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 an actual shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick [2001] 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 et al. [2000]. Our result is the first analytical bound coupled to the parameter of the power-law graph model for a compact routing scheme. Let n denote the number of nodes in the network. We provide a labeled routing scheme that, after a stretch-5 handshaking step (similar to DNS lookup in TCP/IP), routes messages along stretch-3 paths. We prove that, instead of routing tables with ? (n1/2) bits (?O suppresses factors logarithmic in n) 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(n1+γlog n), with γ = τ-2 2τ-3 + ε, where τ ∈ (2, 3) is the power-law exponent and ε > 0 (which implies ε < γ < 1/3 + ε). Both bounds also hold with probability at least 1-1 (independent of ε). The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step. The scheme uses 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 [2001, 2005] for stretch-3 and we obtain a new upper bound of expected ?O(n 1+γ) for space and preprocessing for random power-law graphs. Our distance oracle is the first one optimized for power-law graphs. Furthermore, we provide a linear-space data structure that can answer 5-approximate distance queries in time at most ?O(n1/4+ε) (similar to γ, the exponent actually depends on τ and lies between ε and 1/4 + ε).
展开▼
