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

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.