(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`(19) World Intellectual Property Organization
`International Bureau
`
`(43) International Publication Date
`12 September 2008 (12.09.2008)
`
`PCT
`
`(51) International Patent Classification:
`H04Q 3/00 (2006 01)
`
`(21) International Application Number:
`PCT/US2008/056064
`
`(22) International Filing Date:
`
`6 March 2008 (06 03 2008)
`
`(25) Filing Language:
`
`(26) Publication Language:
`
`(30) Priority Data:
`60/905,526
`60/940,383
`
`English
`
`English
`
`6 March 2007 (06 03 2007) US
`25 May 2007 (25 05 2007) US
`
`(71) Applicant and
`(72) Inventor: KONDA, Venkat [US/US], 6278, Grand Oak
`Way, San Jose, CA 95135 (US)
`
`(10) International Publication Number
`WO 2008/109756 Al
`AO, AT,AU, AZ, BA, BB, BG, BH, BR, BW, BY, BZ, CA,
`CH, CN, CO, CR, CU, CZ, DE, DK, DM, DO, DZ, EC, EE,
`EG, ES, FI, GB, GD, GE, GH, GM, GT, HN, HR, HU, ID,
`IL, IN, IS, JP, KE, KG, KM, KN, KP, KR, KZ, LA, LC,
`LK, LR, LS, LT, LU, LY, MA, MD, ME, MG, MK, MN,
`MW, MX, MY, MZ, NA, NG, NI, NO, NZ, OM, PG, PH,
`PL, PT, RO, RS, RU, SC, SD, SE, SG, SK, SL, SM, SV,
`SY, TJ, TM, TN, TR, TT, TZ, UA, UG, US, UZ, VC, VN,
`ZA, ZM, ZW
`
`(84) Designated States (unless otherwise indicated, for every
`kind of regional protection available): ARIPO (BW, GH,
`GM, KE, LS, MW, MZ, NA, SD, SL, SZ, TZ, UG, ZM,
`ZW), Eurasian (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM),
`European (AT,BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI,
`FR, GB, GR, HR, HU, IE, IS, IT, LT,LU, LV,MC, MT, NL,
`NO, PL, PT, RO, SE, SI, SK, TR), OAPI (BF, BJ, CF, CG,
`CI, CM, GA, GN, GQ, GW, ML, MR, NE, SN, TD, TG)
`
`(81) Designated States (unless otherwise indicated, for every
`Published:
`kind of national protection available): AE, AG, AL, AM, — with international search report
`
`(54) Title: FULLY CONNECTED GENERALIZED MULTI-STAGE NETWORKS
`
`j *Logt N-i)
`
`-22x N )
`
`FIG. IB
`
`130 + 10«(Lo ,
`
`(57) Abstract: A multi-stage network
`compp sing (2x log N)
`- I stages
`is operated in strictly nonblocking
`manner for unicast includes an input
`stage having N / d switches with
`each of them having d inlet
`links
`and 2x d outgoing links connecting
`to second stage switches, an output
`stage having N / d switches with each
`of them having d outlet links and 2
`xd incoming links connecting from
`in the penultimate stage
`switches
`The network also has (2x log N)
`- 3 middle stages with each middle
`stage having 2 x N / d 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
`immediate
`in its
`succeeding stage
`Also the same
`multi-stage network is operated in
`rearrangeably nonblocking manner for
`arbitrary fan-out multicast and each
`multicast connection is set up by use
`of at most two outgoing links from the input stage switch A multi-stage network compp sing (2x log N) - I stages is operated in
`strictly nonblocking manner for multicast includes an input stage having N / d switches with each of them having^ inlet links and 3
`x d outgoing links connecting to second stage switches, an output stage having N / d switches with each of them having d outlet
`links and 3 x d incoming links connecting from switches in the penultimate stage The network also has (2x log N) - 3 middle
`stages with each middle stage having 3 x N / f 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 succeeding stage
`
`Page 1 of 117
`
`FLEX LOGIX EXHIBIT 1009
`
`

`

`FULLY CONNECTED GENERALIZED MULTI-STAGE NETWORKS
`
`Venkat Konda
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`reference in its entirety the U.S. Provisional Patent Application Serial No. 60/905,526
`
`entitled "LARGE SCALE CROSSPOINT REDUCTION WITH NONBLOCKING
`
`UNICAST & MULTICAST IN ARBITRARILY LARGE MULTI-STAGE
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed March 6, 2007.
`
`This application is Continuation In Part PCT Application to and incorporates by
`
`reference in its entirety the U.S. Provisional Patent Application Serial No. 60/940, 383
`
`entitled "FULLY CONNECTED GENERALIZED MULTI-STAGE NETWORKS" by
`
`Venkat Konda assigned to the same assignee as the current application, filed May 25,
`
`2007.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`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.
`
`This application is related 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 assigned to the same assignee as the current
`
`application, filed May 25, 2007.
`
`Page 2 of 117
`
`

`

`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Serial No. 60/940, 390 entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS" by Venkat
`
`Konda assigned to the same assignee as the current application, filed May 25, 2007.
`
`This application is related to and incorporates by 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, filed May 25, 2007.
`
`This application is related 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 Konda assigned to the same assignee as the current application,
`
`filed May 25, 2007.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`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 U.S.
`
`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 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 assignee as the current application, filed January 1, 2008.
`
`Page 3 of 117
`
`

`

`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.
`
`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
`
`nonblocking for unicast connections.
`
`Page 4 of 117
`
`

`

`U.S. 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‡ min((« - l)(x + rllx )) where
`1< x £ min(« - 1, r) , the resulting network is nonblocking for multicast assignments.
`the relation, r is the number of switches in the input stage, and n is the number of inlet
`
`In
`
`links in each input switch.
`
`U.S. 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‡ 2xn. And U.S. 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‡ 3x 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.l, pp. 406-424 showed a way of constructing large multi-stage networks by
`recursive substitution with a crosspoint complexity of d2xNx(logd N) 258 for strictly
`nonblocking unicast network. Similarly U.S. 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
`d2xNx(logd N)2 for strictly nonblocking unicast, (by using log N number of Benes
`Networks for d = 2) and without counting the crosspoints in multiplexers and
`
`Page 5 of 117
`
`

`

`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.
`
`SUMMARY OF INVENTION
`
`A multi-stage network comprising (2xlog N )-I
`
`stages is operated in strictly
`
`N
`nonblocking manner for unicast includes an input stage having — switches with each of
`d
`
`them having d inlet links and 2 x d outgoing links connecting to second stage switches,
`N
`an output stage having — switches with each of them having d outlet links and 2 x d
`d
`
`incoming links connecting from switches in the penultimate stage. The network also has
`
`(2xlog N ) - 3 middle stages with each middle stage having
`
`switches, and each
`
`d
`
`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 succeeding stage. Also the same multi-stage network is operated in
`
`rearrangeably nonblocking manner for arbitrary fan-out multicast and each multicast
`
`connection is set up by use of at most two outgoing links from the input stage switch.
`
`A multi-stage network comprising (2xlog N )-I
`
`stages is operated in strictly
`
`N
`nonblocking manner for multicast includes an input stage having — switches with each
`d
`
`of them having d inlet links and 3x d outgoing links connecting to second stage
`
`Page 6 of 117
`
`

`

`N
`switches, an output stage having — switches with each of them having d outlet links
`d
`and 3 x d incoming links connecting from switches in the penultimate stage. The
`
`network also has (2xlog N ) - 3 middle stages with each middle stage having
`
`d
`switches, and each switch in the middle stage has d incoming links connecting from the
`switches in its immediate preceding stage, and d outgoing links connecting to the
`
`switches in its immediate succeeding stage.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG.
`IA is a diagram IOOA of an exemplary symmetrical multi-stage network
`V(N,d, s) having inverse Benes connection topology of five stages with N = 8, d = 2 and
`
`s=2 with exemplary multicast connections,
`
`strictly nonblocking network for unicast
`
`connections
`
`and rearrangeably
`
`nonblocking
`
`network for arbitrary fan-out multicast
`
`connections,
`
`in accordance with the invention.
`
`FIG.
`
`V(N,d,2) with
`
`I B is a diagram IOOB of a general
`(2xlog N )-l
`
`stages
`
`strictly
`
`symmetrical multi-stage network
`
`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 IOOC of an exemplary asymmetrical multi-stage network
`V(N1,N2 ,
`= p* Ni = 24 where p = 3, and d = 2 with exemplary multicast connections,
`
`,2) having inverse Benes connection topology of five stages with Ni = 8, N2
`
`strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG.
`I D is a diagram IOOD of a general asymmetrical multi-stage network
`V(N1,N2,d,2) with N2 = p * Ni and with (2xlog N )-l
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`stages strictly nonblocking
`
`out multicast connections in accordance with the invention.
`
`Page 7 of 117
`
`

`

`FIG. I E is a diagram IOOE of an exemplary asymmetrical multi-stage network
`V(N1,N2,d,2) having inverse Benes connection topology of five stages with N2 = 8, Ni
`= 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.
`I F is a diagram IOOF of a general asymmetrical multi-stage network
`V(N1,N2,d,2) with Ni = p* N2 and with (2xlog N )-l
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`stages strictly nonblocking
`
`out multicast connections in accordance with the invention.
`
`is a diagram 100Al of an exemplary symmetrical multi-stage network
`FIG. IAl
`V(N,d,2) having Omega connection topology of five stages with N = 8, d = 2 and s=2
`
`with exemplary multicast
`
`connections,
`
`strictly nonblocking
`
`network
`
`for unicast
`
`connections
`
`and rearrangeably
`
`nonblocking network for arbitrary fan-out multicast
`
`connections,
`
`in accordance with the invention.
`
`FIG. ICl
`is a diagram IOOCI of an exemplary asymmetrical multi-stage network
`V(N1,N2,d,2) having Omega connection topology of five stages with Ni = 8, N2 = p*
`Ni = 24 where p = 3, and d = 2 with exemplary multicast connections,
`strictly
`
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG. IEl
`is a diagram 100El of an exemplary asymmetrical multi-stage network
`V(Nl,N2,d,2) having Omega connection topology of five stages with N2 = 8, Ni = p*
`strictly
`N2 = 24, where p = 3, and d = 2 with exemplary multicast connections,
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections,
`
`in accordance with the invention.
`
`FIG. 1A2 is a diagram 100A2 of an exemplary symmetrical multi-stage network
`V(N,d,2) having nearest neighbor connection topology of five stages with N = 8, d = 2
`
`and s=2 with exemplary multicast connections, strictly nonblocking network for unicast
`
`Page 8 of 117
`
`

`

`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections, in accordance with the invention.
`
`FIG. 1C2 is a diagram 100C2 of an exemplary asymmetrical multi-stage network
`V(N1,N2,d,2) having nearest neighbor connection topology of five stages with Ni = 8,
`N2 = p* Ni = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 1E2 is a diagram 100E2 of an exemplary asymmetrical multi-stage network
`V(N1,N2,d,2) having nearest neighbor connection topology of five stages with N2 = 8,
`Ni = p* N2 = 24, where p = 3, and d = 2 with exemplary multicast connections, strictly
`nonblocking network for unicast connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`FIG. 2A is a diagram 200A of an exemplary symmetrical multi-stage network
`V(N, d,3) having inverse Benes connection topology of five stages with N = 8, d = 2 and
`
`s=3 with exemplary multicast connections strictly nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 2Bl & FIG. 2B2 is a diagram 200B of a general symmetrical multi-stage
`
`network V(N,d,3) with (2xlog N )-I
`
`stages strictly nonblocking network for arbitrary
`
`fan-out multicast connections in accordance with the invention.
`
`FIG. 2C is a diagram 200C of an exemplary asymmetrical multi-stage network
`V(N1,N2,d,3) having inverse Benes connection topology of five stages with Ni = 8, N2
`= p* Ni = 24 where p = 3, and d = 2 with exemplary multicast connections strictly
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2Dl & FIG. 2D2 is a diagram 200D of a general asymmetrical multi-stage
`network V(N1,N2,d,3) with N2 = p* Ni and with (2xlog N )-l
`
`stages strictly
`
`Page 9 of 117
`
`

`

`nonblocking network for arbitrary fan-out multicast connections in accordance with the
`
`invention.
`
`FIG. 2E is a diagram 200E of an exemplary asymmetrical multi-stage network
`V(N1,N2,d,3) having inverse Benes connection topology of five stages with N2 = 8, Ni
`= p* N2 = 24, where p = 3, and d = 2 with exemplary multicast connections strictly
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2Fl & FIG. 2F2 is a diagram 200F of a general asymmetrical multi-stage
`network V(N1,N2,d,3) with Ni = p* N2 and with (2xlog N )-l
`nonblocking network for arbitrary fan-out multicast connections in accordance with the
`
`stages strictly
`
`invention.
`
`is a diagram 200Al of an exemplary symmetrical multi-stage network
`FIG. 2Al
`V(N,d,3) having Omega connection topology of five stages with N = 8, d = 2 and s=3
`
`with exemplary multicast connections, strictly nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`FIG. 2Cl is a diagram 200Cl of an exemplary asymmetrical multi-stage network
`V(Nl ,N2,d,3) having Omega connection topology of five stages with Ni = 8, N = p*
`Ni = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2El
`is a diagram 200El of an exemplary asymmetrical multi-stage network
`V(N1,N2,d,3) having Omega connection topology of five stages with N2 = 8, Ni = p*
`N2 = 24, where p = 3, and d = 2 with exemplary multicast connections, strictly
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2A2 is a diagram 200A2 of an exemplary symmetrical multi-stage network
`V(N,d,3) having nearest neighbor connection topology of five stages with N = 8, d = 2
`
`Page 10 of 117
`
`

`

`and s=3 with exemplary multicast connections, strictly nonblocking network for arbitrary
`
`fan-out multicast connections, in accordance with the invention.
`
`FIG. 2C2 is a diagram 200C2 of an exemplary asymmetrical multi-stage network
`
`V(N 1,N 2,d,3) having nearest neighbor connection topology of five stages with Ni = 8,
`N2 = p* Ni = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2E2 is a diagram 200E2 of an exemplary asymmetrical multi-stage network
`
`V(N 1,N 2,d,3) having nearest neighbor connection topology of five stages with N2 = 8,
`Ni = p* N2 = 24, where p = 3, and d = 2 with exemplary multicast connections, strictly
`nonblocking network for arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 3A is high-level
`
`flowchart of a scheduling method according to the
`
`invention, used to set up the multicast connections in all the networks disclosed in this
`
`invention.
`
`FIG. 4Al
`
`is a diagram 400Al of an exemplary prior art implementation of a two
`
`by two switch; FIG. 4A2 is a diagram 400A2 for programmable integrated circuit prior
`
`art implementation of the diagram 400Al of FIG. 4Al; FIG. 4A3 is a diagram 400A3 for
`
`one-time programmable integrated circuit prior art implementation of the diagram 400Al
`
`of FIG. 4Al; FIG. 4A4 is a diagram 400A4 for integrated circuit placement and route
`
`implementation of the diagram 400Al of FIG. 4Al.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention is concerned with the design and operation of large scale
`
`crosspoint reduction using arbitrarily large multi-stage switching networks for broadcast,
`
`unicast and multicast connections including their generalized topologies. Particularly
`
`multi-stage networks with stages more than three and radices greater than or equal to two
`
`Page 11 of 117
`
`

`

`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.
`
`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
`
`of the available outlet links.
`
`In certain multi-stage networks of the type described herein, any connection
`
`request of arbitrary fan-out, i.e. from an inlet link to an outlet link or to a set of outlet
`
`links of the network, can be satisfied without blocking if necessary by rearranging some
`
`of the previous connection requests. In certain other multi-stage networks of the type
`
`described herein, any connection request of arbitrary fan-out, i.e. from an inlet link to an
`
`outlet link or to a set of outlet links of the network, can be satisfied without blocking with
`
`never needing to rearrange any of the previous connection requests.
`
`In certain multi-stage networks of the type described herein, any connection
`
`request of unicast from an inlet link to an outlet link of the network, can be satisfied
`
`without blocking if necessary by rearranging some of the previous connection requests. In
`
`certain other multi-stage networks of the type described herein, any connection request of
`
`unicast from an inlet link to an outlet link of the network can be satisfied without
`
`blocking with never needing to rearrange any of the previous connection requests.
`
`Page 12 of 117
`
`

`

`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`1) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized butterfly fat tree networks Vbft (N 1, N 2,d, s) with numerous
`connection topologies and the scheduling methods are described in detail in U.S.
`
`Provisional Patent Application, Attorney Serial No. 60/940, 387 that is incorporated by
`
`reference above.
`
`2) Rearrangeably nonblocking for arbitrary fan-out multicast and unicast, and
`
`strictly nonblocking for unicast for generalized multi-link multi-stage networks
`
`Vmlmk (N 1,N 2,d, s) and generalized folded multi-link multi-stage networks
`2,d , s) with numerous connection topologies and the scheduling methods
`f oid-mi nk (
`are described in detail in U.S. Provisional Patent Application, Attorney Serial No.
`
`1
`
`60/940, 389 that is incorporated by reference above.
`
`3) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`unicast for generalized multi-link butterfly fat tree networks Vmlmk_bft (N 1,N 2,d,s) with
`numerous connection topologies and the scheduling methods are described in detail in
`
`U.S. Provisional Patent Application, Attorney Serial No. 60/940, 390 that is incorporated
`
`by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary fan-out multicast and
`
`unicast for generalized folded multi-stage networks Vfold (N 1,N 2,d,s) with numerous
`connection topologies and the scheduling methods are described in detail in U.S.
`
`Provisional Patent Application, Attorney Serial No. 60/940, 391 that is incorporated by
`
`reference above.
`
`5) Strictly nonblocking for arbitrary fan-out multicast for generalized multi-link
`
`multi-stage networks V
`
`(N 1,N 2,d,s) and generalized folded multi-link multi-stage
`networks Vfold_mlmk (N 1,N 2,d,s) with numerous connection topologies and the scheduling
`
`Page 13 of 117
`
`

`

`methods are described in detail in U.S. Provisional Patent Application, Attorney Serial
`
`No. 60/940, 392 that is incorporated by reference above.
`
`6) VLSI layouts of generalized multi-stage networks V(N 1,N 2,d,s) , generalized
`folded multi-stage networks Vfold (N 1,N 2,d,s) , generalized butterfly fat tree networks
`
`Vbft (N 1, N 2,d,s) , generalized multi-link multi-stage networks Vmlmk (N 1,N 2,d,s) ,
`
`generalized folded multi-link multi-stage networks Vfold_mlmk (N 1,N 2,d,s) , generalized
`
`multi-link butterfly fat tree networks Vmlmk_b (N 1, N 2,d,s)
`
`, and generalized hypercube
`
`networks Vhcube (N 1,N 2,d,s)
`detail in U.S. Provisional Patent Application, Attorney Serial No. M-0045 US that is
`
`for s = 1,2,3 or any number in general, are described in
`
`incorporated by reference above.
`
`7) VLSI layouts of numerous types of multi-stage networks with locality
`
`exploitation are described in U.S. 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.
`
`8) VLSI layouts of numerous types of multistage pyramid networks are described
`
`in 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 assignee as the current application, filed January 1,
`
`2008.
`
`Symmetric RNB Embodiments:
`
`Referring to FIG. IA, in one embodiment, an exemplary symmetrical multi-stage
`
`network IOOA with five stages of thirty two 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
`
`Page 14 of 117
`
`

`

`stages 130, 140, and 150 is shown where input stage 110 consists of four, two by four
`
`switches IS1-IS4 and output stage 120 consists of four, four by two switches 0S1-0S4.
`
`And all the middle stages namely middle stage 130 consists of eight, two by two switches
`
`MS(1, 1) - MS(1, 8), middle stage 140 consists of eight, two by two switches MS(2,1) -
`
`MS(2,8), and middle stage 150 consists of eight, two by two switches MS(3,1) - MS(3,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, middle stage 140 and middle stage 150. 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, middle
`
`stage 140 and middle stage 150.
`
`In one embodiment of this network each of the input switches IS1-IS4 and output
`
`switches OS1-OS4 are crossbar switches. The number of switches of input stage 110 and
`N
`of output stage 120 can be denoted in general with the variable — , where N is the total
`d
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`N
`is denoted by 2 x — . The size of each input switch IS1-IS4 can be denoted in general
`d
`
`with the notation d * d and each output switch OS1-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 d * d . 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 multi-stage network can be represented with the notation V(N, d ,s) , where
`
`N represents the total number of inlet links of all input switches (for example the links
`
`IL1-IL8), d 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 IL1-IL8 as there are outlet links OL1-OL8, in a symmetrical network they are
`
`the same.
`
`Page 15 of 117
`
`

`

`N
`Each of the — input switches ISl - IS4 are connected to exactly 2xd switches
`
`in middle stage 130 through 2xd links (for example input switch ISl is connected to
`
`middle switches MS(I I), MS(1,2), MS(1,5) and MS(1,6) through the links ML(I I),
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`N
`Each of the 2x— middle switches MS(I I) - MS(1, 8) in the middle stage 130
`d
`
`are connected from exactly d input switches through d links (for example the links
`
`ML(I I) and ML(1,5) are connected to the middle switch MS(I I) from input switch ISl
`
`and IS2 respectively) and also are connected to exactly d switches in middle stage 140
`
`through d links (for example the links ML(2,1) and ML(2,2) are connected from middle
`
`switch MS(I I) to middle switch MS(2,1) and MS(2,3) respectively).
`
`N
`Similarly each of the 2x— middle switches MS(2,1) - M