direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 24-2010

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Universal packet routing with arbitrary bandwidths and transit times
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe