Fast Routing Table Construction Using Small Messages

VCLA hosted a RiSE seminar talk by Christoph Lenzen on November 15th, 2012.

ABSTRACT

A fundamental task in distributed systems (like the Internet) is to determine efficient routing paths between all pairs of nodes. For efficiency reasons, one frequently resorts to constructing approximate shortest path based on new node labels that encapsulate some hints on a node's location in its name. While the optimal trade-off between routing tables size and approximation ratio is fairly well-understood in this setting, little attention has been paid to quick construction of such tables in a distributed manner. This is crucial, since usually it is impractical - or even infeasible - to aggregate the topology of large systems in a single location, and in a dynamic environment the solution might be already outdated before it can be put to use.

In this talk, we present a novel technique for distributed routing table construction running in O(n^(1/2+eps)+D) rounds of communication (up to polylogarithmic factors in n), where n is the number of nodes in the system and D the diameter of the communication graph. Our algorithm uses messages of size O(log n) and guarantees approximation ratio O(eps^(-1) log eps^(-1)). Under these constraints, our solution is near-optimal: Every algorithm using messages of size O(log n) and achieving a polylogarithmic approximation must run for Omega(n^(1/2)+D) rounds. In constrast, previous algorithms incur running times of Omega(n) even in graphs of constant diameter. Our approach yields improved distributed algorithms for a number of related problems, including distance approximation and Generalized Steiner Forest approximation.