（计算机软件与理论专业论文）基于网络qos的队列调度算法研究.pdf

硕士论文 基于网络q o s 的队列调度算法研究 摘要 近年来，随着因特网各种传输服务业务的迅猛增长，人们对互联网服务质量保证 技术的研究非常活跃，涉及到的关键技术主要包括网络的资源分配和业务控制。本文 主要研究高速互联网中的队列调度算法及其流量控制技术。队列调度算法属于资源分 配技术的一种，负责对链路带宽的资源进行分配和管理。流量控制技术则是对业务流 进行控制，进一步提高业务q o s 控制方面的能力和性能。 本文首先论述了在当今因特网上的q o s 研究现状及有待解决的问题。然后对队 列调度技术的相关研究内容进行了较为详细的介绍，包括队列调度算法的技术指标和 常见队列调度算法的分类、比较、分析等。 基于对队列调度算法的介绍和分析，本文从队列的优先级角度入手，对数据结构 中经典的二进制堆调度算法进行了改进( h e a p + ) ，使之能通过流水线操作达到高度 的并行性，且具备很高的资源利用率和可扩展性，可用于高速链路上高精度虚拟开始 时间的排序操作。 拥塞控制与队列调度技术紧密相连，对此，本文详细分析了主动队列管理中的 r e d 算法及其衍生算法，指出了它们的优缺点。针对r e d 算法进行了改进( 立方 r e d 算法) ，而且通过n s 2 仿真软件加以证明，该算法能较好地减少流传输过程中 的丢包率，增加数据流的吞吐率。 最后，对本论文所做的工作加以总结，并提出今后努力的方向。 关键词：服务质量，队列调度算法，二进制堆排序， 拥塞控制，随机早期检测 硕士论文基于网络q o s 的队列调度算法研究 a b s t r a c t w i t ht h ei n c r e a s e so fd i f f e r e n tt r a n s m i s s i o ns e r v i c ec l a s s e s ，i pq o si sb e c o m i n gah o t t o p i ci nr e s e a r c ha n di n d u s t r yc o m m u n i t yi nr e c e n ty e a r s t h ek e yt e c h n o l o g i e si n v o l v e di n t h i ss u b j e c ta r en e t w o r kr e s o u r c ea l l o c a t i o na n dt r a f f i cc o n t r 0 1 t h i st h e s i sw i l ls t u d yq u e u e s c h e d u l i n gs c h e m ea n df l o wc o n t r o li nh i g h - s p e e di n t e r n e t a sak i n do f n e t w o r kr e s o u r c e a l l o c a t i o nt e c h n o l o g y , q u e u es c h e d u l i n gi so f i g l lu s e dt oa l l o c a t et h el i n kb a n d w i d t h f l o w c o n t r o li su s e df o rh a n d l i n gt h e 触cf l o w sa n do b t 蛐m o r eq o sg u a r a n t e e c a p a b i l i t i e s f i r s t ，t h er e s e a r c he x i s t i n gc o n d i t i o na n da no p e nq u e s t i o nh a v eb e e nd i s c u s s e di nt h e i n t e r a c tq o s a n dt h e n , c o r r e l a t i o ns t u d yc o n t e n t so fq u e u es c h e d u l i n gs c h e m ea r e d e t a i l e d ，i n c l u d i n gt e c h n i c a lt a r g e t so f t h eq u e u es c h e d u l i n ga l g o r i t h m ，a sw e l la si n c l u d i n g c l a s s i f i c a t i o n 、c o m p a r i s o na n da n a l y s i so f f a m i l i a rq u e u es c h e d u l i n ga l g o r i t h m b a s e d0 1 1t h ea b o v e - m e n t i o n e da n a l y s i s ，t h i sp a p e ri m p r o v e st h ec l a s s i c a lb i n a r yh e a p s c h e d u l i n ga l g o r i t h mo f d a t ab t i u c t u r ef r o mt h ep r i o r i t yp e r s p e c t i v eo f t h eq u e u e w e c a l li t h e a p + t h i ss c h e m ee n a b l e st h ep i p e l i n i n go ft h ee n q u e u ea n dd e q u e a eo p e r a t i o n st o r e a c hv e r yp a r a l l e f i s m a tt h es a n l et i m ei th a sv e r ya v a i l a b i l i t yo fr e s o u r c e sa n d e x p a n d a b i l i t y i t i s u s e d i n t a x i s o p e r a t i o n o f v i r t u a ls t a r t i n g t i m e w i t h v e r y p r e c i s i o n o n t h e h i g h - s p e e dd a t al i n k c o n g e s t i o nc o n t r o li sc o m p a c tw i t hq u e u es c h e d u l i n ga l g o r i t h m t h i sa r t i c l ea r g u e s a b o u tt h er e da n di t sd e r i v a t i v ea l g o r i t h m s ，a n dt h e np o i n t so u tt h o rr e l a t i v em e r i t sa n d f a u l t s b a s e do nt h er e da l g o r i t h m ，t h ec u b i cr e di sp u tf o r w a r d t h ec u b i cr e dc a n r e d u c et h ed r o p - r o t eo ft h ed a t af l o we f f e c t i v e l ya n di n c r e a s et h et h r o u g h p u to ft h ed a t a f l o ww h i c hm a yb ep r o v et h r o u g ht h es o f t w a r en s - 2 f i n a l l y , t h ep a p e rs u m m a r i z e sw i t ht h er e s e a r c hw o r ka n dp u t sf o r w a r dt h ed i r e c t i o no f s t r i v i n gt ot h er e s e a r c hi nt h ef u t u r e k e y w o r d s ： q o s ，q u e u es c h e d u l i n ga l g o r i t h m ，b i n a r yh e a po r d e r ， c o n g e s t i o nc o n t r o lr e d 硕士论文 基于网络q o s 的队列调度算法研究 q o s f c f s w f q w f 2 q + i n t s e r v d i 妇c s e r v l 峪v p t d s s l a p h b d s i s p l i 塔 r s t g p s r r p g p s d r r w r r s f f s e f f c b r r e d r e m p q s f i w f i p f q e w m a d s c p 缩略词 q u a l i t yo fs e r v i c e ，服务质量 f i r s tc o m ef i r s ts e r v i c e ，先到先服务 w e i g h t e df a i rq u e n e i n g ，加权公平排队 w o r s tc a s ef a i rw f q ，最差情况公平加权公平排队算法 i n t e g r a t e ds e r v i c e ，综合服务 d i f f e r e n t i a t e ds e r v i c e ，差分服务 r e s o u r c er e s e r v a t i o np r o t o c o l ，资源预留协议 t y p eo fs e r v i c e ，业务类型 s e r v i c el e v e la g r e e m e n t ，业务等级约定 p e rh o pb e h a v i o r ，每一跳行为 d i f f e n e n t i a t e ds e r v i c e ，差分服务 i n t e r n e ts e r v i c ep r o v i d e r ，互联网业务提供商 l a t e n c yr a t es e r v e r ，时延速率调度器 r a t es p a c e dt h n e s t a m ps c h e d u l e r ，速率分隔时间标签调度器 g e n e r a l i z e dp r o c e s s o rs h a r i n g ，广义处理器共享 r o u n dr o b i n ，循环 p a c k e t - b y - p a c k e tg p s ，基于分组的广义处理器共享 d e f i d tr o u n dr o b i n ，差额循环 w e i g h t e dr o u n dr o b i n ，加权循环 s m a l l e s tv i r t u a lf i n i s h i n gt i m ef i r s t ，最小虚结束时间优先 s m a l l e s te l i g i b l ev i r t u a lf i n i s h i n gt i m ef i r s t ，最小资格虚时间优先 c o n s t a n tb i tr a t e ，恒定比特率 r a n d o m e a r l yd e t e c t i o n ，随机早期检测 r a n d o me x p o n e n t i a lm a 凼n g ，随机指数标记 p r i o r i t yq u e u e i n g ，优先级排序 s e r v i c ef a i r n e s si n d e x ，服务公平指数 w o r s tc a s ef a i r n e s si n d e x ，最坏公平指数。 p a c k e tf a i rq u e n e i n g ，分组公平排队 e x p o n e n t i a lw e i g h t e dm o v i n ga v e r a g e ，指数加权滑动平均 d i f f e r e n t i a t e ds e r v i c e sc o d e p o i n t ，区分服务标记 v 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：年月 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：年月 日 硕士论文 基于网络q 娼的队列调度算法研究 1 绪论 1 1 网络q o s 的综述 自从计算机系统诞生开始，就一直存在着提高系统的服务性能和服务质量的问 题。因此，计算机系统的q o s 问题由来已久。 1 1 1q o s 的定义 从一般质量的角度来看，网络服务质量可以认为是使用网络提供服务的容易程度 以及它的统一性。在因特网中，它的基本特性是被指定的两点之间提供具有尽力( b e s t e f f o r t ) 质量的传输服务。也就是说数据将被送到所希望的地方，基本服务是连通性服 务，除此之外并无其他规定。因此，在因特网中路径的传输速率、可靠性( 误码率1 、 延迟等都是服务质量的要素。也就是说，因特网的q o s 1 】是指某个主机上的应用向其 它主机上的应用发出一连串的数据包时的平均速率、最大速率( p e a kr a t e ) 、数据包的 延迟时间、抖动( j i t t e r ) 、数据包的损失等。 但是这些值并不是只从网络的结构上就能确定的，它具有受流入网络中的通信量 影响的特性。就拿类似的高速公路做个比喻。高速公路上的质量应该是时速每小时多 少公里，以及从某地到某地所需的时间。仅靠公路的结构值是不可能预测公路的质量 的。它与汽车通过的流量有着紧密的关系，而且这些值的预测是很困难的，几乎是不 可能保证的。很多人使用的因特网也是同样的情况。比如，如果有人对流入的通信量 加以制约，就不可能预测和控制网路内的延迟。不仅使自己的通信量由于线路速率、 误码率和延迟等的改变而发生变化，还会使别人的通信量也受到同样的影响。 因此，只给出网络结构然后预测其质量或者指定因特网质量值来设计满足需要的 网络都很困难。由于这个原因，对因特网的q o s 的实际业务的定义是很难的，在实 际情况中已有很多种对q o s 的解释。表1 1 1 就是各种对q o s 的定义【2 】。 文献【3 】中描述：q o s 是网络在传输数据流时要求满足的一系列服务请求，具体 可以量化为带宽、延迟、延迟抖动、丢失率、吞吐量等性能指标。此处的服务具体是 指数据包( 流) 经过若干网络节点所接受的传输服务，强调端到端( e n d - t o - e n d ) 或 网络边界到边界的整体性，q o s 反映了网络元素( 例如：应用程序、主机或路由器) 在保证信息传输和满足服务要求方面的能力。 硕士论文 基于网络q o s 的队列调度算法研究 表1 1 1 各种i p q o s 定义的列表 q o s 概念 覆盖范围特点 研究范围主要局限于t c p i p 协议栈的m 层， 没有从整个网的角度去分析问题。另外，目前 i e t f 在提供q o s 方面的几乎所有研究都仅仅局 1 f 口层 限于单个网络而不是多个网，自治域，也就是说， i e t f 还没有跨过多个网保证端到端q o s 的清晰 的技术路线。 网络中的各个运 从整个运营商的角度出发，直接面向网络中 玎1 加! t s i 的各个运营实体( 用户、s p ，n p 等) ；在实际应 营实体 用中通常需要更为深入的技术层面的支撑。 o s i 网络某型的是一种理论模型。其逻辑抽象层次较高，需 各个协议层次之间、要对具体网络进行功能化，通常不能直接应用到 i s o 多个协议栈的对等协具体的网络中 议层之间。 q o s 控制的目标是为i n t e m e t 应用提供服务区分和性能保证；服务区分是指根据 不同应用的需求为其提供不同的服务；性能保证则要解决诸如带宽、丢失、延迟、延 迟抖动等性能指标的保证问题。然而，在网络中，特别是在i n t e r n e t 这样大规模的全 球网络中提供q o s 绝非易事，它需要自顶向下所有网络层( 即i s o o s i 模型中的第1 层第7 层) 以及端到端( 即从信息的发送者到接收者) 的所有网络元素的整体协作。 1 1 2q o s 的技术特征 最近随着q o s 技术的进步，如果给予因特网的结构和流入因特网的通信量双方 某种制约时，网络的操作是可以预测的。对于研究者来说，q o s 技术是指可以预测网 络操作的方法。表1 1 2 给出了q o s 的技术特征【4 】。 2 硕士论文 基于网络q o s 的队列调度算法研究 表1 1 2 基于技术的q o s 特征 种类参数说明 时延传输一个分组的时间 时间 时延抖动传输时间的变化 响应时间发送请求到收到响应的往返时间 系统级速率 可用的带宽( b y t e s ) 带宽应用级速率 可用的带宽( 帧，s ) 传输速率每秒传输的数字信号速率( b s ) 平均运行时间( m t r f ) 正常运行的时间 平均修复时间( m t t r )出现故障的时间 可靠性 平均故障间隔时间( m t b f )m n f 司肼+ m 珊t 可用时间率m r n m t b r 丢失率或出错率丢失或没有正确接收的分组率 1 1 3q o s 的描述 q o s 描述是为了精确地表达用户应用的q o s 要求和管理策略。系统不同层次的 q o s 描述通常是不同的，分别用于配置和维护该层次的q o s 控制和管理机制。例如， 应用层的q o s 描述主要是面向用户而不是面向系统的，而较低层次的相关考虑，如 线程调度的细节，应该被应用层的q o s 描述隐藏。从用户应用的角度来看，q o s 描 述应该包含以下几个方面： ( 1 ) 信息流特征 它描述了用户应用的信息流量特征，如信息流产生的峰值速率和平均速率、信息 流的突发长度以及平均周期等。信息流特征描述是综合服务网络系统为用户应用分配 和管理资源的依据，也是用户应用向网络系统所作的承诺。 ( 2 ) 信息流性能要求 它描述了多媒体应用对网络性能的要求，如网络系统的吞吐量、信息的延迟、抖 动以及丢失率等。不同多媒体应用对网络性能的要求是不同的，为了进行相应的端系 统和网络资源分配，综合服务网络必须提前了解应用对网络性能的要求。 ( 3 ) 信息流同步要求 它描述了应用多个相关信息流之间的同步程度。例如，同时记录的视频图像必须 被精确地一帧帧同步播放，以便有关的特征能够被同时观察到。当然，在播放多媒体 视频时，如果主要关注声音，而视频图像只是为了增强表示效果，那么声音与图像流 硕士论文 基于网络q o s 的队列调度算法研究 之间的纯同步也就不需要绝对精确了。 ( 4 ) 服务层次( 1 e v e lo f s e r v i c e 。l o s ) 它描述了端到端q o s 担保的程度，如可控负载型服务、保证型服务以及尽力而 为型服务。尽管信息流性能要求的描述允许用户以量化的方式表达所要求的性能尺 度，然而服务层次描述能够对这些要求做质的提炼，以便区分出哪些要求更强烈，哪 些要求不那么强烈，从而使系统能够更细致地分配和调度资源，使综合服务网络的总 体用户满意度最佳。服务层次描述也有助于系统在资源紧张或不足时采用更灵活有效 的q o s 控制策略。 ( 5 ) q o s 管理策略 它描述了当系统承诺的应用q o s 不能达到时，应用能够忍受的q o s 降级的程度 以及可被采用的管理行为。例如，当网络系统因为某些原因无法满足多媒体信息的延 迟要求时，通过对可得到的带宽做时间和空间质量的折中，或者操纵连续媒体的播放 时间，最大可能地减少音频和视频流在播放设备上产生的失真，使得感觉仍可接受。 q o s 管理透视图也包括用户层的q o s 降级指示以及周期性的带宽、延迟、抖动以及 丢失率的通知。 ( 6 ) 服务成本( c o s to f s e r v i c e ，c o s ) 它描述了用户对所要求的服务愿意付出的成本。服务成本是q o s 描述中非常重 要的一个方面，设想一下，如果在q o s 描述中不包含服务成本的描述，那么用户将 没有任何理由不去选择最高层次的服务。 1 , 2 队列调度算法的重要性和研究意义 1 2 1 网络节点中q o s 实现的简单模型 图1 2 1 所示是一个简单的q o s 模型i s ，其中包括分类模块、输入控制模块、排 队队列模块、队列调度模块和队列管理模块。分类模块完成了对进入网络节点分组的 分类和标记的任务。输入控制模块对进入队列的分组进行严格的检查，确保其流量符 合约定。排队队列模块负责分组在缓冲区存储。队列调度模块对分组进行调度，使其 规则的进入输出链路。队列管理模块的主要工作是监视排队缓冲区的状况，确保到达 分组不会导致缓冲区的溢出。 4 硕士论文基于网络q o s 的队列调度算法研究 输 入 控 制 图1 2 1 网络节点q o s 实现模型 1 2 2队列调度算法的研究意义 网络q o s 控制的本质在于资源的管理，即控制缓冲队列、链路带宽等网络资源 的分配和使用。队列管理在网络传输控制中发挥着相当大的作用，是网络服务质量 ( q o s ) 控制的核心技术之一，也是实现网络拥塞控制的重要手段。q o s 控制算法的 设计需要满足一定的性能要求，而系统性能的好坏是针对一定的性能评价标准而言 的，应用不同的评价标准往往会导致不同的评价结果和q o s 控制方案设计。不论在 i n t s e r v 还是在d i f f s e r v 里，都涉及队列调度问题。简言之，队列调度的功能就是路 由器如何从一个或多个队列中选择下一个将要转发的分组，这与队列管理机制有着本 质的区别。一个有效的队列调度算法应达到的性能指标有：公平性、时延特性、对恶 意业务流的隔离能力、链路带宽的利用率、复杂性等。前4 个指标与q o s 密切相关。 在队列调度算法研究中，如何提供较好的公平性、时延特性，同时算法复杂度较 低且易于实现的特性成为人们关心的焦点，所以开展对这一方面的研究具有较高的研 究价值和实际意义。 1 3国内外现状和研究内容 对q o s 的研究历史可以追溯到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 通信时已提出基于用户的性能评 价问题1 6 j ，这也许是关于q o s 研究的最早的文献。早期的o s i 协议的制定中，也为 服务质量的一些参数留有相应的表示手段，但一直空缺未用研。很长的一段时间内， 由于计算机网络的性能尚未达到一定水平，人们对q o s 的关注只是停留在数据流传 输中的正确率、吞吐量和延迟等单一服务质量的评价和控制【羽。直到8 0 年代末期， 5 硕士论文 基于网络q o s 的队列调度算法研究 宽带i s d n 技术以及a t m 交换网的出现和分布式多媒体应用的急剧增加，人们才开 始系统地对q o s 管理和控制进行了较为深入的研究。经过几年的努力，对q o s 的研 究逐渐集中到q o s 控制和管理框架、q o s 定义和标准、q o s 主客观方法的统一网，以 及q o s 中的市场机制等焦点上。一些实验性系统也应运而生，较有代表性的有英国 兰开斯特大学的q o s - a 工程【1 0 】、美国哥伦比亚大学的扩展的集成化参考模型( x r m ) 系统、国际合作项目t i n a - c 工程0 2 1 、美国加州伯克利大学的t e n e t 工程t 1 3 1 、i b m 公司在黑森伯格欧洲网络中心的h e i p r o j e c t 工程【1 4 】等。与此同时，随着因特网商业化 的巨大成功，双上传输的多媒体信息迅速增多，网络拥塞现象日益严重，因特网的 q o s 研究也随之开始深入，i e t f 于1 9 9 7 年9 月开始制定了有关q o s 定义与服务的 一系列r f c 标准。国内也于近几年开始了有关q o s 控制方面的研究，东南大学顾冠 群院士的研究小组在实时协议r t p 的实现、q o s 的定义与机制等方面做了许多深入 细致的工作u 5 l 【l 们。清华大学计算机系的研究小组则在日本富士通研究所、m i t 计算 科学研究所等的支持下，也开始了t h q o s 工程的研究【l7 。2 0 】。目前，计算机网络的 q o s 问题已经成为国际研究领域公认的最重要、最富有魅力的研究领域之一，并且被 称为下一代计算机网络为数不多的最重要的研究领域之一。 众所周知，服务质量已成为当今网络发展的一个重要课题，网络中的服务是面向 不同的用户的，提供包括及时性、准确性和高效率几个方面的服务质量。然而传统尽 力而为型的网络不能够很好提供这些方面的服务，所以如何有效的提高和改善网络中 的服务质量这一问题，各种方面的解决方案层出不穷，如流分类、链路技术、路由协 议等等。在这其中，比较行之有效且被大家所公认的一种解决方式就是调度算法。 调度算法决定了被服务的分组接受服务的顺序，使其所在的数据转发设备能够智 能的控制数据转发的优先级，每条链路的带宽以及平均时延等特性以满足一定程度上 的服务质量。 调度算法的研究由来已久，随着网络规模的膨胀以及人们对业务种类和质量要求 的上升，调度算法已经成为众多网络工程师所面临的一个重要难题。 当前调度算法的发展的趋势基本分为3 种：分组公平排队类调度算法、轮循类调 度算法和服务曲线类调度算法。公平类调度算法最早来源于对g p s 流体模型的研究， 其后衍生出多个不同的算法，其中以h u i z h a n g 等人的w f 2 q 最具有代表性，他们还 提出了若干种适用于p f q 算法中减少算法复杂度的方法，这些方法有的已经被成功 的用于商业交换网片中。轮循类算法是一类比较简单的算法，虽然公平性不如p f q 算法，但是算法的简单性却是其在硬件实现上的最大优势所在。这其中具有代表性的 算法有w r r 、d r r 、u r r 等。而服务曲线类算法又是另一种与前两者完全不同的算 法，它从去耦时延与带宽的角度出发，解决了如何同时获得低时延和低带宽的问题。 这其中具有代表性的算法有最早期限优先( e a r l i e s td e a d l i n ef i r s t , e d f ) 算法、 6 硕士论文基于网络q o s 的队列调度算法研究 s c e d ( s e r v i c ec u r v e b a s e de a r l i e s td e a d l i n ef l s t ) 和h f s c 算法。 通信网络正朝着宽带化、综合化和数字化的方向发展，链路的速率越来越快，网 络中需要承载的业务也呈现多样化，包括语音、数据、图像，而且不同的业务有不同 的q o s 要求，这就要求网络交换节点能对其输入业务进行快速、有效和合理的调度， 以尽量满足不同业务的不同需求。 调度是系统资源管理的核心机制之一，是解决多个业务竞争共享资源问题的有效 手段。管理系统资源大致包含三个部分：缓冲区、链路带宽、处理机资源。对队列调 度的研究主要从以下三个方面来研究： ( 1 ) 缓冲管理是对网络传输节点中队列缓冲资源的管理。 在缓冲管理中，如何设置合适的队列缓存空间容量，如何在网络运行期间合理地 控制队列长度的动态变化，以平衡系统吞吐量和分组排队延迟之间的矛盾，是缓冲管 理乃至整个网络q o s 控制需要解决的重要问题。 缓冲管理的控制策略有资源管理策略( 包括完全划分策略、完全共享策略、部分 共享策略) 和分组丢弃策略( 包括随机丢弃、选择性丢弃、非参数控制丢弃等) 两种。 缓冲管理的典型算法是r e d 及其衍生算法、a v q 算法、成比例丢失率控制算法等。 缓冲管理的研究方向有：1 ) 基于流量预测提高系统资源利用率。2 ) 与分组调度 相结合融入带宽分配。3 ) 队列长度的控制与维护。 ( 2 ) 用分组调度实现对链路带宽的管理。 分组调度是指按照一定的规则来决定从等待队列中选择哪个分组进行发送，使得 所有输入业务流能够按照预定的方式共享输出链路带宽。分组调度的算法很多，但基 本过程都是根据一定的系统信息做出判断，控制各个队列占用链路带宽的频率，进而 影响时延、丢失等服务质量空间状态。一般来说，考虑的信息越多，算法越有效，复 杂性也就越高。先进的队列调度算法都是把分组存到不同的队列里，然后为其计算一 个动态优先级作为控制参数，根据这些参数进行调整。 未来网络有两个发展趋势：带宽高速化和业务多样化。分组调度算法的研究要适 合这些发展趋势，既要保证高的分组调度速率，又要提供时延等服务质量和公平性保 证。即在追求简单性和易实现性的同时，考虑算法的综合性能。 ( 3 ) 对于处理机资源的管理涉及到系统实现方面的内容。 现在，大部分商用网络处理器系统是一个典型的多r i s c 内核的并行处理系统， 同时存在着大量共享资源，如共享存储器、共享内存和协处理器等，依据系统特性对 处理器、存储器等共享资源的有效调度已经成为当前的热门课题。特别是围绕着处理 器所展开的负载平衡和处理器调度算法的研究更为突出。 7 硕士论文 基于网络q o s 的队列调度算法研究 1 4论文所做的工作及论文结构 本文的结构安排如下： 第一章绪论，介绍了网络o o s 的基本概念、网络q o s 和队列调度算法的联系及 研究意义，讨论了目前在此课题上国内外研究的基本现状，最后是本文所做的主要贡 献和论文结构。 第二章将给出全文的相关技术研究背景理论，主要包括队列调度技术、流量控制 和拥塞控制技术的讨论、比较和分析。首先是对队列调度算法的综述和分析，然后是 流量控制和拥塞控制方面的归纳讨论。 第三章集中讨论了国内外己知的主要队列调度算法，并对这些算法的性能进行深 入分析。 第四章针对基于二进制堆的队列优先级调度算法进行研究，并在此基础上对算法 进行了改进( h e a p + ) ，使之可以进行流水化。 第五章对主动队列管理算法中的r e d 算法进行了研究，分析了它的工作原理和 不足之处，提出了立方函数r e d 算法，并在n s - 2 环境下进行仿真说明。 第六章是工作总结与展望，对全文进行总结，指出目前在研究中还存在的一些 问题和不足，并给出了下一步可能的研究课题和相应的一些设想。 8 硕士论文 基于网络q o s 的队列调度算法研究 2 队列调度算法的基本理论 本章主要对全文的研究背景做一个较为全面地介绍，力求对各研究主题的现状做 较为深入地分析讨论。首先给出队列调度算法的相关研究背景，对其目前的相关算法 进行了分析和比较，指出了其研究现状和存在的问题。然后给出了流量和拥塞控制方 面的相关研究背景，也包括研究现状和存在的问题。 2 1q o s 的服务模型和平面机制 为满足i n t e r a c t 上多种业务对q o s 的需求，i e t f 先后制定了两种q 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 ) 【2 l 】和区分服务( d i f f e r e n t i a t e ds e r v i c e s ， d i f f s e r v ) 吲，用来在不同场合提供相应的质量保证。 ( 1 ) i n t s e r v 综合服务 综合服务由i e t f 的i n t s e r v 工作组于1 9 9 4 年提出，它定义了三种服务类型： 1 ) 、g u a r a a t e d ( 质量保证型) ，可以提供虚链路服务，对带宽、时延和分组丢失提供 端到端定量的q o s 保证；2 ) 、c o n t r o l l e dl o a d ( 可控负载型) ，给用户提供一种类似 在网络轻负载、无阻隔情况下尽力而为的网络服务，它是一种定性的指标；3 ) 、b e s t e f f o r t ( 尽力而为型) ，即传统m 网络上提供的服务，是一种尽力而为的工作方式，没 有q o s 保证。 i n t s e r v 主要引入了一个重要的网络控制协议r s v p ( 资源预留协议) 。r s v p 的引 入使得m 网络为应用提供所要求的端到端的q o s 保证成为可能。i n t s e r v 尽管提供 q o s 保证，但其扩展性差。因为其工作方式是基于每个流的，这就需要保存大量的与 分组队列数成正比的状态信息。此外，r s v p 的有效实施必须依赖于分组所经过路径 上的每个路由器。在骨干网上，业务流的数目可能很大，因此要求路由器的转发速率 很高，这使得i n t s e r v 难子在骨干网上得到实施。目前的解决方案是在边缘网络实施 i n t s e r v ，或者粗化业务流的定义以使业务流的数目降低到可以承受的地步。 ( 2 ) d i f f s e r v 区分服务 m t f 在r f c 2 4 7 5 中提出d i f f s e r v 体系结构，旨在定义一种能实施q o s 且更易 扩展的方式，以解决i n t s e r v 扩展性差的缺点。d i f f s e r v 简化了信令，对业务流的分 类颗粒度更粗。d i r s e r v 通过汇聚( a g g r e g a t e ) 和p h b ( p e rh o pb e h a v i o r ) 的方式提供 q o s 。汇聚是指路由器把q o s 需求相近的业务流看成一个大类，以减少调度算法所处 理的队列数。p h b 是指逐跳的转发方式，每个p h b 对应一种转发方式或q o s 要求。 由于d i f f s e r v 采用对数据流分类聚集后提供差别服务的方法实现对数据流的可预测 9 硕士论文 基于网络q o s 的队列调度算法研究 性传输，所以对q o s 的支持粒度取决于传输服务的分级层次，各网络节点中存储的 状态信息数量仅正比于服务级别的数量而不是数据流的数量，因此d i f p 3 e r v 获得了良 好的扩展性，且便于实现。区分服务体系结构的框架如图2 1 1 所示。 图2 1 1 区分服务体系结构的框架示意图 综合服务模型很有可能因为伸缩性的问题，无法在w a n 上使用。将来区分服 务模型，在q o s 方面很可能占有主导地位。事实上，很多i s p 期待区分服务模型能 够满足他们所有的q o s 需求。而与此相反的是，综合服务模型能够在企业网中实施， 很多企业的联网产品中都已经或即将集成某种程度的综合业务能力。如果广域网用的 是区分型服务模型，而局域网用的是综合业务和区分业务模型的混合形式，那么当发 送者和接收者之间的通路同时需要局域网和广域网时，如何才能够保证端到端的q o s 呢? i e 盯建议了两种互操作方式。一种方法是将综合业务覆盖在区分业务网上， r s v p 信令完全透明的通过区分业务网。位于两种网络边缘的设备处理r s v p 消息， 并且根据区分业务网络中合适资源的可用性提供许可控制。另外一种方法是简单的并 行处理。区分业务网中的每个节点可能也是具有r s v p 功能的。采取一些策略决定哪 些包使用r s v p ，哪些包使用区分业务处理。这种模型可能适用于小型网络。 ( 3 ) q o s 的平面机制 规范的q o s 体系结构框架中定义的构件模块可分为3 种类型嘲，并形成3 个相 互独立但有机关联的平面：控制平面、数据平面和管理平面。控制平面内包含了一系 列与用户流量传播路径相关的控制机制，这些控制机制包括接纳控制、q o s 路由和资 源预留等；数据平面内包含的是直接涉及用户流量的控制机制，包括缓存管理、拥塞 避免、分组标记、排队和调度、流量分类、流量管理和流量整形；管理平面内包含的 机制涉及网络运营、管理等方面，包括服务等级协议、流量恢复、流量计量和测量、 策略管理等。 除了各平面内所含的控制机制外，还需要用于在网络节点间交互信息的信令机 1 0 硕士论文 基于网络q o s 的队列调度算法研究 制。根据节点所处的网段不同，信息交互可以在端节点与端节点、端节点与边缘节点、 边缘节点与边缘节点、或网络与网络之间进行。信息交互可以发生在上述三个逻辑平 面中的任何一个。当发生在控制平面或管理平面时，信息交互必须采用特定的信令协 议。 2 2 队列调度算法的基本思想及相关理论 广义上的调度指的是对任务、工作、资源等进行适当分配和规划来满足预定的 目标。一个完整的调度系统一般包括四个元素：被调度对象、调度者、调度目标、调 度规则( 也可称为调度机制或调度算法) ，如图2 2 i 所示。调度者通过一定的调度规 则对被调度对象进行调度，以力求满足特定的调度目标一反映调度者和被调度对象 的一些需求。可以看出，调度算法实际上也是个最优化问题。根据实际的调度结果 和预定的调度目标，调度者可以调整调度机制。一个调度系统的关键在于：1 ) 调度 机制的生成一即根据预定的调度目标和( 或) 实际的调度结果找到合适的调度机制 和规则；2 ) 调度机制的执行旨调度者如何有效地把生成的调度机制施加于被调 度对象，以期得到一定的调度结果。在计算机网络和实际生活中存在许多这样的调度 系统，比如：一个公司或者单位里现金的调度、电力系统电能的分配和调度、计算机 操作系统中进程和内存的调度等。 图2 2 1 调度系统组成元素 为了给不同的业务提供不同的服务质量保证，通常在网络节点把业务放到不同的 队列里，再利用不同的调度规则( 比如：先进先出、优先级调度、轮询调度、处理器 共享、随机调度等) 对业务队列进行调度，这就是队列调度技术所要完成的工作。队 列调度技术能够给业务提供带宽和调度时延等方面的q o s 保证，它还应该能够隔离 恶意业务流，提供业务之间公平性的保证，间接达到流量控制和拥塞控制的作用。在 硕士论文 基于网络q o s 的队列调度算法研究 高速分组交换网络中，队列调度算法根据交换机或者路由器排队方式的不同主要分为 两大类：输出排队队列调度算法和输入排队队列调度算法。目前，输出排队队列调度 算法在公平性、时延特性和算法复杂性方面很难达到完美的统一；而输入排队队列调 度算法则很难同时保证业务q o s 、公平性和算法的可扩展性。本文主要研究输出排队 队列调度算法( 图2 2 2 ) ，当然输出排队机制也可以很容易地应用到输入排队中以提 高更灵活的q o s 保证。 g ， 。f 、i ji 、 ( 剡啪翱8 出缴ll ： q 丽i 丌r 几7 v 图2 2 2 输出调度 输入业务到达节点后，分别暂存到相应的队列中，假设总共有n 个队列，队列 调度算法的任务是如何从n 个队列中选择下个要传输的分组。当一个分组到达网 络节点后，分类器根据分组( 或业务流) 的上下文和粒度确定它所在的队列，分组进 入相应队列排队等候，直至调度时将其选择发送。 在i n t e r n e t 中，可以基于p 源目的地址、传输层源目的端口或协议类型对输入 业务进行分类，也可以根据口头中的t o s ( t y p eo f s e r v i c e ，服务类型) 字段进行分 类，每一类可能对应一个队列。疋包头的区分服务标记域( d sf i e l d ) 是d s 区域的 边界节点与内部节点问传递流聚集信息的媒介，是连接边界的传输分类和调节机制与 内部p h b 的桥梁。d s 标记域定义为原i p v 4 包头的t o s 字节或i p v 6 包头的流类型字 节( t r a 伍cc l a s so c t e t ) 的前六位，其余两位以备将来使用。其结构如图2 2 3 所示 口5 日 t i i 图2 2 3 口包头的区分服务标记域 1 2 硕士论文基于网络q o s 的队列调度算法研究 在d s 域里，p h b 所分配的资源，取决于分组得到服务的频率。当网络通畅时， 属于各种p h b 的分组都能得到较好的服务。当网络拥塞时，分组得到的频率取决于 路由器，也就是d s 域内部节点的排队分组的调度规则。i n t e m e t 上的传统分组调度 规则是先进先出( f o ) ，以分组到达的左右顺序来传输分组。f 0 没有一个分组的 区别对待机制，因此，不能对属于不同p 皿的分组分配不同的资源。在d s 域内部， 用什么样的排队机制来实现p h b 的服务取决于i s p 对路由器的配置。 2 3 队列调度算法的性能指标 在网络应用中，用来衡量一种队列调度算法性能的好坏主要涉及到时延性能、公 平性、复杂性这三个方面【2 5 1 。队列调度算法可能在不同环境下有不同的应用。例如： 队列调度算法可能被用于隔离恶意业务流来为正常业务流提供服务质量保证；队列调 度算法还可能用来让用户平等地共享链路的可用带宽；或者用来实现分级的链路共享 等。实际上，有效的队列调度算法应该拥有诸多好的特性，即下面要讨论的队列调度 算法应达到的主要性能指标。 ( 1 ) 时延性能队列调度算法应为不同的业务流提供端到端的时延保证，而且 只与此业务流的某些参数( 如带宽需求等) 有关，而与其他的业务流无关。要为信息 流提供一定界限的时延，就必须对信息流的突发程度有一定的限制。s t i l i a d i s 和v a r m