• 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.

  HTML Postscript Compressed Postscript
  Back to other publications

  Back to my home page