The last several years has seen a renewed interest in smart queue management to curb excessive network queueing delay, as people have realised the prevalence of bufferbloat in real networks. However, for an effective deployment at today's last mile connections, an improved queueing algorithm is not enough in itself, as often the bottleneck queue is situated in legacy systems that cannot be upgraded. In addition, features such as per-user fairness and the ability to de-prioritise background traffic are often desirable in a home gateway.In this paper we present Common Applications Kept Enhanced (CAKE), a comprehensive network queue management system designed specifically for home Internet gateways. CAKE packs several compelling features into an integrated solution, thus easing deployment. These features include: bandwidth shaping with overhead compensation for various link layers; reasonable DiffServ handling; improved flow hashing with both per-flow and per-host queueing fairness; and filtering of TCP ACKs. Our evaluation shows that these features offer compelling advantages, and that CAKE has the potential to significantly improve performance of last-mile internet connections.
Among the state of the art algorithms in modern queue management, is the FQ-CoDel algorithm @cite_4 . FQ-CoDel implements a hybrid AQM fairness queueing scheme which isolates flows using a hashing scheme and schedules them using a Deficit Round-Robin (DRR) @cite_13 scheduler. In addition, FQ-CoDel contains an optimisation that provides implicit service differentiation for sparse (low-bandwidth) flows, similar to @cite_0 @cite_8 . Evaluations of FQ-CoDel have shown that it achieves low queueing latency and high utilisation under a variety of scenarios @cite_6 @cite_5 .
@cite_4 @cite_8 @cite_6 @cite_0 @cite_5 @cite_13
2539125154 2147272999 1119123231 618348488 2097831241
This memo presents the FQ-CoDel hybrid packet scheduler and Active Queue Management (AQM) algorithm, a powerful tool for fighting bufferbloat and reducing latency. FQ-CoDel mixes packets from multiple flows and reduces the impact of head-of-line blocking from bursty traffic. It provides isolation for low-rate traffic such as DNS, web, and videoconferencing traffic. It improves utilisation across the networking fabric, especially for bidirectional traffic, by keeping queue lengths short, and it can be implemented in a memory- and CPU-efficient fashion across a wide range of hardware. In this paper we present Cross-protect, a combination of router mechanisms allowing quality of service differentiation while maintaining the simple user-network interface of the best effort Internet. By associating implicit flow level admission control and per-flow fair queuing in a router it is possible to distinguish streaming and elastic flows and meet their respective quality requirements without requiring specific packet marking. We describe the implied mechanisms and justify the claimed performance and scalability properties by means of simulation and analysis. Several new active queue management (AQM) and hybrid AQM fairness queueing algorithms have been proposed recently. They seek to ensure low queueing delay and high network goodput without requiring parameter tuning of the algorithms themselves. However, extensive experimental evaluations of these algorithms are still lacking. This paper evaluates a selection of bottleneck queue management schemes in a test-bed representative of residential Internet connections of both symmetrical and asymmetrical bandwidths as well as WiFi. Latency under load and the performance of VoIP and web traffic patterns are evaluated under steady state conditions. Furthermore, the impact of the algorithms on fairness between TCP flows with different RTTs, and also the transient behaviour of the algorithms at flow startup is examined. The results show that while the AQM algorithms can significantly improve steady state performance, they exacerbate TCP flow unfairness. In addition, the evaluated AQMs severely struggle to quickly control queueing latency at flow startup, which can lead to large latency spikes that hurt the perceived performance. The fairness queueing algorithms almost completely alleviate the algorithm performance problems, providing the best balance of low latency and high throughput in the tested scenarios. However, on WiFi the performance of all the tested algorithms is hampered by large amounts of queueing in lower layers of the network stack inducing significant latency outside of the algorithms' control. Active Queue Management (AQM) design has again come into the spotlight of network operators, vendors and OS developers. This reflects the growing concern and sensitivity about the end-to-end latency perceived by today’s Internet users. Indeed, delays on the order of seconds have become common due to the deployment of excessively-sized FIFO DropTail buffers at the edge of many networks. CoDel and PIE are two AQM mechanisms that have recently been presented and discussed at the IRTF and the IETF. However, to the best of our knowledge, they have not yet been thoroughly evaluated or compared against each other except by simulation. We set thus to perform an experimental evaluation using real-world implementations, in both wired and wireless testbeds. We have in addition compared them with a decade-old variant of RED called Adaptive RED, which shares with CoDel and PIE the goal of “knob-free” operation. Surprisingly, in many instances results were much more favorable towards Adaptive RED. We do not call into question the need for new AQMs, however, there are lessons yet to be learned from old designs. Fair queuing is a technique that allows each flow passing through a network device to have a fair share of network resources. Previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement; specifically, the work required to process a packet in these schemes was O(log(n)), where n is the number of active flows. This is expensive at high speeds. On the other hand, cheaper approximations of fair queuing reported in the literature exhibit unfair behavior. In this paper, we describe a new approximation of fair queuing, that we call deficit round-robin. Our scheme achieves nearly perfect fairness in terms of throughput, requires only O(1) work to process a packet, and is simple enough to implement in hardware. Deficit round-robin is also applicable to other scheduling problems where servicing cannot be broken up into smaller units (such as load balancing) and to distributed queues.