高级操作系统AdvancedOperatingSystemppt课件.ppt

高级操作系统AdvancedOperatingSystem 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 为当前节点与目标节点不同的所有维度 也叫首选维度 preferreddimension 注意 为表示一个消息的目标 等位序列要和消息一起传送因当前节点会随着消息的传递而变化 故等位序列也随着变化 例如 当前节点 0010目标节点 0111等位序列是 1 3 4 10 1基于局部信息的模型消息的表示 每个消息都有一个n位的向量标志 用以保存 空余维度 sparedimensions 可以用这些维度来绕过出错组件 注意 空余维度就是那些没有在最初的等位序列中出现的维度源节点发起路由时 标志中的所有位都将清零 消息的表示 k d1 d2 dk 消息 标记 k为剩余路径长度 k会在消息的发往过程中不断更新当k变为0时 消息就到达目标了 4 10 1基于局部信息的模型算法描述 当节点收到一个消息时 检查k的值以判断自身是否为消息的目标若不是 节点将尝试按照剩下的等位序列中指定的维度发送消息每个节点都将努力沿着最短路径发送消息 然而 若通往最短路径的维度的那些连接出错 这个节点将使用空余维度通过另外的路径发送消息 4 10 1基于局部信息的模型算法的描述 注意 u i 表示沿着维度i的u的邻居 初始 等位序列为由源和目标地址异或得到的所有首选维度 空余维度的所有位清零 每个节点努力沿着最短路径传送 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基于局部信息的模型算法举例 cont d 由于0101的第3维链接出现错误 节点0101将发送 1 3 m 0000 到01014 1101 然而 由于1101的第3维的链接出现错误 节点1101将使用第1维 标记 0100 标记记下了要绕道时的首选维度 并发送消息 2 3 1 m 0101 到1100 4 10 1基于局部信息的模型算法举例 cont d 1100依次将发送 1 1 m 0101 到1000 随后 节点1000的第一个链接又出现错误 这时将使用第2维 此时标记 0101 2 1 2 m 0111 被路由到1010 之后 消息将经过1011到达目标1001 结果路径的长度是8 4 10 2基于有限全局信息的模型 安全等级 定义 考虑具有节点故障的超立方中的有效路由每个节点的有限全局信息使用安全等级来标记 从根本上说 安全等级就是每个节点周围邻居中失效节点的大致数目 定义 设s a k是节点a的安全等级 则称a是k 安全的 一个失效节点是0 安全的 即最低的安全等级 一个n 安全的节点 也叫安全节点 安全级别最高若k n 那么一个k 安全的节点就是不安全的 安全等级的计算算法 下述算法决定了每个节点的状态 每个节点a i 都保存它所有邻居节点的非递减安全状态序列开始 所有非出错节点都是n 安全的 所有出错节点都是0 安全的 该算法需要n 1次重复达到稳定状态 安全等级举例 出错节点0011 0100 0110和1001是0 安全的 黑色 节点0001 0010 0111和1011是1 安全的 棕色 因为每个都有两个出错节点 非递减序列为 0 0 2 2 或 0 0 2 4 或 0 0 4 4 k 1节点0000和0101是2 安全的 紫色 非递减序列为 0 1 1 4 k 21000 1010 1100 1101 1110和1111是安全的 蓝色 非递减序列为 0 4 4 4 或 1 1 4 4 或 0 2 4 4 0 0 1 0 1 2 3 安全等级的性质和基于安全等级的路由 安全等级有以下性质 若一个节点的安全等级是k 0 k n 那么在k海明距离内 至少存在一个从该节点到任意节点的海明距离路径 因此 当源的安全等级大于源和目标间的距离时 就可以保证最优路由 在基于安全等级的路由中 一个引导向量被附加在路由消息上引导向量 当前节点和目标节点的按位异或 基于安全等级的路由举例 图中 每个圆圈 节点 中的数字表明该节点的安全等级 考虑以s1 1110和d1 0001为源和目标的单播路由引导向量是N1 s1 d1 1111 从而H s1 d1 4 由于源节点s1的安全等级是4 从而可以使用最优算法 如下页 在源节点的首选节点中 节点1010 1100和1111的安全等级为4 蓝色 节点0110的安全等级为0 黑色 选择一个具有最高安全等级的一个邻居节点 比如沿0维度的1111引导向量N的相应维复位为0 11110 1110 和消息一起被发送 在中间节点1111 根据引导向量1110 首选邻居集合为 0111 1011 1101 其中 沿1维度的邻居1101具有最高的安全等级4 因此它成为下一个中间节点 引导向量更新为11101 1100 在节点1101 两个首选邻居节点中 3维度邻居0101的安全等级为2 2维度邻居1001是出错节点选择安全等级为2的0101 并更新引导向量为 11003 0100在节点0101 只在2维度有一个首选邻居0001引导向量更新为 01002 0000 收到引导向量为0000的单播消息后 节点0001把自已作为目标节点 同时终止单播算法 4 10 2基于有限全局信息的模型 安全等级 当源s的安全等级小于它和目标d间的距离 s d 时只要存在一个安全等级不小于 s d 1的首选邻居 仍可通过将信息转发到这个节点来实现最优路由否则 如果存在一个安全等级不低于 s d 1的空闲邻居 也可通过将消息转发到这个节点实现次优路由 结果路径的长度是 s d 2 4 10 3基于扩展安全等级模型的路由 安全向量 安全等级模型具有以下缺陷 节点的安全等级为k仅说明在k海明距离中存在一个海明距离路径 并没有提供关于是否存在到达超过k海明距离的节点的海明距离路径 安全向量的概念可以有效地引入失效链接的信息 并能提供系统中错误的数量和分布的信息 安全向量 特别地 设 a1 a2 an 是n维立方中节点a的安全向量如果ak 1 则存在一个从a到任意一个k海明距离的节点的海明距离路径 一个节点的安全向量可以通过在邻居节点中进行n 1轮信息交换来计算 一个出错节点的安全向量是 0 0 0 任意一个节点到a的海明距离在1 n之间 ak的取值为0或1 安全向量 cont d 对于一个非出错节点a 设a的安全向量是 a1 a2 an a在维度i上的邻居的安全向量是 a1 i a2 i an i 若节点a是一个出错链接的端节点 那在相邻的其他端节点看来 a的安全向量是 0 0 0 且以及 a到相应端节点的海明距离为1 但不存在到该端节点的距离为1的路径 求和的话 值在0 n之间 4 10 3基于扩展安全等级模型的路由 安全向量 计算安全向量的方法与通过节点之间交换信息和邻居之间互相更新而计算安全等级的方法类似 路由算法和基于安全等级模型的方法也类似 4 11容错组播 如前所述 在没有出错组件的情况下 网和超立方中的大部分组播问题都是NP完全问题 在出现错误的情况下 问题变得更复杂 一般会使用启发性方法 本节再一次使用n维立方来说明不同的方法 仅考虑系统中的单一组播 4 11 1一般方法 几种容错组播方案已经被提出来 可以按照每个节点使用的网络信息对它们进行分类基于局部信息的容错组播每个节点仅仅知道它的相邻节点和链接的状态优点 简单 缺点 在最坏的情况下需要的时间步数不可控基于局部信息 并且限制性错误模型的容错组播例如 每个节点最多有一个出错邻居基于全局信息的组播 假定每个节点都知道网络中的错误分布 可以保证时间最优 然而 它需要一个复杂的收集全局信息的过程 4 11 1一般方法 基于有限全局信息的组播是上述两种方案的综合 可以得到一个最优或次优的方案同时可以使收集和维护全局信息的过程相对不是很复杂例如 Liang Bhattacharya和Tsai提出了组播方案中 每个节点知道两个跳跃之内所有链接的状态这个方案可以经受n 1个错误链接 在最坏情况下额外的时间步数为2n 4 11 2基于路径的路由为什么考虑路径的路由 在使用树结构的特定系统中在路由过程中复制路由消息是很低效的 而且 如果树形结构的一个树枝阻塞 那么路由就被阻塞 对于长消息这个问题更为严重 因此需要考虑一个禁止在路由过程中分叉的方法 比如基于路径的路由 参见4 4 使用哈密尔顿回路 路径 本小节介绍Wu的基于轨迹的模式 该方法是对路径模式的扩展下面首先给出Wu提出算法的背景 背景 前面讲过 在Lin等人提出的基于路径的路由中 使用了双向信道模型 即每个信道都是双向的在网络中找到一个哈密尔顿路径 所有的路由步骤都遵从选定的哈密尔顿路径 在两个方向 显然 这样避免了循环等待和死锁 每个 有序的 源和目标对在路径的一个方向上出现 但系统使用半双工信道时 信道可以在两个方向发送信息 但是同时只能有一个方向发送 用于双向链接的哈密尔顿路径方法就不再适用了 Wu将基于路径的模式扩展为基于轨迹的模式 4 11 2基于路径的路由Wu的基于轨迹的模式 轨迹的定义 图G中的一个轨迹v0 v1 v2 vn是一次所有边都不同的 行走 walk 图G中的一次行走是一个有限的边的序列 路径是一种特殊的轨迹 所有的点都是不同的 为了保证每个源和目标对都在轨迹中出现至少一次 每个节点都至少要出现两次 4 11 2基于路径的路由Wu的基于轨迹的模式 充要条件 由图论可知 在每个节点都具有偶节点度数 4 的图中 一定有一个每个节点都至少出现两次的轨迹 而且 任何一个有3个以上节点并且具有一个度数小于4的节点的图都没有那样一个轨迹 然而 每个节点出现两次仅仅是必要非充分条件 考虑下面的一部分轨迹 上标i表示对应节点是第i次出现vi1 vi2 vj1 vj2假定vi和vj在轨迹中仅仅出现两次 显然 vj vi 不是这个轨迹上的一个可行的路由 4 11 2基于路径的路由Wu的基于轨迹的模式 充要条件 因此 问题的充要条件如下 对于一个任意给定的节点vi 在出现在最右边的vi的左边一定会至少有一个其他节点 并且在出现在最左边的vi的右边一定会至少有一个其他节点 基于轨迹的模式 两个连续的哈密尔顿路径 4 5节中的基于路径的双环路由方法是符合这个充要条件的 任何两个连续的哈密尔顿路径都符合这个条件 注意 两个连续的哈密尔顿路径需要一个更强的条件然而 如果每个节点在轨迹中出现的次数不能多于两次 那么两个连续的哈密尔顿路径就是一个充要条件了 基于轨迹的模式 两个连续的哈密尔顿路径 cont d 易知在任何2维圆环和任何k 4 维立方中 都存在两个连续的哈密尔顿路径 下图显示了在4维立方中的两个边分离的哈密尔顿回路 基于轨迹的模式 建立两个连续的哈密尔顿路径 在n n 4 维立方中建立边分离的哈密尔顿回路的一般方法如下 将n维立方沿着维度n分成两个n 1维立方 每个n 1维立方中建立两个哈密尔顿回路 把n 1维立方的两个边分离的哈密尔顿回路连接起来 组成n维立方中的一个哈密尔顿回路 方法是 在每个回路中去掉一个边以便打破回路 沿着维度n增加两个边从而把两个打破的回路连接起来 连接剩下的两个哈密尔顿回路 从而形成n维立方中的另一个哈密尔顿回路 在n维立方中建立两个边分离的哈密尔顿路径 从n维立方的两个边分离的哈密尔顿回路中去掉两个邻边 就得到了两个连续的哈密尔顿路径 4 11 3使用安全等级在超立方中进行组播 组播的关键问题是 每个中间节点u 包括源节点s 向它的合适的邻居节点发送一个目标节点集合 u1 u2 um 例如 若一个目标节点集合 u1 u2 u3 0101 1001 0000 并且节点u 1010 相对地址 本节介绍的算法中涉及如下的定义 相对地址ri 取节点u与目标节点ui的地址值的异或值上例中 u 1010 u1 0101则相对地址r1 u u1 1010 0101 1111相对地址的某一位为1 表示在相应的维度上必须进行一次跳步因此可以用目标节点关于节点u的相对地址来代表目标节点使用相对地址的集合表示目标节点的集合 用R表示 R ri 其中ri u ui 1 i m 上例中 u 1010 u1 u2 u3 0101 1001 0000 则R r1 r2 r3 1111 0111 1010 节点间的距离 地址总和 由于相对地址中的1代表了一个必须的跳步 因此相对地址中1的个数 ri 1 j nri j 代表节点u和ui的最短距离如上例中 r1 4 r2 3 r3 2地址总和 表示集合中目标节点在不同维度的分布 使用as表示由于相对地址的每一位对应于一个维度 取所有相对地址在某一维的值之和 1的个数 就是所有目标节点在该维度的分布情况因此 地址总和as ri Rri如上例中 R r1 r2 r3 1111 0111 1010 因此as 2232 相对地址的更新 为避免重复计算相对地址 仅在源节点计算相对地址 每当具有相对地址r的目标节点被沿着维度d发送到下一个节点 r的第d位就被置为0 即这个目标节点的新的相对地址是r d 上例u 1010 u1 0101 相对地址r1 1111 假如u1沿着第2维被送到邻居1000处 则在新的中间节点 1000 上 具有新的相对地址为1101 正好为r1 2 为避免在新的中间节点1000上重新计算相对地址 只需要在发送消息时将目标地址的相应位置0即可 即r d 操作 基于相对地址路由的基本描述 为保证时间最优 使用下面的简单策略 当目标节点ui关于中间节点u的相对地址ri的第d位等于1时 ri d 将沿着d维度发送到u的邻居u d 当目标节点ui的相对地址ri在不同的位 维度 有超过一个的1值时 相对地址ri可以被转发到任意一个维度 此时 需要在n维中确定一个优先级顺序 这个优先级顺序的信息决定了组播的结果 优先级顺序的定义应该能够实现对路径的最大限度的共享从而使流量最小 使用安全等级的原因 在组播中 组播消息不应到达死端 deadend 当一个特定目标节点的所有海明距离路径都被出错邻居阻塞时 死端就会出现在中间节点 在这种情况下 为了到达那个目标必须绕道或回退 为了避免尽头的出现 应该限制向附近有出错节点的邻居发送的目标的数目 这就是在维度有限决策时使用安全等级的原因 基于安全等级的组播 介绍三个方法基于安全等级的组播SLBM 修正的基于安全等级的组播 MSLBM 和基于地址总和的组播ABSM SLBM SLBM中 维度优先级根据该维度上的邻居的安全等级事先决定的 沿着一个维度的邻居的安全等级越高 这个维度的优先级顺序就越高当有两个或两个以上的维度上的邻居具有相同的最高安全等级时 可以使用两个方法 SLBM中 随机决定它们的优先顺序MSLBM 见下页 MSLBM MSLBM中 当两个 或更多 邻居具有相同的安全等级时维度优先顺序根据相应位在所有目标的地址总和中的值决定 若维度d上的邻居可以承担最大可能的目标节点 即若as d 在地址总和中具有最大值 则d就有最高优先级 当地址总和中有超过一个的位其有相同的最大值时 选择是随机的 下一个优先级的选择使用同样的方法 只不过此时要根据更新的目标节点集 即去掉上述被转发到高优先级维度的节点 ASBM ASBM中 维度优先级主要依赖于地址总和中的位值若在一个维度上的邻居节点能承受最大数目的节点 那这个维度就具有最高优先级 为保证时间最优 只有与选定的邻居的海明距离不超过k k为该邻居的安全等级 的目标节点才能被包括进来 在这种情况下 所有邻居的安全等级和目标节点的相对距离都在决策中体现出来了 当存在一个以上的能承载同样最大数目的目标节点的邻居时可以使用一种修正的ASBM正如MSLBM那样 这些邻居的优先级根据其安全等级确定在ASBM中 这些节点的优先顺序是随机选择的 SLBM MSLBM和ASBM 若源节点在出错的n维立方中是安全的 那么由SLBM MSLBM或ASBM产生的组播一定是时间最优的 当源节点不安全并且出错节点的个数不超过n 1时 从源节点到一个目标的路径的长度或者等于相应的海明距离 或者比相应的海明距离多2 若源和任一目标间的相对距离不超过源的安全等级 那么由SLBM MSLBM或ASBM产生的组播一定是时间最优的 算法举例 下图显示了一个有四个出错节点的Q4 出错节点为黑色节点 1100 0110 0011和0001 算法举例 计算安全等级 开始 所有非出错节点都是4 安全的 即安全的第一轮邻居间交换过信息后节点0010 0111 0100和1110因有两个或两个以上的出错邻居 都从4 安全变为1 安全状态其他节点的状态保持不变 算法举例 计算安全等级 cont d 在第二轮之后 节点0000和0101的状态变为2 安全 这是因为它们有两个1 安全的节点和一个2 安全的节点 两轮之后 每个节点的安全等级达到稳定 图中节点中的数字即代表该节点最终的安全等级 算法举例 计算相对地址和地址总和 假定图中源节点是安全节点1000 组播集合u u1 u2 u3 u4 u5 u6 0000 0010 0100 0101 0111 1001 源和目标之间的相对地址集合为R r1 r2 r3 r4 r5 r6 1000 1010 1100 1101 1111 0001 因此 地址总和as 5323 算法举例 使用SLBM SLBM方法仅使用邻居维度序列 ds 所代表的邻居的安全等级来确定邻居节点间的优先级 本例中 维度2具有最高的优先级 其次是维度1和维度4 维度3具有最低的优先级 因为r2和r5的第二位是1 所以r2 2 和r5 2 和组播消息一起将被发往节点1010 1000沿着维度2的邻居 假定组播消息总是附加在从一个节点转发到另一个节点的目标节点的相对地址上面