跳跃级拥塞控制：计算机网络原理中的实践

跳跃级拥塞控制的目标是防止存储转发缓冲器拥挤以及由此引起的吞吐量下降和死锁。跳跃级控制以本地的“近视”的方式工作，由它监视着每一条通向其它结点线路上的队列和缓冲器的占用率，当其超过某些预先规定的阈值（如最大队列限制）后，将丢弃那些到达本结点进行存储转发的分组。这种放弃分组的方法，可以将某处的拥挤向信源处疏散一些。

存储转发拥塞将导致两个不良的后果——吞吐量下降和死锁。导致吞吐量下降的主要原因是网络资源的浪费。这种浪费既可能是由于两个或更多个用户请求的冲突造成的资源不稳定而引起的，也可能是由于某用户得到的资源多于它的实际需要，从而造成其它用户资源的缺乏而引起的。结点的有限存储容量可能会间接地造成缓冲器的浪费。例如，当一个分组在流向终点的途中到达某个中间结点时，若该结点的所有缓冲器被其它的分组所“霸占”，那么即使该分组沿着流动的路线的通信容量足够大，堵塞仍可能发生，从而引起吞吐量的不必要下降。某些用户对结点缓冲器不必要的垄断，如用虚电路预约了缓冲器，但又长期既不使用又不关闭该虚电路，将导致通信无法进行，如图5.3.3所示。

死锁表现为网络的全部或局部崩溃，通常是由于用户循环地等待着可得到的资源而引起的。当一个用户已拥有当前所需资源的一部分，但还在等待第二个用户释放所需的另一部分的资源时，若此时第二个用户也正等待着第三个用户释放这一部分资源，……于是一个接一个处于“等待”的用户闭合成为一个环，使环上的任何一个用户都无法前进，从而用户集的吞吐量下降为0，如图5.3.4（a）所示，当A，B两个结点互相期待对方释放缓冲器时，若A中的5个缓冲器全部装上了向B传送的分组，而B中的5个缓冲器又全部装上了向A传送的分组，则将因为没有多余的缓冲器致使死锁——谁也无法从对方接收报文，也无法释放已占用的缓冲器。这种死锁称为直接存储转发死锁。多个结点构成等待环引起的死锁则称为间接存储转发死锁。

图5.3.3　AA'垄断了缓冲器，使BB'无法通信

图5.3.4　存储转发死锁

须强调指出的是，只有被丢弃的报文分组要被CCP重发的网络（即当前向通路的下一个CCP结点传输分组时，每个结点留有该报文分组的副本，并在超时后重发该副本），才有可能造成存储转发死锁。如果被丢弃的分组在各结点不需重发，而将重发的任务留给端点或主机，各个结点就无需在下一结点接收该分组之前一直保留它的副本，从而产生死锁的必要条件也就不存在了。因此，数据报结构的子网不会产生这种死锁。

下面简要介绍几种跳跃级拥塞控制的方法。

1、信道队列限制法（Channel Queue Limit，CQL）

所谓信道队列限制法是指：将结点内的分组按其要输出的方向，在相应输出线路上排队，并对每一输出线路上的输出分组的数目规定某个限制（固定的或可动态调整的），凡超过此限制的分组均被丢弃。

若不对输出线路上的输出分组数（又称为输出队列长度，即所占用的缓冲器数）加以限制，则全部缓冲器可能被某一输出队列垄断，导致存储转发死锁。根据缓冲器的分配办法，或说根据对各输出队列长度的限制，CQL可有以下几种方案。

（1）完全分配（Complete Partitioning，CP）

此方案将所有缓冲器平均地分配各队列，故各队列可占用的缓冲器相同，允许的最大队列长度也相同。此方案对各输出队列是公平的，但因任何队列都不能借用其它队列空闲着的缓冲器，故效率不高。若设N为输出队列数，ni为第i个队列中的分组数，B为缓冲器总数，则此方案对队列的限制可表示为

0 ≤ ni≤ B/N，　i=1，2，…，N

（2）共享最大队列（Sharing with Maxmmum Queues，SMXQ）

此方案不是将所有缓冲器都分配给各队列，而是留出部分缓冲器供各队列共享，故各队列可占用的缓冲器不同，且可超过平均数B/N，允许的最大队列长度也可超过B/N，但各队列长度之和仍须小于缓冲器总数。此方案允许队列长的输出线路在一定范围内向队列短的线路（空闲线路）借用一些缓冲器，从而提高效率。若设bmax为允许的最大队列长度，则此方案对队列的限制可表示为

此方案中的bmax是一个须仔细选择的参数。最优的bmax实际上是平均通信量的复杂函数。虽然CCP可随通信量的变化不断地调整bmax，但对于突发的通信量变化，这种调整难以奏效。Irland提出了一个相当好的经验公式

(www.xing528.com)

（3）共享最小分配（Sharing with Minimum Allocation，SMA）

与SMXQ不同，此方案仅给各输出线路分配其所必需的最少（最低限度的）缓冲器。用SMA的提出者Kammou的话来说，这叫防止“饿死”每条线路。由于此方案为各线路都分配了一定数量的缓冲器，故可保证各线路上的信息流动。若设bmin为分配给每个队列（线路）的最小缓冲器数，且bmin＜B/N，则此方案对队列的限制可表示为

与SMXQ类似，此方案中的bmin是一个须仔细选择的参数，但不会等于0.

（4）共享最小分配及最大队列

此方案是SMA与SMXQ的结合，其既保证为每个队列提供所必需的最少缓冲器，又允许最大队列长度大于B/N（但各队列长度之和须小于B），从而为防止吞吐量下降，公平使用缓冲器及防止直接型存储转发死锁提供了双重保护。这是CQL各方案中最好的一个，ARPANET中采用的就是这种方案。

虽然通过丢弃报文分组的方法可一定程度地防止吞吐量下降等不利情况的产生，但重发被丢弃的报文分组毕竟要浪费一定的资源，所以报文分组的丢弃应遵循一定的原则。一般说来，因数据报子网的端点能控制重发，故允许数据报子网丢弃报文分组，而虚电路子网仅允许丢弃哪些被子网内某结点存储并能适时重发的报文分组。在必须丢弃报文分组时，应首先丢弃只传了很近距离的分组而尽量保留哪些已传了很远距离的分组，尽量不丢弃应答分组或至少给该分组进行处理的最小空间。

图 5.3.5　ARPANET的缓冲器分配方案

事实上，输入缓冲器的分配问题与输出缓冲器的分配问题是类似的，而且输入、输出和重装缓冲器都是先分配一定数量的缓冲器，余下的缓冲器依据需要进行动态共享分配。图5.3.5给出了ARPANET的缓冲器分配方案。

2、结构式缓冲池法（Structured Buffer Pool，SBP）

用CQL法来防止发生直接型存储转发死锁是有效的。这是因为对缓冲器的分配保证对方可以接收本方发去的分组，因而就不会产生互相等待资源的现象，发过去的分组也就不会再次排入发回来的队列之中，它或从别的输出线路出去，或送交主机。但是，用CQL法却不能防止发生间接型存储转发死锁。图5.3.6就是一种间接型存储转发死锁的例子。若假设图中所示的环形拓扑中，不适宜的信息量条件导致每个队列都被Qmax个报文分组所填满，这里Qmax是由CQL法所加的限制；设每个结点上的报文分组，都是向两三个跳跃以外的结点转发的，例如在AB链路上排队的分组都是到C去的。这时，因为进入的分组都无法进入继续沿环转发的队列，也就无法使发出该分组的结点中的队列腾空，从而造成互相牵制的循环“等待”局面，使任何信息量都不能在该环中传送。即使该网中具有CQL控制，也无法打破各个队列均长到最大值的局面，所以CQL无法防止间接型存储转发死锁。

图5.3.6　间接型存储转发死锁一例

结构式缓冲池法能防止间接型存储转发死锁。这种方法将进入结点的每个报文分组根据它们已经经过的跳跃数来分级。例如，从主机进入结点的分组属于该结点的第0级分组，因为它们还未经过任何的跳跃；在网络中已经历过Hmax次跳跃的分组为第Hmax级分组。这里Hmax是网络中最长的通路跳跃长度，即最长路径，它是拓扑和路由选择算法的函数。这种方法将各个CCP中的缓冲器以分组为单位分级，并从0至Hmax分别编类号，且规定哪一级的分组只能进入哪一级（即哪一号）的缓冲器，超过Hmax个跳跃的分组将被丢弃。这实际上是建立了一个缓冲器有向图，也即将缓冲池进行了结构化处理。

由于主机发出的分组为0级，所以只能进入0级缓冲器。当该级缓冲器中有别的分组时，该分组须待其空闲后方可进入。分组在子网内的传输过程中，每经过一个跳跃，都要长一级，其所进入的缓冲器的级数也逐渐升高。一般地讲，某CCP的i级缓冲器中的分组能继续传输的条件是，路由选择算法所选的下一个CCP中（i+1）级缓冲器为空。注意，对缓冲器的编号分级不受所选路由算法的限制。在传输过程中，若分组到达了目的地，则被从子网中移出，若到达某一结点中的Hmax级缓冲器后仍未到达目的地，则将被丢弃，以防止它在子网中绕圈子。

要证明此方法是无死锁的，只需要考虑瞬间所有Hmax级缓冲器的状态即可。它们只能处于下述三种状态之一：空闲、存有到达了目的地的分组及存有还未到达目的地的分组。因第二种状态中，分组将向主机交付，而第三种状态中，分组按规定要丢弃，故这三种状态都可以使Hmax级缓冲器腾空。Hmax级缓冲器的腾空就意味着（Hmax-1）级缓冲器中的分组可以继续下移，也就意味着（Hmax-2）级缓冲器中的分组也可以继续下移。如此下去，就得知所有级缓冲器中的分组都可以继续移动，而不会死锁。如果路由算法可以保证分组不在网内兜圈子，那么所有的分组都可以被正确投送到终点而不必丢弃。仔细研究会发现，SBP法不仅可以防止间接型存储转发死锁，且可防止直接型存储转发死锁。

还有一种SBP法，它规定第i级的分组可以使用第i级及以下各级的缓冲器。当一个分组进入时，将首先判别其为哪一级分组，若为i级分组，则先将其送入第i级缓冲器中，若第i级缓冲器不空，就依次送入第（i-1）级，第（i-2）级，…，直至有空缓冲器时为止。这样，级别越高的分组获得缓冲器的机会愈大，而由于得不到缓冲器被丢弃的机会就愈小。可以证明，它也是可以防止死锁的，此处不再赘述。