`
`
`
`
`
`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-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 2 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`EXHIBIT A
`
`Page 2 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 3 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
` ' |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`(10) International Publication Number
`
`WO 2008/109756 A1
`
`(19) World Intellectual Property Organization _
`International Bureau
`
`(43) International Publication Date
`
`12 September 2008 (12.09.2008)
`
`(51) International Patent Classification:
`H04Q 3/00 (2006.01)
`
`(21) International Application Number:
`PCT/U82008/056064
`
`(22) International Filing Date:
`
`6 March 2008 (06.03.2008)
`
`(25) Filing Language:
`
`(26) Publication Language:
`
`(30) Priority Data:
`60/905,526
`60/940,383
`
`English
`
`English
`
`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
`Way, San Jose, CA 95135 (US).
`
`A0, 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.
`
`(84) 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).
`
`(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
`
`110
`
`130
`(WW
`
`1003
`
`FIG. IR
`l30+10*(L0ng42)
`(WW
`MSLo N—1,1)
`
`
`130+1o»(2*zog,N—4) 120M rW\
`Ms 2xbo_ N—3,1)
`
`
`Hm“) MsrzogN—1,2; M\S.(
`
`
`
`0L1
`
`L(2><Long — 2,1)
`
`
`
`OL(d)
`.
`14; N—2,2><d
`
`3"
`-L(d+1§
`
`OL(2d)
`
`
`“ng0ng — 2,4xd)
`
`ML(2><L<;,,N—2.2X(N—d))
`
`OL(N-d)
`
`- OL(N)
`
`(57) Abstract: A multi—stage network
`comprising (2x logd 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 logd 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
`
`
`
`
`
`
`ML(1 ,ZN)
`
`......................
`
`ML(2XLog,,N —Z,Z>< N)
`
`ML(Long +1,2>< N)
`
`Also the same
`succeeding stage.
`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 (2x logd N) — 1 stages is operated in
`strictly nonblocking manner for multicast includes an input stage having N / d switches with each of them havingd inlet 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 logd 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.
`
`
`
`W02008/109756A1|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`Page 3 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 4 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`WO 2008/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
`
`reference in its entirety the US. Provisional Patent Application Serial No. 60/ 905,526
`
`entitled "LARGE SCALE CROSSPOINT REDUCTION WITH NONBLOCKING
`
`UNICAST & MULTICAST IN ARBITRARILY LARGE MULTI—STAGE
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed March 6, 2007.
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`reference in its entirety the US. Provisional Patent Application Serial No. 60/ 940, 383
`
`entitled "FULLY CONNECTED 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 US
`
`Provisional Patent Application Serial No. 60 / 940, 387 entitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE NETWORKS" by Venkat Konda assigned
`
`to the same assignee as the current application, filed May 25, 2007.
`
`10
`
`15
`
`20
`
`This application is related to and incorporates by reference in its entirety the US
`
`Provisional Patent Application Serial 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
`
`25
`
`application, filed May 25, 2007.
`
`Page 4 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 5 of 708
`
`IPR2020—00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`2
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Serial No. 60/940, 390 entitled "FULLY CONNECTED
`
`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 US.
`
`Provisional Patent Application Serial No. 60/940, 391 entitled "FULLY CONNECTED
`
`GENERALIZED FOLDED 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 US.
`
`Provisional Patent Application Serial No. 60/940, 392 entitled "FULLY CONNECTED
`
`GENERALIZED STRICTLY NONBLOCKING MULTI-LINK 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 US.
`
`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 US.
`
`Provisional Patent Application Serial No. 60/984, 724 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED NETWORKS WITH LOCALITY EXPLOITATION" by Venkat
`
`Konda assigned to the same assignee as the current application, filed November 2, 2007.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`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 the current application, filed January 1, 2008.
`
`10
`
`15
`
`20
`
`25
`
`Page 5 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 6 of 708
`
`IPR2020—00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`BACKGROUND OF 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 between its 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 number of 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
`
`15
`
`20
`
`25
`
`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
`
`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 connections, 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 nonblocking 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 carefully 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 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 Networks of radix
`
`two are shown to be built with back to back baseline networks which are rearrangeably
`
`30
`
`nonblocking for unicast connections.
`
`Page 6 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 7 of 708
`
`IPR2020—00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`4
`
`US. 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 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 indicates that if the number of switches in the middle stage, m,
`
`of a three-stage network satisfies the relation m 2 min((n —1)(x + r1” )) where
`
`1 S x S min(n — 1, r) , the resulting network is nonblocking 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.
`
`US Patent 6,885,669 entitled “Rearrangeably Nonblocking Multicast Multi-stage
`
`Networks” by Konda showed that three-stage Clos network is rearrangeably nonblocking
`
`for arbitrary fan-out multicast connections when m 2 2 X n. And US. Patent 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 m 2 3 X n —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-
`
`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 2 X N X (log d N)2‘58 for strictly
`
`nonblocking unicast network. Similarly US. Patent 6,885,669 entitled “Rearrangeably
`
`Nonblocking Multicast Multi-stage Networks” by Konda showed a way of constructing
`
`large multi-stage networks by recursive substitution for rearrangeably nonblocking
`
`multicast network. An article by D. G. Cantor entitled “On Non-Blocking Switching
`
`Networks” 1: pp. 367-377, 1972 by John Wiley and Sons, Inc., showed a way of
`
`constructing large multi-stage networks with a crosspoint complexity of
`
`d 2 X N X (log d N)2 for strictly nonblocking unicast, (by using log d N number of Benes
`
`Networks for d = 2) and without counting the crosspoints in multiplexers and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Page 7 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 8 of 708
`
`IPR2020—00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`5
`
`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 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
`
`SUMMARY OF INVENTION
`
`A multi-stage network comprising (2X log d N) —1 stages is operated in strictly
`
`nonblocking manner for unicast includes an input stage hav1ng — sw1tches With each of
`d
`
`them having d inlet links and 2X d outgoing links connecting to second stage switches,
`
`an output stage having fl switches with each of them having d outlet links and 2 X d
`d
`
`incoming links connecting from switches in the penultimate stage. The network also has
`
`(2X log d N) — 3 middle stages with each middle stage having
`
`
`2><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. 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.
`
`15
`
`20
`
`A multi-stage network comprising (2X log d N) —1 stages is operated in strictly
`
`nonblocking manner for multicast includes an input stage hav1ng — sw1tches With each
`d
`
`of them having d inlet links and 3X d outgoing links connecting to second stage
`
`Page 8 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 9 of 708
`
`IPR2020—00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`.
`.
`.
`.
`N
`.
`.
`sw1tches, an output stage hav1ng — sw1tches With each of them hav1ng d outlet links
`d
`
`and 3 X d incoming links connecting from switches in the penultimate stage. The
`
`d
`
`3><N
`
`network also has (2X log d 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 preceding stage, and d outgoing links connecting to the
`
`switches in its immediate succeeding stage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi-stage network
`
`10
`
`V(N,d, 5) 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
`
`15
`
`V(N,d,2) with (2Xlog d N )—1
`
`stages
`
`strictly nonblocking network for unicast
`
`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(N1,N2,d ,2) having inverse Benes connection topology of five stages with N1 = 8, N2
`
`= p* N1 = 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(N1,N2,d ,2) with N2 = p* N1 and with (2Xlogd N )—1 stages strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections in accordance with the invention.
`
`20
`
`25
`
`Page 9 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 10 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`7
`
`FIG. 1E is a diagram 100E of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,d ,2) having inverse Benes connection topology of five stages with N2 = 8, N1
`
`= p* N2 = 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(N1,N2,d,2) with N1 = p* N2 and with (2Xlogd N )—1 stages strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections in accordance with the invention.
`
`10
`
`15
`
`20
`
`25
`
`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.
`
`FIG. 1C1 is a diagram 100C1 of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,d ,2) having Omega connection topology of five stages with N1 = 8, N2 = p*
`
`N1 = 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. 1E1 is a diagram 100E1 of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,d ,2) having Omega connection topology of five stages with N2 = 8, N1 = p*
`
`N2 = 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. 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-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 11 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/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(N1,N2,d ,2) having nearest neighbor connection topology of five stages with N1 = 8,
`
`N2 = p* N1 = 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(N1,N2,d ,2) having nearest neighbor connection topology of five stages with N2 = 8,
`
`N1 = p* N2 = 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
`
`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 (2Xlogd 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(N1,N2,d ,3) having inverse Benes connection topology of five stages with N1 = 8, N2
`
`= p* N1 = 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(N1,N2,d,3) with N2 = p* N1 and with (2Xlogd N)—1 stages strictly
`
`10
`
`15
`
`20
`
`25
`
`Page 11 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 12 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/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(N1 , N2,d ,3) having inverse Benes connection topology of five stages with N2 = 8, N1
`
`= p* N2 = 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(N1,N2,d,3) with N1 = p* N2 and with (2Xlogd N)—l
`
`stages strictly
`
`10
`
`nonblocking network for arbitrary fan-out multicast connections in accordance with the
`
`invention.
`
`FIG. 2A1 is a diagram 200Al 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 200Cl of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,d ,3) having Omega connection topology of five stages with N1 = 8, N2 = p*
`
`N1 = 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. 2E1 is a diagram 200El of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,d ,3) having Omega connection topology of five stages with N2 = 8, N1 = p*
`
`N2 = 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-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 13 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/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(N1,N2,d ,3) having nearest neighbor connection topology of five stages with N1 = 8,
`
`N2 = p* N1 = 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(N1,N2,d ,3) having nearest neighbor connection topology of five stages with N2 = 8,
`
`10
`
`N1 = p* N2 = 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 400Al 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. 4A3 is a diagram 400A3 for
`
`one-time programmable integrated circuit prior art implementation of the diagram 400Al
`
`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
`
`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
`
`20
`
`25
`
`Page 13 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 14 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`11
`
`offer large scale crosspoint reduction when configured with optimal links as disclosed in
`
`this invention.
`
`When a 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 devices is 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 networks of 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 networks of 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 with
`
`never needing to rearrange any of the previous connection requests.
`
`In certain 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 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.
`
`20
`
`25
`
`Page 14 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 15 of 708
`
`IPR2020—00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`12
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks Vbfl (N1 , N2, d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application, Attorney Serial No. 60/ 940, 387 that is incorporated by
`
`reference above.
`
`10
`
`15
`
`20
`
`25
`
`2) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`leink (N1 , N2 , d , s) and generalized folded multi-link multi-stage networks
`
`Vfoldimlink (N1 , N2 , d , s) with numerous connection topologies and the scheduling methods
`
`are described in detail in US. 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
`
`unicast for generalized multi-link butterfly fat tree networks leink_bfi (N1 , N2 , d , s) with
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`US. 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
`
`unicast for generalized folded multi-stage networks Vfold (N1 , N2 , d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`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
`
`multi-stage networks leink (N1 , N2 , d , s) and generalized folded multi-link multi-stage
`
`networks Vfoldwhnk (N1 , N2 , d , s) with numerous connection topologies and the scheduling
`
`Page 15 of 708 IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`
`
`Page 16 of 708
`
`IPR2020-00260
`
`VENKAT KONDA EXHIBIT 2032
`
`W0 2008/109756
`
`PCT/US2008/056064
`
`13
`
`methods are described in detail in US. Provisional Patent Application, Attorney Serial
`
`No. 60/ 940, 392 that is incorporated by reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N1 , N2 , d , s) , generalized
`
`folded multi-stage networks Vfold (N1 , N2 , d , s) , generalized butterfly fat tree networks
`
`Vbfi (N1 , N2 , d , s) , generalized multi-link multi-stage networks leink (N1 , N2 , d , s) ,
`
`generalized folded multi-link multi-stage networks Vfoldwhnk (N1 , N2 , d , s) , generalized
`
`multi-link butterfly fat tree networks leink_bfi (N1, N2, d , s) , and generalized hypercube
`
`networks Vhwbe (N1,N2,al , s) for s = 1,2,3 or any number in general, are described in
`
`detail in US. Provisional Patent Application, Attorney Serial No. M-0045 US that is
`
`10
`
`incorporated by reference above.
`
`7) VLSI layouts of numerous types of multi-stage networ