（通信与信息系统专业论文）基于cicq排队机制与调度策略的研究.pdf

信息 ：程大学硕七学位论文 摘要 交换结构和调度策略作为路由交换设备中的核心技术，其性能直接影响甚至决定路由 交换设备的性能。近年来随着现代网络技术的迅猛发展，互联网在总体规模和体系结构上 发生了重大改变，传统交换调度机制已经成为制约网络规模进一步发展的瓶颈之一，网络 核心结点路由交换设备的交换性能正面临严峻的挑战。 论文结合国家“十五”8 6 3 计划信息技术领域“高性能宽带信息网( 3 n i e t ) ”重大专项 课题大规模接入汇聚路由器( a c r ) 系统性能和关键技术研究( 简称a c r ) 的研发，从交 换系统的普遍模型出发对现有的交换系统进行了分类和比较，对该领域的成果进行了较为 全面的总结，并基于带缓存交叉开关这一新型交换单元，在高速环境的可扩展性、组播支 持方面进行了研究，为a c r 构建了一种合适的交换系统解决方案。本文主要工作如下： _ 针对目前交换技术领域理论分析的不足以及仿真实验评价手段缺乏对交换系统性能评 估的有力支撑，采用系统级设计方法和面向对象技术设计实现了一种专用的交换技术 性能仿真与评价系统一s p e s ( s 谢t c hp e r f 0 吼a l l c ee v a l u a t i o ns v s t c m ) 。具有良好的可扩 展与可继承特性，为交换技术领域的技术创新和方案设计提供了一个基础研究平台。 - 分析了具有良好可扩展性交换结构和调度策略设计的基本准则。依据这一准则重点研 究了基于联合输入交叉节点排队交换结构调度算法的设计，提出了一种基于份额的动 态轮询调度策略f d r ，其算法复杂度仅为o ( 1 ) ，具有良好的动态与可扩展特性。s p e s 系统仿真结果表明f d r 具有良好的吞吐量、时延和抗突发性能。 从传统交换结构支持组播交换方面存在的不足出发，提出了支持单组播混合调度的交 换结构一m c i c q ( m u l t i c a s ts u p p o n i n gc i c q ) 。该结构能够有效解决单组播在交叉开关 内部的带宽冲突问题，采用简单的m f d r 调度策略就可以获得良好的性能。针对单组 播业务对q o s 的不同需求，在m f d r 的基础上给出了m f s 调度策略。m f s 除具备良 好的可扩展特性外，还具有能够为单组播业务提供不同的带宽保证能力。 依据a c r 的研制需求，针对该路由器的特点，以及综合考虑系统性能、设计成本和工 程开发周期的基础上，为a c r 设计了一种具有组播支持能力的交换系统工程解决方 案，满足了其在可扩展性、组播支持方面的需求。该工程实现方案己在大规模接入 汇聚路由器( a c r ) 系统性能和关键技术研究项目的路由器设备实际研发中得到成功 应用。 关键词：交换结构，带缓存交叉开关，调度算法，动态轮询，组播交换 第v i 页 信息工程大学硕士学位论文 a b s t r a c t s 丽劬i n gf a b r i c sa n ds c h e d u l i n gp o l i c i e sa r et h cc o r et e c l l i l o l o g i e so ft 1 1 ef o u t i n ga n d s w i 洲n ge q u i p m e m ，a n d 协e i rp e r f o r i i l a f l c e h a sd i r e c te 丘c c t s 柚de v e nd e t e r i 】1 i n e sm e p e d - 0 咖a n c eo fm er o u t i n ga n ds w i t c l l i n ge q u i p m e n t ，w i t l it l l ef 酤td e v e l o p m e n to fi n f o m l a t i o n t c c i l n o i o g y i n t e m e th a su n d e r g o r i e 掣号a tc h a i l g e si nt 坞o v e r a i is c a i ea 1 1 da r c i l j t e c t u r ei nt h ei a s c f e wy e 盯s t r a d i t i o n a ls w i t c h i i l ga n ds c h e d l l l i i l gm e c h 枷s m sh a v eb e c o m em eb o t t l e n e c k sf o r f 鼬e rn 咖o r kd e v e l o p m e n t s c o m b i n e dw i mt h e s e 鲫c h 粕dd e v e l o p m c n to ft l l e p r d j e c t “r e s e a r c ho ng y s t e m p e r f o m l a n 伪孤dk e yt e c h n o i o g i e so fi a 唱e s c a i ea c c e s sc o n v e f g e n c er o u t c r ( a c r ) ”s u p p o r t e d b yt h em 勾o rd e d i c a t e dr e 船a r c hp r o j e c to f 吐1 eh i 曲p e r f 0 珊a n c eb m a d b a n di n f o m 鲥o n n e t w o r k 吼d e rc h i i l an a t i o n a lr e s e a r c ha n dd e v e l 叩m e mp r o g r a m8 6 3f o rt 1 1 et e n m f i v e - y c a r p l a i l i nt h ei n f o r i i l a t i o nt e c h n o l o g y ，t t l i sd i s r t a t i o nc l 嬲s i f i e sa n dc o m p a r e st t l ec u 盯e n t s w i t c h i n gs y s t e m s 舶mt h ep e r s p e c t i v eo f 协eg e n e r a im o d e lo fv a r i o 璐s 晰t c h i n gs y s t e m s ，a n d a r i z e sr e s u l t sa c h i e v e di nm i sa r e a b a do nt l l en e wb u f 诧r c dc r o s s b 甜s w i t c l l i n gl | l l i t ，i t c o m e su pw i 也r e s e a r c h c si n t ot h ee x t e n s i b i l 时a i l dm u l t i c a s ts u p p o n i n gs c h e m emt h c h i 曲- s p e e de n v i r o m e n t ，c 陀a t i n gas u i t a b l e l m i o nt ot h es 晰t c h i n gs y s t e mf o ra c r i t s 啪i l l w o r ka n dc o n 砸b u t i o n sa r eo m l i n e da sf o i l o w s ： -d u et ot l l e d e f i c i e n c y o ft h e o r y a i l a l y s i s i ns w i t c h i n gt e c h n o l o g ya i l dm el a c ko f s y s t e m - l e v e ls u p p o r to ft h e 州t c l l i n gt e c h n o l o g y 舶ms i m u l a t i o na i l de x p c r i m e n 协l e v a l u a t i o nt o o l s ，ad c d i c a t e ds w i t c h i n gp e r f 0 加a 1 1 c ee v a l t i o ns y s t e m ( s p e s ) i sd e s i g l l c d a n di m p l e m e n t e db ya d o p t i n gs y s t e m i e v e ld e s i g nm e t h o d sa n do b j e c t o r i e n 钯dt c c h n 0 【o g y i th a 8g o o dc x t e n s i b i l i 够a n df o l i o 、- o nf e a m r e sa n dp m v i d e sab a s i cr c s e a r c hp l a t f o 衄f b r t c c 量l i l i c a li l l i l o v a t i 帆a r i ds c h e m ed e s i g no f t h es w i t c h i n gt e c h n o l o g y 一 t h ed i s s e r t a t i o na 】1 a l y z e sm eg l l i d e l i n ef o rd e s i g n i n gh i 曲e x t e n s i b l es w i 纰i n g 卸d s c h e d u i i n ga l g o r i t h m s b a s e do nt h i sg u i d e l i n e ，i tf o c u s e si t sr c s e a r c ho nt h ed e s i g no f t t 坼 s c h e d u l i n gp o l i c i e sf o rc o m b i n e di n p u ta i l dc r o s s - p o i mq u e u i n gs w i t c h i n gf a b r i c 锄dc o m e s u p 毗f d r ( f a i r 柚dd y n 锄i cr o u n d - m b i n ) a l g o 删瑚，w l l o s ec o m p l e x 姆i so i l l yd ( 1 ) i t l 脚e x c e l l e md y n a m i ca n de x t e n s i b i l i t yt 1 1 es j m u l a t i o nr e s u l t so ft h cs p e ss y s 0 e ms h o w t t l a tt h ef d ra 1 9 0 r i t h me ) 【l l i b i t sg o o dt 置l r o u g h p u t ，d e l a ya n da i l t i b u r s tp e r f l 0 册a n c e 一 i i lo r d e rt 0o v e r c o m et h cd e 舭i e n c yi ns u p p o n i n gm u l t i c a s ti nc u 圩c n ts “t c h i n gs y s t e m s ，t h e d i s s e n a t i o np r o p o s e san e ws w 沁h i n gf a b r i cm c i c q ( m u l t i c a s ts u p p o r t i i l gc i c q ) w h i c h s u p p o r 协t h eu n i m u l t i c a s th y b r i ds c h e d u l i n g ，a n ds c h e d u l i n gp o l i c i e sm f d r 觚dm f s w h i c hs 叩p o r tt h cp a r a i i e ld s 嘶b u t c du n i m u i t i c a s ta r ea i s op r o p o s e d w i mt h e 鼠u t s p l i t t i n gm e c h a l l i s m ，b o t hm f d r a i l dm f sc a l la c h i e v eg o o dp e r f b n n a n c ew i t l l o u ts p e e d u p ， 蛐d 圯i rc o m p l e x 时i so i l l yd ( 1 ) m f ss c h c d u l i n gp o l i c yc 锄a l s op r o v i d ed i 任吼n t b 锄d w i d t l lg u a 舢t c e s 矗) r 蚰i - ，m u l t i c 嬲tt r a 简c ，s i m u i a t i d nr c s u h 舶d e rs p e ss h o wt h a t b o t hm f d ra n dm f sc 龃a c h j e v eg o o dp e 面咖a n c e -f f o mt l l ed e v e l o p m e mr c q u i 陀m e i l t so ft l l ea c rr o u t e r 柚do r i e n t e dt o w a r da c r f e a t u r e s ， 第v l i 页 信息工程大学硕士学位论文 s u c hf a c t o r s 私s y s t e m a t i cp e r f b 蛐a i l c e ，d e s i g n i n gc o s ta i l dd e v e l o p m e n tc y c l eh a v eb e e n 戗汜ni n t oa c c o 蚰t as y s t e ms o l i n i o nh b c e np r o v i d e dh e r e i nf d ra c rt os u p p o r tm u l t i c a s t ， i tn 懈恕t h ef e q u i r e m e n t si n e x t e l l s i b i l i 哆a r l dm u l t i c 私ts u p p o n i i 培i t s 饥g i n e e f i n g i m p l 铷e n t a ：t i o ns c h c m e 啪b e e ns u c c e s s 伽l ya p p l i e dt 0t h ea c t u a ld e v e l o p m e n to fr o u t i n g a n d s 、】l ，i t c h i n ge q u i p 嘲l tu n d e rt l l ep 删e c to f a c r k b yw b r d s ：s 谢t c h j n 舀b u 彘r e dc r o s s b 鸩s c h e d u i i n 舀d y n 锄i cr rm u l t i c a s ts w i t c h i n g 第v i l i 页 信息工程大学硕士学位论文 表目录 表1s p e s 目前集成的交换结构与调度算法1 6 表2a s i c 和f p g a 的指标比较4 l 表3 吞吐量性能测试结果4 8 第1 v 页 信息工程大学硕士学位论文 图目录 图1 单光纤传输容量和路由器交换容量增长趋势对比1 图2 交换系统模型6 图3 输出排队交换结构模型，7 图4 输入排队交换结构模型9 图5 联合输入输出排队交换结构模型1 l 图6 联合输入交叉点排队交换结构模型1 2 图7s p e s 系统交互界面1 5 图8 交换系统性能仿真系统结构模型1 6 图9 联合输入交叉点排队交换结构模型2 1 图l o 马尔科夫链状态转换关系图2 2 图l lf d r 输入与输出调度的伪码描述2 6 图1 2 线形和非线性分配函数影射示意图2 7 图1 3 贝努利业务源下算法性能仿真结果，2 7 图1 4 突发业务源下算法性能仿真结果2 8 图1 5 不同x b 大小下交换系统的时延性能2 8 图1 6h o t s p o t 业务源下各种算法的吞吐量性能2 8 图1 7 突发业务源下算法的抗突发性能2 9 图1 8m c i c o 交换结构3 2 图1 9 贝努利和突发均匀业务流模型下各种算法时延性能3 6 图2 0 贝努利与突发业务源不同组播比例下的平均时延性能3 7 图2 l 不葡组播队列数下系统平均时延性能3 7 图2 2m s f 和m r r 带宽性能仿真结果3 8 图2 3a c r 路由器系统总体结构4 0 图2 4 端口交换系统功能模块框图4 1 图2 5 输入调度单元和交叉点调度单元硬件功能模块框图4 2 图2 6 单队列状态监控硬件电路实现4 3 图2 7 份额生成模块硬件电路实现4 3 图2 8 组播请求发生模块硬件电路实现4 4 图2 9 单播优先级仲裁硬件电路实现4 5 图3 0 输入端口h i s 调度模式硬件实现原理图，4 6 图3 1 单播优先级仲裁模块硬件电路实现4 7 图3 2 时延性能测试结果4 8 第v 页 原创性声明 本人声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写 过的研究成果，也不包含为获得信息工程大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文版权使用授权书 本人完全了解信息工程大学有关保留、使用学位论文的规定，本人授权信息工程大学 可以保留并向国家有关郁r 了或机构送交论文的复印件狃毫子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 学位论文作者签 作者指导教师签 信息工程大学硕士学位论文 第一章绪论 随着现代网络技术的迅猛发展，互联网在总体规模和体系结构上发生了重大改变：在 骨干传输网上，光传输链路代替了传统的电传输链路，o c 1 9 2 、o c 7 6 8 乃至更高速率的商 用接口技术稳步出现，网络核心节点交换容量从g 比特级向t 比特级转型：另一方面，边缘 网络承载业务类型呈多元化发展，移动化、宽带化和多媒体化成为现代网络的发展趋势。 因此，作为核心组网结点的路由交换设备在交换能力以及为新型业务提供服务质量 ( q u a l 崎o fs e r 、，i c e ，q o s ) 保障方面将面临新的挑战；交换结构与调度策略作为路由器设备 中的关键技术将成为互联网发展的瓶颈，寻求适合互联网发展需求的交换结构与调度策略 成为交换技术领域亟待解决的问题。 1 1 课题研究背景 在过去3 0 年间，互联网经历了一个飞速发展的时代，以应用为驱动，互联网正朝着高 速化和宽带化的方向演变，由单一的数据传送网络发展成为数据、语音、图像和实时多媒 体信息的综合传输网络。作为高性能宽带信息网络的重中之重，核心路由交换设备必须能 够适应信息容量的急剧膨胀和网络业务的多样化需求，从而为高性能宽带信息网络的建设 和运营提供一个具有良好扩展性、支持新型多媒体业务和具有服务质量保障能力的基础平 台。然而现有交换技术却面临着各种严：峻的挑战： 第一，光传输技术的飞速进步和网络业务量的爆炸性增长迫使路由交换设备必须能够 支持更高的端口速率和提供更大的交换容量。目前光纤传输带宽正在沿着每9 个月增大一 倍的超摩尔定律发展，而路由交换设备的交换容量却受限于每1 8 个月增大一倍的摩尔定 律，这使得路由交换设备的发展速度远远滞后于传输设备的发展速度。图l 给出了单光纤 传输容量和作为网络节点的路由交换设备交换容量的增长趋势对比关系。传统交换结构由 于内部加速问题或者是调度算法复杂度问题，可扩展性受到了限制以致无法满足支持更高 端口速率和提供更大交换容量的路由交换设备的客观需要。 1 9 9 82 0 0 22 0 0 6 年份 喜 q 一 蓑 釜 薹 1 9 9 21 9 9 41 9 9 61 9 9 82 0 0 02 2 啪42 0 帖 年份 图l 单光纤传输容量和路由器交换容量增长趋势对比 第l 页 o 0 0 o o 0 l o 0 o o o l o o o 0 l o 0 0 l 0 o 1 o 1 l 吾口。一。一肄舞啦雹姑鬟井 笪星三墨奎堂堡主堂垡丝茎 第二，网络的多元化发展导致了许多新型业务的出现，如视频点播、远程教学、网络 电视等，这些业务的一个显著特征就是具有组播性。随着组播业务上层应用技术的逐步成 熟，网络中组播业务所占的比例正在逐年递增【l j ，在下一代网络( n e x t g e n e r a t i o n n e 铆o r k n g n ) 中，支持组播已经成为网络节点设备的强制执行标准【2 】。然而，传统交换技术的组播 支持机制存在加速比过大、实现成本过高和调度算法过于复杂等难题，可扩展性较差，在 高速环境下难以为组播业务提供良好的支持。因此，研究能够高效支持组播的交换技术是 提供多种综合业务的高性能宽带信息网络的重要保障。 为适应新形势的发展需要，国家数字交换系统工程技术研究中心承担了国家8 6 3 计划 信息技术领域“高性能宽带信息网( 3 t n e t ) ”重大专项课题大规模接入汇聚路由器( a c r ) 系统性能和关键技术研究的研发。a c r 路由器是一种具有宽带组网和大规模接入汇聚能 力的高性能双协议栈核心路由器，通过多个路由单元互联可进一步支持到t 比特级的交换 容量。本课题以该项目为依托，针对高速宽带通信网的飞速发展对交换技术不同层面的应 用需求，在交换结构及其调度策略的可扩展性和组播支持方面进行了研究，从而为a c r 路 由器的研制构建一种满足应用需求的交换系统工程解决方案，并予以实现。 1 2 交换技术面临的挑战 本文所探讨的交换技术特指分组交换技术。分组交换技术的两个重要的研究内容包括 基于排队机制和交换单元构建的交换结构与基于交换结构所设计的调度策略，两者共同决 定一个交换系统的性能。其中，交换结构决定如何对到达的数据分组进行缓存以及如何对 分组进行交换，其主要影响交换系统的可扩展性能；调度策略主要影响交换系统的可预测 性能，如吞吐量、时延和抖动等。由于交叉开关( c m s s b 砌交换单元具有无阻塞特性，实 现简单，并且有成熟的商用芯片可直接应用，因此无论在学术研究方面还是在设备研制方 面都被广泛的应用于交换结构的构建。 根据排队机制的不同，基于交叉开关构建的交换结构主要可分为输出排队( 0 u t p u t q u e u i l l g ，o q ) 交换结构、输入排队( i 印u tq u e u i n 岛i q ) 交换结构和联合输入输出排队 ( c o m b i n ei n p u ta 1 1 d0 u t p u tq u e u i n c i o q ) 交换结构。虽然o q 交换结构能够提供良好的服 务质量保障，但是要求存储器的访问速率至少是 吝的线路速率p 】，这严重限制了其可扩展 性。i q 交换结构的交换单元与存储单元均只需工作于线路速率【4 】，并且在输入端口采用虚 拟输出排队( r h m lo u t p u tq u e u i n g ，v o q ) 机制后，可以完全避免队头阻塞( h e a do fl i n c b l o c k i n g ，h o l b ) 【5 l 问题，因而对于构建大容量交换系统是一种有效的解决方案。然而，i q 交换结构需要通过集中式的调度策略来实现c r o s s b 甜的无冲突传输，而这种集中式调度策 略的算法复杂度过高从而限制了交换规模的扩展；此外，输入排队交换结构要求c m s s b a r 内部的数据是定长形式的信元，这种方式在处理变长业务分组时开销很大以致无法提供服 务质量保证。通过c r o s s b a r 内部加速从而使i q 交换结构演变为c i o q 交换结构，c i o q 交换 结构可以获得良好的服务质量保障。然而，联合输入输出排队交换结构依然要求集中式的 第2 页 堕垦型查兰堡主兰垡笙奎 调度策略和定长的信元格式，在实现可扩展大规模交换容量时，交换系统的处理复杂度依 然很高。 由于a c r 路由器要求具有大规模交换容量的同时能够进一步扩展的t 比特级，无论是 o q 、i q 还是c i o q 交换结构几乎无一能实现a c r 路由器对交换系统性能的要求，尤其是在 支持组播交换时上述问题会进一步恶化，因而传统的交换结构与调度策略面临着严峻的挑 战。随着c m o s 工艺水平的提高，在c r o s s b a r 交换单元内部集成一定容量的存储单元已成为 现实：交叉点缓存的引入能够有效的将输入与输出端口之间的带宽冲突隔离开来，使分布 式与并行调度策略的设计成为了可能。本文力图通过对这一新型交换单元的可扩展性与组 播支持方面的研究，从而为a c r 路由器寻求一种合适的工程解决方案。 1 3 本文的主要贡献 本文以大规模接入汇聚路由器a c r 的研制为依托，针对现有交换技术存在的有关不 足，基于带缓存交叉开关这一新型交换单元，在可扩展性、组播支持以及单组播服务质量 保障三个方面进行了研究，从而为a c r 路由器构建一种合适的交换系统解决方案。概括起 来，本文主要贡献如下： 针对目前理论分析手段仅能为交换系统性能进行定性分析与粗略评估，以及仿真实验 手段缺乏对交换系统性能评估的有力支撑，在一致性、可继承性和可扩展性方面存在 缺陷，采用系统级设计方法和面向对象技术设计并实现了一种专用的交换技术性能仿 真评价系统s p e s 。该系统集成了多种典型的交换结构及相关调度策略，具有良好的可 继承与可扩展特性，为交换技术领域的技术创新和方案设计提供了一个基础研究平台。 夺分析了限制交换技术可扩展性的主要因素，提出了具有良好可扩展性交换结构和调度 策略设计的基本准则。依据这准则重点研究了基于联合输入交叉节点排队交换结构 的调度算法的设计，并提出了一种基于份额的动态轮询调度策略f d r 。该调度策略依 据v 0 q 和交叉点缓存的状态分配调度份额，其算法复杂度仅为d ( 1 ) ，具有良好的动 态和可扩展特性。s p e s 系统仿真结果表明f d r 算法具有良好的吞吐量、时延和抗突 发性能。 夺从传统交换结构在支持组播交换方面存在的不足出发，提出了一种支持单组播混合调 度的m c i c q 交换结构及支持单组播并行分布式调度的m f d r 和m f s 调度策略，采用 扇出拆分机制无需加速即可实现高效的组播复制，其算法复杂度为d ( 1 ) 。m f s 调度策 略还可以为单组播业务提供不同的带宽保证，满足两类业务对q o s 的不同需求。s p e s 系统仿真结果表明m f d r 和m f s 均可获得良好的性能。 夺基于a c r 的研制需求，针对a c r 路由器的特点，以及综合考虑系统性能、设计成本 和工程开发周期的基础上，为a c r 设计了一种具有组播支持能力的交换系统工程解决 方案，满足了其在可扩展性与组搔支持方面的需求。该方案已在大规模接入汇聚路 由器( a c r ) 系统性能和关键技术研究项目的路由器设备实际研发中得到成功应用。 第3 页 笪星三堡查堂堡圭堂垡丝塞 1 4 本文的结构和安排 本文行文共分为五章，剩余各章内容安排如下： 第二章对前人的研究工作进行了总结与评述，分析了输出排队交换结构、输入排队交 换结构以及联合输入输出排队交换结构及相应调度策略在高速环境下应用时存在的问题； 并重点论述了联合输入交叉点排队交换结构在构建大规模交换系统运用中的优势。该章还 阐述了交换系统性能评价的主要手段及性能指标，并介绍了交换系统性能评价平台一 s p e s 。 第三章首先分析了交换技术的可扩展性问题，给出了影响基于带缓存交叉开关构建的 交换系统可扩展性的主要因素。综合考虑这些因素，基于联合输入交叉节点排队交换结构 提出一种满足可扩展性要求的公平动态轮询调度算法f d r ，并通过s p e s 系统对f d r 算法 的稳定性、时延和抗突发性能进行了仿真评估。 第四章主要研究了带缓存交叉开关的支持组播交换问题。从现有交换系统在支持组播 交换方面存在的不足出发，提出一种高效的支持单组播混合调度的m c i c q 交换结构。基 于该结构具体分析了调度策略的设计问题，并给出了两种调度方案m f d r 和m f s 。最后 对该交换结构及其调度算法的有效性在s p e s 平台上进行了仿真验证。 第五章结合大规模接入汇聚路由器在大规模接入汇聚与骨干组网方面的需求，基于 m c i c q 交换结构为a c r 路由器设计了一套完整的交换系统解决方案，并给出了其详细的 工程实现。测试结果表明：该方案具有良好的吞吐量和时延性能，满足了a c r 路由器项 目开发的需要。 最后是结束语。该部分对全文内容进行了总结，同时指出了下一步可能的研究课题与 设想。 第4 页 信息工程大学硕士学位论文 第二章交换系统模型分析及性能评价 本章从交换系统的普遍模型出发，全面地介绍了交换技术领域的发展概况，分析了目 前基于c r o s s b a r 交换单元构建的各种交换结构及其调度策略存在的问题与不足，从而为 a c r 路由器交换系统的研究与设计提供参考依据；此外，针对当前理论分析在交换系统性 能评估方面存在的不足，设计实现了一种具有良好可扩展与可继承性的交换系统性能评价 系统( s w i t c hp e r f b 咖锄c ee v a l u a t i o ns y s t e m ，s p e s ) ，以期为交换调度领域的技术创新和方 案设计提供向导作用。 2 1 引言 在分组交换网中，各种业务流汇聚到网络交换节点设备时常常具有突发性，因而交换 设备需要对到达的业务分组进行缓存。根据物理交换单元之上构建的排队机制的不同，基 于交叉开关交换单元构建的交换结构主要可分为输出排队( 0 u t p u tq u e u i n g ) 交换结构、输入 排队( i n p u tq u e u i n g ) 交换结构以及联合输入输出排队( c o m b i n ei n p u t 舭d0 u t p u tq u e u i n g ) 交换结构。随着c m o s 工艺水平的提高，在交换单元内部集成一定容量的存储单元成为可 能嘲，相关交换结构的研究迅速成为了该领域的研究热点。其中最具影响力的为联合输入 交叉节点排队( c o m b i n e di n p u t 孤dc r o s s p o i n tq u e l l i n g ) 交换结构【”。调度策略是以交换结构 为基础构建的分组的逻辑管理机制，是交换系统性能的重要保证。交换结构与调度策略共 同决定整个交换系统的性能。 近年来由于交换技术的发展，交换系统的行为变得十分复杂，理论分析很难得出系统 模型的解析解，而主要用于交换技术复杂性的评价以及其它性能指标的定性分析与粗略评 估嘲。由于能够更客观、更直观和更准确的描述系统行为，仿真实验已经成为交换系统性 能评价的重要手段，对方案的设计与决策具有十分重要的意义。为此，本文构建了一种系 统级描述语言建模与面向对象技术实现的交换结构与调度策略的性能评价平台一s p e s i g 】。 目前该平台集成了现有各种交换结构与调度策略，并为支持新的结构和调度策略的扩展预 留了接口。用户通过与仿真平台之间的简单交互就可以方便的完成仿真参数的配置，专用 性与可扩展性强，为交换技术领域的技术创新和方案设计提供一个重要的基础研究平台。 本章首先给出了交换系统的一般抽象模型与性能评价指标，以该模型为基础分析了目 前典型的交换结构及其调度策略在高速环境下的可扩展性与组播支持方面存在的问题，从 而为后续章节提出新的方案奠定基础。本章剩余部分是按照下面的结构进行组织的：第二 部分给出了交换系统的一般模型及其性能评价指标；第三部分以该模型为基础，详细总结 了现有基于c r o s s b 村构建的各种交换结构及其调度策略，并指出了它们各自存在的优缺点： 第四部分对现有的交换技术进行比较，为后续研究指明方向：第五部分概要介绍了s p e s 性能评价平台的设计思路和其中的关键技术；最后总结本章。 第5 页 信息工程大学硕士学位论文 2 2 交换系统抽象模型 2 2 1 概念定义及描述 首先给出交换技术相关的若干名词解释： 分组( p a c k e t ) ：在分组交换网络中，业务都是以数据分组的形式传输的，分组可以 是定长也可以是变长的，将定长的数据分组称为信元( c e l l ) 。 输入端口：输入端口用来接收和处理来自外部物理链路的业务分组，并将分组按照 一定的规则送往交换单元。 线路速率( l i n em t e ) ：用r 表示，指外部物理链路的传输带宽( 传输速率) ，如o c 1 9 2 等，单位一般为6 瑚。 时隙( t i m es l o t ) ：时隙用来描述以速率r 传输一个c 础所需要的时间，在定长分组 交换系统中，时隙是信元调度的基本单位。 交换单元：将分组从输入端口交换到输出端口，是交换系统的核心单元，根据内部 是否存在冲突可以分为内部有冲突和内部无冲突两类。 加速比( s p e e d u p ) ：若交换单元内部线路速率为，则加速比定义为铲r r 。对一个 交换系统而言。所需的加速比越小越好，当严l ，此交换系统无加速。 输出端口：经交换单元交换后的数据分组，由输出端口发送到外部物理链路上。 交叉开关( c r o s s b a r ) ：交叉开关是一类内部无冲突的交换单元，在任意时刻都存在 从任一输入端口到达任一输出端口的连接。 2 2 2 交换系统模型 输入端口交换单元输出端口 |，j 八 a f 调 一度 1 几” x 卜 策 k 。 一：卜 调 度 策 略l 略 ： l o1 一卜v v 图2 交换系统模型 虽然交换系统形态各异，但抽象到模型的层面上都由输入端口、交换单元、输出端口 和调度策略四部分组成，如图2 所示。前三部分又可统称为交换结构，是交换系统的物理 基础；调度策略作用于物理交换结构之上保证交换系统达到预期的性能。 本文在后续描述中遵循如下假设条件： 第6 页 堕星三堡盔堂堡主堂垒堡壅 1 ) 除特殊指名外，交换系统的规模默认为，即一个交换系统有个输入端口和 个输出端口： 2 ) 本文仅研究单平面交换系统，对于多平面交换系统可以由单平面交换系统通过空分 得到，如并行分组交换( p a r a l l e lp a c l s 、) l ，i t c h ，p p s ) 系统； 3 ) 除特别指明外，本文所研究的排队机制和调度策略均基于c m s s b 甜交换单元构建； 4 ) 为了研究的方便，假定在交换系统内部传输的分组为定长的信元，并假定信元长度 为6 4 字节( b y t c ) ，一个时隙为一个信元的传输时间。 2 3 分组交换技术综述 从交换系统的普适模型出发，本节对现有基于c r o s s b a r 构建的各种交换结构及其调度 策略进行了较为全面的分类和比较，分析了它们在高速环境的可扩展性以及组播支持方面 面临的挑战，并重点研究了联合输入交叉点排队交换结构及其调度策略的设计，以期为 a c r 路由器交换系统的设计指明研究方向。 2 3 1 输出排队交换系统 2 3 1 1 输出排队交换结构 l 2 图3 输出排队交换结构模型 输出排队( o q ) 交换结构是指到达各个输入端口的分组直接经由交换单元到达输出端 口，并在每个输出端口进行统一排队，如图3 所示。每个输出端口可能有l m 个队列，m 的大小取决于业务流分类的规则。如果按照输入端口进行分类，则m 等于输入端口数； 如果按照“分组字段”( 如源目的i p 地址、源目的端口号、协议类型等) 迸行分类，则m 的 值可能要比大很多。 输出排队方式的优点是：1 ) 能够获得1 0 0 的最大吞吐量；2 ) 输出端口可以采用灵活 的调度机制，从而为各类业务提供更好的服务质量保证；3 ) 无队头阻塞( h o l b ) 问题；4 ) 能够很好地支持组播业务。然而，输出排队交换结构存在无法克服的不足：1 ) 交换矩阵和 输出端口需要工作于倍输入端口的链路速率，若输入链路速率不等，则为所有输入链路 速率之和：2 ) 随着链路速率的提高和交换规模的扩大，这种结构的可扩展性降低。 可以看出：o q 交换结构的实现存在倍加速问题，对交换结构的规模过于敏感，不 具备良好的可扩展性，因而o q 不适合a c r 路由器交换系统。 第7 页 信息工程大学硕士学位论文 2 3 1 2 输出排队的调度策略 输出排队调度策略运行于交换系统的输出端口，按照一定的服务规则对到达输出端口 的业务流进行调度和服务，使所有的业务流按照预定的规则共享交换节点的输出链路带 宽。本文采用 9 中的分类方法将输出排队调度策略分为五类：基于轮询( r o l l i l dr o b i n ) 的 调度策略、基于优先级的调度策略、基于通用处理机共享( g p s l l 0 1 ) 的调度策略、基于时延 的调度策略、基于服务曲线( s e r v i c ec u n ，e 【i i j ) 的调度策略和一类新的调度策略。由于r r 和g p s 调度策略是目前输出排队调度策略的研究热点，这里主要介绍这两类调度策略。 1 基于轮询的调度策略 轮询调度策略对所有输出端口队列进行无差别的服务。如果不同输出队列具有不同的 分组长度，则分组长度大的队列就会比分组长度小的队列获得更多的服务，队列之间就会 产生不公平的现象；此外，这类算法不具备为各类业务流提供q o s 保障的能力。 为了改善l 汛算法的性能，研究人员提出了一些改进型的算法，典型的如加权轮询 ( w r r l l 2 j ) 、差额轮询( d r r 【”j ) 等。他们从不同的角度对r r 算法的时延性能及其在变长分 组环境下的不公平性进行了改进。、r r 算法为每个队列赋予定权值( 可以理解为信元数 目) 并维护了一个计数器。轮询时，计数器不为零的队列可以输出一个信元。计数器的更 新规则为：初始值为权值，每发送一个信元就减一，当所有队列的计数器值为零时，则重 置为权值。w r r 算法能提供很好的公平性，并以较为平滑的方式输出业务流。 d r r 算法是为了解决传统r r 算法的不公平性而提出的。与w r r 相似，d r r 也为每 个队列赋予了一个计数器，轮询时。只有长度小于计数器值的分组才允许发送。计数器的 更新规刚为：初值为定额值g ，每发送一个分组就减去此分组的长度值；每轮询一次就加 上定额值q 。d r r 算法解决了r r 算法在变长分组环境下带来的队列间的不公平性，可以 应用于变长分组环境，并且实现较为简单。其缺陷在于不能很好地满足业务所要求的时延 性能，因而不能有效地支持实时业务和像w r r 那样以较为平滑的方式输出业务流。 2 基于g p s 的调度策略 g p s ( g e n e m lp f o c e s s o rs c h e d u l i n g ) 是一种理想化的流调度模型，它依据各队列的共享 比例对所有活动队列同时服务，因而能使各业务流真正公平地共享链路带宽。g p s 对每个 业务流有明确的端到端的时延上限保证，而且与其他队列的业务流无关。g p s 是流系统模 型，而实际的系统都是分组系统，即在任何给定的时刻只能有一个分组可以接受服务，分 组的服务是不能被抢占的。为此，出现了一类用来逼近基于流的g p s 模型的分组调度算法 一分组公平排队( p f q l l 4 j ) 算法。p f q 逼近g p s 模型的方法是：在假设无后续分组到达的前 提下，选择在g p s 中