Static and Dynamic Hot-Potato Packet Routing in Communication Networks

We consider a problem of scheduling packets in communication networks subject to the ``hot potato'' restriction. In a static version, the problem is to route a set of packets in a communication graph from the origins to destinations along the pre-specified paths in minimal (makespan) time subject to the ``hot potato'' constraint that no packets wait in the intermediate nodes of their corresponding paths. In a dynamic version, the packets are injected over time by an adversary and the problem is to construct a stable schedule which satisfies the ``hot potato'' requirement. For the static version of the problem we prove that the ratio between the optimal makespan time and the natural lower bound -congestion asymptotically does not exceed O(\sqrt{m}) when the total number of packets diverges to infinity, where m is the number of edges in the graph. We complement this result with an instance of the problem for which this ratio is achieved. We also provide a complete classification of graphs for which this ratio is asymptotically equal to one. Our results have immediate ramifications to the dynamic version of the problem in terms of maximal arrival rates for which there exist a stable ``hot potato'' scheduling policy against an arbitrary adversary.