Optimal Rearrangeable Multistage Connecting Networks

A study of rearrangeable connecting networks, begun in a previous paper,1 is here continued; the object of the present work is to solve the synthesis problem of choosing, from a class of networks that are built of stages of square switches and satisfy some reasonable conditions on uniformity of switch size, a rearrangeable connecting network having a minimum number of crosspoints. Some of the terminology, notation, and results of Ref. 1 are used, and familiarity with it will be assumed from Section IV on. Naturally, we do not pretend that minimizing the number of crosspoints (used to achieve a given end) is the only consideration relevant to the design of a connecting network. Other factors, like the number 1641 1642 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1964 of memory elements, the amount and placing of terminal equipment, the ease with which a network is controlled (e.g., the possibility of reliable end-marking), etc., maj r be of overriding significance, depending on the technology used. Still, it is important to know the limits of the region of possible designs, and these are obtained by optimizing 011 one variable without attention to others. T h e problem of designing a good rearrangeable network was (probably first) considered in a paper of C. E. Shannon2 investigating memory requirements in a telephone exchange. On the networks that he considered he imposed the realistic "separate memory condition" to the effect that in operation a separate part of the memory can be assigned to each call in progress.