第二章分布式路由算法 分布式路由算法导论 ● 一 般类型网络的最短路径路由算法 。特殊类型网络的单播算法 ● 特殊类型网络中的多播算法 虚信道和虚网络 ● 完全自适应和无死锁路由算法 几个自适应和无死锁路由算法 容错单播的一般方法 ● 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法
第二章 分布式路由算法 ⚫ 分布式路由算法导论 ⚫ 一般类型网络的最短路径路由算法 ⚫ 特殊类型网络的单播算法 ⚫ 特殊类型网络中的多播算法 ⚫ 虚信道和虚网络 ⚫ 完全自适应和无死锁路由算法 ⚫ 几个自适应和无死锁路由算法 ⚫ 容错单播的一般方法 ⚫ 网格和圆环中的容错单播算法 ⚫ 超立方中的容错单播算法 ⚫ 容错组播算法
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