死锁防止

拥塞的极端后果是死锁。死锁是网络中最容易发生的故障之一,即使在网络负荷不很重时也会发生。死锁发生时,一组节点由于没有空闲缓冲区而无法接收和转发分组,节点之间相互等待,既不能接收分组也不能转发分组,并一直保持这一僵局,严重时甚至导致整个网络的瘫痪。此时,只能靠人工干预来重新启动网络,解除死锁。但重新启动后并未消除引起死锁的隐患,所以可能再次发生死锁。死锁是由于控制技术方面的某些缺陷所引起的,起因通常难以捉摸、难以发现,即使发现,也常常不能立即修复。因此,在各层协议中都必须考虑如何避免死锁的问题。存储转发死锁及其防止最常见的死锁是发生在两个节点之间的直接存储转发死锁。

例如,A节点的所有缓冲区装满了等待输出到B节点的分组,而B节点的所有缓冲区也全部装满了等待输出到A节点的分组;此时,A节点不能从B节点接收分组,B节点也不能从A节点接收分组,从而造成两节点间的死锁。这种情况也可能发生在一组节点之间,例如,A节点企图向B节点发送分组、B节点企图向C节点发送分组、而C节点又企图向A节点发送分组,但此时每个节点都无空闲缓冲区用于接收分组,这种情形称做间接存储转发死锁。当一个节点处于死锁状态时,所有与之相连的链路将被完全拥塞。一种防止存储转发死锁的方法是,每个节点设置M+1个缓冲区,并以0到M编号。M为通信子网的直径,即从任一源节点到任一目的节点间的最大链路段数。每个源节点仅当其0号缓冲区空时才能接收源端系统来的分组,而此分组仅能转发给1号缓冲区空闲的相邻节点,再由该节点将分组转发给它的2号缓冲区空闲的相邻节点……最后,该分组或者顺利到达目的节点并被递交给目的端系统,或者到了某个节点编号为M的缓冲区中再也转发不下去,此时一定发生了循环,应该将该分组丢弃。由于每个分组都是按照编号递增规则分配缓冲区,所以节点之间不会相互等待空闲缓冲区而发生死锁现象。

这种方法的不足之处在于,当某节点虽然有空闲缓冲区,但正巧没有所需要的特定编号的缓冲区时,分组仍要等待,从而造成了缓冲区和链路的浪费。另一种防止存储转发死锁的方法是,使每个分组上都携带一个全局性的惟一的"时间戳",每个节点要为每条输入链路保留一个特殊的接收缓冲区,而其它缓冲区均可用于存放中转分组。在每条输出链路的队列上分组按时间戳顺序排队。例如,节点A要将分组送到节点B,若B节点没有空闲缓冲区,但正巧有要送到A节点的分组,此时A、B节点可通过特殊的接收缓冲区交换分组;若B节点既没有空闲缓冲区,也没有要送往A节点的分组,B节点只好强行将一个出路方向大致与A节点方向相同的分组与A节点互相交换分组,但此时A节点中的分组必须比B节点中的分组具有更早的时间戳,这样才能保证子网中某个最早的分组不受阻挡地转发到目的地。由此可见,每个分组最终总会成为最早的分组,并总能被一步一步地发送到目的节点,从而避免了死锁现象的发生。重装死锁及其防止死锁中比较严重的情况是重装死锁。

假设发给一个端系统的报文很长,被源节点拆成若干个分组发送,目的节点要将所有具有相同编号的分组重新装配成报文递交给目的端系统,若目的节点用于重装报文的缓冲区空间有限,而且它无法知道正在接收的报文究竟被拆成多少个分组,此时,就可能发生严重的问题:为了接收更多的分组,该目的节点用完了它的缓冲空间,但它又不能将尚未拼装完整的报文递送给目的端系统,而邻节点仍在不断地向它传送分组,但它却无法接收。这样,经过多次尝试后,邻节点就会绕道从其它途径再向该目的节点传送分组,但该目的节点已被死锁,其周边区域也由此发生了拥塞。下面几种方法可用以避免重装死锁的发生:①允许目的节点将不完整的报文递交给目的端系统;②一个不能完整重装的报文能被检测出来,并要求发送该报文的源端系统重新传送;③为每个节点配备一个后备缓冲空间,用以暂存不完整的报文。①、②两种方法不能很满意地解决重装死锁,因为它们使端系统中的协议复杂化了。一般的设计中,网络层应该对端系统透明,也即端系统不该考虑诸如报文拆、装之类的事。③方法虽然不涉及端系统,但使每个节点增加了开销。