QoS Token Bucket Algorithm Analysis
Traffic Policing in QoS controls traffic by monitoring the rate of traffic entering a network port and "punishing" excess traffic (this punishment can be dropping or delaying transmission), thereby limiting the traffic entering the port to a reasonable range. For example, it can restrict HTTP messages from occupying more than 50% of the network bandwidth; otherwise, the QoS traffic policing function can choose to drop the messages or reconfigure their priority.
The QoS traffic policing function is implemented using a Token Bucket mechanism. Here, a "token bucket" refers to an internal storage pool within a network device, and "tokens" refer to virtual information packets that fill the token bucket at a given rate. These virtual information packets are used to determine the current rate of incoming messages.
When a switch receives each frame, it adds a token to the token bucket. However, this token bucket has a hole at the bottom, constantly releasing tokens (i.e., removing tokens from the bucket) at a rate you specify as the average communication rate (in b/s). This is analogous to a water bucket with an inlet pipe at the top and an outlet pipe at the bottom leading to where the water is used. Each time a new token packet is to be added to the token bucket, the switch checks if there is sufficient capacity in the token bucket (i.e., before adding water to the bucket, it first checks if the bucket is already full). If there is not enough space, the packet will be marked as non-compliant, and the action specified by the regulator (discard or mark) will be applied to the packet. This is similar to a full water bucket where water from the inlet pipe still arrives; at this point, either the excess water flows out of the bucket, or it is collected in another container and poured back in when the bucket is no longer full, for user consumption. The basic working principle of the entire token bucket can be represented by Figure 6-10 
The time it takes for the token bucket to fill is jointly determined by three factors: the token bucket depth (i.e., capacity, in bits, similar to the depth of a water bucket), the token leakage rate (similar to the water flow rate from the pipe at the bottom of the bucket), and the duration of burst traffic exceeding the average rate (similar to a sudden rapid flow of water from the pipe at the top of the bucket). The size of the token bucket is derived by multiplying the maximum burst duration by the frame limit during point-to-point transmission (similar to the duration of a burst water flow * the flow rate of the burst water flow). If the burst duration is short, the token bucket will not overflow, and no action will be taken on the traffic flow. However, if the burst duration is long and the rate is high, the token bucket will overflow, and at this point, corresponding traffic policing policy actions will be taken on the frames during the burst (i.e., how to handle the overflowing water when the bucket is full).
Regarding the behavior of token buckets in processing packets, RFCs define two token bucket algorithms: the single rate three-color marker (srTCM) algorithm and the two rate three-color marker (trTCM) algorithm. Both evaluate packets and mark them with red, yellow, or green (hence "three-color marker"; the specific meanings of these colors will be introduced in the respective algorithms). QoS sets the packet's discard priority based on its color. The single rate three-color marker is more concerned with burst size, while the two rate three-color marker focuses on rate bursts. Both algorithms can operate in color-blind and color-aware modes (described below). The principles of these two algorithms are introduced separately below.
1. Single Rate Three-Color Marker Algorithm Principle
First, it's important to understand what "single rate" means here: both token buckets in the algorithm have the same Committed Information Rate (CIR), meaning they have the same average access rate. These two token buckets are the normally used token bucket (referred to as the C bucket below) and the burst token bucket for exceeding capacity (referred to as the E bucket below). This can be understood as two water buckets: one for normal use, and another for holding excess water when the first bucket is full. The principle of the single rate three-color marker algorithm is explained in detail below.
The single rate three-color marker (srTCM) algorithm focuses on packet burst size. Packet color marking is evaluated based on the following three parameters: Committed Information Rate (CIR), Committed Burst Size (CBS), and Excess Burst Size (EBS). CIR refers to the average rate at which tokens are filled into the token bucket, i.e., the allowed average traffic speed. CBS refers to the maximum traffic size allowed for each burst, which is also equivalent to the maximum rate at which tokens can be taken, equal to the bucket's capacity (at maximum, a single packet can consume all tokens in the bucket). EBS refers to the maximum traffic size allowed to exceed CBS for each burst. The units for both CBS and EBS are bits.
The single rate three-color mechanism uses a dual-bucket structure: C bucket and E bucket (these letters are used to align with the first letters of CBS and EBS, respectively, for ease of description). Both token buckets have the same CIR. Any unused tokens in the C token bucket are placed into the E token bucket, to be used for future burst traffic that temporarily exceeds the CIR. Additionally, when the C token bucket is full, excess tokens are also placed into the E token bucket.
Tc and Te represent the number of tokens in the C token bucket and E token bucket, respectively, which is the current capacity in the buckets (also in bits). The total capacities of the two buckets are CBS and EBS, corresponding to the Committed Burst Size and Excess Burst Size introduced earlier. Initially, both are full, meaning the initial values of Tc and Te are equal to CBS and EBS, respectively. Under normal circumstances, the second token bucket (E bucket) is not used directly; instead, any unused tokens from CBS (i.e., the C bucket) are placed into the E bucket. Only when the C token bucket is full are subsequent tokens placed into the E token bucket, providing credit tokens (i.e., allowed tokens) for potential burst data.
In this single rate three-color marker algorithm, tokens are added to both token buckets at the same CIR rate. That is, one token is added every 1/CIR time. The order of addition is to fill the C bucket first, then the E bucket. When both token buckets are full, any newly generated tokens are discarded. Regarding token usage when sending data packets, IEEE defines three colors (red, yellow, and green) and two modes: color-blind mode and color-aware mode, with color-blind mode being the default. The functions of these three colors are similar to the three colors of traffic lights in our daily lives: red indicates non-compliant data, which is directly discarded; yellow indicates that although the packet is non-compliant, it is not directly discarded but rather delayed; and green indicates compliant data packets, which are sent directly.
In color-blind mode, it is assumed that packets have not been "colored" (the original marked color in the packet is not distinguished), and the packet's marked color is determined based on its length. Let's assume the arriving packet length is B (in bits). If packet length B is less than the number of tokens Tc in the C bucket (meaning the number of tokens in the C bucket is sufficient for sending this packet), the packet is marked green, indicating compliance. After the packet is sent, the number of tokens Tc in the C bucket decreases by B. If Tc < B < Te (meaning the packet length is greater than the number of tokens in the C bucket but less than the number of tokens in the E bucket), it is marked yellow, and the required tokens are taken from the E bucket, reducing Te by B. If B > Te, it is marked red, indicating a non-compliant packet, which is directly discarded, and the total number of tokens in both token buckets does not decrease.
In color-aware mode, it is assumed that packets have been "colored" beforehand (the original marked color in the packet is distinguished). If a packet has already been marked green, or if packet length B < Tc (note that only one of these conditions needs to be met, same below), then the packet is marked green, and the value of Tc in the C bucket decreases by B accordingly. If a packet has already been marked yellow, or if Tc < B < Te, then the packet is marked yellow, and the value of Te in the E bucket decreases by B accordingly. If a packet has already been marked red, or if B > Te, then the packet is marked red, and neither Tc nor Te decreases.
2. Two-Rate Three-Color Algorithm
Here, it's also important to first clarify what "two rate" means: it refers to the fact that the two token buckets in this algorithm have different CIR rates, meaning there are two token filling rates.
The IETF's two rate three-color marker (trTCM) algorithm primarily evaluates based on four traffic parameters: CIR, CBS, Peak Information Rate (PIR), and Peak Burst Size (PBS). The CIR and CBS parameters have the same meaning as in the single rate three-color algorithm. PIR is the maximum allowed burst information transmission rate, and its value will certainly not be less than CIR. PBS is the maximum allowed burst information size, and its value will also not be less than CBS.
Unlike the single rate three-color marker algorithm, the two token buckets in the two rate three-color marker algorithm are the C bucket and the P bucket (not the C bucket and the E bucket). However, their token filling rates are different: the C bucket filling rate is CIR, and the P bucket filling rate is PIR. The capacities of the two buckets are CBS and PBS, respectively (C and P buckets are used for convenience of description, as the parameters representing different rates correspond to the bucket capacities, with the first letter being C or P). Tc and Tp represent the number of tokens in the two buckets. In the initial state, both buckets are full, meaning the initial values of Tc and Tp are equal to CBS and PBS, respectively.
The two rate three-color marker algorithm focuses on rate bursts, but unlike the single rate three-color marker algorithm, it does not place unused tokens from the first bucket into the second. Instead, it uses two independent token buckets. The first token bucket is for PIR, with a size of PBS, and the second token bucket is for CIR, with a size of CBS.