（通信与信息系统专业论文）基于pfq的分组调度算法的研究.pdf

中文摘要 随着网络技术的飞速发展，网络中承载的实时性业务越来越多。传统网络“尽 力而为”的服务类型不能支持服务质量( q o s ) 保证，给实时性业务的承载带来 诸多不便。q o s 的控制机制由于可以为网络提供服务质量保证而成为下一代高速 网络的核心技术之一。 分组调度算法是为网络提供q o s 保证的一项重要措施，也是q o s 控制机制 中的关键技术之一，如今已成为网络研究与开发的热点问题。有线网络分组调度 算法的研究已经较为成熟，在广义处理机算法的基础上人们提出了许多面向数据 包的调度算法。 无线分组网络中的服务质量保证是其提供实时性业务传输的关键。无线网络 频带资源有限、无线信道易受外界干扰，网络特有的突发性和位置依赖性错误使 得传统的有线网络调度算法不能直接应用于无线网络。无线分组调度算法都是考 虑了无线信道的特点，在有线网络调度算法的基础上提出的。 本文首先对有线网络分组调度算法进行了概述；其次，在总结了基于p f q 的分组调度算法共同点的基础上研究了一种通用的算法框架，并实现了w f q 、 v c 两种算法，同时对v c 的优先级策略进行了改进，提出了一种动态优先权机 制；然后，介绍了影响无线信道通信质量的重要因素和无线网络调度算法的一般 框架，研究了w f 2 q 的在无线环境中的应用；最后，针对p f q 算法具有时延一 带宽耦合的缺点，提出了一种综合考虑时延和带宽的调度算法，对时延和带宽的 解耦问题进行了初步的探讨。 通过大量的仿真实验，结果证明动态优先权策略和已有算法相比具有更好的 灵活性。时延一带宽的解耦算法也可在一定程度上减少p f q 算法中的时延一带 宽耦合现象。 关键词t服务质量分组调度公平排队补偿 a b s t r a c t r e c e n t l yw i n lt h ee x p l o s i v eg r o w t hi nn e t w o r k , t h e r ea r em o r ea n dm o r e r e a l - t i m ea p p l i c a t i o n s t h eb e s t - e f f o r ts e r v i c ei nt r a d i t i o n a ln e t w o r kc a n n o ts u p p o r t q o sg u a r a n t e e ，s or e a l - t i m ea p p l i c a t i o nc a n n o tb ea p p l i e dc o n v e n i e n t s i n c et h eq o s c o n t r o lm e c h a n i s mi sa b l et op r o v i d eq o sg u a r a n t e ef o rn e t w o r k , i tb e c o m e sak e y t e c h n i q u ei nh i 曲- s p e e dn e t w o r k p a c k e ts c h e d u l i n gi sak i n do fm e a s u r ef o rp r o v i d i n gq o sg u a r a n t e ea n da l l i m p o r t a n tt e c h n i q u eo fq o sc o n t r o lm e c h a n i s m t h er e s e a r c ho nw i r e l i n ep a c k e t s c h e d u l i n ga l g o r i t h m sh a sb e c o m ev e r ym a t u r e p e o p l eh a v ep u tf o r w a r dm a n y a l g o r i t h m si np a c k e tc o m m u n i c a t i o nb a s c d o ng p s t h ec o n v e n t i o n a ls c h e d u l i n ga l g o r i t h m si nw i r e l i n en e t w o r kc a n n o tb ed i r e c t l y a p p h e d t ow i r e l e s sc o m m u n i c a t i o ne n v i r o n m e n t sb e c a u s eo fw i r e l e s s s p e c i f i c c h a r a c t e r i s t i c s ：b u r s t ya n dl o c a t i o n d e p e n d e n te r r o r t a k i n gi n t oa c c o u n t t h e c h a r a c t e r i s t i c so fw i r e l e s sc h a n n e l ，w 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 sa r e s u b m i t t e db a s e do nw i r e l i n ep a c k e ts c h e d u l i n ga l g o r i t h m s f i r s t ，w em a k eas u m m a r i z ea b o u tw i r e l i n ep a c k e ts c h e d u l i n ga l g o r i t h m s ；t h e n , r e s e a r c haf r a m ew o r ku s e di np f qa l g o r i t h m sa n dp r o p o s eal 【i n do f d y n a m i cp r i o r i t y a l g o r i t h mo fv c ；n e x t ，i n 仃o d u c es o m ei m p o r t a n tf a c t o r si n f l u e n c i n gt h ew i r e l e s s c h a n n e la n dr e s e a r c ht h ea p p l i c a t i o no f w f 2 qi nw i r e l e s se n v i r o n m e n t ；f i n a l l y , m a k e ap r e l i m i n a r yd i s c u s s i o no nd e l a ya n db a n d w i d t hd e c o u p l i n gi np f q a l g o r i t h m s d o i n gal o to f s i m u l a t i o n ，t h er e s u l ts h o wt h a tt h en e wp r i o r i t ya l g o r i t h mh a sb e t t e r f l e x i b l et h a nt h eo l do n ea n dt h ed e c o u p l ea l g o r i t h mc a nd e c r e a s et h ec o u p l i n go f d e l a ya n db a n d w i d t hi ns o m ed e g r e e k e yw o r d s ：q o sp a c k e ts c h e d u l i n gf a i rq u e u i n g c o m p e n s a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鎏盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者躲巷乏，缘签字溉翮年2 ，月日 学位论文版权使用授权书 本学位论文作者完全了解基鲞盘生有关保留、使用学位论文的规定。 特授权鑫鲞表堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：考乏绎 导师签名： 孑雪 签字日期：五怫年二月巧日签字日期：2 。口6 年2 月之6 日 第一章绪论 1 1 服务质量的产生背景 第一章绪论 在i n t e m e t 发展的初期，其主要的业务范围集中在电子邮件、网页浏览、文 件传送协议等对服务质量( q u a l i t yo f s e r v i c e - q o s ) 不敏感的业务上。随着高速 网络技术和多媒体技术的飞速发展，产生了大量实时性要求很高的应用( 如i p 电 话、视频会议、电子商务等) ，人们越来越多地提出了包括多媒体通信在内的综合 服务要求。 从2 0 世纪8 0 年代至今，分组网络以其固有的带宽分配灵活、带宽利用率高 等特点在通信网络中扮演了重要的角色。传统的分组交换网络是面向非实时的数 据通信而设计的，采用的t c p i p 协议主要是为了优化整个网络的数据吞吐量并 保证数据通信的可靠性。而当今分布式多媒体应用( 如视频会议、视频点播、远 程教育等) 不仅包括文本数据信息，还包括语音、图形、视频这些类型的多媒体 信息。分布式多媒体应用不但对网络有很高的带宽要求，而且要求信息传输的低 延迟和低抖动等，同时这些应用大都能够容忍一定程度的信息丢失和错误。为了 降低网络的建设、运营成本，人们希望采用统一的分组网络实现多类型业务的综 合承载。如何保证分组网络承载多种类型应用时的业务服务质量，已经成为人们 重点关注的问题。 目前，运营网络中大量的业务类型丰富的应用开始有分组网络承载。其中， 不乏对服务质量要求较高的实时业务。不同类型的应用对网络有不同的服务质量 要求，在网络资源有限的情况下不可能同时满足所有业务的服务质量要求。因此， 需要有合适的控制机制通过对网络资源的合理分配以尽量满足各种业务的q o s 要 求，这就是所谓的q o s 保证机制【”。要在“尽力而为”的传统网络上承载对q o s 敏感的业务类型，就必须引入有效的q o s 保证机制，将i n t e r n e t 从提供“尽力而为” 服务的网络改造成具有良好q o s 保证能力的网络。如今，服务质量不仅在传统的 电信领域里得到了广泛的使用，还逐渐扩展应用于基于分组的宽带、无线和多媒 体等服务领域。与此同时，通信网络和通信系统的设计和规划也越来越多低考虑 到用户应用的端到端性能需求。 为了在i n t e m e t 上提供具有q o s 保证的业务，并很好地区分“尽力而为”业 务和实时业务，i e t f 等标准化组织指定了各种协议和标准。总的思想是通过在 网络中添加一些协议，对网络中不同的业务进行分类，通过指定优先等级和资源 第一章绪论 预留标准，对于优先级高的业务优先预留网络资源( 如带宽、缓冲区等) ，从而 满足其q o s 要求。 1 2 服务质量保证和分组调度算法 实时性的应用要求网络提供基于q o s 的信息流实时拥塞控制，而这种控制是 通过q o s 控制机制来实现的。具体而言主要包括：通信量管理控制、q o s 路由、 基于q o s 的传输调度、缓冲区管理、流量管理和分组丢弃等。 分组调度可以在满足分组服务质量的前提下，合理安排和控制分组离开调度 器的时间和顺序，是服务质量保证机制中的一项关键技术。 无论在综合服务体系还是在区分服务体系中都涉及队列调度问题。调度算法 的基本功能是从节点的每一个输出链路中挑选出一个有效周期发送的分组。通常 这个排队系统由一个或多个队列和一个调度器组尉”。 图1 1 排队系统的组成 一个有效的队列调度机制应能够保证公平性、时延特性、对恶意业务流的隔 离能力、链路带宽的利用率等。算法的复杂性要适应网络高速传输并便于实现， 使其具有可扩展性和鲁棒性。 目前，常用的排队和调度机制包括：先进先出排队( f i f o f i r s ti nf i r s to u t ) 、 公平排队( f q f a i rq u e u i n g ) 、优先级排队( p q - p r i o r i t yq u e u i n g ) 、加权公平队列 ( w f q w e i g h tf a i rq u e u i g n ) 和基于分类的排队( c l a s s - b a s e dq u e u i n g ) 等。在众 多的q o s 保证机制中，本文主要研究的就是数据流的调度算法。 1 3 本文的主要内容和结构安排 分组调度算法是一种重要的服务质量保证措施，也是本文的主要研究对象。 冒 第一章绪论 首先，在研究有线网络p f q ( p a c k e tf a i rq u e u i n g ) 算法的基础上分析了算法的 通用模型，并对v c 算法中优先权问题加以了改进。其次，研究了无线网络调度 算法实现的框架结构，对w f 2 q 算法进行了改进使其能够应用于无线环境中。 最后，针对p f q 算法存在的时延带宽耦合问题提出了一种改进措施，使得算 法具有更加灵活的时延保障性能。 本文主要分为七个章节，另外在附录中对离散事件仿真机制进行了简要的介 绍，同时给出了几个重要定理的证明过程。 第一章绪论。概括介绍了服务质量、分组调度算法和本文的主要研究内容。 第二章服务质量保证。介绍了和服务质量有关的性能参数、控制机制和综 合服务模型区分服务模型等内容。 第三章有线网络分组调度算法的研究现状。详细介绍了有线网络分组调度 算法的研究现状，对各种类型的算法分别进行了说明。 第四章基于p f q 的分组调度算法研究。在分析p f q 算法原理的基础上研 究了算法实现的一般模型，并对v c 算法进行了改进使其可以支持动态优先权。 第五章无线网络分组调度算法研究。首先，介绍了影响无线信道质量的几 个重要因素；接着，分析了无线网络调度算法实现的框架结构；最后，改进了 w f 2 q 算法使其可以应用于无线环境中。 第六章时延一带宽祸合问题的初步探讨。分析了p f q 调度算法中存在时延 一带宽耦合的原因并提出了一种改进措施，在时延保证算法和带宽保证算法之间 取得一种折中。 第七章结束语。对全文进行综述并探讨了未来的研究方向。 第二章服务质量保证 2 1 服务质量的定义 2 1 1 服务质量的含义 第二章服务质量保证 任何服务都需要考虑质量，在通信和计算机网络中服务质量简称为q o s ( q u a l i t yo f s e r v i c e ) 。q o s 有广义和狭义之分1 2 ：狭义q o s 指技术指标如传输延迟、 抖动、丢失率、带宽要求、吞吐量等即“as e to f s e r v i c er e q u i r e m e n t st ob em e tb y t h en e t w o r kw h i l et r a n s p o r t i n gaf l o w 。”；广义q o s 指的是资源的调配与利用、层 与层之间的协商，从而涉及不同层次的q o s 。我们研究的q o s 指的是狭义的q o s 。 另一种定义方式将q o s 描述为：发送和接收信息的用户之间以及用户与传输 信息的综合服务网络之间关于信息传输的质量约定。该约定可以被理解为当用户 按照约定的信息流特征产生数据时，服务提供者与用户之间的一份服务契约即服 务提供者承担支持的服务质量。换句话说，服务质量包括用户的要求和网络服务 提供者的行为两个方面，是用户与服务提供者两方面主客观标准的统一。 从根本意义上说，q o s 指网络对业务性能要求的支持能力。这里的性能要求 是特定于不同业务的即不同的业务有不同的性能要求。 q o s 的定义是以端到端为基础的，强调端到端( e n d - t o e n d ) 或网络边界到 边界的整体性即q o s 是和终端用户密切相关的，反映了网络元素在保证信息传输 和满足服务要求方面的能力。 2 1 2 对服务质量含义的理解 q o s 的含义可以从服务固有的q o s 、用户感知的q o s 和用户评价的q o s - - 个方 面来理解”j 。 1 服务固有的q o s 。属于和服务特性相关联的技术方面的范畴，是由传输网 络设计的优劣以及网络接入、终止和连接的提供情况所决定的。通过适当地选择 传输协议、q o s 保证机制和相关参数的值，就能够得到特定应用所要求的q o s 。 用户对q o s 的主观评价不会影响服务固有q o s 的等级。 2 用户感知的q o s 。反映了用户对使用特定服务的体验，受观察到的服务性 能和用户期望比较后的结果的影响。对于不同的用户，具有相同固有q o s 特性的 服务会得到不同的评价。 第二章服务质量保证 3 用户评价的q o s 。取决于被感知q o s 、服务价格以及服务提供者受理用户 抱怨和服务问题的响应情况。 网络提供的q o s 可以从四个角度进行描述：用户的q o s 需求、服务提供者 计划提交的q o s 、服务提供者达到的q o s 、用户感知的q o s 。四者之间的关系如 下图所示 图2 1 q o s 的四个视角 用户的0 0 s 需求陈述了用户对特定业务所要求的质量水平，准确而清晰地描 述用户的服务质量要求是服务提供者用来规划网络服务等级的基本前提；服务提 供者计划提交的q o s 相当与一份服务质量水平声明，描述了服务提供者计划向用 户提交的服务质量，可以通过对q o s 参数分配具体数值来描述；服务提供者实现 的q o s 描述了服务提供者实际向用户提交的服务质量水平，也是通过一组q o s 参数分配数值来表述的；用户感知的q o s 反映了已经得到用户认可的该用户得到 的服务质量水平。 在以上的四个方面中，用户的q o s 需求是一个逻辑的出发点，用户需求可以 作为服务提供者的信息输入，帮助确定计划提交的q o s 水平，同时也将对监测系 统产生影响。这四个方面相结合能够准确而全面地对服务质量进行描述。 2 1 3 服务质量控制的目标 q o s 控制的目标是为h l t 锄e t 应用提供服务区分和性能保证。服务区分是指 根据不同应用的需求为其提供不同的服务；性能保证是要解决诸如带宽、丢失、 延迟、延迟抖动等性能指标的保证问题。数据流的分组在网络中传输时，能预测 出可期望的带宽、延迟、抖动和分组丢失是非常重要的。 第二章服务质量保证 2 2 服务质量的主要性能参数 服务质量的性能参数很多，其中主要的参数包括带宽、延迟、延迟抖动和丢 失率等”。 1 带宽。指在特定的网络介质或者协议中额定的吞吐量。q o s 并不能对任何 给定的实际容量产生影响。因此，在q o s 中带宽特指带宽的分配。换言之，没有 任何一种q o s 机制可以产生额外的带宽，它无非是使管理员能更有效地利用带 宽，有时带宽也被称为吞吐量( t h r o u g h p u t ) 。 2 延迟。指数据从网络入口点到达出口点所需要的传输时间间隔。造成网络 延迟的主要因素包括：传播延迟( 信号在物理介质上传输所需要的固有延迟) 、 交换和路由延迟( 网络结点转发数据包的时间) 、排队延迟( 由于i p 网络的统计 复用和数据包到达的异步特性，在结点的输入和输出端口必然要依次排队，这样 数据包才能发送到相应的链路上。排队延迟主要取决于队列长度和数据包在端口 的统计分布) 、跳数。对于某些对时延敏感的应用，时延将直接影响用户对服务 的满意程度。 3 延迟抖动。指分组间到达和离开时的差异，也就是不同分组之间在延迟上 的偏差。由于分组网络固有的不同分组到达时间的可变性，一般情况下，时延变 化是采用网络提供传送服务时必须考虑的一个性能参数。由于大量应用对服务的 时延变化指标较敏感，因此我们必须采取措施来消除或明显降低服务的时延变 化。 4 丢包率。指沿着转发路径所产生的分组丢失。导致分组丢失的因素很多， 比如缓冲器拥塞、线路出错，甚至q o s 机制本身也会有意地丢失分组。丢失率可 以直接影响到最终向用户提交的信息服务质量，无论该服务类型是语音、视频还 是数据。下表列举了常见应用对带宽、延迟、抖动和分组丢失的不同要求。 表2 1 常见应用对数据流的要求 语音f t pt e l n e t 带宽要求低或中中或高低 分组丢失敏感 低 低 中 延迟敏感高低中 抖动 高 低 中 第二章服务质量保证 2 3 服务质量的控制机制 当用户应用与网络系统达成q o s 约定后，网络系统就必须提供基于q o s 的信 息流实时拥塞控制，这种控制是通过q o s 控制机制来实现的【4 】。 q o s 控制主要包括信息传输的实时性和信息丢失率的管理与控制等问题。在 高速网络中，不同用户对传输有不同的要求，要保证信息传输的实时性和不丢失 的综合需求是网络传输控制的一个重要问题。具体而言，q o s 控制主要包括：通 信量管理控制、q o s 路由、基于q o s 的传输调度、缓冲区管理、流量管理和分组 丢弃等。 1 通信量管理控制。主要包括接纳控制、业务整形和监控。接纳控制负责管 理q o s 合同，根据系统拥有的可用资源来决定接收或拒绝用户的申请。业务整形 使通信流的业务特征近似于某个特定的模式，避免分组在网络中的突发性传输。 监控是保证流特性在规定范围内而进行的控制，它和业务整形配合使用来管理不 符合要求的流。 2 q o s 路由。路由机制要完成两个目标：选择满足q o s 需求的路由和从多条 可行的通路中选择一条可以提供高的网络吞吐量的有效路径，包括管理路由信息 和路由算法。 3 q o s 调度算法。调度算法的基本功能是从结点的每一个输出链路中挑选出 在下一个有效期发送的分组。调度控制要基于如带宽的保证、流的隔离、时延的 保证和公平性等原则。算法的复杂性要适应网络高速传输和便于实现，使其具有 可扩展性和鲁棒性。网络中端到端的时延保证包括固定时延( 线路传输时延等) 和排队时延两个部分。固定时延表现了所选通路的特性，可由路由选择算法描述， 而排队时延则由q o s 控制的调度策略决定。 4 流量控制。是拥塞控制的有效方法，大致可以分为开环控制和闭环控制。 5 分组丢弃。路由器在输出缓存完全装满之前可以利用分组丢弃算法丢弃一 个或多个分组以提高整个网络的性能，从而保证关键性任务的服务质量。 q o s 控制的实现是一个端到端的过程，实现q o s 控制的目的是为用户提供多 种类型的综合服务。具体而言，q o s 控制的实现框架包括以下几个部： 1 用户与用户、用户与网络系统的q o s 协商方法与界面。 2 用户q o s 要求的接纳控制。 3 q o s 参数与服务类型的控制分组的定义与实现。 4 资源预留协议。 5 分组调度和队列管理方法。 目前，主要的q o s 控制机制可以分为三种类型：1 网络为实现q o s 保证所需 第二章服务质量保证 要支持的协议，主要包括集成服务( i n t s e r v ) 资源预留协议( r s v p r e s o u r c e r e s e r v a t i o n p r o t o c 0 1 ) 、区分服务( d i f f s e r v ) 两种协议以及它们之间相互结合所派 生出来的协议。2 在网络节点内部实现q o s 保证所需的控制机制和算法，主要包 括队列管理机制和调度算法。3 网络节点对于流量工程的支持。在网络内实现流 量工程的工具包括：多协议标记交换( m p l s m u l t ip r o t o c o ll a b e ls w i t c h i n g ) 、约 束路由、携带链路状态的增强内部网关协议( i g p i n n e r g a t e w a y p r o t o c 0 1 ) 等。 2 4 服务质量的体系结构框架 2 0 0 2 年，i t u t 开始考虑通过规范q o s 体系结构框架来系统地解决电信网全 网的业务服务质量问题【1 】。q o s 网络体系结构框架的核心是规范一套通用的网络 机制，其功能包括：控制特定于某一网元的针对不同业务请求的服务响应，在网 元间交互必要的信令，控制和管理穿越网络的流量等。上述网络控制机制又称为 q o s 构件模块，它与网络处理能力、区分服务、集成服务等实现q o s 保证的具体 方式无关。 目前，正在讨论规范的q o s 构件模块包括接纳控制、拥塞避免、策略及策略 配置、排队和调度、资源预留、服务等级管理、费率表征和流量标识等。每个构 件模块都不可能单独实现网络服务端到端的控制，但通过不同的方式把这些构件 模块组织起来，就可以对网络进行有效的控制，以提供用户业务所要求的q o s 。 将这些构件模块组织起来的结构框架就是q o s 体系结构框架，如下图所示 图2 - 2 服务质量体系结构框架 第二章服务质量保证 目前，q o s 体系结构框架中定义的构件模块可以分为三种模型，并形成了控 制平面、数据平面和管理平面三个相互关联的平面。 1 控制平面内包含了一系列与用户流量传播路径相关的控制机制，这些控制 机制包括接纳控制、q o s 路由和资源预留等。 2 擞据平面内包含的是直接涉及用户流量的控制机制，包括缓存管理、拥塞 避免、分组标记、排队和调度、流量管理等。 3 管理平面内包含的机制涉及网络运营、管理等方面，包括服务等级协议、 流量恢复、流量计量、策略管理等。 本文主要研究的问题是数据平面中有关排队和调度的内容，另一个相关的问 题是流量整形。流量整形控制机制负责控制进入网络的流量速率和数量。流量整 形机制通过对超过平均速率的分组进行排队或保存到缓存区，将突发通信平缓下 来，以满足服务提供者配置的向用户承诺的信息速率( c i r - - e o m m i t t e di n f o r m a t i o n r a t e ) 。经过流量整形降低了流量的突发性，并使其变得更可预测。这部分内容在 之后的关于漏桶模型的介绍中有所涉及。 2 5 综合服务模型和区分服务模型 2 5 1 综合服务模型 i n t e r n e t 最初是面向非实时的、单向数据类型通信( 如文件传输、e - m a i l ) 设 计的，设计时没有关注q o s 控制和管理技术，不能保证网络按照用户所需的质量 要求数据的传输。由于没有必要的对服务质量的控制和保证，这种传统i p 传输 服务被称为尽力而为类型( b e s te f f o r ts e r v i c e ) 的服务。 尽力而为类型服务无法给传输提供好的服务质量保证。于是i e t f 借鉴q o s 技术加强实现资源的控制和调整机制，使得网络能够支持多种服务既能保证有服 务质量需求者的服务又能为原有的尽力而为类型服务，为此提出了综合服务体 系。其主要目的是在网络中提供一定级别的服务质量。 1 9 9 4 年r f c l 6 3 3 率先定义了综合服务模型模型( i n t e g r a t e ds e r v i c e s - - i n t s e r v ) 【4 】，它的基本思想是在传送数据之前根据业务的q o s 要求进行网络资源预留，从 而为给数据流提供端到端的q o s 保证。该模型以标准的资源预留协议( r e s o u r c e r e s e r v a t i o n p r o t o c o l - - r s v p ) 作为实现机制，r s v p 是综合服务的核心。它是一种 信令协议，是一种请求带宽的机制，用来通知网络节点预留资源。发送方发送一 个路径消息给接收方，该消息还收集了中间节点的q o s 能力的信息；接收方处理 第二章服务质量保证 此路径信息后，产生一个预留请求( r e s e r v a t i o n - - r e s v ) ，请求再逆向传输给发 送方，以确保真正的预留资源请求；当发送方接收到该请求后，开始发送数据。 如果资源预留失败，协议会向主机发回拒绝消息。 目前，综合服务模型定义了三种服务类型【2 】：q o s 保证服务型( g u a r a n t e e d s e r v i c e - - g s ) 、受控负载服务型( c o n , o i l e dl o a ds c r v i c e - - c l s ) 和尽力而为服务 型( b e s te f f o r ts e r v i c e - - b e s ) 。 1 q o s 保证服务型。适用于需要固定时延限制的应用。这种服务等级提供明 确的参数级别，能够为用户业务提供时延、带宽、丢包率等性能保证，要求数据 在有保证的时间内到达目的地。 2 受控负载服务型。能够提供最小的传输延时。在提供受控负载的网络中， 应用可以假设网络传输的分组差错率近似于下层传输媒质的基本分组差错率；分 组平均传输时延与网络绝对时延差别不大。 3 尽力而为服务型。是传统的网络所提供的服务，该服务不具有任何q o s 保 证能力。当网络比较宽松时用户能获得较好的服务。然而，当网络拥挤时用户所 获得的服务也随之下降。 r f c1 6 3 3 中指出的综合服务体系结构整体解决方案如下图所示 第一 出一- 鼯 图2 3 综合服务体系结构整体解决方案 1 资源预留协议r s v p 。是i n t e m e t 上的信令协议，通过r s v p 用户可以给每 个业务流或连接申请资源预留，要预留的资源可能包括缓冲区及带宽的大小。这 种预留需要对路径上的每一跳都要进行，这样才能提供端到端的q o s 保证。r s v p 是单向的预留，适用于点到点以及一点到多点的通信环境。 2 接纳控制。当有一个新的流请求时，预留协议就调用接纳控制模块。该模 块要判断对这个流所请求的q o s 网络是否有足够的资源可提供，这个判断是根据 第二章服务质量保证 当前已对其它预留的承诺及网络的当前状况而做出的。如果网络内的路由器共同 认定没有足够的资源来保证所请求的服务质量，则这个流就不允许进入网络。 3 管理代理。网络的管理代理能监督接纳控制模块并且设置接纳控制的策 略；同时它能够修改业务控制数据库，以影响队列调度和分组丢弃。 4 路由选择和路由数据库。通过对数据包分类，路由算法可以根据数据包的 类型、最小代价及其它服务质量参数进行路由选择。同时此路由还维护一个路由 数据库，对每个目的地址和每个数据流都给出应到达的下一站。 5 分类器。根据预留的一些规则对进入路由器的每一个分组进行分类。这可 能需要查看i p 分组里的某些域：i p 源地址、i p 目的地址、上层协议类型、源端 口号、目的端1 2 1 号；分组经过分类以后被放到不同的队列中等待接收服务。这方 面的技术还不很成熟，是一个有待研究的领域。 6 队伍调度器和分组丢弃功能。队伍调度器主要是基于一定的调度算法对分 类后的分组队列进行调度服务。如果许多数据包在输出端口排队时，当数据包使 用完缓冲区时数据包的丢弃策略就是服务质量的一个重要元素。 综合服务模型是一个组织管理严格的q o s 控制方法，能够为每个业务流提供 与其需求相匹配的q o s 保证；r s v p 在源节点和目的节点之间可以使用现有的路 由协议；综合服务模型还可以方便地支持多播业务流。 2 5 2 区分服务模型 综合服务模型基于流的q o s 控制影响了网络的可扩展性。基于每个流的工作 方式需要在路由器中维护保存大量的与分组队列数成正比的状态信息。此外， r s v p 的有效实施必须依赖于分组所经过的路径上的每个路由器。综合服务对路 由器的要求很高，当网络中数据流的数量很大时，路由器的存储和处理能力将面 临很大的压力。 为解决综合服务的缺点，i e t f 在r f c 2 4 7 5 中提出了区分服务体系 ( d i f f e r e n t i a t e ds e r v i c e - - d i f f s e r v ) 。该模型与综合服务模型最本质的区别在于【l 】： 它不是针对每一个业务流进行网络资源分配与q o s 参数配置，而是将具有相似要 求的一组业务归为一类，然后对这一类业务采取一致的处理方式。 区分服务的基本思想是将用户的数据流按照服务质量要求来划分等级，任何 用户的数据流都可以自由进入网络。但是当网络出现拥塞时，级别高的数据流在 排队和占用资源时比级别低的数据流有更高的优先权。区分服务只承诺相对的服 务质量，而不对任何用户承诺具体的服务质量指标。它是一个由多个组件组成的 复杂的体系结构，主要完成分组分类、分组标记、拥塞管理、拥塞避免和流量调 节等任务。 第二章服务质量保证 区分服务只包含有限数量的业务等级，状态信息的数量少，因此实现简单、 扩展性较好。但它属于粗粒度q o s 控制，无法为高层用户提供精确的q o s 控制。 虽然综合服务体系有自身的缺点，但它相对于区分服务体系而言属于细粒度 q o s 控制即可以为高层用户提供较为准确的带宽、延迟、延迟抖动和丢失率控制。 综合服务和区分服务的q o s 控制都不能够完善地满足要求，各有其长处和局限 性。为了支持端到端的q o s 可以考虑将二者相结合，使其相互协作共同实现端到 端的q o s 保证机制。目前，这两种技术的结合仍然是一个开放的研究问题。 2 6 本章小结 本章首先引入了服务质量的概念，之后分别介绍了常见的服务质量参数、服 务质量的保证机制、综合服务模型以及区分服务模型。服务质量的保证是相对于 端对端而言的，分组调度算法主要负责数据包在调度器中转发时的延迟问题，是 一项重要的服务质量保证技术。 第三章有线网络分组调度算法概述 第三章有线网络分组调度算法概述 调度是系统资源管理的核心之一，是解决多个业务竞争共享资源问题的有效 手段。网络系统资源大致包含三个部分：缓冲区、链路带宽、处理器资源。分组 调度按照一定的规则来决定从等待队列中选择哪个分组进行发送，保证所有的输 入流能够按照预定的方式共享输出链路带宽来实现对链路带宽的管理。它影响的 主要性能参数包括带宽分配、时延和时延抖动等，是实现网络服务质量控制的核 心技术。调度的目标是要在满足一定的性能指标和优先约束关系的前提下，将可 并行执行的任务按适当分配策略确定一种分派和执行顺序，以达到减少总的执行 时间的目的。 3 1 分组调度策略 根据分组在系统中的存储位置可以分为三种排队策略：输出排队( o q ) 、输 入排队( i q ) 睁j 和输入输出排队( c i o q ) 。 1 输出排队将到达输入接口的分组立即转移到相应的输出接口进行缓存。分 组在发送前排队由调度算法进行调度输出，可以方便地用于提供服务质量控制， 大多数理论研究成果都是针对这种排队模型的。输出排队的缺点是要求交换机有 很高的加速比，需以n 倍于接口单链路线速的速率工作。当输入接口较多、接 口速率较高时输出排队就无法实现。 2 输入排队把分组首先存储在输入接口中，交换机只要以线速实现交换即 可，可扩展性好。但是，可能发生各个输入接口争用交换机的情况。为了处理这 个问题，需要引入复杂的交换机调度机制以仲裁各输入接口的请求。 3 将以上两种排队方式结合起来就形成了输入输出排队策略。它综合了输入 队列和输出队列的优点，既不需要很大的加速比，便于扩展，又可以有效地避免 拥塞。但这种排队策略尚处在研究阶段，还有许多问题要解决。 3 2 分组调度的功能 一般情况下，分组调度发生在路由器去往下一个路由器或主机的输出接口。 但它可以潜在地存在于路由器内部的任何发生资源竞争而需要排队等待调度的 第三章有线网络分组调度算法概述 地方。当一个分组到达网络节点后，分类器根据分组的上下文和粒度确定它所在 的队列，分组进入相应队列排队等候，直到调度器将其选择发送，如下图所示 图3 1 多队列系统图 如何把输入业务流对应到不同的队列中，不同的调度算法在不同的网络环境 中有不同的方法，需要分类功能和调度规则的配合。虽然分类和调度紧密相关， 但本文只讨论不同业务流所属队列的调度。 每个调度器对应多个队列，这些队列之问共享输出链路容量。何时和如何频 繁地从队列中取出分组进行传输是由调度器中运行的调度算法完成的。当某个队 列中的分组被调度发送时，其余队列只能等待，而每个队列内部仍然采用f c f s 的服务方式。 分组调度规定了分组从队列离开时的瞬间特性，通过流隔离使得不同业务类 型的分组得到不同等级的服务，具体表现为带宽分配、时延范围和抖动控制、不 同业务类之间公平性和相对优先级。 1 带宽分配。调度器可以为特定的业务类提供最低的带宽保证，以确保分组 规则地从该类所在队列中取出；也可以提供速率整形以限制该类的队列被服务的 频率。 2 时延控制。某些实时业务要求严格的时延范围保证和抖动控制，而某些非 实时业务则需要较为宽松的时延控制。对于某个业务类，其平均服务速率r ( s ) 和时延d 存在着关系：q = d r ( s ) ，其中q 表示该服务类所在队列的平均长度。 这个关系可以理解为：调度器通过控制各个业务的服务速率分配来实现对时延特 性的控制。分组公平队列p f q o a a c k e t f a i r q u e u i n g ) 算法采用的就是这种思想。 3 相对优先级控制。调度器使得重要的分组得到最好的服务，次要分组得到 较差的服务，表现出使用共享资源的一定的相对优先级。这种优先级关系可以在 系统初始化时设置为静态优先级，也可以在运行过程中根据系统状态进行调节既 计算动态优先级。 1 4 第三章有线网络分组调度算法概述 3 3 分组调度算法的本质 调度算法是研究分组调度的核心问题，本质上可以理解为从多个对象q ( 0 i s n ) 中选择一个符合某种条件c 的对象q 进行服务。分组调度就是从 多个队列q i 中选择一个符合某种条件的队列q l 进行发送，即从系统中找到一个 关系 ，) 。确定关系( c ，j ) 有两种基本的方法： 1 先确定j 。即假设下一个要服务的队列是q ，然后判断是否满足条件c 。 如果满足为其提供服务，否则判断下一个队列。这种方法可称之为基于轮循的方 法。 2 通过比较判断条件c 来确定j 。按照条件的要求为每个队列动态地计算一 个优先级参数，每次调度具有最大或最小优先级的队列。这种方法可以称为基于 优先级的方法，大部分现有算法可以归结为此类方法。 如果从分组调度的控制过程来看，分组调度就是根据某些与队列相关的信息 进行判断和控制，从而改变队列和系统的状态，实现某种控制目标。分组调度算 法所依据的系统信息可分为两个层面：时间层面和空间层面。 1 时间层面指算法所考虑的信息是静态的( 如静态优先级、权值等) 、当前 的状态信息或历史的状态信息。例如轮循r r ( r o u n d - r o b i n ) 、优先排队 p q ( p r i o r i t y - q u e u i n g ) 都只考虑队列的静态信息即静态优先级。 2 空间层面则考虑不同对象的信息如数据的到达速率、队列长度、分组的等 待时间等。如w f q ( w e i g h t e df a i rq u e u i n g ) 、e d f ( e a r l i e s td e a d l i n ef i r s t ) 考虑了分组 的服务时间、到达时间等状态信息。当然，算法考虑的信息越多就越有效率，但 复杂性也越高。 调度算法的控制目标在某种程度上是与系统服务模型有关的。算法可以进行 带宽分配如d r r ( d e f i c i tr o u n dr o b i n ) ，可以提供服务等级的比例关系如 w t p ( w a i t i n gt i m ep r i o r i t y ) ，也可以提供严格的时延范围保证如e d f 。 调度算法可以分为两种类型：连续工作的( w o r k - c o n s e r v i n g ) 或非连续工作 的( n o n - w o r k - c o n s e r v i n g ) 。1 连续工作类型。只要系统中有分组等待，调度器就 会选择分组进行发送，因此链路利用率很高。2 非连续工作类型。如果输入业 务流在被调度前要进行整形处理，那么系统中有等待分组时调度器也不一定立刻 对其进行调度。虽然链路利用率不如前者高，但可以对端到端时延和时延抖动进 行控制如h r r ( h i e r a r c h i c a lr o u n dr o b i n ) 。 第三章有线网络分组调度算法概述 3 4 分组调度算法的性能指标 分组调度算法可以应用在不同的环境中：可以用来隔离恶意流，为正常的业 务提供服务质量保证；或让用户平等地使用共享链路的带宽。因此，算法应该具 有诸多良好的特性【4 】。 1 有效性。指算法能够实现预期的控制目标，使得各个数据流能够得到事先 约定等级的服务，可以包括资源利用率和时延特性等。资源利用率体现了系统对 调度算法的要求，时延特性则体现了用户对调度算法的要求。 2 公平性。可用的链路带宽必须以公平的方式分配给共享链路的各个数据流， 并且能够隔离不同的数据流让其只享用自己的带宽。关于公平性的定义有服务公 平指数( s e r v i c ef a i r n e s si n d e x - - s f i ) 、最坏公平指数( w o r s e - c a s ef a i r n e s si n d e x - - w f i ) 和r a jj a i n 公平指数( r a jj a i n sf a i r n e s si n d e x ) 等。 3 复杂性。速度的不断提高和规模的不断扩大是网络发展的一个趋势。在高 速网络中，分组调度算法不仅能够在很短的时间内完成分组的调度转发，还要求 算法比较简单且易于实现。但是复杂性和有效性之间是存在矛盾的，考虑的信息 越多算法也就越有效率，复杂性也越高。 4 可扩