中国科学技术大学：《高级操作系统 Advanced Operating System》课程PPT教学课件（分布式系统设计）分布式路由算法（2/3）

第四章分布式路由算法 分布式路由算法导论 ● 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 ● 特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法 ● 几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法 ● 超立方中的容错单播算法 容错组播算法 2/83

2/83 第四章 分布式路由算法 ⚫ 分布式路由算法导论 ⚫ 一般类型网络的最短路径路由算法 ⚫ 特殊类型网络的单播算法 ⚫ 特殊类型网络中的多播算法 ⚫ 虚信道和虚网络 ⚫ 完全自适应和无死锁路由算法 ⚫ 几个自适应和无死锁路由算法 ⚫ 容错单播的一般方法 ⚫ 网格和圆环中的容错单播算法 ⚫ 超立方中的容错单播算法 ⚫ 容错组播算法

4.5虚信道和虚网络 ·网络资源 。在存储转发交换中，资源是缓冲区； 。在虫孔路由中，资源是信道。 网络通信中，若消息在占有资源的前提下可以 申请资源，就有可能发生死锁 通过控制路由的自适应性可以预防和避免死锁，同 时也保证一定的容错性。 虚信道和虚网络经常用于实现无死锁、自适应和 (或)容错的路由。 3/83

3/83 4.5 虚信道和虚网络 ⚫ 网络资源 ⚫ 在存储转发交换中，资源是缓冲区； ⚫ 在虫孔路由中，资源是信道。 ⚫ 网络通信中，若消息在占有资源的前提下可以 申请资源，就有可能发生死锁 ⚫ 通过控制路由的自适应性可以预防和避免死锁，同 时也保证一定的容错性。 ⚫ 虚信道和虚网络经常用于实现无死锁、自适应和 （或）容错的路由

4.5虚信道和虚网络 通过网络分区避免死锁 通过网络分区可以避免死锁 。给定的网络可以分成几个子网。 根据源和目标位置的不同，消息被路由到不同的 子网 ·举例说明： 。3×3网格的适应性双Y信道路由 。如图： 。Y方向有两个物理信道（双向） (a)一个3×3网格的 双Y信道网 /83

4/83 4.5 虚信道和虚网络 通过网络分区避免死锁 ⚫ 通过网络分区可以避免死锁 ⚫ 给定的网络可以分成几个子网。 ⚫ 根据源和目标位置的不同，消息被路由到不同的 子网 ⚫ 举例说明： ⚫ 3×3网格的适应性双Y信道路由 ⚫ 如图： ⚫ Y方向有两个物理信道（双向） （a）一个3×3网格的 双Y信道网

4.5虚信道和虚网络 通过网络分区避免死锁（cont'd) 。上述网格被分成正、负两个子网（如下图） ·如果目标位于源的右侧，则使用正网； ·否则将使用负网。 ·当源和目标同列时，两个子网都不用。 由于两个子网中都没有回路，所以可避免死销。 (b)正网络 (c)负网络5/83

5/83 1 2 3 4 5 6 7 8 9 4.5 虚信道和虚网络 通过网络分区避免死锁（cont'd） ⚫ 上述网格被分成正、负两个子网（如下图） ⚫ 如果目标位于源的右侧，则使用正网； ⚫ 否则将使用负网。 ⚫ 当源和目标同列时，两个子网都不用。 ⚫ 由于两个子网中都没有回路，所以可避免死锁。 （b）正网络 （c）负网络

4.5虚信道和虚网络 虚信道 若网络没有双Y信道，则可用几个虚信道复用一 个物理信道 。每个虚信道都有自己的缓冲区。 当物理信道被其它虚信道使用时，就用这个缓冲 区保存消息 ·若虚信道间没有循环等待，就可避免死锁。 假设上例改为单Y信道网，那么原来的正、负子 网中所有的Y信道都是虚信道。 6/83

6/83 4.5虚信道和虚网络 虚信道 ⚫ 若网络没有双Y信道，则可用几个虚信道复用一 个物理信道 ⚫ 每个虚信道都有自己的缓冲区。 ⚫ 当物理信道被其它虚信道使用时，就用这个缓冲 区保存消息 ⚫ 若虚信道间没有循环等待，就可避免死锁。 ⚫ 假设上例改为单Y信道网，那么原来的正、负子 网中所有的Y信道都是虚信道。 1 2 3 4 5 6 7 8 9

4.5虚信道和虚网络 虚信道(cont'd) 。当两个虚信道共享一个物理信道时， 信道利用率大幅提高。 虽然虚信道提供了一个具有多重信道的网络， 但仍需仔细设计路由算法。例如， 可以按照信道标记的升序使用虚信道，以便避免虚 信道间循环依赖。 7/83

7/83 4.5虚信道和虚网络 虚信道（cont'd） ⚫ 当两个虚信道共享一个物理信道时， 信道利用率大幅提高。 ⚫ 虽然虚信道提供了一个具有多重信道的网络， 但仍需仔细设计路由算法。例如， ⚫ 可以按照信道标记的升序使用虚信道，以便避免虚 信道间循环依赖

4.5虚信道和虚网络 虚网终 ● 前面那个例子中，若使用单Y信道，则前面的正、 负子网可认为是两个虚网络。 。显然每个网络中都没有回路。因每个路由过程最多只使用 一个虚网络，所以不会产生互相交叉的虚网络回路。 8/83

8/83 ⚫ 比虚信道更高一级的虚拟化是虚网络 ⚫ 一个给定的物理网络被分成几个虚网络，每个虚网络包括 一系列的虚信道。 ⚫ 虚网络中相邻的节点被映射到物理网络中时也要相邻 ⚫ 一个虚网络中的虚信道设置应避免信道间的回路。 虽然仍有可能存在互相交叉的虚网络回路，但可以 通过使虚网络遵循全序或偏序来避免回路 ⚫ 前面那个例子中，若使用单Y信道，则前面的正、 负子网可认为是两个虚网络。 ⚫ 显然每个网络中都没有回路。因每个路由过程最多只使用 一个虚网络，所以不会产生互相交叉的虚网络回路。 4.5虚信道和虚网络 虚网络 1 2 3 4 5 6 7 8 9

4.5虚信道和虚网络 虽然虚网络包含虚信道，二者完全不同。 ·一般，虚信道使用与路由过程紧密相连，包括源和 目标的位置。必须合理安排虚信道，以避免死锁。 虚网络通常设计为没有回路，因而路由算法可以不 必考虑死锁，除非存在交叉虚网络的依赖性 9/83

9/83 4.5虚信道和虚网络 ⚫ 虽然虚网络包含虚信道，二者完全不同。 ⚫ 一般，虚信道使用与路由过程紧密相连，包括源和 目标的位置。必须合理安排虚信道，以避免死锁。 ⚫ 虚网络通常设计为没有回路，因而路由算法可以不 必考虑死锁，除非存在交叉虚网络的依赖性

4.5虚信道和虚网络 虚信道举例 ·考虑一个有四个节点的单向环。如果同时有几个 路由进程启动，就会发生死锁。 P2 P3 P1 PO 10/83

10/83 4.5虚信道和虚网络 虚信道举例 ⚫ 考虑一个有四个节点的单向环。如果同时有几个 路由进程启动，就会发生死锁。 P2 P0 P3 P1

4.5虚信道和虚网络 虚信道举例(cont'd) 。通过给每个链接增加两个虚信道可以避免死锁 ·如图，信道被分为 高虚信道，和 Cho,Ch1,Ch2,Ch3 低虚信道 Ch3 Ch2 C10,C1,C12,C13 C13 C12 P3 Cho Chl 11/83

11/83 4.5虚信道和虚网络 虚信道举例（cont'd） ⚫ 通过给每个链接增加两个虚信道可以避免死锁 ⚫ 如图，信道被分为 ⚫ 高虚信道，和 Ch0, Ch1, Ch2, Ch3 ⚫ 低虚信道 Cl0, Cl1, Cl2, Cl3 P2 P0 P3 P1 Ch2 Ch0 Ch1 Ch3 Cl3 Cl2 Cl0 Cl1