Compact Routing with Stretch Factor of Less Than Three
Kazuo Iwama and Akinori Kawachi
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
Recently, Cowen gave a universal compact routing algorithm with a stretch
factor of three and table size of O(n^{2/3} log^{4/3}n) based on a simple
and practical model. This paper considers, using the same model, how the
necessary table-size differs if the stretch factor must be less than
three. It is shown that: (i) There is a routing algorithm with a stretch
factor of two whose table-size is (n-sqrt(n)+2) log n. (ii) There is a
network for which any routing algorithm which follows the model and has
a stretch factor of less than three needs a table size of $(n-2sqrt(n))
log n in at least one node. Thus, we can only reduce roughly an additive
sqrt(n) log n from the trivial table-size of n log n which obviously enables
shortest-path routing.