Tech Report CS-07-01

Towards Fast Decentralized Construction of Locality-Aware Overlay Networks

Aleksandrs Slivkins

March 2007


We consider a large overlay network where any two nodes can communicate directly via the underlying Internet as long as the sender knows the recipient's ip-address. Due to the scalability requirement, the overlay network must be sparse: a given node can store at most a polylogarithmic number of ip-addresses. A notion of distance (locality) in the network is given by node-to-node round-trip times. We assume that initially the overlay links are random, and hence have no explicit locality-aware properties.

We provide fast distributed constructions for various locality-aware (low-stretch) distributed data structures, such as: distance labeling schemes, name-independent routing schemes, and multicast trees. In previous work, such data structures have only been constructed via centralized algorithms. Our constructions complete in poly-logarithmic time (and thus induce at most a poly-logarithmic load on every given node), and achieve quality guarantees similar to those of the corresponding centralized algorithms.

Our algorithms use a common locality-aware, small-world-like overlay framework, constructed via concurrent random walks. Our guarantees are for growth-constrained metrics, a well-studied family of metrics which have been proposed as a reasonable abstraction of round-trip times in the Internet.

(complete text in pdf)