莫 涵，蘭巨龍，賀 煒

（國家數(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ù)采用樹狀結(jié)構(gòu)，實(shí)現(xiàn)了一對多或多對多的通信方式，可有效節(jié)約帶寬，減輕網(wǎng)絡(luò)負(fù)載，滿足了多媒體應(yīng)用的傳輸需求。但是，樹狀結(jié)構(gòu)具有兩面性，雖然可以節(jié)約資源，但當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí)，一條鏈路或者一個(gè)節(jié)點(diǎn)的失效將會(huì)導(dǎo)致下游所有組成員節(jié)點(diǎn)無法接收數(shù)據(jù)，影響甚廣。因此，為確保網(wǎng)絡(luò)出現(xiàn)故障時(shí)，網(wǎng)絡(luò)仍能對多媒體應(yīng)用提供足夠的服務(wù)水平，研究組播快速故障恢復(fù)技術(shù)是十分必要的。

網(wǎng)絡(luò)故障不僅可能發(fā)生在工作路徑，還可能發(fā)生在備份路徑上?，F(xiàn)有方案[2，3]多數(shù)通過建立多條備份路徑并設(shè)置優(yōu)先級(jí)來解決備份路徑故障的問題，但這樣一來計(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ò)資源的重要程度，資源越重要，說明該資源故障對組播樹的影響越大、破壞性越高。在構(gòu)建備份組播樹時(shí)，通過加入對資源重要程度的考慮，避免占用重要程度較高的資源，可以構(gòu)建具有容錯(cuò)能力的備份組播樹，減少備份組播樹出故障的可能性，并均衡資源利用。同時(shí)，REDMRS機(jī)制采用本地處理方式，直接激活備用父節(jié)點(diǎn)，恢復(fù)速度快。

1 相關(guān)工作

組播快速故障恢復(fù)方法主要分為兩類:被動(dòng)式，在故障發(fā)生檢測到故障點(diǎn)后，重新尋找和建立新的路徑來完成傳輸服務(wù)，又稱為按需恢復(fù)。該方法不需要預(yù)留資源，但恢復(fù)時(shí)間較長，無法滿足時(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í)間和資源利用率兩者間互相矛盾。

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

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

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

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

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

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

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

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

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

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

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

2.1 相關(guān)定義

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

物理網(wǎng)絡(luò)可看作一個(gè)加權(quán)無向圖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越大，說明節(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）值越大說明節(jié)點(diǎn)ni出現(xiàn)故障對網(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）越大，說明鏈路l（i，j）出現(xiàn)故障時(shí)對節(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）鏈路容量比為LCR（i，j）＝1－

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

定義5 鏈路影響力 （link effect degree，LED）:在網(wǎng)絡(luò)G中，鏈路l（i，j）的連接度為LCD（i，j），鏈路容量比為LCRt（i，j）， 則l（i，j）鏈 路 影 響 力 為LED（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）值越大說明鏈路l（i，j）出現(xiàn)故障對網(wǎng)絡(luò)的影響越大，同時(shí)鏈路l（i，j）的后續(xù)承載能力越弱。

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

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

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

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

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

同時(shí)，為了盡可能減少備份樹與原始組播樹中共享的節(jié)點(diǎn)和鏈路的數(shù)目，則計(jì)算備份樹或備份路徑時(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ò)中所有鏈路的影響力之和，使得組播樹中資源的影響力大于網(wǎng)絡(luò)G中其余任意資源的影響力。

備份樹計(jì)算算法見表2。

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

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

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

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

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

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

組播樹重構(gòu)機(jī)制不僅可處理鏈路故障，也可處理節(jié)點(diǎn)故障。同時(shí)，由于事先計(jì)算了備份樹，組播樹重構(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，通過NS－2仿真軟件實(shí)現(xiàn)RED－MRS機(jī)制，并與冗余樹方法[5]、不相交雙樹方法[7]和相交雙樹[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ī)選擇。

仿真過程中，每條節(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í)間越短，對通信的影響越小。

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

3.3 組播樹代價(jià)

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

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

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

3.4 資源影響力

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

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

4 結(jié)束語

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