Electronic Patent Application Fee Transmittal
`——
`
`Filing Date:
`
`Title of Invention:
`
`FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE
`NETWORKS
`
`First Named Inventor/Applicant Name:
`
`Venkat Konda
`
`Venkar Konda
`
`Attorney Docket Number:
`
`S-OO38PCT
`
`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
`
`88
`
`14
`
`1173
`
`1232
`
`Miscellaneous-Filing:
`
`Page 1 of 164
`
`FLEX LOGIX EXHIBIT 1016
`
`Page 1 of 164
`
`FLEX LOGIX EXHIBIT 1016
`
`

`

`Post-AIIowance-andPost-Issuance:
`
`Extension-of-Time:
`
`Patent-Appeals-and-lnterference:
`
`4505
`
`Total in USD ($)
`
`Page 2 of 164
`
`Page 2 of 164
`
`

`

`Electronic Acknowledgement Receipt
`
`“—
`——
`
`
`
`International Application Number: PCT/U808/64603
`
`Confirmation Number:
`
`5415
`
`Title of Invention:
`
`FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE
`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:32:34
`
`Application Type:
`
`International Application for filing in the US receiving office
`
`Payment information:
`
`Page 3 of 164
`
`Page 3 of 164
`
`

`

`File Listing:
`
`Document
`
`Number
`
`Document Description m /Message Digest Part/.zip (it appl.)
`
`.
`
`.
`
`File Size(Bytes)
`
`Multi
`
`Pages
`
`Specification
`
`8-0038PCT.pdf
`
`455158
`
`c246882dlca0a5ac717689ie35cbcee7d
`49d1 63d
`
`S-OOSSPCT-FIGspdf
`
`436121164004500089575174911eaBSIOd4
`2ala9e
`
`219915
`
`PCT-Transmittal Letter
`
`S-OOSSPCT-PTO-1382.pdf
`
`513587
`
`57406034884eebdeb5466194d764bcec
`818e9c80
`
`FIG/101 - Request form for new IA -
`Conventional
`
`8-0038PCT-R0-101 .pdf
`
`55lo440b99149956009454Iel2d071225
`SebaSOE
`
`267730
`
`I
`Fee payment - International
`Application
`
`8-0038PCT-Fee.pdf
`
`1850b84Beb49552820d301bb756803b0
`21 263069
`
`356132
`
`Fee Worksheet (PTO-06)
`
`fee-info.pdf
`
`2965a4469b9127360200933776Cd2b8
`169e4ce5d
`
`I
`I
`I
`Drawmgs-only black and white line
`rawmgs
`d
`.
`
`Information:
`
`Information:
`
`Warnings:
`
`Information
`
`Information:
`
`Warnings
`
`Information:
`
`Information:
`
`Page 4 of 164
`
`Page 4 of 164
`
`

`

`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 5 of 164
`
`Page 5 of 164
`
`

`

`5-0038 PCT
`
`FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE 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, 387
`
`entitled "FULLY CONNECTED GENERALIZED BUTTERFLY FAT TREE
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`10
`
`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, 390
`
`entitled "FULLY CONNECTED GENERALIZED MULTI-LINK BUTTERFLY FAT
`
`TREE NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`15
`
`application, filed May 25, 2007.
`
`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
`
`Application Serial No. 60 / 905,526 entitled ”LARGE SCALE CROSSPOINT
`
`REDUCTION WITH NONBLOCKING UNICAST & MULTICAST IN
`
`ARBITRARILY LARGE MULTI-STAGE NETWORKS" by Venkat Konda assigned to
`
`the same assignee as the current application, filed March 6, 2007, 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.
`
`20
`
`25
`
`Page 6 of 164
`
`Page 6 of 164
`
`

`

`5-0038 PCT
`
`This application is related to and incorporates by reference in its entirety the PCT
`
`Application Docket N o. S-0039PCT entitled "FULLY CONNECTED GENERALIZED
`
`MULTI—LINK MULTl-STAGE NETWORKS" by Venkat Konda assigned to the same
`
`assignee as the current application, filed concurrently, 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, the US. Provisional Patent Application Serial No. 60 / 940, 391 entitled "FULLY
`
`CONNECTED GENERALIZED FOLDED MULTI-STAGE NETWORKS" by Venkat
`
`Konda assigned to the same assignee as the current application, filed May 25, 2007 and
`
`the US. Provisional Patent Application Serial No. 60 / 940, 392 entitled "FULLY
`
`CONNECTED GENERALIZED STRICTLY NONBLOCKING MULTI-LINK MULTI-
`
`STAGE NETWORKS" by Venkat Konda assigned to the same assignee as the current
`
`application, filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the 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.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Serial No. 60 / 984, 724 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED NETWORKS WITH LOCALITY EXPLOITATION" by Venkat
`
`Konda assigned to the same assignee as the current application, filed November 2, 2007.
`
`This application is related to and incorporates by reference in its entirety the US.
`
`Provisional Patent Application Serial No. 61/018, 494 entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED AND PYRAMID NETWORKS" by Venkat
`
`Konda assigned to the same assignee as the current application, filed January 1, 2008.
`
`10
`
`15
`
`20
`
`25
`
`-2-
`
`Page 7 of 164
`
`Page 7 of 164
`
`

`

`5-0038 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 8 of 164
`
`Page 8 of 164
`
`

`

`5-0038 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 9 of 164
`
`Page 9 of 164
`
`

`

`5-0038 PCT
`
`demultiplexers. Jonathan Turner studied the cascaded Benes Networks with radices larger
`
`than two, for nonblocking multicast with 10 times the crosspoint complexity of that of
`
`nonblocking unicast for a network of size N2256.
`
`The crosspoint complexity of all these networks is prohibitively large to
`
`implement the interconnect for multicast connections particularly in field programmable
`
`gate array (FPGA) devices, programmable logic devices (PLDs), field programmable
`
`interconnect Chips (FPICs), digital crossconnects, switch fabrics and parallel computer
`
`systems.
`
`10
`
`SUMMARY OF INVENTION
`
`A generalized butterfly fat tree network comprising (log, N ) stages is operated in
`
`strictly nonblocking manner for unicast includes a leaf stage consisting of an input stage
`
`having fl switches with each of them having d inlet links and 2X d outgoing links
`d
`
`N
`connecting to its immediate succeeding stage switches, and an output stage having —
`d
`
`switches with each of them having d outlet links and 2X cl incoming links connecting
`
`from switches in its immediate succeeding stage. The network also has (log d N ) —1
`
`middle stages with each middle stage, excepting the root stage, having
`
`
`2xN
`
`d
`
`switches,
`
`and each switch in the middle stage has d incoming links connecting from the switches
`
`in its immediate preceding stage, cl incoming links connecting from the switches in its
`
`immediate succeeding stage, d outgoing links connecting to the switches in its
`
`immediate succeeding stage, d outgoing links connecting to the switches in its
`2xN
`
`immediate preceding stage, and the root stage having
`
`switches, and each switch in
`
`the middle stage has d incoming links connecting from the switches in its immediate
`
`preceding stage and d outgoing links connecting to the switches in its immediate
`
`preceding stage. Also the same generalized butterfly fat tree network is operated in
`
`15
`
`20
`
`25
`
`-5-
`
`Page 10 of 164
`
`Page 10 of 164
`
`

`

`5-0038 PCT
`
`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 butterfly fat tree network comprising (log d N ) stages is operated in
`
`strictly nonblocking manner for multicast includes a leaf stage consisting of an input
`
`stage having l switches with each of them having d inlet links and 3 X d outgoing links
`d
`
`connecting to its immediate succeeding stage sw1tches, an output stage hav1ng —
`d
`
`switches with each of them having (I outlet links and 3 X d incoming links connecting
`
`from switches in its immediate succeeding stage. The network also has (log, N) —1
`
`switches,
`
`d
`
`3><N
`
`middle stages with each middle stage, excepting the root stage, having
`
`and each switch in the middle stage has (I, incoming links connecting from the switches
`
`in its immediate preceding stage, (I incoming links connecting from the switches in its
`
`immediate succeeding stage, (l outgoing links connecting to the switches in its
`
`immediate succeeding stage, (I outgoing links connecting to the switches in its
`
`immediate preceding stage, and the root stage having
`
`
`3><N
`
`d
`
`switches, and each switch in
`
`the middle stage has d incoming links connecting from the switches in its immediate
`
`preceding stage and cl outgoing links connecting to the switches in its immediate
`
`preceding stage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary Symmetrical Butterfly fat
`
`tree
`
`network Vbfl (N, d, 5) having inverse Benes connection topology of three 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.
`
`10
`
`15
`
`20
`
`Page 11 of 164
`
`Page 11 of 164
`
`

`

`5-0038 PCT
`
`FIG. 1B is a diagram 100B of a general symmetrical Butterfly fat tree network
`
`Vbfl (N ,d ,s) with (log d N) stages strictly nonblocking network for unicast connections
`
`and rearrangeably nonblocking network for arbitrary fan-out multicast connections in
`
`accordance with the invention.
`
`FIG. 1C is a diagram 100C of an exemplary Asymmetrical Butterfly fat tree
`
`network Vbfl (N1,N2,d ,2) having inverse Benes connection topology of three stages with
`
`N1 = 8, N2 = p* N1 = 24 where p = 3, and d = 2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1D is a diagram 100D of a general asymmetrical Butterfly fat tree network
`
`Vbfl (N1,N2,d,2) with N2 = p* N1 and with (log d N) stages 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 100E of an exemplary Asymmetrical Butterfly fat tree
`
`network Vbfl (N1,N2,d ,2) having inverse Benes connection topology of three stages with
`
`N2 = 8, N1 = p* N2 = 24, where p = 3, and d = 2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast connections and rearrangeably nonblocking
`
`network for arbitrary fan—out multicast connections, in accordance with the invention.
`
`FIG. 1F is a diagram 100F of a general asymmetrical Butterfly fat tree network
`
`Vbfl (N1, N2,d ,2) with N1 = p* N2 and with (log, N ) stages 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 Butterfly fat
`
`tree
`
`network Vbfl (N, d, 5) having inverse Benes connection topology of three stages with N =
`
`8, d = 2 and s=1 with exemplary unicast connections rearrangeably nonblocking network
`
`for unicast connections, in accordance with the invention.
`
`10
`
`15
`
`20
`
`25
`
`Page 12 of 164
`
`Page 12 of 164
`
`

`

`5-0038 PCT
`
`FIG. 2B is a diagram 200B of a general symmetrical Butterfly fat tree network
`
`Vbfi(N,d,s) with (log d N ) stages and s=1, rearrangeably nonblocking network for
`
`unicast connections in accordance with the invention.
`
`FIG. 2C is a diagram 200C of an exemplary Asymmetrical Butterfly fat tree
`
`network Vbfl (N1,N2,d,1) having inverse Benes connection topology of three stages with
`
`N1 = 8, N2 = p* N1 = 24 where p = 3, and d = 2 with exemplary unicast connections
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`FIG. 2D is a diagram 200D of a general asymmetrical Butterfly fat tree network
`
`Vbfi (N1,N2,0! ,1) with N2 = p* N1 and with (log d N ) stages rearrangeably nonblocking
`
`network for unicast connections in accordance with the invention.
`
`FIG. 2E is a diagram 200E of an exemplary Asymmetrical Butterfly fat tree
`
`network Vbfl (N1,N2,d,l) having inverse Benes connection topology of three stages with
`
`N2 = 8, N1 = p"< N2 = 24, where p = 3, and d = 2 with exemplary unicast connections
`
`rearrangeably nonblocking network for unicast connections,
`
`in accordance with the
`
`invention.
`
`FIG. 2F is a diagram 200F of a general asymmetrical Butterfly fat tree network
`
`Vbfi (N1,N2,d ,1) with N1 = p* N2 and with (logd N) stages rearrangeably nonblocking
`
`network for unicast connections in accordance with the invention.
`
`FIG. 3A is a diagram 300A of an exemplary symmetrical multi—link Butterfly fat
`
`tree network thnkibfi (N ,d ,5) having inverse Benes connection topology of five stages
`
`with N = 8, d = 2 and s=2 with exemplary multicast connections, strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 3B is a diagram 300B of a general symmetrical multi-link Butterfly fat tree
`
`network leink_bfi (N,d ,2) with (log, N) stages strictly nonblocking network for unicast
`
`10
`
`15
`
`20
`
`25
`
`_3_
`
`Page 13 of 164
`
`Page 13 of 164
`
`

`

`S-0038 PCT
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections in accordance with the invention.
`
`FIG. 3C is a diagram 300C of an exemplary asymmetrical multi-link Butterfly fat
`
`tree network leink—bft (N1,N2,d ,2) having inverse Benes connection topology of five
`
`stages with N1 = 8, N2 = p* N1 = 24 where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 3D is a diagram 300D of a general asymmetrical multi-link Butterfly fat tree
`
`network lemk_bfi(N1,N2,d,2) with N2 = p* N1 and with (log, N) stages strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`FIG. 3E is a diagram 300E of an exemplary asymmetrical multi-link Butterfly fat
`
`tree network leink_bfi (N1,N2,d ,2) having inverse Benes connection topology of five
`
`stages with N2 = 8, N1 = p* N2 = 24, where p = 3, and d = 2 with exemplary multicast
`
`connections, strictly nonblocking network for unicast connections and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 3F is a diagram 300F of a general asymmetrical multi-link Butterfly fat tree
`
`network leink_bfi (N1,N2 ,d ,2) with N1 = pi< N2 and with (log, N) stages strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections in accordance with the invention.
`
`10
`
`15
`
`20
`
`FIG. 4A 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
`
`25
`
`invention.
`
`FIG. 5A1 is a diagram 500Al of an exemplary prior art implementation of a two
`
`by two switch; FIG. 5A2 is a diagram 500A2 for programmable integrated circuit prior
`
`_9_
`
`Page 14 of 164
`
`Page 14 of 164
`
`

`

`5-0038 PCT
`
`art implementation of the diagram 500Al of FIG. 5A1; FIG. 5A3 is a diagram 500A3 for
`
`one-time programmable integrated circuit prior art implementation of the diagram 500Al
`
`of FIG. 5A]; FIG. 5A4 is a diagram 500A4 for integrated circuit placement and route
`
`implementation of the diagram 500A] of FIG. 5A].
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention is concerned with the design and operation of large scale
`
`crosspoint reduction using arbitrarily large Butterfly fat tree networks and Multi-link
`
`Butterfly fat tree networks for broadcast, unicast and multicast connections. Particularly
`
`Butterfly fat tree networks and Multi-link Butterfly fat tree networks with stages more
`
`than or equal to three and radices greater than or equal to two offer large scale crosspoint
`
`reduction when configured with optimal links as disclosed in this invention.
`
`When a transmitting device simultaneously sends information to more than one
`
`receiving device, the one-to-many connection required between the transmitting device
`
`and the receiving devices is called a multicast connection. A set of multicast connections
`
`is referred to as a multicast assignment. When a transmitting device sends information to
`
`one receiving device, the one-to-one connection required between the transmitting device
`
`and the receiving device is called unicast connection. When a transmitting device
`
`simultaneously sends information to all the available receiving devices, the one-to-all
`
`connection required between the transmitting device and the receiving devices is called a
`
`broadcast connection.
`
`10
`
`15
`
`‘20
`
`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
`
`25
`
`of the available outlet links.
`
`In certain butterfly fat tree networks and multi-link butterfly fat tree networks of
`
`the type described herein, any connection request of arbitrary fan-out, i.e. from an inlet
`
`link to an outlet link or to a set of outlet links of the network, can be satisfied without
`
`_10_
`
`Page 15 of 164
`
`Page 15 of 164
`
`

`

`5-0038 PCT
`
`blocking if necessary by rearranging some of the previous connection requests. In certain
`
`other Butterfly fat tree networks of the type described herein, any connection request of
`
`arbitrary fan-out, i.e. from an inlet link to an outlet link or to a set of outlet links of the
`
`network, can be satisfied without blocking with never needing to rearrange any of the
`
`previous connection requests.
`
`In certain butterfly fat tree networks and multi-link butterfly fat tree networks of
`
`the type described herein, any connection request of unicast from an inlet link to an outlet
`
`link of the network, can be satisfied without blocking if necessary by rearranging some of
`
`the previous connection requests. In certain other Butterfly fat tree networks of the type
`
`described herein, any connection request of unicast from an inlet link to an outlet link of
`
`the network, can be satisfied without blocking with never needing to rearrange any of the
`
`previous connection requests.
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized multi-stage networks V(N1 , N2 , d, s) with numerous connection
`
`topologies and the scheduling methods are described in detail in the PCT Application
`
`Serial No. PCT / U808 / 56064 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
`
`thnk (N1 ,N2 , cl , s) and generalized folded multi-link multi-stage networks
`
`Vfold—mlink (N1 , N2 , d , s) with numerous connection topologies and the scheduling methods
`
`are described in detail in US. Provisional Patent Application Serial No. 60/ 940, 389 that
`
`is incorporated by reference above.
`
`3) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks Vfold (N1 , N2 , d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`10
`
`15
`
`20
`
`25
`
`-11-
`
`Page 16 of 164
`
`Page 16 of 164
`
`

`

`5-0038 PCT
`
`Provisional Patent Application Serial No. 60/940, 391 that is incorporated by reference
`
`above.
`
`4) Strictly nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`multi-stage networks Vka (N 1, N 2 , d , s) and generalized folded multi-link multi-stage
`
`networks Vfo,d_m,,nk (N1 , N2 , d, s) with numerous connection topologies and the scheduling
`
`methods are described in detail in US. Provisional Patent Application Serial No. 60/940,
`
`392 that is incorporated by reference above.
`
`5) VLSI layouts of generalized multi—stage networks V(N1,N2,d, s) , generalized
`
`folded multi-stage networks Vfo,d (N1 , N2 , d , s) , generalized butterfly fat tree networks
`
`10
`
`Vbfl (N1, N2 , d , s) , generalized multi-link multi-stage networks leink (N1 , N2 , d , s) ,
`
`0
`generalized folded multi-link multi-stage networks Vf
`
`[Mm/m, (N1 , N2 , d , s) , generalized
`
`multi-link butterfly fat tree networks Killink—bfi (N1 , N2 , d , S) , and generalized hypercube
`
`networks thbe (N1 , N2,0! ,5) for s = 1,2,3 or any number in general, are described in
`
`detail in US Provisional Patent Application Serial N 0. 60/940, 394 that is incorporated
`
`15
`
`by reference above.
`
`6) VLSI layouts of numerous types of multi-stage networks with locality
`
`exploitation are described in US. Provisional Patent Application Serial No. 60/984, 724
`
`that is incorporated by reference above.
`
`7) VLSI layouts of numerous types of multistage pyramid networks are described
`
`in US. Provisional Patent Application Serial No. 61/ 018, 494 that is incorporated by
`
`reference above.
`
`-12-
`
`20
`
`25
`
`Page 17 of 164
`
`Page 17 of 164
`
`

`

`5-0038 PCT
`
`BUTTERFLY FAT TREE EMBODIMENTS:
`
`Symmetric RNB Embodiments:
`
`Referring to FIG. 1A, in one embodiment, an exemplary symmetrical butterfly fat
`
`tree network 100A with three stages of twenty four switches for satisfying
`
`communication requests, such as setting up a telephone call or a data call, or a connection
`
`between configurable logic blocks, between an input stage 110 and output stage 120 Via
`
`middle stages 130, and 140 is shown where input stage 110 consists of four, two by four
`
`switches 131-134 and output stage 120 consists of four, four by two switches OSl-OS4.
`
`Input stage 110 and output stage 120 together belong to leaf stage. And all the middle
`
`stages excepting root stage namely middle stage 130 consists of eight, four by four
`
`switches MS(l,l) - MS(l,8), and root stage i.e., middle stage 140 consists of eight, two
`
`by two switches MS(2,1) - MS(2,8).
`
`Such a network can be operated in strictly non-blocking manner for unicast
`
`connections, because the switches in the input stage 110 are of size two by four, the
`
`switches in output stage 120 are of size four by two, and there are eight switches in each
`
`of middle stage 130 and middle stage 140. Such a network can be operated in
`
`rearrangeably non-blocking manner for multicast connections, because the switches in the
`
`input stage 110 are of size two by four, the switches in output stage 120 are of size four
`
`by two, and there are eight switches in each of middle stage 130 and middle stage 140.
`
`In one embodiment of this network each of the input switches ISl-IS4 and output
`
`switches OSl-OS4 are crossbar switches. The number of switches of input stage 110 and
`
`of output stage 120 can be denoted in general with the variable % , where N is the total
`
`number of inlet links or outlet links. Input stage 110 and output stage 120 together
`
`belong to leaf stage. The number of middle switches in each middle stage is denoted by
`
`10
`
`15
`
`‘20
`
`25
`
`ZXE . The size of each input switch ISl—IS4 can be denoted in general with the notation
`d
`
`d * 2d and each output switch OSl-OS4 can be denoted in general with the notation
`
`2d * d . Likewise, the size of each switch in any of the middle stages can be denoted as
`
`2d * 2d excepting that the size of each switch in middle stage 140 is denoted as d * d .
`
`_13_
`
`Page 18 of 164
`
`Page 18 of 164
`
`

`

`5-0038 PCT
`
`(In another embodiment, the size of each switch in any of the middle stages other than the
`
`middle stage 140, can be implemented as d * 2d and d * d since the down coming
`
`middle links are never setup to the up going middle links. For example in network 100A
`
`of FIG. 1A, the down coming middle links ML(3,2) and ML(3,5) are never setup to the
`
`up going middle links ML(2, 1) and ML(2,2) for the middle switch MS(1,1). So middle
`
`switch MS(1,l) can be implemented as a two by four switch with middle links ML(1,1)
`
`and ML(1,3) as inputs and middle links ML(2,1), ML(2,2), ML(4,l) and ML(4,2) as
`
`outputs; and a two by two switch with middle links ML(3,2) and ML(3,5) as inputs and
`
`middle links ML(4,l) and ML(4,2) as outputs).
`
`Middle stage 140 is called as root stage. A switch as used herein can be either a
`
`crossbar switch, or a network of switches each of which in turn may be a crossbar switch
`
`or a network of switches. A symmetric Butterfly fat tree network can be represented with
`
`the notation Vbfl (N, d, s), where N represents the total number of inlet links of all input
`
`switches (for example the links ILl-ILS),
`
`(1 represents the inlet links of each input switch
`
`or outlet links of each output switch, and s is the ratio of number of outgoing links from
`
`each input switch to the inlet links of each input switch. Although it is not necessary that
`
`there be the same number of inlet links ILl-ILS as there are outlet links OLl-OLS, in a
`
`symmetrical network they are the same.
`
`Each of the % input switches ISl — 134 are connected to exactly 2Xd switches
`
`in middle