M-0041 US
`
`FULLY CONNECTED GENERALIZED FOLDED 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
`
`assignee as the current application,filed concurrently.
`
`10
`
`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 Kondaassigned
`
`to the same assignee as the current application, filed concurrently,
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`15
`
`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.
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`20
`
`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 reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0042USentitled "FULLY CONNECTED
`
`GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULTISTAGE
`
`NETWORKS"by Venkat Konda assigned to the same assignee as the current application,
`
`filed concurrently.
`
`-|-
`
`Page 1 of 157
`
`FLEX LOGIX EXHIBIT 1022
`
`Page 1 of 157
`
`FLEX LOGIX EXHIBIT 1022
`
`

`

`M-0041 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 folded multi-stage
`
`network V,,,(N,d,s) having inverse Benes connection topology of five stages with N =
`
`8, d = 2 and s=2 with exemplary multicast connections, strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`10
`
`multicast connections, in accordance with the invention.
`
`FIG. 1A1 is a diagram 100A1 of an exemplary symmetrical folded multi-stage
`
`network Viota (N,d,2) having Omega connection topologyof five stages with N = 8, d=
`
`2 and s=2 with exemplary multicast connections, strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`15
`
`connections, in accordance with the invention.
`
`FIG. 1A2 is a diagram 100A2 of an exemplary symmetrical folded multi-stage
`
`network V,,,,(N,d,2) having nearest neighbor connection topology of five stages with N
`
`= 8, d = 2 and s=2 with exemplary multicast connections, strictly nonblocking network
`
`for unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`FIG. 1B is a diagram 100B of a general symmetrical folded multi-stage network
`View (N.d,2) with (2x logaN)-1 stages strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections in accordance with the invention.
`
`25
`
`FIG. 1C is a diagram 100C of an exemplary asymmetrical folded multi-stage
`
`network V,,,,(N,,N,,d,2) having inverse Benes connection topology of five stages with
`
`N,=8, No = p* N; = 24 where p = 3, and d = 2 with exemplary multicast connections,
`
`2.
`
`Page 2 of 157
`
`Page 2 of 157
`
`

`

`M-0041 US
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1C1 is a diagram 100C1 of an exemplary asymmetrical folded multi-stage
`
`network V,.,(N,,N.,d,2) having Omega connection topology of five stages with N; =
`
`8, Nz = p* N; = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG, 1C2 is a diagram 100C2 of an exemplary asymmetrical folded multi-stage
`
`network V,.;(N,,N,,d,2) having nearest neighbor connection topology of five stages
`
`10
`
`with N; = 8, No = p* N; = 24 where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1D is a diagram 100D of a general asymmetrical folded multi-stage network
`View (N|,N,,d,2) with No = p* N; and with (2xlog, N)-1 stages strictly nonblocking
`
`15
`
`network for unicast connections and rearrangeably nonblocking networkforarbitrary fan-
`
`out multicast connections in accordance with the invention.
`
`FIG. 1E is a diagram 100E of an exemplary asymmetrical folded multi-stage
`
`network V,,,(N,,N,,d,2) having inverse Benes connection topology of five stages with
`
`20
`
`No =8, Ni = p* No= 24, where p = 3, and d = 2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1E1 is a diagram 100E1 of an exemplary asymmetrical folded multi-stage
`
`network Vrot (N,,N,,d,2) having Omega connection topology of five stages with N2 =
`
`25
`
`8, Ni = p* No= 24, where p = 3, and d = 2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`-3-
`
`Page 3 of 157
`
`Page 3 of 157
`
`

`

`M-0041 US
`
`FIG, 1E2 is a diagram 100E2 of an exemplary asymmetrical folded multi-stage
`
`network V,,,(N,,N,,d,2) having nearest neighbor connection topology of five stages
`
`with No = 8, N; = p* No = 24, where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1F is a diagram 100F of a general asymmetrical folded multi-stage network
`Via (N1,N,,d,2) with Ni = p* No and with (2xlog, N)-1 stages strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking networkforarbitrary fan-
`
`10
`
`out multicast connections in accordance with the invention.
`
`FIG. 2A is a diagram 200A of an exemplary symmetrical folded multi-stage
`
`network V,,,,(N,d,s) having inverse Benes connection topology of five stages with N =
`
`8, d= 2 and s=1 with exemplary unicast connections rearrangeably nonblocking network
`
`for unicast connections, in accordance with the invention.
`
`15
`
`FIG, 2B is a diagram 200B of a general symmetrical folded multi-stage network
`Vioa(N.d.1) with (2xlogiN)-1 stages rearrangeably nonblocking network for unicast
`
`connectionsin accordance with the invention.
`
`FIG. 2C is a diagram 200C of an exemplary asymmetrical folded multi-stage
`
`network V,,,,(N,,N,,d,1) having inverse Benes connection topologyoffive stages with
`
`20
`
`N,; = 8, No = p* N; = 24 where p = 3, and d = 2 with exemplary unicast connections
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`FIG. 2D is a diagram 200D of a general asymmetrical folded multi-stage network
`Vioa(N1,N,,d,1) with No = p* N; and with (2xlog, N)-1 stages rearrangeably
`
`25
`
`nonblocking network for unicast connections in accordance with the invention.
`
`FIG. 2E is a diagram 200E of an exemplary asymmetrical folded multi-stage
`
`network V,,,,(N,,N,,d,l) having inverse Benes connection topologyof five stages with
`
`4.
`
`Page 4 of 157
`
`Page 4 of 157
`
`

`

`M-0041 US
`
`No = 8, N; = p* No = 24, where p = 3, and d = 2 with exemplary unicast connections
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`FIG, 2F is a diagram 200F of a general asymmetrical folded multi-stage network
`Vio (N;,N>,d,1) with Ni = p* No and with (2xlog, N)-1 stages rearrangeably
`
`nonblocking network for unicast connections in accordance with the invention.
`
`FIG. 3A is a diagram 300A of an exemplary symmetrical multi-stage network
`
`V(N,d,s) having inverse Benes connection topology of five stages with N = 8, d = 2 and
`
`s = 1, rearrangeably nonblocking network for unicast connections, in accordance with the
`
`10
`
`invention.
`
`FIG. 3B is a diagram 300B of an exemplary symmetrical multi-stage network
`
`V(N,d,s) (having a connection topology built using back-to-back Omega Networks) of
`
`five stages with N = 8, d = 2 and s = 1, rearrangeably nonblocking network for unicast
`
`connections.
`
`15
`
`FIG. 3C is a diagram 300C of an exemplary symmetrical multi-stage network
`
`V(N,d,s) having an exemplary connection topology of five stages with N = 8, d = 2 and
`
`s=1, rearrangeably nonblocking network for unicast connections, in accordance with the
`
`invention.
`
`FIG. 3D is a diagram 300D of an exemplary symmetrical multi-stage network
`
`20
`
`V(N,d,s) having an exemplary connection topology of five stages with N = 8, d = 2 and
`
`s = 1, rearrangeably nonblocking network for unicast connections, in accordance with the
`
`invention.
`
`FIG. 3E is a diagram 300E of an exemplary symmetrical multi-stage network
`
`V(N,d,s) (having a connection topology called flip network and also known as inverse
`
`25
`
`shuffle exchange network) of five stages with N = 8, d = 2 and s = 1, rearrangeably
`
`nonblocking network for unicast connections.
`
`Page 5 of 157
`
`Page 5 of 157
`
`

`

`M-0041 US
`
`FIG, 3F is a diagram 300F of an exemplary symmetrical multi-stage network
`
`V(N,d,s) having Baseline connection topology offive stages with N = 8,d =2 ands =
`
`1, rearrangeably nonblocking network for unicast connections.
`
`FIG. 3G is a diagram 300G of an exemplary symmetrical multi-stage network
`
`V(N,d,s) having an exemplary connection topology of five stages with N = 8, d= 2 and
`
`s = 1, rearrangeably nonblocking network for unicast connections, in accordance with the
`
`invention.
`
`FIG. 3H is a diagram 300H of an exemplary symmetrical multi-stage network
`
`V(N,d,s) having an exemplary connection topology of five stages with N = 8, d = 2 and
`
`10
`
`s = 1, rearrangeably nonblocking network for unicast connections, in accordance with the
`
`invention.
`
`FIG. 3I is a diagram 3001 of an exemplary symmetrical multi-stage network
`
`V(N,d,s) (having a connection topologybuilt using back-to-back Banyan Networks or
`
`back-to-back Delta Networks or equivalently back-to-back Butterfly networks) of five
`
`15
`
`stages with N = 8, d = 2 and s = 1, rearrangeably nonblocking network for unicast
`
`connections.
`
`FIG. 3J is a diagram 300J of an exemplary symmetrical multi-stage network
`
`V(N,d,s) having an exemplary connection topology of five stages with N = 8, d = 2 and
`
`s = 1, rearrangeably nonblocking network for unicast connections.
`
`20
`
`FIG. 3K is a diagram 300K of a general symmetrical multi-stage network
`V(N,d,s) with (2xlog iN )—-1 stages with s = 1, rearrangeably nonblocking network for
`
`unicast connections in accordance with the invention.
`
`FIG. 3A1 is a diagram 300A1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N.,,d,s) having inverse Benes connection topology of five stages with N; = 8, No
`
`25
`
`= p* N; = 24 where p = 3, d=2 and s = 1, rearrangeably nonblocking network for unicast
`
`connections, in accordance with the invention.
`
`Page 6 of 157
`
`Page 6 of 157
`
`

`

`M-0041 US
`
`FIG, 3B1 is a diagram 300B1 of an exemplary asymmetrical 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 ands = 1,
`
`rearrangeably nonblocking network for unicast connections.
`
`FIG, 3C1 is a diagram 300C1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,s) having an exemplary connection topologyof five stages with N; = 8, N2
`
`= p* N; = 24 where p = 3, d= 2 and s = 1, rearrangeably nonblocking network for unicast
`
`connections, in accordance with the invention.
`
`FIG. 3D1 is a diagram 300D1 of an exemplary asymmetrical multi-stage network
`
`10
`
`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 = 1, rearrangeably nonblocking network for unicast
`
`connections, in accordance with the invention.
`
`FIG. 3E1 is a diagram 300E1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,s) (having a connection topology called flip network and also known as
`
`15
`
`inverse shuffle exchange network) of five stages with N; = 8, N2 = p* N; = 24 where p =
`
`3, d=2 and s = 1, rearrangeably nonblocking network for unicast connections.
`
`FIG, 3F1 is a diagram 300F1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,s) having Baseline connection topology of five stages with N; = 8, N2 = p*
`
`N, = 24 where p = 3, d = 2 ands = 1, rearrangeably nonblocking network for unicast
`
`connections.
`
`FIG, 3G1 is a diagram 300G1 of an exemplary asymmetrical 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 = 1, rearrangeably nonblocking network for unicast
`
`connections, in accordance with the invention.
`
`25
`
`FIG, 3H1 is a diagram 300H1 of an exemplary asymmetrical multi-stage network
`
`V(N,, N.,d,s) having an exemplary connection topology of five stages with N; = 8, No
`
`Page 7 of 157
`
`Page 7 of 157
`
`

`

`M-0041 US
`
`= p* N; = 24 where p = 3, d=2 and s = 1, rearrangeably nonblocking network for unicast
`
`connections, in accordance with the invention.
`
`FIG, 311 is a diagram 30011 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,.d,s) (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, No = p* N; = 24 where p = 3, d = 2 and s = I, rearrangeably
`
`nonblocking network for unicast connections.
`
`FIG, 3J1 is a diagram 300J1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N.,d,s) having an exemplary connection topology of five stages with N; = 8, No
`
`10
`= p* N; = 24 where p = 3, d=2and s = 1, rearrangeably nonblocking network for unicast
`
`connections.
`
`FIG. 3K1 is a diagram 300K1 of a general asymmetrical multi-stage network
`V(N,,N,,d,s) with (2xlog, N)-1 stages with N; = p* No and s = 1, rearrangeably
`
`nonblocking network for unicast connections in accordance with the invention.
`
`15
`
`FIG, 3B2 is a diagram 300B2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N.,d,s)
`
`(having a connection topology built using back-to-back Omega
`
`Networks) of five stages with No = 8, Ni = p* No= 24, where p= 3,d=2 ands =1,
`
`rearrangeably nonblocking network for unicast connections.
`
`FIG, 3A2 is a diagram 300A2 of an exemplary asymmetrical multi-stage network
`
`20
`
`V(N,,N.,d,s) having inverse Benes connection topology of five stages with No = 8, Ni
`
`= p* No = 24, where p = 3, d = 2 and s = 1, rearrangeably nonblocking network for
`
`unicast connections, in accordance with the invention.
`
`FIG, 3C2 is a diagram 300C2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N.,,d,s) having an exemplary connection topology of five stages with No = 8, Ni
`
`25
`
`= p* No = 24, where p = 3, d = 2 and s = 1, rearrangeably nonblocking network for
`
`unicast connections, in accordance with the invention.
`
`Page 8 of 157
`
`Page 8 of 157
`
`

`

`M-0041 US
`
`FIG, 3D2 is a diagram 300D2 of an exemplary asymmetrical 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 = 1, rearrangeably nonblocking network for
`
`unicast connections, in accordance with the invention.
`
`FIG, 3E2 is a diagram 300E2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,s) (having a connection topology called flip network and also known as
`
`inverse shuffle exchange network) of five stages with No = 8, N; = p* N2.= 24, where p
`
`=3,d=2 ands=1, rearrangeably nonblocking network for unicast connections.
`
`FIG, 3F2 is a diagram 300F2 of an exemplary asymmetrical multi-stage network
`
`10
`
`V(N,,N.,d,s) having Baseline connection topology of five stages with N2 = 8, N; = p*
`
`N2 = 24, where p = 3, d= 2 ands = 1, rearrangeably nonblocking network for unicast
`
`connections.
`
`FIG. 3G2 is a diagram 300G2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,s) having an exemplary connection topology of five stages with No = 8, N;
`
`15
`
`= p* No = 24, where p = 3, d = 2 and s = 1, rearrangeably nonblocking network for
`
`unicast connections, in accordance with the invention.
`
`FIG, 3H2is a diagram 300H2 of an exemplary asymmetrical 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 = 1, rearrangeably nonblocking network for
`
`unicast connections, in accordance with the invention.
`
`FIG, 312 is a diagram 30012 of an exemplary asymmetrical multi-stage network
`
`V(N,,N.,d,s) (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 No = 8, N; = p* No = 24, where p = 3, d = 2 and s = 1, rearrangeably
`
`25
`
`nonblocking network for unicast connections.
`
`FIG, 3J2 is a diagram 300J2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N.,d,s) having an exemplary connection topology of five stages with No = 8, Ni
`
`-9-
`
`Page 9 of 157
`
`Page 9 of 157
`
`

`

`M-0041 US
`
`= p* No = 24, where p = 3, d = 2 and s = 1, rearrangeably nonblocking network for
`
`unicast connections.
`
`FIG, 3K2 is a diagram 300K2 of a general asymmetrical multi-stage network
`V(N,,.N,.d,s5) with (2xlog, N)-1 stages with Ny = p* N, and s = 1, rearrangeably
`
`nonblocking network for unicast connections in accordance with the invention.
`
`FIG. 4A 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
`
`invention.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`10
`
`The present invention is concerned with the design and operation of large scale
`
`crosspoint reduction using arbitrarily large folded multi-stage switching networks for
`
`broadcast, unicast and multicast connections. Particularly folded 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.
`
`15
`
`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 devices is 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. Whena transmitting device
`
`simultaneously sends information to 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
`
`25
`
`includes unicast and broadcast connections. A multicast assignmentin a switching
`
`network is nonblocking if any of the available inlet links can always be connected to any
`
`of the available outlet links.
`
`-10-
`
`Page 10 of 157
`
`Page 10 of 157
`
`

`

`M-0041 US
`
`In certain folded multi-stage networks of the type described herein, any
`
`connection request of arbitrary fan-out, i.e. from an inlet link to an outletlink or to a set
`
`of outlet links of the network, can be satisfied without blocking if necessary by
`
`rearranging some of the previous connection requests. In certain other folded multi-stage
`
`networksof the type described herein, any connection requestof arbitrary fan-out, i.e.
`
`from an inlet link to an outlet link or to a set of outlet links of the network, can be
`
`satisfied without blocking with never needing to rearrange any of the previous connection
`
`requests,
`
`In certain folded multi-stage networks of the type described herein, any
`
`10
`
`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 folded 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
`
`15
`
`requests.
`
`The folded multi-stage network V,,,(N,,N.,d,s) disclosed, in the current
`
`invention, is topologically exactly the same as the multi-stage network V(N,,N,,d,s),
`
`disclosed in U.S. Provisional Patent Application Docket No. M-0037USthatis
`
`incorporated by reference above, excepting that in the illustrations folded network
`
`20
`
`Vota (N,,N..d,5) is shown asit is folded at middle stage 130+10*(Log,N, —2)
`
`. This
`
`is true for all the embodiments presented in the current invention.
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`25
`
`unicast for generalized multi-stage networks V(N,,N.,,d,s) with numerous connection
`
`topologies and the scheduling methods are described in detail in U.S. Provisional Patent
`
`Application, Attorney Docket No. M-0037 USthat is incorporated by reference above.
`
`-l[1-
`
`Page 11 of 157
`
`Page 11 of 157
`
`

`

`M-0041 US
`
`2) Strictly and rearrangeably nonblockingfor arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks V,,(N,,N,,d,s) with numerous
`
`connection topologies and the scheduling methods are 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
`
`Vnine (N{»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
`
`unicastfor generalized multi-link butterfly fat tree networks V_io¢(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 nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`multi-stage networks V,,,,,,(N,,N,,d,s) and generalized folded multi-link multi-stage
`
`networks Vijg—mtine(Ni,N,,d,5) with numerous connection topologies and the scheduling
`
`20
`
`methodsare described in detail in U.S. Provisional Patent Application, Attorney Docket
`
`No. M-0042 USthat is incorporated by reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N,,N,,d,5), generalized
`
`folded multi-stage networks V,,(N,,N,,d,5), generalized butterfly fat tree networks
`
`Vig(N,,N,,d,s), generalized multi-link multi-stage networks V,,,.,(N,,N,,d,8),
`
`25
`
`generalized folded multi-link multi-stage networks Vg14-nine(N1,N>2,d,5), generalized
`
`multi-link butterfly fat tree networks V,,j,.-4,(N,,N.,d,5), and generalized hypercube
`
`networks V,_,,(N,,N,,d,5) for s = 1,2,3 or any numberin general, are described in
`
`-|2-
`
`Page 12 of 157
`
`Page 12 of 157
`
`

`

`M-0041 US
`
`detail in U.S. Provisional Patent Application, Attorney Docket No. M-0045 USthatis
`
`incorporated by reference above.
`
`Symmetric folded RNB Embodiments:
`
`Referring to FIG. 1A, in one embodiment, an exemplary symmetrical folded
`
`multi-stage network 100A with five stages of thirty two 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 whereinput stage 110 consists of four, two by
`
`10
`
`four switches IS1-IS4 and output stage 120 consists of four, four by two switches OS1-
`
`OS4. Andall the middle stages namely middle stage 130 consists of eight, two by two
`
`switches MS(1,1) - MS(1,8), middle stage 140 consists of eight, two by two switches
`
`MS(2,1) - MS(2,8), and middle stage 150 consists of eight, two by two switches MS(3,1)
`
`- MS(3,8).
`
`15
`
`Such a network can be operated in strictly non-blocking mannerfor unicast
`
`connections, because the switches in the input stage 110 are of size two by four, the
`
`switches in output stage 120 are of size four by two, and there are eight switches in each
`
`of middle stage 130, middle stage 140 and middle stage 150. Such a network can be
`
`Operated in rearrangeably non-blocking mannerfor multicast connections, because the
`
`20
`
`switches in the input stage 110 are of size two by four, the switches in output stage 120
`
`are of size four by two, and there are eight 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-OS4 are crossbar switches. The number of switches of input stage 110 and
`
`25
`
`ofoutput stage 120 can be denoted in general with the variable ot , where AN isthetotal
`
`numberofinlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by 2x—, Thesize of each input switch IS1-IS4 can be denoted in general
`
`-13-
`
`Page 13 of 157
`
`Page 13 of 157
`
`

`

`M-0041 US
`
`with the notation d *2d and each output switch OS1-OS4 can be denoted in general with
`
`the notation 2d *d. Likewise, the size of each switch in any of the middle stages can be
`
`denoted as d *d. A switch as used herein can beeither a crossbar switch, or a network
`
`of switches each of which in turn maybe a crossbar switch or a network of switches. A
`
`symmetric folded multi-stage network can be represented with the notation V,,,,(N,d,5s),
`
`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. Although it is not necessary that there be the same
`
`10
`
`numberofinlet links IL1-IL8 as there are outlet links OL1-OL8, in a symmetrical
`
`network they are the same.
`
`Eachofthe - input switches IS1 — IS4 are connected to exactly 2xd switches
`
`in middle stage 130 through 2xd links (for example input switch IS1 is connected to
`
`middle switches MS(1,1), MS(1,2), MS(1,5) and MS(1,6) through the links ML(1,1),
`
`15
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`Each ofthe 2x middle switches MS(1,1) — MS(1,8) in the middle stage 130
`
`are connected from exactly d input switches through d links (for example the links
`
`ML(1,1) and ML(1,5) are connected to the middle switch MS(1,1) from input switch IS1
`
`and IS2 respectively) and also are connected to exactly d switches in middle stage 140
`
`20
`
`through d links (for example the links ML(2,1) and ML(2,2) are connected from middle
`
`switch MS(1,1) to middle switch MS(2,1) and MS(2,3) respectively).
`
`Similarly each of the 2x= middle switches MS(2,1) — MS(2,8) in the middle
`
`stage 140 are connected from exactly d switches in middle stage 130 through d links
`
`(for example the links ML(2,1) and ML(2,6) are connected to the middle switch MS(2,1)
`
`25
`
`from middle switches MS(1,1) and MS(1,3) respectively) and also are connected to
`
`exactly d switches in middle stage 150 through d links (for example the links ML@G,1)
`
`-14-
`
`Page 14 of 157
`
`Page 14 of 157
`
`

`

`M-0041 US
`
`and ML(3,2) are connected from middle switch MS(,1) to middle switch MS@,1) and
`
`MS(3,3) respectively).
`
`Similarly each of the 2x— middle switches MS(3,1) — MS(3,8) in the middle
`
`stage 150 are connected from exactly d switches in middle stage 140 through d links
`
`(for example the links ML(3,1) and ML(3,6) are connected to the middle switch MS(3,1)
`
`from middle switches MS(2,1) and MS(2,3) respectively) and also are connected to
`
`exactly d output switches in output stage 120 through d links (for example the links
`
`ML(4,1) and ML(4,2) are connected to output switches OSI and OS? respectively from
`
`middle switches MS(3,1)).
`
`10
`
`Eachofthe - output switches OS1 —- OS4 are connected from exactly 2xd
`
`switches in middle stage 150 through 2xd links (for example output switch OS1 is
`
`connected from middle switches MS(3,1), MS(3,2), MS@,5) and MS(3,6) through the
`
`links ML(4,1), ML(4,3), ML(4,9) and ML(4,11) respectively).
`
`Finally the connection topology of the network 100A shown in FIG. 1A is known
`
`15
`
`to be back to back inverse Benes connection topology.
`
`Referring to FIG. 1A1, in another embodimentof network Vota (N,d,s),an
`
`exemplary symmetrical folded multi-stage network 100A1 with five stages of thirty two
`
`switches for satisfying communication requests, such as setting up a telephonecall ora
`
`data call, or a connection between configurable logic blocks, between an input stage 110
`
`20
`
`and output stage 120 via middle stages 130, 140, and 150 is shown whereinput stage 110
`
`consists of four, two by four switches IS1-IS4 and output stage 120 consists of four, four
`
`by two switches OS1-OS4. And all the middle stages namely middle stage 130 consists of
`
`eight, two by two switches MS(1,1) - MS(1,8), middle stage 140 consists of eight, two by
`
`two switches MS(2,1) - MS(2,8), and middle stage 150 consists of eight, two by two
`
`25
`
`switches MS(3,1) - MS(3,8).
`
`Such a network can be operated in strictly non-blocking manner for unicast
`
`connections, because the switches in the input stage 110 are of size two by four, the
`
`-15-
`
`Page 15 of 157
`
`Page 15 of 157
`
`

`

`M-0041 US
`
`switches in output stage 120 are of size four by two, and there are eight switches in each
`
`of middle stage 130, middle stage 140 and middle stage 150. Such a network can be
`
`operated in rearrangeably non-blocking manner for multicast connections, because the
`
`switchesin the input stage 110 are of size two by four, the switches in output stage 120
`
`are of size four by two, and there are eight 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 number of switches of input stage 110 and
`
`ofoutput stage 120 can be denoted in general with the variable ot , whereANisthetotal
`
`10
`
`numberofinlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by 2x, The size of each input switch IS1-IS4 can be denoted in general
`
`with the notation d *2d and each output switch OS1-OS4 can be denoted in general with
`
`the notation 2d *d. Likewise, the size of each switch in any of the middle stages can be
`
`denoted as d*d. A switch as used herein can be either a crossbar switch, or a network
`
`15
`
`of switches each of which in turn maybe a crossbar switch or a network of switches. The
`
`symmetric folded multi-stage network of FIG. 1A1 is also the network of the type
`
`Vio (N,d,s), where N represents the total numberofinlet links ofall 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
`
`20
`
`input switch to the inlet links of each input switch. Althoughit is not necessary that there
`
`be the same numberof inlet links IL1-IL8 as there are outlet links OL1-OL8, ina
`
`symmetrical network they are the same.
`
`Eachofthe - input switches IS1 —IS4 are connected to exactly 2xd switches
`
`in middle stage 130 through 2xd links (for example input switch IS1 is connected to
`
`25
`
`middle switches MS(1,1), MS(1,2), MS(1,5) and MS(1,6) through the links ML(1,1),
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`-16-
`
`Pa