多域光网络中采用条件风险分离度的生存性策略

赵季红，曲桦，王力，毛宏宝

(1. 西安邮电学院 通信工程系，陕西 西安 710061; 2. 西安交通大学 电信学院，陕西 西安 710048)

1 引言

随着通信网的发展和各种通信技术在网络中的应用，使得应用不同通信技术的设备组成一个独立的域，每个服务提供商也控制一个独立的域，因而形成了多域光网络[1]。多域光网络的形成原因导致其域与域之间相对独立，域与域的设备之间不能互操作[2]；同时，考虑到具有高带宽需求的、动态的、跨越多个光网络域的新业务的不断涌现，对多域光网络的生存性提出了更高的要求[3～6]。为了增强多域光网络的生存性，在多域光网络中应用保护机制为业务计算工作路由和保护路由，当工作路由发生故障后将业务倒换到保护路由上。但是在多域光网络中，各个域的拓扑及带宽分配信息被限制在单域范围内，只有边界节点信息对外部域可见，要让某个节点掌握网络的全局信息是不现实的，这种现象被称作可扩展性约束[7]，由于可扩展性约束的存在，路由数据库维护的只是不准确的网络状态信息，这就需要应用虚链路映射技术生成抽象拓扑，在抽象拓扑上应用路由算法为业务计算端到端的工作路由和保护路由，以减少网络开销和运营成本。

为了提高网络生存性，IETF提出 SRLG[8]约束保护路由的计算，保证保护路由和工作路由物理故障分离，即保护路由和工作路由不会同时发生故障，达到了增强网络生存性的目的，但是会造成业务阻塞率的增加。由于一条链路可能属于多个SRLG，文献[9, 10]提出用条件故障概率描述属于同一 SRLG的链路发生故障的概率，文献[11]提出一种不共享风险的路由算法。本文在条件故障概率的基础上提出条件风险分离度（CRDD）定量描述工作路由和保护路由的故障关联程度，提出一种部分共享风险的、基于CRDD的、区分业务可靠性的多域光网络生存性策略，该策略首先应用基于CRDD的域内虚链路映射算法生成抽象拓扑，再根据业务请求可靠度，应用基于CRDD的端到端工作/保护路由算法在抽象拓扑上计算CRDD满足其请求可靠度的工作/保护路由对，达到在多域光网络中区分业务可靠性的目的。

文章安排如下：第2节给出CRDD的定义，比较基于CRDD计算保护路由和SRLG约束下计算保护路由的区别；第3节研究采用CRDD的区分业务可靠性的多域光网络生存性策略，包括基于CRDD的域内虚链路映射算法和基于 CRDD的端到端工作/保护路由算法；第4节对基于CRDD的区分业务可靠性的多域光网络生存性策略性能进行仿真分析；第5节总结全文。

2 条件风险分离度

CRDD是为了从数学角度定性地描述工作路由和保护路由的故障关联程度而提出的。CRDD的概念建立在条件故障概率[10]的基础上，条件故障概率（风险概率）是对物理链路的故障关联性的定量描述。

定义 链路Li的SRLG集合表示为srlgi，P(srlgi)表示链路Li的条件故障概率，即风险概率。假设条件故障概率则对于属于 srlgi的多条链路，当其中一条链路失效时，其他任意一条链路不受该故障影响的概率为1-k，即

设链路Li的SRLG集合为srlgi，链路Lj的SRLG集合为srlgj，链路Li和链路Lj的共同SRLG集合为为链路 Li的条件故障概率，P(srlgj)为链路Lj的条件故障概率，则链路Li和链路Lj的条件风险分离度定义为

设工作路由和保护路由所属SRLG集合为其经过的链路所属 SRLG的并集，即工作路由和保护路由的共同SRLG集合为则工作路由和保护路由的条件风险分离度定义为

应用CRDD定义和式（2）分析基于CRDD计算保护路由和SRLG约束下计算保护路由的区别，图1为示例拓扑图。

图1 示例拓扑图

设从节点1到节点5的工作路由为1→2→5，不考虑SRLG约束，它的备选保护路由有4条，分别是：1→3→5，1→3→4→5，1→4→5 和 1→6-→5；如果考虑 SRLG约束，链路 1→2、1→4和链路 1→3属于SRLG1，保护路由1→3→5、1→4→5和1→3→4→5不可用，只有保护路由1→6→5可用，增加了业务的阻塞率。

讨论基于CRDD为业务计算保护路由。备选保护路由BP1为1→6→5，它经过链路的SRLG集合为{srlg3, srlg4}；备选保护路由BP2为1→3→5，它经过链路的SRLG集合为{srlg1, srlg5}；备选保护路由 BP3为 1→4→5，它经过链路的 SRLG 集合为{srlg1, srlg2}。

再根据不同业务选择 CRDD大于其请求可靠度的工作/保护路由对。相比SRLG约束，基于CRDD计算保护路由为业务提供了更多的备选保护路由，不仅降低了业务阻塞率，还达到了区分业务可靠度建立保护路由的目的。

3 采用 CRDD的区分业务可靠性的多域光网络生存性策略

3.1 网络模型

在多域光网络中应用生存性策略为业务请求计算工作/保护路由对时，需要抽象多域光网络，生成抽象拓扑，在抽象拓扑上计算工作/保护路由对。

为了区分业务可靠性，为不同业务请求计算不同可靠性的工作/保护路由对，本节提出基于CRDD的区分业务可靠性的多域光网络生存性策略。其中信息聚合模块应用基于 CRDD的域内虚链路映射算法，以CRDD为约束条件，将内部光路映射成反映工作光路和保护光路故障关联程度的域内虚链路，构成抽象拓扑；路由模块应用基于CRDD的端到端工作/保护路由算法区分业务请求可靠度，计算满足要求的工作/保护路由对。

图2为多域光网络分层路由模型[12]。最底层是多域光网络的物理拓扑，它由5个不同的路由控制域(RCD, routing control domain)互联构成，每一个RCD都由边界节点、内部节点及连接这些节点的物理链路组成，每一个RCD不包含其他RCD的任何信息，不使用骨干域进行通信，每个 RCD配置一个路由控制器(RC, routing controller)，负责完成该域的信息聚合、路由信息分发、路由计算等；中间层是由RC1、RC2、RC3、RC4和RC5互联形成的互操作控制平面，其中RC1、RC2、RC3、RC4和RC5分别属于 RCD1、RCD2、RCD3、RCD4和RCD5；顶层是聚合网络，是由各域RC在控制平面内广播各自的聚合信息形成的逻辑虚拓扑。

图2 基于拓扑抽象的多域光网络分层路由模型

3.2 基于CRDD的域内虚链路映射算法

在基于CRDD的区分业务可靠性的多域光网络生存性策略中，需要路由控制器将工作/保护内部光路映射为域内虚链路，要求生成的域内虚链路具有可靠性差异，即能够反映工作/保护内部光路的可靠性差异。

以图2多域光网络为例，它可以表示为D=(N,L)，它由5个相互独立的单域构成，即m=1,…,5；N(Nm)和 L(Lm)分别表示 D(Dm)的节点集合和链路集合。

为了简化分析，假设在单域光网络中采用全网格拓扑抽象，以D3为例，如图3所示，当D3的域内 RC3完成拓扑抽象后，得到 D3的抽象拓扑表示D3的边界节点集合， C3VIRTUAL表示所有连接边界节点的反映穿越该域特征信息的域内虚链路e的集合。

图4给出了基于CRDD的域内虚链路映射算法流程图，其中应用了 Dijkstra-improved算法，Dijkstra-improved算法是使用了双尺度(P, C)的Dijkstra[13]算法，其中P表示内部光路q的条件故障概率，C表示内部光路q的代价，C=1/rq，rq为q的剩余带宽容量。基于CRDD的域内虚链路映射算法流程如下。

图3 全网格抽象生成候选内部光路组

图4 基于CRDD的域内虚链路映射算法流程

Start初始化计数器j、k，置为1。

Step1如果j和k的值不相等，说明选定一条虚链路（j, k），跳转至Step 2，否则跳转至Step9。

Step2对选定的域内虚链路，使用 Dijkstraimproved算法得到最稳最短内部光路候选组 PjSkEL（候选内部光路总数 nSjkEL）。使用的尺度标准为（P,C），其中 P(L)表示物理链路 L的失效概率，表示物理链路L的代价，CLRES表示物理链路的剩余带宽。仍以Dm为例，如图3所示，4个边界节点之间的任意一条虚链路都确定了可能的内部光路组。

失效概率

条件概率

其中，srlgi表示链路 Li的 SRLG；S(q)表示内部光路q的SRLG集合，即CS(q1,q2)表示内部光路q1和q2的共有SRLG集合，即

Step3通过判定分析虚链路（j, k）是否已经得到预期的内部光路，若没有，则转到Step 4；反之，跳转至Step 9。

Step4对域内虚链路（j, k），在 PjSkEL中搜索工作内部光路q，并添加到集合Se中。搜索原则：对（j, k）而言，由于该内部光路的选入，新增的与备份虚链路的CRDD之和最大，ye1置1时表示内部光路 qe1属于集合 PB，否则置0；i i e1其中 C 是q和 qe1的CRDD，根据式(2)表示如下

Step5根据在Step 4中得到的Se搜索q。搜索原则是：该q与已选工作内部光路的CRDD之和最大，其中，xe1置1时表示内i部光路 qe1i在PWe1中，否则置0，并做如下更新。

Step6搜索备份q。搜索原则是：对域内虚链路（j, k）而言，由于该内部光路的选入，新增的与工作虚链路的CRDD之和最大，并做如下更新：

Step7对于集合中的任意 q，沿着q的域内物理链路序列依次执行可用波长向量与运算，得到光路q的可用波长向量组。

Step8对集合中的所有 q，求和可用波长出现的次数，并基于门限Q限制得到最后的内部光路可用波长向量；跳转至Step 9。

Step9对k的值加1，转至Step 10。

Step10如果k的值大于该单域的边界节点总数b，则说明已到达最后一个边界节点，跳转至Step 11；否则，跳转至Step 1。

Step11对j的值加1，转至Step 12。

Step12如果 j的值大于该单域的边界节点总数 b，则说明已到达最后一个边界节点，该域虚链路映射完成；否则，跳转至Step 1。

End没有搜索到满足条件的工作/保护内部光路，或者

至此，单域RC完成了域内虚链路映射，得到相应的具有可靠性差异的备选工作/保护路由。

3.3 基于CRDD的端到端工作/保护路由算法

当所有单域完成拓扑抽象和虚链路映射后，RC通过域间路由协议在控制平面内广播聚合信息，形成聚合网络。由于聚合网络直接关联了域内光路和域间物理链路，因此基于聚合网络的代价计算是准确且不失可扩展性的。基于 CRDD的端到端工作/保护路由算法的主要思想是：对那些与工作路由经过的链路具有相同SRLG标识的链路，并非直接删除它，而是将其与工作路由的 CRDD作为选路依据，计算满足业务可靠性要求的最优保护路由。端到端工作/保护路由算法如下。

Step1在聚合网络上，使用最短通道优先算法计算工作路由p，跳转至Step 2。

Step2对于跨越多域的工作路由 p，根据式(3)，计算p的失效概率。

根据式(4)计算p的条件故障概率：

Step3基于业务可靠性 R，计算，并且对任意，P(Sj)=0；其中，本质上是通过对SRLG进行分类处理以优化算法，计算的过程如下。

根据特定业务的可靠性需求，算法需要搜索这样的工作和保护路由对：它们同时失效的概率不超过(1-R)，即

由贝叶斯公式得到

联系p的条件故障概率公式

因此，满足了式(12)也就满足了业务可靠性需求。

由上面的分析可知，对于SRLG集合中的srlgi，如果，即当工作路由和保护路由同时关联srlgi时，仍能满足业务可靠性需求，称该srlgi为不需要考虑风险的SRLG集合，否则为需要考虑风险的SRLG集合。由此，SRLG集合被分成2类：需要考虑风险的srlgi的集合和不需要考虑风险的 srlgi的集合在计算保护路由时，对于不需要考虑风险的 srlgi，其条件风险分离度置 1，即对任意

Step4删除工作路由经过的内部光路，域间物理链路及节点，使用Dijkstra-improved算法计算保护路由。此处，Dijkstra-improved算法使用的双尺度是（P, C），其中表示内部光路q的条件风险分离度；内部光路q的代价表示为表示内部光路q的剩余带宽容量。

至此，源RC通过在聚合网络上运行端到端工作/保护路由算法，向源节点返回包含端到端工作/保护路由的响应消息，随后源节点发起资源预留请求。

4 仿真与数值分析

为了验证多域光网络中应用条件风险分离度的生存性策略的性能，以图2所示多域光网络为参考拓扑进行仿真。图2所示多域光网络包含28个节点和 46条物理链路，每条物理链路由一对方向相反的单向光纤组成，每根光纤支持8个波长，单域边界节点具备波长转换能力。

设网络链路的可靠性随机分布在0.8～1.0之间，链路的条件故障概率随机为 0.1、0.2和 0.5。连接请求表示为R(s, d, B, R)，s和d分别是业务请求的源、目的节点，B为请求带宽，R是业务请求可靠度且随机分布在0.85～1.0之间。所有业务请求的源、宿节点对随机生成，且连接请求按照平均速率服从参数为λ的泊松分布独立到达网络各节点，业务连接的持续时间服从均值为1/μ的负指数分布，网络总负载为 λ/μ。算法依据业务请求可靠度 R建立光路，如果没有成功，则连接阻塞，不存在排队现象。

在仿真时，对于不同的网络负载，分别产生106次业务连接请求，使用统计方法进行分析。

1) 仿真首先研究了所提生存性策略的阻塞率特性。为了更直观地表现所提策略的优势，同等条件下引入了2种已有技术：考虑物理分离的多域层次路由（MHR）算法和未区分业务可靠性的多域风险分离（SD）算法。

图5比较了不同网络负载下所提生存性策略和MHR、SD的阻塞率特性，由于所设计仿真网络每条物理链路只支持8个波长，网络资源有限，当网络负载较大时，导致阻塞率偏高。

图5 算法的阻塞率性能分析

由图5可知，在网络负载相同的情况下，所提生存性策略的阻塞率总是介于 SD和 MHR之间，这是因为相比 SD算法，本文所提生存性策略在搜索路由时，并不是直接将那些与工作路由经过的链路具有相同SRLG标识的链路删除，而是基于CRDD选路，这大大增加了可用资源的使用效率，从而提高了建路成功的概率；另一方面，由于MHR算法只考虑了工作/保护路由的物理分离，所以在计算保护路由时获得了相对较广的可选网络资源，得到了比本文所提生存性策略稍低的阻塞率。

同时，从图5还可以发现，在网络负载较轻的情况下，所提生存性策略的阻塞率非常低，显示出它的建路能力丝毫不逊于考虑物理分离的MHR算法。

2) 仿真同时也对所提生存性策略区分可靠性的能力进行了研究。图6统计了实际成功建立的工作路由的可靠度分布。

图6 实际工作通路的可靠度分析

业务连接的请求可靠度在 0.924～0.962之间随机取值，由图6可见，实际工作路由的可靠度集中分布在 0.991～0.998之间，提高了网络生存性，并且对于可靠性要求高的业务成功建立的工作路由的可靠度也相对较高，保证了区分业务可靠性的性能指标。同时，随着网络负载的增加，实际连接的可靠度呈现微弱下降的趋势，说明当网络负载增大时，对所提生存性策略的影响较为明显。

5 结束语

可靠性是衡量网络生存性的重要参数，考虑多域网环境缺乏完整的关于网络拓扑和带宽分配的信息，本文引入CRDD，提出基于CRDD的域内虚链路映射算法构建的抽象拓扑，在抽象拓扑上应用基于CRDD的端到端工作/保护路由算法，区分业务可靠性，为业务建立工作/保护路由对。仿真结果表明，相比先前的多域光网络生存性技术，该策略很好地实现了区分业务可靠性的目的，有效地降低了网络阻塞率，而且能够提供平均高于业务请求6.5%的可靠性。同时，作为区分业务可靠性的的手段，CRDD的概念也可以应用在单域光网络和多层网络中。

[1] IETF RFC 4726. A Framework for Inter-domain MPLS Traffic Engineering[S].

[2] SARADHI C V, RAMAMURTHY B, SCHUPKE D A, et al. Guest editorial-multidomain optical networks∶ issues and challenges[J]. IEEE Communications Magazine, 2008,46(6)∶ 76-77.

[3] PICKAVET M, AUDENAERT P, VANHAVERBEKE J, et al. Optimizing reliable multidomain optical routing[A]. 2006 International Conference on Transparent Optical Networks[C]. Nottingham，Britain,2006. 1-4.

[4] ZHAO J H, MAO H B, QU H. Research on survivability in multi-service-based multi-domain optical networks[A]. 11th International Conference on Advanced Communication Technology[C].Phoenix Park, Phoenix Park, Republic of Korea, 2009. 161-165.

[5] TAKEDA T, IKEJIRI Y, FARREL A, et al. Analysis of inter-domain label switched path (LSP) recovery[EB/OL]. http∶//tools.ietf.org/html/draft- ietf-ccamp-inter-domain-recovery-analysis-03,2008.

[6] 赵季红, 曲桦. 基于约束的 GMPLS恢复算法[J]. 电子科技大学学报, 2005,34(1)∶101-104.ZHAO J H, QU H. GMPLS recovery algorithm based on constrained[J]. Journal of University of Electronic Science and Technology of China, 2005, 34 (1)∶ 101-104.

[7] IETF RFC 4105. Requirements for Inter-Area MPLS Traffic Engineering[S].

[8] PAPADIMITRIOU D, POPPE F, JONES J, et al. Inference of shared risk link groups[EB/OL]. http∶//tools.ietf.org/html/draft-many- inferencesrlg-02. 2001,11.

[9] 虞红芳, 温海波, 王晟等. 网状WDM网中支持区分可靠性的共享通路保护算法[J].电子与信息学报, 2005,27(8)∶1295-1298.YU H F, WEN H B, WANG S, et al. Shared-path protection algorithm with differentiated reliability in mesh WDM networks[J]. Journal of Electronics & Information Technology, 2005,27(8)∶ 1295-1298.

[10] 谢晖, 曹振海, 钱松荣. 一种基于SRLG条件失败概率限制的保护算法[J]. 计算机工程与设计, 2004,10(34)∶ 1742-1744.XIE H, CAO Z H, QIAN S R. Path-protection algorithm under conditional failure probability of SRLG constrains[J]. Computer Engineering and Design, 2004,10(34)∶1742-1744.

[11] 周韬, 郭磊, 虞红芳. WDM光网络中一种不共享风险的路由算法[J].电子科技大学学报, 2006,35(4)∶440-442.ZHOU T, GUO L, YU H F. A routing algorithm with no-shared-risk for wdm optical networks[J]. Journal of University of Electronic Science and Technology of China, 2006,35(4)∶440-442.

[12] Implementation Agreement E-NNI OSPF-based routing-1.0 (Intra-Carrier)[EB/OL]. http∶//www.oiforum. com/public/documents/OIFENNI-OSPF-01.0.pdf, 2007.

[13] 张仁平, 周庆忠, 熊伟. A*算法改进算法及其应用[J]. 计算机系统应用,2009,9(27)∶99-100.ZHANG R P, ZHOU Q Z, XIONG W. Updated A* algorithm and application[J]. Applications of the Computer Systems, 2009, 9(27)∶99-100.