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 $\tilde{O}(n^{1/2})$ bits as in the general scheme by Thorup and Zwick, expected sizes of $O(n^{\gamma}\log n)$ bits are sufficient, and that all the routing tables can be constructed at once in expected time $O(n^{1+\gamma}\log n)$, with $\gamma=(\tau-2)/(2\tau-3)+\epsilon$, where $\tau$ in (2,3) is the power-law exponent and $\epsilon>0$ (which implies $\epsilon < \gamma < 1/3 + \epsilon$). Both bounds also hold with probability at least 1-1/n (independent of $\epsilon$). The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step and using addresses and message headers with $O(\log n\log\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 $\tilde{O}(n^{1+\gamma})$ for space and preprocessing for random power-law graphs.

msr-tr-2009-84.pdf
PDF file

Details

TypeTechReport
NumberMSR-TR-2009-84
> Publications > A Compact Routing Scheme and Approximate Distance Oracle for Power-Law Graphs