Compact roundtrip routing with topology-independent node names

AbstractConsider a strongly connected directed weighted network with n nodes. This paper presents compact roundtrip routing schemes with O˜(n) sized local tables4 and stretch 6 for any strongly connected directed network with arbitrary edge weights. A scheme with local tables of size O˜(ϵ−1n2/k) and stretch min((2k/2−1)(k+ϵ),8k2+4k−4), for any ϵ>0 is also presented in the case where edge weights are restricted to be polynomially-sized. Both results are for the topology-independent node-name model. These are the first topology-independent results that apply to routing in directed networks. 4The O˜(R) notation denotes O(RlogO(1)R)