direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2010

Universal packet routing with arbitrary bandwidths and transit times
Zitatschlüssel Report-024-2010
Autor Britta Peis and Andreas Wiese
Jahr 2010
Nummer 024
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag