A central issue in the design of modern communication networks is that of p
roviding performance guarantees. This issue is particularly important if th
e networks support real-time traffic such as voice and video. The most crit
ical 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 i
s defined. For each session i, packets are injected at a rate r(i) to follo
w a predetermined path of length d(i). Due to limited bandwidth, only one p
acket at a time may advance on an edge (link). Session paths may overlap su
bject to the constraint that the total rate of sessions using any particula
r 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 as
ymptotically 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 o
btain a delay bound of O(c(i) + d(i)) for packets on path P-i, where d(i) i
s 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 gener
alized to (leaky-bucket constrained) bursty traffic, where session i tolera
tes 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.