@device(postscript) @libraryfile(Mathematics10) @libraryfile(Accents) @style(fontfamily=timesroman,fontscale=11) @pagefooting(immediate, left "@c", center "@c", right "@c") @heading @heading(CMU-CS-96-152) @center(@b(F. Tom Leighton@foot, Bruce M. Maggs, Andrea W. Richa)) @center(July 1996) @center(FTP: CMU-CS-96-152.ps) @blankspace(1) @begin(text) In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to their destinations in @math steps using constant-size queues, where @math is the congestion of the paths in the network, and @math is the length of the longest path. The proof, however, used the Lov@aac()sz Local Lemma and was not constructive. In this paper, we show how to find such a schedule in @math time, with probability @math<1#@Sub#1/P@+[b]>, for any positive constant @math, where @math

is the sum of the lengths of the paths taken by the packets in the network. We also show how to parallelize the algorithm so that it runs in @math. The method that we use to construct the schedules is based on the algorithmic form of the Lov@aac()sz Local Lemma discovered by Beck. @blankspace(2line) @begin(transparent,size=10) @b(Keywords:@ )@c @end(transparent) @blankspace(1line) @end(text) @flushright(@b[(15 pages)])