高级操作系统AdvancedOperatingSystem.ppt

《高级操作系统AdvancedOperatingSystem.ppt》由会员分享，可在线阅读，更多相关《高级操作系统AdvancedOperatingSystem.ppt（140页珍藏版）》请在三一办公上搜索。

1、高级操作系统Advanced Operating System,熊焰0551_3600689中国科学技术大学计算机系,第二章 分布式路由算法,分布式路由算法导论一般类型网络的最短路径路由算法 特殊类型网络的单播算法特殊类型网络中的多播算法虚信道和虚网络 完全自适应和无死锁路由算法几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法超立方中的容错单播算法容错组播算法,2.5 虚信道和虚网络,网络资源在存储转发交换中，资源是缓冲区；在虫孔路由中，资源是信道。网络通信中，若消息在占有资源的前提下可以申请资源，就有可能发生死锁通过控制路由的自适应性可以预防和避免死锁，同时也保证一

2、定的容错性。虚信道和虚网络经常用于实现无死锁、自适应和（或）容错的路由。,2.5 虚信道和虚网络通过网络分区避免死锁,通过网络分区可以避免死锁给定的网络可以分成几个子网。根据源和目标的位置，消息被路由到不同的子网举例说明：3X3网格的适应性双Y信道路由如图：在Y方向有两个物理信道（双向）,（a）一个3X3网格的 双Y信道网,2.5 虚信道和虚网络通过网络分区避免死锁（contd）,上述网格被分成正、负两个子网（如下图）如果目标位于源的右侧，则使用正网；否则将使用负网。当源和目标同列时，两个子网都不用。由于两个子网中都没有回路，所以可避免死锁。,（b）正网络,（c）负网络,2.5虚信道和虚网络虚

3、信道,若网络没有双Y信道，则可用几个虚信道复用一个物理信道每个虚信道都有自己的缓冲区。当物理信道被其它虚信道使用时，就用这个缓冲区保存消息若虚信道间没有循环等待，就可避免死锁。假设上例改为单Y信道网，那么原来的正、负子网中所有的Y信道都是虚信道。,2.5虚信道和虚网络虚信道（contd）,当两个虚信道共享一个物理信道时，信道利用率大幅提高。虽然虚信道提供了一个具有多重信道的网络，但仍需仔细设计路由算法。例如，可以按照信道标记的升序使用虚信道，以便避免虚信道间循环依赖。,2.5虚信道和虚网络虚网络,比虚信道更高一级的虚拟化是虚网络一个给定的物理网络被分成几个虚网络，每个虚网络包括一系列的虚信道。

4、虚网络中相邻的节点被映射到物理网络中时也要相邻一般地，一个虚网络中的虚信道设置应避免信道间的回路。虽然仍有可能存在互相交叉的虚网络回路，但可以通过使虚网络遵循全序或偏序来避回路前面那个例子中，若使用单Y信道，则前面的正、负子网可认为是两个虚网络。显然每个网络中都没有回路。因每个路由过程最多只使用一个虚网络，所以不会产生互相交叉的虚网络回路。,2.5虚信道和虚网络,虽然虚网络包含虚信道，二者是完全不同的概念。一般地，虚信道的使用是与路由过程紧密相连的，包括源和目标的位置。必须合理安排虚信道，以避免死锁。虚网络通常设计为没有回路，因而路由算法可以不必考虑死锁，除非存在交叉虚网络的依赖性,2.5虚信

5、道和虚网络虚信道举例,考虑一个有四个节点的单向环。如果同时有几个路由进程启动，就会发生死锁。,2.5虚信道和虚网络虚信道举例（contd）,通过给每个链接增加两个虚信道可以避免死锁如图，信道被分为高虚信道，和Ch0,Ch1,Ch2,Ch3低虚信道Cl0,Cl1,Cl2,Cl3,2.5虚信道和虚网络虚信道举例（contd）,若源地址大于目标地址，可从任何一个信道开始；但一旦使用一个高（低）信道，那以后也要使用同一信道若源地址小于目标地址，首先使用高信道，经过节点P3后，高虚信道切换为低虚信道图示为相应的信道依赖图以信道为节点边为信道之间的切换关系,P3,2.5虚信道和虚网络虚网络举例,在上述虚信

6、道方法中，给定的环被分成两个虚环：Vr1和Vr2每个环中都有一个回路。,两个虚环：Vr1：高信道形成的虚环Vr0：低信道形成的虚环,虚环形成的回路。图中，节点内的边表示回路中信道的切换关系,2.5虚信道和虚网络虚网络举例（contd）,要避免虚网络内部的回路，可以在vr1中禁止从Ch0切换到Ch3，和在vr0中禁止从Cl0切换到C13。,P3中，Ch0到Ch3的切换被禁止；Cl0到Cl3的切换也被禁止,2.5虚信道和虚网络虚网络举例（contd）,可在任一步进行从vr1到vr0 的虚网络切换（如图）例如若源地址大于目标地址，如从P2到P0的路由可以从Ch2开始，并在P1切换至Cl1从P3到P0

7、的路由中，可在P2或P1进行切换也可以不切换但若目标地址大于源地址，则必须在节点P3切换，因为在单向环中，若目标地址大于源地址，则必然要经过P3路由两个虚环都不允许在P3进行从Ch0到Ch3 和Cl0到Cl3 的切换。所以在P3只能进行Ch0到Cl3的切换,图中，每个节点都可以进行vr1到vr0的虚网络切换,2.5虚信道和虚网络虚网络举例（contd）,基于虚网络的路由过程比基于虚信道的路由有更强的适应能力。在上例中，虚信道路由仅在P3进行高虚信道到低虚信道的切换虚网络路由允许在任一点进行虚网络切换为了保证从vr1到vr0的切换生成一个合法的路由路径，若Cli是vr0中的切换信道，则i必须不能

8、小于剩余的路由跳跃数。,2.5虚信道和虚网络双环路由,上述每一个单向信道增加一个虚信道的方法叫双环路由形式化地描述双环路由：假定使用n个进程：Pn-1,Pn-2,P1,P0，信道是Ch或Cl：,2.5虚信道和虚网络双环路由算法,2.5虚信道和虚网络双环路由,在上述算法中，当进程发起路由时，如果i des，可以使用高信道或者低信道。如果i des，则只能使用高信道。,2.6 完全自适应和无死锁路由算法,适应性和无死锁是两个互相矛盾的要求。像2 维网格的XY路由和n维立方的e-立方等决定性的无死锁路由虽然简单，但都不是适应性的。一个决定性路由在存在错误组件（如链接或节点）的系统中有可能失效例如，一

9、个XY路由完成了X方向的路由，但在Y方向上由于错误被阻塞，这个信息就不能被继续转发但没有限制的适应性路由可能引发死锁。因此，必须在不引发死锁的前提下增加适应性,2.6 完全自适应和无死锁路由算法,几乎所有的完全适应性路由都可以通过增加一定数量的虚信道（或虚网络）来避免死锁。例如，一个最小化的适应性的n 维立方路由可以通过加入n个虚信道来避免死锁。每一步都使用比前一个具有更高标记的信道。因为需要n步，所以n个虚信道足以避免虚信道之间的循环等待。然而使用虚信道会引入附加的缓冲区等开销。所以，要尽量限制虚信道的数目。,2.6.1 虚信道类,如前所述，通过引入足够多的虚信道，任何路由都可以保证避免死锁

10、。当路由开始时，使用虚信道1，vc1。在第i 步使用虚信道i，vci及相应的链接。如果一个给定网络的最长路径（也叫直径）是Dmax那么就要用Dmax个虚信道；,2.6.1 虚信道类,为了减少虚信道的数量，可将一个网络分成几个节点的子集，每个子集都不会包含相邻的接点。例如，考虑一个形似跳棋盘的2维网格，上面有黑白方格。黑节点属于个子集，白色节点属于另外一个。当一个消息从一个白色节点移动到黑色节点时，就将虚信道的标记加一。如果是从黑色节点向白色节点移动，虚信道标记保持不变。显然，在2维网格中，节点标记的改变次数最多为路由步数的一半。这样虚信道的总数就缩减了一半。,2.6.1 虚信道类,可以将上述思

11、想一般化：将给定网络分成k个子集S1,S2,Sk，每个子集都不包含相邻节点当一个消息从子集Si中的一个节点移动到子集Sj中的一个节点（i j）时，称之为上移动；反之为负移动。发生负移动时，虚信道标记加一假定信道标记从1 开始从而，所需信道的个数就是一个路由路径中负移动的个数。目标就是要选择一个合适的k以及一个划分，使路由过程中的负移动个数最小,2.6.2 逃逸信道等待和非等待信道,使用逃逸信道的路由算法中，虚信道被分为等待信道（又称为逃逸信道）和若一个等待信道处于繁忙状态，而此时一个消息需要通过该信道，则这个消息必须等待，直到该信道可用即一个等待信道能够阻塞消息非等待信道（又称为一般信道）若一

12、个消息碰到一个处于繁忙状态的非等待信道，它不必被阻塞以等待该信道变得可用，可以选择其他信道因此，一个消息会首先考虑通过非等待信道到达目标若所有的非等待信道都繁忙，它就考虑等待信道,2.6.2 逃逸信道混合路由,使用逃逸信道扩展完全适应的概念例如，可以用两个路由进程实现混合路由：路由进程1：完全适应性路由，使用标记为非等待的虚信道；路由进程2：限制性但无死锁路由可能是XY路由或e-立方等决定性路由使用标记为等待的虚信道。,2.6.2 逃逸信道混合路由（contd）,混合路由算法：开始时，使用完全适应路由，直到阻塞为止；然后切换到限制性路由。混合路由是无死锁的由于等待信道是在无死锁路由中定义的，并

13、且消息仅仅等待上述等待信道合理分配等待和非等待信道是关系到混合路由效率的关键问题,2.6.2 逃逸信道混合路由的扩展I,扩展I：当消息发现等待信道被占用时，可以使用非等待信道扩展I增加灵活性的同时也引入了选定的逃逸信道之间新的依赖性。通过使用一个或多个中间的一般信道，一个逃逸信道可能间接地依赖于另一个逃逸信道。因此无回路条件必须包括逃逸信道之间的所有间接依赖。不幸的是，没有循环依赖只是不发生死锁的一个充分条件；也即，对于一个特定的虫孔网络，若使用某一个路由算法，扩展I太弱，不会得到任何结果。扩展信道依赖图中的一个回路可能表示一个死锁状态，也可能不是。,2.6.2 逃逸信道混合路由的扩展I I,

14、Duato通过使用基于消息目标的逃逸路径进一步扩展了上述思想 对于不同的目标，使用不同的逃逸信道。在同样的无回路条件下，可以得到一个无死锁的充分必要条件。然而，在生成扩展信道依赖图的时候，直接依赖、间接依赖、直接交叉依赖（在不同目标的逃逸信道之间）和间接交叉依赖都要被考虑进去。,2.6.2 逃逸信道,上述两个扩展都可用于避免死锁。为了设计一个无死锁的路由函数，首先创建一个名为R1(x,y)的路由子函数，它的功能是将当前和目标节点映射到当前节点的输出信道的子集。R1(x,y)是连通的，无回路的。可以通过增加信道或者将已有信道分割为虚信道将R1(x,y)扩展为R(x,y)，以便增加可选路径的数目，

15、同时又不会在R1(x,y)的扩展信道依赖图中增加回路。这一设计规程又被称为Duato协议。,2.6.2 逃逸信道维度逆转路由,如果不要求最小路由，那么虚信道的数量还可以减少。对于一个k元n维立方（没有环绕连接），有如下的一般非最小无死锁路由：对每个物理信道，有k个虚信道与之对应其中一个用于逃逸信道，以便进行无死锁的按维排序的路由消息可以按照任何方向路由，而不一定是最小路径。每个消息都有一个维度逆转数DR相对应，DR：记录消息从高维度路由到低维度的次数。,2.6.2 逃逸信道维度逆转路由（contd）,一旦一个消息取得一个信道，它就将该信道标记为当前的DR数。为了避免死锁，一个DR数为i的消息不

16、能等待一个DR数为j的信道，这里ij。此时，选用下一层的虚信道。假定每个未被访问的信道的DR标记为0。当虚信道的标记达到k时，就使用决定性的按维度排序的路由。,2.7 几个部分适应和无死锁路由算法,很多路由算法的路由适应性仅对一小部分虚信道有效。这种算法属于部分适应性路由本节讨论三个部分适应性和无死锁路由算法转弯模型平面自适应模型其他部分自适应模型,2.7.1 转弯模型,2维网格的转弯模型提供了一个部分适应性和无死锁的路由。下图显示了2维网格中的抽象回路。,2.7.1转弯模型基本思想,上图显示了XY路由中所允许的四个转弯（实心箭头所指）。只允许先X方向路由后Y方向路由显然，这个条件太严格了，因

17、为可以通过去掉回路中的一个角来打破回路。转弯模型的基本思想通过禁止最小数目的转弯来增加适应性，以避免回路。,X方向,Y方向,2.7.1 转弯模型正向优先协议和负向优先协议,左下图为一个正向优先路由协议。可以有6个转弯从负向到正向的转弯，也即南到东和西到北，被禁止右下图为一个负向优先路由协议。可以有6个转弯从正向到负向的转弯，也即北到东和东到北，被禁止,X方向,Y方向,X负到Y正,Y负到X正,X正到Y负,Y正到X负,正向优先协议,负向优先协议,2.7.1 转弯模型转弯模型的适应性,由于源和目标的位置的不同，转弯模型可能有适应性，也可能没有。下图显示了源s和目标d的两种不同位置。若目标位于源的东北

18、或西南方，那么正向优先路由就是完全适应性的，如图a否则，就是决定性的，如图b,（a）完全适应性路由,（b）确定性路由,东北,东南,OK,Not OK,2.7.1 转弯模型转弯模型的平衡性,某些情况下，上述不平衡的适应可能会导致拥塞或不平衡的工作量。可以使用虚信道将几种不同的协议结合起来。每个协议都是基于转弯模型，但有不同的区域适应性，因而可以得到一种平衡的方法。例如，若允许使用两个虚信道，就可设计两个具有互补适应性的转弯模型。,2.7.2 平面自适应模型,对应于一般的k元n维立方，Chien和Kim提出了一种部分适应性和无死锁的路由。基本思想是：在某一时刻将路由的自由度限制到儿个维度以降低对硬

19、件（虚信道）的要求。例如，若每次只选两个维度，就有A0,A1,An这些平面，其中Ai在维度di和di+1方向扩展。,2.7.2 平面自适应模型举例,下图显示了三个平面的例子：A0（维度为d0和d1），A1（维度为d1和d2），和A2（维度为d2和d3）,平面自适应路由所允许的路径,2.7.2 平面自适应模型举例,对每个Ai，引入三个虚信道，一个沿着第i 维，两个沿着第（i+1）维。设di,j是维度j通过维度i的虚信道。Ai使用三个虚信道：di,2、di+1,0和di+1,1,2.7.2 平面自适应模型,由于每个虚信道都是双向的，可将di,2分成两个单向信道di,2+和di,2-Ai也就被分成两

20、个子网：包含di,2+和di+1,0的正向子网；以及包含di,2-和di+1,1的负向子网本课开始的正负子网可看成是上述正向和负向子网的例子：将X和Y视为di和di+1,正网络,负网络,2.7.2 平面自适应模型,Ai内部的路由可依据源和目标的位置不同而选用正向或负向子网。若目标的标识大于源标识，则选用正向子网；否则，选用负向子网。注意：虚信道di,di,0,di,1中的另外两个也用于平面Ai-1，即相邻平面有一个公共维度。相对于完全适应而言，平面适应方法牺牲了一些路由自由度（适应性），从而大大降低了虚信道的数目。,2.7.3 其他部分自适应模型,Li出了e-立方路由的一个要求稍低的版本。对一

21、个超立方中的任意回路，我们总能找出沿着最低维度的两个链接，比如设该维度为i。其中一个链接是从第i 位为0 的节点到第i 位为1 的节点（负向链接）另一个是从第i 位为1的节点到第i位为0 的节点（负向连接）。为了打破一个回路，只需禁止从较高维度的正向连接向沿着维度i的负向连接转换即可，除非这个转换符合e立方路由。,2.7.3 其他部分自适应模型,如果e立方路由满足维度递增的顺序，一个沿着维度dim(c1)的信道c1到一个沿着维度dim(c2)的信道c2的转换是允许的当且仅当下述条件中的一个为真：dim(c1)dim(c2)，或c2是正向的假定维度是从右向左编号的，即最右边的一位对应于维度1。按

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

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

24、|S1|=2,|S2|=2使用完全适应性路由算法有|S|!=4!=24种路由选择使用扩展转弯模型有|S1|!|S2|!=2!2!4种路由选择,2.7.3 其他部分自适应模型2维网格中基于起源的路由,基于起源的路由是XY路由在2 维网格中的一个扩展一个起源节点o是预先选定的（如图）路由分成两个阶段阶段1：从源s到起源节点o阶段2：从起源节点o到目标节点d,2.7.3 其他部分自适应模型2维网格中基于起源的路由,网络被分成两个子网。IN子网包括所有指向起源节点o的单向信道OUT子网包括所有离开起源节点o的单向信道路由的第一阶段使用IN子网第二阶段使用OUT 子网图中仅显示了IN子网。将图中的每个链

25、接反向可得到OUT子网。,2.7.3 其他部分自适应模型2维网格中基于起源的路由,为了对源s和目标d决定这两个阶段的临界点，建立一个outbox outbox 是一个以起源节点o和目标节点d为对角顶点的矩形。实际上，outbox 是一个包含了所有位于目标节点d和起源节点o之间的最短路径上的节点的子网。确切地说，基于起源的路由将使用IN子网将消息向目标节点d 转发；一旦消息到达outbox 边界，就将切换为OUT 子网。,2.8 容错单播：一般方法,随着分布式系统中处理器数量的增多，处理器失效的可能性也会加大。所以，路由算法应该在处理器失效时仍然有效。但仍要达到一定程度的适应性，同时也要保证无死

26、锁。在通过增加（或删除）节点和/或链接来达到容错方面已经做过许多研究。然而，这需要更改网络拓扑，而这很昂贵、很困难。在这里将重点放在通过使用网络中已有的冗余来达到容错，而不会增加空节点和/或链接。,2.8 容错单播：一般方法,在设计路由算法之前，需要确定下面几点：最短路径或非最短路径。错误类型：链接错误，节点错误，或者链接错误和节点错误都有出错的组件的个数是有限的还是无限的对错误分布的了解：局部、全局和有限的全局冗余或非冗余回退或者前进,2.8 容错单播：一般方法,最短路由路径需要有在出错情况下工作的最优路由。这一要求对于非最短路径路由是可以放松的，因为对后者而言，非最短路径也是可以接受的。链

27、接错误和节点错误是不同的。典型情况是，当一个节点失效时，它周围的链接也被认为失效了。然而，如果一个节点周围的一个或多个链接失效，那么只要这个节点没有被孤立，它就仍然是好的。,2.8 容错单播：一般方法失效组件的数量,失效的组件（节点或链接）的数量在设计容错路由算法时具有重要地位。一般地，设计一个可以经受有限（或恒定）数日的故障的路由算法是相对容易的。,2.8 容错单播：一般方法错误分布信息的了解,对于错误分布的了解决定了路由算法的效率。典型地，基于局部信息的路由不能达到最优，因为它对系统的了解是有限的。如果能够得到全局信息，就有可能达到最优。当然要有一个单独的进程按时收集信息。有限全局信息是介

28、于局部和全局信息之间的一个平衡,2.8 容错单播：一般方法冗余 or 非冗余,可以利用冗余路由来很容易地获得容错路由。如果消息的k 个拷贝通过节点分离路径发往目标，就可以经受至少k-1个错误。但，即使系统中没有错误，通信量也会因此增加k-1倍。非冗余方法仅仅发送消息的一个拷贝，并通过绕过故障而将消息转发到目标。,2.8 容错单播：一般方法回退 or 前进,前进型协议会等待、中止或者选择错误的路径，但是方向始终是向前的，而不会回到上一个节点重新开始。前进式路由在虫孔路由中很重要，因为这种路由不允许回退。有一种叫做流水线电路交换的路由方法扩展了虫孔路由，可以允许回退。回退协议认为与其等待一个可用的

29、路径，不如去找其他路径。18 中针对虫孔网络提出了一个容错路由理论。在这个理论中，Duato 将互连性和无死锁联系起来，分析了虫孔网络的容错性。,2.9 2维网格和圆环中的容错单播,根据路由过程中使用的故障信息，本节考虑如下几种容错路由算法：基于局部信息基于有限全局信息基于其他故障模型,2.9.1 基于局部信息的路由,许多适应性路由算法，例如转弯模型，可以经受一个有限数量的故障（如k 元n 维立方中为n一1 个故障）。2 维网格中，若源和目标都有四个邻居，那么2 维网格的冗余路由可以至少经受三个错误（链接和/或节点）。为了能够承受更多的错误，通常使用错误区域的概念。若错误区域是一个凸形，就有可

30、能设计一个简单的容错和无死锁路由对于凹形，可以在区域中加入一些非错误节点，从而将其转变为凸形,2.9.1 基于局部信息的路由基本安全/非安全定义,安全/非安全节点的定义：所有错误节点都是不安全的。所有非错误节点开始时都是安全的。如果一个非错误节点有两个或两个以上的非安全邻居，那么它的状态就变为非安全的。,2.9.1 基于局部信息的路由基于基本安全/非安全定义的出错块,下图显示了一个出错块的例子红色节点是错误节点黑色节点代表非错误但不安全的节点。易证，错块是分离的且它们的距离最少是3,2.9.1 基于局部信息的路由扩展安全/非安全定义,为减少出错块中非出错节点的数目，对上述安全/非安全定义进行如

31、下扩展：所有错误节点都是不安全的。所有非错误节点开始时都是安全的。若一个非出错节点在两个维度上都有错误的或不安全的邻居，它的状态就变为非安全的,2.9.1 基于局部信息的路由基于扩展安全/非安全定义的出错块,下图为对上述同一个例子使用扩展安全节点概念的结果图中有两个分离的出错块。可以证明两个出错块之间的距离最少为2。然而，出错块中所包含的非错误节点的总数比基于基本的安全非安全定义的出错块要少。,2.9.1 基于局部信息的路由基于出错块的路由,对2 维网格或圆环的路由可进行如下扩展：若没有因错误阻塞，就按无错的情况路由。若在X维（或Y维）阻塞，就在Y维（或X维）路由若因错误在X维受到阻塞，而Y维

32、度的距离已接近零，就有必要进行曲折路由。随便选择一个Y方向，开始曲折路由。首先试着从X维度到达目标。继续沿着X方向，直到Y方向正确为止。即沿着出错块的边缘路由。Y 维度的出错块可用类似的方法处理。,2.9.1 基于局部信息的路由基于出错块的路由举例,下图是一个沿着凸形错误区域路由的例子。注意：消息可能会在凹形出错区域受到限制。,2.9.1 基于局部信息的路由基于出错块的路由举例,当消息沿着凸起的出错块移动时，一个维度（X或Y）总是单调增加或减少。注意凹陷的出错块没有这个特性。所以每个路由都可呆在正向子网或负向子网，正如平面适应路由中那样。因此无需引入更多的虚信道，可以在这里使用与平面适应路由同

33、样的算法。即，在n维(n0)网中，使用三个虚信道来避免死锁。对n维圆环，每个环绕信道需要两个虚信道来打破同一个维度中的回路。总之，对n(n0)维圆环需要6 个虚信道。2 维网格中，使用两个虚信道，网络被分成正/负向两个子网。类似地，在2 维圆环中，使用4个虚信道。,2.9.2 基于有限全局信息的路由Wu的最优容错路由算法,Wu提出了一个有出错块的2维网格的最优容错路由算法。首先，他证明：设节点(0,0)是源节点，节点(i,j)是目标节点。若没有出错块通过X和Y轴，那至少存在一个始于(0,0)的最优路径，长度为|i|+|j|。在一给定的2维网格中，上述结果对任意位置的目标节点和任何数目和分布的出

34、错块都成立，相应的源叫做安全的。上述结果可以进一步扩展：允许X和Y轴有出错块，只要它们到源的距离分别大于|i|和|j|。这样的源节点叫做扩展安全的。,2.9.2 基于有限全局信息的路由Wu的最优容错路由算法,有两个最优和适应性容错的路由算法：面向目标路由，和面向源路由。为简单起见，假定源节点是(0,0)，目标节点是(i,j)，且i,j=0，即路由永远是向东北方向的。,2.9.2 基于有限全局信息的路由面向目标的路由,面向目标的路由使用最短路径区域RMP的概念：对给定的源和目标对，RMP包含最短路径的所有中间节点为建立RMP做一条从目标节点(i,j)开始到Y轴结束的线。遇到出错块时，先向南绕过出

35、错块，然后继续向西类似地，建立一个从(i,j)开始向南到X轴截止的线。遇到出错块时，先向西绕过出错块，然后继续向南。已经证明由向西和向南的线以及X轴和Y轴围起来的区域是RMP。,2.9.2 基于有限全局信息的路由面向目标的路由举例,下图显示了一个RMP的例子，这里向西的线标记为路径A，向南的线标记为路径B。,2.9.2 基于有限全局信息的路由面向目标的路由,仅当源是扩展安全的，才使用面向目标路由源通过一个最优或不是最优的路径向目标发一个信号接到信号后目标发两个信号，一个向西一个向南向西的信号建立RMP的路径A，向南的信号建立RMP的路径B。一旦源收到来自目标的两个信号，就意味着RMP已建立起来

36、。源就用任何一种适应性最小路由发送路由消息。遇到路径A（或路径B）的边界时，剩下的路由就要沿着路径A（路径B）发往目标。,2.9.2 基于有限全局信息的路由面向源的最优路由,为支持面向源的最优路由，必须把出错块的信息分布到系统中的特定节点上。举例说明：下图显示了一个出错块L1,L2,L3,L4与出错块的四条线平行x=0和y=0的区域被分成8 个子区域：R1R8L14上的点可划归任一相邻区域。,2.9.2 基于有限全局信息的路由面向源的最优路由（contd）,显然，可用任一最小路由算法到达R1,R2,R3,R7,R8中的点可用XY路由（先X后Y）到达R6中的任何点。可用YX路由（先Y后X）到达R

37、4中的任何点。用XY路由和YX路由都可到达R5 中的点。,2.9.2 基于有限全局信息的路由面向源的最优路由（contd）,当目标节点位于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,-),2.9.2 基于有限全局信息的路由面向源的最优路由（contd）,显然，目标位于路径1的南侧或东侧的路由消息不能

38、通过路径1。目标位于路径2的北侧或西侧的路由消息不能通过路径2。路径1的路径信息存储在(-,y)到(x,y)间的每个节点上路径2的路径信息存储在点(x,-)到(x,y)间的每个节上为最小化路径信息，只有每个转弯（出错块的角落）的位置是必要的。所以(x,y)和(x,y)对路径1是必要的，而(x,y)和(x,y)对路径2是必要的。,2.9.2 基于有限全局信息的路由面向源路由的步骤,面向源路由的步骤：首先使用任何一个适应性最小路由，直到遇到出错块的一个（路径1或路径2）为止。（遇到路径1的L1）若目标节点在路径1的南/东侧，那消息将一直留在L1直到到达出错块的L1和L4的边界为止；否则将穿过L1。

39、（遇到路径2的L2）若目标节点在路径2的北/西侧，那消息将一直留在L2直到到达出错块的L2和L4的边界为止；否则将穿过L2。,2.9.2 基于有限全局信息的路由面向源路由的步骤（contd）,上述方法中，两个虚信道足以避免死锁。一个简单的方法是为东北和东南方向的路由使用正向子网，对西北和西南方向的路由使用负向子网。,2.9.3 基于其他故障模型的路由Wu的直角凸多边形模型,虽然矩形出错块很简单，但它引入了很多被禁止的非出错节点，即它们将不会在路由过程中起作用。但矩形为凸形的特性使得可以用最少的虚信道把路由信息绕过出错区域。另外一些非矩形的凸形出错块也被引入了。Wu将出错块模型扩展为直角凸多边形

40、模型。一个凸多边形的定义是：多边形P，P中的任意两点之间的线段都在P内部。在直角凸多边形中，线段被限制为只能是水平或垂直的。,2.9.3 基于其他故障模型的路由直角凸多边形,可以将给定的矩形出错块转换为一系列分离的直角凸多边形这一思想根源于这样一个事实：可以通过将出错块中的一些非出错节点移出去，从而将它们激活，同时又保持这个区域的凸性。,2.9.3 基于其他故障模型的路由活跃/不活跃节点,与标准出错块中的安全/非安全定义不同，Wu给出了活跃/不活跃节点的概念：所有出错节点都是非活跃的，所有安全节点都是活跃的。一个非安全节点开始的时候是非活跃的但如果它有两个或两个以上的活跃邻居，那么它就可以称为

41、活跃的。因此，对于一个非出错节点，有三种可能情况：安全且活跃。非安全但活跃。非安全且不活跃。,2.9.3 基于其他故障模型的路由活跃/不活跃节点举例,下图是将wu的活跃/不活跃规则用于图7-7的出错块的结果。显然，结果是一个直角凸多边形。,2.10 超立方中的容错单播,按照使用的错误信息类型对超立方中的容错单播路由进行分类：基于局部信息的基于有限全局信息的基于扩展安全等级模型的,2.10.1 基于局部信息的模型,已经证明，对n维立方中的任何两点u和w，如果H(u,w)=k，那么从u到w恰好有n条点分离路径。其中，有k条长度为k的路径和(n-k)条长度为k+2的路径若出错组件的数目L小于n，那么

42、用多条路径进行路由的方法是很直接的。消息沿着n条点分离路径进行传送，并且其中至少有一条是好的。这样，就可通过那条路径到达目标，路径最大长度是k+2,2.10.1 基于局部信息的模型,chen和shin给出了下面四种容错路由算法:出错组件小于n-1，不确保有最优路径。出错组件小于n-1，确保有最优路径。出错组件无限制，不确保有最优路径。出错组件无限制，确保有最优路径。第2和第4种情况是所希望的，但相应的算法会引入特别的开销。,2.10.1 基于局部信息的模型第1种情况等位序列定义,考虑一个第1种情况的算法。为了容错，一些访问过的节点也保存在消息中。定义：等位序列d1,d2,dk为当前节点与目标节

43、点不同的所有维度（也叫首选维度，preferred dimension）例如，假设0010和0111是当前节点和目标节点，那相应的等位序列就是1,3为表示一个消息的目标，等位序列要和消息一起传送因当前节点会随着消息的传递而变化，故等位序列也随着变化,2.10.1 基于局部信息的模型第1种情况消息的表示,每个消息都有一个n位向量标志，用以保存“空余维度(Pare dimensions)”。可以用这些维度来绕过出错组件。注意空余维度就是那些没有在最初的等位序列中出现的维度源节点发起路由时，标志中的所有位都将清零。消息的表示：(k,d1,d2,dk,消息,标记)。k为剩余路径长度，k会在消息的发往过

44、程中不断更新当k变为0时，消息就到达目标了。,2.10.1 基于局部信息的模型算法的描述,当节点收到一个消息时，检查k的值以判断自身是否为消息的目标若不是，节点将尝试按照剩下的等位序列中指定的维度发送消息每个节点都将努力沿着最短路径发送消息。然而，若通往最短路径的维度的那些连接出错，这个节点将使用空余维度通过另外的路径发送消息。开始时，等位序列为由源和目标地址异或得到的所有首选维度空余维度的所有位清零。,2.10.1 基于局部信息的模型算法的描述,更正式地，这个路由算法可以描述如下。,注意：u(i)表示沿着维度i的u的邻居。,2.10.1 基于局部信息的模型算法举例,考虑下图中的出错超立方。假

45、设消息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。,2.10.1 基于局部信息的模型算法举例（contd）,由于0101的第3维链接出现错误，节点0101将发送(1,3,m,0000)到01014=1101。然而，由于1101的第3维的链接出现错误，节点1101将使用第1维（标记=0100，标记记下了要绕道时的首选维度），并发送消息(2,3,1,m,0101)到1100。,2.10.

46、1 基于局部信息的模型算法举例（contd）,1100依次将发送(1,1,m,0101)到1000。随后，节点1000的第一个链接又出现错误。这时将使用第2维（此时标记=0101）,(2,1,2,m,0111)被路由到1010。之后，消息将经过1011到达目标1001。结果路径的长度是8。,2.10.2 基于有限全局信息的模型：安全等级（定义）,下面讨论具有节点故障的超立方中的有效路由这种模式基于每个节点的有限全局信息这种信息被标记为安全等级。从根本上说，安全等级就是每个节点周围邻居中失效节点的大致数目。定义：设s(a)=k是节点a的安全等级，称a是k-安全的；一个失效节点是0-安全的，即最低

47、的安全等级，一个n-安全的节点（也叫安全节点）安全级别最高若kn，那么一个k-安全的节点就是不安全的,安全等级的定义及计算,n维立方中，令节点a的所有邻居节点的安全等级的非递减安全状态序列为：(S0,S1,S2,Sn-1)，0=(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次重复达到稳定状态。,安全等级举例,例如，下图的出错超立方中，出错

48、节点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,安全等级的性质和基于安全等级的路由,安全等级有以下性质：如果一个节点的安全等级是k(0k=n)，那么在k海明距离内，至少存在一个从该节点到任意节点的海明距离路径。确

49、切地说，节点的安全等级不仅提供了它的路由能力，也提供了路由信息。当源的安全等级大于源和目标之间的距离的时候，就可以保证最优路由。实际上，可以在每一步通过选择具有最高安全等级的邻居来产生最优路径。一个引导向量（定义为当前节点和目标节点的按位异或）被附加在路由消息上。,基于安全等级的路由举例,在此考虑图7-13 的例子每个圆圈（节点）中的数字表明了该节点的安全等级。考虑以s1=1110和d1=0001为源和目标的单播路由引导向量是N1=s1d1=1111，从而H(s1,d1)=4。由于源节点s1的安全等级是4，从而可以使用最优算法（如下页）。,基于安全等级的路由举例,在源节点的首选节点中，节点10

50、10,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，并更新