（电路与系统专业论文）光网络流量工程优化算法研究.pdf

中国科学技术大学硕士学位论文 摘要 流量工程就是一种能将业务流映射到实际物理链路上，同时又可以自动优化 网络资源以实现特定应用性能要求的、具有宏观调节和微观控制能力的网络工程 技术。随着电信业务的迅速增长，特别是宽带业务的增长，用户对带宽的需求嗣 益增加，越来越多的用户更加注重网络带宽资源的合理应用，其中的核心问题之 一就是路由全局优化。 光网络有特殊的网络结构、复杂的子网保护结构和众多的约束条件，业务的 可行路由集的寻找非常复杂，因此需针对光网络提出一个简便的寻路算法。本文 主要研究光网络流量工程优化计算。由于遗传算法( g a ) 不要求目标函数约束可 微，同时g a 能以较大概率求得全局最优解，故本文采用遗传算法以网络资源和 保护资源的占有尽量小，分布更加平衡为优化目标，最终得到优化的路由解。 路由解的优劣以及g a 选择操作都需要用到适应度函数进行评价，适应度函 数涉及到相互制约、权重不同以及量纲不统一的四个单目标网络资源占有、 网络资源负载均衡、保护资源占有和保护资源负载均衡，因此需要为四个单目标 进行数据的标准化消除量纲差异以及制定一个合理的兼顾各个单目标的适应度 函数。 论文在以下几方面作了有意义的研究工作： 1 寻找可行路由集 抽象了光网络各种保护子网以及跨保护子网连接的路由规则。 求得约束条件下的正向工作路由，按照对应的路由规则，获取了可行路由集， 从而为g a 优化提供了一个可行解集合。 2 为路由解提供了合适的编码方案 使用业务编号和路由编号组成的符号作为编码，交叉和变异容易采用相应检 查防止无效个体的产生。 在符号编码的基础上，采用改进的两点交叉( 矩形框交叉) 和基本位变异。 3 构造综合适应度函数 根据光网络结构以及业务特性，提出四个单目标的数学表达式，为构造综合 适应度函数打下基础。 对传统方法和主分量分析方法构造的综合适应度函数进行对比研究，实验表 明：主分量分析方法能更好地反映各个目标之间的制约关系，且在综合评价 时能取各个目标的权重，它比一般的综合适应度函数更合理，能取得好的优 化效果，从而得到更优的路由解。 关键字：光网络，流量工程，遗传算法，适应度函数，主分量分析 中国科学技术丈学硕士学位论文 a b s t r a c t t r a f f i c e n g i n e e r i n g i san e t w o r k e n g i n e e r i n gt e c h n i q u e w i t h 【a c r o s c o p i c a la c c o m m o d a t i n sa n dm i c r o c o s m i cc o n t r o l l i n ga b i l i t y ，w h i c h c a nm a k e m a p p i n g s f r o ms e r v i c es t r e a m st op h y s i c a la c c e s s e s ，a n dc a n s i m u l t a n e o u s l ya n da u t o m a t i c a l i fo p t i m i z en e t w o r kr e s o u r c e st or e a l i z e c e r t a i na p p l i c a t i o np e r f o r m a n c er e q u i r e m e n t s w i t ht h ev a s ti n c r e a s eo f t e l e g r a p hs e r v i c e s ，e s p e c i a l l yb r o a d b a n ds e r v i c e ，t h eu s e r s c a l l i n gf o r b a n d w i d t hg r o w s ，s ot h a tm o r eu s e r st u r nd i r e c t l yt or a t i o n a lu s a g eo f b a n d w i d t hr e s o u r c eo fn e t w o r k ，o n eo ft h ek e r n e lp r o b l e m so fw h i c hi st h e u n i v e r s a lr o u t eo p t i m i z a t i o n a so p t i c a ln e t w o r k sh a v ep a r t i c u l a rn e t w o r ks t r u c t u r e sa n dp r o t e c t i n g s u b n e t w o r ks t r u c t u r e s ，a sw e l la si m m e n s er e s t r i c t i o n s ，t h es e a r c h i n g f o rf e a s i b l er o u t e si sr a t h e rc o m p l e x t h u sap r o p e rr o u t i n ga l g o r i t h m s p e c i f i c a l l yf o ro p t i c a l n e t w o r k s a p p e a r se s p e c i a l l yi m p o r t a n t t h i s a r t i c l em a i n l yf o c u s e so no p t i c a ln e t w o r kt r a f f i ce n g i n e e r i n go p t i m i z i n g c o m p u t a t i o n g e n e t i ca l g o r i t h m ( g a ) i sa d o p t e dt om i n i m i z et h eo c c u p a t i o n o fn e t w o r kr e s o u r c e sa n d p r o t e c t i n gr e s o u r c e sa n db e t t e rt h ed i s t r i b u t i o n o ft h e s er e s o u r c e sa n dt o g a i no p t i m i z e dr o u t i n gs o l u t i o n s t h ee v a l u a t i o no f r o u t i n g si n v o l v e sf o u rs i n g l eo b j e c t sw i t hv a r i o u s w e i g h t s a n dd i m e n s i o n st h a t i n t e r - r e s t r i c tw i t he a c ho t h e r ：n e t w o r k r e s o u r c e o c c u p a t i o n ，n e t w o r k r e s o u r c el o a d e q u i l i b r i u m ，p r o t e c t i n g r e s o u r c e o c c u p a t i o na n dp r o t e c t i n gr e s o u r c el o a de q u i l i b r i u m t h u sa s t a n d a r d i z a t i o no fd a t ao ft h ef o u ro b j e c t st od i m i n i s ht h ed i f f e r e n c e o fd i m e n s i o n sa n dap r o p e rf i t n e s sf u n c t i o nd e a l i n gw i t ha l l o b j e c t si s n e c e s s a r y t h i sa r t i c l ec o n t a i n st h ef o l l o w i n gv a l u a b l ew o r k s ： 1 f e a s i b l er o u t i n ss e t ： e x t r a c t e d r o u t i n gr e g u l a t i o n s f o rc o n n e c t i o n sw i t h i na n d a m o n g p r o t e c t i n gs u b n e t w o r k sf o ro p t i c a ln e t w o r k s 2 中国科学技术大学硕士学位论文 g a i n e dw o r k i n gr o u t e su n d e rv a r i o u sr e s t r i c t i o n s ，a n de x t r a c t e df r o m w o r k i n g r o u t e s t h e k e yq u e u e s c o n s t r u c t e dw i t hc o m m o n 1 i n k s s u b n e t w o r ka n di n t e r s u b n e t w o r kc o n n e c t i o n s g a i n e d f e a s i b l e r o u t i n g s e t sb a s e d o n k e yq u e u e s a n dr o u t i n g r e g u l a t i o n s ，p r o v i d i n gaf e a s i b l es o l u t i o ns e t f o rg ao p t i m i z a t i o n 2 p r o p e re n c o d i n gs c h e m e sf o rr o u t i n g s a st h el e n g t ho fc o d e sw o u l db er a t h e rg r e a ti fb i n a r ye n c o d i n gi s a d o p t e di ng a ，a n da f t e rc r o s sa n dm u t a t i o ni n v a l i di n d i v i d u a l sw o u l db e g e n e r a t e d ，d e n o t a t i o n sc o n s t r u c t e db ys e r v i c en u m b e r sa n dr o u t i n gn u m b e r s a r eu s e di ne n c o d i n g ，s ot h a tt h e l e n g t ho fe n c o d i n gi ss i g n i f i c a n t l y d i m i n i s h e da n dc o r r e s p o n d i n gc h e c k i n gp r o c e d u r e sa r ee a s i l ye m p l o y e dt o p r e v e n ti n v a l i di n d i v i d u a l s 3 g e n e r a lf i t n e s sf u n c t i o n e x p r e s s i o n sf o rt h ef o u r t r o t f l e s t a b s l n g c o m i n gi n t ob e i n g l i s h i n g l eo b j e c t sa r ep u tf o r w a r d ，b a s e do n s t r u c t u r ea n ds e r v i c ef e a t u r e so fo p t i c a ln e t w o r k sf o rt h e p u r p o s e o fc o n s t r u c t i o no f g e n e r a lf i t n e s sf u n c t i o n r e s e a r c h e s c o m p a r i n gg e n e r a l f i t n e s sf u n c t i o n se s t a b l i s h e dw i t h t r a d i t i o n a lm e t h o d sw i t ht h a ti sg e n e r a t e dw i t hp r i n c i p l ec o m p o n e n t a n a l y s i s ，e x p e r i m e n t s i n d i c a t et h a ts i n c e p r i n c i p l ec o m p o n e n t a n a l y s i s c a ns h o wt h er e s t r i c t i o n s a m o n gt h eo b j e c t sa n dc a ng i v e e v a l u a t i o n sw i t ht h e i rw e i g h t sr e s p e c t i v e l y ，t h ee v a l u a t i o nf u n c t i o n g a i n e db yp r i n c i p l ec o m p o n e n ta n a l y s i s i sm o r er a t i o n a la n dc a n r e c e i v eb e t t e rr o u t i n gs o l u t i o n s k e y w o r d s ：o p t i c a ln e t w o r k s ，t r a f f i ce n g i n e e r i n g ，g e n e t i ca l g o r i t h m f i t n e s sf u n c t i o n ，p r i n c i p a lc o m p o n e n ta n a l y s i s 3 中国科学技术大学硕士学位论文 第一章序言 在现有的计算机网络中，网络搁塞主要由两种原因造成，一种是网络资源( 带 宽) 不够大，难以承载更多的数据流量。在这种情况下，解决的办法只能是增加 网络带宽，对网络进行扩容。另一种原因是由于网络在设计时的构想与现实的业 务流量分布不一致，导致网络的某些链路数据流量远大于当初的设计，造成局部 拥塞，而某些链路却造成局部空闲。而传统的i p 路由算法更加剧了这种不均衡“1 ， 无论是最短路径优先算法( o s p f ) 还是距离向量算法( r i p ) ，在选路时都是使用 最短的路径转发i p 分组。由于内部网关协议( i g p ) 在计算路由时并未将链路带 宽和流量特点考虑进去，而单纯计算出最短路径，这必然使得短的路径容易拥塞， 而较长的路径容易空闲。这种由于网络资源使用不均衡造成的网络拥塞必然致使 网络性能降低，服务质量( q o s ) 无法保证。要解决这种网络资源使用的不均衡 就需要引入流量工程啪( t r a f f i ce n g i n e e r i n g t e ) 。 i n t e r n e t 中的流量工程技术是一项以优化网络工作性能为主要目标的网络 工程技术p j ，它能合理安排业务流量在网络中的流向以避免造成网络资源的不均 衡使用。 1 1 流量工程 1 1 1 流量工程的发展 在早期基于路由器的核心网中，流量工程技术是通过简单地使用路由量度值 “1 ( m e t r i c ) 来实现的。即给每条链路规定一个量度值，两点之间的路由是按照一 定的策略计算量度值后来确定的。因为那时无论从路由器数量、链路数还是业务 流量来讲，i n t e r n e t 骨干网都是非常“小”的，所以基于量度的控制是足以胜任的。 同时，在w w w 普遍流行之前，i n t e r n e t 的拓扑层次也强制业务流通过网络中较为确 定的路径，不会产生临时的“热点”。 近年来，随着i p 网络规模越来越大和光纤通信技术的发展，现在的骨干网很 多都开始采用全波长的光网络，网络结构更加复杂和网络容量也加大很多，基于 中国科学技术大学硕士学位论文 量度的流量控制越来越显出它的局限性。 当前，流量工程技术的研究主要集中在对自治系统内部的各种业务流的管理 与控制方面。通过对各种具有不同q 。s 要求的业务流进行适当的路由选择、路由 优化和采取多种高效的流量管理和控制手段来达到此目的。使各种业务流能够在 系统内部均匀、合理地分布，从而显著地降低链路的拥塞概率，提高网络资源的利 用率，实现网络工作性能最佳化的目标。 基于约束的路由选择“。是流量工程中的核心技术，也是实现q 。，s 业务的关键。 它可以根据多个约束条件( 既可以是q o s 的约束条件，也可以是其他策略性的约束 条件) 计算出所有的可行路径，并根据一定的优选策略从中选出一条最优的路径， 以提高网络资源的利用率和网络负载的均衡，实现网络性能的优化。 本文主要针对复杂的光网络进行流量工程的优化计算，按照光网络的特殊结 构和子网保护规则计算出所有的可行路由集，以网络资源占有、网络负载均衡、 保护资源占有、保护资源均衡四个目标为优化目标，以g a 算法优化求取一条较优 的路由。 1 1 2 流量工程模型 从图论观点看，该工程是一个传输网络中的问题，传输网络中的问题又叫网 络流问题( 或流问题) 。通信网络是一种传输网络，传送的是多业务。多业务流 问题就是多个业务的资源优化分配问题。多业务流问题是n p 完全问题，在数学 上还没有有效的解决方法。 从数学观点看，这是一个多目标的优化问题。优化的具体目标包括：占用网 络资源尽量少、网络负载均衡、占用保护资源尽量少、保护资源负载均衡等。 一、多目标优化 对于多目标优化“1 问题，科学和工程领域最终归结为求解一个带有约束条件 的函数优化问题。对于约束优化问题，已有的许多算法都基于梯度的概念，只适 用于目标函数约束可微的情形，而且一般只能保证到局部最优解。由于遗传算法 中国科学技术大学硕j 学位论文 不要求目标函数约束是可微的，同时，g a 能以较大概率求得全局最优解，因此， 它成为求解约束优化问题的一个强有力的工具。 在ga 被广泛应用之前，优化问题的解法主要有： ( 1 ) 基于计算的方法 通过求目标函数导数的零点或一系列迭代计算过程求最优解。对多峰问题， 这类方法易陷入局部最优点附近，且要求目标函数有较好的连续性或可微性。 ( 2 ) 枚举法 在有限的或被离散化的无限搜索空间中比较每一点的目标函数值，求出最优 解。当搜索空间大时，计算量的迅速增加使这类算法失效。 ( 3 ) 随机算法 这类算法主要有m o n t e r c a r l o 法和模拟退火法。m o n t e r c a r l o 法盲目性大； 模拟退火法在实际应用中较成功，但它的从一点到另一点的迭代过程使多峰问题 较容易陷入局部最优解。 对于一个优化算法，寻求最优点不是唯一目的，实际中经常遇到的优化问题 更重要的目标是进步，即优化过程应该是一个不断改进的过程，对复杂系统的优 化更是如此。 与传统优化算法相比，ga 具有如下特点： ( 1 ) 搜索时，不直接使用变量本身，而使用它的编码； ( 2 ) 搜索过程是从一组解迭代到另一组解，减少了陷入局部最优解的可能性； ( 3 ) 它使用的是随机搜索过程而非确定性搜索过程： ( 4 ) 对搜索空间没有任何特殊要求( 如连通性，凸性等) ，只需要计算目标函数值， 不需要目标函数是否连续、可微等辅助信息，因而它的适用范围更广。 光网络流量工程优化计算的核心问题是路由分配全局优化，即根据输入的光 网络拓扑、业务需求等信息，求出满足限制条件的业务路由，并且该解对应的综 合指标最好( 或接近最好) 。工程欲采用g a 算法”1 并且合理的构造个兼顾多个 目标的适应度函数，实现上述要求。 要优化的具体目标比较多，这些目标相互存在矛盾( 矛盾是指某个目标的优 化可能以另一些目标的劣化为代价) ，要全局平衡各目标的矛盾，构造一个兼顾 各个目标的适应度函数。 里型兰垫查查兰竺主兰垡堡兰 在计算中主要考虑的是四个目标：网络资源的占用情况、网络负载均衡、保 护资源的分配以及保护资源分配的均衡。希望网络资源被占用得越少越好、网络 流量在各条链路上分配愈均衡愈好、网络保护资源分配和使用的尽量少、保护资 源在起保护作用的链路上分配尽可能均衡。 目标之间的矛盾主要是：网络资源的占用和均衡上，资源占用少的情况下使 得负载均衡有所劣化；保护资源分配和使用的越少可能造成保护负载不均衡，使 得保护负载过于集中反而不利于保护。 光网络拓扑信息和网络业务信息的数据量也太大，路由的全局优化过程存在 太多的变量和约束条件“3 ，计算难度很大。采用普通的优化算法计算效率低而且 很可能找到的解只是局部最优解。 最主要的难点主要在于： ( 1 ) 构造一个兼顾各个目标的综合适应度函数： ( 2 ) 网络拓扑和网络业务信息量很大，光网络特殊的网络结构以及网络中复杂的 保护结构，优化计算太复杂，计算效率比较低。 经过预处理找到可行的路由集情况下采用g a 来求解问题能够在保证有可行 解的前提下以较大概率求得一个兼顾各个目标的全局最优解。 二、光网络流量工程的数学模型 用图论工具来描述网络的模型。采用一个1 个节点、j 条边、k 个子网和l 个子网互通结构的图g = ( ，e ，s ，r ) 作为光网络拓扑结构。1 ，其中n 代表节点集 合、e 代表链路集合、s 代表子网集合、r 代表子网互通结构集合。e 代表第f 条 链路的容量，b 代表第f 条链路用于保护的容量。 用，的业务矩阵t 来描述欲优化计算的业务，z ，表示第f 个节点到第个 节点的业务，其中的业务按宿点个数有单播业务( 单个源点到单个宿点) 和组播 业务( 单个源点到多个宿点) ，业务按照是否需要光网络提供保护链路以便在工 作路由出现故障情况下能走保护路由可以分成保护业务和非保护业务，业务按照 工作方向可以分为单向业务( 业务仅从源点到宿点) 和双向业务( 业务也可以从 中国科学技术大学硕士学位论文 宿点按照同样的限制发向源点) 。所以一个业务的路由包括四个部分：正向工作 路由、正向保护路由、反向工作路由、反向保护路由。 现在优化计算的目的就是在为业务t 在光网络拓扑结构中的可行路由集中 寻找出全局优化的路由解。四个单目标之间相互制约、四个单目标同时达到最优 化不可能，所以需要寻找一个能兼顾各个单目标的综合目标的综合适应度函数， 使得综合目标达到优化。 其中的数学描述： ( 1 ) 优化目标： m i n ( f ( f 4 ，厶，五，厶) ) ( 卜1 ) 六，厶，五，厶分别代表网络资源占有、网络负载均衡、保护资源占有、 保护资源占有和保护资源负载均衡四个单目标的评价函数，( 厶，厶，正，厶) 是兼 顾四个单目标的适应度函数。 ( 2 ) 约束条件： 民九q ，1 k s k ，1 j j 瓯，a ，1 尼s k ，1 i j ( 1 2 ) 氏= 艺 占“= 1 表示第七个业务经过第i 条链路，为0 的时候不经过：纯，和分别表示第 k 个业务占用第i 条链路的容量和保护资源容量。 1 2 论文的主要研究内容 预处理得到满足约束条件的所有可行路由集，可行路由集很庞大，采用g a 算法从可行路由集中优化计算得出优的路由解，路由解的优劣评价涉及到相互制 约、权重不同以及量纲不统一的四个单目标，为四个单目标进行数据的标准化消 除量纲差异以及制定一个合理的兼顾各个单目标的适应度函数显得尤其重要。 在本文中根据光网络的特殊结构以及业务特性提出四个单目标的数学表达 式，四个单目标的综合适应度函数采用主分量分析方法来动态给出，依照g a 每 中国科学技术人学硕士学位论文 一代样本的数据计算出各个单目标的标准化数据以及各个单目标的合理权重，利 用权重进行线性加和，该种形式的综合评判优于普通的综合适应度函数。 算法流程如下 图1 1 算法整体流程图 中周科学技术大学硕士学位论文 第二章光网络流量工程预处理 光网络流量工程优化计算首先要通过预处理求得所有业务的可行路由集， 然后在庞大的可行路由集中采用遗传算法优化计算求取最终路由解。由于光网络 特殊的网络结构：复杂的子网保护结构“、子网之间互连互通关系“众多，使得 可行路由集寻找很复杂，为光网络提供一个合适的寻找路由路算法“”尤其重要。 光网络“”的基本组成元素和一般的网络是一致的，都是由网络节点、链路、 子网组成，不同的是光网络的子网保护结构众多和子网之间复杂的关系。其中子 网保护结构主要包括p p 、二纤和四纤的m s p 、s n c p ，子网之间的关系有相切、相 交、链路共事以及d n i 关系。 寻求可行路由集的问题描述如下： 输入：网络拓扑信息和业务信息。 网络拓扑信息主要包括网络节点的标识、链路的标识、链路的容量、子网的 组成、子网的保护结构、子网之间的关系，业务信息主要有容量、业务的源点和 宿点、业务是否需要保护。 输出：业务的可行路由集，路由采用业务所经过的链路序列和占用的链路虚 通道表示。 限制条件：路由要遵循子网保护规则、同一个业务的路由不能过同一子网两 次、业务容量不能超过链路容量、业务保护容量不能超过链路提供的保护容量、 满足保护要求。 2 1 光网络拓扑结构 环形网络“”是一种常见的通信网络拓扑形式。和网孔结构相比，环形网络在 保持较高生存性的同时更容易实现和管理，因此广泛用于光网络通信。环形网络 的实现方式多种多样，按节点间波长通道来实现业务的传输方向，可以分为单向 环和双向环两种。针对一个节点而言，在同一传输通道中，如果业务的波长传输 方向与去业务的波长传输方向相同( 如都是顺时钟传输或都是逆时钟传输) ，则 这种环称为单向环；如果传输方向相反，则为双向环。按连接环路中相邻节点的 中国科学技术大学硕上学位论文 光纤数目，环形网络可以分成单纤环、两纤环、四纤环和多纤环。 2 1 1 单向两纤环 如图2 1 所示，设外环光纤为工作光纤，其中复用的波长携带工作业务，内 环光纤为备用光纤，复用保护波长。在这种环状结构中，节点之间的通信业务由 预定波长携带，对应的来业务方向与去业务方向是同向传输的。如图所示，假设 环路节点不作波长变换( 本文中所有的节点都不考虑作波长变换) ，节点a 到节 点b 的通信由波长九。实现；节点b 到节点a 的通信由波长九。携带，节点c 、d 分别直通该波长。 2 1 2 双向两纤环 一、单纤双向传输方式 图2 - 1 两纤单向配置环 图2 - 2 所示为单纤双向传输方式。假设外环光纤为工作光纤。图中的工作光 纤携带双向传输的波长。节点之间的通信通道由在同一光纤上反向传输的光载波 建立( 如节点a 和节点c 之间分别为 c 和屯) 。 中国科学技术大学硕士学位论文 二、双向双纤方式 图2 - 2 单纤双向配置环 、”- 1 撩妒醴琏! i “螂：】 l i 柏= 渡鲢粼舶，2 - 1 ) 图2 - 3 双向双纤配置环 9 二缝 中国科学技术大学硕士学位论文 2 1 3 四纤w d m 环 图2 - 4 所示为w d m 的四纤结构。在四纤环中，相邻节点用四根光纤连接，它 们可以分成传输方向相反的两对光纤，其中一对为工作光纤，另一对为保护光纤。 图中，实线所示为工作光纤对，虚线为保护光纤对。节点a 、c 之间的通道由顺 时针传输的波长l 。和逆时针方向传输的波长_ 。构成。在相同网络规模情况下， 网络总容量比两纤双向环提高了一倍。同时还具有灵活的业务保护能力。 2 2 光网络保护结构 图2 4 w d m 四纤环配置 支持单向双向通道保护环( p p ) 、子网连接保护( s n c p ) 、支持单向双向复 用段保护环( m s p ) 、支持1 + l 线性复用段保护( m s p ) 及共享虚拟光纤路径保护。 符号约定： 彬表示正向工作路径，表示反向工作路径，鼻表示的保护路径，只表 示的保护路径；巳表示用于正向工作的边，巳：表示用于反向工作的边，岛，表 ! 璺型堂垫查查兰堡主主堡篓墨 示用于保护正向路径的边，p 。表示用于保护反向路径的边。在不同的保护结构 中，符号约定可能有变化。形哆，_ ，尸哆_ ，月，l ，r p 哆1 分别表示同个结 构中两点之间的正向工作路由，正向保护路由，反向工作路由，反向保护路由， 当为了表示是哪一个结构的时候，加入表示结构的下标，如阡z 。儿_ 表示r i n g l 中 的两点之间的路由。在路径串s = v ，e 。k p ：中点与_ 问的子串用s u b ( s ，巧) 表示。 2 2 1 通道保护环 通道保护环( p p ) 的业务保护是以通道为基础的，是否进行保护倒换要根据 出、入环的个别通道信号质量的优劣来决定。通道保护环一般采用i + i 保护方式， 即工作通道与保护通道在发送端永久性地桥接在一起，接收端则从中选取质量好 的信号作为工作信号。在进行通道保护倒换时只需在接收端把开关从工作通道倒 换到保护通道上，其保护倒换时间小于5 0 m s 。常用的通道保护环有二纤单向通 道保护环和二纤双向通道保护环两种。 一、单向通道保护环 v v 1 v 3 v 2 图2 5 单向通道保护环图 ( 1 ) 结构描述 彤：k g l l k 1 巧。g ；e ：k p 。，k 8 1 3 k ，。 ( 2 ) 路由规则 中国科学技术人学硕士学位论文 k 与y 之间的路由 正向工作路由：w p ，= s u b ( w 1 ，k ，一) 正向保护路由：p ，。= s u b ( p , ，k ，巧) 反向工作路由：r w _ ，。2 w ， 反向保护路由：r p ，_ = p ，k 。 二、双向通道保护环 ( 1 ) 结构描述 ：v , e u 坞吒，k 。 暖：巧z 巧q ：巧。 鼻：k 。v k 8 。k 。； 岛：巧q ，圪，巧。 ( 2 ) 路由规则 与之间的路由 v 1 图2 - 6 双向通道保护环 正向工作路由：w 气，。2 s u 。b ( w ：j v f ，f j p ) l ，e n g 州t h ( s m u b ( ( w 吖i , ，v - , ，v 蚴j ) ) $ ，l k e n 刚g t h ( ( s u b 6 ( ( w k 2 ，k h ，v _ i ) ) ) ) 正向保护路由：9 ，_ 2 嚣：i z i 鼍z 要： 反向工作路由：r w ，吩= ”_ ，h ； 反向保护路由：8 ，y ，= 。 1 2 中国科学技术大学硕士学位论文 2 2 2 子网连接保护 子网连接保护( s n c p ) 是指对某一子网连接预先安排专用的保护路由，这样一 旦子网发生故障，专用保护路由便取代子网担当在整个网络中的传送任务。 子网连接保护在网络中的配置保护连接方面具有很大的灵活性，特别适用于 不断变化、对未来传输需求不能预测的、根据需要就可以灵活增加连接的网络， 故而它能够应用于干线网、中继网、接入网等网络，以及树形、环形、网状的各 种网络拓扑，其保护结构为1 + 1 方式，即每一个工作连接都有一个相应备用连接， 保护可任意置于v c l 2 、v c 2 、v c 3 、v c 4 各通道，同样，运营者也能决定那些连接 需要保护，那些连接不需要保护。当同时在复用段实行保护时，传输信号将有可 能被双重保护。 v 1 猡习v o 图2 7 子网连接保护环 ( 1 ) 结构描述 ：矿i i c i i v 2 k ，。；墨：k p 。：8 。：k 。，k 。表示环回到k ，寻找子序列 的时候要考虑是环。 ( 2 ) 路由规则 与矿之间的路由： 正向工作路由：w l ，_ ： ：x 鬈彭l ：| ：篙搿鬈聋喾：箸：龆：鬈参：； 正向保护路由：p ，。= 篓 黪z ：_ 甏。缮： 反向工作路由：r w ，吁= s u b 。( w 1 ，y ，i v ，j ) 1 e n g t h ( s u b ( w ，t , v ，! , v t ) ) _ l e n g t h ( s u b 。( p i 。, v j 。, v j ) ，) 反向保护路由：r p i ，。= ：嚣z 篆冀虢鬈盏。 中国科学技术大学硕士学位论文 2 2 3 复用段保护 线性复用段保护是一种专用或共用的保护机制。它对复用段层提供保护，适 用于点到点的物理网络。一个复用段保护用于保护一定数量( n ) 的工作复用段， 但不能对节点故障提供保护，它可工作于单端或双端方式，此外复用段保护在备 用状态时还可用来开通无需保护的额外业务。 复用段共享保护环的工作通道传送业务，其保护通道则留作业务信号的保护 之用外还可以作为工作通道传送工作业务，专用保护环的保护通道则只能作为保 护所用，其保护倒换时间为5 0 m s ，分为二纤双向复用段共享保护环和四纤双向 复用段共享保护环两种保护方式。 一、线性复用段保护 以双向四纤描述；若为二纤单向的复用段，表述为双向四纤的复用段的反方 向为空。由于专用保护和共享保护不影响路由确定，在描述保护规则的时候，暂 不考虑。 ( 1 ) 结构描述 图2 - 8 线性复用段保护 ：8 ( ) 2 一】e ( m _ 2 ) 2 圪8 【) 2 v 2 e 1 2 k e l ：v i e i3 k p 2 ”k ”圪： b ：8 ( ) 4 v 0 7 _ l 。( + 2 ) 4 v k e ( 胪v 2 e 】4 k 。 ( 2 ) 路由规则 n u 帅 中国科学技术大学硕士学位论文 矿与矿之间的路由： 正向工作路由：w p v , ，_ = 登：麓盘z 一登糍j ；茄 正向保护路由：p ，_ = 篓是i z 一强。z 妻； 反向工作路由：r w 力= 篓麓i z l 罨z 蓦； 反向保护路由：r p ，_ = ：浍j 考l 澎盏要。 二、复用段保护环 以双向四纤描述；两纤情况，每纤看作两个虚光纤。一般的保护图示例中， 复用段保护环的保护路径都用同一跨段内的复用段保护，而不是倒换环保护。这 里的保护描述只讨论同一跨段内的保护，实际上还潜在有倒换环保护。 图2 - 9 复用段保护环 ( 1 ) 结构描述 啊：k p l l k p 2 r 吃p 。l k w ： ：v , e 。2 e 1 2 k w ； 鼻：k q 3 k e 2 ”p 。3 k ，。g ； 与：v , e 。4 k ，k 口1 4 k 。g 。 ( 2 ) 路由规则 与之间的路由： 正向f 作路由：w _ ，巧= ( 嚣豫盏彭j 铭 篙：盏紫2 嚣溢豫薯z ： 中国科学技术大学硕士学位论文 正向保护舳：9 = 鬻燃麓缮 反向工作路由：r w l ，o2 ”，f ： 反向保护路由：r p p f ；f j 2 p p 5 k 。 2 2 4 共享虚拟光纤路径 仅考虑同向p p 环共享时的路由以及s n c p 和m s p 环光路共享时的路由。其他 共享光纤按照争用处理。 一、同向p p 环共享 图2 一1 0 同同p p 耶共享 ( 1 ) 结构描述 两p p 环r i n g l ，r i n 9 2 ，同向，两点v o 平n g 间的线路共享，k r i n g l ，r i n 9 2 。 ( 2 ) 路由规则 f 与v j 之间的路由： 正向工作路由：w i ，吩2 w p ，哪l ，h 。圪+ 肜0 懈2 ，匕，r ，； 正向保护路由：p 。吁2 pp ，垤l k + 尸只w 2 ，_ ： 反向工作路由：r w p f , ，吁2 h 馆2 ，_ ，+ w p ，馏l ，圪，； 反向保护路由：r p ，0 2 p p ，憎2 ，_ ，圪+ p 0 惟i ，吒，q 。 二、s n c p 和m s p 共享 ! 里型竺丝查查兰堡点兰堡堡兰一 v j 图2 - 1 1s n c p 和m s p 共孚 ( 1 ) 结构描述 两环r i n g l ，r i n 9 2 ，r i n g l 是m s p 环，r i n 9 2 是s n c p 环，两点吃和间的线 路共享，r i n g l ，r i n 9 2 。 ( 2 ) 路由规则 与r 之间的路由： 令圪为m s p 环中与k 近的相交点，另一个交点为吒，则 正向工作路由：唧麓，0 2 畔w f ，_ ，赡+ 弓2 ，_ ； 正向保护路由：p ，r ，2 p 如馏l 并，硌+ 户j 0 2 ，匕，o ； 反向工作路由：r w 。匕2 w p r i n 9 2 , y j ，眨+ w p ，i n g i ，以，_ ； 反向保护路由：r p p , 。0 2 p p r 懈2 ，_ ，_ + p 0 ，馏l ，”。 2 3保护结构的互连与互通 两个子网之间的关系主要有相交、相切和环网间互通业务保护( d n i ) 。 2 3 1 相切 中国科学技术大学顶士学位论文 图2 1 2 两子网相切 ( 1 ) 结构描述 两环r i n g l ，r i n 9 2 ，两环切点：t ，r i n g l ，v r i n 9 2 。 ( 2 ) 路由规则 与_ 之间的路由 正向工作路由：w 吃，_ = z 懈1 ，k ，_ + 形2 ，。 正向保护路由：p ，o = p 0 1 ，_ ，_ + p 只2 ，。5 反向工作路由：r w p k , ，_ = w g t 9 2 , , ，+ l ，_ ： 反向保护路由：r p ，巧= e g 增2 ，_ ，+ 皿啊1 ，k 。 2 3 2 相交 这种情况因两环的不同而不同，情况复杂，分情况讨论 一、p p - p p 同向 ( 1 ) 结构描述 图2 1 3p p p p 同向相交 8 婴燮塑型燮l 两p p 环一n g l , r i n 9 2 ，交点吃和圪，同向，v , r i n g l ，_ ，f 馏2 。 ( 2 ) 路由规则 与一之间的路由： 不妨 r i n g 工作方向上，交点依次为圪，( 容易判断出) ： 正向工作路由：w ，。= 鸭w l ，k ，+ 啤2 ，吃一； 正向保护路由：9 ，吩2 p 0 i ，q ，+ p 只，增2 ，_ ； 反向工作路由：r w ，_ 。阡。2 ，吩，吒+ 形1 ： 反向保护路由：r p ，吩2 肼2 ，吩，+ p 0 吣i ，”。 二、p p p p 异向 图2 - 1 4p p p p 异向相交 ( 1 ) 结构描述 两p p 环由9 1 ，一n 啦，交点圪和，异向，v ；r i n g l ，砌曙2 。 ( 2 ) 路由规则 与之间的路由： 不妨设r i n 9 1 工作方向上，交点依次为圪，圪( 容易判断出) 正向工作路由；”肾：圳 正向保护路由：_ p 。， 碑慨_ ； 反向工作路由：暇。2 2 + 聊，删 反向保护路由：r p ，。2 9 2 ，。，坫+ p 。增i ，吒，_ 。 中国科学技术大学硕士学位论文 三、s n c p s n c p s n c ps n c p 图2 - 1 5s n c p s n c p 相交 1 ) 结构描述 两s n c p 环r i n g l ，r i n 9 2 ，交点v o 和k ，r i n g l ，r i n 9 2 。 2 ) 路由规则 k 与r 之间的路由： 令一为圪和k 中距较近的一个，另一个为；令为圪和圪中距一较近的 个，另一个为k ： 正向工作路由：w ，巧2 w p r 增l ，k ，+ 阿弓愕2 ，_ ： 正向保护路由：p _ ，0 2 p p ，蛔1 ，。，以+ p 2 ，乓，_ ； 反向工作路由：r w p f , ，o = w p r 懈2 ，。，+ l ，l ； 反向保护路由：r p p 5 ，吩2 p 耳，增2 ，_ ，屹+ 牌w l ，l 。 四、s n c p m s p ( 1 ) 结构拙述 图2 - 1 6s n c p m s p 保护相交点 中国科学技术大学硕士学位论文 两环r i n 9 1 ，r i n 9 2 ，r i n 9 1 是s n c p 环，r i n 9 2 是m s p 环，交点圪和 v i r t n g l , p r i n 9 2 。 ( 2 ) 路由规则 与r 之间的路由： 令圪为m s p 环中距_ 较近的一个，另一个为v ： 若w ，。，则： 正向工作路由：w ，o2 w 弓嘲l ，l ，+ 阡7 2 ，。，y ，； 正向保护路由：p ，0 2 p 耳，增l ，h ，哆+ p 0 ，增2 ，咋，_ + 霉懈2 ，“，k ； 反向工作路由：r w p f , , v j 一- - 阡z w 2 ，y ，+ w p ，w l ，心，_ ； 反向保护路由：r p ，_ 2 p p ，馏2 ，。，+ 尸p 2 ，。，。+ 尸p 增l ，。，k 。 若巧w ，吒，则： 正向工作路由：w 吃。_ 。w p ，w l ，k ，。+ 阡? 增2 ，。，巧； 正向保护路由：p 民，。2 p 培1 ，k ，h + p 2 ，。+ 皿2 ，。，吒