USOO827 0400B2
`
`(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
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 1 of 29
`Sheet 1 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`L10
`
`210
`
`£10
`
`v10
`
`$10
`
`910
`
`L10
`
`810
`
` ZomSAeheeaanLEMWye
`
`Wi
`
`Page 2 of 64
`
`Page 2 of 64
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 2 of 29
`Sheet 2 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
` IVIOW
`
`
`
`
`
`
`
`IVI "OIH
`
`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
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 4 of 29
`Sheet 4 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`
`
`(Te-N*80TXZ7)SW
`
`807XT)SH
`
`t.,
`
`(P-N)10
`
`(N10
`
`(pz)10
`
`
`
`(PXP'T—N’SOTXT)TNN__
`
`p(P—N)XTT—N’SETXDI
`
`
`
`
`
`
`
`L10
`
`
`(1+P)10®wtress¢(PIN'LISINL+p)1I
`VIP,=x?8oy)SNPNE-(p10i(Pp)
`
`(PXTT—NBOTTA
`
`
`
`(NXTT+A307)TWN
`
`
`
`1 \
`
`|
`
`a}Lo\—~!og,|PHNHOTeTeOT+OL(ZN?801).01-+0E1~~0eLOLE
`
`
`
`JLalOld
`
`goor
`
`
`
`Page 5 of 64
`
`Page 5 of 64
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 5 Of 29
`Sheet 5 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`% As
`
`
`
`
`
`VL
`
`
`
`xxoesl¢Xx)esl\WfLSI
`
`(DAW
`
`“OLL
`
`ZI
`
`Page 6 of 64
`
`(e‘e)SW
`(9L‘eWNL,
`(g'zswNOF2
`
`(‘LSI
`
`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
`
`

`

`an4os,ort“Og
`
`
`
`
`
`
`
`Z5001.COlDIL
`
` (‘ew(PSN
`.ne’Aezw(Z'bSw
`
` EWNzgn)IMoy
`(9g7:
`NIVNIA
`iVI
`
`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 7 Of 29
`Sheet 7 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`
`
`
`
`7'Z)1
`
`RSWA/C?CW!—??????????????????
`
`Tl
`
`‘ll
`
`Il
`
`vl
`
`‘ll
`
`91l
`
`ZI
`
`81
`
`Page 8 of 64
`
`Page 8 of 64
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 8 of 29
`Sheet 8 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`(P.d)10q(p)71
`
`(PXEXTC—N'BOTXTITN
`
`
`
`
`
`(L+P,4)10L+p)1I
`
`((P-N).0)10
`
`
`
`(N.4)10<—
`
`+(P/N)JSO
`
`P(PXEXPT-N
`SOTXTYIN
`
`_
`
`(P=N)XEXTT—NOSOUXTTIN
`
`
`
`(NXTL+NNSOUYIN (NXOxTT—N?SOTXTIN
`«— (
`
`¢\(PatLW
`
`(P-N)«2'LW
`
`(p.4.2)10
`
`pe)
`
`|TO
`L10
`
`~aa| 2o
`
`e8
`J]
`
`xA ==
`
`C—N"8OTXZ)SWONopsnst”)a(9
`‘:,Ww;Lhe:Ty
`(p'Z7‘a;fscseesesee-,(FLSA|:
`a“‘
`
`ii
`
`i i
`
`(1-p)},
`
`
`(TE-N’S0TXZ)SH(I=N80NSW(L
`bead+—Tr.
`
`aoor
`
`VeamLWeyWee~~}VeaLoany~_}Oz(P-N’8OTeZ)
`
`
`eOL+0EL (Z—N?SOT)2OL+0ETO€LOLLJql‘ol
`
`
`
`
`
`
`
`
`
`Page 9 of 64
`
`Page 9 of 64
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 9 Of 29
`Sheet 9 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`810Q'dsw|ASW(gzswLMSW(9'soe
`
`noeOfcomToSNoan|
`(eveninpentLNN\Aheber
`(geswNOPE"—iziswNY(‘SW
`YfronRSvonRomWG”ES
`
`feNT\l
`
` ALOW
`
`CHI "OIH
`
`
`
`StlZt
`
`
`
`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
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 12 of 29
`Sheet 12 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`
`
`(NXTT—N°SOTxTIN4sommmmmmersmmm04.2"LN\
`
`(NXTT+ASOTYIN
`
`roremrenemegd|pstaenanones:(P/NZ'LSW;:peti(P-Nz‘z)
`
`
`(PXTT—N'8OTKEINfrSOTXTIS
`
`(P=NYXTT~N’SPTXOIN
`
`
`(e-N'807;xT)SW
`
`
`
`BOTXTSN
`
`\(\!\~Jetye!Lee
`
`
`
`og,PONFOTaDeOIFOET (Z-N?FOP)eOL+OELOSLOLJAL‘OM
`
`
`
`(PxP'S—N’SOTXO)INS
`
`WoesVYLl
`
`(p)10Npd)
`
`(L+p)7wR1+P,4)
`
`
`
`(PZ)10p.d,2)11
`
`
`
`
`
`(2-N)10«<—P-N)Q)11
`
`(N) TO <–
`
`(Z+P/N'LSI
`
`(N-9)11
`
`4001
`
`
`
`
`
`
`
`
`
`
`
`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
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 15 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`c10
`
`€10
`
`v10
`
`S10
`
`910
`
`210
`
`810
`
`L10
`
`
`o
`s
`
`
`
`LSOLX
`
`(rp
`
`
`
`
`
`
`
`
`
`
`
`ZWZ º?IH
`
`
`
`OT
`
`(ce
`(L‘Z)SW
`
`_Or.Oh“Ost/eveOA
`
`(bw(Z‘S)SWAeSait(z‘Z)Sw
`oo.rey.
`SyJj(eeswSEM(zion
`|02EIN(OL‘S)SWLCASLSIW(OL'Z)SW
`
`
`(zeswmMEE)(zyz)sw
`(6'E(6'Z)SW
`sw(SL€)10
`‘(p2"LW0z'Z)1N‘Asucrw(0/'L)SW_/
`
`(8h(6Low
`fe(2hWS\CECSW
`pez)
`——/}4,(Coa
`‘oeYN/\AK(ZL‘LI/LKS
`HINYcSl
`
`(r'Z)SW
`
`
`
`
`
`(PrLISW
`
`
`
`XK
`
`Ll
`
`ll
`
`‘ll
`
`Vl
`
`ll
`
`11
`
`Zl
`
`81
`
`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
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 17 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`(PXTT—-N*SOTXT)IN
`
`oN
`
`
`
`(cT-N°SCTXZ)IW
`
`(P‘T-N’S80TXT)IN
`
`
`
`
`
`(P-N‘T-N’S8OTXTYIN
`
`_
`
`(N‘T-N°S0TXZ)IN\
`
`—‘¢-N’S0TX7)SWorgOS
`
`
`
`
`TI-N20T)SW
`
`
`
`
`
`(I+P'T-N’80TXDINCeNPBOTXOSW
`
`(p—N°80727)xOT+081Zcg00z
`(T€-N’S0TXZ)SW\yo
`eneneee:Loteecececnee#(SW|:(PW
`(pz'z©)‘ooPesrerreors|(ZLISIN|!~e_((1+p)'2#——>PLN
`
`(T-N’80T)xOL+0€1Oct
`(PNET\\(PezLN‘_~a"
`—Wr—
`(i-NsonswLaD)
`yonLE—~__)enn
`cdcOl
`
`
`
`
`
`
`
`
`
`(pz‘‘j
`
`
`
`Page 18 of 64
`
`Page 18 of 64
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 18 Of 29
`Sheet 18 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`cSO
`
`€SO
`
`vSO
`
`
`
`
`
`
`
`~~OFk
`
`Oyare)Kl
`
`COZ "?INH
`
`
`
`07||0810 || ||
`
`Page 19 of 64
`
`
`
`Cll
`
`bl
`
`‘ll
`
`val
`
`‘ll
`
`911
`
`L111
`
`81
`
`Page 19 of 64
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 19 Of 29
`Sheet 19 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`
`
`LSO
`
`€SO
`
`vSO
`
`i
`)
`Mb
`\)
`
`/|ET
`
`|=.i
`i
`
`32°C)TJA àý
`
`TICIIT-
`
`Vy
`
`
`“wensQO
`(peLWWo
`ih(XWri\WKLPXKLW1s|
`\\NWesrn
`AGesl
`
`
`
`
`
`(6LISI
`
`SS
`
`Sl
`
`yl
`
`l
`
`Ll
`
`Tl
`TI
`
`Il
`TI
`
`vl
`
`Tl
`TI
`
`gl
`
`Page 20 of 64
`
`
`
`
`
`
`
`|×I OZ. "?INH
`
`
`lcOl
`
`_Orl
`
`(L‘Z)SW
`
`(2‘z)SW
`
`
`
`HY)
`fa:(or‘r)1N‘v"I(ZL‘S)SW
`
`pGresnFey(LL‘Z)SWPe}*(oRrdsw.BAAR(olSn
`PEween6m(ezsw*2
`
`Page 20 of 64
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 20 Of 29
`Sheet 20 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`29002
`
`
`
`LSO
`
`zSO
`
`rSO7)#4
`
`(p'p)1N
`coHf
`
`“OZ.9gaae“OstOLE/707‘OM
`eSOll
`
`
`(s‘S)SW011
`
`Gasw&@2WCUYswcen
`
`
`
`
`
`
`
`
`
`Vv
`
`“ny
`
`i
`
`I
`
`I
`
`ral
`
`A
`
`811
`
`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
`
`

`

`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 22 of 29
`
`US 8,270,400 B2
`
`
`
`((P-N)xd‘Z-N’S80TXZ)IW
`
`(Nxd‘7-N’80TXZYIN
`
`B07TxT7WeN807XT)SW
`—‘c—a?
`
`
`
`
`(+Px@'7-N'30TXTINENPROTXOSI
`(soySiN‘NEP
`
`
`
`(pxdx77Z—N°807XZ)IN
`paoo™~
`a(pez
`\\(P.2'))W—\
`
`
`
`(Px4d‘T-N°S0TXZYIN
`
`oo.
`
`(i7-N’807XZYIW
`
`~~
`
`
`
`zc00zCd¢Dl
`
`
`
`(y-N'807x7)xOL+0EL(ZT—N’80T)xO1+0€IOe
`P\TyayLay“em
`
`
`
`(Te-N’80TXZSW7
`
`Page 23 of 64
`
`
`
`
`
`Page 23 of 64
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2012
`Sep. 18, 2012
`
`Sheet 23 Of 29
`Sheet 23 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`LO
`
`210+—
`
`
`2
`
`
`
`810avonAWS6b
`910YAK6sSLIKi,SES10€SOAANAWAYeb
`E10+—‘.,ynOL
`
`
`
`—_
`yy10<—|LL“e.saa
`\VNA210(\(YY41)
` Oeos}|~~/A?Ol
`
`¥SOrnWKH
`
`AWW9Uy
`
` Ny\\NowSX7APS(OL'LISWNYrs)=Ey0211
`
`0€L
`
`~~
`
`~~Olh
`
`Page 24 of 64
`
`
`
`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
`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 25 of 29
`
`US 8,270,400 B2
`US 8,270,400 B2
`
`
`
`~x4_—=—<—<—<—<<$_(/AhAeoee)ee
`e10+<——_iySamevenMSES
`S10“zm(2'2)SI
`
`Z10+—aNA”.\‘Ni
`L10HN
`;WEnor
` orloctOre
`
`
`
`CH¢e“OIA
`
`ZICHZ * OIDH
`
`
`
`
`
`
`
`
`
`Page 26 of 64
`
`No.
`
`és\\F~ir4cianANGNi
`cep(LLLSW
`
`(3LW
`
`,I)‘X)Vi
`
`eeWy
`
`
`
`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
`
`

`

`U.S. Patent
`
`Sep. 18, 2012
`
`Sheet 27 of 29
`
`US 8,270,400 B2
`
`
`(I+P‘T-N'80TXZ)IW7t~
`
`‘3eea(P'T-N’SOTXTIW||tesesceeees(p.d‘LIW
`
`_a(PXTT—N°8OTXTYIN\ecceceeeee
`
`
`|_'Ab+Pxd‘LW
`(N‘°T—N°380TXZ)IN\ (P-
`
`
`
`N‘T-N°80TXTYIN
`
`tcP80M(veN'807XT)SW
`
`
`
`(N.d“)IW
`
`
`
`(JE-—NN’SOTXT)SW
`
`
`
`
`
`(Pdg'LW
`
`((T—N?80TXTIN
`
`\_.—(TE-N'S0TXZ)SW-
`
`
`
`24002TAZ“OIA
`
`
`
`
`(p—-N’807x7)xOL+0€T(T-N’S8OT)xOL+0€1~OeL
`aeayLJ(LLIN
`
`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.S. Patent
`
`Sep. 18, 2012
`
`Sheet 29 of 29
`
`US 8,270,400 B2
`
`eVv00r
`
`(z‘z)dod/(.‘aoa
`
`rvoovGay10114)
`
`CVFOM
`
`210
`
`bVP‘Ola
`
`VrOld
`
`bl
`
`él
`
`LVO0r
`
`J(z'do(ao
`
`210«+110
`
`IVP‘Old
`
`(41V1011d)
`
`Kl
`
`ell
`
`(ZL)AHA
`
`c1O=+10
`
`
`
`eVr‘Old
`
`(AV1011d)
`
`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 Applica