Routing in
Networks with Low Doubling Dimension
|
Andrew V. Goldberg Dahlia Malkhi |
Abstract This paper studies compact routing schemes
for networks with low doubling dimension. Two variants are explored,
name-independent routing and labelled routing. The
key results obtained for this model are the following. First, we provide the
first name-independent solution. Specifically, we achieve constant stretch
and polylogarithmic storage. Second, we obtain the
first truly scale-free solutions, namely, the network's aspect ratio is not a
factor in the stretch. Scale-free schemes are given for three problem models:
name-independent routing on graphs, labelled
routing on metric spaces, and labelled routing on
graphs. Third, we prove a lower bound requiring linear storage for stretch
<3 schemes. This has the important ramification of separating for the
first time the name-independent problem model from the labelled
model, since compact stretch-(1+epsilon) labelled
schemes are known to be possible. |
|
|
[ICDCS
version pdf]
[TR: local pdf,
remote MSR-TR-2005-175 |
|
|
|
|
||