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


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.