General dynamic routing with per-packet delay guarantees ofO(distance+1/session rate)

摘要

A central issue in the design of modern communication networks isthat of providing performance guarantees. This issue is particularlyimportant if the networks support read-time traffic such as voice andvideo. The most critical performance parameter to bound is the delayexperienced by a packet as it travels from its source to itsdestination. We study dynamic routing in a connection-orientedpacket-switching network. We consider a network with arbitrary topologyon which a set of sessions is defined. For each session i, packets areinjected at a rate r_i to follow a predetermined path oflength d_i. Due to limited bandwidth, only one packet at atime may advance on an edge. Session paths may overlap subject to theconstraint that the total rate of sessions using any particular edge isless than 1. We address the problem of scheduling the sessions at eachswitch, so as to minimize worst-case packet delay and queue buildup atthe switches. We show the existence of an asymptotically-optimalschedule that achieves a delay bound of O(1/r_i+d_i)with only constant-size queues at the switches. We also present a simpledistributed algorithm that, with high probability, delivers everysession-i packet to its destination within O(1/r_i+d_i log(m/r_min)) steps of its injection, where r_min is the minimum session rate, and m is the number of edges in thenetwork. Our results can be generalized to (leaky-bucket constrained)bursty traffic, where session i tolerates a burst size of b_i.In this case, our delay bounds become O(b_i/r_i+d_i) and O(b_i/r_i+d_i log(m/r_min)), respectively