Universal packet routing with arbitrary bandwidths and transit times

Britta Peis, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations

Abstract

We prove bounds for the length of optimal schedules for store-and-forward packet routing in the setting of arbitrary bandwidths and transit times. The problem is commonly studied only in the setting of unit bandwidths and unit 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 trivial lower bounds congestion and dilation. If every link in the network has a certain minimum transit time or capacity our bounds improve even further up to 4.32(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. This is the first improvement of the bounds for this very fundamental problem in more than 10 years.

Original languageEnglish
Title of host publicationInteger Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
Pages362-375
Number of pages14
DOIs
StatePublished - 2011
Externally publishedYes
Event15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011 - New York, NY, United States
Duration: 15 Jun 201117 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6655 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
Country/TerritoryUnited States
CityNew York, NY
Period15/06/1117/06/11

Fingerprint

Dive into the research topics of 'Universal packet routing with arbitrary bandwidths and transit times'. Together they form a unique fingerprint.

Cite this