Slashdot Mirror
"Random Walkers" may speed P2P networks
sean23007 writes "New Scientist posts an article about an innovative new method of controlling P2P traffic to maximize speed over a very large network. The idea, thought up by researchers at Princeton, Berkeley, AT&T, and Cisco, involves sending random "walkers" around the network, looking for a particular file, which would theoretically yield much better search speed than such other networks as Gnutella. They claim this could result in a network very capable of facilitating a massive distributed supercomputer."
It shouldn't be too difficult to build a system like this that could operate over something like gnutella. You could monitor the search queries and record the most popular requests, then you could use the random walker technique to search out the best sources for these requested files. Anybody else running the same software could enter in a search query and have it look first in the list of popular items before doing the standard crawl-type search over the gnutella network.
___
Cogito cogito, ergo cogito sum.
"...such file networks have particular difficulty locating uncommon documents, and that walkers are especially bad at it. This is because there are relatively few walkers, which might have to visit every node on the network to find the file.
"Langley also says the different connection speeds and processing power of the individual computers in the network may complicate the model: "Random walkers are going to end up at the well connected nodes."
My biggest pleasure from P2P is finding obscure or rare music. I could care less how many copies of N*Sync or Britney Spears there are. Give me rare studio cuts or bootleg recordings of the Grateful Dead any day. This strategy won't help searches for those types of items, but it sure will help the sheeple get their music.
If your on a marginally slow network (say upto a T1 (24 lines at 64 kbps)) and if you enable full node peering support on a Gnutella like network, you know why Random Walkers is needed. Cause the networks have become so huge, most of the bandwidth is taken by message searches. Even if you are not a node peer you would still be saturated by these.
The Random Walker idea isn't new, it was tried a few times before as well on the orginal Gnutella network when they first came out. But, I don't think Random Walkers would be the answer to this network, the bigger the network gets, even Random Walkers would saturate the bandwidth and all you'd have is these bots finding the optimal path to files.
Presently the network works much like how old routhers worked. Search packets are broadcasted to peering nodes which then broadcast the same packets off to their own neighbors. But the problem is that their own neigbors are sometimes the ones that sent the orignial packets. If this was to be done efficently (and how routers implement it), they need to create buffers to hold searches, once a search is recived a search would not be propagated to the other peers, it would be held for a given time period (say a few milliseconds), the node would then wait for the same search to appear from other neighoring nodes, it if does then it wouldnt send this search off down that node. This would cut down a lot of the wasted bandwidth and I am not sure why Gnutella ppl didn't model p2p after these routing methods.
Walkers in an intellient routing setup would be the most optimial way of doing p2p, hopefully this would loose up some of on the congestion on the current p2p networks and let people with less bandwidth access to the shared files with the least sacrifice on bandwitdh for searches.
to know the path you must walk the path
four-oh-four
The paper that was presented, entitled Search and Replication in Unstructured Peer-to-Peer Networks, can be found here (top of the page)
-=20
me doesn't live for do [DEPRECATED]
Why let some algorithm trawl around your network when you can let some human dweeb do it for you. The problem with robots - or computers in general, is that they can be fooled into thinking something is something else.
Personally I use Filemirrors. It shows what people are really downloading.
Q: Can we use it to predict the weather?
A: Yes.
Q: Well, that's not bad. Can it model the behavior of biological molecules?
A: You betcha.
Q: Still, that's rather pedestrian. Can it find large prime numbers?
A: Numbers so big we can't even say them.
Q: Hmm.. almost there. Can it evaluate complex object-relational predicates to get me EXACTLY the porn I want?
A: Er..... Yes.
Q: Excellent! Now we're talking. From the output, can we say conclusively that all of the porn which I want has been found?
A: Please go away.
Q: What about porn that I don't want - gay porn, scatalogical stuff. Can you guarantee I won't get that?
A: Fine, yes. It predicts what you want from your past behavior and is always right. Happy?
Q: Isn't that an invasion of my privacy?
A: Arghhh!
The good and new comes from no quarter where it is looked for, and is always something different from what is expected.
Ohh, bad pun, sorry.
But really, I think the way to think about P2P downloading is to use non-interactive search agents. These guys are on the right path, the random walkers appear to be a bit brighter than an exponentially widening search.
The problem with current p2p networks is that the database is constantly churning. It's not like the web, where data is relatively stable. Two identical searches performed within minutes of each other will return different results. The problem, of course, is that polling the network with these huge searches inflicts a massive bandwidth cost.
A better system would be to have a search agent. You would enter a set of search criteria (with a richer syntax than the existing model), and every 30 seconds or so the software would fire off an agent. The agent does a random walk, then downloads anything that matches. You then go on about your business. When the agents have collected a sufficient number of results. it alerts you.
This lacks the immediate satisfaction of searching and getting results right now, but when you're looking for obscure stuff, you don't get that satisfaction anyway.
Also note that the autonomous downloading assumes you're looking for something reasonably small, like an mp3, and not Girls Gone Wild.
Of course, it also has the advantage that if gives an incentive for hosts to remain connected longer, adding to the stability of the entire system.
buffering searches would definately solve the problem.
Why dont we buffer the searches and cache the route somehow, on certain computers so that when anyone else searches it goes directly down the preset buffered path?
Ok since you have the solution, go implement it, code it!
If you use Linux, please help development of Autopac
It occured to me a while ago that the ability of a peer-to-peer's network to provide a particular file would go up dramatically if less emphasis was put on "real-time" searching and instead in a sort-of subscription model -- the user would request a file, and the request could propagate overnight from client to client while the network itself decided the best/most reliable way to provide that particular file to that particular user... beyond privacy concerns and TTL spoofing on requests (which are probably both non-trivial problems with this idea) I'd certainly be willing to wait a couple days to get a particular file or set of files as long as I didn't have to "babysit" the client and as long as I could be assured that the file would be full and complete when it finally arrived.
~jeff
Qin Lv, one of the researchers, was a TA in one of my classes last semester. She has a website, and the paper is posted there.
How about things like.
I'm looking for that too searching.
Only letting nodes return results if they have an uptime of more that 10mins or so.
Nodes caching recient searches and performance stats.
Quick searches (hits popular search caches) and deep searches.
thank God the internet isn't a human right.
All of the ads on
Napster-to-go says "Fill and refill your compatible MP3 player", which is a lie. It's not MP3. It's WMA with DRM.
This might be easier for non-conforming members of the P2P net to disrupt (The RIAA). If everybody followed the rules, you'd be fine. But since the point of origin is contained in the walker itself, it would be trivial to crapflood the entire system with random walkers, all with different points of origin. Since random walkers are more bandwidth intensive than normal searches, you'd make everything slow as syrup.
I still want to see an option on GNUtella to automatically download Songs from a top10 list
Wouldn't be too hard:
cron - schedule the script execution while I'm asleep
wget - to download the html
perl - to strip out the file names and write out a "wanted list"
maybe a script would even burn CD-RWs of the top weekly songs.
I'm sure that these songs are the ones creating the most traffic, so it is almost the same concept. I like my idea better because you don't need to manually type a bunch of stuff.
Use a non random walk (i.e. tuned to a specific domain or set of preferences) and let it walk the network with a lightweight UDP protocol:
cubicmetercrystal.com/alpine/
The conservative use of bandwidth with an intelligent search mechanism can provide scalable decentralized search for peer networks of any size.
It's easy. Just give a Googlebot a large bottle of grog (I suggest Bundaberg Rum.)
No, I mean something that actually works.
But no, we can't do it that way. It takes orders of magnitude more bandwidth to support music "sharing" as currently implemented. What we have now is comparable in efficiency to buying groceries on eBay.
It does work, well sometimes, its working right now but im sure they will break it again
If you use Linux, please help development of Autopac
yesterday it was working great, today it seems to not work for me anymore. Its getting faster quick though, yesterday it was almost as fast as the WWW.
If you use Linux, please help development of Autopac
The Gnut client will drop any connections that it sees too many duplicate packets on. However, it doesn't help with the badwidth problem that I can see, since the bandwidth consumption is due to the rebroadcasting nature of the network and not necessarily the fact that you're recieving duplicate packets.
I have a positive modifier on Troll. When I mod someone Troll their karma should go UP!
The main advantage of intelligent walking is the ability to find obscure or unpopular data quickly once a peer group is tuned to your preferences (all done locally using implicit query feedback when interacting with peers).
This is important as the paper mentions the problems random walkers have with regards to unpopular resources.
I can picture it now, playing Return to Castle Wolfenstein, with Gnutella running in the background...
Suddenly, my framerate grinds to a halt.
"F%#!!@ Gnutella findfast"
Cool idea, I'm wondering what other uses there might be for this. I do have one question though: how random is the randomness? Will there be some applied chaos theory at work (such as strange attractors)? How do you decide upon the point where the approach to pure randomness (starting from a non-random beginning) is too expensive in network terms?
C|N>K
The paper mentioned in the above article is available (full version) here
Extended version here
Is a project called Circle. It uses the idea of a distributed hash table.
The Author has a overview here.
My brief synopsis:
The network is orginized in a circle, like a circular link list, each node knows about it's neightbors it's neighbors neighbors and maybe a little more, bassicly every node knows about maybe 6 or so other nodes. Each node keeps a section of the hash table, say 0x0500-0x1000 or so.
Each search item is hashed and then sent left or right depending on if it's less or greater then range you are storing, so 0x3000 would be sent to the rightmost node because it's larger. That node would repeat the process, therefore making the search a lot like a binary search.
-Jon
this is my sig.
Here's an idea...
Rather than dynamically searching for the file you want each and every time you type in the name, why not each user create a data-base on the files all the other users on the network are using?
Once you get on the network, it does a search and accesses other people's database, so your current file database is updated.
This would require much less bandwidth than searching dynamically every time you typed in a search term (though it would require a little bit of hard drive space), and it would allow search results to be produced very quickly, as you'd essentially be searching a file on your hard drive.
social sciences can never use experience to verify their statemen
perhaps files should be stored (or at least indexed) from newest to oldest? "The team also showed that deliberately storing information in a random fashion made the network function more efficiently and that there is an optimum number of copies of a file, related to the number of requests that file gets." If files where searched in the order of newest to oldest it would be effectively stored randomly in an alphabetic sense. Then most importantly people are more likely to be searching for recent files and will get results for them sooner. Caching of results of walkers before they are sent on, for a period of time, would surely help as well.
Check out the different lists on Billboard.com Sometime. I agree with you that most of the top 40 stuff sucks (i.e. Britney Spears, Boybands, Etc.)
:-)
I happen to prefer the Modern Rock list myself.
Perhaps what we all need is a "don't play their own instruments" Filter
Seriously though, an ignore list, or a feature like Amazon's "other customers who bought this also liked...." feature might have potential.
One this is for sure, Hard Drive companies would love this because we'd all fill our harddrives fast.