传统的路由器缓冲管理“尾部丢弃(Drop Tail)”策略,数据包到达时,如果缓冲队列已满,路由器则丢弃该数据包,但是Drop Tail算法很容易产生持续的满队列状态,甚至导致业务流对缓存的死锁和业务流的全局同步[2]。要防止拥塞的出现,应该预见式的而非反应式的丢弃分组,这种预见式的方法称为“主动队列管理”(AQM),是近来端到端拥塞控制研究中的一个热点。它除了使用分组丢弃,还使用分组标记还通知源端降低速率。虽然Braden等人在IETF提出的AQM的研究是在1998年,但与其密切相关的RED(Random Early Detection,随机早期检测)算法的研究却由来已久。
在1993年Floyd和Jacobson就提出了RED[3],当时的主要目的是克服网关偏袒突发业务而造成的不公平问题。因为在提出AQM研究时,RED是唯一能实现其目标的唯一算法,RED 算法主要试图达到以下目标:(1)最小化分组丢失率和排队延迟;(2)避免全局同步现象;(3)避免对突发业务的偏见;(4)在缺乏传输层协议有效配合的情况下也能控制平均队列长度,从而避免拥塞。它成为1998 年IETF 推荐的AQM 算法的惟一候选者。但它还是有一些明显的缺陷的,比如RED对参数设置非常敏感, 在一些特定的网络环境下很容易导致TCP全局同步和产生队列震荡。所以RED算法的改进引起了网络研究的关注。除了一些对RED稳定性的理论分析和通过实验对它的效果进行验证, 大部分工作都是修正RED算法来克服它的缺点, 产生许多RED的修改算法。较有影响力的:VRED、FRED、Adaptive RED、Self-configuration、RED、Stabilized-RED、Balanced-RED等。64488
此后,围绕着AQM和RED的研究逐渐丰富起来,相继产生了不少有影响力的算法,如:1999年Feng等人提出了BLUE算法[4],此算法是改进的on-off 控制,利用丢包事件和链路空闲时间动态微调报文丢弃概率:当报文发生丢弃时增加报文丢弃概率,当链路出现空闲降低报文丢弃概率。2001年Hollot等提出的PI(Pmportional—Integral)算法[5],此算法应用控制理论线性模型在链路中设置比例积分控制器以增加系统的稳定性与适应能力。论文网
此后,大量从控制理论角度出发的AQM 算法也涌现了出来。还有Kunniyur等提出了AVQ(Adaptive Virual Queue)算法[6],Athuraliya等提出了REM(Random Exponential Marking)算法。近年来仍有许多研究人员对这一热点领域进行了研究:
其中针对RED算法改进的有:许文龙,张京军等结合RED算法的主要思想,提出了一种改进的算法——IARED,利用模糊分布中的升半哥西分布的隶属函数代替原来的线性增加丢包率函数[7];还有王志等应用Logistic方程的RED改进算法[8]等。
研究利用控制理论提出的AQM算法也有很多,还有将神经网络控制、预测控制、自适应控制、模糊控制等方法运用于主动队列管理的设计和分析中。例如:Yang Hong等利用经典控制理论提出P算法,PI算法,PID算法[9],到近年仍有很多学者对此进行研究和改进[19][20]:如Jinsheng Sun,Sammy Chan等提出的智能自适应PI的主动队列管理算法[10];此外还有利用控制理论分析Smith预估器的暂态和稳态性能的,如Yi LI;King-Tim等提出了一种基于Smith预估器的AQM PI控制器(SPPA)[11]。