（电路与系统专业论文）高速可扩展网络交换调度系统的实现及组播技术研究.pdf

摘要 摘要 本文研究了可扩展网络交换调度系统f s s a 的实现及组播的r t l 级设计。f s s a 是 在国家自然科学基金资助下提出的一种公平可扩展网络交换调度结构，旨在解决单片调 度器规模和输入输出端口数受集成电路工艺限制的问题。它由若干片容量较小的调度 器( 子调度器) 串联而成，在中心控制器的控制下，各子调度器并行工作完成人容量、 多端口的调度任务。在实际应用中，f s s a 可根据需要扩展成不同容量和端口数的调度 器，不仅速度高，而且规模可扩展，从根本上解决单个调度器容量和端口受限的问题。 本文采用x i l i n xv i r t e x - 4f p g a 设计实现了基于f s s a 的6 4 x 6 4 可扩展调度器，该 调度器由4 片f p g a 级联构成，每片完成1 6 x 6 4 的子调度器任务。设计中充分合理地应 用了x i l i n xv i r t e x - 4f p g a 的新特性以及其内嵌的i p 核及功能模块，如高性能输入输出 串并( i s e r d e s ) 、并串转换器( o s e r d e s ) 、数字时钟控制器d c m 等，节省了f p g a 宝贵的硬件资源，提高了：卷片的速度和性能。 在此基础卜，通过精心、合理的设计，成功构建了由4 片f p g a 构成的f s s a 验证 平台，并进行了测试。单片f p g a 的测试结果表明，每个子调度器时序和功能正确，能 够同时处理1 6 路6 4 0 m b p s 的数据。整个系统的测试结果表明，各子调度器通过正确的 时序配合和信息交互，真正实现了6 4 x 6 4 的调度功能。 另外，本文对组播算法进行了一定的研究，设计实现了适合f s s a 的组播方案。仿 真结果标明，该系统通过单播组播标志实现组播的合理调度，不仅使可扩展调度系统 具有完整的单播、组播调度功能，而且充分复用单播调度模块，节省硬件资源。 关键词：路由器，输入队列交换，可扩展调度器，f p g a ，p c b ，组播 第1 页 摘要 a b s t r a c t a si n t e m e tg r o w sw i t ha ni n c r e d i b l es p e e d ，h i g h p e r f o r m a n c es c h e d u l e r sw i t hl a r g e rc a p a c i t y , t h r o u g h p u t , a n dl o w e rl a t e n c ya sw e l la sas a t i s f a c t o r yl o s sr a t eu n d e ra n yt r a f f i cp a t t e ma r er e q u e s t e d n u m e r o u ss t u d i e ss h o wt h a tt h ei n t e r n e tt r a f f i ci si n c r e a s i n ga tr a t e so f10 0 t o15 0 p e ry e a r , h o w e v e r t h es w i t c hc a p a c i t yh a sd o u b l e de v e r yl8m o n t h sa c c o r d i n gt om o o r e sl a w o b v i o u s l y , i ft h i st r e n d c o n t i n u e st oe n l a r g e ，t h ee x t e n d e dd i s p a r i t yb e t w e e nt r a f f i ca n dc a p a c i t yw i l lc a u s eab o t t l e n e c ko fi n t e m e t o nt h eo n eh a n d ，t h es w i t c h i n gc a p a c i t y , s p e e da n di 0n u m b e r so fas i n g l ec h i pa r cl i m i t e db yc u r r e n t s e m i c o n d u c t o rt e c h n o l o g y o nt h eo t h e rh a n d ，a l t h o u g hr e v i s i n gp o i n t e r s ，s e t t i n gt h r e s h o l d s ，i n c r e a s i n ga n d d e c r e a s i n gs c h e d u l i n gp h a s e s ，c a na c h i e v el o w e rl a t e n c ya n dh i g h e rt h r o u g h p u tt h ei m p r o v e m e n ti sn o t d i s t i n c t t h e r e f o r e 。t h es c h e d u l i n ga r c h i t e c t u r e sr a t h e rt h a ns c h e d u l i n ga l g o r i t h mi t s e l fn e e dm o r e c o n s i d e m t i o n t h i sp a p e rp r o p o s e st h ef a i rs c a l a b l es c h e d u l i n ga r c h i t e c t u r e ( f s s a ) ，a n dp r e s e n t st h e i m p l e m e n t a t i o nw i t hx i l i n xv i r t e x - 4f p g a f o ra l ln x ni n p u tq u e u e d ( i q ) s w i t c h ，e a c hi n p u tb u f f e rr e s e r v e sc e l l si nns e p a r a t eq u e u e s a c c o r d i n gt ot h e i rd e s t i n e do u t p u t sb e f o r es c h e d u l i n g ，w h e r es u c hq u e u e sa r ec a l l e dv i r t u a lo u t p u tq u e u e ( v o q ) u s i n gv o q a n da p p r o p r i a t es c h e d u l i n ga l g o r i t h m ，i qs w i t c h e sc a l le f f e c t i v e l ye l i m i n a t et h eh e a d o fl i n e ( h o l ) b l o c k i n ga n da c h i e v el0 0 t h r o u g h p u tu n d e rs o m et r a f f i cp a u e r n s t h e r e f o r e ，i qs w i t c h e s c u r r e n t l yo c c u p i e dd o m i n a n c ea m o n gv a r i o u ss c h e d u l i n ga r c h i t e c t u r e s t h i sd e s i g ni se x a c t l yb a s e do ni q s w i t c h e s f s s ab e a r st w of e a t u r e s ：f i r s t ，f s s ad e c o m p o s e daf o r m e r l yl a r g e s c a l en e t w o r ks c h e d u l e ri n t o s e v e r a lc a s c a d e ds m a l l e rs u b - s c h e d u l e r s s e c o n d ，b ye m p l o y i n gp a r a l l e ls c h e d u l i n ga l g o r i t h ma n dp i p e l i n e s c h e m e ，f s ac a nr e a l i z eab e t t e rl a t e n c yp e r f o r m a n c ei nc o m p a r i s o nw i t hm o n o l i t h i cs c h e d u l e r s t h i s d e s i g ni m p l e m e n t sa6 4 x 6 4s c h e d u l e rc o n s i s t i n go f4s u b - s c h e d u l e r s ，a n di tc a nb ee a s i l ye x t e n d e dt o l a r g e ra p p l i c a t i o nw h e nn e c e s s a r y i no r d e rt o s a v ep r e c i o u sl o g i cr e s o u r c e sa n dt h er e l i a b i l i t y , l a r g e a m o u n to fe m b e d d e dm o d u l e ss u c ha si s e r d e s o s e r d e s ，d i g i t a lc l o c km a n a g e m e n t ( d c m ) ，f i f o s a n db l o c kr a m sa r ee m p l o y e d ab o a r do ft e s t i n ge x p e r i m e n tb a s e do nf p g ai sd e s i g n e di nt h i sp a p e r ，a n df s s ah a sp a s s e dt h e f u n c t i o n v a l i d a t e t h er e s u l ts h o w st h a te v e r ys m a l l e rs u b - s c h e d u l e r sc a nd e a lw i t h1 6r o a d sd a t aw i t ht h e r a t eo f6 4 0 m b p s ，w h i c hm e e t sw i t hd e s i g nr e q u e s t a st h em u l t i m e d i ao p e r a t i o nt u r ni n t oa ni m p o r t a n ta s p e c t ，f o re x a m p l e ，v i d e om e e t i n g ，l o n g - d i s t a n c e e d u c a t i o n ，n o t e so fs t o c kq u o t e se t c ，m u l t i c a s ti st h ef e a t u r eo ft h i ss e r v i c e s s os w i t c h sh a v eau r g e n tn e e d t os u s t a i nm ul t i c a s to p e r a t i o n b a s e do nt h er e s e a r c ho fm u l t i c a s ta r i t h m e t i c ，t h i sp a p e rd e s i g nam u l t i c a s t s y s t e mw o r k i n g i nf s s a t e s tr e s u l t ss h o wt h a tt h i ss y s t e mh a sl o wh a r d w a r ec o m p l e x i t ya n daf i n e m u l t i c a s tf u n c t i o n k e y w o r d s ：r o u t e r , i n p u tq u e u e ，s c a l a b l es c h e d u l e r , f p g a ，p c b ，m u l t i c a s t 第1 页 图片索弓 图片索引 图2 1 交换式网络调度系统结构6 图2 2 输入队列交换结构6 罔2 3 输队列交换结构7 图2 4 输入输出交换结构7 图2 5 基于v o q 的i q 交换8 图3 14 个子调度器构成的6 4 6 4 可扩展调度结构1 2 图3 2 6 4 x 6 4f s s a = 1 ：作原理1 3 图3 3改进的6 4 x 6 4f s s a 13 图3 4 管脚锁定图。l5 图3 51 6 x 6 4 了调度器后仿真波形1 7 图3 6l 乜源板照片18 图3 7 验讪f 板系统架构图19 图3 8a d p 3 3 3 9 应用框图2 0 警i3 9 配置模式选择位连接图2 l 罔3 1 0d o n e 信n 显示原理图设计2 2 图3 1 l配置电路原理图2 2 图3 1 2 输出信号灯显示原理罔2 3 图3 1 3 时钟办案原理图2 3 图3 1 4 全局复化信号设计原理图2 4 | 冬| 3 1 5 地址选择开关部分原理阁2 4 图3 1 6 验i | f 板布局图2 5 图3 1 7a d p 3 3 3 9 和滤波电容放置位置。2 6 图3 1 8 品振和滤波电容放置位置2 6 图3 1 9 电容布线图2 6 图3 2 0f p g a 芯片连接图2 7 图3 2l项层布线图2 7 图3 2 2p c b 板图2 8 图3 2 3 验证板照片2 9 图4 1可扩展调度器验证平台示意图。3 l 图4 2f p g a 验证系统3 l 图4 3子调度器后仿真结果3 2 图4 4 子调度器后仿真结果( 位置a 展开) 。3 2 图4 5 子渊j 叟器测试结果之一3 3 图4 6 子调度器测试结果之二3 4 l 冬i4 7 子调度器测试结果之三3 4 图4 g 了渊度器测试结果之四3 5 图4 9 子调度器测试结果之五3 5 f - q4 1 0 可扩展调度器测试结果之一3 6 图4 1l吖扩展调度器的测试结果之二3 6 图4 1 2 调度器输出端口数据波形3 7 图5 1 1 6 x 6 4 子调度器框图4 0 图5 2l i 模块结构4 2 第v i i 页 东南大学硕上学位论文 图5 3l i 模块的引脚图4 2 图5 4v e r t e x - 4 的i s e r d e s 结构图4 4 图5 5 用主从i s e r d e s 实现l ：8 转换4 4 图5 6l ：8 串并转换器仿真波形4 4 图5 7 一个m f i f o 4 5 图5 8 r e q 模块引脚图4 6 图5 9s a l 模块结构4 7 图5 1 0 组播功能后仿真波形之一( 无组播请求) 4 8 图5 1 l组播功能后仿真波形之二( 同时有组播和单播请求) 4 8 图5 1 2 组播功能后仿真波形之三( 有两个组播请求) 4 9 第v i i i 页 东南大学学位论文独创性声明 本人声明所呈空的学位论文足我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论j 中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教百机构的学位或证书而使用 过的材料。与我同1 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示了谢意。 研究生签名：盘主蛊签日期：业达 东南大学学位论文使用授权声明 东南人学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电了文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊晋) 论文的全部或部分内容。论文的公布( 包括刊卺) 授权东南大学研 究生院办理。 研究生繇啦新虢姆啦日期：出士 第一章绪论 第一章绪论 本章首先介绍了课题背景及意义，接下来介绍常见网络交换调度系统的结构，然后概述当前网 络交换调度系统的研究热点，最后给出作者在攻读硕士学位期间研究工作的内容和论文的结构安排。 1 1 课题背景及意义 一卜世纪8 0 年代以来，由于处理器速度的提高及硬件成本的下降，桌面计算机得到迅速发展。局 域网也随着繁荣起来。当人们要求把- 卞机、局域网、广域网连接起来的时候，计算机网络就诞生了。 九十年代以来，i n t e r n e t 以惊人的速度迅速扩展，骨干网上的i n t e m e t 业务量每6 9 个月翻一番， 远远超过摩尔定律每1 8 个月翻一番的速度。为了适应数据业务量超过话音的发展趋势，适应客户一 服务器应用办式引起的网络流量分布变化以及i p 业务特有的目相似性和收发不对称性，各国都在探 索和试验町持续发腱的新一代公用网。 新一代公用网最基本的特征是对i p 业务优化的宽带分组网，由骨干网和接入网组成，骨干网是 网络核心，严董制约着整个网络的服务质量。因此，骨干网成为技术发展最活跃、设备更新最快的 领域。 未来骨干网的i 个关键组成部分是光纤、d w d m 和高瑞路由器。光纤具有极人的原始带宽，是 大容量骨干网的基硎；。d w d m 是原始带宽复用器，在单个光纤上实现多信道复用。高瑞路南器足骨 干网的核心器件，光纤和光互联技术的进步使网络带宽容量扩大1 0 0 0 0 倍，然而电予技术的发展没 有跟上光技术的发腱步伐，交换机路卜h 器的带宽j l 增加了l o 倍。光网层现在运行在o c - - 4 8 和 o c - - 1 9 2 的速率，原有路由器无法提供相应的接口速率和瑞口密度，不能有效利用光纤和d w d m 技术所创造的巨大带宽。采用高瑞路南器能把大量的原始带宽转换成可片j 带宽，解决骨- t 网潜在的 瓶颈问题，并确保现自i p 、a t m 、顿j l 继网之间的互操作性，使a t m 网能顺利向i p 网过渡。高瑞 路卜h 器是运营者级设备，能提供全实时应用，具有高性能、高密度、扩展性，占尽可能小的空问， 降低操作维护成本，是未来骨十网的关键节点，将源源不断的带宽资源传送给用户。 一般说来，异种l 】。9 络互联与多个予网互联都应采用路由器来完成。路由器的一个作用是连通不 同的网络，另一个作用是选择信息传送的线路。选择通畅快捷的近路，能大大提高通信速度，减轻 网络系统通信负荷，节约网络系统资源，提高网络系统畅通率，从而让网络系统发挥出更大的效益 来。骨干级路南器是骨干网的关键设备，它数据吞吐量较大，非常重要。对骨干级路由器的基本性 能要求是高速度和高可靠性。 高端路由器的主要作用表现在以几个方面： ( 1 ) 促进骨干网结构简化 随着具有高速接u 的高端路由器推出，a t m 与s d h 层设备可能消亡，骨干网经历了i p o v e r a t m 、i p o v e r s d h 和i po v e r o p t i c a l 的过程，虽然它们各有自己的定位和适用范围，f ri po v e ro p t i c a l 代表着网络体系结构的发展方向。骨干网物理结构将越来越简单，趋向由少量太比特传输链路和太 比特路由器构成所谓双t 网络。 ( 2 ) 降低了骨t 网建设成本 1 p o v e r o p t i c a l 的组网方式消除了对a t m 和s d h 层的需求，直接降低设备成本，节约了大量的 运行手| l 维护费用。 第l 页 东南大学硕士学位论文 ( 3 ) 有助于骨干网摆脱不断更新换代的压力。 i p 业务量按指数增长，现有的骨干网基础设施每隔l 2 年就需要伞面升级，运营者无法适应 高瑞路由器j 有良好的i ，扩展性，不但能以较低的配置满足目前的容量需求，还能通过互联扩展方 式满足本来需求。 ( 4 )能保证骨干网提供良好的服务质量 骨t 网必须解决时延和网络拥塞问题，确保q o s ，才能满足终端用广的需求。高瑞路由器把a s i c 用于分组的转发和路由表的查寻，不仅备吐量有突破，而且可以基本保证服务质量，转发分组延时 也降至几十微秒级。 ( 5 )使骨干网具有极高的可靠性 高端路由器具有冗余的硬件配置、快速的故障恢复能力和9 9 9 9 9 的可用性，在减少网络层次 的同时，减少了潜在的故障发生点，保证骨t 网的可靠性更高。 ( 6 ) 提高了骨干网的安令性能 由于黑客猖撅，网络安全越来越为人们将遍关注。高瑞路由器是抵抗黑客入侵、保护网络安全 的重要一环，其良好的安全设计和软硬件配置，犬大提高了骨干网的安伞性能。 自岛端路由器面世以来，凭借其优良的性能，迅速成为业界倍受瞩目的热点。然而，这魑高端 路由器的核心技术和1 场份额，尤其是高速网络交换和调度的关键技术和知识产权基奉上都掌握在 凼外开发者手里。因此，发展具有我国r l 我知识产权的商性能骨干交换技术已经越来越迫切。 岛端路由器是t 作在骨干网卜的核心路由器，它的核心技术就是高速地进行人容量地网络交换， 性能良好地路由器j 有较高地吞吐率，较小地延迟时间并且能够在任意流量下都i 有较低地丢包率。 图1 1 为交换式n x n 网络交换的体系结构，它由两个事要部件一交换机构( s w i t c hf a b r i c ) 和调度 器( s c h e d u l e r ) 组成，交换机构在调度器的控制下从线卡( 1 i n ec a r d ) 中接受米自s d h e t h e m e t 等的 包，并实现任意n 个输入端l i ( p o r t ) 到任意n 个输出端口之日j 的包交换。 随着网络交换的发展，下一代网络不仅需要向更大容量、更多端口交换发展，而且对交换的吞 吐率、延迟和公平性等方面也提出了更高的要求。下一代嘲络交换对网络设备有以下三个不断提高 的要求：一是要能处理更多的端口，二是能实现更高的端l j 速率，三足能支持更高级的服务方式川 端口数可扩展一即交换结构的解决方案在所支持的端口数方面应该是可扩展的。所用的体系结 构必须保证以少数几个端几开始的交换网络，以后能扩展到数十、成百甚至上千个端口。最终用户 必须能以所需的任意端口数开始组网，逐步增加系统容量，而不必浪费其最初的投资。系统端口数 的扩展应该简单到只需插入额外的线卡以及相应的交换芯片卡以支持增加带宽要求即町。 虽然网络交换中的两个主要的部件一交换结构和调度器都有成功开发的集成电路( i c ) 芯片， 但大多郜足由国外厂商研制的，其中的核心技术和知识产权也掌握在国外开发商手中而且受到单 个芯片规模、i 0 管脚数、功耗等i c 工艺渊素的限制，单i c | ：所实现的交换容量和调度容量都有限， 通常只能实现3 2 个端口之问的交换和调度。例如世界上著名的集成电路公司p m c 公司推出的整套 网络交换奄翠决方案中包括3 2 x 3 2 的c r o s s b a r 交换芯片和3 2 x 3 2 调度芯片1 2 j ，端口速率达到l o g b s 。 然而，受到来自芯片本身的管脚、晶体管数、功耗等因素的限制，要想在单片集成电路上实现 更大规模的交换和调度功能( 如2 5 6 2 5 6 ) 就十分困难，端u 数的扩展也就很难实现。 虽然单片电路难以实现大规模交换，但采片j 多级交换结构( m u l t i s t a g e ) 可以解决单片交换电流 的端口扩展问题。多级交换结构是将多个交换单元互联起来的，每个交换单元具有一整套输入输出。 通过互连多个小的交换单元，就可以构建个大型的、可扩展的交换结构。多级结构之i 日j 的刁i 同取 第2 页 第一章绪沦 决于交换荤元之问是如何互联的。典型的结构包括c l o s 网、b e n e s 网、b u t t e r f l y 网等形式。多级结 构虽然在操作上较复杂，但是可以扩展到成百上千个端口，这对于建立下一代i n t e r n e t 核心路由系统 是很有必要的。 然而，网络交换的另一个重要单元一调度器却尚未研究出真正有效的端u 扩展方法。很明显， 只有当网络交换中的两个关键部件一交换和调度都能够真止地实现规模可扩展时，组建下- 一代高速 大容量交换网络才真正成为可能。 所以，研究如何由若干小规模调度器( 称为子调度器) 实现大规模调度的结构，对下一代高速 骨干交换网的建立具有十分重要的理论意义和实际意义。 1 2 本文主要研究内容和结构安排 本课题的研究背景是国家自然科学基金项目“高性能可扩展网络调度系统研究”。众所周知， 下代网络不仪需要更大的容量和更多的端口，而且对交换的延迟、吞吐率和公j i ，性等性能也提出 了更高的要求：一是要能处理更多的端口，二是能实现更岛的端口速率，三是能支持更高级的服务 方式。因此，在调度算法更新的同时，有必要研究发展具有更高性能的网络调度系统。同前，虽然 交换机和调度器都有成功开发的集成电路芯片，但大多部是由国外厂商研制的，其核心技术和知识 产权也掌握在国外开发商的手中，而且受到单个芯片规模、i o 管脚数、功耗等集成电路工艺因素的 限制，单片i c 上所能实现的交换容量和调度容量都是有限的( 如通常只能实现3 2 x 3 2 ) ，要想在单片 集成电路上实现更大规模的交换和调度功能( 如2 5 6 x 2 5 6 ) 就十分困难。冈此，有必要研究出一种新的 调度结构以满足下一代网络交换所需的多端口、人容量的要求。岛性能可扩展网络调度系统f s s a ( f a i rs c a l a b l es c h e d u l i n g a r c h i t e c t u r e s ，f s s a ) 1 3 1 正是针对这一问题提出的。f s s a 用若干较小规模 的调度器实现了难以在单片电路上实现的大规模调度器。 本文研究的主要内容之一就是岛性能公平可扩展网络调度结构f s s a 的f p g a 验i j f 实现，具体 为采用4 片x i l i n xv e r t e x - 4 系列f p g a 实现了基于f s s a 的高速6 4 x 6 4 可扩腱嗍络调度系统，测试 结果表明该系统功能止确，单通道速率可达6 4 0 m b p s 。 本文的另一主要工作就是在对常用的组播方案分析的基础上，提 l j 了适用于可扩展调度系统的 纽播实现方式。该实现方式充分复用原有模块，只需增加少量资源，即可使可扩展调度系统具有完 整的单播、组播调度功能。 本文的结构安排如下： 第二章介绍了网络调度系统的发展及主要结构，同时介绍了小同的网络调度算法及其优缺点。 第三章先介绍了f s s a 的结构和丁作原理，然后介绍了本文的重点内容一可扩展网络调度系 统验证平台的设计。 第四章重点即介绍可扩展网络调度系统的测试和分析结果。 第l i 章描述了基于可扩展网络调度系统的组播技术及其r t l 设计。 第六章对全文进行总结，指出了有待进一步研究的工作及建 义。 最后足致谢和作者攻读硕士学位期问发表的论文。 第3 页 第二章网络调度系统及算法概述 第二章网络调度系统及算法概述 2 1 网络调度系统的发展 2 1 1 传统的网络调度系统 网络调度系统的主要设备是路由器，路由器j 【作在o s i 参考模型的第三层一网络层，完成数据 包的转发任务，实现网络互连，通过与网络上其它路由器交换路由和链路信息来维护路由表，通过 动态维护路由表来反映当前的网络拓扑。传统的路由器一般用一个或几个r i s cc p u 进行路由处理、 安全过滤处理，并计算路由信息表，进行系统维护。 第一代路由器一 连接各接口模块的内部总线为路由器伞体线路接u 所共有，每个分组要经过两 次共享总线才能完成分组的转发。随着网络上业务量的增加及接口模块的追加，总线上数据也随之 增加，这就降低了路南器的性能；再加上分组的寻路、转发都足由软件处理，业务量的增加加重了 c p u 的处理负担，使路由器1 i 堪重负。 为了解决第代路山器存在的问题，第二代路由器增强了线路接口卡的功能，该卡上配有一定 容量的存储器，另外还有木地c a c h e 存储路由信息。当某一个数据流的第1 个分组到达时，该分组 被送往c p u ，c p u 上的软件在做出转发决定后，在接口卡的本地c a c h e 中加入转发信息：此后到达 的属于该流的分组就可以通过查询线路 上的c a c h e 来进行转发了。这样，如果c a c h e 的命中率较 岛，人部分的分组只需要使用一次共亨总线，这就提岛了系统的吞吐能力，同时，c p u 的处理负担 也得以大大减轻。第二代路南器解决了部分问题，但是仍然存在如下缺点： 1 ) 随着i n t e r n e t 规模不断的扩大，路由器的端口速率不断增加，主干网路由器每个端口上同时 存在的流的数目也不断增加。由二i 二局部缓存c a c h e 的容量有限，这就不可避免地造成c a c h e 命l f l 率 的下降，从而降低路由器的性能。随着路由器端u 速率的不断增加，这个缺点会越米越明显； 2 ) 共享总线方式所能提供的带宽不能适应网络发展的需要。目前其所能提供的最高带宽是 2 0 g b i t s 。对于主- t 网路由器米说这样的速率仍然太低，而兆享总线的带宽很难再提高。 2 1 2 交换式的网络调度系统 为了解决第二代路南器存在的问题，第三代路由器对其总体结构做了重大的改进。它采用了分 布式的体系结构，一个路由器内有多个处理单元，可以同时对进入线卡的分组进行寻路，如图2 1 所 示。同传统的集l f l 式结构相比，其系统性能得到了很人改进，具有如下特点：支持t c p i p 协议，大 人减轻了的路由器的负担，加快了其处理分组的速度。随着网络的发展，t c p i p 协议已经在网络卜 占据了统治地位。数据通道与管理通道部分分开。采用交换结构代替共享总线方式，大大提高了系 统的总容量。许多路由器能够根据i p 分组的源l p 地址、目的i p 地址、协议类型、源端几号和目的端口 号对分组进行分类，对不同种类的分组提供不同的服务( 称第四层交换) 。大多数交换式路由器在 交换时采用定长的信元，这一点与a t m 交换机类似。 第5 贞 东南大学硕士学位论文 图2 1交换式网络调度系统结构 2 2 交换式网络调度系统的结构 常用的交换式网络调度系统的结构有输入队列交换( i q ，i n p u tq u e u e ds w i t c h ) 、输出队列交换 ( o q ，o u t p u tq u e u e ds w i t c h ) 、输入输 i 组合交换( c i c q ，c o m b i n e di n p u to u t p u tq u e u e ds w i t c h ) 等方式，主要是根据缓冲数据所存放的位置来区分的。 2 2 1 输入队列( i q ) 交换 输入队列交换是指将缓冲数据放置于输入端u 的交换结构，其结构如图2 2 指所示。 一二二1 卜 一：二i ) 一 f 图2 2 输入队列交换结构 基于输入队列交换的优点是存储器仅需要上作于2 倍加速比，这是因为输入队列交换在同一时 隙内最多只能有一个包到达、一个包离开缓冲区。但其缺点是不采用内部加速，因此会导致吞吐量 的降低。当两个队列中的包要去往同一个输出端几时，就会发生队头阻塞( h e a do f l i n e ，h o l ) ， 影响其执行效率。h o l 产生的原迭l 在于输入端口等待交换的分组使用f i f o ( f i r s ti nf i r s t o u t ) 输入 排队策略。即当一个分组移动到输入队列的队首时，如果目标输出端u 正忙，则它将在该队列中等 待，直到目标端口空闲。当某一个输 j 端u 空闲时，它交换最先处于等待位置的分组。也就是说， 每个时隙到达时，j 有在缓冲器队首位置的分组彳能参与输出端口的竞争，且每个输出端几最多只 能接受一个分组。显而易见，在f i f o 队列中，当队首的分组受阻时，跟在其后的所有准备发送的分 组也都将受阻，即使当前时隙该分组指向的输出端口处于空闲状态也无法参与交换，即空闲的输出 端u 处丁“饥饿，( s t a r v i n g ) 状态。从理论分析和计算机模拟研究可知，对于输入缓冲采用f i f o 队 列的n x n 交换机，由于h o l 阻塞的影响，在相同随机流量情况下，交换端口能达到的最大吞吐率 被限制在2 一2 = 5 8 6 i o j 。而周期性的队首位置阻塞则町能导致更差的效果。 2 2 2 输出队列( o q ) 交换 输 f 队列交换足指将缓冲数据放置丁输：i j 端u 的交换结构，其结构如图2 3 如示。 第6 页 第二章网络调度系统及算法概述 一 一 i 璺| 2 3 输出队列交换结构 因为输出队列交换方式在输入端口没有设置缓冲区队列，所有到达的包必须立即送往输i i 端口。 从吞吐最和时延特性的角度来看，这是有利的。但是所有到达的包同时传送到输出端口需要更多的 内部连接带宽和存储器带宽。对于一个n x n 的交换结构，可能有n 个包同时到达任意一个输j i j 端 口。要在一个时隙犟接收n 个包，输出缓冲区队列的存储器必须能在一个时隙里完成n 次写入，传 送到存储器的内部线路速率也必须为包到达速率的n 倍。这就需要一个内部加速比为n 的交换网络。 对于高速路由器，这种结构上的缺点限制了它的发展。 2 2 3 输入输出( c i o q ) 交换 输入输出组合交换是指在输入端和输出端都设置缓冲数据队列的交换结构，其结构如i 刳2 4 所 示。 ：i 卜 三二：1 卜 _ r ， - 二：d 二 ) 一一 一一u 一 图2 4 输入输m 交换结构 通过合理安排，任何规模任何类型到达的交换网络，c i o q 的加速比为4 时，可以完全相同地仿 效f i f o 输出缓冲队列工作。而且它适用于一大类广泛使片j 的o q 调度算法，仉足目前基_ 丁此种结构提 出的调度算法复杂度过高，难以实现。 2 2 4 几种交换结构的比较 网络交换的三种体系结构中o q 方式由于其物理实现难度大，在实际中很少使用；i q 和c 1 c q 交换方式在实际中应用较多。同时和c i o q 相比，l q 交换方式由于容易用硬件实现而得到j “泛应用。 在l q 交换方式中，人们提出了用虚拟输出队列v o q ( v i r t u a lo u t p u tq u e u e ) 来解决对首阻塞 问题，即为每个输入端口保存一组v o q ，来自该输入端口的所有目的地相| 一j 的包被存放在同一个队 列中，等待调度和转发。假设整个交换系统需要实现6 4 x 6 4 的交换，则每个输入端的v o q 的队列 数应为6 4 个，每个队列对应个输h 端口。这种虚拟输出队列机制的采用解决了刚扰l q 交换方式 的一大难题即对头阻塞问题，研究证明，若不采用虚拟输出队列机制，系统的吞吐率最大只能达到 5 8 6 。图2 5 为实现n 个端口i q 交换的原理框图，图中来自n 个线卡的输入l n p u t li n p u t n 于 交换机构的n 个输入端相连，各线卡上接受到的数据包根据输出目的地的不i 列被分别存放在相席的 虚拟是输出队列v o q l 广v o q i n ，v o q 2 l v o q 2 n ，一和v o q n l v o q n n 中，在调度器的摔制下，通 过交换机构( c r o s s b a r ) 被交换到n 个不同的输出端口。 第7 页 东南大学硕士学位论文 v o qi l n 图2 5 基于v o q 的i q 交换 在该种结构中，交换机构实际上是一组物理开关，实现任意n 个输入到任意n 个输出的连接和 断开，开关的开和关则是由调度器产生的挖制信几控制的。由于与变换结构相连的锥个输入端口都 有一组v o q 队列，存在同时有多个来 j 不同输入端的包等待去往同个h 的地的现象，仉通常在。一 个时隙( t i m es l o t ) 里，岁 能有一个包去往该输出端，因此，需要调度器对其进行合理的涮度。 2 3 网络调度算法概述 调度器的丰要功能就足在每个时隙内产生一组摔制信号，控制该时刻将有来i ，i 哪些输入端的包 通过c r o s s b a r 参与交换。冈此，整个系统性能的好坏很大程度上取决于调度器性能的好坏，也就是 与调度器l - 的调度算法密切相关。 高性能路由器调度算法的性能好坏主要集中体现在以下几个方面：1 ) 算法的延迟，保证不吲服 务类型的数据包时延要求：2 ) 算法的效率，包括带宽利用率、r 奋吐率；3 ) 算法的稳定性，即小同流 量模式下均具有稳定的处理能力；4 ) 算法的扩展性，需要支持组播、混播、支持优先级服务：5 ) 硬 件实现简单。近几年，国内外对调度算法研究丰h 当活跃， n 南于提出算法都有着这样或者那样的不 足，因而只有少数得剑了应用。 输入队列交换中基于v o q 结构的调度算法主要分为两人类：最大尺寸匹配算法( m a x i m a ls i z e m a t c h i n g ：m s m ) 和最大权匹配算法( m a x i m a lw e i g h tm a t c h i n g ：m w m ) 。前者以p i m i j ，r r m 0 2 i ， i s l i p l l 3 l ，和f i r m ! i 等为代表，硬件实现简单，然而与极大权匹配算法相比，其性能表现却不容乐 观。后者以l q f i ”l ，o c f l l q 【以及l p f ! 仃1 等算法为代表，他们在绝大多数流量模式下都能很好的满 足低延迟与大吞吐量的性能要求，然而由j ：硬件电路难以实现，很难在实际中应用。下面分别介绍 几种典型的渭度算法 2 3 1 i s l i p 算法 i s l i p 算法( i t c r a t i v er o u n d r o b i ni nm a t c h i n gw i t hs l i p ，简称i s l i p ) 在充分保证算法高效的基础上实 现了算法的公平和稳定包括以下三个步骤