（通信与信息系统专业论文）基于服务曲线的公平分组调度算法的设计与实现.pdfVIP

； f 于交通人学坝1 ：学位论文 基于服务曲线的公平分组调度算法的设计与实现 摘要 f 随着i n t e m e t 的高速发展，近年来在互联网上出现了多种新的网 ； 络应用，这些应用对网络所能提供的q o s ( q u a l i t y o f s e r v i c e 服务质 量) 保证提出了很高的要求。传统的i p 网络提供的是尽力传输服务， 这种服务很难满足新应用的需求，特别是那些对时延、时延抖动、带 宽和丢失率等参数有着很高要求的实时和交互式应用，在现有的 i n t e r n e t 上很难产生令人满意的效果。这就需要对目前存在的网络体 系结构进行一定的改进，使之能够提供q o s 保证。为了达到这一目 的，i e t f 提出了一些新的网络模型，例如集成服务模型和区分服务 、。 模型等，它们可以提供不同级别的服务质量保证。) 本文对那些为提供 网络服务质量保证而要使用到的技术进行了比较深入的讨论。 分组调度是在网络中提供服务质量保证的关键环节。f 所谓的分组 调度就是指：当需要发送分组时，路由器依据一定的算法从若干不同 的队列中选取某个合适的分组予以转发。人们往往从时延性能、公平 、7 性、复杂度三方面来衡量个算法的好坏j 作为提供网络q o s 保证 的重要手段之一，分组调度在近十年中得到了广泛而深入的研究，产 生了许多分组调度算法，并发展出了一门称为网络演算的专门用于分 组调度算法研究的理论。 基于服务曲线理论的s c e d 分组调度算法是众多分组调度算法 淘交通人学坝【j 学位论文 中一个比较重要的算法，f 它有许多很吸引人的优点，例如该算法可以 、 提供时延与带宽保证的解耦。但是，s c e d 分组调度算法存在公平性 不足的问题，这个缺点将对算法的实用性产生不利的影响。在前人研 ，旷一 究的基础上我们对s c e d 分组调度算法存在公平性不足的问题进行 了一些讨论，并设计了一种经过改良的基于s c e d 的分组调度算法， 这种算法称为f s c e d ( f a i rs e r v i c ec u r v e b a s e de a r l i e s td e a d l i n ef i r s t 公平的基于服务曲线的最早期限优先算法) 。我们利用n s 2 网络仿真 软件对这算法进行了性能测试，实验证明该算法可以达到预定的设 计目标。 关键词：服务质量，分组调度，网络演算，服务曲线，s c e d ，公平 性 t h ed e s i g na n di m p l e m e n t a t i o no f f a i rs e r v i c ec u r v eb a s e d p a c k e t s c h e d u l i n ga l g o r i t h m a b s t r a c t t h e e x p o n e n t i a ld e v e l o p m e n t o ft h ei n t e r n e tm a k e sm a n yn e w n e t w o r ka p p l i c a t i o n sa p p e a r , w h i c hh a v es t r i n g e n tr e q u i r e m e n t so nt h e q o s ( q u a l i t yo fs e r v i c e ) p r o v i s i o n e db yt h e n e t w o r k t h eb e s te f f o r t s e r v i c et h a ti s p r o v i d e db yt h et r a d i t i o n a l i n t e m e ti sh a r dt om e e tt h e d e m a n d s e s p e c i a l l yt h eo u t c o m e o fr e a l t i m ea n di n t e r a c t i v ea p p l i c a t i o n s t h a ta r eh y p e r c r i t i c a lo np a r a m e t e r so fd e l a y , d e l a yj i t t e r , b a n d w i d t ha n d l o s sr a t ec a n h a r d l ym a k ep e o p l e s a t i s f i e d h e n c et h ec u r r e n ta r c h i t e c t u r e o ft h ei n t e r n e th a st ob ei m p r o v e di no r d e rt op r o v i d eb e t t e rq u a l i t yo f s e r v i c e i e t fh a sm a d es o m ee f f o r t s t h ei n t s e r va n dd i f f s e r vm o d e la r e t w oa t t e m p t sr e c o m m e n d e db yi e t ft oi m p r o v et h ep e r f o r m a n c eo ft h e i n t e r n e t v a r i o u s c o m p o n e n t s t h a ta r ec r i t i c a lt on e t w o r k q o s a r e d i s c u s s e di nt h i sd i s s e r t a t i o n p a c k e t s c h e d u l i n g i sab a s i c q o sc o m p o n e n t ap a c k e t i s g e t s c h e d u l e dm e a n st h a tt h er o u t e rs e l e c t sap a r t i c u l a rp a c k e tt ot r a n s m i t f r o ms e v e r a l q u e u e sa c c o r d i n g t oa s p e c i f i cq u e u i n gd i s c i p l i n e t h e c r i t e r i au s e dt oj u d g et h eu s e f u l n e s so faq u e u i n gd i s c i p l i n ec o n s i s t so f l a t e n c y , f a i r n e s sa n dc o m p l e x i t yo f t h ea l g o r i t h m a sa ni m p o r t a n tm e a n s 4 海交通人学坝l 学位论史 t op r i v i d en e t w o r kq o s ，p a c k e ts c h e d u l i n ga l g o r i t h mh a sb e e nc o m p l e t e l y s t u d i e di nt h el a s td e c a d ea n dal o to fa l g o r i t h m sa r e s u g g e s t e db y d i f f e r e n tr e s e a r c h e r s e v e nat h e o r yc a l l e dn e t w o r kc a l c u l u si sd e r i v e d d u r i n g t h ep e r i o do fr e s e a r c h s c e d ，a s e r v i c ec u r v eb a s e d p a c k e ts c h e d u l i n ga l g o r i t h m ，i so fg r e a t i m p o r t a n c ea m o n g v a r i o u s d i s c i p l i n e s d e c o u p l i n g o f d e l a y a n d b a n d w i d t hg u a r a n t e ei so n eo ft h ea t t r a c t i v ep r o p e r t i e so fs c e d ，b u ti t l a c k sf a i r n e s s t h i sd e f i c i e n th a sn e g a t i v ei m p a c to nt h eu s e f u l n e s so ft h e a l g o r i t h m i nt h i sd i s s e r t a t i o nw ed i s c u s st h el a c k n e s so ff a i r n e s sa n d m a k ea ni m p r o v e ds c e d a l g o r i t h mt h a ti sc a l l e df s c e d a v a i l a b l e w e u s ea s 一2n e t w o r ks i m u l a t i o ns o f t w a r ep a c k a g et ot e s tt h ea l g o r i t h ma n d t h er u l ti n d i c a t e st h a tt h ef s c e d a l g o r i t h m h a sa c h i e v e di t so b j e c t s k e yw o r d s ：q o s ，q u e u i n gd i s c i p l i n e ，p a c k e t s c h e d u l i n g ，n e t w o r k c a l c u l u s ，s e r v i c ec u r v e ，s c e d ，f a i r n e s s 5 第1 章引言 随着i n t c r n e t 的高速发展，近年来在互联网上出现了多种新的网络应用，这 些应用列网络所能提供的q o s ( q u a l i t yo f s e r v i c e 服务质量) 保证提出了很高的 要求。作为提供网络q o s 保证的重要手段之一，分组调度( p a c k e ts c h e d u l i n g ) 在近十年中得到了广泛而深入的研究。在前人研究的基础上，我们设计了一种经 过改良的分组调度算法，这种算法称为f s c e d ( f a i rs e r v i c e c u r v e b a s e d e a r l i e s t d e a d l i n ef i r s t 公平的基于服务曲线的最早期限优先算法) ，并利用a s 2 网络仿真 软件i i 】对这一算法进行了性能测试。算法本身、算法相关理论、仿真结果都将在 本文中予以介绍。 1 1 q o s 要求 随着i n t e m e t 的高速发展，近年来人们对网络提出了越来越高的q o s 要求。 如同文 2 中所述，在这一趋势的背后隐藏着两个主要的驱动力。第一个驱动力 是新型网络应用的产生，这主要是指v o l p ( v o i c e o v e r i p n e t w o r k 基于网络的语 音应用) 和v o d ( v i d e oo nd e m a n d 基于网络的视频服务) 。v o l p 要求网络为分 组提供端到端时延( d e l a y ) 和分组丢失率( 1 0 s sr a t e ) 的保证，v o d 要求网络提 供带宽( b a n d w i d t h ) 保证，这些都是传统l 刊络无法保证的，也f 是网络q o s 理 论所要保证的三个基本要素。第二个驱动力是市场对网络提供服务区分( s e r v i c e d i f f e r e n t i a t i o n ) 的要求，这一压力主要来源于商业上的考虑。可以举一个提供 v p n ( v i s u a lp r i v a t e n e t w o r k 虚拟专用网络) 服务的网络服务供应商的例子，如 果有两个提供v p n 服务的网络服务供应商进行竞争，其中一个只提供保证安全 的v p n 服务，另一个在提供保证安全的v p n 服务之外还为v p n 用户提供虚拟 租用专线( v i r t u a ll e a s e dl i n e ) 服务，无疑后者比前者更有竞争力。这就迫使网 络服务供应商使用q o s 技术为不同的用户提供不同的服务，通过增加网络附加 值的方式来提高竞争力。 总的来说，随着i n t e m e t 的高速发展，人们对网络的q o s 要求越来越高，传 统网络已无法令人满意，这就需要向网络引入一些新的机制来满足人们的需求。 1 2 q o s 组件 提供q o s 保证的网络需要同时使用许多q o s 组件( c o m p o n e n t ) ，这些q o s 组件分别提供不同的功能，我们可以从这些组件的作用时间数量级来进行考察。 最小一级时间数量级是分组级( 作用叫间l 1 0 0 a s ) ，在这一级别上工作的主要 就是分组调度技术，分组调度是逐分组进行的；较大一级时间数量级是i h t ( r o u n dt r i pt i m e ) 级( 作用时间1 l o o m s ) ，在这一级别上工作的是全网的流量 控制( f l o wc o n t r 0 1 ) 和拥塞控制( c o n g e s t i o nc o n t r 0 1 ) ；最大一级时间数量级是会 话( s e s s i o n ) 绒( 作用时间数量级是分、小时) ，在这一级别上工作的是接纳控 制( a d m i s s i o nc o n t r 0 1 ) 和网络路由；除了上述三个级别以外还有一些组件在各 个时间数量级上( 包括分、小时、天、月、年) 都要产生作用，业务量工程( t r a f f i c e n g i n e e r i n g ) 就是这样的一个例子。 洵交通人学坝i j 学位l 仑文 在这么许多q o s 组件中，分组调度起着基础性的作用。所谓的分组调度就 是指：当需要发送分组时，路由器依据一定的算法从若干不同的队列中选取某个 合适的分组予以转发。前面已经提到，分组的时延( 包括时延抖动j i t t e r ) 、带宽、 丢失率是提供q o s 服务的网络所要保证的三个基本要素，而这些保证是由分组 调度技术直接提供的。 1 3 分组调度 分组调度的研究发端于八十年代术，至今已有十余年历史。最早提出的分组 调度算法都是基于理想流模型的，其中第一篇讲述基于理想流模型的f q 算法的 文章是 3 】，后来在f q 算法的基础上又衍生出了w f q 、w f 2 q 1 4j 、w f 2 q + 【5 j 、 s c f q t 、s f q “、f f q 8j 等算法。其中a b h a yk p a r e k h 写的【9 】、 1 0 对以后的分 组调度理论研究产生了深远的影响。上述这些算法实际上都是基于速率的，后来 又出现了基于时延的调度算法，包括e d f 1 r c s 【l2 j 等。随着近年来i n t e m e t 的 高速发展，分组调度理论又有了新的研究方向，主要是探讨大规模网络中如何利 用流聚集来减少单个节点的流状态信息，这一方向与d i f f s e r v 的研究方向是一致 的，典型的算法是c s f q ”“、s c e d + i i 叫等等。 随着研究的深入，分组调度已从最早的调度算法研究发展出了一门用来研究 调度算法的理论，这一理论称为网络演算( n e t w o r kc a l c u l u s ) 。网络演算理论已 经比较成熟，近两年来国外已出现了讲授这一理论的教材i i “、【”j 。s c e d 分组调 度算法可以认为是这一理论应用于分组调度的一个例子。 1 4 我们的工作 我们的工作主要是对s c e d 调度算法进行了一些讨论，指明这一算法在公平 性( f a i r n e s s ) 上存在着问题，并逐步对这一算法进行了改进，最后在文中完整 地阐述了s c e d 调度算法的改良f s c e d 调度算法。为了验证这一算法的有效性， 我们利用n s 一2 网络仿真软件对这一算法进行了性能测试，仿真结果表明f s c e d 调度算法达到了预期的设计目标。 1 5 各章内容 本文的第一章是引f i - ，主要是对论文内容的介绍：第二章是例络q o s 背景， 主要介绍了在q o s 技术中经常使用的几个组件，以及近儿年来i e t f 及其它 i n t e r n e t 研究力量提出的几种为i n t e m e t 引入q o s 服务的体系结构：第三章是分 组调度算法，主要按分组调度算法类别的不同介绍了几个较为重要且具有代表性 的算法，并对这些算法作了一些比较；第四章是服务曲线理论及f s c e d 算法， 先是介绍了f s c e d 调度算法的理论基础，接着讨论了s c e d 调度算法的不足， 然后逐步对这一算法进行了改进，最后完整地阐述了f s c e d 调度算法并给出了 算法的伪码；第五章是仿真结果及分析主要展示了f s c e d 调度算法的n s 2 仿 真结果，并对这些结果作了分析，指出f s c e d 调度算法达到了预定的设计目标； 第六章是全史的总结。 海交通人学坝l 学位论义 第2 章网络q o s 背景 在i n t e r n e t 的发展过程中出现了许多诸如i p 电话、视频点播、远程教育、远 程会议、远程医疗之类的新的应用。这些应用具有一些传统应用所不具有的特点。 对于e 。m a i l 、f t p 等传统应用，i n t e r n e t 所提供的b e s te t t b r t 服务已经足够了，但 是对于新的应用，b e s te f f o r t 服务却不能令人满意。 现有的工作在i n t e m e t 上的应用，依照对数据传输时延要求的不同，可以作 如下的一个划分。 对时延的容忍程度类型描述 异步对时延无任何要求 次高同步所传输的数据对时延敏感，但对时延无严格要求 d 交互过人的时延会被州户察觉，但不影响应用的使_ l j 次低等时过人的时延将影响麻_ l j 的使t l j 低任务关键过大的时延将使鹿刚无法使用 表2 - l 网络应用的时延敏感性分类 t a b l e 2 - 1c l a s s i f i c a t i o no f n e t w o r k a p p l i c a t i o n su s i n gs e n s i t i v i t yt od e l a y 从上表可以看出，新的应用对于网络的服务质量有很高的要求，但是传统的 i p 网络无法提供服务质量的保证，这就需要在网络中引入q o s 机制，从而使得 旧有的网络经过q o s 改造后可以很好的支持新的应用。 2 1 q o s 组件 2 1 1 分组分类 分组分类( p a c k e tc l a s s i f i c a t i o n ) 是q o s 机制的一个重要组成部分。所谓分 组分类就是指依据分组首部的若干信息将分组分到不同的类别中去，从而使得不 同的分组有可能得到不同的服务。原始的i p v 4 协议中i p 分组的t 0 s ( t y p eo f s e r v i c e ) 域就是一个分组分类的例子，但是由于 l o s 域从未被真正使用过，所以 分组分类的作用也无从体现，然而分组分类在i e t f 的d i f l s e r v 模型中有很大作 用。d i i t s e r v 模型对i p 分组的首部重新作了定义，如下图所示， 图2 - 1d i f f s e r v 模型中d s 域的定义 f i g 2 - 1d e f i n i t i o no fd sf i e l di nd i f f s e r vm o d e l 0 j f j 交通人学帧 j 学位论史 d i t p s e r v 模型对i p v 4 中的i p 分组首部的 l o s 域重新作了定义，该域被重新 命名为d s 域( d i f f e r e n t i a t e ds e r v i c ef i e l d ) 。如图2 1 所示，d s 域的前六位称为 d s c p ( d i f f e r e n t i a t e ds e r v i c ec o d ep o i n t ) ，后两位朱使用。在d i f f s e r v 模型中， 分组进入网络边缘时首先要进行分类，其分类结果被编码并用d s c p 予以纪录， 后续路由器根据分组的d s c p 值来选择该分组的p h b 。这实际上是进行了一次 业务流聚集( t r a f f i ca g g r e g a t i o n ) ，使得数目繁多的流依据其业务性质的不同被 聚集到少量的几个类中，这样就减小了网络核心路由器的负担。 2 1 2 流量成形 许多应用都要求网络提供端到端的时延保证，但是由于应用的任意性，进入 网络的业务流往往是随意的，这样网络就很难提供时延保证。于是就有必要在网 络的边缘对业务流进行整形，使进入网络的业务流具有一定的特征，以便于后续 网络提供q o s 服务。 流量成形( t r a f f i cs h a p i n g ) 通常利用漏桶( l e a k y b u c k e t ) 模型来描述， 定义2 1漏桶通过以下的方式对业务流进行处理：漏桶可以容纳b 个单位 数据，在漏桶底部有一个孔，漏桶内的数据可以以，单位数据秒的速率从漏桶 中流走。漏桶初始为空，当漏桶非空时数据以恒定速率从漏桶中流走，如果在漏 桶未满时有数据进入漏桶则这些数据被丢弃。 这样，业务流经过流量成形后的输出在任何时刻f 都不会大于r t + b 。从下图 可以直观地看出流量成形的作用。 图2 - 2 流垃成型 f i g 2 2t r a f f i cs h a p i n g 图2 2 ( 1 ) 是未经流量成形的输入业务流，图2 - 2 ( 2 ) 是该业务流通过整 形器( s h a p e r ) 后的输出。 通过使用整形器，路由器就可以对那些资源使用超出预先约定的流进行控 制，使之不会将网络资源消耗光，同时也限制了业务流的特性，便于以后提供 q o s 保证。 2 1 。3 分组调度 所谓的分组调度就是指：当需要发送分组时，路由器依据一定的算法从若干 不同的队列中选取某个合适的分组予以转发。f i f o ( f i r s ti nf i r s to u t ) 队列是最 简单的一个例子，在这种队列中，路由器总是按照分组到达的顺序来进行转发。 其他算法的分组离去的顺序与分组到达的顺序有可能不同。 传统的路由器总是使用f i f o 方式来转发分组，但是这种方式有若干缺点： 1 流与流之问无法隔离，一个流的行为可能影响其他的流；2 无法对流提供带宽 保证；3 无法对流提供时延保证；4 彳亍为不当的流会导致数据丢失率的急剧上升； 5 无法公平对待所有的流。因此就有必要使用其它算法来进行改进。 通过使用合适的分组调度算法，路由器就可以对分组的带宽、时延、时延抖 动、丢失率等要求予以保证。应用可以先对所需的资源进行预约，在获得保证后 再使用网络，这样就可以保证应用的q o s 要求了。 当然，在路由器中使用复杂的调度算法也要付出一定的代价。复杂的调度算 发会给分组带来额外的时延，这就要求在设计算法时要考虑到算法的复杂度，必 要时可以由硬件来实现， 以后的章节将对分组调度予以详述。 2 1 4 缓存管理 为了满足多种i n t e r n e t 应用不同的q o s 要求，网络中的每个节点必须合理地 为应用分配资源。单个节点拥有的资源包括缓存和带宽两大类，与之对应的，分 组调度是用来管理带宽的机制，而缓存管理就足用来管理缓存的机制。 分组交换网络是以统计时分复用( s t a t i s t i c a lt i m ed i v i s i o nm u l t i p l e x i n g ) 的方 式来工作的，因此不可避免地会产生分组丢失的现象。当路由器的缓存已满时如 果又有分组到达，路由器不得不从缓存中选择分组予以丢弃，这就是缓存管理 ( b u f f e rm a n a g e m e n t ) 。 传统的f i f o 队列使用队尾丢弃( d r o p t a i l ) 的方式进行缓存管理，这种方 式虽然简单，但是有许多缺点。例如，当由某个流占掘了队列的大部分空间时， 属于其他流的分组进入队列时都会被丢弃，这样一个行为失当的流就会使其他流 饿死，采用其他的缓存管理方式可以有效避免这一点。 对于某些应用而占，并非流中的所有分组郜同等重要。例如传输m p e g 视 频的数据流，流中的i 帧比b 帧更重要，因此有必要赋予二者不同的优先级，在 需要丢弃分组时不使用简单的队尾丢弃的方式。 基于这些考虑，许多异于d r o p t a i l 的缓存管理方式被设计出来，包括 d r o p h e a d ”1 、r e d ( r a n d o me a r l yd e t e c t i o n ) 1 8 1 、b l u e t ”1 等等。 2 1 5q o s 路由 传统的i n t e r n e t 路由只保证网络的连通性，对于需要提供q o s 保证的网络来 既是不够的。这就有必要使用新的路由方式，即基于q o s 的路由。 使用q o s 路由要达到两个目的：1 为分组选择满足q o s 要求的通路；2 使业 海交通人学坝i 学位论文 务流在网络中分布合理，从而使网络被充分利用。 与传统路由方式不同，q o s 使用的网络链路权值不只是跳数，而可以包括连 路带宽、时延、当前负载等多种参数。这些参数既可以是静态指定的，也可以通 过动态测量网络来得到。使用这些参数作为选路依据时有多种方式可以进行，既 可以为每个参数设置权重，然后计算出单条链路的权值，也可以在路由器中使用 多张路由表，使分组在需要转发时有多条路径可以选择。 使用基于q o s 的路由也会引入新的问题。当路由器通过q o s 路由发现存在 负载较轻的通路时会将业务流导到该通路上，从而改变当前的网络负载情况。经 过一段时f 日j 可能发现原来负载较重的通路的负载下降了，于是又会将业务流导回 到原通路。如果业务流在不同路径上来回切换的速率过快就会导致网络震荡 ( o s c i l l a t i o n ) ，这会产生过多不必要的额外丌销，不利于网络资源的利用。此外， q o s 路由协议和算法比较复杂，会增加路由器间传输的路由信息的信息量，并增 加路由器的计算丌销，在使用0 0 s 路由时这些因素都要考虑在内。 2 2 i n t s e r v 模型 为了在i n t e r n e t 中引入q o s 机制，i e t f 于1 9 9 4 年提出了i n t s e r v 模型1 2 。 在这个模型中，应用在传输数据f ；1 首先要通过某种方式描述自己的q o s 要求， 并将之提交给网络，接入路由器根据现在的网络状况决定是否接纳这一请求：倘 若接纳，则需要使用r s v p 协议1 2 l j 在流所通过的每个路由器上进行资源预留； 当数据开始传输时路由器要为所有通过该路由器的流保留状态信息。i n t s e r v 模 型通过这样的方式为应用提供q o s 保证。 i n t s e r v 模型支持两种提供不同q o s 保证的服务，称为保证服务( g u a r a n t e e d s e r v i c e ) 1 2 2j 和负载受控服务( c o n t r o l l e d l o a ds e r v i c e ) 1 2 “。 保证服务：这种服务确保应用的可用带宽和端到端的时延上界，并且保证如 果应用产生的业务流特征未违背预约时可穿越网络而不经受分组丢失； 负载受控服务：这种服务不提供严格的q o s 保证，而只提供统计意义上的 q o s 保证。在网络没有过载的情况下，使用负载受控服务的应用可以得到相 当低的分组丢失率，而且产生的分组中的大部分将在时延上界以内到达目的 地。可以认为负载受控服务类似于在网络负载较轻情况下b e s te f f o r t 方式所 提供的服务。 2 2 1 参考实现模型 支持i n t s e r v 模型的路由器要使用许多在七一节中提到的q o s 组件，使用这 些组件的路由器参考实现模型可用下图表示。 2 2 2 工作原理 图2 - 3i n t s e r v 参考模型 f i g 2 - 3 i n t s e r vr e f e r e n c em o d e l 巨群f d e l a y b o u n d = 幽r p 尚r 降r 叫月( 一，)l”+ r 等+ 陋k 月 其中c = h2 jn c n d = e n ：l2n d n 。 淘交通人学坝j 学位沦史 2 。2 3r s v p i n t s e r v 模型只规定了网络通过伺种方式来提供q o s 保证，并未包括用来在 网络元素问传递控制信息的信令协议，这一任务由资源预留协议r s v p 协议完 成。i n t s e r v 依靠r s v p 逐跳( h o p b y h o p ) 地建立( s e t - u p ) 或拆除( t e a r - d o w n ) 每个流的资源预目软状态( s o f ts t a t e ) 。 下图是一个利用r s v p 进行资源预留的一个例子。 图2 - 4 用r s v p 进行资源预留 f i g 2 - 4r e s e r v er e s o u r c eb yu s i n gr s v p r s v p 在进行资源预留时主要使用两个命令：p a t h 和r e s v 。图2 - 4 包括两 个流，一个是传递p a t h 消息的广播流，另一个是传递r e s v 的预留流。 p a t h 消息由要使用q o s 服务的应用从源端发出。这条消息中包括源的 t s p e c ，它代表了源将要产生的业务流的特征。p a t h 消息中的t s p e c 域在传 输过程中不会被修改。p a t h 消息中包括另一个域a d s p e c ，这个域被用来记 录c ，。，和d ，。，。p a t h 消息通过每个节点时a d s p e c 都会被修改，到达终点时 产生积累后的c k ，和d 。当网络节点收到p a t h 消息时不作任何资源预留 工作。 r e s v 消息由应用的目的端发出，这条消息完成真正的资源预留工作。r e s v 消息逆着p a t h 消息的发送路径传输，消息中的r s p e c 域记录着节点为响应 p a t h 消息的要求而保证的带宽下限。 2 2 4 缺点 在i n t s e r v 的部署过程中，人们发现了该模型在实际使用中的一些问题。 i n t s e r v 是基于流的、状态相关的体系结构，i n t s e r v 中的节点要记录每个流 ( p e r - f l o w ) 的状态并对每个流进行管理。这种实现机制一方面使i n t s e r v 能够提 海交通人学f 血l 学位论文 供更高的灵活性和更好的多级别服务，但同时也导致i n t s e r v 在可扩展性 ( s c a l a b i l i t y ) 和鲁棒性( r o b u s t n e s s ) 卜存在问题，其后果是实现复杂，难于应 用。 在i n t s e r v 体系结构中，网络中每个节点都要维护各类数据库。例如，对于 使用链路状态协议的q o s 路由，路由器必须同时维护链路状态数据库和q o s 路 山表；路由器还必须为通过它的每个流维护资源( 例如带宽、缓存) 使用信息。 与此同时，路由器还要实现复杂的功能模块( 如资源预留、路由、整形等等) 。 r s v p 信令协议提供q o s 协商机制；各网络节点建立和维护预留信息，并根据自 身资源状况对用户的预留请求进行接纳控制；数据传输时各网络节点监控传输 流，并提供相应服务。这种完全分布式的控制造成了极大的复杂性。 要将现有的i n t e r n e t 改造成完全的i n t s e r v 网络需要极大的投入，要求人们在 世界范围的网络中引入繁重的软件和硬件修改，实现难度很大。这严重妨碍了 i n t s e r v 在大型网络中的应用。 归纳起来，i n t s e r v r s v p 结构存在以下几个比较严重的问题： 基于流的r s v p 资源预留、调度处理以及缓冲区管理，有利于提供q o s 保证，但使系统开销过高，对于大型网络存在可扩展性的问题； 目前，只有少量的主机产生r s v p 信令，虽然其数量预计会大幅度增长， 但许多应用却从不产生r s v p 信令，因而在实现时修改应用所遇到的阻 力会很大； 许多应用的q o s 要求无法用i n t s e r v 模型来表达； 由于i n t s e r v 在实现时有许多难以克服的缺点，纯粹的i n t s e r v r s v p 结构实 际上无法被业界接受，在商业上不可能有大的作为。现在人们普遍认为，i n t s e r v r s v p 以其现在的形式将不会在i n t e m e t 中得到广泛应用。 2 3d i f f s e r v 模型 i n t s e r v 模型中的每一个路由器都需要保持通过该路由器的所有流的状态信 息，在网络规模不太大的时候路由器的负担还不算太重，但对于i n t e r n e t 的骨干 网络( b a c k b o n e ) 上的路由器来说要实现这一点有相当大的困难，因此i n t s e r v 模型的可扩展性很差。i n t s e r v 模型的另一个缺陷就是它很难逐步部署，如果要 利用i n t s e r v 模型来提供网络的q o s 保证就必须在全网中都使用i n t s e r v 路由器。 由于i n t s e r v 模型有这两个缺点，i e t f 又提出了d i f f s e r v 2 4 1 模型。 d i f f f 3 e r v 模型与i n t s e r v 模型相比有着三个显著的不同之处：1 在i n t s e r v 模 型中q o s 提供对象是流，粒度很细，但在d i f f s e r v 模型中边界路由器要对流进 行聚集( a g g r e g a t i o n ) ，传输网络中的路由器要处理的仅仅是经过聚集后的流， 粒度很粗，因此就有可能保留它们的状态信息，换言之，d i f 俗e r v 模型的可扩展 性要比i n t s e r v 模型好得多。2 与i n t s e r v 模型不同，d i f l s e r v 模型中的路由器可 以逐渐部署，从而逐步改善网络的服务质量，虽然此时的服务并不能提供严格的 0 0 s 保证，但它可以提供比b e s te f f o r t 服务要好的服务质量。3 i n t s e r v 模型对传 输网络中的路由器有着很高的要求，d i f l s e r v 模型则把大部分的工作推到了网络 边界上，它要通过边界路由器来进行分组分类、数据流聚集等工作，i n t s e r v 模 型中传输网络有着较高的智能，d i f f s e r v 模型中的传输网络相对比较无能 ( d u m b ) 。 淘交通人学帧l 。学位论文 2 3 1 工作过程 在d i f l s e r v 模型中，路山器被分成边界路山器( e d g e r o u t e r ) 和核心路由器 ( c o r er o u t e r ) 两大类，两者的功能有较明显的区别。边界路由器要埘注入网络 的业务流予以摔制，它所要完成的工作包括：需要依掘网络服务提供者与用户事 先约定的s l a ( s e r v i c el e v e la g r e e m e n t j 进行接纳控制；刈注入的业务流进行 整形；刈微流( m i c r o f l o w ) 进行聚集；为每个分组作上d s c p 标| 己，等等。业 务流住通过边界路由器后被分入为数不多的儿个q o s 类中，供网络的核心路由 器使用。核心路由器位于网络的内部，负责对幅于不i 几jq o s 类的分组进行不l j 的处理，这些处埋方式被称为p h b ( p e r h o p b e h a x ，i o r ) ，分组中的d s c p 域就是 被用来选择p h b 的。 i e t f 并未觇定路由器必须实现何种p h b ( b e s te f f o r t 服务除外) ，d s c p 与 p h b 之州的对应关系也不足令网固定的。提供某个特定p h b 服务集上土规定了 d s c p 与p h b 之间的对应关系的子嗍被称为d s 域( d sd o m a i n ) 。通常不同的网 络服务提供商之川i i 的网络属于不同的d s 域，当分组离丌荣个d s 域进入另一个 d s 域时住往需要罩新标注d s c p ，这是位丁不同d s 域之问的路由器所要完成的 工作。由十这种路由器是分组离外d s 域的出口，因此被称为出口路由器( e g r e s s r o u t e r ) ，以别于分组进入叫络时通过的入厂i 路l “器( i n g r e s sr o u t e r ) 。 d i f f s e r v 模罐的网络拓 町玎1r l 冬i 表示， d sd o m a i n ， t r a f f icc o n f 1 i t i o n i n g 蚓2 - 5d i t 体m v 网络拓补 f i g 2 5d i f e s e r vn e t w o r k 2 。3 2 参考实现模型 支持i n t s e r v 模型的路山器同样要使用许多在第一节中提到的q o s 组件。由 湘交通人学坝i 学位沦义 于d i f f s e r v 模型中的边界路由器和核心路由器的功能有所不同，它们的结构也不 太一样。入口路由器、核心路由器、出口路由器的参考实现模型分别由下图中的 ( 1 ) 、( 2 ) 、( 3 ) 表示， ( 1 ) 入口路由器 ( 1 ) i n g r e s sr o u t e r ( 2 ) 核心路由器 ( 2 ) c o r er o u t e r 海交通人学坝l 学位论文 2 3 3 p h b 种类 ( 3 ) 山口路由器 ( 3 ) e g r e s sr o u t e r 幽2 - 6d i f f s e r v 参考模型 f i g 2 - 6d i f f s e r vr e f e r e n c em o d e p h b ( p e r h o pb e h a v i o r 逐跳行为) 是对可从外部观察到的d i f f s e r v 节点转 发经过聚集后的业务流的行为的描述。d i f f s e r v 节点通过业务流中的i p 分组首 部的d s c p 域来为业务流选择p h b 。p h b 可以用转发业务流时的一些特性参数 ( 如带宽、时延、丢失率) 描述。当有多个p h b 共存于同一d i f r s e r v 节点时， 还必须指出在分配资源( 如带宽、缓存) 时不同p h b 之间的相对优先级。事实 上，也只有在多个经过聚集后的业务流竞争资源时，p h b 甚至整个d i i t s e r v 体 系才有意义。p h b 实际上描述的就是单个节点为经过聚集后的特定业务流分配 资源的方式；d i f f s e r v 体系的整体资源分配策略也就通过这一个个单节点资源分 配实现的。 应该注意的是，p h b 仅是d i f t s e r v 节点转发经过聚集后的业务流的外部特 征描述，而不涉及具体的实现机制。p h b 的实现可以用分组调度与缓冲管理等 各种算法，如p q 、c b q 、r e d 等。 已由i e t f 定义的p h b 主要由以下几种。 1 ) 缺省p h b ：缺省p h b 就相当于传统i p 网络提供的b e s te f f o r t 服务。任何一 个d i f f s e r v 节点都应支持这种p h b 。r f c 舰定缺省p h b 的d s c p 是0 0 0 0 0 0 。 此外，在d s c p 到p h b 的映射表中，任何没有明确指出映射关系的d s c p 也都被映射到缺省p h b 。换句话说，d s c p 无明确意义的i p 分组都将接受传 统的b e s te f f o r t 服务。通常情况下，缺省p h b 具有最低的优先级。这种p h b 可以用如下方式实现：属于本p h b 的i p 分组仅在链路空闲时被发送。为保 1 9 淘交通人学1 ：i ! ! f j 学位论殳 证未支持区分服务的用户可以像住常一样使刖网络，可以采用为缺省p h b 保留少量资源的策略，以防止侄高优先级聚集业务流存在时属于缺省p h b 的流饿死( s t a r v a t i o n ) 。 2 ) 加速转发p h b ( e x p e d i t e df o r w a r d i n gp h b ) 2 5 1 ：e fp h b 是在讨论奖赏服务 f p