`
`
`
`
`
`VENKAT KONDA
`6278 Grand Oak Way
`San Jose, California 95135
`Telephone: (408) 472-3273
`Email: vkonda@gmail.com
`
`Plaintiff Pro se
`
`
`
`19CV345846
`Santa Clara – Civil
`
`Electronically Filed
`by Superior Court of CA,
`County of Santa Clara,
`on 3/22/2021 11:34 PM
`Reviewed By: F. Miller
`Case #19CV345846
`Envelope: 6087286
`
`SUPERIOR COURT OF CALIFORNIA - COUNTY OF SANTA CLARA
`UNLIMITED JURISDICTION
`
`
`
`VENKAT KONDA, Ph.D., an individual,
`
`Plaintiff,
`
`
`
`
`
`v.
`
`DEJAN MARKOVIC, Ph.D., an individual;
`CHENG C. WANG, Ph.D., an individual;
`FLEX LOGIX TECHNOLOGIES, INC., a
`Delaware Corporation; THE REGENTS OF
`THE UNIVERSITY OF CALIFORNIA;
`GEOFFREY TATE, an individual; PIERRE
`LAMOND, an individual; PETER HEBERT,
`an individual; LESLIE M. LACKMAN, Ph.D.,
`an individual; and DOES 1-20, inclusive,
`
` CASE NO. 19CV345846
`
`EXHIBITS A - E IN DECLARATION OF
`VIPIN CHAUDHARY, Ph.D. IN SUPPORT
`OF PLAINTIFF’S FOURTH AMENDED
`COMPLAINT
`
`Department: 2
`Before: Honorable Drew C. Takaichi
`
`Date Complaint Filed: April 3, 2019
`Trial Date: None
`
`Defendants.
`
`
`
`
`
`
`
`
`
`
`Vipin Chaudhary Ph.D. Declaration
`
`1
`
`Case No: 19CV345846
`
`
`
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`27
`
`28
`
`
`
`Page 1 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 2 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`EXHIBIT A
`
`Page 2 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 3 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY(PCT)
`
`(19) World Intellectual Property Organization { A
`
`International Bureau
`
`fe) CANIM UMATAA
`
`
`
`(43) International Publication Date
`12 September 2008 (12.09.2008)
`
`(51) International Patent Classification:
`H04Q 3/00 (2006.01)
`
`(21) International Application Number:
`PCT/US2008/056064
`
`(22) International Filing Date:
`
`6 March 2008 (06.03.2008)
`
`(25) Filing Language:
`
`(26) Publication Language:
`
`English
`
`English
`
`(84)
`
`(30) Priority Data:
`60/905,526
`60/940,383
`
`6 March 2007 (06.03.2007)
`25 May 2007 (25.05.2007)
`
`US
`US
`
`(71) Applicant and
`(72) Inventor: KONDA, Venkat [US/US]; 6278, Grand Oak
`
`(81) Designated States (unless otherwise indicated, for every
`kind of national protection available): AE, AG, AL, AM,
`
`Published:
`with international search report
`
`(54) Title: FULLY CONNECTED GENERALIZED MULTI-STAGE NETWORKS
`
`(10) International Publication Number
`WO 2008/109756 Al
`
`AO,AT, AU, AZ, BA, BB, BG, BH, BR, BW, BY, BZ, CA,
`CH, CN, CO, CR, CU, CZ, DE, DK, DM, DO, DZ, EC, EE,
`EG, ES, FI, GB, GD, GE, GH, GM, GT, HN, HR, HU, ID,
`IL, IN, IS, JP, KE, KG, KM, KN, KP, KR, KZ, LA, LC,
`LK, LR, LS, LT, LU, LY, MA, MD, ME, MG, MK, MN,
`MW, Mx, MY, MZ, NA, NG, NI, NO, NZ, OM,PG, PH,
`PL, PT, RO, RS, RU, SC, SD, SE, SG, SK, SL, SM, SV,
`SY, TJ, TM, TN, TR, TT, TZ, UA, UG, US, UZ, VC, VN,
`ZA, ZM, ZW.
`
`Designated States (unless otherwise indicated, for every
`kind of regional protection available): ARIPO (BW, GH,
`GM,KE, LS, MW, MZ, NA, SD, SL, SZ, TZ, UG, ZM,
`ZW), Eurasian (AM, AZ, BY, KG, KZ, MD, RU,TJ, TM),
`European (AT, BE, BG, CH, CY, CZ, DE, DK,EE,ES, FI,
`FR, GB, GR, HR, HU,IE,IS, IT, LT, LU, LV, MC, MT, NL,
`NO,PL, PT, RO, SE, SI, SK, TR), OAPI (BF, BJ, CF, CG,
`CI, CM, GA, GN, GQ, GW, ML, MR, NE, SN, TD, TG).
`
`FIG. 1B
`130+10* (Log,N ~2)
`oh)
`
`
`
`WO2008/109756A.IMTTTINTIMTMINNAAITATA Way, San Jose, CA 95135 (US).
`
`100B
`
`120
`-
`*(2*
`1s0UorarLegaN—HO\
`MS(2x Log, N -3,1)
`
`Olt
`
`(57) Abstract: A multi-stage network
`comprising (2x log, N)
`-
`I 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 2x d outgoing links connecting
`to second stage switches, an output
`stage having N / d switches with each
`of them having d outlet links and 2
`xd incoming links connecting from
`switches
`in the penultimate stage.
`The network also has (2x logy N)
`- 3 middle stages with each middle
`stage having 2 x N / d switches, and
`each switch in the middle stage has
`d incoming links connecting from the
`switches in its immediate preceding
`stage, and d outgoing links connecting
`to the
`switches
`in its
`immediate
`
`L(2.x Log,N -2,1)
`
`
`
`OL(d)
`
`2x Log,N —2,2xd
`
`Be Olde}
`
`OL(2d)
`
`L(2x Log,N -2,4xd)
`ML(2xLég,N ~2,2x(N ~d))
`
`ML(1,24(N-€))
`
`IS(N/d)
`
`
`
`
`
`
`
`
`Also the same
`succeeding stage.
`multi-stage network is operated in
`rearrangeably nonblocking mannerfor
`arbitrary fan-out multicast and each
`multicast connection is set up by use
`of at most two outgoing links from the input stage switch. A multi-stage network comprising (2x log, N) - 1 stages is operated in
`strictly nonblocking mannerfor multicast includes an input stage having N / d switches with each of them havingdinlet links and 3
`x d outgoing links connecting to second stage switches, an output stage having N / d switches with each of them having d outlet
`links and 3 x d incoming links connecting from switches in the penultimate stage. The network also has (2x log, N) - 3 middle
`stages with each middle stage having 3 x N / d switches, and each switch in the middle stage has d incoming links connecting from
`the switches in its immediate preceding stage, and d outgoing links connecting to the switches in its immediate succeeding stage.
`
`ME(Log,N +1,2xN)
`
`Page 3 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 4 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`FULLY CONNECTED GENERALIZED MULTI-STAGE NETWORKS
`
`Venkat Konda
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`referencein its entirety the U.S. Provisional Patent Application Serial No. 60/905,526
`
`entitled "LARGE SCALE CROSSPOINT REDUCTION WITH NONBLOCKING
`
`UNICAST & MULTICAST IN ARBITRARILY LARGE MULTISTAGE
`
`10
`
`NETWORKS"by Venkat Kondaassigned to the same assignee as the current application,
`
`filed March 6, 2007.
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`referencein its entirety the U.S. Provisional Patent Application Serial No. 60/940, 383
`
`entitled "FULLY CONNECTED GENERALIZED MULTI-STAGE NETWORKS"by
`
`15
`
`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 U.S.
`
`Provisional Patent Application Serial No. 60/940, 387 entitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE NETWORKS"by Venkat Kondaassigned
`
`20
`
`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 U.S.
`
`Provisional Patent Application Serial No. 60/940, 389 entitled "FULLY CONNECTED
`
`GENERALIZED REARRANGEABLY NONBLOCKING MULTI-LINK MULTI-
`
`STAGE NETWORKS"by Venkat Kondaassigned to the same assignee as the current
`
`25
`
`application, filed May 25, 2007.
`
`Page 4 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 5 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`2
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Serial No. 60/940, 390 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS"by Venkat
`
`Kondaassigned to the same assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Serial No. 60/940, 391 entitled "FULLY CONNECTED
`
`GENERALIZED FOLDED MULTI-STAGE NETWORKS"by Venkat Kondaassigned
`
`to the same assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`10
`
`Provisional Patent Application Serial No. 60/940, 392 entitled "FULLY CONNECTED
`
`GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULTI-STAGE
`
`NETWORKS"by Venkat Kondaassigned to the same assignee as the current application,
`
`filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`15
`
`Provisional Patent Application Serial No. 60/940, 394 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED 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 U.S.
`
`Provisional Patent Application Serial No. 60/984, 724 entitled "VLSI LAYOUTS OF
`
`20
`
`FULLY CONNECTED NETWORKSWITH LOCALITY EXPLOITATION"by Venkat
`
`Kondaassigned to the sameassignee as the current application, filed November 2, 2007.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Serial No. 61/018, 494 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED AND PYRAMID NETWORKS"by Venkat
`
`25
`
`Kondaassigned to the same assignee as the current application, filed January 1, 2008.
`
`Page 5 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 6 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`BACKGROUNDOF INVENTION
`
`Clos switching network, Benes switching network, and Cantor switching network
`
`are a network of switches configured as a multi-stage network so that fewer switching
`
`points are necessary to implement connections betweenits inlet links (also called
`
`"inputs") and outlet links (also called "outputs" ) than would be required by a single stage
`
`(e.g. crossbar) switch having the same numberof inputs and outputs. Clos and Benes
`
`networks are very popularly used in digital crossconnects, switch fabrics and parallel
`
`computer systems. However Clos and Benes networks may block some of the connection
`
`requests.
`
`10
`
`There are generally three types of nonblocking networks: strictly nonblocking;
`
`wide sense nonblocking; and rearrangeably 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 network's ability to rearrange prior
`
`15
`
`connections as new incomingcalls are received. In strictly nonblocking network, for any
`
`connection request from an inlet link to someset of outlet links, it is always possible to
`
`provide a connection path through the networkto satisfy the request without disturbing
`
`other existing connections, and if more than one such path is available, any path can be
`
`selected without being concerned aboutrealization of future potential connection
`
`20
`
`requests. In wide-sense nonblocking networks, it is also always possible to provide a
`
`connection path through the networkto satisfy the request without disturbing other
`
`existing connections, but in this case the path used to satisfy the connection request must
`
`be carefully selected so as to maintain the nonblocking connecting capability for future
`
`potential connection requests.
`
`25
`
`Butterfly Networks, Banyan Networks, Batcher-Banyan Networks, Baseline
`
`Networks, Delta Networks, Omega Networks and Flip networks have been widely
`
`studied particularly for self routing packet switching applications. Also Benes Networks
`
`with radix of two have been widely studied and it is known that Benes Networksof radix
`
`two are shownto be built with back to back baseline networks which are rearrangeably
`
`30
`
`nonblocking for unicast connections.
`
`Page 6 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 7 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`4
`
`U.S. Patent 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 numberof well known nonblocking multi-stage switching network
`
`designs in the backgroundsection at column 1, line 22 to column3, 59. Anarticle by Y.
`
`Yang, and G.M., Massonentitled, “Non-blocking Broadcast Switching Networks” IEEE
`
`Transactions on Computers, Vol. 40, No. 9, September 1991 that is incorporated by
`
`reference as backgroundindicates that if the number of switches in the middle stage, m,
`of a three-stage networksatisfies the relation m > min((n —I(xtr'” )) where
`
`1<x<min(#—-1,r), the resulting network is nonblocking for multicast assignments. In
`
`10
`
`the relation, ris the number of switches in the input stage, and n is the numberofinlet
`
`links in each input switch.
`
`U.S. Patent 6,885,669 entitled “Rearrangeably Nonblocking Multicast Multi-stage
`
`Networks” by Konda showedthat three-stage Clos network is rearrangeably nonblocking
`
`for arbitrary fan-out multicast connections when m22xn. And U.S. Patent 6,868,084
`
`15
`
`entitled “Strictly Nonblocking Multicast Multi-stage Networks” by Konda showedthat
`
`three-stage Clos networkis strictly nonblocking for arbitrary fan-out multicast
`
`connections when m>3xn-—1.
`
`In general multi-stage networks for stages of more than three and radix of more
`
`than two are not well studied. An article by Charles Clos entitled “A Study of Non-
`
`20
`
`Blocking Switching Networks” The Bell Systems Technical Journal, Volume XXXII,
`
`Jan. 1953, No.1, pp. 406-424 showed a way of constructing large multi-stage networks by
`
`recursive substitution with a crosspoint complexity of d* x N x(log, N)**forstrictly
`
`nonblocking unicast network. Similarly U.S. Patent 6,885,669 entitled “Rearrangeably
`
`Nonblocking Multicast Multi-stage Networks” by Konda showed a wayof constructing
`
`25
`
`large multi-stage networksby recursive substitution for rearrangeably nonblocking
`
`multicast network. Anarticle by D. G. Cantor entitled “On Non-Blocking Switching
`
`Networks” 1: pp. 367-377, 1972 by John Wiley and Sons, Inc., showed a way of
`
`constructing large multi-stage networks with a crosspoint complexity of
`
`d* xNx(log, N)” forstrictly nonblocking unicast, (by using log, N number of Benes
`
`30
`
`Networks for d = 2) and without counting the crosspoints in multiplexers and
`
`Page 7 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 8 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`5
`
`demultiplexers. Jonathan Turnerstudied 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 networkof size N=256.
`
`The crosspoint complexity of all these networksis prohibitively large to
`
`implement the interconnect for multicast connections particularly in field programmable
`
`gate array (FPGA)devices, programmable logic devices (PLDs), field programmable
`
`interconnect Chips (FPICs), digital crossconnects, switch fabrics and parallel computer
`
`systems.
`
`10
`
`SUMMARYOF INVENTION
`
`A multi-stage network comprising (2x logaN )-1 stages is operatedinstrictly
`
`nonblocking mannerfor unicast includes an input stage having 7 switches with each of
`
`them having d inlet links and 2xdoutgoing links connecting to second stage switches,
`
`an output stage having 7 switches with each of them having d outlet links and 2xd
`
`_,
`
`;
`
`_
`
`N
`
`;
`
`15
`
`incoming links connecting from switches in the penultimate stage. The network also has
`
`(2xlog aN )-3 middle stages with each middle stage having
`
`
`2xN
`
`switches, and each
`
`switch in the middle stage has d incoming links connecting from the switchesin its
`
`immediate preceding stage, and d outgoing links connecting to the switchesin its
`
`immediate succeeding stage. Also the same multi-stage network is operated in
`
`20
`
`rearrangeably nonblocking mannerfor arbitrary fan-out multicast and each multicast
`
`connection is set up by use of at most two outgoing links from the input stage switch.
`
`A multi-stage network comprising (2x logaN )-1 stages is operatedinstrictly
`
`nonblocking mannerfor multicast includes an input stage having 7 switches with each
`
`of them having d inlet links and 3xd outgoing links connecting to second stage
`
`Page 8 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 9 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`switches, an output stage having = switches with each ofthem having d outlet links
`
`and 3xd incominglinks connecting from switches in the penultimate stage. The
`network also has (2x logaN)—3 middle stages with each middle stage having 3x N
`
`
`
`switches, and each switch in the middle stage has d incoming links connecting from the
`
`switchesin its immediate preceding stage, and d outgoing links connecting to the
`
`switchesin its immediate succeedingstage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi-stage network
`
`10
`
`V(N,d,s) having inverse Benes connection topology of five stages with N = 8, d = 2 and
`
`s=2 with exemplary multicast connections, strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections, in accordance with the invention.
`
`FIG. 1B is a diagram 100B of a general symmetrical multi-stage network
`V(N,d,2) with (2xlog aN )-1 stages
`strictly nonblocking network for unicast
`
`15
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections in accordance with the invention.
`
`FIG. 1C is a diagram 100C of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,2) having inverse Benes connection topologyoffive stages with N; = 8, N2
`
`20
`
`= 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,,d,2) with No = p* N; and with (2xlogaN )-1 stages strictly nonblocking
`
`25
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections in accordance with the invention.
`
`Page 9 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 10 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`7
`
`FIG. 1E is a diagram 100E of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,2) having inverse Benes connection topology of five stages with No = 8, Ni
`
`= p* No = 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* No and with (2xlogaN )-1 stages strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections in accordance with the invention.
`
`10
`
`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 exemplary multicast connections,
`
`strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections, in accordance with the invention.
`
`15
`
`FIG. 1C1 is a diagram 100C1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,2) having Omega connection topology of five stages with N; = 8, No = p*
`
`Ni = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`20
`
`FIG. 1E]1 is a diagram 100E1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,2) having Omega connection topology of five stages with No = 8, Ni = p*
`
`No = 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.
`
`25
`
`FIG. 1A2 is a diagram 100A2 of an exemplary symmetrical multi-stage network
`
`V(N,d,2) having nearest neighbor connection topology of five stages with N = 8, d = 2
`
`and s=2 with exemplary multicast connections, strictly nonblocking network for unicast
`
`Page 10 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 11 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`8
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections, in accordance with the invention.
`
`FIG. 1C2 is a diagram 100C2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,2) having nearest neighbor connection topology of five stages with N; = 8,
`
`No = 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. 1E2 is a diagram 100E2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,2) having nearest neighbor connection topology of five stages with N> = 8,
`
`10
`
`Ni = p* No= 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. 2A is a diagram 200A of an exemplary symmetrical multi-stage network
`
`V(N,d,3) having inverse Benes connection topology of five stages with N = 8, d = 2 and
`
`15
`
`s=3 with exemplary multicast connections strictly nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 2B1 & FIG. 2B2 is a diagram 200B of a general symmetrical multi-stage
`network V(N,d,3) with (2xlog aN )-1 stagesstrictly nonblocking network for arbitrary
`
`fan-out multicast connections in accordance with the invention.
`
`20
`
`FIG. 2C is a diagram 200C of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,3) having inverse Benes connection 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.
`
`25
`
`FIG. 2D1 & FIG. 2D2 is a diagram 200D of a general asymmetrical multi-stage
`network V(N,,N,,d,3) with No = p* N; and with (2xlog, N)-1 stages strictly
`
`Page 11 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 12 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`9
`
`nonblocking network for arbitrary fan-out multicast connections in accordance with the
`
`invention.
`
`FIG. 2E is a diagram 200E of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,3) having inverse Benes connection topology of five stages with Nz = 8, Ni
`
`= p* No = 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,,d,3) with N; = p* No and with (2xlog, N)-1 stages strictly
`
`10
`
`nonblocking network for arbitrary fan-out multicast connections in accordance with the
`
`invention.
`
`FIG. 2A1 is a diagram 200A1 of an exemplary symmetrical multi-stage network
`
`V(N,d,3) having Omega connection topology of five stages with N = 8, d = 2 and s=3
`
`with exemplary multicast connections, strictly nonblocking network for arbitrary fan-out
`
`15
`
`multicast connections, in accordance with the invention.
`
`FIG. 2C1 is a diagram 200C1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,3) having Omega connection topology of five stages with N; = 8, No = p*
`
`Ni = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`20
`
`invention.
`
`FIG. 2E]1 is a diagram 200E1 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,3) having Omega connection topology of five stages with No = 8, Ni = p*
`
`Nz = 24, where p = 3, and d = 2 with exemplary multicast connections, strictly
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`25
`
`invention.
`
`FIG. 2A2 is a diagram 200A2 of an exemplary symmetrical multi-stage network
`
`V(N,d,3) having nearest neighbor connection topology of five stages with N = 8, d = 2
`
`Page 12 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 13 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`10
`
`and s=3 with exemplary multicast connections, strictly nonblocking network for arbitrary
`
`fan-out multicast connections, in accordance with the invention.
`
`FIG. 2C2 is a diagram 200C2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,3) having nearest neighbor connection topology of five stages with N; = 8,
`
`No = 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. 2E2 is a diagram 200E2 of an exemplary asymmetrical multi-stage network
`
`V(N,,N,,d,3) having nearest neighbor connection topology of five stages with No = 8,
`
`10
`
`Ni = p* No= 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 connections in all the networks disclosed in this
`
`15
`
`invention.
`
`FIG. 4A1 is a diagram 400A1 of an exemplary prior art implementation of a two
`
`by two switch; FIG. 4A2 is a diagram 400A2 for programmable integrated circuit prior
`
`art
`
`implementation of the diagram 400A1 of FIG. 4A1; FIG. 4A3is a diagram 400A3 for
`
`one-time programmable integrated circuit prior art implementation of the diagram 400A1
`
`20
`
`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
`
`The present invention is concerned with the design and operation of large scale
`
`25
`
`crosspoint reduction using arbitrarily large multi-stage switching networks for broadcast,
`
`unicast and multicast connections including their generalized topologies. Particularly
`
`multi-stage networks with stages more than three and radices greater than or equal to two
`
`Page 13 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 14 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`11
`
`offer large scale crosspoint reduction when configured with optimal links as disclosed in
`
`this invention.
`
`Whena transmitting device simultaneously sends information to more than one
`
`receiving device, the one-to-many connection required between the transmitting device
`
`and the receiving devices is called a multicast connection. A set of multicast connections
`
`is referred to as a multicast assignment. When a transmitting device sends information to
`
`one receiving device, the one-to-one connection required between the transmitting device
`
`and the receiving device is called unicast connection. When a transmitting device
`
`simultaneously sends information to all the available receiving devices, the one-to-all
`
`10
`
`connection required between the transmitting device and the receiving devicesis called a
`
`broadcast connection.
`
`In general, a multicast connection is meant to be one-to-many connection, which
`
`includes unicast and broadcast connections. A multicast assignment in a switching
`
`network is nonblocking if any of the available inlet links can always be connected to any
`
`15
`
`of the available outlet links.
`
`In certain multi-stage networksof the type described herein, any connection
`
`request of arbitrary fan-out, i.e. from an inlet link to an outlet link or to a set of outlet
`
`links of the network, can be satisfied without blocking if necessary by rearranging some
`
`of the previous connection requests. In certain other multi-stage networksof the type
`
`20
`
`described herein, any connection request of arbitrary fan-out, i.e. from an inlet link to an
`
`outlet link or to a set of outlet links of the network, can be satisfied without blocking with
`
`never needing to rearrange any of the previous connection requests.
`
`In certain multi-stage networksof the type described herein, any connection
`
`request of unicast from an inlet link to an outlet link of the network, can be satisfied
`
`25
`
`without blocking if necessary by rearranging some of the previous connection requests. In
`
`certain other multi-stage networks of the type described herein, any connection request of
`
`unicast from an inlet link to an outlet link of the network can be satisfied without
`
`blocking with never needing to rearrange any of the previous connection requests.
`
`Page 14 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 15 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`12
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methodsare disclosed as follows:
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks V,,(N,,N,,d,s5) with numerous
`
`connection topologies and the scheduling methods are described in detail in U.S.
`
`Provisional Patent Application, Attorney Serial No. 60/940, 387 that is incorporated by
`
`reference above.
`
`2) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`10
`
`Vtine (N,,N,,d,5) and generalized folded multi-link multi-stage networks
`
`Veamine (N,,N,,d,5) with numerous connection topologies and the scheduling methods
`
`are described in detail in U.S. Provisional Patent Application, Attorney Serial No.
`
`60/940, 389 that is incorporated by reference above.
`
`3) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`15
`
`unicast for generalized multi-link butterfly fat tree networks V,jing (Ni,N.,d,5) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`U.S. Provisional Patent Application, Attorney Serial No. 60/940, 390 that is incorporated
`
`by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`20
`
`unicast for generalized folded multi-stage networks V,,,(N,,N,,d,5) with numerous
`
`connection topologies and the scheduling methods are described in detail in U.S.
`
`Provisional Patent Application, Attorney Serial No. 60/940, 391 that is incorporated by
`
`reference above.
`
`5) Strictly nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`25
`
`multi-stage networksV,,,,,,(N,,N,,d,s) and generalized folded multi-link multi-stage
`
`networks Vpigmntine(Ni,N>,d,5) with numerous connection topologies and the scheduling
`
`Page 15 of 708 IPR2020-00261
`
`VENKAT KONDA EXHIBIT 2032
`
`

`

`Page 16 of 708
`
`IPR2020-00261
`
`VENKAT KONDAEXHIBIT 2032
`
`WO2008/109756
`
`PCT/US2008/056064
`
`13
`
`methods are described in detail in U.S. Provisional Patent Application, Attorney Serial
`
`No. 60/940, 392 that is incorporated by reference above.
`
`6) VLSIlayouts of generalized multi-stage networks V(N,,N.,,d,s5), generalized
`
`folded multi-stage networks V,,,(N,,N,,d,5), generalized butterfly fat tree networks
`
`Vig(N,,N,,d,5), generalized multi-link multi-stage networks V,,,,,.(N,,N>.,d,5),
`
`generalized folded multi-link multi-stage networks Vgi4—mtink (Ni,N2,d,5), generalized
`
`multi-link butterfly fat tree networks V,,ji.Ȣ(N,,N.,d,5), and generalized hypercube
`
`networksV,__,, (N,,N,,d,s) for s = 1,2,3 or any numberin general, are described in
`
`detail in U.S. Provisional Patent Application, Attorney Serial No. M-0045 USthatis
`
`10
`
`incorporated by reference above.
`
`7) VLSI layouts of numerous types of multi-stage networks with locality
`
`exploitation are described in U.S. Provisional Patent Application Serial No. 60/984, 724
`
`entitled "VLSI LAYOUTS OF FULLY CONNECTED NETWORKS WITH LOCALITY
`
`EXPLOITATION"by Venkat Kondaassigned to the same assignee as the current
`
`15
`
`application, filed November 2, 2007.
`
`8) VLSI layouts of numerous types of multistage pyramid networksare described
`
`in U.S. Provisional Patent Application Serial No. 61/018, 494 entitled "VLSI LAYOUTS
`
`OF FULLY CONNECTED GENERALIZED AND PYRAMID NETWORKS"by
`
`Venkat Konda assigned to the same assignee as