（计算机软件与理论专业论文）交换超立方体网络下的容错路由研究.pdf

广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明g 所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名： 莉般 2 卟年6 其蕊日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 囹即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：舔役导师签名：碧辔葶舢睥莎月陟日 交换超立方体网络下的容错路由研究 摘要 针对超立方体结构的多处理机系统出现故障的问题，本文对容错超立 方体网络的连通性进行了研究。通过对超立方体网络的局部连通性概念进 行分析，提高了超立方体网络的容错能力。根据超立方体网络局部连通性 的特点定义了相邻结点集合类的概念，提出并证明了求解两类相邻结点集 合的公式。给出了基于相邻结点集合类的满足任意子连通性条件的超立方 体网络自适应容错路由算法。该算法是分布式和基于局部信息的，可以预 防死锁。仿真实验的结果表明算法是高效的且构建的路径长度接近于最优 路径长度。 对于超立方体网络的大规模实现存在困难的问题，本文对一种新提出 的超立方体网络变体结构交换超立方体进行了研究。通过对交换超立 方体网络拓扑结构的特点进行分析，提出了交换子立方体的概念。基于此 概念对交换超立方体网络的局部连通性进行了研究，提高了交换超立方体 网络的容错能力。根据交换超立方体网络局部连通性的特点定义了相邻结 点集合类的概念，提出并证明了求解相邻结点集合的公式。给出了基于相 邻结点集合类的满足任意子连通性条件的交换超立方体网络自适应容错路 由算法，并给出了算法的步长上界。仿真实验的结果表明算法是有效的。 关键词：交换超立方体网络容错路由算法局部连通性 r e s e a r c ho nf a u l 月t o l e r a n tr o u t i n ga l g o i u t h m i nt h ee x c h a n g e dh y p e r c u b en e t w o r k s a b s t r a c t i no r d e rt od e a lw i t ht h ef a u l tp o s s i b i l i t yo fc o m p u t e r sa n dl i n k si n h y p e r c u b em u l t i c o m p u t e rs y s t e m ，c o n n e c t i v i t yo ff a u l tt o l e r a n th y p e r c u b e n e t w o r k si ss t u d i e di nt h i sp a p e r t h r o u g ht h ea n a l y s i so ft h ec o n c e p to fl o c a l c o n n e c t i v i t yo nh y p e r c u b en e t w o r k ，f a u l tt o l e r a n c eo fh y p e r c u b en e t w o r k si s i m p r o v e d t h ec o n c e p to ft h en e i g h b o rs e t so fp r e s e n tn o d eh a sb e e nd e f i n e di n a c c o r d a n c ew i t ht h ec h a r a c t e r i s t i c so fl o c a lc o n n e c t i v i t y t h ef o r m u l aw h i c h c o u l ds o l v et w ok i n d so fs e t so fn e i g h b o rn o d e si sp r o p o s e da n dp r o v e d a n a d a p t i v e f a u l tt o l e r a n t r o u t i n ga l g o r i t h m i s d e v e l o p e d f o r a r b i t r a r y s u b c u b e c o n n e c t e dh y p e r c u b en e t w o r k s t h i sa l g o r i t h mi sd i s t r i b u t e da n db a s e d o n1 0 c a li n f o r m a t i o n ，a n di tc o u l dp r e v e n td e a d l o c k s i m u l a t i o nr e s u l t ss h o wt h i s a l g o r i t h mi se f f i c i e n ta n dt h el e n g t ho ft h er o u t i n gp a t hc o n s t r u c t e db yt h i s a l g o r i t h mi sc l o s et ot h eo p t i m a ll e n g t h f o rt h ep r o b l e mo fl a r g e s c a l eh y p e r c u b en e t w o r ki st o od i f f i c u l tt ou t i l i z e ， an e wv a r i a t i o n ss t r u c t u r eo fn c u b e w e x c h a n g e dh y p e r c u b e ( e h ) h a sb e e n s t u d i e d t h r o u g ha n a l y s i st h et o p o l o g yc h a r a c t e r i s t i c so fe h ，t h ec o n c e p to f s u b - e x c h a n g e dh y p e r c u b ei sp r o p o s e d t h el o c a lc o n n e c t i v i t yo ne hn e t w o r k si s s t u d i e d f a u l tt o l e r a n c eo fe hn e t w o r k si si m p r o v e d t h ec o n c e p to ft h en e i g h b o r s e t so fp r e s e n tn o d eh a sb e e nd e f i n e di na c c o r d a n c ew i t ht h ec h a r a c t e r i s t i c so fl o c a l c o n n e c t i v i t y t h ef o r m u l aw h i c hc o u l ds o l v et h es e t so fn e i g h b o rn o d e si sp r o p o s e d a n dp r o v e d aa d a p t i v ef a u l tt o l e r a n tr o u t i n ga l g o r i t h mi s d e v e l o p e df o ra r b i t r a r y s u b c u b e - c o n n e c t e de hn e t w o r k s t h eu p p e rb o u n do ft h ea l g o r i t h ms t e pi sg i v e n t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f e c t i v e k e yw o r d s ：e x c h a n g e dh y p e r c u b e n e t w o r k ； f a u l tt o l e r a n t m u t i n g a l g o r i t h m ；l o c a lc o n n e c t i v i t y 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 课题的背景和意义。l 1 2 国内外进行的研究工作2 1 3 本文的主要研究内容6 1 4 本文的内容组织结构7 第二章超立方体网络容错模型。9 2 1 超立方体网络的基本概念9 2 2 交换超立方体网络的基本概念1 0 第三章基于n c u b e 子连通性的容错路由1 4 3 1 超立方体网络的连通性1 4 3 2 超立方体网络相邻结点集合类的提出1 6 3 3 基于相邻结点集合类的容错路由算法2 1 3 4 模拟实验结果与分析：2 2 第四章基于e h ( m ，n ) 子连通性的容错路由2 4 4 1 交换超立方体网络的比较分析2 4 4 2 交换超立方体网络子连通性的提出2 9 4 3 交换超立方体网络相邻结点集合类的提出3 2 4 4 基于相邻结点集合类的容错路由算法3 5 4 5 模拟实验结果与分析。3 8 第五章总结与展望4 0 参考文献4 l 致谢4 5 攻读学位期间发表的论文4 6 1 1 1 广西大掌硕士学位论文 交换超立方体用络- i t 的容错路由研究 第一章绪论 本章旨在对论文研究的课题和意义做一个简要的阐述，接着介绍了一些国内外的专 家学者们对此课题做的研究工作，然后对本文的主要研究内容进行了概述，最后是对文 章的总体组织结构的说明。 1 1 课题的背景和意义 随着人类的科技水平不断进步与发展，人们所遇到的新的科学与技术难题不论是在 问题的规模上还是在问题的复杂度上都有了一个质的飞跃，早期发明的计算机在求解这 类问题时已经显得力不从心了。人们急切的需要一种具有更高性能的，计算速度可以用百 万亿次甚至更高的单位来衡量的超级计算机，以此来解决诸如半导体模拟、污染分析、视 学科学、海洋环境、认知科学、核试验模拟、人类染色体、燃烧系统、气象模拟、流体 湍流分析这一类的极其复杂的计算问题。实现与解决这些难题的方法就在于规模并行处 理技术。如此一来，大规模并行机的研究开发工作成了当务之急。国家之间以机构和企 业为代表在高性能并行计算机这一领域展开了激烈的竞争，它的研究和发展水平也反映 了一个国家的科技发展水平和综合国力。 在近期公布的全球超级计算机五百强排行榜中，著名超级计算机厂商c r a y 制造的 位于美国橡树岭国家实验室计算科学中心的“美洲虎”( j a g u a r ) 以1 7 5 9 p f l o p s ( 每秒一千 万亿次浮点计算) 的速度获得第一。由我国自主生产的第一台千万亿次超级计算机“天 河一号”获得了排行榜第五的位置，而中国也因此成为了继美国之后在世界上第二个能 够研发千万亿次超级计算机的国家。它目前已被应用于进行大飞机的设计、模拟，石油 勘探等工作。 并行计算机是指由一组处理器单元通过相互之间的通信与协作，以并行处理的方式 以较快的速度完成大量的计算任务。因此，并行计算机的性能在很大程度上就取决于计 算节点和它们之间的通信与合作。而它们之间的通信就是建立在某种计算机互联网络拓 扑结构上的。采用何种网络拓扑结构，直接影响了节点之间的通信延迟，通信的可靠性， 通信算法的复杂度等等，从而影响并行计算机的系统性能。特别是现在的超级计算机采 用的处理器单元越来越多，某些单元发生故障的情况在所难免，如何在这种存在故障处 理器的情况下保证通信的可靠性，就需要采用一种具有较高容错性的网络拓扑结构。同 广西大掌硕士掌位论文交换超立方佛网络下的容错路由研究 时这种网络拓扑结构应该具有较强的可扩展能力和对不同应用的适应能力，在经济上也 应该是可行的。在此基础上还需要一个高效的容错路由算法，保证正确结点之间可以通 过较短的路径通信。目前国内外主流研究的计算机互联网路拓扑结构模型有 h y p e r c u b e ( 超立方体) ，s t a r ( 星型) ，m e s h ( 网格) ，t o m s ( 环绕) ，r i n g ( 环) ，t r e e ( 树) 等。 h y p e r c u b e ( 超立方体) 是其中一种较早提出的高性能并行计算机网络拓扑结构，这种结构 具有直径小、结构对称、哈密顿性、强容错性、网络路由算法简单等优点，一些简单的 拓扑结构可以很好的进行嵌入。 1 2 国内外进行的研究工作 目前一些商用的多计算机体系结构如s g f c r a yo d g h a 2 0 0 0 、n c u b e 1 0 、i n t e l i p s c 2e 2 7 1 、c m 2 t 2 9 1 都采用了超立方体网络拓扑结构来进行处理机之间的通信。本文也 仅针对超立方网络拓扑结构来进行说明和研究。 随着研究和实践的深入，人们发现超立方体网络拓扑结构虽然具有很多优点，但是 要设计制造高维的超立方体网络和对它进行结构的扩展都很困难。人们为了克服这些缺 点，设计出很多超立方体网络的变体。 文 9 中w j h s u 提出了一种f i b o n a c c ic u b e s 网络结构，这种变体和超立方体结构 不同，它是非对称的，而且边要比超立方体稀疏。它能够作为超立方体的子图进行嵌入， 它也能够作为其他一些结构的超图。从图一中我们可以看出这种结构虽然克服了超立方 体边数增长过快的问题，但是它的非对称性提高了可靠性分析和路由的难度，增加了不 确定因素。 f i g 1 - 1f i b o n a c c ic u b e s 文 1 0 中j w h 提出了改进的e x t e n d e df i b o n a c c ic u b e s 网络结构，弥补了以上的一 些缺点，但是超立方体的连通性被降低了很多。 2 广西大掌硕士掌位论文 交换超立方体网络下的容错路由研究 * ：鼍r 一，一，“ 印1 ；? ! ? 一j + t 摹一一 ；争；，：，二，：，一_ 鸶笪篙莨毽墓翼：譬露穗堕曼 一- t - t - 二二 一 ：二二：? ：， 。4 之o ：毪i 三二：芷二= j 一五矗三二i ；一：。 ：，? ：y ? 搴t 宅= 睁。 d 囊墓塑峨两逸耋囊莹 。：+ 。： ：，。一j ：。一： j - j ；赢j k 二； f i g 1 - 2e x t e n d e df i b o n a c c ic u b e s 文 8 】中w j h s u ，m j c h u n g ，和z h u 提出了一种g a u s s i a nh y p e r c u b e 网络结构，这 种结构可以通过改变参数的设置来改变网络的连通性强弱，从而让设计者在连接的开销 和路由效率之间做一个平衡。这样，设计者就可以在一个给定的连通性上选择一个合适 的拓扑结构。 f i g 1 - 3g a u s s i a nh y p e r c u b e ( g ( 6 6 ) ) 。 文 1 1 】中n f t z e n g 和s w e i 提出了一种e n h a n c e dh y p e r c u b e 网络结构，这种结构 的提出是基于这样一种考量：超立方体系统中的每个结点的边数都在制造时就固定了， 有些边可能未被使用，这些边可以被加在一对需要的结点上，缩短网络的半径，缓解容 易拥堵的结点。 0 1 0 0 1 0 l l l 1 0 1 f i g 1 - 4e n h a n c e dh y p e r c u b e ( k = 1 , k = 0 ) 文 1 2 】中s ( 2 z i a v r a s 提出了一种r e d u c e dh y p e r c u b e 网络结构，这种结构也是为了 在保持超立方体结点数不变的同时降低网络的连接复杂度与制造成本。它能够嵌入立方 体连接的环结构。但是它还有一些问题需要解决，比如处理器在网络中的分布，映射应 用的算法等。 3 广西大学硕士掌位论文交换超立方体网络下的容错路由研究 f i g 1 - 5r e d u c e dh y p e r c u b e ( r h ( k , 2 ) ) 文 1 7 1 中k e m a le f e 提出了一种c r o s s e dc u b e 网络结构，它的网络半径只有超立方 体网络的一半，而且它能够保证在任意一对结点间可以用一种简单的分布式路由算法找 到一条最优通路。它具有简单的递归结构，结构对称，高连通性等特点。但是这种结构 对其他网络的嵌入式应用不能很好的支持。 f i g 1 - 6c r o s s e dc u b e ( n = 3 ，4 ) 文 1 8 中y a h q i n gz h a n g 和y ip a n 提出了一种c r o s s e dc u b e 的变体，称为i n c o m p l e t e c r o s s e dh y p e r c u b e ，它是由两个互补的c r o s s e dc u b e 而成的。这种变体的思想和前面提到 的e n h a n c e dh y p e r c u b e 的一种变体“i n c o m p l e t ee n h a n c e dh y p e r c u b e ”有些类似，它们都 使得在结点数n 较大时，结点间的距离得以缩短，而且同时能保持原有网络的特性。 4 广西大掌硕士掌位论文交换超立方体网络下的容错路由研究 f i g 1 7i i l c o m p l e t ec r o s s e dh y p 盯c u b e ( c i ；) 此外还有在较早时候由文 1 9 1 提出的确s t e dc u b e 和文 2 0 1 提出的m o b i u sc u b e 这里 就不一一赘述了。这些超立方体网络的变体都是为了在保持超立方体网络原有优点的同 时尽量缩小缺点，寻求一种更优异的网络拓扑结构。 人们在改进网络拓扑结构以追求更高性能同时，也在网络的容错性分析方面取得了 很大的进展。传统的容错性度量方法有些只考虑结点出错时的网络容错性，有些只考虑 边出错时的网络容错性，有些则把它们综合起来考虑。实施上当边出错时我们可以把问 题等效为边两端的结点不能相互访问，也就是邻接点失效了。这种失效也分为无法传输 信号和传输错误的信号，暂时的失效和永久失效等。 在用这些容错性度量方法分析超立方体网络时我们发现，尽管超立方体网络结构具 有如此高的边复杂度，但是它的连通度却非常低。例如，超立方体网络h n 去掉任意k 个节点和相应边后要保持连通，必须有k n 一1 。这种特殊情况使超立方体网络的容错性 被极大的低估了。因为在实际应用中超立方体网络h n 的某个结点的所有n 个邻结点同 时失效的概率是极小的。所以传统的容错性度量方法不能完全显示出超立方网络的容错 性能。因此，人们试图引入更能有效度量网络实际能力的定义。文1 1 3 提出了f o r b i d d f i a u l t ys e t 概念的网络容错模型，该模型是指网络中的一些结点或边不可能同时出错以避 免上述情况的发生。作为这种模型的一种特殊情况，文 1 4 】提出了k s a f e 容错模型，即 每一个正确结点至少有k 个正确的邻结点。文【1 5 】提出了s u b c u b ep a r t i t i o n i n g ( 子立方体 划分) 的方法，利用该方法使人们可以从局部入手来研究超立方体网络的整体容错性。 文 1 6 提出了局部连通性的概念，满足此概念条件的超立方体网络可包含任意接近5 0 广西大掌硕士掌位论文交换超立方体网络- - g 的容错路由研究 的错误结点而仍保持正确结点的连通性。文【3 0 对文 1 6 1 的局部连通性的概念进行了 扩展，进一步提出了子连通性的概念，其目的是在满足概念条件的超立方体网络的故障 节点数任意大于整个立方体网络的节点总数的一半时，仍然能够保证整个立方体网络的 全局连通性。这一研究成果具有很高的研究价值，因为超立方体网络的很多变体都继承 和发展了超立方体网络的容错性，因此，我们可以把这一研究成果推广到超立方体网络 拓扑结构的变体中去。 在有了网络拓扑结构和容错模型之后，另一个要考虑的问题就是与之匹配的容错路 由算法了。可以说容错路由算法是建立在网络拓扑和容错模型之上的，一个好的算法可 以让它所依赖的模型更具有实际应用的价值。容错路由算法根据目的结点的不同可以分 为单播( u n i e a s t ) 、多播( m u l t i e a s t ) 、并行( p a r a l l e l ) 、广播( b r o a d c a s t ) 等几种。因为 根据拓扑结构和容错模型的不同容错路由算法的性能也会更着改变，本文将在后面的内 容说明应用在本文主要研究的网络拓扑结构之上的容错路由算法，所以这里就不再更多 的就容错路由算法进行阐述了。 下一个要研究的问题就是网络容错性和容错路由算法的容错性了，为了让网络模型 尽可能的反映网络的真实情况，人们需要一个网络错误的分布模型。这些错误可以分为 网络结点的错误和结点之间通信的边发生错误。目前常用的两种研究的方法是：在可以 确定错误结点或边发生错误的上界值时，以最大值的情况来考量，这种模型被称为界限 模型。在知道结点或边可能发生错误的概率时，那他们发生错误的情况应该是独立而且 是随机的，这种模型被称为概率模型。最后，把网络的错误分布模型应用到网络拓扑结 构上去，我们就可以分析出一个网络拓扑结构的连通性和在这个结构上应用的路由算法 的可行性。 1 3 本文的主要研究内容 本文的研究工作主要放在了超立方体网络的局部连通性的研究上。1 1 维的超立方体 网络具有2 ”个结点和n 2 ”1 条边，每个结点都具有n 一1 个邻结点。所以超立方体网络 的连通性可以说是相当高的，而且具有相当程度的冗余。可是，当某一个结点的n 1 条 边同时出现错误时，这个超立方体网络就变为不连通的了。因此，容许出现的错误结点 或边的数量仅仅是o ( n ) ，这与1 1 维超立方体网络的实际容错能力相差太大。因此本文选 用了一种更能反映出实际情况的网络容错模型局部连通性模型来进行研究。在这种 6 广西大掌硕士掌位论文 交换超立方体网络下的容错路由研究 模型下超立方体网络的容错能力可以得到很大的提高。通过分析超立方体网络的局部连 通性特点本文提出了一个相邻结点集合类的概念，利用相邻结点集合类我们可以很容易 的分析出一个超立方体网络的连通性特征，根据它我们可以进行很高效的路由。接着本 文提出并证明了求解两类相邻结点集合的公式。在求解出相邻结点集合类后我们就可以 把它作为一个路由的依据。其次本文给出了满足任意子连通性条件的超立方体网络的自 适应容错路由算法。算法是建立在网络局部结点的状态信息上的。考虑到可能发生死锁 的情况，加入了预防死锁发生的方法。仿真实验的结果表明算法是高效的且构建的路径 长度接近于最优路径长度。 接下来本文的研究工作转到了交换超立方体网络上。这是一种既继承了超立方体网 络的优点，又改进了超立方体网络的拓扑结构以降低超立方体网络的构造难度，提高网 络的性价比的超立方体网络变体。如前所述n 维的超立方体网络具有2 “个结点和n x2 ”1 条边，在n 的值较大时，也就是网络中的结点数很大时，过多的边数使得超立方体网络 的制造和扩展很困难，开销和性能提高的对比越来越大。交换超立方体具有非常灵活的 结构，可以根据需要很容易的在原有基础上进行扩展。此外它在和其他超立方体网络的 变体比较时也有自己独特的优势。本文对交换超立方体网络的局部连通性进行了研究， 分析了交换超立方体网络在减少了超立方体网络边数的情况下局部连通性的变化，从而 大大交换超立方体网络的容错能力。根据交换超立方体网络的特点分析了它的相邻结点 集合类和相关的计算公式。在此基础上提出了满足任意子连通性条件的交换超立方体网 络的自适应容错路由算法。算法在交换超立方体参数变化或进行结构扩展时都是自适应 的，且给出了算法的步长上界。 1 4 本文的内容组织结构 本文共分为五章。第一章是绪论部分，第二章到第四章是论文的主体内容，第五章 是论文的结论和结束语。 第一章主要是对论文内容的大致介绍。 第二章主要是说明一些超立方体网络容错模型和交换超立方体网络容错模型的相 关基本概念。 第三章是本文提出的超立方体网络模型的相邻结点邻接类的概念等，随后是基于超 立方体网络局部连通性和相邻结点邻接类设计的容错路由算法和算法的实验结果和分 广西大掌司e 士掌位论文 交换超立方体网络下的容错路由研究 析等。 第四章首先是对超立方体网络的一些几种变体结构进行的比较分析，随后是本文提 出的交换超立方体网络的局部连通性。然后是本文提出的交换超立方体网络的相邻结点 邻接类，最后是根据交换超立方体网络的局部连通性和相邻结点邻接类设计的容错路由 算法和算法的实验结果与分析。 第五章是结束部分，对论文的一个工作总结和结论，以及对论文工作的不足之处和 以后可进行的研究展望。 广西大学硕士掌位论文交换超立方体网络下的容错路由研究 第二章超立方体网络容错模型 本章主要是说明一些超立方体网络容错模型和交换超立方体网络容错模型的相关 基本概念，这是本文之后几章主要工作的理论基础。 2 1 超立方体网络的基本概念 超立方体网络是一种抽象的网络拓扑结构，是一个由表示结点的点和表示结点之间 传递信息关系的连线组成的无向图。 超立方体网络的无向图由一个有序的二元组( v e ) 组成，记作h n ，其中v 0 是 结点集合，e 是结点之间边的集合。 n 维超立方体网络h 。( n c u b e ) 的结点集v 由2 n 个结点组成，我们可以用不同的n 位二进制编号( x n 1 x n 2 x l x o ) 来表示不同的结点。边集e 由n * 2 小1 条边组成，每条边连 接着一对h n 的结点且这对结点仅有一位二进制位不等。 图2 1 是一个三维超立方体网络h 3 的图例，它总共具有2 3 个结点，结点的标号顺 序可以由维数来指定，这个指定可以是任意的，不同的指定也不会影响研究。它的3 * 2 3 j 条边按规则连接h n 的一对结点。 l 抛 0 1 1 妇l 图2 一l 三维超立方体网络 f i g 2 - 13 - d i n l e n s i o nh y p e r c u b en e t w o l l 【s 图2 2 是一个四维超立方体网络m 的图例，它总共具有2 4 个结点和4 宰2 4 d 条边， 也可以说是从两个三维超立方体网络连接相应的边扩展而成的。我们把三维超立方体网 络的图和四维超立方体网络的图作为对比可以看出，超立方体网络在扩展时，特别是当 n 很大的时候，就算要增加一个维度也使得相应需要增加的边数数量非常可观，这使得 h n 的应用受到了硬件制造成本和v l s i 制作难度的限制。而且结点数2 n 的限制也使得要 9 广西大掌硕士掌位论文交换超立方体网络下的容错路由研究 扩展h 。时一定要成倍的增长结点，失去了灵活性。在第三章论文将介绍种更具有灵 活性和降低了h 。边复杂度的h n 变体结构。 枷m瞳l 图2 2 四维超立方体网络 1 0 1 1 f i g 2 。24 - d l m e n s l 彻h y p e r c u b en e 咖o r i 路 从三维超立方体网络和四维超立方体网络的图作对比我们还可以看出超立方体具 有子立方体的性质。n 维超立方体网络h n 中的k 维子立方体网络h k 是由长度为n - k 的 二进制串( x n - k _ l x n 托x l x 0 ) 表示的。不难证明所有k 维子立方体都是同构的。我们不 妨设任意两个k 维子立方体v l 和v 2 ，再构造这样一种双射函数f v 1 一v 2 ，对于vv i ，v v l ，( v i ，v j ) e 1 ( e 1 ) ，通过改变维数指定使( f 【v i ) ，坟v j ) ) e 2 ( e 2 ) ，并且 ( v i ，v j ) ( ) 与( 坟v i ) ，坟v j ) ) ( ) 具有相同的重数，所以v l 和、，2 是同构的。 2 2 交换超立方体网络的基本概念 交换超立方体网络是一种抽象的网络拓扑结构，是一个由表示结点的点和表示结点 之间传递信息关系的连线组成的无向图。 交换超立方体网络的无向图由一个有序的二元组( v e ) 组成，记作e h ( m ，n ) = ( v e ) ( m l ，n 1 ) 。其中v a 是结点集合，v = a i l l 1 a o b n 1 b o cla i ，b i ，c o ，1 ) ，其中i 【0 , m ) j 0 ，n ) ) 。e 是结点之间边的集合，e = ( v i ，v j ) v vl ，v i 0v j = 1o r 1 0 广西大掌硕士掌位论文交换超立方体网爱 下的容错路由研究 v i m + n ：n + 1 = = v j m + n ：n + 1 】，h ( v i n ：1 ，v j 【n ：1 ) = 1 ，v i o - - - - - - v j o 2 1o r v i n ：1 】= v i n ：1 ，h ( v i m + n ：n + 1 ，v j m + n ：n + 1 ) = 1 ，v i o 飞 0 = o ) 在这里。表示异或运算符，v 【x ：y 】表示位于结点v 的x 维到y 维之间的比特串， h ( x ，y ) 表示结点x 和y 之间的汉明距离，其中( x ，y ) v v 。这意味着一个交换超立方 体具有两类边。其中一类边连接前m 位的汉明距离为1 的对结点，第二类边连接后i i 位的汉明距离为1 的一对结点。图3 1 是e h ( 1 ，2 ) 的拓扑结构图，其中粗实线代表了前一 类的边，细实线代表了第二类的边，虚线代表的是连接v i o v j = l 的边。 交换超立方体的两个参数调换位置后的结构是同构的，也就是说 e h ( m n ) 丝e h ( n ，m ) 证明：根据第二章的超立方体网络的子立方体结构的同构性证明，只要两个网 络能够通过重新给结点标号后相同，他们就是同构的。那么这里我们可以分为m - - b 和m n 的两种情况讨论。当m = n 时，让m = n = a ，显然有e h ( m ，n ) = e h ( n ，m ) = e h ( a ，a ) 。 当m e n 时，不妨设e h ( m ，n ) 中的结点u - a m 1 a o b n 1 b o cla i , b i ，c 0 ，1 ) ，其中i 【o , m ) g 【o ，n ) 。l = ( m + n ) ，可得u = x 1 1 x i m x l - n 1 x m n - m elx i ，c o ，1 ) ，其中i 0 ，1 ) ) 。我们可 以把它表示为等价的v = a m 1 ”a o b m 1 b o cia i , b i ，c 0 ，1 ) ，其中i o ，曲，j 【0 ，n ) ) 。根据 定义v 是e h ( m ，n ) 中的结点，因此，e h ( m ，n ) 丝e h ( n ，m ) 图2 3 交换超立方体网络( e h ( 1 ，2 ) ) f i g 2 - 3e x c h a n g e dh y p e r c u b en e t w o r k s ( e h ( 1 ，2 ) ) 定理2 1 交换超立方体网络e h ( m ，n ) 可以被分解为两个较小的网络e h ( m 1 ，n ) 或e h ( m n 1 ) 。 1 l 交换超立方体网络下的容错路由研究 证明：设有两个相同的相同的交换超立方体网络e h l ( m 1 ，n ) 和e h 2 ( m 1 ，n ) ，设u ，v 为e h l ( m 1 ，n ) 和e h 2 ( m 1 ，n ) 中的任意两个结点。于是有u = a m 2 a o b m 1 b o ci 毛，b i ，c o ，1 ) ，其中i 0 , m 一1 ) ，j 0 ，n ) ) ，、，= x m 2 x o y m 1 y o dix i ，y i ，d 0 ，1 ) ，其中i 0 , m 一1 ) ，j o ，n ) ) 。根据交换超立方体网络的定义可知e h i ( m 1 ，n ) 和e h 2 ( m 1 ，n ) 中的结点满足以下几 种相连方式：当u o v = l 时，有c , d = e o ，1 ) ，且c d 。当a i = x i 时，有o i ( m 2 ) ，h ( b n 卜l b o ，y m 1 y o ) - - 1 ，且c = d = l 。当b i = y i 时，有o j ( n - 1 ) ，h ( 1 a o ，x m 1 x o ) - - 1 ，且c - - d = 0 。 交换超立方体网络e h ( m ，n ) 在扩展网络结构时结点和边的扩展比例在m 或n 足够大 时都是趋近于1 的，因此它拥有比超立方体网络扩展时更好的性价比，下面给出证明。 证明：根据定义e h ( m ，n ) 具有2 ( m + n + 1 个结点和( m + n + 2 ) 2 ( m 蜘1 条边。我们用t 表示 需要扩展一个网络的规模并保持它的拓扑结构特性时所需要的最小网络元件( 结点和 边) 的数量，那么i e = a t t 就表示网络增量的比例。用i e n o d e 和i e i 诎分别表示结点和 边的增量。那么i e n o d e t n o d “o d c _ ( 2 m + n + 1 + 1 ) -2 m 坩1 ) ) 2 m + n + 1 ) = 1 ， i e l i n k = t l i n k 厂r h n k = 【( m + n + 3 ) 2 m + m - ( m + n + 2 ) 2 m + n - 1 ) ( m + n + 2 ) 2 肭- 1 k ( m + n “) 2 肭1 ) ( ( m + n + 2 ) 2 m + n 1 ) = ( m + n “) ( m + n + 2 ) ，当m 一+ 或n 一+ 时都有k o d e 一1 。根据定义，一个与交换超立 方体网络具有相同维数( m + n + 1 ) 的超立方体网络有( m + n + 1 ) 2 ( 咖条边。那么e h ( m ，n ) 的边数与h ( m + n + 1 ) 的边数比率r 芋( m + n + 2 ) 2 m + n 一) ( m + n + 1 ) 2 m + n ) - ( m + n + 2 ) ( 2 ( m + n + 1 ) ) = ( ( m + n + 1 ) + 1 ) ( 2 ( m + n + 1 ) ) = l 2 + 1 ( 2 ( m + n + 1 ) ) 。 从结论我们可以看出当1 1 1 或n o o 时，相同维数的交换超立方体网络的边数只有超 立方体网络的一半。而且如果m 和n 的值靠的越近，那么减少的边数就越多。在交换超 立方体中编号以o 为结尾的结点具有m + l 度，也就是有m + 1 个邻结点，而编号以1 为 结尾的结点具有n + 1 度，也就是有n + 1 个邻结点。而在超立方体中每个结点都具有m + n + 1 度，也就是有m + n “个邻结点。 在交换超立方体网络中路由要根据边的定义进行，如果源结点和目标结点的结点编 号是最左边的m 位不同，那么路由必须进行到以o 为编号结尾的结点，然后就可以在这 个结点的子图中继续路由。如果源结点和目标结点的结点编号是中间的n 位不同，那么 路由必须进行到以1 为编号结尾的结点，然后就可以在这个结点的子图中继续路由。如 果源结点和目标结点的结点编号是最左边的m 位不同，而目标结点和源结点都是以1 为结尾的，那么路由必须进行到以o 为编号结尾的结点，在子图中路由使源结点的编号 与目标结点的编号最左边的m 位匹配后再回到以1 为结尾的结点。如果源结点和目标结 点的结点编号是中间的n 位不同，而目标结点和源结点都是以0 为结尾的，那么路由必 1 2 广西大掌硕士掌位论文交换超立方体网络下的容错路由研究 须进行到以1 为编号结尾的结点，在子图中路由使源结点的编号与目标结点的编号中间 的n 位匹配后再回到以0 为结尾的结点。我们以在e h ( 2 ，2 ) 中的路由为例，假设要 从源结点0 0 0 0 0 路由到目标结点1 0 1 0 0 ，那么路由可以走p = 0 0 0 0 0 - * 1 0 0 0 0 一1 0 0 0 1 1 0 1 0 1 1 0 1 0 0 ，如果源结点改为0 0 0 0 1 ，目标结点改为1 0 1 0 1 ，那么路由可以走p = 0 0 0 0 1 一0 0 1 0 1 0 0 1 0 0 一l o l 0 0 1 0 1 0 1 由此我们假设交换超立方体网络的网络e h ( m ，n ) 的直径是m + n + 2 。 证明：不妨设e h ( m ，n ) 中的任意两个结点u ，v ，其中u = a m 2 a o b m - l b o cla i ，b i ，c o ，1 ) ，其中i 【o , m - 1 ) ，j 【0 ，n ) ) ，v = x m - 2 x o y m i y o dix i ，y i ，d 0 ，1 ) ，其中i 【o , m 1 ) ，j 【0 ，n ) ) 。用lu ，vi 表示从u 到v 的最短距离，当a m 2 a o ：g ：x m - 2 x o ，b m - l b o = y m 1 y o ，c - - d = l 时，根据定义和表3 1 我们有iu ，vi = h + 2 ，h 表示u ，v 之间的汉明距离。+ 2 是因为0 维被使用了2 次。而h m + n ，所以iu ，vi 最大不会超过m + n + 2 ，而在其他情 况下iu ，vl m + n + l 。综上所述，e h ( m ，n ) 的直径是m + n + 2 。 表2 - 1 交换超立方体网络的结点距离 t a b l e2 1n o d ed i s t a n c eo fe x c h a n g e dh y p e r c u b en e t w o r k s n 0 口- - a n = 口，一i 口。i b ，_ l 色，= b 一一b 。 c ，d l m m c e ly e s y e sm 、 、 h 2y e sn oo0叶2 3y e sn o0l 4y e sn o10h 5y e sn o11h 6 n oy e s0 o h 7n oy e s0i 8n oy 嚣l0h q n oy e s1l，一2 l o n o n 0 0 0加2 l l n on o 0 lh 1 2 n o n o l0 h 1 3 n o n 0i1 伊2 交换超立方体网络下的容错路由研究 第三章基于n - c u b e 子连通性的容错路由 本章对超立方体网络的局部连通性进行了研究，提出了超立方体网络相邻结点邻接 类，并给出了它的求解方法和证明。相邻结点邻接类充分反映了超立方体网络的局部连 通性