available under
`Document made
`Patent Cooperation Treaty (PCT)
`
`the
`
`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/905 ,526
`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) - Genéve, Suisse
`
`Page 1 of 38
`
`FLEX LOGIX EXHIBIT 1013
`
`Page 1 of 38
`
`FLEX LOGIX EXHIBIT 1013
`
`

`

`SRR=SNwin.
`sx
`\
`a eeeees~reserceWOee
`
`SL v
`
`:
`
`SSS
`
`.
`
`ee
`
`DEPARTMENT OF COMMERCE
`
`United States Patent anc Trademark Ofvice
`
`March 29, 2008
`
`Patent and Trademark Office
`
`THIS IS TO CERTIFY THAT ANNEXED HERETOIS A TRUE COPY FROM
`THE RECORDSOF THE UNITED STATES PATENT AND TRADEMARK
`OFFICE OF THOSE PAPERS OF THE BELOW IDENTIFIED PATENT
`APPLICATION THAT MET THE REQUIREMENTSTO 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
`NR
`tN W.
`Na
`%
`
`:
`
`Under Secretary of Commerce
`for InteHectual Property
`aad Director af the Lnited States
`
`Page 2 of 38
`
`Page 2 of 38
`
`€
`

`

`v
`
`
`
`
`
`Given Name(first and middle [if any)
`
`Family Name or Sumame
`
`Residence
`and either State or Foreign Count
`
`ity
`
`separately numbered sheets attached hereto
`TITLE OF THE INVENTION (500 characters max):
`;
`
`:
`
`Direct ail correspondence to:
`
`CORRESPONDENCE ADDRESS
`
`PTO/S8/16 (02-07)
`Approved for use through 02/28/2007. OMB 0651-0032
`U.S.Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of 1995, no persons are required to respondto a collection of information unless it displays a valid OMBcontrol number. U.S. PTO
`PROVISIONAL APPLICATION FOR PATENT COVER SHEET- Page 1 of 2
`60/905526
`This is a requestforfiling a PROVISIONAL APPLICATION FOR PATENT under 37 CFR 1.53(c).
`DExpress Mail Label No.___ER 899 369 144 US
`03/06/2007 |
`
`
`
`SNL9E9L
`
`
`pkomte|SanHose, CA
`
`
`
`
` Additional inventors are being named on the
`
`
`OR
`
`The address corresponding to Customer Number.
`Firm or
`\
`
`Individual Name '@ak Networks, Inc.
`Address §278, Grand Oak Way
`
`38130
`
`;
`
`[Elo sasemona
`
`com
`
`
`
`
`
`
`
`Telephon 408-472-3273
`ENCLOSED APPLICATION PARTS (check all that apply)
`
`
`| Application Data Sheet. See 37 CFR 1.76
`CO CD(s), Number of CDs
`vv) Drawing(s) NumberofSheets 14
`CJ Other(specify
`
`
`
`
`
`
`20
`Specification (e.g. description of the invention) Number of Pages
`If the specification and drawings exceed 100 sheets of paper, an application size feeis
`Fees Due:Filing Fee of $200 ($100 for smail entity).
`also due, which is $250 ($125 for smail entity) for each additional 50 sheets orfraction thereof. See 35 U.S.C. 41(a)(1)(G) and 37 CFR 1.16(s).
`
`
`
`
`
`METHOD OF PAYMENT OF THE FILING FEE AND APPLICATION SIZE FEE FOR THIS PROVISIONAL APPLICATION FOR PATENT
`
`Applicant claims small entity status. See 37 CFR 1.27.
`$100.00
`A check or money orderis enclosed to cover thefiling fee and application size fee (if applicable).
`TOTAL FEE AMOUNT ($)
`Paymentby credit card. Form PTO-2038is attached
`The Director is hereby authorized to chargethefiling fee and application size fee (if applicable) or credit any overpayment to Deposit
`
`Account Number:
`- Aduplicative copy of this form is enclosed for fee processing.
`USE ONLY FOR FILING A PROVISIONAL APPLICATION FOR PATENT
`This collection of information is required by 37 CFR 1.51. The informationis fequired 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 U.S.C. 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 amourt of time you require to complete this form and/or suggestions for reducing this burden, should be sent to the Chief Information Officer, U.S. Patent
`and Trademark Office, U.S. Department of Commerce, P.O. Box 1450, Alexandria, VA 22313-1450. DO NOT SEND FEES OR COMPLETED FORMSTO THIS
`ADDRESS. SEND TO: Commissionerfor Patents, P.O. Box 1450, Alexandria, VA 22313-1460.
`#fyou need assistance in completing the form, call 1-800-PTO-9199 and select option 2.
`
`
`
`Page 3 of 38
`
`Page 3 of 38
`
`

`

`PROVISIONAL APPLICATION COVER SHEET
`Page 2 of 2
`
`PTO/SB/16 (02-07)
`Approved for use through 02/26/2007. OMB 0651-0032
`U.S. Patent and Trademark Office; U.S. 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 OMBcontro! number.
`
`Theinvention was made by an agency of the United States Government or under a contract with an agency of the United States Government.
`No.
`
`Cj Yes, the name of the U.S. Government agency and the Governmentcontract numberare:
`
`WARNING:
`Petitioner/applicant is cautioned to avoid submitting personal information in documentsfiled 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 orcredit card authorization form PTO-2038 submitted for paymentpurposes)is never required by
`the USPTOto support a petition or an application.
`If this type of personalinformation 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 madein 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 card
`authorization forms PTO-2038 submitted for payment purposes are not retained in the application file and therefore are not
`publicly available.
`SIGNATURE
`hen~
`Date_3/6/2007
`
`TYPED or PRINTED NAME Venkat Konda
`
`REGISTRATION NO.
`(if appropriate)
`
`TELEPHONE 408-472-3273
`
`Docket Number: M-0036 US
`
`Page 4 of 38
`
`Page 4 of 38
`
`

`

`wr.
`
`.
`
`M-0036 U.S.
`
`
`
`ER 899 369 144 US
`
`NO:|
`
`
`
`LARGE SCALE CROSSPOINT REDUCTION WITH NONBLOCKING
`
`UNICAST & MULTICAST IN ARBITRARILY LARGE MULTI-STAGE
`
`NETWORKS
`
`Venkat Konda
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`FIG. 1A 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 connections and rearrangeably nonblocking network for
`
`arbitrary fan-out multicast connections, in accordance with the invention.
`
`5
`
`10
`
`FIG. 1B is a diagram of a general symmetrical multi-stage network with
`(2xlog, 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. 2A is a diagram of an exemplary multi-stage symmetrical network offive
`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. 2B1 & FIG. 2B2 is a diagram of a general symmetrical multi-stage network
`with (2 xlog, NV)-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
`
`-1-
`
`Page 5 of 38
`
`Page 5 of 38
`
`

`

`M-0036 U.S.
`
`FIG. 3B is a diagram of an exemplary multi-stage symmetrical network offive
`
`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
`
`15
`
`of five stages with N = 8 and d = 2, rearrangeably nonblocking network for unicast
`connections.
`
`FIG. 3G 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.
`
`20
`
`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.
`
`FIG. 31 is a diagram of a general symmetrical multi-stage network with
`(2x log, V)—1 stages rearrangeably nonblocking network for unicast connections in
`
`25
`
`accordance with the invention.
`
`-2-
`
`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 oflarge scale
`crosspoint reductionusing 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 equalto two offer large scale crosspoint reduction
`whenconfigured with optimal links as disclosed in this invention.
`
`10
`
`Whena transmitting device simultaneously sends information to more than one
`receiving device, the one-to-many connection required between the transmitting device
`andthe 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. Whena transmitting device
`simultaneously sends informationto all the available receiving devices, the one-to-all
`connection required between the transmitting device and the receiving devicesis 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 ofarbitrary 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 networksofthe 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 someof 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
`
`

`

`a
`
`ica
`
`M-0036 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 assetting
`up a telephonecall 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 IS1-IS4 and output stage 120 consists of four, four by two switches OS1-
`OS4. Andall the middie 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@,8).
`
`Such a network can be operatedin 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 ofsize two byfour, the switchesin 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.
`
`10
`
`15
`
`20
`
`In one embodimentofthis network each of the input switches IS1-IS4 and output
`
`switches OS1-OS4are crossbar switches. The numberof switches of input stage 110 and
`
`ofoutput stage 120 can be denoted in general with the variable = , where WN isthetotal
`
`numberofinlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by 2x - . The size ofeach input switch [S1-IS4 can be denoted in general
`
`25
`
`with the notation d *2d 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
`multi-stage network can be represented with the notation V(N,d,s), where N represents
`
`-4-
`
`Page 8 of 38
`
`Page 8 of 38
`
`

`

`M-0036 U.S.
`
`the total numberofinlet 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 numberof outgoing links from each input switchto the inlet links of each
`input switch. Although it is not necessary that there bethe same numberofinlet links
`IL1-IL8as there are outlet links OL1-OL8, in a symmetrical network they are the same.
`
`Eachofthe - input switches IS] — IS4 are connected to exactly 2x d switches
`
`in middle stage 130 through 2xdlinks (for example input switch IS1 is connected to
`middle switches MS(1,1), MS(1,2), MS(1,5) and MS(1,6) through the links ML(1,1),
`
`10
`
`15
`
`20
`
`25
`
`ML(1,2), ML(1,3) and ML(1,4)respectively).
`
`Each ofthe 2x = 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(1,1) and ML(1,14) are connected to the middle switch MS(1,1) from input switch IS1
`
`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(i,1) to middie 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)
`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 x
`
`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
`(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 examplethe links
`
`-5-
`
`Page 9 of 38
`
`Page 9 of 38
`
`

`

`M-0036 U.S.
`
`ML(4,1) and ML(4,2) are connected to output switches OS1 and OS2 respectively from
`
`middle switches MS(3,1)).
`
`Each ofthe a output switches OS1 —OS4 are connected from exactly 2x d
`
`switches in middle stage 150 through 2d links (for example output switch OS1 is
`
`connected from middie switches MS(3,1), MS(3,4), MSG,5) and MS(3,8) through the
`
`links ML(4,1), ML(4,2), ML(4,3) and ML(4,4) respectively).
`
`Eachofthe links ML(1,1) — ML(1,16), ML(2,1) — ML(2,16), ML(3,1) —- ML(3,16)
`
`and ML(4,1) — ML(4,16) are either available for use by a new connectionor not available
`
`if currently used by an existing connection. The input switches IS1-IS4 are also referred
`
`10
`
`to as the network input ports. The input stage 110 is often referred to as the first stage.
`
`The output switches OS1-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(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.
`
`15
`
`In the example illustrated in FIG. 1A, a fan-out of four is possible to satisfy a
`
`multicast connection request if input switch is IS2, 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 IS1, 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
`
`20
`
`two middle switches are selected to ensure that the connection requestis satisfied, i.e. the
`
`destination switches identified by the connection request can be reached from the middle
`
`switchesthat 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.
`
`25
`
`The connection request ofthe 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 oneis used, i.e. 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 of 38
`
`Page 10 of 38
`
`

`

`aw
`
`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. 1B is an example of general symmetrical multi-stage
`network V(N,d,s) with (2x log, N)—1stages. 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
`
`10
`
`network V(N, d,s) can be operated in strictly nonblocking mannerfor unicast if
`
`s = 2 accordingto the current invention. (and in the example of FIG. 1B, s = 2). The
`general symmetrical multi-stage network V(N,d,s) with (2x log, N)- 1 stages has d
`inlet links for each of : input switches IS1-IS(N/d) (for example the links IL1-IL(d) to
`the input switch IS1) and 2xd outgoing links for each of — input switches IS1-IS(CN/d)
`
`15
`
`(for example the links ML(1,1) - ML(1,2d) to the input switch IS1). There are d outlet
`
`links for each of : output switches OS1-OS(N/d) (for example OL1-OL(d) to the output
`switch OS1) and 2x d incoming links for each of ‘ output switches OS1-OS(N/d) (for
`
`example ML(2 x Log,N — 2,1) - ML(2x Log, N — 2,2 d) to the output switch OS 1).
`
`Each ofthe “ input switches IS1 — ISQN/d) are connected to exactly 2x d
`
`20
`
`switches in middle stage 130 through 2xd links (for example input switch IS1 is
`
`connected to middle switches MS(1,1) - MS(1,d) through the links ML(1,1) - ML(1,d)
`
`and to middle switches MS(1,N/d) — MS(1, {N/d}+d) through the links ML(,d+1)) —
`
`ML(1,2d) respectively, not shown in FIG. 1B.).
`
`-7-
`
`Page 11 of 38
`
`Page 11 of 38
`
`

`

`M-0036 U.S.
`
`Eachofthe 2x . middle switches MS(1,1) —MS(1,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. 1B) through d links.
`
`Similarly each ofthe 2 “ middle switches MS(Log,N—1,1) -
`MS(Log,N-1,2=) in the middle stage 130+10*(Log,N—2) are connected from
`exactly d switches in middle stage 130+10* (Log, N —3) (not shown FIG. 1B) through
`
`d links and also are connected to exactly d@ switches in middle stage
`
`130+10*(Log,N —1) (not shown FIG. 1B) through d links.
`
`Similarly each ofthe 2 x = middle switches MS(2x Log,N—3,)) -
`MS(2x Log,N—3,2x=) in the middle stage 130+10*(2*Log,N—4) are connected
`from exactly d switches in middle stage 130 +10*(2* Log, N —5) (not shown FIG. 1B)
`
`10
`
`through d links andalso are connected to exactly d output switches in output stage 120
`
`through d links.
`
`Eachofthe ‘ output switches OSI — OS(N/d) are connected from exactly 2x d
`
`15
`
`switches in middle stage 130+10*(2* Log,N —4) through 2x d links.
`
`The general symmetrical multi-stage network V(N,d,5) 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. Ina V(N,d,s) 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
`
`-8-
`
`Page 12 of 38
`
`Page 12 of 38
`
`

`

`M-0036 U.S.
`
`that path can be multicast within the output switch to as manyoutlet 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 switchesis said to have fan-out r’. If all multicast assignments of a
`
`first type, wherein anyinlet 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 anyinlet 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
`
`see
`.
`:
`.
`N
`is limited to general multicast connections ofthe first type (with fan-out r', 1 <7'< 7
`
`10
`
`although the samediscussion is applicable to the second type.
`
`To characterize amulticastassignment, foreach inlet link /€ {2.0}, let
`I, =O, where Oc {12.424}, denote the subset ofoutput switches to which inlet link 7
`
`is to be connected in the multicast assignment. For example, the network of Fig. 1A
`
`showsan exemplary five-stage network, namely V(8,2,2), with the following multicast
`assignment J, = {2,3}and all other 7, = ¢ for j =[1-8]. It should be noted that the
`
`15
`
`connection /, fans out in the first stage switch IS] into the middle switches MS(1,1!) and
`
`MS(1,5) in middle stage 130, and fans out in middle switches MS(1,1) and MS(1,5) only
`
`once into middle switches MS(2,1) and MS(2,5) in middle stage 140.
`
`The connection J, also fans out in middle switches MS(2,1) and MS(2,5) only
`
`20
`
`once into middle switches MS(3,1) and MS(3,6) in middle stage 150. The connection J,
`
`also fans out in middle switches MS(3, 1) and MS(3,6) only once into output switches
`
`OS2 and OS3in output stage 120. Finally the connection 7, fans out once in the output
`
`stage switch OS2 into outlet link OL3 and in the output stage switch OS3 twice into the
`
`outlet links OL5 and OL6.
`
`In accordance with the invention, each connection can fan
`
`25
`
`outin the first stage switch into at most two middle stage switches.
`
`-9-
`
`Page 13 of 38
`
`Page 13 of 38
`
`

`

`“i
`
`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 telephonecall or a data call, between an input stage 110 and output stage 120 via
`middle stages 130, 140, and 150 is shown whereinput stage 110 consists of four, two by
`six switches IS1-IS4 and output stage 120 consists of four, six by two switches OS1-OS4.
`
`Andall 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).
`
`10
`
`Such a network can be operated in strictly nonblocking manner for multicast
`
`connections, because the switchesin 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 embodimentof this network each of the input switches IS1-1S4 and output
`
`15
`
`switches OS1-OS4 are crossbar switches. The numberof switches of input stage 110 and
`
`ofoutput stage 120 can be denoted in géneral with the variable - , where N is the total
`
`numberofinlet links or outlet links. The number of middle switches in each middle stage
`
`is denoted by 3x ‘ . The size ofeach input switch IS1-IS4 can be denoted in general
`
`with the notation d*3d and each output switch OS1-OS4 can be denoted in general with
`
`20
`
`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 numberofinlet links of all input switches (for example the links IL1-IL8), d
`
`25
`
`representsthe inlet links of each input switch or outlet links of each output switch, and s
`
`is the ratio of numberof outgoing links from each input switch to the inlet links of each
`
`input switch. Although it is not necessary that there be the same numberofinlet links
`
`IL1-IL8asthere are outlet links OL1-OL8, in a symmetrical network they are the same.
`
`-10-
`
`Page 14 of 38
`
`Page 14 of 38
`
`

`

`M-0036 U.S.
`
`Each ofthe : input switches IS1 —1S4 are connected to exactly 3x d switches
`
`in middle stage 130 through 3xd links (for example input switch IS1 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(1,2), MLC,3), ML(1,4), ML(1,5) and ML(1,6) respectively).
`
`Each ofthe 3x 4 middle switches MS(1,1) —- MS(1,12) in the middle stage 130
`
`are connected from exactly d input switches through d links (for example the links
`
`ML(1,1) and ML(1,20) are connected to the middle switch MS(1,1) from input switch IS1
`
`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
`
`10
`
`switch MS(1,1) to middle switch MS(2,1) and MS(2,2) respectively).
`
`Similarly each ofthe 3x= 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)
`
`from middle switches MS(1,1) and MS(1,4) respectively) and also are connected to
`
`15
`
`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
`
`20
`
`(for example the links ML(3,1) and ML@,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
`
`ML(4,1) and ML(4,2) are connected to output switches OS1 and OS2 respectively from
`
`middle switch MS(3,1)).
`
`25
`
`Each ofthe * output switches OS1 —OS4 are connected from exactly 3x d
`
`switches in middle stage 150 through 3xd links (for example output switch OS! is
`
`-ll-
`
`Page 15 of 38
`
`Page 15 of 38
`
`

`

`M-0036 US.
`
`connected from middle switches MS@G,1), MS(3,4), MS(3,5), MS(G3.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 ofthe links ML(1,1) — ML(1,24), ML@Q,1) —- ML(Q2,24), ML@G,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 IS1-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 OS1-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(1,1)
`
`10
`
`—~ MS(1,12), MS(2,1) — 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 IS2, but only two middle stage switches
`
`will be used. Similarly, although a fan-out of three is possible for a multicast connection
`
`15
`
`request if the input switch is IS1, again only a fan-out of two is used. The specific middle
`
`switches that are chosen whenselecting a fan-out of twois irrelevant so long as at most
`
`two middle switches are selected to ensure that the connection requestis 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
`
`20
`
`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, i.e. a single
`
`25
`
`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
`
`switches, the limit can be greater depending on the number of middle stage switches in a
`
`network (while maintainingthe strictly nonblocking nature of operation of the network
`
`for multicast connections). Any arbitrary fan-out may be used between each middle stage
`
`30
`
`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.
`
`-[2-
`
`Page 16 of 38
`
`Page 16 of 38
`
`

`

`M-0036 US.
`
`Network 400 of FIG. 2B1 is an example of general symmetrical multi-stage
`network V(N,d,s) with (2 xlog, NV)-1 stages. Network 400 of FIG. 2B1 contains