（计算机应用技术专业论文）在internet中多限制条件下qos路由算法研究.pdf

中南丈学硕士学位论文 摘要 目前的i n t e r n e t 只提供“尽力而为”的服务，这就意味着它只能尽力的转 发用户的数据报，而在带宽和延迟等方面不提供任何保证。虽然这种服务非常适 用于传统的应用，但是对于新出现的实时和多媒体应用却是无法忍受的。在新一 代i n t e r n e t 网络上提供高水平服务质量保证已经成为目前计算机网络研究的主 要课题。 近几年的研究表明网络路由算法对实现网络保证质量的服务起到了非常关 键的作用，对0 0 s 路由的研究已经成为q o s 研究领域中的一个非常重要研究方向。 由于基于多个约束条件建立的网络模型可以更准确地反映实际的q o s 路由选择 问题，随着人们对网络服务质量要求的提高和网络规模的不断扩大，研究基于多 条件限制的q o s 路由算法，以获得良好的网络服务质量和高的网络资源利用率具 有十分重要的研究意义。本文主要研究基于多个限制条件下的q o s 路由算法及相 关技术。 本文首先深入分析了基于i p 的q o s 研究体系、路由策略与算法，论述了多 个限制条件下的0 0 s 路由算法的研究现状。对现有的多限制条件q o s 路由算法进 行了分类，并讨论了多个限制条件下路由算法研究的问题和模型。 多个限制条件下的q o s 路由问题是q o s 路由研究中的一个重要课题。它包括 多个限制条件下的路径选择( m c p ) 和路径优化选择( m c o p ) 两个主要问题。对于 m c p 问题，本文提出了一种有效的多个限制条件下的q o s 路由算法一e r a m c 。 e r a m c 算法利用预先计算来简化网络拓扑，然后采用带优先权的宽度优先搜索算 法寻找满足多个限制条件的传输路径。对于m c o p 问题，本文主要讨论了在一般 意义上多个限制条件下的q o s 路由优化算法问题，提出和建立了多受限的q o s 路由优化问题的研究模型。在此基础上，提出了一种新的多受限优化路径选择算 法一e a m c o p 。该算法通过有效的限界剪枝策略大大减少了搜索空间的大小，极 大的提高了算法的性能。 总之，本文主要研究基于多个限制条件下的q o s 路由算法，为今后该问题的 研究提供了一定的理论依据。 关键词：路由算法服务质量多个限制条件 中南文学硕士学 荻论义 a b s t r a c t e u r f e n ti n t e r 魏e tc a no n l yp r o v i 鑫e ”b e s 弋e f f o r t ”s e r ￥i c e ，鬻h 主b 豫e a 巍s i tw i l lt r yi t sb e s tt of o r w a r du s e r s 娃a t ap a c k e t s ， b u tc a np r o v i d en o g u a r a n t e e sr e g a r d i n gb a n d w i d t ha n dd e l a y w h i l et h i sk i n do fs e r v i c ei s 8 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 j o n s ， i t si n t 0 1 e r a b l ef o rn e w l y e m e r g e dr e a l t i m e ，u l t i m e d i aa p p l i c a t i o n s h a wt op r o v i d eh i g hq u a l i t y o fs e r v i c ei nt h en e x tg e n e r a t i o ni n t e r n e ti sak e yp r o j e c ti nc o i d p u t e r n e t w o r kr e s e a r c h t h er e s e a r c hi nt h e s ey e a r ss h o w st h a tt h ea l g o r i t h mo fn e t w o r k r o u t i n gp l a y s a n i m p o r t a n tp a r t i n p r o v i d i n gq u a l i t y 一。f s e r v i c e g u a r a n t e e s 。 了h es t u d yo f 盆o sr o u t i n gh 挂sb e c o 氆eav e r yi m p o r t a n ts t u d y i r e c t i o ni 耙r e s e a r e hf i e l do f 舀o s 。e o 秘s i d 棼r i 珏gt h a tn e t 餮o r k 毪l o d e lb a s e 蠢 瓣h l t i p j eo o 菇s t r a i 扎t se a nr e f l e c t 奄o sr o h t i n gp r o b l e 氆i np r a e t i c e 瑗o r e 8 c o u r 拄t 8 l y ， w i t ht b ei n c r e 8 s eo fq u 8 li t y o f s e r v i c ed e 珥a n da n d t b e e n l a r g e m e n to fn e t w o r ks c a l e ， t h er e s e a r c ho fq o sr o u t i n ga l g o r i t h l l lw i t h m u l t i p l ec o n s t r a i n t si so fv e r yi m p o r t a n tr e s e a r c hs i g n i f i c a n c et o a c h i e v eg o o dn e t w o r kq u a l i t yo fs e r v i c ea n dh i g he f f i c i e n c yi nr e s o u r c e u t j1 iz a t i o n i nt h i sp a p e r ，w em a i n l y8 t u d yq o sr o u t i n ga l g 。r i t h 丌1 sb a s e d m u l t i p l ec o n s t r a i n t sa n dr e l a t i v et e c h n o l o g i e s f i r s t ，t h i sp a p e rd e e p l ya n a l y z e sq o sr e s e a r c ha r c h i t e c t u r e ，r o u t i n g p 0 1 j c ya n da l g o r i t h mb a s e do ni p ，a n di n t r o d u c e st h er e s e a r c hs t a t u so f r o u t i n ga l g o r i t h 强sw i t h 瑶u l t i p l eo o n s t r a i n t s ， e u r r e n ta l g o r l t h m sw i t h 辩u l t i 登i ee o 秘s t r 鑫i n t sa r ee l 盆s s i f i e 鑫a 黪dt b er o 珏专i n gp r o b j 8 琢a n dm o d e lw i t 纛 黼h l t i 羚1 eo o n s t r a i n t sa r ed i s e u s s e 畦i nt 囊ep 鲁p e r 。 舀o sr o u t i n gp r o b l e m 霄i t b u l t i p l ec o n s t r a i n t si sa ni p o r t a n tp r o j e e t i nq o sr o u t i n gr e s e a r c h i t a i n l yi n c l u d e sm u l t i c o n s t r a i n e dp a t h ( m c p ) p r o b l e ma n d u l t i c o n s t r a i n e do p t i m a lp a t h( m c o p )p r o b l e m f o rm c p p r o b l e m ， t h ep a p e rp r e s e n t sa 九e f f i c i e n tq o sr o u t i n ga l g o r i t h mw i t h m u l t i p l ec o n s t r a i n t s e r l c m a k i n gu s eo fp r e c o m p u t a t i o n ， a l g o r i t h m e r a m cs i m p l i f i e sn e t w o r kt o p o l o g ya n du s e sab r e a d t h f i r s ts e a r c h a l g o r i t h mw i t hp r i o r i t y t of i n dat r a n s m i s s i o np a t ht h a ts a t i s f i e s f i l u l t i p l e c o n s t r a i n t s +f o rm c o pp r o b l e 辩，t h ep a p e rd i s e u s s e st b eq o s r o u 专i n go p t i m a la l g o r i t h 疆 w it h g e n e r a l臻u l t i p l ee o n s t r a i n t s ， a n d e o n s t r u c t st h em o 巷e lo ft b e o s o u l n 器o 专i 矗 & lp r o b l e 瑶w i t 魏臻u l t i p l e 4 ! 堕查堂堡主兰生堡苎一 c 。n s t r a i n t s ， a n dp r o p o s e san e wq o sr o u t i n go p t i m a la l g o r i t h mw i t h m u l t i d l ec o n s t r a i n t s e a m c o p m a k i n gt h eb e s t 。fa n e f f i c i e n tp r u n i n g p 。1 i c y ， t h ea l g o r i t h i i lr e d u c e sg r e a t l yt h es i z eo fs e a r c hs p a c ea n d i m p r o v e st h ep e r f o r l l l a n c e o fa l g o r i t h m i nc o n c l u s i o n ， t h ep a p e rf o c u s e si nt h er e s e a r c ho fq o sr o u t i n g a l g o r i th i i l s b a s e dm u n i p l ec 。n s t r a i n t s i tw i l lp r o v i d es o m et h e o r y r e f e r e n c ef o r t h es t u d ya b o u tt h ep r o b l e i nt h ef u t u r e k e yw o r d s r o u t i n ga l g o r i t h m q u a l i t yo fs e r v i c e sm u l t i p l ec 。n s t r a i n t s 中南大学硕士学能论文 第一章绪论 瓣耱，基于存筵转发撬裁懿i n t e r n e t ( 1 p v 4 标准) 只为焉户提篌了“尽力蔼 淹( b e s t e f f o r t j ”的服务，不能傈证数搽谯传输豹实时健、完整往戳及至l 达懿 顺序性，不能保证服务的质量，所以主瑟殿蹋在文件传送和电子邮件服务。随慧 i n t e r n e t 的飞速发展，人们对于在i n t e r n e t 上传输分布式多媒体应用的需求越 来越大，一般来说，用户对不同的分布忒多媒体应用有着不同的服务质量要求， 这就受求网络应能根据用户的要求分配和调度资源，因此，传统的所采用的“尽 力而为”转发机制，已经不能满足用户的鼹求。为了解决在i n t e r n e t 等计算 机网上商质量地传输多媒体信息地问题，荧圆于1 9 9 6 年底，开始了以提高网络 服务质量研究为核心的i n t e r n e t 以及n g i ( 下代i n t e r n e t ) 等研究项目。 i 仔( i n t e r 勰te n g i n e e r i n gt a s kf o r c e ) 魄成立了专门的工亏# 小组来研究多媒 拣熬努蓑量豹定义襄摆关豹拣准。 黼络缀务蕨量( q 珏a l i t yo fs e r v i e e ，簿繇o s ) 莛阏终与爨户之阗戮及网络 上鞭辐邂信静蔫户之闻关于信惠传输与共攀鹣囊的约定。服务质量可敬由一些特 定的参数来描述，服务的提供者允许服务盼使用者在建立连接时对各种服务参数 指定希望的、可接受的最低限度值，有些参数迸可以用于无连接的传输服务。服 务的提供者根据网络服务的种类或它能够获得的服务来检查这些参数，决定能否 撼供所要求的服务。一些典型参数直口下：网络带宽、传输延时、延时抖动、差错 帮等。在i n t e r n e t 上对网络服务质最的瓣求也越来越高，例如，视频会议、网 络电话的实时和带宽要求，大数据量数据备份的完成时间要求等。如何在网络中 实蛾多种服务质量是全世界通信领域霓椒研究的重点课题”。 q o s 的掰究有多个方面，包括流量熬形( t r a f f i o 曲a p i n 函”3 、包调度算法 ( p 8 e k e ts e h e 囱l i n g ) “。、路盘算法( sr o n t i n g ) ”1 、资源预錾0 e s o u r e e r e s e r v 8 t i o 娃) ”。、莹入控裁( c 越la 翻i s s i o n n r 0 1 ) 。等静磅交。在舀o s 豹霉 鹣磷究中，主要的研究集中于网络节点闻瓣调度策赂、接入控制策略上，面网络 路妇算法的研究一直被忽视。近几年的研究液明网络路由算法对实现网络保证质 爨的服务起到了非常关键的作用，同时网络路由算法也是平衡网络负载和充分利 用网络资源的重要保证“1 。 1 + 1q o s 体系结构 标准i n t e r n e t 协议( i p ) 的网络提供尽力丽为的数据传输。这种i p 网络允许 客户端主祝的结构复杂一些，丽网络端的精构可以操持相对的简单，因为 i n t e r n e t 耍支持叁身豹快速发震，掰默这撵戆缝掏翅分是有磐楚豹。当越来越 多蠡冬主簸连在一霆懿霹误，黯霜络羧务熬爨袋袋终会超过疆终兹簸力，嚣骚务鞠 6 中南大学硕士学位论文 不会停止，由此产生网络性能的逐渐恶化，进而造成传输迟延的变化( 抖动) ，甚 至引起分组丢失，虽不会影响常用的i n t e r n e t 应用( 如，电子邮件，文件传输和 w e b 应用) ，但其它应用就不能适应有迟延的服务。传输迟延对有实时要求的应 用( 例如传送多媒体信息) 及大多数双向通信( 如电话) 带来了问题。这就要通过在 i n t e r n e t 网络中实现q o s 协议来保证多媒体业务的应用。 关于q o s 体系结构的研究已经进行了多年，并提出了一些体系结构，主要包 括：i b m 公司的h e i d e l b e r gq o s 模型”3 、美国哥伦比亚大学c o 肛t 研究组提出的 x r m 模型”3 、美国宾夕法尼亚大学的o 皿g a 体系结构“、加利福尼亚大学伯克利 分校的t e n e t 模型“”等。 i e t f 已经建议了很多服务模型和机制，以满足q o s 的需求。其中比较有名 的有：集成业务r ：v p 模型”“，区分业务( d s ) 模型“，多协议标记交换( m p l s ) ， 流量工程和约束路由。集成业务的特点是资源预留，实时应用在传输数据前必须 首先建立通道和预留资源。r s v p 是用来建立通道和预留资源的协议。在区分业 务中，把包加以标记，产生不同的级别，每个级别的包得到不同的服务级别。m p l s 是一种前向转发策略，在进入m p l s 作用域时给包赋予一定的标签，随后包的分 类、转发和服务都将基于标签完成。流量工程是一种安排通信流量如何通过网络 的过程。约束路由在寻径路由时会受到一定的约束，如带宽或时延的要求。 1 1 1 集成业务r s v p 模型 集成业务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 消息请求。如果请求被拒绝，路由器将发送一个出错消息给接收方，并 且中断信令的处理过程。如果请求被接受，为该流分配链路带宽和缓冲区空间， 并且把相关的流状态信息装入路由器中。 除了最佳效果业务外，集成业务模型还新定义了两种服务类型：( 1 ) 确保型 ( g u a r a n t e e d ) 业务，用于需要固定时延限制的应用；( 2 ) 预测型( p r e d i c t i v e ) 业 务，用于可能需要时延限制的应用。实现确保型业务和预测型业务的定义分别在 确保型业务r f c 2 2 1 2 和控制负载( c o n t r 0 1 l e dl o a d ) 业务r f c 2 2 1 1 中。这一模型 的思想是“为了给特定的客户包流提供特殊的0 0 s ，要求路由器必须能够预留资 源。反过来要求路由器中有特定流的状态信息”。 集成业务模型的优点有( 1 ) 能够提供绝对有保证的o o s 。详细的设计使r s v p 用户能够仔细地规定业务种类。因为r s v p 运行在从源端到目的端的每个路由器 中南大学硕士学位论文 上，因此可以监视每个流，以防止其消耗比它请求、预留和预先购买的要多的资 源。( 2 ) r s v p 在源和目的地之间可以使用现有的路由协议决定流的通路r s v p 使用i p 包承载，使用“软状态”的概念，通过周期性的重传p a t h 和r e s 、r 消息， 协议能够对网络拓扑的变化做出反映。正如p a t h 和r e s v 刷新用来更改该预留的 流的通路那样，没有了这些消息时，r s 、，p 协议释放与之关联的资源。( 3 ) 设计集 成模型开始的目的之一就是使得q o s 能够工作在从一个源到一个目的地 ( u n i c a s t ) 和从一个源到多个目的地( 叫l t i c a s t ) 。r s v p 协议能够让p a t h 消息识 别多播流的所有端点，并发送p a t h 消息给它们。它同样可以把自每个接收端的 r e v p 消息合并到一个网络请求点上，该点可以让一个多播流在分开的连接上发 送同样的流。但是集成业务模型同样存在一些缺点( 1 ) 伸缩性不好。随着流数目 的增加，状态信息的数量成比例上升，占用了大量的路由器存储空间和处理开销。 因此，在因特网核心中这种结构的伸缩性不好。( 2 ) 对路由器的要求较高。由于 需要进行端到端的资源预留，必须要求从发送者到接收者之间的所有路由器都支 持所实施的信令协议。因此所有路由器必须实现r s v p 、许可控制。m f ( m u l t i f i e l d ) 分类和包调度。( 3 ) 对确保型业务需要网络全部使用集成业务。如果中间 有不支持的节点或网络存在。虽然信令可以透明通过，但实际上对于应用来说， 已经无法实现真正意义上的资源预留，所希望达到的q o s 保证也就打了折扣。( 4 ) 该模型不适合于短生存期的流。因为为短生存期包预留资源的开销很可能大于处 理流中所有包的开销。但因特网流量绝大多数是由短生存期的流构成的。在短生 存期的流需要一定程度的q o s 保证时，集成业务模型就显得得不偿失了。 l - 1 2 区分业务( d s ) 模型 基于既考虑网络现状，同时又能达到实现服务质量的目的，研究人员提出了 区分业务( d i f f s e r v ) 模型。 1 1 2 1 区分业务( d s ) 模型介绍 i p v 4 头包括一个t o s 字段，它的含义以前有定义。应用程序可以设置t o s 字段中的3 个比特来表示需要低时延、高吞吐量或低丢失率的服务。但是这种选 择很有限。区分业务定义了t o s 字节的格式( 术语叫d s 字段) ，以及一个包转发 处理库的集合( 术语叫p e r h o p 行为，或p 衄) 。通过对一个包d s 字段的不同标 记，以及基于d s 字段的处理，能够产生一些不同的服务级别。因此，区分业务 本质上是一种相对优先级策略。 为了让一个客户从他的i s p 那里得到区分业务服务，客户必须与他的i s p 签定一个服务级别合同( s l a ) 。一个s l a 从根本上明确了所支持的业务级别以及 在每个业务级别中所允许的通信量。它可以是静态的也可以是动态的。静态 s l a 定期地协商，如以月或按年为单位。动态s l a 的客户用某种信令协议( 如r s v p ) 中南丈学磺士学证论文 谤求辩要求懿藏务。客户霹澈搽记爨嚣豹蕊字爱良指定戆要褥赘戆骚务，镌霹 竣迁边缘路壶器根据耀分类来檬诡。 在i s p 的入口，包被分类、管制，魄可能被整形。在入口路由器，掰眷的分 炎、管制和整形规则均依据s l a 。遮嫩搡作所需要的缓冲空间也依据s l a 确定。 当一个包从一个域( d o 腿i n ) 进入另外一个域时，它的d s 字段可能会被重新标记， 这由两个域之间的s l a 确定。运用分裳、管制、整形和调度策略，可以提供多种 业务。注意，区分业务只定义了d s 字段和p l 仍，究竟会提供什么样的服务由i s p 决定。 区分业务模型完全不同于集成溅渡努模型，它的具有以下优点( 1 ) 伸缩憾较 好。d s 字段只是规定了有限数量鲍娩务缀剃，状态信息的数量正比于业务级涮， 露不是泷的数量。( ：) 便于实觋。只在耀络麴逑爨上方需要复杂筠分类、栋记、 簧澍露整形操终。i p 孩心跨壹嚣只鬟溪安瑷行为聚集( 8 趵魏分类，毽诧实璞秘 部署区分业务毫汔较容易。 1 1 2 2 与集成业务模型的互道 很有可能的是，集成业务模型念圆为伸缩性的问题而无法在w a n 上使用。将 来区分业务模型( 配合m p l s ) ，在q o s 方面很可能占有主导地位。而事实上，很 移i s p 期待区分业务模型能够满足所榭他们的q o s 需求。而与此相反的是，鬃成 业务模型能够在企业网中实施，很多企她的联网产品中都己经或即将集成巢种獠 度的集成业务能力。如果w a n 用的是隧分业务模型，而l a n 用的是集成业务和区 别妲务模型的混合形式，那么当发邀赣釉接收者之闯的通路同时需要l a n 和w a k 对，如每方能够保证端至端的q o s 瞩? l 鞭建议了嚣魏互搽终方式。秘方法是将集藏鲎务覆盖在区分监务瓣上， 於￥p 售令完全透鹱囊亟透过区分照务湖。经予两静溺终边缘豹设备楚溪r s ￥p 滚惑， 并且根据区分业务两络中合适的爨漾的可翔健提供许可控剃。另乡 一种方法怒简 单的并行处理。区分业务网中的每个带点可能也是具有r s v p 功能的。采取一黩 策略来决定哪些包用r s v p ，哪些用区分业务处理。这种模型可能适用于小型网 络。 1 1 3 多协议标记交换( 仲l s ) 多协议标记交换( m p l s ) 的动机楚用一个固定长度的标签决定包的处理。m p l s 是一个前向转发策略，由c i s c o 的栋记路幽发展两来。在o s i 的7 层模型中，它 谯予筵2 层萃羹第3 层之闻。 l 。1 3 i 箍疆s 奔绥 每个挺p l s 都有一个头。这个头彀据一个2 0 b i t 的标签，个3 b i t 豹业务级 中南大学硕士学位论文 别( c o s ) 字段，一个1 b i t 的标签栈指示器和一个8 b “的t t l 字段。肝l s 头的封 装是在链路层头和网络传输层头之间。一个具有肝l s 能力的路由器( 标记交换路 由器l s r ) ，在转发包时只检查标签。网络协议可以是i p 或其他类型的，这也是 叫多协议标记路由的原因。 m p l s 需要一个分配标签。建立标签交换通道( l s p ) 的协议。是创建一个普通 的标签分配协议( l d p ) ，或是扩展r s v p 提供此功能是一个还在争论的问题。一个 l s p 与一个a t m 虚链路相似，从发送端到接收端是单向的。仲l sl s r 用此协议协 商每个标签的涵义，规定如何处理来自对等端的一个特定标签的包。l s p 的建立 可以是控制驱动的，即由象路由更新那样的控制流触发。或者是数据驱动的，即 由一个流请求或一个流量的中继触发。在m p l s 中，一个流量交易是那些具有相 同服务级别的，能够放到一个l s p 的流的聚集。两个路由器之间的l s p 可以与 l 3 的逐跳路由一样，或发送端l s r 能够为l s p 规定一个显式路由( 既p l i c i t r o u t e ) 。能够建立显式路由是m p l s 晟有用的特点之一。用标签索引的转发表的 构造是标签分配的结果。每个转发表入口规定了如何处理运载索引标签的包。 分类和路由包是在一个m p l s 作用域的入口l s r 处。当一个l s r 收到一个标 记了的包时，它将用标签作为索引查找转发表。这比i p 路由时查找匹配、解析 路由表的处理要快些。由转发表的入口决定处理包的方式。进入时的标签被离开 时的标签所替代，并且包被交换到下一l s r 。标记交换的过程与a t m 的v c i v p i 处理类似。在一个m p l s 域的内部，包转发、分类和q o s 服务均由标签和c o s 域 确定。这使得核心l s r 很简单。在一个包离开某m p l s 域时，删除它的m p l s 标签。 m p l sl s p 也能够当作隧道( t u n n e l ) 用。当一个包进入一个隧道的起点时， 它的通道已经完全确定了，包将出现在隧道的终点处。它的通道完全由入口处分 配给它的标签决定，没有必要列举出隧道中所有的路由器。因此，它的效率比其 他隧道机制都要高。 m p l s 的优点是它能够提供更快的包分类和转发速度以及一种有效的隧道机 制。 1 1 3 2m p l s 与区分业务模型 m p l s 可以与区分业务用在一起来提供q o s 。在这样的一种结构中，首先配置 每个入口一出口对之间的l s p 。对于l s p ( l s r l 一l s r 2 ) 和l s p ( l s r 2 一l s r l ) ，它们 之间的l s r 不需要互相彼此相反。很有可能对于每个入口一出口对，为每个流量 类型创建一个分开的l s p 。为了减少l s p 的数量，到某一出口的所有来自入口路 由器的l s p 合并到一个树池( s i n k t r e e ) 。也可能用一个树池传送不同流量类型的 包，并且用c o s 比特区分包的类型。在这种结构中，随着正在传送的流量数的增 加，在每个l s p 或树池的流量数也会增加。但所需要的l s p 的数目或树池数不会 增加。因此这种体系结构是可伸缩的。 中南大学硕士学位论文 在路由器中的操作与前面提到的基于d s 字段的操作基本上是一样的。在对 一个数据包进行处理时有3 点不同之处：( 1 ) 在i s p 网络的入口处，除了那些基 于d s 字段的处理外，还要给包中插入一个肝l s 头；( 2 ) 核心路由器处理包是基 于它们的标签和c o s 字段，而不是它们的d s 字段；( 3 ) 在出口处，除非配置了外 部域l s p ，否则删除肝l s 头。 注意在这种策略里，肝l s 的作用限制在使用咿l s 的i s p 内。对于其他的i s p ， 一个特定的i s p 的体系结构是基于d s 字段还是肝l s ，是完全透明的。因此，基 于d s 字段的体系结构和基于肝l s 的体系结构能够很容易地互操作。 1 1 4 流量工程 从根本上讲，在网络负载严重时，集成型业务模型和区分业务模型等o o s 策略提供的是性能的平稳下降。当通信负载比较轻时，集成业务和最佳效果业务 几乎没什么差别。因此，为什么不在第一步就设法避免拥塞昵? 这就是流量工程 的动机。导致网络拥塞的原因可能会是网络资源不足或通信分布不均匀。在前一 种情况下，所有路由器和链路都会过载，唯一的解决办法是升级基础设施，提供 更多的资源。在第二种情况下，网络的一些地方过载而其他地方的负载却较轻。 现在的动态路由协议r i p ，o s p f 和i s i s 都会导致不均匀的通信分布，因为它 们总是选择最短路径转发包。结果是，在两个结点之间顺着最短路径上的路由器 和链路可能发生了拥塞，而沿较长路径的路由器和链路却是空闲的。o s p f 的等 价多路径( e c 咿) 选项，以及最近的i s i s ，在给多个最短路径分配负载时是有 用的。但是，如果只有一条最短路径，e c m p 就无能为力了。对于简单网络，可 以让网络管理员手工配置链路的代价，均匀地分配流量是可以的。但对于复杂网 络，这几乎不可能。 流量工程就是安排传输流如何通过网络，以避免不均匀地使用网络而导致拥 塞的过程。为使流量工程自动化，约束寻径是一种重要的工具。因为在避免拥塞 和提供良好的性能方面，流量工程其实是对区分业务模型的补充。 1 1 5 约束路由 约束路由( c o n s t r a i n t e db a s e dr o u t i n g ) 用来计算受到多种约束时的路由。 1 1 5 1 约束路由介绍 约束路由是从q o s 路由发展而来的。对于给定q o s 请求的一个流或一个流的 聚集，q o s 寻径返回的路由能够最大限度地满足o o s 需求。约束路由扩展了q o s 路由，考虑管制等其他约束，约束路由的目标是选择能够满足特定q o s 需求的路 由和提高网络的资源利用率。 中南大学硕士学位论文 当决定一个路由时，约束路由不仅涉及网络的拓扑结构。而且还包括流提出 的需求、链路资源可用性以及网络管理员规定的一些可能的管制。因此，约束路 由可能会找到一条较长和较轻负载的路径，这条路径优于重负载的最短路径。网 络流量会因此而更均匀一些。要想实现约束寻径，路由器需要计算新链路的状态 信息，再根据这些状态信息计算路由。 1 1 5 2 约束路由与其他q o s 机制的关系 ( 1 ) 集成业务模型：r s v p 与约束路由是相互独立却互为补充的。约束路由狭 定r s v p 消息的通路，但并不预留资源。r s v p 预留资源但有赖于约束路由或动态 路由决定通路。 ( 2 ) 区分业务模型：约束路由为流选择最优路由，因此最大限度地保证了 q o s 。约束路由不是要取代区分业务模型，而是帮助它更好的传送。 ( 3 ) m p l s ：从理论上说，二者是互斥独立的，因为m p l s 是种前向转发策略， 而约束路由是一种路由策略。约束路由基于资源和拓扑信息决定两个节点之间的 路由，有没有肝l s 都可以。舻l s 用标签分配协议建立l s p ，而不关心路由是由 约束路由，还是动态路由确定的。 1 2q o s 路由 q o s 路由和基于0 0 s 的传输调度是当前i n t s e r v 领域研究的热点问题”“。q o s 路由需要在信息传输之前在源节点和目的节点之间寻找符合q o s 需求的传输路 径，并通过r s v p 协议为其预留资源“”。在i n t s e r v r s v p 模型中的q o s 路由算法 的研究中，多个限制条件下的q o s 路由算法、q o s 组播路由算法、q o s 路由实现 及性能评测等问题难度较大，需要更深入地研究”“”1 。 q o s 路由是一个十分复杂的问题。这是因为首先，网络电话和分布式游戏等 分布式应用在延迟、延迟抖动、丢失率和带宽等方面有许多不同的q o s 限制。多 个限制经常使得路由问题更加复杂。例如，寻找一条具有两个独立路径限制的可 行路径是n p 难的。其次，将来的集成服务网很可能既要传输q o s 数据流叉要传 输尽力而为的数据，这就使得性能优化问题更加复杂。第三，由于瞬间的负载波 动使得网络状态是动态变化的。不断增长的网络大小使得在动态环境中收集晟新 的状态信息日益困难。如果使用过时的状态信息，q o s 路由算法的性能将被严重 降低。为了进行q o s 路由，路由器需要得到可用网络资源的信息。 1 2 1 网络模型 网络的拓扑结构和资源容量可以抽象为一个赋权图g ( v ，e ) ，其中v = ( v 。 v ：，v 。) 是由代表路由器的所有交换节点组成的集合，e = ( e 。，b ，e 。) 是 中南大学硕士学位论文 所有连接路由器的链路的集合。如果传输线路是对称的，则对应的边是无向的。 因为对称线路对两个方向上的数据都有同样的特性。对于大多数实际的网络而 言，其链路般都是非对称的，因而其每一条链路对应于模型中就是两条有向的 加权边。每条链路都有一个对应于相关q o s 参数的状态。而每一个节点也有相 应的状态，它可以单独表示出来，或者也可以把它折算到与节点相连的链路状态 中去。 1 2 2 网络状态信息 路由选择包含两个基本任务：收集状态信息并更新信息和基于收集的信息为 一新的请求寻找一条可行的路径。任何一个路由选择算法的性能直接依赖于前一 任务解决的好坏。网络状态信息可分为局部、全局和汇聚状态信息三类。 ( 1 ) 局部状态信息：假定每一节点保持其更新的局部状态，包括排队和传送 延迟、输出链路的剩余带宽、以及其它资源的可利用性。 ( 2 ) 全局状态信息：是所有节点局部状态信息的组合，每个节点通过链路状 态协议或距离矢量协议能够保持全局状态”，链路状态协议通过让各节点广播其 本地信息来确定网络的拓扑结构和各链路的状态。距离矢量协议通过相邻节点定 期交换其距离矢量来取得并扩散全局信息。每一个节点保持的全局信息总是对现 有网络状态的一种近似。这是由于信息传输时延造成的。而时延的不可避免性表 明这种不确定性会随着网络规模的增加而不断扩大。 ( 3 ) 汇聚状态信息：因为任何物理设备的存储资源和处理能力都是有限的， 所以对全局信息的精确保存，会带来扩容性问题，于是降低全局信息的规模就变 得十分重要。这可以通过把一个具有层次性结构的大型网络的局部信息进行聚合 来完成，即把包含几个物理节点的组抽象为一个逻辑节点，而逻辑节点又可以进 一步聚合成更高一级的逻辑节点，如此反复下去。在聚合过程中，必须把下层节 点的网络度量特性聚集为本层逻辑节点的度量特性。这种过程是复杂的，而不同 的聚集方法对状态信息的影响也是一个开放性的问题。如i p 的内部网路由算法 o s p f 支持两层的聚合信息发布，而a t m 可支持任意多层的聚合。必须注意的是 聚合引入了额外的不确定性，并且不确定性会随着聚合层次的增大而变大。聚合 后的两个逻辑节点间的链路有可能对应于多条物理链路，从而带来一系列新的问 题。 1 2 3q o s 参数 对于路径p = a ，b ，c ，f ，g ，用d ( a ，b ) 表示对应链路( a ，b ) 的参数 则q o s 参数可以按性质可以分为以下三类“”： ( 1 ) 凸性o o s 参数。 中南大学硕士学位论文 如粜d ( a ，曲= 强i n ( d ( a ，b ) ，d ( b ，c ) ，d ( f ，g ) ) ，那么参数由传输域 邋巾稳撬颈决定，嚣此参数仅与黯径上豹蘩个糕颈豹q o s 参数毒关，如剩余豢宽、 裂众缓狰窆瀛、链爨速率等。 ( 2 ) 热往q o s 参数。 如果d ( a ，g ) = d ( a ib ) + d ( b ，c ) + + d ( f ，曲，那么参数由传输通道中的所 谢链路的特性共同来决定，如时延、时娥抖动、费用等。 ( 3 ) 乘性q o s 参数。 如果d ( a ，g ) = d ( a ，b ) $ d ( b ，c ) 书m d ( f ，g ) ，即参数为所有链路对应参数 的乘积，如可靠性等。通过取对数可将獭性q o s 参数转化为加性q o s 参数。 圈此，按参数豹性质q o s 路由可归髂为基本的两大类：路径优化问题，对应 加性参数；链路优化问题，对应凸性参数。 l 。2 。_ 重鼹交策瘩 路由计算可菇是集中计算，郄整个赚妇的诗算在个节点内进霉，也霹戬怒 分帮计算，即计算开销由沿着踌由的备个节点分担。总之，主要根据如何维护状 态信息和计算路由，q o s 路由策略通常分为以下3 种“。：源端路由、分布式路由 年口屡次路由。 ( 1 ) 源端路由” 每个节点都维护完整的全局信息，源端节点根据全局信息计算一条可行路 径，然詹沿着这条选出的路径发一个控制消息，通知中间节点其前驱和后继节点。 这擎争策路下，每个节点使用链路状态协议擞激全局状态。源端路由以集中方式计 舞黯出，可疆避免分布计算蟊蟾的一臻闽越，强燹镁捡铡蟊颈茨等。还能确保没 蠢锤繇( l o o pf r e e 熬鼹弪，劳显易于实糍、洋惩、调试移秀缀。勇努，为瓣决 藜黧黼完全的路壶计算闻蘧，集孛方式下瓣赌发式算法毙分毒方式更容易设诗。 德源端路由有以下几个缺点：首先是扩鼹瞧极差，为与不断交诧的网络参数( 鲡 带宽和时延) 保持一致，节点的全局状态必须频繁更新，这对大型网络来说开锩 徽犬。其次，为减少开销而降低更新频露以及更新消息本身一定的传播时延，使 樽节点只能提供不太精确的状态信息，绡粜q o s 路由可能发现不了实际存在的一 祭w 行路径1 。另外，源端节点的计算镦衙会很重，尤其是在组播和多约束条件 的q o s 路由情况下更是如此。 ( 2 ) 分布式路由” 瓷分布式路由选择中，路径通过分稚式计算褥出，控割信息在节煮闻交换， 缳存凌每一节点兹获态痿意鼓竣集莛象燃予懿径援索。太多鼗分毒式路出选择髯 中南大学硕士学位论文 法需要一距离矢量协议( 或一链路状态协议) ，以便使每一节点以距离矢量形式存 在的全局状态得以维持。在分布式路由选择中，路径计算分布在从源端到目的端 之间的节点上。因此，路由选择响应时间被缩短，算法更易扩展。为找到一可行 路径，并行地搜索多条路径成为可能，提高了成功机率。大多数存在的路由选择 算法要求每一个节点保持全局的网络状态( 距离矢量) ，基于此分段地做出路由选 择的决定。一些扩散式算法不要求保持任何全局状态，路由选择的决定和最优化 完全基于局部( 本地) 状态而进行。依赖于全局状态的分布式路由选择算法或多或 少会遇到与源端路由选择算法一样的问题。不需要任何全局状态的分布式路由选 择算法易于发送更多的消息。但它难以为n p 完全的路由选择问题设计有效的分 布式启发搜索，尤其在多点传送路由选择情况下更是如此，这主要是因为没有详 细的拓扑结构和链路状态信息。此外，当在不同节点的全局状态不一致时，循环 可能发生。当路由选择消息被一个节点第二次收到时，循环能轻易地检测到。然 而，循环通常使路由选择失败，因为距离矢量不能提供足够信息来改变路径。 ( 3 ) 层次路由。3 在层次路由选择中，节点簇集成组，组又簇集成更高一级的组，产生个多 级的层次。每一物理节点保持一聚集的全局状态。这个状态中包含同组中的节点 的详细状态。源端路由选择用来在那些作为逻辑节点表示组的节点上，寻找一可 行路径。随后沿该路径发送控制消息以建立连接。当由逻辑节点代表的组边界节 点收到消息后，它使用源端路由选择扩展路径至整个组。每个最底层的节点( 实 际的网络节点) 都维护一个汇聚的全局状态信息。汇聚的全局状态信息也是分层 的，每一层的信息包括本层中同属一个组的逻辑节点和逻辑链路的详细信息和其 他组的汇聚信息。在最上层的逻辑节点间采用源端路由找到一条可行逻辑路径， 然后一个控制消息沿着这条逻辑路径发送以建立真实的连接。当路径上逻辑节点 所代表的组边界节点( 即下层的逻辑节点) 收到消息后，则它在这个组内仍采用源 端路由扩展路径到该组的出口边界节点，递归这样的过程，直到真实的连接建立。 层次路由的可扩展性很好，因为每个节点只需维护部分的全局信息，大小是网络 详尽全局信息大小的对数。在每一层，逻辑节点依据汇聚信息直接采用源端路由， 因而层次路由继承了源端路由的优点，同时路由计算还是由路径上的许多节点共 同分担，因而还继承了分布计算的优点。层次路由是对大型网络而言最有前途的 路由策略。当然，由于汇聚信息引入了不精确性，层次路由在一些情况下可能导 致选路失败。这通常是由于逻辑节点通告的其自身的多个q o s 能力可能对应的不 是通过该逻辑节点的同一条路径。 1 2 5q o s 路由算法 q o s 路由可以分为两大类：单播和多播。这两类路由问题是密切相关的。在 很多情况下，多播路由可以视为单播路由的推广。 中南大学硕士学位论立 ( 1 ) 单播路由 对上面所述的两类q o s 参数都可以定义两种基本路由问题：最优化问题和性 能约束问题。最优化问题就是寻找对应q o