（通信与信息系统专业论文）10g线路输出接口大容量缓冲机制研究.pdf

中文摘要 网络规模和通信量的日益膨胀，使得1 0 g 速率的线路接口成为未来路由器的主要接口 类型；此外网络业务呈现出多样化趋势，不同特性的业务对缓冲容量有着不同的要求，尤 其是一些热点业务需要大容量缓冲进行支持；同时多样化的业务也使得路由器必须为不同 特性的业务提供区分的服务质量( q o s ) 保障。因此需要在t 比特路由器中设置高速大容 量缓冲来应对这些需求。 本文主要研究t 比特路由器1 0 g 线路输出接口大容量缓冲机制的设计实现方案，分别 从缓冲结构设计、缓冲队列管理机制和缓冲调度机制三个方面对高速大容量缓冲机制进行 了系统的研究和分析，给出了1 0 g 线路输出接口大容量缓冲机制的设计方案，并通过硬件 电路实现。 本文的贡献主要包括以下几点： 从理论上证明了并行分布式缓冲结构( p a r a l l e ld i s t r i b u t e db u f f e ra r c h i t e c t u r e ， p d b a ) 稳定工作的条件；并对p d b a 子层缓冲器的速率和容量设置进行了解析分析。 给出了一种新的队列拥塞控制机制区分服务的随机早期探测机制( d i f f e r e n t s e r v i c er a n d o m e a r l yd e t e c t i o n , d s r e d ) 。与其它队列管理机制相比，d s r e d 在拥塞避免 阶段能始终保证不同类型的业务具有不同的丢包率，从而为不同业务提供了区分的服务质 量。 给出了一种平滑输出的加权差额轮询调度算法( s m o o t ho u t p u tw e i g h t e dd e f i c i t r o u n dr o b i n s o w d r r ) 。s o w d r r 算法通过引入差额机制和公平插入机制，解决了由 于分组变长和各个队列权值不同引起的调度不公平性，改善了调度的时延特性，平滑了输 出端的突发强度，减轻了对下一跳路由节点的缓冲压力，并且实现简单。理论分析和仿真试 验均证明s o w d r r 算法可以获得良好的性能。 针对网络业务不同程度的服务质量需求，进一步给出了区分服务的平滑输出加权差 额轮询调度算法( d i f f e r e n ts e r v i c es m o o t ho u t p u tw e i g h t e dd e f i c i tr o u n dr o b i n , d s s o w d r r ) 。d s s o w d r r 算法即继承了s o w d r r 算法的优点，又能为实时业务和 非实时业务提供区分的服务质量，满足了t 比特路由器的性能要求。 给出了1 0 g 接口缓冲模块的总体设计方案，并给出了d s r e d 算法和d s s o w d r r 算法的工程设计方案和具体实现框图，通过硬件电路实现了1 0 g 线路输出接口大容量缓冲 模块。在此基础上，通过整机测试方案对1 0 g 线路输出接口大容量缓冲模块进行了测试， 测试结果表明该缓冲模块完全满足t 比特路由器的功能和性能要求。 关键词：t 比特路由器；缓冲机制；缓冲结构；队列管理：调度 第l 页 a b s t r a c t a l o n g w i t ht h ee x p l o s i v ee x p a n s i o no ft h et r a f f i cc a r r i e db yt h ei n t e m e ta n dr a p i dg r o w t ho f t h en e t w o r ks c a l e ，t h e1 0 g - i n t e r f a c eo f t h er o u t e rw i l lb e c o m eo n eo f t h em a i ni n t e r f a c et y p e si n t h ef u t u r e i na d d i t i o nt h eb u s i n e s si nt h en e t w o r kp r e s e n t st h et e n d e n c yo ft h ed i v e r s i f i c a t i o n t h ev a r i o u sb u s i n e s s e sh a v et h ed i f f e r e n tr e q u i r e m e n ti nt h eb u f f e rc a p a c i t y , a n ds o m eh o ts p o t b u s i n e s sp a r t i c u l a r l yn e e d st h el a r g ec a p a c i t yb u f f e rt oc a r r y a tt h es 锄et i m et h ed i v e r s e b u s i n e s sa l s on e e d sd i f f e r e n tq u a l i t yo fs e r v i c e ( q o s ) t h e r e f o r ei ti sn e e d e dt os e tt h eh i g h s p e e da n dl a r g ec a p a c i t yb u f f e ri nt h et b i tr o u t e r t om e e tt h e s ed e m a n d s t h i sp a p e rm a i n l ys t u d i e dt h ed e s i g ni m p l e m e n t a t i o np l a no ft h el a r g ec a p a c i t yb u f f e r m e c h a n i s mb a s e do nt h e1 0 g i n t e r f a c ew h i c hw a sl o c a t e di nt h eo u t p u tp o r t so f t h etb i tr o u t e r , t h eh i 曲s p e e dl a r g ec a p a c i t yb u f f e rm e c h a n i s mw a ss y s t e m l yr e s e a r c h e da n da n a l y e df r o mt h e d e s i g no ft h eb u f f e rs t r u c t u r e ，t h em a n a g e dm e c h a n i s mo ft h eq u e u ea n dt h es c h e d u l e d m e c h a n i s mo f t h eq u e u e t h ed e s i g np l a no f t h el a r g ec a p a c i t yb u f f e rb a s e do nt h e1 0 0i n t e r f a c e w h i c hw a sl o c a t e di nt h eo u t p u tp o r t so ft h etb i tr o u t e rw a sp r o p o s e d ，a n dw a si m p l e m e n t e d t h r o u g hh a r d w a r ee l e c t r i cc i r c u i t t h i sp a p e r sc o n t r i b u t i o nm a i n l yi n c l u d e dt h ef o l l o w i n gs e v e r a lp o i n t s ： t h es t e a d yw o r kc o n d i t i o no ft h ep a r a l l e ld i s t r i b u t e db u f f e ra r c h i t e c t u r e ( p d b mh a s p r o v e di nt h e o r y a n dt h ef o r m u l a ew e r eo b t a i n e da b o u tt h es p e e da n dt h ea p a c i t yo f t h ep d b a s u b l e v e lb u f f e r p r o p o s e do n ek i n do f t h en e wq u e u ec o n g e s t i o nc o n t r o lm e c h a n i s m d i f f e r e n ts e r v i c ei n t h er a n d o me a r l yd e t e c t i o n ( d s r e d ) c o m p a r e dt oo t h e r s ，t h ed s r e dw a sa b l et og u a r a n t e e d i f f e r e n tl o s sr a t ef o rt h ev a r i o u s b u s i n e s si nt h ee v e r yp h a s eo f t h ec o n g e s t i o na v o i d t h e r e f o r e , t h ed s r e dw a sa b l et os u p p o r td i f f e r e n ts e r v i c ef o rt h ev a r i o u sb u s i n e s s e s p r o p o s e do n ek i n do ft h en e ws c h e d u l e da l g o r i t h m s m o o t ho u t p u tw e i g h t e dd e f i c i t r o u n dr o b i n ( s o w d r r ) t h r o u g ht h ei n t r o d u c t i o no ft h ed e f i c i ta n df a i ri n s e r t i o nm e c h a n i s m ， t h es o w d r ra l g o r i t h mh a ss o l v e du n f a i m e s s e sw h i c hw e r ee a s e db e c a u s eo ft h ev a r i o u s l e n g t ho f t h ei pp a c k e t sa n dt h ed i f f e r e n tw e i g h tv a l u ei nt h ed i f f e r e n tq u e u e ，i m p r o v e d t h ed e l a y , s m o o t h e dt h eo u t b u r s ti n t e n s i t y , r e d u e e dt l l eb u f f e rp r e s s u r eo ft h en e x tm u t e r t h es o w d r r a l g o r i t h mw a sa l s op r o v e dt om a yo b t a i nt h eg o o dp e r f o r m a n c et h r o u g ht h et h e o r e t i c a la n a l y s i s a n dt h es i m u l a t i o ne x p e r i m e n t b e c a u s eo f t h ed i f f e r e n tn e e d sf o rt h ev a r i o u sb u s i n e s s e si nt h eq o s f u r t h e rp r o p o s e dt h e s c h e d u l e da l g o r i t h m - d i f f e r e n ts e r v i c ei nt h es o - w d r ra l g o r i t h m ( d s s o - w d r r ) b e s i d e s i n h e r i t e dt h es o w d r ra l g o r i t h mm e r i t ，t h i sa l g o r i t h mw a sa b l et os u p p o r tt h ed i f f e r e n tq o s 第页 f o rt h er e a l t i m ea n dn o n r e a l - t i m eb u s i n e s sa n ds a t i s f yt h ep e r f o r m a n c er e q u i r e m e n to ft h etb i t r o u t e r p r o p o s e dt h ed e s i g np l a no f t h eb u f f e rm o d u l eb a s e do nt h e1 0 go u t p u ti n t e r f a c eo f t h et b i tr o u t e r , a n dp r o d u c e dt h ee n g i n e e r i n gd e s i g np l a na n dt h es p e c i f i ci m p l e m e n t a t i o nd i a g r a mf o r t h ed s r e da l g o r i t h ma n dt h ed s s o w d r ra l g o r i t h m t h eb u f f e rm o d u l eh a si m p l e m e n t e d t h r o u g ht h eh a r d w a r ee l e c t r i cc k c m t i nt h i sf o u n d a t i o n ，t h ei m p l e m e n t e db u f f e rm o d u l ew a s t e s t e dt h r o u g ht h et e s tp l a no f t h ee n t i r er o u t e r a n dt h er e s u l th a di n d i c a t e dt h a tt h ei m p l e m e n t e d b u f f e rm o d u l ec o m p l e t e l ys a t i s f i e dt h ef u n c t i o na n dt h ep e r f o r m a n c er e q u i r e m e n to ft h etb i t r o u t e r k e yw o r d s ：tb i tr o u t e r ：b u f f e rm e c h a n i s m = b u f f e ra r c h i t e c t u r e ；m a n a g e m e n to ft h e q u e u e = s c h e d u l e 第1 1 i 页 信息工程大学硕士学位论文 表目录 表格1p f q 算法性能比较。”。2 5 表格2 输入数据指示位说明4 6 表格3 各种包在不同长度下的丢包率。5 3 表格4 各种包在不同长度下的平均延迟5 4 信息工程大学硕士学位论文 图目录 图l 单一缓冲结构7 图2s r a m 和d r a m 相结合的缓冲结构8 图3 并行分布式缓冲结构p d b a 9 图4 拥塞状态下三种队列管理策略的丢包方式。1 6 图5d s r e d 示意图1 9 图6 输出排队调度模型2 2 图7w r r 算法( a - f 的权值分别为2 ：2 ：1 ：2 ：1 ：2 ) 2 3 图8d d r 工作原理2 8 图9s o - w d r r 算法的逻辑框图3 2 图1 0w d r r 算法与s o - - w d r r 算法下各队列的平均时延3 6 图l ld s s o w d r r 算法原理( 设队列o 为实时队列) 3 7 图1 2s o w d r r 算法与d s s o w d r r 算法下各队列的平均时延3 9 图1 3 大容量缓冲模块在系统中的位置( 黄色部分) 4 2 图1 4 单一缓冲结构4 3 图1 5 两层的p d b a 结构4 3 图1 6 缓冲模块的逻辑结构与子模块划分4 5 图1 7d s r e d 工程实现方案4 8 图1 8d s s o - w d r r 输出示意图4 9 图1 9d s s o - w d r r 算法实现框图5 0 图2 0 合路与分路模块实现图5 1 图2 1 运行流程示意图与系统逻辑流程图5 2 图2 2 整机测试连接图5 3 图2 3 各种包在不同长度下的丢包率与平均延迟5 4 图2 4 缓冲模块硬件实物图5 4 独创性声明 所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中标注和致谢的相关内容外，论文中不包含其他个人或集体已经公开的研究成 果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文题目：! q q 线路箍出攮旦太空量缓独扭剑堡究 学位论文作者签名： 扬尘波鑫五当谈= 日期：2 0 0 64 月2 0 日 学位论文版权使用授权书 本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 涉密学位论文在解密后适用本授权书。) 学位论文题目：! q 鱼线路捡出撞旦盔奎量缓独扭制研究 学位论文作者签名： 作者指导教师签名： 日期：2 0 0 6 年4 月2 0 日 日期：加彳年6 月彩日 信息工程大学硕士学位论文 第一章绪论 路由器是一种典型的网络层设备。它通常用于连接多个逻辑上分开的网络，并为经过 的数据选择最佳的传输路径。 近年来，我国通信与网络产业发展迅速，但是在核心网络技术发展上仍然滞后。在核 心路由器技术取得重大突破的基础上，为抢占下一代网络技术的制高点，实现我国网络技 术的跨越式发展，对未来通信和网络产业实行战略性布局，为此科技部发布了国家“十 五”8 6 3 计划信息技术领域高性能宽带信息网专项的重大项目“可扩展到t 比特的高性能 i p v 4 ，i p v 6 路由器基础平台及实验系统”，研制t 比特路由器作为中国高性能宽带信息网运 营的关键设备。本文主要研究t 比特路由器中1 0 g 线路输出接口大容量缓冲机制的若干关 键技术。 1 1 课题研究背景 目前，我国骨干网上主要是2 5 g b p s 的链路，但是在网络用户数量的急剧膨胀和用户 业务多样化需求的强劲推动下，同时随着网络处理技术和光传输技术的不断成熟，1 0 g 速 率的链路必将会很快取代当今的2 5 g 链路，甚至1 0 g 的链路将会被用于边缘接入网中。 因此在t 比特路由器中，1 0 g 速率的链路接口将是主要的接口形式。 另一方面，用户业务呈现多样化趋势，除了传统的数据业务外，远程教育、远程实时 医疗、v o i p 、 c o d 、i p t v 等实时业务也主要由i p 网络来承载。多种多样的业务各具有不 同的业务特性，某些业务( 如i p t v 等并发流媒体) 对缓冲器容量有很高的要求。例如， 在t 比特路由器中，由于i p 业务的非均匀性，t 比特路由器需要支持众多线路接口要求同 一输出端口的突发热点业务。并发流媒体业务不仅增大了突发热点业务的出现频度，而且 流媒体业务较长的持续时间大大提高了突发热点业务的突发长度。可见并发流媒体业务会 使得基于输出端口的突发热点业务的突发度大幅度提高，因此在t 比特路由器中输出端口 必须设置大容量缓冲区对突发热点业务进行平滑0 1 。此外，网络业务多样性的要求，需要 网络为不同业务提供不同的服务质量保证。从网络运营的需求上，也需要为不同的用户提 供区分的服务质量。 由上所述，在t 比特路由器中需要支持1 0 g 速率的高速数据接口，并提供对非实时业 务、实时业务、混合业务的支持。这些要求，现有的缓冲机制几乎不可能实现。因此，研 究高速大容量缓冲机制是高速核心路由器技术中的重要组成部分，对t 比特路由器样机的 研制也具有重要的现实意义。 1 2 课题的研究任务 第1 页 信息工程大学硕士学位论文 本课题的主要任务是对1 0 g 线路输出接口的大容量缓冲机制进行研究。现有的单一缓 冲机制在读写访问速率和容量设置上是一对矛盾：读写速率高的缓冲机制，可设置的缓冲 器容量小；设置缓冲容量大的缓冲机制，读写速率低，无法同时满足高速率和大容量的要 求。而s r a m 和d r a m 相结合的缓冲机制，虽然能兼顾高速率和大容量的要求，但是它 只支持定长数据缓冲，并且控制逻辑复杂，可扩展性差，不能对缓冲进行平滑的升级。而 并行分布式缓冲不仅能同时提供高速率和大容量的要求，并且能缓冲变长数据，各层的控 制逻辑也可以复用，可扩展性良好。因此研究并行分布式缓冲机制具有重要的意义。 并行分布式缓冲机制还需要对缓冲队列进行管理，以满足多样化业务的区分服务质量 要求。缓冲队列管理主要有两部分内容，其一是缓冲队列管理机制管理着数据是进入 缓冲队列，还是丢弃，以怎样的策略进行丢弃的机制；其二是缓冲调度机制决定着缓 冲器中数据以怎样的顺序进行输出，如何为各个队列分配输出带宽。 1 3 本文的主要工作 本文研究的总体目标是：结合“十五”8 6 3 计划重大专项课题“可扩展到t 比特的高性能 i p v 4 i p v 6 路由器基础平台及实验系统”的研发，分析和研究基于1 0 g 线路输出接口的大容 量缓冲机制。高速大容量缓冲机制主要包括1 ) 缓冲总体结构的设计和缓冲性能的分析；2 ) 缓冲队列管理机制，管理着数据是进入缓冲器还是丢弃的策略；3 ) 缓冲调度机制，决定 着缓冲器中数据输出的先后顺序和输出带宽的分配；4 ) 数据在缓冲器中的组织形式。在 路由器中数据常常组织为f i f o 形式，本文就假设数据在缓冲器中组织为多队列f i f o 的形 式。 高速大容量缓冲机制的内在逻辑是：缓冲总体结构是高速大容量缓冲机制的重要组成 部分，它决定了缓冲机制的总体性能，包括缓冲器的访问速率、容量以及数据的缓冲时延 等；缓冲队列管理机制和缓冲调度机制也是高速大容量缓冲机制的重要组成部分， 缓冲 队列管理机制运行在缓冲器的入口，管理着数据是进入缓冲器还是丢弃，以什么策略丢弃； 缓冲调度机制运行在缓冲器的出口，决定着缓冲器中数据输出的先后顺序和输出带宽的分 配；数据组织形式是指数据在缓冲器中的逻辑结构。 本文研究了高速大容量缓冲机制的各个部分，主要工作概括如下： 针对1 0 g 线路输出接口缓冲机制的高速和大容量需求，在分析现有缓冲机制的基础 上，从理论上证明了并行分布式缓冲结构( p a r a l l e ld i s t r i b u t e db u f f e r a r c h i t e c t u r e ，p d b a ) 稳定工作的条件；并对p d b a 予层缓冲器的速率和容量进行了解析分析。为t 比特路由 器中1 0 g 线路输出接口大容量缓冲器的设计提供了理论依据。 面对不同用户和业务的不同服务质量需求，在分析现有缓冲队列管理算法的基础 上，给出了一种新的队列管理机制区分服务的随机早期探测机制( d i f f e r e n ts e r v i c e r a n d o me a r l yd e t e c t i o n , d s r e d ) 。与其它队列管理机制相比，d s r e d 在拥塞避免阶段能 第2 页 信息工程大学硕士学位论文 始终保证不同类型的业务具有不同的丢包率，从而为不同业务提供了区分的服务质量，满 足了网络业务不同程度的服务质量需要。 在分析了现有缓冲调度算法的基础上，针对现有加权差额轮询调度算法( w e i g h t e d d e f i c i tr o u n dr o b i n ，w d r r ) 时延特性差、输出突发性大的缺点，给出了平滑输出的加权 差额轮询调度算法( s m o o t ho u t p u tw e i g h t e dd e f i c i tr o u n dr o b i n ，s o w d r r ) 。s o w d r r 算法通过引入差额机制和公平插入机制，解决了由于分组变长和各个队列权值不同引起的 调度不公平性，改善了调度的时延特性，平滑了输出端的突发强度，减轻了对下一跳路由 节点的缓冲压力，并且实现简单。理论分析和仿真试验均证明s o w d r r 算法可以获得良好 的性能。 针对网络业务不同程度的服务质量需求，进一步对s o w d r r 算法的时延特性进行 改进，给出了区分服务的平滑输出加权差额轮询调度算法( d i f f e r e n ts e r v i c es m o o t ho u t p u t w e i g h t e dd e f i c i tr o u n dr o b i n d s s 0 w d r r ) 。d s s o w d r r 算法即继承了s o w d r r 算 法调度公平，时延特性好，输出平滑，实现简单的优点，又能为实时业务和非实时业务提 供区分的服务质量，满足了t 比特路由器的性能要求。 给出了1 0 g 接口缓冲模块的总体设计方案，并给出了d s r e d 算法和d s s o - w d r r 算法的工程设计方案和具体实现框图，通过硬件电路实现了1 0 g 线路输出接口大容量缓冲 模块。在此基础上，通过整机测试方案对1 0 g 线路输出接口大容量缓冲模块进行了测试， 测试结果表明该缓冲模块完全满足t 比特路由器的功能和性能要求。 1 4 本文的结构安捧 本文剩余部分安排如下： 第二章从传统缓冲器面临的挑战入手，针对当今电子系统对高速大容量缓冲器的需 要，对现存的高速大容量缓冲结构进行了分析。然后对并行分布式缓冲结构的稳定工作条 件、读写访问速率以及容量要求进行了理论推导和解析分析，使其在稳定工作条件下能完 全等效一个单一的缓冲器。 第三章从网络拥塞的原因出发，重点讨论了网络节点上的网络拥塞控制机制一一队 列管理策略。在对现存的队列管理策略进行比较分析的基础上，给出了区分服务的随机早 期探测机制( d s r e d ) 。最后还对缓冲队列容量的设定进行了讨论。 第四章在分析现有调度算法的基础上，对差额轮询调度算法( d r r ) 进行了详细讨论， 针对它时延特性差，输出突发性大的缺点，通过引入差额机制和公平插入机制，给出了平 滑输出的加权差额轮询调度算法( s o w d r r ) 。针对网络业务多样化的需要，进一步对 s o w d r r 的时延特性进行改进，给出了区分服务的平滑输出加权差额轮询调度算法 ( d s s o w d i 汛) 。并通过理论计算和仿真试验验证了s o w d r r 和d s s o w d r r 的优良 性能。 第3 页 信息工程大学硕士学付论文 第五章给出了1 0 g 接口缓冲模块的总体设计方案，并给出了d s r e d 算法和 d s s o w d r r 算法的工程设计方案和具体实现框图，通过硬件电路实现了1 0 g 线路输出接 口大容量缓冲模块。在此基础上；给出了整机测试方案和测试结果。 最后是结束语，对全文进行总结，指出目前在研究中还存在的一些问题和不足，并给 出下一步可能的研究课题和相应的一些设想。 第4 页 信息工程大学硕士学伊论文 2 1 引言 第二章高速并行分布式缓冲机制的解析分析 缓冲不仅能够提高带宽的利用率，并且结合缓冲器可以实现对数据的丢包率进行控 制，也可以对输出带宽进行分配。当今，网络的发展要求对不同的业务提供不同的服务质 量( q o s ) ，因此缓冲的作用越发显得重要。另外，随着网络的快速发展，对网络节点的实 现提出了越来越高的要求，缓冲也面临着高速、大容量的挑战。研究高速大容量缓冲机制 对高速网络节点的实现有着重要的意义。( 说明：除明确指出外，本文对缓存、缓冲器， 包、分组、报文，缓冲队列管理、队列管理，缓冲调度、缓冲队列调度、调度等概念不做 区分) 随着网络的发展，网络业务呈现多样性。不同业务对网络有着不同的服务质量要求， 还有链路速率的快速提高，这些都为传统的缓冲机制提出了挑战。具体表现有如下几个方 面： 1 商用缓冲器的读写访问速率跟不上链路速率提高的要求，成为了高速网络节点实现 中的一个瓶颈。 由摩尔定律和超摩尔定律可知，设备处理速度的增长远远跟不上链路带宽的增长。随 着传输技术的飞速发展，路由器尤其是核心路由器的线路接口速率越来越高。当高速路由 器的端口速率大于o c l 9 2 ( 1 0 g b s ) 达到o c 7 6 8 ( 4 0 g b s ) 甚至o c 3 0 7 2 ( 1 6 0 g b s ) 时， 路由器几乎不可能对分组包进行缓冲“3 。因此必需研究高速缓冲机制，降低对缓冲器访问 速率的要求。 2 i 商用缓冲器的容量和成本之问的矛盾，使得采用单一大容量缓冲器几乎不可能。 随着网络业务呈现多样化，不同的业务有着不同的特性，某些业务( 如并发流媒体) 对缓冲器容量有很高的要求。例如，在t 比特路由器中，由于i p 业务的非均匀性，t 比特 路由器需要支持众多线路接口要求同一输出端口的突发热点业务。并发流媒体业务不仅增 大了突发热点业务的出现频度，而且流媒体业务较长的持续时间大大提高了突发热点业务 的突发长度。可见并发流媒体业务会使得基于输出端口的突发热点业务的突发度大幅度提 高，因此在t 比特路由器中输出端口必须设置大容量缓冲区对突发热点业务进行平滑【2 】。 另一方面，商用缓冲器容量和成本并不是线性的，容量越大成本越高，缓冲器的性价 比越低。面对当今业务需要的缓冲器容量要求，采用单一的缓冲结构几乎不可能。 本章通过对现存的缓冲结构进行分析，采用并行化分布式技术，试图在性能满足的前 提下，使用几个小容量缓冲器来等效一个大容量缓冲器，同时降低对缓冲器的访问速率要 求，以及探讨这种等效的约束条件。 第5 页 信息工程大学硕士学位论文 本文分析中的假设如下t 1 研究对象主要是单网络节点交换结构输出端缓冲，交换结构采用c i o q 排队 机制，根据c i o q 的理论，要求交换结构加速2 - 1 n 倍。1 。本文采用2 倍加速， 即缓冲器的输入速率是输出速率的2 倍； 2 路由器具有前端包分类功能； 3 缓冲器中数据组织为多队列f i f o 的形式。 本文中所用到的符号约定如下： r 链路速率，也即缓冲器输出速率，单位：b p s 矿 缓冲器的容量，单位：b i t 后并行分布式缓冲结构中的层数，单位：层 ， 并行分布式缓冲结构中子层缓冲器的输出速率，单位：b p s d 总线带宽，单位：b i t r x l 表示对x 向上取整 且丁丁环回时间，单位：m s ，典型t c p 连接的r t t = 2 5 0 m s 4 在时间域以f ，内分配到第盘层的业务量 a 渺在时间域以f ，内分配到各个子层的总业务量 在t 时y t j p d b a 结构中第七层缓冲器的排队长度 q 在f 时刻参考结构中缓冲器的排队长度 2 2 对现有缓冲结构的分析 当前的缓冲结构主要有两种：单一缓冲结构( 见图1 ) 、s r a m 和d r a m 相结合的缓 冲结构( 见图2 ) 。单一缓冲结构使用物理上一个单一的商用缓冲器对数据进行缓冲，它的 优点主要是控制逻辑简单，可以缓冲变长数据，数据在缓冲器中的时延性能确定，不需要 额外的数据读写算法；缺点是成本太高，受商用缓冲器访问速率和容量的限制，可扩展性 差。s r a m 和d r a m 相结合的缓冲结构，是通过s r a m 和d r a m 相结合，降低了对高成 本的s r a m 的容量要求，从总体上提高了系统的性价比。它的优点主要是系统性价比提高， 可以满足高速和大容量缓冲的需要：缺点主要是需要复杂的缓冲器管理算法，只支持定长 数据的读写，并且有较大的访问延迟。下面两小节将就这两种结构进行详细的分析。 2 2 1 单一缓冲结构 单一缓冲结构如图l 所示，当链路速率为r 时，线速处理的系统要求它的最小输出速 率为r ，根据c i c q 的理论，它的最小输入速率为( 2 1 n ) r ，我们的系统为2 r 。如果总 第6 页 信息工程大学硕士学位论文 线宽度为d 时，写访润一次的周期为d d 2 r ，例如当总线宽度为6 4 b i t ，链路速率为2 。s o b r , s 时。需要达到的读写周期为1 2 8 n s ，而当链路速率达到1 0 g b p s 时，需要的读写周期则为 3 2 n s 。对于前者当时钟频率为1 0 0 m h z 时，采用单速率s r a m 可以基本满足，对于后者 则显然无法满足。因此，高速路由器对报文缓冲器的存取速度提出了较高的要求。 缓冲器 图l 单一缓冲结构 另终，由于输入i p 业务模型的不确定性，无法对大容量高速缓冲所需要的容量进行 精确分析，当连接环回时间为r t t 时。粗略的可以认为需要的最小缓冲容量为r r t t 。 根据文献【3 】就t c p 连接的环回时间( r t r ) 为例，高速路由器缓冲时间选为2 5 0 m s ，所以 在1 0 g 的线路接口上要求设计的高速缓冲的容量大于2 5 g 比特。 由上所述单一缓冲结构的性能指标如下： 输入速率2 r 输出速率r 缓冲容量v = r r t t 通过典型值的计算，知道单一缓冲要求的读写访问速率和容量要求对当今的商用缓冲 器是个挑战。这种结构的读写访问速率和缓冲容量与链路速率有关，当链路速率进一步提 高时，就需要对整个缓冲系统进行升级，为增加系统的缓冲性能需要付出高昂的代价，可 扩展性很差。 2 2 2s r a m 和d r a m 相结合的缓冲结构 s r a m 和d r a m 相结合的缓冲结构如图2 所示。它是由s u n d a ri y e r 和n i c km c k e o w n 等在文献【4 】中提出的。该方案的思想是通过一次并行读取b 个信元( 定长分组) 来加快 d r a m 的访问速度。设信元的长度为c ，外部端口速度为r ，d r a m 访问时间为t ，则b 应满足下式：b - 2 _ 2 r t c ，即在t 时间内，只要链路上传送的数据量2 r t 不大于s r a m 和 d r a m 之间传送的数据量b c 时，就能保证整个系统的性能。入口和出口s r a m 保存f i f o 队列的头尾信元，s r a m 中信元往d r a m 中的读入和读出以及指针管理由内存管理算法 来控制。该方案可以提高信元在d r a m 中的访问速度，并可实现大容量的f i f o 队列。 这种缓冲结构通常用在基于c r o s s b a r 交换网络中，其致命的缺点是仅适用于定长分 组的缓冲，且存在较大的访问延时，还需要复杂的内存管理算法。此外这种结构的可扩展 第7 页 信息工程大学硕士学位论文 性也不好，当链路速率进一步提高时，s r a m 和d r a m 之间并行传送的信元数b 会变化， 对应的内存管理算法也需要变化。由于该内存管理算法是高速的硬件逻辑实现，要修改会 带来很多不便。另外链路速率的变化也会引起d r a m 容量的变化，那么最坏情况下需要 更换整个d r a m 。对于输入数据为变长分组时，内存管理算法非常复杂，高速条件下这种 结构几乎不可用。 刊 组 口5r 口 图2s r a m 和d r a m 相结合的缓冲结构 2 3 并行分布式缓冲结构 根据高性能路由器的要求和对现有两种缓冲结构的分析，需要设计一种即能缓冲变长 分组，又能降低对缓冲读写访问速率要求，并且可扩展性好的缓冲结构。总的思路是对单 一缓冲结构进行并行分布式改造，力求在性能满足的前提下，使用几个小容量缓冲器来等 效一个大容量缓冲器，同时降低对缓冲器访问速率的要求。 2 - 3 1 并行分布式缓冲结构( p d b a ) 对单一缓冲结构进行并行分布式改造，得到的并行分布式缓冲结构( p a r a l l e l d i s t r i b u t e db u f f e ra r c h i t e c t u r e ，p d b a ) 如图3 所示。它有分路器、子层缓冲器和合路器 组成。分路器将外界输入数据以一定机制分配到各层；各层并行对该层输入数据进行缓冲 和其它相应处理；合路器对各子层缓冲器的输出数据进行合路输出，从而等效为一个单一 的高速大容量缓冲器，并使得缓冲器的读写访问速率可以低于链路速率。 并行分布式缓冲结构( p d b a ) 其实是并行分组交换p p s 在一个端口状况下，交换结构 是单一缓冲时的特例。因此p p s 的结论对它也适用。因此可以用p p s 理论来分析p d b a 的性 能。 第8 页 信息工程大学硕士学位论文 图3 并行分布式缓冲结构p d b a 假定所讨论的p d b a 结构各层之间没有共享信息，分路器与各层之间也无反馈通信， 并且p d b a 满足尽职工作( w o r k - c o n s e r v i n g ) 。刀的条件。为便于分析，引入一个单一缓冲 结构作为参考结构“”，该参考结构输出链路的最大速率为r ，输入链路的最大速率为2 r ， 满足尽职工作条件。 对于排队长度为q 似的队列，若队列输出速率为r ，则到达包的拥塞处理时间为 q ( t ) r 。参照p p s 的稳定工作条件吲来定义p d b a 的稳定工作条件，可以认为，参考结构是 稳定的，那么可以定义p d b a 稳定工作如下： 定义2 1 ( p d b a 稳定工作) ：在相同的外来业务条件下，如果p d b a 中到达包的拥塞处理 时间不大于参考结构中到达包的拥塞处理时间，则称p d b a 稳定工作。 这个定义说明只要p d p a 稳定工作，那么它的时延性能就能等效一个单一的缓冲。要 分析p d b a 的时延性能，那么就转化为考虑p d b a 的稳定工作条件了。 2 3 2p d b a 的稳定工作条件分析 并行分布式缓冲结构( p d b a ) 相当于是并行分组交换p p s 在一个端口状况下，交换 结构是缓冲器时的特例。它相当于分配器中无缓冲的p p s ，只是子层交换结构是缓冲器而 已。当外部一有输入数据时，那么输入数据就立即被分配器分配到各个子层中，不会在分 配器中被缓冲。由于p d b a 输入速率是输出速率的2 倍，所以子层缓冲器中只要不为空， p d b a 就处于拥塞状态。 对于无缓冲p p s 结构，到达包的拥塞处理时间为子交换结构部分的拥塞处理时间，对 p d b a 结构，即子层缓冲器的缓冲时间和相应处理时间。如果p d b a 要稳定工作，由定义 1 可得下式： 垒塑。盟 ( 式1 ) rr 为分析方便，考虑定长信元时的情况，令6 为包长。下文均是以c e 为基本单元进行 分析。因此后文中的t 均指的是对应整包操作完成的离散时间点。对于t 时刻p d b a 分配 到第k 层的业务4 m ，有如下定理： 定理2 1 ：p d b a 结构稳定工作的充要条件是：对于任意k ，t ，a k ( t ) 满足公式2 。 0 云爿 证明：充分性 ( 式2 ) 第9 页 信恳工程大学硕十学位论文 令p d b a 结构菜次发生拥塞的初始时刻为0 时刻，考虑处于搠塞情况下任一包在f 时刻到达，其拥塞处理时间为矿传j ，根据基本库存模型可得公式3 咖甜鲈引 ( 式3 ) 当公式2 成立时，根据公式3 可得： 渺，纠何z 肛4 纠炒= 口何一l 詈j 少倪= q ( t ) r 根据定义1 可知p d b a 稳定工作，所以充分性得证。 必要性 采用反证法，假设公式2 不满足，则有爿 导彳，所以有 蝴伽砌一