（通信与信息系统专业论文）k元n方的高维交换结构和多播研究.pdf

摘要 摘要 在因特网快速发展的今天，宽带视频、多媒体等业务对路由器技术提出了史 高的要求，快速增长的网络流量也要求交换容量不断升级。k 元以方交换结构由于 其灵活的扩展性，已成为构建大容量可扩展路由器的常用选择。 一方面，采用多维交换结构建分布式的大容量交换网络是分组交换技术的发 展趋势。比较相同拓扑类型、不同维度的多维交换结构，一般情况下，高维的结 构在吞吐率、交换延迟等性能指标上具有天生的优势。如果交换节点总数( 即交 换结构规模) 固定不变，维度高意味着每维节点数少，节点连接度高，从而交换 结构的直径更小，对分带宽更大。直径小有利于减小交换延迟，而对分带宽大有 利于提高吞吐率，因为多维交换结构理论上能达到的交换能力与其对分带宽成正 比。 但是高维度也会带来成本上与技术上的问题。维度高意味着每个节点的连接度 高，从而需要更多的互连通道及节点缓存。这直接增加了交换结构的实现成本， 同时加大了交换节点上的缓存管理、调度、控制信息传输与处理等模块的难度， 不利于节点实现。而且由于互连通道数随着节点数的增加而快速增大，使得其可 扩展性受到限制。因为受限于复杂互连的可实现性限制等，所以今后的研究方向 之一是采用光介质来连接多维交换结构。 另一方面，面对视频会议、计算机协同工作等新业务的快速增长，多播通信 的应用越来越广泛，相对传统的点到点通信方式，多播不仅能够节约大量的网络 带宽，而且可以提高工作效率。随着对多播性能要求的不断增加，多播应用逐渐 从应用层向网络结构的下层延伸，在交换和路由层上实现多播已经成为当前国内 外研究的热点。 k 元n 方中的多播既可以通过软件，也可以依靠硬件的支持得以实现。但硬件 开销会增加系统的设计成本和实现的复杂度，并会降低路由硬件的速度。同时， 现有的尼元n 方实现系统大多只支持点对点的单播路由。因此，利用现有的单播技 术在软件层面上实现多播是目前和今后很长一段时间内的很好的选择。 针对以上问题，对现有的软件多播算法做出了改进；设计了以单播路由为基 础的多播路由算法：k m p a m r ( k m e s hp a r t i t i o n - b a s e da d a p t i v em u l t i c a s tr o u t i n g ) 算法；搭建了k 元，z 方交换结构的通用仿真模型，采用面向策略的设计模式为不同 i 摘要 的路由算法提供了通用的访问接口，并对算法性能进行了分析和讨论。实验表明， 本文提出的两种算法能够取得较好的性能。 首先，本文从k 元，z 方交换结构、死锁问题、虫孔交换、路由算法和虚通道流 控制几个角度出发，介绍了本文研究的背景知识。接着描述了构建多维交换结构 需要注意的问题和介绍了多播的前景。 其次，介绍了多维交换结构的研究背景，并对不同维数的拓扑结构进行了仿 真。分析了由维数引起的t o r u s 交换结构性能和复杂度上的变化。 再次，本文在分析已有的软件多播算法的基础上，提出一种针对并发多播业 务设计的多播路由算法：k m p a m r 算法。k m p a m r 算法具有更为灵活的分区方 式，通过增大多播的并行性和路由的灵活性来改善多播性能。仿真表明，k m p a m r 算法在负载较低的情况下能取得较高的吞吐率和较低的延迟，但会加速交换结构 “过饱和”现象的出现。一旦出现“过饱和”，交换结构的性能( 特别是吞吐率) 会急剧 下降。 最后，为了考察多维交换结构和k m p a m r 算法的性能，我们在o p n e t 平台 下搭建了基于虫孔交换和虚通道流控制的k 元玎方交换结构的通用仿真模型，采用 面向策略的设计模式，为不同的路由算法提供了通用的访问接口。此外，本文还 结合对仿真结果的讨论，提出了开展下一步研究的参考性建议。 关键词：k 元n 方交换结构，高维，多播，k m p a m r 算法 i i a b s 仃a c t a b s t r a c t c o n f r o n t e dw i t ht h ee x p l o s i o n o fc o m m u n i c a t i o nt r a f f i ci ni n t e m e t ，t h e a p p l i c a t i o n s o fb r o a d b a n dv i d e oa n dm u l t i m e d i ar e q u i r er o u t e r s t op r o v i d eb e t t e r s e r v i c e sa n dan e ws w i t c hf a b r i ci sn e e d e dt oc o n s t a n t l ym e e tt h er e q u i r e m e n to f i n c r e a s i n gc a p a c i t y 昕坊t h ef l e x i b l es c a l a b i l i t ya n dl a r g ec a p a c i t y , k - a r yn - c u b e s w i t c h i n gf a b r i ci sb e i n gw i d e l yu s e dt oc o n s t r u c th i 曲s p e e d t e r a b i tr o u t e r s o nt h eo n eh a n d ，i tw o u l db ead e v e l o pt r e n do fp a c k e ts w i t c ht e c h n o l o g yt ob u i l d d i s t r i b u t e d ，v a s tc a p a c i t ys w i t c hn e t w o r k sw i t hm u l t i d i m e n s i o ns w i t c hf a b r i c s u n d e r t h ec o n d i t i o nt h a tt h et o p o l o g i e sa r es a m e ，i ng e n e r a l ，h i g h d i m e n s i o n a lt o m sn e t w o r k s h a v es o m ei n h e r e n ta d v a n t a g e si np e r f o r m a n c ei n d e x e ss u c ha st h r o u g h p u t ，s w i t c hd e l a y , a n ds oo n h i 曲d i m e n s i o ni m p l i e sf e wn o d e si ne a c hd i m e n s i o n ，s h o r td i a m e t e ra n d w i d eb i s e c t i o nb a n d w i d t hi ft h et o t a ln u m b e ro fs w i t c hn o d e s ( t h es i z eo fs w i t c h t o p o l o g y ) i sf i x e d s h o r td i a m e t e ri s b e n e f i c i a lt od e c r e a s es w i t c hd e l a y , a n dw i d e b i s e c t i o nb a n d w i d t hi sh e l p f u lt oi n c r e a s et h r o u g h p u ta s t h es w i t c hc a p a c i t y o f m u l t i d i m e n s i o ns w i t c hf a b r i ca n db i s e c t i o nb a n d w i d t hh a st h ed i r e c tr a t i ot h e o r e t i c a l l y b u t ，h i g h - d i m e n s i o n a l s oi n c u r st h ep r o b l e m so fc o s ta n dt e c h n o l o g y h i g h e r - d i m e n s i o ni m p l i e sm o r en o d ed e g r e e ，s ot h e r e m u s tb em o r ei n t e r c o n n e c t c h a n n e l sa n dn o d et e m p o r a r ym e m o r y t h a td i r e c t l ya d d st h ec o s to fs w i t c hf a b r i c ，a n d i n c r e a s e sa r c h i t e c t u r a lc o m p l e x i t yi nm a n a g i n gt e m p o r a r y , s c h e d u l i n ga n dc o n t r o l l i n g i n f o r m a t i o nt r a n s p o r ta n dh a n d l e t h eh i g h e r - d i m e n s i o ns w i t c hf a b r i c s p o t e n t i a lo f s c a l a b l ei sr e s t r i c t e d ，b e c a u s et h et o t a ln u m b e ro fi n t e r c o n n e c t i o nc h a n n e l si n c r e a s e s f l e e t l yw h i l et h en u m b e ro f n o d e sa d d s 。 o nt h eo t h e rh a n d ，t om e e tt h ed e v e l o p m e n to fn e ws e r v i c e s ，s u c ha sv i d e o c o n f e r e n c ea n dc o o p e r a t i v ec o m p u t i n ge t c ，t h et r a d i t i o n a lp o i n tt op o i n tc o m m u n i c a t i o n w o u l db er e p l a c e db ym u l t i c a s tc o m m u n i c a t i o n n o to n l ym u l t i c a s tc a ns a v ev a s t c o m m u n i c a t i o nb a n d w i d t h , b u ta l s oi ti m p r o v e st h ew o r k i n ge f f i c i e n c yo ft e r m i n a l e q u i p m e n t a l o n gw i t ht h ef a s tg r o w i n go fp e r f o r m a n c er e q u i r e m e n t ，m u l t i c a s t i s e x t e n d i n gf r o ma p p l i c a t i o nl a y e rt ol o w e rl a y e r so fn e t w o r ka r c h i t e c t u r e s t h e r e f o r e ， s u p p o r t i n gm u l t i c a s ti nh i 曲s p e e ds w i t c ha n dr o u t e r sb e c o m e s ah o ti s s u ef o rr e s e a r c h i i i a l t h o u g hm u l t i c a s tc a l lb ei m p l e m e n t e di ne i t h e rs o f t w a r eo rh a r d w a r e ，a d d i n g h a r d w a r es u p p o r tf o ri tw i l li n c r e a s ec o s ta n dc o m p l e x i t y , p o s s i b l ys l o w i n gd o w nt h e r o u t i n gs p e e d f u r t h e r m o r e ，m o s te x i s t i n gw o r m h o l e s w i t c h e ds y s t e m so n l ys u p p o r t u n i c a s ti nh a r d w a r e h e n c e ，m u l t i c a s ts h o u l db ei m p l e m e n t e di ns o f t w a r ei ns u c h s y s t e m sb ys e n d i n gm u l t i p l eu n i c a s tm e s s a g e s ，a n dt h e r e f o r ei ss u i t a b l ef o rc l 】r r e n ta n d f u t u r es y s t e m s t oa d d r e s st h ea b o v ei s s u e s ，w ee n h a n c et h ee x i s t e n ts o f t w a r em u l t i c a s ta l g o r i t h m a n d p r o p o s ean o v e ls o f t w a r em u l t i c a s ta l g o r i t h m , k m p a m r ( k - m e s hp a r t i t i o n - b a s e d a d a p t i v em u l t i c a s tr o u t i n g ) a l g o r i t h m ，w h i c ha r eb a s e do nt m i c a s t r o u t i n ga n d a p p l i c a b l ef o rm u l t i p l em u l t i c a s t s a n dt h i st h e s i sa l s oi n t r o d u c e st h eg e n e r a lm o d e lf o r s i m u l a t i o n , p r o v i d e sac o n - u l l o ni n t e r f a c e f o rd i f f e r e n tr o u t i n ga l g o r i t h m sw i t ht h e s t r a t e g yd e s i g np a t t e r n , a n da l s od i s c u s s e st h es i m u l a t i o nr e s u l t s s i m u l a t i o nr e s u l t s s h o wt h a tt h ep r o p o s ea l g o r i t h mc a np e r f o r m k - a r yn c u b es w i t c h i n gf a b r i c e f f i c i e n tm u l t i p l em u l t i c a s to p e r a t i o n si n f i r s t ，t h i st h e s i si n t r o d u c e st h eb a s i cr e s e a r c hb a c k g r o u n d sa b o u tk a r yn c u b e s w i t c h i n gf a b r i c ，s u c ha st o p o l o g y , d e a d l o c kp r o b l e m ，w o r m h o l es w i t c h i n ga n dv i r t u a l c h a n n e lf l o wc o n t r 0 1 t h e n , s o m ei s s u e sa b o u tb u i l d i n gm u l t i d i m e n s i o ns w i t c ha 1 1 dm e p r o s p e c to fm u l t i c a s tr e s e a r c hi nk a r yn - c u b es w i t c h i n gf a b r i ci sd e s c r i b e d s e c o n d ，t h er e s e a r c hb a c k g r o u n do fm u l t i d i m e n s i o ns w i t c hf a b r i ch a sb e e n i n t r o d u c e d a n dw eh a v ed o n es o m es i m u l a t i o ni n t h e t o p o l o g i e sw i t hd i f f e r e n t d i m e n s i o n s ，t h e nt h ee f f e c to fd i m e n s i o no np e r f o r m a n c ea n dc o m p l e x i t yh a sb e e n s t u d i e d t h i r d ，b a s e do np r o b l e ma n a l y s i s ，t h i st h e s i sp r o p o s e san o v e la l g o r i t h m s ： k m p a m r ( k - m e s hp a r t i t i o n - b a s e da d a p t i v em u l t i c a s tr o u t i n g ) a l g o r i t h m k m p a m r c a na c h i e v eh i g hd e g r e eo fp a r a l l e l i s mb yd i v i d i n gt h en e t w o r ki n t os e v e r a ls e p a r a t e d b l o c k sd y n a m i c a l l ya n ds e n d i n gm e s s a g ec o p i e s c o n c u r r e n t l yi ne a c hb l o c k b y a p p l y i n ga d a p t i v eu n i c a s ts c h e m e ，k m p a m rc a nd e c r e a s et h ed e l a yc a u s e db yc h a n n e l c o n t e n t i o n s i m u l a t i o nr e s u l t ss h o wt h a tk m p a m ra c h i e v e sg o o dp e r f o r m a n c eu n d e r l o wa p p l i e dl o a d h o w e v e r , k m p a m rm i g h ta c c e l e r a t et h es w i t c h i n gf a b r i cr e a c h i n g s a t u r a t i o n p o i n ta n dr e s u l ti nb e y o n ds a t u r a t i o n b e y o n ds a t u r a t i o nc o u l dc a u s e c o n s i d e r a b l yd e g r a d e do np e r f o r m a n c e f i n a l l y , a g e n e r a l s i m u l a t i o nm o d e li sb u i l tt ot e s tt h e p e r f o r m a n c eo f i v a b s t r a c t m u l t i d i m e n s i o ns w i t c hf a b r i ca n dt h ep r o p o s e da l g o r i t h m ，a n dp r o v i d e sac o m m o n i n t e r f a c ef o rd i f f e r e n tr o u t i n ga l g o r i t h m sw i t ht h es t r a t e g yd e s i g np a t t e r n f u r t h e r m o r e ， s i m u l a t i o nr e s u l t sa r es h o w na n dd i s c u s s e d s o m ei m p r o v e m e n t sa n df u t u r e 、o r k sa r e a l s ob ep r o p o s e d k e y w o r d s ：k - a r yn c u b es w i t c h i n gf a b r i c ，h i g h - d i m e n s i o n ，m u l t i c a s t ，k m p a m r a l g o r i t h m v 图目录 图目录 图1 1 互连网络分类4 图1 2 ( a ) 4 x 3 x 3m e s h 结构( b ) 4 x 3 x 2t o r u s 结构5 图1 3 ( c ) 2 元4 方h y p e r c u b e 结构6 图1 4 交换结构的拓扑图6 图1 5 三种交换方式的对比7 图1 - 6 物理通道空闲但分组b 阻塞8 图1 7 两种通道组织方式的对比8 图1 8 通道死锁9 图1 - 9 路由算法的分类1 0 图1 1 0 * - c h a n n e l 自适应路由算法的路由示例1 2 图2 - 12 5 6 个节点的t o t u s 网络吞吐率，1 6 x 1 6 ，8 x 8 x 4 和4 x 4 x 4 x 4 ，路由算法= 牢c h a n n e l 1 9 图2 22 5 6 个节点的t o t u s 网络平均f l i t 延：1 6 x 1 6 ，8 x 8 x 4 和4 x 4 x 4 x 4 ，路由算法 ：= = ：宰c h a n n e l 2 0 图2 3 表2 1 大小为2 5 6 ，5 7 6 和1 2 7 6 的t o r u s 网络的互连导线数和节点度2 0 图3 13 个目的节点的多播通信模式2 2 图3 2 多播路由中的消息阻塞2 4 图3 3 二维交换结构中的多播树路由死锁2 5 图3 4m 个目的节点采用全目的地址编码2 7 图3 5 软件多播示例2 8 图3 - 6 逻辑多播树2 9 图4 18 x 8 x 8 的三维t o r u s 结构的坐标平面及分区情况3 4 图4 2k m p a m r 算法流程图3 6 图4 3p m a r 算法和k m p a m r 算法分离多播域后的路由线路和软件多播树的比较 3 9 图4 4 二维结构交换节点的多端口结构示意图4 0 图4 5 确定性路由与自适应路由的对比4 1 图4 6 不同负载量下的多播平均延时4 2 图4 7 不同负载量下的吞吐率4 3 图4 8 不同负载量下的虚通道预约成功率4 4 图5 1 分层结构图4 7 图5 2 用面向策略的设计模式实现可访问不同多播路由算法的统一接口5 0 图5 38 x 8 x 8 三维交换结构5 0 图5 44 x 4 x 4 x 4 四维交换结构5 1 图5 5 交换节点工作流程图5 2 图5 - 6 交换节点示意图5 3 v i 图目录 图5 7 源模块状态转换图5 4 图5 8 注入模块状态转换图5 5 图5 - 9 交换模块状态转换图5 6 图5 1 0 路由与仲裁模块状态转换图5 7 图5 11 接受模块状态转换图5 8 i x 缩略词表 m p p d i n p s f d o r 缩略词表 m a s s i v e l yp a r a l l e lp r o c e s s o r大型并行处理器 d i r e c ti n t e r c o n n e c t i o nn e t w o r k直接互连网络 p a c k e ts w i t c h i n gf a b r i c d i m e n s i o no r d e rr o u t i n g 分组交换结构 维序路由 k m e s hk x km e s h ( p a r t i t i o n )k x km e s h 分区 k 口a 嗄r e m a i s l 口 k - m e s hp a r t i t i o n b a s e da d a p t i v em u l t i c a s t 基于k m e s h 分区的自适 r o u t i n g应多播路由 e x t e r n a lm o d e la c c e s s外部模块接入 i t e r a t i v er o u n dr o b i n m a t c h i n gw i t hs l i p 使用s l i p 的迭代轮询 匹配 k - a r yn - - c u b e k a r r a yn c u b e l c m s t n r p a m r q o s r o c s a f v c w f q l i n kc o n t r o l e r m i n i m a ls p a n n i n gt r e e n e a r e s t n o d er o o t e d p a r t i t i o n - b a s e da d a p t i v em u l t i c a s tr o u t i n g q u a l i t yo fs e r v i c e k 元n 方 链路控制器 最小生成树 最近节点优先 基于分区的自适应多播 路由 服务质量 r a n d o mo d e rc h a i n随机序列链 s t o r ea n df o r w a r d v i r t u a lc h a n n e l w e i g h t e df a i rq u e u e i n g x 存储转发 虚通道 加权公平排队 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 日期：圳i ! 年万月f 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：韭置导师签名：蛔 日期：h 毽年f 月歹e l 第一章绪论 第一章绪论 采用多维交换结构构建分布式的大容量交换网络是分组交换技术的发展趋 势。比较相同拓扑类型、不同维度的多维交换结构，一般情况下，高维的结构在 吞吐率、交换延迟等性能指标上具有天生的优势。如果交换节点总数( 即交换结 构规模) 固定不变，维度高意味着每维节点数少，节点连接度高，从而交换结构 的直径更小，对分带宽更大。直径小有利于减小交换延迟，而对分带宽大有利于 提高吞吐率，因为多维交换结构理论上能达到的交换能力与其对分带宽成正比。 但是高维度也会带来成本上与技术上的问题。维度高意味着每个节点的连接度 高，从而需要更多的互连通道及节点缓存。这直接增加了交换结构的实现成本， 同时加大了交换节点上的缓存管理、调度、控制信息传输与处理等模块的难度， 不利于节点实现。而且由于互连通道数随着节点数的增加而快速增大，使得其可 扩展性受到限制。 网络业务的爆炸式增长促进了通信技术和计算机技术的迅速发展，人们对通 信带宽的需求不断提高，同时对i n t e r n e t 的服务内容和服务质量也提出了更高的要 求。为了适应网络流量和传输带宽的增长速度，大容量交换技术面临着新的挑战。 此外，面对视频会议、计算机协同工作等新业务的快速增长，多播应用发展得越 来越快，相对传统的点到点通信方式，多播通信不仅能够节约大量的网络带宽， 而且还可以提高设备终端的工作效率。随着对多播性能的不断增加，多播应用正 逐渐从应用层向网络结构的下层延伸，在交换和路由上实现多播已经成为当前国 内外研究的持续热点的【1 】【2 】。 1 1k 元n 方交换结构概述 线卡通过物理链路直接互连构成直接互连结构，因此直接互连结构中各个节点 是对等的。在本文的后续部分中，用来实现节点间互连的设备为物理链路或者物 理通道。从节点处理的不同业务类型，可以把节点分成两个功能模块：本地处理 模块和互连模块。前者负责处理到达本节点的和从外部输入端口进入的业务。互 连模块则负责非本地业务，即转发到相邻节点的业务和接收从相邻节点发到本节 点的业务。 电子科技大学硕士学位论文 在m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) 应用中互连模块连接的是处理器和存储器 【4 9 】【5 0 】【5 1 1 ( s w i t c hf a b r i c ) 应用中连接的是各个输入输出端e l ( f a b r i cp o r t ) ，端口又通 过线卡( l i n ec a r d ) 连接到路由器的外部输入输出接口。由于在实现时通常把互连 模块功能直接放在线卡上来实现，所以在本文后续部分提到所有交换单元和节点， 如没有特别说明，都是为一个具有互连模块的线卡。 分组交换是有别于电路交换的一种交换技术。在本文中，如无特别说明，我 们所提到的交换都指的是分组交换。分组交换节点中核心的器件是交换矩阵( 又称 为交换结构) ，本文的研究工作就是在一种被称为k 元n 方的交换结构中展开的【3 1 。 下面，我们将介绍k 元n 方的发展和研究情况，为后续章节的进一步展开做好铺 垫。 当前骨干路由器所存在的问题是促使业界研究新的骨干路由器技术的一个重 要原因。这些问题主要表现在扩展性、可靠性、维护性等方面： 系统扩展代价高：带宽需求的增长要求服务供应商不断地扩展其骨干路由 器设备的容量，往往是新的设备更新完成，便开始计划下一次升级方案。 采用当前的骨干路由器，系统的扩展大多需要通过很复杂的方式来完成， 如将多个路由器互连来模拟一个大容量的路由器工作。 系统可靠性低：目前的路由器尚无法提供很高的可靠性保证，网络运营商 不得不在网络层进行复杂的冗余设计以提高系统可靠性，如大量网络设备 的冗余配置。 维护复杂：当采用多个路由器互连来提供大容量的路由交换时，系统的复 杂化直接导致了维护的复杂化。因为需要对这样的路由器进行单独配置和 维护，所以导致维护成本激增。 所有这些问题都是传统路由器所采用的交换结构技术难以解决的，需要采用 新的设计思想和结构。 互连网络具有很高的并行处理特性和极好的扩展性，因而其应用十分广泛，主 要包括大规模集成电路底板总线和系统域网络，以及超级计算机处理器存储器互 连、多计算机和分布式共享主存多处理器系统互连网络，工作站和个人计算机集 群等。当前，随着网络业务的持续快速增长，对交换性能的要求也不断提高，在 交换结构领域也越来越多的考虑采用互连技术来实现高速、易扩展的路由器【3 】【5 1 。 k 元n 方是互连网络中的一个子类，如图1 - 1 给出了互连网络的一种分类方案。其 中，直接网络( d i r e c tn e t w o r k ) 与间接网络( i n d i r e c tn e t w o r k ) 是交换结构研究关注的 重点：前者每个节点内部集成了路由交换模块，各节点通过一个或多个独立的路 2 第一章绪论 由交换模块，各节点通过一个或多个独立的路由交换模块连接在一起。本文关注 的k 元n 方就是直接网络中的代表。直接网络主要由三个要素来描述：拓扑、交 换和路由【6 】。因此本节后面的内容将围绕k 元1 1 方的这三个要素来展开。因为k 元 n 方的概念来源于互连网络，而被用于构建交换结构，k 元n 方交换结构也就是一 种交换网络，所以在本文的后续章节中我们不在严格区分”交换结构”和”交换网络” 这两个概念。 随着互连的交换节点个数增加，各个节点对间的距离增加，即分组在传送时 需要经过更多的中间节点。为减少节点个数增加造成的距离增加，通常一个节点 与多个节点互连，从而构成一种多维的拓扑结构，称为多高维互连网络。在本文 中称这类利用高维互联网络构建的k 元1 1 方交换结构为高维k 元n 方交换结构。 在研究高维结构之前，首先在本节分别介绍，分析几种常见的结构拓扑、交换技 术与结构内部业务流的控制方式。 3 电子科技大学硕士学位论文 fll-2。维；盛m。es。h。、(i。nte1p ，一a w r a 孔g o u n u ) e ) l 悱董一三 l 混合网络 拓扑结构 满足以下条件的立方结构被称为k 元n 方：它们具有n 个维度空间，在每个维 度上有k 个节点。对一个n 维网络，设第i 维度上共有色个节点，岛2 ， 4 第一章绪论 f = o ，l ，2 ，n - 1 ，则有：全网共有k o xk , 乞颤一，个节点；节点x 可以用n 维向 量( 吒一。( 功，吒一2 ) ，吒( x ) ，q ( x ) ，( x ) ) 来表示，其中0 呒( x ) 红一1 。 如果一个n 维网络是一个k 元以方，那么对于网络中任意两节点x 和y ，有以 下命题成立： 当x 与y 相邻，对所有f ，f = o ，1 ，2 ，n l ，i j ，有q o ) = q ( y ) ，其中 仃，( x ) = c r j ( y ) lm o d 后，。 对所有维度f ，都有忍= k ，即每一维度上的节点数都为k 个。 图1 2 b ) , 1 1 图1 - 2 ( c ) 分别给出了两种k 元n 方结构。k 元n 方还可以从另一个角 度来定义：在一些文献中【6 1 ，图1 2 ( b ) 的结构又被称为t o m s 结构，而图1 2 ( c ) 则被 称为h y p e r c u b e 结构。k 元n 方实际是k 元，z 维t o m s ( k 2 ) 和n 维h y p e r c u b e 的总称， 即k 元n 方是： h r y 址 ：凳臻= 是 k 元n 方结构上的一个显著特征是：任意节点在任意维度上均具有两个相邻节 点，故共有2 ，z 个邻居，亦即k 元n 方结构具有全网对称性。这样的结构既增大了 路由选择的灵活性，也更有利于实现业务量的负载均衡【7 1 。本文的研究工作将主要 围绕t o m s 结构展开。 w r a p a r o u n dc h a n n e l 图1 - 2 ( a ) 4 x 3 x 3m e s h 结构 ( b ) 4 x 3 x 2t o m s 结构 5 电子科技大学硕士学位论文 z 坐标系 图1 - 3 ( c ) 2 元4 方h y p e r c u b e 结构 图1 - 4 交换结构的拓扑图 x 值得一提的是如图1 - 2 ( a ) 所示的m e s h 结构。t o m s 结构的定义中由于有取模运 算，因而比m e s h 结构有更多的边。这些边通常称为环绕边( w r a p a r o u n dc h a n n e l ) 。 对比m e s h 和t o r u s 结构可以发现：它们的主要区别在于t o r u s 结构是全网对称的， 而m e s h 结构是中心对称的。我们可以通过去掉t o r u s 结构中的一部分连接，把全 网对称的t o r u s 结构转变为中心对称的m e s h 结构。 虫孔交换 虫孔交换( w o r m h o l es w i t c h i n g ) 首先由d a l l y 和s e i t z t s 提出，用来解决交换结 构中传输延迟太大的问题。在采用虫孔交换的交换结构中，进入交换结构每个分 组源节点被切分成若干个f l i t ，其中n i t 的长度由系统参数决定。每个p a c k e t 的第 一个f l i t 是h e a d e rf l i t ，它包含了路由信息，其他n i t 仅包含原p a c k e t 中的数据， 没有路由信息，称为b o d yf l i t ( 最后一个b o d yf l i t 也称为t a i lf l i t ) 。当h e a d e rf l i t 沿 着一定的路径传送后，同一个p a c k e t 中的b o d yf l i t s 就沿着h e a d e rf l i t 走过的路径， 以隧道方式( p i p e l i n e ) 个接着一个依次传送，类似于一个火车头带着整列火车前 进。在传送时如果h e a d e rf l i t 被阻塞，则同一个p a c k e t 中的其他f l i t 分别在当前 节点存储，见图1 5 。这样在每个节点上的缓存只需要存储f l i t ，不需要存储整个 p a c k e t ，从而大大降低了对缓存空间的要求。 虫孔交换的提出，成功解决了一直困扰k 元n 方交换结构的两个重要问题。其 一，降低了节点对缓存容量的需求。交换结构中每个交换节点上的缓存只需存储 f l i t ，而不需要存储整个数据分组，这就大大降低了对节点缓存空间的要求；其二， 更为重要的一点是：使用虫孔交换，在不发生阻塞的情况下，传输延迟几乎与路 由经过的跳数无关。 6 第一章绪论 lii i l 头部 数据 。l 盯l ( 拄) 节点 s n l n 2 n 3 ( b ) 间 节点 三种交换疗式的埘比：( a ) 分组交换；( b ) | 毪蹈交换；( e 擞孔变换 图1 5 三种交换方式的对比 阀 闯 虚通道流控制 提出虚通道流控n t 9 是出于优化资源分配的目的，多维交换结构的吞吐量限制 在其容量的2 0 - - - 5 0 。交换结构的资源主要包括两类：缓存和通道。一般来说， 每个通道对应了一个缓存，具体地讲，只要分组a 分配了缓存x ，别的分组就不能 使用缓存x 对应的通道，直到分组a 释放工。在使用f l i t 级流控制的网络中，分组 a 在持有工的时候因为网络中别的地方发生拥塞而阻塞。在这种情况下，即使网络 中还有别的分组，通道也会被闲置