TY - GEN
T1 - Universal packet routing with arbitrary bandwidths and transit times
AU - Peis, Britta
AU - Wiese, Andreas
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79960004477&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-20807-2_29
DO - 10.1007/978-3-642-20807-2_29
M3 - Conference contribution
AN - SCOPUS:79960004477
SN - 9783642208065
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 362
EP - 375
BT - Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
T2 - 15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
Y2 - 15 June 2011 through 17 June 2011
ER -