（电路与系统专业论文）ip+over+wdm网络的多层生存性研究.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 随着i p 业务的迅猛发展及w d m 波分复用信道数的增加，单信道速率由2 5 g b i v s 到 1 0 g b i t s 再到4 0 g b i v s 不断的提高，这使得在i po v e rw d m 网络中，一旦网络故障导致传 输业务失效，将造成巨大的经济损失，因此i po v e rw d m 网络生存性问题就成为人们日益 关注的重要问题。对i p 层和w d m 层单层生存性研究已经有很多年，众所周知，i p 层是 通过动态选择路由方式再加t c p 的可靠传输机制来实现保护机制的，这就使得t c p i p 网 络具有很好的生存性，而且i p 层能够恢复的操作粒度比较小，能够恢复多故障业务，但是 i p 层的生存性也有恢复时间太长，没有办法满足实时业务需求的缺点：而w d m 层生存性 具有高速、高效、简单的优点，但是它不能处理所有的故障，而且有些故障在光层是无法 检测到。单层生存性的这些优缺点就使得对联合生存性研究很有必要。 本文首先指出生存性研究的目的和意义，并对生存性的基本概念进行简单介绍；其次 论述了i po v e rw d m 网络发展的3 种模型：重叠模型、扩张模型和对等模型，而本文关于 生存性的研究都是基于对等模型的；再其次研究了i po v e rw d m 网络的单层生存性问题， 分析了i p 层、w d m 层单层生存性的优缺点，继而指出了研究联合生存性问题的必要性， 并对其进行具体的分析；接下来第三章论述了现有的一种i po v e rw d m 网络的有效保护机 制动态分配可保证带宽的恢复路径，并给出进行路由分配的联合路由算法基于跳 数的联合路由算法( h i r a ：h o p b a s e di n t e g r a t e dr o u t i n g a l g o r i t h m ) ；最后是本文的重点，提 出一种基于多纤分层图模型的算法：最小跳数最大容量算法。之前关于联合路由算法的研 究大都没有采用分层的概念，而本章在多纤分层图模型基础上来研究最小跳数最大容量算 法，可一次性解决选路和带宽分配问题，并将最小跳数最大容量算法和目前较为先进的 h i r a 算法就连接阻塞率和带宽阻塞率两个指标进行比较，分析最小跳数最大容量算法负 载较大时的优越性。 关键字：联合生存性，多纤分层图模型，i po v e rw d m a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi ps e r v i c ea n d t h ei n c r e a s ei nt h en u m b e ro fw d mc h a n n e l s ， t h es i n g l ec h a n n e lr a t eh a sb e e nr a i s e df r o m2 5 g b i t st o10 g b i t sa n d t o4 0 g b i t sg r a d u a l l y i n i po v e rw d mn e t w o r k s ，i fs o m e t h i n gi sw r o n g 谢t hn e t w o r k s ，w h i c hw i l lm a k eh u g el o s s ，s o m o r ea n dm o r ep e o p l ep a ya t t e n t i o nt ot h es u r v i v a b i l i t yo fi po v e rw d m n e t w o r k s t h e s u r v i v a b i l i t yo fi pl a y e ra n dw d ml a y e rh a sb e e ns t u d i e df o rm a n yy e a r s i pl a y e ra c h i e v e s p r o t e c t i o ns c h e m eb yr e m u t i n gd y n a m i c a l l ya d d i n gt c p r e l i a b l et r a n s m i s s i o nm e c h a n i s m ， w h i c hm a k e st c p i pn e t w o r kp o s s e s sg o o ds u r v i v a b i l i t y b u ti tt a k e sm u c hm o r et i m ef o ri pt o r e c o v e r yf a i l u r e s ，s oi tc a l l tm e e tt h ed e m a n do f r e a l t i m es e r v i c e w h i l ew d m l a y e rh a v es o m e v i r t u e s ，f o re x a m p l e ：h i g h s p e e d ，h i g he f f i c i e n c ya n ds i m p l e ，b u ti t c a n td e a lw i t ha l lf a i l u r e s ， a n dd e t e c ts o m ef a i l u r e s t h es h o r t c o m i n g so fs i n g l e - l a y e rm a k e si n t e g r a t e ds u r v i v a b i l i t y r e s e a r c hn e c e s s a r y f i r s t l y , t h i sp a p e rd e s c r i b e st h ea i ma n dm e a n i n ga b o u t t h er e s e a r c ho ns u r v i v a b i l i t y , a n d a l s oi n t r o d u c e st h eb a s i cc o n c e p t so fs u r v i v a b i l i t y s e c o n d l y , i td i s c u s s e st h r e ek i n d so fm o d e lo f i po v e rw d m n e t w o r k s d e v e l o p m e n t ：o v e r l a ym o d e l ，a u g m e n t e dm o d e la n dp e e rm o d e l ，a n d o u rr e s e a r c ho ns u r v i v a b i l i t yi sb a s e do np e e rm o d e li n t h i sp a p e r n e x t ，i ti n t r o d u c e st h e s u r v i v a b i l i t yo fi pl a y e ra n dw d ml a y e r , a n da n a l y z e st h e i rv i r t u e sa n ds h o r t c o m i n g s ，a n dt h e n b r i n g su pt h ei n t e g r a t e ds u r v i v a b i l i t ya n da n a l y z e si ts p e c i f i c a l l y i nc h a p t e r3 ，i td i s c u s s e sa n e f f i c i e n tp r o t e c t i o ns c h e m et od y n a m i c a l l ya l l o c a t er e s t o r a b l eb a n d w i d t h g u a r a n t e e dp a t h si n i n t e g r a t e di po v e rw d mn e t w o r k s ，a n dg i v e st h ei n t e g r a t e dr o u t i n ga l g o r i t h m ，t h a ti sh o p b a s e d i n t e g r a t e dr o u t i n ga l g o r i t h m ( h i r a ) t h ef i n a lc h a p t e ri st h em o s ti m p o r t a n tp a r ti nt h i sp a p e r , i t p r o p o s e st h ea l g o r i t h mt h a ti sb a s e do nm u l t i - f i b e rl a y e r e dg r a p hm o d e l ：m i n i m u mh o pa n d m a x i m u mc a p a c i t ya l g o r i t h m m a n yr e s e a r c h e so ni n t e g r a t e da l g o r i t h ma r en o to nt h eb a s i so f l a y e r e dm o d e lb e f o r e ，w h i l et h i sc h a p t e rs t u d i e s m i n i m u mh o pa n dm a x i m u mc a p a c i t y a l g o r i t h m ( m h m c a ) t h a ti sb a s e do nm u l t i f i b e rl a y e r e dg r a p hm o d e l ，w h i c hc a nd e a l w i t h r o u t i n ga n dd i s t r i b u t i n gb a n dt o g e t h e r f i n a l l yi tc o m p a r e sm h m c a w i t hh i r ai nc o n n e c t i o n b l o c k i n gp r o b a b i l i t ya n db a n db l o c k i n gp r o b a b i l i t y , a n dt h e na n a l y z e st h ev i r t u eo f m h m c aa s l o a db e c o m e sh i g h e r k e y w o r d s ：i n t e g r a t e ds u r v i v a b i l i t y , m u l t i f i b e rl a y e r e dg r a p hm o d e l ，i po v e rw d m i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的如何贡献均己在论文中作了明确的说明并表示了谢意。 研究生签名：拯虹日期：掣 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所 送交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保 存论文。本人电子文档的内容和纸质论文的内容相致。除了保密期内的保 密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部 分内容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：秘龟虹 导师签名： 醐：严， 南京邮电大学硕士研究生学位论文第三章i po v c ! rw d m 网的一种有效动态保护机制 业务请求是从源点s n 宿点d ，实线和虚线分别代表物理链路和逻辑链路。s r a 寻路要 求有两个步骤。步骤l ，s r a 试图在逻辑链路上为业务请求寻路，而且这条路径仅有逻辑链 路( 如路径l ：1 2 3 - 4 5 ) 组成。如果步骤1 失败，s 与d 之间的直接光通道需要在步骤2 建立( 如 路径2 ：8 - 9 1 0 1 1 ) 。这种方法有两个缺点：第一、步骤1 找到的路径可能非常长，这样可能 消耗掉大量的带宽及光电光转换的次数。第二、步骤2 在物理拓扑上建立光通道然后再在 此光通道上建立l s p ，随着网络负载的加重，物理拓扑上的资源被逐渐耗尽，这将导致下 面到来的连接请求被拒绝。有时由于波长连续的制约，不可能打开新的波长，结果就是业 务请求被阻塞。本章提到的联合路由算法( h i r a ) 很大程度上克服了上述的限制，提高了网 络资源利用率。这种算法基于成本度量，决定了在己存在光通道，打开的新光通道上，或 者在逻辑链路和新建额外的光通道上为业务请求进行寻路( 如路径3 ：6 7 ) 。注意在路径3 中， 边6 对应物理链路( 导致新光通道的建立) ，而边7 对应逻辑链路( 已存在光通道) 。由i r a 得到 的路径可能更短，有效的利用了网络资源并且提高了业务请求被接受的概率。 3 3 问题的定义及算法的提出 3 3 1 问题的定义 我们假设o x c 没有波长变换的能力，故障是单链路故障，业务请求是一次到达而未来 的业务请求未知，业务请求的入节点为s ，出节点为d ，业务请求带宽为b 。对每个请求， 工作路径和它链路不相连的保护路径都能被找到。如果没有足够的带宽满足工作路径或者 是它的保护路径，业务请求被阻塞。如果业务请求被接受，带宽b 预留给工作路径。而对 于保护路径所需的带宽是由当前所服务的业务请求所达到的共享程度决定的。现在解释如 何计算保护路径所需的带宽。 符号定义： p ，：承载着一些逻辑链路即一些l s p s 的物理链路 勿。：承载着一些l s p s 的逻辑链路f ：网络中物理链路的数目 6 ) ：工作路径为p ，保护路径为境的所有的业务连接请求中慨上所需要的保护容量 6 ，( m 调整当前的请求后，工作路径为p ，而保护路径为慨的所有的业务连接请求中识 上所需要的保护容量 m a x ( i ) ：l p , 上所需要的保护容量 1 9 南京邮电大学硕士研究生学位论文 第三章i po v e rw d m 网的一种有效动态保护机制 m a x ( i ) ：调整当前的请求后，城上所需要的保护容量 b o ( i ) ：调整当前的业务请求后，它的带宽最大值为b ，概所需要的额外的保护容量 我们有： m a x ( i ) = m a x b j ( i ) ，l n ( 3 1 ) m a x ( i ) = m a x j ( f ) 1 j n ( 3 2 ) 6 口( f ) = m a x ( f ) - m a x ( i )( 3 - 3 ) 对于网络中的每条p b ，所对应的每条玩都有一个表格来记录6 ，( f ) ，概所需的保护容 量是表格中的最大值。基本思想是一旦物理链路故障，逻辑链路要保证用它的保护路径恢 复该逻辑链路上的所有工作业务。在本章中，我们采用全保护，也就意味着所有被工作路 径占用的带宽需要为它的保护路径预留。换句话说，所有的失效业务都能够被恢复。如果 仅一小部分工作业务失效，性能会更好。 3 3 2 算法的提出 下面来阐述h i r a 联合路由算法。h i r a 联合路由算法的目的是工作l s p s 和它的保护 l s p s 所用的已存在光通路和新建光通路的物理跳数最小。这样做，可以减少资源的利用， 提高了业务请求被接受的概率。 符号定义： n t ：一条路径所用的己存在逻辑链路的数目 力。：一条路径所用的新物理链路数目 1 4 , ( f ) ：逻辑链路f 的物理跳数 日。( ) ：物理链路的物理跳数，它恒等于1 k ：控制参数，定义物理链路和逻辑链路的相对重要性 对h i r a ，工作路径和保护路径的成本函数相同，如下。 n tn f p a t h c = 芝h t ( o + k z 砟( ) ( 3 4 ) i = 1 = l 由于保护共享，保护路径所经过的光通道上所需的额外带宽应小于b 。控制参数k 在 路径选择上决定物理链路与逻辑链路的相对优先权。当k 专0 0 时，h i r a 就像连续路由一样。 这种情况已存在的光通道优先被选择，可能导致更长的路径，结果是需要预留更多的带宽， 更多的光电光转换器。当kj 0 时，优先选择物理链路，这样，更多的光通路被建立，随 南京邮电大学硕士研究生学位论文第三章i po v c tw d m 网的一种有效动态保护机制 着负载的增加，资源利用率更低，更多的连接请求被阻塞。 对于本算法，物理链路和逻辑链路的权值是按不同的算法计算的。 对于物理链路： 勺= c 1 o ，荔量篡誓裹呈用 c 3 - 5 ， 勺 i ，物理链路被占用 、7 对于逻辑链路： 3 3 3 算法的步骤 勺2 马( f ) 上l 一，节点对f 栅之间存在朋条光通道 ( 3 6 ) ，” ， 节点对f 和，不存在光通道 步骤l 等待业务请求r ( s ，d ，b ) 如果r ( s ，d ，b ) 为业务连接请求，则转步骤2 如果r ( s ，d ，6 ) 业务连接释放请求，则转步骤4 步骤2 根据网络的虚拓扑结构及每个虚波长所对应的物理拓扑上的所占物理资源的 信息，找出从业务请求的源点到宿点且满足式( 3 4 ) 的一条工作路径( 链路的权值由式( 3 5 ) 、 ( 3 6 ) 求得) ，计算如果成功，转步骤3 ；否则，业务请求被阻塞，转步骤1 。 步骤3 找出一条和步骤2 所找的工作路径链路不相连且满足式( 3 4 ) 的保护路径，保护 路径的容量由式( 3 1 ) 决定，如果成功，转步骤1 ；否则，业务请求被阻塞。 步骤4 释放r ( s ，d ，b ) 所占用的资源。 3 4 性能研究及仿真 本章通过随意的一个网络仿真来评估这种算法，该网络由3 2 个节点，8 5 条双边链路， 每根光纤包含4 根波长组成。业务请求目的节点是在除了源节点之外的所有节点中随机选 择。全网所有源宿节点对间的业务强度都相同。业务到达成泊松分布，平均到达率为兄。 已经建立的l s p 的通道保持时间服从负指数分布，通道的平均保持时间为土。则网络的负 h 载用p = 兰来表示。这里设土：1 个单位时间， 弘 斗 不失一般性，认为土：1 s 。所以兄的大小 p 就表示了网络的负载。连接请求带宽在 1 ，1 0 _ 1 2 均匀分布，波长的最大容量假设为1 0 。对 2 i 南京邮电大学硕士研究生学位论文第三章1 9o v c rw d m 网的一种有效动态保护机制 于到达的每个请求需要为它建立l s p ，一旦l s p 建立请求被拒绝，就立即丢弃，无等待队列。 总的l s p 的连接请求次数为3 2 0 0 0 0 。 评价指标： 连接阻塞率：如果由于网络资源受限不能为某业务成功建立工作路由和保护路由，则 该连接请求被拒绝，连接阻塞率是被拒绝业务占总业务请求的比率。 仿真结果如图3 3 和图3 4 所示。 槲 悄 圜 辎 蜊 一k = i n f s m a l i - - , 0 - - k = 0 2 卜一k = i n f i n i t e _ 卜k = 5 力 - - 一k = 1 乙 7 岳二萝7 髟气么 匕豸歹 l ，r 、，j p p 二 一 _ 33 54 负载( e r l a n g s ) 图3 3h i r a 算法中连接阻塞率随负载变化情况 5 南京邮电大学硕士研究生学位论文第三章i po v e rw d m 网的一种有效动态保护机制 褂 稍 四 糙 蜊 s r a 夕 i h i r a 一彳多 7 ? 、 仿真结果分析： 33 54 负载( e d a n g s ) 图3 - 4s r a 算法和h i r a 算法的连接阻塞率比较 5 图3 - 3 表明了h i r a 算法在k = l 情况下，连接阻塞率的性能是最好的，当k 变大或变 小，阻塞率都会变高。这是因为，当k 比1 大时，优先选择逻辑链路，这种情况下，路径可 能因经过很多已存在的光通道而变长，结果需要更多带宽，这样对于后来的业务请求所预 留的带宽就相对减少，可能提高连接阻塞率。当k 比1 小时，新的物理波长链路被优先选择， 随着负载的增加，更多的光通路被建立，物理拓扑上的资源逐渐被耗尽，这样可能导致更 差的资源利用率，继而连接阻塞率也变高。 图3 - 4 表明了h i r a 算法相比与s r a 算法，连接阻塞率性能要好，理由与对图3 3 分析 同。 综合所述，由于h i r a 算法是按最短路由( 基于跳数) 的原则选路，所以其可以保证所 建立的l s p 所占的平均物理资源最小化，但是h i r a 算法没有采用分层的概念，它的路由选 择和带宽分配是分两步进行的，这样就使得网络资源不能够利用最优化，这在网络负载较 轻的情况下，该路由策略还可以取得很好的效果，但随着负载的急剧增加，也就是说在网 络负载较重的情况下，物理资源不能够优化利用，导致越来越多的连接请求被拒绝，最终 会导致网络的性能迅速恶化。 南京邮电大学硕士研究生学位论文 第三章i po v e rw d m 网的一种有效动态保护机制 3 5 小结 本章主要是对现有较为先进的算法一基于跳数的联合路由算法【1 0 】进行分析，仿真表 明h i r a 算法在k = 1 的情况下连接阻塞率的性能最好。而且该算法保证所建立的l s p 所占 的平均物理资源最小化，在网络负载较轻的情况下，该路由策略可以取得很好的效果：但 随着负载的急剧增加，由于h i r a 算法仍然遵照物理资源占用最小的原则选路，而且选路和 带宽分配分别进行，使得网络资源不能合理分配，所以会导致更多的连接请求被拒绝，最 终导致网络的性能急剧恶化。针对这一点下一章将提出基于多纤分层图模型的最小跳数最 大容量算法( m h m c a ) ，并将该算法与h i r a 算法就连接阻塞率和带宽阻塞率这两个指标进 行仿真分析，比较基于多纤分层图模型的最小跳数最大容量算法相比h i r a 算法在负载较高 时的优越性。 2 4 南京邮电大学硕士研究生学位论文第四章i po v e rw d m 网络的一种动态联合路由算法 第四章i po v e rw d m 网络的一种动态联合路由算法 4 1 概述 在w d m 光网络，我们必然会遇到一个问题就是如何有效地分配网络资源，而解决这 个问题通常有两种方法：静态和动态路由波长( r w a ) 分配方法。静态r w a 问题是预先给出 多条光路连接需求，计算路由和分配波长，计算可以是离线的，即不需要实时计算。静态 的路由波长分配算法已经被研究了很多年，而动态的却研究不多。对于动态情况，光路需 求逐条地提出，但一条光路持续一段时间后又被拆除，要为每一条光路做实时r w a 计算。 影响r w a 的因素很多，对波长连续的网络，在网络拓扑和d i m e n s i o n i n g 给定的情况下，网 络的阻塞率很大程度上取决于所采用的路由和波长分配策略。d i m e n s i o n i n g 为网络直径， 网络直径的定义为所有节点对之间的最短路中的最长值，单位是跳数。很多研究表明网络 直径对连接阻塞率和波长转换有一定的影响，网络直径越大，连接阻塞率就越大，而在有 波长转换的情况下，网络直径越大，波长转换效果就越明显【3 4 1 。工程上常将r w a 问题分解 为路由r 问题和波长w 问题，分两步求解。 4 1 1 路由r 问题 固定路由( f r ，f i x e dr o u t i n g ) ：这是最直接最简单的选路算法。在全网拓扑已知的情 况下，当光路请求到达时，为任意源、目的节点对根据一定的原则指定唯一的路由，如果 存在多个符合要求的路由，将在其中随机选取一个。此种路由算法简单、快速，但是在网 络负载重时会带来很高的阻塞率，且在对待网络的故障方面显得无能为力。 固定可选路由( f a r ，f i x e d a l t e r n a t er o u t i n g ) ：f r 算法无法有效地利用网络资源，因 此出现了f a r 方案。在这种方案中，预先为每一对源宿节点计算多条备用路由，构成备选 路由集。备选路由集的路由按照一定的顺序进行排列i 一般来说，较短的路由拥有较高地 优先级。当请求到达时，按照预先排定地顺序确定路由，即当优先级别较高地路由阻塞时， 才会考虑优先级较低的路由。 自适应选路( a r ，a d a p t i v er o u t i n g ) ：f r 和f a r 算法均可以离线的进行，并且只需计算 一次，只要网络的物理拓扑不发生变化，但这两种算法的问题在于，不能充分考虑到网络 的当前状态，而a r 则可以根据当前的网络状态，如资源使用信息以及故障状况和网络拓扑 的变化等信息动态地进行路由选择。a r 方案具体还可细分为两种：一种是受限a r ，另一 种是非受限自适应路由a u r ( a l t e r n a t eu n c o n s t r a i n e dr o u t i n g ) 。受限自适应选路算法可以用 南京邮电大学硕士研究生学位论文第四章口o v c rw d m 网络的一种动态联合路由算法 下面的例子来具体说明，如4 3 节要提到的基于跳数的最小路算法为例，在进行选路计算之 前，要确定链路的权值( 跳数) ：对于物理链路，当物理链路空闲时，链路的权值为l ，当物 理链路被占用时，链路的权值为0 0 ；对逻辑链路，当b i i b ，链路的权值为逻辑链路所经 过的物理链路的跳数，其它情况下，链路的权值为0 0 ，由于选路要在这样的限制下进行的， 所以叫做受限自适应选路，对于非受限自适应路由算法道理与受限a r 同。由于a r 算法需 要每次在连接请求到达时实时在线的运行，因此它是三种路由方法中最复杂的，但相比前 两种路由选择策略有更好的性能，不仅能优化资源的使用，而且也能使网络资源的分布保 持均衡。 4 1 2 波长w 问题 在确定好路由之后需要为相应的连接请求在路径中分配波长资源，常用的波长选择算 法有： 随机波长分配算法( r a ) ：首先搜索整条路径上所有链路的波长空间，得到可用波长集 ( 如遵从波长连续性限制) ，从该路由上已建光路所使用的波长之外，随机另选一个波长分 配给光通路。 f i r s t - f i t 法( f f ) ：将所有波长编号，在整条路径上根据固定顺序( 波长编号升序或降序) 对每条组成链路进行搜索，最先找到的那个可用波长被分配给光通路。该算法不需要知道 所有波长空间的信息。 l e a s t - u s e d 法( l u ) ：根据网络当前的状态选择在全网各光纤中使用频率最低的波长。 该算法可能由于全网可供使用的波长资源迅速减少，而使网络性能急剧下降。 m o s t u s e d 法( m u ) ：与l u 法正相反，依据当前的网络资源占用情况优先选用被最多链 路占用的波长。该算法可能由于加大干涉路径长度l ，可以获得很好的性能。 最小负载算法( l l ) ：利用网络的局部信息，选择可用路径中具有最大剩余信道数的波 长。 最小影响法( l i ) ：为新的连接请求分配对全网影响最小地波长，考虑了分配波长后产生 多条公共链路成为通路瓶颈的影响。 参考文献【9 】研究显示几种不同波长分配策略下，相对于不同网络，负载的动态阻塞性 1 能不同，其中路由策略为固定最短路由，通道的平均保持时间为一1 = 1s 。当网络负载加重 p 时，几种不同波长分配策略的阻塞率也随之增大，f f 和m u 的不同网络负载下的阻塞率很 相近，r a 和l u 在不同网络负载下的阻塞率也很相近。 南京邮电大学硕士研究生学位论文第四章口o v e rw d m 网络的一种动态联合路由算法 关于对等模型，已经有很多文献对其进行研究，也有一些文献提出了联合路由算法来 解决i po v e rw d m 网络的路由问题，但是这些算法大都属于固定选路的算法( 上面已经简 要介绍) ，很少使用备用选路算法( a r ) 。a r 可以根据当前的网络状态动态地进行路由选择， 尝试从多条路由组成的备用路由集中选择一条合适的路由来建立l s p 。 本章提出的算法是基于备用选路策略的联合路由算法，在多纤分层图模型基础上研究 最小跳数最大容量算法，然后与第三章的算法h i r a 进行比较，通过仿真来说明基于多纤分 层图模型的最小跳数最大容量算法的优越性。 4 2 多纤i p o v e r w d m 网的分层图模型 4 2 1 基本概念 虚拓扑 物理拓扑 a fc fe 瑾 i p l s 路由器 固o x c 一拓扑链路 d 光通道 图4 - 1i p m p l so v e rw d m 网络拓扑结构示意副9 j 在介绍多纤分层图模型之前我们先详细介绍一下物理拓扑、虚拓扑、物理链路与逻辑 链路的概念以及虚拓扑如何得来的。在图4 1 所示的对等模型中，节点是由路由器和o x c 组成的，两者是相当于集成在一起的，是对等实体，采用同一个控制平面，o x c 之间使用 光纤链路连接，在没有任何光通道建立的情况下，由o x c 和光纤链路组成的拓扑图是物 理拓扑，这时候o x c 之间的链路就是物理链路，路由器之间不存在任何逻辑链路，如果 有业务请求从a c 到达，那么只要在节点a 和节点c 之间建立一条光通道( 在物理资源 上是占用物理链路的波长) ，这时对应的路由器a 和c 之间就存在逻辑链路。其实这时候 的拓扑图中既有逻辑链路也有物理链路，建立一条逻辑链路肯定要占用物理拓扑上相应节 点间的物理链路。由于在物理拓扑中，任两个节点中可以建立多条光通道( 在虚拓扑中， 2 7 南京邮电大学硕士研究生学位论文第四章i po v e rw d m 网络的一种动态联合路由算法 这些光通道就等同为光网络中的一条链路) ，所以在虚拓扑的逻辑链路中为了区分这些不 同的光通道，称这些光通道为虚波长。虚波长有3 个属性：生存周期t 、剩余容量c 足以及 在逻辑链路中的虚波长号。在一个虚波长刚刚建立时，c 舟= 波长容量，当有l s p 在该虚波 长上建立时，c r 相应减少。当有l s p 释放时，c r 相应增加。当增加到c r = 波长容量时， 则释放掉该虚波长，同时在光层拆除相应的光通道。在虚拓扑中，一旦两个节点之间至少 存在一个虚波长，那我们就称它们之间就存在逻辑链路。随着更多光通道的建立，逻辑 链路越来越多，虚拓扑图也会越来越大。而带宽的分配其实就是在虚拓扑上分配的，也就 是说是在逻辑链路上分配上的。 图4 - 2 物理拓扑 逻辑链路的寻路过程可以以图4 2 为参考，假如该图是只有一个波长的波长平面，如 果有业务请求从1 到1 3 ，带宽为0 5 个波长容量，我们找到的最短路为1 2 1 1 1 3 ，那么在 1 1 3 就建立了一条光通道，也就是说1 1 3 建立了逻辑链路，该逻辑链路的剩余带宽为0 5 个波长容量，那么物理拓扑上对应的物理链路1 2 ，2 1l ，1 1 1 3 全部删除，因为虽然这个 业务请求只占用o 5 个波长容量，但是建立一条光通道的话整个波长都要被占用，所以如 果再有一个业务请求是从1 到1 3 或者是在虚拓扑上需要经过1 1 3 这条逻辑链路( 业务请求 带宽小于这条逻辑链路的剩余带宽o 5 个波长) ，仍然可以用这条光通道，也就是说两个业 务请求可以复用在一条l s p 上进行传输，这就是在逻辑链路上寻路的过程。对于多纤分层 图来说，因为是根据光纤中的波长数分的层，相当于一根光纤中只有一个波长，所以从一 个节点到另一个节点建立光通路后，一条逻辑链路就建立了，因为逻辑链路在物理拓扑上一 肯定要占用相应的物理链路，所以在混合拓扑图上应该删除相应的物理链路。物理拓扑和 逻辑拓扑还有一点不同：物理拓扑是由o x c 和光纤链路组成的，在没有建立虚链路之前， 0 x c 能处理的最小粒度是一个波长，也就是说只要有业务到达，如果业务的请求的带宽小 2 8 南京邮电大学硕士研究生学位论文 第四章i po v e rw d m 网络的一种动态联合路由算法 于一个波长容量，还是要占用一个波长，即使剩余波长的容量可以供其它的业务占用也不 行；而在逻辑链路中路由器可以处理的粒度较细，比如说0 5 个波长，可以几条l s p 复用 到一条光通道上，这样就会使资源利用率提高。 但是对于没有分层的网络图中，比如一根光纤4 个波长，假设图4 2 没有分层：如果 有业务请求从1 到1 3 ，带宽为0 5 个波长容量，我们找到的最短路为1 2 1 1 1 3 ，那么在 1 1 3 就建立了一条光通道( 占用一个虚波长) ，也就是说1 1 3 存在逻辑链路，该虚波长的 剩余带宽为0 5 个波长容量，但这时1 2 ，2 1 1 ，1 1 1 3 的物理链路在物理拓扑上不能删除， 因为虽然1 2 ，2 1 1 ，1 1 1 3 的波长已经被占用了一个，它们还有3 个波长剩余，当有业务 请求到达2 1 4 时，仍然可以在物理链路2 1 1 1 3 1 4 寻路，这时在2 1 4 建立了一条光通道， 2 1 4 之间存在逻辑链路。如果又有一个业务请求从1 1 4 时，带宽为0 5 个波长容量，那么 它可以在混合拓扑中寻找路由，比如1 1 3 1 4 ，1 1 3 就是逻辑链路，而1 3 1 4 就是一条新打 开的光路，就是物理链路，就如图3 1 的s d 之间的混合路由6 和7 一样。 只有物理链路的波长数用完了物理链路才被删除，逻辑链路删除只要满足一定的条件 就必须删除，比如剩余带宽小于业务请求的最小带宽了，就要把逻辑链路删除。 4 2 2 多纤分层图模型 以往对联合路由的研究都没有采用的分层的概念，它们在分配网络资源时先进行路由 选择，然后再分配带宽，这点4 1 节给出了详细的介绍，而本章提出的最小跳数最大容量算 法就是根据光纤所含的波长数将物理拓扑分解为多纤分层图模型，通过d i j k s t r a 【3 3 】算法计算 出七条最短路由，然后从七条备选路由中选择出一条剩余容量最多的虚波长进行选路。下 面简单介绍一下多纤分层图模型的概念。 多纤分层图模型【1 刁( g m ：g r a p hm o d e l ) 可以一次性解决选路和带宽分配问题。假设给 定网络的物理拓扑g ( n ，l ，f ，驴) ，其中代表节点集，三代表双向链路集，f 代表每条链 路上的光纤集，形是每根光纤上的可用波长集。节点数、链路数、光纤数和波长数分别用 i l 、h 、i f i 和l 形f 表示。考虑的光路也是双向光路。节点包括路由器和光交叉连接器( o x c ) 。 用尺代表多有路由器的集合，z 代表所有o x c 的集合，则n = r u x 。 在分层图中，将物理拓扑g ( n ，l ，f ，形) 中的节点和链路复制i w 次，得到i 1 个子图 g ( n ，) ，兄形，分别对应特定的波长，称为波长平面( 聊) 。为计算路由，添加两个新 节点，对应到达业务的源、目的节点，分别称为虚源节点( v s n ) 和虚目的节点( v d 。分 层图中的边取决于网络的当前可用资源以及此时己建光路情况。具体分为四种：物理链路 2 9 南京邮电大学硕士研究生学位论文第四章i po v e rw d m 网络的一种动态联合路由算法 边( p l e - p h y s i c a ll i n ke d g e ) 、波长变换边( w c e ：w a v e l e n g t hc o n v e r s i o ne d g e ) 、单向边( d e ：) 和逻辑链路边( l l e ：l o g i cl i n ke d g e ) 。如果物理拓扑g 中节点对( f ，) 之间存在一条链路， 而且该链路上存在以个空闲波长兄，则在波长平面w p 旯上的节点对( f ，_ ，a ) 之间存在n 条 p l e ；逻辑链路边表示物理拓扑g 中，节点i 和，之间建立地一条光路，该光路使用波长五， 建立一条逻辑链路必然要占用相应地物理链路。如果节点f 具有波长变换能力，那么在分 层图中节点f 丑和节点f “1 ( 五= 1 ，2 j l 一1 ) 之间存在一条双向边，称为波长变换边。当计算 业务路由时，需要添加2 l 形l 条d e 分别将v s n 连接到节点s a 和将节点d 五连接至i v d n ( 名取值 l l 矽i ) 。对于道道地连接业务请求，只需在g m 上运行路由算法( 如d i j k s t r a 算法等) ，找出 从v s n 到v d n 的最优路径。如果存在，则该路由可能由p l e 、l l e 、d e 和w c e 组成。在为 请求建立标签交换路径( l s p ) 时，只需将找到的路径映射回物理拓扑，此时所有的w c e 和 d e 被忽略。 图4 3 给出了一个物理拓扑图，假设i f i 为2 ，i 形i 为3 。图4 4 是根据单根光纤的波长数 对图4 3 所进行的分层模型图。对多纤分层图，其初始状态时，因为没有业务建立，所以并 不存在v l e ，随着业务的建立，v l e 会逐渐地增多，虚拓扑也会慢慢扩大。虚拓扑的扩大 过程如4 2 1 所述。 为什么说波长分层图模型是同时解决w d m 网络中选路和波长分配问题呢? 如图4 - 4 所 示，分层图的每一层都代表一个波长，在波长分层图模型中，光通道从源节点到目的节点 必须要在同一个波长平面内，即满足波长连续性限制。对于一个连接请求，在波长分层图 上进行选路，它所经过的路径，就是该连接请求在物理拓扑上经过的路径，路径所在的波 长分层，就是它所占用的波长。比如光连接( v 5 ，v 4 ) 的路径是v 3 ，jv 3 ：一v 3 ，专v 3 4 ，即 该请求在物理拓扑中的路径为v 5 专v 2 专v 3 哼v 4 ，且为该路径分配的波长为硒。所以， 波长分层图模型可以同时解决w d m 网络中的选路和波长分配问题。 图4 3 物理拓扑 南京邮电大学硕士研究生学位论文第四章口o v e rw d m 网络的一种动态联合路由算法 4 3 算法描述 叫 波长五层 波长五层 w 图4 - 4 波长分层图模型 波长五层 v ； 本文提出的联合路由算法一最小跳数最大容量算法( m h m c a ) 首先利用网络当前的 拓扑结构及单根光纤所含的波长数将物理拓扑转化为多纤分层图，并根据式( 4 一1 ) 和式( 4 2 ) 确定图中链路的权值，然后用最短路算法( 基于跳数的) 为业务连接请求计算出七条备选路 由( p ( 七) 代表为新到达的连接请求所选的女条备选路由) 。然后从p ( 惫) 中选择具有最大剩 余容量的链路来建立工作路径。从混合拓扑来讲，最大剩余容量确定的原则：以图4 1 为例， 假设a c 为k 条备选路由之一，它在物理拓扑上经过的路径为a b 、b c ，由于a b 、b c 路径上剩余的容量可能不同，通路a c 的容量应该为a b 、b c 路径上剩余容量的最小值， 其它k 一1 条备选通路的容量确定方法与a c 同，而最终选择的路径是这k 条通路上剩余容 量最大的那条，即最小最大原则。m h m c a 算法采用多纤分层图模型一次性解决了路由和 带宽分配问题，而且由于它的基本思想是能达到容量均衡，在剩余容量多的虚波长上进行 南京邮电大学硕士研究生学位论文第四章i po v e rw d m 网络的一种动态联合路由算法 路由，所以在网络负载较重的时候可以避免网络性能迅速恶化取得较好的性能。 对于链路权值是按这样的原则确定的。初始的拓扑是物理拓扑，没有任何逻辑链路的 建立，当物理链路空闲时，物理链路的权值应该为l ( 因为两节点对之间通过光纤相连，其 物理链路的跳数为1 跳) ；当物理链路被占用时，其链路权值应该是无穷。随着一条条光通 道的建立，虚拓扑渐渐地增大，物理链路的部分权值逐渐更新为逻辑链路的权值。逻辑链 路的权值按以下原则定义：当业务请求带宽小于链路剩余带宽的情况下，则逻辑链路的权 值为该逻辑链路所经过的物理链路的跳数；其它情况，逻辑链路的权值为无穷；特殊情况 当逻辑链路和物理链路完全重合时，那么物理链路肯定被占用，所以物理链路的权值应该 是无穷大，而逻辑链路的权值满足带宽要求的情况下为其经过的物理链路的跳数，其值为 1 ，所以链路的权值应该显示为逻辑链路的权值。设b 为新到请求的带宽，良，为链路剩余带 宽，h o p 为逻辑链路所经过的物理链路的跳数。则物理链路和逻辑链路的代价函数如下。 对于物理链路： 勺= ? 耋鬻薹蓑誓裹謇篙时 件， ” i ，当物理链路被占用时 注：当物理链路空闲时，物理链路的跳数恒等于l 。 对于逻辑链路： 其中，h o p =，节点对f 和，之间存在m 条光通道 节点对f 和，不存在光通道 ( 4 - 2 ) 注：对多纤分层图模型，设每条链路之间的光纤集为l f i ，因为波长平面是根据单根光 纤所含的波长数划分的，所以两个节点之间虚波长数最多为f f l 个，即m 最多为i f l 。 波长变换边及单向边代价函数为零。 对基于多纤分层图模型的m h m c a 算法设计时考虑了三个矩阵：网络状态矩阵、逻辑 链路剩余带宽矩阵及物理波长数矩阵，这三个矩阵都是在多纤分层图模型的单个波长平面 上考虑的，具体分析如下。 一 网络状态矩阵：它反映当前网络的混合拓扑情况，矩阵的元素值即为链路的权值( 基于