随着网络中信息（数据包）的不断增长，必然引起网络拥塞。于是，拥塞避免显得尤为重要，现在Internet上使用得比较广泛的拥塞避免机制是尾部丢弃策略（Tail drop polocy）：

TCP全局同步

当队列的长度达到规定的最大长度时，所有到来的报文都被丢弃。这种丢弃策略会引发tcp 全局同步（global synchronization）现象——由于Internet上数据(Traffic)的突发，到达路由器的数据包也往往是突发的。如果队列是满的或者几乎是满的，就会导致在短时间内连续大量地丢封包。而TCP流具有自适应特性(Adaptiveness)，来源端发现数据包丢失就急剧地减小发送窗口(congestion window，cwnd)，数据包到达速率就会迅速下降，于是网络拥塞得以解除。

但来源端得知网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞，而且这种现象常常会周而复始地进行下去，从而在一段时间内网络处于网络利用率(Network Utilization)很低的状态，降低了整体吞吐量(throughput)，这就是所谓地"TCP全局同步"现象。

丢尾会造成TCP流量之间分配带宽不均衡，一些"贪婪"的流量会占用大部分的带宽，而普通的TCP流量分配不了带宽而"饿死"。特别是网络中既有TCP又有UDP流量的时候，TCP流量因为窗口机制（丢尾造成滑动窗口cwnd减小）而释放带宽，UDP流量没有窗口机制，于是UDP流量会迅速占用TCP释放的带宽，最终造成UDP流量占用了所有带宽而TCP流量因没有带宽分配而"饿死"。

RED算法

RED算法其实很简单的，简单说就是防止网络拥塞的，一般来讲它是端到端的TCP拥塞控制的补充，用于路由器的居多。RED算法旨在能预测到网络将要拥塞，而提前采取丢包动作，而不是等到网络实际拥塞了以后再采取措施，这里的方式和操作系统的内存置换策略有点类似，因为在操作系统内核中也是需要提前预知内存将不足，而不是到实际内存不足的时候再腾地方，这是一种以保障持续运行为目的的策略，RED算法也是，典型的实现就是设置一个经验性的阀值，一旦剩余内存低于这个阀值 (对于内存置换算法)或者网络包的总长度大于这个阀值(对于RED算法)，那么就认为必须采取措施了。

RED算法中关键的两个参数：首先是计算平均队列长度，以此作为对拥塞程度的估计。另一个就是计算丢弃分组的概率。

计算平均队列长度

由于Internet数据的突发性，如果一个队列很多时候是空的，然后迅速被充满，又很快被取空，这时就不能说路由器发生拥塞而需要向源端发送拥塞指示。因此，RED在计算平均队长avgQ时，采用了类似计算平均往返时延RTT带权值的方法：

avgQ=(1-Wq)*avgQ+ Wq* q。

其中，Wq为权值，q为采样测量时实际队列长度。这样由于Internet数据的突发本质或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队长有明显的变化，从而“过虑"掉短期的队长变化，尽量反映长期的拥塞变化。

在计算平均队长的公式中，权值Wq决定了路由器对输入流量变化的反应程度。因此对Wq的选择非常重要，如果Wq过大，那么RED就不能有效地过虑短暂的拥塞；如果Wq太小，那么avgQ就会对实际队列长度的变化反应过慢。

随机早期检测 RED (Random Early Detection)算法使路由器的队列维持两个参数，即队列长度最小门限 THmin 和最大门限 THmax。

RED 对每一个到达的数据报都先计算平均队列长度 LAV。

若平均队列长度小于最小门限 THmin,则将新到达的数据报放入队列进行排队；

若平均队列长度超过最大门限 THmax,则将新到达的数据报丢弃；

若平均队列长度在最小门限 THmin 和最大门限THmax 之间,则按照某一概率 p 将新到达的数据报丢弃。

丢弃概率计算比较复杂，在此不再赘述，仅简要列出下面的关系:

丢弃概率 p 与 THmin 和 Thmax 的关系:

当 LAV<Thmin 时,丢弃概率 p = 0

当 LAV>Thmax 时,丢弃概率 p = 1

当 THmin<LAV<THmax时, 0<p<1

来源参考：

谢希仁，《计算机网络第五版》，电子工业出版社，p212-215