网络拥塞控制经典算法RED仿真(2)
图1.1刻画了负载与吞吐量之间的关系，当负载较小时，吞吐量与负载之间呈线性关系，到达膝点(Knee)之后，随负载的增加，吞吐量的增量逐渐变小。当负载越过崖点(Cliff )之后，吞吐量却急剧下降。通常将Keen点附近称为拥塞避免区间；Keen和Cliff之间是拥塞恢复区间；Cliff之外是拥塞崩溃区间。为最大限度地利用资源，网络工作在轻度拥塞状态时应该是较为理想的，但这也增加了滑向拥塞崩溃的可能性，因此需要一定的拥塞控制机制来加以约束和限制，是研究拥塞控制最本质的意义[1]。
图1.1 负载与吞吐量间的关系曲线
1.2 网络拥塞控制经典算法RED
1.2.1 基本思想
Random Early Detection是为避免发生网络中的全局同步现象，在路由器采用的一种措施。它的基本思想是：通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。由于RED是基于FIFO队列调度策略的，并且只是丢弃正进入路由器的数据包，因此其实施起来也较为简单。
RED算法主要分为两个部分：首先是计算平均队列长度，以此作为对拥塞程度的估计。另一个就是计算丢弃分组的概率。
(1)计算平均队列长度
由于Internet数据的突发性，如果一个队列很多时候是空的，然后迅速被充满，又很快被取空，这时就不能说路由器发生拥塞而需要向源端发送拥塞指示。因此，RED在计算平均队长avgQ时，采用了类似低通滤波器(Low—pass filter)带权值的方法：
avgQ=(1.Wq)*avgQ+ Wq* q 式1.1
其中，Wq为权值，q为采样测量时实际队列长度。这样由于Internet数据的突发本质或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队长有明显的变化，从而“过虑"掉短期的队长变化，尽量反映长期的拥塞变化。
在计算平均队长的公式中，权值Wq相当于低通滤波器的时间常数，它决定了路由器对输入流量变化的反应程度。因此对Wq的选择非常重要，如果Wq过大，那么RED就不能有效地过虑短暂的拥塞；如果Wq太小，那么avgQ就会对实际队列长度的变化反应过慢，不能合理地反映拥塞状况，在这种情况下，路由器就不能有效检测到早期的拥塞。Wq的值应根据不同情况预先设置，一般来说，它是由路由器允许发生的突发业务的大小和持续的时间所决定的。
(2)计算丢弃分组的概率
计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃分组的概率，从而有效地控制平均队列长度。
RED有两个和队列长度相关的阈值：minth和maxth。当有分组达到路由器时，RED计算出平均队长avgQ。若avgQ< minth，则没有分组需要丢弃；minth ≤ avgQ ≤maxth时，因为avg的值域是（minth，maxth），包标记概率pb 从0到maxp线性变化：
pb←maxp (avg - minth)/(maxth - minth ) 式1.2
最终包标记概率pa 从上一个被标记包开始随着计数增加而缓慢增加：
pa←pb/(1.count*pb) 式1.3
并以此概率丢弃分组；当avgQ> maxth时，所有的分组都被丢弃。
图1. 2 丢包概率与分组队列的关系
由于RED使用的是基于时间的平均队长度，就有可能会发生实际队长大于平均队长的情况，如果队列已满，则到达的分组只能被丢弃。RED网关克服了丢尾网关和随机丢弃网关在控制行为不当用户和只有队列填满后丢弃后续的分组的缺陷 ，但是，RED算法的性能敏感于设计参数和网络状况，在特定的网络负载状况下依然会导致多个TCP的同步，造成队列震荡，吞吐量降低和时延抖动加剧[2]。RED算法的公平性和稳定性也存在问题。自RED被首次提出来之后，它的参数配置就是一个没有彻底解决的问题。
上一篇：神经元耦合系统中的同步研究综述
下一篇：基于FPGA的脉冲信号发生器设计