文档介绍：1
1、RED
RED拥塞控制机制的基本思想是通过监控路由器输出端口队列的平均长度 来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞， 使他们在队列 溢出导致丢包之前减小拥塞窗口， 降低发送数据速度，从而缓解网络拥塞。由于 RED是基于FIFO队列调度策略的，并且只是丢弃正进入路由器的数据包， 因此 其实施起来也较为简单。
RED主要试图达到以下目标：
最小化包丢失率
最小化排队延迟
避免全局同步现象
避免对突发流的偏见：网络中含有大量的突发数据，而传统的 "去尾
"算法对突发流有很大的偏见。在采用 "去尾"算法的路由器中，如果某 个流的突发性越高，贝U当该流的包进入队列时越容易造成队列溢出，从 而导致连续地丢弃大量的该流的包。即使在缺乏传输层协议有效配合的
情况下也能控制平均队列长度，从而避免拥塞。
为了达成以上目标，RED采用了基于时间的平均队列长度，并且随机地选择 正进入路由器地包进行丢弃。这种方法能被有效地实施而无需在路由器中维持每 个流(per-flow)的状态信息。
RED算法主要分为两个部分。首先是计算平均队列长度，以此作为对拥塞程 度的估计。另一个就是计算丢弃包的概率。
计算平均队列长度：
avg 二(1 - Wq) avg Wq q
其中，wq为权值，q为采样测量时实际队列长度。这样由于网络数据的突
发本质或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队长有明
显的变化，从而"过虑"掉短期的队长变化，尽量反映长期的拥塞变化。在计算平
均队长的公式中，Wq权值相当于低通滤波器的时间常数，它决定了路由器对输 入流量变化的反应程度。因此对 Wq的选择非常重要，如果 Wq过大，那么RED 就不能有效地过虑短暂的拥塞；如果Wq太小，那么就会avg对实际队列长度的 变化反应过慢，不能合理地反映拥塞状况，在这种情况下，路由器就不能有效检 测到早期的拥塞。Wq的值应根据不同情况预先设置，一般来说，它是由路由器 允许发生的突发业务的大小和持续的时间所决定的。
计算丢弃包的概率：
计算平均队长的目的就是为了反映拥塞状况， 根据拥塞的程度来计算丢弃
包的概率，从而有效地控制平均队列长度。RED有两个和队列长度相关的阈值：
3
minth和maxth。当有包达到路由器时，RED计算出平均队长avg。若avg小 于min th，则没有包需要丢弃；当 min^空avg空max^时，计算出概率P,并
以此概率丢弃包；当avg > maxth时，所有的包都被丢弃。由于 red使用的是 基于时间的平均队长，就有可能会发生实际队长大于平均队长的情况， 如果队列 已满，则到达的包只能被丢弃。
计算概率Pa的方法如下：
Pb 二 maxp (avg - minQ/(max^ 一 minQ
Pa 二 Pb 1 coun Pb)
我们注意到Pa不仅和avg有关，而且还和从上一次丢包开始到现在进入队列 的包的数量cout有关。随着cout的增加，下一个包被丢弃的可能性也在缓慢增 加。这主要是为了在到来的包之间均匀间隔地丢包， 避免连续丢包，从而避免对
突发流的偏见和产生全局同步现象。
下图一显示了 RED算法的丢包概率与平均队列长度之间的关系。 从图中,我
们可以看出丢包概率在两个阂值之间