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 U.S.
`
`Provisional Patent Application Docket No. M-0037USentitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS"by Venkat Kondaassigned to the same
`
`10
`
`assignee as the current application,filed concurrently.
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0038USentitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE NETWORKS"by Venkat Konda assigned
`
`to the same assignee as the current application, filed concurrently.
`
`15
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0039USentitled "FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTI
`
`STAGE NETWORKS"by Venkat Kondaassigned to the same assignee as the current
`
`application, filed concurrently.
`
`20
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0041USentitled "FULLY CONNECTED
`
`GENERALIZED FOLDED MULTI-STAGE NETWORKS"by Venkat Kondaassigned
`
`to the same assignee as the current application, filed concurrently,
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0042USentitled "FULLY CONNECTED
`
`GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULTISTAGE
`
`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 U.S.
`
`Provisional Patent Application Docket No. M-0045USentitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED NETWORKS"by Venkat Konda assigned to
`
`the same assigneeas 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 V,,j.-4;,(N,d,5) having inverse Benes connection topology of five stages
`
`10
`
`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 Vinca (N,d,2) with (logaN) stages strictly nonblocking network for unicast
`
`15
`
`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 Vin(N,,N>,d,2) having inverse Benes connection topology of five
`
`stages with N; = 8, No = p* Ni = 24 where p = 3, and d = 2 with exemplary multicast
`
`20
`
`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 V,jin.o¢(N,,N>,d,2) with No = p* Ni and with (logaN) stages strictly
`
`25
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`Page 2 of 57
`
`Page 2 of 57
`
`

`

`M-0040 US
`
`FIG, 1E is a diagram 100E of an exemplary asymmetrical multi-link Butterfly fat
`
`tree network Vyvineo¢ (N,,N,,d,2) having inverse Benes connection topology of five
`
`stages with N» = 8, N; = p* No= 24, where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1F is a diagram 100F of a general asymmetrical multi-link Butterfly fat tree
`network V,ji.o¢(N,,N>,d,2) with N; = p* No and with (log, 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
`
`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
`
`20
`
`offer large scale crosspoint reduction when configured with optimal links as disclosed in
`
`this invention.
`
`Whena transmitting device simultaneously sends information to more than one
`
`receiving device, the one-to-many connection required between the transmitting device
`
`and the receiving devices is called a multicast connection. A set of multicast connections
`
`25
`
`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 devicesis called a
`
`broadcast connection.
`
`In general, a multicast connection is meant to be one-to-many connection, which
`
`includes unicast and broadcast connections. A multicast assignment in a switching
`
`networkis nonblocking if any of the available inlet links can always be connected to any
`
`of the available outlet links.
`
`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
`
`10
`
`rearranging someof 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 besatisfied without blocking with never needing to rearrange anyof the
`
`previous connection requests.
`
`15
`
`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 someof 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 anyof 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 forarbitrary fan-out multicast and
`
`25
`
`unicast for generalized multi-stage networks V(N,,N.,d,s5) with numerous connection
`
`topologies and the scheduling methods are described in detail in U.S. Provisional Patent
`
`Application, Attorney Docket No. M-0037 USthat is incorporated by reference above.
`
`4.
`
`Page 4 of 57
`
`Page 4 of 57
`
`

`

`M-0040 US
`
`2) Strictly and rearrangeably nonblocking forarbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks V,,(N,,N,,d,s) with numerous
`
`connection topologies and the scheduling methodsare described in detail in U.S.
`
`Provisional Patent Application, Attorney Docket No. M-0038 US that is incorporated by
`
`reference above.
`
`3) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`Vink (N1»N>,d,5) and generalized folded multi-link multi-stage networks
`
`Vjott-miine (N;,N,.d,5) with numerous connection topologies and the scheduling methods
`
`10
`
`are described in detail in U.S. Provisional Patent Application, Attorney Docket No. M-
`
`0039 USthat is incorporated by reference above.
`
`4) Strictly and rearrangeably nonblockingfor arbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks V,.,(NV,,N,,d,5) with numerous
`
`connection topologies and the scheduling methods are described in detail in U.S.
`
`15
`
`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 V,,,,,.(N,,N,,d,s) and generalized folded multi-link multi-stage
`
`networksVig-mtine(Ni,N,,d, 5) with numerous connection topologies and the scheduling
`
`20
`
`methodsare described in detail in U.S. Provisional Patent Application, Attorney Docket
`
`No. M-0042 USthatis incorporated by reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N,,N,,d,5), generalized
`
`folded multi-stage networks V,,(N,,N,,d,5), generalized butterfly fat tree networks
`
`Vig(N,,N,,d,s), generalized multi-link multi-stage networks V,,,.,(N,,N,,d,8),
`
`25
`
`generalized folded multi-link multi-stage networks Vg14-nine(N1,N>2,d,5), generalized
`
`multi-link butterfly fat tree networks V,,j,.-4,(N,,N.,d,5), and generalized hypercube
`
`networks V,_,,(N,,N,,d,5) for s = 1,2,3 or any numberin general, are described in
`
`-5-
`
`Page 5 of 57
`
`Page 5 of 57
`
`

`

`M-0040 US
`
`detail in U.S. Provisional Patent Application, Attorney Docket No. M-0045 USthatis
`
`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
`
`10
`
`switches IS1-IS4 and output stage 120 consists of four, four by two switches OS1-OS4.
`
`And all the middle stages excepting root stage namely middle stage 130 consists of four,
`
`eight by eight switches MS(1,1) - 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 mannerfor unicast
`
`15
`
`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 110 are of size two by four, the switches in output stage 120 are of size four
`
`20
`
`by two, and there are four switches in each of middle stage 130 and middle stage 140.
`
`In one embodimentof this network each of the input switches IS1-IS4 and output
`
`switches OS1-OS4 are crossbar switches. The number of switches of input stage 110 and
`
`of output stage 120 can be denoted in general with the variable - , where N is the total
`
`numberofinlet links or outlet links. The number of middle switches in each middle stage
`
`25
`
`is denoted by * . The size ofeach input switch IS1-IS4 can be denoted in general with
`
`the notation d*2d and each output switch OS1-OS4can be denoted in general with the
`
`notation 2d *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(1,1). So middle switch MS(1, 1) can be
`
`implemented as a four by eight switch with middle links ML(1,1), ML(,2), ML(1,5) and
`
`ML(1,6) as inputs and middle links ML(2,1), ML(2,2), ML(2,3), ML@,4), ML(@.1),
`
`10
`
`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
`
`15
`
`or a network of switches. A symmetric Multi-link Butterfly fat tree network can be
`
`represented with the notation V,,j,._4;(N,d,5), where N represents the total number of
`
`inlet links of all input switches (for example the links IL1-IL8), d represents the inlet
`
`links of each input switch or outlet links of each output switch, and s is the ratio of
`
`numberof outgoing links from each input switch to the inlet links of each input switch.
`
`20
`
`Althoughit is not necessary that there be the same numberofinlet links IL1-IL8 as there
`
`are outlet links OL1-OL8, in a symmetrical network they are the same.
`
`Eachof the - input switches IS1 — IS4 are connected to exactly d switches in
`
`middle stage 130 through 2xd links (for example input switch IS1 is connected to
`
`middle switch MS(1,1) through the links ML(1,1) and ML(1,2); and input switch IS1 is
`
`25
`
`also connected to middle switch MS(1,2) through the links ML(1,3) and ML(1,4)).
`
`Each ofthe ot middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`
`connected from exactly d input switches through 2xd links (for example the links
`
`ML(1,1) and ML(1,2) are connected to the middle switch MS(1,1) from input switch IS1;
`
`-7-
`
`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 2xd links (for example the links ML(3,3) and ML(@,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)).
`
`Eachof the
`
`middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`
`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
`
`10
`
`MS(1,1) to middle switch MS(,3)) and also are connected to exactly d output switches
`
`in output stage 120 through 2x d links (for example the links ML(4,1) and ML(4,2) are
`
`connected to output switch OS1 from middle switch MS(1,1), and the links ML(4,3) and
`
`ML(4,4) are connected to output switch OS2 from middle switch MS(1,1)).
`
`Similarly each of the = middle switches MS(2,1) — MS(2,4) in the middle stage
`
`15
`
`140 are connected from exactly d switches in middle stage 130 through 2xd_ 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(Q,1) from middle switch MS(1,3)), and also are connected to exactly d
`
`switches in middle stage 130 through 2xd links (for example the links ML(3,1) and
`
`20
`
`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)).
`
`Eachofthe = output switches OS1 —- OS4 are connected from exactly d
`
`switches in middle stage 130 through 2xd links (for example output switch OS1 is
`
`25
`
`connected from middle switch MS(1,1) through the links ML(4,1), ML(4,2); and output
`
`switch OS1 is also connected from middle switch MS(1,2) through the links ML(4,5) and
`
`ML(4,6)).
`
`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 embodimentisillustrated, in general, the
`
`network Vi...;(N,d,5) can comprise any arbitrary type of connection topology. For
`
`example the connection topology of the network V,,,,_4;(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 topologyofthe V,,i.Ȣ(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 tine(Nd, 5) can be built. The embodimentof FIG. 1A is only one example of
`
`network V,jineop (Nd,5) «
`
`15
`
`In the embodiment of FIG. 1A each of the links ML(1,1) - ML(,16), ML(Q,1) -
`
`ML(2,16), ML(3,1) -ML(,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 IS1-IS4 are also referred to as the network input ports. The input stage 110 is
`
`often referred to as thefirst stage. The output switches OS1-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(,4) are referred to as root stage switches.
`
`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 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 [S1, again onlya fan-out of two is used. The
`
`specific middle switches that are chosen in middle stage 130 whenselecting a fan-out of
`
`twois 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 requestis 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 mannerin 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 tosatisfy the request. Moreover,
`
`although in the above-described embodimenta 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
`
`10
`
`on the number of middle stage switches in a network (while maintaining the
`
`rearrangeably nonblocking nature of operation of the network for multicast connections).
`
`Howeveranyarbitrary 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:
`
`15
`
`Network 100B of FIG. 1B is an example of general symmetrical Multi-link
`Butterflyfat tree network V,jinno¢(N.d,5) with (log, N) stages. The general
`
`symmetrical Multi-link Butterfly fat tree network V,j4.,4 (N,d,5) 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
`
`20
`
`V nineon (N,d,8) can be operated in strictly nonblocking mannerfor unicastif
`
`s = 2 according to the current invention. (And in the example of FIG. 1B, s = 2). The
`general symmetrical Multi-link Butterfly fat tree network Vj,4,(N,d,5) with (log, N)
`stages has d inlet links for each of - input switches IS1-IS(N/d) (for example the links
`IL1-IL(d) to the input switch IS1) and 2xd_ outgoing links for each of = input switches
`
`25
`
`IS1-ISCN/d) (for example the links ML(1,1) - ML(1,2d) to the input switch IS1). There
`
`are d outlet links foreach of = output switches OS1-OS(N/d) (for example the links
`
`-10-
`
`Page 10 of 57
`
`Page 10 of 57
`
`

`

`M-0040 US
`
`OL1-OL(d) to the output switch OS1) and 2xd incominglinks for each of
`
`output
`
`switches OS1-OS(N/d) (for example ML(2x Log ,N —2,1)- ML(2x Log ,N —2,2xd) to
`
`the output switch OS1).
`
`Eachofthe - input switches ISI — ISCN/d) are connected to exactly d switches
`
`in middle stage 130 through 2xd links.
`
`Eachofthe ot middle switches MS(1,1) - MS(1,N/d) in the middle stage 130 are
`
`connected from exactly d input switches through 2d links and also are connected to
`
`exactly d switches in middle stage 140 through 2xd links.
`
`Similarly each of the 7 middle switches MS(1,1) - MS(1,N/d) in the middle
`
`10
`
`stage 130 are also connected from exactly d switches in middle stage 140 through 2x d
`
`links and also are connected to exactly d output switches in output stage 120 through
`
`2xd links.
`
`Similarly each of the - middle switches MS(Log,N—-1,1) - MS(Log,N- La)
`
`in the middle stage 130+10*(Log,N —2) are connected from exactly d switches in
`
`15
`
`middle stage 130+10*(Log,N —3) through 2xd links and also are connected to
`
`exactly d switches in middle stage 130+10* (Log ,N —1) through 2xd_ links.
`
`Each ofthe ot output switches OS1 — OS(N/d) are connected from exactly d
`
`switches in middle stage 130 through 2xd links.
`
`As described before, again the connection topology of a general V44 (N.d,5)
`
`20
`
`may be any one of the connection topologies. For example the connection topology of the
`
`network V,i.»;(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
`
`topologyof the general V,,,,.,4,(N,d,s) network is, when no connectionsare setup from
`
`any input link if any output link should be reachable. Based on this property numerous
`
`embodiments of the network V,in-Ȣ(N.d,5) can be built. The embodiment of FIG. 1A
`
`are one example of network V,,i,4;(N.d,5) .
`
`The general symmetrical Multi-link Butterfly fat tree network V,,,,44;,(N.d,5)
`
`can be operated in rearrangeably nonblocking mannerfor multicast when s = 2
`
`according to the current invention. Also the general symmetrical Multi-link Butterfly fat
`
`tree network V,ji.4¢(N,d,5) 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. Ina V,,,.4,(N.d,s) network,if a networkinletlink 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
`
`15
`
`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
`
`20
`
`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 (with fan-out r', 1<r'< 7 although the same discussion is applicable to the
`
`second type.
`
`-|2-
`
`Page 12 of 57
`
`Page 12 of 57
`
`

`

`M-0040 US
`
`To characterize a multicast assignment, foreach inlet link i€ {Bonn let
`I, =O, where Oc {hdl denote the subset ofoutput switches to whichinlet link i
`
`is to be connected in the multicast assignment. For example, the network of Fig. 1A
`
`shows an exemplary three-stage network, namely V,,ji.» (8,2,2) , with the following
`multicast assignment 7, = {2,3}and all other [; =@ forj = [2-8]. It should be notedthat
`
`the connection 7, fans outin the first stage switch IS1 into middle switches MS(1,1) and
`
`MS(1,2) in middle stage 130, and fans out in middle switches MS(1,1) and MS(1,2) only
`
`once into output switch OS2 in output stage 120 and middle switch MS(2,2) in middle
`
`stage 140 respectively.
`
`10
`
`The connection /, also fans out in middle switch MS(2,2) only once into middle
`
`switches MS(1,4) in middle stage 130. The connection /, also fans out in middle switch
`
`MS(1,4) only once into output switch OS3 in output stage 120. Finally the connection J,
`
`fans out once in the output stage switch OS2 into outlet link OL3 andin the output stage
`
`switch OS3 twiceinto the outlet links OLS and OL6.
`
`In accordancewith the invention,
`
`15
`
`each connection can fan out in the input stage switch into at most two middle stage
`
`switches in middle stage 130.
`
`Asymmetric RNB (Nz > Ni) Embodiments:
`
`Referring to FIG. 1C, in one embodiment, an exemplary asymmetrical Multi-link
`
`Butterfly fat tree network 100C with three stages of sixteen switchesfor 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 IS1-IS4 and output stage 120 consists of four, eight by six switches OS1-OS4.
`
`Middle stage 130 consists of four, eight by twelve switches MS(1,1) - MS(1,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 mannerfor unicast
`
`connections, because the switches in the input stage 110 are of size two by four, the
`-|3-
`
`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 mannerfor 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 embodimentof this network each of the input switches IS1-IS4 and output
`
`switches OS1-OS4are crossbar switches. The numberof switches of input stage 110 and
`
`.
`N,
`of output stage 120 can be denoted in general with the variable 7 where WN,
`
`.
`isthe total
`
`10
`
`numberofinlet links or and N,, is the total numberof outlet links and N, > N, and
`
`N, = p*N, where p> 1. The number of middle switches in each middle stageis
`
`denoted by =. The size ofeach input switch IS1-IS4 can be denoted in general with the
`
`notation d *2d and each output switch OS1-OS4 can be denoted in general with the
`
`notation (d +d,)*d,, where d, = N, xo = pXd. Thesize ofeach switch in middle
`
`1
`
`15
`
`stage 130 can be denoted as 4d * 2(d +d.,). The size of each switch in the root stage
`
`(i.e., middle stage140) can be denoted as 2d * 2d . The size of each switchin 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
`
`20
`
`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), 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-
`
`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
`
`V,intine-o (N,N>,d,8), where N, represents the total numberofinletlinks of all input
`
`switches (for example the links IL1-IL8), N, represents the total numberof outlet links
`
`of all output switches (for example the links OL1-OL24), d represents the inlet links of
`
`each input switch where N, > WN,
`
`, and s is the ratio of numberof outgoing links from
`
`each input switch to the inlet links of each input switch.
`
`Eachofthe “ input switches IS1 —IS4 are connected to exactly d switches in
`
`10
`
`middle stage 130 through 2xd links (for example input switch IS1 is connected to
`
`middle switch MS(1,1) through the links ML(1,1) and ML(1,2), and input switch IS1 is
`
`also connected to MS(1,2) through the links ML(1,3) and ML(1,4)).
`
`Each ofthe “ middle switches MS(1,1) — MS(1,4) in the middle stage 130 are
`
`connected from exactly d input switches through 2xd links (for example the links
`
`15
`
`ML(1,1) and ML(1,2) are connected to the middle switch MS(1,1) from input switch IS1
`
`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 2xd_ 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
`
`20
`
`ML(3,10) are connected to the middle switch MS(1,1) from middle switch MS(2,3)).
`
`Similarly each of the “1 middle switches MS(1,1) — MS(1,4) in the middle stage
`
`130 are 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
`
`25
`
`switch MS(1,1) to middle switch MS(@,3)), and also are connected to exactly = output
`
`switches in output stage 120 through d, 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 OS1; the links
`
`ML(4,3) and ML(4,4) are connected from middle switch MS(1,1) to output switch OS2;
`
`the links ML(4,4) and ML(4,6) are connected from middle switch MS(1,1) to output
`
`switch OS3; and the links ML(4,7) and ML(4,8) are connected from middle switch
`
`MS(1,1) to output switch OS4).
`
`Similarly each of the = middle switches MS(2,1) — MS(2,4) in the middle stage
`
`140 are connected from exactly d switches in middle stage 130 through 2xd_links (for
`
`example the links ML(2,1) and ML(,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
`
`10
`
`switch MS(Q,1) from middle switch MS(1,3)) and also are connected to exactly d
`
`switches in middle stage 130 through 2xd links (for example the links ML(3,3) and
`
`ML(3,4) are connected from middle switch MS(2,1) to middle switch MS(1,1); and the
`
`links ML(3,1) and ML(3,2) are connected from middle switch MS(2,1) to middle switch
`
`MS(1,3)).
`
`15
`
`E