U8008170040B2
`
`(12) United States Patent
`US 8,170,040 B2
`(10) Patent N0.:
`Konda
`
`(45) Date of Patent: *May 1, 2012
`
`ABSTRACT
`(57)
`A generalized butterfly fat tree network comprising (logd N)
`stages is operated in strictly nonblocking manner for unicast
`and in rearrangeably nonblocking manner for arbitrary fan—
`out multicast when 522, and is operated in strictly nonblock-
`ing manner for arbitrary fan-out multicast when 523,
`includes a leaf stage consisting of an input stage having
`
`N d
`
`switches with each of them having d inlet links and sxd
`outgoing links connecting to its immediate succeeding stage
`switches, and an output stage having
`
`N E
`
`switches with each of them having (1 outlet links and s><d
`incoming links connecting from switches in its immediate
`succeeding stage. The network also has (logd N)—l 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
`
`SXN
`
`switches, and each switch in the middle stage has (1 incoming
`links connecting from the switches in its immediate preced-
`ing stage and d outgoing links connecting to the switches in its
`immediate preceding stage.
`
`22 Claims, 20 Drawing Sheets
`
`(54) FULLY CONNECTED GENERALIZED
`BUTTERFLY 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 of this
`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. N0.:
`
`12/601,273
`
`(22) PCT Filed:
`
`May 22, 2008
`
`(86) PCT N0.:
`§ 371 (0X1),
`(2), (4) Date:
`
`PCT/US2008/064603
`
`Nov. 22, 2009
`
`(87) PCT Pub. No.: W02008/147926
`PCT Pub. Date: Dec. 4, 2008
`
`(65)
`
`Prior Publication Data
`US 2010/0172349 A1
`Jul. 8, 2010
`
`Related US. 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)
`H04L 12/28
`
`.......... 370/408
`(52) U.S.Cl.
`......................................
`370/3517357,
`(58) Field of Classification Search
`370/3597360, 3697370, 372, 375, 380, 3867390,
`370/400, 408, 422, 427, 901, 9027903
`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 ....................... 370/381
`5/1991 Netravali et a1.
`................ 398/55
`
`(Continued)
`
`Primary Examiner 7 Derrick Ferris
`Assistant Examiner 7 Omar Ghowrwal
`
`ML3.9
`as
`
`
`
` J
`
`(
`83
`v)
`
`t
`
`:2
`
`L
`
`
`
`1
`fMLHA)
`MLIM)
`|L5
`lL6
`0L5
`0L6
`|L7
`ILB
`0L7
`0L8
`|L1
`|L2
`0L1
`0L2
`IL3
`|L4
`0L3
`0L4
`
`Page 1 of 58
`
`FLEX LOGIX EXHIBIT 1015
`
`
`'
`ML(2.10)
`
`.
`‘"
`
`
`6;.
`
`79‘ 4/
`
`/
`
`
`
`Page 1 of 58
`
`FLEX LOGIX EXHIBIT 1015
`
`

`

`US 8,170,040 B2
`
`PageZ
`
`3/2005 Konda ................... 370/388
`,
`7
`-
`5,2005 Ixonda
`37073954
`3,2005 126nm
`.. 37/0/432
`
`,5,2005 Ixonday
`
`
`-.. 3/0/370
`,
`7
`-
`,2005 Ronda
`.. 3/0/388
`,
`r
`-
`6,2005 Ronda
`.. 310/389
`/
`r
`-
`6,2005 Ixonda
`.. 3/0/412
`,
`,
`-
`2006 Ixonda
`.. 3/0/386
`,
`7
`7
`,2006 Ronda
`37073951
`,
`-
`,
`11,2006 Ramanan
`.. 310/229
`/
`-
`7
`3,2007 Ixonda
`.. 3/0/390
`,
`,
`-
`2010 Ixonda
`.. 3/0/388
`,2011
`370/388
`’
`
`
`
`"""""
`
`U.S. PATENT DOCUMENTS
`
`.
`“1993 Turner
`.......................... ”0/398
`5,179,551A *
`
`
`.. 370/427
`7/1996 Knshnamoorthy et 211.. .
`5,541,914 A *
`
`5,689,506 A * 11/1997 Ch1u551etal.
`370/388
`.......
`5,864,552 A *
`1/1999 Du etal.
`370/388
`.
`
`.. 370/352
`6,307,852 B1* 10/2001 F1sher et al.
`.
`6,452,926 131*
`9/2002 Wlklund
`370/388
`
`370/3951
`6,868,084 132*
`3/2005 Konda
`..
`6,885,669 B2'*
`4/2005 Konda
`370/395.1
`.. 340/222
`7.378.938 B2*
`5/2008 Konda
`
`9/2008 Konda .......................... 370/388
`7,424,010 132*
`
`9/2008 Konda .......................... 370/388
`7,424,011 B2*
`2004/0032866 A1*
`2/2004 Konda
`370/388
`2004/0056757 A1*
`3/2004 Konda ......................... 340/222
`
`2005/0053061 A1*
`*
`2005/0094644 A1
`2005/0063410 A1*
`2005/0105517 A1
`,,,
`,,
`2005/0117573 A1
`*
`2005/0117575 A1
`*
`2005/0129043 A1
`2
`2006/0159078 A1
`,,
`2006/0165085 A1
`*
`2006/0268691 A1
`*
`2007/0053356 A1
`2
`2010/0135286 A1
`2011/0044339 A1*
`,
`“
`.
`* Clted by exammer
`
`Page 2 of 58
`
`Page 2 of 58
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 1 0120
`
`US 8,170,040 B2
`
`)5)ML\(3‘16)
`
`
`
`ML(3‘1
`
`ML\(4,13)l
`
`
`T
`
`l
`
`
`
`
`
`0L70L8
`
`|L8
`
`|L7
`
`0L6
`
`OL5
`
`|L6
`
`|L5
`
`0L3OL4
`
`|L3|L4
`
`0L2
`
`|L1
`
`ML(1,13)T
`
`T
`
`T
`
`1
`
`082
`
`T
`
`T
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG.1A
`
`
`
`
`
`OS1(flISZ
`
`
`lMLE44)T
`
`
`l 0L1
`
`
`(\ ML(1,4)
`
`
`
`735me
`
`Page 3 of 58
`
`Page 3 of 58
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 2 0f 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`
`AquImzfi3%:a+hnTz£cE:Fw»is123532.2......N_.zw......\ifljmw:is:.z..AMTzQSfiEEKElfimfiwg
`
`
`
`m2:m2.0;
`
`
`
`2x§+2£3§<3+z§d§Wm
`
`m
`
`hmAWN
`
`\+
`
`Page 4 of 58
`
`...........4,m
`
`
`
`
`
`
`
`...........3&2;va2+3?in€2in.:::::@5222,592/,
`
`AwXNNIwax‘
`
`vu
`
`
`
`................0
`
`
`
`
`
`
`
`
`
`
`
`//,34'E5T>33I23%:V83:43c2mfixmvfie
`
`//
`
`2+madI2J3V85:
`
`
`
`
`
`
`
`
`
`
`
`IIIIII\.IIIIIaa\.—‘_.
`
`//2:08-2332:8-2:.Gujo$30ea...Cid/:35So8:.S.
`
`Qimlzxmfixg:m:2sz0/:2QO...........so/
`....../LE:>bw.zvm,:.__>_w/(§m.:._s_\
`
`
`
`
`
`
`
`
`
`Page 4 of 58
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 3 0f 20
`
`US 8,170,040 B2
`
`
`
`82m:.UE
`
`8.842
`
`
`
`
`
`
`
`
`
`
`
`
`63:26:83AZ.__>_
`8592Saw:3392AA_Vx\\83::mm5adj:\0A70A»m3:7;
`Sum:p.3926%:33m:9%:
`
`
`
`
`
`SE3383.3$3.22@332
`
`\@sz
`
`
`
`
`
`
`
`aim:Sims.aims.Sims.2»in8.322@5923:92
`
`
`
`\/\\\6F:.__2\:.:.__>_
`
`
`A84}::_$.__>_\\
`
`
`
`1/
`
`
`
`
`
`aaaaaaswig€2.32aaqaeeaaaaaee6+3:qaaaaa$5.“:emmVV«modE.8.$0mm.__twoEH
`
`
`
`
`
`
`
`
`0000000000000.00000000000
`
`
`
`mmmmmmw.__Emmwmmmo.__m.__mummmuS_3mmwmanS.:_
`
`
`
`.\J
`
`..,.,RN32:V5223WEE:\(\‘C~322.342%
`
`
`
`
`
`8E3:W\H?.mx,“Nam/M4
`
`
`
`‘\ /~\V/\
`O17L
`
`/
`
`“\ /—\/
`09L
`
`Page 5 of 58
`
`Page 5 of 58
`
`

`

`U
`
`2B
`
`ma+wxax3I2&3XSS0‘V0,STzvxmeNIzN/mfixsgAnxqumlzfimfixgs74///M,
`
`
`2??ng/S23:0L\A2;8-2;cm:for;
`
`€330:0so:3.UIIIIII\IIIIIIIIIIII\IIIIIIIII-I/
`
`
`
`
`
`
`
`
`
`
`
`
`
`ug2\\\\\k0.unu”9En3%vMEWTN»Zuwfi‘:EmIIQsI».IV.y2H2EH+ZHmewvS:
`
`...R$4I>1«23%......aIM......................Er»RH
`
`
`
`
`
`S.A:GE
`
`3+2£5E§Wnwm\wD...08—..Q
`tExqizumeqi:
`
`Page 6 of 58
`
`
`
`
`
`/‘1:,/{«zN,5.22\//,.x,0m2.2«$12935
`
`rm\/(\iJ/J43:.__>_mL
`mu»................Fm...........
`
`
`“$22in522:2;€2inaim:,
`
`
`
`
`
`
`
`:22va/2225.........../9
`....../in:_\>/®w-zvm,:§/Au
`
`
`
`
`
`
`
`Page 6 of 58
`
`
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 5 0f 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`yE
`
`FIG.1E
`
`Page 7 of 58
`
`Page 7 of 58
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 6 0f 20
`
`US 8,170,040 B2
`
`
`
`
`
`98“zQSXN:\/
`
`
`
`
`
`RxfilmzwvA+mgsa:..,Q2N......SEa2T2m......:ljmm....wdgQT@522
`
`ExN;+zNair:a+zQSEE“W
`
`...........VL+L+L+
`
`_\Nw
`
`Page 8 of 58
`
`
`592%:v
`
`
`
`
`...........0
`
`
`
`.....xlc
`
`,V
`
`
`
` 32:9595/2:0L23:.xvii;A830\éhKEEPQ1:640:083:.:_a......a:......e,a......4;......fa......fie......«a\53%|zwmfixmi:/mm5sz0/2225./so
`....../\/l\.a.a,g/Jflzl.&32.rU0
`
`
`
`
`
`
`
`2+mgl2&3xmi:
`
`N»
`
`AlevmtleQSxSSQ/,lQmm2Maggi:
`
`
`
`
`
`
`
`
`Page 8 of 58
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 7 0f 20
`
`US 8,170,040 B2
`
`ij5.5ml:NI:95aa9$3:
`
`m._Om.:e
`
`ml:v.5m._OAnn:9a
`
`9
`
`@632a
`
`aF
`
`ml:
`
`N._O
`
`_\._O
`
`Nu::_
`
`
`
`
`aw#9¥
`
`\\
`
`\ v
`
`mwOwm2
`
`NmOwNm_
`
`_\mOwwm_
`
`A
`
`2&va
`
`8.3.3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OZL’QOLL
`
`Page 9 of 58
`
`Page 9 of 58
`
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 8 0f 20
`
`US 8,170,040 B2
`
`
`
`
`
`AATz.mlz£SxA§AAAQIzQSXAEA
`
`.///
`
`AA+A..NI2&3xNE:
`
`
`
`A......A
`
`
`
`
`A
`
`A22.592Wm
`
`
`
`A.N+UNAZS92:iuNAZ.392
`
`
`
`A.cNAz:wz
`
`.+A»
`
`
`
`+|£3.z......5382TzA:
`EAA/NAA“m{MEXSAwfiA
`ENAmmo
`
`
`
`
`
`
` /2:082:92;6-2:.AnmjoAEsOAR:AA+E._:A_o:o:0AB...A.__
` ANAIzQQAxm_:a}
`
`
`mAszQEAE
`
`
`.A.A..FT2AAA:%\<.....RAJ/3.3:.......
`A\\..\....\\A....AVA--
`
`moanmu.0:
`
`A2A+>AASE:
`
`A:+2£35:
`
`tfisg
`
`II.-
`
`3.592
`
`
`
`
`
`
`-_AAA
`
`
`
`—N”B’07 gz) $011021? 09L
`
`AA.A/._:_.=>_V
`
`\\_/ V
`OZL ’9 OW/
`
`
`
`(Z—N
`
`0])
`
`.01+0€I
`
`<17
`
`Page 10 of 58
`
`Page 10 of 58
`
`
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 9 0f 20
`
`US 8,170,040 B2
`
`6?
`
`E
`«a
`
`d—Z
`
` 1.
`
` (35311m10011
`
`
`
`
`g
`o
`“‘
`
`FIG.2C
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`V
`E12
`
`
`
`|l_55
`
`ZL'IO
`LL'IO
`OL'IO
`
`0011
`
`4T
`
`
`
`
`|l_‘4
`
`|l_13
`
`9'IO
`S'IO
`17'IO
`S'IO
`Z'IO
`L'IO
`
`|l_22
`
`|l_1
`
`IESZZ
`
`AAL(11) />
`
`\
`
`/—\V/\
`017L
`
`/
`
`\ AR /
`figmosf
`
`/—\/\ /'
`\lewémi
`
`Page 11 0f58
`
`Page 11 of 58
`
`

`

`S.
`
`2B
`
`m.22;ZQSXNEw0\){x0m1Ea‘‘oe......7‘..NHmu»0
`24+2«3::A:+zwmedg:AWmwm\_Na88aP.a”.GE
`‘TL.0u.m0.ummN2W”.ENfi"NQN;.n‘._19AZHI
`
`
`
`....5.V~\<AN+MH.,._..WwL
`M...........m
`
`
`Vfigz;:92A325m:...........aim:U0
`
`\.\u-:\uu\.\-uuuI
`
`
`
`
`
`Am
`
`1E
`
`Page 12 of 58
`
`
`m:ixmfimuzsmfixflimAQVIvam,NIZwms/XNVQE/mef
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`\ZQQNXNHEENM,5-230$936/SAzémofigA2:_8.2;APBNIOi83.:3+2:83:0:0a::_U......
`
`
`
`
`
`
`
`OZLiéOLL
`
`Page 12 of 58
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 11 of 20
`
`US 8,170,040 B2
`
`»
`6
`3*
`//2
`,
`
`—>
`
`3
`O
`
`<r
`0')
`o
`
`N__.p_|
`A OQ)
`
`:5V] _|
`2
`
`fl. 4— 173‘”
`(D 1— 88'”
`— <— 68‘”
`<— L?”
`1— OT”
`(— 6L‘II
`
`é?
`\d _l
`5.
`
`\
`
`NJ
`o
`o
`N
`
`FIG.2E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`E
`
`
`
`
`
`
`
`
`
`
`/
`
`\
`
`/—\/\ /
`691002?
`
`\
`
`/
`/—\/\
`621001?
`
`Page 13 of58
`
`Page 13 of 58
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 12 0f 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`
`
`2+EI2&3x3:
`
`
`
`
`
`
`
`Séwéw2.NI2:.3x643/wx/<_\_
`
`
`I>3IimixgsVAN/NIzQSXNEE
`
`
`ALT€53Q+|4Iz§dmaFAIR/z5",;,,,..rz......z............(
`
`
`gmiémfiié\_33"MWnmENm.m_.Ag3m2,:2pN
` 8.2;$340/2:0L3:18-er3.98:0.2QV353.830:05%:i:a......a\h......ea......4an;\a......ae......eI/\Q?I2&3VANS:/A\W:22vaA/5QO.........../Nmomm.
`
`
`
`.010A,mIzMEI.,,«”783\m2.,,_V+
`.......-......-.-.........IEM..u...nun.I*$32in$32,392...........aims.2:92737%S\......,......Illa.flm€2inN...........
`
`
`
`
`
`
`
`
`
`
`
`rmoE6.
`
`......7Au
`
`
`uccu.
`
`ENUfa
`
`2g+{3:3A:+2£3§<Wm
`
`...........,,,,m
`
`
`
`
`
`
`
`«Mm
`
`+
`RmV)*
`
`,0
`
`Page 14 of 58
`
`Page 14 of 58
`
`€
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 13 of 20
`
`US 8,170,040 B2
`
`1004,13)l1CL?0L8
`
`|L8
`
`
`
`ML(1,13)T
`
`|L7
`
`0L50L6
`
`
`T |L6
`
`T |L5
`
`
`
`1
`
`0L3OL4
`
`
`
`T
`
`|L4
`
`|L3
`
`lML(4,4)T 0L2
`
`
`
`
`
`
`0L1
`
`|L1
`
`
`TML(1,4)l |L2
`
`yA
`
`FIG.3A
`
`
`
`IA\_‘;'
`I-\_I.\'
`
`
`
`
`
`
`
`
`
`Page 15 of58
`
`Page 15 of 58
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 14 0f 20
`
`US 8,170,040 B2
`
`
`
`
`
`@wsz.5...).
`
`thIzQSXNifi
`
`
`
`
`
`
`
`30I33I2&3VANS:
`
`
`
`///
`
`2:052:32:8-2:.AomjofvfioamzE35630So6:.S.
`
`:+5NI2&3var:
`
`
`
`(manIznmfixgé
`
`W.
`
`
`
`Va,0
`
`73/218} OW/
`
`
`
`AZXNfiizhué‘E3+2Mada:\N
`
` A~+§ziw§3:52in$2.53...........@592Vmm3‘u.
`
`
`....../mm
`9+.T2%a;n.I.
`
`
`
`
`
`
`Fm\\)W,EW0
`
`m8».mm.0:—
`
`Page 16 of 58
`
`Page 16 of 58
`
`
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 15 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`
`
`9'IO
`S'IO
`17'IO
`S'IO
`Z'IO
`L'IO
`
`IL’I
`
`|L2
`
`
`
`
`
`FIG.3C
`
`Page 17 of 58
`
`Page 17 of 58
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 16 of 20
`
`US 8,170,040 B2
`
`
`
`2+3?szng:
`
`N2-
`
`2%
`
`INagI2&3xNE:/
` -uh34m?4::62:8-2:.N......N
`
`QWNIzQSXNE/N
`Ana-N30NIPQ/zoN83112:N
`
`
`a N......Z......
`HHS-Q3030a::_
`
`/
`
`,/QN.NI253VANS:
`
`//
`
`/
`
`N a.
`
`.....
`
`
`
`.........../
`
`2&2in
`
` 234+
`
`
`
`.NN..-.NN-NN.N-
`
`2£3V§N
`
`\Doom
`
`Gm.UHH
`
`
`
`NI.{MEX-E
`
`N3+>15qu
`
`
`
`/—\V/\
`
`/
`
`(z—NTBU'D-IUI 47051
`
`\N . /—\(/ \ /
`OZL’S’OLL
`
`Page 18 of 58
`
`Page 18 of 58
`
`
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 17 of 20
`
`US 8,170,040 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9‘“
`9‘“
`17'“
`‘8'“
`Z‘II
`
`Page 19 of 58
`
`Page 19 of 58
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 18 of 20
`
`US 8,170,040 B2
`
`:22va/
`
`ۤIEMSXNEE
`
`flrm_
`
`§I>33I2&35:://-(23:.3+3on:+Po_:_
`
`
`
`
`“2:09zjovxvii;98:01::_V630Socob::_a......a;......ea......:......E......:......:I
`
`,
`
`9+3mI23:53::
`
`/€m..mI2&3xNE:
`
`
`
`»VJ,wEx§+2£Q~z§3+2media\N\m”38mm.UE
`
`Page 20 of 58
`
`
`
`
`
`
`
`
`
`/
`
`A”
`......_\7.,
`
`Page 20 of 58
`
`
`
`

`

`US. Patent
`
`May 1, 2012
`
`Sheet 19 of 20
`
`US 8,170,040 B2
`
`o:0:
`
`80m
`
`
`
`
`
`ONO:0::02:003020.500:.:0:_>>0:29:0:::0x:__060E969:0:000E9“.
`
`
`
`
`
`
`
`
`
`
`
`
`
`‘:__069E969:00620J--.
`
`
`
`0:00:965:00:=0:0_:>>:m:0::::0:_>>0::Q:_
`
`
`
`
`
`«060:000:
`
`
`
`
`
`
`
`
`
`80::m:0:::5:00:600::a::0m
`
`
`
`
`0::E0:00E:069Em:69:003:05“.E0:00E:062E969:003:
`
`
`0:::052:359:95:59:50:39:10::DEV—m:>350:30:350::
`060:000:0:006:05:00::000.6::.”::-D00:00:
`
`
`
`
`0:0:
`
`:00:
`
`\
`
`0::0:20:E:25:9:0::
`
`
`
`:000.6:E::-3:0800:
`
`:o_:m:_:000
`
`
`
`
`
`
`
`mm;E0:06:069Em:69:00:0\:m:9::6:00:500::q::00
`
`
`
`6:05:00:
`
`
`
`
`
`
`
`
`
`6:50:350:::006:062Em:69:0:000E0:m:_:._m:005:05:00:
`
`
`
`
`
`
`
`
`
`050600::00:0:0::0:90:00.Zmo._090:0062E0:::_00:0:_>>0062E063620
`
`
`
`
`
`
`
`
`
`\0.02:0:m:__0>m:090:0062E:000:_00:0:30069E060:000::00:0:
`
`
`
`
`
`
`
`
`
`omofl:0:0__0::0::02:002020500:60:05:00::000:06:3059:00::E9”.:0603:0:96:
`
`
`
`
`
`
`
`
`069E:000:_062000..0_6:05:800:::0_:>>E0:00:0:_>>0062E0:000:009300::
`2mo:090:0069E0:000:0:::::0E0:00:03:00:9:020:000:0\:0500"M02828
`
`
`
`
`
`
`
`._0::::00
`
`
`
`
`
`96:80:000::a:m:_:0:0E:3000:003:03030::0:::_00:0:0c0m0:0:0::9:030:800:60L050
`
`0:0>0::
`
`6:0_:0__0>0::
`
`
`
`200:09:0069E0::090:0069EE0:
`
`2:250::=0:0:
`
`
`
`6:30:39::0:0v6::0_:_:0E0:5:00:500E6:0::00300:0>060m
`
`
`
`
`
`cor
`
`:6.UHH
`
`
`
`Page 21 of 58
`
`Page 21 of 58
`
`
`
`
`
`
`
`
`

`

`m«a.UE
`
`waP
`
`SU
`
`2
`
`
`
`adiooii3.\3.318
`
`\_fl.
`
`m358mGE3?:m2m.UE
`
`mayo23?:
`
`m:38
`
`u3So:0mANNE/o
`1,zN...M:_\,/S.\Swim.
`
`ciao
`
`—<m.05
`
`8,So:0
`
`B9.2BEAU0v<m.05.M,m<m.UEm30So
`
`Page 22 of 58
`
`Page 22 of 58
`
`
`

`

`US 8,170,040 B2
`
`1
`FULLY CONNECTED GENERALIZED
`BUTTERFLY FAT TREE NETWORKS
`
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`
`
`
`
`This application is related to and claims priority of PCT
`Aoplieation Serial No. PCT/USO8/64603 ent'tled “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
`Vlay 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 by reference
`'n its entirety the US. 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 G1NERALIZED MULTI-STAGE
`
`\IETWORKS” by Venkat Konda assigned to the same
`assignee as the current application, filed VIar. 6, 2008, the
`JS. Provisional Patent Aflplieation Ser. No. 60/905,526
`entitled “LARGE SCALE CROSSPOII\T REDUCTION
`WITH NONBLOCKING UNICAST & VIULTICAST IN
`ARBITRARILY LARGE VIULTI-STAGE NETWORKS”
`
`
`
`
`
`
`
`
`
`3y Venkat Konda assigned to the same assignee as the current
`application, filed Mar. 6, 2007, and the US. Provisional
`3atent Application Ser. No. 60/940,383 entitled “FULLY
`
`CONNECTED GENERALIZ1D MUL I-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 3y reference
`'n its entirety the US. oatent application Ser. No. 12/601,274
`entitled “FULLY CONNECTED GENERALIZED MULTI-
`EINK MULTI-STAGE NETWORKS” by Ve 1kat Konda
`assigned to the same assignee as the current application filed
`concurrently, the PCT Application Serial No. PCT/US08/
`64604 entitled “FULEY CONNECTED GENERALIZED
`VlULTI-LINK MULTI-STAGE NETWORKS” by Venkat
`(onda 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
`
`
`
`
`
`VIULTI—LINK MULTI—STAGE NETWORKS’ by Venkat
`{onda 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 “F ULLY CONNEClED
`
`G1NERALIZED FOLDED MULTI- STAGE NETWORKS”
`
`3y Venkat Konda assigned to the same assignee as the current
`application, filed May 25, 2007 and the US. Provisional
`3atent Application Ser. No. 60/940,392 entitled “FULLY
`
`CONNECTED GENERALIZED STRICTLY NON-
`BLOCKING MULTI-LINK MULTI-STAGE NETWORKS”
`
`3y Venkat Konda assigned to the same assignee as the current
`application, filed May 25, 2007.
`This application is related to and incorporates by reference
`in its entirety the US. patent application Ser. No. 12/601 ,275
`entitled“VLSI LAYOUTS OF FULLY CONNECTED GEN-
`
`ERAI ,IZED NETWORKS” by Venkat Konda assigned to the
`
`Page 23 of 58
`
`2
`same assignee as the current application filed concurrently,
`the PCT Application Serial No. PCT/U808/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 US. Provisional Patent Application Ser. No. 60/940,394
`entitled “VLSI LAYOUTS OF FULLY CONNECTED GEN-
`
`ERALIZED NETWORKS” by Venkat Konda assigned to the
`same assignee as the current application, filed May 25, 2007.
`This application is related to and incorporates by reference
`in its entirety the US. Provisional Patent Application Ser. No.
`61/252,603 entitled “VLSI LAYOUTS OF FULIY CON-
`
`NECTED NETWORKS WITH LOCALITY EXPLOITA-
`
`TION” by Venkat Konda assigned to the same assignee as the
`current application, filed Oct. 16, 2009.
`This application is related to and incorporates by reference
`in its entirety the L .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.
`
`BACKGROUND OF INVENTION
`
`Clos switching network, Benes switching network, and
`Cantor switching network are a network of switches config-
`ured as a rnulti-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 (eg. crossbar)
`switch having the same number of inputs and outputs. Clos
`and Benes networks are very popularly used in digital cross-
`connects, switch fabrics and parallel computer 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, Bateher-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 Networks of radix two are shown
`to be built with back to back baseline networks which are
`rearrangeably nonblocking for unicast connections.
`US. Pat. No. 5,451,936 entitled “Non-blocking Broadcast
`Network” granted to Yang et al. is incorporated by reference
`herein as background of the invention. This patent describes
`
`20
`
`25
`
`30
`
`40
`
`60
`
`Page 23 of 58
`
`

`

`US 8,170,040 B2
`
`Nd
`
`switches with each of them having d outlet links and 2><d
`incoming links connecting from switches in its immediate
`succeeding stage. The network also has (logd N)—l middle
`stages with each middle stage, excepting the root stage, hav-
`ing
`
`switches, and each switch in the middle stage has (1 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
`
`2><N
`
`switches, and each switch in the middle stage has d incoming
`links connecting from the switches in its immediate preced-
`ing stage and d outgoing links connecting to the switches in its
`immediate preceding stage. Also the same generalized but-
`terfly fat tree network is operated in rearrangeably nonblock—
`ing manner for 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 (logd
`N) stages is operated in strictly nonblocking manner for mul-
`ticast includes a leaf stage consisting of an input stage having
`
`N Z
`
`switches with each of them having (1 inlet links and 3><d
`outgoing links connecting to its immediate succccding stagc
`switches, an output stage having
`
`N E
`
`switches with each of them having d outlct links and 3><d
`incoming links connecting from switches in its immediate
`succeeding stage. The network also has (logd N)—1 middle
`stages with each middle stage, excepting the root stage, hav-
`ing
`
`3><N
`
`5
`
`20
`
`25
`
`30
`
`40
`
`60
`
`3
`a number of well known nonblocking multi-stage switching
`network designs in the background section at column 1. line
`22 to column 3, 59. An article byY. Yang, and G. M., Masson
`entitled, “Non-blocking Broadcast Switching Networks”
`IEEE Transactions on Computers, Vol. 40, No. 9, September
`1991 that is incorporated by reference as background indi-
`cates that if the number of switches in the middle stage, In, of
`a three—stage network satisfies the relation mimin((n—l)(x+
`‘19)) where léxéminm—Lr), the resulting network is non-
`Jlocking for multicast assignments. In the relation, r is the
`number of switches in the input stage, and n is the number of
`'nlet links in each input switch.
`US. Pat. No. 6,885,669 entitled “Rearrangeably Non-
`alocking Multicast Multi—stage Networks” by Konda showed
`hat three-stage Clos network is rearrangeably nonblocking
`for arbitrary fan-out multicast connections when 11122xn.
`And US. Pat. No. 6,868,084 entitled “Strictly Nonblocking
`VIulticast Multi-stage Networks” by Konda showed that
`hree—stage Clos network is strictly nonblocking for arbitrary
`fan-out multicast cmmections when m§3><n—1.
`
`
`
`In general multi-stage networks for stages of more than
`hree and radix of more than two are not well studied. An
`
`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 d2><N><(logd
`N)2'58 for strictly nonblocking unicast network. Similarly
`US. 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 d2><N><(logd
`N)2 for strictly nonblocking unicast, (by using long number
`of Benes Networks for d:2) and without counting the cross-
`points in multiplexers and demultiplexers. Jonathan Turner
`studied the cascaded Benes Networks with 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.
`
`The crosspoint complexity of all these networks is prohibi-
`tively large to implement the 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.
`
`SUMMARY OF INVENTION
`
`A generalized butterfly fat tree network comprising (log,
`N) stages is operated in strictly nonblocking manner for uni-
`cast includes a leaf stage consisting of an input stage having
`
`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 succeeding stage, 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 outgoing links connecting to the switches in its
`immediate preceding stage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary Symmetrical
`Butterfly fat tree network Vbfl(N,d,s) having inverse Benes
`connection topology of three stages with N:8, d:2 and 5: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 Vbfl(N,d, s) with (logd N) stages strictly
`nonblocking network for unicast connections and rearrange-
`ably nonblocking network for arbitrary fan-out multicast con-
`nections in accordance with the invention.
`FIG. 1C is a diagram 100C ofan exemplaryAsymmetrical
`Butterfly fat tree network Vbfl(Nl,N2,d,2) having inverse
`Benes connection topology of three stages with N1:8,
`\Iz:p*Nl: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
`'nvention.
`
`FIG. 1D is a diagram 100D of a general asymmetrical
`Butterfly fat tree network Vbfl(N1,N2,d,2) with Nzrp’I‘Nl and
`with (logd N) stages strictly nonblocking network for unicast
`connections and rearrangeably nonblocking network for arbi-
`rary fan-out multicast connections in accordance with the
`'nvention.
`
`FIG. IE is a diagram 1003 of an exemplary Asymmetrical
`Butterfly fat tree network Vhflafl1 ,N2,d,2) having inverse
`Benes connection topology of three stages with N2:8,
`\Ilrp*N2:24, where p:3, and d:2 with exemplary multicast
`connections, strictly nonblocking network for unicast con—
`1ections and rearrangeably nonblocking network for arbi-
`rary fan—out multicast connections, in accordance with the
`'nven ion.
`
`
`
`FIG. 1F is a diagram 100F of a general asymmetrical
`3utte‘fly fat tree network Vbfl(N1.N2,d,2) with N1:p*N2 and
`with (log4 N) stages strictly nonblocking network for unicast
`connections and rearrangeably nonblocking network for arbi-
`rary fan—out multicast connections in accordance with the
`'nven ion.
`FIG. 2A is a diagram 200A of an exemplary Symmetrical
`Butte‘fly fat tree network Vbf,(N,d,s) having inverse Benes
`connection topology of three stages with N:8, d:2 and F1
`with exemplary unicast connections rearrangeably nonblock-
`ing network for unicast connections, in accordance with the
`inven ion.
`
`
`
`FIG. 2B is a diagram 200B of a general symmetrical But-
`terfly fat tree network Vbfl(N,d,s) with (log, N) stages and
`5: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 Vbfl(Nl,N2,d,l) having inverse
`
`Page 25 of 58
`
`6
`Benes connection topology of three stages with Nl:8,
`N2:p*N1:24 where p:3, and d:2 with exemplary unicast
`connections rearrangeably nonblocking network for unicast
`connections, in accordance with the invention.
`FIG. 2D is a diagram 200D of a general asymmetrical
`Butterfly fat tree network be,(N1,N2,d, l) with N2:p"‘N1 and
`with (logd 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 Vbfl(N1,N2,d,l) having inverse
`Benes connection topology of three stages with N2:8,
`N1:p*N2:24, where p:3, and d:2 with exemplary unicast
`connections rearrangeably nonblocking network for unicast
`connections, in accordance with the invention.
`FIG. 2F is a diagram 200F of a general asymmetrical
`Butterfly fat tree network Vbfl(N 1,N2,d,1) with N 1:p*N2 and
`with (logd N) stages rearrangeably nonblocking network for
`unicast connections in accordance with the invention.
`FIG. 3A is a diagram 300A of an exemplary symmetrical
`multi-link Butterfly fat tree network th.,,k_bfl(N,d,s) having
`inverse Benes connection topology of five stages with N:8,
`d:2 and F2 with exemplary multicast connections, strictly
`nonblocking network for unicast connections and rearrange-
`ably nonblocking network for arbitrary fan-out multicast con-
`nections, in accordance with the invention.
`FIG. 3B is a diagram 300B ofa general symmetrical multi-
`link Butterfly fat tree network szmk_bfi(N,d,2) with (logd N)
`stages strictly nonblocking network for unicast connections
`and rearrangeably nonblocking network for arbitrary fan-out
`multicast connections in accordance with the invention.
`
`FIG. 3C is a diagram 300C of an exemplary asymmetrical
`multi-link Butterfly fat tree network Vm[WPbfl(N1,N2,d,2)
`having inverse Benes connection topology of five stages with
`N1:8, N2:p*Nl: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 ButterIy fat tree network lemk_bft(Nl,N2,d,2)
`with N2:p*N1 and with (log, N) stages strictly'nonblocking
`network for unicast comiections and rearrangeably nonblock-
`ing network for arbitrary fan-out multicast connections in
`accordance with I16 invention.
`FIG. 3E is a diagram 300E of an exemplary asymmetrical
`multi—link ButterIy fat tree network Vmfink_bfl(Nl,N2,d,2)
`having inverse Be 1es connection topology of five stages with
`N2:8, N1:p*N2:24, where p:3, and d:2 with exemplary
`multicast connect'ons, 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 ciagram 300F of a general asymmetrical
`multi—link ButterIy fat tree network szmk_bfl(Nl,N2,d,2)
`with N 1:p*N2 and with (log, N) stages strictly'nonblocking
`network for unicast comiections and rearrangeably nonblock-
`ing network for arbitrary fan-out multicast connections in
`accordance with I16 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.
`
`
`
`FIG. 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 ofFIG.
`
`20
`
`25
`
`30
`
`40
`
`60
`
`Page 25 of 58
`
`

`

`US 8,170,040 B2
`
`7
`5A1; FIG. 5A4 is a diagram 500A4 for integrated circuit
`placement and route implementation ofthe diagram 500A] of
`FIG. 5A1.
`
`DETAII ED DESCRIPTION OF THE INVENTION
`
`5
`
`8
`
`V}-0,d_m,mk(Nl,N2,d,s) with numerous connection topologies
`and the scheduling methods are described in detail in the PCT
`Application Serial No. PCT/U808/64604 that is incorporated
`by reference above.
`3) Strictly and rearrangeably nonblocking for arbitrary
`fan-out multicast and unicast for generalized folded multi-
`stage