`
`(12) United States Patent
`Konda
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,270,400 B2
`*Sep. 18, 2012
`
`(54)
`
`(75)
`(73)
`
`(*)
`
`(21)
`(22)
`(86)
`
`(87)
`
`(65)
`
`(60)
`
`(51)
`
`(52)
`(58)
`
`FULLY CONNECTED GENERALIZED
`MULT-STAGE NETWORKS
`
`Inventor: Venkat Konda, San Jose, CA (US)
`Assignee: Konda Technologies Inc., San Jose, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 439 days.
`This patent is Subject to a terminal dis
`claimer.
`
`Notice:
`
`Appl. No.:
`
`12/530,207
`
`PCT Fled:
`
`Mar. 6, 2008
`
`PCT NO.:
`S371 (c)(1),
`(2), (4) Date:
`
`PCT/US2O08/056.064
`
`Sep. 6, 2009
`
`PCT Pub. No.: WO2O08/109756
`PCT Pub. Date: Sep. 12, 2008
`
`Prior Publication Data
`US 2010/O135286 A1
`Jun. 3, 2010
`
`Related U.S. Application Data
`Provisional application No. 60/905,526, filed on Mar.
`6, 2007, provisional application No. 60/940,383, filed
`on May 25, 2007.
`
`Int. C.
`(2006.01)
`H04L 2/28
`U.S. Cl. ......................... 370/388; 7.10/316:379/342
`Field of Classification Search .................. 370/388,
`370/390
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`2002/0031124 A1
`3/2002 Li ................................. 370,390
`* cited by examiner
`Primary Examiner — Dang Ton
`Assistant Examiner — Lionel Preval
`
`ABSTRACT
`(57)
`A multi-stage network comprising (2xlog N)-1 stages is
`operated in strictly nonblocking manner for unicast, also in
`rearrangeably nonblocking manner for arbitrary fan-out mul
`ticast when S22, and is operated in strictly nonblocking
`manner for arbitrary fan-out multicast when S23, includes an
`input stage having
`
`N
`d
`
`switches with each of them having d inlet links and sxd
`outgoing links connecting to second stage Switches, an output
`stage having
`
`N
`d
`
`switches with each of them having d outlet links and sxd
`incoming links connecting from Switches in the penultimate
`stage. The network also has (2xlog N)-3 middle stages with
`each middle stage having
`
`SXN
`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 outgoing links connecting to the Switches in
`its immediate Succeeding stage. Also each multicast connec
`tion is set up by use of at most two outgoing links from the
`input stage Switch.
`
`21 Claims, 29 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`MS(3,2)
`
`MS(3,3)
`
`MS(18)
`
`
`
`MS(3,8)
`
`OL1
`
`OLF
`
`Page 1 of 64
`
`FLEX LOGIX EXHIBIT 1011
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet],0f29
`Sheet 1 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`r40
`
`N40
`
`M40
`
`V40
`
`m40
`
`Q40
`
`N40
`
`w40
`
`
`
`aavi
`
`.dd
`
`Nd
`
`wd
`
`Page 2 of 64
`
`Page 2 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet20f29
`Sheet 2 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`
`
`IVI "OIH
`
` H<H.Umm
`
`
`
`Page 3 of 64
`
`Page 3 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 3 of 29
`
`US 8,270,400 B2
`
`|TO
`
`ZTO
`
`£TO
`
`#7 TO
`
`GTO
`
`9TO
`
`Z TO
`
`9TO
`
`
`
`
`
`ZVI "OIH
`
`Page 4 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 4 0f 29
`Sheet 4 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`|
`
`_\._O
`
`‘lN112m3x9§
`
`3.mlZwc‘NXNvmfiNA:IZ,k05m3
`
`8-230
`
`2:0
`
`Swjo
`
`
`
` 3+3“...Vmemlz$3de5.8:0
`
`
`
`
`
`Qx3I20.03x3?,,\
`
`3.STExamI2M30&3
`
`
`
`A2x3+{$332
`
`
`...........nnu:22.cm:
`
`Ag
`
`
`
`43.3.3
`
`A52rm.Es.
`
`.UHH
`
`
`93/157zxmfiwmroiofl3|hymns/021080(of,(\o?,,\M:.\p\‘0,\‘\/y\_/\/\_(
`
`
`
`
`moo?
`
`
`
`Page 5 of 64
`
`Page 5 of 64
`
`
`
`
`
`
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet50f29
`Sheet 5 Of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`% As
`
`
`
`
`
`
`
`Page 6 of 64
`
`Page 6 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 6 of 29
`
`US 8,270,400 B2
`
`
`
`M.
`
`
`
`
`
`
`
`LOI "OIDH
`
`Page 7 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 7 0f 29
`Sheet 7 Of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`m:-ia.
`
`o
`
`aCF9\no‘Vx‘
`wwaa‘\
`
`,.
`xx»\
`
`
`(is2,42.55//“no’(
`
`m:-u...40'
`wk...»9,.”A$922
`
`RSWA/C?CW!—??????????????????
`
`$0WOQ’H/fianew:
`
`k/Maég
`a.,._.
`
`$532
`an:
`I
`A:_
`
`
`
`
`
`
`
`
`
`an:.me
`
`0:
`
`
`
`./I\|/\/\_03
`
`I
`
`[Qums.
`
`ANN:
`
`Sims.
`
`8392
`
`
`
`_\.__
`
`I:
`
`I:
`
`VI:
`
`1:
`
`1:
`
`ml:
`
`ml:
`
`Page 8 of 64
`
`Page 8 of 64
`
`
`
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 8 0f 29
`Sheet 8 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`QEIZvXRanmIZumfiwwwwé............."..M.U.;...Z:N.._.:+U\Z.CWE
`
`
`
`
`
`
`
`Afizrqjo.I
`
`23:0.I
`
`u:22va
`
`flzxqumnzfimfixmgw
`
`
`
`A
`
`
`
`32$,:.__>_
`
`.
`
`:ws.
`
`Exfl+2£3E§
`
`$93.6
`
`Vszxilz
`
`
`ME53%,\
`
`QEXSIZEMSXNKNS
`
`
`
`$93.;$3.:
`
`63:0w:3.
`
`|TO
`_‘._O
`
`
`
`.u.'2«Exam:«N133QuLfENr/E
`
`4/.
`(1-p)},
`
`:"mI2«3Ex:3I2fi3:5::
`AlA‘IIAl“a
`
`
`
`
`/,,\\\J://(\\rw\\>,fi//(_\,,<\\Jfi//I\r\\J\//(\rK\)fl//(\_
`
`
`owr€9z£=§~§£+ciRIZQSVEHESo?o:\m:
`.05
`
`
`
`
`
`
`
`
`
`Page 9 of 64
`
`Page 9 of 64
`
`
`
`
`
`
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet90f29
`Sheet 9 Of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`s;6‘6%.“mw_
`
`
`
`
`
`
`m:.UHH
`CHI "OIH
`
`
`Page 10 of 64
`
`Page 10 of 64
`
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 10 of 29
`
`US 8,270,400 B2
`
`
`
`
`
`IGII ‘5)I, H.
`
`ZSI
`
`Page 11 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 11 of 29
`
`US 8,270,400 B2
`
`
`
`
`
`ZGII "OIDH
`
`Page 12 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 12 0f 29
`Sheet 12 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`28:0
`
`QxiI2&3xg?
`
`ST5x3I2&3wag:
`
`(N) TO <–
`
`Ex3I>53xaux/II
`
`ZVmSEE
`
`938,:
`
`
`
`
`
`$22.:92
`
`6:02
`
`:10:u.
`
`
`
`CQXNNIIZVWSXNBr/V+U¢QVI=vSIAl«IzWSXNK
`
`
`
`
`
`
`
`
`
`
`
`r40
`
`:wfzmixsms
`
`
`
`moor
`
`r,\,g,Ix)2/\I_r,I,x)k2,,lK(\mK\I\\JIIII[\\
`
`03:72mfiuwmrwoioiQI2QEIE+OE0.2o:\E.UE
`
`1,I_\\],<III(,\I
`
`Page 13 of 64
`
`Page 13 of 64
`
`
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 13 Of 29
`
`US 8,270,400 B2
`
`ZTO
`
`çTO 4–
`
`9TO
`
`9TO
`
`/TO
`
`VZ “OICH
`
`0+1 ,
`
`
`
`
`
`
`
`Page 14 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 14 of 29
`
`US 8,270,400 B2
`
`
`
`
`
`LVZ “OICH
`
`TI
`
`TI
`
`TI
`
`Page 15 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep.18,2012
`
`Sheet150f29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`m._O
`:0
`m._O
`m._O
`©._O
`N._O
`SO
`_\._O
`
`
`o
`s
`
`3&4“:2
`
`a
`
`
`
`.992
`
`8$va
`
`
`
` \3.8m:wwfgimz MNJENWE
`
`1‘:‘A‘QAEs?Amtmvwg2:Grim—2r;
`
`
`
`
`
`
`
`
`
`
`ZWZ º?IH
`
`:35:4
`
`aim:
`
`57m
`.mfi4:
`
`.38&va
`
`
`
`W:
`
`I:
`
`1:
`
`Page 16 of 64
`
`Page 16 of 64
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 16 of 29
`
`US 8,270,400 B2
`
`(p)TO
`
`|TO
`
`
`
`Z8IZ "OIDH
`
`
`
`
`
`
`
`
`
`
`
`Page 17 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep.18,2012
`
`Sheet170f29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`sawI2&3Xmiyfl/
`
`
`
`sawIzQSXNEE
`
`QxmflmI2&35::
`
`\I//
`
`
`
`f:72me\NmooN
`>\(\)4/l\
`*Nv%ofi+0mfl
`
`QmIzQExSE
`
`
`
`QT>3IzQSXNEE
`
`/
`
`
`
`AZINIZQSXNEE/
`
`I“IZQSX2A2man
`
`
`
`uuuuuuuu".uII-IAumI-N-J"A—xnvaE"xbtévI—S—
`
`AIIMfiafiAllfll
`QTszqdm::N/
`
`
`
`
`
`
`
`
`//AUIN\SI__>_
`
`
`
`
`
`
`
`
`
`
`
`
`
` rx/(I>\6NN:AV.........uuuN;m:._4dw,4/:PEN?IF;3:NT2«3va
`
`
`
`Nm—N.UFE
`
`QIzQSvaoioQov
`A_v()<)/\())/\_‘I__>_
`
`Page 18 of 64
`
`Page 18 of 64
`
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet180f29
`Sheet 18 Of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`va
`
`
`
`07||0810 || ||
`
`Page 19 of 64
`
`
`
`_\.__
`
`.__
`
`ll:
`
`.v.__
`
`l:
`
`1:
`
`NI:
`
`ml:
`
`\oE
`
`UN.05.—
`COZ "?INH
`
`
`
`
`
`
`
`
`Page 19 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet190f29
`Sheet 19 Of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`N40
`
`m._0
`
`.30
`
`owdall
`9-0T
`Mmel
`VNIOT
`NVIOLII
`awn”
`SHOT
`QWOQI
`CIOAII
`@401
`Aw._OA|I
`30"
`SOT
`30"
`
`
`or:
`9.:3|
`mru
`
`o:
`
`30
`
`FwO
`
`mwO
`
`
`
`
`
`
`
`
`
`HUN
`\mWi—W/
`
`€892
`admz
` UP!
`
`32°C)TJA àý
`
`
`
`
`
`|×I OZ. "?INH
`
`
`
`
`
`_\.__
`
`I:
`TI
`
`.=
`TI
`
`VI:
`
`I:
`TI
`
`.1:
`
`Nu:
`
`ml:
`
`Page 20 of 64
`
`Page 20 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet200f29
`Sheet 20 Of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`
`
`me
`
`
`
`
`
`Sim:
`
`
`
`
`
`NON.Uum
`
`\
`
`
`
`_.n__
`
`I__
`
`1:
`
`vi:
`
`1:
`
`.1:
`
`NI:
`
`ml:
`
`Page 21 of 64
`
`Page 21 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 21 of 29
`
`US 8,270,400 B2
`
`LTIO
`
`
`
`ZGIZ “OICH
`
`
`
`ZGIZ "OIDH
`
`
`
`ZOIZ "SOICH
`
`
`
`
`
`Page 22 of 64
`
`
`
`US. Patent
`
`Sep. 18, 2012
`
`Sheet 22 0f 29
`
`US 8,270,400 B2
`
`@Izvxmamlewavu:
`
`
`
`Azxm”NI2&3meng
`
`SNI2£3xNV‘Efl/
`
`Afmnmlzfimfixsg
`
`
`
`2+f”5|25033:me
`
`mexmamlzwmfixau:
`
`\I/
`
`>/
`
`\><
`
`am
`
`QTZQSXNVE
`
`
`
`
`
`
`
`
`
`\//\|£|F<
`
`APN_\:.__>_
`
`3chNQN.UHm
`
`
`@Izsfiérfloiofl3120003331302
`/\\)Z//\\/\/\\K‘l/K,
`
`A:IZ95mgW
`
`
`
`3732
`
`Page 23 of 64
`
`Page 23 of 64
`
`
`
`
`
`
`U.S. Patent
`US. Patent
`
`Sep. 18, 2012
`Sep.18,2012
`
`Sheet230f29
`Sheet 23 Of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`:0
`
`N._OAll
`
`m._OAl
`
`VJOAII
`
`nu1_O
`
`
`
`SO
`
`540
`
`w._O
`
`
`
`
`
`
`
`
`
`
`
`Page 24 of 64
`
`
`
`
`
`2
`
` om?/,8m\/,(\ofi:,,02;o:\HNAVHH
`
`
`
`
`Page 24 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 24 of 29
`
`US 8,270,400 B2
`
`ZTO
`
`GTO
`
`9TO
`
`/TO
`
`
`
`IGHZ * OIH
`
`Page 25 of 64
`
`
`
`U.S. Patent
`US. Patent
`
`Sep.18,2012
`
`Sheet250f29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`_\._0
`
`N._OAll
`
`m._OAl
`
`vJOAII
`
`m._O
`
`w._OL0.5
`
`
`
`
`
`.UHm
`
`awe)
`
`Nm—N
`ZICHZ * OIDH
`
`
`
`No.
`
`
`
`N.:W:
`
`.v.:m:
`
`0.:m:
`
`LIN:
`
`Tm:
`
`T:.:
`
`LIN—H:
`
`OW:m:
`
`MP:
`
`3.:
`
`m7:
`
`9.:
`
`5.:
`
`w—.:
`
`9.:
`
`ON.:
`
`_‘N.:
`
`NN.:
`
`MN:
`
`VN:
`
`
`
`
`
`
`
`
`
`Page 26 of 64
`
`Page 26 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 26 of 29
`
`US 8,270,400 B2
`
`(pZ) TO <–
`
`0ZSO
`
`
`
`|×I HZ. “OICH
`
`
`
`ZHZ “OICH
`
`
`
`ZHZ "OIDH
`
`
`
`
`
`
`
`
`
`Page 27 of 64
`
`
`
`US. Patent
`
`Sep.18,2012
`
`Sheet270f29
`
`US 8,270,400 B2
`
`n\I//.\$3I2&3VANS:..
`
`9NI2£3XNEE/(fl
`.
`I<\AwfimIzwmfixS§<>
`
` A?zragjz
`
`
`
`
`
`AZIQ9v42
`
`QIanIimeNEE"
`
`
`
`93IZQSXNVS/
`
`NEMexAzmzaSm:
`lnl
`
`nt>2+N9NIzMSXNE:
`@mI2m3xam:
`
`4/
`
`
`
`chmI2&3VANS:
`
`GIzQSZVMAoioS\Nn—OON
`GIznmfivéiofl
`rf\\j\\/[k
`
`NmN.me
`
`Page 28 of 64
`
`Page 28 of 64
`
`
`
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 28 Of 29
`
`US 8,270,400 B2
`
`000),
`
`Vº “?INH
`
`
`
`
`
`
`
`
`
`
`
`
`
`ON080||
`
`0/01
`
`Page 29 of 64
`
`
`
`U
`
`nwa
`
`US 8,270,400 B2
`
`w\\C:109m:38:23?:mNS“
`.05
`
`ANNmooFWH
`
`s:2.8th
`
`So
`
`
`
`#4.“.UHm
`
`N._OSO
`
`«.3.0E
`
`c2.52.:
`
`POS”«Gware
`
`N:mSo:0.
`
`t:38
`
`N.__m1S_:_S\aimm3310
`m,
`
`#4?.Uarm
`
`Page 30 of 64
`
`Page 30 of 64
`
`
`
`
`US 8,270,400 B2
`
`1.
`FULLY CONNECTED GENERALIZED
`MULT-STAGE NETWORKS
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is related to and claims priority of PCT
`Application Serial No. PCT/US08/56064 entitled “FULLY
`CONNECTED GENERALIZED MULTI-STAGE NET
`WORKS by Venkat Konda assigned to the same assignee as
`10
`the current application, filed Mar. 6, 2008, the U.S. Provi
`sional Patent Application Ser. No. 60/905,526 entitled
`LARGE SCALE CROSSPOINT REDUCTION WITH
`NONBLOCKING UNICAST & MULTICAST IN ARBI
`TRARILY LARGE MULTI-STAGE NETWORKS by Ven
`15
`kat Konda assigned to the same assignee as the current appli
`cation, filed Mar. 6, 2007, and the U.S. Provisional Patent
`Application Ser. No. 60/940,383 entitled “FULLY CON
`NECTED GENERALIZED MULTI-STAGE 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 PCT Application Serial No. PCT/US08/
`64603 entitled "FULLY CONNECTED GENERALIZED
`BUTTERFLY FAT TREE NETWORKS by Venkat Konda
`25
`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 GENER
`ALIZED BUTTERFLY FAT TREE NETWORKS by Ven
`kat Konda assigned to the same assignee as the current appli
`cation, filed May 25, 2007, and the U.S. Provisional Patent
`Application Ser. No. 60/940,390 entitled “FULLY CON
`NECTED GENERALIZED MULTI-LINK BUTTERFLY
`FAT TREE 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 PCT Application Serial No. PCT/US08/
`646O4 entitled "FULLY CONNECTED GENERALIZED
`MULTI-LINK MULTI-STAGE NETWORKS” by Venkat
`Konda assigned to the same assignee as the current applica
`tion, 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
`tion, filed May 25, 2007, the U.S. Provisional Patent Appli
`cation Ser. No. 60/940,391 entitled “FULLY CONNECTED
`GENERALIZED FOLDEDMULTI-STAGE NETWORKS
`by Venkat Konda assigned to the same assignee as the current
`application, filed May 25, 2007 and the U.S. Provisional
`50
`Patent Application Ser. No. 60/940,392 entitled “FULLY
`CONNECTED GENERALIZED STRICTLY NON
`BLOCKING MULTI-LINK MULTI-STAGENETWORKS
`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 PCT Application Serial No. PCT/US08/
`64605 entitled VLSI LAYOUTS OF FULLY CON
`NECTEDGENERALIZED 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 GENERALIZED NETWORKS by Venkat
`Konda assigned to the same assignee as the current applica
`tion, filed May 25, 2007.
`This application is related to and incorporates by reference
`in its entirety the PCT Application Serial No. PCT/US08/
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`2
`821.71 entitled VLSI LAYOUTS OF FULLY CON
`NECTED GENERALIZED NETWORKS AND PYRAMID
`NETWORKS WITH LOCALITY EXPLOITATION” by
`Venkat Konda assigned to the same assignee as the current
`application, filed Nov. 2, 2008, the U.S. Provisional Patent
`Application Ser. No. 60/984,724 entitled “VLSI LAYOUTS
`OF FULLY CONNECTED NETWORKS WITH LOCAL
`ITY EXPLOITATION” by Venkat Konda assigned to the
`same assignee as the current application, filed Nov. 2, 2007
`and the U.S. Provisional Patent Application Ser. No. 61/018,
`494 entitled VLSI LAYOUTS OF FULLY CONNECTED
`GENERALIZED AND PYRAMID NETWORKS” by Ven
`kat Konda assigned to the same assignee as the current appli
`cation, filed Jan. 1, 2008.
`
`BACKGROUND OF 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 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 if more 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 Networks of 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 Yang et al. is incorporated by reference
`herein as background of the invention. This patent describes
`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 by Y. 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, m, of
`
`Page 31 of 64
`
`
`
`US 8,270,400 B2
`
`5
`
`10
`
`25
`
`30
`
`3
`a three-stage network satisfies the relation m2min(n-1)(x+
`r")) where 1sxsmin(n-1,r), the resulting network is non
`blocking for multicast assignments. In the relation, r is the
`number of Switches in the input stage, and n is the number of
`inlet links in each input Switch.
`U.S. Pat. No. 6,885,669 entitled “Rearrangeably Non
`blocking Multicast Multi-stage Networks” by Konda showed
`that three-stage Clos network is rearrangeably nonblocking
`for arbitrary fan-out multicast connections when ms2xn.
`And U.S. Pat. No. 6,868,084 entitled “Strictly Nonblocking
`Multicast Multi-stage Networks” by Konda showed that
`three-stage Clos network is strictly nonblocking for arbitrary
`fan-out multicast connections when me3xin-1.
`In general multi-stage networks for stages of more than
`15
`three 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 dxNx(log,
`N)
`for strictly nonblocking unicast network. Similarly
`U.S. Pat. No. 6,885,669 entitled “Rearrangeably Nonblock
`ing Multicast Multi-stage Networks” by Konda showed away
`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 dxNx(log,
`N) for strictly nonblocking unicast, (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 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.
`
`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 Succeeding stage. Also the same multi-stage
`network is operated in rearrangeably nonblocking 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 multi-stage network comprising (2xlog N)-1 stages is
`operated in strictly nonblocking manner for multicast
`includes an input stage having
`
`N
`d
`
`switches with each of them having d inlet links and 3xd
`outgoing links connecting to second stage Switches, an output
`stage having
`
`N
`d
`
`switches with each of them having d outlet links and 3xd
`incoming links connecting from switches in the penultimate
`stage. The network also has (2xlog N)-3 middle stages with
`each middle stage having
`
`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 succeeding stage.
`
`35
`
`40
`
`SUMMARY OF INVENTION
`
`45
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`A multi-stage network comprising (2xlog N)-1 stages is
`operated in strictly nonblocking manner for unicast includes
`an input stage having
`
`N
`d
`
`switches with each of them having d inlet links and 2xd
`outgoing links connecting to second stage Switches, an output
`stage having
`
`N
`d
`
`50
`
`55
`
`60
`
`switches with each of them having d outlet links and 2xd
`incoming links connecting from Switches in the penultimate
`stage. The network also has (2xlog N)-3 middle stages with
`each middle stage having
`
`65
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical
`multi-stage network V(N.d.S) having inverse Benes connec
`tion topology of five stages with N=8, d=2 and S-2 with
`exemplary multicast connections, strictly nonblocking net
`work for unicast connections and rearrangeably nonblocking
`network for arbitrary fan-out multicast connections, in accor
`dance with the invention.
`FIG.1B is a diagram 100B of a general symmetrical multi
`stage network V(N.d.2) with (2xlog N)-1 stages strictly
`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
`multi-stage network V(N.N.,d2) having inverse Benes con
`nection topology of five stages with N=8, N2=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.
`FIG. 1D is a diagram 100D of a general asymmetrical
`multi-stage network V(N.N.,d2) with NapN and with
`
`Page 32 of 64
`
`
`
`5
`(2xlog N)-1 stages strictly nonblocking network for unicast
`connections and rearrangeably nonblocking network for arbi
`trary fan-out multicast connections in accordance with the
`invention.
`FIG. 1E is a diagram 100E of an exemplary asymmetrical
`multi-stage network V(N.N.,d2) having inverse Benes con
`nection topology of five stages with N=8, N.pn=24.
`where p=3, and d=2 with exemplary multicast connections,
`strictly nonblocking network for unicast connections and
`rearrangeably nonblocking network for arbitrary fan-out
`multicast connections, in accordance with the invention.
`FIG. 1F is a diagram 100F of a general asymmetrical
`multi-stage network V(N.N.d.2) with N=p'N and with
`(2xlog N)-1 stages strictly nonblocking network for unicast
`connections and rearrangeably nonblocking network for arbi
`trary fan-out multicast connections in accordance with the
`invention.
`FIG.1A1 is a diagram 100A1 of an exemplary symmetrical
`multi-stage network V(N.d.2) having Omega connection
`topology of five stages with N=8, d=2 and S-2 with exem
`plary multicast connections, strictly nonblocking network for
`unicast connections and rearrangeably nonblocking network
`for arbitrary fan-out multicast connections, in accordance
`with the invention.
`FIG. 1C1 is a diagram 100C1 of an exemplary asymmetri
`cal multi-stage network V(N.N.d.2) having Omega connec
`tion topology of five stages with N=8, N.pN=24 where
`p=3, and d-2 with exemplary multicast connections, strictly
`nonblocking network for unicast connections and rearrange
`ably nonblocking networkfor arbitrary fan-out multicast con
`nections, in accordance with the invention.
`FIG. 1E1 is a diagram 100E1 of an exemplary asymmetri
`cal multi-stage network V(N.N.d.2) having Omega connec
`tion topology of five stages with N=8, N-pn=24, where
`p=3, and d-2 with exemplary multicast connections, strictly
`nonblocking network for unicast connections and rearrange
`ably nonblocking networkfor arbitrary fan-out multicast con
`nections, in accordance with the invention.
`FIG. 1A2 is a diagram 100A2 of an exemplary symmetrical
`multi-stage network V(N.d.2) having nearest neighbor con
`nection topology of five stages with N=8, d=2 and S-2 with
`exemplary multicast connections, strictly nonblocking net
`work for unicast connections and rearrangeably nonblocking
`network for arbitrary fan-out multicast connections, in accor
`dance with the invention.
`FIG. 1C2 is a diagram 100C2 of an exemplary asymmetri
`cal multi-stage network V(N.N.d.2) having nearest neigh
`bor connection topology of five stages with N=8,
`N.pN=24 where p=3, and d=2 with exemplary multicast
`connections, strictly nonblocking network for unicast con
`nections and rearrangeably nonblocking network for arbi
`trary fan-out multicast connections, in accordance with the
`invention.
`FIG. 1E2 is a diagram 100E2 of an exemplary asymmetri
`cal multi-stage network V(N.N.d.2) having nearest neigh
`bor connection topology of five stages with N=8,
`Np 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
`trary fan-out multicast connections, in accordance with the
`invention.
`FIG. 2A is a diagram 200A of an exemplary symmetrical
`multi-stage network V(N.d3) having inverse Benes connec
`tion topology of five stages with N=8, d=2 and s=3 with
`exemplary multicast connections strictly nonblocking net
`work for arbitrary fan-out multicast connections, in accor
`dance with the invention.
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 8,270,400 B2
`
`10
`
`15
`
`6
`FIG. 2B1 & FIG. 2B2 is a diagram 200B of a general
`symmetrical multi-stage network V(N.d.3) with (2xlog
`N)-1 stages strictly nonblocking network for arbitrary fan
`out multicast connections in accordance with the invention.
`FIG. 2C is a diagram 200C of an exemplary asymmetrical
`multi-stage network V(N.N.d3) having inverse Benes con
`nection topology of five stages with N=8, N2=p'N=24
`where p=3, and d=2 with exemplary multicast connections
`strictly nonblocking network for arbitrary fan-out multicast
`connections, in accordance with the invention.
`FIG. 2D1 & FIG. 2D2 is a diagram 200D of a general
`asymmetrical multi-stage network V(N.N.d,3) with
`N.pN and with (2xlog N)-1 stages strictly nonblocking
`network for arbitrary fan-out multicast connections in accor
`dance with the invention.
`FIG. 2E is a diagram 200E of an exemplary asymmetrical
`multi-stage network V(N.N.d3) having inverse Benes con
`nection topology of five stages with N=8, Npn=24.
`where p=3, and d=2 with exemplary multicast connections
`strictly nonblocking network for arbitrary fan-out multicast
`connections, in accordance with the invention.
`FIG. 2F1 & FIG. 2F2 is a diagram 200F of a general
`asymmetrical multi-stage network V(N.N.d3) with
`Np N and with (2xlog N)-1 stages strictly nonblocking
`network for arbitrary fan-out multicast connections in accor
`dance with the invention.
`FIG. 2A1 is a diagram 200A1 of an exemplary symmetrical
`multi-stage network V(N.d3) having Omega connection
`topology of five stages with N=8, d=2 and S-3 with exem
`plary multicast connections, strictly nonblocking network for
`arbitrary fan-out multicast connections, in accordance with
`the invention.
`FIG. 2C1 is a diagram 200C1 of an exemplary asymmetri
`cal multi-stage network V(N.N.d3) having Omega connec
`tion topology of five stages with N=8, N.pN=24 where
`p=3, and d=2 with exemplary multicast connections, strictly
`nonblocking network for arbitrary fan-out multicast connec
`tions, in accordance with the invention.
`FIG.2E1 is a diagram 200E1 of an exemplary asymmetri
`cal multi-stage network V(N.N.d.3) having Omega connec
`tion topology of five stages with N=8, N-pn=24, where
`p=3, and d=2 with exemplary multicast connections, strictly
`nonblocking network for arbitrary fan-out multicast connec
`tions, in accordance with the invention.
`FIG. 2A2 is a diagram 200A2 of an exemplary symmetrical
`multi-stage network V(N.d3) having nearest neighbor con
`nection topology of five stages with N=8, d=2 and S-3 with
`exemplary multicast connections, strictly nonblocking net
`work for arbitrary fan-out multicast connections, in accor
`dance with the invention.
`FIG. 2C2 is a diagram 200C2 of an exemplary asymmetri
`cal multi-stage network V(N.N.d3) having nearest neigh
`bor connection topology of five stages with N=8,
`N.pN=24 where p=3, and d=2 with exemplary multicast
`connections, strictly nonblocking network for arbitrary fan
`out multicast connections, in accordance with the invention.
`FIG.2E2 is a diagram 200E2 of an exemplary asymmetri
`cal multi-stage network V(N.N.d3) having nearest neigh
`bor connection topology of five stages with N=8,
`Np N=24, where p=3, and d=2 with exemplary multicast
`connections, strictly nonblocking network for arbitrary fan
`out multicast 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 con
`nections in all the networks disclosed in this invention.
`FIG. 4A1 is a diagram 400A1 of an exemplary prior art
`implementation of a two by two switch; FIG. 4A2 is a dia
`
`Page 33 of 64
`
`
`
`US 8,270,400 B2
`
`7
`gram 400A2 for programmable integrated circuit prior art
`implementation of the diagram 400A1 of FIG. 4A1: FIG. 4A3
`is a diagram 400A3 for one-time programmable integrated
`circuit prior art implementation of the diagram 400A1 of FIG.
`4A1: FIG. 4A4 is a diagram 400A4 for integrated circuit
`placement and route implementation of the diagram 400A1 of
`FIG. 4A1.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`8
`S) and generalized folded multi-link multi-stage networks
`V(N.N.d.s.) with numerous connection topologies
`and the scheduling methods are described in detail in the PCT
`Application Serial No. PCT/US08/64604 that is incorporated
`by reference above.
`3) Strictly and rearrangeably nonblocking for arbitrary
`fan-out multicast and unicast for generalized multi-link but
`terfly fat tree networks V. (N.N.d.s.) with numerous
`connection topologies and the scheduling methods are
`described in detail in the PCT Application Serial No. PCT/
`US08/64603 that is incorporated by reference above.
`4) Strictly and rearrangeably nonblocking for arbitrary
`fan-out multicast and unicast for generalized folded multi
`stage networks V(N.N.d.s.) with numerous connection
`topologies and the scheduling methods are described in detail
`in the PCT Application Serial No. PCT/US08/64604 that is
`incorporated by reference above.
`5) Strictly nonblocking for arbitrary fan-out multicast and
`unicast for generalized multi-link multi-stage networks
`V(N.N.d.s.) and generalized folded multi-link multi
`stage networks Van (N.N.d.s.) with numerous connec
`tion topologies and the scheduling methods are described in
`detail in the PCT Application Serial No. PCT/US08/64604
`that is incorporated by reference above.
`6)VLSI layouts of numerous types of multi-stage networks
`are described in the PCT Application Serial No. PCT/US08/
`64605 entitled VLSI LAYOUTS OF FULLY CON
`NECTED NETWORKS that is incorporated by reference
`above.
`7)VLSI layouts of numerous types of multi-stage networks
`with locality exploitation are described in PCT Application
`Serial No. PCTFUSO8/821.71 entitled VLSI LAYOUTS OF
`FULLY CONNECTED GENERALIZED AND PYRAMID
`NETWORKS WITH LOCALITY EXPLOITATION” by
`Venkat Konda assigned to the same assignee as the current
`application, filed Nov. 2, 2008.
`8) VLSI layouts of numerous types of multistage pyramid
`networks are described in PCT Application Serial No. PCT/
`USO8/821.71 entitled VLSI LAYOUTS OF FULLY CON
`NECTED GENERALIZED AND PYRAMID NETWORKS
`WITH LOCALITY EXPLOITATION” by Venkat Konda
`assigned to the same assignee as the current application, filed
`Nov. 2, 2008.
`Symmetric RNB Embodiments:
`Referring to FIG. 1A, in one embodiment, an exemplary
`symmetrical multi-stage network 100A with five stages of
`thirty two Switches for satisfying communication requests,
`Such as setting up a telephone call or a data call, or a connec
`tion between configurable logic blocks, between an input
`stage 110 and output stage 120 via middle stages 130, 140,
`and 150 is shown where input stage 110 consists of four, two
`by four switches IS1-IS