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

Re:More connections == Better network?

[kris_lang]

Actually, there was a system in the 1980s that did implement a 10-dimensional binary hypercube topology for communication and implemented it well. Daniel Hillis' Thinking Machine was a highly parallel 1024 node machine which implemented inter-node communication via a 10-bit binary hypercube address system.

Despite what one of the other posters has said about "binary hypercubes" being nonsensical, they are simply a way of describing the nodes of a hypercube with a binary address. Each node in a 1024 node network has a ten bit address. Each one has to connect only to ten other nodes: the ten nodes which are specified by flipping only ONE bit on that nodes address. This provides multiple redundant paths by which a message can be routed in the case of the failure or congestion of a node.

And by intermittently polling the other nodes to which it connects, it can keep a routing table which optimizes the paths to be used. The major difference is that in Hillis' Thinking Machines the number of nodes was capped, in fact it was a fixed number of nodes. 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.

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.

Re:Good lord!!!

[GigsVT]

Even though you might have been trying to be a little facetious, I think your point is very valid.

I can grab files, with no small amount of effort, from an online file sharing service, and maybe get 2 GB a day. If I network, in person, with people who share similar tastes in music, I can get a lot more bang for the buck. As soon as we see larger portable technologies (It's already happening), trading media will be just like trading games in user groups was back in the 80s and early 90s. We all just bring our 300GB portable disks to meetings, link them all up, and take them home to copy onto our TB home systems.

The only thing that would prevent this from happening is a very rapid growth of broadband, to something like reliable 10Mbit levels. I don't see that happening before hard disk space grows to the sizes I quoted above.

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

huh?

[Magila]

While I admit I have no clue what the article is talking about (hyper what?), I was under the impression we could already do better than linear scalability with a simple hierarchical P2P network. Just have a dynamic cluster of loosely connected "servers" to which clients maintain a persistent connection to only one. With a little intelligent routing of queries between servers (i.e. don't just spit the querey out to all the other servers you know) you get O(1) scalability at the client side and something (probably significantly) better than O(n) on the server side.