（通信与信息系统专业论文）可伸展多级分组交换网络结构的研究.pdf

摘要 捅妥 为了适应通信业务流量与同俱增的需要，当前的路由器和交换机工程实践强 调交换网络具有可扩展性。解决可扩展性有两种基本途经：一种是提升单级交换 单元的交换容量，但是由于工程实现的限制，单级交换单元的交换容最不可能 比 大；另一种途径是采用由多个交换单元构成连接网络的方法来实现一个更大规筷 的交换网络，这是目前可扩展交换网络最常用的解决方案。当前大型交换网络的 连接网络拓扑主要采用多级网络，其中以三级c l o s 网络( c 3 ) 最为常用。本文阿 先研究三级c l o s 网络的广义无阻塞条件，三级c l o s 网络上的e v i l t w i n 随机路i j 算法，给出了h 一关系流量条件下三级c l o s 网络上的简单随机路由算法的理沦。p 二 能分析，然后研究分组交换的m s m 结构( m e m o r y - s p a c e m e m o r y ) 实现的= i 线 c l o s 网络的概率无阻塞条件和平均时延，以及s s s 结构( s p a c e s p a c e s p a c e ，s 3 ) 实现的三级c l o s 网络的吞吐特性。 但是1 程实际需求的交换网络的端口数目可能是任意的，丽采用基本交换m 元构建的c l o s 网络拓扑是一种固定的拓扑，往往不能充分利用很多交换单元，这 意味蕾更高的成本和复杂性。针对c l o s 网络拓扑缺乏足够的伸展性、不够灵活的 问题，提出多级网络的可伸展性问题。研究表明，存在两类多级网络是可伸展的， 其级间连接模式分别为模加减和混洗连接。首先研究以2 2 交换单元为基本交换 单元、级问连接模式为模加减的b a n y a n 网络，称为p 2 i 网络和p n 2 i 网络，接着 将其推广至p k i 网络。最后研究级问连接模式为混洗连接的多级网络，即广义混洗 网络( g e n e r a l i z e ds h u f f l e e x c h a n g en e t w o r k s g s e n ) 和广义d e l t a 网络( g e n e r a l i z e d d e l t an e t w o r k s ，g d n ) 。 在可伸展的多级网络的研究中，遇到的主要问题是：可伸展的多级网络在其 网络端口数目为整数的幂次时，其网络拓扑具有最好的对称性( 简称为幂次网络 或完全网络) ，标记路由算法简单、易于实现，因而具有良好的性能。随着网络的 伸展，网络端口数目不再是整数的幂次时，原来适用于完全网络的标记路由算法 可能不再适用，需要采用新的标记路由算法。另外，此时网络结构的对称性要比 完全网络差，在均匀到达、目的地址为均匀分布的注入业务流条件下，采用适川 于完全网络的标记路由算法将导致非完全网络内部链路流量的不均衡，为此提出 了新的流量均衡的平衡标记路由算法。通过理论分析和仿真实验表明，流量均衡 的平衡标记路由算法可以有效的改善非完全网络的时延吞吐性能，使之具有完全 网络的性能。 概括的讲，本文的主要工作和贡献包括以下几个方面： 1 研究了三级c l o s 网络的广义无阻塞条件，采用启发式搜索算法得到其必要条件。 研究了三级c l o s 网络上的e v i l t w i n 随机路由算法，证明了e v i l t w i n 置换和 西安电子科技大学博士学位论文：可伸展多级分组交换网络结构的研究 拉丁矩阵之间的密切关系，并相应给出了e v i l t w i n 置换的构建方法。给出了 在h 一关系流量条件下，三级c l o s 网络上的随机路由算法的理论性能分析。 分析了分组交换m s m 结构实现的三级c l o s 网络的概率无阻塞条件和平均时 延，以及s s s 结构实现的三级c l o s 网络的吞吐率。针对c l o s 网络拓扑缺乏伸 展性，不够灵活的缺点，提出了多级网络的可伸展性的概念。 2 提出了级间连接模式基于模加减的一类可伸展多级网络：p 2 i 网络、p n 2 i 网络 以及p k i 网络。提出了这类网络上的基于数的进制表示的标记路由算法，并分 析了这类网络的结构属性。发现这类网络在网络端口数目不是整数的幂次时， 该标记路由算法将导致网络内部链路流量不均衡的问题。为此，提出了新的 流量均衡的平衡标记路由算法，并证明了其正确性。仿真实验结果表明平衡 标记路由算法有效地改善了网络性能。 3 研究了另外一类基于混洗连接模式的可伸展多级网络：广义混洗网络和广义 d e l t a 网络。同样的，广义混洗网络和广义d e l t a 网络在网络端口数目不是整 数的幂次的情况下，原路由算法也将导致网络内部链路流量不均衡的问题。 为此，提出了新的流量均衡的平衡标记路由算法，通过仿真实验表明平衡标 记路由算法有效地改善了网络性能。研究了单向和双向广义混洗网络的标记 路由算法，提出了双向广义混洗网络的后向网络的标记路由算法。 4 研究了三级广义d e l t a 网络( d 3 ) 。三级广义d e l t a 网络是三级c l o s 网络的一个 直接推广。其网络端口数目可以按需构建，因而具有更好的灵活性。在均匀 到达、目的地址为均匀分布的注入业务流条件下，仿真分析表明采用平衡标 记路由算法的三级g d n 网络与相同端口数目的三级c l o s 网络具有同等的性 能。同时，研究了三级g d n 网络的具体实现问题。研究表明，三级g d n 网 络是设计端口数目为任一整数的倍数的交换网络实际可行的候选方案。 关键词：分组交换交换网络可扩展性可伸展性多级网络标记路由算法 流量均衡 a b s t r a c t a b s t r a c t c o n 疗o n t e dw i t ht h ee x p l o s i o no 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 c o m m u n i c a t i o nn e t w o r k sa r c h i t e c t sm a k eg r e a te f f o r t st op r o v i d es c a l a b i l i t yf o rs w i t c h a r c h i t e c t u r ei nt h ec u r r e n tr o u t e r sa n ds w i t c h e s t w oa p p r o a c h e sa r ea v a i l a b l e o n ei st o l i f tt h es w i t c hc a p a c i t yo ft h es i n g l e s t a g es w i t c h ，b u tt h i sa l t e r n a t i v ei s a l w a y s u n s u c c e s s f u lf o rt h ep r a c t i c a li m p l e m e n t a t i o nl i m i t so ft h es i n g l e s t a g es w i t c h t h e o t h e ri st oc o n s t r u c tal a r g e r s w i t c h i n gf a b r i cb yu s i n gi n t e r c o r m e c t i o nn e t w o r k s i n c l u d i n gs e v e r a ls w i t c he l e m e n t s w h i c hi sc o m m o n l yu s e da ss c a l a b l i t ys o l u t i o n s c u r r e n t l y , t h r e es t a g ec l o sn e t w o r k s ( c 3 ) a r et h em o s tp o p u l a rn e t w o r kt o p o l o g y c e n t e r i n go nt h ec 3 ，w ef i r s t l ya d d r e s st h en o n b l o c k i n gc o n d i t i o ni nt h ew i d es e n s e ，t h e e v i l - t w j nr a n d o m i z e dr o u t i n ga l g o r i t h m a n d g i v eat h e o r e t i c a la n a l y s i su n d e rt h e a s s u m p t i o no ft h eh r e l a t i o nt r a f i l e f 冶a l s op r e s e n tp e r f o r m a n c ea n a l y s i so ft h ec 3 w i t hm s m ( m e m o r y s p a c e m e m o r y ) s t r u c t u r ea n ds s s ( s p a c e s p a c e s p a c e ) s t r u c t u r e r e s p e c t i v e l y b u tt h ep r o b l e mt ob u i l dam 1 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 s 、w i t ht h es i z e o nd e m a n d ，w h i c hf r e q u e n t l yo c c u r si nt h ep r a c t i c eo fe n g i n e e r i n g ，h a sn o tb e e n e x t e n s i v e l ya d d r e s s e di nt h el i t e r a t u r e o b v i o u s l y , t h ec l o sn e t w o r k st o p o l o g yc a n n o t 1 i v eu pt oi t t h u s t h eo n l yc h o i c el e f tf o rt h ea r c h i t e c ti st od e s i g nam i no ft h es i z e w h i c hi s l a r g e rt h a nt h en u m b e rn e e d e d w h i c hw i l lm a k em a n ys w i t c he l e m e n t s u n n e c e s s a r ya n dw a s t e d ，c a u s i n gh i g h e rc o s ta n dc o m p l e x i t y t oc i r c u m v e n ts u c h p r o b l e m s ，w ep r o p o s et h ec o n c e p t so ft h ee x t e n s i b i l i t ya n dt h ee x t e n s i b l em u l t i s t a g e n e t w o r k s 。w h i c ha r et h em a i nf o c u so ft h i sp a de r r e s e a r c hs h o w st h a tt h e r ea r et w o c l a s s e so ft h ee x t e n s i b l em u l t i s t a g en e t w o r k s ，o fw h i c ht h ec o n n e c t i n gp a t t e r nb e t w e e n t h ea d j a c e n ts t a g e sa r et h ep l u s m i n u s m o d u l o na n ds h u 御e e x c h a n g e f i r s t l y , w e p r e s e n tt h ep 2 in e t w o r k sa n dp n 2 in e t w o r k s w h i c ha r et h ee x t e n s i b l eb a n y a nn e t w o r k s c o m p o s e do f2 2s w i t c he l e m e n t s t h e nw eg e n e r a l i z et h i si d e aa n dp r o p o s et h ep k i n e t w o r k s s e e o n d l y ，w es t u d ya n o t h e rc l a s so ft h ee x t e n s i b l em u l t i s t a g en e t w o r k s ，t h e s h u f f l e - e x c h a n g ec o n n e c t e dm u l t i s t a g en e t w o r k s i n c l u d i n gt h eg e n e r a l i z e ds h u 聊e e x c h a n g en e t w o r k s ( g s e nf o rs h o e ) a n dg e n e r a l i z e dd e l t an e t w o r k s ( g d nf o r s h o r t ) i nt h es t u d yo ft h ee x t e n s i b l em u l t i s t a g en e t w o r k s ，t h em o s ti n t r a c t a b l ep r o b l e m e n c o u n t e r e di s ：w h e nt h es i z ei sap o w e r ，t h ee x t e n s i b l em u l t i s t a g en e t w o r k sp o s s e s st h e s y m m e t r y , h e n c et h et a g b a s e dr o u t i n ga l g o r i t h mi sv e r ys i m p l e u n d e rt h ec o n d i t i o no f t h ee q u i p r o b a b l ea d d r e s so fu n i f o r mp a c k e tt r a f f i ca te a c hi n p u tp o r t ，t h et r a f f i ci ne a c h l i n ki se v e na n dt h en e t w o r kp e r f o r m a n c ei sg o o d i nt h i sc a s e w ec a l lt h en e t w o r kj s c o m p l e t e a st h es i z ei sn ol o n g e rap o w e r , t h es y m m e t r yi sb r o k e n u n d e rt h es a m e t r a f f i cc o n d i t i o na te a c hi n p u tp o r t ，w cf i n d ，t h es i m p l et a g b a s e dr o u t i n ga l g o r i t h mu s e d l nt h ec o m p l e t en e t w o r k sw i l lm a k et h et r a f i l ei ni n t e m a ll i n k su n e v e n w h i c h d e t e r i o r a t e st h en e t w o r kp e r f o r m a n c e t h u sw ep r o p o s eal l e wr o u t i n ga l g o r i t h mc a l l e d b a l a n c e d t a g - b a s e dr o u t i n ga l g o r i t h m ，w h i c hm a k e st h ei n c o m p l e t ee x t e n s i b l e m u l t i s t g a en e t w o r k sb e h a v ea l m o s tt h es a m ea st h ec o m p l e t ee x t e n s i b l em u l i t s t a g e n e t w o r k sw i t hr e s p e c tt ot h ep e r f o n n a n c ei s s u e s 2 西安电予科技大学博士学位论文：可伸展多级分组交换网络结构的研究 a l li na 1 1 t h ec o n t r i b u t i o n sc a nb eo u t l i n e da sf o l l o w s ： 1 t h en o n b l o c k i n gc o n d i t i o ni nt h ew i d es e n s eo ft h ec 3i ss t u d i e d a n dt h ee m p i r i c a l n e c e s s a r yc o n d i t i o ni sa c q u i r e db yt h eh e u r i s t i cp r o b i n ga l g r i t h md u b b e d 髂f o r c e d a l g o r i t h m t h ee v i l t w i nr a n d o m i z e dr o u t i n ga l g o r i t h mi si n v e s t i g a t e di nt h ec 3 t h ee s s e n c eo fe v i l 一1 、w i np e r m u t a t i o n si ss h o w na n dh o wt oc o n s t r u c te v i i t w i n p e r m u t a t i o n si si m p l i c i t l yg i v e nb yt h ep r o o f at h e o r e t i c a la n a l y s i so ft h ec 3u n d e r t h ea s s u m p t i o no ft h eh r e l a t i o nt r 瓶ci sp r e s e n t e d t h en o n b l o c k i n gc o n d i t i o ni n t h ep r o b a b i l i s t i cs e n s ea n dt h ea v e r a g ed e l a yo ft h ec 3w i mm s ms t r u c t u r ea r e a n a l y z e d a n dt h ep e r f o r m a n c ea n a l y s i so ft h et h r o u g h p u to ft h ec 3w i t l ls s s s t r u c t u r ei sa l s og i v e n f o rt h ep u r p o s eo fc o n s t r u c t i n gal a r g es c a l es w i t c h i n gf a b r i cw i t ht h ea r b i t r a r y n u m b e ro fp o r t s ，i tw i l lb en o t i c e dt h a tt h ec l o sn e t w o r k si sn o tf l e x i b l ee n o u g h w h i c hi m p l i e st h a tt h ec l o sn e t w o r k sa r en o tg o o da tt h ee x t e n s i b i l i t y h e n c e ，t h e c o n c e p t so ft h ee x t e n s i b i l i t yo fm u l i t i s t a g en e t w o r k sa n dt h ee x t e n s i b l em u l t i s t a g e n e t w o r k sa r ep r o p o s e ds u b s e q u e n t l y 2 an e wc l a s so f t h ee x t e n s i b l em u l t i s t a g en e t w o r k si sd i s c o v e r e d ，i e ，t h ep 2 in e t w o r k s ， t h ep n 2 in e t w o r k sa n dt h ep k in e t w o r k s t h es t r u c t u a lp r o p e r t i e so fs u c hn e t w o r k s a r ei n v e s t i g a t e da n dt h et a g b a s e dr o u t i n ga l g o r i t h m so nt h eb a s i so ft h en u m b e r r e p r e s e n t a t i o ni nk r a d i x a r eg i v e n w ed i s c o v e rt h ep h e n o m e n ao fu n e v e nt r a f f ci n s u c hn e t w o r k sa n df o r m u l a t et h i sp r o b l e m m e t h o d o l o g i e st os o l v et h e s ep r o b l e m s a r ep u tf o r w a r d a n dt h ec o r r e c t n e s si s p r o v e dr e s p e c t i v e l y s i m u l a t i o nr e s u l t sa l s o s h o wt h a tt h ep e r f o r m a n c ei ss i g n i f i c a n t l yi m p r o v e db yu s i n gb a l a n c e dt a g b a s e d r o u t i n ga l g o r i t h m 3 t h es h u f f l e e x c h a n g ec o n n e c t e de x t e n s i b l em u l t i s t a g en e t w o r k sa r ei n v e s t i g a t e d ，i e t h eg e n e r a l i z e ds h u f f l e e x c h a n g en e t w o r k s ( g s e n ) a n dt h eg e n e r a l i z e dd e l t a n c t w o r k ( g d n ) a ss u c h ，u n d e rt h ec o n d i t i o no fe q u i p r o b a b l ea d d r e s so fu n i f o r m p a c k e tt r a f f i ca te a c hi n p u tp o r t t h eg s e nw i l lr o u t es u c ht r a f i l cu n e v e n l y t h i s p r o b l e mi sa d d r e s s e di na s i m i l a rw av s i m u l a t i o nr e s u l t ss h o wt h a tt h ep e r f o r m a n c e i s s i g n i f i c a n t l yi m p r o v e db yu s i n gt h eb a l a n c e dt a g b a s e dm u t i n ga l g o r i t h m t h e r o u t i n gp r o b l e mi nt h eb i d i r e c t i o n a lg s e ni sa l s os t u d i e d at a g b a s e dr o u t i n g a l g o t r i h t mf o rb a c k w a r dn e t w o r k si sp r o p o s e d 4 t h et h r e es t a g eg e n e r a l i z e dd e l t an e t w o r k ( d 3 ) i ss t u d i e d ，w h i c hh a st h ea d v a n t a g e o fc o n s t r u c t i n gs w i t c h i n gf a b r i cw i t ht h es i z eo nd e m a n d w i t ht h eb a l a n c e d t a g b a s e dr o u t i n ga l g o r i t h m ，s i m u l a t i o nr e s u l t ss h o wt h a tt h ed 3b e h a v e sa l m o s tt h e s a m ea st h ec 3w i t hr e s p e c tt ot h ep e r f o r m a n c ei s s u e s t h e r e f o r et h ed 3 o fw h i c h p e r f o r m a n c ei sc o m p a r a b l et ot h ec 3w i t ht h es a m es i z e i sap r a c t i c a b l ea l t e r n a t i v e f o r t h ed e s i g no fs w i t c h i n gf a b r i cw i t ht h ea r b i t r a r yn u m b e ro f p o r t s ， k e yw o r d s ：p a k c e ts w i t c h i n g ，s w i t c h i n gf a b r i c s ，s c a l a b i l i t y , e x t e n s i b i l i t y , m u l t i s t a g e n e t w o r k ，t a g b a s e dr o u t i n ga l g o r i t h m ，t r a f f i cb a l a n c e 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：e 基震 日期：2 塑生：! ：量q 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的沦 文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名 导师签名 睦囊 鞲 u 日期：2 0 0 4 - i 2 0 日期：如呼2 0 第一章绪论 第一章绪论 随着通信技术和计算机技术的迅速发展，特别是w w w 和多媒体业务的爆炸 式增长，i n t e m e t 的数据流量急剧增加，人们对通信带宽的需求也相应增加，对 i n t e r n e t 的服务质量和服务内容也提出了更高的要求。当i 诲正在研究和发展更高 性能的宽带通信网络。这样不但要向用户提供宽带接入网，还要发展高速骨干删。 大容量的分组交换路由器是实现高速骨干网并决定其性能的关键所在。 1 1 交换网络概述 1 1 i 交换网络的地位和作用 交换网络 输入接口f 。丽天磊苫趸接谪磊1 藉苗磊苫一j输出接口 一一“ 一 - ! 输入：皇 一扣 “ 一一 - - ” 卜 x i 一 n 1 _ j 什 一卜 。一卜 一， 一 l 。_ - - 图l _ 1 路由器和交换机的参考模型 交换网络( s w i t c h i n gf a b r i c s ) 是路由器和交换机( 为了表述方便，统称为交 换系统) 内部的核心部件。分组交换网络的交换能力在很大程度上决定着分组交 换系统的性能，如吞吐率，交换时延及其抖动、丢失和乱序等。 图1 1 给出了当前分组交换系统的参考模型川。交换系统包含输入输出接口和 交换网络，交换网络又包括输入( 出) 端口和将它们互连起来的连接网络( 又称 交换核心) 。不失一般性，假定交换网络只处理定长的数据单元( c e l l ，即信元) 。 如果交换系统传递不定长的分组，则要求输入输出接口具有分段重装功能( s a r ) s a r 功能般在交换网络外部完成。这里使用s a p 的字面含义，并不是基于a t m 的背景；同样，信元泛指定长的分组，不仅限于a t m 信元。 这种基于定长信元交换的假设并不是凭空想象，因为当前几乎所有实用大容 量分组交换机或路由器均采用定长分组交换网络。交换网络接收或者发送一个信 元的时间称为一个时隙( t i m e s l o t ) 。 出输 ，卜， 卜卜 一 一 一 一 一 1k-jl_1kl 一 _ - 西安电子科技大学博士学位论文；可伸展多级分组交换网绍结构的研究 交换网络包括以下三个功能模块： 1 ) 输入端口，从输入接口接收信元； 2 ) 输出端口，向输出接口发送信元： 3 ) 连接网络，提供所有输入端口和输出端口之问的可控的连通性。 假定所有输入( 输出) 端口具有相同的输入( 输出) 速率。为了简单起见， 只考虑有个输入端口和个输出端口的交换网络，且每个输入( 输出) 端口对 应单条输入( 输出) 链路的情况。当输入( 输出) 接口上有多条入( 出) 链路时， 需要交换网络外的设备( 如复接分接器，分组调度器，流量管理器等) 来加以处 理。这种附加的复接分接等功能，尽管对整个交换设备的的性能和设计至关重要， 但与交换网络的结构却是独立的，且对交换网络的可扩展性影响较小。 1 1 2 分组交换网络的演进 1 1 2 1 交换网络结构方面【3 】 6 】 在分组交换技术发展过程中，分组交换网络曾经采用了几种不同的架构。尽 管不同的商用交换网络各有特色，但是从广义而言，它们的演进的方式是类似的， 那就是朝着更加并行的方向发展，以实现更高速率和更大容量的交换。并行性可 通过两个方面实现：首先，原来由各端口共用的组件( 如中央处理器c p u 和共享 缓存器b u f f e r s ) 如今分布在各个端口线卡( l i n ec a r d ) 处。其次，并行性体现在 使用多个相同的处理单元来分头处理分组流。 1r l i n ec；t r dl i njc a r d w i t h (p uw i t l【c p u & b u f：e r s& eu f r e r s ? 嵩口1端口，r立；i ( a ) 单总线单c p i j 结构( b ) 单总线对称式多c p u 结构( c ) 交义开关矩阵型结构 图1 2 分组交换网络架构的演进过程 最初的分组交换网络是按照传统计算机的体系架构设计的，包括总线，c p u 缓存和线卡。线卡完成物理层和数据链路层功能，作为与外部链路的接口，如图 第一章绪论 1 2 ( a ) 所示。从端口到达的信元通过总线传送给c p u ，由c p u 完成转发处理功能后， 将信元存储到缓存器中等到输出端口空闲时再转发出去。当轮到该信元发送时， 总线再次将其传送给输出线卡，然后由输出线卡输出到链路。这种结构的性能) f c 颈在于c p u 和缓存器，于是导致新的结构的出现，即将c p u 和缓存器分布在各个 端口的线卡处，如图1 2 ( b ) 所示。各端口范围内的转发处理的功能由各端口的擘 用c p u 完成，然后分组立即转发给相应的目的端口线卡。多个处理单元的并行：l i 作提高了整个交换系统的吞吐性能。 这种结构的性能最终受限于总线的速率，因为总线每个时隙只能传送一个信 元。为此，采用单级交叉开关矩阵( 以下称为交换单元) 代替总线，如图l 。2 ( c ) 所示。这样多个端口之i h 可以并行通信，提高了整体性能。另外的一一个好处是从 端口线卡到背板的连接可采用短的高速点到点的连接。 最近，随着端口线卡速率的提升，因而单级交换单元已经不能满足对交换容 量的要求。于是采用多个并行的单级交换单元，或者采用由单级交换单元组成的 多级网络，成为目前大容量交换网络的最常用架构。 1 1 2 2 物理实现方面【6 i 【8 】 为了增加线卡的数目和交换系统的聚合带宽，分组交换系统实现方面的主要 演进趋势就是分离线卡和交换核心的群集系统( 又称多机框或多机架系统) 。通过 高速的电或光的链路将两者连接起来。采用这种架构的典型例子是j u n i p e r 网络t 系列的路由器以及p m c s i e r r a 的e t t l ：蓦片组交换网络架构。 这种物理实现架构的好处有： 1 可以容纳数量巨大的线卡 由于消除了在单机架内在交换核心周围布置线卡的物理封装限制，交换系统 更容易封装，更容易散热，并且最重要的是可以互连大量的线卡。 2 简化交换核心的容错技术 单个公用交换核心一旦出现故障，整个系统就会瘫痪。对于高可用性的系统， 需要第二个交换核心用来提供简单的容错。 3 具有可升级的向后兼容能力 线卡和交换核心之间的彻底分离也就分离了各自的研发过程。当前丌发的线 卡可以连接到未来端口密度更高的、功能更丰富的、添加了新功能的交换网络中。 这种架构还允许在不中断当前服务的情况下升级整个交换系统。 4 具有空间可扩展性【2 】 这一用语由g o r d e nb e l l 发明，用来表示一个系统可从一个盒子、一问房予 或一幢大楼中扩展到多幢大楼和更大地理区域( 远距离) 的能力。 西安电子科技大学博士学位论文：可伸展多级分组交换网络结构的研究 1 1 2 3 高速互连通信技术 以上的物理实现架构的发展趋势是基于高速电光互连技术的最新进展。 物理层技术3 】1 4 】 以往，基于背板的交换系统一直是遵循采用更宽的总线和更高的信号时钟频 率这一方式演进的。然而当单根信号线上传输速率超过某个上限后，这种方法已 不大适用，原因是信号的失真( d i s t o r t i o n ) 和串扰( c r o s s t a l k ) 以及负载驱动 的问题( 驱动更多的信号线和更高频率的信号可能消耗更大的功率) 。设计者被迫 从并行总线转移到串行点到点连接。使用串行器和解串行器( s e r d e s ) 的方法，能 够在同一信号线上组合传输数据和时钟的串行信号流。目前每个s e r d e s 通路可传 输的速率为2 5 3 1 2 5 g b i t s s 。但是当速率超过1 g b i t s s 以后，电方式的高速串 行线上的信号的完整性( i n t e g r a l i t y ) 受以下因素影响：信号线上的阻抗不匹配 ( i m p e d a n c em is m a t c h ) 产生的信号反射，背板材料引起的信号衰减 ( a t t e n u a t i o n ) ，由线问串扰和码间干扰( i s i ) 引入的噪声。 随着线卡工作速率的不断提高，采用光纤进行连接逐渐成为趋势。光纤的优 点是可以传送大容量、不同速率、不同波长的信号，是实现板间和机架间信号互 连的良好选择。目前可以通过一个光收发器传送1 2 条s e r d e s 通路，传送距离约 3 0 0 米。更高带宽的光连接技术正在不断研究，如光互连论坛( o p t i c a l i n t e r n e t w o r k i n gf o r u m ，o i f ) 正在为高速背板开发公用的解决方案( 4 9 g b i t s s 到6 4 g b i t s s 和1 1 g b i t s s ) 。 线卡与交换核心网络之间的接口协议 在分离的线卡和交换核心之间采用一种专门的高速通信接口协议。这里以 p m c s i e r r a 公司的l c s 协议【5 】【6 1 ( l i n ec a r dt os w i t c h ，l c s ) 2 , j f f j 。其它如a g e r e s y s t e m s 公司的p i 意片组提供了几种协议兼容的接口。 l c s 协议( l i n ec a r dt os w i t c hp r o t o c o l ，l c sp r o t o c 0 1 ) l c s 协议l c s 协议 卜卜 l i n ec a r d sr a c k s w i t c hc o r er a c kl i n ec a r d sr a c k 图1 3 使用l c s 协议的群集交换系统 第一章绪论 交换核心可以通过l c s 协议来互连速率高达1 0 g b i t s s 的线卡。该协议也川。 用于2 5 g b i t s s 以及扩展到更高速率4 0 g b i t s s 的情况下。 l c s 协议可称为具有流控功能的标记交换协议( l a b e ls w a p p i n gw i t h f 1 0 w c o n t r 0 1 ) 。发送给交换核心的信元打上一个交换核心和线卡预先协商好的标记， 该标记用来指示信元的优先级以及目的输出端口。每队列的流控机制用来傈i i ：交 换核心无丢失。l c s 协议的逻辑表示示于图1 3 。 l c s 协议的协议数据单元( l c sp d u ) 出l c s 协议头和载荷域( p a y l o a d ) 构成。 l c s 协议头的长度为8 字节，p a y l o a d 用来装载一个长度为6 4 字节( 或7 6 字节) 的信元。l c sp d u 格式如图1 4 所示。其中各信息域的功能描述如下： c e llf i e l d ：标识载荷装载信元所属的分组流： r e q u e s tf i e l d ：为在输入侧线卡处排队的信元请求交换核心调度传送孩信元： g r a n tp i e l d ： 认可先前请求的输入侧信元在有限的往返时州内从输入侧线卡1 0 送至交换核心： h o l er e q u e s t ： 请求传送一个信元至指定输出流的事件迟延一个信元时间发生。 l c sp d u 的载荷可以是变长i p 分组的分片、以太网帧的一部分或者是完整的 a t m 信元。l c s 协议与载荷内容的独立性使得l c s 协议可以用于a t m 交换机、i p 路 由器或者是g 比特以太网交换机。 2 4 - b i t s1 6 - b i t s8 - b i t s1 6 - b i t s 6 4 - b y t e s r e q u e s tf i e z d c e l lf i e l dh o l er e q u e s th e a d e rc r cd a t a f j l 2 9 一b i t s1 9 一b i t s1 6 一b i t s 6 4 一b y t e s 图1 4l c s 协议的协议数据单元格式 通过三次握手( t h r e e w a yh a n d s h a k e ) ，l c s 协议无丢失地传送信元从输入侧 线卡通过交换核心转发到输出侧线卡。其详细的工作过程如图1 5 所示。 首先，l c sp d i j 携带缓存于线卡的信元的请求( r e q u e s t ) 消息，从输入侧线 卡发往交换核心。请求