TY - JOUR
T1 - Scale-free compact routing schemes in networks of low doubling dimension
AU - Konjevod, Goran
AU - Richa, Andrea
AU - Xia, Donglin
N1 - Publisher Copyright:
© 2016 ACM.
PY - 2016/6
Y1 - 2016/6
N2 - We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2α balls of half radius. There are two variants of routing-scheme design: (i) labeled (name-dependent) routing, in which the designer is allowed to rename the nodes so that the names (labels) can contain additional routing information, for example, topological information; and (ii) name-independent routing, which works on top of the arbitrary original node names in the network, that is, the node names are independent of the routing scheme. In this article, given any constant ∈ ∈ (0, 1) and an n-node edge-weighted network of doubling dimension α ∈ O(loglogn), we present-a (1+∈)-stretch labeled compact routing scheme with [log n] -bit routing labels, O(log2 n/loglogn)-bit packet headers, and ((1/∈)O(α) log3n)-bit routing information at each node; -a (9 + ∈)-stretch name-independent compact routing scheme with O(log2 n/loglogn)-bit packet headers, and ((1/∈)O(α) log3n)-bit routing information at each node. In addition, we prove a lower bound: any name-independent routing scheme with o(n(∈/60)2) bits of storage at each node has stretch no less than 9 - ∈ for any ∈ ∈ (0, 8). Therefore, our name-independent routing scheme achieves asymptotically optimal stretch with polylogarithmic storage at each node and packet headers. Note that both schemes are scale-free in the sense that their space requirements do not depend on the normalized diameter Δ of the network. We also present a simpler nonscale-free (9 + ∈)-stretch name-independent compact routing scheme with improved space requirements if Δ is polynomial in n.
AB - We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2α balls of half radius. There are two variants of routing-scheme design: (i) labeled (name-dependent) routing, in which the designer is allowed to rename the nodes so that the names (labels) can contain additional routing information, for example, topological information; and (ii) name-independent routing, which works on top of the arbitrary original node names in the network, that is, the node names are independent of the routing scheme. In this article, given any constant ∈ ∈ (0, 1) and an n-node edge-weighted network of doubling dimension α ∈ O(loglogn), we present-a (1+∈)-stretch labeled compact routing scheme with [log n] -bit routing labels, O(log2 n/loglogn)-bit packet headers, and ((1/∈)O(α) log3n)-bit routing information at each node; -a (9 + ∈)-stretch name-independent compact routing scheme with O(log2 n/loglogn)-bit packet headers, and ((1/∈)O(α) log3n)-bit routing information at each node. In addition, we prove a lower bound: any name-independent routing scheme with o(n(∈/60)2) bits of storage at each node has stretch no less than 9 - ∈ for any ∈ ∈ (0, 8). Therefore, our name-independent routing scheme achieves asymptotically optimal stretch with polylogarithmic storage at each node and packet headers. Note that both schemes are scale-free in the sense that their space requirements do not depend on the normalized diameter Δ of the network. We also present a simpler nonscale-free (9 + ∈)-stretch name-independent compact routing scheme with improved space requirements if Δ is polynomial in n.
KW - Compact routing
KW - Doubling dimension
KW - Labeled routing
KW - Name-independent routing
KW - Scale free
UR - http://www.scopus.com/inward/record.url?scp=84976359351&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84976359351&partnerID=8YFLogxK
U2 - 10.1145/2876055
DO - 10.1145/2876055
M3 - Article
AN - SCOPUS:84976359351
SN - 1549-6325
VL - 12
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 3
M1 - 27
ER -