基于彈性光網絡的多播業務保護算法

吳菁晶，張建芳

?

基于彈性光網絡的多播業務保護算法

吳菁晶，張建芳

（東北大學計算機科學與工程學院，遼寧 沈陽 110819）

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

彈性光網絡；網絡生存性；多播；路由

1 引言

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

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

對于彈性光網絡，人們不僅要關注有效性和可擴展性，網絡的生存性也至關重要。網絡生存性是指網絡在受到各種故障（如鏈路、節點等失效）后能夠維持可接受的連接質量的能力，因為任何鏈路的失效都會導致大量數據的丟失，當在光網絡中建立光通道時，同時也需要建立鏈路不相交或者節點不相交的保護鏈路。隨著多播技術的快速發展，光網絡的多播路由及多播生存性問題成為研究的熱點。多播業務的路由和保護算法也越來越受到業界學者的重視。

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

2 相關工作

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

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

多播是一種有效利用現有帶寬的技術，不僅可以高效率地傳輸業務，也可以節省頻譜資源。文獻[11]研究了彈性光網絡中多種動態多播業務的保護策略，還對比了不同的多播保護方案。文獻[12]研究了彈性光網絡單鏈路失效前提下的多播保護問題，提出了2種基于分段的保護算法，2種算法在阻塞率和資源利用率性能方面有很大提升。文獻[13]采用距離自適應頻譜資源分配，目標是使用最少的頻譜資源分配所有的多播請求，提出混合整數線性規劃模型，采用可擴展升級的啟發式算法改善運行時間長的缺點。文獻[14]研究了光網絡中多播保護問題，基于p-Cycle提出啟發式算法，該算法將網絡拓撲分解為一系列p-Cycle，為環上鏈路和跨接鏈路提供保護。

3 問題描述

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

3.1 整數線性規劃模型

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

：物理節點集合。

：物理光纖鏈路集合。

：多播業務請求集合。

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

對于靜態業務請求，在完成對多播業務保護的同時還要提高網絡頻譜資源利用率，因此優化目標是當為所有業務請求提供服務后，最小化所有物理鏈路上使用的最大頻譜分片數目。

目標函數定義為

約束條件為

3.2 多播子樹

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

假設彈性光網絡中每個節點都具有全光多播能力和足夠數量的光收發器。考慮4種調制格式BPSK、QPSK、8QAM、16QAM，分別對應4種不同的透明傳輸距離，對應的最大傳輸距離分別為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的容量，然后分配一個額外的頻譜分片作為保護帶寬。

圖1 源節點為光樹分裂點

圖2 中間節點為光樹分裂點

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

4 啟發式算法

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

4.1 多播樹的建立

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

為了詳盡地描述該算法，以圖3為例進行說明，在每個多播業務請求到達以前，更新每條鏈路的可用頻譜資源，計算源到目的節點的主干多播樹，建立連接。在多播樹干基礎上對剩余節點進行連接并分配資源，決定調制格式和放置光收發器，最后需要為已經建立的多播樹或多播樹分段計算保護路徑。

圖3 多播樹的建立

4.2 多播樹及多播子樹的保護機制

為了對業務連接請求提供100%的保護，需要確保保護路徑不能與其工作樹相交。對于多播請求，若頻譜資源充足，能夠為該單一多播樹成功分配頻譜資源，只需為之前創建的多播工作樹計算鏈路分離的保護路徑即可。如圖4(a)所示，為了創建鏈路分離的多播樹，將工作路徑從拓撲圖中移除。本節提出的算法在選擇保護路徑時，優先選擇共享鏈路最多的路徑作為保護路徑。從拓撲圖中可以看出，保護路徑為A—B—G—I—J。若頻譜資源短缺，為了成功為多播業務選路并為其提供保護，采用基于多播子樹的分段路由頻譜分配保護機制為多播業務提供保護。假設該多播樹分為子樹1和子樹2（如圖3(c)所示），為子樹1提供的保護路徑為A—B—G—I，為子樹2提供的保護路徑為A—C—F—J，如圖4(b)所示。此時，保護路徑的計算是獨立的，因此，從原始源節點A開始為目的節點J尋找保護路徑。

4.3 MSPA具體流程

輸出 彈性光網絡中多播業務請求的工作路徑和保護路徑以及它們的頻譜分配

步驟1 檢測并更新當前網絡頻譜資源使用狀態。

步驟2 等待網絡中業務連接請求到達。如果業務連接請求是建立一個新的連接，轉到步驟3；如果業務連接請求是釋放一個舊的連接，轉到步驟13。

步驟3 為業務連接請求計算并比較每一對源—目的節點的距離（如距離相同則隨機選擇一個），將距離最小的源—目的節點對所經過的鏈路作為多播樹主干。

步驟4 在多播樹主干基礎上對剩余目的節點進行連接，剩余目的節點需要遵循到多播樹干的距離最短。

步驟5 多播樹選取完畢后根據當前網絡頻譜資源判斷該多播請求是否成功分配，若成功分配，則根據最遠傳輸距離為多播樹決定調制格式并轉到步驟6；若失敗，轉到步驟10。

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

步驟7 將工作通路從網絡拓撲移除，為連接請求計算保護通路。

步驟8 工作通路移除后為業務連接請求的源—目的節點計算保護通路，找到一棵源節點到所有目的節點的最小生成樹為工作通路提供保護。

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

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

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

步驟12 將子樹分段通路從拓撲中移除，分別為每個子樹計算各自的保護通路，采用首次命中算法為保護路徑分配頻譜資源，轉到步驟2。

步驟13 當釋放連接請求到達時，釋放業務連接請求所占資源，釋放該請求所使用工作和保護通道的剩余頻譜資源，轉到步驟2。

5 仿真與性能評價

5.1 仿真參數

5.2 實驗結果及分析

實驗首先在14個節點21條鏈路的NSFNET網絡拓撲上測試了MSPA和MLPA在業務阻塞率指標上的性能，如圖6所示。從圖6可以看出，MSPA和MLPA的業務阻塞率都是隨著業務請求數量的增加而增加的。當網絡負載為90 Erlang（愛爾蘭）時，2種算法的業務阻塞率都較低，接近2%；當網絡負載增加到240 Erlang時，2種算法的阻塞率都隨負載的增加而提高，這是因為隨著更多多播業務請求的到達，網絡中沒有足夠的空閑頻譜資源提供給后續到達的多播業務請求。但是MLPA在負載為240 Erlang時，阻塞率接近15%，而MSPA在負載為240 Erlang時，阻塞率僅接近5%，在同等條件下可以看出，MSPA可以顯著降低業務阻塞率，這是因為MSPA可以將大型多播樹分解為若干子樹，當單一多播工作樹業務阻塞時，可以通過小型多播子樹承載業務請求，顯著降低業務阻塞率。

圖7展示了MSPA和MLPA在不同的網絡負載下頻譜利用率的比較，本節頻譜利用率定義為網絡中消耗的頻譜與總頻譜的比值。隨著網絡負載的增加，MSPA和MLPA的頻譜利用率總體都呈緩慢增加趨勢，這是因為多播請求增加意味著需要更多的頻譜資源承載多播業務，而總的頻譜資源是一定的。在同等條件下，MSPA的頻譜利用率高于MLPA，這是因為MLPA不能滿足頻譜一致性限制，所以更多的業務被阻塞，頻譜利用率低。而MSPA利用分子樹的方法打破頻譜一致性的限制，使更多的多播業務請求成功選路，提高了頻譜利用率。

圖5 仿真網絡拓撲

圖6 在不同的網絡負載下，NSFNET網絡中MSPA和MLPA平均業務阻塞率的比較

圖7 在不同的網絡負載下，NSFNET網絡中MSPA和MLPA頻譜利用率的比較

實驗對比了MSPA和MLPA需要的光收發器的數目，如圖8所示。為了確保沒有業務阻塞，實驗降低了到達業務請求的總數量，因為被阻塞的業務不消耗光收發器。隨著多播請求業務的增加，MSPA和MLPA消耗的光收發器總數也隨之增加。從圖8可以看出，在同等條件下，MSPA消耗的光收發器總數比MLPA多，這是因為MSPA將單一的多播業務分解為多個子樹，也就是說，將大型的單一業務分解為多個子業務來滿足多播請求，所以MSPA會耗費更多的光收發器。

圖8 在不同的網絡負載下，NSFNET網絡中MSPA和MLPA消耗光收發器數目的比較

考慮到預算及性價比，MSPA若應用在全部類型的網絡則會大大地增加網絡成本，所以該算法主要應用于以下2種場景以達到成本優化。

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

2) 服務質量等級（QoS）高。不同的群體，不同的用戶，對業務傳輸的順暢度、速度、受損恢復時間要求也是不同的，當用戶需要高服務質量等級時，MSPA便可以實現低阻塞、快恢復的優勢。雖然大量光收發器耗費網絡成本，但是滿足了用戶的特殊需求，實現了成本優化。

圖9~圖11是在24個節點43條鏈路的USNET網絡拓撲上的實驗結果。盡管USNET有更大的拓撲尺寸、更多的網絡節點和鏈路數目，但是仿真結果和關鍵觀測結果相似。

圖9 在不同的網絡負載下，USNET網絡中MSPA和 MLPA平均阻塞率的比較

圖10 在不同的網絡負載下，USNET網絡中MSPA和 MLPA頻譜利用率的比較

圖11 在不同的網絡負載下，USNET網絡中MSPA和 MLPA消耗光收發器數目的比較

6 結束語

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

[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

國家重點研發計劃基金資助項目（No.2017YFB0306400）；國家自然科學基金資助項目（No.61501105, No.61871107）；中央高校基本科研業務費專項資金資助項目（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-），女，遼寧沈陽人，博士，東北大學副教授，主要研究方向為光傳送網、網絡安全等。

張建芳（1992- ），女，河北宣化人，東北大學碩士生，主要研究方向為多播保護、網絡生存性。