網(wǎng)狀光網(wǎng)絡預置圈的一種啟發(fā)式構造

安 李, 范九倫

(西安郵電大學 通信與信息工程學院, 陜西 西安 710121)

網(wǎng)狀光網(wǎng)絡預置圈的一種啟發(fā)式構造

安 李, 范九倫

(西安郵電大學 通信與信息工程學院, 陜西 西安 710121)

為了提高預置圈(P圈)先驗效率，減少備選P圈個數(shù)，給出一種基于圈擴張策略的相交圈合并算法。利用跨接鏈路算法計算基礎P圈，在其中找出兩個相交P圈，以及它們之間的相交節(jié)點，對其進行相加合并，生成新的P圈。以先驗效率為篩選標準，將性能較好的新P圈加入備選P圈，丟棄性能較差的P圈。針對Italy和Cost239兩個網(wǎng)絡拓撲進行算法仿真，結(jié)果表明，所給算法能夠提高P圈先驗效率，并將備選P圈個數(shù)減少一半，性能優(yōu)于P圈啟發(fā)式構造算法中的擴展算法(Grow Algorithm)。

光網(wǎng)絡；生存性；預置圈；先驗效率

光通信承載著通信網(wǎng)絡中80%以上的信息流量[1]。利用波分復用技術[2]，單條光纖可以同時發(fā)送多束不同波長的光信息，每束光波最高可達40 Gb/s的數(shù)據(jù)傳輸率[3]。為了保證網(wǎng)絡正常運行，光網(wǎng)絡的生存性技術成為研究熱點。

預置圈(Pre-configuration cycle, P圈)是一種基于環(huán)結(jié)構的格狀網(wǎng)絡保護方案[4]，利用空閑資源預先設置的環(huán)形通道實現(xiàn)對網(wǎng)狀網(wǎng)絡的快速保護。P圈可以同時對圈上鏈路和跨接鏈路提供保護路徑，兼有網(wǎng)狀網(wǎng)絡的高容量效率與環(huán)狀網(wǎng)絡恢復時間短的優(yōu)勢，為網(wǎng)絡生存性技術提供了一個可靠保障。

P圈的構造算法，可以分為完全優(yōu)化算法[5]、聯(lián)合優(yōu)化算法[6]和完全啟發(fā)式算法[7]。完全啟發(fā)式算法過程簡單且計算時間短，是構造P圈的理想選擇。

擴展算法(The Grow Algorithm, Grow算法)[7]是啟發(fā)式P圈構造算法中的一個典型算法，它是一種以跨接鏈路算法(The Straddling Link Algorithm，SLA)[8]和邊增加算法(The Span-Add Algorithm, Sp-Add)[7]為基礎的重復迭代的過程。Grow算法產(chǎn)生的P圈先驗效率高、資源利用率大，但此算法在計算過程中會產(chǎn)生數(shù)目過多的備選P圈，給網(wǎng)絡管理帶來了困難。

本文擬針對Grow算法中的不足，給出一種相交圈合并(Intersecting Cycles Merge, ICM)算法，即以SLA算法所產(chǎn)生的P圈為基礎，尋找兩兩相交的P圈進行合并，并以先驗效率(Prior Efficiency, PE)為篩選標準，丟棄性能較差的P圈，以此降低備選P圈的數(shù)量，解決因Grow算法產(chǎn)生備選P圈過多而帶來的網(wǎng)絡管理問題。

1 P圈評價標準

衡量P圈構造優(yōu)劣的參數(shù)有[9]先驗效率、P圈的個數(shù)、平均跳數(shù)和平均代價。

一個P圈的先驗效率是指被保護的最大工作容量與配置此圈消耗的網(wǎng)絡容量的比值[10]。以S表示P圈中所有鏈路的集合，Xi和Ci分別表示P圈對鏈路i提供的保護路徑數(shù)量和提供保護的代價(代價可以是鏈路的物理距離、費用、帶寬等)，且

則P圈的先驗效率可表示為

由上式可知，P圈的跨接鏈路越多，其先驗效率就越高，潛在的保護效率也就越高，因此，先驗效率越高的P圈，其性能也就越好。

P圈的個數(shù)是衡量P圈性能好壞的第二個重要指標，在不降低先驗效率的前提下，P圈的數(shù)量越少，網(wǎng)絡管理的負擔越小[11]。

2 相交圈合并算法

為了在不影響先驗效率的前提下減少P圈的數(shù)目，先以SLA算法所計算出來的P圈為基礎，通過兩個相交P圈之間的相加，生成新的P圈。

如圖1所示，在圖1(a)中，有兩個相交P圈，第一個P圈節(jié)點為2，3，11，8，5，第二個P圈節(jié)點為5，4，11，10，7，兩個P圈的相交節(jié)點為5和11，以這兩個相交節(jié)點為擴張點,經(jīng)過圈的相加,可以得到圖1(b)中的P圈，其節(jié)點為2，3，11，10，7，5。

(a) 相交P圈

(b) 合并后的P圈

在對兩個相交P圈進行相加運算時，應該選擇相交節(jié)點數(shù)最少的P圈，相交節(jié)點數(shù)越少，得到的新P圈的先驗效率高的可行性就越大。相加完成后，需要比較新P圈與合并前的兩個P圈的先驗效率的大小，若新P圈的先驗效率較大，則將此P圈加入到備選P圈中,否則，舍棄此P圈。算法具體步驟如下。

算法輸入 網(wǎng)絡物理拓撲G=(N,S)，其中N為網(wǎng)絡中所有節(jié)點的集合，S是網(wǎng)絡中所有雙向鏈路的集合。

算法輸出 P圈個數(shù)，平均PE，平均跳數(shù)，平均代價。

步驟1 在網(wǎng)絡中，利用SLA算法構造出一組基礎圈集合A，其元素個數(shù)為M。

步驟2 對A中第i個P圈(i從1開始)尋找與其相交的P圈，并記錄下相交節(jié)點。若相交P圈的個數(shù)大于等于2，選擇相交節(jié)點數(shù)最少的P圈，經(jīng)過圈相加，得到一個新的P圈。

步驟3 判斷新P圈的PE是否大于等于合并前兩個P圈的PE，若是，將新P圈加入備選圈集合，否則，舍棄新P圈，查找并刪除重復圈。

步驟4 計算備選圈集合中P圈個數(shù)M0，若M0>M，更新集合A中P圈個數(shù)M，返回步驟2。否則，不再產(chǎn)生新的P圈，算法結(jié)束。

3 算法性能檢驗

為了檢驗算法性能的好壞，對Italy(21個節(jié)點,36條鏈路)和Cost239(11個節(jié)點,26條鏈路)兩個網(wǎng)絡拓撲(圖2)進行構造P圈的仿真，其中跳數(shù)為圈上鏈路數(shù)，代價為圈上鏈路的物理距離。

(a) Italy網(wǎng)絡

(b) Cost239網(wǎng)絡

表1和表2分別給出了在Italy和Cost239這兩種網(wǎng)絡拓撲中，Grow算法和ICM算法的輸出結(jié)果。

表1 Italy網(wǎng)絡中ICM算法與Grow算法對比

表2 Cost239網(wǎng)絡中ICM算法與Grow算法對比

由表1和表2可見，ICM算法在平均PE和平均跳數(shù)兩指標上略高于Grow算法，在平均代價方面，兩算法基本持平，不相上下，但ICM算法構造的P圈數(shù)近乎是Grow算法所構造P圈數(shù)的一半，其優(yōu)勢較為明顯。

4 結(jié)束語

ICM算法以SLA算法算出的P圈為基礎，通過兩個相交P圈之間的相加，生成新P圈，并對新P圈的質(zhì)量進行判斷，將性能較好的P圈加入到最終的備選圈中。經(jīng)檢驗，該算法在增加先驗效率的同時，可將備選P圈數(shù)目減少約一半，能夠大大降低管理上的負擔。

[1] 韋樂平.光網(wǎng)絡的發(fā)展、演進和面臨的挑戰(zhàn)[J].中興通訊技術,2002,8(4):1-5.

[2] 張亮,鞏稼民,張玲.WDM網(wǎng)中一種考慮優(yōu)先級的多播共享段保護[J].西安郵電學院學報,2010.15(3):43-46.

[3] 鞏稼民,李歡,張博.40Gb/s光通信系統(tǒng)驅(qū)動放大器設計[J].西安郵電大學學報,2014,19(4):85-89.

[4] Grover W D, Stamatelakis D. Cycle-oriented distributed pre-configuration: ring-like speed with mesh-like capacity for self-planning network restoration[C]//Proceedings of International Conference on Communications. Atlanta: IEEE, 1998: 537-543.

[5] Mylonakis S. Optical WDM mesh networks with dedicated optical path protection with finite differences[C]//Proceedings of IEEE 5th International Conference on Networking and Services, Valencia: IEEE,2009:76-85.

[6] Kang B, Habibi D, Lo K, et al. An approach to generate an efficient set of candidate P-cycles in WDM Mesh networks[C]//Proceedings of International Conference on Communications. Busan: IEEE, 2006:1-5.

[7] Doucette J, He D, Grover W D, et al. Algorithmic approaches for efficient enumeration of candidate P-cycles and capacitated P-cycle network design[C]//Proceedings of the 4th International Workshop on the Design of Reliable Communication Networks. Alaska: IEEE, 2003: 212-220.

[8] Zhang Hanxi, Yang O O. Finding protection cycles in DWDM networks[C]//Proceedings of International Conference on Communications. New York: IEEE, 2002: 2756-2760.

[9] 張沛, 鄧宇,黃善國, 等. WDM網(wǎng)絡中P圈保護算法[J]. 北京郵電大學學報,2007,30(1):127-131.

[10] Grover W D, Doucette J. Advances in optical networks design with P-cycles, joint optimization and pre-selection of candidate P-cycles[C]//Proceedings of LEOS Summer Topical Meeting. Quebec Mont Tremblant: IEEE, 2002: 49-50.

[11] Onguetou D P, Grover W D. P-cycle network design: from fewest in number to smallest in size[C]//Proceedings of International Workshop on Design of Reliable Communication Networks. Edmonton: IEEE, 2007: 3161-3168.

[責任編輯:瑞金]

A heuristic construction based on P-cycle in mesh optical network

AN Li, FAN Jiulun

(School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to increase the prior efficiency of pre-configuration cycle(P-cycle), and reduce the number of candidate P-cycles, an intersecting cycles merge algorithm based on cycle expansion strategy is proposed. Firstly, the straddling link algorithm is used to calculate the basic P-cycles. Secondly, two intersecting P-cycles with their intersection nodes are found from the basic P-cycles, and merged into a new one. Thirdly, the prior efficiency is chosen as the standard, the better performance of the new P-cycle is combined with candidate P-cycles, and the poor performance of P-cycle is discarded. Simulation on Italy and Cost239 network topologies show that, the new algorithm can increase the prior efficiency of P-cycles and also reduce the number of candidate P-cycles more than half. Therefore the performance of new algorithm is better than that of the Grow algorithm.

optical networks, survivability, P-cycle, prior efficiency

10.13682/j.issn.2095-6533.2015.04.006

2014-11-07

國家自然科學基金資助項目(61340040，61202183)

安李(1988- )，女，碩士研究生，研究方向為光纖通信。E-mail: 497480556@qq.com 范九倫(1964- ),男，博士，教授，博士生導師，從事模式識別、信號與信息處理等研究。E-mail：jiulunf@163.com

TN929.11

A

2095-6533(2015)04-0029-03