M—0038 US
`
`FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE NETWORKS
`
`Venkat Konda
`
`5
`
`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—0037US entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed concurrently.
`
`10
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0039US entitled ”FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTI-
`
`STAGE 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 U.S.
`
`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 U.S.
`
`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 U.S.
`
`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 83
`
`FLEX LOGIX EXHIBIT 1017
`
`Page 1 of 83
`
`FLEX LOGIX EXHIBIT 1017
`
`

`

`M—0038 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 Butterfly fat tree
`
`network Vbfi (N, d, 5) having inverse Benes connection topology of three 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. 1B is a diagram 100B of a general symmetrical Butterfly fat tree network
`
`Vbfi (N,d,s) with (log d N ) stages strictly nonblocking network for unicast connections
`
`and rearrangeably nonblocking network for arbitrary fan-out multicast connections in
`
`accordance with the invention.
`
`15
`
`20
`
`FIG. 1C is a diagram 100C of an exemplary Asymmetrical Butterfly fat tree
`
`network V (N ,N ,d ,2) having inverse Benes connection topology of three stages with
`bft
`1
`2
`
`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. 1D is a diagram 100D of a general asymmetrical Butterfly fat tree network
`
`Vbfl(N1,N2,d,2) with N2 = p* N1 and with (logd N) stages strictly nonblocking network
`
`for unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections in accordance with the invention.
`
`FIG. 1E is a diagram 100E of an exemplary Asymmetrical Butterfly fat tree
`
`network Vbfl(N1,N2,d,2) having inverse Benes connection topology of three stages with
`
`N2 = 8, N1 = p* N2 = 24, where p = 3, and d = 2 with exemplary multicast connections,
`
`Page 2 of 83
`
`Page 2 of 83
`
`

`

`M—0038 US
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. lF is a diagram 100F of a general asymmetrical Butterfly fat tree network
`
`Vbfl(N1, N2,d ,2) with N1 = p* N2 and with (log d N ) stages 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 Butterfly fat tree
`
`network V
`bfl(N, d, 5) having inverse Benes connection topology of three stages with N =
`
`8, d = 2 and s=1 with exemplary unicast connections rearrangeably nonblocking network
`
`10
`
`for unicast connections, in accordance with the invention.
`
`FIG. 2B is a diagram 200B of a general symmetrical Butterfly fat tree network
`
`Vbfl(N,d,s) with (log d N ) stages and s=1, rearrangeably nonblocking network for
`
`unicast connections in accordance with the invention.
`
`FIG. 2C is a diagram 200C of an exemplary Asymmetrical Butterfly fat tree
`
`network Vbfi (N1,N2, d,1) having inverse Benes connection topology of three stages with
`
`N1 = 8, N2 = p* N1 = 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 Butterfly fat tree network
`
`Vbfi (N1,N2,d ,1) with N2 = p* N and with (log d N ) stages rearrangeably nonblocking
`
`network for unicast connections in accordance with the invention.
`
`FIG. 2B is a diagram 200E of an exemplary Asymmetrical Butterfly fat tree
`
`network Vbfl (N1,N 2’ d ,1) having inverse Benes connection topology of three stages with
`
`N2 = 8, N1 = p"< N2 = 24, where p = 3, and d = 2 with exemplary unicast connections
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`15
`
`20
`
`25
`
`Page 3 of 83
`
`Page 3 of 83
`
`

`

`M—0038 US
`
`FIG. 2F is a diagram 200E of a general asymmetrical Butterfly fat tree network
`
`Vbfi (N1,N2,d ,1) with N1 = p* N2 and with (logd N ) stages rearrangeably nonblocking
`
`network for unicast 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.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`10
`
`15
`
`20
`
`25
`
`The present invention is concerned with the design and operation of large scale
`
`crosspoint reduction using arbitrarily large Butterfly fat tree networks for broadcast,
`
`unicast and multicast connections. Particularly Butterfly fat tree networks with stages
`
`more than or equal to 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
`
`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 Butterfly fat tree 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
`-4-
`
`Page 4 of 83
`
`Page 4 of 83
`
`

`

`M—0038 US
`
`links of the network, can be satisfied without blocking if necessary by rearranging some
`
`of the previous connection requests. In certain other Butterfly fat tree 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 requests.
`
`In certain Butterfly fat tree 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 Butterfly fat tree 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 , d, s) with numerous connection
`
`topologies and the scheduling methods are described in detail in US. Provisional Patent
`
`Application, Attorney Docket No. M-0037 US that is incorporated by reference above.
`
`2) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`thnk (N1 ,N2 , d , s) and generalized folded multi-link multi-stage networks
`
`V
`
`foldimlink (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-
`
`0039 US that is incorporated by reference above.
`
`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
`
`10
`
`15
`
`20
`
`Page 5 of 83
`
`Page 5 of 83
`
`

`

`M—0038 US
`
`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
`
`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
`
`10
`
`networks an,d_m,ink (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-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
`
`15
`
`m
`Vbfi (N1, N2 , d , s) , generalized multi-link multi-stage networks V
`
`link(N1’N2’d’S) 3
`
`generalized folded multi-link multi-stage networks Vfold—mlink (N1,N2 , d, s) , generalized
`
`multi—link butterfly fat tree networks leink_bfi (N1 , N2 , d , s) , and generalized hypercube
`
`networks thbe (N1, N2,01 ,s) 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
`
`20
`
`incorporated by reference above.
`
`Symmetric RNB Embodiments:
`
`Referring to FIG. 1A, in one embodiment, an exemplary symmetrical Butterfly fat
`
`tree network 100A with three stages of twenty four switches for satisfying
`
`communication requests, such as setting up a telephone call or a data call, or a connection
`
`25
`
`between configurable logic blocks, between an input stage 110 and output stage 120 via
`
`middle stages 130, and 140 is shown where input stage 110 consists of four, two by four
`
`switches IS1—IS4 and output stage 120 consists of four, four by two switches OS1—OS4.
`
`-6-
`
`Page 6 of 83
`
`Page 6 of 83
`
`

`

`M—0038 US
`
`And all the middle stages excepting root stage namely middle stage 130 consists of eight,
`
`four by four switches MS(1,1) - MS(1,8), and root stage i.e., middle stage 140 consists of
`
`eight, two by two switches MS(2,1) - MS(2,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
`
`switches in output stage 120 are of size four by two, and there are eight switches in each
`
`of middle stage 130 and middle stage 140. 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
`
`10
`
`by two, and there are eight switches in each of middle stage 130 and middle stage 140.
`
`In one embodiment of this network each of the input switches IS l-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 E , where N is the total
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`
`15
`
`is denoted by 2><%. The size of each input switch ISl—IS4 can be denoted in general
`
`with 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 excepting that the size of each switch in middle stage 140 is denoted
`
`as d * d . (In another embodiment, the size of each switch in any of the middle stages
`
`other than the middle stage 140, can be implemented as d * 2d and d * d since the down
`
`coming middle links are never setup to the up going middle links. For example in
`
`network 100A of FIG. 1A, the down coming middle links ML(3,2) and ML(3,5) are never
`
`setup to the up going middle links ML(2,1) and ML(2,2) for the middle switch MS(l, 1).
`
`So middle switch MS(1,1) can be implemented as a two by four switch with middle links
`
`ML(l,l) and ML(1,3) as inputs and middle links ML(2,1), ML(2,2), ML(4,1) and
`
`ML(4,2) as outputs; and a two by two switch with middle links ML(3,2) and ML(3,5) as
`
`20
`
`25
`
`inputs and middle links ML(4,1) and ML(4,2) as outputs).
`
`Middle stage ’140 is called as root stage. 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
`-7-
`
`Page 7 of 83
`
`Page 7 of 83
`
`

`

`M—0038 US
`
`or a network of switches. A symmetric Butterfly fat tree network can be represented with
`
`the notation Vbfi (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 131 is connected to
`
`middle switches MS(1,1), MS(l,2), MS(l,5) and MS(l,6) through the links ML(l,l),
`
`ML(l,2), ML(l,3) and ML(l,4) respectively).
`
`Each of the 2X% middle switches MS(l,l) — MS(1,8) in the middle stage 130
`
`are connected from exactly (1 input switches through (1 links (for example the links
`
`ML(l, l) and ML(1,5) are connected to the middle switch MS(1,1) from input switch 131
`
`and 132 respectively) and are also connected from exactly cl switches in middle stage
`
`140 through d links (for example the links ML(3,l) and ML(3,6) are connected to the
`
`middle switch MS( 1,1) from middle switches MS(2,1) and MS(2,3) respectively).
`
`Each of the 2X% middle switches MS(l,l) — MS(1,8) in the middle stage 130
`
`are connected to exactly d switches in middle stage 140 through d links (for example
`
`the links ML(2,1) and ML(2,2) are connected from middle switch MS(l,l) to middle
`
`switch 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 OS] and 032 respectively from middle
`
`switches MS(l,l)).
`
`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
`
`-8-
`
`10
`
`15
`
`20
`
`25
`
`Page 8 of 83
`
`Page 8 of 83
`
`

`

`M—0038 US
`
`(for example the links ML(2,1) and ML(2,5) are connected to the middle switch MS(2,1)
`
`from middle switches MS(1,1) and MS(1,3) respectively) and also are connected to
`
`exactly (1 switches in middle stage 130 through (1 links (for example the links ML(3,1)
`
`and ML(3,2) are connected from middle switch MS(2,1) to middle switch MS(1,1) and
`
`MS(1,3) respectively).
`
`Each of the % output switches 08] — 034 are connected from exactly 2X d
`
`switches in middle stage 130 through 2 Xd links (for example output switch 081 is
`
`connected from middle switches MS(l,l), MS(1,2), MS(1,5) and MS(1,6) through the
`
`links ML(4,1), ML(4,3), ML(4,9) and ML(4,11) respectively).
`
`10
`
`15
`
`‘20
`
`25
`
`Finally the connection topology of the network 100A shown in FIG. 1A is known
`
`to be back to back inverse Benes connection topology.
`
`In the three embodiments of FIG. 1A, FIG. 1A1 and FIG. 1A2 the connection
`
`topology is different. That is the way the links ML(1,1) - ML(1,16), ML(2,1) - ML(2,16),
`
`ML(3,1) - ML(3,16), and ML(4,1) - ML(4,16) are connected between the respective
`
`stages is different. Even though only three embodiments are illustrated, in general, the
`
`network VW (N, d, s) can comprise any arbitrary type of connection topology. For
`
`example the connection topology of the network Vbfi (N, d , 5) may be back to back Benes
`
`networks, Delta Networks and many more combinations. The applicant notes that the
`
`fundamental property of a valid connection topology of the Vbfi (N ,d, 5) network is, when
`
`no connections are setup from any input link all the output links should be reachable.
`
`Based on this property numerous embodiments of the network Vbfi (N, d , s) can be built.
`
`The embodiments of FIG. 1A, FIG. 1A1, and FIG. 1A2 are only three examples of
`
`network Vbfi(N,d,s).
`
`In the three embodiments of FIG. 1A, FIG. 1A1 and FIG. 1A2, each of the links
`
`ML(1,1) — ML(1,16), ML(2,1) — ML(2,16), ML(3,1) — ML(3,16) and ML(4,1) —
`
`ML(4,16) are either available for use by a new connection or not available if currently
`
`used by an existing connection. The input switches ISl-IS4 are also referred to as the
`
`network input ports. The input stage 110 is often referred to as the first stage. The output
`-9-
`
`Page 9 of 83
`
`Page 9 of 83
`
`

`

`M—0038 US
`
`switches OSl-OS4 are also referred to as the network output ports. The output stage 120
`
`is often referred to as the last stage. The middle stage switches MS(1,1) — MS(1,8)and
`
`MS(2, l) — MS(2,8) are referred to as middle switches or middle ports. The middle stage
`
`130 is also referred to as root stage and middle stage switches MS(1,2) — MS(2,8) are
`
`referred to as root stage switches.
`
`In the example illustrated in FIG. 1A (or in FIG1A1, or in FIG. 1A2), a fan-out of
`
`four is possible to satisfy a multicast connection request if input switch is IS2, but only
`
`two switches in middle stage 130 will be used. Similarly, although a fan-out of three is
`
`possible for a multicast connection request if the input switch is 181, again only a fan—out
`
`10
`
`of two is used. The specific middle switches that are chosen in middle stage 130 when
`
`selecting a fan—out of two is irrelevant so long as at most two middle switches are selected
`
`to ensure that the connection request is satisfied. In essence, limiting the fan-out from
`
`input switch to no more than two middle switches permits the network 100A (or 100A1,
`
`or 100A2), to be operated in rearrangeably nonblocking manner in accordance with the
`
`15
`
`invention.
`
`The connection request of the type described above can be unicast connection
`
`request, a multicast connection request or a broadcast connection request, depending on
`
`the example.
`
`In case of a unicast connection request, a fan-out of one is used, i.e. a single
`
`middle stage switch in middle stage 130 is used to satisfy the request. Moreover,
`
`20
`
`although in the above-described embodiment a limit of two has been placed on the fan-
`
`out into the middle stage switches in middle stage 130, the limit can be greater depending
`
`on the number of middle stage switches in a network (while maintaining the
`
`rearrangeably nonblocking nature of operation of the network for multicast connections).
`
`However any arbitrary fan—out may be used within any of the middle stage switches and
`
`the output stage switches to satisfy the connection request.
`
`Generalized Symmetric RNB Embodiments:
`
`Network 100B of FIG. 1B is an example of general symmetrical Butterfly fat tree
`
`network Vbfi (N, d, s) with (log d N) stages. The general symmetrical Butterfly fat tree
`
`network Vbfl (N, d, s) can be operated in rearrangeably nonblocking manner for multicast
`
`-10-
`
`Page 10 of 83
`
`Page 10 of 83
`
`

`

`M—0038 US
`
`when s = 2 according to the current invention. Also the general symmetrical Butterfly fat
`
`tree network Vbfl (N, d , s) can be operated in strictly nonblocking manner for unicast if
`
`s = 2 according to the current invention. (And in the example of FIG. 1B, 5 = 2). The
`
`general symmetrical Butterfly fat tree network Vb (N , d , s) with (logd N ) stages has d
`fl
`
`inlet links for each of E input switches ISl-IS(N/d) (for example the links ILl-IL(d) to
`d
`
`the input switch 181) and 2X d outgoing links for each of E input switches ISl-IS(N/d)
`d
`
`(for example the links ML(1,1) — ML(1,2d) to the input switch 181). There are d outlet
`
`links for each of % output switches OSl-OS(N/d) (for example the links OLl-OL(d) to
`
`the output switch 051) and 2X d incoming links for each of % output switches OSl-
`
`OS(N/d) (for example ML(2X Long — 2,1) - ML(2X Long — 2,2>< d) to the output
`
`switch 031).
`
`Each of the % input switches ISl — IS(N/d) are connected to exactly 2 Xd
`
`switches in middle stage 130 through 2 ><d links (for example input switch 131 is
`
`connected to middle switches MS( 1,1) - MS(1,d) through the links ML(1,1) - ML(1,d)
`
`and to middle switches MS(1,N/d+1) — MS(1, {N/d}+d) through the links ML(1,d+1) —
`
`ML(1,2d) respectively.
`
`Each of the 2X% middle switches MS(1,1) , MS(1,2N/d) in the middle stage
`
`130 are connected from exactly d input switches through d links and also are connected
`
`to exactly d switches in middle stage 140 through d links.
`
`10
`
`15
`
`20
`
`Similarly each of the 2X% middle switches MS(1,1) — MS(1,2N/d) in the middle
`
`stage 130 are also connected from exactly d switches in middle stage 140 through d
`
`links and also are connected to exactly d output switches in output stage 120 through d
`
`links.
`
`-11-
`
`Page 11 of 83
`
`Page 11 of 83
`
`

`

`M—0038 US
`
`Similarly each of the 2X% middle switches MS(LogdN —1,1)
`
`-
`
`MS(L0ng — 1,2XE!) in the middle stage 130 +10 * (Long — 2) are connected from
`
`(
`
`exactly (I switches in middle stage 130 +10 * (Long —3) through d links and also are
`
`connected to exactly d switches in middle stage 130 +10 * (Long — 1) through d links.
`
`Each of the % output switches OS] — OS(N/d) are connected from exactly 2>< d
`
`switches in middle stage 130 through 2 x d links.
`
`As described before, again the connection topology of a general Vbfl (N, d , s) may
`
`be any one of the connection topologies. For example the connection topology of the
`
`network Vbf, (N, d, s) may be back to back inverse Benes networks, back to back Omega
`
`networks, back to back Benes networks, Delta Networks and many more combinations.
`
`The applicant notes that the fundamental property of a valid connection topology of the
`
`general be; (N, d, 5) network is, when no connections are setup from any input link if any
`
`output link should be reachable. Based on this property numerous embodiments of the
`
`network Vbfi (N, d , s) can be built. The embodiments of FIG. 1A, FIG. 1A1, and FIG.
`
`1A2 are three examples of network Vbfi (N, d, s) .
`
`10
`
`15
`
`The general symmetrical Butterfly fat tree network Vbfi (N, d , s) can be operated
`
`in rearrangeably nonblocking manner for multicast when s = 2 according to the current
`
`invention. Also the general symmetrical Butterfly fat tree network Vbfi (N, d, s) can be
`
`operated in strictly nonblocking manner for unicast if s = 2 according to the current
`
`20
`
`invention.
`
`Every switch in the Butterfly fat tree networks discussed herein has multicast
`
`capability. In a Vbfi (N, d , 5) network, if a network inlet link is to be connected to more
`
`than one outlet link on the same output switch, then it is only necessary for the
`
`corresponding input switch to have one path to that output switch. This follows because
`
`25
`
`that path can be multicast within the output switch to as many outlet links as necessary.
`-12-
`
`Page 12 of 83
`
`Page 12 of 83
`
`

`

`M—0038 US
`
`Multicast assignments can therefore be described in terms of connections between input
`
`switches and output switches. An existing connection or a new connection from an input
`
`switch to r' output switches is said to have fan-out r'. If all multicast assignments of a
`
`first type, wherein any inlet link of an input switch is to be connected in an output switch
`
`to at most one outlet link are realizable, then multicast assignments of a second type,
`
`wherein any inlet link of each input switch is to be connected to more than one outlet link
`
`in the same output switch, can also be realized. For this reason, the following discussion
`
`is limited to general multicast connections of the first type (w1th fan-out r , 1: r S —)
`d
`
`although the same discussion is applicable to the second type.
`
`To characterize a multicast ass1gnment, for each inlet link 16 {IWZE} let
`
`.
`
`.
`
`.
`
`N
`
`.
`
`.
`
`.
`
`10
`
`15
`
`Il. = 0, where 0 C {1H2...,,%} denote the subset of output switches to which inlet link i
`
`is to be connected in the multicast assignment. For example, the network of Fig. 1A
`
`shows an exemplary three-stage network, namely Vbfl (8,2,2), with the following
`
`multicast assignment I1 = {2,3}and all other Ij = ¢ for j = [2-8]. It should be noted that
`
`the connection I1 fans out in the first stage switch 181 into middle switches MS(l,l) and
`
`MS(1,5) in middle stage 130, and fans out in middle switches MS(1,1) and MS(1,5) only
`
`once into output switch 082 in output stage 120 and middle switch MS(2,7) in middle
`
`stage 140 respectively.
`
`The connection I1 also fans out in middle switch MS(2,7) only once into middle
`
`switches MS(3,1) and MS(3,7) respectively in middle stage 150. The connection I1 also
`
`fans out in middle switch MS(1,7) only once into output switch OS3 in output stage 120.
`
`Finally the connection I1 fans out once in the output stage switch 082 into outlet link
`
`0L3 and in the output stage switch OS3 twice into the outlet links 0L5 and 0L6.
`
`In
`
`accordance with the invention, each connection can fan out in the input stage switch into
`
`25
`
`at most two middle stage switches in middle stage 130.
`
`Page 13 of 83
`
`Page 13 of 83
`
`

`

`M—0038 US
`
`Asymmetric RNB (NZ > N1) Embodiments:
`
`Referring to FIG. 1C, in one embodiment, an exemplary asymmetrical Butterfly
`
`fat tree network 100C with three stages of twenty four 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 and 140 is shown where input stage 110 consists of four, two by four
`
`switches 131-134 and output stage 120 consists of four, eight by six switches OSl-OS4.
`
`Middle stage 130 consists of eight, four by six switches MS(l,l) - MS(1,8) and middle
`
`stage 140 consists of eight, two by two switches MS(2,1) — MS(2,8).
`
`10
`
`15
`
`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 eight by six, and there are eight switches in each
`
`of middle stage 130 and middle stage 140. 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 eight
`
`by six, and there are eight switches of size four by six in middle stage 130 and eight
`
`switches of size two by two in middle stage 140.
`
`In one embodiment of this network each of the input switches 131—134 and output
`
`switches OSl-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 fi, where N1 is the total
`d
`
`number of inlet links or and N2 is the total number of outlet links and N2 > N1 and
`
`N, = p * N1 where p > 1. The number of middle switches in each middle stage is
`
`denoted by 2 X%. The size of each input switch ISl-IS4 can be denoted in general with
`
`the notation d >I< 2d and each output switch OSl-OS4 can be denoted in general with the
`
`notation (d + d2) * d , Where al2 = N2 Xi = p x d . The size of each switch in middle
`N1
`
`stage 130 can be denoted as 2d * (d + (Z2) . The size of each switch in the root stage (i.e.,
`
`middle stage140) can be denoted as d * d . The size of each switch in all the middle
`
`-14-
`
`Page 14 of 83
`
`Page 14 of 83
`
`

`

`M—0038 US
`
`stages excepting middle stage 130 and root stage can be denoted as 2d >I< 2d (In network
`
`100C of FIG. 1C, there is no such middle stage). (In another embodiment, the size of each
`
`switch in any of the middle stages other than the middle stage 140, can be implemented
`
`as d * 2d and (Z * d since the down coming middle links are never setup to the up going
`
`middle links. For example in network 100C of FIG. 1C, the down coming middle links
`
`ML(3,2) and ML(3,5) are never setup to the up going middle links ML(2,1) and ML(2,2)
`
`for the middle switch MS(1,1). So middle switch MS(1, 1) can be implemented as a two
`
`by four switch with middle links ML(1,1) and ML(1,3) as inputs and middle links
`
`ML(2,1), ML(2,2), ML(4,1) and ML(4,2) as outputs; and a two by two switch with
`
`middle links ML(3,2) and ML(3,5) as inputs and middle links ML(4, 1) and ML(4,2) as
`
`outputs).
`
`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. An asymmetric
`
`Butterfly fat tree network can be represented with the notation Vbfi (N1 , N2 , d , s) , where
`
`N1 represents the total number of inlet links of all input switches (for example the links
`
`IL1-IL8), N2 represents the total number of outlet links of all output switches (for
`
`example the links OL1-OL24), d represents the inlet links of each input switch where
`
`NZ > N1 , and s is the ratio of number of outgoing links from each input switch to the
`
`inlet links of each input switch.
`
`10
`
`15
`
`20
`
`Each of the % input switches [81 — IS4 are connected to exactly 2x d switches
`
`in middle stage 130 through 2x d links (for example input switch 181 is connected to
`
`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).
`
`N1
`Each of the 2X7 middle switches MS(1,1) — MS(1,8) in the middle stage 130
`
`25
`
`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 131
`
`and ISZ respectively) and are also connected from exactly cl switches in middle stage
`
`-15-
`
`Page 15 of 83
`
`Page 15 of 83
`
`

`

`M—0038 US
`
`140 through d links (for example the links ML(3,1) and ML(3,6) are connected to the
`
`middle switch MS(1,1) from middle switches MS(2,1) and MS(2,3) respectively).
`
`N1
`Similarly each of the 2X7 middle switches MS(1,1) — MS(1,8) in the middle
`
`stage 130 are connected to exactly d switches in middle stage 140 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) and also are connected to exactly
`
`
`
`d +2d2 output switches in output stage 120 through d +2d2
`
`
`
`links (for e