|
3 随机早期检测算法（Random Early Detection，RED）
RED拥塞控制机制的基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。由于RED是基于FIFO队列调度策略的，并且只是丢弃正进入路由器的数据包，因此其实施起来也较为简单。
3.1 随机早期检测的设计目标
RED主要试图达到以下目标：
最小化包丢失率和排队延迟
避免全局同步现象
避免对突发业务的偏见：网络中含有大量的突发数据，而传统的"去尾"算法对突发业务有很大的偏见。在采用"去尾"算法的路由器中，如果某个流的突发性越高，则当该流的包进入队列时越容易造成队列溢出，从而导致连续地丢弃大量的该流的包。
即使在缺乏传输层协议有效配合的情况下也能控制平均队列长度，从而避免拥塞。
为了达成以上目标，RED采用了基于时间的平均队列长度，并且随机地选择正进入路由器地包进行丢弃。这种方法能被有效地实施而无需在路由器中维持每个流（per-flow）的状态信息。
3.2 随机早期检测算法
RED算法主要分为两个部分。首先是计算平均队列长度，以此作为对拥塞程度的估计。另一个就是计算丢弃包的概率。
3.2.1 计算平均队列长度
由于Internet数据的突发性，如果一个队列很多时候是空的，然后迅速被充满，又很快被取空，这时就不能说路由器发生拥塞而需要向源端发送拥塞指示。因此，RED在计算平均队长avgQ时，采用了类似低通滤波器（low-pass filter）带权值的方法：
avgQ = (1-w)×avgQ+q×w
其中，w为权值，q为采样测量时实际队列长度。这样由于Internet数据的突发本质或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队长有明显的变化，从而"过虑"掉短期的队长变化，尽量反映长期的拥塞变化。
在计算平均队长的公式中，权值w相当于低通滤波器的时间常数，它决定了路由器对输入流量变化的反应程度。因此对w的选择非常重要，如果w过大，那么RED就不能有效地过虑短暂的拥塞；如果w太小，那么avgQ就会对实际队列长度的变化反应过慢，不能合理地反映拥塞状况，在这种情况下，路由器就不能有效检测到早期的拥塞。w的值应根据不同情况预先设置，一般来说，它是由路由器允许发生的突发业务的大小和持续的时间所决定的。
3.2.2 计算丢弃包的概率
计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃包的概率，从而有效地控制平均队列长度。
RED有两个和队列长度相关的阈值：minth和maxth。当有包达到路由器时，RED计算出平均队长avgQ。若avgQ小于minth，则没有包需要丢弃；当minth≤avgQ≤maxth时，计算出概率P，并以此概率丢弃包；当avgQ>maxth时，所有的包都被丢弃（如图1所示）。由于RED使用的是基于时间的平均队长，就有可能会发生实际队长大于平均队长的情况，如果队列已满，则到达的包只能被丢弃。
计算概率P的方法如下：
[1] [2] [3] [4] [5] [6] 下一页
|
|
|
