Compact Roundtrip Routing in Directed Networks
Lenore Cowen and Christopher Wagner
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
The first sublinear average space universal compact routing schemes for
directed networks are presented. For each integer k>=1, they use O(k
log n) size addresses; soh(k n^{1/(k+1)})-sized routing tables on average
at each node; and achieve roundtrip routes of stretch at most 2^{k+1}-1
in any (weighted) directed network. (The roundtrip route between u and
v is defined to be d(u,v) + d(v,u)). We extend our results to yield universal
compact roundtrip routing schemes with the stronger requirement that they
use sublinear maximum space at every node. These schemes also use O(k log
n) size addresses and achieve roundtrip routes of stretch at most 2^{k+1}-1
in any (weighted) directed network, and they bound the maximum sized table
at each node by soh(k n^{(3^k + 1)/(2 3^k)}).