Greedy Õ(C+D) Hot-Potato Routing on Trees
Costas Busch, Malik Magdon‐Ismail, Marios Mavronicolas, Roger P. Wattenhofer · 2003
In hot-potato (deflection) routing, nodes in the network have no bu#ers for packets in transit. A hotpotato 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 # C +D).