next up previous
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 tex2html_wrap_inline992 using queues of size tex2html_wrap_inline994 , 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 tex2html_wrap_inline1002 , where tex2html_wrap_inline1004 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 tex2html_wrap_inline1010 packets use a particular edge g at a particular time step t is at most

displaymath1016

since at most c different packets pass through g, and for each of these, at most one of the tex2html_wrap_inline1022 possible delays sends it through g at step t. This sum is at most tex2html_wrap_inline1028 . To bound the probability that more than tex2html_wrap_inline1030 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 tex2html_wrap_inline1038 . Using the inequality tex2html_wrap_inline1040 for 0 < b < a, and noting that tex2html_wrap_inline1044 , we see that for large enough, but fixed, tex2html_wrap_inline1046 , the product is at most tex2html_wrap_inline1048 . Thus, with high probability, no more than tex2html_wrap_inline1050 packets will want to traverse any edge at any step of this unconstrained schedule.

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



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



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