（应用数学专业论文）互连网络的容错性和可诊断性研究.pdf

摘要 本文建立了互连网络拓扑结构的超连通度( 超边连通度) 和限制可诊断数研 究的基本理论和方法，并且得到了几个著名的 呵络拓扑结构的超连通度f 超边连通 度1 和限制可诊断数以及折叠立方体网络的限制连通度和限制边连通度 连通度和边连通度是度量网络容错性的重要的确定性参数尽管对于含有少 量处理器的多处理器系统，这个参数可以比较恰当的衡量网络的容错性但是当 多处理器系统中处理器的数目很多时，这个参数在很大程度上低估了网络的容错 能力因此人们提出了许多别的刻画网络容错性的参数限制连通度，限制边连通 度，超级连通度以及舡超连通度都是一些更有效的参数 立方体网络是目前最著名、使用的最广泛、研究的最多较深刻的一种网络折 叠立方体( f 0 1 d e dh y p e r c u b e 8 ) 、交叉立方体( c r o s s e dc u b e s ) 、纽结立方体( t w i s t e d c u b e s l 、m i b i u s 立方体都是立方体网络中通过添加一些边或者改变某些边的连接 方式而得到的这些网络保留了立方体网络的递归结构和高连通性等好的特点而 直径只是相同规模的立方体网络的大约一半，因此被看作立方体网络的可能的很 好的替代者本文中的工作主要是关于这几个网络的容错性和可诊断性 我们得到了折叠立方体网络的限制连通度和限制边连通度和超级立方体的2 - 超连通度和2 一超边连通度通过建立了n + 1 维超级立方体和n 维折叠立方体的一个 同态映射，我们利用超级立方体网络的结果得到了折叠立方体网络的限制连通度 和限制边连通度这种研究方法对于利用立方体网络来研究折叠立方体网络的其 他一些性质以及路由算法必将有重要的作用 通过研究一个图类( 匹配图) ，我们得到了超级立方体，m 6 b i u s 立方体，交叉立 方体，纽结立方体的2 一超连通度和2 一超边连通度以前关于超连通度的工作主要是 关于一些围长比较大的图类，这些图类在实际应用中的作用还没有体现出来我们 研究了对于具体的著名的网络拓扑结构( 一般围长都比较小) 的2 一超连通度和2 一超 边连通度的研究而且所褥到的结果对于这些网络的容错性能有了很大的理论上 的提升我们的研究方法对于研究其他网络的性质也有重要的意义 网络的诊断数对于网络的设计和分析都有着非常重要的意义类比限制连 通度，我们在限制网络中非错误节点的邻点集不会全部出错的条件下，引入了限 制可诊断数的概念，并且通过匹配网络的限制可诊断数从而得到了超级立方体， m 6 b i u s 立方体，交叉立方体，纽结立方体的限制可诊断数我们得到对于一个n - 维的立方体、交叉立方体、纽结立方体和m 曲i u s 立方体，它们的限制可诊断数都 是4 n 一7 这几乎是它们的诊断数的四倍因此我们的研究结果有重要的理论意 义 a b s t r a c t i nt h i s d i s s e r t a t i o n ，w ee s t a b l i s ht h ef u n d a m e n t a lt h e o r ya n dm e t h o d st o s t u d yt h ee x t r a - c o n n e c t i v i t y ( e x t r a - e d g e - c o n n e c t i v i t y ) ，t h er e s t r i c t e dc o 皿e c t i v i t y ( r e s t r i c t e de d g e c o n n e c t i v i t y ) a n dt h er e s t r i c t e dd i a g o s a b i l i t yo ft o p 0 1 0 9 ys t r u c t u r eo fi n t e r c o n n e c t i o nn e t w o r k s c o n n e c t i v i t ya n de d g ec o n n e c t i v i t y 甜ei m p o r t a n tp 缸a m e t e r st om e 船l l r et h e f a l l l tt o i e r a c eo fi n t e r c o n n e c t i o nn e t w o r k s a 1 t h o u 曲c o n n e c t i v i t ya n d e d g ec o n n e c t i v i t yc 蛆c o r r e c t l yr e h e c tt h ef a u l tt 0 1 e r a n ta b i l i t yo fm u l t i p r o c e s s o rs y s t e m s w i 七hj u s tf e wp r o c e s s o r s i t g r e a t l yu n d e r e s t i m a t et h ef a u l t t o l e r a n ta b i l i t yo f l 缸g em u l t i p r o c e s s o rs y s t e m s s os o m en e wp a r 锄e t e r sa r ep r o p o s e d t h er e _ s t r i c t e dc o n n e c t i v i t y it h es u p e rc o n n e c t i 、r i t ya n dt h ee x t r ac o n n e c t i v i t ya r e 锄0 n g t h e m a st h em o s tf a m o u sa n dm o s t 丽d e l yu s e dn e t w o r k s ，t h eh y p e r c u b e sh a v e b e e ns t u d i e da1 0 ta n dm a n yo fi t sp r o p e r t i e sh a v eb e e na c q u i r e d t h ef o l d e d h y p e r c u b e s ，t h ec r o s s e dc u b e s ，t h et w i s t e dc u b e sa n dt h em 6 b i u sc u b e s 舡es e v - e r a lv a r i a t i o n so fh y p e r c u b e sb ya d d i n gs o m ee d g e so rr e p l a c i n gs o m e1 i n l 【si n h y p e r c u b e sw i t ho 廿l e rl i n k s a l 王t h e s en e t w o r k sr e s e r v e dt h er e c u r s i v es t r u c t u r e ， t h eh i g hc o n n e c t i v i t ya ds o m eo t h e rg o o dp r o p e r t i e so fh y p e r c u b e s ，a n df u r t h e 卜 m o r et h e ya l lh a v ead i a 肛l e t e ro fa b o u to l l l yh a l fo ft h ed i a m e t e ro fs i m i l a rs i z e h y p e r c u b e s h e n c et h e ya l lb er e g a r d e da sc a n d i d a t e st or e p l a c et h eh y p e r c u b e s t h e2 - e x t r a - c o n n e c t i v i t y ( 2 - e x t r a - e d g ec o n n e c t i v i t y ) o fh y p e r c u b e sa n dt h e r e 8 t r i c t e dc o n n e c t i v i t y ( r e s t r i c t e de d g ec o n n e c t i v i t y ) o ff 0 1 d e dh y p e r c u b e sa r ed e _ r l v e dl nt h i 8d l s s e r t a t l o nah o m o m o r p h i s mf r o man + 1 d i m e n s i o n 出h y p e r c u b e t oa 礼d i m e n s i o n a lf o l d e dh y p e r c u b e 8 盯ec o n 8 t r u c t e d t h r o u 曲t h i sh o m o m o r - p h i s m ，w ed e r i v et h er e s t r i c t e dc o n n e c t i v j t ya n dr e s t r i “e de d g ec o n n e c t i v i t yo f f o l d e dh y p e r c u b e sb yu s i n gt h er e s u l t so nh y p e r c u b e s t h i sm e t h o dm a yb e 璐e d v 1 v l 王 i nt h es t u d yo fo t h e rp r o p e r t i e so ft h ef o l d e dh y p e r c u b e s t h r o u g ht h es t u d yo fad a s so fm a t c h i n gg r a p h s ，w eo b t a i nt h e2 - e x t r a _ c o n n e c t i v i t ya n d2 一e x t r a r e d g e c o n n e c t i v i t yo fh y p e r c u b e s ，t w i s t e dc u b e s ，c r o s s e d c u b e sa n dm 6 b i u se u b e s p f e v i o u ss t u d yo fe x t r ac o n n e e t i v i t ya t em a i n l y 如o u t g r a p h 8o fl a r g eg i r t h a sw ek n o w ，o u rs t u d ya r eo fg r e a ts i g 工l i f i c a n c ea si tb e g i n s t h es t u d y w d l - k n o w ni n t e r c o n n e c t i o nn e t w o r k sw h o s e g i n hi ss m 出l b yr e s t r i c t i n gt h a ta ut h en e i g h b o r i n gv e r t i c e 8o fa n yn o - f a u l t yv e r t l c e 8c a n n o tf a i la tt h es a m et i m e ，w ei n t r o d u c et h er e s t r i c “dd i a g n o s a b i l i t 矿t h e na l s o t h r o l l g ht h es t u d yo fac l a s so fm a t c h i n gg r 印l l s ，w eo b t 缸nt h er e s t r i c t e dd i a g n o s a b i l i t yo fh y p e r c u b 豁，t w i s t e dc u b e s ，c r o s s e dc u b e sa n dm 6 b i u sc u b e s t h e r e s t r i c t e dd i a g n o s a b i l i t yi sa b o u t4t i i n e sa sl a r g ea 8t h e i rt r a d i t i o n a ld i a 髀o s a b i l - i 慨s o o u rs t u d y 缸eo fg r e a ts i g n m c a n c e 引言 由于多处理器系统比起大型的主机具有更高的性能价格比，在近年来多处理 器系统已经引起了很大的研究关注很多这方面的系统已经被实现多处理器系 统是由一些拥有自己的内存的处理器相互连接在一起而组成的处理器之间可以 通过相互传递消息来交互一个消息在到达它的目的地之前可能要经过许多个中 间的处理器这样的系统也被称作点对点或者消息传递网络一个多处理器系统 的底层拓扑可以用一个图g ( ke ) 来建模图g 的顶点集y 对应这些处理器的集合 而边集e 代表这些处理器之间的连线在设计一个多处理器系统时，首先要考虑的 一个方面是系统的容错性因为对于一个大型的多处理器系统来说，错误总是可 能会发生的 在一个大规模的多处理器系统中，某些元件或者通讯边的出错是无法避免的 当一个系统中有一些节点或者边出错的情况下，就需要采取某些措施来保证系统 的健康高效运行，这就在实际应用中提出了很多有待解决的问题一般的说，这类 问题的解决都是困难的，因为事先并不知道那些点或者那些边会出错尽管如此， 这些问题在最近十年引起了很多研究人员的兴趣，并且在这方面取得了一些漂亮 的成果我的这篇博士论文就做了一些这方面的工作 当有处理器或者连线出错的情况下由于多处理器系统的应用环境的区别，有 两个标准来判断系统是否仍然是有用的 第一个标准是考察容错系统中在逻辑上是否还包含着某种特定的拓扑结构 到目前为止，已经有了很多关于开发并行算法和找到最适宜这些并行算法的多处 理器系统的工作f 4 2 1 对于这些并行算法来说，这种特定的拓扑结构的存在对于算 法发挥期望的性能起着非常重要的作用当应用这个标准的时候，为了设计构建 这种容错性网络，最基本的方法是为每个节点提供备用节点并且使用诊断算法及 时发现错误并且在点或者边出错的情况下重新配置这个标准首先是由h a y e s 建立 的，随后引起了一系列这方面的工作 2 8 】【4 3 】【3 3 】 第二个标准，本文的研究在很大程度上是基于这个标准的只要任何两个没 l x 有发生错误的处理器之间还有不包含出错的处理器或者边的通讯链路、就认为这 个多处理器系统依旧是有用的 7 1 3 1 1 f 4 0 1 也就是说扣除错误节点或者边后的网络 仍然是连通的就认为这个多处理器系统是有用的在本文的以下部分，我们都是 采用的这个容错性标准 在基于第二个标准的时候，也就是考察网络是否仍然连通。这时候人们通常 用连通度和边连通度被用来刻画系统的容错性能例如，一个m 维立方体中最少需 要坏掉n 个节点才会使得整个系统变的不连通，但是只是在某种极端的情形下才 会出现坏掉n 个节点会使得系统不连通的情形在实际问题中，一个n 一维立方体 可以承受比这多得多的节点出错面系统仍然保持连通s ，l a t i 矗等人发现，唯一一 种可以去掉n 个节点从而使网络不连通的情形是这n 个节点都是网络中同一个点 的邻点然而，在一个像立方体这样的多处理器中，同一个节点的所有邻点同时 出错的可能性是很小的因此，人们开始寻找更加好的刻画网络容错性能的度量 参数e s f a h a n i a nf 1 9 1 于1 9 8 9 年提出了限制集的概念，在限制集中的节点或者边 是不会同时出错的，在将限制集定义为立方体中点的邻点集和邻边集的情况下定 义了限制连通度和限制边连通度，他们得到了立方体的限制连通度和限制边连通 度都是2 n 2 1 9 9 4 年，j f 轴r e g a 【3 9 】等提出了超连通度的概念并且研究了围长 较大的图的超连通度在本文中，我们研究了折叠超立方体网络的限制连通度和 限制边连通度和一类包含立方体，交叉( c r o s s e d ) 立方体，m 曲i u s 立方体，绞结立方 体f t w i s t e d ) 等著名拓扑结构的图类，通过研究这个图类的2 超连通度和2 一超边连 通度从而也就得到了这些著名网络的2 。超连通度和2 _ 超边连通度 要保持系统的高度可靠性和可用性，当系统中有一些节点或者边出错的时候， 定位出错的点或者边用备用的点或者边来代替它对于构建和维护整个系统来说都 是非常重要的在一个容错系统中，错误是可能出现的可是我们可以通过不让 错误节点产生的数据参与计算从而抵消错误产生的效果容错系统的构建可以通 过设计高度可靠性的系统部件和引入备用模块来实现，当一个模块出错的时候可 以用备用的模块来替换它，或者修复这个模块在一个容错性系统中，当错误模块 达到一定的数量之后，定位错误模块变的不再可能，因此对于这样的系统来说确 定系统可以在多少个节点出错的时候仍然可以定位出错误节点对于系统是很重要 中国科学技术大学博士学位论文 的这就是网络的可诊断数的研究这方面的研究是建立在局部信息的基础上( 如 网络中的节点可以知道自己相邻的节点是不是已经出错) ，考察网络中最多有多少 节点出错的情况下可以诊断出是哪些节点出错，从而可以用新的节点来取代这些 坏掉的节点，保持整个网络的性能在第四章我们通过限制非错误节点的所有的 邻点不会同时出错来推广了可诊断数的概念，在这种限制条件下提出的限制可诊 断数概念相对于传统的可诊断数可以更好的刻画系统的可诊断性我们在第四章 研究了一类匹配图的限制可诊断数并从而得到了立方体、交叉立方体、纽结立方 体、m 矾i u s 立方体的限制可诊断数 全文共分四章、包括了作者近期研究工作的主要内容，除了第一章为基础只是 外，其余部分全部是作者的研究成果 第一章是预备知识包括图论术语和一些著名的网络拓扑结构的介绍主要介 绍了基本的一些图论术语和一些著名的网络拓扑结构以及网络容错性和可诊断 性研究里面的些基本的知识 第二章立方体和折叠立方体网络的容错性研究在这一章里面，我们得到了立 方体网络的2 一超连通度和2 超边连通度并且建立了一个n + l 维立方体到n 维折叠 立方体的图同态利用这个图同态，我们利用立方体网络的结果得到了折叠立方 体网络的限制连通度和限制边连通度 第三章几种类立方体网络的容错性研究在这一章里，我们研究了一类匹配 图，得到了它的2 一超连通度和2 _ 超边连通度这一类匹配网络的重要性在于它包含 立方体，m 曲i u s 立方体，交叉立方体，纽结立方体等因而我们也就得到了这几种 著名的网络拓扑结构的2 一超连通度和2 一超边连通度 第四章几种类立方体网络的限制可诊断数的研究在这一章里，我们引入了 限制可诊断数的概念并且通过研究一类匹配网络的限制可诊断数得到了立方体， m 6 b i u s 立方体，交叉立方体，纽结立方体的限制可诊断数 第一章预备知识 我们现在正处于信息社会，信息社会的一大基础是电脑和网络在本文中研 究的网络并不是通常所指的i t e r e t 或者i n t r a n e t 而是多处理器系统的底层拓扑 结构随着微电子技术、超大规模集成电路技术的发展，现在已经可以建造大型的 多处理器系统多处理器系统比起同样性能的超级计算机来说在造价上有很大的 节省 我们所说的互连网络一些单元通过通讯信道( 包括有线的和无线的) 通过一 定的点对点的方式连接而构成的系统这些单元包括计算机子网络、计算机、计算 机内部的处理器、存储器、通信设备、其他元件和设备等这些单元之间的连接方 式是决定整个系统的性能和价格比的一个主要因素网路中单元和单元的连接方 式称为网络的拓扑结构设计网络的拓扑结构是大型多处理器系统的第一步，也 是实现各种协议的基础，他对网络的性能，系统的可靠性影响很大 在分析计算机互联网络时，人们通常把网络中的一个单元抽象成一个点把 通信信道看成连接这两个点的边，这样网络拓扑结构就可以用一个图来建模研 究网络拓扑结构的问题就归结为研究图的结构的问题因此我们可以通过图论的 方法来研究网络的拓扑结构，见4 8 】 1 1 图论术语的介绍 本节简单介绍图的基本概念和在以后的讨论中要用到的记号文中没有定义 的有关图的术语和记号可参见4 9 1 所谓图( g r a p h ) 是指有序三元组( vf ，咖) ，其中y 非空称为顶点集( v e r t e x - s e t ) e 称为边集( e d g e _ s e t ) ，而币是f 到y 中元素有序对或无序对簇y y 的函数，称为 关联函数( i n c i d e n tf u n c t i o n ) y 中元素称为顶点( v e r t e x ) ( 或点( p o i n t ) ) ，e 中 元素称为边( e d g e ) ，妒描述了边与点之间的关联关系若对每个( z ，) 妒( e ) 均 有( ，z ) 1 】f j ( e ) ( 这样的两条边成为对称边( s y m m e t r i ce d g e s ) ，) 则称图g 为无 1 2 中国科掌技术大学博士学位论文 向图( u n d i r e c t e dg r 印h ) ；否则就称为有向图( d i r e c t e dg r a p h 或d i g r 印h ) 显 然，无向图可以看成是特殊的有向图( 对称有向图) ， 用无序对z 来表示成对称边( z ，y ) 和( f ，z ) 有序对e = ( z ，) e 称为有 向边，z 称为边的起点，称为边e 的终点；而e = z 称为无向边；起点和终点统称为 边e 的端点边的两端点称为相邻的( a 枷a c e n t ) 两端点相同的边称为环( 1 0 0 p ) 无环的图称为简单图( s i m p kg r a p h 或d i g r a p h ) 设( ke ，妒) 是图，v 中元素的个数”和e 中元素的个数e ，即口= i y i 和e = i e l 分 别称为该图的顶点数或阶( o r d e r ) 和边数( s i z e ) 设g 是无向图，z 矿( g ) 的顶点度( v e r t e xd 8 口e e ) 定义为g 中与z 关联的边 的数目( 一条环要计算两次) ，记为d g ( z ) 顶点度为d 的顶点称为d 度点( 出d e g r e ev e r t e x ) 零度点称为孤立点( i s o l a t e d v e r t e x ) 用( g ) 和6 ( g ) 分别表示g 的最大( m “i m u m ) 和最小( m i n i h m m ) 顶点 度即 ( g ) = m ， d g ( z ) z v ( g ) ) ， d ( g ) = m i n d g 0 ) z y ( g ) ) 无向图g 称为正则的( k r e g u l a r ) ，如果对每个z y ( g ) 均有d g ( z ) = k 设d 是有向图p y ( d ) 的顶点出度( v e r t e x - d e g r e e ) 定义为d 中以为起点 的有向边的数目，记为d + ( f ) y ( d ) 的顶点入度( v e r t e x d e g r e e ) 定义为d 中 以口为终点的有向边的数目，记为d d ( g ) 图d ( 或g ) 中连接顶点。和且长度( 1 e n g t h ) 为的链( c l l a i n 或) w a l k ，记为珂链 是指顶点o ，和边n ，交错出现的序列 u ，= z 0 ( = z ) n ：l t 1 口砬n 礓z 瞳( = 掣) 其中与边n 。，相邻的两顶点一。和q ，正好是啦，的两个端点( 可能有z v 一。= ) 茹和称 为w 的端点( e n d - v e r t i c e s ) ，其余的顶点称为内部点( i n t e r n a lv e r 七i c e s ) 中边 1 2 网络设计的基本原则3 的数目称为v 矿的长度边互不相同的链成为迹( t r a i l ) 内部点互不相同的链称为 路( p a t h ) 两端点相同的链( 迹、路) 称为闭( c l o s e d ) 链( 迹、路) 设z ，v 若d ( 或g ) 中存在连接z 和f 的路，则称z 和! ，是连通的( c o n n e c t e d ) 若d ( 或g ) 中每对顶点都是连通的，则称d ( 或g ) 为连通图( c o n n e c t e dd i g r a p ho r g r a p h ) 反之为非连通图( d i s c o n n e c t e dg r a p h ) 若y 的子集y 使得g v 7 不连通，则y 7 称为g 的顶点割枷点割是指有个元 素的顶点割若g 至少有一对相异的不相邻顶点，则g 所具有的女顶点割中最小的， 称为g 的连通度，记为k ( g ) ；否则定义k ( g ) 为u 一1 若k ( g ) ，则称g 为连通的 两个图g 和日称为是同构的，记为g 掣日，如果存在一个双射口：y ( g ) 一 y ( 日) 使得z e ( g ) 一日( z ) 日( g ) e ( h ) 并称日为图g 和日的一个同构映射如 果g h ，则称口为图g 的一个自同构映射 图g 称为点对称的，如果对于任意的。，f y ( g ) ，均存在图g 的自同构日， 使口( z ) = ”图g 称为边对称的，如果对于任意的两条边e 1 = m r ，e 2 = z 9 e ( g ) ， 均有g 的一个自同构口使得口( u ) = z ，口( 口) = g 即将边e 1 映到边8 2 一个图g 是，一容错的，如果对于任意的fcy ( g ) ，l f i ，g f 仍是连 通的图g 的容错性被定义为最大的，使得g 是，容错的设图g 是正则的，如 果x ( g ) = ，就称g 是最大容错的 设mc 曰( g ) ，m 称为图g 的一个匹配，如果m 中任意两边在图g 中是不相邻 的图g 的匹配m 称为图g 的完美匹配，如果m 的端点集等于v ( g ) 1 2 网络设计的基本原则 互连网络拓扑的选择不但要考虑系统的性能，更要考虑系统的制造成本高 性能低成本始终是网络设计者所追求的目标下面我们列出衡量计算机互连网络 系统的高性能低成本的一些参数和设计这些网络时所遵循的原则，这些原则往往 是互相冲突的所以设计者需要在性能和造价之间找到一个满意的解因为网络 4 中国科学技术大学 尊士学位论文 拓扑结构可以用图来建模，下面我们用一些图论的术语来描述这些基本的设计原 则 4 9 1 1 、小的或者固定的度 即对应的图的顶点的最大度受到某个常数的限制顶点的度对应于单元的可 供使用的输入输出端口的数目每个单元的物理连接应受限于该单元的端口数目 小顶点度意味着少的物理连接，可以降低网络的构建成本 2 、小的通信传输延迟 网络中任何一个点的信息传递到另外一个点所费的时间要尽可能的少，即对 应的图应该具有较小的直径或者平均距离小的传输延迟不仅能降低网络的建造 和维护费用，而且能确保网络的有效性。 3 、简单的路由算法 路由选择是互连网络的最主要的功能之一路由选择的优劣深刻影响着网络 的性能和效率因而互连网络有好的，简单的，有效的路由算法对于网络的选择是 很重要的事情 4 、高对称性 人们希望网络中的各单元都以相同的方式启动和连接，使得各个节点的容量 和连线的负载保持均衡这就要求对应的图应具有某些对应性看是否是点对称 的，边对称的最好能是c a y l e y 图 5 、较高的容错性 网络应有一定的容错性，即容许网络中有若干数目的点或者边发生故障我 们要求，当故障节点或者连线的总数不超过某一固定的值时，剩余的网络的性能没 有大的退化 6 、可扩展性 设计出的网络要容易扩展，使得网络可以由较小的规模改造成较大规模的网 络，而仍然保持网络的拓扑结构， 1 3 本文主要研究的几个著名网络5 7 、可嵌入性 通常人们对已经存在的一些简单网络比较熟悉，并且已经掌握了在这些网络 上设计的一些算法所以当设计一个新的网络拓扑结构时，要求能够将一些简单 的网络嵌入到所设计的网络中 8 、有效的布图算法 布图设计涉及到图的可平面性问题如果这个图是平面图，布图设计实际上是 找出该平面图的实现方法如果该图不是平面图，则要么把该图分解成若干各子 平面图并找出该图的厚度；要么求出该图的交叉数布图问题是一个n p h a r d 问 题，但对于具体的互连网络来说，布图问题的有效算法是可能存在的 1 3 本文主要研究的几个著名网络 早期的互连网络主要是一些比较平凡的图，包括完全图、单环网、树等然而 每一种这样的简单的拓扑结构都有着比较大的缺陷以完全图为网络拓扑结构的 网络造价非常昂贵；单环网的信息传输延迟很大；而树的容错性能很差 二十世纪七八十年代，微电子技术和超大规模集成电路技术的发展使得建造 大规模的多处理器系统称为可能这时候应运而生了很多比较复杂的网络拓扑结 构其中比较著名的有d eb r u j i n 图【6 】【1 3 】、k a u t z 于1 9 6 9 年提出的k a u t z 网络【3 0 】、 网状网、金字塔网、蝶形网、移位交换网等等 但是目前使用的最广泛的，研究的较多较深刻的互连网络拓扑结构是超立方 体网络 1 3 1 超立方体网络 超立方体网络的拓扑结构是指n 维立方体，通常记为0 。它的图论模型是一个 简单无向图q 。= ( ve ) h ”a r y 2 q 已列出它的许多等价定义，最常见的是如下 两个 6 中国科学技术大学博士学位论文 1 o ，l 有序n 元数组( 亦称长为n 的2 元序列) v = z l z 2 z 。：z 。 o ，1 ) ，i = 1 ，2 ，n ) ， 两顶点z = z l z 2 。和v = 口l 妇在中相邻协墨1 恢一玑l = l ，即有 且仅有一个坐标不同 2 笛卡尔乘积 利用图的笛卡尔乘积，超立方体0 。按如下递归方法得到： 0 1 = 魁，骗= q 州xq 1 = 鲍，札2 2 图1 4 所示的是超立方体0 1 ，q 2 和q 3 o 0 l1 1 0 2 0 1 0 0 3 0 1 1 图1 1 ：超立方体q 。，如和饥 n 维立方体有下面一些性质 定理1 3 1 。j 、q 。有2 ”各项点，是n 正则的，有们“一1 条边 2 、0 。的直径是n ? 、0 。是二部分图 4 、一( 0 。) = ( q 。) = 6 ( 0 。) = ( q 。) = n 5 、q 。是点和边对称的 1 0 l 1 3 本文主要研究的几个著名网络7 1 3 2 折叠立方体 在文献【l7 中e 1 一a m a w y 和l a t i 矗提出n 维折叠立方体f q 。的概念它是通过 在n 维超立方体q 。中添加n 条边而得到的新的网络即y ( f q 。) = ( ( z ，z 。z 。) ： o ，1 ) ，任何顶点。= ( 0 1 0 2 n 。) 和顶点b = ( 6 1 6 2 6 忆) 相邻甘6 = ( b l b 2 k ) = ( 0 1 0 2 o “巩。) ，其中l 茎i n ( 此时称( n ，6 ) 为正常边) ；或b = ( 6 1 k k ) = ( 西，面，靠) = 孟，其中6 = 1 ，i = o ( 此时称( n ，6 ) 为补边) 在文献【17 中，e l - a m a w y 和s l 蚯6 等人研究了折叠立方体的性质。n 维折 叠立方体显然和n 维立方体具有相同数目的顶点数目，边数比n 维立方体多2 1 条 n 维折叠立方体的连通度是n 十1 ，直径是2 # 它具有和立方体网络类似的高对 称性结构、简单的路由算法而它的直径几乎是同样规模的立方体网络的一半，因 此折叠立方体网络被看作立方体网络的一个很好的替代者 1 3 3 交叉立方体网络 交叉立方体是e f e 于1 9 9 1 在文献 1 6 中提出 o 。4 图12 ：交叉立方体网络g q 3 和g q 4 具体定义如下：记a = ( 0 0 ，o o ) ，( 1 0 ，l o ) ，( o l ，1 1 ) ，( 1 l ，0 1 ) ) 若( z ，f ) a ，则记 8 中国科学技术大学博士学位论文 z n 维交叉立方体网络，记为g q 。，是指这样的一个图，它有顶点集 y = z ：z = 茁一z 2 2 1 ， o ，1 ) ，1 j n ) 两顶点z = z 她z 1 和口= 玑耽玑之间有边相连当且仅当存在一个j ( 1 茎js n ) 使得 ( 1 ) z 。j + l = 聊+ 1 ， ( 2 ) q 协， ( 3 ) 如果j 是偶数，那么有协一l = 一l ，并且 ( 4 ) 对每个t = 1 ，2 ，i ；l l ，均有z z 2 ，l 一z t 姚一， 图1 7 所示的是交叉立方体网络e q 3 和g q 4 交叉立方体作为立方体的一种变形，保留了立方体的高对称性等很好的性质 一个n 维的交叉立方体网络的连通度是n ，直径是【；j + 1 它同样有较为简单的路 由算法也被看作超立方体网络的一种很好的替代者 1 - 3 4 纽结立方体 n 维纽结立方体t q 。是通过改变m 维立方体中边的连接方式而得到的文献 1 ， 2 和文献【2 0 】提出的构造方法稍有不同在文献【1 ，2 】中提出的构造方法仅仅适用于 奇数维的丁一个联结顶点x ( = 。一1 z 。z z o ) 和y ( = 一1 玑仇一1 珈) 被称作跨越维数t 当且仅当墨雏对于维数的i 奇偶函数p 是这样定义的：只( x ) = 矾o z i l o o 。o ( 在这儿。是指异或运算) 对于一个奇数n = 2 + 1 ，o ，n 维纽结立方体t q 。的构造是从一个n 一维 立方体开始的在n 维立方体里面任取一个顶点x ( 一。一，z ；z z o ) 如 果尸2 ，2 ( x ) = o ( o sj 字) ，将x 的跨越维度2 j 一1 的邻边用下面的边替 换：巧卸一1 = 岳2 j 面2 j _ 1 ：当 2 j 或者巧一1 时执= q ( 虽然刚刚替换过来 的边跨越两个维度，跨越维度卸一1 的边还是要被保留) 当所有这样的边被替换 过之后，就得到了纽结立方体由文献【2 0 】提出的构造方法与上面的方法类似但是 1 3 本文主要研究的几个著名网络 9 仅仅适用与里面的一个2 一维的子立方体在这一节里，我们讨论的纽结立方体是根 据文献 1 ，2 提出的定义 t 也可以像如下这样的循环定义：r q ，是一个完全圈娲它的两个顶点标 为o 和1 令n 是一个奇数并且n 23 我们把r q 。的顶点集分解为四个子集：y ”、y ”、y ” 在这儿子集y 巧中的点由使得z 。一l i 并且。一2 一j 的所有这样的顶点z 组成对任 意一个巧 0 0 ，0 1 ，1 0 ，1 1 ) ，由顶点子集y 2 j 在t q 。中诱导出的子图是和t q 。一2 同 构的，我们用t q ”_ ，来表示这四个字纽结立方体之间的连边是下面这样的一些 边：使得r 一3 ( z ) = 0 的顶点z = z 。一1 z 。一2 茁1 z o 和顶点瓦一1 瓦一2 z 1 o 以 及i 。一1 。一2 z l z o 相邻；如果只一3 ( z ) = l 那么就和顶点z 。一l 瓦一2 z l z o 以及顶 点j k 1 z 。一2z l o o 相令b 1 3 5 m 曲i u s 立方体 n 一维m 6 b i u s 立方体m q 。，是由c u l l 和l a r s o n 最先提出的【1 1 】它的顶点集 与m 维立方体q 。的顶点集相同，顶点x = z - 。z z 。有n 个邻点咒( 1s is n ) ，每 一个五满足下列方程中的一个： 磁= 嚣1 2 2 - t 一1 夏+ 1 - t z n 如果。t 一1 = 0 z l z 2 。一l 夏夏+ 1 - j k 虫口果z i l = l 根据上面的定义，如果她一1 = 0 ，那么x 的邻点k 就只需要把按位去反就可 以得到了；如果z = 1 ，那么就需要按位去反所有的甄，o 。但是x 的邻点x 1 根据上面的定义是没有确定的，因为在这儿我们可以假设z o 等于0 或者等于l ，我 们假设的不同就得到了两个稍微有些不同的网络拓扑结构当我们假设z o = o 时 得到的拓扑结构称为一个o - m 6 b i u s 立方体；当我们假设。o = l 时得到的网络拓 扑结构就称为一个1 一m 6 b i u s 立方体我们用0 m q 。和1 - m q 。来表示它们 1 0 中国科学技术大学博士学位论文 1 4 互连网络的容错性的一些预备知识 连通度和边连通度是度量网络容错性的重要的确定性参数一个图是连通的 如果这个图中的任何两队顶点之间都有一条路相连一个图的连通度是可以去掉 的最少的使得这个图不连通的点的数目；一个图的边连通度是可以去掉的最少的 使得这个图不连通的边的数目连通度通常作为一个来衡量多处理器系统的容错 性的参数 尽管对于含有少量处理器的多处理器系统，这个参数可以比较恰当的衡量网 络的容错性但是当多处理器系统中处理器的数目很多时，这个参数在很大程度 上低估了网络的容错能力这是因为使得一个含有很多处理器的多处理器系统不 连通的事件发生的概率是很小的在很大程度上来说是不可能的因此连通度只是 衡量了最坏情况下网络的容错能力因而连通度和边连通度在刻画网络容错性方 面仍然有一些局限，为此一些新的刻画网络容错性能的参数被提出了 给定一个图g 和一个图的性质沪，h a r a r y 定义了 2 5 j 定义了条件连通度一( g ，泸) ( 条件边连通度a ( g ，9 ) ) 为可以去掉的使得图g 不连通并且每个连通分支具有性 质汐的最少的点( 边1 的数目 另外一个相关的工作是由e s f a h a n i a n 等人引入的f 1 8 在| 1 8 中，作者们推广了 边连通度的概念，限制非连通分支必须满足某些性质由此他们引入了限制连通 度的概念接着在f 1 9 1 中，通过引入禁止错误集，他们研究了超立方体网络的限制 连通度一个错误集不能包含一个禁止集图g 的g d 限制连通度是这样定义的 定义1 4 1 设g = g ( ue ) ，身是顶点集y 的一些子集的集合，则图g 的易点连通 度是最小的顶点子集f 的秩，g f 是不连通的并且f 劈 类似的通过将劈定义为边子集的集合，f 定义为边子集就可以定义一个图的曰一 限制边连通度 e s f a h a n i a n 等人通过分别将劈定义为j 致= x y i 坳kr ( 口) 茌x ) ；g 既= xce l 地ke ( u ) 篮x ) 其中r ( 口) 和e ( ) 分别为顶点”的邻点集和邻边集 这样他们就定义图g 的限制连通度和限制边连通度为k 。( g ) = k ( g ，g 霸) ， ( g ) = 1 4 互连网络的容错性的一些预备知识 l l a ( g ，g 易) 并且得到了当n 3 的时候，超立方体的限制连通度和限制边连通度都 是2 n 一2 在 3 5 】中，l a t i 6 等人对于正则图推广了上面的限制连通度和限制边连通度的 概念下面介绍一下他们的工作： 定义1 4 2 设g ( ke ) 是一个 正则的图，o 9 l f e 口na ( ) 是顶点u 的邻点集定义 羁扣) = 矿c a 扣) ，i u | n 一9 ) 一个点集s 是禁止错误集当且仅当sc 峨( ”) 接着可以定义允许错误集的集 合 g = y cy i 任取一个顶点u 任意的一个集合ac 羁( ) ，a 仁y 定义1 4 3 设g ( ve ) 是一个正则图，9 是一个正整数则g 的g 点连通度可以定 义为：k ( ，( g ) = k ( g i f ：) 就是使得g f 不连通的最小的舅；中的点集f 的秩 类似的，只要把点用边来代替就可以定义正则图g ( ve ) 的g 一边连通度 对于n 一为立方体q 。，l a t i 6 等人得到了下面的结果 35 ： 引理1 4 4 设n 3 ，1 g l 号j 则托( 鲫( q 。) = ( 礼一g ) 2 9 超连通度是另一个比连通度更强的度量网络容错性的确定性参数，它是由b o e s c h 和t i n d e l l 引入的【7 】关于超连通度过去几年中做了人们做了很多的工作 4 】【8 【2 l 】【3 7 4 6 一个连通图被称为最大连通的，如果它的连通度等于它的最小的点度 同样的，一个连通图被称为最大边连通度如果它的边连通度等于它的最小的点度 个最大连通的图称为超连通的如果它的每一个最小的点割都是某一个顶点的邻 点集；一个最大边连通的图称为超边连通的如果它的每一个最小的边