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