（计算机应用技术专业论文）多优先级队列管理机制研究与仿真.pdf

摘要 随着网络的迅速发展，网络的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 保证成为当前网络研究的热点问题。主动队列管理和分组调度算法都 是实现q o s 重要的内容。 本文首先分析了现有的队列管理算法：r e d ( r a n d o me a r l y d e t e c t i o n ) 及其衍生算法，并在w r e d ( w e i g h t e dr a n d o me a r l yd e t e c t i o n ) 算法的基础上，通过引入r e dg e n t l e 算法中使用的2 m a x t h 参数，提 出了一种改进的队列管理算法：w r e d 。此改进算法可实现区gentle 分服务，并能稍微减弱对m a x d 参数的敏感性，增强了w r e d 的鲁棒 性。 然后对现有的典型分组调度算法：p q ( p r i o r i t yq u e u e i n g ) 算法、 e d f ( e a r l i e s td e a d l i n e df i r m ) 算法等进行了阐述。详细分析了一种将时 间片与优先级相结合的新的动态优先级调度算法：p q b e d f ( p r i o r i t y q u e u eb a s e do ne d f ) ，由于p q b e d f 方案中动态优先级随时间片变化 过快从而降低了高优先级队列服务质量，从而提出了一种改进的分 组调度算法：p q b e d f + 。此改进算法根据缓冲区的实际使用情况， 通过对不同的业务引入阈值来控制优先级的动态变化，从而有效地增 强了算法的公平性保证。同时从缓冲区管理算法考虑，由于p q b e d f 算法中采用的丢弃策略为d r o p - t a i l 或d r o p h e a d ，采用此策略在缓冲 区管理方面没有分组优先级的概念，无法提供区分服务，因而考虑将 p q b e d f + 调度算法与w r e dg e n t l e 缓冲区管理算法有机地结合在一 起，能够实现区分服务，保证分组的端到端延迟，明显提高了网络资 源分配的有效性。 最后对论文中所提出的w r e dg e n t l e 算法和p q b e d f + 算法均在 o p n e t 网络仿真环境下进行了仿真实验，实验结果表明改进后的算 法性能明显提高。 关键词：服务质量，队列管理，分组调度，o p n e t a b s t r a c t f i t ht h ed e v e l o p m e n to ft h ei n t e r n e t ，t h eg u a r a n t e e i n go f o u a l i t yo fs e r v i c e ( q o s ) h a sb e c o m ea ni m p o r t a n tp r o b l e m a c t i v e q u e u e sm a n a g e m e n ta n dp a c k e ts c h e d u li n ga l g o r i t h m s a r e i m p o r t a n tc o n t e n t so fo o s f i r s t l y ，t h i st h e s i sa n a l y z e st h er e c e n tq u e u e sm a n a g e m e n t a l g o r i t h m s ：r e d ( r a n d o me a r l yd e t e c t i o n ) a n di t sd e r i v a t i r e a l g o r i t h m s t h e nb yi n t r o d u c i n g2 m a x t hp a r a m e t e r st h a ta r eu s e d i nr e d g e n t l e ，a ni m p r o v e dq u e u em a n a g e m e n ta l g o r i t h mo nt h e b a s i so ff r e d ( w e i g h t e dr a n d o me a r l yd e t e c t i o n ) ：f r e d g e n t l e ，i s p r o p o s e d t h i sn e wa l g o r i t h mc a na c h i e v ed i f f s e r va n ds li g h t l y w e a k e nt h es e n si ti v tit yo f m a x pp a r a m e t e ra n de n h a n c et h e r o b u s t n e s so fw r e da l g o r i t h m s e c o n d l y ，t h i st h e s i sa n a l y z e st h er e c e n t p a c k e t s c h e d u li n g a l g o r i t h m s ：p o ( p r i o r i t yq u e u e i n g ) ，e d f ( e a r l i e s t d e a d li n e d f i r s t ) a l g o r i t h m sa n ds oo n a na d v a n c e dd y n a m i c p r i o r i t ys c h e d u l i n ga l g o r i t h mc o m b i n i n gs l o ta n dp r i o r i t i e s ： p o b e d f ( p r i o r i t yq u e u eb a s e do ne d f ) a l g o r i t h m ，i sa n a l y z e d b e c a u s et h ed y n a m i cp r i o r i t yi sc h a n g i n gt o oq u i c k l ya n dt h e o u a li t yo fs e r v i c ef o rh i g h e rp r i o r i t yq u e u e si sr e d u c e d ，a n i m p r o v e dp a c k e ts c h e d u li n ga l g o r i t h m ：p o b e d f + i sp r e s e n t e d d e p e n d i n go nt h ea c t u a ls i t u a t i o no fu s e db u f f e r ，p q b e d f + a l g o r i t h mi n t r o d u c e st h r e s h o l df o rd i f f e r e n tb u s i n e s s e sa n d e n h a n c e si t sf a i r n e s sg u a r a n t e e a tt h es a m et i m e ，b u f f e r m a n a g e m e n ta l g o r i t h m sa r ea l s oc o n s i d e r e d s i n c et h ed r o p t a i l o rd r o p h e a d d i s c a r d i n gs t r a t e g yi si m p l e m e n t e di np q b e d f a l g o r i t h m ，t h ec o n c e p to fp a c k e tp r i o r i t yd o e sn o te x i s ta n d d i f f s e r vc a n tb e p r o v i d e d h e n c ep q b e d f + a l g o r i t h ma n d w r e d _ g e n t l ea l g o r i t h ma r ec o m b i n e dt oa c h i e v ed i f f s e r va n d g u a r a n t e et h ee n dt oe n dd e l a yo fp a c k e t s ，w h i c ho b v i o u s l y i n c r e a s e st h ee f f e c tiv e n e s so fn e t w o r kr e s o u r c ea ll o c a tio n f i n a l l y ，t h ef r e d _ g e n t l ea n dp q b e d f + a l g o r i t h md e s c r i b e d a b o v ea r es i m u l a t e da n d p r o v e d w i t ho p n e ts o f t w a r e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep e r f o r m a n c eo fa l g o r i t h m s a r ei m p r o v e dg r e a tly k e yw o r d s ： q u a li t yo fs e r v i c e ，q u e u em a n a g e m e n t ，p a c k e t s c h e d u li n g ，o p n e t 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：同馨哞 五d 扩年月厂日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密留。 ( 请在以上相应方框内打“ ) 作者签名：闻荣竿 日期：2 0 。孑年 月g 日 导师签名：钐舷 日期占。箩年 月j 日“ 多优先级队列管理机制研究与仿真 1 绪论 i n t e m e t 自2 0 世纪6 0 年代出现以来发展迅速，近年来更是随着计 算机技术与通信技术的不断发展正以惊人的速度增长，联网的主机每 年翻一番，w e b 站点每半年翻一番。同时，伴随着计算机多媒体技术 的不断发展，i n t e m e t 已经由传统的数据传输转向综合数据、语音、 图像等多媒体的综合业务传输。而i n t e m e t 中以口技术为主体的特点 决定了其只能提供尽量做好( b e s t e f f o r t ) ) 艮务，与虚电路技术相比，p 采用的是非面向链接，这就使得在p 网络上传送语音、图像等多媒 体业务时，其延时不可预测，网络带宽不能保证，无法满足多媒体应 用和不同的用户对网络传输质量的不同要求。因此，网络服务质量 ( q u a l i t yo fs e r v i c e ，q o s ) 控制方面的研究是目前计算机网络中的热点 领域。 1 10 0 s 的发展 对计算机q o s 的研究可以追溯到2 0 世纪8 0 年代初期。那时， 尽管网络的性能还比较低，提供的服务种类也比较少，但一些有远见 的研究者已经认识到服务质量的重要性。s e i t z 和w o r t e n d y k e 等人在 研究a r p a n e t 中的x 2 5 通信时已提出基于用户的性能评价问题， 这也许是关于计算机网络q o s 研究的最早文献【lj 。在早期的o s i 协议 制定中，也为服务质量的一些参数留有相应的表示手段，但一直空缺 未用。很长一段时间，由于计算机网络的性能所限，人们对q o s 的 关注只停留在数据流传输中的正确率、吞吐量、延迟等单一服务质量 的评价与控制上。直到2 0 世纪8 0 年代末期，随着b i s d n 技术以及 a t m 交换网的出现和分布式多媒体应用的急剧增加，人们才开始系 统地对q o s 管理和控制进行较为深入的研究。一些实验性系统也应 运而生，代表性的有英国兰开斯特大学的q o s a 工程【2 1 、美国哥伦比 亚大学的扩展的集成化参考模型( x r m ) 系统【3 】、国际合作项目 硕士学位论文 t i n a c 工程【4 】、美国加州伯克利大学的t e n e t 工程式【5 1 、i b m 公司 黑森伯格欧洲网络中心的h e i p r o j e c t 工程1 6 j ，等等。 随着i n t e r n e t 商业化的巨大成功，网上传输的多媒体信息迅速增 多，网络拥塞现象日益严重，i n t e r n e t 的q o s 问题研究也随之开始深 入，i e t f 于1 9 9 7 年9 月开始制定了有关q o s 定义与服务的一系列 r f c 标准，典型的工作是提出了两种不同的i n t e m e tq o s 体系结构： 综合服务( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) 7 1 和区分服务( d i f f e r e n t i a t e d s e r v i c e s ，d i f f s e r v ) 1 8 1 。截至目前，q o s 控制技术的研究和开发都进展 得非常迅速，并且已经取得了很多基本的成果。国内也于近些年开始 了有关q o s 控制方面的研究。 1 20 0 s 的概念和技术指标 1 2 1o o s 的概念 服务质量( q o s ) 的提出是独立于宽带网络的，因为它泛指所有通 信业务的服务质量，但是宽带网络的发展使q o s 这个概念变得格外 重要。这有多种等价或互补的定义形式。 r f c 2 3 8 6 9 】中描述为：q o s 是网络在传输数据流时要求满足的一 系列服务请求，具体可以量化为带宽、延迟、延迟抖动、丢失率、吞 吐量等性能指标。此处的服务具体是指数据包( 流) 经过若干网络节点 所接受的传输服务，强调端到端( e n d - t o e n d ) 或网络边界到边界的整体 性。q o s 反映了网络元素( 例如，应用程序、主机或路由器) 在保证信 息传输和满足服务要求方面的能力。 另一种描述【1 0 】为：q o s 是指发送和接收信息的用户之间以及用户 与传输信息的综合服务网络之间关于信息传输的质量约定。该约定可 以被理解为服务提供者与用户之间的一份服务契约，即服务提供者承 担支持给定的服务质量，当且仅当用户按照约定的信息流特征产生数 据。换句话说，服务质量包括用户的要求和网络服务提供者的行为两 个方面，是用户与服务提供者两方面主客观标准的统一。用户的要求 多优先级队列管理机制研究与仿真 是指用户在i n t e r n e t 上进行多媒体通信时所要求的服务类型以及相应 的传输性能和质量等；网络服务提供者的行为则指i n t e m e t 针对某一 类服务所能提供和达到的性能与质量。 从以上两种描述不难看出，对q o s 的理解总的来说可以总结为 两类看法：一类从网络的角度出发，认为q o s 最终体现为网络性能 n p ，对应于第一种描述；另一类从用户的角度出发，认为q o s 是业 务的质量要求，对应于第二种描述。 q o s 控制的目标是为i n t e r n e t 应用提供服务区分和性能保证：服 务区分是指根据不同应用的需求为其提供不同的服务；性能保证则要 解决诸如带宽、丢失、延迟、延迟抖动等性能指标的保证问题。 1 2 20 0 $ 的技术指标 q o s 的技术指标包括多个方面的内容，如可用带宽、时延、时 延抖动、丢包率、可用性等。每种业务都对q o s 有特定的要求，有 些可能对其中的某些指标要求高一些，有些则可能对另外一些指标要 求高些。衡量q o s 的技术指标主要有以下几个方面： ( 1 ) 可用带宽 可用带宽指网络的2 个节点之间特定应用业务流的平均占用带 宽，主要衡量用户从网络取得业务数据的能力。所有的实时业务对带 宽都有一定的要求，如对于视频业务，当可用带宽低于视频源的编 码速率时，图像质量就无法保证。 为保证一些关键业务的可用带宽，在带宽设置上一般采用轻载的 方式来保证其相应的需求。对于商业用户的普通业务，带宽设计是其 实际需求的1 5 倍；对于商业用户的商业数据业务，带宽设计是其实 际需求的2 倍；对于商业用户的语音视频业务，带宽保证采用优先 队列的方式，只要有商业用户语音和视频数据过来就传送，但限制 最大可使用链路的总带宽：对于普通互联网业务，不作带宽保证， 使用剩余带宽。 ( 2 ) 时延和时延抖动 硕士学位论文 时延指数据包在网络的2 个节点之间传送的平均往返时间。所 有实时性业务都对时延有一定要求，如v o p 业务，一般要求网络单 向时延小于1 0 0m s ，当网络单向时延大于2 0 0m s 时，通话就会受到 影响。时延抖动指时延的变化。有些业务，如流媒体业务，可以通 过适当的缓存来减少时延抖动对业务的影响；而有些业务则对时延 抖动非常敏感，如语音业务，稍许的时延抖动就会导致语音质量迅 速下降。 ( 3 ) 丢包率 丢包率指在网络传输过程中丢失报文的百分比，用来衡量网络正 确转发用户数据的能力。不同业务对丢包的敏感性不同。在多媒体业 务中，丢包是导致图像质量恶化的最根本原因，少量的丢包就可能使 图像出现马赛克现象。丢包通常是拥塞造成的。 在口网络拥塞时，对不同业务应采用不同的丢包策略。商业用 户的语音和视频业务等级最高，实施不参与w r e d 丢包策略，采用 最大带宽的方式限制对其他业务级别带宽占用；对商业用户的商业数 据、普通数据和普通互联网业务等级实施w r e d 丢包策略，以预防 拥塞。为了实现各业务等级服务质量的差异性，不同等级的队列采用 不同的w r e d 参数进行丢包。总的来说，等级越低，丢包越早。 ( 4 ) 网络可用性 网络可用性是指网络节点之间在能够保证质量要求的前提下传 输数据的时间占总时间的百分比，是衡量网络质量的最重要的指标。 决定网络可用性的关键技术包括路由快速收敛技术、快速重路由 ( f r r ) 技术、软硬件在线升级技术、协议平稳重启技术和设备自身可 靠性技术，另外，还与传输网络的可用性相关。 为提高网络可用性，一般建议在网络核心节点之间启用m p l s f r r ，通过m p l sf r r 对核心链路作毫米级别快速保护；同时，在 设备条件允许的情况下，可实施路由快速收敛技术和协议平稳重启技 术，保证i g p 的快速收敛和设备路由引擎切换时不影响网络流量。 多优先级队列管理机制研究与仿真 1 3 目前关于q o s 的研究状况 到目前为止，已经提出了许多q o s 控制机制，包括综合服务体 系结构模型( i n t s e r v ，i n t e g r a t e ds e r v i c e s ) 与资源预留( 如r s v p ) ；区分 服务体系结构模型( d i f f s e r v ，d i f f e r e n t i a t e ds e r v i c e ) ；拥塞控制机制； 分组调度和队列管理算法等等。下面就这几个方面的研究状况分别作 简要的介绍。 1 3 1 综合服务与区分服务体系结构 q o s 研究的目标是提供有效的端到端的服务质量控制或保证。 q o s 就是网络单元( 例如，应用程序，主机或路由器) 能够在一定级别 上确保它的业务流和服务要求得到满足。q o s 并没有创造带宽，只 是根据应用程序来实现q o s 的一种方法是按照服务水平的要求分 配资源给每一个数据流。这种采用“资源预留 进行带宽分配的方法 并不适合“尽力而为 型应用。由于带宽资源是有限的，q o s 的设 计者引入了优先级概念，使得在资源预留后“尽力而为”服务的数据 流的传输也能得到一定的保障。因此，i pq o s 可以分为两种基本类 型： 基于资源预留：网络资源按照某个业务的q o s 要求进行分配， 制定资源管理策略。互联网工程任务组( i n t e m e te n g i n e e r i n gt a s k f o r c e ，i e t f ) 提出的综合服务( i n t s e r v ) 川体系结构便是基于这种策略， 资源预留协议( r e s o u r c e r e s e r v a t i o np r o t o c o l ，r s v p ) t 忆】是其核心部分。 i n t s e r v 通过r s v p 能够提供很好的确定服务质量保证，但是它需要 在整个路径上进行资源的预留，这种资源预留是基于软状态机制对每 个业务流实施的，软状态需要周期性地进行更新，当业务流数目很多 时，扩展性受到很大的影响，这是i n t s e r v 最大的缺陷。 基于优先级：网络边界节点对业务流进行分类、整形、标记。核 心节点按照资源管理策略分配资源，对q o s 要求高的业务给以优先 处理。i e t f 提出的区分服务( d i f t s e r v ) 1 1 3 】【1 4 1 便是基于这种策略。 硕士学位论文 d i f f s e r v 是为解决i n t s e r v 不足和缺陷提出的，它在业务的q o s 保证 和算法的复杂性方面做了一定的折衷。在d i f f s e r v 里，引入了d i f t s e r v 域的概念，把支持相同规则d i f f s e r v 功能的路由器集合称为一个 d i f f s e r v 域。d i f f s e r v 域由边界路由器和中间路由器组成。边界路由 器主要完成业务量调节的功能，包括业务的测量、标记和丢弃处理， 经过边界路由器后，分组被打上相应的标记( 称为d i f f s e r v c o d e p o i n t ，d s c p ) ，然后进入d i f f s e r v 域内。中间路由器每收到一个 p 分组，就查看其d s c p 值，然后进行相应的调度处理，这种调度处 理与d s c p 值是一一对应的，在d i f f s e r v 体系结构里，称为逐跳行为 ( p e r - h o p b e h a v i o r ，p h b ) 【l 5 1 ，逐跳转发行为p h b 是一个d s 节点调 度转发特定流聚集行为的外特性描述，p i - b 可以调度转发流聚集时 的一些流特性参数( 如延迟、丢失率) 描述，当某个p h b 可能与其它 p h b 共存于一个节点时，还心须指出在分配资源( 如缓冲区、带宽) 时与其它p i - i b 的相对优先级。本质上，p h b 就是单个d s 节点根据 收到的分组包头的d s c p 为特定流聚集分配资源的方式。d i f f e r s e r v 体系的整体资源分配策略也就通过这个一个个单点资源分配实现的。 应该注意的是，p h b 仅是外特性描述，而不是涉及具体的实现 机制。这类似于对象封装后的外部接口描述。p h b 的实现可以用于 队列调度与缓冲管理等各种算法，如优先队列、分类队列等。多个 p h b 定义为一个p h b 组，其中每个p h b 使用同样的缓冲区管理和分 组调度机制。厂商通过对标准p h b 的组合，可以实现自已所专用的 业务。 ( 1 ) 尽力而为p h b ( b e s te f f o r tp h b ) ：b e 是缺省的p h b ，对应的是 传统的尽力而为的网络传输业务。显然任何一个d s 节点都支持b e 。 r f c2 4 7 2 规定：当d s c p 为全零( 编码点为：“0 0 0 0 0 0 ”) 时，也采用 b e 服务。b ep h b 具有最低的优先级。 ( 2 ) 快速转发p h b ( e x p e d i t e df o r w a r d i n g ，e fp h b ) ：e fp h b 描述 的是一组用于实现低丢失率、低延迟、具有带宽保证的，以及在d s 域中具有端到端服务质量保证的业务传输。被定义为e fp h b 的优先 多优先级队列管理机制研究与仿真 级最高。e fp h b 对应的d s c p 编码为：“1 0 1 1 1 0 ”。 ( 3 ) 确保转发p h b ( a s s u r e df o r w a r d i n gp h b ，a fp h b ) ：a fp h b 实 际上是一种根据相对带宽可用性和多种分组丢失优先级定义的端到 端服务的p h b 组。在业务流开始转发之前，发送方与网络节点之间 将对业务流的速率作一定的约定，这种约定称为业务流的轮廓。在 a fp h b 中，网络节点将允许业务流的速率大于这一轮廓，但是，网 络节点将对超出轮廓的业务流分组采用较大的丢弃优先级。根据这一 思想i 讧c 2 5 9 7 对a fp h b 定义了4 个服务类和3 级优先级，并用 a f x y 表示a f 服务类x 具有丢弃优先级y 。服务类提供了分组用于 选择适当的队列的依据，而每个队列的分组丢弃器则可以根据分组的 丢弃优先级来进行拥塞处理。 本文主要研究这种基于优先级( 即区分服务) 的q o s 保证策略。 1 3 2 拥塞控制 拥塞控制算法包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制 ( c o n g e s t i o nc o n t r 0 1 ) 这两种不同的机制【1 6 】。拥塞控制是“恢复”机制， 它用于把网络从拥塞状态中恢复出来；拥塞避免是“预防”机制，它 的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延迟的 状态下。根据算法的实现位置，可以将拥塞控制算法分为两大类：链 路算法( 1 i n ka l g o r i t h m ) 和源算法( s o u r c e a l g o r i t h m ) 【1 7 】。链路算法在网络 设备( 如路由器和交换机) 中执行，作用是检测网络拥塞的发生，产生 拥塞反馈信息。源算法在主机和网络边缘设备中执行，作用是根据反 馈信息调整发送速率。拥塞控制算法设计的关键问题是如何生成反馈 信息和如何对反馈信息进行响应。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是 目前在i n t e m e t 中使用最广泛的传输协议。根据m c i 的统计，总字 节数的9 5 和总报文数的9 0 使用t c p 传输。近年来，t c p 中采 用了很多新的算法，包括慢启动( s l o ws t a r t ) 、拥塞避免、快速重传( f a s t r e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应答( s a c k ) 等，大大提 硕士学位论文 高了网络传输的性能。t c p 中使用的拥塞控制算法已经成为保证 i n t e r n e t 稳定性的重要因素【1 8 l 。 链路算法的研究目前集中在“主动队列管理 ( a c t i v eq u e u e m a n a g e m e n t ，简称a q m ) 算法方面。和传统的“队尾丢弃”( d r o p t a i l ) 相比，a q m 在网络设备的缓冲溢出之前就丢弃或标记报文。a q m 的一个代表是r e d ( r a n d o me a r l yd e t e c t i o n ) 。研究表明，r e d 比 d r o p t a i l 具有更好的性能。但是，r e d 的性能对算法的参数设置十 分敏感，至今没有在i n t e m e t 中得到广泛的使用。 1 3 3 分组调度和队列管理算法 当前在分组调度和队列管理算法方面的研究很多。各种文献中 提出的分组调度算法有：p q 算法、e d f 算法、w r r 算法等：队列 管理算法主要是主动队列管理算法：r e d 算法，w r e d 算法、 r e dg e n t l e 算法等。分组调度和队列管理算法的好坏直接影响着q o s 性能指标的实现，因此在因特网中采用合适的算法是非常重要的。本 文后面的大量工作就是从这些算法着手展开的。 1 4 论文组织及主要研究内容 本文围绕区分服务( d i f f s e r v ) 体系结构下q o s 的实现方案及队列 管理算法改进所进行的研究，论文章节组织如下： 第一章在分析当前q o s 发展状况的基础上，阐述了网络的服务 质量，包括q o s 的概念、技术指标、研究状况：最后指出了本文的 主要研究内容及论文组织情况。 第二章分析了被动式队列管理的主要缺陷，并详细介绍了路由器 中的主动式队列管理算法r e d 算法及其几种典型的衍生算法，通过 各算法优缺点的分析，本章结合w r e d 算法和r e dg e n t l e 算法的优 点，在体现区分服务的基础上为了保持算法性能的强壮性特提出了 w r e d _ g e n t l e 算法。 第三章对几种分组调度算法( 基于静态优先级算法、基于时延算 多优先级队列管理机制研究与仿真 法、基于轮循算法) 进行了对比研究，分析其优缺点从而为第五章的 算法的提出奠定了坚实基础。 第四章首先着重分析了p q b e d f 算法的实现机制，并针对其存 在的不足提出了p q b e d f + 算法，此算法与w r e dg e n t l e 算法相结合， 能够实现丢弃区分和动态优先级，从而保证了不同等级业务的q o s 。 第五章首先简单介绍了o p n e t 仿真平台，然后为了分别验证 w r e dg e n t l e 、p q b e d f + 算法详细介绍了其仿真模型在o p n e t 下的 构建，最后给出了仿真环境参数，对仿真结果做出了分析。 结束语总结了本文的主要研究工作，并阐述了将来进一步的工作 计划。 最后是致谢和参考文献。 硕士学位论文 2 区分服务的队列管理机制 队列管理从狭义的角度来看仅指对网络传输节点中队列缓冲资 源的管理和分配( 即缓冲管理) 。本章将仅限于缓冲管理展开讨论，重 点分析了r e d 及其衍生算法，同时结合w r e d 与r e dg e n t l e 这两 种算法的优点提出了w r e dg e n t l e 算法，而关于此算法的验证将在 第五章中给出。 2 1 队列管理机制简介 就单个网络传输节点而言，其控制目标在于解决输出链路的带宽 资源分配问题，把有限的资源公平而有效的分配给不同的服务类型。 而在众多网络传输节点构成传输网络的基础上，网络传输控制需要整 合、规划所有的网路带宽资源的使用，为用户提供端到端的有服务质 量保证的网络传输服务，这也是q o s 控制的目标。带宽资源的分配 在网络传输节点上主要通过基于多队列的分组调度机制来实现。虽然 队列管理机制直接涉及到的是节点中的队列缓冲资源，直接影响到的 是分组丢失率性能，然而其对系统带宽分配的性能有着不可忽视的影 向： ( 1 ) 合理的队列管理机制，对于平衡系统吞吐量和分组排队延迟起 着至关重要的作用； ( 2 ) 在多队列情况下，缓冲资源在不同队列( 服务类型) 之间的分配 只有在与输出带宽的分配相互一致时，才能获得最佳的缓冲效果。 因此，我们将研究的重点放在传统上相互独立、缺乏联系的队列 管理机制与队列调度机制的结合上，研究更优的资源分配方案，以获 得最优的系统性能。如何与分组调度机制有效地结合，解决网络带宽 资源的有效、公平分配问题，是队列管理设计的关键。 目前韵队列管理机制可以分为两大类：被动式队列管理( p a s s i v e q u e u em a n a g e m e n t ，p q m ) 和主动式队列管理( a c t i v eq u e u e 多优先级队列管理机制研究与仿真 m a n a g e m e n t ，a q m ) 。 2 1 1 被动式队列管理及其局限性 管理队列长度的传统方法是对每个队列设置一个最大值( 以包为 单位、) ，然后接受包进入队列直到队长达到最大值，接下来到达的包 就要被拒绝进入队列直到队长下降。这种技术也就是传统的“去尾” ( d r o p t a i l ) 算法。由于这种方法是在队列满了之后被迫丢包，因此称 为被动式队列管理。虽然“去尾”算法在当前i n t e m e t 上得到了广泛 的使用，但其存在两个重要问题【1 9 1 ： 死锁( 1 0 c k o u t ) 现象：在某些情况下，由于同步或其他定时作用的 结果，“去尾”算法会让某个流或者少数几个流独占队列空间，阻止 其他流的包进入队列。 满队歹l j ( f u l lq u e u e s ) 问题：由于“去尾”算法只有在队列满时才会 发出拥塞信号，因此会使得队列在相当长时间内处于充满( 或几乎充 满) 的状态。而i n t e r n e t 数据的突发性使得队列在满状态下会产生 “t c p 全局同步”( t c pg l o b a ls y n c h r o n i z a t i o n ) 现象。 2 1 2 主动式队列管理简介 在当前的i n t e r n e t 上，丢包是对端节点进行拥塞通知的重要机制， 解决路由器“满队列”的方法便是在队列充满之前丢包，这样端节点 便能在队列溢出前对拥塞作出反应，这种方法便称为“主动队列管理 ( a q m ) 。 a q m 实际上是基于f i f o 调度策略的队列管理机制，使得路由 器能够控制在什么时候丢多少包，以支持端到端的拥塞控制。a q m 有以下优势： 减少了路由器中丢弃的包的数量：i n t e r n e t 中数据包的突发本 质是不可避免的，a q m 通过保持较小的平均队列长度( a v e r a g eq u e u e s i z e ) ，能提供更大的容量吸收突发数据包，从而大大减少了丢包数。 进一步说，如果没有a q m ，会有更多的包被丢弃。 硕士学位论文 对交互式服务提供了更低的延迟：a q m 通过保持较小的平均 队列长度，队列管理能够减少包的排队延迟( q u e u e i n gd e l a y ) ，而排队 延迟是造成端到端延迟( e n dt oe n dd e l a y ) 的主要原因。这对交互式应 用比如w r e b 浏览、t e l n e t 业务和视频会议等非常重要。 避免了“死锁 现象：a q m 能够通过确保到来的包几乎总是 有可用的队列空间，从而阻止“死锁”行为的发生。也因为这个原因， a q m 能防止路由器对低带宽高突发的流的偏见。 2 2 几种典型的r e d 及其衍生算法 最早的a q m 算法是由f l o y d 和j a c o b s o n 提出的影响相当广泛 的随机早期检澳, l j ( r a n d o me a r l yd e t e c t i o n ，r e d ) 算法 2 0 i , r e d 算法基于 平均队列长度预测可能到来的网络拥塞，并采用随机选择的策略对数 据分组进行标记( 或丢弃该分组，这是为了与早期t c p 协议中拥塞控 制机制相兼容) ，在拥塞尚未出现是时提示端系统降低其发送速率， 以达到避免拥塞的目的。 r e d 的各种变体形式分为四大类： ( 1 ) 单平均队列一单门限( s i n g l ea v e r a g es i n g l et h r e s h o l d ，s a s t ) ，这 就是典型的r e d 算法； ( 2 ) 单平均队列一多门限( s i n l g ea v e r a g em u l t i p l et h r e s h o l d ss a m t ) ，这种实现方式包括w r e d ； ( 3 ) 多平均队列一多门限( m u l t i p l ea v e r a g e sm l u t i p l e t h r e s h - - o l d s ，m a m t ) ，这种实现方式包括0 c ； ( 4 ) 多平均队列一单门限( m u l t i p l ea v e r a g e ss i n g l e t h r e s h o l d ，m a s t ) 。 其中除m a s t 以外，s a s t 、s 蝴t 以及m a m t 都在实际 中有应用。s a s t 方式无法实现服务区分。在d i f f s e r v 网络中可以采 用s a m t 、m a m t 这两种m r e d 方式。 多优先级队列管理机制研究与仿真 2 2 1r e d 算法 ( 1 ) r e d 算法的实现机制 r e d 算法主要包括两步，首先计算平均队列长度，然后计算丢 弃包的概率。在分组到达时，r e d 算法采用指数加权平均算法计算 系统的平均队列长度，作为拥塞预测的依据，并依此计算该分组的标 记( 或丢弃) 概率。平均队列长度的计算公式如下： a v g q = ( 1 一w q ) x a v g q + w qx q公式( 2 - 1 ) 其中q 为当前队列长度，w q 为当前队列长度加权系数，满足 0 w 。 1 ，a v g q 为平均队列长度。从公式( 2 一1 ) 中可以看出，r e d 算法 采用平均队列长度作为判断是否拥塞的依据，其中w a 参数一般设置 得较小( 在实际应用中一般取w q 为0 0 0 2 ) ，使得平均队列的长度变化 得很缓慢，这样平滑了突发流量到来时对算法的影响。在r e d 中， 还引入了两个与队列长度有关的重要参数m i n t h 和m a x t h ，当平均队列 长度a v g q 小于最小阈值m i n t b ，则没有分组丢弃；当a v g q 超过最大 阈值m a x t h 时，所有到达的分组都被丢弃；当a v g q 在m i n t h 和m a x t h 之间时，将依据一定的概率标记( 或丢弃) 到达的分组，标记( 或丢弃) 概率的计算公式如下： 只= m a x 。( a v g q r f f m 晴) ( m a x 抽一m i n 伪)公式( 2 2 ) 其中m a x p 是预先设置的标记概率，p b 为当前分组标记概率的计 算值，如图2 1 所示。 m a x p m m t hm a x t h q u e u e _ a v g 图2 - 1 平均队长和丢包概率的关系 从公式( 2 2 ) 中可以看出，r e d 算法的标记概率随平均队列长度 的变化满足分段线性关系。在算法的实际实现中，为了使被标记的分 硕士学位论文 组散布得更均匀，对标记概率p b 作出如下修正以得到p a 作为实际标 记概率： 只= 忍( 1 一c o u n t x p b )公式( 2 3 ) 显然p a 不仅和a v g q 有关，而且还和从上一次丢包开始到现在进 入队列的包的数量c o u n t 有关。随着c o u n t 的增加，下_ 个包被丢弃 的可能性也在缓慢增加。这主要是为了在到来的包之间均匀间隔地丢 包，避免连续丢包，从而避免了对突发流的偏见和产生全局同步现象。 r e d 算法可以简单地描述为： f o rp a c k e t _ a r r v i a l p a c k e t _ a c c e p t = f a l s e ； c a l c u l a t ea v g q ；产计算平均队列长度木 i f ( a v e q m i n t h ) p a c k e t _ a c c e p t - - - - t r u e ； e l s ei f ( m i n t h 冬a v g q p ) p a c k e t _ a c c e p t - - t r u e ； e l s e d i s c a r dp a c k e t _ a r r v i a l ；) ) e l s ei f ( a v g q m a x t h ) d i s c a r dp a c k e t _ a r r v i a l ；) ( 2 ) r e d 算法优缺点分析 r e d 算法在拥塞发生之前通知发送方调整速率，通常能够有效 地降低丢包率；r e d 随机通知发送方而不是通知所有发送方，能够 有效地消除全局同步；r e d 在平均队长超过了最大阈值后就丢包， 从而有效地控制了平均队长，限制了平均时延的大小；r e d 还可以 通过保持较小的队列长度来容纳突发的数据流。虽然r e d 能够有效 多优先级队列管理机制研究与仿真 避免拥塞，但是该算法仍然存在以下不足： 对控制参数过于敏感，难以优化参数设定。 不支持服务区分，基于b e s t e f f o r t 服务模型，没有考虑不同 等级服务之间、不同用户流之间的差别，无法提供有效的公平性保障。