Nonblocking networks arise in a variety of communications contexts. Common examples include telephone systems and network architectures for parallel computers. In a typical application, there are 2N terminals (usually thought of as N inputs and N outputs) interconnected by switches that can be set to link the inputs to the outputs with node-disjoint paths according to a specified permutation. (Switches are also called nodes.) In a nonblocking network, the terminals and nodes are interconnected in such a way that any unused input-output pair can be connected by a path through unused nodes, no matter what other paths exist at the time. The 6-terminal graph shown in Figure 1.1, with inputs Bob, Ted, and Pat and outputs Vanna, Carol, and Alice, for example, is nonblocking because no matter which input-output pairs are connected by a path, there is a node-disjoint path linking any unused input-output pair. In particular, if Bob is talking to Alice and Ted is talking to Carol, then Pat can still call Vanna.
Figure 1.1: A nonblocking network with
3 inputs and 3 outputs.
The notion of a nonblocking network has several variations. The nonblocking network in Figure 1.1 is an example of the most commonly studied type. This network is called a strict-sense nonblocking connector, because no matter what paths are established in the network, it is possible to establish a path from any unused input to any unused output. A slightly weaker notion is that of a wide-sense nonblocking connector. A wide-sense nonblocking connector does not make the same guarantee as a strict-sense nonblocking connector. A network is a wide-sense nonblocking connector if there is an algorithm for establishing paths in the network one after another so that after each path is established, it is still possible to connect any unused input to any unused output. Still weaker is the notion of a rearrangeable connector. A rearrangeable connector is capable of realizing any 1-1 connection of inputs to outputs with node-disjoint paths provided that all the connections to be made are known in advance. A nonblocking or rearrangeable connector is a called a generalized connector if it has the additional property that each input can be simultaneously connected to an arbitrary set of outputs, provided that every output is connected to just one input. Generalized connectors are useful for multiparty calling in a telephone network as well as for broadcasting in a parallel machine.