A Probability Inequality and Its Application to Switching Networks

In this paper we consider a switching network as a directed graph. A vertex is called a switch if its in-degree and out-degree are both positive, an input terminal if it has in-degree zero and out-degree one, and an output terminal if it has in-degree one and out-degree zero. The edges between the switches are called links. A switch is said to be of size n X m if it has in-degree n and out-degree m. Every switch in our network is assumed to be two-sided nonblocking in the sense t h a t when the network is in actual use, traffic can be routed from every input link to every output link in a switch, provided the two links involved are not carrying other traffic, and regardless of the traffic carried by other links. In a multistage switching network, the switches are partitioned into a sequence of stages with the following properties. (i) The sizes of switches in a given stage are identical. 821 (ii) All input terminals are connected to the switches of the first stage; all output terminals are connected to the switches of the last stage. (iii) Links exist only between two switches in adjacent stages. [We call links between the z'th stage and the (i 4- l)st stage the ith-stage links.] The direction of an ith-stage link is from the ith stage to the (i + l)st stage. A channel graph between a given input terminal and a given output terminal is the smallest subgraph containing all paths connecting the two terminals. Since a link in a path is also shared by other paths connecting possibly other pairs of terminals, the actual routing of a path will fail if any link involved has already been used to route some other path.