（计算机应用技术专业论文）基于qos控制的分组调度算法的研究.pdf

摘要 随着h t e m c t 的飞速发展，各种新业务的迅猛发展，尤其是视频、语音等多媒体业务 ( 如视频会议、视频点播、i p 可视电话) 的迅猛增长，i p 网络也由以前单一的数据网变 成了多业务的综合数字网。正是由于各种多媒体应用的推动，在当前高速网络中按照用 户的要求提供q o s 控制成为一个普遍的要求，也是h l t c m c t 发展的重要挑战。因此， 研究分组调度算法，以获得更优的资源分配方案，实现q o s 性能要求是具有重要意义 的。 本文首先总结了计算机网络o o s 控制研究现状和发展趋势，较完整地分析了实现 网络q o s 控制的两种体系结构i i l t s e 和d i f f s e r v 。然后对网络q o s 控制的关键技 术分组调度机制进行了深入的研究。分组调度是网络资源管理的重要内容，通过控 制不同类型的分组对链路带宽的使用，使具有不同服务质量q o s 要求的数据流得到不 同的服务。目前比较成熟的分组调度算法主要包括先来先服务调度算法、优先级调度算 法、循环调度算法、加权公平排队算法等。 本文重点研究了g p s 模型及p g p s 算法中w f q 算法，通过对w f q 算法无法 保证实时业务的q o s 这一现象及其原因的深入分析，发现其在公平性方面存在着不区 分会话优先级缺陷。在此基础上本文提出了一种基于服务分类的加权公平排队算法 s c w f q ( w f o b a s e do ns e r v i c co a s s ) 。该算法通过对服务分类，将实时业务与非实时 业务区分开，对分属于不同类别的业务流采用不同的带宽分配方法，首先满足实时业务 对延时的要求，使得实时业务的服务质量在链路带宽不足的情况下得到有效的保证。 本文还进一步对算法的实现进行了仿真实验。通过l i n u x 下的网络仿真软件n s 一2 网络模拟器在同样拓扑结构的网络和链路、带宽、信息源等环境下对w f q 和s c w f q 两种调度算法进行了仿真实验，来检测新算法的实现并对比两种算法性能。结果给出了 s c w f q 算法有效控制了实时业务的最大延时，改进了它们的q 0 s 性能。 本文由六部分组成，第一章介绍了研究背景和意义；第二章比较了综合服务模型和 区分服务模型；第三章研究了调度及其相关概念，并对比研究了目前比较成熟的几种分 组调度算法；第四章针对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 ，v a r i o u sn e wa p p l i c a t i o n si n e a s ec o n t i n u o u s l y , e s p e c i a l l yf o rt h em u l t i m e d i as e r v i c e ss u c ha sv i d e o c o n f e r e n c e ，v i d e o - o n d e m a n d ，v i s u a l t e l e p h o n eo v e r i p i pn 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 kf r o mt h es i n g l e d i g i t a ln e t w o r k w i t ht h ed e v e l o p m e n t o ft h em u l t i m e d i aa p p l i c a t i o n s ，p r o v i d i n gq o sc o n t r o l a c c o r d i n gt ot h ec u s t o m e r s r e q u i r e m e n t sb e c o m e sp o p u l a r , w h i c hi s a l s oa ni m p o r t a n t c h a l l e n g eo fi n t e m e 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 ea n d m 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 ts c h e d u l i n ga l g o r i t h m sa r eo fg r e a ti m p o r t a n c e i nt h i sp a p e r , w ef i r s t l yg i v ear e v i e wo fr e s e a r c ha n dd e v e l o p m e n to fq o sc o n t r o l ，a n d i n t s e r va n dd i f f s e r va r ea n a l y s e da n dd i s c i l s s e d t h e nw es t u d yp a c k e ts c h e d u l i i l g m e c h a n i s md e e p l y p a c k e ts c h e d u l i n gi st h ek e yt e c h n i q u eo fo o sc o n t r o la n di ti sa n i m p o r t a n tp a r to fr e s o u r c em a n a g e m e n t b yc o n t r o l i n gt h eu s eo fl i n kb a n d w i d t h , a c c o r d i n g t or e q u i r e m e n t so fq o s ，d i f f e r e n tf l o w sg e td i f f e r e n ts e r v i c e s n o w a d a y s ，c o m m o np a c k e t s c h e d u l i n ga l g o r i t h m sm a i n l yi n c l u d ef i r s tc o m ef i r s ts e r v i c ea l g o r i t h m ，p r i o r i t yo u e u e i n g a l g o r i t h m ，r o u n dr o b i na l g o r i t h m ，w e i g h t e df a i rq u e u e i n ga l g o r i t h ma n de t c t h i sp a p e rf o c u s e so i lg p ss y s t e ma n ds t u d i e so n eo fp g f sa l g o r i t h m s - w f q a c o r r d i n gt ot h ed e e pa n a l y s i so ft h ep h e n o m e n o na n dt h er e a s o nw h yw f q c a n n o te n s u r e t h eq u a l i t yo fr e a l - t i m es e r v i c e ，t h ep a p e rp o i n t so u tt h es h o r t c o m i n ge x i s t i n gi nt h ef a i r q u e n e i n gp r i n c i p l eo fw f oa l g o r i t h m w er e a l i z et h a tw f qd o e s n td i s t i n g u i s hs e s s i o n s p r i o r i t ya n dp r o p o s et h es c w f qa l g o r i t h mb a s e do ns e r v i c e sc l a s s 1 1 l ep r o p o s e da l g o r i t h m d i s t i n g u i s h e sb e t w e e nr e a l t i m es e r v i c ea n dn o m c a l - t i m es e r v i c ea n dd i s t r i b u t e sb a n d w i d t h b a s e do ns e r v i c e sc l a s st of i r s t l yf u l f i lt h er e a l - t i m es e r v i c e 。sr e q u i r e m e n to fd e l a y 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 研d t hi si n a d e q u a t e ，s c w f qe n s u r e st h eq u a l i t yo fr e a l - t i m e s e r v i c e i nt h i sp a p e r , w ea l s oi n t r o d u c et h ea r c h i t e c t u r ea n dm a i nc o m p o n e n t so fn s t h e nw e s i m u l a t et h ew f qa l g o r i t h ma n dt h es c w f qa l g o r i t h mu n d e rn e t w o r ks i m u l a t o rb a s e do n t h es a m en e t w o r kt o p o l o g y , l i n k , b a n d w i d t h , a n ds o u r c et oc o m p a r es c w f qw i t hw f qi n t h ep e r f o r m a n c e a n dt h es i m u l a t i o nr e s u l t ss h o wt h a tt h es c w f qa l g o r i t h mc o n t r o l st h e d e l a yo fr e a l - t i m es e r v i c ee f f i c i e n t l ya n di m p r o v e t h eq o sp e r f o r m a n c e t h i sa r t i c l ei sm a d eu po f6p a r t s s e c t i o n1i n t r o d u c e st h eb a c k g r o u n da n ds i g n i f i c a n c e o ft h ei n v e s t i g a t i o n s e c t i o n2c o m p a r e st h ei n t e g r a t e ds e r v i c e sw i t ht h ed i f f e r e n t i a t e d s e r v i c e s i ns e c t i o n3 ，w es t u d ys c h e d u l i n gm e c h a n i s ma n ds e v e r a lc o m m o np a c k e ts c h e d u l i n g a l g o r i t h m s s e c t i o n4a n a l y s e st h es h o r t c o m i n g o ft h ew f o a l g o r i t h ma n dg i v e sam e t h o dt o s o l v et h i sp r o b l e m s e c t i o n5g i v e st h es i m u l a t i o no ft h es c w f qa l g o r i t h m i c i nt h ef i n a l p a r t ，s e c t i o n6 w eg i v ea s u m m a r i z a t i o no ft h i sp a p e ra n dw e s e n tt h en e x tw o r kw ew i l ld o k e yw o r d s ：q o s ，p a c k e ts c h e d u l i n g ，s e r v i c e sc l a s s ，w f q ，r e a l t i m es e r v i c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得丞洼理王太堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：蓝衙祆 签字日期：抽7 年，月莎日 学位论文版权使用授权书 本学位论文作者完全了解丞洼理王太堂有关保留、使用学位论文 的规定。特授权丞洼堡王太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：蓝奔认 签字日期：加7 年f 月莎日 第一章绪论 1 1 研究背景和意义 第一章绪论 在早期计算机网络和分组转发网中，网络只提供尽力而为( b e s te f f o r t ) 的服务。这 种网络系统对所有进入网络的业务流( 视频、图像或数据) 都是按照先来先服务的方式 进行服务。这种方式能很好地满足没有时延和带宽约束的纯数据服务( 如f t p 和e - r e a l l 的传输) 。 随着高速网络技术的飞速发展，各种业务的迅猛发展，尤其是视频、语音等多媒体业 务( 如视频会议、视频点播、i p 可视电话) 的迅猛增长，i p 网络也由以前单一的数据网 变成了多业务的综合数字网。这些新的应用不仅包括文本数据信息，还包括语音、图形、 图像，视频、动画等类型的多媒体信息，因此对网络提出了新的要求，如分布式多媒体 应用，不但对网络有很高的带宽要求，而且要求信息传输是低延迟和低抖动，同时，这 些应用大都能够容忍一定程度的信息丢失和错误。这种应用对网络的各种要求被称为网 络服务质量( q u a l i t yo f s e r v i c e ，q o s ) 要求【l l 。 正是由于各种多媒体应用的推动，在当前高速网络中按照用户的要求提供q o s 控 制成为一个普遍的要求，也是i n t e r n e t 发展的重要挑战。多媒体信息传输与管理的q o s 控制技术已经成为国际网络研究领域中最重要的研究方向之一。这种情况下，针对如何 有效的提高和改善网络中的服务质量这一问题，各个研究团体纷纷开始组织大规模的 q o s 研究，一些大的通信厂商也联合成立了q o s 论坛，协商各种q o s 技术标准的实 施方案。截至目前，各种方面的解决方案层出不穷，如流分类、路由协议等等。这其中， 比较行之有效且被大家所公认的一种解决方式就是分组调度算法。 分组调度算法决定了被服务的分组接收服务的顺序，使其所在的数据转发设备能够 智能的控制数据转发的优先级，每条链路的带宽以及平均时延等特性以满足一定程度上 的服务质量。因此研究基于网络o o s 控制的调度算法是非常必要而且迫切的。 1 2 网络服务质量 1 2 1q o s 的概念描述 q o s 服务质量，它有多种定义形式。 r f c 2 3 8 6 1 2 l 中描述为：q o s 是网络在传输数据流时要求满足的一系列服务请求，具 体可以量化为带宽、延迟、延迟抖动、丢失率、吞吐量等性能指标此处的服务具体是 指数据流经过若干网络节点所接受的传输服务，强调端到端的或网络边界到边界的整体 性。q o s 反映了网络元素( 例如：应用程序、主机、或路由器) 在保证信息传输和满 足服务要求方面的能力。 第一章绪论 另一种描述【3 j 为：q o s 是指发送和接收信息的用户之间以及用户与传输信息的综合 服务网络之间关于信息传输的质量约定。该约定可以被理解为服务提供者与用户之间的 一份服务契约，即服务提供者承担支持给定的服务质量，当且仅当用户按照约定的信息 流特征产生数据。换句话说，服务质量包括用户的要求和网络服务提供者的行为两个方 面，是用户与服务提供者两方面主客观标准的统一。用户的要求是指用户在i n t e m e t 上 进行多媒体通信时所要求的服务类型以及相应的传输性能和质量问题等；网络服务提供 者的行为则指i n t e r n e t 针对某一类服务所能提供和达到的性能与质量。 q o s 控制的目标是为i n t e r n e t 提供服务区分和性能保证：服务区分是指根据不同 应用的需求为其提供不同的服务；性能保证则要解决诸如带宽、丢失、延迟、延迟抖动 等性能指标的保证问题。然而在网络中，特别是在i n t e m e t 这样大规模的全球网络中提 供q o s 保证绝非易事，它需要自顶向下的所有网络层( b p l s o o s i 模型中的第1 层至第 7 层) 以及端到端( 即从信息的发送者到接收者) 的所有网络元素的整体协作i l j 。 1 2 2 性能参数 i p q o s 的研究目标是有效地为用户提供端到端的服务质量控制或保证，它通过以下 的性能参数来衡量网络传输各种业务的性能： 1 端到端的时延：指发送端与接收端之间发送和接收数据包的时间间隔，它主要 是由分组在路由器中的等待时间和服务时间引入的。 2 时延抖动( j i t t e r ) ：指端到端传输时延的变化，即相邻两个分组到达接收端的 时间间隔相对与发送端发送这两个分组的时间间隔之间的差值。 3 丢包率：指在分组传输过程中，丢失的分组数与源端发送的分组数之比。分组 的丢失主要是由出错或者网络拥塞引起的。在o o s 解决方案设计时应充分考虑到不同 业务对丢包率的要求。 4 吞吐量：指单位时间内有多少数据进入网络( 网络中发送分组的速率) ，可用平 均速率或峰值速率表示。网络吞吐量就是它的有效带宽。 以上四个性能参数也是调度算法所要满足的基本要求。 1 2 3 实施方案 为了解决i p q o s 问题，i n t e m e t 工程任务组i e t f ( i n t e m e t e n g i n e e r i n g t a s k f o r c e ) 于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 ) 1 4 j 和 区分服务模型( 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 ) p l o 其中，i n t s e r v 的基本策略是基于资源预留，即网络资源按照某个业务的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 ) 1 6 是i n t s e r v 的核心部分。这种方法是按照服务水平的要求给每一个数据流分配资源，当数 据流数目很多时，网络的扩展性会受到很大的影响。因此，这种采用“资源预留”进行 2 第一章绪论 带宽分配的方法并不适合“尽力而为”型应用。 由于带宽资源是有限的，o o s 的设计者引入了优先级概念，使得在资源预留后“尽 力而为”服务的数据流的传输也能得到一定的保障基于优先级正是d i f f s e r v 的基本策 略。这种方法是指网络边界节点对业务流进行分类、整形、标记。核心节点按照资源管 理策略分配资源，对o o s 要求高的业务给以优先处理。在d i f f s e r v 网络中，边界路由 器将用户流划分为不同的级别，再聚合成流聚集，聚集信息存放在i p 包头的d s 标记 域，称为d s 标记( d i f f e r e n t i a t e ds e r v i c e sc o d ep o i n t ，d s c p ) 。内部节点则根据d s c p 提供不同质量的调度转发服务。 1 3 调度算法的研究与发展 分组调度算法是实现网络q o s 的核心技术之一，其主要功能是通过调度策略来实现 网络资源的分配，从而对预留带宽或延时进行较为严格的保证在i n t s e r v 及类似模型中， 队列调度与接纳控制配合实现严格的o o s 保证。 分组调度算法可能在不同环境下有不同的应用。例如，分组调度算法可能被用于隔 离恶意业务流来为正常业务流提供服务质量保证；分组调度算法还可能用来让用户平等 她共享链路的可用带宽；或者用来实现分级的链路共享等。 根据不同的服务规则，分组调度算法可以分为以下几种：先到先服务、循环调度、处 理机共享、优先级服务、随机服务等根据调度算法的调度目标，也可分为基于时延的 和基于速率的两类。根据调度算法的工作状态，又可以分为连续工作和断续工作 7 1 。其 中连续工作算法表示只要系统中有等待分组，调度算法就一定会工作；而断续工作算法 则意味着即使系统中有等待分组，调度算法也可能暂时不对其进调度。实际上，对于某一 特定的调度算法，根据不同的分类标准，又可属于多个不同的类，所以并没有一种统一的 分类标准。 另外，调度算法的控制在某种程度上是与系统服务模型相关的。例如，可以进行带 宽分配的算法d r r ( d e f i c i tr o u n dr o b i n ) 和可以提供严格的时延范围保证的算法w f q ( w e i g h t e df a i rq u e u e ) 都适用于综合服务模型；而可以提供服务登记的比例关系的算法 w t p ( w a i t i n g t i m ep r i o r i t y ) 适用于区分服务模型。近年来，随着i n t s e r v 网络研究的不断 深入，适合于这一模型的调度算法研究也有了一个新的发展。其特点是不再以单独地 进行单个、具体的算法研究为主要工作，而是以调度算法研究本身的综合、调度算法与 i n t s e r v 其它方面研究的综合以及分析已有算法在特定场合下的应用与改进作为主要研 究方向。同时，d i f f s e i n 模型正成为研究的热点，在将来队列调度算法的研究中，可同 时考虑d i f f s e r v 中已经定义的未来可能出现的区分业务种类，以期研究出更有效的队 列调度算法。 1 4 本文的主要工作 本文的主要目的是设计一种优化性能的o o s 调度算法，并通过n s 2 仿真来检验 第一章绪论 算法的优劣。 首先，本文对q o s 控制模型以及目前比较成熟的分组调度算法进行了探讨，其中 包括先来先服务调度算法、严格的优先级调度算法、循环调度算法、加权公平排队算法 等，为后文的算法设计做了理论铺垫。 然后，主要对基于g p s 模型的w f q 算法进行了一定的研究，通过一个实例分析 了w f q 不区分会话优先级，在链路拥塞情况下，无法保证低速率的实时业务的q o s 延时要求的缺陷，并针对此缺陷提出了一种基于服务分类的加权公平排队算法s c w f q ( w f qb a s e do ns e r v i c ec l a s s ) 。该算法通过对服务分类，将实时业务与非时业务区分开， 对分属于不同类别业务流采用不同的带宽分配方法，以首先满足实时业务对延时的要 求。 最后对算法的实现进行了仿真来验证设计结果。通过l i n u x 下的网络仿真软件 n s - 2 网络模拟器在同样拓扑结构的网络和链路、带宽、信息源等环境下对w f q 和 s c w f q 两种调度算法进行了仿真实验，来检测新算法的实现并对比两种算法性能结 果给出了s c w f q 算法有效控制了实时业务的最大延时，改进了它们的q o s 性能。 文末对下一步可能的研究趋势进行了分析。 1 5 本文的组织结构 本文分为六章，具体结构如下： 。 第一章介绍了研究背景和意义，调度算法的研究内容和发展趋势，并指出了本文的 主要研究内容及论文安排。 第二章介绍和比较了两种不同的i n t e r n e tq o s 控制模型：综合服务模型和区分服务 模型 第三章研究了调度及其相关概念，并对几种分组调度算法( 先来先服务调度算法、 严格的优先级调度算法、循环调度算法、加权公平排队算法) 进行了对比研究 第四章重点研究了g p s 模型及w f q 算法的调度机制，并针对w f q 不区分会 话优先级的缺陷提出了一种基于服务分类的加权公平排队算法s c w f q ( w f ob a s e d o ns e r v i c ec l a s s ) 。然后，对算法性能进行了理论分析并讨论了算法的实现。 第五章是算法的仿真与实现。采用l i n u x 下的网络仿真软件n s 一2 网络模拟器在 同样拓扑结构的网络和链路、带宽、信息源等环境下对w f q 和s c w f q 两种调度算 法进行了仿真实验，来检测新算法的实现并对比两种算法性能。 第六章总结了本文的主要工作并对未来的q o s 控制中的调度工作进行了展望。 最后在附录中介绍了n s 2 下s c w f q 调度算法模拟实验的脚本代码。 本文的重点是第四章和第五章。 4 第二章 n t e r n c tq o s 控制模型 第二章i n t e r n e tq o s 控制模型 i n t e r n e t 的传统服务模型是i p 的尽力而为传输服务。尽力而为服务将数据包从某个 源端点高效地传送到某个目的端点，而不提供端到端的可靠和q o s 保证，例如，时延、 时延抖动、包丢失、包无序到达等等。这种服务显然已经不能满足当今各种网络应用的 需要。因此，为了满足人们对i n t e r n e t 服务质量的需求，i e t f 先后提出了综合服务模 型( 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 4 j 和区分服务模型( 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 ) 【5 1 。 2 1 综合服务模型 2 1 1 概述 i n t s e r v 服务模型【8 】的基本思想是在传送数据之前，根据业务的q o s 需求进行网络 资源预留，从而为该数据流提供端到端的q o s 保证。在r f c l 6 3 3 中，资源预留协议 ( r s v p ，r e s o u r c er e s e r v a t i o np r o t o c 0 1 ) 被定义为i n t s e r v 结构中的主要信令协议。 i n t s e r v 在发送方和接收方之间用r s v p 作为每个流的信令：主机利用雕p 为应用流向 网络提出q o s 的请求( 如带宽及缓冲区大小等) ；路由器利用r s v p 将q o s 请求信息传 给流的路径中的其它路由器，并建立和保存该服务的信息，使得网络资源在数据传输路 径上的各个节点中得到预留，从而对每个业务流( 即具有相同的源和目的地址及端口号、 相同的传输层协议) 实现逐个控制。 2 1 2 功能模块 为了实现对每个流提供端到端的保证，i n t s e r v r s v p 服务模型主要由4 个模块构 成，即信令协议r s v p 、接纳控制器( a d m i s s i o nc o n t r o lr o u t i n e s ) 、分类器( c l a s s i f i e r ) 和分组调度器( p a c k e rs c h e d u l e r ) 组成，传输网络中的每个路由器皆需要实现这4 个部 件，结构如图2 - 1 所示。 主帆路由器 i 应用h 昭v p 处理模块l 曰号v 口 1 册处理梗块k 路由协议 t 傲罨库 l 拶写r制 1 分类器u 黻墨l m 数据鞲 1 分类墨l 。l 调度嚣t - _f_ 图2 1i n t s e r v r s v p 服务模型图 第二章i n t e r n e to o s 控制模型 1 r s v p ：它是主机用来从应用程序获得特定的q o s 的一种控制协议，实现综合服 务需要定义的呼叫接纳控制功能和资源预留功能。通过r s v p ，用户可以给每个业务流 ( 或连接) 申请资源预留，要预留的资源可能包括缓冲区及带宽的大小这种预留需要 在路径上的每一跳都要进行，这样才能提供端到端的q o s 保证。r s v p 的工作机理是发 送方先向接收方发送一个r s v p 信息。r s v p 信息同其他口包一样通过各个路由器到达 目的站点。接收端接收到发送端发送的路径信息之后，逆向发起资源预留的过程，即资 源预留信息沿着原来发送数据包相反的方向对沿途的路由器逐个进行资源预留。 2 接纳控制器：它根据链路和网络节点的资源使用情况以及q o s 请求的具体要求 决定是否接受一个资源预留请求，有利于保证用户的利益和确保网络的性能。 3 分类器：根据预置的一些规则，它对进入路由器的每一个分组进行分类。i n t s e r v 常采用多域( m u l t i f i e l d , m f ) 分类器，当路由器接收到数据分组时，它根据数据分组 头部的多个域( 如五元组：源口地址，目的l p 地址，远端口号，目的端口号，传输协 议) 将数据分组分类放入不同的队列中等待接收服务。相同类的分组将会得到相同的处 理，获得相同的o o s 。 4 分组调度器：它主要是基于一定的调度算法对分类后的分组队列进行调度服务。 常见的调度算法有w f q 、w f 2 0 、s c f q 、w r r 、c b q 等。 2 1 3 业务类型 在r f c l 6 3 3 中，i n t s e r v r s v p 提供了三种级别业务类型，即端到端的质量保证 型服务( g u a r a n t e e ds e r v i c e s ，g s ) 、可控负载型服务( c o n t r o l l e d - l o a ds e r v i c e s , c s ) 和 尽力而为服务( b e s t e f f o r t , b e ) 端到端的质量保证型服纠1 4 1 ：它提供保证的带宽、时延限制和分组丢失率来满足应 用程序的要求。这类服务主要针对实时性要求很高的应用，如v o l p 应用可以预留i o m 带宽和要求不超过1 秒的时延由于需要在通信过程建立之前分配固定资源，质量保证 型服务会对网络中的其它业务产生不良影响，在应用过程中不能无限制地使用，需要在 记费时给于更高的费率。 可控负载型服务【1 5 j ：它保证即使在网络过载( o v e r l o a d ) 的情况下，能对报文提供 近似于网络未过载类似的服务，即在网络拥塞的情况下，保证某些应用程序的报文低时 延和高通过。但是这种服务只能提供定性的服务质量保障，是在现有的i p 网络环境中 利用数据包分类及优先机制等方法为业务提供尽可能好的服务。 尽力而为服务( b e s t e f f o r t ) ：它是指类似于目前i n t e r n e t 网上提供的服务，是一种 尽力而为的工作方式，基本上无任何质量保证，所有业务不加区分地抢占网络资源。 2 1 4 研究所使用的流量模型 在综合服务模型的相关研究中，提出了以流量的界限( t r a f f i ce n v e l o p e ) 来描述 流量而不是去精确地描述流行为的一类流量描述模型。这样描述的好处在于避免了纠缠 6 第二章i n t e r n e tq o s 控制模型 于具体而复杂的网络流量精确模型问题，而能够以所使用的界限模型在一个有效的范 围内讨论流的各种处理性能i 本文在适合于综合服务模型的调度算法研究中主要采用了( 盯，p ) 模型【1 j 7 l ( 漏 桶模型，l e a k yb u c k e tm o d e l ) ，如图2 2 所示。模型的含义是符合本模型描述的流在任意 时段内，所产生的流量不大于口+ p 。因此o r 和p 可以看成是流的最大突发尺度和 产生流量的上界速率。 差冲区 产生敷髓事p 图2 - 2 漏桶模型示意图 i n t s e r v r s v p 服务模型的优点是它能提供端到端的绝对的q o s 保证，但在实现上 是非常困难的，主要体现在以下几方面： 第一，网络的扩展性不好。综合服务模型的基于单个流的操作机制要求网络传输路 径上所有节点( 路由器) 为每个业务流进行资源预留，并不断的刷新和保持状态信息， 这使得路由器的负担会随着网络的扩大、业务流的增加而加重。不利于网络扩展。 第二，综合服务模型需要进行端到端的资源预留，必须要求整个网络从主机到路由 器都要对r s v p 支持，而现行口网络并不能完全支持r s v p 。 第三，i n t s e 州r s v p 还存在着资源预留和路由协议之间的矛盾。如图2 3 所示，a 要向c 发送数据包，从路由角度来看a e f g c 是一条好的路径，但从资源预留来看，由 于路由器e 没有足够的资源可以预留，不能为数据流建立起一条路径，因此这一进程只 能停留在这里，等待上层超时拆除这个应用进程，再重新建立路径此外，资源预留本 身就与i p 网络的最大特点“无连接”相冲突。 b c d -礁据包信输的路由路径 一罄r r 资溺嘎管毫湖噼径 图2 - 3r s v p 与路由之间的矛盾 7 ， 第二章i n t e r a c tq o s 控制模型 2 2 区分服务 综合服务模型所暴露出的种种不足，表明了综合服务模型不能很好地提供端到端的 q o s 保证。为此，i e t f 组织在1 9 9 8 年提出了一个新的、扩展性强的服务模型，即区分服 务模型( d i f f e r e n t i a t e ds e r v i c e ，d s ) 9 1 。1 1 3 i 。 2 2 1 概述 d i f f s e r v 模型实际上是尽力而为的先来先服务( f c f s ) 与综合服务资源预留 ( i n t e s e r v 瓜s v p ) 所提供的针对每个业务流的复杂机制之间的一种折衷方案，采用的 是分组标记和按类排队的方法。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 s c p ( d i f i s e r vc o d e p o i n d1 9 1 与p h b ( p e r - h o pb e h a v i o r ) 1 1 1 1 1 2 1 的对应机制，在数据 流进入核心路由器时只根据分组头部d s ( d i f f e r e n t i a t e ds e r v i c e s ) 域中的d s c p 进行转 发，而业务流状态信息的保存与流监控机制的实现等都在网络边界节点进行，内部节点 是状态无关的。 聚合网络内部核心路由器的服务对象，采用流聚集的方式进行传输控制，具有相同 d s c p 的数据流组成一个宏流( m a c r o - f l o w ) ，核心路由器的服务对象是宏流，而不是 单流( m i c r o f l o w ) ，单流信息只在网络边界节点保存和处理。 区分服务模型的关键技术在将业务流进行聚合与分类这种聚合与分类都由d s 标记来表征。d s 标记的结构图如图2 4 所示。d s 标记不额外添加字节，而是定义为i p v 4 头中的服务类型( t o s ，t y p eo f s e r v i c e ) 字节或i p v 6 头中的业务类( t r a f f i cc l a s s ) 字节。 056t 图2 - 4d s 标记结构图 其中，d s c p 占六个b i i ，是d s 标记域中的具体值，用来标识数据包所属的流聚 集，供数据包经过d s 节点时选择特定的p h b ，不同的p h b 决定了分组的转发性能。c u ( c u r r e n t l yu n u s e d ) 占两个b i t ，暂时没有定义实际上，按照d s 域的标记，以相应方 式提供不同质量的分组转发服务，也正是区分服务名字的由来。 8 第二章i n t e r n e tq o s 控制模型 2 2 2 功能模块 与综合服务模型中路径上的所有路由器完成的功能都基本类似不同，区分服务模型 区别对待边界路由器与核心路由器。当数据流进入d s 域，根据分组所属应用的服务质 量要求，分组在边界网络设备中被分类标记，从而可以将各个分组归入各种具有相同码 值的行为聚集b a ( b e h a v i o ra g g r e g a t e ) 。每种行为聚集通过一个单一的d s c p 值来标 识。 因而边界节点从功能上可以分为两个模块，即分类器( c l a s s i f i e r ) 和调节器 ( c o n d i t i o n e r ) 1 1 0 1 ，分类器和调节器之间的逻辑结构如图2 5 所示。 i 。 1 分勰f 图2 - 5 区分服务中分类器和调节器逻辑结构图 分类器遵照特定规则，根据包头的某些域( 如d s c p 值或m f 五元组) 将包划归到 某一类别，然后交由相应的调节模块进一步处理。目前主要有两种类型的分类器： ( 1 ) b a 分类器：最简单的区分服务分类器，仅仅用分组i p 头中的d s c p 决定业 务流应选择的逻辑输出流。 ( 2 ) g f ( 多域) 分类器：除了d s c p 外，还使用其它的分组头字段的值选择分组。 一个常见的m f 分类器是五字段分类器，使用诸如源地址、目的地址、协议i d 、发送 端口和目的端口号。 调节器在逻辑上又分为计量器( m e t e r ) 、标记器( m a r k e r ) 、整形器( s h a p e r ) 和丢 包器( d r o p p e r ) 计量器测量业务流的当前属性并将结果传递给调节器的其他部分，从而 影响其他部分的行为。标记器根据计量器传递的状态信息标记分类器传递的分组的 d s c p 并将标记好的分组添加到一个特定的d s 行为聚集中。标记器可以重新标记 ( r e m a r k ) 分组的d s c p 值。整形器和丢包器通过缓存或者丢弃业务流的部分或全部 分组，使业务流符合流量调节约定( t r a f f i cc o n d i t i o n i n g a g r e e m e n t ，t c a ) 的流量规格。 边缘路由器对上述处理之后的业务流进行d s c p 的检查，并依据i p 流中的d s c p 值对分组进行转发。而核心路由器根据分组d s c p 值采用相应的p h b ( p e r - h o pb e h a v i o r ) 【1 1 j 【1 2 】来转发分组，不同的p h b 使得分组在通过网络设备时得到不同的处理。 2 2 3 业务类型 与i n t s e r v 类似，d i f f s e r v 也定义了三种业务服务类型，即尽力而为的服务( b e s t e f f o r t s e r v i c e ，b e ) 、奖赏服务( p r e m i u ms e r v i c e s ，is ) 和确保服务( a s s u r e ds e r v i c e s ，a s ) 。 尽力而为的服务：它是指类似于目前i n t e r n e t 网上提供的服务。 9 第二章i n t e r n e tq o s 控制模型 奖赏服务1 1 3 】为用户提供低延迟、低抖动、低丢失率、保证带宽的端到端或网络边界 到边界的传输服务，是目前所定义的服务级别最高的区分服务种类。这种“三低一保证” 的服务承诺用户可以享受类似专线业务的服务质量，因此奖赏服务也被称为“虚拟专线” 服务。奖赏服务并非要取代传统的尽力而为的服务，而是与之共存以提高网络资源的利 用率。实际上，奖赏服务流只会占据很小一部分资源。 在奖赏服务中要确保以下两点： ( 1 ) 在传送节点处保证p s 流最小出速率不依赖于节点状态的动态变化，不依赖于 此节点处其它流的强度。 ( 2 ) 调节p s 流( 通过整形或丢弃) ，以保证它在任何节点处的入速率都小于此处的 最小出速率。