第章自适应、无死锁和容错路由.ppt

第7章 自适应、无死锁和容错路由 自适应、无死锁和容错路由 网络通信中，消息在占有资源（缓冲区、信道）的情况下再申请资源，就可能会发生死锁。在自适应路由环境下，死锁更容易发生。 自适应、无死锁和容错路由 本章主要讨论： 如何通过对网络逻辑上的改造或对自适应路由一定的限制，避免自适应路由中死锁的发生。 节点或链路发生错误时，如何实现路由（容错路由）。 虚信道和虚网络 在死锁的4个条件（互斥、占有并等待、不可剥夺、循环等待）中，避免路由死锁主要通过避免循环等待来实现。 网络通信中的链路（信道）是双向的，路由时容易产生回路。如果避免网络通信中产生回路，那么就不会形成循环等待，路由也就不会发生死锁。 虚信道和虚网络 一种办法是通过划分子网，每个子网中没有回路。不同方向的网络通信在不同子网中进行，从而避免死锁。例： 虚信道和虚网络 当物理上不存在双（多）信道时，可以使用虚信道来实现。 虚信道 多个虚信道对一个物理信道进行复用，每个虚信道都有自己的缓冲器。当物理信道被其它虚信道使用时，就用这个缓冲器保存信息。 如果虚信道之间没有循环等待，那么就可以避免死锁。 虚信道同时也可以提高对物理信道的利用率。 虚信道和虚网络 虚信道上更高一级的虚拟化是虚网络。 虚网络 一个给定的物理网络可被分成几个虚网络。 每个虚网络包括一系列的虚信道。 在虚网络中相邻的节点被映射到物理网络中的时候也要相邻 。 虚信道和虚网络 一个是信道层次上的虚拟化，一个是网络层次上的虚拟化。 必须合理安排虚信道，以避免因为虚信道间的依赖性而产生死锁；虚网络通常设计成没有回路的，其中通信不会产生死锁。 虚信道和虚网络 例：4个节点的单向环。 如果同时有几个路由进程启动，就会发生死锁。 为每个链路设计2个虚信道来避免死锁。 虚信道和虚网络 虚信道安排： 如果源地址大于目的地址，可以从任何一个信道开始；但一旦使用一个高（低）信道，那么以后也要使用同一信道。 如果源地址小于目的地址，首先使用高信道，经过P3节点后，高虚信道切换为低虚信道。 这样，相应的信道依赖图如下： 虚信道和虚网络 DCDL形式化描述： /* 最大节点 */ P(n-1)::= * [ initiate a routing ? [ send(m,des) to Ch(n-1) ? send(m,des) to Cl(n-1) ] ? receive(m,des) from Ch0 ? [ Pn-1=des ? send (m) to local processor ? Pn-1?des ? send (m,des) to Cl(n-1) ] ] 虚信道和虚网络 /* 其他节点 */ P(i:0..n-2)::= * [ initiate a routing ? [ true ? send(m,des) to Chi ? i des ? send(m,des) to Cli ] /* 如果i des，可以使用高信道或低信道； */ /* 如果i des，则只能使用高信道。 */ ? receive(m,des) from Ch(i+1) (or Cl(i+1)) ? [ Pi=des ? send (m) to local processor ? Pi?des ? send (m,des) to Chi (or Cli) ] ] 也可以通过虚网络来实现，而且具有更好的适应性（不一定在最大节点处切换信道）。 完全自适应和无死锁路由 适应性和无死锁是两个互相矛盾的要求。 一个决定性路由可以确保无死锁，但网络组件（链接或节点）错误时，无法适应，路由只好失效。 另一方面，没有限制的适应性路由很可能引发死锁。 目标：在不引发死锁的前提下，尽可能增加适应性。 虚信道类 为了做到完全自适应的无死锁路由，需要引入足够多的虚信道。 当路由开始时，使用虚信道1(vc1)。在第i步使用虚信道i(vci)以及相应的链接。这样，如果一个给定网络的最长路径（网络直径）是Dmax，就要用Dmax个虚信道。 为了减少虚信道的数量，可以通过将虚信道分类来实现。 将给定网络分成k个子集：S1,S2,…,Sk，每个子集都不会包含相邻的节点。当一个消息从子集Si中的一个节点移动到子集Sj中的一个节点时（这里ij），称之为正移动；反之为负移动。当发生负移动时，虚信道标记加1（假定信道标记是从1开始的）。这样，所需虚信道的个数就是一个路由路径中负移动的个数。 选择