基于分層路徑計(jì)算單元與雙矩陣博弈的多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)算法

陳 浩，吳啟武，李 芳，姜靈芝

(1.武警工程大學(xué) 研究生大隊(duì), 西安 710086； 2.武警工程大學(xué) 裝備管理與保障學(xué)院，西安 710086；3.武警工程大學(xué) 信息工程學(xué)院，西安 710086)(*通信作者電子郵箱chenhaoyan14@163.com)

0 引言

隨著主干光網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，整體多域化特征越來(lái)越明顯; 同時(shí)，光層組播是一種高效的點(diǎn)對(duì)多點(diǎn)或者多點(diǎn)對(duì)多點(diǎn)業(yè)務(wù)的通信模式。組播業(yè)務(wù)根據(jù)組播請(qǐng)求需求可以分為靜態(tài)和動(dòng)態(tài)組播兩種: 靜態(tài)組播業(yè)務(wù)是指預(yù)先知道網(wǎng)絡(luò)的全局狀態(tài)，網(wǎng)絡(luò)系統(tǒng)對(duì)一組請(qǐng)求統(tǒng)一調(diào)度，沒(méi)有實(shí)時(shí)性要求; 動(dòng)態(tài)組播業(yè)務(wù)是指組播請(qǐng)求隨機(jī)到達(dá)，具有實(shí)時(shí)性，并在請(qǐng)求存續(xù)期間對(duì)保護(hù)能力有一定要求，通常需要逐個(gè)請(qǐng)求進(jìn)行保護(hù)配置。光網(wǎng)絡(luò)生存性是指當(dāng)光網(wǎng)絡(luò)系統(tǒng)出現(xiàn)故障或惡意攻擊時(shí)，能夠通過(guò)各種手段維持服務(wù)或者恢復(fù)業(yè)務(wù)[1]。光網(wǎng)絡(luò)生存性技術(shù)一般分為保護(hù)和恢復(fù)，其中保護(hù)技術(shù)可分為點(diǎn)對(duì)點(diǎn)保護(hù)、環(huán)狀網(wǎng)保護(hù)和網(wǎng)狀網(wǎng)保護(hù)。專用保護(hù)屬于點(diǎn)對(duì)點(diǎn)保護(hù)，是指為光網(wǎng)絡(luò)上的業(yè)務(wù)路徑配置一條專門的保護(hù)路徑，一旦發(fā)生故障可以直接切換至保護(hù)路徑，快速恢復(fù)業(yè)務(wù)傳輸。組播1+1保護(hù)指對(duì)光組播業(yè)務(wù)實(shí)施專用保護(hù)，利用兩條路徑同時(shí)傳輸相同業(yè)務(wù)，確保任意時(shí)刻有一條路徑上的業(yè)務(wù)實(shí)現(xiàn)正常傳輸。

針對(duì)多域光網(wǎng)絡(luò)靜態(tài)保護(hù)，國(guó)內(nèi)外的研究人員提出各種優(yōu)化方案。文獻(xiàn)[2]的配置方式使其具備生存能力，能夠消耗較少的波長(zhǎng)為組播請(qǐng)求提供保護(hù)，但是在復(fù)雜拓?fù)渖线\(yùn)行時(shí)間顯著增加, 而且作者并未考慮阻塞率這一重要評(píng)價(jià)指標(biāo)。文獻(xiàn)[3]提出在組播樹(shù)中應(yīng)用單播1+1保護(hù)的理念，利用邏輯或以及允許中間節(jié)點(diǎn)合并輸入流來(lái)解決瞬時(shí)故障，從而提高成本效率, 為此提出了兩種啟發(fā)式算法，分別為最小路徑對(duì)啟發(fā)式(Minimum Path-Pair Heuristic, MPPH)算法、最小路徑和最小路徑對(duì)啟發(fā)式(Minimum Path Heuristic + Minimum Path-Pair Heuristic, MPH+MPPH)算法。在雙倍資源消耗的情況下保障了網(wǎng)絡(luò)不中斷，但是本文僅僅設(shè)想了靜態(tài)組播業(yè)務(wù)流量，并沒(méi)有結(jié)合算法予以分析說(shuō)明，而且是在單域環(huán)境中的組播保護(hù)，沒(méi)有涉及復(fù)雜的多域網(wǎng)絡(luò)。文獻(xiàn)[4]提出了一個(gè)結(jié)合應(yīng)用層和光層的雙層優(yōu)化問(wèn)題，在光層提供了一個(gè)專用路徑保護(hù)，但是作者僅僅設(shè)想了靜態(tài)單播業(yè)務(wù)需求的優(yōu)化問(wèn)題，并沒(méi)有針對(duì)靜態(tài)組播業(yè)務(wù)的生存能力進(jìn)行優(yōu)化。文獻(xiàn)[5]基于網(wǎng)絡(luò)運(yùn)營(yíng)商和用戶之間非合作型競(jìng)爭(zhēng)建立博弈論模型，并針對(duì)靜態(tài)業(yè)務(wù)進(jìn)行仿真，但是當(dāng)優(yōu)質(zhì)鏈路被哄搶時(shí)運(yùn)營(yíng)商的價(jià)格策略不能及時(shí)調(diào)整會(huì)導(dǎo)致阻塞率上升。

對(duì)于動(dòng)態(tài)組播保護(hù)：文獻(xiàn)[6]提出了一種多播多域?qū)Ｓ帽Ｗo(hù)(Multicast Multi-domain Dedicated Protection, MMDP)啟發(fā)式算法，動(dòng)態(tài)更新域內(nèi)路徑對(duì)，提升基于多域邏輯拓?fù)涞挠蜷g路由的成功率；文獻(xiàn)[7]基于用戶對(duì)光網(wǎng)絡(luò)服務(wù)質(zhì)量(Quality of Service, QoS)需求、支付費(fèi)用和網(wǎng)絡(luò)供應(yīng)商的利潤(rùn)、網(wǎng)絡(luò)負(fù)載均衡等因素設(shè)計(jì)了博弈路由和博弈保護(hù)機(jī)制。針對(duì)動(dòng)態(tài)業(yè)務(wù)設(shè)計(jì)了波分復(fù)用(Wavelength Division Multiplexing, WDM)多域光網(wǎng)絡(luò)單播和組播保護(hù)算法，但是當(dāng)業(yè)務(wù)強(qiáng)度增大后，共享保護(hù)的比例增大，算法的效用函數(shù)下降。文獻(xiàn)[8]提出了包含多個(gè)QoS參量的多域網(wǎng)絡(luò)模型，結(jié)合菌群優(yōu)化思想提出兩種混合保護(hù)算法，分別是域內(nèi)子路徑保護(hù)(Intra-domain Sub-path Protection, ISP)算法和域間端到端保護(hù)(Inter-domain End-to-end Protection, IEP)算法，ISP算法有更好的資源利用率、更低的阻塞率和更高的運(yùn)營(yíng)商效用，但是ISP算法設(shè)想域間鏈路有額外專用保護(hù)路徑，避開(kāi)了域間鏈路保護(hù)優(yōu)化問(wèn)題；文獻(xiàn)[9-10]針對(duì)多域光網(wǎng)絡(luò)組播業(yè)務(wù)，基于路徑計(jì)算單元 (Path Computation Element, PCE)架構(gòu)提出了一種多域最小代價(jià)路徑啟發(fā)式(Multi-Domain Minimum-cost Path Heuristic, MDMPH)算法，能夠計(jì)算出代價(jià)較小的組播樹(shù)，并比較了3種基于PCE的組播方案，但是二者都未考慮組播業(yè)務(wù)生存能力，僅在組播樹(shù)生成上具有一定意義。

綜合以上研究發(fā)現(xiàn)，針對(duì)多域光網(wǎng)絡(luò)靜態(tài)組播業(yè)務(wù)的專用保護(hù)進(jìn)行的研究?jī)H僅局限在備份路徑的優(yōu)化，忽視了組播樹(shù)和備份樹(shù)聯(lián)合優(yōu)化問(wèn)題。多數(shù)結(jié)合博弈論思想的文獻(xiàn)中，基于用戶和運(yùn)營(yíng)商的對(duì)立關(guān)系進(jìn)行博弈并將結(jié)果作為鏈路的權(quán)值，生成組播樹(shù)后計(jì)算保護(hù)路徑，易造成備份樹(shù)成本過(guò)大，所以本文結(jié)合分層PCE架構(gòu)和雙矩陣博弈思想，在靜態(tài)環(huán)境下綜合考慮組播樹(shù)和組播保護(hù)樹(shù)的資源平衡，提出了一種多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)算法，提高組播業(yè)務(wù)的生存能力。

1 基于分層PCE的多域光網(wǎng)絡(luò)組播模型

PCE是網(wǎng)絡(luò)中負(fù)責(zé)路徑計(jì)算的結(jié)構(gòu)單元，計(jì)算處理能力強(qiáng)大，是多域光網(wǎng)絡(luò)中路徑計(jì)算問(wèn)題的常用解決方案[10]。本文采用分層式PCE架構(gòu)方案，由一個(gè)pPCE(parent-PCE)和多個(gè)cPCE(child-PCE)構(gòu)成，如圖1所示。給定3個(gè)域的多域光網(wǎng)絡(luò)G=(14,27)和一個(gè)組播請(qǐng)求R={1;3,6,13}，即源節(jié)點(diǎn)為V1，目的節(jié)點(diǎn)為V3、V6、V13，則處理請(qǐng)求R建立組播路徑的步驟如下：

① 首先源節(jié)點(diǎn)V1查看本域內(nèi)拓?fù)湫畔?，發(fā)現(xiàn)只有目的節(jié)點(diǎn)V3在本域內(nèi)則計(jì)算源節(jié)點(diǎn)V1至目的節(jié)點(diǎn)V3的路徑，發(fā)送給pPCE。

② 根據(jù)cPCE的路由信息，目的節(jié)點(diǎn)V6和V13不在域1即Domain 1內(nèi)，則源節(jié)點(diǎn)向cPCE1發(fā)送跨域路徑計(jì)算請(qǐng)求，然后cPCE1轉(zhuǎn)發(fā)給pPCE。由pPCE首先向各域cPCE廣播剩余目的節(jié)點(diǎn)地址，確定目的節(jié)點(diǎn)V6和V13所在域即Domain 2和Domain 3，然后pPCE計(jì)算一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的光路，并向域1、域2和域3的cPCE發(fā)送算路指令，即要求計(jì)算各域內(nèi)源節(jié)點(diǎn)到邊界節(jié)點(diǎn)的光路、進(jìn)邊界節(jié)點(diǎn)和出邊界節(jié)點(diǎn)間光路、邊界節(jié)點(diǎn)與目的節(jié)點(diǎn)間路徑。

③ 各相關(guān)cPCE完成的光路計(jì)算后提交pPCE，由pPCE記錄路由合并全部路徑段，得到多條橫跨各域的路徑，然后基于約束條件選擇最優(yōu)路徑，將最終結(jié)果發(fā)送各cPCE。

④ 各cPCE收到來(lái)自pPCE的最終結(jié)果后，開(kāi)始波長(zhǎng)分配, 即完成了跨域路徑的計(jì)算。

⑤ 至此多域光網(wǎng)絡(luò)的組播樹(shù)路徑計(jì)算結(jié)束。

本文采用分層PCE架構(gòu)設(shè)計(jì)，增加了pPCE與cPCE的層級(jí)結(jié)構(gòu)，統(tǒng)一對(duì)光域進(jìn)行管理，能夠在保護(hù)域內(nèi)隱私信息的同時(shí)，滿足多域光網(wǎng)絡(luò)組播業(yè)務(wù)需求。

圖1 分層PCE架構(gòu)

2 多域光網(wǎng)絡(luò)靜態(tài)組播保護(hù)算法

2.1 定義與假設(shè)

博弈論主要研究公式化的激勵(lì)結(jié)構(gòu)間的相互作用，是研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法，是競(jìng)爭(zhēng)環(huán)境下的多人決策理論[11-12]?；诓┺恼摰亩嘤蚬饩W(wǎng)絡(luò)研究大多利用用戶和運(yùn)營(yíng)商之間的零和關(guān)系，對(duì)光網(wǎng)絡(luò)中的鏈路賦予權(quán)值，結(jié)合啟發(fā)式算法進(jìn)行路徑計(jì)算。本文基于分層PCE結(jié)構(gòu)和雙矩陣博弈思想對(duì)多域光網(wǎng)絡(luò)保護(hù)機(jī)制進(jìn)行研究，提出了一種多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)算法。兩個(gè)用戶通過(guò)競(jìng)爭(zhēng)獲得鏈路的使用權(quán)，以得到一對(duì)聯(lián)合評(píng)價(jià)最優(yōu)的路徑對(duì)的方式建立組播樹(shù)和組播保護(hù)樹(shù)。

定義1 定義多域光網(wǎng)絡(luò)G′(V,E)，其中Vs、Vd∈V，V是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合V={V1,V2,…,Vn}。節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vj間的鏈路表示為eij，E是網(wǎng)絡(luò)中鏈路的集合E={eij|i,j∈{1,2,…,n}}。定義集合K代表光路徑(K由鏈路eij組成)記為K={eij|i,j∈N*}，其中N*是正整數(shù)集。

定義2 博弈G=[N,S,P]，其三要素為局中人、策略集和收益集。局中人是參與博弈并在博弈中追求自身利益最大化的決策主體。本文有兩個(gè)局中人分別為用戶U1和用戶U2，用戶U1和用戶U2都是理性的，期望在多域光網(wǎng)絡(luò)中尋找到最好的光路徑。

定義3 策略集是博弈中局中人的行動(dòng)規(guī)則，以指導(dǎo)局中人在博弈中每一個(gè)階段的行動(dòng)。設(shè)用戶U1有m個(gè)策略，其策略集為A={a1,a2,…,am}；用戶U2有n個(gè)策略，其策略集為B={b1,b2,…,bn}；用戶的策略代表用戶從源節(jié)點(diǎn)至目的節(jié)點(diǎn)之間尋找到的光路徑。對(duì)任意節(jié)點(diǎn)間的鏈路，兩個(gè)用戶都有{占用，不占用}兩種選擇，將集合A和B稱為用戶U1和用戶U2的純策略集。定義用戶U1的混合策略集為:

X=

用戶U2的混合策略集為:

Y=

定義5 定義用戶U1和用戶U2的鏈路占用度分別為S1和S2。當(dāng)同一條鏈路既被用戶U1占用又被用戶U2占用時(shí)，令S1=1，S2=1；當(dāng)同一條鏈路只被用戶U1占用時(shí)，令S1=1，S2=0；當(dāng)同一條鏈路只被用戶U2占用時(shí)，令S1=0，S2=1；當(dāng)同一條鏈路既沒(méi)有被用戶U1占用又沒(méi)有被用戶U2占用時(shí)，令S1=0，S2=0。

本文設(shè)計(jì)的多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)算法的優(yōu)化目標(biāo)是：在滿足組播用戶QoS和一定資源利用的情況下，最大化用戶U1和用戶U2混合策略效用之和，使得多域光網(wǎng)絡(luò)最小化組播樹(shù)和組播保護(hù)樹(shù)的結(jié)構(gòu)均衡。用數(shù)學(xué)模型可以表示如下：

Mij+Nij→min {Mij+Nij}

(1)

Cij+Dij→min {Cij+Dij}

(2)

s.t.costCij≥costDij

(3)

delayCij≥delayDij

(4)

berCij≤berDij

(5)

costCij+costDij<2costmax

(6)

上述約束條件表示為用戶U1選擇的組播樹(shù)成本不小于用戶U2選擇的組播樹(shù)成本，用戶U1的組播樹(shù)時(shí)延不小于用戶U2的組播樹(shù)時(shí)延，用戶U1的誤碼率不大于用戶U2的誤碼率，用戶U1和用戶U2的組播樹(shù)成本之和小于網(wǎng)絡(luò)中鏈路總成本的兩倍。

2.2 算法描述

組播樹(shù)專用保護(hù)方案可以分為三種：一是為每個(gè)目的節(jié)點(diǎn)建立通道級(jí)專用保護(hù)路徑；二是為組播樹(shù)中任意節(jié)點(diǎn)間的鏈路建立專用保護(hù)鏈路; 三是將組播樹(shù)上的路徑分為若干段，基于各分段建立專用路徑保護(hù)。針對(duì)靜態(tài)環(huán)境下多域光網(wǎng)絡(luò)組播請(qǐng)求規(guī)劃問(wèn)題，結(jié)合分層PCE架構(gòu)和雙矩陣博弈思想，采用通道級(jí)專用保護(hù)方案，本文提出一種多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)算法，稱為SMDP(Static Multicast Dedicated Protection)算法。算法旨在生成鏈路不相交的組播樹(shù)和組播保護(hù)樹(shù)，在靜態(tài)環(huán)境下預(yù)先配置組播請(qǐng)求的專用保護(hù)方案。算法主要步驟描述如下：

輸入為多域光網(wǎng)絡(luò)拓?fù)銰′(V,E,W)和一組靜態(tài)組播請(qǐng)求R={R1,R2,…,Rk}；輸出為組播工作樹(shù)T和組播保護(hù)樹(shù)P。

步驟1 對(duì)于多域光網(wǎng)絡(luò)G′(V,E,W)，設(shè)定初始值costeij=0，delayeij=0，bereij=0，i=1,j=1，Set1={}，定義Distance1(i,j)為用戶U1中節(jié)點(diǎn)Vi至Vj之間的路徑長(zhǎng)度，Distance2(i,j)為用戶U2中節(jié)點(diǎn)Vi至Vj之間的路徑長(zhǎng)度。其中1≤i≤n，1≤j≤n。定義VLmi為組播請(qǐng)求Rm的第i個(gè)葉節(jié)點(diǎn)，集合Mm={VLmi|i=1,2,…,n}為組播請(qǐng)求Rm的葉節(jié)點(diǎn)集合，1≤m≤k。給定組播請(qǐng)求集合R={R1,R2,…,Rk}，定義生成的組播樹(shù)T={T1,T2,…,Tk}，以及組播保護(hù)樹(shù)P={P1,P2,…,Pk}。

步驟2 初始化多域光網(wǎng)絡(luò)的拓?fù)湫畔⒉⑦M(jìn)行拓?fù)渚酆稀?/p>

步驟3 對(duì)于組播請(qǐng)求Rm，將Rm的源節(jié)點(diǎn)Vsm作為該請(qǐng)求的組播樹(shù)根節(jié)點(diǎn)，計(jì)入組播樹(shù)Tm和組播保護(hù)樹(shù)Pm，若某條鏈路權(quán)值W=∞，則認(rèn)定該鏈路不可用。

步驟4 對(duì)于葉節(jié)點(diǎn)VLmi，根節(jié)點(diǎn)所在域cPCE判斷該葉節(jié)點(diǎn)是否在本域內(nèi)，是，轉(zhuǎn)步驟5；不是，轉(zhuǎn)步驟6。

步驟5U1和U2分別進(jìn)行尋路，博弈開(kāi)始。

5.1) 對(duì)于U1，域內(nèi)cPCE利用Dijkstra算法計(jì)算從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的一條或多條路徑，將其距離置于集合Set1中并計(jì)算路徑成本代價(jià)選擇最優(yōu)路徑，將最優(yōu)路徑賦值于Distance1(sm,Lmi)。

5.2) 對(duì)于U2，域內(nèi)的cPCE利用Floyd算法計(jì)算從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑并賦值于Distance2(sm,Lmi)。

5.3) 根據(jù)U1和U2的路徑選擇得出路徑策略集A和B，并計(jì)算所有效用函數(shù)Cij、Dij、Mij、Nij。就路徑中每一段鏈路的使用權(quán)進(jìn)行博弈，從而得出最優(yōu)的路徑對(duì)。判斷S1·S2=0是否成立，若滿足S1·S2=0，轉(zhuǎn)步驟7；若不滿足，轉(zhuǎn)5.4)。

5.4) 當(dāng)S1·S2=1，計(jì)算并比較效用函數(shù)Cij和Dij，收益高者占用該鏈路，對(duì)于另一個(gè)用戶則令該鏈路權(quán)值W=∞并重新尋路，如果是U1重新尋路轉(zhuǎn)5.1)，如果是U2重新尋路轉(zhuǎn)5.2)。

步驟6 若不在同一個(gè)域，源節(jié)點(diǎn)所在域的cPCE向pPCE發(fā)送請(qǐng)求，pPCE廣播并找到目的節(jié)點(diǎn)所在域。

6.1) 對(duì)于U1，pPCE利用Dijkstra算法計(jì)算從源節(jié)點(diǎn)所在域到目的節(jié)點(diǎn)所在域之間的域間路徑，發(fā)送指令給各域cPCE計(jì)算域內(nèi)路徑，最終將整體路徑距離置于集合Set1中。對(duì)于集合Set1中的所有元素，各域cPCE計(jì)算域內(nèi)最優(yōu)路徑賦值于Distance1(sm,Lmi)。

6.2) 對(duì)于U2，pPCE利用Floyd算法計(jì)算從源節(jié)點(diǎn)所在域到目的節(jié)點(diǎn)所在域之間的域間路徑，發(fā)送指令給各域cPCE計(jì)算域內(nèi)路徑，將計(jì)算出的路徑賦值于Distance2(sm,Lmi)。

6.3) 根據(jù)用戶U1和用戶U2的路徑選擇得出路徑策略集A和B，并計(jì)算所有效用函數(shù)Cij、Dij、Mij、Nij。就路徑中每一段鏈路的使用權(quán)進(jìn)行博弈，從而得出最優(yōu)的路徑對(duì)。判斷S1·S2=0是否成立，若滿足S1·S2=0，轉(zhuǎn)步驟7；若不滿足，轉(zhuǎn) 6.4)。

6.4) 當(dāng)S1·S2=1，計(jì)算并比較效用函數(shù)Cij和Dij，收益高者占用該鏈路，對(duì)于另一個(gè)用戶則令該鏈路權(quán)值W=∞，如果是U1重新尋路轉(zhuǎn)6.1)，如果是U2重新尋路轉(zhuǎn)6.2)。

步驟7 判斷i

7.1)對(duì)所有葉節(jié)點(diǎn)至組播樹(shù)的聯(lián)合路徑對(duì)進(jìn)行比較，取評(píng)價(jià)最優(yōu)的葉節(jié)點(diǎn)VLmi，將其U1和U2對(duì)應(yīng)最優(yōu)策略所得路徑分別添加至組播樹(shù)Tm和組播保護(hù)樹(shù)Pm中，然后在集合Mm中刪去該葉節(jié)點(diǎn)。判斷集合Mm是否為空，如果是，轉(zhuǎn)步驟8；如果不是，令i=1，轉(zhuǎn)步驟4。

步驟8 對(duì)于組播請(qǐng)求Rm，其組播樹(shù)Tm和組播保護(hù)樹(shù)Pm構(gòu)造完畢。判斷m

步驟9 算法結(jié)束，輸出T和P。

2.3 算法分析

證明 首先介紹納什均衡存在性定理,在N個(gè)參與者的標(biāo)準(zhǔn)式博弈G=[N,S,P]，如果N是有限的，且對(duì)每個(gè)參與者的策略空間S中的純策略Si是有限的，則博弈至少存在一個(gè)純策略納什均衡(或者混合策略)。而本文中采用基于混合策略的雙矩陣博弈，且給定的多域光網(wǎng)絡(luò)包含固定節(jié)點(diǎn)數(shù)量，用戶對(duì)于每一段鏈路只有{占用，不占用}兩種選擇，所以純策略集是一定的，所以本文設(shè)計(jì)的SMDP算法一定存在納什均衡點(diǎn)。

其次，用戶U1和U2的混合策略集X和Y是A和B中的有界閉凸集，故C=X*Y是A∪B中的有界閉凸集。?(x,y)∈X×Y=C，定義映射f(x,y)=(x′,y′)如下：

i=1,2,…,m

j=1,2,…,n

定理2 SMDP算法的時(shí)間復(fù)雜度為O(mkn3)。

證明 假定多域光網(wǎng)絡(luò)中共有n個(gè)節(jié)點(diǎn)，有m個(gè)葉節(jié)點(diǎn)，有k個(gè)組播請(qǐng)求。則Dijkstra算法的時(shí)間復(fù)雜度為O(n2)，F(xiàn)loyd算法的時(shí)間復(fù)雜度為O(n3)。對(duì)于k個(gè)組播請(qǐng)求，m個(gè)葉節(jié)點(diǎn)，從步驟4～7每個(gè)葉節(jié)點(diǎn)至少重復(fù)一次，從步驟3～7每個(gè)組播請(qǐng)求至少重復(fù)一次，而用戶U1計(jì)算路徑的時(shí)間復(fù)雜度為O(mkn2)，用戶U2計(jì)算路徑的時(shí)間復(fù)雜度為O(mkn3)，所以SMDP算法的時(shí)間復(fù)雜度為O(mkn3+mkn2)，即SMDP算法時(shí)間復(fù)雜度為O(mkn3)。

定理3 SMDP算法能夠?qū)崿F(xiàn)多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)。

證明 SMDP算法能夠解決多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)機(jī)制的配置問(wèn)題。分層PCE架構(gòu)用于全局拓?fù)湫畔⒌恼{(diào)度計(jì)算，雙矩陣博弈通過(guò)競(jìng)爭(zhēng)關(guān)系生成鏈路不相交的組播樹(shù)和組播保護(hù)樹(shù)。在博弈中兩個(gè)用戶就鏈路的使用權(quán)進(jìn)行競(jìng)爭(zhēng)，尋找納什均衡點(diǎn)確保路徑分配的最優(yōu)化，促進(jìn)了網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化利用; 然后將博弈產(chǎn)生的兩條路徑分別用于生成組播樹(shù)和組播保護(hù)樹(shù)，以實(shí)現(xiàn)組播業(yè)務(wù)的通道級(jí)專用保護(hù)，預(yù)先配置能夠解決合理分配工作樹(shù)和保護(hù)樹(shù)的網(wǎng)絡(luò)資源問(wèn)題，避免工作樹(shù)與保護(hù)樹(shù)的代價(jià)相差較大, 所以SMDP算法能夠?qū)崿F(xiàn)多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)。

2.4 SMDP算法實(shí)例

給定如圖2所示的多域光網(wǎng)絡(luò)G=(19，50)，經(jīng)過(guò)拓?fù)渚酆虾蟮亩嘤蚬饩W(wǎng)絡(luò)拓?fù)淙鐖D3所示。

圖2 基于PCE架構(gòu)的多域光網(wǎng)絡(luò)

在靜態(tài)環(huán)境下對(duì)其運(yùn)用SMDP算法所得組播樹(shù)保護(hù)方案進(jìn)行實(shí)例說(shuō)明。給定組播請(qǐng)求R1={1;5,7,12}，R2={8;10,12,18}，R3={16;1,2,7,8,10,19}。首先處理組播請(qǐng)求R1，判斷目的節(jié)點(diǎn)是否在域1內(nèi)，如果是，cPCE1直接計(jì)算路徑開(kāi)始博弈；如果不是，cPCE1向pPCE發(fā)送請(qǐng)求，在虛擬拓?fù)鋱D中統(tǒng)一計(jì)算域間路徑并向各域cPCE發(fā)送指令，各域cPCE計(jì)算各自域內(nèi)路徑，而后進(jìn)行博弈，所得組播樹(shù)T1和組播保護(hù)樹(shù)P1,如圖4(a)所示，其中組播樹(shù)T1由路徑1- 5和1- 6- 7- 11- 12構(gòu)成，組播保護(hù)樹(shù)P1由路徑1- 4- 5- 9- 7和1- 4- 5- 9- 10- 12構(gòu)成。然后處理組播請(qǐng)求R2，在拓?fù)鋱D中刪去組播樹(shù)T1的路徑，所得組播樹(shù)T2和組播保護(hù)樹(shù)P2如圖4(b)所示，其中組播樹(shù)T2由路徑8- 12和8- 10- 13- 18構(gòu)成，組播保護(hù)樹(shù)P2由路徑8- 9- 10- 12和8- 9- 15- 18構(gòu)成。最后處理組播請(qǐng)求R3，在拓?fù)鋱D中刪去組播樹(shù)T2的路徑，所得組播樹(shù)T3和組播保護(hù)樹(shù)P3如圖4(c)所示，其中組播樹(shù)T3由路徑16- 19、16- 3- 2- 1、16- 3- 2- 5- 9- 8- 7和16- 3- 2- 5- 9- 8- 10構(gòu)成，組播保護(hù)樹(shù)P3由路徑16- 17- 19、16- 17- 18- 15- 5- 4- 2、16- 17- 18- 15- 5- 4- 1、16- 17- 18- 13- 10、16- 17- 18- 13- 8和16- 17- 18- 13- 7構(gòu)成。可以看出在靜態(tài)環(huán)境下組播請(qǐng)求保護(hù)樹(shù)的部分路徑可以共享，只要為鏈路預(yù)置足夠帶寬，可實(shí)現(xiàn)組播請(qǐng)求的專用保護(hù)。

圖3 虛擬拓?fù)?/p>

圖4 組播請(qǐng)求

3 實(shí)驗(yàn)與分析

本文采用光通信仿真軟件(VPI transmission Maker，VPI)設(shè)計(jì)多域光網(wǎng)絡(luò)系統(tǒng)驗(yàn)證SMDP算法的保護(hù)性能，選擇OPP算法、組播1+1算法與SMDP算法進(jìn)行比較。如圖5所示，本文搭建了雙向連接的多域光網(wǎng)絡(luò)系統(tǒng)，即如圖3所示多域光網(wǎng)絡(luò)的VPI系統(tǒng)圖，另外在圖5的基礎(chǔ)上去除一條連接方向得到單向連接的無(wú)保護(hù)機(jī)制的多域光網(wǎng)絡(luò)VPI系統(tǒng)圖。圖7中為3個(gè)域的多域光網(wǎng)絡(luò)，其中域1內(nèi)為節(jié)點(diǎn)3、5和6，域2內(nèi)為節(jié)點(diǎn)7、9和13，域3內(nèi)為節(jié)點(diǎn)15、16和18。節(jié)點(diǎn)間為雙向連接，增加了保護(hù)機(jī)制的可用路徑。

圖5 VPI系統(tǒng)

3.1 參數(shù)設(shè)置

圖5的系統(tǒng)采用了TxExtModLaser、FiberNLS、WDM_MUX_N_1_Ideal、Fork、Powermeter、AmpSysOpt、SignalAnalyzer和Const等模塊。由于本文針對(duì)靜態(tài)環(huán)境下組播業(yè)務(wù)分配進(jìn)行研究，PCE相關(guān)結(jié)構(gòu)并未在系統(tǒng)中顯示，而是由節(jié)點(diǎn)代替其一部分功能。本文設(shè)置故障模塊并設(shè)定衰減值，當(dāng)衰減值達(dá)30 dBm 以上認(rèn)為該鏈路故障。另外，系統(tǒng)中的光纖長(zhǎng)度不一隨機(jī)設(shè)置。系統(tǒng)主要參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 無(wú)保護(hù)機(jī)制系統(tǒng)實(shí)驗(yàn)結(jié)果

圖6(a)為無(wú)保護(hù)機(jī)制的多域光網(wǎng)絡(luò)系統(tǒng)正常運(yùn)行時(shí)的光譜圖，圖中4種頻率的光信號(hào)可用于至少4個(gè)組播請(qǐng)求。當(dāng)鏈路遭受故障時(shí)，所得光譜圖如圖6(b)所示，光信號(hào)整體功率值衰減30 dBm, 其中中心頻率為192.9 THz。由于實(shí)驗(yàn)中設(shè)置的故障模塊只針對(duì)功率進(jìn)行衰減，默認(rèn)衰減達(dá)30 dBm則不能滿足正常業(yè)務(wù)傳輸需求，故此時(shí)接收端不能正常接收業(yè)務(wù)。

圖6 故障前后無(wú)保護(hù)機(jī)制的多域光網(wǎng)絡(luò)系統(tǒng)光譜圖

3.2.2 基于SMDP算法的系統(tǒng)實(shí)驗(yàn)結(jié)果

圖7(a)為基于SMDP算法的多域光網(wǎng)絡(luò)系統(tǒng)的光譜圖，建立組播工作樹(shù)和組播專用保護(hù)樹(shù); 當(dāng)組播樹(shù)上的路徑發(fā)生故障所得光譜圖如圖7(b)所示。一旦檢測(cè)到發(fā)生故障，迅速切換至組播保護(hù)樹(shù)將業(yè)務(wù)流傳輸?shù)绞芄收嫌绊懙娜~節(jié)點(diǎn)。從圖7可以看出，無(wú)論是光譜形狀還是光譜的功率與故障前系統(tǒng)的相似度達(dá)99%以上，所以業(yè)務(wù)可以繼續(xù)傳輸，該系統(tǒng)也實(shí)現(xiàn)了對(duì)故障路徑的保護(hù)，保證了組播業(yè)務(wù)的正常傳輸。

圖7 故障前后基于SMDP算法的多域光網(wǎng)絡(luò)系統(tǒng)光譜圖

3.2.3 算法比較

本文對(duì)最優(yōu)路徑對(duì)(OPP)算法，SMDP算法和組播1+1算法進(jìn)行性能比較，其中OPP算法是指對(duì)組播業(yè)務(wù)的每個(gè)目的節(jié)點(diǎn)建立單播路徑對(duì)連接，而組播1+1算法旨在建立兩個(gè)鏈路不相交的組播樹(shù)，然后同時(shí)提供兩路相同的業(yè)務(wù)用于接收端的擇優(yōu)接收。

圖8為在不同數(shù)量的葉節(jié)點(diǎn)下運(yùn)行OPP算法、SMDP算法以及組播1+1算法所得的成本，以光纖長(zhǎng)度(單位m)為單位。由于OPP算法建立發(fā)送端到各接收端的路徑對(duì)所以成本相對(duì)較高；而SMDP算法作為一種專用保護(hù)算法，利用博弈論的競(jìng)爭(zhēng)關(guān)系對(duì)組播1+1算法的尋路過(guò)程進(jìn)行優(yōu)化，以最優(yōu)路徑對(duì)的形式構(gòu)造兩個(gè)組播樹(shù)代替重復(fù)尋找組播樹(shù)，從而較組播1+1算法而言提高了效率、降低了成本。

圖8 三種算法的成本對(duì)比

圖9是對(duì)于不同數(shù)目的組播請(qǐng)求，在靜態(tài)環(huán)境下進(jìn)行路徑分配所占用的鏈路資源利用率的比較。其中面對(duì)同樣組播請(qǐng)求數(shù)，SMDP算法構(gòu)造的組播保護(hù)樹(shù)之間可以共享鏈路從而資源的利用率得到提高，而其他兩個(gè)算法都旨在生成不相交的路徑對(duì)，所以SMDP算法表現(xiàn)相對(duì)最好。同時(shí)隨著組播請(qǐng)求數(shù)的增加，網(wǎng)絡(luò)資源利用率也逐漸增加。

圖9 三種算法的資源利用率

4 結(jié)語(yǔ)

隨著光網(wǎng)絡(luò)大規(guī)模發(fā)展，再加上各運(yùn)營(yíng)商隱私保護(hù)需求更加強(qiáng)烈，多域光網(wǎng)絡(luò)生存能力變得更加重要。針對(duì)靜態(tài)環(huán)境下多域光網(wǎng)絡(luò)組播請(qǐng)求配置的復(fù)雜性，對(duì)其保護(hù)方案進(jìn)行研究。本文基于分層PCE架構(gòu)和雙矩陣博弈思想，設(shè)計(jì)了一種多域光網(wǎng)絡(luò)靜態(tài)組播專用保護(hù)算法，生成鏈路不相交的組播工作樹(shù)與保護(hù)樹(shù)。實(shí)驗(yàn)結(jié)果表明，該算法提高了多域光網(wǎng)絡(luò)靜態(tài)環(huán)境下組播業(yè)務(wù)的生存能力，平衡了組播工作樹(shù)和保護(hù)樹(shù)的資源消耗，提高了資源利用率。在以后的研究中，將著重對(duì)動(dòng)態(tài)環(huán)境下組播業(yè)務(wù)的生存能力進(jìn)行研究。