众所周知，由于Internet采用的是统计复用(statistical multiplexing)技术，因此必须提供拥塞控制机制。TCP端到端的拥塞控制机制是确保Internet鲁棒性（robustness）的重要因素。在发生拥塞时，TCP源端会降低发送数据的速度，从而使得大量的TCP连接能够共享一条拥塞的链路。TCP拥塞控制机制已被证明在防止拥塞崩溃（congestion collapse）方面取得了巨大的成功。但这种机制的有效性依赖于两个基本的假设：
所有（或者几乎所有）的流都采用了拥塞控制机制
这些流采用的机制是同质的（homogene- ous）或者大体上相同即在相似的环境下按可比条件（丢包率、RTT、MTU）不会占用比TCP流更多的带宽，也即是TCP友好的（TCP-friendly）流。
但随着近十年来计算机网络的爆炸式增长，特别是多媒体业务的广泛应用，Internet已经不可能再仅仅依靠端节点提供的拥塞控制机制。这是由于下述原因，导致以上假设不成立：
（1） 一些应用没有采用拥塞控制机制因而不能对拥塞作出反应。许多多媒体应用和组播应用都属于此类。
（2） 有些应用使用了拥塞控制算法，但并不是TCP友好的，比如接受端驱动分层组播（Receiver-driven Layered Multicast RLM）采用的就是这种算法。
（3） 一些用户由于有意或无意的原因，使用了 non-TCP的拥塞控制算法。比如修改TCP，使得窗口的初始值很大并且保持不变，即所谓的"快速TCP"。
另外，我们知道，Internet上的流量是由无数条异质的数据流混合而成的。从有无有效拥塞控制机制的角度可以将这些异质的流分为以下三类：
TCP-friendly流
非适应（unresponsive）流：这种流是由于上述原因（1）造成的。
适应（responsive）流但非TCP- friendly流：这种流是由于上述原因（2）和（3）引起的。
很明显，这些不受TCP拥塞控制的应用会进一步增加Internet范围内拥塞崩溃的可能，并且TCP拥塞控制还存在着自相似、效率、公平性等方面的问题。因此尽管TCP拥塞控制机制是必须的而且非常强大，但仍然需要采用基于器的拥塞控制机制对端节点的拥塞控制机制进行补充。
拥塞避免机制的首要任务是检测早期的拥塞。这是因为，路由器能够有效地监控队列的长度，因此其也能有效地检测早期的拥塞（incipient congestion）。拥塞避免机制的另一个任务是选择哪个流发出拥塞通知。因为路由器能够全面地审视各个流对产生拥塞的影响，因此其也能够有效地决定将拥塞信息通知哪个源端，使其降低数据发送速度。
2 从传统的被动式队列管理到主动式队列管理
由于路由器是基于包的设备，每个端口采用带宽统计复用，所以路由器必须在端口上维护一个或多个队列，否则路由器无法处理多个数据包同时向同一端口转发以及端口QOS等问题。对队列进行管理直接影响路由器性能、拥塞管理能力以及QOS能力。路由器有两类和控制队列的算法：队列管理算法和队列调度算法。前者主要是在必要时通过丢包来管理队列长度。后者决定下一个要发送哪个包，主要用来管理各流之间带宽的分配。
由于Internet数据本质上是突发的，因此允许传输突发的数据包非常必要，而路由器中队列的重要作用就是吸收（absorb）突发的数据包。较大的队列能够吸收更多的突发数据，提高吞吐量，但TCP机制往往会保持较高的队列占用，从而增加了数据包的排队延迟。因此需路由器对队列进行管理，维持较小的队列长度。因为维持较小的队列长度除了降低排队延迟，提高吞吐量外，还能保持较大的队列空间来吸收突发数据包。拥塞控制机制就是要维持网络处于低延迟高吞吐量的状态。
当前的队列管理算法可以分为两大类：被动式队列管理（Passive Queue Management，PQM）和主动式队列管理（Active Queue Management，AQM）。
2.1 被动式队列管理及其缺陷
管理路由器队列长度的传统技术是对每个队列设置一个最大值（以包为单位），然后接受包进入队列直到队长达到最大值，接下来到达的包就要被拒绝进入队列直到队长下降。这种技术也就是所谓的"去尾"（drop-tail）算法。虽然这个方法在当前Internet上得到了广泛的使用，但其存在几个重大缺陷：
死锁（lock-out）问题：在某些情况下，"去尾"算法会让某个流或者少数几个流独占队列空间，阻止其他流的包进入队列。这种"死锁"现象通常是由于同步（synchronization）或其他定时作用的结果。
满队列（full queues）问题：由于"去尾"算法只有在队列满时才会发出拥塞信号，因此会使得队列在相当长时间内处于充满（或几乎充满）的状态。而队列管理最重要的目标之一就是降低稳定状态下队列的长度，因为端到端的延迟主要就是由于在队列中排队等待造成的。
全局同步（global synchronization）问题：由于Internet上数据的突发本质，到达路由器的包也往往是突发的。如果队列是满的或者几乎是满的，就会导致在短时间内连续大量地丢包。而TCP流具有自适应特性，源端发现包丢失就急剧地减小发送窗口，包到达速率就迅速下降，于是网络拥塞得以解除，但源端得知网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞，而且这种现象常常会周而复始地进行下去，从而在一段时间内网络处于链路利用率很低的用状态，降低了整体吞吐量，这就是所谓地"TCP全局同步"现象。
除了"去尾"机制，另外两种在队列满时进行队列管理的机制是"随机丢弃"（random drop）和"从前丢弃"（drop front）机制。当队列满时，前者从队列中随机找出一个包丢弃以让新来的包进入队列；后者从队列头部丢包，以便让新包进入队列。这两种方法虽然都解决了"死锁"问题，但仍然没有解决"满队列"问题。由于这几种方法都是在队列满了被迫丢包，因此称为被动式队列管理。
2.2 主动式队列管理及其优点
在当前的Internet上，丢包是对端节点进行拥塞通知的重要机制，解决路由器"满队列"的方法便是在队列充满之前丢包，这样端节点便能在队列溢出前对拥塞作出反应。这种方法便称为"主动式队列管理"（Active Queue Management）。
AQM是一族基于FIFO调度策略的队列管理机制，使得路由器能够控制在什么时候丢多少包，以支持端到端的拥塞控制。AQM有以下优势：
减少了路由器中丢弃的包的数量：Internet中数据包的突发本质是不可避免的，AQM通过保持较小的平均队列长度（average queue size），能提供更大的容量吸收突发数据包，从而大大减少了丢包数。进一步说，如果没有AQM，会有更多的包被丢弃，这主要是因为以下三个原因：
1) 由于使用共享的队列和PQM，会不可避免地产生全局同步，导致很低的平均带宽利用率，也即吞吐量很低。
2) TCP从突发包的丢弃中恢复要比从单个包丢弃中恢复更复杂。
3) 如果一个数据包在到达目的端之前被丢弃，则其在传输过程中所消耗的资源都被浪费，降低了网络带宽的利用率。因此，不必要的包丢弃也就意味着带宽的浪费。
对交互式服务提供了更低的延迟：AQM通过保持较小的平均队列长度，队列管理能够减少包的排队延迟（queueing delay），而排队延迟是造成端到端延迟（end to end delay）的主要原因。这对交互式应用比如Web浏览、Telnet业务和视频会议等非常重要。
避免了"死锁"现象：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
【责编:admin】
--------------------next---------------------
