Slashdot Mirror
Mathematical Analysis of Gnutella
jrp2 sent in a paper written by one of Napster's founding engineers. It is
a mathematical evaluation of Gnutella discussing
why the network won't be able to scale up to any reasonable size. I
have been impressed with Gnutella in the past, and have wondered along
these same lines in the past.
If I can be modded down for being a troll, can I be modded up for being an orc, or a balrog?
Napster: Sucks ass.
Gnutella: Doesn't scale.
(Mod my ass as Flamebait for this, but didn't everyone know about Gnutella's scaling problems, and for-pay Napster sucking ass, based on Slashdot stories months and weeks before today?)
haven't we been here before?
I mean, I know that none of us - including our fine moderators - are perfect, but are they at least paying attention?
OK,
- B
http://www.bradheintz.com/
- updated
and on the same day someone from Napster says not Pay Gnutella won't scale
.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
Heh...somehow I read the title as "Mathematical Analysis of Guatemala", since this article has been posted before and Slashdot never posts anything twice.
This space intentionally left blank.
The problem is not that difficult, if you want Gnutella to scale, then you need to avoid the exponential explosition of the number of messages exchanged between the clients as their number grows. The only solution is to structure the network by using "super clients" or "servants" or "super nodes", call them what you want, the later is what KaZaa and Morphus have accomplished; this makes the number of messages exchanged grows in a logarithmic way (this is an outrageous simplification of course, but gives an idea). There are many such expriments with Gnutella two with those ideas, this is what BearShare is trying to do.
Look at ICQ. It was fairly decent as an instant messaging client until the numbers hit one million or so and then it needed to control everything under the sun and companies could spam through it. File sharing happens through it all the time too.
I don't care if Gnutella cannot scale to the levels that Napster saw. Smaller is better in my opinion!
Click here or here.
Yes, but..
It's sort of like calculating the maximum hull speed for steam ships crossing the Atlantic Ocean and saying there is a theoretical maximum speed to intercontinental travel. Then someone comes along and invents airplanes.
Gnutella will mutate and evolve, and will at somepoint in the future be replaced by something better when it starts to fall over.
The demand for Ms. Spears and the Backstreet Boys is just too damn strong for things to stand still.
I enjoyed that this post was next to the announcement that of the new-and-not-so-improved preview of Napster was out..
~.~
I'm a peripheral visionary.
On the topic of this program, a more current story running on msnbc.com right now is telling how it is becoming a severe security risk for users of the program. Here is the article.
What I find most interesting are the kinds of projects that have sprung up in Gnutella's wake. Many of these started out as attempts to improve Gnutella, and have since moved on (the Gnutella Next Generation working group never really materialized into anything)
We had napster and one extreme, gnutella at the other, and in the middle a re a number of partially centralized systems with super peers like Fast Track, such as:
Open FT
JXTA Search
GNet
NEShare
and many others...
Then there are the alternative projects that use an entirely different mechanism. For example, social discovery as implemented in:
NeuroGrid
ALPINE
Or distributed keyword hash indexes like:
Chord
Circle
GISP
JXTA Distributed Indexing
And many others as well.
The coming year(s) will see a lot of maturity in these areas, and searching large peer networks will become ever more efficient over time. Gnutella showed us the possibilities of a fully decentralized model, and refinements of its underlying architecture can produce vastly better solutions.
2002 will be an interesting year for peer networking applications...
Since numerous people above have pointed out this is a repeat, everyone should browse the older article and repost all the comments that were modded up to +5, and reap the benefits when that karma comes rollin' in! ;)
Last night I shot an elephant in my pajamas. How he got in my pajamas I'll never know.
The only solution is to structure the network by using "super clients" or "servants" or "super nodes", call them what you want, the later is what KaZaa and Morphus have accomplished...
This is exactly the point. This is the only way to properly distribute querys, as anyone who has set up a multi-homed ISP knows. It works on the same principle as BGP routing, i.e. there are routers (super-nodes, or whatever) that have a specific number (an ASN - or in P2P, the supernode address) but there are thousands of computers (casual modem users - p2p) on the internet that these routers have information about. If BGP routing worked this way, nothing would go anywhere. However, by having several nodes giving out information on who has what and how to get it, while the majority of users just download and give out their own info, not pass along info of others, things work much smoother. And with a correct implementation, everyone could have a route to everyone's file list at a minimal bandwidth useage.
sig?
In theory, a true Peer-to-Peer file transfer network would exist in a decentralized fashion where you would never have to query a central host for routing or file availability. Napster requires you to route through one of the Napster servers for information. Even introducing Napigator still doesn't alter the Napster model because all it does is allow you to route through a different central host. It seems that all Napster did was integrate a search engine and nameserving into one element (coming from only one provider).
This isn't to knock the accomplishments of Napster, it was certainly an original idea to incorporate these areas and provide a GUI access client to boot. But it is apparent that Napster developers weren't all that revolutionary in their thinking either.
The suggestion of true P2P is revolutionary, and the perfect implementation (should it ever arrive) will also be revolutionary. But the Napster model is no different than everyone providing their MP3 list to a website who maintains a list of links on where to download MP3s. Napster simply automated this process. Napster is no more P2P than any TCP/IP connection not operated through a proxy.
Is http P2P? I'm talking directly to another system, and there is no moderator/mediator. Normally, I have to find out about that system from a 3rd party (e.g. a search engine) -- just like someone obtains a list of links from Napster.
True, I'm being no better than the author of the original article; because I too am offering no solutions. I'm just holding out hope for true P2P in the future.
I'm not very familiar with the deep technical details of Gnutella, but isn't there a limit on how far the "horizon" is (i.e.:how many users near by you can see)? If this is correct, all the mathematics here presented apply only in theory and not in practice, as what will happen is that (1) most queries will not be relayed past a "reasonable horizon", and (2) there exists a good (or high?) probability that as long as you're searching for "popular" files, that you will eventually find them.
Because of this basic and simple observation, I do not foresee gnutella to die anytime soon because of scalability reasons alone (however copy-protection issues are another story).
Again let me stress that my observation here is based on the strong assumption that the "search horizon" is "reasonable sized" so as not to have to search the whole gnutella network.
If you read through this research paper it'll start with N=4 and T=5. As you continue to read through the paper he quotes bandwidth figures from his table using various other N and T values.
For example, in the very last table (Bandwidth rates for 10qps) he says the bandwidth generated will by 8GB/s, which align with N=8, T=7. Where you to use the N and T values from the beginning, this would be 2.4MB/s, which is off by 3143 and one third times.
Going back to Joe User's Greatful Dead query, it only generates ~250KB, not 800MB.
Remember, very very few people are going to modify their TTL or open connections. This ``white paper'' grossly misstates the amount of bandwidth Gnutella generates and seems to be an anti-Gnutalla paper designed to mislead rather than an honest and fair judgment
marotti.com
As I pointed out last time this was posted, this article is basically 100% FUD. Yes, the amount of traffic goes up. And no, gnutella doesn't scale very well. But the author goes out of his way to make the problem look worse than it actually is. You see, the article only computes the total amount of traffic in the entire network. A number which is both huge and meaningless. You see, by this math, if I send a packet somewhere and it takes 10 hops, well, thats like sending 10 packets!
At the end of the paper, the author coughs up the big scary number of 63GBps of traffic in the Gnutella network when the nodes each have 8 connections and are using a TTL of 8. Wow! That's a lot of traffic. That certainly isn't scaling! Well, what the author never points out is that, by his own math, the network has 7,686,400 users at this point! When we divide up the total traffic among all of those network links, we get a different view. If you do the math you discover that this is a whopping 72Kbps! Oh no! It's the end of the world! Well, no, it's not. True, it's more than a modem can handle. But it's well within the reach of most cable modem connections. Given that your computer is being expected to handle the search requests of over 7 million other people, it's not that much traffic.
Don't get me wrong, I agree that Gnutella doesn't scale all that well. But this paper is just plain FUD. The only number that really matters to users is the total bandwidth load on their pipe. By carefully avoiding that number, which isn't very big and scary at all, the auther is clearly lying by ommision. Given all of the real problems networks like Gnutella encounter, it isn't interesting to read this sort of drivel. Why don't we drag out Mathmatical and model how much bandwidth Napster wastes by transmitting the names of all the files being shared even though most of them will never get searched for. Hmmm. lets assume 7,000,000 users. Let's assume that they each share 1000 files with an average filename length of 32 characters. Why, that's 224 Gigabytes of data, and we haven't even done any searches yet! Cleary, Napster doesn't scale. Ugh. This guy might know how to use Mathematica, but I still suspect he worked in the Marketing department. With the same guys who will tell you about their 200Mbps fast ethernet.
its important to know that the author of this paper is Jordan Ritter, who is the co-founder of Napster.
-- Betting on the survival of the media industry is a serious risk. I advise investing elsewhere.
First, if I understand what he's driving at correctly, the bandwidth numbers he gives are for the Gnotella network as a whole, not for each and every client connected to it. This is equivelent to saying "average 'HTTP' usage generates n amount of bandwidth over the Internet", or "DNS traffic will consume x number of bytes on a given network". So what? Would anyone be really shocked if 7,000,000 web browsers generated HTTP and DNS traffic in the gigabyte range? Doesn't bother me. That might be an interesting number to your ISP but as a user of Gnotella I could care less about how much total bandwidth my query for 'The Grateful Dead' takes up. It sure sounds like alot of traffic, but it's distributed over the entire Gnotella network. As long as the traffic isn't high enough to overwhelm individual clients I don't see the problem. These numbers just don't seem to be that important, or am I missing something here?
The other item the author fails to consider (and I'm going to guess that, as one of the engineers behind Napster, he probably knows better) are client-side optimizations like search caching and differentiation of the clients. The caching arguement goes like this:
If client A sends out a query to client C looking for 'Grateful Dead' and client B sends out a very similar request to client C , say, 'The Grateful Dead', even basic caching would prevent client C from sending this request back out to the same hosts that responded to the first request made by client A. Again, am I missing something important here? I'm not sure that caching would reduce the traffic dramatically but I'd be willing to bet that it would improve matters significantly, especially for clients that remained 'up' for long periods of time (which is in itself another important factor that seems to be missing here). This just seems so obvious.
There are bunches of optimizations like this that can be done with the Gnotella application to reduce the overall bandwidth. And this leads to the other half of my point, i.e. the author assumes that each and every client will be functionally the same. They aren't. The Gnotella FAQ tells you to reduce your N if your on a slow connection. This means that not all Gnotella clients are exactly the same now anyway; some have higher N's than others. The FastTrack guys (i.e. KaZaA, Morpheous, et. al.) have already shown that it makes sence from an efficency standpoint to have some clients do more then others via 'supernodes' and the like. This seems like a fairly obvious development on the client side and I can't for the life of me understand why this isn't addressed. I mean, really, isn't the 'client-client' vs. 'client-server' approach really the underlying assumption behind why Napster will scale and Gnotella won't?
I hate to say it but it looks to me like the author is showing just a little bias here. Hey, I suppose that if I worked on a competing standard I'd trash-talk the competition too but I think his time would be better spent making the Napster approach work better. No matter how you slice it or dice it Napster is pretty much dead while the Gnotella network is still alive and kicking. Maybe it will never scale to 'billions and billions' of hosts but at least it's still around and going strong.
There were several responces to this article pointing out that the current Gnutella network is much more scalable than the one discussed in the article. Try looking here and here for articles discussing the changes since early 2000.
Come on Slashdot, its 2002 not 2000. It looks pretty bad accepting this article right after the Napster one. Does Slashdot or VA own a stake in Napster or something?
and I hate to say this, but take an idea from the windows networking world... each machine has an election to see who is going to be the master browser (based on average connected and up times.. the clients that are up and serving the longest and with the shortest down times historically) then we have the next few building the same master browser database but sitting dormant (just listening and cacheing) until the master browser disappears, then the next highest pipes up and says "ohhh lookie me!" thus keeping a master server up (and that master server could load balance with the sub servers by just sending a "busy use 127.0.0.2 or 127.0.0.3" back to the client.
it could be fixed, and made powerful, self scaling.
Do not look at laser with remaining good eye.
That's not logarithmic. If every client node connects to a "super node," and every other "super node," then what you have is a two-level tree. Growth at each level is O(sqrt{n}), not logarithmic.
Chord, a p2p research project from MIT, is truly logarithmic. Go read their SIGCOMM'01 paper for an explanation of how their system works.
--Patrick
If you are going to criticize a paper, do so on the basis of what they are claiming (there is no shortage of support for the claims he is making), not with conspiracy theories about the author's motivation.
Plus the author ignores (mostly due to the fact that they didn't exist back when it was written, this IS an old article) the innovations made with Gnutella (and other, newer competing technologies). Specifically, there are now 'search proxies' that exist on Gnutella that cache and return common queries, thus not saturating the network with redundant queries. For a modem user, this makes the network usable if they limit their connections to proxy servers, because the number of searches hitting their client directly shrinks as common queries are sifted through.
Not to mention there's still room for improvement to the protocol itself-- there's no reason a proxy couldn't cache a list of all files shared by a connected client, then answer queries directly, NEVER sending a query directly to a client. (Ultimately, as people run proxies like this more and more, you'd end up having proxies talking directly to eachother.) The ultimate Gnutella proxy would cache commonly requested files and make them available over a bigger pipe.
No money in it, but for the Gnutella enthusiast, I could see them running this kind of thing from work off of a QA box, for example, or from their support desk at an ISP. =)
All I know about Bush is I had a good job when Clinton was president.
A good analogy might be a detective trying to find a suspect for a crime. The Gnutella approach is akin to going on TV and asking everyone in the area to let you know if they know who did it. It may work once, but the more you do it, the less effective it is. Freenet works as detectives do normally, they gradually home in on their suspect by gathering information, and using that information to refine their search.
Some say that Freenet only achieves this scalability because it doesn't do the type of "fuzzy" search Gnutella does. You need to know exactly what you are looking for in Freenet to find it. This isn't true, the Freenet searching algorithm can be generalised to allow fuzzy searching. While this has not yet been demonstrated in practice, it is definitely possible in theory.
It always amazes me that people continue to lament flaws in many current P2P architectures when Freenet has incorporated solutions to those problems almost from its inception.
Disclaimer: I am Freenet's architect and project coordinator, so you could be forgiven for thinking I am biased, but you are free to review our papers and research to decide for yourself.
You're either an idiot, a karma whore, or both. Go ahead, download Bearshare (or any Gnutella based client) and look at the number of query responses you get to common queries-- oh look, most of them are RIGHT. Sure, you get some dead hits, but most of the time this is someone who's behind a firewall that doesn't have their client setup to work behind said firewall (or can't, because of a non-static IP address).
Saying it's "historical" is just flamebait though, but I guess I answered the call like an idiot. As the original poster said, it's all FUD-mongering. As your post is.
All I know about Bush is I had a good job when Clinton was president.
Obviously you haven't used GNUtella for the past year. Xolox is a GNUtella client that allows for parallel downloading, resuming, and Xolox will even look for other sources of the file that you are currently downloading, if the current sources are too slow or down. Basically, with Xolox, you search for a file that you want, and you get results with numbers by them depicting how many sources have the file. That way you don't have to decide which source you want to download from. You decide which file you want to download... and Xolox figures out the rest.
My average download speeds on Xolox are around 160Mbs. Of course, I am use the ever so crappy AT&T cable modem service... so other people on faster DSL lines will most likely experience faster downloads.
Next thing you are going to tell me is that Windows is better than Linux because Linux doesn't have any good GUIs or desktop environments for it. Yeah, lets just ignore everything thats out there right now.
Not only that, but Limewire also supports multisource, segmented, or swarmed downloading. Though Limewire has only recently gotten such functionality, while Xolox has had it for the past year.
Oh, and GNUtella is free as in beer and as in speech.
Of course, building an indexing system that scales arbitrarily is difficult, and building an indexing system that recognizes local topologies is also critical. A typical problem universities had with Napster was that if N people at the school wanted a given tune, most of them would be likely to fetch it across the school's limited outside bandwidth instead of most people fetching it from other sites on the fast LAN after the first one or two had downloaded it across the limited part. Napster was able to reduce this problem, at least at some schools, because having a centralized indexing service means that they can enforce more locality by making it easiest for people to find nearby peers. A decentralized system *may* be able to accomplish this, but it's a lot harder.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Easy-- this is where proxies come in, and proxies that talk to other proxies across the world (ie: proxies that intentionally look for and connect to other proxies, essentially sharing information across a larger umbrella). I think you're referring to the issue of TTL in query packets, and a proxy can solve that problem as well (especially, as my other post in this same thread indicated, the proxy and protocol can be extended to immediatly poll clients upon connection for what files they're sharing (and thus, never pass queries on to clients directly)).
Yes there are chances to optimize the protocol, but it's all fairly basic-- Kazaa's technology isn't that far removed from Gnutella. Supernodes (which is basically what I described above, a 'proxy/cache') are the next logical step to the Gnutella spec.
All I know about Bush is I had a good job when Clinton was president.
It's worth noting that giFT/OpenFT just entered its first stage of network testing--and with that in mind, they need as many people as possible to download and run the client so they can test the network. Complete instructions for so doing are given on the website.
Editor Emeritus and Senior Writer, TeleRead.org
Not if you couldn't predict which machines on the net would act as those supernodes. If, like another poster mentioned, machines that met a certain criteria (bandwidth, storage, time on line, whatever) simply won an election to act as a node, there's no single point to shut down. Shut down one supernode, the others are informed that a replacement is needed and another election is called for.
:)
Following an election, the supernodes update the clients as to the lookup machines. I suppose you could even have it where if all the supernodes were shut down that an entirely new election process takes place creating a new set of supernodes. Kind of like having a DNS server setup where any machine can act as one of the root servers based on a criteria based election by those machines doing a lookup.
Way too much for my wee brain to work out all the details on. Sounds good in theory anyway
The line must be drawn here. This far. No further.
This sig under construction. Please check back later.
Taco's not a patent examiner.