| b.2007)
`PTO-L182 (Rev.
`Approved for use through 02/28/20l0. 0MB 065l-002l
`US. Patent and Trademark Office; US DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of I995, no persons are required to respond to a collection of information unless it displays a valid OMB control number.
`
`TRANSMITTAL LETTER TO THE UNITED STATES RECEIVING OFFICE
`
`Express Mail mailing number:
`
`Date of deposit: 3/6/2008
`
`File reference no.: 3-0036 PCT
`
`lntemational application no. (if known):
`
`Customer Number‘: 38139
`
`Earliest priority date claimed (Day/Month/Year): 3/6/2007
`
`
`
`
`
`Title of the invention: Fully Connected Generalized Multi-stage Networks
`
`‘ Customer Number will allow access to the application in Private PAIR but cannot be used to establish or change the correspondence address.
`
`This is a new International Application
`
`SCREENING DISCLOSURE INFORMATION:
`
`In order to assist in screening the accompanying international application for purposes of determining whether a
`license for foreign transmittal should and could be granted and for other purposes, the following information is
`supplied. (check as boxes as apply):
`
`The invention disclose was not made in the United States of America.
`
`There is no prior US application relating to this invention.
`
`The following prior U.S. application(s) contain subject matter which is related to the invention disclosed in the
`attached international application. (NOTE: priority to these applications man; or may not be claimed on the
`Request (form PCT/RO/I ()1) and this listing does not constitute a claim for priority.)
`
`
`
`The present international application contains additional subject matter not found in the prior U.S. application(s)
`identified above. The additional subject matter is found on pages
`59-72
`and
`DOES NOT ALTER
`[:I MIGHT BE CONSIDERED TO ALTER the general nature of the
`invention in a manner which would require the US. application to have been made available for inspection by the
`appropriate defense agencies under 35 U.S.C. lSl and 37 C.F.R. 5.15.
`Itemized list of contents
`
`
`
`
`_
`Sheets ofdescription .
`(excluding sequence listing): 76
`
`Sheets of abstract:
`
`1
`
`Sheets of drawings: 29
`
`Sheets of sequence listing:
`
`Sequence listing diskette/CD:
`
`Tables related to sequence listing CD:
`
`.
`Return receipt postcard:
`
`Certified copy °.f priority
`document (specrfy):
`
`
` Other (specify):
`
`
`
`
`
`form is:
`
`The person
`signing this
`
`Applicant
`
`Venkat Konda
`
`D Attomey/Agent (Reg. No.)
`
`Name ofPerson signing
`Nenkat Konda/
`
`Signature
`CI Common Representative
`This collection of'iniormation is required by 37 CFR HO and |.412. The information is required to obtain or retain a benefit by the public, which is to file (and by the
`USPTO to process) an application. Confidentiality is govemed by 35 LLSC. 122 and 37 (‘FR 1 H and l 14. This collection is estimated in take 15 minutes In complete,
`including gathering information. preparing, and submitting the completed fonn to the USPTO. Time will vary depending upon the individual case. Any comments on the
`amount of time you require to complete this form and/or suggestions for reducing this burden, should be sent to the Chief lnfonnation Officer, US. Patent and Trademark
`Office, US Department ofConimerce, PO. Box 1450, Alexandria, VA 223l3~l450. DO NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS.
`SEND TO: Mail Stop PCT. Commissioner for Patents, PO. Box 1450, Alexandria, VA 22313-1450.
`
`Page 1 of 137
`
`FLEX LOGIX EXHIBIT 1012
`
`Page l of l
`
`Page 1 of 137
`
`FLEX LOGIX EXHIBIT 1012
`
`

`

`Electronic Patent Application Fee Transmittal
`——
`
`Filing Date:
`
`Title of Invention:
`
`Fully Connected Generalized Multi-stage Networks
`
`First Named Inventor/Applicant Name:
`
`Venkat Konda
`
`Venkar Konda
`
`Attorney Docket Number:
`
`8-0036PCT
`
`International Application for filing in the US receiving office Filing Fees
`
`was?"
`
`Basic Filing:
`
`
`
`
`
`
`
`1 300Transmittal fee 300
`
`
`
`PCT Search Fee- no prior US appl filed
`
`Intl Filing Fee (1st-30 Pgs.) PCT Easy
`
`Suppl. Intl Filing Fee (each page > 30)
`
`1701
`
`1703
`
`89
`
`13
`
`1109
`
`1157
`
`Miscellaneous-Filing:
`
`Page 2 of 137
`
`Page 2 of 137
`
`

`

`Post-AIIowance-andPost-Issuance:
`
`Extension-of-Time:
`
`Patent-Appeals-and-lnterference:
`
`4366
`
`Total in USD ($)
`
`Page 3 of 137
`
`Page 3 of 137
`
`

`

`Electronic Acknowledgement Receipt
`
`“—
`——
`
`
`
`International Application Number: PCT/U808/56064
`
`Confirmation Number:
`
`5795
`
`Title of Invention:
`
`Fully Connected Generalized Multi-stage Networks
`
`
`
`Customer Number:
`
`38139
`
`Correspondence Address:
`
`Venkat Konda
`
`Konda Technologies Inc
`
`6278 Grand Oak Way
`
`San Jose
`
`US
`
`408-472-3273
`
`venkat@kondatech.com
`
`“—
`
`
`
`Receipt Date: oe-MAR-zoos
`
`Filing Date:
`
`Time Stamp:
`
`17:14:01
`
`Application Type:
`
`International Application for filing in the US receiving office
`
`Payment information:
`
`Submitted with Payment
`
`yes
`
`Page 4 of 137
`
`Page 4 of 137
`
`

`

`
`Payment Type
`Credit Card
`
`Payment was successfully received in RAM
`
`$4366
`
`
`File Listing:
`
`Document
`Number
`
`Document Description
`
`File Name
`
`8-0036PCT.pdf
`
`part /.zip (if appl.)
`
`File Size(Bytes)
`/Message Digest
`413391
`
`4200511591155e$212d36b0d1leb1cb6
`d4000545
`
`Multipart Description/PDF files in .zip description
`
`—mu
`
`—-—
`
`
`
`Drawings-only black and white line
`rawmgs
`d
`.
`
`8-0036PCT-FIGS.pdf
`
`3206246264348851 95e28487cb6443b
`b7d4d4619
`
`277196
`
`FIG/101 - Request form for new IA -
`.
`Conventional
`
`S-OOS6PCT-RO-101PDF
`
`265627
`
`311c4206b0117d8253110427b9d41be1c9
`833418
`
`Fee payment - International
`.
`.
`Application
`
`8-0036PCT-Fee.PDF
`
`23:1e77d0160'6438d'd78b0d6134dab
`78603657
`
`PCT-Transmittal Letter
`
`S-OOSGPCT-PTO-1382PDF
`
`131178
`
`811bd6696db0119307d295217712413
`012352230
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Page 5 of 137
`
`Page 5 of 137
`
`

`

`Fee Worksheet (PTO—06)
`
`fee—info.pdf
`
`3261d696b292021190370100d6262243
`78d4ecod
`
`Warnings:
`
`Information:
`
`Total Files Size (in bytes):
`
`1164666
`
`Receipt will establish the international filing date of the application.
`
`New International Application Filed with the USPTO as a Receiving Office
`If a new international application is being filed and the international application includes the necessary
`components for an international filing date (see PCT Article 11 and MPEP 1810), a Notification of the
`International Application Number and of the International Filing Date (Form PCT/RO/105) will be issued in due
`course, subject to prescriptions concerning national security, and the date shown on this Acknowledgement
`
`This Acknowledgement Receipt evidences receipt on the noted date by the USPTO of the indicated documents,
`characterized by the applicant, and including page counts, where applicable.
`It serves as evidence of receipt
`similar to a Post Card, as described in MPEP 503.
`
`New Applications Under 35 U.S.C. 111
`If a new application is being filed and the application includes the necessary components for a filing date (see
`37 CFR 1.53(b)-(d) and MPEP 506), a Filing Receipt (37 CFR 1.54) will be issued in due course and the date
`shown on this Acknowledgement Receipt will establish the filing date of the application.
`
`National Stage of an International Application under 35 U.S.C. 371
`If a timely submission to enter the national stage of an international application is compliant with the conditions
`of 35 U.S.C. 371 and other applicable requirements a Form PCT/DO/EO/903 indicating acceptance of the
`application as a national stage submission under 35 U.S.C. 371 will be issued in addition to the Filing Receipt,
`in due course.
`
`Page 6 of 137
`
`Page 6 of 137
`
`

`

`5-0036 PCT
`
`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 7 of 137
`
`Page 7 of 137
`
`

`

`5-0036 PCT
`
`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 8 of 137
`
`Page 8 of 137
`
`

`

`5-0036 PCT
`
`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 9 of 137
`
`Page 9 of 137
`
`

`

`5-0036 PCT
`
`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 a N)2 for strictly nonblocking unicast, (by using log a N number of Benes
`
`Networks for d = 2) and without counting the crosspoints in multiplexers and
`
`_4_
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Page 10 of 137
`
`Page 10 of 137
`
`

`

`5-0036 PCT
`
`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 N2256.
`
`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 (2Xlogd 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 2X d
`d
`
`incoming links connecting from switches in the penultimate stage. The network also has
`
`switches, and each
`
`d
`
`2xN
`
`(2X log d N ) — 3 middle stages with each middle stage having
`
`switch in the middle stage has (I 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 (2Xlogd N ) —1 stages is operated in strictly
`
`N
`nonblocking manner for multicast includes an input stage having — switches with each
`d
`
`of them having d inlet links and 3X d outgoing links connecting to second stage
`
`Page 11 0f137
`
`Page 11 of 137
`
`

`

`5-0036 PCT
`
`N
`switches, an output stage having — switches with each of them having d outlet links
`d
`
`and 3X d incoming links connecting from switches in the penultimate stage. The
`
`3xN
`
`network also has (2Xlogd N) — 3 middle stages with each middle stage having
`
`d,
`
`switches, and each switch in the middle stage has d incoming links connecting from the
`
`switches in its immediate preceding stage, and (I outgoing links connecting to the
`
`switches in its immediate succeeding stage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`10
`
`15
`
`FIG. 1A is a diagram 100A 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=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 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.
`
`—6—
`
`Page 12 of 137
`
`Page 12 of 137
`
`

`

`5-0036 PCT
`
`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* 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.
`
`lF is a diagram lOOF of a general asymmetrical multi-stage network
`
`V(N1,N2,d,2) with N1 = p1< 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 13 of 137
`
`Page 13 of 137
`
`

`

`5-0036 PCT
`
`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 (2X log d 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. 2Dl & FIG. 2D2 is a diagram 200D of a general asymmetrical multi-stage
`
`network V(N,,N2,d,3) with N2 = p* N1 and with (2Xlogd N)—1 stages strictly
`
`10
`
`15
`
`20
`
`25
`
`Page 14 of 137
`
`Page 14 of 137
`
`

`

`5-0036 PCT
`
`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)—1 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
`
`_9_
`
`Page 15 of 137
`
`Page 15 of 137
`
`

`

`5-0036 PCT
`
`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.
`
`20
`
`25
`
`FIG. 4A1 is a diagram 400A1 of an exemplary prior art implementation of a two
`
`by two switch; FIG. 4A2 is a diagram 4OOA2 for programmable integrated circuit prior
`
`art
`
`implementation of the diagram 400A] of FIG. 4A]; FIG. 4A3 is a diagram 4OOA3 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
`
`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
`
`_10_
`
`Page 16 of 137
`
`Page 16 of 137
`
`

`

`5-0036 PCT
`
`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
`
`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.
`
`-11-
`
`Page 17 of 137
`
`Page 17 of 137
`
`

`

`5-0036 PCT
`
`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 , cl , 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—bft (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 Vmfink (N1, N2 , d , s) and generalized folded multi-link multi-stage
`
`networks Vfo,d_m,ink (N1 , N2 , d, s) with numerous connection topologies and the scheduling
`
`-12-
`
`Page 18 of 137
`
`Page 18 of 137
`
`

`

`5-0036 PCT
`
`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-st