# On Cross-Layer Interactions for Congestion Control in the Internet
## 4 AQM Algorithms
### Pie  
The main purpose of the Proportional Integral Enhanced (PIE) controller [27] is to deal with a bufferboat problem by effectively controlling the average queuing delay to a target value and providing high bandwidth utilization under varying conditions at the same time. PIE is an enhancement to the Proportional Integral (PI) controller. Assumptions that stand behind PIE design are straightforward implementation and scalability in high-speed networks. In contrast to PI, PIE parameters are auto-tuned.  
On a reception, PIE drops a packet randomly with a probability \(p\) before enqueuing. When the packet is dequeued, PIE calculates the average dequeue rate \(avg\_rate\). This value is used to estimate the available bandwidth and to track its variation. The calculations are performed in measurement cycles. If the current queue length exceeds a defined threshold (set to 16 kB by default), a new measurement cycle is started, during which PIE keeps track of the summed size of dequeued packets. The threshold should mean that the measurements are carried out when the queue backlog is large enough; such a precaution provides a meaningful estimate of the dequeue rate. The measurement cycle ends when the number of dequeued bytes exceeds the defined threshold. Then, PIE computes the dequeue rate and derives the average dequeue rate as a weighted average of the previous average dequeue rate and the last dequeue rate sample.  
For every \(T_{update}\) interval rate (15 ms as recommended by [27] ), the current queuing delay is updated--from the Little's Law--as a ratio of the current queue length \(qlen\) and the estimated average dequeue rate \(avg\_rate\). The dropping probability \(p\) is also updated as a linear combination of the previous value, the difference between the current queue delay \(cur_{del}\) and the reference value \(ref_{del}\) (weighted by a parameter \(\alpha\)), and the difference between the current queue delay \(cur_{del}\) and the previous queue delay \(old_{del}\) (weighted by a parameter \(\beta\)). PIE steady state is achieved when the current queue delay equals the reference queue delay. PIE scales parameters \(\alpha\) and \(\beta\) to adapt the dropping probability to the current network conditions. Summarizing, in every rate interval, the following calculations occur:  
\[cur_{del}=\frac{qlen}{avg\_rate}, \tag{3}\] \[p=p+\alpha*(cur_{del}-ref_{del})+\beta*(cur_{del}-old_{del}),\] \[old_{del}=cur_{del},\]  
Basing on the current value of dropping probability \(p\), the scale parameters \(\alpha\) and \(\beta\) are determined as follows:  
\[\text{if }p<0.01,\,\alpha=\overline{\alpha}/8, \beta=\overline{\beta}/8, \tag{4}\] \[\text{else if }p<0.1,\,\alpha=\overline{\alpha}/2, \beta=\overline{\beta}/2,\] \[\text{else, }\alpha=\overline{\alpha}, \beta=\overline{\beta},\]  
where \(\overline{\alpha}\) and \(\overline{\beta}\) are the initial values of both parameters.  
The main problem of PIE in the real world comes from the implementation. Linux traffic control module dequeues several packets simultaneously, which influences the average dequeue rate, which is closer to the estimated rate at which packets are stored in the device driver's transmission ring. To overcome this issue, the authors of [28] proposed using packet timestamps for dequeue rate calculations. Moreover, in [29], the authors claim that in 100 Mbps and faster networks, adapting the \(ref_{del}\) results in shorter standing queues.