ITR: Optimal Diffusion Mechanisms for Fast and Robust TCP Congestion Control

随机早期检测（RED）是在90年代早期引入的，它是第一个重要的主动队列管理（AQM），旨在与TCP共存——这一概念彻底改变了互联网的拥塞控制。尽管最近对RED提出了许多改进，如自适应RED、SRED、REM和BLUE，但所有这些AQM协议中固有的许多基本弱点都没有被克服，包括过度参数化、设计和实现的复杂性，以及缺乏对不同流量混合的鲁棒性。提出的研究重点是基于在信号处理中发现并广泛应用于该领域的最优误差扩散概念开发新一代主动拥塞控制机制。值得注意的是，数据包标记或丢弃机制与信号处理中的最优抖动和量化机制之间存在对偶性。更准确地说，（二进制）量化类似于数据包标记，其中用作RED输入的平均队列长度被量化为“开”（标记）或“关”（不标记）。然后将量化（标记）误差扩散到后续的量化（标记）操作中。最优量化或抖动是通过所谓的误差扩散滤波器实现的，当它应用于AQM问题时，会产生非常有效的拥塞控制机制，这里称为扩散早期标记（DEM）。与许多AQM系统不同，由于误差扩散达到了最优（伪随机）抖动，因此不需要随机变量生成，更重要的是，DEM只需要一个控制参数，该参数是基于对活动流量的估计或其他网络统计量来设计的。因此，所提出的方法依赖于跨层交互来提高AQM性能。例如，期望最大化（EM）算法和应用于ECN标记的其他更简单的统计方法承诺提供充分和稳健的拥塞估计。因此，DEM中的机制允许它在不同数量的流中保持稳定的平均队列长度。在DEM的设计与优化方面取得了初步成果。然而，在实施之前仍有许多悬而未决的问题需要解决，包括：(a)基于速率和队列长度的丢包机制的参数优化设计方法；(b)基于包头信息和/或队列动态的活动流和网络拥塞数量的快速鲁棒估计；(c)包括网络老鼠和大象在内的混合流量网络的扩散机制；(d) DEM差异化服务机制的开发。本研究的主要贡献在于将丰富的量化和鲁棒估计理论应用于基于跨层信息的新型鲁棒AQM机制的设计。新的空气质素监测机制，配合即将发展的估计架构，可望充分控制各种交通混合及不稳定交通动态的网络拥塞。提出的工作的一个重要方面是在实验和可扩展的测试平台上对具有真实流量的DEM路由器进行测试。这个测试平台的可用性将有助于学生更深入地理解网络的一些困难概念，如拥塞控制和主动队列管理，并使他们获得网络流量管理和控制方面的实际经验。

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.