Shortest-Path Routing in Arbitrary Networks
Friedhelm Meyer auf der Heide, Berthold Vöcking · Journal of Algorithms · 1999
We introduce an on-line protocol which routes any set ofNpackets along shortest paths with congestionCand dilationDthrough an arbitrary network inO(C + D + log N) steps, with high probability. This time bound is optimal up to the additive log N, and it has previously only been reached for bounded-degree leveled networks. Further, we show that the preceding bound holds also for random routing problems withCdenoting the maximum expected congestion over all links. Based on this result, we give applications for random routing in Cayley networks, general node symmetric networks, edge symmetric networks, and de Bruijn networks. Finally, we examine the problems arising when our approach is applied to routing along non-shortest paths, deterministic routing, or routing with bounded buffers.