Compact routing design in networks of low doubling dimension.

摘要

A routing scheme is a distributed algorithm that allows any source node to route packets to any destination node in a distributed network. There are two variants of routing scheme design: (i) labeled (name-dependent) routing, where the designer is allowed to rename the nodes so that the names (labels) can contain additional routing information, e.g. topological information; and (ii) name-independent routing, which works on top of the arbitrary original node names in the network, i.e. the node names are independent of the routing scheme.; This thesis focuses on the design of routing schemes, in both labeled and name-independent models, in networks whose shortest path metric has low doubling dimension. The main trade-off considered in the design is between the space requirement and the stretch, where the stretch is the maximum ratio of the length of a routing path to the shortest-path distance, over all source-destination pairs. The space requirement of a scheme refers to the size of routing tables maintained at each node and the size of packet headers used by the scheme. A routing scheme is compact if its space requirement is polylogarithmic in the number of nodes.; The following paragraphs describe the results, achieved in the thesis, of various of compact routing problems.; First, given any constant epsilon in (0, 1), and an n-node edge-weighted network of low doubling dimension in O(loglog n), both a compact labeled routing scheme with (1+epsilon) stretch and a compact name-independent routing scheme with (9 + epsilon) stretch are achieved. In addition, an asymptotically tight lower bound is proved that any name-independent routing scheme with compact space requirement has stretch no less than 9. In spite of the lower bound, compact name-independent routing schemes with better stretch, (1 + epsilon), are presented by relaxing guarantees to allow for (i) a small fraction of nodes to have large storage, or for (ii) a small fraction of source-destination pairs to have larger, but still constant (9 + epsilon), stretch.; Furthermore, this thesis also considers scenarios where the network topology may vary over time. In networks in presence of failures, optimal-stretch compact routing schemes are provided. In dynamic networks where nodes may join, leave and move, optimal-stretch compact metric routing schemes with locality-sensitive movement protocol are presented.; Finally, constant-stretch compact routing schemes are achieved in bounded decomposable networks, a more general class than bounded doubling networks.