   Next: 3.2 The main result Up: 3 An -step schedule Previous: 3 An -step schedule

## 3.1 A preliminary result

Before proving the main result of this section, we show that there is a schedule of length that uses queues of size . This preliminary result is substantially simpler to prove because of the relaxed bounds on the schedule length and queue size. Nevertheless, it illustrates the basic ideas necessary to prove the main result. We begin by proving a lemma that is used in the proofs of both the preliminary result and the main result.

Before proceeding, we need to introduce some notation. A T-frame is a sequence of T consecutive time steps. The frame congestion, C, in a T-frame is the largest number of packets that traverse any edge in the frame. The relative congestion, R, in a T-frame is the ratio of the congestion in the frame to the size of the frame. Proof: The proof uses the Lovász Local Lemma. The first step is to assign an initial delay to each packet. Without loss of generality, we assume that c=d. The delays are chosen from the range , where is a fixed constant that will be determined later. In the resulting schedule, , a packet that is assigned a delay of x waits in its initial queue for x steps, then moves on to its destination without waiting again until it enters its final queue. The length of is at most . We use the Lovász Local Lemma to show that if the delays are chosen randomly, independently, and uniformly, then with nonzero probability the relative congestion in any frame of size or greater is at most 1. Thus, such a set of delays must exist.

To apply the Lovász Local Lemma, we associate a bad event with each edge. The bad event for edge g is that more than T packets use g in some T-frame, for . To show that there is a way of choosing the delays so that no bad event occurs, we need to bound the dependence, b, among the bad events and the probability, p, of each individual bad event occurring.

The dependence calculation is straightforward. Whether or not a bad event occurs depends solely on the delays assigned to the packets that pass through the corresponding edge. Thus, two bad events are independent unless some packet passes through both of the corresponding edges. Since at most c packets pass through an edge, and each of these packets passes through at most d other edges, the dependence, b, of the bad events is at most .

Computing the probability of each bad event is a little trickier. Let p be the probability of the bad event corresponding to edge g. Then This expression is derived as follows. Frames of size greater than d cannot have relative congestion greater than 1, since the total congestion is only d. Thus, we can ignore them. We bound the probability that any frame has relative congestion greater than 1 by summing, over all frame sizes T from to d, the probability that some T-frame has relative congestion greater than 1. Furthermore, for any T, there are at most different T-frames and we bound the probability that any one of them has relative congestion greater than 1 by summing their individual probabilities. The number of packets passing through g in any T-frame has a binomial distribution. There are d independent Bernoulli trials, one for each packet that uses g. Since at most T of the possible delays will actually send a packet through g in the frame, each trial succeeds with probability . (Here we use the assumption that the paths are edge-simple.) The probability of more than T successes is at most .

For sufficiently large, but fixed, the product 4pb is less than 1, and thus, by the Lovász Local Lemma, there is some assignment of delays such that the relative congestion in any frame of size or greater is at most 1.

to .667emto .667em Proof: For simplicity, we shall assume without loss of generality that c=d, so that the bounds on the length and queue size are and , respectively.

The proof has the following outline. We begin by using Lemma 3.2 to produce a schedule in which the number of packets that use an edge in any -frame is at most . Next we break the schedule into  -frames, as shown in Figure 3. Finally, we view each -frame as a routing problem with dilation and congestion , and solve it recursively. Figure 3: Schedule . The schedule is derived from the greedy schedule, , by assigning an initial delay in the range to each packet. We use the Lovász Local Lemma to show that within each -frame, at most packets pass through each edge.

Each -frame in can be viewed as a separate scheduling problem where the origin of a packet is its location at the beginning of the frame, and its destination is its location at the end of the frame. If at most packets use each edge in a -frame, then the congestion of the problem is . The dilation is also because in time steps a packet can move a distance of at most . In order to schedule each frame independently, a packet that arrives at its destination before the last step in the rescheduled frame is forced to wait there until the next frame begins.

All that remains is to bound the length of the schedule and the size of the queues. The recursion proceeds to a depth of at which point the frames have constant size, and at most a constant number of packets use each edge in each frame. The resulting schedule can be converted to one in which at most one packet uses each edge in each time step by slowing it down by a constant factor. Since the length of the schedule increases by a constant factor during each recursive step, the length of the final schedule is . The bound on the queue size follows from the observation that no packet waits at any one spot (other than its origin or destination) for more than consecutive time steps, and in the final schedule at most one packet traverses each edge at each time step.

to .667emto .667em   Next: 3.2 The main result Up: 3 An -step schedule Previous: 3 An -step schedule

Bruce Maggs
Mon Jul 22 20:27:47 EDT 1996