4.3.2.1.1 Modified Token Bucket Algorithm

Basic Operation

The modified token bucket algorithm allows each queue in a cluster to be assigned a fixed rate in bytes per time iteration (typically 25 µs, but is configurable). This is called iteration credit. In addition, there is a maximum number of bytes that can be retained as credit against a future traffic burst. This retained credit is called total credit. The maximum limit is called maximum credit.

Iteration credit is added to a queue's total credit at the start of each sampling period. While total credit remains above 0, the packet waiting at the head of the QoS queue is examined for size. If the byte size of the packet is less than or equal to the queue's total credit, the packet is forwarded and the packet byte size is deducted from the credit bytes. The queue's unused credit is carried over to the next iteration (held in its total credit), up to the maximum amount allocated to the queue.

For example, if a flow is rated for 40Mb/s, but can burst up to 20,000 bytes at a time, the queue would be configured as follows on a system with a 25-µs iteration:

• Iteration Credit = 125 bytes (40 Mb/s is 125 bytes every 25 µs)
• Maximum Credit = 20,000 bytes

The sum total of iteration credit for all queues in the cluster should add up to the total expected data rate of the egress device. When configuring a cluster, it is important that this rule be followed.

Global Credit and Borrowing

After all packets have been transmitted from a QoS queue, the queue's remaining total credit can not exceed the maximum credit allocated to that queue. Any credit bytes above the maximum credit limit are added to a global credit sum, and the total credit is set to the maximum credit.

Any queue may borrow from the global credit pool when doing so allows the queue to transmit an additional packet or is used to fill its allotted maximum credit level. This is done on a first come, first served basis. The global credit system allows queues that are allocated less credit than necessary to saturate a device to make use of the additional bandwidth when it is not being used by the other QoS queues in the cluster.

Thus in the example above, the queue was set to 40 Mb/s can use the entire bandwidth of the egress device when the other cluster queues are idle.

There is also a configurable maximum size on global credit. The limit on global credit is checked after every queue is processed. So for example, if the maximum global credit were set to 0, then the credit borrowing feature would be disabled.

Congestion and Packet Discard

A queue can become congested if the bandwidth of data arriving exceeds the bandwidth allocated or available. Each queue has a drop threshold expressed in bytes. Once the backlog in a QoS queue reaches its drop threshold, any packets that can not be transmitted are discarded until the backlog is cleared back below the threshold level.

For example, the 40-Mb/s flow with the 20,000-byte burst could be assumed to be congested if more than one burst’s worth of data has accumulated on the QoS queue. In this case, the drop threshold would be set to 40,000 bytes.

Congestion and Credit Scaling

The destination queue for a QoS cluster may also be congested. For example, a cluster may configure 100-Mb/s worth of data on an Ethernet device, but find that, for various reasons, the device is capable of sending only 70 Mb/s. The cluster algorithm will automatically scale the credit assigned to each queue according to how congested the egress queue becomes.

Each QoS cluster is configured with four egress congestion threshold values. Iteration credit is assigned to each queue in the cluster depending on the egress congestion, and the value of these four congestion thresholds. This is implemented as shown in Table 4-54.

Note that the use of double credit for near idle situations is used to ensure that each queue's burst potential be refilled as quickly as possible. It also allows the full bandwidth of a device to be used when the allocated bandwidth isn't quite enough to fill the device (for example allocating 98 Mb/s from a 100-Mb/s device).

If the egress queue for a cluster becomes congested due to external influences (like heavy load on the network), the credit scaling will affect each QoS queue equally. There may be cases in which some flows require hard real-time scheduling. In this case, the queue can be marked as real time and exempt from credit scaling.

For example, in a 100-Mb/s system that has two flows, a 40-Mb/s flow and everything else, the first queue in the cluster would be configured as 40-Mb/s real time, and the second queue can be configured as 60-Mb/s (without the real time setting). As the available bandwidth on the network drops, the 40-Mb/s flow would remain unaffected, while the 60-Mb/s flow would be scaled down.

Fixed Priority Configuration

This algorithm can also be used to implement a fixed-priority method, in which each queue is serviced in a fixed priority with the first queue in the cluster being the highest priority. This is done by assigning all iteration credit to the first queue in the cluster, and setting the maximum credit of each queue to the maximum packet size. This ensures that credit is passed only to subsequent queues when there are no packets waiting on the current queue.

For example, assume there are three queues, A, B, and C. In a simple priority system, queue A would always transmit packets when packets are available, while queue B transmits only when queue A is idle, and queue C transmits only when queue B is idle.

On a 100-Mb/s system, the queues could be configured as follows:

• Queue A
  • Iteration Credit = 313 (100 Mb/s is 312.5 bytes every 25 µs)
  • Max Credit = 1514
• Queue B
  • Iteration Credit = 0
  • Max Credit = 1514
• Queue C
  • Iteration Credit = 0
  • Max Credit = 1514

The way the algorithm works, queue A will get 313 bytes of credit at the start of each iteration. Because queue A can hold up to 1514 bytes as max credit, queue A will never pass credit onto queue B while queue A has a packet. (If queue A has more than 1514 bytes of credit, it can always forward a packet.)

Queue A must be idle for an entire packet time (1514 bytes of iteration credit) before any credit will start flowing into queue B. The same relationship holds between queue B and queue C. The only way queue B sends a packet is after queue A is idle for a packet time, and the only way queue C can send a packet is after queue B is idle for a packet time.