（通信与信息系统专业论文）约束路由及动态业务量疏导算法研究与实现.pdf

摘要 摘要 目前，在广域网上进行大规模实时视频传输已成为可能。对于传统的口网络， 实旌的路由策略集中于建立端到端的连接，并且一般只考虑一种服务数据结构。 而高速多媒体应用具有不同的性能需求诸如带宽、延迟、延迟抖动、损失率和必 经禁忌等。q o s 的概念被用来描述服务提供者和用户应用程序之间的性能约定， q o s 需求体现为一系列网络约束条件，如链路约束或端到端的加性约束等。q o s 路由是一种具有双重目标的路由机制：寻找满足约束条件的路径同时有效利用网 络资源，因此q o s 路由问题可归结为寻找路径在满足约束条件的同时优化某种特 定的代价函数。这类问题可以用i l p 建模求解，但随着网络规模的增加，求解时 间会变得无法接受，所以，本文集中研究如何利用启发式算法解决现有约束路由 中存在的问题。 本文第二章首先从多加性约束路由计算出发，研究并实现了多种k 路由算法， 分析对比性能，指出各种不同算法不同的应用场景和改进措施。必经点必经链路 约束是较常见的策略约束，目前尚未有成熟算法在保证低时间复杂度基础上达到 较好性能。本文提出了一种基于分割和迭代的必经点必经链路约束路由算法，仿 真结果表明该算法具有较好的性能且时间复杂度较低。在此基础之上，本文提出 了可支持多分离原则的多约束多分离路径算法，可有效支持计算节点分离、链路 分离和s r l g 分离等，比a p f 等传统算法的成功率提高很多，可用于大网络下的 多点失效问题如1 + 1 + s h a r e d 保护等场景。 本文第三章主要研究在基于p c e 环境下的域间多约束路由计算问题。传统的 基于p c e 的b r p c 算法在求解域问路由时过分追求源目之间的最优路径，而使得 算法易陷入路由陷阱。本文提出了一种新的求解域间路由的框架，将域间约束路 由计算分为正向约束传递过程和反向约束路由计算过程，从而有效的将约束合理 的分配到各域，该方法能有效解决多域中路由陷阱问题，提高域问路由成功率。 针对两层网络中动态业务批量到达的业务选路问题，本文在第四章提出了一 种基于业务持续时间的启发式算法。该算法在继承已有算法在均匀业务模型下低 阻塞率的优点基础之上，还有效的解决了在非均匀业务模型下传统算法高阻塞率 问题，仿真结果表明该算法能提高网络利用率、降低业务阻塞率。 关键词：多约束路由，q o s 路由，必经点必经链路，两层网络设计，动态业务 a b s t r a ( 了r a b s t r a c t t h ed e l i v e r yo fl a r g es c a l ed i g i t i z e dv i s u a li n f o r m a t i o no v e rw i d ea r c an e t w o r k si s n o wb e c o m i n gr e a l i s t i c f o rt r a d i t i o n a li pn e t w o r k , t h ec u r r e n o yd e p l o y e dr o u t i n g s c h e m ei sf o c u s e do nc o n s t r u c t i n ge n d - t o - e n dc o n n e c t i v i t yw h i c h u s u a l l ys u p p o r t so n l y o n et y p eo fd a t a g r a ms e r v i c e r 1 1 l ee m e r g i n gh i 曲s p e e dm u l t i m e d i aa p p l i c a t i o n sh a v e d i f f e r e n tp e r f o r m a n c er e q u i r e m e n t ss u c ha sb a n d w i d t h ，d e l a y , d e l a yj i t t e r , l o s sr a t e ， n o d e s l i n k si n c l u s i o na n dn o d e s l i n k se x c l u s i o ne t c t h en o t i o no fq u a l i t y - o f - s e r v i c e ( q o s ) h a sb e e np r o p o s e dt od e s c r i b et h eq u a l i t yd e f i n e dp e r f o r m a n c ec o n t r a c tb e t w e e n t h es e r v i c ep r o v i d e ra n dt h eu s e ra p p l i c a t i o n s t h eq o sr e q u i r e m e n to fac o n n e c t i o ni s g i v e n 勰as e to fc o n s t r a i n t s ，w h i c hc a nb el i n kc o n s t r a i n t so re n dt oe n da d d i t i v e c o n s t r a i n t s q o sr o u t i n gi so n es u c hm e c h a n i s mw i t ht w og o a l s ：s e l e c t i n gf e a s i b l ep a t h s t h a tm e e tq o sc o n s t r a i n t sa n dm a k i n ge f f i c i e n tu t i l i z a t i o no ft h en e t w o r kr e s o u r c e s s o t h eq o sr o u t i n gp r o b l e mc a nb ea t t r i b u t e dt ot h ec o n s t r u c t i o no fp a t hw h i c hs a t i s f i e st h e e n d - t o e n dq o sc o n s t r a i n t sa tt h es a m et i m eo p t i m i z e ss o m es p e c i a lc o s tf u n c t i o n t h i s k i n d o fp r o b l e mc a l lb es o l v e db yi l p ( i n t e g e rl i n e a rp r o g r a m m i n g ) u s i n g c p l e x 蝴p l h o w e v e r , t h er u n n i n gt i m eo fc p l e xw i l lb eu n a c c e p t a b l ew h e nt h e n e t w o r ks c a l eb e c o m ev e r yl a r g e s o ，i nt h i sp a p e r , w ew i l lf o c u so ns o l v i n gt h e p r o b l e mb yh e u r i s t i ca l g o r i t h m s i nc h a p t e rt w o ，w ef i r s tr e s e a r c ha n df o r m u l a t es e v e r a lks h o r t e s tp a t ha l g o r i t h m s ， t h e nw eg i v eo u ra t t e n t i o no nn o d e s l i n k si n c l u s i o nr o u t i n gp r o b l e m ，w h i c hi sav e r y i m p o r t a n ts t r a t e g yc o n s t r a i n t w ep r o p o s ea ne f f e c t i v ea l g o r i t h m ( n i r ) t os o l v et h e n o d e s l i n k si n c l u s i o na l g o r i t h m ，t h es i m u l a t i o nr e s u l t ss h o wt h a t0 1 1 1 a l g o r i t h mc a n a c h i e v eac o n s i d e r a b l ep e r f o r m a n c ew h e nt h et i m ec o m p l e x i t yi sv e r yl o w b a s eo nt h e r e s e a r c ha b o v e ，w eg i v ea na l g o r i t h mt os o l v i n gt h ed i s j o i n tp a t h sc o m p u t i n gp r o b l e m t h ea l g o r i t h mc a ns u p p o r tn o d ed i s j o i n t ，l i n kd i s j o i n ta n ds r l g d i s j o i n t i nc h a p t e rt h r e e ，w ef o c u so nt h ei n t e r - d o m a i nm u l t i c o n s t r a i nr o u t i n gp r o b l e m a n f r a m e w o r kf o rd i s t r i b u t e dp c ei n t e r - d o m a i ne n v i r o n m e n tm u l t i c o n s t r a i n r o u t i n g p r o b l e mw a sp r o p o s e d n et r a d i t i o n a lb r p ca l g o r i t h ma i m st og e tt h eo p t i m a lr e s u l t s ， a n dd on o tc o n s i d e rh o wt oa v o i dt of a l l i n gi n t ot h er o u t i n gt r a p ，w h i c hi sv e r yc o m m o n i l a b s t r a c t i nb r p c o u rm e t h o dg a ns o l v et h er o u t i n gt r a pe f f e c t i v eb yi n t r o d u c i n ga ne x t r a b a c k w a r di t e r a t i o np r o c e s s r o u t i n gf o rd y n a m i cd e m a n d si nt w ol a y e rn e t w o r ki sv e r yc r i t i c a lf o rt w ol a y e r n e t w o r kd e s i g n t h em o s te x i s t i n ga l g o r i t h m sf o c u so nt h eb e h a v i o ru n d e ru n i f o r m t r a f f i cm o d e l w h e l lt h et r a f f i cm o d e li sn o nu n i f o r m , t h ep e r f o r m a n c eo ft h e s e a l g o r i t h m sb e c a m ew o r s e ，a n dt h eb l o c k i n gp r o b a b i l i t yb e c o m e sh i g h t os o l v et h e p r o b l e m ，w ep r o p o s e ah o l d i n gt i m ea w a g ea l g o r i t h m s , w h i c hc a ni m p r o v et h e p e r f o r m a n c eu n d e r n o nu n i f o r mt r a f f i cm o d e l k e y w o r d s ：m u l t i - c o n s t r a i n tr o u t i n g , q o sr o u t i n g , n o d e l i n ki n c l u s i o n , t w o l e v e l n e t w o r kd e s i g n ，d y n a m i cd e m a n d s i i i 缩略词表 a g a p f a s b r b r p c g a g n m l s k d p k s p i l p i s i s l s r m c p 缩略词表 a u x i l i a r yg r a p h 辅助图 a c t i v ep a t hf i r s t工作路优先算法 a u t o n o m o u ss y s t e mb o u n d a r yr o u t e r自治域边界路由器 b a c k w a r d r e c u r s i v ep c e b a s e dc o m p u t a t i o n 基于p c e 的反向递归 计算方法 g e n e t i ca l g o r i t h m遗传算法 g e n e r a l i z e dm u l t i - p r o t o c o ll a b e ls w i t c h i n g 通用多协议标签协议 k d i s j o i n tp a t h k - 分离路算法 ks h o r t e s tp a t h k 路由算法 i n t e g e rl i n e a rp r o g r a m m i n g 整数线性规划 i n t e r m e d i a t es y s t e mt oi n t e r m e d i a t es y s t e m 中间系统到中间系统的 r o u t i n gp r o t o c o l路由协议 l a b e ls w i t c hr o u t e r标签交换路由器 m u l t i c o n s t r a i n e dp a t h 多约束路径 m p l s m u l f i p r o t o c o ll a b e ls w i t c h m 浓i ， m s t n i r n p c 0 s p f p c c p c e p c e p q o s m a x i m u mr e s o u r c eu t i l i z a t i o n m a x i m u m s i n g l e h o pt r a f f i c n o d ei n c l u s i o nr o u t i n g n o n p o l y n o m i a lc o m p l e t e o p e ns h o r t e s tp a t hf i r s t p a t hc o m p u t a t i o nc l i e n t s p a t hc o m p u t a t i o ne l e m e n t p c ec o m m u n i c a t i o np r o t o c o l q u a l i t yo fs e r v i c e v i 多协议标签交换 最大资源利用率 最大单跳业务量 含必经点约束路由算法 n p 完全问题 开放最短路径优先 路径计算客户 路径计算单元 p c e 通信协议 服务质量 缩略词表 o x c o p t i c a lc r o s sc o n n e c t o r s d h s r l g t e d v s p t w d m s y n c h r o n o u sd i g i t a lh i e r a r c h y s h a r e dr i s k l i n kg r o u p t r a f f i ce n g i n e e r i n gd a t a b a s e v i r t u a ls h o r t e s tp a t ht r e e w a v ed i v i s i o nm u l t i p l e x i n g v l i 光交叉连接器 同步数字体系 共享风险链路组 流量工程数据库 虚拟最短路径树 波分复用 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：罢。逛 醐：1 钳凡汨 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 翼。垒蜓 导师签名： 日期：矿7 年厂月善z 日 第一章绪论 第一章绪论 近年来随着i n t e r n e t 的发展和全球范围内的数据业务量的迅猛增长，对目前网 络传输设备的容量和网络带宽提出了更高的要求。w - o v e r - o p t i c a l n e t w o r k , 由于能 够极大地拓展现有的网络带宽，最大限度地提高线路利用率，并且在外围网络以 千兆以太网成为主流的情况下，能真正地实现无缝接入，从而成为未来网络发展的 方向。在这种高速路由器被智能核心光网络互联的i n t e r n e t 结构模式下，目前业界 的共识是，光网络的控制平面应该以i p m p l s 为中心，利用基于口的协议进行光 通道的动态配置和恢复。在实际情况中，为i p 流量工程开发的信令和路由机制可 以重新用于光网络中；同时必须考虑光网络特有的问题和需求，尤其是网络恢复 的问题，并由此引入g m p l s 的概念。 为支持迅猛增长的业务需求，对业务路由也提出了更高的q o s 要求。为了能 把p 的路由算法扩展到光网络中，i e t f 标准组织提出了带有光域扩展的o s p f 和 i s i s 草梨1 1 1 2 1 。这些扩展包括光链路参数以及与光网络相关的任何约束条件，使所 有节点( o x c 和路由器) 维持的拓扑和链路状态信息是一致的。 目前，已经有很多文献对约束路由进行了讨论，尤其是对于q o s 路由技术( 约 束路由是从q o s 路由引出的，可将q o s 要求转化为一系列对业务路由的约束) ，近 年来一直是研究热点。为此，i e t f 专门成立了q o s 路由工作组( i e t fp o l i c y f r a m e w o r kw o r k i n gg r o u p ) 来指导相关研究工作，并制定了一个q o s 路由的框架【3 j 。 除了路由算法、路由技术外，路由策略也是十分重要的，如在动态业务批量到达 的情况下合理安排业务路由使得阻塞率最低等。本章主要介绍多约束路由算法的 研究现状和多层网络中的业务的路由策略问题研究现状。 1 1 多0 0 s 路由问题概述 对于传统的数据网络，路由计算问题多集中于如何建立连接。路由协议只关 注一种网络数据结构如跳数、带宽、延迟、总代价等等，相应的数据流称为b e s t e f f o r t ( 尽力而为) 数据流。路由算法多遵循丌发式最短路径优先协议o s p f ( o p e n s h o r t e s tp a t hf i r s t ) ，如b e l l m a n f o r d 动态规划算法或d i j k s t r a 算法5 】【6 】。但随着 越来越丰富的业务出现，如多媒体应用、视频音频会议等，这些应用对服务质量 电子科技大学硕士学位论文 q o 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 要求包括带宽( b a n d w i d t h ) ，延迟( d e l a y ) ， 延迟抖动( d e l a yj i t t e r ) 及损失率( 1 0 s tr a t e ) 等。另外，网络鲁棒性、链路拥塞控制等指 标也可转化为链路的约束度量。一般情况下决策者不仅要求所建立的连接满足某 些q o s 约束，同时要求优化其中某个q o s 参数或约束值，如跳数( h o p ) 是最常 见的而且通常需要被优化( 而不仅仅是满足) 的指标，实际应用中我们把需要优 化的q o s 指标或约束度量称为代价参数，或简称代价( c o s t ) 【刀【8 】【9 】。q o s 概念反 映了网络服务提供者和用户之间一种数量及质量的约定。例如视频会议参加者的 响应时间，多媒体应用的质量等待。 q o s 路由或多约束路由是一种具备双重目标的路由机制：寻找满足约束条件 的连接同时有效利用网络资源【1 0 】【1 1 】【1 2 1 。实现第一个目标的连接( 一般包含路径或 树) 称为可行解，为了实现网络资源的有效利用，多数q o s 路由算法需要在满足 约束条件的同时，优化其中一个度量值，即前文提到的代价。链路的代价参数是 般能用某些经济指标量化的某些链路参数，一个连接的代价是指由该连接所有 链路的代价参数构成自变量的函数，因此可称之为代价函数。例如，如果链路代 价是延迟，则连接的代价函数是所有该连接的链路延迟之和。如果链路代价是带 宽，则连接的代价函数是所有该连接的链路带宽的最小值。q o s 优化算法的目标 是在所有的可行连接中寻找使代价函数得到优化的连接。 基于以下几个原因多约束路由问题是难解的。首先，目标节点对数据流的q o s 需求一般是多方面的。例如，视频会议对延迟时间及视频质量都有严格要求。而 寻找一条满足两个独立加性约束的路径的路由问题就是t c p c ( n p c o m p l e t e ) 问题， 除非其中一个约束条件是跳数【l3 1 。其次，如果不仅需要考虑目标节点的q o s 需求， 同时需要考虑所有连接所在节点或链路的q o s 需求【1 4 】【u 】，约束路由问题将变为结 合资源分配的路由问题，从而更加复杂，本文将在第四章讨论两层网络下的含有 资源分配的路由问题。最后，在实际情况下，网络是高度动态的，任何连接的建 立和释放，链路负载的变动，链路的失效和修复等等都会导致网络信息发生变化。 网络规模的不断扩大也使得实时网络信息的采集变得越来越困难。如果采用过时 的网络信息进行约束路由计算将会严重损害网络性能。虽然各种动态的，需要较 少网络信息的分布式算法已经提出，但是作为网络基本路由策略的静态路由算法 或源路由算法必须反映动态的及非确定的网络环境对路由策略的影响。 关于q o s 约束条件的物理背景的研究和资源预留、接纳控制等相关算法详见 2 第一章绪论 文献【1 6 】【1 刀f 1 8 】【1 9 1 。本文集中于q o s 问题的数学机制即多约束路由问题在不同应用中 的研究。 经过数学抽象，q o s 约束度量可分为加性、乘性、凸性和策略约束等，延迟 就属于典型的加性约束，端到端的延迟等于路径上各链路延迟之和；乘性约束表 现为端到端的约束度量值等于路径上各链路度量约束之积，如损失率等，但此类 约束可以通过取对数转化为加性约束；凸性约束指端到端的约束为路径各链路约 束值的最大者，如带宽等；策略约束指那些有业务使用者或决策者指定业务路由 需要满足某种特定策略，如必经某个链路或必经某个光口等。q o s 路由问题可定 义为：给定源节点s 和目的节点d ，一系列约束d ，以及需要优化的目标函数，要 求找出一条0 ，力间的路径满足约束条件或进一步满足代价优化函数。 路由由两个基本任务构成：第一是收集并刷新网络状态信息；第二是根据收 集的网络信息建立满足约束的连接。路由算法的性能直接取决于第一个任务的表 现。根据网络信息在网络中的存储方式，有以下三种路由算法：源路由算法、分 布式算法以及分层路由算法。源路由算法要求网络每个节点通过链路状态协议 【2 0 】【2 l 】或距离矢量协议 2 2 】 2 3 】保存全网信息并通过这些协议交换节点状态信息。链 路状态协议对网络所有其他节点广播本节点的状态信息使得每个节点都知道网络 的拓扑结构变化以及链路信息变化。距离状态协议周期性地在邻近节点中交换距 离矢量，每个距离矢量包括到每个可能目标节点的最优路径的相关信息。分布式 算法要求网络每个节点保存与其相邻的节点以及链路的信息，同样通过链路状态 协议或距离矢量协议向邻近节点传递本节点的相关网络信息。路由是通过逐点计 算( h o p b y h o p ) 进行的。分层路由协议一般针对大型网络，是通过某种网络信息的集 中从而达到缩减网络规模的目的【2 4 】 2 5 】【2 6 1 。首先将大型网络分成若干个组( g r o u p ) ， 每个组由若干在距离上比较接近的节点构成，有链路与两个以上组相连的节点称 为边界点，每组选出一个节点作为该组的代表并称为逻辑节点，组中其余节点称 为该逻辑节点的c h i l d r e n ，而该逻辑节点称为p a r e n t ，每个组还可以继续分层，每 个逻辑节点保存该层的网络信息，这样网络的规模得到缩减。在每一层运用源路 由算法求解最优路径并通过边界点形成最终路径。源路由算法 2 6 2 7 2 8 1 1 2 9 是三 种算法的基础，也是多约束路由算法的理论基础，它能保证寻找一条无环的路径， 而且对于一些n p c 问题，相对分布式算法和分层路由算法易于设计和实现，本文 主要讨论源路由算法，并集中于如何采用启发式算法到达满足各种约束下最优化 代价函数。 3 电子科技大学硕士学位论文 1 2 多o o s 路由研究现状 q o s 路由( 或称为多约束路由) 可分为单路径约束路径计算问题和多路径多 约束路径计算问题。而单路径的路由约束大致可分为加性约束、乘性约束、凸性 约束和策略约束等【3 0 】。加性约束是指从路径所经过的所有链路上的某个属性值之 和不能大于给定值，如端到端的时延不能超过多少；乘性约束是指路径所经过的 所有链路上某个属性值的乘积不能超过给定值，如路径的稳定性；凸性约束是指 路径所经过的每个链路上的某个属性值都不能超过给定值，如带宽；策略约束指 路径需要满足某种给定的策略使得路径便于被配置或管理，如必经点必经边等。 乘性约束可以通过取对数转化为加性约束，凸性约束可以通过在计算路径之前预 处理将那些不满足凸性约束的链路从网络中删除即可，所以近来研究热点均是多 加性约束。 而对于多路径的路由约束除了在多路径中的每条路径均可能含有单路径的约 束外，还有多路径之间的约束，如多路径之间的分离约束( 节点分离链路分离 s r l g 分离等) 以及多路径之间的跳数差或距离差约束等。 1 2 1 多约束单路径路由研究现状 多约束路由算法是涉及到两个或两个以上加性q o s 度量的优化或约束问题。 考虑网络由图g = ( 矿，d 表示，v 表示节点，e 表示链路，e 中的每一条链路o ，j f ) e 都与一个代价参数砸，_ ，) 以及k 个q o s 参数w k ( i ，) 相联系，k = 1 ，2 ，k 。在加性 约束中所有的参数都是非负的，加性的。给定k 个约束参数，仁，k = 1 ，2 ，k 。 要求找出一条联结源节点s 和目标节点t 的路径尸满足以下q o s 约束条件： ( 1 ) w k ( p ) = k ( f ，) c k ，k = 1 ，2 ，k 。 ( f ，j ) e p ( 2 ) 在满足( 1 ) 的所有可行路径上极小化d ( 尸) = ( i ，力，即寻找一条路径满 ，j ) e p 口 巴： t ( p ) = m i n d ( 尸) ，p 满足条件( 1 ) ) 。 k 2 的多约束问题属于n p 一完全仪p c o m p l e t e ) l h - 题_ 1 3 1 1 ，不能在多项式时间 内获得精确的解。这类问题经常使用各类启发式算法来处理，使它达到多项式时 间复杂度。为此，国内外也提出了多种解决n p 完全问题的算法，历史上经典算法 有： hc o m p ( h e u r i s t i cm u l t i c o n s t r a i n e do p t i m a lp a t h ) 算法，核心思想为：把所 4 第一章绪论 有约束用一个非线性c o s t 函数表示，用遗传算法求这个函数和最小，从而获得解； 有限粒度启发( 1 i m i t e dg r a n u l a r i t yh e u r i s t i c ) 算法( 其思想是使用有界的有限 范围来近似度量，把原始的n p 完全问题简化为用扩展的d i j k s t r a 或b e l l m a n - f o r d 算法能在多项式时间能解决的简单问题) 和有限路径启发( t h el i m i t e dp a t h h e u r i s t i c ) 算澍3 2 】( 其思想是为每个节点维持有限数目的最优路径) 。 近期国内外业界优秀研究学者也提出了很多算法，如： 文献【3 3 】提出f p t a s ( f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e s ) 算法，解决 了k = 2 加性约束的路由问题m c p ( m u l t i c o n s t r a i n e dp a t hp r o b l e m ) 。该文献的主要 贡献有：1 ) 提出一种可以运用于跳到跳路由协议的o ( k m + n l o g n ) 时间忌近似算 法；2 ) 提出两种有略微区别的f t a s 算法，时间复杂度分别为为d ( m ( ! ) 肛1 ) 、 占 o ( n l o g n + 坍( 兰) n ) ，与已有的算法的时间复杂度相当。 占 文献【蚓提出一种遗传算法g a ( g e n e t i ea l g o r i t h m ) 来解决多约束路由问题，这 里主要涉及的是加性约束路由问题m c p 。仿真表明，该算法能高机率的找到满足 条件的路径。 从以上文献可以看出，目前业界对于多加性约束研究较多，但对于策略约束 研究较少，如必经点或必经链路的处理等。 1 2 2 多约束分离路由研究现状 多约束路由问题一个较少涉及的方向是链路分离的多约束路径。随着m p l s 和g m p l s 网络的实施，网络规模的不断扩大，如果决策者只在源节点和目标节点 之间确定一条路径，由节点或链路失效引起的网络失败将可能导致连接的失败。 因此，建立源节点和目的节点之间的分离路径对网络容错性和鲁棒性十分重要。 为了应付不同的失效，需要在源目间建立不同分离原则的分离路，节点分离路径 可应付节点失效但不能应付链路失效。将共享相同失效风险的链路组合起来形成 一个共享风险链路组s r l g 。利用s r l g 的概念，可以统一链路失效和节点失效。 文献【3 5 】【3 6 】刚研究了如何计算一对链路分离或节点分离的路径同时使得两条路 径的总的代价最小。文献【3 8 】研究了计算一对s r l g 分离路径问题。为了解决在多 失效场景下能保证业务不中断，一对分离路径已不能应付，此时需要提前配置好 多分离路径。本文在文献【3 8 】的基础上提出了可支持节点链路s r l g 分离的多分离 路径计算方法，详细描述将在第二章中呈现。 5 电子科技大学硕士学位论文 1 2 3 两层网络选路算法研究现状 w d m 技术在光网络中，尤其在光传送网中已经得到了广泛应用。目前，单个 波长的带宽可以达到g 比特级，例如0 c - 4 8 、o c - 1 9 2 和o c - 7 6 8 ( 对应带宽分别 为2 5 g b p s 、1 0 g b p s 和4 0 g b p s ) 。而实际运营网络中上层业务的带宽请求往往小于 一个波长所提供的带宽，例如o c - 1 、0 c - 3 、0 c - 1 2 ( 对应带宽分别为5 1 8 4 m b p s 、 1 5 5 5 2 m b p s 和6 2 2 0 8 m b p s ) 。两者相对比可以发现w d m 网络中波长的带宽是粗 粒度，而上层实际业务的带宽则是细粒度，二者之间存在明显的带宽差异。显然， 如果为每个上层业务提供一个波长，资源利用率很低且不经济；同时由于光纤中 波长数目的限制、网络节点中光收发器数目的限制( 一条光路的建立需要在其两 个终点各占用一个光收发器) 等，也不可能为每个业务连接建立端到端的独立光 路连接。因此在s d ho v e i w d m 的两层网络中，为了有效地容纳上层低速业务， 需要引入业务量疏导( t r a f f i cg r o o m i n g ) 技术，将多个低速业务进行汇聚，使其 共用w d m 光网络中的高速的波长通道，从而提高网络的资源利用率并降低网络 建设成本和运营成本，提高网络性能。各种网络设计的技术均可看作是选路时的 一种策略，可认为是支持阻塞率约束的路由，只是这个路由是批量业务的路由计 算，而不再是单路径的路由计算。 在两层网络设计问题中，按照业务量的到达情况可以分为静态业务量疏导和 动态业务疏导两种。所谓静态业务量疏导是指业务批量到达并一直持续，优化目 标为在满足所有业务的带宽要求前提下最小化网络代价或者最大化吞吐量【3 9 1 。静 态业务量疏导实质上是一种特殊的网络全局优化设计问题，可以使用线性规划、 模拟退火、遗传算法【的】等优化设计手段加以解决。 动态业务量疏导是指单个业务到达时间不确定，且业务持续时间也不确定， 优化目标为最小化网络中业务的阻塞率。文献 4 1 】 4 2 】 4 3 】研究了单个到达的动态 业务的启发式算法。此外，当前两层网络中还存在着批量业务动态到达的情况， 即在不确定时刻网络中同时到达多个业务，每个业务持续时间不定，业务到达符 合泊松过程。目前，还没有专门针对批量业务动态到达的两层网络设计方法的现 有文献。由于动态到达的批量业务既有静态业务的批量特性，同时也具有动态业 务的不确定性以及瞬时性，因此需要在现有静态动态业务量疏导方法的基础上进 行拓展，采用两层网络设计中常见的辅助图方式，综合考虑网络优化性能和算法 运行时间，找到合理有效的设计方法。 6 第一章绪论 1 3 本文主要贡献和内容安排 本文主要研究支持多q o s 的路由算法，包括多q o s 单路径计算、多q o s 分离 路计算以及选路策略的研究。在路由算法研究中，提出了必经点必经链路路由算、 多分离路计算等具有创新的启发式算法，有效的解决了必经约束和多分离路计算 问题；在选路策略的研究中，针对两层网络中最小化业务阻塞率的路由问题，提 出了结合业务生存时间和网络资源的路由策略，并对业务路由进行迭代处理等方 法达到降低阻塞率目的，并与业界主要算法进行比较，结果表明本文的方法性能 较好。本文的组织结构如下： 第一章主要介绍多q o s 路由问题概述和研究现状等； 第二章首先从多加性约束路由计算出发，给出了基于缸路由的多约束单路径 计算方法。必经点必经链路约束是较常见的策略约束，目前尚未有成熟算法在保 证低时间复杂度基础上达到较好性能。本文提出了一种基于分割和迭代的必经点 必经链路约束路由算法，仿真结果表明该算法具有较好的性能且时间复杂度较低。 在此基础之上，本文提出了可支持多分离原则的多约束多分离路径算法，有效支 持计算节点分离、链路分离和s r l g 分离等，仿真结果表明该算法较传统a p f 或 k s p 等有较大的性能或时间优势，可应用于大网络下的多点失效问题，如l + 1 + s h 矾 保护，用于预先在源目之间计算多条路径。 第三章提出了一种可用于分布式p c e 环境下的域间多约束路由算法。可有效 解决目前域间约束路由易陷入路由陷阱的问题。p c e 是一种功能实体，用于自治 域的路由计算。传统的基于p c e 的b r p c 算法过分追求源目之间的最优路径，各 自治域在计算域内路由时，盲目追求本域内最优而导致可能占用较多约束度量值 而导致后续的自治域由于不能找到满足约束的域内路径而导致端到端的路径计算 失败，陷入路由陷阱。本文提出了一种新的求解域问路由的框架，将域间约束路 由计算问题分为正向约束传递过程和反向约束路由计算过程，这种反向递归方法 可合理的将加性约束分配于各域内，从而避免自治域在计算域内路由时过多占用 约束值，结果表明该方法能有效解决域间多约束路由的路由陷阱问题，提高域问 路由成功率。 针对两层网络中动态业务批量到达的业务选路问题，本文在第四章提出了一 种基于业务持续时间的启发式算法。该算法在继承已有算法在均匀业务模型下低 阻塞率的优点基础之上，还有效的解决了在非均匀业务模型下传统算法高阻塞率 问题，大量仿真结果表明该算法能有效提高网络利用率、降低业务阻塞率。 7 电子科技大学硕士学位论文 第五章简单介绍了本文的方针平台框架，该框架将路由计算和资源处理相互 隔离，移植性较好，可以简单的将图算法应用到其他需要路由计算的地方如网络 规划等，对于网络规划或路由算法研究等应用领域的平台搭建提供了一定的参考 和借鉴作用。 第六章总结全文，并根据本文的研究结果提出了多q o s 路由算法一些看法和 展望。 第二章多约束路由算法研究 第二章多约束路由算法研究 2 1 单路径多约束路由计算 正如第一章中介绍的那样，目前约束路由的研究重点大部分集中在多加性约 束上，有大量优秀的理论成果和各种有效的启发式算法，但少见有文献提到必经 点必经链路的讨论。本章首先给出肛路由不同实现方式，缸路由是求解约束路由 的方式之一，后续章节中的加性约束的处理都是借助于本章讨论的肛路由算法， 本章的第二节给出了必经点必经链路的一种有效的启发式算法，并和一些典型算 法进行了对比测试。 2 1 1 缸路由算法研究与实现 2 1 1 1 珏路由算法原理研究 肛路由算法是路由算法中非常重要的一个问题，在很多时候都需要提供一个源 目节点对间的多条可用路径，这个时候就需要缸路由算法为我们计算源目节点对 间的多条路径。假定现有一个有向图g ( 儿日，其中，y 表示点的集合，e 表示边 的集合，源点j ，目的点d ，从s 到d 的所有路径集合p = - ( 墨，名) ，k 路由算法 就是指计算从s 到d 的k 条路径，令计算出的k 条最短路分别为鼻，罡最，则这后 条路需满足： ( 1 ) 曰，只必须是无环的路径； ( 2 ) 在路径集合p 中找不到代价比小的路径； ( 3 ) c o s t ( p i ) c o s t ( 罡) c o s t ( 置) 七路由的一种经典实现方式是y e n sk - s h o r t e s t p a t h 4 4 1 ，我们可以称之为y e n s k s p ，其基本流程如图2 1 所示： 9 电子科技大学硕士学位论文 图2 - 1y e n s k s p 的流程图 从图中可以看出，y e n sk s p 是预先计算出全网所有点到目的点的最短路径， 然后从源点开始向目的点进行摆动而拼凑路径，所以y e n sk s p 也被称为基于摆动 的肛路由，y e n sk s p 的优势是，当k 较大时可以较快得到多条路径，而缺点也是 很明显的： ( 1 ) 当k 较小时，预先计算出所有点到目的点的路径显然是不合理的，比如 k 为1 或2 时； ( 2 ) 当k 特别大时，每次摆动不一定都能找到可行路径，如成环等多种原因， 使得算法不停的在候选路径中摆动，而始终难以找到一条可行的路径，使得最终 1 0 第二章多约束路由算法研究 的求解时间变得特别长，难以接受。 所以，有很多针对y e n sk s p 的改进【4 5 1 ，如限制候选路径集的大小，限制摆次 数等，但这些难从根本上解决这种矗路由算法的缺陷。 另一种计算缸路由的方法是利用最短路算法计算出一条路径，然后再禁忌掉 这条路径上的某些链路得到次短路，依次进行下去，直到计算出k 条，我们称这 种方法为s p k s p ( s h o r t e s tp a t hb a s e dk s p ，基于最短路的珏路由) 。s p k s p 的流 程如图2 2 所示。 图2 - 2s p - k s p 的总体流程图 在图2 2 中，g e l l p a t h s 函数用于根据一条路径产生更多可行路径，而且这些新 计算得到的可行路径不会与已有的路径重复。很显然，k 条路径中最短的一条路( 即 两点间的最短路) 可以利用最短路算法如d i j k s t r a 算法【5 】计算得到，