（通信与信息系统专业论文）基于广义处理器共享模型的网络分组调度算法的研究.pdf

摘要 随着i n t e m e t 的飞速发展，网络由以前单一的数据网变成了多业务的综合数字网， 它的设计有两大目标：一是保证各类业务的q o s 要求，二是使网络的资源利用率达到最 佳。因此，研究网络分组调度算法，以获得更优的资源分配方案，满足服务质量的要求 具有重要意义。 本文首先综述了有线和无线的分组调度机制，详细介绍和分析了已有的分组调度算 法，如f c f s ，w r r ，p f q ，e d f ，i w f q ，c s d p s 等。重点研究了广义共享模型及其 p g p s 算法中w f 0 算法，该算法优点是不但保证带宽分配的公平性，而且具有较好的时延 性能，缺点是在链路带宽不足的情况下，无法保证实时业务的服务质量。本文提出了一 种基于服务类优先级的网络分组调度算法p s c w f q ( w f qb a s e do np r i o r i t ys e r v i c e c l a s s ) ，通过对服务分类，将实时业务与非实时业务区分开，保证实时业务具有高优先 级，使实时业务的服务质量在链路带宽不足的情况下得到有效的保证。仿真结果表明 p s c w f q 算法既保持了w f q 算法的优点，也有效控制了实时业务的最大时延，提高了 服务质量。随后分析了将有线网络调度算法引入无线网络中应该注意的问题，由于无线 信道的特殊性，算法引入了补偿和再分配模式。在此基础上研究了一种基于比例补偿的 无线分组调度算法。仿真结果表明，采用比例补偿模式后提高了网络的公平性。 关键词：服务质量，分组调度，实时业务，广义共享模型，无线网络 a b s t r a c t w i t ht h ee v o l u t i o no fi n t e m e t ，n e t w o r kh a sc h a n g e dt om u l t i - s e r v i c e sd i g i t a ln e t w o r k f r o mt h es i n g l ed i g i t a ln e t w o r k t h e r ea r et w om a i no b j e c t sf o rn e t w o r kd e s i g n ，o n ei st o g u a r a n t e eq o sr e q u i r e m e n t so fh e t e r o g e n e o u ss e r v i c e s ，a n dt h eo t h e ri s t om a k er e s o u r c e u t i l i z a t i o na c h i e v eb e s t t h u s ，i no r d e rt og a i nm o r ee x c e l l e n tr e s o u r c ed i s t r i b u t i o ns c h e m e a n dm e e tt h er e q u i r e m e n to fq o s ，s t u d yo np a c k e t s c h e d u l i n ga l g o r i t h m sa r eo fg r e a t i m p o r t a n c e f i r s t l yt h ep a p e rd i s c u s s e st h e w i r e da n dw i r e l e s sp a c k e t s c h e d u l i n gm e c h a n i s m ， d e s c r i b e sa n da n a l y z e san u m b e ro fp a c k e ts c h e d u l i n ga l g o r i t h mc o m m o n l yu s e d s u c ha s ： f c f s ，w r r ，p f q ，e d e i w f q ，c s d p s t h i sp a p e rf o c u s e so ng p ss y s t e ma n ds t u d i e so n eo f p g p sa l g o r i t h m s - - w f q i t sa d v a n t a g ei sn o to n l yg u a r a n t e e dt h ef a i m e s so fb a n d w i d t h a l l o c a t i o n ，a n dh a sag o o dd e l a yp e r f o r m a n c e ，t h es h o r t c o m i n g si st h a ti nt h ea b s e n c eo f s u f f i c i e n tl i n kb a n d w i d t hr e a l t i m es e r v i c e sc a nn o tg u a r a n t e et h eq u a l i t yo fs e r v i c e t h ep a p e r p r o p o s e t h ep s c w f qa l g o r i t h mb a s e do np r i o r i t ys e r v i c e sc l a s s t h ea l g o r i t h md i s t i n g u i s h e s b e t w e e nr e a l t i m es e r v i c ea n dn o n r e a l - t i m es e r v i c eb a s e do ns e r v i c e sc l a s s ，u n d e rt h e c o n d i t i o nt h a tt h el i n kb a n d w i d t hi si n a d e q u a t e ，p s c w f qe n s u r e st h eq o so fr e a l t i m e s e r v i c e t h er e s u l t so fs i m u l a t i o ns h o wt h a tt h ea l g o r i t h mc o n t r o le f f e c t i v e l yd e l a yo f r e a l - t i m eb u s i n e s s ，a n di m p r o v et h ep e r f o r m a n c eo ft h e i rq o s t h e nt h ep a p e rd i s c u s s e st h e k e yi s s u e si nh o wt oa d a p tp a c k e ts c h e d u l i n ga l g o r i t h m si n w i r e l i n en e t w o r k st ow i r e l e s s n e t w o r k s ；b e c a u s eo ft h ep a r t i c u l a r i t yo fw i r e l e s sc h a n n e l ，t h ea l g o r i t h mi n t r o d u c e dam o d e l o fc o m p e n s a t i o na n dr e d i s t r i b u t i o na n dp r o p o s e saw i r e l e s sp a c k e ts c h e d u l i n ga l g o r i t h m b a s e do np r o p o r t i o n a lc o m p e n s a t i o n t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o r t i o no ft h e c o m p e n s a t i o nm o d e lu s e di m p r o v et h ef a i m e s so ft h en e t w o r k k e y w o r d - q o s ，p a c k e ts c h e d u l i n g ，r e a l s e r v i c e s ，g p s ，wi r e l e s sn e t w o r k i i 海南大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所旱交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写 过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 论文作者签名： 铸宝 日期：力听年争月彦日 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权海南人 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密论文在解密后遵守此规定。 论文作者签名：雄导师签名彬 日期：勿即年年月陟日日期：矽，7 年舻月f6 日 1 。1 本人已经认真阅读“c a l i s 高校学位论文全文数据厍发布苹程”，同葸将本人的学何论 文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程”中规定享受相关 权益。旦重邀邀卮鲎正吐生乙旦二生l 幽。 才 一 论文作者签名：砌按导师签名：够形 日期：2 听年年月彦日日期：勿口刁年中月，6 日 1 1 研究的背景 第一章绪论弟一早珀y 匕 随着高速网络技术的飞速发展，各种业务的迅猛发展，尤其是视频、语音等多媒体 业务( 如视频会议、视频点播、i p 可视电话) 的迅猛增长，i p 网络也由以前单一的数 据网变成了多业务的综合数字网。对网络提出了新的要求，如分布式多媒体应用，不但 对网络有很高的带宽要求，而且要求信息传输是低延迟和低抖动，同时，这些应用大都 能够容忍一定程度的信息丢失和错误。这种应用对网络的各种要求被称为网络服务质量 ( q u a l i t yo fs e r v i c e ，q o s ) 要求。 正是由于各种多媒体应用的推动，在当前高速网络中按照用户的要求提高服务质量 成为一个普遍的要求，也是i n t e m e t 发展的重要挑战。多媒体信息传输与管理的服务质 量的研究已经成为国际网络研究领域中最重要的研究方向之一。这种情况下，针对如何 有效的提高和改善网络中的服务质量这一问题，各个研究团体纷纷开始组织大规模的 o o s 研究，一些大的通信厂商也联合成立了q o s 论坛，协商各种q o s 技术标准的实施 方案。截至目前，各种方面的解决方案层出不穷，如流分类、路由协议等等。这其中， 比较行之有效且被大家所公认的一种解决方式就是分组调度算法。 1 2 网络服务质量 1 2 1 网络服务质量的定义 从一般质量的角度来看，网络服务质量可以认为是使用网络提供服务的容易程度以 及它的统一性。但在因特网中，它的基本特性是被指定的两点之间提供具有尽力而为的 传输服务，也就是说数据将被送到所希望的地方，基本服务是连通性服务，除此之外并 无其他规定。因此，在因特网中路径的传输速率、可靠性( 误码率) 、延迟等都是服务质 量的要素。也就是说，因特网的q o s 是指某个主机上的应用向其它主机上的应用发出一 连串的数据包时的平均速率、最大速率、数据包的延迟时间、抖动、数据包的损失等。 但是这些值并不是只从网络的结构上就能确定的，它具有受流入网络中的通信量影响的 特性。以高速公路做个比喻，高速公路上的质量应该是时速每小时多少公里，以及从某 地到某地所需的时间。仅靠公路的结构值是不可能预测公路的质量的。它与汽车通过的 流量有着紧密的关系，而且这些值的预测是很困难的，几乎是不可能保证的。很多人使 用的因特网也是同样的情况。比如，如果有人对流入的通信量加以制约，就不可能预测 和控制网路内的延迟。不仅使自己的通信量由于线路速率、误码率和延迟等的改变而发 生变化，还会使别人的通信量也受到同样的影响。 因此，只给出网络结构然后预测其质量或者指定因特网质量值来设计满足需要的网 络都很困难。由于这个原因，对因特网的q o s 的实际业务的定义是很难的，在实际情况 中已有很多种对q o s 的解释。表卜1 就是对q o s 的定义 表1 - 1o o s 定义的列表 o o s 概念覆盖范围 特点 研究范围主要局限于i p 层， 没有从整个网的角度去分析 l e t fp 层问题。筋的研究都局限于单 个网络而不是多个网自治 域， 直接面向网络中的各个运营 i t u e t s i网络中的各个运营实体实体( 用户、s p , n p 等) o s i 网络某型的各个协议层逻辑抽象层次较高，需要对具 i s o次之间、多个协议栈的对等协体网络进行功能化，通常不能 议层之间。直接应用到具体的网络中。 文献乜1 中描述：o o s 是网络在传输数据流时要求满足的一系列服务请求，具体可以量 化为带宽、延迟、延迟抖动、丢失率、吞吐量等性能指标。此处的服务具体是指数据包 ( 流) 经过若干网络节点所接受的传输服务，强调端到端或网络边界到边界的整体性，q o s 反映了网络元素( 应用程序、主机或路由器) 在保证信息传输和满足服务要求方面的能 力。 控制q o s 的目标是为i n t e r n e t 应用提供服务区分和性能保证：服务区分是指根据不 同应用的需求为其提供不同的服务：性能保证则要解决诸如带宽、丢失、延迟、延迟抖 动等性能指标的保证问题。然而，在网络中，特别是在i n t e m e t 这样大规模的全球网络 中提供q o s 绝非易事，它需要自顶向下所有网络层( 即i s o o s i 模型中的第卜第7 层) 以及端到端( 即从信息的发送者到接收者) 的所有网络元素的整体协作。 1 2 2 性能参数 网络o o s 的研究目标是有效地为用户提供端到端的服务质量控制或保证，它通过以 下的性能参数来衡量网络传输各种业务的性能： 1 端到端的时延：指发送端与接收端之间发送和接收数据包的时间间隔，它主要 是由分组在路由器中的等待时间和服务时间引入的。 2 时延抖动：指端到端传输时延的变化，即相邻两个分组到达接收端的时间间隔 相对与发送端发送这两个分组的时间间隔之间的差值。 3 丢包率：指在分组传输过程中，丢失的分组数与源端发送的分组数之比。分组 的丢失主要是由出错或者网络拥塞引起的。在q o s 解决方案设计时应充分考虑到不同 2 业务对丢包率的要求。 4 吞吐量：指单位时间内有多少数据进入网络( 网络中发送分组的速率) ，可用平 均速率或峰值速率表示。网络吞吐量就是它的有效带宽。 以上四个性能参数也是调度算法所要满足的基本要求 1 3 分组调度的意义 1 3 1 分组调度对q o s 的意义 网络q o s 控制的目标是在众多网络传输节点构成传输网的基础上，通过整合、规划 所有的网路带宽资源的使用，为用户提供端到端的有服务质量保证的网络传输服务。而 带宽资源在网络传输节点上的分配主要通过基于多队列的分组调度机制来实现。因此本 文将主要研究分组调度算法，以获得更优的资源分配方案，满足o o s 的性能要求。 1 3 2 分组调度对拥塞控制的意义 当网络中的通信量大于所提供的带宽时，就会出现拥塞。拥塞导致的直接结果是分 组丢失率提高，端到端时延加大，甚至有可能使整个系统发生崩溃。调度通过在网络中间 节点( 路由器) 上直接管理输出链路的带宽资源来协助解决网络拥塞问题。调度功能n 阳 对于保证拥塞控制机制的公平性将起不小的作用。因为目前有关拥塞控制的研究还没有 过分地强调公平性，而是将注意力放在端到端的性能上，但随着应用需求的加强，为保证 一定的公平性，调度在拥塞控制中的作用将会慢慢地显现出来，基于中间节点上的调度 机制强化拥塞控制的功能也将会是一种有效的技术途径。 1 4 论文所做的工作 本文的主要目的是研究网络分组调度算法及其应用，主要是基于广义处理器模型的 网络分组调度算法，研究了基于服务优先级的p s c w f q 调度算法和一种基于补偿的无 线网络调度算法。 首先，本文对有线分组调度算法和无线分组调度算法进行研究，例如：先来先服务 调度算法、优先级调度算法、轮循环调度算法、加权公平排队、i w f q 算法等，为后面 的算法的提出做了理论铺垫。 然后，提出了一种基于广义处理器共享模型的p s c w f q 的算法，p s c w f q 算法针 对w f q 算法不区分服务类的缺点而提出了，它通过区分服务类别并保证实时业务的高 优先级，在带宽不足的情况下首先保证实时业务的带宽需求，提高了实时业务的服务质 量。接着研究了一种基于比例补偿的无线分组调度算法，并利用o p n e t 对算法进行了仿 真，我们在仿真时主要针对补偿带来的性能变化。 最后本文对全文进行了总结，并对下一步的研究趋势进行了分析 1 5 论文内容安排 本文的结构安排如下： 第一章绪论，介绍了网络q o s 的基本概念、网络q o s 的性能参数和调度算法的研 究意义。 第二章研究了国内外已知有线网络的分组调度算法，主要包括先来先服务队列调度 算法、基于优先级的调度算法、基于轮循的调度算法、基于广义处理器共享模型的调度 算法和基于时延的调度算法。 第三章集中讨论了国内外已知的无线网络的调度算法，并对这些算法的性能进行分 析和比较。 第四章研究了基于广义处理器共享模型的w f q ，并针对w f q 分组调度算法不区分 服务类别，提出了基于服务类优先级的p s c w f q 算法，并利用o p n e t 进行了仿真。 第五章研究了一种基于比例补偿的无线网络分组调度算法，利用o p n e t 进行仿真， 主要针对补偿带来的性能变化。 第六章是工作总结与展望，对全文进行总结，指出目前在研究中还存在的一些问题 和不足，并给出了下一步可能的研究课题和相应的一些设想。 4 第二章有线分组调度机制 调度是系统资源管理的核心机制之一，是解决多个业务竞争共享资源问题的有效手 段。本章所述分组调度，是指对连接中的数据报文的服务顺序进行控制，实现了对链路 带宽的管理。 首先概述了分组调度算法的意义、原理、性能指标和连续工作与非连续工作的特性 等相关知识，然后分析研究了几种主要调度算法( 先到先服务、优先级服务、循环调度、 处理器共享、曲线服务) 的设计思想。 2 1 分组调度算法原理 分组调度算法，是指路由器按照某种规则从多个( 或一个) 队列中选择下一次待转 发的分组，使得所有的输入业务流能按照预定的方式共享输出链路带宽，占有相应的网 络资源，满足自己要求的服务性能。如图2 - 1 所示，输入业务到达交换节点后，分别暂 存到相应的队列中，假设总共有n 个队列，分组调度算法的任务是如何从这n 个队列中选 择下一个要传输的分组。分组调度算法是实现网络服务质量的核心技术之一，主要实现 对链路带宽的管理。 ，膏队列l k 、 7 、k 。输出业务。输入业务 ：7交换节点输出模块 ，扩7 、| 、誓队列n l ， + 调度算法 图2 - 1 调度算法原理 2 2 分组调度算法的性能指标 有效的分组调度算法应该拥有诸多良好的特- i 生t 4 ，主要涉及到时延性能、公平性和 复杂性1 3j 等几个方面。 ( 1 ) 时延性能：分组调度算法应为不同的业务流提供端到端的时延保证，而且只与 此业务流的某些参数( 如带宽需求等) 有关，而与其他的业务流无关。时延性能体现了用户 对调度算法的要求。s t i l i a d i s 和v a n t l a 【5 】首先提出了一种分析网络中不同队列调度算法 带来的端到端时延的模型：时延速率服务器( 1 a t e n c yr a t es e r v e r , l r s ) 。 f r a n c i n i l 6 1 随后又 提出了另一种分析端到端时延的模型：速率分隔时签调度器( r a t es p a c e dt i m e s t a m p s c h e d u l e r , r s t ) 6 】【7 】，此模型的限制条件比l r s 要少且在定长分组环境下应用时更加有 效。 ( 2 ) 公平性：可用的链路带宽必须以公平的方式分配给共享此链路的各业务流， 并且必须能够隔离不同的业务流，让不同的流只享用自己可以享用的带宽，这样即使存在 恶意或高突发性业务，它也不致影响到其他的正常业务流。目前普遍衡量一个调度算法的 公平性有两个参数标准：服务公平指数( s e r v i c ef a i r n e s si n d e x ，s f i ) 【8 】【9 1 和最坏公平指数 ( w o r s t c a s ef a i r n e s si n d e x ，w f i ) t 8 】【9 】两种。s f i 定义为任意两个活动队列在任意时间 间隔内收到的归一化服务量( 等于服务量与其分配的服务速率的比值) 的最大差值。s f i 的定义如公式2 1 。 s f i 彬( f 】，乞) 辟一( f j ，t 2 ) p ， ( 2 - 1 ) 其中，彬( “t ：) 和( f ，f ：) 表示连接i 和连接j 在活动时间间隔( ，f ：) 期间分别所得到的 服务量；岛和尸，表示分给连接i 和连接j 的速率。w f i 用来表示一个队列在分组级系统 和相应流系统上接受到的服务量的最大差值，较大的w f i 意味着调度输出业务较大的 突发性。w f i 的定义如下： 形( ，t 2 ) ( t 2 一f 1 ) 岛一e ( 2 2 ) w f i = 而n ( e ) 肛 ( 2 3 ) ( 3 ) 简单性和可扩展性：调度算法实现起来应该比较简单。在高速网络中，传输一 个分组的时间很小，所以调度算法必须在短时间里完成对分组的调度，这就要求调度算法 尽量简单，易于实现。另外当业务流数量增加和链路速率变化范围较大时，调度算法仍应、 有效工作，这要求调度算法应该具有良好的可扩展性。 2 3 连续工作和断续工作 分组调度算法还有一种特性：连续工作或断续工作【l 。其中连续工作算法表示只要 系统中有等待分组，调度器就可以选出一个分组进行服务，其原理如图2 2 所示。而断续 工作算法则意味着即使系统中有等待分组，调度算法也可能暂时不对其进调度。这一类算 法一般是在输入业务流被调度之前对其进行整形处理。它的基本思路如图2 3 所示，即 当有分组到达时，该分组首先进入一个流的调节器，通过使用调节算法，使到达分组在 适当的时间才可以进行调度输出。在调节算法的设计上可以针对不同的调节目标，如消除 时延抖动或速率抖动，进行选择和优化。只有少数算法是断续工作的，比如 h r r ( h i e r a r c h i c a lr o u n dr o b i n ) ，j i t t e r - e d d ( ji t t e r - e a r l i e s t d u e d a t e ) ，s t o p a n d g o 。 6 图2 - 2 连续工作调度算法原理图 调节器1 ： 输出连路 输入连路 ( 二 一 调节器n 调节器调度输出 图2 - 3 断续工作调度算法原理图 对连续工作型调度算法而言，由于此类算法可以允许网络流量特性扭曲，所以可以 在不关心所调度的流量特性是否被改变的情况下，持续地进行工作，因而对提高网络的 利用率和转发系统的吞吐率来说，此类算法是比较好的；同时一般情况下，通过对不同 流进行调度时刻的隔离，此类算法可以保证较好的端端时延等各种调度指标，特别是公 平队列一类算法，同时还可以保证算法的公平性。此类算法的不足之处在于可能因为调 度算法的原因，造成网络流量特性的扭曲，使网络流量的突发性增大，这对于网络的其 他工作机制，如拥塞控制机制会造成很大的负面影响，同时也增加了对中继节点的缓冲 开销要求。对断续工作型调度算法而言，由于此类算法的特点就是试图尽可能地维持网 络的流量特性，因此不能持续地进行工作，因而从提高网络利用率和转发系统吞吐率的 角度来看，此类算法存在不足。但此类算法的优点也很明显：由于不改变流特性，此类 算法最大的优点在于可以解耦带宽与所要到达的时延界限。同时由于可以分别实现不同 的调节器和调度器，因而可以为实现提供不同的选择。因为使用了一定的调节机制，所以 对中继节点的缓冲开销要求降低。 2 4 主要的有线分组调度算法 分组调度算法的研究一直是一个热门课题，到目前为止，产生的算法已有几十种， 分别有着不同的服务规则、控制目的和复杂度。为了了解调度算法的设计思想并对调度 器设计有一个宏观的理解，本节简要描述一下这几类算法的基本思想。 本文拟提出的p s c w f q 算法属于基于广义处理器器共享模型的算法，因此将在后面 7 章节介绍了广义处理器器模型比较成功的w f o 算法。 2 4 1 先来先服务队列调度算法的实现 先来先服务( f i r s tc o m ef i r s ts e r v i c e ，f c f s ) 队列调度算法是一种基本的队列调 度算法，也是目前路由器上最常用的一种调度策略。在这种调度策略下，分组进入队列 的顺序与被传输的顺序相同。通过将分组放置到一个队列中，并按照它们到达的先后顺 序对它们进行服务。如图2 4 所示。 f c f sq u e u e 图2 - 4f c f s 队列调度算法 f c f s 的优点是： ( 1 ) 队列管理简单，调度实现方便。 ( 2 ) 这种排队方式下，在接收端不需要对分组进行重排序，并且最大时延可以通 过最大队列深度来决定。只要保证较短的队列长度，就可以获得较小的时延。 f c f s 策略为共享网络资源提供一种最简单的队列调度算法，但f c f s 算法也存在 着比较明显的弊端： ( 1 ) 它不能对具有不同服务等级要求的业务流进行区别对待，即不能对不同流提 供区分服务。即无法保证一个对q o s 要求高的分组得到比一个对q o s 要求低、甚至没 有q o s 要求的分组获得更好的服务。 ( 2 ) 这种策略不能实现t c p 和u d p 之间的公平性，当发生拥塞时，可能使u d p 流占用更多的带宽资源，导致t c p 流时延、时延抖动增加以及带宽占用率减少。 ( 3 ) 当拥塞发生时，所有的业务流的平均排队时延都增加，所以这种队列调度方 式对所有业务流的影响都是一样的，而这对实时应用更为不利，因为时延、时延抖动的 增加会严重影响这些业务的性能。 ( 4 ) 这种策略不能在业务流之间提供很好的隔离性。一个突发业务流或非适应流 8 可能占用所有的缓存空间，从而导致所有其他的服务被拒绝。 2 4 2 基于优先级的调度算法 常见的基于优先级的分组调度算法有基于优先级调度策略的( p r i o r i t yq u e u e i n g ， p q ) 和q l t ( q u e u el e n g t ht h r e s h o l d ) 13 1 。 p q 算法可以为不同等级的服务提供一种相对简单的调度方法。p q 算法给每个队列 赋予不同的优先级，系统将到达的分组进行分类，然后分配到不同的优先级队列中，每 次需要调度时，具有最高优先级的非空队列中的分组最先被选择服务，在一个队列中分 组按照f c f s 的原则被服务，如图2 5 所示。如果最高优先级的队列为空，则选择具有 次优先级的队列进行服务，依此类推。这样，被分配到较高优先级的队列按照事先的设 想优先得到服务和传输，其分组时延就比较小，吞吐量也相对较大。 商f l o w i 1l 7 路 p q q u e u e 22 由 小一 _ _ - j 3221 器 337 图2 - 5p q 调度算法 p q 策略的优点在于它能为业务提供不同等级的服务，可以通过为实时业务设定比 较高的优先级来更好地保证他们的服务质量。严格的优先级排队策略保证路由器总是先 服务高优先级队列的分组，并且只有在高优先级的所有队列为空的时候才为低优先级的 队列提供服务，这种过于严格的规则使这一策略存在致命的缺点：当某一时间段内有大 量该队列的分组到达时，会造成服务器资源在一段时间内被该队列全部占用，其它队列 的服务质量将无法保证。即低优先级队列长时间内得不到服务，会产生“饿死”现象， 因而公平性很差。如果有恶意攻击者发出大量具有高优先级的数据包，会造成服务器被 完全占用而导致该算法不可用。另外，优先级是静态配置的，不能动态适应变化的网络 要求。 解决p q 算法中低优先级队列“饿死”现象的对策是设置调度阈值。q l t 给各个 队列设置调度阈值，需要进行调度时从最高优先级开始比较队列的长度和调度阈值。当 最高优先级队列的长度大于或等于调度阈值时，该队列头部的分组首先被选择服务。当 最高优先级队列的长度小于其调度阈值时，不再服务调度该队列，而是检查具有次高优 先级的队列，依次类推。通过调度阈值的合理配置，q l t 算法能够对队列进行简单的 分隔，限制了它们之间的相互影响，提高了公平性。 9 2 4 3 基于轮循的调度算法 轮循类算法的基本思路是对每条链路的头分组采用轮循的方式来选择可以发送的 分组。常见的基于轮循的算法有r r ( r o u n dr o b i n ) ，加权轮循w r r ( w e i g h t e d r o u n d r o b i n ) 1 4 】，差额轮循d r r ( d e f i c i tr o u n dr o b i n ) 1 5 1 和紧急轮循u r r ( u r g e n c y b a s e d r o u n dr o b i n ) 1 6 1 等。 l 、r r 算法 传统的r r 算法先将分组分配到指定的队列，然后对不同队列进行无区别的循环调 度服务，跳过空队列。一次调度一个分组，使得不同队列在某种程度上“平等”地利用 带宽资源，如图2 6 所示。但是，如果不同的队列具有不同的分组长度，则分组长度 大的队列可能会比分组长度小的队列接受更多的服务，使队列之间产生不公平的现象。 而且，这种算法不能对业务提供时延保证。为了改进r r 算法的时延特性和其在变长 分组环境下的不公平性，出现了些改进型的算法，如w r r 、d r r 、u r r 等。这些 算法力图在尽量保持r r 算法实现的简单性的同时，从不同的方面改进r r 算法的时 延性能和其在可变长分组环境下的公平性。 f l o w i 五口 凡。眦 二 f l o w 3 丑 r r q u e u e 图2 - 6r r 队列调度算法 2 、w r r 调度算法 该算法最初是用在a t m 交换机上的，它在r r 基础上为每个队列赋予了一个权值， 同时为每个队列维护一个记数器，初始值为权值。在每次轮循时，计数器允许非零的队 列仅发送一个信元，并把计数器减1 。当所有的队列的计数器均为零时，重置为权值。 如图2 7 所示，w r r 算法能够比r r 更灵活地控制带宽在不同队列的分配，而且同时 以比较平滑的方式输出业务，其最主要的不足在于只有当分组尺寸一样时，这种算法才 能为每个服务等级提供准确的带宽分配比例，如果一个服务等级业务的分组尺寸大于另 一个等级，它将会占用比预定值更多的输出带宽。在队列调度算法中，为照顾公平性和 效率，w r r 是常用的队列调度算法，它也是i e t f 推荐的q o s 调度算法。 1 0 2 正田o ： 3 匝亚田囊 3 d r r 算法 w r rq u e u e 图2 7 w r r 队列调度算法 d r r 算法的提出是为了解决r r 和w r r 算法中由于分组变长带来的不公平性， d r r 算法以字节为单位为每个队列分配一个带宽配额，该配额的比例对应于队列服务 速率的比例。同时，为每个队列维护一个计数器，初始化为其带宽配额。每次轮循时， 如果待发送分组长度小于或等于计数器值，则允许发送，并把计数器减去此分组长度值； 如果待发送分组长度大于计数器值，则检查下一个队列，同时把该队列计数器值累加到 下一次循环( 即下次调度该队列之前把次剩余值和配额之和赋予计数器) 。d r r 由于考虑 了分组变长这一信息，很好地解决了带宽分配的公平性问题。缺陷是不能很好地满足业 务的时延特性，不能像w r r 那样以较平滑的方式调度输出业务流，不能有效地支持实 时业务。 4 u r r 算法 该算法主要的目的是在不过度提高复杂性的情况下，改善传统的r r 算法的时延特 性。在u r r 算法中，系统给每一个队列赋予一个紧急参数o ) ，在每一轮循环开始之 前，算法都要计算每个队列的( f ) 参数( 等于其队列长度与速率的比值) ，并按降序排列， 服务顺序从大到小。u r r 算法改善了r r 的时延特性，但仍然存在传统r r 算法中的不 公平性【3 1 。 2 4 4 基于广义处理器器共享模型的调度算法 g p s 模型，即广义处理器器共享( 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 ) 模型是一个理想 化的流模型【l7 1 ，它根据各队列的共享比例对所有的活动队列同时服务，所以能使各业务 流真j 下公平地共享链路带宽。g p s 对每个队列业务流保证有明确的端到端的时延上限， 而且与其他队列业务流无关。g p s 是流系统，但是实际的传输系统都是基于分组的， 在任何给定的时刻只能有一个分组得到服务，而且分组的传输是不能被抢占的。因此 g p s 模型在实际网络中是无法实现的，继而出现了一类在分组环境中逼近g p s 的分组 调度算法，即分组公平队列算法( p a c k e tf a i rq u e u e i n g ，p f q ) 。常见的p f q 算法有w f q ( w e i g h t e df a i rq u e u e i n g ) 1 1 9 1 ，w f 2 q 【2 0 1 ，w f 2 q + 1 21 1 ，v c ( v i r t u a lc l o c k ) 2 2 】，s c f q ( s e l f - c l o c k e df a i rq u e u e i n g ) 2 3 】，s f q ( s t o c h a s t i cf a i rq u e u e i n g ) 1 2 4 】，s p f q ( s t a r t i n g p o t e n t i a lf a i rq u e u e i n g ) 【8 】和f f q ( f r a m e b a s e df a i rq u e u e i n g ) 【9 1 等。这些算 法在仿真流体g p s 模型的时候都采用了一些控制措施把与g p s 的q o s 性能误差如 分组时延、吞吐量限制在一个有限的范围内。它们的调度性能都不可能达到g p s 的标 准，但是与以前的调度算法相比其性能有了很大的提高。其中，w f q 模拟g p s 最成 功，因此被i e t f 指定为有保证业务的参考排队算法。所有的p f q 算法的核心是维护一 个系统虚拟时间函数v ( t ) ，同时为每一个分组队列维护了一个虚拟开始时间标签s ( f ) ( 代表队列i 头部分组的虚拟开始发送的时间) 和一个虚拟完成时间标签f ( r ) ( 代表队 列i 头部分组的虚拟完成发送的时间) ，并当空队列有分组到达，或者队列中有分组发送 完毕时分别计算如式2 4 ： 群= m a x ( f , 肛1 ，y ( 群) ) f 。= 酽+ 髟f ( 2 _ 4 ) 其中p ? 表示连接i 的第k 个分组，口! 表示p ? 的到达时间，磷表示p ? 的服务开始时 间标签，f 表示p ? 的结束服务时间标签，t 表示p ? 的分组长度，表示连接i 的预约 的服务速率。 每次调度时，系统根据时间标签的大小选择分组进行传送。系统通过给用户链接提 供最小的带宽保证，进而提供时延范围的保证。所有p f q 算法都是在虚拟时间函数的 基础上根据一定的选择策略进行调度的。分组的选择策略主要有三种：最小虚拟完成时 间优先( s f f ：s m a l l e s tv i r t u a lf i n i s h e dt i m ef i r s t ) ，即系统中具有最小虚拟完成时间的队列 的队头分组被选择发送；最小虚拟开始时间优先( s s f ：s m a l l e s tv i r t u a ls t a r t e dt i m ef i r s t ) ， 即系统中具有最小虚拟开始时间的队列的队头分组被选择发送；最小合法虚拟完成时间 优先( s e f f ：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 e dt i m ef i r s t ) ，即系统中具有最小虚完成时间且 “合法”的分组先得到服务，所谓合法是指分组的虚拟开始时间不大于当前的系统虚拟 时间。前两种策略对于分组的选择只使用一个时间标签，因而可能会产生与g p s 模型 较大的偏差，影响系统的公平性。 2 4 5 基于时延的调度算法 基于轮循和g p s 模型的调度算法可以看成是基于速率的调度算法，这种算法通常 为每个队列提供一定的速率保证来达到提供时延保证的目的。而基于时延的调度算法则 是直接以排队时间作为参数，并以提供时延保证为目的。这类算法主要包括e d f ( e a r l i e s t d e a d l i n ef i r s t ) t 2 5 1 ，r c s ( r a t e c o n t r o l l e ds e r v i c e ) ，d e l a y e d d ，j i t t e r - e d d ，r c - e d f ( r a t e c o n t r o l l e de d f ) ，d c e d f ( d e a d l i n e c u r v ee d f ) 和e e d f ( e a r l i e s te f f e c t i v e d e a d l i n ef i r s t ) 等。在e d f 算法中，给每个队列赋予了一个时延参数，表示系统对此队 1 2 列提供的时延上界；e d f 为每个到达的分组计算一个时间标签( 等于分组到达时间与其 所属队列值之和，时间标签最小的最先得到服务) 。e d f 算法中由于涉及到对时签的排 序，其复杂度为。e d f 能很好地提供时延保证，但输入业务必须满足一定的属性要求。 在网络环境下，进入到下游交换节点的业务属性早已发生了变化，所以在实际中f d f 无法提供端到端的时延保证。为了改进这种缺点，文献【3 4 j 提出了r c 调度算法。r c s 在 f d f 的基础上引入了整形机制。到达的业务流首先进入整形器，经过整形后的业务必须 满足一定的属性要求，然后进入r c s 中的f d f 调度器，这样在每个节点处都能得到时 延保证( 等于整形时延与调度时延之和) 。 2 4 6 基于服务曲线的算法 g p s 模型的局限性在于业务只用了一个参数( 速率) 来指定，使得时延与带宽的分配 互相耦合在一起，也就是说低时延就需要高带宽。这对于低时延、低带宽的业务就不能 有一个很高的资源利用率。为了解决这个问题，c r u z 啪1 首先提出了服务曲线的q o s 模型 及其算法。基于服务曲线的算法不是用一些简单的数字来描述服务的，而是引入了一种 通用的服务描述函数。这使得网络连接的服务特性与其它网络连接区别开来，更好的满 足了用户所需求的q o s 。如图2 8 所示，每一种业务被赋予一条服务曲线，这条服务曲 线制定了它不同时刻应该收到的最小服务量；最上面一条为到达曲线，下面三条为服务 曲线，可见对于相同的到达曲线，不同的服务曲线所提供的时延是不同的。而且两段线 形的服务曲线去耦了时延与带宽的分配问题。但是一个根本的矛盾就是由于有了非线性 的服务曲线和有优先级的业务，就有可能对所有的业务种类不能同时提供保证的服务曲 线，也有可能不能同时保证实时性和公平性。基于服务曲线的算法有：基于服务曲线的 最早期限优先( s c e d ，s e r v c i ec u r v e b a s e d e a r l i e s td e a d l i n e ) 和分级的公平服务曲线 ( h f s c ，h i e r a r c h i c a lf a i rs e r v i c ec u r v e ) 。 时间 图2 8 基于服务曲线的调度算法 2 4 7 其它算法 根据调度算法的工作原理和控制目标，还有几种其它的调度算法： 分层链路共享算法，它把不同类型的业务流划分成不同级别的类，并同时考虑业务 的实时性和链路共享的需求，按照不同的层次进行分组调度，从而提供了在分层共享树 内进行不同等级的共享链路带宽资源的方法。常见的分层链路共享算法有 c b q ( c l a s s b a s e dq u e u e i n g ) ，h p f q ( h i e r a r c h i c a l p a c k e tf a i r q u e u e i n g ) 和 h f s c ( h i e r a r c h i c a lf a i rs e r v i c ec u r v e ) 等。类似于区分服务( d i f f s e r v ) 的核心无状态算 法，它的主要思想是避免核心交换节点过于繁忙，依赖于边缘交换节点和核心交换节点的 有效