高级操作系统高级操作系统Advanced Operating System熊焰yxiongustc.edu.cn0551_3600689中国科学技术大学计算机系第二章第二章 分布式路由算法分布式路由算法l分布式路由算法导论l一般类型网络的最短路径路由算法 l特殊类型网络的单播算法l特殊类型网络中的多播算法l虚信道和虚网络 l完全自适应和无死锁路由算法l几个自适应和无死锁路由算法 l容错单播的一般方法 l网格和圆环中的容错单播算法l超立方中的容错单播算法l容错组播算法2.5 虚信道和虚网络虚信道和虚网络l网络资源l在存储转发交换中，资源是缓冲区；l在虫孔路由中，资源是信道。l网络通信中，若消息在占有资源的前提下可以申请资源，就有可能发生死锁l通过控制路由的自适应性可以预防和避免死锁，同时也保证一定的容错性。 l虚信道和虚网络经常用于实现无死锁、自适应和（或）容错的路由。2.5 虚信道和虚网络虚信道和虚网络通过网络分区避免死锁通过网络分区避免死锁l通过网络分区可以避免死锁l给定的网络可以分成几个子网。l根据源和目标的位置，消息被路由到不同的子网l举例说明：l3X3网格的适应性双Y信道路由l如图：l在Y方向有两个物理信道（双向）（a）一个3X3网格的 双Y信道网2.5 虚信道和虚网络虚信道和虚网络通过网络分区避免死锁（通过网络分区避免死锁（contd）l上述网格被分成正、负两个子网（如下图）l如果目标位于源的右侧，则使用正网；l否则将使用负网。l当源和目标同列时，两个子网都不用。l由于两个子网中都没有回路，所以可避免死锁。 （b）正网络（c）负网络2.5虚信道和虚网络虚信道和虚网络虚信道虚信道l若网络没有双Y信道，则可用几个虚信道复用一个物理信道l每个虚信道都有自己的缓冲区。l当物理信道被其它虚信道使用时，就用这个缓冲区保存消息l若虚信道间没有循环等待，就可避免死锁。l假设上例改为单Y信道网，那么原来的正、负子网中所有的Y信道都是虚信道。2.5虚信道和虚网络虚信道和虚网络虚信道虚信道（contd）l当两个虚信道共享一个物理信道时，信道利用率大幅提高。l虽然虚信道提供了一个具有多重信道的网络，但仍需仔细设计路由算法。例如，l可以按照信道标记的升序使用虚信道，以便避免虚信道间循环依赖。2.5虚信道和虚网络虚信道和虚网络虚网络虚网络l比虚信道更高一级的虚拟化是虚网络l一个给定的物理网络被分成几个虚网络，每个虚网络包括一系列的虚信道。l虚网络中相邻的节点被映射到物理网络中时也要相邻l一般地，一个虚网络中的虚信道设置应避免信道间的回路。虽然仍有可能存在互相交叉的虚网络回路，但可以通过使虚网络遵循全序或偏序来避回路l前面那个例子中，若使用单Y信道，则前面的正、负子网可认为是两个虚网络。l显然每个网络中都没有回路。因每个路由过程最多只使用一个虚网络，所以不会产生互相交叉的虚网络回路。 2.5虚信道和虚网络虚信道和虚网络l虽然虚网络包含虚信道，二者是完全不同的概念。l一般地，虚信道的使用是与路由过程紧密相连的，包括源和目标的位置。必须合理安排虚信道，以避免死锁。l虚网络通常设计为没有回路，因而路由算法可以不必考虑死锁，除非存在交叉虚网络的依赖性2.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例l考虑一个有四个节点的单向环。如果同时有几个路由进程启动，就会发生死锁。2.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例（contd）l通过给每个链接增加两个虚信道可以避免死锁l如图，信道被分为l高虚信道，和Ch0, Ch1, Ch2, Ch3l低虚信道Cl0, Cl1, Cl2, Cl32.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例（contd）l若源地址大于目标地址，l可从任何一个信道开始；l但一旦使用一个高（低）信道，那以后也要使用同一信道l若源地址小于目标地址，l首先使用高信道，经过节点P3后，高虚信道切换为低虚信道l图示为相应的信道依赖图l以信道为节点l边为信道之间的切换关系P32.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例l在上述虚信道方法中，给定的环被分成两个虚环：Vr1和Vr2l每个环中都有一个回路。两个虚环：Vr1：高信道形成的虚环Vr0：低信道形成的虚环虚环形成的回路。图中，节点内的边表示回路中信道的切换关系2.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例（contd）l要避免虚网络内部的回路，可以l在vr1中禁止从Ch0切换到Ch3，和l在vr0中禁止从Cl0切换到C13。P3中，Ch0到Ch3的切换被禁止；Cl0到Cl3的切换也被禁止2.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例（contd）l可在任一步进行从vr1到vr0 的虚网络切换（如图）l例如l若源地址大于目标地址，如l从P2到P0的路由可以从Ch2开始，并在P1切换至Cl1l从P3到P0的路由中，可在P2或P1进行切换l也可以不切换l但若目标地址大于源地址，则必须在节点P3切换，因为1.在单向环中，若目标地址大于源地址，则必然要经过P3路由2.两个虚环都不允许在P3进行从Ch0到Ch3 和Cl0到Cl3 的切换。所以在P3只能进行Ch0到Cl3的切换图中，每个节点都可以进行vr1到vr0的虚网络切换2.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例（contd）l基于虚网络的路由过程比基于虚信道的路由有更强的适应能力。在上例中，l虚信道路由仅在P3进行高虚信道到低虚信道的切换l虚网络路由允许在任一点进行虚网络切换l为了保证从vr1到vr0的切换生成一个合法的路由路径，l若Cli是vr0中的切换信道，则i必须不能小于剩余的路由跳跃数。2.5虚信道和虚网络虚信道和虚网络双环路由双环路由l上述每一个单向信道增加一个虚信道的方法叫双环路由l形式化地描述双环路由：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方向的路由，但在Y方向上由于错误被阻塞，这个信息就不能被继续转发l但没有限制的适应性路由可能引发死锁。l因此，必须在不引发死锁的前提下增加适应性2.6 完全自适应和无死锁路由算法完全自适应和无死锁路由算法l几乎所有的完全适应性路由都可以通过增加一定数量的虚信道（或虚网络）来避免死锁。l例如，l一个最小化的适应性的n 维立方路由可以通过加入n个虚信道来避免死锁。l每一步都使用比前一个具有更高标记的信道。l因为需要n步，所以n个虚信道足以避免虚信道之间的循环等待。l然而使用虚信道会引入附加的缓冲区等开销。所以，要尽量限制虚信道的数目。2.6.1 虚信道类虚信道类 l如前所述，通过引入足够多的虚信道，任何路由都可以保证避免死锁。l当路由开始时，使用虚信道1，vc1。l在第i 步使用虚信道i，vci及相应的链接。l如果一个给定网络的最长路径（也叫直径）是Dmax那么就要用Dmax个虚信道；2.6.1 虚信道类虚信道类l为了减少虚信道的数量，可将一个网络分成几个节点的子集，每个子集都不会包含相邻的接点。l例如，l考虑一个形似跳棋盘的2维网格，上面有黑白方格。l黑节点属于个子集，白色节点属于另外一个。l当一个消息从一个白色节点移动到黑色节点时，就将虚信道的标记加一。l如果是从黑色节点向白色节点移动，虚信道标记保持不变。l显然，在2维网格中，节点标记的改变次数最多为路由步数的一半。这样虚信道的总数就缩减了一半。2.6.1 虚信道类虚信道类l可以将上述思想一般化：l将给定网络分成k个子集S1, S2, Sk ，每个子集都不包含相邻节点l当一个消息从子集Si中的一个节点移动到子集Sj中的一个节点（i j ）时，称之为上移动；反之为负移动。l发生负移动时，虚信道标记加一l假定信道标记从1 开始l从而，所需信道的个数就是一个路由路径中负移动的个数。l目标就是要选择一个合适的k以及一个划分，使路由过程中的负移动个数最小2.6.2 逃逸信道逃逸信道等待和非等待信道等待和非等待信道l使用逃逸信道的路由算法中，虚信道被分为等待信道（又称为逃逸信道）和l若一个等待信道处于繁忙状态，而此时一个消息需要通过该信道，则这个消息必须等待，直到该信道可用l即一个等待信道能够阻塞消息非等待信道（又称为一般信道）l若一个消息碰到一个处于繁忙状态的非等待信道，它不必被阻塞以等待该信道变得可用，可以选择其他信道l因此，一个消息会首先考虑通过非等待信道到达目标l若所有的非等待信道都繁忙，它就考虑等待信道2.6.2 逃逸信道逃逸信道混合路由混合路由 l使用逃逸信道扩展完全适应的概念l例如，可以用两个路由进程实现混合路由：路由进程1：完全适应性路由完全适应性路由，使用标记为非等待的虚信道；路由进程2：限制性但无死锁路由限制性但无死锁路由可能是XY路由或e-立方等决定性路由使用标记为等待的虚信道。2.6.2 逃逸信道逃逸信道混合路由混合路由（contd）l混合路由算法：1.开始时，使用完全适应路由，直到阻塞为止；2.然后切换到限制性路由。l混合路由是无死锁的l由于等待信道是在无死锁路由中定义的，并且l消息仅仅等待上述等待信道l合理分配等待和非等待信道是关系到混合路由效率的关键问题2.6.2 逃逸信道逃逸信道混合路由的扩展混合路由的扩展Il扩展I：当消息发现等待信道被占用时，可以使用非等待信道l扩展I增加灵活性的同时也引入了选定的逃逸信道之间新的依赖性。l通过使用一个或多个中间的一般信道，一个逃逸信道可能间接地依赖于另一个逃逸信道。l因此无回路条件必须包括逃逸信道之间的所有间接依赖。l不幸的是，没有循环依赖只是不发生死锁的一个充分条件；也即，对于一个特定的虫孔网络，若使用某一个路由算法，扩展I太弱，不会得到任何结果。扩展信道依赖图中的一个回路可能表示一个死锁状态，也可能不是。2.6.2 逃逸信道逃逸信道混合路由的扩展混合路由的扩展I IlDuato通过使用基于消息目标的逃逸路径进一步扩展了上述思想 l对于不同的目标，使用不同的逃逸信道。l在同样的无回路条件下，可以得到一个无死锁的充分必要条件。l然而，在生成扩展信道依赖图的时候，直接依赖、间接依赖、直接交叉依赖（在不同目标的逃逸信道之间）和间接交叉依赖都要被考虑进去。2.6.2 逃逸信道逃逸信道l上述两个扩展都可用于避免死锁。l为了设计一个无死锁的路由函数，首先创建一个名为R1(x,y)的路由子函数，它的功能是将当前和目标节点映射到当前节点的输出信道的子集。R1(x,y)是连通的，无回路的。可以通过增加信道或者将已有信道分割为虚信道将R1(x,y)扩展为R(x,y)，以便增加可选路径的数目，同时又不会在R1(x,y)的扩展信道依赖图中增加回路。l这一设计规程又被称为Duato协议。2.6.2 逃逸信道逃逸信道维度逆转路由维度逆转路由 l如果不要求最小路由，那么虚信道的数量还可以减少。l对于一个k元n维立方（没有环绕连接），有如下的一般非最小无死锁路由：l对每个物理信道，有k个虚信道与之对应l其中一个用于逃逸信道，以便进行无死锁的按维排序的路由l消息可以按照任何方向路由，而不一定是最小路径。l每个消息都有一个维度逆转数DR相对应，lDR：记录消息从高维度路由到低维度的次数。2.6.2 逃逸信道逃逸信道维度逆转路由维度逆转路由（contd）l一旦一个消息取得一个信道，它就将该信道标记为当前的DR数。l为了避免死锁，一个DR数为i的消息不能等待一个DR数为j的信道，这里ij。l此时，选用下一层的虚信道。l假定每个未被访问的信道的DR标记为0。l当虚信道的标记达到k时，就使用决定性的按维度排序的路由。2.7 几个部分适应和无死锁路由算几个部分适应和无死锁路由算法法l很多路由算法的路由适应性仅对一小部分虚信道有效。这种算法属于部分适应性路由l本节讨论三个部分适应性和无死锁路由算法l转弯模型l平面自适应模型l其他部分自适应模型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右下图为一个负向优先路由协议。l可以有6个转弯l从正向到负向的转弯，也即北到东和东到北，被禁止X方向Y方向X负到Y正Y负到X正X正到Y负Y正到X负正向优先协议负向优先协议2.7.1 转弯模型转弯模型转弯模型的适应性转弯模型的适应性l由于源和目标的位置的不同，转弯模型可能有适应性，也可能没有。l下图显示了源s和目标d的两种不同位置。l若目标位于源的东北或西南方，那么正向优先路由就是完全适应性的，如图al否则，就是决定性的，如图b（a）完全适应性路由（b）确定性路由东北东南OKNot OK2.7.1 转弯模型转弯模型转弯模型的平衡性转弯模型的平衡性l某些情况下，上述不平衡的适应可能会导致拥塞或不平衡的工作量。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），A1（维度为d1和d2），和A2（维度为d2和d3）平面自适应路由所允许的路径2.7.2 平面自适应模型平面自适应模型举例举例l对每个Ai，引入三个虚信道，一个沿着第i 维，两个沿着第（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正网络负网络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 位为1 的节点（负向链接）l另一个是从第i 位为1的节点到第i位为0 的节点（负向连接）。l为了打破一个回路，只需禁止从较高维度的正向连接向沿着维度i的负向连接转换即可，除非这个转换符合e立方路由。2.7.3 其他部分自适应模型其他部分自适应模型l如果e立方路由满足维度递增的顺序，一个沿着维度dim(c1)的信道c1到一个沿着维度dim(c2)的信道c2的转换是允许的当且仅当下述条件中的一个为真：1.dim(c1)0)网中，使用三个虚信道来避免死锁。l对n维圆环，每个环绕信道需要两个虚信道来打破同一个维度中的回路。总之，对n(n0)维圆环需要6 个虚信道。l2 维网格中，使用两个虚信道，网络被分成正/负向两个子网。l类似地，在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 基于有限全局信息的路由基于有限全局信息的路由Wu的最优容错路由算法的最优容错路由算法l有两个最优和适应性容错的路由算法：l面向目标路由，和l面向源路由。l为简单起见，假定源节点是(0, 0)，目标节点是(i, j)，且i, j =0，即路由永远是向东北方向的。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目标的路由面向目标的路由l面向目标的路由使用最短路径区域RMP的概念：l对给定的源和目标对，RMP包含最短路径的所有中间节点l为建立RMPl做一条从目标节点(i, j)开始到Y轴结束的线。l遇到出错块时，先向南绕过出错块，然后继续向西l类似地，建立一个从(i, j)开始向南到X轴截止的线。l遇到出错块时，先向西绕过出错块，然后继续向南。l已经证明由向西和向南的线以及X轴和Y轴围起来的区域是RMP。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目标的路由面向目标的路由举例举例l下图显示了一个RMP的例子，这里向西的线标记为路径A，向南的线标记为路径B。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目标的路由面向目标的路由l仅当源是扩展安全的，才使用面向目标路由l源通过一个最优或不是最优的路径向目标发一个信号l接到信号后目标发两个信号，一个向西一个向南向西的信号建立RMP的路径A，向南的信号建立RMP的路径B 。l一旦源收到来自目标的两个信号，就意味着RMP已建立起来。源就用任何一种适应性最小路由发送路由消息。l遇到路径A（或路径B）的边界时，剩下的路由就要沿着路径A （路径B ）发往目标。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由l为支持面向源的最优路由，必须把出错块的信息分布到系统中的特定节点上。l举例说明：下图显示了一个出错块L1, L2, L3, L4与出错块的四条线平行x=0和y=0的区域被分成8 个子区域：R1R8L14上的点可划归任一相邻区域。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由（contd）l显然，l可用任一最小路由算法到达R1, R2, R3 , R7, R8中的点l可用XY路由（先X后Y）到达R6中的任何点。l可用YX路由（先Y后X）到达R4中的任何点。l用XY路由和YX路由都可到达R5 中的点。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由（contd）l当目标节点位于R4或R6时，为达到最优路由，位于L1（位于(x,y)西侧的节点）和L2（位于(x,y)南侧的节点）上的特定节点必须具有这个出错块的信息。这些信息可以用出错块的相应角的位置来编码。l特别地，为每个出错块建立两个概念上的路径l路径1（虚线）：(,y)(x,y)(x,y)(x,y)(- ,y)l路径2（实线）：(x, )(x,y)(x,y)(x,y)(x,- )2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由（contd）l显然，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）为止。1.（遇到路径1的L1）若目标节点在路径1的南/东侧，那消息将一直留在L1直到到达出错块的L1和L4的边界为止；否则将穿过L1。2.（遇到路径2的L2）若目标节点在路径2的北/西侧，那消息将一直留在L2直到到达出错块的L2和L4的边界为止；否则将穿过L2。2.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源路由的步骤面向源路由的步骤（contd）l上述方法中，两个虚信道足以避免死锁。l一个简单的方法是为东北和东南方向的路由使用正向子网，对西北和西南方向的路由使用负向子网。2.9.3 基于其他故障模型的路由基于其他故障模型的路由Wu的直角凸多边形模型的直角凸多边形模型l虽然矩形出错块很简单，但它引入了很多被禁止的非出错节点，即它们将不会在路由过程中起作用。l但矩形为凸形的特性使得可以用最少的虚信道把路由信息绕过出错区域。l另外一些非矩形的凸形出错块也被引入了。lWu将出错块模型扩展为直角凸多边形模型。l一个凸多边形的定义是：多边形P，P中的任意两点之间的线段都在P内部。l在直角凸多边形中，线段被限制为只能是水平或垂直的。2.9.3 基于其他故障模型的路由基于其他故障模型的路由直角凸多边形直角凸多边形l可以将给定的矩形出错块转换为一系列分离的直角凸多边形l这一思想根源于这样一个事实：l可以通过将出错块中的一些非出错节点移出去，从而将它们激活，同时又保持这个区域的凸性。2.9.3 基于其他故障模型的路由基于其他故障模型的路由活跃活跃/不活跃节点不活跃节点l与标准出错块中的安全/非安全定义不同，Wu给出了活跃/不活跃节点的概念：l所有出错节点都是非活跃的，所有安全节点都是活跃的。l一个非安全节点开始的时候是非活跃的但如果它有两个或两个以上的活跃邻居，那么它就可以称为活跃的。l因此，对于一个非出错节点，有三种可能情况：1.安全且活跃。2.非安全但活跃。3.非安全且不活跃。2.9.3 基于其他故障模型的路由基于其他故障模型的路由活跃活跃/不活跃节点举例不活跃节点举例l下图是将wu的活跃/不活跃规则用于图7-7的出错块的结果。l显然，结果是一个直角凸多边形。2.10 超立方中的容错单播超立方中的容错单播 l按照使用的错误信息类型对超立方中的容错单播路由进行分类：l基于局部信息的l基于有限全局信息的l基于扩展安全等级模型的2.10.1 基于局部信息的模型基于局部信息的模型l已经证明，l对n维立方中的任何两点u和w，如果H(u,w)=k，那么从u到w恰好有n条点分离路径。其中，l有k条长度为k的路径和(n-k)条长度为k+2的路径l若出错组件的数目L小于n，那么用多条路径进行路由的方法是很直接的。l消息沿着n条点分离路径进行传送，并且其中至少有一条是好的。l这样，就可通过那条路径到达目标，路径最大长度是k+22.10.1 基于局部信息的模型基于局部信息的模型lchen和shin给出了下面四种容错路由算法: 1.出错组件小于n-1，不确保有最优路径。2.出错组件小于n-1，确保有最优路径。3.出错组件无限制，不确保有最优路径。4.出错组件无限制，确保有最优路径。l第2和第4种情况是所希望的，但相应的算法会引入特别的开销。2.10.1 基于局部信息的模型基于局部信息的模型第第1种情况种情况等位序列定义等位序列定义l考虑一个第1种情况的算法。l为了容错，一些访问过的节点也保存在消息中。l定义：等位序列d1, d2, , dk为当前节点与目标节点不同的所有维度（也叫首选维度，preferred dimension）l例如，假设0010和0111是当前节点和目标节点，那相应的等位序列就是1,3l为表示一个消息的目标，等位序列要和消息一起传送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 基于局部信息的模型基于局部信息的模型算法的描述算法的描述l当节点收到一个消息时，检查k的值以判断自身是否为消息的目标l若不是，节点将尝试按照剩下的等位序列中指定的维度发送消息l每个节点都将努力沿着最短路径发送消息。l然而，若通往最短路径的维度的那些连接出错，这个节点将使用空余维度通过另外的路径发送消息。l开始时，等位序列为由源和目标地址异或得到的所有首选维度空余维度的所有位清零。2.10.1 基于局部信息的模型基于局部信息的模型算法的描述算法的描述l更正式地，这个路由算法可以描述如下。注意：u(i)表示沿着维度i的u的邻居。2.10.1 基于局部信息的模型基于局部信息的模型算法举例算法举例l考虑下图中的出错超立方。l假设消息m从u=0110路由到w=1001。在u=0110处的最初消息是(4, 1, 2, 3, 4, m, 0000)l按照上述算法，1.节点0110将(3, 2 ,3 ,4, m, 0000)发送给01101=0111，2.随后0111将(2, 3, 4, m, 0000)发送给01112=0101。2.10.1 基于局部信息的模型基于局部信息的模型算法举例算法举例（contd）3.由于0101的第3维链接出现错误，节点0101将发送(1, 3, m, 0000)到01014=1101。4.然而，由于1101的第3维的链接出现错误，节点1101将使用第1维（标记=0100，标记记下了要绕道时的首选维度），并发送消息(2, 3, 1 , m, 0101)到1100。2.10.1 基于局部信息的模型基于局部信息的模型算法举例算法举例（contd）5.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从根本上说，安全等级就是每个节点周围邻居中失效节点的大致数目。l定义：设s(a)=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)，那么s(a) n；否则，如果(S0, S1, S2, Sk-1 )=( 0, l, 2, k-1)并且(Sk=k-1)，那么S(a)=k。安全等级的计算算法安全等级的计算算法l下述算法决定了每个节点的状态。l每个节点a(i)都保存它所有邻居节点的非递减安全状态序列l开始时，所有非出错节点都是n-安全的。l该算法需要n-1次重复达到稳定状态。安全等级举例安全等级举例l例如，下图的出错超立方中，出错节点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安全等级的性质和安全等级的性质和基于安全等级的路由基于安全等级的路由l安全等级有以下性质：l如果一个节点的安全等级是k (0k=4)的图中，一定有一个每个节点都至少出现两次的轨迹。而且，任何一个有3个以上节点并且具有一个度数小于4 的节点的图都没有那样一个轨迹。l然而，每个节点出现两次仅仅是必要非允分条件。l考虑下面的一部分轨迹，每个节点的上标i表示这个节点是第i次出现vi1vi2vj1vj22.11.2 基于路径的路由基于路径的路由 Wu的基于轨迹的模式：充要条件的基于轨迹的模式：充要条件l假定vi和vj在轨迹中仅仅出现两次。显然(vj,vi)不是这个轨迹上的一个可行的路由。l因此，问题的充要条件如下：对于一个任意给定的节点vi，在出现在最右边的vi的左边一定会至少有一个其他节点，并且在出现在最左边的vi的右边一定会至少有一个其他节点。基于轨迹的模式：基于轨迹的模式：两个连续的哈密尔顿路径两个连续的哈密尔顿路径l2.5节中的基于路径的双环路由方法是符合这个充要条件的。l确切地说，任何两个连续的哈密尔顿路径都符合这个条件。l注意：两个连续的哈密尔顿路径需要一个更强的条件l然而，如果每个节点在轨迹中出现的次数不能多于两次，那么两个连续的哈密尔顿路径就是一个充要条件了。基于轨迹的模式：基于轨迹的模式：两个连续的哈密尔顿路径两个连续的哈密尔顿路径（contd）l易知在任何2维圆环和任何k(=4)维立方中，都存在两个连续的哈密尔顿路径。l下图显示了在4维立方中的两个边分离的哈密尔顿回路。基于轨迹的模式：基于轨迹的模式：建立两个连续的哈密尔顿路径建立两个连续的哈密尔顿路径l在n(n=4)维立方中建立边分离的哈密尔顿回路的一般方法如下：1.将n维立方沿着维度n分成两个n-1维立方。2.每个n-1维立方中建立两个哈密尔顿回路。3.把n-1维立方的两个边分离的哈密尔顿回路连接起来，组成n维立方中的一个哈密尔顿回路。方法是：l在每个回路中去掉一个边以便打破回路，沿着维度n增加两个边从而把两个打破的回路连接起来。4.连接剩下的两个哈密尔顿回路，从而形成n维立方中的另一个哈密尔顿回路。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=uu1=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=nri(j)代表节点u和ui的最短距离l如上例中：|r1|=4, |r2|=3, |r3|=2l地址总和：表示集合中目标节点在不同维度的分布，使用as表示l由于相对地址的每一位对应于一个维度，取所有相对地址在某一维的值之和（1的个数），就是所有目标节点在该维度的分布情况l因此，地址总和as=riRril如上例中， R=r1, r2, r3= 1111, 0111, 1010，因此as = 2232相对地址的更新相对地址的更新l为避免重复计算相对地址，仅在源节点计算相对地址。l每当具有相对地址r的目标节点被沿着维度d发送到下一个节点，r的第d位就被置为0。即这个目标节点的新的相对地址是r(d)。l上例u=1010，u1=0101，相对地址r1=1111，假如u1沿着第2维被送到邻居1000处，则在新的中间节点（1000）上，具有新的相对地址为1101，正好为r1(2)l为避免在新的中间节点1000上重新计算相对地址，只需要在发送消息时将目标地址的相应位置0即可（即r(d)操作）基于相对地址路由的基本描述基于相对地址路由的基本描述l为保证时间最优，使用下面的简单策略：l当目标节点ui关于中间节点u的相对地址ri的第d位等于1 时，ri(d)将沿着d维度发送到u的邻居u(d)。l当目标节点ui的相对地址ri在不同的位（维度）有超过一个的1值时，相对地址ri可以被转发到任意一个维度。l此时，需要在n维中确定一个优先级顺序。这个优先级顺序的信息决定了组播的结果。l优先级顺序的定义应该能够实现对路径的最大限度的共享从而使流量最小使用安全等级的原因使用安全等级的原因l在组播中，组播消息不应到达死端（dead end）l当一个特定目标节点的所有海明距离路径都被出错邻居阻塞时，死端就会出现在中间节点。l在这种情况下，为了到达那个目标必须绕道或回退。l为了避免尽头的出现，应该限制向附近有出错节点的邻居发送的目标的数目。l这就是在维度有限决策时使用安全等级的原因。基于安全等级的组播基于安全等级的组播l介绍三个方法l基于安全等级的组播SLBM；l修正的基于安全等级的组播（MSLBM）和l基于地址总和的组播ABSMSLBMlSLBM中，维度优先级根据该维度上的邻居的安全等级事先决定的。l沿着一个维度的邻居的安全等级越高，这个维度的优先级顺序就越高l当有两个或两个以上的维度上的邻居具有相同的最高安全等级时，可以使用两个方法。1.SLBM中，随机决定它们的优先顺序2.MSLBM（见下页）MSLBMlMSLBM中，当两个（或更多）邻居具有相同的安全等级时l维度优先顺序根据相应位在所有目标的地址总和中的值决定。l从根本上说，若维度d上的邻居可以承担最大可能的目标节点，即若as(d)在地址总和中具有最大值，则d就有最高优先级。l当地址总和中有超过一个的位其有相同的最大值时，选择是随机的。l下一个优先级的选择使用同样的方法，只不过此时要根据更新的目标节点集，即去掉上述被转发到高优先级维度的节点ASBMlASBM中，维度优先级主要依赖于地址总和中的位值l若在一个维度上的邻居节点能承受最大数目的节点，那这个维度就具有最高优先级。l为保证时间最优，只有与选定的邻居的海明距离不超过k（k为该邻居的安全等级）的目标节点才能被包括进来。l在这种情况下，所有邻居的安全等级和目标节点的相对距离都在决策中体现出来了。l当存在一个以上的能承载同样最大数目的目标节点的邻居时1.可以使用一种修正的ASBM正如MSLBM那样，这些邻居的优先级根据其安全等级确定2.在ASBM中，这些节点的优先顺序是随机选择的。SLBM、MSLBM和和ASBMl若源节点在出错的n维立方中是安全的，那么由SLBM, MSLBM或ASBM产生的组播一定是时间最优的。l当源节点不安全并且出错节点的个数不超过n-1时，从源节点到一个目标的路径的长度l或者等于相应的海明距离，或者比相应的海明距离多2。l若源和任一目标间的相对距离不超过源的安全等级，那么由SLBM, MSLBM或ASBM产生的组播一定是时间最优的。算法举例算法举例l下图显示了一个有四个出错节点的Q4 ，出错节点为黑色节点：1100, 0110, 0011和0001算法举例：算法举例：计算安全等级计算安全等级l开始，所有非出错节点都是4-安全的，即安全的l第一轮邻居间交换过信息后节点0010, 0111, 0100和1110 因有两个或两个以上的出错邻居，都从4-安全变为1-安全状态其他节点的状态保持不变。算法举例：算法举例：计算安全等级（计算安全等级（contd）l在第二轮之后，节点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, 1010, 1100, 1101, 1111, 0001因此，地址总和as=5323算法举例：算法举例：使用使用SLBMlSLBM方法仅使用邻居维度序列（ds）所代表的邻居的安全等级来确定邻居节点间的优先级。l本例中，维度2具有最高的优先级，其次是维度1和维度4；维度3具有最低的优先级。l因为r2和r5的第二位是1，所以r2(2)和r5(2)和组播消息一起将被发往节点1010（1000 沿着维度2 的邻居）。l假定组播消息总是附加在从一个节点转发到另一个节点的目标节点的相对地址上面。l在R中剩余的节点中，r4和r6在第一位的值为1。地址r4(1)和r6(1)将被发往节点1001。l因为剩下的r1和r3的第四位的值是1，地址r1(4)和r3(4)将沿着维度4访问1000的邻居。算法举例：算法举例：使用使用SLBM （contd）l没有目标节点被发往沿着维度3的邻居l对1000的收到目标节点的邻居节点递归使用这个步骤，可以产生一个如图的组播树。l树的深度就是所用的时间步数，树中的边的数目是所用的流量步数。本例，时间步数是4 流量步数是10 算法举例：算法举例：使用使用MSLBMlMSLBM 也使用邻居维度序列（ds ）来决定优先级。l然而，当两个或两个以上的邻居具有同样的安全等级的时候，将由剩余目标节点的地址总和（as）来决出胜负。l上例中，源节点1000沿着维度1和2的两个邻居具有同样的安全等级。l根据as=5323，沿维度2的邻居1010可承载2(as第二位的值)个目标节点沿维度1的邻居1001可承载3个目标节点。这样，1001就比1010有更高的优先级。结果是r4(1), r5(1), 和r6(1)被发往1001。r2(2)被发往1010。算法举例：算法举例：使用使用MSLBM （contd）lr1(4)和r3(4)被发往沿着维度4的1000的邻居。l下图显示了具有4个时间步骤和9个流量步骤的组播树算法举例：算法举例：使用使用ASBMl在ASBM中，维度优先级取决于目标节点的地址总和。l即在地址总和中具有最大值的那个维度具有最大的优先级。l在该维度的地址为1的目标将被发往相应的邻居。l然而，为避免向一个不安全或出错的邻居发送过多的目标，将目标地址发往一个k-安全的邻居仅当相应的目标节点与这个k-安全的邻居的海明距离小于或等于k。l当有两个或两个以上的邻居可承载相同最大数目的目标节点时，选择是随机的。l当然也可很容易地将ASBM扩展，从而可根据邻居的安全等级来进行选择。