孫 偉 ，羅俊海 ，肖志輝

（1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 成都 610031；2.電子科技大學(xué)電子工程學(xué)院 成都 611731；3.邁普通信技術(shù)股份有限公司 成都610041）

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展和網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，多播業(yè)務(wù)得到越來(lái)越多的應(yīng)用，如VoIP、視頻會(huì)議、視頻點(diǎn)播、遠(yuǎn)程教育、在線(xiàn)聊天等。具有健壯性的多播系統(tǒng)會(huì)有較大的市場(chǎng)需求，對(duì)多播系統(tǒng)的保護(hù)和故障后的快速恢復(fù)技術(shù)的研究成為網(wǎng)絡(luò)路由領(lǐng)域的重要課題[1～3]。這些技術(shù)目標(biāo)是尋找有效的方法來(lái)提高多播網(wǎng)絡(luò)的健壯性，確保網(wǎng)絡(luò)通信中數(shù)據(jù)的連續(xù)性或盡可能地減少中斷，這就要求在網(wǎng)絡(luò)中利用冗余的資源提高網(wǎng)絡(luò)的生存性或在檢測(cè)到網(wǎng)絡(luò)故障后能夠快速地確定新的路徑，以繞過(guò)故障節(jié)點(diǎn)或鏈路保證網(wǎng)絡(luò)的正常通信。

網(wǎng)絡(luò)中通過(guò)多路徑傳輸數(shù)據(jù)可以使網(wǎng)絡(luò)健壯性提高、負(fù)載均衡、擁塞減少和吞吐量提高。通常從一個(gè)源節(jié)點(diǎn)到一個(gè)目的節(jié)點(diǎn)可以有多條路徑，如果有足夠的網(wǎng)絡(luò)資源，這些路徑可共享同一鏈路或節(jié)點(diǎn)，為了提高傳輸?shù)目煽啃院捅苊夤蚕礞溌坊蚬?jié)點(diǎn)的失敗，這些路徑則應(yīng)是節(jié)點(diǎn)或鏈路不相交的。

對(duì)節(jié)點(diǎn)/鏈路不相交的多路徑路由的研究已有很多[4,5]，這些研究關(guān)注于多路徑路由對(duì)節(jié)點(diǎn)或鏈路失敗的作用。其中一條路徑作為主路徑，其余作為備用路徑，如果主路徑中鏈路或節(jié)點(diǎn)發(fā)生故障，則數(shù)據(jù)將會(huì)通過(guò)備用路徑傳輸。顏色樹(shù)是一種使用最小的路由表項(xiàng)開(kāi)銷(xiāo)和查詢(xún)時(shí)間實(shí)現(xiàn)節(jié)點(diǎn)/鏈路不相交的多路徑路由的方法[6,7]，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的多條路徑中有兩個(gè)最優(yōu)的鄰居：紅色和藍(lán)色，在源節(jié)點(diǎn)數(shù)據(jù)分組被標(biāo)記為這兩種顏色中的一種，中間節(jié)點(diǎn)通過(guò)識(shí)別數(shù)據(jù)分組的顏色標(biāo)記，轉(zhuǎn)發(fā)數(shù)據(jù)分組到相應(yīng)的鄰居節(jié)點(diǎn)。參考文獻(xiàn)[8]中提出的SimCT算法通過(guò)組建和維護(hù)兩棵節(jié)點(diǎn)/鏈路不相交的顏色樹(shù)，同時(shí)在網(wǎng)絡(luò)節(jié)點(diǎn)/鏈路失敗情況下，通過(guò)本地信息有效地組建新的顏色樹(shù)，提高了網(wǎng)絡(luò)的健壯性。本文在SimCT算法的基礎(chǔ)上，以多播源節(jié)點(diǎn)作為根節(jié)點(diǎn)組建兩棵顏色樹(shù)（Red和Blue），根據(jù)兩棵顏色樹(shù)有效地組建多播數(shù)據(jù)轉(zhuǎn)發(fā)樹(shù)；多播樹(shù)節(jié)點(diǎn)/鏈路失效時(shí)，可通過(guò)顏色樹(shù)快速地組建新的多播轉(zhuǎn)發(fā)樹(shù)，保證網(wǎng)絡(luò)數(shù)據(jù)的傳輸。

2 SimCT算法

SimCT算法分為3個(gè)步驟：

（1）分發(fā)深度優(yōu)先搜索（depth-first-search，DFS）序號(hào)和全局低點(diǎn)值計(jì)算；

（2）網(wǎng)絡(luò)節(jié)點(diǎn)的邏輯分層；

（3）選擇左（Blue）轉(zhuǎn)發(fā)節(jié)點(diǎn)和右（Red）轉(zhuǎn)發(fā)節(jié)點(diǎn)。

（2）中的邏輯分層與節(jié)點(diǎn)/鏈路不相交有關(guān)，本文只考慮節(jié)點(diǎn)不相交的多路徑路由，此處節(jié)點(diǎn)不相交的限制如下。

如果從節(jié)點(diǎn)s到節(jié)點(diǎn)d的Red路徑穿過(guò)節(jié)點(diǎn)i，那么從節(jié)點(diǎn)s到節(jié)點(diǎn)d的Blue路徑則不會(huì)穿過(guò)節(jié)點(diǎn)i，如，坌s∈No0isu0m和坌i∈N{s,d}，則：

算法中所使用的符號(hào)如表1所示。

2.1 分發(fā)DFS序號(hào)

算法的第一階段是為網(wǎng)絡(luò)中各節(jié)點(diǎn)分發(fā)DFS索引序號(hào)和計(jì)算節(jié)點(diǎn)的全局低點(diǎn)值，具體算法如圖1所示。

算法中，節(jié)點(diǎn)x的全局低點(diǎn)值是指節(jié)點(diǎn)x通過(guò)貫穿一系列節(jié)點(diǎn)所能達(dá)到的DFS索引最小的節(jié)點(diǎn)的索引值，即glpv（x）=min（DFS 索引），一系列節(jié)點(diǎn)中，除最后一跳外，其余DFS序號(hào)是遞增的。

2.2 網(wǎng)絡(luò)節(jié)點(diǎn)的邏輯分層

算法的第二個(gè)階段是為網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行邏輯分層，為了限制每一層節(jié)點(diǎn)的全局低點(diǎn)值glpv（x），此處定義一個(gè)勢(shì)值（potential）術(shù)語(yǔ)——即同一層節(jié)點(diǎn)的glpv的邊界值。節(jié)點(diǎn)x的勢(shì)值表示為pot（x），根據(jù)glpv（x）和pot（x）的關(guān)系為節(jié)點(diǎn)分層（odd層和even層）。

表1 SimCT算法中所使用的符號(hào)

圖1 分發(fā)DFS序號(hào)和計(jì)算glpv值的算法

勢(shì)值計(jì)算規(guī)則如下：

p（x）為節(jié)點(diǎn)x的DFS搜索路徑的父節(jié)點(diǎn)。分層規(guī)則如下：

～l（p（x））表示與p（x）不同的層，即如果l（p（x））=odd，則～l（p（x））=even。

2.3 選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)

算法的第3個(gè)階段是為每個(gè)節(jié)點(diǎn)選擇到根節(jié)點(diǎn)的左轉(zhuǎn)發(fā)節(jié)點(diǎn)（Blue）和右轉(zhuǎn)發(fā)節(jié)點(diǎn)（Red）。

如果節(jié)點(diǎn)x在even層，則：

如果節(jié)點(diǎn)x在odd層，則：

通過(guò)SimCT算法組建兩棵不同路徑的顏色樹(shù)，網(wǎng)絡(luò)中各節(jié)點(diǎn)可以通過(guò)兩棵不同顏色樹(shù)到達(dá)根節(jié)點(diǎn)。

3 基于SimCT的多播樹(shù)的組建

3.1 多播樹(shù)的組建

SimCT算法要求網(wǎng)絡(luò)拓?fù)浔仨殲?連接網(wǎng)絡(luò)，即點(diǎn)到點(diǎn)之間至少有兩條通過(guò)不同節(jié)點(diǎn)的路徑，如圖2所示網(wǎng)絡(luò)拓?fù)?。如圖3所示，以多播源節(jié)點(diǎn)S為根節(jié)點(diǎn)使用SimCT算法，組建Red和Blue兩棵顏色樹(shù)，節(jié)點(diǎn)上所標(biāo)序號(hào)為算法中為各節(jié)點(diǎn)分發(fā)的DFS序號(hào)。

圖2 網(wǎng)絡(luò)拓?fù)涫纠?/p>

圖3 用SimCT算法構(gòu)造的以多播源節(jié)點(diǎn)S為根的顏色樹(shù)

為了描述方便，本文把網(wǎng)絡(luò)中的路由節(jié)點(diǎn)，按照在構(gòu)建多播樹(shù)過(guò)程中的不同職責(zé)分成3類(lèi)：源節(jié)點(diǎn)、目的節(jié)點(diǎn)和中間節(jié)點(diǎn)。

源節(jié)點(diǎn)：一個(gè)源節(jié)點(diǎn)對(duì)應(yīng)一棵多播樹(shù)，負(fù)責(zé)發(fā)送多播數(shù)據(jù)，是多播樹(shù)的根節(jié)點(diǎn)。

目的節(jié)點(diǎn)：用于接收從源節(jié)點(diǎn)發(fā)出的多播數(shù)據(jù)，多播樹(shù)的組建將會(huì)連接源節(jié)點(diǎn)和所有目的節(jié)點(diǎn)，是多播樹(shù)的葉子節(jié)點(diǎn)。

中間節(jié)點(diǎn)：在多播樹(shù)中連接源節(jié)點(diǎn)和各個(gè)目的節(jié)點(diǎn)，只負(fù)責(zé)轉(zhuǎn)發(fā)接收的數(shù)據(jù)報(bào)文，是多播樹(shù)的非葉子節(jié)點(diǎn)。

網(wǎng)絡(luò)中需要接收多播數(shù)據(jù)的節(jié)點(diǎn)，沿著到達(dá)多播源節(jié)點(diǎn)的顏色樹(shù)路徑，發(fā)送加入多播組報(bào)文。網(wǎng)絡(luò)中節(jié)點(diǎn)加入多播樹(shù)算法如圖4所示。

多播樹(shù)組建的具體報(bào)文交互過(guò)程如下。

（1）網(wǎng)絡(luò)中目的節(jié)點(diǎn)需要接收多播數(shù)據(jù)，則沿Blue樹(shù)向源節(jié)點(diǎn)方向發(fā)送join報(bào)文。

圖4 節(jié)點(diǎn)加入多播樹(shù)算法

（2）中間節(jié)點(diǎn)維護(hù)兩個(gè)多播表項(xiàng)，即多播樹(shù)的上游節(jié)點(diǎn)列表iif_list和多播樹(shù)的下游節(jié)點(diǎn)列表oif_list。中間節(jié)點(diǎn)x接收join報(bào)文后，將join報(bào)文的發(fā)送節(jié)點(diǎn)添加到oif_list中；同時(shí)，檢查iif_list是否為空，如為空，則將join報(bào)文沿Blue樹(shù)轉(zhuǎn)發(fā)到節(jié)點(diǎn)x的左轉(zhuǎn)發(fā)節(jié)點(diǎn)，并添加節(jié)點(diǎn)x的左轉(zhuǎn)發(fā)節(jié)點(diǎn)（Blue樹(shù)路徑）到iif_list中。如果iif_list不為空，則不再轉(zhuǎn)發(fā)join報(bào)文，并向join報(bào)文接收的方向返回success報(bào)文。

（3）在join報(bào)文發(fā)送過(guò)程中，如果某中間節(jié)點(diǎn)檢測(cè)到Blue樹(shù)的上游節(jié)點(diǎn)或鏈路發(fā)生故障，則join報(bào)文沿Red樹(shù)發(fā)送，即將join報(bào)文轉(zhuǎn)發(fā)到中間節(jié)點(diǎn)的右轉(zhuǎn)發(fā)節(jié)點(diǎn)；如果Red樹(shù)的上游節(jié)點(diǎn)或鏈路也發(fā)生故障，則向join報(bào)文接收的方向返回failure報(bào)文。

（4）如果join報(bào)文沿Blue/Red樹(shù)路徑一路轉(zhuǎn)發(fā)到達(dá)源節(jié)點(diǎn)S，源節(jié)點(diǎn)將join報(bào)文的發(fā)送節(jié)點(diǎn)加入到自己的oif_list中，并向join報(bào)文接收的方向返回success報(bào)文。

（5）中間節(jié)點(diǎn)收到success報(bào)文，轉(zhuǎn)發(fā)報(bào)文至oif_list中各節(jié)點(diǎn)。

（6）中間節(jié)點(diǎn)接收到failure報(bào)文，則將其轉(zhuǎn)發(fā)至oif_list中的各節(jié)點(diǎn)，并刪除相應(yīng)的iif_list和oif_list中的節(jié)點(diǎn)。

（7）目的節(jié)點(diǎn)接收到success報(bào)文，則成功加入多播樹(shù)；如接收到failure報(bào)文，則加入多播樹(shù)失敗。

（8）已成為多播組成員的節(jié)點(diǎn)如不再需要接收多播數(shù)據(jù)，則沿多播樹(shù)上游方向發(fā)送prune報(bào)文。

（9）中間節(jié)點(diǎn)接收到 prune報(bào)文，刪除 oif_list中接收prune報(bào)文的發(fā)送節(jié)點(diǎn)，接著檢查oif_list表項(xiàng)中是否還有節(jié)點(diǎn)項(xiàng)存在，如果有，則不再轉(zhuǎn)發(fā)prune報(bào)文；如oif_list已經(jīng)為空，則轉(zhuǎn)發(fā)prune報(bào)文至iif_list中節(jié)點(diǎn)，之后刪除iif_list中相應(yīng)的節(jié)點(diǎn)項(xiàng)。

圖5 成功組建的多播通信樹(shù)

多播通信是一對(duì)多的通信方式，因此iif_list中表項(xiàng)只有一個(gè)，而oif_list中則可有多個(gè)。為了滿(mǎn)足多播通信中組成員的動(dòng)態(tài)變化，可以通過(guò)發(fā)送加入/剪枝報(bào)文動(dòng)態(tài)地加入或退出多播組。

如網(wǎng)絡(luò)中節(jié)點(diǎn)4、8、9、12想要接收多播數(shù)據(jù)，則通過(guò)本文所述多播的組建過(guò)程，在沒(méi)有故障的情況下得到多播通信樹(shù)如圖5所示。多播通信中如多播成員不再需要接收多播數(shù)據(jù)，則可向多播樹(shù)上游節(jié)點(diǎn)發(fā)送剪枝報(bào)文prune，如節(jié)點(diǎn)12可向上游節(jié)點(diǎn)發(fā)送prune報(bào)文，退出多播組。

3.2 單節(jié)點(diǎn)/鏈路故障恢復(fù)

對(duì)于多播通信而言，多播通信樹(shù)中的任何節(jié)點(diǎn)或鏈路故障都可能影響它下游所有的多播成員的正常通信，因此多播的通信故障恢復(fù)方法復(fù)雜于單播的故障恢復(fù)方法。為了提高多播通信的健壯性，需要有相應(yīng)的通信保護(hù)或故障恢復(fù)措施。

本文提出的多播路由的故障恢復(fù)方法是由檢測(cè)到故障的節(jié)點(diǎn)本地執(zhí)行，快速地將受影響的故障節(jié)點(diǎn)的下游子樹(shù)通過(guò)顏色樹(shù)重新連接到多播樹(shù)。

圖6 故障恢復(fù)過(guò)程中的新路徑選擇算法

基于顏色樹(shù)成功組建的多播通信樹(shù)，如多播樹(shù)中單節(jié)點(diǎn)或單鏈路發(fā)生故障時(shí)，故障恢復(fù)過(guò)程中的新路徑選擇算法如圖6所示。

多播保護(hù)樹(shù)構(gòu)造的具體報(bào)文交互過(guò)程如下。

（1）多播樹(shù)中故障節(jié)點(diǎn)或鏈路的下游節(jié)點(diǎn)檢測(cè)到故障發(fā)生時(shí)，如果該下游節(jié)點(diǎn)的iif_list中節(jié)點(diǎn)為它的左轉(zhuǎn)發(fā)節(jié)點(diǎn)（Blue樹(shù)路徑），則向其右轉(zhuǎn)發(fā)節(jié)點(diǎn)（Red樹(shù)路徑）發(fā)送change報(bào)文，并更新iif_list中節(jié)點(diǎn)項(xiàng)為右轉(zhuǎn)發(fā)節(jié)點(diǎn)；如果iif_list中節(jié)點(diǎn)項(xiàng)為該節(jié)點(diǎn)的右轉(zhuǎn)發(fā)節(jié)點(diǎn) （Red樹(shù)路徑），則向左轉(zhuǎn)發(fā)節(jié)點(diǎn) （Blue樹(shù)路徑）發(fā)送change報(bào)文，并更新iif_list中節(jié)點(diǎn)項(xiàng)為左轉(zhuǎn)發(fā)節(jié)點(diǎn)。

（2）中間節(jié)點(diǎn)接收到change報(bào)文，首先檢查change報(bào)文的發(fā)送節(jié)點(diǎn)是否與iif_list中節(jié)點(diǎn)項(xiàng)相同，如相同則刪除iif_list中對(duì)應(yīng)的此節(jié)點(diǎn)項(xiàng)。同時(shí)將change報(bào)文的發(fā)送節(jié)點(diǎn)添加到oif_list中。

（3）檢查iif_list是否為空，如不為空，則不再轉(zhuǎn)發(fā)change報(bào)文，并向change報(bào)文發(fā)送節(jié)點(diǎn)返回done報(bào)文；如iif_list為空，則轉(zhuǎn)發(fā)change報(bào)文。

圖7 節(jié)點(diǎn)7出現(xiàn)故障后，執(zhí)行本文恢復(fù)方案得到的多播樹(shù)

（4）轉(zhuǎn)發(fā)change報(bào)文的規(guī)則如下：如果中間節(jié)點(diǎn)接收的change報(bào)文的發(fā)送節(jié)點(diǎn)是該節(jié)點(diǎn)的左轉(zhuǎn)發(fā)節(jié)點(diǎn)（Blue樹(shù)路徑），則change報(bào)文轉(zhuǎn)發(fā)至該中間節(jié)點(diǎn)的右轉(zhuǎn)發(fā)節(jié)點(diǎn)（Red樹(shù)路徑）；其他情況則將change報(bào)文轉(zhuǎn)發(fā)至該中間節(jié)點(diǎn)的左轉(zhuǎn)發(fā)節(jié)點(diǎn)（Blue樹(shù)路徑）。

（5）如果中間節(jié)點(diǎn)的Blue樹(shù)和Red樹(shù)路徑對(duì)應(yīng)的轉(zhuǎn)發(fā)節(jié)點(diǎn)都不能成功發(fā)送change報(bào)文，則沿change報(bào)文接收的方向返回exit報(bào)文。

（6）中間節(jié)點(diǎn)接收到done報(bào)文后，沿著change報(bào)文接收的方向轉(zhuǎn)發(fā)done報(bào)文，一直轉(zhuǎn)發(fā)至初始change報(bào)文的發(fā)送節(jié)點(diǎn)，則保護(hù)樹(shù)構(gòu)造成功。

（7）中間節(jié)點(diǎn)接收到exit報(bào)文后，沿著change報(bào)文接收的方向轉(zhuǎn)發(fā)exit報(bào)文，一直轉(zhuǎn)發(fā)至初始change報(bào)文的發(fā)送節(jié)點(diǎn)，則保護(hù)樹(shù)構(gòu)造失敗。

（8）故障節(jié)點(diǎn)或鏈路的上游節(jié)點(diǎn)檢測(cè)到失敗發(fā)生時(shí)，刪除自身節(jié)點(diǎn)中對(duì)應(yīng)的oif_list中的下游節(jié)點(diǎn)項(xiàng)，檢查oif_list表項(xiàng)中是否還有其他下游節(jié)點(diǎn)，如還有下游節(jié)點(diǎn)項(xiàng)存在，則不再做其他動(dòng)作；如oif_list變?yōu)榭?，則該節(jié)點(diǎn)發(fā)送prune報(bào)文至iif_list中節(jié)點(diǎn)，之后刪除iif_list中的節(jié)點(diǎn)項(xiàng)。

圖8 節(jié)點(diǎn)5出現(xiàn)故障后，執(zhí)行本文恢復(fù)方案得到的多播樹(shù)

（9）中間節(jié)點(diǎn)接收到prune報(bào)文，刪除oif_list中對(duì)應(yīng)的prune報(bào)文的發(fā)送節(jié)點(diǎn)，接著檢查oif_list中是否還有節(jié)點(diǎn)表項(xiàng)存在，如果有，則不再轉(zhuǎn)發(fā)prune報(bào)文；如oif_list已經(jīng)為空，則向iif_list中節(jié)點(diǎn)轉(zhuǎn)發(fā)prune報(bào)文，之后刪除iif_list中的節(jié)點(diǎn)項(xiàng)。

對(duì)于圖5中的多播通信樹(shù)，假如節(jié)點(diǎn)7發(fā)生故障，多播成員8、9、12與多播源的通信將中斷。根據(jù)本文所提出的故障恢復(fù)方法在故障節(jié)點(diǎn)的下游節(jié)點(diǎn)8、10、11檢測(cè)到故障后，執(zhí)行本文所述恢復(fù)方法，將多播成員繞過(guò)故障節(jié)點(diǎn)重新連接到多播樹(shù)。同時(shí)根據(jù)本文所提出的方案中，為了避免無(wú)用的多播數(shù)據(jù)流的發(fā)送，節(jié)點(diǎn)5發(fā)送prune剪枝報(bào)文將自己從多播通信樹(shù)中剔除。通過(guò)本文方案的執(zhí)行，得到如圖7所示的新的多播通信樹(shù)。圖8為節(jié)點(diǎn)5到節(jié)點(diǎn)7的單鏈路失敗后，通過(guò)本文恢復(fù)方案得到的新的多播樹(shù)，圖中節(jié)點(diǎn)7檢測(cè)到多播樹(shù)上游鏈路發(fā)生故障，通過(guò)Red樹(shù)繞過(guò)故障鏈路，同時(shí)節(jié)點(diǎn)5檢測(cè)鏈路故障并檢測(cè)到下游已無(wú)多播接收成員，則向上游節(jié)點(diǎn)發(fā)送prune報(bào)文，刪除多播樹(shù)中多余的分枝。

4 仿真與性能分析

本文的性能仿真均是在Matlab上實(shí)現(xiàn)，仿真中使用的網(wǎng)絡(luò)拓?fù)浣梃bSalama博士的隨機(jī)網(wǎng)絡(luò)拓?fù)渌惴╗9,10]生成，網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布的正方形區(qū)域大小設(shè)定為2 000 km×2 000 km,根據(jù)概率來(lái)確定和之間是否存在鏈路，其中d(u,v)是u和v之間的歐氏距離，L是任意兩點(diǎn)間的最大距離。α和β是常數(shù)，較小的α將增大鏈路的密度，較大的β將導(dǎo)致較高的鏈路密度。通過(guò)調(diào)整α、β使產(chǎn)生的網(wǎng)絡(luò)拓?fù)錆M(mǎn)足2連接的要求，即拓?fù)渲许旤c(diǎn)之間必須至少有兩個(gè)經(jīng)過(guò)不同節(jié)點(diǎn)的路徑，本文仿真中取α=0.15，β=2.2。

本節(jié)對(duì)方法的性能進(jìn)行兩方面的仿真分析：首先是生成的多播樹(shù)所經(jīng)過(guò)的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，多播樹(shù)中網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較少表明多播通信所需成本相對(duì)較低；另外需要關(guān)注的是多播通信保護(hù)中，故障恢復(fù)后多播樹(shù)的代價(jià)，代價(jià)的增加量反映了多播故障恢復(fù)的質(zhì)量。仿真中，每條鏈路的代價(jià)被配置為1，這樣多播樹(shù)的代價(jià)就是樹(shù)中鏈路的總個(gè)數(shù)。

仿真實(shí)驗(yàn)中，隨機(jī)選擇一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)作為多播源節(jié)點(diǎn)，并隨機(jī)選擇多個(gè)節(jié)點(diǎn)作為多播組成員，通過(guò)運(yùn)行本文所提出的算法生成一棵多播樹(shù)，記錄多播樹(shù)所經(jīng)過(guò)的節(jié)點(diǎn)數(shù)。除了對(duì)本文方法仿真外，對(duì)參考文獻(xiàn)[11]中所提出的多播冗余樹(shù)方法也進(jìn)行了對(duì)比仿真。在故障恢復(fù)仿真中，隨機(jī)選擇多播樹(shù)中一個(gè)單節(jié)點(diǎn)作為故障節(jié)點(diǎn)，記錄多播故障前與故障恢復(fù)后多播樹(shù)的代價(jià)。本文做了100次重復(fù)實(shí)驗(yàn)，取所記錄的平均值作對(duì)比分析。

圖9 隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為100個(gè)時(shí)，不同多播規(guī)模下的多播樹(shù)包含節(jié)點(diǎn)數(shù)

圖10 隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為200個(gè)時(shí)，不同多播規(guī)模下的多播樹(shù)包含節(jié)點(diǎn)數(shù)

圖9顯示隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為100時(shí)，本文方案和參考文獻(xiàn)[11]所提出的多播冗余樹(shù)方案在不同多播規(guī)模下，多播樹(shù)中所包含的節(jié)點(diǎn)數(shù)；圖10顯示隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為200時(shí)的仿真對(duì)比。從圖9、圖10中可以看出本文的多播樹(shù)方案生成的多播樹(shù)所包含的節(jié)點(diǎn)數(shù)明顯少于參考文獻(xiàn)[11]中的冗余樹(shù)方案；另外從圖中還可以看出，在多播規(guī)模較小時(shí)，冗余樹(shù)方案所生成的多播樹(shù)仍包含較多的節(jié)點(diǎn)數(shù)，原因在于參考文獻(xiàn) [11]中的冗余樹(shù)方案采用路徑擴(kuò)大（path augmentation）方法，使得較多的冗余節(jié)點(diǎn)也被加入多播樹(shù)，而本文的方法則通過(guò)SimCT算法得到的顏色樹(shù)組建多播樹(shù)，在多播規(guī)模較小時(shí)，生成的多播樹(shù)中節(jié)點(diǎn)數(shù)也相對(duì)較少，減少了過(guò)多的資源浪費(fèi)。

圖11和圖12顯示隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)分別為100和200時(shí)，本文方案中多播單節(jié)點(diǎn)故障前與單節(jié)點(diǎn)故障恢復(fù)后多播樹(shù)的代價(jià)。從圖中可以看出，采用本文中單節(jié)點(diǎn)故障恢復(fù)方案，故障前與恢復(fù)后多播樹(shù)的代價(jià)成本基本一致，即有效克服了在多數(shù)方案[1～3]中所產(chǎn)生的多播保護(hù)樹(shù)相對(duì)通信多播樹(shù)長(zhǎng)度過(guò)長(zhǎng)的問(wèn)題。

圖11 隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為100個(gè)時(shí)，單節(jié)點(diǎn)故障前與故障恢復(fù)后的多播樹(shù)代價(jià)

圖12 隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為200個(gè)時(shí)，單節(jié)點(diǎn)故障前與故障恢復(fù)后的多播樹(shù)代價(jià)

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

本文在分析和研究SimCT算法的基礎(chǔ)上，提出了一種基于顏色樹(shù)的多播樹(shù)生成方法，并提出了一種多播單節(jié)點(diǎn)故障時(shí)的多播通信的恢復(fù)方案。仿真實(shí)驗(yàn)表明，本文所提出的多播樹(shù)生成方案相比現(xiàn)有方案可以減少網(wǎng)絡(luò)資源的浪費(fèi)，并且故障恢復(fù)后的代價(jià)與原多播通信樹(shù)相當(dāng)。本文方案中的故障恢復(fù)，主要對(duì)單節(jié)點(diǎn)/鏈路進(jìn)行保護(hù)，下一步將繼續(xù)研究和分析在多個(gè)節(jié)點(diǎn)/鏈路失敗情況下的故障恢復(fù)方法。

1 Hiltunen M，Schlichting R,Ugarte C.Building survivable servicesusingredundancy and adaptation.IEEE Transon Cormputers,2003,52（2）:181～194

2 Wu Jian,Shin K G.SMRP:fast restoration of multicast sessions from persistent failures.In:Proc of the 2005 International Conference on Dependable Systems and Networks （DSN’05）,Yokohama,Japan,2005

3 Feather M S.A risk-centric decision process.In:Proc of Software Engineering for High Assurance Systems （SEHAS） ,Portland,Oregon,USA,2003

4 Ramesh B.Survivable Networks:Algorithms for Diverse Routing.Norwell:Kluwer Academic Publishers,1999

5 Wayne D G.Mesh-Based Survivable Networks:Options and Strategies for Optical,MPLS,SONET and ATM Networking.New Jersey:Prentice Hall Publishers,2003

6 RamasubramanianS,Krishnamoorthy H,KrunzM.Disjoint multipath routing using colored trees.Computer Networks:The InternationalJournalofComputer and Telecommunications Networking,2007,51（8）

7 Ramasubramanian S,Harkara M,KrunzM.Lineartime distributed construction of colored trees for disjoint multipath routing.Computer Networks:The International Journal of Computer and Telecommunications Networking,2007,51（10）

8 Jayavelu G,Ramasubramanian S,Younis O.Maintaining colored trees for disjoint multipath routing under node failures.IEEE/ACM Transactions on Networking,2009,17（1）:346～359

9 Salama H F.Multicast routing for real-time communication of high-speed networks.Raleigh:Department of Electricaland Computer Engineering North Carolina State University,1996

10 Junhai Luo,Danxia Ye,Xue Liu,et al.A survey of multicast routing protocols for mobile ad hoc networks. IEEE Communications Surveys and Tutorials,2009,11（1）

11 Shang Wang,Chun He,Yide Zhang,et al.Construction of multicast protection tree based on single node failure.In:2010 International Conference on Communications and Mobile Computing （cmc’10）,Shenzhen,China,2010