几种主动式队列管理算法的比较研究

主动式队列管理(Active Queue Management,AQM)技术是IETF为了解决Internet拥塞控制问题而提出的一种路由器缓存管理技术.本文对几种主要AQM算法RED、BLUE、ARED和SRED的性能在基于ns-2仿真实验的基础上进行了比较研究.研究的性能包括队列长度、丢包概率、丢包率、连接数对吞吐量的影响及缓冲区大小对链路利用率的影响等.仿真结果表明BLUE、ARED和SRED在这几方面的性能都要优于RED算法.     

RED gateway congestion control using median queue size estimates

This paper focuses on the queue size estimation problem in random early detection (RED) gateways. Queue size estimation plays a fundamental role in the congestion control dynamics of RED, as it determines gateways' awareness of network congestion, which in turn determines the packet dropping/marking decision. Conventional RED gateways use exponentially weighted moving averages (EWMA) to estimate the queue size. These infinite impulse response (IIR) filters require very small EWMA weights in order to effectively avoid nonlinear instabilities in RED and to filter out bursty increases in the queue size. While small EWMA weights enable gateways to accommodate transient congestion, they also lead to gateways' failure to closely track rapid queue size depletion and thus causes link under utilization. We investigate the use of simple nonlinear queue size estimators. In particular, we study the congestion control dynamics of a network where adaptive weighted median filters are used for queue size estimation by the gateways. Analytical results for the expected queue size in the steady state are derived. Under this new queue size estimation framework, design guidelines for the remaining RED parameters are provided. Simulation results show that the proposed algorithm provides greater network power, better prevention of global synchronization, and a fairer treatment to bursty traffic than the RED algorithm does.     

Steady state and transient state behaviours analyses of TCP connections considering interactions between TCP connections and network

The Internet uses a window‐based congestion control mechanism in transmission control protocol (TCP). In the literature, there have been a great number of analytical studies on TCP. Most of those studies have focused on the statistical behaviour of TCP by assuming a constant packet loss probability in the network. However, the packet loss probability, in reality, changes according to the packet transmission rates from TCP connections. Conversely, the window size of a TCP connection is dependent on the packet loss probability in the network. In this paper, we explicitly model the interaction between the congestion control mechanism of TCP and the network as a feedback system. By using this model, we analyse the steady state and the transient state behaviours of TCP. We derive the throughput and the packet loss probability of TCP, and the number of packets queued in the bottleneck router. We then analyse the transient state behaviour using a control theoretic approach, showing the influence of the number of TCP connections and the propagation delay on the transient state behaviour of TCP. Copyright © 2005 John Wiley & Sons, Ltd.     

A comparison of active queue management algorithms using the OPNETModeler

A number of active queue management algorithms for TCP/IP networks such as random early detection (RED), stabilized RED (SRED), BLUE, and dynamic RED (DRED) have been proposed in the past few years. This article presents a comparative study of these algorithms using simulations. The evaluation is done using the OPNET Modeler, which provides a convenient and easy-to-use platform for simulating large-scale networks. The performance metrics used in the study are queue size, packet drop probability, and packet loss rate. The study shows that, among the four algorithms, SIZED and DRED are more effective at stabilizing the queue size and controlling the packet loss rate while maintaining high link utilization. The benefits of stabilized queues in a network are high resource utilization, bounded delays, more certain buffer provisioning, and,traffic-load-independent network performance in terms of traffic intensity and number of TCP connections     

动态权重RED网关

随着网络流量的增加,拥塞控制的重要性日益突出,尤其是链路拥塞控制。IETF推荐RED(Random Early Detection)作为下一代Internet路由器的拥塞控制算法。该文在分析了RED的优点和缺点后,在现在RED算法的基础上通过改进RED算法的平均队列长度计算,使用平均队列长度的均值,判断拥塞的发生和结束,动态调整权重,提高RED对拥塞发生和拥塞结束的反应速度,缩短拥塞时间,维持较低的实际队列长度。最后用仿真验证了该方法。     

一种参数自适应的主动队列管理算法-自适应BLUE

BLUE算法是一种典型的主动队列管理(Active Queue Management,AQM)算法,研究表明BLUE算法优于RED算法.BLUE算法使用丢包事件和链路空闲事件控制网络拥塞.但由于BLUE算法在参数设置方面存在不足,尤其是当TCP连接数突然剧烈变动时,容易导致队列溢出或空闲的频繁发生.该文引进参数自适应机制,提出了自适应BLUE算法,并借鉴了RED算法的早期拥塞检测机制.NS仿真实验表明该算法能有效保持队列长度的稳定,减少队列溢出或空闲现象的发生,在提高链路利用率的同时降低丢包率.     

数据流的活动队列管理算法:MBLUE

MBLUE(Modified BLUE)是一种面向数据流的活动队列管理算法.它不是使用平均队列长度指示缓冲区拥塞状态,而是使用数据报丢弃的频率和队列空闲程度来管理网络拥塞.探测瓶颈连接早期的拥塞信息,通过数据报的丢弃和标记避免拥塞.它只维护一个先进先出队列,以较少的数据流状态信息,在不同流之间公平的分配网络带宽.能够适应瞬时的猝发流,能合理控制非TCP数据流,又能够保持较短的平均队列长度,从而控制、减轻网络拥塞.通过TCP/IP网络的模拟,证实算法在公平的分配网络带宽和降低数据报的丢失率上具有较好的鲁棒性.     

A dynamic priority approach to reducing delay in interactive TCP connections

Many interactive applications require continuous user interaction, for example ssh and many web applications like online games. The TCP connections created by these applications are in a class called interactive. When interactive applications suffer from packet loss, packet retransmission time severely increases the user perceived delay. This work introduces a Dynamic Priority RED Queue (DPRQ) algorithm that dynamically changes the priority of queues instead of dropping packets when the interactive queue is overloaded. The algorithm reduces the user perceived delay by reducing packet loss in interactive TCP connections. The DPRQ is compared to an existing Class-Based Queue which incorporates RED (RCBQ) as would typically be used for Assured Forwarding. An analytical model of the DPRQ and RCBQ is presented with both experimental and analytical results. The DPRQ is found to decrease packet loss by up to eight times and therefore provide a lower user perceived delay even though queuing delay is increased by up to five times.     

修正开关泊松过程（RSPP）和RSPP／M／1排队

在通信网互连中，若被连子网具有不同的最大允许分组长度，那么有信关中一个较长的分组就可能要被拆分为多个较小的分组，这就是公组再分问题，已经证明，在某些情况下。再分后的公组流可以用一个修正的开关泊松过程来，本文ＲＳＰＰ和ＲＳＰＰ／Ｍ／１排队。文中推导出了ＲＳＰＰ到达间隔分布的表达式，并给出了平均到达率。文中还给出了队长分布，平均等候时间的表达式；信关输出流的特性对于全网的性能分析是必需的，因此本文着重     

Active queue management with flow proportional buffering

Most active queue management schemes maintain an average of the queue length which they use together with a number of queue thresholds to detect congestion. However, the setting of the queue thresholds is problematic because the required buffer size for good sharing among TCP connections is dependent on the number of TCP connections using the buffer. This paper describes an improved active queue management scheme which dynamically changes its threshold settings as the number of connections and system load changes. This technique allows network devices to effectively control packet losses and TCP timeouts while maintaining high link utilization. Copyright © 2003 John Wiley &Sons, Ltd.     

一种基于速率和队列长度的主动队列管理机制

本文研究了拥塞产生的原因及其表现形式,提出了一种基于报文到达速率和队列长度的随机早丢弃算法(RQ).根据拥塞的严重程度和变化趋势将拥塞划分为六个级别,每个级别采用合适的丢弃概率,从而将队列控制在理想工作点附近.利用经典控制理论,分析了系统的稳定性,给出了参数配置的原则.最后,用NS网络仿真器对算法性能进行了验证.     

FRED-fair random early detection algorithm for TCP over ATMnetworks

The authors present the FRED (fair random early detection) algorithm as a congestion control mechanism for TCP over ATM networks. The FRED algorithm enhances the RED gateway algorithm, by using the fact that TCP connections should be allocated buffer space in proportion to their bandwidth-delay products. Through simulation, the effectiveness of the proposed FRED algorithm is shown as compared with the drop-tail and the original RED algorithms     

DRED: a random early detection algorithm for TCP/IP networks

It is now widely accepted that a RED [2] controlled queue certainly performs better than a drop‐tail queue. But an inherent weakness of RED is that its equilibrium queue length cannot be maintained at a preset value independent of the number of TCP active connections. In addition, RED's optimal parameter setting is largely correlated with the number of connections, the round‐trip time, the buffer space, etc. In light of these observations, we propose DRED, a novel algorithm which uses the basic ideas of feedback control to randomly discard packets with a load‐dependent probability when a buffer in a router gets congested. Over a wide range of load levels, DRED is able to stabilize a router queue occupancy at a level independent of the number of active TCP connections. The benefits of stabilized queues in a network are high resources utilization, predictable maximum delays, more certain buffer provisioning, and traffic‐load‐independent network performance in terms of traffic intensity and number of connections. Copyright © 2002 John Wiley & Sons, Ltd.     

主动队列管理中的智能分组丢弃新机制

主动队列管理通过网络中间节点有控制的分组丢弃实现了较低的排队延时和较高的有效吞吐量,是TCP端到端拥塞控制近来研究的一个技术热点.已有的大多数算法在判定分组丢弃时大都沿袭了RED的概率丢弃机制,具有一定计算复杂度的随机数生成过程不利于路由器性能的优化.在本文中,我们首先定义了拥塞指数这一新的测度变量来量化描述网络的拥塞状态.接着,利用模糊逻辑设计了一种新的智能分组丢弃机制,离线的合成推理使得分组丢弃的判定仅需要简单的查表操作和比较运算即可完成,为优化路由器的性能提供了便利.数字仿真的结果表明:智能分组丢弃机制的性能优于经典的RED算法,控制队列的能力强,鲁棒性好,稳定工作域大,能很好地抵抗突发性和非弹性业务的干扰,适合工作在瞬息万变的动态网络环境中.     

PAQM: an adaptive and proactive queue management for end‐to‐end TCP congestion control

Two functions, the congestion indicator (i.e. how to detect congestion) and the congestion control function (i.e. how to avoid and control congestion), are used at a router to support end‐to‐end congestion control in the Internet. Random early detection (RED) (IEEE/ACM Trans. Networking 1993; 1 (4):397–413) enhanced the two functions by introducing queue length averaging and probabilistic early packet dropping. In particular, RED uses an exponentially weighted moving average (EWMA) queue length not only to detect incipient congestion but also to smooth the bursty incoming traffic and its resulting transient congestion. Following RED, many active queue management (AQM)‐based extensions have been proposed. However, many AQM proposals have shown severe problems with detection and control of the incipient congestion adaptively to the dynamically changing network situations. In this paper, we introduce and analyse a feedback control model of TCP/AQM dynamics. Then, we propose the Pro‐active Queue Management (PAQM) mechanism, which is able to provide proactive congestion avoidance and control using an adaptive congestion indicator and a control function under a wide range of traffic environments. The PAQM stabilizes the queue length around the desired level while giving smooth and low packet loss rates and high network resource utilization. Copyright © 2004 John Wiley & Sons, Ltd.     

The impact of multihop wireless channel on TCP performance

This paper studies TCP performance in a stationary multihop wireless network using IEEE 802.11 for channel access control. We first show that, given a specific network topology and flow patterns, there exists an optimal window size W* at which TCP achieves the highest throughput via maximum spatial reuse of the shared wireless channel. However, TCP grows its window size much larger than W* leading to throughput reduction. We then explain the TCP throughput decrease using our observations and analysis of the packet loss in an overloaded multihop wireless network. We find out that the network overload is typically first signified by packet drops due to wireless link-layer contention, rather than buffer overflow-induced losses observed in the wired Internet. As the offered load increases, the probability of packet drops due to link contention also increases, and eventually saturates. Unfortunately the link-layer drop probability is insufficient to keep the TCP window size around W'*. We model and analyze the link contention behavior, based on which we propose link RED that fine-tunes the link-layer packet dropping probability to stabilize the TCP window size around W*. We further devise adaptive pacing to better coordinate channel access along the packet forwarding path. Our simulations demonstrate 5 to 30 percent improvement of TCP throughput using the proposed two techniques.     

TCP SkyLine:数据中心网络高吞吐率传输

针对数据中心网络在"多对一"并发流量模式下,TCP（Transmission Control Protocol）及其现有改进方案在单轮数据传输和多轮数据传输下吞吐率低下问题,提出了一种通过数据包标记实现丢包快速发现和快速重传并动态调整拥塞窗口初始值的策略,称为TSL（TCP SkyLine）.TSL同时解决了传统TCP Incast问题和多轮数据传输下由遗留窗口引发的TCP Incast问题.实验表明,TSL在单轮数据传输和多轮数据传输下均能获得90%以上的带宽利用率.在10Gbps网络中,其支持的并发连接数与传统TCP和DCTCP相比分别提升了5倍和1倍,有效吞吐率分别提升了18倍和8.6倍;在1Gbps网路中,支持的并发连接数较传统TCP和DCTCP分别提升了5.8倍和1倍.     

A novel congestion control protocol with AQM support for IP-based networks

Multimedia services (Real-time and Non real-time) have different demands, including the need for high bandwidth and low delay, jitter and loss. TCP is a dominant protocol on the Internet. In order to have the best performance in TCP, the congestion window size must be set according to some parameters, since the TCP source is not aware of the window size. TCP emphasizes more on reliability than timeliness, so TCP is not suitable for real-time traffic. In this paper an active Queue management support TCP (QTCP) model is presented. Source rate is regulated based on the feedback which is received from intermediate routers. Furthermore, in order to satisfy the requirements of multimedia applications, a new Optimization Based active Queue management (OBQ) mechanism has been developed. OBQ calculates packet loss probabilities based on the queue length, packets priority and delay in routers and the results are sent to source, which can then regulate its sending rate. Simulation results indicate that the QTCP reduces packet loss and buffer size in intermediate nodes, improves network throughput and reduces delay.     

TCP-friendly flow control of wireless multimedia using ECN marking

In a wireless network packet losses can be caused not only by network congestion but also by unreliable error-prone wireless links. Therefore, flow control schemes which use packet loss as a congestion measure cannot be directly applicable to a wireless network because there is no way to distinguish congestion losses from wireless losses. In this paper, we extend the so-called TCP-friendly flow control scheme, which was originally developed for the flow control of multimedia flows in a wired IP network environment, to a wireless environment. The main idea behind our scheme is that by using explicit congestion notification (ECN) marking in conjunction with random early detection (RED) queue management scheme intelligently, it is possible that not only the degree of network congestion is notified to multimedia sources explicitly in the form of ECN-marked packet probability but also wireless losses are hidden from multimedia sources. We calculate TCP-friendly rate based on ECN-marked packet probability instead of packet loss probability, thereby effectively eliminating the effect of wireless losses in flow control and thus preventing throughput degradation of multimedia flows travelling through wireless links. In addition, we refine the well-known TCP throughput model which establishes TCP-friendliness of multimedia flows in a way that the refined model provides more accurate throughput estimate of a TCP flow particularly when the number of TCP flows sharing a bottleneck link increases. Through extensive simulations, we show that the proposed scheme indeed improves the quality of the delivered video significantly while maintaining TCP-friendliness in a wireless environment for the case of wireless MPEG-4 video.     

A study of deploying smooth‐ and responsive‐TCPs with different queue management schemes

While there exist extensive research works on congestion control and active queue management, or the joint dynamics of a congestion control strategy with the random early detection (RED) algorithm, little has been done on the interactions between different window adjustment strategies and different queue management schemes such as DropTail and RED. In this paper, we consider a spectrum of TCP‐friendly additive increase and multiplicative decrease (AIMD) parameters. At the one end of this spectrum, smooth‐TCP enhances smoothness for multimedia applications by reducing the window decrease ratio upon congestion, at the cost of the additive increase speed and the responsiveness to available bandwidth. At the other end, responsive‐TCP enhances the responsiveness by increasing the additive increase speed, at the cost of smoothness. We investigate the network dynamics with various combinations of AIMD parameters and queue management schemes, under different metrics. The investigation is conducted from the deployment (especially incremental deployment) point of view. We discussed the impact of the interactions on the goodput, fairness, end‐to‐end delay, and its implications to energy consumption on mobile hosts. Copyright © 2008 John Wiley & Sons, Ltd.