I 1111111111111111 11111 lllll 111111111111111 1111111111 11111 lll111111111111111
`US007675926B2
`
`c12) United States Patent
`Olsen et al.
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 7,675,926 B2
`Mar.9,2010
`
`(54) HIERARCHICAL QOS BEHAVIORAL MODEL
`
`(75)
`
`Inventors: Robert Olsen, Dublin, CA (US);
`Michael Laor, Zichron-Yakov, IL (US);
`Clarence Filsfils, Brussels (BE)
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1017 days.
`
`(21) Appl. No.: 10/840,126
`
`(22) Filed:
`
`May 5, 2004
`
`(65)
`
`Prior Publication Data
`
`US 2005/0249220 Al
`
`Nov. 10, 2005
`
`(51)
`
`Int. Cl.
`H04L 12156
`(2006.01)
`(52) U.S. Cl. ....................................... 370/412; 370/428
`(58) Field of Classification Search ................. 370/412,
`370/395.4, 395.43, 468, 428, 392,395.21;
`709/232
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,864,540 A
`6,130,878 A
`6,147,996 A *
`6,408,005 Bl
`6,424,649 Bl *
`6,721,796 Bl*
`6,778,546 Bl *
`6,813,243 Bl*
`6,831,923 Bl*
`6,888,830 Bl *
`6,940,864 B2 *
`
`. ................. 370/394
`
`1/1999 Bonomi et al.
`10/2000 Charny
`11/2000 Laor et al.
`6/2002 Fan et al.
`7/2002 Laor et al ................... 370/359
`4/2004 Wong ......................... 709/232
`8/2004 Epps et al. .................. 370/413
`11/2004 Epps et al. .................. 370/235
`12/2004 Laor et al ................... 370/412
`5/2005 Snyder, II et al. ........... 370/392
`9/2005 Abdelilah et al.
`........... 370/412
`
`6,977,930 Bl*
`6,980,552 Bl *
`7,020,143 B2 *
`7,231,425 Bl*
`7,280,542 B2 *
`7,286,525 Bl*
`7,304,999 B2 *
`7,321,940 Bl*
`7,385,987 Bl*
`7,417,999 Bl*
`
`12/2005 Epps et al. .................. 370/392
`12/2005 Belz et al .................... 370/392
`3/2006 Zdan ..................... 370/395.21
`6/2007 Charny et al. ............... 709/205
`10/2007 Hassan-Ali et al.
`...... 370/395.1
`10/2007 Laor et al.
`.................. 370/359
`12/2007 Sukonik et al.
`............. 370/396
`1/2008 Smith et al. ................. 709/240
`6/2008 Charny et al. ............ 370/395.4
`8/2008 Charny et al. ............... 370/408
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`WO 99/17575
`
`4/1999
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`Hierarchical packet fair queueing algorithms; Bennett, J.C.R.; Hui
`Zhang; Networking, IEEE/ ACM Transactions on vol. 5, Issue 5, Oct.
`1997 pp. 675-689.*
`
`(Continued)
`
`Primary Examiner-Salman Ahmed
`(74) Attorney, Agent, or Firm--Cindy Kaplan
`
`(57)
`
`ABSTRACT
`
`A hierarchical traffic management system and method (i.e., a
`QoS behavioral model) are disclosed herein. The system
`includes a classifier operable to identify and classify incom(cid:173)
`ing traffic streams and a queuing system. The queuing system
`includes a plurality of queues and is operable to apply sched(cid:173)
`uling policies to the traffic streams. The queues of the queuing
`system each include enqueue attributes configured to control
`a depth of the queue and dequeue attributes configured to
`control scheduling of the queue. The dequeue attributes
`include minimum bandwidth, maximum bandwidth, excess
`bandwidth, and priority, wherein each of the queues has one
`or more of the dequeue attributes defined.
`
`27 Claims, 6 Drawing Sheets
`
`f20
`
`s stem
`
`30
`
`CLASSIFICATION
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 1 of 14
`
`

`

`US 7,675,926 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`7,522,609 B2 *
`4/2009 Cohen et al ............ 370/395.42
`7,554,907 Bl*
`6/2009 Epps et al. .................. 370/230
`7,567,572 Bl*
`7/2009 Charny et al. ............ 370/395.4
`2/2002 Mitchell
`2002/0023168 Al
`6/2002 Sridhar et al.
`2002/0073226 Al
`12/2002 Zdan
`2002/0191622 Al
`2004/0156367 Al*
`370/395.4
`8/2004 Albuquerque et al.
`2005/0036495 Al*
`2/2005 Wishneusky et al. ..... 370/395.4
`2005/0047415 Al*
`3/2005 Channegowda et al ... 370/395.4
`2005/0091642 Al*
`4/2005 Miller ........................ 7 l 7 /124
`2005/0094643 Al*
`5/2005 Wang et al ............... 370/395.4
`2005/0220115 Al* 10/2005 Romano eta!. .......... 370/395.4
`2007/0050495 Al*
`3/2007 Sridhar et al ................ 709/223
`
`FOREIGN PATENT DOCUMENTS
`
`Performance analysis of hierarchical task queue organization for
`parallel systems; Cheng, S.P.; Dandamudi, S.; Distributed Comput(cid:173)
`ing Systems, 1992., Proceedings of the 12 th International Conference
`on Jun. 9-12, 1992 pp. 286-293.*
`Hierarchical fair queuing: single-step approximation ofhierarchical(cid:173)
`GPS; Jun, A.D.-S.; Jinwoo Choe; Leon-Garcia, A.; Global Telecom(cid:173)
`munications Conference, 2002. Globecom '02. IEEE vol. 3, Nov.
`17-21, 2002, pp. 2405-2409 vol. 3.*
`Fair queuing with service envelopes (FQSE): a cousin-fair hierarchi(cid:173)
`cal scheduler for Ethernet PONs; Kramer, G.; Banerjee, A.; Singha!,
`N.K.; Mukherjee, B.; Dixit, S.; Ye, Y.; Optical Fiber Communication
`Conference, 2004. OFC 2004; vol. 1, Feb. 23-27, 2004.*
`Floyd S. et al:"Link-Sharing and Resource Management Models for
`Packet Networks" IEEE/ACM Transactions on Networking, IEEE/
`ACM, New York, NY, US, vol. 3, No. 4, Aug. 1, 1995.
`
`WO
`
`WO2005/l 12347 A2 * 11/2005
`
`* cited by examiner
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 2 of 14
`
`

`

`U.S. Patent
`
`Mar. 9, 2010
`
`Sheet 1 of 6
`
`US 7,675,926 B2
`
`CONFIGURATION LANGUAGE
`
`BEHAVIORAL MODEL
`
`I
`12"
`
`12
`
`FIGURE 1
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 3 of 14
`
`

`

`U.S. Patent
`
`Mar. 9, 2010
`
`Sheet 2 of 6
`
`US 7,675,926 B2
`
`ROUTER/SW ITCH
`
`20
`
`2
`
`20
`
`24
`
`INGRESS
`PATH
`
`TMN
`
`TMN
`
`SWITCH
`FABRIC
`
`1 - - - - - - - - - -<
`
`TMN
`
`21
`
`EGRESS
`PATH
`
`26
`
`FIGURE 2
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 4 of 14
`
`

`

`U.S. Patent
`
`Mar. 9, 2010
`
`Sheet 3 of 6
`
`US 7,675,926 B2
`
`r20
`
`30
`
`_ _.,. CLASSIFICATION
`
`FIGURE 3
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 5 of 14
`
`

`

`U.S. Patent
`
`Mar.9,2010
`
`Sheet 4 of 6
`
`US 7,675,926 B2
`
`N z
`::s
`>
`
`...--z
`::s
`>
`
`(/) w
`:::)
`w
`:::) a
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 6 of 14
`
`

`

`0--, = N
`
`N
`\0
`UI
`-....l
`O'I
`-....l
`d r.,;_
`
`0 ....
`Ul
`.....
`rJJ =(cid:173)
`
`('D
`('D
`
`O'I
`
`0 ....
`
`N
`~\,Ci
`
`0
`
`~ :-:
`~
`
`~ = ~
`
`~
`~
`~
`•
`00
`~
`
`FIGURE 5
`
`-Priority_ level
`-Excess BW
`-Max BW -shaping
`-Min BW guarantee
`output from queue:
`Attributes controlling
`
`-Tail drop
`-AQM
`depth of queue:
`Attributes controlling
`
`PACKETS
`
`DEPARTIN
`DEQUEUE
`
`l
`
`p1
`
`p2
`
`P3
`
`---
`
`l
`
`pn
`
`I
`
`PACKETS I
`
`ARRIVING
`ENQUEUEJ
`
`r40
`
`QUEUE OF PACKETS
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 7 of 14
`
`

`

`U.S. Patent
`
`Mar.9,2010
`
`Sheet 6 of 6
`
`US 7,675,926 B2
`
`60
`~
`
`66
`r---1
`
`66
`r---1
`
`LINECARD
`
`LINECARD
`
`a
`
`I I
`
`62
`
`_I
`
`....
`
`PROCESSOR
`
`68
`r---1
`
`PACKET
`MEMORY
`
`68
`, J
`
`PROGRAM
`MEMORY
`
`FIGURE 6
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 8 of 14
`
`

`

`1
`HIERARCHICAL QOS BEHAVIORAL MODEL
`
`2
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`US 7,675,926 B2
`
`FIG. 1 depicts a QoS behavioral model of the present
`invention.
`FIG. 2 is a block diagram illustrating traffic management
`nodes of the behavioral model located in a router or switch.
`FIG. 3 is a block diagram illustrating components of one
`embodiment of the traffic management node of FIG. 2.
`FIG. 4 illustrates a three layer hierarchy which can be
`supported by the behavioral model of FIG. 1.
`FIG. 5 depicts an example of attributes of a queue of the
`traffic management node of FIG. 3.
`FIG. 6 is a block diagram of one example of a network
`device for use in implementing embodiments of the present
`invention.
`Corresponding reference characters indicate correspond(cid:173)
`ing parts throughout the several views of the drawings.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates generally to connnunication 5
`networks, and more specifically, to a hierarchical QoS behav(cid:173)
`ioral model that includes as a component a hierarchical packet
`scheduling behavioral model.
`High speed networks are designed to carry services with a
`wide range of traffic characteristics and quality-of-service 10
`(QoS) requirements. Traffic management mechanisms pro(cid:173)
`vide a variety of QoS behaviors (e.g., policing, marking, low
`latency service, bandwidth allocation services) in routers and
`switches. A connnon task for the packet scheduling compo(cid:173)
`nent of the QoS behavioral model is ensuring that each of 15
`multiple queues is guaranteed a minimum rate, excess band(cid:173)
`width is shared in accordance with predefined weights, each
`queue does not exceed a specified maximum rate, and the link
`is maximally utilized within the maximum rate constraints.
`Many different QoS behavioral models have been defined, 20
`and this can be confusing to users that want, or require, a
`consistent model across the entire network. In some cases,
`individual platforms or implementations have a different
`means to enable basic QoS functionality or have unique inter(cid:173)
`nal system bottlenecks (e.g., a switch fabric, an encryption 25
`engine) whose resources must be managed directly (via plat(cid:173)
`form specific CLI ( Connnand Line Interface)) in order for the
`user to achieve basic QoS goals ( e.g., provide low latency to
`voice traffic). In such an environment, users must acquire
`knowledge and expertise of platform specific architectural 30
`issues and essentially learn multiple ways to achieve what is
`really the same goal (i.e., define the QoS behavior on a prod(cid:173)
`uct). Users want a connnon and consistent interface, and the
`historical lack of such connnonality and consistency is a
`serious problem for many deployments involving multiple 35
`platforms. A uniform interface is a key component to success(cid:173)
`fully providing customers with an end-to-end QoS solution.
`There is therefore, a need for a highly functional QoS
`behavioral model that can be used on various components and
`platforms.
`
`40
`
`The following description is presented to enable one of
`ordinary skill in the art to make and use the invention.
`Descriptions of specific embodiments and applications are
`provided only as examples and various modifications will be
`readily apparent to those skilled in the art. The general prin(cid:173)
`ciples described herein may be applied to other embodiments
`and applications without departing from the scope of the
`invention. Thus, the present invention is not to be limited to
`the embodiments shown, but is to be accorded the widest
`scope consistent with the principles and features described
`herein. For purpose of clarity, details relating to technical
`material that is known in the technical fields related to the
`invention have not been described in detail.
`The present invention operates in the context of a data
`connnunication network including multiple network ele(cid:173)
`ments. Some of the elements in a network that employs the
`present invention may be network devices such as routers and
`switches. A traffic management system according to a behav(cid:173)
`ioral model of the present system is located in one or more of
`the network elements. The system may be used, for example,
`in a router or switch platform that performs non-trivial (i.e.,
`non-first in first out) queuing and packet scheduling. This
`includes, for example, applications on service provider edge
`and broadband aggregation.
`A QoS behavioral model that supports a general classifier,
`pre-queueing operator ( e.g., policing, marking), hierarchical
`queueing/scheduling system, and post-queueing operator
`(e.g., compression) is disclosed herein. The hierarchical
`scheduler supports an n-level priority service along with
`50 parameters for scheduling (e.g., minimum bandwidth, maxi(cid:173)
`mum bandwidth, and excess bandwidth). The scheduler is
`also configured to handle priority propagation, minimum rate
`propagation, and oversubscription. These scheduler behav(cid:173)
`iors, described further below, are combined in an integrate
`55 manner to create a behavioral model for a hierarchical sched(cid:173)
`uler that is a component of the broader QoS behavioral model.
`As previously discussed, the motivation for defining a QoS
`behavioral model is to ensure that any platform that imple(cid:173)
`ments QoS will do so in a way that will result in a behavior
`60 that is consistent with the behavior provided by other plat(cid:173)
`forms. That is, all platforms should conform to the QoS
`behavioral model and preferably present a connnon user
`interface irrespective of the implementation details of the
`platforms.
`FIG. 1 illustrates the relationship among a configuration
`language for user interface (referred to herein as MQC
`(Modular QoS CLI)), the behavioral model and various sys-
`
`SUMMARY OF THE INVENTION
`
`A hierarchical traffic management system and method (i.e., 45
`a QoS behavioral model) are disclosed herein. The basic
`building block of the model is the traffic management node
`(TMN). The TMN includes a classifier operable to identify
`and classify incoming traffic streams, a pre-queueing opera(cid:173)
`tor, a hierarchical queuing system, and a post-queueing
`operator. The queuing system includes a plurality of queues
`and is operable to apply scheduling policies to the traffic
`streams. The queues of the queuing system each include
`enqueue attributes configured to control a depth of the queue
`and dequeue attributes configured to control scheduling of the
`queue. The dequeue attributes include minimum bandwidth,
`maximum bandwidth, excess bandwidth, and priority,
`wherein each of the queues has one or more of the dequeue
`attributes defined.
`The traffic management nodes operate according to a
`specified behavioral model and a plurality of components
`within a network system comprise one or more of the traffic
`management nodes. A connnon configuration language is
`provided for user interface with the behavioral model.
`Further understanding of the nature and advantages of the 65
`inventions herein may be realized by reference to the remain(cid:173)
`ing portions of the specification and the attached drawings.
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 9 of 14
`
`

`

`US 7,675,926 B2
`
`3
`tern components (e.g., routers and switches) 12. MQC is one
`example of a configuration language for the abstract behav(cid:173)
`ioral model and is used to enable QoS functionality by pro(cid:173)
`viding a platform independent interface for configuring QoS.
`In order to attain platform independence, the commands
`within the MQC define QoS functionality and behavior inde(cid:173)
`pendent of implementation or algorithm (i.e., platform or
`implementation specific details are not exposed in the CLI).
`Examples of abstract behaviors configurable via the configu(cid:173)
`ration language include guaranteeing a minimum bandwidth
`allocation to a class of traffic, imposing a maximum trans(cid:173)
`mission rate on a class of traffic, and guaranteeing low latency
`to a class of traffic. Each of these examples illustrates a
`general behavior that is useful across platforms, and thus a
`common, consistent, and platform independent interface is 15
`preferably used to enable the same behavior on all platforms.
`It is to be understood that the configuration language referred
`to herein is only one example and different configuration
`languages may be used. Therefore, details of MQC are not
`provided herein.
`The basic building block of the behavioral model is a
`Traffic Management Node (TMN). A TMN can identify dif(cid:173)
`ferent traffic streams and apply policies or actions to those
`streams as defined by the configuration language. The TMN
`exists at any point along a platform data path where there is a
`need to manage traffic. Thus, a router may have multiple
`TMN structures in its datapath. The TMN may or may not be
`at a point where congestion may occur. FIG. 2 illustrates
`traffic management nodes 20 installed within a router or
`switch 12 at the ingress and egress ports 24, 26, and prior to
`the switch fabric 21 (e.g., bus). In a distributed architecture,
`for example, there is preferably a TMN 20 at the ingress path
`24 that manages the incoming traffic stream from the inter(cid:173)
`face. Such an ingress TMN may involve only classifying and
`policing the traffic streams, or it may involve shaping the
`stream to create an artificial congestion point that has an
`associated queuing system. The incoming stream may then
`congest with traffic from other interfaces or other line cards as
`they all attempt to traverse the router interconnect on their
`way to the egress interfaces, so a second TMN 20 may exist at
`the interconnect point 21. A third TMN structure 20 may exist
`on the egress path 26 providing management to traffic prior to
`exiting the interface.
`While the TMN 20 may apply policies by placing packets
`into queues, the configuration of its behavior is not specified 45
`in terms of queues, but rather by defining traffic streams and
`the actions or policies that should be applied to those streams.
`Queues may be inferred by the underlying implementation if
`required to apply a policy that was defined by the user. Simi(cid:173)
`larly, when the user defines various other actions on a class 50
`(e.g., policing), it is the underlying platform that translates
`this action and programs a specific operator. This creates an
`abstraction in which traffic streams and policies or actions are
`defined irrespective of the specific implementation.
`FIG. 3 illustrates details of the behavioral model at a traffic 55
`management node 20. The traffic management node structure
`has four components: classification phase 30, pre-queuing
`operator 32, queuing system 34, and post-queuing operator
`36. It is not necessary for each component to be included at
`every traffic management node 20. For example, the pre(cid:173)
`queuing operator 32 and post-queuing operator 36 may be
`optional. As shown in FIG. 3, the pre-queuing and post(cid:173)
`queuing operators 32, 36 are allowed to send some or all of the
`packets back to previous stages. The following provides
`details of the TMN components.
`The classification phase 30 is the first component that the
`packet stream enters. The classification function identifies
`
`4
`packet streams that require traffic management and classifies
`packets. Classification can be done based on any logical com(cid:173)
`bination of any fields in the packet header. Additionally, clas(cid:173)
`sification can be done based on the ingress or egress physical
`5 or virtual interface, as well as based on routing related infor(cid:173)
`mation that is stored in the FIB (Forwarding Information
`Base) ( e.g., BGP (Border Gateway Protocol) community, AS
`(Autonomous Systems) number), or various non-data related
`criteria (e.g., time-of-day). Further, classification can be
`10 based on any form of stateful classification or inspection,
`such as regular-expression searches, or identification of state(cid:173)
`ful protocols that have behaviors such as port hopping (i.e.,
`protocol first negotiates connection setup on one port, and
`then moves to a different port for data transmission).
`The pre-queuing operator 32 may then be invoked to oper-
`ate on some or all of the packet streams prior to queuing. For
`example, pre-queueing operators 32 include a policing func(cid:173)
`tion (e.g., measure and enforce a packet stream rate) and a
`packet marking function (e.g., change IP DSCP (differenti-
`20 ated services code point) field). As previously noted, the
`pre-queuing operator 32 is optional and thus need not apply to
`all traffic streams. The pre-queuing operator 32 applies to
`traffic as it traverses the datapath, and does not provide any
`buffering. Policing may be applied, for example, on high
`25 priority traffic and not required for best effort traffic. Since the
`optional pre-queuing operation is applied prior to queuing, it
`may effect operation in the subsequent queuing system. In
`policing, for example, the policer may drop packets, thus
`impacting queue depths in the queuing system. Similarly, a
`30 pre-queuing coloring operation may affect a WRED
`(Weighted Random Early Detection) profile that is applied to
`a packet if WRED is enabled in the queuing system. Pre(cid:173)
`queuing operations may include hierarchical operations.
`Hierarchical policing allows for policing an aggregate stream
`35 on an interface, as well as policing a specific subset of traffic.
`The queuing system 34 controls several behavioral aspects,
`including for example, minimum bandwidth allocation,
`maximum bandwidth enforcement, and excess bandwidth
`allocation. The complete behavior of individual queues 40 is
`40 defined by the full set of attributes that control how traffic
`enters and exits the queue and is described in detail further
`below.
`The post-queuing operator 36 may be invoked to operate on
`some of the packet streams after dequeue has occurred. The
`optional post-queuing operator 36 is the final stage before
`packets exit the TMN 20. The post-queuing operator 36 is
`necessary for instances when the operator must be applied to
`packets in the order in which they exit the TMN. For example,
`it may be required to compress traffic that is sent downstream
`through an interface. This operation may require attaching a
`sequence number to each packet so that the decompression
`agent downstream can determine the order in which packets
`were compressed. Therefore, the compression and attaching
`of the sequence number can only be done after packets are
`dequeued, since the order of dequeue is not known prior to
`performing the queuing function. The post-queuing operator
`36 provides a path which allows for sending a packet back
`through the TMN 20 either to the optional pre-queuing opera(cid:173)
`tor or to the classifier and back through the queuing system
`60 (FIG. 3).
`As illustrated in FIG. 4, it is useful to define a hierarchy of
`traffic classes over which QoS requirements may be config(cid:173)
`ured. The behavioral model may include an arbitrary number
`of layers of hierarchy. A model may include, for example,
`65 three levels ofhierarchy as shown in FIG. 4. The bottom level
`or root is a node 42 defining a single physical interface over
`which traffic will be transmitted. The next level of hierarchy
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 10 of 14
`
`

`

`US 7,675,926 B2
`
`15
`
`6
`assigning a priority attribute of the highest priority level indi(cid:173)
`cates a class has the most stringent latency requirements of all
`classes. The priority attribute defines strict priority. This
`means that a queue gets to send its traffic ahead of every other
`sibling queue of lower priority that is connected to same
`parent node. An optional parameter may specify the rate that
`gets priority service, and beyond this rate, a policing function
`is invoked when there is congestion (i.e., the policer operates
`when congestion occurs, and is thereby a conditional policer)
`in order to avoid starvation of other nodes. In the absence of
`congestion, the priority class is allowed to exceed its config(cid:173)
`ured rate. If no rate parameter is specified, the priority class
`can get the entire available bandwidth, and, if it is still desired
`to avoid starvation of other classes, priority may be used in
`conjunction with an unconditional policing pre-queueing
`operator.
`The priority propagation behavior allows low latency
`behavior to be delivered through the hierarchy from leaf to
`root. Priority propagation effectively allows for priority traf(cid:173)
`fic to not be bound by short-term rate constraints imposed at
`?nces!ra! nod~s in the queueing hierarchy. In this way, latency
`1s opt1m1zed (1.e., reduced as much as possible) at the cost of
`increased burstiness in the delivery of minimum and excess
`rate service. Long term rate constraints generally must still be
`enforced, and the general model allows for the duration of
`disobedience to the rate to be configurable. More specifically,
`a burst tolerance parameter, for each layer of hierarchy
`through which priority behavior propagates, is associated
`with the stream that is enabled with priority propagation
`behavior. A burst tolerance parameter of O indicates the
`stream must always obey ancestral rate constraints. A burst
`tolerance of infinity indicates the stream need never obey the
`ancestral rate constraint. A burst tolerance between O and
`infinity specifies how much the stream may burst beyond the
`rate constraint of the ancestral node before it becomes con(cid:173)
`strained by the rate. While the priority traffic is allowed to
`exceed the ancestral node rates, its traffic will receive priority
`service (with respect to other traffic) at each layer of the
`hierarchy, and users can control or specify how competing
`such traffic streams should be serviced with respect to each
`other.
`In addition to the priority attribute that can be assigned to
`que~es, the following priority service order preferably
`applies to the schedule. Queues with the priority attribute are
`served before non-priority sibling queues connected to the
`same parent node. If there is no traffic on the queues with the
`priority attribute, then any queue that has a minimum band(cid:173)
`width guarantee that has not yet been met is served. Finally,
`excess bandwidth is delivered to queues eligible for sharing in
`excess bandwidth. This multi-level priority service ensures a
`better latency for non-priority traffic with a minimum rate
`attribute ( e.g. business traffic), as compared to traffic without
`a minimum rate attribute. Note that for queues with minimum
`bandwidth guarantee, no conditional policer is invoked once
`the minimum rate is delivered. Rather, traffic above the mini(cid:173)
`mum guarantee competes for excess bandwidth.
`The behavioral model allows for defining of multiple levels
`of priorities. An optional parameter defines the priority level
`and higher levels are given strict priority service over lower
`levels. For example, the priority service order may be:
`Priority N
`Priority N-1
`
`5
`includes logical interfaces 44 which may correspond to, for
`example, virtual LANs (VLANs). The example shown in
`FIG. 4 includes VLAN 1, VLAN 2, DLCI (Data Link Con(cid:173)
`nection Identifier) 1 and DLCI 2 at this second level. A third
`level of hierarchy consists of classes 46. Thus, all of the 5
`classes, logical interfaces, and physical interfaces are repre(cid:173)
`sented by nodes in a tree structure.
`Each layer of the hierarchy may be configured to support:
`m levels of strict priority service; a set of nodes each with an
`attribute defining a guaranteed minimum service rate; a set of 10
`nodes each with an attribute defining given excess service
`(i.e., when all priority service and minimum rate service is
`given, then excess service is delivered); and an optional maxi(cid:173)
`mum rate attribute for each priority or non-priority node. A
`node may be given a minimum rate service as well as excess
`an maximum rate service. Default attributes, discussed
`d
`below, apply when no attributes are defined for a given queue.
`It should also be noted that in the preferred embodiment
`within a given branch of a tree, only one queue (node) car:
`have the priority attribute.
`As illustrated in FIG. 5, a queue ( or node) 40 in the behav- 20
`ioral model has two sets of attributes, enqueue and dequeue.
`Enqueue attributes control how packets enter a queue, and as
`such control the depth of the queue. Enqueue attributes
`include controlling the depth of a queue via specification of a
`maximum queue depth, resulting in tail-drop when this limit 25
`is reached, or via specification of the parameters for the active
`queue management (AQM) mechanism (e.g., RED or
`WRED).
`Dequeue attributes control how packets exit the queue, and
`as such control the scheduling of the queue with respect to 30
`other queues. Dequeue attributes include minimum band(cid:173)
`width guarantee, maximum bandwidth guarantee, excess
`bandwidth, and priority. Minimum bandwidth guarantee
`specifies the minimum bandwidth that is to be delivered to the
`d~~~:s u:t:~!~!~z- b1:~~~n:~t1I: tt:n~:!~:h l~fia~=c~f~~ 35
`Excess bandwidth defines how to allocate bandwidth with
`siblings of the node on which it is defined. The priority
`attribute, described further below, defines that any offered
`load in this queue, up to an optionally specified rate, is to be
`serviced ahead of all other queues or nodes of lower priority 40
`connected to the same parent. The model allows a user to
`define a bandwidth associated with the priority attribute. Any
`traffic up to this bandwidth is regarded as priority traffic and
`is gi:'en pri_ority over other queues of a lower priority. If no
`rate 1s specified, then by default the priority class can use the 45
`entire interface available bandwidth.
`Minimum rate propagation is a behavior implied by some
`configurations of the minimum rate attribute. Minimum rate
`propagation allows child nodes to be configured with a mini(cid:173)
`mum rate, even though the parent node does not have an equal 50
`or greater minimum rate. This means that effectively the
`parent node has a conditional minimum rate guarantee, in the
`sense that when traffic is present on the child node that has a
`minimum rate guarantee, the parent also has the guarantee
`(i.e., the guarantee has propagated from the child to the par(cid:173)
`ent) to be used only for traffic coming from the child with the
`guarantee (i.e., the parent does not have the guarantee to be
`used by traffic from some other child that does not have a
`minimum rate guarantee.) This minimum rate propagation
`~rovides efficiency in applications ( e.g., broadband aggrega(cid:173)
`tion) where oversubscription is common and it is not possible 60
`or ~esirable to give each parent node its own guarantee, yet
`delivery of some guaranteed service for some child node
`services is required, while the non-guaranteed services must
`be allowed to utilize available bandwidth (in a user-controlled
`manner) when guaranteed services are not active.
`The priority attribute specifies that a class has stringent
`delay requirements with respect to lower priority classes, and
`
`55
`
`Minimum bandwidth guarantees
`Excess bandwidth
`It should be noted that the minimum, maximum, and excess
`bandwidth attributes are independent of each other. For
`65 example, the share of excess bandwidth given to a queue can
`be defined irrespective of how much minimum bandwidth the
`queue is guaranteed. Hence, if it is not desired to guarantee
`
`Ex.1012
`CISCO SYSTEMS, INC. / Page 11 of 14
`
`

`

`US 7,675,926 B2
`
`7
`any minimum bandwidth to best effort general Internet traffic,
`but it is desired to give it a larger portion of any remaining
`bandwidth, the attributes can be set accordingly.
`As previously discussed, it is not required to explicitly
`configure all of the attributes for a queue. If an attribute is not 5
`explicitly configured, then a default value applies. If no mini(cid:173)
`mum bandwidth guarantee is defined, then the queue is guar(cid:173)
`anteed no bandwidth. If no maximum (shape) rate is defined,
`the queue is allowed to take as much as it can up to the
`maximum available bandwidth of its parent node. The queue 10
`( or node) will still share bandwidth with its sibling queues ( or
`nodes) as may be defined by the excess bandwidth attributes.
`If no excess bandwidth is defined, then the queue will share
`equally any excess bandwidth not consumed by queues with
`explicitly configured excess shares, and the sharing occurs 15
`with the queue's siblings that also have no excess explicitly
`defined.
`As an example, traffic classes may be grouped into
`VLANs. In this case the excess bandwidth attribute can be
`used to define the sharing of excess bandwidth among the
`VLANs. And the maximum rate attribute can be used to
`define the maximum bandwidth of a VLAN. If the excess
`bandwidth attribute is not defined, then the VLAN swill share
`excess bandwidth equally among them (since this is the
`default behavior for sharing excess bandwidth). Likewise, if 25
`no maximum rate is defined, each VLAN will try to get as
`much bandwidth as it can, subject to appropriate sharing with
`the otherVLANs.
`An implied class, referred to as class-default, may be
`defined. This class-default may not be explicitly set forth in a
`configuration file. For class-default no minimum bandwidth
`is guaranteed and no maximum rate is defined. Therefore
`class-default will attempt to get as much as it can, and having
`no excess bandwidth attribute defined, it will share bandwidth
`equally with other queues that have no explicitly configured
`