Optimal Routing in a Small-World Network

Substantial researchhas been devoted to the modelling of the small-world phenomenonthat arises in nature as well as human society. Earlier work hasfocused on the static properties of various small-world models. Toexamine the routing aspects, Kleinberg proposes a model based on ad-dimensional toroidal lattice with long-range links chosen atrandom according to the d-harmonic distribution. Kleinberg showsthat, by using only local information, the greedy routingalgorithm performs in O(lg^2 n) expected number of hops. Weextend Kleinberg's small-world model by allowing each node x tohave two more random links to nodes chosen uniformly and randomlywithin (lg n)^(2/d) Manhattan distance from x. Basedon this extended model, we then propose an oblivious algorithmthat can route messages between any two nodes in O(lg n)expected number of hops. Our routing algorithm keeps only O((lgn)^beta+1) bits of information on each node, where 1< beta<2, thus being scalable w.r.t. the network size. To ourknowledge, our result is the first to achieve the optimal routingcomplexity while still keeping a poly-logarithmic number of bitsof information stored on each node in the small-world networks.