Small-world routing
In
Greedy routing
Nearly every solution to the problem of routing in small world involves the application of
Constructing a reference base
Greedy routing will not readily work when there is no obvious reference base. This can occur, for example, in overlay networks where information about the destination's location in the underlying network is not available. Friend-to-friend networks are a particular example of this problem. In such networks, trust is ensured by the fact that you only know underlying information about nodes with whom you are already a neighbor.[citation needed]
One solution in this case, is to impose some sort of artificial addressing on the nodes in such a way that this addressing can be effectively used by greedy routing methods. A 2005 paper by a developer of the
An important problem involved with this solution is the possibility of
This method for constructing a reference base can also be adapted to distributed settings, where decisions can only be made at the level of individual nodes who have no knowledge of the overall network. It turns out that the only modification necessary is in the method for selecting pairs of random nodes. In a distributed setting, this is done by having each node periodically send out a random walker terminating at a node to be considered for swapping.[citation needed]
The Kleinberg model
The Kleinberg model of a network is effective at demonstrating the effectiveness of greedy small world routing. The model uses an n x n grid of nodes to represent a network, where each node is connected with an undirected edge to its neighbors. To give it the "small world" effect, a number of long range edges are added to the network that tend to favor nodes closer in distance rather than farther. When adding edges, the probability of connecting some random vertex to another random vertex w is proportional to , where is the clustering exponent.[1]
Greedy routing in the Kleinberg model
It is easy to see that a greedy algorithm, without using the long range edges, can navigate from random vertices on the grid in time. By following the guaranteed connections to our neighbors, we can move one unit at a time in the direction of our destination. This is also the case when the clustering component is large and the "long range" edges end up staying very close; we simply do not take advantage of the weaker ties in this model. When , the long range edges are uniformly connected at random which means the long range edges are "too random" to be used efficiently for decentralized search. Kleinberg has shown that the optimal clustering coefficient for this model is , or an inverse square distribution.[2]
To reason why this is the case, if a circle of radius r is drawn around the initial node it will have nodal density where n is the number of nodes in the circular area. As this circle gets expanded further out, the number of nodes in the given area increases proportional to as the probability of having a random link with any node remains proportional , meaning the probability of the original node having a weak tie with any node a given distance away is effectively independent of distance. Therefore, it is concluded that with , long-range edges are evenly distributed over all distances, which is effective for letting us funnel to our final destination.[citation needed]
Some structured Peer-to-peer systems based on DHTs often are implementing variants of Kleinberg's Small-World topology to enable efficient routing within Peer-to-peer network with limited node degrees.[3]
See also
- Social network – Social structure made up of a set of social actors
- Small-world network – Graph where most nodes are reachable in a small number of steps
- Watts-Strogatz model– Method of generating random small-world graphs
References
- ^ Kleinberg, Jon. "Networks, Crowds, and Markets: Reasoning about a Highly Connected World" (PDF). Retrieved 10 May 2011.
- PMID 10972276.
- ^ Manku, Gurmeet Singh Manku. "Symphony: Distributed Hashing in a Small World" (PDF). usenix.org.