`Approved for use through 02/28/2010. OMB 0651-0021
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of 1995, no personsare required to respondto a collection of information unlessit displays a valid OMB control number.
`
`TRANSMITTAL LETTER TO THE UNITED STATES RECEIVING OFFICE
`Express Mail mailing number:
`Date of deposit: 5/22/2008
`
`International application no. (if known):
`File reference no.; S-0039 PCT
`Earliest priority date claimed (Day/Month/Year): 5/25/2007
`Customer Number!: 38139
`Title of the invention: Fully Connected Generalized Multi-Link Multi-Stage Networks
`
`' 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 accompanyinginternational 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):
`
`(J
`
`(]__
`
`Theinvention 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 whichis related to the invention disclosed in the
`attached international application. (NOTE: priority to these applications may or may not be claimed on the
`Request (form PCT/RO/101) andthis listing does net 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
`_207-211
`and
`DOES NOT ALTER
`[] MIGHT BE CONSIDERED TO ALTER thegeneral nature ofthe
`invention in a manner which would require the U.S. application to have been made available for inspection by the
`appropriate defense agencies under 35 U.S.C. 181 and 37 C.F.R. 5.15.
`Itemized list of contents
`
`
`/Nenkat Konda/ (-] CommonRepresentative
`
`Sheets of description
`(excluding sequence listing): 211
`
`.
`Return receipt postcard:
`
`Sheets of abstract: 1
`
`Sheets of drawings: 125
`
`Sheets of sequence listing:
`
`Sequencelisting diskette/CD:
`
`Tables related to sequence listing CD:
`
`Certified copy of. priority
`document(specify):
`Other(specify):
`
`The person
`signing this
`form is:
`
`Applicant
` Attomey/Agent (Reg. No.)
`
`[]
`
`Name ofperson signing
`
`Venkat Konda
`
`Signature
`This collection of information is required by 37 CFR 1.10 and 1.412. The information is required to obtain or retain a benefit by the public, whichtsto 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 form to the USPTO. Timewill vary depending uponthe individual case. Any commentson the
`amount of 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 Stop PCT, Commissioner for Patents, P.O. Box 1450, Alexandria, VA 22313-1450.
`
`Page 1 of 369
`
`FLEX LOGIX EXHIBIT 1020
`
`Page | of 1
`
`
`
`Page 1 of 369
`
`FLEX LOGIX EXHIBIT 1020
`
`
`
`Electronic Patent Application Fee Transmittal
`
`Filing Date:
`
`Title of Invention:
`
`FULLY CONNECTED GENERALIZED MULTI-LINK MULTI-STAGE
`NETWORKS
`
`First Named Inventor/Applicant Name:
`
`Venkat Konda
`
`Attorney Docket Number:
`
`§-0039PCT
`
`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
`
`320
`
`1173
`
`14
`
`1173
`
`4480
`
`Miscellaneous-Filing:
`
`Page 2 of 369
`
`Page 2 of 369
`
`
`
`eeeDssee|a
`
`7753
`
`Miscellaneous:
`
`Total in USD ($)
`
`Page 3 of 369
`
`Page 3 of 369
`
`
`
`Electronic Acknowledgement Receipt
`Se
`|__epteasonnumpes
`
`
`
`International Application Number: PCT/US08/64604
`
`Confirmation Number:
`
`5419
`
`Title of Invention:
`
`FULLY CONNECTED GENERALIZED MULTI-LINK 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: 22-MAY-2008
`
`Filing Date:
`
`Time Stamp:
`
`23:42:21
`
`Application Type:
`
`International Application for filing in the US receiving office
`
`Paymentinformation:
`
`Page 4 of 369
`
`Page 4 of 369
`
`
`
`Number DocumentDescription|FileName /Message Digest} Part /.zip| (if appl.)
`
`-
`
`oe
`
`File Size(Bytes)
`
`Multi
`
`Pages
`
`
`
`
`
`546772d05
`
`Specification
`
`S-0039PCT.pdf
`
`1016396
`
`1551 548beccStadedatt2672e1b6idteda
`4a6di2
`
`——
`;
`Drawings-only black and white line
`drawi
`rawings
`
`S-0039PCT-FIGs.pdf
`
`901693
`
`bf3ata7239e79117683413abb131dcbe1
`2de87c5
`
`RO/101 - Request form for new IA -
`Conventional
`
`S-0039PCT-RO-101.pdf
`
`PCT-Transmittal Letter
`
`$-0039PCT-PTO-1382.pdf
`
`271086
`
`5c747bt9e6006701 7073b92c4t6d2a1 4
`Sec27c74
`
`105350
`
`42a5e375c3c54725e29049bad033d3a
`75aabeose
`
`Fee payment- International
`Application
`
`S-0039PCT-Fee.pdf
`
`ade90ee7e547310066ffct3deb25idéttd4
`4260b
`
`Fee Worksheet (PTO-06)
`
`fee-info.padf
`
`6e4c8ec55b1€77e5684a29791 2a929c
`
`File Listing:
`
`Document
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Information:
`
`Warnings:
`
`Information:
`
`Warnings:
`
`Information:
`
`Page 5 of 369
`
`Page 5 of 369
`
`
`
`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
`shownonthis AcknowledgementReceiptwill 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.
`
`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.
`
`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
`componentsfor an internationalfiling date (see PCT Article 11 and MPEP 1810), a Notification of the
`International Application Number andof 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
`
`Page 6 of 369
`
`Page 6 of 369
`
`
`
`$-0039 PCT
`
`FULLY CONNECTED GENERALIZED MULTI-LINK 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/940, 389
`
`entitled "FULLY CONNECTED GENERALIZED REARRANGEABLY
`
`NONBLOCKING MULTI-LINK MULTI-STAGE NETWORKS"by Venkat Konda
`
`10
`
`assigned to the same assignee as the current application, filed May 25, 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, 392
`
`entitled "FULLY CONNECTED GENERALIZED STRICTLY NONBLOCKING
`
`MULTI-LINK MULTI-STAGE NETWORKS"by Venkat Kondaassigned to the same
`
`15
`
`assignee as the current application, filed concurrently.
`
`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, 391
`
`entitled "FULLY CONNECTED GENERALIZED FOLDED MULTI-STAGE
`
`NETWORKS"by Venkat Konda assigned to the same assignee as the current application,
`
`20
`
`filed concurrently.
`
`This application is related to and incorporates by referencein its entirety the PCT
`
`Application Serial No. PCT /US08/56064 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed March 6, 2008, the U.S. Provisional Patent
`
`25
`
`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
`
`-1-
`
`Page 7 of 369
`
`Page 7 of 369
`
`
`
`$-0039 PCT
`
`the same assignee as the current application, filed March 6, 2007, and the U.S.
`
`Provisional Patent Application Serial No. 60/940, 383 entitled "FULLY CONNECTED
`
`GENERALIZED 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 PCT
`
`Application Docket No. S-0038PCT entitled "FULLY CONNECTED GENERALIZED
`
`BUTTERFLY FAT TREE NETWORKS"by Venkat Kondaassignedto the same
`
`assignee as the current application, filed concurrently, the U.S. Provisional Patent
`
`Application Serial No. 60/940, 387 entitled "FULLY CONNECTED GENERALIZED
`
`10
`
`BUTTERFLY FAT TREE NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed May 25, 2007, and 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 sameassignee as the current application, filed May 25, 2007.
`
`15
`
`This application is related to and incorporates by referencein its entirety the PCT
`
`Application Docket No. $-0045PCTentitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS"by Venkat Kondaassigned to the same
`
`assignee as the current application, filed concurrently, and the U.S. Provisional Patent
`
`Application Serial No. 60/940, 394 entitled "VLSI LAYOUTS OF FULLY
`
`20
`
`CONNECTED GENERALIZED 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.
`
`Provisional Patent Application Serial No. 60/984, 724 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED NETWORKSWITH LOCALITY EXPLOITATION"by Venkat
`
`Kondaassigned to the same assignee as the current application, filed November 2, 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
`
`Konda assigned to the same assigneeas the current application, filed January 1, 2008.
`
`2.
`
`Page 8 of 369
`
`Page 8 of 369
`
`
`
`$-0039 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 369
`
`Page 9 of 369
`
`
`
`$-0039 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 369
`
`Page 10 of 369
`
`
`
`$-0039 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 generalized multi-link multi-stage network comprising (2x logaN )-1 stagesis
`operated in strictly nonblocking mannerforunicast includes an input stage having 7
`
`switches with each of them having d inlet links and 2 xd outgoing links connecting to
`
`second stage switches, an output stage having 7 switches with each of them having d
`
`15
`
`outlet links and 2xd incoming links connecting from switches in the penultimate stage.
`
`The network also has (2xlogiN)-—3 middle stages with each middle stage having -
`
`switches, and each switch in the middle stage has 2d incoming links connecting from
`
`the switches in its immediate preceding stage, and 2xd outgoing links connecting to the
`
`switchesin its immediate succeeding stage. Also the same generalized multi-link multi-
`
`stage network is operated in rearrangeably nonblocking mannerforarbitrary fan-out
`
`multicast and each multicast connection is set up by use of at most two outgoing links
`
`from the input stage switch.
`
`A generalized multi-link multi-stage network comprising (2 xlogaN )-1 stagesis
`
`operated in strictly nonblocking mannerfor multicast includes an input stage having 7
`
`25
`
`switches with each of them having d inlet links and 3x d outgoing links connecting to
`
`5-
`
`Page 11 of 369
`
`Page 11 of 369
`
`
`
`$-0039 PCT
`
`second stage switches, an output stage having “ switches with each of them having d
`
`outlet links and 3x d incoming links connecting from switches in the penultimate stage.
`
`The network also has (2xlogaN)-—3 middle stages with each middle stage having -
`
`switches, and each switch in the middle stage has 3x d incoming links connecting from
`
`the switchesin its immediate preceding stage, and 3xd outgoing links connecting to the
`
`switchesin its immediate succeedingstage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG, 1A is a diagram 100A of an exemplary symmetrical multi-link multi-stage
`
`10
`
`network V,miink (N,d,s) having inverse Benes connection topology of five stages with N =
`
`8, d = 2 and s=2,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 an exemplary symmetrical multi-link multi-stage
`
`15
`
`network V,,,,CN,d,s)
`
`(having a connection topology built using back-to-back Omega
`
`Networks) of five stages with N = 8, d = 2 and s=2, 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 symmetrical multi-link multi-stage
`
`20
`
`network V,,,,,,(N.d,s) having an exemplary connection topology of five stages with N =
`
`8, d = 2 and s=2,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 an exemplary symmetrical multi-link multi-stage
`
`network V__,,,(N,d,s) having an exemplary connection topology of five stages with N =
`
`8, d = 2 and s=2,strictly nonblocking network for unicast connections and rearrangeably
`
`-6-
`
`Page 12 of 369
`
`Page 12 of 369
`
`
`
`$-0039 PCT
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG, 1E is a diagram 100E of an exemplary symmetrical multi-link multi-stage
`
`network V,,,,,(NV.d,s) (having a connection topology called flip network and also known
`
`as inverse shuffle exchange network) of five stages with N = 8, d = 2 and s=2,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 an exemplary symmetrical multi-link multi-stage
`
`network V,,,,,.(N,d,s) having Baseline connection topology of five stages with N = 8, d
`
`10
`
`= 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1G is a diagram 100G of an exemplary symmetrical multi-link multi-stage
`
`network V,,,,,(N.d,s) having an exemplary connection topology offive stages with N =
`
`15
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1H is a diagram 100H of an exemplary symmetrical multi-link multi-stage
`
`network V,,,,.,(N.d,s) having an exemplary connection topology offive stages with N =
`
`20
`
`8, d = 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG, 11 is a diagram 1001 of an exemplary symmetrical multi-link multi-stage
`
`network V,,..(N.d,s) (having a connection topology built using back-to-back Banyan
`
`25
`
`Networks or back-to-back Delta Networks or equivalently back-to-back Butterfly
`
`networks) of five stages with N = 8, d = 2 and s=2,strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`7-
`
`Page 13 of 369
`
`Page 13 of 369
`
`
`
`$-0039 PCT
`
`FIG. 1J is a diagram 100J of an exemplary symmetrical multi-link multi-stage
`
`network V‘ning, d,8) having an exemplary connection topology of five stages with N =
`
`8, d= 2 and s=2, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 1K is a diagram 100K of a general symmetrical multi-link multi-stage
`network Vaine(Nd,s) with (2xlog,N)-1 stages with s=2,
`strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking networkforarbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`10
`
`FIG. 1A1 is a diagram 100A1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,(N,,N,,d,s) having inverse Benes connection topology of five
`
`stages with N; = 8, No = p* N; = 24 where p = 3, d = 2 and s = 2,strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking networkforarbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`15
`
`FIG. 1B1 is a diagram 100B1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,,(N,,N,,d,5) (having a connection topology built using back-to-back
`
`Omega Networks) of five stages with Ni = 8, No = p* Ni = 24 where p= 3, d=2 ands =
`
`2, strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`20
`
`FIG. 1C1 is a diagram 100C1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,,(N,,N,,d,s) having an exemplary connection topology of five
`
`stages with N; = 8, No = p* N; = 24 where p = 3, d = 2 and s = 2,strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking networkforarbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`25
`
`FIG. 1D1 is a diagram 100D1 of an exemplary asymmetrical multi-link multi-
`
`stage network V,,,,,(N,,N,,d,5) having an exemplary connection topology offive stages
`
`with N; = 8, No = p* N; = 24 where p = 3, d = 2 and s = 2,strictly nonblocking network
`
`Page 14 of 369
`
`Page 14 of 369
`
`
`
`$-0039 PCT
`
`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-link multi-
`
`stage network V,,,,,,(N,,N,.d,s) (having a connection topology called flip network and
`
`also knownas inverse shuffle exchange network) of five stages with N; = 8, No = p* Ny
`
`= 24 where p = 3, d = 2 and s = 2,strictly nonblocking network for unicast connections
`
`and rearrangeably nonblocking network for arbitrary fan-out multicast connections, in
`
`accordance with the invention.
`
`FIG, 1F1 is a diagram 100F1 of an exemplary asymmetrical multi-link multi-stage
`
`10
`
`network V,,,,,(N,.N,,d,5) having Baseline connection topology offive stages with N; =
`
`8, No = p* N; = 24 where p = 3, d= 2 ands = 2,strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections, in accordance with the invention.
`
`FIG. 1G1 is a diagram 100G1 of an exemplary asymmetrical multi-link multi-
`
`15
`
`stage network V,ming (N»N>,d,5) having an exemplary connection topology of five
`
`stages with N; = 8, No = p* N; = 24 where p = 3, d = 2 and s = 2,strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1H1 is a diagram 100H1 of an exemplary asymmetrical multi-link multi-
`stage network V,7HtingN|,N,,d,5) having an exemplary connection topology of five
`
`20
`
`stages with N; = 8, N> = p* N; = 24 where p = 3, d = 2 and s = 2,strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG, 111 is a diagram 10011 of an exemplary asymmetrical multi-link multi-stage
`
`25
`
`network V,,..(N,,N,,d,8)
`
`(having a connection topology built using back-to-back
`
`Banyan Networksor back-to-back Delta Networks or equivalently back-to-back Butterfly
`
`networks) of five stages with N; = 8, No = p* N; = 24 where p = 3, d = 2 ands = 2,
`
`Page 15 of 369
`
`Page 15 of 369
`
`
`
`$-0039 PCT
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG, 1J1 is a diagram 100J1 of an exemplary asymmetrical multi-link multi-stage
`
`network V,,,,,(N,,N,.d,s) having an exemplary connection topology of five stages with
`
`N, =8, No = p* Ni = 24 where p = 3, d=2and s = 2, strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`FIG. 1K1 is a diagram 100K1 of a general asymmetrical multi-link multi-stage
`network V,,,,(N,,N,,d,s) with (2xlog, N)-1 stages with N; = p* No and s = 2,
`
`10
`
`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 asymmetrical multi-link multi-
`
`stage network V,,,,.(N,,N,,d,8) having inverse Benes connection topology of five
`
`stages with N. = 8, N; = p* No. = 24, where p = 3, d =2 and s = 2,strictly nonblocking
`
`15
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1B2 is a diagram 100B2 of an exemplary asymmetrical multi-link multi-
`
`lin
`stage network V,,,,,(N,,N,,d,s) (having a connection topology built using back-to-back
`
`Omega Networks) of five stages with Nz = 8, N,; = p* N.= 24, where p=3,d=2 ands
`
`20
`
`= 2, strictly nonblocking network for unicast 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-link multi-
`
`stage network V_,,,(N,,N,,d,s) having an exemplary connection topology of five
`
`stages with N. = 8, N; = p* Ny = 24, where p = 3, d =2 and s = 2,strictly nonblocking
`
`25
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`-10-
`
`Page 16 of 369
`
`Page 16 of 369
`
`
`
`$-0039 PCT
`
`FIG, 1D2 is a diagram 100D2 of an exemplary asymmetrical multi-link multi-
`
`lin
`stage network V__,,,,(N,,N,,d,s) having an exemplary connection topology of five stages
`
`with No = 8, N; = p* No= 24, where p =3, d=2 and s = 2, 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-link multi-
`
`stage network V,,,,,,(N,,N,,d,5) (having a connection topology called flip network and
`
`also knownas inverse shuffle exchange network) of five stages with No = 8, N; = p* No
`
`= 24, where p = 3, d= 2 and s = 2,strictly nonblocking network for unicast connections
`
`10
`
`and rearrangeably nonblocking network for arbitrary fan-out multicast connections, in
`
`accordance with the invention.
`
`FIG. 1F2 is a diagram 100F2 of an exemplary asymmetrical multi-link multi-stage
`
`network V,,,,.(N,,N>,d,5) having Baseline connection topologyof five stages with N> =
`
`8, N; = p* No= 24, where p = 3, d = 2 and s = 2,strictly nonblocking network for
`
`15
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`FIG. 1G2 is a diagram 100G2 of an exemplary asymmetrical multi-link multi-
`
`stage network V_,,,(N,,N,,d,s) having an exemplary connection topology of five
`
`stages with N. = 8, N; = p* N= 24, where p = 3, d = 2 ands= 2,strictly nonblocking
`
`20
`
`network for unicast connections and rearrangeably nonblocking network forarbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1H2 is a diagram 100H2 of an exemplary asymmetrical multi-link multi-
`
`lin
`stage network V__,,,(N,,N,,d,s) having an exemplary connection topology of five stages
`
`with No = 8, N; = p* No= 24, where p = 3, d=2 ands = 2, strictly nonblocking network
`
`25
`
`for unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`-11-
`
`Page 17 of 369
`
`Page 17 of 369
`
`
`
`$-0039 PCT
`
`FIG, 1f2 is a diagram 10012 of an exemplary asymmetrical multi-link multi-stage
`
`network VnineN,,N,,d,8)
`
`(having a connection topology built using back-to-back
`
`Banyan Networks or back-to-back Delta Networks or equivalently back-to-back Butterfly
`
`networks) of five stages with No = 8, N; = p* No = 24, where p =3,d =2 ands =2,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG, 1J2 is a diagram 100J2 of an exemplary asymmetrical multi-link multi-stage
`
`network V,,,,,(N,,N,,d,s) having an exemplary connection topology offive stages with
`
`N2=8, Ni; = p* No= 24, where p = 3, d= 2 ands= 2,strictly nonblocking network for
`
`10
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`FIG. 1K2 is a diagram 100K2 of a general asymmetrical multi-link multi-stage
`network V,,,,(N,,N,,d,s) with (2xlog, N)-1 stages with N. = p* N; and s = 2,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`15
`
`networkfor arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 2A is a diagram 200A of an exemplary symmetrical folded multi-link multi-
`
`stage network Voinine(N,d, 5) having inverse Benes connectiontopologyof five stages
`
`with N = 8, d = 2 and s=2 with exemplary multicast connections, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking networkforarbitrary fan-
`
`20
`
`out multicast connections, in accordance with the invention.
`
`FIG. 2B is a diagram 200B of a general symmetrical folded multi-link multi-stage
`network Vijmine (N,d,2) with (2x logaN)-1 stages strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`multicast connections in accordance with the invention.
`
`25
`
`FIG, 2C is a diagram 200C of an exemplary asymmetrical folded multi-link multi-
`stage network V,0.ld—mlineN,,N.,d,2