Traffic spreading to reduce blocking in a groomed CLOS...

Details Traffic spreading to reduce blocking in a groomed CLOS... Traffic spreading to reduce blocking in a groomed CLOS...

2001-08-01

2004-06-22

Holloway, III, Edwin C. (Department: 2635)

Multiplex communications

Pathfinding or routing

Through a circuit switch

C370S386000, C370S369000, C340S002600

Reexamination Certificate

active

06754208

ABSTRACT:

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT N/A
BACKGROUND OF THE INVENTION
CLOS networks, which are 3-stage unidirectional switching networks, are well known in the art. As depicted in
FIG. 1
, a typical CLOS network
100
includes a source stage
102
that includes a plurality of R source modules
102
-
1
to
102
-R, wherein each source switching module is a N×M switch, which may be a crossbar switch. The M output ports of the R source modules are connected to the input ports of a midstage switching stage
104
. The midstage switching stage
104
includes M midstage switching modules
104
-
1
to
104
-M each having R input ports, wherein each of the midstage switching modules
104
is an R×R switch, which may be a crossbar switch. The R output ports of the midstage switching modules are connected to the input ports of a destination stage
106
. The destination stage
106
includes R destination modules,
106
-
1
to
106
-R wherein each of the R destination modules is an M×N switch, which may be a crossbar switch. Thus, for each of the R source modules
102
there is exactly one connection, i.e., one unit of edge capacity, between the source module and any midstage switching module. Similarly, there is exactly one connection, i.e., one unit of edge capacity, between each of the M midstage switching modules and each of the R destination modules.
As used herein an input circuit is an input signal having one or more component signals. An input circuit typically is applied or allocated to an input port on one of the source switching modules. A unicast input circuit is an input circuit that has a single source port and a single destination port. A dualcast input circuit is an input circuit that has a single source port and two destination ports on one or more destination switching modules, and a multicast input circuit is an input circuit that has a single source port and more than two destination ports on one or more switching modules.
A 3-stage CLOS network is strict sense non-blocking when carrying unicast circuits when there is no need to re-route any existing circuits to allow the switching of a new input circuit from the desired source module to the desired destination module. A sufficient condition for strict sense non-blocking of unicast input circuits is that the number of output ports per source switching module and therefore the number of midstage switching modules M is greater than or equal to 2 times the number of input ports per source module minus 1, or M≧2*N−1.
A 3-stage CLOS network is considered reconfigurably non-blocking when carrying unicast circuits when to accommodate a new input circuit, existing circuits may have to be re-routed within the CLOS network. A sufficient condition for unicast reconfigurably non-blocking is that the number of midstage switching modules is greater than or equal to the number of input ports on a source module, or M≧N.
A 3-stage CLOS network is strict sense non-blocking when carrying dualcast circuits when there is no need to re-route any existing circuits to allow the switching of a new input circuit from the desired source module to the desired destination modules. A sufficient condition for dualcast strict sense non-blocking is that the number of output ports per source switching module, and therefore the number of midstage switching modules, M is greater than or equal to 3 times the number of input ports per source module minus 2, or M≧3*N−2.
A 3-stage CLOS network is considered reconfigurably non-blocking when carrying dualcast circuits when to accommodate a new input circuit an existing circuit may have to be re-routed within the CLOS network. A sufficient condition for dualcast reconfigurably non-blocking is that the number of midstage switching modules is greater than or equal to twice the number of input ports on a source module, or M≧2N. A necessary condition for dualcast reconfigurably nonblocking is that the number of midstage switching modules is greater than or equal to four-thirds times the number of input ports on a source module, or M≧4N/3.
Typically, CLOS networks may have several hundred input ports distributed among tens or hundreds of source modules. To provide a suitable quality of connectivity the CLOS network should be configured to be at least reconfigurably nonblocking. However, as the size of the CLOS network grows, reconfiguring the CLOS network involves coordinating switchovers in all three switching stages. This recoordination is time consuming and may lead to traffic disruptions resulting in loss of data. For example re-routing an existing circuit may result in traffic disruptions that are greater than 50 ms. Therefore, creating a system that is reconfigurably nonblocking is not an efficient network architecture and can be disruptive to the traffic carried thereon. As discussed above, to ensure strict sense non-blocking for large CLOS networks, the required number of midstage switching modules must increase at twice to three times the rate as the number of input ports. This can lead to large, expensive, and complex switching systems.
Therefore it would be desirable to provide a 3-stage CLOS network that is not as large and complex as a strict sense non-blocking network, does not require reconfiguration as a reconfigurable non-blocking network, but provides a suitably low blocking probability of a circuit.
BRIEF SUMMARY OF THE INVENTION
A method and apparatus are disclosed for spreading an input circuit through a three-stage CLOS network such that the CLOS network has an extremely small blocking probability. In one embodiment, a method is provided that includes receiving an incoming input circuit that includes a plurality of component signals and also has associated therewith a source and destination identifier. Each component signal has further associated therewith a bandwidth requirement. The input circuit is allocated to one of a plurality of source switching modules that corresponds to the source identifier associated with the input circuit. At least two of the component signals are to be spread over the various midstage switching modules. As such, an ordered list is made that includes each of the midstage switching modules, and each midstage switching module is evaluated in order to identify a first midstage switching module that has a first connection to the source switching module corresponding to the source identifier, and a second connection to the destination switching module corresponding to the destination identifier. If both the first and second connections have sufficient spare bandwidth to accommodate the bandwidth of the first component signal, the first component signal is routed through the first midstage switching module. The search for a second midstage switching module to route the second component signal through begins with the next midstage switching module in the ordered list. Each midstage switching module is again evaluated to identify a second midstage switching module that has a first connection to the source switching module corresponding to the source identifier, and a second connection to the destination switching module corresponding to the destination identifier. If both the first and second connections have sufficient spare bandwidth to accommodate the bandwidth of the second component signal, the second component signal is routed through the second midstage switching module.
In one embodiment, if the search for a second midstage switching module has reached the last midstage switching module in the ordered list and not all of the midstage switching modules have been evaluated, the search for a second midstage switching module continues from the first midstage switching module of the ordered list and will continue up to and including the first midstage switching module.
An input circuit that is be a multicast circuit includes two or more identified destinations for a single identified source. A dualcast circuit is a multicast circuit having two identified destinations for a single identified source.

Affiliated with

Also associated with

Rating

Traffic spreading to reduce blocking in a groomed CLOS... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Traffic spreading to reduce blocking in a groomed CLOS..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Traffic spreading to reduce blocking in a groomed CLOS... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3309021