基于SimCT 的多播路由及故障恢復(fù)研究*

孫 偉 ，羅俊海 ，肖志輝

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

1 引言

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

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

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

2 SimCT算法

SimCT算法分為3個步驟：

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

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

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

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

如果從節(jié)點s到節(jié)點d的Red路徑穿過節(jié)點i，那么從節(jié)點s到節(jié)點d的Blue路徑則不會穿過節(jié)點i，如，坌s∈Nj5i0abt0b和坌i∈N{s,d}，則：

算法中所使用的符號如表1所示。

2.1 分發(fā)DFS序號

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

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

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

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

表1 SimCT算法中所使用的符號

圖1 分發(fā)DFS序號和計算glpv值的算法

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

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

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

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

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

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

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

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

3 基于SimCT的多播樹的組建

3.1 多播樹的組建

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

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

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

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

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

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

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

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

多播樹組建的具體報文交互過程如下。

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

圖4 節(jié)點加入多播樹算法

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

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

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

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

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

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

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

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

圖5 成功組建的多播通信樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真與性能分析

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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