M—0039 US
`
`FULLY CONNECTED GENERALIZED REARRANGEABLY 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 US.
`
`Provisional Patent Application Docket No. M-0037US entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`10
`
`assignee as the current application, filed concurrently.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Docket No. M-003 SUS entitled "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 reference in its entirety the US.
`
`Provisional Patent Application Docket No. M-0040US entitled "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 US.
`
`20
`
`Provisional Patent Application Docket No. M-0041US entitled "FULLY CONNECTED
`
`GENERALIZED FOLDED MULTI-STAGE 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 US.
`
`Provisional Patent Application Docket No. M-0042US entitled "FULLY CONNECTED
`
`25
`
`GENERALIZED STRICTLY NONBLOCKING MULTI—LINK MULTI-STAGE
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed concurrently.
`
`-1-
`
`Page 1 of 140
`
`FLEX LOGIX EXHIBIT 1021
`
`Page 1 of 140
`
`FLEX LOGIX EXHIBIT 1021
`
`

`

`M—0039 US
`
`This application is related to and incorporates by reference in its entirety the US
`
`Provisional Patent Application Docket No. M-0045US entitled ”VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned 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 thnk (N ,d , 5) having inverse Benes connection topology of five stages with N =
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`10
`
`invention.
`
`FIG. 1B is a diagram 100B of an exemplary symmetrical multi—link multi—stage
`
`network leink (N ,d ,5)
`
`(having a connection topology built using back-to-back Omega
`
`Networks) of five stages with N = 8, d = 2 and s=2, strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`15
`
`multicast connections, in accordance with the invention.
`
`FIG. 1C is a diagram 100C of an exemplary symmetrical multi—link multi—stage
`
`network leink (N, (Ls) having an exemplary connection topology of five stages with N =
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`20
`
`invention.
`
`FIG. 1D is a diagram 100D of an exemplary symmetrical multi—link multi—stage
`
`network Vmlink (N, (1,5) having an exemplary connection topology of five stages with N =
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`25
`
`invention.
`
`FIG. 1E is a diagram 100E of an exemplary symmetrical multi-link multi-stage
`
`network Vmlink
`
`(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=2, strictly
`-2-
`
`Page 2 of 140
`
`Page 2 of 140
`
`

`

`M—0039 US
`
`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 an exemplary symmetrical multi-link multi-stage
`
`network Vmlink (N ,(1 , 5) having Baseline connection topology of five stages with N = 8, d
`
`= 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`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 ‘/mlink (N, (1,5) having an exemplary connection topology of five stages with N =
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`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
`
`m
`network V link (N, (1,5) having an exemplary connection topology of five stages with N =
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 11 is a diagram 1001 of an exemplary symmetrical multi-link multi-stage
`
`m
`network V M (N ,(1 ,5)
`
`(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, d = 2 and s=2, strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`10
`
`15
`
`20
`
`FIG. 1] is a diagram 100] of an exemplary symmetrical multi-link multi-stage
`
`25
`
`m
`network V M (N, (1,5) having an exemplary connection topology of five stages with N =
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`Page 3 of 140
`
`Page 3 of 140
`
`

`

`M—0039 US
`
`FIG. 1K is a diagram 100K of a general symmetrical multi-link multi-stage
`
`network leink(N,d,s) with (2Xlog d N )—1
`
`stages with s=2,
`
`strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1A1 is a diagram 100A1 of an exemplary asymmetrical multi-link multi-
`
`stage network leink (N1,N2,d,s) having inverse Benes connection topology of five
`
`stages with N1 = 8, N2 = p1< N1 = 24 where p = 3, d = 2 and s = 2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for 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 leink (N1 , N2 , d , 5) (having a connection topology built using back—to—back
`
`Omega Networks) of five stages with N1 = 8, N2 = p* N1 = 24 where p = 3, d = 2 and s =
`
`2, strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1C1 is a diagram 100C1 of an exemplary asymmetrical multi-link multi-
`
`stage network thnk (N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N1 = 8, N2 = p* N = 24 where p = 3, d = 2 and s = 2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1D1 is a diagram 100D1 of an exemplary asymmetrical multi—link multi—
`
`stage network leink (N1,N2,al , 5) having an exemplary connection topology of five stages
`
`with N1 = 8, N2 = p* N = 24 where p = 3, d = 2 and s = 2, 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 multi—link multi—
`
`stage network thnk (N1,N2 ,d, 5) (having a connection topology called flip network and
`
`also known as inverse shuffle exchange network) of five stages with N1 = 8, N2 = p* N1
`
`= 24 where p = 3, d = 2 and s = 2, strictly nonblocking network for unicast connections
`
`-4-
`
`10
`
`15
`
`20
`
`25
`
`Page 4 of 140
`
`Page 4 of 140
`
`

`

`M—0039 US
`
`and rearrangeably nonblocking network for arbitrary fan-out multicast connections, in
`
`accordance with the invention.
`
`FIG. 1F1 is a diagram 100F1 of an exemplary asymmetrical 111ulti-linkmulti-stage
`
`network thnk (N1 , N2 , d , 5) having Baseline connection topology of five stages with N1 =
`
`8, N2 = p1< N1 = 24 where p = 3, d = 2 and s = 2, strictly nonblocking network for unicast
`
`connections and rearrangeably 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 thnk(N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N1 = 8, N2 = p1< N1 = 24 where p = 3, d = 2 and s = 2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1H1 is a diagram 100H1 of an exemplary asymmetrical multi-link multi-
`
`stage network Vmhnk(N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N1 = 8, N2 = p1< N1 = 24 where p = 3, d = 2 and s = 2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 111 is a diagram 10011 of an exemplary asymmetrical multi-link multi-stage
`
`m
`network V link(N1,N2,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 N1 = 8, N2 = p3< N1 = 24 where p = 3, d = 2 and s = 2,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1J1 is a diagram 100J1 of an exemplary asymmetrical multi-link multi-stage
`
`network V M (N1 ,N2,al , 5) having an exemplary connection topology of five stages with
`
`N1 = 8, N2 = p* N1 = 24 where p = 3, d = 2 and s = 2, strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`-5-
`
`10
`
`15
`
`20
`
`25
`
`Page 5 of 140
`
`Page 5 of 140
`
`

`

`M—0039 US
`
`FIG. 1K1 is a diagram 100K1 of a general asymmetrical multi-link multi-stage
`
`network VmM(N1,N2,d,s) with (2Xlogd N)—1 stages with N1 = p1< N2 and s = 2,
`
`strictly nonblocking network for unicast connections and rearrangeably 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-
`
`stage network leink (N1,N2, d , 5) having inverse Benes connection topology of five
`
`stages with N2 = 8, N1 = p* N2 = 24, where p = 3, d = 2 and s = 2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for 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 leink (N1 , N2 , d , 5) (having a connection topology built using back—to—back
`
`Omega Networks) of five stages with N2 = 8, N1 = p* N2 = 24, where p = 3, d = 2 and s
`
`= 2, 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 multi-link multi-
`
`stage network thnk (N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N2 = 8, N1 = p* N2 = 24, where p = 3, d = 2 and s = 2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for 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 leink (N1,N2,al , 5) having an exemplary connection topology of five stages
`
`with N2 = 8, N1 = p* N2: 24, where p = 3, d = 2 and s = 2, strictly nonblocking network
`
`for unicast connections and rearrangeably 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—
`
`stage network thnk (N1,N2 ,d, 5) (having a connection topology called flip network and
`
`also known as inverse shuffle exchange network) of five stages with N2 = 8, N1 = p* N2
`
`= 24, where p = 3, d = 2 and s = 2, strictly nonblocking network for unicast connections
`
`-6-
`
`10
`
`15
`
`20
`
`25
`
`Page 6 of 140
`
`Page 6 of 140
`
`

`

`M—0039 US
`
`and rearrangeably nonblocking network for arbitrary fan-out multicast connections, in
`
`accordance with the invention.
`
`FIG. 1F2 is a diagram 100F2 of an exemplary asymmetrical 111ulti-linkmulti-stage
`
`network thnk (N1 , N2 , d , 5) having Baseline connection topology of five stages with N3 =
`
`8, N1 = p* N2 = 24, where p = 3, d = 2 and s = 2, strictly nonblocking network for
`
`unicast connections and rearrangeably 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 thnk(N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N2 = 8, N1 = p* N2 = 24, where p = 3, d = 2 and s = 2, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1H2 is a diagram 100H2 of an exemplary asymmetrical multi-link multi-
`
`m
`stage network V
`
`link (N1,N2,al , 5) having an exemplary connection topology of five stages
`
`with N2 = 8, N1 = p* N2 = 24, where p = 3, d = 2 and s = 2, strictly nonblocking network
`
`for unicast connections and rearrangeably nonblocking network 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
`
`m
`network V link(N1,N2,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 N2 = 8, N1 = p* N2 = 24, where p = 3, d = 2 and s = 2,
`
`strictly nonblocking network for unicast connections and rearrangeably 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 M (N1 ,N2,al , 5) having an exemplary connection topology of five stages with
`
`N2 = 8, N1 = p* N2 = 24, where p = 3, d = 2 and s = 2, strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`-7-
`
`10
`
`15
`
`20
`
`25
`
`Page 7 of 140
`
`Page 7 of 140
`
`

`

`M—0039 US
`
`FIG. 1K2 is a diagram 100K2 of a general asymmetrical multi-link multi-stage
`
`network VmM(N1,N2,d,s) with (2Xlogd N)—1 stages with N2 = pl< N1 and s = 2,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 2A is a diagram 200A of an exemplary symmetrical folded multi-link multi-
`
`stage network Vfold—mlink (N ,d , 5) 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 multicast connections, in accordance with the invention.
`
`FIG. 2B is a diagram 200B of a general symmetrical folded multi—link multi—stage
`
`network Vfola'imlink (N,d ,2) with (2Xlogd N )—1 stages strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections in accordance with the invention.
`
`FIG. 2C is a diagram 200C of an exemplary asymmetrical folded multi-link multi-
`
`stage network Vfoldimlink (N1,N2,d ,2) having inverse Benes connection topology of five
`
`stages with N1 = 8, N2 = p* N1 = 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. 2D is a diagram 200D of a general asymmetrical folded multi-link multi-
`
`0
`stage network Vf
`
`ld,mli,1k(N1,N2,d,2) with N2 = p* N1 and with (2Xlogd N)—1 stages
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan—out multicast connections in accordance with the invention.
`
`FIG. 2E is a diagram 200E of an exemplary asymmetrical folded multi-link multi-
`
`stage network Vfoldimlink (N1,N2,d ,2) having inverse Benes connection topology of five
`
`stages with N2 = 8, N1 = p"< N2 = 24, where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`-8-
`
`10
`
`15
`
`20
`
`25
`
`Page 8 of 140
`
`Page 8 of 140
`
`

`

`M—0039 US
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2F is a diagram 200F of a general asymmetrical folded multi-link multi-stage
`
`network Vfgld mlink(N1,N2,d,2) with N1 = p* N2 and with (2xlogd N)—1 stages strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`FIG. 3A 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.
`
`10
`
`15
`
`20
`
`DETAILED 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
`
`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 optimal links as disclosed in this invention.
`
`When a 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. When a transmitting device
`
`simultaneously sends information to all the available receiving devices, the one-to-all
`
`connection required between the transmitting device and the receiving devices is called a
`
`25
`
`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
`
`-9-
`
`Page 9 of 140
`
`Page 9 of 140
`
`

`

`M—0039 US
`
`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
`
`of outlet links 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 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
`
`10
`
`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:
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks V(N1, N2 , (1,5) 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.
`
`2) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks Vbfl (N1 , N2 , 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.
`
`15
`
`20
`
`‘25
`
`-10-
`
`Page 10 of 140
`
`Page 10 of 140
`
`

`

`M—0039 US
`
`3) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-link butterfly fat tree networks leinkibfi (N1 , N2 , d , s) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`US. Provisional Patent Application, Attorney Docket No. M-0040 US that is
`
`incorporated by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized folded multi—stage networks Vfold (N1 , N2 , d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application, Attorney Docket No. M-0041 US that is incorporated by
`
`10
`
`reference above.
`
`5) Strictly nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`multi-stage networks Vmfink (N1, N2 , d , s) and generalized folded multi-link multi-stage
`
`networks Vfoldimlink (N1 , N2 , d, s) with numerous connection topologies and the scheduling
`
`methods are described in detail in US. Provisional Patent Application, Attorney Docket
`
`15
`
`No. M-0042 US that is incorporated by reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N1,N2,d, s) , generalized
`
`folded multi-stage networks Vfold (N1 , N2 , d , s) , generalized butterfly fat tree networks
`
`Vbfl (N1, N2 , d , s) , generalized multi-link multi-stage networks leink (N1 , N2 , d , s) ,
`
`0
`generalized folded multi-link multi-stage networks V}.
`
`WWW (N1 , N2 , d , s) , generalized
`
`20
`
`m
`multi-link butterfly fat tree networks V
`
`linHfi (N1 , N2 , d , s) , and generalized hypercube
`
`networks thbe (N1, N2,0! ,5) for s = 1,2,3 or any number in general, are described in
`
`detail in US. Provisional Patent Application, Attorney Docket No. M-0045 US that is
`
`incorporated by reference above.
`
`Symmetric RNB 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
`
`-11-
`
`Page 11 of 140
`
`Page 11 of 140
`
`

`

`M—0039 US
`
`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
`
`four switches IS 1-134 and output stage 120 consists of four, four by two switches OS 1-
`
`084. And all the middle stages namely middle stage 130 consists of four, four by four
`
`switches MS(1,1) - MS(1,4), middle stage 140 consists of four, four by four switches
`
`MS(2,1) - MS(2,4), and middle stage 150 consists of four, four by four switches MS(3,1)
`
`- MS(3,4).
`
`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
`
`10
`
`switches in output stage 120 are of size four by two, and there are four 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
`
`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 four switches in each of middle stage 130, middle
`
`15
`
`stage 140 and middle stage 150.
`
`In one embodiment of this network each of the input switches ISl-IS4 and output
`
`switches OSl-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
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`
`20
`
`is denoted by E. The size of each input switch ISl-IS4 can be denoted in general with
`d
`
`the notation d * 2d and each output switch OSl-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 2d * 2d . 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
`
`25
`
`switches. A symmetric multi—link multi—stage network can be represented with the
`
`notation Vmlink (N, d , s) , where N represents the total number of inlet links of all input
`
`switches (for example the links [Ll-1L8), 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. Although it is not necessary that
`
`-12-
`
`Page 12 of 140
`
`Page 12 of 140
`
`

`

`M—0039 US
`
`there be the same number of inlet links ILl-IL8 as there are outlet links OLl-OLS, in a
`
`symmetrical network they are the same.
`
`Each of the % input switches ISl — 154 are connected to exactly 2Xd switches
`
`in middle stage 130 through 2X d links (for example input switch 181 is connected to
`
`middle switch MS(l,l) through the links ML(l,1), ML(1,2), and also to middle switch
`
`MS(1,2) through the links ML(1,3) and ML(1,4)).
`
`Each of the E middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`d
`
`connected from exactly d input switches through 2 X d links (for example the links
`
`ML(l, l) and ML(1,2) are connected to the middle switch MS(1,1) from input switch 131,
`
`and the links ML(1,7) and ML(1,8) are connected to the middle switch MS(l,l) from
`
`input switch 1S2) and also are connected to exactly (I switches in middle stage 140
`
`through 2x (1 links (for example the links ML(2,1) and ML(2,2) are connected from
`
`middle switch MS(],l) to middle switch MS(2,1), and the links ML(2,3) and ML(2,4) are
`
`connected from middle switch MS( 1 , l) to middle switch MS(2,3)).
`
`Similarly each of the E middle switches MS(2,1) — MS(2,4) in the middle stage
`d
`
`140 are connected from exactly (I switches in middle stage 130 through 2x (1 links (for
`
`example the links ML(2,1) and ML(2,2) are connected to the middle switch MS(2,1) from
`
`middle switch MS(] , 1), and the links ML(Z, 1 1) and ML(2,12) are connected to the
`
`middle switch MS(2,l) from middle switch MS(l,3)) and also are connected to exactly (I
`
`switches in middle stage 150 through 2x (I links (for example the links ML(3,1) and
`
`ML(3,2) are connected from middle switch MS(2,1) to middle switch MS(3,1), and the
`
`links ML(3,3) and ML(3,4) are connected from middle switch MS(2,1) to middle switch
`
`MS(3,3)).
`
`Similarly each of the E middle switches MS(3,1) — MS(3,4) in the middle stage
`d
`
`150 are connected from exactly (1 switches in middle stage 140 through 2X d links (for
`
`example the links ML(3,1) and ML(3,2) are connected to the middle switch MS(3,1) from
`
`-13-
`
`10
`
`15
`
`20
`
`25
`
`Page 13 of 140
`
`Page 13 of 140
`
`

`

`M—0039 US
`
`middle switch MS(2,1), and the links ML(3,11) and ML(3,12) 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 2 Xd links (for example the links ML(4,1)
`
`and ML(4,2) are connected to output switch 031 from Middle switch MS(3,1), and the
`
`links ML(4,3) and ML(4,4) are connected to output switch 032 from middle switch
`
`MS(3,1)).
`
`10
`
`15
`
`20
`
`25
`
`Each of the % output switches OSl — 034 are connected from exactly 2X d
`
`switches in middle stage 150 through 2 Xd links (for example output switch 081 is
`
`connected from middle switch MS(3,’I) through the links ML(4,’I) and ML(4,2), and
`
`output switch 081 is also connected from middle switch MS(3,2) through the links
`
`ML(4,7) and ML(4,8)).
`
`Finally the connection topology of the network 100A shown in FIG. 1A is known
`
`to be back to back inverse Benes connection topology.
`
`Referring to FIG. 1B, in another embodiment of network thnk (N, d, s) , an
`
`exemplary symmetrical multi-link multi-stage network 100B 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 output stage 120 Via middle stages 130, 140, and 150 is shown where input stage 110
`
`consists of four, two by four switches 131-134 and output stage 120 consists of four, four
`
`by two switches OSl-OS4. And all the middle stages namely middle stage 130 consists of
`
`four, four by four switches MS(1,1) - MS(1,4), middle stage 140 consists of four, four by
`
`four switches MS(2,1) — MS(2,4), and middle stage 150 consists of four, four by four
`
`switches MS(3,1) — MS(3,4).
`
`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
`
`switches in output stage 120 are of size four by two, and there are four 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
`
`switches in the input stage 110 are of size two by four, the switches in output stage 120
`-14-
`
`Page 14 of 140
`
`Page 14 of 140
`
`

`

`M—0039 US
`
`are of size four by two, and there are four switches in each of middle stage 130, middle
`
`stage 140 and middle stage 150.
`
`In one embodiment of this network each of the input switches ISl-IS4 and output
`
`switches OSl-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
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by E . The size of each input switch lSl-lS4 can be denoted in general with
`d
`
`the notation d >|< 2d and each output switch OSl—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 2d >|< 2d . 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 leink (N, d , s) , where N represents the total number of inlet links of all input
`
`switches (for example the links ILl-ILS), 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. Although it is not necessary that
`
`there be the same number of inlet links ILl-ILS as there are outlet links OLl-OLS, in a
`
`symmetrical network they are the same.
`
`Each of the % input switches ISl — 134 are connected to exactly 2Xd switches
`
`in middle stage 130 through 2X (1 links (for example input switch 151 is connected to
`
`middle switch MS(1,1) through the links ML(1,1), ML(1,2), and also to middle switch
`
`MS(1,2) through the links ML(1,3) and ML(1,4)).
`
`Each of the E middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`d
`
`connected from e