Frame Relay Traffic Policing and Shaping

Network Consultants Handbook – Frame Relay
by Matthew Castelli

Cisco IOS QoS offers two types of traffic regulation mechanisms: policing and shaping.

The rate-limiting features of committed access rate (CAR) and the traffic policing feature provide the functionality for policing traffic.

The features of GTS, class-based shaping, DTS, and FRTS provide the functionality for shaping traffic.

These features can be deployed throughout the network to ensure that a frame, packet, or other data source adheres to a stipulated contract. These features can also be used to determine the QoS with which to render the packet. Both policing and shaping mechanisms use the traffic descriptor for a packet — indicated by the classification of the packet — to ensure adherence and service.
Traffic policers and shapers identify traffic descriptor violations in an identical manner. These policers and shapers differ in how they respond to violations, for example:

• A policer drops traffic. For example, the CAR rate-limiting policer will either drop the packet or rewrite its IP precedence, resetting the type of service bits in the packet header.

• A shaper delays excess traffic using a buffer, or queuing mechanism, to hold packets and shape the flow when the data rate of the source is higher than expected. For example, GTS and class-based shaping use a weighted fair queue to delay packets to shape the flow. DTS and FRTS use either a priority queue, a custom queue, or a FIFO queue for the same, depending on how the queue is configured.

Traffic shaping and policing can work in tandem. For example, a good traffic-shaping scheme should make it easy for nodes that are inside the network to detect misbehaving flows. This activity is sometimes called “policing the traffic of the flow.”

Because policing and shaping each use the token bucket mechanism, token buckets will be discussed in the next section.

Token Bucket
A token bucket is a formal definition of a rate of transfer with three components: burst size, mean rate, and a time interval (TC). The mean rate is generally represented as bits per second, and any two values can be derived from the third, as shown by the following formula:

  mean rate = burst size / time interval

where:

• Mean rate — Also called the CIR. The mean rate specifies how much data can be sent or forwarded per unit time on average.
• Burst size — Also called the committed burst (Bc) size. The burst size specifies in bits (or bytes) per burst how much traffic can be sent within a given unit of time without creating scheduling concerns. For a shaper, such as GTS, burst size specifies bits per burst; for a policer, such as CAR, burst size specifies bytes per burst.
• Time interval (TC) — Also called the measurement interval. The time interval specifies the time in seconds per burst. By definition, over any integral multiple of the interval, the bit rate of the interface will not exceed the mean rate. The bit rate, however, might be arbitrarily fast within the interval.

A token bucket is used to manage a device that regulates the data in a flow. For example, the regulator might be a traffic policer, such as CAR, or a traffic shaper, such as FRTS or GTS. A token bucket has no discard or priority policy. Rather, a token bucket discards tokens and leaves to the flow the problem of managing its transmission queue if the flow overdrives the regulator. (CAR, FRTS, and GTS do not implement either a true token bucket or a true leaky bucket.)

In the token bucket metaphor, the following occurs:

• Tokens are put into the bucket at a certain rate. The bucket has a specified capacity.
• If the bucket fills to capacity, newly arriving tokens are discarded.
• Each token has permission for the source to send a certain number of bits into the network.
• To send a packet, the regulator must remove from the bucket a number of tokens equal in representation to the packet size.
• If not enough tokens are in the bucket to send a packet, the packet either waits until the bucket has enough tokens (in the case of GTS), or the packet is discarded or marked down (in the case of CAR).
• If the bucket is already full of tokens, incoming tokens overflow and are not available to future packets. Thus, at any time, the largest burst that a source can send into the network is roughly proportional to the size of the bucket.

The token bucket mechanism used for traffic shaping has both a token bucket and a data buffer, or queue. If the token bucket mechanism for traffic shaping did not have a data buffer, it would be a traffic policer.

The following applies for traffic shaping:

• Packets that arrive that cannot be sent immediately are delayed in the data buffer.
• A token bucket permits burstiness, but also bounds it.
• Traffic shaping guarantees that the burstiness is bounded so that the flow will never send more quickly than the capacity of the token bucket plus the time interval multiplied by the established rate at which tokens are placed in the bucket.
• Traffic shaping guarantees that the long-term transmission rate will not exceed the established rate at which tokens are placed in the bucket.

Traffic Policing with CAR
CAR is a rate-limiting feature for policing traffic, in addition to its packet classification feature. The rate-limiting feature of CAR manages the access bandwidth policy for a network by ensuring that traffic that falls within specified rate parameters is sent, while dropping packets that exceed the acceptable amount of traffic or sending them with a different priority. CAR’s exceed action is to either drop or mark down the packet’s priority.

The CAR rate-limiting function performs the following:

• Controls the maximum rate of traffic sent or received on an interface.
• Defines Layer 3 aggregate or granular incoming or outgoing (ingress or egress) bandwidth rate limits and specifies traffic-handling policies when the traffic either conforms to or exceeds the specified rate limits.

CAR bandwidth rate limits perform one of two functions:

• Aggregate — Aggregate bandwidth rate limits match all of the packets on an interface or subinterface.
• Granular — Granular bandwidth rate limits match a particular type of traffic based on precedence, MAC address, or other parameters.

CAR is often configured on interfaces at the edge of a network to limit traffic into or out of a network.

CAR Operation
CAR examines traffic received on an interface or a subset of that traffic selected by access list criteria. CAR compares the rate of the traffic to a configured token bucket and takes action based on the result. For example, CAR will drop the packet or rewrite the IP precedence by resetting the type of service (ToS) bits.

CAR can be configured to send, drop, or set precedence.

Aspects of CAR rate limiting include the following:

• Matching criteria
• Rate limits
• Conform and exceed actions
• Multiple rate policies

CAR utilizes a token bucket measurement, operating as follows:

• Tokens are inserted into the bucket at the committed rate.
• The depth of the bucket is the burst size.
• Traffic arriving at the bucket when sufficient tokens are available is said to conform, and the corresponding number of tokens is removed from the bucket.
• If a sufficient number of tokens is not available, then the traffic is said to exceed.

CAR Traffic-Matching Criteria
Traffic matching involves the identification of interesting traffic for rate limiting, precedence setting, or both. Rate policies can be associated with one of the following qualities:

• Incoming interface
• All IP traffic
• IP precedence (defined by a rate-limit access list)
• MAC address (defined by a rate-limit access list)
• IP access list (standard and extended)

CAR provides configurable actions, such as send, drop, or set precedence when traffic conforms to or exceeds the rate limit.

Matching to IP access lists is more processor intensive than matching based on other criteria.

Rate Limits
CAR propagates bursts and performs no smoothing or shaping of traffic; therefore, it performs no buffering and adds no delay. CAR is optimized (but not limited) to run on high-speed links, such as DS3 or higher, and in distributed mode on Versatile Interface Processors (VIPs) on the Cisco 7500 series.

CAR rate limits can be implemented either on input or output interfaces or subinterfaces, including those found with Frame Relay and ATM implementations.

Rate limits define which packets conform to or exceed the defined rate based on the following three parameters:

• Average rate — Determines the long-term average transmission rate. Traffic that falls under this rate will always conform.
• Normal burst size — Determines how large traffic bursts can be before some traffic exceeds the rate limit.
• Excess Burst size (BE) — Determines how large traffic bursts can be before all traffic exceeds the rate limit. Traffic that falls between the normal burst size and the Excess Burst size exceeds the rate limit with a probability that increases as the burst size increases.

The tokens in a token bucket are replenished at regular intervals, in accordance with the configured committed rate. The maximum number of tokens that a bucket can contain is determined by the token bucket’s normal burst size configuration.

When the CAR rate limit is applied to a packet, CAR removes from the bucket tokens that are equivalent in number to the byte size of the packet. If a packet arrives and the byte size of the packet is greater than the number of tokens available in the token bucket, extended burst capability is engaged (if it is configured).

Setting the extended burst value greater than the normal burst value configures extended burst. Setting the extended burst value equal to the normal burst value excludes the extended burst capability. If extended burst is not configured, the CAR exceed action takes effect because a sufficient number of tokens are not available.

When extended burst is configured, the flow is allowed to borrow the needed tokens to allow the packet to be sent. This capability exists to avoid tail-drop behavior, and, instead, engage behavior like that of random early detection (RED).

Extended burst operates in the following fashion:

• If a packet arrives and needs to borrow n number of tokens because the token bucket contains fewer tokens than its packet size requires, then CAR compares the following two values:
  • Extended burst parameter value
  • Compounded debt, which is computed as the sum over all ai:

  a indicates the actual debt value of the flow after packet i is sent. Actual debt is simply a count of how many tokens the flow has currently borrowed.
  i indicates the packet that attempts to borrow tokens since the last time a packet was dropped.

• If the compounded debt is greater than the extended burst value, the exceed action of CAR takes effect. After a packet is dropped, the compounded debt is effectively set to 0. CAR computes a new compounded debt value equal to the actual debt for the next packet that needs to borrow tokens.

• If the actual debt is greater than the extended limit, all packets are dropped until the actual debt is reduced through accumulation of tokens in the token bucket.

Dropped packets do not count against a rate or burst limit. In other words, when a packet is dropped, no tokens are removed from the token bucket.

Although the entire compounded debt is forgiven when a packet is dropped, the actual debt is not forgiven, and the next packet to arrive to insufficient tokens is immediately assigned a new compounded debt value equal to the current actual debt. In this way, actual debt can continue to grow until it is so large that no compounding is needed to cause a packet to be dropped. In effect, the compounded debt is not really forgiven. This scenario leads to excessive drops on streams that continually exceed normal burst.

Cisco recommends the following values for the normal and extended burst parameters:

  normal burst = configured rate 4 (1 byte)/(8 bits) 4 1.5 seconds
  extended burst = 2 4 normal burst

Now look at an example that shows how the compounded debt is forgiven, but the actual debt accumulates.

In this example, the following parameters are assumed:

• Token rate is 1 data unit per time unit
• Normal burst size is 2 data units
• Extended burst size is 4 data units
• 2 data units arrive per time unit

After two time units, the stream has used up its normal burst and must begin borrowing one data unit per time unit, beginning at time unit 3:

 Time    DU arrivals     Actual Debt     Compounded Debt
 -------------------------------------------------------
 1       2               0               0
 2       2               0               0
 3       2               1               1
 4       2               2               3
 5       2               3 (temporary)   6 (temporary)

The following actions occur at this time:

• A packet is dropped because the new compounded debt (6) would exceed the extended burst limit (4).
• When the packet is dropped, the compounded debt effectively becomes 0, and the actual debt is 2. (The values 3 and 6 were only temporary and do not remain valid if a packet is dropped.)
• The final values for time unit 5 follow. The stream begins borrowing again at time unit 6.

 Time    DU arrivals     Actual Debt     Compounded Debt
 -------------------------------------------------------
 5       2               2               0
 6       2               3               3
 7       2               4 (temporary)   7 (temporary)
 At time unit 6, another packet is dropped and the debt values are
  adjusted accordingly.
 Time    DU arrivals     Actual Debt     Compounded Debt
 -------------------------------------------------------
 7       2               3               0

Conform and Exceed Actions
Because CAR utilizes a token bucket, CAR can pass temporary bursts that exceed the rate limit as long as tokens are available.

After a packet has been classified as conforming to or exceeding a particular rate limit, the router performs one of the following actions:

• Transmit — The packet is sent.
• Drop — The packet is discarded.
• Set precedence and transmit — The IP precedence (ToS) bits in the packet header are rewritten. The packet is then sent. You can use this action to either color (set precedence) or recolor (modify existing packet precedence) the packet.
• Continue — The packet is evaluated using the next rate policy in a chain of rate limits. If another rate policy does not exist, the packet is sent.
• Set precedence and continue — Set the IP precedence bits to a specified value and then evaluate the next rate policy in the chain of rate limits.

For VIP-based platforms, two more actions are possible:

• Set QoS group and transmit — The packet is assigned to a QoS group and sent.
• Set QoS group and continue — The packet is assigned to a QoS group and then evaluated using the next rate policy. If another rate policy does not exist, the packet is sent.

Multiple Rate Policies
A single CAR rate policy includes information about the rate limit, conform actions, and exceed actions. Each interface can have multiple CAR rate policies corresponding to different types of traffic. For example, low-priority traffic might be limited to a lower rate than high-priority traffic. When multiple rate policies exist, the router examines each policy in the order entered until the packet matches. If no match is found, the default action is to send.

Rate policies can be independent or cascading:

• Independent — Each rate policy deals with a different type of traffic.
• Cascading — A packet might be compared to multiple different rate policies in succession.

Cascading of rate policies supports a series of rate limits to be applied to packets to specify more granular policies. For example, total traffic could be rate limited on an access link to a specified subrate bandwidth and then rate limit World Wide Web traffic on the same link to a given proportion of the subrate limit.

Match packets could be rate limited against an ordered sequence of policies until an applicable rate limit is encountered. For example, as the sequence of policies is applied, the rate limiting of several MAC addresses with different bandwidth allocations can occur at an exchange point.

Up to 100 rate policies can be configured on a subinterface.

CAR Restrictions
CAR and VIP-distributed CAR can only be used with IP traffic. Non-IP traffic is not rate limited.
CAR or VIP-distributed CAR can be configured on an interface or subinterface, with the exception of the following interface types:

• Fast EtherChannel
• Tunnel
• PRI
• Any interface that does not support Cisco Express Forwarding (CEF)

CAR is supported only on ATM subinterfaces with the following encapsulations: aal5snap, aal5mux, and aal5nlpid.

CAR provides rate limiting and does not guarantee bandwidth. CAR should be used with other QoS features, such as distributed weighted fair queuing (DWFQ), if premium bandwidth assurances are required.

—
Our final segment from Cisco Press’ Network Consultants Handbook will summarize Frame Relay.