高级操作系统 Advanced Operating System 熊焰 yxiong@ustc.edu.cn 0551_3607394 中国科学技术大学计算机系

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

4.10 超立方中的容错单播 按照使用的错误信息类型对超立方中的容错单播路由进行分类： 基于局部信息的 基于有限全局信息的 基于扩展安全等级模型的

4.10.1 基于局部信息的模型 已经证明， 若出错组件的数目L小于n，那么用多条路径进行路由的方法是很直接的。 对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给出了下面四种容错路由算法: 第2和第4种情况是所希望的，但相应的算法会引入特别的开销。 出错组件无限制，不确保有最优路径。 出错组件无限制，确保有最优路径。 第2和第4种情况是所希望的，但相应的算法会引入特别的开销。

4.10.1 基于局部信息的模型 下面考虑上述第一种情况的算法， 首先，给出等位序列的定义 接着，给出消息的表示方法 然后，给出算法 最后，举例

4.10.1 基于局部信息的模型 等位序列定义 定义：等位序列[d1, d2, …, dk] 为当前节点与目标节点不同的所有维度（也叫首选维度，preferred dimension） 注意： 为表示一个消息的目标，等位序列要和消息一起传送 因当前节点会随着消息的传递而变化，故等位序列也随着变化 例如： 当前节点：0 0 1 0 目标节点：0 1 1 1 等位序列是[1,3]

4.10.1 基于局部信息的模型 消息的表示 每个消息都有一个n位的向量标志，用以保存“空余维度(spare dimensions)”。 可以用这些维度来绕过出错组件。 注意： 空余维度就是那些没有在最初的等位序列中出现的维度 源节点发起路由时，标志中的所有位都将清零。 消息的表示： (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 超立方中的容错单播 按照使用的错误信息类型对超立方中的容错单播路由进行分类： 基于局部信息的 基于有限全局信息的 安全等级 基于扩展安全等级模型的

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=2 1000, 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|时

4.10 超立方中的容错单播 按照使用的错误信息类型对超立方中的容错单播路由进行分类： 基于局部信息的 基于有限全局信息的 基于扩展安全等级模型的

4.10.3 基于扩展安全等级模型的路由：安全向量 安全等级模型具有以下缺陷： 节点的安全等级为k仅说明在k海明距离中存在一个海明距离路径。并没有提供关于是否存在到达超过k海明距离的节点的海明距离路径。 安全向量的概念可以有效地引入失效链接的信息，并能提供系统中错误的数量和分布的信息

安全向量 特别地， 一个节点的安全向量可以通过在邻居节点中进行n-1轮信息交换来计算。 设(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维中确定一个优先级顺序。这个优先级顺序的信息决定了组播的结果。 优先级顺序的定义应该能够实现对路径的最大限度的共享从而使流量最小

使用安全等级的原因 在组播中，组播消息不应到达死端（dead end） 当一个特定目标节点的所有海明距离路径都被出错邻居阻塞时，死端就会出现在中间节点。 在这种情况下，为了到达那个目标必须绕道或回退。 为了避免尽头的出现，应该限制向附近有出错节点的邻居发送的目标的数目。 这就是在维度有限决策时使用安全等级的原因。

基于安全等级的组播 介绍三个方法 基于安全等级的组播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产生的组播一定是时间最优的。 或者等于相应的海明距离， 或者比相应的海明距离多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 的邻居）。 假定组播消息总是附加在从一个节点转发到另一个节点的目标节点的相对地址上面。 在R中剩余的节点中，r4和r6在第一位的值为1。地址r4(1)和r6(1)将被发往节点1001。 因为剩下的r1和r3的第四位的值是1，地址r1(4)和r3(4)将沿着维度4访问1000的邻居。

算法举例： 使用SLBM （cont'd） 没有目标节点被发往沿着维度3的邻居 对1000的收到目标节点的邻居节点递归使用这个步骤，可以产生一个如图的组播树。 树的深度就是所用的时间步数， 树中的边的数目是所用的流量步数。 本例，时间步数是4 流量步数是10

算法举例： 使用MSLBM MSLBM 也使用邻居维度序列（ds ）来决定优先级。 然而，当两个或两个以上的邻居具有同样的安全等级的时候，将由剩余目标节点的地址总和（as）来决出胜负。 上例中，源节点1000沿着维度1和2的两个邻居具有同样的安全等级。 根据as=5323， 沿维度2的邻居1010可承载2(as第二位的值)个目标节点 沿维度1的邻居1001可承载3个目标节点。 这样，1001就比1010有更高的优先级。 结果是 r4(1), r5(1), 和r6(1)被发往1001。 r2(2)被发往1010。

算法举例： 使用MSLBM （cont'd） r1(4)和r3(4)被发往沿着维度4的1000的邻居。 下图显示了具有4个时间步骤和9个流量步骤的组播树

算法举例： 使用ASBM 在ASBM中，维度优先级取决于目标节点的地址总和。 即在地址总和中具有最大值的那个维度具有最大的优先级。 在该维度的地址为1的目标将被发往相应的邻居。 然而，为避免向一个不安全或出错的邻居发送过多的目标，将目标地址发往一个k-安全的邻居仅当相应的目标节点与这个k-安全的邻居的海明距离小于或等于k。 当有两个或两个以上的邻居可承载相同最大数目的目标节点时，选择是随机的。 当然也可很容易地将ASBM扩展，从而可根据邻居的安全等级来进行选择。

本部分内容小结 基于局部信息的容错单播 基于有限全局信息的容错单播 安全等级的扩展：安全向量 容错组播：Wu的基于轨迹的模式 等位序列、空余维度 基于有限全局信息的容错单播 安全等级 安全等级的扩展：安全向量 容错组播：Wu的基于轨迹的模式 使用安全等级在超立方中进行容错组播 SLBM、MSLBM、ASBM