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