# A Sketch-Based Fine-Grained Proportional Integral Queue Management Method
###### Abstract  
The phenomenon \"bufferbloat\" occurs when the buffers of the network intermediary nodes fill up, causing long queuing delays. This has a significant negative impact on the quality of service of network applications, particularly those that are sensitive to time delay. Many active queue management (AQM) algorithms have been proposed to overcome this problem. Those AQMs attempt to maintain minimal queuing delays and good throughput by purposefully dropping packets at network intermediary nodes. However, the existing AQM algorithms mostly drop packets randomly based on a certain metric such as queue length or queuing delay, which fails to achieve fine-grained differentiation of data streams. In this paper, we propose a fine-grained sketch-based proportional integral queue management algorithm S-PIE, which uses an additional measurement structure Sketch for packet frequency share judgment based on the existing PIE algorithm for the fine-grained differentiation between data streams and adjust the drop policy for a differentiated packet drop. Experimental results on the NS-3 simulation platform show that the S-PIE algorithm achieves lower average queue length and RTT and higher fairness than PIE, RED, and CoDel algorithms while maintaining a similar throughput performance, maintaining network availability and stability, and improving network quality of service. queue management; frequency counting; differentiated packet drop; fine-grained identification; fairness 22 July 2  
quality of service of the network. Various AQM algorithms have been proposed in recent years, mainly random early detection (RED) [3], BLUE [4], controlled delay (CoDel) [5], proportional integral controller enhanced (PIE) [6], etc. However, these existing AQM algorithms drop data packets frequently and randomly in order to guarantee certain metrics, such as buffer queue length, queuing delay, etc., resulting in some TCP flows with weaker transmission capacity and lower bandwidth utilization being more impaired. The research goal of this study is to perform the fine-grained identification of data streams on the basis of guaranteeing the stability and throughput of data streams. To address the problem that the existing AQM algorithm cannot identify the network congestion status and distinguish the packet drop at a fine-grained level, this paper introduces the traffic measurement method into the traditional AQM algorithm PIE and proposes a Sketch-based proportional integral queue management algorithm S-PIE. The Sketch helps to find out which packets are in \"large flows\", i.e., which flows are congestion-causing flows, to decide which packets are more likely to be dropped, to reduce the bandwidth pressure when congestion is likely to occur, and to maintain better fairness. S-PIE has the following main features: (1) the Sketch structure is used to map and store the message information, and then the frequency of transmission of the current message in a certain time period can be obtained by querying the index of the Sketch, and to determine whether the packet corresponding to that data stream has a high traffic volume, so as to execute a differential drop policy; (2) the algorithm has lightweight characteristics, querying the frequency values of corresponding messages through Sketch and calculating the frequency of different data streams forwarded by the weighted averaging method, which has better robustness; (3) S-PIE can improve fairness between data flows and reduce queuing latency while maintaining throughput. The remainder of this paper is organized as follows. Section 2 describes the related work, including the active queue management algorithm used in this study and some related research advances. Section 3 presents the design of the proposed S-PIE algorithm. Section 4 presents an experimental and performance comparison that analyzes and compares the experimental results of the S-PIE algorithm with those of other classical AQM algorithms in different scenarios.