PTO—1382 (Revi 11-2007)
`Approved for use through 02/28/20l0. OMB 0651-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: 5/22/2008
`
`File reference “0,; 8-0039 PCT
`
`lntemational application no. (if known):
`
`Customer Number]: 38139
`
`Earliest priority date claimed (Day/Month/Year): 5/25/2007
`
`Title of the invention: Fully Connected Generalized Multi-Link Multi-Stage Networks
`
`1 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 may or may not be claimed on the
`Request (form PCT/RO/I 0/) and this listing does not constitute a claim for priority.)
`
`
`Nenkat Konda/
`
`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
`[j MIGHT BE CONSIDERED TO ALTER the general nature ofthe
`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. l8l and 37 CPR. 5.15.
`Itemized list of contents
`
`.
`Sheets of description
`(excluding sequence listing): 211
`
`_
`Return receipt postcard:
`
`Sheets of abstract: 1
`
`Certified COPY of priority
`document (specrfy):
`
`The person
`signing, this
`form is:
`
`Applicant
`
`Venkat Konda
`
`[I Anomey/Agent (Reg. No.)
`
`Name orperson signing
`
`Signature
`E] Common Representative
`This collection of information is required by 37 CFR HO and l.4l2. 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 governed by 35 USC. 122 and 37 CFR H l and 1.14. This collection is estimated to take l5 minutes to complete,
`including gathering information, preparing, and submitting the completed form 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 Information Officer, US. Patent and Trademark
`Office, US. Department ofCommerce, PO Box I450, Alexandria, VA 223l3-I450. DO NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS.
`SEND TO: Mail Stop PCT. Commissioner for Patents, P.0. Box I450, Alexandria, VA 223lJ-l450.
`
`Page 1 of 369
`
`FLEX LOGIX EXHIBIT 1020
`
`Page I of I
`
`
`
`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
`
`Venkar Konda
`
`Attorney Docket Number:
`
`8-0039PCT
`
`International Application for filing in the US receiving office Filing Fees
`
`13mm
`
`Basic Filing:
`
`
`
`
`
`
`
`1 300Transmittal fee 300
`
`
`
`PCT Search Fee- no prior US appl filed
`
`lntl Filing Fee (1st-30 Pgs.) PCT Easy
`
`Suppl. lntl Filing Fee (each page > 30)
`
`1701
`
`1703
`
`320
`
`1173
`
`14
`
`1173
`
`4480
`
`Miscellaneous-Filing:
`
`Page 2 of 369
`
`Page 2 of 369
`
`

`

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

`

`Electronic Acknowledgement Receipt
`
`“—
`——
`
`
`
`International Application Number: PCT/U808/64604
`
`Confirmation Number:
`
`5419
`
`Title of Invention:
`
`FULLY CONNECTED GENERALIZED MULTI-LINK 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: 22-MAY-2008
`
`Filing Date:
`
`Time Stamp:
`
`23:42:21
`
`Application Type:
`
`International Application for filing in the US receiving office
`
`Payment information:
`
`Page 4 of 369
`
`Page 4 of 369
`
`

`

`File Listing:
`
`Document
`
`Number
`
`Document Description m /Message Digest Part/.zip (it appl.)
`
`.
`
`.
`
`File Size(Bytes)
`
`Multi
`
`Pages
`
`Specification
`
`8-0039PCT.pdf
`
`1016396
`
`I551 548becc512de4all267231 b6ldleda
`4a6d12
`
`S-OOSQPCT-FIGspdf
`
`b1331a7239e79l17683413abb1 31d0be1
`2de8705
`
`901693
`
`FIG/101 - Request form for new IA -
`Conventional
`
`S-OOSQPCT-RO-101pdf
`
`50747b19660067017073b920416d2314
`50027074
`
`271086
`
`PCT-Transmittal Letter
`
`S-OOSQPCT-PTO-1382pdf
`
`105350
`
`4255837503054725829049bad033d3a
`7Saabe99e
`
`Fee payment - International
`Application
`
`S-OOSQPCT-Feepdf
`
`ade90ee7e547310066flcl3deb251d6lld4
`4260b
`
`Fee Worksheet (PTO-06)
`
`fee-info.pdf
`
`6&4086055b1e7755684a29791239290
`546772d05
`
`I
`I
`I
`Drawmgs-only black and white line
`rawmgs
`d
`.
`
`Information:
`
`Information:
`
`Warnings:
`
`Information
`
`Information:
`
`Warnings:
`
`Information:
`
`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 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.
`
`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.
`
`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
`
`Page 6 of 369
`
`Page 6 of 369
`
`

`

`5-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 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 application, filed May 25, 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, 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 concurrently.
`
`10
`
`15
`
`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, 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 reference in its entirety the PCT
`
`Application Serial No. PCT / U808 / 56064 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed March 6, 2008, the US. 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
`
`

`

`5-0039 PCT
`
`the same assignee as the current application, filed March 6, 2007, and 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 PCT
`
`Application Docket No. S-0038PCT entitled "FULLY CONNECTED GENERALIZED
`
`BUTTERFLY FAT TREE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed concurrently, 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, and 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 PCT
`
`Application Docket No. S-0045PCT entitled "VLSI LAYOUTS OF FULLY
`
`CONNECTED GENERALIZED NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed concurrently, and 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..
`
`10
`
`15
`
`20
`
`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.
`
`_2_
`
`Page 8 of 369
`
`Page 8 of 369
`
`

`

`5-0039 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 369
`
`Page 9 of 369
`
`

`

`5-0039 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 369
`
`Page 10 of 369
`
`

`

`5-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
`
`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 generalized multi-link multi-stage network comprising (2 X log d N) —1 stages is
`
`operated in strictly nonblocking manner for unicast 1ncludes an input stage hav1ng —
`d
`
`switches with each of them having d inlet links and 2 X d outgoing links connecting to
`
`N
`second stage switches, an output stage having — switches with each of them having d
`d
`
`15
`
`outlet links and 2X (1 incoming links connecting from switches in the penultimate stage.
`
`The network also has (2Xlogd N) — 3 middle stages with each middle stage having E
`d
`
`switches, and each switch in the middle stage has 2X d incoming links connecting from
`
`the switches in its immediate preceding stage, and 2X d outgoing links connecting to the
`
`switches in its immediate succeeding stage. Also the same generalized multi-link multi-
`
`stage network is operated in rearrangeably nonblocking manner for arbitrary fan-out
`
`multicast and each multicast connection is set up by use of at most two outgoing links
`
`from the input stage switch.
`
`A generalized multi-link multi-stage network comprising (2 X log d N ) — 1 stages is
`
`N
`operated in strictly nonblocking manner for multicast includes an input stage having —
`d
`
`25
`
`switches with each of them having d inlet links and 3 X Li outgoing links connecting to
`
`_5_
`
`Page 11 of 369
`
`Page 11 of 369
`
`

`

`5-0039 PCT
`
`N
`second stage switches, an output stage having — switches with each of them having d
`d
`
`outlet links and 3 X (l incoming links connecting from switches in the penultimate stage.
`
`The network also has (2Xlogd N) — 3 middle stages with each middle stage having Ed,
`
`switches, and each switch in the middle stage has 3x (I incoming links connecting from
`
`the switches in its immediate preceding stage, and 3Xd outgoing links connecting to the
`
`switches in its immediate succeeding stage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi-link multi-stage
`
`10
`
`network Vmlink (N, (I, 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.
`
`15
`
`20
`
`FIG. 1B is a diagram 100B of an exemplary symmetrical multi-link multi-stage
`
`network leink (N ,d ,5)
`
`(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
`
`network lemk (N, d, 5) 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 lemk (N, d, 5) 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
`
`

`

`5-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 Vka (N, d, 5) (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 leink(N, d, 5) having Baseline 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. 1G is a diagram 100G of an exemplary symmetrical multi-link multi-stage
`
`m
`network V M (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. 1H is a diagram 100H of an exemplary symmetrical multi-link multi-stage
`
`network lemk(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. 11 is a diagram 1001 of an exemplary symmetrical multi-link multi-stage
`
`network leink(N,d,s) (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 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_
`
`10
`
`15
`
`20
`
`25
`
`Page 13 of 369
`
`Page 13 of 369
`
`

`

`5-0039 PCT
`
`FIG. 1] is a diagram 100J of an exemplary symmetrical multi-link multi-stage
`
`network leink (N, d, 5) 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 Vmlink (N,d,s) with (2Xlog d N )—1
`
`stages with s=2,
`
`strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 1A1 is a diagram 100A1 of an exemplary asymmetrical multi-link multi-
`
`stage network leink (N1,N2,d,s) having inverse Benes connection topology of five
`
`stages with N1 = 8, N2 = p"< N1 = 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. 1B1 is a diagram lOOBl of an exemplary asymmetrical multi—link multi—
`
`stage network leink (N1 , N2, d , 5) (having a connection topology built using back-to-back
`
`Omega Networks) of five stages with N1 = 8, N2 = p* N1 = 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. 1C1 is a diagram lOOCl of an exemplary asymmetrical multi—link multi—
`
`stage network lemk (N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N1 = 8, N2 = p"< N1 = 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. lDl is a diagram 100D1 of an exemplary asymmetrical multi—link multi—
`
`stage network leink (N1 , N2, d , 5) having an exemplary connection topology of five stages
`
`with N1 = 8, N2 = p* N1 = 24 where p = 3, d = 2 and s = 2, strictly nonblocking network
`
`10
`
`15
`
`20
`
`25
`
`Page 14 of 369
`
`Page 14 of 369
`
`

`

`5-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 thnk(N1,N2,d, s) (having a connection topology called flip network and
`
`also known as inverse shuffle exchange network) of five stages with N1 = 8, N2 = p* N1
`
`= 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 ‘lmlink (N1 , N2, d , 5) having Baseline connection topology of five stages with N1 =
`
`8, N2 = p* N1 = 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. 1G1 is a diagram 100G1 of an exemplary asymmetrical multi-link multi-
`
`15
`
`stage network Vmlin
`
`k(N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N1 = 8, N2 = p"< N1 = 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-
`
`20
`
`m
`stage network V
`
`M (N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N1 = 8, N2 = p"< N1 = 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 leink(Nl,N2,d,s)
`
`(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 N1 = 8, N2 = p* N1 = 24 where p = 3, d = 2 and s = 2,
`
`Page 15 of 369
`
`Page 15 of 369
`
`

`

`5-0039 PCT
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1] 1 is a diagram 100J1 of an exemplary asymmetrical multi-link multi-stage
`
`network lemk(N1,N2,d, 5) having an exemplary connection topology of five stages with
`
`N1 = 8, N2 = p* N1 = 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. 1K1 is a diagram 100K1 of a general asymmetrical multi-link multi-stage
`
`network leink(N1,N2,d,s) with (2Xlogd N)—1 stages with N1 = p* N2 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. 1A2 is a diagram 100A2 of an exemplary asymmetrical multi-link multi-
`
`stage network lemk(N1,N2,d,s) having inverse Benes connection topology of five
`
`stages with N2 = 8, N1 = p* N2 = 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. 1B2 is a diagram 100B2 of an exemplary asymmetrical multi-link multi-
`
`[in
`stage network Vm k (N1 , N2, d , 3) (having a connection topology built using back-to-back
`
`Omega Networks) of five stages with N2 = 8, N1 = p* N2 = 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. 1C2 is a diagram 100C2 of an exemplary asymmetrical multi-link multi-
`
`stage network lemk (Nl,N2,d,s) having an exemplary connection topology of five
`
`stages with N2 = 8, N1 = p* N2 = 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.
`
`10
`
`15
`
`20
`
`25
`
`_10_
`
`Page 16 of 369
`
`Page 16 of 369
`
`

`

`5-0039 PCT
`
`FIG. 1D2 is a diagram 100D2 of an exemplary asymmetrical multi-link multi-
`
`[in
`stage network Vm k (N1,N2, d , s) having an exemplary connection topology of five stages
`
`with N2 = 8, N1 = p* N2 = 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. IE2 is a diagram 100E2 of an exemplary asymmetrical multi-link multi-
`
`stage network lemk(N1,N2,d, 5) (having a connection topology called flip network and
`
`also known as inverse shuffle exchange network) of five stages with N2 = 8, N1 = p* N2
`
`= 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. 1F2 is a diagram 100F2 of an exemplary asymmetrical multi-link multi-stage
`
`network leink (N1 , N2, d , s) having Baseline connection topology of five stages with N2 =
`
`8, N1 = p* N2 = 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. 1G2 is a diagram 100G2 of an exemplary asymmetrical multi-link multi-
`
`stage network lemk (N1,N2,d,s) having an exemplary connection topology of five
`
`stages with N2 = 8, N1 = p* N2 = 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. 1H2 is a diagram 100H2 of an exemplary asymmetrical multi-link multi-
`
`[in
`stage network Vm k (N1,N2, d , 5) having an exemplary connection topology of five stages
`
`with N2 = 8, N1 = p* N2 = 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.
`
`10
`
`15
`
`20
`
`25
`
`-11-
`
`Page 17 of 369
`
`Page 17 of 369
`
`

`

`5-0039 PCT
`
`FIG. 112 is a diagram 10012 of an exemplary asymmetrical multi-link multi-stage
`
`network Vmlink(N1,N2,d,s)
`
`(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 N2 = 8, N1 = p* N2 = 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. 1J2 is a diagram 100J2 of an exemplary asymmetrical multi-link multi-stage
`
`network leink(N1,N2,d, s) having an exemplary connection topology of five stages with
`
`N2 = 8, N1 = 13* N2 = 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. 1K2 is a diagram 100K2 of a general asymmetrical multi-link multi-stage
`
`network leink(N1,N2,d,s) with (2Xlogd N)—1 stages with N2 = p* N1 and s = 2,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`10
`
`15
`
`FIG. 2A is a diagram 200A of an exemplary symmetrical folded multi-link multi-
`
`stage network Vfoldimlink (N, d, 5) having inverse Benes connection topology of five stages
`
`with N = 8, d = 2 and s=2 with exemplary multicast connections, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`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 an,d_mh.nk (N,d ,2) with (2Xlog,1 N )—1 stages strictly nonblocking network for
`
`unicast connections and rearrangeably nonblocking network for arbitrary fan-out
`
`mu