A Compact Routing Scheme and Approximate Distance Oracle for Power-Law Graphs

Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang

July 2009

## Abstract

Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of a shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello, Chung, and Lu. Our result is the first theoretical bound coupled to the parameter of the power-law graph model for a compact routing scheme. In particular, we prove that, for stretch 3, instead of routing tables with *˜O(n*^{1/2}) bits as in the general scheme by Thorup and Zwick, expected sizes of *O(n*^{γ}log n) bits are sufficient, and that all the routing tables can be constructed at once in expected time *O(n*^{1+γ}log n), with *γ=(τ-2)/(2τ-3)+ε*, where *τ* in (2,3) is the power-law exponent and *ε>0* (which implies *ε < γ < 1/3 + ε*). Both bounds also hold with probability at least 1-1/n (independent of *ε*). The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step and using addresses and message headers with *O(log nlog log n)* bits, with probability at least 1-o(1). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs. With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick for stretch 3 and obtain a new upper bound of expected *˜O(n*^{1+γ}) for space and preprocessing for random power-law graphs.

## Details

Publication type | TechReport |

Number | MSR-TR-2009-84 |

## Publication files

##
Related people