（通信与信息系统专业论文）基于ip网络的qos约束组播路由算法研究.pdf

武汉理工大学硕士学位论文 摘要 随着网络技术的飞速发展，当前通信网络带宽和处理能力的提高使网络能 够提供更多的多媒体业务，也使得支持“点到多点”或“多点到多点”的组擢 通信方式成为网络支持多媒体业务的必要形式。组播路由是网络层具备的功能， 组播问题的关键在于组播路由的确定。寻找简单、高效、健壮的组播路由算法 一直是网络界致力研究但未完全解决的问题。另一方面，许多分布式的多媒体 应用对时延、时延抖动、带宽以及包丢失率有不同的要求，这需要当前网络能 够传送具有这些q o s 要求的实时多媒体信息。因此，作为q o s 为中心的网络 体系结构中不可缺少的组成部分，基于i p 网络的q o s 约束组播路由算法的研 究成为网络研究领域的重要内容和热点问题。 本文系统的研究了i pq o s 的体系结构、典型服务模型和机制，并对相关的 关键技术进行了介绍；阐述了i pq o s 组播路由原理；并将现有q o s 约束组播 路由算法的研究成果进行了归纳、分类，其中详细分析了i pq o s 约束的s t e i n e r 树算法；重点介绍了时延约束最小代价组播路由问题及其相关算法。 本文工作重心在于：分析总结了传统遗传算法、禁忌搜索算法和模拟退火 算法各自的优缺点，并在此基础上结合禁忌搜索算法和模拟退火算法各自的优 点，提出了一种改进的混合遗传算法t s s a g m a 。该算法的适应度函数采用模 拟退火算法的思想来确保在后期快速收敛，同时引入禁忌搜索算法的交叉和变 异算子，来防止算法早熟。通过仿真实验表明，t s s a g m a 混合遗传算法在解 决时延约束最小代价组播路由的问题上优于传统算法，能够在较小的代价下搜 索到较好的解。另外，本文还引入了边交换和路径交换的概念，提出了两种改 进模拟退火算法；基于边交换的退火组播路由算法( s a e s m a ) 和基于路径交 换的退火组播路由算法( s a p s m a ) ，并分别对它们的时间复杂度进行了证明。 关键词：q o ss t e i n e r 树组播路由算法时延约束混合遗传算法 禁忌搜索算法模拟退火算法 茎塑型兰查堂堡堂堡堡茎 a b s t r a c t w i t hf a s td e v e l o p m e n to f n e t w o r kt e c h n o l o g i e s ，i n c r e a s eo f n e t w o r kb a n d w i d t h a n dp r o c e s s i n gp o w e rm a k e st h en e t w o r kp r o v i d em o r em u l t i m e d i aa p p l i c a t i o n s ，a n d a l s om a k e st h em u l t i c a s tc o m m u n i c a t i o nt 1 1 a ts u p p o r t s ”o n e t o m a n y ”o r ”m a n y t o m a n y ”b e c o m ean e c e s s a r ym o d eo fm u l t i m e d i as e r v i c e s af u n d a m e n t a l i s s u ei nm u l t i c a s tc o m m u n i c a t i o ni sh o wt od e t e r m i n ea l le f f i c i e n tm u l t i c a s tr o u t i n g ， a n df i n d i n gs i m p l e ，e f f e c t i v ea n dr o b u s tm u l t i c a s t r o u t i n ga l g o r i t h m s t h i s i s u n s o l v e dp r o b l e mi nn e t w o r kf i e l d s i na d d i t i o n ，m a n yd i s t d b u t e dm u l t i m e d i a a p p l i c a t i o n sh a v ev a r i o u sd e m a n d s o nd e l a y , d e l a yv a r i a t i o n ，b a n d w i d t ha n dp a c k e t l o s s ，w h i c hr e q u i r e sc u r r e n tn e t w o r kt ot r a n s m i tm a l d i m em u l t i m e d i ai n f o r m a t i o n w i t ht h e s eq u a l i t y o f - s e r v i c e ( q o s ) c o n s t r a i n t s s o ，, a sa ni n d i s p e n s a b l ec o m p o n e n t i naq o s c e n t f i cn e t w o r ka r c h i t e c t u r e ，r e s e a r c ho nm u l t i c a s tr o u t i n ga l g o r i t h m s b a s e do ni pq o sc o n s t r a i n tb e c o m e sa l li m p o r t a n tp a r ta n dh o t s p o ti s s u eo fn e t w o r k r e s e a r c hf i e l d s t h i sp a p e rr e s e a r c h e st h es t r u c t u r e ，t y p i c a ls e r v i c em o d e la n dm e c h a n i s mo f q o sb a s e do ni pn e t w o r k ，a n di n t r o d u c e st h ek e yt e c h n o l o g ya b o u ti t ；s e t sf o r t ht h e p r i n c i p l eo fm u l t i c a s tr o u t i n gb a s e do ni pq o s ；a n dc l a s s i f i e st h em u l t i c a s tr o u t i n g a l g o r i t h m sw i t hq o sc o n s t r a i n t sw h i c hh a v eb e e np u tf o r w a r d ，e s p e c i a l l ya n a l y z e s s t e i n e rt r e ea l g o r i t h m sw i t hi pq o sc o n s t r a i n t ，e m p h a s i z e st h el e a s tc o s tm u l t i c a s t r o u t i n gw i t hd e l a yc o n s t r a i n tp r o b l e ma n da l g o r i t h m s t h ee m p h a s e so f t h i sp a p e rr e s tw i t h ：a n a l y z s e st h ea d v a n t a g ea n dd i s a d v a n t a g e o ft h et r a d i t i o n a lg e n e t i ca l g o r i t h m ，t u b as e a r c ha l g o r i t h ma n ds t i m u l a t e da n n e a l i n g a l g o r i t h mf r o mc o n v e r g e n c ea n dt h et i m ea n ds p a c ec o m p l e x i t y a n dp r e s e n t sa n i m p r o v e dh y g r i dg e n e t i ca l g o r i t h m ：t s s a g m a ，w h i c hc o m b i n e st h em e r i to f t u b a s e a r c ha l g o r i t h m sa n ds t i m u l a t e da n n e a l i n ga l g o r i t h m s 。t h i sa l g o r i t h me n s u r e s q u i c k c o n v e r g e n c ei nt h el a s tp h a s eb e c a u s ei ta d o p t st h ef i m e s st r a c t i o no fs t i m u l a t e d a n n e a l i n ga l g o r i t h m o nt h eo t h e rh a n d ，b yi n t r o d u c i n gc r o s s o v e ra n dm u t a t i o no f 武汉理工大学硕士学位论文 t u b as e a r c ha l g o r i t h m ，t s s a g m ac a l la v o i dp r e c o c i t ya n dc a l lg e tab e t t e rs o l u t i o n t h es i m u l a t i v er e s u l ti l l u s t r a t e st s s a g m ai sb e t t e rt h a nt r a d i t i o n a la l g o r i t h m si n s o l v i n gt h el e a s tc o s tm u l t i c a s tr o u t i n gp r o b l e mw i t l ld e l a yc o n s t r a i n t i na d d i t i o n b y a n a l y z i n gt h es i m u l a t e da n n e a l i n g a l g o r i t h ma n di m p o r t i n gt h ec o n c e p t i o n o f e d g e s s w i t c h i n ga n dp a t h s s w i t c h i n g ，t h ep a p e rp r e s e n t st w ok i n d so fi m p r o v e d s i m u l a t e da n n e a l i n ga l g o r i t h m s ：s a e s m aa n ds a p s m a ，a n dp r o v e st h er e s p e c t i v e t i m ec o m p l e x i t yo f t h e mi nt h e o r y k e yw o r d ：q o s s t e i n e rt r e em u l t i c a s tr o u t i n ga l g o r i t h m d e l a yc o n s t r a i n th y g r i dg e n e t i ca l g o r i t h m t u b as e a r c ha l g o r x t h ms i m u l a t e da n n e a l i n g a l g o r i t h m 1 i i 武汉理丁_ 人学硕士学位论文 第1 章绪论 1 1 本课题的选题意义 随着网络通信技术的发展以及i n t e r n e t 的普及，网络正以前所未有的速度 发展，网络规模进一步扩大，网络信息流量迅速增加，从而网络将变得更加拥 挤，这将严重影响网络的传输速率。 网络的快速发展要求当前网络既能传送常规的“尽力传输( b e s t - e f r o t - t ) ” 服务( 如：e m a i l ，f t p 等) ，也能传送有一定服务质量( q u a l i t y o f s e r v i c e ，q o s ) 要求的实时多媒体，如视频点播、远程教育、视频音频会议、网络游戏等。这 些网络的实时多媒体业务都依赖于从一个主机向多个主机或者从多个主机向多 个主机发送同一信息的能力，使用传统的点到点通信机制的单播通信方式或广 播方式已无法满足当前网络信息传输的要求，不仅浪费大量的网络带宽，而且 效率很低。组播( m u l t i c a s t ) 正是针对此类问题提出的一种新的、高效的网络 传输方案，与单播相比，组播网络中需要传送的复制信息最少，节省网络资源。 使用i p 组播技术分发信息常常能从本质上减少整个网络带宽的需求。 i p 网络的q o s 已经成为了一个迫切需要关注的问题。实时性的应用要求通 信子网提供传输延迟的均值和方差均可以接受的平滑传输流。但是由于网络业 务的高速增长和明显的突发性特征，虽然网络的物理带宽不断增加，高的平均 传送延迟和不可预估的传输延迟抖动仍严重限制着实时因特网应用的发展。实 时性问题可在一定的程度上由软方法解决，其关键之一是路由算法的优化。 路由( r o u t i n g ) 是计算机网络核心层的主要功能，也是决定网络传输性能 的主要因素之一 2 1 。同时，它也是组播通信的瓶颈，组播的核心问题在于组播 路由。为了准确、有效地将信息送到组播组，必须为它们确定路由，信息按选 择的路由进行传送，选择高效率、低费用的路由是组播通信的关键。因此，作 为组播通信的重要组成部分和亟待解决的关键问题，寻找简单、高效、健壮的 组播路由算法一直是网络界致力研究但未完全解决的问题。 与单播路由不同的是，组播路由的目标是寻找一系列从源节点出发并最终 武汉理工大学硕十学位论文 到达所有目的节点的路径，因此组播路由也比单播路由复杂许多。目前实现组 播通信最有效的一种方式就是构造组播树( m u l t i c a s tt r e e ) 。组播树就是覆盖所 有组播组成员的棵生成树。所以，组播路由算法就是研究如何在网络中建立 一棵组播树。 传统的尽力传输路由只关心网络的平均性能，各种数据流在网络中平等地 分享网络资源且能沿多条路径传输，但是仅有这种特性的路由技术不能满足有 q o s 要求的实时多媒体业务传送的需要口】。因此，q o s 约束的组播路由算法的 研究逐步发展起来。另外，q o s 路由问题成为当今网络通信领域的研究热点的 另个原因可以说是由网络全局状态信息的不精确性引起的，如何利用网络不 精确的信息来选择最优的路径也是很多人对q o s 路由进行研究的原因。分布式 连续媒体应用及基于w e b 的应用对延时、延时抖动、带宽、分组丢失率有不同 的需求，基于q o s 约束的组播路由技术作为以q o s 为中心的网络体系结构中 不可缺少的组成部分，己成为网络研究领域的重要内容和热点问题。 1 2 本文相关研究现状 网络q o s 已经引起了越来越多的研究人员的兴趣，不仅如此，工业界对 q o s 研究进展的关注程度也日益提高，有影响力的网络运行商和网络设备提供 商都提供了一定程度的q o s 支持。而新型的网络应用对q o s 的需求也日益迫 切，这些都使得q o s 正成为研究热点。总体上来说，i pq o s 的研究还没成熟， 还没有成为一个统一的标准。不同的单位或组织提出了自己对i pq o s 的认知及 研究成果。下面便是研究i pq o s 的几个代表机构和模型： i b m 公司的h e i d e l k e gq o s 模型： 美国哥伦比亚大学c o m e t 研究组提出的x r m 模型： 美国宾夕法尼亚大学的0 m e g a 体系结构模型； 加利福尼亚大学伯克利分校的t e n e t 模型； i e t f 工作组提出的集成业务体系机构和区分业务体系机构。 综合服务资源预留( i n t e s e r v r s v p ) 模型在数据传输前首先要通过r s v p 协议建立路径和预约资源，网络节点通过分组调度算法根据时延敏感类业务预 留的带宽确保其时延上限。综合服务模型的优点是能够充分的保障业务的q o s ， 武汉理工大学硕士学位论文 但是它是需要记录和维护每个数据流的状态，当网络节点中存在大量的数据流 时，需要占用较多的资源，因而其扩展性遭到置疑。 区分服务( d i f f s e r v ) 是在网络边界将数据流按照其q o s 要求进行简单分 类，将同种类型的流合并起来进行集束传输，流的按入允许控制在网络中的边 缘节点完成。每一种类型的流在网络内部分别进行处理，分类的工作在网络的 入r 进行，每个分组被标识为一定的服务类型，每种类型的分组都按照各自的 流量控制策略进入网络。网络内部的路由器通过检查分组的服务类型来决定将 分组置入哪一种队列，以及当拥塞发生时如何丢弃分组。区分服务不能保证端 到端的服务质量。 当前对q o s 研究主要集中在以下几个方面：服务模型、队列管理、接入控 翻、资源管理、标记算法、以及t c p 协议研究、路由算法等等。 队列的管理主要涉及到分组调度算法和接入控制，分组调度算法的作用就 是根据一定的规则选择分组输出到输出链路上。分组调度算法决定着分组的输 出次序，因此决定着分组的时延、时延抖动；如果一个连接中的分组在较长时 间内得不到服务，该连接的队列就有可能溢出，所以分组调度算法也影响着分 组丢失率。所以调度算法和接入控制对q o s 至关重要。 对标记算法的在带宽共享的公平性闯题上的研究。有入提出了自适应的公 平标记算法，它采用带宽估计机制，对网络中可使用的带宽进行动态估计，将 所估计的带宽以按比例的方式公平的分配给各个汇聚流，同时将根据数据包标 记结果，对t c p 源端的拥塞窗口进行控制，从而保证对网络带宽利用的公平性。 路由选择算法是网络层软件的一部分，负责确定所收到数据包的输出路径。 在数据包交换网络中，路由器对收到的每个数据包都要重新做路由选择，因为 对每个数据包来说，上次到达的最佳路由可能已经改变了。路由算法必须具有 l f 确性、简单性、健壮性、稳定性、公平性、最佳性。q o s 路由选择算法就是 要在考虑网络拓扑、流的要求、链路资源以及网络管理员设定的策略的情况下 达到高网络吞吐率。 q o s 组播路由的组成部分如图1 1 所示。实现i pq o s 组播路由最普遍的方 法是构造树形路由结构，寻找连接源节点和一组目的节点的一棵树，信息可沿 这棵树决定的路径进行发送。基于树实现组播路由具有以下优点： 信息以并行方式沿树枝发送到组成员，减少了信息传递的延时； 网络中需要传送的复制分组晟少，信息的复制只在树权处进行，可以节 武汉理工大学硕士学位论文 省网络带宽资源，提高组播通信时的资源利用率，减少拥塞，降低网络负载。 理想有效的组播路出算法是发现一棵覆盖所有组播组成员的树，并体现如 f 特征：树随着组成员动态变化更新；节点状态信息量最小化；避免链路和节 点的流量集中：根据服务质量约束和费用函数优化路由。 组播群组 q o s 约束 l ( 如时延、抖动) f 、，!i。、，一 有约束的组播路由 目标函数 ( 如代价) 拓扑结构h 飘司嘛 篇 本地) 一全局 精确信息ll 聚集信息il 概率模型 l 精确信息l 聚集信息 图1 1q o s 组播路由的组成部分 现有的网络传输并不能完全支持q o s 的需求。在r f c l 3 4 9 中给出了数据 报中字段所存储的服务类型信息，i pq o s 只包括了最小时延、最大吞吐量、最 高可靠性和最小费用。开放最短路径优先算法( o s p f ) 具有了选择满足一定业 务质量的路由能力，但是仍然不能完全满足的要求。找到满足多个约束条件的 q o s 路径优化是n p 完全问题 4 1 ，n p 完全问题是当前数学界尚未解决的数学难 题。这就意味着无法在多项式的计算级别上找到最优解。有文献给出了自适应 路由机制的网络模型：有人讨论了基于多约束条件的q o s 路出选择优化问题： 有文献讨论了基于资源优化的q o s 路径选择模糊算法；还有研究人员针对q o s 组播路由问题的复杂性，引入了一些人工智能优化算法寻求最优解。 在组播路由中提供q o s 支持的困难在于： 1 ) 分布式连续媒体应用如视频会议、视频点播、i p 电话及基于w e b 的应 用对延时、延时抖动、带宽、分组丢失率有不同的需求，多个约束使得组播路 由成为n p 完全问题可见q o s 组播路由技术研究的难度。 2 ) 当将一个路由算法结合进组播路由协议时，有许多实际问题需要考虑， 如状态的更新、动态拓扑和成员改变的处理、树的维护以及可扩展性，这些问 题被考虑进后使得协议设计过程更为复杂； 3 ) 必须考虑如何以最小代价收集和维护与q o s 相关的状态，如何在聚集 4 武汉理工大学硕士学位论文 的不精确的状态信息的基础上构造满足q o s 条件的路径，树，如何维护路由域 间的q o s 等。 1 3 论文研究内容和组织结构 1 3 1 论文的研究内容 本论文主要研究i p 网络具有q o s 约束的组播路由算法，系统研究i pq o s 的体系结构、典型服务模型和机制，并对相关的关键技术进行了介绍； 在介绍组播路由技术背景知识的基础上，将现有q o s 约束组播路由算法的 研究成果进行归纳、分类，并总结q o s 组播路由的典型问题及相关经典算法， 其中详细分析i pq o s 约束的s t e i n e r 树算法，重点介绍了时延约束最小代价组 播路由问题及其相关算法，为本文q o s 组播路由算法的研究工作奠定了坚实的 理论基础； 研究具有时延约束的最小代价组播路由问题，对传统遗传算法、禁忌搜索 算法和模拟退火算法各自的优缺点进行了分析总结，在此基础上结合禁忌搜索 算法和模拟退火算法各自的优点，提出了一种改进的混合遗传算法t s s a g m a ， 并对其进行仿真； 分析模拟退火思想，引入边交换和路径交换的概念，提出两种改进退火算 法：基于边交换的退火组播路由算法( s a e s m a ) 和基于路径交换的退火组播 路由算法( s a p s m a ) 。 1 3 2 论文的组织结构 第l 章，讨论i pq o s 约束组播路由技术的发展背景及其研究现状。 第2 章，介绍了i pq o s 体系结构。并详细分析了i pq o s 的典型服务模型 和机制，同时重点讨论了各个典型i pq o s 服务模型的原理及其关键技术。 第3 章，主要讨论组播路由技术的发展背景，对q o s 组播路由的基本概念 及组播通信机制进行了阐述，给出q o s 组播路由的网络模型；并对目前的一些 组播路由算法的研究成果进行归纳、分类和分析，其中详细分析了q o s 约束的 武汉理t 大学硕士学位论文 s t e i n e r 树问题及算法。另外，介绍了几个实际应用中的组播路由协议。 第4 章，分析介绍了时延约束最小代价组播路由的概念和相关的算法。阐 述了遗传算法、禁忌搜索算法、模拟退火算法的优缺点，并在此基础上结合禁 忌搜索算法和模拟退火算法的优点提出了一种时延约束最小代价混合遗传算法 t s s a g m a ，并对其进行了仿真。 第5 章，提出了两种改进的模拟退火算法：基于边交换的退火组播路由算法 ( s a e s m a ) 和基于路径交换的退火组播路由算法( s a p s m a ) 。 第6 章，对全文进行了总结，并对i p q o s 约束组播路由相关阀题进行了展望。 1 3 3 论文的创新之处 首先，本文对现有的i p q o s 约束组播路由问题和相关的算法进行了总结分 类。 然后，在分析总结了传统遗传算法、禁忌搜索算法和模拟退火算法各自的 优缺点的基础上，结合禁忌搜索算法和模拟退火算法各自优点，提出了一种改 进的混合遗传算法t s s a g m a ，t s s a g m a 算法的适应度函数采用退火算法的 思想来确保在后期快速收敛，同时引入禁忌搜索算法的交叉和变异算子，来防 止算法早熟。通过仿真实验表明该混合遗传算法在解决时延约束最小代价组播 路由的问题上优于传统算法，能够在较小的代价下搜索到较好的解。 最后，本文还引入了边交换和路径交换的概念，提出了两种改进退火算法： 基于边交换的退火组播路由算法( s a e s m a ) 和基于路径交换的退火组搔路出 算法( s a p s m a ) 。 6 武汉理t 大学硕士学位论文 第2 章i pq o s 的体系结构 2 1i pq o s 概述 i p 网络即采用i p ( i n t e n a e tp r o t o c 0 1 ) 协议的网络。现在，因特网( i n t e r n e t ) 上 大部分的网络采用该协议。l n l c r n e l 是在a r p a n e t ( 美国国防高级研究计划局网 络) 和n s f n e t 网络互联的基础上发展起来的。a r p a n e t 是在6 0 年代末期发 展的，它是第一个电子的存储转发分组交换网。1 9 6 9 年试验性网络取得成功 后，逐渐发现当时的a r p a n e t 协议不适合在多个网络上运行。这导致了对协 议更深入的，最后产生了t c p i p 模型和协议。t c p i p 协议( 5 - 8 1 是目前最流行的 网际互联协议，它为互联网提供了基本的通信机制。 i n t e m e t 已成为一个重要的和无处不在的商业基础设施，随着互联网的高速 增长，i p 业务也得快速增长和多样化，这大大改变了消费者对网络性能、安全 性和服务的期望。但是“尽力而为”服务仍是目前i n t e m e t 中主要的一种服务 类别，所有分组在网络中被同等对待，任何拥塞链路都会增加分组传输时间， 从而导致性能下降、数据抖动、或者分组丢失，不能保证服务质量。随着分布 式多媒体应用需求的不断增长，以及i n t e r n e t 上商业化应用的飞速发展，对服 务质量( q u a l i t yo f s e r v i c e ，q o s ) 提出了更高的要求一。”，高效的q o s 支持显 得越来越重要。 i pq o s 的研究目标是有效地为用户提供端到端的服务质量控制或保证。 q o s 就是网络单元( 例如：应用程序、主祝或路由器) 能够在一定级别上确保 它的业务流和服务要求得到满足【1 2 】。简单地说，q o s 能够对数据包进行合理的 排队，对含有内容标识的数据包进行优化，并对其中特定的数据包赋以较高的 优先级，从而加速传输的进程。q o s 并没有创造带宽，只是根据应用程序的需 求以及网络状况来管理带宽。q o s 直接表现为l p 数据流通过网络时的性能，它 有一套度量指标，包括业务可用性、时延、时延抖动、吞吐量和丢包率： 业务可用性：用户到互联网业务之间连接的可靠性。 时延( d e l a y ) ：指两个参照点之间发送和接收数据包的时问间隔。 武汉理工大学硕士学位论文 时延抖7 裂3 ( j i u e r ) ：指在同一条路由上发送的一组数据流中数据包之间的 时| 日j 差异。 吞吐量：网络中发送数据包的速率，可用平均速率或峰值速率表示。 丢包率：在网络中传输数据包时丢弃数据包的最高比率。数据包丢失一 般是由网络拥塞引起的。 实现q o s 的一种方法是按照服务水平的要求分配资源给每一个数据流。这 种采用“资源预留”进行带宽分配的方法并不适合“尽力而为”型应用。由于 带宽资源是有限的，q o s 的设计者引入了优先级概念，使得在资源预留后“尽 力而为”服务的数据流的传输也能得到一定的保障。拥塞控制和q o s 路由，资 源预留，构成了q o s 研究体系的基础部分，如图2 1 所示： 嵌入式实时应用q o s ：音频视频应用 流量q o s 协商、声明和检测 堕! 接纳控制 q o s 单组播路由卜叫资源预留 芷塑 拥塞控制i 下“ ! - 一 l 传输协议 链路管理 图21 网络中支持q o s 的研究体系 为了解决i pq o s 问题，i e t f 已经提出了几种的服务模型和机制来满足q o s 需求，其中比较典型的有： 综合服务和资源预留协议i n t s e r v r s v p t l 3 】：以r s v p 信令1 1 4 1 向网络提 出业务流传输规格( f l o w s p e c ) ，并建立和拆除传输路径上的业务流状态。主机 和路由器节点建立和保持业务流状态信息。 区分服务d i t t s e r v ”1 ：在d i f f s e r v 网络中，边界路由根据用户的流规格 ( s t r e a mp r o f i l e ) 将用户流划分为不同的级别，再聚合成流聚集，聚集信息存 放在i p 包头的d s 标记域1 1 6 j ，称为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 提供不同质量的调度转发服务。 多协议标记交换m p l s ( m u l t ip r o t o c o ll a b e ls w i t c h ) | l7 j ；根据分组头 的标记，通过网络路径控制来提供流聚集的带宽管理。 流量工程( t r a f f i ce n g i n e e r i n g ) 1 8 】：将业务流量合理分配在现有的网络 武汉理工大学硕士学位论文 拓扑结构上，以优化网络资源的合理使用。 子网带宽管理s b m ( s u b n e tb a l l d w i d mm a n a g e m e n t ) 19 】：负责o s i 第 二层( 数据链路层) 的分类和优先级排列，同i e e e8 0 2 网络进行共享和交换。 2 2i n t s e r v r s v p 服务模型 2 2 1i n t s e r v 基本概念 为在i p 网上提供q o s ，i e t f 出了一种资源预留及q o s 控制流程的模型( 综 合服务模型) ，这个模型解释了如何在主机和路由器中进行资源预留以及对相关 的q o s 参数进行控制。r f c l 6 3 3 将资源预留协议r s v p 作为i n t s e r v 结构中的 主要信令协议。其基本思想就在于以资源预留的方式来实现q o s 保障，r s v p 是其核心部分。r s v p 是主机用来从应用程序获得特定的q o s 的一种控制协议， 完成综合服务需要定义的呼日q 接纳控制功能和资源预留功能。端点应用程序利 用r s v p 消息向网络提出完成数据传送必须保留的网络资源( 如带宽及缓冲区 大小等) ，同时也确定沿传送路径的各个节点传输处理策略，从而对每个业务流 实现逐个控制。 i n t s e r v 模型对传统i m e m c t 体系结构的扩展主要包括在路由器中保存数据 流状态信息以及明确的状态建立机制。这种模型在路由器中所保存的数据流状 态信息是软状态信息( s o f ts t a t e ) ，由于软状态信息在路由器发生错误时容易通过 r s v p 信令刷新而隐含地拆除并在另外路由嚣中重建数据流状态信息。不象硬 状态信息( h a r ds t a t e ) 需要明确地拆除状态信息，因而保持了网络体系结构的鲁 棒陛( r o b u s t n e s s ) 。 在服务层次上，i n t s e r v r s v p 提供了3 种级别的业务： 1 】端到端质量保证型服务【2 。】( g u a r a n t e e ds e r v i c e ) ：该业务提供时延、带 宽与丢包率的保证。该业务不能控制固定时延( 如传输时延等) ，它所能保证的 是排队时延的大小。 【2 可控负载型服务f 2 1 】( c o n t r o l l e dl o a ds e r v i c e ) ：在负载较轻的网络中这 种业务类似于“尽力而为”业务。在控制负载业务网络中，应用可以假设网络 传输的包差错率近似于下层传输媒质的基本包差错率。包平均传输时延与网络 9 武汉理工大学硕士学位论文 绝对时延差别不大。 【3 】尽力而为服务( b e s t - e f f o r ts e r v i c e ) 类似当前互联网在提供的尽力而 为的服务，该业务不提供任何q o s 保证。 2 2 2i m s e r v r s v p 主要构件 i n t s e r v r s v p 服务模型主要由四个部分构成：信令协议r s v p 、接纳控制 器、分组分类器以及分组调度器。 主机路由器 图2 2 资源预留及q o s 控制流程 从图2 2 可以看出：主机和路由器中最主要的区别在于路由器中有一个路 由模块，这表明，资源预留机制依赖于当前和将来的路由协议。各个模块的功 能如下： ( 1 ) 资源预留协议r s v p ：负责逐点( h o p b y h o p ) 地建立或者拆除每个流 的资源预留软状态( s o f ts t a t e ) ，也即建立或拆除数据传输路径。 ( 2 ) 策略控制( p o l i c i n gc o n t r 0 1 ) ：确定请求预留的应用是否有许可做资源 预留。它需要检查r s v p 包是否满足r s v p 连接请求中的流特性( f l o w s p e c ) 来确定是否禁止该预留行为。同时，它还对每一数据流进行监控，确定它们是 否遵守预留的带宽并采取措施在数据流“违规”时使其重新符合规定。它能提 供对数据流进行平滑控制、拥塞控制等。比较成熟的算法有漏桶( 1 e a k yb u c k e t ) 、 窗口控制( w i n d o wc o n t r 0 1 ) 等。 ( 3 ) 接纳控制( a d m i s s i o nc o n t r 0 1 ) ：也称为容许控制，它确定在端系统和 路由器中是否有足够的本地资源来支持请求预留的带宽。如果没有足够的资源， 则接纳控制将拒绝该预留请求。接纳控制算法的核心，是通过预定的q o s 参数 计算出信道的最大容量。 1 0 武汉理工大学硕士学位论文 ( 4 ) 分组分类器( p a c k e tc l a s s i f i e r ) ：负责确定q o s 的级别，对应用程序送 来的每一个分组进行检查，对属于不同数据流的分组进行分类，并发送到分组 调度器。对于一个新的资源预留请求，在同时通过接纳控制和策略控制后，分 组分类器将确定该数据流的传输优先级参数并在分组调度器上获得所需的 q o s 。i n t s e r v 常用的分组分类器是多域( m u l t i f i e l d ，m f ) 分类器。 ( 5 ) 分组调度器( p a c k e ts c h e d u l e r ) ：按不同数据流事先预留好的资源，根 据不同的策略对各个队列中的数据包来进行调度转发。例如，在路由器中，收 到数据分组后先暂存在缓冲区( b u f f e r ) 中，再按一定算法规定的顺序或优先 级交由c p u 处理。调度器必须保证有足够的缓冲区来缓存数据，也必须保证 c p u 处理分组的能力满足q o s 的要求。调度算法是目前研究较多的算法，主要 包括2 大类：一类是静态的调度算法，如h o l ( h e a do f l i n ep r i o r i t ys c h e d u l i n g ) ： 另一类是基于速率( r a t e b a s e d ) 的调度算法，如虚拟时钟( v i r t u a lc l o c k ) 算 法、公平队列( f a i rq u e u i n g ) 算法等。 在实现层次上，i n t s e r v 需要所有路由器在控制路径上处理每个流的信令消 息并维护每个流的路径状态和资源预留状态，在数据路径上执行流的分类、调 度和缓冲区管理。 r s v p 可以看作是配置业务处理的机制，i n t s e r v 则是在r s v p 信令基础上 够用以提供端到端q o s 保证的体系结构。i n t s e r v 设定网络设备支持业务的处理 机制，保证每一个业务流严格独立于其他业务流的服务，并设定提供特定量化 资源的服务。 2 2 3 资源预留协议r s v p 由r f c 2 2 0 5 定义的资源预留协议( 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 ) 用来向 网络发送信号，告诉它们用户在特定的应用程序下对网络服务的要求，也被路 由器用来向沿发送方到接收方的路径传递q o s 参数，预留并维持提供服务所需 的资源i j j 。r s v p 在i p v 4 或i p v 6 之上工作，在协议栈中处于传输层协议的位置。 和i c m p 、i g m p 以及路由协议一样，r s v p 不负责实际传送应用程序的数据， 并且主要在后台运行。 r s v p 早在1 9 9 3 年就被提出，用于为i p 网提供q o s 能力。1 9 9 7 年初1 e t f 武汉理工大学硕士学位论文 批准r s v p 成为r f c 文件，在i n t s e r v 工作组内进行标准制定工作。r s v p 是 种提供预留设置和控制以实现综合服务合协议，是所有q o s 协议中最复杂 的。 最基本的r s v p 资源预留请求包括流规格说明( t s p e c ) 、资源预留规格说 明( r s p e c ) 和过滤器规格说明( f i l t e rs p e c ) ，它们一起称为“流描述符”( f l o w d e s c r i p t o r ) 。 流规格说明通常包含服务类型和数字参数集合：预留说明定义了所期望的 q o s ：数据流说明描述数据流，预留说明和数据流说明决定于综合服务模型并 且对r s v p 来说是透明的；过滤器规格说明定义了由流规格说明所定义的q o s 的数据包集合( 即数据流f l o w ) 以及设置数据包分类器中的参数。过滤器规格说 明的格式依赖于所使用的网络层协议，即i p v 4 或i p v 6 。 使用r s v p 信令建立数据发送路径以及为数据流预留资源的过程可以分成 薅步：按数据流传输方向以p a t h 消息建立起数据流的传输路径，然后逆向以 r e s v 消息为数据流预留资源。 目前所用的r s v p 中定义的基本过滤器规格说明格式具有严格的形式；发 送端i p 地址和可选的t c p l d p 端口号。在服务保证、资源分配的粒度和对保 证q o s 应用及用户反馈的细节等方面r s v p 都能提供最高级的q o s 。 2 2 4i n t s e r v r s v p 的局限性 从理论上讲i m s e r v r s v p 模型完全可以保证为i p 网络提供q o s 保障。但 随后在一些网上的实验表明这种服务模型有很明显的局限性，i m s e r v r s v p 是 面向流的、与状态相关的服务模型。根据每个流的服务要求实施接入控制，根 据每个流的状态实篪管理，这种实现机制一方面使i n t s e r v r s v p 能够提供更高 的灵活性和更好的多级别服务，但同时也导致了i n t s e r v r s v p 的可扩展性 ( s c a l a b i l i t y ) 问题和鲁棒性( r u b u s t n e s s ) 问题，致使其难以在广域网上实现。 在i n t s e r v r s v p 体系结构中，网络中每个节点都要维护各类数据库并实现 所有复杂的功能模块( 包括资源预留、路由、接入控制等) 。r s v p 信令协议提供 q o s 协商机制，各网络节点建立和维护预留信息，并根据自身资源状况对用户 的预留请求执行接入控制，数据传输时各网络节点监控数据流，并提供相应的 服务，可以看出，几乎任何一项功能都将涉及到所有的网络节点，这种完全分 武汉理工大学硕+ 学位论文 布式的控制造成了极大的复杂性。总而言之，i m s e r v r s v p 在广域网络的应用， 存在如下根本的局限性： 基于流的资源预留、调度处理以及缓冲区管理，有利于提供q o s 保证， 但状态信息与业务流数量的增长成正比，而路由器的存储容量有限，使骨干网 络中系统开销过高，可扩展性差； 对路由器的要求过高，网络中所有的路由器都必须实现r s v p 信令协议、 接入控制程序、分类器以及调度器，这使得路由器的设计复杂性和运行复杂性 都大火提高； 资源预留不适用于短时流，比如w 曲流等，而在因特网中w e b 流量超 过了5 0 。 i n t s e r v r s v p 还存在着资源预留和路由协议之间的矛盾。而且许多应用 需要某种形式的q o s ，但是无法使用i n t s e r v r s v p 模型来表达q o s 请求，尤 其是为现有的应用程序提供i n t s e r v r s v p 服务存在困难。 最初的i n t s e r v r s v p 是面向单流( m i c r o f l o w ) 的，在路由器中配里并且使用 多域分类准则，这给路由器尤其是主干网络核心路由器带来了巨大负担，近期 r s v p 己经开始支持流聚集 2 2 - 2 4 】，即沿数据流传输路径