一种降低丢包率的主动队列管理改进算法

张 洁，韩 波，卢 琼

（商洛学院 数学与计算机应用学院，陕西商洛 726000）

拥塞控制一直是互联网中最重要的问题之一。随着越来越多的基于UDP的上层多媒体应用被部署，单纯依赖TCP端到端的传统拥塞控制算法不再可行[1]。在网络中，尤其是网络中的路由器，应该在资源分配方面承担主要作用，这样有利于有效的控制/阻止拥塞，这一类策略被称为主动队列管理（AQM）。在众多AQM策略中，随机早期检测算法（简称RED）是目前研究的热门。RED算法旨在解决全局同步问题和突发数据源受限问题。一些研究者提出，RED算法的性能相比普通的数据包丢弃策略没有明显的提升[2]。而更多的研究者[3]则认为，RED算法与普通的弃包策略相比有明显的优势但仍然不完美，事实上，这种不完美则主要在于以下若干原因。

RED算法的性能极大的受影响于其参数的设置[4]。在RED算法中至少有4个参数，分别名为：最大阈值（maxth）、最小阈值（minth）、最大弃包概率（maxp）和加权因子（wq），这四个参数必须设置的非常恰当才能明显提高RED算法的性能；RED算法的性能对于竞争数据源/数据流的数目比较敏感；RED算法的性能也受到数据包长度的影响；RED弃包概率函数是一个分段线性函数。它由一个三元组（minth,maxth,pmax）来定义。当某个数据包到达，如果队列的平均长度qa小于minth，那么该数据包将被提交至队列。否则，当队列平均长度大于maxth则该数据包将被丢弃。如果qa介于minth和maxth之间，则对qa进行线性函数概率计算，随机丢弃该数据包。但是，队列的长度并不能有效的反映出网络拥塞的真实状况。发送过多的拥塞通知包会导致多余的数据包丢失，而过少则无法有效的组织拥塞形成。

在RED算法当中，当数据负载变化时容易发生恶性的队列振荡。结果，RED算法通过各种方法被进一步拓展和改进。近年来，国内外关于提高RED算法的稳定性和鲁棒性的研究主要集中在设计自适应地控制参数调整策略和采用其他更能反映网络拥塞的丢弃概率函数两个方面。这方面的改进算法有基于网络流量变化的Adaptive RED[5]、根据比例微分控制器原理的PD-RED[6-7]。除了以上两方面的研究，关于RED算法的研究还涉及到其他方面。比如，CHOKe算法最大的缺点是随着网络中流数目的增加，每个流在当前队列缓存中的分组数也会减少，对非适应流的惩罚力度不够，不能很好地实现带宽的公平分配[8]。以及AFD(Approximate Fair Dropping)[9]算法巧妙利用了网络流量的分布，是少数的“大”流占据绝大部分的带宽，即重尾分布的特性。通过分组采样记录的流以较大的概率包含网络中的“大”流。在网络发生拥塞时，对这些“大”的分组实施丢弃，对于没被记录的流不丢弃分组。

1 风险均数算法

所谓的风险均数算法，就是在给定某个单元直到时间t无效的情况下，在时间t发生失效的条件密度函数。所以，用X表示随机变量，用x表示自变量。

式(1)表明，指定一个风险算法可以完全确定累积分布函数，反之亦然。

威布尔分布的风险均数的计算公式为：

对于式(2)，当β=1时，威布尔风险均数是个常量。因为当β=1时，威布尔分布将为常值。当β＞1时，威布尔风险均数将从β开始增大并趋于无穷大。因此，对于那些由于负载过重或任务过量造成性能严重退化的系统或部件而言，威布尔风险均数是最合理的选择。当β＜1时，威布尔风险均数将由β开始减小并趋于0。

相比之下，伽马分布的风险均数也有γ和λ-两个参数。同样地，当γ=1时，风险均数将为常值。当γ＞1时，风险均数将递增且当γ＜1时风险均数将递减。但是，当γ＜1时，风险均数从小增大并趋近于λ，且当γ＜1时从大到小趋近于λ。所以，即使伽马分布曲线与威布尔分布曲线看起来非常相似，并且两种方法都能产生符合要求的数据样本。但是他们在定义有效数据或可信数据方面有不同的特点。

最终，把威布尔分布函数的风险均数算法简化为 h（x）=cac-1，见图1。

图1 威布尔分布的风险均数函数

2 HERED算法

与目前大多数改进的RED算法不同的是，本文提出的改进思路将RED算法中的弃包策略更换为风险评估算法，其余部分依然保持原有的RED策略不变，将这种策略称之为HERED。也就是说，利用这种非线性包丢弃方法，能够根据数据负荷的实际情况，在负载较轻时减少弃包，在负载较重时加速弃包，从而有效提高传输效率和算法性能。所以，当负载较轻时，HERED能够动态的调整操作队列长度。当负载很重或队列平均长度接近最大阈值maxth时，队列长度指示器会很快失去控制，HERED算法允许快速将大量的数据包快速丢弃。通过仿真可以证明，HERED算法能够达到比RED算法更高更稳定的吞吐率。因为HERED能够完全兼容RED算法，可以很容易将RED算法升级或更新至HERED算法。

对RED算法进行了一些大的改变，并且称之为HERED算法。HERED算法的一个最重要的优势是，它通过使用风险均数函数来改变弃包概率值。在这里，用T和qlen分别来标记目标值和队列长度。为了在高拥塞水平下稳定队列长度，设置风险均数函数中的c=3，c=2，再c=3来分别对应 minth

对每一个到达的数据包

用风险均数函数

h(x)=cxc-1

计算新的弃包概率p：

如果qlen

c=0

不丢弃

或者，如果 minth≤qlen＜T

c=3

计算Pa概率：

对于Pa概率：

或者，如果 T≤qlen＜maxth

c=2

计算Pa概率：

对于Pa概率：

标记到达的数据包

或者，如果 maxth≤qlen＜2*maxth

c=3

计算Pa概率：

对于Pa概率：

标记到达的数据包

或者，如果 qlen≥2*maxth

标记到达的数据包

3 仿真结果

将HERED算法与现有的队列管理策略REM和RED进行仿真结果比较。

所有的仿真结果均使用NS-2模拟器来实现。在所有仿真中，使用图2所示的网络拓扑结构，该拓扑结构包括N个发送方和一个sink节点，通过路由器N连接在一起，然后采用某种队列管理算法。Sn代表TCP流的源。通过改变每个源Sn的数据流数目来产生不同级别的负载轻重，从而仿真瓶颈链路的不同级别的网络拥塞。其中，N具有50个数据包长度的缓冲区队列。

仿真使用的参数见表1。

表1 仿真参数

在这些仿真中，从所有（S1，S2）中的节点到目的节点d1,d2，有10到200个TCP源运行了100 s。图3说明了RED、REM和HERED算法的数据表丢失率。很明显，HERED算法丢失的数据包最少。

图2 仿真拓扑结构

图3 RED、REM和HERED算法的丢包率

4 结论

针对RED中使用的风险率评估包丢弃方法，分析不同复杂算法的主动队列管理策略，进而根据负载情况动态调整弃包策略，在轻负载时减缓弃包，在重负载情况下加速弃包，由此给出一种基于威布尔分布失效函数的主动队列管理算法，仿真结果表明，所给算法具有较低的数据包丢弃率，性能优于已有的主动队列管理算法。

[1]Floyd S,Fall K.Promoting the use of end-to-end congestion control in the Internet[J].IEEE/ACM Transactions on Networking(TON),1999,7(4):458-472.

[2]Fan X,Zhang J,Guan L.QBLUE:A New Congestion Control Algorithm based on Queuing Theory,HPCC-2012,25-27 June,2012:1253-1257.

[3]Zhang J,Fan X.An Improvement Algorithm of AQM to Reduce the Packet Loss Rate,2012 Third International Conference on E-Business,11-13 May,Shanghai,China,2012:3294-3297.

[4]Fan X,Wang J,Guan L.Heuristic Active Queue Management with Hazard Rate Function,ICNC'11-FSKD'11,26-28 July,Shanghai,China,2011:281-2285.

[5]Floyd S,Gummadi R,Shenker S.Adaptive RED:An Algorithm for Increasing the Robustness of RED's Active Queue Management[R].Berkeley,CA,2001.

[6]Sun J,Ko K,Chen G,et al.PD-RED:to improve the performance of RED[J].IEEE Communication Letters,2003,7(8):406-408.

[7]魏 涛,张顺颐.一种模糊自调整的PD-RED算法[J].计算机工程与应用,2007,43(5):124-126.

[8]高文宇,王建新，陈松乔．PFED:一种基于预测的公平的主动队列管理算法[J].计算机研究与发展,2006,43(2)：204-210．

[9]邹雪兰,刘伟彦,孙雁飞.一种基于速率的公平队列管理算法[J].计算机工程,2009,35(6):29-31,34．