Greedy O(C+D) Hot-Potato Routing on Trees Costas Busch Malik Magdon-Ismail Marios Mavronicolas Roger Wattenhofer 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 toward their destinations whenever possible. The 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: i. A deterministic algorithm, which has a routing time of O(([delta]· C+D)lgn), where [delta] is the maximum node degree; thus, for bounded degree trees, the routing time becomes O((C +D)lgn). ii. A randomized algorithm which has a routing time of O((C + D)lg2 n) with high probability, for any node degree. Randomization is used for adjusting packet priorities. Both algorithms are online and simpleyet efficient. They arebuilt upontheideaof 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. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 07/11/2003 cs-03-07
Greedy O(C+D) Hot-Potato Routing on Trees
Costas Busch
Malik Magdon-Ismail
Marios Mavronicolas
Roger Wattenhofer
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 toward their destinations whenever possible. The 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: i. A deterministic algorithm, which has a routing time of O(([delta]· C+D)lgn), where [delta] is the maximum node degree; thus, for bounded degree trees, the routing time becomes O((C +D)lgn). ii. A randomized algorithm which has a routing time of O((C + D)lg2 n) with high probability, for any node degree. Randomization is used for adjusting packet priorities. Both algorithms are online and simpleyet efficient. They arebuilt upontheideaof 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.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
07/11/2003
cs-03-07