控制网

 

        在因特网上，当一个子网或者其中的一部分出现太多分组时，网络的性能开始下降，诸如网络延时加大、丢包率上升、吞吐量下降等，这种情况即称为拥塞（congestion）。导致拥塞出现的原因通常是当前的负载（临时性地）超过了（网络中的某一部分）资源的处理能力，或者说用户提供给网络的负载大于网络资源的容量和处理能力，如网络相对于负载需求表现为节点存储空间不足、链路带宽不足、处理器处理速度慢，以及系统各部分性能不匹配等等，从而导致网络上的包时延增加，丢包率上升，吞吐量下降，直接使服务质量下降。在处理网络的拥塞问题时一般采用两种方法：一是采取措施预防网络拥塞，也就是采取流量控制技术；二是采取措施减少已拥塞时的拥塞程度，即减少拥塞时间以及防止拥塞扩散，直至拥塞的消失，也就是采取拥塞控制技术。

        拥塞控制的任务是确保子网能够处理承载所到达的流量，这是全局性的问题，涉及各方面的行为，包括所有的主机、路由器及内部的存储转发过程等；流量控制只与特定的发送方和接收方之间的点到点流量有关，它的做法是接收方向发送方提供某种直接的反馈以通告发方另一端的情况，使发方动态调整发送速率，以确保一个快速的发送方不会持续地以超过接收方能力的速率传输数据。流量控制和拥塞控制之间的关系是：有些拥塞控制算法在网络出现拥塞时，通过往各个源端发送消息来通知它们减缓发送数据的速度，可见流量控制只是实现后者的一种技术实现途径。

 

 

        在计算机网络这样复杂的系统中可以用控制论的角度来看待拥塞控制的解决方案：开环的和闭环的。开环的解决方案试图用良好的设计来解决问题，其本质是从一开始就保证问题不会发生，手段包括：确定何时接受新的流量、确定何时丢弃分组及丢弃那些分组，以及在网络的不同点上执行调度策略，这些手段在作出决定的时候不考虑当前的网络状态；闭环的解决方案则恰恰建立在反馈环路的基础上，这种方法可以分为三个部分，即监视系统检测到何时何地发生了拥塞，将该信息传递到能够采取行动的地方，调整系统的运行以改正问题。监视子网的拥塞状况时可以采用多种度量标准，包括因缺少缓存而丢包的百分比、平均队列长度、平均分组延迟等；闭环方案的第二部分可以有多种实现方法，一种方法是检测到拥塞的路由器给流量源发送一个分组通告以拥塞的发生，另外也可以在每个分组中保留一位或一个域用以标志拥塞。为了使收到拥塞信息的主机能采取适当的行动，必须谨慎选择地时间尺度，选取一个合理的平均值。

        当前存在很多拥塞控制算法，总体可以分为开环算法和闭环算法两大类。开环算法中一类在源端采取行动，另一类在目标端采取行动；闭环算法分为显式反馈和隐式反馈，其中显式反馈从拥塞点向源端发送分组以警示源端，隐式反馈中源端利用本地观察到的现象如分组往返时间来推断拥塞的发生。目前在Internet上实际使用的拥塞控制基本上是建立在TCP层的窗口控制基础之上的，即基于窗口的端到端的闭环控制方式, IP层的拥塞控制主要在网络中间节点如路由器上及链路上实施资源控制，IP层所起的作用相对较小。

 

 

         TCP的拥塞控制采用的是基于窗口的端到端的闭环控制方式。目的节点正确地接收到包后将向信源发出确认（ACK）信息。每个信源有一个大小可变的窗口，使用窗口大小来确定还没有收到确认信息的包的数量。当窗口已满，信源在发送一个新包前必须等待一个确认信息。TCP算法有两个重要特征：一个是“自定时”特征，当网络出现拥塞且确认信息出现延迟时自动放慢信源的发送速率；另一个是使用窗口大小来控制信源速率，大约每个往返时间发送一个窗口的数据包。TCP拥塞控制由慢启动（slow start）、拥塞避免（congestion avoidance）、快速重传（fast retransmit）和快速恢复（fast recovery）四个核心部分组成。TCP使用的是加式增加积式减少（AIMD）的基于窗口的端到端的拥塞控制机制，即如果一个数据包丢失，发送窗口就要减半；否则就简单的增加一个数据包的发送量。大量的实践证明，这种拥塞控制机制对Internet上大批量文件传输等尽力型（best-effect）服务具有较好的适应性。

         TCP Tahoe 算法主要分为两个阶段：慢启动和拥塞避免，在TCP建立连接时，为发送方增加一个拥塞窗口（cwnd）用以控制发送包的数量,并设置一个慢启动阈值            （ssthresh）用以判定从慢启动状态切换到拥塞避免状态。一开始，拥塞窗口设置为1，发方发送一个报文段，并启动定时器，在超时之前收到一个收方应答响应ACK，则cwnd相应增加一个报文段大小变成2，以此类推cwnd按照1,2,4,8……的指数规律增长。如果出现响应超时或连续收到3个以上的重复ACK，则停止继续增加cwnd，将ssthresh设为当前cwnd的一半（最小为2），如果是超时的情况则将cwnd重新置为1，否则cwnd不变。算法中比较cwnd与ssthresh，当cwnd比ssthresh大时将进入拥塞避免阶段，即每收到相应ACK时对cwnd只按照线性规律增加1/cwnd，直到cwnd过大，发包数量相对网络当前承载能力过多，重新导致超时或重复ACK。当cwnd不大于ssthresh时，则进入慢启动状态。

        Reno 算法对Tahoe算法作了改进，增加了快速重传/快速恢复机制，即在接连收到3个重复ACK时就断定丢包，进入快速重传阶段，而无需等待定时器超时，接下来执行的是拥塞避免算法而非慢启动，这就是快速恢复。当收到第3个重复的ACK时，将ssthresh设置为当前拥塞窗口cwnd的一半，重传丢失的报文段。然后再改变cwnd的当前值，将其设置为ssthresh加上3倍的报文段大小，此后每收到另一个重复的ACK，就将cwnd增加1个报文段大小并发送1个分组（如果新cwnd允许发送）。当下一个确认新数据的ACK到达时，设置cwnd为ssthresh。这个ACK是进行重传后的一个往返时间内对丢失报文段重传的确认，也是对丢失的分组和收到的第1个重复的ACK之间的所有中间报文段的确认。这一步采用的是拥塞避免，因为当分组丢失时，将当前的速率减半而不是置为慢启动初值。

        Vegas对Reno进行了三项改进：首先采用新的重传触发机制,即只要收到一个重复的ACK就断定超时，以便及时检测到拥塞；而在慢启动阶段则采用了更加谨慎的方式来增加cwnd,以减少不必要的分组丢失；改进“拥塞避免”阶段的窗口调整算法，通过观察以前的TCP 连接中RTT值改变情况来控制拥塞窗口cwnd , 当RTT变大时就认为发生拥塞, 开始减小cwnd，如果RTT变小,就增加cwnd，解除拥塞，理想情况下cwnd就会稳定在一个合适的值上。 这样使拥塞机制的触发不再依靠包的具体传输时延，而只与RTT的改变有关。

 

 

        TCP拥塞控制机制本质上是端到端的控制机制，它默认为IP层对拥塞的发生和拥塞的控制不进行任何支持。当前随着Internet业务的迅猛发展，仅依靠单一的端到端的拥塞控制机制不可能有效地解决拥塞问题，另外期望所有用户在Internet应用中都遵守这种端到端的拥塞控制也是不现实的，这要求网络本身也必须参与对资源的管理与控制。基于此，提出了在路由器中采用排队算法和数据包丢弃的策略，即IP拥塞控制机制。

        FIFO 即“先到先服务”，意指先到达路由器的数据包就先被传输，如果缓存已满则丢包。优先级排队对基本FIFO排队进行了简单改进，它为每个数据包分配一个优先级标志，在路由器按照不同优先级进行多个FIFO排队，非空的最高优先级队列优先发送，同一优先级队列内仍然是FIFO方式。由于高优先级队列会“抢占”所有其它的队列，因此用户不能用不受控的方式为自己的数据包指定高的优先级。一些重要的报文如路由更新包往往采用优先级排队的方式，其优先级由IP包头的TOS域定义并由一个特殊的队列保存, 这其实是区分服务思想的一种实现。

         RED算法在路由器监控队列长度, 一旦发现拥塞迫近, 就通知源端调整拥塞窗口。 它也是通过丢包的方式使源端发现超时或重复应答，隐式通知源端拥塞情况。RED算法包含两部分：如何监控队列长度和何时丢弃数据包。首先, RED使用类似TCP计算超时时使用的权值Weight来计算平均排队长度Qe=(1-Weight)×Qe+Weight×SampleQe

        其中，0< Weight< 1, SampleQe是采样测量时的排队队长。使用平均队长比使用瞬时值更能精确“捕捉”拥塞情况。RED丢弃数据流中包的概率与这个流在路由器中所获得的带宽成比例,因为一个发送数量相对较大的数据流可供随机丢弃的数据包的数量也相对较多。因此在RED算法中需要考虑公平性。

         ECN算法在源端数据包中嵌入ECN, 由路由器根据网络情况设置CE (Congestion Experienced) 比特位，源端从网络中接收反馈回来的已被CE置位的数据包, 再将随后发出的数据包标记为“可丢弃”的数据包。改进算法NewECN可通过调整拥塞窗口cwnd大小, 纠正了有长时间RTT的TCP 连接的偏差, 改进了共享瓶颈处带宽的公平性。

        在FQ算法中, 路由器的每个输出链路(outputline)都对应一个排队队列，对它们按“轮询”( round robin)方式处理。当有某条输出链路空闲时, 路由器就顺次扫描所有队列, 将每队第一个包发出。 当某个流的数据包到达过快时, 其队列就会很快占满, 属于这个流的新到的包就会被丢弃。 采用这种方式, 每个数据流就不可能牺牲其它数据流而额外占用资源。FQ算法并没有告知源端路由器状态的机制, 也就是说, FQ仍然要依赖于端到端的拥塞控制机制。它只是将数据流分隔, 使不遵守拥塞控制机制的数据流不至于影响其它流。所以它在没有牺牲统计复用的情况下提供了公平性, 与端到端的拥塞控制机制也可以较好地协同。由于数据包是变长的, 所以为了在输出链路上公平分配带宽, 必须考虑包的大小。

       它是FQ的改进算法。WFQ对每个流即每个排队分配一个权值。这个权值决定了路由器每次转发该队列的比特数量, 从而控制数据流得到的带宽。将所有权值看成1, 那么FQ也是一种特殊的WFQ。权值的分配往往对应不同优先级的数据流,例如用IP包头中TOS域指定流的优先级, 排队时再按优先级分配权值。这也是区分服务的思想。权值可以由路由器自己决定, 也可以由源端通过某种信令通知路由器来决定。 总之,WFQ 根据不同数据流应用的不同带宽要求, 对每个排队队列采用加权方法分配缓存资源, 从而增加了FQ对不同应用的适应性。

 

        按照拥塞时包丢弃的方式，可以将拥塞控制策略分成3种类型：一是混合式, 即在路由器中不管是哪种数据流, 其优先级如何, 均共同排队处理, 共享同一路由器资源, 如FIFO，RED等；二是分离式,各数据流在路由器中单独排队,如FQ；三是基于部分缓存共享方式，根据缓存大小设置一个阈值来控制包丢失率。 当缓存达到或超过给定阈值时,只有高优先级数据包才能进行缓存, 低优先级数据包则被丢弃，当缓存满时, 高优先级数据包也被丢弃。

        FIFO的主要问题是无法区分不同的数据流,它对拥塞控制不起作用，主要由TCP进行拥塞的检测和响应。RED 设计的出发点是怎样与TCP拥塞控制有效配合。对面向连接的TCP数据流来说, RED有可能避免丢弃属于同一连接的连续数据包, 从而提高连接的吞吐量。在路由器上运行RED可以更精确地管理队长，其最优队长取决于各种数据流的特性。ECN不依赖于重传超时和粗粒度的TCP定时, 对有一定时延要求的应用效果较好。TCP在源端进行拥塞控制, 传统的FIFO排队不提供约束所有数据源遵守拥塞控制的机制, 这就有可能让行为不良的数据流强占大量带宽。针对此提出了FQ算法即公平排队法，可以解决这个问题。

 

         以上对当前Internet上实行的各种基于TCP/IP的拥塞和流量控制算法原理进行了总体概述，分析、比较了这些算法的基本性能的优劣。TCP协议通过窗口机制，以丢包率或排队时延作为拥塞的度量，进行拥塞控制；在整个因特网上，通过分布式的对单个信源传输速率进行调整，进行流量控制；而流量控制是拥塞控制的一种有效手段，目的是避免链路容量过载，保证服务质量，并使网络资源得到充分的利用。拥塞/流量控制算法的自相似问题、稳定性、效率问题以及公平性问题都是有待进一步研究和改进的问题，另外，如何在IP层实现拥塞控制以更有效地解决拥塞问题及多点广播中的拥塞控制等是目前研究的热点。