US007310333B1
`
`(12) United States Patent
`US 7,310,333 B1
`(10) Patent No.:
`Conklin et al.
`(45) Date of Patent:
`*Dec. 18, 2007
`
`(54) SWITCHING CONTROL MECHANISM FOR
`SUPPORTING RECONFIGUARATION
`WITHOUT INVOKING A REARRANGEMENT
`ALGORITHM
`
`(75)
`
`Inventors: Richard Conklin, Gainesville, GA
`(US); Jeflrey T. Gullicksen, Mountain
`View, CA (US)
`
`(73) Assignee: Ciena Corporation, Linthicum, MD
`(US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 911 days.
`
`This patent is subject to a terminal dis-
`claimer.
`
`(21) Appl. No.: 10/608,492
`
`(22)
`
`Filed:
`
`Jun. 30, 2003
`
`Related US. Application Data
`
`(60) Provisional application No. 60/392,461, filed on Jun.
`28, 2002.
`
`(51)
`
`Int. Cl.
`(2006.01)
`H01Q 11/00
`(52) US. Cl.
`....................................... 370/388; 370/390
`(58) Field of Classification Search ................ 370/254,
`370/388, 354; 340/221, 2.26; 385/17, 24
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`.................. 385/24
`4/1998 Wang et al.
`5,745,612 A *
`6/1999 Yoshifuji
`................... 340/226
`5,917,426 A *
`7/2000 Arzt
`.......................... 340/2.2l
`6,087,958 A *
`4/2003 Dragone ..............
`.. . 385/17
`6,542,655 B1*
`
`......... 370/388
`9/2006 Gullicksen et al.
`7,106,729 B1 *
`7,154,887 B2 * 12/2006 Wu et al.
`................... 370/388
`2005/0157713 A1*
`7/2005 Klausmeier et al.
`........ 370/388
`
`* cited by examiner
`
`Primary Examiner%hi Pham
`Assistant ExamineriAlbert T. Chou
`
`or FirmiClements Walker;
`(74) Attorney, Agent,
`Christopher L. Bernard; Tyler S. Brown
`
`(57)
`
`ABSTRACT
`
`Amethod of modeling or constructing a switch element uses
`an ingress stage with input sorters and input routers; an
`egress stage with output routers and output sorters; and a
`center stage interconnecting the ingress and egress stages.
`Routers are partitioned such that each partition is assigned to
`only one data line. A switch controller and method may use
`such modeling to advantage. For example, during initial
`configuration of the switch element, a subset of connections
`are excluded from a control algorithm that initially config-
`ures the switch with the subset being subjected to post
`processing. Furthermore, a fast rearrangement of the switch
`rearranges only part of the existing connections and then
`adds/deletes cross connects as necessary to complete the
`connections.
`
`4,926,416 A *
`
`5/1990 Weik .......................... 370/354
`
`35 Claims, 15 Drawing Sheets
`
`
`X215""""""""2'Is"""1/210
`
`Output Router
`Input Router
`
`1
`1
`
`
`
`
`Partition
`
`Lines
`
`226
`
`Output Router
`Input Router
`
`16
`
`
`
`
`Sorter
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Input Router
`Output Router
`497
`497
`
`
`
`
`
`226
`Output Router
`Input Router
`
`512
`
`
`
`512
`_24,,.
`
`
`
`
`Petitioner Huawei - Exhibit 1006, p. 1
`
`Petitioner Huawei - Exhibit 1006, p. 1
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 1 of 15
`
`US 7,310,333 B1
`
`
`
`9:1
`
`130
`
`140
`
`130
`
`ES,
`
`ESN
`
`
`
`
`
`
`
`CLOSNETWORK
`
`
`
`100
`/
`
`
`
`
` FIG.1a
`
`
`Petitioner Huawei - Exhibit 1006, p. 2
`
`Petitioner Huawei - Exhibit 1006, p. 2
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 2 of 15
`
`US 7,310,333 B1
`
`Logical SWitCh
`Controller
`
`Switch Control Module
`
`Output! lnput
`
`APS, VLSR I:
`TLSR and |
`UPSR
`
`Engines
`
`Sorter
`
`Manager
`
`Switch Control
`
`Algorithm
`
`Program
`Controller
`
`interfaces
`
`Figure 1b
`
`Petitioner Huawei - Exhibit 1006, p. 3
`
`Petitioner Huawei - Exhibit 1006, p. 3
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 3 of 15
`
`US 7,310,333 B1
`
`
`
`
`
`
`
`
`
`‘IVN_‘
`
`
`
`53:0
`
`Lmtom
`
`
`
`
`
`[IVN©—\
`
`Alp550m59:0
`
`
`
`wmm\mr_r
`
`
`
`
`
`"mmmatom"59:0
`
`
`
`
`ta5:mAl?550m5930
`
`
`
`
`
`
`
`8N
`
`
`
`
`
`mmm\\mmm
`
`CNN
`
`ENH..
`
`
`
`mtaNE_mAIF650$39:0
`oomNEmR550m59:m8NmmmmVNLatowm8:265:5059:u
`
`5:m550m59:mEN\\m
`
`
`
`
`
`
`
`
`
`_
`
`.N.9".
`
`Petitioner Huawei - Exhibit 1006, p. 4
`
`
`
`Em\\rmac:Stow_
`
`Egan.59;u
`
`ea;m
`
`
`
`
`
` —\VNim550$59:vim:53N\m
`
`
`
`
`
`
`
`Petitioner Huawei - Exhibit 1006, p. 4
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 4 of 15
`
`US 7,310,333 B1
`
`
`
`EACH ROUTER OF EACH INGRESS DEVICE IS ASSIGNED TO A
`
`310
`
`DATA LINE
`
`J/
`
`
`
`320
`
`330
`
`340
`
`EACH ROUTER OF EACH EGRESS DEVICE IS ASSIGNED TO A
`
`DATA LINE.
`
`
`
`
`
`_1
`
`LE
`
`ACH INGRESS ROUTER IS CONNECTED TO AN EDGE OF EACH
`
`CENTER STAGE DEVICE
`
` i
`
`EACH EGRESS ROUTER IS CONNECTED TO AN EDGE OF EACH /
`
`CENTER STAGE DEVICE
`
`
`
`FIG. 3a
`
`Petitioner Huawei - Exhibit 1006, p. 5
`
`Petitioner Huawei - Exhibit 1006, p. 5
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 5 of 15
`
`US 7,310,333 B1
`
`
`
`
`DETERMINE SUBSET 0F CONNECTIONS IN INITIAL
`CONFIGURATION TO EXCLUDE
`
`350
`
`
`
`
`
`EXECUTE CONTROL ALGORITHM TO ESTABLISH
`
`CONFIGURATION FOR SWITCH ELEMENTS FOR PT TO PT
`
`CONNECTIONS
`
`
`360
`
`
`__v
`
`370
`
`POST PROESSING FOR NON PT TO PT CONNECTIONS
`
`FIG. 3b
`
`Petitioner Huawei - Exhibit 1006, p. 6
`
`Petitioner Huawei - Exhibit 1006, p. 6
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 6 of 15
`
`US 7,310,333 B1
`
`
`DETECT FAILURE IN ONE OF THE CONNECTIONS IN THE SWITCH
`
`CONFIGURATION
`
`
`J
`
`400
`
`410
`
`IDENTIFY SPECIFIC CONNECTIONS ASSOCIATED WITH THE
`
`SWITCH EVENT THAT ARE REQUIRED TO BE CHANGED
`
`
`
`CONNECTIONS
`
`DELETE CROSS-CONNECTIONS AS REQUIRED TO COMPLETE
`
`
`
`_I_
`
`430
`
`ADD CROSS-CONNECTIONS AS REQUIRED TO COMPLETE /
`
`CONNECTIONS
`
`
`
`FIG. 4
`
`Petitioner Huawei - Exhibit 1006, p. 7
`
`Petitioner Huawei - Exhibit 1006, p. 7
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 7 of 15
`
`US 7,310,333 B1
`
`(510
`
`(530
`
` LINE MODULE
`
`FIG. 5
`
`Petitioner Huawei - Exhibit 1006, p. 8
`
`Petitioner Huawei - Exhibit 1006, p. 8
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 8 of 15
`
`US 7,310,333 B1
`
`_\
`
`r
`
`530m59:0550m39:
`
`vmnNvm
`
`
`mc_vto>>_\mc_vto>>
`w5991690$
` .mo.0."—
`.vN¢N
`
`
`550m59.10mwysom.‘Sac.
`
`I[w/,w\vN
`mwrmm:
`
`
`585%L950Lwfi‘om:55
`SOEISHwVwolu—va-”VN
`ENoTxx«N
`
`_\
`
`_\
`
`_\
`
`Petitioner Huawei - Exhibit 1006, p. 9
`
`Petitioner Huawei - Exhibit 1006, p. 9
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 9 of 15
`
`US 7,310,333 B1
`
`_,
`
`
`
`6991“mo>>m6?
`
`.nm.0."—
`
`VN«orax:E$50K59:050:255:60550m59:
`
`
`
`
`
`v-09690iHwo>>
`
`w,.9$35$N
`‘E28,,
`
`,Wknx,
`
`
`
`omELL[WMHWFEMN/wVN
`
`$50K59:
`
`NVN
`
`550$39:
`
`
`
`
`
` FWe?H.092;6mm.
`
`$50K59:
`
`mmvm
`
`$50K39:0530m59:
`
`mowm9,
`
`w
`
`Petitioner Huawei - Exhibit 1006, p. 10
`
`Petitioner Huawei - Exhibit 1006, p. 10
`
`
`
`
`
`

`

`U.S. Patent
`
`“oD
`
`00
`
`1f001m
`
`33,013,
`
`m
`
`«M‘v>.>
`2Qm32‘‘
`7‘v'
`
`620E“mam.
`
`_\
`
`vm,,,,,,,K1,
`Lflsom39.10
`
`vmw\
`
`550m5930\
`
`camsomSag
`\m\\\\\\
`
`3do.0."—
`
`5650m59:
`
`7|||||||Svm......worwmUcog/mL850@3quEgg.
`
`we
`
`
`
` ......F6981“we;
`
`Petitioner Huawei - Exhibit 1006, p. 11
`
`Petitioner Huawei - Exhibit 1006, p. 11
`
`
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 11 of 15
`
`US 7,310,333 B1
`
`
`
`FIG. 6d
`
`Petitioner Huawei - Exhibit 1006, p. 12
`
`Petitioner Huawei - Exhibit 1006, p. 12
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 12 of 15
`
`US 7,310,333 B1
`
`WOfking Timesbi is Dropped for Faikure at TLSR Link a
`IWWWEW "mes'omswsr
`° I'll-“II...“-i
`' III-I..."
`
`Flattenad pr
`
`g
`
`t
`
`i
`
` a.._.._.@myrm
`
`:
`
`FIG. Ge
`
`Petitioner Huawei - Exhibit 1006, p. 13
`
`Petitioner Huawei - Exhibit 1006, p. 13
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 13 of 15
`
`US 7,310,333 B1
`
`Input
`
`figure:
`_/" 53
`
`.,
`
`““““““ Master
`
`Output —1 —>
`Router
`
`104
`
`2”
`
`FIG. 7a
`
`Petitioner Huawei - Exhibit 1006, p. 14
`
`Petitioner Huawei - Exhibit 1006, p. 14
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 14 of 15
`
`US 7,310,333 B1
`
`Drop
` [:124+
`
`Center
`Switch
`24
`
`Router
`1 04
`
`24+
`
`1 —’
`
`24+
`Master
`1—>
`
`
`
`Output
`Router
`
`103
`734
`
`FIG. 7b
`
`Petitioner Huawei - Exhibit 1006, p. 15
`
`Petitioner Huawei - Exhibit 1006, p. 15
`
`

`

`U.S. Patent
`
`Dec. 18, 2007
`
`Sheet 15 of 15
`
`US 7,310,333 B1
`
`
`
`Petitioner Huawei - Exhibit 1006, p. 16
`
`Petitioner Huawei - Exhibit 1006, p. 16
`
`

`

`US 7,310,333 B1
`
`1
`SWITCHING CONTROL MECHANISM FOR
`SUPPORTING RECONFIGUARATION
`WITHOUT INVOKING A REARRANGEMENT
`ALGORITHM
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application claims the benefit of priority under 35
`U.S.C. § 119(e) to US. Provisional 60/392,461 Application
`Ser. No. filed on Jun. 28, 2002 the entirety of which is hereby
`incorporated by reference.
`
`FIELD OF THE INVENTION
`
`The present invention generally relates to a switching
`control mechanism for a switch element that interconnects
`
`high-speed data lines.
`
`BACKGROUND OF THE INVENTION
`
`Switches or switch elements are interconnected within a
`communication network in order to direct data from one
`
`point to another point within the network. Typically, each
`switch element has a plurality of inputs and a corresponding
`plurality of outputs. Network connections can be coupled to
`each of the switch element inputs and outputs. Typically,
`data carried on any input line of a switch element can be
`switched to any output line on the same switch element.
`Conventional switch devices typically use rearrangement or
`control algorithms, such as Paull’s algorithm or the Looping
`algorithm, to establish initial configurations for the switch
`element.
`
`Networks, however, do not remain fixed. Rather, fre-
`quently, some network connections are added, while others
`are dropped. Alternatively, data previously intended for one
`switch output line may be required to be shifted to another
`output line. In general, switching events output line may be
`required to be shifted to another output line. In general,
`switching events may occur, which would require the net-
`work connections across the switch element to be manipu-
`lated. Due to the number of connections across a single
`switching element, compensating for a switching event can
`be a complex and computationally intensive procedure.
`Examples of switching events include instances when net-
`work connections are added to a switch element already in
`use or instances when one of the links between network
`
`elements fails and another route through the network ele-
`ment is needed.
`
`When switching events require new connections to be
`formed, conventional switch elements must be reconfigured.
`Many switch elements comprise devices, which are grouped
`into one of three stages of a three stage Clos network (i.e.,
`within an ingress stage, a center stage or an egress stage). In
`response to switching events, typically, all of the switching
`devices in the Clos network (including those related to
`connections that are not directly affected by the switching
`event) need to be reconfigured to form new connections
`through the switch element.
`A conventional switch element in such a rearrangeable,
`non-blocking switching configuration typically requires
`considerable computational resources to accomplish recon-
`figuration of the switching devices within the switch element
`at the speed required by such standards as SONET (Syn-
`chronous Optical Network) or SDH (Synchronous Digital
`Hierarchy) which requires, for example, restoration switch
`events to be completed within 50 ms. Due to the complexi-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`ties of the algorithms used to establish such reconfigurations
`for switch elements, it can become even more difficult to
`repeatedly execute control algorithms in a manner that
`ensures switching events are compensated for while being
`transparent to the end-user. Conventional control algorithms
`are computationally intensive and can be intermittently
`unpredictable in temporal length to compute. As such, use of
`these algorithms for the purpose of performing rearrange-
`ments of switches with existing connections can result in
`unacceptable delays.
`One-way to speed the reconfiguration process is to pre-
`configure portions of the Clos network to support change.
`For example, the center stage of the Clos network can be
`pre-configured to include standby connections. The stand-by
`connections can be used to realize changes in the network to
`support various protocols (i.e., protection protocols) or
`otherwise allow for reconfiguration of the network element
`in response to a switching event. The stand-by connections
`can be quickly realized without having to run resource
`intensive rearrangement algorithms. However, such pre-
`configured connections require sufficient bandwidth in the
`center stage, such bandwidth that is unavailable for conven-
`tional operations (i.e., over-provisioned bandwidth, that is,
`bandwidth over and above necessary bandwidth to support
`point-to-point connections).
`Accordingly, there is a need for a new switching control
`mechanism, which provides for
`faster performance in
`response to switching events and does not require over-
`provisioned bandwidth.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The following drawings illustrate by way of example, and
`not by way of limitation, embodiments of the present
`invention in which like reference numerals refer to similar
`elements and in which:
`
`FIG. 1a is a block diagram illustrating a Clos network that
`has applications for switching control mechanisms.
`FIG. 1b is a block diagram illustrating a switch control
`module that has applications for switching control mecha-
`nisms.
`
`FIG. 2 is a block diagram illustrating a logical model for
`the Clos network of FIG. 1.
`
`FIG. 3a is a method for structuring a switch element to
`conform to the logical model of FIG. 2.
`FIG. 3b is a method for initializing connections in a
`switch element modeled in accordance with FIG. 311.
`
`FIG. 4 is a method for performing a fast rearrangement on
`a switch element having existing connections.
`FIG. 5 is a block diagram illustrating a switch control
`mechanism that
`includes a Clos network configured in
`accordance with the logical model shown in FIG. 2.
`FIG. 6a illustrates a method for performing a switchover
`from a working line to a protect line in a switch element
`configured to support APS 1+1.
`FIG. 6b illustrates a method for performing a switchover
`in response to a switch event in a switch element configured
`to support VLSR pass-through.
`FIG. 60 illustrates a method for performing a switchover
`in response to a switch event in a switch element configured
`to support TLSR.
`FIG. 6d shows a network configured to support TLSR that
`includes a failed link.
`
`FIG. 66 shows a TLSR drop table.
`FIG. 7a illustrates a method for performing a switchover
`in response to a switch event in a switch element configured
`to support UPSR for a drop connection.
`
`Petitioner Huawei - Exhibit 1006, p. 17
`
`Petitioner Huawei - Exhibit 1006, p. 17
`
`

`

`US 7,310,333 B1
`
`3
`FIG. 7b illustrates a method for performing a switchover
`in response to a switch event in a switch element configured
`to support UPSR for a drop connection.
`FIG. 70 shows a node in a network configured for UPSR
`including connections to two rings.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`In the following description, for the purposes of expla-
`nation, numerous specific details of an embodiment of the
`present invention are set forth in order to provide a thorough
`understanding of the present invention. It will be apparent,
`however, that the present invention may be practiced with-
`out some of these specific details.
`A. Terminology
`A switch element connects one set of data lines to another
`set of data lines. As described herein, the switch element
`may comprise ingress devices, center stage devices, and
`egress devices. Embodiments of the invention provide that
`the devices of the switch element form a Clos network.
`
`An ingress device is a component of the switch element
`that can be configured to switch incoming communications
`from one or more data lines to one or more selected center
`
`stage devices, or to one or more selected center stage device
`ports.
`An egress device is a component of the switch element
`that can be configured to switch communications from one
`or more center stage devices to one or more data lines that
`connect to the switch element.
`
`A center stage device is a component of the switch
`element
`that
`interconnects the ingress devices with the
`egress devices. One or more center stage devices may
`physically reside on a switch module (SM).
`Both ingress and egress devices may physically reside on
`a line module (LM) that is connected to a switch module
`SM. In one implementation, a line module LM comprises
`one ingress device and one egress device.
`A bank is a device programming memory that controls an
`ingress, egress, or center stage device. An ingress device, an
`egress device, and a center stage device may contain two
`banks, bank A and bank B, of memory used to program the
`device. A bank may be either the active bank or the standby
`bank. One of the banks will be the active bank and the other
`
`will be the standby bank. When bank A is the active bank,
`bank B is the standby bank. When bank B is the active bank,
`bank A is the standby bank. The active bank programming
`specifies the device programming currently applied to the
`device. The standby bank programming specifies a device
`programming to be used for the device programming at a
`future time. In one implementation, the ingress device, the
`egress device, and the center stage device all switch banks
`from active to standby (and standby to active) simulta-
`neously. In such an implementation, changes to the active
`bank programming memory immediately update the device
`while changes to the standby bank programming memory
`update the device at a later time when all
`the devices
`perform a coordinated bank switch.
`A router is a functional aspect of an ingress or egress
`device that connects that ingress/egress device to a selected
`center stage device or center stage device’s port.
`A sorter is a functional aspect of an ingress or egress
`device that connects a data line coupled to an ingress or
`egress device to a plurality of routers of that ingress or
`egress device.
`In one implementation, ingress, egress, and center stage
`devices are switches. These devices may be formed by a
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`combination of circuitry, memory, and multiplexers. Func-
`tional aspects of these devices, such as routers and sorters,
`may be implemented using internal components of the
`devices.
`
`An edge connection is a link between an ingress device
`and a center stage device, or between the center stage device
`and an egress device.
`A connection refers to interconnected components of a
`switch element that combine to enable one data line con-
`nected to one side of the switch element to communicate to
`another data line on another side of the switch element. Each
`
`connection may use an ingress device, a center stage device,
`and an egress device.
`A switching event is an event that causes one or more of
`the devices in a switching element
`to be reconfigured.
`Examples of switching events include a path failure, a line
`failure, or a component failure. The switching event may
`occur on the ingress side, the egress side, both the ingress
`and the egress sides, or internally in the switch element.
`B. Overview
`
`for illustrative purposes,
`In the following discussion,
`implementations of the invention will be described in the
`context of a 3-stage Clos network. It should be noted,
`however, that if so desired, the concepts taught herein may
`be applied to other switching configurations. Such applica-
`tions are within the scope of this invention.
`1. Physical Clos Network
`FIG. 1a is a block diagram illustrating a Clos network 100
`within a network element, such as a CoreDirector® switch
`manufactured by CIENA Corporation of Linthicum, Md.,
`that can have applications for switching control mecha-
`nisms. The Clos network 100 includes a plurality of ingress
`stage switches 110, a plurality of center stage switches 120,
`and a plurality of egress stage switches 130. A first set of
`edge connections (or edges) 112 connects the ingress stage
`switches 110 to the center stage switches 120. A second set
`of edges 132 connects the center stage switches 120 to the
`egress stage switches 130. Each edge 112 in the first set
`carries a certain amount of bandwidth. Likewise, each edge
`132 in the second set carries bandwidth. While edges 112,
`132 in each set are assumed to carry the same amount of
`bandwidth as other edges in the same set, sometimes edges
`in the same set can carry different amounts of bandwidth.
`Switch elements for high-speed data lines are structured
`into Clos networks in order to connect high-speed data lines
`140 to one another. For example, a first set of data lines 140
`may be connected to a second set of data lines 140 across a
`Clos type switch element. The switch element 100 can be
`configured to initially connect the data lines 140 in a first
`configuration, and to reconnect the data lines in case of
`switching events.
`Embodiments of the invention may be implemented using
`the 3-stage Clos network configuration. According to one
`implementation,
`the ingress stage switches 110 are each
`symmetrically connected to all center stage switches 120.
`Similarly, the egress stage switches 130 are each symmetri-
`cally connected to all of the center stage switches 120. The
`symmetrical connections between ingress and egress stage
`switches to the center stage switches may be accomplished
`by configuring the switch element so that the amount of
`bandwidth carried by the ingress stage switches and egress
`stage switches are the same. Furthermore, in one implemen-
`tation the size of the ingress stage switches and egress stage
`switches are the same, for any symmetrical pair. While
`relationships for creating symmetry across a Clos type
`switch element are described herein, it is possible for one
`
`Petitioner Huawei - Exhibit 1006, p. 18
`
`Petitioner Huawei - Exhibit 1006, p. 18
`
`

`

`US 7,310,333 B1
`
`5
`skilled in the art to apply the teachings disclosed herein to
`asymmetrical switch elements.
`FIG. 1b shows an embodiment of a switch control module
`190, such as can be found within a network element 110, 120
`or 130, such as a CoreDirector® switch, available from
`CIENA Corporation, that can be used to configure a switch
`element. The switching control module 190 includes a
`logical switch controller 191, a sorter manager 192, a switch
`control algorithm encapsulating the rearrangement algo-
`rithm 193, a program controller 195, various connection
`protocol support engines including APS, VLSR/TLSR, and
`UPSR engines 196 and interfaces for communicating with
`various other modules embodying components of the switch
`element. In addition, the switch control module 190 includes
`various tables for storing connection information created
`during the connection setup process. Examples of tables
`include an output/input (O/I) table, a UPSR connection
`table, and a VLSR/TLSR connection table. While software
`defined tables are described herein, it is possible for one
`skilled in the art to apply the teachings disclosed herein to
`hardware based switching components. The operation and
`interaction of the switch control module 190 and the switch
`
`element are described in greater detail below.
`2. Logical Modeling/Partitioning
`In one implementation, use of a control algorithm is
`avoided by modeling the various devices in a switch ele-
`ment. An example of such a model is illustrated in FIG. 2.
`Such a model enables selective rearrangement of connec-
`tions across the switch element to be achieved in an efficient
`
`manner. As shown in FIG. 2, a physical three stage Clos
`network switch element 100 (such as that shown in FIG. 1)
`can be modeled as a five-stage logical switch element 200.
`In the logical model 200, the middle three stages form a Clos
`network. The first and last stages, the sorters 215, 225, allow
`switching across a subset of the routers 216, 226. The routers
`216, 226 are the ingress and egress stages of the logical
`3-stage Clos network.
`Set forth below is the relationship between the physical
`Clos network 100 and the logical model 200 of the switch
`element.
`
`A model for a physical ingress switch 110 is formed by
`decomposing the physical
`ingress switch into a logical
`ingress device 210 comprising multiple routers 216 inter-
`connected to one or more sorters 215, as shown in FIG. 2.
`Likewise, a model for a physical egress switch 130 is formed
`by decomposing the physical egress switch into a logical
`egress device 220 comprising multiple routers 226 intercon-
`nected to one or more sorters 225, as shown in FIG. 2. In one
`implementation, a sorter 215, 225 is responsible for select-
`ing a time slot, and a router 216, 226 is responsible for
`selecting a center stage device 230 to which the time slot is
`to be switched or from which the time slot is to be received.
`
`Aphysical center stage switch 120 is modeled as a logical
`center stage device 230 by expanding the number of edges
`and reducing the number of time slots per edge. For
`example,
`if a physical center stage switch 120 has 32
`physical edges and 16 time slots per edge, then the logical
`center stage device 230 would have 32x16 or 512 edges with
`one time slot per edge. Thus, the logical center stage device
`230 is able to accommodate the same aggregate bandwidth
`as the physical center stage switch 120, but just uses a
`flattened index by converting the indices of the multidimen-
`sional array to an index of a single dimensional array. In one
`implementation, each router 216, 226 is connected to an
`edge of each logical center stage device 230. This means that
`the size of each router 216, 226 is equal to the number of
`logical center stage devices 230. Thus, if there are K center
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`stage devices 230, then each router 216, 226 has a size of K
`(i.e., can send or receive K time slots at a time). In one
`implementation, the size of each router 216, 226 is 24x24 to
`support 24 center stage devices 230.
`The model 200 shown includes 24 center switches.
`
`Though the number of center stage switches 24 is selected
`to achieve certain optimizations, other numbers may be
`used. The input sorter 215 (and output sorter 225) is parti-
`tioned so that no connection may cross a partition line (i.e.
`lines from a sorter are statically mapped to routers). So, as
`in the example shown where there are 24 center switches,
`each router is sized to be 24x24. Therefore every line gets
`exclusive use of the router(s) that it maps to. For instance,
`any port on an eight-port line module maps to exactly 2
`routers. Similarly, an OC 192 port maps to 8 routers. On a
`sixteen-port line module, each port maps to one router. The
`partition lines in the sorter 215, 225 are not between all
`routers, just at the boundary between lines.
`One of the properties relating to this model of the switch
`is that protection operations for protection applications can
`all be done in the active bank. Examples of protection
`applications include APS, VLSR, TLSR, and UPSR; how-
`ever,
`it is possible for one skilled in the art to apply the
`teachings disclosed herein to other protection types. Fur-
`thermore,
`the actions for achieving these operations are
`independent of the control algorithm and supported by the
`model alone. Protection switching events can occur very
`quickly for two reasons, because no control algorithm needs
`to be run and, since the operations are performed in the
`active bank, there is no need for a central control to commit
`the changes to the switch fabric thus further reducing
`protection-switching times. Another more subtle improve-
`ment with this method is that line-based protection events
`are not implemented with connection-based manipulations.
`A model such as that described above is an isomorphism
`of the physical switch element 100. Descriptions provided in
`this application may incorporate aspects of this model, but
`other models may also be implemented and contemplated in
`different embodiments of the invention, using similar prin-
`ciples disclosed herein.
`This model enables many benefits to be realized. As will
`be described in greater detail below, the model enables faster
`response to switching events to be achieved. In addition, it
`realizes this benefit without needing over-provisioned band-
`width. Over provisioned bandwidth is the bandwidth over
`and above the needed bandwidth to support point-to-point
`connections. One example of over provisioned bandwidth in
`a 3 stage Clos architecture is input copy multicast.
`C. Switch Configuration
`This section further describes the logical model of the
`switch element, according to an embodiment of the inven-
`tion.
`
`FIG. 2 illustrates a logical model 200 of a switch element
`100. Switch element 100 includes a set of ingress devices
`210, a set of center stage devices 230, and a set of egress
`devices 220. As was described above, the logical model 200
`provides that the components of switch element 100 can be
`separated into 5-stages. The 5-stages include input sorters
`215, ingress routers 216, center stage devices 230, egress
`routers 226, and output sorters 225. This logical model can
`be mapped back to a physical switch element (such as the
`Clos network shown in FIG. 1) to implement a switch
`element capable of performing fast reconfigurations. Soft-
`ware or other logic can be used to implement the logical
`model on the components of a physical switch element.
`Ingress device 210 includes at least one input sorter 215
`and ingress router 216. Egress device 220 includes at least
`
`Petitioner Huawei - Exhibit 1006, p. 19
`
`Petitioner Huawei - Exhibit 1006, p. 19
`
`

`

`US 7,310,333 B1
`
`7
`one output sorter 225 and egress router 226. A plurality of
`ingress data lines (not shown) couple to input sorters 215 of
`ingress devices 210. A plurality of egress data lines (not
`shown) couple to output sorters 225 of egress devices 220.
`Input framers (not shown) frame communications from the
`ingress data lines to input sorters 215. The communications
`framed by the input framers provide the bandwidth (i.e. time
`slots) to ingress device 210. Output framers (not shown)
`frame communications from output sorters 225 to the egress
`data lines. The communications framed by the output fram-
`ers provide the bandwidth to the egress data lines.
`In one implementation, each ingress router 216 receives
`data from only one ingress data line. Likewise, each egress
`router 226 forwards data to only one egress data line. One
`or more ingress routers 216 may receive data from the same
`ingress line, and one or more egress routers 226 may
`forward data to the same egress line, but each ingress or
`egress router may receive or forward data to only a single
`data line. This restriction gives rise, at least partially, to the
`ability to respond to switching events more quickly.
`In order to assign routers 216, 226 to each data line,
`corresponding input and output sorters 215, 225 are parti-
`tioned. When partitioned, any unit of bandwidth from an
`ingress or egress line may be connected through the corre-
`sponding input or output sorter 215, 225 to only those
`routers 216, 226 assigned to that line.
`On the ingress side, the number of bandwidth units that
`each ingress data line carries is received by one of the input
`sorters 215. The input sorter 215 selects one or more routers
`216 for each ingress data line (each data line has one or more
`routers dedicated thereto). The bandwidth units are distrib-
`uted to the selected ingress routers 216. Each selected
`ingress router 216 is coupled to each center stage device
`230. As such, the size of each ingress router 216 (i.e. the
`amount of bandwidth that can pass through it at one time) is
`equal to the number K of center stage devices 230. Thus,
`each router can output K units of bandwidth, one to each
`center stage device 230.
`On the egress side, the size of each egress router 226 is
`equal to the number of center stage devices 230 in use. Each
`egress router 226 is assigned only one egress data line. In
`addition, egress router 226 may receive a unit of bandwidth
`from each one of the center stage devices 230. Each egress
`router 226 receives from the center stage devices 230 a total
`amount of bandwidth that is equal to the number K of center
`stage devices 230. More than one egress router 226 may
`supply bandwidth to a particular egress data line, but each
`egress router 226 is assigned to only one egress data line. As
`with the ingress side, the output sorter 225 selects one or
`more routers 226 for each egress data line.
`The sorter 215 partitions time slots to the routers 216 in
`accordance with the symmetrical structure set forth above. A
`detailed description of the partitioning process is provided in
`copending and commonly owned U.S. Patent Application
`entitled “Switching Control Mechanism Based Upon The
`Logical Partitioning of a Switch Element” to Jeff Gullickson
`et. al. and filed Oct. 29, 2001, and assigned Ser. No.
`10/020,014, the contents of which are expressly incorpo-
`rated herein by reference.
`Given the model 200, switch element 100 can be partially
`configured at initialization using a conventional control or
`arrangement algorithm. However, portions of the connec-
`tions are not initialized using the control algorithms. These
`portions are initialized using a post-processing (i.e., post
`rearrangement processing) method that
`is discussed in
`greater detail below.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`