Startseite > Publikationen > Publikationen


Meyer auf der Heide, Friedhelm;Vöcking, Berthold:

Shortest Paths Routing in Arbitrary Networks.

Journal on Algorithms 31: S. 105-131, Jun. 1999


We introduce an on-line protocol which routes any set of N packets along shortest paths with congestion C and dilation D through an arbitrary network in O(C+D+logN) steps, with high probability. This time bound is optimal up to the additive logN, and it has previously only been reached for bounded-degree leveled networks. Further, we show that the above bound holds also for random routing problems with C denoting 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.




author = {Meyer auf der Heide, Friedhelm and V{\"o}cking, Berthold},
title = {Shortest Paths Routing in Arbitrary Networks},
journal = {Journal on Algorithms},
volume = {31},
pages = {105-131},
month = jun,
year = {1999},

BibTeX in die Zwischenablage kopieren