Next: 3 An -step schedule Up: Packet Routing and Job-Shop Previous: 1 Introduction

# 2 An on-line algorithm

There is a simple randomized on-line algorithm for producing a schedule of length using queues of size , where c is the congestion, d is the dilation, and N is the number of packets.

First, each packet is assigned a delay chosen randomly, independently, and uniformly from the interval , where is a constant that will be specified later. A packet that is assigned a delay of x waits in its initial queue for x time steps, and then moves on to its final destination without ever stopping.

The trouble with this schedule is that several packets may traverse the same edge in a single step. However, we can bound the number of packets that are likely to do so. The probability that more than packets use a particular edge g at a particular time step t is at most

since at most c different packets pass through g, and for each of these, at most one of the possible delays sends it through g at step t. This sum is at most . To bound the probability that more than packets pass through any edge at any time step, we multiply this quantity by the number of choices for g, at most Nd, and the number of choices for t, at most . Using the inequality for 0 < b < a, and noting that , we see that for large enough, but fixed, , the product is at most . Thus, with high probability, no more than packets will want to traverse any edge at any step of this unconstrained schedule.

Each step of the unconstrained schedule can be simulated by steps of a legitimate schedule. The final schedule requires steps to complete the routing, and uses queues of size .

Next: 3 An -step schedule Up: Packet Routing and Job-Shop Previous: 1 Introduction

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