孟永輝，趙斌鋒，劉志強(qiáng)，覃 波

（中國(guó)電子科技集團(tuán)公司 第三十四研究所,廣西 桂林541004）

基于多面體結(jié)構(gòu)的光網(wǎng)絡(luò)多故障恢復(fù)方法

孟永輝，趙斌鋒，劉志強(qiáng)，覃 波

（中國(guó)電子科技集團(tuán)公司 第三十四研究所,廣西 桂林541004）

提出了基于多面體結(jié)構(gòu)的光網(wǎng)絡(luò)多故障恢復(fù)方法，介紹了光網(wǎng)絡(luò)多面體尋找算法的原理，描述了恢復(fù)路徑和保護(hù)路徑計(jì)算的詳細(xì)流程，并給出了恢復(fù)策略。

光網(wǎng)絡(luò)；多面體；多故障；網(wǎng)絡(luò)恢復(fù)

0 引言

流媒體和互動(dòng)多媒體等新型數(shù)據(jù)業(yè)務(wù)的興起和快速發(fā)展使人們對(duì)帶寬和網(wǎng)絡(luò)生存性要求越來越高。傳統(tǒng)的基于同步數(shù)字體系（SDH）環(huán)網(wǎng)的組網(wǎng)方式只能有效對(duì)抗單點(diǎn)（單鏈路）網(wǎng)絡(luò)故障，無法對(duì)抗多點(diǎn)（多鏈路）網(wǎng)絡(luò)故障[1]。因此，基于自動(dòng)交換光網(wǎng)絡(luò)（ASON）的多層多域光網(wǎng)絡(luò)結(jié)構(gòu)成為必然發(fā)展趨勢(shì)?；贏SON的傳送網(wǎng)能有效提供光層網(wǎng)絡(luò)的專用保護(hù)和動(dòng)態(tài)恢復(fù)[2]，但專用保護(hù)本身要占用比工作通道還要多的網(wǎng)絡(luò)資源，資源利用率太低，且分離多域光網(wǎng)絡(luò)中工作／保護(hù)通道的共享風(fēng)險(xiǎn)鏈路組（SRG）比較困難，難以實(shí)現(xiàn)多故障網(wǎng)絡(luò)的快速恢復(fù)。

W.D.Grover教授提出利用空閑資源預(yù)先設(shè)置環(huán)形通道（P圈）來實(shí)現(xiàn)網(wǎng)狀網(wǎng)絡(luò)的快速恢復(fù)[3]。在單故障情況下，P圈中的哈密頓圈能達(dá)到最優(yōu)的資源利用率。但是，要恢復(fù)多條并發(fā)鏈路的故障就要求物理拓?fù)渲械拿織l鏈路都處在多條物理路徑不相交的P圈中，在多故障情況下至少有一個(gè)P圈沒有受到故障影響。根據(jù)理論證明可以得出，針對(duì)多故障情況下的P圈組合并不能達(dá)到最優(yōu)的保護(hù)資源利用率[4]。為解決此問題，本文提出基于多面體結(jié)構(gòu)的光網(wǎng)絡(luò)多故障恢復(fù)方法。

1 多面體結(jié)構(gòu)的光網(wǎng)絡(luò)多故障恢復(fù)流程

在基于多面體結(jié)構(gòu)的光網(wǎng)絡(luò)中，多故障恢復(fù)方法的核心步驟是計(jì)算恢復(fù)路徑，本文首先通過網(wǎng)絡(luò)拓?fù)浜凸收湘溌穼ふ揖W(wǎng)絡(luò)中存在的哈密頓圈多面體，得出故障發(fā)生后網(wǎng)絡(luò)的連通情況，然后通過不相交路徑算法得到恢復(fù)路徑和恢復(fù)路徑的保護(hù)路徑，最后根據(jù)恢復(fù)策略完成工作路徑的恢復(fù)。具體恢復(fù)流程如圖1所示。

圖1 基于多面體結(jié)構(gòu)的光網(wǎng)絡(luò)多故障恢復(fù)流程

2 光網(wǎng)絡(luò)多面體尋找算法

2.1 網(wǎng)絡(luò)拓?fù)?/p>

本文以初始網(wǎng)絡(luò)為例，介紹網(wǎng)絡(luò)中多面體的尋找算法，具體網(wǎng)絡(luò)拓?fù)鋱D如圖2所示。網(wǎng)絡(luò)由11個(gè)物理鏈路節(jié)點(diǎn)和25條物理鏈路組成，假設(shè)每條鏈路的資源以波長(zhǎng)為單位，不需要考慮波長(zhǎng)連續(xù)型限制。網(wǎng)絡(luò)中并發(fā)出現(xiàn)的鏈路故障數(shù)目為3，3條故障鏈路隨機(jī)在25條物理鏈路上并發(fā)出現(xiàn)。

圖2 初始網(wǎng)絡(luò)拓?fù)?/p>

2.2 算法描述

假設(shè)在原物理拓?fù)渲墟溌?-10,3-4和6-9出現(xiàn)故障，要得到恢復(fù)路徑，就要先根據(jù)故障鏈路修改網(wǎng)絡(luò)的流量工程數(shù)據(jù)庫(kù)尋找存在哈密頓圈（從某一節(jié)點(diǎn)出發(fā)不重復(fù)地走過所有節(jié)點(diǎn)，最后又回到原節(jié)點(diǎn)）的多面體，再根據(jù)得到的多面體計(jì)算恢復(fù)路徑。

本文采用貪婪算法來尋找多面體圈圖，算法如下：①令S為初始網(wǎng)絡(luò)G中任一節(jié)點(diǎn)，以S為源節(jié)點(diǎn)，從S節(jié)點(diǎn)出發(fā)，不重復(fù)地經(jīng)過各節(jié)點(diǎn)和路徑，遍歷網(wǎng)絡(luò)G中的所有節(jié)點(diǎn)后回到源節(jié)點(diǎn)S，則該節(jié)點(diǎn)序列為哈密頓圈。②重復(fù)步驟①，找出所有以S為源節(jié)點(diǎn)的哈密頓圈序列。③以與S節(jié)點(diǎn)相連接的某一節(jié)點(diǎn)為源節(jié)點(diǎn)，重復(fù)以上步驟，找出以該節(jié)點(diǎn)為源節(jié)點(diǎn)的哈密頓圈序列。④重復(fù)步驟③，遍歷所有節(jié)點(diǎn)，直至找出網(wǎng)絡(luò)中所有的哈密頓圈圖。⑤所得的哈密頓圈圖構(gòu)成的網(wǎng)絡(luò)即為尋找得到的多面體圈。算法返回找到的多面體圈圖如圖3所示。

圖3 算法返回的多面體圈圖

3 恢復(fù)路徑的計(jì)算

恢復(fù)路徑的計(jì)算主要包括計(jì)算恢復(fù)路徑和恢復(fù)路徑的保護(hù)路徑，為保證網(wǎng)絡(luò)恢復(fù)的魯棒性和可靠性，這兩條路徑應(yīng)該是完全不相關(guān)的。因此，本文引入不相交路徑。

3.1 不相交路徑

不相交路徑指兩條路徑的鏈路不相交，也就是說一條路徑的任何鏈路故障對(duì)另一條鏈路都沒任何影響。不相交路徑示意圖如圖4所示，若域1中的節(jié)點(diǎn)1表示為域11，則在兩個(gè)域中,工作路徑為域11→域14→域15→域23→域22，保護(hù)路徑為域11→域12→域13→域21→域22。這兩條路徑在域內(nèi)和域間都不相交，這兩條路徑即為不相交路徑。

圖4 不相交路徑

3.2 恢復(fù)路徑和保護(hù)路徑的計(jì)算

恢復(fù)路徑和其保護(hù)路徑應(yīng)該是不相交的。不相交路徑的計(jì)算思路是先獲得工作路徑，修改流量工程數(shù)據(jù)庫(kù)，再根據(jù)修改后的流量工程數(shù)據(jù)庫(kù)計(jì)算恢復(fù)路徑，得到的恢復(fù)路徑和工作路徑即為不相交的[5]。具體步驟如下：

①根據(jù)原工作路徑，確定恢復(fù)路徑的源端和宿端。②根據(jù)相應(yīng)的路徑計(jì)算算法，計(jì)算出恢復(fù)路徑。③根據(jù)恢復(fù)路徑的資源占用情況修改臨時(shí)流量工程數(shù)據(jù)庫(kù)，即將恢復(fù)路徑的鏈路狀態(tài)設(shè)置為不可用。④基于修改后的臨時(shí)流量工程數(shù)據(jù)庫(kù)，利用步驟①確定的源端和宿端，再次調(diào)用相應(yīng)路徑計(jì)算算法，計(jì)算出一條與恢復(fù)路徑不相交的保護(hù)路徑。

4 恢復(fù)策略

計(jì)算出恢復(fù)路徑后，即可將故障鏈路切換到恢復(fù)路徑，實(shí)現(xiàn)業(yè)務(wù)的恢復(fù)和暢通。在鏈路故障修復(fù)前，應(yīng)再設(shè)置相應(yīng)的保護(hù)路徑，避免再次發(fā)生網(wǎng)絡(luò)故障時(shí)影響業(yè)務(wù)暢通。網(wǎng)絡(luò)故障修復(fù)后，經(jīng)過等待恢復(fù)時(shí)間,業(yè)務(wù)從恢復(fù)路徑返回至原工作路徑，除保護(hù)路徑外，釋放恢復(fù)時(shí)占用的網(wǎng)絡(luò)資源。

5 結(jié)束語

網(wǎng)絡(luò)發(fā)生多點(diǎn)故障時(shí)，傳統(tǒng)的保護(hù)恢復(fù)方法將不可靠，為保證業(yè)務(wù)的暢通，本文將多面體結(jié)構(gòu)和光網(wǎng)絡(luò)多故障恢復(fù)方法結(jié)合，通過尋找存在哈密頓圈的多面體，利用不相交路徑計(jì)算方法得到恢復(fù)路徑，實(shí)現(xiàn)了光網(wǎng)絡(luò)多故障業(yè)務(wù)的恢復(fù)。

[1]毛宏寶,趙季紅.多域光網(wǎng)絡(luò)生存性的關(guān)鍵技術(shù)研究[J].量子電子學(xué)報(bào),2009,26(2)：243-251.

[2]張杰,徐云斌,宋鴻升,等.自動(dòng)交換光網(wǎng)絡(luò)[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]韓大海,沈劍峰,趙時(shí)煜.多層多域光網(wǎng)絡(luò)中針對(duì)群故障的基于PCE架構(gòu)的路由機(jī)制研究[C].天津：全國(guó)第14次光纖通信暨第15屆集成光學(xué)學(xué)術(shù)會(huì)議,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-），男，碩士，工程師，主要從事智能光網(wǎng)絡(luò)技術(shù)方面的工作。