On-line algorithms for path selection in a nonblocking network
Sanjeev Arora, T. Leighton, Bruce MacDowell Maggs · 1990
Nonblocking networks arise in a variety of applications involving communications.The most well known examples include telephone networks, data networks, and distributed memory architectures.Although asymptotically optimal constructions are known for nonblocking networks in a variety of models, it is generally not known how to select paths for the desired network connections efficiently on-line.In this paper, 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(logN) 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(logN) 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.