【摘 要】隨著多媒體業(yè)務(wù)的迅速發(fā)展，網(wǎng)絡(luò)中多播業(yè)務(wù)變得越來越普及，并且光傳輸網(wǎng)故障導(dǎo)致的業(yè)務(wù)中斷將造成巨大經(jīng)濟損失，因此有必要研究光網(wǎng)絡(luò)中多播生存性技術(shù)。本文研究了基于自動交換光網(wǎng)絡(luò)（ASON）的多播專用保護算法。仿真結(jié)果表明，本文所設(shè)計的基于ASON的綠色多播專用疏導(dǎo)保護算法具有更低的業(yè)務(wù)阻塞率，而且可以節(jié)省較多的能耗。

【關(guān)鍵詞】ASON 綠色光網(wǎng)絡(luò) 動態(tài)多播 疏導(dǎo)保護

一、引言

光核心網(wǎng)技術(shù)的發(fā)展迅猛，一旦某條光纖斷裂將造成嚴重后果，如何實現(xiàn)高效的網(wǎng)絡(luò)保護和恢復(fù)，如何實現(xiàn)保護帶寬的智能動態(tài)分配，都是自動交換光網(wǎng)絡(luò)（ASON）需要解決的問題。ASON作為具有分布式智能的光傳送網(wǎng)，它的最大特點就是在傳送平面（TP）和管理平面（MP）的基礎(chǔ)上引入了具有智能的控制平面（CP），并使用了信令、路由和自動發(fā)現(xiàn)等技術(shù)，因此ASON能夠?qū)崿F(xiàn)實時的光通道指配及靈活的帶寬管理。

本文針對可能發(fā)生的光網(wǎng)絡(luò)多播單鏈路失效情況提出了新的保護算法，即基于ASON的綠色多播專用疏導(dǎo)保護算法（Dedicated Multicast Green-grooming Algorithm based on Spanning-path）簡稱DMGAS，該算法基于遍歷路徑保護，結(jié)合ASON智能控制和動態(tài)自動調(diào)節(jié)的優(yōu)勢，大大提高了多播傳輸?shù)姆?wù)質(zhì)量，同時針對綠色節(jié)能方面我們提出的算法可以最小化由鏈路保護所帶來的電能消耗。

二、數(shù)學(xué)模型

（一）輔助圖模型Auxiliary Graph Model

為了進行動態(tài)的業(yè)務(wù)量疏導(dǎo)，本文在文獻[1]所提出的疏導(dǎo)圖的基礎(chǔ)上定義兩種輔助圖：虛拓撲圖（Virtual topology Graph，VG）和聯(lián)合疏導(dǎo)圖（Integrated Graph，IG），如圖2.1所示。

數(shù)學(xué)符號說明如下：

：網(wǎng)絡(luò)物理拓撲上的節(jié)點標(biāo)號；

：IG中波長平面中的對應(yīng)于物理拓撲節(jié)點的節(jié)點；

：VG和IG中的虛拓撲平面中，利用波長所建立的光路的端節(jié)點；

：IG中的節(jié)點對之間的物理鏈路；

：IG中波長平面中節(jié)點對之間的波長鏈路；

：IG中的虛拓撲平面，利用波長在節(jié)點對之間所建立的光路鏈路

：物理鏈路的代價

：波長鏈路的代價，與對應(yīng)的物理鏈路代價相等；

：光路的代價，光路代價為組成條光路的所有波長鏈路代價之和；

：三種符號分別表示物理鏈路，波長鏈路，光路鏈路的狀態(tài)，有四種狀態(tài)，分別用u、w、p和mix來表示，分別為空閑、工作、保護和混合。

虛拓撲圖VG是一個單層圖，如圖2.1（b），圖中每條鏈路都是光路鏈路（Partially Available Lightpath， PAL）。虛拓撲中節(jié)點具有波長變換能力，這種波長變換的能力實現(xiàn)的前提是在該點處分配光收發(fā)器，通過光收發(fā)器將光信號轉(zhuǎn)換成電信號，在電交換矩陣中實現(xiàn)業(yè)務(wù)融合以及波長變換。新到達的低速業(yè)務(wù)可以利用所有PAL鏈路上的剩余帶寬來建立連接。

聯(lián)合疏導(dǎo)圖IG是將分層圖和虛拓撲圖聯(lián)合在一起，如圖2.1（c），即將物理拓撲轉(zhuǎn)化為個互不相鄰的波長平面，每個平面都對應(yīng)一個特定的波長，另外又增加了虛拓撲圖作為平面，將個平面聯(lián)系起來的是虛鏈路（如圖2.1（c）中的虛線所示），如果在節(jié)點中存在空閑的光收發(fā)器，那么就可以將在每個層中對應(yīng)的這個點用虛鏈路連接起來。

圖2.1輔助圖

（二）問題描述

物理拓撲，其中是網(wǎng)絡(luò)節(jié)點集；是鏈路集；為每根光纖支持的可用波長集，并且。每條鏈路賦予一正權(quán)值，表示使用該條鏈路疏導(dǎo)業(yè)務(wù)所需的代價。多播業(yè)務(wù)請求隨機動態(tài)地到達和離開，其中是源節(jié)點；是目的節(jié)點集合；是業(yè)務(wù)請求帶寬；是業(yè)務(wù)服務(wù)持續(xù)時間。

如果多播業(yè)務(wù)請求成功建立一棵工作樹，工作樹中的節(jié)點度為1的節(jié)點數(shù)目為，那么可以將這棵劃分為條遍歷路徑，每條遍歷路徑可以看作一個單播請求，其中分別是源節(jié)點和目的節(jié)點。為這些單播請求計算保護路徑，最后計算出最小代價樹，使得工作樹上任意一條鏈路失效后都能利用保護路徑實現(xiàn)業(yè)務(wù)恢復(fù)。

優(yōu)化目標(biāo)：最小化

（2.1）

模型的優(yōu)化目標(biāo)（公式（2.1））最小化網(wǎng)絡(luò)的能耗。公式前半部分計算光收發(fā)器和路由器端口的能耗，公式的后半部分統(tǒng)計光放大器的能耗。因為多播樹的計算是一個NP-hard問題，所以針對如上問題我們在第三章中提出了啟發(fā)式算法。

三、DMGAS算法描述

（一）選路圖構(gòu)建

在計算工作樹和保護路徑時需要根據(jù)疏導(dǎo)輔助圖來構(gòu)建有效的選路圖。在構(gòu)建計算工作樹的選路圖時只要輔助圖的鏈路的帶寬大于或是等于業(yè)務(wù)請求的帶寬就可以加入到選路圖中，但是在構(gòu)建計算保護路徑的選路圖時不僅帶寬要滿足要求，并且要與被保護的工作路徑鏈路分離。計算工作樹和保護路徑時，按照相關(guān)公式在選路圖上設(shè)置各鏈路的代價。目的是使保護路徑能夠相對集中在同一條鏈路上，那么就可以有更多的設(shè)備可以進入睡眠狀態(tài)，促進節(jié)能的實現(xiàn)。

（二）算法步驟

步驟1：根據(jù)物理拓撲和當(dāng)前的網(wǎng)絡(luò)狀態(tài)初始化虛拓撲圖或聯(lián)合疏導(dǎo)圖。

步驟2：等待多播業(yè)務(wù)請求，如果是建立連接請求，轉(zhuǎn)至步驟3；如果是釋放連接請求，轉(zhuǎn)至步驟5；

步驟3：用下面的步驟為連接請求計算多播樹和保護路徑：如果成功，記錄工作樹和保護路徑集信息，轉(zhuǎn)至步驟4；如果失敗，該業(yè)務(wù)請求被阻塞，返回步驟2。

（a）根據(jù)網(wǎng)絡(luò)資源使用狀況和多播業(yè)務(wù)請求帶寬在虛拓撲圖中裁減帶寬值小于的光路鏈路PAL，并根據(jù)公式3.2和重新設(shè)置光路代價，得到有效虛拓撲圖。用最小代價樹MPH算法尋找連接源節(jié)點s并包含目的節(jié)點集D中所有節(jié)點的工作樹，如果成功，則記錄多播樹信息，并找出節(jié)點度為1的節(jié)點，將工作樹劃分成條遍歷路徑，并根據(jù)第條遍歷路徑形成一個單播請求，并轉(zhuǎn)至（c）；否則繼續(xù)（b）。

（b）根據(jù)網(wǎng)絡(luò)資源使用狀況和多播業(yè)務(wù)請求帶寬，與（a）相同，根據(jù)公式3.1和3.2以及，重新設(shè)置光路和波長鏈路的代價。采用MPH算法為業(yè)務(wù)請求計算一棵多播樹，在這棵多播樹中可能是光路鏈路、波長鏈路和虛鏈路的組合。如果計算成功，與（a）相同，則轉(zhuǎn)至（d）；否則業(yè)務(wù)阻塞，轉(zhuǎn)至步驟2。

（c）針對每個單播請求。根據(jù)保護請求帶寬形成與鏈路分離的可用的虛拓撲圖，并根據(jù)公式3.4和重新設(shè)置光路代價，轉(zhuǎn)至（e）。

（d）針對單播請求。根據(jù)保護請求帶寬b形成與遍歷路徑鏈路分離的可用的聯(lián)合疏導(dǎo)圖，并根據(jù)公式3.3和3.4及重新設(shè)置光路和波長鏈路的代價，轉(zhuǎn)至（e）。

（e）利用Dijkstra’s算法為所有單播請求計算保護路徑，如果為至少個請求選路成功，則轉(zhuǎn)至（f），否則業(yè)務(wù)阻塞，轉(zhuǎn)至步驟2。

（f）利用最小遍歷樹算法選出代價最小的保護路徑集。如果工作樹中任意鏈路故障都通過保護路徑恢復(fù)業(yè)務(wù)，則記錄保護路徑集信息，并轉(zhuǎn)至步驟4，否則業(yè)務(wù)阻塞，轉(zhuǎn)至步驟2。

步驟4：為多播業(yè)務(wù)請求分配資源，為建立的所有保護路徑預(yù)留資源。統(tǒng)計新建光路在IP路由端口、光收發(fā)器、光放大器等器件所消耗的能量。

步驟5：釋放鏈路帶寬資源，更新節(jié)點空閑光收發(fā)器資源和IP路由器端口資源，如果某節(jié)點的光收發(fā)器由無到有，則恢復(fù)這個節(jié)點的虛鏈路。

四、仿真分析

本章將DMGAS算法分別與沒有采用疏導(dǎo)技術(shù)的多播遍歷路徑專用保護算法（DMPAS）[3]、多播疏導(dǎo)專用樹保護算法（DMGAT）[3]和多播疏導(dǎo)專用分段保護算法（DMGASE）[3]進行了比較。最后分析了不同的代價設(shè)置參數(shù)對算法DMGAS的影響。網(wǎng)絡(luò)拓撲模型為USNET，每個節(jié)點都采用的是結(jié)構(gòu)和功能相同的GMC-OXC，并且具有完全分光能力，且配備有足夠多的光收發(fā)器。在網(wǎng)絡(luò)中每條物理鏈路可容納的波長數(shù)相同為2，每個波長所支持的帶寬為OC-48。

如圖4.1所示，四種算法在網(wǎng)絡(luò)負載增加時業(yè)務(wù)阻塞率不斷增加，其中DMPAS最差，DMGAT和DMGASE其次，DMGAS最好。DMGAS阻塞率較低的原因是采用了基于遍歷路徑的保護方式，這種方式不會像基于樹保護時對鏈路分離的限制那么高，只需要與被保護的遍歷路徑鏈路分離即可，也不會像基于分段保護需要較多的保護路徑。所以在網(wǎng)絡(luò)負載較低的情況下業(yè)務(wù)阻塞率幾乎為零，網(wǎng)絡(luò)負載較高的情況下業(yè)務(wù)阻塞率的增漲也很緩慢。

圖4.1四種算法業(yè)務(wù)阻塞率BR的比較

比如DMPAS算法的平均能耗一直比較平穩(wěn)。DMGAS算法的平均能耗則是隨著網(wǎng)絡(luò)負載的增加而逐漸降低，但DMGAT算法的平均能耗最高，然后是DMGASE算法，最低是DMGAS算法。DMGAT和DMGASE這兩個算法總能耗相差不多，但DMGASE的業(yè)務(wù)阻塞率低，平均每個業(yè)務(wù)的能耗就要低一些。DMGAS的平均能耗較低是因為除了采用光旁路和業(yè)務(wù)量疏導(dǎo)這兩個技術(shù)外，還采用設(shè)備睡眠技術(shù)。

圖4.2在DMGAS算法中代價設(shè)置參數(shù)對AEC的影響

圖4.2所示，四種參數(shù)的DMGAS算法平均能耗趨勢均與仿真時鐘相似，隨著網(wǎng)絡(luò)負載的增加，平均能耗降低，在網(wǎng)絡(luò)負載低時下降速度非?？欤?dāng)網(wǎng)絡(luò)負載高時平均能耗趨于平穩(wěn)。在相同負載下，越大，平均能耗越低。平均能耗均降低的主要原因是隨著網(wǎng)絡(luò)負載的增加，處理相同數(shù)目的業(yè)務(wù)所需要的時間越短，消耗的總能耗也就越少。參數(shù)越大，就有越多的工作路徑和保護路徑分別集中，使更多的鏈路進入睡眠狀態(tài)。但代價設(shè)置參數(shù)過高，并沒有對能耗有更大的貢獻，反而使業(yè)務(wù)阻塞率增加。的增加能有效的降低網(wǎng)絡(luò)能耗，但其代價是業(yè)務(wù)阻塞率增加，并且其增加到一定程度后便失去了對節(jié)能的貢獻。

五、結(jié)論

本文研究了基于ASON的多播專用綠色疏導(dǎo)保護算法，首先設(shè)計了輔助圖，并將專用多播保護節(jié)能問題抽象成數(shù)學(xué)模型，然后提出了改變鏈路代價的公式并設(shè)計了算法。仿真分析顯示，我們所提出的算法不但在阻塞率方面較先前算法有所提高，而且更加節(jié)能。

參考文獻：

[1]溫海波.WDM網(wǎng)狀網(wǎng)中的業(yè)務(wù)量疏導(dǎo)算法研究[D]，電子科技大學(xué)，2004.

[2]Idzikowski F， Orlowski S， Raack C， et al. Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios[C]， Conference on Optical Network Design and Modeling （ONDM）， 2010， 1-6.