劉 非，褚兵兵，沈建華

（南京郵電大學(xué)通信與信息工程學(xué)院，南京 210003）

基于智能P圈的多播業(yè)務(wù)光保護(hù)方案

劉 非，褚兵兵，沈建華

（南京郵電大學(xué)通信與信息工程學(xué)院，南京 210003）

生存性是WDM（波分復(fù)用）光網(wǎng)絡(luò)的核心技術(shù)之一，對(duì)多播業(yè)務(wù)而言，IpC（智能P圈保護(hù)）是一種具有快速、高效等特點(diǎn)的保護(hù)算法。文章提出一種EIpC（增強(qiáng)型智能P圈）保護(hù)方案，包括分段和路徑IpC算法，分段和路徑IpC算法分別為每個(gè)分段和路徑尋找新的P圈。理論分析和仿真結(jié)果表明，路徑IpC在資源利用率、P圈構(gòu)造個(gè)數(shù)以及圈平均覆蓋度等方面最優(yōu)，分段IpC次之，傳統(tǒng)（鏈路）IpC最低。在先驗(yàn)效率方面，鏈路IpC最優(yōu)，分段IpC次之，路徑IpC最低。

波分復(fù)用；生存性；多播；P圈

0 引 言

在WDM（波分復(fù)用）網(wǎng)絡(luò)中研究支持多播業(yè)務(wù)的生存性機(jī)制已成為業(yè)界高度關(guān)注的重點(diǎn)［1］。光網(wǎng)絡(luò)中的多播連接需要將信息從源節(jié)點(diǎn)通過全光通路傳送到多個(gè)目的節(jié)點(diǎn)，利用分光器可以構(gòu)建樹狀路由來傳送多播連接。因此可將多播保護(hù)技術(shù)分為鏈路保護(hù)、自共享保護(hù)、分段保護(hù)以及路徑保護(hù)等［2-5］。大量文獻(xiàn)證明，光網(wǎng)絡(luò)中單鏈路故障是各類業(yè)務(wù)失效的主要原因，因此本文主要關(guān)注支持多播業(yè)務(wù)的光網(wǎng)絡(luò)中單鏈路故障及其對(duì)策。

P圈是一種高效的光網(wǎng)絡(luò)保護(hù)策略，具有快速的環(huán)網(wǎng)恢復(fù)速度和有效的網(wǎng)狀恢復(fù)容量等特點(diǎn)［6］。DpC（動(dòng)態(tài)P圈）方案是從候選P圈中選擇P圈來保護(hù)多播樹［7］，其缺點(diǎn)是候選P圈為預(yù)先計(jì)算，無法滿足動(dòng)態(tài)恢復(fù)的要求。IpC（智能P圈）方案是在多播樹建立后，為多播樹上每條鏈路動(dòng)態(tài)計(jì)算P圈［8］，其缺點(diǎn)是基于鏈路保護(hù)的特征需占用較多的網(wǎng)絡(luò)資源。本文提出了一種EIpC（增強(qiáng)型智能P圈）保護(hù)方案，包含分段和路徑IpC，能提供基于分段和路徑的保護(hù)。

1 EIpC工作原理

1.1分段IpC算法

假定WDM網(wǎng)狀網(wǎng)的物理拓?fù)錇镚=（V，E），其中V為節(jié)點(diǎn)集，E為鏈路集。給定一個(gè)多播請(qǐng)求r（s，D），其中s是該多播請(qǐng)求的源節(jié)點(diǎn)，D=｛d1，d2，…，dk｝表示該多播請(qǐng)求的目的節(jié)點(diǎn)集合，k表示該多播請(qǐng)求的目的節(jié)點(diǎn)個(gè)數(shù)。當(dāng)多播請(qǐng)求r到達(dá)時(shí)，建立多播樹T，T上的鏈路集合表示為ET，分段集合表示為ED。分段IpC算法的主要目標(biāo)為：建立P圈集合PC以使ED中每個(gè)分段都可以被集合中的P圈保護(hù)。

當(dāng)有向分段u→v是P圈的跨接分段或分段v→u在P圈上時(shí)，該分段可以被該P(yáng)圈保護(hù)，即若節(jié)點(diǎn)u和節(jié)點(diǎn)v均在P圈上，則該P(yáng)圈可以保護(hù)該分段。假設(shè)多播樹T建立后，P圈c可以保護(hù)T上的某些分段。定義先驗(yàn)效率ERD為

式中，PS（c）表示ED中可以被c保護(hù)的元素集合，|c|表示c中的鏈路數(shù)目。ERD值越大，c的效率越高。該方案具體流程如下：

（1）對(duì)于ED中的每個(gè)分段，有兩種方法對(duì)其進(jìn)行保護(hù)：即為其找一條新的P圈或者擴(kuò)展集合PC中已有的P圈；

（2）找到步驟（1）所有P圈中ERD值最大的P 圈p，將p加入集合PC并移除ED中所有被P圈保護(hù)的元素；

（3）將p與PC中的其他P圈混合以減少P圈使用的波長；

（4）當(dāng)集合ED為空時(shí)，PC即為所求；否則，重復(fù)上述步驟。

1.2路徑IpC算法

當(dāng)多播請(qǐng)求到達(dá)時(shí)，多播樹T被建立，T上的路徑集合表示為EP。定義先驗(yàn)效率ERP為

式中，PP（c）表示EP中可以被c保護(hù)的元素集合。ERP值越大，c的效率越高。

對(duì)于多播樹T，路徑IpC算法主要目標(biāo)為：建立P圈集合PC，以使EP中每條路徑都可以被集合中的P圈保護(hù)。該方案的具體流程與分段IpC算法相似，不同點(diǎn)為需要保護(hù)的是EP中的每條路徑。

2 仿真和結(jié)果分析

仿真拓?fù)錇?4個(gè)節(jié)點(diǎn)、20條鏈路的NSFNET（美國國家科學(xué)基金網(wǎng)）。每條鏈路的權(quán)重設(shè)為1，對(duì)于每個(gè)多播請(qǐng)求，隨機(jī)選擇源節(jié)點(diǎn)和目的節(jié)點(diǎn)。當(dāng)多播請(qǐng)求到達(dá)時(shí)，使用Prim（普里姆）算法建立多播樹。分別對(duì)鏈路IpC、分段IpC和路徑IpC尋找P圈集合。仿真中每次實(shí)驗(yàn)重復(fù)1 000次，并計(jì)算在每個(gè)目的節(jié)點(diǎn)數(shù)目下每種方案所使用的波長總數(shù)、構(gòu)造P圈個(gè)數(shù)總和、圈平均覆蓋度以及平均P圈先驗(yàn)效率。

圖1　三種算法的仿真結(jié)果

圖1所示為三種算法所對(duì)應(yīng)的仿真結(jié)果。由圖可以看出：當(dāng)目的節(jié)點(diǎn)數(shù)變化時(shí)，三種算法使用的波長數(shù)、構(gòu)造P圈個(gè)數(shù)總和及平均P圈先驗(yàn)效率總體呈上升趨勢(shì)。而在目的節(jié)點(diǎn)數(shù)目相同的情況下，路徑IpC具有最佳的資源利用性能和最少的P圈構(gòu)造個(gè)數(shù)，分段IpC次之，鏈路IpC最低；而鏈路IpC的平均先驗(yàn)效率最大以及具有最佳的圈平均覆蓋度，分段IpC次之，路徑IpC最小。

3 結(jié)束語

本文研究了基于智能P圈的保護(hù)方案，提出了包括分段IpC和路徑IpC的EIpC方案，以保護(hù)動(dòng)態(tài)多播業(yè)務(wù)。分段和路徑IpC的主要特點(diǎn)分別是尋找保護(hù)分段或保護(hù)路徑集合中元素的P圈集合。仿真結(jié)果表明，在資源利用率、P圈構(gòu)造個(gè)數(shù)以及圈平均覆蓋度等方面，路徑IpC具有最佳性能；在先驗(yàn)效率方面，鏈路IpC最優(yōu)，分段IpC性能居于路徑和鏈路IpC之間。

［1]Singhal N K，Sahasrabuddhe L H，Mukherjee B.Protecting amulicast session against single link failuresin a mesh network［C］//ICC 2003.Anchorage，US：IEEE，2003：1504-1508.

［2]Singhal N K，Mukherjee B.Protecting mulicast sessions in WDM optical mesh networks［J］.IEEE/OSA Journal of Lightwave Technology，2003，21（4）：884-892.

［3]Lu Cai，Sheng Wang，Li Lemin.A Novel Shared Segment Protection Algorithm for Multicast Sessions in Mesh WDM Networks［J］.ETRI Journal，2006，28 （3）：329-336.

［4]Singhal N K，Sahasrabuddhe L H，Mukherjee B.Provisioning of survivable multicast sessions against single link failures in optical WDM mesh networks［J］.Lightwave Technol，2003，21（11）：2587-2594.

［5]Singhal Narendra K，Caihui Ou.MukherieeCross-sharing vs.self-sharing trees for protecting multicast sessions in mesh networks［J］.Computer Networks，2006，50（2）：200-206.

［6]Grover W，Stamatelakis D.Cycle-oriented distributed preconfiguration：ring-like speed with mesh-like capacity for self-planning network restoration［C］//ICC 1998.Atlanta，US：IEEE，1998：537-543.

［7]Zhang F，Zhong W.Applying p-cycles in dynamic provisioning of survivable multicast sessions in optical WDM networks［C］//OFC 2007.Anaheim，US：IEEE，2007：1-3.

［8]Feng Taiming，Lu Ruan，Zhang Wensheng.Intelligent p-Cycle Protection for Dynamic Multicast Sessions in WDM Networks［J］.Journal of Optical Communications &Networking，2010，2（7）：389-399.

Efficiency-Score Based Intelligent P-cycle Protection of Multicast Sessions in WDM Networks

LIU Fei，CHU Bin-bin，SHEN Jian-hua
（School of Communications and Information Engineering，NJUPT，Nanjing 210003，China）

Survivability is one of the most important promising technologies in Wavelength Division Multiplexing（WDM）networks.The P-cycle based dynamic multicast protection scheme（IpC）is widely accepted as a good solution due to its fast restoration time and high capacity efficiency.This paper presents an improved IpC mechanism named EIpC including both the segment IpC and the path IpC algorithm simultaneously.The main feature of EIpC is to use segment IpC algorithm to find a new P-cycle for a segment and path IpC algorithm to find a new P-cycle for a path，respectively.Theoretical analysis and simulation results show that the path IpC has better performance in resource utilization，the number of P-cycle（s）and the P-cycle＇s average coverage，than the segment IpC and the classical（link）IpC.However，the link IpC has a higher average AE than the segment IpC and the path IpC.

WDM；Survivability；Multicast；P-cycle

TN915.01

A

1005-8788（2016）02-0022-02

10.13756/j.gtxyj.2016.02.007

2015-11-01

劉非（1990-），男，安徽宣城人。碩士研究生，主要研究方向?yàn)楣馔ㄐ排c光網(wǎng)絡(luò)。

沈建華，教授。E-mail：shenjh@njupt.edu.cn。