N次随机丢包的被动队列管理算法

王文涛, 郭 峰, 王奇枫, 郑 芳, 唐 菀

(中南民族大学 计算机科学学院，武汉 430074)

拥塞产生的本质原因是网络资源无法合理分配以满足通信需求.当通信子网负荷比较小时,网络的吞吐量随着网络负荷的增加而线性增加.当网络负荷增加到某一值后,网络吞吐量反而下降,则表征网络中出现了拥塞现象.当拥塞比较严重时,传输能力和节点缓冲器大多用来重传,从而使通信子网的有效吞吐量下降，引起恶性循环,进而使通信子网处于局部死锁状态,最终导致网络有效吞吐量接近于零.

拥塞控制分为两部分：1)中间路由节点拥塞控制；2)边缘终端节点拥塞控制，即TCP拥塞控制.

目前主要队列管理机制分为主动队列和被动队列,IEFT推荐RED为主动队列管理机制.主动队列(以随机早检测RED为典型算法)需要消耗更多运算资源，并且参数设置没有合理的解决方案，部分缓存没有得到合理利用，并没有在实际网络上使用.文献[1]指出随机早检测算法在现实网络中的性能并不是最优的，因为其算法复杂导致处理速度下降，没有在实际网络上使用[2].虽然后续研究提出改进的CR模型丢弃策略[3]，但并不适用.被动队列是在队列满之后丢包，充分利用缓存，目前网络中队列管理采用这种机制，其优点是实现比较简单，但是存在死锁、全局同步等问题.

边缘终端节点拥塞控制通过TCP协议实现.通过“和式增加”、“积式减少”，对“慢启动”、“拥塞避免”、“快重传”、“快恢复”4个算法设置参数来实现不同的TCP拥塞控制[4].鉴于AQM的复杂性，以及PQM机制的不足[5],本文在中间节点拥塞控制方面做了相关研究，提出了N次随机丢包队列管理机制.

1 队列管理机制分析

1.1 AQM

主动队列管理(Active Queue Management, AQM)是队列管理策略之一，可以有效解决“全局同步”问题.但是AQM存在参数设置敏感的缺陷，在不同的网络状况很难保持其性能[6].为了维持队列长度稳定、减少排队时延并降低丢包率，主动队列管理总是提前丢包，同样会导致中间节点的传输效率下降.可见主动队列管理是牺牲部分网络传输效率来获得低时延、队列长度稳定等性能[7].

RED是比较经典的主动队列管理算法之一[8]，基本思想就是在拥塞发生的早期，动态计算当前队列的平均队列长度.当新分组到达的时候，根据当前平均队列长度计算出分组丢弃概率p.在RED引入两个门限参数m_min,m_max,当前平均队列长度小于m_min,新来的数据包进入队列，当前平均队列长度∈(m_min,m_max)，则根据概率p丢弃，当前平均队列长度大于m_max，到达分组直接丢弃，式(1)为丢弃概率计算函数，式(2)为平均队列长度计算公式.队列允许最大缓冲长度为Q_limit.Q_min,Q_max的计算公式如式(3)、(4)，两个比例因子(0.4,0.8)、Pmax、w权值根据网络情况确定[8].Q_avg平均队列长度计算公式引入了w权值，是为了缓冲网络抖动的影响，w一般取值为0.002左右，也就是反应了队列长期的变化趋势，短期的数据流并不会影响平均队列长度大幅波动.

(1)

qN=(1-w)×qN-1+q_now.

(2)

Qmin=0.4×Q_limit.

(3)

Qmax=0.8×Q_limit.

(4)

1.2 PQM

被动队列管理(PQM)是当前网络中广泛使用的队列管理机制，其设计和实现比较简单，而且对缓存利用率比较高.网络中最常用的是弃尾队列(DropTail)[9],也就是当网络中缓冲区数据溢出的时候，丢弃到达的分组.

1.2.1 弃尾队列

弃尾队列(DropTail)是在队列满之后，所有到达的分组直接被丢弃，直到队列有空余位置才吸收数据包.根据Jacobson对拥塞的研究发现，这种方式有如下3种严重的缺陷：

(1)全局同步现象.当网络中大量数据通信时，导致网络拥塞，所有后面到达的分组会被全部丢弃，所有发送节点都会检测到重传超时，发送端减小发送窗口，进入慢启动或者拥塞避免.网络空闲之后，所有发送节点再次增大发送速率，再次导致拥塞，重复上述情形，浪费了很多网络资源.

(2)死锁.少数TTL比较大的链接持续占用网络资源，其他链接得不到足够的网络资源.

(3)队列持续满状态.当网络发生拥塞的时候，队列一直保持满状态，增加了排队延迟.对于满队列造成的排队时延，文献[10]提出给队列设定一个阈值，当队列长度超过阈值之后，就开始随机丢弃数据包，但是这个阈值的设定需要根据网络情况，而且会造成硬件资源的浪费，对于突发数据流仍然无能为力.

1.2.2 弃首队列

弃首队列(DropFront),就是当缓冲队列满时，丢弃队列首部的数据包，然后新数据包进入队列.弃首队列可以减少排队时延，新来的数据包都能进入队列，死锁问题得到解决.但是当数据量比较大的时候仍然不能解决全局同步问题，以及队列满问题.

1.2.3 随机丢弃队列

随机丢弃队列(DropRand)，当缓冲队列满的时候，随机从队列中丢弃一个数据包，然后新到达的数据包进入队列.由于随机性，所以可以解决全局同步问题，以及死锁问题，但是队列持续满状态无法得到快速解决.丢弃一次对于整个队列的影响速度比较慢.

1.2.4 两次随机丢包队列管理算法

两次随机丢包队列管理算法(DropRand2),当缓冲队列满的时候，随机丢两次数据包.在一定程度上比一次随机丢弃队列DropRand丢包效率要好，也就是加快了对拥塞的响应.对于弃尾队列满造成的排队时延，被动队列管理解决办法之一就是如文献[10]所述人为地缩短中间节点缓冲区长度，减少排队时延.文献[11]指出，RTT 小的 TCP 数据流的拥塞窗口的增长速度会快于RTT大的TCP数据流，从而占有较多的网络带宽，造成RTT不公平性问题.弃尾队列管理存在速度不公平性，这点鲜见文献报道.所谓速度不公平性就是连接同样中间结点的链路，如果链路的速度不同则其发送的有效数据包差别很大，这并不是指链路速度快的发送端发送的有效数据包多，与其相反，仿真表明中间结点采用弃尾队列管理时，链路速度快的发送端发送的有效数据包要少于链路速度慢的发送端发送的有效数据包，而且链路速度差异越大，前者发送的有效数据包就越少.

两次随机丢包的队列管理策略在一定程度上能改善RTT的不公平性，丢包两次主要是因为：

(1)队列满时，说明拥塞比较严重，因此只丢弃1个数据包是不够的；

(2)如果一个 TCP 链接在队列中的数据包个数为n个，队列最大长度为Q个数据包，则该 TCP链接第1次被丢包的概率为n/Q，第2次被丢包的概率为(n-1)/(Q-1)或为n/(Q-1)，因此对占据队列较多的TCP链接有更好的惩罚作用，改善了公平性.

两次随机丢包的被动队列管理的具体算法如下[11]：

1) 有新的数据包要进入队列，如果q

2) 有新的数据包要进入队列，如果q≥Q-1，则计算一个[1,Q-1]之间的随机值，丢弃该值位置的数据包，再次计算一个[1,Q-2]之间的随机值，丢弃该值位置的数据包，新的数据包进入到队列.

其中Q表示最大队列长度，q表示当前队列长度.

2 DropRandN

文献[12]提出了N次弃头的被动队列管理算法，相对于一次弃头，算法优化了许多.文献[11]提出了两次随机丢包算法，丢包次数是2次. 两次随机丢包能够在一定程度上解决网络拥塞的3个问题.一次随机丢弃能够缓解网络拥塞，两次效果又增进一步.可见丢弃次数与缓解网络拥塞存在密不可分的关系.

2.1 N次随机丢弃算法

基于以上思考，提出了N次随机丢包的被动队列管理算法.该算法是在缓冲队列满之后才开始丢弃数据包，所以属于被动队列管理算法.它有如下优点：

缓冲队列满之后，表明当前网络拥塞比较严重，那么随机丢弃一次、两次对于缓解拥塞来说太少.N次随机丢包能够更快地响应网络拥塞，迅速地应对、处理拥塞.从概率上来讲，N次对于占据队列较多的发送端有较好的惩罚作用.

全局同步发生之后，所有发送节点同时减小拥塞窗口，所有节点发送速率下降.网络此时会有部分空闲，但是发现空闲之后所有节点同时增大，再次导致网络拥塞.这样来回地争夺带宽导致了带宽利用率的下降.N次随机丢弃算法能够以一定的数目随机丢弃数据包，随机程度比两次随机丢包要高，对网络拥塞节点惩罚力度更大.能够更加有效地打破全局同步的僵局.N次的选取借鉴黄金分割点比例0.618∶0.382,0.382接近1/3，故采用N/3.资源发生死锁是因为部分节点因发送速度差异或者链路状况差异，占据了大部分带宽，其他节点发送速率严重下降.主要体现为速度不公平和链路RTT时延不公平.采用N次随机丢弃能够以更高的概率惩罚占据大量带宽资源的节点，相对于两次随机丢包而言能够更好地保证带宽资源的公平性.

N次随机丢包具体算法如下.

Qmax表示缓冲队列长度，Qcurrent表示当前队列长度，N为与当前节点通信的其他节点数目.

触发事件：新数据包到达.

1)如果Qcurrent

2)如果Qcurrent>Qmax-1,缓冲区已满，无法直接接纳更多数据包，根据N值决定丢弃数量Ndrop=N/3,如果Ndrop<3 ,Ndrop=3至少丢3次.

3)根据Ndrop值采用N次随机丢弃算法丢弃数据包.

2.2 改进的随机丢弃策略

//一般的随机丢弃策略

1: for i<-0 to N do

2: length<-_q->length

3: j<-random(length)

4: while(j--) do

5: _q->next

6: end while

7: drop(_q->current)

8: end for

//改进的随机丢弃策略

1: for i<-0 to N do

2:rand_pos[i]<-random(_q->length)

3: end for

4: k<-0

5: while(j <= _q->length) do

6: j++

7: if(j=rand_pos[k])

8: drop(_q->current)

9: end if

10: _q->next

11: end while

一般的随机N次丢弃算法，其思想就是每一轮扫描，随机丢弃N个数据包，N=n/3,每次扫描长度为n, 两层循环遍历队列，时间复杂度T(n)=O(n2).

改进的随机N次丢弃算法，首先计算好N次随机丢弃的位置，然后在扫描的时候通过和预定义丢弃位置对比，决定是否丢弃当前数据包.改进的随机N次丢弃算法只需要随机生成丢包位置N次，以及遍历一轮队列n次，N=n/3为常数，所以时间复杂度T(n)=O(n).这样就可以大大降低N次随机丢包的复杂性，而且只需要一个随机算法以及遍历操作，并不像文献[11]中所说的增加了硬件开销.

3 DropRandN性能分析

3.1 网络拓扑结构

以下实验仿真工具使用NS2,采用与文献[13]类似的仿真方案.网络拓扑结构采用经典哑铃模型，本实验采用动态节点配置,仿真节点数目可根据脚本动态设置，初始节点数目为20.关键链路位于R0和R1之间，带宽10Mbit/s,时延10ms.其他节点与R0,R1链路之间带宽20Mbit/s,延时10ms,所有Sender(i)节点向Receiver(i)节点发送数据，具体参见文献[12].路由协议采用TCPNewreno，所有数据包大小为1000Byte.

3.2 全局同步问题

由于发送节点众多，所以随机抽取3个发送节点，来分析全局同步问题.R0和R1之间分别采用弃尾、两次随机丢包、N次随机丢包来观察拥塞窗口的变化情况，见图1.

图1 拥塞窗口变化Fig.1 The variation of congestion window

图1(a)中，发送节点Sender20个，接收节点Receiver20个，R0和R1之间采用弃尾队列，由于发送节点较多，所以只用其中3个节点观察拥塞窗口变化情况.图1(b)采用两次随机丢弃队列管理，图1(c)采用N次随机丢包队列管理.可以看出，图1(a)出现全局同步现象，而且3个节点拥塞窗口同步现象十分严重.图1(b)，1(c)采用随机策略，随机使得各个发送节点发现拥塞的时机不一致，从而避免全局同步现象的发生.图1(c)和图1(b)相比，3个节点拥塞窗口变化幅度有所减小，因为当网络发生拥塞的时候，N次随机丢弃能够更快地处理拥塞情况，幅度的减小也说明N次随机丢包能够使网络中各个节点拥塞窗口变化更加平缓，这样有利于提高网络带宽的利用率.

3.3 网络资源死锁问题(RTT，速度不公平)

RFC2309指出死锁经常会出现部分链路占据大部分带宽的现象.

在弃尾队列中，发送速率是造成死锁的因素之一，速率快的节点会比速率慢的节点先发现网络的拥塞，发送窗口开始减少，速率下降，而速率慢的节点速率下降得慢，占据大部分带宽.

对文献[12]中拓扑结构作如下调整,R0,R1 带宽为0.5Mbit/s,Sender0,Sender1与R0之间20Mbit/s,Sender2为速度最快链路80Mbit/s，然后分别使用DropTail,DropRand2,DropRandN.由图2可以看出，图2(a)DropTail弃尾队列速率最快的节点拥塞窗口最小，也就是一直处于低速率发送状态，始终处于不公平状态.这是因为速率快的节点频繁呈现拥塞避免，导致发送速率较低；图2(b)采用两次随机丢包策略，能够解决这种速率上的不公平；随机N次丢包算法拥塞窗口中(图2(c))，拥塞过程数目比图2(b)要多，也就是图中尖角.这是因为随机N次丢包一次丢弃了大量节点，短时间内不会出现频繁的拥塞，所以能够更快速地缓解拥塞.

图2 3种算法对于拥塞窗口的变化Fig.2 Three algorithm responding to the variation of cwnd

拥有不同RTT时延的链路也会产生网络资源死锁问题，少部分链路占用大部分带宽.RTT时间比较短的链路能够尽早地检测到网络拥塞，开始TCP拥塞避免，而RTT较长的链路此时可能还未发现网络拥塞，速率没有下降，所以RTT大的链路也会占据大部分带宽.对文献[12]中拓扑结构作如下调整,最后一个节点延时20ms，是其他普通链路的两倍，R0与R1之间链路速度为0.5Mbit/s，为了让网络更加拥塞，20个节点同时发送数据.图3(a)弃尾队列可以看出节点node3拥塞窗口一直很大，比另外2个节点拥塞窗口都大.由于20个节点绘图分析太多，所以随机抽取2个普通节点和最后一个RTT大的节点.经分析得知，由于R0和R1之间采用了弃尾队列，RTT大的node3节点短时间内未检测到拥塞，其他节点已经开始拥塞避免，拥塞窗口开始减小，节点node3未减小拥塞窗口，占据大部分带宽.其他节点只能分得很小的一部分.文献[11]中随机丢2次也能很好地解决死锁问题，图3(b)随机两次丢弃算法拥塞窗口没有出现死锁现象.

N次随机丢弃算法，由于丢弃的随机性，能很好地解决死锁问题，同时丢弃数目的增加能够对RTT较长有更好的惩罚作用.多个节点之间拥塞窗口比较接近，这也表明更多的随机次数能够有效打破死锁僵局，图3(c)各个节点拥塞窗口变化没有出现全局同步，同时也没有出现部分节点占据大部分带宽，而且相对于两次随机丢包而言，节点拥塞窗口分布更加均匀，能够更好地利用带宽资源.

图3 不同算法在不同RTT下拥塞窗口变化Fig.3 Cwnd of different algorithms responding to different RTT

3.4 持续满

队列满后, 后来的数据包全被丢弃, 不能吸收突发的数据流,但是这是在采用弃尾策略时考虑的问题.队列满主要影响是使后来的数据无法进入队列而被丢弃.

随机丢弃策略就可以解决这个问题, 在队列满时随机丢弃数据包, 后来的数据包都能够进入队列, 就能够吸收突发的数据流.两次随机丢弃每次可以空出2个位置来吸纳突发数据包.但是两次随机丢包空余出来的容量有限，如果数据流持续拥塞，那么会频繁丢包.N次随机丢包可以较好地解决队列抖动问题，当队列满时丢弃N个数据包，队列有较大空余容量吸收更多数据包，拥塞次数大大减少，这点从图2(c)和图3(c)可以看出.

3.5 传输效率

文献[12]的网络拓扑中，分别采用RED, DropTail, DropRand1, DropRand2,DropRandN,设置发送节点个数为4,8,10,12,20,40,接收节点个数与发送节点个数相同.统计100s内关键链路R0到R1之间的有效包个数如表1.发送节点Sender对应Ndrop分别为 3，3，3，4，6，13[11].DropRandN传输效率分别比DropTail,RED,DropRand1,DropRand2高出91%,2.6%,1.2%,0.8%.

4 结论

被动队列的改进主要集中在随机以及弃首两个方面，与主动队列相比，被动队列算法比较简单，容易实现，对硬件资源要求也少.主动队列算法尽可能地利用中间节点的运算能力来提高改善拥塞状况.但是事实上中间节点运算能力并不强，反而加剧拥塞程度；同时基于当前两次随机丢弃次数进行了改进，改进的丢弃策略提高了其性能，提出了N次随机丢弃被动队列管理算法DropRandN.N次丢弃能够对占据网络带宽的链路有更好的惩罚作用，在低速率以及高RTT时延的链路发挥更好的作用.仿真结果表明：该算法能够很好地处理全局同步、死锁、队列持续满3个主要问题，其设计简单、效率高，容易在现有物理网络基础上更新.

N次丢弃对于当前拥塞程度判断不是很准确，这是下一步需要研究的；同时N次也需要改进，因此后续工作是结合文献[14]研究出相关关系之后，设计出自适应随机丢包算法，再次提高网络传输的性能.

参 考 文 献

[1] Tahiliani M P, Shet K C.Analysis of cautious adaptive red (cared)[C]// IEEE. Advances in Computing, Communications and Informatics (ICACCI), 2013 International Conference on IEEE. Mysore: ICACCI, 2013: 1029-1034.

[2] Raghuvanshi D M, Tahiliani M P. On the effectiveness of CoDel for active queue management[C]// IEEE.Advanced Computing and Communication Technologies (ACCT), 2013 Third International Conference on IEEE. Rohtak: ACCT,2013: 107-114.

[3] Kong Zhizhou, Cai Zixing, Chen Yulin.A packet dropping strategy based on C-R model[C]// IEEE.Intelligent Information Technology Application. Third International Symposium on IEEE. Nanchang: IITA,2009: 437-440.

[4] 王宏伟.TCP/IP网络拥塞控制中主动队列管理算法研究[D].沈阳：东北大学,2008.

[5] May M, Bolot J, Diot C, et al.Reasons not to deploy red[C]// IEEE. 1999 Seventh International Workshop on Quality of Service, London:IWQoS′99,1999: 260-262.

[6] 任丰原,林 闯,王福豹.RED算法的稳定性:基于非线性控制理论的分析[J]. 计算机学报, 2002(12):1302-1307.

[7] 梁 潘.基于NS2的PQM和AQM的仿真实现与比较[J].常州工学院学报,2010,Z1:60-63;79.

[8] Floyd S, Jacobson V. Random early detection gateways for congestion avoidance [J]. IEEE/ACM Transactions on Networking, 1993, 1(4):397-413.

[9] 王云涛.网络拥塞控制算法研究[D].上海:东华大学,2010.

[10] Zheng C, Dai Y, Chen J. Is current active queue management really necessary[C]// IEEE. Education Technology and Computer Science, First International Workshop on IEEE. Wuhan: ETCS,2009: 538-541.

[11] 姜文刚,孙金生,王执铨.两次随机丢包的被动队列管理算法[J].系统仿真学报,2011(5):987-991;997.

[12] 姜文刚,孙金生,王执铨.N次弃头的被动队列管理算法[J].小型微型计算机系统,2011(9):1849-1853.

[13] 王文涛,王 豪,郭 峰,等.基于OMNeT++的AODV-UU、DSR-UU 和DYMOUM路由协议性能仿真与分析[J].中南民族大学学报：自然科学版,2013,32(4):91-96.

[14] Jiang W, Shang J, Sun J, et al. Reformed passive queue management algorithm[C]//IEEE.Electrical and Control Engineering, 2011 International Conference on IEEE. Yichang:ICECE,2011: 3087-3090.