（计算机应用技术专业论文）一种基于mpls的服务质量路由改进算法.pdf

华中科技大学硕士学位论文 摘要 近年来，随着多媒体技术_ 摹 1 网络技术的飞速发展，1 日招m e t 上的音频和视频等多媒 体鹰崩瑶出不穷，这些成翔需要网络提供端羁端的0 0 s 控制窝保证。当今的i n t l e t 只能提供尽力而为的服务机制，在流量、延迟和网络带宽管理上功能很弱，不可能真 正解决融前日盏增长的网络q 0 s 要求，发展薪一代的l n 船m t 已经成为一罩串必然的趋 势。 为了解决i n t e m e c 上的q o s 控制和管理问题，i e t f 桐继提啦了几种服务体系模型， 如i n t s e r v 瓜s v p 、d 虹s e r v 和m p l s 等，只有菝赖这些体系结构，才能更好地设计0 0 s 潞 ；| ； 算法，柬支持多媒体应用，并提供q o s 保证。 q o s 路由的目标是寻找条有足够资源又能满足用户q o s 要求的可行路径。然 丙，仪仅根据用户业务的q o s 需球来为箕寻找一条最短路径的q o s 路由策略，有可 能使稽大多数业务流聚集到相闷的路径上，导致网络资源使嗣的不均衡，会造成莱些 链路拥塞的现象。为了解决这个问题，从负载均衡的角度出发，结台m p l s 的约束路 出机制，对带宽与时延约束的q o s 潞出算法进行了新的探索。新的算法在带宽与时延 的约束外，引入节点负荷率的限制，在路由时避歼负载较重的链路，为一部分流燕寻 找一条相对较长但负载较轻的路轻，以使褥整个网络的流量分布更加均衡，从一定程 度上可以减少网络拥塞。从仿真实验结果来看，改进后的算渡在吞l 垃量、请求建立的 成功率以及端到端时延等性能方面有比较好的表现。 关键词：下一代因特网，服务葫量，服务质量模型，服务质量路由，约束路出，多协 议标签交换，流爨工程 华中科技大学硕士学位论文 a b s t r a c t i nr e c e n t y e a r s ，、v i 血t h ed w e l o p m e n to fm u l t i n l e d i at e c l l l l o l o g ya n dn e t w o r k t e o h n o l o g y ，m u n m c d i as e r v i c e ss u c ha sd 塘i t a lv e d i oa n d 醐d i oo v e r 斑l e r n e th a v eb e e n m o r ca n dm o r ci n c 础骆e d ，t h e s en e w a p p l i c a t i o n sr e q u hn e t w o r kl os u p p l ye n d 一- e 1 1 d q o sc o m r 0 1a n dq o s 翱i a r 锄t c e d h o w e v e i m e r n e tc a no n l yp r o v i d e rb e s t e 舶r ts e 阿j c e s t o d 8 y a n di t ，sv e r yw e a kh 1t h em a n a g e m e n to fl f & 衢c ，d e l a ya n db 柚d w 谴m s oi r s i m p o s s i b l et os 0 1 v e 出ep m b l e i nc o m p l e t e l yh o wt os a t i s 黟q o sr e q u l 【i ：l e n t s0 fm e s e 黼w a p p l i c a d o n sw h i c hh a v eb e e ni n c r e a s i n gi n t h el n l e 阳e ta r c h “e c t u r e n o wi tb e c o m e sa o e 精畦n 仃e n dt od e v e l o pt h en e x tg e n e r 鲥o ni n t c r n e t 蒯妣撇 i no r d e rt os o l v em ep m b l e mo f q o sc o n t r o la n dm 8 n 矗g e m e n to v e ri n t e m e t ，i e l th a s p r o p o s e ds u c c e s s h e l y s o m ed i f f 毫r c n ts e r v i c em o d e l sa 1 1 dm e c h 弛i s m ss u c ha s i n t s s v p ，d i 丘s e r va n dm p l sa n ds oo n n o w ，ab e 钍e rq o sr o u t i n ga l g o t h mw h i c h c a ns u p p o r t sm u h i m e d i aa p p l i c a t i o l l sa n dp r o v i d e sq o sg u a r a l l t e e sf 西山e mc a n n o tb e d e s i g n e du n l e s sd e p e n d i n gu p o nt h e s en e wm o d e l s 鲫dn l e c h 腿i s m s t 讯g o a lo f q o sr o u t i n gi st on n daf e a s + b l ep a t h 【h a th a ss u m c i e n tr e s o u r c ea i j dc a n s a l i s 母t ku s e r sq o sr e q u i r e m e n t sh o w e v e lt h eq o sr o u t i n ga l g o r i t h m sw l c ha r eo n l y s u 秘e c tt o ( 扣sf e q l l i r c m e m st h e ns i m p l yf i n das h o r 把s tp 柏m a ym a s sn 狮e f o u st r a 塌ci n t h es a l n e1 址hc a l lm a k et h et r a f f i c1 0 a di nt h en e l w o r ki m b a l a n c e ，t 1 1 e nc o n 窟e 幽o nw i l 】 o c c u ri ns o m el i r 止si no r d e rt 0s 0 1 v em 。p r o b l e m ，b yi i s i n gc o n s t r a i n e d 七船e dr o u n n gi n 毛l l em p l sn e 押。电w cs t u d yt l l ep r 。b k mo fd e l a ) ra n db a | l d w i d mc o n s 乜嘶n e d b 髂e d r o u i i n 昏a i l dp r e s c man e wa l g o r i l mb a s e do ni o a d - b a l a n c i n gf o r t h em p l sn e t w o r k s b y l 砌t i n gt h el o a dr a t eo ft h en o d e si nt h en e t w o r k ，s o m et m 街cw o u l dp a s sa1 0 n g e fb u t l i g h t l yl o a d e dp a t ht 1 a ts 撕s f l e st w oc o n s t 脚m sb a n d w i d t la 1 1 dd e l a 弘b e t 研仙a nt i l e 1 1 e a v i l y1 0 a d e d 曲o r t e s tp a f h hm e a n st h a tt r a 衢cl o a dj nt h en e t w o r kw ；1 1b ea d j u s t e dt oa b a l a n c el e v e la 1 1 dc o n g e s 百o nw o u l db e 删d e df b mac e r t a i ne x t e n t t h es i m u l m i o n 卿l 招 s h o w h 毗t h ep r o p o s e da l g o r i m mh a sag o o dp e r f o 抛a n c ei n 恤0 u g h p u t ，c a l lb l o c k i n gr a t e a n de n d 岫- e n dd e la y k e yw o r d s ：n g i ，q o s ，q o sm o d e l ，q o sm u t i n c o n m a i l l t - b a s e dm u t i n m p l s ，t e h 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果南本人承担。 学位论文作者签名：丑勇智 日期：二。5 年4 月上日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可咀将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口在年解密后适用本授权书。 本论文属于 不保密回。 ( 请在以上方框内打“”) 指导教师签名蝥挟 日期：州年乒月乎日 华中科技大学硕士学位论文 1 绪论 1 1 课题的提出 近年来，随着多媒体技术和嘲络技术的飞速发展，因特网( i n t e r n e t ) 上的音频 和视频业务呈现出爆炸性增长的趋势，i p 电话、视频会议、交互游戏以及远程教育等 新业务层出不穷。这些新兴的网上多媒体业务不仪包括文本数据信息，还包括语音、 图形图像、视频与动画等多媒体信息，它们小但对网络有很高的带宽要求，而且还要 求信息传输的低延迟和低抖动。可以说，当今的分布式多媒体应用不仅增加了网络流 量，同时改变了网上的流量性质。这些应用对网络提了不同于以往数据应用的服务 质量( 。u a l i t yo fs e r v i c e ，q o s ) 要求，需要提供端到端的q o s 控制和保证。 当今的因特网提供的是一种“尽力而为”服务( b e s te f f o r ts e r v i c e ，b e s ) 和 公半共享的资源分配机制，采用先束先服务( f i r s tc o m ef i r s ts e r v e r 。f c f s ) 的公 平排队路由机制进行分组调度，在网络发生棚塞时，会产生较大延迟或随机丢包，小 提供任何服务质量保证，这种机制不可能真正觯决目前日益增长的网络0 0 s 要求，因 此必须发展新一代的幽特网川。 下一代因特网( n e x tg e n e r a t i o ni n t e r n e t ，n g ) 的研究议题是由美国计算机学 会在1 9 9 7 年5 月提出的。研究议题包括六个主题：1 应用；2 中间件：3 服务质量： 4 流量工程；5 安全；6 体系结构。n g i 的实质”j 是通过些革命性的技术发展，解 决目前互联网在管理、安全、服务质量以及规模和性能可扩展性方面存在的问题。 n g i 要求能承载各种q o s 保证的业务、采用开放的体系结构、刚络结构灵活并易 于扩充，能够适应业务的不断变化，实现业务管理的自动化、灵活化和可扩展化，实 现业务管理的服务质量保障日】。 0 0 s 研究的目的是为用户提供有效的端到端的服务质量控制或保证i 4 l 。要在一个 网络中为各种业务( 包括数据、多媒体和实时业务等) 提供可靠的端到端服务质量保证 需要以下三个部分来支持： l 冶b 够支持0 0 s 的各类网络元件，如路由器、以太网交换机等。这些删络元件的 作用是对报文进行分类，并对不同类别的报文提供不同的处理：提供队列管理和调度 华中科技大学硕士学位论文 功能柬满足不同应用所要求的不同的q o s ；提供流量监管和流量整形，限制和调整报 文输入、输出的速度：提供许可控制来确定是否允许用户数据流使用网络资源。 2 信令技术，用来协调端到端之间的网络元素为报文提供q o s 。 3 q o s 控制和管理机制。 在现阶段，q o s 的研究主要集中在两个方面：一是q u s 控制，目前需要解决的主 要问题是算法复杂性和0 0 s 控制效果之问的权衡；二是多种技术的结合，即研究各层 ( 应用层、传输层、网络层链路层、物理层) 、各面( 数据平面、控制平面和管理平 面) 之间的交互作用，将备种q o s 机制综合起来，改善i p 网的服务质量。 目前，o o s 问题已经成为国际网络研究领域最重要、最富有魅力的核心研究领域 之一，是目前计算机网络中研究j _ j 开发的热点问题。国际上不同组织和团体先后提出 了小同的q o s 控制策略和机制，迄今为止，q o s 研究已有不少成果。但是，当前的解决 方案都在不同的方面存在许多不完善的地方，主要存在以下问题【4 1 ： 1 网络系统状态和链路带宽容量变化的不确定性，使得传输通路的端到端带宽预 留缺乏有效的保证。 2 q o s 选路、资源预留和信息传输调度算法的复杂性，还不能适应高速信息传输 处理时间的要求。 3 o o s 要求所导致的资源利用的无效性导致不能充分利用网络资源提高网络的吞 吐量。 4 ，0 0 s 控制方案基本上是静态方案，缺乏有效的动态控制方案来捕捉网络拓扑结 构的变化。 5 一些基本研究成果主要存在于理论中，没有形成专利技术和成熟的技术产品。 因此，q o s 问题在当前也是一个开放性的问题。随着人们对网络q o s 研究的不断 深入，许多新的技术与标准层出不穷，与此同时，一些原有的控制方案与措施也不可 避免地呈现出不足与值得改进的地方。因此，根据业务的需求，结合网络的实际情况， 不断融合新技术，对服务质最保证的相关问题进行研究具有重要的意义。 本文的研究焦点在于，结合当前的q o s 控制技术和q o s 网络模型的路由机制， 研究现有的q o s 约束路由算法，探索在q o s 网络模型下的带宽与时延约束的路由策 略问题。 华中科技大学硕士学位论丈 1 2 国内外研究现状 12 1 有q o s 保证的网络模型研究现状 i p 新业务的不断出现，对i n t e r n e t 业务管理提出了新的要求。由于i n t e r n e t 设计 时没有关注q o s 挎青稠镑理技零，尽力丽为型服务无法给传输提供好的殷务质量保证， 所以必须改变现有网络的体系结构。随羞b i s d n 以及a t m 交换网的出现，人们开始系 统地剐q o s 管理和控制进行较为深入的研究，。些实验性系统也应运而生，代表性的 有英国兰歼斯特火学的q 。sa 工程、美国哥伦比豫大学的女。展集成纯参考模型( x 蹦) 系统、国际合作项目7 l l n a c 等等，这些工作为后来i p 网络中的0 0 s 问题研究葜定了基 础。 因特网工程工作组i e 盯( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 相继提出了多种 服务模型来满足对q o s 的需求，其中比较典型的有：综合服务模型( i n t s e r v ) 、区分服 务模型( d i f f s e r v ) 、m p l s 模型( m u l t i p r o t o c 0 1l a b e ls w i t c h i n g ) 等。目前i e l 下 的这些技术可以作为基科；0 0 s 技术在相关豹阏络部件上使用，但是它的这些成果没有 解决全网的q o s 问题缺乏一个可以实施的整网o o s 机制。有关高速网络的研究开发 在近儿年进展得异常迅速，q o s 问题的研究已经有了一些基本成果，这些成果大量地 反映在i e e ei n f o c 0 m 每年的会议论文集和h e m e t 的l e j 下r f c 标准革集中，这些技术 还处于初步框架制订阶段，在具体的实施技术规藏上还没有显著的成果1 5j 。目藏攫多 标准化组织包括i n t e r n e t 2 、m s f 、i t u 等组织目前都在大力研究和制订i p 嘲整网q o s 机 制，而美国有线电视工业的标准组绣c a b l e l a b 也在为c 曲1 e 运营商研究制订q 隅机制， 3 g p p 剥为下一代无线核心网络研究制订q o s 机制。 将多种模型结合来提供q o s 是解决网络可扩展性问题的一个研究力向 ”。i m s e r v 模型可提供每一个流的q o s 保证能力，但可扩展性麓。d i 勰e r v 模型提供不同服务类别 之闻的区别处理，可扩展性很好，但不关心单个微沆，难以在每个微流的基础上提供 q o s 保证能力。为厂i _ j 时具备每个流的处理能力和好的可打展性，建议采用一种混合 网络模型j 。在嗣络边缘位置，微流数量较少，可扩展性要求较低，对每个流进行处 理，采用i n l s e r v 网络；在网络核心位置，漉数量较大，高速数据传输是最重要的要求， 使用聚合流处理，采用d i f r s e r v 网络。这种混合模型目前在研究上仍不完善，要真正 华中科技大学硕士学位论文 晟初的q 。s 路由算法只是需要找到一条能够满足如带宽、时延等q o s 要求的路径， 但足当网络承载的业务较重时，因网络资源的匮乏或网络业务的不均衡分布，会导致 网络拥塞的出现。约束路由( c o n s t r a i n t b a s e dr o u t i n g c b r ) 的提出就是对最初 o o s 路由的延伸和扩展，它选择路出不仅仅考虑到业务的q a s 要求，而且以提高网络 利用率为日标，即网络必须同时考虑到链路上的其他限制条件如资源利用率等，并将 作为路径代价。其结果是，网络可能会选择一条负载较轻但较长的路由，而不是一 条较短但负载较重的路由。这样网络的业务分布将更加均匀，也是实簏流量j 二程的一 个途径。 一个约束路由方案最重要的组成部分包括链路状态信息广播、约束条件选择和路 由算法。多个度量条件约束的模型往往能更精确地反映一个网络。然而，在q o s 路由 中，由于对资源的需求经常是多样的而且是依赖于应用的，这就使得求取满足多约束 解的问题更加复杂。研究表明，寻找一条满足两个或者多个独立的q o s 约束条件的路 径问题属于n p 完全问题叭”】。也就是说，还不存在有效的( 多项式阶) 算法能完全找 到这样的可行路径并同时满足这些约束。这个问题一直是q o s 路由问题研究中的难点。 近年来，多学科交叉的趋势正在增强，许多学者根据遗传算法、运筹学及最优化 理论，提出了多种智能优化算法，如遗传算法盼1 ”、模拟退火算法等等，来解决多 约束q o s 路由的n p 完全问题。这些方法能比较成功地用丁通信网络拓扑结构的优化， 但是，这些算法的提出与研究尚处存起步和探索阶段，还存在相当多的问题亟待进 步研究“。 有关q o s 路由的研究在近年来取得了较大的进展，但也存在着如下一些尚待解决 的问题吡18 j ： 1 路由信息的非精确性问题 路由选择的基本任务是收集状态信息并更新，为了要获得精确的网络状态信息， 理想的状态更新策略是网络中状态一旦改变，马上触发状态更新，把新的状态信息发 布到网络中的其它位置。在高度动念或规模较大的网络中，将导致巨大的协议通信开 销，显然是不现实的。传统q o s 路由算法的出发点都假定节点获知的路由信息是精确 的，由此引起的非精确性，必然会列路由算法的性能和有效性带来不良影响。因此， 研究非精确路由状态信息下的q o s 路由算法具有十分重要的意义和价值。 华中科技大学硕士学位论文 数。通常用日j 度量的业务有效性、延迟、可变延迟、吞吐量和丢包率等参数来描述( 2 4 】。 针避具体的q 。s 性能参数，结台当前网络中业务跏s 的震求表征，对影响业务服务质 量的主要凶素分析如下： 1 丢包率：是指i p 包在网络结点之问传输时壬失的i p 包数与己发送的i p 包总数 的比值。当网络拥塞、传输损伤、超过生存周麓 丌l ) 时，丢包就可能发生。其形 成原因有两点：一是物理传输过程中的误码，这种情况发生的概率极低；另一个是传 统q o s 技术不能保障业务带宽造成的，而且越是当网络流量拥塞时，影响更为强烈， 其发生概率瞧就越大。 2 时延：是指i p 包从网络入口点到选出口点所需要的传输时m 问隔。造成网络延 迟的主要因素有传输延邂、链路速度延迟、交换和路由延迟、排队延迟以及跳数。目 前控制时簸的主要方法之一是减少数据包传送所经过的跳数。 3 可变时延：即抖动( j i t t c r ) ，通常是指在一段测最时间间隔内，最大i p 包传 输时延的差值。其形成原因主要是由于i p 网络路由状态频繁变化，使得备数据包分 别经由不同物理路由到达，产生时间差异，或者因为网络节点流量超忙，数据包在各 节点缓存时间过氏，使得到达速率变化较大。它会对语音、视频流等实时业务造成较 大影响。严重时甚覃会造成业务质量无法接受。 4 业务带宽：对于未柬核心网络中的承载业务两言，其对带宽的需求分为两类口5 j ： 一娄咀背景类业务为代袭，对总体时延和抖动等宴时指标并不敏感，只关心在单位列 间内能否将数据送选接收方，其体现在带宽需求上就是平均带宽；另一类以交互式业 务为代表，对抖动等实时指标敏感，强调尽可能保障其最大带宽需求。 针对不同数据业务，将满足用户需求的最小带宽称为该业务的等效带宽需求。由 于数据业务多种多样，在计算其等效带宽需求时应考虑对不同业务的通用性和可扩展 性。县体而苦，则是针对不同业务时延容忍程度和蓖要级剐对最小带宽需求进行调节， 透过调节系数。实现。美等魏带宽可阻由| 丛f 数学表达公式来估算： b 阡；教= ? w 平均+ o ( t h 晕 t h 平均) 其中，b w # 为业务的等效带宽，t h 十目为业务要求的平均吞吐量，t h 为业 务要求的塌大吞吐量，毋为与业务时延和重要级别相关的参数，由运营商确定，取值 华中科技大学硕士学位论文 23q o s 控制技术 耍对用户业务提供q o s 保汪，必额依靠良好的q o s 控制和管理机制。为了支持端 到端的网络q o s ，必须对用户的传输实旋接纳控制；剥其信源实施业务整形( t r a f f jc s h a p i n g ) ；同时要对数据流的特性进行监控( m o n i t o r ) ，以保证其不超过播磷的范嗣。 多媒体信息传输与管理的0 0 s 控制技术是当前计算机网络中研究与开发的热点问 题。q o s 控制技术涉及到网络的各个方丽，综合各种文献和资料，将几种常见的q o s 控 制策略与搜术综合擐讨如下； 2 3 + 接纳控制 接纳控制( a d m i s s i o nc o 蚰r 0 1 ) 负责管理q 。s 合同，它根据系统拥有的可用资源 柬决定接受或拒绝用户的中请。如果接受申请，则对接受的用户分配相应的资源，随 后进行业务整彤，同时进行监控。q o s 的传输连接要求在新用户进行传输前先进行接 纳控制，即在用户入网时将其传输特性和参数以及其所需求的服务质量卷知刚络，剃 络再根据现存资源的情况，同j = i 户协商决定是否予以接纳，并建立一个新的q 0 s 传输 连接。 提供鼹络资源来滏足实时应用的0 0 s 保障是未寒多簸务蹰中的关键，这种隧络 资源提供必须通过接纳控制算法来实现。接纳拧制通过限制业务流的数月来满足实时 应用所请求豹q o s 参数。接纳控制算法的设计对网络件能有直接的影响，好的接纳 控制算法瘦该有赢的弼络资源利用率，即在阚络资源充分刚不拯绝新的业务流，嗣辩 接入新的流后又不违背已接入流的q o s 要求。 簇纳控制应综合考虑当前的网络资源状态和请求流的资源需求，判定当前可用的 网络巍源能甭满足薪请求洗的q 。s 需求来侔出接纳决策。目前接纳控制算法一般分 为两种：基于参数的控制接纳算法和基于测量的控制接纳算法。基于参数的接纳拄制 算法是一种传统的0 0 s 接纳控制算法，利用数据源的先验特征，计算出在最坏情况 下所有己接纳流所占掰的列络资源，然后作 h 接纳判定。基下测鬟的控制接纳算法是 根据对实际达到的流量测量碗做出接纳决策| _ 2 6 】。 舞实现一个0 0 s 接纳控制，需要考虑三个方面的因素： 华中科技大学硕士学位论文 1 要求用户捋述的s 参数：在目前的网络q o s 研究中，要求用户提供的有关q o s 属性参数主要包括【4 】： ( 1 ) 峰值分组速率( p e a kp a c k e tr a t e ) ：指传输的最大瞬间速率，可以用相邻分 组的最短抟输时间间隔的倒数来表示。 ( 2 ) 平均分组速率( s u s t a i n e dp a c k e tr 8 t e ) ：捐一段时间内分组传翰的平均速率。 ( 3 ) 分组丢失率( p a c k e tl m sr a t e ) ：指在传输中丢失分组数目占发送分组总数目 的比率。 ( 4 ) 分组传输时延( p a c k e tt r a n s f e rd e l a y ) ：指分缀从信源发出至到达目的节点 的时间，它由传播时延、排队时延、交换时延等组成。 ( 5 ) 分组时延变化量( p a c k e td e l a yv a r i a t i o n ) ：指分组在传输过程中的时延变化 量。此参数变化撼太，意味藿要传输延迟敏感的数据赝需要的缓冲医就越大。 2 接纳判据：是指网络在划断并决定是否接受个新的连接时的依据。分组传输 速率、时延和分组丢失率是号个最常用的接纳判据。 3 + 列络性能与传输参数之闻的关系：在实时或多媒体网络的接纳控制中，各种传 输参数与网络性能之间的关系较为重要。一些定性的关系和影响已经给出，但是如何 给出定量的数学描述来表明它们之问的关系仍然面临挑披，尤其是在多个异种传输流 被多路复用的情况下更是一个难题。 2 ，3 2 业务整形和监控 在多媒 奉网终中，业务常常是惑度突发的，其传输流的传输速率变化较夫，这时 q o s 网络系统就有必要对分组到达的流速进行整彤，从而达剑避免分组在网络中的突 发性传输，确保网络日o s 性能的目的。 目前最常躁的信源整形和带宽簸控技术是漏桶( l e a 晒b u c k e t ) 算法，此算法霹 将突发的信源流转化为平缓传输流，井确保用户的传输滤遵守用户在建立连接时的传 输要求。 漏撬算法静基本思想是：任何分组进入两络，定要从令牌池( 漏桶) 中获取 张令牌，如果令牌池为空，则该分组将丢弃。令牌由网络平均接纳速率r 产生，令牌 池最多可存放p 个令牌( p 即漏桶的大小) ，令牌池满时，新产生的令牌将被薹弃。在 华中科技大学硕士学位论文 漏桶算法限定的信源模型中，传输限制雨数b ( t ) = p 十r t ，这就规定了一种模式，即允 许一个信源在任意短的时间间隔内发送p 个分组的突发信息，但在长时间间隔范围内， 信源被限定以平均速率r 来发送。一种改进的方法是在分组到达漏桶前增加一个缓冲 区。如图2 1 所示。这样，当令牌池为空时，只要缓冲医未满，分组就可以缓存在缓 冲器巾而不被丢失。带缓冲器的漏桶算法也有一些缺点。例如，即使网络负载很低时， 漏桶算法对违约分组仍然采用丢弃或者放入缓冲区的方法，由于算法的限制，减缓了 传输流速，造成网络资源的浪费。采用标记法可以对此加以改善田j ：当分组到达而令 牌池为空或缓冲区己满时，就将该分组打上一个标记，蜕明是违约分组，然后接纳它 进入网络：如果在网络某处遇到拥塞，则丢弃；若一直没有遇到拥塞，则可到达同的 结点。这也是目i i i p 网络所采用的区分服务的基本思路。 图2 4 带缓冲器的漏桶算法 监控是指为了保证流特性在规定范围内而进行的控制。它与业务整形配合使用， 用于管理不符合协商要求的流。如果检测到流有违规的迹象，就利用平滑算法将多余 的部分“平滑”掉。这种方式有时会丢弃数据包，但是如果没有监控措施，某些流会 钻缺乏监视的空子，使得其他遵循规矩的流反而得小到应有的服务等级保证。 2 3 3q o s 调度算法 q o s 调度算法的基本功能是：从结点的每一个输出链路中挑选出在下一个有效周 期发送的分组。q 。s 传输调度控制要基于几个原则，如带宽保证、流的隔离、时延保 证和公平选择等。算法的复杂性要适应网络高速传输和便于实现，使其具有可扩展性 和鲁棒性。 华中科技大学硕士学位论文 目前最主要的调度策略都是近似于广义处理器共享的g p s 口1 ( g e r e r a l i z e d p f ( m e s rs h a r i n g ) 策略。在g p s 中，输出链路在任何小的时间间隔内都在同时为 所有的活动的流服务，且服务的速率与流的预约速率成正比，并且在任何时间间隔内， 任意的两个括动流所得到的归一化服务( 相对服务速率) 相等。 从理论上看，g p s 能保证端到端有限制的时延服务和确保带宽的公平分配。 将n 个连接( 会话) 由n 个t f 实数萌破，九来描述，它们分别反映会话f 在时间 间隔 s t 1 所接收到的服务发送量哦( s ，r ) 。对于在 s l 】期间正在传输的任意两个会话f 和 j ，令c 表示服务速率可以推出会话i 的最小服务速率为 2 掣。刍圮 这表明了g p s 的隔离特性，即每个会话不受其他会话的影响，可以有其最小服 务速率的下界，同时服务速率的下界也确保了会话传输时延的上界。服务共享权既可 用于描述晟小要求的服务速率，又表示了公平共享的比例。f j i 提条件是： 谚( f - s ) c 调度策略是实现网络0 0 s 控制的核心机制之一，近年来一直是一个热门课题。到 目前为止，产生的算法已有几十种，分别有着不同的服务规则、控制目的和复杂度。 g p s 只是一个理想的方案，并不能完全在实际中应用，实际应用中采用近似于g p s 的 调度器。简化近似g p s 策略调度算法实现的复杂件是q o s 调度策略的主要研究方向。 现在已研究的近似g p s 调度的策略有自时钟公平排队( s c 阳，s e l f c l o c k e df a i r q u e u i n g ) 、最坏状况公平加权公平排队( w f 3 0 ，w o r s oc a s e r a i rw e i 曲t e df a i r q u e u i n g ) 和晟小时延自时钟公平排队( m d 0 u e u i n g ) 以及w f 。o 的改进算法w f 2 0 + 等。 s c f q ，m i n i m u md e l a ys e l f c l o c k e df a l r 文献 2 9 将这些分组公平调度算法在一定 约束条件下进行了时延和公平性等对比，并得出结论，m d s c f q 与w f 2 q + 既能保证一 定的时延，又能提供很好的公平性。 华中科技大学硕士学位论文 2 4 本章小结 q o s 控制和管理主要包括信息传输的实时性和信息丢失的管理与控制等问题。在 高速网络中，不同用户可能有不同的服务需求，而不同的业务又需要不同的服务等级， 要保证信息传输的实刚性和不丢失的综合需求是网络传输控制的个重要问题。 本章从介绍q o s 的定义入手，描述了q o s 实现的一般过程；针对具体的q o s 性 能参数，结合当前网络中、i k 务的0 0 s 需求表征，对影响业务q o s 的主要因素进行了 分析；从通信量管理、传输调度等方面对q o s 控制管理技术进行了探讨这些方法和 思路对于网络q o s 控制的理解、设计和实现具有普遍意义。值得指出的是，q o s 路由 策略是o o s 控制的一个重要方面，本章并未提及，将在第四章进行专门讨论。 华中科技大学硕士学位论文 3 下一代因特网q o s 模型及其路良机制 。s 所追求的传输艨量在于：数据分组不仅要能到达其封的端，雨雕要保证分组的 顺序性、完整性和实时性【3 。 。尽力而为型的服务体系已经不能满足日兢增长的q o s 需 求，为了解决i n t e r n e t 上的q 。s 控制和管理问题，i e t f 借鉴q o s 技术，相继提出了 凡释服务体系摸型，如i n t s e r v r s v p 、d i f f s e r v 和m p l s 等，来支持多媒体应用，并 提供q o s 保证。本章将结合国内外学者的相关研究工作，从0 0 s 保证技术与路由机制 角度来探讨这些网络模型。 3 1 综合服务模型 综合服务模型( i n t s e r v ) 是i e t f 在r f c l 6 3 3 中正式提出来的，目标是在i p 网 络中提供端到端严格的q o s 保汪，其所采用的信令协议为资源预留协议( r o s o u r o e r e s e r v a t i o np r o t o c 0 1 ，r s v p ) 。i n t s e iv 的操作都是建立在流( 微流) 概念上的，流 是指属于同一个麻用业务丽具有相同源地址，目的地址和挤议端口号的数据分蛆。 r s v p 本身不是一个路南选择协议，而是用来沿着所选定的路由预留资源的信令 协议。r s v p 的基本功能蹙通过预约和保留传输路径中的资源而发送或保证用户应用的 q o s 。r s v p 对资源的预留是端到端的，可在i p 协议( i p v 4 或i p v 6 ) 上实现，也可在 u d p 协议上实现。它涉及到主机和路由器等网络元素。在主机和路由器中使用r s v p 实 现i n l s e r v 的工作原理如图3 1 所示。 o p 肇 藤小 盐悉堂f l 堡蒌i 数据 l 盐签室fi 型墨l 数a 俦输型一 恃输控制 网3 1 在主机和路由器中使川r s v p 实现i n t s e r v 的工作原理图 华中科技大学硕士学位论文 每一个具有q o s 控制能力的节点都让应用的数据分组通过一个分组分类器以决 定分组的路由和所要求的q o s 级别，然后，把具有相应路由和q o s 级别的分组转交给 分组调度器，并按照所要求的q o s 进行调度转发。在每个节点中，一个r s v p 的q o s 控制要求各分组( 路径分组与预留分组) 都要交给两个决策模块即接纳控制模块和策 略控制模块处理。在r s v p 的控制进程中，除了控制模块与接纳模块之外，还负责转 发路径分组“p a t h ”和预留分组“r e s v ”，并维护和刷新路由器中的软状态表。i n t s e r v 依靠r s v p 提供q o s 协商机制，逐跳( h o p b y h d p ) 地建立或拆除每个数据流的路径 状态和资源预留软状态( s o f ts t a t e ) ；接纳控制决定链路或网络节点是否有足够的 资源满足用户的资源预留请求；依靠传输控制将i p 分组分类成不同的传输流，并根 据每个流的状态对分组的传输实施q o s 路由、传输调度( s c h e d u l i n g ) 等控制。 r f c l 6 3 3 规范中给出了i n t s e r v 整体解决方案的q o s 组件，规定网络中的每个路 由器都需要实现这些组件。如图3 2 所示。所有的路由器在控制路径上处理每个流的 信令信息并维护每个流的路径状态和资源预留状态，并且在数据路径上执行慕于流的 分类、调度和缓冲区管理。 图32 在路由揣上实现的t n 塌e r vq o s 控制组忭 t n t s e r v 能提供三种服务类型：确保服务( g u a r a n t e e ds e r v i c e ，g s ) 、可控负 载服务( c o n t r o l l e d l 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 ) 。g s 确保分组在确定的时间内到达接收端，并且当网络负载过重时，不会被丢 弃。g s 是一种“硬实时”( h a r dr c a 卜t i m e ) 服务，它要求应用指定通信量参数( 如 华中科技大学硕士学位论文 带宽、端到端延迟等) ，常用于需要严格保证无丢失、准确达到的实时传输应用上。 与g s 不同，c l s 是。种“软实时”( s o 广l 卧a | _ t i m e ) 服务。c l s 在小拥挤且负载较轻 的网络中近似于b f s ，它与8 e s 的主要区别在于当网络负载加重时，b e s 流会有很大的 延迟或丢包的日j 能，而c l s 流小会叫显的恶化。c l s 提供的是一个得到保证的持续传输 速率以及偶然出现的突发峰值速率，这两个速率可以沿用令牌桶方法加以描述，它适 合于那些能够容忍一定限度丢失和延迟的应用类型，可以利用简单的f c f s 调度机制与 基于有效带宽的接纳控制来配合实现。 i n t s e r v 是基于流的( 单独的或聚集的) 、状态相关的体系结构，依赖于每个流 ( p e r _ f l o w ) 的状态和针对每个流的管理。这种实现机制+ 方面使i n t s e r v 能够提供 较状态无关的体系结构，具有更高的灵活性和更好的服务级别保证的服务，但同时也 导致了t ll s e r v 的可扩展性问题和鲁棒性问题，其后果是实现复杂，难于应用。 i n t s e r v r s v p 在整个i n t e r n e t 网络应用上存在着如下的根本局限盼3 m ： 1 基于流的r s v p 资源预留、调度处理以及缓冲区管理，有利于提供q o s 保证， 但使系统开销过岛，对于大型网络存在刊扩展性问题。路由器要维护的信息最大，实 现较复杂。 2 目前，只有少量的主机产生r s v p 信令，因而实现上修改程序的阻力较人。 3 许多应用需要某种形式的q o s ，但却无法使用i n t s e r v 模型来表达q o s 请求。 4 必要的策略控制和价格机制目前尚处于发展阶段，无法付诸应用。 冈此，单纯的i n t s e r v r s v p 结构实际上无法被业界接受，在商业上不可能有大 的作为_ 2 8 j 。但是，由于微软公司在其w i n d o w s9 8 ，2 0 0 0 ，n t 5 0 等操作系统中提供了 r s v p 和q o s 功能，现阶段，i n t s e r v 极有可能会应用在企业网边缘、校园网与小型的 公司网络中，这些网络中的用户数据流可以在桌面用户一级进行管理。 3 2 区分服务模型 为了解决i n l r v 中存在的较复杂和扩展性差等问题，i e t f 在r f c 2 4 7 5 中提出了 区分服务模型( d i r f s e r v ) 。d i f f s e r v 的基本思想是“边缘分类，内部转发”，边界结 点根据用户对流的轮廓描述和资源预留信息将进入网络的单流分类、聚合为不同的流 华中科技大学硕士学位论文 聚集，这种聚集信息存储在每个t p 包头的d s ( 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 标记( d i f l l s c r vc o d ep o i n t ，d s c p ) 。内部结点在调度转发i p 包时 根据包头的d s c p 选择提供特定质量的调度转发服务，其特性称为逐跳行为( p e r h 。p b e 1 a v i o r ， p h b ) 。网络边界对甲流作分类聚合和网络内部对聚集流提供特定质量的 调度转发服务，这两个过程是依靠i p 包头内的d s c p 联系起来的。i p 包头的区分服务 标记域( d sf i e l d ) 是d s 区域的边界节点与内部节点阃传递流聚集信息的媒介，是 连接边界的传输分类和调节机制与内部p i b 的桥梁。i p 包头的区分服务标记域格式如 图3 3 所示。 0567 id sf i e l dc u l 图3 3i p 包头的区分服务标记域 d i f f s e r v 定义了区分服务标记域为原i p v 4 包头的t o s 字节或i p v 6 包头的流类型 字节的前6 位，而c u 未存d i f f s e r v 中定义，具有其他用途。d s c p 足区分服务标记域 的具体值，用来标识数据包所属的流聚集，供数据包d s 结点时选择特定的p h b 。d s 结点上d s c p 到p h b 的映射在其体实现l 卜| 必须是可配置的，定义p h b 时，应i j 时指定 对应的d s c p 的推荐值。 在d i f f s e r v 模型中，不要求路由器维护每个流的状态，而是将分组分类为少量 的聚合类，路由器为这些类提供每跳行为p h b 。对进入网络的i p 分组进行分类和标记 以及可能的调整等复杂工作都是由网络的边缘路由器完成的( 如图3 4 所示) ，使得 高性能的核心交换机和路由器能以极高的速度转发分组穿过网络，网络中也不需要维 护每个业务流的信令或状态，从而核心路由器和交换部件只需要很少的改动或者根本 无需改动就能具有良好的扩缩性和可升级性。满足一个特定首部条件的所有分组收到 同样的标汜，而与分组的到达速率无关。如果个端用户为了获得高优先级的服务， 可以和它的i s p 进行协商，但是它要认可分组发送率符合某个流量