Permutation Groups, Complexes, and Rearrangeable Connecting Networks
Vladimír Beneš · Bell System Technical Journal · 1964
In the interest of providing good telephone service with efficient connecting networks, it is desirable to have at hand a knowledge of some of the combinatorial properties of such networks. One of these properties is 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 that the idle inlet can be connected to the idle outlet. A natural algebraic and combinatorial approach to the study of rearrangeable networks is described, with attention centered principally on two-sided networks built of stages of square crossbar switches, each stage having N inlets and N outlets. The approach is based in part on the elementary theory of permutation groups. The principal problem posed (and partly answered) is this: What connecting networks built of stages are rearrangeable? Sufficient conditions, including all previously known results, are formulated and exemplified.