- On-line algorithms for path selection in a nonblocking
network. S. Arora, B. M. Maggs, and F. T. Leighton, SIAM
Journal on Computing, Vol. 25, No. 3, June 1996, pp. 600-625.
- This paper presents the first optimal-time algorithm for path
selection in an optimal-size nonblocking network. In particular, we
describe an N-input, N-output, nonblocking network with O(N log N)
bounded-degree switches, and an algorithm that can satisfy any request
for a connection or disconnection between an input and an output in
O(log N) bit steps, even if many requests are made at once. Viewed
in a telephone switching context, the algorithm can put through any
set of calls among N parties in O(log N) bit steps, even if many
calls are placed simultaneously. Parties can hang up and call again
whenever they like; every call is still put through O(log N) bit
steps after being placed. Viewed in a distributed memory machine
context, our algorithm allows any processor to access any idle block
of memory within O(log N) bit-steps, no matter what other
connections have been made previously or are being made
simultaneously.

**Back to other
publications**

**Back to my home page**