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)}).