Fast routing table construction using small messages: extended abstract

We describe a distributed randomized algorithm to construct routing tables. Given 0< ε <= 1/2, the algorithm runs in time ~O(n 1/2+ε + HD), where n is the number of nodes and HD denotes the diameter of the network in hops (i.e., as if the network is unweighted). The weighted length of the produced routes is at most O(ε -1 log ε -1 ) times the optimal weighted length. This is the first algorithm to break the Omega(n) complexity barrier for computing weighted shortest paths even for a single source. Moreover, the algorithm nearly meets the ~Omega(n 1/2 + HD) lower bound for distributed computation of routing tables and approximate distances (with optimality, up to polylog factors, for ε=1/log n). The presented techniques have many applications, including improved distributed approximation algorithms for Generalized Steiner Forest, all-pairs distance estimation, and estimation of the weighted diameter.

Authors

• Christoph Lenzen 0001
• Boaz Patt-Shamir

Keywords

• approximate shortest paths
• routing
• small messages