传统的管理队列长度的方法就是对每个队列设置一个最大阈值,然后接收包进入队列直到队长达到队列的最大阈值,接下来到达的数据包就会被拒绝进入队列直到队长下降,这种算法被称为“去尾”(drop tail)算法。由于该方法实现起来比较简单,当前广泛应用于Internet,但是该算法存在两个重要的问题:死锁现象(Lock-out)和满队列(Full-queues)问题。
由于传统的“队尾丢包”管理机制不能有效的解决网络拥塞问题,IETF(Internet Engineering Task Force)即互联网工程任务组,提出使用主动队列管理算法(AQM)进行分组报文缓冲管理。它与传统的“队尾丢包”相比,AQM在网络设备队满缓冲溢出前就主动丢弃/标记报文,这样源端便能在队满溢出前对拥塞作出反应。这种方法称为“主动式队列管理”(Active Queue Management ,AQM)。
早期的IP网络中拥塞控制机制缺少网络传输节点的配合,这使得网络的运行效率很低,难以达到消除拥塞的效果,而且网络发生拥塞后,会造成网络利用率急剧下降。最早的AQM算法是由Floyd和Jacobson提出的的随机早期检测(Random Early Detection,简称RED)算法,该算法把拥塞控制加入到网络传输节点控制机制中,从而提高了网络资源的利用率,该算法至今都有广泛的影响。RED算法是根据平均队列长度来预测可能到达的网络拥塞,只要发现拥塞逼近,就会随机选择对分组进行丢弃/标记,这样就随机地通知源端到达的拥塞,使它们在队满溢出前降低发送数据的速率,以减少网络拥塞,从而达到拥塞避免的目的。由于RED算法随即地丢弃/标记到达的分组报文,使不同的TCP流不会同时降低或升高发送数据速率,从而避免了TCP流的全局同步问题。
在目前的网络中,RED算法是IETF指定的唯一的AQM算法,但它存在两个明显的缺陷:参数设置难度大和丢包的随意性。这会导致网络的性能下降,使网络的延迟变大,吞吐率下降,从而导致网络链路利用率降低低,网络资源浪费严重。为了克服RED算法的种种缺点,近些年很多的研究者提出了各种新的AQM算法。而每种算法都有其优点,能够在某些特定的方面改进网络性能,但在不同的环境下也存在着各种缺点。源:自~751-·论`文'网·www.751com.cn/
由于RED算法采用线性丢包策略,不同负载时效果不同,在轻负载时RED的参数设置使丢包率过大,而重负载时参数设置又使丢包率过小,导致采用RED算法时的吞吐量较低。为此Kaiyu Zhou等人首先提出了非线性RED(NLRED)算法。他们认为RED算法的不稳定性是由于该算法采用的线性丢包函数,故其提出使用二次函数代替线性函数的AQM策略。
Feng等人提出了一种可以自适应配置参数的RED算法(Self-Configuring RED),解决了RED算法静态参数配置的局限性。该算法能够在线自动地配置参数来选择合适的参数。这种算法能够有效地降低数据包的丢失率,而且还能在网络负载较重的情况下,维持较高的链路利用率。算法实现简单,开销低,特别适用于主干路由器。但是这种参数调整给最大丢包概率带来的波动比较大,导致队列波动也比较大。Floyd[15]在Feng等人提出的参数自适应配置的RED算法基础上,改进了该自适应配置参数的RED算法,提出了自适应RED算法(Adptive-RED算法),简称ARED算法,该算法更严格地限制了平均队列长度的变化范围和丢弃或标记概率参数的调整范围,保持了队列的稳定。他们提出的算法把RED算法的控制参数动态化,提高了RED算法的鲁棒性,能获得更加稳定的性能,但是这种算法却增加了处理的复杂度,参数的调整设置需要考虑,参数取值不当会导致系统振荡,不利于网络的稳定。