Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension

摘要

We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value a such that any ball in the network can be covered by at most 2(alpha) 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.