Slashdot Mirror

← Back to Stories (view on slashdot.org)

Hypernets -- Good (G)news for Gnutella

Posted by timothy on from the network-arcana dept.

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."

2 of 169 comments (clear)

  1. p2p evolution by nabucco · · Score: 5, Interesting

    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.

  2. Implementing the bear by MarkusQ · · Score: 5, Interesting
    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