`
`
`
`
`
`
`| 1-2007}
`PTO-1382 (Rev.
`Approved for use through 02/28/2010. OMB 0651-0021
`US. Patent and Trademark Office, U.S. DEPARTMENT OF COMMERCE
`Underthe Paperwork Reduction Act of 1995, 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:
`
`
`
`File reference no: §-0096 PCT
`
`Customer Number!: 38138
`
`
`
`
`
`
`
`Venkat Konda/ [1 Common Representative
`
`' Customer Numberwill 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 orderto 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):
`
`CJ
`
`The invention disclose was not made in the United States of America.
`
`[]_There is no prior U.S. 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. (VOTE: priority to these applications may or may not be claimed on the
`Request (form PCT/RO/101) and this listing does not constitute a claim for priority.)
`
`
`
`application no.|60/905,526 3/6/2007
`
`application no.
`
`60/940,383
`
`filed on
`
`5/25/2007
`
`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
`_69-72
`and
`DOES NOT ALTER
`[] MIGHT BE CONSIDERED TO ALTER the generalnature ofthe
`invention in a manner which would require the U.S. application to have been madeavailable for inspection by the
`appropriate defense agencies under 35 U.S.C. 181 and 37 C.F.R. 5.15.
`Itemized list of contents
`
`Sheets of description
`(excluding sequencelisting): 76
`
`.
`Return receipt postcard:
`
`Sheets ofabstract: 4
`
`Sheets of drawings: 29
`
`Sheets of sequence listing:
`
`Sequence listing diskette/CD:
`
`Tables related to sequence listing CD:
`
`Certified copy of. priority
`document(specify):
`
`Other(specify):
`
`The person
`signing this
`formis:
`
`Applicant
`[[] Attorney/Agent (Reg. No.)
`
`Nameofperson signing
`
`Venkat Konda
`
`Signature
`This callection of information is required by 37 CFR 1.10 and 1.412. The information is required to obtainor retain a benefit by the public, whichts to file (and by the
`USPTOto process) an application. Confidentiality is governed by 35 U.S.C. 122 and 37 CFR 1.11 and 1 14. This collection is estimated to take 15 minutes to complete,
`including gathering information, preparing, and submitting the completed formto the USPTO. Time will vary depending upon the individual case. Any commentson the
`amountof time you require to complete this form and/or suggestions for reducing this burden, should be sent to the Chief Information Officer, U.S. Patent and Trademark
`Office, U.S. Department of Commerce, P.O. Box 1450, Alexandria, VA 22313-1450. DO NOT SEND FEES OR COMPLETED FORMSTO THIS ADDRESS.
`SEND TO: Mail Step PCT, Commissioner for Patents, P.O. Box 1450, Alexandria, VA 22313-1450.
`
`Page 1 of 137
`
`FLEX LOGIX EXHIBIT 1012
`
`Page | of|
`
`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
`
`Attorney Docket Number:
`
`§$-0036PCT
`
`International Application for filing in the US receiving office Filing Fees
`
`sony] ame |
`
`Basic Filing:
`
`
`
`
`
`1 300Transmittal fee 300
`
`
`
`
`
`PCT Search Fee- no prior US appl filed
`
`Int! 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
`
`

`

`eeeDssee|a
`
`4366
`
`Miscellaneous:
`
`Total in USD ($)
`
`Page 3 of 137
`
`Page 3 of 137
`
`

`

`Electronic Acknowledgement Receipt
`Se
`|__epteasonnumpes
`
`
`
`International Application Number: PCT/US08/56064
`
`Confirmation Number:
`
`5795
`
`Title of Invention:
`
`Fully Connected Generalized Multi-stage Networks
`
`Customer Number:
`
`38139
`
`CorrespondenceAddress:
`
`Venkat Konda
`
`Konda Technologies Inc
`
`6278 Grand Oak Way
`
`San Jose
`
`US
`
`408-472-3273
`
`venkat@kondatech.com
`
`
`
`eeie
`
`
`
`ReceiptDate: 06-MAR-2008
`
`Filing Date:
`
`Time Stamp:
`
`17:14:01
`
`Application Type:
`
`International Application for filing in the US receiving office
`
`Paymentinformation:
`
`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
`
`DocumentDescription
`
`File Name
`
`File Size(Bytes)
`/Message Digest| Part /.zip|
`413391
`
`(if appl.)
`
`$-0036PCT.pdt
`
`4200511591 155e8212d36b0d1feb1 ch6
`d4cc0e45
`
`Multipart Description/PDFfiles in .zip description
`
`ee
`
`pWarningss
`Warnings:
`
`es
`
`Information:
`
`——
`;
`Drawings-only black and white line
`drawi
`rawings
`
`S-0036PCT-FIGs.pdf
`
`277196
`
`3206246264348851 9528487cb6443b
`b7d4d4619
`
`RO/101 - Request form for new IA -
`:
`Conventional
`
`S-0036PCT-RO-101.PDF
`
`265627
`
`3t1c4206b0It7d8253tc427p9d41 bel c9
`83ad18
`
`Fee payment- International
`oe
`Application
`
`S-0036PCT-Fee. PDF
`
`23c1 e77d01 GOtc438did78bOdG61 S4dab
`78203667
`
`PCT-Transmittal Letter
`
`S-0036PCT-PTO-1382.PDF
`
`131178
`
`81 1bd6e96db01 19307d298217712413
`02352230
`
`Information:
`
`Information:
`
`Information:
`
`Warnings
`
`Information:
`
`Page 5 of 137
`
`Page 5 of 137
`
`

`

`Fee Worksheet (PTO-06)
`
`fee-info.paf
`
`3261d696b292021 19¢37c100d62e2243
`
`Warnings:
`Information:
`
`Total Files Size (in bytes);
`
`1164666
`
`Receiptwill 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
`componentsfor an internationalfiling date (see PCT Article 11 and MPEP 1810), a Notification of the
`International Application Numberand ofthe 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 AcknowledgementReceipt evidences receipt on the noted date by the USPTOofthe indicated documents,
`characterized by the applicant, and including page counts, where applicable.
`It serves as evidenceof 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 componentsfora 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
`shownon this Acknowledgement Receiptwill 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 acceptanceof 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
`
`

`

`$-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 U.S. Provisional Patent Application Serial No. 60/905,526
`
`entitled "LARGE SCALE CROSSPOINT REDUCTION WITH NONBLOCKING
`
`UNICAST & MULTICAST IN ARBITRARILY LARGE MULTI-STAGE
`
`10
`
`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 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 referencein 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 referencein 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 7 of 137
`
`Page 7 of 137
`
`

`

`$-0036 PCT
`
`This application is related to and incorporates by referencein 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
`
`Konda assigned to the same assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by referencein 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 referencein its entirety the U.S.
`
`10
`
`Provisional Patent Application Serial No. 60/940, 392 entitled "FULLY CONNECTED
`
`GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULTISTAGE
`
`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.
`
`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 referencein its entirety the U.S.
`
`Provisional Patent Application Serial No. 60/984, 724 entitled "VLSI LAYOUTS OF
`
`20
`
`FULLY CONNECTED NETWORKS WITH LOCALITY EXPLOITATION"by Venkat
`
`Konda assigned to the sameassignee as the current application, filed November2, 2007.
`
`This application is related to and incorporates by referencein 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
`
`Konda assigned to the same assigneeas the current application, filed January 1, 2008.
`
`Page 8 of 137
`
`Page 8 of 137
`
`

`

`$-0036 PCT
`
`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
`
`"{nputs") and outlet links (also called "outputs") than would be required bya single stage
`
`(e.g. crossbar) switch having the same numberof inputs and outputs. Clos and Benes
`
`networksare very popularly used in digital crossconnects, switch fabrics and parallel
`
`computer systems. However Clos and Benes networks may block someof 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 incoming calls 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 network to satisfy the request without disturbing
`
`other existing connections, and if more than one such pathis 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 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.
`
`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 Networksofradix
`
`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
`
`

`

`$-0036 PCT
`
`U.S. Patent 5,451,936 entitled “Non-blocking Broadcast Network”granted to
`
`Yangetal. 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 background section at column 1, line 22 to column 3, 59. An article 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 network satisfies the relation m= min((n -—1)(x4r'" )) where
`
`1<x<min(a —1,r), the resulting network is nonblocking for multicast assignments. In
`
`10
`
`the relation, r is 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 m2=2xn. And U.S. Patent 6,868,084
`
`15
`
`entitled “Strictly Nonblocking Multicast Multi-stage Networks” by Konda showedthat
`
`three-stage Clos network is 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 wayof constructing large multi-stage networks by
`
`recursive substitution with a crosspoint complexity of d’ x Nx (log, N)’™forstrictly
`
`nonblocking unicast network. Similarly U.S. Patent 6,885,669 entitled “Rearrangeably
`
`Nonblocking Multicast Multi-stage Networks” by Konda showed a wayofconstructing
`
`25
`
`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° xNx(log, N)° forstrictly nonblocking unicast, (by using log, N numberof Benes
`
`30
`
`Networks for d = 2) and without counting the crosspoints in multiplexers and
`
`4.
`
`Page 10 of 137
`
`Page 10 of 137
`
`

`

`$-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 N=256.
`
`The crosspoint complexity of all these networks is prohibitively large to
`
`implementthe 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 (2xlogaN)-1 stages is operated in strictly
`
`nonblocking mannerfor unicast includes an input stage having a 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
`(2xlogaN)-—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 switches in 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 (2xlogaN)-1 stages is operated in strictly
`
`nonblocking mannerfor multicast includes an input stage having 7 switches with each
`
`of them having d inlet links and 3x d outgoing links connecting to second stage
`
`Page 11 of 137
`
`Page 11 of 137
`
`

`

`$-0036 PCT
`
`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 logiN)-3 middle stages with each middle stage having 3x
`
`
`
`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
`
`switches in 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 iN)-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 topology offive stages with Ni = 8, N2
`
`= p* N; = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention,
`
`FIG. 1D is a diagram 100D of a general asymmetrical multi-stage network
`V(N,.N,,.d.2) with No = p* N; and with (2xlog, 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
`
`

`

`$-0036 PCT
`
`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* Np and with (2xlog, N)-1 stagesstrictly 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, 1E1 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 13 of 137
`
`Page 13 of 137
`
`

`

`$-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(N,,N,,d,2) having nearest neighbor connection topology of five stages with N; = 8,
`
`Nz = 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 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. 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 connectionsstrictly 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, N)-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 N. = p* N; and with (2xlog,N)-1 stages strictly
`
`Page 14 of 137
`
`Page 14 of 137
`
`

`

`$-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(N,,N,.d,3) having inverse Benes connection topologyof 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, Nz = 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
`
`20
`
`invention.
`
`FIG, 2E1 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, N; = 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
`
`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
`
`

`

`$-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(N,,N,.d,3) having nearest neighbor connection topology of five stages with N; = 8,
`
`Nz = 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,
`
`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. 4A? 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 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
`
`-10-
`
`Page 16 of 137
`
`Page 16 of 137
`
`

`

`$-0036 PCT
`
`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 networks of the type described herein, any connection
`
`request of arbitrary fan-out, i.e. from an inletlink 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 inletlink 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 aninlet 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
`
`

`

`$-0036 PCT
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`1) Strictly and rearrangeably nonblockingfor arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks V,,(N,,N,,d,s) with numerous
`
`connection topologies and the scheduling methods are described in detai] 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
`
`Ving (N{»N>,d,5) and generalized folded multi-link multi-stage networks
`
`Viotd—mlink (N,,N,.d,s) 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,,jin» (N,.N2,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 networks V,,,,,(N,,N,,d,s) and generalized folded multi-link multi-stage
`
`networks Viimtine(Ni,N,,d, 5) with numerous connection topologies and the scheduling
`
`-12-
`
`Page 18 of 137
`
`Page 18 of 137
`
`

`

`$-0036 PCT
`
`methods are described in detail in U.S. Provisional Patent Application, Attorney Serial
`
`No. 60/940, 392 that is incorporated by reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N,,N,,d,5), generalized
`
`folded multi-stage networks V,.,(N,,N,,d,5), generalized butterfly fat tree networks
`
`Vig(N,,N,,d,s), generalized multi-link multi-stage networks V,,,,.,(N,,N,,d,5),
`
`generalized folded multi-link multi-stage networks Vjeia—miine(Ni,N2,d,5), generalized
`
`multi-link butterfly fat tree networks V,,ji.4,(Ni,N.,d,5), and generalized hypercube
`
`networks V,_,, (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 Pa