（信号与信息处理专业论文）适用于动态网络交通的共享路径保护结构的研究.pdf

擒要 摘要 由于生存性在网络规划和设计中的重要性，共享路径保护作为一种有效的 在现代可生存性网络中应用的保护方法，可以保护网络连接免受网络节点和网 络路径的损坏所造成的中断。这是本论文研究的主要课题。 共享路径保护是一种面向路径的保护方法，集运算简便，速度快，效率高 于一体。它为每一条工作路径建立一条保护路径，当工作路径上的任何一段路 径不能正常工作时，数据将被快速的重新分配到保护路径上。以实现连接的可 持续性。由于，当相应的工作路径彼此分开没有共同的路径时，保护路径之间 可以共享保护资源，这大大提高了资源的利用率。 在该论文中，我们研究并开发了两种不同的基于i l p 的实现共享路径的结 构以适应不断变化的交通模式。通过实验结果分析，算法得出的最优化结果将 被展示论文最后，我们将对两种共享路径保护结构的工作效率做出总结。 关键词；生存性设计。共享路径保护，i l p 公式 a b s t r a c t a b s t r a c t d u et ot h ei m l x , a a n c eo ft h es u r v i v a b i l i t yd e s i g ni nt h en e t w o r kp l a n n i n g , s h a r e dp a t hp r o t e c t i o na 3 咄o ft h ee f f e c t i v em e t h o d su s e di nm o d e ms u r v i v a b l e n e t w o r k st op r o t e c tac o n n e c t i o nf r o mt h ef a i l u r eo f a n ys i n g l el i n ko ras i n g l en o d ei s t h et a r g e ti s s u ew ew a n td or e s e a r c hw i t hi nt h i sw o r k s h a r e dp a t hp r o t e c t i o n ( s p p ) i sap a t h - o r i e n t e dp r o t e c t i o ns c h e m ew i t ha p e r t i c u l a rc o m b i n a t i o no f o p e r a t i o n a ls i m p l i c i t y , s p e e da n de f f i c i e n c y i te s t a b l i s h e sa w o r k i n gp a t ha n dal i n kd i s j o i n tp r o t e c t i o np a t h , s ot h a ti nt h ee v e n to fal i n kf a i l u r e i nt h ew o r k i n gp a t h , d a t a 锄b e q u i c k l yr e r o u t e dt h r o u g ht h ep r o t e c t i o np 地i ti s c a p a c i t ye f f i c i e n td u et ot h ef a c tt h a tp r o t e c t i o np a t h s 锄s h a r el i n k sw h e nt h e i r c o r r e s p o n d i n gw o r k i n gp a t h sa 聘m u t u a l l yd i v e r s e i nt h i sw o r k , w ed e v e l o pt w od i f f e r e n ts h a r e dp a t hp r o t e c t i o nc o n f i g u r a t i o n s s u i t i n gc h a n g i n g 缸瓶cp a t t e r n s , o nt h eb a s i so fl ipf o r m u l a t i 哪t a r o u g ht h e e x p e r i m e n t a le v a l u a t i o n s ，t h ea l g o r i t h mp r o d u c e s0 l ，删s o l u t i o n si sd e m o n s t r a t e d a tt h ee n do ft h ew o r kac o n c l u s i o nw i l lb eo v e no u tt oj u d g eh o we f f i c i e n te a c h c o n f i g u r a t i o nw o r k s 1 畸w o r d s ：s u r v i v a b i l i t yd e s i g n , s h a r e dp a t hp r o t e c t i o n , i l pf o r m u l a t i o n 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：j 爻据 扣6 年d 3 月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 截钳 年月日a 一6 年啼月a f 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： 扣6 年o f 月争厂e t 第1 章引言 第1 章引言 共享路径保护是- 种十分重要的网络生存性设计方法。由于生存性设计在 网络规划中的重要性与日俱增，而共享路径保护方法具有运算简单，高效率以 及简便性等优良特性，因此成为该论文研究的主要课题。 在该论文中，我们研究了适应于动态交通的共享路径保护结构，分析了基 于整型线性公式的方法并进行了例案研究首先，通过开发整型线性公式我们 建立了适应于动态交通的有效结构，之后通过实验数据分析，由算法产生的优 化结果将会被展示。最后，在不同的配置结构建成之后，根据得出的优化结果 我们将对不同配置的有效性做出总结 1 1 网络生存性设计背景 如今，网络业务快速的发展带动了与之相关的各项业务以及服务的快速膨 胀。这种信息的高速膨胀对带宽的需求十分大。为了满足不断增长的带宽需求， 网络中的波长信道都有很高的传输速度，甚至超过每秒c , i g a b i t s ，例如在某些高速 网络中，信道的传输速率甚至达到了每秒t e r a b i t s 然而，当某一信道或者光纤连接被切断时，高速的传输速率可能导致一系 列服务堵塞而无法正常完成传输任务。这种切断有可能是操作错误、软件程序 缺陷、硬件缺点、自然灾害甚至是人为作恶所造成的。 由于当今社会，国家经济、社会安全以及日常生活越来越多的依赖于通信 两络。为了避免由于意外的错误导致的信息交换中断，成为网络规划中一个越 发重要的任务 因此，生存性设计已经成为光纤网络研究中重要的课题之一为了克服不 可避免的偶然性突发状况，最普遍的方法无外乎于为网络中的工作路径预先规 划或者预先配置网络资源以保证被错误影响数据流能够快速切换到备用资源上 以维持业务的连续性这种设计的初衷十分简单、清楚，但是妥开发一种行之 有效的分配备用资源的方法却仍然是尚待解决的问题 第1 章引言 1 2 生存性设计方法 由于生存性设计已经成为网络规划和设计中十分重要的一个课题，首先我 们将介绍应用于网络中不同层的用于防止发生网络突然中断的一些基本技术。 表格1 1 中详细说明了在四个层次中可以使用的网络生存性实现方法。每 一层都对相应的下一层提供一定类型的服务。虽然这里采用了分层的抽象概念， 但是每一个为上一层提供相应服务的层次，不需要知道其下层是如何实现提供 给它的那些服务的。所以很重要的一点，即使这里用了层次的概念，但是这不 表示一个或者所有的生存性实现方法一定要应用于每个层次上 表1 1 分别应用于四个层次的生存性设计方法 层功能和服务一般的生存性设计方法 服务层 网络，i s d n ，多媒体适应性路由安捧，应用再尝试 逻辑层逻辑传输结构，带宽的分配和管理 网眼保护机制和恢复机制 系统层 点对点的b i t 传输，点对点的光纤 i ：na p s ，l + ld pa p s ，环状保护 物理层 保证传输联通性的物理媒介保证物理层的多样性 物理层是网络中物理资源的基础配置场所。在这个层次中，生存性设计方 法的主要宗旨在于，保证物理层的拓扑结构能够为其以上的层次提供空间多样 性，让在这些层次应用的技术能够正常工作 系统层中为了避免电缆切断的生存性方法是保护机制。保护机制的主要特 点在于，保护路径以及保护量提前设置好( 关于保护机制的主要原理将在下一 章中详细介绍) 它是一种自身独立的保护机制采取的措旆主要是应付本层 内发生的意外中断。 不同于系统层采用的保护机制，这种方法基本上是静态，逻辑层的生存性 方法则更加的灵活和动态。逻辑层的灵活性表现在可以根据连接请求的实时需 要在端点之间建立路径更高的效率可以通过网络恢复机制实现，它可以允许 保护量在不同时出错的链路上实现共享，来提高资源的利用率。 服务层的生存性方法是最后一道保证物理错误不被用户察觉的关卡。不同 于以下各层，其成本主要是引入的多余端口以及分配的保护量服务层主要是 基于软件的一些应用，它只是尝试分配那些对于本层透明的工作量和保护量 2 第1 章引言 在本论文中，我们主要讨论共享路径保护，它是一种十分重要的应用于逻 辑层的生存性设计方法 1 3 本论文研究的核心问题 由于生存性设计成为网络规划中日益重要的任务之一，共享路径保护作为 可生存性网络中一种行之有效的保护方法，能够保护连接免受单一连接或者结 点切断错误的影响。这也是本论文要研究的主要课题。 共享路径保护，是一个面向路径的保护机制，它集操作简便性，速度快和 高效率性于一体。这些优点使它在i p 中心光网络以及m l p s 层中发挥了相当的 作用。它是一种独立于故障的，面向路径的机制，保护通道提前为工作路径规 划好，但是备用资源需要在保护通道上通过交叉连接实时分配 这种保护机制是本论文要讨论的主要课题。但是不同于以往的研究，以垄 的研究大多都是集中满足静止的交通需求。然而，网络中不断涌现的新服务以 及不断提高的数据传输率使得面向灵活动态交通的网络配置结构在网络设计中 越发的重要。本论文研究了适合于动态交通模式的共享路径保护设计我们分1 析了基于整型线性设计的方法并进行了个案研究。 因此，本论文的目标就是要建立适应于动态交通的实现共享路径保护的结 构在不同的配置结构建成后，我们还将对其做出比较，对这些结构工作的有 效性做出判断。 在以下的章节里，我们将介绍一些广泛应用的网络保护机制，并以共享路 径保护方法作为介绍重点。第3 章我们将集中精力介绍本论文研究的课题。详 细对问题进行描述并且介绍算法。在第4 章和第5 章中，基于说明性的例子以 及仿真结果，一些实验数据和初步的分析结果会被展示第6 章中我们将得出 结论 3 第2 章网络保护方法 第2 章网络保护方法 在本章中，我们将详细介绍用于可生存性网络设计的一些基本概念，其中 包括保护机制和恢复机制的区别，面向路径的保护机制和面向边的保护机制的 区别。之后我们会介绍面向路径的保护机制的优点共享路径保护作为一种重 要的面向路径的设计方法将会被详细介绍。我们还会详细介绍它的主要工作原 理以及优化的设计模式。 2 1 保护和恢复 为了清楚的呈现保护机制和恢复机制之间的区别，首先让我们看下面的表 格2 1 表2 1 三种基本的生存性设计概念 层功能和服务一般的生存性设计方法 服务层网络i s d n , 多媒体适应性路由安捧。应用再尝试 逻辑层逻辑传输结构。带宽的分配和管理网眼保护机制和恢复机制 系统层点对点的b i t 传输。点对点的光纤i ：n a p s ，i + ld p a p s ，环状保护 物理层保证传输联通性的物理媒介保证物理层的多样性 从上表中可以看出，所谓的保护机制，就是将由工作路径到启用保护路径 的行为完全提前定义好。保护系统在起始和终点结点之问提前建立好，处于待 命状态因为保护路径是完全提前定义好的，不需要经过交叉连接来实时建立 连接 与保护机制不同，在恢复机制中，取代工作路径的保护路径需要经过交叉 连接实时建立连接。 因此，可以说在一个纯粹的保护机制中，备用的保护路径完全专注于变更 发生错误的工作路径。在一个纯粹的恢复机制中，所有多余的可用资源储存在 一个共用的空间，直到根据需求在错误发生时实时建立保护连接。因为要实时 4 第2 章网络保护方法 寻找建立保护路径，就有反映速度慢的缺点，相比之下在保护机制中，备选路 径是提前定义好的，它的恢复速度就明显快 但是结合两者的中间机制才是最有竞争力的有效机制，因为它可以结合资 源利用率和速度快，这两种机制分别的优点。在错误发生之前，各选的保护路 径已经提前确定号，但是当错误发生时，才实时通过交叉连接来建立这条保护 路径。因此，从这种意义上不能将共享路径保护简单的归于保护机制或者是恢 复机制，它是一种介于两者之问生存性设计方法 2 i i 路径保护和链接保护 我们已经知道了三种基本的生存性设计方法，还有必要了解其他一些在保 护机制中相互区别的概念。也就是，基于路径的保护机制和基于链接的保护机 制 在基于链接的保护机制中，所有通过被切断的链接的连接都围绕着这条链 接，寻找其他备选的保护路径。而连接的起始和终止结点对这条发生错误的链 接一无所知。这表示作为替换的保护路径起始于发生错误的链接的起点，终止 于发生错误的链接的终点 而在基于路径的保护机制中，当一条链接被切断时，与被切断的链接的始 末结点相邻的结点会通知整条连接的起点和终止结点因此，作为保护工作路 径的替换保护路径在连接的起点和终点之间重新寻找图2 ，1 到图2 3 举例说 明了这两种机制之间的详细区别 5 第2 章网络保护方法 图2 1 两条发生故障的工作路径 图2 2 可能采取的基于链路的保护 图2 3 可能采取的基于路径的保护 从图2 1 中我们可以看出，图表中有两条工作路径，一条是黑色的，另外 一条是灰色的。由于边c - d 的意外切断影响到了这两条工作路径图2 2 展示 了基于链路的保护机制。灰色的工作路径在发生错误的c - d 链路周围，寻找到 了备用链路c - i , - - d ，相应的黑色的工作路径在发生错误的链路c - d 周围找到了 替代的链路c i h - e d 与之相对比，图2 3 展示了基于路径的保护机制。采用更全面的变更路径 方法来帮助维持网络的连续性它在距离发生错误链路的远处采取行动，在建 6 第2 章网络保护方法 立连接的起始和终点结点之间找到一条替代路径。基于路径的保护机制的一个 优点就是，它不会出现在图2 2 基于链路的保护机制中发生的迂回通信情况 2 1 2 路径保护机制的优越性 从以上解释的原理来看，在一个基于路径的可恢复网络或者基于路径保护 的网络中，采取行动的位置远于真正发生错误的连接的起始和终点结点这种 生存性机制拥有如下的优点： 首先，它在客户层次的控制，以及透明性方面更禁得起考验。基于链路的 保护机制只是网络传输层本身的一个功能，但是基于路径的保护机制是一个能 放入客户控制层，或者放在服务层控制下的功能。其使用范围更广泛 其次，在共享路径保护中，使用者可以在发生错误的情况下，提前知道究 竟在哪里可以使得服务重新恢复。有时候这对于客户是十分重要的。相比之下。 在基于链路的保护机制中，虽然使用者知道服务可以被恢复。但是具体在哪里 被恢复却不得而知。另外，没有迂回通信，基于路径的保护机制比基于链路的 保护机制更具有资源利用的高效率性。 最后，基于路径的保护机制还能对结点上发生的错误做出反映，采用相应 的恢复措施。但是这对于基于链路的保护机制却不是总能做的到。因为基于路 径的保护机制只需要对路径连接的起始和终止结点做检测，这一点对于只能在- 起点和终点处做信号检测的透明的或者半透明的光网络来说是十分可贵的 除了这些主导性的优点，基于路径的保护机制实际上在速度上不如基于边 的保护机制快主要原因在于相对来说较长的恢复路径以及被涉及的网络结点 过多 2 2 共享路径保护 共享路径保护是一种基于路径的生存性机制，它集合了操作简便，高效率 和速度快等优点 截至目前大量的研究都集中于对已经明确的故障进行恢复的保护机制。但 是共享路径保护是一个独立于故障的保护机制，其中保护路径已经提前确定好， 只要在故障发生时通过实时的交叉连接来建立这条保护路径的连接即可 7 第2 章网络保护方法 换句话说，共享路径保护是一种介于纯粹的保护机制与纯粹的恢复机制中 间的机制任何的影响到工作路径正常工作的错误都会使提前确定好的，但是 需要交叉连接建立的保护路径投入使用。这样，在不同保护路径上的保护量， 在其工作路径相互分离的情况下就可以实现共享 2 2 1t 作原理 图2 4 详细表述了共享路径保护方式的工作原理。所谓的保护量在保护路 径上实现共享的核心思想得到充分展示。在图2 4 中，三条工作路径在边a - b 上实现共享，以分别为其建立三条保护路径 w 1 p 1 图2 4 三条彼此分开的工作路径的保护路径在 b 边上实现共享 w i 、w 2 、w 3 是三条彼此分开的工作路径p l 、p 2 、p 3 是三条工作路径 相应的保护路径。 为了满足保护路径可以实现共享，必须保证没有任何一个错误能同时影响 到两条相互分开的工作路径，这样它们的保护路径也就不会在同一时间被需要 因而可以实现共享。 从图2 4 我们可以清楚的看到，三条保护路径在边a - b 上实现共享，而它 们相关的工作路径都彼此分离。由于三条工作路径可以在a b 边上实现共享， 那么a b 边上分配到的保护量就是它们在不能实现共享情况下的三分之一这 1 第2 章网络保护方法 样就大大提高了资源的利用率 2 2 2 相互分离的工作和保护路径对 从以上介绍的关于共享路径保护的工作原理来看，在安排实现共享路径保 护的网络中最重要的一点就是在有连接请求的起始结点和目的结点之间，寻找 到成本最小的相互分离的，没有共同边的工作路径和保护路径对寻找有效的 这样的路径对也是实现共享路径保护的最基本也是最为重要的算法之一 在这样一对路径对之中，其中一条路径是在有连接请求的结点之间的工作 路径，另一条是一条与工作路径相分离的，作为备选路径的保护路径。当工作 路径由于意外状况切断时，保护路径可以作为备选重新建立连接以维护网络的 持续性。 在实际应用中，共享路径保护中的工作和保护路径对通常是这样获得的： 一般来说，要在起始结点和目的结点之间找到的所有有效物理路径之中，选择 最短的一条物理路径做为工作路径，其次短的一条被当作工作路径的保护路径 在图2 5 中详细阐述了工作路径和保护路径之间的逻辑关系，这种关系保 证了保护路径上的保护量可以实现彼此共享 图2 5 工作路径和保护路径的逻辑关系 图中所列的两个域分别是工作路径域 w ) 和保护路径域f p 。它们之间有一 一相互对应的关系，即一条工作路径对应一条保护路径在工作路径域 w 中， 会有一些相互分开即没有共同边的工作路径，它们相应的保护路径在保护路径 9 第2 章网络保护方法 域 p 很可能有共同的边，这些保护路径就可以实现资源共享。但是那些不是相 互独立的有共同边的工作路径，即使它们的保护路径之间有共同的边，也不能 实现共享因为当意外发生，很可能同时影响两条工作路径，那么其保护路径 上分配的保护量可能不够同时维持两条连接，这样就不能保证正常网络连接的 联通性而发生中断。将会影响到网络的服务质量。 2 2 3 共享路径保护的最优设计 路径和流量设计模型是目前网络中应用的两种主导的实现共享路径保护的 模型。 传统的选择合适的工作路径和保护路径是路径模型中使用的方法。但是在 这个模型中根据选择路径方法的不同还可以做出如下的分类： 不联合共享路径保护模型 在不联合共享路径保护模型中，要为已经找到的工作路径寻找相应的 保护路径。 联合共享路径保护模型 在联合共享路径保护模型中，有效的工作路径和保护路径作为一个决 策整体。也就是说，首先在有连接请求的起始结点和终止结点之间找到合 适的工作路径和保护路径，然后只要做出一次选择来满足这个连接请求的 需要。 另外一种设计可能是，对一对起始结点和目的结点之间的所有连接请求只 选择一条保护路径，另外一种可能是对一对起始结点和目的结点之间的所有连 接请求分别选择不同的保护路径。比如说，一对起始和目的结点之间有五个连 接请求，在第一种设计中五个连接请求将会通过同样的工作路径，并且只有一 条保护踌径。而在第二中设计中，五个连接请求有各自不同的工作路径，并被 不同的保护路径保护 由于在不联合共享路径保护模式中，为已经确定好的工作路径可能寻找不 到合适的保护路径。为了避免这种风险，在本论文中，我们集中研究第二种方 法，即联合共享路径保护模式，即为网络中的每一个连接请求找到合适的并且 成本最低的工作和保护路径对。我们还假设，在起始结点和目的结点之问的每 一个连接请求都有各自的工作路径和保护路径 1 0 第3 章共享路径保护的算法研究 第3 章共享路径保护的算法研究 本章中，首先将会详细描述我们建立的两种实现共享路径保护的配置结构。 然后介绍这两种配置结构的i l p 公式。i l p 公式的设计目的就在于使网络中消耗 的工作量和保护量达到最小值。 3 1 研究问题的定义 就像我们在第1 章中对论文核心问题的介绍一样，不同于以往的研究，它 们大多集中于满足静态网络交通需求。本论文研究的共享路径保护设计是适应 于不断变化的动态交通模式的我们分析了基于整型线性设计的解决方法，并 进行了个案分析。 因此，我们的首要任务是建立适应于动态交通的有效结构。不同的配置建 成后，根据仿真结果我们将作出比较，评价不同配置的工作效率 3 1 1 两种配置结构的描述 结构一：我们将这种配置结构称作完全重新配置系统 在这种结构中，对于当前的所有的交通连接请求，工作和保护路径将被完 全重新寻找。确切的讲，不考虑在k l 时刻网络配置结构如何，对在t i 时刻的交 通模式，所有工作和保护路径都将被重新为现有的连接请求寻找 与此对比，第二种配置结构我们称之为对已有结构的升级。从字面上理解， 我们可以基本了解这个结构与以上介绍的结构的不同之处也就是说，对当前 网络中所有的连接请求，我们试图重新利用那些仍然存在的，在上一时刻网络 中找到的资源来满足这一时刻新到的连接请求。我们为新到的连接请求寻找工 作路径以及保护路径，并让这些新寻找到的保护路径尽可能共享已经存在的保 护资源 图3 1 和图3 2 清楚的解释了这两个配置结构是如何操作的 第3 章共享路径保护的算法研究 a d o 暑 c 图3 1 初始的网络交通状态 图3 2 两种实现共享路径保护的配置 初始状态中在b - c 结点之间有两个连接请求，这两个连接请求的工作路径 分别是b - c 和b f _ , - c ，我们假设保护路径b - a - m c 被选作保护这两条工作路径， 它们在链路& 气a _ d 和d 屺上实现共享 当当前的交通模式发生任何变化时，我们假设b - c 之间的一个连接请求终 止了，另外一个连接请求在结点a e 之间产生。此时面对已改变的交通模式， 不同的算法将在这两个不同配置结构 在完全重新配置系统中，不考虑原来的网络结构，我们将重新为两个现有 的连接请求寻找两条新的保护路径。例如，6 婚e 被选作保护工作路径a - f ， 与此同时m e 选作来保护工作路径1 3 4 2 在对已有结构进行升级系统中，当前的连接建立请求将会被完全不同的对 待。在初始状态被选中的工作和保护路径对b - c 和b a d 屺保持不变，因为 b c 之间有一个连接请求在此刻仍保持不变我们需要做的，仅仅是为a - e 之 1 2 第3 章共享路径保护的算法研究 间新到的那个连接请求寻找保护路径，并且保证新寻找到的这个保护路径尽可 能的与原有的已经存在的保护路径( 例如例中的良a d c ) 共享保护资源。结 果，a b - e 被选择来保护工作路径a - e ，事实上这条保护路径确实在链接a - b 上与已经存在的保护路径m - d c 实现了共享 3 2 整型线性设计公式( 几p ) 3 2 1 线性整型设计皿种的介绍 线性整型设计方法起源于o p t i o n sr e s e a r c h ( 0 r ) c o m m u n i t y 。是一种数 学设计方法。需要解释的是，虽然它是一种。p r o g r a m m i n g ”的方法，但是它和 我们今天所说的“p r o g r d m m i n g ”即编程是完全不同的两个概念。它是一种数学 决策模型，通过规划决策来对一个目标函数进行优化，并且使这个目标函数能 够满足某些数学约束条件。 以下是四种基本的数学设计方法类型 1 线性设计( l p ) 线性设计的目标函数以及约束条件都是线性的函数，其决策变量可以是连 续的实数 2 整型线性设计0 if ) 一个或多个决策变量被严格的定义为整型值所有的目标函数和约束条 件都是线性的在一个纯粹的整型线性设计中，所有的变量值都严格定义为整 型 3 混合型整型设计( m i p ) 一些变量是连续的实数，另外一些规定为整数m i p 的一个基本形式是1 o m m ，其中整型变量规定只能取值o 或者1 也就是典型的是非类型 4 非线性设计( b j i ) 一个或者多个目标函数和约束条件不是线性的 我们在该论文中只考虑整型线性设计方法，并且所有的变量都严格定义为 整型值所有的目标函数和约束条件也都是线性的 以上提到的设计方法在生产和研究领域，对网络规划以及在线操作都有很 重要的意义它们可以解决各种类型的大规模优化问题，并且在可以接受的时 1 3 第3 章共享路径保护的算法研究 间内计算出最优的有效结果。尤其是l p 和i l p 设计方法具有更加重要的意义： 1 数学设计的语法和结构为开发，详细说明以及理解规划问题的根本特性 及结构，提供了精确、紧凑的语言和格式。 2 它对问题的格式化声明，几乎可以直接转化为可以执行的指令来得出实 际规划问题的最优结果并且能帮助寻找网络中一些特性的存在性或者可操作 性 接下来，我们就介绍一下i l p 公式的基本格式 m a x i m i z e ：q 而+ c 2 屯+ + q 毛 o b j e c t i v e ( 3 1 ) s u b j e c tt o ：a l i 毛+ a i 2 而+ + a 1 毛协与= 撬c o n s t r a i n t ( 3 2 ) 吗i 而+ a 2 2 x 2 + + 口2 _ 协与= 溉 ； 口- l 而+ a 2 x 2 + + 口_ 隹与= 丸 o x j_ = l 2 一 在这个i l p 公式的基本格式中，x 是一系列决策变量f x l , x 2 ，x e 中的一个 向量所有的变量都必须保证为非负的整数。常数项不能出现在约束条件的左 边而约束条件的右边不能出现变量。在一个目标或者约束条件函数中，一个 变量不可以出现两次优化的意义在于让目标函数值最大化或者最小化系统 约束条件左边的所有系数构成了一个系数矩阵 3 2 2 完全重新配置结构的i l p 公式 在3 1 1 节中我们已经介绍了两种有效的配置采用不同的算法来实现共享 路径保护。一个是完全重新配置系统，另外一个是对已有结构的升级在本节 中我们首先介绍用i l l ) 方法书写的完全重新配置结构 参数定义： n ：网络中的所有结点，指数为n e ：网络中所有的边指数为i i r ；起始结点至终结点的所有可能的组合，指数为r d r ：网络中所有现有的需要建立连接的需求量，指数为击 b r ：一对起始结点和终结点之间的所有可能的工作和保护路径对，指数 1 4 第3 章共享路径保护的算法研究 为b 。 册：，j ：当第b 个工作和保护路径对中的工作路径通过第i 条边时，此 参数值为l ，否则为0 。 丑毋，j ：当第b 个工作和保护路径对中的保护路径通过第i 条边时，此 参数为1 ，否则为0 变量定义： 曲：在一对起始结点和终结点之问，有一个建立连接的请求，当第 b 对工作和保护路径对被选中来满足这个连接请求时，此变量的值为1 否则为0 。 ：网络中第j 条边上的工作量 弓：网络中第j 条边上的保护量 目标函数：使网络中所有边上的工作量和保护量的和值尽可能小 m i n 妒，+ 乃) ( 3 3 ) 约束条件： 1 保证每次对于一对起始结点和终结点之间的一个建立连接请求，只有一器 个工作和保护路径对被选中 p ，= 1【v ，e 置，v 毋e d ，) ( 3 4 ) 2 计算网络中边j 上的i 作量，只有当第b 个工作和保护路径对被选中，并 且被选中的工作和保护路径对中的工作路径通过边j 时，边j 上才有工作量 = 喝，j( 功 ( 3 5 ) 3 当除了j 边以外的其他i 边上的工作路径被破坏时，保证j 边上的保护量 足够进行路径保护。 吼j 岛，鹎，j 弓( e ，v i e e , j i ) ，e r 士e j d r 6 e 西 ( 3 6 ) 3 2 3 对已有结构的升级配置的 l p 公式 参数定义： 一 蔓! 童茎皇堕墨堡芏箜蔓茔堡壅 n ：网络中的所有结点，指数为n e ：网络中所有的边指数为i ，i r ：一对对起始结点至终结点的所有可能组合，指数为r b r ：一对起始结点和终结点之间的所有可能的工作和保护路径对，指数 为b 。 聊：， ：当第b 个工作和保护路径对中的工作路径通过第i 条边时，此 参数值为1 ，否则为0 。 剧：，：当第b 个工作和保护路径对中的保护路径通过第i 条边时，此 参数为l ，否则为0 。 岛曲j ：在一对起始结点和终结点之间，有一个建立连接的请求，当第 b 对工作和保护路径对被选中来满足这个连接请求时，此变量的值为1 否则为0 。 形：阿络中第j 条边上的工作量 毋：网络中第j 条边上的保护量。 d ：网络中前一时刻所有的连接请求 d 尸：网络中现有的所有连接请求 p 出耐；网络中新到的连接请求 z 矿“：相对于前一时刻的连接请求，现在不再存在的连接请求 声，：网络中可以再利用的保护量，也就是说，对于这一时刻仍然存在 的连接请求已经找到的保护量 磊鲋：相对于前一时刻所有的连接请求，现在仍然存在的连接请求。 第b 对工作和保护路径对被选中满足这神连接请求时，此值为l 否则为 0 变量定义： p j ：在一对起始结点和终结点之间，有一个新到的建立连接的请求， 当第b 对工作和保护路径对被选中来满足这个连接请求时，此变量的值 为l 否则为0 ：网络中第j 条边上的工作量 弓：网络中第j 条边上的保护量 目标函数：使网络中所有边上的工作量和保护量的值尽可能小。 1 6 第3 章共享路径保护的算法研究 砌+ 弓)( 3 7 ) i e 约束条件： 1 保证每次对于，一对起始结点和终结点之间的一个新到的连接请求，只 有一个工作和保护路径对被选中 蒌j = l( v ，e 胄，v d r 旷) ( 3 8 ) 。7 2 计算网络中边j 上的工作量，只有当第b 个工作和保护路径对被新到的连 接请求选中，并且被选中的工作和保护路径对中的工作路径通过边j 时，边j 上 才有工作量。 矿，5 暑士蟊d 乏卯 九( e 功 ( 3 躔 r e r 由t l h 、1 j 一j 1i 3 当除了j 边以外的其他i 边上的工作路径被破坏时，保证j 边上的保护量 足够进行路径保护，并且尽可能的利用网络中已经存在的保护量 。、 。王。溉弛+ s 霉+ 弓 瑚硝萨俨叫曲砌，e 面 。； 0 ，e v i 丘，f ) ( 3 1 0 ) ? 3 3 算法分析 3 3 i 完全重新配置系统的c - h 程序算法 步骤一：为网络中现有的连接请求找到必须的工作和保护路径对 首先，为起始和终点结点对之间的存在的连接请求，找到有效的物理 路径。我们定义每一条边上从起始结点到终点结点的方向为正方向 其次，所有寻找到的有效物理路径会按照长度捧列顺序，并输出结果 最后，经过比较最短的路径将会被选作工作路径，第二短的路径被选 作是保护工作路径的保护路径很明显，一个路径对里的工作和保护路径 必须相互分开没有共同的边。 1 7 第3 章共享路径保护的算法研究 步骤二：建立变量 建立网络中每条边上的工作量和保护量为变量我们定义每条边上通 过的工作路径以及保护路径的数目分别为该边上的工作量和保护量 步骤三：建立约束条件 约束条件一：对一个连接请求，每次只能有一个工作保护路径对被选 中来满足这个请求。 约束条件二：计算工作路径中每条边上的工作量。 约束条件三：使用下述方法计算保护路径中每条边上的保护量，当计 算某一条边上的保护量时，我们让其他任意一条边切断，那么通过该边的 保护路径数目的最大值就被定义为这条边上的保护量 步骤四：建立目标函数 我们让网络中所有边上的工作量和工作量的和值最小化。 步骤五：建立优化模型 我们借助c p l e x 软件环境建立优化模型 步骤六：求值 为网路中现有的连接请求找到最优的工作和保护路径对，计算并输出 每条边上消耗的工作量，保护量以及总共消耗的资源( 即工作量和保护量 之和) 这些值将被用做数据分析 3 3 2 对已有结构升级配置的c + + 程序算法 步骤一：为新到的连接请求计算网络中已经存在的可以再度使用的保护 量。 首先，在已有配置结构的基础上我们得到了总共消耗的保护量，以及对 已有配置结构中旧的连接请求所选择的工作和保护路径对 之后，我们通过增加和减少某些连接请求使得现有的交通模式发生变 化。基于那些停止的连接请求，我们要删除为这些连接请求寻找到的保护 量，并且得到为这些已经停止的连接请求所选择的工作保护路径对作为返 回值。但是必须考虑的是，不能对那些用来保护已经停止的连接请求的保 护量简单的进行删除，因为它可能与其他仍然存在的连接请求的保护量实 现资源共享我们只能删除那些单单用来保护已停止的连接请求的保护量。 i s 第3 章共享路径保护的算法研究 我们使用以下方法计算每条边上仍然可以被再利用的保护量，我们得到 那些在已有配置结构中，为仍然存在的连接请求选择的最优的工作和保护 路径对。当计算某一条边上的可利用的保护量时，我们让其他任意一条边 被切断，那么通过该条边上的保护路径的最大数目就是该边上的可利用保 护量。 重新计算出来的可以被重新利用的保护量，以及那些为仍然存在的连接 请求选择的工作保护路径对，被作为参数加入该配置结构的第三个约束条 件之中。正如公式( 3 1 0 ) 所示 步骤二：为网络中新到达的那些连接请求寻找有效的工作和保护路径 对。 具体的算法实现和上述的配置结构中介绍的算法一样 步骤三：建立变量 定义每一条上的工作量和保护量作为变量。我们定义每条边上通过的 工作路径以及保护路径的数目分别为该边上的工作量和保护量 步骤四：建立约束条件 约束条件一：为一个新到的连接请求，每次只能选择一个工作和保护r 路径对。 约束条件二：为新到的连接请求找到的工作路径，计算每一条边上的 工作量。 约束条件三：我们为新到的连接请求找保护路径，重要的一点是，让 这些新寻找到的保护路径尽可能的与那些已经存在的可以再利用的保护量 实现共享。 步骤四：建立目标函数 我们让网络中所有边上的工作量和工作量的和值最小化 步骤五：建立优化模型 我们借助c p l e x 软件环境建立优化模型 步骤六：求值 为网路中现有的连接请求找到最优的工作和保护路径对，计算并输出 每条边上消耗的工作量，保护量以及总共消耗的资源( 即工作量和保护量 之和) 这些值将被用做数据分析 挣 第4 章倒证性说明示范 第4 章例证性说明示范 在本章中，我们将集中介绍两个不同的基于i l p 公式实现共享路径保护的 配置结构在实际网络中的应用。首先我们将其运用于一个小的例证性网络，以 证明它们的可实现性。首先，我们将展示，算法怎样为满足网络中的连接请求 找到有效的工作和保护路径工作对。其次，我们假设网络中的交通模式发生了 变化，两种不同的配置结构将采用不同的算法找到最优的工作和保护路径对来 满足网络中连接请求的需要。 4 1 例证性结果的分析 由下图可以看出，我们将基于i l p 公式的实现共享路径保护的两周配置结 构首先应用于一个小的网络研究。 第4 章例证性说明示范 o 图4 。1 网络中的物理连接 b e 圈t2 网络中的连接请求 从图4 1 中可以看出，实际中的物理网络有5 个结点，8 条物理的边。图 4 2 详细描述了网络中现有的连接请求，通过它可以详细了解网络中在哪两个结 点之闯，有多少个连接请求存在。我们的首要任务就是满足这些连接请求，为 其找到有效的最优的工作和保护路径对。 从图4 2 中我们可以看出。有4 对结点之问有连接请求，他们分别是a 和 c 、a 和e 、b 和c 、c 和d 之间，他们之间连接请求的个数分别的2 、2 、2 和 2 我们已经在第二章提到过，因为没有一个错误能影响烈相互分离的工作路 径，所以他们的保护路径可以在同一时间实现共享因为正常情况下，只有工 作路径承载数据，保护路径上的带宽资源是不被使用的，那么不同保护路径上 的保护量不会在同一时间内使用，所以能够实现共享。我们认为，通过一条边 上的工作路径的数目为该边上的工作量保护量是当其他任意一条边切断，该 2 l 第4 章例证性说明示范 边上通过的保护路径的最大数目。 通过c 卜+ 编程，首先我们将所有的连接请求映射到实际的物理网络中去 这表示，我们要为有连接请求的两个结点之间找到一条有效的物理路径。之后 所有的工作都是在物理网络中完成的，因为它才是实际中存在的网络。我们计 算出所有基于连接请求的有效物理路径，并挑选出那些彼此没有共同边的，相 互分开的路径作为各选，工作和保护路径对就从它们之间选出 我们为所有的连接请求提供一系列有效的物理路径，并且按照其长度的大 小顺序捧列。一般来说，最短的路径会被选择作为工作路径，其次短的路径被 选为保护路径。 在l ip 公式的帮助下，我们在图4 3 中详细给出了为不同连接请求找到的 工作和保护路径对 图4 3 为所有连接请求找刭的工作和保护路径对 以a c 之间的连接请求为例我们首先在物理网络中为 - c 之间寻找有效 的物理路径。从所有有效的物理路径中最短的路径会被选为工作路径，当工作 路径由于种种原因被意外切断时，其次短的路径被选为保护路径来保护工作路 径，。因为工作和保护路径对是被选来满足连接请求的但事实上，a 之间有 两个连接请求，那么算法会根据l ip 公式的目标函数，为另一个连接请求选择 第4 章例证性说明示范 合适的工作和保护路径对，以使得网络中消耗的工作量和保护量之和最小 图4 4 具体列出了为不同连接请求找到的工作和保护路径对 d e m a n d e d g ew o r k i n gp a t h p r o t e c t i o np a t h j 4 一c a ca d c a ca _ b _ edc a _ e4 。d _ e a 一日- e a 日一e a d e e b 。cb + cb e e b cb a d c c dc e dc d c dc e b a d t o t a lw o r k i n gc a p a c i t y 1 l t o t a lp r o t e c t i o nc a p a c i t y 5 图4 4 计算出的有效工作和保护路径对 从图中我们可以看出，满足此刻网络中所有的连接请求，消耗的工作量和 保护量分别是1 l 和5 ，总共消耗量为1 6 a - c 和b - c 之间的工作路径，其保护 路径在b - e 和e c 上实现共享 图4 5 详细介绍了我们如何计算每一条边上的保护量。当我们考虑计算保 护路径通过的j 边上的保护量，首先我们让其他任意一条不同于j 边的边被切断， 计算当其他任意一条边被切断时，j 边上通过的保护路径的数目，最后经过比较 通过i 边的最大的保护路径的数目就被设置成j 边上的保护量。最后通过累加每 一条边上的保护量，我们就得出在网络中总共消耗的保护量 第4 章饲证性说明示范 e d g e j f a i l e de d g ei n u m b e ro fp r o t e c t i o np s t hc 8e d g ej a 一层a 一口 0 a c1 a dl 口一e 1 b _ e0 c _ dl c _ e0 d e0 p r o t e c t