[network communication -- webrtc] analysis of webrtc source code -- supplement of pacingcontroller related knowledge points

【 Network communication -- WebRTC】WebRTC Source code analysis -- PacingController Relevant knowledge points supplement

【1】 Introduction to leaky bucket current limiting algorithm

Leaky bucket algorithm (Leaky Bucket) Network traffic shaping (Traffic Shaping) Or speed limit (Rate Limiting) An algorithm often used when , Its main purpose is to control the rate of data injection into the network , Smooth the burst traffic on the network ;
As shown in the figure , Compare the request to water , When the water comes, put it in the bucket first , And at a limited rate , When the water comes too fast and the water doesn't come out fast enough, it will cause the water to overflow directly , Denial of service ;

Leaky bucket current limiting algorithm -- Main attribute fields

• 1. The rate at which requests are processed (rate), This value represents how often a request is processed
• 2. The maximum capacity of the barrel (capacity), This value represents the maximum number of requests allowed to queue
• 3. The time when the last queued request in the bucket is processed (last)
  • 1) When a new request comes in , You can calculate how long a new request needs to be processed ,last + rate
  • 2) according to last、 current time (t) And speed (rate) Calculate how many requests are currently waiting to be processed ,waitRequests = (last - t) / rate 

Leaky bucket current limiting algorithm --  How to calculate the actual processing time of the request

• 1. Calculate the interval between the current time and the last processed time
• 2. And rate Compare , Calculation and rate The difference between the , Then complete the difference

delta =  current time (t) - last
last =  current time (t) + (rate - delta)

Leaky bucket current limiting algorithm -- " bucket " Full judgment method

• According to the current time (t), And the time when the last request queued in the bucket is processed (last) Difference between , Then divide by the rate (rate), Calculate the number of requests waiting to be processed , Then with the maximum capacity of the barrel (capacity) Just compare

Reference and thanks

This blog is a study note for bloggers , At the same time, I refer to the blogs of online bloggers and relevant professional books , Thank you , If there are deficiencies in this paper , Please criticize and correct me .

【1】 Graphic leaky bucket （LeakyBucket） Implementation principle of current limiter

【2】 Interface current limiting algorithm ： Leaky bucket algorithm & Token bucket algorithm

【3】 Current limiting —— The difference between leaky bucket algorithm and token bucket algorithm