M-0042 US
`
`FULLY CONNECTED GENERALIZED STRICTLY NONBLOCKING
`
`MULTI-LINK MULTI-STAGE NETWORKS
`
`Venkat Konda
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0037USentitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS"by Venkat Kondaassigned to the same
`
`10
`
`assignee as the current application,filed concurrently.
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0038USentitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE NETWORKS"by Venkat Konda assigned
`
`to the same assignee as the current application, filed concurrently.
`
`15
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0039USentitled "FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTI
`
`STAGE NETWORKS"by Venkat Kondaassigned to the same assignee as the current
`
`application, filed concurrently.
`
`20
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0040USentitled "FULLY CONNECTED
`
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS"by Venkat
`
`Konda assigned to the same assignee as the current application, filed concurrently.
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0041USentitled "FULLY CONNECTED
`
`GENERALIZED FOLDED MULTI-STAGE NETWORKS"by Venkat Kondaassigned
`
`to the same assignee as the current application, filed concurrently.
`
`-|-
`
`Page 1 of 107
`
`FLEX LOGIX EXHIBIT 1023
`
`Page 1 of 107
`
`FLEX LOGIX EXHIBIT 1023
`
`

`

`M-0042 US
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0045USentitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED NETWORKS"by Venkat Kondaassigned to
`
`the same assignee as the current application, filed concurrently.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi-link multi-stage
`
`network V,,,,,,(N,d,s5) having inverse Benes connection topologyof five stages with N =
`
`8, d= 2 and s=3, strictly nonblocking networkfor arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`10
`
`FIG. 1B is a diagram 100B of an exemplary symmetrical multi-link multi-stage
`
`network V.“wing ON» d,5)
`
`(having a connection topology built using back-to-back Omega
`
`Networks) of five stages with N = 8, d = 2 and s=3, strictly nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1C is a diagram 100C of an exemplary symmetrical multi-link multi-stage
`
`15
`
`network Vatin. (N,@,5) having an exemplary connection topology of five stages with N =
`
`8, d= 2 and s=3, strictly nonblocking network for arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG. 1D is a diagram 100D of an exemplary symmetrical multi-link multi-stage
`
`network V“dineN,@,S) having an exemplary connection topology of five stages with N =
`
`20
`
`8, d= 2 and s=3, strictly nonblocking networkfor arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG, 1E is a diagram 100E of an exemplary symmetrical multi-link multi-stage
`
`network V“ning (N.d,5) (having a connection topology called flip network and also known
`
`as inverse shuffle exchange network) of five stages with N = 8, d = 2 and s=3, strictly
`
`25
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`Page 2 of 107
`
`Page 2 of 107
`
`

`

`M-0042 US
`
`FIG, 1F is a diagram 100F of an exemplary symmetrical multi-link multi-stage
`
`network V_,,,(N,d,s) having Baseline connection topology of five stages with N = 8, d
`
`= 2 and s=3, strictly nonblocking network for arbitrary fan-out multicast connections, in
`
`accordance with the invention.
`
`FIG. 1G is a diagram 100G of an exemplary symmetrical multi-link multi-stage
`
`network V_,,,,(N.d,s) having an exemplary connection topology of five stages with N =
`
`8, d= 2 and s=3, strictly nonblocking network for arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG. 1H is a diagram 100H of an exemplary symmetrical multi-link multi-stage
`
`10
`
`network V_,,,,(NV.d,s) having an exemplary connection topology of five stages with N =
`
`8, d= 2 and s=3, strictly nonblocking networkfor arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG. 1I is a diagram 1001 of an exemplary symmetrical multi-link multi-stage
`
`network V_,,.(N,d,s) (having a connection topology built using back-to-back Banyan
`
`15
`
`Networks or back-to-back Delta Networks or equivalently back-to-back Butterfly
`
`networks) of five stages with N = 8, d = 2 and s=3, strictly nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1J is a diagram 100J of an exemplary symmetrical multi-link multi-stage
`
`network V,,,,,(N,d,s) having an exemplary connection topology of five stages with N =
`
`20
`
`8, d= 2 and s=3, strictly nonblocking networkfor arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG. 1K is a diagram 100K of a general symmetrical multi-link multi-stage
`network Vmiink (N,d,s) with (2xlog, N)-1 stages with s=3,
`strictly nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`25
`
`FIG, 1A1 is a diagram 100A1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,,(N,,N,,d.s) having inverse Benes connection topology of five
`
`Page 3 of 107
`
`Page 3 of 107
`
`

`

`M-0042 US
`
`stages with N; = 8, No = p* Ni = 24 where p = 3, d = 2 and s=3, strictly nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1B1 is a diagram 100B1 of an exemplary asymmetrical multi-link
`
`multi-stage network V_,,,,(N,,N..d,s) (having a connection topology built using back-
`
`to-back Omega Networks) of five stages with N; = 8, No = p* N; = 24 where p=3,d=2
`
`and s=3, strictly nonblocking networkfor arbitrary fan-out multicast connections.
`
`FIG, 1C1 is a diagram 100C1 of an exemplary asymmetrical multi-link multi-
`stage network V,7HtineN,,N,,d,s) having an exemplary connection topology of five
`
`stages with N; = 8, No = p* N; = 24 where p = 3, d = 2 ands=3, strictly nonblocking
`
`10
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG, 1D1 is a diagram 100D1 of an exemplary asymmetrical multi-link multi-
`
`stage networkV,,,,,,(N,,N,,d,s) having an exemplary connection topology of five stages
`
`with N; = 8, Nz = p* N; = 24 where p = 3, d = 2 and s=3, strictly nonblocking network
`
`for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1E1 is a diagram 100E1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,,,(N,,N,,d,s) (having a connection topology called flip network and
`
`also knownas inverse shuffle exchange network) of five stages with N, = 8, No = p* Ny
`
`= 24 where p = 3, d = 2 and s=3, strictly nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`20
`
`FIG, 1F1 is a diagram 100F1 of an exemplary asymmetrical multi-link multi-stage
`
`network V,,,,,,(N,,N,,d,s5) having Baseline connection topology of five stages with N; =
`
`8, Nz = p* N; = 24 where p = 3, d= 2 and s=3, strictly nonblocking network for arbitrary
`
`fan-out multicast connections, in accordance with the invention.
`
`FIG. 1G1 is a diagram 100G1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,,(N,,N,,d,s) having an exemplary connection topology of five
`
`stages with N; = 8, No = p* N; = 24 where p = 3, d = 2 and s=3, strictly nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`4.
`
`Page 4 of 107
`
`Page 4 of 107
`
`

`

`M-0042 US
`
`FIG. 1H1 is a diagram 100H1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,(N,,N.,,d,s) having an exemplary connection topology of five
`
`stages with N; = 8, No = p* N; = 24 where p = 3, d = 2 and s=3, strictly nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 111 is a diagram 10011 of an exemplary asymmetrical multi-link multi-stage
`
`network V,,,,.(N,,N,.d,s5)
`
`(having a connection topology built using back-to-back
`
`Banyan Networks or back-to-back Delta Networks or equivalently back-to-back Butterfly
`
`networks) of five stages with N; = 8, Nz = p* N; = 24 where p = 3, d= 2 and s=3, strictly
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`10
`
`invention.
`
`FIG. 1J1 is a diagram 100J1 of an exemplary asymmetrical multi-link multi-stage
`
`network V_,,,,(N,,N,,d,5) having an exemplary connection topology of five stages with
`
`N; = 8, No = p* Ni = 24 where p = 3, d = 2 and s=3, strictly nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`15
`
`FIG. 1K1 is a diagram 100K1 of a general asymmetrical multi-link multi-stage
`network V,,,,(N,,N,,.d,5) with (2xlog, N)—1 stages with N, = p* No and s=3, strictly
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1A2 is a diagram 100A2 of an exemplary asymmetrical multi-link multi-
`
`20
`
`stage network V,,,,(N,,N,,d,s) having inverse Benes connection topology of five
`
`stages with N. = 8, N; = p* No= 24, where p = 3, d = 2 and s=3, strictly nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1B2 is a diagram 100B2 of an exemplary asymmetrical multi-link multi-
`
`stage network V__,,,(V,,N,,d,s5) (having a connection topology built using back-to-back
`
`25
`Omega Networks) of five stages with No = 8, Ni = p* No= 24, where p = 3, d=2and
`
`s=3,
`
`strictly nonblocking network for arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`Page 5 of 107
`
`Page 5 of 107
`
`

`

`M-0042 US
`
`FIG, 1C2 is a diagram 100C2 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,(N,,N.,,d,s) having an exemplary connection topology of five
`
`stages with Nz = 8, N; = p* No= 24, where p = 3, d = 2 and s=3, strictly nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1D2 is a diagram 100D2 of an exemplary asymmetrical multi-link multi-
`
`stage network V__,,(N,,N,,d,s) having an exemplary connection topology of five stages
`
`with No = 8, N; = p* No= 24, where p = 3, d = 2 and s=3, strictly nonblocking network
`
`for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1E2 is a diagram 100E2 of an exemplary asymmetrical multi-link multi-
`
`10
`
`stage network V,,,,,(N,,N,,d,5) (having a connection topology called flip network and
`
`also knownas inverse shuffle exchange network) of five stages with No = 8, Ni = p* No
`
`= 24, where p = 3, d = 2 and s=3, strictly nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`FIG. 1F2 is a diagram 100F2 of an exemplary asymmetrical multi-link multi-stage
`
`15
`
`network V,,,,.(N,,N,,d,s) having Baseline connection topologyof five stages with N> =
`
`8, Ni = p* No = 24, where p = 3, d = 2 and s=3, strictly nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1G2 is a diagram 100G2 of an exemplary asymmetrical multi-link multi-
`
`stage network V_,,,(N,,N,,d,s) having an exemplary connection topology of five
`
`20
`
`stages with No = 8, N; = p* No = 24, where p = 3, d = 2 and s=3, strictly nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1H2 is a diagram 100H2 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,,(N,,N.,,d,s) having an exemplary connection topology of five stages
`
`with No = 8, Ni; = p* No= 24, where p = 3, d = 2 and s=3, strictly nonblocking network
`
`25
`
`for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG, 112 is a diagram 10012 of an exemplary asymmetrical multi-link multi-stage
`
`network V.miink (N,,N,.d,s)
`
`(having a connection topology built using back-to-back
`
`-6-
`
`Page 6 of 107
`
`Page 6 of 107
`
`

`

`M-0042 US
`
`Banyan Networks or back-to-back Delta Networks or equivalently back-to-back Butterfly
`
`networks) of five stages with No = 8, Ni = p* No= 24, where p = 3, d = 2 and s=3,
`
`strictly nonblocking network for arbitrary fan-out multicast connections, in accordance
`
`with the invention.
`
`FIG. 1J2 is a diagram 100J2 of an exemplary asymmetrical multi-link multi-stage
`
`network V,,,,(N,,N,,d,s) having an exemplary connection topology of five stages with
`
`No = 8, Ni = p* No= 24, where p = 3, d= 2 and s=3, strictly nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1K2 is a diagram 100K2 of a general asymmetrical multi-link multi-stage
`network V,,,,,(N,,N,.d.s) with (2xlog, N)-1 stages with Ny = p* N, and s=3, strictly
`
`10
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2A is high-level
`
`flowchart of a scheduling method according to the
`
`invention, used to set up the multicast connections in all the networks disclosed in this
`
`15
`
`invention.
`
`DETATLED DESCRIPTION OF THE INVENTION
`
`The present invention is concerned with the design and operation of large scale
`
`crosspoint reduction using arbitrarily large multi-link multi-stage switching networks for
`
`20
`
`broadcast, unicast and multicast connections. Particularly multi-link multi-stage networks
`
`with stages more than three and radices greater than or equal to two offer large scale
`
`crosspoint reduction when configured with optimallinks as disclosed in this invention.
`
`Whena transmitting device simultaneously sends information to more than one
`
`receiving device, the one-to-many connection required between the transmitting device
`
`and the receiving devicesis called a multicast connection. A set of multicast connections
`
`is referred to as a multicast assignment. When a transmitting device sends information to
`
`one receiving device, the one-to-one connection required between the transmitting device
`
`and the receiving device is called unicast connection. When a transmitting device
`-7-
`
`Page 7 of 107
`
`Page 7 of 107
`
`

`

`M-0042 US
`
`simultaneously sends informationto all the available receiving devices, the one-to-all
`
`connection required between the transmitting device and the receiving devicesis called a
`
`broadcast connection.
`
`In general, a multicast connection is meant to be one-to-many connection, which
`
`includes unicast and broadcast connections. A multicast assignment in a switching
`
`network is nonblocking if any of the available inlet links can always be connected to any
`
`of the available outlet links.
`
`In certain multi-link multi-stage networks of the type described herein, any
`
`connection request of arbitrary fan-out,i.e. from an inlet link to an outlet link or to a set
`
`10
`
`of outlet links of the network, can be satisfied without blocking if necessary by
`
`rearranging someof the previous connection requests. In certain other multi-link multi-
`
`stage networksof the type described herein, any connection request of arbitrary fan-out,
`
`i.e. from an inletlink to an outlet link orto a set of outlet links of the network, can be
`
`satisfied without blocking with never needing to rearrange any of the previous connection
`
`15
`
`requests.
`
`In certain multi-link multi-stage networks of the type described herein, any
`
`connection request of unicast from an inlet link to an outlet link of the network, can be
`
`satisfied without blocking if necessary by rearranging some of the previous connection
`
`requests. In certain other multi-link multi-stage networks of the type described herein,
`
`any connection request of unicast from an inlet link to an outlet link of the network, can
`
`be satisfied without blocking with never needing to rearrange any of the previous
`
`connection requests.
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`25
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks V(N,,N,.d,s5) with numerous connection
`
`topologies and the scheduling methods are described in detail in U.S. Provisional Patent
`
`Application, Attorney Docket No. M-0037 US that is incorporated by reference above.
`
`Page 8 of 107
`
`Page 8 of 107
`
`

`

`M-0042 US
`
`2) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks V,,,(N,,N,,d,s) with numerous
`
`connection topologies and the scheduling methodsare described in detail in U.S.
`
`Provisional Patent Application, Attorney Docket No. M-0038 US that is incorporated by
`
`reference above.
`
`3) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`Ving (N1»N>,d,5) and generalized folded multi-link multi-stage networks
`
`Vjotd—mlink (N,,N,.d,s) with numerous connection topologies and the scheduling methods
`
`10
`
`are described in detail in U.S. Provisional Patent Application, Attorney Docket No. M-
`
`0039 USthat is incorporated by reference above.
`
`4) Strictly and rearrangeably nonblockingfor arbitrary fan-out multicast and
`
`unicast for generalized multi-link butterflyfat tree networks Vj...44(N,.N.,d,5) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`15
`
`U.S. Provisional Patent Application, Attorney Docket No. M-0040 USthatis
`
`incorporated by reference above.
`
`5) Strictly and rearrangeably nonblockingfor arbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks V,.,(N,,N,,d,5) with numerous
`
`connection topologies and the scheduling methodsare described in detail in U.S.
`
`20
`
`Provisional Patent Application, Attorney Docket No. M-0041 USthatis incorporated by
`
`reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N,,N.,,d,s5), generalized
`
`folded multi-stage networks V,,,(N,,N,,d,5), generalized butterfly fat tree networks
`
`V,,(N,,N,,d,5), generalized multi-link multi-stage networks V,,,,,,(N,,N,,d,5),
`
`25
`
`generalized folded multi-link multi-stage networks Vji4_mniine (N,N>,d,5), generalized
`
`multi-link butterfly fat tree networks V,,j,,4,(N,,N.,d,s), and generalized hypercube
`
`networksV,_,,,(V,,N.,d,s) for s = 1,2,3 or any numberin general, are described in
`
`-9-
`
`Page 9 of 107
`
`Page 9 of 107
`
`

`

`M-0042 US
`
`detail in U.S. Provisional Patent Application, Attorney Docket No. M-0045 USthatis
`
`incorporated by reference above.
`
`Symmetric SNB Embodiments:
`
`Referring to FIG, 1A, in one embodiment, an exemplary symmetrical multi-link
`
`multi-stage network 100A with five stages of twenty switches for satisfying
`
`communication requests, such as setting up a telephone call or a data call, or a connection
`
`between configurable logic blocks, between an input stage 110 and outputstage 120 via
`
`middle stages 130, 140, and 150 is shown whereinput stage 110 consists of four, two by
`
`10
`
`six switches IS1-IS4 and output stage 120 consists of four, six by two switches OS1-OS4.
`
`Andall the middle stages namely middle stage 130 consists of four, six by six switches
`
`MS(1,1) - MS(1,4), middle stage 140 consists of four, six by six switches MS(2,1) -
`
`MS(2,4), and middle stage 150 consists of four, six by six switches MS(3,1) - MS(3,4).
`
`Such a network can be operated in strictly non-blocking manner for multicast
`
`15
`
`connections, because the switches in the input stage 110 are of size two bysix, the
`
`switches in output stage 120 are of size six by two, and there are four switches in each of
`
`middle stage 130, middle stage 140 and middle stage 150.
`
`In one embodimentof this network each of the input switches IS 1-IS4 and output
`
`switches O$1-OS4 are crossbar switches. The number of switches of input stage 110 and
`
`20
`
`of output stage 120 can be denoted in general with the variable = , where N is the total
`
`numberofinlet links or outlet links. The numberof middle switches in each middle stage
`
`is denoted by = . The size of each input switch IS1-IS4 can be denoted in general with
`
`the notation d *3d and each output switch OS1-OS4 can be denoted in general with the
`
`notation 3d *d. Likewise, the size of each switch in any of the middle stages can be
`
`25
`
`denoted as 3d *3d. A switch as used herein can be either a crossbar switch, or a network
`
`of switches each of which in turn maybe a crossbar switch or a network of switches. A
`
`symmetric multi-link multi-stage network can be represented with the notation
`
`-10-
`
`Page 10 of 107
`
`Page 10 of 107
`
`

`

`M-0042 US
`
`Vtink (N.d,S), where N represents the total numberofinlet links of all input switches
`
`(for example the links IL1-IL8), d represents the inlet links of each input switch or outlet
`
`links of each output switch, and s is the ratio of number of outgoing links from each
`
`input switch to the inlet links of each input switch. Althoughit is not necessary that there
`
`be the same numberofinlet links IL1-IL8 asthere are outlet links OL1-OL8, ina
`
`symmetrical network they are the same.
`
`Eachofthe - input switches IS1 — IS4 are connected to exactly 3xd switches
`
`in middle stage 130 through 3xd links (for example input switch IS1 is connected to
`
`middle switch MS(1,1) through the links ML(1,1), ML(1,2), and ML(1,3); and also to
`
`10
`
`middle switch MS(1,2) through the links ML(1,4), ML(1,5), and ML(1,6)).
`
`Each ofthe - middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`
`connected from exactly d input switches through 3xd links (for example the links
`
`ML(1,1), ML(1,2), and ML(1,3) are connected to the middle switch MS(1,1) from input
`
`switch IS1, and the links ML(1,10), ML(1,11), and ML(1,12) are connected to the middle
`
`15
`
`switch MS(1,1) from input switch IS2) and also are connected to exactly d switches in
`
`middle stage 140 through 3xd links (for example the links ML(2,1), ML(2,2), and
`
`ML(,3) are connected from middle switch MS(1,1) to middle switch MS(2,1), and the
`
`links ML(2,4), ML(2,5), and ML(2,6) are connected from middle switch MS(1,1) to
`
`middle switch MS(2,3)).
`
`Similarly each ofthe = middle switches MS(2,1) - MS(2,4) in the middle stage
`
`140 are connected from exactly d switches in middle stage 130 through 3xd links (for
`
`example the links ML(2,1), ML(2,2), and ML(2,3) are connected to the middle switch
`
`MS(,1) from middle switch MS(1,1), and the links ML(2,16), ML(2,17), and ML(2,18)
`
`are connected to the middle switch MS(2,1) from middle switch MS(1,3)) and also are
`
`25
`
`connected to exactly d switches in middle stage 150 through 3xd_ links (for example the
`
`links ML(3,1), ML(3,2), and ML(3,3) are connected from middle switch MS(2,1) to
`
`-11-
`
`Page 11 of 107
`
`Page 11 of 107
`
`

`

`M-0042 US
`
`middle switch MS(3,1), and the links ML(3,4), ML(3,5), and ML(3,6) are connected from
`
`middle switch MS(2,1) to middle switch MS(3,3)).
`
`Similarly each of the = middle switches MS(3,1) — MS(3,4) in the middle stage
`
`150 are connected from exactly d switches in middle stage 140 through 3x d links (for
`
`example the links ML(3,1), ML(3,2), and ML(3,3) are connected to the middle switch
`
`MS(3,1) from middle switch MS(2,1), and the links ML(3,16), ML(@,17), and ML(3,18)
`
`are connected to the middle switch MS(3,1) from middle switch MS(2,3)) and also are
`
`connected to exactly d output switches in output stage 120 through 3xd links (for
`
`example the links ML(4,1), ML(4,2), and ML(4,3) are connected to output switch OS1
`
`10
`
`from Middle switch MS(3,1), and the links ML(4,10), ML(4,11), and ML(4,12) are
`
`connected to output switch OS2 from middle switch MS(3,1)).
`
`Eachof the - output switches OS1 —OS4 are connected from exactly 3xd
`
`switches in middle stage 150 through 3xd links (for example output switch OS1 is
`
`connected from middle switch MS(3,1) through the links ML(4,1), ML(4,2), and
`
`15
`
`ML(4,3), and output switch OS1 is also connected from middle switch MS(3,2) through
`
`the links ML(4,10), ML(4,11) and ML(4,12)).
`
`Finally the connection topology of the network 100A shownin FIG. 1A is known
`
`to be back to back inverse Benes connection topology.
`
`Referring to FIG. 1B, in another embodimentof network V,,,,,,(N,d,s), an
`
`20
`
`exemplary symmetrical multi-link multi-stage network 100B with five stages of twenty
`
`switches for satisfying communication requests, such as setting up a telephonecall or a
`
`data call, or a connection between configurable logic blocks, between an input stage 110
`
`and output stage 120 via middle stages 130, 140, and 150 is shown where input stage 110
`
`consists of four, two by six switches IS1-IS4 and output stage 120 consists of four, six by
`
`25
`
`two switches OS1-OS4. Andall the middle stages namely middle stage 130 consists of
`
`four, six by six switches MS(1,1) - MS(1,4), middle stage 140 consists of four, six by six
`
`switches MS(2,1) - MS(@,4), and middle stage 150 consists of four, six by six switches
`
`MS@G,1) - MS@G,4).
`
`-12-
`
`Page 12 of 107
`
`Page 12 of 107
`
`

`

`M-0042 US
`
`Such a network can be operated in strictly non-blocking mannerfor multicast
`
`connections, because the switches in the input stage 110 are of size two bysix, the
`
`switches in output stage 120 are of size six by two, and there are four switches in each of
`
`middle stage 130, middle stage 140 and middle stage 150.
`
`In one embodimentof this network each of the input switches IS1-IS4 and output
`
`switches OS1-OS4are crossbar switches. The numberof switches of input stage 110 and
`
`of output stage 120 can be denoted in general with the variable - , where N is the total
`
`numberofinlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by * . The size ofeach input switch IS1-IS4 can be denoted in general with
`
`10
`
`the notation d*3d and each output switch OS1-OS4 can be denoted in general with the
`
`notation 3d *d. Likewise, the size of each switch in any of the middle stages can be
`
`denoted as 3d *3d . A switch as used herein can be either a crossbar switch, or a network
`
`of switches each of which in turn may be a crossbar switch or a network of switches. The
`
`symmetric multi-link multi-stage network of FIG. 1B is also the network of the type
`
`15
`
`Vtink (N.d,5), where N represents the total numberofinlet links of all input switches
`
`(for example the links IL1-IL8), d represents the inlet links of each input switch or outlet
`
`links of each output switch, and s is the ratio of numberof outgoing links from each
`
`input switch to the inlet links of each input switch. Althoughit is not necessary that there
`
`be the same numberof inlet links IL1-I[L8 as there are outlet links OL1-OL8, ina
`
`20
`
`symmetrical network they are the same.
`
`Eachofthe - input switches IS1 — IS4 are connected to exactly 3xd switches
`
`in middle stage 130 through 3xd links (for example input switch IS1 is connected to
`
`middle switch MS(1,1) through the links ML(1,1), ML(1,2), and ML(1,3); and also to
`
`middle switch MS(1,2) through the links ML(1,4), ML(1,5), and ML(1,6)).
`
`25
`
`Eachofthe - middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`
`connected from exactly d input switches through 3xd links (for example the links
`
`ML(1,1), ML(1,2), and ML(1,3) are connected to the middle switch MS(1,1) from input
`-13-
`
`Page 13 of 107
`
`Page 13 of 107
`
`

`

`M-0042 US
`
`switch IS1, and the links ML(1,13), ML(1,14), and ML(1,15) are connected to the middle
`
`switch MS(1,1) from input switch I[S3) and also are connected to exactly d switches in
`
`middle stage 140 through 3xd links (for example the links ML(2,1), ML(2,2), and
`
`ML(2,3) are connected from middle switch MS(1,1) to middle switch MS(2, 1); and the
`
`links ML(2,4), ML(2,5), and ML(2,6) are connected from middle switch MS(1,1) to
`
`middle switch MS(2,2)).
`
`Similarly each of the = middle switches MS(2,1) — MS(2,4) in the middle stage
`
`140 are connected from exactly d switches in middle stage 130 through 3xd links (for
`
`example the links ML(2,1), ML(2,2), and ML(2,3) are connected to the middle switch
`
`10
`
`MS(2,1) from middle switch MS(1,1), and the links ML(2,13), ML@,14), and ML(, 15)
`
`are connected to the middle switch MS(2,1) from middle switch MS(1,3)) and also are
`
`connected to exactly d switches in middle stage 150 through 3xd_links (for example the
`
`links ML(3,1), ML(3,2), and ML(3,3) are connected from middle switch MS(2,1) to
`
`middle switch MS(3,1), and the links ML(3,4), ML@G,5) and ML(3,6) are connected from
`
`15
`
`middle switch MS(2,1) to middle switch MS(3,2)).
`
`Similarly each of the - middle switches MS(3,1) — MS(3,4) in the middle stage
`
`150 are connected from exactly d switches in middle stage 140 through 3x d links (for
`
`example the links ML(3,1), ML(3,2), and ML(3,3) are connected to the middle switch
`
`MS(3,1) from middle switch MS(2,1), and the links ML(3,13), ML(3,14), and ML(3,15)
`
`20
`
`are connected to the middle switch MS(3,1) from middle switch MS(2,3)) and also are
`
`connected to exactly d output switches in output stage 120 through 3xd links (for
`
`example the links ML(4,1), ML(4,2), and ML(4,3) are connected to output switch OS1
`
`from Middle switch MS(3,1), and the links ML(4,4), ML(4.5), and ML(4,6) are
`
`connected to output switch OS2 from middle switch MS(3,1)).
`
`25
`
`Eachofthe = output switches OSI — OS4 are connected from exactly 3xd
`
`switches in middle stage 150 through 3xd links (for example output switch OS1 is
`
`connected from middle switch MS(3,1) through the links ML(4,1), ML(4,2), and
`
`-14-
`
`Page 14 of 107
`
`Page 14 of 107
`
`

`

`M-0042 US
`
`ML(¢4,3), and output switch OS1 is also connected from middle switch MS(3,3) through
`
`the links ML(4,13), ML(4,14), and ML(4,15)).
`
`Finally the connection topology of the network 100B shownin FIG. 1B is known
`
`to be back to back Omega connection topology.
`
`Referring to FIG. 1C, in another embodimentof network V,,,,,,(N,d, 5), an
`
`exemplary symmetrical multi-link multi-stage network 100C with five stages of twenty
`
`switchesfor satisfying communication requests, such as setting up a telephonecall or a
`
`data call, or a connection between configurable logic blocks, between an input stage 110
`
`and output stage 120 via middle stages 130, 140, and 150 is shown where input stage 110
`
`10
`
`consists of four, two bysix switches IS1-IS4 and output stage 120 consists of four, six by
`
`two switches OS1-OS4. Andall the middle stages namely middle stage 130 consists of
`
`four, six by six switches MS(1,1) - MS(1,4), middle stage 140 consists of four, six by six
`
`switches MS(2,1) - MS(2,4), and middle stage 150 consists of four, six by six switches
`
`MS@G,1) - MS@,4).
`
`15
`
`Such a network can be operated in strictly non-blocking manner for multicast
`
`connections, because the switches in the input stage 110 are of size two bysix, the
`
`switches in output stage 120 are of size six by two, and there are four switches in each of
`
`middle stage 130, middle stage 140 and middle stage 150.
`
`In one embodimentof this network each of the input switches IS1-IS4 and output
`
`20
`
`switches OS1-OS4 are crossbar switches. The number of switches of input stage 110 and
`
`of output stage 120 can be denoted in general with the variable - , where N is the total
`
`numberofinlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by = . The size of each input switch IS1-I$4 can be denoted in general with
`
`the notation d *3d and each output switch OS1-OS4 can be denoted in general with the
`
`notation 3d *d. Likewise, the size of each switch in any of the middle stages can be
`
`denoted as 3d *3d . A switch as used herein can be either a crossbar switch, or a network
`
`of switches each of which in turn may be a crossbar switch or a network of switches. The
`
`symmetric multi-link multi-stage network of FIG. 1C is also the network of the type
`
`-15-
`
`Page 15 of 107
`
`Page 15 of 107
`
`

`

`M-0042 US
`
`Vning (N»d,5), where N represents the total numberofinlet links of all input switches
`
`(for example the links IL1-IL8), d represents the inlet links of each input switch or outlet
`
`links of each output switch, and s is the ratio of number of outgoing links from each
`
`input switch to the inlet links of each input switch. Althoughit is not necessary that there
`
`be the same numberofinlet links IL1-IL8 asthere are outlet links OL1-OL8, ina
`
`symmetrical network they are the same.
`
`Eachofthe - input switches IS1 — IS4 are connected to exactly 3xd switches
`
`in middle stage 130 through 3xd links (for example input switch IS1