基于彈性光網(wǎng)絡(luò)的多播業(yè)務(wù)保護(hù)算法

吳菁晶，張建芳

?

基于彈性光網(wǎng)絡(luò)的多播業(yè)務(wù)保護(hù)算法

吳菁晶，張建芳

（東北大學(xué)計算機(jī)科學(xué)與工程學(xué)院，遼寧 沈陽 110819）

隨著網(wǎng)絡(luò)中業(yè)務(wù)量的急劇增長以及寬帶業(yè)務(wù)的普及，傳統(tǒng)的波分復(fù)用光網(wǎng)絡(luò)由于靈活性差、頻譜資源浪費(fèi)嚴(yán)重而面臨嚴(yán)峻挑戰(zhàn)。彈性光網(wǎng)絡(luò)以靈活利用頻譜為特征，可以根據(jù)用戶需要和業(yè)務(wù)量大小動態(tài)分配適量的頻譜資源并配置相應(yīng)的調(diào)制格式，有效克服了波分復(fù)用光網(wǎng)絡(luò)的缺陷。同時，彈性光網(wǎng)絡(luò)中的多播路由和頻譜分配以及網(wǎng)絡(luò)的生存性問題也變得更加復(fù)雜。針對彈性光網(wǎng)絡(luò)中多播路由和保護(hù)算法進(jìn)行了研究，首先引入整數(shù)線性規(guī)劃模型（ILP, integer linear programming），最大限度地利用網(wǎng)絡(luò)中的頻譜資源。在此基礎(chǔ)上，提出了啟發(fā)式算法——基于多播子樹的分段路由頻譜分配保護(hù)算法（MSPA, multicast sub-tree protection algorithm），為多播業(yè)務(wù)請求提供保護(hù)的同時最小化頻譜資源的使用。仿真結(jié)果表明，與傳統(tǒng)的多播路由算法及多播保護(hù)算法相比，所提算法通過改變信號調(diào)制格式，靈活運(yùn)用鏈路上的頻譜碎片，可以降低網(wǎng)絡(luò)的阻塞率，提高網(wǎng)絡(luò)的頻譜利用率。

彈性光網(wǎng)絡(luò)；網(wǎng)絡(luò)生存性；多播；路由

1 引言

隨著互聯(lián)網(wǎng)的急速發(fā)展，如何提高頻譜利用率成為一個熱門的研究課題。盡管傳統(tǒng)的波分復(fù)用（WDM, wavelength division multiplexing）網(wǎng)絡(luò)在高速傳輸方面有很多優(yōu)勢，但WDM網(wǎng)絡(luò)的缺點(diǎn)也比較明顯。WDM網(wǎng)絡(luò)是固定帶寬粒度，對于各種帶寬需求的業(yè)務(wù)連接請求，WDM網(wǎng)絡(luò)需要將整個波長的帶寬都分配給該業(yè)務(wù)，即便有的業(yè)務(wù)連接請求并不需要如此大的帶寬，因此造成了在WDM網(wǎng)絡(luò)中頻譜利用率降低的缺點(diǎn)。此外，波分復(fù)用的效率較低也造成了業(yè)務(wù)連接請求的可擴(kuò)展性降低。因此，基于正交頻分復(fù)用（OFDM, orthogonal frequency division multiplexing）的彈性光網(wǎng)絡(luò)應(yīng)運(yùn)而生[1-3]。

彈性光網(wǎng)絡(luò)提供了更細(xì)的頻譜粒度和距離自適應(yīng)調(diào)制格式，可以實(shí)現(xiàn)頻譜的有效分配。隨著光網(wǎng)絡(luò)向靈活柵格方向發(fā)展，網(wǎng)絡(luò)資源的實(shí)體由波長向頻譜轉(zhuǎn)變，使資源管理與調(diào)控問題的復(fù)雜性提高，路由計算和頻譜資源的分配策略變得復(fù)雜多樣。同時，與傳統(tǒng)的點(diǎn)到點(diǎn)通信方式相比，多播傳輸不僅節(jié)省了大量的網(wǎng)絡(luò)帶寬，還提高了效率。多播傳輸是一種有效利用現(xiàn)有帶寬的技術(shù)，因此對多播技術(shù)的相關(guān)研究有非常大的意義。

對于彈性光網(wǎng)絡(luò)，人們不僅要關(guān)注有效性和可擴(kuò)展性，網(wǎng)絡(luò)的生存性也至關(guān)重要。網(wǎng)絡(luò)生存性是指網(wǎng)絡(luò)在受到各種故障（如鏈路、節(jié)點(diǎn)等失效）后能夠維持可接受的連接質(zhì)量的能力，因?yàn)槿魏捂溌返氖Ф紩?dǎo)致大量數(shù)據(jù)的丟失，當(dāng)在光網(wǎng)絡(luò)中建立光通道時，同時也需要建立鏈路不相交或者節(jié)點(diǎn)不相交的保護(hù)鏈路。隨著多播技術(shù)的快速發(fā)展，光網(wǎng)絡(luò)的多播路由及多播生存性問題成為研究的熱點(diǎn)。多播業(yè)務(wù)的路由和保護(hù)算法也越來越受到業(yè)界學(xué)者的重視。

為了更好地解決頻譜利用及網(wǎng)絡(luò)阻塞問題，本文將關(guān)注點(diǎn)放在路由及頻譜資源的分配調(diào)度上，采用多播子樹算法解決頻譜資源有限時利用足夠光收發(fā)器解決多播業(yè)務(wù)請求阻塞以及頻譜的利用率問題，采用基于分段的多播保護(hù)算法為多播業(yè)務(wù)請求提供保護(hù)，當(dāng)網(wǎng)絡(luò)發(fā)生故障時，可以快速為多播業(yè)務(wù)請求提供保護(hù)，使業(yè)務(wù)連接請求得以快速恢復(fù)。

2 相關(guān)工作

目前，已有很多文獻(xiàn)研究了光網(wǎng)絡(luò)中的保護(hù)問題。文獻(xiàn)[4]將粗細(xì)粒度路由結(jié)合，主要研究了兩方面內(nèi)容，分別是將共享保護(hù)應(yīng)用于粗、細(xì)粒度和對這2種不同共享保護(hù)方案形成靜態(tài)網(wǎng)絡(luò)設(shè)計算法。文獻(xiàn)[5]主要研究了光物理層受到侵害時光網(wǎng)絡(luò)的生存性問題，文章回顧了光網(wǎng)絡(luò)容易受到侵害的類型并討論了幾個保護(hù)算法以提高網(wǎng)絡(luò)的安全性。文獻(xiàn)[6]首先針對被單一鏈路失效影響到的鏈路分組，提出分組工作路徑保護(hù)，目標(biāo)是建立組內(nèi)鏈路不相交的工作路徑和備份路徑，首先為工作路徑和備份路徑的路由和波長分配提供兩步法整數(shù)線性規(guī)劃模型，然后提出啟發(fā)式算法應(yīng)用到大型網(wǎng)絡(luò)。

近些年，由于彈性光網(wǎng)絡(luò)可變顆粒度能提高網(wǎng)絡(luò)的靈活性，彈性光網(wǎng)絡(luò)中生存性問題得到廣泛關(guān)注和應(yīng)用。文獻(xiàn)[7]對IP-over-EON提出多層生存性問題，應(yīng)用整數(shù)線性規(guī)劃模型給出最優(yōu)解，然后提出多層概念提高網(wǎng)絡(luò)疏導(dǎo)能力，對于特定的失效狀態(tài)，不僅可以共享備份資源，還可以使工作路徑和備份路徑共享資源。文獻(xiàn)[8]為共享保護(hù)提出整數(shù)線性規(guī)劃模型，該算法能最大化網(wǎng)絡(luò)吞吐量，最小化資源的使用，此外，還研究了單播的共享保護(hù)算法。文獻(xiàn)[9]提出了基于頻譜窗平面的有效啟發(fā)式算法并且應(yīng)用距離和調(diào)制格式自適應(yīng)的路由和頻譜分配來最大化共享保護(hù)路徑的空閑容量。文獻(xiàn)[10]提出自適應(yīng)生存性方法實(shí)現(xiàn)保護(hù)路徑有效性和路由花費(fèi)的最佳權(quán)衡，此外，還提出新穎的路由、頻譜和調(diào)制格式的分配算法最優(yōu)化業(yè)務(wù)。

多播是一種有效利用現(xiàn)有帶寬的技術(shù)，不僅可以高效率地傳輸業(yè)務(wù)，也可以節(jié)省頻譜資源。文獻(xiàn)[11]研究了彈性光網(wǎng)絡(luò)中多種動態(tài)多播業(yè)務(wù)的保護(hù)策略，還對比了不同的多播保護(hù)方案。文獻(xiàn)[12]研究了彈性光網(wǎng)絡(luò)單鏈路失效前提下的多播保護(hù)問題，提出了2種基于分段的保護(hù)算法，2種算法在阻塞率和資源利用率性能方面有很大提升。文獻(xiàn)[13]采用距離自適應(yīng)頻譜資源分配，目標(biāo)是使用最少的頻譜資源分配所有的多播請求，提出混合整數(shù)線性規(guī)劃模型，采用可擴(kuò)展升級的啟發(fā)式算法改善運(yùn)行時間長的缺點(diǎn)。文獻(xiàn)[14]研究了光網(wǎng)絡(luò)中多播保護(hù)問題，基于p-Cycle提出啟發(fā)式算法，該算法將網(wǎng)絡(luò)拓?fù)浞纸鉃橐幌盗衟-Cycle，為環(huán)上鏈路和跨接鏈路提供保護(hù)。

3 問題描述

目前，已有研究人員開始了對彈性光網(wǎng)絡(luò)中多播業(yè)務(wù)保護(hù)問題的研究與探討，但彈性光網(wǎng)絡(luò)中的生存性研究仍存在著很多問題。首先，全光多播通常采用單一光樹來服務(wù)多播業(yè)務(wù)請求；其次，多播業(yè)務(wù)請求不僅有工作頻譜資源請求，還有保護(hù)頻譜資源請求，而在資源分配過程中可能造成資源使用不平衡。因此，本文首先描述了彈性光網(wǎng)絡(luò)中多播保護(hù)問題的數(shù)學(xué)模型，在此基礎(chǔ)上，設(shè)計了針對動態(tài)業(yè)務(wù)請求的啟發(fā)式算法。

3.1 整數(shù)線性規(guī)劃模型

算法中用到的參數(shù)和變量定義如下。

：物理節(jié)點(diǎn)集合。

：物理光纖鏈路集合。

：多播業(yè)務(wù)請求集合。

：每條物理鏈路上連續(xù)子載波的集合。

對于靜態(tài)業(yè)務(wù)請求，在完成對多播業(yè)務(wù)保護(hù)的同時還要提高網(wǎng)絡(luò)頻譜資源利用率，因此優(yōu)化目標(biāo)是當(dāng)為所有業(yè)務(wù)請求提供服務(wù)后，最小化所有物理鏈路上使用的最大頻譜分片數(shù)目。

目標(biāo)函數(shù)定義為

約束條件為

3.2 多播子樹

傳統(tǒng)的多播路由和頻譜分配問題通常采用全光多播距離自適應(yīng)頻譜分配應(yīng)對大帶寬業(yè)務(wù)，通常為多播業(yè)務(wù)請求建立單一光樹，在這種方案中，調(diào)制格式的選擇至關(guān)重要，源節(jié)點(diǎn)到每一個相關(guān)聯(lián)的目的節(jié)點(diǎn)的距離是不同的，單一光樹的調(diào)制格式是由距離最遠(yuǎn)的源—目的節(jié)點(diǎn)距離決定的。正是由于單一大型光樹的限制，調(diào)制格式等級降低，需求的頻譜容量增加，造成了頻譜資源浪費(fèi)及業(yè)務(wù)請求阻塞。頻譜碎片的問題更是給這種方案造成了很大的困難。由此，本節(jié)提出多播子樹路由算法，該算法的核心思想是將多播的目的節(jié)點(diǎn)分組，將大型單一光樹分成若干個子樹，每個子樹可以根據(jù)子樹當(dāng)前頻譜狀態(tài)選擇合適的調(diào)制格式。子樹的形成方式可以分為以下2類：1) 源節(jié)點(diǎn)為光樹分裂點(diǎn)，如圖1所示；2) 中間節(jié)點(diǎn)為光樹分裂點(diǎn)，如圖2所示。

假設(shè)彈性光網(wǎng)絡(luò)中每個節(jié)點(diǎn)都具有全光多播能力和足夠數(shù)量的光收發(fā)器?？紤]4種調(diào)制格式BPSK、QPSK、8QAM、16QAM，分別對應(yīng)4種不同的透明傳輸距離，對應(yīng)的最大傳輸距離分別為8 000 km、4 000 km、2 000 km、1 000 km，每個頻譜分片的帶寬為12.5 GHz，分別攜帶25 Gbit/s、50 Gbit/s、75 Gbit/s、100 Gbit/s的容量，然后分配一個額外的頻譜分片作為保護(hù)帶寬。

圖1 源節(jié)點(diǎn)為光樹分裂點(diǎn)

圖2 中間節(jié)點(diǎn)為光樹分裂點(diǎn)

圖2展示了一個多播子樹路由算法采取方式2)，即以中間節(jié)點(diǎn)為光樹分裂點(diǎn)的子樹形成方式。圖2(a)展示了頻譜使用現(xiàn)狀（假設(shè)每條鏈路上有7個頻譜分片）。一個同樣的多播業(yè)務(wù)請求到達(dá)，源節(jié)點(diǎn)為A，目的節(jié)點(diǎn)分別為B、F、G，對于單一光樹方案，由于合適的調(diào)制格式是由最遠(yuǎn)距離決定的，最遠(yuǎn)的距離是A—C—E—G，總距離為2 100 km，可用的最高調(diào)制格式為QPSK，需要5個頻譜分片來滿足該多播業(yè)務(wù)請求。但是鏈路A—B的頻譜分片6、7已經(jīng)被占用，所以沒有足夠的頻譜分片來滿足該多播業(yè)務(wù)請求需要的頻譜分片（頻譜一致性限制），所以該多播業(yè)務(wù)請求被阻塞。如圖2(b)所示，對比于單一光樹方案，多播子樹路由算法采取方式1)以源節(jié)點(diǎn)為光樹分裂點(diǎn)將多播業(yè)務(wù)請求分解為2個子樹，子樹1包含目的節(jié)點(diǎn)B，子樹2包含目的節(jié)點(diǎn)F、G。根據(jù)每個子樹的傳播距離，子樹1的最遠(yuǎn)距離為900 km，合適的調(diào)制格式為16QAM，需要3個頻譜分片（1~3），子樹2的最遠(yuǎn)距離為2 100 km，合適的調(diào)制格式為QPSK，需要5個頻譜分片（3~7），但是，此時只有A—C的空閑頻譜滿足，C—G和C—F的頻譜被占用，所以只采用方式1)，也無法滿足多播業(yè)務(wù)請求，此時采取方式2)，以中間節(jié)點(diǎn)為光樹分裂點(diǎn)的分子樹形成方式來完成多播業(yè)務(wù)請求。如圖2(c)將節(jié)點(diǎn)C作為新的源節(jié)點(diǎn)，在中間節(jié)點(diǎn)C處再形成子樹，該子樹最遠(yuǎn)的路徑C—E—G，距離為1 200 km，合適的調(diào)制格式為8QAM，需要4個頻譜分片（4~7）。由此，在中間節(jié)點(diǎn)C處形成子樹使該多播業(yè)務(wù)請求得以實(shí)現(xiàn)。該方案不僅成功分配了多播業(yè)務(wù)請求，還節(jié)省了頻譜資源，但是，該方案需要更多的光收發(fā)器。

4 啟發(fā)式算法

彈性光網(wǎng)絡(luò)中多播業(yè)務(wù)保護(hù)的路由和頻譜分配問題是一個NP-hard問題[15]。為解決此問題，本節(jié)提出了基于多播子樹的分段路由頻譜分配保護(hù)機(jī)制（MSPA, multicast sub-tree protection algorithm）以改善頻譜利用。該算法的核心思想是：首先，在多播業(yè)務(wù)請求到達(dá)以前，更新每條鏈路的可用頻譜資源；然后，找到最佳路徑建立工作路徑，當(dāng)多播業(yè)務(wù)請求到達(dá)彈性光網(wǎng)絡(luò)時，網(wǎng)絡(luò)的控制平面找到可用路徑并且分配足夠的頻譜資源，計算源到目的節(jié)點(diǎn)的最短路徑作為多播樹干，接著在多播樹干基礎(chǔ)上對剩余節(jié)點(diǎn)進(jìn)行連接并分配資源；最后，決定調(diào)制格式和保護(hù)方案，當(dāng)多播樹能夠成功分配頻譜資源，則直接為多播樹提供保護(hù)；當(dāng)頻譜資源短缺，則先將多播樹分成多播子樹，再為每個子樹分段提供保護(hù)，從而得到彈性光網(wǎng)絡(luò)多播樹保護(hù)的路由和頻譜分配的解決方案。

4.1 多播樹的建立

在彈性光網(wǎng)絡(luò)中需要滿足以下3個限制：頻譜一致性、頻譜連續(xù)性和頻譜非重疊。換句話說，選定的頻譜分片需要在端到端的光路上傳輸。如果頻譜分片已經(jīng)分配給現(xiàn)存的多播業(yè)務(wù)請求，則該分片不能再分配給其他多播業(yè)務(wù)請求。需要注意的是，不同的調(diào)制格式有不同的傳輸距離和頻譜效率，因此，所需要設(shè)計的路由和頻譜分配算法必須同時選擇路徑和調(diào)制格式。

為了詳盡地描述該算法，以圖3為例進(jìn)行說明，在每個多播業(yè)務(wù)請求到達(dá)以前，更新每條鏈路的可用頻譜資源，計算源到目的節(jié)點(diǎn)的主干多播樹，建立連接。在多播樹干基礎(chǔ)上對剩余節(jié)點(diǎn)進(jìn)行連接并分配資源，決定調(diào)制格式和放置光收發(fā)器，最后需要為已經(jīng)建立的多播樹或多播樹分段計算保護(hù)路徑。

圖3 多播樹的建立

4.2 多播樹及多播子樹的保護(hù)機(jī)制

為了對業(yè)務(wù)連接請求提供100%的保護(hù)，需要確保保護(hù)路徑不能與其工作樹相交。對于多播請求，若頻譜資源充足，能夠?yàn)樵搯我欢嗖涑晒Ψ峙漕l譜資源，只需為之前創(chuàng)建的多播工作樹計算鏈路分離的保護(hù)路徑即可。如圖4(a)所示，為了創(chuàng)建鏈路分離的多播樹，將工作路徑從拓?fù)鋱D中移除。本節(jié)提出的算法在選擇保護(hù)路徑時，優(yōu)先選擇共享鏈路最多的路徑作為保護(hù)路徑。從拓?fù)鋱D中可以看出，保護(hù)路徑為A—B—G—I—J。若頻譜資源短缺，為了成功為多播業(yè)務(wù)選路并為其提供保護(hù)，采用基于多播子樹的分段路由頻譜分配保護(hù)機(jī)制為多播業(yè)務(wù)提供保護(hù)。假設(shè)該多播樹分為子樹1和子樹2（如圖3(c)所示），為子樹1提供的保護(hù)路徑為A—B—G—I，為子樹2提供的保護(hù)路徑為A—C—F—J，如圖4(b)所示。此時，保護(hù)路徑的計算是獨(dú)立的，因此，從原始源節(jié)點(diǎn)A開始為目的節(jié)點(diǎn)J尋找保護(hù)路徑。

4.3 MSPA具體流程

輸出 彈性光網(wǎng)絡(luò)中多播業(yè)務(wù)請求的工作路徑和保護(hù)路徑以及它們的頻譜分配

步驟1 檢測并更新當(dāng)前網(wǎng)絡(luò)頻譜資源使用狀態(tài)。

步驟2 等待網(wǎng)絡(luò)中業(yè)務(wù)連接請求到達(dá)。如果業(yè)務(wù)連接請求是建立一個新的連接，轉(zhuǎn)到步驟3；如果業(yè)務(wù)連接請求是釋放一個舊的連接，轉(zhuǎn)到步驟13。

步驟3 為業(yè)務(wù)連接請求計算并比較每一對源—目的節(jié)點(diǎn)的距離（如距離相同則隨機(jī)選擇一個），將距離最小的源—目的節(jié)點(diǎn)對所經(jīng)過的鏈路作為多播樹主干。

步驟4 在多播樹主干基礎(chǔ)上對剩余目的節(jié)點(diǎn)進(jìn)行連接，剩余目的節(jié)點(diǎn)需要遵循到多播樹干的距離最短。

步驟5 多播樹選取完畢后根據(jù)當(dāng)前網(wǎng)絡(luò)頻譜資源判斷該多播請求是否成功分配，若成功分配，則根據(jù)最遠(yuǎn)傳輸距離為多播樹決定調(diào)制格式并轉(zhuǎn)到步驟6；若失敗，轉(zhuǎn)到步驟10。

步驟6 為工作通路分配資源，采用首次命中算法為工作路徑分配頻譜資源。

步驟7 將工作通路從網(wǎng)絡(luò)拓?fù)湟瞥?，為連接請求計算保護(hù)通路。

步驟8 工作通路移除后為業(yè)務(wù)連接請求的源—目的節(jié)點(diǎn)計算保護(hù)通路，找到一棵源節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的最小生成樹為工作通路提供保護(hù)。

步驟9 為保護(hù)通路分配資源，采用首次命中算法為保護(hù)路徑分配頻譜資源，并輸出工作路徑和保護(hù)路徑以及各自的頻譜資源分配，轉(zhuǎn)到步驟2。

步驟10 若多播樹計算失敗，根據(jù)多播子樹路由算法將多播樹分解為若干子樹。

步驟11 為每個子樹分段分配資源。

步驟12 將子樹分段通路從拓?fù)渲幸瞥?，分別為每個子樹計算各自的保護(hù)通路，采用首次命中算法為保護(hù)路徑分配頻譜資源，轉(zhuǎn)到步驟2。

步驟13 當(dāng)釋放連接請求到達(dá)時，釋放業(yè)務(wù)連接請求所占資源，釋放該請求所使用工作和保護(hù)通道的剩余頻譜資源，轉(zhuǎn)到步驟2。

5 仿真與性能評價

5.1 仿真參數(shù)

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

實(shí)驗(yàn)首先在14個節(jié)點(diǎn)21條鏈路的NSFNET網(wǎng)絡(luò)拓?fù)渖蠝y試了MSPA和MLPA在業(yè)務(wù)阻塞率指標(biāo)上的性能，如圖6所示。從圖6可以看出，MSPA和MLPA的業(yè)務(wù)阻塞率都是隨著業(yè)務(wù)請求數(shù)量的增加而增加的。當(dāng)網(wǎng)絡(luò)負(fù)載為90 Erlang（愛爾蘭）時，2種算法的業(yè)務(wù)阻塞率都較低，接近2%；當(dāng)網(wǎng)絡(luò)負(fù)載增加到240 Erlang時，2種算法的阻塞率都隨負(fù)載的增加而提高，這是因?yàn)殡S著更多多播業(yè)務(wù)請求的到達(dá)，網(wǎng)絡(luò)中沒有足夠的空閑頻譜資源提供給后續(xù)到達(dá)的多播業(yè)務(wù)請求。但是MLPA在負(fù)載為240 Erlang時，阻塞率接近15%，而MSPA在負(fù)載為240 Erlang時，阻塞率僅接近5%，在同等條件下可以看出，MSPA可以顯著降低業(yè)務(wù)阻塞率，這是因?yàn)镸SPA可以將大型多播樹分解為若干子樹，當(dāng)單一多播工作樹業(yè)務(wù)阻塞時，可以通過小型多播子樹承載業(yè)務(wù)請求，顯著降低業(yè)務(wù)阻塞率。

圖7展示了MSPA和MLPA在不同的網(wǎng)絡(luò)負(fù)載下頻譜利用率的比較，本節(jié)頻譜利用率定義為網(wǎng)絡(luò)中消耗的頻譜與總頻譜的比值。隨著網(wǎng)絡(luò)負(fù)載的增加，MSPA和MLPA的頻譜利用率總體都呈緩慢增加趨勢，這是因?yàn)槎嗖フ埱笤黾右馕吨枰嗟念l譜資源承載多播業(yè)務(wù)，而總的頻譜資源是一定的。在同等條件下，MSPA的頻譜利用率高于MLPA，這是因?yàn)镸LPA不能滿足頻譜一致性限制，所以更多的業(yè)務(wù)被阻塞，頻譜利用率低。而MSPA利用分子樹的方法打破頻譜一致性的限制，使更多的多播業(yè)務(wù)請求成功選路，提高了頻譜利用率。

圖5 仿真網(wǎng)絡(luò)拓?fù)?/p>

圖6 在不同的網(wǎng)絡(luò)負(fù)載下，NSFNET網(wǎng)絡(luò)中MSPA和MLPA平均業(yè)務(wù)阻塞率的比較

圖7 在不同的網(wǎng)絡(luò)負(fù)載下，NSFNET網(wǎng)絡(luò)中MSPA和MLPA頻譜利用率的比較

實(shí)驗(yàn)對比了MSPA和MLPA需要的光收發(fā)器的數(shù)目，如圖8所示。為了確保沒有業(yè)務(wù)阻塞，實(shí)驗(yàn)降低了到達(dá)業(yè)務(wù)請求的總數(shù)量，因?yàn)楸蛔枞臉I(yè)務(wù)不消耗光收發(fā)器。隨著多播請求業(yè)務(wù)的增加，MSPA和MLPA消耗的光收發(fā)器總數(shù)也隨之增加。從圖8可以看出，在同等條件下，MSPA消耗的光收發(fā)器總數(shù)比MLPA多，這是因?yàn)镸SPA將單一的多播業(yè)務(wù)分解為多個子樹，也就是說，將大型的單一業(yè)務(wù)分解為多個子業(yè)務(wù)來滿足多播請求，所以MSPA會耗費(fèi)更多的光收發(fā)器。

圖8 在不同的網(wǎng)絡(luò)負(fù)載下，NSFNET網(wǎng)絡(luò)中MSPA和MLPA消耗光收發(fā)器數(shù)目的比較

考慮到預(yù)算及性價比，MSPA若應(yīng)用在全部類型的網(wǎng)絡(luò)則會大大地增加網(wǎng)絡(luò)成本，所以該算法主要應(yīng)用于以下2種場景以達(dá)到成本優(yōu)化。

1) 網(wǎng)狀型網(wǎng)絡(luò)，且網(wǎng)絡(luò)復(fù)雜，網(wǎng)絡(luò)中每個節(jié)點(diǎn)的度（連接密集處）較大。雖然增加了成本，但是可以有效降低網(wǎng)絡(luò)阻塞率，同時提高頻譜利用率。

2) 服務(wù)質(zhì)量等級（QoS）高。不同的群體，不同的用戶，對業(yè)務(wù)傳輸?shù)捻槙扯?、速度、受損恢復(fù)時間要求也是不同的，當(dāng)用戶需要高服務(wù)質(zhì)量等級時，MSPA便可以實(shí)現(xiàn)低阻塞、快恢復(fù)的優(yōu)勢。雖然大量光收發(fā)器耗費(fèi)網(wǎng)絡(luò)成本，但是滿足了用戶的特殊需求，實(shí)現(xiàn)了成本優(yōu)化。

圖9~圖11是在24個節(jié)點(diǎn)43條鏈路的USNET網(wǎng)絡(luò)拓?fù)渖系膶?shí)驗(yàn)結(jié)果。盡管USNET有更大的拓?fù)涑叽?、更多的網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路數(shù)目，但是仿真結(jié)果和關(guān)鍵觀測結(jié)果相似。

圖9 在不同的網(wǎng)絡(luò)負(fù)載下，USNET網(wǎng)絡(luò)中MSPA和 MLPA平均阻塞率的比較

圖10 在不同的網(wǎng)絡(luò)負(fù)載下，USNET網(wǎng)絡(luò)中MSPA和 MLPA頻譜利用率的比較

圖11 在不同的網(wǎng)絡(luò)負(fù)載下，USNET網(wǎng)絡(luò)中MSPA和 MLPA消耗光收發(fā)器數(shù)目的比較

6 結(jié)束語

本文針對彈性光網(wǎng)絡(luò)中的多播路由保護(hù)算法進(jìn)行了研究。為了更好地解決頻譜利用及網(wǎng)絡(luò)阻塞問題，本文將關(guān)注點(diǎn)放在路由及頻譜資源的分配調(diào)度上，采用多播子樹算法解決頻譜資源有限時利用足夠光收發(fā)器解決多播業(yè)務(wù)請求阻塞率以及頻譜利用率問題，采用基于分段的多播保護(hù)算法為多播業(yè)務(wù)請求提供保護(hù)，當(dāng)網(wǎng)絡(luò)發(fā)生故障時，可以快速為多播業(yè)務(wù)請求提供保護(hù)。仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的多播路由算法及多播保護(hù)算法相比，所提算法通過改變信號調(diào)制格式、靈活運(yùn)用鏈路上的頻譜碎片，可以降低網(wǎng)絡(luò)的阻塞率，提高網(wǎng)絡(luò)的頻譜利用率。

[1] SHIEH W. OFDM for adaptive ultra high-speed optical networks[C]// 2010 Conference on Optical Fiber Communication (OFC). 2010: 1-51.

[2] SZCZESNIAK I, GOLA A, JAJSZCZYK A, et al. Itinerant routing in elastic optical networks[J]. Journal of Lightwave Technology, 2017, 35(10): 1868-1857.

[3] HADI M, PAKRAVAN M R. Spectrum-convertible BVWXC placement in OFDM-based elastic optical networks[J]. IEEE Photonics Journal, 2017, 9(1): 1-12.

[4] ISHIKAWA T, MORI Y, HASEGAWA H, et al. Spectral efficiency maximization of grouped routing optical networks with shared protection[J]. IEEE/OSA Journal of Optical Communications and Networking, 2017, 9(10): 864-875.

[5] DAHAN D, MAHLAB U. Security threats and protection procedures for optical networks[J]. IET Optoelectronics, 2017, 11(5): 186-200.

[6] FURDEK M, SKORIN-KAPOV N, WOSINSKA L. Attack-aware dedicated path protection in optical networks[J]. Journal of Lightwave Technology, 2016, 34(4): 1050-1061.

[7] PAPANIKOLAOU P, CHRISTODOULOPOULOS K, VARVARIGOS E. Joint multi-layer survivability techniques for IP-over-elastic- optical-networks[J]. IEEE/OSA Journal of Optical Communications and Networking, 2017, 9(1): 85-98.

[8] XU R, CHEN B, DAI M, et al. Disaster survivability in elastic optical datacenter networks[C]// 2016 IEEE Optoelectronics Global Conference (OGC). 2016: 1-3.

[9] WANG C, SHEN G, BOSE S K. Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection[J]. Journal of Lightwave Technology, 2015, 33(14): 2955-2964.

[10] AIBIN M, WALKOWIAK K, SEN A. Software-defined adaptive survivability for elastic optical networks[J]. Optical Switching and Networking, 2016, 23(2): 85-96.

[11] AIBIN M, WALKOWIAK K. Different strategies for dynamic multicast traffic protection in elastic optical networks[C]// International Workshop on Resilient Networks Design and Modeling(RNDM). 2016: 174-180.

[12] DIN D, LAI I. Multicast protection problem on elastic optical networks using segment-base protection[C]// International Conference on Informatics, Electronics & Vision(ICIEV). 2015: 1-6.

[13] CAI A, GUO J, LIN R, et al. Multicast routing and distance-adaptive spectrum allocation in elastic optical networks with shared protection[J]. Journal of Lightwave Technology, 2016, 34(17): 4076-4088.

[14] PANAYIOTOU T, ELLINAS G, ANTONIADES N. P-cycle-based protection of multicast connections in metropolitan area optical networks with physical layer impairments constraints[J]. Optical Switching and Networking, 2016, 19(2): 66-77.

[15] FAN Z, LI Y, SHEN G, et al. Distance-adaptive spectrum resource allocation using subtree scheme for all-optical multicasting in elastic optical networks[J]. Journal of Lightwave Technology, 2017, 35(9): 1460-1468.

[16] AHUJA S S, RAMASUBRAMANIAN S, KRUNZ M. Single-link failure detection in all-optical networks using monitoring cycles and paths[J]. IEEE/ACM Transactions on Networking, 2009, 17(4): 1080-1093.

Multicast service protection algorithm based on elastic optical network

WU Jingjing, ZHANG Jianfang

School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China

With the rapid growth of the network traffic, the elastic optical network (EON) has been proposed as a promising solution due to its high spectrum efficiency and flexible bandwidth provision. Meanwhile, multicast routing and spectrum allocation, and the survivability of the network become more challenging than that in the conventional optical network. The routing for multicast traffic and its protection algorithm in EON was investigated. An integer linear programming (ILP) formulation with the objective to minimize total spectrum consumption was presented. In addition, a heuristic algorithm called multicast sub-tree protection algorithm (MSPA) to achieve sufficient protection and satisfy resources savings was designed. The simulation results demonstrate that comparing with the traditional multicast routing and protection algorithm, MSPA performs well in improving the blocking probability and the spectrum utilization of the network.

elastic optical network, network survivability, multicast, routing

TN915

A

10.11959/j.issn.1000?436x.2019061

2018?04?03；

2018?08?20

國家重點(diǎn)研發(fā)計劃基金資助項(xiàng)目（No.2017YFB0306400）；國家自然科學(xué)基金資助項(xiàng)目（No.61501105, No.61871107）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（No.N171612014）

The National Key R&D Program of China (No.2017YFB0306400), The National Natural Science Foundation of China (No.61501105, No.61871107), The Central University Basic Business Expenses Special Funding for Scientific Research Project (No.N171612014)

吳菁晶（1981-），女，遼寧沈陽人，博士，東北大學(xué)副教授，主要研究方向?yàn)楣鈧魉途W(wǎng)、網(wǎng)絡(luò)安全等。

張建芳（1992- ），女，河北宣化人，東北大學(xué)碩士生，主要研究方向?yàn)槎嗖ケＷo(hù)、網(wǎng)絡(luò)生存性。