第六章 拥塞控制

6.1 拥塞和流量控制概论

在计算机网络中，链路的容量、交换节点中的缓冲区和处理机等都是网络的资源。在某段时间内，若对网络某一资源的需求超过了该资源所能提供的可用部分，网络的性能就会恶化。同时，如果信息流无限制的进入网络也会导致网络的性能恶化。当报文在网络中经历了比所期望的时延更长的时间时，就认为网络产生了拥塞。当网络发生拥塞时，只能有很少的信息流动，而且拥塞会很快的延伸，甚至导致“死锁”。发生死锁时，网络中几乎没有分组能够传送。因此，如果对网络的拥塞不加控制，网络的性能将会迅速下降。

造成网络出现拥塞有若干种原因。
例如：
当从多个输入端到达同一节点的分组要求同一条输出链路时，就形成分组的排队。如果该节点的缓冲器容量不够，就会造成分组丢失。在某种程度上增加缓冲器的容量可以减少这种由于缺少缓冲容量而造成的分组丢失率；

同时，如果处理器的处理速度太低，或者链路带宽不够也会导致拥塞；

另外，拥塞节点本身也会使拥塞变得更严重。因为如果节点没有空闲的缓冲区，那么新到达的分组必定被丢弃，而发送端会因为等待应答超时而重发，甚至重发若干次，这必然会增加网络的负荷，使整个网络中节点的缓冲器逐渐地都将处于饱和。随着网络负荷的激增，吞吐率骤降，最后达到零值，导致网络进入死锁状态.

6.1.1网络数据流的控制技术分类

网络数据流的控制技术可以分为3类，即流量控制、拥塞控制和死锁防止。
1.流量控制
流量控制是对网络上的两个节点之间的数据流量施加限制。它的主要目的是让接收端来控制链路上的平均数据速率，以满足接收端本身的承受能力，以免过载。

2.拥塞控制
拥塞控制的目的是将网络内（或网络的部分区域内）的报文分组数目保持在某一量值之下，超过这一量值，分组的平均排队时延将急剧增加。因为一个分组交换网络实质上是一个排队的网络，每个节点的输出链路端口都配置一个排队队列，如果分组到达的速度超过或等于分组发送的速度，队列就会无限制地增长，致使分组平均传输时延趋于无穷大。如果进入网络的分组数目继续增加，节点缓冲器将会占满溢出，丢失一些分组。丢失分组的后果是导致发端重发。重发实际上又增加了网络内流通的业务量，最终可能使所有节点缓冲器都被占满，所有的通路完全被阻塞，系统的吞吐率趋于０。

3.死锁防止
网络拥塞到一定程度时，就要发生死锁现象。死锁发生的条件就是在构成一个封闭环路上的所有节点的相关链路缓冲器都被积压的报文分组所占满而失去了节点所担负的存储转发能力。即使在网络轻负荷情况下，也可能出现死锁的现象。死锁防止技术旨在合理地设计网络使之免于发生死锁现象。

6.1.2拥塞控制的基本原理

拥塞控制的基本原理是：寻找输入业务对网络资源的要求小于网络可用资源成立的条件。这可以通过增大网络的某些可用资源（如输入业务繁忙时增加一些链路，增大链路的带宽，或使额外的通信量从另外的通路分流），或者通过减少一些用户对某些资源的需求（如拒绝接受新的建立连接的请求，或者要求用户减轻其负荷，这属于降低服务质量）。

闭环控制是建立在反馈控制的概念之上，其控制过程有以下几种部分：
（１） 实时监测网络，以便监测到拥塞在何时、何处发生；
（２） 将拥塞发生的信息传送到可采取行动的地方（如控制中心）；
（３） 调整系统的操作过程，以便纠正拥塞问题。

6.1.3 流控和拥塞控制所经历的层次

流量及拥塞控制可以出现在所有的协议层次上，不过主要还是在数据链路层、网络层和传送层；分段（逐跳）流控是数据链路层的功能，称为节点到节点之间的流控；而端到端流控主要在传送层，称为全局流控；拥塞控制则主要集中在网络层。影响拥塞控制的一些主要策略如表６－１所示。

6.2 流量和拥塞控制技术

流量和拥塞控制技术按执行流控和拥塞的方式可分为：集中式和分布式流量拥塞控制。

在集中式流控中，网络中有一个特定的网控节点执行某种算法，为各个节点计算报文流量的分配值，然后将新的流量分配值传送给所有其他网络节点。
而分布式流控则是把管理网络的流量过程分配到若干个网络节点来完成，这些节点控制通过其自身或外部的业务流量。

流量及拥塞控制有许多具体的实现方式，下面将着重讨论窗口式流量拥塞控制和漏斗式流量控制算法。

6.2.1 窗口式流量和拥塞控制

窗口式流控的思想类似于数据链路层的返回ｎ－ ＡＲＱ，在一个session中，发端Ａ在未得到收端Ｂ 的应答情况下，最多可以发送Ｗ（窗口大小）个消息或分组或字节。收端Ｂ 收到后，回送给发端Ａ 一个permit（它既可以是应答，也可以是分配消息），Ａ 收到后方可发送新的数据。下面首先介绍一下在窗口式流控中应该注意的问题，然后再集中讨论具体的窗口式流控算法。

1.滑动窗口控制机构的建立

通信子网中的任意节点对之间都可能构成源／目的节点对。若子网的节点数为ｍ，则一个节点可能与其他ｍ－１个节点结合，最多形成ｍ－１个源／目的节点对。如果在一个节点内为每一个源／目的节点对常设一个滑动窗口控制机构，将使节点控制机构变得相当复杂，占用许多的缓冲存储容量。减少这种复杂性的途径就是采用动态方法：在每个节点中只为有当前通信业务的源／目的节点对设置窗口控制机构，并相应地分配缓冲区。每一个源／目的节点对实际上就是一条虚拟的线路。可见，窗口控制机构应当随着每一条虚拟线路的建立而建立，这与为每一条数据链路建立一对滑动窗口控制机制是一样的。

2.窗口宽度的确定

一个源节点可能与许多不同节点构成源／目的节点对。如果源／目的节点对之间的距离比较远，则相应的两个节点之间的端到端时延就比较长，从源节点发出一个分组到它收到应答期间连续发出的分组数会比较大。因此，为了有效地利用通信子网的传输能力，这时源／目的节点对之间的窗口宽度Ｗ 就应当比较大。相反，源／目的节点对之间跳数比较少的节点对之间的窗口宽度Ｗ 就应该相应的小一些。

可见，窗口宽度应当根据源／目的节点对之间的距离来选择，而不能简单地选成一样大小。为此，可以在每一个源节点内设置一张说明窗口宽度和节点距离关系的对应表。根据这种对应关系，动态选择合适的窗口宽度，以便建立起相适应的窗口控制机制。

理想的窗口宽度应当这样选择：源节点从发送第一个分组到收到目的节点对该分组的确认时，源节点的窗口控制应该刚好发完窗口宽度允许的最后一个分组。这种情况下，源节点就能以最佳的速率不间断的发送分组。

3.报文的重装

当目的节点全部收完一个报文的所有分组后，才能着手重装报文，然后再提交给目的主机。这是，该源目的节点对上的一个报文才算传输成功，目的节点将给源节点返回一个确认应答。可见，端到端流控功能中还包括在目的节点进行报文重装的功能，特别是当通信子网采用自适应型路由策略和采用网内数据报传输方式时报文重装的功能尤其重要。在这两种情况下，源节点发出的报文分组可能沿不同的路径到达目的节点，因而造成分组到达的次序与发送次序可能不一致。如果某一分组在中转过程中丢失，在目的节点将无法将报文重装出来。此时，目的节点应在返回的应答中报告这一情况。源节点在确知后，应立即重发被丢弃的那个分组。为此，源节点缓冲区必须保留全部未应答的数据分组，以便在需要重传时使用。

下面讨论具体的窗口式流控技术。

1. 端到端的窗口流控

Ｗ：窗口大小，即流控窗口为Ｗ 个分组，如果收端希望收到的分组序号为ｋ，则发端可以发送的分组序号为ｋ～ｋ＋Ｗ－１的分组。
ｄ：分组传输的来回时延，它包括来回的传播时延、处理时延、分组传输时间、应答分组的传输时延。
Ｘ：单个分组的传输时间。

在图６－５（ａ）中，ｄ≤ ＷＸ，则发端可以以１/Ｘ（分组／秒）的速率全速发送，流控不会被**。而在图６－５（ｂ）中，ｄ＞ ＷＸ，在ｄ 时间内，最多只能传送Ｗ 个分组，即分组传输的速度为Ｗ/ｄ(分组／秒）。显然，对于给定来回时延ｄ，最大的分组传输速率ｒ为:

其结果如图６－６所示。从图中可以看出，ｄ增加表明网络中拥塞增加，这样会导致分组传输速率Ｗ/ｄ下降。如果Ｗ 较小，则拥塞控制反应较快，即在Ｗ个分组内就会作出反应。这种以很小的开销获得的快速反应是窗口流控策略的主要优势之一。

请看例题

2. 虚电路中逐跳窗口流控

虚电路中逐跳窗口流控（node-by-node windows for virtual circuits）是在虚电路经过的每个节点中保留Ｗ 个分组的缓冲区。在该链路上的每一个节点都参与流控，每一条链路的窗口都为Ｗ，每个接收分组的节点可以通过减缓回送允许（应答）分组给发送节点的方式来避免内存中积压太多的分组。在这种方式下，各个节点的窗口或缓冲区是相关的。假定虚电路是经（ｉ－１）→ｉ→（ｉ＋１）等节点，当节点ｉ缓冲区满时，只有当节点ｉ向节点ｉ＋１发送一个分组后，ｉ才可能向ｉ－１发送一个应答分组。这样就会导致ｉ的上游节点ｉ－１缓冲区满，依此类推，最后将导致源节点的缓冲区满。这样从拥塞节点缓冲区满返回到源节点缓冲区被填满的现象被称为反压现象（Back pressure）。