QoS Policing in Cisco IOS

[LEFT][CODE]http://wiki.nil.com/QoS_Policing_in_Cisco_IOS[/CODE][B]By Ivan Pepelnjak[/B]
The activity called [I]policing [/I]or [I]rate limiting [/I]in various Cisco IOS releases is actually a traffic contract conformance measurement that can result in [I]marking[/I] (changing QoS attributes of individual packets in the traffic flow) or [I]policing [/I](dropping of packets violating the traffic contract).
This document describes various algorithms used to implement rate limiting on non-distributed software-based router platforms running Cisco IOS. Distributed platforms (Cisco 7600, GSR) might use different algorithms depending on software release and the hardware QoS implementations on Catalyst switches differ significantly from the software ones.
[B] Cisco IOS Implementations [/B]

Cisco IOS implements policing/marking functionality with two unrelated mechanisms:

[LIST][*] The [B]rate-limit [/B]command implements per-interface input- and output-rate limiting.[*] The [B]police [/B]command implements the traffic measurement within the scope of the Modular QoS Command Line Interface (MQC).[/LIST]
[B]Rate-limit [/B]commands and QoS [B]policy-maps [/B]containing the [B]police [/B]command can measure inbound or outbound packets on physical or logical interfaces (tunnels, subinterfaces). They introduce no delay (apart from slightly increased CPU load on the router) in the packet forwarding mechanism.
[B] Rate-limit command [/B]

The [B]rate-limit [/B]interface configuration command can match packets based on IP access lists, IP precedence settings, DSCP settings, QoS groups or source MAC addresses. It can set the IP precedence, DSCP or MPLS QoS bits in the measured packets, or group the packets into QoS groups.
The [B]rate-limit [/B]command uses dual token bucket mechanism and drops all packets that exceed the excess burst size.
[B] Police action [/B]

The [B]police [/B]action specified within a [B]class [/B]in a [B]policy-map [/B]can use three different measurement mechanisms:

[LIST][*] Single token bucket measurement is used when the [B]police[/B] command specifies only the [B]conform[/B] and [B]exceed[/B] actions.[*] Dual token bucket measurement is used to support [B]conform[/B], [B]exceed[/B] and [B]violate[/B] actions.[*] Dual-rate dual token bucket measurement is used when the [B]police[/B] command specifies [B]cir[/B] and [B]pir[/B] rates.[/LIST]
As the traffic measurement takes place within a traffic class defined by a [B]class-map[/B], any criteria supported by the [B]class-map[/B] configuration command can be used to define the traffic class.
Each [B]police [/B]command can specify three types of actions:

[LIST][*] The [B]conform[/B] action is executed for packets within the average rate and burst size.[*] The [B]exceed[/B] action for a [B]police[/B] command specifying traffic [B]rate[/B] is executed for packets within the average rate and excess burst size.[*] The [B]exceed[/B] action for a [B]police[/B] command specifying [B]pir[/B] rate is executed for packets within the excess rate and excess burst size.[*] The [B]violate[/B] action is executed for packets that exceed excess rate/burst size.[/LIST]
The actions executed by the [B]police[/B] command can pass the packet unmodified, drop it or mark it. The following QoS attributes of a packet can be modified:

[LIST][*] IP precedence;[*] IP Differentiated Services Control Point (DSCP);[*] Discard class (within the DSCP field);[*] ATM Cell Loss Priority (CLP) – used only for packets transmitted over an ATM interface;[*] Ethernet 802.1q Class of Services (CoS) marking;[*] MPLS QoS (experimental) bits – used only for MPLS-encapsulated packets;[*] Frame Relay Discard Eligibility (DE) bit – used only for packets transmitted over an outbound Frame Relay interface;[*] QoS group (an extra marker internal to the router).[/LIST]
[B] Measurement Mechanisms [/B]

The traffic contracts conformance measurement is usually performed with a [I]token bucket [/I]algorithm:

[LIST][*] The token bucket [I]size[/I] defines the initial [I]burst size[/I] that can exceed the average rate.[*] Tokens (conforming-bytes or conforming-packets) are added to the bucket at a constant rate (the average traffic arrival/departure rate). Tokens exceeding the bucket size are dropped.[*] Each conforming packet consumes the tokens relative to its size (when measuring packet rate, each packet consumes a single token). Packets exceeding the traffic contract do not consume tokens.[/LIST]
[B] Single Token Bucket Algorithm [/B]

The single token bucket algorithm is used for simple traffic contracts that differentiate the measured packets into conforming and non-conforming. The [B]police [/B]command using a single token bucket algorithm can specify:

[LIST][*] Average traffic bit rate with the [B]rate[/B] [I][B]speed[/B][/I] [B]bps[/B] parameter or [B]rate [/B] [I][B]percentage[/B][/I] [B]percent[/B] parameter.[/LIST]
The rate specified with the [B]percent[/B] parameter is calculated based on the [B]bandwidth[/B] settings of the interface to which the [B]policy-map[/B] is applied.

[LIST][*] Average packet rate with the [B]rate[/B] [I][B]number[/B][/I] [B]pps[/B] parameter.[*] Burst size with the [B]burst[/B] [I][B]size[/B][/I] parameter.[*] Conform and exceed actions with the [B]conform-action[/B] and [B]exceed-action[/B] keywords.[/LIST]
IOS release 12.4T supports multiple [B]conform-action[/B] and [B]exceed-action[/B] commands.
The single token bucket algorithm is illustrated in the following figure:
[URL="http://wiki.nil.com/Image:QoSPolicingSingleBucket.gif"][IMG]http://wiki.nil.com/wk/images/4/4b/QoSPolicingSingleBucket.gif[/IMG][/URL]
To optimize the token bucket algorithm, the tokens are added to the bucket that the packet arrival time using the following formula: Bucketnew = Min(BurstSize,BucketOld + Interpacket-Time * MeasurementRate)
[B] Example [/B]

The following router configuration measures the web traffic received through a serial interface and drops all packets exceeding the 512000 bps average rate:
[CODE]
class-map match-any Web
match protocol http
match protocol secure-http
!
policy-map MeasureWeb
class Web
police rate 512000 bps
conform-action transmit
exceed-action drop
!
interface Serial1/0
service-policy input MeasureWeb

[/CODE] [B] Dual Token Bucket Algorithm [/B]

Slightly more flexible traffic contracts might allow extra (best-effort) packets beyond the average rate/burst size specification. These packets are usually marked differently from the in-contract packets and transported across the network only if it's not congested. In most scenarios, the extra packets are allowed only in the initial burst (long-term traffic rate cannot exceed the average rate) and are measured with an extra token bucket (exceed bucket) as shown in the following diagram:
[URL="http://wiki.nil.com/Image:QoSPolicingDoubleBucket.gif"][IMG]http://wiki.nil.com/wk/images/7/7b/QoSPolicingDoubleBucket.gif[/IMG][/URL]
Dual token bucket contracts are common in ATM environments (where the excess cells are marked with CLP bits) and Frame Relay environments (where the excess frames are marked with the DE bit).
The dual token bucket algorithm is used by the [B]rate-limit [/B]command specifying the [B]exceed [/B]option and the [B]police [/B]command specifying the [B]exceed-action [/B]and [B]violate-action[/B]. In both cases, the size of the excess burst (but not the average excess rate) can be set.
[B] Example [/B]

The following router configuration allows e-mails to be sent at line speed if the size of the transfer does not exceed 100 kilobytes. However, the packets exceeding the 128kbps average rate and the 16 kilobytes initial burst size will be marked with a different DSCP value.
[CODE]
class-map match-any Mail
match protocol smtp
!
policy-map LimitEmails
class Mail
police rate 128000 burst 16000 peak-burst 100000
conform-action transmit
exceed-action set-dscp-transmit af13
violate-action drop

[/CODE] [B] Dual Rate Policing [/B]

In Frame Relay environment, the traffic contracts commonly specify average rate (Committed Information Rate – CIR) as well as constant excess rate (Excess Information Rate – EIR – or Peak Information Rate – PIR) that the customers can use.
The EIR mechanism is different from the excess burst size; the excess burst prolongs the initial packet burst (marking some packets as exceeding the contract) while the EIR allows long-term transmission of excess packets.
The CIR/EIR or CIR/PIR policing requires two independent token buckets as shown in the following diagram. Each bucket independently measures the traffic conformance to the average or peak/excess rate; there is no overflow from the [I]conforming[/I] bucket to the [I]excess [/I]bucket.
[URL="http://wiki.nil.com/Image:QoSPolicingDualRate.gif"][IMG]http://wiki.nil.com/wk/images/9/99/QoSPolicingDualRate.gif[/IMG][/URL]
The dual rate policing is configured with the [B]police [/B]command specifying [B]cir [/B]and [B]pir'[/B][I] [B]rates or [/B]rate [B]and [/B]peak-rate [B]parameters. In both cases, you can specify the [/B]burst [B]size and the [/B]peak-burst [B]size (they could be different). You also have to specify [/B]conform-action'[/I], [B]exceed-action [/B]and [B]violate-action[/B]; without the [B]violate-action[/B], the single token bucket measurement will be used.
[B] Example [/B]

The following service policy can be used on a Frame Relay interface to set the DE bits on excess packets and drop out-of-contract packets:
[CODE]
policy-map FrameRelay
class class-default
police cir 128000 pir 256000
conform-action transmit
exceed-action set-frde-transmit
violate-action drop
!
interface serial 1/0.1
frame-relay interface-dlci 100
service-policy output FrameRelay

[/CODE][/LEFT]