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

Comments

The research paper

[sitcoman]

The paper that was presented, entitled Search and Replication in Unstructured Peer-to-Peer Networks, can be found here (top of the page)

Re:Random Walkers and other algorithems

[Sanity]

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.

Freenet does something quite like this. Requests are routed based on local heuristic knowledge of the network, information gravitates towards the demand for that information through a form of dynamic mirroring.

this paper (PDF) gives a great overview.

Related Paper

[chaih]

The paper mentioned in the above article is available (full version) here

Extended version here

Another, i think somewhat better approach.

[jon_c]

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