Nonblocking switching system and method
BACKGROUND OF THE INVENTION 
     The present invention relates to switching systems for communications systems, and in particular to an improved switching system which includes a pair of three-stage connecting networks and a method of operating the same. 
     Many communications systems, particularly telephone systems, contain a connecting network. A connecting network is an arrangement of switches and transmission links through which terminals connected to sources and terminals connected to destinatinos may be connected together in many combinations. 
     Calls in progress in a connecting network do not arise in a selected order or time sequence. Requests for connections (new calls) and terminations of connections (hangups) occur more or less at random, and the performance of a network when subjected to random traffic is measured by the fraction of requested connections that cannot be completed, or by the probability of blocking. 
     The performance of a connecting network for a given level of traffic is determined largely by its structure, i.e., by what terminals have a switch placed between them and can be connected together by closing the switch. The structure of a network determines what combinations of terminals can be connected together simultaneously, and if the structure is too simple, only a relatively few calls can be in progress at the same time. If the structure is extensive and complex, it may accommodate a large number of simultaneous calls in progress, but the network may be expensive to build and difficult to control. 
     Connecting networks made of square switches have long been used in telephone central offices. In a network made of square switches, each switch has the same number of inlets as outlets. The network is said to be arranged in stages if the switches are partitioned into sets called stages, two of which respectively carry the inlets to and outlest from the network, while the other are internal stages between the two, with the arrangement being such that every path from an inlet to an outlet passes through each stage only once. If the network is full access, each switch in a given stage has a link to every switch in the adjacent stages. 
     A network is in a blocking state if there are an idle inlet to and outlet from the network, but no available path exists through the network to connect the inlet and outlet. A routing algorithm may be used for choosing routes through the network for unblocked calls during its operation, or in the alternative to reestablish paths through the network in a manner to prevent the network from going to a blocking state. Such a network is said to be nonblocking in the wide sense if it is capable of blocking, but there is an algorithm for assigning routes to incoming calls that precludes any blocking, such that if the rule is applied, no blocking state is accessible. The system can then satisfy demands for connections as they arise without rejecting any or rerouting existing calls. However, networks controlled by such algorithms and the algorithms themselves are often complex. 
     A connecting network may also be nonblocking in the strict sense, if no matter what state the network may be in, it is always possible to connect together an idle pair of terminals without disturbing calls already in progress. In most new telephone switching systems, nonblocking in the strict sense is achieved by an N 2  type of network. An example of this would be a 2000 port network which requires 4 million switch elements to ensure nonblocking, but such networks are quite complex and extensive and add considerable cost to the system. 
     OBJECTS OF THE INVENTION 
     An object of the present invention is to provide an improved switching system which is reduced in complexity and cost, but in which blocking states may easily be avoided. 
     Another object is to provide such a switching system, which comprises two connecting networks for reliability through redundancy, but by virtue of which redundancy the networks may conveniently be made nonblocking should a blocking state occur. 
     A further object is to provide a method of operating such a switching system. 
     SUMMARY OF THE INVENTION 
     In accordance with the present invention, there is provided a switching system for connecting individual ones of a plurality of sources to individual ones of a plurality of destinations in various combinations. The system comprises a pair of connecting networks that are nonblocking in the wide sense, each for being connected in series between all of the sources and all of the destinations. Also included are means for controlling the networks to establish and interrupt paths therethrough between individual ones of the sources and destinations, along with selector means for connecting one or the other of the networks in series between the sources and destinations, such that the network connected in series is active to establish connections between the sources and destinations, while the other network is inactive. The arrangement is such that the means for controlling, upon occurrence of a blocking state in the active network before its maximum capacity is reached and the network is full, includes means for emptying the inactive network of all paths therethrough and then establishing paths through the network which will connect the sources and destinations in the manner attempted when the active network went to a blocking state--without occurrence of a blocking state in the inactive network. After the paths are established through the inactive network, the selector means is operative to connect the inactive network in series between the sources and destinations and to disconnect the active network from in series, whereby the roles of the networks are reversed and the previously inactive network becomes active while the previously active network becomes inactive. 
     The invention also contemplates a method of connecting individual ones of a plurality of sources to individual ones of a plurality of destinations in various combinations. The method comprises the steps of coupling all of the sources to inlets to each of first and second connecting networks that are nonblocking in the wide sense, coupling all of the destinations to outlets from each of the networks, and connecting the first network only in series between the sources and destinations. Paths are then established and interrupted through the first network to connect and disconnect individual ones of the sources and destinations. Upon occurrence of a blocking state in the first network before it has reached its maximum capacity and is full, paths are established through the second network which will connect the sources and destinations in the manner attempted when the blocking state occurred in the first network--without causing a blocking state to occur in the second network. The second network is then connected in series between the sources and destinations and the first network is disconnected from in series, whereby the second network then connects the sources and destinations. 
     The foregoing and other objects, advantages and features of the invention will become apparent upon a consideration of the following detailed description, when taken in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a known type of digital switching system, illustrating basic components of the system, which include a digital connecting network; 
     FIG. 2 is a simplified block diagram of a digital switching system according to the teachings of the present invention; 
     FIG. 3 is a block diagram of a 4×4 connecting network of a type which may represent each network of FIG. 2; and 
     FIG. 4 is similar to FIG. 3, except that it illustrates a n×n connecting network. 
    
    
     DETAILED DESCRIPTION 
     The Prior Art 
     FIG. 1 shows in block diagram form a typical prior art digital switching system including a line and trunk interface, a digital connecting network and a central control. The line and trunk interface connects the system to the outside world, e.g., to service circuits, digital trunks, analog trunks and subscriber lines. Where the signals from the outside world are analog, the interface converts them to digital. 
     The digital connecting network is an arrangement of switches and transmission links through which terminals connected to sources of signals may be selectively coupled in many combinations to terminals connected to destinations, the basic function of the digital connecting network being to perform the necessary switching to establish the paths for the connections. The central control in turn provides stored program control for both the system and a man/machine interface (not shown). 
     Calls in progress in a digital connecting network do not usually arise in a predetermined order or time sequence. Requests for connections (new calls) and terminations of connections (hangups) occur more or less at random, and unless the network is nonblocking in the strict sense, or nonblocking in the wide sense, it can happen that the it is not able to establish a connection between a calling source and a selected destination. When that occurs, the network is said to be in a blocking state, i.e., there is an idle inlet to and an idle outlet from the network, but there is no available path through the network to connect the inlet to the outlet. 
     To avoid a blocking condition, most new telephone switching systems use connecting networks that are nonblocking in the strict sense. However, a strictly nonblocking network is often extensive and complex since nonblocking is normally achieved by an N 2  type of network, such that a 2000 port network requires 4 million switch elements to ensure nonblocking. 
     The Invention 
     To mitigate cost and complexity disadvantages of conventional switching systems having connecting networks that are nonblocking in the strict sense or nonblocking in the wide sense, as seen in FIG. 2 the invention provides an improved switching system which includes a pair of identical connecting networks 0 and 1, each of which is nonblocking in the wide sense. Every source is connected through each network to every destination, and although only a single source and destination are illustrated for simplicity, it is understood that in actual use, the networks would be connected between pluralities of sources and destinations. 
     At any given time, only one network actively establishes paths from sources to destinations as determined by and through a conventional 1 of 2 selector circuit. The other network is inactive at the time and in a standby mode, although the same paths established through the active network also exist in the inactive network. This type of redundant configuration of networks increases the reliability of the switching system, such that if the active network fails, the other one will be prepared to maintain the paths and assume switching functions. However, according to the invention, the redundant configuration also is used to establish an easily implementable nonblocking environment. 
     The connecting networks 0 and 1 are n×n three stage networks which are responsive to a central control having a man/machine interface (not shown). Connections are added and dropped in a random manner, so blocking can occur. When a blocking state occurs in the active network before it has reached its maximum capacity and is full, instead of using a complicated algorithm to rearrange existing connections in the active network, according to the invention a nonblocking condition of the system is easily reached by: (1) eliminating all of the paths in the inactive network, so that the network is empty: (2) reestablishing paths in the inactive network, according to a relatively simple algorithm, that will connect the sources to the destinations in the manner attempted when the active network reached a blocking state, without a blocking state occurring in the inactive network until the network is full; (3) switching or reversing the roles of the active and inactive networks, so that the previously inactive network becomes active and establishes the paths from the sources to the destinations through the 1 of 2 selector circuit, and the previously active network becomes inactive; and then (4) copying the paths established in the newly active network into the newly inactive network, so that the inactive network will be prepared to connect the sources to the destinations and assume switching functions should the active network fail. 
     To demonstrate that paths may be established through an initially empty n×n three stage network, such that no blocking state occurs until the maximum realizable capacity of the network is reached and the network is full, consider the 4×4 three stage network shown in FIG. 3, which may represent each of the networks 0 and 1. The network is comprised of square switches, each having the same number of inlets as outlets. For a 4×4 network, each stage has 4 switches and each switch has 4 inlets and 4 outlets, so inputs Y 0  -Y 3  each represent four lines from respective sources to associated input terminals of source switches S 0  -S 3 , and outputs X 0  -X 3  each represent four lines to respective destinations from associated output terminals of destination switches D 0  -D 3 . The network is full access, so each switch in a given stage has a transmission link to every switch in adjacent stages, although for simplicity of illustration only links between the source switch S 0  and intermediate stage switches I 0  -I 3 , as well as between the destination switch D 0  and the intermediate stage switches, have been shown. 
     Starting with an initially empty network, i.e., whichever network 0 or 1 was inactive and emptied of paths when the other became blocking, to connect the sources and destinations through the inactive network in the manner attempted when the active network reached a blocking state, such that the inactive network does not become blocking until it is completely full, a connection from S k  to D j  is established by choosing an intermediate stage I i , through which the connection is to pass, according to the following algorithm: 
     Choose the path (D j , I 0 ), (D j , I 1 ), (D j , I 2 ) or (D j , I 3 ) that has the minimum number of existing connections on that particular link. 
     After the path is chosen and established, the path (I j , S k ) is established to complete the connection from S k  to D j . 
     The above path choosing and establishing sequence is then repeated until all of the desired connections that are to exist between sources and destinations have been established. The 1 of 2 selector circuit is then operated to reverse the roles of the active and inactive networks, such that the previously inactive network, with the newly established paths therein, becomes active and connects the sources to the destinations, and the previously active network becomes inactive. The paths in the newly active network are then copied into the newly inactive network, so that it will be prepared to assume connection and switching functions should the active network fail. 
     To appreciate that connections may be added to the emptied inactive network, so that no blocking occurs until the network is full, considering the following: 
     Note 1: The capacity of link (D j , I i ) is not exceeded since each link has a maximum capacity of X max  /4 and X j  /4≦X max  /4, where X j  is the traffic leaving D j  and X max  is the maximum traffic capacity of D j . 
     Note 2: Since X 0  ≦X max , . . . , X 3  ≦X max , the maximum traffic through the center stage I i  is X 0  /4+X 1  /4+X 2  /4+X 3  /4≦1/4(4X max )=X max . Therefore, the maximum capacity of the center stage is not exceeded. 
     Note 3: Let t j ,k =(the number of connections from D j  to S k ) /X max , or the portion of X j  that is connected to S k , and 0≦t j ,k ≦1. Then, the maximum traffic over link (I i , S k )=1/4X 0  t 0k  +1/4X 1  t 1k  +1/4X 2  t 2k  +1/4X 3  t 3k  ≦1/4X max  (t 0k  +t 1k  +t 2k  +t 3k ). However, for a full network X max  (t 0k  +t 1k  +t 2k  +t 3k )=X max , since the maximum traffic entering S k  from the left side of the network is also Y max  =X max . Therefore, for a full network (t 0k  +t 1k  +t 2k  +t 3k )=1, although in general, and to include the situation where the network is less than full, (t 0k  +t 1k  +t 2k  +t 3k )≦1. 
     Thus, the maximum traffic on link (I i , S k )≦1/4(X max ). This satisfies the maximum link requirements of link (I i , S k ). 
     As seen from note 1, the (D j , I j ) intermediate link capacity is not exceeded; according to note 2, the center stage capacity is not exceeded; and from note 3 it is seen that the (I i , S k ) link capacity is not exceeded. The network therefore remains nonblocking when connections are sequentially added to the initially empty network according to the above algorithm. 
     The proof that paths may be established through an initially empty three stage network, such that the network remains nonblocking until it is full, may be extended to any n×n network. 
     Consider the full access n×n network in FIG. 4, which may represent each of the networks 0 and 1. Starting with the network initially empty, to establish a connection from S k  to D j , choose an intermediate stage I i , through which the connection is to pass, according to the following algorithm: 
     Choose the path [(D j , I 0 ), (D j , I 1 ), . . . , or (D j , I n-1 )] that has the minimum number of existing connections on that particular link. 
     After the path is chosen and established, the path (I i , S k ) is established to complete the connection from S k  to D j . 
     The above path choosing and establishing sequence is then repeated until all of the desired connections that are to exist between sources and destinations have been established. The 1 of 2 selector circuit is then operated to reverse the roles of the active and inactive networks, such that the previously inactive network, with the newly established paths therein, becomes active and connects the sources to the destinations, and the previously active netowrk becomes inactive. The paths in the newly active network are then copied into the newly inactive network, so that it will be prepared to assume connection and switching functions should the active network fail. 
     To appreciate that connections may be added to the network, so that no blocking occurs until the network is full, consider the following: 
     Note 1: The capacity of link (D j , I i ) is not exceeded since each link has a maximum capacity of X max  /n and X j  /n≦X max  /n, where X j  is the traffic leaving D j  and X max  is the maximum traffic capacity of D j . 
     Note 2: Since X 0  ≦X max , . . . , X n-1  ≦X max , the maximum traffic through the center stage I i  is X 0  /n+X 1  /n+ . . . +X n-1  /n≦1/n(nX max )=X max . Therefore, the maximum capacity of the center stage is not exceeded. 
     Note 3: Let t j ,k =(the number of connections from D j  to stage S k )/X max , or the portion of X j  that is connected to S k , and 0≦t j ,k ≦1. Then, the maximum traffic over link (I i , S k )=1/n X 0  t 0 ,k + . . . +1/n X j  t j ,k + . . . +1/n X n-1  t n-1  ≦1/n X max  (t 0 ,k + . . . +t j ,k + . . . +t n-1 ,k). However, for a full network X max  (t 0 ,k + . . . +t j ,k + . . . +t n-1 ,k)=X max , since the maximum traffic entering S k  from the left side of the network is also Y max  =X max . Therefore, for a full network (t 0 ,k + . . . +t j ,k + . . . t n-1 ,k)=1, although in general, and to include the situation where the network is less than full, (t 0 ,k + . . . +t j ,k + . . . +t n-1 ,k)≦1. 
     Again, the maximum traffic on link (I i , S k )≦1/n(X max ). This satisfies the maximum link requirements of link (I i , S k ). 
     The invention therefore contemplates a switching system having two identical, full access, n×n, three stage blocking networks. One network at a given time is active and connects the sources to the destinations, while the other is inactive and in a standby mode, but has in it the same paths as are in the active network, so that should the active network fail, the inactive one will be ready to assume connections and switching functions. The redundancy provides increased reliability in the event of failure of one of the networks. 
     The redundancy also enables the switching system to be maintained in a nonblocking mode. Although the networks may reach a blocking state, should that occur it may readily be resolved. In particular, upon occurrence of a blocking state in the active network, the inactive network is simply cleared of the paths therein, and new paths are established that will connect the sources and destinations in the manner attempted when the active network became blocking, without a blocking state occurring in the inactive network until it is fully loaded. The roles of the active and inactive networks are then reversed. 
     By virtue of the arrangement, it is not necessary to interrupt and rearrange connections through the active network should it reach a blocking state, so there is no interruption of communications services. In addition, the particular algorithm for establishing the transmission paths through the inactive network is relatively simple compared with prior algorithms used to establish and rearrange paths through networks that are noblocking in the wide sense. In essence, after emptying the inactive network, paths are reestablished through its center stage, beginning with I 0  and sequentially cycling from I 0  to I n-1 , to make the connections between the center stage switches and the various output stage switches D 0  to D n-1 . After each path between a switch of the center stage and a switch of the output stage is established, one is then established between the particular center stage switch and a selected switch of the input stage, such that a connection from S k  to D j  is completed. The rule for making the connections from S k  to D j  ensures that the network may be completely loaded to its maximum capacity before it reaches a blocking state. 
     While embodiments of the invention have been described in detail, various modifications and other embodiments thereof may be devised by one skilled in the art without departing from the spirit and scope of the invention, as defined in the appended claims.