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