高级操作系统AdvancedOperatingSystemPPT课件课件.pptVIP

高级操作系统Advanced Operating System 熊焰 yxiong@ustc.edu.cn 0551_3607394 中国科学技术大学计算机系 第四章 分布式路由算法 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法 几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法 4.10 超立方中的容错单播 按照使用的错误信息类型对超立方中的容错单播路由进行分类： 基于局部信息的 基于有限全局信息的 基于扩展安全等级模型的 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给出了下面四种容错路由算法: 出错组件小于n-1，不确保有最优路径。 出错组件小于n-1，确保有最优路径。 出错组件无限制，不确保有最优路径。 出错组件无限制，确保有最优路径。 第2和第4种情况是所希望的，但相应的算法会引入特别的开销。 4.10.1 基于局部信息的模型 下面考虑上述第一种情况的算法， 首先，给出等位序列的定义 接着，给出消息的表示方法 然后，给出算法 最后，举例 4.10.1 基于局部信息的模型等位序列定义 定义：等位序列[d1, d2, …, dk]为当前节点与目标节点不同的所有维度（也叫首选维度，preferred dimension） 注意： 为表示一个消息的目标，等位序列要和消息一起传送 因当前节点会随着消息的传递而变化，故等位序列也随着变化 4.10.1 基于局部信息的模型消息的表示 每个消息都有一个n位的向量标志，用以保存“空余维度(spare dimensions)”。 可以用这些维度来绕过出错组件。 注意：空余维度就是那些没有在最初的等位序列中出现的维度 源节点发起路由时，标志中的所有位都将清零。 消息的表示：(k, [d1, d2, …, dk], 消息, 标记)。 k为剩余路径长度， k会在消息的发往过程中不断更新 当k变为0时，消息就到达目标了。 4.10.1 基于局部信息的模型算法描述 当节点收到一个消息时，检查k的值以判断自身是否为消息的目标 若不是，节点将尝试按照剩下的等位序列中指定的维度发送消息 每个节点都将努力沿着最短路径发送消息。 然而，若通往最短路径的维度的那些连接出错，这个节点将使用空余维度通过另外的路径发送消息。 4.10.1 基于局部信息的模型算法的描述 4.10.1 基于局部信息的模型算法举例 假设消息m从u=0110 ? w=1001。最初消息是(4, [1, 2, 3, 4], m, 0000) 按照上述算法， 节点0110将(3, [2 ,3 ,4], m, 0000)发送给01101=0111， 随后0111将(2, [3, 4], m, 0000)发送给01112=0101。 4.10.1 基于局部信息的模型算法举例（contd） 由于0101的第3维链接出现错误，节点0101将发送(1, [3], m, 0000)到01014=1101。 然而，由于1101的第3维的链接出现错误，节点1101将使用第1维（标记=0100，标记记下了要绕道时的首选维度），并发送消息(2, [3, 1] , m, 0101)到1100。 4.10.1 基于局部信息的模型算法举例（contd） 1100依次将发送(1, [1], m, 0101)到1000。 随后，节点1000的第一个链接又出现错误。这时将使用第2维（此时标记=0101）, (2, [1, 2], m, 0111)被路由到1010。 之后，消息将经过1011到达目标1001。结果路径的长度是8 。 4.10 超立方中的容错单播 按照使用的错误信息类型对超立方中的容错单播路由进行分类： 基于局部信息的 基于有限全局信息的 安全等级 基于扩展安全等级模型的 4.10.2 基于有限全局信息的模型：安全等级（定义） 考虑具有节点故障的超立方中的有效路由 每个节点的有限全局信息使用安全等级来标记。 从根本上说，安全等级就是每个节点周围邻居中失效节点的大致数目。 定义：设s(a)=k是节点a的安全等级，则称a是k-安全的； 一个失效节点是0-安全的，即最低的安全等级，