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

摘要 在设计和选择一个互连网络的拓扑结构时，可靠性是评估网络性能的重要概 念高可靠性的互连网络一直是网络设计者追求的重要目标之一我们从网络的 拓扑结构上考虑硬件故障对网络可靠性的影响，即在网络结点和( 或) 连线可能发 生故障的情况下的数据传输的可靠性在这种意义下，我们所说的网络容错性是 指该网络能容忍多少组件和( 或) 连线同时发生故障，剩余的子网络中仍然含有某 些特殊结构并仍能正常工作故考虑网络的容错性具有实际意义 本文主要研究几个著名网络的宽直径和容错泛圈性全文共分四章 第一章介绍了本文用到的一些图和网络的基本概念，网络容错性问题的研究 背景和意义，以及几个著名的网络的定义 第二章研究了几个互连网络的宽直径运用归纳和构造相结合的方法研究了 局部纽立方体嘲络l t q 。( n 芝2 ) 和m s b i u s 立方体网络的宽直径，得到了以f 结果： l t q 。的宽直径d 2 = 3 ，d 3 = d 4 = 4 ，勘s 旦乒1 + 2 ( n 5 ) 当n 是奇数且7 时，此 上界是可达的对任意两个顶点z ，y ，存在n 条内点不交的( z ，) 路，路民至多d 州且 其中所有点的最末位均相同的路长至多旦丝2 第三章研究了增广立方体网络的容错泛圈性，得到了以下的结果：当n 4 时， 增广立方体a q 。是f 2 n 一3 ) 容错泛圈的 在第四章中，我们对本文的工作进行了总结，并且提出了儿个有待进一步研究 的问题 a b s t r a c t w h e nd e s i g na n ds e l e c ta t o p o l o g i c a l s t r u c t u r ef o ra ni n t e r c o n n e c t i o nn e t w o r k ， r e l i a b i l i t yi sas i g n i f i c a n tc o n c e p tf o re v a l u a t i n gt h ep e r f o r m a n c eo fn e t w o r k h i g h r e l i a b i l i t yi sa l w a y so n eo ft h ei m p o r t a n tg o a l sp u r s u e db yn e t w o r kd e s i g n e r s w 色 c o n s i d e rt h ee f f e c to nr e f i a b i f i t yc a u s e db yh a r d - w a r ef a i l u r e sf r o mt h et o p o l o g i c a l s t r u c t u r eo fn e t w o r k ，t h a ti s ，t h er e l i a b i l i t yo fd a t at r a n s m i s s i o nw h e nt h e r ea r e f a u l t yv e r t i c e so r a n de d g e s u n d e rt h i sc o n c e p t ，t h et e r m s ”f a u l tt o l e r a n c e m e a n sw h e nh o wm a n yf a i l u r e se x i s td o e st h er e m a i n e ds u b - n e t w o r ks t i l lc o n t a i n s o m es p e c i a ls t r u c t u r ea n dp e r f o r i nc o r r e c t l y s i n c ev e r t e xf a u l t sa n de d g ef a u l t s m a yh a p p e nw h e na n e t w o r ki su s e d ，i ti sp r a c t i c a l l ym e a n i n g f u lt oc o n s i d e rf a u l t y n e t w o r k s i nt h i sd i s s e r t a t i o n ，w ed i s c u s st h ew i d e - d i a m e t e ra n df a u l t - t o l e r a n tp a n c y c l i c - i t yo fs o m en e t w o r k s i tc o n s i s t so ff o u rc h a p t e r s i nt h ef i r s tc h a p t e r ，w ei n t r o d u c eg r a p h - t h e o r e t i c a lt e r m i n o l o g ya n dn o t a - t i o nu s e di no u rd i s c u s s i o n w ea l s oi n t r o d u c et h er e s e a r c hb a c k g r o u n do ff a u l t t o l e r a n c e ，a n dt h es t r u c t u r eo fs o m ew e l l - k n o w nn e t w o r k s i nt h es e c o n dc h a p t e r ，w eb e g i nt os t u d yt h ew i d e - d i a m e t e ro fs o m en e t w o r k s b yt a k i n gu s eo fi n d u c t i o na n dc o n s t r u c t i o nm e t h o d s ，w ef i r s ts t u d yt h ew i d e - d i a m e t e ro fl o c a l l yt w i s t e dc u b e s w ep r o v e dt h a tt h ew i d e - d i a m e t e rd r io f l t q 。i sd 2 = 3 ，d 3 = d 4 = 4 ，a n d 厶堡2 + 2f o rn 5 t h i su p p e rb o u n di s r e a c h a b l ei fni so d da n dn 7 m o r e o v e r ，f o rt w ov e r t i c e sza n dy ，t h e r ee x i s t ni n t e r n a l l yd i s j o i n t ( z ，) 一p a t h so fl e n g t ha tm o s t 厶，i nw h i c ht h ep a t hw h o s e a 1 1v e r t i c e sh a v et h el a s tb i t si d e n t i c a li so fl e n g t ha tm o s t 学1 w ea l s os t u d y t h ew i d e - d i a m e t e ro fm s b i u sc u b e s ( i np r o c e s s ) ，a n de x p e c tt og e tad e f i n i t ev a l u e r a t h e rt h a nab o u n d i nt h et h i r dc h a p t e r ，w ec o n s i d e rt h ef a u l t t o l e r a n c eo fa u g m e n t e dc u b e s w e p r o v et h a tf o rn 4 ，a u g m e n t e dc u b e si s ( 2 n - 3 ) 一f a u l t - t o l e r a n tp a n c y c l i c i t y c o n c l u s i o n sa n ds o m ep r o b l e m st ob es t u d i e df u r t h e ra r ei nt h ef o r t hc h a p t e r 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： 们年上月钞日 矗 第一章基本概念 我们这里所说的互连网络( i n t e r c o n n e c t i o nn e t w o r k ) 是泛指一些组件通过 通讯信道( 包括有线的和无线的) 按照一定的点对点的方式相互连接而构成的系 统这些组件可以是计算机子网络、计算机、计算机内部的处理器、存储器、通信 设备、其他元件或设备等这些组件之间的连接方式是决定网络性能和价格比的 一个主要因素，因此研究网络组件之间的连接方式显得尤为重要网络中组件和组 件之间的连接方式称为该网络的拓扑结构( t o p o l o g i c a ls t r u c t u r e s ) 在分析网 络拓扑结构时，人们通常把网络中组件抽象成一个点，把通信信道抽象成两点之间 的连线，那么该网络的拓扑结构就被抽象成一个图研究网络的拓扑结构问题就 归结为研究图的结构问题换句话说，图是网络结构的数学模型，我们可以通过图 论方法来研究网络的拓扑结构如不加特殊说明，本文所涉及的图均为有限简单 图，有关图的术语和记号可参见f 2 8 1 事实证明，图是互连网络设计和分析的最有用的数学工具，并已被计算机科学 家广泛接受和采用本章将会在第一节简单介绍图的基本概念以及在以后讨论中 要用到的记号；第二节介绍网络容错性问题的背景及研究意义；第三节介绍本文主 要研究的几个著名的网络 1 1图论的基本概念 所谓图( g r a p h ) 是指有序三元组g = ( y ( g ) ，e ( g ) ，妒g ) ，其中v ( g ) 非空，称 为顶点集( v e r t e x - s e t ) ，e ( g ) 称为边集( e d g e - s e t ) 而忆是e ( c ) 到v ( a ) 中元 素有序对或无序对簇v ( g ) xv ( c ) 的函数，称为关联函数( i n c i d e n tf u n c t i o n ) 从定义看，图是一种特殊的代数结构，v ( c ) 中元素称为顶点( v e r t e x ) ，e ( a ) 中 元素称为边( e d g eo ra r c ) ，妒g 描述了边与点之间的关联关系若对每个( 。，y ) 妒g ( e ( g ) ) ，均有( y ，。) 舻g ( e ( g ) ) 即两条边成为对称边( s y m m e t r i ce d g e s ) ，则 称图g 为无向图( u n d i r e c t e dg r a p h ) ，一般记为g ( ve ) ；否则称有向图( d i r e c t e d g r a p h 2 j d i g r a p h ) ，一般记为d ( v e ) 显然，无向图可以看成是特殊的有向图( 对 称有向图1 用无序对x y 来表示成对称边( z ，y ) 和( ，z ) 有序对e = ( 。，y ) e 称为有向 边，z 称为边的起点，g 称为边e 的终点；而e = x y 称为无向边；起点和终点统称为 边e 的端点边的两端点称为相邻的( a d j a c e n t ) 两端点相同的边称为环( 1 0 0 p ) 无环的图称为简单图( s i m p l eg r a p h 或d i g r a p h ) 2 中国科学技术大学硕士学位论文 设g = e ) 是图，y 中元素的个数t ，和e 中元素的个数，即t ，= vj 和e = e f 分别称为该图的顶点数或阶( o r d e r ) 和边数( s i z e ) g 是无向图，岳矿( g ) 的顶点度( v e r t e xd e g r e e ) 定义为g 中与茹关联的边 的数目( 一条环要计算两次) ，记为如 ) 顶点度为d 的顶点称为d 度点( d - d e g r e e v e r t e x ) 零度点称为孤立点( i s o l a t e dv e r t e x ) 用a ( g ) 和6 ( g ) 分别表示g 的 最大( m a x i m u m ) 和最小( m i n i m u m ) 顶点度即 ( g ) = m a x d o ) z v ( g ) ) 6 ( g ) = m i n d a ( z ) z v ( c ) ) 无向图g 称为七正则的( k - r e g u l a r ) ，如果对每个z v ( g ) 均有d g ( z ) = k 设d 是有向图y v ( d ) 的顶点出度( v e r t e x - o u t d e g r e e ) 定义为d 中以 可为起点的有向边的数目，记为站( 可) y v ( d ) 的顶点入度( v e r t e x - i n - d e g r e e ) 定义为d 中以为终点的有向边的数目，记为d 五( 可) 图d ( 或g ) 中连接顶点z 和y 且长度( 1 e n g t h ) 为k 的链( c h a i n 或w a l k ) ，记 为z 耖链，是指顶点戤和边o ，交错出现的序列 w = z 如( = z ) 啦! z i l 口b a i - z “( = 可) ， 其中与边啦，都相邻的两顶点z 白一，和戥，正好是啦，的两个端点( 可能有。= 以a o 和y 称为的端点( e n d - v e r t i c e s ) ，其余顶点称为内部点( i n t e r n a lv e r t i c e s ) w 中边的数目七称为的长度边互不相同的链成为迹( t r a i l ) 内部点互不相同 的链称为路( p a t h ) 两端点相同的链( 迹、路) 称为闭( c l o s e d ) 链( 迹、路) ，闭( 有 向) 路称为( 有向) 圈( c y c l e ) 包含图中所有顶点的路称为哈密顿路( h a m i l t o n i a n p a t h ) 包含图中所有顶点的圈称为哈密顿圈( h a m i l t o n i a nc y c l e ) 图g 中最短 圈的长度称为g 的围长( g i r t h ) ，记为9 ( g ) 图g 中两顶点卫和y 2 _ 间的最短路的 长度称为两点间的距离( d i s t a n c e ) ，记为d g ( o ，! ，) ，当图g 明确时，简记为d ( z ，可) 图g 中任意两顶点z 和之间的距离的最大值，称为图g 的直径( d i a m e t e r ) ，记 为d ( g ) 设z ，掣v 若g 中有连接z 和y 的路，则称z 和可是连通的( c o n n e c t e d ) 若g 中每对顶点都是连通的，则称g 为连通图( c o n n e c t e dd i g r a p ho rg r a p h ) 反之为非连通图( d i s c o n n e c t e dg r a p h ) 两个图g 和日称为是同构的( i s o m o r p h i c ) ，记为g 篁日，如果存在一个双 射0 ：v ( g ) 一y ( 日) ，使得( o ，y ) e ( g ) 乍辛( 日( o ) ，口( 可) ) e ( 日) 并称0 为 1 1 网论的基本概念 3 图g 和日的一个同构映射如果g = 日，则称日为图g 的一个自同构映射( a u t o - m o r p h i s m m a p p i n g ) 图g 的所有自同构构成的群，称为图g 的自同构群( a u t o - m o r p h i s mg r o u p ) 记为a u t ( g ) 图g 称为点可迁的( v e r t e x - t r a n s i t i v e ) ，如果对于任意的两点z ，y v ( g ) ， 存在图g 的自同构日，使p ( 。) = 图g 称为边可迁的( e d g e - t r a n s i t i v e ) ，如果对 于任意的两条边e 1 = 伽，e 2 = x y e ( g ) ，有g 的一个自同构目，使得口( ，t ，) ) = 伽，可 即将边e l 映到边e 2 设m c e c o ) 如果m 中任意两边在图g 中是不相邻的，则m 称为图g 的一 个匹e ( m a t c h i n g ) 如果图g 的匹配m 的端点集等于y ( g ) ，则m 称为图g 的 完备匹百己( p e r f e c t - m a t c h i n g ) 许多著名的网络结构属于笛卡尔乘积图或c a y l e y 图 1 笛卡尔乘积图 设a 和b 是两个有限集，a 和b 的笛卡尔乘积a b = f ( 口，b ) ：a a ，b b ) 为使记号简单起见，在不至于引起混淆的情况下，简记a x b 中元素( r l ，6 ) 为n 6 同样地，简记n 重笛卡尔乘积a 1 a 2 a = ( n 1 ，a 2 ，a n ) ：啦a ，i = 1 ，2 ，住 中的元素( a l ，a 2 ，n ，1 ) 为a l a 2 a n 笛卡尔乘积方法是一个重要的构图方法，它是i 扫s a b i d u s s i ( 1 9 5 7 ，1 9 6 0 ) ( 参见 f 7 ，8 】) 首先提出来的笛卡尔乘积方法是从已知图构造更大图的有效方法由这种 方法构造的图保持了因子图的许多性质，并且它的许多的图论参数，例如直径、顶 点度、连通度等等都能由其因子图计算出来正是由于这些好的性质，使得笛卡尔 乘积方法成为网络设计的重要方法之一 设g = 似，蜀) 是顶点数为i k i = 啦，边数为i 蜀i = e ，i = 1 ，2 ，k 的 无向图图g 1 ，g 2 ，g k 的笛卡尔乘积是一个无向图，称为笛卡尔乘积图，记 为g l g 2 g k ，其中v ( 0 1 g 2 g k ) = k k v k ；两个不同顶 点z l z 2 茹k 和y l y 2 y k 在g 1 g 2 x g k 中相邻铮x l ，z 2 ，钆和y l ，y 2 ， 蛳仅有一个坐标不同，不妨设为第i 个坐标，并且z 执e ( g t ) 2c a y l e y 图 可迁图是一类重要的图，它具有高度的对称性，是比较理想的高性能超大规模 计算机系统互连网络的拓扑结构这里我们介绍构造一类重要可迁图c a y l e y 图 的方法因为构造涉及到群论的概念，因而被称为代数方法 设r 是非平凡有限群，s 是r 的不包含单位元e 的非空子集定义一个有向 4 中国科学技术大学硕士学位论文 图g 如下 v ( c ) = r ( 。，y ) e ( c ) 兮x - l y 最对于任意z ，y r 如上定义的有向图，是由英国数学家c a y l e y 【1 】首先提出，所以一般教科书和文献 都称它为群r 关于子集s 的c a y l e y 图，记为g r r ( s )c a y ( r ，s ) 当s - 1 = s 时，群r 关于子集s 的c a y l e y 图c r ( s ) 是对称有向图，它可以看成 是无向图 c a y l e y 图有许多好的性质，一个最明显的性质就是c a y l e y 图是点可迁的但 是点可迁图并不都是c a y l e y 图，一个著名的例子是p e t e r s e n 图 1 2网络容错性问题的背景和研究意义 在设计和选择一个互连网络的拓扑结构时，可靠性是评估网络性能的重要概 念高可靠性的互连网络直是网络设计者追求的重要目标之一然而可靠性是 一个非常抽象的概念，我们只从网络的拓扑结构上考虑硬件故障对网络可靠性的 影响，即在网络结点和( 或) 连线可能发生故障的情况下的数据传输的可靠性在这 种意义下，对于一个给定的互连网络，最多能容纳多少个结点和( 或) 连线同时发生 故障，而剩余的子网络中每个结点之间还仍能继续保持通信为区别其他含义可 靠性，文献上习惯称这种可靠性为容错性( f a u l t t o l r e n c e ) 网络容错性的实质是 当故障发生时，剩余网络的重组能力 两个重要的衡量重组能力的标准一是：图的嵌入此标准最早f 扫h a y e s 在文献 9 】中提出二是：网络中存在一定的故障点，它是否还能保持连通即任何一对非 故障点之间是否存在路相连 近些年，人们对结点和( 或) 边发生故障的网络中路和圈的嵌入问题作了很多 研究在文献f 2 4 】中，h s i e h 等人提出了点容错哈密顿性和边容错哈密顿性，用来 度量网络的容错哈密顿性文献 2 6 】， 17 将此概念推广为点( 边) 容错哈密顿连通 性，容错哈密顿性，容错哈密顿连通性及容错泛圈性等概念 如果对图g 的任意故障点( 边) 集f v ( c ) 旧( g ) ) 且i f is 后，图g f 仍是 哈密顿的( 哈密顿连通的，泛圈的，泛连通的) ，称图g 为k 点( 边) 容错哈密顿的( 哈 密顿连通的，泛圈的，泛连通的) 如果对图g 的任意故障集f v ( g ) u e ( g ) 且l f k ，图g f 仍是哈密顿的( 哈密顿连通的，泛圈的，泛连通的) ，称图g 为k 容错 哈密顿的( 哈密顿连通的，泛圈的，泛连通的) 文献【1 9 】，【1 6 】，【2 5 l ，【2 7 】，【1 4 】研究 1 3 几个著名的网络 5 了不同f 。9 络的上述容错性能 人们还提出了一系列方法衡量网络的容错性。包括确定性的和概率性的研 究者们主要运用图论的概念发展确定性的方法连通度就是被广泛应用的一种 如果图g 代表互连网络的拓扑结构，那么连通度托( g ) ( 或边连通度a ( g ) ) 是破坏 网络连通性的最小结点数；换句话说，即网络要保持连通性可以允许斤( g ) 一1 ( 或a ( g ) 一1 ) 同时发生故障因此连通度越大，网络的可靠性越大我们知道如 果图g 是沙连通，汕正则的，则它同时拥有最优的连通度和最小的边数因此，u 一连 通汕正则图是一种经济而可靠的网络结构 1 3 几个著名的网络 本节将介绍几个著名的网络，它们一般都具有简单的递归结构和高对称往、高 容错性、简单结构的可嵌入性、简单路由选择算法和易扩充性等许多好的性质 1 3 1 超立方体网络 图1 1 ：超立方体网络口l ，口。和口3 1 0 1 1 1 1 超立方体网络的拓扑结构是指竹维立方体，通常记为q 。它的图论模型是一 个简单无向图q k = ( ke ) h a x a r y ( 6 】已列出它的许多等价定义，最常见的是如 下定义 q k 的顶点集由所有长为n 的二元字符串组成，即 v = z n 一1 z 1 ：茹i t o ，1 ) ，i = 1 ，2 ，竹 6 中国科学技术大学硕士学位论文 两顶点z = 一1 z 1 和y = y , ，y n 一1 玑在q 。中相邻铮墨lj 毛一玑i = 1 ，即有且仅有一个坐标不同 图1 1 所示的是超立方体网络q 1 ，q 2 和q 3 礼维超立方体网络有下面一些性质 性质1 瓴有铲各顶点，是h i e 则的，有彬。条边 性质2q 。的直径是n ， 性质3q 。是二部分图 性质4q 。是c a y l e y 图 性质5q 。是点和边可迁的 1 3 2 折叠立方体网络 在文献 2 】中，e 1 - a m a w y 和l a t i f i 提出n 维折叠立方体网络f q 。的概念，它 是通过在礼维超立方体网络固k 中添加2 1 条边而得到的新网络即v ( f q n ) = o n 一1 z 1 ：甄 o ，1 ，i = 1 ，2 ，) ，预点x = x n x ，1 o l 和y = y n y n 一1 y l 相邻咎可= y , 。y n 一1 y l = 劣n x n 一1 x i + l x i x i 一1 z 1 ，其中1 is n ( 此时称( o ，y ) 为正常边) ；或y = 铷一1 讥= 孟。孟。一1 孟1 = 孟，其中0 = 1 ， i = 0 ( 此时称( 。，y ) 为补边) ，顶点y = 磊牙。一1 牙1 = 至称为x 的补点 图1 ，2 所示的是折叠立方体网络f q 3 和f 矾 i n f q 图1 2 ：f q 3 - 与f q a ( 视边表示朴边) 在文献【2 】中，e 1 一a m a w y 和s l a f i i i 等人研究了折叠立方体网络的性质n 维 折叠立方体网络显然和仃维超立方体网络具有相同的顶点数目，边数比n 维超立 1 3 几个著名的网络 7 方体网络多2 ”1 条n 维折叠立方体网络的连通度是n + 1 ，直径是学1 它具有 和超立方体网络类似的高对称性结构、简单的路由算法而它的直径几乎是同样规 模的超立方体网络的一半，因此折叠立方体网络被看作超立方体网络的一个很好 的替代者 1 3 3 局部纽立方体网络 圆 ( 耐l t q a( ”l t q 3 的一种对称画法 ( c ) l t q , j 图1 3 ：局部纽立方体网络l 购3 和工t 铂 局部纽立方体网络l t q 。( n 2 ) 是由y a n g 等人【3 2 】最近提出来的一种超 立方体网络q 。的变型它同超立方体网络一样有妒个顶点，每个顶点是一个长 为7 , 的二元字符串一l z 。一2 z l z o 其中趣 o ，1 两个顶点z = 一l x n 一2 1 z o 与g ，= 鲰一1 一2 1 珈相邻当且仅当它们满足下面的其中一条： ( 1 ) 存在整数k ，满足2 k n 一1 使得 ( 8 ) = 饥( 蟊是y k 在 o ，1 ) 中的补) ， ( b ) 钆一1 = y k 一1 + 勒，且 8 中国科学技术大学硕士学位论文 ( c ) z 和其余的分量相同 ( 2 ) 存在整数詹，满足k o ，1 使得。和仅有第k 个分量不同，其余分量都 相同 图1 3 所示的是局部纽立方体网络l t q 3 和l t q t 局部纽立方体网络作为超立方体网络的一种变型，尽大可能的保留了超立方 体网络的递归结构等很好的性质它的两个相邻的顶点至多有两个相继分量不同 一个n 维的局部纽立方体网络的连通度是n ，当竹25 时，直径是堡笋1f 3 2 】它同 样有较为简单的路由算法也被看作超立方体网络的一种很好的替代者 1 3 4m s b i u s 立方体网络 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 图1 4 ：m 6 b i u s 立方体阿络m q o 和m 饿 f 戗 盯0 ： e h c u l l 与l a r s o n 2 0 ，2 1 ，2 2 提出的m 曲i 1 】s 立方体网络m q 。，它的顶点集 与n 维超立方体网络a k 的顶点集相同，具有2 ”个顶点，每个顶点是一个长为n 的 二元字符串，当顶点0 = 1 ，2 ，1 1 , ) 满足下列条件时，顶点k 与顶点x = 1 - 3 几个著名的网络 9 z l z 2 z n 相邻 ， ，i o l o t 一1 磊z t + 1 x n当一1 = o 日寸， iz 1 一1 磊磊+ 1 ，孟n 当以一1 = 1 时， 其中霸为戤在 o ，1 中的补元素 也就是说，当z “= 0 时，顶点x 与一个仅在分量飘与x 不同的顶点相邻， 当1 = 1 时，顶点x 与一个从分量戤到分量z 。都与x 不同的顶点相邻当i = 1 时，顶点x 与顶点m 的连接方式没有定义，所以可以设o o = 0 或z o = 1 ，我们得 到两种稍微有些不同的网络当：g o = 0 时，将得到的网络记为m q ：；当x o = 1 时， 将得到的网络记为m 硪 图1 4 所示的是m 6 b i u s 立方体网络m q 2 和m q i m s b i u s 立方体网络作为超立方体网络的一种变型，不但保留了超立方体网络 的递归结构等很好的性质还有许多优良性质一个n 维的m s b i u s 立方体网络的 连通度是当n 1 时，d ( m q ：) = 8 笋 ；当n 4 时，d ( m q o ) = 字 【2 2 】 它同样有较为简单的路由算法也被看作超立方体网络的一种很好的替代者 1 3 5 增广立方体网络 最近c h o u d u m 和s t m i t h a 提出了增广立方体网络 它的拓扑结构定义如下：a q l 即为k 2 ，顶点定义在集合 o ，1 ) 上当n22 时 a q 。可由在相同递归结构a 职一1 和a q ：一1 之间添加妒条边得到 图1 5 ：增广立方体a q l ， 口2a n da q a 假设4 职一1 的顶点集为 o 一l u 2 u l ：u i = 0 ，1 ，a 砚一1 的顶点集为 1 一1 t j 2 口1 ：地= 0 ，1 ) ，t = o u 一l 坳u 1 和口= 1 一1 忱t ，1 相连当且仅当： ( 1 ) 地= 饥，1sts 礼一1 ，此时令口= 铲或“= v h ； 1 0 中国科学技术大学硕士学位论文 ( 2 ) m = 魂，1 i t l 一1 ，此时令t ，= , u c 或u = t ，c ； 图1 5 所示的是增广立方体网络a q l ，a q 2 ，a q 3 在文献f 2 3 】中，c h o u d u m 和s u n i t h a 指出增广立方体是超立方体的一种新变 形它继承了超立方体的优点，包括c a y l e y 图，点对称，( 2 n 一1 ) 连通，最优的宽直 径值径+ 1 ) 他又有超立方体及其他变形所没有的优点，比如1 1 维的增广立方体包 含两个具有相同根结点的边不交的完伞二叉树，两个边不交的生成二叉树 第二章互连网络的宽直径 2 1宽直径及相关概念和研究意义 在引入宽直径概念之前，先介绍著名的m e n g e r 定理 定义2 1 1 x , y 是图g 的两个相异顶点u 条( x ，y ) 一路p 1 ，恳，兄称作是内点 不交的f 边不交，如果这条路上没有相同的内点( 边) 定义2 1 2 ( z ，掣) 一m e n g e r 数，记做 d ( x ，y ) = 丁n + 1 ，如果n 是奇且几7 ， d ( x ，仇) = d ( x ，w ) = 字 对i = t ，2 ，n 一1 所以，任何长达到d ( x ，w ) 的( z ，t j ) 路必然通过y 而非t ，的其他邻点任何( z ，) - c o n t a i n e r 中必有一条( z ，y ) 一路，假设 为p ，= p ( x ，叫) u ，可) ，p ( z ，钮) 是一条( z ，伽) 路，其上没有y 所p a p ( x ，叫) 的路 长至少d ( 易 t o ) + 1 = 字1 + 1 则p ，的长度至少学 + 2 ，即，厶2 学1 + 2 定理得证 2 4m s b i u s 立方体的宽直径 由第一章介绍的m s b i u s 立方体网络的定义知，m 识( 或m q i ) 可以由m q o 一1 和m q ：一1 之间加2 ”1 条边得到我们给m 职一1 或m q j 一1 中的点x = 岳1 2 2 z 。1 重新标号，得到点x 7 = z i 靠，其中当i = 1 ，2 ，n - 1 时，令z “d t = 戤， 当x 在m o 一1 中时，令硝= o ；当x 在m 识一l 中时，令z i = 1 将m 职一l 中新 标号的点与m q ：一1 中仅在第一个分量与之不同的顶点相连，得到m q o ；将m o 一1 中新标号的点与m q ：一，中从第一个分量到第n 个分量都与之不同的顶点相连，得 到m q ：我们可以简记m q 。= l or ，其中l = m q o 一1 ，冗= m q ：- 1 图2 4 所示的是m q 2 和m 硪，其中( c ) 是m q o 的一种对称画法 中国科学技术大学硕士学位论文 图2 4 ：( ”吖翻( b ) 识( c ) m q o 的一种对称i 面法 1 0 作为超立方体网络q 。的一个的变型，m s b i u s 立方体网络m q l n 具有许多优于 超立方体网络k 的一些性质，例如，当n 1 时，d ( m q ：) = f 警 ，当n 4 时， d ( m q o n ) = 孚1f 2 2 】 对于m s b i u s 立方体的宽直径，徐俊明和邓志国曾得到了一个界 定理2 4 1 ( x u 和d e n g 2 9 】) 堡2 2 + 1 厶( 嘲) f 孚 + 2 当n 4 时 墨笋1 + 1 厶( 螈) s 孚1 + 2 当n 1 时 我们改进了这一结果，期望得到一个较为确定的值 定理2 4 2 ( 完成中) m s b i u s 立方体尬。的宽直径， a ( i o ) = 孚1 + 1 ； 厶( ) = 字 + 1 ( n 是偶) ； f 孚1 + 1 d r i ( u x ) 2 笋 + 2 ( n 是奇) ； 此结果表明m s b i u s 立方体的宽直径只有大约同阶超立方体的一半 在证明定理之前，先介绍几个定义 顶点k 与顶点x = z l z 2 相邻 k ： 勋址佩坼1 岛凯- 0 时 【x l 鼢一1 氟蕊+ 1 童n 当戤一1 = 1 时， 其中霸为x i 在 o ，l ，中的补元素， 2 4m s b i u s 立方体的宽直径 定义2 4 3 = z l 戤一1 孟t 黾十1 z 。，( 如果甄l = 0 则称此( x ，k ) 边是m 型边；如果z “= 1 ，则称此( x ，k ) 边是1 一型边 定义2 4 4 称 缸中的一条路是偶( 奇) 的，如果包含偶( 奇) 数条1 型边 令p ，是。一婶n 一2 ) 中的一条( ) c ，) 路，其中文= z 1 x 2 x n t ，y ，= 可1 耽一f 我们通过在上的每个点添加后缀x 。一l q - 1 或一“l 霸可以 得到螺中的( x ，y ) 路p 首先，添加一f + l 为x 的后缀，即，x = z 1 一1 z 。 然后依次添加其他点的后缀对于p ，中的边( z ，u ，) ，如果z 7 的后缀a z 。一t + 1 ， ：2 u - t + l 一“2 孟。) ，那么边( z ，u ) 可以通过向u 添加后缀得到规则如下： 1 如果( z 7 ，u ，) 是o - 型边，则添加a 作为“的后缀 2 如果( z ，u ，) 是1 一型边，则添加矗作为u ，的后缀 显然，根据以上的规则，如果( z ，u ，) 是p ，中的m 型( 1 一型) 边，则( z ，u ) 仍是 靠中 的0 型边( 1 型) 因此，p 是 乱中的一条与p ，有相同长度和奇偶性的路如果p ， 是偶路，则x 和y 的最末z 位均是z 。“1 ，如果p ，是奇路，则y 的末f 位 是一t + l 一抖2 引理2 4 5 礼是偶数且佗2 ，x = z 1 x 2 和y = y l y 2 鲰是 靠中两相异 点那么存在n 条内点不交的( x ，y ) 路，路长不超过f 譬2 + 1 1 ) 当鲰一1 = 孟 n - 1 或一1 y n = 一1 时，满足以下三个性质中的任一个 巩：至少有一条偶路长至多f 譬2 1 1 踢：至少有一条偶路和一条奇路长都至多f 2 軎窒1 绲：至少有两条偶路长至多f 2 竽1 且都至少含有一条l 一型边( 其中一条上至 少含有1 。型内边) 2 ) 当鲰一1 = x n - 1 或鲰一1 鲰= 一l 时，满足以下三个性质中的任一个 巩：至少有一条偶路长至多r 翌乒1 1 ； 踢：至少有一条偶路和一条奇路长都至多f 卫# 1 绲：至少有两条偶( 奇) 路长至多f 譬2 1 且都至少含有一条1 一型边( 其中一条上 至少含有1 型内边) 证明：我们对偶数n ( 22 ) 进行归纳 如是a 圈，显然结论对n = 2 成立n = 4 时，也容易从m 2 构造出满足性质的路我们证明对n 4 的偶数也成立令= z 1 勋：g n - 3 2 3 。2 和，= 掣1 抛y n 一3 y n 一2 是肘j 一2 的两个相异点为得到中的 中国科学技术大学硕士学位论文 路，我们向) c ，和，分别添加后缀z 。一1 和鲰一1 如根据不同的弧一l ，我们分以下 四种情形讨论 情形1 一1 = 一l x n 如果爿是偶路，我们容易从只得到( 一1 z 。，y ，z 。一1 ) 路，路长至多f 2 1 如果只是奇路且有一个内点的末位是1 ，假设为2 帕我们可以构造乃如 下 弓( ) 【，一l x n ，z 。一l x n ) 和弓( z 。1 ，y l z n 一1 ) 可以分别由弓( ) c ，) 和彰( ，y ) 得到 如果弓心，) 是偶路，则弓( ，矿) 必为奇路 b = 弓( 】( ，一i ，$ ，1 ) u ( 瓢一l x n ，一1 牙n ) u 弓( 瓢霸一l 牙n ，y ，一1 ) 如果弓f ，) 是奇路，则弓( ，y 7 ) 必为偶路 b = 巧( x 乞，1 ，磊一l 厶) u ( 孟n 一1 孟n ，一1 ) u 巧( 一l x ny 7 z 一1 z n ) 显然马的长至多半1 + 1 ，剩下还需构造两条路r 一1 和p n 根据不同的骱一3 y 一2 ， 我们分两种子情形讨论，试图在螈中构造出满足引理条件的路 子情形1 1 一3 一2 = 一3 一2 或鲰一3 y n 一2 ；x n 一3 z n 一2 子情形1 2 一3 鲰一2 = z 。一3 牙”2 或铷一3 y n 一2 = 霸一3 牙p 2 情形2 一l y n 一一l x n 如果只是奇路，假设z t 是的邻点 只= 只( ) 【，一1 ，z i x n 一1 z 。恢靠一l 牙。】) u ( z 一i x 。陬一l 】，z i z n 一1 阮牙。一1 。j ) u ( 固一1 霸k 一l 】，y 7 磊一1 z n ) 如果只是偶路且至少含有一个最末位是0 的内点，假设为乃，则我们可以构 造毋如下： b = g ( ) c ，一1 ，巧g ，1 z j x n l 露。】) u ( z 。一1 防一l 牙n j ，巧磊一l b z l 霸】) u 碍( 巧厶一1 z 。 z j x 。一l j ，y 7 牙，l x 。 情形3 一1 弧= 一1 如果只是偶路，假设z t 是矿的邻点 只= 爿( ) 【，一1 ，z i z n i x 。眩一1 】) u ( z t 一1 阮一1 】，施一1 磊f z i 牙。一l z n ) u 慨一1 眩一1 】，一1 ) 如果爿是奇路且至少有一个内点的最末位是o ，假设为巧，则我们构造弓如下： 2 4m s b i u s 立詹体的宽直径 2 7 p j = 弓( 一1 z n ，。n 一1 b 牙。1 孟。】) u ( 巧z 。i x 。【磊一1 靠】，巧牙。一1 【z j 一1 孟。】) u 碍( 一1 畅z ，1 】，y x n 一1 牙。) 情形4 y n 一1 = 一1 如果只是奇路，只= 只( 】【，一1 z 。，y ，牙。1 牙。) 如果有条偶路砭，所有内点的最末位都是o 且路长至多三1 我们构造最 如下假设是冠上的任一个内点 最= 最( 一一1 ，一l k 懂。一1 牙。】) u ( 一1 z 。 磊一1 孟。】，z z 。1 牙。【一i t , 。】) u ( z t x n 一1 孟。k 孟。一1 】，一靠一1 牙。f x n i x 。】) u 最( 一一1 孟。【一z 。1 j ，暑，牙。一1 ) 如果在偶路爿上至少