（通信与信息系统专业论文）基于用户需求的ip网络qos算法研究.pdf

插图目录 图2 1 执行w f q 算法的路由器带宽与会话数关系 图2 2 路由器中会话数与时延的关系 图2 _ 3 路由器中会话数与丢包率之间的关系 图2 4 边缘节点进行数据包分类和调节 图2 5 核心无状态网络模型 图26 边缘路由器与核心路由器的功能图 图3 1 传统令牌桶整流机制 图32 动态令牌桶整流机制 图3 3 基于供需平衡的核心无状态网络 图3 4 边缘路由器与核心路由器结构 图4 1 仿真网络拓扑结构 图4 2 路径s 3 7 1 叫上的涨落， 图4 3 路径s 2 5 8 d 上的涨落 图4 4 路径s 1 4 8 d 上的涨落 图4 ，5 路径s 1 4 8 d 上的流量 图4 6 路径s 3 7 1 0 d 上的流量 图4 7 路径s 1 4 8 d 上的涨落 图5 1c j v c 与j v c 端到端延迟保证算法实现描述 图5 2 端到端时延计算路径 图6 1c s f o 核心无状态公平调度算法参考模型 图6 2 公平算法举例 图6 3 核心路由器数据包丢弃概率 图6 4 简单拥塞链路拓扑图 图6 5 单一拥塞链路性能比较 图66 t c p 流公平性比较 图6 7 多拥塞链路拓扑 图6 8 多拥塞链路性能比较 图6 9 队列门限性能比较 纠烈控翦拍卯舶犯衄”叭矾酡毋铝仍|卯蛇舛舛鳄卯 北京交通大学硕士学位论文 基于用户需求的i p 网络o o s 算法研究 缩略语及符号说明 确保转发( a s s u r e df o r w a r d i n g ，简称a f ) 有效带宽指标( a v a i l a b i eb a n d w i d t hi n d e x ，简称a b l ) 平衡速率时钟( ba l a l l c er a t ec l o c k l 简称b r c ) 带宽代理( b a n d w i d t hb m k e r ，简称b b ) 区分服务( d i 髓r e n t i a t e ds e r v i c e s ，简称d i 腮e r v ) 动态包技术( d y n a r n i cp a c k e ts t a t e ，简称d p s ) 动态平衡令牌桶( d ”a m i cb a j a n c et o k e nb u c k e l ，简称d b t b ) 广义处理器共享( g 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 ) 服务水平协商( s e r v i c el e v e la g r e e m e n t 简称s l a ) 核心无状态公平队列( c o r es t a t e l e s sf a i rq u e u i n g ，简称c s f q ) 核心抖动虚时钟( c o r ej i t t e rv i r t u a lv l o c k ，简称c j v c ) 加速转发( e x p e d j t e df o r w a r d i n g ，简称e f ) 先到先服务( f i r s ti n p u tf i r s ts e i c e ，简称f l f s ) 公平早期随即检测( f a j r 舢d o me a r l yd e t e c t i o n ，简称f r e d ) 公平队列( f a j r q u e u i n 舀简称f q ) 因特尔工程任务组( i n t e r n e te n g i n e e r i n gt 砸kf o r c e ，简称【e t f ) 集成服务( i n t e g r a t e ds e i c e s ，简称i n t s e r v ) 抖动虚时钟( i i n e rv i r t u a lc l o c k ，简称j v c ) 传输控制协议( 订硼s p o r tc o n t r 0 1p r o t o c o l ，简称t c p ) 每跳行为( p 。rh o pb e h a v i o r ，简称p h b ) 核心无状态比例带宽分配( p r o p o r t i o n a lb a n d w i d t ha l l o c a t i o ns t a t e l e s sc o r e ，简称 p b a - s c o r e 服务质量( q u a l i t yo f s e “i c e ，简称q o s ) 服务质量路由( q o sm u t i n g ，简称q o s r ) 环回时间( m u n d 廿i 口t i m e ，简称r t t ) 资源预留协议( r 船o u r c e r e s e r v a t i o np r o t o c o l ，简称r s v p ) 加权公平队列( w e i g h t e df a i rq u e u i n g ，简称w f q ) 用户数据报协议( u s e rd a t ap r o t o c o i ，简称u d p ) v 独创性说明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京交通大 学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 签名占止纽日期：遂：生 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论 文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学i p 网络实验室所有。未经许可，任何 单位和个人不得拷贝。版权所有，违者必究。 弛姗纭艺脚期：娃z 巧 北京交通大学硕士学位论文 基于用户需求的i p 网络o o s 算法研究 摘要 i n t e m e t 自出现以来一直以惊人的速度增长。网络中传输的信息已经从 原来单纯的数据向多媒体扩展，除了传统的w e b 、e m a i l 、f t p 等数据应 用之外，用户对于在i n t e m e t 上传输分布式多媒体实时应用( 例如视频、音 频、在线游戏等等) 的愿望越来越强烈。研究可扩展的服务质量保证机制 对推动互联网发展以及实时应用具有重要的意义。因此，服务质量也就成 为i p 网络一个重要的课题。 本文针对当前服务资源分配研究存在的主要问题，根据用户与网络之 间服务资源形成的供求关系。提出了基于服务资源供需平衡的资源分配策 略：根据用户的合理需求，允许资源分配量在一定合理的范围内波动，以 限制用户对资源的过度侵占，并确保对用户的基本资源供给。 首先，根据网络中研究服务质量而存在的普遍性问题提出基于资源供 需平衡的用户需求表达方式，并基于核心无状态服务模式提出了一种新的 服务模式一供需平衡的核心无状态网络服务模式。对该服务模式以及实现 机制进行了详细论述。分析了基于供需平衡的用户需求模式和令牌桶模式 之间的关系。将令牌桶改造成为供需平衡的动态令牌桶。 第二，分析了核心无状态虚时钟的实现机制以及需要改进的措施，然 后描述速率保证时钟算法。最后基于第三章提出的供需平衡的核心无状态 网络服务模式，提出了一种新的基于供需平衡的虚时钟调度算法一平衡速 率时钟调度算法。通过分析证明，该算法可以为数据流提供端到端的服务 质量保证，同时保证网络的可扩展性和鲁棒性。 第三，基于第三章提出的用户需求表达方式，将传统的不提供服务质 量的路由协议改造成为服务质量路由。即提出了基于服务资源供需平衡的 北京交通大学硕士学位论文 基于用户需求的i p 网络o 。s 算法研究 源路由器算法，基于服务资源供需平衡链路状态路由算法。通过仿真实验 证明，基于供需平衡的服务质量路由不仅满足用户q o s 需求，同时平衡网 络负载，具有良好的可扩展性 最后，讨论了当前具有代表性的资源分配算法特点以及存在的问题， 主要讨论c s f o 以及其多种改进算法的实现机制。最后根据用户的q o s 需 求提出了一种新的具有可扩展性的比例带宽分配算法，通过仿真分析，该 算法能够在满足用户需求的基础上兼顾公平，为资源的分配提出了新的研 究方向。 关键词 配 服务质量，核心无状态，供需平衡，虚时钟，公平分配，比例带宽分 垄蔓至望奎堂堡主茎垡堡奎 茎王星生堕查塑! ! 塑竺g ! ! 苎鲨笪塞 a b s t r a c t w i mi n c r e a s i n ga t 付1 es 唧h s i n gs p e e ds i n c el a s tt w e m i e sy e a r s ，t h ec o n t e x ti nt h e i n t e l n e th a sa l r e a d yd e v e l o p e df r o mo r i g i n a l l ys i m p l ed a t at ot h em u l t i m e d i ai n f o m a t i o n e x c o p tt r a d i t i o n a ld a t aa p p l i c a t i o n ，s u c ha sw 曲、e m a 订、f t pe t c ，m o r ea i l dm o r eu e r sa n d d e m a l l dw a mt ot r a n s m i td i s 订i b u t e dm u l t i m e d i aa p p l i c a t i o n s ( s u c ha sv d e o 、a u d i o 、g a l l l e o n1 i n ee t c ) o nl m e m e t s o ，i ti sv e r yi m p o n a l l tt h ew o r k st op r o m o t es c a l a b l eq o s g u a r a i 】t e em e c h a n i s mo f m u l t i m e d i ar e a l - t l m e8 p p l i c a t i o na 1 1 de v e nt ot h ew h o l ei n t e r n e t t bs l o v es o m et r o u b l eo fr e s o i l r c e sa l l o ca t o no f l pq o s ，w ep r o p o s et h ed y n a m i cq o s a n ds e 阿i c er e s o u r c e sa l l o c a t i o nw t t ha i m0 fi m p r o v i n g ( sm e c h a n j s m sa n ds e r v i c e m o d e l si n t h i sd i s s e n a t i o n f i r s t w ed e f i n ean e ws e r v i c er e s o u r c ea l l o c a n o ns c h e m e b a l a i l c er e s o u r c e sa l l o c t i o ns c h e m e ，w h i c hi s8s p e c i a l r e l a t i o nf o r m a e db e t w e e nu s e r sa n d n e t 、v o r k s ，w h e r et h em o u n to fr e s o u r c e ss u p p i i e dt ou s e r si sm ea m o u n to fr e s o u r c e su s e r s r e a l l yn e e d ，n om u c hm o r ea n dn om u c h1 e s s 血a nt h a to f e q u i l i b r i u mp o i n t ，姐dt h e 蛳o u m o fr e s o i l r c e ss u p p | i e dt ou s e r si sa 1 i o w e dt 0c h a n g ed y i l 啪j c a l l yw i t h i nar e a s o n a b l es c o p e w h i c hc e n t e r sa r o u l l dt h ee q u i l i b r i u mp o i n t b a s e do nt h en e wr e s o u r c e sa l l o c a t i o nt h e o r y ，n r s t ly ，w ed e n n ean e wt o o lc a l l e dq o s 玎u c a t i o nf u n c “o n ，w 1 1 i c ho u t l n e st h en u c a t i n gt r a c eo ft h es e r v i c er e s o u r c es u p p l yl h a ti s c h a l l g i n ga r o u n dm ee q u i l i b 九l i np o i n t a tt h es 砌et i m e ，b a s e do “p r i n c i p l eo f t h et o k e n b u c k e tw ep r o p o s ead y n a m i ct o k e nb u k e n ta l g o r i 血mw h i c hm e e tu e r s r e a in e e dw i t h p r o p e r i y 硒s i g n e ds e r v i c er e s o u r c e st h e n ，w ep r o p o s ean e wi pn 毗w o r ks e r v i c em o d e i ， ( s e r v i c er e s o u r c ep r o v i s i o nb a l a n c e - s t a t e l e s sc o r e ， s r p b s t a _ t e l e s sc o r e ) w h i c hi m p r o v e d t h es c o r em o d e l sa n dd j f f s e r vm o d e l sb yd y n 锄i ct o k e nb u c k e ta i 卫o r i t h m ， s e c o n d l y ，w ea n l y s i sm a n y 血ee n d - t o e n dd a t ap a c k e ts c h e d u l i n ga 培o r i t 皿s u c ha s t h ec o r ej i 仕e rv i r t u a lc 1 0 c k ( c c ) ，s o m ei m p r o v e dc j v ca i g o r i l h m s ，a n dt h e g u a 湖t e e dr a t ec l o c k( g r c ) d a t ap 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 nb a s e do no u r n e wi p s e r v i c em o d l e s r p b s t a t e l e s sc o r e ，w ei m p r o v et h eg r ca l g o r i m m ，t h a ti st h e b a l a n c eg u a 瑚t e e dr m ec l o c k b yt h e o r ya i l l y s i s ，t h i si m p r o v e da l g o r t h mc o u l ds u p p l y e n d _ t o - e n dd e l a yg u a r 眦t e d f u n h e rm o r e ，d u et oi t sn o tn e e df 0 。p e r - f o r m i n gp e 卜订o w m a n g a g e m e n ta tc o r er o u t c r s ，i ti se a s yd e p l o yi ni pn e t w o r k s t h j r d l y ，b a s e do nt h eq o s f l u c a t i o nf u n c u o n ，a 士1 dt r a d i a t i o n a ls t a t i cr o u t i n gp r o t o c 0 1 ， s u c h 船d i s t a n c e 、，e c t o rr o u t i n gp r o t o c o j ，s o u r c er o u t j n gp r o t o c o i ，l i n ks t a 托呻u “g p r o t o c o l - w ep r o p o s et h ed y n a r n i cd i s t a n c ev e c t o rr o u t i n gp r o t o c o l ，s o u r c er o u t i “g p r o t o c o l ，l i n ks t g er o u t n g b yn s 2s i m u l a t i o nc x p e r i m e m ，t h ei m p r o v e dq o sr o u t i “g s a t i s f i e sw i t hu s e r s o o sn e e d ，b a l a i l c en e t w o r ki o a da n dh a v ew e l ls c a i a b i l i t y f o u r t h l y w ed i s c u s sa 】| “n d so fr e s o u r c e sa l l o c a t i o na l g o r t h m s ，s u c ha st h ec o r e 北京交通大学硕士学位论文 基于用户需求的i p 网络o o s 算法研究 s t a t e l e s sf a i rq u e u e i n g ( c s f q ) ，i m p r o v e dc s f qa n dt h ef a i rq u e u e i n g ( f q ) t h e n ，w e p r e s e n tan e wp r o p o r f i o n a lb a n d w j d 血aj l o c a t i ( p b a s c o r e ) 吐1 a ts a t i s f l e sw i 出u s 郇 q o sr e q u i r e m e n t a tt h es a m et i m e ，e d g er o u t e r sm a i m a i np e rf l o ws t a t ea i l dc o r er o u 钯r n o tn e e dm a i n t a i np e r 日o ws t a t e w ed i s c u s ss i m u l a t i o n so nm ep e r f o m l a n c eu n d e r d i f f e r e n ts c e n 鲥o k e y w o r d s ： q u a l n yo fs e r v i c e ，c o r es t a t e l e s s ，b a l a n c eo fp r o v i d s i o n ，v i n u a lc 1 0 c k ，f a i ra l l o c a t i o n ， p r o p o n i o n a lb a n d w i d t ha 1 1 0 c a t i o n 4 北京交通大学硕士学位论文 基于用户需求的i p 网络q o s 算法研究 1 1 引言 第一章绪论 i n t e m e t 的成功主要归因于分组交换、无连接和t c p ( t r a i l s d o r tc o m o l p r o t o c 0 1 ) 拥塞控制机制。其采用i p 作为网络层协议为各种不同介质的物 理网络提供互联互通的平台，而且，由于采用无连接机制，网络资源分配 相对简单，从而降低了网络设备的复杂度。使得网络具有极强的可扩展性 和鲁棒性。 但是，伴随着多媒体技术的飞速发展，i n t e m e t 已经逐步由单一的数据 传输网络向数据、语音、图象、视频等多媒体信息的综合传输网演化。视 频点播、视频会议、i p 电话、远程教育、远程医疗等都是今后i n t e m e t 上 典型的分布式多媒体应用。通常这些应用大多能容忍一定程度的信息丢失 和错误，但是对网络有很高的带宽要求，而且要求信息传输满足低延迟和 低抖动等服务要求。这些特征对传统的i p 网络提出了严竣的挑战。如何在 i p 网络上为实时应用提供具有良好扩展性的服务质量( q u a l i t yo fs e r v i c e ， o o s ) 保证已经成为i n t e m e t 迫切需要解决的问题。 为了满足i n t e m e t 多媒体应用的实时传输要求，近年来大量的研究者在 这方面付出了巨大的努力，取得了一系列的研究成果。研究热点主要集中 在：i p 网络体系结构的改进、路由器排队调度算法的研究、网络资源的管 理和分配、q o sr o u t i n g 算法的研究、端系统的拥塞控制机制等方面。其中 最基本的是涉及网络体系结构的改进问题。i e t f ( i n t e m e te n g i n e e r i n gt a s k f o r c e ) 先后提出了集成服务模型( i n t e g r a t e ds e f 、r i c e s ，i n t s e r v ) 1 和区分服务 模型( d i 仃e r e m i a t e ds c r v i c e s ，d i 妇! s e n ，) 【2 。两种服务模式在为多媒体流提 北京交通大学硕士学位论文基于用户需求的i p 网络q o s 算法研究 供服务质量保证方面各有优点和不足。 服务质量保证的另一个研究重点是路由器的排队调度算法。由于传统 路由器采用先到先服务( f i r s ti n p u tf i r s ts e r v i c e ，f i f s ) 3 】的机制，不能满 足多媒体流实时性要求，因此大量的文献对路由器的排队调度算法进行了 研究，提出了多种复杂度和性能各异的排队调度算法。但是，研究表明， 虽然复杂的排队调度算法可以实现良好的服务质量，但是对路由器性能要 求较高，在实际中不易实现。反之，简单的排队调度算法提供的服务质量 又相对较差。怎样在调度算法的复杂度和性能之间进行合适的折中还需要 深入的研究。 为媒体流寻找一条满足带宽和延迟的传输路径也是服务质量研究的热 点之一。但是由于网络中资源信息的瞬时性，使得路由器获得网络状态信 息是不精确、过时的。在这种状态信息下获得的质量路由存在不稳定性， 不能保证为数据流提供端到端的服务。使得大量的服务质量路由( q o s r o u t i n 臣q o s r ) 选择成为一种理想的算法。同时n p c o m p l e t e 4 1 也是困扰 服务质量路由的另一个问题。 从上面的分析可以看出，虽然网络中各种服务质量研究取得很大的进 展，但是还有大量问题没有解决，其中关键的就是i p 网络的可扩展性、鲁 棒性与网络复杂度之间的矛盾。因此要在传统的网络中重新部署提供服务 质量保证的模型和算法还是一个开放的问题。 本质上，要为用户提供服务质量保证，就需要网络提供相应的服务资 源( 带宽、缓存等) 作为根本的保障。即网络资源决定服务质量水平。如 果我们能够获得网络资源的精确信息，就可以为用户分配相应的服务资源 满足用户的服务质量需求。但是，i 熊釉e t 是一个相对松散的网络，这就决 定了在这样的网络里获得的网络资源状态信息是相对滞后的，因此状态信 息是不精确性的 5 】。在另一方面，用户对资源的需求有三个突出的特点： 6 北京交通大学硕士学位论文 基于用户需求的i p 网络q o s 算法研究 一是网络中存在多种数据流模型，不同类型的数据流在突发性、平均速率 等参数上差别极大。二是用户对网络的服务质量要求不尽相同( 例如，有 的流对丢包率e e 较敏感，有的流需要严格的延迟和抖动保证【6 】) 。三是数 据流对资源的获取往往是贪婪的、非友好的。不管是采用拥塞控制的t c p 流还是非拥塞控制的u d p 实时流，在对资源的占有上都属于“非友好”【7 】 的。只要网络中有剩余的资源，t c p 流就会不断地增加速率，直到出现拥 塞才开始减小发送速率。而u p d 实时流在网络处于拥塞情况下也不会减小 发送速率，加重网络的负担，降低整个网络的性能。 服务资源的有限性、状态信息的不精确性与用户需求之间的无限性决 定了在用户需求与资源供给之间存在矛盾和冲突。但是，如果在有序分配 服务资源的情况下，则对资源的需求能够达到所需即所求的相对平衡状态， 即所谓的供需平衡。在这种平衡状态下，网络为用户提供的服务质量是合 适的。偏离平衡只能存在两种不同的结果：一种是用户占用过多的资源， 另一种是用户占用的资源不能满足其合理的要求。从供求关系的角度，当 前i p 网络中服务质量方面存在的问题基本属于上述两种非平衡条件下所 产生的问题。 因此，根据网络中服务资源的不精确性，针对用户的q o s 需求我们首 先提出资源供需平衡的概念。并且在供需平衡概念的基础上讨论用户对资 源需求的统表达式。然后利用供需平衡的概念以及用户对资源需求的统 一表达式作为研究q o s 的工具，对传统的质量路由算法、流量整形问题进 行讨论。基于供需平衡的思想，在核心无状态服务模型下讨论端到端的时 延保证和公平带宽分配问题。 ! ! 塞奎望查堂堡主兰竺堡塞 苎王旦芝至查箜竖旦丝里! ! 竺堕竺塞 1 2 本论文的主要工作和创新性 本文的工作属于国家自然科学基金项目( 基于i p v 6 动态服务质量理论 及其应用的研究，项目编号：6 0 2 7 2 叭2 ) 研究内容的一部分。是在课题负 责人胡九川博士的研究内容方面的扩展。是在胡博士提出的“资源供需平 衡理论”【8 - 1 1 方面的具体算法研究。 从用户需求和资源供给之间存在的矛盾出发，提出了资源供需平衡概 念。并在供需平衡概念的基础上对当前网络服务质量的热点问题进行了探 讨。理论分析和仿真实验结果证明，供需平衡的思想以及提出的相应的理 论体系对解决网络服务质量问题提供了新的思路和解决方法。本文的主要 工作及贡献如下： 1 ) 提出了基于供需平衡的用户需求表达式 基于用户需求与网络服务资源供给之间的矛盾关系，提出了基于供需 平衡的用户需求表达式。该表达式可以很好地描述用户对网络资源需求的 动态特征。同时根据该表达式，可以确定用户对服务质量的需求水平。为 了将用户需求表达式用网络中的具体策略和机制予以实现，我们将传统的 令牌桶改造为支持动态服务质量的动态令牌桶模型，成为我们在网络系统 中实现基于资源供需平衡的服务质量的工具。理论分析证明。基于供需平 衡的令牌桶算法在实现上简单，并且可与传统的令牌桶兼容。通过令牌桶 与路由器的结合可以为用户提供相应的服务质量，不需要在路由器中进行 复杂的排队调度算法，也不需要改变端系统的拥塞控制机制。 北京交通大学硕士学位论文基于用户需求的i p 网络o o s 算法研究 2 ) 提出一种满足用户动态服务质量需求的无状态服务模式 基于区分服务模型和s c o r e 模型的基本思想，提出一种满足用户动 态服务质量需求的无状态服务模式。边界路由器维持每流状态信息，对数 据流进行整形、速率估计和标记，而核心路由器不需要维持每流状态信息， 只需要根据数据包头中携带的流状态信息进行转发服务。该服务模式对路 由器性能要求不高，整个服务模式具有较强的可扩展性和鲁棒性。 3 ) 提出两种基于供需平衡的q o s 路由算法 基于供需平衡服务质量的思想，实现了对传统的路由协议( 链路状态 路由协议和源路由协议) 的改造，成为既能够满足用户q o s 要求，又能与 传统的路由协议相兼容的路由算法。使得服务质量路由的计算和实现更加 简单。仿真实验表明，基于供需平衡的质量路由算法可以实现资源供给和 用户需求平衡的同时平衡网络负载。 4 ) 提出了端到端时延保证的平衡速率虚时钟调度算法 由于在s c o r e 模型中为用户提供端到端服务质量保证的核心抖动虚 时钟( c o r ej i t t e r n u a lv 1 0 c k ，c c ) 调度算法资源的利用率不高，并且 短期内不能保证数据流的吞吐量，因此在速率保证调度算法的基础上提出 了基于供需平衡的端到端时延保证的平衡速率虚时钟( b a l a n c er a t e c l o c k ，b r c ) 调度算法。理论分析证明，该调度算法可以提供与集成服务相 当的端到端时延保证，同时提高资源的利用率。 北京交通大学硕士学位论文 基于用户需求的i p 网络q o s 算法研究 5 ) 提出了一种保证用户需求的比例带宽分配算法 分析了s c o r e 模型中最大最小公平带宽分配算法。由于最大最小公 平带宽分配实际上是一种不考虑用户实际需求的资源分配算法，因此本文 根据用户的需求提出一种新的比例带宽分配算法( p b a s c o r e ) 。仿真实 验表明，该算法可以保证各用户对资源需求的同时很好地限制非友好流对 资源过度侵占问题，保证资源分配的公平性。 1 3 论文的主要结构和内容 本文的其余部分可以分为六章。 第二章首先给出了q o s 的定义，并综述了提供服务质量的三种服务模 式。重点讨论了近年提出的一种新的服务模式一核心无状态网络服务模式。 分析了该服务模式的的优点和存在的问题。另外，还比较了当前网络中为 实现服务质量而提出的各种排队调度算法的优缺点，最后分析了寻找满足 用户服务质量需求的q o s 路由算法。 第三章，根据当前研究q o s 保证存在的普遍性问题而提出了基于资源 供需平衡的用户需求表达方式，并根据供需平衡的思想，基于核心无状态 服务模式提出了一种新的服务模式一供需平衡的核心无状态网络服务模 式。然后对该服务模式的机制以及涉及的思路进行了详细论述。分析了基 于供需平衡的用户需求模式和令牌桶整流模型之间的关系。提出了供需平 衡的动态令牌桶流量整形模型。 第四章，基于3 1 提出的用户需求表达式，将传统的不提供服务质量 的路由协议改造成为q o s r 。即提出了基于服务资源供需平衡的q o s 源路 由算法、基于服务资源供需平衡的距离向量协议的q o s 路由算法、基于服 1 0 北京交通大学硕士学位论文 基于用户需求的m 网络o o s 算法研究 务资源供需平衡链路状态q o s 路由算法。通过仿真实验证明，基于供需平 衡的q o s r 不仅满足户需求，同时平衡了网络负载。具有良好的可扩展性。 第五章，首先分析了核心无状态抖动虚时钟c c 的实现机制以及存 在的问题，然后描述速率保证时钟算法。最后基于3 3 提出的供需平衡的 核心无状态网络服务模式，提出了一种新的基于供需平衡的虚时钟调度算 法一平衡速率时钟调度算法。通过分析证明，该算法可以为数据流提供端 到端时延保证的同时维持i p 网络的可扩展性和鲁棒性。 第六章，首先分析了在核心无状态服务模型中保证资源公平分配的最 大最小公平带宽分配算法一核心无状态公平队列c s f q 的实现机制和存在 的问题。然后提出了基于用户需求的比例带宽分配算法。并对该算法进行 了仿真验证和分析。 第七章，对全文进行总结并对今后的研究工作进行展望。 北京交通大学硕士学位论文 基于用户需求的i p 网络0 0 s 算法研究 第一章 第二章 第三章 第三童 第三章l 供需平衡服务模式l 一j 匿言星耋需求的服务质量ib 釜蓑蓑霎磊霎端到端ii 萋曩磊塞军萎嚣募配算l 第四章第六章 j l 结论与展望 l 第七章 1 2 8一。一。一 北京交通大学硕士学位论文 基于用户需求的i p 网络q o s 算法研究 第二章i pq o s 研究进展 有关在i p 网络中为多媒体流提供服务质量保证的研究早就展开。讨论 的主要热点集中在：i p 网络体系结构的改进、路由器排队调度算法的研究， 即网络资源的管理和分配、q o sr o u t i n g 算法的研究、端系统的拥塞控制机 制等方面。其中最基本的是涉及网络体系结构的改进问题。传统的i p 网络 不提供服务质量保证，但是具有良好的可扩展性和鲁棒性。因此改进的网 络体系结构不仅要能为多媒体流提供服务质量保证的同时，还需要保持传 统i p 网络的优点。这就成为研究服务质量的重点，同时也是难点。 传统的路由器采用先到先服务的机制，因此不能满足实时流要求，因 此大量的文献对路由器的排队调度算法进行了研究。但是，虽然复杂的排 队调度算法可以实现良好的服务质量，然而对路由器性能要求较高，在实 际中不易实现。反之，路由器提供的服务质量又相对较差。怎样在算法的 复杂性与服务质量之间进行折中还是一个开放的问题。 为多媒体流寻找一条满足带宽和延迟的q o s r 也是服务质量研究的热 点。但是由于网络中资源信息的瞬时性，使得路由器获得网络状态信息是 不精确的，过时的【1 ，在这种状态信息下获得的质量路由存在不稳定性， 并不能保证为数据流提供端到端的服务。使得大量的q o s r 算法成为一种 理想化的算法。同时n p c o m p l e t e 也是困扰服务质量路由的另一个问题。 本章主要综述i p 网络中q o s 保证的服务模式、队列调度算法、服务 质量路由等q o s 热点问题。分析它们各自在提供服务质量保证方面突出的 特点、存在的问题以及今后的研究方向。 北京交通大学硕士学位论文 基于用户需求的i p 网络o o s 算法研究 l 服务质量的定义及其度量 服务质量，是指发送和接收信息的用户之间以及用户与传输信息的网 络之间关于信息传输的质量约定 1 2 】。该约定可以理解为服务提供者与用 户之间的一种服务契约，即服务提供者承担支持给定的服务质量，当且仅 当用户按照预定的信息流特征产生数据。r f c 2 3 8 6 【1 3 】中描述为：q o s 是网 络在传输数据流时要求满足的一系列服务请求，具体可以量化为带宽、延 迟、延迟抖动、丢包率、吞吐量等性能指标。因此服务质量包括用户的需 求和网络资源供给两方面 1 4 】，是用户与服务提供者两方面的对立与统一。 用户与网络之间的这种关系为我们在第三章提出供需平衡的概念提供了依 据。 在一般的q o s 服务模型中，把延迟、抖动、丢包和带宽作为服务质量 的评价指标。但是针对网络中不同的应用，对指标的侧重点不同。 延迟是指数据包从源端到目的端经历的时间长度，分为固定部分和可 变部分。固定部分主要是指传输时延和转发时延。可变部分包括数据包在 路由器中的处理和排队延迟。传输延迟主要由源节点和目的节点之间的距 离决定。转发时延取决于网络节点的处理能力和数据包处理的复杂度，路 由器采用的复杂的队列调度算法也可能导致延迟的明显增加，排队延迟则 与网络负载、流量突发性和队列调度算法相关，采用复杂的调度算法可能 减少排队时延，但是由于增加了处理器的开销，又可能会导致转发时延的 增加。因此合适的队列调度算法应该是在算法的复杂度与性能之间取得折 中。 延迟抖动是指端到端的延迟变化特性，它是由于延迟的可变部分的变 化导致的。流量的突发性、不公平的队列调度方法都是可能导致较大的延 迟抖动。按照对延迟和延迟抖动的敏感性，多媒体应用分为两类，即交互 北京交通大学硕士学位论文基于用户需求的i p 网络0 0 s 算法研究 式和非交互式。非交互式对延迟的影响不敏感，仅仅是多媒体节目晚一点 开始而己；对于延迟抖动，只要缓存的长度大于延迟抖动的极值，就可以 避免它的影响。交互式业务则不同，它对于延迟和延迟抖动都严格的要求。 丢包率是指包丢失数占全部传输量的比例。造成丢包的原因包括误码、 路由变化和队列溢出等。随着传输设备性能的提高，误码引起的丢包已经 非常小，路由变化引起的包丢失也仅占很小的比例。由于现在互联网没有 接入控制机制，网络拥塞引起的队列溢出成为包丢失的主要原因。实时多 媒体业务由于不能采取重传的方式补救丢失的数据，因而包丢失对于服务 质量会产生较大影响。 2 2 q o s 的体系结构 现有的i p 网络最初是面向非实时的，单一的数据类型通信而设计的。 i p 协议提供的是一种无连接的网络层传输服务，必须结合其他更高层协议 ( 传输控制协议等) 才能更好地为用户提供端到端的可靠传输服务。但是 这种服务容易受到分组丢失、分组重复、路由器排队调度算法的影响，只 能为用户提供尽力而为的服务( b e s t e 舶r ts e r v i c e s ) 。这种服务实现简单，但 是已经不能满足当今各种网络应用的需要。因此，i e t f 相应地定义了集成 服务模式【1 ，虽然集成服务模型可以为多媒体应用提供比较严格地服务质 量保证，但是存在实现复杂，可扩展性差，鲁棒性不强的缺点 1 5 。鉴于 此，i e t f 又提出了可以为用户提供相对严格服务质量保证的区分服务模式 2 】。虽然具有较强的可扩展性和鲁棒性，但是为数据流提供的是相对严格 的服务质量，并且在各汇聚流之间和汇聚流内部存在资源分配不公平问题 1 6 】。文献【1 7 ，1 8 】在区分服务的基础上提出了核心无状态的网络体系结构。 该网络体系结构实现简单。解决了公平性问的同时可以为用户提供相应的 北京交通大学硕士学位论文 基于用户需求的i p 网络q o s 算法研究 服务质量。以下对这三种服务模式进行简单分析比较。 2 2 1 集成服务模式 集成服务模式由t f 的i n t s e r v 工作组于1 9 9 4 年提出。其目的在于建 立一个能同时提供实时和非实时业务的包交换网络。集成服务借鉴了电话 网交换的经验。在每个实时业务开始之前，由终端设备向网络发出请求， 为它预留必要的网络资源。但是在实现方式上与时分复用不同，集成服务 通过在分组交换中采用实时队列调度，保证实时业务的带宽和延迟。资源 预留协议( r s v p ) 1 9 是集成服务的核心，它通过控制信令为终端和网络 提供预留信息的传输通道。集成服务定义了两种服务类型提供服务质量保 证：质量保证型服务( g u a r a i l t e e dq u a l i t yo f s e r v i c e ) 和可控制负载型服务 ( c o n 订0 1 l e dl o a ds e i c e ) 。 2 2 1 1 集成服务类型 质量保证型服务 i e t fr f c 2 2 1 2 中定义的质量保证型服务要求网络中各元素保证用户 要求的最小延迟时间，从而保证会话过程中每个分组确定的延迟界限，保 证该会话的数据包在规定的时间内到达，只要数据流的传输保持在定的 传输参数范围内，就不会因为队列的溢出而丢弃数据包。为此，提供服务 质量保证型服务的各个元素必须先对各个服务参数所要求的资源进行计 算，并给出这些元素可能带来的最大延迟，具体而言，质量保证型服务具 有以下3 个特点： 1 ) 质量保证型服务要求用户在发起请求时描述其需求，而不是实现这 些需求的机制。这些机制对用户而言是不透明的。 2 ) 质量保证型服务的数据传输路径上的每一个网络元素都必须支持质 1 6 北京交通大学硕士学位论文 基于用户需求的i p 网络o o s 算法研究 量保证型服务，即每个元素都必须提供一个明确的网络延迟。 3 ) 虽然质量保证型服务要求网络系统提供相应的服务，但是不保证所 有的延迟都能完全得到满足。 质量保证型服务的目的在于为某种特定的，实时性要求较高的多媒体 应用提供服务，为了实现它所提供的定量带宽和延迟保证，网络节点必须 采用相当复杂的调度机制保证服务的要求。 在路由器中一般采用加权公平队列( 聃，e i g h t e df a i rq u e u i n g ，w f q ) 【2 0 ，2 1 等调度算法保证用户的q o s 需求。时延以流模型为基础计算，由路 径上的各个路由器共同协调完成，分别计算出在本节点的绝对时延和相对 时延。 可控制负载型服务 i e t fr f c2 2 1 1 中把可控制负载型服务定义为一种端到端的行为。使 用户感到网络是在一种很轻的负载或者具有很大的容量条件下运行，用户 感觉不到明显的延迟或者抖动。它在本质上是一种定性的服务。具体而言： 很高的百分比的分组被成功地转发给接收端，丢失分组的百分比低于一定 许可范围内；绝大部分分组的时延要小于一个可以接收的时延范围； 可控制负载性服务需要指定用户服务指标作为接纳控制处理的关键， 以限制流的数目，从而保证网络处于非重负载的网络模式。为了保证可