Method and apparatus for performing group switching in dense wavelength division multiplexing optical networks

BACKGROUND OF THE INVENTION

Technical Field of the Invention

0001The present invention generally relates to Wavelength Division Multiplexing ("DWDM") optical networks. More particularly, and not by way of any limitation, the present invention is directed to group switching method and apparatus for such networks.

Description of Related Art

0002The laying of new fiber was once the only way to cope with fiber exhaust in optical telecommunications networks. In addition to being labor- and cost-intensive, this "solution" did not enable network operators to provide additional services to customers. In the early 1980s, time-domain multiplexing ("TDM") technology enabled an increase in the bit rate of optical telecommunications networks. With TDM, the capacity of a single fiber was increased by dividing time into small intervals and multiplexing the various signals onto these separate time intervals.

0003In TDM systems, each optical fiber is capable of transporting an optical signal from a single laser. The optical signal is converted into an electrical signal, electrically reshaped, retimed, and reamplified ("3R regenerated"), and finally transformed back into an optical signal, resulting in additional losses. Wavelength-division multiplexing ("WDM") networks, which enabled the simultaneous transmission of multiple signals of different wavelengths over a single fiber, were deployed in the late 1980s and proved in many cases to be a preferable alternative to TDM.

0004During the 1990s, WDM networks were developed that enabled up to four different signals to be transmitted over one fiber at different wavelengths within the same optical window. For obvious reasons, such networks necessitate the use of narrow lasers.

0005In order to increase the number of services that can be provided, the channel spaces can be moved closer together, creating Dense WDM ("DWDM"). This technology economically increases transport capacity through the utilization of existing fiber routes and terminal equipment.

0006A DWDM system can be described as a parallel set of optical channels each using a slightly different wavelength, but all sharing a single transmission medium or fiber. In a typical embodiment, various signals are fed to optical transmission modules. The optical output signals are converted to defined wavelengths within a 1550 nanometer ("nm") window via wavelength transponders. An optical DWDM coupler then multiplexes these optical signals onto a single fiber and forwards them to an optical fiber amplifier ("OFA").

0007Every router in a DWDM network must provide a switching function between <i>N</i> inputs thereto and <i>N</i> outputs therefrom such that simultaneous one-to-one connections between <i>the N</i> inputs and any one of the <i>N</i> outputs. Note that a group connector is able to distinguish among groups of outputs. Clearly, an <i>N</i> x <i>N</i> permutation network, such as a Benes or Clos network, can be used to provide the switching function; however, such permutation networks can be costly in terms of hardware.

SUMMARY OF THE INVENTION

0008One embodiment is an <i>N</i>x<i>N</i> three-stage group connector with <i>N</i> inputs and <i>N</i> outputs, wherein the <i>N</i> outputs are divided into r output groups, each group including <i>n</i> outputs such that <i>r = N</i>/<i>n</i>. The group connector comprises a first stage comprising <i>r nxm</i> crossbar switch modules, wherein <i>m</i> ≥ n-1; a second stage comprising <i>m rxr</i> crossbar switch modules; and a third stage comprising <i>r MxN</i> concentrator switch modules.

0009Another embodiment is a method of constructing an <i>N</i>_<i>1</i>x<i>N</i>_<i>2</i> multistage group connector with <i>N</i>_<i>1</i> inputs and <i>N</i>_<i>2</i> outputs from a three-stage group connector, wherein the three-stage group connector comprises a first stage comprising <i>r nxm</i> crossbar switch modules, a second stage comprising <i>m rxr</i> crossbar switch modules, and a third stage comprising <i>r mxn</i> concentrator switch modules. The method comprises replacing each of the <i>r rxm</i> crossbar switch modules of the first stage with a three-stage group connector of the same size as the <i>rxm</i> crossbar switch module; and replacing each of the <i>m r</i>x<i>r</i> crossbar switch modules of the second stage with a three-stage group connector of the same size as the <i>r</i>x<i>r</i> crossbar switch module.

0010Another embodiment is an <i>N</i>x<i>N</i> multi-stage group connector with <i>N</i> inputs and <i>N</i> outputs, wherein the <i>N</i> outputs are divided into r output groups, each group including <i>n</i> outputs such that <i>r</i> = <i>N</i>/<i>n</i>. The group connector comprises a first portion comprising <i>r n</i>x<i>m</i> three-stage group connectors, wherein <i>m</i> ≥ n-1; a second portion comprising <i>m r</i>x<i>r</i> three-stage group connectors; and a third portion comprising <i>r p</i>x<i>q</i> fat and slim concentrator switch modules.

0011Another embodiment is an <i>N</i>x<i>N</i> two-stage group connector with <i>N</i> inputs and <i>N</i> outputs, wherein the <i>N</i> outputs are divided into r output groups, each group including <i>n</i> outputs such that <i>r</i> = <i>N</i>/<i>n</i>. The group connector comprises a first stage comprising <i>r nxm</i> crossbar switch modules; and a second stage comprising <i>m r</i>x<i>r</i> crossbar switch modules, wherein <i>m</i> is equal to 2<i>n</i>-1.

0012Another embodiment is a method of constructing an <i>N</i> x <i>N</i> group connector of group size 2^<i>k</i> from an <i>N</i> x <i>N</i> Benes network. The method comprises setting all switches in stages 2<i>m</i>-2, 2<i>m</i>-3, ... 2<i>m</i>-(<i>k</i>+1) of the Benes network to straight connections; and removing all switches in stages 2<i>m</i>-2, 2<i>m</i>-3, ... 2<i>m</i>-(<i>k</i>+1) of the Benes network.

BRIEF DESCRIPTION OF THE DRAWINGS

0013A more complete understanding of the present invention may be had by reference to the following Detailed Description when taken in conjunction with the accompanying drawings wherein:

0014FIG. 1 is a schematic block diagram of an ingress edge router of one embodiment;

0015FIG. 2A illustrates an embodiment of an optimal concentrator comprising a <i>p</i> x <i>q</i> fat-and-slim concentrator;

0016FIG. 2B illustrates an embodiment of an optimal concentrator comprising a <i>p</i> x <i>q</i> banded concentrator;

0017FIG. 3 is a schematic block diagram of an <i>N</i> x <i>N</i> three-stage group connector <i>g</i>(<i>m,n,r</i>), where <i>N=nr;</i>

0018FIG. 4 illustrates an embodiment of a 9x4 fat-and-slim concentrator;

0019FIG. 5 is a schematic block diagram of a <i>N</i>_<i>1</i><i> x N</i>_<i>2</i> three-stage group connector <i>v</i>(<i>m,n</i>_<i>1</i><i>,r</i>_<i>1</i><i>,n</i>_<i>2</i><i>,r</i>_<i>2</i>);

0020FIG. 6 is schematic block diagram of an <i>n</i> x <i>n</i> two-stage rearrangeably non-blocking group connector, where <i>N=nr;</i>

0021FIG. 7A illustrates an embodiment of a 16 x 16 Benes network; and

0022FIG. 7B illustrates construction of a 16 x 16 group connector of group size four from the Benes network of FIG. 7A.

DETAILED DESCRIPTION OF THE DRAWINGS

0023In the drawings, like or similar elements are designated with identical reference numerals throughout the several views thereof, and the various elements depicted are not necessarily drawn to scale.

0024A new class of interconnection networks called group connectors is introduced. A group connector <i>G(N,n)</i> is a switching network that consists of <i>N</i> inputs and <i>N</i> outputs such that (1) its <i>N</i> outputs are divided into <i>N</i>/<i>n</i> groups with <i>n</i> outputs in each group; and (2) it can provide any simultaneous one-to-one connections from the <i>N</i> inputs to the <i>N</i> outputs, possibly without the ability of distinguishing the order of the outputs within each group. Note that a group connector is able to distinguish among groups of outputs. Group connectors have application in the switching matrices in dense wavelength division multiplexing ("DWDM") networks. Clearly, an <i>N</i> x <i>N</i> permutation network can be used as an <i>N</i> x <i>N</i> group connector; however, as will be demonstrated hereinbelow, a group connector <i>G</i>(<i>N,n</i>) can be built at a lower hardware cost than can a permutation network of the same size.

0025In general, a group connector <i>G(N,n)</i> captures the simultaneous connections between <i>N</i> clients and <i>N</i> servers, which are divided into <i>N</i>/<i>n</i> equal-size server groups such that the <i>n</i> servers in each group are functionally equivalent. Group connectors are particularly useful in DWDM networks. With DWDM, it is possible to transmit different wavelengths of light over the same fiber. This development has provided another dimension to increasing bandwidth capacity. Suppose that an optical fiber link connecting two nodes transmits data using <i>n</i> different wavelengths and an optical router has <i>N</i>/<i>n</i> output links. Each wavelength on a link is called a channel. Then the channels on a link can be considered functionally equivalent and which wavelength to use for transmission along a link may only depend on the availability of these channels. A group connector can be used as a switching network in a DWDM router. For example, if some inputs and one or more groups of outputs are connected to a local node, a group connector can be used as an add/drop crossconnect switching matrix.

0026Group connectors also have application in the construction of ingress edge routers of DWDM networks. FIG. 1 is a block diagram of an ingress edge router 100 for a DWDM optical network. The ingress edge router 100 includes a set of <i>N</i> electrical or optical input links 102(1)-102(<i>N</i>) and a set of <i>N</i>/<i>n</i> optical output links 104(1)-104(<i>N</i>/<i>n</i>). Each optical output link 104(1)-104(<i>N</i>/<i>n</i>) includes of a set of <i>n</i> data channels <i>Ch</i>_<i>i,1</i><i>,</i> ... <i>Ch</i>_<i>i,n</i>, each using a different wavelength. Associated with each input link 102(1)-102(<i>N</i>) is a respective input line card ("ILC") 106(1)-106(<i>N</i>). Similarly, associated with each output link 104(1)-104(<i>N</i>/<i>n</i>) is a respective output line card ("OLC") 108(1)-108(<i>N</i>/<i>n</i>). A switching matrix 110 is disposed between the set of ILCs 106(1)-106(<i>N</i>) and the set of OLCs 108(1)-108(<i>N</i>/<i>n</i>). The switching matrix 110 is individually connected to each of the OLCs 108(1)-108(<i>N</i>/<i>n</i>) by connections 112(1)-112(<i>n</i>).

0027The main function of each ILC 106 is to route each input packet to the appropriate OLC 108 via routing table lookup. Each OLC 108 transmits the packets it receives using the <i>n</i> optical channels of the link 104(1)-104(<i>N</i>/<i>n</i>) it controls. As will be described in greater detail below, a group connector can be used as the switching matrix (such as the switching matrix 110) in the design of an ingress edge router (such as the ingress edge router 100) of a burst-switched DWDM network.

NON-BLOCKING GROUP CONNECTORS

0028A group connector <i>G(N,n)</i> is "non-blocking" if any of its <i>n</i> inputs can be connected to a group at its output in a non-blocking fashion such that no rearrangement is required to the existing connections to the other groups in the network.

Non-Blocking Three-Stage Group Connectors

0029Group connector designs can utilize "concentrators" to reduce network cost. A <i>p</i>x<i>q</i> (<i>p ≤ q</i>) concentrator under consideration is a single stage sparse crossbar switching device that can connect any <i>q</i> of its <i>p</i> inputs to its <i>q</i> outputs, possibly without the ability of distinguishing their order. Significant research has been performed with respect to designing efficient sparse crossbar concentrators. This research has shown that there is a lower bound on the number of crosspoints such a concentrator must have. In particular, it has been established that every <i>p</i>x<i>q</i> sparse crossbar concentrator must contain at least (<i>p</i>-<i>q</i>+1)x<i>q</i> crosspoints.

0030More recently, sparse crossbar concentrators that use (<i>p</i>-<i>q</i>+1)x<i>q</i> crosspoints have been designed. Two 9x4 concentrators with a minimum number of crosspoints are illustrated in FIGs. 2A and 2B, respectively, and respectively designated by reference numbers 200 and 202. The concentrator 200 is referred to as a "fat-and-slim concentrator". The concentrator 202 is referred to as a "banded concentrator". Each of the concentrators 200, 202, includes 24 crosspoints, as represented in FIGs. 2A and 2B by crosspoints 204.

0031For purposes of example herein, the fat-and-slim concentrator 200 illustrated in FIG. 2A will be used. In general, to construct a <i>p</i>x<i>q</i> fat-and-slim concentrator, its input set <i>I</i> (|<i>I</i>| = <i>p</i>) is partitioned into two sets <i>I</i>_<i>1</i> and <i>I</i>_<i>2</i>, where |<i>I</i>_<i>1</i>| = <i>p-q</i> and |<i>I</i>_<i>2</i>| = <i>q</i> and where each of the <i>p-q</i> inputs in <i>I</i>_<i>1</i> are connected to all of the <i>q</i> outputs and each of the <i>q</i> inputs in <i>I</i>_<i>2</i> are connected to a single but distinct output. It can be shown that every <i>p</i>x<i>q</i> fat-and-slim concentrator is a sparse crossbar concentrator with a minimum number of crosspoints for any 1 ≤ <i>p ≤ q</i>.

0032A block diagram of an embodiment of three-stage group connector 300 constructed using crossbars and concentrators is illustrated in FIG. 3. Because the structure of the group connector 300 is determined by three parameters <i>m, n,</i> and <i>r,</i> it is denoted by <i>g(m,n,r).</i> In particular, the group connector 300 includes <i>r n</i>x<i>m</i> crossbar switch modules 302(1)-302(r) in an input stage 304, <i>m r</i>x<i>r</i> crossbar switch modules 306(1)-306(<i>m</i>) in a middle stage 308, and <i>r m</i> x <i>n</i> concentrator switch modules 310(1)-310(<i>r</i>) in an output stage 312, wherein <i>n</i> = <i>nr</i> and <i>m</i>≥ <i>n</i> and <i>n</i> is the group size. Note that the structure of the group connector 300 is similar to that of a three-stage Clos network (<i>m,n,r</i>), except that the output stage 312 comprises concentrators instead of crossbar switches. The group connector 300 is non-blocking for connecting any <i>n</i> inputs to a group at the output of the connector if <i>m</i> ≥ 2<i>n</i>-1.

0033In general, the number of crosspoints of a network is a representative measure of network cost. The number of crosspoints of a non-blocking three-stage group connector, such as the group connector 300, will now be calculated. Recall that an <i>n</i>₁x<i>n</i>₂ crossbar has <i>n</i>₁<i>n</i>₂ crosspoints, while an <i>n</i>₁x<i>n</i>₂ concentrator has (<i>n</i>₁-<i>n</i>₂+1)<i>n</i>₂ crosspoints. Thus, for a non-blocking group connector <i>g</i>(<i>m,n,r</i>), the number of crosspoints is:<maths id="math0001" num="(1)"><math display="block"><mrow><mtext mathvariant="italic">rnm</mtext><mtext> + </mtext><mtext mathvariant="italic">mrr</mtext><mtext> + </mtext><mtext mathvariant="italic">r</mtext><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext>-</mtext><mtext mathvariant="italic">n</mtext><mtext>+1)</mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1549102A2_D0001.tif" /></maths> Non-Blocking Multistage Group Connectors

0034To reduce network cost, the three-stage group connector 300 illustrated in FIG. 3 can be generalized to a non-blocking multistage group connector as follows. First, a <i>p</i>x<i>q</i> fat-and-slim concentrator is implemented using a (<i>p-q</i>)x<i>q</i> crossbar switch and <i>q</i> 2x1 switches. A 9x4 fat-and-slim concentrator 400 implemented in this manner is illustrated in FIG. 4. The concentrator 400 includes a 5x4 crossbar switch 402 and four 2x1 switches 404(1)-404(4).

0035To construct the non-blocking multistage group connector, every crossbar switch module 302(1)-302(<i>r</i>), 306(1)-306(<i>m</i>), in every stage 304, 308, 312, of the three-stage group connector 300 is recursively replaced by a three-stage group connector <i>g(m,n,r)</i> that has the same size as the crossbar switch module being replaced. The following discussion addresses how to determine the parameters of the three-stage network that replaces an <i>N</i>_<i>1</i>x<i>N</i>_<i>2</i> crossbar to achieve a minimum cost, where <i>N</i>_<i>1</i> is not necessarily equal to <i>N</i>_<i>2</i>.

0036FIG. 5 is a block diagram of a general <i>N</i>_<i>1</i>x<i>N</i>_<i>2</i> three-stage network 500 with five parameters, denoted <i>v</i>(<i>m,n</i>_<i>1</i><i>,r</i>_<i>1</i><i>,n</i>_<i>2</i><i>,r</i>_<i>2</i>), where <i>N</i>_<i>1</i><i> = n</i>_<i>1</i>x<i>r</i>_<i>1</i> and <i>N</i>_<i>2</i><i> = n</i>_<i>2</i>x<i>r</i>_<i>2</i>. In particular, the network 500 includes a first stage 502, a second stage 504, and a third stage 506. The first stage 502 comprises <i>r</i>_<i>1</i> crossbar switches 508(1)-508(<i>r</i>_<i>1</i>), the second stage 504 comprises <i>m</i> crossbar switches 510(1)-510(<i>m</i>), and the third stage 506 comprises <i>r</i>_<i>2</i> crossbar switches 512(1)-512(<i>r</i>_<i>2</i>). A condition that must be met for the network 500 to be non-blocking for any one-to-one connections is that the number of middle stage switches <i>m</i> satisfies the following:<maths id="math0002" num="(2)"><math display="block"><mrow><mtext mathvariant="italic">m ≥</mtext><mtext> (</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext> - 1)</mtext></mrow></math><img file="EP1549102A2_D0002.tif" /></maths> Therefore, the number of crosspoints in a non-blocking <i>N</i>_<i>1</i>x<i>N</i>_<i>2</i><i> v</i>(<i>m,n</i>_<i>1</i><i>,r</i>_<i>1</i><i>,n</i>_<i>2</i><i>,r</i>_<i>2</i>) network can be calculated as follows:<maths id="math0003" num="(3)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mspace linebreak="newline" /><mtext> = (</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>)</mtext><mtext mathvariant="italic">m</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mspace linebreak="newline" /><mtext>= </mtext><mtext mathvariant="italic">m</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>)</mtext><mspace linebreak="newline" /><mtext> = (</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext> - 1)((</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>)/(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>) + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1549102A2_D0003.tif" /></maths>

0037It can be shown that when<maths id="math0004" num="(4)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext> = ((</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>)/(</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup></mrow></math><img file="EP1549102A2_D0004.tif" /></maths> an <i>N</i>_<i>1</i>x<i>N</i>_<i>2</i> three-stage non-blocking network achieves the minimum number of crosspoints, which is:<maths id="math0005" num="(5)"><math display="block"><mrow><mtext>2(</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>)[2((</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> x </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext>)/(</mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext> - 1]</mtext></mrow></math><img file="EP1549102A2_D0005.tif" /></maths> Thus, for any <i>N</i>_<i>1</i> x <i>N</i>_<i>2</i> crossbar switch, based on equations (4) and (2), an <i>N</i>_<i>1</i> x <i>N</i>_<i>2</i> three-stage non-blocking network with a minimum cost can be constructed.

0038In the following, a nine-stage group connector is used as an example to illustrate how to calculate the crosspoints of a non-blocking multistage group connector. A similar method can be used for any 3<i>k</i>-stage non-blocking group connector with <i>k</i> > 1,

0039A nine-stage group connector is realized by replacing each switch in a three-stage group connector by a same-size three-stage network. Since the first stage of the original three-stage network consists of <i>r n</i>x<i>m</i> switches, after replacing each such switch with an <i>n</i>x<i>m</i> three-stage network, according to equation (5), there are<maths id="math0006" num="(6)"><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext>[2 (</mtext><mtext mathvariant="italic">n</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext>)(2((</mtext><mtext mathvariant="italic">n</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext><mtext>)/(</mtext><mtext mathvariant="italic">n</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext> - 1)]</mtext><mspace linebreak="newline" /><mtext> = 2</mtext><mtext mathvariant="italic">r</mtext><mtext>(2(</mtext><mtext mathvariant="italic">n</mtext><mtext> x </mtext><mtext mathvariant="italic">m</mtext><mtext> (</mtext><mtext mathvariant="italic">n</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">m</mtext><mtext>)</mtext></mrow></math><img file="EP1549102A2_D0006.tif" /></maths> crosspoints in the first three stages of the nine-stage group connector.

0040Similarly, since the second stage of the original three-stage network consists of <i>m r</i>x<i>r</i> switches, after replacing each such switch with an <i>r</i>x<i>r</i> three-stage network, according to equation (5), there are<maths id="math0007" num="(7)"><math display="block"><mrow><mtext mathvariant="italic">m</mtext><mtext>[2® + </mtext><mtext mathvariant="italic">r</mtext><mtext>) (2((</mtext><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext><mtext>)/</mtext><mtext mathvariant="italic">(r</mtext><mtext> + </mtext><mtext mathvariant="italic">r</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext> - 1)]</mtext><mspace linebreak="newline" /><mtext> = 4</mtext><mtext mathvariant="italic">mr</mtext><mtext>(2</mtext><mtext mathvariant="italic">r</mtext><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext> - 1</mtext></mrow></math><img file="EP1549102A2_D0007.tif" /></maths> crosspoints in stages four, five, and six of the nine-stage group connector.

0041Finally, since the last stage of the original three-stage network consists of <i>r</i> (<i>m-n</i>)x<i>n</i> switches and <i>rn</i> 2x1 switches, after replacing each (<i>m-n</i>)x<i>n</i> switch with an (m-<i>n</i>)x<i>n</i> three-stage group connector, according to equation (5), there are<maths id="math0008" num="(8)"><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext>[2(</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + </mtext><mtext mathvariant="italic">n</mtext><mtext>) (2(((</mtext><mtext mathvariant="italic">m</mtext><mtext>-</mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext><mtext mathvariant="italic">n</mtext><mtext>)/(</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + </mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext> - 1) + 2</mtext><mtext mathvariant="italic">n</mtext><mtext>]</mtext><mspace linebreak="newline" /><mtext> = 2</mtext><mtext mathvariant="italic">r</mtext><mtext>(2(</mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext><mtext> (</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext> + </mtext><mtext mathvariant="italic">n - m</mtext><mtext>)</mtext></mrow></math><img file="EP1549102A2_D0008.tif" /></maths> crosspoints in the last three stages of the nine-stage group connector. By combining equations (6), (7), and (8), the total number of crosspoints of the nine-stage group connector is<maths id="math0009" num="(9)"><math display="block"><mrow><mtext>2</mtext><mtext mathvariant="italic">r</mtext><mtext>(2(</mtext><mtext mathvariant="italic">n</mtext><mtext>x</mtext><mtext mathvariant="italic">m</mtext><mtext>(</mtext><mtext mathvariant="italic">n</mtext><mtext>+</mtext><mtext mathvariant="italic">m</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-</mtext><mtext mathvariant="italic">n</mtext><mtext>-</mtext><mtext mathvariant="italic">m</mtext><mtext>)+4</mtext><mtext mathvariant="italic">mr</mtext><mtext>((2</mtext><mtext mathvariant="italic">r</mtext><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-1)+2</mtext><mtext mathvariant="italic">r</mtext><mtext>(2(</mtext><mtext mathvariant="italic">m</mtext><mtext>x</mtext><mtext mathvariant="italic">n</mtext><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext>-</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>+</mtext><mtext mathvariant="italic">n</mtext><mtext>-</mtext><mtext mathvariant="italic">m</mtext><mtext>)</mtext><mspace linebreak="newline" /><mtext> = 4</mtext><mtext mathvariant="italic">r</mtext><mtext>[</mtext><mtext mathvariant="italic">m</mtext><mtext>x</mtext><mtext mathvariant="italic">n</mtext><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext>+</mtext><mtext mathvariant="italic">n</mtext><mtext>)+</mtext><mtext mathvariant="italic">m</mtext><mtext>x</mtext><mtext mathvariant="italic">n</mtext><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext>-</mtext><mtext mathvariant="italic">n</mtext><mtext>)+</mtext><mtext mathvariant="italic">m</mtext><mtext>(2</mtext><mtext mathvariant="italic">r</mtext><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-2</mtext><mtext mathvariant="italic">m</mtext><mtext>]</mtext></mrow></math><img file="EP1549102A2_D0009.tif" /></maths> Under certain conditions, a three-stage group connector can be recursively transformed into a multi-stage group connector consisting of 2 x 2 switches.

<u>REARRANGEABLY NON-BLOCKING GROUP CONNECTORS</u>

0042A group connector is rearrangeably non-blocking if it can realize all possible connections between the inputs and any groups of outputs, where the rearrangement to existing connections is permitted.

<u>Rearrancreably Non-Blocking Three-Stage Group Connectors</u>

0043A three-stage g(<i>m,n,r</i>) network is rearrangeably non-blocking for connecting any n inputs to a group at the output of the network, if the number of middle stage switches <i>m</i> . <i>n</i>. It will be recognized that a three-stage Clos network is rearrangeably non-blocking for permutations if <i>m</i> ≥ <i>n.</i> In a <i>g</i>(<i>m,n,r</i>), since there is no need to distinguish the outputs in a group, concentrators are used in the third stage. Thus, the connections can be rotated the same way as a permutation at the first two stages and then concentrated to each group through concentrators. In fact, if the minimum value of m is considered, the concentrators at the output stage become <i>n</i> x <i>n</i> concentrators. In this case, a two-stage rearrangeably non-blocking group connector is obtained by simply removing the concentrators of the group connector 300 (FIG. 3), the result of which is illustrated in FIG. 6. Thus, for a three-stage rearrangeably non-blocking group connector, the number of crosspoints is<maths id="math0010" num="(10)"><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext><mtext> x </mtext><mtext mathvariant="italic">m</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext></mrow></math><img file="EP1549102A2_D0010.tif" /></maths> Rearrangeably Non-Blocking Multistage Group Connectors

0044Similar to permutation networks, the rearrangeably non-blocking three-stage group connector can be generalized to a multi-stage group connector. In particular, a group connector can be constructed from a Benes network of the same size. FIGs. 7A and 7B illustrate construction of a 16 x 16 group connector of group size 4, designated in FIG. 7B by a reference numeral 700, from a 16 x 16 Benes network, designated in FIG. 7A by a reference numeral 710. That the network illustrated in FIG. 7B is a group switch of group size 4 can be verified by setting all switches to strait connections in stages 5 and 6 of the Benes network 710. In general, an <i>N</i> x <i>N</i> (<i>N</i> = 2^<i>m</i>) group connector of group size 2^<i>k</i> (<i>k</i> &lt; <i>m</i>) can be obtained by setting all switches in stages 2<i>m</i> - 2, 2<i>m</i> - 3, ... , 2<i>m</i> - (<i>k</i> + 1) to straight connections and removing these switches. Since a Benes network can realize all possible permutations between the network inputs and outputs, the network constructed in this manner can realize all possible group connections from network inputs to network outputs.

0045Clearly, an N x N multi-stage group connector of size 2^<i>k</i> has crosspoints<maths id="math0011" num="(11)"><math display="block"><mrow><mtext>(2 log </mtext><mtext mathvariant="italic">N</mtext><mtext> - 1 - </mtext><mtext mathvariant="italic">k</mtext><mtext>) (</mtext><mtext mathvariant="italic">N</mtext><mtext>/2 x 2 x 2)</mtext></mrow></math><img file="EP1549102A2_D0011.tif" /></maths>

NETWORK COST COMPARISONS

0046The network cost of a one embodiment of a group connector as described hereinabove can be compared with the corresponding permutation network to determine how much can be saved on crosspoints. It will be recalled that for a three-stage permutation network <i>v</i> (<i>m, n, r</i>), the number of crosspoints is<maths id="math0012" num="(12)"><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext><mtext> x </mtext><mtext mathvariant="italic">m</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext><mtext> + </mtext><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1549102A2_D0012.tif" /></maths> Since a three-stage non-blocking group connector <i>g(m, n, r</i>) has<maths id="math0013" num=""><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext><mtext> x </mtext><mtext mathvariant="italic">m</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext><mtext> + </mtext><mtext mathvariant="italic">r</mtext><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 1)</mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1549102A2_D0013.tif" /></maths> crosspoints, the savings in crosspoints by using an <i>N</i> x <i>N</i> non-blocking group connector as opposed to a permutation network is<maths id="math0014" num="(13)"><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext><mtext>(</mtext><mtext mathvariant="italic">n</mtext><mtext> - 1) = </mtext><mtext mathvariant="italic">N</mtext><mtext>(</mtext><mtext mathvariant="italic">n -</mtext><mtext> 1)</mtext></mrow></math><img file="EP1549102A2_D0014.tif" /></maths>

0047Since a three-stage rearrangeably non-blocking group connector has<maths id="math0015" num=""><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext><mtext> x </mtext><mtext mathvariant="italic">m</mtext><mtext> + </mtext><mtext mathvariant="italic">m</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext><mtext> x </mtext><mtext mathvariant="italic">r</mtext></mrow></math><img file="EP1549102A2_D0015.tif" /></maths> crosspoints, compared with a three-stage permutation network, the savings in crosspoints using a three-stage <i>n</i> x n rearrangeably non-blocking group connector is<maths id="math0016" num="(14)"><math display="block"><mrow><mtext mathvariant="italic">r</mtext><mtext> x </mtext><msup><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> = </mtext><mtext mathvariant="italic">N</mtext><mtext> x </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1549102A2_D0016.tif" /></maths> A multi-stage group connector will now be considered. For a non-blocking multi-stage network, a nine-stage group connector is used as an example. It will be recognized that a nine-stage permutation network and a nine-stage group connector differ only in their last three stages and the cost of the last three stages of the permutation network is given in equation (6) and that of the group connector given in equation (8). Thus, the savings in crosspoints for a nine-stage group connector, compared with a nine-stage permutation network is<maths id="math0017" num="(15)"><math display="block"><mrow><mtext>2</mtext><mtext mathvariant="italic">r</mtext><mtext>(2(</mtext><mtext mathvariant="italic">n</mtext><mtext>x</mtext><mtext mathvariant="italic">m</mtext><mtext>(</mtext><mtext mathvariant="italic">n+m</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-</mtext><mtext mathvariant="italic">n</mtext><mtext>-</mtext><mtext mathvariant="italic">m</mtext><mtext>)-2</mtext><mtext mathvariant="italic">r</mtext><mtext>(2(</mtext><mtext mathvariant="italic">m</mtext><mtext>x</mtext><mtext mathvariant="italic">n</mtext><mtext>(-</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>+</mtext><mtext mathvariant="italic">n</mtext><mtext>-</mtext><mtext mathvariant="italic">m</mtext><mtext>)</mtext><mspace linebreak="newline" /><mtext> = 2</mtext><mtext mathvariant="italic">r</mtext><mtext>[2(</mtext><mtext mathvariant="italic">n</mtext><mtext>(2</mtext><mtext mathvariant="italic">n</mtext><mtext>-1)(3</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>-1))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-3</mtext><mtext mathvariant="italic">n</mtext><mtext>+1]-2</mtext><mtext mathvariant="italic">r</mtext><mtext>[2(</mtext><mtext mathvariant="italic">n</mtext><mtext>(2</mtext><mtext mathvariant="italic">n</mtext><mtext>-1)(</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>-1))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-</mtext><mtext mathvariant="italic">n</mtext><mtext>+1]</mtext><mspace linebreak="newline" /><mtext> = 4</mtext><mtext mathvariant="italic">r</mtext><mtext>[(</mtext><mtext mathvariant="italic">n</mtext><mtext>(2</mtext><mtext mathvariant="italic">n</mtext><mtext>-1)(3</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>-1))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-((2</mtext><mtext mathvariant="italic">n</mtext><mtext>-1)(</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>-1))</mtext></mrow><mrow><mtext>½</mtext></mrow></msup><mtext>-</mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1549102A2_D0017.tif" /></maths>

0048Finally, since a <i>n</i> x <i>n</i> Benes network has<maths id="math0018" num=""><math display="block"><mrow><mtext>(2 log </mtext><mtext mathvariant="italic">N</mtext><mtext> - 1) (</mtext><mtext mathvariant="italic">N</mtext><mtext>/2 x 2 x 2) = 2</mtext><mtext mathvariant="italic">N</mtext><mtext>(2 log </mtext><mtext mathvariant="italic">N</mtext><mtext> - 1)</mtext></mrow></math><img file="EP1549102A2_D0018.tif" /></maths> crosspoints, while an <i>N</i> x <i>N</i> multi-stage rearrangeable group connector of size 2<i>k</i> has<maths id="math0019" num=""><math display="block"><mrow><mtext>(2 log </mtext><mtext mathvariant="italic">N -</mtext><mtext> 1 - </mtext><mtext mathvariant="italic">k)</mtext><mtext> (</mtext><mtext mathvariant="italic">N</mtext><mtext>/2 x 2 x 2)</mtext></mrow></math><img file="EP1549102A2_D0019.tif" /></maths> crosspoints, the savings in crosspoints by using an <i>N</i> x <i>N</i> multi-stage group connector of size 2^<i>k</i> is<maths id="math0020" num="(16)"><math display="block"><mrow><mtext>2</mtext><mtext mathvariant="italic">N</mtext><mtext> x </mtext><mtext mathvariant="italic">k</mtext></mrow></math><img file="EP1549102A2_D0020.tif" /></maths>

0049From the above analysis, it is apparent that for applications that do not require the order of outputs within a group to be distinguished, a group connector can be used to reduce the network cost. For example, assuming an application with 1024 inputs/outputs and a group size of eight, by replacing a 1024 x 1024 Benes network with a group connector of the same size, 8/19, or 42%, of the crosspoints can be eliminated.

0050In summary, a class of interconnection networks called group connectors have been described which have important application in constructing client-server connections, DWDM add/drop cross-connects, and switching matrices for DWDM routers. It has been demonstrated that the cost of such group connectors, in terms of crosspoints, is significantly lower than that of permutation networks. The embodiments described herein are particularly useful for ingress routers for DWDM networks operating in slot transmission mode, in which input packets with the same destination are assembled into larger, fixed-length frames, each corresponding to a time-slot, at ingress line cards ("ILCs"). All <i>N</i> input requests are given simultaneously for switching and unnecessary connection conflicts can be avoided by properly controlling the switching elements. The amortized overhead in routing and forwarding of frames can be much smaller than that for switching individual packets.

0051The following methods or apparatus or method steps or apparatus features, separately or in combination, also constitute advantageous embodiments of the invention: <ul id="ul0001" list-style="dash"><li>A method of constructing an <i>N</i>_<i>1</i>x<i>N</i>_<i>2</i> multistage group connector with <i>N</i>_<i>1</i> inputs and <i>N</i>_<i>2</i> outputs from a three-stage group connector, wherein the three-stage group connector comprises a first stage comprising <i>r n</i>x<i>m</i> crossbar switch modules, a second stage comprising <i>m r</i>x<i>r</i> crossbar switch modules, and a third stage comprising <i>r m</i>x<i>n</i> concentrator switch modules, the method comprising: replacing each of the <i>r r</i>x<i>m</i> crossbar switch modules of the first stage with a three-stage group connector of the same size as the <i>r</i>x<i>m</i> crossbar switch module; and replacing each of the <i>m r</i>x<i>r</i> crossbar switch modules of the second stage with a three-stage group connector of the same size as the rxr crossbar switch module;</li><li>The described method further comprising: implementing each concentrator of the third stage using a <i>p</i>x<i>q</i> fat-and-slim concentrator;</li><li>An <i>N</i>x<i>N</i> multi-stage group connector with <i>N</i> inputs and <i>N</i> outputs, wherein the <i>N</i> outputs are divided into r output groups, each group including <i>n</i> outputs such that <i>r</i> = <i>N</i>/<i>n</i>, the connector comprising: a first portion comprising <i>r n</i>x<i>m</i> three-stage group connectors, wherein <i>m</i> ≥ n-1; a second portion comprising <i>m r</i>x<i>r</i> three-stage group connectors; and a third portion comprising <i>r p</i>x<i>q</i> fat and slim concentrator switch modules;</li><li>The described group connector wherein each of the concentrators includes a minimum number of crosspoints;</li><li>The described group connector wherein each of the concentrators includes a maximum of (<i>m-n</i>+1)<i>n</i> crosspoints;</li><li>The described group connector wherein m ≥ n;</li><li>The described group connector wherein the group connector is non-blocking;</li><li>The described group connector wherein m ≥ 2n-1;</li><li>An <i>N</i>x<i>N</i> two-stage group connector with <i>N</i> inputs and <i>N</i> outputs, wherein the <i>N</i> outputs are divided into <i>r</i> output groups, each group including <i>n</i> outputs such that <i>r</i> = <i>N</i>/<i>n</i>, the group connector comprising: a first stage comprising <i>r n</i>x<i>m</i> crossbar switch modules; and a second stage comprising <i>m r</i>x<i>r</i> crossbar switch modules; wherein <i>m</i> is equal to 2<i>n</i>-1;</li><li>The described group connector wherein the group connector is non-blocking;</li><li>A method of constructing an <i>N</i> x <i>N</i> group connector of group size 2^<i>k</i> from an <i>N</i> x <i>N</i> Benes network, the method comprising: setting all switches in stages 2<i>m</i>-2, 2<i>m</i>-3, ... 2<i>m</i>-(<i>k</i>+1) of the Benes network to straight connections; and removing all switches in stages 2<i>m</i>-2, 2<i>m</i>-3, ... 2<i>m</i>-(<i>k</i>+1) of the Benes network;</li><li>The described method wherein <i>N</i> is equal to 2^<i>m</i>;</li><li>The described method wherein <i>k</i> is less than or equal to <i>m</i>;</li><li>The described method wherein <i>N</i> is equal to 2^<i>m</i> and <i>k</i> is less than or equal to <i>m</i>.</li></ul>

0052It is believed that the operation and construction of the present invention will be apparent from the Detailed Description set forth above. While the exemplary embodiments of the invention shown and described have been characterized as being preferred, it should be readily understood that various changes and modifications could be made therein without departing from the scope of the present invention as set forth in the following claims.