Optimal Routing in a Small-World Network

Substantial research has been devoted to the modelling of the small-world phenomenon that arises in nature as well as human society. Earlier work has focused on the static properties of various small-world models. To examine the routing aspects, Kleinberg proposes a model based on a d-dimensional toroidal lattice with long-range links chosen at random according to the d-harmonic distribution. Kleinberg shows that, by using only local information, the greedy routing algorithm performs in O(lg² n) expected number of hops. We extend Kleinberg’s small-world model by allowing each node x to have two more random links to nodes chosen uniformly and randomly within Manhattan distance from x. Based on this extended model, we then propose an oblivious algorithm that can route messages between any two nodes in O(lgn) expected number of hops. Our routing algorithm keeps only O((lgn)^β+1) bits of information on each node, where 1 < β < 2, thus being scalable w.r.t. the network size. To our knowledge, our result is the first to achieve the optimal routing complexity while still keeping a poly-logarithmic number of bits of information stored on each node in the small-world networks.