几种典型AQM算法在高速网络下的比较研究

苏聪

【摘要】 本文分析和比较几种典型的主动队列管理（Active Queue Management， AQM）算法在高速网络中的性能，经仿真实验发现这几种AQM算法在高速网络中的性能都不理想，主要表现为：链路的带宽利用率不高，全局同步现象严重，队列长度不能维持在一定值附近。这些现象说明了现有的AQM算法在高速网络下不能很好地满足QoS（quantity of serve）的要求，改进AQM算法势在必行。

【关键词】 AQM算法 NS仿真模拟

一、引言

当前针对高速网络的拥塞控制研究中，主要针对源端算法或基于反馈的机制而进行，在中间节点方面研究得较少。而对于源端算法来说，如果没有中间节点的支持，很难达到理想的性能。因此，有必要考察各种典型的AQM算法结合源端算法在高速网络下的性能。

二、算法的评价指标

目前，路由器中大多數是基于“弃尾”（Drop-Tail）的队列管理，RED[1]算法或RED的变种作为可选配置在路由器上，但常常不被使用。AQM的部署步伐之所以慢是由于缺乏对各种算法较为详细的、一致的客观评价标准，大多数AQM评价工作是为了新算法的有效性目的而进行的。通常对AQM算法性能的评价主要包括：

1、队列的稳定性：AQM的目的是控制路由器中的队列长度，因此算法稳定与否直接关系到路由器中队列长度的变化情况，而队列长度的变化又直接影响到网络的服务质量。一方面，对于一个特定的TCP连接，由于其传播延迟是固定的，因此该连接传输时延和时延抖动的大小主要是由路由器中的队列长度所决定的；另一方面，路由器中的队列长度直接关系到其输出链路的带宽利用率，只有当队列长度不为零时才能保证网络带宽的有效利用。因此一个好的AQM算法应能使队列长度稳定在一个较低的值附近。

2、高效的带宽利用率：队列长度不为零时可以保证路由器输出链路的带宽利用率，但输入链路的带宽利用率要靠丢包率来保证，对于一个特定的TCP连接，若丢包率过高，将会导致不必要的重传，从而降低带宽的利用率。因此，一个好的AQM算法应该既要保证队列长度的稳定性，又要保证高效的带宽利用率。

3、公平性：AQM的目标之一是改进Drop-Tail队列的公平性。REC2309强调：路由器的队列机制应保护适应流，对非适应流进行有效的鉴别和限制。

4、算法的复杂程度：算法的复杂程度是决定AQM算法是否实用的一个关键因素。近年来，随着网络带宽的迅速增加，路由器的处理速度成为影响网络性能的一个主要因素，因此应尽可能降低AQM算法的复杂程度以减小路由器的计算量。由于骨干路由器的负荷相当重，瓶颈链路非常繁忙，因此一个简单高效的拥塞检测方法以及丢弃策略对于算法的利用及有效推广是至关重要的。

5、对网络状态变化的适应能力：具有较强的鲁棒性，即对环境变化不敏感。Internet的复杂性和异构性决定了网络状态的变化是难以避免的，因此一个好的AQM算法应该对网络状态的变化具有很好的适应能力，在网络负载、传输时延等因素发生变化时，仍可实现好的传输性能。

下面，笔者将从带宽利用率、丢包率、队列长度的稳定性来考察几种典型的AQM算法在高速网络中的性能。

三、仿真实验环境

对于现有的AQM算法，可以归为三类，分别为：基于队列长度的AQM算法、基于瞬时队列长度和装载量的AQM算法和基于速率的AQM算法。这里，笔者选择典型的、具有代表性的RED、PI[2]、BLUE[3]和REM[4]算法和现行使用的Drop-Tail算法来进行考察。笔者在ns-2[5]平台上进行仿真，仿真的网络拓扑结构如图1所示，该环境中，有两个中间节点N1、N2，其相连的链路为瓶颈链路，带宽为1Gbps，时延为20ms。发送端和接收端各为4个节点，其中，S1到N1，R1到N2之间的链路带宽为1Gbps，时延为1ms， 其他节点到N1和N2的链路带宽均为1Gbps和2ms。瓶颈链路的缓冲区容量设为2500个数据包。每隔0.1s，S1、S2、S3、S4各发起一个HSTCP连接，这里需要说明的是，HSTCP是针对高速网络而设计的协议，正如前面所讨论，TCP协议在高速网络下性能非常差，而笔者仿真的目的是考察各种AQM算法在高速网络下的性能，因此不能使用TCP连接，而HSTCP在响应性、公平性、TCP友好性上都较为优秀，因此笔者的仿真实验选择HSTCP作为配合AQM的端算法。为了能引起拥塞，四个HSTCP连接的应用均为FTP，也就是说只要拥塞窗口允许就一直发送数据，且不考虑接收端的接收能力，只考虑网络传输能力，为了做到这点，笔者设置接收端的通告窗口为8000个数据包。同时，接收端采用每收到一个数据包就发回一个确认的机制。整个仿真过程为1000s，在瓶颈链路上，笔者分别使用Drop-Tail，RED，REM，PI及BLUE算法。其中，BLUE使用原算法的参数值，RED算法的minth，maxth分别设为瓶颈链路缓冲区的1/4和3/4，REM和PI控制器的期望队列长度设1000个数据包。

四、性能分析

对于PI控制器，计算丢包概率的公式为：

其中，q（k）是在k时刻的瞬时队列长度，q0为目标队列长度。参数a、b的取值跟链路容量、数据流的个数、时延有关，但是PI控制器本身不提供计算a、b的值，即在路由器执行PI时，不根据实时的网络状况调整a、b的值，一经设定，则固定不变。在这个模拟环境下，a的取值为：0.0000001822，b的取值为：0.0000001816，这个值在高速网络下不适用，导致了PI的带宽利用率没有达到理想的效果，如图2（b）所示。

REM算法適用于基于速率的拥塞控制，而本身不能提供与源端速率控制算法进行合作的机制，当与之相配合的是TCP拥塞控制机制或TCP的变种时，它将退化成一般的AQM算法。而且， REM算法其实是PI控制器的一个特例，其在高速网络中的带宽利用率同样没有达到理想的效果，如图2（c）所示。

BLUE算法在队列溢出时增加丢包概率，在队列为空时减小丢包概率。但是，队列溢出和队列为空是两个极端，并且，丢包概率的增减步长缺乏对环境的适应性，所以，在高速网络下，同样出现同步的问题，使得带宽利用率时高时低，如图2（e）所示。

从图2（d）可以很明显地看出Drop-Tail算法固有的问题：容易导致TCP连接的全局同步。

在笔者的模拟环境下，在N1节点分别使用RED、PI、REM、Drop-Tail和BLUE时，瓶颈链路的平均带宽利用率在表1给出，由表可以看出，这几种AQM算法的平均带宽利用率在75%左右，不是很高。

4.2 瓶颈节点丢包率的比较

队列长度不为零时可以保证路由器输出链路的带宽利用率，但输入链路的利用率要靠丢包率来保证，对于一个特定的TCP连接，若丢包率过高，将会导致不必要的重传，从而降低带宽的利用率。因此，一个好的AQM算法应该在保证带宽利用率的前提下，保证低的丢包率。笔者在N1节点分别使用RED，PI，REM，DROP-TAIL和BLUE算法，并统计N1节点的丢包率，结果如图3所示。

从丢包率的情况来看，RED、REM、DROP-TAIL和 BLUE都存在同步现象。而PI的丢包率则维持在一定的值附近，因为参数a、b不能根据网络环境而自适应地进行调整，在笔者的仿真环境下，拥塞控制过于激进，使得丢包率一直维持在0.001附近，造成了带宽利用率的降低。与带宽利用率相对应的是，丢包率增大，则利用率降低，如图3（a），与之对应的是图2（a），在16s时，丢包率为0.001149，相应的带宽利用率降为31%。

4.3 瓶颈节点队列长度的比较

AQM对队列长度的要求是：维持较小的队列长度，避免队列长度剧烈抖动，以减小排队时延。

笔者在N1节点分别使用RED，PI，REM，DROP-TAIL和BLUE算法，并统计N1节点的实时队列长度，结果如图4所示。从图4可以看出，PI不能很好地控制队列长度在所期望的值附近，而DROP-TAIL、RED和REM的队列长度剧烈抖动，表现出了明显的同步现象。

4.4不同带宽时平均利用率和平均队列长度的比较

图5是瓶颈链路的带宽从200M变化到1000M，在N1节点分别使用RED、PI、REM、DROP-TAIL和BLUE时，瓶颈链路的平均带宽利用率和N1节点的平均队列长度情况。从实验结果图来看，带宽越大，各种算法的平均利用率性能表现越差，同时，平均队列长度也很低，这虽然符合AQM的初衷（尽可能使队列长度很小），但这是以牺牲链路的带宽利用率为代价的。笔者评价一个AQM算法的好坏，要看它是否能在高的链路带宽利用率和低的队列长度之间做好平衡，RED、PI、REM、DROP-TAIL和BLUE在高速网络中，这点就没有做好。

五、结论

本文通过仿真实验，比较研究了RED、PI、REM、BLUE这几种典型的AQM算法和Drop-Tail在高速网络下的性能，发现这几种AQM算法的性能都不理想，链路利用率较低，并且全局同步的现象很严重。因此，设计新的或改进已有的AQM算法势在必行。

参 考 文 献

[1] Floyd， S. Jacobson， V. Random early detection gateways for congestion avoidance [J]. IEEE/ACM. Transactions on Networking， 1993， 1（4）： 397～413

[2] C Hollot， V Misra， D Towsley， W B Gong. On designing improved controllers for AQM routers supporting TCP flows [A]. In： IEEE INFOCOM 2001[C]. Anchorage， Alaska， 2001.1726～1734

[3] W Feng， D Kandlur， D Sah， K Shin. Blue： A new class of active queue management algorithm [R]. University of Michigan Technical Reports CSE-TR-387-99， April 1999

[4] Sanjeewa Athuraliya， Steven H Low， Victor H Li， Qinghe Yin. REM： Active queue management [J]. IEEE Network， 2001， 15（3）： 48～53

[5] S Mccannne， S Floyd. Ns-LBNL the network simulator [EB/OL]. http：//www.isi.edu/nsnam/ns.