（信号与信息处理专业论文）高速光交换机体系结构及调度技术研究.pdf

冀庆郏屯大举硕士论文拣要 摘要 随着i n t e m e t 瓣整务数攥量垒爆浑式增长，人稍对蒋输带宽帮交换寮黧翡需 求随之迅猛增长，w d m ( w a v e l e n g t hd i v i s i o nm u l t i p l e x ) 和d w d m ( d e n s i t y w a v e l e n g h hd i v i s i o nm u t t i p l e x ) 提袋了缝够开发光绎中聂大带交资源潜力叛满足 人们对带宽的需求。可传统的路幽器在交换过程中由于存在光电光( o ，e 。o 、转 换，其中鲍邀子嚣 掌在适应离速、大容量翡嚣慕上存在诸多缺点，难黻寇或毫 速宽带综合业务的传送和交换处理，而成为网络中的“瓶颈”。本文对下一代 巅速交换蹲络豁核心拄拳一毙交换桃熬髂系蘩梅疑潺发技张迸毒 j 二+ r 磅究。至要 集中于光交换的集中式交羧结构及调度算法。 在本文中，黄隽就当翦网络辩离瞧魏路壶器筑霉求以及嚣蠹羚学零器、产 娩界对路囱器的研究现状避行了分析；接精对交换结构的禳块实现功能进行了 阐述，并对调度葵法鲍性熊指标如吞蛙量、聪延特性、公_ 乎性鞠复杂蛙这四个 方滔盼特燃进行了分耩。为了推动下一步必交换调度算法瓣提离，在第三辩中， 对基于c r o s s b a r 电交换算滋进行了麓单回顾。在第四章中对基于光c r o s s b m - 交 欹绪j 勾的络构、线“管信元豁瓣装拽术、调凌流疆以及热速网子等毙交换调凄中 所用到的必需因素遴幸亍了详细说嘴。光交换具有可舞级、态带浇、功率损凝低 和成本低舔优点。然丽，以m e m s 为交换单元的光交换，藜切换鳍寸延相比予电 交换来说婺长得多。在充分考虑韬换瞬延的情况下，在第纛章中，将光交换谖 凄分成同步调度和异步调廉，以及根据披努矩砗的元索是否在嗣个配置矩阵 传输完毕，本人又将同步磷艘分成捻占式调度车蹉嚣捻占式调度。从调度算法盼 溺大指标出发，分裂提出了新静解决方法并用仿真证实了簿法的优越性。最后， 本人怼下一步工作计划避行了展望。 关键弼；光交换楗，同步调度，：器步诞度，受载均簿，1 0 岛砖 霞痰姆电大学硕圭论文 摘要 a b s t r a c t w 3 t ht h ee x p l o s i v ei n c r e a s i n go fo p e r a t i o nq u a n t i t yo nt h ei n t e r n e t ，t h ed e m a n d o fn e t w o r kb a n d w i d t hi si n c r e a s i n gd r a m a t i c a l l y t h ew d m ( w a v e l e n g t hd i v i s i o n m u l t i p l e x ) a n dd w d m ( d e n s i t yw a v e l e n g t hd i v i s i o nm u l t i p l e x ) t e c h n o l o g yc a l l m a k eg r e a tu s eo f t h el a r g el a t e n tb a n d w i d t ho f f i b e r , s oi ti sa b l et om e e tt h ed e m a n d o fb a n d w i d t h t h et r a d 试o n a ls w i t c h e sh a v em a n yd r a w b a c k sd u r i n gp a c k e t s f o r w a r d i n gp r o c e s s ，a n d i tc a n n o tc o m p l e t et h eh i g h - s p e e dt r a n s m i t t i n ga n d s w i t c h i n go fb i s d n ( b r o a d b a n di n t e g r a t e ds e r v i c e sd i g i t a ln e t w o r k ) ，a n db e c o m e a b o t t l e - n e c k i nn e t w o r k i nt h i sp a p e r , w eh a v ed o n em u c hw o r ko nc o l e t e c h n o l o g yo fh i g h - s p e e ds w i t c h i n gn e t w o r ko no p t i c a ls w i t c h i n ga r c h i t e c t u r ea n d s c h e d u l i n ga l g o r i t h m e s p e c i a l l y w ef o c u so nc e n t r a l i z e ds w i t c hf a b r i cs c h e d u l e , d i s t i l b u t e ds w i t c hf a b r i cs c h e d u l ea n dm u l t i c a s ti ns w i t c hf a b r i c f i r s t l y , t h i sp a p e rg i v e s 鑫na n a l y s i so ft h eg o o dp e r f o r m a n c eo fs w i t c h e s r e q u i r e db yc u r r e n tr e s e a r c hn e t w o r ka sw e l la sp r e s e n tr e a c hs t a t u so fs w i t c h e s c o n d u c t e db ya c a d e m i cc i r c l e sa n di n d u s t r i a ld o m a i n 戡h o m ea n da b r o a d 。n e x l 、转 a n a l y z et h ei m p l e m e n t a lf u n c t i o no ft h em o d u l eo fs w i t c hf a b r i ca n dt h ec a p a b i l i t y c r i t e r i o no fs c h e d u l i n ga l g o r i t h m ，s u c ha st h r o u g h p u t ，r e e o n f i g u r a t i o nd e l a ) ；f a i r n e s s a n dc o m p l e x i t y i nc h a p t e r3 ，w eg i v eag e n e r a lo v e r v i e wo f t h ea l g o r i t h m sb a s e do n c i r c u i ts w i t c h i nt h en e x tc h a p t e r , w ee x p l a i ni nd e t a i lo no p t i c a ls w i t c ha r c h i t e c t u r e ， e n c a p s u l a t i o no fl i n e c a r d sc e l l s ，s c h e d u l i n gf l o w , a n ds oo no t h e rf a c t o r so fo p t i c a l s c h e d u l i n g + a c c o r d i n gt oc o n f i g u r a t i o nd e l a y , w ed i v i d eo p t i c a ls c h e d u l i n gi n t o s y n c h r o n o u ss c h e d u l i n ga n da s y n c h r o n o u ss c h e d u l i n gi nc h a p t e r5 a n di r ae l e m e n t o ft r a f f i cm a t r i xc a nt r a n s m i ti no n ec o n f i g u r a t i o nm a t r i x ，w ec a l li tap r e e m p t i v e s c h e d u l i n g ，o t h e r w i s e ，n o n - p r e e m p t i v es c h e d u l i n g b a s e do no p t i c a lc r o s s b a rs w i t c h a n ds c h e d u l i n ga l g o r i t h m sc a p a c i t y , w ep r o p o s e dn o v e la l g o r i t h m sc o r r e s p o n d i n gt o d i f f e r e n ts c h e d u l i n gm e t h o d s s i m u l a t i o nr e s u l t sd e m o n s w a t et h a to u ra l g o r i t h m sa r e s u p e r i o r i t yt h a ns o m eo t h e ra n a l o g ys c h e d u l i n ga l g o r i t h m s l a s t l y , w el i s tt h en e x t w o r kp l a n k e yw o r d s ：o p t i c a ls w i t c h ，s y n c h r o n o u ss c h e d u l i n g , a s y n c h r o n o u ss c h e d u l i n g ，l o a d b a l a n c e ，1 0 0 t b l s l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得重庞蛏虫太堂或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：茬覆磐 签字日期：加占年，月? 日 学位论文版权使用授权书 本学位论文作者完全了解重废鲣电太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文 被查阅和借阅。本人授权 重庆整虫太堂可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位做作者躲专季秀导师张矧诊 签字日期：庐一占年, e j 王e t签字日期咖莎年且岁e t 重庆邮电大学硕士论文第一章绪论 1 1 研究背景 第一章绪论 为了解决这个问题，在今年刚出来的2 0 0 6 年国家计划的基金项目中有这样 一个相关项e l 一光分组交换关键技术与实验平台，它是针对光交换技术的发展趋 势和下一代网络业务的需求，该项目重点研究光分组交换技术及组播光交换功能 等关键理论与前沿技术问题。主要研究内容：( 1 ) 基于光标记的光分组交换技 术或新型全光分组交换技术：( 2 ) 光分组在网络中的传输控制；( 3 ) 组播光交 换单元技术；( 4 ) 结合与现有网络的融合策略，视频流媒体及存储域网等新兴 业务对光交换网络服务质量等要求，构建典型光分组交换网络实际应用原型系 统。 当前，国际上也对光交换研究得如火如茶。 前不久，美国斯坦福大学( s t a n d f o r du n i v e r s i t y ) 的n m c k e o w n 教授及 其数位博士生组成的研究小组向业界报道了他们最新的工程项目研究符合 r f c1 8 1 2 规范的新一代光交换机路由器。在基于台湾清华大学张正尚教授的 l o a d - b a l a n c e d ( 负载均衡) 路由器基础上，研究人员采用了与传统路由器完全不 同的多机架式、基于光交换内核的分布式结构，其线卡和交换内核被完全隔离。 他们坚信，产业界在约5 年左右的时间将对其研究结果感兴趣。i l l “美国贝尔实验室及其合作者美国加州大学s a n t a - c r u z 分校、美国 l e h i g h 大学和a g i l i t y 通信公司近期获得美国国防高级研究计划局( d a r p a ) 1 2 0 0 万美元资金资助，以期在四年时间内共同攻克1 0 0 t b i 幽光交换机( i 砌s ) 核心 技术。致力于u s 系统结构和核心算法的负责人a v a r m a 在2 0 0 4 年向学术界和 产业界宣称：i r i s 的设计是一项艰巨的任务，它与当前的交换机路由器结构有 很大不同，其核心基于光交换。如果能够攻克关键技术，将从根本上改变目前数 据通信的特性”。1 2 1 “美国加州大学光交换和通信系统实验室也获得d a r p a 的资助，致力于 光交换节点体系结构和可升级的交换平台的研究( h t t p ：s i e r r a e e e u e d a v i s e d u ) ， 研究小组这样报道：交换平台将由我们提出的新的可调谐波长变换和波长路由概 念进行设计和验证。基于阵列波导光栅路由器( a r r a yw a v e - g n i d eg r a t i n gt o u t e r , a w g r ) 的交换平台能够在波长域、时间域和空间域解决可变长分组的冲突问题。 当a w g r s 的端口数为2 5 6 x 2 5 6 时，系统的可升级能力达4 2 p b i t s ”。 “思科( c i s e o ) 公司于2 0 0 4 年5 月报道了其新研制的c r s 1 路由器 重庆邮电大学硕士论文 第一章绪论 ( h t t p ：w w w c i s c o c o m e n u s p r o d u c t s p s 5 7 6 3 ) ，采用了多机架三级c l o s 网络结 构，最大容量可达9 2 n 憎。 “2 0 0 6 年1 月日本横河电机报道他们已成功开发出切换时间为2 n s 的高 速光交叉连接设备，成为取代由于m e m s 镜片切换速度慢，线路交换方式的效 率低的高速交换元件，预计在2 0 0 6 年投入应用”。 近年来，以光交换为内核的交换技术的研究开发正在国外深入开展，国内的 清华大学、解放军信息工程大学、北京邮电大学、电子科技大学、上海交通大学、 华为公司等在传统的电路由器方面具有较扎实的积累，但在面向以光交换为内核 的、面向下一代互联网络应用的交换机体系结构和核心调度算法等研究方面，还 处于初步阶段。 i 2 高速路由器交换机研究中的热点问题 为了取得优异的性能，高速交换机路由器要求具有较高的交换容量和数据 传输率，同时系统应当能够灵活配置，以满足不同用户的需求。因此在下一代高 速交换机路由器的发展和设计中必须克服如下五个关键技术难点：高速背板、 高速接口模块、可扩展交换网络、路由器核心调度软件和q o s 保证： 高速背板 交换背板是交换机，路由器的关键部件，背板传输带宽是衡量背板性能的关 键参数，至少要保证所有接口满负荷运行时数据传输正常。考虑到内部处理的额 外负荷，背板带宽通常是端口总容量的2 4 倍，而下一代高速光交换机路由器 机架的互连又加大了对背板带宽的需求，这样如何使交换背板达到数百g 比特 级、t 比特级甚至p 比特级带宽是下一代光交换机，路由器设计中首先需要解决 的问题。传统的电子线路背板设计受到物理特性和制作工艺的限制，难以实现如 此高速率的数据传输。就目前技术而言，使用光纤背板是唯一经济有效的途径。 光纤背板是以光纤作为传输媒质，为了不增加线卡和交换结构设计的复杂度，在 线卡和交换结构之间需设置光收，发设备。同时为了保证数据传输的效率和正确 性，要求光收发设备具有同步、高速、极低误码率的性能。 高速接口模块 拥有高速、大容量、高密度的接口是高速光交换机路由器最大的特点之一， 但同时也给研发高速光交换机路由器带来了严峻的挑战。首先是高速环境下的 p o s 接口( 如o c 1 9 2 ，o c 7 6 8 ) 和大容量分组缓冲及其管理的设计和实现；其次， 高速接口模块已不再是简单地接收和发送数据的设备。一些原先由软件负责完成 的功能，如分类、查表、排队、q o s 、流量控制、输入输出链路调度等逐渐地集 成到线卡接口模块中，从而大大增加了设计的复杂度。目前这部分急需解决的关 2 重庆邮电大学硕士论文 第一章绪论 键技术主要体现在以下几个方面：( 1 ) 超高速p o s 接口技术。光纤技术的应用为 i n t e m e t 骨干传输网带来大量的原始带宽。为了最大限度地把原始带宽转变成可 用带宽，缩短与传输技术之间的差距。( 2 ) 高速大容量分组缓冲技术。分组缓冲 区的访问速度和容量决定了端口的速率，也是影响交换机路由器性能的主要因 素。 可扩展交换结构 交换结构是高速交换机路由器的核心部件，是限制交换机路由器交换容量 的另一个重要因素。交换结构有多种实现形式，常见的形式有共享缓存、分布式 输出存储和集中调度的c r o s s b a r 。其中共享缓存交换方式使用集中管理的存储器， 结构复杂性低，控制简单，但这种方式可扩展性差，带宽有限( 一般只能达到数 十g b i t s ) 。分布式输出存储对缓存速度和容量要求高，可扩展性差，不适合在高 速路由器交换机中使用。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 结构的扩展， 这是下一代光交换机，路由器研制的核心问题。 q o s 保证 q o s 保证能力是电信运营商和i s p ( i n t e m e t 服务提供者) 非常关心的，也是衡 量一个交换柳路由器产品的重要技术指标。目前，国外高速交换机路由器产品 都声称具备区分服务功能，包括业务流的分类、整型以及资源分配。目前高速交 换机产品基本上都采用c i o q 排队方式，通过提高交换结构带宽来加速数据传输 以减少分组在输入输出端间的时延。此外，在高速交换机中实现q o s 保证还要 受硬件环境，处理速度、存储器访问速度等因素的制约。因此实现难度较大，此 外调度算法的设计、排队策略的研究及其硬件实现也必须与q o s 保证机制相连 起来，所以q o s 保证机制是下一代高速光交换机路由器实现中一个重要的技术 突破点。 以上介绍了当高速光交换机，路由器研发中涉及到的热点问题，从中我们可 以看出，在高速交换机的实现过程中，存储器作为重要的实现部件，其访问速度 和存储容量是上述热点问题实现的关键之一。但由于目前高速光缓存器件很少， 短期内实现较困难，因此，迄今为止，国际上的研究项目基本是采用光电混合型 交换机，交换在光域内并行实现，其它分组的处理则是在电域内进行。 重庆邮电大学硕士论文 第一章绪论 1 3 课题意义 虽然光交换机在下一代互联网络中有着广阔的应用前景，但要进入实用化还 有许多技术问题需要解决。 第一，体系结构方面。目前，光技术和路由器技术并没有很好的结合起来， 综合考虑了这两方面的文献不多，也不成熟。从读到的文献来看，体系结构几乎 都是基于单播业务考虑，很小部分组播业务就有可能导致交换性能急剧下降。 第二，调度技术方面。目前，调度技术主要侧重于三个分离的方面：基于电 域的交换内核调度( 多局限于时隙调度) 、基于光域的交换内核调度( 也是多局 限于时隙调度) 、以及线卡调度( 主要为信元的封装策略、排队策略) 。在时隙调 度策略中( t s a ，t i m es l o ta s s i g n m e n t ) ，绝大多数研究又只考虑了两种极端情 况，即交换单元的切换时延相对于调度周期来说，要么为无穷大，要么忽略不计， 这对于光交换调度来说，是极为不合理的。这也是本文讨论的重点。 因此，光交换机在实用化之前需要解决的关键问题应该是通过优化设计交换 结构及其调度技术来降低成本、提高交换效率和可升级性、以及支持各种业务类 型。本文将致力于调度技术方面的研究，预期通过优化设计调度技术，而获得低 成本、高效率、高可升级性能的光交换机，这对于推动下一代高速大容量光交换 机的研制，继而推动下一代互联网的发展具有重要意义。 1 4 论文结构 全文共分六章： 在第一章中，首先就当前对交换机路由器的研究背景，研究现状以及研究 的意义进行了概述。这些对于整个课题的进行有非常大的指导意义。 第二章，将高速交换机路由器体系结构主要分成四个模块：输入模块、调 度器、交换结构( s w i t c hf a b r i c ) 和输出模块。并对各个模块的应用及所实现的 功能进行了分析介绍，其中以基于c r o s s b a r 交换结构的集中式调度以其无阻塞特 性、实现简单而成为研究交换结构、设计调度算法，分析交换单元性能方面的基 本结构模型。 第三章，将基于c r o s s b a r 交换结构的调度算法分成四大类：最大匹配类算法、 最大权重匹配类算法、稳定结合类和确定调度算法。因为电交换的切换时延相对 于光交换来说要小得多，因此这些算法在设计时没有考虑交换结构的切换时延， 但这些算法都是一些很成熟的算法，对于基于光c r o s s b a r 结构的调度算法设计有 一定指导作用。 4 重庆邮电大学硕士论文第一章绪论 第四章，对光交换结构进行了详细描述，为了对下一章的调度算法提出作好 铺垫，并对线卡的信元封装技术，调度流程以及加速因子等做了细致的说明。 虽然光交换具有可升级、高带宽、功率损耗低和成本低等优点。然而，以 m e m s 为交换单元的光交换，其切换时延( r e c o n f i g u r a t i o n d e l a y ) 相比于电交换 来说要长得多。因此，在整个调度过程中，切换时延是一个不容忽视的开销。 第五章，在充分考虑切换时延的情况下，本人将光交换调度分成同步调度和 异步调度，以及根据业务矩阵的元素是否在同一个配置矩阵传输完毕，又将同步 调度分成抢占式调度和非抢占式调度。从调度算法的四大指标出发，分别提出了 新的解决方法并用仿真证实了算法的优越性。 基于c r o s s b 盯交换结构的调度存在其调度算法实现复杂、不具有可扩展性等 原因难以运用于实际应用中。因为调度器必须掌握所有输入输出队列情况，然后 根据相应调度算法进行转发信元。近来台湾清华的张正尚教授提出了一个负载均 衡( 1 0 a d - b a l a n c e d ) 交换机，它因为不需要额外的调度算法，并且能适应于所有的 业务模式和实现1 0 0 吞吐量成为一个新的研究方向。但负载均衡很容易造成分 组信元的乱序。另外，他的交换结构也是基于光c r o s s b a r 的，他仍然没有解决可 扩展性问题。因为对于有着相同输入输出端口的信元，都经过同一交叉开关，如 果某一个交叉开关坏了，经过此交叉开关的信元由于不能得到及时转发而将丢 失，使整个交换机路由器的性能受到影响；交叉开关的切换时延太长，难以实 现高速业务转发功能。分布式结构及调度就可以解决基于c r o s s b a r 结构的调度问 题。因此，在最后一章对以后的研究工作进行了展望。其研究方向主要基于两个 方面：( 1 ) 负载均衡路由器中的乱序解决；( 2 ) 基于负载均衡分布式交换机结构 及调度的设计。 重庆邮电大学硕士论文 第二章交换机体系结构及调度模型 第二章交换机体系结构及调度模型 2 1 基本结构及模块功能 光交换是指不经过任何光电转换，在光域直接将输入光信号交换到不同 的输出端。图2 1 所示结构只是一般的光交换机体系结构，主要由输入模块、 交换矩阵、输出模块和控制单元四部分组成。 输入模块交换斧阵输出模块 图2 1 交换机路由器一般体系结构 1 输入模块及实现功能 对输入数字信号进行3 r ( 再生、再定时、波形整形) ，以便在后面的处理 和交换之前恢复信号质量；提取漂移和抖动；进行分组描述，以识别每一 分组的头尾以及报头与净负荷；进行分组同步，使它们与交换的时隙对准； 把报头分开，并转发给控制单元，好作处理；把分组的外部波长( w i ) m 传 输波长) 变换为在交换矩阵中使用的内部波长。 - 2 控制单元， ， 控制单元处理报头信息和发布所有指令，对交换矩阵进行配置。为此要询 问保存在每一节点的转发表。转发表需要借助网管系统( n m s ) 不断予以更新。 控制单元还要完成报头更新和向输出接口转发新报头的工作。新报头将能识别 分组路径中的下一节点。目前，控制功能是用电子电路来完成的。交换矩阵根 据控制单元的指令来完成净负荷的交换操作 3 输出模块及实现功能 再生、再定时、波形整形，以便在由于交换矩阵中元件不完善和串话引 起失真之后重新恢复信号质量；把新报头附加在相关的净负荷上；进行分 组描述和再同步；把内部波长变换为外部波长；进行输出功率均衡( 因为信 号功率电平随不同路径和交换矩阵插入损耗而变) 。 6 重庆邮电大学硕士论文第二章交换机体系结构及调度模型 通用的光分组格式如图2 2 所示，说明了光分组格式是如何放在交换时隙中 的。保护带用来对付定时的不定性。净负荷是用户数据，占有分组长度的大部 分。报头长短是一个最优化问题，因为它一方面要服务于所需的多项控制功能。 另一方面它是一种开销，不能够太长。 图2 2 在同步o p s 网中的分组格式 4 交换矩阵 交换矩阵是光交换节点的核心之一，由光交换单元组成。节点的交换速率、 吞吐量、可扩展性和可靠性等主要取决于光交换单元的性能。它根据调度算法 将输入端的数据交换到相应的目的端口。目前已推出产品的光交换单元有阵列 波导光栅( a w o ) 、微电机械系统( m e m s ) 、半导体光放( s o a ) 开关、声光开关几 种。其中，a w g 、s o a 开关和l f n b o ，声光开关( a o t s ) 的动作反应速度快， 适用于光分组交换矩阵。三维高速m e m s 技术在光交换结构中的应用还正在研 究中。在下一代高速交换机路由器中一般要求交换单元的操作时间为纳秒级， 要求光交换节点处理光分组信元的时间在几百纳秒，目前对纳秒级光开关的研 究成果已不少见。如2 0 0 6 年1 月日本横河电机报道他们己成功开发出切换时间 为2 n s 的高速光交叉连接设备，成为取代由于m e m s 镜片切换速度慢，线路交 换方式的效率低的高速交换元件。 一 网络容量需求的急速增加导致下一代高速大容量交换机路由器则必须采 用多机架( m u l t i - r a c k ) 结构，将交换内核和输入输出线卡完全隔离，如图2 3 所示。其交换内核可以采用在光域进行交换处理( 图2 4 ) 。 7 重庆邮电大学硕士论文 第二章交换机体系结构及调度模型 交换 拨 0 - 2 5 52 5 6 - 5 1 1 5 1 2 - 7 6 77 6 8 - 1 0 2 3 图2 3 多机架交换系统( 端口数：1 0 2 4 x 1 0 2 4 ，4 个机架) 辅 鳢卡e 蛳； ( h 喜t i 中 _ ， n 竞囊囊 辅 搜昔 i 趋划畸气 一， ， 凫重撬一镶 图2 4 基于光交换内核的交换机体系结构【3 i 辅 睦卡 _ 】i 翱睡i ( 刨嘲。 图匿断k同囫 l 凇蛀曩i k 。a g 馘鬟i 辅入眭卡 ( 幽嘲。 圈匣麟卜 唯叫函【哩粤叼。 踟慷姑1 1 i 重囊一坎 图2 5 高速电子式交换机体系结构嘲 很显然，与传统基于电交换的交换内核相比( 图2 5 ) ，基于光交换内核( 图 2 4 ) 的体系结构具有下列两点突出优势：( 1 ) 交换内核毋需进行“光一电”和“电 光”变换处理，系统成本、端口密度、体积和功耗得以显著降低；( 2 ) 大大提 升了系统的可升级性能和交换速度。 ， 以上优势促使人们对以光交换为内核的光交换机体系结构及其调度技术展 开深入研究。 s 重庆邮电大学硕士论文 第二章交换机体系结构及调度模型 2 2 空分交换结构 为使交换机的吞吐率达到最大，目前高性能交换机一般采用空分交换结构。 这是因为空分交换结构的总容量不受共享资源带宽的限制，可以在入线与出线 阃同时建立多个并发通道，使得在一个实时隙有多个信元通过交换结构，并可 扩展为更大规模的交换机。然而空分结构也有一些缺点，它需要提供路由功能， 用来选择一条到请求的输出端口的路径，另一个问题时阻塞，阻塞是影响交换 机吞吐率的主要原因。 路由功能可以采用两种方式实现： 集中式处理。集中处理单元检查每一个进入交换结构的信元目的地址， 然后在交换结构中设置所需的路径 分布式，也就是自路由方式。每一个交换单元简单的检查信元所包含的 目标地址，然后快速的、独立的做出路由决定。 交换机中存在两种阻塞( b l o c k i n g ) 形式；即内部阻塞和外部阻塞。所谓 内部阻塞，就是指到达不同的输出端口的两个以上的信元要经过相同一条内部 链路传送时，这些信元就在该链路上产生冲突而形成内部阻塞。而当两个以上 的信元在相同时隙趋向同一个输出端口，就会出现外部阻塞。内部阻塞是可以 克服的，通常所说的无阻塞指的就是无内部阻塞，一般可以采用c r o s s b a r 结构 实现；而外部阻塞是不可以避免的，这时需在交换结构的不同位置设置缓冲区， 缓冲方式可以分为输入列队缓冲、输出列队缓冲和中央缓冲等。 2 3c 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 结构由n x n 交叉点构成。交叉点与二维交换矩阵有一种对应的映射关 系( 如图2 6 所示) 。每个交叉点有两种状态：l i p c r o s s 或b a r 。当要在输入端口和输 ，、 出端口j 建立链接，只需要将交叉点v ，j j 置成闭合状态即可。交叉点的打开与闭合 是由调度器来控制的。因此，c r o s s b a r 结构的速度要取决于调度器的速度。调度 器是c m s s b a r 交换结构的核心，它在每个调度时隙内收集各输入端口有关数据包 队列的信息，经过一定的调度算法得到输入端口和输出端口之间的一个匹配，提 9 重庆邮电大学硕士论文第二章交换机体系结构及调度模型 供输入端口到输出端口的通路。本文c r o s s b a r 的交换单元( 交叉点，c r o s sp o i n t ) 是基于l v i e m s 结构的。如图2 6 所示。 输 入 卜 f 一 、 一 r o1 o0 00 lo ”。一 开关控制 图2 6c r o s s b a r 交换结构及交换矩阵示意图 c r o s s b a r 结构可以支持高带宽的原因主要有两个：第一，线路卡到交换结构 的物理连接现在简化为点到点连接，这使得该连接可以运行在非常高的速率。半 导体厂商目前已经可以用传统c m o s 技术制造出1 g b i t s 速度的点对点串行收发 芯片，并且可以在今后几年里把速度进一步提高到4 l o g b i t ，s 的水平。第二个原 因是它的结构可以支持多个连接同时以最大速度传输数据。这一点极大的提高了 整个系统的吞吐量。只要同时闭合多个交叉节点，多个不同的端口就可以同时传 输数据。从这个意义上，我们称所有的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 以前把它分割为固定长度的信元 ( c e l l s ) ，等这些信元通过交换结构以后再按照原样把它组织成原来的变长分组 ( p a c k e t ) 。 通过使用下面的几种技术，使得c r o s s b a r 交换结构很好的应用在路由器的背板 交换上： ( 1 ) 将可变长度的报文分割成固定长度部分通过交换机构，这使得传输一块数 据的时间相等，即为一个时隙。在每个时隙的结束时刻，所有输入端口和输 出端口同时传输完毕，这使得调度器的工作变得简单，只需在每个时隙结束 的时候做出调度决定。而对于可变长度报文，在任何时刻报文都可能传输完 毕，调度器需要每时每刻的监督每一个端口，而无法实现高速传输； ( 2 ) 使用虚拟输出队列去除输入队列模型中存在的队头阻塞。队头阻塞指的是 在输入排队的情况下，如果队头报文到达的输出端口正忙，即使后面报文要 到达的端口空闲也无法进行发送。队头阻塞限制吞吐量为理想的6 0 。采用 1 0 o 1 o o 0 o l o l = p 重庆邮电大学硕士论文 第二章交换机体系结构及调度模型 虚拟输出队列( v i r t u a l o u t p u t q u e u e ，简称v o q ) 可以解决这个阻塞问题。 在输入端口为每个输出端口维护一个单独的队列。当一个报文经过路由查询 后，放入它要输出的端口的队列中。在每个时隙的开始，中央调度算法会检 查所有的输入队列，在输入端口和输出端口之间寻找一个无冲突的匹配。在 理论上，v o q 能够把吞吐率提高到1 0 0 ； ( 3 ) 高效的调度算法：一个好的调度算法要满足4 个要求：( 1 ) 高的吞吐率；( 2 ) 不会出现某个队列始终得不到服务的情况；( 3 ) 快速，调度开销不至于成为 瓶颈；( 4 ) 简单容易实现，能够在一块芯片中实现。 ( 4 ) 输入阻塞：由于在每个时隙调度器对每个输入端口的多个v o q 只能服务一 个，因此出现输入阻塞。输出阻塞：不同输入端口的报文发送向同一个输出 端口出现输出阻塞。输入输出阻塞都只会影响报文的延迟而不会影响交换机 构的吞吐率。通过设置优先级队列能够提高q o s 。另外一种办法是提高交叉 开关的处理速度，近年来的研究表明，2 倍于端口速率交叉开关处理效果接 近于倍端口速率的处理速度的交叉开关。 2 4 排队模型 传统的路由器一般基于输出排队( o u t p u tq u e u i n g ，o q ) 。在这种结构下，到达 输入端口的信元马上被交换到相应的输出端口。o q 的优点是能够提供最优的吞 吐量和延迟控制，其调度算法( 如通用处理器共享【4 1 ) 在理论上已得到深入的研究 且实现简单。但为了保i z 正o q 的正常运行，交换结构的内部带宽和输出队列的存 储器访问速率必须是输入端口链路速率的倍( 如果输入速率不同，则为端口速率 之和) ，即要求倍的加速比，这里，是输入端口数。随着链路速率或端口数的 增加，在现有的工艺水平下很难实现高速的基于o q 的交换结构。 为了克服o q 结构的可扩展性问题，高速路由器考虑采用输入排队( i n p u t q u e u i n g ，i q ) 。到达的信元首先被保存在输入端口的缓冲区中，然后通过调度算 法决定信元何时通过交换结构传送到输出端口。i q 的优点是不需要加速比，但是 存在链头阻塞问题( h e mo fl i n e ，h o l ) ：如果队列链头的信元被阻塞，同队列 到其他输出端口的信元就不能被转发。研究表明，当端口数较多时，在所有输出 均匀分布的b e r n o u l l i 到达下，i q 只能达到5 8 6 的吞吐率【5 】。 重庆邮电大学硕士论文 第二章交换机体系结构及调度模型 输入线卡i 输入线卡2 输入线卡 f i f 厂 o 1 一i ， 厂1 输出线卡 i 输入模块交换矩阵输出模块 图2 7 输入排队交换机路由器结构 一解决输入排队链头阻塞问题的一种简单方案是文献【6 】提出的虚拟输出排队 ( v i r t u a lo u t p u tq u e u i n g ，v o q ) 。在这种结构下，每个输入端口为每个输出端口 设置一个队列，从而消除了链头阻塞并保持加速比为l 。理论研究和仿真实验 都表明，一个采用最大权重匹配调度算法的v o q 路由器可以达到1 0 0 的吞吐 率。在本文中，如不特别指出，输入排队路由器均采用v o q 排队方式。但是， v o q 路由器的一个不足是很难提供q o s 保证，原因在于信元的转发不仅与输 入端口的业务量大小有关，而且受调度算法的影响。 提高v o q 路由器性能的一种方法是利用加速比，这需要在输入和输出端口 都设置缓冲区。这种结构称为组合输入输出排队( c o m b i n e di n p u t o u t p u t q u e u i n g ，c i o q ) 。研究表明，加速比为2 的c i o q 路由器能够完全仿真一个o q 路 由器。这样，我们可以利用c i o q 继承o q 的吞吐率和延迟特性。但是，要在c i o q 路由器( 如图2 9 ) 中实现q o s 保证，关键在于设计一个有效的配置交换结构的调 度算法。 v o q 路由器的逻辑结构如图2 8 所示。它主要由4 部分组成：输入端口、输出 端口、交换结构和调度器。我们假设输入和输出端口的数量都是_ 且数据传输速 率相同。输入端1 ：3 采用v o q ，每个输入端1 ：3 为每个输出设置一个队列，则共有 n x n = n 2 个队列。变长分组在进入交换结构前已被分成定长信元，在v o q 中以 f i f o ( f i r s ti nf i r s to u t ) 排队，等候调度器根据调度算法转发。 重庆邮电大学硕士论文 第二章交换机体系结构及调度模型 2 输入模块光交换矩阵输出模块 图2 8v 0 0 交换机路由器系统结构 c i o q 交换机路由器的系统结构，如图2 9 所示。c i o q 在输入端的设置的 缓存区就是v o q ( 图2 8 ) ，不同的是，在输出端再设置了一个缓存区v i q ，每 个输出端口为每个输入设置了一个队列，用于对信元的重组。这也是第四章中 研究基于光c r o s s b a r 交换结构的调度算法基础结构。 输入模块交换矩阵输出模块 图2 9c 1 0 0 交换机路由器系统结构 2 5 调度算法性能指标 卡l 卡2 卡 调度算法是按照一定的规则对交换节点的不同业务进行缓存、调度和服务， 同时实现流量的管理与控制、冲突处理、带宽的分配与管理等功能。其性能主 要由吞吐量、时延特性、公平性和复杂性这四个方面的特性决定，下面分别介 绍这四个性能指标。 。吞吐量：吞吐量是单位时间内传送通过网络的给定点的平均比特数。一般 重庆邮电大学硕士论文 第二章交换机体系结构及调度模型 来说，将吞吐量除以信道传输速率，可使其归一化，其值通常在“0 ”和“l ” 之间。作为路由器性能指标的吞吐量通常指的是归一化的吞吐量。吞吐量决定 路由器处理数据包的能力，好的调度算法应该具有高的吞吐量。 时延特性：时延特性分平均时延和时延抖动两个方面。好的调度算法应可 以为特定要求的业务流提供端到端的时延保障。时延速率调度器( l r s ： l a t e n c y - r a t es e r v e r ) 模型可用于分析网络中不同调度算法带来的端到端时延，对 于定长分组情况，应用速率分隔时签调度器( r s t ：r a t e - s p a c e t i m e s t a m p s c h e d u l e r ) 模型分析会更有效【1 0 l 。 公平性：公平性是指链路带宽必须以公平合理的方式分配给共享链路带宽 的业务流。因此高性能的调度算法应可以隔离不同的业务流，这样即便发生高 突发型业务也不至于影响其他正常业务流。单位时间内不同业务流因为约定的 服务速率不同因而获得的服务量也不相同，因此通常采用归一化服务量( 单位时 间的服务量与分配服务速率的比值) 服务公平指数( s f i ：s e r v i c ef a i r n e s si n d e x ) 来衡量。另外最坏公平指数( w f i ：w o r s t - c a s ef a i r n e s si n d e x ) 也用来衡量调度算法 的公平性，较大的w f i 意味着调度输出业务存在较大的突发性。 复杂性：复杂性指的是算法复杂度和工程中的易于实现性和易于扩展性。 高速网络中传输一个分组的时间很小，所以调度算法必须能在很短的时间完成 对分组的调度，因此调度算法必须有很小的复杂度。而且好的调度算法应该易 于硬件实现，且具有良好的可扩展性。 2 6 信元调度模型 衮换结构包含个输入端口和个输出端口，变长的分组进入交换结构前 首先被分割成定