Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Universal packet routing with arbitrary bandwidths and transit times
Author(s): Peis, Britta
Wiese, Andreas
Type: Research Paper
Abstract: 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.
Subject(s): packet routing
Lovasz local lemma
bounds optimal kakespan
Issue Date: 2010
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2010, 24
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 462.55 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.