（系统工程专业论文）分布式QoS路由算法的研究.pdf

沈阳工业大学硕士学位论文 摘要 目前的i n t e m e t 只提供“尽力而为”的服务，这就意味着它只能尽力的转发用户的 数据报，而在带宽和延迟等方面不提供任何保证。虽然这种服务非常适用于传统的应用， 但是对于新出现的实时和多媒体应用却是无法忍受的。在下一代互联网( n e x tg e n e r a t i o n i n t e m e t ，n g i ) 上提供高水平服务质量( q u a l i t yo fs e r v i c e ，q o s ) 保证己经成为目前计算机网 络研究的主要课题。 网络为用户业务提供服务质量保证是源于多方面的，而服务质量路由技术是提供服 务质量保证的关键技术之一。在路由算法的研究中，国内外的学者提出很多具有创造性 和实用价值的q o s 路由算法，这些算法大体可分为：源路由算法和分布式路由算法两大 类。尽管这些算法各有缺陷和局限性，但它们的提出不仅给出了网络路由的优化解决方 案，并且将路由算法的研究不断向前推进。 本文提出并实现了2 种q o s 路由算法：基于多路探测的分布式q o s 路由算法 ( d i s t r i b u t e dq o sr o u t i n ga l g o r i t h mw i t hm u l t i - p a t hp r o b i n g ，m p d q r a ) 和基于多路探测 的分布式并行q o s 路由算法( d i s t r i b u w dp a r a l l e lq o sr o u t i n ga l g o r i t h mw i t hm u l t i - p a t h p r o b i n g ，m p d p q r a ) 。m p d q r a 算法利用分布式路由选择的优点，仅使用相邻节点的 状态信息，利用节点的传输成功率有效减少分布式路由算法在选路过程中所引起的盲目 性，并利用多路选择提高链路建立的成功率。m p d p q r a 算法基于改进的m p d q r a 算 法，它在单一通路不能满足连接请求要求时，寻找多条能联合满足要求的一组并路，并 预留资源共同满足用户的服务质量要求。m p d p q r a 算法可以减少网络处于重负荷时所 产生的“资源碎片”，接纳更多的业务。 本文用n s 2 建立网络仿真场景，采用这两种q o s 路由算法进行仿真试验。通过与 传统算法性能的比较，可以看出这两种算法能平衡网络负载，提高网络资源利用率，具 有较好的性能。它们在网络轻负载情况下，通信开销小。在网络重负载情况下， m p d p q r a 算法使用并行多路增加连接请求的接通率。将这两种算法应用于支持服务质 量保证的多媒体数据网。能充分利用有限的网络资源，提高传输多媒体信息的能力。 关键词：0 0 8 ，多路路由算法，分布式路由，咿完全问题 r e s e a r c ho f d i s t r i b u t e dq o s r o u t i n ga l g o r i t h m c u r r e n ti n t e m e tc a n o n l yp r o v i d e ”b e s t - e f f o r t s e r v i c e , w h i c hm e a n si tw i l lt r yi t sb e s tt o f o r w a r du s g sd a t ap a c k e t s b u tc 锄p r o v i d en og u a r a n t e e s 托g a r d i n gb a n d w i d t ha n dd e l a y l et h i sk i n do fs e r v i c ei ss u i t a b l ef o rs o m et r a d i t i o n a la p p l i c a t i o n s i t si n t o l e r a b l ef o r n e w l ye m e r g e dr e a l - t i m e ，m u l t i m e d i aa p p l i c a t i o n s h o wt op r o v i d eh i g hq u a l i t yo fs e r v i c ei n t h en e x tg e n e r a t i o ni n t e m e ti sa k e yp r o b l e m i nc o m p u t e rn e t w o r kr e s e a r c h t h e r ea r em a n ya s p e c t sw h i c hn e t w o r k sp r o v i d et h eg u a r a n t e eo ft h eq u a l i t yo fs e r v i c e h o w e v e rt h eo n eo f t h ek e yt e c h n o l o g yf o rp r o v i d i n gt h eg u a r a n t e eo f t h e q u a l i t yo f s e r v i c e i s t h eq o sm u t i n g r e s e a r c h e r sa n de x p e r t sp r o p o s em a n yc r e a t i v ea n dp r a c t i c a b l eq o sr o u t i n g a l g o r i t h m s ，w h i c hc a nb ed i v i d e di n t ot w oc l a s s e s ：s o u r c er o u t i n ga l g o r i t h m sa n dd i s t r i b u t e d r o u t i n ga l g o r i t h m s t h o u g hh a v i n gs o m ed e f e c t s ，t h e s ea l g o r i t h m sc o n t r i b u t eal o tt on e t w o r k r e s e a r c h e s t h i st h e s i sp r o p o s e st od e s i g na n dr e a l i z ed i s t r i b u t e dq o s r o u t i n ga l g o r i t h m s ：d i s t r i b u t e d q o sr o u t i n ga l g o r i t h mw i t hm u l t i - p a t hp r o b i n g ( m p d q r a ) a n dd i s t r i b u t e dp a r a l l e lq o s r o u t i n ga l g o r i t h mw i t hm u l t i p a t hr o b i n g ( m p d p q r a ) i nt h em p d q r a ，e v e r yn o d e o n l yn e e dt om a i n t a i nl o c a ls t a t ei n f o r m a t i o no fi t sa d j a c e n tn o d e s ，t h em e t r i co fw h i c hi s s 1 b ? a ? 七f l sr a t i oo fn o d ei su s e dt od e e a s et h ee x t e n s i o no ff l o o d i n g , w h i l em u l t i - p a t hc a l l i n c r e a s et h ep r o b a b i l i t yo ff i n d i n gt h ef e a s i b l ep a t h s b a s e do l li m p r o v e dm p d q r a ， m p d p q r ap r o b e sa n dr e s e r v e sr e s o u r c e si l lo n eo fs e v e r a lp a r a l l e lp a t h sa c c o r d i n gt ot h e s t a t u so fn e t w o r ka n dt h ec o n n e c t i o nq o sr e q u i r e m e n t s m p d p q r ac a nr e d u c er e s o u r c e f i a g m e n t sa n da d m i tm o r es e r v i c e si n t oan e t w o r kw i t hh e a v y1 0 a d n 圮t h e s i sc r e a t e sn e t w o r ks i m u l a t e 锄sa n dg oa l o n gs i m u l a t ee x p e r i m e n tu s i n gt h e s e t w oq o sr o u t i n ga l g o r i t h m s b yc o m p a r i s o nw i t ht r a d i t i o n a ls h o r t e s tp a t hf i r s tr o u t i n g a l g o r i t h m , i tc a nb es e e nt h a tt h e s et w oa l g o r i t h m sc 蛆b a l a n c en e t w o r kl o a da n dp r o m o t e n e t w o r kr e s o u r c eu t i l i z a t i o n u n d e rt h ec i r c u m s t a n c eo ft h en e t w o r kl i g h tl o a d ，t h e i r c o m m u n i c a t i o no v e r h e a di ss m a l l e r u n d e rt h ec i r c u m s t a n c eo ft h en e t w o r ko v e r l o a d , m p d p q r a c a nc o m b i n ew i t hs e v e r a lp a t h st oa d m i tn e wc o n n e c t i o n , s oi ti m p r o v e st h e 沈阳工业大学硕士学位论文 n e t w o r kf c s o u r c eu t i l i z a t i o nr a t i oa n dt h r o u g h p u t i nc o n c l u s i o n , a p p l y i n gt h ep r o p o s e d 蛔f i t h m st oc o n n e c t i o n - o r i e n t e dm u l t i m e d i ad a t an e t w o r kw i l li m p r o v et h ec a p a b i l i t yo f t r a n s m i t t i n gm u l t i m e d i ai n f o r m a t i o n k e yw o r d s ：q o s ，m u l t i - p a t ha l g o r i t h m ，d i s t r u b u t e dr o u t i n g , n p - c o m p l e t ep r o b l e m 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：肄日期：鲣 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 签名： ( 保密的论文在解密后应遵循此规定) 肄 导师签名：互鲤至日期：鱼兰2 ：兰：! l 沈阳工业大学硕士学位论文 1 绪论 1 10 0 s 产生的背景 服务质量( q u a l i t yo f s e r v i c e ，q o s ) 是日常生活中人们再熟悉不过的字眼。顾名思义， 服务质量往往体现了消费者对服务者所提供服务的满意程度，是对服务者服务水平的一 种度量和评价计算机系统，特别是计算机网络系统，作为计算和信息等服务的提供者， 同样存在服务质量优劣的问题。事实上，从计算机系统诞生伊始，人们就一直孜孜不倦 地致力于提高系统的服务性能和服务质量，因此，q o s 问题实际上由来已久。目前计 算机网络的q o s 问题已经成为国际网络研究领域最重要、最富有魅力的研究领域之一， 并且和网络安全等问题一道被称为下一代互联网( n e x tg e n e r a t i o ni n t e r n e t ，n g i ) 最重 要的研究领域之一，对未来网络技术的研究、应用和发展具有举足轻重的意义。 1 1 1 概述 计算机网络技术已经历了近三十年的发展过程。近年来随着i n t e m e t 和多媒体技术 的迅速发展，i n t e r n e t 上的信息量急剧增长，已由单一的数据通信向语音、图像、视频 等综合传输服务演变。而网络层不区分用户业务的种类，只提供尽力发送( b e s t - e f f o r t ) 服 务，将网络资源公平地提供给各类业务，在分组丢失、延迟等方面公平的对待各类业务， 这种尽力发送的机制使网络层无法保证传输的参数。然而，丢失率、带宽、端到端延迟、 延迟抖动等对于应用业务往往是至关重要的。 i n t e m e t 要得到进一步的发展，就必须提供这样一种方法，即用户可以通过提高网 络使用费来改善服务质量，如小的时延和稳定的时延抖动：而当用户不需要高的服务质 量时，网络使用费应随之下降；同时。当用户所交纳的网络费用一样时，应该公平的分 配网络资源。因此，面向服务质量的网络体系结构应运而生。 目前在高速网络中按照用户的要求提供q o s 控制是一个普遍的要求，也是i n t e r n e t 发展的重要挑战。多媒体信息传输与管理的q o s 控制技术作为下一代网络的核心技术之 一，是当前计算机网络中研究与开发的热点问题。 1 1 20 0 s 的定义 q o s ，即服务质量。它有多种等价或互补的定义形式。 分布式q o s 路由算法的研究 r f c 2 3 8 6 1 i 】中描述为：q o s 是网络在传输数据流时要求满足的一系列服务请求，具 体可以量化为带宽、延迟、延迟抖动、丢失率、吞吐量等性能指标。此处的服务具体是 指数据包( 流) 经过若干网络节点所接受的传输服务，强调端到端( e n d - t o - e n d ) 或网络边 界到边界的整体性。q o s 反映了网络元素( 例如，应用程序、主机或路由器) 在保证信 息传输和满足服务要求方面的能力。 另一种描述 2 1 为：q o s 是指发送和接收信息的用户之间以及用户与传输信息的综合 服务网络之问关于信息传输的质量约定。该约定可以被理解为服务提供者与用户之间的 一份服务契约，即服务提供者承担支持给定的服务质量，当且仅当用户按照约定的信息 流特征产生数据。换句话说，服务质量包括用户的要求和网络服务提供者的行为两个方 面，是用户与服务提供者两方匾主客观标准的统一。用户的要求是指定用户在i n t e r a c t 上进行多媒体通信时所要求的服务类型以及相应的传输性能和质量等；网络服务提供者 的行为则指i n t e r n e t 针对某一类服务所能提供和达到的性能与质量。 1 1 3o o s 的发展概述 自从计算机系统诞生开始，就一直存在提高系统的服务性能和服务质量的问题，因 此，可以说计算机系统的q o s 问题由来已久。对计算机网络q o s 的研究可以追溯到2 0 世纪8 0 年代初期。那时，尽管网络的性能还比较低，提供的服务种类也比较少，但一 些有远见的研究者已经认识到服务质量的重要性。s e i t z 和w o r t e n d y k e 等人在研究 a r p a n e t 中的x 2 5 通信时已提出基于用户的性能评价问题，这也许是关于计算机网 络q o s 研究的的最早文献1 3 。在早期的o s i 协议制定中也为服务质量的一些参数留有相 应的表示手段，但一直空缺未用i 1 。很长的一段时间，由于计算机网络的性能所限，人 们对q o s 的关注只停留在数据流传输中的正确率、吞吐量和延迟等单服务质量的评级 与控制上四。直到2 0 世纪8 0 年代末期，随着b i s d n 技术以及a t m 交换网的出现和 分布式多媒体应用的急剧增加，人们才开始系统地对q o s 管理和控制进行较为深入的研 究。一些实验性系统也应运而生，代表性的有英格兰开斯特大学的q o s a 工程【们、i b m 公司黑森伯格欧洲网络中心的h e i d e l b e r gq o s 模型【7 ，s l 、美国哥伦比亚大学c o m e t 研究 组提出的扩展的集成化参考模型( x r m ) 系统 9 ，1 0 1 、美国宾夕法尼亚大学的o m e g a 体系 结构【】、加利福尼亚大学伯克利分校的t e n e t 模型【1 2 l 、国际合作项目t i n a c 0 3 1 工程等。 沈阳工业大学硕士学位论文 随着i n t e r n e t 商业化的巨大成功，网上传输的多媒体信息迅速增多，网络阻塞现象 日益严重，i n t e r n c t 的q o s 问题研究也随之开始深入。i e t f ( i n t e r n e t e n g i n 吲 i n g t a s k f o r c e ) 于1 9 9 7 年9 月开始制定了有关q o s 定义与服务的一系列r f c 标准。截至目前，q o s 控制技术的研究和开发都进展得非常迅速，并且取得了许多基本的成果。国内也于近些 年开始了有关q o s 方面的研究，而且在国际上也有一定地位。目前，计算机网络的q o s 问题已经成为国际网络研究领域公认的最重要、最富有魅力的研究领域之一，并且被称 为下一代计算机网络为数不多的最重要的研究领域之一。 1 2o o s 的体系结构 关于q o s 体系结构的研究己经进行了多年，i e t f 己经建议了很多服务模型和机制， 以满足q o s 的需求。其中比较有名的有：综合服务( i n t e g r a t e ds e r v i c e s , i n t s e r v ) 模型【1 4 1 ， 区分业务( d s ) 模型1 5 d 6 l ，多协议标记交换( 1 7 ( m p l s ) ，流量工程和约束路由。综合业务 的特点是资源预留，实时应用在传输数据前必须首先建立通道和顸留资源。r s v p 是用 来建立通道和预留资源的协议。在区别型业务中，把包加以标记，产生不同的级别，每 个级别的包得到不同的服务级别。m p l s 是一种前向转发策略，在进入m p l s 作用域时 给包赋予一定的标签，随后包的分类、转发和服务都将基于标签完成。流量工程是一种 安排通信流量如何通过网络的过程。约束路由在寻径路由时会受到一定的约束，如带宽 或时延的要求。 1 2 1 综合服务 由于网络应用的发展与网络所能提供的服务之阔的矛盾，促进了综合服务研究的发 展。日前，综合服务 1 4 1 ( i n t s e r v ) 的体系结构己经相当成熟，其基本实现方法是： ( 1 ) 信令向网络提出业务流传输规格( f l o ws p c c ) ，并建立和拆除传输路径上的业务 流状态 ( 2 ) 主机和路由器节点建立和保持业务流状态信息。 在i n t s c z 、t 体系结构中，必须对网络资源进行明确的管理。这意味着，资源预留 ( r e s o u r c er e s e r v a t i o n ) 与接入控制( a d m i s s i o n c o n t r 0 1 ) 将会是i n t s e r v 体系中的主要构件，这 就是对传统网络模型的最重要和最基本的改变。资源预留协议( r e s o u r c er e s e r v a t i o n 分布式q o s 路由算法的研究 p r o t o c o l ，r s v p ) 在i n t s e r v 体系结构中起着至关重要的作用，不管是接入控制还是业务流 控制，r s v p 都不可或缺。 使用r s v p 信令建立数据发送路径以及为业务流预留资源的过程为：发送端给接收 端发送一个p a t h 消息，以指定通信的特性。沿途的每个中间路由器把p a t h 消息转发 给由路由协议决定的下一跳。当收到个p a t h 消息时，接收方做出的反应是用一个 r e s v 消息为该流请求资源。沿途的每个中间路由器可以拒绝或接受r e s v 消息请求。 如果请求被拒绝，路由器将发送一个出错消息给接收方，并且中断信令的处理过程。如 果请求被接受，为该流分配链路带宽和缓冲区空间，并且把相关的流状态信息装入路由 器中。 除了最佳效果业务外，集成业务模型还新定义了两种服务类型：确保型 ( g u a r a n u ：e d ) 业务，用于需要固定时延限制的应用；预测型( p r e d i c t i v e ) ! i k 务，用于可 能需要时延限制的应用。实现确保型业务和预测型业务的定义分别在确保型业务和控制 负载( c o n t r o l l e dl o a d ) 业务中。这一模型的思想是“为了给特定的客户包流提供特殊的 o o s ，要求路由器必须能够预留资源。反过来要求路由器中有特定流的状态信息”。 集成业务模型的优点有：能够提供绝对有保证的q o s 。详细的设计使r s v p 用 户能够仔细地规定业务种类。因为r s v p 运行在从源端到目的端的每个路由器上，因此 可以监视每个流，以防止其消耗比它请求、预留和预先购买的要多的资源。r s v p 在 源和目的地之间可以使用现有的路由协议决定流的通路。r s v p 使用i p 包承载，使用“软 状态”的概念，通过周期性的重传p a t h 和r e s v 消息，协议能够对网络拓扑的变化傲 出反映。正如p a t h 和r e s v 刷新用来更改该预留的流的通路那样，没有了这些消息时， r s v p 协议释放与之关联的资源。设计集成模型开始的目的之一就是使锝q o s 能够 工作在从一个源到一个目的地( u n i c a s t ) 和从一个源到多个目的地( m u l t i c a s t ) 。r s v p 协议 能够让p a t h 消息识别多播流的所有端点，并发送p a t h 消息给它们。它同样可以把自 每个接收端的r e v p 消息合并到一个网络请求点上，该点可以让一个多播流在分开的连 接上发送同样的流。 但是集成业务模型同样存在一些缺点：伸缩性不好。随着流数目的增加，状态 信息的数量成比例上升，占用了大量的路由器存储空间和处理开销。因此，在因特网核 沈阳工业大学硕士学位论文 心中这种结构的伸缩性不好。对路由器的要求较高由于需要进行端到端的资源预 留，必须要求从发送者到接收者之间的所有路由器都支持所实施的信令协议。因此所有 路由器必须实现r s v p 、许可控制。m f ( m u l t i f i e l d ) 分类和包调度。 对确保型业务 需要网络全部使用集成业务。如果中间有不支持的节点或网络存在，虽然信令可以透明 通过，但实际上对于应用来说，已经无法实现真正意义上的资源预留，所希望达到的 q o s 保证也就打了折扣该模型不适合于短生存期的流。因为为短生存期包预留资 源的开销很可能大予处理流中所有包的开销。但因特网流量绝大多数是由短生存期的流 构成的。在短生存期的流需要一定程度的q o s 保证时，集成业务模型就显得得不偿失了。 1 2 2 区分服务 在i n t s e r v 体系的发展遭遇巨大障碍的时候，d i f i s e r v 应运而生【1 5 l 。事实上，也正是 i n t s e r v 的推动者缔造了d i f f s e r v 。区分服务( d i f f s e r v ) 是一种适合于大型路由器网络的集 中式通信量处理机制。其目标在于设计、实现、管理方面的简单有效，以克服i n t s e r v 所遇到的难题。 经过几年的发展，d i f l s e r v 的相关概念及模型己经比较成熟，d i f f s e r v 体系结构也 已经比较明确。在d i f l s e r 结构上有关服务的提供方面的研究，如d s c p 的定义，p h b 服务的定义等也逐步得到发展【1 6 1 。区分服务体系结构基于这样一个简单的模型：进入 d s 区域的业务流在网络边界节点被分类和调节。并归入到不同的行为聚集中。每个行 为聚集用一个d s c p 值来标明。在网络内部，报文以与d s c p 相关的逐跳行为来转发。 d i f f s e r v 基本实现方法是嗍： ( 1 ) 简化网络内部节点的服务机制。在网络内部的核心路由器中只保存简单的区分 服务代码( d i f f e r e n t i a t e ds e r v i c e sc o d e p o i n t ，d s c p ) 与逐跳行为( p e rh o pb e h a v i o r , p h b ) 的 对应机制，在数据流进入核心路由器时只根据报文头部区分服务嗍( d i f f e r e n t i a t e d s e r v i c e s ，d s ) 域中的d s c p 进行简单的转发服务。 ( 2 ) 聚合网络内部核心路由器的服务对象。网络内部路由器的服务对象为宏流，而 不是单流。 5 一 分布式q o s 路由算法的研究 1 2 3 多协议标签交换 1 9 9 7 年，以c i s c o 公司为主的几家公司f 包括i p s i l o n 、m m 、c a s c a d e 、t o s h i b a ) 提出 了多协议标签交换【1 7 1 ( m u l t i p r o t o c o ll a b e ls w i t c h , m p l s ) 技术。m p l s 技术产生的初衷就 是为了综合利用网络核心的交换技术和网络边缘的m 路由技术各自的优点而产生的。 m p l s 还处在发展及完善当中，标签分发协议，l s p 控制、标签合并等都还不完善。m p l s 所能支持的q o s 机制也正处在试验中。尽管如此m p l s 的体系结构大致还是明确的： m p l s 是一个前向转发策略，由c i s c o 的标记路由发展而来。在o s i 的7 层模型中，它 位于第2 层和第3 层之间。每个m p l s 都有一个头。这个头包括一个2 0 b i t 的标签，一 个3 b r 的业务级另o ( c o s ) 字段，一个l b i t 的标签栈指示器和个s b i t 的t t l 字段。m p l s 头的封装是在链路层头和网络传输层头之间。一个具有m p l s 能力的路由器，在转发包 时只检查标签。网络协议可以是m 或其他类型的，这也是叫多协议标记路由的原因。 在文献【1 7 】中，将标签定义为“标签是一个短的、固定长度的并且是局部重要的标 识符以用于标识一个转发等价类。添加于一个特定报文的标签表示该报文所分配的转发 等价类。”。这种基于标签的交换方式允许路由器在作转发决定的时候仅仅以简单的标 签为基础，而不是基于目标i p 地址作复杂的路由查找。m p l s 为基于m 的网络带来了 许多优点：虚拟专用网提供可伸缩的、稳固的r o s 控制，m p l sv p n 是基于网络的v p n 、 消除多层数据包的转发仅仅根据其标签来决定，丽不需要经过多层协议的头部分析以及 流量工程，多条传输路径之间的负载平衡。它能够提供更快的包分类和转发速度以及一 种有效的隧道机制。 在一个m p l s 网络当中，进入m p l s 区域的报文在“标签边缘路由器( l a b e le d g e r o u t e s ，l e r ) ”处被分配一个标签，报文沿着“标签交换路径( l a b e ls w i t c hp a t h , l s p ) ”， 进行转发，路径中的每个标签“交换路由器( l a b e ls w i t c hs o u t c s ，l s 鼬”仅仅根据标签内 容来做出转发决定。 具体来说，m p l s 将每个进入m p l s 区域的报文归类为一个转发等价类( f o r w a r d i n g e q u i v a l e n c ec l a s s ，f e c ) ，该等价类以一个标签来标识。因此，报文中的标签内容也表示 了该报文所分配的f e c 。 一6 沈阳工业大学硕士学位论文 在m p l s 体系结构中，还有一个非常关键的问题，就是如何将路由器分配给某一特 定的业务流的标签通知其他的路由器，这就是标签分发协议( 1 a b e ld i 鲥b i i t i p r o t o c o l ， l d n 的工作。当一个l s r 分配了一个标签值给某个转发等价类时，它需要让它的对端 路由器知道该分配的标签以及它所代表的意义，l d p 正是用少此目的。由于在一个m p l s 区域内从入域l s r 到出域l s r 的一组标签定义了一条标签交换路径( l s p ) ，并且由于 标签是网络层路由到数据链路层路径的映射，通过使用一组过程在l s r 对端之间分发 标签，l d p 帮助建立一条l s p 。 m p l sl s p 能够当作隧道( t u n n e o 用。当一个包进入一个隧道的起点时，它的通道已 经完全确定了，包将出现在隧道的终点处。它的通道完全由入口处分配给它的标签决定， 没有必要列举出隧道中所有的路由器。因此，它的效率比其他隧道机制都要高。 1 2 4 流量工程 从根本上说，在网络负载严重时，集成服务模型和区服务模型提供的性能平稳下 降。当网络负载比较轻时，集成服务模型和尽力而为服务机制没什么差别。在网络负载 比较大时，导致网络拥塞的原因可能会是网络资源不足或者流量分布不均匀。在前一种 情况下，所有路由器和链路都会过载，唯一的解决办法是升级基础设施，提供更多的网 络资源。在第二种情况下，网络的一些地方过载而其他地方负载却较轻，网络资源不能 得到充分的利用。现在的动态路由协议r i p 、o s p f 和i s i s 都会导致不均匀的流量分布， 因为他们总是选择最短的路径转发包。结果是，在两个结点之间顺着最短路径上的路由 器和链路可能发生了拥塞，而沿较长路径的路由器和链路却是空闲的。o s p f 等价多路 径( e c m p ) 选择，在给多个最短路径分配负载时是有用的。但是，如果只有一条最短路 径，e c m p 也无能为力了。对于简单网络，可以让网络管理员手工配置链路的代价，均 匀的发配流量是可以的，但是对于复杂网络，这几乎是不可能的。流量工程( t r a f f i c e n g i n e e r i n g ，t e ) 就是安排传输流如何通过网络，以避免不均匀的使用网络而导致拥塞的 过程。因而，在避免拥塞和提供良好的网络性能方面，流量工程其实是对区分服务模型 的补充。 流量工程就是为业务流选择路径的处理过程，以在网络中不同的链路、路由器和交 换机之间平衡流量负载。当网络中存在多条并行或可选的路径时，流量工程就显得非常 分布式q o s 路由算法的研究 重要了。流量工程的主要目的是提供有效可靠的网络操作，同时优化网络资源的利用和 业务流性能。t f 的目标是在一给定节点从与另一节点之间计算一条路径( 源路由) ， 该路径不违反它的约束( 例如。带宽管理要求) ，并且从一些数量指标看来是最优的。 一但路径被计算后，t f 将负责在该路径上建立和维护转发状态。 1 2 5 约束路由 约束路由 1 8 1 是由q o s 路由发展而来，这两个术语经常交换使用，但实际上，约束 路由是一个更一般的术语。约束路由和q o s 路由之间的区别是：q o s 路由在为业务流 选择路由时，只考虑个别业务流的q o s 需求，而约束路由在为业务流或者业务流的集合 计算路由时，除了考虑业务流或者业务流集合的q o s 需求外，还考虑其他诸如管理策略 等的约柬。 约束路由对q o s 路由进行了扩展，其目标是： ( 1 ) 选择能够满足一定服务质量要求的路由 ( 2 ) 避免拥塞并改善网络的效率 ( 3 ) 提高网络的利用率 当决定一条路由时，约束路由不仅考虑网络的拓扑结构，还要考虑数据流的需求， 链路资源的可用性，以及网络管理员指定的其他规则。通过对这些因素的全面考虑，约 束路由可能发现一条负载很轻但较长的路径要比一条负载很重的最短路径要好，因而可 以对网络业务进行更加平均的分配。 目前的网络使用的q o s 控制技术还不够完善，主要存在以下问题【1 9 1 ： ( 1 ) 网络系统状态和链路带宽容量变化的不确定性，使得传输通路的端到端带宽预 留缺乏有效的保证。 ( 2 ) q o s 选路、资源预留和信息传输调度算法的复杂性，还不能适应高速信息传输 处理时间的要求。 ( 3 ) q o s 要求所导致的资源利用的无效性导致不能充分利用网络资源提高网络的吞 吐量。 ( 4 ) q o s 控制方案基本上是静态方案，缺乏有效地动态控制方案来捕捉网络拓扑结 构的变化。 一8 沈阳工业大学硕士学位论文 ( 5 ) 一些基本研究成果主要存在于理论中。没有形成专利技术和成熟的技术产品。 1 3 研究内容与本文所做的工作 使下一代互联网( n g i ) 能够提供有服务质量保证的传输业务是目前计算机网络研究 的主要课题。而在实际的多媒体和实时应用中，对延迟、延迟抖动、丢失率和带宽等方 面有许多不同的q o s 限制。因此基于多个约束条件建立的网络模型可以更准确地反映实 际的q o s 路由选择问题，随着人们对网络服务质量要求的提高和网络规模的不断扩大， 研究基于多约束的q o s 路由算法，以获得良好的网络服务质量和高的网络资源利用率具 有十分重要的研究意义。本课题的主要研究目标是研究基于多约束的q o s 路由算法及有 关技术。主要研究内容包括： ( 1 ) 多约束的q o s 路由问题就是在网络中找到一条满足多个独立限制条件的可行路 径。这个问题是q o s 路由中的一个主要问题，同时它也是一个n p 完全问题。在这个领 域的研究人员已经提出了许多算法来解决这个问题。本文对现有的多约束q o s 路由算法 进行了分类，按类别着重分析和评价了在这个研究领域中提出的新算法。 ( 2 ) 提出了基于多路探测的分布式q o s 路由算法m p d q r a 。m p d q r a 算法是 一种以节点传输成功率为度量标准，改进的分布式q o s 路由算法。通过模拟测试说明了 该算法能平衡网络负载，提高网络资源利用率，具有较好的性能。它在网络轻负载情况 下，通信开销比传统的分布式路由算法( d r a ) 小。 ( 3 ) 在m p d q r a 算法的基础上提出了基于多路探测的分布式并行q o s 路由算法 m p d p q r a 。m p d p q r a 算法在单一通路不能满足连接请求要求时，寻找多条能联 合满足要求的一组并路，并预留资源共同满足用户的服务质量要求。通过仿真测试可知 该算法不仅继承了分布式q o s 路由算法简单、链路开销小的优点，而且可以减少网络处 于重负荷时所产生的“资源碎片”，接纳更多的业务。 1 4 论文的组织 论文全文共分6 章。在论述q o s 路由算法的研究时，首先提出问题，然后针对具体 问题提出相应的算法，并在模拟仿真环境中通过与其它算法的比较来验证算法的有效 性，最后给出结论。 分布式q o s 路由算法的研究 第一部分主要介绍q o s 的产生背景、q o s 体系结构，并对本文的主要工作进行了 论述。 第二部分给出了q o s 路由的定义、q o s 路由的目标，并对q o s 路由引起的问题及 解决方法进行了详细论述。 第三部分讨论基于多约束条件下，q o s 路由算法的相关概念问题。首先介绍需要用 到的网络模型，度量以及度量的组合规则并且提出了数学模型。这章中，还归纳分析了 已有的各种多约束条件下的q o s 路由算法。 第四部分集中讨论本文提出的m p d q r a 和m p d p q r a 这两种分布式路由算法。 第五部分介绍网络仿真平台n s 2 ，给出q o s 路由流程，及测试方案，讨论如何建 立q o s 网络仿真环境，并对本文提出的算法进行仿真验证，结果分析。 第六部分对这篇论文进行总结，并讨论未来的研究方向和工作。 沈阳工业大学硕士学位论文 2o o s 路由 2 1 概述 目前网络研究主要通过两个途径提高q o s ，一个是结点控制：另一个是整体网络或 局部网络控制。结点控制在单结点或单链路完成，主要控制业务对单结点共享资源的占 用，包括共享的链路、缓存区、处理器资源。结点控制主要的策略包括：业务流整形、 业务调度、结点缓冲区管理，整体或局部网络控制通常通过对路由与信令的控制达到对 业务流或业务连接在网络中传输的直接控制，因路由直接关系到网络性能，所以q o s 路由成为解决q o s 问题的一项关键技术。 路由是把信息从源端穿过网络传递到目的端的行为，在传递的路径中至少遇到一个 中间( i n t e r m e d i a t en o d e ) 节点。路由通常与桥接来对比，在表面看来，它们具有相同的功 能，完成相同的任务。但从本质来讲，路由和桥接有一定的区别，其主要区别在于桥接 发生在o s i 参考协议的第二层( 链接层) ，而路由发生在第三层( 网络层) 。这一区别 使二者在传递信息的过程中使用不同的信息，从而以不同的方式来完成其任务。 路由的话题早己在计算机界出现，但直到八十年代中期才获得商业成功，这一时间 延迟的主要原因是七十年代的网络很简单，后来大型的网络才较为普遍。在传统的数据 网络中，路由选择主要内容是在源端和目的端建立一条通路。路由协议通常只对网络的 特性进行某一方面的量度，如源端和目的端之间的跳数、延迟等。随着网络的不断发展， 多媒体信息在网络中的应用越加广泛，对网络所能提供的服务质量也提出了更高的要 求。因此满足服务质量的路由协议也随之出现，并迅速发展起来。为了支持更多的q o s 请求，路由协议需要通过更为复杂的模型使用多个量度( m u l t i p l em e t r i c s ) 来表示网络特 性，如在带宽、延迟和丢失率三个方面表现网络特性。因此，q o s 路由最基本的问题就 是如何找到一条能满足多个限制的路径。由于以往路由协议的复杂度已经接近可能的极 限，所以q o s 路由协议设计中一个很重要的方面就是如何使由于支持q o s 而引入的复 杂度不削弱路由协议的可测量性脚，2 ”。 分布式q o s 路由算法的研究 2 2o o s 路由的目标 q o s 路由即根据网络上可提供的一些资源信息( 如流的q o s 要求) 决定流的路径。 q o s 路由的主要目标有： ( 1 ) 决定合理路径：基于q o s 路由从很多可能的选择中决定一个路径，这个路径更 可能提供给定流的q o s 要求。理合路径的选择以多约束为条件，例如路径花费，提供者 选择。 ( 2 ) 优化资源的使用：一个依赖与网络状态的q o s 路由机制可以通过提高网络总体 吞吐量使网络资源得以有效的利用。这样路由机制可以作为有效网络工程的基础。 ( 3 ) 良好的性能补偿：在网络工程中，依赖于状态的路由可以作为传输不足的补充， 和集中式状态路由机制相比。得出更好的吞吐量和更好的性能补偿。 2 30 0 $ 路由在q o s 架构中的位置 下面讨论q d s 路由和其他相关的q o s 机制的关系 2 2 - 2 5 ，不同的部分在框架里的相 关位置如下图： 图2 1o o s 各个部分在o o s 框架中的位置 f i g 2 1t h er e l a t i o n s h i pb e t w e e nq o sc o m p o n e n t sa n dq o sf r a m e w o r k 2 3 1 区分服务和( 1 0 s 路由 区分服务机制是减弱i p 路由的，所以在一个源和目的的数据流会沿着同一路径， 不管它属于哪一个类型的服务，所以区分服务本身对路由没有任何影响。这意味着区分 沈阳工业大学硕士学位论文 服务域容易引起拥塞。例如，在网络中心聚集的额外流量会引起拥塞。当流量从边缘路 由汇集到中心路由的时候，因为从中心路由到下一个中心路由的连接比边缘路由到中心 路由要快，所以，不会引起拥塞。然而，如果流量在中心路由之间路由，以致于流量都 汇聚到一个路由，传出数据的路由不够快。区分服务不能解决这个问题。q o s 路由用于 避免这种情况。在一个区分服务域，q o s 路由用来发现可以满足数据流要求和避免拥塞 的路径。 另一个有可能发生的问题是，额外的流量是否能够比较好的考虑低优先级的流量的 路由问题。由于高优先级流量的原因，当一些额外的流量优先级很高的时候，会给一些