第二章分布式路由算法 分布式路由算法导论 ● 一 般类型网络的最短路径路由算法 。特殊类型网络的单播算法 ● 特殊类型网络中的多播算法 虚信道和虚网络 ● 完全自适应和无死锁路由算法 几个自适应和无死锁路由算法 容错单播的一般方法 ● 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法
第二章 分布式路由算法 ⚫ 分布式路由算法导论 ⚫ 一般类型网络的最短路径路由算法 ⚫ 特殊类型网络的单播算法 ⚫ 特殊类型网络中的多播算法 ⚫ 虚信道和虚网络 ⚫ 完全自适应和无死锁路由算法 ⚫ 几个自适应和无死锁路由算法 ⚫ 容错单播的一般方法 ⚫ 网格和圆环中的容错单播算法 ⚫ 超立方中的容错单播算法 ⚫ 容错组播算法
2.5虚信道和虚网络 ·网络资源 。在存储转发交换中，资源是缓冲区； 。在虫孔路由中，资源是信道。 网络通信中，若消息在占有资源的前提下可以 申请资源，就有可能发生死锁 。通过控制路由的自适应性可以预防和避免死锁，同 时也保证一定的容错性。 。虚信道和虚网络经常用于实现无死锁、自适应和 (或)容错的路由
2.5 虚信道和虚网络 ⚫ 网络资源 ⚫ 在存储转发交换中，资源是缓冲区； ⚫ 在虫孔路由中，资源是信道。 ⚫ 网络通信中，若消息在占有资源的前提下可以 申请资源，就有可能发生死锁 ⚫ 通过控制路由的自适应性可以预防和避免死锁，同 时也保证一定的容错性。 ⚫ 虚信道和虚网络经常用于实现无死锁、自适应和 （或）容错的路由
2.5虚信道和虚网络 通过网络分区避免死锁 ·通过网络分区可以避免死锁 。给定的网络可以分成几个子网。 。根据源和目标的位置，消息被路由到不同的子网 举例说明： 。3X3网格的适应性双Y信道路由 如图： 。在Y方向有两个物理信道 (双向) (a)一个3X3网格的 双Y信道网
2.5 虚信道和虚网络 通过网络分区避免死锁 ⚫ 通过网络分区可以避免死锁 ⚫ 给定的网络可以分成几个子网。 ⚫ 根据源和目标的位置，消息被路由到不同的子网 ⚫ 举例说明： ⚫ 3X3网格的适应性双Y信道路由 ⚫ 如图： ⚫ 在Y方向有两个物理信道 （双向） （a）一个3X3网格的 双Y信道网
2.5虚信道和虚网络 通过网络分区避免死锁（cont'd) 上述网格被分成正、负两个子网（如下图） 。如果目标位于源的右侧，则使用正网； 否则将使用负网。 。当源和目标同列时，两个子网都不用。 由于两个子网中都没有回路，所以可避免死锁。 b)正网络 (c)负网络
2.5 虚信道和虚网络 通过网络分区避免死锁（cont'd） ⚫ 上述网格被分成正、负两个子网（如下图） ⚫ 如果目标位于源的右侧，则使用正网； ⚫ 否则将使用负网。 ⚫ 当源和目标同列时，两个子网都不用。 ⚫ 由于两个子网中都没有回路，所以可避免死锁。 （b）正网络 （c）负网络
2.5虚信道和虚网络 虚信道 。若网络没有双Y信道，则可用几个虚信道复用一个物 理信道 。每个虚信道都有自己的缓冲区。 当物理信道被其它虚信道使用时，就用这个缓冲区保存消息 。若虚信道间没有循环等待，就可避免死锁。 01 假设上例改为单Y信道网，那么原来的正、负子网中 所有的Y信道都是虚信道
2.5虚信道和虚网络 虚信道 ⚫ 若网络没有双Y信道，则可用几个虚信道复用一个物 理信道 ⚫ 每个虚信道都有自己的缓冲区。 ⚫ 当物理信道被其它虚信道使用时，就用这个缓冲区保存消息 ⚫ 若虚信道间没有循环等待，就可避免死锁。 ⚫ 假设上例改为单Y信道网，那么原来的正、负子网中 所有的Y信道都是虚信道
2.5虚信道和虚网络 虚信道(cont'd) ·当两个虚信道共享一个物理信道时， 信道利用率大幅提高 虽然虚信道提供了一个具有多重信道的网络， 但仍需仔细设计路由算法。例如， 。可以按照信道标记的升序使用虚信道，以便避免虚 信道间循环依赖
2.5虚信道和虚网络 虚信道（cont'd） ⚫ 当两个虚信道共享一个物理信道时， 信道利用率大幅提高。 ⚫ 虽然虚信道提供了一个具有多重信道的网络， 但仍需仔细设计路由算法。例如， ⚫ 可以按照信道标记的升序使用虚信道，以便避免虚 信道间循环依赖
2.5虚信道和虚网络 虚网络 。比虚信道更高一级的虚拟化是虚网络 一个给定的物理网络被分成几个虚网络，每个虚网络包括 一系列的虚信道 。 虚网络中相邻的节点被映射到物理网络中时也要相邻 一般地，一个虚网络中的虚信道设置应避免信道间 的回路。虽然仍有可能存在互相交叉的虚网络回路， 但可以通过使虚网络遵循全序或偏序来避回路 ● 前面那个例子中，若使用单Y信道，则前面的正、 负子网可认为是两个虚网络。 8于 显然每个网络中都没有回路。因每个路由过程最多只使用 一个虚网络，所以不会产生互相交叉的虚网络回路
2.5虚信道和虚网络 虚网络 ⚫ 比虚信道更高一级的虚拟化是虚网络 ⚫ 一个给定的物理网络被分成几个虚网络，每个虚网络包括 一系列的虚信道。 ⚫ 虚网络中相邻的节点被映射到物理网络中时也要相邻 ⚫ 一般地，一个虚网络中的虚信道设置应避免信道间 的回路。虽然仍有可能存在互相交叉的虚网络回路， 但可以通过使虚网络遵循全序或偏序来避回路 ⚫ 前面那个例子中，若使用单Y信道，则前面的正、 负子网可认为是两个虚网络。 ⚫ 显然每个网络中都没有回路。因每个路由过程最多只使用 一个虚网络，所以不会产生互相交叉的虚网络回路
2.5虚信道和虚网络 。虽然虚网络包含虚信道，二者是完全不同的概 念。 一般地，虚信道的使用是与路由过程紧密相连的， 包括源和目标的位置。必须合理安排虚信道，以避 免死锁。 虚网络通常设计为没有回路，因而路由算法可以不 必考虑死锁，除非存在交叉虚网络的依赖性
2.5虚信道和虚网络 ⚫ 虽然虚网络包含虚信道，二者是完全不同的概 念。 ⚫ 一般地，虚信道的使用是与路由过程紧密相连的， 包括源和目标的位置。必须合理安排虚信道，以避 免死锁。 ⚫ 虚网络通常设计为没有回路，因而路由算法可以不 必考虑死锁，除非存在交叉虚网络的依赖性
2.5虚信道和虚网络 虚信道举例 ●考虑一个有四个节点的单向环。如果同时有几个 路由进程启动，就会发生死锁。 P2 P3 P1 PO
2.5虚信道和虚网络 虚信道举例 ⚫ 考虑一个有四个节点的单向环。如果同时有几个 路由进程启动，就会发生死锁。 P2 P0 P3 P1
2.5虚信道和虚网络 虚信道举例(cont'd) 。通过给每个链接增加两个虚信道可以避免死锁 。如图，信道被分为 高虚信道，和 Cho,Ch1,Ch2,Ch3 ●低虚信道 Ch3 Ch2 C10,C1,C12,C3 C13 C12 P3 D Cho Chl
2.5虚信道和虚网络 虚信道举例（cont'd） ⚫ 通过给每个链接增加两个虚信道可以避免死锁 ⚫ 如图，信道被分为 ⚫ 高虚信道，和 Ch0, Ch1, Ch2, Ch3 ⚫ 低虚信道 Cl0, Cl1, Cl2, Cl3 P2 P0 P3 P1 Ch2 Ch0 Ch1 Ch3 Cl3 Cl2 Cl0 Cl1