（计算机系统结构专业论文）基于分层服务曲线算法的ip服务质量研究.pdf

华中科技大学博士学位论叉 摘要+ 厂 随着因特网舰模的日益扩大，各种各样的网络应用层出不穷。因特网已由单 一的数据传输网逐步向数据、语音和图像等多媒体信息的综合传输网演化。但因 特网中现有的传输模式仍为单一的尽力传输( b e s te 仃o n ) 服务，无法很好地满足多 媒体应用和各种用户对网络传输质量的不同要求。因此，提供服务质量( q u a l i t yo f s e r v i c e ，q o s ) 成为因特网发展的重要挑战，网络q o s 技术作为公认的新一代网络 的核心技术之一，是当前网络研究和开发的热点。解决这些问题的最简单的办法 是增大带宽，但是，由于这种方法代价高昂，并不十分可行。这就要求网络管理 者对不同的服务区别管理，不能对所有的数据数据包一视同仁：于是，各种q o s 技术应运而生厂矿一 为了同时支持多媒体实时传输以及w 曲浏览等多种应用程序，必须设计一种 数据包调度算法，使其同时支持分层连接共享服务、实时服务和优先级服务。数 据包调度通过对数据包进行排队，对某些特定的数据包赋予较高的优先级，就可 以满足各种业务的q o s 需求。通过分析分层连接共享服务的特点，提出了一种新 的服务质量模型服务曲线连接共享模型，f 此模型能够同时支持连接共享、实 时和优先级服务。通过对此模型的分析，可以知道这三种服务的目标之间有时会 发生冲突，在发生冲突时必须进行相应的折衷选择。在服务曲线连接共享模型的 基础之上j 提出了分层服务曲线调度算法，眦算法优先保证实时准则，从而确保 了实时和优先级服务，同时分层服务曲线算法也尽可能地逼近服务曲线连接共享 模型，使得实际提供的服务与服务曲线连接共享模型提供的服务之间差别最小。 并 从理论上分析并证明了分层服务曲线调度算法的实时保证和公平性。最后用实 验验证了分层服务曲线算法的有效性。 仙于实现i n t s e r v 和r s v p 需要增加复杂的信令系统，收集和处理每个业务流 的信息，因此在很大程度上增加了网络的负载，只能适用于小型网络通过区分 服务体系与o o s 和c o s 的深入对比，研究了区分服务体系的由来、性能、特点、 现状和问题。f 对d i f 瑁e r v 和i n t s e r v 的关键问题，包括服务模型、质量性能机制和 各自的特性，都做了详尽的论述，并提出了基于分层服务曲线算法实现d i f r s e r v 的服务模型，以及d i f r s e n r 面临的问题和今后研究的方向。，1 。 本文的研究i ：作获得国家高技术研究与发展计划“可扩展集成多媒体系统的建模与实现” ( 8 6 3 3 1 7 - 0 l - 1 0 9 9 ) 和国防预研项目“评估多媒体存取与交换方法的研究”( 1 5 _ 8 4 ) 资助。 l，：l 据包调度算法的实现。 关键词：服务质量多媒体网络 i p v 6包调度资源预约咖议 i i 华中科技大学博士学位论文 a b s t r a c t + w i t ht h ei n c r e a s eo ft h ei n t e r n e ta n dt h ei n t r a n e t ，n l a n yn e w a p p l i c a t i o n sa p p e a r s m a nc a p a c i t yt e l n e ts e s s i o n sb e c o m eb l g g e rc l i e n t s e e rs e s s i o n s a n dn o wt h e r c c o m e sm o r ea n dm o r e g r a p h i c i n t e n s i v e w b r i dw i d ew e bt r a m c s i nt h e s e d a y s r e a l e i n l ea u d i oa n dv i d e oa p p i i c a t i o n sb r i n gm o r eb u r d e n st ot h en e t w o r k t bf h 熵1 1 t h e s er e q u i r e m e n t s ，i ti si n s u 岱c i e n tt oi n c r e a s et h en e t w o r k c a p a c i t y w e n e e dt c c h n i q u e st om a l l a g e r a 街ca j l dc o n t r o lc o n g e s t i o ns e n s 谢v e l ya n de 虢c t i v e l yi n t 1 1 i sp a p e r ，w ew i j lf e s e a r c ho nt l l e s e f i r s t ，w er e s e a r c hl h es e n ，i c ec u n r e 】i 1 1 l ( 一s h a r j n gm o d e ji nt h i sp 印e r w ep r o p o s ea s e r v i c ec u r v e 1 j n k s h a f i n gm o d e la st h eb a s i so f t h ep a c k e t s c h e d u l i n ga l g o r i t h i n f i r s t ， u n l i k e p r e v i o u sm o d e l s ， t h j sm o d e l e x p l i c j t l y d e 矗n e st h es j t u a t i o n s r h e na l l p e r f b m a n c eg o a l sc a n n o tb es j m u l t 卸e o u s l ys a t i 娟e d 。1 h se x p o s e st h ef u n d a m e n t a l a r c h i t e c t u r e 仃a d e o f rd e c i s i o n s0 n eh a st om a k e 埘t 1 1r e 印e c tt ot h ef e l a t i v ei m p o r t a n c e 锄o n gt h ec o n n i c t i n gp e r f o m l a n c eg o a l s s e c o n d ，t 1 】em o d e ls e n ，e sa sa ni d e a lt a 唱e t t h a ta s c h e d u l i n ga l g o r i m m s h o u l d a p p r o x i n l a t ea sc l o s e l ya sp o s s j b l e b a s e do nt h es e r v i c ec u r v el i n k - s h a r i n gm o d e l ，w e p r o p o s eac o r r e s p o n d j n gp a c k e t s c h e d u l i n ga l g o r i t i l i l l t h ee x p e r i m e m ss h o wt h a t t h i s a l g o r i m m c a j l s u p p o nb o t h l i n k s h a r i n ga n dr e a l t i m es e r v i c e a n dw ea l s oa n a l y z et 1 1 e r e a l 一t i m eg u a r a l l t e ea j l d f a i m e s so f t h i sh i e r a r c h i c a ls e n r i c ec u r 、，ea l g o r i t l l mi nm e o r y d i 腩r e n t i a t e ds e r v i c e s ( d i 凰e r v ) i sa r c h i t e c t u r ef o rp m v i d i n gd i 腩r e n tt y p e so r l e v e l so fs e r v i c ef o rn e t w o r kt 豫m c 0 n ek e vc h a r a c t e r i s t i co fd i f r s e r vi st h a tf l o w sa r e a g g r e g a t e di nt h en e t w o r k ，s om a tc o r er o u t e r so n l yn e e dt od i s t i n g u i s hac o m p a r a b l y s m a l ln u m b e ro f a g g r e g a t e dn o w s ，e v e ni ft h o s en o w sc o n t a i nt h o u s a n d s o rm i l i i o n so f i n d i v i d u a ln o w s i p v 4i sa ne x c e l l e n t d e s i g n i f t h e r ew e r e g r e a td e f e c t s ，m ei n t e m e t 、v o u l dn o tg r o w i n t ot o d a y ss i z e ，i p v 6i n h e r i t st h em e r i t so f i p v 4 ，a n de x t e n d s i t sf u n c t i o n sa c c o r d i n gt o t h cm a f l yy e a r s e x p e r i e n c e so fu s i n gi p v 4 w eg i v et h eb a s i cp r o g r a m m i n gr u l eo f s u p p o n i n gm u l t i p l ea d d r c s sf 抽i l i e s a n d 、v ep r o p o s ea na p p l i c a t i o n l e v e lg a t e w a y t h i sr e s e a r c hw o r ki ss u p p o r t e db yn a t i o n a lh j g ht e c hr & d p m g r a m ( g r a n tn o 8 6 3 - 3 1 7 l o l - 1 0 - 9 9 ) a n d t h e n a t i o n a ld e f 色n s e t e c h n o l o g yr e s e a r c hp f o j e c t ( g r a n t n o 1 5 8 4 ) ， l i i 、v h e nt h ei p v 6a n di p v 4c o e x i s t a tl a s tw em a k eo u rp a c k e ts c h e d u l i n ga l g o r i t h m s u p p o r tb o t h t h ei p v 6a n di p v 4 k e y w o r d s ：q u a i i t y o fs e r v i c en e t w o r k e d m u l t i m e d i ai p v 6 p a c k e ts c h e d u l i n gr 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 v 华中科技大学博士学位论文 l 绪论 1 1 服务质量及定义 q o s ( q u a l j y o fs e r v i c e ，服务质量) 是指发送和接收信息的用户之间、以及用 户与传输信息的集成服务( i n t e g r a t e ds e i c e s ，i n t s e r v ) 网络之间关于信息传输的质 量约定】。服务质量包括用户要求( u s e rr e q u i r e m e n t ) 和网络集成服务提供者的行为 ( a c t i v i t y ) 两个方面。用户要求指用户在i n t e m e t 网络上进行多媒体通信时所要求的服 务类型以及相应的传输性能和质量等。集成服务提供者的行为则指因特网针对某 一类服务所能提供和达到的性能与质量。 q o s 与用户以及网络系统的关系如图l 一1 所示。由图1 一l 可以看出，q o s 刁i 是 网络中某个个体或元素的行为描述，它涉及到用户与用户、用户与网络以及网络 内部节点( 或元素) 的整体行为。例如，图1 1 中用户1 与用户2 之间要相互通信时， 事先必须相互协商通信时的服务类型以及相应的性能参数。否则，如果用户2 接 收来自于用户1 的实时图像信息，用户l 每秒按3 0 帧发送，用户2 只有每秒2 0 帧接收能力的话，尽管i n t e m e t 提供了3 0 帧的传输服务，信息仍会出于用户2 的 接收能力不够而丢失，从而也就无法进行满意的实时通信。 撇瞎= = = 夕 图1 1q o s 与用户以及网络系统的关系 除了用户和用户之间的协商之外，用户和网络、网络中的各个元素之间也存 在着q o s 协商和管理问题。当用户的q o s 要求太高，网络无法提供相应的集成服 务时，将要求用户降低其q o s 要求，甚至为了保护其他用户的服务质量而拒绝用 华中科技大学博士学位论文 户的q o s 要求。用户和网络系统之间的q o s 协商称为准入控制( a d m i s s i o n c o m r o i p 3 ，4 1 。 在网络内部的路由器、交换机的端口，以及端主机系统r l j ，为了保证用户要 求的服务质量，必须调度相应的资源，甚至进行资源预约，这就需要相应的资源 预约协议和资源调度算法。所以，q o s 控制过程的引入是剥i n l e m e t 协议以及传输 机制的重大改变0 1 。 对q o s 的研究始于8 0 年代初期。但是，由于当时网络性能低，提供的服务 少，且人们对分布式多媒体应用无太多的要求，因而当时主要停留在网络性能评 价、吞吐量的计算以及传输延迟等方面，l “。随着宽带i s d n 技术以及a t m 交换 网的出现和分布式多媒体应用的急剧增加，人们才开始对q o s 管理和控制进行深 入研究3 ，1 8 】。由于因特网上传输多媒体信息的要求，以及在传输数据时经常出现 拥塞现象，因特网的q o s 研究也随之开始深入，并于1 9 9 7 年9 月制定了有关o o s 定义与服务的系列r f c ( r e q u e s t f o rc o n u n e n t s ，征求评议) 标准陋。 1 1 1 0 s i 参考模型中的q o s 定义 i s o ( i n t e m a t i o n a ls t a i l d a r d s0 r g a n i z a t i o n ，国际标准化组织) 最早开始q o s 问题 的研究。针对o s l ( o p e ns y s t e m si n t e r c o n n e c t i o n ，开放系统互连) 参考模型的7 层 协议，i s 0 组织要求每层协议都在向高层提供相应服务的同时，提供如表卜1 所示 的服务质量。 表1 1 o s i 参考模型中的q o s 定义 参数含义 吞吐率单位时间内在一个连接上传递的最大字节数 传输延迟从数据传输请求开始到数据传输完成确认为止的时问间隔 出错率数据单元错传、丢失或重传的概率 建立连接延迟从请求建立连接开始到建立连接确认为止的时间间隔 连接失败率建立连接失败的概率 传输失败率传输失败的概率 释放延迟从释放请求开始到释放确认为止的时间延迟 释放失败率释放连接时失败的概率 如表l 一1 所示，o s i 参考模型t 1 ，的服务质量q o s 用参数方式进行定义，即商 一一一一一一一 2 华中科技大学博士学位论文 层协议要求低层咖议在提供相应的服务质量时，高层踟议向低层l 办议发送包信q o s 参数值的服务数据单元( s e r v i c ed a t au n i t ，s d u ) ，低层协议按高层咖议对q o s 要求 进行有关操作，如图l 一2 所示。 按o o s 要求的服务 in 层协议 tj r l( ”，) 层协议 o o s 婴求s d u ( 吞l 牢、传输延迟等) 图1 2o s i 参考模型的参数传递 另外，i s o 还定义了与协议功能无关的安全性，成本与传输优先级等q o s 参 数，如表1 2 。 表1 2o s i 中与协议功能无关的q o s 参数 参数含义 访问权限防止非法用户访问 优先级包括传输优先级和使用优先级 成本信息传输时所消耗的资源或资金 1 1 2 c c i t t ( 1 t u ) 的q o s 定义 0 s i 参考模型中的q o s 参数定义主要是针对数据传输的。这些定义既未考虑 服务类型，也未考虑传输出错的概率分布及传输峰值的变化等因素，而且o s i 参 考模型的o o s 定义未给出如何实现q o s 要求的方法与框架【l ”。1 9 9 0 年，当时的 c c i t t ( c o m i t 6c o n s u l t “fi n t e m a t i o n a lt 色l 印h o n i q u ee tt 6 l e g r a p h i q u e ，国际电报电 话咨询委员会) 又针对q o s 制定了c c i t t _ i 系列建议。 该建议从呼叫控制、连接以及数据单元的传输控制等3 个不同层次上定义了 宽带i s d n 的q o s 。呼叫控制级的q o s 包括呼叫次数、失败率等；连接级的q o s 包括连接延迟、连接失败率、释放的延迟和释放失败率等参数的定义；数据单元 传输控制级的o o s 定义包括数据包的峰值到达率、峰值持续时间、数据包平均到 达率、数据包丢失率、数据包插入率以及比特出错率等。 不过，这些q o s 定义仍然未提供实现q o s 控制和用户q o s 要求的机制，也 未对用户要求的服务进行分类。这些q o s 定义不是站在用户的立场，而是站在服 一 3 华中科技大学博士学位论文 务提供者，即网络的立场上定义的。 1 1 3a t m 的q o s 定义 a t m 论坛不仅把服务质量q o s 的概念引入了a t m 交换机中，而且列f j 户的 应用和a t m 所对应的服务分成了5 类，即恒定比特率服务( c b r ，c o n s t a n t b i t r a t c ) 、 实时可变比特率服务r t v b r ( r e a l t i m e 、r 甜i a b l eb i tr a t e ) 、非实时可变比特率服务 ( i l n v b r ，n o nr e a l t i m e 、协i a b l eb i tr 丑t e ) 、自适应比特率服务( a b r ，a l t e m a t eb i t r a t e ) 和未指定比特率服务( u b r ，u n s p e c i f i e d b i tr a t c ) 【1 9 2 叭。 a t m 论坛也定义了相应的呼叫准入控制( c a c ，c a l la d m i s s i o nc o n t r 0 1 ) 检查用 户连接请求的服务类型，并根据a t m 交换机中的资源空闲情况决定接受或拒绝用 户的连接请求。 由于a t m 用面向连接方式交换信元，一旦一个虚电路被建立起来之后，在数 据传输完成之前不会被切断。因此，a t m 用户u n i ( u s e rn e t w o r ki n t e r r k e l 方面的 q o s 要求主要以服务类型为主，a t m 交换机则把u n i 提交过来的服务类型自动匹 配到相应的q o s 参数上去。当然，这些参数包括优先级、交换速率、延迟时问等。 a t m 交换机把不同的服务类型的信元放入不同优先级的队列，并为它们分配不同 数量的缓冲区。 1 1 4l e t f 的q o s 定义 如何在因特网上提供集成服务的关键是q o s 控制。为此，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 kf o r c e ，因特网工程任务组) 把q o s 控制问题划分为两大部分，即集 成服务模型与o o s 实现框架【四2 5 】。自r f c l 6 3 3 提出了i m e m e t 集成服务的概念之 后f 3 5 j ，r f c 2 2 1 l 定义了i n t e m e t 的控制负载型服务( c o n 咖l l e d l o a dn e t w o r k e l e l e n t s e r v i c e ) 【2 9 l ，r f c 2 2 1 2 定义了保证型服务( g u a m n t e e dq u a l i t yo f s e r v i c e ) 【2 8 】，r f c 2 2 1 5 则定义了i n t e m e t 的集成服务1 2 7 】，即q o s 控制用的通用特征参数( g e n e r a l c h a r a c t e r i z a t i o np a r 锄e t e r s ) ，r f c 2 216 定义了q o s 服务规范1 2 6 j ，而r f c 2 2 0 5 则给 出了实现q o s 控制的最关键部分【3 3 】一资源预约协议r s v p ( r e s o u r c er e s e r v a t i o n p r o t o c o n 。 下面是i 强c 2 2 1 6 中关于q o s 的定义，q o s 是用带宽、数据包延迟和数据包丢 失率等参数描述的关于数据包传输的质量。传统的i n t e m e t 只提供单一的服务质量， 华中科技大学博士学位论文 即尽力而为服务，在该服务中，可利用的带宽以及相应的延迟特性取决于网络中 的负载状况。 为了进一步描述q o s 控制过程和服务模型与实现框架，r f c 2 2 1 6 还定义了网 络元素( n e t w o r ke i e m e n t ) 、流( f l o w ) 、服务( s e r v i c e ) 、行为( b e h a v i o r ) 、特性化 ( c h a r a c t e r i z a t i o n ) 、相应的流量规范( t r a m cs p e c m c a t i o n ，简称t s p e c ) 、服务要求规 范( s e n ，i c er e q u e s ts p e c i f i c a t i o n ，简称r s p e c ) 以及与q o s 控制有关的其它术语。 i e t f 规定，网络元素指任何一个可在i n t e m e t 中处理数据数据包的构件，它 具有在数据通过时进行o o s 控制的能力。网络元素包括路由器、子网、端主机系 统的操作系统等。流则指具有相同q o s 要求和服从同一q o s 控制方法的通过某个 网络元素的数据包集合，在一个给定的网络元素中，一个流的数据包可以来自于 某个单一的应用，也可以来自于不同的应用。 服务与q o s 控制服务具有相同的意义，它描述网络元素的q o s 控制能力。服 务包括规范和功能两大部分。 行为是指与q o s 相关的端到端性能，它是应用直接可见的山服务提供的最终 结果。 t s p e c 是要求服务提供的流量描述，它实际上是一份数据流和网络元素提供 的服务之问的合同；r s p e c 则是用户对网络元素的q o s 要求。t s p e c 和r s p e c 都 被资源预约协议r s v p 规定有相应的格式和定义f 2 。 i e t f 把o o s 定义为一个两维空间： 、 。服务类型与参 数类型两者都用整数表示。 的取值范围为( o ，2 5 5 ) 。该取值范围被进一 步划分为3 个区，即：l 、( 1 ，1 2 8 ) 、( 1 2 9 ，2 5 5 ) 。服务类型1 被保留下来指定通用参 数，即当服务参数类型为j 时，参数类型中给出的任何参数都可被所有服务所使 用；服务类型( 1 ，1 2 8 ) 表示i e t f 定义的各种服务。i e t f 的i n t s e 工作小组负责定 义各种服务的编号，例如，保证型服务的标号为2 ，控制负载型服务的编号为5 。当 前，i e t f 还未定义更多的服务类型，如果研究人员开发和定义了新的服务类型， 并准备提交给公众服务的话，应从i e t f 的i n t s e r v 工作小组获得相应的服务编号； 服务类型( 1 2 9 ，2 5 5 ) 是专为服务与实验开发保留的，研究人员在实验阶段可任意从该 区间选取服务号在本地使用。服务号中未使用编号o ，这是因为这些编号将被用作 直接访问m i b ( m a j l a g e m e n t i n f o 衄a t i o nb a s e ，管理信息库) 对象库的指针。 与 相同， 的取值范围也是( 0 ，2 5 5 ) 。区膪j ( 0 ，1 3 ) 是保留区 间，专门用于指定那些供所有服务公用和共享的参数，例如，当前可利用的带宽 可供各种服务共享的q o s 参数；区间( 1 2 9 ，2 5 5 ) 由服务规范的设计人员给定，它们 不是共享的，只针对相应的服务类型。 1 2q o s 研究的主要技术课题 上面分别介绍了几种q o s 定义。有关分前j 式多媒体应用中的q o s 控制还需要 进一步研究。这些研究大致集中在以下几个方面：q o s 定义与标准、q o s 协商与 准入控制方法、数据包分类与调度、资源分配与预约方法以及基于q o s 的操作系 统和q o s 的实现方法等。 1 _ 2 1q o s 定义与标准 尽管i e t f 在1 9 9 7 年9 月定义了一系列有关q o s 与集成服务的定义和标准， 但仍存在下述几个方面的问题：这些定义都是针对网络传输延迟的，未考虑抖动、 同步、声音图像的失真率等因素；尽管定义了f l o w s p e c 等数据流的q o s 参数， 但用户如何表示自己的o o s 需求，仍是一个十分困难的问题。特别是很难量化用 户对画面和音质等感觉上的质量要求；由于q o s 涉及到协议上的每个层次，因此， q o s 控制和服务提供也应该是分层次的。然而，i e t f 的定义并未对集成服务以及 q o s 控制的层次进行适当的定义和划分。 针对上述问题，国际上许多研究小组( 包括l e t f 的工作小组) 正在进行相应的 研究。例如，英国l a l l c a s t e r 大学的研究小组在q o s - a ( q u a i i t y o f s e r v i c e a r c h i t e c t u r e ， 服务质量体系结构) 工程中提出了一个按系统处理方式对q o s 进行分层【8 8 ，8 9 ，0 1 ，按 用户需求和应用进行分维，并将不同维中具有某些共同属性的q o s 组成类的新方 法。 1 2 2q o s 协商和准入控制 o o s 协商指用户和系统以及用户和用户之间就所传输信息的服务质量进行交 互，最后根据应用和系统资源确定系统和用户的q o s 的过程。 用户和系统之间的协商过程如下。 首先，协商程序分析用户的行为，将其分解为一些元素，使得每一个元素都 可由一个或多个独立的q o s 参数表示。用户行为分解的基本准则是这些参数的组 一一一一一6 华中科技大学博士学位论父 合应该保护用户行为的q o s 。在对用户行为分析结束之后，系统把所得到的参数 组映射到相邻的低层，并确定以相邻的低层是否能够支持这些q o s 要求。在此基 础上，系统将为用户的行为元素定出各自的q o s 级别，或者向用户报告拒绝服务 的情况和原因。 q o s 协商一般都伴有q o s 重协商功能，q o s 重协商是指对网络传输中的已确 定的数据流的o o s 级别和服务类型进行再调整的响应过程。这种情况一般发生在 有新的多媒体用户的高优先级抢占网络资源或已有的网络资源发生敞障，使得现 有的网络资源无法使用时。 准入控制可以看作q o s 协商的一部分，即q o s 协商时，网络资源是否达到让 用户进入网络系统传输、使用网络资源的过程。当前，i n t e m e t 上有关q o s 协商的 研究大多集中在准入控制方面。 与服务质量控制有关的网络资源较多，例如带宽、缓冲、c p u 、线程等。r s v p 协议主要是针对与数据流特征有关的带宽和缓冲区的分配口“，c p u 、线程等资源 的分配调度等则要依赖于别的方法。r s v p 虽然规定了将n o w s p e c 等参数传送给各 网络元素、设置和维护相应的软状态表，进而预约带宽和缓冲等资源的方法，但 并未规定如何实现和如何完成数据包的转发调度。这就需要列每个网络元素中等 待处理的数据包进行排队，根据相应的q o s 要求和级别赋予相应的优先级并调度 执行，而且，在等待队列超过一定的长度时，还需要按照一定的策略丢弃一部分 等待数据包以减缓发送端的数据流【3 7 j 9 ”j 。 当前几种比较常用的数据包排队和调度算法有先进先出排队法、优先级排队 法、基于等级的排队法以及加权公平排队法等。另外，还有避免拥塞再发生的随 机早期检测法( r a f l d o me a r l yd e t e c “o n ，r e d ) 等川。 先进先出排队法的基本原理是按数据包到达的先后顺序转发数据包，对于超 过网络元素缓冲区长度的数据包，则丢弃最后到达的数据包。这是i n t e r n e t 网上通 用的转发方法，但由于这种方法不区分服务类型，从而无法支持用户的q o s 要求。 优先级排队法是一种最简单的支持q o s 控制的调度方法，它按照i p 数据包自 身的优先级转发到达数据包。优先级排队法的重点主要是确定被转发数据包的优 先级，而被转发数据包的优先级又由用户应用确定。因此，如果优先级在事先安 排时欠妥的话，将会造成在某个优先级上发生拥塞的现象。另外，在使川同一个 优先级的数据包队列中，仍然按照先进先出的方式进行数据包调度，这样也会产 生无法满足用户o o s 要求的现象。 并为这些队列赋予不同的等级，在同一等级的队列内按先进先出的原则调度转发 数据数据包。其最大缺点是在同一等级内仍是采用先进先出的转发方法，从而无 法预测同一等级的数据包的延迟时问。 加权公平排队法仿照时分复用( t i m e d i v i s i o nm u l t i p l e x i n g ，t d m ) 方式按时隙 调度和转发不同队列的数据包。由于这种方法可以预测调度转发各数掘包的时问， 从而可根据应用的q o s 要求调整数据包的调度顺序。缺点是需要对应用类型进行 整理，以及计算等待调度的时间，这将花费较多的c p u 时间。 1 2 3 基于q o s 的操作系统 传统的操作系统如u n i x 、w i n d o w s9 5 9 8 n t 等都是面向数据处理的，在c p u 调度、内存和缓冲以及文件系统等的管理中都是以二进制数据为基础，很少考虑 多媒体数据的实时性和表现的连续性等因素。要操作系统能支持和实现q o s 控制， 就必须对操作系统的调度策略、内存访问和管理方法以及文件管理系统等进行新 的设计与研究。近年来，有不少研究单位开始了以分稚式多媒体应用和q o s 控制 为目标的新操作系统设计与研究【76 1 。另外，基于市场经济模型的网络资源分配与 q o s 要求的平衡方法等也是q o s 控制研究的重点之一1 5 ”。 1 3 资源分配和数据包调度 数据包交换计算机网络自它们出现以来获得了引人注目的发展。从仅仅连接 几台计算机的小型网络，i n t e m e t 发展成连接几千万台计算主机的最大的计算机网 络。传统上，这些网络提供尽力传输服务( b e s t e 仃o r ts e n ，i c e ) ，在尽力传输服务中， 网络并不保证一个数据数据包何时与是否被传递。虽然这些网络提供的尽力传输 服务对t e l n e t 和f t p 等应用已经足够，但一些新应用的出现刺激了计算机网络提 供的服务必须有根本的改变。 多媒体应用：在过去几年里，通讯与计算机技术的发展使得网络带宽和计算 机处理能力成倍的增加，与此同时视频压缩技术也有了很大的发展。这些发展配 合起来使得对数字视频而言带宽和存储空问的需求得到满足，因此产生了如视频 会议( v i d e oc o n f e r e n c i n g ) 、远程学习( d i s t a n c e1 e a m i n g ) 、虚拟现实等大量的多媒体应 用( 1 1 5 1 。 垫工堕塞堕些垒塑签廛旦麴让篡扭圃终逝埕供鳆腿釜，_ 羞虑二企典型的多始。 华中科技大学博士学位论叉 体应用视频会议。在视频会议中，来自参加者( 源) 的音频和视频信号全部是数字化 的，在可能压缩的情况下，打包并从网络传送到另一参加者( 接收者) ，在收到包后， 接收者解压缩包( 如果需要) 并回放它们，以使得重组的音频视频信号尽可能的与原 来的信号接近。为了使接收者达到这个目标，网络必须保证以下条件满足： 最小带宽：因为音频和视频信号有着本身的数据产生率，为了使接收者高 保真度重组信号，网络必须保证接近与数据产生率的最小带宽。 数据包的延迟范围：由于数据包的非零延迟，重组信号是原信号的时移版 本。令信号的时移为d ，在时刻什d 重组信号，数据包在时刻t 时的信号 应在不迟于t 十d 时到达接收者，即数据包的延迟最大为d 。否则，在时刻 什d 时一些信号不能被重组，因此导致重组信号的逼真度降低。为了避免 逼真度的降低，网络必须保证数据包延迟的上限。进而，山于最大时移取 决于交互性需要，应用程序应该能够指定数据包延迟的范田。 当前的网络既不能保证最小带宽，也不能保证数据包延迟的范围，因此对多 媒体应用来说是不适当的。 实时应用：计算机网络被越来越多地使用在实时应用上，如工厂的生产控制 和股票交易等，这些应用要求网络保证数据包的延迟，由于普通的计算机网络并 不提供延迟保证，它们使用专门的网络。为了使网络的应用面更广，普通的计算 机网络也需向能提供实时服务方面发展。 计算机网络在支持传统的数据应用的基础上支持多媒体和实时应用的需要， 导致了集成服务网络的出现。集成服务网络将支持满足不同q o s 需要的一系列应用 程序，它将提供以下q o s 保证：最小带宽、数据包延迟的上限、实时应用和连续媒 体( c o m i n u o u sm e d i a ) 应用( 如音频和视频会议) 的数据包丢失率，它同时也支持当前 网络的尽力传输服务。设计提供如此灵活q o s 服务的网络非常具有挑战性，它的实 现需要网络结构的各层的革新。由于o s i 的网络层定义了网络对应用程序输出的服 务，最重要的和持久的改变需要在网络层发生。 网络层的一个基本问题是满足数据包源的q o s 需求。为了控制数据包的延迟 和数据包丢失率，从而避免捌塞，网络必须管理两种资源：连接带宽和每个数据 包交换机的缓冲区。在包交换网络中，资源并非在不同源问物理上分开，因此刈 连接和缓冲区的竞争叫能发生。因此网络必须仲裁对资源的存取和限制对资源的 竞争。特别地： 仲裁存取的算法：连接带宽和缓冲区的仲裁存取算法分别称为数据包调度 一一 q 华中科技大学博士学位论父 ( p a c k e ts c h e d u l i n g ) 和缓冲区调度( b u 腩rs c h e d u l i n g ) 算法a 数谢包侧厦算怯祆疋 了在一连接点数据包传输的次序因而控制了源点的带宽、数据包延迟和数据包 丢失率。缓冲区调度算法决定了缓冲区溢出时丢弃哪些数据包因此控制了源点 的数据包丢失率。这样，通过区别对待不同的源点，数据包调度算法和缓冲区 调度算法能对各个源点提供不同的q o s 。 限制竞争的技术：限制竞争的技术取决于源点的q o s 需要，要综合考虑到源点 既有保证0 0 s 服务又有尽力传输服务。 _ 保证的0 0 s ：此时，源点需要网络保证最小带宽、数据包延迟上限、延时 差和数据包丢失率等q o s 参数。数据包延迟和数据包丢失率或者是确定性 的或者是由概率决定的。为了满足源点的q o s 需要，网络使用开环控制技 术，源点对网络规定它的平均速率、峰值速率和突发尺寸等q o s 需要和流 量特征，反过来网络使用许可控制算法来决定是否给以源点许可权。许可 控制算法使用网络交换机的数据包调度算法和以被许可的源点来决定是 否新源点的q o s 需要能被满足。如果需要能被满足，源点被许可且资源为 之保留。数据包调度算法被用来确保源点按说明书接收服务。 _ 尽力传输0 0 s ：此时刚络并不保留资源也并不保证是否或何时数掘包将被 传送。它通过使用闭环控制技术来避免拥塞，数据包源点估计可用的缓冲 区和连接带宽等网络状态，在或者隐含地或者明确地发现拥塞后，它们使 用加窗或基于速率的流控制算法来避免拥塞。这种控制技术可有效利用网 络资源。对源点的部分数据包要求保证q o s 而余下的数据包要求尽力传输 服务，网络可以通过结合使用开环和闭环技术来满足。由于集成服务网络 将同时支持保证q o s 和尽力传输服务的应用，开环和闭环控制技术将同时 存在。 丌环和阿环控制技术与数据包调度和缓冲区调度算法密切地交织在一起并互 相倚靠。开环控制中，数据包调度算法的特点决定了能被容许的源点的集合，因 此也决定了网络的可达到利用率。更进一步的，它确保了源点按照它的预定得到 服务。对闭环控制而言，调度算法使得：( 1 ) 网络资源的公平分配；( 2 ) 网络状态估 计；f 3 ) 不同反馈控制算法的共存1 9 】。因而，数据包调度算法和缓冲区调度算法使得 网络对不同的源点交付不同的q o s ，也可满足单个的源点的q o s 要求。所以，数据 包调度算法和缓冲区调度算法对集成服务网络的实现来说非常关键。 虽然数据包调度算法和缓冲区调度算法都很重要，数据包调度算法在满足q o s 1 0 华中科技大学博士学位论文 需要上起了更为基本的作用，这是因为虽然缓冲区调度算法控制了源点的数据包 丢失率，但数据包调度算法控制了源点的数据包延迟、数据包丢失率和啪宽。圜 此本文主要研究数据包调度算法。 集成服务网络对数据包调度算法的设计和分析提出了几个挑战。由于集成服 务网络的源点的流量特征变化很大，调度算法需对不同特征的源点提供q o s 保证， 它也要满足尽力传输服务源点的0 0 s 需要。此外，由于集成服务网络使用多种控制 技术，它需使多种控制技术共存。最后，山于将来的网络实际上足高速刚络，它 必须有效率。 1 4 国内外相关研究概况 q o s 正成为业界关注和研究的热点，i e t f 为之成立了专门的工作组，研究出 一些初步的成果，但q o s 的彻底解决还有待于更进一步的研究和发展。 1 4 1q o s 的体系结构 到目前为止，业界的不同组织或单位已提出了一些o o s 的体系结构，这包括 i b m 公司的h e i d e l b e 唱q o s 模型、美国哥伦比亚大学c o m e t 研究组提出的 x r m 模型【5 9 】、美国宾夕法尼亚大学的o m e g a 体系结构6 2 1 、加利福尼亚大学伯克 利分校的t e n e t 模型等m 6 ”。但对于i p 服务质量则主要有以下两种体系结构。 1 4 2i n t s e n ，集成服务体系结构 i n t s e r v 由i e t f 的i n t s e r v 工作组于1 9 9 4 年在r f c l 6 3 3 中提出。i n t s e r v 定 义了三种服务类型。 g u a r a l l t e e ds e r v i c e s f r f c 2 2 1 2 1 【2 7 】：对带宽、时延、数据包丢失率提供定量的 质量保证； c o n t r 0 1 l e d 1 0 a ds e r v i c e s ( r f c 2 2 1 1 ) 【2 8 1 ：给用户提供一种类似在网络欠载情况下 的服务，它是一种定性的指标； b e s t e 肋r t ：类似于目前i n t e m e t 网上提供的服务，是一种尽力而为的工作方 式，基本上无任何质量保证。 为了实现上面的服务，i m s e r v 定义了4 个功能部件，网络中的每个路出器皆 一一一 l l 华中科技大学博士学位论文 需要实现这4 个部件。 r s v p f r f c 2 2 0 5 ) f 蚓：r s v p ( r e s o u r c er e s e n ，a t i o np r o t o c 0 1 ) 即资源预约协议，它 足i n t e r n e t 上的信令拂议。通过r s v p ，用户可以给每个业务流( 或连