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

中文摘要 随着网络技术的飞速发展，网络中承载的实时性业务越来越多。传统网络“尽 力而为 的服务类型不能支持服务质量( q o s ) 保证，给实时性业务的承载带来 诸多不便。q o s 的控制机制由于可以为网络提供服务质量保证而成为下一代高速 网络的核心技术之一。 分组调度算法是为网络提供q o s 保证的一项重要措施，也是q o s 控制机制中 的关键技术之一，如今已成为网络研究与开发的热点问题。有线网络分组调度算 法的研究已经较为成熟，在广义处理机算法的基础上人们提出了许多面向数据包 的调度算法。 无线分组网络中的服务质量保证是其提供实时性业务传输的关键。无线网络 频带资源有限、无线信道易受外界干扰，网络特有的突发性和位置依赖性错误使 得传统的有线网络调度算法不能直接应用于无线网络。无线分组调度算法都是考 虑了无线信道的特点，在有线网络调度算法的基础上提出的。 本文首先对有线网络分组调度算法进行了概述；其次，在研究了处理机共享 模型( g p s ) 基础上研究并实现了了经典算法w f q ( 力i ：i 权公平排队1 ，同时比较了 1 】i f q 算法和p q ( 优先级排队) 算法的优缺点，结合p q 算法的优点对w f o 的调度策略进 行了改进；然后，研究7 w f 2 q ( 最坏情况加权公平排队) 和、肝2 q + 算法，最后， 针对w f 2 q + 支持可变组长的数据包较为复杂的特点，提出了一种支持可变组长的 改进w f 2 q + 算法，并对可用于实现该算法的频率分组的策略进行了初步探索。 通过大量的仿真实验，结果证明结合p q 算法的w f q 算法有更好的时延特性。 支持可变长分组的w f 2 0 + 的改进算法在性能上同w f 2 q + 算法相当，但实现方法要 简单于w f 2 q + 算法。 关键词： 服务质量分组调度公平排队广义处理机共享 a b s t r a c t r e c e n t l yw i t ht 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 er 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 tq o s g 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 g h - 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 n 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 e h 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 n b a s e do 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 l i 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 y a n dl o c a t i o n - d e p e n d e n t e r r o r t a k i n gi n t o a c c o u n tt h e c h a r a c t e r i s t i c so fw i r e l e s s c 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 s a 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 ht h eg e n e r a l i z e dp r o c e s s o rs h a r i n g ( g p s ) a n db a s e do ni tt h ec l a s s i ca l g o r i t h m w f q ( w e i g h t e df a i rq u e u e i n g ) c o m p a r e dw i t hp q ( p r i o r i t yq u e u e i n g ) w ei m p r o v e i t sp r i o r i 够s t r a t e g y n e x t , w ed os o m er e s e a r c ho nw f e q ( w o r s t c a s ef a i r q u e u e i n g ) a n dw f 2 q + t h e ni m p r o v et h ev a r i a b l eg r o u pl e n g t hw f 2 q + f i n a l l y ， m a k eap r e l i m i n a r yd i s c u s s i o no nf r e q u e n c yp e rs e r v i c es t r a t e g y d o i n gal o to fs 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 s b e t t e rd e l a yc h a r a c t e rt h a nt h eo l do n ea n df r e q u e n c yp e rs e r v i c es t r a t e g yi se a s i e rt o b er e a l i z e d k e yw o r d s ：q o s p a c k e ts c h e d u l i n gf a i rq u e u i n gg p s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丕鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者躲暑压、签字眺岬年岬日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 躲3 厉、 辩吼吲年厂月彳同 新躲s 矛 签字同期：2 驴。) 年1 月乏 日 第一章绪论 1 1 研究背景 第一章绪论 计算机和网络是当今两大热点。而计算机技术和通信技术和结合就构成了今 天的i n t e r n e t ，几乎是我们生活中所不可缺少的一大工具，l g 女l e - m a i l ，看新闻， 查资料，网上娱乐等等。在i n t e r n e t 发展的初期，其主要的业务范围集中在电子 邮件、网页浏览、文件传送协议等对服务质量( q u a l i t yo fs e r v i c e - - o o s ) 不 敏感的业务上。目前电信业务发展迅猛，以因特网为代表的新技术革命正在深刻 地改变着传统电信的概念和体系，电信业正在进行一场巨变：新业务层出不穷， 数据业务快速发展，以音频和视频服务为目标的大流量业务需求成为主要的业务 增长点。这些直接导致了近年来电信业的网络结构发生了根本的变化，从原来的 主要支持语音通信的网络转变为提供以数据业务为主的多媒体综合宽带业务网。 综合宽带业务网目前已经从异步传输模式( a t m ) 为主发展为异步传输模式和因特 网协议模式( i p ) 混用共存的局面，并显现出将进一步演变为以i p 为主的趋势。随 着由i p 协议为基础的因特网( i n t e r n e t ) 以新的公共网络的角色出现，用户要求并 期待提高因特网的可靠性和稳定性，并以此支持紧要事务应用。因特网不能再继 续只提供时好时坏的不稳定的服务，它们己经被期望成为像公共电话交换网 ( p s t n ) 一样，用户只要进行通信就能受到高质量的服务。因此用户和电信商都希 望能进一步的提高i p 网络的性能，其中主要就是对q o s 保证的要求。为此而推动 着传输和分组交换技术的进步而新的核心技术如软交换、多协议标签交换( m p l s ) 标签分发协议( l d p ) 、资源预留协议( r s v p ) 等i p 交换技术大量出现n 1 。 目前，运营网络中大量的业务类型丰富的应用开始有分组网络承载。其中， 不乏对服务质量要求较高的实时业务。不同类型的应用对网络有不同的服务质量 要求，在网络资源有限的情况下不可能同时满足所有业务的服务质量要求。因此， 需要有合适的控制机制通过对网络资源的合理分配以尽量满足各种业务的q o s 要 求，这就是所谓的o o s 保证机制乜1 。要在“尽力而为”的传统网络上承载对q o s 敏 感的业务类型，就必须引入有效的q o s 保证机制，将i n t e r n e t 从提供“尽力而为 服务的网络改造成具有良好q o s 保证能力的网络。如今，服务质量不仪在传统的 电信领域里得到了广泛的使用，还逐渐扩展应用于基于分组的宽带、无线和多媒 体等服务领域。与此同时，通信网络和通信系统的设计和规划也越来越多地考虑 到用户应用的端到端性能需求。 1 2 研究现状 第一章绪论 实时性的应用要求网络提供基于q o s 的信息流实时拥塞控制，而这种控制是 通过q o s 控制机制来实现的。具体而言主要包括：通信量管理控制、q o s 路由、 基于q o s 的传输调度、缓冲区管理、流量管理和分组丢弃等。分组调度可以在满 足分组服务质量的前提下，合理安排和控制分组离开调度器的时间和顺序，是服 务质量保证机制中的一项关键技术。无论在综合服务体系还是在区分服务体系中 都涉及队列调度问题。调度算法的基本功能是从节点的每一个输出链路中挑选出 一个有效周期发送的分组。通常这个排队系统由一个或多个队列和一个调度器组 成刳。 ， 输出链路 调度器 图1 1 排队系统的组成 研究者们针对各种网络的特点提出了多种分组调度算法以提高网络传输性 能。其中a b h a y k p a r e k h 于1 9 9 2 年在其博士论文 3 中提出的基于比特流的理想 模型g p s 成为分组调度的公平性参考基础，其分组化的w f q ( 加权公平排队) 算法己 被i e t f 采用。j o nb e n n e t 和h u iz h a n g 等在其论文中分析了w f q 的缺陷，提出了最 坏情况下的w f q 算法耳o w f 2 q h 】，进一步提高了w f q 的性能。他们提出的w f 2 q + 哺3 是目 前所有模拟g p s 算法中最接近理想的一个，同时降低了w f 2 q 的实现复杂度。权值 的概念使分组调度算法摒弃了简单的先到先服务f i f o ( f i r s ti nf i r s t o u t ) f c f s ( f i r s tc o m ef i r s ts e r v e d ) 思想，而要追求更多的公平性，能够同时 提供不同等级的o o s 以适应多种业务要求。主要的调度算法按服务器的工作方式 分两类：连续工作和断续工作。g p s 及模拟g p s 的分组调度算法都属于连续工作型。 此外属于连续工作的还有w r r ( w e i g h t e dr o u n dr o b i n ) 、v c ( v i r t u a lc l o c k ) 、 d e l a y e d d ( d e l a y e a r li e s t d u e d a t e ) 、f f o ( f l u i df a i rq u e u e i n g ) ， s c f q ( s e l f c l o c k e df a i ro u e u e i n g ) 。s f q ( s t a r t t i m ef a i r o u e u e i n g ) ，f f q ( f r a m e - b a s e df a i rq u e u e i n g ) ，s p f q ( s t a r tp o t e n t i a l b a s e d f a i ro u e u e i n g ) ，d r r ( d e f i c i tr o u n dr o b i n ) 。断续工作型如j i t e r e d d ( j i t e r e a r li e s t d u e d a t e ) ，s t o p - a n d - g o ，f i r r ( h i e r a r c h i c a lr o u n dr o b i n ) 。r c s p 2 器 第一章绪论 ( r a t e - c o n t r o l l e ds t a t i cp r i o r i t y ) 等。近年的研究多是对已有算法在特定场 合下的应用与改进。 性能评价标准是进行网络传输控制机制和算法设计的个重要问题。由于传 输控制本身的多目标性，导致了性能评价标准也需要同时考虑多项内容。算法的 性能评价也是一个重要方面。目前有关服务质量的性能评价标准的定义有：服务 公平指数( s e r v i c ef a i r n e s si n d e x ，s f i ) 1 ，最坏公平指数( w o r s t c a s ef a i r n e s s i n d e x ，w f i ) 呻1 ，r a jj a i n 提出的公平度量因子( r a jj a i n sf a i r n e s si n d e x ) 阻1 和比例公平原则，以及林闯等提出的综合性能评价标准n 仉1 1 1 。 1 3 本文的主要工作 分组调度算法是一种重要的服务质量保证措施，也是本文的主要研究对象。 先，在研究有线网络基于g p s 模型的经典算法w f q 的基础上分析了算法的原理以及 较基于优先级的调度算法p q 的优越性，并对w f q 算法中优先权问题加以了改进。 其次，在w f q 算法的改进算法w f 2 q 和w f 2 q + 的基础上，提出一种支持可变组长的 w f 2 q 算法。 1 4 本文的结构安排 本文主要分为六个章节，另外在附录中对离散事件仿真机制进行了简要的介 绍。 第一章绪论。概括介绍了本文的研究背景，研究现状和主要研究内容。 第二章网络q o s 背景。介绍了和服务质量有关的性能参数、控制机制和综合 服务模型区分服务模型等内容。 第三章有线网络分组调度算法的研究现状。详细介绍了有线网络分组调度算 法的研究现状，对各种类型的算法分别进行了说明。 第四章w f q 算法研究与改进。在分析g p s 算法原理的基础上研究t w f q 算法实 现模型，并对w f q 算法进行了优先级方面的改进使其既保证了公平性又综合t p q 算法的优点。 第五章w f 2 q ，w f 2 q + 算法研究与改进。首先，对w f 2 q 和w f 2 q + 算法基本原理 和性能进行了深入研究，并提出一种支持可变长分组的w f 2 q + 算法，在支持变长 分组的前提下降低了w f 2 q + 算法的复杂度。 第六章总结和展望。对全文进行综述并探讨了未来的研究方向。 第二章网络q o s 背景 2 1o o s 的概念 第二章网络o o $ 背景 服务质量( o o s ) 的概念己用于定量和定性描述服务的提供者与接受者之间协 商的服务性能。服务性能可由一些特定的参数描述，服务的提供者允许服务的使 用者在建立连接时对各种服务参数指定希望的、可接受的最低限度值，有些参数 还可以用于无连接的传输服务。服务的提供者根据网络服务的种类或它能获得的 服务来检查这些参数，决定能否提供所要求的服务。典型的参数包括网络带宽、 传输时延、时延抖动和差错率等。在i n t e r n e t 上对网络服务的质量的要求越来越 高( 视频会议、网络电话的实时和带宽要求，大数据量数据备份的完成时间要求 等) 。网络服务质量对于多媒体应用特别重要，这是因为多媒体应用涉及实时音 频、视频通信，对网络的性能有较高的要求。 服务质量基于这样的概念： ( 1 ) 不同的网络提供不同的性能。同一网络也可以为不同的应用提供不同的性能 服务。 ( 2 ) 不同的应用一般需要网络提供的性能也不同。应用程序在开始进行传送信息 数据之前就应该表示对网络性能的要求。 ( 3 ) 当用户提出某一性能的服务，网络也接受了这一服务，则这一性能应能得到 保证。 服务质量这个概念最早起源于邮政网，用来指不同质量的邮递服务，如平邮、 航空、挂号、快递、保险等。x 2 5 公用分组交换网出现后，主要是从吞吐量等级 和不能满足性能要求时拒绝建立服务等方面补充了q o s 的概念。i s d n 和b i s d n 由 于旨在提供综合的业务，所以对q o s 提出了更多的内容。i t u 针对b i s d n 给出的q o s 概念为“一个决定给用户满意程度的服务质量的总效果”。由欧委会r a c e 项目给 出的q o s 定义为：o o s 是展示给用户时，服务好坏程度的衡量，它以用户可以理解 的语言来表达，并通过一系列主观或客观的参数值来显示。按i s o 的概念q o s 是用 来规定所提供的网络服务的好坏程度的。q o s 可用一些规定的参数来表征。 2 2o o s 的分层 传统的q o s ( i s o ) 只是由通信系统的网络层提供的。而对于多媒体通信系统 ( m c s ) o o s 被扩展为与m c s 的4 个层次，即用户层、应用层、系统层、设备及网络 层对应的o o s 图2 一l 表示了q o s 的分层模型。 4 第二章网络q o s 背景 2 3o o s 的量化指标 图2 1q o s 的分层模型 q o s 是由一系列具体的，可度量的，可量化的参数来表征的，这些参数称为 服务质量的量化指标。服务质量的量化指标主要可以分为两类： ( 1 ) 呼叫与连接速度 用户感知到的服务质量的一个重要方面，是其服务流量所经历的时延。时延 是数据分组在网络的两个节点之间传送的平均往返时间。时延主要从以下方面对 不同服务产生不同的影响：端到端时延( e n d t o - e n dd e l a y ) ；时延变化( 即抖动， j i t t e r ) 。 交互式的实时应用程序( 如语音通信等) 对端到端时延和抖动很敏感，如果时 延大，则对通信的交互性有所削弱。 非交互式的实时应用程序( 如单向广播等) 对端到端时延不敏感，但对抖动 敏感。 非实时应用程序往往对时延不敏感。不过，由于这些应用可能会用时延指标 来控制其流量速率( 如t c p ) ，或在应用得到响应前需要对数据进行缓存( 安i f t p ) ， 所以时延和抖动也可能影响这些应用的质量。 端到端的时延可以分成两个部分：固定时延和可变时延。固定时延包括编码 解码时延和打包时延。固定时延式是和采用的压缩算法，打包的语音数据量相关 的。这部分时延的优化可能性不大，通过选择合适的压缩算法，减少打包数据量， 合理分配数字信号处理器的负荷，采用设计良好的流水线处理流程等方法可以改 进这部分的时延。 可变时延包括：排队缓存时延，串行化时延，去抖时延。这些和设备的端 5 第_ 二章网络q o s 背景 口速率，网络的负载情况，经过的网络路径，设备对q o s 的支持方式，实现的0 0 s 算法等密切相关。特别是去抖时延与承载网络的抖动指标密切相关，通过采用合 适的网络技术可以显著降低语音通过网络时引用的抖动，从而减少去抖时延。 另外一个比较重要的参数是端到端的时延抖动边界。在连续的多媒体回放 中，理想的情况是网络能提供一个固定不变的时延，或者说是零抖动。在网络中， 得到有界时延抖动的服务意味着目标节点可以计算出缓冲区的数目以消除抖动。 抖动的边界越小，则需要的缓冲空间越少。因为提供端到端的时延和抖动边界比 平均时延的降低更重要，所以分组过早的到达在这种情况下并不一定是好事。事 实上，分组到达的越早于时延边界或者回放点，它就要越长时间的占用缓冲区。 这是保证性能服务和传统计算机网络提供的尽力而为的服务之间最大的不同。后 者更注重于平均的性能指标，而对于前者，有界的性能参数是非常重要的。 ( 2 ) 网络数据的传送速度( 吞吐量) 吞吐量的主要指标是应用可用的带宽大小。吞吐量决定应用可以在网络传输 的流量速率。吞吐量取决于以下因素：链路特性：带宽，出错率；节点特性：缓 冲区容量，处理机能力。 分组丢失率也是比较重要的指标。分组的丢失一般发生在缓冲溢出或者是超 过时延边界。传输过程中丢失某些分组不可避免，而视频和音频数据的实时性不 允许其数据分组重发，这样的情况下也会增加分组的丢失率。对接受端而言，数 据包丢失率是质量的重要衡量指标。 终端主机、链路、交换栅路由器等网络元素的特征，通过时延和吞吐量的 尺度，共同决定了提供给应用的服务质量。下表列举了常见应用对带宽、延迟、 抖动和分组丢失的不同要求。 表2 一l 常见应用对数据流的要求 语音f t pt e i n e t 带宽要求低或巾巾或高低 分组丢失敏感 低低 中 延迟敏感 高低 由 抖动 古 低 由 i n j 2 40 0 s 的分类 对q o s 进行分类和定义的目的是使网络可以根据不同类型的q o s 进行管理和 分配资源。如，给实时服务分配较大的带宽和较多的c p u 处理时间等，另一方面， 对q o s 进行分类定义也方便用户根据不同的应用提出q o s 需求。从q o s 的严格程度 6 第二章网络q o s 背景 来分，可以认为o o s 有以下几个种类： ( 1 ) 确定型( d e t e r m i n i s t i c ) o o s 承诺 在通信过程中，提供o o s “硬”保证，确保通信各方协商好的各o o s 参数值， 不允许有任何违背，否则可能会造成严重后果。这类服务一般用于硬实时应用。 例如，远程医疗诊断这样的分布式多媒体应用，就需要这类服务来支持诸如患者 的x 射线影像数据的实时无差错传送。 ( 2 ) 统计型( s t a t i s t i c a l ) q o s 承诺 在通信过程中，提供o o s “软”保证，允许对通信各方协商好的各q o s 参数值 有一定比例的违约，适合于软实时应用。例如，对于分布式多媒体信息点播服务 中的影片点播来说，用户通常可以容忍一定数量的比特错和帧丢失。 ( 3 ) 尽全力型( b e s t e f f o r t s ) q o s 承诺 不提供任何量化的o o s 保证，只承诺提供所能给予的最好服务。这并不是严 格意义上的o o s 。目前由于带宽的限制，广域网( 如i n t e r n e t ) 中的分布式多媒体 服务多属于这类服务。在这种网络中，服务是相当低质量且不可靠的。 2 5o o s 的实现机制 q o s 的实现是一个系统的工程，由七大部分组成。分别是呼叫接纳控制，拥 塞控制，报文分类，流量成形，队列管理，分组调度和q o s 路由。图2 2 n 显示了 支持q o s 的输入输出队列结构路由器中分组出来流程。集中体现了各种o o s 技术的 分工协作。以下将对其进行分别介绍。 厂q o s 控制、 流分类 物理 卜 流量整形 a 缓存分组 a 物理 一 八输入八交换 队列 输出 调度 队列 叫 设备 设备 刊。 策略控制 叫 队列 叫 机构 叫 管理器 路由表查找 图2 2 支持q o s 的路由器中分组处理流程 1 呼叫接纳控制 呼叫接纳控制是指，当用户要求建立一个通信连接时，呼叫接纳控制机制根 据首先查看该连接所提出的q o s 要求( 包括时延、时延抖动、丢失率等要求) ，判 断网络可用的资源是否能够满足该连接的要求。如果不能，则该连接被拒绝。这 样作的目的是为了避免因新业务的加入而影响到己经建立起来的业务流的服务 7 第二章网络q o s 背景 质量。 2 拥塞控制 拥塞是指一种持续过载的网络状态，指用户对网络资源的需求超过了其固有 容量的限制。拥塞的结果是分组丢失率提高，分组端到端时延加大，甚至有可能 使整个网络发生崩溃拥塞控制本质上是如何共享资源的问题。这里的资源包括链 路带宽，存储空间和处理器能力等。拥塞控制的实现主要从两方面考虑。一是增 加系统资源，二是降低用户需求。前者一般通过动态配置网络资源来实现，如在 高峰期增加接入线路，使用多路径等方法。后者则通过三种方法实现，包括拒绝 服务，较低服务质量，合理调度安排用户对网络资源的使用( 如加入轮循，优先 级，资源预留等) 。拥塞控制的研究最初并非源于对q o s 的需要，但在强调业务模 型的新型网络体系结果中，如何通过增强的拥塞控制为q o s 的实现提供一定的便 利，也成了研究热点之一。 3 报文分类 报文分类是指分组交换网络中路由器基于一个或多个报文头字段或报文内 容，把报文分类到相应的流服务类的过程。所有同属一个流的报文应遵循实现约 定的规则，又路由器按照相同或相近的方式进行处理。报文分类用在0 0 s 、拥塞 控制、入侵检测、负载均衡等技术当中，在1 p 网络中能否实现高速、准确的报文 分类直接影响到上述技术的效能。 4 流量成形 流量成形是指在数据传输过程中，路由器根据约定的传输模式调整数据传输 的平均速率以达到传输没事规定的速率。流量成形主要采用两种基本算法：漏桶 ( 1 e a k yb u c k e t ) 算法和令牌桶( t o k e nb u c k e t ) 算法。流量成形的作用是避免突发 通信导致的拥塞问题。 5 队列管理 从排队论的观点看，可以把分组流经路由器的过程用客户一服务模型来描 述。在路由器中设置队列缓冲的目的是通过一定程度上增大客户等待时间一分组 排队时延，来提高服务器利用率一输出链路的带宽利用率。队列管理主要指缓冲 管理，又名丢弃控制，指路由器依据一定规则决定缓冲队列中的或新到达的分组 是否应当丢弃。 缓冲管理直观的作用虽然只是影响分组丢失率，但是对q o s 仍有着不可忽视 的意义。首先，合理的系统队列缓冲区容量，对平衡系统容量和分组排队时延起 着至关重要的作用。其次，在多队列( 意味着多服务类别) 情况下，缓冲长度作为 一种资源，如何在队列间合理分配，涉及到服务公平性问题。 6 q o s 路由 8 第二章网络q o s 背景 路由机制要完成两个目标：选择满足q o s 需求的路由和从多条可行的通路中 选择一条可以提供高的网络吞吐量的有效路径，包括管理路由信息和路由算法。 7 分组调度 分组调度指按照一定规则来确定等待队列中各个分组的发送顺序。一是所有 输入业务流能够按照预定的方式共享输出链路带宽。它影响的主要参数性能包括 带宽分配，时延，时延抖动等。分组调度是实现网络服务质量控制的一项关键技 术。 综上所述，为了保障服务质量，现代分组交换网络采用了多种技术，综合协 作，成为一个q o s 支撑系统二前述的每一种技术对o o s 都有重要意义。而本文重点 考察其中的分组调度技术，特别是基于g p s 模型的分组公平调度算法。 2 6q o s 网络的服务模型 尽力而为服务模型( b e s t - e f f o r t ) 是传统e p 网络使用的服务模型。综合服务 模型( i n t s e r v 模型) 是i e t f 第一个支持基于数据流提供q o s 保证的服务模型。它要 求沿着端到端相对复杂的分类、排队和调度结构。区分服务模型( d i f f s e r v 模型) 被看作是i n t s e r v 模型的对应结构。它提供两至三个基本的汇聚业务级。通过扩 展数据包的分类规则，d i f f s e r v 模型也可以提供多个汇聚业务级。 2 6 1 尽力而为服务模型 b e s t - e f f o r t 模型是一种单一的网络服务模型，也是最简单的网络服务模型。 对b e s t - e f f o r t 模型来说，应用程序可以在任何时候向网络发出任意数量的报文， 而不需要事先获得网络的批准，也不需要通知网络。网络尽最大可能发送报文， 对报文传输的时延、时延抖动、可靠性、丢包率等性能不提供任何保证。 b e s t - e f f o r t 模型是传统i n t e r n e t 网络采用的缺省服务模型，适用于绝大多 数网络应用，如f t p ，e - m a i1 等。它通过先进先出( f i f o ) 队列来实现 2 6 2 综合服务模型 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 ) 1 ，它的基本思想是在传送数据之前根据业务的q o s 要求进行网络资源 预留，从而为给数据流提供端到端的q o s 保证。该模型以标准的资源预留协议 ( 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 - - r s v p ) 作为实现机制，r s v p 是综合服务的 核心。它是一种信令协议，是一种请求带宽的机制，用来通知网络节点预留资源。 发送方发送一个路径消息给接收方，该消息还收集了中间节点的o o s 能力的信息； 接收方处理此路径信息后，产生一个预留请求( r e s e r v a t i o n - - r e s v ) ，请求再 逆向传输给发送方，以确保真正的预留资源请求；当发送方接收到该请求后，开 9 第二章网络q o s 背景 始发送数据。如果资源预留失败，协议会向主机发回拒绝消息。 目前，综合服务模型定义了三种服务类型n 副：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 t r o l l e dl o a ds e 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 尽力而为服务型。是传统的网络所提供的服务，该服务不具有任何o o s 保 证能力。当网络比较宽松时用户能获得较好的服务。然而，当网络拥挤时用户所 获得的服务也随之下降。 r f c l 6 3 3 中指出的综合服务体系结构整体解决方案如图2 3 所示： 图2 3 综合服务体系整体解决方案 哥 1 资源预留协议r s v p 。是i n t e r n e t 上的信令协议，通过r s v p 用户可以给每 个业务流或连接申请资源预留，要预留的资源可能包括缓冲区及带宽的大小。这 种预留需要对路径上的每一跳都要进行，这样才能提供端到端的o o s 保证。r s v p 是单向的预留，适用于点到点以及一点到多点的通信环境。 2 接纳控制。当有一个新的流请求时，预留协议就调用接纳控制模块。该模 块要判断对这个流所请求的q o s 网络是否有足够的资源可提供，这个判断是根据 当前已对其它预留的承诺及网络的当前状况而做出的。如果网络内的路由器共同 1 0 第二章网络q o s 背景 认定没有足够的资源来保证所请求的服务质量，则这个流就不允许进入网络。 3 管理代理。网络的管理代理能监督接纳控制模块并且设置接纳控制的策 略：同时它能够修改业务控制数据库，以影响队列调度和分组丢弃。 4 路由选择和路由数据库。通过对数据包分类，路由算法可以根据数据包的 类型、最小代价及其它服务质量参数进行路由选择。同时此路由还维护一个路由 数据库，对每个目的地址和每个数据流都给出应到达的下一站。 5 分类器。根据预留的一些规则对进入路由器的每一个分组进行分类。这可 能需要查看i p 分组里的某些域：i p 源地址、i p 目的地址、上层协议类型、源端 口号、目的端口号；分组经过分类以后被放到不同的队列中等待接收服务。这方 面的技术还不很成熟，是一个有待研究的领域。 6 队伍调度器和分组丢弃功能。队伍调度器主要是基于一定的调度算法对分 类后的分组队列进行调度服务。如果许多数据包在输出端口排队时，当数据包使 用完缓冲区时数据包的丢弃策略就是服务质量的一个重要元素。 综合服务模型是一个组织管理严格的q o s 控制方法，能够为每个业务流提供 与其需求相匹配的q o s 保证；r s v p 在源节点和目的节点之间可以使用现有的路由 协议；综合服务模型还可以方便地支持多播业务流。 2 6 3 区分服务模型 综合服务模型基于流的q o s 控制影响了网络的可扩展性。基于每个流的工作 方式需要在路由器中维护保存大量的与分组队列数成正比的状态信息。此外， r s v p 的有效实施必须依赖于分组所经过的路径上的每个路由器。综合服务对路由 器的要求很高，当网络中数据流的数量很大时，路由器的存储和处理能力将面临 很大的压力。 为了解决i n t s e r v 模型存在的缺点，i e t f 在r f c 2 4 7 5 提出了d i f f s e r v 模型，旨 在定义一种能够提供q o s s 。匕力且更容易扩展的方式。该模型与综合服务模型最本 质的区别在于：它不是针对每一个业务流进行网络资源分配与q o s 参数配置，而 是将具有相似要求的一组业务归为一类，然后对这一类业务采取一致的处理方 式。 在d i f f s e r v 模型中，网络好像一个具有反馈控制的系统，应用程序在发送数 据包之前不需要向网络请求资源分配，网络也不需要为每个数据流维持状态网 络根据数据包携带的q o s 标识决定需要为数据包提供的服务质量保证。这种标识 符可以是数据包中的优先级b i t ，源和或目的地址，v l a nt a g 等。d i f f s e r v 模型 非常适合于聚合后的数据流，因为这种数据流己经进行了一般的业务流分类。在 d i f f s e r v 模型中终端节点监测网络状态，根据网络状态调节输出业务流量，在不 引入拥塞的情况下公平共享网络资源。当网络发生拥塞时，信源在一个往返的时 第二章网络q o s 背景 间内被通知。信源根据通知减少注入网络中的流量以减轻网络拥塞。 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 模型中引入了域( d o m a i n ) 的概念。一个d i f f s e r v 域可以认为是一 个能够提供d i f f s e r v 业务的子网( 如图3 4 所示) d i f f s e r v 域主要由一些路由器 组成。位于d i f f s e r v 域边界的路由器称为边界路由器( e d g er o u t e r ) ，位于 d i f f s e r v 域内部的路由器称为核心路由器( c o r er o u t e r ) c r 是具有c q s ( c l a s s i f i c a t i o n ，q u e u i n ga n ds c h e d u l i n g ) 能力的高速路由器，而e r 速度较慢， 但具有更高级的c q s b 邑力边缘一核心模型可以使c r 采用硬件实现，以获得很高的 处理速度，而将更加复杂的、速度慢的处理留给基于软件的e r e r 可以实现几百 或上千个数据流的分类和排队，同时平滑注入网络中的业务流的突发性，而在c r 中通常只设定少数队列。在c r 中多种业务流将被汇聚到同一个共享队列中，业务 流之间相互影响的不可预测性很大，解决这个问题的方法是：在业务流进入c r 之 前，由e r 处理每一个业务流，同时对各业务流进行汇聚，在业务流到达c r 之前就 提供某种级别的可预测性。d i f f s e r v 域力图通过分类、整形、排队和调度对业务 流提供q o s 保证。d i f f s e r v 模型同样定义了三种业务类型： 图2 4d if f s e r v 域结构 1 有严格带宽和时延要求的实时业务( g u a r a n t e e ds e r v i c e s ) ：对带宽、时 延、时延抖动和分组丢失率提供定量的保证。 2 控制负载业务( c o n t r o l e dl o a ds e r v i c e s ) ：保证即使在网络过载的情况 1 2 第二章网络q o s 背景 下，也能向业务流提供近似于网络未过载的服务质量保证，即在网络发生拥塞的 情况下，也能保证某些业务流的低时延和高通过率。 3 尽力而为业务( b e s t - e f f o r t ) ：类似于目前i n t e r n e t 中提供的服务，是一种 尽力而为的工作方式，基本上无任何质量保证。 区分服务只包含有限数量的业务等级，状态信息的数量少，因此实现简单、 扩展性较好。但它属于粗粒度q o s 控制，无法为高层用户提供精确的q o s 控制。虽 然综合服务体系有自身的缺点，但它相对于区分服务体系而言属于细粒度。 q o s 控制即可以为高层用户提供较为准确的带宽、延迟、延迟抖动和丢失率 控制。综合服务和区分服务的q o s 控制都不能够完善地满足要求，各有其长处和 局限性。为了支持端到端的q o s 可以考虑将二者相结合，使其相互协作共同实现 端到端的q o s 保证机制。目前，这两种技术的结合仍然是一个开放的研究问题。 2 7 本章小结 本章简要介绍了服务质量的概念，之后分别介绍了常见的服务质量参数、服 务质量的保证机制和q o s 网络常用的三种服务模犁和网络处理器的基本原理，从 中可以看出1 ) i f f s e r v 模型是目前q o s 网络最主要的服务模型。服务质量的保证 是相对于端对端而言的，分组调度算法主要负责数据包在调度器中转发时的延迟 问题，是一项重要的服务质量保证技术。 第三章分组调度算法 第三章分组调度算法 传统的i n t e r n e t 只提供尽力而为的服务，与此对应的网络应用( 例如e m a i l ， f t p ，t e l n e t ，等等) 也都是非实时的，因此路由器中通常只使用f i f o ( 先进先出) 队列来调度分组的发送。也就是说，所有进入路由器的分组按到达时间的先后次 序被放到同一个队列中，当路由器需要发送分组时按f c f s ( 先到先服务) 原则从 队首取出分组予以发送。在这种情况下，分组在路由器内的停留时间、单个流的 分组丢失率等因素俱无法得到保证，因此路由器提供的只能是尽力而为的服务。 这与早期i n t e r n e t 传输速率低、主要业务为非实时业务的特征是一致的。 随着网络技术的发展，i n t e r n e t 上出现了许多新的应用，例如1 p 电话、视频 点播、远程教育、远程会议、远