TY - CHAP
T1 - Near-optimal hot-potato routing on trees
AU - Busch, Costas
AU - Magdon-Ismail, Malik
AU - Mavronicolas, Marios
AU - Wattenhofer, Roger
PY - 2004
Y1 - 2004
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=35048829948&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048829948&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-27866-5_109
DO - 10.1007/978-3-540-27866-5_109
M3 - Chapter
AN - SCOPUS:35048829948
SN - 3540229248
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 820
EP - 827
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Danelutto, Marco
A2 - Vanneschi, Marco
A2 - Laforenza, Domenico
PB - Springer Verlag
ER -