US008170040B2
`
`a2) United States Patent
`US8,170,040 B2
`(10) Patent No.:
`Konda
`
`(45) Date of Patent: *May 1, 2012
`
`ABSTRACT
`(57)
`A generalized butterfly fat tree network comprising (log, N)
`stages is operated in strictly nonblocking mannerfor unicast
`and in rearrangeably nonblocking mannerfor arbitrary fan-
`out multicast when s=2, and is operatedin strictly nonblock-
`ing manner for arbitrary fan-out multicast when s23,
`includesa leaf stage consisting of an inpul stage having
`
`N d
`
`a
`
`switches with each of them having d inlet links and sxd
`oulgoing links connecting to ils immediate succeeding stage
`switches, and an output stage having
`
`N d
`
`a
`
`switches with each of them having d outlet links and sxd
`incoming links connecting from switches in its immediate
`succeeding stage. The network also has (log, N)-1 middle
`stages with each middle stage, excepting the root stage, hav-
`ing
`
`d
`
`SXN
`
`switches, and each switch in the middle stage has d incoming
`links connecting from the switches in its immediate preced-
`ing stage, d incoming links connecting from the switches in
`its immediate succeeding stage, d outgoing links connecting
`to the switches in its immediate succeeding stage, d outgoing
`links connecting to the switches in its immediate preceding
`stage, and the root stage having,
`
`sxXN
`
`switches, and each switch in the middle stage has d incoming
`links connecting from the switches in its immediate preced-
`ing stage and d outgoinglinks connectingto the switchesin its
`immediate preceding stage.
`
`22 Claims, 20 Drawing Sheets
`
`(54) FULLY CONNECTED GENERALIZED
`BUTTERELY FAT TREE NETWORKS
`
`(75)
`
`Inventor: Venkat Konda, San Jose, CA (US)
`
`(73) Assignee: Konda Technologies Inc., San Jose, CA
`(US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U'S.C. 154(b) by 273 days.
`This patent is subject to a terminal dis-
`claimer.
`
`(21) Appl. No.:
`
`12/601,273
`
`(22) PCT Filed:
`
`May22, 2008
`
`(86) PCT No::
`§ 371 (c)(),
`(2), (4) Date:
`
`PCT/US2008/064603
`
`Nov. 22, 2009
`
`(87) PCT Pub. No.: WO2008/147926
`PCT Pub. Date: Dec. 4, 2008
`
`(65)
`
`Prior Publication Data
`US 2010/0172349 Al
`Jul. 8, 2010
`
`Related U.S. Application Data
`
`(60) Provisional application No. 60/940,387,filed on May
`25, 2007, provisional application No. 60/940,390,
`filed on May 25, 2007.
`
`(51)
`
`Int. Cl.
`(2006.01)
`HOAL 12/728
`ose. 370/408
`(52) US. CD. eeceeecccccccceceeetteneeeeeeeee
`
`(58) Field of Classification Search.
`........... 370/351-357,
`370/359-360, 369-370, 372, 375, 380, 386-390,
`370/400, 408, 422, 427, 901, 902-903
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,991,168 A *
`5,018,129 A *
`
`2/1991 Richards oo... ee 370/381
`5/1991 Netravali et al... 398/55
`
`(Continued)
`
`Primarv Examiner — Derrick Ferris
`Assistant Examiner — Omar Ghowrwal
`
`ML(3,9)
`“gy
`
`
`
`
`
`
`
`
`
`
`Li
`IL2
`OL1
`OL2
`La
`IL4
`OLB
`COLA
`
`Page 1 of 58
`
`FLEX LOGIX EXHIBIT 1015
`
`Page 1 of 58
`
`FLEX LOGIX EXHIBIT 1015
`
`

`

`US 8,170,040 B2
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`5,179,551 A *
`11993 Tamer seccsocmeccwee 370/398
`:
`
`.. 370/427
`5,541,914 A *
`7/1996 Krishnamoorthy et al.oe
`
`5,689,506 A * 11/1997 Chiussietal. 0.0... 370/388
`... 370/388
`.......
`5,864,552 A *
`1/1999 Duetal.
`:
`
`... 370/352
`6,307,852 B1* 10/2001 Fisheretal.
`.
`.. 370/388
`6,452,926 BL*
`9/2002 Wiklund
`
`370/395.1
`6,868,084 B2*
`3/2005 Konda ...
`k
`6,885,669 B2*
`4/2005 Konda ...
`370/395.1
`5/2008 Konda...
`.. 340/2.22
`7,378,938 B2*
`
`9/2008 Konda o...ccscssseeeeneeee 370/388
`7,424,010 B2*
`9/2008 Konda we 370/388
`7,424,011 B2*
`
`2/2004 Konda ...
`... 370/388
`2004/0032866 Al*
`2004/0056757 Al*
`3/2004 Konda oo. 340/2.22
`
`3/2005 Konda oc 370/388
`2005/0053061 A1l*
`wR
`>
`5
`2005/0063410 A1*
`3/2005 Konda .
`370/432
`5/2005 Konda .
`370/395.4
`2005/0094644 Al
`2005/0105517 Al
`x
`
`:5/2005 Konda .>
`
`a.. 370/370
`
`ne
`.
`,
`/2005 Konda .
`. 370/388
`2005/0117573 Al
`*
`i
`7
`4
`6/2005 Konda .
`.. 370/389
`2005/0117575 Al
`x
`}
`7
`4
`6/2005 Konda .
`.. 370/412
`2005/0129043 Al
`nom
`.
`,
`/2006 Konda .
`.. 370/386
`2006/0159078 Al
`noo
`.
`:
`/2006 Konda ....
`370/395.1
`2006/0165085 Al
`x
`1
`an
`/99)
`11/2006 Ramanan
`.. 370/229
`2006/0268691 A1*
`*
`}
`4
`7
`3/2007 Konda....
`.. 370/390
`2007/0053356 Al
`a .
`Z
`(2010 Konda .
`.. 370/388
`2010/0135286 Al
`2011/0044329 Al*
`MOLL Konda
`370/388
`:
`“
`: EE
`* cited by examiner
`
`
`
`Page 2 of 58
`
`Page 2 of 58
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 1 of 20
`
`US8,170,040 B2
`
`eS
`ee
`fas]ae
`— 00
`
`
`+f[>+——~+ _]
`C=O =
`—>-
`2
`a
`e
`©
`st
`©
`
`g
`io (2
`=
`=
`gt
`o
`~
`=
`Nw
`5
`z
`2
`
`™ x
`—s
`—S
`
`
`
`st
`”
`
`{——
`
`— >
`wo —
`
`¢
`Oo
`lO_i
`Oo
`
`=2
`
`2
`w~
`O
`
`oO
`2
`
`8
`
`Ts)
`‘ =
`
`
`
`
`
`
`
`
`<
`oS
`=
`
`
`
`
`
`
`
`
`
`—
`=
`
`O=
`
`ro—>
`“I
`CO
`
`W O
`
`o
`
`_ O
`
`o *
`
`-—S
`+
`zut
`MN
`=
`—> —
`oO
`5—
`_ Oo
`N,
`_-F=
`
`“
`- “2
`”
`
`— _
`
`N ”
`
`=
`
`Y°
`
`“
`
`
`
`
`weye Ne NL
`Orl
`O€L
`OZ/l 8 OLL
`
`Page 3 of 58
`
`Page 3 of 58
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 2 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`WeljCte{)SVLowIWeeSN\CWOyN?BOD)Samed(TI-MeTYsW
`
`(xgLiveODSW(7424uPSo\¢wP.be(C—N°380T)SW
`veneee\Possess_~MP2LINxB——{NZ'1~/(NHXT'T—NTSLZ_
`
`(1+N’80T)IN2we (S(a(NXTI+NN80T)IN -\oeeMEa (P/NJSO(D/N)S]|seenneee:ge
`
`
`
`ooZNNA
`senenenenee(Z+P/N'LSI(L+P/N‘L)SW(P/N‘'LSWtoreweowone(ZS(L'LSW
`
`
`
`
`(Oo
`
`(Pr't—N’80Tx7YIW[Ss
`
`
`
`
`
`
`
`tetm4
`
`
`
`(P-N)10)(NT(P-N)T1I ((P-NIZTZ-N“807XT\(N10
`
`
`(par10(Ls)(oz)(L+9)11(PI10.(pTssTH
`
`
`
`
`
`
`
`(I+PTT—N’SOTXTIN
`
`\PUT—N*8OTXTYIN
`
`
`
`(0M
`
`a001al‘Old
`
`a8i+
`
`Page 4 of 58
`
`Page 4 of 58
`
`
`
`
`
`
`

`

`Sheet 3 of 20
`
`
`
`
`
`
`(‘sw(2:LISI(9's(s‘LsW(P'S(s'HSn(ZS(LSM
`
`
`
`(ze‘ry1M(L'pyIW_—~{(ob‘LW
`(LHI
`
`US 8,170,040 B2
`
`
`
`
`
`
`{tttttneHoveitttttt||(o'r)ttttttwn
`
`j)vsO/|vSl|,eslzSOcsifISO||LSI||~
`
`
`REARSsuZTSidaES91SINisemhvuelBinksZul
`O00000O0O0000299000OCc;O000~O
`
`
`
`
`
`
`
`
`
`
`(or'zW(—*Ccvsan-ag'Zzy1N(Zhafis2~~.-(enn.(Z’ey1W
`
`May1, 2012
`
`(s¥'z)N|(6'2nINlz“\g'ann
`
`
`
`
`
`~-(eZ)
`
`(QE(sie=Ven
`(LZSW(@nf—_(oL‘eyW8eyenw>)(~5(z's)(ie)
`
`(s'Z)SW(2’2)SW(9'Z)SW('Z)SW(y'ZISW(sZSw(z'Z)SiN
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(BEN
`
`U.S. Patent
`
`9001ITDT
`
`Page 5 of 58
`
`‘|——
`
`Page 5 of 58
`
`

`

`
`
`(P.d,z)10Ay(02
`
`(Nd)I000-|(NDT(P-NDTI
`PP(oxziy’ODSW(C+1-N?80dw+—bs)ItaTayi?SW
`
`(P-N)XEXTT—N'SOTXTIN
`(on).sr0
`
`
`(I+Pxdx7Z—N°80TXT)IW
`(P.dIOFIO.(PI|
`
` \pz)(L+P)1]
`
`pptat
`
`
`
`
`
`
`
`
`
`
`TLAl7
`
`
`
`(pxdx77—N’80TXZ)IWN\
`
`
`
`
`
`i
`
`
`
`U.S. Patent
`
`May1, 2012
`
`Sheet 4 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`(NXTI+N807)IN(1+N°807)TWfq00raI‘D1
`
`(L+P/N'LISW(P/N'LISA|tmeenmenene(Z'LSW
`
`
`
` "T)xO1+0€1—(T-N
`
`“OZBOLL
`
`Page 6 of 58
`
`Page 6 of 58
`
`
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 5 of 20
`
`US 8,170,040 B2
`
`|
`
`OL7OL8
`25)ftttttmua] SANS
`
`6b
`
`
` \Mtttecs
` musstnt
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG.1E
`
`Stl
`
`9b
`
`eb
`
`eb ll
`
`OLl
`
`
`OL1OL2|
`SSS3S
`
`—Ork OZ)BOLL
`
`Page 7 of 58
`
`Page 7 of 58
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 6 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`4001ALD1
`
`(L+p)10\(N)10_)(Ned)((P-N)49)(Pz)10»\(p,d.z)rtPx9TL(PIO«110(Px)17
`
`
`
`NOUSNren[orgDYYSNNUN(CINPSOT)SMommef
`
`xcgonsw(c+1N80dwyebs)Ly-y'songy
`(NXTL+N801YIN(T+N°S07)IW5A%
`
`
`
` .auw{\|3=‘8(DINZLISA0etrereeees('LSW]{/f///Lei](Z+D/N‘LISIN(L+P/N'LISW(PINSeeneennnee(Z‘L)SIN
`
`
`
`
`
`(P-NYTT-N?SOTXTIWPTTN°80TXC)TN
`tetf=]tetPedtetdeb/(Pr't—N’80TXZYIN\is(P/N)SO
`(PD/INJSL|rnteennee~Qe\lsa feveneee
`|S
`onoe8444),¢
`(P-N)IO
`
`
`
`
`
`
`
`Page 8 of 58
`
`(I+PTT-N°8OTXTYIN
`
`\‘Pp
`
`
`
`
`
`Page 8 of 58
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 7 of 20
`
`US 8,170,040 B2
`
`s10410.8sC10S10otsSTs10s10soteTsoet0«HTeasttl(2'L)W||t||(Zptt|vSO87S!JESO8€SIZSO8ZSI)/SO8LSI
`
`
`/
`
`
`(
`
`VoOl
`
`(r'Z)SW
`
`(ee)W
`
`
`
`
`
`
`
`
`
`ote=
`
`
`
`(
`
`os=
`=
`
`
`
`JC
`
`p
`
`
`
`(9'Z)W
`
`(eLsw
`
`(z‘LSW
`
`
`
`
`
`Ne
`
`Ori
`
`OZl 8 OLL
`
`Page 9 of 58
`
`Page 9 of 58
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 8 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`(P-N‘T-N°807XZYIN\
`
`coe\Joma
`
`
`
`
`(N10(p-NO.(N)T1(P-N)TI
`
`
`tt/b|
`(P/N)SO(P/N)SI
`
`
`(T+P‘T-N°SOTXT)IN
`
`
`
`WT-N’SOTXOIN
`
`(pz)
`
`\
`
`\
`
`\Oo(140)O(pz)11(L+9)11(®N10
`
`
`Lio)(PTsTI
`
`
`
`
`
`
`
`(TE-N°801XTIsyhorZ)SW
`
`==Is
`
`g00e
`
`deOld
`
`(NT+N°807)TN
`
`(IT+N’S07)IW
`
`N \weteeN
`PPC
`“tee-NOOSE
`
`
`
`ror)SA(T+—‘T-N’S07)S
`
`
`{Y/7L4/7idelaw'aghsyCtyens
` ae
`VL
`
`I
`
`(P/NLISI
`
`(Z+PZ/N‘LISIN
`(L+PZ/N'SW
`
`(pZ/N‘LSW
`
`(z‘L)SW
`
`(‘Lsw
`
`
`
`
`
`(TT—N?S07)SPYvwnnee
`
`
`
`y
`— N° 307 eZ) xO1+0E18 OFL
`
`Se ~
`OZl BOLL
`
`(CT-N
`
` ran
`-OL+0E1
`
`Page 10 of 58
`
`Page 10 of 58
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`/
`
`FIG.2C
`
`May1, 2012
`
`Sheet 9 of 20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ML(2,1)
`
` US 8,170,040 B2
` t IL5
`
`
`
`1 IL6
`
`IS2
`
`// \
`
`OS1
`
`/
`
`(
`
`
`
`toaAUP
`
`IL3
`
`TNOTLOCO245535000000
`
`IL2
`
`IL1
`
`Orb
`
`“OSL8OGL
`
`OZ)BOLL
`
`Page 11 of 58
`
`Page 11 of 58
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 10 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`
`
` ((P—N)X4‘7-N*80TXZ7)IN\(pxd‘7—N’807xZ)IW
`
`
`
`
`
`
`(.pid10\(N.4)10.—SS(NDT(NDT(p,d,Z)10V(pz)(0h.(p,d1010)(PTs
`
`(NT+N8071)TW(T+N’S0T)IW
`
`seceeet-1fmonaere—wesersornPetded)fetded
`(P/N)SO|(P/N)SE|eneenneneLSI
`teceee|aseeeee\sennce|seceee
`
`veceee\a~_§P-N'EYINveceee
`((P-N).4)'10
`€-NP807xz)1[y~7{|7/(~7TP,“1::iWN
`
`
`
`
`sreeecocces(Z+PZIN'LISI(L+PZ/N‘LSW(pZ/N‘LISWseroeomonne(Zs('LSW
`
`
`
`
`
`q00zdz‘
`
`
`oval"SODSACTnw!
`PC—J-—OT4+—‘T-
`
`(Pz
`
`
`
`
`
`
`
`
`(Nad‘TPN’SOTXZ.
`
`a
`
`(f-‘¢-Nfso7—‘¢-—N’SOFRT)SI
`Nn.aNfAL
`
`SS{N'WW
`
`forosii
`
`uw|
`— N’80T eZ) n01+ote O€
`
`(1+Ppxd‘7-N’s07xZ7IW
`
`
`
`
`
`
`
`([- N"507),
`DxOlt0EL (
`
`Page 12 of 58
`
`|
`
`4
`
`OZL BOLL
`
`Page 12 of 58
`
`
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 11 of 20
`
`US8,170,040 B2
`
`OS4
`
`
`
`
`
`\
`
` OL3OL4
`Is2( ttt oa
`
`
`
`200E\
`
`FIG,2E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Orr—*~=<C«~CSGBEL
`
`“OZ80ll
`
`Page 13 of 58
`
`Page 13 of 58
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 12 of 20
`
`US 8,170,040 B2
`
`(N’7—N'BOTXTIW
`
`(f-‘€-NPe207
`
`
`
`
`
`
`(P/N)SO
`
`
`
`
`(L+P)10\(NIO(ad((P-N).0)11(pz)102\(padazyie+P24A(POLIO(P.ATL+7@/tftttt=]
`(P-N‘7—N"80TXZYIN(REN'BOTXCYIN
`
`(N‘L+NS07YIN(1+N°S0T)INf400¢AZ‘OM
`
`
`
`
`
`
`(PIN'LISWfarmerrnnen(Z+PZ/N‘LISW(L4PZ/N'LISA|(PZIN'LISIfreee(Z‘WSW(LHS
`osFr:nooneateoe=werep
`
`
`
`ePT‘"0°SW(C+I-NPSODST-N’sons
`(P-N)1C
`
`DT..
`TERPTLPTETNf.
`WINtSPT.‘e
`Z;(‘wy
`PsforZ)sw
`
`
`
`
`
`(I+P°7-N’80TXZ)IN
`
`
`
`(Z ~ Nes xOT+0EL CFO71);
`
`—
`
`
`-N’807 x
`
`Se
`
`oe OE
`7) «OT +0€T9 OFL
`
`aN
`NL
`OZL POLL
`
`Page 14 of 58
`
`Page 14 of 58
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 13 of 20
`
`US8,170,040 B2
`
`300A
`
`FIG.3A
`
`
`
`
`
`tML(1,4)| IL2
`
`IL3 |ML(4,4)t OL2
`
`
`
`
`
`fusal|IL8OL7OL8
`ML(1.13)F IL7
`OL5OL6
`
`
`
`
`t IL6
`
`t IL5
`
`
`
`,OL3OL4
`
`
`t IL4
`
`OL1
`
`IL1
`
`ML(3,1}
`
`i
`
`Orr
`
`Nee
`O€1
`
`\
`
`OZ8OlL
`
`Page 15 of 58
`
`Page 15 of 58
`
`

`

`(N)10(P-N)10|(NYT(P-N)11(pz)10(L+P)10(pz)(L491)(70100(Pp)Ts
`
`
`
`
`
`
`((P—NYCT—NN"807XZYIN\eee—N*807xO\\\
`
`(NXTL+N’SOTIN(IT+N°S0T)IN
`ST)SW(T+TONSODSHGta'1-NOW):
`“7qooed¢Ol
`UNWEIT
`
`
`
`'TLUTL|
`
`
`
`(Pr't—N'80TXTYIN
`
`«PN)LW
`
`(L+PT7—N°SOTXZYIN
`
`
`
`
`
`U.S. Patent
`
`US 8,170,040 B2
`
`May1, 2012
`
`Sheet 14 of 20
`
`(Z+PZ/N‘LSW(L+PZ/N‘LISW(PZIN'LISW|aneeeneeee(Z‘WSW(DSW
`
`
`
`
`
`(LCN
`
`7%
`
`+ OL+OETy,
`—N*807
`
`
`
`OZ)BOLL
`
`Page 16 of 58
`
`Page 16 of 58
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 15 of 20
`
`
`
`
`
`US8,170,040 B2
`
`
`
`
`
`
`
`
`
`Orrt—<is~=Sst
`
`OZ)BOLL.
`
`Page 17 of 58
`
`Page 17 of 58
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 16 of 20
`
`US 8,170,040 B2
`
`(—‘T-NYSeTISW(T+—‘T-N’SOT)SV(F‘(—'TEN“307)SWiNaNCeta(21—N80T)SN,
`
`
`PPCPTPoS07:
`
`
`
`-N).d\\(nai;0(N)q(PND(P.d,210(L+P.d)10(PZ)TL+P)TI(P.4)10FIO(PYLE
`nneen
`(P-NYTT-N’80TXUIN\
`
`(NXTT+NS07)TW(I+N’S0TIWw
`
`tJTYtefodedot=tdeb.
`(PAINFayYLEYVTTATV,
`\\
`aooed¢Olt
`RE~Scha)Z|Freelg~oaeerindoon=|aosoyoO
`
`(Z+PZ/N'SINL+DZ/N‘LISIN(PZIN'VISAJsense(z‘sw(LSM|/nennne
`
`
`
`!l2\pols'S
`
`eo
`“
`(Z- N87) x OL FUEL
`
`
`
`(I+P77—N°80TXZIN
`
`\(PUT—NOSOTXZIN
`
`
`
`
`Page 18 of 58
`
`Page 18 of 58
`
`
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 17 of 20
`
`US 8,170,040 B2
`
`{
`
`OS4
`
`/tie
`
`So ML(1,25
`
`OL7OL8
`GBOrnos=ANNAAee
`OL5OL6
`IS3 ITAA
`OL3OL4
`
`
` fl
`
`
`
`|
`
`OS2
`
`IS2 nta
`
`|uae OL1OL2
`
`
`
`
`
`
`
`
`
`
`
`AVS
`
`
`VV
`
`
`
`vwKY
`
`
`
`TN
`y
`7AK\)
`.
`
`1}
`
`Nedieat 2d
`
`/
`
`\\
`A,
`
`FIG.3E
`
`
`
` '»
`
`
`
`Orr
`
`OeL
`
`Page 19 of 58
`
`Page 19 of 58
`
`

`

`
`
`\\\(N)10enoNMCony.A)(pzy10(PIO.{+P(p)10110(P.-E
`(NXTL+NSOT)IN(T+N°807TyIWf400¢AcOM
`
`
`ttf]|peetetpd
`(Py'T—N'8OTXT)IN\|(P/N)SO|(P/N)SE|sectssee~LSOLSI
`
`
`
`
`
`Man seewceenene(z‘L)SW(L'LSW7|Tl.
`
`
`
`
`
`U.S. Patent
`
`May1, 2012
`
`Sheet 18 of 20
`
`US 8,170,040 B2
`
`
`
`(P-NIZT-N'S0TX7YIW
`
`
`
`=TP\..-|
`
`(1+PUTNV807XC
`
`\(PETN"BOTXTYIN
`
`\
`
`\
`
`SODSW3(TT—N?SOT)
`NWff(T-
`
`
`
`Page 20 of 58
`
`Page 20 of 58
`
`
`
`
`

`

`eo)|403S!Ou}OUIey]WoyleUgaMIEgSyulIOALJEpAjanisunde4‘UOeUSEpYORJOYOIMsyNdjNo
`
`
`
`
`
`
`OrolaxeKay}
`
`
`
`
`
`
`
`Bulpuodseosay}dnBulyojyewAq‘sdajsom)SNO!AsJd8ujUlpe}2J9Ua6bsisi|auBuisqSUONOSUUODJOJO
`
`
`
`
`
`
`0ZOl|ayyaauapAjanisunaau‘yoMsyndulayyJoyu]ajppiwBuloBynoyoeswol4
`
`
`
`
`
`,S|PPILUYOOUI!‘B|QeYDeSISIUONEUNSEPau)UDIUMWOU‘S@yd1MSO/PpPIW0]pasnsa6e]s84)
`/Jo}ajqeyeaeun
`9|qeyoediJO$}SI|9y}o}e9U9B‘NOTa6e}ssIPpILWSu}U!SOYDUMSB|PPILUBjqe|IeAe
`
`
`
`
`
`
`0901yBnosy)uonoeuuCsay}dnjas
` OLol
`N607s6eisa/ppitu0}abe}syndjnowowspremyoegGuljaae.y‘abels/)Yeu]OSonoouuos
`
`
`
`
`
`
`
`
`
`
`_| paemuoyBuljene.‘oBe}sapplyoreu!SeyoyMs9|ppiwa|qeyoeedJos}sI|
`
`
`
`
`YOIIMSJNdU!UeJOYU]J9|U!UBLOI},UONDSUUODBLWJOJ0}Jsanbassvgioay
`Yousjndulay}Joyul|sjppiwGulioBynoyaeswouBuleyssuojeunsep
`
`
`
`
`
`-“|QU)WOSyul]a]ppILUBuIOHynoom}pul4WOSYUl|a|ppiluBuloGynoomy
`
`
`
`
`
`
`aiesuoeunsap[jeyoluMYUBnou)YoIMsyndu!
`
`
`
`
`
`
`ey}yeyorumUBnodu}YoyMsyndul8}BuryeyAq‘yoq!msIndu!ay}
`
`
`4ul]a]ppiluBuioBinoajGulsesyey
`
`
`giqeyoeeuavesuoleunsepYOR?JO}WN]Jseseou
`
`
`
`
`N607e6elss]ppiw0}|abeyssjppiwwWoy
`,au}dnjes
`
`
`
`SAA|wouyureyppituBulobynosuo
`
`
`
`/|UBNOJY]UONOSUUOD8y}dN18S
`
`
`
`9y}BuryeyAg‘yousyndulayy
`
`
`yoeeJO}WIN}-7)}seueeU
`S|PPIWau}|eWW
`
`
`
`OZOL
`
`0801
`
`
`
`uojeusep
`
`
`
`U.S. Patent
`
`May1, 2012
`
`Sheet 19 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`é3|qeuoea.
`
`uoyeUusep
`
`O00L
`
`VPOla
`
`Page 21 of 58
`
`Page 21 of 58
`
`
`
`
`

`

`U.S. Patent
`
`May1, 2012
`
`Sheet 20 of 20
`
`US 8,170,040 B2
`
`(Z'Z)d~—
`
`(Z‘Z)o"
`
`yvo0s
`
`(Z'Z)dodI/(L'b)dod
`
`Zl
`
`CVS‘OlA
`
`
`
`QAVy4011d)
`
`
`
`zZ10.«110
`
`PVS“OLA
`
`Vs‘Old
`
`Ll
`
`Z1l
`
`Lvoos
`
`1LI/(do(do
`
`(Z'Z)d9
`
`=Zl
`
`z10110
`
`IVSOM
`
`GAY1011q)
`
`evo0s
`
`f
`
`(ZCAiI—(WAUDA
`
`210110
`
`
`
`EVs‘Ol
`
`(IV101d)
`
`LiZa
`
`Zll
`
`Page 22 of 58
`
`Page 22 of 58
`
`
`
`
`

`

`US 8,170,040 B2
`
`1
`FULLY CONNECTED GENERALIZED
`BUTTERFLY FAT TREE NETWORKS
`
`
`CROSS REFERENCE TO RELAT!
`APPLICATIONS
`
` eslD
`
`
`
`This application is related to and claims priority of PCT
`Application Serial No. PCT/US08/64603 entitled “FULLY
`
`CONNECTED GENERALIZED BUTTERFLY FAT TREE
`
`
`
`NETWORKS” by Venkat Konda assigned to the same
`assignee as the current application, filed May 22, 2008, the
`U.S. Provisional Patent Application Ser. No. 60/940,387
`entitled “FULLY CONNECTED GENERALIZED BUT-
`TERFLY FAT ‘TREE NETWORKS” by Venkat Konda
`assigned to the same assignee as the current application,filed
`May 25, 2007, and the U.S. Provisional Patent Application
`Ser. No. 60/940,390 entitled “FULLY CONNECTED GEN-
`ERALIZED MULTI-LINK BUTTERFLY FAT TREE NET-
`WORKS”by Venkat Konda assigned to the same assignee as
`he current application, filed May 25, 2007.
`This applicationis related to and incorporates byreference
`in its entirety the U.S. application Ser. No. 12/530,207
`entitled “FULLY CONNECTED GENERALIZED MULTI-
`
`STAGE NETWORKS” by Venkat Konda assigned to the
`same assignee as the current application, filed Sep. 6, 2009,
`he PCT Application Serial No. PCT/US08/56064 entitled
`“FULLY CONNECTED GENERALIZED MULTI-STAGE
`
`by Venkat Konda assigned to the sameassignee as the current
`application, filed Mar. 6, 2007, and the U.S. Provisional
`Patent Application Ser. No. 60/940,383 entitled “FULLY
`
`CONNECTED GENERALIZED MULTI-STAGE NET-
`
`
`
`
`
`WORKS”by Venkat Konda assigned to the same assignee as
`he current application, filed May 25, 2007.
`This applicationis related to and incorporates byreference
`in its entirety the U.S. patent application Ser. No. 12/601,274
`entitled “FULLY CONNECTED GENERALIZED MULTI-
`LINK MULTI-STAGE NETWORKS” by Venkat Konda
`assigned to the sameassignee as the current application filed
`concurrently, the PCT Application Serial No. PCT/US08/
`64604 entitled “FULLY CONNECTED GENERALIZED
`MULTI-LINK MULTI-STAGE NETWORKS”by Venkat
`Konda assigned to the same assignee as the current applica-
`ion, filed May 22, 2008, the U.S. Provisional Patent Appli-
`cation Ser. No. 60/940,389 entitled “FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING
`
`MULTI-LINK MULTI-STAGE NETWORKS”by Venkat
`Konda assigned to the same assignee as the current applica-
`ion, filed May 25, 2007, the U.S. Provisional Patent Appli-
`cation Ser. No. 60/940,391 entitled “FULLY CONNECTED
`
`GENERALIZED FOLDED MULTI-STAGE NETWORKS”
`
`by Venkat Konda assigned to the sameassigneeas the current
`application, filed May 25, 2007 and the U.S. Provisional
`Patent Application Ser. No. 60/940,392 entitled “FULLY
`
`CONNECTED GENERALIZED STRICTLY NON-
`BLOCKING MULTI-LINK MULTI-STAGE NETWORKS”
`
`by Venkat Konda assigned to the same assignee as the current
`application, filed May 25, 2007.
`This applicationis related to and incorporates byreference
`in its entirety the U.S. patent application Ser. No. 12/601,275
`entitled ““VLSILAYOUTS OF FULLY CONNECTED GEN-
`
`FRALIZED NETWORKS”by Venkat Kondaassigned to the
`
`Page 23 of 58
`
`2
`same assignee as the current application filed concurrently,
`the PCT Application Serial No. PCT/US08/64605 entitled
`“VLSI LAYOUTS OF FULLY CONNECTED GENERAL-
`
`IZED NETWORKS”by Venkat Konda assigned to the same
`assignee as the current application, filed May 22, 2008, and
`the U.S. Provisional Patent Application Ser. No. 60/940,394
`entitled “VLSI LAYOUTS OF FULLY CONNECTED GEN-
`
`10
`
`ERALIZED NETWORKS”by Venkat Kondaassigned to the
`same assignee as the current application,filed May 25, 2007.
`This application is related to and incorporates by reference
`inits entirety the U.S. Provisional Patent Application Ser. No.
`61/252,603 entitled “VISIT LAYOUTS OF FULLY CON-
`
`NECTED NETWORKS WITH LOCALITY EXPLOITA-
`
`20
`
`25
`
`30
`
`40
`
`50
`
`60
`
`TION”by Venkat Konda assigned to the same assigneeas the
`current application, filed Oct. 16, 2009.
`This application is related to and incorporates by reference
`in its entirety the U.S. Provisional Patent Application Ser. No.
`61/252,609 entitled “VLSI LAYOUTS OF FULLY CON-
`
`NECTED GENERALIZED AND PYRAMID NET-
`
`
`
`WORKS”by Venkat Konda assigned to the same assignee as
`the current application,filed Oct. 16, 2009.
`
`BACKGROUNDOF INVENTION
`
`Clos switching network, Benes switching network, and
`Cantor switching network are a network of switches config-
`ured as a multi-stage network so that fewer switching points
`are necessary to implement connections between its inlet
`links (also called “inputs”) and outlet links (also called “out-
`puts”) than would be required by a single stage (e.g. crossbar)
`switch having the same numberof inpuls and outputs. Clos
`and Benes networks are very popularly used in digital cross-
`connects, switch fabrics and parallel compuler systems.
`However Clos and Benes networks may block some of the
`connection requests.
`There are generally three types of nonblocking networks:
`strictly nonblocking; wide sense nonblocking; and rearrange-
`ably nonblocking (See V. E. Benes, “Mathematical Theory of
`Connecting Networks and Telephone Traffic’ Academic
`Press, 1965 that is incorporated by reference, as background).
`In a rearrangeably nonblocking network, a connection path is
`guaranteed as a result of the networks ability to rearrange
`prior connections as new incoming calls are received. In
`strictly nonblocking network, for any connection request
`from an inlet link to some set of outlet links, it is always
`possible to provide a connection path through the network to
`satisfy the request without disturbing other existing connec-
`tions, and ifmore than one such path is available, any path can
`be selected without being concerned about realization of
`future potential connection requests. In wide-sense non-
`blocking networks, it is also always possible to provide a
`connection path through the network to satisfy the request
`without disturbing other existing connections, but in this case
`the path used to satisfy the connection request must be care-
`fully selected so as to maintain the nonblocking connecting
`capability for future potential connection requests.
`Butterfly Networks, Banyan Networks, Batcher-Banyan
`Networks, Baseline Networks, Delta Networks, Omega Net-
`works and Flip networks have been widely studied particu-
`larly for self routing packet switching applications. Also
`Benes Networks with radix of two have been widely studied
`and it is known that Benes Networksof radix two are shown
`to be built with back to back baseline networks which are
`rearrangeably nonblocking for unicast connections.
`U.S. Pat. No. 5,451,936 entitled “Non-blocking Broadcast
`Network”granted to Yanget al. is incorporated by reference
`herein as backgroundofthe invention. This patent describes
`
`
`
`
`
`NETWORKS” by Venkat Konda assigned to the same
`assignee as the current application, filed Mar. 6, 2008, the
`U.S. Provisional Patent Application Ser. No. 60/905,526
`entilled “LARGE SCALE CROSSPOINT REDUCTION
`WITH NONBLOCKING UNICAST & MULTICAST IN
`ARBITRARILY LARGE MULTI-STAGE NETWORKS”
`
`
`
`
`
`Page 23 of 58
`
`

`

`US 8,170,040 B2
`
`Nd
`
`switches with each of them having d outlet links and 2xd
`incoming links connecting from switches in its immediate
`succeeding stage. The network alsa has (log, N)-1 middle
`stages with each middle stage, excepting the root stage, hav-
`ing
`
`switches, and each switch in the middle stage has d incoming
`links connecting from the switches in its immediate preced-
`ing stage, d incoming links connecting from the switches in
`its immediate succeeding stage, d outgoing links connecting
`to the switches in its immediate succeeding stage, d outgoing
`links connecting to the switches in its immediate preceding
`stage, and the root stage having
`
`20
`
`3
`a numberof well known nonblocking multi-stage switching
`network designs in the background section at column 1, line
`22 to column 3, 59. An article by Y. Yang, and G. M., Masson
`entitled, “Non-blocking Broadcast Switching Networks”
`IEEETransactions on Computers, Vol. 40, No. 9, September
`1991 that is incorporated by reference as backgroundindi-
`cates that if the numberof switches in the middle stage, m, of
`a three-stage networksatisfies the relation m=min((n-1)(x+
`r’*)) where 1=x=min(n-1,n,the resulting network is non-
`blocking for multicast assignments. In the relation, r is the
`numberof switchesin the input stage, and n is the number of
`inlet links in each input switch.
`USS. Pat. No. 6,885,669 entitled “Rearrangeably Non-
`blocking Multicast Multi-stage Networks” by Konda showed
`hat three-stage Clos network is rearrangeably nonblocking
`for arbitrary fan-out multicast connections when m==2xn.
`And US. Pat. No. 6,868,084 entitled “Strictly Nonblocking
`Multicast Multi-stage Networks” by Konda showed that
`hree-stage Clos networkis strictly nonblocking forarbitrary
`fan-out multicast connections when m=3xn-1.
`
`In general multi-stage networks for stages of more than
`hree and radix of more than two are not well studied. An
`
`
`
`2xN
`d
`
`switches, and each switch in the middle stage has d incoming
`links connecting from the switches in its immediate preced-
`ing stage and d outgoinglinks connectingto the switchesin its
`immediate preceding stage. Also the same generalized but-
`terfly fat tree network is operated in rearrangeably nonblock-
`ing mannerfor arbitrary fan-out multicast and each multicast
`connection is set up by use of at most two outgoing links from
`the input stage switch.
`A generalized butterfly fat tree network comprising (log,
`N)stagesis operated in strictly nonblocking mannerfor mul-
`ticast includes a leaf stage consisting of an input stage having
`
`N a
`
`switches with each of them having d inlet links and 3xd
`outgoing links connecting to its immediate succeeding stage
`switches, an output stage having
`
`N a
`
`25
`
`article by Charles Clos entitled “A Study of Non-Blocking
`Switching Networks” The Bell Systems Technical Journal,
`Volume XXXII, January 1953, No. 1, pp. 406-424 showed a
`way of constructing large multi-stage networks by recursive
`substitution with a crosspoint complexity of d?xNx(log,
`N)?°* for strictly nonblocking unicast network. Similarly 30
`USS. Pat. No. 6,885,669 entitled “Rearrangeably Nonblock-
`ing Multicast Multi-stage Networks” by Konda showed a way
`of constructing large multi-stage networks by recursive sub-
`stitution for rearrangeably nonblocking multicast network.
`An article by D. G. Cantor entitled “On Non-Blocking
`Switching Networks” 1: pp. 367-377, 1972 by John Wiley
`and Sons, Inc., showed a way of constructing large multi-
`stage networks with a crosspoint complexity of d’xNx(log,
`N)? forstrictly nonblockingunicast, (by using log,N number
`of Benes Networks for d=2) and without counting the cross-
`points in multiplexers and demultiplexers. Jonathan Turner
`studied the cascaded Benes Networkswith radices larger than
`two, for nonblocking multicast with 10 times the crosspoint
`complexity of that of nonblocking unicast for a network of
`size N=256.
`
`40
`
`The crosspoint complexity of all these networks is prohibi-
`tively large to implementthe interconnect for multicast con-
`nections particularly in field programmable gate array
`(FPGA) devices, programmable logic devices (PLDs), field
`programmable interconnect Chips (FPICs), digital crosscon-
`nects, switch fabrics and parallel computer systems.
`
`SUMMARYOF INVENTION
`
`A generalized butterfly fat tree network comprising (log,
`N)stages is operated in strictly nonblocking mannerfor uni-
`cast includesa leaf stage consisting of an input stage having
`
`switches with cach of them having d outlet links and 3xd
`incoming links connecting from switches in its immediate
`succeeding stage. The network also has (log, N)-1 middle
`stages with each middle stage, excepting the root stage, hav-
`ing
`
`60
`
`3xN
`
`switches with each of them having d inlet links and 2xd
`outgoing links connecting to its immediate succeeding stage
`switches, and an output stage having
`
`switches, and each switch in the middle stage has d incoming
`links connecting from the switches in its immediate preced-
`ing stage, d incoming links connecting from the switches in
`its immediate succeeding stage, d outgoing links connecting
`to the switches in its immediate succeedingstage, d outgoing
`
`Page 24 of 58
`
`Page 24 of 58
`
`

`

`US 8,170,040 B2
`
`5
`links connecting to the switches in its immediate preceding
`stage, and the root stage having
`
`3xN
`
`switches, and each switch in the middle stage has d incoming
`links connecting from the switches in its immediate preced-
`ing stage and d outgoinglinks connecting to the switchesin ils
`immediate preceding stage.
`
`10
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1Ais 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 nonblock-
`ing network for arbitrary fan-out multicast connections, in
`accordance with the invention.
`
`FIG.1B is a diagram 100B of a general symmetrical But-
`terfly fat tree network V,,,(N,d,s) with (log, N) stagesstrictly
`nonblocking network for unicast connections and rearrange-
`ably nonblocking networkfor arbitrary fan-out multicast con-
`nections in accordance with the invention.
`FIG. 1C is a diagram 100C of an exemplary Asymmetrical
`Butterfly fat tree network V,,(N,,N3,d,2) having inverse
`Benes connection topology of three stages with N,=8,
`N,=p*N| =24 where p=3, and d=2 with exemplary multicast
`connections, strictly nonblocking network for unicast con-
`nections and rearrangeably nonblocking network [or arbi-
`rary fan-out multicast connections, in accordance with the
`invention.
`
`6
`Benes connection topology of three stages with N,=8,
`N.=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 V,,(N,,N2,d,1) with N,=p*N,and
`with (log, N) stages rearrangeably nonblocking 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 of three stages with N,=8,
`N,=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. 2F is a diagram 200F of a general asymmetrical
`Butterfly fat tree network V,,(N,,N.,d,1) with N,=p*N, and
`with (log, N) stages rearrangeably nonblocking network for
`unicast connections in accordance with the invention.
`VIG. 3A is a diagram 300A of an exemplary symmetrical
`multi-link Butterfly fat tree network V,,.22-4¢(N.d,s) having
`inverse Benes connection topology offive stages with N=8,
`d=2 and s=2 with exemplary multicast connections, strictly
`nonblocking network for unicast connections and rearrange-
`ably nonblocking networkforarbitrary fan-out multicast con-
`nections, in accordance withthe invention.
`FIG.3B is a diagram 300Bof a general symmetrical multi-
`link Butterfly fat tree network Vjinz-5a(N.d,2) with (logy N)
`stages strictly nonblocking network for unicast connections
`aod rearrangeably nonblocking network for arbitrary fan-out
`multicast connections in accordance with the invention.
`
`FIG. 3C is a diagram 300C of an exemplary asymmetrical
`multi-link Butterfly fat tree network Vpring-an(Ni,.N2.4,2)
`having inverse Benes connection topology offive stages with
`N,=8, N,=p*N,=24 where p=3, and d=2 with exemplary
`multicast connections, strictly nonblocking network for uni-
`cast connections and rearrangeably nonblocking network for
`arbitrary fan-out multicast connections, in accordance with
`the invention.
`
`FIG. 3D is a diagram 300D of a general asymmetrical
`multi-link Butterfly fat tree network V,,j¢-(N,,.N2,d,2)
`with N,=p*N, and with (log, N) stagesstrictlynonblocking
`network for unicast connections and rearrangeably nonblock-
`ing network for arbitrary fan-out multicast connections in
`accordance with the invention.
`FIG.3E is a diagram 300E of an exemplary asymmetrical
`multi-link Butterfly fat tree network Vjring-o¢(Ni,N2,d,2)
`having inverse Benes connection topologyoffive stages with
`N,=8, N,=p*N,=24, where p=3, and d=2 with exemplary
`multicast connections, strictly nonblocking network for uni-
`cast connections and rearrangeably nonblocking network for
`arbitrary fan-out multicast connections, in accordance with
`the invention.
`FIG. 3F is a diagram 300F of a general asymmetrical
`multi-link Butterfly fat tree network V,j.4-2a(N,,.N2,d,2)
`with N,=p*N,, and with (log, N) stagesstrictlynonblocking
`network for unicast connections and rearrangeably nonblock-
`ing network for arbitrary fan-out multicast connections in
`accordance with the invention.
`FIG. 4A is high-level flowchart of a scheduling method
`according to the invention, used to set up the multicast con-
`nections in all the networks disclosed in this invention.
`
`
`
`20
`
`25
`
`30
`
`40
`
`50
`
`60
`
`
`
`FIG. 1D is a diagram 100D of a general asymmetrical
`Butterfly fat tree network V,,(N,.N2,d,2) with N=p*N, and
`with (log, N)stages strictly nonblocking network for unicast
`connections and rearrangeably nonblocking network for arbi-
`rary 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,,N3,d,2) having inverse
`Benes connection topology of three stages with N.=8,
`N,=p*N,=24, where p=3, and d=2 with exemplary multicast
`connections, strictly nonblocking network for unicast con-
`nections and rearrangeably nonblocking network for arbi-
`rary fan-out multicast connections, in accordance with the
`invention.
`
`FIG. 1F is a diagram 100F of a general asymmetrical
`Butterfly fat tree network V,,(N,.N2,d,2) with N,=p*N, and
`with (log, N)stages strictly nonblocking networkfor unicast
`connections and rearrangeably nonblocking networkfor arbi-
`rary fan-out multicast connections in accordance with the
`invention.
`FIG. 2A is a diagram 200A 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=1
`with exemplaryunicast connections rearrangeably nonblock-
`ing network for unicast connections, in accordance with the
`imvention.
`
`
`
`T'IG.2B is a diagram 200B of a general symmetrical But-
`terfly fat tree network V,,(N,d,s) with (log, N) stages and
`s=1, rearrangeably nonblocking network for unicast connec-
`tions in accordance with the invention.
`
`FIG. 2C is a diagram 200C of an exemplary Asymmetrical
`Butterfly fat tree network V,,(N,,Nz,d,1) having inverse
`
`VIG. 5A1 is a diagram 500A1 of an exemplary prior art
`implementation of a two by two switch; FIG. 5A2 is a dia-
`gram 500A2 for programmable integrated circuit prior art
`implementation ofthe diagram 500A1 ofFIG. 5A1; FIG. 5A3
`is a diagram 500A3 for one-time programmable integrated
`circuit prior art implementation ofthe diagram 500A1 of FIG.
`
`Page 25 of 58
`
`Page 25 of 58
`
`

`

`US 8,170,040 B2
`
`
`
`
`
`
`
`7
`5A1; FIG. 5A4