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

众所周知，由于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的选择非常重要，假如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的增加，下一个包被丢弃的可能性也在缓慢增加。这主要是为了在到来的包之间均匀间隔地丢包，避免连续丢包，从而避免对突发流的偏见和产生全局同步现象。
对队列治理而言，吞吐量和排队延迟始终是一对矛盾的关系。假如平均队长能够充分权衡吞吐量最大化和延迟最小化之间的矛盾，从而在总体性能上得到较为理想的结果，则该队长称为理想的平均队长。阈值minth和maxth就是由理想的平均队长决定的。一般来说， maxth－minth应大于一个回路响应时间内平均队长的增加值，以避免由于路由器丢弃过多的包而导致全局同步。根据目前Internet上数据流的特点，可以将maxth设为minth的两倍。由于理想的平均队长依靠于不同的网络条件，因此，如何确定理想的平均队长仍是一个有待研究的问题。
3.3 显式拥塞指示（Explicit Cogestion Notifica- tion ECN ）
在RED机制中，当平均队长超过一定的阈值时便开始丢包了，也就是说RED是在队列未满的情况下丢包的，并不是由于队列溢出而被迫丢包的。在这种情况下丢包，虽然使得RED有效地治理了平均队长，但也浪费了网络资源，并且对时延有一定要求地多媒体应用不是很理想。因此除了使用丢包作为拥塞通知方式外， AQM还可以采用其它方法， ECN便是IETF建议使用地一种拥塞通知方式。
ECN需要在IP包头设置一个两位（bit）的ECN域（如图2所示），一个是ECT（ECN-Capable Transport）位，由源端设置以显示源端节点的传输协议是支持ECN的；另一个是CE（ Congestion Experienced ）位，由路由器设置，以显示是否发生了拥塞。IPv4中TOS字节的第6位被设置为ECT位，第7位被设置为CE位。IPv4中TOS字节和IPv6中的流类型字节（traffic class octet）是相对应的，它们的前六位被设置为区分服务中的（Different- iated Services）中的区分服务标记域（DS field）。后两位保留未用，因此可用来作为ECN域。
除了在IP头中设置ECN域外， ECN还需要传输协议的支持。在TCP头中需要设置两个标志位：ECN-Echo和CWR（Congestion Window Red- UCed）。ECN-Echo是接受端用来通知源端收到一个CE包；CWR是源端用来通知接受端拥塞窗口已减小。
在TCP连接建立阶段，源端和目的端TCP交换有关它们是否愿意以及是否支持ECN的信息。然后源端设置IP头中的ECT位以向网络显示其支持ECN ，因而，假如路由器需要的话，可以标记IP头中的CE位作为拥塞通知的方式。下面具体阐述ECN的工作方式。
在TCP连接建立阶段，若源端支持并愿使用ECN,则其可在SYN包的TCP头中设置ECN-Echo和CWR标志位。假如源端支持并愿使用ECN ，则其可在SYN-ACK包中设置ECN-Echo标志，但不设置CWR标志。这样当前的TCP便是支持使用ECN的。
图2 ECN工作原理
对路由器来说，假如其队列位满，并且其要对源端发出拥塞通知，那么路由器应该首先检查IP包头的ECT位是否已经设置，如是则应该设置CE位而不是以丢包作为对源端的通知信息。接着，当目的端接受到了CE包时，就会设置确认包TCP头的ECN-Echo标志，并且为了防止确认包的丢失，目的端必须在接下来一系列的确认包中设置ECN-Echo标志。假如源端收到了ECN -Echo的确认包，那么也就知道了在发往目的端的路径中发生了拥塞，因而需要将拥塞窗口减半并且减小慢启动阈值，同时在接下来要发送的包中设置CWR标志，以通知目的端拥塞窗口已减小，假如目的端接受到了CWR包，就停止在接下来的确认包中设置ECN-Echo标志。
假如路由器收到了CE包，则CE位保持不变，包的传输还和往常一样。若发生了严重拥塞，队列满了，那么路由器别无选择就只好丢包了。在现在的"延迟确认"（delayed-ACK）TCP应用中，目的端收到两个包时发送一个确认，那么只要接收到的包中有一个CE包，确认包中的ECN-Echo标志就要设置。
另外，假如在一个RTT内，源端同时收到ECN和丢包传达的拥塞指示，则只对其中之一作出拥塞反应。假如拥塞反应已经开始，则必须等到所有正在传送的数据都被确认后才能开始新的拥塞反应。
3.4 RED和ECN地结合
将RED和ECN结合起来，假如拥塞是在队列满之前检测到的，那么除了用丢包作为拥塞通知外，对支持ECN的源端和目的端，还可以采在IP包头设置CE位的方法。这样就避免了不必要的丢包，非凡是对短的TCP连接和对时延敏感的TCP连接而言；另外也避免了不必要的TCP超时重传。在下面的内容中，我们统一将上述两种方法称为"标记"（mark）。
3.5 RED的优点和存在地问题
RED在平均队长超过了最大阈值后就丢包，而不是采用诸如设置CE位之类的标记包的方法，从而有效地控制了平均队长，限制了平均时延地大小。在发生拥塞时， RED标记某个流的数据包的概率基本上和该流在路由器中得的带宽成比例。这是因为发送速度更快的流，其供随机标记的包也更多。从而消除了对突发流的偏见。RED标记包的概率依靠于拥塞水平，并且均匀地间隔丢包，避免了由于连续丢包导致地全局同步现象。总而言之， RED是IETF推荐的一种基于路由器的有效的拥塞避免机制，其和传输协议的合作能有效地控制网络上发生的拥塞。
尽管和"去尾"算法相比， RED是一种更为有效的拥塞控制机制，但其仍然有许多问题：
（1）参数设置问题：RED工作性能的优劣很大长度上是由其预先设置的参数w_Q、min_th和max_th决定的。一组RED参数也许是给定业务吞吐量的最优化参数，但对于连续丢包、延迟等就未必是最优参数了。因此如何权衡它们（吞吐量、延迟等）之间的关系，从而找到一组最优的参数仍然是有待进一步研究的问题。另外， RED参数的微小的变化会给总体性能带来很大的影响。一组RED参数也许在特定的业务环境下表现非常好，但由于Internet 是动态变化的，当流的数量及负荷的改变导致业务环境的变化时，则该组RED参数也会就会给拥塞治理带来非常不利的影响。
（2）不能有效估计拥塞的严重性：
图3 一个RED队列治理的例子
图4 理想的队列治理算法工作情况
基于"去尾"机制的TCP拥塞控制的一个很大问题就是从路由器丢包开始，到源端检测到丢包，需相当长时间。在这段时间里，源端继续以原速或更高的速度发送数据，从而导致更多的包被丢弃。RED通过检测早期的拥塞从而减轻了这个问题。但RED必须配置足够的缓冲区来容纳从检测到拥塞到瓶颈链路负荷开始下降这段时间到达的数据包。RED还要确保送出的拥塞通知信息的速度充分降低了源端的发送速度而不是降低了链路利用率。但当有大量的活跃的TCP（active TCP connections）连接时，总的流量往往突发性非常高，队长的增减非常迅速，而RED还没有来得及作出很好的行动。图3显示了在这种情况下RED是如何工作的。在从t=1开始发生拥塞，直到t=7负荷才小于链路容量，在这之间由于总的流量的突发性，就会有大量包被丢弃或被ECN标记，从而降低了链路使用率。图4显示了理想的队列治理算法是如何工作的，其传递拥塞指示的速度刚好使得总的源端的发送速度等于或略小于瓶颈带宽。
要解决这个问题， RED不仅需要正确的参数配置，还需要足够大的缓冲区，比如缓冲区是带宽延迟积的两倍。但假如带宽延迟积很大，又会大大增加端到端的延迟。而且对那些已经在使用的，存储器不是很大的路由器也无法用此方法解决。
（3）和"去尾"算法相比， RED消除了对突发流的偏见，但它并不是通过降低突发流的丢包率来实现的，而是通过增加非突发流的丢包率来消除这种偏见的。
（4）由于权重w_Q很小，因此平均队长的变化很小。当负荷很重时，平均队长总是在max_th四周缓慢地振动，从而会导致长时的连续标记包（avg_Q>max_th）或者长时连续随机地标记包（avg_Q< max_th），产生全局同步现象。也由于此原因，尽管RED减小了平均时延，但却增加了延迟抖动。
（5）公平性问题：我们知道，不同的RTT、拥塞窗口的大小、包的大小、目标速度以及TCP/UDP的相互作用都会影响TCP流对带宽的享用。由于Internet上数据流是异质的，而RED标记包的概率是和该流使用的带宽成比例的，这就会带来不公平的带宽使用。例如两个TCP流竞争带宽，一个使用小窗口，另一个使用大窗口，发生拥塞时， RED就会使得小窗口的源端陷入多重超时。另外，由于UDP之类的流没有拥塞控制机制，其在和TCP-friendly流竞争时会获得更多的带宽，有可能使后者陷入"饥饿" 。
由于RED存在着诸多问题，导致了其它AQM算法的产生。这些AQM算法主要有：SRED、FRED、ARED和BLUE等，由于篇幅的原因，我们对这几种算法的原理和性能进行具体分析。