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."
By the way, I'm doing a better protocol, Samizdat.
- Kaos games and encryption systems developer
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....
one of these days ill get it...
Oops!
?
I stopped reading this headline when I saw the word "hypertori", because I knew whoever wrote it thinks i'll believe he's smart simply because he peppers his article with Al Gore-caliber buzzwords.
So..Who has a really interesting article to share?
Bowie J. Poag
Anyone remember Gary Gnu?
"Any Gnews is Good Gnews with Gary Gnu."
For more information on the structure try Relation Nets and Hypernets in pdf form.
anyone who has taken basic algebra knows this article is a complete farce...let me count the ways:
- a hypertorus has d^2 orthogonal dimensions, not d, as the "article" states
- his explanation of network diameter is a complete fantasy. the latency between points on a network has absolutely nothing to do with the chordal length, as he would well know if he'd get out of his ivory tower and do actual internet studies, as I have
- equating the path length with the peer horizon is utter speculation, and Ritter himself has denounced this type of mathematical voodoo
- "Little's Law," as he calls it, has been discredited at least a half dozen times by researches at Harvard, Stanford, and elsewhere
- anyone with a grounding in mathematical principles knows that there is no such thing as a binary hypercube, any more than there is such a thing as a square circle
I can't believe Slashdot just posts this psuedomathematical nonsense without doing even elementary fact-checking
Gary Gnu was on The Great Space Coaster.
Anyone have any good learn math links?
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
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."
Jeez. Editors and submitters take note: if you want somebody to click the link to the story, don't make the blurb a pile of almost-unintelligible mush. A much better way to submit it would be:
Check out this article. It explains more or less how we might shift the paradigm of a Gnutella-like P2P network towards a more geometric model that has *much* less bandwidth overhead and possibly much better performance. Beware the big words, but do yourself a favor and check it out.
oh yeah, and if the editor's michael, you can tag this on the end:
i fucking hate all p2p networks, and this is a really stupid concept, but check it out.
Hey Taco! Looks like you're using the "infinite monkeys and typewriters" scheme to generate Ask Slashdots again...
Go to bed.
If you use Multicast for the information where reasable, you will have a linear behaviour there. The problem I guess is that you don't have Multicast connectivity to most end users.
Now that I don't have the time limit of First Post gloating, I can give you the details of Samizdat...
Samizdat is a censor resistant agile network protocol named for the clandestine publication of banned literature in the Soviet Union.
Some americans have asked me if this is just about stealing music from big companies and giving it to your friends.
While this is possible, the real purpose of Samizdat is to share files and messages in a secure, anonymous network.
The right to Free Speech is a part of the Universal Declaration of Human Rights and is also in the constitution of the USA and the Human Rights acts of Canada, the UK, Australia and New Zealand.
Recently, the governments of the free world have tried to remove that right by claiming hacking is terrorism and information is a weapon.
I say "freedom is the freedom to say 2 + 2 = 4" that the following articles from http://www.un.org/Overview/rights.html the declaration states laws like the USA PATRIOT , UK RIP and acts in other countries which allow the secret service or police to read your email are illegal under international law.
Articles 12, 19 & 27 of the universal declaration of human rights http://www.un.org/Overview/rights.html deal with the information rights of everyone.
If anyone tells you filesharing is illegal, then that law is a violation of an internation treaty your country has signed to join the UN.
- Kaos games and encryption systems developer
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.
Not to be confused with GGG - Christians in China
FOAD, DF.
this is funny. get it, a joke.
The state is the great fiction by which everyone tries to live at the expense of everybody else. ~F. Bastiat
The complaint seems to be that the "network" is being used inefficiently. But who cares? I pay for my bandwith, and I'm glad to use it all up. Costs the same for me.
Sure, as the number of users gets larger, the quality of my searches stops getting better. But I don't care because the quality of my searches are already good enough.
This whole thing sounds like sour grapes from people who want to control from a central server.
Gnutella is not agile, Samizdat is.
This means it can be upgraded by anyone who can program a protocol.
As Smaizdat is Java2 based, protocols are easy to write and insert in your collection. Samizdat just transfers between protocols.
Cayley Tree Gnutella vs Decentralised Hierarchy Samizdat.
Although gnutella and samizdat have no root in the tree, samizdat uses end point hierarchy to prefer local copies of files or servers with more bandwidth, etc.
Gnutella can be slow, so Samizdat gives you the option to choose how to transfer files.
Gnutella plaintext vs Samizdat encryption.
Gnutella can be intercepted by hackers or the government and it's ports blocked.
Samizdat can't be read in between the authorised receipients, the traffic only decrypts on the receiver.
Samizdat also switches ports to stop DoS attacks or IP port censorship.
IP port censorship is used by communist china, singapore, most arab nations and western universities.
Don't let yourself be censored or have your internet use intercepted by idiots.
If there are any other coders out there, I'm willing to share Samizdat as a GPL project.
- Kaos games and encryption systems developer
Or German Scheiss videos. Essen mein Scheisse!
good one! Shame not many have bitten yet though.
All you P2P advocates (and yes that includes me) had better quit programming P2P platforms and get on your lawyer-faggot wigs because in less than 24 months, Microsoft's DRM will be COMPULSORY on all new computers, and then some.
Tell your local member of parliament you think this fucking stinks. Or bye-bye P2P, scalable or not.
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
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
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.
Which part of that article do I understand?
</Fry>
Flick du. Du bist Scheisse! Auf wiedersehen.
Signed,
Anal Cox
how is a gnutella node supposed to know where it is in the net/tree/whatever ?
send status information from all other nodes ? (some million status packets hurt modem users)
how is it supposed to built the net/tree/whatever ? communicate with the other nodes ?
node1: "im node xyz in grid zxy"
node2: "no you are not"
node3: "node2, who are you ?"
to be clear, the "connect to nodes and aproximate network efficiency" is the only simple and (somewhat) working way to handle the gnet.
no way you can control some thousands of gnodes to form a certain topology.
Dont know what a hypercube is? click here
This paper is a great germ for further study, but until there is some practical experimentation to support it, it's hot air. Good hot air, perhaps, but still vapor. If theoreticians want the support of engineering types, we need to see some experimental tests. I've seen dozens of really good theories on improving peer and grid networks that turn sour as soon as anyone tries to implement them. This paper mentions much about peer networks and nothing about peer review. I'm withholding judgement until I read the peer review.
Sounds just like something I heard about once. The speedball. Everyone who does them loves them. The mix of heroine and cocaine are insane one slows you down the other picks up as you are about to crash. Of course everyone who does them dies. Tagging something like this onto a broken model is just ludicrous. The point is this, where the current model is strecthed to the point of death, adding one more element to it to work around it isn't going to make it work better, it needs to be taking to rehab and given a clean start or possibly taken out back and shot ending the problem entirely.
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.
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...
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?
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.
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
Thinking Machines Corp went out of business around 1994.
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.
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
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.
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:
This should at least be functional; no doubt there are a number of clever hacks that could be made...-- MarkusQ
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!
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
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?
...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.
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!
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.
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.
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.
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:
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
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.
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.
you could say the same for gnutella now. Yet only LOCAL information is needed, nobody needs to see the big picture.
for example a node that newly connects to the network could jump from node to node until it finds a suitable place in the network (you should be able to easily work out this method for a binary tree). It could even (for efficiëncy) ask the network to give it a free spot. Nodes should then jump inwards to accomplish a smaller network.
I wish slashdotters would not respond to a technical article unless they understood what they were talking about.
The author fully understands the nature of the internet. He is limiting the scope of his study to "theoretical bandwidth limitations" because that provides an upper bound on scalability regardless of the underlying hardware network structure. Yeah, okay, you won't actually hit that upper bound, but that's not the point. You can't possibly *exceed* the upper bound. That's the point. Earlier papers attempted to prove much lower upper bounds, and this is a (quite good) refutation of them.
Most posters are also confused about the relationship between hardware and software network topologies. Yes, the Internet connection going into your college or whatever has a fixed limited network topology. Yes, that will cause a 20-cube to have less bandwidth utilization than the theoretical limit. But guess what... the current logical tree structure that gnutella uses *also* does not match the underlying hardware structure, and so suffers in the same way.
By discussing the differences between the Cayley tree and the hypercube, we can do things like quantify the *rate* at which each of them suffers due to a bottleneck like this.
This is how science is done. People who ignore the science and just say "I am going to hack some super l33t heuristics into the network so searches work better" are being fools. Any heuristic you implement over a poorly-performing topology is going to work much better on the well-performing topology.
You can install Linux on a 486, or you can install it on a 1GHz Athlon. The slashdotters dissing this paper are essentially saying "Well it's stupid to install Linux on the Athlon, it won't go any faster because you know, those instruction cycle counts for the Athlon are all theoretical and you will never hit that performance in the real world... there are going to be cache misses and FPU stalls and stuff. So let's stay with the 486! Yeah, it's slow, but if we just optimize our apps, they will run faster!" Well you can optimize your apps and fool yourself into thinking you are doing a good job. But if you then turn around and run the newly optimized apps on the Athlon (or put the same amount of effort into optimizing them differently for the different CPU architecture) you will ground the 486 into a pile of rubble.
-N.
True. The fact that the physical layer of the network plays a large part in the performance of a P2Pnet is often neglected. I personally believe that the best performance increase in the next couple of months/years will come from designing 'virtual networks' around physical sublayers instead of just mathematical analysis. Both are important, but for now, one of these is completely overlooked. Since I'm seriously considering writing my masters thesis about coupling physical with virtual nets in the most efficient manner I'd like to hear about current research related to per peer bandwith and latency issues (being the first to address this sounds just as well, though ;) ).
Mathematical proofs are very important when practicing 'good' research, but practical issues always seem to screw up these theoretical proofs, so I believe we should try to address these too.
http://www.timecube.com
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. :)
Another paper that describes the hosts participating in Gnutella and Napster (2001) and how Gnutella's overlay can be easily shattered. http://www.cs.washington.edu/homes/tzoompy/publica tions/mmcn/2002/abstract.html
Put it on sourceforge.
Lerne erst mal vernünftig Deutsch, Du Schwachmat.
Reicht es nicht, wenn Ihr Niveauficker auf Englisch hier rumtrollt?
Real, massively scalable P2P, here and now!... and its open source :-)
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!
The problem with forcing stuff into a pre-defined address space is you'll have peers connected to each other based on a purely arbitrary notion without regard to actual network speeds or conditions. I don't want to find myself connected to some slow dial-up half a world away just because it happens to have a similar address.
Peers should seek other peers based on the quality and better connected peers should automatically move to the center of things. FastTrack works quite well, and it only has one layer of organization (regular vs. supernodes). It might be better to use nature as an example and have some simple set of rules peers would follow to naturally find the best spot for whatever they're doing (the old "ant" idea). You could factor in things like bandwidth, how many searches produced good results, how much overhead traffic is being generated, file types shared, etc. Peers would then keep or drop connections based on these factors. The goal being for each to find its ideal spot. Not just for connectivity, but productivity. Peers with similar searches and files could naturally group together making it easier to find the files you actually care about.
A simple approach to the IP address issue would be for each peer to generate a GUID and use this like a dynamic DNS name (similar to your 64bit idea but less chance of collision). You could then find another peer even when it re-connected under a different IP and more intelligent routing could be set up.
Google or Babelfish don't have a fuzzy-math-to-English convertor tool.
Zodiac Survey
FastTrack on the other hand has a semi-heirarchical structure so it uses less bandwith, with those with the fastest connections doing the routing.
(Plug: View my Honours dissertation by clicking here)
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.
Then we can just start making connections, getting their IDs, and dropping the furthest out, yes?
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?
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? 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?
If we use the introduction method, won't the "core" of the network [those hosts that stay on for a long long time] eventually fall into place as a proper hypercube?
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]?
--Knots
Anarchy$ dd if=/dev/random of=~/.signature bs=120 count=1
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.
SGI's Origin and Onyx topologies have been based on hardware hypercubes since the mid to late 90s. This allows them to have unholy scalability, low latency, and extreme bandwidth.
For more info, check the tech details here:
http://www.sgi.com/origin/images/hypercube.pdf
You cannot understand the TimeCube.. you are not the wisest human
That is a sad site. It is obvious that the one who authored it is demon-possessed. Those that are Christian should pray for his salvation and deliverance.
Isn't the problem with trying to apply HyperCubes to a p2p network is that it takes no account for the churn rate of the peers in the network?
...
Hypernets are all about maintaining connections to a particular subset of nodes right?
The important thing about Gnutella and other P2P nets is that the peers are unstable, dropping in and out. How can you maintain a hypernet over the network when from one moment to the next you can't predict which peers are a part of the network?
The advantage (if I can call it that) of the Cayley tree is that you just need any set of random connections and you're away