M—0040 US
`
`FULLY CONNECTED GENERALIZED MULTI-LINK BUTTERFLY FAT TREE
`
`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
`
`20
`
`This application is related to and incorporates by reference in its entirety the US.
`
`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.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`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
`
`GENERALIZED STRICTLY NONBLOCKING MULTI—LINK MULTI-STAGE
`
`Page 1 of 57
`
`FLEX LOGIX EXHIBIT 1018
`
`Page 1 of 57
`
`FLEX LOGIX EXHIBIT 1018
`
`

`

`M—0040 US
`
`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-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 Butterfly fat
`
`tree network lemk_bfi(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 multicast connections, in accordance with the invention.
`
`FIG. 1B is a diagram 100B of a general symmetrical multi-link Butterfly fat tree
`
`network leinkibfi (N ,d ,2) with (log a N ) stages strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections in accordance with the invention.
`
`FIG. 1C is a diagram 100C of an exemplary asymmetrical multi-link Butterfly fat
`
`tree network lemkibfl (N1,N2,d,2) having inverse Benes connection topology of five
`
`stages with N1 = 8, N3 = pi< 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 multi-link Butterfly fat tree
`
`network leinkibfi(N1
`
`, N2 ,d ,2) with N2 = p* N1 and with (log, N ) stages strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`10
`
`15
`
`20
`
`25
`
`Page 2 of 57
`
`Page 2 of 57
`
`

`

`M—0040 US
`
`FIG. IE is a diagram 100E of an exemplary asymmetrical multi-link Butterfly fat
`
`tree network leinkibfi (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
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1F is a diagram 100F of a general asymmetrical multi-link Butterfly fat tree
`
`network lemkibfi(N1, N2 ,d ,2) with N1 = pl< N2 and with (logd N ) stages strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`10
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`FIG. 2A is high-level flowchart of a scheduling method according to the
`
`invention, used to set up the multicast connections in all the networks disclosed in this
`
`invention.
`
`15
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`20
`
`25
`
`The present invention is concerned with the design and operation of large scale
`
`crosspoint reduction using arbitrarily large Multi-link Butterfly fat tree networks for
`
`broadcast, unicast and multicast connections. Particularly Multi-link 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
`
`-3-
`
`Page 3 of 57
`
`Page 3 of 57
`
`

`

`M—0040 US
`
`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.
`
`10
`
`15
`
`In certain Multi-link 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 if necessary by
`
`rearranging some of the previous connection requests. In certain other Multi-link
`
`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 Multi-link 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 Multi—link 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
`
`25
`
`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.
`
`Page 4 of 57
`
`Page 4 of 57
`
`

`

`M—0040 US
`
`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 US
`
`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
`
`thnk (N1 , N2 , d , s) and generalized folded multi—link multi—stage networks
`
`Vfoldflnlmk (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.
`
`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-004l US that is incorporated by
`
`reference above.
`
`5) Strictly nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`multi—stage networks leink (N1, N2 , d , s) and generalized folded multi—link multi—stage
`
`networks Vfoldwhnk (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 anm (N1 ,N2 , d, s), generalized butterfly fat tree networks
`
`Vbfi (N1, N2 , d , s) , generalized multi-link multi-stage networks leink (N1 , N2 , d , s) ,
`
`generalized folded multi-link multi-stage networks Vfoldflnhnk (N1 , N2 , d , s) , generalized
`
`multi-link butterfly fat tree networks Vm,inkibfi (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
`
`-5-
`
`10
`
`15
`
`20
`
`25
`
`Page 5 of 57
`
`Page 5 of 57
`
`

`

`M—0040 US
`
`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
`
`Butterfly fat tree network 100A with three stages of sixteen 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, four by two switches OSl-OS4.
`
`And all the middle stages excepting root stage namely middle stage 130 consists of four,
`
`eight by eight switches MS(1,l) - MS(1,4), and root stage i.e., middle stage 140 consists
`
`of four, four by four switches MS(2,1) - MS(2,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 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 1 10 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 and middle stage 140.
`
`10
`
`15
`
`20
`
`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 E , where N is the total
`(1
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`
`‘25
`
`is denoted by E. The size of each input switch IS l-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 >i< d . Likewise, the size of each switch in any of the middle stages can be
`
`-6-
`
`Page 6 of 57
`
`Page 6 of 57
`
`

`

`M—0040 US
`
`denoted as 4d >|< 4d excepting that the size of each switch in middle stage 140 is denoted
`
`as 2d * 2d . (In another embodiment, the size of each switch in any of the middle stages
`
`other than the middle stage 140, can be implemented as 2d >|< 4d and 2d >|< 2d 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,3), ML(3,4), ML(3,9)
`
`and ML(3,10) are never setup to the up going middle links ML(2,1), ML(2,2), ML(2,3)
`
`and ML(2,4) for the middle switch MS(l,l). So middle switch MS(l, 1) can be
`
`implemented as a four by eight switch with middle links ML(1,1), ML(1,2), ML(1,5) and
`
`ML(1,6) as inputs and middle links ML(2,1), ML(2,2), ML(2,3), ML(2,4), ML(4,1),
`
`ML(4,2), ML(4,3), and ML(4,4) as outputs; and a four by four switch with middle links
`
`ML(3,3), ML(3,4), ML(3,9) and ML(3,10) as inputs and middle links ML(4,1), ML(4,2),
`
`ML(4,3), and ML(4,4) 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
`
`or a network of switches. A symmetric Multi-link Butterfly fat tree network can be
`
`represented with the notation lemkibfi (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 3 input switches ISl — 134 are connected to exactly d switches in
`
`middle stage 130 through 2 X d links (for example input switch 151 is connected to
`
`middle switch MS(1,1) through the links ML(1,1) and ML(1,2); and input switch 151 is
`
`also connected to middle switch MS(1,2) through the links ML(1,3) and ML(1,4)).
`
`Each of the E middle switches MS(l,l) — 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(1,1) and ML(1,2) are connected to the middle switch MS(1,1) from input switch 151;
`
`-7-
`
`10
`
`15
`
`20
`
`25
`
`Page 7 of 57
`
`Page 7 of 57
`
`

`

`M—0040 US
`
`and the links ML(1,5) and ML(1,6) are connected to the middle switch MS(1,1) from
`
`input switch IS2) and are also connected from exactly d switches in middle stage 140
`
`through 2X (1 links (for example the links ML(3,3) and ML(3,4) are connected to the
`
`middle switch MS(1,1) from middle switch MS(2,1) and also the links ML(3,9) and
`
`ML(3,10) are connected to the middle switch MS(1,1) from middle switch MS(2,3)).
`
`Each of the E middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`d
`
`connected to exactly d switches in middle stage 140 through 2Xd 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 the links ML(2,3) and ML(2,4) are connected from middle switch
`
`MS(1, 1) to middle switch MS(2,3)) and also are connected to exactly (1 output switches
`
`in output stage 120 through 2X (I links (for example the links ML(4,1) and ML(4,2) are
`
`connected to output switch OS] from middle switch MS(1,1), and the links ML(4,3) and
`
`ML(4,4) are connected to output switch 032 from middle switch MS(1,1)).
`
`Similarly each of the E middle switches MS(2,1) — MS(2,4) in the middle stage
`(I
`
`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, 1), and the links ML(2,9) and ML(2,10) are connected to the middle
`
`switch MS(2,1) from middle switch MS(1,3)), and also are connected to exactly d
`
`switches in middle stage 130 through 2 X d 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,3); and the
`
`links ML(3,3) and ML(3,4) are connected from middle switch MS(2,1) to middle switch
`
`MS(1,1)).
`
`Each of the % output switches OSl — 034 are connected from exactly d
`
`switches in middle stage 130 through 2 Xd links (for example output switch 031 is
`
`connected from middle switch MS(1,1) through the links ML(4,1), ML(4,2); and output
`
`switch 031 is also connected from middle switch MS(1,2) through the links ML(4,5) and
`
`ML(4,6)).
`
`10
`
`15
`
`20
`
`25
`
`Page 8 of 57
`
`Page 8 of 57
`
`

`

`M—0040 US
`
`Finally the connection topology of the network 100A shown in FIG. 1A is known
`
`to be back to back inverse Benes connection topology.
`
`In other embodiments the connection topology may be different from the network
`
`100A of FIG. 1A. 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 one embodiment is illustrated, in general, the
`
`network leinkibfl (N, d, s) can comprise any arbitrary type of connection topology. For
`
`example the connection topology of the network leinkibft(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 Vm
`
`linkibft
`
`(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
`
`m
`V linkibfl (N, d, s) can be built. The embodiment of FIG. 1A is only one example of
`
`network thnkwfi (N ,d , S) -
`
`In the embodiment of FIG. 1A 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 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,4)and MS(2,1) — MS(2,4) 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(2,1) — MS(2,4) are referred to as root stage switches.
`
`10
`
`15
`
`In the example illustrated in FIG. 1A, a fan-out of four is possible to satisfy a
`
`25
`
`multicast connection request if input switch is 132, 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 IS], again only a fan-out 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
`
`-9-
`
`Page 9 of 57
`
`Page 9 of 57
`
`

`

`M—0040 US
`
`connection request is satisfied. In essence, limiting the fan-out from input switch to no
`
`more than two middle switches permits the network 100A, to be operated in
`
`rearrangeably nonblocking manner in accordance with the 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,
`
`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 Multi-link
`
`Butterfly fat tree network Vmfinkibfl (N ,d , s) with (log d N) stages. The general
`
`symmetrical Multi—link Butterfly fat tree network leinkibfl (N, d , s) can be operated in
`
`rearrangeably nonblocking manner for multicast when s = 2 according to the current
`
`invention. Also the general symmetrical Multi-link Butterfly fat tree network
`
`V linkibfl (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 Multi-link Butterfly fat tree network Vmfinkibfi (N, d, s) with (logd N )
`
`stages has d inlet links for each of % input switches ISl—IS(N/d) (for example the links
`
`ILl-IL(d) to the input switch 131) and 2 Xd outgoing links for each of E input switches
`d
`
`ISl-IS(N/d) (for example the links ML(l,l) - ML(l ,2d) to the input switch 181). There
`
`are (1 outlet links for each of % output switches OSl-OS(N/d) (for example the links
`
`10
`
`15
`
`20
`
`25
`
`-10-
`
`Page 10 of 57
`
`Page 10 of 57
`
`

`

`M—0040 US
`
`OLl-OL(d) to the output switch 031) and 2X d incoming links for each of l output
`d
`
`switches OSl-OS(N/d) (for example ML(2 >< Logd N — 2,1) - ML(2 >< Long — 2,2 x d) to
`
`the output switch 031).
`
`Each of the % input switches ISl — IS(N/d) are connected to exactly d switches
`
`in middle stage 130 through 2X d links.
`
`Each of the E middle switches MS(1,1) — MS(1,N/d) in the middle stage 130 are
`d
`
`connected from exactly d input switches through 2 X d links and also are connected to
`
`exactly d switches in middle stage 140 through 2><d links.
`
`Similarly each of the E middle switches MS(l,l) — MS(1,N/d) in the middle
`d
`
`stage 130 are also connected from exactly d switches in middle stage 140 through 2>< d
`
`links and also are connected to exactly d output switches in output stage 120 through
`
`2 X d links.
`
`Similarly each of the % middle switches MS(Long —l,l) - MS(Long — l,%)
`
`in the middle stage 130 +10 * (Long — 2) are connected from exactly d switches in
`
`middle stage 130 +10 * (Long — 3) through 2X d links and also are connected to
`
`exactly d switches in middle stage 130+10*(L0ng—l) through 2><d links.
`
`Each of the % output switches 08] — OS(N/d) are connected from exactly d
`
`switches in middle stage 130 through 2 X d links.
`
`10
`
`15
`
`As described before, again the connection topology of a general leinkibft (N, d, 5)
`
`20
`
`may be any one of the connection topologies. For example the connection topology of the
`
`network thnkibfl (N, d, 5) may be back to back inverse Benes networks, back to back
`
`Omega networks, back to back Benes networks, Delta Networks and many more
`
`-11-
`
`Page 11 of 57
`
`Page 11 of 57
`
`

`

`M—0040 US
`
`combinations. The applicant notes that the fundamental property of a valid connection
`
`topology of the general leinkibfo, d,s) 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 thnkibfl (N, d , s) can be built. The embodiment of FIG. 1A
`
`are one example of network leinkibfi (N, d, s) .
`
`The general symmetrical Multi-link Butterfly fat tree network leinkibfl (N ,d , s)
`
`can be operated in rearrangeably nonblocking manner for multicast when s = 2
`
`according to the current invention. Also the general symmetrical Multi-link Butterfly fat
`
`tree network Vmfinkibfi (N ,d , s) can be operated in strictly nonblocking manner for unicast
`
`10
`
`if s = 2 according to the current invention.
`
`Every switch in the Multi-link Butterfly fat tree networks discussed herein has
`
`multicast capability.
`
`In a leimbfi (N ,d , 5) network, if a network inlet link is to be
`
`15
`
`20
`
`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 that path can be multicast within the output switch to as many outlet
`
`links as necessary. 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 , l S r S 3) although the same d1scuss1on 1s apphcable to the
`
`second type.
`
`-12-
`
`Page 12 of 57
`
`Page 12 of 57
`
`

`

`M—0040 US
`
`.
`
`.
`
`.
`
`To charactenze a mult1cast ass1gnment, for each 1nlet llnk l e {Linng}, let
`
`.
`
`.
`
`.
`
`N
`
`Il. = 0, where 0 C {LAME}, denote the subset of output switches to which inlet link i
`
`d
`
`is to be connected in the multicast assignment. For example, the network of Fig. 1A
`
`shows an exemplary three-stage network, namely leinkibfl (8,2,2) , with the following
`
`multicast assignment I] : {2,3}and all other Ij : ¢ for _] = [2-8]. It should be noted that
`
`the connection I1 fans out in the first stage switch 131 into middle switches MS(l,l) and
`
`MS(l,2) in middle stage 130, and fans out in middle switches MS(l,l) and MS(1,2) only
`
`once into output switch 032 in output stage 120 and middle switch MS(2,2) in middle
`
`stage 140 respectively.
`
`10
`
`15
`
`The connection I1 also fans out in middle switch MS(2,2) only once into middle
`
`switches MS(l,4) in middle stage 130. The connection II also fans out in middle switch
`
`MS(l,4) only once into output switch 0S3 in output stage 120. Finally the connection 11
`
`fans out once in the output stage switch 032 into outlet link 0L3 and in the output stage
`
`switch 033 twice into the outlet links 0L5 and 0L6.
`
`In accordance with the invention,
`
`each connection can fan out in the input stage switch into at most two middle stage
`
`switches in middle stage 130.
`
`Asymmetric RNB (N2 > N1) Embodiments:
`
`Referring to FIG. 1C, in one embodiment, an exemplary asymmetrical Multi—link
`
`Butterfly fat tree network 100C with three stages of sixteen 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 four, eight by twelve switches MS(l,l) - MS(l,4) and
`
`25
`
`middle stage 140 consists of four, four by four switches MS(2,1) - MS(2,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
`-13-
`
`Page 13 of 57
`
`Page 13 of 57
`
`

`

`M—0040 US
`
`switches in output stage 120 are of size eight by six, and there are four 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 four switches of size eight by twelve in middle stage 130 and four
`
`switches of size four by four in middle stage 140.
`
`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
`
`N
`of output stage 120 can be denoted in general with the variable —1, where N1 is the total
`(1
`
`number of inlet links or and N 2 is the total number of outlet links and N 2 > Nl and
`
`N7 = p * N1 Where p > 1. The number of middle switches in each middle stage is
`
`denoted by % 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 (d + d2) * d2, where al2 = N2 Xi = p X (Z . The size of each switch in middle
`N1
`
`stage 130 can be denoted as 4d * 2(d + d2) . The size of each switch in the root stage
`
`(i.e., middle stage140) can be denoted as 2d * 2d . The size of each switch in all the
`
`middle stages excepting middle stage 130 and root stage can be denoted as 4d * 4d (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 2d * 4d and 2d * 2d 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,3), ML(3,4), ML(3,9) and ML(3,10) are never setup to the up going
`
`middle links ML(2,1), ML(2,2), ML(2,3) and ML(2,4) for the middle switch MS(1,1). So
`
`middle switch MS(1,1) can be implemented as a four by eight switch with middle links
`
`ML(1,1), ML(1,2), ML(1,5) and ML(1,6) as inputs and middle links ML(2,1), ML(2,2),
`
`ML(2,3), ML(2,4), ML(4,1), ML(4,2), ML(4,3), and ML(4,4) as outputs; and a four by
`
`four switch with middle links ML(3,3), ML(3,4), ML(3,9) and ML(3,10) as inputs and
`
`middle links ML(4,1), ML(4,2), ML(4,3), and ML(4,4) as outputs).
`
`-14-
`
`10
`
`15
`
`20
`
`Page 14 of 57
`
`Page 14 of 57
`
`

`

`M—0040 US
`
`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
`
`Multi-link Butterfly fat tree network can be represented with the notation
`
`Vmlinki
`
`bfi (Nl , 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 N2 > N1 , and s is the ratio of number of outgoing links from
`
`each input switch to the inlet links of each input switch.
`
`Each of the —1 input switches [31 , IS4 are connected to exactly d switches in
`d
`
`middle stage 130 through 2 X d links (for example input switch 131 is connected to
`
`middle switch MS(1,1) through the links ML(1,1) and ML(1,2), and input switch 131 is
`
`also connected to MS(1,2) through the links ML(1,3) and ML(1,4)).
`
`Each of the fi 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(1,1) and ML(1,2) are connected to the middle switch MS(1,1) from input switch 131
`
`and the links ML(1,5) and ML(1,6) are connected to the middle switch MS(1,1) from
`
`input switch 132) and are also connected from exactly (1 switches in middle stage 140
`
`through 2X d links (for example the links ML(3,3) and ML(3,4) are connected to the
`
`middle switch MS(1,1) from middle switch MS(2,1), and the links ML(3,9) and
`
`ML(3,10) are connected to the middle switch MS(1,1) from middle switch MS(2,3)).
`
`10
`
`15
`
`20
`
`Similarly each of the fi middle switches MS(1,1) — MS(1,4) in the middle stage
`d
`
`130 are connected to exactly d switches in middle stage 140 through 2 X 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 the links ML(2,3) and ML(2,4) are connected from middle
`
`25
`
`switch MS(1, 1) to middle switch MS(2,3)), and also are connected to exactly % output
`
`switches in output stage 120 through al2 links (for example the links ML(4,1) and
`
`-15-
`
`Page 15 of 57
`
`Page 15 of 57
`
`

`

`M—0040 US
`
`ML(4,2) are connected from middle switch MS(1,1) to output switch 051; the links
`
`ML(4,3) and ML(4,4) are connected from middle switch MS(1,1) to output switch 082;
`
`the links ML(4,4) and ML(4,6) are connected from middle switch MS(] ,1) to output
`
`switch 083; and the links ML(4,7) and ML(4,8) are connected from middle switch
`
`MS(1, 1) to output switch 034).
`
`Similarly each of the £ middle switches MS(2,1) — MS(2,4) in the middle stage
`d
`
`140 are connected from exactly d switches in middle stage 130 through 2X d links (for
`
`example the links ML(2,1) and ML