Self-tuning active queue management for combating bufferbloat

Abstract

The Internet is playing an increasingly important role in providing real-time communication for people via network applications that impose stringent requirements on delivery delay. On the other hand, inexpensive memory has given rise to large router buffers installed in the Internet. Excessive buffering of packets results in high queueing delay and delay variation, which is recently termed "bufferbloat." Larger buffer sizes and more delay-sensitive applications on the Internet have made bufferbloat a pressing issue.

Active queue management (AQM) has been proposed to manage router buffers by dropping packets probabilistically before a buffer gets full. AQM plays a crucial role in combating bufferbloat since it can avoid full buffer and high queueing delay. However, none of existing AQM algorithms have been widely deployed so far due to complicated manual parameter tuning. Moreover, there is generally no single set of parameters that can guarantee an AQM to perform well in all possible network scenarios. Thus, it is desirable to automate parameter tuning for AQM, such that parameters can be configured automatically and properly based on network conditions. This requires a thorough understanding of the Internet congestion control mechanism formed by the Transmission Control Protocol (TCP) and AQM.

In this thesis, I systematically address the bufferbloat problem and propose two novel frameworks to achieve this goal. First, an adaptive delay control framework is proposed to combat bufferbloat in networks with a single bottleneck link. Controlled Delay (CoDel), a popular modern AQM with fixed parameter settings, is used as the basic AQM in the framework. I develop an analytical model for the TCP/CoDel system and derive necessary and sufficient conditions for its stability. Based on the derived stability conditions, two adaptive algorithms for CoDel are devised to automatically tune its parameters. Extensive simulation results demonstrate the effectiveness of the proposed algorithms on improving system performance and stabilizing the queueing delay in single-bottleneck networks.

Second, and more importantly, I propose a general framework to combat bufferbloat in networks with multiple bottleneck links. This is challenging since it is even unclear if there exists an equilibrium in a multi-bottleneck network. Thus, I conduct an equilibrium analysis for a general multi-bottleneck TCP/AQM system. Moreover, I derive sufficient conditions for the uniqueness of an equilibrium point and propose an algorithm to compute it. Then, the stability of the multi-bottleneck TCP/AQM system is studied using Lyapunov stability theory. In order to facilitate distributed algorithm design, I further decompose the multi-bottleneck system into single-bottleneck subsystems and derive sufficient conditions for the local asymptotic stability of the subsystems. The presented equilibrium and stability studies constitute a general framework for analyzing TCP/AQM systems with multiple bottleneck links. Utilizing the framework, I present a case study to analyze the stability of CoDel in multi-bottleneck networks and propose Self-tuning CoDel algorithm to improve the system stability. Extensive simulation results show that Self-tuning CoDel effectively stabilizes queueing delays at all the bottleneck links around small values, thereby significantly mitigating bufferbloat.