Optimal Routing in a Small-World Network

Recently a bulk of research [14, 5, 15, 9] has been done on the modelling of the smallworld phenomenon, which has been shown to be pervasive in social and nature networks, and engineering systems [16, 1, 2, 11]. In order to examine the navigating aspects of small-world graphs, Kleinberg [9] proposes a network model based on a d-dimensional torus lattice with longrange links chosen at random according to the d-harmonic distribution. Kleinberg shows that the greedy routing algorithm, by using only local information, performs in O(lg 2 n) expected number of hops. We extend Kleinberg’s small-world model in that each node x has two more random links to nodes chosen uniformly and randomly within (lg n) 2 d Manhattan distance from x, where d denotes the dimension of the model. Based on this extended model, we then propose an oblivious algorithm that can route messages between any two nodes in O(lg n) expected number of hops, which is an optimal expected bound for routing. Our routing algorithm keeps only O((lg n) β+1) bits of information on each node, where 1 < β < 2, thus being scalable with 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. Our results may be applied to the design of the logical overlay structure of large-scale distributed systems, such as peer-to-peer networks, in the same spirit as Symphony [11]. Since the links are randomly constructed according to the probabilistic distribution, our extended smallworld network is less vulnerable to adversarial attacks, and thus provides good fault tolerance. Key words: small-world networks, augmented local awareness, decentralized routing, design of algorithms, distributed systems.