On the complexity of greedy routing in ring-based peer-to-peer networks
George Giakkoupis, Vassos Hadzilacos · 2007
We investigate the complexity of greedy routing in uniform ring-based random graphs, a general model that captures many topologies that have been proposed for peer-to-peer and social networks. In this model the nodes form a ring; for each node u we independently draw the set of distances along the ring from u to its "long-range contacts" from a fixed distribution P (the same for all and connect u to the corresponding nodes as well as its ring successor. We prove that, for any distribution P, in a graph with n nodes and an expected number of long-range contacts per node constructed in this fashion, the expected number of steps for greedy routing is Ω((log2n)/lalog*n), for some constant a > 1. This improves an earlier lower bound of Ω((log2n)/llog log n) by Aspnes et al. and is very close to the upper bound of O((log2n)/l) achieved by greedy routing in Kleinberg's (one-dimensional) "small-world" networks, a particular instance of uniform ring-based random graphs.