基于神经网络的自适应RED算法及其仿真研究(6)
第五章总结本文所研究的内容，并展望未来AQM算法的研究方向。
2 随机早期检测算法及其仿真研究
主动队列管理是当前网络拥塞控制的研究热点之一，近年来相继产生了许多AQM算法。本章先介绍一种最经典的AQM算法——RED算法，分别介绍RED算法的设计原理和计算过程，并分析它的优缺点。然后简要讨论网络模拟软件NS2在网络仿真中的应用情况。最后通过NS2网络模拟软件验证RED算法在变化的网络环境下的拥塞控制性能。
2.1 RED算法的设计原理
随机早期检测(Random Early Detection，RED)算法[14]是最著名的AQM算法之一，它由AQM创始研究人员Floyd教授提出，并且是IETF推荐的标准AQM算法。RED算法是一种早期丢弃技术，即在网络发生拥塞的早期就丢弃部分分组数据，改善队列的动态特性，提高网络利用率。与“队尾丢包”算法相比，RED为队列管理增添了两种新机制：(1) 分组丢弃不是等到队列缓存溢出时发生，而是根据队列长度利用概率判定机制预先丢弃部分分组来预防可能发生的拥塞；(2) 判定分组丢失概率依据的队列长度是平均队列长度，而不是即时队列长度，这在一定程度上可以吸收部分短暂的突发流量。
RED算法的网络拥塞衡量指标是平均队列长度，以和平均队列长度成正比的丢包率对到达的数据包进行丢弃或标记，尽早对网络拥塞信息采取行动，达到拥塞避免的目的。其基本思想是路由器在每个接口只文持一个队列，采用指数加权滑动平均的方法计算平均队列长度 。每收到一个分组就重新计算队列的平均长度，并和预先设定的两个门限：平均队列长度的最大门限 和最小门限 进行比较，然后以一定的概率丢弃数据包。
RED算法主要分成两个部分，首先计算平均队列长度，以此作为拥塞程度的估计，然后就是计算丢包概率。具体过程如下[51]：
RED队列管理策略根据分组到达或固定的时间间隔，采用指数加权滑动平均方法(exponential weighted moving average，EWMA)计算平均队列长度
(2.1)
其中 表示平均队列长度， 表示瞬时队列长度， 是一个加权系数，也是一个时间常数。
计算平均队列长度的目的就是反映拥塞程度并以此计算丢包概率。RED算法为平均队列长度设定了两个相关的阈值 和 以及最大丢包概率 。当有数据包到达路由器时，RED计算出平均队列长度 。若 ，则不丢弃包。当 时，计算出概率 ，并以此概率丢包，当 时，丢弃所有的包。计算丢包概率 的方法如下式：
其中 是预先设置的最大丢弃/标记概率， 是当前分组标记概率的计算值。概率 不仅与 有关，而且还和从上一次丢包开始到现在为止连续进入队列的数据包的数量 有关，随着 的增加，下一个包被丢弃的可能性也在缓慢增加。这主要是为了在到来的数据包之间均匀间隔地丢包，避免连续丢包，以消除对突发流的偏见及产生全局同步现象。
综上所述，所以数据包的丢弃/标记概率为
(2.2)
RED算法对改善路由器的队列特性有一定的作用，对突发数据流的适应性也较强；通过分摊各数据流的分组丢失概率，可以在各连接之间获得较好的公平性。虽然RED能够有效避免拥塞，但该算法仍然存在以下几个主要不足[52][53]：
(1) 公平性问题：对于不响应流，RED算法无法有效处理，所以这样的业务流经常会挤占大量的网络带宽，导致各种连接不公平地共享带宽。
(2) 参数设置问题：RED算法对参数设置很敏感，两个门限阈值 和 以及最大丢包概率 的细微变化经常会对网络性能造成很大影响，如何根据具体网络环境设置合适的参数是RED算法的一个重要问题。另外，一组参数可能会在获得较高的吞吐量的同时，也造成较高的分组丢弃率和较长的延时。如何设置参数，使得算法在吞吐量、时延和分组丢弃率等各方面均获得较好的性能也是有待解决的问题。