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/905526
`Filing date:
`06 March 2007 (06.03.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 38
`
`FLEX LOGIX EXHIBIT 1013
`
`Page 1 of 38
`
`FLEX LOGIX EXHIBIT 1013
`
`

`

`
`
`
`
`
`
`
` \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/905,526
`FILING DATE: March 06, 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/905,526
`
`
` 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 38
`
`Page 2 of 38
`
`

`

`lllllllllllll S'l'i
`£989I
`
`£09080
`
`Given Name (first and middle [if any])
`
`Family Name or Surname
`
`Venkat
`
`Residence
`and either State or F0 - 'n Coun
`
`‘
`
`San Jose. CA
`
`PTO/SW16 (02-07)
`Approved for use through 02/23/2007. OMB 0651-0032
`US. Patent and Trademark Office: US. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of 1995. no persons are required to respond to a collection of information unless it displays a valid OMB control number. U ”S PTO
`PROVISIONAL APPLICATION FOR PATENT COVER SHEET — Page 1 of 2
`60/905526
`This is a request for filing a PROVISIONAL APPLICATION FOR PATENT under 37 CFR 1.5302).
`03/06/2007
`E 'nEpress Mail Label No._£B§33_3§.QJAAJJ§_____—___
`
`
`
`
`
`
`
`
`
`
`
`
`
`'
`
`.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`$100 00
`Applicant claims small entity status. See 37 CFR 1.27.
`I
`A check or money order is enclosed to cover the filing fee and application size fee (if applicable).
`
`
`TOTAL FEE AMOUNT (S)
`'2] Payment by credit card. Form PTO-2038 Is attached
`I: The Diredor is hereby authorized to charge the filing fee and application size fee (if applicable) or credit any overpayment to Deposit
`
`
`
`Account Number.
`A duplicative copy of this form is enclosed for fee processing.
`
`
`USE ONLYFOR FILING A PROVISIONAL APPLICA'ITON FOR PA TENT
`This collection of intormetion is required by 37 CFR 1.51. The information is required to obtain or retain a benefit by the public which is to file (and by the USPTO
`to process) an application. Confidentiality is governed by 35 use. 122 and 37 CFR 1.11 and 1.14. This collection is estimated to take 8 hours to complete.
`including gathering. preparing. and submitting the completed application form to the USPTO. Time will vary depending upon the individual case. Any comments
`on the amount of time you require to complete this form end/or suggestions for mducing this burden. should be sent to the Chiet Information Officer. US. Patent
`and Trademark Office. US. Department of Commerce. P.O. Box 1450. Alexandria. VA 223131450. DO NOT SEND FEES OR COMPLETED FORMS TO THIS
`ADDRESS. SEND TO: Commissloner for Patents, P.O. Box 1450. Alexandria, VA 22313-1450.
`Ifyou need assistance in completing the form, will 1-600-PTO-9199 and select option 2.
`
`D Application Data Sheet. See 37 CFR 1.76
`lZl Drawing(s) Number of Sheets 14
`20
`Specification (e.g‘. description of the invention) Number of Pages
`Fees Due: Filing Fee of $200 ($100 for small entity).
`If the specification and drawings exceed 100 sheets of paper. an application size fee is
`also due. which is $250 ($125 for small entity) for each additional 50 sheets or fraction thereof. See 35 U.S.C. 41(a)(1)(G) and 37 CFR 1.16(s).
`
`separate/y numbered sheets attached hereto
`Additional inventors are being named an the
`TITLE OF THE INVENTION (500 characters max):
`.
`
`
`
`Direct all correspondence to:
`
`CORRESPONDENCE ADDRESS
`
`The address corresponding to Customer Number.
`
`Teak Networks. Inc.
`
`OR
`
`
`Firm or
`Individual Name
`Address 6278, Grand Oak Way
`
`38139
`
`.
`
`county USA
`
`
`
`Telephone 408-472-3273
`ENCLOSED APPLICATION PARTS (check all that appM
`
`= I :51 (r?
`
`9 2 AJ .: L. 0
`
`r.- u
`
`'3 CD(s). Number of CDs
`
`D Other (specify)
`
`METHOD OF PAYMENT OF THE FILING FEE AND APPLICATION SIZE FEE FOR THIS PROVISIONAL APPLICATION FOR PATENT
`
`Page 3 of 38
`
`Page 3 of 38
`
`

`

`PROVISIONAL APPLICA TION COVER SHEET
`Page 2 of 2
`
`PTO/SW16 (02-07)
`Approved for use through 02/28/2007. OMB 0651-0032
`US. Patent and Trademark Office; US. DEPARTMENT OF COMMERCE
`Under the Paperwork Roduaion Act of 1995. no persons are required to respond to a coileaion of information unless it displays a valid OMB control number.
`
`The invention was made by an agency of the United States Government or under a contract with an agency of the United States Govemment.
`No.
`
`D Yes, the name of the U.S. Government agency and the Government contract number are:
`
`WARNING:
`Petitioner/applicant is cautioned to avoid submitting personal information in documents filed in a patent application that may
`contribute to identity theft. Personal information such as social security numbers. bank account numbers. or credit card
`numbers (other than a check or credit card authorization form PTO-2038 submitted for payment purposes) is never required by
`the USPTO to support a petition or an application.
`If this type of personal information is included in documents submitted to
`the USPTO, petitioners/applicants should consider redacting such personal information from the documents before submitting
`them to the USPTO. Petitioner/applicant is advised that the record of a patent application is available to the public after
`publication of the application (unless a non—publication request in compliance with 37 CFR 1.213(a) is made in the application)
`or issuance of a patent. Furthermore, the record from an abandoned application may also be available to the public if the
`application is referenced in a published application or an issued patent (see 37 CFR 1.14). Checks and credit and
`authorization forms PTO—2038 submitted for payment purposes are not retained in the application file and therefore are not
`publicly available.
`SIGNATURE
`kilo
`Date 3/6/2007
`
`
`TYPED or PRINTED NAME Venkat Konda
`
`REGISTRATION No.
`(if appmpn‘ai‘e)
`
`TELEPHONE 408—472-3273
`
`Docket Number: M-0036 US
`
`Page 4 of 38
`
`Page 4 of 38
`
`

`

`"
`
`‘
`
`M-0036 us.
`
`
`
`ER 899 369 144 US
`
`Now?
`
`
`
`
`LARGE SCALE CROSSPOINT REDUCTION WITH NONBLOCKING
`
`UNICAST & MULTICAST IN ARBITRARILY LARGE MULTI—STAGE
`
`5
`
`NETWORKS
`
`Venkat Konda
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. IA is a diagram of an exemplary multi-stage symmetrical network of five
`
`stages with N = 8 and d = 2 with exemplary unicast and multicast connections, strictly
`
`10
`
`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 of a general symmetrical multi-stage network with
`
`(2xlogd N)—1
`
`stages
`
`strictly nonblocking network for unicast connections and
`
`rearrangeably nonblocking network for arbitrary fan-out multicast connections in
`
`15
`
`accordance with the invention.
`
`FIG. 2A is a diagram of an exemplary multi-stage symmetrical network of five
`
`stages with N = 8 and d = 2 with exemplary unicast and multicast connections, strictly
`
`nonblocking network for unicast and arbitrary fan-out multicast connections,
`
`in
`
`accordance with the invention.
`
`20
`
`FIG. 281 & FIG. 2132 is a diagram of a general symmetrical multi-stage network
`
`with (2 x logd N)——1 stages strictly nonblocking network for unicast and arbitrary fan-out
`
`multicast connections in accordance with the invention.
`
`FIG. 3A is a diagram of an exemplary multi-stage symmetrical network of five
`
`stages with N = 8 and d = 2, rearrangeably nonblocking network for unicast connections,
`in accordance with the invention.
`
`25
`
`Page 5 of 38
`
`Page 5 of 38
`
`

`

`M-0036 U.S.
`
`FIG. 3B is a diagram of an exemplary multi-stage symmetrical network of five
`
`stages with N = 8 and d = 2, rearrangeably nonblocking network for unicast connections,
`
`in accordance with the invention.
`
`FIG. 3C is a diagram of an exemplary multi-stage symmetrical Benes network
`
`(built using back-to-back Banyan Networks or back-to-back Delta Networks or
`
`equivalently back-to—back Butterfly networks) of five stages with N = 8 and d = 2,
`
`rearrangeably nonblocking network for unicast connections.
`
`FIG. 3D is a diagram of an exemplary multi-stage symmetrical network of five
`
`stages with N = 8 and d = 2, rearrangeably nonblocking network for unicast connections,
`
`10
`
`in accordance with the invention.
`
`FIG. 3E is a diagram of an exemplary multi-stage symmetrical Flip network (also
`
`known as inverse shuffle exchange network) of five stages with N = 8 and d = 2,
`
`rearrangeably nonblocking network for unicast connections.
`
`FIG. 3F is a diagram of an exemplary multi-stage symmetrical Baseline network
`
`of five stages with N = 8 and d = 2, rearrangeably nonblocking network for unicast
`connections.
`
`FIG. 36 is a diagram of an exemplary multi-stage symmetrical network of five
`
`stages with N = 8 and d = 2, rearrangeably nonblocking network for unicast connections,
`
`in accordance with the invention.
`
`FIG. 3H is a diagram of an exemplary multi-stage symmetrical Benes network
`
`(built using back-to-back Omega Networks) of five stages with N = 8 and d = 2,
`
`rearrangeably nonblocking network for unicast connections.
`
`15
`
`20
`
`FIG. 31 is a diagram of a general symmetrical multi-stage network with
`
`(2x logd N)—1 stages rearrangeably nonblocking network for unicast connections in
`
`25
`
`accordance with the invention.
`
`Page 6 of 38
`
`Page 6 of 38
`
`

`

`M-0036 U.S.
`
`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. 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
`
`10
`
`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
`
`15
`
`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.
`
`20
`
`25
`
`30
`
`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
`
`-3-
`
`Page 7 of 38
`
`Page 7 of 38
`
`

`

`(I
`
`H.
`
`M0036 U.S,
`
`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.
`
`Referring to FIG. 1A, an exemplary symmetrical multi-stage network 100 'with
`
`five stages of thirty two switches for satisfying communication requests, such as setting
`
`up a telephone call or a data call, 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 181-184 and output stage 120 consists of four, four by two switches 051-
`
`084. 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 130 are of size two by four, the
`
`switches in output stage are of size four by two, and there are eight switches in the 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 130 are of size two by four, the switches in output stage are of size four by
`
`two, and there are eight switches in the middle stage 130, middle stage 140 and middle
`
`stage 150.
`
`In one embodiment of this network each of the input switches 181-184 and output
`
`switches OSl—OS4 are crossbar switches. The number of switches of input stage 110 and
`
`ofoutput 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 x % . The size ofeach input switch ISl-IS4 can be denoted in general
`
`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 t 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
`
`multi-stage network can be represented with the notation V(N, d, s) , where N represents
`
`.4-
`
`10
`
`15
`
`20
`
`25
`
`Page 8 of 38
`
`Page 8 of 38
`
`

`

`M0036 US.
`
`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-IL8 as there are outlet links OLl-OL8, in a symmetrical network they are the same.
`
`Each ofthe % input switches ISl - 184 are connected to exactly 2 x d switches
`
`in middle stage 130 through 2 x d links (for example input switch 181 is connected to
`
`middle switches MS(1,1), MS(1,2), MS(l,5) and MS(1,6) through the links ML(l,l),
`
`ML(1,2), ML(1,3) and ML(1,4) respectively).
`
`10
`
`15
`
`Each ofthe 2 x 1:— middle switches MS(1,1) — MS(1,8) in the middle stage 130
`
`are connected from exactly d input switches through d links (for example the links
`
`ML(l,l) and ML(l,l4) are connected to the middle switch MS(1,1) from input switch 181
`
`and 184 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 ofthe 2 x % 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,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
`exactly d switches in middle stage 150 through d links (for example the links ML(3,1)
`
`20
`
`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 ofthe 2 x 1:- middle switches MS(3,1) — MS(3,8) in the middle
`
`stage 150 are connected from exactly d switches in middle stage 140 through d links
`
`25
`
`(for example the links ML(3, 1) and ML(3,8) are connected to the middle switch MS(3,1)
`
`from middle switches MS(2,1) and MS(2,4) respectively) and also are connected to
`
`exactly d output switches in output stage 120 through d links (for example the links
`
`-5-
`
`Page 9 of 38
`
`Page 9 of 38
`
`

`

`M0036 US.
`
`ML(4,1) and ML(4,2) are connected to output switches OS] and 082 respectively from
`
`middle switches MS(3,1)).
`
`Each ofthe 71} output switches 08] - 084 are connected from exactly 2 x d
`
`switches in middle stage 150 through 2 x d links (for example output switch 081 is
`
`connected from middle switches MS(3,1), MS(3,4), MS(3,5) and MS(3,8) through the
`
`links ML(4,1), ML(4,2), ML(4,3) and ML(4,4) respectively).
`
`10
`
`15
`
`20
`
`25
`
`Each ofthe links ML(l,l) — ML(1,16), ML(2,1) — ML(2,16), ML(3,1) — ML(3,l6)
`
`and ML(4,1) — ML(4,16) are either available for use by a new connection or not available
`
`if currently used by an existing connection. The input switches ISl-IS4 are also referred
`
`to as the network input ports. The input stage 110 is often referred to as the first stage.
`
`The output switches OSl-OS4 are also referred to as the network output ports. The
`
`output stage 120 is ofien referred to as the last stage. The middle stage switches MS(1,1)
`
`— MS(1,8), MS(2,1) — MS(2,8), and MS(3, 1) — MS(3,8) are referred to as middle switches
`
`or middle ports.
`
`In the example illustrated in FIG. 1A, a fan—out of four is possible to satisfy a
`
`multicast connection request if input switch is ISZ, but only two middle stage switches
`
`will be used. Similarly, although a fan-out of three is possible for a multicast connection
`
`request if the input switch is 181, again only a fan-out of two is used. The specific middle
`
`switches that are chosen when selecting a fan-out of two is irrelevant so long as at most
`
`two middle switches are selected to ensure that the connection request is satisfied, i.e. the
`
`destination switches identified by the connection request can be reached from the middle
`
`switches that are part of the selected fan-out. In essence, limiting the fan-out from input
`
`switch to no more than two middle switches permits the network 100 to be operated in
`
`rearrangeably nonblocking manner in accordance with the invention.
`
`The connection request of the type described above can be unicast connection
`
`request, a multicast connection request or a broadcast connection request, depending on
`
`the example. In case of a unicast connection request, a fan-out of one is used, Le. a single
`
`middle stage switch is used to satisfy the request. Moreover, although in the above-
`
`described embodiment a limit of two has been placed on the fan-out into the middle stage
`
`.6.
`
`Page 10 of38
`
`Page 10 of 38
`
`

`

`M-0036 U.S.
`
`switches, the limit can be greater depending on the number of middle stage switches in a
`
`network (while maintaining the rearrangeably nonblocking nature of operation of the
`
`network for multicast connections). Any arbitrary fan-out may be used between each
`
`middle stage switch and the output stage switches, and also any arbitrary fan-out may be
`
`used within each output stage switch, to satisfy the connection request.
`
`Network 200 of FIG. 13 is an example of general symmetrical multi-stage
`
`network V(N, d, s) with (2 x logd N)—1 stages. The general symmetrical multi-stage
`
`network V(N,d, s) can be operated in rearrangeably nonblocking manner for multicast
`
`when s = 2 according to the current invention. Also the general symmetrical multi-stage
`
`network V(N, d, s) can be operated in strictly nonblocking manner for unicast if
`
`s = 2 according to the current invention. (and in the example of FIG. 1B, 5 = 2). The
`
`general symmetrical multi-stage network V(N,d,s) with (2 x logd N)— 1 stages has d
`
`inlet links for each of % input switches [SI-IS(N/d) (for example the links ILl-IL(d) to
`
`the input switch 181) and 2 x d outgoing links for each of ~13;— input switches IS l-IS(N/d)
`
`(for example the links ML(1,1) - ML(1,2d) to the input switch 181). There are d outlet
`
`links for each of % output switches OSl-OSCN/d) (for example OLl-OL(d) to the output
`
`switch 081) and 2 x d incoming links for each of % output switches OSl-OS(N/d) (for
`
`example ML(2 x Long —- 2,1) - ML(2 x Long — 2,2 x d) to the output switch 0S1).
`
`Each ofthe 33— input switches 15] — IS(N/d) are connected to exactly 2 x d
`
`switches in middle stage 130 through 2 x d links (for example input switch [81 is
`
`connected to middle switches MS(l ,l) - MS(l ,d) through the links ML(1,1) - ML(l,d)
`
`and to middle switches MS(l,N/d) — MS(l ,{N/d}+d) through the links ML(1 ,d+])) —
`
`ML(1,2d) respectively, not shown in FIG. 18.).
`
`10
`
`15
`
`20
`
`Page 11 of 38
`
`Page 11 of 38
`
`

`

`"
`
`M0036 U.S.
`
`Each ofthe 2 x ~13;— middle switches MS(1,1) — MS(l,2N/d) in the middle stage
`
`130 are connected from exactly d input switches through d links and also are connected
`
`to exactly d switches in middle stage 140 (not shown in FIG. 13) through d links.
`
`Similarly each ofthe 2 x % middle switches MS(Long—IJ) -
`
`5 MS(Long —1,2 x%) in the middle stage 130+10*(L0ng — 2) are connected from
`
`exactly d switches in middle stage 130 +10 * (Long —3) (not shown FIG. 13) through
`
`d links and also are connected to exactly d switches in middle stage
`
`130 +10 * (Long - 1) (not shown FIG. 1B) through d links.
`
`Similarly each ofthe 2 x {:1 middle switches MS(2x Long — 3,1) -
`
`10 MS(2 x 1.0ng —3,2 x%) in the middle stage 130 +10 * (2 * Long — 4) are connected
`
`from exactly (I switches in middle stage 130 +10 * (2 * Long - 5) (not shown FIG. 1B)
`
`through d links and also are connected to exactly of output switches in output stage 120
`
`through d links.
`
`Each ofthe g— output switches OSl — OS(N/d) are connected from exactly 2 x d
`
`15
`
`switches in middle stage 130+ 10 "‘ (2 * Long -4) through 2 x d links.
`
`The general symmetrical multi-stage network V(N, d, s) can be operated in
`
`rearrangeably nonblocking manner for multicast when s = 2 according to the current
`
`invention. Also the general symmetrical multi~stage network V(N,d,s) can be operated
`
`in strictly nonblocking manner for unicast if s = 2 according to the current invention.
`
`20
`
`Every switch in the multi-stage networks discussed herein has multicast
`
`capability. In a V(N,d, 5) network, if a network inlet link is to be connected to more
`
`than one outlet link on the same output switch, then it is only necessary for the
`
`corresponding input switch to have one path to that output switch. This follows because
`
`-3-
`
`Page 12 0f38
`
`Page 12 of 38
`
`

`

`M-0036 US.
`
`that path can be multicast within the output switch to as many outlet links as necessary.
`
`Multicast assignments can therefore be described in terms of connections between input
`
`switches and output switches. An existing connection or a new connection from an input
`
`switch to r' output switches is said to have fan-out r'. If all multicast assignments of a
`
`first type, wherein any inlet link of an input switch is to be connected in an output switch
`
`to at most one outlet link are realizable, then multicast assignments of a second type,
`
`wherein any inlet link of each input switch is to be connected to more than one outlet link
`
`in the same output switch, can also be realized. For this reason, the following discussion
`
`is limited to general multicast connections ofthe first type (with fan-out r' ,
`
`l s r's 9;)
`
`10
`
`although the same discussion is applicable to the second type.
`
`To characterize a multicast assignment, for each inlet link is {l,2,...,%}, let
`
`1,. = 0, where 0 c {l,2,...,%} , denote the subset ofoutput switches to which inlet link i
`
`is to be connected in the multicast assignment. For example, the network of Fig. 1A
`
`shows an exemplary five-stage network, namely V(8,2,2) , with the following multicast
`
`assignment I1 = {2,3}and all other Ij z ¢ forj = [1-8]. It should be noted that the
`
`connection Il fans out in the first stage switch 181 into the middle switches MS(l, l) and
`
`MS(1,5) in middle stage 130, and fans out in middle switches MS(l,l) and MS(1,5) only
`
`once into middle switches MS(2,1) and MS(2,5) in middle stage 140.
`
`The connection II also fans out in middle switches MS(2,l) and MS(2,5) only
`
`once into middle switches MS(3,1) and MS(3,6) in middle stage 150. The connection 11
`
`also fans out in middle switches MS(3,1) and MS(3,6) only once into output switches
`
`082 and 083 in output stage 120. Finally the connection I1 fans out once in the output
`
`stage switch 082 into outlet link 0L3 and in the output stage switch 083 twice into the
`
`outlet links 0L5 and 0L6.
`
`In accordance with the invention, each connection can fan
`
`out in the first stage switch into at most two middle stage switches.
`
`15
`
`20
`
`25
`
`Page 13 of 38
`
`Page 13 of 38
`
`

`

`‘1
`
`M-0036 U.S.
`
`Referring to FIG. 2A, an exemplary symmetrical multi-stage network 300 with
`
`five stages of forty four switches for satisfying communication requests, such as setting
`
`up a telephone call or a data call, 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
`
`six switches 181-184 and output stage 120 consists of four, six by two switches OSl-OS4.
`
`And all the middle stages namely middle stage 130 consists of twelve, two by two
`
`switches MS(1,1) — MS(1,12), middle stage 140 consists of twelve, two by two switches
`
`MS(2,1) - MS(2,12), and middle stage 150 consists of twelve, two by two switches
`
`MS(3,1) — MS(3,12).
`
`Such a network can be operated in strictly nonblocking manner for multicast
`
`connections, because the switches in the input stage 130 are of size two by six, the
`
`switches in output stage are of size six by two, and there are twelve switches in the
`
`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
`
`ofoutput 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 3 x 71} . The size ofeach input switch 181 -IS4 can be denoted in general
`
`with the notation d 4. 3d and each output switch OSl-OS4 can be denoted in general with
`
`the notation 3d * 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
`
`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
`
`[Ll-1L8 as there are outlet links OLl-OLS, in a symmetrical network they are the same.
`
`10
`
`15
`
`20
`
`25
`
`-10-
`
`Page 14 0f38
`
`Page 14 of 38
`
`

`

`M4W36US.
`
`Each ofthe 1:1: input switches I81 — 184 are connected to exactly 3 x d switches
`
`in middle stage 130 through 3 x d links (for example input switch 151 is connected to
`
`middle switches MS(1,1), MS(1,2), MS(1,5), MS(1,6), MS(1,9) and MS(1,10) through
`
`the links ML(1,1), ML(l,2), ML(1,3), ML(1,4), ML(1,5) and ML(1,6) respectively).
`
`Each ofthe 3 x % middle switches MS( 1, l) - MS(l, 12) in the middle stage 130
`
`are connected from exactly d input switches through d links (for example the links
`
`ML(l, l) and ML(l,20) are connected to the middle switch MS(1,l) from input switch 181
`
`and 184 respectively) and also are connected to exactly a' switches in middle stage 140
`
`through d links (for example the links ML(2,l) 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 ofthe 3 x 1:— middle switches MS(2,1) — MS(2,12) 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,8) are connected to the middle switch MS(2,1)
`
`fi‘om middle switches MS(1,1) and MS(1,4) respectively) and also are connected to
`
`exactly d 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,2) respectively).
`
`Similarly each ofthe 3 x % middle switches MS(3,1) — MS(3,12) in the middle
`
`stage 150 are connected from exactly d switches in middle stage 140 through d links
`
`(for example the links ML(3, l) and ML(3,8) are connected to the middle switch MS(3,1)
`
`from middle switches MS(2, 1) and MS(2,4) respectively) and also are connected to
`
`exactly d 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 OS] and 082 respectively from
`
`middle switch MS(3,1)).
`
`10
`
`15
`
`20
`
`25
`
`Each ofthe % output switches 08] — 084 are connected from exactly 3 x d
`
`switches in middle stage 150 through 3 x d links (for example output switch 081 is
`
`-1]-
`
`Page 15 of 38
`
`Page 15 of 38
`
`

`

`MJMBGUS.
`
`connected from middle switches MS(3,1), MS(3,4), MS(3,—5), MS(3,8), MS(3,9) and
`
`MS(3,12) through the links ML(4,1), ML(4,2), ML(4,3), ML(4,4), ML(4,5) and ML(4,6)
`
`respectively).
`
`Each of the links ML(1,1) — ML(1,24), ML(2,1) — ML(2,24), ML(3,1) — ML(3,24)
`
`and ML(4,1) — ML(4,24) are either available for use by a new connection or not available
`
`if currently used by an existing connection. The input switches ISl-IS4 are also referred
`
`to as the network input ports. The input stage 1 10 is often referred to as the first stage.
`
`The output switches OS] -OS4 are also referred to as the network output ports. The
`
`output stage 120 is often referred to as the last stage. The middle stage switches MS(l, l)
`
`—- MS(1, 12), MS(2,]) — MS(2,12), and MS(3,1) ~ MS(3,12) are referred to as middle
`
`switches or middle ports.
`
`In the example illustrated in FIG. 1A, a fan-out of four is possible to satisfy a
`
`multicast connection request if input switch is 182, but only two middle stage switches
`
`will be used. Similarly, although a fan-out of three is possible for a multicast connection
`
`request if the input switch is IS], again only a fan-out of two is used. The specific middle
`
`switches that are chosen when selecting a fan-out of two is irrelevant so long as at most
`
`two middle switches are selected to ensure that the connection request is satisfied, i.e. the
`
`destination switches identified by the connection request can be reached from the middle
`
`switches that are part of the selected fan-out. In essence, limiting the fan-out from input
`
`switch to no more than two middle switches permits the network 300 to be operated in
`
`rearrangeably nonblocking manner in accordance with the invention.
`
`The connection request of the type described above can be unicast connection
`
`request, a multicast connection request or a broadcast connection request, depending on
`
`the example. In case of a unicast connection request, a fan-out of one is used, Le. a single
`
`middle stage switch is