第四章分布式路由算法 分布式路由算法导论 ● 一般类型网络的最短路径路由算法 。特殊类型网络的单播算法 ● 特殊类型网络中的多播算法 ● 虚信道和虚网络 ● 完全自适应和无死锁路由算法 ● 几个自适应和无死锁路由算法 ● 容错单播的一般方法 ● 网格和圆环中的容错单播算法 ● 超立方中的容错单播算法 容错组播算法
第四章 分布式路由算法 ⚫ 分布式路由算法导论 ⚫ 一般类型网络的最短路径路由算法 ⚫ 特殊类型网络的单播算法 ⚫ 特殊类型网络中的多播算法 ⚫ 虚信道和虚网络 ⚫ 完全自适应和无死锁路由算法 ⚫ 几个自适应和无死锁路由算法 ⚫ 容错单播的一般方法 ⚫ 网格和圆环中的容错单播算法 ⚫ 超立方中的容错单播算法 ⚫ 容错组播算法
4.10超立方中的容错单播 按照使用的错误信息类型对超立方中的容错单 播路由进行分类： 。基于局部信息的 。基于有限全局信息的 基于扩展安全等级模型的
4.10 超立方中的容错单播 ⚫ 按照使用的错误信息类型对超立方中的容错单 播路由进行分类： ⚫ 基于局部信息的 ⚫ 基于有限全局信息的 ⚫ 基于扩展安全等级模型的
4.10.1基于局部信息的模型 已经证明， 。对n维立方中的任何两点u和w,如果H(u,w)=k,那 么从u到w恰好有n条点分离路径。其中 。有k条长度为k的路径和(-k)条长度为k+2的路径 ● 若出错组件的数目L小于n,那么用多条路径进 行路由的方法是很直接的。 。消息沿着条点分离路径进行传送，并且其中至少 有一条是好的。 这样，就可通过那条路径到达目标，路径最大长度 是k+2
4.10.1 基于局部信息的模型 ⚫ 已经证明， ⚫ 对n维立方中的任何两点u和w，如果H(u,w)=k，那 么从u到w恰好有n条点分离路径。其中， ⚫ 有k条长度为k的路径和(n-k)条长度为k+2的路径 ⚫ 若出错组件的数目L小于n，那么用多条路径进 行路由的方法是很直接的。 ⚫ 消息沿着n条点分离路径进行传送，并且其中至少 有一条是好的。 ⚫ 这样，就可通过那条路径到达目标，路径最大长度 是k+2
4.10.1基于局部信息的模型 ● chen和shin给出了下面四种容错路由算法： 1. 出错组件小于n-1,不确保有最优路径。 2. 出错组件小于-1，确保有最优路径。 3. 出错组件无限制，不确保有最优路径。 4. 出错组件无限制，确保有最优路径。 ● 第2和第4种情况是所希望的，但相应的算法 会引入特别的开销
4.10.1 基于局部信息的模型 ⚫ chen和shin给出了下面四种容错路由算法: 1. 出错组件小于n-1，不确保有最优路径。 2. 出错组件小于n-1，确保有最优路径。 3. 出错组件无限制，不确保有最优路径。 4. 出错组件无限制，确保有最优路径。 ⚫ 第2和第4种情况是所希望的，但相应的算法 会引入特别的开销
4.10.1基于局部信息的模型 。下面考虑上述第一种情况的算法， 。首先，给出等位序列的定义 。接着，给出消息的表示方法 ·然后，给出算法 最后，举例
4.10.1 基于局部信息的模型 ⚫ 下面考虑上述第一种情况的算法， ⚫ 首先，给出等位序列的定义 ⚫ 接着，给出消息的表示方法 ⚫ 然后，给出算法 ⚫ 最后，举例