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

A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as voice and video. The most critical performance parameter to bound is the delay experienced by a packet as it travels from its source to its destination. We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r(i) to follow a predetermined path of length d(i). Due to limited bandwidth, only one packet at a time may advance on an edge (link). Session paths may overlap subject to the constraint that the total rate of sessions using any particular edge is at most 1 - epsilon for any constant epsilon is an element of (0, 1). We address the problem of scheduling the sessions at each switch, so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of a periodic schedule that achieves a delay bound of O(1/r(i) + d(i)) with only constant-size queues at the switches. This bound is asymptotically optimal for periodic schedules. A consequence of this result is an asymptotically optimal schedule for the static routing problem, wherein all packets are present at the outset. We obtain a delay bound of O(c(i) + d(i)) for packets on path P-i, where d(i) is the number of edges in P-i and c(i) is the maximum congestion along edges in P-i. This improves upon the previous known bound of O (c + d), where d = max(i)d(i) and c = max(i)c(i). We also present a simple distributed algorithm that, with high probability, delivers every session-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 the network. Our results can be generalized to (leaky-bucket constrained) bursty traffic, where session i tolerates a burst size of b(i). n 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.