（计算机系统结构专业论文）三级clos网的优化及阻塞概率的研究.pdf

摘要 摘要 三级c l o s 网络是采用基本交换单元来搭建大型交换网络的最常用拓扑结 构。三级c l o s 网能在置换、- - n 多播送、多源点多播等多种通信方式中实现严 格、广义和可重排无阻塞播送，可以很好地满足大规模交换网络的设计要求。 因此，研究三级c l o s 网的优化设计以及阻塞概率分析在理论和实际上都有非常 重要的意义。 论文围绕三级c l o s 网硬件代价的降低和统一的阻塞概率分析模型的建立的 问题，开展了以下研究工作： 针对严格无阻塞的多播三级c l o s 网的硬件代价比较大的问题，提出了对其 进行优化的办法。利用对网络总的硬件代价求微分的方法，得到使得网络硬件 代价最小所满足的条件及优化后的网络硬件代价。通过分析和比较发现，严格 无阻塞的多播三级c l o s 网优化后可以有效的降低网络的硬件代价。 针对三级c l o s 网目前已有的概率分析模型只是单一的单播或者多播模型的 问题，提出了利用h w a n g 的统一方法和p a t t a v i n a 的阻塞概率分析模型结合的办 法，建立了统一的阻塞概率分析模型。通过与已有的结论进行分析比较发现， 提出的统一的分析模型更准确全面的描述了多播三级c l o s 网的阻塞性能。 通过对阻塞概率与硬件代价的折衷比较，搭建出具有小阻塞、低代价的置 换三级c l o s 网的结构。经过分析和比较可以发现，搭建的网络的硬件代价比相 应的严格无阻塞网络降低将近一半，而阻塞概率却非常小。 提出一个基于三级c l o s 网模型的w d m 光网络的硬件代价的优化方法。根 据相应的限制条件，结合第三章已有的针对一般三级c l o s 网的优化办法，得到 了基于三级c l o s 网模型的w d m 光网络优化的方法。通过比较和分析发现，优 化方法可以有效降低基于三级c l o s 网模型的w d m 光纤网络的硬件代价。 关键词：三级c l o s 网络；多播；严格无阻塞；置换；阻塞概率；硬件代价；交 叉点；w d m 光网络 a b s t r a c t a b s t r a c t t h r e es t a g ec l o sn e t w o r ki st h em o s tc o m m o n l yu s e dn e t w o r kt o p o l o g yw h i c h u s e sb a s i cs w i t c hm o d u l e st ob u i l dl a r g e s c a l es w i t c h i n gn e t w o r k i tc a ni m p l e m e n t s t r i c t l yn o n b l o c k i n gn e t w o r k ，w i d e s e n s en o n b l o c k i n gn e t w o r ka n dr e a r r a n g e a b l e n o n b l o c k i n gn e t w o r ki ns o m ec o m m u n i c a t i o nt y p e ss u c ha sp e r m u t a t i o n ，m u l t i c a s t a n dm u l t i - s o u r c em u l t i c a s te t c s ot h r e es t a g ec l o sn e t w o r kc a nc o m m e n d a b l ym e e t d e s i g nr e q u i r e m e n t so fl a r g e - s c a l en e t w o r k t h u s ，r e s e a r c h i n go nt h eo p t i m i z a t i o n a n da n a l y s i so fb l o c k i n gp r o b a b i l i t yi nt h r e es t a g ec l o sn e t w o r kn o to n l yh a sav e r y i m p o r t a n ts i g n i f i c a n c ei nt h e o r y , b u ta l s oh a sg r e a ta p p l i c a b l ev a l u e t h er e s e a r c hw o r kp r e s e n t e di nt h ed i s s e r t a t i o ni sm a i n l yf o c u s e do nr e d u c i n g t h eh a r d w a r ec o s to ft h r e es t a g ec l o sn e t w o r ka n dc o n s t r u c t i n gt h eu n i f y i n gm o d e l o fb l o c k i n gp r o b a b i l i t y f i r s t l y , c o n s i d e r i n gt h ep r o b l e mt h a tt h eh a r d w a r ec o s to fs t r i c t l yn o n b l o c k i n g m u l t i c a s tt h r e es t a g ec l o sn e t w o r ki sr e l a t i v e l yb i g g e r , am e t h o di sp r o p o s e df o r o p t i m i z i n gi t b yc a l c u l a t i n gt h ed i f f e r e n t i a lo f t h eh a r d w a r ec o s t ，t h ec o n d i t i o n st h a t m a k em i n i m i z i n gt h eh a r d w a r ec o s ta r eo b t a i n e d t h e nt h eh a r d w a r ec o s ta f t e r o p t i m i z i n gt h en e t w o r ki sg e t t h r o u g ha n a l y z i n ga n dc o m p a r i n g ，t h eh a r d w a r ec o s t o fs t r i c t l yn o n b l o c k i n gm u l t i c a s tt h r e es t a g ec l o sn e t w o r ki se f f i c i e n t l yr e d u c e da f t e r o p t i m i z i n gt h en e t w o r k s e c o n d l y , c o n s i d e r i n gt h ep r o b l e mt h a tt h ee x i s t i n gp r o b a b i l i t ya n a l y s i sm o d e l o ft h r e es t a g ec l o sn e t w o r ki so n l yas i n g l eu n i c a s ta n dm u l t i c a s tm o d e l ，au n i f y i n g m o d e lo fb l o c k i n gp r o b a b i l i t ya n a l y s i si sp r o p o s e dw h i c hu s e sh w a n g su n i f y i n g a p p r o a c ha n dp a t t a v i n a sm e t h o d c o m p a r e dt op r e v i o u sr e s u l t st h en e w l yp r o p o s e d u n i f y i n gm o d e lc a nm o r ec o r r e c t l ya n dc o m p r e h e n s i v e l yd e s c r i b et h eb l o c k i n g b e h a v i o r o ft h em u l t i c a s tt h r e es t a g ec l o sn e t w o r k t h i r d l y , t h r o u g ht h et r a d e o f fb e t w e e nb l o c k i n gp r o b a b i l i t ya n d t h eh a r d w a r ec o s t ， t h et h r e es t a g ec l o sn e t w o r km o d e l 、i t hs m a l lb l o c k i n gp r o b a b i l i t ya n dl o w h a r d w a r ec o s ti so b t a i n e d b yt h ec o m p a r i s o n sb e t w e e nd i f f e r e n ts i z e so fn e t w o r k ，i t c a nb ec o n c l u d e dt h a tt h eh a r d w a r ec o s to ft h ed e s i g n e dn e t w o r ki sl e s sa p p r o x i m a t e 5 0 t h a nt h a to fc o r r e s p o n d i n gs t r i c t l yn o n b l o c k i n gn e t w o r kb u tt h ep r o b a b i l i t yi s v e r ys m a l l f i n a l l y , am e t h o dt oo p t i m i z eh a r d w a r ec o s to fw d mo p t i c a ln e t w o r kb a s e d o n t h r e es t a g ec l o sn e t w o r ki sp r o p o s e d a c c o r d i n gt ot h er e s t r i c t e dc o n d i t i o n ，t h e o p t i m i z a t i o nm e t h o di so b t a i n e db yt h et h i r dc h a p t e r sr e s u l t s b ya n a l y s e sa n d i i a b s t r a c t c o m p a r i s o n si ti sv a l i d a t e dt h a tt h ep r o p o s e do p t i m i z a t i o nm e t h o dc a l le f f i c i e n t l y r e d u c et h eh a r d w a r ec o s to fw d m o p t i c a ln e t w o r kb a s e do nt h r e es t a g ec l o s n e t w o r k k e yw o r d s ：t h r e es t a g ec l o sn e t w o r k ，m u l t i c a s t ，s t r i c t l yn o n b l o c k i n g ，p e r m u t a t i o n ， b l o c k i n gp r o b a b i l i t y , h a r d w a r ec o s t ，c r o s s p o i n t ，w d mo p t i c a l n e t w o r k i i i 目录 图目录 图1 1 共享介质网络【8 】3 图1 2 静态网络中结点的结构【8 】4 图1 3 路由器的一般结构i3 4 图1 4 基于开关的动态网络1 8 j 5 图1 5 一个小型的交叉开关pj 7 图1 6 交叉开关的四种状态【3 】8 图1 7 千兆开关f d d i 引8 图1 8 一般的三级n n 2 的c l o s 网f 2 5 】1 1 图1 95 级c l o s 网示意图【1 4 1 1 2 图2 1 三级c l o s 网 。，。， 示意图以及另一种表示【1 0 0 1 1 6 图2 2 交换卡内部的三级c l o sn t l 0 1 1 1 7 图2 3 交换卡内部的单路径b a n y a n 网f l o 1 7 图2 4x i l i n x 公司第二代交换模块示意图( 采用c l o s 网结构) 1 0 2 】1 8 图2 5f b - c l o s 网的拓扑结构【3 0 】。1 9 图3 13 x3 交叉开关网络，2 9 图4 1 三级c l o s 网示意图1 2 8 j 4 0 图5 1 当n = 1 0 2 4 时，在不同利用率a 下，三级c l o s 网c 1 和c 2 阻塞概率的对 比5 5 图5 2 当n = 2 0 4 8 时，在不同利用率a 下，三级c l o s 网c 1 和c 2 阻塞概率的对 比5 6 图5 3 当n = 4 0 9 6 时，在不同利用率a 下，三级c l o s 网c 1 和c 2 阻塞概率的对 e 匕5 6 图6 1 一个的w d m 互连网络( 包含k 个波长) i s 0 】6 2 图6 2 一个n k n k 的基于交叉开关网络的w d m 光网络( 包含k 个波长) 【7 9 】6 3 图6 3k 个n xn ( 包含一个波长) 组成的w d m 开关网络【。7 5 】6 4 图6 4 基于三级c l o s 网模型的w d m 光网络6 5 图6 5= 1 6 ，k = 4 时，搭建的最优的基于三级c l o s 网模型的w d m 光网络7 2 图6 6= 3 2 ，k = 8 时，搭建的最优的基于三级c l o s 网模型的w d m 光网络7 4 图6 7= 3 6 ，k = 4 时，搭建的最优的基于三级c l o s 网模型的w d m 光网络7 6 v i 目录 表目录 表1 1 静态网络性质表【】5 表3 1 当万= l 和n = 2 1 0 ，d 取不同值时，网络优化的结果以及交叉点总数g 的 取值3 6 表3 2 当艿= l 和d = 2 ，取不同值时，网络优化的结果以及交叉点总数g 的 取值3 6 表3 3 当d = 2 和n = 2 3 3 2 ，万取不同值时，网络优化的结果以及交叉点总数g 的取值3 7 表3 4 当l = = n = 3 2 ，满足，l l = 的所有解以及相应的交叉点总数g 3 7 表3 5 当m ：3 6 0 ，：9 6 ，d = 4 时满足( 3 1 3 ) 式的所有的解以及相应的交叉 点总数g 3 8 表3 6 当i ： = n = 3 6 ，d ：4 时满足( 3 1 3 ) 式的所有的解以及相应的交叉点 总数g 3 8 表4 1 四种模型下的参数结果4 9 表5 1 四种网络类型的硬件代价的对比5 7 表5 2 七种网络类型的硬件代价的对比5 8 表5 3 在不同规模和不同利用率下，网络c l 和c 2 的阻塞概率的对比5 9 表6 1 当= 3 2 ，k = 4 时，采用的三级c l o s 网的硬件代价6 8 表6 2 当= 1 6 ，k = 4 时，采用的三级c l o s 网的硬件代价7 2 表6 3 当= 3 2 ，k = 8 时，采用的三级c l o s 网的硬件代价7 4 表6 4 当= 3 6 ，k = 4 时，采用的三级c l o s 网的硬件代价7 6 v l i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：逋签字日期：丝2 ：z ! 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 9 么开口保密( 年) 作者签名：重叠 签字日期：型12 ：2 ： 聊躲丝 签字日期：2 翌阻 第1 章绪论 第1 章绪论 随着现代通信网络和多处理器系统的发展和日益复杂的通讯需求，支持并 发多播的多级互连网络已经成为计算机学科一个活跃的研究分支。多播的多级 互连网络有着广阔的应用前景【l 】，在视频会议、视频广播、网上新闻、网上学 校、高清晰度电视等领域有着巨大的应用优势。在各种多级互连网结构中，三 级c l o s 1 】网能在置换、一到多播送、多源点多播等多种通信方式中实现广义、 严格无阻塞播送和受限播送等【2 】，并且具有结构规则、低延迟、易扩展的优点， 可以很好地满足大规模交换网络的设计要求 2 1 。然而一般的严格无阻塞的三级 c l o s 网硬件代价仍然比较大【l 】，为此需要考虑对严格无阻塞的三级c l o s 网进行 合理的优化；另一方面，可以试图考虑一下有小阻塞低代价的网络，这样就需 要对三级c l o s 网建立统一的概率分析模型。因此，研究三级c l o s 网的优化设 计以及阻塞概率分析在目前已经变得非常迫切，其研究不仅在理论上有非常重 要的意义，对于下一代互连网络和多处理机内部通讯而言，也具有极大的应用 价值。 本章首先对互连网络进行了介绍，然后介绍动态互连网络，接着介绍多级 互连网的多播，之后又介绍了三级c l o s 网，最后给出论文的研究内容和组织思 路，以及论文的组织结构。 1 1 互连网络 随着计算机技术的发展，在现有制造工艺下，处理器的速度几乎达到了极限 【2 】。为了制造速度更快的计算机，只能把多个处理器连接成一个网络【2 】【3 1 。处理 器之间如何连接，对整个系统的速度有着至关重要的影响【3 1 ，因此关于互连网络 的研究成为一个热点。 互连网络越来越广泛地应用于许多不同的领域中【2 】，包括超大规模集成电路 和系统域网、电话交换网络、交换机与路由器内部的网状结构【”，同时还包括高 性能并行计算机中处理器存储器互连、片上多核的互连网络、局域网、城域网 等【3 】，并且互连网络的应用仍然在不断增长。 1 1 1 并行计算与互连网络 并行计算【4 】( p a r a l e l lc o m p u t i n g ) 是指同时使用多种计算资源解决计算问题 的过程，是目前计算机科学与技术研究的前沿。互连网络作为并行计算的主干， 它的性能对整个并行计算的性能起着决定性作用【3 1 。高性能计算【5 】就是利用并行 第1 章绪论 互连把非常多的处理器连接起来以获得非常大的计算处理能力的技术。 随着当前科学技术迅猛发展，人类对高性能计算的需求越来越大。自2 0 世 纪8 0 年代以来，计算机处理器的性能每1 8 个月翻一番【3 】，但仍不能满足基础 学科的科学计算、国防、政府部门、航空航天、石油开发仿真、汽车设计、材 料设计和生命科学等领域对高性能计算的需求【2 】【3 】【5 】。目前出现了许多具有重大 挑战性的应用问题，如全球天气预报、地震预测、动漫渲染、视频计算、网络 加速、核武器评估、生物信息学和金融模拟分析等【3 】【5 j 。这些应用问题都要求计 算机具有每秒钟万亿次( t e r a f l o p s ) 甚至千万亿次( p e t a f l o p s ) 以上的计算处理 能力【5 1 ，单个的处理器即使集成度非常高也无法达到这样的计算能力，而通过 并行互连可以把多个处理器连接起来获得更高性能的计算能力。例如，在最新 公布( 2 0 0 8 年1 1 月) 的全球运行速度最快的超级计算机5 0 0 强【6 l 排名中，排名 第一的是i b m 的b l a d ec e n t e rq s 2 2 l s 2 1 ，其峰值速度超过每秒1 0 2 6 万亿次浮 点运算，所用的处理器数多达1 2 9 ，6 0 0 个1 6 。为了有效连接这么多的处理器，获 得如此快速的计算能力，就必须设计具有高性能、低代价和低功耗的互连网络 结构和提供有效的通信模式【3 】。 互连网络在并行计算机系统中占有重要的地位【3 】1 3 1 ，在某些应用领域中，互 连网络的研究已有几十多年的历史【3 】。在最初的研究阶段，研究的重点主要集中 在拓扑结构和功能特性上【8 i ，在多计算机出现以后，大量与实现、性能有关的问 题成为研究重点。互连网络的研究内容很多，包括拓扑结构理论、硬件代价分 析、网络系统设计、路由算法、调度算法、阻塞概率的分析等【3 】【7 】。在上述的每 个方向上，都已经有大量的研究成果发表，+ 这些研究成果大大推动了多计算机 的发展和应用，然而在理论与实际上仍有大量的问题迫切需要得到解决。 1 1 2 互连网络分类 互连网络【8 】是一种由开关元件按照一定的拓扑结构和控制方式构成的网 络，以实现计算机系统内部多个处理机或多个功能部件间的相互连接【们，用 于在多计算机系统的处理节点之间或多个功能部件之间传递包含数据的消息 【8 】。互连网络有两个重要的特性【3 】：能够同时实现多个端口的互连；所有输入端 能与任意输出端互连。 互连网络在现代并行计算机中扮演者十分重要的角色，已成为并行处理系 统的核心组成部分【8 1 。已知的互连网络按照网络拓扑结构可分为四类【7 】：共享介 质网络( s h a r e d - m e d i u mn e t w o r k ) 、静态网络( s t a t i cn e t w o r k 或r o u t e r - b a s e d n e t w o r k ) 、动态网络( d y n a m i cn e t w o r k 或s w i t c h b a s e dn e t w o r k ) 和混合网络 ( h y b r i dn e t w o r k ) 。 2 第1 章绪论 ( 1 ) 共享介质网络 在共享介质网络【8 】结构中，所有的处理器( 或者通信设备) 共享传输介质， 在每一个时刻，只允许有一个处理器进行通信传输【3 】，如图l 。l 所示【8 】o 当共享 介质网络的访问产生冲突时，就需要一定的仲裁机制来决定介质总线的使用者， 因此在此网络中的关键研究问题是仲裁策略【7 1 。根据仲裁机制的不同，共享介 质网络又可分为争用总线( c o n t e n t i o nb u s ) 、令牌总线( t o k e nb u s ) 、令牌环 ( t o k e nr i n g ) 和底板总线( b a c k p l a n eb u s ) 等【3 】。 共享介质网络的优点是它具有广播的能力【3 】【引，任意时刻，网络上所有的设 备都可以监视网络的动作，同时接受共享介质上传输的信息，因此，共享介质 网络可以有效的支持广播的通信类型【8 1 。然而，由于每一次只允许一个处理器 设备进行数据传输【3 】【8 】，这样就不能充分的利用网络带宽，导致传输介质的带宽 利用率很低【3 】【7 】【8 】，因此共享介质网络不适用于大规模的系统，一般用于局域网 和处理器内部的底板通信【7 】。 i总线( b u s ) 图1 1 共享介质网络【8 】 ( 2 ) 静态网络 静态网络【8 】是指网络中的节点与节点之间的相互连接在网络运行期间保持 恒定不变，因为这类网络每个节点与其它一些节点是直接的相互连接，所以也 被称为直接网络【3 】。在静态网络中，互连网络的拓扑结构由节点之间的连接方 式所决定1 2 1 。一维线性阵列、环、2 d m e s h 、超立方、树、胖树、星形、碟形、 洗牌交换、全互连网络都是典型的静态网络【2 】【3 】【8 1 。 在静态网络中，每个节点由处理器、存储器、路由器( r o u t e r ) 和其它功能 单元【3 】组成，如图1 2 所示【引。路由器的主要功能是完成节点之间的消息传递。 路由器是静态网络的核心部件闭( 路由器的一般结构如图1 3 所示【3 】) ，它占有 重要的地位，所以在通常情况下，我们也把静态网络称为基于路由器的网络【8 】。 静态网络一般具有很强的网络功能，其中点对点的直接通道传输速率高、 易于实现【3 1 ，因而构造大规模高性能并行计算机经常采用静态网络【引。另一方面， 静态网络的拓扑结构也大都具有良好的数学特性，所以它具有实际与理论双重 第1 章绪论 的研究价值【3 1 。 其它 处理器 局部 功能单元存储器 王!工 t土内部通道 叫鼬器l ；卜 叫 卜 图1 2 静态网络中结点的结构【8 】 图1 3 路由器的一般结构【3 】 最理想的拓扑结构是全连接结构 3 1 ，它可以大大减少了通信延迟【3 】【钉。然而， 全连接结构的网络具有非常高的硬件代价【l 们，当网络规模较大时，网络的硬件 代价就会非常高，所以从性能与代价折衷的角度来看，采用全连接网络是不适 当的。另外，一个节点的物理连接的数量由于受到硬件技术的限制也不可能很 大【8 】【1 0 】【l l 】，所以从实际工程中的角度也排除了使用全连接网络的可能性。为此， 研究人员提出并研究了各种各样的网络拓扑结构【1 1 1 ，因此在实际设计中就可以 从中选取适合实际情况的网络，在性能和代价之间取得一个比较好的折衷。表 1 1 【l l 】汇总了一些静态互连网络的重要特性，其中 r 为节点数，刀为维数。 4 第l 章绪论 表1 1 静态网络性质表【1 1 l 网络名称网络规模结点度网络直径对剖宽度链路数 对称性 线性阵列个结点 2一1l一l 非 环形个结点 2 l 2 j ( 双向) 2n是 全连接个结点一l1 ( n 2 ) 2 n o n 一0 2 是 二维网孔 ( 届届) 4 2 ( 万一1 )4 n2 ( 一万) 非 i l l i a c 网孔 ( 届届) 4瓜一l2 万2 非 二维环网 ( 厢打) 4 2 i # z i 2 万2 是 二叉树个结点3 2 ( - l o g n - 一1 ) l一l 非 超立方n = 2 ”个结点 刀力n | 2n nf 2 是 立方环n = | j 2 个结点 3 2 k 1 + l k 2 j n ( 2 k ) 3 2 是 ( 3 ) 动态网络 动态网络【8 】( 也称为间接网络或基于开关的网络【3 】) 是另一类主要的互连网 络。动态网络用交换开关构成，可按应用程序的要求动态地改变连接组态嘲， 如图1 4 所示喁】。典型的动态网络包括总线网络、交叉开关网络和多级互连网络 等【2 】【3 】【8 1 。每个开关有多个端口，用来与本地节点相连，或是连接到其它的开关， 也可以闲置不用。开关的不同互连方式构成了动态网络的不同拓扑结构【7 1 。 图1 4 基于开关的动态网纠8 】 ( 4 ) 混合网络 混合网络【3 】是综合了前面三种网络的优点而构成的一种网络。与共享介质 网络相比，混合网络相应的增加了带宽和延展性【2 1 ；与静态网络或动态网络相 比，混合网络节点之间的距离更短【3 】【引。典型的混合网络有多总线【1 2 1 、超网格 ( h y p e r m e s h ) 1 1 3 】等。在超网格中，总体的节点排列利用m e s h 结构，但是在每 一维上，节点通过共享总线的形式互相连接。超网络这种结构最初是由w i t t i e h 】 第1 章绪论 提出，其最大的特点是网络直径很短，当网络规模增大时。节点间的平均距离 增加比较小，缺点是带宽的可扩展性差【1 4 】。随着光纤网络的迅速发展，混合网 络实现的可能性越来越大，已经得到人们越来越多的认可【2 】【3 】【7 1 。 1 2 动态互连网络 动态互连网络【8 】( 也称为间接网络或基于开关的网络【3 1 ) 是一类主要的互连 网络。动态互连不是静态固定连接，而是在连接路径的交叉点处放置电子开关、 路由器、集中器、分配器、仲裁器等【8 1 ，以提供动态连接。动态互连网络用交 叉开关构成，可按应用程序的要求动态地改变连接组态【8 】。每个开关有多个端 口，用来与本地节点相连，或是连接到其它的开关，也可以闲置不用。开关的 不同互连方式构成了动态网络的不同拓扑结构1 7 】。基于开关的动态网络已经发 展了很长时间，从规整的阵列处理器和共享主存u m a 多处理器【7 】到当前用于 n o w 的不规整拓扑【7 】，其中涉及了大量的拓扑结构。规整的拓扑在开关之间具 有规则的连接模式，而不规整的拓扑则没有一定的模式【3 1 。这两类拓扑可以根 据消息到达目的地的过程中必须经过的开关数目来进一步进行分类【3 】【刀。 动态网络的主要属性由三个要素来描述：拓扑、路由和交换【”。拓扑定义 了开关是如何通过通道互连的1 8 】，般可以用类似于图1 4 的模型加以描述；路 由的选择由路由算法来决定【s 】，在每一个中间节点，路由算法指出下一步要使 用的通道，该通道可以从多个可能的通道中选择。如果所有的候选通道都繁忙， 消息就被阻塞，不能再继续前进，有效的路由对互连网络的性能十分关键【3 1 【。1 ： 交换机制决定怎么给消息传输分配网络资源【8 】，它确定何时、如何将输入通道 连接到路由算法选择的输出通道上。 动态互连网络包括交叉开关( c r o s s b a r ) 网络、多级互连网络m i n ( m u l t i s t a g e i n t e r c o n n e c t i o nn e t w o r k ) 和不规则的机群网络等【3 】。其中，交叉开关网络是单 级交换网络 2 1 1 3 1 ，每个空闲端口都可以连接到任何其它空闲端口上，所以交叉开 关网络的硬件代价比较高【2 】【8 】，它主要用于高性能的小规模的多处理机系统的设 计p j ，也可以用作静态网络的路由器设计或是大模块动态网络中小的基本部件 的设计【3 】【7 】【8 】。多级互连网络则通过数级开关来动态地连接每个输入设备和输出 设备f 8 j ，其中每个开关模块就是一个小的交叉开关网络。各级开关之间不同的 连接模式构成了不同的网络，例如c l o s 网络、b a s e l i n e 网络、b a n y a n 网络、c u b e 网络和o m e g a 网络等【2 】【3 】【引。机群系统则采用高性能开关把工作站或p c 机连接 起来，构成不规则的网络【3 】。 6 第1 章绪论 1 2 1 交叉开关网络 交叉开关( c r o s s b a r ) 网络是单级交换网络【2 】【3 】，可为每个端口提供更高的 带引8 1 。在每个输入端和输出端的交叉点上都有交叉点开关，像电话交换机一 样，交叉点开关可根据需要动态的设置“开 或“关”状态，它能提供所有( 源、 目的) 对之间的动态连接【2 】【3 1 。规模为疗刀的交叉开关网络允许力对源和目的同 时不冲突的( 不会占用相同的资源) 进行通信，也允许一个输入端向多个输出 端同时发送信息【2 】【3 1 。 在并行处理中，交叉开关网络一般有两种使用方式：一种是用于高性能多 处理机系统中处理器间的通信【3 】【8 1 ；另一种是用于高性能多处理机系统中处理器 和存储器之间的存取【3 】【8 】。图1 5 1 8 】描绘了一个小型的交叉开关网络模块，其中 i n p u t 2 被连接到o u t p u t 2 、i n p u t 3 被连接到o u t p u t 4 、i n p u t 4 被连接到o u t p u t 3 ，每 一对源、目的端1 2 1 都是通过一个交叉点( c r o s s p o i n t ) 连接的。值得注意的是任 意一对空闲的源、目的端口对都可以无阻塞的进行连接。交叉开关网络的突出 优点是其交换容量大，扩展能力强口】【3 】【7 】【引，基本不受硬件条件的限制，可以实 现无阻塞通信【8 】。当交叉开关网络用在小规模共享主存多处理器中时，只要每 个处理器读、写不同的存储模块，所有的处理器就可以同时访问存储器【盯。当 两个或多个处理器请求访问同一个存储器模块时，仲裁机制【3 】会令一个处理器 访问而令其它处理器等待。交叉开关的仲裁器分布在所有连接到同一输出的开 关点上【3 】。交叉开关的仲裁机制比总线要简单，因为交叉开关中的冲突是异常 情况而不是协议规则【3 】，所以更容易解决。 i n p t 1 吣2 i 呻u t 3 i , 舭t 4 岫位5 o 位p l t l 州2哪3m p t t 4 图1 5 一个小型的交叉开关【3 】 交叉开关中的交叉点( c r o s s p o i n t ) 状态有四种，如图1 6 所示引。图1 6 ( a ) 中把从左边进来的输入改为从下面出去的输出，同时阻塞了请求同样输出的另 一个输入( 从上面进来) 。图1 6 ( b ) 中把从左边进来的输入改为从右边出去的 7 第1 章绪论 输出，同时从上面进来的输入改为从下面出去的输出。图16 ( c ) 中从上面发 出的输入改为从下面出去的输出，同时阻塞了请求同样输出的另一个输入( 从 左边进来) 。图1 6 ( d ) 中状态只用于要求交叉开关支持多播的情形。 砷串呻串 抽)m ) c )( d ) 图1 6 交叉开关的四种状态 交叉开关网络被广泛应用于实际中，图17 1 8 1 给出了d i g i t a l 公司的千兆开关 f d d l 中所设计的交叉开关。该交叉开关是为a l p h a 工作站和服务器的多个 f d d i 环之间计算机群互连而设计的娜“。使用f d d i 全双工技术( f f d t ) ，能 够连接多至2 2 个f d d i 端口，每路速度为1 0 0 m b s t ”口】。千兆开关赝d d i 能提供 高选36 g b s 的带宽( 是以太网的3 6 0 倍) ，它己用在d i g i r a l 的t r a c l u s t e r 中嗍。 千兆开关，f d d i 是一种通用的网络产品，可用于任意以f d d i 环连接的系统中嘲。 4 蚪_ 摹g 毒事革强 b c 爿臣鼍专长戳 毒轴簦：_ 錾团 啐强：臣翠 f 前 一般而言，交叉开关网络的成本为矿，其中”为端口数，其硬件代价是比 较高的i ”。但是交叉开关网络具有良好的带宽特性：并且任意两节点之间的通 信不会阻塞其它节点之间的通信2 ”。 第1 章绪论 1 2 2 多级互连网络 为了构筑大型开关网络，可将单级交叉开关网络连合起来形成多级互连网 络m i n ( m u l t i s t a g ei n t e r c o n n e c t i o n n e t w o r k ) ，它已经被用在m i m d 和s i m d 计 算机设计中【引。多级互连网络通过一定级数的开关连接输入和输出设备，每一 个开关模块都是一个交叉开关网络，每级都使用多个开关模块，而相邻级间的 开关使用固定的级间连接【2 】【8 】。为了在输入和输出之间建立需要的连接模式，交 换开关可动态设置为“开 或“关 状态。 多级互连网络最初是为电话网提出的，后来用于阵列处理机【3 】。在这些情 况下，由中央控制器建立从输入到输出的路径。其中单播通信模式可以用输入 地址的排列来表示【3 1 。另一方面，在异步多处理器系统中，集中控制和排列路 由是不可行的【8 1 。在这种情况下，需要路由算法建立多级互连网络的跨级路径。 一般而言，r 刀多级互连网络能实现刀! 置换连接【引。不同类型的多级互连 网络，其开关模块和使用的级间连接i s c 7 1 ( i n t e r s t a g ec o n n e c t i o n ) 方式也有所 不同。常用的级间连接方式包括均匀洗牌、蝶网、多路均匀洗牌、交叉开关、 立方连接等【2 】【3 】【引。 多级互连网络通过数级开关网络来动态地连接每个输入设备和输出设备 【3 1 ，各级开关网络之间不同的连接模式构成了不同的网络，例如c l o s 网络、 b a s e l i n e 网络、b a n y a n 网络、c u b e 网络和o m e g a 网络等【2 】【3 】【引。 1 3 多级互连网的多播 多播是把信息从一个消息源传输到多个目的地的过程【1 5 】，它的使用策略是 高效的【1 6 】，因为消息在每条网络链路上只需传递一次，而且只有在链路分叉的 时，消息才会被复制，所以说多播是高效网络的一个必要条件【l5 1 。多播作为一 点对多点的通信，是节省网络带宽的有效方法之一【1 5 】。在网络音频视频 广播的应用中，当需要将一个节点的信号传送到多个节点时，无论是采用 重复点对点通信方式，还是采用广播方式，都会严重浪费网络带宽【l 引，只 有多播才是最好的选择。多播能使一个或多个多播源只把数据包发送给特 定的多播组，而只有加入该多播组的主机才能接收到数据包。目前，多播 通讯模型已经广泛地应用在很多场合，例如：网络音频视频广播、信息网络 的视频点播服务、网络音频( 或视频) 会议、多媒体远程教育、“p u s h ”技术 ( 如股票行情等) 和虚拟现实游戏、矩阵乘法、分布式数据库的记录更新等 等【1 6 】【1 7 】【1 8 】。而多播操作是宽带综合业务数字网和多计算机中一个非常重要的通 信操作【他】。在给定的多播模式下，一个网络的多播能力被定义为在此网络中能 实现的多播指派的个数t 1 3 】。 9 第l 章绪论 随着网络技术的飞速发展以及v l s i 工艺的日益提高，新型路由器通常采 用网络处理器n p ( n e t w o r kp r o c e s s o r ) 和交换模块( s w i t c hf a b r i c ) 芯片结合的方式 来构建【8 1 ，其中多播主要是通过交换模块芯片部分来实现的 3 1 。由于新一代网络 处理器一般都具有并行处理能力，所以路由器可以同时处理多个多播请求，并且 能够适应不同速率等级的网络应用【”】，满足日益复杂多样的网络业务需求。目 前，在新一代路由器和交换机的内部交换模块通常采用支持多播操作的多级互 连网络来高速率低代价地实现多播、并发多播【1 5 】【1 6 】，因此支持多播操作的多级 互连网络将变成未来通信的关键环节，直接影响新一代网络的性能【1 6 之0 1 。 将任一输入单元的输入端连向任一输出单元的输出端时，有的多级互连网 络会产生阻塞，有的则不会产生阻塞。对于产生阻塞的多级互连网络，有的可 以通过重新调整现有的连接而避免阻塞，有的不能。因此，根据阻塞情况的不 同可以对多播的多级互连网络进行如下分类【l5 】： 严格无阻塞多播网络：当一个新的多播连接请求到达时，不需要对已有的 连接进行任何改动就可以为新请求提供连接链路。 广义无阻塞多播网络：当一个新的多播连接请求到达时，不需要对已有的 连接进行任何改动，但是需要采用一定的路由策略来为新的多播连接请求安排 链路。 可重排无阻塞多播网络：当一个新的多播连接请求到达时，往往需要对网 络中现有的所有连接重新安排新的通信链路。 目前正处于研究热潮中的多播技术可以有效地利用现有的带宽，很好地支 持视频会议、视频广播、网上新闻、网上学校、高清晰度电视这些新的应用需 求f 1 5 1 3 】。此外在进行气象预报、地震预测、金融分析、石油仿真等高性能计算 的大规模并行处理机系统中【4 】【5 】，在处理机技术、存储技术、i o 技术等方面 i s 】【1 5 1 ，为了高效地进行数据传输和信息通讯，解决大规模并行处理机系统性能的 瓶颈，也需要并发多播技术【1 6 2 们。随着光纤网络( 具有巨大的带宽资源和优异的 传输特性) 技术的成熟，多播可以更好的应用在以光纤网络为主干的互连网络 中。因此，并发多播技术无论是对于下一代网络通讯，还是对并行处理机系统 内部的通讯，均具有重要的研究意义。目前有很多文献【2 m 5 】都对互连网络中的 多播进行了相关研究和探讨。 1 4 三级c l o s 网 一般的三级j v i m 的c l o s 网模型如图1 8 所示口5 1 ，其中输入级由吒个，l i 所 的开关组成，中间级由m 个1 吃的开关组成，输出级由，