（计算机应用技术专业论文）基于网络处理器的流量管理系统研究与实现.pdf

摘要 近年来，随着计算机网络的飞速发展，新的应用层出不穷，而传统的i p 网络只 提供尽力而为( b e s te f f o r t ) 的业务，伴随着多媒体业务的引入，网络应用的多样性 要求其提供不同等级的服务并保证其服务质量安全技术，这就使得流量管理成为网络 研究体系中的一个重要组成部分。实现流量管理，不仅可以避免网络拥塞，还可以通 过减小丢包率、降低端到端延迟、提高吞吐量等支持服务质量，而且还可通过对不同 业务实施不同的流量控制机制来达到区分服务的目的。 本文对校园网出口大规模流量的特点进行了深入的研究，在现有算法的基础上， 提出了一种基于不同业务实施不同流量管理算法的方案，通过深入比较分析几种主要 队列管理算法的优缺点，在网络仿真平台n s 2 下，对不同应用的流量：f t p 流量、c b r 流量、h m 流量分别使用7 种队列管理算法：d r o p t a i l 、r e d 、f r e d 、s r e d 、b l u e 、 p i 、r e m 来进行仿真，得到不同应用流量的最优队列管理机制，然后综合所有流量进 行验证，实验结果表明，在网络利用率和数据包吞吐量方面均有明显的提高。 论文详细分析了i x p 2 4 0 0 的硬件架构和软件模型，利用其典型的多r i s c 内核并 行实时处理特性，在慰m i s y s 公司开发的e n p 2 6 1 1 开发板上进行流量管理系统的 实现。论文分析应用中的数据包处理流程，对系统资源的分配进行了规划，详细设计 和实现了软件架构的功能模块，主要的微码核心模块包括：数据包接收模块、流量识 别分类模块、流量整形模块、流量拥塞控制模块、队列管理模块、队列调度模块、数 据包发送模块，并在i n t e li x as d k4 0 上实现了系统仿真及在开发板e n p 2 6 11 上实 现了硬件测试。 实验结果测试表明：该系统能够对标记后的数据包进行准确的识别分类，对不同 应用的流量实行不同等级的服务，能够有效地保证网络的服务质量，并按要求实现速 率限制，有效地抑制了由于网络流量过大引起的网络拥塞，能够达到线速转发要求， 提高了网络带宽的利用率，符合设计要求。论文最后针对该设计方案的不足指出并提 出了相应的改进意见。 关键词：流量管理，队列管理，队列调度，网络处理器 基于网络处理器的流量管理系统研究与实现 a b s t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r ki nr e c e n ty e a r s ，n e w a p p l i c a t i o n sa l s oe m e r g em o r ea n dm o r ef r e q u e n t l y t r a d i t i o n a li pn e t w o r ko n l yp r o v i d e s t h eb e s t - - e f f o r t8 e t v i o e ，w i t ht h ei m p o r t i n go fm u l t i m e d i at r a n s m i s s i o n , ，n l ed i v e r s i t yo f n e t w o r ka p p l i c a t i o n sr e q u i r e sd i f f e r e n tl e v e l so fs e r v i c e st ob ep r o v i d e da n dt oe n s u r et h e q u a l i t yo fs e r v i c e ss e c u r i t yt e c h n o l o g y , 1 1 ：l i sm a k e st h e 锄cm a n a g e m e n ts y s t e mb e c o m e ： ： a ni m p o r t a n tc o m p o n e n to ft h en e t w o r kr e s e a r c h n 刮匝cm a n a g e m e n tn o to n l yc a na v o i d t h en e t w o r kc o n g e s t i o n , s u p p o r tt h eq o sb yi m p r o v i n gd r o p p i n gr a t e ，e n dt oe n dd e l a ya n d t h r o u g h p u t , b u ta l s oc a na c h i e v ed i f f e r e n ts e r v i c e st h r o u g he x p o s i n gd i f f e r e n tf l o wc o n t r o l m e c h a n i s mo nd i f f e r e n tt r a 伍c 珏ep a p e rh a sa d e e pr e s e a r c ho nm a s sf l o wc h a r a c t e r i s t i c so fc a m p u sn e t w o r ke x p o r t 。 b a s e do nc u r r e n ta l g o r i t h m s ，an e w a l g o r i t h mi sp r o p o s e dw h i c hu s e sd i f f e r e n tf l o w c o n t r o lm e c h a n i s mo nd i f f e r e n ts e r v i c e s w ec o m p a r ea n da n a l y z ed i f f e r e n tq u e u e m a n a g e m e n ta l g o r i t h m s ，u n e t w o r ks i m u l a t i o ns o f f w a r o - - n s 2t os i m u l a t et h en e t w o r k e n v i r o n m e n ti nw h i c hs e v e nq u e u em a n a g e m e n ta l g o r i t h m si n c l u d i n gd r o p t a i l ，r e d ， f r e d ，s r e d ，b l u e ，p i ，r e ma r ci m p l e m e n t e do nf 1 限f l o w , c b rf l o w , r n 叩f l o w r e s p e c t i v e l yt og e td i f f e r e n tm a n a g e m e n tm e c h a n i s ma n ds y n t h e s i z ea l lt h ef l o w st ov e r i f y t h ee x p e r i m e n ts h o w st h a tn e t w o r ke f f i c i e n c ya n dd a t at h r o u g h o u ta r ei m p r o v e d a p p a r e n t l y 1 1 l i sp a p e ra n a l y z e st h eh a r d w a r ea r c h i t e c t u r ea n ds o f t w a r ef r a m e w o r ko fi x p 2 4 0 0 ， e x p l o r e s i t sm u l t i p l e p a r a l l e l r e a l - t i m ep r o c e s s i n gr i s c s ，a n dr e a l i z e st h e 位喵c m a n a g e m e n t s y s t e m0 1 1t h ee v a l u a t i o nb o a r d - - e n p 2 6 11 ，ap r o d u c to fr a d i s y s 砸s t h e s i sa n a l y z e st h ed a t ap r o c e s s i n gf l o w , p l a n st h es y s t e mr e s o u i v 冶a l l o c a t i o n , a n dd e s i g n s m i c r o b l o c k si nt h es o r w a r ea r c h i t e c t u r e ，s u c ha sp a c k e tr x ，砌cm a n a g e m e n t , q u e u e m a n a g e m e n t , s c h e d u l e r , a n dp a c k e tt x ，a n dt h e ni m p l e m e n t st h es o l , r a r es i m u l a t i o no f t h i sa p p l i c a t i o no ni n t e ld 队s d k4 0a n di m p l e m e n t st h eh a r d w a r et e s t i n go nt h eb o a r d i l e n p 2 6 1 1 t h ee x p e r i m e n tt e s t i n gs h o w st h a t ：t h em a r k e d p a c k e t sc a nb ei d e n t i f i e da n dc l 嬲s i f i e d a c c u r a t e l y , a n db es e r v e da td i f f e r e n tl e v e l s ，w h i c hc a ne n s u r et h eq u a l i t yo f s e r v i c e s ，a n d t h e nb ef o r w a r d e da tl i m i ts p e e d ；w h i c hc a nr e d u c et h en e t w o r kc o n g e s t i o n t h i ss y s t e m c a ni m p r o v eu t i l i z a t i o no fn e t w o r kb a n d w i d t ha n d s a t i s f yt h es y s t e md e s i g nr e q u i r e m e n t s a tl a s tt h ep a p e r p o i n t so u tt h ed e s i g nd e f i c i e n c i e sa n dt h ec o r r e s p o n d i n gi m p r o v e m e n t s k e yw o r d s ：t r a f f i cm a n a g e m e n t 、q u e u em a n a g e m e n t 、q u e u es c h e d u l i n g 、n e t w o r k p r o c e s s o r i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律责任由本人承担。 论文作者签名： 丕工肇 日 期：2 遄、z ! 丝 关于学位论文使用授权的声明 本人完全了解济南大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借鉴；本人授权济南大学可以将学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复 制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 敝轹砗翩摊产? 型 第一章绪论 1 1 论文研究背景和意义 目前，计算机网络正处于其高速发展的时期，不但体现在网络传输速度的不断提 高，同时也体现在用户数量的急剧增长，以及网络应用的不断拓展和更新。除了传统 的数据业务，语音、视频等实时多媒体业务也正在被引入计算机网络并得到快速发展， 使得网络呈现服务多样性的发展趋势。简单的网络管理技术己不能适应网络迅速发展 的需要，如何高效、高质量地满足各种现代网络应用的多元化需求，如何保证计算机 网络的服务质量( q u a l i t yo fs e r v i c e ，q o s ) ，作为网络管理基础和核心部分的网络流量 管理技术，在理论上和技术上至今依然存在着许多重大的科学问题和挑战。 近年来i n t e m e t 主干网流量呈指数增长，主干路由器的处理速率已达1 0 g b p s 级， 这就对下一代网络设备提出了更高的要求：具有优异的性能，支持高速分组处理，具 有高度灵活性，支持不断变换的高层网络服务。传统的基于g p p ( g e n e r a lp u r p o s e p r o c e s s o r ) 的网络设备只满足灵活性要求；基于a s i c 的网络设备只满足高性能要求； 而网络处理靴【1 ( n e t w o r kp r o c e s s o r ) 兼有高性能和灵活性的特点，能够通过灵活的 软件体系提供硬件级的处理性能，并以其优异的性价比和高度的灵活性成为影响未来 口网络发展的关键技术之一。网络处理器是面向网络应用领域的特定应用指令处理 器，是面向数据分组处理的、具有体系结构特征和特定电路的、软件可编程器件。它 是一种专用于网络通信设备的通用芯片i 其灵活的软件体系提供硬件级的处理性能是 n p 的关键特性。网络处理器可以完成各种增值服务，如网络服务质量、虚拟专用网 p 、v o m 等。它也可以帮助业务供应商对服务进行区分，同时降低开发和配置服 务的成本。包括视频点播等服务在内的下一代应用，对流量优化和服务水平有着更严 格的要求，q o s 在其中作用重大。网络处理器的低开发成本和可编程特性使其成为实 现路由器q o s 的首选硬件。实现网络的q o s 要求网络能够区分不同的业务流，从而对 不同业务流的分组按q o s 要求进行不同的处理j 为此，要求路由器能够对到达的分组 进行分类，将不同类型的分组放入不同的缓存中进行排队，在分组发送时通过一定的 流量控制机制，使得发送的分组满足一定的延迟和抖动的要求。这些q o s 机制包括分 l 基于网络处理器的流量管理系统研究与实现 组队列的管理和队列输出调度机制。因此，研究探讨网络处理器中的q o s 实现机制中 有着重大的理论和实践意义。近几年，国内外基于网络处理器的研究也不断开展起来， 2 0 0 2 年，w e i d o n gs h i 【2 等人基于网络处理器使用动态窗函数约束调度算籼w c s ( d y n a m i cw i n d o w - c o n s t r a i n e ds c h e d u l i n g ) 来实现计算机网络q o s 保证，并对其进行 了改进，提出m l q ( h i e r a r c h i c a l l yi n d e x e dl i n e 婶q u e u e ) 分层检索线性队列机制来 提高网络数据包的处理速度。2 0 0 5 年，j i a n ig u o 3 1 等人基于网络处理器对动态批合作 调度算法 - - - d b c s ( d y n a m i cb a t c hc o s c h e d u l i n g ) 进行了改进，在d r r t l 7 】和s 砌一 算法的组合基础上提出动态封包批合作调度算法p 巾b c s ( d y n a m i cb a t c h c o - s c h e d u l i n g ) ，结果表明即满足负载平衡，又能按要求调度转发数据包。 目前大部分厂商都是以套片或集成的方式推出流量管理器芯片，比如：2 0 0 3 年领 先网络处理器的厂商e z c h i p 开发的第三代网络处理器n p 2 ，是一块全双工，分类搜索 引擎，进口出口1 0 g 1 ) s 的流量管理器【5 】；随后，b a y m i c r o s y s t e m s 公司的m o n t e g o 【6 1 是 一款单芯片o c l 9 2 e 1 0 g 网络处理器、流量管理器和s a r ( 分割和重组) 处理器，采用 x t e n s a 内核担当网络处理器执行c p u 。2 0 0 4 年a m c c 公司推出r i p 3 7 0 0 产品集成了网络 处理和流量管理功能，支持5 层分类和多层整形一能够为用户提供更好的，更灵活的 性能和流量管理解决方案忉。随着业界和研究领域的不断推动，流量管理成为当今网 络通信系统的网络处理器众多功能的核心。正如，2 0 0 3 年v i n o jk u m a r t 8 】提出了流量管 理正成为网络处理器领域的一大亮点，研究基于网络处理器的流量管理系统具有越来 越重要的意义，所以本论文的工作就集中在基于网络处理器的平台来研究流量管理系 统的方案设计、研究及实现。 1 2 作者的主要工作和贡献 由于园区内所有流量必须共享网络，以同样的方式对待它们是不公平的，所以本 论文在网络处理器的平台上提出了一种针对不同应用类型的数据流进行流量管理的 方案，主要完成以下工作： 1 针对不同应用流量的特点，对几种主要的公平队列管理算法的研究成果进行 分类、分析、模拟和比较，总结它们的优缺点，提出了一种基于不同业务实施不同队 列管理算法的方案的设计目标和策略， 2 对上述方案在网络仿真软件下进行仿真实验，主要从以下4 个q o s 性能指标 2 来进行比较：丢包率、传输时延、数据流的吞吐量、抖动率。仿真结果表明该方案能 提高网络利用效率，提高系统吞吐量。 3 充分利用网络处理器的并行性特点，在网络处理器i n t e li x p 2 4 0 0 平台上对流 量管理系统进行实现，主要完成流量识别分类、流量整形、流量拥塞管理，队列管理 及调度等功能，测试结果表明可以实现不同优先级的服务并能达到线速转发要求，能 够有效地保证网络的服务质量。 1 。3 论文的内容安排 本文详细论述了基于网络处理器的流量管理系统的研究与实现。全文组织结构如 下： 第l 章介绍了本论文的研究背景和意义、国内外相关研究工作情况、论文的主 要研究工作和贡献。 第2 章总体介绍流量管理系统的主要任务：流量识别分类、流量整形、队列管 理和调度。详细分析比较几种主要的队列管理算法和调度算法，并对流量整形算法进 行描述，分析其设计思路及优缺点； 。 第3 章简要介绍了系统开发过程中所用到的关键技术和部件，包括网络处理器 i n t e li x p 2 4 0 0 的硬件架构和软件模型、r a d i s y se x n p 2 6 1 1 开发板的结构和开发环境、 i x p 的可编程特性和开发调试环境等。 第4 章着重描述了本文提出的基于不同业务实施不同队列管理算法的方案，针 对不同应用流量的特点，在网络仿真软件n s 2 中进行模拟实验，对模拟结果进行分 析，得出本方案在减小丢包率和抖动率、降低端到端延迟、提高吞吐量等方面都有一 定的提高。 第5 章详细介绍了基于网络处理器的流量管理系统方案的设计和实现过程，设 计出编程模型的结构，给出每一个组成部分的功能及主要模块在网络处理器上的微码 实现。 第6 章对流量管理系统进行结果测试，分别使用i n t e l 提供的d e v e l o p e r w o r k b e n c h 软件仿真环境和r a d i s y s 提供的开发板e n p 2 6 11 硬件环境两方面对系统性 能进行测试分析。最后总结全文。 第二章网络流量管理 网络流量管理是网络处理器领域中众多技术中的一项重要技术。进行流量管理首 先要识别出网络中运行的所有流量，对各种不同应用的流量进行分类。然后根据标签 区分各种应用类型的数据流，什么流允许通过，什么流不允许通过，允许通过的流可 以按照什么样的速率通过，对延迟和延迟抖动有什么样的要求。最后经过整形调度输 出。即流量管理系统应该包括以下几个部分：流量的统计收集，流量识别分类，队列、 缓冲信息管理( 包括应用经典算法、如w r e d 、r i o 、f r e d 等以及理想地采用多个 缓冲池更好地隔离流量) ，还有调度整形。 国内外对网络流量管理的研究由来己久，对各个控制模块都有相应的算法研究。 如典型的策略算法包括漏桶( 1 e a k yb u c k e t ) k 令牌桶( t o k e nb u c k e t ) 算法等。拥塞管理算 法包括随机早期检测( 】陋d ) 和加权随机早期检测( w k e d ) 等。调度算法包括优先级队 列( p q ) 、公平队列( f q ) 、加权公平队列( w f q ) 和轮询队列- t e , _ r ) 等。 目前国内外许多厂商实现并整合了以上一些算法，把流量分类、整形、监测以及 队列缓存管理、队列调度等模块整合在一起，形成自己的流量管理产品。如p a e k e t e e r 公司的p a c k e ts h a p e r 系列就采用了c b q + p f q 卜t c r ，o p e n s o u r c e 公司的a l t q 采用 了c b q + r e d 算法，a c u t e b r o a d w e b 公司的i p o l i e e r l 0 0 c r 2 2 0 2 ，采用的整形算法就 是t c r 9 ，这些产品都能够对网络流量进行良好的控制。现今国内这种产品很少，对 网络控制算法进行深入研究，开发出原型系统，进而做出相应的网络设备具有重要的 意义。下文是各个控制模块的相关算法研究。 2 1 流量的统计、识别、分类： 为了让高优先级业务在接入网中的各个节点得到优先转发，保证“实时性 业务 对时延和时延抖动的需求，在本系统中，需要为不同的业务流提供不同的处理方式， ； 需要对业务流的行为进行检查和控制，需要采取措施使得每个业务流中的分组保持一 定的时间间隔。为此，需要对业务流的分组进行分类、计量、管制、调度、整形等措 施，需要有一个分组队列的管理机制以避免拥塞现象。； 分组的分类是为了识别分组所属的业务流。分组的分类可以用于各种目的，如为 4 不同的业务流提供不同的q o s 保证，对某些业务流进行过滤等。业务流通常可以分 为w e b 、电子邮件、办公系统、即时通讯、视频语音、网络下载以及其他应用类别。 这些类型是静态的，可以根据分组头中的协议类型进行分类。有些业务流信息是动态 的，比如从某个m 地址发出的到达某个目的地的业务流。它随时可能出现，随时可 能消失，需要根据分组的m 地址进行识别，这种分类是动态的分类。为了能够根据 分组的疋地址对业务流进行识别，路由器中需要记录有关业务流的地址信息。分 组的分类往往是一个跨越多个协议层次的操作，它可以根据p 分组头的信息进行， 同时也可以根据t c p 头的信息进行。目前，分组的分类通常根据分组中的源地址、 目的地址、源端口号、目的端口号和协议类型进行，称为5 元组分类。路由器根据这 些信息通过查找分类信息数据库以确定需要进行的处理方式，包括q o s 处理方式。 分组以后的分组进入不同的缓存队列，从而得到不同方式的处理。 2 2 流量整形控制 ， 流量整形控制是网络处理中的一种常用q 6 s 技术。流量整形的目的是为了使经过 网络瓶颈的数据包平缓地进入网络，减少数据包在边缘网关排队等待时问，从而减少 边缘网关缓存的大小以及数据包丢失率。 当今最著名而被广泛应用的流量控制技术莫过于t c p 协议中采用的滑动窗口；此 外，令牌桶过滤器也是一种常用的流量控制技术。 令牌桶过滤器( t o k e nb u c k e tf i l t e r ，t b f ) ，简称为令牌桶。其基本思想是通过 控制令牌流入流出令牌桶来调控网络中流经的数据包( 如图2 1 ) ，从而达到调控数据 流速率，使网络流量平滑，避免过大的突发流量的目的。 一个令牌桶可以由2 个基本参数描述：令牌流入令牌桶的速度v ( 令牌产生速率) ， 令牌桶的深度( 最大容量) n 。通过将数据流关联到令牌流上，即每个到来的令牌从 数据队列中收集一个数据包，然后从桶中被删除，则某段时间t 内流过令牌桶的数据 包的数目c 最多只能为：c = v t + n ，这样便可以达到调控数据流的目的。另外，通过 讨论数据流与令牌流的关系可以得到3 种情况： 基于网络处理器的流量管理系统研究与实现 鼍詈鼍曼量曼詈詈詈皇曼皇暑皇皇曼皇毫曼詈! 暑詈皇皇曼i 皇詈鼍! 曼詈暑詈! 曼曼詈曼! ! 皇皇曼曼曼暑皇皇皇皇曼皇曼皇量量曼曼皇詈量詈皇詈詈鼍 令牌流 l 速度vl 令牌，秒i j i 桶 深 n 令 竺 图2 1 令牌桶流量控制示意图 二 1 数据流以等于令牌流的速率到达令牌桶。这种情况下，每个到来的数据包都 能对应一个令牌，这意味着令牌的消耗速率不是恒定的但是有限的。如果桶中没有令 牌，那么下一个数据包将被延迟并缓存。这保证了数据包的转发速率得到了有效地控 制，因为令牌的产生速率引入了一个限制。 2 数据流以小于令牌流的速度到达令牌桶。通过队列的数据包只消耗了一部分 令牌，剩下的令牌会在桶里积累下来，直到令牌桶装满。剩下的令牌可以在需要以高 于令牌流速率来发送数据流的时候消耗掉，这种情况下就会产生小量而且可控的突发 传输流。 3 数据流以大于令牌流的速率到达令牌桶。这时桶里的令牌很快就会被耗尽， 而且缓冲队列将会被占满。如果数据包持续超出限制地到来，则超出的那部分报文将 会被丢弃。这时虽然流进令牌桶队列的流量速率大于令牌产生速率，但流出的流量将 可以比较稳定的维持在令牌产生速率上。 实际应用中，除了令牌产生速率和桶深度外，还可以对缓冲等待队列的长度进行 调节来控制令牌桶的工作性能。 常见令牌桶算法： 1单速率三色标记器算法s r t c m ( r f c 2 6 9 7 ) 0 0 算法的参数包括：承诺信息速率c i r ( 即用户设定的流量速率上限值，单位k b p s ) 、 承诺突发大小c b s ( 即用户设定的可接受的最大突发数据包的长度，也就是令牌桶 的深度，单位b 归) ，超出突发大小( e b s ) 。算法地实现过程如图2 2 所示，使用了两 个令牌桶与单一的产生令牌的速率c i r ，以c i r 的速率向c 桶中填充令牌，如果令 牌桶c 未满，则把该令牌放入令牌桶c 中，否则当c 桶中令牌满( t ( c ) = c b s ) 后“溢出”的令牌流向e 桶，当e 桶中令牌满( t ( e ) = e b s ) 后“溢出”的令牌直接丢 弃。 i b - e 坚鳃n l - 一ii 幽口 圉曲黾 图2 2s r t c l l 令牌控制示意图 数据报文处理中的转发和丢弃。算法流程如下：当一个令牌桶尚未取完时，数据包被 2双速率_ - - 色标记器算法t r t c m ( r f c 2 6 9 8 ) t i l l 法与s r t c m 相同。即根据4 种流量参数：承诺访问速率( c i r ) ，承诺突发尺寸( c b s ) ，峰 值速率( p i r ) ，峰值突发尺寸( p b s ) 来标识报文的颜色( 绿、黄、红) 。 2 3 队列管理与调度技术 理和队列调度是数据流量处理过程中2 个关键环节，前者为到达的流量分配存储空间， 并且在存储空间满，网络发生拥塞的时候选择数据包丢弃。而队列调度机制是从所有 7 基于网络处理器的流量管理系统研究与实现 2 3 1 队列管理算法简介 队列管理1 2 1 1 1 【1 是对网络传输节点中队列缓冲资源的管理。在分组传输过程中，其 流经的网络传输节点通常采用队列缓存、延迟转发的服务方式以提高输出链路的带宽 利用率。缓冲管理机制在分组到达队列前端时依据一定的策略和信息决定是否允许该 分组进入缓冲队列，从另一个角度看，也就是做出是否丢弃该分组的决策，因此也称 为丢弃控制。 队列管理在网络传输控制中发挥着相当大的作用，是网络服务质量( q o s ) 控制的 核心技术之一，也是实现网络拥塞控制的重要手段。队列管理算法主要是在网络发生 拥塞时通过丢包来管理队列长度。对队列长度进行管理直接影响到路由器的拥塞控制 能力和q o s 能力。队列管理是管理一种类型的业务流的分组在缓存中的队列长度，通 过采取适当的措施来避免队列长度超出一定的限度。队列长度的增加会使得分组传输 延迟增加。如果没有队列管理，在队列溢出时就要被迫丢弃分组。t c p 协议的重传机 制会重新发送被丢弃的分组，从而增加网络的传输负担，甚至导致网络拥塞现象。队 列管理可以选择丢弃的分组来控制队列的长度，从而达到更好的效果，即减少分组的 延迟并避免拥塞现象。主要的队列管理算法有以下几种t 1 d r o p t a i l 即所谓的”去尾 算法，就是对每个队列设置一个最大值( 以包为单位) ，然后接 收包进入队列直到队长达到最大值，接下来到达的包就要被拒绝进入队列直到队长下 降。这种技术存在几个重大缺陷【1 3 1 ： 死锁问题：在某些情况下，去尾”算法会让某个流或者少数几个流独占队列空间， 阻止其他流的包进入队列。这种”死锁”现象通常是由于同步或其他定时作用的结果。 满队列问题：由于去尾”算法只有在队列满时才会发出拥塞信号，因此会使得队 列在相当长时间内处于充满( 或几乎充满) 的状态。而队列管理最重要的目标之一就 是降低稳定状态下队列的长度，因为端到端的延迟主要就是由于在队列中排队等待造 成的。 全局同步问题：由于i n t e r a c t 上数据的突发本质，到达路由器的包也往往是突发的。 如果队列是满的或者几乎是满的，就会导致在短时间内连续大量地丢包。而t c p 流具 有自适应特性，源端发现包丢失就急剧地减小发送窗口，包到达速率就迅速下降，于 8 济南大学硕士学位论文 是网络拥塞得以解除，但源端得知网络不再拥塞后又开始增加发送速度，最终又造成 网络拥塞，而且这种现象常常会周而复始地进行下去，从而在一段时间内网络处于链 路利用率很低的用状态，降低了整体吞吐量，这就是所谓地t c p 全局同步”现象。 除了 去尾”机制，另外两种在队列满时进行队列管理的机制是”随机丢弃和 从前 丢弃”机制。当队列满时，前者从队列中随机找出一个包丢弃以让新来的包进入队列； 后者从队列头部丢包，以便让新包进入队列。这两种方法虽然都解决了”死锁”问题， 但仍然没有解决”满队列”问题。 2 r e d 1 4 , 1 s l 随机早期检测叫o me a r l yd e t e c t i o n ，r e d ) 算法，是目前最常用的一种主动队列 管理算法。r e d 的基本思想是路由器通过监控队列的平均长度来探测拥塞。一旦发现 拥塞逼近，就随机地选择源端来通知拥塞，使它们在队列浠小之前降低发送数据速率， 以缓解网络拥塞。r e d 算法主要包括两步：一 1 ) 首先计算平均队列长度，然后计算丢弃包的概率。r e d 使用了一个指数加权滑 动平均地滤波器来计算平均队列长度，公式如下： a v g = ( 1 一) a v g + g ( 1 ) 其中，为权值，决定了低通滤波器的时间常数。q 为采样测量时实际队列长度。 从而“过虑 掉由于i n t c m c t 数据的突发性导致的短期队长变化，尽量反映长期的拥 塞变化。计算平均队长的目的就是为了反映拥塞程度并据此来计算丢包概率。 2 ) 计算丢弃包的概率 计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃包的概 率，从而有效地控制平均队列长度。r e d 有两个和队列长度相关的阈值： m i n 埔，t i i 敬埔。当有数据包达到路由器时，i 迮d 汁算出平均队k a v g 。设 p 6 = 竺殳型罢l m a xp：2 ) m a xt h 。m l n t k 则包丢弃概率p 口由下式给出： 1 0 , 0 a v g f r e e z e _ t i i i l e ) ， 1 0 p m = p m d 2 l a s t _ u p d a t e - - - n o w ； u p o np a c k e tl o s se v e n t ：拥塞时的事件 i f ( ( n o w - l a s tu p d a t e ) f r e e z et i m e ) p m = p m + d 1 ； l a s tu p d a 慨o w ； b l u e 基于丢包事件和链路空闲事件的拥塞管理，能够使用相对较小地缓冲区完 成较好的估计拥塞程度，提高了t c p 流的吞吐量。因此其标记包的比率相对较稳定， 这又使得队长也相对稳定，减少了延迟抖动。而r e d 基于平均队长拥塞管理，由于不 能正确及时地估计拥塞严重性，特别是在负荷很重，变化很快的情况下，常常导致队 长波动很大，增加了丢包率和延迟抖动，甚至产生全局同步现象，降低链路使用率。 4 。s t a b i l i z e dr e d ( s r e d ) t 1 9 1 s r e d 的设计目的是保持f i f o 队列长度的稳定而与活跃流的数量无关。 s r e d 的基本思想就是利用将到达数据包与多个存于b u f f e r 中的不同流的包中 随机取出一个进行比较。当有一个包到达队列时，就从队列中随机选出的一个包进行 比较，若这两个包属于同一个流，则称为“击中 。s r e d 设计了一种数据结构，称为 “僵尸 列表，相当于一种流c a c h e ，其中记录了最近流经该队列的m 个流及两个状 态信息：c o u n t 和时间戳。其中c o u n t 表示被击中的次数；时间戳则记录了该“僵尸一 产生的时间或最近一次被“击中”的时间。 起初列表为空，当有一个包到达时，则将该包的流标识( 源、目的地址等) 加入列 表，这样，就产生了一个新的“僵尸 。一旦“僵尸一列表满了，那么就将新来的数 据包和“僵尸一列表中随机选出的“僵尸 进行比较： ( 1 ) 如果击中，则此僵尸的c o u n t 加1 ，时间戳改为当前包的到达时间； ( 2 ) 如果未击中，则以某个概率用新数据包的流标识覆盖选出来的僵尸，c o u n t 重 置为0 ，时间戳改为刚到包的到达时间。 s r e d 用一个函数h i t ( t ) 来记录第t 个包是否击中，如果击中，贝j j h i t ( t ) 取值为1 ，否 则为0 。然后计算第t 个数据包到达时击中的概率【2 0 】： 尸( f ) = ( 1 一口) p ( t 一1 ) + 口h i t ( t ) ，( o a 8 ) a v g ( 2 ) 队列非空时的平均队列长度计算与_ i 三速类似，公式简化后如下： a v g 2 1 6 = a v g 2 1 6 + 国一嘴) p r o b a b i l i t y )m o v e d m n e x t _ b l o c k , b i d _ q m e l m o v e d l _ n e x t _ b l o c k , b i d _ d r o p 】 5 3 3 队列管理模块 队列管理模块q m 是单独运行在单个微引擎的微块，负责对分组发送队列进行入 队和出队操作，各个队列的描述符存放在s r a m 中，由于s r a m 控制器中有专门的 硬件q - a r r a y 单元和可用于快速查找匹配的c a m 部件，在微引擎的q - a r r a y 单元中 存放1 6 个l r u 队列( l r u 机制由c a m 部件提供) 的信息，并和c a m 部件中 的查找项相匹配，当分组到达时，首先根据其队列编号通过c a m 部件查找，如果匹 配上，则无须再读取该队列的信息，可以节省一次共享存储器的存取操作；否则，选 择一个缓存的队列信息项( l r u ) 写回到s r a m 中，读取指定的队列信息到q _ a r r a y 单元中，并更新c a m 查找项的内容。 考虑到队列管理模块处理的分组的连续性( 由突发造成) ，采取队列信息缓存的策 略可以有效地降低共享存储器的访问次数，减少微引擎的内存访问延迟，提高系统的 运行效率和微引擎处理器资源的利用率。 然而，新的队列管理策略同样也带来了新的共享数据同步问题。由于部分队列信 息缓存在队列管理模块中，分组调度模块无法直接访问这些队列信息，而如果引入数 据同步更新机制将极大程度地增加系统的复杂性和运行开销。考虑到这一点，我们把 分组的出队列操作转移到队列管理模块中，由队列管理模块负责全部的队列操作，避 免数据同步更新问题；而分组调度模块只负责分组的“调度 ，不再参与队列操作。 分组调度模块用于调度算法执行的分组信息由队列管理模块通过专用数据通道提供， 将在队列管理模块设计部分中给出较为详细的说明。 5 3 4 队列调度模块 图5 7 队列管理模块 分组调度模块用于调度算法执行的分组信息由队列管理模块通过n n r 提供。所 以q m 只负责处理入列和处理请求，同时每入列或出列一个数据包，q m 都会给调度 器发送一个通知消息。q m 模块负责接收e n q u e u e 请求，将数据包加入到指定的发送 队列，接收调度器发来的d e q u e u e 请求，从指定的发送队列中取出一个数据包，交给 发送模块发送。 在本系统中，调度模块支持4 个端口，在不同的端口之间采用w r r 调度算法， 而在每个端口上可以支持1 6 个不用的队列，队列之间采用d r r 调度算法，实现如下： ，少、 皿皿栅 4 专瓣 圆皿牝l 衄皿l 皿圆籼- j 图5 8 队列调度示意图 端口调度执行w r r 算法，找出至少有一个队列有数据可供调度的端口，队列调 度执行d r r 算法，找出一个有数据可供调度的队列。端口调度和队列调度都使用比 特矢量来跟踪、记录端口和队列的状态信息。一旦调度算法找到一个可供调度的队列， 调度器就向q m 发送一个d e q u e l l e 请求，请求从指定的发送队列中取出一个数据包 夺给管潢燧换侍拱 5 3 5 数据包发送模块 数据包发送模块负责将数据包发送到以太网的网络接1 2 1 。发送模块q m 从s c r a t c h r i n g 中得到队列管理模块发送过来的数据包描述符。并据此确定数据包在d r a m 中 的具体位置，同时追踪被发送的包的数量并使用反馈装置告诉调度模块多少包已经被 发送了。在封装了二层包头之后，将一个p a c k e t 拆分为多个m p a c k e t ，最后通过m s f 中的发送状态机将m p a c k e t 发送到外部网络接口。 数据包发送模块