（通信与信息系统专业论文）交换结构及其调度与带宽分配算法研究.pdf

摘要 摘要 本论文的研究主要分为两部分：第一部分是大容量可扩展交换结构及其调度 算法的研究；第二部分是以太网交换机的流量控制研究，结合公司项目，提出解 决方案。 随着互联网快速发展，网络承载的带宽需求也快速增长。光传输技术波分复用 的发展和成熟应用，使得网络传输链路不再是限制网络带宽增长的主要因素，而作 为业务节点的交换机、路由器已成为网络性能的“瓶颈”，不仅要提供基于端口的 高带宽，而且设备的端口更需要具有不时升级扩展特性，因此设计大容量可扩展 性的交换设备在设计下一代网络中占有关键的地位，成为目前国内外诸多学者， 技术专家关注的焦点。 目前业界对可扩展性交换结构的研究主要集中在多级交换结构，即是把多个 交换单元按一定规则连接起来，构成容量更大，端口数更大的交换结构。多级交 换结构按照内部连接方式的不同，可分为多种类型。其中的三级a o s 结构由于具 有很好的扩展性能，是最适宜用于构建可扩展的交换结构。本文首先对交换结构 的可扩展性进行了深入的研究，然后基于对d u n en c t 、o r l 【s 公司某交换芯片研究而 提出的改进的三级c l o s 结构的基础上，设计了基于流的调度算法，传统的用于多 级交换结构中的调度算法是受单级交换结构调度算法启发，主要的思想是解决图 的匹配的问题，基于端口寻求最大连接。目前业界已有不少经典的调度算法，这些 算法能够达到较好的性能目标，但也存在一些不足，比如：q o s 得不到保证。而 基于流的调度算法是按照流的属性给予服务，针对当前网络中业务多样性的特性， 调度算法能区分不同的业务，选择服务的级别，给予不同的q o s 保证，这正是最 近研究的热点。我们通过搭建仿真模型，验证了基于流的调度算法的性能，为构 建大容量交换结构及其调度算法提供了一个可行的方案。 本文的第二部分是对以太网交换机的研究，是对上海普然通讯技术提出的一 个通用问题的解决方案的研究：在以太网交换机中由于存在某一持续时间多个端 口同时向一个出端口发送数据的可能，直接的后果是出现流量拥塞，丢失数据包， 严重影响交换机的性能，因此针对这个问题，本文提出了动态带宽分配调度入口 流的解决方法：在系统外部设计一个独立的调度器，硬件用高速f p g a 实现，调 度器与交换端口和交换芯片互通，控制出口带宽在各竞争入端口的分配，达到避 摘要 免拥塞发生和保障一定包转发率与时延性能。在调度方法上相继提出了两种解决 方案：一，基于出口缓存调度；二，基于出口带宽调度。同时设计了两种带宽分 配算法：一，公平逆序算法；二，公平和流量整形算法。通过搭建仿真模型，验 证了方案的可行性。最后，对项目中的关注的更加细致的问题做了分析，给予了 参考的方案。 本文两部分都采用o p n i 玎搭建了仿真模型，对系统的多个方面进行的仿真验 证，对仿真的结果进行了深入分析，为工程实践提供了科学的依据。 关键词：交换结构，调度算法，调度器，以太网交换机 a b s i m d a b s t r a c t ，1 1 l i st h e s i sc o 船i s t so f 啊op a n s ：p a no n ei sf 伪e a r c h 衄t h el a r g ec a p a c i t ys c a l d b l e 刚t c l l i n gf a b r i a 彻dt h cf c l a t c ds c h e d u i i n ga 1 9 0 r i t h m s p a i nt w oi sr e s e a r c ho nt r a 伍c c o n 删o fe t h e i n e ts 们t c h ，w h i c hi sc o m b i i i e dw 油ac 0r p l d m t i o n sp r o j e c tt 0p r o v i d e s o i u t i o ns c h c m e s w i t ht h er a p i dd c v e l o p m e mo fi n t 啪e 也cr e q u i r e n l e n to fn e 咖) r kb a n d w i d t h i n c r e m e n ta l s o 鲫7 sd 掘啪t i c a l l y s i n c et h cd c v e l o p m e n ta n da p p l i c a t i o no ft h eo p t i c a l t r 锄s m i s s i o nd w d m t l l em a i nf a d o rt h a tl i m i t sn e “唧r kb 强d w i d t hi n c r e m 朋th 嬲 n c v 盯b e e nn 嘶r kt r 觚s m i s s i o nl i l l i 【s w i t c h 龉o rm u t e 髂勰n e t w o r ks e r v i c cp o i n t s h a v eb 啪t h eb o t t l e n c c ko fn e “v o r kp e 咖皿姐c e n e y 盯en o to n l yr e q u i r e dt op r 0 v i d e h i g hb 卸d w i d t hb 嬲e d 衄p o n ，b u ta l s ot om a l 【ep o nu p 掣a d c 舭e l y t h e r e f o i e ，t h ev m r k o fd 鼯i 伊o fl a r g cc a p a c i t ys c a i 曲l e 鲫i 姚c sl o c a t e si nt h ek e yp o s i t i o nd u r i n gt h e p r o 掣e s so fd e s i 伊i n gn c x tg e n e r a t i o nn e 伽。咄w h i c hh 嬲b c c nt h ca l t e n l i o nf o c l l so f m 孤yr e s e a r c h e 职a n dt e c h n i c a lc x p c n si nt h i sf i e l d a tp r e s e n t ，m er c s e a r c ho f s c a l a b l es w i t c hf 曲r i cm a i n l yc c n t r a l i z e si nt h e m u i t i - s 蜘，cs w “c hf a b r i ct h a ti si n t e r c o n n e c t i o no fm u i t i p l es w i t c hu n i t si nt e l l n so f s o m e 埘l e sf o rc o n s t r u c t i n gm o r e l a r g ec a p a c i t y a n dm o r cp o r t ss w i t c hf a b r i c m u l t i s t a g es w “c hf a b r i cc a nb ec l a s s 馅e di n t om 蛐yc a t e 9 0 f j c sa c c o r d i l l g t ot h e i n t e l = n a lc 0 姐e c t i 衄m a n n c ld u et ot h r s t a g ca o ss w “c hf 曲r i ch 勰a9 0 0 ds c a l a b n i l y c h a r a c i e r i s t i c ，i th a sb e c nt h eb c s tc h o i c ef o rs c a i a b l es w i t c h 脑t m d i o n t h j sp a p e r s 缸ts c c t i o ni ss t i i d y i n gi nt h e 鲫i t c hf a b r i c ss c a l a b i l i t yp r o p e n y s u b s e q u e n n yb 船e d o nt h ei m p m v e m 髓t0 ft h r e es t a g ec l o ss w i t c hf 曲r i c ，w eh a 、，cd e s i 弘c dt h en o wb 勰e d s c h e d u l i n ga 1 9 0 血b m 1 r a d i t i o n a l l yt h em u l t i s t a g c f a b r i c s s d l e d u l i l l ga l g o r i t h m s d e r i v e d 丘o ms i n 酉es t a g ef a b r i c ，s s c h e d u l i n ga l g o r i t h i l l sw h o s em a i nt h o u g h t i s m a t c h i n go fg r a p h s 柚df i n d i i l go ft h em a x i m u mp o r t s i l n e d i o n s u pt on a w ，t h e r cm m a n yd a s s i c a ls c h e d l l l i n ga 1 9 0 r i t l l m s ，t l l o u g ht h e yc a nr c a c hg o o dp e f f 0 咖卸c c ，t h e f e a r cs o m es h o r tc 距n o tb ei 印o r e d ，f o rc x 锄p l et h cl a c ko fq o sg i l a r a l l t e e o nt h eo 也c r h a n d ，t h cs c h e d u l i n ga l g o r i t h mb 髂e do nn o wc 牡s e n r i c cf l o w si nt c 姗so ft h e i r d i 疵r e n tc h a r a c t 甜s t i c s ，a i m i l l ga tt h ec i l 玎c mn e 脚o r kt r a f f j c ，sd i v e r s i t y ，i tp r o v i d c s t q o sg u 黝t e ea c r d i n gt o 日o w sr e q u i r c m e n t ，w h i c ha l s oi st h er c s e a r c hh o tp r 幅曲t l y 1 1 l i sp a p c rh 嬲c o n s t n l c i c ds i l n u l a t i o nm o d e lt ov e r i f ym en o wb a s e ds c h e d u l i n g a i g o r i t h m sp e “b r m a n c ca n dh 猫p r o v i d e daf e 勰i b l es c h e m e0 fc o i l s t m c t i n gl a 昭e c a p a d t y s w i t c hf a b r i 鼯柚ds c h e d u l i n ga 1 9 0 i i t h m s 1 1 l i sp a p e r sp a r tt w oi sar e s e a f c ho fe t h 锄e ts w i t c h ，w h i c hi ss o l u t i o ns c h c m ef o r g c n e r a lp m b l 锄b ys h a n g l l a io p l u 粕c o r p o n t i o np u tf o r w a r d ：t h e r ee x i s t sp r o b 曲m t y o fm u n i p l ep o n sp e r s i s ti ns e n d i l l gp a c k c tt oo n c 姗o ne 掣e 豁p o r t 蛐ga 咖t i n u o u s 劬e 缸e t h c m e ts w i t c 也t 1 i ed i r 。c tr e s u l ti so c c u n 姐c co ft m 伍c n g c s t i o n a n dl o s s e so fp a c k e tt i l a ta 虢c ts w i t c hp c r f o 】啪如c cb a d i y 1 1 1 e 坨f o r e ，i no r d 盯t or e l v e t h i sp r o b l e m ，w eh a v eb m u g h tf o 】r w a r d sam e t h o dt h a td y n 锄i c a l l ya l l o c a t e sb a n d w i d m f o rj n g r c s sn o w s ：d 骼i g nm i n d e 肼m d ts c h c d u l e ro u t s i d eo ft h es y s t e mt h a th a f d w a r e i i i l p l c m 锄t e db yf p g a 耽es c h e d u l e r 咖u l l i c a t e si n f o m a t i w i n ls w i t c hc b j p t h r o u g hh i g hs p e c di i l t e r f a c ea n dc 0 毗r o l si l l 掣e s sn o w t h ep 加口e c t sg o a li st 0r e a c h a v o i d a n c co f 仃a m cc o n g e s t i o n 卸dp r 0 v i d es o m ed e g r e ep a c k e td e l i v e r y 锄dd e l a y p e 面珊a n c eg l l a r 锄t w bh a v ep u tf o 州a r d 柳os c h e m e si nt e n 璐o fs c h e d u l i n g m c t h o d s ：0 n ei ss c h e d u l i n gb 弱e d 吼e 留e s sp o n s b u 虢rs t a t u s ；t h eo t h e ri ss c h e “h n g b a s c do ne 蓼e s sp o r t s b a n d w i d t h a tt h es 锄et i m e ，w eh a v ed 鹪i 印e d 伽ob a n d 耐d t h a n o c a t i o na l g 鲥t h m s ：圮o n ei s “触龃dr c v e r s ea l g o r i t h m ”；1 cs e c o n di s “f a i r 粕d s h 印i n ga l g o r i t h n l ”t h em o d c l so ft h e 铆0s c h e m c sh a v eb e e nc 0 i l s t n l c t e da n dt h e i f p e r f o 珊觚c e sh a v eb e 姐v c r i 丘e d 陆a l l y w eh a v ed i s c 惦s e dt h cp r o j e c t s d c t a n p m b i c m s 卸d 舀v e nr c f c r e n c cs c h e m 鼯 1 w op a n si nt h i sp a p c rh a v ea d 叩t e d f t w a r eo p n e tt oc o n s t m c ts i n l u l a t i o n m o d e l s ，柚dh a v em ns i m l l l a t i o m 舶mm a i i y 弱p e c t s ，a i l a l y z e ds j m u l a t i o nf c s u l t s a l lo f t h 鼯ew o f i 【sh a v ep r 0 v i d e ds d c n t i 丘cv e r i f i c a t i o nf o re n 百n e e r i n gp r a c t i c c 1 【e yw o r d s ：s 、) l ，i t c h i n gf a b 如s c h e d u l 堍a l g o r i t h m ，s c h e d u l e r ，e m c m e ts w i t c h 图表目录 图1 1 图1 - 2 图1 - 3 图1 4 图1 5 图2 1 图2 - 2 图2 1 3 图2 4 图2 - 5 图2 6 图2 7 图2 - 8 图2 9 图2 1 0 图3 1 图3 2 图3 3 图3 - 4 图3 - 5 图3 6 图3 7 图舢1 图4 2 图4 1 3 图 图4 5 图4 6 图表目录 交换结构参考模型1 交换结构的概念图示 交换结构分类 “2 a ) b 趾y 蛆网络内部阻塞b ) 三级a o s 网络”4 a ) 排头阻塞b ) 调度器方案- 7 4 4c r o s s b 盯交换结构9 基于c r o s s b a r 的排队几种类型1 0 三种b 蛆y 雏网络拓扑与内部阻塞1 1 a ) 三级a o s 结构b ) c l o s 结构内部阻塞1 2 输入排队v o q 结构” 图和它的匹配1 4 三步迭代过程1 5 i s u p 算法 d r r m 算法1 7 m s m 交换结构 改进三级m s m 型a o s 交换结构“2 3 输入级程序流程图2 7 输出级算法程序流程图2 8 仿真模型 输出端口带宽利用率 平均时延 链路平均负载 两级以太网交换机 交换机性能下降图示 v o q 调度器 调度时序 l s 逻辑结构 3 1 3 7 3 8 b c m 5 6 9 5 的动态缓存管理3 9 图表目录 图4 7 图4 8 图4 9 图4 1 0 图舢1 1 图禾1 2 图4 1 3 图4 1 4 图4 1 5 图禾1 6 图禾1 7 图舢1 8 图舢1 9 图4 加 图4 2 1 图4 2 2 图4 2 3 图4 2 4 图4 2 5 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 f s 基于端口的调度模块一 基于出口缓存调度的数学模型 3 9 4 0 公平逆序算法4 2 输出端口带宽利用率 不同调度时隙下平均时延 交换机在两种不同状态下时延图示“ 拥塞状态下输出端口带宽利用率 交互时序图” 4 3 4 4 一个输出端口的数学模型4 7 理想调度时隙 4 8 增大调度时隙数学模型4 8 基于出口带宽调度方案数学模型4 9 改善的基于出口带宽调度方案数学模型 璐中由令牌桶实现的s h a p c r 功能模块“ 4 9 5 0 f a i r 柚ds h a p i n g 程序流程图5 4 输出端口带宽利用率5 5 不同调度时隙下分组平均时延5 6 拥塞状态下的输出端口带宽利用率- 5 7 不同优先级队列的时延性能5 7 仿真模型的节点层模型6 1 s r c 模块的进程模型6 2 l s 模块的进程模型”6 3 f s 模块的进程模型6 4 调度器模块的进程模型6 5 s i l l l 【模块的进程模型”6 6 表2 1 变量定义 表3 1 队列状态数据库2 4 表4 1 常量定义4 7 表4 2 变量定义5 2 甜牾拍 主要符号表 缩写词 a n 讧 c o s c r r d d w d m f s f i f 0 h o l i r r m i sl 】咿 l s l r m s m p i m q o s r r r d s d s s p s u p t d s v l s i v o q w r r 主要符号表 英文全称 a s y n c h r o n o u st r 锄s f c fm 0 d e a 勰s0 fs e n ，i c e o d n c u r r 曲tr o u n dr o b i nd i s p a t c b j n g d c 璐ew a v c l e n g t hd i v i s i o nm u l t i p l 懿j n g f a b r i cs w i t c h f i r s t mf i 塔t o u t h e a do f i 血e b h 必n g n e 珀t i v cr 0 u n dr o b i nm a t c h i n g i t c r a t i v er 0 咖dr o b i nm a t c h i n gw i t hs i j i u n es w i t d i i j n k r a t e m e m o r y s p a c c - m e m o r y p a r a l l e l i t e r a t i v em a t i 埘n g q u a l i t yo f s e 妣 r o u n dr o b i n r a n d o md i s p a t c h i i l g s p a c c d i o ns w i t c h s t r i c tp r i o r i t y s e r i a l “n eh l t e r f a c cp f o t o c o l 砸m ed i v i s i o ns w i t c h v c r ) rl a r g cs c a l ei n t e 孕a t i o n r t l l a lo u t p u tq u e u i n g w e i g b t e dr o u n dr o b i l l 符号意义 异步转移模式 服务等级 并行轮询分配算法 密集波分复用 交换结构 先进先出队列 队头阻塞 迭代轮询匹配 s u 咿迭代轮询匹配 线端交换芯片 线路速率 缓存一空分一缓存 并行迭代匹配 服务质量 轮询 随机分配算法 空分交换 严格优先级 串行线路接口协议 时分交换 超大规模集成电路 虚拟输出队列 加权轮询 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的 说明并表示谢意。 签名： 日期。叩年，月 关于论文使用授权的说明 日 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：獭 导师签名： 李乐氏 日期：叩年岁j j 1 了目 第一章绪论 第一章绪论 随着通信技术和计算机技术的快速发展，互联网的数据流量急剧增加，同时 随着多媒体技术的发展与网络业务的差异化明显，对网络服务质量要求已不再仅 仅是提供“最大努力”的服务，而是能够区分不同业务请求，给予多个级别保障 的服务质量水平。网络传输链路随着光纤技术d w d m ( d e n w 打e l c n g t hd i v i s i m u n i p l e x i n g ) 采用，目前从容量和质量方面都己不再是限制网络发展的关键因素； 同样，随着计算机技术的发展，网络终端强大的处理能力也解决了用户对数据业 务的处理需求；作为网络业务节点的交换、路由设备成为构造高性能的宽带通信 网络的决定因素。要充分利用充足的网络带宽资源，就必须不时的对交换系统升 级，而事实上这是网络运营商最不情愿看到的事情，因为很多设备的升级就意味 着整个系统的替换，对成本难以控制，而且实旅复杂。因此交换系统的可扩展性 能变得尤为重要。一个可扩展的交换系统要求其端口数目随着需求增加，更重要 的是强调交换系统的性能不会因为端口数目的增加而下降。交换结构( s w i t c h f a b r i c ) 是交换系统的核心部件，交换结构的交换能力很大程度上决定了交换系 统的性能，交换结构选取的准确与否将直接影响交换系统的性能，解决交换结构 的可扩展性和服务质量的确定性也是近年来网络研究的热点和难点【2 j 。 1 1 交换结构概述 1 1 1 交换结构参考模型 输入端口 交换内辕 输出端口 i _ jl v 1 二二h 八 一厂i 土 图卜l 交换结构参考模型 l 电子科技大学硕士学位论文 如图1 1 所示，交换结构由输入端口，输出端口，连接输入输出端口的交换内 核组成1 3 1 。输入端口负责接收外部分组、切分分组为定长信元、发送信元至交换内 核功能；输出端口负责从交换内核接收信元、重装分组、发送分组到外部链路功 能；交换内核是交换结构核心，负责信元交换功能。交换内核交换的对象为定长 的分组，习惯称信元( c e u ) ，并不特指甜m 信元。交换结构传输一个信元的时间 称为一个时隙( t i m es l o t ) 。由于在多个不同的输入端口可能同时到达的信元都去 往同一个输出端日，而在一个时隙，输出端口只能输出一个信元，因此输出冲突 ( o u t p u t n t c n t i o n ) 不可避免。为了避免因为输出冲突造成丢包，必须在交换结 构内设置缓冲，使得当前时隙不能被传输的信元暂时存储在缓冲里，等待下次传 输的机会。根据缓冲放置的位置，可以分为输入排队和输出排队两大类。 在每个时隙，输出排队要求对缓冲区需要支持n 次写操作和至少一次读操作， 使得对存储器的访问速度至少是n 倍于链路速率，随着链路速率不断提高( 1 0 g b p s 甚至更高) 和端口数增多，这将成为系统的瓶颈。 目前高性能交换机和路由器很多都采用输入排队，输入排队内部不需要加速， 但存在队头阻塞问题( h e a do fl i n eb l o c l 【i n g ) ，研究表明，当端口数较多时，在所 有输出均匀分布的b e m o u m 到达下，输入排队只能达到5 8 6 的吞吐率【4 】。v o q ( v i n u a lo u t p u tq u 印i n g ) 结构能完全解决队头阻塞【5 】，即在每个输入端设置n 个 n f 0 队列用于存储分别去往n 个输出端口的分组。配合输入排队调度算法，使得 理论上吞吐率达到1 0 0 。交换结构中的几个概念如图1 2 所示。 交挠结构 输出冲突交换结构 茭：鞋i 嚣奖瑟 a ) 输出冲突 交换结构 b 1 输 捧队c ) 输出排队 善蛰一 1 丁缸a + 厂+ 1 1 r n 计呻h 厂p 鬈三摊：蔷茭：薰叫i ：蔷 4 = j 廿+ 匕二= + 4 1 q 。料j ! 卜 d ) 队头阻塞_ i = ：坫l 工删 、 2 第一章绪论 1 1 2 交换结构的分类 交换结构按照交换内核的交换技术不同主要分为两大类：时分交换( t d s ) 和 空分交换( s d s ) 。时分交换迸一步分为：共享存储类型和共享媒介类型；同样， 空分交换进一步分为：单路径交换和多路径交换嘲，如图卜3 所示。 交换结构( s 椭自撕c ) i 厂 时分交换c r d s ) 空分交换( s d s ) 厂- 广j ，共 存储，共 媒岔 单路径 多踌径 ( m 删m 锄哪蛳脚m e d i ) ( 罩嘲e p a m ) ( n 丑t 洒m ) i 广n 厂_ t 厂 c 陆恐蒯脚“a u 舯枷砌m 秭 b a 珂她 图卜3交换结构分类 时分交换结构，就是把时间划分为不同的时间片，使得不同的信元在互不相 同的时间片通过交换结构。在时分交换结构里，有一个单一的通信通道被所有从 输入端口传输到输出端口的信元共享。这个通信通道可以是总线，环，存储器等。 时分交换结构的主要不足是：内部通信通道的带宽限制，比如总线带宽、环带宽、 存储器的读写速率等不可能无限制的增加，致使这种结构不适宜用于高速交换系 统；但由于这种结构是所有的信元经过同一个通信通道，很容易扩展支持组播、 广播，方便实现网络中需要组播或广播的应用。 荏高速分组交换系统中通常采用空分交换结构。相比于时分交换结构，空分 交抉结构为输入输出端口提供多条物理通路，相互之间并行工作，使得多个分组 能够同时通过交换结构。这种交换结构的交换能力是所有通路传输能力之和，理 轮上是不受限制的，但实践上受物理实现方面的一些限制，比如芯片引脚数，连 接的限制和同步等。 空分交换结构可以按照任意一对输入输出端口之间的通路数量分为两类：单 通路结构( s j n 酉ep a i h ) 和多通路结构( n m h ip a m ) 。前者比后者需要简单的路由 控制，而后者比前者具有更强的容错能力。在图1 2 中，单通路结构中c r o s s b a r 和b a n y a n 结构比较常用，而多通路中c 1 0 s 结构适合用于构建大容量交换结构，因 电子科技大学硕士学位论文 此我们的研究也主要集中在这里。 1 1 3 交换结构的可扩展性分析 交换结构具有可扩展性，即是要求交换结构在性能不降低的前提下，按需增 加交换结构的端口数目或端口交换容量。灵活性，可靠性，经济性都是需要考虑 的重要方面。 交换结构的扩展性主要体现在两方面： 1 一个具有良好可扩展性的交换结构，其内部链路的加速比越小越好， 因为加速比小表明对内部链路带宽需求越小，对存储器带宽越低，从而具有更好 的可实现性。 2 随着线速率的提高和交换端口数的增大，一个良好的可扩展性交换结 构应能提供较高的交换容量及提供较好的服务质量保证。 单级交换结构在目前技术下，一般不能做到很大，般在1 2 8 1 2 8 ，在可扩 展性方面没有优势。目前广泛采用的方法是把多个交换单元按照一定的拓扑结构 互连起来，构成一个交换网络。 很多交换网络被用来构建可扩展性网络；环绕网络( t m u so rm e s h ) 、超立方 网络( h y p e r c u b e ) 、b a n y a n 网络和c l o s 网络等。在通信网络中，通信模式和网络 流量模式的不确定性，要求交换网络必须是无阻塞的，即是要求交换结构能够为 任何一对空闲的输入输出建立连接。环绕网络和b a n y 卸网络存在内部阻塞，超立 方网络扩展要求不切实际的内部链路数。 目前实用的大容量交换结构多采用c 【0 s 交换网络，由于c l o s 网络内部无阻塞 f j ，能容易的通过增加模块来扩展端口，也成为最有前途的可扩展的交换结构。 b 胁y 蛆网络内部阻塞【8 】【9 】和三级c l o s 网络如图1 - 4 所示 内部阻塞 输入级中同级 输出级 曲b 锄y 姐内部阻毫 b ) 三级c l o s 结构 图l - 4 a ) b a n y a n 网络内部阻塞b ) 三级c l o s 网络 4 第一章绪论 1 2 本文需要解决的问题及解决方法 本文的研究工作主要包括两大部分：交换结构及其调度算法研究和以太网交 换机的交换结构及其带宽分配算法研究。 1 2 1 可扩展性的交换结构及调度算法研究 三级c 1 0 s 网络由于具有良好的可扩展性，常被用来作为大容量交换系统的交 换结构。由于三级c 1 0 s 网络不具有自路由功能，在每个时隙的开始，都必须要有 仲裁算法来决定输入端口与输出端口的连接匹配问题。受输入排队交换结构的调 度算法的启发，在三级c 1 0 s 结构仍然采用图匹配的思想，与输入排队的调度算法 不同的是匹配的过程包括两步：输入队列与输出链路匹配；输入模块与中间模块 匹配。 三级c l o s 的一种实现棚a n r a 【埘，是m s m 型( 第一，三级是存储模块，中 间级是无缓存的( r o s s b a r 模块) ，内部采用随机分配算法( r 卸d o md i s p a t c h i n g s 曲e m e ) ，由于在中间级不可避免的存在碰撞，要达到1 0 0 的吞吐率是不实际的， 除非内部链路带宽加速1 6 倍左右1 1 0 l ，显然这是不利于交换结构的扩展能力。e 0 h 等人提出的基于轮循的并行轮转分配算法( c r r d ) i 儿】，能在不需要内部加速的情 况下，达到1 0 0 的吞吐率，但需要经过多次迭代。 【1 】中作者通过对d u mn c t w o r k s 提供的交换芯片研究，提出了改进m s m 型的 三级c l o s 结构，并提出了a c b s ( a s y n c l l r o n o u sc r e d “b a s e ds c h e d u l i n g ) 调度算 法和c b s t d m ( c r c d i t b a s e ds c h e d u l i n gw i t ht d m ) 调度算法，这些调度算法与传 统的图匹配算法的不同在于：一是采用分配输出端口带宽给竞争输入端口的思想， 把数据从输入端口“拉”到输出端口，一次匹配的过程，节省了交换数据之前的 仲裁对问；二是调度算法是完全基于流的调度，能够根据流的属性不同，来提供 区别的服务，能够提供更好的服务质量保证。作者通过仿真验证了算法的性能， 从而证明交换结构和调度算法的可行性。 本文在此基础上，提出了改进的调度算法，算法本身仍是基于流的，同样也 是一次匹配的过程，主要的不同在两方面： 1 提出分配带宽的不同策略，尽量减少在输入模块由于链路数限制而丢失过 多带宽的情况； 2 改变了第一级路由，能够避免第二级碰撞造成的吞吐率下降问题，同时支 持从长期统计意义上负载平衡。 电子科技大学硕士学位论文 通过研究发现，这种改进的交换结构能够轻易的增加模块来扩展交换规模， 同时调度算法的分布式操作，也能很好的支持交换结构的扩展。硬件实现简单。 1 2 2 以太网交换机的交换结构及其带宽分配算法研究 以太网已占据了9 0 的局域网市场，而以太网也从最早的共享式到现今的交 换式以太网的转变，以太网的传输介质和连接中转设备也从最早的粗同轴电缆和 集线器发展到单模光纤和交换机。以太网交换机从最简单的多端口集线器发展到 现在功能强大的支持链路汇聚、虚拟局域网( a n ) 、口交换等复杂的系统。可 以肯定的是，以太网交换机支持的功能将会越来越全面，而且以太网也己不再仅 仅限于小范围局域网，而是会向城域网，甚至广域骨干网发展，以太网交换机也 会不断的从1 0 m b p s 向1 0 g b p s 甚至更高的带宽方向发展【1 2 1 。 在交换机的设计中，为了避免流量拥塞，通常采用反压( b a c kp r e s s u r e ) ，当 端口状态超过某一规定的门限，立即产生反压帧( p a u s e 丘a m e ) ，发往输入端口， 通知输入端口暂停一段时间发送数据，使输出端口有时问来处理拥塞的流量。这 种反压机制是来自于反馈理论，能够根据资源的利用情况，较精确地控制交换机 的资源在所有请求者之间的合理分配，不会因为某一端口或用户的接入带宽过高， 造成交换机的性能下降。 反压机制带来的问题是排头阻塞( h o l ) ，针对某一输出端口拥塞而产生的反 压帧会叫停所有入端口，即使入端口的数据不是发往拥塞端口，直接的影响是交 换机性能下降，包括吞吐率下降和平均时延增大。 项目问题描述：多个端口同时向一个端口发送分组，造成输出端口缓存溢出， 丢失数据包，同时产生反压帧，造成排头阻塞，系统性能下降。 为了解决这些问题，本文设计了调度器来调度入口流的方案，先后设计了两 种调度方案：一是基于出口缓存调度的方案；二是基于出口带宽调度的方案。同 时在带宽分配算法方面设计了两种带宽分配算法：一是公平逆序带宽分配算法； 二是公平流量整形算法。通过仿真验证，两种方案都能够保证不丢包，同时系统 性能得到控制，包括交换机包转发速率和平均时延。 项目问题和解决方案如图1 5 所示。 6 第一章绪论 输入端口输出端口输入端口 收到反压帧停止发送 a 1 捧头阻塞 图卜5 1 2 3 本文主要贡献 输出端口 b ) v o q 调度器 a ) 排头阻塞b ) 调度器方案 1 研究了各种类型的交换结构的可扩展性能，分析比较了调度算法的特性； 2 基于改进三级m s m 型a o s 网络，提出了基于流的调度算法； 3 搭建了三级m s m 型交换结构仿真模型，对基于流的调度算法迸行了仿真验证； 4 为以太网交换机性能下降问题提出了解决方案，通过理论分析与仿真验证，为 公司提出了两种可实现的方案； 1 3 全文的组织安排 全文共分为六章，每章内容组织安排如下： 第一章：绪论，介绍了交换结构的基本理论知识，同时对交换结构的可扩展 性进行了分析，介绍了需要解决的问题，以及本文的贡献； 第二章：交换结构及调度算法介绍，对输入排队调度算法和三级c l o s 交换结 构的调度算法做了详细的介绍，为本文的背景知识； 第三章：对改进的三级m s m 型c l o s 结构作介绍，设计基于流的调度算法， 并对仿真结果进行了分析； 第四章：针对以太网交换机存在性能下降的问题，设计了调度器调度入口流 的方案，就如何调度设计了两种调度策略，就带宽分配设计了两种带宽分配算法， 在每个策略后都给出了仿真结果并对结果进行了分析； 第五章：介绍了网络仿真建模的方法和以太网交换机仿真模型的各个模块的 设计。 第六章：总结全文。 7 电子科技大学硬士学位论文 第二章可扩展交换结构及其调度算法研究 本章对交换结构的可扩展性和目前业界已有的经典调度算法做详细分析研 究，为后续章节做好铺垫。 2 1 可扩展交换结构 交换结构是交换系统的核心，从系统资源的利用方式，可以分为时分交换和 空分交换。时分交换即是所有端口分时共享交换资源，包括总线，环和存储空间， 这种结构适合用于小规模交换系统，一旦交换规模增大，同时随着端口线速的提 高和端口数目的增多，共享资源的允许接入的最大访问速度将必定成为系统性能 的瓶颈，因此高性能大容量的交换系统通常采用空分交换结构。 空分交换其实早在电话系统的电路交换中就被采用，在一个时刻，能为多条 话务建立连接，多个用户共享交换资源，达到并行操作的目的。同样，在分组交 换系统中，空分交换成为主要的交换结构形式。空分交换结构按输入输出能建立 的连接数可以进一步分为单路径交换结构和多路径交换结构；按交换结构的内部 构成可以分为单级交换结构和多级交换结构。这两种分类方法彼此独立，只是从 不同方面对交换结构的属性进行划分。下面将详细介绍几种常用交换结构，并对 其扩展性进行分析。 2 1 1c r o s s b a r 交换结构 c r o s s b 盯交换结构早在电路交换中就被采用，如图2 1 所示，交叉连接点由电 子开关实现，每条输入线都通过电子开关与所有输出线连接，数据能快速通过交 换结构，实现交换。在分组交换结构，c r o s s b a r 结构也占有非常重要的地位，很多 商家生产的交换机，路由器都采用c 幻s s b a r 结构或其变形。 8 第二章可扩展交换结构及其调度算法研究 图2 一l4 4c r o s s b ”交换结构 图2 1 中是4 x 4c r o 豁b 缸交换结构，4 条入线，4 条出线，每对入，出线之间 用交叉连接点连接，交叉连接点的数目是入( 出) 线数的平方。交叉连接点有两 神状态：c r o s s 状态，b a r 状态。它们分别代表上下，左右连通和左下，上右连通。 为任何