（通信与信息系统专业论文）大规模接入汇聚路由器（acr）交换网络的研究与实现.pdf

中文摘要信息时代的来临使得i n t e r a c t 网上的信息量以爆炸式的速度急剧增长。这就要求新的互联网设备能够实时地对海量信息进行传输，交换和处理。随着光纤的大规模使用，数据传输速度得以很大地提高。但由于工艺水平和理论发展的相对滞后，数据交换设备成为整个互联网发展的瓶颈。因此大容量，高性能路由器的研制成为网络技术发展的关键之所在。本文结合国家8 6 3 项目“大规模接入汇聚路由器( a c r ) 系统性能与关键技术研究”，从交换结构模型的角度研究了高速路由器调度算法及其实现技术。在对现有交换结构和调度算法分析比较的基础上，我们提出了联合输入队列与交换矩阵队列( c i s f q ) 的结构，证明该结构在2 倍加速的情况下，使用尽职工作的调度算法能够提供1 0 0 的吞吐量和速率的保证。针对这种结构提出了支持变长分组的调度算法，并给出了该结构在a c r 路由器中的实现方案。本文所做的主要工作如下：1 研究了不同交换结构中缓存设置的原则，并分析了各种结构的优缺点，指出它们在实现高速交换、q o s 保障、组播支持时所面临的挑战，为a c r 路由器交换网络的设计提供参考依据。2 针对a c r 路由器的实际需求，本文提出了一种联合输入队列与交换矩阵队列( c o m b i n e d i n p u t a n ds w i t c h f a b r i c q u e u e ，c i s f q ) 的结构，通过增加匹配缓存消除了输入端口之间的冲突，并从性能保证的方面对其进行了论证，特别是在满足强大数定理和可控到达流的情况下，该结构可以提供1 0 0 吞吐量和速率保证，为a c r 路由器的设计奠定了理论基础。3 结合实际网络中传输的是变长分组的现状，对已有的r r r r 调度算法进行改进，提出了易于实现的基于变长分组的二次轮循调度算法，并对交换网络中如何实现组播功能进行了初步的分析。4 在a c r 路由器的总体框架下，根据本文提出的设计方案在f p g a 上实现1 6 0 g 的交换单元。通过增加输入交换和输出交换模块实现了容量的扩展，并给出了扩展到t 比特级的实现方案。关键词：路由器；交换网络；调度；联合输入队列与交换矩阵队列；基于变长分组的二次轮循第l 页a b s t r a c t1 1 1 ec o m i n gi n f o r m a t i o na g eb r i n g st h ee x p l o s i o no ft h ei n t e m e ti n f o r m a t i o ng r o w t h a n dt h i sr e q u i r e sn e wn e t w o r k i n gd e v i c e st ot r a n s f e r , e x c h a n g ea n dp r o c e s st h eh u g ea m o u n to fd a t u mi nr e a lt i m e 1 1 1 er a t eo f t b et r a n s m i s s i o nh a sb e e ng r e a t l yi m p r o v e dd u et ot h ew i d e l yu s eo fo p t i c a lf i b e rt h e s ey e a s b u tt h er a t eo fs w i t c hi sb e c o m i n gt h eb o t t l en e c ko ft h ew h o l ei n t e m e tg r o w t hb e c a u s eo ft h er e l a t i v e l yl a g g a r dp r o g r e s so ft h es w i t c ht h e o r ya n dt e c h n o l o g y s ot h er o u t e rw i t hh u g ee a p a b i l i t ya n dh i g hp e r f o r m a n c eb e c o m e st h ek e yo ft h en e t w o r kt e c h n o l o g yd e v e l o p m e n t g i v e nt h e8 6 3p r o j e c tr e q u i r e m e n t sf o r t h er e s e a r c ho f p e r f o r m a n c ea n dk e yt e c h n o l o g yo fa c c e s sc o n v e r g er o u t e r ( a c r ) ”，t h i sd i s s e r t a t i o ni sd e v o t e dt ot h er e s e a r c h e so fh i g hs p e e ds c h e d u l i n ga l g o r i t h mf r o ms w i t c h i n ga r c h i t e c t u r em o d e lv i e w p o i n ti nb o t ht h e o r ya n di m p l e m e n t a t i o n b a s e do nt h ea n a l y s i sa n dc o m p a r i s o no fs c h e d u l i n ga l g o r i t h m si ne x i s t e n c e ，w ep r o p o s eac o m b i n e di n p u ta n ds w i t c hf a b r i cq u e u i n g ( c i s f q ) a r c h i t e c t u r e ，a n dp r o v et h a tt h ea r c h i t e c t u r ec a ng i v e1 0 0 t h r o u g h p u ta n dr a t eg u a r a n t e e a c c o r d i n gt ot h ec i s f qa r c h i t e c t u r eav a r i a b l e l e n g t hp a c k e ts c h e d u l i n ga l g o r i t h mi sd e s c r i b e df o re f f i c i e n t l ya c c o m m o d a t i n gi pt r a f f i c a n dw eg i v et h ei m p l e m e n t a t i o n si na c r t h ew o r k so f t h i sd i s s e r t a t i o nc o n t a i n s ：1 r e s e a r c h i n gt h ep r i n c i p l e so fb u f f e rc o n f i g u r a t i o nw i t h i nd i f f e r e n ta r c h i t e c t u r e s ；a n a l y z i n ga n dc o m p a r i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e sa m o n gv a r i o u ss w i t c hf a b r i c ；p o i n t i n go u tt h ec h a l l e n g e so fi m p l e m e n t i n gh i g hs p e e de x c h a n g e ，q o sa s s u r a n c ea n dm u l t i c a s ts u p p o r t i n g s u p p l y i n gr e f e r e n c e sf o rt h ed e s i g no f a c r ss w i t c h i n gn e t w o r k 2 p r o p o s i n ga na r c h i t e c t u r eo f “c o m b i n e di n p u ta n ds w i t c hf a b r i cq u e u e ( c i s f q ) a c c o r d i n gt ot h ep r a c t i c a lr e q u i r e m e n to fa c r t 1 1 i sc i s f qa r c h i t e c t u r ec a ne l i m i n a t et h ec o l l i s i o n sa m o n gt h ed i f f e r e n ti n p u tp o r t sb ya d d i n gm a t c h i n gb u f f e r s d e m o n s t r a t i n gt h ec i s f qa r c h i t e c t u r ef r o mt h ep e r f o r m a n c ev i e w p o i n t ，e s p e c i a l l yw h e nt h ea r r i v a lp r o c e s so b e y sas t r o n gl a wo fl a r g en u m b e r s ，t h ea r c h i t e c t u r eg i v e s1 0 0 t h r o u g h p u ta n dr a t eg u a r a n t e e t h e s ew o r k se s t a b l i s ht h et h e o r yb a s i sf o rt h ed e s i g no f a c r 3 i m p r o v i n gt h ee x i s t i n gr r r rs c h e d u l i n ga l g o r i t h ma n dp r o p o s i n gam o r er e a l i z a b l es c h e d u l i n ga l g o r i t h mc a l l e dp a c k e t - b a s e dr r r r , g i v e nt h es i t u a t i o no fv a r i a b l e - l e n g t hp a c k e t st r a n s m i t t e di nt h en e t w o r k ；e l e m e n t a r ya n a l y z i n go fh o wt oi m p l e m e n tm u l t i c a s ti ns w i t c h i n gn e t w o r k 4 i m p l e m e n t i n g1 6 0 g b p ss w i t c hu n i to nf p g aw i t h i nt h ef r a m e w o r ko fa c ra c c o r d i n gt ot h ep r o p o s e dd e s i g na r c h i t e c t u r e b ya d d i n gi n p u t s w i t c hm o d u l e sa n do u t p u t - s w i t e hm o d u l e s ，w ee x p a n dt h ec a p a b i l i t yu pt ot e r a b i t k e yw o r d s ：r o u t e r ；s w i t c h i n gn e t w o r k ；s c h e d u l i n g ；c i s f q ；p a c k e t b a s e dr r r r第i i 页笪：垦二堡盔兰堡兰生丝茎图目录参考交换模型。5o q 交换结构模型6优先级调度。7非尽职工作调度9i q 结构模型1 0v o q 扫 队1 li s l i p 算法1 2w f a 算法l ：!l q f 中的短队列饿死1 3i l q f 算法1 4改进的e d m o n d s k a r p 算法1 6i l p f 算法1 7c i o q 结构模型1 8c i s f q 的内部结构。2 0调度阶段示意图。2 1t m 0 的情况2 3最坏情况下缓存大小的设置2 8单级交换网络模块。3 0两种轮循方式的比较3 1输入出调度算法流程图3 2输入端口中完成组播报文的复制。3 3交换矩阵中完成组播报文的复制。3 4c i s f q 中的组播3 4a c r 路由器系统级总体结构3 6路由单元之l 日j 数据平面互连示意图。3 7路由单元内部结构3 8交换网络模块在系统中的位置。3 9单元级交换网络结构。4 0交换网络模块逻辑划分。4 0输入端口组播实现门级图。4 3轮循调度模块的实现。4 4交换网络实物图4 5单元级交换网络的测试连接图4 5不同分组长度下的丢包率。4 6不同分组长度下的端口吞吐量( 单位：千包每秒) 。4 6不同分组长度下的平均时延( 单位：微秒) 4 6第v 页：04 ，0 ，0 ，mn 屹bhb怕他侈加m挖拐抖筋拍”勰凹如”砣驺m弘”图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图独创性声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中标注和致谢的相关内容外，论文中不包含其他个人或集体已经公开的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文题目：太规撞接厶堑鐾堕自矍( 垦交缝囝终的班究生塞现学位论文作者签名：赵盘；氐日期：2 矿9 石年莎月2 莎日学位论文版权使用授权书本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 涉密学位论文在解密后适用本授权书。)学位论文题目：太趣撞撞厶歪聚蹬由墨( b 2 銮逸圆终的硒究皇塞现学位论文作者签名：赵盘遗日期：2 口衫年多月2 莎日作者指导教师签名：羔哑日期：。跏年月彳日信息二r 稃大学硕十学位论文第一章绪论1 1 研究背景1 9 6 9 年，美国国防部下达a r p a n e t 网络的研制计划，建立了第一个分组交换的计算机网络。网络技术的兴起，推动了社会经济的飞速前进，社会经济的不断前进又反过来对互联网络提出了更高的要求。信息时代已经到来，资源的共享和信息的实时获取是信息时代的一大特征，而这一切都要依靠各种网络来实现。目前主要存在三大网络：电信网，有线电视网，和计算机网。三大网络各有优缺点，但最大的问题是每个网络都是业务相关的，各自只能承载单一的业务，无法做到互联互通。网络的分散建设不利于资源的有效共享，重复建设也是对资金的浪费。电信网、计算机网、广电网的三网融合一直是业界的一个焦点，随着信息技术的飞速发展，三网合一的趋势愈发明显。从技术的层面上讲，交换的全i p 化趋势和基础光传输设施的宽带化趋势，构成了未来网络技术的总体发展方向，而两者之间的交叉与融合则是这一总体方向的核心技术基础。因此电视与电信业务的i p 化以及依靠光纤传输，是三网融合的必由之路。三网融合的趋势对核心路由器的容量提出了更高的要求，传统的互联网业务以传输数据为主，对网络带宽、服务质量以及传输时延并没有特殊的要求。随着技术的不断进步互联网的业务走向语音、数据以及多媒体整合的趋势，用户开始要求更高的带宽，更稳定的品质，以及网络电视( i p t v ) ，视频点播( v o d ) ，网络电话( t pp h o n e ) 等多种应用，基于以上几点路由器走向高性能，大容量势在必行。由国家数字交换系统工程技术研究中心承担的“大规模接入汇聚路由器( a c r ) 系统性能与关键技术研究”项目为国家“十五”8 6 3 计划信息技术领域高性能宽带信息网的重大项目。本课题以此项目为背景，对该项目的交换网络进行深入地研究，在参考前人的成果基础上，接合当前的器件工艺水平，提出切实可行的交换网络模块方案并实现。1 2目前存在的主要问题在光通信领域，光纤传输速率每1 0 年增长1 0 0 倍，这种趋势还能持续l o 年【1 l ，目前实用化的w d m ( 波分复用) 系统速率己达3 2 0 g b p s ，已能满足近几年内互联网对传输介质带宽的要求。但是与传输设备的所能提供的带宽相比，现有交换设备的吞吐量远远达不到与之匹配的水平，因此交换设备已成制约网络速度的瓶颈。作为网络中的主要交换设备，路由器要为网络中的数据提供大容量低时延的交换，而其中的交换网络模块更是整个路由器的核心，它直接决定着路由器的交换容量，时延以及对服务质量( q o s ) 和组播的支持。结合我国目前的需要和今后几年的发展，我们提出了单机架1 6 0 g b p s ，多机架互连时可以完成1 2 8 t b p s 的交换容量。并且为了支持多媒体，要求交换能够更好地支持组播业务。第1 页信息t 释大学硕十学付论文交换结构和调度算法经过多年的发展已经形成了完整的体系但同时也存在着一些问题。输出排队( o q ) 能够提供很好的性能保证以及服务质量保证( q o s ) ，但是对于一个n x n 交换网络为了达到1 0 0 的吞吐量需要在n 倍加速下工作，随着网络传输速率的不断提高和端口密度的增加，这个条件越来越难以实现。输入排队( i q ) 通过使用虚拟输出排队( v o q ) 的机制可以克服队头阻塞( h o l ) ，并且在使用最大权重匹配算法( m w m ) 的情况下输入排队不需要加速就可以实现1 0 0 的吞吐量【2 1 。但是最大权重匹配仅有理论意义，在实际中往往使用极大匹配来代替最大匹配，经过多次迭代运算实现匹配。输入排队调度一般都需要一个集中的调度器，这就限制了其扩展的能力，因此也不适合用在大容量的路由器上。就交换矩阵的结构来讲目前在核心路由器上最为常用的是c r o s s b a r 结构，这种结构依然要求集中式调度和定长的信元格式，在实现大容量的可扩展交换时，该交换的处理复杂度依然很高，并且由于定长与变长相互转化的原因还需要额外的开销。并行分组交换( p p s ) 【3 1 为大容量可扩展交换的设计提供了一种思路，它不仅可以提供良好的服务质量，而且还具有灵活的可扩展性。但是现有对并行分组交换的研究都是建立在以输入排队交换作为子层交换单元的基础上的，这使得子层交换单元的设计依然面临着同输入排队交换相同的问题。1 3 本文的主要贡献本文以国家“十五”8 6 3 计划信息技术领域高性能宽带信息网的重大项目“大规模接入汇聚路由器( a c r ) 系统性能与关键技术研究”项目为依托1 4 】，在总结前人工作的基础上分析了各种因素对交换性能的影响。提出一种易于实现的交换结构并对其性能进行了分析，针对这种结构提出一种并行调度算法并在f p g a 上完成了设计。本文主要的工作有以下几点：在对交换结构和调度算法进行了深入研究的基础上，总结了不同结构中缓存设置的原则，并分析了各种结构的优缺点，指出它们在实现高速交换、q o s 保障、组播支持时所面临的挑战，为a c r 路由器交换网络的设计提供参考依据。针对a c r 路由器的实际需求，本文提出了一种联合输入队列与交换矩阵队列( c o m b i n e d i n p u ta n ds w i t c h f a b r i c q u e u e ，c i s f q ) 的结构，通过增加匹配缓存消除了输入端口之间的冲突，并从性能保证的方面对其进行了论证，特别是在满足强大数定理和可控到达流的情况下，该结构可以提供1 0 0 吞吐量和速率保证，为a c r 路由器的设计奠定了理论基础。结合网络中主要传输的是变长分组的实际情况，对已有的r r r r 调度算法进行改进，提出了易于实现的基于分组的二次轮循调度算法，并对交换网络中如何实现组播功能进行了初步的分析。在a c r 路由器的总体框架下，根据本文提出的设计方案在f p g a 上实现1 6 0 g b p s的交换单元。通过增加输入交换和输出交换模块实现了容量的扩展，并给出了扩展到t 比特级交换网络的方案。第2 页信息丁程大学硕十学付论文1 4 本文的结构和安捧本文其他章节的安排如下：第二章中首先给出了交换的参考模型，以及常用的概念和衡量交换系统性能的一些指标。然后从交换网络队列结构的角度对当前已有的交换结构作了归纳和总结，并对每种结构下对应的不同调度算法进行了分析对比。第三章提出了c i s f q 交换结构模型，并从性能保证的方面对c i s f q 结构的吞吐量，速率保证进行了论证分析。得出在2 倍加速的情况下，使用尽职工作的调度算法c i s f q 结构可以实现1 0 0 的吞吐量，并且能够模拟一个受限的w r r - o q 交换，从而提供速率保证，为后续章节提供理论基础。第四章中针对c i s f q 交换结构提出了一种基于变长分组的二次轮训调度算法，并进一步设计了完成分组调度的算法流程。针对变长分组的的特点和网络流量的实际特点，研究分析了设置匹配缓存大小时需要考虑的因素，以及组播的实现方法。第五章以三、四章的理论和设计方案为基础并对其进行合理的简化和修改，给出了实现方案，重点介绍了轮循机和组播交换的实现方法。并结合项目的要求给出了基于这种方案如何将交换容量扩展到t 比特的方法。第六章对全文的内容进行了总结，并根据路由器的发展现状对交换技术的未来发展趋势做了预测和展望。第3 页笪：垦三翌奎堂里兰笪丝茎第二章现有交换结构及调度算法的分析研究本章给出了交换的参考模型，结合模型对衡量交换性能的指标进行了说明，并解释了在文章中出现的一些术语。交换结构和调度算法是交换领域研究的主要内容，交换结构决定了报文在交换系统中的缓存方式，对整个系统的可扩展性也有着重要影响。调度算法的本质是解决冲突，即多个客户争用一个服务器的时候调度算法决定以什么样的策略对其进行服务，并确保交换性能的可预测性。通过分析现有的交换结构和调度算法，为a c r 路由器交换网络模块的设计实现提供参考。2 1 交换的参考模型从整个路由器的角度来看，交换网络模块可以看作是一个有n 个输入端口和n 个输出端口的黑匣子。每个输入端口都以速率r 发送去往各个输出端口的数据，数据可能为定长叫做信元( c e l l ) ，也有可能为变长叫做包，报文或者分组( p a c k e t ) 。每个数据都带有要去往端口的端口号，也可以带有用于q o s 的优先级，高优先级的数据优先通过，当发生拥塞时低优先级的数据先被丢弃。同时，数据可以为单播( 只去往一个目的端口) ，也可以为组播( 要同时去往多个目的端口) 。基于以上条件如何设计一个交换系统，能够正确的、低时延的、无抖动的把数据从输入端口交换到输出端口，能够很好的支持q o s 和组播，并具有良好的可扩展性，就是我们所要处理的最主要的问题。如图1 所示，一个交换网络通常可以分为三个部分：1 输入端口( i n p u tp o r t ) ，从输入线路接收数据单元。2 输出端口( o u t p u tp o r t ) ，向输出线路发送数据单元。3 交换结构( s w i t c h f a b r i c ) ，也称为交换矩阵，为所有的输入端口和输出端口之间提供完全的互联。第4 页笪垦二蔓奎兰堡兰生笙奎时隙( t i m es l o t ) ：时隙是指在速率为r 的链路上，发送或者接收一个定长信元所需要的时问。为了达到线速的交换，在没有加速的情况下，一个时隙周期内要完成一个信元的调度。例如，在l o g b s 的链路上交换长度为6 4 字节的信元，其所对应的时隙周期就是：6 4 8 1 0 1 0 9 = 5 1 2 n s ，也就是说交换模块要在5 1 2 n s 的时间内完成对这个信元的调度。加速比( s p e e d u p ) ：假设输入和输出链路每个时问段都传输一个数据分组，交换内部链路速率与输入链路速率的比率称为交换的加速比。一般情况下，加速比越高，交换矩阵内部堵塞率也就越小，但是整个系统的造价也就越高。因此单纯的提高加速比以减少交换的堵塞并不是一个明智的做法【5 1 。模拟( m i m i c ) ：两个同样的报文分别同时进入两个不同交换系统，如果能同时完成交换离开，那么这两个交换系统就可以相互模拟。f a r m1 9 9 5 给出了交换系统的基本性能指标：1 吞吐量( t h r o u g h p u t ) ：是指交换设备在不丢包的情况下能够提供的最大速率。在做理论研究时经常将其归一化( 整体输入流速率输出速率) ，吞吐量是衡量交换性能的一个重要指标。2 利用率( u t i l i z a t i o n ) ：平均输入速率最大输出速率。3 丢包率( 1 0 s sr a t e ) ：在网络中传输数据包时丢弃数据包的最高比率。数据包丢失一般是由网络拥塞引起的。4 时延( d c l a y ) ：时延是指数据包第一个比特进入路由器到最后一比特从路由器输出的第5 页信息t 稃大学硕十学位论文时间问隔。在测试中通常使用测试仪表发出测试包到收到数据包的时间间隔。时延与数据包长相关，通常在路由器端口吞吐量范围内测试，超过吞吐量测试该指标没有意义。5 缓存容量( a m o u n to f b u f f e r i n g ) ：交换中需要的缓存大小。6 复杂性( c o m p l e x i t y ) ：复杂性指的是算法复杂度和工程中的易于实现性和易于扩展性。高速网络中传输一个分组的时间很小，所以调度算法必须能在很短的时间完成对分组的调度，因此调度算法必须有很小的复杂度。而且好的调度算法应该易于硬件实现，且具有良好的可扩展性。2 2 现有交换结构及算法分析对于交换的研究主要集中在两个主要方面，一是交换的结构( 排队的机制) ，二是调度算法。交换结构分类的方法有很多，通常根据数据队列的位置把交换结构分成输出排队( o q ) 、输入排队( i q ) 、联合输入输出排队( c i o q ) 。交换系统中队列的设置为信元提供了缓存的方法，是影响可扩展性的主要因素。不同的排队机制下有不同的调度算法，其性能也不尽相同。2 2 1 输出排队结构和调度算法o q 结构中所有缓存队列都设置在输出端口处，如图2 所示。输入的信元在输入端没有任何停留直接完成交换送到其目的端口，当有多个输入分组要同时去往同一个输出端口时，为了不影响交换的性能，要求内部互联网络能够同时将这多个分组同时送到目的端。在最恶劣的条件下( 个输入端口的分组要同时去往同一个目的端口) 内部互联网络要求加速倍，为了不产生输出端口冲突则要求输出端的缓存能够同时处理倍链路速率的写操作。由于输出链路无法送出同时到达的信元，因此，到达的信元需要暂存在队列中，等链路空闲时再输出这些信元。图2o q 交换结构模型最常见的o q 交换实现是共享缓存方式【卅。这种方式下共享缓存要同时被所有输入和输出端口访问，每个时隙最大要处理个读操作和个写操作。显而易见，共享缓存的带宽是限制交换容量的主要因素。一种提高交换容量的方法是将共享缓存分割成个独立的缓存单元，每个对应一个输出端口，这样就将每时隙访问缓存的速率由2 n 减小到 1 。然而，这要求具有全m e s h e d 结构的中间互联网络来连接输入和缓存端口。这种全m e s h e d的结构由于在板级布线方面比较复杂，这同样影响了该结构的可扩展性。第6 页信息t 程大学硕十学伊论文基于输出排队结构的调度算法由于结构优势，可获得高的吞吐量和提供q o s 保障【7 】【3 】，缺点是未能充分利用存储器带宽。早期的路由调度算法多是基于此种结构提出的，根据文献发表时间看，此领域的经典算法多数在1 9 9 5 年以前提出，随后几年的研究不多，一般是对以前算法的一些小改进。但从2 0 0 2 年i n f o c o m 会议内容来看，此种结构的研究有所升温。基于输出排队结构的调度算法由于存储器访问速率的限制，使其很难适用于大容量的路由器，因而本部分的介绍较为简略。基于输出排队结构的q o s 调度算法：在基于输出排队的调度算法研究中，通常按调度服务器的输出队列在队列非空时是否持续处于工作状态，把所对应的调度算法分成尽职工作( w o r kc o n s e r v i n g ) 型和非尽职工作m o n - w o r k c o n s e r v i n g ) 型两大类。l 尽职工作型调度算法在以下一些尽职工作型调度算法中，都采用了类似的优先级排序队列机制，其核心思想是在所设计的调度算法中都维持一个全局的优先级状态变量，每当有分组需要调度时，此优先级状态变量按相应算法进行更新并被作为分组的优先级赋予该分组，在随后的实际输出队列时，分组被按优先级顺序排序并依次输出到输出链路。如图3 所示。图3 优先级调度由上述可见，在以下的算法中如何维护和更新此全局的优先级状态变量是它们之间的主要区别所在。主要提出了如下一些尽职工作的调度算法：v c ( v i r t u a lc l o c k ) 算法【9 】。本算法以一个时分复用( t d m ) 系统作为调度服务器的模拟对象。算法维护的优先级状态变量称为a u x i l i a r yv i r t u a lc l o c k ( 用a u xv c 表示) 。当有分组到达时，根据分组所属流的输出链路平均带宽计算相应的改变值v f i e k 并有a n xv c = m a x ( a , a u xv c ) + v t i e k ，a 表示分组的实际到达时刻。随后将修改过的a u x v c 值赋予所调度的分组作为其调度时的优先级。在文献l i 仉l l 】中已经证明，当所调度的流满足漏桶模型时，v c 算法可以保证端到端时延、时延抖动和相应的缓冲器大小等调度性能有确定的上界。d e l a y e d d ( d e l a y - e a r l i e s t - d u e d a t e ) 算法【1 2 1 。第7 页信息t 程大学硕十学付论文此算法扩展了传统的e a r l i e s t d e a d l i n e f i r s t 调度。在算法中维护的优先级状态变量称为e x p e c t e dd e a d l i n e ( 用e xd 表示) 。算法中假定所调度的流满足( x m i n ，x a v e ，i ，s m a x ) 模型并假定有确定的本地( 调度) 时延d 当有分组到达时，根据分组所属流的到达时间间隔下界值x m i n 等参数，计算并修改e xd = m a x ( a + d ，e xd + x m i n ) ，a 表示分组的实际到达时刻。随后将修改过的e xd 值赋予所调度的分组作为其调度时的优先级。当所调度的流满足假定时，本算法可以保证端到端时延、时延抖动和相应的缓冲器大小等调度性能得到确定上界。由上述可知，上面两种调度算法在更新其优先级状态变量时都只考虑当前所调度的流的特性。而另有一些调度算法在进行优先级状态变量更新时，同时考虑流本身和调度系统其它流的特性。如w f q l l 3 - 1 5 、w f 2 q 1 6 1 、w f 2 q + i m 、s c f q 1 8 1 、s f q t l 9 1 等调度算法中，各算法都试图模拟一种理想化的流量公平队列( f l u i df a i rq u e u e i n g ，f f q ) ，也称广义处理器共享策略( g e n e r a l i z e dp r o c e s s o rs h a r i n gp o l i c y ，g p s ) i 作模型。在这种工作模型里，所有参与调度的工作流各自组成缓冲队列。在任意的时段内，调度服务器从所有非空队列中各取队列头任务，按照各工作流的服务速率同时进行服务。这样各工作流都按照其分得的处理服务器服务配额，公平地共享处理服务器的服务。在分组网络环境下实现g p s 算法时，由于能够进行调度的最小任务粒度为分组，所以，在分组进入各自流的缓冲队列时必须由调度算法为其加上调度优先级标记，并依此顺序逐次调度各分组进行服务，才能模拟上述g p s 系统进行调度。由于基于输出排队结构的调度算法不适合用于高速路由器，在此就不对上述算法作一一介绍了。2 非尽职工作( n o n - w o r k c o n s e r v i n g ) 型调度算法在以下一些非尽职工作型调度算法中，都可以如图4 中所示的工作框图来描述它们的基本思路。即当有分组到达时，该分组首先进入一个流的调节器( t r a f f i cr e g u l a t o r ) ，通过使用调节算法，使到达分组在适当的时间才可以进行调度输出。在调节算法的设计上可以针对不同的调节目标，如消除时延抖动或速率抖动，进行选择和优化。不同的调节算法和不同的分组输出选择算法的组合可以得到不同的此类工作算法。主要提出了如下一些非尽职工作型调度算法。调节嚣1 褥节器开调节器illll )l；调度输出第8 页信息t 稃大学硕十学何论文图4 非尽职工作调度j i t t e r - e d d ( j i t t e re a r l i e s t d u e d a c e ) 算法【2 0 】。此算法是对d e l a y e d d 算法的进一步扩展。当有分组到达时，首先对该分组进行时延抖动调节，根据该分组中记录的( 由上一中继结点标记) 提前输出时间值a h e a d i 1 ，计算分组的可被调度时间e i = a i + a h e a d i 1 并在调节器中保持此分组直到时刻e i 随后调度算法以此时刻作为分组到达时刻，按照在d e l a y e d d 算法中所述的相同调度机制进行。但在分组被输出时，必须将其输出时刻与希望输出时刻之间的差值赋予a h e a d ，并记入该分组中，以便后继的算法进行。在下面两种调度算法中，都采用了基于周期( f r a m e ) 的调度设计方法。调度算法把调度时间划分为等长的时间段，称为f r a m e 。s t o p a n d - g o 算法【2 1 1 。本算法对各条链路都定义了离开周期和到达周期，其长度为t 一个分组在输入链路的某一个到达周期进入，经过一个确定的时延o ( 0 薹7g r a n t一一a e c e p tr静c i s i o图7i s l i p 算法2 w f a 算法w f a 算法【2 9 j 也是一种用迭代方式逼近m s m ( b i j m w m 算法中的权值因子均为1 时的算法) 算法的典型代表，它易于实现，能够适用于大容量交换中f 2 引。算法如下：( 1 ) 请求。每一个非空未匹配的输入队列，向其目的端口发送一个请求信号。( 2 ) 匹配。使用确定优先级关系的仲裁器，对请求端口进行匹配。仲裁器采用图8 结构进行仲裁。图中每个单元有两个输入信号和两个输出信号。一单元若其左侧或自身有匹配关系，则向右输出指示信号，若其上侧或自身有匹配关系匹配，则向下输出指示信号。一单元若其左侧和上侧均无指示信号，而同时对应v o q 队列发出请求信号，则进行匹配。w f a 算法其单元位置直接决定优先级，缺乏公平性。另p i 女i i s l i p算法一样，对于非均匀型业务，其吞吐量会降低，因而也不宜采用。图8w f a 算法3 p i m 算法p i m 算法是1 9 9 3 年提出的，并首先应用于d e c 公司的a n 2 3 0 l 。但该算法中使用了随机数发生器，因而其速度较慢，很可能不适合用于大容量交换口1 1 。第1 2 页信息工程大学硕十学何论文p i m 算法：( 1 ) 请求。每一个非空未匹配的输入队列，向其目的端口发送一个请求信号。( 2 ) 响应。所有未匹配输出端口在收到请求队列中以等概率随机选取一个响应。( 3 ) 接受响应。所有未匹配输入端口在收到应答中以等概率随机选取一个建立匹配关系。p i m 的主要问题是响应与接受响应中采取随机选取的方式，在高速交换结构中既不经济又会导致速度较慢。本节中介绍的几种算法的共同特点是：他们都是一种无加权的最大匹配，虽然实现上较为简单，但是对于非均匀型业务将导致吞吐量降低。最大权重匹配算法正是为了解决这一问题而提出的。最大权重匹配算法( m w m )最大权重匹配算法( m w m ) 因实现过于复杂只具备理论意义，后来提出了一些采用轮循的最大权重匹配算法是基于此算法提出的，故在此先介绍m w m 算法。匹配x ( t 产【x ”( t ) 】的权重定义为：w ( t ) = q ”o h ”( f ) ，其中连接入口i 与出1 ：3j 的连接的权值为v o q ，队列的l ，j长度q “( t ) 。在每一时隙，m w m 算法选出权重最大的匹配，记作) ( ”( t ) 。上述可用数学表达式表示如下：x ”( t ) = a r g m a x q 9 ( o x 9 ( f ) ，已证明，对于贝努利独立同分布到达业务，m w m 算法可实现1 0 0 的吞吐量【7 】，【1 2 1 。文献【1 证明贝努利独立同分布这一条件可以放宽。此外，许多仿真结果证明它能提供低时延。但是其算法复杂度为0 ( n 25 ) ，在高速路由器中不易实现。l q f ( t h e l o n g e s t q u e u e f i r s t ) 是最早被提出的m a x w e l g h t 算法。l q f 通过给长队列高的优先级，可实现对各类型业务1 0 0 的吞吐量口7 1 。但是给长队列高的优先级，有可能导致短队列得不到服务，以至于出现饥饿现象，如图9 所示。图9l q f q b 的短队列饿死堡丝o u l p u t id ，m j- - - - - - 二二- - 。o u i p t i t2第1 3 页笪皇二堡奎竺堡堂笪丝苎如果后来业务只到q 1 2 ，q 2 1 队列，则另两个队列中的数据包将永远得不到服务。为了解决这一问题，又提出的o c f ( o l d e s tc e l lf i r s t ) 算法改变优先级规则，给等待时间长的数据包高的优先级，显然，这一方式可以避免饥饿现象出现。因为随着数据包等待时间的增加，其优先级也会随着变高，终究是会发送出去的。与l q f 一样，o c f 也可以对各种类型业务获得1 0 0 的吞吐量【2 7 1 。然而上述两种算法复杂度为0 ( n 2 1 0 9 n ) ，只有理论上的意义。就像m a x s i z e 算法可以用p i m 、i s l i p 逼近一样，用在l q f 、o c f 中的m a x w e i g h t算法也可以用迭代算法逼近，称作i l q f 、i o c f 2 ”。以i l q f 为例介绍其算法即实现。1 请求。每一个非空未匹配的输入队列，向其目的端口发送一个请求信号。请求信息中包含权值，对l q f 即是相应队列长度。2 响应。每一个输出端口响应最大权值的请求，连接关系在迭代时可任意断开。3 接受响应。每个输入端口接受最高权值的响应，同样连接关系在迭代时可任意断开。4 重复：1 3 重复n 次或直到上次迭代未能发现更大权值的匹配为止。实现框图如图1 0 所示。看起来他很像i s l i p 或p i m ，然而第二步与第三步中的权重比较使其较i s l i p 复杂得多。在最坏情况下，它需要n 次迭代找到最佳匹配，而实际中仅需l o g n 次迭代即可获得最佳效果【2 9 】。然而每次迭代运算中，n 输入的比较器结构复杂，耗时较多。旦臀窖鹫麓i!且瑚。毒一鬈警盏蛊强瓤：弱二图1 0i l q f 算法第1 4 页信息工程大学硕十学付论文虽然在一定程度上，i l q f ，i o c f 算法降低了原算法的复杂度，但其实现的复杂度为0 ( 1 0 9 b + l o g n ) 1 2 7 1 , 依然相当高。对于n o n - u n i f o r m 型业务，此上两种算法仿真结果明显优于i s l i p 。仿真图参见附录1 。l q f 与o c f 虽然能够在各种类型业务下获得1 0 0 的吞吐量，然而由于其算法复杂度高，速度慢，缺乏实际意义。a d i s a km e k k i t t i k u l 提出了两种新的算法，l p f 与o p f ，他们虽然是m a x w e i g h t 型算法，但是却可以用m a x s i z e 型算法的方式求解。他们均可以在各种类型业务下获得1 0 0 的吞吐量【2 9 】。m a x w e i g h t 算法运行时间为o l n x l o g n ) ，而m a x s i z e 算法运行时间为o ( n 25 ) 【2 9 】，因而上述算法极大的改进了m a x w e i g h t 算法。而且因为已有许多逼近m a x s i z e 算法的m a x s i z e 型算法，因此逼近m a x s i z e 算法比逼近m a x w e i g h t 算法要容易得多。l p f 的权重矩阵如下式：，j 琢剐4 够 ，三 h 玲。哆，伪21 0 罐i e m i 。e ，l p f 算法即求取最大权重：蕃置k ，铆。可以证明下式：苓& 缈洲2 澎t 。弘l p f 所找出的m a x w e i g h t 匹配同时也是m a x s i z e 匹配【嘲，然而并非所有m a x s i z e匹配都是m a x w e i g h t 匹配。为了使找到的m a x s i z e 匹配同时也是m a x w e i g h t 匹配，必须给请求信号合适的优先级。文献【6 j 已证明：改进后的e d m o n d s k a r p 算法，找出的m a x s i z e 匹配同时也是m a x w e i g h t 匹配。算法简介如下：第1 5 页玎以絮n(da行，乏i l栉s信息t 稃大学硕十学俯论文m o d i f i e df d m o n d s - k a r na l w i f f i t h