高级操作系统3ppt课件

《高级操作系统3ppt课件》由会员分享，可在线阅读，更多相关《高级操作系统3ppt课件（140页珍藏版）》请在金锄头文库上搜索。

1、高级操作系统高级操作系统Advanced Operating System熊焰yxiongustc.edu0551_3600689中国科学技术大学计算机系第二章第二章 分布式路由算法分布式路由算法l分布式路由算法导论l普通类型网络的最短途径路由算法 l特殊类型网络的单播算法l特殊类型网络中的多播算法l虚信道和虚网络 l完全自顺应和无死锁路由算法l几个自顺应和无死锁路由算法 l容错单播的普通方法 l网格和圆环中的容错单播算法l超立方中的容错单播算法l容错组播算法2.5 虚信道和虚网络虚信道和虚网络l网络资源l在存储转发交换中，资源是缓冲区；l在虫孔路由中，资源是信道。l网络通讯中，假设音讯在占有

2、资源的前提下可以恳求资源，就有能够发生死锁l经过控制路由的自顺应性可以预防和防止死锁，同时也保证一定的容错性。 l虚信道和虚网络经常用于实现无死锁、自顺应和或容错的路由。2.5 虚信道和虚网络虚信道和虚网络经过网络分区防止死锁经过网络分区防止死锁l经过网络分区可以防止死锁l给定的网络可以分成几个子网。l根据源和目的的位置，音讯被路由到不同的子网l举例阐明：l3X3网格的顺应性双Y信道路由l如图：l在Y方向有两个物理信道双向a一个3X3网格的 双Y信道网2.5 虚信道和虚网络虚信道和虚网络经过网络分区防止死锁经过网络分区防止死锁contdl上述网格被分成正、负两个子网如以以下图l假设目的位于源的

3、右侧，那么运用正网；l否那么将运用负网。l当源和目的同列时，两个子网都不用。l由于两个子网中都没有回路，所以可防止死锁。 b正网络c负网络2.5虚信道和虚网络虚信道和虚网络虚信道虚信道l假设网络没有双Y信道，那么可用几个虚信道复用一个物理信道l每个虚信道都有本人的缓冲区。l当物理信道被其它虚信道运用时，就用这个缓冲区保管音讯l假设虚信道间没有循环等待，就可防止死锁。l假设上例改为单Y信道网，那么原来的正、负子网中一切的Y信道都是虚信道。2.5虚信道和虚网络虚信道和虚网络虚信道虚信道contdl当两个虚信道共享一个物理信道时，信道利用率大幅提高。l虽然虚信道提供了一个具有多重信道的网络，但仍需仔

4、细设计路由算法。例如，l可以按照信道标志的升序运用虚信道，以便防止虚信道间循环依赖。2.5虚信道和虚网络虚信道和虚网络虚网络虚网络l比虚信道更高一级的虚拟化是虚网络l一个给定的物理网络被分成几个虚网络，每个虚网络包括一系列的虚信道。l虚网络中相邻的节点被映射到物理网络中时也要相邻l普通地，一个虚网络中的虚信道设置应防止信道间的回路。虽然仍有能够存在相互交叉的虚网络回路，但可以经过使虚网络遵照全序或偏序来避回路l前面那个例子中，假设运用单Y信道，那么前面的正、负子网可以为是两个虚网络。l显然每个网络中都没有回路。因每个路由过程最多只运用一个虚网络，所以不会产生相互交叉的虚网络回路。 2.5虚信道

5、和虚网络虚信道和虚网络l虽然虚网络包含虚信道，二者是完全不同的概念。l普通地，虚信道的运用是与路由过程严密相连的，包括源和目的的位置。必需合理布置虚信道，以防止死锁。l虚网络通常设计为没有回路，因此路由算法可以不用思索死锁，除非存在交叉虚网络的依赖性2.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例l思索一个有四个节点的单向环。假好似时有几个路由进程启动，就会发生死锁。2.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例contdl经过给每个链接添加两个虚信道可以防止死锁l如图，信道被分为l高虚信道，和Ch0, Ch1, Ch2, Ch3l低虚信道Cl0, Cl1, Cl2, Cl32.

6、5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例contdl假设源地址大于目的地址，l可从任何一个信道开场；l但一旦运用一个高低信道，那以后也要运用同一信道l假设源地址小于目的地址，l首先运用高信道，经过节点P3后，高虚信道切换为低虚信道l图示为相应的信道依赖图l以信道为节点l边为信道之间的切换关系P32.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例l在上述虚信道方法中，给定的环被分成两个虚环：Vr1和Vr2l每个环中都有一个回路。两个虚环：Vr1：高信道构成的虚环Vr0：低信道构成的虚环虚环构成的回路。图中，节点内的边表示回路中信道的切换关系2.5虚信道和虚网络虚信道和虚网络虚网络举

7、例虚网络举例contdl要防止虚网络内部的回路，可以l在vr1中制止从Ch0切换到Ch3，和l在vr0中制止从Cl0切换到C13。P3中，Ch0到Ch3的切换被制止；Cl0到Cl3的切换也被制止2.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例contdl可在任一步进展从vr1到vr0 的虚网络切换如图l例如l假设源地址大于目的地址，如l从P2到P0的路由可以从Ch2开场，并在P1切换至Cl1l从P3到P0的路由中，可在P2或P1进展切换l也可以不切换l但假设目的地址大于源地址，那么必需在节点P3切换，由于l在单向环中，假设目的地址大于源地址，那么必然要经过P3路由l两个虚环都不允许在P3

8、进展从Ch0到Ch3 和Cl0到Cl3 的切换。l所以在P3只能进展Ch0到Cl3的切换图中，每个节点都可以进展vr1到vr0的虚网络切换2.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例contdl基于虚网络的路由过程比基于虚信道的路由有更强的顺应才干。在上例中，l虚信道路由仅在P3进展高虚信道到低虚信道的切换l虚网络路由允许在任一点进展虚网络切换l为了保证从vr1到vr0的切换生成一个合法的路由途径，l假设Cli是vr0中的切换信道，那么i必需不能小于剩余的路由腾跃数。2.5虚信道和虚网络虚信道和虚网络双环路由双环路由l上述每一个单向信道添加一个虚信道的方法叫双环路由l方式化地描画双环

9、路由：l假定运用n个进程：Pn-1,Pn-2,P1, P0，信道是Ch或Cl：2.5虚信道和虚网络虚信道和虚网络双环路由算法双环路由算法2.5虚信道和虚网络虚信道和虚网络双环路由双环路由l在上述算法中，当进程发起路由时，l假设i des ，可以运用高信道或者低信道。l假设i des ，那么只能运用高信道。2.6 完全自顺应和无死锁路由算法完全自顺应和无死锁路由算法 l顺应性和无死锁是两个相互矛盾的要求。l像2 维网格的XY路由和n维立方的e-立方等决议性的无死锁路由虽然简单，但都不是顺应性的。l一个决议性路由在存在错误组件如链接或节点的系统中有能够失效l例如，一个XY路由完成了X方向的路由，但

10、在Y方向上由于错误被阻塞，这个信息就不能被继续转发l但没有限制的顺应性路由能够引发死锁。l因此，必需在不引发死锁的前提下添加顺应性2.6 完全自顺应和无死锁路由算法完全自顺应和无死锁路由算法l几乎一切的完全顺应性路由都可以经过添加一定数量的虚信道或虚网络来防止死锁。l例如，l一个最小化的顺应性的n 维立方路由可以经过参与n个虚信道来防止死锁。l每一步都运用比前一个具有更高标志的信道。l由于需求n步，所以n个虚信道足以防止虚信道之间的循环等待。l然而运用虚信道会引入附加的缓冲区等开销。所以，要尽量限制虚信道的数目。2.6.1 虚信道类虚信道类 l如前所述，经过引入足够多的虚信道，任何路由都可以保

11、证防止死锁。l当路由开场时，运用虚信道1，vc1。l在第i 步运用虚信道i，vci及相应的链接。l假设一个给定网络的最长途径也叫直径是Dmax那么就要用Dmax个虚信道；2.6.1 虚信道类虚信道类l为了减少虚信道的数量，可将一个网络分成几个节点的子集，每个子集都不会包含相邻的接点。l例如，l思索一个形似跳棋盘的2维网格，上面有黑白方格。l黑节点属于个子集，白色节点属于另外一个。l当一个音讯从一个白色节点挪动到黑色节点时，就将虚信道的标志加一。l假设是从黑色节点向白色节点挪动，虚信道标志坚持不变。l显然，在2维网格中，节点标志的改动次数最多为路由步数的一半。这样虚信道的总数就缩减了一半。2.6

12、.1 虚信道类虚信道类l可以将上述思想普通化：l将给定网络分成k个子集S1, S2, Sk ，每个子集都不包含相邻节点l当一个音讯从子集Si中的一个节点挪动到子集Sj中的一个节点i j 时，称之为上挪动；反之为负挪动。l发生负挪动时，虚信道标志加一l假定信道标志从1 开场l从而，所需信道的个数就是一个路由途径中负挪动的个数。l目的就是要选择一个适宜的k以及一个划分，使路由过程中的负挪动个数最小2.6.2 逃逸信道逃逸信道等待和非等待信道等待和非等待信道l运用逃逸信道的路由算法中，虚信道被分为l等待信道又称为逃逸信道和l假设一个等待信道处于忙碌形状，而此时一个音讯需求经过该信道，那么这个音讯必需

13、等待，直到该信道可用l即一个等待信道可以阻塞音讯l非等待信道又称为普通讯道l假设一个音讯碰到一个处于忙碌形状的非等待信道，它不用被阻塞以等待该信道变得可用，可以选择其他信道l因此，一个音讯会首先思索经过非等待信道到达目的l假设一切的非等待信道都忙碌，它就思索等待信道2.6.2 逃逸信道逃逸信道混合路由混合路由 l运用逃逸信道扩展完全顺应的概念l例如，可以用两个路由进程实现混合路由：l路由进程1：完全顺应性路由，运用标志为非等待的虚信道；l路由进程2：限制性但无死锁路由能够是XY路由或e-立方等决议性路由运用标志为等待的虚信道。2.6.2 逃逸信道逃逸信道混合路由混合路由contdl混合路由算法

14、：l开场时，运用完全顺应路由，直到阻塞为止；l然后切换到限制性路由。l混合路由是无死锁的l由于等待信道是在无死锁路由中定义的，并且l音讯仅仅等待上述等待信道l合理分配等待和非等待信道是关系到混合路由效率的关键问题2.6.2 逃逸信道逃逸信道混合路由的扩展混合路由的扩展Il扩展I：当音讯发现等待信道被占用时，可以运用非等待信道l扩展I添加灵敏性的同时也引入了选定的逃逸信道之间新的依赖性。l经过运用一个或多个中间的普通讯道，一个逃逸信道能够间接地依赖于另一个逃逸信道。l因此无回路条件必需包括逃逸信道之间的一切间接依赖。l不幸的是，没有循环依赖只是不发生死锁的一个充沛条件；也即，对于一个特定的虫孔网

15、络，假设运用某一个路由算法，扩展I太弱，不会得到任何结果。扩展信道依赖图中的一个回路能够表示一个死锁形状，也能够不是。2.6.2 逃逸信道逃逸信道混合路由的扩展混合路由的扩展I IlDuato经过运用基于音讯目的的逃逸途径进一步扩展了上述思想 l对于不同的目的，运用不同的逃逸信道。l在同样的无回路条件下，可以得到一个无死锁的充沛必要条件。l然而，在生成扩展信道依赖图的时候，直接依赖、间接依赖、直接交叉依赖在不同目的的逃逸信道之间和间接交叉依赖都要被思索进去。2.6.2 逃逸信道逃逸信道l上述两个扩展都可用于防止死锁。l为了设计一个无死锁的路由函数，首先创建一个名为R1x,y的路由子函数，它的功

16、能是将当前和目的节点映射到当前节点的输出信道的子集。R1x,y是连通的，无回路的。可以经过添加信道或者将已有信道分割为虚信道将R1x,y扩展为Rx,y，以便添加可选途径的数目，同时又不会在R1x,y的扩展信道依赖图中添加回路。l这一设计规程又被称为Duato协议。2.6.2 逃逸信道逃逸信道维度逆转路由维度逆转路由 l假设不要求最小路由，那么虚信道的数量还可以减少。l对于一个k元n维立方没有环绕衔接，有如下的普通非最小无死锁路由：l对每个物理信道，有k个虚信道与之对应l其中一个用于逃逸信道，以便进展无死锁的按维排序的路由l音讯可以按照任何方向路由，而不一定是最小途径。l每个音讯都有一个维度逆转

17、数DR相对应，lDR：记录音讯从高维度路由到低维度的次数。2.6.2 逃逸信道逃逸信道维度逆转路由维度逆转路由contdl一旦一个音讯获得一个信道，它就将该信道标志为当前的DR数。l为了防止死锁，一个DR数为i的音讯不能等待一个DR数为j的信道，这里ij。l此时，选用下一层的虚信道。l假定每个未被访问的信道的DR标志为0。l当虚信道的标志到达k时，就运用决议性的按维度排序的路由。2.7 几个部分顺应和无死锁路由算几个部分顺应和无死锁路由算法法l很多路由算法的路由顺应性仅对一小部分虚信道有效。这种算法属于部分顺应性路由l本节讨论三个部分顺应性和无死锁路由算法l转弯模型l平面自顺应模型l其他部分自

18、顺应模型2.7.1 转弯模型转弯模型 l2维网格的转弯模型提供了一个部分顺应性和无死锁的路由。l以以下图显示了2维网格中的笼统回路。2.7.1转弯模型转弯模型根本思想根本思想l上图显示了XY路由中所允许的四个转弯实心箭头所指。l只允许先X方向路由后Y方向路由l显然，这个条件太严厉了，由于可以经过去掉回路中的一个角来突破回路。l转弯模型的根本思想l经过制止最小数目的转弯来添加顺应性，以防止回路。X方向Y方向2.7.1 转弯模型转弯模型正向优先协议和负向优先协议正向优先协议和负向优先协议l左以以下图为一个正向优先路由协议。l可以有6个转弯l从负向到正向的转弯，也即南到东和西到北，被制止l右以以下图

19、为一个负向优先路由协议。l可以有6个转弯l从正向到负向的转弯，也即北到东和东到北，被制止X方向Y方向X负到Y正Y负到X正X正到Y负Y正到X负正向优先协议负向优先协议2.7.1 转弯模型转弯模型转弯模型的顺应性转弯模型的顺应性l由于源和目的的位置的不同，转弯模型能够有顺应性，也能够没有。l以以下图显示了源s和目的d的两种不同位置。l假设目的位于源的东北或西南方，那么正向优先路由就是完全顺应性的，如图al否那么，就是决议性的，如图ba完全顺应性路由b确定性路由东北东南OKNot OK2.7.1 转弯模型转弯模型转弯模型的平衡性转弯模型的平衡性l某些情况下，上述不平衡的顺应能够会导致拥塞或不平衡的任

20、务量。l可以运用虚信道将几种不同的协议结合起来。每个协议都是基于转弯模型，但有不同的区域顺应性，因此可以得到一种平衡的方法。l例如，假设允许运用两个虚信道，就可设计两个具有互补顺应性的转弯模型。2.7.2 平面自顺应模型平面自顺应模型 l对应于普通的k元n维立方，Chien和Kim提出了一种部分顺应性和无死锁的路由。l根本思想是：l在某一时辰将路由的自在度限制到儿个维度以降低对硬件虚信道的要求。l例如，假设每次只选两个维度，就有A0, A1, An这些平面，其中Ai在维度di和di+1方向扩展。2.7.2 平面自顺应模型平面自顺应模型举例举例l以以下图显示了三个平面的例子：A0维度为d0和d1

21、，A1维度为d1和d2，和A2维度为d2和d3平面自顺应路由所允许的途径2.7.2 平面自顺应模型平面自顺应模型举例举例l对每个Ai，引入三个虚信道，l一个沿着第i 维，l两个沿着第i+1维。l设di,j是维度j经过维度i的虚信道。lAi运用三个虚信道：di,2 、di+1,0和di+1,12.7.2 平面自顺应模型平面自顺应模型l由于每个虚信道都是双向的，可将di,2分成两个单向信道di,2+和di,2-lAi也就被分成两个子网：包含di,2+和di+1,0的正向子网；以及包含di,2-和di+1,1的负向子网l本课开场的正负子网可看成是上述正向和负向子网的例子：l将X和Y视为di和di+1

22、正网络负网络2.7.2 平面自顺应模型平面自顺应模型lAi内部的路由可根据源和目的的位置不同而选用正向或负向子网。l假设目的的标识大于源标识，那么选用正向子网；l否那么，选用负向子网。l留意：l虚信道di, di,0, di,1中的另外两个也用于平面Ai-1，即相邻平面有一个公共维度。l相对于完全顺应而言，平面顺应方法牺牲了一些路由自在度顺应性，从而大大降低了虚信道的数目。2.7.3 其他部分自顺应模型其他部分自顺应模型lLi出了e-立方路由的一个要求稍低的版本。l对一个超立方中的恣意回路，我们总能找出沿着最低维度的两个链接，比如设该维度为i 。l其中一个链接是从第i 位为0 的节点到第i 位

23、为1 的节点负向链接l另一个是从第i 位为1的节点到第i位为0 的节点负向衔接。l为了突破一个回路，只需制止从较高维度的正向衔接向沿着维度i的负向衔接转换即可，除非这个转换符合e立方路由。2.7.3 其他部分自顺应模型其他部分自顺应模型l假设e立方路由满足维度递增的顺序，一个沿着维度dimc1的信道c1到一个沿着维度dimc2的信道c2的转换是允许的当且仅当下述条件中的一个为真：ldimc10网中，运用三个虚信道来防止死锁。l对n维圆环，每个环绕信道需求两个虚信道来突破同一个维度中的回路。总之，对nn0维圆环需求6 个虚信道。l2 维网格中，运用两个虚信道，网络被分成正/负向两个子网。l类似地

24、，在2 维圆环中，运用4个虚信道。2.9.2 基于有限全局信息的路由基于有限全局信息的路由Wu的最优容错路由算法的最优容错路由算法lWu提出了一个有出错块的2维网格的最优容错路由算法。l首先，他证明：设节点0, 0是源节点，节点i, j是目的节点。假设没有出错块经过X和Y轴，那至少存在一个始于0, 0的最优途径，长度为|i|+|j| 。l在一给定的2维网格中，上述结果对恣意位置的目的节点和任何数目和分布的出错块都成立，相应的源叫做平安的。l上述结果可以进一步扩展：允许X和Y轴有出错块，只需它们到源的间隔 分别大于|i|和|j|。这样的源节点叫做扩展平安的。2.9.2 基于有限全局信息的路由基于

25、有限全局信息的路由Wu的最优容错路由算法的最优容错路由算法l有两个最优和顺应性容错的路由算法：l面向目的路由，和l面向源路由。l为简单起见，假定l源节点是0, 0，l目的节点是i, j，且i, j =0，l即路由永远是向东北方向的。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目的的路由面向目的的路由l面向目的的路由运用最短途径区域RMP的概念：l对给定的源和目的对，RMP包含最短途径的一切中间节点l为建立RMPl做一条从目的节点i, j开场到Y轴终了的线。l遇到出错块时，先向南绕过出错块，然后继续向西l类似地，建立一个从i, j开场向南到X轴截止的线。l遇到出错块时，先向西绕过

26、出错块，然后继续向南。l曾经证明由向西和向南的线以及X轴和Y轴围起来的区域是RMP。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目的的路由面向目的的路由举例例l以以下图显示了一个RMP的例子，这里向西的线标志为途径A，向南的线标志为途径B。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目的的路由面向目的的路由l仅当源是扩展平安的，才运用面向目的路由l源经过一个最优或不是最优的途径向目的发一个信号l接到信号后目的发两个信号，一个向西一个向南向西的信号建立RMP的途径A，向南的信号建立RMP的途径B 。l一旦源收到来自目的的两个信号，就意味着RMP已建立起来。源就用任

27、何一种顺应性最小路由发送路由音讯。l遇到途径A或途径B的边境时，剩下的路由就要沿着途径A 途径B 发往目的。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由l为支持面向源的最优路由，必需把出错块的信息分布到系统中的特定节点上。l举例阐明：以以下图显示了一个出错块lL1, L2, L3, L4与出错块的四条线平行lx=0和y=0的区域被分成8 个子区域：R1R8lL14上的点可划归任一相邻区域。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由contdl显然，l可用任一最小路由算法到达R1, R2, R3 , R7,

28、 R8中的点l可用XY路由先X后Y到达R6中的任何点。l可用YX路由先Y后X到达R4中的任何点。l用XY路由和YX路由都可到达R5 中的点。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由contdl当目的节点位于R4或R6时，为到达最优路由，位于L1位于x,y西侧的节点和L2位于x,y南侧的节点上的特定节点必需具有这个出错块的信息。这些信息可以用出错块的相应角的位置来编码。l特别地，为每个出错块建立两个概念上的途径l途径1虚线：l,yx,yx,yx,y- ,yl途径2实线：lx, x,yx,yx,yx,- 2.9.2 基于有限全局信息的路由基于有限全局

29、信息的路由面向源的最优路由面向源的最优路由contdl显然，l目的位于途径1的南侧或东侧的路由音讯不能经过途径1。l目的位于途径2的北侧或西侧的路由音讯不能经过途径2。l途径1的途径信息存储在-,y到x,y间的每个节点上l途径2的途径信息存储在点x,-到x,y间的每个节上l为最小化途径信息，只需每个转弯出错块的角落的位置是必要的。l所以x,y和x,y对途径1是必要的，而x, y和x, y对途径2是必要的。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源路由的步骤面向源路由的步骤l面向源路由的步骤：l首先运用任何一个顺应性最小路由，直到遇到出错块的一个途径1或途径2为止。l遇到途径

30、1的L1l假设目的节点在途径1的南/东侧，那音讯将不时留在L1直到到达出错块的L1和L4的边境为止；l否那么将穿过L1。l遇到途径2的L2l假设目的节点在途径2的北/西侧，那音讯将不时留在L2直到到达出错块的L2和L4的边境为止；l否那么将穿过L2。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源路由的步骤面向源路由的步骤contdl上述方法中，两个虚信道足以防止死锁。l一个简单的方法是为东北和东南方向的路由运用正向子网，对西北和西南方向的路由运用负向子网。2.9.3 基于其他缺点模型的路由基于其他缺点模型的路由Wu的直角凸多边形模型的直角凸多边形模型l虽然矩形出错块很简单，但它

31、引入了很多被制止的非出错节点，即它们将不会在路由过程中起作用。l但矩形为凸形的特性使得可以用最少的虚信道把路由信息绕过出错区域。l另外一些非矩形的凸形出错块也被引入了。lWu将出错块模型扩展为直角凸多边形模型。l一个凸多边形的定义是：多边形P，P中的恣意两点之间的线段都在P内部。l在直角凸多边形中，线段被限制为只能是程度或垂直的。2.9.3 基于其他缺点模型的路由基于其他缺点模型的路由直角凸多边形直角凸多边形l可以将给定的矩形出错块转换为一系列分别的直角凸多边形l这一思想根源于这样一个现实：l可以经过将出错块中的一些非出错节点移进来，从而将它们激活，同时又坚持这个区域的凸性。2.9.3 基于其

32、他缺点模型的路由基于其他缺点模型的路由活泼活泼/不活泼节点不活泼节点l与规范出错块中的平安/非平安定义不同，Wu给出了活泼/不活泼节点的概念：l一切出错节点都是非活泼的，一切平安节点都是活泼的。l一个非平安节点开场的时候是非活泼的但假设它有两个或两个以上的活泼邻居，那么它就可以称为活泼的。l因此，对于一个非出错节点，有三种能够情况：l平安且活泼。l非平安但活泼。l非平安且不活泼。2.9.3 基于其他缺点模型的路由基于其他缺点模型的路由活泼活泼/不活泼节点举例不活泼节点举例l以以下图是将wu的活泼/不活泼规那么用于图7-7的出错块的结果。l显然，结果是一个直角凸多边形。2.10 超立方中的容错单

33、播超立方中的容错单播 l按照运用的错误信息类型对超立方中的容错单播路由进展分类：l基于部分信息的l基于有限全局信息的l基于扩展平安等级模型的2.10.1 基于部分信息的模型基于部分信息的模型l曾经证明，l对n维立方中的任何两点u和w，假设Hu,w=k，那么从u到w恰好有n条点分别途径。其中，l有k条长度为k的途径和n-k条长度为k+2的途径l假设出错组件的数目L小于n，那么用多条途径进展路由的方法是很直接的。l音讯沿着n条点分别途径进展传送，并且其中至少有一条是好的。l这样，就可经过那条途径到达目的，途径最大长度是k+22.10.1 基于部分信息的模型基于部分信息的模型lchen和shin给出

34、了下面四种容错路由算法: l出错组件小于n-1，不确保有最优途径。l出错组件小于n-1，确保有最优途径。l出错组件无限制，不确保有最优途径。l出错组件无限制，确保有最优途径。l第2和第4种情况是所希望的，但相应的算法会引入特别的开销。2.10.1 基于部分信息的模型基于部分信息的模型第第1种情况种情况等位序列定等位序列定义l思索一个第1种情况的算法。l为了容错，一些访问过的节点也保管在音讯中。l定义：等位序列d1, d2, , dk为当前节点与目的节点不同的一切维度也叫首选维度，preferred dimensionl例如，假设0010和0111是当前节点和目的节点，那相应的等位序列就是1,3

35、l为表示一个音讯的目的，等位序列要和音讯一同传送l因当前节点会随着音讯的传送而变化，故等位序列也随着变化2.10.1 基于部分信息的模型基于部分信息的模型第第1种情况种情况音音讯的表示的表示l每个音讯都有一个n位向量标志，用以保管“空余维度Pare dimensions。l可以用这些维度来绕过出错组件。l留意空余维度就是那些没有在最初的等位序列中呈现的维度l源节点发起路由时，标志中的一切位都将清零。l音讯的表示：k, d1, d2, , dk, 音讯, 标志。lk为剩余途径长度， k会在音讯的发往过程中不时更新l当k变为0时，音讯就到达目的了。2.10.1 基于部分信息的模型基于部分信息的模型

36、算法的描画算法的描画l当节点收到一个音讯时，检查k的值以判别本身能否为音讯的目的l假设不是，节点将尝试按照剩下的等位序列中指定的维度发送音讯l每个节点都将努力沿着最短途径发送音讯。l然而，假设通往最短途径的维度的那些衔接出错，这个节点将运用空余维度经过另外的途径发送音讯。l开场时，等位序列为由源和目的地址异或得到的一切首选维度空余维度的一切位清零。2.10.1 基于部分信息的模型基于部分信息的模型算法的描画算法的描画l更正式地，这个路由算法可以描画如下。留意：ui表示沿着维度i的u的邻居。2.10.1 基于部分信息的模型基于部分信息的模型算法举例算法举例l思索以以下图中的出错超立方。l假设音讯

37、m从u=0110路由到w=1001。在u=0110处的最初音讯是4, 1, 2, 3, 4, m, 0000l按照上述算法，l节点0110将3, 2 ,3 ,4, m, 0000发送给01101=0111，l随后0111将2, 3, 4, m, 0000发送给01112=0101。2.10.1 基于部分信息的模型基于部分信息的模型算法举例算法举例contd3.由于0101的第3维链接呈现错误，节点0101将发送1, 3, m, 0000到01014=1101。4.然而，由于1101的第3维的链接呈现错误，节点1101将运用第1维标志=0100，标志记下了要绕道时的首选维度，并发送音讯2, 3,

38、 1 , m, 0101到1100。2.10.1 基于部分信息的模型基于部分信息的模型算法举例算法举例contd5.1100依次将发送1, 1, m, 0101到1000。6.随后，节点1000的第一个链接又呈现错误。这时将运用第2维此时标志=0101, 2, 1, 2, m, 0111被路由到1010。7.之后，音讯将经过1011到达目的1001。结果途径的长度是8 。2.10.2 基于有限全局信息的模型：基于有限全局信息的模型：平安等级定义平安等级定义l下面讨论具有节点缺点的超立方中的有效路由l这种方式基于每个节点的有限全局信息l这种信息被标志为平安等级。l从根本上说，平安等级就是每个节点

39、周围邻居中失效节点的大致数目。l定义：设sa=k是节点a的平安等级，称a是k-平安的；l一个失效节点是0-平安的，即最低的平安等级，l一个n-平安的节点也叫平安节点平安级别最高l假设kn，那么一个k-平安的节点就是不平安的平安等级的定义及计算平安等级的定义及计算ln维立方中，令节点a的一切邻居节点的平安等级的非递减平安形状序列为：S0, S1, S2, Sn-1，0=Si=n且0=Si=Si-1= 0, l, 2, n-1，那么sa n；否那么，假设S0, S1, S2, Sk-1 = 0, l, 2, k-1并且Sk=k-1，那么Sa=k。平安等级的计算算法平安等级的计算算法l下述算法决议了

40、每个节点的形状。l每个节点ai都保管它一切邻居节点的非递减平安形状序列l开场时，一切非出错节点都是n-平安的。l该算法需求n-1次反复到达稳定形状。平安等级举例平安等级举例l例如，以以下图的出错超立方中，l出错节点0011, 0100, 0110和1001是0-平安的黑色l节点0001, 0010, 0111和1011是1-平安的棕色，由于每个都有两个出错节点，非递减序列为0,0,2,2或 0,0,2,4或0,0,4,4,k=1l节点0000和0101是2-平安的紫色。非递减序列为：0,1,1,4,k=2l1000, 1010, 1100, 1101, 1110和1111是平安的蓝色非递减序列

41、为：0,4,4,4或1,1,4,4或0,2,4,4平安等级的性质和平安等级的性质和基于平安等级的路由基于平安等级的路由l平安等级有以下性质：l假设一个节点的平安等级是k 0k=4的图中，一定有一个每个节点都至少呈现两次的轨迹。而且，任何一个有3个以上节点并且具有一个度数小于4 的节点的图都没有那样一个轨迹。l然而，每个节点呈现两次仅仅是必要非允分条件。l思索下面的一部分轨迹，每个节点的上标i表示这个节点是第i次呈现vi1vi2vj1vj22.11.2 基于途径的路由基于途径的路由 Wu的基于轨迹的方式：充要条件的基于轨迹的方式：充要条件l假定vi和vj在轨迹中仅仅呈现两次。显然vj,vi不是这

42、个轨迹上的一个可行的路由。l因此，问题的充要条件如下：对于一个恣意给定的节点vi，在出如今最右边的vi的左边一定会至少有一个其他节点，并且在出如今最左边的vi的右边一定会至少有一个其他节点。基于轨迹的方式：基于轨迹的方式：两个延续的哈密尔顿途径两个延续的哈密尔顿途径l2.5节中的基于途径的双环路由方法是符合这个充要条件的。l确切地说，任何两个延续的哈密尔顿途径都符合这个条件。l留意：两个延续的哈密尔顿途径需求一个更强的条件l然而，假设每个节点在轨迹中呈现的次数不能多于两次，那么两个延续的哈密尔顿途径就是一个充要条件了。基于轨迹的方式：基于轨迹的方式：两个延续的哈密尔顿途径两个延续的哈密尔顿途径

43、contdl易知在任何2维圆环和任何k=4维立方中，都存在两个延续的哈密尔顿途径。l以以下图显示了在4维立方中的两个边分别的哈密尔顿回路。基于轨迹的方式：基于轨迹的方式：建立两个延续的哈密尔顿途径建立两个延续的哈密尔顿途径l在nn=4维立方中建立边分别的哈密尔顿回路的普通方法如下：l将n维立方沿着维度n分成两个n-1维立方。l每个n-1维立方中建立两个哈密尔顿回路。l把n-1维立方的两个边分别的哈密尔顿回路衔接起来，组成n维立方中的一个哈密尔顿回路。方法是：l在每个回路中去掉一个边以便突破回路，沿着维度n添加两个边从而把两个突破的回路衔接起来。l衔接剩下的两个哈密尔顿回路，从而构成n维立方中的

44、另一个哈密尔顿回路。l在n维立方中建立两个边分别的哈密尔顿途径。l从n维立方的两个边分别的哈密尔顿回路中去掉两个邻边，就得到了两个延续的哈密尔顿途径。2.11.3 运用平安等级在超立方中运用平安等级在超立方中进展组播进展组播l组播的关键问题是：l每个中间节点u包括源节点s向它的适宜的邻居节点发送一个目的节点集合u1, u2, um。l例如，l假设一个目的节点集合u1, u2, u3=0101, 1001, 0000并且节点u=1010相对地址相对地址l本节引见的算法中涉及如下的定义：l相对地址ri：取节点u与目的节点ui的地址值的异或值l上例中，u=1010；u1=0101那么相对地址r1=u

45、u1=10100101=1111l相对地址的某一位为1，表示在相应的维度上必需进展一次跳步l因此可以用目的节点关于节点u的相对地址来代表目的节点l运用相对地址的集合表示目的节点的集合，用R表示：R=ri ，其中ri=uui, 1=i=m。l上例中： u=1010； u1, u2, u3= 0101, 1001, 0000 那么R=r1, r2, r3= 1111, 0111, 1010节点间的间隔节点间的间隔 、地址总和、地址总和l由于相对地址中的1代表了一个必需的跳步，因此相对地址中1的个数|ri|=1=j=nrij代表节点u和ui的最短间隔 l如上例中：|r1|=4, |r2|=3, |r

46、3|=2l地址总和：表示集合中目的节点在不同维度的分布，运用as表示l由于相对地址的每一位对应于一个维度，取一切相对地址在某一维的值之和1的个数，就是一切目的节点在该维度的分布情况l因此，地址总和as=riRril如上例中， R=r1, r2, r3= 1111, 0111, 1010，因此as = 2232相对地址的更新相对地址的更新l为防止反复计算相对地址，仅在源节点计算相对地址。l每当具有相对地址r的目的节点被沿着维度d发送到下一个节点，r的第d位就被置为0。即这个目的节点的新的相对地址是rd。l上例u=1010，u1=0101，相对地址r1=1111，假设u1沿着第2维被送到邻居100

47、0处，那么在新的中间节点1000上，具有新的相对地址为1101，正好为r12l为防止在新的中间节点1000上重新计算相对地址，只需求在发送音讯时将目的地址的相应位置0即可即rd操作基于相对地址路由的根本描画基于相对地址路由的根本描画l为保证时间最优，运用下面的简单战略：l当目的节点ui关于中间节点u的相对地址ri的第d位等于1 时，rid将沿着d维度发送到u的邻居ud。l当目的节点ui的相对地址ri在不同的位维度有超越一个的1值时，相对地址ri可以被转发到恣意一个维度。l此时，需求在n维中确定一个优先级顺序。这个优先级顺序的信息决议了组播的结果。l优先级顺序的定义应该可以实现对途径的最大限制的

48、共享从而使流量最小运用平安等级的缘由运用平安等级的缘由l在组播中，组播音讯不应到达死端dead endl当一个特定目的节点的一切海明间隔 途径都被出错邻居阻塞时，死端就会出如今中间节点。l在这种情况下，为了到达那个目的必需绕道或回退。l为了防止尽头的呈现，应该限制向附近有出错节点的邻居发送的目的的数目。l这就是在维度有限决策时运用平安等级的缘由。基于平安等级的组播基于平安等级的组播l引见三个方法l基于平安等级的组播SLBM；l修正的基于平安等级的组播MSLBM和l基于地址总和的组播ABSMSLBMlSLBM中，维度优先级根据该维度上的邻居的平安等级事先决议的。l沿着一个维度的邻居的平安等级越高

49、，这个维度的优先级顺序就越高l当有两个或两个以上的维度上的邻居具有一样的最高平安等级时，可以运用两个方法。lSLBM中，随机决议它们的优先顺序lMSLBM见下页MSLBMlMSLBM中，当两个或更多邻居具有一样的平安等级时l维度优先顺序根据相应位在一切目的的地址总和中的值决议。l从根本上说，假设维度d上的邻居可以承当最大能够的目的节点，即假设asd在地址总和中具有最大值，那么d就有最高优先级。l当地址总和中有超越一个的位其有一样的最大值时，选择是随机的。l下一个优先级的选择运用同样的方法，只不过此时要根据更新的目的节点集，即去掉上述被转发到高优先级维度的节点ASBMlASBM中，维度优先级主要

50、依赖于地址总和中的位值l假设在一个维度上的邻居节点能接受最大数目的节点，那这个维度就具有最高优先级。l为保证时间最优，只需与选定的邻居的海明间隔 不超越kk为该邻居的平安等级的目的节点才干被包括进来。l在这种情况下，一切邻居的平安等级和目的节点的相对间隔 都在决策中表达出来了。l当存在一个以上的能承载同样最大数目的目的节点的邻居时l可以运用一种修正的ASBM正如MSLBM那样，这些邻居的优先级根据其平安等级确定l在ASBM中，这些节点的优先顺序是随机选择的。SLBM、MSLBM和和ASBMl假设源节点在出错的n维立方中是平安的，那么由SLBM, MSLBM或ASBM产生的组播一定是时间最优的。

51、l当源节点不平安并且出错节点的个数不超越n-1时，从源节点到一个目的的途径的长度l或者等于相应的海明间隔 ，或者比相应的海明间隔 多2。l假设源和任一目的间的相对间隔 不超越源的平安等级，那么由SLBM, MSLBM或ASBM产生的组播一定是时间最优的。算法举例算法举例l以以下图显示了一个有四个出错节点的Q4 ，出错节点为黑色节点：1100, 0110, 0011和0001算法举例：算法举例：计算平安等级计算平安等级l开场，一切非出错节点都是4-平安的，即平安的l第一轮邻居间交换过信息后l节点0010, 0111, 0100和1110 因有两个或两个以上的出错邻居，都从4-平安变为1-平安形状

52、l其他节点的形状坚持不变。算法举例：算法举例：计算平安等级计算平安等级contdl在第二轮之后，节点0000 和0101 的形状变为2-平安，这是由于它们有两个1-平安的节点和一个2-平安的节点。l两轮之后，每个节点的平安等级到达稳定。l图中节点中的数字即代表该节点最终的平安等级算法举例：算法举例：计算相对地址和地址总和计算相对地址和地址总和l假定图中源节点是平安节点1000 ，组播集合u=u1, u2, u3, u4, u5, u6=0000, 0010, 0100, 0101, 0111, 1001源和目的之间的相对地址集合为R=r1, r2, r3, r4, r5, r6=1000, 1

53、010, 1100, 1101, 1111, 0001因此，地址总和as=5323算法举例：算法举例：运用运用SLBMlSLBM方法仅运用邻居维度序列ds所代表的邻居的平安等级来确定邻居节点间的优先级。l本例中，维度2具有最高的优先级，其次是维度1和维度4；维度3具有最低的优先级。l由于r2和r5的第二位是1，所以r22和r52和组播音讯一同将被发往节点10101000 沿着维度2 的邻居。l假定组播音讯总是附加在从一个节点转发到另一个节点的目的节点的相对地址上面。l在R中剩余的节点中，r4和r6在第一位的值为1。地址r41和r61将被发往节点1001。l由于剩下的r1和r3的第四位的值是1，

54、地址r14和r34将沿着维度4访问1000的邻居。算法举例：算法举例：运用运用SLBM contdl没有目的节点被发往沿着维度3的邻居l对1000的收到目的节点的邻居节点递归运用这个步骤，可以产生一个如图的组播树。l树的深度就是所用的时间步数，树中的边的数目是所用的流量步数。本例，时间步数是4 流量步数是10 算法举例：算法举例：运用运用MSLBMlMSLBM 也运用邻居维度序列ds 来决议优先级。l然而，当两个或两个以上的邻居具有同样的平安等级的时候，将由剩余目的节点的地址总和as来决出胜负。l上例中，源节点1000沿着维度1和2的两个邻居具有同样的平安等级。l根据as=5323，沿维度2的

55、邻居1010可承载2as第二位的值个目的节点沿维度1的邻居1001可承载3个目的节点。这样，1001就比1010有更高的优先级。结果是r41, r51, 和r61被发往1001。r22被发往1010。算法举例：算法举例：运用运用MSLBM contdlr14和r34被发往沿着维度4的1000的邻居。l以以下图显示了具有4个时间步骤和9个流量步骤的组播树算法举例：算法举例：运用运用ASBMl在ASBM中，维度优先级取决于目的节点的地址总和。l即在地址总和中具有最大值的那个维度具有最大的优先级。l在该维度的地址为1的目的将被发往相应的邻居。l然而，为防止向一个不平安或出错的邻居发送过多的目的，将目的地址发往一个k-平安的邻居仅当相应的目的节点与这个k-平安的邻居的海明间隔 小于或等于k。l当有两个或两个以上的邻居可承载一样最大数目的目的节点时，选择是随机的。l当然也可很容易地将ASBM扩展，从而可根据邻居的平安等级来进展选择。