入口出口级拥塞控制-计算机网络原理

图5.3.7　入口出口的概念

入口出口（Entry—To-Exit，ETE）级拥塞控制的主要目标是，防止由于远地的信源以比接在出口结点的主机的接收速率还要高的速率送出分组而造成的出口结点处的缓冲器拥挤。产生这种问题的原因既可能是出口结点与主机的通信过负荷，也可能是主机的接收速率太低。当出口结点还必须把报文分组重装成完整报文或把报文分组传送到主机前必须重新排序时，防止出口结点（即目的CCP）处拥塞的问题变得更加复杂。由于这种拥塞主要产生在出口结点，故将控制这种拥塞的方法称为入口出口级拥塞控制。这种拥塞控制是一种端—端控制，故要通过入口和出口的协调，才能完成。

入口出口级拥塞控制不仅要进行端—端流控，还要防止发生死锁。可能发生的死锁有重装死锁和重排序死锁两类。因此对它们也要有特殊的预防措施。

为了研究解决这些死锁，首先要分析产生重装死锁及重排序死锁的原因。重装死锁可以用图5.3.8来说明。假设报文在CCP的网络层中组装，存储转发结点1、2、3有三个多报文分组的报文A、B、C朝着主机1的方向传送，最大报文有四个报文分组，每一结点上有四个分组缓冲器供装配报文使用，且跳跃级信道队列限制Qmax=4.从图中可以看出：因为分组A2未到，故报文A不能送往主机；因为结点2的队列已满，故A2不能送往结点2；因为结点3没有报文B和C重装的地方，故结点2的队列也不能前进，发生了死锁。

图5.3.8　重装死锁（假设报文在CCP组装）

和重装死锁十分类似，重排序死锁可用图5.3.9来解释。设一个有序的分组序列通过一个三结点的网络从主机2朝主机1传送，由于必须按顺序送达，故在分组A被接收以前，不能接收B、C、D、E.由于结点2的存储转发缓冲器已被占满，故A到不了结点3，即发生了死锁。

图5.3.9　重排序死锁

虽然入口出口级控制的主要目标是防止出口结点的拥挤，但其同时也可防止全局（即子网内部）的拥挤。这是因为所有的入口出口级拥塞控制都是建立在滑窗方法基础上的，而在端—端的ACK被接收以前，滑窗法最多只允许网络中有W（即窗口大小）个顺序分组是未应答的。如果网络拥挤（这可能与目的结点拥挤无关），分组和ACK将使端—端延迟增大。这些延迟连同窗口的约束一起，实际上也起到了降低新的分组进入网络的速率的作用。下面，简要介绍两种入口出口级的控制方法。

1、RFNM重装法（Request For Next Message）(www.xing528.com)

这种方法中，首先假定从同一源主机到同一目的主机的全部报文分组是在同一个逻辑“管道”中传输并且在目的CCP中组装成报文的；每一个管道都用滑窗法单一地控制信息流且都有一个独立的报文顺序号，用于排序和检测重复的报文；在源结点和目的结点都保留一个有效的窗口大小（例如W=8）；在目的结点，窗口外的报文都将被丢弃；无次序到达的报文也将被丢弃，这是因为存储这些报文同时等待没有到达的报文可能造成潜在的重排序死锁。下面以图5.3.10所示的例子对RFNM法进行说明。

图5.3.10　RFNM示意

■——ACK　●——返回RFNM信号　▲——对RFNM的应答

在开始时，Host1与Host4之间已通过某种形式建立了连接。当源Host4收到RFNM时，就向源CCP4发送一个报文；然后由源CCP4将报文拆成分组逐个向CCP3传送，CCP3每收到一个分组就向CCP4返回一个ACK信号，以确认收妥，直到报文传到CCP1；CCP1在正确地接收到完整的报文时，即将完整的报文传送给Host1，同时向CCP4返回RFNM信号；在返回RFNM的时候，各中转CCP之间要用ACK返回表示收妥确认。这里RFNM是一种用于流量控制的短报文，但RFNM也可用于错误控制。如果在一个规定的时间间隔内（如30s）没有收到RFNM，CCP4将向CCP1送一个控制报文，查询未完成传输的原因，以保持CCP4和CCP1报文号的同步，并在报文丢失时要求主机重发。这样的RFNM方法只能控制端—端的信息流，使之不过多地涌入出口结点，要防止死锁还需要一单独的重装缓冲器。对于每一个多分组的报文，在传输之前必须保证在CCP1有一个重装缓冲器组可用，为此在传输之前须用预约的方法向CCP1请求一个可用的重装缓冲器组，并且等待CCP1将应答附在RFNM中送回。

单报文分组的报文可以不用预约直接发送，到目的地后若无缓冲器则丢弃，在一定时间后将再次重发。

在上述讨论中，假定报文是在第三层组装和拆开的，原因是采用RFNM法的原型网是这样规定的，但这不影响讨论问题的实质。对于更一般的子网（只传送分组，组装由主机完成），RFNM法同样可用于端—端的流控，这实际上应属于传送层的问题了。

2、预约缓冲器

对于虚电路机制的子网来说，用预约缓冲器法可以防止拥塞的发生。在虚电路机制的子网中，报文分组将沿着一条事先建立的虚电路顺序地传送，子网只负责传送报文分组，不负责组装报文，故不会有重装死锁。但由于在传送途中要争用CCP的缓冲器，所以仍可能造成网络的拥挤和重排序死锁。为此，可以利用在入口处建立虚电路的呼叫分组，让其在穿过子网建立虚电路的同时，向沿途各个CCP预约缓冲器，当一个呼叫分组到达某CCP后，若得知该CCP的全部缓冲器已被占用，它或是另寻其它路径，或是向源点回送一个忙信号。当呼叫分组到达目的地后，它不仅建立了一条虚电路，而且向各CCP预约了缓冲器，从而保证了入口出口之间逻辑信道的畅通。

借助于每一个CCP为每一虚电路分配的缓冲器和使用该缓冲器的准则，任何进站的分组在转发之前都有地方可存。对于CCP到CCP之间采用停等方式工作的情况，在单工情况下，每个CCP为每一条虚电路预留一个分组缓冲器，在全双工情况下，为每个方向预留一个分组缓冲器，在未将收到的分组转发出去前不发应答信号。这样，应答不仅表示正确地接收了一个分组，还表示有缓冲器可接收下一分组。如果允许CCP到CCP之间有多个未应答的分组，则每个CCP应为每条虚电路规定一个与缓冲器多少相适应的窗口大小，以完全消除发生拥塞，尤其是发生重排序死锁的可能性，这点与上一章的回退n和选择重发所使用的缓冲器准则相类似。

当所有的虚电路通过CCP都得到足够的缓冲器时，分组交换就与电路交换非常相似。这两种情况下，基本资源都永久性（相对来说）地分配给某些特定的入口出口连接，而不考虑其是否有通信。因为所有虚电路都得到了为处理通信信息所必须的资源，故这两种情况都不会发生拥塞，但资源没有得到充分利用。资源为某一连接所专用的另一个问题是该连接必须负担占用资源的全部费用，而不能和其它用户均摊。所以，一些子网仅在低延迟、高速率为传输的基本要求时，例如数字式语音传输时才采用这种方法。当低延迟这个指标不是一直都重要时，合理的做法是给每一缓冲器配一定时器，如果长时间不使用此虚电路，则自动释放缓冲器，当下一报文分组到达时再将释放出去的缓冲器收回来。当然，这个过程可能要占一定时间。