Permutation Groups, Complexes, and Rearrangeable Connecting Networks

A connecting network is an arrangement of switches and transmission links through which certain terminals can be connected together in many combinations. Typical examples of connecting networks can be found in telephone central offices, where they are used to complete calls among the customers themselves, and between customers and outgoing trunks leading to other offices. In the interest of providing good service with efficient connecting networks, it is desirable to have a thorough understanding of some of the combinatorial properties of such networks. In a previous paper,1 we singled out three such combinatory properties as useful in assessing the performance of connecting networks. The weakest of these properties 1(519 l()2fi THE BELL SYSTEM TECHNICAL JOURNAL, J U L Y 1904 was that of rearrangeability. A connecting network is rearrangeable if its permitted states realize every assignment of inlets to outlets, or alternatively, if given any state x of the network, any inlet idle in x, and any outlet idle in x, there is a way of assigning new routes (if necessary) to the calls in progress in x so as to lead to a new state of the network in which the idle inlet can be connected to the idle outlet. Figs. 1 and 2 show the structure of two connecting networks built out of square crossbar switches, with each switch capable of connecting any subset of its inlets to an e qui numerous subset of its outlets in any desired one-one combination. The network of Fig. 1 is often found in telephone central offices; we may call it the No.