US 20050141804A1
`
`(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2005/0141804 A1
`(43) Pub. Date: Jun. 30, 2005
`
`Yang et al.
`
`(54) GROUP SWITCHING METHOD AND
`APPARATUS FOR DENSE WAVELENGTH
`DIVISION MULTIPLEXING OPTICAL
`NETWORKS
`
`(76)
`
`Inventors: Yuanyuan Yang, East Setauket, NY
`(US); Siqing Zheng, Plano, TX (US);
`Dominique Verchere, Dallas, TX (US)
`
`Correspondence Address:
`ALCATEL USA
`INTELLECTUAL PROPERTY DEPARTMENT
`3400 W. PLANO PARKWAY, MS LEGL2
`PLANO, TX 75075 (US)
`
`(21) Appl. No.:
`
`10/745,872
`
`(22)
`
`Filed:
`
`Dec. 24, 2003
`
`Publication Classification
`
`Int. Cl.7 ....................................................... G02B 6/35
`(51)
`(52) U.S.Cl.
`................................................................ 385/17
`
`(57)
`
`ABSTRACT
`
`Method and apparatus for performing group switching in
`DWDM optical networks are described. One embodiment is
`an N><N three-stage group connector with N inputs and N
`outputs, wherein the N outputs are divided into r output
`groups, each group including n outputs such that r=N/n. The
`group connector comprises a first stage comprising r n><m
`crossbar switch modules, wherein min—1; a second stage
`comprising m r><r crossbar switch modules; and a third stage
`comprising r M><N concentrator switch modules.
`
`r.__.___________________.__...__....__.__._.__.__.____________._____
`
`mxn
`
`smamo
`
`Petitioner Huawei - Exhibit 1007, p. 1
`
`Petitioner Huawei - Exhibit 1007, p. 1
`
`

`

`Patent Application Publication Jun. 30, 2005 Sheet 1 of 6
`
`US 2005/0141804 A1
`
`100
`
`“0
`112(1)
`108(1)
`
`
`
`
`13h1
`Ch2
`ChN/n-1
`ChN/n
`
`108(2)
`
`106(1)
`102(1)
`
`106(2)
`102(2)
`
`106(3)
`102(3)
`
`TT\
`
`104(1)
`
`104(2)
`
`Ch1
`Ch2
`Cthn-1
`ChN/n
`
`
`
`105W)
`102(N)
`
`108(N/n)
`
`a
`
`Ch
`Ch‘
`Chg/M
`
`ChN/n
`
`104 N/n
`(
`
`)
`
`FIG. 1
`
`200.
`
`/
`
`204
`
`204
`
`O
`S.
`“U
`a
`
`INPUTS
`
`FIG. 2A
`
`204
`204
`204
`
`202
`
`/
`
`INPUTS
`
`204
`
`O
`E.
`'U
`a
`
`204
`
`204
`
`FIG. 28
`
`Petitioner Huawei - Exhibit 1007, p. 2
`
`Petitioner Huawei - Exhibit 1007, p. 2
`
`

`

`Patent Application Publication Jun. 30, 2005 Sheet 2 of 6
`
`US 2005/0141804 A1
`
`5885\L38mmmasr.........................A.r...............-r...............-/8m/gm
`
`.3:
`
`Ex:.Am“
`
`Lmnmweu.
`
`ch
`
`
`
`5885..x.Exc.11‘1ISam
`5386
`
`N.
`
`._o
`
`Petitioner Huawei - Exhibit 1007, p. 3
`
`Petitioner Huawei - Exhibit 1007, p. 3
`
`
`

`

`Patent Application Publication Jun. 30, 2005 Sheet 3 of 6
`
`US 2005/0141804 A1
`
`
`
`E
`
`I
`
`404(2) 3
`
`404(3)
`
`402
`
`Petitioner Huawei - Exhibit 1007, p. 4
`
`Petitioner Huawei - Exhibit 1007, p. 4
`
`

`

`Patent Application Publication Jun. 30, 2005 Sheet 4 of 6
`
`US 2005/0141804 A1
`
`8m
`
`
`
`Petitioner Huawei - Exhibit 1007, p. 5
`
`Petitioner Huawei - Exhibit 1007, p. 5
`
`

`

`mo.GE
`
`mas
`
`5385HW_fExcM38m3%m\an
`m..FF.m285cHH5885
`
`uP
`
`n.
`
`0m.w,
`
`mm5
`
`nN965c5385N.mExcmSwen
`
`m_.M3:90:5885HUEx:
`mN.
`smsaU.Tw.wUoN50II
`
`
`3%
`
`Petitioner Huawei - Exhibit 1007, p. 6
`
`Petitioner Huawei - Exhibit 1007, p. 6
`
`

`

`Patent Application Publication Jun. 30, 2005 Sheet 6 of 6
`
`US 2005/0141804 A1
`
`
`
`
`
`
`wllvlvll
`
`
`MAP-1R”,-
`
`‘V’T.:=:=:.."‘:*'
`‘ ‘ s
`i ‘ I
`
`
`
`
`
`
`
`
`
`
`o».
`J»
`
`
`
`
`
`J‘l-O~l--I-l-'%-l-’\-I
`
`
`
`-I‘..‘i’..‘.‘l
`
`
`
`Stage 0
`
`Stage 1
`
`Stage 2
`
`Stage 3
`
`Stage 4
`
`Stage 5
`
`Stage 6
`
`FIG. 7A
`
` Group 4
`
`Stage 0
`
`Stage 1
`
`Stage 2
`
`Stage 3
`
`Stage 4
`
`FIG. 7B
`
`Petitioner Huawei - Exhibit 1007, p. 7
`
`Petitioner Huawei - Exhibit 1007, p. 7
`
`

`

`US 2005/0141804 A1
`
`Jun. 30, 2005
`
`GROUP SWITCHING METHOD AND APPARATUS
`FOR DENSE WAVELENGTH DIVISION
`MULTIPLEXING OPTICAL NETWORKS
`
`Benes or Clos network, can be used to provide the switching
`function; however, such permutation networks can be costly
`in terms of hardware.
`
`BACKGROUND OF THE INVENTION
`
`SUMMARY OF THE INVENTION
`
`[0001]
`
`1. Technical Field of the Invention
`
`[0002] The present invention generally relates to Wave-
`length 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.
`
`[0003]
`
`2. Description of Related Art
`
`[0004] The laying of new fiber was once the only way to
`cope with fiber exhaust in optical telecommunications net-
`works. 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 net-
`works. With TDM,
`the capacity of a single fiber was
`increased by dividing time into small intervals and multi-
`plexing the various signals onto these separate time inter-
`vals.
`
`In TDM systems, each optical fiber is capable of
`[0005]
`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 trans-
`mission 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.
`
`[0006] During 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 neces-
`sitate the use of narrow lasers.
`
`In order to increase the number of services that can
`[0007]
`be provided,
`the channel spaces can be moved closer
`together, creating Dense WDM (“DWDM”). This technol-
`ogy economically increases transport capacity through the
`utilization of existing fiber routes and terminal equipment.
`
`[0008] ADWDM system can be described as a parallel set
`of optical channels each using a slightly different wave-
`length, 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 con-
`verted 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
`(“OF 1’).
`
`[0009] Every router in a DWDM network must provide a
`switching function between N inputs thereto and N outputs
`therefrom such that simultaneous one-to-one connections
`
`between the N inputs and any one of the N outputs. Note that
`a group connector is able to distinguish among groups of
`outputs. Clearly, an N><N permutation network, such as a
`
`is an N><N three-stage group
`[0010] One embodiment
`connector with N inputs and N outputs, wherein the N
`outputs are divided into r output groups, each group includ-
`ing n outputs such that r=N/n. The group connector com-
`prises a first stage comprising r n><m crossbar switch mod-
`ules, wherein m>n—1; a second stage comprising m r><r
`crossbar switch modules; and a third stage comprising r
`M><N concentrator switch modules.
`
`[0011] Another embodiment is a method of constructing
`an leN2 multistage group connector with N1 inputs and N2
`outputs from a three-stage group connector, wherein the
`three-stage group connector comprises a first stage compris-
`ing r n><m crossbar switch modules, a second stage com-
`prising m r><r crossbar switch modules, and a third stage
`comprising r m><n concentrator switch modules. The method
`comprises replacing each of the r r><m crossbar switch
`modules of the first stage with a three-stage group connector
`of the same size as the r><m crossbar switch module; and
`replacing each of the m r><r crossbar switch modules of the
`second stage with a three-stage group connector of the same
`size as the r><r crossbar switch module.
`
`[0012] Another embodiment is an N><N multi-stage group
`connector with N inputs and N outputs, wherein the N
`outputs are divided into r output groups, each group includ-
`ing n outputs such that r=N/n. The group connector com-
`prises a first portion comprising r n><m three-stage group
`connectors, wherein m>n—1; a second portion comprising m
`r><r three-stage group connectors; and a third portion com-
`prising r p><q fat and slim concentrator switch modules.
`
`[0013] Another embodiment is an N><N two-stage group
`connector with N inputs and N outputs, wherein the N
`outputs are divided into r output groups, each group includ-
`ing n outputs such that r=N/n. The group connector com-
`prises a first stage comprising r n><m crossbar switch mod-
`ules; and a second stage comprising m r><r crossbar switch
`modules, wherein m is equal to 2n—1.
`
`[0014] Another embodiment is a method of constructing
`an N><N group connector of group size 2k from an N><N
`Benes network. The method comprises setting all switches
`in stages 2m—2, 2m—3, .
`.
`. 2m—(k+1) of the Benes network
`to straight connections; and removing all switches in stages
`2m—2, 2m—3,
`.
`.
`. 2m—(k+1) of the Benes network.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0015] A more complete understanding of the present
`invention may be had by reference to the following Detailed
`Description when taken in conjunction with the accompa-
`nying drawings wherein:
`
`[0016] FIG. 1 is a schematic block diagram of an ingress
`edge router of one embodiment;
`
`[0017] FIG. 2A illustrates an embodiment of an optimal
`concentrator comprising a p><q fat-and-slim concentrator;
`
`[0018] FIG. 2B illustrates an embodiment of an optimal
`concentrator comprising a p><q banded concentrator;
`
`Petitioner Huawei - Exhibit 1007, p. 8
`
`Petitioner Huawei - Exhibit 1007, p. 8
`
`

`

`US 2005/0141804 A1
`
`Jun. 30, 2005
`
`[0019] FIG. 3 is a schematic block diagram of an N><N
`three-stage group connector g(m,n,r), where N=nr;
`
`[0020] FIG. 4 illustrates an embodiment of a 9x4 fat-and-
`slim concentrator;
`
`[0021] FIG. 5 is a schematic block diagram of a N1><N2
`three-stage group connector v(m, n1, r1, n2, r2);
`
`[0022] FIG. 6 is schematic block diagram of an n><n
`two-stage rearrangeably non-blocking group connector,
`where N=nr;
`
`[0023] FIG. 7A illustrates an embodiment of a 16x16
`Benes network; and
`
`[0024] FIG. 7B illustrates construction of a 16x16 group
`connector of group size four from the Benes network of
`FIG. 7A.
`
`DETAILED DESCRIPTION OF THE DRAWINGS
`
`In the drawings, like or similar elements are des-
`[0025]
`ignated with identical reference numerals throughout the
`several views thereof, and the various elements depicted are
`not necessarily drawn to scale.
`
`[0026] A new class of interconnection networks called
`group connectors is introduced. A group connector G(N,n) is
`a switching network that consists of N inputs and N outputs
`such that (1) its N outputs are divided into N/n groups with
`n outputs in each group; and (2) it can provide any simul-
`taneous one-to-one connections from the N inputs to the N
`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”) net-
`works. Clearly, an N><N permutation network can be used as
`an N><N group connector; however, as will be demonstrated
`hereinbelow, a group connector G(N,n) can be built at a
`lower hardware cost than can a permutation network of the
`same size.
`
`In general, a group connector G(N,n) captures the
`[0027]
`simultaneous connections between N clients and N servers,
`which are divided into N/n equal-size server groups such
`that the n servers in each group are functionally equivalent.
`Group connectors are particularly useful in DWDM net-
`works. 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 n different wavelengths and an
`optical router has N/n 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. Agroup 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 con-
`nected to a local node, a group connecter can be used as an
`add/drop cross-connect switching matrix.
`
`[0028] Group 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 N electrical or optical input links 102(1)-
`
`102(N) and a set of N/n optical output links 104(1)-104(N/
`n). Each optical output link 104(1)-104(N/n) includes of a
`set of n data channels Chm, .
`.
`. Chm, each using a different
`wavelength. Associated with each input link 102(1)-102(N)
`is a respective input line card (“ILC”) 106(1)-106(N). Simi-
`larly, associated with each output link 104(1)-104(N/n) is a
`respective output
`line card (“OLC”) 108(1)-108(N/n). A
`switching matrix 110 is disposed between the set of ILCs
`106(1)-106 (N) and the set of OLCs 108(1)-108(N/n). The
`switching matrix 110 is individually connected to each of the
`OLCs 108(1)-108(N/n) by connections 112(1)-112(n).
`
`[0029] The 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 n optical channels of the link 104(1)-104(N/n) 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
`
`[0030] A group connector G(N,n) is “non-blocking” if any
`of its n 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
`
`[0031] Group connector designs can utilize “concentra-
`tors” to reduce network cost. A p><q (péq) concentrator
`under consideration is a single stage sparse crossbar switch-
`ing device that can connect any q of its p inputs to its q
`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 p><q sparse
`crossbar concentrator must contain at least (p—q+1)><q cros-
`spoints.
`
`[0032] More recently, sparse crossbar concentrators that
`use (p—q+1)><q crosspoints have been designed. Two 9x4
`concentrators with a minimum number of crosspoints are
`illustrated in FIGS. 2A and 2B, respectively, and respec-
`tively designated by reference numbers 200 and 202. The
`concentrator 200 is referred to as a “fat-and-slim concen-
`trator”. 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.
`
`[0033] For purposes of example herein, the fat-and-slim
`concentrator 200 illustrated in FIG. 2A will be used. In
`
`to construct a p><q fat-and-slim concentrator, its
`general,
`input set I(|I|=p) is partitioned into two sets I1 and 12, where
`|Il|=p—q and |12|=q and where each of the p—q inputs in Il are
`connected to all of the q outputs and each of the q inputs in
`I2 are connected to a single but distinct output. It can be
`shown that every p><q fat-and-slim concentrator is a sparse
`crossbar concentrator with a minimum number of cross-
`
`points for any 1§p§q
`
`Petitioner Huawei - Exhibit 1007, p. 9
`
`Petitioner Huawei - Exhibit 1007, p. 9
`
`

`

`US 2005/0141804 A1
`
`Jun. 30, 2005
`
`[0034] A block diagram of an embodiment of three-stage
`group connector 300 constructed using crossbars and con-
`centrators is illustrated in FIG. 3. Because the structure of
`
`the number of crosspoints in a non-
`[0039] Therefore,
`blocking N1><N2 v(m,n1,r1,n2,r2) network can be calculated
`as follows:
`
`the group connector 300 is determined by three parameters
`m, n, and r, it is denoted by g(m,n,r). In particular, the group
`connector 300 includes r n><m crossbar switch modules
`
`302(1)-302(r) in an input stage 304, m r><r crossbar switch
`modules 306(1)-306(m) in a middle stage 308, and r m><n
`concentrator switch modules 310(1)-310(r) in an output
`stage 312, wherein n=nr and min and n is the group size.
`Note that the structure of the group connector 300 is similar
`to that of a three-stage Clos network (m,n,r), except that the
`output stage 312 comprises concentrators instead of crossbar
`switches. The group connector 300 is non-blocking for
`connecting any n inputs to a group at the output of the
`connector if miZn—l.
`
`In general, the number of crosspoints of a network
`[0035]
`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 n1><n2 crossbar has nln2 crosspoints, while an
`n1><n2 concentrator has (nl—n2+1)n2 crosspoints. Thus, for a
`non-blocking group connector g(m,n,r), the number of cros-
`spoints is:
`
`mm+mrr+r(m—n+1)n
`
`(1)
`
`Non-Blocking Multistage Group Connectors
`
`the three-stage group
`[0036] To reduce network cost,
`connector 300 illustrated in FIG. 3 can be generalized to a
`non-blocking multistage group connector as follows. First, a
`p><q
`fat-and-slim concentrator
`is implemented using a
`(p—q)><q crossbar switch and q 2x1 switches. A 9x4 fat-and-
`slim concentrator 400 implemented in this manner is illus-
`trated in FIG. 4. The concentrator 400 includes a 5x4
`
`crossbar switch 402 and four 2x1 switches 404(1)-404(4).
`
`the non-blocking multistage group
`[0037] To construct
`connector, every crossbar switch module 302(1)-302(r),
`306(1)-306(m), in every stage 304, 308, 312, of the three-
`stage group connector 300 is recursively replaced by a
`three-stage group connector g(m,n,r) 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 N1><N2 crossbar to
`achieve a minimum cost, where N1 is not necessarily equal
`to N2.
`
`[0038] FIG. 5 is a block diagram of a general N1><N2
`three-stage network 500 with five parameters, denoted v(m,
`n1,r1,n2,r2), where N1=n1><r1 and N2=n2><r2. In particular, the
`network 500 includes a first stage 502, a second stage 504,
`and a third stage 506. The first stage 502 comprises r1
`crossbar switches 508(1)-508(r), the second stage 504 com-
`prises m crossbar switches 510(1)-510(m), and the third
`stage 506 comprises r2 crossbar switches 512(1)-512(r2). A
`condition that must be met for the network 500 to be
`
`the
`non-blocking for any one-to-one connections is that
`number of middle stage switches m satisfies the following:
`
`m§(n1+n2—1)
`
`(2)
`
`nlxmxr1+m><r1><r2+m><n1><r2=
`(N1+N2)m+m><r1><r2 =m(r1><r2+N1+N2)=
`
`(”1 +”2 —1)((N1><N2)/(”1><”2)+N1 +N2)
`
`It can be shown that when
`[0040]
`”1:”2=((N1XN2)/(N1+N2)) 1/2
`
`(3)
`
`(4)
`
`three-stage non-blocking network
`an N1><N2
`[0041]
`achieves the minimum number of crosspoints, which is:
`
`2(N1+N2)[2((N1XN2)/(N1+N2))1/2‘1]
`
`(5)
`
`[0042] Thus, for any N1><N2 crossbar switch, based on
`equations (4) and (2), an N1><N2 three-stage non-blocking
`network with a minimum cost can be constructed.
`
`In the following, a nine-stage group connector is
`[0043]
`used as an example to illustrate how to calculate the cros-
`spoints of a non-blocking multistage group connector. A
`similar method can be used for any 3k-stage non-blocking
`group connector with k>1,
`
`[0044] Anine-stage group connector is realized by replac-
`ing 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 r n><m switches,
`after replacing each such switch with an n><m three-stage
`network, according to equation (5), there are
`r[2(n+m)(2((nxn)/(n+m))1/2— 1)]=2r(2(nxm(n+m))1/2—
`n—m)
`
`(6)
`
`crosspoints in the first three stages of the nine-stage
`[0045]
`group connector.
`
`[0046] Similarly, since the second stage of the original
`three-stage network consists of m r><r switches, after replac-
`ing each such switch with an r><r
`three-stage network,
`according to equation (5), there are
`
`m[2®+r)(2((rxr)/(r+r))1/2—1)]=4mr(2r 1/2—1
`
`(7)
`
`crosspoints in stages four, five, and six of the
`[0047]
`nine-stage group connector.
`
`[0048] Finally, since the last stage of the original three-
`stage network consists of r (m—n)><n switches and rn 2x1
`switches, after replacing each (m—n)><n switch with an
`(m—n)xn three-stage group connector, according to equation
`(5), there are
`
`r[2(m—n+n)(2(((m—n)n)/(m—n+n))1/2—1)+2n]=2r(2(m><
`n(m—n))1/2+n—m)
`
`(8)
`
`crosspoints in the last three stages of the nine-stage
`[0049]
`group connector. By combining equations (6), (7), and (8),
`the total number of crosspoints of the nine-stage group
`connector is
`
`2r(2(nxm n+m))1/2—n—m)+4mr((2r)1/2—1)+2r(2(m><
`n(m—n))1/ +n—m)=4r[m><n(m+n)+m><n(m—n)+m(2r)1/
`2—2m]
`
`(9)
`
`[0050] Under certain conditions, a three-stage group con-
`nector can be recursively transformed into a multi-stage
`group connector consisting of 2x2 switches.
`
`Petitioner Huawei - Exhibit 1007, p. 10
`
`Petitioner Huawei - Exhibit 1007, p. 10
`
`

`

`US 2005/0141804 A1
`
`Jun. 30, 2005
`
`Rearrangeably Non-Blocking Group Connectors
`
`[0051] A 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.
`
`[0056] Since a three-stage non-blocking group connector
`g(m, n, r) has
`rxnxm+mxrxr+r(m—n+1)n
`
`crosspoints, the savings in crosspoints by using an
`[0057]
`N><N non-blocking group connector as opposed to a permu-
`tation network is
`
`Rearrangeably Non-Blocking Three-Stage Group
`Connectors
`
`rxn(n—1)=N(n—1)
`
`(13)
`
`[0052] A three-stage g(m,n,r) 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 min. It will be recognized that a three-stage Clos
`network is rearrangeably non-blocking for permutations if
`min. In a g(m,n,r), 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 n><n 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
`rxnxm+m><r><r
`
`(10)
`
`Rearrangeably Non-Blocking Multistage Group
`Connectors
`
`[0053] Similar to permutation networks, the rearrangeably
`non-blocking three-stage group connector can be general-
`ized 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
`
`16x16 group connector of group size 4, designated in FIG.
`7B by a reference numeral 700, from a 16x16 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 N><N (N=2m) group connector of group size 2k
`(k<m) can be obtained by setting all switches in stages
`2m—2, 2m—3,
`.
`.
`.
`, 2m—(k+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.
`
`[0054] Clearly, an N><N multi-stage group connector of
`size 2k has crosspoints
`(2 log N—1—k)(N/2><2><2)
`
`(11)
`
`Network Cost Comparisons
`
`[0055] The 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 v (m, n, r), the number of
`crosspoints is
`rxnxm+mxrxr+rxmxn
`
`(12)
`
`[0058] Since a three-stage rearrangeably non-blocking
`group connector has
`rxnxm+m><rxr
`
`crosspoints, compared with a three-stage permuta-
`[0059]
`tion network, the savings in crosspoints using a three-stage
`n><n rearrangeably non-blocking group connector is
`rxn2=N><n
`
`(14)
`
`[0060] A multi-stage group connector will now be con-
`sidered. 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 cros-
`spoints for a nine-stage group connector, compared with a
`nine-stage permutation network is
`
`l
`2r(2(n Xm(n + m))§ — n — m) — 2r(2(m ><n(—n))% + n — m) =
`
`(15)
`
`2r[2(n(2n—1)(3n—1))i—3n+1]—
`
`2r[2(n(2n—1)(n —1))i —m +1]:
`
`4r[(n(2n — l)(3n _1))i —((2n — l)(n —1))i _ n
`
`[0061] Finally, since a n><n Benes network has
`(2 log N—1)(N/2><2><2)=2N(2 log N—1)
`
`crosspoints, while an N><N multi-stage rearrange-
`[0062]
`able group connector of size 2k has
`(2 log N—1—k)(N/2><2><2)
`
`crosspoints, the savings in crosspoints by using an
`[0063]
`N><N multi-stage group connector of size 2k is
`2.ka
`
`(1 6)
`
`[0064] From 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 1024x1024 Benes network with a
`group connector of the same size, 8/19, or 42%, of the
`crosspoints can be eliminated.
`
`In summary, a class of interconnection networks
`[0065]
`called group connectors have been described which have
`important application in constructing client-server connec-
`tions, 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
`
`Petitioner Huawei - Exhibit 1007, p. 11
`
`Petitioner Huawei - Exhibit 1007, p. 11
`
`

`

`US 2005/0141804 A1
`
`Jun. 30, 2005
`
`replacing each of the r r><m crossbar switch modules of the
`first stage with a three-stage group connector of the
`same size as the r><m crossbar switch module; and
`
`replacing each of the m r><r crossbar switch modules of the
`second stage with a three-stage group connector of the
`same size as the r><r crossbar switch module.
`
`12. The method of claim 11 further comprising:
`
`implementing each concentrator of the third stage using a
`p><q fat-and-slim concentrator.
`13. An N><N multi-stage group connector with N inputs
`and N outputs, wherein the N outputs are divided into r
`output groups, each group including n outputs such that
`r=N/n, the connector comprising:
`
`a first portion comprising r n><m three-stage group con-
`nectors, wherein min—1;
`
`a second portion comprising m r><r
`connectors; and
`
`three-stage group
`
`a third portion comprising r p><q fat and slim concentrator
`switch modules.
`
`14. The group connector of claim 13 wherein each of the
`concentrators includes a minimum number of crosspoints.
`15. The group connector of claim 13 wherein each of the
`concentrators includes a maXimum of (m—n+1)n cross-
`points.
`16. The group connector of claim 13 wherein min.
`17. The group connector of claim 13 wherein the group
`connector is non-blocking.
`18. The group connector of claim 13 wherein m§2n—1.
`19. An N><N two-stage group connector with N inputs and
`N outputs, wherein the N outputs are divided into r output
`groups, each group including n outputs such that r=N/n, the
`group connector comprising:
`
`a first stage comprising r n><m crossbar switch modules;
`and
`
`a second stage comprising m r><r crossbar switch modules;
`
`wherein m is equal to 2n—1.
`20. The group connector of claim 19 wherein the group
`connector is non-blocking.
`21. Amethod of constructing an N><N group connector of
`group size 2k from an N><N Benes network,
`the method
`comprising:
`
`. 2m—(k+1)
`.
`setting all switches in stages 2m—2, 2m—3, .
`of the Benes network to straight connections; and
`
`removing all switches in stages 2m—2, 2m—3, .
`1) of the Benes network.
`22. The method of claim 21 wherein N is equal to 2m.
`23. The method of claim 21 wherein k is less than or equal
`to m.
`
`. 2m—(k+
`
`.
`
`embodiments described herein are particularly useful for
`ingress routers for DWDM networks operating in slot trans-
`mission mode, in which input packets with the same desti-
`nation are assembled into larger, fixed-length frames, each
`corresponding to a time-slot, at ingress line cards (“ILCs”).
`All N 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.
`
`It is believed that the operation and construction of
`[0066]
`the present invention will be apparent from the Detailed
`Description set forth above. While the exemplary embodi-
`ments of the invention shown and described have been
`
`characterized as being preferred, it should be readily under-
`stood 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.
`What is claimed is:
`
`1. An N><N three-stage group connector with N inputs and
`N outputs, wherein the N outputs are divided into r output
`groups, each group including n outputs such that r=N/n, the
`connector comprising:
`
`a first stage comprising r n><m crossbar switch modules;
`
`a second stage comprising m r><r crossbar switch modules;
`and
`
`a third stage comprising r m><n concentrator switch mod-
`ules.
`
`2. The group connector of claim 1 wherein the first stage
`comprises an input stage.
`3. The group connector of claim 1 wherein the third stage
`comprises an output stage.
`4. The group connector of claim 1 wherein the second
`stage is a middle stage disposed between the first and third
`stages.
`5. The group connector of claim 1 wherein each of the
`concentrators includes a minimum number of crosspoints.
`6. The group connector of claim 1 wherein each of the
`concentrators is of a type selected from a group consisting
`of a fat-and-slim concentrator and a banded concentrator.
`
`7. The group connector of claim 1 wherein each of the
`concentrators includes a maXimum of (m—n+1)n cross-
`points.
`8. The group connector of claim 1 wherein min.
`9. The group connector of claim 1 wherein the group
`connector is non-blocking.
`10. The group connector of claim 1 wherein m§2n—1.
`11. A method of constructing an N1><N2 multistage group
`connector with N1 inputs and N2 outputs from a three-stage
`group connector, wherein the three-stage group connector
`comprises a first stage comprising r n><m crossbar switch
`modules, a second stage comprising m r><r crossbar switch
`modules, and a third stage comprising r m><n concentrator
`switch modules, the method comprising:
`
`24. The method of claim 21 wherein N is equal to 2m and
`k is less than or equal to m.
`*
`*
`
`*
`
`*
`
`*
`
`Petitioner Huawei - Exhibit 1007, p. 12
`
`Petitioner Huawei - Exhibit 1007, p. 12
`
`