一种基于排队论的主动队列拥塞控制算法

闫英战，田立伟

(广东科技学院计算机系,广东东莞 523083)

一种基于排队论的主动队列拥塞控制算法

闫英战*，田立伟

(广东科技学院计算机系,广东东莞 523083)

主动队列(AQM)算法存在诸多的不足，如排队延时大、时延抖动性强、数据进队与出队速率不匹配等，从而导致数据的滞留、丢失和振荡．基于此，在BLUE算法的基础上，引入M/M/m (n)排队系统的思想，提出一种新的算法——PBLUE．该算法根据稳定状态下的平衡方程来保证队列长度的稳定性，增加扩充因子调节路由器的缓存来快速恢复丢失的数据．通过仿真实验，改进的算法降低了丢包率，提高了带宽利用率，并稳定了队列长度．

排队论； 主动队列； BLUE； 带宽利用率； 丢包率； 队列长度

目前常见的主动队列管理算法有：RED,PI,REM,BLUE[1],AVQ等．作为中间路由管理算法，他们共同的目标就是期望在减小排队时延的同时保证较高的吞吐量和带宽利用率，并减小丢包率．综合比较之下，BLUE算法表现得最为优秀，但在链路状态不稳定时，队列依旧会发生较大的振荡．基于此，很多学者从不同的方面对BLUE算法进行了改进[2-4]:文献[2]依据平均队列长度，动态调整BLUE算法丢包率的控制参数d1和d2，同时在tcp连接数不断突变的情况下，动态调整P的值和提高算法的刷新速度，降低了丢包率；文献[3]依据模糊控制理论，细化了丢包概率控制步长d的值，提高了带宽利用率，维持了队列长度；文献[4]根据队列负载因子控制丢包步长，稳定队列长度在一定的范围内，从而使丢包率能够自适应并调节，队列收敛时间短，丢包率小．这些算法都有效提高了算法的鲁棒性和实用性．本文引入M/M/m(n)排队系统模型的思想，解决系统的服务质量与系统效率之间的矛盾，以期能压缩排队长度、减小等待时间．通常采用2种措施：一是增加路由结点(窗口)，可提高总服务率但意味着投资加大；二是稳定排队长度，提高系统效率和稳定性．

1 BLUE算法简析

1.1BLUE算法

BLUE算法提出了用丢包概率P来标记数据包．如果链路空闲导致队列空或者队列长度较小，BLUE就减小概率P的值．相反，如果队列有较大溢出导致数据持续的丢失，BLUE算法就增加概率P的值，同时增加了向发送端反馈拥塞状态的速度．这样BLUE就能有效地控制反馈拥塞通知信息的速度．其具体算法如下所示[1]：

Upon the queue overflows lead to greater sustained loss of data:

if ((now-last_update)>f_time)

{P = P+d1;last_update = now;}

Upon link idle event lead to queue empty or queue length smaller:

if ((now-last_update)>f_time)

{P = P-d2;last_update = now;}

BLUE的主要参数有d1、d2和f_time．其中，d1决定了当队列溢出时P增加的量，d2决定了当链路空闲时P减少的量．f_time决定了连续改变P的最小时间间隔，使得P改变之后在再次变化之前能有效发挥作用，是一个控制周期．一般来说，d1要比d2大，因为丢包只发生在拥塞管理太保守时．这样，通过赋予丢包事件更大的比重，BLUE能够对流量迅速的增加很快地作出反应．

1.2Blue算法的优缺点

BLUE基于丢包事件和链路空闲事件的拥塞管理，能够较好地估计拥塞程度，作出适当的反应．因为标记数据包的丢包概率P相对较稳定，使得队长也相对稳定，从而减小了延迟抖动．而RED基于平均队长的拥塞管理，由于不能正确及时地估计拥塞严重性，特别是在负荷很重、变化很快的情况下，常常导致队长波动很大，增加了丢包数和延迟抖动，甚至产生全局同步现象，降低链路使用率．但是BLUE算法仍然存在以下缺点：一是由于发生丢包事件后BLUE会相对大的增加丢包概率，从而会产生连续丢包，导致TCP陷入超时，严重时会降低链路利用率．二是参数f_time的设置问题．如果f_time太小，会导致P的变化过于频繁，使得拥塞管理很激进；如果f_time太大，P的变化很缓慢，从而使得拥塞管理很保守，不能适应流量的快速变化．

2 M/M/m(n)排队系统模型

2.1模型简介

图1 M/M/1/K排队系统模型

图2 M/M/1/K的排队系统的状态转移

2.2瞬态方程及其解

现考察区间(0，t+△t),它可看成(0,t]∪(t,t+△t)．于是，可以把n个数据包的到达这个事件分解为以下事件的合并:在(0,t]内到达n+1个数据包,在(t,t+△t)内离开一个数据包；在(0,t]内到达n-1个数据包,在(t,t+△t)又到达一个数据包；在(0,t]内到达n个数据包,在(t,t+△t)内数据包的到达数为0．时间间隔t(不失一般性,可设为(0,t]区间)内有n个数据包到达的概率记为Pn(t)．故而可列出以下瞬态方程[5]:

(1)

M/M/1/n的稳态解为：

Pn=(1-ρ)ρn(n=0,1,2,…),

(2)

平均队长为：

(3)

由Little定理,时延为：

(4)

2.3稳定状态下的平衡关系

设所有到达间隔和服务时间都是服从泊松(指数)分布的,那么从任何时刻直到状态变化的这段时间也是泊松(指数)分布的．对于M/M/1，表1展示了平衡方程的进入率与离开率的对应关系．

表1 平衡对应关系Table 1 Balance correspondence relationship

3 改进的算法—PBLUE

3.1算法基本思想

采用多次排队-多窗口串列排队系统．该系统中，设数据流是参数为的泊松流(指数流)，表示单位时间到达的数据包个数(到达率)，从而数据包到达间隔时间服从参数为的负指数分布，平均到达间隔时间为1/，到达的数据能全部进入系统接受服务．处理一个数据包的服务时间V服从参数为μ的负指数分布，平均服务时间为1/μ．且设服务时间与到达间隔时间相互独立，ρ=/μ称为服务强度．

下面考虑中间系统(图3)构成的排队系统．

图3 多次排队-多窗口串列

Figure 3 Multiple queue - multiple window series

在原有BLUE算法机制基础上，本文提出基于排队论的改进算法——PBLUE．该算法的核心思想是针对服务强度、路由器缓冲区和链路环回时间等3方面进行改进的，具体做法如下：

第一：根据稳定状态下的平衡方程，用ρ来表征对系统稳定性的影响：若ρ<1，即<μ时，说明平均到达系统的数据包数小于平均离开系统的数据包数．这时系统是稳定的，可以采取递增方式．若ρ≥1，即≥μ时，说明平均到达系统的数据包数多于平均离开系统的数据包数．这时应该采用拥塞控制方式，即提高向发送端反馈拥塞状态的速度，限制系统内的数据包数量，保证系统的稳定性．

第二：增加扩充因子△n调节路由器缓冲区的空间，根据数据包序列号进行判断，如果当前收到的数据包序列号不是上个数据包序列号加1,并且当前数据包序列号小于上个数据包序列号加△n，那么就空出缓冲位置重新接收2个序列号之间的数据；反之如果当前数据包序列号大于上个数据包序列号加△n，那么就丢弃该数据包[6]．△n的大小设置采用下式所示:

(5)

3.2算法代码描述

(1)拥塞控制的调整.

当队列增加新的数据包后：

//认为是队列缓存严重溢出

P=P+d1; //增加丢包率

cwnd=cwnd*m; //通过调控因子m减小发送窗口的值

end if

P=P+d1/2;cwnd=cwnd+(1/cwnd)*m;

end if

P=P-d2; //减小丢包率

cwnd=cwnd^2; //保持发送窗口指数增长

end if

(2)对路由器缓存和队列长度的调整.

当有新的数据包进入队列后：

//j为当前数据包的序列号，i为上一个数据包的序列号，p_len为缓存区长度

end if

p_len=p_len; //保持缓存长度，丢弃该数据包

end if

4 仿真实验

采用NS-2仿真平台对以上改进做仿真实验．记录瓶颈链路的带宽利用率、丢包率和队列长度,网络拓扑结构如图4所示．网络相关参数为：发送端和接收端的带宽为1 Gb/s，时间延迟为10 ms．瓶颈链路带宽为100 Mb/s，时间延迟为20 ms，模拟时间为50～100 s．PBLUE算法中的参数设置如下：R1到R2之间的队列缓存初始长度为100个数据包，d1=0.000 15，d2=0.000 015，f_time=10 ms[3],m=0.5或m=0.4[7]，模拟时间50～100 s．

图4 网络拓扑结构

实验一：3个协议流共享瓶颈带宽．它们分别是2个中间队列算法为BLUE的TCP协议流和1个UDP流；2个中间队列算法为PEBLUE[2]的TCP协议流和1个UDP协议流；2个中间队列算法为PBLUE的TCP协议流和1个UDP协议流．由图5可以看出新算法每条TCP流的带宽利用率比PEBLUE有所提高，与BLUE算法相比有较大的提高．由表2可以看出2条PBLUE流的带宽利用率比2条BLUE流的利用率高出大约12%.

由表3看出，新算法PBLUE在瓶颈链路的丢包率大大降低．BLUE算法的丢包率为0.545%，而PBLUE算法的丢包率是0.281%，新协议丢包率降低了46.2%．

图5 BLUE/PEBLUE/PBLUE的带宽利用率比较

Figure 5 BLUE/PEBLUE /PBLUE bandwidth utilization comparison

表2 BLUE、PEBLUE和PBLUE的平均带宽利用率的比较

Table 2 BLUE、PEBLUE、PBLUE comparison of the average bandwidth utilization

AQMBLUEPEBLUEPBLUE带宽利用率/%74.5076.4486.28

表3 BLUE/PBLUE在瓶颈链路上的丢包率比较

Table 3 BLUE/PBLUE packet loss rate comparison on the bottleneck link

AQMBLUEPBLUE发送包数1430613163丢包数7837丢包率/%0.5450.281

实验二：设置瓶颈带宽为100 M，分别让BLUE流、PEBLUE流和PBLUE流通过，测得BLUE算法、PEBLUE算法和PBLUE算法瞬时队列长度如图6、图7和图8所示(通过计算BLUE算法的队列长度方差为447.83，而PBLUE算法的队列长度的方差为125.26),显然BLUE算法队列长度抖动大，队列保持不稳定状态；观察PEBLUE算法前期队列长度集中收敛，随着拥塞的发生，队列波动偏大；而PBLUE算法队列长度相对稳定集中，这样有利于中间路由的存储和转发，也有效避免拥塞的发生．

图6 BLUE流的瞬时队列长度

图7 PEBLUE流的瞬时队列长度

图8 PBLUE流的瞬时队列长度

5 结束语

本文借助排队论的一些思想，结合BLUE算法原有的机制，对算法进行改进．实验结果表明新算法在带宽利用率和丢包率方面有所改善，并保持排队长度相对稳定，但在算法的友好性和公平性方面仍需加强．总之，引入排队论理论[8]、模糊控制理论[3]、非线性动力学理论等方面的知识来改善网络拥塞控制算法是一个值得努力的方向．

[1] FENG W C，SHIN Kang G，KANDLUR D, et al.The blue active queue management algorithms IEEE /ACM transactions on networking[J].August，2002，10(4)：513-528．

[2] 杨云，徐佳，王秋平，等.一种精确度加强的主动队列管理算法PEBLUE[J].小型微型计算机系统，2006,27(4).592-595.

[3] 苏聪，陈元琰，罗晓曙，等. 基于模糊理论的主动队列管理算法—FBLUE[J]，计算机工程与应用，2006,23. 117-120.

[4] 陈伟杰，王万良，蒋一波, 等. SABlue：一种带加速因子的自适应AQM算法[J]，电子与信息学报，2011，33(2)，479-484.

[5] 盛友招. 排队论及其在现代通信中的应用[M]. 北京：人民邮电出版社，2007.

[6] 赵跃华，徐胜芹. 排队论在AQM网络传输中的应用[J]. 计算机工程与设计，2008,29(15):3870-3871; 4085.

[7] 张瑞，洪佩琳，李津生，等. 无线网络中一种改进的TCP 拥塞控制机制 [J]. 电路与系统学报，2006:7-13.

[8] 于国防，王耀才，庄立运，等.基于分配器队列模糊控制的集群负载平衡[J].计算机工程，2008,34(6):129-130;136.

Keywords： queuing theory； AQM； BLUE; bandwidth utilization; packet loss rate； queue length

ANewCongestionControlAlgorithmforActiveQueueBasedonQueuingTheory

YAN Yingzhan*, TIAN Liwei

(Department of Computer, Guangdong University of Science and Technology，Dongguan, Gunagdong 523083, China)

AQM algorithm has many deficiencies, such as a large queuing delay, strong delay jitter, the rate of the data into and out the team not matched, and thus it always leads to data retention, loss and oscillation. Based on this, the M/M/m (n) queuing system thought based on the BLUE algorithm is introduced which is called PBLUE. The algorithm ensures the stability of the queue length according to equilibrium equation under stable state. Meanwhile, it increases the expansion factor and adjusts the router’s cache for quickly recovering of the lost data. In the simulation, the improved algorithm reduced the packet loss rate and increased the bandwidth utilization and stabled the queue length.

2011-04-29

国家自然科学基金项目(70571017)；广西壮族自治区自然科学基金项目 (0728099)

*通讯作者, 749284297@qq.com

1000-5463(2012)01-0063-04

TP393

A

【责任编辑 庄晓琼】