© 2002 by British Computer Society
Lower Bounds for One-to-one Packet Routing on Trees using Hot-Potato Algorithms
1 University of Sydney, Sydney NSW 2006, Australia Email: alanr@zip.com.au 2 Department of Mathematics, University of Ioannina, 45110 Ioannina, Greece 3 School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada
In this paper, we consider hot-potato packet routing of one-to-one routing patterns on $n$-node trees. By applying a ‘charging argument’, we show that any greedy hot-potato algorithm routes a one-to-one routing pattern within $2(n-1)$ steps. On the other hand, a trivial lower bound suggests that at least $3n/2$ steps are required by any oblivious greedy algorithm. As the main contribution of the paper, we tighten the $2(n-1)$ upper bound by constructing (for all sufficiently large $n$) an elaborate one-to-one packet routing problem on an $n$-node tree for which an oblivious greedy hot-potato algorithm requires at least $2n-o(n)$ steps. This improved lower bound is also shown to be valid for the minimum-distance heuristic. For trees of maximum degree $d$, we establish a lower bound of $2((d-3)/(d-2))n-o(n)$ routing steps.