云南龙网

  1. 首页 > 云知道 > >

1 Internet路由器主动式队列管理机制综述( 三 )

云知道


避免了"死锁"现象：AQM能够通过确保到来的包几乎总是有可用的队列空间 ， 从而阻止"死锁"行为的发生 。也因为这个原因 ， AQM能防止路由器对低带宽高突发的流的偏见 。
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的方法如下：
Pb = maXP×(avgQ-minth) / (maxth-minth)
P = Pb / (1-count×Pb)

我们注重到P不仅和avgQ有关 ， 而且还和从上一次丢包开始到现在进入队列的包的数量count有关 。随着count的增加 ， 下一个包被丢弃的可能性也在缓慢增加 。这主要是为了在到来的包之间均匀间隔地丢包 ， 避免连续丢包 ， 从而避免对突发流的偏见和产生全局同步现象 。

推荐阅读


上一篇：永州师范高等专科学校有哪些专业

下一篇：电流的磁效应 电流的磁效应和电磁感应的区别