（管理科学与工程专业论文）互联网络中通信模式及路由算法研究.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导卞进行的研究丁二作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 ：( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名 震爹 导师签字； 学位论文版权使用授权书 刊声取 本学位论文作者完全了解堂控有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 圭l 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 索蕾 蝴签字：1 才 签字日期：2 0 0 。t 年u 月“日 签字日期：2 0 0 3 7 年缸月细 山东师范大学硕士学位论文 摘要 随着高性能计算技术的不断创新，各种拓扑结构的互联网络，如环形、m e s h 、超立 方和星形网等也相应地得到迅速发展，互联网络对于社会的发展与进步已起到举足轻重 的作用。在互联网络中，不同的应用需要不同通信模式，如单播( u n i c a s t ) 、组播 ( m u l t i c a s t ) 、广播( b r o a d c a s t ) 等，如何高效的实现这些通信模式是一个重要的研 究课题。网络中的通信效率依赖于路由算法的效率，因此在不同拓扑结构下，研究实现 各种通信模式的路由算法具有重要的理论和现实意义。 本文的主要研究工作及创新点如下： 1 分析互联网络的研究现状，对网络中存在的诸如单播、组播、广播及选播通信模式 进行深入的理论探讨。 2 在研究超立方网络基础上，提出在局部k 一子立方体连通的超立方网络中实现广播通 信的容错路由算法。 广播通信是互联网络中最常用的通信模式之一。随着互联网络规模的日益增大，故 障节点更加频繁的出现。所以，广播容错路由已经成为互联网络研究中的重要课题。此 前已有许多学者提出了实现广播容错路由的各种算法，但目前广播容错路由的研究多数 集中于降低路由的时间复杂性，较少考虑提高网络的容错性。据作者所知，目前存在的 超立方体心中的广播容错路由算法所能容纳的坏节点数不超过0 ( n ) 。因而，本文基于 局部k 一予立方体连通性的概念，提出了在局部k 一子立方体连通的超立方体中实现广播 容错路由的算法。该算法是分布的、基于局部信息的，也就是说，网络中的每一个节点 仅需知道其邻接点的状态，而不需全局信息。该广播容错路由算法在局部k 一子立方体连 通的条件下能容纳坏节点的上界为2 ”1 - 2 ”“。因此，在容错性上该算法较之已有算法有了 很大的提高。更进一步说，它能在线性时间内构造超立方体h n 中接近最优的广播路径。 3 本文将a n y c a s t 引入到互联网络中，提出在超立方网络中实现a n y c a s t 通信的有效 算法。 a n y c a s t 是i n t c m e t 中一种新的通信模式，是l p v 6 的一个新特性。它要求数据包被 路山到具有相同h n y c a s t 地址的一组网络节点中距离用户“最近”的一个节点。通过 对a n y c a s t 的研究发现，a n y c a s t 通信的应用空阳j 非常广阔，不仅可以满足大量地理位 置分散的用户的需要，而且在互联网络中也有着重要的应用。因而，本文将a n y c a s t 引 山东师范夫学硕士学位论文 入到互联网络中，提出在超立方网络中实现a n y c a s t 通信的有效算法，并对该算法的效 率进行了分析，结果表明在超立方互联网络中只需o ( 3 n 2 k + 2 ) 个时间步即可实现a n y c a s t 通信。并且，通过模拟实验分析了在超立方互联网络中实现a n y c a s t 通信时链路缓冲区 数与丢包率间的关系，为互联网络的规划设计提供了理论指导；同时，通过对比实验结 果得到，在超立方互联网络中引入a n y c a s t 通信能够有效地提高网络性能。 4 将a n y e a s t 通信引入光互联网络，在光r p ( k ) 网络中设计了实现a n y c a s t 通信模式的算 法。 在互联网络中，不同通信模式路由算法的好坏直接影响到整个网络的效率。所以， 研究互联网络中实现各通信模式的路由算法是研究互联网络的重要环节。而光互联网络 因其隐含巨大的带宽容量，成为网络发展的必然趋势。基于前面的分析，在光r p ( k ) 互 联网络中设计了实现上述多种通信模式的算法，将a n y c a s t 通信引入光互联网络。 5 提出将f f t 通信模式嵌入环形光网络的算法。并在此基础上，在光r p ( k ) i n 络中设 计了实现f f t 的算法，同时也进一步分析了光r p ( k ) 网络的性能。 关键字：互联网络、通信模式、容错广播、选播、路由算法 中图法分类号：t p 3 9 3 ： 山东师范大学硕士学位论文 a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fh i 曲一p e r f o r m a n c et e c h n o l o g y , t h ei n t e r c o n n e c t i o nn e t w o r k s o fd i f f e r e n t t o p o l o g i e s ，s u c h a s t r e e ，r i n g ，m e s h ，h y p e r c u b ea n ds t a r n e t w o r ke t c ，a r e d e v e l o p e dr a p i d l y , t h ei n t e r c o n n e c t i o nn e t w o r k sh a v ea l r e a d yp l a y e dav e r yi m p o r t a n tr o l et o t h ed e v e l o p m e n to ft h es o c i e t y i ni n t e r c o n n e c t i o nn e t w o r k sd i f f e r e n ta p p l i c a t i o n sn e e d d i f f e r e n tc o m m u n i c a t i o nm o d e s ，s u c ha su n i c a s t ，m u l t i c a s t ，b r o a d c a s ta n da n y c a s t h o wt o r e a l i z es u c hc o m m u n i c a t i o nm o d e se f f i c i e n t l yi sa ni m p o r t a n ts u b j e c tf o rr e s e a r c h t h e c o m m u n i c a t i o ne f f i c i e n c yi nt h en e t w o r kd e p e n d so nt h ee f f i c i e n c yo fr o u t i n ga l g o r i t h m ，s o s t u d yo nr o u t i n ga l g o r i t h m so fd i f f e r e n tc o m m u n i c a t i o nm o d e su n d e rd i f f e r e n tt o p o l o g i e sh a s i m p o r t a n tt h e o r e t i c a la n dr e a l i s t i cs i g n i f i c a n c e t h em a i nr e s e a r c hw o r ka n di n n o v a t e so ft h i sp a p e ra r ea sf o l l o w s ： 1 a n a l y z et h e s t a t eo fc u r r e n tr e s e a r c hi nt h ei n t e r c o n n e c t i o nn e t w o r k sa n ds t u d y c o m m u n i c a t i o nm o d e si nt h en e t w o r k sd e e p l y , s u c ha su n i c a s t ，m u l t i c a s t ，b r o a d c a s ta n d a l l y c a s t 2 b a s eo nt h es t u d yo ft h eh y p e r c u b en e t w o r k s ，a ne f f i c e n tb r o a d c a s tr o u t i n ga l g o r i t h mw i t h f a u l t t o l e r a n c eo nl o c a l l yk - 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 si sd e v e l o p e d b r o a d c a s tc o m m u n i c a t i o ni so n eo ft h em o s tf r e q u e n t l yu s e dc o m m u n i c a t i o nm o d e si n t h ei n t e r c o n n e c t i o nn e t w o r k s w i t hc o n t i n u o u si n c r e a s e si nn e t w o r ks i z e ，m o r ea n dm o r e n o d e sa r ef a u l t y s ob r o a d c a s tr o u t i n gw i t hf a u l t t o l e r a n c eh a sa l r e a d yb e c o m ea ni m p o r t a n t s u b j e c ti nt h ei n t e r c o n n e c t i o nn e t w o r k s al o to fs c h o l a r sh a v ep r o p o s e dv a r i o u sa l g o r i t h m s f o rt h eb r o a d c a s tr o u t i n gw i t hf a i n t - t o l e r a n c e b u tm o s tr e s e a r c h e sc o n c e n t r a t eo nr e d u c i n g t h et i m ec o m p l e x i t ya n di ti sl e s sl i k e l yt oc o n s i d e rr a i s i n gt h ea b l i t yo ff a u l tt o l e r a n c ef o rt h e h nn e t w o r k t ot h ea u t h o r sk n o w l e d g e ，t h e r eh a sn o tb e e na n yd e v e l o p m e n to fe f f i c i e n t b r o a d c a s tr o u t i n ga l g o r i t h m sf o rh y p e r c u b et h a ta l l o w st h en u m b e ro ff a u l t yn o d e st ob el a r g e r t h a no ( n ) t h i st h e s i sp r o p o s e sa ne f f i c i e n tb r o a d c a s tr o u t i n ga l g o r i t h mw i t hf a u l t - t o l e r a n c e o nl o c a l l yk - 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 ，b a s e do nt h ec o n c e p t i o no fl o c a l l y k - s u b c u b e c o n n e c t e dh y p e r c u b e t h i sa l g o r i t h mi sd i s t r i b u t e da n dl o c a l - i n f o r m a t i o n - b a s e di n t h es e n s et h a te a c hn o d ei nt h en e t w o r kk n o w so n l yi t s n e i g h b o r s s t a t u sa n dn og l o b a l i n f o r m a t i o no ft h en e t w o r ki sr e q u i r e db yt h ea l g o r i t h m i tc a nt o l e r a n tt h eu p p e rb o u n d 2 - 12 “f o rf a u l t yn o d e su n d e rt h ec o n d i t i o no fl o c a l l yk - s u b c u h e - c o n n e c t e dh y p e r c u b e t h i s i sam u c hl a r g e rb o u n do nt h en u m b e ro ff a u l t yn o d e sc o m p a r e dt ot h ep r e v i o u sb r o a d c a s t a l g o r i t h m s m o r eo v e r ，t h i sa l g o r i t h mc a nc o n s t r u c tb r o a d c a s t i n gp a t h so fn e a r l yo p t i m a l l e n g t hi naf a u l t yh y p e r c u b eh ni nl i n e a rt i m e 3 山东师范大学硕士学位论文 3 i n t r o d u c ea n y c a s ti n t ot h ei n t e r c o n n e e t i o nn e t w o r k sa n dp r o p o s ea ne f f e c t i v ea l g o r i t h mt o i m p l e m e n tt h ea n y c a s tc o m m u n i c a t i o n i naf a m i l i a ri n t e r c o n n e c t i o nn e t w o r k h y p e r c u b e a n y c a s t i san e wc o m m u n i c a t i o nm o d ei nt h en e t w o r k s i ti san e wc h a r a c t e r i s t i co fi p v 6 a n a n y c a s tm e s s a g ei st h eo n e t h a ts h o u l db ed e l i v e r e dt ot h e n e a r e s t m e m b e ri nag r o u po f d e s i g n a t e dr e c i p i e n t s t h r o u g ht h es t u d yo fa n y c a s t ，i tc a nb ef i n dt h a ta n y c a s th a sn u m e r o u s p o t e n t i a la p p l i c a t i o n sa n d i tn o to n l yh a st h ea b i l i t yt om e e tt h ed e m a n d so fal a r g en u m b e ro f g e o g r a p h i c a l l yw i d es p r e a du s e r sb u ta l s oh a si m p o r t a n ta p p l i c a t i o n si nt h ei n t e r c o n n e c t i o n n e t w o r k s s o ，t h i sp a p e ri n t r o d u c e sa u y c a s ti n t ot h ei n t e r c o n n e c t i o nn e t w o r k s a ne f f e c t i v e a l g o r i t h mw a sp r o p o s e d t o i m p l e m e n tt h ea n y c a s tc o m m u n i c a t i o ni nh y p e r c u b e t h e e f f i c i e n c yo ft h ea l g o r i t h mi sa n a l y z e d i tn e e d so ( 3 n - 2 k + 2 ) s t e p st oi m p l e m e n ta n y c a s t c o m m u n i c a t i o n b ys i m u l a t i v ee x p e r i m e n t ，t h er e l a t i o n s h i pb e t w e e nt h en u m b e ro fl i n kb u f f e r a n dt h er a t i oo fl o s i n gd a t ap a c k e t st oi m p l e m e n ta n y c a s ti nh y p e r c u b ei so b t a i n e d i tw i l l p r o v i d et h et h e o r e t i c a lg u i d a n c ef o rd e s i g n i n gi n t e r c o n n e c t i o nn e t w o r k s a tt h es a m et i m e ， t h r o u g hc o m p a r i n gt h er e s u l to fs i m u l a t i o n s ，i ti s o b t a i n e dt h a ti n t r o d u c i n ga n y c a s ti n t oh y p e r c u b ew i l l i m p r o v et h ep e r f o r m a n c e o ft h en e t w o r k 4 i n t r o d u c ea n y c a s tt ot h eo p t i c a li n t e r c o n n e c t i o nn e t w o r k sa n dd e s i g na na l g o r i t h mt or e a l i z e a n y c a s tc o m m u n i c a t i o nm o d e i no p t i c a lr p ( 1 【) n e t w o r k t h eq u a l i t yo ft h er o u t ea l g o r i t h mu n d e rd i f f e r e n tc o m m u n i c a t i o nm o d ed i r e c t l y i n f l u e n c e st h ee f f i c i e n c yo ft h ew h o l en e t w o r k s o ，s t u d yt h er o u t ea l g o r i t h mo fe a c h c o m m u n i c a t i o nm o d ei nt h ei n t e r c o n n e c t i o nn e t w o r k si si m p o r t a n tt os t u d yt h en e t w o r k s s i n c et h eo p t i c a ln e t w o r k sh a v ee n o r m o u sp o t e n t i a lc a p a c i t yo fb a n d w i d t h ，i tb e c o m e st h e i n e x o r a b l et r e n do fn e t w o r kd e v e l o p m e n t s o ，b a s e do nt h ea b o v e m e n t i o n e da n a l y s i s ，t h i s p a p e rd e s i g na l g o r i t h m st o r e a l i z ev a r i o u sk i n d so fc o m m u n i c a t i o nm o d e si no p t i c a lr p ( k ) n e t w o r k ，a n di ti n t r o d u c e sa n y c a s tt ot h eo p t i c a li n t e r c o n n e c t i o nn e t w o r k s 5 p r o p o s ea na l g o r i t h mt oe m b e d f f rc o m m u n i c a t i o nm o d ei n t ot h eo p t i c a lr i n gn e t w o r k a n do nt h e b a s i so fi t ，t h ep e r f o r m a n c eo fo p t i c a lr p ( k ) i sf u r t h e rr e s e a r c h e dt h r o u g hd e s i g n i n ga l g o r i t h m t or e a l i z ef f to ni t i n d e xt e r m s - - i n t e r c o n n e c t i o nn e t w o r k s ，c o m m u n i c a t i o nm o d e ，b r o a d c a s t i n gw i t hf a u l t y t o l e r a n c e ，a n y c a s t ，r o u t ea l g o r i t h m c i a s s i f i e a t i o n t p 3 9 3 ： 4 山东师范大学硕士学位论文 第一章互联网络概述 1 1 什么是互联网络? 到目前为止，人们从未停止过对更高计算能力的追求。尽管从1 9 8 0 年到1 9 9 6 年， 处理器的性能大约每3 年翻一番，但软件复杂度、应用的规模和解决方案的质量仍不断 推动着处理器向更快的速度发展【1 1 。在国防、太空、汽车制造业和科学领域已经出现了 大量具有巨大挑战性的应用问题，它们要求计算机具有每秒钟万亿次级浮点运算 ( t e r a f l o p s ) ，甚至更高级别的计算能力。 2 0 世纪9 0 年代以来，并行计算已经成为计算技术的一个至关重要的组成部分。具 有多处理器的并行计算机为实现高性能计算提供了解决方案，以满足对计算能力曰益增 长的要求。即使对计算能力要求并不高的应用，多处理机也是一种划算的解决方案。由 于处理器设计上的复杂和成本的提高，设计更高性能的处理器无论从经济上还是从技术 上是不划算的。一种可行的方法就是使用商品化部件( 处理器、存储器、磁盘、互联网 络等) 来组建并行计算机。 而改善并行计算机性能的关键问题是设计高性能的互联网络。因此互联网络的设计 就变得尤为重要了。目前较为常见的高性能网络，如m y r i n e t 2 1 ，n c u b e 2 f 3 1 ，i n t e lp a r a g o n 4 1 ， c r a yt 3 d 1 5 】，t h i n k i n gm a c h i n e sc o r p c m 5 t6 1 ，n e cc e n j u 3 17 1 ，i b ms p 2 8 】等。 那么，究竟什么是互联网络呢? 并行机的互联网络是一种由开关元件按一定的拓扑 结构和控制形式构成的网络。其任务是实现从任何源节点向任何目的节点传输信息，支 持用以实现编程模型的网络事务处理吼它必须以尽可能小的延迟完成这个任务，并允 许大量这样的传输并发地发生。 互联网络的模型可以表示为一个三元组( n ，m ，c ) ，如图1 1 所示。 n 表示输入端数；m 表示输出端数；c 表示连接能力，即网络能同时实现连接的最 大数目； ? 。、 输 入 二山 斯呵 r j 控制机制 f ：= = = = = = = 烈一j 图1 1 互联网络的模型 输 出 端 山东师范大学硕士学位论文 我们可以将并行机互联网络形式化的描述成个图，这里顶点v 是由通信通道 c v v 连接的处理主机或交换机单元。通道是主机或交换机单元之间的一条物理链 路，包括保存传送数据的缓冲器。典型情况下，主机与单个交换机相连，但也可以与多 个独立的通道连接。消息沿网络中的一条路径从源主机传输到目的主机，该路径由一系 列通道和交换机组成。 互联网络应用十分广泛，小到超大规模集成电路( v l s i ) 内部总线，大到计算机广 域网【。互联网络的应用主要包括底板总线和系统域网络、电话交换机、异步传输模式 ( a t m ) 和网际协议( i p ) 交换机内部网络。同时还包括向量超级计算机处理器，存储器 互连、多计算机和分布共享主存多处理器系统互联网络、工作站和个人计算机集群、局 域网、城域网、广域计算机网以及工业应用网络等。互联网络的应用还在不断增长，例 如：汽车集中控制系统就需要个网络把多个微处理器和外设连接起来。正因为多计算 机互联网络可以应用于绝大多数分布共享主存多处理器系统、局域网和系统域网，所以 对互联网络进行研究具有重要的理论和现实意义。 1 2 互联网络的特性 互联网络的特征由其拓扑结构、路由算法、交换策略和流控机制所刻画。 扬铲舒杓是网络图的物理互连结构，它可以是规则的，如二维的网格，也可以 是非规则的。大多数并行机采用高度规则的网络。通常我们区别直接或间接网 络：直罄网磐使主机与每一个交换机连接，而廊蜜忍努中主机仅与特定的交换 机子集相连，这一子集形成了网络的边沿。许多机器使用混合的策略，所以更 重要的是要区别两类节点：主祝可以产生和吸收流量，而芟攒祝仅仅传递经过 的流量。 够曲靠弦泱定了消息在网络中沿哪一条路径传输。路由算法把可能的路径集合 限制为较小的合法路径集。存在许多不同的路由算法，提供不同的保证和各异 的性能折中。在并行机中我们仅关心主机到主机的路径。 芟旗蔗嗒决定了消息中的数据如何穿越它的路径。有两种基本的交换策略：电 路交换策略和数据包交换策略。辔劈变攒笫璐中，在源主机和目的主机之间建 立一条路径并一直保持到消息通过电路为止。j 瑟旃自交换将消息分割成系列 数据包。数据包包含路由、序列信息和数据。数据包被逐个从原丰机传递到目 的主机。数据包交换允许我们更好的利崩网络资源，因为链路和缓冲器只有在 数据包通过时j 被占用。 山东师范大学硕十学位论文 墒拦扔励抉定消息或消息的一部分何时在它的路径上运动。当两个或更多的消 息试图同时使用同一网络资源( 如一个通道) 时特别需要流控。可以让其中某 个数据流原地暂停，或令其分流进入缓冲器，或迂回到另一条路径，或简单地 丢弃它。每一种选择都对交换机的设计提出特殊的要求，并影响到通信子系统 的其它方面。 1 3 互联网络拓扑结构 研究通信网络和通信算法是设计高性能并行和分布式计算机系统的关键【1 0 1 。在过去 的几十年中，大量工作集中于发现有效的拓扑为潜在的通信网络结构服务。导致诸如环、 m e s h 1 ”、超立方【1 2 1 、星形图【”1 等拓扑的设计和分析。对于一个好的网络设计的重要要 求是，对不同通信任务所提出的有效算法应具有可用性。 可见，对于并行处理或分布式系统来说，互联网络的设计是极为重要的f 1 4 】。分布式 系统的通信性能很大程度上是由所选择的网络拓扑结构决定的。 网络的拓扑结构是抛开网络物理连接来讨论网络系统的连接形式，网络中各站点相 互连接的方法和形式称为网络拓扑( n e t w o r k t o p o l o g y ) 。拓扑图给出网络服务器、工作 站的网络配置和相互间的连接，它的结构主要有总线结构、环形结构、星型结构、树型 结构、m e s h 结构、超立方结构等。什么是最好的拓扑取决于设备的类型和用户的需求。 一种在某环境中表现很好的拓扑结构照搬到另一环境中，也许其表现就变差了。 为讨论方便，介绍以下定义： 定义1 1 射入或射出一个节点的边数称为苇点发( n o d e d e g r e e ) 。在单向网络中入射 和出射边之和称为节点麦， 定义1 2 网络中任伺两个节点之闻的最长距离，即最大路径数。豫为两络直径( n e t w o r k d i a m e t e rj 。 定义1 3 将嘲络对分各半昕必须移去的最少边数稼为对韵宽度( b i s e c t i o nv e z d t h ) ， 互联网络可分为静态网络与动态网络两类，本部分将分别予以介绍： 1 3 1 静态网络 1 ) 一维线性阵列( 1 - dl i n e a r a r r a y ) 一维线性阵列是并行机中最简单、最基本的互连方式，其中每个节点只与其左、右 近邻相连，故也叫二近邻连接。如图1 2 所示，用n 一1 条边将n 个节点串接，网络规模 n ，内节点度为2 ，直径为n 1 ，去掉一条链路就分割了网络，因此它的对剖宽度为1 。 任何连续的节点段都是具有与整个网络相同拓扑结构的子网。此网络中的路由是简单 山东师范大学硕士学位论文 的，因为在任何一对节点之间只有一条路径。也正是由于在一对节点之间存在惟一的路 径，该网络显然不提供容错能力。一维线性阵列可扩展性好但可靠性差，只要网络上一 个节点发生故障，就会导致整个网络瘫痪。 o c 卜0 0 o 一o 图1 2 一维线性阵列 2 ) 环形拓扑结构( r i n gt o p o l o g y ) 环形结构由网络中若干节点通过点到点的链路首尾相连形成一个闭合的环，即将一 维线性阵列的两端简单连接就形成了环( 如图1 3 所示) ，这种结构使每一个节点只能和 它的一个或两个相邻节点直接通信。要与其它节点通信，信息必须依次经过两者之间的 每一个节点。环形网络可以是单向的，也可以是双向的。其节点度恒为2 ，对剖宽度为 2 ，网络规模为n 。 环形结构具有如下特点：对于单向环，信息流在网中是沿固定方向流动的，两节点 间仅有一条路径，故简化了路径选择的控制；硬件复杂度低；当环中节点过多时，信息 传输速率低；节点更多的时间被用于替其它节点转发数据；环路是封闭的，不便于扩充： 可靠性差；维护难，对分支节点故障定位较难。尽管环形结构有上述诸多缺点，但因其 简单易行国内外许多多处理机系统采用环形拓扑结构，如f d d i ，s c i 等。 亡二二二三j 图1 3 环形结构 3 ) m e s h 拓扑结构 m e s h f n j 网络是研究的较早，并且现在仍然是最为重要和最有吸引力的网络模型之 一。因其结构简单、规则及良好的可扩展性且易于v l s i 的实现，m e s h 网络不仅成为许 多理论研究的基础模型，也是许多大型多处理器并行计算机系统所采用的拓扑结构。在 众多的m e s h 网络模型中，较为有用且最为流行的是二维m e s h ( 2 - dm e s h ) 网络，因此 国内外许多多处理机系统采用该拓扑结构，如i n t e lp a r a g o n 4 i 、s t a n f o r dd a s h 1 5 1 、 t o u c h s t o n ed e l t a 1 6 i 、s y m u l t2 0 1 0 ”1 和国内的曙光系列。 2 dm e s h 在一个| v 的二维网络中，每个节点只与其上、下、左、右的近邻 相连( 边界点除外) ，敝也称四近邻连接，如图1 4 ( a ) 所示。在m e s h 结构中，用- - 维坐 标( x ，y ) 来标识其节点，若两个节点相邻，则它们的坐标值只有一位不同且差值为1 ， 称这样的两个节点为邻接点。不难得到，该刚络的节点度为4 ，网络直径为2 ( j v - i ) ， 对剖宽度为。 如果在垂直方向上带环绕，而水甲方向呈蛇状，则2 - dm e s h 就变成l l l i a cm e s h ， 山东师范大学硕士学位论文 如图1 4 ( b ) 所示，此时节点度恒为4 ，n n i 抬n 4 - ；1 ，对剖宽度为2 万。如果2 - d m e s h 的垂直和水平方向均带环绕，则它就变成2 - d 环绕( 2 dt o r u s ) ，如图1 4 ( c ) 所示，其节 点度恒 2 万。 也吣 _ 由 m 1 图1 4 四近邻连接 0 ) 2 d 网孔；( b ) i l l i a c 网孔：( c ) 2 - d 环绕 4 ) 星形拓扑结构( s t a rt o p o l o g y ) 星形结构1 1 3 】是指每一个远程节点都通过一条单独的通信线路，直接与中心节点连 接。即中心节点与每一个远程节点之间都是采用点一点连接方式，中心节点是其它节点 唯一的中继节点，如图1 5 ( b ) 所示，这种结构使用中心节点与网络中其它节点通信， 采用集中控制的方式，因此又称为集中式网络。一个需要通信的设备把数据传输给中心 节点，然后中心节点再把数据送往目标节点。 星形结构具有如下特点：a ) 功能高度集中。整个网络的处理和控制功能，都高度 地集中在中心节点，这样的系统容易构造、便于管理，但存在着潜在的不可靠性。中心 节点易成为系统的“瓶颈”，且一旦中心节点出现故障将直接导致整个系统的崩溃：b ) 网络延迟小，传输误差低；c ) 单信息流通路径。每个终端通常只有一条信息通路到达 中心节点，反之亦然。因而，不存在路径选择问题，但无疑也是影响网络可靠性的一个 因素：d ) 线路利用率低。每条线路只连接一台终端，使该线路利用不充分：e ) 可扩充 性差。星形网络受硬件和软件功能的限制，致使其可扩充性差、成本高、资源共享能力 也较差。目前，有许多应用采用该拓扑结构，如l a n ，a t m 。 5 ) 树形拓扑结构( t r e et o p o l o g y ) 在实际构造一个较大型的网络时，往往采用多级星形网络，将多级星形网络按层次 方式排列，即可形成树形网络。网络的最高层是中央处理机，最低层是终端，而其它层 次可以是多路转换器、集中器或计算机。树形结构是分级的集中控制式网络，与星形结 构相比，它的通信线路总长度短，成本较低，树可划分为子树，宵点易于扩充，寻找路 径比较方便，多个终端共享一条通信线路，线路利用率较高。但在任何一对节点间存在 惟一的路径，凼此，不存在容错能力，即除r 叶节点及其相连的线路外，任意节点或其 山东师范大学硕士学位论文 相连的线路故障都会使系统受到影响。树的一个优点在于它能很容易地支持一个节点对 多个节点的广播和组播通信。 树形结构中最常见的是二叉树，它除了根节点和叶节点之外每个内节点只与其父节 点和两个子节点相连，故也称为三近邻连接。如图1 5 ( a ) 所示，显然节点度为3 ，对剖 宽度为1 ，直径为2 ( p o g 卜1 ) ( n 为树的总节点数) 。为了减小直径，可使用x - 树， 将同级的兄弟彼此相连。如果尽量增大节点度为n 1 ，则直径缩小为2 ，此时就变成了 如图1 5 c o ) 所示的星形网络，其对剖宽度为l 2l 。 j 传统二叉树的主要问题是根易成为通信瓶颈i ”】。1 9 8 5 年l e i s e r s o n 1 9 1 提出的胖树( f a t t r e e ) 可缓解此问题。如图1 5 ( c ) 所示，胖树节点间的通路自叶向根逐渐变宽，它更像 真实的树，连向根部的枝权变得愈来愈粗。 ( c ) 图1 。5 树形连接 ( a ) 二叉树；( b ) 星形连接：( c ) 二叉胖树 6 ) 超立方拓扑结构( h y p e r c u b e ) 一个n 维超立方网络包含2 “个节点，并且每个节点与f 1 条边相连。每一节点用唯一 的y 1 位_ 进制地址来标识，两个节点是瓦连的当且仪当它们的二进制地址中仅有一位不 同。超立方是一种高度并行、容错能力极强、具有递归结构的网络拓扑。它具有优良的 拓扑特性如，对称性、高连通性、容错性等。同时，许多其它类型的拓扑，如环、m e s h 、 树等在多数应用中都能有效的嵌入到超立方网络中 2 0 】。 由_ 十：超立方拓扑的这些优势，在并行计算领域，它被广泛用于构建多处理机系统 ( m p s ) 组成的高性能计算平台 2 1 l ，是并行计算理论研究的基础网络结构。因而对基于超 立方互联刚络的路由研究一直都没有间断m2 2 删i 。超市方测络已成为并行计算机通信 系统中最受青睐的互联网络之一。 山东师范大学硕士学位论文 同时超立方拓扑结构还常用来设计不同的商用多处理机系统。许多商用系统如 c o n n e c t i o nm a c h i n e ，n c u b e ，a n di p s c i 弘2 5 + 2 6 】都采用超立方作为其根本的网络拓扑。如 图1 6 所示是一个4 维超立方网络。 图1 64 维超立方网络 7 ) 全连接拓扑结构 在全连接拓扑结构中，每一对设备问都有直接的连接，如图1 7 所示。 图1 7 全连接 这是种极端的方案。由于不再需要竞争公用线路，通信变得非常简单。任意两台 设备可以直接通信，通信速度快。然而，每一对设备直接连接必然使费用增加、灵活性 较差，如n 个节点的全互连网络，若增加一个节点，则必须增加n 条线路。而且。肯定 有很多连接得不到充分利用。如果两台设备间很少通信，那么它们之间的物理线路的利 用率就相当低。一个更经济的解决方案就是不让这两台设备直接连接，去掉这些低效率 的通信线路。只有每个站点都要频繁发送信息时才使用这种方法。它的安装也复杂，但 系统可靠性高，容错能力强。 1 3 2 动态网络 1 ) 总线( b u s ) 总线结构是指各工作站和服务器均挂在一条总线上，各工作站地位平等，无中心节 点控制，公用总线上的信息多以基带形式串行传递，其传递方向总是从发送信息的节点 开始向两端扩散，如同广播电台发射的信息一样，因此又称广播式网络，如图1 8 所示。 各节点在接收信息时都进行地址检查，看是否与自己的工作站地址相符，相符则接收陔 信息。 总线型结构的特点是，结构简单，可扩充性好；当需要增加节点时，只需要在总线 上增加一个分支接门便可与分支节点相连，当总线负载不允许时还可以扩充总线；使用 山东师范大学硕士学位论文 的电缆少 难。 且安装容易；使用的设备相对简单，可靠性高；维护难，分支节点故障查找 2 ) 交叉开关 交叉开关网络允许系统中任意处理器连接到其他处理器或存储器，这样多个处理器 可以同时进行通信而不会冲突。只要请求的输入端口和输出端口空闲，任何时间都可以 建立一个新的连接。交叉开关网络可用于高性能小规模的多处理器系统设计、直接网络 路由器设计和大规模间接网络基本部件的设计。交叉开关可以定义为具有n 个输入和m 个输出的开关网络，允许m i n n ，m ，个无冲突的一对一连接。图1 , 9 给出了一个n m 的交叉开关网络。除了交叉开关连接处理器和存储器模块外，通常情况下n - m 。 n 个 输 入 开关点 m 个输出 图1 9 交叉开关网络 对于具有分布式控制的交叉开关，每个开关点可以包含4 种状态，如图1 1 0 所示。 在图1 1 0 ( a ) 中通过开关点的行输入允许访问相应的输出，而从上面发出的、访问同 一输出的输入请求被阻塞。在图1 1 0 ( b ) 中，上面发出的输入请求允许访问输出，通 过开关点的行输入不请求同一输出并可以传向其他的开关。在图1 1 0 ( c ) 中，从上面 发出的输入请求允许访问相应的输出，但是通过开关点的行输入也请求同一输出，所以 被阻塞。图1 1 0 ( d ) 所示的状态只用于要求交叉开关支持组播的情形。 奇母呻串 ( a )( b )( c ) ( d ) 图1 1 0 开关点的4 种状态 v l s i 的发展允许几千个丌关集成到一个芯片