# A Sketch-Based Fine-Grained Proportional Integral Queue Management Method
## 3 System Model
### Queue Management  
Based on the PIE algorithm, the queue management part of the S-PIE algorithm adds a Sketch-based traffic statistics module, which is mainly divided into: adding Sketch's insertion operation and frequency counting function before leaving the queue, adding Sketch's query operation when judging packet drop before entering the queue, and adjusting packet drop conditions to realize a differentiated packet drop policy. The specific process is as follows. in Equation (3), according to the working mode of PIE, where \(p\_old\) is the packet drop probability obtained in the previous calculation cycle. \(del\_cur\) and \(del\_old\) denote the current queuing delay and the last estimate of the queuing delay, respectively, and \(del\_ref\) denotes the reference value of the delay. \(\alpha\) and \(\beta\) are two adjustment parameters. The parameter \(\alpha\) determines how the deviation of the \(del\_cur\) from the \(del\_ref\) affects the drop probability; the parameter \(\beta\) makes an additional adjustment to the drop probability depending on whether the trend of the delay change is increasing or decreasing. \(del\_cur\) is calculated as in Equation (4), where \(q\_len\) is the current queue length and \(dq\_rate\_avg\) is the calculated average departure rate, as in Equations (5) and (6), where \(dq\_count\) indicates the number of packets left since the last measurement, and \(\varepsilon\) is the average parameter. In addition, to prevent short, non-persistent packet bursts that lead to empty queues and render the off-queue rate measurement less accurate, the algorithm sets a threshold value that reduces the off-queue rate \(dq\_rate\) when the queue length exceeds the threshold value. The flow of the S-PIE algorithm is shown in Algorithm 1. \[p=p\_old+\alpha\big{(}del\_old-del\_ref\big{)}+\beta\big{(}del\_cur-del\_old \big{)}\] (3) \[del\_cur=\frac{q\_len}{dq\_rate\_avg}\] (4) \[dq\_rate=\frac{dq\_count}{dq\_time}\] (5) \[dq\_rate\_avg=\big{(}1-\varepsilon\big{)}*dq\_rate\_avg(old)+\varepsilon*dq \_rate\] (6)
* Enqueue: before the packets enter the queue, it first judges whether the queue is full, and if it is full, the packets are dropped directly. If the queue is not full, the current network state is judged according to the \(del\_cur\) obtained when the packets are out of the queue, and if \(del\_cur\) < \(del\_ref\)/3, the network is considered to be in a relatively uncongested state, and the packets are dropped probabilistically according to the calculated probability \(p\). Otherwise, the network is considered to be in a relatively congested state, and the function \(Query()\) of Sketch is called to obtain the frequency of new packets appearing in the current phase \(m\_res\), as shown in Equation (7). The percentage of data stream \(k\) corresponding to this packet appearing in the queue at the same time was calculated, as shown in Equation (8), where \(m\_count\) is the total number of packets mapped in Sketch, i.e., the total number of packets passing through the intermediate nodes of the network in the current time period. Then, the threshold \(G_{Threshold}\) is calculated using Equation (9) when the percentage of the stream occupying the router cache space reaches the set threshold \(G_{Threshold}\), i.e., when the packet percentage of a stream exceeds the weighted average queue percentage, the stream is judged to be a large stream and the packet is dropped. Otherwise, the flow corresponding to the packet is considered to be a small flow and is allowed to enter the queue. The flow of the S-PIE algorithm is shown in Algorithm 2.