|
Researchers working on finding better ways to search the Internet are increasingly turning to methods that require individual nodes, or servers, to know a little bit about nearby servers, but don"t require servers to look much beyond their own neighborhoods.
Researchers from the University of California at Los Angeles have devised a fast search algorithm that promises to increase Internet efficiency by making it easier to find routes between hosts. The algorithm could also be used to reduce by one or two orders of magnitude traffic in peer-to-peer networks running on the Internet that allow people to exchange files, like Kazaa and Gnutella, according to the researchers.
The researchers" algorithm is based on the bond percolation threshold, or the smallest probability that a message is guaranteed to reach a core sub-network of highly-connected nodes.
When a node joins a peer-to-peer network it performs a one-time short random survey of nearby nodes and adds its content directory to each of these neighboring nodes. When a node has a query, it performs another short survey and passes the query along to each node it encounters. All of the initially queried nodes percolate the query throughout the network so that the query is guaranteed to reach the core sub-network.
The traffic generated per query using this method is relatively low, and grows more slowly than the network. In a 100-million node network, for example, the random walks will hit about 100 nodes each, and the traffic generated per query 10,000, according to the researchers.
|