Efficient One-Sided Rearrangeable Multistage Switching Network

This invention relates to switching networks and, more particularly, to rearrangeable switching networks.

Switching systems such as the telephone switching network are generally designed to interconnect, upon request selected pairs of customer terminals from a large plurality of terminals connected to the system. The simplest connecting network capable of such interconnections is a single switching matrix designed to connect any idle customer terminal to any other idle terminals in the network, regardless of whether all other terminals in the network are interconnected therein.

To achieve this capability with a single switching matrix it is necessary to employ a number of elemental switches, or crosspoints, within the matrix which increases as the square of the number of customer terminals served by the network. This may result in matrices having prohibitively large numbers of crosspoints.

Fortunately it is not necessary to employ such a capable switching network because advantage can be taken of the theory of trunking probability which recognizes that seldom are more than 10 percent of the terminals active at any particular time. In view of this theory of trunking probability, it is possible, and economically advantageous, to use a less capable switching network.

One such less capable switching arrangement is realized with a multistage connecting network which comprises an ordered plurality of s interconnected stages ( v.sub.i). In such a multistage network, each stage v.sub.i includes a plurality of switches v.sub.i1, v.sub.i2 . . . v.sub.ir.sbsb.i having input and output links. The input links of each switch in a stage are respectively connected to the output links of switches in the preceding stage while the output links of each switch in a stage are respectively connected to the input links of switches in the succeeding stage. The input links of the first stage switches are connected to customer terminals termed input terminals, and the output links of the last stage switches are connected to customer terminals termed output terminals. For purposes of the instant specification, it is assumed that each first stage switch, v.sub.1j, has n input links, that each last stage switch, v.sub.sj, has n output links, that there are n input switches (r.sub.1 =n) and that there are n output switches (r.sub.s =n). Additionally, only a three-stage network (s=3) is described herein, although it is to be understood that the disclosed invention is applicable to any value of s.

The words "input" and "output" of phrases "input terminals" and "output terminals" refer, of course, to the arbitrary input and output designations of the switching network. Each "input" or "output" terminal can in fact be the calling or the called party of an interconnection request. In a telephone system, for example, the input terminals may be the telephones of one central office while the output terminals may be the telephones of another central office.

As implied above, it is possible for a customer terminal connected to a multistage switching network to be blocked from being connected as desired, if the network happens to be interconnected in a manner that prevents effecting the desired interconnection. This, of course, is an undesirable situation which in an appropriately designed network can be remedied by dismantling existing interconnections and by rearranging the interconnection paths to accommodate the new request. When such a rearrangement is possible, it is said that the new assignment, which is the new set of interconnections desired to be established, is realizable. A network which can realize all possible assignments without rearranging existing connections is said to be nonblocking, while a network which can realize all possible assignments only by occasionally rearranging existing connections is said to be merely rearrangeable.

A network is said to be one-sided rearrangeable if it can realize all assignments which interconnect input terminals to all other input terminals, input terminals to output terminals and vice versa, and output terminals to all other output terminals.

A network is said to be two-sided rearrangeable if input terminals can only connect to output terminals (and vice versa).

A network is said to be input-mixed rearrangeable if input terminals can be connected to other input terminals or to output terminals, but output terminals cannot connect to other output terminals. Similarly, a network is said to be output-mixed rearrangeable if output terminals can connect to other output terminals or to input terminals, but input terminals cannot connect to other input terminals.

The above definitions of one-sided rearrangeability, two-sided rearrangeability, input-mixed rearrangeability and output-mixed rearrangeability can be applied to a switch v.sub.ij in the same manner as applied to a network.

FIG. 1 illustrates a prior art three-stage input-mixed rearrangeable network. It comprises stages v.sub.1 (element 10), v.sub.2 (element 20) and v.sub.3 (element 30). Stage v.sub.1, in turn, comprises r.sub.1 input-mixed rearrangeable switches v.sub.11, v.sub.12 . . . v.sub.1r.sbsb.1, stage v.sub.2 comprises r.sub.2 one-sided rearrangeable switches v.sub.21, v.sub.22 . . . v.sub.2r.sbsb.2, and stage v.sub.3 comprises r.sub.3 output-mixed rearrangeable switches v.sub.31, v.sub.32 . . . v.sub.3r.sbsb.3. As indicated above, r.sub.1 =n, r.sub.3 =n, switches v.sub.1j have n input links each and, similarly, switches v.sub.3j have n input links each. Since one output link of each v.sub.1j switch is connected to an input link of each v.sub.2j switch, and since there are r.sub.2 second stage switches, each v.sub.1j switch must have r.sub.2 output links. For corresponding reasons, each v.sub.3j switch has r.sub.2 input links while each v.sub.2j switch has r.sub.1 (equal to n ) input links and r.sub.3 (equal to n ) output links. Because the v.sub.2j switches are one-sided rearrangeable, the distinction between input and output links need not be maintained. It may be said, therefore, that the v.sub.2j switches have 2n input/output links (I/O links).

To help in ascertaining the number of crosspoints required for each particular type of switch, switches v.sub.11 and v.sub.21 are illustrated in FIG. 1 with the prior art internal arrangement of elemental switches, or crosspoints, within each type of switch. Modeled after the switch arrangements shown in "Mathematical Theory of Connecting Networks for Telephone Logic" by V. E. Benes, Academic Press, 1965, Chap. 4, FIGS. 9 and 10, the one-sided rearrangeable switch v.sub.21 is depicted as a triangular switch with each I/O link connected to a bus line that intersects bus lines connected to the other I/O links of the switch. The intersections of all of the bus lines are connected with normally open elemental switches such as switch 103, and the closure of those crosspoints effectuate the desired interconnection. It can mathematically be shown, as well as seen from the drawing of FIG. 1, that the triangular switch v.sub.21 is nonblocking, i.e., any I/O link may be connected to any idle I/O link in the switch by the closure of a single crosspoint, irrespective of whether the other I/O links are connected. It can also be seen that in a v.sub.21 type switch having x input links and y output links, the number of elemental switches, or crosspoints, required to implement the switch is equal to (x+y) (x+y-1)/2 or approximately (x+y).sup.2 /2.

Also in accordance with the above mentioned Benes book, the input-mixed rearrangeable switch v.sub.11 is depicted as a trapezoidal switch. It may be viewed as a triangular switch section v.sub.11, which connects any input link of switch v.sub.11, and a square switch section v.sub.11 " which connects input links of v.sub.11 to output links of v.sub.11. The square switch section v.sub.11 " function is achieved by connecting each input link of v.sub.11 to a bus line, e.g., 104, and each output link of v.sub.11 to a bus line, e.g., 105. The input link bus lines are arranged so that each input link bus line intersects all output bus lines, and the intersecting bus lines are interconnected with normally open elemental switches such as switch 106. It can be shown that the trapezoidal switch v.sub.11 is nonblocking in the same sense that the triangular switch v.sub.21 is nonblocking.

From the above it can be seen that the number of crosspoints required for the square switch section of the v.sub.11 type switch (for x input links and y output links) is equal to xy, and that the total number of crosspoints required for the v.sub.11 type switch is (x)(x-1)/2+xy, or approximately (x.sup.2 /2)+xy. Of course, it should be noted that the output-mixed rearrangeable switches of stage v.sub.3 are of the same construction as the input-mixed rearrangeable switches of stage v.sub.1. The stage v.sub.3 switches are drawn in FIG. 1 as mirror images of the stage v.sub.1 switches because the output links of v.sub.3 are on the right side whereas the input links of v.sub.1 are on the left side.

Since the stage v.sub.1 and v.sub.3 switches are rearrangeable (and nonblocking), any input terminal may be connected to any other terminal if a sufficient number of stage v.sub.2 switches are made available, i.e., if r.sub.2 is large enough to accommodate all input terminal/output terminal connections employing a particular v.sub.2 switch, plus whatever input terminal/input terminal (and output terminal/output terminal) connections may need to be made through the same particular v.sub.2 switch (e.g., connection between input (output) terminals associated with different v.sub.1 ( v.sub.2) switches). It can be shown that for the network of FIG. 1 to be rearrangeable, r.sub.2 must at least be equal to the integer part of 3 n/2, which for large values of n is essentially equal to 3 n/2. Calculating the total number of crosspoints required for the network of FIG. 1 results in stages v.sub.1 and v.sub.3 requiring n(n.sup.2 /2+ n3n/2), or 2 n.sup.3 crosspoints each, and stage v.sub.2 requiring 3n/2(4n/2), or 3 n.sup.3 crosspoints, for a total of 7n.sup. 3 crosspoints.

It is an object of this invention to construct a one-sided rearrangeable network which has a number of crosspoints lower than the number of crosspoints required for the above prior art network.

This object, among others, is realized with a three stage one-sided rearrangeable switching network having input-mixed rearrangeable switches in the first switching stage, output-mixed rearrangeable switches in the third switching stage, and interconnected one-sided rearrangeable switches in the second switching stage. The interconnection of the one-sided switches in the second stage is accomplished by pairing off the switches and by interconnecting each pair with an auxiliary two-sided rearrangeable switch. Specifically, the I/O links of the first one-sided switch in a pair are connected to the input links of an associated auxiliary switch, and the output links of the associated auxiliary switch are connected to the I/O links of the second one-sided rearrangeable switch in the pair.

FIG. 1 depicts a block diagram of a prior art configuration for a one-sided rearrangeable multistage switching network;

FIG. 2 depicts a block diagram of a one-sided rearrangeable multistage switching network in accordance with the principles of this invention;

FIG. 3 describes the second stage interconnection requirements associated with a circular interconnection assignment in a FIG. 1 network; and

FIG. 4 illustrates the interconnection paths of the FIG. 2 network arranged to implement a selected assignment.

FIG. 1 depicts a block diagram of a prior art one-sided rearrangeable network which was, in the interest of simplicity, limited to three stages. To make the FIG. 1 network operate, however, a control section must be employed which would maintain the necessary data related to the existing assignment and which would be capable of altering the assignment of the FIG. 1 network in response to additional interconnection requests. This control section is not illustrated in FIG. 1 because it relates only peripherally to the subject matter of this invention, and inclusion thereof, it is believed, would only confuse the issue.

For similar reasons, FIG. 2, which presents the block diagram of a three stage one-sided rearrangeable network in accordance with the principles of this invention, also does not illustrate the control section associated with the network. It is noted, however, that a number of known controllers are suitable for use with the networks of FIGS. 1 and 2 and that whatever control section is employed in conjunction with the network of FIG. 1 may also be employed in conjunction with the network of FIG. 2. For those interested, reference is made to a control section described by M. C. Paull in U.S. Pat. No. 3,129,407 issued Apr. 14, 1964.

As illustrated, FIG. 2 comprises a first switching stage, 40, designated v.sub.1, a second switching stage, 50, designated v.sub.2, and a third switching stage, 60, designated v.sub.3. Each switching stage v.sub.i contains an r.sub.i plurality of switches v.sub.ij j=1, 2 . . . r.sub.i and each v.sub.ij switch contains input links and output links. As in the network of FIG. 1, there are n input-mixed rearrangeable switches in stage v.sub.1, each having n input and r.sub.2 output links respectively connected to r.sub.2 switches in v.sub.2, and n output-mixed rearrangeable switches in stage v.sub.3, each having n output and r.sub.2 input links respectively connected to the r.sub.2 switches in v.sub.2. Also as in the network of FIG. 1, stage v.sub.2 has r.sub.2 one-sided rearrangeable switches each having 2n I/O links respectively connected to stages v.sub.1 and v.sub.3.

The FIG. 2 network differs from the FIG. 1 network in that the number of stage v.sub.2 switches, r.sub.2, is only equal to n, rather than 3n/2, and in that a number of auxiliary interconnecting switches are introduced into the stage v.sub.2 of FIG. 2. The purpose, construction, and the interconnections of those auxiliary switches will become apparent when the reason for the FIG. 1 requirement of v.sub.2 being equal to 3n/2 is more fully appreciated from the discussion below.

In general, any stage v.sub.2 switch may be employed to interconnect more than one pair of I/O links. An unusual situation occurs, however, when a desired assignment includes a circular assignment, as for example, { (I.sub.1,I.sub.2), (I.sub.2,I.sub.3), (I.sub.3,I.sub.1)} where I.sub.1, I.sub.2, and I.sub.3 represent an input terminal connected to v.sub.11, v.sub.12 and v.sub.13, respectively. FIG. 3 illustrates such an assignment for a FIG. 1 switching network with n=4 and shows that three stage v.sub.2 switches must be employed to implement the above circular assignment. This is shown with solid lines 210, 211, 212, 213, 214 and 215. From FIG. 3 it can also be seen that in order to connect the other two terminals associated with switch v.sub.11 to terminals associated with switches v.sub.12 and v.sub.13, three additional stage v.sub.2 switches are necessary. Thus, it appears that for n=4, r.sub.2 must equal 6, or 3n/2.

I have discovered that but for the circular assignments as described above, the value of r.sub.2 would need only be equal to n to make the network of FIG. 2 rearrangeable. Therefore, in accordance with the principles of this invention, the number of stage v.sub.2 switches is permitted to be as low as n (r.sub.2 .gtoreq. n) and the circular assignments implemented with auxiliary switches. Actually, since two interconnections of each circular assignment can be implemented by a pair of stage v.sub.2 triangular switches, the auxiliary switches need only implement the third interconnection in each circular assignment.

In FIG. 2, the auxiliary switches are depicted in FIG. 2 with blocks .mu..sub.1 . . . .mu..sub.r.sbsb.2/2. To interconnect the auxiliary switches, stage v.sub.2 switches, v.sub.2j, are grouped in pairs (which, conveniently, may be grouped into pairs of adjacent switches v.sub.2,2i.sub.-1 and v.sub.2,2i i=1, 2 . . . n/2) and each pair of switches is interconnected with an auxiliary two-sided rearrangeable switch .mu..sub.i. That is, the 2n I/O links of each switch v.sub.2,2i.sub.-1 are connected to the 2n input links of a two-sided rearrangeable switch .mu..sub.i, and the 2n I/O links of each switch v.sub.2,2i are connected to the 2n output links of switch .mu..sub.i. Again, since only one out of three possible interconnections needs to be implemented by any switch .mu..sub.i, each two-sided .mu..sub.i switch may advantageously comprise a cascade of two two-sided rearrangeable switches with one switch, .mu. .sub.i ', having 2n input links and 2n/3 output links and the other switch, .mu..sub.i ", having 2n/3 output links (connected to the 2n/3 input links of .mu..sub.i ') and 2n output links. This is shown diagrammatically within switch .mu..sub.1 of FIG. 2.

Computing the crosspoint count of individual switches, it can be seen that the number of crosspoints in stages v.sub.1 and v.sub.3 (having input-mixed and output-mixed switches) is ##EQU1## or 3n.sup.3 /2 crosspoints in each stage, the number of crosspoints in stage v.sub.2 (having triangular switches) is ##EQU2## and the number of crosspoints in switches .mu..sub.i is ##EQU3## for a total of ##EQU4## crosspoints (as compared to 7n.sup.3 for the network of FIG. 1).

Another reduction in the crosspoint count may be achieved when it is realized that if more than one switch is permitted to be closed for any particular interconnection, and if a two-sided rearrangeable switch has a number of output links that is at least equal to the number of its input links, then such a two-sided rearrangeable switch can also serve as an input-mixed rearrangeable switch. This can easily be shown when it is realized that an input-mixed assignment can be decomposed into two two-sided assignments which may be connected to the same output link bus by the closure of two crosspoints. If this simplification is employed in the network of FIG. 2, the input-mixed rearrangeable and the output-mixed rearrangeable switches of stages v.sub.1 and v.sub.3, respectively, can be replaced with two-sided rearrangeable switches, reducing thereby the crosspoint count of the FIG. 2 network to ##EQU5## crosspoints.

The following example is presented to illustrate the rearrangeability property of the FIG. 2 circuit.

Consider the assignment:

where I.sub.ij designates the j.sup.th input terminal in the i.sup.th switch of stage v.sub.1, where O.sub.ij designates the j.sup.th output terminal in the i.sup.th switch of stage v.sub.3 and where the two terminals within each parenthesized expression signify a desired interconnection.

FIG. 4 shows the interconnection of the above assignment in a switching network in accordance with the principles of this invention with n=4 and r.sub.2 =4. The interconnections of FIG. 4 were derived by proceeding in accordance with the following method:

1. Any interconnection consisting of two customer terminals connected to the same switch (input or output) are interconnected within the switch. In the above example, interconnections (I.sub.11,I.sub.13) and (O.sub.32,O.sub.34) fall into this category. These interconnections are depicted in FIG. 4 within switches v.sub.11 and v.sub.33, respectively.

2. Remaining interconnection pairs are partitioned into n/2 groups, subject to the condition that terminals associated with a particular switch of stage v.sub.1 or stage v.sub.3 appear within a group no more than twice. For example, I.sub.11, I.sub.12 and I.sub.14 relate to switch v.sub.11 and therefore only two of them are permitted to be included in any one group. Such partitioning is always possible since there are n input terminals associated with stage v.sub.1 switches and n output terminals associated with stage v.sub.3 switches. A mathematical analysis proving that such partitioning is always possible is presented by J. Peterson in "Die Theorie Der Regularen Graphen," Acta. Math. 15 (1891), 193-220.

In the above example, n=4 and the two groups arbitrarily chosen are:

3. each group is partitioned into three subgroups such that no switch is repeated within a subgroup. This is always possible because each switch appears at most twice in each group. In the above example, the subgroups chosen are

and

4. Each subgroup G.sub.i1 assignment is implemented with switch v.sub.2,2i.sub.-1, subgroup G.sub.i2 assignment is implemented with switch v.sub.2,2i and subgroup G.sub.i3 assignment is implemented with switch .mu..sub.i. In the above example, groups G.sub.11, G.sub.12, G.sub.13, G.sub.21, and G.sub.22 are implemented with switches v.sub.21, v.sub.22, .mu..sub.i, v.sub.23, and v.sub.24, respectively. Switch .mu..sub.2 is not employed because subgroup G.sub.23 is empty.

A perusal of FIG. 4 reveals that switch v.sub.23 is employed by all four stage v.sub.3 switches. It appears, therefore, that no additional interconnections to output terminals can be made in group G.sub.2 since they would necessarily involve the output links of switch v.sub.23. That is not a calamity beacause an additional connection involving output terminals, such as (O.sub.24,O.sub.33), need not be placed in group G.sub.2. In the above example, the additional interconnection above may be placed in group G.sub.1, subgroup G.sub.12, and may be implemented with switch v.sub.22 as depicted in FIG. 4. Alternatively, this interconnection could be placed in subgroup G.sub.13 and implemented with switch .mu..sub.1.

It should be noted that the embodiments illustrated and described herein are merely illustrative of the principles of this invention and should not be construed as fully depicting my invention. Particularly, it should be realized that the various simplifications introduced into the description were so introduced only to simplify the drawing and to make the discussion more concise. For example, the circuit of FIG. 2 can be implemented with any number of input and output terminals and with any number of stages. Also, any input-mixed one-sided or two-sided switch can be decomposed into a three stage network composed of smaller switches.