基于資源影響力的組播快速重構機制

莫 涵，蘭巨龍，賀 煒

（國家數字交換系統工程技術研究中心，河南 鄭州450002）

0 引 言

互聯網的快速發展和廣泛部署，使得以IPTV、網絡視頻和遠程教育等為代表的新型多媒體應用迅猛發展，已成為當前互聯網的基礎業務[1]，是互聯網最為重要的應用和核心體驗。組播技術采用樹狀結構，實現了一對多或多對多的通信方式，可有效節約帶寬，減輕網絡負載，滿足了多媒體應用的傳輸需求。但是，樹狀結構具有兩面性，雖然可以節約資源，但當網絡出現故障時，一條鏈路或者一個節點的失效將會導致下游所有組成員節點無法接收數據，影響甚廣。因此，為確保網絡出現故障時，網絡仍能對多媒體應用提供足夠的服務水平，研究組播快速故障恢復技術是十分必要的。

網絡故障不僅可能發生在工作路徑，還可能發生在備份路徑上?，F有方案[2，3]多數通過建立多條備份路徑并設置優先級來解決備份路徑故障的問題，但這樣一來計算復雜度增加，同時網絡資源大量浪費。因此，本文提出了一種基于資源影響力的組播快速重構機制 （fast multicast reconfigurable scheme based on resource effect degree，REDMRS），旨在實現組播故障快速恢復。RED－MRS刻畫了不同網絡資源的重要程度，資源越重要，說明該資源故障對組播樹的影響越大、破壞性越高。在構建備份組播樹時，通過加入對資源重要程度的考慮，避免占用重要程度較高的資源，可以構建具有容錯能力的備份組播樹，減少備份組播樹出故障的可能性，并均衡資源利用。同時，REDMRS機制采用本地處理方式，直接激活備用父節點，恢復速度快。

1 相關工作

組播快速故障恢復方法主要分為兩類:被動式，在故障發生檢測到故障點后，重新尋找和建立新的路徑來完成傳輸服務，又稱為按需恢復。該方法不需要預留資源，但恢復時間較長，無法滿足時延要求較高的通信需求；主動式，在故障發生之前，預先計算備份路徑，并預留相應資源。主動式方法[4]在故障發生時可實現快速切換，恢復時間短，但會消耗較多的網絡資源。顯然，備份路徑的計算時間和資源利用率兩者間互相矛盾。

針對保護對象的不同，組播主動式故障恢復方法又分為兩種:

（1）局部保護，分別為每一條源到目的節點的路徑建立保護路徑，包括鏈路保護與路徑保護。

鏈路保護與路徑保護分別借鑒于單播中的鏈路恢復和路徑恢復方法。鏈路保護方法為每條鏈路的兩個節點間預先建立一條備用路由，若原始組播樹中鏈路出現故障，故障檢測點通過本地恢復繞過故障鏈路，將數據發送到故障鏈路的下游節點。路徑保護方法為每個組成員節點建立一條從源到目的端的備用路徑，要求備用路徑與原始組播樹中從源到目的端的路徑是不相交的。

（2）組播組保護，為整個組播樹建立一個備份樹，主要方法有冗余樹保護和雙樹保護。

冗余樹保護方法[5，6]通過搜索路徑可將網絡中所有節點連接起來，以計算網絡中兩棵不相交的樹，其中一棵作為從源到所有組成員節點的主樹，另一棵是預先建立的備份冗余樹，使得網絡中任何節點 （鏈路）失效時，組成員節點都可通過至少一棵樹連接到源點。冗余樹保護方法不僅可以恢復主樹中出現的任何節點或鏈路故障，而且可以恢復不止一個故障。但構建的組播樹太過冗余，包含了網絡所有節點。同時，兩樹不相交的情況使得冗余樹方法對網絡拓撲結構要求苛刻，網絡必須是雙聯通的，即網絡任意兩節點間至少有兩條節點或鏈路不相交的路徑。

與冗余樹保護方法相比，雙樹保護方法[7]僅計算兩棵連接源到所有組成員節點的組播樹，一棵作為主樹，另一棵作為備份樹。與鏈路保護和路徑保護方法相比，雙樹保護方法不需要對每條鏈路或是路徑進行單獨的管理和維護。雙樹保護方法又分為不相交雙樹和相交雙樹。不相交雙樹要求網絡是雙聯通的，且在任意兩節點間有至少兩條節點或鏈路不相交的路徑，構建起來十分困難。針對不相交備份樹存在構建失敗的問題，相交雙樹則在保護能力和構建成功率兩者間進行了折中，允許部分路徑相交，但不能提供100%的保護。文獻[8]提出可通過共享某些鏈路建立從數據源到目的節點的多條相交路徑來進行故障恢復。同時，文獻[9]證明在網絡拓撲不能保證不相交備份樹一定構建成功的情況下，相交備份樹的可靠性高于不相交備份樹。因此，相交雙樹可有效適應網絡拓撲，確保為組播數據傳輸提供最大限度的保護。

表1給出了常見組播主動式故障恢復方法的比較?？梢钥闯?，局部保護方法管理和維護代價較高，并且易出現路由環路，但對網絡拓撲不特殊要求。而組播組保護管理和維護開銷較小，但若要實現100%的保護，需要網絡具有雙聯通的拓撲結構，同時需要建立一個與原始組播樹鏈路、節點完全不相交的組播樹，實現上非常困難。

表1 組播主動式故障恢復方法

2 組播快速重構機制

本文從如何有效提高備份樹構建成功率和容錯能力的角度出發，提出了一種基于資源影響力的組播快速重構機制 （RED－MRS）。RED－MRS定義了資源影響力，反映資源在網絡中的使用情況，避免備份路徑選取重要程度較大的資源，降低備份樹故障可能性，減少多條備份路徑共存浪費資源的情況，并均衡資源利用。同時，在計算備份樹時，優先選擇計算與原始組播樹不相交的備份樹，若不存在不相交備份樹，則引入相交思想，允許備份樹與原始組播樹部分路徑共享，降低網絡拓撲聯通性要求，提高備份樹構建成功率。

RED－MRS主要包括備份樹計算算法和組播樹重構機制兩部分。其中，備份樹計算算法利用資源影響力選擇備份路徑，計算備份樹；組播樹重構機制用于當原始組播樹出現故障時，快速重構出備份路徑，恢復數據傳輸。

2.1 相關定義

現有組播故障恢復機制沒有對網絡資源進行區分對待，在選擇路徑時忽略了資源對備份路徑的影響。為衡量網絡中各個節點和鏈路在網絡中的重要程度，本文首先提出資源影響力的概念，包括節點影響力和鏈路影響力兩方面。

物理網絡可看作一個加權無向圖G＝（V，E），V為網絡節點集合，例如路由器和交換機等；E為網絡鏈路集合，代表連接網絡節點的通信鏈路。

定義1 節點容量比 （node capacity ration，NCR）:在網絡G中，設節點ni能提供的最大服務能力為Cmax（ni），如內存、CPU等，C（i）表示節點ni已消耗資源，則ni節點容量比為

NCR反映了節點剩余可用資源的多少，NCR越大，說明節點可用資源越多，服務能力越強。

定義2 節點影響力 （node effect degree，NED）:在網絡G中，G中最大的節點度數為dmax，設節點ni的度為di，節點容量比為NCRt（ni），則ni節點影響力為NED（i）＝αdi／dmax＋βNCR（i），其中α和β是調節因子，且α＋β＝1。

NED（i）反映了節點ni在網絡中的重要程度，α和β則可調節節點度和節點容量比在節點影響力中占的比例。NED（i）值越大表示節點ni在網絡中越重要，承載的服務越重。因此，NED（i）值越大說明節點ni出現故障對網絡的影響越大，同時節點ni的后續承載能力越弱。

定義3 鏈路連接度 （link connection degree，LCD）:在網絡G中，設鏈路l（i，j）為連接節點ni和節點nj的一條鏈路，則節點ni和節點nj的度可以反映鏈路l（i，j）在網絡中的連接程度，表示為稱為鏈路連接度。

LCD（i，j）越大，說明鏈路l（i，j）出現故障時對節點ni和節點nj的影響越大。

定義4 鏈路容量比 （link capacity ration，LCR）:在網絡G中，設鏈路l（i，j）能提供的最大服務能力為Cmax（l（i，j）），如鏈路帶寬等，Ct（l（i，j））表示鏈路l（i，j）已消耗資源，則l（i，j）鏈路容量比為LCR（i，j）＝1－

LCR反映了鏈路剩余資源的多少，LCR越大，說明鏈路可用資源越多，服務能力越強。

定義5 鏈路影響力 （link effect degree，LED）:在網絡G中，鏈路l（i，j）的連接度為LCD（i，j），鏈路容量比為LCRt（i，j）， 則l（i，j）鏈 路 影 響 力 為LED（i，j）＝ρLCD（i，j）＋μLCR（i，j），其中ρ和μ是調節因子，且ρ＋μ＝1。

LED（i，j）反映了鏈路l（i，j）在網絡中的重要程度，ρ和μ則可調節鏈路連接度和鏈路容量比在鏈路影響力中占的比例。LED（i，j）值越大表示鏈路l（i，j）在網絡中越重要，承載的服務越重。因此，LED（i，j）值越大說明鏈路l（i，j）出現故障對網絡的影響越大，同時鏈路l（i，j）的后續承載能力越弱。

定義6 資源影響力 （resource effect degree，RED）:綜合考慮節點影響力和鏈路影響力，可得資源影響力，用式 （1）表示

2.2 備份樹計算算法

現有備份組播樹計算算法通常采用不相交雙樹保護算法，對網絡拓撲限制較大，構建成功率不高。文獻[10]分別對節點不相交和鏈路不相交雙樹進行試驗，結果表明在節點個數為100的隨機網絡中，隨著組成員的增多，平均構建成功率逐漸下降，當組成員數目為30時，鏈路不相交雙樹的構建成功率為7%，而節點不相交雙樹構建成功率更低，幾乎無法構建成功。因此，本文的備份樹計算算法采用如下策略:優先選擇計算不相交備份樹；若不存在不相交的備份樹，則允許備份樹與原始組播樹部分相交，共享某些節點和鏈路。

在計算備份樹時，不僅要考慮代價，還要盡量避免占用影響力較大的資源，以提高備份樹的容錯能力，均衡資源利用。因此，結合資源影響力，給出備份樹代價函數，見式 （2）

其中c（n）、c（e）分別代表節點和鏈路的初始代價。由式 （2）可知，資源影響力越大，占用其資源計算的備份樹代價越高。按照式 （2），備份樹上，源s到每個目的節點di（di∈D）的備份路徑的代價定義為

同時，為了盡可能減少備份樹與原始組播樹中共享的節點和鏈路的數目，則計算備份樹或備份路徑時，原始組播樹上的節點和鏈路的影響力分別如式 （4）和式 （5）

其中NED（i）和LED（i，j）分別為原始節點和鏈路的影響力，σ1為網絡中所有節點的影響力之和，σ2為網絡中所有鏈路的影響力之和，使得組播樹中資源的影響力大于網絡G中其余任意資源的影響力。

備份樹計算算法見表2。

算法步驟1－2實現初始化，并將備份樹的計算過程分解為組播源到每個目的節點的路徑計算。步驟3－6利用最短路徑算法計算s到di的最小代價路徑PminC b（s，di）；步驟4在網絡G中，刪除原始組播樹上的所有中間節點和鏈路，計算與原始路徑P（s，di）節點不相交的備份路徑；若步驟4不成功，則步驟5在網絡G＇中，加入原始組播樹上的中間節點，計算與原始路徑P（s，di）鏈路不相交的備份路徑；若步驟5不成功，則步驟6在網絡G中利用最短路徑算法尋找源到每個目的節點的代價最小路徑，此時允許備份路徑與原始路徑相交。步驟7將計算的備份路徑加入到備份樹中。步驟8比較Tb（s，D）與T（s，D），防止出現原始組播樹與備份樹相同的情況。

表2 備份樹計算算法

2.3 組播樹重構機制

當原始組播樹中的節點或者鏈路出現故障時，通過激活故障源子節點在備份樹上的父節點，組播樹重構機制對原始組播樹進行重構，激活備用路徑，實現將數據流快速切換到可用父節點。組播樹重構機制對故障采用本地處理方式，相比于分布式方式可用性高，恢復速度快。組播樹重構機制見表3。

表3 組播樹重構機制

算法步驟1首先發現故障，定位故障源。步驟2－7說明激活備份路徑的過程:由故障源的子節點開始，發起重構消息，收到重構消息的節點依次激活備用樹上的父節點，直到重構出備份路徑，故障源的子節點再次連接到原始組播樹上。

組播樹重構機制不僅可處理鏈路故障，也可處理節點故障。同時，由于事先計算了備份樹，組播樹重構機制只需依次重構出各故障源子節點的備份路徑，便可解決多點故障。

3 算法分析與仿真實驗

3.1 實驗設置

實驗環境為Intel（R）Core（TM）i7CPU 2.67GHz、RAM 2G的普通PC，通過NS－2仿真軟件實現RED－MRS機制，并與冗余樹方法[5]、不相交雙樹方法[7]和相交雙樹[10]算法進行性能比較。為確保算法性能的普適性，本文在Salama拓撲生成模型上進行了改進，生成平均節點度為4的不同大小的隨機網絡，節點個數在[20，160]之間隨機選擇。同時，隨機生成一個組播組，假定組播組的大小是網絡中節點數目的30%，組播源和目的節點在拓撲上隨機選擇。

仿真過程中，每條節點和鏈路的原始代價均被設置為1，節點和鏈路的容量比在[0，1]隨機分配。式 （1）中α、β、ρ、μ均取0.5。為了反映更準確的結果，仿真共進行200次，取所有實驗結果的平均值。

3.2 恢復時間

恢復時間是組播故障恢復方法的重要指標，反應了通信中斷的時間，恢復時間越短，通信中斷的時間越短，對通信的影響越小。

圖1給出了不同網絡規模下4種算法的平均恢復時間。從圖中可以看出，RED－MRS所需的平均恢復時間最短，而冗余樹方法的恢復時間最長。這是由于冗余樹方法對端到端的路徑進行備份，激活過程中，需要依次通知故障節點以下的所有節點，導致恢復時間較長。而RED－MRS只需依次激活備份樹上收到重構消息的父節點，重構出備份路徑即可，恢復過程需要激活的節點少，時間較短。不相交雙樹方法需要對故障節點之下的部分中間節點進行操作，恢復時間比RED－MRS長。相交雙樹方法對故障也采用本地處理方式，但在處理過程中需要在原始父節點和備份父節點間進行切換，因此恢復時間比RED－MRS略長。

3.3 組播樹代價

圖1 平均恢復時間

組播樹代價反應了組播傳輸性能，組播樹代價越小，傳輸性能越好。為便于比較，對于恢復后的組播樹代價按計算，不考慮資源的影響。圖2給出了4種方法法對應的故障恢復后組播樹代價?？梢钥闯?，冗余樹方法和不相交雙樹方法的代價基本相同，且高于相交雙樹和RED－MRS，RED－MRS的代價最小。這是由于冗余樹方法和不相交雙樹方法的核心思想較為相似，原始組播樹為最小代價樹，而備份組播樹由于原始組播樹不相交，因此代價較高；相交雙樹方法允許備份樹和原組播樹有一定程度的交集，可以利用原組播樹中的一些路徑，因此備份樹的代價有所降低，但在構建原始組播樹時隨機選取節點使得其代價仍高于RED－MRS；RED－MRS不僅允許備份樹和原組播樹有一定的交集，同時計算時備份樹時盡可能使代價最小，因此代價值最低。

圖2 恢復后的組播樹代價

3.4 資源影響力

在網絡節點數目為100個，組成員數目為30個的條件下，對網絡中的資源使用情況進行測試。圖3給出了執行4種方法后，具有不同資源影響力的資源在全部資源中所占的百分比?？梢钥闯?，RED＿MRS的效果最好，結果中影響力偏高或者偏低的資源數目較少，影響力居中的節點在全部資源中占多數，較好的實現了資源的均衡利用。冗余樹和不相交雙樹中，高影響力和低影響力的資源都較多，沒有充分發揮資源的能力，造成資源的浪費。相交雙樹方案由于隨機選擇資源，導致資源利用不均衡，雖然低影響力的資源較少，但高影響力的資源仍然較多。

圖3 不同影響力的資源占全部資源的百分比

4 結束語

本文設計了一種基于資源影響力的組播快速重構機制RED－MRS，實現了組播故障快速恢復。RED－MRS刻畫了網絡資源的重要程度，在計算備份樹的過程中綜合考慮代價及資源影響力，避免備份路徑占用重要程度較大的資源，降低了備份樹故障可能性，并實現了資源的均衡利用。同時，允許備份樹與原始組播樹共享某些節點或鏈路，有效提高備份樹構建成功率。當網絡出現故障時，RED－MRS采用組播樹重構機制激活備份路徑，保證了備份路徑的快速重構和恢復。仿真結果表明，RED－MRS在恢復時間、組播樹代價和資源利用三方面均優于現有方法。

[1]China Internet Network Information Center.The status report on Internet development in China[EB／OL].[2013－01－15].http:／／www.cnnic.cn／hlwfzyj／hlwxzbg／ （in Chinese）.[中國互聯網絡信息中心.中國互聯網絡發展狀況統計報告[EB／OL].[2013－01－15].http:／／www.cnnic.cn／hlwfzyj／hlwxzbg／.]

[2]YANG Zhenqi，HE Wenting，YANG Yunxue.Research on MPLS fast reroute multi－failure recovery algorithm[J].Computer Engineering and Design，2012，33 （6）:2133－2136 （in Chinese）.[楊振啟，何文庭，楊云雪.MPLS快速重路由多故障恢復算法的研究[J].計算機工程與設計，2012，33（6）:2133－2136.]

[3]REN Jinqiu，ZHANG Jianhui，WANG Binqiang.Fast recovery from multi－failure patterns in MPLS networks[J].Computer Engineering and Design，2008，29 （15）:3861－3903 （in Chinese）.[任金秋，張建輝，汪斌強.支持多故障恢復的 MPLS快速重路由[J].計算機工程與設計，2008，29 （15）:3861－3903.]

[4]Kvalbein A，Audun Fosselie Hansen，Cicic T，et al.Fast IP network recovery using multiple muting configurations[C]／／Proceeding of IEEE INFOCOM，Barcelona，Spain，2006:1－11.

[5]Yigal Bejerano，Pramod V Koppol.Optimal construction of redundant multicast trees in directed graphs[C]／／Proceeding of IEEE INFOCOM，2009:2696－2700.

[6]WANG Shang，HE Chun，ZHANG Yide，et al.Construction of multicast protection tree based on single node failure[C]／／International Conference on Communications and Mobile Computing，2010:202－206.

[7]Mohand Yazid Saidi，Bernard Cousin，Miklos Molnar.Improved dual－forest for multicast protection[C]／／The 2nd Conference on Next Generation Internet Design and Engineering，2006:371－378.

[8]WANG J，YANG M，YANG B，et al.Dual－homing based scalable partial multicast projection[J].IEEE Transactions on Computer，2006，55 （9）:1130－1140.

[9]WANG Xiaonan.Algorithm research on multicast routing with fault－tolerance and high reliability[D].Zhengzhou:PLA Information Engineering University，2010 （in Chinese）.[王肖楠.高可靠性的容錯組播路由算法研究[D].鄭州:解放軍信息工程大學，2010.]

[10]WANG Xiaonan，CHENG Dongnian，ZHANG Jianhui.Braided multipaths based multicast preactive recovery scheme[J].Application of Electronic Technique，2010 （7）:112－116 （in Chinese）.[王肖楠，程東年，張建輝.基于相交多路徑的組播主動 式 恢 復 方 案[J].電 子 技 術 應 用，2010 （7）:112－116.]