M-0038 US
`
`FULLY CONNECTED GENERALIZED 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
`
`assignee as the current application,filed concurrently.
`
`10
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0039USentitled "FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTI-
`
`STAGE NETWORKS"by Venkat Kondaassigned to the same assignee as the current
`
`application, filed concurrently.
`
`15
`
`This application is related to and incorporates by referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0040USentitled "FULLY CONNECTED
`
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS"by Venkat
`
`Kondaassigned to the same assignee as the current application, filed concurrently.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`20
`
`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
`
`NETWORKS"by Venkat Konda assigned to the same assignee as the current application,
`
`filed concurrently.
`
`-|-
`
`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 referencein its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0045USentitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED NETWORKS"by Venkat Kondaassigned to
`
`the same assignee as the current application, filed concurrently.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary Symmetrical Butterfly fat tree
`
`network V,,, (N,d,s) 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
`Vi,(N,d,s) with (logaN) stages strictly nonblocking network for unicast connections
`
`and rearrangeably nonblocking network for arbitrary fan-out multicast connections in
`
`accordance with the invention.
`
`15
`
`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
`
`N, =8, Nz = p* N; = 24 where p = 3, and d = 2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`20
`
`FIG. 1D is a diagram 100D of a general asymmetrical Butterfly fat tree network
`Vig(N,,N>,d,2) with No = p* N; 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.
`
`FIG. 1E is a diagram 100E of an exemplary Asymmetrical Butterfly fat tree
`
`network V,,(N,,N,,d,2) having inverse Benes connection topology of three stages with
`
`No = 8, N; = p* No= 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
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1F is a diagram 100F of a general asymmetrical Butterfly fat tree network
`Vig(N,,N>.d.2) with N; = p* No and with (logiN) 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,pn (N. d,s) 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
`Vig(Nd,s) with (log, 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
`
`15
`
`network V,,(N,,N,,d.1) having inverse Benes connection topology ofthree stages with
`
`N; = 8, No = p* N; = 24 where p = 3, and d = 2 with exemplary unicast connections
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`FIG, 2D is a diagram 200D of a general asymmetrical Butterfly fat tree network
`Vi;(N,,N.,d,1) with No = p* N; and with (logiN) stages rearrangeably nonblocking
`
`20
`
`network for unicast connections in accordance with the invention.
`
`FIG. 2E is a diagram 200E of an exemplary Asymmetrical Butterfly fat tree
`
`network V,,(N,,N,,d,1) having inverse Benes connection topology ofthree stages with
`
`No = 8, N; = p* No = 24, where p = 3, and d = 2 with exemplary unicast connections
`
`25
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`Page 3 of 83
`
`Page 3 of 83
`
`

`

`M-0038 US
`
`FIG, 2F is a diagram 200F of a general asymmetrical Butterfly fat tree network
`Vig(Ni,N.,d,1) with N; = p* Np and with (log, 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
`
`The present invention is concerned with the design and operation of large scale
`
`10
`
`crosspoint reduction using arbitrarily large Butterfly fat tree networks for broadcast,
`
`unicast and multicast connections. Particularly Butterfly fat tree networks with stages
`
`morethan or equal to three and radices greater than or equal to two offer large scale
`
`crosspoint reduction when configured with optimallinks as disclosed in this invention.
`
`Whena transmitting device simultaneously sends information to more than one
`
`15
`
`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
`
`20
`
`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
`
`25
`
`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 inletlink 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, 1.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
`
`10
`
`request of unicast from aninlet 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:
`
`15
`
`1) Strictly and rearrangeably nonblocking forarbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks V(N,,N.,,d,s) with numerous connection
`
`topologies and the scheduling methods are described in detail in U.S. Provisional Patent
`
`Application, Attorney Docket No. M-0037 USthat is incorporated by reference above.
`
`2) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`20
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`Vnine (N{»N>,d,5) and generalized folded multi-link multi-stage networks
`
`Vfold—mink (N,,N,,d,8) with numerous connection topologies and the scheduling methods
`
`are described in detail in U.S. Provisional Patent Application, Attorney Docket No. M-
`
`0039 USthat 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 Vin.44(N,,.N2.d,5) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`Page 5 of 83
`
`Page 5 of 83
`
`

`

`M-0038 US
`
`U.S. Provisional Patent Application, Attorney Docket No. M-0040 USthatis
`
`incorporated by reference above.
`
`4) Strictly and rearrangeably nonblockingfor arbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks V,,(N,.N,.d.s5) with numerous
`
`connection topologies and the scheduling methods are described in detai] in U.S.
`
`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
`
`10
`
`networks Vinsmtine(N;,N,,d,5) with numerous connection topologies and the scheduling
`
`methods are described in detail in U.S. Provisional Patent Application, Attorney Docket
`
`No. M-0042 USthat is incorporated by reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N,,N,,d,5), generalized
`
`15
`
`folded multi-stage networks V,.,(N,,N,,d,s), generalized butterfly fat tree networks
`Vor (N,,N,,d,s), generalized multi-link multi-stage networks V,THtin (N,.N>,d,8),
`generalized folded multi-link multi-stage networks V,01ta_mtine (N1,N>,d,8), generalized
`
`multi-link butterfly fat tree networks Vnlink—bft (N,,N,,d,s5), and generalized hypercube
`
`networksV,_,,.(NV,,N,,d,s) for s = 1,2,3 or any numberin general, are described in
`
`detail in U.S. Provisional Patent Application, Attorney Docket No. M-0045 USthatis
`
`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 whereinput stage 110 consists of four, two by four
`
`switches IS1-IS4 and output stage 120 consists of four, four by two switches OS1-OS4.
`
`-6-
`
`Page 6 of 83
`
`Page 6 of 83
`
`

`

`M-0038 US
`
`Andall the middle stages excepting root stage namely middle stage 130 consists of eight,
`
`four by four switches MS(1,1) - MS(,8), and root stage i.e., middle stage 140 consists of
`
`eight, two by two switches MS(2,1) - MS(@,8).
`
`Such a network can be operated in strictly non-blocking mannerfor unicast
`
`connections, because the switches in the input stage 110 are of size two by four, the
`
`switches in output stage 120 are of size four by two, and there are eight switches in each
`
`of middle stage 130 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 embodimentof this network each of the input switches [S1-IS4 and output
`
`switches O$1-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
`
`15
`
`is denoted by 2x7 . The size of each input switch IS1-IS4 can be denoted in general
`
`with the notation d *2d and each output switch OS1-OS4 can be denoted in general with
`
`the notation 2d *d. Likewise, the size of each switch in any of the middle stages can be
`
`denoted as 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
`
`20
`
`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(1, 1).
`
`So middle switch MS(1,1) can be implemented as a two by four switch with middle links
`
`25
`
`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).
`
`Middle stage 140 is called as root stage. A switch as used herein can beeither a
`
`crossbar switch, or a network of switches each of which in turn may be a crossbar switch
`-J-
`
`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 V,, (N,d,s), where N represents the total numberofinlet links of all input
`
`switches (for example the links IL1-IL8), d represents the inlet links of each input switch
`
`or outlet links of each output switch, and s is the ratio of number of outgoing links from
`
`each input switch to the inlet links of each input switch, Althoughit is not necessary that
`
`there be the same numberofinlet links IL1-IL8 asthere are outlet links OL1-OL8, in a
`
`symmetrical network they are the same.
`
`Eachofthe ] input switches IS1 — IS4 are connected to exactly 2xd switches
`
`in middle stage 130 through 2xd links (for example input switch IS1 is connected to
`
`10
`
`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).
`
`Eachofthe 2x— middle switches MS(1,1) — MS(1,8) in the middle stage 130
`
`are connected from exactly d input switches through d links (for example the links
`
`ML(1,1) and ML(1,5) are connected to the middle switch MS(1,1) from input switch IS1
`
`15
`
`and IS2 respectively) and are also connected from exactly d switches in middle stage
`
`140 through d links (for example the links ML(3,1) and ML(3,6) are connected to the
`
`middle switch MS(1,1) from middle switches MS(2,1) and MS(2,3) respectively).
`
`Eachofthe 2x— 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
`
`20
`
`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 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 OS1 and OS2 respectively from middle
`
`switches MS(1,1)).
`
`25
`
`Similarly each of the ax— 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-
`
`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 d switches in middle stage 130 through d links (for example the links ML@G,1)
`
`and ML(3,2) are connected from middle switch MS(,1) to middle switch MS(1,1) and
`
`MS(1,3) respectively).
`
`Eachof the = output switches OS1 —- OS4 are connected from exactly 2xd
`
`switches in middle stage 130 through 2?xd links (for example output switch OS1 is
`
`connected from middle switches MS(1,1), MS(1,2), MSC1,5) and MS(1,6) through the
`
`links ML(4,1), ML(4,3), ML(4,9) and ML(4,11) respectively).
`
`10
`
`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
`
`topologyis different. That is the way the links ML(1,1) - ML(1,16), ML(2,1) - ML(@,16),
`
`ML(3,1) - ML(3,16), and ML(4,1) - ML(4,16) are connected between the respective
`
`15
`
`stages is different. Even though only three embodiments are illustrated, in general, the
`
`network V,na (Nd, 5) Can comprise any arbitrary type of connection topology. For
`
`example the connection topology of the network V,,(NV,d,s) 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 V,,(N,d,s) network is, when
`
`20
`
`no connectionsare setup from any inputlink all the output links should be reachable.
`
`Based on this property numerous embodiments of the network V,,,(N,d,s) can be built.
`
`The embodiments of FIG. 1A, FIG. 1A1, and FIG, 1A2 are only three examples of
`
`network Vig (N,d,s).
`
`In the three embodiments of FIG. 1A, FIG. 1A1 and FIG. 1A2, each of the links
`
`25
`
`ML(,1) —- ML(,16), ML(2,1) - ML@,16), ML(3,1) - MLG,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 [$1-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 O$1-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,1) — MS@,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 FIGIAI, 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-outof three is
`
`possible for a multicast connection request if the input switch is IS1, 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 twois 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 oneis 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 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
`
`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 anyarbitrary 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 V,,(N.d,s) with (log aN ) stages. The general symmetrical Butterflyfat tree
`bf
`
`network V,ng (N, d,s) can be operated in rearrangeably nonblocking mannerfor 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 V,nx (N, d,s) 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 Butterfly fat tree network V,,(N,d,s) with (log aN ) stages has d
`of
`inlet links for each of - input switches [S1-IS(N/d) (for example the links IL1-IL(d) to
`the input switch IS1) and 2xd outgoing links for each of = input switches [IS1-IS(N/d)
`
`(for example the links ML(1,1) - ML(1,2d) to the input switch IS1). There are d outlet
`
`links for each of - output switches O$1-OS(N/d) (for example the links OL1-OL(d) to
`
`the output switch OS1) and 2xd incoming links for each of
`
`output switches OS1-
`
`10
`
`OS(N/d) (for example ML(2 x Log, N —2,1)- ML(2x Log, N —2,2Xd) to the output
`
`switch OS1).
`
`Eachofthe ] input switches IS1 — IS(N/d) are connected to exactly 2xd
`
`switches in middle stage 130 through 2xd links (for example input switch IS1 is
`
`connected to middle switches MS(1,1) - MS(1,d) through the links ML(1,1) - ML(1,d)
`
`15
`
`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.
`
`Eachofthe 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.
`
`20
`
`similarly each of the ax— 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.
`
`-l[1-
`
`Page 11 of 83
`
`Page 11 of 83
`
`

`

`M-0038 US
`
`Similarly each of the 2x2 middle switches MS(Log,N—-1,]) -
`MS(Log,N -1,2=) in the middle stage 130+10*(Log,N—2) are connected from
`
`a
`
`exactly d switches in middle stage 130+10*(Log,N —3) through d links and also are
`
`connected to exactly d switches in middle stage 130+10* (Log ,,N —1) through d links.
`
`Eachof the - output switches OS1 — OS(N/d) are connected from exactly 2x d
`
`switches in middle stage 130 through 2xd links.
`
`As described before, again the connection topology ofa general V,,(N,d,s) may
`
`be any one of the connection topologies. For example the connection topology of the
`
`network Vor (N,d,s) may be back to back inverse Benes networks, back to back Omega
`
`10
`
`networks, back to back Benes networks, Delta Networks and many more combinations.
`
`The applicant notes that the fundamental property of a valid connection topology ofthe
`
`general V,,(N,d,s) network is, when no connections are setup from any inputlink if any
`
`output link should be reachable. Based on this property numerous embodiments of the
`
`network Vig (N,d,s) can be built. The embodiments of FIG. 1A, FIG, 1A1, and FIG.
`
`15
`
`1A2 are three examples of network Vig (N,d,s).
`
`The general symmetrical Butterfly fat tree network V,,(N,d,s) can be operated
`
`in rearrangeably nonblocking mannerfor multicast when s = 2 according to the current
`
`invention. Also the general symmetrical Butterfly fat tree network V,,(N,d,s) can be
`
`operated in strictly nonblocking mannerfor unicast if s = 2 according to the current
`
`20
`
`invention.
`
`Every switch in the Butterfly fat tree networks discussed herein has multicast
`
`capability. Ina V,,(N.d,s) network, if a networkinlet link is to be connected to more
`
`than one outlet link on the same output switch, then itis 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 switchesis said to have fan-out r'. If all multicast assignments of a
`
`first type, wherein anyinlet 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 anyinlet 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 connectionsofthe first type (with fan-out r', 1<r's 7?
`
`although the same discussion is applicable to the second type.
`
`10
`
`.
`
`.
`
`.
`
`To characterize a multicast assignment, for each inlet link ieé Len , let
`I, =O, where Oc {ident denote the subset ofoutput switches to whichinlet link 7
`
`. a.
`
`N
`
`is to be connected in the multicast assignment. For example, the network of Fig. 1A
`
`shows an exemplary three-stage network, namely V,,(8,2,2), with the following
`
`multicast assignment J, = {2,3}and all other 7; =¢@ forj = [2-8]. It should be noted that
`
`15
`
`the connection /, fans out in the first stage switch IS1 into middle switches MS(1,1) and
`
`MS(1,5) in middle stage 130, and fans out in middle switches MS(1,1) and MS(1,5) only
`
`onceinto output switch OS2 in output stage 120 and middle switch MS(Q,7) in middle
`
`stage 140 respectively.
`
`The connection /, 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 J, also
`
`fans out in middle switch MS(1,7) only once into output switch OS3 in output stage 120.
`
`Finally the connection /, fans out once in the output stage switch OS2 into outlet link
`
`OL3 and in the output stage switch OS3 twice into the outlet links OLS and OL6.
`
`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 (N2 > Ni) 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 IS1-IS4 and output stage 120 consists of four, eight by six switches OS1-OS4.
`
`Middle stage 130 consists of eight, four by six switches MS(1,1) - MS(1,8) and middle
`
`stage 140 consists of eight, two by two switches MS(2,1) - MS(@,8).
`
`10
`
`Such a network can be operated in strictly non-blocking mannerfor unicast
`
`connections, because the switches in the input stage 110 are of size two by four, the
`
`switches in output stage 120 are of size 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 mannerfor multicast connections, because the switches in the
`
`15
`
`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 embodimentof this network each of the input switches IS1-IS4 and output
`
`switches OS1-OS4are crossbar switches. The number of switches of input stage 110 and
`
`20
`
`ofoutput stage 120 can be denoted in general with the variable =, where WN,
`
`isthe total
`
`numberofinlet links or and NV, is the total numberof outlet links and N, > N, and
`
`N, = p* WN, where p> 1. The numberof middle switches in each middle stage is
`
`denoted by 2on . 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 (d+d,)*d , where d, =N, a = pxd. Thesize of each switch in middle
`
`1
`
`stage 130 can be denoted as 2d *(d +d.,). The size of each switch in the root stage (Le.,
`
`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 * 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 d *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), ML(4,1) and ML(4.2) as outputs; and a two by two switch with
`
`10
`
`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 Via (N,,N.,d,5), where
`
`15
`
`N, represents the total numberof inletlinks of all input switches (for example the links
`
`IL1-IL8), 4. 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,>N, ,and s is the ratio of number of outgoing links from each input switch to the
`
`inlet links of each input switch.
`
`20
`
`Each ofthe - input switches IS] —I1S4 are connected to exactly 2xd switches
`
`in middle stage 130 through 2xd links (for example input switch IS1 is connected to
`
`middle switches MS(1,1), MS(1,2), MS(1,5) and MS(1,6) through the links ML(1,1),
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`Eachofthe 2x 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 examplethe links
`
`ML(1,1) and ML(1,5) are connected to the middle switch MS(1,1) from input switch IS1
`
`and IS2 respectively) and are also connected from exactly d 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).
`
`Similarly each of the 2x 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
`tas output switches in output stage 120 through dtd,
`
`
`
`
`
`links (for example the links
`
`ML(4,1), ML(4,2), ML(4,3) and ML(4,4) are connected to output switches OS1, OS2,
`
`OS3, and OS4 respectively from middle switch MS(1,1)).
`
`10
`
`Similarly each of the 2xa middle switches MS(2,1) — MS(2,8) in the middle
`
`stage 140 are connected from exactly d switches in middle stage 130 through d links
`
`(for example the links ML(2,1) and ML(2,5) are connected to the middle switch MS(2,1)
`
`from middle switches