Close to optimal decentralized routing in long-range contact networks

We design and analyze a new decentralized routing algorithm, in which nodes consult their neighbors near by, before deciding to whom forward the message. Our algorithm uses similar amount of computational resources as Kleinberg's greedy algorithm: it is easy to implement, visits O(log2n/log2(1+k)) nodes on expectation and requires only Θ(log2n/log(1+k)) bits of memory-note that [G.S. Manku, M. Naor, U. Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, in: Proc. of 36th ACM STOC 2004, 2004, to appear], shows that any decentralized algorithm visits at least Ω(log2n/k) on expectation. Our algorithm computes however a path of expected length O(logn(loglogn)2/log2(1+k)) between any pair of nodes. Our algorithm might fit better some human social behaviors (such as web browsing) and may also have successful applications to peer-to-peer networks where the length of the path along which the files are downloaded, is a critical parameter of the network performance.