Compact Routing with Slack
Mike Dinitz
Given a weighted graph G=(V,E), a compact routing scheme is a distributed
algorithm for forwarding packets from any source to any destination. The
fundamental tradeoff is between the space used at each node and the stretch of
the total route, measured by the multiplicative factor between the actual
distance traveled and the length of the shortest possible route. We extend the
normal definition with a slack parameter epsilon, which allows us to ignore up
to epsilon*n2 of the shortest pairwise routes and give stronger guarantees on
the remaining ones. We give good epsilon-slack routing schemes in a variety of
standard routing models, including the labeled model and the name-independent
designer-port model. We also give a lower bound that proves that such schemes
do not exist in the name-independent fixed-port model. In the labeled model we
also give a gracefully degrading scheme which works simultaneously for all
epsilon > 0 and guarantees constant average stretch with polylog space.