基于資源影響力的組播快速重構(gòu)機(jī)制

莫 涵，蘭巨龍，賀 煒

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州450002）

0 引 言

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

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

1 相關(guān)工作

組播快速故障恢復(fù)方法主要分為兩類:被動(dòng)式，在故障發(fā)生檢測(cè)到故障點(diǎn)后，重新尋找和建立新的路徑來(lái)完成傳輸服務(wù)，又稱為按需恢復(fù)。該方法不需要預(yù)留資源，但恢復(fù)時(shí)間較長(zhǎng)，無(wú)法滿足時(shí)延要求較高的通信需求；主動(dòng)式，在故障發(fā)生之前，預(yù)先計(jì)算備份路徑，并預(yù)留相應(yīng)資源。主動(dòng)式方法[4]在故障發(fā)生時(shí)可實(shí)現(xiàn)快速切換，恢復(fù)時(shí)間短，但會(huì)消耗較多的網(wǎng)絡(luò)資源。顯然，備份路徑的計(jì)算時(shí)間和資源利用率兩者間互相矛盾。

針對(duì)保護(hù)對(duì)象的不同，組播主動(dòng)式故障恢復(fù)方法又分為兩種:

（1）局部保護(hù)，分別為每一條源到目的節(jié)點(diǎn)的路徑建立保護(hù)路徑，包括鏈路保護(hù)與路徑保護(hù)。

鏈路保護(hù)與路徑保護(hù)分別借鑒于單播中的鏈路恢復(fù)和路徑恢復(fù)方法。鏈路保護(hù)方法為每條鏈路的兩個(gè)節(jié)點(diǎn)間預(yù)先建立一條備用路由，若原始組播樹(shù)中鏈路出現(xiàn)故障，故障檢測(cè)點(diǎn)通過(guò)本地恢復(fù)繞過(guò)故障鏈路，將數(shù)據(jù)發(fā)送到故障鏈路的下游節(jié)點(diǎn)。路徑保護(hù)方法為每個(gè)組成員節(jié)點(diǎn)建立一條從源到目的端的備用路徑，要求備用路徑與原始組播樹(shù)中從源到目的端的路徑是不相交的。

（2）組播組保護(hù)，為整個(gè)組播樹(shù)建立一個(gè)備份樹(shù)，主要方法有冗余樹(shù)保護(hù)和雙樹(shù)保護(hù)。

冗余樹(shù)保護(hù)方法[5，6]通過(guò)搜索路徑可將網(wǎng)絡(luò)中所有節(jié)點(diǎn)連接起來(lái)，以計(jì)算網(wǎng)絡(luò)中兩棵不相交的樹(shù)，其中一棵作為從源到所有組成員節(jié)點(diǎn)的主樹(shù)，另一棵是預(yù)先建立的備份冗余樹(shù)，使得網(wǎng)絡(luò)中任何節(jié)點(diǎn) （鏈路）失效時(shí)，組成員節(jié)點(diǎn)都可通過(guò)至少一棵樹(shù)連接到源點(diǎn)。冗余樹(shù)保護(hù)方法不僅可以恢復(fù)主樹(shù)中出現(xiàn)的任何節(jié)點(diǎn)或鏈路故障，而且可以恢復(fù)不止一個(gè)故障。但構(gòu)建的組播樹(shù)太過(guò)冗余，包含了網(wǎng)絡(luò)所有節(jié)點(diǎn)。同時(shí)，兩樹(shù)不相交的情況使得冗余樹(shù)方法對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)要求苛刻，網(wǎng)絡(luò)必須是雙聯(lián)通的，即網(wǎng)絡(luò)任意兩節(jié)點(diǎn)間至少有兩條節(jié)點(diǎn)或鏈路不相交的路徑。

與冗余樹(shù)保護(hù)方法相比，雙樹(shù)保護(hù)方法[7]僅計(jì)算兩棵連接源到所有組成員節(jié)點(diǎn)的組播樹(shù)，一棵作為主樹(shù)，另一棵作為備份樹(shù)。與鏈路保護(hù)和路徑保護(hù)方法相比，雙樹(shù)保護(hù)方法不需要對(duì)每條鏈路或是路徑進(jìn)行單獨(dú)的管理和維護(hù)。雙樹(shù)保護(hù)方法又分為不相交雙樹(shù)和相交雙樹(shù)。不相交雙樹(shù)要求網(wǎng)絡(luò)是雙聯(lián)通的，且在任意兩節(jié)點(diǎn)間有至少兩條節(jié)點(diǎn)或鏈路不相交的路徑，構(gòu)建起來(lái)十分困難。針對(duì)不相交備份樹(shù)存在構(gòu)建失敗的問(wèn)題，相交雙樹(shù)則在保護(hù)能力和構(gòu)建成功率兩者間進(jìn)行了折中，允許部分路徑相交，但不能提供100%的保護(hù)。文獻(xiàn)[8]提出可通過(guò)共享某些鏈路建立從數(shù)據(jù)源到目的節(jié)點(diǎn)的多條相交路徑來(lái)進(jìn)行故障恢復(fù)。同時(shí)，文獻(xiàn)[9]證明在網(wǎng)絡(luò)拓?fù)洳荒鼙ＷC不相交備份樹(shù)一定構(gòu)建成功的情況下，相交備份樹(shù)的可靠性高于不相交備份樹(shù)。因此，相交雙樹(shù)可有效適應(yīng)網(wǎng)絡(luò)拓?fù)?，確保為組播數(shù)據(jù)傳輸提供最大限度的保護(hù)。

表1給出了常見(jiàn)組播主動(dòng)式故障恢復(fù)方法的比較?？梢钥闯?，局部保護(hù)方法管理和維護(hù)代價(jià)較高，并且易出現(xiàn)路由環(huán)路，但對(duì)網(wǎng)絡(luò)拓?fù)洳惶厥庖蟆６M播組保護(hù)管理和維護(hù)開(kāi)銷較小，但若要實(shí)現(xiàn)100%的保護(hù)，需要網(wǎng)絡(luò)具有雙聯(lián)通的拓?fù)浣Y(jié)構(gòu)，同時(shí)需要建立一個(gè)與原始組播樹(shù)鏈路、節(jié)點(diǎn)完全不相交的組播樹(shù)，實(shí)現(xiàn)上非常困難。

表1 組播主動(dòng)式故障恢復(fù)方法

2 組播快速重構(gòu)機(jī)制

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

RED－MRS主要包括備份樹(shù)計(jì)算算法和組播樹(shù)重構(gòu)機(jī)制兩部分。其中，備份樹(shù)計(jì)算算法利用資源影響力選擇備份路徑，計(jì)算備份樹(shù)；組播樹(shù)重構(gòu)機(jī)制用于當(dāng)原始組播樹(shù)出現(xiàn)故障時(shí)，快速重構(gòu)出備份路徑，恢復(fù)數(shù)據(jù)傳輸。

2.1 相關(guān)定義

現(xiàn)有組播故障恢復(fù)機(jī)制沒(méi)有對(duì)網(wǎng)絡(luò)資源進(jìn)行區(qū)分對(duì)待，在選擇路徑時(shí)忽略了資源對(duì)備份路徑的影響。為衡量網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)和鏈路在網(wǎng)絡(luò)中的重要程度，本文首先提出資源影響力的概念，包括節(jié)點(diǎn)影響力和鏈路影響力兩方面。

物理網(wǎng)絡(luò)可看作一個(gè)加權(quán)無(wú)向圖G＝（V，E），V為網(wǎng)絡(luò)節(jié)點(diǎn)集合，例如路由器和交換機(jī)等；E為網(wǎng)絡(luò)鏈路集合，代表連接網(wǎng)絡(luò)節(jié)點(diǎn)的通信鏈路。

定義1 節(jié)點(diǎn)容量比 （node capacity ration，NCR）:在網(wǎng)絡(luò)G中，設(shè)節(jié)點(diǎn)ni能提供的最大服務(wù)能力為Cmax（ni），如內(nèi)存、CPU等，C（i）表示節(jié)點(diǎn)ni已消耗資源，則ni節(jié)點(diǎn)容量比為

NCR反映了節(jié)點(diǎn)剩余可用資源的多少，NCR越大，說(shuō)明節(jié)點(diǎn)可用資源越多，服務(wù)能力越強(qiáng)。

定義2 節(jié)點(diǎn)影響力 （node effect degree，NED）:在網(wǎng)絡(luò)G中，G中最大的節(jié)點(diǎn)度數(shù)為dmax，設(shè)節(jié)點(diǎn)ni的度為di，節(jié)點(diǎn)容量比為NCRt（ni），則ni節(jié)點(diǎn)影響力為NED（i）＝αdi／dmax＋βNCR（i），其中α和β是調(diào)節(jié)因子，且α＋β＝1。

NED（i）反映了節(jié)點(diǎn)ni在網(wǎng)絡(luò)中的重要程度，α和β則可調(diào)節(jié)節(jié)點(diǎn)度和節(jié)點(diǎn)容量比在節(jié)點(diǎn)影響力中占的比例。NED（i）值越大表示節(jié)點(diǎn)ni在網(wǎng)絡(luò)中越重要，承載的服務(wù)越重。因此，NED（i）值越大說(shuō)明節(jié)點(diǎn)ni出現(xiàn)故障對(duì)網(wǎng)絡(luò)的影響越大，同時(shí)節(jié)點(diǎn)ni的后續(xù)承載能力越弱。

定義3 鏈路連接度 （link connection degree，LCD）:在網(wǎng)絡(luò)G中，設(shè)鏈路l（i，j）為連接節(jié)點(diǎn)ni和節(jié)點(diǎn)nj的一條鏈路，則節(jié)點(diǎn)ni和節(jié)點(diǎn)nj的度可以反映鏈路l（i，j）在網(wǎng)絡(luò)中的連接程度，表示為稱為鏈路連接度。

LCD（i，j）越大，說(shuō)明鏈路l（i，j）出現(xiàn)故障時(shí)對(duì)節(jié)點(diǎn)ni和節(jié)點(diǎn)nj的影響越大。

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

LCR反映了鏈路剩余資源的多少，LCR越大，說(shuō)明鏈路可用資源越多，服務(wù)能力越強(qiáng)。

定義5 鏈路影響力 （link effect degree，LED）:在網(wǎng)絡(luò)G中，鏈路l（i，j）的連接度為L(zhǎng)CD（i，j），鏈路容量比為L(zhǎng)CRt（i，j）， 則l（i，j）鏈 路 影 響 力 為L(zhǎng)ED（i，j）＝ρLCD（i，j）＋μLCR（i，j），其中ρ和μ是調(diào)節(jié)因子，且ρ＋μ＝1。

LED（i，j）反映了鏈路l（i，j）在網(wǎng)絡(luò)中的重要程度，ρ和μ則可調(diào)節(jié)鏈路連接度和鏈路容量比在鏈路影響力中占的比例。LED（i，j）值越大表示鏈路l（i，j）在網(wǎng)絡(luò)中越重要，承載的服務(wù)越重。因此，LED（i，j）值越大說(shuō)明鏈路l（i，j）出現(xiàn)故障對(duì)網(wǎng)絡(luò)的影響越大，同時(shí)鏈路l（i，j）的后續(xù)承載能力越弱。

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

2.2 備份樹(shù)計(jì)算算法

現(xiàn)有備份組播樹(shù)計(jì)算算法通常采用不相交雙樹(shù)保護(hù)算法，對(duì)網(wǎng)絡(luò)拓?fù)湎拗戚^大，構(gòu)建成功率不高。文獻(xiàn)[10]分別對(duì)節(jié)點(diǎn)不相交和鏈路不相交雙樹(shù)進(jìn)行試驗(yàn)，結(jié)果表明在節(jié)點(diǎn)個(gè)數(shù)為100的隨機(jī)網(wǎng)絡(luò)中，隨著組成員的增多，平均構(gòu)建成功率逐漸下降，當(dāng)組成員數(shù)目為30時(shí)，鏈路不相交雙樹(shù)的構(gòu)建成功率為7%，而節(jié)點(diǎn)不相交雙樹(shù)構(gòu)建成功率更低，幾乎無(wú)法構(gòu)建成功。因此，本文的備份樹(shù)計(jì)算算法采用如下策略:優(yōu)先選擇計(jì)算不相交備份樹(shù)；若不存在不相交的備份樹(shù)，則允許備份樹(shù)與原始組播樹(shù)部分相交，共享某些節(jié)點(diǎn)和鏈路。

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

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

同時(shí)，為了盡可能減少備份樹(shù)與原始組播樹(shù)中共享的節(jié)點(diǎn)和鏈路的數(shù)目，則計(jì)算備份樹(shù)或備份路徑時(shí)，原始組播樹(shù)上的節(jié)點(diǎn)和鏈路的影響力分別如式 （4）和式 （5）

其中NED（i）和LED（i，j）分別為原始節(jié)點(diǎn)和鏈路的影響力，σ1為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的影響力之和，σ2為網(wǎng)絡(luò)中所有鏈路的影響力之和，使得組播樹(shù)中資源的影響力大于網(wǎng)絡(luò)G中其余任意資源的影響力。

備份樹(shù)計(jì)算算法見(jiàn)表2。

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

表2 備份樹(shù)計(jì)算算法

2.3 組播樹(shù)重構(gòu)機(jī)制

當(dāng)原始組播樹(shù)中的節(jié)點(diǎn)或者鏈路出現(xiàn)故障時(shí)，通過(guò)激活故障源子節(jié)點(diǎn)在備份樹(shù)上的父節(jié)點(diǎn)，組播樹(shù)重構(gòu)機(jī)制對(duì)原始組播樹(shù)進(jìn)行重構(gòu)，激活備用路徑，實(shí)現(xiàn)將數(shù)據(jù)流快速切換到可用父節(jié)點(diǎn)。組播樹(shù)重構(gòu)機(jī)制對(duì)故障采用本地處理方式，相比于分布式方式可用性高，恢復(fù)速度快。組播樹(shù)重構(gòu)機(jī)制見(jiàn)表3。

表3 組播樹(shù)重構(gòu)機(jī)制

算法步驟1首先發(fā)現(xiàn)故障，定位故障源。步驟2－7說(shuō)明激活備份路徑的過(guò)程:由故障源的子節(jié)點(diǎn)開(kāi)始，發(fā)起重構(gòu)消息，收到重構(gòu)消息的節(jié)點(diǎn)依次激活備用樹(shù)上的父節(jié)點(diǎn)，直到重構(gòu)出備份路徑，故障源的子節(jié)點(diǎn)再次連接到原始組播樹(shù)上。

組播樹(shù)重構(gòu)機(jī)制不僅可處理鏈路故障，也可處理節(jié)點(diǎn)故障。同時(shí)，由于事先計(jì)算了備份樹(shù)，組播樹(shù)重構(gòu)機(jī)制只需依次重構(gòu)出各故障源子節(jié)點(diǎn)的備份路徑，便可解決多點(diǎn)故障。

3 算法分析與仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境為Intel（R）Core（TM）i7CPU 2.67GHz、RAM 2G的普通PC，通過(guò)NS－2仿真軟件實(shí)現(xiàn)RED－MRS機(jī)制，并與冗余樹(shù)方法[5]、不相交雙樹(shù)方法[7]和相交雙樹(shù)[10]算法進(jìn)行性能比較。為確保算法性能的普適性，本文在Salama拓?fù)渖赡Ｐ蜕线M(jìn)行了改進(jìn)，生成平均節(jié)點(diǎn)度為4的不同大小的隨機(jī)網(wǎng)絡(luò)，節(jié)點(diǎn)個(gè)數(shù)在[20，160]之間隨機(jī)選擇。同時(shí)，隨機(jī)生成一個(gè)組播組，假定組播組的大小是網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的30%，組播源和目的節(jié)點(diǎn)在拓?fù)渖想S機(jī)選擇。

仿真過(guò)程中，每條節(jié)點(diǎn)和鏈路的原始代價(jià)均被設(shè)置為1，節(jié)點(diǎn)和鏈路的容量比在[0，1]隨機(jī)分配。式 （1）中α、β、ρ、μ均取0.5。為了反映更準(zhǔn)確的結(jié)果，仿真共進(jìn)行200次，取所有實(shí)驗(yàn)結(jié)果的平均值。

3.2 恢復(fù)時(shí)間

恢復(fù)時(shí)間是組播故障恢復(fù)方法的重要指標(biāo)，反應(yīng)了通信中斷的時(shí)間，恢復(fù)時(shí)間越短，通信中斷的時(shí)間越短，對(duì)通信的影響越小。

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

3.3 組播樹(shù)代價(jià)

圖1 平均恢復(fù)時(shí)間

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

圖2 恢復(fù)后的組播樹(shù)代價(jià)

3.4 資源影響力

在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目為100個(gè)，組成員數(shù)目為30個(gè)的條件下，對(duì)網(wǎng)絡(luò)中的資源使用情況進(jìn)行測(cè)試。圖3給出了執(zhí)行4種方法后，具有不同資源影響力的資源在全部資源中所占的百分比?？梢钥闯?，RED＿M(jìn)RS的效果最好，結(jié)果中影響力偏高或者偏低的資源數(shù)目較少，影響力居中的節(jié)點(diǎn)在全部資源中占多數(shù)，較好的實(shí)現(xiàn)了資源的均衡利用。冗余樹(shù)和不相交雙樹(shù)中，高影響力和低影響力的資源都較多，沒(méi)有充分發(fā)揮資源的能力，造成資源的浪費(fèi)。相交雙樹(shù)方案由于隨機(jī)選擇資源，導(dǎo)致資源利用不均衡，雖然低影響力的資源較少，但高影響力的資源仍然較多。

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

4 結(jié)束語(yǔ)

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

[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）.[中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心.中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[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快速重路由多故障恢復(fù)算法的研究[J].計(jì)算機(jī)工程與設(shè)計(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）.[任金秋，張建輝，汪斌強(qiáng).支持多故障恢復(fù)的 MPLS快速重路由[J].計(jì)算機(jī)工程與設(shè)計(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－h(huán)oming 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）.[王肖楠.高可靠性的容錯(cuò)組播路由算法研究[D].鄭州:解放軍信息工程大學(xué)，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）.[王肖楠，程?hào)|年，張建輝.基于相交多路徑的組播主動(dòng) 式 恢 復(fù) 方 案[J].電 子 技 術(shù) 應(yīng) 用，2010 （7）:112－116.]