- Randomized routing and sorting on fixed-connection
networks. F. T. Leighton, B. M. Maggs, S. B. Rao, and A. G.
Ranade, Journal of Algorithms, Vol. 17, No. 1, July 1994, pp.
- This paper presents a randomized on-line algorithm for scheduling any
set of N packets whose paths are fixed and have congestion c on
any bounded-degree leveled network with depth L. With high
probability, the algorithm delivers the packets to their destinations
in O(c+L+log N) steps, using constant-size queues. The scheduling
algorithm yields the first algorithm for routing permutations of N
packets on the shuffle-exchange network in O(log N) steps using
constant-size queues, for sorting on butterfly and shuffle-exchange
networks in O(log N) steps using constant-size queues, and for
routing and sorting on N^k-node multidimensional arrays in O(kN)
steps using constant-size queues. The algorithm also leads to the
construction of an area-universal network: an N-node network
with area Theta(N) that can simulate any other network of area
O(N) with slowdown O(log N).
- Back to other
- Back to my home page