数据通信课件笫10章网络互连幻灯片.ppt

分组消灭 该法不必预先保留缓冲区,当缓冲区占满时,将到来的分组丢弃。 若通信子网提供的是数据报服务,则用分组丢弃法来防止拥塞发生不会引起大的影响。但若通信子网提供的是虚电路服务,则必须在某处保存被丢弃分组的备份,以便拥塞解决后能重新传送。 缓冲分配 该法用于虚电路分组交换网中。在建立虚电路时,让呼叫请求分组途经的节点为虚电路预先分配一个或多个数据缓冲区。若某个节点缓冲器已被占满,则呼叫请求分组另择路由,或者返回一个“忙”信号给呼叫者。这样,通过途经的各节点为每条虚电路开设的永久性缓冲区(直到虚电路拆除),就总能有空间来接纳并转送经过的分组。 此时的分组交换跟电路交换很相似。当节点收到一个分组并将它转发出去之后,该节点向发送节点返回一个确认信息。该确认一方面表示接收节点已正确收到分组,另一方面告诉发送节点,该节点已空出缓冲区以备接收下一个分组。 上面是停一等协议下的情况,若节点之间的协议允许多个未处理的分组存在,则为了完全消除拥塞的可能性,每个节点要为每条虚电路保留等价于窗口大小数量的缓冲区。 10.8.2死锁 拥塞严重时甚至会导致网络通信业务陷入停顿，即出现死锁现象。 死锁发生时,一组节点由于没有空闲缓冲区而无法接收和转发分组,节点之间相互等待,既不能接收分组也不能转发分组,并一直保持这一僵局,严重时甚至导致整个网络的瘫痪。 防止存储转发死锁的方法 一种防止存储转发死锁的方法是,每个节点设置M+1个缓冲区,并以0到M编号。M为通信子网的直径,即从任一源节点到任一目的节点间的最大链路段数。每个源节点仅当其0号缓冲区空时才能接收源端系统来的分组,而此分组仅能转发给1号缓冲区空闲的相邻节点,再由该节点将分组转发给它的2号缓冲区空闲的相邻节点……最后,该分组或者顺利到达目的节点并被递交给目的端系统,或者到了某个节点编号为M的缓冲区中再也转发不下去,此时一定发生了循环,应该将该分组丢弃。由于每个分组都是按照编号递增规则分配缓冲区,所以节点之间不会相互等待空闲缓冲区而发生死锁现象。 重装死锁及其防止 死锁中比较严重的情况是重装死锁。 假设发给一个端系统的报文很长,被源节点拆成若干个分组发送,目的节点要将所有具有相同编号的分组重新装配成报文递交给目的端系统,若目的节点用于重装报文的缓冲区空间有限,而且它无法知道正在接收的报文究竟被拆成多少个分组,此时,就可能发生严重的问题:为了接收更多的分组,该目的节点用完了它的缓冲空间,但它又不能将尚未拼装完整的报文递送给目的端系统,而邻节点仍在不断地向它传送分组,但它却无法接收。 这样,经过多次尝试后,邻节点就会绕道从其它途径再向该目的节点传送分组,但该目的节点已被死锁,其周边区域也由此发生了拥塞。 避免重装死锁: ①允许目的节点将不完整的报文递交给目的端系统; ②一个不能完整重装的报文能被检测出来,并要求发送该报文的源端系统重新传送; ③为每个节点配备一个后备缓冲空间,用以暂存不完整的报文。 ①、②两种方法不能很满意地解决重装死锁,因为它们使端系统中的协议复杂化了。一般的设计中,网络层应该对端系统透明,也即端系统不该考虑诸如报文拆、装之类的事。③方法虽然不涉及端系统,但使每个节点增加了开销。 * * Dijkstra集中式算法： 算法举例 上述算法作用于如图所示的网络：以P5为源节点 集合N只包含源节点P5即N= { P5}。对不在N中的节点P1,P2,P3,P4计算：D(1)=D(2)=∞；（由于P1和P2不与P5直接相连）D(3)=l(P5 ,P3) =20D(4)=l(P5,P4)=2 Dijkstra集中式算法： 算法举例（contd） 取D(1),D(2),D(3),D(4)中具最小值的对应节点P4加入到集合N中, N= { P5,P4},对不在N中的其它节点P3,P2,P1更新D(1)=min{D(1),D(4)+l(4,1)} =min{∞,2+∞}=∞,D(2)=min{D(2),D(4)+l(4,2)} =min{∞,2+1}=3,D(3)=min{D(3),D(4)+l(4,3)} =min{20,2+2}=4。 Dijkstra集中式算法： 算法举例（contd） 取D(1),D(2),D(3)中具最小值的对应节点P2加入到集合N中，N={P5,P4,P2},对不在N中的其它节点P3,P1更新D(1)=min{D(1),D(2)+l(2,1)} =min{∞,3+4}=7D(3)=min{D(3),D(2)+l(2,3)} =min{4