Compact Routing with Slack in Low Doubling Dimension

Written with Goran Konjevod, Andrea Richa, and Donglin Xia.

In Proc. Proc. 26th Annual Symposium on Principles of Distributed Computing, pages 71-80, 2007.

Downloads: PDF, PS

Abstract: We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek name-independent routing schemes with 1 + ε stretch and polylogarithmic storage at each node. Since existing lower bound precludes such a scheme, we relax our guarantees to allow (i) a small fraction of nodes to have large storage, say of O(n log n) bits, or (ii) a small fraction of source-destination pairs to have larger, but still constant, stretch.