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 trac 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 dened. 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", for any constant " 2 (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