Slashdot Mirror


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

62 of 169 comments (clear)

  1. The Fly In The Hypernet Ointment by Anonymous Coward · · Score: 5, Funny

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

    1. Re:The Fly In The Hypernet Ointment by evilviper · · Score: 2

      OF course you realize that 4-D would simply be 3-D space+Time. If you've got a 3-D router (or a 3-D world for that matter) NOTHING WOULD EVER HAPPEN.

      So, because of the fact that your router is not frozen in time, you can see the future?

      Besides, I can't remeber the last time I went to the lotto website and it wasn't down.

      --
      Slashdot gets worse every day... Pipedot: News for nerds, without the corporate slant
  2. More Info by Mattygfunk · · Score: 3, Informative

    For more information on the structure try Relation Nets and Hypernets in pdf form.

  3. wish I understood this kind of math by t0qer · · Score: 2, Offtopic

    Anyone have any good learn math links?

    1. Re:wish I understood this kind of math by Andux · · Score: 2, Informative
      Allow me to translate:

      Cayley Tree - A network where the nodes are connected together without any central server.

      Hypernet - A network where smaller nodes connect to high-capacity supernodes, which are in turn connected to other supernodes, each with their own sub-network, i.e. the same thing as FastTrack, but without the central encryption servers (at least, that's how I understand it).

      In short, this is good technology, but, once you scrape the marketing bullshit off, hardly new.

      --
      (Do not sign anything.) -- Fell, Planescape: Torment
    2. Re:wish I understood this kind of math by Perdo · · Score: 2
      --

      If voting were effective, it would be illegal by now.

    3. Re:wish I understood this kind of math by stevew · · Score: 2

      Now it has been A LONG time since i could have answered this authoritively - BUT - I'm pretty sure that the hypercube being mentioned in the article is a mathematical construct so your definition of Hypernet may not be real appropriate. A hypercube is a 4 dimensional construct if I remember.

      There were supercomputers built by Intel in the early 90's that used hypercube connectivity schemes to minimize connection times for data as I recall. This has been done before.

      --
      Have you compiled your kernel today??
    4. Re:wish I understood this kind of math by talonyx · · Score: 2

      Here, mesmerize yourself looking at some four dimensional shapes, courtesy of the elite Ken Perlin.

      (Note: This page is much more fun while under the influence of hallucinogenics.)

  4. Neil Gunther and PDQ software by Anonymous Coward · · Score: 4, Informative

    The author, Neil Gunther is semi-famous
    in the Unix community for giving very
    good talks and courses on performance.

    Check out his open source performance analysis
    softwar PDQ (Pretty Damn Quick)

    http://www.perfdynamics.com/Tools/PDQ.html

  5. A bit harsh for dear Neil eh? :) by arnoroefs2000 · · Score: 2


    Neil J. Gunther (author of afore mentioned article)

    "was born in Melbourne, Australia. He holds undergraduate degrees in Chemistry and Physics, a Masters Degree in Applied Mathematics (1976) from La Trobe University, Australia, and a Doctorate in Theoretical Physics (1980) from the University of Southampton, England."

    Gore

    "was born on March 31, 1948, and is the son of former U.S. Senator Albert Gore, Sr. and Pauline Gore. Raised in Carthage, Tennessee, and Washington, D.C., he received a degree in government with honors from Harvard University in 1969. After graduation, he volunteered for enlistment in the U.S. Army and served in Vietnam."

    1. Re:A bit harsh for dear Neil eh? :) by Perdo · · Score: 2

      So since he does this for a living does he sue gnutella for using his idea after they have implemented it?

      --

      If voting were effective, it would be illegal by now.

  6. More connections == Better network? by Matrian · · Score: 2, Interesting

    As far as I can tell, what this is saying is that Gnutella is scaleable because it doesn't use a tree, (with each node connected to only a few 'nearby' others) but rather as a more complex graph, with each node having connections to many nodes which aren't really nearby. In a true tree, there's really only one route from one node to another. In contrast, a hypercube has many many paths from one node to another.

    In reality, I'm pretty sure no actual large-scale networks are like this, for obvious reasons, but I surmise they tend to be more treelike than gnutella is, where each client tends to try to make as many connections to other clients as it can. Therefore, it should be pretty scaleable; since if each new client is making connections to a bunch of other clinets that might not otherwise have a short distance between them, there aren't really goingto be any bottlenecks.

    1. Re:More connections == Better network? by kris_lang · · Score: 4, Interesting
      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.

  7. Good lord!!! by powerlinekid · · Score: 2

    Hyper-cube? Cylnar tree? All this for giving someone else a file? What happened to the good old days when you either used ftp or walked over and gave the guy a floppy.

    --

    can't sleep slashdot will eat me
    1. Re:Good lord!!! by GigsVT · · Score: 3, Interesting

      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.

      --
      I've had enough abrasive sigs. Kittens are cute and fuzzy.
    2. Re:Good lord!!! by powerlinekid · · Score: 2

      I aim to be honest yet sarcastic. Anyway, me and my friends just use cd-rw to trade big stuff. Otherwise theres nothing I really need that I can't get with my modem and 3 hours between 3-6AM ;-).

      python & forte 3.0 tonite and java 1.4 last nite... not bad for 6.5 kB max bandwidth per sec (56kb modem is 6.5 kB transfer rate... I think they probably just use bit to make it sound faster).

      --

      can't sleep slashdot will eat me
  8. Correct me if I'm wrong. by Rhinobird · · Score: 3, Insightful

    Correct me if I'm wrong here, but, the article seems to be saying that packet switching is more effiecient than old style circuit switching (?hierarchal switcing?). It says that bouncing stuff around nodes connected to a bunch of other nodes and letting the stuff find a path to its destination is more effiecient and scalable than any kind of tree structure where stuff goes down to the trunk and back up to a different branch to reach its destination.

    Unfortunately with the way things are set up right now, I think our beloved internet is set up like a toroid instead of a cube. You have a backbone as the middle loop and then coming off of it are rings that are local that provide service to local ISPs. Then they sell to thier end users. In the end I picture a fuzzy torroid. And according to the article, those are more scalable than trees, but not as much as the cube. However the article says that they are harder to implement than the cubes, not so, as they seem to have evolved in the marketplace naturally, and setting up a cube like network in the real world is harder.

    But they're talking about this applied to software, and virtual networks, not real world hardware. However, seeing as how the real world has moved from a tree based telecom system, to the torroid sceme of the current system, it would be interesting to see what happens when the torroidal system in the real world runs into scalability problems and goes for the cube.

    --
    If Mr. Edison had thought smarter he wouldn't sweat as much. --Nikola Tesla
    1. Re:Correct me if I'm wrong. by mindstrm · · Score: 2

      Well.. to have a huge search network.. this is better.

      As long as it has some sort of geometric shape, we can make searching more efficient.

      Gnutella has no shape, It's a handful of spaghetti thrown on the floor.

      The there's Fastrack.. it's like throwing a handful of spaghettios on top of the first pile of spaghetti.

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

  10. Re:what a crock by Perdo · · Score: 4, Informative
    --

    If voting were effective, it would be illegal by now.

  11. Re:Don't break out the champagne yet... by DrSkwid · · Score: 3, Insightful

    I'm not one for saying "it'll never happen" because sometimes if you just sit there that's exactly what happens.

    But I'm not convinvced of this particular threat.
    It would require worldwide cooperation and at every level of computing. It would be difficult to draft an international law AND define what a computer was. Does my digital watch need DRM?

    To get this law in one country (probably the US) is going to have to implement it unilaterally. Chaos will ensue. I think it's just too much hassle for a government to embark on.

    So mark my words, and then punch me with them when you can't play your .ogg files no more.

    --
    There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
  12. Re:Does it matter? by GigsVT · · Score: 3, Insightful

    You don't pay enough to suck down all your bandwidth 24/7. If you were led to believe that was your right when you bought your broadband, then I'm sorry you were misled, but the only people who are sold lines that they are allowed to max out 24/7 are the people that pay for real Internet access, i.e. a T1 from a first tier provider. Otherwise, you have to share.

    --
    I've had enough abrasive sigs. Kittens are cute and fuzzy.
  13. Hypercube by nr · · Score: 3, Informative

    Dont know what a hypercube is? click here

  14. Already being implemented. by RobL3 · · Score: 3, Informative

    A form of this organizational structure is already being implemented by Lime wire. Here is an excerpt from thier FAQ:

    we've created a new Gnutella hierarchy, whereby high performance machines become 'Ultrapeers'. These machines accept connections from many LimeWire clients while also connecting to the rest of the Gnutella network. Moreover, the Ultrapeer shields these 'regular' LimeWire clients from the CPU and bandwidth requirements associated with Gnutella, directing traffic to clients in an efficient manner. The reason you see only one connection in your connections tab is because you are a LimeWire client connected to an Ultrapeer. Unfortunately, not all Ultrapeers are as good as others. If you find that you aren't getting many search results with the Ultrapeer you are connected to, simply disconnect and connect. You'll probably connect to a different Ultrapeer, which is more 'connected'. Also, as time goes on and the network grows, you'll receive more results. Moreover, we are currently working hard to ensure that any Ultrapeer you connect to will be well connected - stay tuned to future versions of LimeWire.

    My success with the new structure is mixed. Downloads and searches seem to work almost as well as before, but I'm getting considerably fewer uploads, which must mean that, someone, somewhere, is getting screwed. Limewire itself is not a bad little product, it's main claim to fame, of course, is that it runs well on both Mac OS X and Linux.

  15. Prototype P2P s/w in 64-dimensional binary space by Anonymous Coward · · Score: 2, Interesting

    I don't have a /. account yet, but I do have written a (prototype) P2P agent that uses a 64-dimensional binary space to arrange itself. This allows for non-centralized address resolution in an statistically well distributed network.

    Every node takes a random 64-bit number as address (collisions are possible but unlikely with 64 bits) and once seeded searches to position itself within its closest peers. The distance to another node is simply the number of different bits in the address (plus a higher weighting of high bits in case of a tie).

    Upon this infrastructure, a group mechanism is implemented, where any member of a group stores all directory information for that group, and a list of known hosts for the identified content, as well as the peers for the next group.

    Groups are hierarchically arranged, like a directory. Membership in one group mandates membership in all "higher" groups, up to the "root" group. Therefore, it is possible to navigate through the whole system like through a file directory tree.

    Source code is available for the Macintosh (think like "Hotline" without servers). It still has a minor memory leak, limiting stability to a couple of hours, and several other drawbacks that prevent it from becoming full featured, like not being able to reach behind NAT, or limited protection against malevolent nodes.

    Ultimately, I stopped development because an IP-to-Content relation can be established and therefore the network is attackable-by-content. If anybody wants to pick it up and push the work ahead, the source (PowerPlant Net classes & UI) is up for grabs. Contact me at "komet163@gmx.net".

    Thought this might interest someone in the context of this multidimensional network discussion...

  16. Trouble: this network topology requires authority by shimmin · · Score: 5, Insightful
    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?

  17. Pounding a dead monkey by Anonymous Coward · · Score: 2, Insightful

    I really cannot understand why we keep harping on about gnutella. Gnutella was the experiment, and not the solution to all your file sharing needs. Ever.
    Just get over it. Gnutella came, was good, and went. Now there are better things. Kazaa/FastTrack. Distributed Napster. Etc.
    Stop trying to add new components to you VW bug, when there are Ferraris to be had.

    Hopfrog.

  18. Exactly backwards by MarkusQ · · Score: 4, Insightful
    ...modern Gnutella servents have reduced traffic and improved network scalability by means of...use of UltraPeer/leaf relationship

    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.

    I think your concern here is exactly backwards. Specifically, higher dimensional topology would decrease the need for central "UltraPeer"s (also known as lawyer bait) and thus make the network harder to shut down. If the trend towards depending more on some "peers" than others continues to the natural limit, you wind up right back at Napster (one UberUltraPeer to rule them all, and in the darkness...get eaten by a grue if it's lucky, sued by the RIAA if it's not).

    On the other hand, if the topology is made more scalable, the targets won't be as tempting at any given network size, and the whole thing would be harder to take down by force. If all nodes are equal, cutting one will likely create enough publicity to attract seven more to take its place.

    -- MarkusQ

  19. Hypercubes and fat trees by Huusker · · Score: 2
    Hypercubes have been around for a long time. The first commercial implementation was the Connection Machine CM-2 circa 1985 by Thinking Machines Corporation. Its a rather cool box with lots of blinky lights. Its successor, the CM-5, used a fat tree network, which was a more economical way of achieving scalable bandwidth.

    Thinking Machines Corp went out of business around 1994.

  20. That's an odd way to explain it... by Nindalf · · Score: 5, Informative

    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.

  21. Beware WIPO and Geneva by FreeUser · · Score: 2

    It would require worldwide cooperation and at every level of computing. It would be difficult to draft an international law AND define what a computer was. Does my digital watch need DRM?

    We, all of us, tend to concentrate more on our own domestic politics than international political trends, especially when thinking and discussing things like privacy, encryption, and yes, the digital copy prevention technology euphemisticly referred to as digitial rights management (DRM).

    But keep in mind that the Hague convention is already passing and allows, indeed requires, any national law regarding copyright (and via the DMCA that includes copy protection, i.e. DRM) to be applied to every signatory country.

    And there are other treaties being railroaded through Geneva by the Copyright Cartels as we discuss this.

    I too once hoped that the DMCA would make the United States so uncompetetive that the problem would be self-solving. This would be true, were it not for the fact that the corporate interests pushing these sorts of things are doing so internationally (both locally in various parliaments, eg. the UK, the EU as a whole, and Australia and at the international treaty level).

    In five or ten years Americans unilateral rewrite of copyright law into criminal law would make it uncompetetive in the new, digital economy (with ripple effects into other parts of the economoy most likely), but we are not going to have five or ten years before things like the DMCA become international law and the playing field levelled once more, at a much lower common denominator.

    --
    The Future of Human Evolution: Autonomy
  22. Wrong. by TheSHAD0W · · Score: 2

    This sounds like a great idea, but unfortunately, it's dead wrong.

    Moving to a higher order of dimensions of course makes the maximum path length shorter; but it also makes the number of edges per vertex increase. Or, in other words, the number of simultaneous connections needed. Most GNet users have already pushed the number of simultaneous connections up to the maximum they can handle, thanks to bandwidth limitations, and are still experiencing the scaling problem.

    I'm convinced the ultimate solution is a hybrid between Napster and Gnutella, with most end users connecting up like Napster clients, and a few volunteering to be index nodes, with a GNet-type organization between them.

    1. Re:Wrong. by Catbeller · · Score: 2

      Bandwidth limitations: artificial, and should never have happened. But now that the content providers are becoming the bandwidth providers, we won't get bandwidth to burn anymore. Though 802.11 networks might give us the capability sometime, since they are constrained by neither profit nor control.

      Hybrid Napster/Gnutellas: now legally impossible in the U.S., and shortly everywhere else in the world. Any volunteer index node owners would be in a world of legal pain, with their homes and future threatened. So sadly, not an option.

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

    1. Re:Implementing the bear by Salamander · · Score: 2
      we just want to bias the network towards the desired form. For example...New nodes pick a random twenty+ bit ID...New nodes connect up to whoever then can find.

      Except that you describe routing based on Hamming distance (which won't work because of looping issues) rather than shared prefix/suffix, this sounds a lot like Tapestry.

      --
      Slashdot - News for Herds. Stuff that Splatters.
    2. Re:Implementing the bear by MarkusQ · · Score: 2
      MarkusQ :we just want to bias the network towards the desired form. For example...New nodes pick a random twenty+ bit ID...New nodes connect up to whoever then can find.

      Salamander: Except that you describe routing based on Hamming distance (which won't work because of looping issues) rather than shared prefix/suffix, this sounds a lot like Tapestry.

      Actually, I was just using the Hamming distance as a rough gauge for "how far is this node from where it should be in a perfect binary hyper-cube" (since in a perfect binary hyper-cube, each node is connected to all the nodes (and only the nodes) at hamming-distance 1 from its ID. So what I described was a way to 1) pick a corner at random, 2) wander towards it, and 3) go to another nearby location if the one you picked turns out to be occupied.

      I'm not familiar with the looping issues you refer to. Can you elucidate? (Note also that this would not be so much a way to "route" as a way to "partially broadcast" (e.g., maybe decrement TTL by two when sending "in the wrong direction" or propogate ox-bow removal info when something is broadcast to you via a sub-optimal path). We wouldn't count on nodes being where they should be, just hamming-close.)

      -- MarkusQ

    3. Re:Implementing the bear by Salamander · · Score: 2
      I'm not familiar with the looping issues you refer to. Can you elucidate? (Note also that this would not be so much a way to "route"

      You're right. I was conflating the issue of how to establish and maintain a topology with that of how to route messages within that topology. I tend to do that, because I find that in real systems the interactions between these two supposedly-separate issues are so strong that they become inseparable.

      Upon reflection, I find it hard to judge how well a system such as yours would work. On the one hand, you might run into a classic hill-climbing problem. Two nodes that "should be" adjacent to each other in a nearly-ideal hypercube might be too far separated (in terms of the underlying IP network) initially to find each other before they each settle on local maxima instead. On the other hand, it might not be good thing if they did find each other, because you might end up with a really neat hypercube at the upper level, but each "adjacency" in the hypercube is really a long multihop route across the continent at the lower level.

      Trying to find a balance between these two extremes might be difficult. In fact, trying to impose a hypercube overlay-network topology on top of an IP network whose physical structure is most definitely not hypercube-like might be a fundamentally doomed idea. I don't mean to say it's not worth it to try. Only detailed simulation or even real-life deployment can truly provide the answers to these sorts of questions. I'm just saying that this particular problem domain tends to be "swampy"; things that appear promising at first run into pitfalls much further down the road, much to everyone's frustration and indignation.

      --
      Slashdot - News for Herds. Stuff that Splatters.
    4. Re:Implementing the bear by MarkusQ · · Score: 2
      Neat idea, only not a very feasible one. You want to have "short" edges in your hypercube in order do reduce the network load and latency. You are in effect organizing a virtual hypercube network on top of a mix of graph- and tree-oriented physical networks. You need to have the hypercube topology make sure that a limited number of physical nodes are in the path between each virtual node.

      Excelent point.

      Even a quite large hammer won't change this.

      But a clever wrench might. Hmmm. Let me think on it...

      -- MarkusQ

    5. Re:Implementing the bear by MarkusQ · · Score: 2
      Only detailed simulation or even real-life deployment can truly provide the answers to these sorts of questions. I'm just saying that this particular problem domain tends to be "swampy"; things that appear promising at first run into pitfalls much further down the road, much to everyone's frustration and indignation.

      *smile* That's why in real life I tent to bid such jobs by the hour rather than by the project.

      -- MarkusQ

    6. Re:Implementing the bear by MarkusQ · · Score: 2
      Or why not go with a 32-dimensional hypersphere. It seems to me we already have that address space handled, routing and all-- IPv4.

      Sounds good...I'm reluctant to give up the random address selection but this seems reasonable...hmmm...

      -- MarkusQ

  24. Re:Trouble: this network topology requires authori by wfrp01 · · Score: 3, Insightful

    Exactly.

    Moreover, what are we to make of this?

    The dominant constraint for hardware implementations of high-dimensional networks is the cost of the physical wires on the interconnect backplane. Since the hypernets discussed here would be implemented in software, no such constraints would prevent reaching the desired level of scalability.

    I really don't see how you can sweep the actual physical infrastrucure under the rug like this. Eventually, virtual hypercubes turn into real packets on a real network. A network that is subject to the very same topological limitations this article discusses. Any wonder that the Tandem Himalaya architecture he mentions was implemented in hardware, rather than as a "virtual" topology implemented on top of a traditional TCP/IP network?

    When it comes to complicated mathematics like this, though, intuition has often led me astray...

    --

    --Lawrence Lessig for Congress!
  25. -1 Troll on the MQR standard by MarkusQ · · Score: 3, Insightful

    I can't believe Slashdot just posts this psuedomathematical nonsense without doing even elementary fact-checking

    At first, I thought you were refering to your own post, and was tempted to give you a couteracting +1 Insightful.

    -- MarkusQ

  26. All of us users just know it works by LM741N · · Score: 2, Insightful

    You can do all the computer simulations you want of the Gnutella network, but I know that it just works. I've never had any problems finding music that I want, its just that it takes a little more time. Its kind of like stamp collecting. Even after Napster fell and there was an upsurge in nodes, I was still able to use it well. Who cares if you are on a subnet of Gnutella if you still find the music you want?

  27. Re:Trouble: this network topology requires authori by Salamander · · Score: 5, Informative
    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.

    --
    Slashdot - News for Herds. Stuff that Splatters.
  28. "Overlooked" beacause it's a CROCK of CRAP by plastik55 · · Score: 4, Informative
    You can turn the Gnutella network into some kind of "virtual" hypercube or hypertorus all you like, but that doesn't change the physical reality of the system, viz:

    The Internet has a structure with physical limitations!

    What good does it do if your many multiply redundant connections allow transmission of messages with a fewer number of virtual hops, when every connection going out of your college dorm goes over the same physical wire. The number of connections over which a search request must travel is a liability, not an asset, when many of those connections happen to use the same physical wire. The author of this "paper" has conveniently ignored this fact, and his conclusion (that adding virtual links to your network allows you to manufacture bandwidth out of thin air) follows directly.

    On a separate topic, the assertion that the virtual connectivity of Gnutella is anything like a Cayley tree is absurd, because it implies no closed paths. Consider: In order to discover and connect to a new a host on the Gnutella network, you need to catch a search request originating from that host. The fact that you were able to recieve that search request in the first place means that there was already a path between you and the remote host--therefore you have created at least one closed cycle by forming the new connection.

    --

    I have a positive modifier on Troll. When I mod someone Troll their karma should go UP!

    1. Re:"Overlooked" beacause it's a CROCK of CRAP by justin.warren · · Score: 3, Insightful
      You appear to have failed to grasp the true meaning of this paper. It is not saying "Scrap all that Gnutella is! It's a load of $EXCREMENT!" It is providing an alternative internetworking topology based on mathematical theory that provides a higher theoretical bandwidth utilisation than is currently enjoyed when the network scales to a large number of nodes.

      To simplify: If the Gnutella network used a different node addressing (and associated routing) scheme, total aggregate bandwidth of the entire network would be increased, even as the network scaled upwards of a million nodes.

      The underlying physical wiring is exactly the same for this method as for the existing Gnutella topology. That's the whole point. By simply changing the way Gnutella nodes connect to one another you can increase the aggregate network efficiency. It isn't manufacturing bandwidth out of thin air, it is making more efficient use of what is already there. Read over sections 4 and 5 again perhaps.

      Finally, I have to admit to being somewhat boggled by your last paragraph. Are you suggesting that in order to become part of a network you must be part of the network already? Various routing protocols have solutions for how to dynamically insert a new node into a topology. STP, OSPF and EIGRP have differing methods, not particularly analagous to Gnutella, but useful nonetheless. A 'closed cycle' as you refer to it could also be thought of as a routing loop. It is possible to have multiple paths and not have a routing loop, something routing protocols are generally designed to prevent. What you're talking about here is that you have to have connectivity into a network in order to become a part of the network, which is somewhat obvious. I mean, it does generally work better if you plug it in.

      --
      Just because you're paranoid doesn't mean they're NOT after you.
  29. Says nothing about Gnutella's scalability by Sanity · · Score: 3, Insightful
    The effectiveness of a search in Gnutella is directly proportional to the number of nodes who receive the query. This paper really only talks about the order in which those queries would be received by those nodes, which is - of course - largely irrelevant.

    Until Gnutella starts directing searches intelligently - towards nodes which are more likely to have the data being sought, as Freenet does, it will always be an inefficient way to search for data.

  30. Question ... by flufffy · · Score: 2
    I have a question. I am interested in but know next to nothing about this stuff. I was wondering if anyone could tell me whether the networks that are being talked about in these articles are theoretical ideals that are different in form as networks that are actually in use.

    As far as I understand it, a lot of the models used in scalability analyses of Gnutella seem to assume a homogeneously connected network. Whereas analyses of the Internet show there to be (a) a few highly connected sites (b) a large number of sites that are not well connected at all, and (c) a tendency for new network connections to appear on already well-connected sites, rather than on less-well connected ones.

    I was wondering if there would be a difference between a network's scalability if (a) the distribution of edges between nodes was considered homogeneous, or if (b) the distribution of nodes was considered as skewed (e.fg. a Zipf distribution). Is case (b) more scalable than case (a)?

    Thanks.

    1. Re:Question ... by flufffy · · Score: 2

      Hey, thanks.

  31. huh? by Magila · · Score: 3, Interesting

    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.

  32. After a little thought.. by MarkusQ · · Score: 2
    You want to have "short" edges in your hypercube in order do reduce the network load and latency. You are in effect organizing a virtual hypercube network on top of a mix of graph- and tree-oriented physical networks. You need to have the hypercube topology make sure that a limited number of physical nodes are in the path between each virtual node.

    Not really. If the present system is tree-on-(uncorrelated)tree, you are still better off going to hypercube-on-(uncorrelated)tree. I agree that you'd be much better off going to a hypercube-on-tree where the hypercube is "rotated" to align with short hops, but that doesn't mean you have to do it that way.

    Given that we can't do it perfectly, we can still try to do "reasonably well". As a first stab:

    Impose a finer grained (say, 16 bits for each bit of the ID) latice on the space. Have every node keep 3+ IDs active (using the rules in my prior post). Track average ping times (using the latice) and periodically introduce new IDs chosen to move you hamming-closer to nodes which are ping-closer, and at the same time gracefully retire IDs that aren't so aligned.
    This should drift towards shorter edges without breaking the pseudo-hypercube. Even though you have more IDs active, it shouldn't affect the amount of traffic at each node if the routing/broadcast rules are set up right. Note also that there is no additional routing trafic required to do this.

    Keep in mind that some problems are very hard to solve but easy to aproximate; often RightAnswer=NP, 99%Answer=O(N).

    -- MarkusQ

    1. Re:After a little thought.. by MarkusQ · · Score: 2
      You still have a problem, though. You are imposing a routing algorithm based on ping times in a dynamic environment. You will get new nodes, others will disappear, while your routing metric will change wildly over time.

      No, we have a considerable advantage over the military networks; they are responsible for everything (down to making sure there is power, EMP hardening, etc., etc.) while we just have to worry very top. Specifically, the ping times here are at the IP level, not at the p2p level. Since someone else is kind enough to maintain that level for us (and with much greater stability than we could hope for at the p2p layer) the (IP) ping times won't change when (p2p) nodes come & go.

      I don't think your algorithm is dynamic enough to cope without having the nodes broadcast their presence in some way.

      Announce, yes. Broadcast, no. In a world with no cheaters, all you need to do (once connected to the network) is talk to your peers (& nodes they refer you to). No broadcasts needed.

      If there are cheaters, you need to do a bit more (e.g. buffer & broadcast proportionate to the depth of the expected cheating). It might seem like this would be an open ended arms race, but in order to pass as good nodes the cheaters would have to act like good nodes and if things go far enough the only way to cheat would be to be a good node for a significant fraction of the time. So you wind you winning after all, at least as far as the network topology goes.

      As for dealing with cheaters, it just moves the problem to a new level (I won't go into more details since I don't want to give any ideas to the bad guys), but as far as I can see it wouldn't be any worse than what those gnutty lime guys face now. Ultimately, the bad guys could get themselves spiffy uniforms and go door to door with guns, matches & branding irons.

      I don't know of a topology that could handle that.

      -- MarkusQ

  33. Umm... by TheSHAD0W · · Score: 2

    Point one: Bandwidth limitations aren't entirely artificial, and are undeniably there for people who don't have DSL or cable connections. A network where everyone has a 20-way connection would require something like 100K/s (800kbps) of throughput per user. Multiply that by the number of users suggested, and the nation's current infrastructure would collapse under its weight.

    Point two: Hybrid Napster/Gnutellas would be no more legally impossible than current peer-to-peer systems are now. Every node is involved in relaying search terms around, and is therefore technically involved in contributory copyright infringement. The only reason Napster went down was because its servers were fixed targets. Volunteer-run servers tied together using a Gnutella-like network could spring up and drop out as necessary, and the network would remain up.

  34. Re:Trouble: this network topology requires authori by Captn+Pepe · · Score: 3, Insightful
    I really don't see how you can sweep the actual physical infrastrucure under the rug like this. Eventually, virtual hypercubes turn into real packets on a real network.

    It doesn't. The problem with the tree topology used by Gnutella is that it utilizes the available bandwidth in a fashion that becomes highly inefficient as the number of nodes becomes large. At around 10^6 nodes, it uses 15-20% of the total available capacity, whereas a hypercube topology at 10^6 nodes uses essentially 100% of the available bandwidth.

    So obviously, if your application runs up against the physical capacity of your underlying communications systems, you can't send more data. But via correct choices of virtual network topology, you can ensure that the physical capacity is being used productively.

    --

    Quantum mechanics: the dreams that stuff is made of.
  35. This paper's math is flawed by jeske · · Score: 5, Insightful
    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. :)

    1. Re:This paper's math is flawed by Salamander · · Score: 2
      Instead of sucking up bandwidth on a chain of ten links, this topology might only require two or three hops to get to its destination.

      The problem is that it's not hops in the overlay network that matter; it's hops in the underlying IP network. Your "two or three hops" in the overlay network might actually involve a dozen 33K modem links in the physical network, whereas a "less optimal" five- or six-hop route in a better-constructed overlay network might involve only eight physical nodes and nothing less than a T1 between them.

      This mismatch between the overlay and physical networks is precisely what caused the famous Gnutella meltdown, as slow modem links saturated by search traffic effectively went down, leaving the network partitioned into a bunch of tiny little islands. This "hypernet" idea is topologically naive in almost exactly the same way, with predictable results. There's nothing in the proposal to prevent the creation of four-hop routes that make two complete trips around the world; such routes may appear "efficient" to a CEO or marketing guy, but to anyone who actually knows about networks it would clearly be otherwise.

      --
      Slashdot - News for Herds. Stuff that Splatters.
  36. Re:Trouble: this network topology requires authori by wfrp01 · · Score: 2

    via correct choices of virtual network topology, you can ensure that the physical capacity is being used productively.

    Would you say that the performance of the system would depend on your choice of which virtual nodes are connected to which other virtual nodes? Or can you say that the performance of a virtual hypercube topology can be considered completely independantly of the underlying physical network?

    --

    --Lawrence Lessig for Congress!
  37. Does anybody have a translation? by Brendan+Byrd · · Score: 2

    Google or Babelfish don't have a fuzzy-math-to-English convertor tool.

  38. Re:Questions about implementing the bear. by MarkusQ · · Score: 2
    I should state up front that my first post on this topic was off the cuff & contemporanious with my first cup of coffee this morning, and I've haven't sat down and put anything on paper. So some or all of this may fall flat on more detailed analysis. But with that caveat:

    If you're trying to minimize Hamming distance, wouldn't it be better to establish the first connection without an ID then ask the peer for its ID and the IDs around it? Then we pick a non-occupied one and use it.

    I suppose I'm assuming that there are a relatively few "doors" into the network, and worried about clustering; also, my gut feeling is that starting at a random point lets you disregard a number of potential problems on statistical grounds.

    Then we can just start making connections, getting their IDs, and dropping the furthest out, yes?

    Hmmm. What you are describing (if you drop my assumption of random starting location) results in what is called flocking. Basically, everyone winds up trying to move to the center of the cloud as they see it. Nice dense connectivity, but (since we aren't charged for hamming-distance) there's no real advantage to it, and it increases the risk of fragmentation.

    I like the idea of "introduction" via peers - watch addresses that come by, if one is a certain Hamming distance or shorter away from one of our connections, tell that connection. 's that basically how it works?

    Yep.

    Finding Hamming distance sounds like a parity-class problem (XOR and sum, right?) so it shouldn't be bad at all. Though is there an easier way for the sum part of it than "if the last bit is one, increment counter, rotate right, repeat"? This might not be a problem, and that's an O(n) loop (right?) - not bad, but is there an O(1) solution?

    It's O(n) where n is the number of bits in the address, which scales log(n) with the max size of the network; not bad at all. You could reduce it further by doing a lookup table (array [0..255] of 0..8 = (0..255).collect{ |i| i.bits_set } or some such), but there isn't really any need; the amount of work is << the amount required just to receive a packet.

    Maybe we'll just want to check addresses at random rather than every one - save cycles for more useful things. Also, saturated hosts will probably not even bother with comparisons - if all n of our local peers are right, then why bother?

    Cynical answer: there's no harm (all of this should be very cheap) and we can avoid having the behaviour change after the beast has been running for hours, which would complicate the code and might open the door for mysterious & hard to find bugs. ("It ran fine for about a week, then it just went cross-eyed and dumped grape jelly onto the hard drive!") If I'm going to leave something running for a long time I like (where possible) to have hitting the same code paths at the end as it was in the begining.

    How do we handle address space conflicts? If, say, the network were to partition itself in two, somehow (links just happened to be dropped in the right way), and then a host comes up that bridges the two segments, what do we do? Worse, what happens if two perfect hypercubes overlap [all n connections in each are only one bitflip away, and all have the same numbers]?

    This is one of the "you can ignore it on statistical grounds" points. With random starting IDs the odds of this scale towards the odds of all the air being on the other side of the room the next time you inhale. It could happen, but I wouldn't hold my breath.

    -- MarkusQ

  39. Re:Trouble: this network topology requires authori by Captn+Pepe · · Score: 2

    The first one -- the virtual network performance obviously cannot be independent of the physical network, since you clearly can't exceed the physical layer's capacity. However, to first order you don't really need to worry about the underlying communication system, since it won't be any different for any arrangement of virtual nodes.

    The issues examined by this paper revolve around things like, how many copies of a given packet need to be created to deliver it, how many nodes must it traverse, and what subset of nodes and links is carrying a disproportionate amount of traffic. This last issue is why the hypercube comes out on top in this analysis -- traffic is perfectly distributed over all nodes and links.

    What this analysis does not consider, though, are complications such as routing protocol overhead, and the mapping of virtual links onto physical ones, among other things. While you can consider a computer and its phone line as a unit, you really need to think about the fact that, if your network spans two continents, a large number of your virtual links are going to be sharing a single physical connection. But again, to first order you can neglect these effects.

    --

    Quantum mechanics: the dreams that stuff is made of.
  40. Re:Don't break out the champagne yet... by Wire+Tap · · Score: 2

    Counter-Terrorists win!

    --

    Man is born free; and everywhere he is in chains.

  41. Re:what a crock by geekoid · · Score: 2

    I can't believe Slashdot just posts this psuedomathematical nonsense without doing even elementary fact-checking
    what, you new here?

    --
    The Kruger Dunning explains most post on /. http://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect