Chinese name: Introduction of token bucket algorithm, working parameters of token bucket, labeling, classification and introduction. When transmitting data in the network, in order to prevent network congestion, it is necessary to limit the traffic flowing out of the network so that the traffic can be transmitted at a relatively uniform speed. Token bucket algorithm realizes this function, which can control the amount of data transmitted to the network and allow the transmission of burst data. Token bucket algorithm is one of the most commonly used algorithms in network traffic shaping and rate limiting. Usually, token bucket algorithm is used to control the amount of data transmitted to the network and allow the transmission of burst data. A token bucket with a fixed size can continuously generate tokens at a constant rate. If tokens are not consumed, or the consumption rate is less than the production rate, tokens will continue to increase until the bucket is filled. Tokens generated later will overflow from the bucket. The maximum number of tokens that can be saved in the last bucket will never exceed the size of the bucket. The packets sent to the token bucket need to consume tokens. The number of tokens consumed is different for packets of different sizes. Token bucket is a control mechanism that indicates when traffic can be transmitted according to whether there are tokens in the token bucket. Each token in the token bucket represents a byte. If there is a token in the token bucket, traffic is allowed to be transmitted; If there is no token in the token bucket, traffic is not allowed to be transmitted. Therefore, if the burst threshold is reasonably configured and there are enough tokens in the token bucket, the traffic can be transmitted at the peak rate. The basic process of token bucket algorithm is as follows: if the average transmission rate configured by the user is r, a token is added to the bucket every 1/r seconds; Assume that a bucket can store and issue at most b tokens. If the token bucket is full when the token arrives, the token will be discarded; When an n-byte data packet arrives, delete n tokens from the token bucket and send the data packet to the network; If there are less than n tokens in the token bucket, the tokens will not be deleted, and the packet is regarded as exceeding the traffic limit; The algorithm allows bursts of up to b bytes, but from the long-term running results, the packet rate is limited to a constant r, and packets exceeding the traffic limit can be handled in different ways: they can be discarded; When enough tokens are accumulated in the token bucket, they can queue up for transmission; They can continue to transmit, but they need to be specially marked. When the network is overloaded, these specially marked packets will be discarded. Note: Token bucket algorithm should not be confused with another common algorithm "leaky bucket". The main difference between these two algorithms is that leaky bucket can restrict the data transmission rate, while token bucket algorithm can limit the average data transmission rate and allow some burst transmission. In the token bucket algorithm, as long as there are tokens in the token bucket, data can be transmitted suddenly until the user-configured threshold is reached, so it is suitable for traffic with sudden characteristics. The working process of token bucket working parameters includes three stages: token generation, token consumption and judging whether the data packet passes or not. There are two parameters involved: token generation rate CIR (committed information rate) /EIR (excess information rate) and token bucket size CBS (committed burst size) /EBS (excess burst size). Let's briefly summarize the relationship between these three stages and two parameters with charts. Token generation: Tokens are added to the token bucket regularly at the rate of CIR/EIR, and the number of tokens in the bucket is increasing. If the number of tokens in the bucket has reached CBS/EBS, the redundant tokens are discarded. Consume tokens: incoming packets will consume tokens in the bucket. In network transmission, the size of data packets is usually inconsistent. Large packets consume more tokens than small packets. Judging whether it passes or not: the result of the input packet passing through the token bucket includes the output packet and the discarded packet. When the number of tokens in the bucket can meet the demand of the packet for tokens, the packet is output, otherwise the packet is discarded. The measurement and marking of tagged traffic are mainly used in differentiated services architecture. The function of the meter is mainly to measure and test the flow characteristics of the flow according to the flow specifications related to the flow, and judge whether it meets the flow specifications or not. The basis of measurement is the business specification of service package flow. The tag marks each metered IP packet as the basis for the network to process the packet according to the tag in the future. In differentiated services architecture, the tags of packages are the settings and services of packages. The functions of measurement and marking are accomplished in coordination, and the measurement results are transmitted to the marking machine as the basis for marking. Mark generally refers to the combination of two functions, and its composition is shown in the figure. There are two ways to classify markers, one is to classify markers according to different colors, including two-color markers and three-color markers; The other category is classified by implementation mechanism, including token bucket-based marking, rate-based marking and policy-based marking. There are many typical tag classification algorithms based on token bucket. The basic algorithm mainly includes in/out fair marking (FM) and tricolor marking (TCM), and the extended algorithm mainly includes single-rate tricolor marking (srTCM) and double-rate tricolor marking (trTCM). Among them, single-rate marking and double-rate marking are called IETF standard recommendations respectively. In/out Fairness Mark (FM) FM is a two-color single token bucket mark. Its Tspec is that the average packet speed of the system is recorded as R, and the allowed burst is B. Its working principle is that when IP packets arrive, if there are enough tokens in the bucket, the packets that meet Tspec will be marked as IN. If there are not enough tokens at this time, it is considered that the arriving packets do not conform to Tpsec, and the packets that do not conform to Tpsec will be marked as OUT, and the network may handle these packets marked as different attributes differently according to the corresponding policies. Single rate tricolor marker (srTCM) srTCM is a tricolor double token bucket marker, and its Tpsec has three parameters: committed information rate, committed burst size and excess burst size. Bps for CIR, Byte for CBS and EBS. SrTCM consists of two token buckets C and E, which have the same CIR and the capacity of CBS and EBS respectively. The memory of bucket C is filled with yellow tokens, and token buckets C and E are full at the beginning. If the incoming packet does not exceed CBS, it is marked as green; More than CBS and not more than EBS marked yellow; Otherwise, mark it in red. In DiffServ, red, yellow and green can be mapped to different DSCP values. Double Rate Marker (trTCM) trTCM is also a three-color double token bucket marker, and its Tpsec has four parameters: Peak Information Rate (PIR), Peak Burst Size (PBS), committed information rate (CIR) and Commitment Burst Size (CBS). PIR and CIR are in bps, while PBS and CBS are in bytes.