Near-optimal hot-potato routing on trees
SourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Google Scholar check
MetadataShow full item record
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 greedyso, routing decisions are made locally, and packets are advanced towards their destinations whenever possible. © Springer-Verlag 2004.