next up previous
Next: 2.1 Leveled networks Up: Randomized Routing and Sorting Previous: 1.5 Some comments on

2 An scheduling algorithm for leveled networks


In this section we present a randomized algorithm for scheduling the movements of a set of N packets in a leveled network with depth L. By assumption, the paths taken by the packets are given and have congestion c. With high probability, the algorithm delivers all of the packets to their destinations in tex2html_wrap_inline2031 steps. The algorithm is on-line in the sense that the schedule is produced as the packets are routed through the network. (Note: The number of nodes in the network does not appear in the time to deliver the packets or in the probability of success. There may be more than N or fewer.)

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996