Document made
`
`available under
`
`the
`
`Patent Cooperation Treaty (PCT)
`
`International application number: PCT/US2008/056064
`
`International filing date:
`
`06 March 2008 (06.03.2008)
`
`Document type:
`
`Certified copy of priority document
`
`Document details:
`
`Country/Office: US
`Number:
`60/940383
`Filing date:
`25 May 2007 (25.05.2007)
`
`Date of receipt at the International Bureau:
`
`29 March 2008 (29.03.2008)
`
`Remark:
`
`Priority document submitted or transmitted to the International Bureau in
`compliance with Rule 17.1(a) or (b)
`
`
`
`World Intellectual Property Organization (WIPO) - Geneva, Switzerland
`Organisation Mondiale de la Propriété Intellectuelle (OMPI) - Geneve, Suisse
`
`Page 1 of 98
`
`FLEX LOGIX EXHIBIT 1014
`
`Page 1 of 98
`
`FLEX LOGIX EXHIBIT 1014
`
`

`

`
`
`
`
`
`
`
` \EEEEE \\
`
`
`
`
`\EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
`
`ENE ExEEE \E-E“ \E‘E\\\\\E\\\ EE‘EEEEEEEM
`
`1‘3 \ -v -.\u\\\\
`
`
`
`
`
`\ ‘ § § - 3 x §E
`_\\\‘
`. § \ §
`§ 1‘ \ Em§§ \‘E§Vfifl§N'3\\\:§¥I.-.\\§':\:§xxN§\%§fiu\Kfi':31.\\\.‘€'\-\§E§E.%\\é\\\\;\\€‘\\\§
`_E
`
`E E EEE EEEE EE EE EEE
`EEE E EE E E EE‘EE EE EEE E EE E EEE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`L" N H Iii-D 5 TA
`D E Ps9. R’I‘ M E-
`
`
`
`
`United Shams Patent and ‘I'E'admnm‘k Offiua‘:
`
`
`
`
`March 29, 2008
`
`
`
`
`
`
`
`
`
`THIS IS TO CERTIFY THAT ANNEXED HERETO IS A TRUE COPY FROM
`THE RECORDS OF THE UNITED STATES PATENT AND TRADEMARK
`OFFICE OF THOSE PAPERS OF THE BELOW IDENTIFIED PATENT
`APPLICATION THAT MET THE REQUIREMENTS TO BE GRANTED A
`FILING DATE.
`
`
`
`
`
`
`
`
`
`APPLICATION NUMBER: 60/940,383
`FILING DATE: May 25, 2007
`RELATED PCT APPLICATION NUMBER: PCT/US08/56064
`
`
`
`THE COUNTRY CODE AND NUMBER OF YOUR PRIORITY
`APPLICATION, TO BE USED FOR FILING ABROAD UNDER THE PARIS
`
`
`
`CONVENTION, IS US60/940,383
`
`
` Certified by
`
`
`
`Under Seeretsn‘y Bf Calamari-e
`fur In‘milurtzu a! Pmperty
`and Director 0f the United Suites
`I’ntuni‘ ism} "l'radmmark [Hfica
`
`Page 2 of 98
`
`Page 2 of 98
`
`

`

`M-0037 US
`
`FULLY CONNECTED GENERALIZED MULTI-STAGE NETWORKS
`
`Venkat Konda
`
`5
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M—003 8US entitled "FULLY CONNECTED
`
`GENERALIZED BUTTERFLY FAT TREE NETWORKS" by Venkat Konda assigned
`
`to the same assignee as the current application, filed concurrently.
`
`10
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M—0039US entitled "FULLY CONNECTED
`GENERALIZED REARRANGEABLY N ONBLOCKIN G MULTI-LIN K MULTI-
`
`STAGE NETWORKS” by Venkat Konda assigned to the same assignee as the current
`
`application, filed concurrently.
`
`15
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M—0040US entitled "FULLY CONNECTED
`
`GENERALIZED MULTI-LINK BUTTERFLY FAT TREE NETWORKS" by Venkat
`
`Konda assigned to the same assignee as the current application, filed concurrently.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`20
`
`Provisional Patent Application Docket N o. M-0041US entitled "FULLY CONNECTED
`
`GENERALIZED FOLDED MULTI-STAGE NETWORKS” by Venkat Konda assigned
`
`to the same assignee as the current application, filed concurrently.
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M-0042US entitled ”FULLY CONNECTED
`
`25
`
`GENERALIZED STRICTLY NONBLOCKING MULTI—LINK MULTI—STAGE
`
`NETWORKS" by Venkat Konda assigned to the same assignee as the current application,
`
`filed concurrently.
`
`_1_
`
`Page 3 of 98
`
`Page 3 of 98
`
`

`

`M-0037 US
`
`This application is related to and incorporates by reference in its entirety the U.S.
`
`Provisional Patent Application Docket No. M—0045US entitled "VLSI LAYOUTS OF
`
`FULLY CONNECTED GENERALIZED NETWORKS” by Venkat Konda assigned to
`
`the same assignee as the current application, filed concurrently.
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A is a diagram 100A of an exemplary symmetrical multi—stage network
`
`V(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
`
`10
`
`connections, in accordance with the invention.
`
`FIG. 13 is a diagram 1003 of a general symmetrical multi—stage network
`
`V(N,d,2) with (2xlogd N)—1
`
`stages
`
`strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast
`
`connections in accordance with the invention.
`
`15
`
`FIG. 1C is a diagram 100C of an exemplary asymmetrical multi-stage network
`
`V(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. 1D is a diagram 100D of a general asymmetrical multi-stage network
`
`V(N1,N2,d,2) with N2 = p* N1 and with (2Xlogd N)—1 stages strictly nonblocking
`
`network for unicast connections and rearrangeably nonblocking network for arbitrary fan-
`
`out multicast connections in accordance with the invention.
`
`FIG. 1E is a diagram 100E of an exemplary asymmetrical multi-stage network
`
`V(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.
`-2-
`
`Page 4 of 98
`
`Page 4 of 98
`
`

`

`M-0037 US
`
`FIG.
`
`lF is a diagram lOOF of a general asymmetrical multi—stage network
`
`V(N1,N2,d,2) with N1 = p* N2 and with (2xlogd N)—1 stages 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 lOOAl of an exemplary symmetrical multi—stage network
`
`V(N ,d ,2) having Omega connection topology of five stages with N = 8, d = 2 and s=2
`
`with exemplary multicast connections,
`
`strictly nonblocking network for unicast
`
`connections and rearrangeably nonblocking network for arbitrary fan-out multicast.
`
`connections, in accordance with the invention.
`
`10
`
`FIG. lCl is a diagram lOOCl of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,d,2) having Omega connection topology of five stages with N1 : 8, N3 : 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. IE] is a diagram 100E] of an exemplary asymmetrical multi—stage network
`
`V(N1,N2,d,2) having Omega 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. 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
`
`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,(I,2) having nearest neighbor connection topology of five stages with N1 = 8,
`
`N2 = p* N1 = 24 where p = 3, and d = 2 with exemplary multicast connections, strictly
`
`Page 5 of 98
`
`Page 5 of 98
`
`

`

`M-0037 US
`
`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,Nz,d ,2) having nearest neighbor connection topology of five stages with N2 : 8,
`
`5
`
`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. 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
`
`10
`
`s:3 with exemplary multicast connections strictly nonblocking network for arbitrary fan-
`
`out multicast connections, in accordance with the invention.
`
`FIG. 2B1 & FIG. 2B2 is a diagram 200B of a general symmetrical multi-stage
`
`network V(N, d ,3) with (2X log d N) —1 stages strictly nonblocking network for arbitrary
`
`fan-out multicast connections in accordance with the invention.
`
`15
`
`FIG. 2C is a diagram 200C of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,(I,3) 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 arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`20
`
`FIG. 2Dl & FIG. 2D2 is a diagram 200D of a general asymmetrical multi-stage
`
`network V(N1,Nz,d,3) with N2 = p* N1 and with (2Xlogd N)—l
`
`stages strictly
`
`nonblocking network for arbitrary fan-out multicast connections in accordance with the
`
`invention.
`
`FIG. 2B is a diagram 200E of an exemplary asymmetrical multi—stage network
`
`25
`
`V(N1, N2,d ,3) 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 arbitrary fan—out multicast connections, in accordance with the
`
`invention.
`
`_4_
`
`Page 6 of 98
`
`Page 6 of 98
`
`

`

`M-0037 US
`
`FIG. 2Fl & FIG. 2F2 is a diagram 200F of a general asymmetrical multi—stage
`
`network V(N1,NZ,(Z,3) with N1 = p* N2 and with (2Xlogd N)—l
`
`stages strictly
`
`nonblocking network for arbitrary fan—out multicast connections in accordance with the
`
`invention.
`
`FIG. 2A1 is a diagram 200Al of an exemplary symmetrical multi—stage network
`
`V(N ,d ,3) having Omega connection topology of five stages with N = 8, d = 2 and s=3
`
`with exemplary multicast connections, strictly nonblocking network for arbitrary fan-out
`
`multicast connections, in accordance with the invention.
`
`FIG. 2C1 is a diagram 200Cl of an exemplary asymmetrical multi-stage network
`
`V(N1,N2,d,3) having Omega 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 arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`FIG. 2E1 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, N1 = 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.
`
`10
`
`15
`
`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
`
`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(N1,Nl,d ,3) having nearest neighbor 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 arbitrary fan-out multicast connections, in accordance with the
`
`invention.
`
`Page 7 of 98
`
`Page 7 of 98
`
`

`

`M-0037 US
`
`FIG. 2E2 is a diagram 200E2 of an exemplary asymmetrical multi—stage network
`
`V(N1,N2,d ,3) having nearest neighbor 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 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.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`10
`
`15
`
`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. Particularly multi—stage networks with stages more
`
`than 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.
`
`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.
`
`Page 8 of 98
`
`Page 8 of 98
`
`

`

`M-0037 US
`
`U]
`
`10
`
`15
`
`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.
`
`Nonblocking configurations for other types of networks with numerous
`
`connection topologies and scheduling methods are disclosed as follows:
`
`1) Strictly and rearrangeably nonbloeking for arbitrary fan—out multicast and
`
`unicast for generalized butterfly fat tree networks Vbfl (N1 , N2 , d , s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application, Attorney Docket No. M70038 US that is incorporated by
`
`reference above.
`
`2) Rearrangeably nonbloeking for arbitrary fan—out multicast and unicast, and
`
`strictly nonbloeking for unicast for generalized multi—link multi—stage networks
`
`Vmfink (N1 , N2 , d , s) and generalized folded multi—link multi—stage networks
`
`V/{leink (N1 ,Nz , d, s) with numerous connection topologies and the scheduling methods
`
`are described in detail in US. Provisional Patent Application, Attorney Docket N o. M-
`
`0039 US that is incorporated by reference above.
`
`3) Strictly and rearrangeably nonbloeking for arbitrary fan-out multicast and
`
`unicast for generalized multi—link butterfly fat tree networks Vm/m/Hfi (N1 , N2 , d, s) with
`
`_7_
`
`Page 9 of 98
`
`Page 9 of 98
`
`

`

`M-0037 US
`
`numerous connection topologies and the scheduling methods are described in detail in
`
`US. Provisional Patent Application, Attorney Docket No. M—0040 US that is
`
`incorporated by reference above.
`
`4) Strictly and rearrangeably nonblocking for arbitrary faniout multicast and
`
`unicast for generalized folded multi-stage networks Vfifld (N1 , N2 , d, s) with numerous
`
`connection topologies and the scheduling methods are described in detail in US.
`
`Provisional Patent Application, Attorney Docket No. M—0041 US that is incorporated by
`reference above.
`
`5) Strictly nonblocking for arbitrary fan—out multicast for generalized multi—link
`
`multi-stage networks leink (N 1 , N 2 , d , 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, Attorney Docket
`
`No. M-0042 US that is incorporated by reference above.
`
`6) VLSI layouts of generalized multi—stage networks V(N1, N2,d, s) , generalized
`
`folded multi-stage networks Vfold (N1 , N2 , d , s) , generalized butterfly fat tree networks
`
`Vbfl (N1 , N2 , cl , s) , generalized multi-link multi-stage networks leink (N1 , N2 , d , s) ,
`
`generalized folded multi-link multi-stage networks Vfifl01,,"ka (N 1 , N 2 , d, s) , generalized
`m
`multi—link butterfly fat tree networks V
`
`, N2 , d , s) , and generalized hypercube
`
`”HM” (N1
`
`networks Vham (N1, N2 , (l, s) for s = 1,2,3 or any number in general, are described in
`
`detail in US. Provisional Patent Application, Attorney Docket No. M-0045 US that is
`
`incorporated by reference above.
`
`Symmetric RNB Embodiments:
`
`Referring to FIG, 1A, in one embodiment, an exemplary symmetrical multi-stage
`
`network 100A 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
`
`stages 130, 140, and 150 is shown Where input stage 110 consists of four, two by four
`
`—8—
`
`10
`
`15
`
`20
`
`[QU]
`
`Page 10 of 98
`
`Page 10 of 98
`
`

`

`M-0037 US
`
`switches 131—134 and output stage 120 consists of four, four by two switches OSl—OS4.
`
`And all the middle stages namely middle stage 130 consists of eight, two by two switches
`
`MS(1, l) - 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,l) - 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 real‘rangeably non-blocking manner for multicast connections, because the
`
`10
`
`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 IS 1-134 and output
`
`switches OSl—OS4 are crossbar switches. The number of switches of input stage 110 and
`
`15
`
`of output stage 120 can be denoted in general with the variable i , where N is the total
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by 2x£ . The size of each input switch IS] —IS4 can be denoted in general
`d
`
`with the notation 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 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
`
`ILl-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 ILl-ILS as there are outlet links OLl-OLS, in a symmetrical network they are
`
`the same.
`
`Page 11 of 98
`
`Page 11 of 98
`
`

`

`M-0037 US
`
`Each of the l input switches ISl — IS4 are connected to exactly 2 Xcl switches
`(Z
`
`in middle stage 130 through 2X d links (for example input switch 1S1 is connected to
`
`middle switches MS(1,1), MS(1,2), MS(1,5) and MS(1,6) through the links ML(1,1),
`
`ML(] ,2), ML(] ,3) and ML(] ,4) respectively).
`
`Each of the 2X% middle switches MS(1,1) — MS(1,8) in the middle stage 130
`
`are connected from exactly d input switches through (1 links (for example the links
`
`ML(1.1) and ML(1.5) are connected to the middle switch MS(1,1) from input switch 131
`
`and 132 respectively) and also are connected to exactly (I, 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(1,1) to middle switch MS(2,1) and MS(2,3) respectively).
`
`Similarly each of the 2X£ middle switches MS(2,1) — MS(2,8) in the middle
`d
`
`stage 140 are connected from exactly d switches in middle stage 130 through d links
`
`(for example the links ML(2,1) and ML(2,6) are connected to the middle switch MS(2,1)
`
`from middle switches MS(1,1) and MS(1,3) respectively) and also are connected to
`
`exactly (1 switches in middle stage 150 through d links (for example the links ML(3,1)
`
`and ML(3,2) are connected from middle switch MS(2, 1) to middle switch MS(3,1) and
`
`MS(3,3) respectively).
`
`10
`
`15
`
`Similarly each of the 2X£ middle switches MS(3,1) — MS(3,8) in the middle
`(1
`
`stage 150 are connected from exactly d switches in middle stage 140 through d links
`
`(for example the links ML(3,1) and ML(3,6) are connected to the middle switch MS(3,1)
`
`from middle switches MS(2,1) and MS(2,3) respectively) and also are connected to
`
`exactly d output switches in output stage 120 through 0! links (for example the links
`
`ML(4,1) and ML(4,2) are connected to output switches 051 and 032 respectively from
`
`middle switches MS(3,1)).
`
`-10-
`
`Page 12 of 98
`
`Page 12 of 98
`
`

`

`M-0037 US
`
`Each of the l output switches OSl — 034 are connected from exactly 2 X d
`(1
`
`switches in middle stage 150 through 2 X (l links (for example output switch 0S1 is
`
`connected from middle switches MS(3,1), MS(3,2), MS(3,5) and MS(3,6) through the
`
`links ML(4,l ), ML(4,3), ML(4,9) and ML(4,l 1) respectively).
`
`Finally the connection topology of the network 100A shown in FIG. 1A is known
`
`to be back to back inverse Benes connection topology.
`
`Referring to FIG. 1A1, in another embodiment of network V(N, d, s) , an
`
`exemplary symmetrical multi—stage network lOOAl with five stages of thirty two
`
`switches for satisfying communication requests, such as setting up a telephone call or a
`
`10
`
`15
`
`data call, or a connection between configurable logic blocks, between an input stage 110
`
`and output stage 120 via middle stages 130, 140, and 150 is shown where input stage 110
`
`consists of four, two by four switches 151-134 and output stage 120 consists of four, four
`
`by two switches OSl-OS4. And all the middle stages namely middle stage 130 consists of
`
`eight, two by two switches MS(l ,l) — MS(l ,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.
`
`25
`
`In one embodiment of this network each of the input switches 181-134 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 i , where N is the total
`d
`
`number of inlet links or outlet links. The number of middle switches in each middle stage
`
`-11-
`
`Page 13 of 98
`
`Page 13 of 98
`
`

`

`M-0037 US
`
`10
`
`15
`
`20
`
`is denoted by 2 ><fl . The size of each input switch ISl-IS4 can be denoted in general
`d
`
`with the notation 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 d >I< 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. The
`
`symmetric multi-stage network of FIG. 1A1 is also the network of the type V(N, (I, s) ,
`
`where N represents the total number of inlet links of all input switches (for example the
`
`links [Ll—1L8), 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 OLl-OLS, in a symmetrical
`
`network they are the same.
`
`Each of the E input switches IS] i 184 are connected to exactly 2 Xd switches
`(I
`
`in middle stage 130 through 2X d links (for example input switch 131 is connected to
`
`middle switches MS(1,1), MS(1,2), MS(1,5) and MS(1,6) through the links ML(1,1),
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`Each of the 2X£ middle switches MS(1 ,l) 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(1, 1) and ML(1,9) are connected to the middle switch MS(1,1) from input switch I31
`
`and IS3 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(1,1) to middle switch MS(2,1) and MS(2,2) respectively).
`
`Similarly each of the 2x% middle switches MS(2,1) , MS(2,8) in the middle
`
`stage 140 are connected from exactly d switches in middle stage 130 through d links
`
`(for example the links ML(2,1) and ML(2,5) are connected to the middle switch MS(2,1)
`
`from middle switches MS(1,1) and MS(1,3) respectively) and also are connected to
`
`exactly d switches in middle stage 150 through (1 links (for example the links ML(3,1)
`_12_
`
`Page 14 of 98
`
`Page 14 of 98
`
`

`

`M-0037 US
`
`and ML(3,2) are connected from middle switch MS(2,1) to middle switch MS(3,1) and
`
`MS(3,2) respectively).
`
`Similarly each of the 2><£ middle switches MS(3,l) — MS(3,8) in the middle
`d
`
`stage 150 are connected from exactly d switches in middle stage 140 through d links
`
`(for example the links ML(3,1) and ML(3,5) are connected to the middle switch MS(3,1)
`
`from middle switches MS(2,1) and MS(2,3) respectively) and also are connected to
`
`exactly (1, output switches in output stage 120 through (1 links (for example the links
`
`ML(4,1) and ML(4,2) are connected to output switches 081 and OSZ respectively from
`
`middle switches MS(3,1)).
`
`10
`
`15
`
`Each of the El output switches OSl — OS4 are connected from exactly 2X d
`
`(
`
`switches in middle stage 150 through 2 Xd links (for example output switch 031 is
`
`connected from middle switches MS(3,1), MS(3,3), MS(3,5) and MS(3,7) through the
`
`links ML(4,1), ML(4,5), ML(4,9) and ML(4,13) respectively).
`
`Finally the connection topology of the network lOOAl shown in FIG. 1A1 is
`
`known to be back to back Omega connection topology.
`
`Referring to FIG. 1A2, in another embodiment of network V(N, (1,5) , an
`
`exemplary symmetrical multi-stage network 100A2 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 stages 130, 140, and 150 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. 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
`
`Ix)U1
`
`switches MS(3,l) — MS(3,8).
`
`Such a network can be operated in strictly non-blocking manner for unicast
`
`connections, because the switches in the input stage 1 l 0 are of size two by four, the
`
`-13-
`
`Page 15 of 98
`
`Page 15 of 98
`
`

`

`M-0037 US
`
`U]
`
`10
`
`15
`
`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 l 10 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 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. The number of middle switches in each middle stage
`
`is denoted by 2 xi . The size of each input switch ISl-IS4 can be denoted in general
`(1
`
`with the notation 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 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. The
`
`symmetric multi—stage network of FIG. 1A2 is also the network of the type V(N, d, s) ,
`
`where N represents the total number of inlet links of all input switches (for example the
`
`links ILl—ILS), 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 ILl-ILS as there are outlet links OLl-OLS, in a symmetrical
`
`network they are the same.
`
`Each of the £1 input switches ISl — 184 are connected to exactly 2 Xd switches
`
`c
`
`in middle stage 130 through 2X (1! links (for example input switch 181 is connected to
`
`[0 U1
`
`middle switches MS(l,l), MS(1,2), MS(l,5) and MS(l,6) through the links ML(l,l),
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`_14_
`
`Page 16 of 98
`
`Page 16 of 98
`
`

`

`M-0037 US
`
`Each of the 2><% middle switches MS(1,1) — MS(1,8) in the middle stage 130
`
`are connected from exactly d input switches through (1 links (for example the links
`
`ML(1, 1) and ML(1,14) are connected to the middle switch MS(1, 1) from input switch 131
`
`and IS4 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(1,1) to middle switch MS(2,1) and MS(2,2) respectively).
`
`10
`
`15
`
`Similarly each of the 2Xfl middle switches MS(2,1) — MS(2,8) in the middle
`(1
`
`stage 140 are connected from exactly (1 switches in middle stage 130 through d links
`
`(for example the links ML(2,1) and ML(2,8) are connected to the middle switch MS(2,1)
`
`from middle switches MS(1,1) and MS(1,4) respectively) and also are connected to
`
`e