（通信与信息系统专业论文）基于并行处理的高速流量平衡技术设计与实现.pdf

中文摘要随着高速光传输技术和智能光网络技术的不断成熟，现代通信网正朝着高速化和宽带化的方向演变。作为高性能宽带信息网的重中之重，高性能路由器必须适应信息容量急剧膨胀和网络业务多样化的需求，t 比特路由器将成为通信骨干网中不可缺少的关键设备。并行交换结构在路由器中的应用使流量平衡问题成为路由器研究中的重要问题，变长分组交换技术给流量平衡机制带来了全新的挑战。本文对变长分组并行交换的流量平衡问题进行了分析和研究，提出了p l cl b a 、带反馈的p l cl b a 、p d d l b 三种具有较高公平性的流量平衡算法以及一种支持业务流保序的流量平衡结构l b f o k ，并给出了以上流量平衡机制的性能分析。本文设计了带反馈p l c l b a 算法的硬件实现方案，该方案在国家8 6 3 重大课题可扩展到t 比特的高性能i p v 4 v 6 路由器基础平台及实验系统中得到了成功应用。本文的主要贡献和工作包括以下几个方面：1 提出了并行交换结构的流量平衡模型，并给出性能评估模型和性能指标定义，为流量平衡算法的研究提供了理论依据；2 针对变长分组交换方式提出了一种基于i p 分组长度分类的p l c l b 流量平衡结构，并给出p l cl b a 、带反馈的p l cl b a 两种基于分组长度分类的变长分组流量平衡算法，以及一种动态分配变长分组的流量平衡算法p d d l b ，分析表明这三种算法都具有较高的公平性，得出带反馈p l cl b a 算法的公平性最佳的结论；3 针对流量平衡过程中同一业务流的分组失序问题提出了l b f o k 路由保序流量平衡结构和p d f c 流量平衡算法，分析表明l b f o k 结构和基于流分类的p d f c 算法具有负载平衡、流保序等优点；4 基于公平性优先的原则选择带反馈p l cl b a 算法作为t 比特路由器的流量平衡机制，给出实现方案，该方案已在国家8 6 3 重大课题可扩展到t 比特的高性能i p v 4 v 6 路由器基础平台及实验系统中得到成功应用并通过性能测试。关键词：路由器；并行分组交换：变长分组交换；流量平衡；流保序第1 页a b s t r a c ta sh i g hs p e e do p t i c a lt r a n s m i s s i o nt e c h n o l o g ya n di n t e l l i g e n to p t i c a ln e t w o r k i n gt e c h n o l o g yg r a d u a l l yb e c o m em a t u r e ，m o d e mc o m m u n i c a t i o nn e t w o r ki sd e v e l o p i n gt o w a r dh i g hs p e e da n db r o a db a n d w i d t h a st h ek e yc o m p o n e n to fh i g hp e r f o r m a n c eb r o a db a n d w i d t i ii n f o r m a t i o nn e t w o r k ，h i g hp e r f o r m a n c er o u t e rm u s tb ea d j u s t a b l et ot h ee x p a n d i n go fi n f o r m a t i o nc a p a c i t ya n dt h en e e do fd i v e r s i t yo fn e t w o r k i n ga p p l i c a t i o n s ，t e r a b i tr o u t e rh a sb e c o m et h ek e ye q u i p m e n to f t e l e c o m m u n i c a t i o nb a c k b o n en e t w o r k t h ea p p l i c a t i o no fp a r a l l e ls w i t c h i n ga r c h i t e c t u r ei nt e r a b i tr o u t e rm a k e st h el o a d b a l a n c ep r o b l e mb e c o m et h ek e yo fr o u t e rd e s i g n v a r i a b l el e n g t hs w i t c h i n gt e c h n o l o g yb r i n g sn e wc h a l l e n g et ol o a db a l a n c em e c h a n i s m t h i sp a p e rm a k e sa n a l y s i sa n ds t u d i e so fp a r a l l e ls w i t c h i n gl o a db a l a n c e ，a n dp r o p o s e sp l c _ l b a ，f e e d b a c k e n a b l e dp l c _ l b aa n dp d d l ba l g o r i t h m st h a tr e p r e s e n tc o m p a r a b l eh i g hf a i r n e s sa n do n el o a db a l a n c ea r c h i t e c t u r et l l a ts u p p o r t st r a f f i cs e q u e n c ek e e p i n gf u n c t i o n t h ep e r f o r m a n c ea n a l y s i so f l o a db a l a n c em e c h a n i s mo f t h ea b o v ea l g o r i t h m sa r ea l s op r e s e n t e dh e r e t h i sp a p e rd e s i g n st h eh a r d w a r ei m p l e m e n t a t i o ns c h e m eo ff e e d b a c k - e n a b l e dp l c _ l b aa l g o r i t h mw h i c hi sa p p l i e ds u c c e s s f u l l yi nn a t i o n a l8 6 3p r o g r a m m e t e r a b i ts c a l a b l eh i 曲p e r f o r m a n c ei p v 4 v 6r o u t e rb a s i cp l a t f o r ma n di t se x p e r i m e n ts y s t e m ，t h ek e yc o n t r i b u t i o n so f t h i st h e s i si n c l u d e ：t h em o d e lo f l o a db a l a n c i n gi np a r a l l e lp a c k e ts w i t c hi sp r o p o s e d t h ed e f i n i t i o n so f t h el o a db a l a n c i n gp e r f o r m a n c ei n d e xa r eg i v e n ak i n do fl o a db a l a n c ea r c h i t e c t u r eb a s e do np a c k e tl e n g t hc l a s s i f i c a t i o nn a m e dp l c l bi sp r o p o s e d p l c l b aa l g o r i t h m ，f e e d b a c k e n a b l e dp l c _ l b aa l g o r i t h m ，p d d l ba l g o r i t h ma r ep r o p o s e da n da n a l y z e d t h ea n a l y s i sr e s u l t ss h o wt h a ta l lt h et h r e ea l g o r i t h m sc a nr e a c hag o o dp e r f o r m a n c eo nd i s t r i b u t i n gp a c k e t sf a i r l y ap a c k e to r d e rk e e p i n gl o a db a l a n c ea r c h i t e c t u r en a m e dl b f o ka n di t sp a c k e td i s t r i b m ea l g o r i t h mp d f ca r ep r o p o s e da n da n a l y z e d t h ea n a l y s i sr e s u l t ss h o wt h a tl b f o kw i t hp d f cm e c h a n i s mg e tt h ec h a r a c t e r i s t i co fl o a db a l a n c i n ga n dp a c k e to r d e rk e e p i n g f e e d b a c k e n a b l e dp l c l b aa l g o r i t h mi sc h o s e nf o r t h et e r a b i tr o u t e rp r o i e c tb a s e do nt h ep r i n c i p l eo ff a i r n e s sp r i o r i t y al o a db a l a n c em e c h a n i s mw i t hf e e d b a c k e n a b l e dp l c l b aa l g o r i t h mi sd e s i g n e d a n dt h em e c h a n i s mi su s e di n 也et e r a b i tr o u t e rp r o j e c ts u c c e s s f u l l y k e yw o r d s ：r o u t e r ；p a r a l l e lp a c k e ts w i t c h ；v a r i a b l el e n g t hp a c k e t ；l o a d _ b a l a n c i n g ；t r a 仟i c es e q u e n c ek e e p i n g第1 i 页笪星三堡奎兰堡主兰生丝苎表目录表1 变长分组交换与定长信元交换的一般性比较7表2 轮询算法和最短队列算法比较1 8表3 分组分类粒度对算法公平性的影响表3 1表4 流量平衡算法的性能比较3 5表5 队列长度表( 模拟数据) 3 9表6 周期t 内流量统计表( 模拟数据) 3 9表7 流分配表3 9表8 流量平衡算法性能比较4 4表9 测试中流量平衡模块输入数据表5 0第v i 页堡垦王塑丕堂堡主兰笪丝苎图目录图1 两级式流量平衡并行交换结构5图2t 比特路由器交换结构8图3 后继无关流量平衡结构1 1图4 后继相关流量平衡结构1 1图5 流量平衡性能评估模型1 2图6 轮询式流量平衡缓存结构图1 4图7p l c l b 结构模型1 9图8p l c _ l b a 算法的缓存结构图2 1图9 采用带反馈p l c - l b a 算法的系统结构2 7图l o 分组分类粒度对算法公平性的影响曲线3 l图1 1p d d l b 算法的分组分配例图3 3图1 2l b f o k 的逻辑结构3 8图1 3 系统级单元化结构4 2图1 4 单元级模块化结构4 3图1 5 流量平衡在系统中的逻辑位置4 4图1 6 带反馈的p l c _ l b a 算法的硬件实现图4 6图1 7t 比特路由器中带反馈的p l c _ l b a 流量平衡算法实现流程图4 8图1 8 流量平衡模块的硬件实现电路图4 9图1 9 测试环境5 0图2 0i p v 4 、i p v 6 两种情况下流量平衡器各输出队列发送图样5 l第v h 页独创性声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中标注和致谢的相关内容外，论文中不包含其他个人或集体己经公开的研究成果。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文题目：基士羞堑丝堡的直适逾量王堑技盔逶让曼塞堡学位论文作者签名：翼卜日期：“年f 月彳日学位论文版权使用授权书本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 涉密学位论文在解密后适用本授权书。)学位论文题1 7 1 ：基王羞征丝堡数直逗盈量垩逝擅丕遮让里塞理学位论文作者签名：作者指导教师签名：日期：伊- ，薛扫- x 日日期：年月日信息1 = 稃大学硕士学仿论文第一章绪论本章介绍了课题的研究背景与来源，简要阐述了全文的主要工作，并给出了全文的结构和安排。1 1 课题背景自从1 9 5 6 年第一个计算机网络建立以来，网络技术得到了极其迅速的发展。因特网带宽的爆发式增长以及用户需求的多样化( 特别是新的流媒体业务的出现) 对网络提出了更高的要求，新的网络设备需要向更高速、更智能、更安全的方向发展。作为高性能宽带信息网的重中之重，高性能路由器必须适应信息容量的急剧膨胀和网络业务的多样化需求。互联网流量的增加对路由器的生产商及研发机构的研制工作提出了更高的要求。路由器需要提供更高的吞吐率，更小的分组时延，以及更好的灵活性。因此，研发t 比特路由器等高性能路由器十分必要。为了提高我国在下一代互联网中的技术竞争力，掌握具有自主知识产权的下一代互联网核心技术，实现关键设备的自主研制，科技部发布可扩展到t 比特的高性能i p v 4 v 6路由器基础平台及实验系统课题，目的是研究未来i p 网络的关键设备和i p v 6 路由器的关键技术，研制具有我国自主知识产权的t 比特路由器作为中国高性能宽带信息网运营的关键设备。t 比特路由器采用并行交换结构1 1 1 2 1 1 1 2 8 1 1 2 9 1 ( p p s - p a r a l l e lp a c k e ts w i t c h ) 来组建高性能大容量的交换网络，并在国际上首次采用变长分组交换方式。并行交换结构的核心思想是利用多个容量较小的交换单元通过并行处理来组建一个大容量的交换结构。通过在输入端口采用流量平衡技术实现负载均衡，使流量在各个小型交换单元中并行处理，然后通过输出端口的复用，从而使其等效或模拟一个输出排队( o q )的交换结构。并行交换结构给路由器带来了交换单元之间的流量平衡问题，流量平衡技术的优劣直接决定了交换单元的负载均衡程度，影响路由器系统的稳定性。变长分组交换是指交换结构直接采用变长的分组进行交换处理。变长分组交换方式使t 比特路由器交换单元的负载不均问题越发突出，成为t 比特路由器设计中亟待解决的重要问题，因此，研究基于变长包交换的流量平衡技术十分必要。目前关于采用变长分组交换方式的并行路由器的研究很少，针对此种结构的流量平衡问题的研究也暂时空白。t 比特路由器的设计无法找到令人满意的流量平衡机制加以应用。为此。结合项目的实际需求，我们开展了基于并行处理的高速流量平衡技术设计与实现课题的研究工作。本课题从工程应用角度出发，通过提出新的流量平衡技术，为高性能路第l 页信息1 = 稗大学硕七学付论文由器的设计和实现提供依据。1 2 前人的工作针对路由器并行交换结构的流量平衡问题，很多学者做了大量的研究工作。s u n d a ri y e r和n i c km e k e o w n 在文献【2 】中提出p p sw i t hr r 的流量平衡结构，采用了轮询的方式进行信元分配，并具有分组保序能力。文献【3 】中提出了一种基于p p s 结构的s qu a 算法，该算法是一种基于最短排队队列的分布式调度算法，其思想是在保证所有流量都平均分配给交换单元的前提下，每次判决都优先将流量分配给排队队列最短的输出f i f o 。s q _ u a 算法降低了信元交换的排队时延，也具有分组保序能力。r r 算法和s q算法也是t比特路由器最初选择的算法，但是经过实践证明，它们_ua并不适用于变长分组交换结构，其对于交换单元的简单轮询选择方式导致长度不同的分组被一视同仁地分配到交换单元中，交换结构的负载均衡性能很低。我们对其性能进行了测试，测试表明，当分组分布为最长分组和最短分组交替发送的极限情况时，交换结构的负载不均程度很高，负载最小的交换单元时间t 内通过的流量值与负载最大的交换单元时间t 内通过的流量值之比接近于0 。由于定长信元交换方式在当前路由器交换结构设计中的统治地位，综观以往的流量平衡机制的研究，目前所有成熟的流量平衡算法都是针对信元分配的。由于信元的长度固定，而分组长度差异很大，由分组长度差异带来的流量分配不均使得针对信元分配的流量平衡算法无法直接应用于采用变长分组交换方式的路由器中。l 。3 本文主要贡献本文研究的总体目标是，结合8 6 3 重大专项课题可扩展到t 比特的高性能i p v 4 v 6路由器基础平台及实验系统的研发，进行相应的理论研究，从而使基于变长分组交换的并行系统流量平衡机制的工程设计和实现由当前的不成熟状态转变到“基本工程设计指导”的状态。本文紧紧围绕以下主要问题展开工作：根据t 比特路由器变长分组交换的需求，如何设计并行交换结构的流量平衡机制，以提高并行交换系统的公平性，满足路由器的性能指标：如何设计流量平衡机制的工程实现方案。本文的贡献和工作主要体现在以下几个方面：提出了并行交换结构流量平衡模型。根据流量平衡模块与后续交换单元的通信关系分为后继无关流量平衡和后继相关流量平衡：给出了流量平衡的性能指标。评价流量平衡算法性能的两个指标为：公平指数和第2 页笪皇三翌奎兰堡兰生丝苎复杂度；提出了p l c l b 流量平衡结构。该结构是一种基于分组长度分类的流量平衡结构；提出了p l cl b a 流量平衡算法。p l cl b a 算法是采用p l c l b 结构的一种分组长度分类流量平衡算法，理论分析表明，该算法可以使并行交换单元的负载达到较好的均衡性：提出了带反馈的p l cl b a 流量平衡算法。带反馈的p l cl b a 算法是在p l cl b a算法的基础上加入反馈机制的一种流量平衡算法，理论分析表明，该算法较之p l cl b a 算法更加灵活，并给出了分组长度的分类粒度对算法公平性影响的分析；提出了p d d l b 动态分配流量平衡算法。p d d l b 算法是一种利用动态分配机制来弥补由于变长分组交换中分组长度不同而引起的流量分配不公平的算法，理论分析表明，该算法能使交换结构达到较好的公平性；提出了l b f o k 结构和p d f c 流量平衡算法。这是一种支持基于业务流的保序的流量平衡结构和其流量平衡算法，分析表明，l b f o k 结构和基于流分类的p d f c 算法具有负载平衡、流保序、开销小等优点；给出了t 比特路由器中流量平衡机制的实现方案。基于公平性优先的原则选用带反馈的p l cl b a 算法作为t 比特路由器的流量平衡机制，并给出实现方案，该方案已在国家8 6 3 重大项目可扩展到t 比特的高性能i p v 4 v 6 路由器基础平台及实验系统中得到成功应用，测试结果表明，该方案较之以往的流量平衡方案的性能更优。1 4 本文的结构和安捧全文共分六章。第一章为绪论，交待了课题背景、研究动机和主要工作；第二章介绍了t 比特路由器的交换结构模型，说明了流量平衡机制的主要作用及目前存在的问题，提出了并行交换结构中的流量平衡模型，并定义了流量平衡的性能评估模型和性能指标，最后分析了两种最基本的流量平衡算法，给出性能分析和局限性分析；第三章提出了一种基于分组长度分类的变长分组流量平衡结构p l c l b ，给出了两种基于此结构的流量平衡算法p l c l b a 算法和带反馈的p l cl b a 算法，并给出了一种动态分配i p 分组的变长分组流量平衡算法p d d l b 算法，针对上述三种算法进行性能分析，分析表明，这些算法能够有效地提高并行交换结构对各交换单元负载分配的公平性，并有较好的可应用性，其中以带反馈的p l cl b a 算法的公平性最高，并且给出了分组长度的分类粒度对带反馈的p l cl b a 算法公平性的影响分析；第四章给出了一种基于流保序的流量平衡结构l b f o k结构及其流量平衡算法p d f c 算法，并做了性能分析，结果表明，采用p d f c 算法的l b f o k结构是一种能够实现基于业务流的保序的流量平衡结构；第五章根据公平性优先的原则，选择带反馈的p l cl b a 算法作为t 比特路由器的流量平衡机制，给出了带反馈的第3 页笪：垦二堡奎兰堡堂笪丝茎p l c _ l b a 算法在t 比特路由器上的实现方案，测试结果表明，该方案较之以往的流量平衡方案性能更优；第六章对全文进行总结，指出本文的局限性，以及下一步的研究工作。第4 页信息丁稃大学硕十学位论文第二章并行交换结构的流量平衡研究流量平衡问题是并行交换结构的重点问题，本章将介绍流量平衡的交换结构背景，分析t 比特路由器中流量平衡的主要问题，并对流量平衡的模型及性能指标进行定义，最后分析基本的流量平衡算法。2 1 流量平衡机制的交换结构模型2 1 t两级式流量平衡并行交换结构文献【4 】中提出了一种两级式流量平衡的交换结构。该结构分两步完成分组的交换：流量平衡与交换调度。我们将此类交换结构引入到t 比特路由器中，提出了一种两级式流量平衡并行交换结构。2 1 1 1 结构模型两级式流量平衡并行交换结构的结构模型如图1 所示：一i ! ：i 。w i t x ：夫i n i e o r t蕊一囱图1两级式流量平衡并行交换结构该交换结构处理i p 分组分为两步：第一步：流量平衡层，将由输入端口到达的分组经流量平衡器均衡分配到k 个交换单元中处理；第二步：交换调度层，每个交换单元完成自身的交换调度功能，最终将分组发送到目的输出端口，t 比特路由器中选用了共享缓存的c r o s s b a r 结构作为交换单元。2 1 1 2 流量平衡的功能描述流量平衡层的功能就是将路由器中的分组均匀地分配到每个并行交换单元中。流量平衡的目的就是保证并行交换结构的稳定性。要想使交换结构达到1 0 0 的吞吐率，则进入交换结构的分组必须在每个交换单元上达到按字节数( 或比特数) 的均衡。第5 页笪星三翌查兰堡主兰笪丝苎下面我们用数学方式描述流量平衡层的功能：假设一个时钟的起始时刻，分组到达交换单元k 对应的流量平衡层的输出队列q k ：一个时钟的结束时刻，分组从q k 中发送；队列长度在一个时钟的中间时刻被测量。令吼( ) 表示系统时刻n ，第k 个队列的队列长度；令a 。( 珂) 表示系统时刻n ，到达第k 个队列的分组个数；令d 。( 胛) 表示系统时刻n ，离开第k 个队列的分组个数；则对于任意队列k ，有q t ( 疗+ 1 ) = 吼( n ) 一d k ( n ) + a k ( n + 1 )流量平衡算法控制到达每个队列的分组个数4 ( 功。而调度算法控制离开每个队列的分组个数b ( 胛) 。2 1 2 变长分组交换i p 分组通过高速路由器的交换结构时，可以采用两种交换方案；定长信元交换或变长分组交换【捌。定长信元交换；在交换结构前，把i p 分组分段成小的定长的处理单元( 简称信元) ，信元在交换结构中完成交换后，于交换结构输出口处，再被重组为i p 分组。本文称之为定长信元交换方案。变长分组交换：直接给i p 分组加上内部标签( 也可能不加) ，采用变长的分组进行交换处理。本文称之为交长分组交换方案。定长信元交换和变长分组交换的选择原则，主要依据以下几点：通信复杂度( c o m m u n i c a t i o nc o m p l e x i t y ) 。通信复杂度是决定流量平衡算法可实现性的关键参数。在变长分组交换系统中，由于每个i p 分组具有不同的到达时刻及分组长度，一般的流量平衡算法应该对输入端在每个分组到达和离开时更新分组分配方式的设置。这样，t 比特高速路由器中，一般流量平衡算法的配置更新就很难跟上分组到达的速率。而定长信元交换的过程可以用“时隙”来度量，方便了定长信元交换的信元分配方式设置更新。保序( o r d e rk e e p i n g ) p s 。i p 分组在网络中传输的保序问题本来就较难解决。但是，定长信元交换还在路由器中附加了信元的保序问题【2 4 】【2 5 1 。因为重组i p 分组时，必须是所有分段片全部完成内部交换，并且在重组缓存中各就其位。时间复杂度( t i m ec o m p l e x i t y ) 。在高速路由器中，定长信元交换方案把所有长度的i p分组都分段为短的信元，而在交换结构的输出口处，又需把相应的分段片重组为原始的i p 分组( 2 6 】，这显然是个较沉重的负担，会占用较多的时间。处理开销。定长信元交换把长的i p 分组都分为短的信元，导致需要在每个信元头部引入头部信息，由于信元头和填充字节的使用，不可避免地加大了处理开销，降低了交第6 页笪星王堡奎兰堡兰生丝壅换结构的带宽利用率。服务质量的保障( q o sg u a r a n t e e ) 。两种交换方案理论上都可以保障q o s 。但定长信元交换需要在每个信元上都附加上q o s 信息，而变长分组交换所处理的口分组本身就具有q o s 的相关信息。我们简单小结两种结构的优缺点，列于表1 中：表1 变长分组交换与定长信元交换的一般性比较选项变长分组交换足长信兀燹抉通信复杂度非常高较高，或者高保序i p 分组保序i p 分组保序，信元保序时间复杂度低高处理开销低很高q o s 保障可以为直接方式必须为间接方式由于在通信复杂度方面的差距，采用一般算法的高速路由器的所有实现方案中，定长信元交换方案占绝对的统治地位。但是随着器件水平的提高，变长分组交换在复杂度方面的弱势有所改善，在目前器件条件下，找到一种可以实现的变长分组交换结构以及算法的可能性是存在的。与此同时，定长信元交换带来的以下问题也是不容忽视的：1 对变长分组的分段与重组装置，增加了处理开销。2 变长分组切片为定长的信元需要系统提供额外的加速。设一个长度为l 的i p 分组，要分割成几个长度为s 的信元，若l 不是s 的整数倍，则最后一个信元就需要填充( s - r )个字节( 这里r = r e m ( l ，s ) ) ( r e m ( x ) 为对x 取余数) 。并且每个信元还要再加上h 字节的内部地址、控制字段等开销。因此本来需要交换的数据长度为( l m ) 字节，分割为信元后总的数据长度就成为：+ s 一，+ il s 怯。所需要的加速比就为：1 + 幽二! 堕兰：0三+ h基于以上考虑，我们选择变长分组交换方式作为t 比特路由器的交换方案。2 2t 比特路由器的流量平衡2 2 1t 比特路由器交换结构t 比特路由器中基于变长分组的并行交换结构模型如图2 所示：第7 页堕星三翌查兰堡主堂生丝兰z 图2t 比特路由器交换结构t 比特路由器的并行交换结构具有如下特点：流量平衡器( l b d ) ：具有多个速度为线速率的f i f o ，每个f i f o 对应于一个p p s的交换单元( l a y e r ) 。流量平衡器根据流量平衡算法选择f i f o ，把下一个到达的分组放入所选f i f o 中，流量平衡器需按字节数统计平均地把收到的分组分配到各个交换单元。交换单元( l a y e r ) ：交换单元负责完成i p 分组在路由器中的交换。t 比特路由器中的交换矩阵是一种带缓存的c r o s s b a r 结构，简称为b cc r o s s b a r 。这种c r o s s b a r结构与以往c r o s s b a r 结构不同的是：在每个交叉节点上设有缓存，交叉节点的缓存中有一个完整分组时，才将该分组交换输出。交换单元的工作速率为r k ，加速比【2 5 】【3 0 1 为2 。在输出端，对应每个输出端口设置一个输出缓存，并配有输出调度器完成n 个缓存之间的公平调度。合路器( m u l t i p l e x e r ) ：合路器中对应于i p 分组的发送，使用了一种优先级轮循仲第8 页信息t 稃大学硕士学伊论文裁( p r i o r i t y r o t a t i n g a r b i t r a t i o n ) 算法。由于t 比特路由器使用了变长分组交换的方式，因此，合路器中就不再需要完成定长信元交换方式所必须的信元保序【1 4 】和重组缓存程序。当一个i p 分组进入路由器的某个输入端口时，t 比特路由器交换结构处理数据的流程如下：第一步：将分组存储在该输入端口对应的流量平衡器的缓存队列中；第二步：由流量平衡器通过流量平衡算法以负载均衡的原则选择一个合适的交换单元作为目的交换单元；第三步：将分组发送到目的交换单元对应的流量平衡器输出队列缓存中；第四步：将分组由输出队列缓存发送到目的交换单元；第五步：交换单元根据并行轮循调度算法，将分组调度到本单元的输出端；第六步：将分组发送到目的输出端口对应的合路器的缓存中；第七步：合路器将分组送出交换结构，发送到目的输出端口。2 2 2t 比特路由器的流量平衡问题流量平衡是提高并行路由器吞吐率，满足t l l 特路由器超高速率的关键。分组进入并行路由器后，分配给不同的交换单元进行处理。如果能够均匀地分配负载，使所有交换单元保持相近的忙闲程度，那么系统的吞吐率等于各交换单元的吞吐率之和，否则会降低处理的并行度，影响系统的吞吐率。并且，如果能够均匀地分配流量，就可以通过增加中问交换单元的数量而获得任意容量的交换系统。流量平衡算法能够保障并行交换结构的稳定性，而高效的算法则可以显著提高并行交换结构的负载均衡的公平性。在并行交换结构的路由器中，交换系统的流量平衡算法是研究的重点问题。流量平衡能够提高并行交换路由器的性能，但是它可能导致来自同一业务流的分组乱序，从而影响t c p 连接的性能和网络利用率【5 】【“。流量平衡和分组保序是一对矛盾，也是并行路由器设计中需要权衡解决的关键问题。目前，学术界对路由器是否必须保证分组的顺序存在较大分歧。n m c k e o w n ”认为，为了支持分组保序，路由器需要完成大量额外的工作，这会影响路由器的性能。从互联网的分层结构来看，路由器工作在网络层，它只需要快速转发分组，传输层协议( 女h t c p l 8 1 1 9 1 )负责提供分组传输的正确性保证。为了使路由器摆脱分组保序所需的繁琐工作，解决路由器性能提高面临的困难，需要研究新的高效传输层协议，使它既具有容忍分组乱序的功能，又不会对性能造成影响。这类协议将路由器的功能定位在网络层，路由器只需快速转发分组，分组乱序造成的影响由高层协议屏蔽，这将为并行路由器的研制扫清最大的障碍。目前，人们对这个问题展开了第9 页笪星三堡奎主堡主主竺丝苎一些研究1 1o 】i 1 】【1 2 l 【1 3 】，但总体上仍处于研究阶段，还没有具体的实现。由于t l t 特路由器采用了变长分组交换的方式，而业界对路由器中变长分组交换中流量平衡机制的研究还很少。目前t l k 特路由器的流量平衡方案是将基于定长信元交换的信元分配机制直接用于变长分组交换结构中，采用简单轮询的方式分配i p 分组，无法满足交换单元负载均衡的需求，令交换结构震荡明显。因此，根据t l k 特路由器性能改善的迫切需求，本文主要研究了并行交换结构的变长分组流量平衡问题，并对支持业务流保序的流量平衡技术做了一些工作。2 2 3 本文的假设条件并行交换结构满足尽职工作( w o r k - c o n s e r v i n g ) 【l 2 】的条件，并且不会丢包，在并行交换结构的理论分析和设计中我们不考虑冗余度的因素；本文中只对同构交换结构【1 4 】进行研究；本文的交换单元均采用共享缓存的c r o s s b a r 结构；本文研究的并行交换结构的每个输入输出端口的调度判决都是独立执行的，各个端口之间无相互通信；本文研究的是带缓存p p s 结构【4 l 【t e l l ”1 ，因为无缓存p p s 结构1 1 1 2 1 3 3 1 只是带缓存p p s 结构的特例( 缓存大小为0 的情况) ；本文研究的是采用变长分组交换的两级式并行交换结构。2 3 流量平衡模型本节将流量平衡机制根据其运行的独立性分为后继无关流量平衡和后继相关流量平衡两种模型：后继无关流量平衡。如果各个输入端口的流量平衡器与并行交换单元之间独立运行，流量平衡器无需获取交换单元负载状态时，本文称这种流量平衡机制称为后继无关流量平衡，如图3 所示。后继相关流量平衡。如果流量平衡器需要通过交换单元的负载状态来进行分组分配判决，那么该流量平衡机制为后继相关流量平衡，如图4 所示。第1 0 页信息t 稃大学硕+ 学位论文图3 后继无关流量平衡结构图4 后继相关流量平衡结构两种流量平衡结构都由以下四部分组成：输入缓存、交换缓存、分配判决器、负载状态表。而且前三项组成部分是相同的：输入缓存：用于存放由输入端口到达流量平衡器的i p 分组( 或信元) ；交换缓存：用于存放流量平衡器发往各个交换单元的i p 分组( 或信元) ；分配判决器：采用某种流量平衡算法根据负载状态表判断分组( 或信元) 的目的交换单元。两种流量平衡结构的区别在于其负载状态表的生成方式。后继无关流量平衡结构的负载状态表由各个交换缓存此时的负载状态信息组成；而后继相关流量平衡结构的负载状态表由后续交换单元此时的负载状态信息生成。第1 l 页信息t 稃大学硕十学仲论文2 4 流量平衡的性能指标为了分析流量平衡算法的性能，我们首先定义两个度量标准：公平指数( 度量流量平衡的公平性) 和运算量( 度量流量平衡算法的复杂度) 。这两个度量标准不仅适用于本文提出的流量平衡算法，而且也适用于其他流量平衡机制。2 4 1 性能评估模型并行交换结构由流量平衡器与多个交换单元组成。在此系统中，流量平衡器接收数据并将其转发给相应的交换单元处理。一个好的流量平衡系统应该将路由器中的流量均匀地或者按照预定义的比例进行分配。为了分析公平指数和运算量，我们假设如下路由器模型：设有n 个输入端口，k 个并行交换单元。假设路由器从时刻0 开始收到各个用户发送的数据，设d 。，为n t 时第k 个交换单元接收到的总字节数，既时间段t 内交换单元k 的负载量；d 为n t 时所有k 个交换单元接收的总字节数，既整个交换结构在时间段t 内的负载量。表示交换单元k 的处理能力。理想n，的系统应在任何时间t 内应满足：三；生= 竺，即流量分配与交换单元的处理能力成正比。u i |r t图5 流量平衡性能评估模型2 4 2 性能指标定义定义2 1 流量比：第k 个交换单元实际获得的流量比为l s k = l i m , _ 。鲁( 式1 )定义2 2 理想流量比：用r k 表示第k 个交换单元的处理速度，则第k 个交换单元得到的理想流量比( 应得份额) 为皿= ；l( 式2 )第1 2 页笪垦三堡奎兰堡兰生笙茎最后，我们用第k 个交换单元实际获得的流量份额与应得份额之比表示流量平衡算法对流量的分配比例偏离理想值的情况，称之为公平指数。定义2 3 公平指数( f a i r n e s s l n d e x 。) ：采用一种流量平衡算法时，第k 个交换单元的公平指数定义为rr ql s i of a i r n e s s l n d e x t2 嚣2 _ ( 式3 )j l s 。九a3j对于并行交换结构来说，每个交换单元都有一个公平指数，其值的大小反应了目前该交换单元所分配的流量与理想流量的偏离程度。f a i r n e s s l n d e x 。的理想值为l ，此时流量平衡算法对流量的分配完全按照理想流量比进行。f a i r n e s s l n d e x k 1 时，表示流量平衡算法给交换单元k 分配的流量多于理想流量，f a i r n e s s l n d e x 。值越大，表示该交换单元的实际负载正向偏离理想负载值越远。我们设计一个流量平衡算法的理想目标是使一个交换结构中所有的交换单元的f a i r n e s s l n d e x 值都为1 。定义2 4 运算量：运算量为将一个分组从输入端口分配到交换单元的时间复杂度的最大值，时间复杂度是处理一个分组需要的操作周期数。即流量平衡器发送一个分组需要的最大运算次数。2 5 基本流量平衡算法分析自从并行交换结构提出以来，流量平衡算法一直是人们研究的重点。本节将重点研究两类最基本的流量平衡算法：轮询式算法、最短队列式算法。2 5 1 轮询式流量平衡算法轮询算法( r o u n d r o b i n ) 是所有流量平衡算法中最简单也最容易实现的一种方法。轮询法简单地在交换结构中顺序轮转选择交换单元。在负载平衡环境中，流量平衡器将新到达的分组轮流发给交换结构中的下一交换单元，如此连续、周而复始，每个交换单元都被轮流选择。轮询算法在已有的交换结构中被广泛使用。轮询算法的活动是可预知的，每个交换单元被选择的机会是1 k ，因此很容易计算出交换单元的负载分布。2 5 1 1 算法描述在输入端，流量平衡器通过采用轮询分配的方式实现负载均衡分配。流量平衡器的缓存结构如图6 所示。每个流量平衡器中设置k 个深度相同的f i f 0 ，f i f o第1 3 页笪：垦三堡查兰堡主堂生笙茎队列q ( i ，k ) 中存储了输入端e i q ，去往交换单元k 的所有分组，其中k 【1 , 2 k 】。算法思想如下：当一个分组到达时，流量平衡器按照轮询的原则选择一个交换单元作为该分组的目的交换单元；然后将该分组发送到目的交换单元所对应的f i f o 队歹l j q ( i ，k ) 中排队等待发送；当由输入端e l i 至l j 交换单元k 的链路空闲时，流量平衡器把q ( i ，k ) 队列头部的第一个分组发送到交换单元k 中。我们将q ( i ，k ) 队列的最长长度作为f i f o 深度。假设每个f i f o 的深度都为d ，则整个缓存的大小为k d 。对任一输入端口的流量平衡器而言，分组依次在q ( i ，k ) ( k e 【1 , 2 k 】) 中按照轮转方式( r o u n d r o b i n ) 分发。图6 轮询式流量平衡缓存结构图下面我们用类c 语言来描述轮询算法如下：轮询信元分配算法：，函数定义：r e c e i v e ( )r e c e i v eac e l l ；f i f o ( f n k ) i n d i c a t e sf n k 】u n u s e df i f o ；q u e u e ( c e l l ，b u f f e r )q u e u e sc e l l ；变量定义：kd e s t i n a t i o nu n i tn u m b e ri n d e x ；l m 】f i f ou s e dn u m b e r ；f i n 】n u m b e ro f u n u s e df i f o ；，p n 【】s e l e c t e df i f on u m b e r ；l o a d _ b a l a n c i n g ( )第1 4 页信息t 稃大学硕士学位论文w h i l e ( t r u e )c e l l = r e c e i v e ( ) ；m 【k 】抖；f n k = k t i n k k 】；i f p n k = k ：t h e np n k 2 1 ：e l s ep n k = p n 【k 】+ 1 ；q u e u e ( c e l l ，b u f f e r p n k ) ；)流量平衡器需要进行以下工作：第一步：查询本轮未用交换单元集合；第二步：如果集合为空，则选择第一个交换单元对应的f i f o 作为发送对象；如果集合非空，选择k 值最小的交换单元对应的f i f o 作为发送对象；第三步：将分组分配到所选f i f o 的队尾进行排队，稍后发送到交换单元k ；第四步：更新未用交换单元集合，若k k ，仅将交换单元k 从未用单元集合中删除，若k k ，表示一轮分组分配结束，将所有交换单元重新纳入未用交换单元集合中。2 5 1 2 算法分析首先我们分析将轮询算法应用在定长信元交换系统中的性能：在定长信元交换结构中，该算法可以实现流量平衡器和合路器独立工作，避免了交换结构内部的实时通信。每一个流量平衡器独立维护本轮未用交换单元的集合，按照轮询分配的方式选择交换单元k ，因此流量平衡器能够独立工作。在定长信元交换系统中，流量平衡器通过设冒缓存能够解决信元失序问题。该算法没有统一的中央调度单元，由流量平衡器按照轮询分配的方式独立地实现负载分配，因此算法虽然能够实现负载平衡，但不能避免信元集中现象的发生。基本的轮询算法典型的适用于交换结构中所有交换单元的处理能力和性能均相同的情况。在实际应用中，一般将它与其他简单方法联合使用比较有效。比如加权轮询算法，加权轮询算法根据交换单元优先级或当前的负载状况( 即权值) 来构成流量平衡的多优先级队列，队列中的每个交换单元都具有相同处理等级，这样在同一个队列里可以按照前面的轮询法进行均衡，而队列之间按照优先级的先后顺序进行平衡处理。在这里权值是基于交换单元能力或负载状况的一个估计值。下面我们分析轮询算法在变长分组交换结构中的公平性：假设各个交换单元的处理能力相同，则根据式2 得皿= i k 。设d f 。为第一轮到第，第1 5 页信息1 = 稃大学硕十学位论文轮交换单元k 收