Compact Roundtrip Routing with Topology-Independent Node Names

摘要

This paper presents compact roundtrip routing schemes with local tables of size O(n~(1/2)) and stretch 6 for any directed network with arbitrary edge weights; and with local tables of size O(ε~(-1) n~(2/k)) and stretch min((2~(k/2) - l)(k + ε), 16k~2 + 8k - 8), for any directed network with polynomially-sized edges, both in the topology-independent node-name model. These are the first topology-independent results that apply to routing in directed networks.