基于多面体结构的光网络多故障恢复方法

孟永辉，赵斌锋，刘志强，覃 波

（中国电子科技集团公司 第三十四研究所,广西 桂林541004）

基于多面体结构的光网络多故障恢复方法

孟永辉，赵斌锋，刘志强，覃 波

（中国电子科技集团公司 第三十四研究所,广西 桂林541004）

提出了基于多面体结构的光网络多故障恢复方法，介绍了光网络多面体寻找算法的原理，描述了恢复路径和保护路径计算的详细流程，并给出了恢复策略。

光网络；多面体；多故障；网络恢复

0 引言

流媒体和互动多媒体等新型数据业务的兴起和快速发展使人们对带宽和网络生存性要求越来越高。传统的基于同步数字体系（SDH）环网的组网方式只能有效对抗单点（单链路）网络故障，无法对抗多点（多链路）网络故障[1]。因此，基于自动交换光网络（ASON）的多层多域光网络结构成为必然发展趋势。基于ASON的传送网能有效提供光层网络的专用保护和动态恢复[2]，但专用保护本身要占用比工作通道还要多的网络资源，资源利用率太低，且分离多域光网络中工作／保护通道的共享风险链路组（SRG）比较困难，难以实现多故障网络的快速恢复。

W.D.Grover教授提出利用空闲资源预先设置环形通道（P圈）来实现网状网络的快速恢复[3]。在单故障情况下，P圈中的哈密顿圈能达到最优的资源利用率。但是，要恢复多条并发链路的故障就要求物理拓扑中的每条链路都处在多条物理路径不相交的P圈中，在多故障情况下至少有一个P圈没有受到故障影响。根据理论证明可以得出，针对多故障情况下的P圈组合并不能达到最优的保护资源利用率[4]。为解决此问题，本文提出基于多面体结构的光网络多故障恢复方法。

1 多面体结构的光网络多故障恢复流程

在基于多面体结构的光网络中，多故障恢复方法的核心步骤是计算恢复路径，本文首先通过网络拓扑和故障链路寻找网络中存在的哈密顿圈多面体，得出故障发生后网络的连通情况，然后通过不相交路径算法得到恢复路径和恢复路径的保护路径，最后根据恢复策略完成工作路径的恢复。具体恢复流程如图1所示。

图1 基于多面体结构的光网络多故障恢复流程

2 光网络多面体寻找算法

2.1 网络拓扑

本文以初始网络为例，介绍网络中多面体的寻找算法，具体网络拓扑图如图2所示。网络由11个物理链路节点和25条物理链路组成，假设每条链路的资源以波长为单位，不需要考虑波长连续型限制。网络中并发出现的链路故障数目为3，3条故障链路随机在25条物理链路上并发出现。

图2 初始网络拓扑

2.2 算法描述

假设在原物理拓扑中链路2-10,3-4和6-9出现故障，要得到恢复路径，就要先根据故障链路修改网络的流量工程数据库寻找存在哈密顿圈（从某一节点出发不重复地走过所有节点，最后又回到原节点）的多面体，再根据得到的多面体计算恢复路径。

本文采用贪婪算法来寻找多面体圈图，算法如下：①令S为初始网络G中任一节点，以S为源节点，从S节点出发，不重复地经过各节点和路径，遍历网络G中的所有节点后回到源节点S，则该节点序列为哈密顿圈。②重复步骤①，找出所有以S为源节点的哈密顿圈序列。③以与S节点相连接的某一节点为源节点，重复以上步骤，找出以该节点为源节点的哈密顿圈序列。④重复步骤③，遍历所有节点，直至找出网络中所有的哈密顿圈图。⑤所得的哈密顿圈图构成的网络即为寻找得到的多面体圈。算法返回找到的多面体圈图如图3所示。

图3 算法返回的多面体圈图

3 恢复路径的计算

恢复路径的计算主要包括计算恢复路径和恢复路径的保护路径，为保证网络恢复的鲁棒性和可靠性，这两条路径应该是完全不相关的。因此，本文引入不相交路径。

3.1 不相交路径

不相交路径指两条路径的链路不相交，也就是说一条路径的任何链路故障对另一条链路都没任何影响。不相交路径示意图如图4所示，若域1中的节点1表示为域11，则在两个域中,工作路径为域11→域14→域15→域23→域22，保护路径为域11→域12→域13→域21→域22。这两条路径在域内和域间都不相交，这两条路径即为不相交路径。

图4 不相交路径

3.2 恢复路径和保护路径的计算

恢复路径和其保护路径应该是不相交的。不相交路径的计算思路是先获得工作路径，修改流量工程数据库，再根据修改后的流量工程数据库计算恢复路径，得到的恢复路径和工作路径即为不相交的[5]。具体步骤如下：

①根据原工作路径，确定恢复路径的源端和宿端。②根据相应的路径计算算法，计算出恢复路径。③根据恢复路径的资源占用情况修改临时流量工程数据库，即将恢复路径的链路状态设置为不可用。④基于修改后的临时流量工程数据库，利用步骤①确定的源端和宿端，再次调用相应路径计算算法，计算出一条与恢复路径不相交的保护路径。

4 恢复策略

计算出恢复路径后，即可将故障链路切换到恢复路径，实现业务的恢复和畅通。在链路故障修复前，应再设置相应的保护路径，避免再次发生网络故障时影响业务畅通。网络故障修复后，经过等待恢复时间,业务从恢复路径返回至原工作路径，除保护路径外，释放恢复时占用的网络资源。

5 结束语

网络发生多点故障时，传统的保护恢复方法将不可靠，为保证业务的畅通，本文将多面体结构和光网络多故障恢复方法结合，通过寻找存在哈密顿圈的多面体，利用不相交路径计算方法得到恢复路径，实现了光网络多故障业务的恢复。

[1]毛宏宝,赵季红.多域光网络生存性的关键技术研究[J].量子电子学报,2009,26(2)：243-251.

[2]张杰,徐云斌,宋鸿升,等.自动交换光网络[M].北京：人民邮电出版社, 2004.

[3]SZIGETI J,ROMERAL R,CINKLER T,et al.P-cycle Protection in multi-domain optical networks[J].Photonic Network Communication, 2009,17(1)：35-47.

[4]韩大海,沈剑峰,赵时煜.多层多域光网络中针对群故障的基于PCE架构的路由机制研究[C].天津：全国第14次光纤通信暨第15届集成光学学术会议,2009.

[5]ZHANG Q,HASAN M M,WANG X,et al.Efficient PCE-based survivable Path Computation in multi-domain networks[C].Shanghai：Computer Communications Workshops(INFOCOM WKSHPS),Conference on IEEE,2011.

Multi-failure restoration method of optic network based on the polyhedron structure

MENG Yong-hui，ZHAO Bin-feng，LIU Zhi-qiang,QIN Bo
(The 34th Research Institute of CETC,Guilin Guangxi 541004,China)

The paper proposes the multi-failure restoration method of optic network based on the polyhedron structure,introduces the principle of the optical network polyhedron search algorithm,the describes the details of the protection path and restoration path compution,and gives the recovery strategy.

optic network,polyhedron,multi-failure,network restoration

TN929.11

A

1002-5561（2016）04-0017-02

10.13921/j.cnki.issn1002-5561.2016.04.006

2015-12-21。

孟永辉（1981-），男，硕士，工程师，主要从事智能光网络技术方面的工作。