On-line algorithms for path selection in a nonblocking network

We present the first optimal-time algorithms for path selection in an optimal-size nonblocking network. In particular, we describe a bounded-degree, O(N log N)-switch nonblocking network that can realize any sequence of connections and disconnections among N terminals with O(log N) bit-step delay. Viewed in the context of a telephone switching network, our network and algorithm can handle any sequence of calls among N parties with O(log N) bit-step delay per call (even if many calls are made at once). Parties can hang up and call again whenever they like, and multiparty calls can be made without affecting the performance of the algorithm - every call is still put through in O(log N) time. Viewed in the context of distributed memories for parallel machines, our algorithm allows any processor to access any idle block of memory within O(log N) bit-steps at any time - no matter what other connections have been made previously or are being made simultaneously.