Folded Clos architecture switching

Details Folded Clos architecture switching Folded Clos architecture switching

2000-09-21

2004-02-24

Horabik, Michael (Department: 2635)

Communications: electrical

Selective

Path selection

C340S014200, C340S002210, C340S002280, C340S002250

Reexamination Certificate

active

06696917

ABSTRACT:

FIELD OF THE INVENTION
This invention pertains to non-blocking switching networks, and more particularly, to Clos switch architectures.
BACKGROUND OF THE INVENTION
Modern high-capacity communication channels have alleviated a number of communication bottlenecks, namely limitations in data transfer rate and channel bandwidth. However, the recent increase in channel bandwidth has also given rise to the need for switching networks capable of maintaining not only high data rates, but also large numbers of separate I/O channels.
Historically, the driving force behind the development of switching networks has been the need to provide a non-blocking telephone switching architecture capable of connecting any pair of user terminals under arbitrary traffic conditions. Early on, it was recognized that a crossbar switch with n input terminals, n output terminals and n
2
crosspoints as shown in
FIG. 1
is capable of providing the required non-blocking performance, only at a prohibitive cost in large systems. For a square crossbar switch, the number of crosspoints grows by n
2
, making the crossbar switch too complex to implement for a large number of inputs.
In a seminal paper entitled “A Study of Non-blocking Switching Networks,” Bell Syst. Tech. J., vol. 32, 3/53, pp. 406-424, published in 1953, Charles Clos proposed a scheme to partition the large crossbar into a number of stages, thus reducing the complexity of the network by decreasing the number of crosspoints.
FIG. 2
shows a square three-stage Clos switch architecture. The first (input) stage includes N
crossbar switches, each having n inlets and k outlets. The second (center) stage consists of k crossbar switches of size (N
)×(N
). Similar to the first stage, the third (output) stage also consists of N
crossbar switches. However, each individual crossbar switch of the third stage has k inlets and n outlets.
According to Clos' space-division technique, there are k possible paths for an inlet to reach an outlet. The worst case scenario occurs when for a given inlet and outlet, (n−1) inlets of the first stage are used by other sources, and (n−1) other sources use (n−1) outlets of the third stage. As a result, a minimum of (n−1)+(n−1)+1 routes must be available between the inlet and the outlet. The three stage switch is therefore non-blocking if k≦(n−1)+(n−1)+1, or simply k≦(2n−1).
In contrast to the crossbar switch of
FIG. 1
, the three stage Clos switch configuration has nk(N
) crosspoints for each first and last stages, and k(N
)
2
crosspoints for the middle stage, for a total of S=2kN+k(N
)
2
[Equation S] crosspoints. The optimum number of crosspoints can be obtained by substituting the total number of crosspoints into equation S and differentiating with respect to n then equating to zero. For large values of N, the optimum value of crosspoints is n
opt
≈(N/2)½, a definite improvement over the single stage crossbar matrix. Nonetheless, the use of generic square crossbar switches to build a multistage switch results in waste of I/O ports at the input and output stages of the Clos switch. Although rectangular (asymmetrical) crossbar switches can be used in each switching stage of a multistage crossbar switch to reduce the number of idle I/O ports, rectangular crossbar switches are application-specific and unlike their generic square counterparts, cannot be readily used in a wide variety of applications.
Switch complexity can be somewhat ameliorated by rearranging an existing connection through a different set of switching interconnections by means of control systems. However, rearrangeable switching networks require data synchronization and employ complex control systems for managing and rerouting large numbers of existing connections. This need for synchronizing the incoming data often requires an additional processing layer at the input and output stages. Furthermore, even though a rearrangeable switch may provide non-blocking behavior, a connection may still suffer from unacceptable performance in terms of delay and data loss if the wrong path is chosen by the control system.
There is therefore a need for a non-blocking switching network that fully utilizes the input and output terminals at various stages of the switching architecture. Preferably, such a system can be implemented using off-the-shelf square crossbar switches having a fixed number of I/O terminals, such that the need for using custom-made rectangular crossbars is avoided.
SUMMARY OF THE INVENTION
The above problems and other similar shortcomings of the existing systems are solved by partitioning a crossbar switch to provide both the first (yth) and last (x−y+1th) stage of a multistage Clos switch architecture where x is the total number of stages in the general case. By aggregating each input stage having n inlets and its corresponding output stage also having n outlets into a single device, a non-blocking crossbar building block of (3n−1)×(3n−1) dimensions is obtained, thereby reducing the number of unused I/O terminals or the need for asymmetrical custom-made switching devices. In the general case of an output stage having a different number of outlets m than the first stage number of inlets n, we encounter the following two cases, as the dilation of the middle stages becomes a function of the greater of n and m:
a) if n≧m, then the non-blocking crossbar building block is of size (3n−1)×(2n+m−1);
b) if n<m, then the non-blocking crossbar building block is of size (2m+n−1)×(3m−1).
This invention arises from the realization that the use of conventional square crossbar devices to build multistage Clos switches results in waste of input and output terminals on all stages except the middle stage, making the cost penalties for implementing large switching systems prohibitive. The architectural complexity and loss of I/O terminals can be obviated by means of a novel method for combining the input and output stages of thp Clos switch network into a single device, thus allowing for an advantageous grouping of functional elements of the Clos switch architecture that minimizes the number of inactive inputs and outputs without loss of non-blocking behavior. The invention departs from a mere replacement of prior art elements with larger size switching devices, and instead focuses on grouping of the input and output stages of a Clos switching architecture into a single device in order to significantly reduce size, complexity and cost of integrated switching networks. Additionally, another benefit of aggregating the first and last stages in the same device is that loopbacks come in for free, be it directly form the switch to I/O port side or from the middle stages.


REFERENCES:
patent: 4821034 (1989-04-01), Anderson et al.
patent: 6335992 (2002-01-01), Bala et al.
F.K. Hwang, “Three-Stage Multiconnection Networks Which Are Nonblocking in the Wide Sense”, The Bell System Technical Journal, pp 2183-2187, 1979.
Riccardo Melen et al., “Nonblocking Networks for Fast Packet Switching”, IEEE, pp. 548-557, 1989.
Charles Clos, “A Study of Non-Blocking Switching Netoworks”, The Bell System Technical Journal, pp. 406-414.

Affiliated with

Also associated with

Rating

Folded Clos architecture switching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Folded Clos architecture switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Folded Clos architecture switching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3309524