Design and analysis of a self-tuning feedback controller for the Internet

Active queue management (AQM) is an effective method used in Internet routers for congestion avoidance, and to achieve a tradeoff between link utilization and delay. The de facto standard, the random early detection (RED) AQM scheme, and most of its variants use average queue length as a congestion indicator to trigger packet dropping. This paper proposes a novel packet dropping scheme, called self-tuning proportional and integral RED (SPI-RED), as an extension of RED. SPI-RED is based on a self-tuning proportional and Integral feedback controller, which considers not only the average queue length at the current time point, but also the past queue lengths during a round-trip time to smooth the impact caused by short-lived traffic dynamics. Furthermore, we give theoretical analysis of the system stability and give guidelines for selection of feedback gains for the TCP/RED system to stabilize the average queue length at a desirable level. The proposed method can also be applied to the other variants of RED. Extensive simulations have been conducted with ns2. The simulation results have demonstrated that the proposed SPI-RED algorithm outperforms the existing AQM schemes in terms of drop probability and stability.     

自相似业务下拥塞避免机制的实现

传统拥塞避免机制所采用的随机早期检测（Random Early Detection,RED）算法是建立在网络流量按Poisson分布的基础上,因此不适应具有自相似业务流量特征的Internet网。针对自相似业务流量特点,对RED算法进行了改进,提出了一种基于时间间隔的随机早期检测（Based Interval Random Early Detection,BIRED）算法。BIRED算法能够在自相似业务流量特征下,通过控制平均队列长度,避免网络进入拥塞状态。通过仿真比较了BIRED和RED的动态性能,显示了BIRED具有更好的鲁棒性,证明了BIRED比RED、DropTail更能适应自相似业务流量,减小系统负担,有效稳定平均队列长度,改善系统的暂态特性。     

RED算法的数学模型研究

RED算法能够及时预测网络拥塞的到来,并同过标记避免网络拥塞,同时还解决了TCP全局同步的问题.RED算法对参数过于敏感一直是研究的主要问题.建立RED算法的数学模型,从数学角度分析RED算法的原理以及工作过程.对数学模型的静态分析、参数分析研究各个参数在算法中所起的作用以及其影响因子;给出如何设定参数才能使RED算法达到更好的性能.     

A linear system analysis of RED

The random early detection (RED) algorithm proposed by Floyd and Jacobson [IEEE/ACM Trans. Networking 1 (4) (1993) 397] is a simple and quite effective mechanism for active queue management and as a result has been widely implemented in Internet routers. While RED certainly performs better than drop-tail, its parameters are difficult to tune to give good performance under different congestion scenarios. Also, studies have shown that RED does not stabilize the queue lengths in routers, because its equilibrium queue length strongly depends on the number of active TCP connections. As a result numerous variants of RED have been proposed to work around the performance problems of RED. In this paper, using inferences drawn from a linear systems analysis, we provide an insight into why RED is difficult to tune. The same linear systems analysis is used to show that the DRED algorithm proposed in [Computer 36 (2–3) (2001) 203; Comput. Commun. 24 (12) 2001 1170] overcomes the performance limitations of RED [IEEE/ACM Trans. Network. 1 (4) (1993) 397].     

一种改进的主动队列管理算法

主动队列管理是实现网络拥塞控制的重要技术,但是多数主动队列管理算法如随机早期检(RED)都存在对参数依赖性强的问题。针对RED算法中平均队列长度不能完全反映网络拥塞状况的问题,该文结合平均队列长度和网络的负载,提出一种改进的RED算法。该算法能根据网络负载的变化,自适应地调整丢包的概率,使它更符合网络的实际状况。通过仿真进行了性能分析,证明了算法的有效性。     

A novel self-tuning feedback controller for active queue management supporting TCP flows

Wireless access points act as bridges between wireless and wired networks. Since the actually available bandwidth in wireless networks is much smaller than that in wired networks, there is a bandwidth disparity in channel capacity which makes the access point a significant network congestion point. The recently proposed active queue management (AQM) is an effective method used in wired network and wired-wireless network routers for congestion control, and to achieve a tradeoff between channel utilization and delay. The de facto standard, the random early detection (RED) AQM scheme, and most of its variants use average queue length as a congestion indicator to trigger packet dropping. In this paper, we propose a Novel autonomous Proportional and Differential RED algorithm, called NPD-RED, as an extension of RED. NPD-RED is based on a self-tuning feedback proportional and differential controller, which not only considers the instantaneous queue length at the current time point, but also takes into consideration the ratio of the current differential error signal to the buffer size. Furthermore, we give theoretical analysis of the system stability and give guidelines for the selection of feedback gains for the TCP/RED system to stabilize the instantaneous queue length at a desirable level. Extensive simulations have been conducted with ns2. The simulation results have demonstrated that the proposed NPD-RED algorithm outperforms the existing AQM schemes in terms of average queue length, average throughput, and stability.     

基于RED的无线传感器网络的拥塞控制

拥塞控制问题是影响无线传感器网络性能的一个重要因素。针对无线传感器网络中的拥塞控制问题,提出了一种基于RED的拥塞避免策略。RED算法目前比较常用于路由器队列管理中,以实现对缓存空间队列长度的管理。将其引入到无线传感器网络中,采用拥塞度门限值作为拥塞调节的依据,以matlab软件作为仿真工具,通过建立简单网络拓扑结构进行模拟实验,综合比对各个实验参数下的不同实验结果,从而得到适当参数值下,较好的无线传感器网络传输性能。     

Reduction of queue oscillation in the next generation Internet routers

The Internet routers employing the random early detection (RED) algorithm for congestion control suffer from the problem of chaotic queue oscillation. It is well known that the slowly varying nature of the average queue size computed using an exponentially weighted moving average (EWMA) used in the RED scheme causes this chaotic behavior. This paper presents a new mathematical function to model the weighting parameter used in the EWMA. The proposed weighting function incorporates the knowledge of the dynamic changes in the congestion characteristics, traffic characteristics and queue normalization. Using this pragmatic information eliminates the slowly varying nature of the average queue size. It is evident from our simulations that the proposed approach not only reduces the chaotic queue oscillation significantly but also provides predictable low delay and low delay jitter with high throughput gain and reduced packet loss rate even under heavy load of traffic conditions.     

An interval-based congestion control algorithm under varying network conditions

A new IRED (interval random early detection) congestion control algorithm is proposed for network congestion avoidance and resource management. Different to the traditional AQM (active queue management) algorithms, the control parameters of IRED are not configured statically, and is setting as a parameter interval according to the changes of network environment. By the interval parameter design, the IRED alleviates the tuning difficulty of RED (random early detection) and shows a robust performance than RED under varying network conditions. It is proved that the stability and stability margin of the IRED control system can be guaranteed. A systematic design method for the configuration of parameter interval is proposed. Simulation studies show the proposed IRED algorithm achieves a robust control performance in varying network environment, which is superior to the RED and Gentle-RED algorithm.     

Bounds estimation and practical stability of AIMD/RED systems with time delays

The Additive Increase and Multiplicative Decrease (AIMD) congestion control algorithm of TCP deployed in the end systems and the Random Early Detection (RED) queue management scheme deployed in the intermediate systems contribute to Internet stability and integrity. Previous research based on the fluid-flow model analysis indicated that, with feedback delays, the TCP/RED system may not be asymptotically stable when the time delays or the bottleneck link capacity becomes large [3]. However, as long as the system operates near its desired equilibrium, small oscillations around the equilibrium are acceptable, and the network performance (in terms of efficiency, loss rate, and delay) is still satisfactory. In this paper, we study the practical stability of AIMD/RED system with feedback delays and with both homogeneous and heterogeneous flows. We obtain theoretical bounds of the flow window size and the RED queue length, as functions of the number of flows, link capacity, RED queue parameters, and AIMD parameters. Numerical results with Matlab and simulation results with NS-2 are given to validate the correctness and demonstrate the tightness of the derived bounds. The analytical and simulation results provide important insights on which system parameters contribute to higher system oscillations and how to set parameters (such as buffer size and queue management parameters) to ensure system efficiency with bounded delay and loss. Our results can also help to predict and control the system performance for Internet with higher data rate links multiplexed with heterogeneous flows with different parameters.     

Adaptive mechanism-based congestion control for networked systems

In order to assure the communication quality in network systems with heavy traffic and limited bandwidth, a new ATRED (adaptive thresholds random early detection) congestion control algorithm is proposed for the congestion avoidance and resource management of network systems. Different to the traditional AQM (active queue management) algorithms, the control parameters of ATRED are not configured statically, but dynamically adjusted by the adaptive mechanism. By integrating with the adaptive strategy, ATRED alleviates the tuning difficulty of RED (random early detection) and shows a better control on the queue management, and achieve a more robust performance than RED under varying network conditions. Furthermore, a dynamic transmission control protocol–AQM control system using ATRED controller is introduced for the systematic analysis. It is proved that the stability of the network system can be guaranteed when the adaptive mechanism is finely designed. Simulation studies show the proposed ATRED algorithm achieves a good performance in varying network environments, which is superior to the RED and Gentle-RED algorithm, and providing more reliable service under varying network conditions.     

Effective RED: An algorithm to improve RED's performance by reducing packet loss rate

Random early detection (RED) is an effective congestion control mechanism acting on the intermediate gateways. We describe a new active queue management scheme, Effective RED (ERED) that aims to reduce packet loss rates in a simple and scalable manner. We made a few change to packet drop function of existing RED scheme. The rest of the original RED remains unchanged. We achieve this by making several refinements and by controlling packet dropping function both with average queue size and instantaneous queue size. Simulations demonstrate that ERED achieves a highest throughput and lowest packet drops than RED, Blue, REM, FRED, LDC and SRED. Since ERED is fully compatible with RED, we can easily upgrade/replace the existing RED implementations by ERED.     

一种适用于无线通信网络的随机提前检测算法*

在无线通信网络环境下,提出了一种改进的基于平均队列长度和等待时间的随机提前检测算法.这种算法根据平均队列长度和等待时间计算数据包的丢弃概率.仿真结果表明,与单纯基于平均队列长度的RED算法相比较,在大的数据业务负荷条件下可以获得相对更大的吞吐量、更低的丢包率以及较低的时延抖动,从而能更有效地实现无线网络中的拥塞控制.     

基于RED分组丢失历史方法的非TCP流鉴别

随机早期检测(RED)是IETF推荐的一种基于路由器的有效的主动队列管理算法,但是在某些情况下,一些数据量很大的高带宽流量会大量占用带宽,从而导致了各流量之间带宽分配的不公平性,甚至产生拥塞崩溃。该文从RED的丢包历史出发,研究了一种在发生拥塞时鉴别出高带宽流量的方法,并通过仿真证实了此方法的有效性。     

基于路由器的随机早期检测算法的分析与优化

因特网的迅速发展使网络拥塞问题目益得到人们的重视,近年来提出了许多基于路由器的拥塞控制机制。本文详细分析了基于路由器的随机早期检测（RED）拥塞控制机制的设计思想、实现原理和优缺点。针对RED算法存在的缺陷提出了一种新的改进算法--SQRED算法,即当平均队列长度在最小和最大闲值之间时,使丢包概率采用一种平滑的增
长机制来代替线性增长。通过在Linux中使用NS-2设计网络仿真实验,对RED和SQ-RED算法的性能和实现进行了对比。仿真结果表明,SQ-RED算法能够获得更好的网络性能。     

非线性高阶RED拥塞控制算法

针对随机早期检测(RED)算法在网络拥塞不严重的时候丢包率相对较大,而在较严重的时候丢包率相对较小的问题,提出了一种非线性高阶RED拥塞控制算法,目的在于提高算法对网络拥塞的调节能力。该算法建立了一个高阶分组丢弃函数模型,在最小门限值附近丢包率缓慢增长,在最大门限值附近丢包率快速增长,有效地控制了平均队列长度。NS2仿真实验验证了改进算法可有效地提高网络性能。     

基于ARED的主动队列管理改进算法

随机早期检测（Random Early Detection,RED）是IETF推荐部署的主动队列管理（Active Queue Management,AQM）算法。 RED存在参数难以配置、无法适应动态网络环境的缺点。 ARED（ Adaptive RED）是RED的自适应版本,通过平均队列长度来动态调整最大丢弃概率,从而达到稳定平均队列长度的目的,但是存在瞬时队列长度振荡的问题。文中研究了拥塞控制中的主动队列管理,对ARED算法进行了改进,优化丢弃概率计算函数,提出TTS-ARED算法,实现在动态网络环境下队列长度的稳定以及丢包率降低。 NS2的仿真结果表明,TTS-ARED算法显著地降低了丢包率,队列长度稳定性比ARED算法更优越。     

路由器算法Droptail和RED的分析与优化

因特网的迅速发展使网络拥塞问题日益得到人们的重视,近年来提出了许多基于路由器的拥塞控制机制。文章详细分析了基于路由器的弃尾(Droptail)和随机早期检测RED(RandomEarlyDetection)拥塞控制机制的设计思想和算法实现。针对RED算法存在的不足对其进行改进,提出CRED(ConicRandomEarlyDetection)算法,该算法的基本思想是,当平均队列长度在最小和最大阈值之间时,使丢包概率采用一种平滑的增长机制。通过大量仿真实验对三种算法的性能进行对比研究,表明CRED算法在网络延迟、振荡等网络性能上比RED算法更有效。     

基于RED算法的改进研究

拥塞控制(congestion control)机制是确保Intemet QoS的关键因素,随机早期检测(Random Early Detection,RED)算法是提高网络服务质量、解决网络阻塞的重要算法.针对网关的到达队列来说,丢包率的算法采用RED基本思想中与平均队列长度呈线性的关系并不合适,提出了立方RED算法.算法对RED算法进行了改进,使流丢包率与平均队列长度呈立方函数关系,通过NS-2仿真软件研究表明.算法可以有效的增加了网关的吞吐量、减少丢包率.