（通信与信息系统专业论文）直接交换变长分组的交换结构研究.pdf

摘要 摘要 变长交换技术是指i p 数据包不缀过切割而直接通过交换结构进行交换。与定长 交换相比，变长交换的实或相对要笈杂，由于交换的信患单元颗粒大，控翎时延 变得复杂。但是与定长交换相比，变长交换不会造成不必要的带宽浪赞。对于定 长交换，切割狰包的辩侯，包豹长度不一定溺婷是定长信元长度的整数倍，因此切 割后可能会产生小于信元长度的单元，这样会造成带宽的损失。另外，变长交换 不需要在数据交换前和交换后进行分割和组合操作，因此在入端口处不需要一个 额外的切割模块，而在出端口处则不需要个额外的组合定长信元的模块，节省 了存储器资源以及信元重排序的规模。 本文首先研究了不带缓存的c r o s s b a r 中的变长调度算法，这些调度算法都是在 定长调度算法的纂础上发展而来。基本的思想都是保持一个完整的数据包传送完 毕，秀改变该通遂交叉开关豹状态。数据包逻辑上被甥害4 成若干信元，僵是在物 理上仍然是连续的。交叉开关的状态一直保持到最后的逻辑信元传送完毕，再根 据 串裁算法进行变化。进行传竣这种机镶通常成为c e l lt r a i n 枫裁。遂过这种掇制 达到交换变长数据包的目的。这些变长调度算法包括i p p i m ，p b i s l i p ，s o l ， p b w m w m 算法等。 在c r o s s b a r 的交叉节点设置缓存，这样构成了b u f f e r e dc r o s s b a r ，目i l c i c q 结构。 这种结构比较适合交换变长的数据包，因为这种结构中各个输入端口可以在不同 的时蘩发送数据包，交叉节点缓存发往不阗的输出端口的数据包也可以不图步， 这样就形成异步b u f f e r e dc r o s s b a r 。本文将d r r 调度算法应用 ；l j b u f f e r e dc r o s s b a r 中，完成了输入蝼口和交叉节点缓存交长数据包的调度。这种调度方案避免交换 链路长时间被长数据包的端口所占据，减少了系统的平均时延。本文还对这种结 构进行了仿真分板，与r r 调度的b u f f e r e d c r o s s b a r 进行了性能的比较。 在端口数不是很多的交换结构中，c r o s s b a r 由于冀结构简单，无阻塞特性，得 到了广泛的应用。随着端阴数n 的增加，c r o s s b a r 的资源消耗与n 2 成正比，并且调 度算法趣很难实现。因此对于端日数很多( 端舀数大子6 4 ) 的交换，多采用多级 交换结构来构成超大容量交换结构。典型的多级交换结构如b a n y a n ，s h u f f l e ，b e n e s ， c l o s 以及国这些结构扩展出来的各种交换结构。本文对多级交换结构熏 接交换变长 分组的技术进行了综述。对于b a n y a n 网络，在内部交换单元设立缓存，相邻的两 ￥ 摘要 级之闻引入反压枫例，变长数据包在b a n y a n 网内异步操j 乍，通过这辨方法完成交 长交换。t a n d e m - b a n y a n 结构暑1 1 s h u f f l e 结构的内部无缓存，处理变长包冲突的方法 是使用偏折路由，对变长数据包采用c u t - t h r o u g h 的交换方式。b a t c h e r - b a n y a n 网内 部也不设缓存，处理变长数据包冲突的方法魁利用b a t c h e r 网对数据包进行排序， 这样进入b a n y a n i - n 的数据包目的地址有一定排列规律，从而可以避免数据包的冲 突。b a t c h e r - b a n y a n 网通遭先送出试探分组，试探对丽输出端臼的竞争情况来进 行变长交换。 b e n e s 网络是应用比较广泛豹一种多级互连结构，由一拿反向b a n y a n 圈嗣 b a n y a n 网连接而成。因此，b e n e s 结构包括分发网( b m w a n 网) 和路由网( 反n b a n y a n 网) 两部分，分发网主要是将进入交换结构的数据包均匀分发到各条链路上，以 便进入路由阏的数据包负载均衡，路由网负责将分组送到目的输出端口。本文究 了b e n e s 结构中的变长交换，并提出了一种基于业务流的变长分组分发算法，这种 算法蘑在分发网中。本文还对交换交长分组b e n e s 网络进行了仿真，比较了随枫分 发算法和繁于业务流分发算法对b e n e s 的时延特性，交换单元排队长度的影响。 关键词：交换结构，变长交换，交叉连接矩跨，差额轮循调度，多级交换结构， b e n e s 结构，分发算法 i i a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，v a r i a b l el e n g t hp a c k e ts w i t c hh a sb e e nw i d e l yi n v e s t i g a t e d c e l l s w i t c hh a st w od i s a d v a n t a g e s f i r s t ，b e c a u s et h ep a c k e t sa r eo fv a r i a b l es i z e ，s ob e f o r e s w i t c l f i n g ，p a c k e tm u s tb es e g m e n ti nt oc e l la n db er e a s s e m b l e dt ob eap a c k e ti nt h e o u t p u t s e g m e n t a t i o na n dr e a s s e m b l y ( s a r ) h a v ei n c r e a s e dt h et i m ec o m p l e x i t y s e c o n d ，c e l lc a l lg e n e r a t eb a n d w i d t hl o s t ，a sac e l lm a yn o tc o n t a i naf u l lp a c k e td a t a f o re x a m p l e , i f ac e l li so f 6 4b y t e s ，ap a c k e to f 6 5b y t e sm u s tb es e g m e n t e di nt w oc e l l s ， a n dt h es e c o n dc e l lo n l yc o n t a i n so n eb y t ep a c k e td a t aa n do t h e rp a d d i n gb y t e s ，s ot h e h i e c h a n i s mo fs e g m e n t a t i o nc a nc a u s es e r i o u sb a n d w i d t hl o s t 。a l s o t o a c h i e v i n g s t a b i l i t y , i n t e r n a ls p e e d u pi sn e e d e d c o m p a r e dt of i x e dl e n g t hs w i t c h ，b ys u p p o r t i n g v a r i a b l el e n g t hp a c k e ts w i t c h ，t h e r ei sn on e e df o rs e g m e n t a t i o na n dr e a s s e m b l yc i r c u i t s ， a n dn os p e e d u pi sn e c e s s a r yt os u p p o r ts a r 。 t h i sd i s s e r t a t i o nf i r s ts t u d i e sv a r i a b l el e n g t hp a c k e ts w i t c hi nu n b u f f e r e dc r o s s b a r t h ef i r s ts c h e d u l i n ga l g o r i t h mu s e di nu n b u f f e r e dc r o s s b a rs u p p o r t i n gv a r i a b l el e n g t h p a c k e ti si p - p i mw h i c hi sb a s e do nv o q w h e nam a t c h i n go fah e a d o f - p a c k e tc e l li s m a d e ，t h i sm a t c h i n gi sm a i n t a i n e du n t i la l lc e l l so ft h a tp a c k e th a v eb e e nt r a n s f e r r e d e a c hp a c k e ti sd i v i d e di n t ol o g i c a lc e l l sw h i c ha r en o tp h y s i c a l l ys e p a r a t e db u t c o n s e c u t i v e l yc o m b i n e d t h es c h e d u l e rm a i n t a i n sc r o s s - p o i n tu n t i lt h el a s tl o g i c a lc e l l n a m e dt h ee n do fp a c k e t ( e o p ) c e l la p p e a r s t h ee o pc e l lm a yc o n t a i ns o m ep a d d i n g o v e r h e a d t h i sm e c h a n i s mi sc a l l e dc e l lt r a i n p b i s l i p ，s o l ( s e l f = o p t i m i z e dl a t e n c y ) a n dp b w m w m ( p a c k e tb a s e dw a i t i n gm w m ) a l g o r i t h m sa l s ou s ec e l lr a i n m e c h a n i s m w i t ht h ec o n t i n u e di n c r e a s ei nd e n s i t yo fv l s i s u f f i c i e n tb u f f e t i n ga lc r o s s b a r c r o s s p o i n tf o ro n ec e l lo rp a c k e th a sb e c o m ef e a s i b l et oi m p l e m e n t b u f f e r e dc r o s s b a r h a sb e e nw i d e l yi n v e s t i g a t e di nt h er e c e n ty e a r s b u f f e r e dc r o s s b a rn a t i v e l ys u p p o n s v a r i a b l el e n g t h p a c k e ts w i t c h ，b e c a u s ei td o s en o t n e e dc e n t r a l i z e ds c h e d u l e ra n d s y n c h r o n i z a t i o nb e t w e e nt h ei n p u ta n do u t p u tc l o c kd o m a i n si ss i m p l i f i e d t h i sp a p e r d e s c r i b e sa r c h i t e c t u r eo fb u f f e r e dc r o s s b a rw o r k i n gd i r e c t l yo nv a r i a b l el e n g t hp a c k e t c h a p t e r3p r e s e n t st h es i m u l a t i o nr e s u l t ，a n da n a l y s i st h ei n f l u e n c eo ft h eq u e u el e n g t h i t l a b s t r a c t a n da v e r a g ed e l a yo nd i f f e r e n ts c h e d u l i n ga l g o r i t h m s f o rl o wt om o d e s tn u m b e r so fp o n s ( u pt oa b o u t6 4 ) ，t h ec r o s s b a ri st h es w i t c h t o p o l o g yo fc h o i c e ，d u et oi t ss i m p l i c i t ya n dn ob l o c k i n go p e r a t i o n h o w e v e r , i t sc o s t g r o w sw i t hn 2 ，w h e r en i st h en u m b e ro f p o r t s ，w h i c hm a k e si tv e r ye x p e n s i v ef o rl a r g e n a d d i t i o n a l l y , c r o s s b a rs c h e d u l i n gi sah a r dp r o b l e m ，a n dg e t sh a r d e rw i t hi n c r e a s i n g n f o rs w i t c h e sw i t hh u n d r e d so rt h o u s a n d so fp o r t s ，m u l t i s t a g es w i t c h i n gf a b r i c a r c h i t e c t u r e sa r en e e d e d ，w h o s ec o s tg r o w t hr a t ei sl e s st h a nq u a d r a t i c c h a p t e r4 s u m m a r i z e ss o m em u l t i s t a g es w i t c h i n gf a b r i cs u p p o s i n gv a r i a b l el e n g t hp a c k e ts w i t c h a s y n c h r o n o u sb a n y a nn e t w o r k s ，w h i c ha r ep r o v i d e dw i t hi n t e r n a lb u f f e r si ne a c h s w i t c h i n ge l e m e n t ，e x p l o i tt h ep a c k e ts e l f - r o u t i n gt e c h n i q u e 。i tc a nh a n d l ev a r i a b l e l e n g t hp a c k e te f f i c i e n t l y t a n d e mb a n y a na n ds h u f f l en e t w o r ku s ed e f l e c t i o nr o u t i n gt o d e a lw i t hc o l l i s i o nb e t w e e np a c k e t s d e f l e c t i o nr o u t i n gm u l t i s t a g en e t w o r kh a v e a d v a n t a g eo fh a r d w a r es i m p l i c i t ys i n c es w i t c he l e m e n th a sn ob u f f e rm e m o r y , a n d v a r i a b l el e n g t hp a c k e ts w i t c h i n gc a nb ee a s i l yb a n d l e d t h eb e n e sn e t w o r ki st h el o w e s t c o s ts w i t c h i n gf a b r i ca n di sw i d e l yu s e dt ob u i l d t e r a b i ts w i t c hf a b r i c a nn nb e n e sn e t w o r kc a nb ec o n s t r u c t e db yp l a c i n gt w ob a n y a n n e t w o r k sb a c kt ob a c k t h et w ob a n y a n sa r ec a l l e dt h ed i s t r i b u t i o nn e t w o r ka n dr o u t i n g n e t w o r k ，r e s p e c t i v e l ms i n c et h ef i r s td i s t r i b u t e si n c o m i n gt r a f f i co v e rt h en l i n k si nt h e m i d d l eo ft h en e t w o r ka n dt h es e c o n dr o u t e sp a c k e t st ot h ep r o p e ro u t p u tl i n k i n c h a p t e r5 ，w ep r o p o s ead i s t r i b u t i o na l g o r i t h mb a s e do ns e r v i c e df l o w0 a c k e tw i t h s o m es o u r c ea d d r e s sa n dd e s t i n a t i o na d d r e s s ) t h i sa l g o r i t h mi su s e di nd i s t r i b u t i o n n e t w o r ka n dd i s t r i b u t e st h ev a r i a b l el e n g t hp a c k e t se f f i c i e n t l y t h es i m u l a t i o ns h o w s 也a tt h ed i s t r i b u t i o nb a s e do ns e r v i c e df l o wp e r f o r m sw e l l i nt h eb e n e sn e t w o r k k e y w o r d s ：s w i t c hf a b r i c ，v a r i a b l el e n g t hp a c k e ts w i t c h , c r o s s b a r , d e f i c i tr o u n dr o b i n ， m u l t i s t a g es w i t c hf a b r i c ，b e n e sn e t w o r k ，d i s t r i b u t i o na l g o r i t h m 缩略词 a p l b c c i c q d r r e o p f o h o l i s l i p i q i s d 孙 q 嗄 o q o s p i m p p s s a r s o l s f u c v o q v i q 缩略词 a v e r a g e p a c k e tl e n g t h b u f f e r e dc r o s s b a r c o m b i n e di n p u t c r o s s p o i n tq u e u e d e f t c i tr o u n dr o b i n e n do f p a c k e t f i r s ti nf i r s t0 u t h c a do f l i n e i t e r a t i v es l i p i n p u tq u e u e i n p u ts c h e d u l e r m a x i m u mw e i e # tm a t c h i n g o u t p u tq u e u e 0 u t p u ts c h e d u l e r p a r a l l e li t e r a t i v em a t c h i n g p a r a l l e lp a c k e ts w i t c h s e g m e n t a t i o na n dr e a s s e m b l y s e l f - o p t i m i z e dl a t e n c y s w i t c hf a b t i c u n b u f f e r e dc r o s s b a r v i r t u a lo u t p l nq u e u e v i r t u a li n p u tq u e u e v i i 平均包长 带缓存的交叉连接矩阵 联合输入交叉节点排队 差额轮循调度 数据包尾部标志 先入先出队列 队头阻塞 迭代s l i p 算法 输入端排队 输入端调度器 最大权重匹配算法 输出端排队 输出端调度器 并行迭代匹配算法 并行分组交换 切割和重组 自最优时延算法 交换结构 不带缓存的交叉连接矩阵 虚拟输出队列 虚拟输入队列 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机橡的学位或证书面馊用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 签名：叁童查：曰期：五卯6 年6 月妇日 关于论文使用授权的说骧 本学位论文作者完全了解逛子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据痒进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：兰童盎锄签名：主遴 日期：z 内年占月7 2 日 第一章引言 1 1 技术背景 第一章引言 作为m 网络中的互连设备，路由器的发展非常迅速，带宽和网络规模的增长推 动着路由器在性能和容量方面不断提升，业务的发展驱动着路由器更加智能化和 具备更强的业务提供能力。路由器的发展至今经历了五代f l 】，由开始的基于总线和 中央处理器的路由器结构发展到了现在的基于a s i c 硬件或网络处理器分布转发， 网络交换的路由器体系结构。2 0 0 2 年1 2 月，华为公司正式发布了第五代路由器 n e t e n g i n e ( n e ) 8 0 4 0 2 0 系列产品，标志着第五代路由器进入成熟的商用阶段。 l 誉蚓劂b 爵= = d 转发引擎- 卡1 l 鬈蚓倒b 。= = d 转发引擎z 卡2 交换结构 l 鬈倒恻旧l 卡n 导瓣 l 攀倒囤净 l 麓倒囤 器 图1 - 1以交换结构为中心的路由器体系 交换结构( s w i t c h f a b r i c ) 是宽带i p 路由器中的关键部分，是解决报文高速转 发的主要方式，各个接口单元的通信都是通过交换结构完成的，它的性能直接决 定了路由器的性能。图1 1 所示的是一个当今主流的高端路由器的体系结构图。 网络接口卡具有本地的快速处理器和高速缓存，具有独立处理分组的能力： 每个连接的第一个包被送到路由协议处理器的路由引擎上进行处理，路由引擎得 到了输出接口卡的端口号之后，将其传给输入网络接口卡，输入网络接口卡就在 1 电子科技大学硕士学位论文 本地高速缓存中增加一个表项。这样，该连接以后的分组就可以直接在网络接口 卡之间交换而无须再经过路由协议处理器。 当数据包到来时，转发引擎负责查找下一跳地址。转发引擎查找到下一地址 后，将其送给网络接口卡，这样，网络接1 3 卡就可以直接通过交换结构把数据包 送交输出端口。 由图1 1 可以看出，交换结构是整个路由器体系的核心部分。从目前研究趋势 来看，交换技术已经成为高速路由器的核心技术。口路由技术的发展也已经和交换 技术以及宽带技术的发展有机的结合在了一起。由于口网络中的数据包是变长的， 传统的处理变长数据包的方法在数据包进入交换结构之前，将变长的数据包切割 成定长的信元( c e l l ) ，再进入交换结构进行交换。这样，整个交换结构的各个交 换单元都是同步操作的，实现起来比较容易。这种方法交换的信息单元颗粒小， 时延小。但是，信元头开销将增加内部的交换容量。同时输出端对信元重组成p a c k e t 会引入时延，会使得输出端的缓存管理和队列调度的复杂性增加。随着交换技术 的发展，近年来出现了变长交换技术，即i p 数据包不经过切割而直接通过交换结构 进行交换。与定长交换相比，变长交换的实现相对要复杂，由于交换的信息单元 颗粒大，控制时延变得复杂。但是与定长交换相比，变长交换存在另外一些优势： 1 变长交换不会造成不必要的带宽浪费。切害, j r p 包的时候，包的长度不一定 刚好是信元长度的整数倍，因此切割后可能会产生小于信元长度的单元，这样会造 成带宽的损失。 交换结构 时分交换结构空分交换结构 厂 共享缓存 共享总线 单级交 结构 c r o s s b a rc l o sb e n e s b a n y a nt o m sm e s hh y p e r c u b e 图1 - 2交换结构的分类 2 不需要在数据交换前和交换后进行分割和组合操作( s a r ，s e g m e n t a t i o na n d r e a s s e m b l y ) ，因此在入端口处不需要一个额外的切割模块，而在出端口处则不需 2 i 第一章引言 要一个额外的组合信元的模块，节省了存储器资源以及信元重排序的规模。 基于以上原因，作为大容量交换中的一项有潜力的技术，变长交换技术在近 年来得到了广泛的关注。 1 2 交换结构的分类 交换结构总体上可分为两大类：时分交换结构和空分交换结构。如图l 一2 所示。 1 2 i 时分交换结构 在时分交换结构中，交换单元不能同时交换一个以上的输入端口数据。从交 换结构的角度看，每个输入端口的处理是串行的。时分的交换结构又分为共享总 线交换结构和共享缓存交换结构两类。如图1 - 3 所示。 总线或环 叫塑垒塑! ! 卜+ _ 叫塑些塑! ! 卜+ 叫输入端口2 卜刊输出端口2 卜+ 小甄丽计幅面砷 1 _ ji _ j ( a )共享缓存结构( b )共享总线结构 图1 - 3两种时分交换结构 1 2 2 空分交换结构 在空分交换结构中，从输入端到输出端有多条通道，这些通道可以同时工作， 多个信元可以同时从输入端到输出端。空分交换结构的交换容量等于通道的带宽 乘以可以同时工作的通道数目。与时分交换结构相比，空分交换结构的适用范围 更广，更容易实现扩容。空分交换结构可分为单级交换结构、多级交换结构和群 集交换结构【2 1 。 3 电子科技大学硕士学位论文 单级交换结构主要是指交叉连接矩阵结构( c r o s s b a r ) 。只要同时闭合多个交 叉节点( c r o s s p o i n t ) ，多个不同的端口就可以同时传输数据。图1 - 4 所示的是c r o s s b a r 的结构示意图。只要同时闭合多个交叉节点( c r o s s p o i n t ) ，多个不同的端口就可以 同时传输数据。从这个意义上，我们称所有的c r o s s b a r 在内部是无阻塞的，因为它 可以支持所有端口同时以最大速率传输数据。由于c r o s s b a r 的多个输入端口有可能 同时竞争一个输出端口，但是只有一个端口的数据可能通过，因此为了解决这种 出线冲突，需要c r o s s b a r 仲裁调度算法。i s l i p 就是一个被广泛使用的调度算法。 c i s c o 公司的高端路由器g s r l 2 0 0 0 系列中，交叉开关调度算法就是采用的i s l l p 算 法。 k i u p u t l。 p u t 2 p u t 3 p u n 一nn 寸 =皇= 已已已 =j oooo 1 11r1 图1 4c r o s s b a r 结构示意图 时分交换结构和c r o s s b a r 都属于单级交换结构，实现比较简单。当交换容量较 大时，尤其是对于今年来出现的t b i t 的超大容量交换，单级交换结构在增加端口和 提升线路速率上非常困难。多级交换结构就可以很好的解决容量扩展的问题。多 级交换结构是由多个交换单元互连起来，每个交换单元具有一整套输入输出，与 普通交换机类似，提供输入输出的连接，通过互联多个小的交换单元，就可以制 造一个大型的、可扩展的交换结构。多级结构之间的不同取决于交换单元之间的 互联方式不同，典型的结构包括b e n e s 网络、c l o s 网络、b a n y a n 网络、s h u m e 网络并 行分组交换( p p s ，p a r a l l e lp a c k e ts w i t c h ) 等结构。图1 - 5 示出了几种应用比较广泛 的多级交换结构。 4 第一章引言 ( a )b a n y a n 交换结构 ( c ) c l o s 交换结构 ( b ) b e n e s 交换结构 ( d ) p p s 交换结构 图1 - 5几种常见的多级交换结构 从网络拓扑上看，群集交换结构与多级交换结构类似，也是通过一些小的交 换结构构建大的交换结构。不同的是，多级交换结构内部的交换单元不与输入输 出端口相连，而群集交换结构通过各线卡上的交换单元堆叠成一个大的交换结构。 在这种交换结构中，所有节点的功能相同，每个节点既处理本节点业务，同时也 负责为别的节点传递业务。对于路由器中的交换结构来讲，每个节点对应一个输 入输出端口，同时节点还负责不同端口间的业务转发。群集交换结构具有很好的 自扩展性，即随着结构中节点数目的增加，整个结构的通信带宽，存储带宽和系 统的处理能力也同时增加。全连接结构就是一种典型的群集交换结构，如图2 6 ( d ) 。 在群集交换结构中，为减少节点个数增加造成的距离增加，通常一个节点与多个 节点互连，从而构成一种多维的拓扑结构，称为多维分组交换结构( m p s f ， m u l t i d i m e n s i o n a lp a c k e ts w i t c h i n gf a b r i c ) 。这种结构主要包含n 维m e s h 结构，n 维 5 电子科技大学硕士学位论文 t o r u s 结构，h y p e r c u b e 结构。图1 - 6 示出了几种典型群集交换结构。 ( a ) 4 x 3 x 3m e s h 网络 ( c )2 元4 维h y p e r c u b 。 1 3 国内外研究动态 图1 - 6群集交换结构 ( b ) 4 x 3 x 2t o r u s 网络 濯全，么 弋纨7 ( d ) 全连接网络 目前关于变长交换的研究很多，主要是研究c r o s s b a r 中的变长交换以及多级交 换结构中的变长交换。 文【3 提出的直接交换变长分组的c r o s s b a r 仲裁算法p b i s l i p ，按时隙配置 c r o s s b a r 。一个输入端和一个输出端被匹配后，要等到一个完整的p a c k e t 通过，才 能参加下一次匹配。匹配算法几乎和i s l i p 相同，也是分为r e q u e s t 一 g r a n t 一 a c c e p t 三个步骤。在不同端口进入的分组大小不同的情况下，p b i s l i p 算法存在不公平。 文 4 】对基于直接交换变长分组的c r o s s b a r 中最大权重匹配算法的稳定性进行研究， 提出了稳定性的改进方法。文【5 】对输入为p o i s s o n 数据源或自相似数据源情况下变长 分组交换的性能作了理论分析。 6 第一章引言 以上的这些研究都是针对交叉节点无缓存的c r o s s b a r 。变长交换也可以应用到 交叉节点带缓存的c r o s s b a r ( b u f f e r e dc r o s s b a r ) 中。文【6 】提出了在b u f f e r e dc r o s s b a r 直接交换变长数据包而不进行分割，并对4 4 的交换结构进行了仿真。文【7 】对 b u f f e r e dc r o s s b a r 进行变长交换做了进一步的研究，提出了p a r a l l e l p o l l e dv o q ( p p v o q ) 的交换结构，并且对最大包长为1 5 0 0 b y t e s 的数据包进行了仿真，通过仿 真的结果可以看出，这种结构的延时低于用i s l i p 调度的u n b u f f e r e dc r o s s b a r 。与前 面的相比，文邛1 对b u f f e r e dc r o s s b a r 变长交换的研究比较深入，不但用多种数据源 对这种结构进行了的性能仿真，还采用1 3 0 n m 技术实现了3 2 3 2 的交换结构芯片， 整个芯片的交换容量可以达至i j 3 0 0 g ，布线的面积为2 0 0 m m 2 ，功耗为4 瓦。 关于多级交换结构中的变长交换技术，也有大量的研究在进行。在文【9 】中提到 一种异步b a n y a n 网络，对变长的分组直接进行交换，这种交换的操作是在无连接 的网络环境中进行，在每个交换单元内部设有缓存，采用数据包的自路由技术， 直接对变长的数据包进行交换。另外在t a n d e m b a n y a n 和b a t c h e r - b a n y a n 结构中， 也可以应用变长交换技术。最初i 扫h u i 于1 9 8 7 年提丑m o o n s h i n e 交换机【加1 就是采用 的b a t c h e r - b a n y a n 网直接交换变长分组。文【“ 中提出了一种用s h u f f l e 结构来实现变 长交换的，交换结构采用了偏折路由和最短路由技术，交换单元内部无缓存，节 省了交换芯片的硬件资源。 1 4 主要的研究工作 本论文主要来源于两个项目：大容量交换网络仲裁和流控算法研究( 国家8 6 3 计划基金资助项目) 和超大容量交换结构( 华为2 0 0 5 高校科技基金项目) 。 在大容量交换网络仲裁和流控算法研究的项目中，本人主要负责研究交换结 构c r o s s b a r 中的变长交换，提出一种变长调度策略，参与o p n e t 进行交换结构的建 模。并在电子科技大学学报发表论文( b u f f e r e dc r o s s b a r 中的变长交换，该方 法已经向国家专利局申请专利，专利号申请号：2 0 0 5 1 0 0 8 9 1 3 2 7 。 在超大容量交换结构的项目中，本人主要负责跟踪国内外的超大容量交换结 构的发展动向，研究多级交换结构中直接交换变长分组的方法。本项目主要采用 排队论做为理论工具，采用o p n e t 作为仿真平台。在这个项目中，提出了一种支 持变长交换的b e n e s 结构中的数据包分发策略，该方法也在申请专利。 1 5 论文组织安排 7 电子科技大学硕士学位论文 本文的主要贡献在于研究了c r o s s b a r 和多级交换结构中的变长调度算法，在 b u f f e r e dc r o s s b a r 和b e n e s 两种交换结构中提出了直接交换变长分组的两种创新方 法。 第二章中对不带缓存的c r o s s b a r 中的变长交换算法进行了分析，解释了c e l l t r a i n 机制，比较了i p p 1 m ，p b i s l i p ，s o l ，p b w m w m 几种调度算法在性能上 的差异。第三章针对b u f f e r e dc r o s s b a r 提出一种变长调度方案，避免交换链路长时 间被长数据包的端口所占据，这样就保证每个端口数据流量的公平性，减少了平 均时延。这种结构同时整合了单播和组播业务。第四章主要是综述了变长交换在 多级交换结构中的应用，对b a n y a n ，t a n d e m b a n y a n ，b a t c h e r - b a n y a n ，s h u f f l e 几 种交换结构中的变长交换进行了分析。第五章提出一种在b e n e s 结构中的分发策 略，在变长的数据包经过b e n e s 分发网时，实现负载均衡，并且以o p n e t 为仿真平 台，对这种分发策略进行了仿真。第六章总结全文。 8 第二章交叉节点不带缓存的c r o s s b a r 中变长调度算法 第二章交叉节点不带缓存的c r o s s b a r 中变长调度算法 关于c r o s s b a r 中的变长交换调度算法，主要可以分为两大类：交叉节点不带缓 存的c r o s s b a r ( u n b u f f c r c dc r o s s b a r ) 和交叉节点带缓存的c r o s s b a r ( b u f f e r e d c r o s s b a r ) 。本章主要讨论交叉节点不带缓存的c r o s s b a r 的变长调度算法。 2 1 概述 最初的c r o s s b a r 交换技术主要是用在a t m 网络中，采用的都是定长交换技术。 当定长的a t m 信元到来时，为了保证在一个时隙内，一个输入端口的数据输出到 一个输出端口中，避免出线冲突，由调度器控制交叉节点的通断，定长的信元通 过c r o s s b a r 至t j 达输出端口。在定长交换中，各个交叉节点的闭合及信元的交换都是 同步的。当c r o s s b a r 用于变长i p 包交换时，沿用了这种机制。i p 包在输入端的线卡 被切割成定长的信元，再通过c r o s s b a r j 羞行交换。随着交换技术的发展，近年来出 现了变长交换技术，u p i p 数据包不经过切割而直接通过c r o s s b a r 进行交换。 为了提高变长交换的效率，解决对数据包切割和组合带来的缺陷，通常在数 据包到达入端口处时，并不采取真正物理上的切割数据包，而是逻辑的分割数据 包为定长的信元，在最后的逻辑信元上面添加一个尾部标志e o p ( e n do f p a c k e t ) ， 对定长的信元进行背靠背的传送，因此在传送的时候和到达出端口处收到的数据 包仍然是完整的，以此避免了组合数据包的操作。在数据通道上，也就是当某个 入端口开始交换一个数据包到出端口时，这个入端口一直保持和这个出端口的连 接，直到整个数据包被传送到出端口。基于以上的处理方法，就可以将一些定长 的交换算法转换成变长交换算法，这种机制也通常被成为c e l lt r a i n 机制。图2 1 就 是一个关于3x3 的交叉连接矩阵中使用c e l lt r a i n 机制的调度算法示意图。 在上图的结构中，在每一个时间间隔，将匹配的入端口和出端口分成以下两 个情况：忙端口和闲端口。忙端口指某个入端口和出端口已经在前一个时间片被 匹配起来，在现在这个时间片仍然在传输数据。闲端口指一对入端口和出端口没 有数据传送，或者刚刚传送完数据。 那么变长数据包交换时，在一个时间片内要保持忙端口的状态，也就是保持 正在传送的数据通道，同时对闲端口采用基于定长的交换算法寻找新的端口匹配。 9 电子科技大学硕士学位论文 2 2i p p i m 算法 图2 1应用c e l lt r a i n 机制的变长调度 最先将定长调度算法应用于变长调度领域的是g en o n g ，他在文【l2 】中提到的 i p p i m 算法就是利用上面的c e l lt r a i n 机制实现的一种变长调度算法。 p i m ( p a r a l l e li t e r a t i v em a t c h i n g ) 算法是基于定长交换提出的调度算法。p i m 算法希望通过一定数目的迭代步骤，快速的收敛得到最大数目的无冲突的端口匹 配。每一次得迭代包含三个步骤：r e q u e s t ，g r a n t ，a c c e p t 。 1 信元请求阶段( r e q u e s t ) ：对于所有没匹配( 建立输入，输出对应关系) 的 输入端口，如果它有信元需要交换，就向对应的输出端