高级操作系统 Advanced Operating System 陈香兰（代） xlanchen@ustc.edu.cn 0551_3606864-83 中国科学技术大学计算机系

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

上次课主要内容（4小节） 4.1 分布式路由算法导论 4.2 一般类型网络的最短路径路由算法 进程间通信类型 通信延迟及其原因 路由算法分类 路由函数定义 4.2 一般类型网络的最短路径路由算法 Dijkstra集中式算法 Ford分布式算法 ARPAnet的路由算法

4.3 特殊类型网络的单播算法 4.4 特殊类型网络中的多播算法 双向环上的单播算法及其一般化 网格和圆环上的单播算法 超立方 2维网格的XY路由、适应性路由、折线路由等 超立方 基于海明距离的一种简单的路由算法 4.4 特殊类型网络中的多播算法 基于（哈密尔顿）路径 基于树的多播 应用于超立方的Lan的贪婪多播算法 U-网格算法

4.5 虚信道和虚网络 网络资源 网络通信中，若消息在占有资源的前提下可以申请资源，就有可能发生死锁 在存储转发交换中，资源是缓冲区； 在虫孔路由中，资源是信道。 网络通信中，若消息在占有资源的前提下可以申请资源，就有可能发生死锁 通过控制路由的自适应性可以预防和避免死锁，同时也保证一定的容错性。 虚信道和虚网络经常用于实现无死锁、自适应和（或）容错的路由。

4.5 虚信道和虚网络 通过网络分区避免死锁 通过网络分区可以避免死锁 举例说明： 给定的网络可以分成几个子网。 根据源和目标的位置，消息被路由到不同的子网 举例说明： 3X3网格的适应性双Y信道路由 如图： 在Y方向有两个物理信道 （双向） （a）一个3X3网格的 双Y信道网

4.5 虚信道和虚网络 通过网络分区避免死锁（cont'd） 上述网格被分成正、负两个子网（如下图） 如果目标位于源的右侧，则使用正网； 否则将使用负网。 当源和目标同列时，两个子网都不用。 由于两个子网中都没有回路，所以可避免死锁。 （b）正网络 （c）负网络

4.5虚信道和虚网络 虚信道 若网络没有双Y信道，则可用几个虚信道复用一个物理信道 若虚信道间没有循环等待，就可避免死锁。 每个虚信道都有自己的缓冲区。 当物理信道被其它虚信道使用时，就用这个缓冲区保存消息 若虚信道间没有循环等待，就可避免死锁。 假设上例改为单Y信道网，那么原来的正、负子网中所有的Y信道都是虚信道。

4.5虚信道和虚网络 虚信道（cont'd） 当两个虚信道共享一个物理信道时， 信道利用率大幅提高。 虽然虚信道提供了一个具有多重信道的网络，但仍需仔细设计路由算法。例如， 可以按照信道标记的升序使用虚信道，以便避免虚信道间循环依赖。

4.5虚信道和虚网络 虚网络 比虚信道更高一级的虚拟化是虚网络 一个给定的物理网络被分成几个虚网络，每个虚网络包括一系列的虚信道。 虚网络中相邻的节点被映射到物理网络中时也要相邻 一般地，一个虚网络中的虚信道设置应避免信道间的回路。虽然仍有可能存在互相交叉的虚网络回路，但可以通过使虚网络遵循全序或偏序来避回路 前面那个例子中，若使用单Y信道，则前面的正、负子网可认为是两个虚网络。 显然每个网络中都没有回路。因每个路由过程最多只使用一个虚网络，所以不会产生互相交叉的虚网络回路。

4.5虚信道和虚网络 虽然虚网络包含虚信道，二者是完全不同的概念。 一般地，虚信道的使用是与路由过程紧密相连的，包括源和目标的位置。必须合理安排虚信道，以避免死锁。 虚网络通常设计为没有回路，因而路由算法可以不必考虑死锁，除非存在交叉虚网络的依赖性

4.5虚信道和虚网络 虚信道举例 考虑一个有四个节点的单向环。如果同时有几个路由进程启动，就会发生死锁。

4.5虚信道和虚网络 虚信道举例（cont'd） 通过给每个链接增加两个虚信道可以避免死锁 如图，信道被分为 高虚信道，和 Ch0, Ch1, Ch2, Ch3 低虚信道 Cl0, Cl1, Cl2, Cl3

4.5虚信道和虚网络 虚信道举例（cont'd） 若源地址大于目标地址， 若源地址小于目标地址， 图示为相应的信道依赖图 可从任何一个信道开始； 但一旦使用一个高（低）信道，那以后也要使用同一信道 若源地址小于目标地址， 首先使用高信道，经过节点P3后，高虚信道切换为低虚信道 图示为相应的信道依赖图 以信道为节点 边为信道之间的切换关系 P3

4.5虚信道和虚网络 虚网络举例 在上述虚信道方法中，给定的环被分成 两个虚环：Vr1和Vr2 每个环中都有一个回路。 两个虚环： 虚环形成的回路。 图中，节点内的边表示 回路中信道的切换关系

4.5虚信道和虚网络 虚网络举例（cont'd） 要避免虚网络内部的回路，可以 在vr1中禁止从Ch0切换到Ch3，和 在vr0中禁止从Cl0切换到C13。 P3中， Ch0到Ch3的切换被禁止； Cl0到Cl3的切换也被禁止

4.5虚信道和虚网络 虚网络举例（cont'd） 可在任一步进行从vr1到vr0 的虚网络切换（如图） 例如 若源地址大于目标地址，如 从P2到P0的路由可以从Ch2开始，并在P1切换至Cl1 从P3到P0的路由中，可在P2或P1进行切换 也可以不切换 但若目标地址大于源地址，则必须在节点P3切换， 因为 在单向环中，若目标地址大于源地址， 则必然要经过P3路由 两个虚环都不允许在P3进行从Ch0到Ch3 和Cl0到Cl3 的切换。 所以在P3只能进行Ch0到Cl3的切换 图中， 每个节点都可以进行 vr1到vr0的虚网络切换

4.5虚信道和虚网络 虚网络举例（cont'd） 基于虚网络的路由过程比基于虚信道的路由有更强的适应能力。在上例中， 虚信道路由仅在P3进行高虚信道到低虚信道的切换 虚网络路由允许在任一点进行虚网络切换 为了保证从vr1到vr0的切换生成一个合法的路由路径， 若Cli是vr0中的切换信道，则i必须不能小于剩余的路由跳跃数。

4.5虚信道和虚网络 双环路由 上述每一个单向信道增加一个虚信道的方法叫双环路由 形式化地描述双环路由： 假定 使用n个进程：Pn-1,Pn-2,…P1, P0， 信道是Ch或Cl：

4.5虚信道和虚网络 双环路由算法

4.5虚信道和虚网络 双环路由 在上述算法中，当进程发起路由时， 如果i > des ，可以使用高信道或者低信道。

4.6 完全自适应和无死锁路由算法 适应性和无死锁是两个互相矛盾的要求。 因此，必须在不引发死锁的前提下增加适应性 像2 维网格的XY路由和n维立方的e-立方等决定性的无死锁路由虽然简单，但都不是适应性的。 一个决定性路由在存在错误组件（如链接或节点）的系统中有可能失效 例如，一个XY路由完成了X方向的路由，但在Y方向上由于错误被阻塞，这个信息就不能被继续转发 但没有限制的适应性路由可能引发死锁。 因此，必须在不引发死锁的前提下增加适应性

4.6 完全自适应和无死锁路由算法 几乎所有的完全适应性路由都可以通过增加一定数量的虚信道（或虚网络）来避免死锁。 例如， 一个最小化的适应性的n 维立方路由可以通过加入n个虚信道来避免死锁。 每一步都使用比前一个具有更高标记的信道。 因为需要n步，所以n个虚信道足以避免虚信道之间的循环等待。 然而使用虚信道会引入附加的缓冲区等开销。所以，要尽量限制虚信道的数目。

4.6.1 虚信道类 如前所述，通过引入足够多的虚信道，任何路由都可以保证避免死锁。 当路由开始时，使用虚信道1，vc1。 在第i 步使用虚信道i，vci及相应的链接。 如果一个给定网络的最长路径（也叫直径）是Dmax那么就要用Dmax个虚信道；

4.6.1 虚信道类 为了减少虚信道的数量，可将一个网络分成几个节点的子集，每个子集都不会包含相邻的接点。 例如， 考虑一个形似跳棋盘的2维网格，上面有黑白方格。 黑节点属于－个子集，白色节点属于另外一个。 当一个消息从一个白色节点移动到黑色节点时，就将虚信道的标记加一。 如果是从黑色节点向白色节点移动，虚信道标记保持不变。 显然，在2维网格中，节点标记的改变次数最多为路由步数的一半。这样虚信道的总数就缩减了一半。

4.6.1 虚信道类 可以将上述思想一般化： 将给定网络分成k个子集 S1, S2, … Sk ，每个子集都不包含相邻节点 当一个消息从子集Si中的一个节点移动到子集Sj中的一个节点（i < j ）时，称之为上移动；反之为负移动。 发生负移动时，虚信道标记加一 假定信道标记从1 开始 从而，所需信道的个数就是一个路由路径中负移动的个数。 目标就是要选择一个合适的k以及一个划分，使路由过程中的负移动个数最小

4.6.2 逃逸信道 等待和非等待信道 使用逃逸信道的路由算法中，虚信道被分为 等待信道（又称为逃逸信道）和 非等待信道（又称为一般信道） 若一个等待信道处于繁忙状态，而此时一个消息需要通过该信道，则这个消息必须等待，直到该信道可用 即一个等待信道能够阻塞消息 非等待信道（又称为一般信道） 若一个消息碰到一个处于繁忙状态的非等待信道，它不必被阻塞以等待该信道变得可用，可以选择其他信道 因此，一个消息会首先考虑通过非等待信道到达目标 若所有的非等待信道都繁忙，它就考虑等待信道

4.6.2 逃逸信道 混合路由 使用逃逸信道扩展完全适应的概念 例如，可以用两个路由进程实现混合路由： 路由进程1：完全适应性路由， 使用标记为非等待的虚信道； 路由进程2：限制性但无死锁路由 可能是XY路由或e-立方等决定性路由 使用标记为等待的虚信道。

4.6.2 逃逸信道 混合路由（cont'd） 混合路由算法： 混合路由是无死锁的 合理分配等待和非等待信道是关系到混合路由效率的关键问题 开始时，使用完全适应路由，直到阻塞为止； 然后切换到限制性路由。 混合路由是无死锁的 由于等待信道是在无死锁路由中定义的，并且 消息仅仅等待上述等待信道 合理分配等待和非等待信道是关系到混合路由效率的关键问题

4.6.2 逃逸信道 混合路由的扩展I 扩展I：当消息发现等待信道被占用时，可以使用非等待信道 通过使用一个或多个中间的一般信道，一个逃逸信道可能间接地依赖于另一个逃逸信道。 因此无回路条件必须包括逃逸信道之间的所有间接依赖。 不幸的是，没有循环依赖只是不发生死锁的一个充分条件；也即，对于一个特定的虫孔网络，若使用某一个路由算法，扩展I太弱，不会得到任何结果。扩展信道依赖图中的一个回路可能表示一个死锁状态，也可能不是。

4.6.2 逃逸信道 混合路由的扩展I I Duato通过使用基于消息目标的逃逸路径进一步扩展了上述思想 对于不同的目标，使用不同的逃逸信道。 在同样的无回路条件下，可以得到一个无死锁的充分必要条件。 然而，在生成扩展信道依赖图的时候，直接依赖、间接依赖、直接交叉依赖（在不同目标的逃逸信道之间）和间接交叉依赖都要被考虑进去。

4.6.2 逃逸信道 上述两个扩展都可用于避免死锁。 为了设计一个无死锁的路由函数，首先创建一个名为R1(x,y)的路由子函数，它的功能是将当前和目标节点映射到当前节点的输出信道的子集。R1(x,y)是连通的，无回路的。可以通过增加信道或者将已有信道分割为虚信道将R1(x,y)扩展为R(x,y)，以便增加可选路径的数目，同时又不会在R1(x,y)的扩展信道依赖图中增加回路。 这一设计规程又被称为Duato协议。

4.6.2 逃逸信道 维度逆转路由 如果不要求最小路由，那么虚信道的数量还可以减少。 对于一个k元n维立方（没有环绕连接），有如下的一般非最小无死锁路由： 对每个物理信道，有k个虚信道与之对应 其中一个用于逃逸信道，以便进行无死锁的按维排序的路由 消息可以按照任何方向路由，而不一定是最小路径。 每个消息都有一个维度逆转数DR相对应， DR：记录消息从高维度路由到低维度的次数。

4.6.2 逃逸信道 维度逆转路由（cont'd） 一旦一个消息取得一个信道，它就将该信道标记为当前的DR数。 为了避免死锁，一个DR数为i的消息不能等待一个DR数为j的信道，这里i≤j。 此时，选用下一层的虚信道。 假定每个未被访问的信道的DR标记为0。 当虚信道的标记达到k时，就使用决定性的按维度排序的路由。

4.7 几个部分适应和无死锁路由算法 很多路由算法的路由适应性仅对一小部分虚信道有效。这种算法属于部分适应性路由 本节讨论三个部分适应性和无死锁路由算法 转弯模型 平面自适应模型 其他部分自适应模型

4.7.1 转弯模型 2维网格的转弯模型提供了一个部分适应性和无死锁的路由。 下图显示了2维网格中的抽象回路。

4.7.1转弯模型 基本思想 上图显示了XY路由中所允许的四个转弯（实心箭头所指）。 方 向 X方向 上图显示了XY路由中所允许的四个转弯（实心箭头所指）。 只允许先X方向路由后Y方向路由 显然，这个条件太严格了，因为可以通过去掉回路中的一个角来打破回路。 转弯模型的基本思想 通过禁止最小数目的转弯来增加适应性，以避免回路。

4.7.1 转弯模型 正向优先协议和负向优先协议 左下图为一个正向优先路由协议。 右下图为一个负向优先路由协议。 可以有6个转弯 从负向到正向的转弯，也即南到东和西到北，被禁止 右下图为一个负向优先路由协议。 从正向到负向的转弯，也即北到东和东到北，被禁止 X正到Y负 Y正到X负 Y 方 向 X负到Y正 Y负到X正 正向优先协议 负向优先协议 X方向

4.7.1 转弯模型 转弯模型的适应性 由于源和目标的位置的不同，转弯模型可能有适应性，也可能没有。 下图显示了源s和目标d的两种不同位置。 若目标位于源的东北或西南方，那么正向优先路由就是完全适应性的，如图a 否则，就是决定性的，如图b OK Not OK 东北 东南 （a）完全适应性路由 （b）确定性路由

4.7.1 转弯模型 转弯模型的平衡性 某些情况下，上述不平衡的适应可能会导致拥塞或不平衡的工作量。 可以使用虚信道将几种不同的协议结合起来。每个协议都是基于转弯模型，但有不同的区域适应性，因而可以得到一种平衡的方法。 例如，若允许使用两个虚信道，就可设计两个具有互补适应性的转弯模型。

4.7.2 平面自适应模型 对应于一般的k元n维立方，Chien和Kim提出了一种部分适应性和无死锁的路由。 基本思想是： 在某一时刻将路由的自由度限制到儿个维度以降低对硬件（虚信道）的要求。 例如， 若每次只选两个维度， 就有A0, A1,…, An这些平面， 其中Ai在维度di和di+1方向扩展。

4.7.2 平面自适应模型 举例 下图显示了三个平面的例子： A0（维度为d0和d1）， A1（维度为d1和d2），和 A2（维度为d2和d3） 平面自适应路由所允许的路径

4.7.2 平面自适应模型 举例 对每个Ai，引入三个虚信道， 设di,j是维度j通过维度i的虚信道。 Ai使用三个虚信道： di,2 、 di+1,0和 di+1,1

4.7.2 平面自适应模型 由于每个虚信道都是双向的，可将di,2分成两个单向信道di,2+和di,2- Ai也就被分成两个子网： 包含di,2+和di+1,0的正向子网；以及 包含di,2-和di+1,1的负向子网 本课开始的正负子网可看成是上述正向和负向子网的例子： 将X和Y视为di和di+1 负网络 正网络

4.7.2 平面自适应模型 Ai内部的路由可依据源和目标的位置不同而选用正向或负向子网。 注意： 若目标的标识大于源标识，则选用正向子网； 否则，选用负向子网。 注意： 虚信道di, di,0, di,1中的另外两个也用于平面Ai-1，即相邻平面有一个公共维度。 相对于完全适应而言，平面适应方法牺牲了一些路由自由度（适应性），从而大大降低了虚信道的数目。

4.7.3 其他部分自适应模型 Li出了e-立方路由的一个要求稍低的版本。 其中一个链接是从第i 位为0 的节点到第i 位为1 的节点（负向链接） 另一个是从第i 位为1的节点到第i位为0 的节点（负向连接）。 为了打破一个回路，只需禁止从较高维度的正向连接向沿着维度i的负向连接转换即可，除非这个转换符合e立方路由。

4.7.3 其他部分自适应模型 如果e立方路由满足维度递增的顺序，一个沿着维度dim(c1)的信道c1到一个沿着维度dim(c2)的信道c2的转换是允许的当且仅当下述条件中的一个为真： dim(c1)<dim(c2)，或 c2是正向的 假定维度是从右向左编号的，即最右边的一位对应于维度1。 按照上述规则， 变换(10010, 00010)(00010, 00000)是不允许的； 变换(10010, 10110)(10110 , 00110)是允许的。

4.7.3 其他部分自适应模型 一个基于扩展转弯模型的类似模型可以用于n维立方。 假定s=snsn-1…s1和d=dndn-1…d1是源和目标节点 设S是s和d所不同的维度的集合。 S被分为S1（正向转换集合）和S2(负向转换集合）。 如果si=0且di =1则i属于S1 如果si=1且di=0则i属于S2 路由分成两个阶段。 阶段1：消息按任意顺序沿集合S1中的维度路由； 阶段2：消息按任意顺序沿集合S2中的维度路由。

4.7.3 其他部分自适应模型 例如， 如果s=0101, d=1010， 那么S1={2, 4}；S2={1, 3} 下面的路由路径是合法的 01011101111110111010 01010111111110111010 01011101111111101010 01010111111111101010

4.7.3 其他部分自适应模型 n维立方中，任何回路都至少有一个从正向到负向和一个从负向到正向的转换。禁止这种转换可避免死锁 上述模型中，只有从正向到负向的转换是允许的。 为评价适应性，仍使用上述S、S1和S2的定义，则 在一个完全适应性的路由算法中,有lSl!种不同的路由选择 使用扩展转弯模型时，为|S1|!|S2|! 上例中：s=0101, d=1010，有|S|=4, |S1|=2, |S2|=2 使用完全适应性路由算法有|S|!=4!=24种路由选择 使用扩展转弯模型有|S1|!|S2|!=2!2!＝4种路由选择

4.7.3 其他部分自适应模型 2维网格中基于起源的路由 基于起源的路由是XY路由在2 维网格中的一个扩展 一个起源节点o是预先选定的（如图） 路由分成两个阶段 阶段1： 从源s到起源节点o 阶段2： 从起源节点o到目标节点d

4.7.3 其他部分自适应模型 2维网格中基于起源的路由 网络被分成两个子网。 IN子网包括所有指向起源节点o的单向信道 OUT子网包括所有离开起源节点o的单向信道 路由的第一阶段使用IN子网 第二阶段使用OUT 子网 图中仅显示了IN子网。 将图中的每个链接反向 可得到OUT子网。

4.7.3 其他部分自适应模型 2维网格中基于起源的路由 为了对源s和目标d决定这两个阶段的临界点，建立一个outbox outbox 是一个以起源节点o和目标节点d为对角顶点的矩形。 实际上，outbox 是一个包含 了所有位于目标节点d和起源 节点o之间的最短路径上的节 点的子网。 确切地说，基于起源的路由 将使用IN子网将消息向 目标节点d 转发； 一旦消息到达outbox 边界， 就将切换为OUT 子网。

4.8 容错单播：一般方法 随着分布式系统中处理器数量的增多，处理器失效的可能性也会加大。所以， 路由算法应该在处理器失效时仍然有效。 但仍要达到一定程度的适应性，同时也要保证无死锁。 在通过增加（或删除）节点和/或链接来达到容错方面已经做过许多研究。 然而，这需要更改网络拓扑，而这很昂贵、很困难。 在这里将重点放在通过使用网络中已有的冗余来达到容错，而不会增加空节点和/或链接。

4.8 容错单播：一般方法 在设计路由算法之前，需要确定下面几点： 最短路径或非最短路径。 错误类型：链接错误，节点错误，或者链接错误和节点错误都有 出错的组件的个数是有限的还是无限的 对错误分布的了解：局部、全局和有限的全局 冗余或非冗余 回退或者前进

4.8 容错单播：一般方法 最短路由路径需要有在出错情况下工作的最优路由。这一要求对于非最短路径路由是可以放松的，因为对后者而言，非最短路径也是可以接受的。 链接错误和节点错误是不同的。典型情况是， 当一个节点失效时，它周围的链接也被认为失效了。 然而，如果一个节点周围的一个或多个链接失效，那么只要这个节点没有被孤立，它就仍然是好的。

4.8 容错单播：一般方法 失效组件的数量 失效的组件（节点或链接）的数量在设计容错路由算法时具有重要地位。 一般地，设计一个可以经受有限（或恒定）数日的故障的路由算法是相对容易的。

4.8 容错单播：一般方法 错误分布信息的了解 对于错误分布的了解决定了路由算法的效率。典型地， 基于局部信息的路由不能达到最优，因为它对系统的了解是有限的。 如果能够得到全局信息，就有可能达到最优。当然要有一个单独的进程按时收集信息。 有限全局信息是介于局部和全局信息之间的一个平衡

4.8 容错单播：一般方法 冗余 or 非冗余 可以利用冗余路由来很容易地获得容错路由。 如果消息的k 个拷贝通过节点分离路径发往目标，就可以经受至少k-1个错误。 但，即使系统中没有错误，通信量也会因此增加k-1倍。 非冗余方法仅仅发送消息的一个拷贝，并通过绕过故障而将消息转发到目标。

4.8 容错单播：一般方法 回退 or 前进 前进型协议会等待、中止或者选择错误的路径，但是方向始终是向前的，而不会回到上一个节点重新开始。 前进式路由在虫孔路由中很重要，因为这种路由不允许回退。 有一种叫做流水线电路交换的路由方法扩展了虫孔路由，可以允许回退。 回退协议认为与其等待一个可用的路径，不如去找其他路径。 [18 ]中针对虫孔网络提出了一个容错路由理论。在这个理论中，Duato 将互连性和无死锁联系起来，分析了虫孔网络的容错性。

4.9 2维网格和圆环中的容错单播 根据路由过程中使用的故障信息，本节考虑如下几种容错路由算法： 基于局部信息 基于有限全局信息 基于其他故障模型

4.9.1 基于局部信息的路由 许多适应性路由算法，例如转弯模型，可以经受一个有限数量的故障（如k 元n 维立方中为n一1 个故障）。 2 维网格中，若源和目标都有四个邻居，那么2 维网格的冗余路由可以至少经受三个错误（链接和/ 或节点）。 为了能够承受更多的错误，通常使用错误区域的概念。 若错误区域是一个凸形，就有可能设计一个简单的容错和无死锁路由 对于凹形，可以在区域中加入一些非错误节点，从而将其转变为凸形

4.9.1 基于局部信息的路由 基本安全/非安全定义 安全/非安全节点的定义： 所有错误节点都是不安全的。 所有非错误节点开始时都是安全的。 如果一个非错误节点有两个或两个以上的非安全邻居，那么它的状态就变为非安全的。

4.9.1 基于局部信息的路由 基于基本安全/非安全定义的出错块 下图显示了一个出错块的例子 红色节点是错误节点 黑色节点代表非错误但不安全的节点。 易证，错块是分离的 且它们的距离最少是3

4.9.1 基于局部信息的路由 扩展安全/非安全定义 为减少出错块中非出错节点的数目，对上述安全/非安全定义进行如下扩展： 所有错误节点都是不安全的。所有非错误节点开始时都是安全的。 若一个非出错节点在两个维度上都有错误的或不安全的邻居，它的状态就变为非安全的

4.9.1 基于局部信息的路由 基于扩展安全/非安全定义的出错块 下图为对上述同一个例子使用扩展安全节点概念的结果 图中有两个分离的出错块。 可以证明两个出错块之间 的距离最少为2 。 然而，出错块中所包含的 非错误节点的总数比基于 基本的安全非安全定义的 出错块要少。

4.9.1 基于局部信息的路由 基于出错块的路由 对2 维网格或圆环的路由可进行如下扩展： 若没有因错误阻塞，就按无错的情况路由。 若在X维（或Y维）阻塞，就在Y维（或X维）路由 若因错误在X维受到阻塞，而Y维度的距离已接近零，就有必要进行曲折路由。 随便选择一个Y方向，开始曲折路由。 首先试着从X维度到达目标。 继续沿着X方向，直到Y方向正确为止。 即沿着出错块的边缘路由。 Y 维度的出错块可用类似的方法处理。

4.9.1 基于局部信息的路由 基于出错块的路由——举例 下图是一个沿着凸形错误区域路由的例子。 注意： 消息可能会在凹形出错区域受到限制。

4.9.1 基于局部信息的路由 基于出错块的路由——举例 当消息沿着凸起的出错块移动时，一个维度（X或Y）总是单调增加或减少。 注意凹陷的出错块没有这个特性。 所以每个路由都可呆在正向子网或负向子网，正如平面适应路由中那样。 因此无需引入更多的虚信道，可以在这里使用与平面适应路由同样的算法。即， 在n维(n>0)网中，使用三个虚信道来避免死锁。 对n维圆环，每个环绕信道需要两个虚信道来打破同一个维度中的回路。总之，对n(n＞0)维圆环需要6 个虚信道。 2 维网格中，使用两个虚信道，网络被分成正/负向两个子网。 类似地，在2 维圆环中，使用4个虚信道。

4.9.2 基于有限全局信息的路由 Wu的最优容错路由算法 首先，他证明：设节点(0, 0)是源节点，节点(i, j)是目标节点。若没有出错块通过X和Y轴，那至少存在一个始于(0, 0)的最优路径，长度为|i|+|j| 。 在一给定的2维网格中，上述结果对任意位置的目标节点和任何数目和分布的出错块都成立，相应的源叫做安全的。 上述结果可以进一步扩展：允许X和Y轴有出错块，只要它们到源的距离分别大于|i|和|j|。这样的源节点叫做扩展安全的。

4.9.2 基于有限全局信息的路由 Wu的最优容错路由算法 有两个最优和适应性容错的路由算法： 面向目标路由，和 面向源路由。 为简单起见，假定 源节点是(0, 0)， 目标节点是(i, j)，且i, j >=0， 即路由永远是向东北方向的。

4.9.2 基于有限全局信息的路由 面向目标的路由 面向目标的路由使用最短路径区域RMP的概念： 为建立RMP 做一条从目标节点(i, j)开始到Y轴结束的线。 遇到出错块时，先向南绕过出错块，然后继续向西 类似地，建立一个从(i, j)开始向南到X轴截止的线。 遇到出错块时，先向西绕过出错块，然后继续向南。 已经证明由向西和向南的线以及X轴和Y轴围起来的区域是RMP。

4.9.2 基于有限全局信息的路由 面向目标的路由——举例 下图显示了一个RMP的例子， 这里向西的线标记为路径A， 向南的线标记为路径B。

4.9.2 基于有限全局信息的路由 面向目标的路由 仅当源是扩展安全的，才使用面向目标路由 源通过一个最优或不是最优的路径向目标发一个信号 接到信号后目标发两个信号，一个向西一个向南 向西的信号建立RMP的路径A， 向南的信号建立RMP的路径B 。 一旦源收到来自目标的两个信号，就意味着RMP已建立起来。源就用任何一种适应性最小路由发送路由消息。 遇到路径A（或路径B）的边界时，剩下的路由就要沿着路径A （路径B ）发往目标。

4.9.2 基于有限全局信息的路由 面向源的最优路由 为支持面向源的最优路由，必须把出错块的信息分布到系统中的特定节点上。 举例说明：下图显示了一个出错块 L1, L2, L3, L4 与出错块的四条线平行 x>=0和y>=0的区域被 分成8 个子区域：R1~R8 L1~4上的点可划归任一 相邻区域。

4.9.2 基于有限全局信息的路由 面向源的最优路由（cont'd） 显然， 可用任一最小路由算法到达R1, R2, R3 , R7, R8中的点 可用XY路由（先X后Y）到达R6中的任何点。 可用YX路由（先Y后X） 到达R4中的任何点。 用XY路由和YX路由都 可到达R5 中的点。

4.9.2 基于有限全局信息的路由 面向源的最优路由（cont'd） 当目标节点位于R4或R6时，为达到最优路由，位于L1（位于(x,y)西侧的节点）和L2（位于(x,y)南侧的节点）上的特定节点必须具有这个出错块的信息。这些信息可以用出错块的相应角的位置来编码。 特别地，为每个出错块 建立两个概念上的路径 路径1（虚线）： (∞,y’)(x’,y’)(x’,y) (x,y)(- ∞,y) 路径2（实线）： (x’, ∞)(x’,y’)(x,y’) (x,y)(x,- ∞)

4.9.2 基于有限全局信息的路由 面向源的最优路由（cont'd） 显然， 目标位于路径1的南侧或东侧的路由消息不能通过路径1。 目标位于路径2的北侧或西侧的路由消息不能通过路径2。 路径1的路径信息存储在(-∞,y)到(x,y)间的每个节点上 路径2的路径信息存储在点 (x,-∞)到(x,y)间的每个节上 为最小化路径信息，只有每 个转弯（出错块的角落）的 位置是必要的。 所以(x’,y)和(x’,y’)对路径1是 必要的，而(x, y’)和(x’, y’)对 路径2是必要的。

4.9.2 基于有限全局信息的路由 面向源路由的步骤 面向源路由的步骤： 首先使用任何一个适应性最小路由， 直到遇到出错块的一个（路径1或路径2）为止。 （遇到路径1的L1） 若目标节点在路径1的南/东侧， 那消息将一直留在L1直到到达 出错块的L1和L4的边界为止； 否则将穿过L1。 （遇到路径2的L2） 若目标节点在路径2的北/西侧， 那消息将一直留在L2直到到达 出错块的L2和L4的边界为止； 否则将穿过L2。

4.9.2 基于有限全局信息的路由 面向源路由的步骤（cont'd） 上述方法中，两个虚信道足以避免死锁。 一个简单的方法是 为东北和东南方向的路由使用正向子网， 对西北和西南方向的路由使用负向子网。

4.9.3 基于其他故障模型的路由 Wu的直角凸多边形模型 虽然矩形出错块很简单，但它引入了很多被禁止的非出错节点，即它们将不会在路由过程中起作用。 但矩形为凸形的特性使得可以用最少的虚信道把路由信息绕过出错区域。 另外一些非矩形的凸形出错块也被引入了。 Wu将出错块模型扩展为直角凸多边形模型。 一个凸多边形的定义是： 多边形P，P中的任意两点之间的线段都在P内部。 在直角凸多边形中，线段被限制为只能是水平或垂直的。

4.9.3 基于其他故障模型的路由 直角凸多边形 可以将给定的矩形出错块转换为一系列分离的直角凸多边形 这一思想根源于这样一个事实： 可以通过将出错块中的一些非出错节点移出去，从而将它们激活，同时又保持这个区域的凸性。

4.9.3 基于其他故障模型的路由 活跃/不活跃节点 与标准出错块中的安全/非安全定义不同，Wu给出了活跃/不活跃节点的概念： 所有出错节点都是非活跃的，所有安全节点都是活跃的。 一个非安全节点开始的时候是非活跃的．但如果它有两个或两个以上的活跃邻居，那么它就可以称为活跃的。 因此，对于一个非出错节点，有三种可能情况： 安全且活跃。 非安全但活跃。 非安全且不活跃。

4.9.3 基于其他故障模型的路由 活跃/不活跃节点举例 下图是将wu的活跃/不活跃规则用于图7-7的出错块的结果。 显然，结果是一个直角凸多边形。

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 基于局部信息的模型 第1种情况——等位序列定义 考虑一个第1种情况的算法。 为了容错，一些访问过的节点也保存在消息中。 定义：等位序列[d1, d2, …, dk] 为当前节点与目标节点不同的所有维度（也叫首选维度，preferred dimension） 例如， 假设0010和0111是当前节点和目标节点， 那相应的等位序列就是[1,3] 为表示一个消息的目标，等位序列要和消息一起传送 因当前节点会随着消息的传递而变化，故等位序列也随着变化

4.10.1 基于局部信息的模型 第1种情况——消息的表示 每个消息都有一个n位向量标志，用以保存“空余维度(Pare 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。 在u=0110处的最初消息是(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-安全的节点就是不安全的

安全等级的定义及计算 n维立方中，令节点a的所有邻居节点的安全等级的非递减安全状态序列为： (S0, S1, S2, …Sn-1)， 0<=Si<=n且0<=Si<=Si-1<=n-1， 那么有：节点a的安全状态定义如下 如果(S0, S1, S2, …Sn-1)>=( 0, l, 2, …n-1)， 那么s(a) ＝n； 否则，如果(S0, S1, S2, …Sk-1 )>=( 0, l, 2, …k-1)并且(Sk=k-1)，那么S(a)=k。

安全等级的计算算法 下述算法决定了每个节点的状态。 每个节点a(i)都保存它所有邻居节点的非递减安全状态序列 开始时，所有非出错节点都是n-安全的。 该算法需要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}

安全等级的性质和 基于安全等级的路由 安全等级有以下性质： 确切地说，节点的安全等级不仅提供了它的路由能力，也提供了路由信息。 如果一个节点的安全等级是k (0<k<=n)，那么在k海明距离内，至少存在一个从该节点到任意节点的海明距离路径。 确切地说，节点的安全等级不仅提供了它的路由能力，也提供了路由信息。 当源的安全等级大于源和目标之间的距离的时候，就可以保证最优路由。 实际上，可以在每一步通过选择具有最高安全等级的邻居来产生最优路径。 一个引导向量（定义为当前节点和目标节点的按位异或）被附加在路由消息上。

基于安全等级的路由举例 在此考虑图7-13 的例子 每个圆圈（节点）中的数字表明了该节点的安全等级。 考虑以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的安全等级小于s和目标d间的距离|s⊕d|时

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

安全向量 特别地， 一个节点的安全向量可以通过在邻居节点中进行n-1轮信息交换来计算。 设(a1, a2, …, an)是n维立方中节点a的安全向量 如果ak=1，则存在一个从a到任意一个k海明距离的节点的海明距离路径。 一个节点的安全向量可以通过在邻居节点中进行n-1轮信息交换来计算。 如果源节点的安全向量的第k位为1，那就可以在这两个节点间实现最优单播路径。 一个出错节点的安全向量是(0, 0, …, 0)。

安全向量（cont'd） 对于个非出错节点a, 设 a的安全向量是(a1, a2, …, an), a在维度i上的邻居的安全向量是(a1(i), a2(i), …, an(i)) 若节点a是一个出错链接的端节点， 那在相邻的其他端节点看来，a的安全向量是(0, 0, …, 0)且 以及 a到相应端节点的海明距离为1， 但不存在到该端节点的距离为1 的路径

4.10.3 基于扩展安全等级模型的路由：安全向量 计算安全向量的方法与通过节点之间交换信息和邻居之间互相更新而计算安全等级的方法类似。 路由算法和基于安全等级模型的方法也类似。

4.11 容错组播 如前所述， 在没有出错组件的情况下，网和超立方中的大部分组播问题都是NP完全问题。 本节 在出现错误的情况下，问题变得更复杂。 一般会使用启发性方法。 本节 再一次使用n维立方来说明不同的方法。 仅考虑系统中的单一组播

4.11.1 一般方法 超立方中的组播 已经证明 在超立方中找到一个时间和流量都最优的组播方案是NP完全问题。 由Lan 、Esfahanian和Ni提出的启发式组播算法实现了无错超立方中的时间最优化和局部流量最优化。 这个算法从源节点出发，在每一组中间节点都执行，并将分区中的每个子集发送给适当的邻居。 分区的划分使得目标节点仅仅发送给几个邻居，从而使沿着从源到目标的最短路径的共同路径得到最大的共享。 最后，所有目标节点关于这个中间节点的相对地址的和被算出来。 目标沿着维度，比如维度i被发往一个邻居节点，仅当地址总和中的i位在那些在该目标的相对地址中值为1的位中有最大值时。

4.11.1 一般方法 几种容错组播方案已经被提出来，可以按照每个节点使用的网络信息对它们进行分类 在Lan提出的基于局部信息的组播中： 每个节点仅知道它的相邻节点和链接的状态。 算法的最大优点是简单，虽然在最坏的情况下需要的时间步数可能会达到不能控制的程度。 [27]提出了一个可以划归基于局部信息的组播算法 实现了时间最优化 然而它基于限制性错误模型： 立方中的每个节点最多有一个出错邻居。

4.11.1 一般方法 基于全局信息的组播： 基于有限全局信息的组播是上述两种方案的综合。 假定每个节点都知道网络中的错误分布。 可以保证时间最优。 然而，它需要一个复杂的收集全局信息的过程。 基于有限全局信息的组播是上述两种方案的综合。 可以得到一个最优或次优的方案 同时可以使收集和维护全局信息的过程相对不是很复杂 Liang, Bhattacharya和Tsai提出了组播方案， 该方案基于有限全局信息的一个特例 每个节点知道两个跳跃之内所有链接的状态 这个方案可以经受n-1个错误链接，在最坏情况下额外的时间步数为2n。

4.11.2 基于路径的路由 原因：禁止路由分叉 在使用树结构的特定系统中 在路由过程中复制路由消息是很低效的。 而且，如果树形结构的一个树枝阻塞，那么路由就被阻塞。 对于长消息这个问题更为严重。 需要一个禁止在路由过程中分叉的方法，比如基于路径的路由（参见4.4，使用哈密尔顿回路/路径）。

4.11.2 基于路径的路由 双信道模型中基于路径的路由 在Lin等人提出的基于路径的路由中，使用了双向信道模型，即每个信道都是双向的 这一方法根源于在网络中找到一个哈密尔顿路径。 所有的路由步骤都遵从选定的哈密尔顿路径（在两个方向）。 显然，这样避免了循环等待和死锁。 每个（有序的）源和目标对在路径的一个方向上出现。 注意基于路径的路由不是最小化的， 它适用于源节点和目标之间的距离可以忽略的虫孔路由 为进一步减小路由路径的长度，消息可以在分离的路径上路由，正像2维网格中的多路径组播路由那样。

4.11.2 基于路径的路由 双信道模型中基于路径的路由 Tseng和Panda对Lin的方法进行了一般化和改进，使它更加能够适应错误，并且网络也不一定要包含哈密尔顿路径。 Robinson 、McKinley 和cheng将基于路径的路由扩展到圆环上。

4.11.2 基于路径的路由 半双工信道模型 系统使用半双工信道时，信道可以在两个方向发送信息，但是同时只能有一个方向发送。 4.11.2 基于路径的路由 半双工信道模型 系统使用半双工信道时，信道可以在两个方向发送信息，但是同时只能有一个方向发送。 用于双向链接的哈密尔顿路径方法就不再适用了。 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

4.11.2 基于路径的路由 Wu的基于轨迹的模式：充要条件 假定vi和vj在轨迹中仅仅出现两次。 显然(vj,vi)不是这个轨迹上的一个可行的路由。 因此，问题的充要条件如下： 对于一个任意给定的节点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扩展，从而可根据邻居的安全等级来进行选择。

本次课的主要内容 虚信道和虚网络 完全自适应和无死锁路由算法 几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法