Near-optimal hot-potato routing on trees
Date
2004Source
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Volume
3149Pages
820-827Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
In hot-potato (deflection) routing, nodes in the network have no buffers for packets in transit, which causes conflicting packets to be deflected away from their destinations. We study one-to-many batch routing problems on arbitrary tree topologies. We present two hot-potato routing algorithms, one deterministic and one randomized, whose routing times are asymptotically near-optimal (within poly-logarithmic factors from optimal). Both algorithms are distributed and greedy so, routing decisions are made locally, and packets are advanced towards their destinations whenever possible. © Springer-Verlag 2004.