Random Early Detection (RED), introduced in the early 90's emerged as the first significant Active Queue Management (AQM) designed to coexist with TCP - a concept that revolutionized congestion control of the Internet. Although numerous improvements on RED have been proposed recently, such as Adaptive RED, SRED, REM, and BLUE, many of the fundamental weaknesses inherent in all of these AQM protocols have not been overcome, including over-parameterization, design and implementation complexity, and the lack of robustness to varying traffic mixtures.
The proposed research focuses on developing a new generation of active congestion control mechanisms based on the concept of optimal error diffusion discovered in signal processing and extensively used today in this field. Notably a duality exists between the mechanisms in packet marking or dropping with that of optimal dithering and quantization in signal processing. More precisely, (binary) quantization is analogous to packet marking where the average queue length, used as the input to RED, is quantized to "on" (marking) or "off" (no marking). The quantization (marking) error is then diffused over to subsequent quantization (marking) operations. Optimal quantization or dithering is attained with the so-called error diffusion filter, which, when applied to the AQM problem leads to remarkably efficient congestion control mechanisms coined here as Diffusion Early Marking (DEM). Unlike many AQM systems, random variable generation is not required as error diffusion attains optimal (pseudo-random) dithering, and more importantly DEM only requires a single control parameter which is designed based on the estimation of active flows or on other network statistics measuring congestion. As such, the proposed methods rely on cross level interactions for improved AQM performance. Expectation maximization (EM) algorithms and other simpler statistical methods applied on ECN markings, for instance, promise to provide adequate and robust estimates of congestion.
The mechanisms in DEM thus allow it to maintain a stable average queue length with a varying number of flows. Preliminary results on the design and optimization of DEM are remarkably promising. There are however, numerous open problems that need to be addressed prior to its implementation including: (a) methods for the optimal design of parameters controlling rate and queue-length based packet drop mechanisms, (b) fast and robust estimation of the number of active flows and network congestion based on packet header information and/or queue dynamics, (c) diffusion mechanisms for networks with mixed traffic including web mice and elephants, (d) development of DEM differentiated service mechanisms.
The major contribution of the proposed research is on the application of the rich theories of quantization and robust estimation to the design of novel and robust AQM mechanisms that rely on cross-layer information. The new AQM mechanisms, in concert with the estimation framework to be developed, promise to adequately control the congestion of networks with various traffic mixtures and non-stationary traffic dynamics.
An important aspect of the proposed work is the testing of DEM routers with real traffic in an experimental and scalable testbed. The availability of this testbed will be valuable in providing students with a deeper understanding of difficult network concepts, such as congestion control and active queue management, and allowing then to gain hands-on experience in network traffic management and control.
