Hypernets -- Good (G)news for Gnutella

Red Roo writes: "This online article addresses the recent criticism of Gnutella network scalability by pointing out that it is a Cayley tree. As a viable candidate for massively scalable P2P bandwidth, all trees are dead! But by going to higher dimensional virtual networks (aka "hypernets") e.g., hypercubes or hypertori, near linear scalability can be achieved for P2P populations on the order of several million peers each with only 20 open connections. This concept seems to have been entirely overlooked by critics and developers alike."

Comments

The Fly In The Hypernet Ointment

[Anonymous Coward]

I had a four dimensional hypernet using a router from Heinlein Technologies installed in our off-site server room and it caused no end of grief.

Firstly we had a continuing problem with dropped packets but things started really screwing up when our time domain packet switching starting picking up packets that HAD NOT BEEN SENT YET!

The collision rate went up to an astounding 53% by the time I was able to pull the plug. In short It sucked big time!

By the way - don't waste your time buying any of those California lotto tickets this week because just before I downed the thing I surfed the net....

p2p evolution

[nabucco]

It should be noted that in it's evolution since the Nullsoft Gnutella 0.56 server/client, modern Gnutella servents have reduced traffic and improved network scalability by means of
- routing pushes instead of broadcasting them
- caching pings/pongs, and even queryhits
- use of UltraPeer/leaf relationship, which increases the speed at which traffic is routed

There are other ideas that Gnutella developers like those at Limewire have been kicking around, which are similar to ideas that publishing networks like Freenet and MojoNation have, such as data specialization (ie. queries are directed to those likely to have the data, not broadcast to the entire world).

I'm glad whenever mathematicians or people with specialities like traffic analysis examine existing p2p systems, or give their ideas on p2p systems - they might come up with some good ideas or give a good critique that clarifies elements of a p2p network. This paper is certainly less arrogant than ones with names like "Why Gnutella Can't Scale. No Really". A hypernet is an interesting idea, although I can think of a number of reasons why current p2p sharing networks would not implement them. Namely, because authoritarian networks like Napster were shut down by trade associations like the MPAA/RIAA, while more anarchic networks like Gnutella are more immune from such actions - we must consider not only the survival of the scaling network due to technical constraints like Dr. Gunther does, but also it's survival due to legal constraints orchestrated by large corporations. Then there's the question of how many peers the network is designed for - scalability is just one factor in the reasons why I would use a particular p2p client. Luckily, we will have competition between p2p networks like FastTrack, Gnutella, Freenet and MNet (Mojonation), and perhaps different ones will be used for different purposes, just like Usenet, distributed.net and so forth.

Trouble: this network topology requires authority

[shimmin]

While the article is interesting in the sense that it shows that efficient p2p network topolgies are possible (for suitably small definitions of efficient), actually implementing it on a network of untrusted peers could be problematic.

This is because it assumes the peers are already arranged in the network in the topology one wants.

If a central addressing authority exists, it is no problem to simply give new peers addresses and the addresses of their neighbors in such a way that the network acquires any topolgy the authority wants. The authority can even cope with peers leaving the network more or less arbitrarily.

However, a real question is -- how do you get peers to "self-assemble" into the desired topology in such a way that a small population of peers that choose not to play by the generally accepted rules cannot dramatically effect the outcome. In other words, how can peers be persuaded to place themselves on the points of a cubic hyperlattice solely by contacting a few already installed peers, some of which may not be telling the truth?

That's an odd way to explain it...

[Nindalf]

A Cayley tree is a tree (network with no cycles, a cycle being a set of connections a path you can take in a circle to get back to the same node) in which every node, except those right at the edges, has the same number of connections. As a tree, if you cut any connection, you're seperating the network into two unconnected networks (or isolating one node). Noting that it's a Cayley tree is pointing out that as it grows, nodes at the edges have more and more connections between them (all clients connecting to one server would be a tree, too, but the number of connections to the server would keep on growing, which means it wouldn't be a Cayley tree).

A hypernet is like a grid: imagine the nodes like the places where the lines cross on graph paper, so each node (except at the edges) is connected to 4 others, in a regular, predictable pattern with lots of cycles. Now imagine a 3d grid, like a lot of stacked sheets of graph paper with each node connected not only North, East, South, and West, but also up and down. Each connected to 6 others, in a regular, predictable pattern with lots of cycles. That's as far as you can go with physical models, but in a freely-connecting network like the internet, you can keep going to 8 connections per node (a 4-dimensional hypercube network), 10 connections (5 dimensions), and so on.

That explanation was for a hypercube, a hypertorus would be like going from a bunch of connections around a circle, to a regular set of connections over the surface of a donut, and so forth.

Either way, it's one huge mass of cycles, lots of redundancy, lots of routing choices. If you cut a connection it doesn't matter much; naturally if one user bogs a connection (or chain of connections) down with a heavy load, it's practically like it's been cut. Hypernetworks give you the freedom to route around traffic jams, and the regular structure (cube or torus) simplifies the routing over an unstructured network of random connections.

Implementing the bear

[MarkusQ]

Now implementing a dynamic network in a hypercude or hypertoroid topology brings on a new set of problems such as dynamically re-allocating the hypercude node addresses as users fall off and climb back on to the network. This can be more of a bear than people realize.

This shouldn't be too hard (at least it doesn't look too hard sitting here on a Sunday morning, half way through my first cup of liquid brains). The key is to note that we can't (and therefore needn't bother trying to) enforce the topology at all times. Instead, we just want to bias the network towards the desired form. For example:

New nodes pick a random twenty+ bit ID. This would probably not be enough to prevent collisions, (cf the Birthday Paradox) but that can be dealt with presently. New nodes connect up to whoever then can find. This would be pretty much what happens on most p2p now. Once the node has the desired number of connections, it can rank them by comparing the number of bits its ID has in common with the IDs of each peer (the Hamming Distance between the IDs). As further peers are discovered, it can establish connections to any that are Hamming-closer than its worst ranked peer and drop the worst ranked peers from its connections. Likewise, if a node detects a pair of peers that are Hamming-closer to each other than either is to it, it can "introduce" them to each other. If two peers meet and discover they have the same randomly chosen ID, the younger can flip one bit (for each ID bit, count the number of ctive connections that differ on that bit; flip one with the max count) and continue. Fat pipe peers can run more than one ID if they wish (cf UltraPeers)

This should at least be functional; no doubt there are a number of clever hacks that could be made...

-- MarkusQ

Re:Trouble: this network topology requires authori

[Salamander]

While the article is interesting in the sense that it shows that efficient p2p network topolgies are possible (for suitably small definitions of efficient), actually implementing it on a network of untrusted peers could be problematic.

...to say the least. Besides the obvious algorithmic problems of establishing and/or maintaining such a topology in an environment where nodes enter and leave at such a high rate, there's a serious overhead issue. Any serious discussion of ad-hoc routing protocols (which is what this is) nowadays needs to include an analysis of the number of packets needed by the routing protocol itself, in addition to the efficiency with which "user" packets are routed. A network that always delivers user packets over an optimal path isn't really all that useful if 90% of the network's capacity is consumed by route updates. I was very disappointed to see that this particular paper attempts no such analysis of routing overhead; without it, the paper's conclusions must be regarded as highly suspect.

This paper's math is flawed

[jeske]

The author is using bandwidth calculations intended for physical network topologies and applying them to virtual networks. This is flawed and renders his analysis invalid.

In layman's terms. If you are a node in one of his example networks, and you're sitting on a DSL connection, does the available bandwidth you contribute to the net change whether you have 20 outbound TCP connections or 2? No. It is constant. The author incorrectly computes the "bandwidth" of these different network topologies like you are stringing a separate DSL to each person you open a TCP connection to.

Available network bandwidth in a peer network like Gnutella is related only to the physical interconnect of the nodes. (i.e. whether they are on an SBC DSL line or sitting a North American OC-3)

The only useful analysis is that which determines the amount of data-transfer required between each node (and all nodes) for common operations when using different topologies. When performing this study, you are looking for the topology which will transfer the smallest amount of data over the smallest number of nodes when performing searches. For a great analysis, see the Gnutella Performance Paper by Ritter, referenced by the above paper.

Careful analysis will tell you the same thing that common sense does -- that the best architecture involves centralized dedicated servers (supernodes), located on machines with the largest physical bandwidth available. (i.e. eactly what Napster did. )

In order to create an efficient peer network which scales, Gnutella 'merely' needs to 1) order the network by physical topology, 2) identify the nodes with the best combination of physical bandwidth, longevity, and CPU/disk resources, and 3) fully utilize those machines as supernodes.

Good luck. :)