（电路与系统专业论文）超立方体网络中容错路由的可靠性研究.pdf

一 南京邮电大学 硕士学位论文摘要 学科、专业：工学电路与系统 研究方向：通信丕统数亘靠丝撞苤 作 者：一2 0 0 7 级研究生梅新岩 i i ir l ff i l li l f li i i ii il y 17 5 4 9 7 6 题目：超立方体网络中容错路由的可靠性研究 英文题目： r e s e a r c ho nt h er e l i a b l ef a u l t - t o l e r a n tr o u t i n gi n h y p e r c u b e s - 主题词：容错路由，超立方体网络，局部安全信息，最大安全子立方体，结点树 k e y w o r d s ：f a u l t - t o l e r a n tr o u t i n g , h y p e r c u b e s ，l o c a l s a f e t y , m a x i m a l s a f e s u b c u b e s ， n o d e t r e e 摘要 摘要 超立方体网络拓扑结构是多处理机系统中常见的一种，并且在i n t e r a c t 上具有广泛的 应用，因此基于超立方体网络的容错性成为研究的焦点。随着多处理机系统规模的增大， 系统出现失效链路和故障结点的概率也随之增大。论文在介绍相关基本概念及国内外研究 现状的基础上，针对传统的容错路由算法进行了分析研究，并找出了传统路由模型、算法 的一些局限性。 在局部安全信息模型的基础上，针对超立方体网络基于局部安全信息模型的优良性 质，研究了当网络中包含的错误结点数和失效链路比较多时，源结点和目的结点之间的单 播和广播容错路由的问题。一方面，关于单播容错路由，由于局部安全信息模型在较多的 失效链路和故障结点的情况下，并不能保证可靠的容错路由。本文提出了一种结点树算法， 继续沿用局部安全信息中一些重要的思想，比如最大安全子立方体网络等。在信息单播路 由的情况下，信息沿着结点树传播，直到当前结点能和目的结点结点树中的结点包含在一 个最大安全子立方体中，从而可更加有效地利用局部安全信息的模型算法，实现更加可靠 的信息路由。在传播路由信息的时候，采取了必要的回退算法。另一方面，关于广播容错 路由，在信息广播的情况下，由于在最大安全子立方体网络中一些固有的缺陷，使得连通 网络中的可到达结点不能接收到信息，文中提出的方法一定程度上缓解了这些问题。 仿真表明，文章所提出的改进思想提高了网络中的信息路由成功率，改善了网络的可 靠性，并且路由信息也是尽可能的沿着最优路径传播，算法所需代价较小。 关键词：容错路由，超立方体网络，局部安全信息，最大安全子立方体，结点树 a b s t r a c t a b s t r a c t h y p e r c u b et o p o l o g yo f n e t w o r ki sac o m m o nm u l t i c o m p u t e r sn e t w o r k ，a n di th a sab r o a d a p p l i c a t i o no nt h ei n t e m e t , s om a n yr e s e a r c hf o c u so nt h ef a u l t - t o l e r a n tr o u t i n g w i t ht h e i n c r e a s i n gs i z e o fam u l t i - c o m p u t e r sn e t w o r k , f a u l tp o s s i b i l i t yo fn o d e sa n dn l e i rl i n k s i n c r e a s e t h i sp a p e ri n t r o d u c e ss o m eb a s i cc o n c e p t i o n s ，s o m er e l a t e dw o r k sa n dt h em a i n r e s e a r c hs i t u a t i o na th o m ea n da b r o a d , t h e nf i n dt h es h o r t c o m i n gi nt r a d i t i o n a lf a u l t - t o l e r a n t r o u t i n ga l g o r i t h mb ya n a l y z i n gt h et r a d i t i o n a la l g o r i t h m t h i sp a p e r sm a i n l yd e a l sw i mt h ef a u l t - t o l e r a n tt m i c a s ta n db r o a d c a s tr o u t i n g f o rt h es a k e o ft h eg o o dc h a r a c t e r so ft h em o d e lo f l o e a l s a f e t yi n f o r m a t i o n ，an e wr o u t i n ga l g o r i t h mb a s e do n l o c a l s a f e t yi n f o r m a t i o ni sp r o p o s e df o rf a u l t - t o l e r a n tr o u t i n gi nh y p e r c u b e s f i r s t ，a b o u tt h e u n i c a s tr o u t i n g ，af e a s i b l ep a t hf r o mt h es o u r c et ot h ed e s t i n a t i o nm a yb en o tg u a r a n t e e da tt h e s o u r c 冶b a s e do nl o c a l s a f e t yi n f o r m a t i o nw h e nt h es y s t e mc o n t a i n sal a r g en u m b e ro ff a u l t y n o d e sa n df a u l t yl i n k sa l t h o u g haf e a s i b l ep a t hi sa v a i l a b l e n o d e t r e ea l g o r i t h mi ss e t u pf o r f a u l t t o l e r a n tm u t i n g , w h e r et h em e s s a g ei sf o r w a r d e du n t i lam a x i m a ls a f es u b c u b ei sf o u n dt o c o n t a i nt h ec u r r e n tn o d ea n dt h en o d ei nn o d e t r e eo fd e s t i n a t i o nn o d e b a c k t r a c k i n gi sa d o p t e d i fn of e a s i b l ep a t hi sn e c e s s a r y s e c o n d ，a b o u tt h eb r o a d c a s tr o u t i n g ，t h i sp a p e rf i n ds o m ew e a k p o i n to fb r o a d c a s t i n gi nt h em a x i m a ls a f es u b c u b e sw h i c hm a k e st h en o d ei nac o n n e c t e d n e t w o r kc a n n o tr e c e i v ei n f o r m a t i o ne f f e c t i v e l y , a n dm a k es o m er e f i n e m e n tt ot h eb r o a d c a s t a l g o r i t h mt or e s o l v et h i si s s u e b ys i m u l a t i n gt h ep e r f o r m a n c eo fr e f i n e da l g o r i t h ma n do r i g i n a la l g o r i t h m ，i tc a nb e o b s e r v e dt h a tt h er e f i n e da l g o r i t h mi n c r e a s e st h es u c c e s sp o s s i b i l i t yo fu n i c a s ta n db r o a d c a s t r o u t i n g ，a n di t a l s od e m o n s t r a t et h a tt h er e f i n e da l g o r i t h mm a k e sag r e a tc o n t r i b u t i o nt ot h e f a u l t - t o l e r a n tc h a r a c t e ra n dt h er e l i a b i l i t yo ft h eh y p e r c u b es y s t e m k e y w o r d s ：f a u l t - t o l e r a n tr o u t i n g ，h y p e r c u b e s ，l o c a ls a f e t y , m a x i m a ls a f es u b c u b e s ，n o d e t r e e i l l ，： 南京邮电大学硕士研究生学位论文 目录 目录 摘要i a b s t r a c t j i i 第一章绪论1 1 1 网络可靠性概述1 1 2 研究背景介绍1 1 3 超立方体网络概述2 1 4 容错路由3 1 4 1 基础概念4 1 4 2 容错路由的方法4 1 5 超立方体网络结构的扩展5 1 5 1 基于结构特性的扩展5 1 5 1 基于应用特性的扩展7 第二章单播和广播的路由模型9 2 1 安全系数模型9 2 1 1 基于安全系数的路由模型9 2 1 2 基于安全系数的路由算法1 0 2 1 3 安全系数模型的局限性1 0 2 2 安全向量模型：1 0 2 1 1 基于安全向量的路由模型1 0 2 1 2 基于安全向量的路由算法1 1 2 1 3 基于安全向量模型的相关定理及其局限性1 2 2 3 广播路由算法1 3 2 3 1 包含最多矿1 个失效链路的网络中的广播策略1 3 2 3 2 包含最多2 刀- 3 个失效链路的网络中的广播策略1 4 2 3 3 包含最多俨1 个故障结点的网络中的广播策略1 4 2 4 本章小节1 5 第三章局部安全信息模型的单播路由1 6 l i i 南京邮电大学硕士研究生学位论文 目录 3 1 基于局部安全信息的路由模型1 6 3 1 1 基础知识1 6 3 1 2 局部安全信息? 1 8 3 1 3 局部安全信息模型下的最优路径1 8 3 1 4 局部安全信息模型下的最优路径算法2 0 3 2 基于局部安全信息的单播路由模型的改进2 3 3 2 1 局部安全信息模型的改进2 3 3 2 2 结点树信息的计算及改进算法2 5 3 2 3 仿真结果2 6 3 3 存在混合故障的局部安全信息模型2 7 3 3 1 存在混合故障的局部安全信息模型2 7 3 3 2 基于结点树的局部路由信息算法3 0 3 3 3 避免死锁3 1 3 3 4 仿真结果3 1 3 4 本章小节3 2 第四章基于局部安全信息模型的广播路由3 3 4 1 基础知识3 3 4 2 广播容错路由3 3 4 2 1 在磁贮内的广播容错路由3 4 4 2 1 在m s c 内改进的广播容错路由的改进算法3 6 4 2 3 基于局部安全信息的广播路由的改进算法3 8 4 2 4 仿真结果3 9 4 3 存在混合故障下的容错广播路由4 0 4 3 1 仿真结果4 1 第五章总结与展望4 3 5 1 本文完成的工作4 3 5 2 下一步研究的展望4 3 致谢4 4 参考文献4 5 i i i i ， 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 网络可靠性概述 第一章绪论 可靠性问题产生于2 0 世纪2 0 年代初。那时，人们对可靠性问题只是有个初步的认识。 第二次世界大战中，武器装备的不可靠问题，给交战国带来血的教训。武器装备可靠带来 的成功经验和其不可靠带来的失败，让人们逐渐加深了对可靠性问题的重视。因此，可靠 性问题是人们在社会实践过程中，伴随着客观形势的需要而产生的。它的诞生及发展是社 会发展的必然趋势，它与科学技术的发展，尤其是与电子技术的发展密不可分。经过半个 多世纪的发展，可靠性问题己发展成为一门涉及面十分广泛的综合性的新兴的交叉学科。 网络可靠性的相关概念是在2 0 世纪7 0 年代出现的，由于通讯技术，光纤技术，计算机 互联网络技术的迅猛发展，使得网络的功能日益增强，推动着计算机网络可靠性问题的研 究不断向纵深方向发展。随着社会信息化进程的加速，不仅计算机网络的用户在增加，而 且计算机网络的连接区域和网络连接规模也在急剧扩展。由于计算机网络广泛应用于企事 业单位、银行、交通、通信、工业、国防等重要领域，计算机网络的功能强大与否与其结 构的复杂性是成正比的。用户对计算机网络的依赖性越大，对计算机网络的要求也随之变 高，即：准确、迅速、安全、方便、可靠。计算机网络系统需要在数量众多的硬件和软件 支持下才能完成期望的功能，在特定的环境下，有时还需要人的参与。计算机网络系统一 旦发生故障，将会对经济、政治、文化、卫生、环境、社会产生极大影响和破坏，甚至危 及社会稳定及国家安全。由此，可以看出对计算机网络可靠性问题研究的重要性及紧迫性， 计算机网络可靠性的研究有着十分重要的理论意义和实用价值。【3 3 1 1 2 研究背景介绍 现代科技的高速发展，很多领域都需要大量的科学计算，随之而来的是对于多处理器 计算机以及分布式计算系统的更高要求。多计算机系统就是由若干自治多处理器单元通过 通信链路互连而成的集合。在处理单元之间，需要通过通信链路相互交换信息，信息从一 个处理器发出，经过中间若干个处理器单元通过通信链路互连而成的集合。在处理器单元 之间，需要通过通信链路相互交换信息，信息从一个处理器发出，经过若干个处理器到达 ， 南京邮电大学硕士研究生学位论文第一章绪论 目的地。这种系统通常被称为信息传递或点对点的互连网络。 在多计算机系统中，一个任务是分配给一组结点来共同完成的，所以任务的执行速度 不仅与处理器的速度有关而且也与系统通信速度有关。由消息从源结点传递到目的结点造 成的延迟影响着整个系统的性能。另外，由于处理机间的相互制约，通信延迟影响着系统 所支持的人物粒度。所以网络中的通信延迟是关系到系统性能的重要因素。通信延迟包括 启动延迟和网络延迟两部分。其中，启动延迟是在源结点与目的结点处理消息所用的时间， 它与处理器和路由器接口的设计有关；网络延迟是指消息在网络中传输所消耗的时间。网 络延迟不仅与互连网络的流控和交换技术有关，而且也与网络的拓扑结构和采用的路由算 法有关。而其中互连网络为多计算机系统中处理器单元之间的通信提供了一种有效的机 制，互连网络的拓扑结构决定着多计算机系统中处理器单元之间协同工作的性能。因此， 选择或设计一种高速可靠的多处理器互连拓扑结构对组建多计算机系统也是非常重要的。 在过去的十几年时间里已经建立了一些类似的系统，包括n c u b e 一2 ，h t e li p s c ，s g i o d i n2 0 0 0 等等。大部分都采用的是超立方体图或者星型图，超立方体及其变体是应用最 广泛的互连网络模型，实际上，对超立方体的研究最早是有m i c h i g e n 大学的两位学者从图 论的角度提出的。立方体之所以这样受到人们的青睐是因为它具有较理想的网络参数、高 度的正规性和结构的递归性。从网络结构特性看，超立方体介于最简单的环和最复杂的全 互连网络模型之间，而且它可以模拟多种互连网络结构，比如：线性列阵、环、网格、树 等等。 1 3 超立方体网络概述 超立方体结构的多处理系统在并行和分布式处理中具有良好的性能，可以在一定容错 能力下实现合适的消息传输。而有效的数据广播是多处理系统的一项重要性能。广播是指 一个信息从源结点出发传播到网络中所有其它正确结点的问题，一些方法如f o r b i d d e n f a u l 锣s e t 的思想和c l u s t e rf a u l tt o l 黝tm o d e l 以及肛s a f ef a u l tt o l 咖tm o d e l 等相继被提了 出来，但是这些路由算法基于容错模型的容错能力都比较小，如刀1 或一个结点错误或链 路错误等。 下面给出，l 维超立方体网络h n 的定义和h n 中的子立方体网络的定义以及图例。 定义1 1 靠维超立方体网络h n ，简称为玎c u b e ，是具有下述性质的一种网络拓扑结构：( 1 ) 2 ， 南京邮电大学硕士研究生学位论文第一章绪论 它由z 个结点和刀砂d 条边构成；( 2 ) 每个结点可由一个不相同的n 位二进制6 1 6 2 6 3 锄进 行编号；( 3 ) 结点编号的规则是，当且仅当h n 中两个结点的二进制串恰有一位不同时，两个 结点是相邻的，即这两个结点之间有一条边相连。两个结点s 和d 之间的海明距离，用月向矽 表示，是指s 和d 之间的不同位的数目。 定义1 2 刀维超立方体网络h n 中，设定源结点为s ，目的结点为d ，对j 的邻居结点s ， 如果n ( s ：砂媚囟，矽1 ，则将s 称为最优邻居结点；如果n ( s ：砂i 矽+ l ，则称s 为次优邻 居结点。如果一条s 与d 之间的可到达路径长度等于日向力，则称之为最优路径；如果路 径长度不等于矾力，则称之为次优路径。 o l o o o 0 0 0 图1 1 四维超立方体网络 如图1 1 所示为4 维立方体网络的图例，图中有1 6 个结点和3 2 条边，图中还标识了 结点的编号，可以看出4 维超立方体网络可看作由两个超立方体网络通过将对应结点用一 条边连接起来构成，以这种方式看待4 维超立方体网络时也很容易对各个结点进行编号。 一个n 维的超立方体网络具有2 一个结点，每个结点可以用一组二进制序列( 锄，a 硝， a n - 2 a 1 ) 表示，a i 0 ，1 ) 。子立方体s c 可以由栉位的序列( 锄c n 1 c 2c 1 ) ，其中c i o ，1 ，宰) ，奉 代表该位可以为0 也可以为1 。s c ( x , y ) 表示包含结点x 和y 的最小子立方体。s “表示超立 方体网络中结点s 沿j 方向的相邻结点。两个结点的二进制序列有且仅有一位不同时，称 它们为相邻结点。如果两个节点之间的传递消息路径的长度等于这两个结点的海明距离， 则称这条消息传递路径为最小可到达路径。 1 4 容错路由 为了研究的方便，传统上把分布式系统中的单个处理器抽象成图中的点，把连接线路 抽象成图中的边。因此研究此类型的系统结构就抽象成研究相应的图。对于很复杂的多计 3 南京邮电大学硕士研究生学位论文 第一章绪论 算机系统，容错( f a u l t - t o l e r a n c e ) 是一个很重要的指标，一个多计算机系统必须有一个容错 的标准。 1 4 1 基础概念 在设计或选择多计算机系统的互连网络拓扑结构时，其中一个需要考虑的基本因素就 是系统级容错。系统级容错中的系统级是指系统中发生故障的设备被局限在多处理器单元 之间的通信链路。当系统中出现故障设备，如果系统仍然能够正常工作，此时称系统具有 容错性。容错性的大小是在系统正常工作的前提下，由系统能够所允许出现故障设备的最 大个数来衡量的。 对于系统的”正常工作”，有两种定义。其中一种是：在隔离出系统的故障设备后，如 果在系统中含有一个确定的拓扑结构，则系统可正常工作。对于这种定义，在并行算法设 计和多处理器结构方面已经做了大量的工作。在这些算法中，确定拓扑结构的存在性是决 定算法性能的重要因素。因此，通过执行这些算法来判断系统中是否能够”正常工作”。系 统的容错性是利用系统的冗余性来重新组建系统而实现的。另一种定义是：如果在任意两 个非故障处理器之间存在非故障的通信链路，则称系统可正常工作，就是说如果剩余的非 故障设备是连通的，就可以认为系统可正常工作。这种容错模型特别适用于那些执行并行 程序的大型多计算机系统，系统允许在性能上有一定的降级但对系统互连拓扑结构的改变 不是很敏感。 1 4 2 容错路由的方法 国内外对多处理器系统互连网络拓扑结构容错路由的研究，已经有了很多年，也出现 了很多很有价值的成果。研究方法大致可以分成两类，一类是在互连网络拓扑结构上通过 添加额外的结点或者连接链路来完成容错。虽然可以达到容错的目的，但是这类方法会使 得投入的硬件成本增加，另外对于那些已经投入市场的并行机来讲，再去改变他们的拓扑 结构使其容错性能增强是不可行的。另一类是利用互连网络拓扑结构本身内在的大量结点 来容错，不需要添加额外的结点，且不会改变其自身的拓扑结构。在这类方法中根据路由 算法在传递消息时所使用的故障信息，又可以把他们分成基于局部故障信息、基于全局故 障信息和基于有限全局故障信息的三类容错路由算法。 基于全局故障消息的路由算法可以为每个消息找到最短通路，但这种方法最大困难是 4 南京邮电大学硕士研究生学位论文 第一章绪论 在各个结点上维护全局的故障信息。而且还要有一个基于全局故障信息的算法把故障信息 传递到每个结点。基于有限全局故障信息的路由算法，可以让每个结点记录与它距离为k 的所有结点和链路的状态，但是这种方法传递消息的延迟也可能会很大，因为消息有可能 被传递到那些到目的结点的最短通路都被故障部件所阻塞的结点，而记录所有这些信息所 需的空间开销也是非常大的。 基于局部故障信息的路由算法在为消息选择后继的邻接结点时，可以根据它的邻接结 点或者链路是否故障来选择，一般这种方法都允许消息回溯。因此，这种方法可以保证， 只要源结点和目的结点是连通的就可以把把消息传递到目的结点，所需要的内存开销也相 对较小。 我们对路由算法的有效性可以从以下几个方面来衡量： ( 1 ) 结点收集故障信息的复杂度； ( 2 ) 路由算法的复杂度； ( 3 ) 信息知道消息沿最优通路或者次最优通路传递的能力。 1 5 超立方体网络结构的扩展 超立方体网络拓扑结构是最早提出的网络拓扑结构之一，由于其正规性，对称性，强 容错性，直径短，可嵌入性，并行性，和网络通信能力的可扩展性等优点，深受研究者和 实践者的欢迎。但是，人们也发现，要设计和实现高维的超立方体网络以及对超立方体网 络进行扩展升级仍存在一些问题，因此一些研究者和实践者提出里多种超立方体网络的变 型。下面从两个只要的方向来介绍超立方体网络的变型或扩展：其一是在保留超立方体网 络特性的基础上，扩展结构的功能与特性，另一个是降低超立方体网络结构的部分特性， 使其与应用相适应【3 2 】。 1 5 1 基于结构特性的扩展 19 8 4 年b h u y a n 和a g r a w a l 提出了g h c 网络( g e n e r a l i z e dh y p e r c u b e ) 2 0 1 。g h c 网络可 以看作是超立方体网络的推广，它包含了r i n g ，h y p e r c u b e 和m e s h 等一大类拓扑结构， 其直径与度的乘积较小，并且具有较强的容错能力。 一些研究者基于分层的方法提出了几种超立方体网络的变型。1 9 9 3 年m e l k s e t i a n 和 c h e n 提出了c c c 网络( c u b e - c o l l i l e c t e dc y c l e s ) t 2 1 1 ，19 9 4 年m a l l u h i 和b a y o u m i 提出了h h c 5 南京邮电大学硕士研究生学位论文 第一章绪论 网络( h i e r a r c h i c a lh y p e r c u b e ) t 2 2 l ，19 9 5 年c h e n 和f a n g 提出了f h n 网络( f o l d e dh y p e r c u b e n e t w o r k ) 2 3 1 。这些基于分层方法的目的在于降低超立方体网络的结点度。同c c c 网络相比， h h c 网络的直径和平均网络结点距离比较小，但是它的网络结点度等于1 0 9 1 0 9 i v ，仍然与 网络结点数n 有关。c c c 网络的结点度等于常数3 ，其固定不变的结点度使得它在超大规 模集成电路设计和实现方面非常容易且有效。h c n 网络是以超立方体网络为基本单元，而 f h n 网络以环绕超立方体网络为基本单元。c c c 网络，h h c 网络以及h c n 网络都是两层 的分层互联网在网络规模需要扩展时必须破坏原有的网络结构以便加入新的结点，因此网 络规模的扩展仍然比较困难。2 0 0 1 年王洪玉和董秀国提出了一种应用于m p p 系统的节点 度等于常数的递归多级分层互连网络，称为全互连立方体网络( f u l l yc o n n e c t e dc u b i c n e t w o r k , f c c n ) 2 4 。f c c n 具有可扩展性好，延伸性能好等优点。f c c n 网络的结点度与 网络规模无关，为一常数4 ，且网络的直径和平均结点距离都与结点数的立方根成正比。 f c c n 网络具有很高的互联效率，而且f c c n 网络联结的并行系统在扩展时无需破坏原有 的任何物理联结，且没有增加结点度，使得f c c n 网络的扩展开销很少，适合与扩展到任 意多的结点度，可以在m p p 系统中得到应用。 1 9 5 5 年c u l l 和l a r s o n 提出了m o b i u s 立方体网络( m o b i u sc u b e s ) t 2 5 】。m o b i u s 立方体网 络是超立方体网络的变型，它具有一些比超立方体网络更优越的特性，如n 维m o b i u s 立 方体网络的直径大约是超立方体网络的一半，其期望距离大约是n 维超立方体网络的三分 之二等。1 9 9 8 年樊建席和逯昭义证明了m o b i u s 立方体网络的另一个比超立方体网络优越 的性质【2 6 1 ，即任一长度为l e n ( 4 = l e n = 2 ) ， 并给出了构造过程，从而也证明了m o b i u s 立方体网络对环网络的模拟能力比超立方体网 络的高。1 9 9 9 年樊建席和管殿柱将具有2 一个结点的m o b i u s 立方体网络的拓扑结构加以改 变，得到了包含任意多个结点的互联网络超级m o b i u s 立方体网络【27 1 ，并证明它保持了 m o b i u s 立方体网络的高连通度，对数级的直径和结点度数等优良性质，并且当结点个数 - z 憎叫时，o 一型超级m o b i u s 立方体网络是一个( 行+ 1 ) 一正则图；更进一步，由于它包 含任意个结点，所以其升级只需要增加任意个结点，从而克服了m o b i u s 立方体网络的升 级必须成倍增加结点个数的缺点。1 9 9 9 年樊建席还基于交叉立方体互联网提出了超级交叉 立方体互联网络的概念，并研究了其拓扑性质网和圈嵌入算澍2 9 1 。 1 9 9 6 年o h r i n g 和d a s 基于p e t e r s e n 图和超立方体网络提出了一种称为f o l d e dp e t e r s o n c u b en e t w o r k s 如】的超立方体网络的变型。这种拓扑结构具有正规性，结点和边对称性，最 6 南京邮电大学硕士研究生学位论文 第一章绪论 优连通性，对数级的直径，模块性，以及允许简单的自路i t l ( s e l f - r o u t i n g ) 和广播算法等优 点t 3 2 j 。 7 1 5 1 基于应用特性的扩展 超立方体结构最早的提出主要是解决并行计算机系统的体系结构，随着超立方体结构 研究的深入及其应用的需求，基于超立方体的广播、组播、单播研究进入到互联网络，然 而，超立方体结构的一个显著的特性是结点数n = 2 打的限制。1 9 9 8 年，v i r g i n i a 大学的j l i e b e h e r r 教授等在研究可靠组播时，为了克服反馈风暴( a c ki m p l o s i o n ) 以及树结构扩展 性差的缺陷，提出了非完全超立方体的组播拓扑结构【3 1 】，我们称之为l o g c u b e ，即允许结 构的结点数n = 2 n ，结点的联结数也可以不一样。文献【3 1 】的研究表明，l o g c u b e 具有很好 的结构可扩展性，支持大量结点的可靠组播应用。但由于l o g c u b e 中部分结点的联结数较 少，大大降低了整个结构的容错性。2 0 0 2 年，rf r i e d m a n 等人在研究稳定性检测协议时提 出了新的称为逻辑超立方体的结构，我们称之为f u l l c u b e 结构，即一方面允许可靠结构的 结点数刀 = s e q 2 指的是序列s e q l 中每个元素的值都大于等于 s e q 2 中相应的元素的值。 正常结点的安全系数是通过与相邻结点的安全系数信息交换而实现的，全部的错误结 点的安全系数都是0 ，而安全结点的安全系数为( 与超立方体网络的维数相同) 。 。根据安全系数的定义易知，每个结点的安全系数是唯一的；如果结点s 的安全系数为k ， 那么对于结点d ，如果h ( s ，矽毛则s 与d 之间总存在一条最优可到达路径；在维故障 超立方体网络内，如果故障结点少于，两个结点间至少有一条通路相连。 对一个给定的故障维超立方体网络q 刀，进行个轮回的赋值操作。在第一个轮回， 对所有的具有两个或者更多的故障邻居结点的正常结点，将其安全系数置为1 ；在第二个 轮回，在剩下的没有赋值的结点中，对具有三个或者以上的安全系数小于等于l 的正常结 点，将其安全系数置为2 ；依次类推，在第k 个轮回，在没有赋值的结点中，对具有斛1 个或者以上的安全系数小于等于后一1 的正常结点，将其安全系数置为k 。在最后一个轮回， 对所有的未赋值的正常结点，安全系数置为。在所有结点的安全系数都被计算后，每个 南京邮电大学硕士研究生学位论文第二章单播和广播的路由模型 结点维护两个序列表，分别保存最优邻居结点和次优邻居结点的安全系数【扪。， 2 1 2 基于安全系数的路由算法 设定从源结点s 发送信息m 到达目的结点d 。 算法u n i c a s l a t _ n o d e ( c u r , d ) * 路由算法 v = s o d ：宰。表示二进制序列的异或操作，v 代表s 与d 的导航序列木 h = h ( s ，d ) ；产表示s 与d 之间的海明距离木 i f ( s l ( s ) h ) l l ( 存在一个最优邻居结点s ，即h ( s ，d ) = h l ，使得s l ( s ) h 1 ) t h e n 执行最优路径单播算法： 发送信息m 给结点s ，v - s o d ，则总能找到一个s 与d 之间的最优路径； e l s ei f 存在一个次优邻居结点s ”，即h ( s ”，d ) = h + 1 ，使得s l ( s ”) h + l t h e n 执行次优路径算法： 发送信息m 到达s ”，v = s ”o d ，则总能找到一个s 与d 之间的次优路径； e l s e 寻找路由失败，退出。 2 1 3 安全系数模型的局限性 在一个维超立方体网络中，假设一个结点j 的安全系数是k ，则它仅仅可以说明， 对于结点d ，如果t t ( s ，由毛则j 与d 之间总存在一条最优可到达路径；但是当 h ( s ，力岛则不能说明s 与d 之间存在一条长度大于k 的可到达路径。 安全系数模型仅仅使用于只含有故障结点的超立方体网络，不适用于含有故障结 点和失效链路的复合故障超立方体网络。 2 2 安全向量模型 2 1 1 基于安全向量的路由模型 在一个维超立方体网络中，简称为n - c u b e ，安全向量模型可以更精确的解决n - c u b e 中失效链路和故障结点的分布信息，n - c u b e 中每个结点u 维护一个向量( “l ，, 2 , ，称 1 0 南京邮电大学硕士研究生学位论文第二章单播和广播的路由模型 之为安全向量s v ( u n 表示结点“到达与“海明距离为k 的通信能力) 。基于= 进制超立方体 网络的特性，安全向量的第k 位可由邻居结点的安全向量的第缸1 位决定。( 川哆屹哆，蛳 表示结点“第i 维的邻居结点的安去向量。安全向量【9 】的定义如下： 故障结点的安全向量为( o ，0 ，o ) 。如果结点“是失效链路的一个端点，则对” 来说，这条失效链路的另一个端点的安全向量将被视为( o ，0 ，o ) 。 初始化安全向量第一位： r0 ， 如果结点u 是失效链路的一个端点 旷 l1 ，其他情况 z 船2 0 如果球i 一。n - k l 王i j n 1 ，其他情况 2 1 2 基于安全向量的路由算法 算法由两部分构成：源结点的路由算法u n i c a s ta ts o u r c en o d e 和中继结点的路由算 法u n i c a s ta ti n t e r m e d i a t en o d e 函数u n i c a s ta ts o g r c en o d e b e g i n v = s o d ：奉。表示二进制序列的异或操作，v 代表s 与d 的导航序y u * h = h ( s ，d ) ；产表示s 与d 之间的海明距离奉 i f ( s v ( h ) 一1 ) i l ( 存在一个最优邻居结点s ，即h ( s ，d ) = h - - 1 ，使得s v ( h - - 1 ) - 一- 1 ) t h e n 执行最优路径单播算法： 发送消息和导航向量到源结点的第i 维的最优邻居结点s ( a pv ( i ) = 1 ) ，这个 结点满足h ( s ，d ) = h 一1 ；然后复位导航向量第i 位，令即v ( i ) = o ； e l s ei f 源结点存在一个第i 维的次优邻居结点s ”( 即v ( i ) - - o ) ，满足s v ( h + i ) - - i t h e n 执行次优路径算法： 发送消息到达结点s ”，职位导航向量v 第i 位，即v ( i ) = 1 j e l s e 失败退出 1 l 广l 南京邮电大学硕士研究生学位论文 第二章单播和广播的路由模型 e n d 函数u n i c a s ta ti n t e r m e d i a t en o d e b e g i n 广中继结点保存了当前信息和导航向量，设定当前结点为u i f 导航向量v 是零向量，则说明当前结点就是目的结点 t h e n 停止 e l s e 发送消息到达u 的一个最优邻居结点，满足s v ( h 一1 ) = 1 ； e n d 2 1 3 基于安全向量模型的相关定理及其局限性 定理一个力维的超立方体网络中，设定源结点和目的结点之间的海明距离为k ，如果 源结点的安全向量第k 位为1 ，或者源结点存在一个最优邻居结点，且该结点的安全安向 量的第后一l 位为1 ，则总可以找到源结点到目的结点的最优最短路径；如果源结点的一个 次优邻居结点满足其安全向量的第斛l 位为l ，则总可以找到源结点到目的结点的次优可 到达路径。 图2 1 含有失效链路的三维超立方体 如图2 1 所示，由安全向量的定义可得到该立方体网络中结点的安全向量，如表2 1 ： n o d e0 0 00 0 10 1 00 1 1 1 0 01 0 1 1 1 01 1 l s a f e t yv e c t o r【0 1 1 】【1 1 1 】【1 0 1 】 1 1 1 】【0 0 1 】 1 1 1 】【0 0 1 】【0 1 1 】 表2 1 图2 1 的安全向量表 1 2 南京邮电大学硕士研究生学位论文 第二章单播和广播的路由模型 对于图2 1 和表格2 1 ，如果源结点s 为1 1 0 ，目的结点d 为0 0 1 ，s o d = l l l 耶，力= 3 。 从图中我们可以清楚的看到有两条可到达路径1 1 0 - ) 0 1 0 - ) 0 1 1 - ) 0 0 1 ，1 1 0 - ) 0 1 0 - ) 0 0 0 - ) 0 0 1 ， 1 1 0 - ) 1 0 0 - ) 1 0 1 - ) 0 0 1 。但是根据安全向量的定义及其路由算法，s 攻l l o ) 【3 】- 1 ，需要找出 s 鲥l l o 【2 】= l 的邻接点( n e i ( 1 1 0 ，i ) 表示结点1 1 0 第f 维方向的邻居结点) ，我们可以从表中看 出s v , , e i 0 0 0 j ) 2 ：o ，s v 肥i ( o l o ) 【2 】- o ，所以找不到源结点s 到目的结点的可到达路径，因此这 也是安全向量的局限性。 2 3 广播路由算法 文献 1 5 1 中提出了一种算法可以实现在一个包含万1 个失效链路或者故障结点的超立 方体网络中的容错广播路由。文献 1 】中也推广到了网络中包含2 刀一3 个失效链路或者故障 结点的情形。文献【1 6 】中提到了一种e - c u b e 广播路由算法，工作原理如下：第一步源处理 器沿着第0 维发送消息，在第一步结束后，有两个处理器收到了消息；第二步这两个处理 器沿着第1 维发送消息，则这一步将有4 个处理器收到消息，同理类推；第拧步所有2 ” 个处理器将全部收到消息。 2 3 1 包含最多n - 1 个失效链路的网络中的广播策略 在e - c u b e 算法【1 6 】中，仅仅用到了2 一一l 条链路，而网络中链路总数为n 2 0 3 锨 1 5 1 的思想如下：令f 为n 维网络q n 中失效链路的集合。如果，为空，则可按照e c u b e 算法， 而当跏中存在失效链路的时候，在，l 一1 条失效链路的情况下，肯定有一维方向的链路是 正常的，设为p 维，即p 维方向不含失效链路。将跏沿p 维分成两个子网络g 1 和q n - i ， 如果在g 1 中可以实现消息的广播，则可以利用p 维无故障链路实现g 1 和q 肛1 之间的 消息互通，上述方法存在存在两种情形。 情形1 ：所有的失效链路都集中在一个子立方体网络中，设为q 小1 ，如果广播源点处于 g 1 中，则可以应用e - c u b e 算法实现g 1 中的广播路由，然后利用p 维无故障链路实现办1 和q 一1 之间的消息互通。如果广播源点处于q 刀1 中，则可以首先将广播源点传送给其 幺1 中的邻居结点代为广播，则仍然可以应用上述的算法。 情形2 ：每个子立方体网络中都含有失效链路，设广播源点在幺1 中，由于两个子网络都 含有失效链路，所以g 1 最多含有刀2 条失效链路。如果可以实现g 1 中的广播路由， 则q 一1 中的广播路由也就实现了。而g 1 这个( 以一1 ) c u b e 中最多