ALCOMFT-TR-03-139

Costas Busch, Malik-Mgdon Ismail, Marios Mavronicolas and Roger Wattenhofer
Greedy ~O(C+D) Hot-Potato Routing on Trees
Cyprus. Work packages 2 and 4. December 2003.

Abstract: In hot-potato (deflection) routing, nodes in the network have no buffers for packets in transit. A hot-potato routing algorithm is greedy if packets are advanced from their sources towards their destinations whenever possible. Th dilation D is the longest distance a packet has to travel. The congestion C is the maximum number of packets that traverse any edge. The routing time of a routing algorithm is the time for the last packet to reach its destination. A well known lower bound on the routing time is Omega(C+D). When is it possible to design routing algorithms whose routing times match this lower bound?

Here, we address this fundamental question within the context of hot-potato routing for the specific case of a tree with n nodes. In particular, we present two greedy, hot-potato routing algorithms.

• A deterministic algorithm, which has a routing time of O((\delta C + D) lg n), where \delta is the maximum node degree. Thus, for bounded-degree trees, the routing time becomes O((C+D) lg n).

• A randomized algorithm, which has a routing time of O((C+D) lg² n) with high probability. Randomization is used for adjusting packet priorities.

Both algorithms are online and simple yet efficient. They are built upon the idea of using safe deflections, which are deflections whose net effect is to "recycle" edges from one path to another. These are the first known hot-potato routing algorithms (whether greedy or not) for trees whose routing time is within logarithmic factors of the Omega(C+D) lower bound.

Postscript file: ALCOMFT-TR-03-139.ps.gz (718 kb).