（应用数学专业论文）互连网络转发指数的研究.pdf

摘要 图g = = ( e ) 是一个n 阶的连通图g 的一个路由选择r 是g 中n ( ”一1 ) 条路径集，它指明对每对顶点( z ，g ) ，z 口，数据从z 通过路径r ( z ，) 传输到g 如 果这些路径经过某个结点的条数过多，即经过该结点转发的数据量过大，势必影 响网络的通讯效率；或者超过该点的控制容量造成信息拥塞，甚至导致整个网络 的瘫痪很显然，一个好的路由选择不应该过多次地经过某个结点 于是c h u n g ，c o f f m a n ，r e i m a n 和s i m o n 于1 9 8 7 年提出一个度量路由选择优劣 的参数：点转发指数 没g 足一个图，r 是给定的路由选择，对于g 中的点z 关于r 的点转发指 数( g ，r ，。) 定义为由r 确定的路径经过z ( 即z 作为中间点) 的条数定义 f ( g ，r ) = m 缸“( g ，r ，z ) ：z y ( g ) 为路由选择r 在g 中的点转发指数；定义 ( g ) = m i n ( g ，r ) ：v 嘲 为g 的点转发指数 类似地，h e y d e m a n n ，m e y e r 和s o t t e a u 于1 9 8 9 年提出了路由选择r 的边转 发指数的概念 设g 是一个图，r 是给定的路由选择对于g 中的边e 关于r 的边转发指 数”( g ，r ，r ) 定义为由r 确定的路径经过边e 的条数定义 ( g ，咒) = m a x _ c ( g ，r ，e ) ：e e ( g ) ) 为路由选择r 在g 中的边转发指数；定义 7 r ( g ) = m i n ( g ，r ) ：v 冗 为g 的边转发指数 与点转发指数一样，一个好的路由选择和好的网络也都应具有小的边转发指 数，或者边转发指数不超过网络各条边的负载量路由选择的边转发指数是受网 络负载量控制，因此边转发指数也是度量路由选择优劣的一个重要参数本文研 究的主要内容是网络的转发指数问题 全文共分五章，其中第一章介绍本文用到的一些著名互连网络拓扑结构和它 们的基本性质，第二章介绍网络的点转发指数和边转发指数的定义和已知的基本 结果第三章和第四章是本文的主要部分，得到了以下几个结果： 1 解决了b o u a b d a l l a h 和s o t t e a u 关于多重集的一个猜想，得到在最大度被限 制的条件下，网络的边转发指数的一些新结果 2 总结了连通度与转发指数的关系，并改进一些已知的结论 3 考虑笛卡尔乘积图的转发指数，得到了它的一个下界，并由此推出一些著 名网络的转发指数 4 通过设计一个合适的路由选择，确定了折叠立方体的转发指数 5 考虑循环网络的转发指数，得到它的上下界，并由此推出一些著名网络的 转发指数 6 在已有路由的基础上，确定了增广立方体的转发指数 在第五章中，我们对本文的工作进行了总结，并且提出了准备研究的几个问 颢 a b s t r a c t l e t g = ( k e ) b e ac o n n e c t e d g r a p h o f o r d e r mar o u t i n g r i n g i s as e to f n ( n 一1 ) f i x e dp a t h sf o ra l lo r d e r e dp a i r s ( 。，y ) o fv e r t i c e so fgt h e p a t hn ( x ，y ) s p e c i f i e db yr f ：a lr i e st h ed a t at r a n s m i t t e df r o mt h es o m c e 。t ot i l ed e s t i n a t i o n y i ti sp o s s i b l et h a tt h e f i x e dp a t h ss p e c i f i e db yag i v e nr o u t i n gr p a s st o of r e q u e n t l yt h r o u g hc e r t a i nv e r t i c e s o l e d g e s ，w h i c hm e a n st h a tt h er o u t i n gr o v e r l o a d st h ev e r t e xo rt h ee d g et h el o a d o fa r t yv e r t e x0 re d g ei sl i m i t e db yt h ec a p a c i t yo ft h ev e r t e xo rt h ee d g e ，o t h e r w i s ei t w o u l da f f e c t , t h ee f f i c i e n c yo ft r a n s m i s s i o n ，e v e nr e s u l t i n gi nm a l f u n c t i o no ft h en e t w o r k i ts t j e l n sq u i t en a t u r a lt h a ta “g o o d ”r o u t i n gs h o u l dn o to v e r l o a da n yv e r t e x0 1 e d g e ，i nt i l es e n s et h a tn o tt o om a n yp a t h ss p e c i f i e db y t h er o u t i n gs h o u l dg ot h r o u g hi t i no r d e i t om e a s u r et h el o a do fav e r t e x ，c h u n g ，c o f f m a n ，r e i m a na n ds i m o np r o p o s e d t h ec o n c e p to ft h ev e r t e x - f o r w a r d i n gi n d e x 。 l e tgb eag r a p hw i t hag i v er o u t i n g 咒a n d 。av e r t e xo fg t i l el o a do fzw i t h r e s p e c t t , or ，d e n o t e db yf ( g ，r ，。) ，i sd e f i n e da s t h en u m b e ro fp a t h ss p e c i f i e db yr g o i n gt u o u g hz t h ep a r a m e t e r ( g ，r ) = m a x f ( g ，咒，茁) ：z v ( g ) i sc a l l e dt l l ev e r t e x - f o r w a ld i n gi n d e xo f ( g ，r ) ，a n dt h ep a r a m e t e r ( g ) = m i n f ( g ，r ) ：vr ) i sc a l l e dt h ev e r t e x - f o r w a r d i n gi n d e xo fg s i i f i l a r p r o b l e m sa r es t u d i e df o re d g e sb yh e y d e m a n n ，m e y e ra n ds o t t e a u t h e 1 0 a do f a ne d g eew i t hr e s p e c tt or ，d e n o t e db y ( g ，r ，e ) ，i sd e f i n e da st h en u m b e ro f p a t h ss p e c i f i e db yr w h i c hg ot h r o u g hi tt h ee d g e f o r w a r d i n gi n d e xo f ( g ，r ) ，d e n o t e d b y 丁r ( g ，r ) i st h em a x i m u m n u m b e ro fp a t h ss p e c i f i e db yrg o i n gt h r o u g ha n ye d g eo f g ，ie ， 7 r ( g ，r ) = m a x c r ( a ，r ，e ) ：e e ( g ) ) ； a n dt h ee d g e - f o r w a r d i n gi n d e xo fg i sd e f i n e da s 7 r ( g ) = m a x 7 r ( g ，r ) ：vr ) v 1 i nt h i sd i s s e , r a t i o n 、w ed i s c u s st m f o r w a r d i n gi n d e xo ft m t w o r k s i tc o r t s i s t so ff i v e c h a p t e i si nt h e 矗s tc h a p t e r w ei n t r o d u c et h et o p o l o g i c a ls t r u c t u r e sa n df o u n d a t i o n a l i ) i ( i p e z t i e so fs e i n ew e l l k n o w nn e t w o r k su s e di no u td i s e u s s i o n i nt h es e c o n dc l l a p 【、 w ei n ti _ o d u c et h ec o n c e p t sa n db a s i ck n o w nr e s u l t s0 fv e r t e x - f o r w a r d i n gi n d e xa n de d g e f ( j 1 1 w u d i n gi n d e xo f an e t w o r k o u rm a i nr e s u l t s & r es e a t e di nt h et h i r dc h a p t e ra n dt h e n n uc h a p t ，e y ，u n dl i s tb e l o w 1i v es e v e r e rl x e wr e s u l t so nt h ee d g e f o r w s x d i n gi n d e xw i t ht h el l l & k i f v 1 r 1 1d e g r e e c o n , s t r ； i n e db yp r o v i n gac o n j e c t u r eo fb o u a b d a l l a ha n ds o t t e a uo nm u l t i p l e - s e e s 2s u mu pt h e e l a t k m s h l pb e t w e e nt hc o n n e c t i v i t y 札1 dt h ef m w a r d i n gi n d e xa n d i m p r o v es o l n ck n o w nr e s u l t s ll e x q t a b t i s hal o w e rb o u n do ft h ef 。1w a r d i n gi n d e x 。ft h ec a r t e s i a np r o d u c t r a g h s 、 t i o mw h i c ht h ef o r w a r d i n gi n d i c e so fs o l i t ew e l l k j l o w nn e t w o r k sa r ed e d u c e e d 4d ee q i u l i n et h ef o r w a r d i n gi n d e xo ft l kf o l d s 4c u b eb ，d e s i g n i n ga a p p r o ”r i a 沁 r o u t i t x g 5e s t a b l i s ht i l e u p p e ra n dt h el o w e r b o u a d so ft h ef o r w a - r d i n gi n d e xo ft h ec l r u k i n tn e t w u r kf r o mw h i c ht h ef o r w a r d i n gi n d i c e so fs o r i l ew e l l - k n o w nn e t w o r k s0 a e d e d u c e d 5d e t e r m i n et h ef o r w a r d i n gi n d e xo ft i ma u g m e n t e dc u b eb a s e do nak n o w nr o u t i n g c o n c l u s i o n sa t l d $ 0 1 1 1 ep r o b l e m st ob es t u d i e df u r t l m ra r ei nt h 吧t i l 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 ) 在分析网络拓扑结构时，人们通常把网络中组件抽象成一个点，把通信信道抽象 成两点之间的连线，那么该网络的拓扑结构就被抽象成一个图研究网络的拓扑 结构问题就归结为研究图的结构问题换句话说，图是网络结构的数学模型，我 们可以通过图论方法来研究网络的拓扑结构，如不加特殊说明，本文所涉及的图 均为有限简单图有关图的术语和记号可参见 8 0 】 本章将会在第一节介绍一些网络设计的方法；第二节介绍一些著名的网络 1 1网络设计的几个方法 1 1 1 网络设计的代数方法和c a y l e y 图 可迁图是一类重要的图，它具有高度的对称性，是比较理想的高性能超大规 模计算机系统互连网络的拓扑结构这里我们介绍构造一类重要可迁图一c a y l e y 图的方法因为构造涉及到群论的概念，因而被称为代数方法 设f 是一非平凡有限群，s 是r 的不包含单位元e 的非空子集定义个有 向图( ；如下； v ( g ) = r ；( z ，y ) e ( a ) 铮x - l y s ，对于任意，y r 如上定义的有向图，是由英国数学家c a y l e y 【1 0 】首先提出，所以一般教科书和文 献都称它为群r 关于子集s 的c a y l e y 图，记为c r ( s ) 或c a y ( r ，s ) 当s 一- = 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 1 ) 1 2 中国科学技术大学博士学位论文 图1 1 ：p e t e r s e n 图 除了c a _ y l e y 图之外，g a u y a c q 于1 9 9 7 年在文献【2 7 】中给出了q u a s i c a y l e y 有 向图的定义 首先我们给出q u a s i 一群的定义称非空集合q 为一个q u a s i 群，如果在q 中 定义了一个封闭的二元运算，它满足v a ，b q ，方程n $ = b 及y a = b 在q 中都有 唯的解 对于一个q u a s i 一群q ，s 是q 的子集，如果v a ，b 日，有( a b ) s ：a ( b s ) ，则s 称为右结合的 设q 是一个有右单位元1 的q u a s i 群，s 是q 的一个不含右单位元的生成 子集，并且是右结合的定义个有向图q c ( q ，s ) ，其中 v ( q c ( q ，s ) ) = q ；e ( q c ( q ，s ) ) = “m q s ) ：q q ，8 s ) 上面定义的图称为q u a s i c a y l e y 有向图 由q c ( ( 4 ，s ) 的定义可知，q u a s i c a y l e y 有向图是无环的，点可迁的( 参见 6 9 ) 对称有向图( 即可看成无向图) ，一般称为q u a s i ，c a y l e y 图当q 是一个群时， q c ( q ，s ) 即为c a y l e y 图c 白( s ) 1 1 2 网络设计的乘积方法和笛卡尔乘积图 设4 和b 是两个有限集，且和b 的笛卡尔乘积a b = ( 。，b ) ：o a ，b 日) 为使记号简单起见，在不至于引起混淆的情况下，简记a x b 中元素( a ，b ) 为0 6 同样 地，简记 重笛卡尔乘积a 1 a 2 x a 。= ( o l ，a 2 ，o 。) ：a 。a ，i = 1 ，2 ，n ) 11 网络设计的几个方法 中的元素( a 2 ，。) 为a l a 2 a n 本节考虑一个重要的构图方法一笛卡尔乘积方法，它是由s a b i d u s s i ( 1 9 5 7 ，1 9 6 0 ) ( 参见【6 3 ，6 4 j ) 首先提出来的笛卡尔乘积方法是从已知图构造更大图的有效方法 由这种方法构造的图保持了因子图的许多性质，并且它的许多的图论参数，例如 直径、顶点度、连通度等等都能由其因子图计算出来正是由于这贱好的性质， 使得笛卡尔乘积方法成为网络设计的重要方法之一 设g 。= ( k ，e ) 是个顶点数为i k | = n i ，边数为l e i i = 岛，i = 1 ，2 ，k 的无向图图g 1 ，g 2 ，g t 的笛卡尔乘积是一个无向图，称为笛卡尔乘积图，记 为g l g 2 x g k ，其中y ( g 1 g 2 g k ) = h 场v k ；两个不同 的顶点z 】上2 。k 和扪y 2 弧在g 1 g 2 xg k 中相邻爷( z h x 2 ，茁k ) 和 ( 扎y 2 ，挑) 仅仅一个坐标不同，不妨设为第i 个坐标，并且x l y l e ( g i 设皿= ( k ，蜀) 是七个顶点数为f kj = ，边数为 且j = 旬，i = l ，2 ，k 的有向图图d 。，域，d k 的笛卡尔乘积是一个有向图，称为笛卡尔乘积有向 图，记为d i d 2 d k ，其中v ( d 1 d 2 d k ) = k ； d l d 2 d k 中存在从顶点z l z 2 z 到另一个顶点y l y 2 y k 的有向边 骨( 扎圯，。) 和( y l ，y 2 ，y k ) 仅仅一个坐标不同，不妨设为第i 个坐标，并且 ( z 。，m ) e ( d 。) 1 1 3 网络设计的线图方法和线圈 线图是由h a r a r y 和n o r m a n ( 1 9 6 0 ) ( 参见 3 7 】) 首先提出来的它是从一个已知 图获得另一个更大的图的一个重要的构图方法，也是从图中与边有关的性质导出 与顶点有关的性质的一个重要工具。因为线图是一个重要的构图方法，所以也是 网络设计的一个重要方法， 设g ：( ke ) 是一个无孤立点的无向图 g 的线图，记为三( g ) ，是这样一个 无向图：y ( 三( g ) ) = f ( g ) ，对任何两条不同的边e ，f ( g ) ，e ，刀( 工( g ) ) 铮8 和 ，在g 中相邻例如，图1 , 2 所示的是无向图g 和它的线图二( g ) 设d ：d ( k e ) 是一个无孤立点的有向图( 可以有环) ，v = y ( d ) ，e = e ( d ) d 的线图，记为l ( d ) ，是这样一个有向图：v ( l ( d ) ) = 日( d ) ，对任何两条不同的 中国科学技术大学博士学位论文 g 图l2 ：图g 和它的线圈l ( g ) l ( g ) 有向边n b e ( d ) ，( n ，6 ) e ( l ( d ) ) 咎。和6 在d 中相邻，且。的终点是b 的起 点例如，图1 3 所示的是有向图d 和它的线图l ( d ) l ( d 口t o 观“ 图1 - 3 ：有向圈d 和它的线图l ( d ) 1 2 一些著名的网络 本节将介绍一些著名的网络，它们一般都因为具有简单的递归和高对称结构、 高容错、另外简单结构的可嵌入性、简单路由选择算法和易扩充性等许多好的性 质而被广泛利用 1 2 1 超立方体网络 超立方体网络的拓扑结构是指n 维立方体，通常记为q 。它的图论模型是一 个简单无向图q 。：( ke ) h e u r a r y 3 4 已列出它的许多等价定义，最常见的是如 驵2 一些著名的网络 下两个 1 0 ，l ，有序n 元数组( 亦称长为n 的2 元序列) v = ( ；1 5 9 2 z ，l ：z 。 o ，1 ，i = l ，2 ，n ) ； 两顶点z = x l x 2 z 。和y = y l y 2 在仉中相邻甘：lk y i l = l ，即 有且仅有一个坐标不同 2 笛卡尔乘积 利用图的笛卡尔乘积，超立方体骗按如下递归方法得到； q l = k 2 ，q n = q n 一1 q l = k 2 k 2 k 2 ，n 2 图l4 所示的是超立方体q l ， ：和仉 0 1曰2 0 1 0 。3 0 1 l 图1 4 ：超立方体q ，q ：和0 a 1 2 2 d e b r u i j n 网络 d eb r u i j n 网络是由d eb r u i j n 和g o o d 于1 9 4 6 年独立提出来的( 参见【1 6 ，3 1 ) ， 把它作为计算机互连网络的拓扑结构是由s t a n f o r d 大学的m l s c h l u m b e r g e r 博 士于1 9 7 4 年在他的博士论文( 参见 6 5 ) 中首先提出的 对于给定的整数d 2 和k 1 ，d eb r u i j n 有向图记为b ( d ，札通常定义如 下：b ( d ，k ) 的顶点集v ( b ( d ，) ) = ( 。1 。2 z 女：巍 0 ，l ，d 一1 ) ，i = 1 ，2 ， ； b ( d j ) 中以顶点2 1 2 2 z 女为起点的d 条有向边的终点为x 2 x 3 z k n ，其中n f f | ，1 ，、，d 1 ) 中国科学技术大学博士学位论文 d eb r u i j n 有向图也可以按线图的构造方法而得到对于固定的d ，用硪表 示在d 阶完全有向图的每个顶点上添加一个环后得到的有向图，则b ( d ，k ) 递归地 定义为： 口) = 簖；b ( d ，2 ) = l ( 耐) ；b ( d ，k ) = l k - i ( 砰) = l ( l 脚( 对) ) ，k 2 图1 5 所示的是d eb r u i j n 有向图b ( 2 ，1 ) ，b ( 2 ，2 ) 和b ( 2 ，3 ) 1 0 01 1 0 m k 爿m 0 0 10 1 1 图1 5 ：d eb r u i j n 有向图b ( 2 ，1 ) ，b ( 2 ，2 ) 和s ( 2 ，3 ) d eb r u i j n 无向图记为u b ( d ，) ，它是d eb r u i j n 有向图b ( d ，) 的基础图，即通 过除掉b ( d ，k ) 中边的方向，然后删除平行边和环后得到的无向图 1 2 3k a u t z 网络 k a u t z 网络是由k a u t z 于1 9 6 9 年提出来的( 参见【5 1 】) ，后来又有人独立发现了 它它和d eb r u i j n 网络一起被认为是对超立方体网络的挑战而替代成为下一代并 行计算机互连网络4 1 对于给定的整数d22 和k 1 ，k a u t z 有向图记为k ( d ，) ，通常定义如下： k ( d ， ：) 的顶点集v ( k ( d ，) ) = x l x 2 。k ：z ； o ，1 ，d ) ，x i i + l ，i = 1 ，2 ， ， ：1 ；k ( d ，) 中以顶点x l x 2 z 为起点的d 条有向边的终点为x 2 x 3 z o 其中n ( 0 ，1 ，d ) ，o x k k a u t z 有向图也可以按线图的构造方法而得到对于固定的d ，用j ，d + 1 表示 l2 一些著名的网络 7 e ( 2 ，1 ) 0 2 k 图16 ：k a u t z 有向图k ( 2 ，1 ) ，k ( 2 ，2 ) 和k ( 2 ，3 ) ( f + 1 阶完全有向图，则k ( d ，k ) 递归地定义为： k ( d ，1 ) ：e 抖l ；k ( d ，2 ) = l ( k d + 1 ) ；k ( d ，) = l k - i ( k d 十1 ) = l ( l 2 2 ( + 1 ) ) ，2 图1 6 所示的是k a u t z 有向图k ( 2 ，1 ) ，k ( 2 ，2 ) 和k ( 2 ，3 ) k a u t z 无向图记为u k ( d ，约，它是k a u t z 有向图k ( d ，缸) 的基础图，即通过除 掉k ( d ，引中边的方向，然后删除平行边后得到的无向图 1 2 4 交叉立方体网络 交叉立方体是e f e 于1 9 9 1 在文献 2 1 中提出 具体定义如下；记a = ( 0 0 ，o o ) ，( 1 0 ，1 0 ) ，( 0 1 ，i i ) ，( 1 1 ，0 1 ) ) 若( z ，) a ，则记 。”n 维交叉立方体网络，记为e q n ，是指这样的一个图，它有顶点集 y = z ：卫= 。n x 2 x l ，x d ( 0 ，1 ，1 j 札) 两顶点z ：$ 2 2 1 和y = y 儿y 2 y l 之间有边相连当且仅当存在一个j ( 1s j n 1 使得 ( 1 ) z n x j + l = y n 蛳+ 1 8中国科学技术大学博士学位论文 ( 1 q 3 g 0 4 图1 7 ：交叉立方体网络g 口3 和c q 4 ( 3 ) 如果j 是偶数，那么有鲫一1 = q 一1 ，并且 ( a ) 对每个i = ，z ，； 一，均有x 2 i ：v 2 i - 1 y 2 i 驷；一t 图1 7 所示的是交叉立方体网络c q 3 和c q 4 1 2 5 立方连通图 ，z 维立方连通图( 参见 6 0 ) ，记为c c c ( n ) 它是一个基于超立方体瓯构造出 来的无向图：用n 阶无向圈g 。替代q 。的每一个顶点，并将q 。的第维边连到 g 。的第 j 个顶点具体的说，c ( n ) 的顶点集为 v = ( z ；k ) ：z v ( q 。) ，1s ks n ) 两顶点( z ； ) 和( z 7 ；k 7 ) 有边相连铮满足下列两条件之一： ( 1 ) z = z 7 且k k i = h l ( r o o dn ) ； ( 2 ) ：= k 且z 和z 在中有k 维边相连 图1 , 8 所示的是3 维立方连通图c c c ( 3 ) c a r l s s o n ，c r u t h i r d s ，s e x t o na n dw r i g h t 9 1 证明n 维立方连通图c c c ( n ) 是 l _ 2 一些著名的网络 9 c a y l e y 图，因而是点可迁的 1 2 6 蝶形网 图1 8 ：3 维立方连通图c c c ( 3 ) n 维正则的缠绕蝶形有向图记为b ( n ) 它的顶点集为 矿= ( z o 1 x n - 1 ；f ) ：f 1 ，2 ，n ) ； 1 ，2 ，) ，i = 0 ，1 ，n 一1 ) 口( ? l ) 中以顶点( z o z l 2 j n - - 1 ；f ) 为起点的条有向边的终点为( x o x l o e x l + 2 x nl ；f + 1 ) ，其中 1 ，2 ，) 显然b a ( n ) 是阶为n a ”的强连通的正则图 ，。维2 a 正则的缠绕蝶形无向图记为矿b 幻) 它是缠绕蝶形有向图b a ( n ) 的 基础图，即通过除掉口( n ) 中边的方向，然后删除平行边后得到的无向图显然 u b ( n ) 是阶为n a “的2 a 正则的连通图 图1 9 所示的是3 维4 正则缠绕蝶形无向图u b 2 ( a ) s h a t l r o k h ia n ds z 6 k e l yf 6 7 证明了n 维正则的缠绕蝶形有向图b a ( n ) 是 c a y l e y 图，因而是点可迁的 l ( ) 中国科学技术大学博士学位论文 1 2 7s t a r 图 图1 9 ：3 维4 正则缠绕蝶形无向图u 日2 ( 3 ) n 维s t ”图，记为岛。它是一个由n ! 个顶点构成的无向图它的顶点集 顶点x 强。j ：1 的 v ( s h ) = z 1 茁2 茁。：。 1 ，2 ，礼) ，当z j 时z q ) x l x 2 。和y = y l y 2 有边相连铮 i 1 ，2 ，7 1 ) 使得玑= 甄 而当i j 时蜥= x j 图11 0 所示的是4 维s t a r 图& 。 3 2 1 4 2 3 1 4 4 3 1 2 1 3 4 2 图1 1 0 ：4 维s t a r 图s t 4 。 a k e r s 和k r i s h n a m u r t h y 【1 】证明n 维s t a r 图& 。是c a y l e y 图，因而是点可迁 1 2 些著名的网络 1 1 一 1 2 8 完全对换图 完全对换图是由l a k s h m i v a r a h a n 等在文献( 5 3 中提出 3 2 l 2 3 1 c n 图l i i ：2 维完全对换图g 乃和3 维完全对换图c b n 维的完全对换图记为g ，它是对称群岛关于子集 正。：l i 为路由选择r 在g 中的边转发指数；分别定义 ( g ) = m i n ( n ( g ，r ) ：vr 和7 r 。( g ) = m i n n ( g ，r m ) ：vj k ) 1 4 中国科学技术大学博士学位论文 为g 的边转发指数和最小路由选择边转发指数 显然，( g ) 岛( g ) ，”( g ) 墨7 1 m ( g ) 然而，等号不是一直成立的 与点转发指数一样，一个好的路由选择和好的网络也都应具有小的边转发指 数，或者边转发指数不超过网络各条边的负载量路由选择的边转发指数是受网 络负载量控制，因此边转发指数也是度量路由选择优劣的一个重要参数 2 2 点转发指数 关于点转发指数的一般性结论并不多，对于一般的图，已经有下述结果： 定理2 2 1 ( c h u n g 等 1 4 j ) 设g 是n 阶连通图，v = y 徊) ，则 ；( d g ( 础) 一1 ) 茎( g ) 曼钿( g ) ( n 1 ) ( n 一2 ) ( 2 1 ) y e vz ( 壬- y ) e v 等式f ( g ) = ( g ) = ；v 。( 水y ( 如( z ，g ) 一1 ) 成立婷存在最小路由选择 使得它对任何点的转发指数都相等 在文献f 5 7 1 中m a n o u s s a k i s 和n z a 证明了上述结论对于强连通的有向图也是 成立的 式( 21 ) 中给出的上界是可以达到的，例如星图k 1 ，1 事实上，星图是唯一 使得式( 21 ) 中上界可以达到的图 既然式( 21 ) 中上界等号成立的充分必要条件已经很清楚，那么我们将兴趣转 移到下界等号何时成立的问题上而h e y d e m a n n 等已经证明，对于类特殊的图 一c a y l e y 图，下界等号是成立的 定理2 2 2 ( h e y d e m a n n 等 3 9 】【4 4 】) 设g 是n 阶( 强) 连通c a y l e y 图，则对任 意z v ( g ) ，有 ( g ) = 。( g ) = d a ( x ，g ) 一m 一1 ) v ( g ) 在文献 2 7 中，g a u y a c q 将结果推广到对于q u a s i - c a y l e y 图也成立 定理2 2 3 ( g a u y a c q 2 7 ) 设g 是n 阶连通q u a s i c a y l e y 图，则对任意z 5 22 点转发指数1 5 矿( g ) ，有 o ( g ) = ( g ) = d c ( x ，) 一m 一1 ) y e y ( g ) 由于c a y l e y 图和q u a s i - c a y l e y 图都是点可迁图，于是h e y d e m a n n 等人提出下 面的猜想： 猜想2 2 4 ( h e y d e m a n n 等 4 4 】) 对任何点可迁图g ，存在最小路由选择r 。使 得对任意。y ( g ) ，有 ( g ) = ( g ，r 。) = d g ( 。，g ) 一( n 一1 ) v e v ( o ) 但是，在文献 7 0 中s h i m ，s i r a f i 和z e r o v n i k 给出了关于这个猜想的一个反例 图一d o d e c a h e d r o n 图这个图是点可迁的非c a y l e y 图，但是它不存在最小路由选 择使得上述猜想成立 从上面的定理2 , 2 2 和定理2 , 23 可以看出，对于ca _ y l e y 图和q u a s i c a y l e y 图， 其点转发指数都是在最小路由选择上达到注意到这一点的确是重要的，因为已 存在许多有效的求最短路由的算法，如果对于一个给定的网络，我们能证明它的 点转发指数在最小路由选择上达到，那么就大大缩小了路由的选择范围，借助于 现行的最短路算法就能快速而有效地设计出理想的路由选择来然而，图的点转 发指数并非总是在最小路由选择上达到 例如，设轮帆的中心点为。，其余顶点为0 , 1 ，2 ，3 ，4 ，5 ，选择甄的个最小( 双 向) 路由选择r 。，其中的路径定义如下： 对任何i ( i = 0 ，1 ，5 ) ，兄。( i ，i + 2 ) = ( i + 2 ，i ) = ( i ，i 十1 ，i + 2 ) ( m o d 6 ) ； 对任何i “= 0 ，1 ，2 ) ，2 k ( i ，i + 3 ) = r 。0 + 3 ，i ) = ( i ，。，i + 3 ) ( r o o d 6 ) ； 其余点对之间的路径取图中的两顶点之间的连边 于是， f ( 眠，r 。z ) = 6 ，并对任何i ( i = o ，1 ，5 ) 有f 陬，r m ，i 1 ：2 ；( 眠，) = 6 但如果我们定义w 6 的一个路由选择r 如下； r ( 2 ，5 ) = ( 2 ，l ，0 ，5 ) ，r ( a ，2 ) = ( 5 ，4 ，3 ，2 ) ，其余的同上述定义 中国科学技术大学博士学位论文 这样定义的路由选择_ r 显然不是最小的w ，6 中各点在这个路由选择咒的点转 发指数分别为： f ( ，r ，。) = 4 ，f ( 眠，r ，2 ) = ( 眠，r ，5 ) = 2 f ( 眠，r ，i ) = 3 ，对 = 0 ，l ，3 ，4 因此( w 6 ，r ) = 4 正是由于图的点转发指数并非都在最小路由选择上达到这一事实，给具有小 点转发指数的路由选择的寻找带来困难 于是c h u n g 等 1 4 开始考虑这个问题的复杂性h e y d e m a n n ，m e y e r ，o p a t r n y 和s o t t e a u 在文献 4 2 】中具体研究这个问题遵照文献【2 6 ，我们将问题写成如下 形式： 问题2 2 5 点转发指数问题( v f i ) 实例：图g 和整数 问：( g ) 曼 ? 当路由选择限制在最小路由选择和最小双向一致路由选择上时，我们把上述 问题分别定义为：最小路由选择点转发指数问题( m v f i ) 和最小双向一致路由选 择点转发指数问题( m c s v f i ) 他们在同一篇文献中得到了下面的定理： 定理2 2 6 ( h e y d e m a n n 等【4 2 】) 对于直径不小于4 的图，最小双向一致路由 选择点转发指数问题是n p 一完备的。对于直径等于2 的图，最小路由选择点转发 指数问题和最小双向一致路由选择点转发指数问题是p 问题，即存在一个多项式 时间算法解决这个问题 在文献f 6 2 中，s a a d 证明了下面的定理： 定理2 2 7 ( s a a d 6 2 ) 对于个直径至少为2 的图，点转发指数问题时n p - 完备的 从而回答了c h u n g 等提出的关于点转发指数的复杂性问题 2 3 边转发指数 1 7 2 3 边转发指数 相应于点转发指数，关于边转发指数也有同样的讨论 定理2 3 1 ( t l e y d e m a n n 等 4 4 】) 设g 是n 阶连通无向图，v = v ( g ) ，e = e ( g ) ，一i e l ，贝0 ；a g ( 。，”) s ”( g ) ”。( g ) lj 。z 3 e 。inyev 。 等式。( g ) ：”。( g ) ：；。vd g ( m ，9 ) 成立 争存在最小路由选择使得它对任 何边的转发指数都相等 对于有向图也有类似的结论： 定理2 3 2 ( m a n o u s s a k i s 和n z a 【5 7 ) 设d 是n 阶强连通有向图， v v ( d ) ，e = e ( d ) ，e = i 目 ，则 ；d d ( 训) 兰”( d ) s ( d ) 茎m 一1 ) 一2 ) + 1 。z g v 等式”( d ) = ( d ) = ；v d d ( x ，g ) 成立甘存在最小路由选择j h 使得它对 任何有向边的转发指数都相等 很可惜，对于c a y l e y 图的边转发指数，文献中没有得到类似于点转发指数的 结果于是h e y d e m a n n ，m e y e r 和s o t t e a u 【4 4 提出下面两个猜想； 猜想2 3 3 ( h e y d e m a n n 等 4 4 】) 设g = ( k e ) 是距离可迁图，则存在最小路 由选择r ，对任意”v ( a ) 有 郴一旧，同2l 南善m ，卟 并且他们通过考虑图k 2 晦，其中p 3 ，发现上面的猜想对于点可迁图甚至对于 c