Universal packet routing with arbitrary bandwidths and transit times

Britta Peis and Andreas Wiese

not available

Packet Routing, Scheduling, Lovasz Local Lemma, Bounds Optimal Makespan

A fundamental problem in communication networks is store-and-forward packet routing. In a celebrated paper Leighton, Maggs, and Rao proved that the length of an optimal schedule is linear in the trivial lower bounds congestion and dilation. However, there has been no improvement on the actual bounds in more than 10 years. Also, commonly the problem is studied only in the setting of unit bandwidths and unit transit times. In this paper, we prove bounds on the length of optimal schedules for packet routing in the setting of arbitrary bandwidths and arbitrary transit times. Our results generalize the existing work to a much broader class of instances and also improve the known bounds significantly. For the case of unit transit times and bandwidths, we improve the best known bound of 39(C+D) to 23.4(C+D), where C and D denote the congestion and dilation, respectively. If every link in the network has a certain minimum transit time or capacity we improve this bounds to up to 4.25(C+D). Key to our results is a framework which employs tight bounds for instances where each packet travels along only a small number of edges. Further insights for such instances would reduce our constants even more.

Download as [PDF]