论文部分内容阅读
1 引言
新型网络应用的不断涌现和用户数量的迅速增长给路由节点造成很大负担，越来越严重的网络拥塞问题暴露出来。拥塞控制算法在网络稳定运行方面具有十分重要的作用。研究表明由IP层参与的控制工作能更有效地对拥塞进行监测和预防，因此关于IP层拥塞控制的研究形成了一个新的热点，目前主要集中在AQM (Active Queue Management）算法方面。
2 RED的缺陷和改进分析
早期的RED算法采用指数加权滑动平均(EWMA)获得平均队长Avg，并通过其与阈值minth和maxth的关系计算丢包率，在一定程度上缓解了拥塞压力。但是其调节决策依据为平均队长，只能保证平均队长的相对稳定。EWMA的滞后性使得流量速率发生突然变化时平均队长不能够反映瞬时队长的变化。因此应将流量速率和队列长度有效地结合来作出预测，作为下一步处理的重要依据。PFED算法在同时满足条件 LF > 1 以及 Qk > Qs/2 (LF 、Qk、Qs分别代表负载因子、瞬时队长和缓存大小)时认为发生了拥塞，然而Qk > Qs/2这一判定条件显然是一种粗粒度的估计方式。
另外Pdrop的值应随拥塞程度的增加而相应增长，当有大量的活跃的TCP连接时，总流量呈现突发性增长。RED仅当Avg在阈值范围内时，丢包率呈线性增长，这与实际网络的性能并不相符。Gentle-RED引入了阈值2maxth 来扩大稳定工作区间，NARED的改进是令Avg在minth 至缓存区间内的丢包率呈非线性函数变化，算法作用范围扩大至整个缓存。研究证明了这种平滑效果的有效性，因此在设计中应考虑以上思想。
3 QRC算法设计与仿真试验
3.1 算法设计
为了对拥塞发生后的链路状态进行更准确的评估，本文采用结合流量速率与队列长度预算下一时段到达满队列时间的办法，简称QRC（Queue and Rate Based Control）。首先采用指数平均预测分组丢弃概率，然后根据下式计算剩余时间Tr（C为链路带宽）并将其同设定阈值Tth进行比较。当Tr Tr=Δq-Δr=(Qs- Qk)/(ri-C)（1）
最后据拥塞程度的不同将主动丢弃概率的计算分为两阶段 (Qtarget为目标队长，β为调节参数)：
3.2 仿真实验
实验1：考察网络负载突然变化情况下的算法稳定性和响应性。在30s突然启动300个TCP流并持续到仿真结束，两种算法的队长变化如下图所示。
大部分时间里QRC能将队长控制在目标附近，获得了更小抖动。相比而言QRC的响应性较好，能在2s内将队长调整至期望值附近。
实验2：使TCP流到达服从指数分布，源节点发送数据大小符合Pareto分布，考察负载随机变化时的算法性能。
表1表明QRC的综合指标优于PFED，算法整体性能得到了提高，基本达到了我们的预期目标。
4 结论
QRC重点针对RED和PFED的缺陷进行了改进，采用流量速率和队长相结合的方法对链路情况作出准确判断，并对Pdrop的计算进行分段调整，实验表明该策略在综合性能上的改善。
参考文献
[1]Floyd S,Jacobson V.Random Early Detection Gateways for Congestion Avoidance.ACM/IEEE Transactions on Networking,1993.1(4):397～413.
[2]高文宇，王建新，陈松乔.一种基于预测的公平的主动队列管理算法.计算机研究与发展,2006.43(2):204～210.
[3]邓晓衡,陈志刚,王建新,等.NARED:一种非线性自适应RED拥塞控制机制.小型微型计算机系统,2006，43（2）：204～210.
[4]I•Stoica,S•Shenker,H•Zhang.Core stateless fair queue:Achieving approximately fair bandwidth allocations in high speed networks IEEE ACM Trans Networking,2003,11(1):33～46.
新型网络应用的不断涌现和用户数量的迅速增长给路由节点造成很大负担，越来越严重的网络拥塞问题暴露出来。拥塞控制算法在网络稳定运行方面具有十分重要的作用。研究表明由IP层参与的控制工作能更有效地对拥塞进行监测和预防，因此关于IP层拥塞控制的研究形成了一个新的热点，目前主要集中在AQM (Active Queue Management）算法方面。
2 RED的缺陷和改进分析
早期的RED算法采用指数加权滑动平均(EWMA)获得平均队长Avg，并通过其与阈值minth和maxth的关系计算丢包率，在一定程度上缓解了拥塞压力。但是其调节决策依据为平均队长，只能保证平均队长的相对稳定。EWMA的滞后性使得流量速率发生突然变化时平均队长不能够反映瞬时队长的变化。因此应将流量速率和队列长度有效地结合来作出预测，作为下一步处理的重要依据。PFED算法在同时满足条件 LF > 1 以及 Qk > Qs/2 (LF 、Qk、Qs分别代表负载因子、瞬时队长和缓存大小)时认为发生了拥塞，然而Qk > Qs/2这一判定条件显然是一种粗粒度的估计方式。
另外Pdrop的值应随拥塞程度的增加而相应增长，当有大量的活跃的TCP连接时，总流量呈现突发性增长。RED仅当Avg在阈值范围内时，丢包率呈线性增长，这与实际网络的性能并不相符。Gentle-RED引入了阈值2maxth 来扩大稳定工作区间，NARED的改进是令Avg在minth 至缓存区间内的丢包率呈非线性函数变化，算法作用范围扩大至整个缓存。研究证明了这种平滑效果的有效性，因此在设计中应考虑以上思想。
3 QRC算法设计与仿真试验
3.1 算法设计
为了对拥塞发生后的链路状态进行更准确的评估，本文采用结合流量速率与队列长度预算下一时段到达满队列时间的办法，简称QRC（Queue and Rate Based Control）。首先采用指数平均预测分组丢弃概率，然后根据下式计算剩余时间Tr（C为链路带宽）并将其同设定阈值Tth进行比较。当Tr
最后据拥塞程度的不同将主动丢弃概率的计算分为两阶段 (Qtarget为目标队长，β为调节参数)：
3.2 仿真实验
实验1：考察网络负载突然变化情况下的算法稳定性和响应性。在30s突然启动300个TCP流并持续到仿真结束，两种算法的队长变化如下图所示。
大部分时间里QRC能将队长控制在目标附近，获得了更小抖动。相比而言QRC的响应性较好，能在2s内将队长调整至期望值附近。
实验2：使TCP流到达服从指数分布，源节点发送数据大小符合Pareto分布，考察负载随机变化时的算法性能。
表1表明QRC的综合指标优于PFED，算法整体性能得到了提高，基本达到了我们的预期目标。
4 结论
QRC重点针对RED和PFED的缺陷进行了改进，采用流量速率和队长相结合的方法对链路情况作出准确判断，并对Pdrop的计算进行分段调整，实验表明该策略在综合性能上的改善。
参考文献
[1]Floyd S,Jacobson V.Random Early Detection Gateways for Congestion Avoidance.ACM/IEEE Transactions on Networking,1993.1(4):397～413.
[2]高文宇，王建新，陈松乔.一种基于预测的公平的主动队列管理算法.计算机研究与发展,2006.43(2):204～210.
[3]邓晓衡,陈志刚,王建新,等.NARED:一种非线性自适应RED拥塞控制机制.小型微型计算机系统,2006，43（2）：204～210.
[4]I•Stoica,S•Shenker,H•Zhang.Core stateless fair queue:Achieving approximately fair bandwidth allocations in high speed networks IEEE ACM Trans Networking,2003,11(1):33～46.