（运筹学与控制论专业论文）互联网络容错的组合研究.pdf

互联网络容错的组合研究 摘要 网络的拓扑结构是设计和制造集群计算机或超大规模并行计算机 系统的首要条件，也是实现各种协议的基础，它对网络的性能、系统 可靠性和费用都有直接的重大的影响 人们通常把互连网络中的处理器抽象成一个点，把连接处理器的 信道抽象成两点之间的连线，那么该网络的拓扑结构就被抽象成一个 图 研究网络拓扑结构问题就归结为研究图的结构问题网络的容错 研究可以转化成对图的参数研究互连网络主要有以下的评价指标： ( 1 ) 硬件复杂程度：可以用网络拓扑图的顶点度来衡量( 2 ) 通信开销： 可以用网络拓扑图的直径来、平均距离来衡量( 3 ) 可扩展性：就是一 个小网络要扩充为一个大网络，并保留小网络的结构性质的可能性， 它可以归结为图的可嵌入性问题( 4 ) 容错能力：可以用图的连通度以 及边连通度、网络的容错直径，宽直径等来衡量 目前讨论比较多的网络主要有网状网、树状网、超方体状网和星状 网类型网络本文主要考虑这些网络的网络性质，我们的工作如下： 首先，我们对这些主要的网络拓扑结构的容错指标，例如通信延 迟、容错直径与宽直径、连通性质进行了系统的总结在此基础上， 提出了互连网络拓扑容错方面一些值得进一步研究的问题 然后，本文对超立方体的子图一广义f i b o n a c c i 系列立方体进行 进一步研究对广义f i b o n a c c i 系列立方体的研究结果已有很多，包括 连通度、递归性，可嵌入环和格、直径等 本文研究广义f i b o n a c c i 系列立方体的容错直径，宽直径，证明了容 错直径，宽直径等于它的直径加1 关键词：广义f i b o n a c c i 系列立方体，容错直径，宽直径 i i 高校教师在职硕士学位论文 a b s t r a c t t h ef i r s tc o n d i t i o n si nt h ed e s i g n i n ga n di m p l e m e n t i n gl a r g es c a l ep a r a l l e l c o m p u t i n gs y s t e mi st oc o n s t r u c ti n t e r c o n n e c t i o nn e t w o r k st o p o l o g i c a ls t r u c t u r e i n t e r c o n n e c t i o nn e t w o r k si sa l s of o u n d a t i o no fi m p l e m e n t i n ga l lk i n d so fp r o t o c o l a n di tp l a y sa ni m p o r t a n tr o l ei nt h ep e r f o r m a n c e ，s y s t e md e p e n d a b i l i t y ，a n d c o s to ft h en e t w o r k s i n t e r c o n n e c t i o nn e t w o r k sa r eo f t e nm o d e l e da sag r a p hw i t h v e r t e xr e p r e s e n t i n gp r o c e s s o ra n da ne d g er e p r e s e n t i n gc o m m u n i c a t i o nc h a n n e l b e t w e e np r o c e s s o r s s ot h es t u d yo ft o p o l o g i c a ls 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 si st u r n e dt ot h es t u d ys t r u c t u r eo fg r a p h a n dt h es t u d yo ff a u l t - t o l e r a n t o fn e t w o r kc a nt r a n s f o r mt ot h es t u d yt h ep a r a m e t e ro fg r a p h 。t h ep a r a m e t e r s t oe v a l u a t et h ep e r f o r m a n 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 r ea sf o l l o w s ：( 1 ) h a r d - w a r ec o m p l e x i t y ：i tc a l lb ee v a l u a t e db yt h ed e g r e eo fv e r t e xo ft o p o l o g i c a lg r a p h ( 2 ) c o m m u i c a t i o ne x p e n s e s ：i tc a nb ee v a l u a t e dt h ed i a m e t e ro ra v e r a g ed i s t a n c e o ft o p o l o g i c a lg r a p h 。( 3 ) e x p a n d a b i l i t y ：i tc a nb ec o m ed o w nt ot h ep r o b l e m o fe m b e d a b i l i t yo fs o m es p e c i a ls t r u c t u r e s 。( 4 ) f a u l tt o l e r a n c e ：i tc a nb ee v a l u - a t e db yt h ec o n n e c t i v i t y ，e d g e - c o n n e c t i v i t y ，f a u l t - t o l e r a n td i a m e t e r ，w i d t h d i a m e t e r ，r e s 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 yo fg r a p h t h ew i d e l ys t u d i e dt o p o l o g i c a ls t r u c t u r ea r em e s h - c o n n e c t e dn e t w o r k s ，t r e e n e t w o r k s ，h y p e r c u b en e t w o r k sa n ds t a rn e t w o r k s w em a i n l yc o n s i d e rt h ef a u l t t o l e r a n tp r o p e r t i e so ft h e s en e t w o r k si nt h i st h e s i s 。o u rr e s e a r c hc o n c e n t r a t eo n t h ef o l l o w i n g ： f i r s t ，w es u r v e yt h ef a u l tt o l e r a n tp a r a m e t e r so ft o p o l o g i c a ls 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 ss u c ha 8c o m m u n i c a t i o nd e l a y ，f a u l t - t o l a r a n td i a m e t e r ， w i d t hd i a m a t e ra n dc o n n e c t i v i t y b a s e do nt h i s ，w ep r o p o s es o m ep r o b l e mt h a t w o r t hf u r t h e rs t u d y i n g 。t h e n ，w es t u d i e dt h es u b g r a p ho fh y p e r c u b e - t h es e r i e s o fe x t e n d e df i b o n a c c ic u b e t h es e r i e so fe x t e n d e df i b o n a c c ic u b ea r ew i d e l ys t u d i e d ，m a n yp a r a m e t e r s a r ed e t e r m i n e d ，i n c l u d i n gc o n n e c t i v i t y ，r e c u r s i o n 、e m b e dr i n ga n dm e s h ， d i a m e t e ra n ds oo n i nt h i st h e s i s 。w es t u d i 蕊t h ef a u l t - t o l e r a n td i a m e t e r ，w i d t hd i a m e t e ro ft h e s e r i e so fe x t e n d e df i b o n a c c ic u b e sa n dp r o v e dt h a tt h ef a u l tt o l e r a n td i a m e t e r w i d t hd i a m e t e ri se q u a lt od i a m e t e rp l u s1 。 互联网络容错的组合研究 i i i k e yw o r d s ：t h es e r i e so fe x t e n d e df i b o n a c c ic u b e ，f a u l t t o l e r a n td i a m - e t e r ，w i d t hd i a m e t e r 互联网络容错的组合研究 3 5 学位论文原创性声明与版权使用授权书 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果除文中已经注明引用的内容外，本论文 不含任何其他个人或集体已经发表或撰写过的作品成果对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完 全意识到本声明的法律结果由本人承担 学位论文作者签名：舅l 侈刃叼年，月岁口日。 d 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅本人授权湖南师范大学可以将本学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文 本学位论文属于 作者签名；知缈 导师签名：彩久 1 、保密o ，在年解密后适用本授权书 2 、不保密o ( 请在以上相应方框内打 ) 日期：矽刃年 日期：矽叼年 ，月岁d 日 f ，月；o 日 互联网络容错的组合研究 第一章网络容错研究现状 1 1 引言 随着各个领域对商陛能计算的要求越来越高，多处理机和多计算机 的规模越来越大，处理机之间或处理单元与存储模块之间的通信要求 和难度越来越突出因此互连网络是并行处理系统的核心组成部分， 它对整个计算机系统的性能价格比有着决定性的影响互连网络研究 主要集中在如下4 个方面： 一：定时方式，有同步和异步两种 二：交换方法，有线路交换( c i r c u i ts w i t c h i n g ) 和分组交换( p a c k e t s w i t c h i n g ) 两种 三：控制策略，有集中式和分散式两种 四：拓扑结构，有静态和动态两种 本文主要综述静态拓扑结构的容错研究现状，提出进一步研究的 问题 1 2 网络拓扑容错性衡量标准 网络的拓扑结构是设计和制造集群计算机或超大规模并行计算机 系统的第一步，也是实现各种协议的基础，它对网络的性能、系统可靠 性和费用都有重大影响互连网络的拓扑结构可以用一个图g = ( ve ) 来表示，每个处理器用图的一个顶点表示，处理器之间的通信信道用 一条边表示因此网络的容错性研究可以转化成对图的参数研究 互连网络主要有以下的评价指标【】： ( 1 ) 硬件复杂度：将挖个处理机按一定的拓扑结构连接成网络所 需的开关的个数可以用拓扑图的顶点度来衡量 ( 2 ) 通信开销：可以用网络拓扑图的直径和平均距离来度量【 ( 3 ) 可扩展性：简单说就是一个小网络要扩充为一个大网络，并 保留小网络的结构性质，它可以归结为图的可嵌入性问题 高校教师在职硕士学位论文 ( 4 ) 容错能力：对网络容错能力的研究即对网络可靠性的研究 传统的网络可靠性和有效性的参数有连通度和直径等 由于连通度和边连通度的研究需要假设网络拓扑中某一处理器的 所有相邻处理器或与此处理器相关信道同时失效，而在实际的情况中， 此种假设不能准确的反映容错网络的真实情况，因而连通度和边连通 度具有明显的缺点e s f a h a n i a n 和h a k i m i 推广了连通度和边连通度， 有兴趣的可以查看文件f 2 】我们主要有如下详细的的基本定义。 定义1 1 ：设g 是图，它可以是无向图，也可以是有向图设z ，y y ( g ) ，g 中其最小的( z ，y ) 路称为最短路( z ，y ) 路。从z 到y 的距离，记 为如( z ，y ) ，定义为最短路( z ，y ) 路的长度对于有向图站( 可，z ) 不一定 等于如( z ，y ) ，但无向图必有如( g ，z ) = d a ( z ，岁) 。约定如z ) = o 若g 中不存在( z ，可) 路，则规定d g ( x ，y ) = + o 。 定义d ( g ) = m a x d a ( z ，可) ：z ，y y ( g ) ) 为g 的直径 定义1 2 ：设g 是连通图，g 的平均距离定义为： 邸) 5 而1 磊撕t 同样，仅仅对网络的直径进行研究也不能真实的反映网络在具有 失效处理器下的网络延迟，因此出现了度量并行实时系统的有效性参 数一宽直径f 3 j ，度量容错网络的有效性的参数容错直径1 3 】具体定义 如下： 定义1 3 设g = ( ke ) 是一个无向或者强连通有向图，fcv ， 称为g 的点故障集z 和y 是g f 的两个顶点 从z 到y 的一1 ) 点容错距离，简称容错距离，记做珑( z ，可) ， 定义为： d 毛( z ，可) 2 陋m a ，i = 1 ，2 ，。，铃 两个顶点嚣= x l x 2 和y = 软珈在q 嚣 秸 中相邻当且仅当| z i y i l 1 1 = 1 超方体有很多变种，这里我船主要介绍给维交叉超方体、折叠超方 体、扎维立方连通圈、扭曲方体、分层方体、变种超方体，广义f i b o n a c c i 立方体。 m 维变种超方体可以这样递归地构造：v q ，是一个有两个顶点的 完全图，v q 。由两个相等的褥一1 维变种方体y 娥，和y 硪一，组成 两个顶点让= o u 行斗洲l v ( v q o 一1 ) 和顶点。= l v 4 川l v ( v q ：一1 ) 有 边相连当且仅当 1 如果钆3 k ，u n 廿珏1 一v n - 1 删1 或者 2 。如果挖= 3 k ， 钍。一3 铭l = t 一3 静l ， 且( u n l u n 一2 ，v n l 锄一2 ) ( ，o o ) ，( 0 1 ，0 1 ) ，1 0 ，1 1 ) ，( 1 1 ，l 舀) 。 藏联网络容错的组合研究 伽维交叉超方体可以这样递归地构造：c q ，是一个有两个顶点的 完全图，c q n 由两个相等的n l 维交叉方体c q o 一，和g q 羡一，组成 两个顼点锃= o _ 2 u o y ( e 砩一1 ) 和顶点杉= l v 船v o y ( g q ：一1 ) 有 边相连当且仅当 1 。当站是偶数时，一2 = 魄一2 并且 2 ( u 2 i + l u 2 t ，v 2 i + 1 锄) r ，0 i ，1 蜒i k + 1 最后一条路为 仳u 7 ，t k + 。 ，得证 ( 莲) 珏一露5 ，魏= 凳+ 6 时，类似可证 佗gk + 6 时，结果显然成立对于扎k + 7 ，假设对于任意的： 他， 高校教师在职硕士学位论文 e f c k ( 1 ) 中任何两个不同点存在嘲条不交路长度均小于z 1 现在我 们将钍，移用二进制表示为铭= u 竹一2 u n 一3 缸n 一4 。u l ? 2 d ，v = v n 一2 v n 一3 v n _ 4 一v l v o 令= f n - 3 1 。我镌将对e f c k ( n ) 作匿2 - 2 中的趔分，在后面的证瞬中， 我们将用到上述划分，后面的图中将不再标出划分后的子图名称 我们分三种情形讨论，在所有的情形中，对于j e t o l o ，0 0 0 ，0 0 1 ，1 0 0 ，l m ， 如果缸磁兢且珏在磁秘内有s 个邻点，则 缸t i l i s ) ，表示珏在 废尉内的邻点集合 域瓣 磴磁0 0 掣1 磁髓 图2 - 2te f c 蠢( n ) 的鲻分 互联网络容错的组合研究 u r 伦 + 上 j ： ! ： ： ： 爝 ： ： ： ： ! 秽 口， 取( 钆一2 )e k ( 礼一2 ) 图2 - 3 ：情形1 2 情形1 ：u n 2 = v n 一2 = 0 情形1 1l 一3 = v n 一3 = 1 由假设在e o z o 内部u ，u 中存在满足条件的k 7 条不交路，找u ，钉在 e o k 0 0 内的邻点u i , 钉，令t 为乱，秽7 在磁o o 中的最短路，则构造另外一条 路上+ 1 为t 正，u ，一兰- ，u ，且i l 膏，+ l l 礼一5 + 2 = 扎一3 情形1 2l 缸托一3 = 一3 = 0 由假设，在e f c k ( n 一1 ) 内，至少有f 丁n - 1 条不交路中的l z ，l 2 l k ， 满足条件令钆，u ，分别表示u ，秒在e f c k ( n 一2 ) 内的邻点，令t 表示让7 ，口7 在e f g ( n 一2 ) 内的最短路，则构造另外一条路l 。为u ，乱，三u ，口，长 度小于n 一2 ，见图2 - 3 情形1 3 ：乱n 一3 = 一 v n - 3 情形1 3 1lu n 一4 = v n 一4 高校教师在职硕士学位论文 图2 4 ；情形1 3 1 找u 在础内的邻点t t 0 0 0 ，则由假设在磁0 0 内u 0 0 0 和v 中存在k 7 条路最尼r ，满足长度小于礼一4 由于u 0 0 0 和“在磁0 0 和磁1 0 中的 构造完全相同，则对于磁0 0 中护0 0 的任一邻点u 严有e 2 加中u 的邻点 u t 与之对应，即仳；0 0 0 ，钍t 中分别有互不相交的边相连 令正= 只一 u 0 0 0 钆p ) ，1 i 令厶为u ，讹，仳严三钞，找秽，u o 在硪0 0 内的邻点口1 0 0 ，t t l 0 0 ，令丁表示? ) 1 0 0u 1 0 0 在磁0 0 内的最短路，则 构造另外一条路三肌1 为铭，u 0 0 0 ，u 1 0 0 三? ) 1 0 0 ，移，见图2 4 情形1 3 2l 钆。一4 = 一v n - 4 令u 0 0 0 ，v 0 0 0 表示钍，可在磁0 0 中的邻点，则由假设，在磁0 0 内u 唧，v 0 0 0 中有k 7 条路只，恳r ，且1 只i 他一4 ，由于u 0 0 0 在伊0 0 内的邻点可 能比”在磁毗内的邻点多一个，除此点之外u 的邻点和v 0 0 0 的邻点相 互对应且有互相不交的边相连 如果只，b r ，有某条路经过此点，不妨设为r ，如果没有，则 任取一条路为既令正= 只一 u 0 0 0 妒，v i o o o v o o o ) ，1 i k 7 1 ，构造乱 到口的路厶为饥，u t ，u 严l 口严，仇，u ，i l t i 他2 ，1 i 一1 ，令 t = p k ，一 乱0 0 0 u o , o o ) ，构造“为乱，让让垆三v 0 0 0 ，t j 互联网络容错的组合研究2 1 最后构造如+ 。，令 的邻点，且厶为让0 0 1 ，i ) 1 0 1 u 1 0 0 , u 1 0 1 分别表示乱0 0 0 ， 在e f c k ( n 一2 ) 中 在e f c a ( n 一2 ) 中的最短路，则令 u ，“0 0 0 ，u 1 上口1 0 1 ，口，i l ，+ 1 i 佗一1 见图2 - 5 情形2l 2 = 一2 = 1 图参5 ：情形1 3 2 同情形1 2 类似可证，见图2 - 6 情形3l 乱。2 = 一v n - 2 情形3 1 ：u n 一3 u n 一4 = 1 0 ，v n 一3 v n 一4 = 0 0 令u 0 0 0 ，口o 为让，” l 南，+ l 为 在磁0 0 中的邻点，则由假设u 0 0 0 和v 0 0 0 内有k ，条 不交路只，马r ，满足条件令 u ，u i ， 构造 正= 最一 u 0 0 0 “? 0 0 ，谚0 0 u 0 0 0 ， 咙0 0 0 三i 唾啪，仇，u ，i l t i n 一1 ，1 i 一1 ， 己南，为缸，“缸俨3 0 0 0 ，钌 令 构造厶为 t k ，= p k ，一 u 0 0 0 珏2 9 h d ) ， 最后构造三，令u 1 为乱o o o 在磁0 0 内的邻点，由假设秽，u 1 0 0 在娥0 0 内至少有k 条不交路满足长度小于n 一4 ，由于l ，l 2 工肚， 仅占用口在e 0 0 内k 7 1 个邻点，则e l o o 内至少有一条路t 满足 t n 厶= 乃，l i k 7 1 ，且i t l 礼一4 连接t ，u 1 0 0 构造己知，为 ，2 2 高校教师在职硕士学位论文 u ，乱咖，u 1 0 0 t 勘，i c k ，i 佗一2 ，见图2 7 乱， 让 j ： ! ： ! 穿 ： ! ： ! ! u ， 秽 图2 - 6 ：情形2 情形3 2 ：乱n - - 3 u n 一4 = 1 0 ，一3 v n 一4 = 0 1 找u 在磁0 0 内的邻点u 0 0 0 钉在磁0 1 内的邻点口0 0 1 以及秽0 0 1 在掣内 的邻点t ) 0 0 0 ，由假设u 0 0 0 ，v 0 0 0 中有k 7 条不交路最，是r ，满足1 只j 妃一4 同情形1 3 2 选择最，则令五= 只一 u 0 0 0 u 一。0 0 0 妒o u 0 0 0 】，构造厶为 钆，讹，u 2 0 0 三v o o o ，y o r e ，仇，钞，i l t l 竹一1 ，1 i 一1 令t k 一最，一( 乱0 0 0 钆垆) ，构造己知，为缸，铆，钍吵旦口0 0 0 ，y o o - ，t ， 最后构造三1 ，找u 0 0 0 ，u 在e 内的邻点u l o ov 1 0 0 ，且令? 为磁 内u 1 0 0 ，u 1 0 0之间的最短路，则构造l 1 为钍，u 0 0 0 ，u 1 0 0 三v l o o ，移，见图2 - 8 互联网络容错的组合研究 2 3 w r h 珏 卜 w 1 屋 j k j r舶0 0 ： w 。一 “。 压。 t j 、r ： 一再一上。蠢7 譬南， 忱 ： ，。 0 吣 u 图2 7 ：情形3 1 图2 - 8 ：情形3 2 2 4 高校教师在职硕士学位论文 情形3 3l u n - - 3 u n 一4 = 0 0 ，v n 一3 v n 一4 = 0 0 口在磁0 0 内的邻点为口咖，由假设u ，u 0 0 0 至少存在条路p 1 ，恳r ， 满足i p , i n 一4 令正= 只一 v o o o v o o o ，构造厶为钆3 陇0 0 0 ，仇，u ， i l l i 佗一1 ，1 i 内v 0 1 0 ，u 0 1 0 之间的 见图2 - 9 。v 0 0 0 ，u 在磁1 0 内的邻点为砂0 1 0 ，u 0 1 0 ，且t 为磁加 最短路，则构造l 1 为缸，u 0 1 0 三u o i o ，v 0 0 0 ，口 情形3 4 ：u n - 3 u n 一4 = 0 0 ，v n 一3 v n 一4 = 0 1 令v 在掣1 内的邻点为u 0 0 1 ，则在e f c k ( n 一1 ) 内由假设，让，v 0 0 1 至少 存在f 丁n - 1 条路中的p 1 ，马最，满足条件设口0 0 0 为u 0 0 1 在磁0 0 内的邻点 若p 1 ，b r ，中有某条路设为r ，经过v 0 0 0 ，不然任取一条路为最，令 正= 只一 陇0 0 1 u 0 0 1 】- ，构造l t 为让! 硼0 1 ，饿，口，i l t i n 一1 ，1 i k i _ 1 ， 则令l 奄，为t 正互可0 0 1 ， 最后构造l 。，则取u ， 在磁0 0 在磁0 0 内的最短路，则构造厶詹，+ 1 为 情形3 5 ：u n - 3 u 仃一4 = o l ，一3 一4 = 0 0 内的邻点u 1 0 0 ，v 1 0 0 ，t 为u 1 0 0 ，v 1 0 0 乱，u 1 0 0 三? ) 1 9 0 ，u ，见图2 - 1 0 令u 在磁0 1 内的邻点为u 1 0 1 ，则在e f c k ( n 一2 ) 内由假设， 至少存在f 丁n - 1 条路中的p 1 ，p 2 p k ，满足条件设乱1 0 0 为u 1 0 1 在 v u 1 0 1 硪0 0 内 的邻点若只，恳r ，中有某条路设为r 经过乱, 1 0 0 ，不然任取一条路为 令正= 只 l k 一1 ，贝0 一 u 1 0 1 钍1 0 1 ，构造l i 为u ，i ，u , t i 0 11 口，i l i i 佗一1 ，1 令l 知，为仳，缸1 0 1 卫u 最后构造l 。，则取钍，v 在酽 在磁0 0 内的最短路，则构造l - 为 内的邻点u 咖，口0 0 0 ，t 为钍咖，口咖 让，u 0 0 0 三v 0 0 0 ，口，见图2 1 1 置联网络容错的组合研究 2 5 u o i o 牡 - 俨 忱 矛 | r 一厶 v o i ov 0 0 0 十1 v 图2 - 9 ：情形3 3 警r u l o ( ? _ o 疗7 十i ! 上z 蠡i ? r 1 0 0 1 r v 0 0 0 耀0 11 忱 v 0 0 1 钉 图2 1 0 ：情形3 4 2 6 高校教师在职硕士学位论文 图2 1 1 ：情形3 5 图2 1 2 ：情形3 6 燕联网络容错的组合研究 情形3 6 ：一3 一4 = 0 1 ，一3 一4 0 1 令珏在互妒1 内的邻点为u 加1 ，由假设，静，u 0 0 1 至少存在f 孚1 条路 中的r ，岛最，_ l 满足| 蜀l 诧一5 ，则令五= 最一 铭i 髓u 埒1 ，构造勘为 u ，札，t 正i 1 0 l2 三+ ，i 厶l 佗一4 ，1 i k 一1 下面构造鼬聃l ，令u 1 0 1 ，移在砭内的邻点为髓瑚，v 瑚，构造 乞知，为札，u 1 0 1 ，t 1 0 0 三v 1 0 0 ，铷，t 为z k l 0 0 内u 1 0 0 ，v 1 0 0 之间的最短路 令移在磁毗内的邻点为v o o l ，嚣0 0 l ，珏在驴内的邻点为u 0 0 0 暂0 0 0 ， 则构造乞褂1 为珏，u 0 0 0 三v 0 0 0 ，v 0 0 1 秒，l 为霹内珏0 0 0 ，? 3 0 0 0 之间的最短 路见图2 1 2 证毕! 定理2 6 ：d 薹( e f c k ( n ) ) = d 奄( e f c k ( n ) ) = 铭一1 ，其中k = 曙 证明：由引理2 1 和引理2 2 以及定理1 1 知砧一1 d ( e f c k ( n ) ) d k ( e f c k ( n ) ) 露一1 ，结论成立 高校教师在职硕士学位论文 2 4 结论 研究结果表明，广义f i b o n a c c i 系列立方体在任意礼一1 个结点失灵 情况下，它的网络直径只比正常情况下的直径最多增加1 ，说明广义 f i b o n a c c i 系列立方体有着良好的网络容错性；其它的宽直径最多只比 直径大1 ，那么在并行计算系统的网络特别在实时系统中，其网络延 迟可以得到很好的控制通过综合分析可知，广义f i b o n a c c i 系列立方 体能适应构造互联网络平行计算系统中点的个数的变化，而且直径比 超立方体要小，容错直径和宽直径也比超立方体小，它还有着优良的 路由和广播算法和好的嵌入性，因此它的应用性要比超立方体强 互联鹅络容错棼缀合研究 结语 本文对互连网络容错性质的衡量标准以及几种特殊类型的网络拓 扑进行了综述，目前国际上对网络拓扑结构容错性分析的研究还不断 出现新的研究结果。从前面的几个表中可以看出，现有的许多网络拓 扑的参数还没有确定 在本文第二章中，我们对广义f i b o n a c c i 系列立方体的容错直径和 宽直径进行了研究，得出了它的容错直径和宽直径的傻。 广义f i b o n a c c i 系列立方体的容错直径只比它的直径增加了1 ，容 错直径的确定使得该网络拓扑结构的容错性有了一个好的衡量指标 宽直径的值也只比直径大1 ，宽直径的确立，使得该拓扑结构在并行 系统和实时系统应用上的网络传输延迟有了衡量指标，这些参数的确 定为广义f i b o n a c c i 系列立方体网络拓扑结构在实际的应用中提供了理 论上的支持 确定网络拓扑的参数是很有意义的研究课题目前国际上不断提 出新的网络拓扑和新的衡量网络性能方面的参数，提出更好的网络拓 扑模型和衡量标准是一个长期的研究譬标。这也是我们在今后的研究 工作要继续研究的方向和目标 3 0 湖南师范大学硕士学位论文 参考文献 x uj u n m i n g t o p o l o g i c a ls t r u c t u r ea n da n a l y s i so fi n t e r c o n n e c t i o n n e t w o r k sk l u w e ra c a - d e m i cp u b l i s h e r s ，2 0 0 1 e s f a h a n i a n ，a h ，h a k i m i ，s 1o nc o m p u t e ra c o n d i t i o n a le d g e - c o n n e c t i v i t yo fa g r a p h 。i n f o r m a t i o np r o c e s s i n gl e t t e r s ，1 9 8 8 ，2 7 ：1 9 5 - 1 9 9 d f h s u o nc o n t a i n e rw i d t ha n dl e n g t hi ng r a p h s g r o u p sa n dn e t w o r k s i e i c e t r a n s a c t i o no nf u n d a m e n t a l so fe l e c t r o n i c s ，c o m m u n i c a t i o n sa n dc o m p u t e rs c i e n c e ， 1 9 9 4 ，e 7 7 - a ：6 6 8 - 6 8 0 s c l i a w ，g j c h a n g ，f c a o ，d f h s u f a u l t - t o l e r r a n tr o u t i n gi nc i r c u l a n tn e t w o r k sa n d c y c l ep r e f i xn e t w o k s a n n a l so fc o m b i n a t o r i c e s1 9 9 8 ，2 ：1 6 5 1 7 2 s c l i a w g j c h a n g g e n e r a l i z e dd i a m e t e r sa n dr a b i nn u m b e r so fn e t w o r k s j o u r n a lo f c o m b i n a t o r i a lo p t i m i z a t i o n ，1 9 9 9 ，4 ：3 7 1 - 3 8 4 y s a n d ，m h s c h u l t z t o p l o l o g i c a lp r o p e r t i e so fh y p e r c u b e s i e e et r a mo nc o m p u t - e r 8 ，1 9 8 8 ，c - 3 7 ：8 6 7 - 8 7 2 y i s h i g a m i t h ew i d ed i a m e t e ro ft h e d i m e n s i o n a lt o r o i d a lm e s h n e t w o r k s ，1 9 9 6 ，2 7 ： 2 5 7 - 2 6 6 a e 1 - a m a w y ，s l a t i f i p r o p e r t i e sa n dp e r f o r m a n c eo ff o l d e dh y p e r c u h e s 。i e e et r a n s o np a r a l l e la n dd i s t r i b u t e ds y s t e m s ，1 9 9 1 ，2 ：3 1 4 2 c p c h a n g , j 。n w a n g t o p o l o g i c a lp r o p e r t i e so ft w i s t e dc u b e i n f o r m a t i o ns c i e n c e 1 9 9 9 ，1 1 3 ：1 4 7 - 1 6 7 【1 0 h o l e e ，j h h u r ，h c c h u n g ，h c c h o f a u l td i a m e t e ra n df a u l tt o l e r a n c eo f h c n ( n ，n ) i c p a d s2 0 0 1 ：3 4 6 - 3 5 4 【1 1 】c 。c h a n g ，t s u n g ，l h s u e d g ec o n g e s t i o na n dt o p o l o g i c a lp r o p e r t i e so fc r o s s e d c u b e s i e e et r a n so np a r a l l e la n dd i s t r i b u t e ds y s t e m s ，2 0 0 0 ，1 1 ：6 4 - 8 0 【1 2 1s y c h e n g ，j h c h u a n g v a r i e t a lh y p e r c u b e - an e w i u t e r c o n n e c t i o nn e t w o r kt o p o l o g y f o rl a r g es c a l em u l t i c o m p u t e r p r o c e e d i n g so fi n t e r n a t i o n a lc o n f e r e n c eo np a r a l l e la n d d i s t r i b u t e ds y s t e m s ，1 9 9 4 ，7 0 3 - 7 0 8 互联网络容错的组合研究3 1 - 【1 3 】胡湘勇几类互联网络性能的组合分析；硕士学位论文中国长沙湖南师范大学数 学与计算机科学学院，2 0 0 6 f 1 4 】m s ，k r i s h n a m o o r t h y ，b k r i s h n a m i r t h y f a u l td i a m e t e ro fi n t e r c o n n e c t i o nn e t w o r k s c o m p u t m a t h a p p l i c ，1 9 8 7 ，1 3 ：5 7 7 - 5 8 2 【1 5 】j i ew u e x t e n d e df i b o n a c c ic u b e s i e e et r a m ，1 9 9 7 ，8 ：1 2 - 1 5 【1 6 i s t o j m e n o v i c h o n e y c o m bn e t w o r k s ：t o p o l o g i c a lp r o p e r t i e sa n dc o m m u n i c a t i o na l g o - r i t h m s i e e et r a mo np a r a l l e la n dd i s t r i b u t e ds y s t e m s ，1 9 9 7 ，8 ：1 0 3 6 - 1 0 4 2 【1 7 s b a k e r s ，d h a r e l ，b k r i s h n a m u r t h y t h es t a rg r a p h ：a na t t r a c t i v ea l t e r n a t i v et o t h e - c u b e p r o c i n t 1c o n f o np a r a l l e lp r o c e s s i n g ，1 9 8 7 ，3 9 3 - 4 0 0 【1 8 】s l a t i f i o nt h ef a u l td i a m e t e ro ft h es t a rg r a p h ，i n f o r m a t i o np r o c e s s i n gl e t t e r s ， 1 9 9 3 ，4 6 ：1 4 3 - 1 5 0 【1 9 】m m a z e v e d o ，n b a g h e r z a d e h ，s l a t i f i f a u l td i a m e t e ro ft h es t a rc o n n e c t e dc y c l e s i n t e r c o n n e c t i o nn e t w o r k s p r o c e e d i n g so ft h e2 8 t hi n t e r n a t i o n a lc o n f e r e n c eo ns y s t e m s c i e n c e ，1 9 9 5 ，4 6 9 - 4 7 8 【2 0 】m i m a s e ，m i t o h ，k o k a d a f a u l t t o l e r a n tp r o c e s s ri n t e r c o n n e c t i o nn e t w o r k s s y s t e m s a n dc o m p u t e r si nj a p a n ，1 9 8 6 ，1 7 ：2 1 3 0 【2 1 】q l i ，d s o t t e a u ，j x u 2 - d i a m e t e ro fd eb r u i j ng r a p h s n e t w o r k s ，1 9 9 6 ，2 8 ：7 - 1 4 【2 2 j b o n da n dc p e y r a t d i a m e t e rv u l n e r a b i l i t yo fs o m el a r g ei n t e r c o n n e c t i o nn e t w o r k s c o n g r e s s u sn u m e r a n t i u m ，1 9 8 8 ，6 6 ：2 6 7 - 2 8 2 【2 3 】c b a l b u e n a ，p g a r c i a ，v a z q u e z