Reswitching of Connection Networks

In a three-stage network of the type pictured in Fig. 1, it is possible that a connection between an input and an output cannot be made despite the fact that neither is already connected. This could happen if other connections already occupy at least one link in every possible path between the input and output in question. As first established by Slepian, 1 a blocked connection in such a network can be unblocked by rearranging the connections already set up in the network. Slepian further showed that such a rearrangement would never require disturbing more than 2n -- 2 calls, where the size of the switches in each stage is n by n, and there are n switches per stage. In the first sections of this article I give a proof that to unblock a connection in such a network in no case requires disturbing more than n -- 1 calls, and furthermore for every n > 1 there is at hast one network state in which n -- 1 calls must be disturbed to unblock a blocked connection. In subsequent sections various generalizations upon which partial results have been obtained are discussed. These include results on different network configurations, and networks having more than three stages. As discussed in the body of this paper, the physical consequence of a 833