基于相交多路徑的組播主動式恢復方案*

王肖楠，程東年，張建輝

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

網(wǎng)絡的一個重要問題是可生存性(survivability)?？缮嫘允侵赶到y(tǒng)在攻擊、故障、意外事件影響下能夠及時完成任務的能力。網(wǎng)絡的可生存性又稱為網(wǎng)絡快速恢復能力，用于描述一個網(wǎng)絡在應對節(jié)點或鏈路失效時的性能。有兩類方法可以提供網(wǎng)絡的快速恢復能力。一種方法稱為被動式(reactive)恢復，又稱為按需(on-demand)恢復，當網(wǎng)絡中檢測到故障時，繞過故障的鏈路/節(jié)點，重新尋找新的路由來完成服務的恢復[1]。該方案的主要缺點是恢復延遲漫長，不利于很多即時通信。另一種方法是主動式(preactive)恢復，它預先計算兩條不相交的路徑，一條被指定為主路徑,另一條是備用路徑[1]。當主路徑因其中的鏈路或節(jié)點故障而失效時，備份路徑被激活，自動成為新的主路徑。對比于被動式恢復方法，該方法能夠減少恢復時間，但在很多情況下，它需要執(zhí)行復雜的恢復操作和花費較多的網(wǎng)絡資源。

組播是一種一對多的傳輸方式，需要將數(shù)據(jù)同時從源發(fā)送到一組目的主機。設計組播通信的快速恢復方案更富有挑戰(zhàn)性，因為一個鏈路/節(jié)點的失效將會影響到很多組播目的主機。許多文獻都提出了針對單一節(jié)點/鏈路失效提供保護的組播主動式恢復方案，這些方案要求計算從數(shù)據(jù)源到目的地的不相交的多條路徑。目前廣泛受到關注的兩種保護方案是：局部保護方案和組播組保護方案。兩者的保護范圍不同，前者是按照單播主動式故障恢復方案將多播樹中源節(jié)點列目的節(jié)點的路徑抽取出來，并分別為它們建立保護路徑；后者則是通過計算兩個鏈路不相交組播樹，其中一個作為主要的組播樹，而另一個作為備份組播樹，以整個組播樹為保護對象。

以上兩種方案均存在不足：局部保護方案需要較高的維護與管理代價，而且可能出現(xiàn)路由環(huán)路；組播組保護方案近年來研究得比較多，然而,找到兩個鏈路/節(jié)點不相交的兩棵組播樹在大型組播通信中是很困難的，甚至是不可能實現(xiàn)的。

針對現(xiàn)有方案中不相交的多路徑構(gòu)建成功率低下的不足，本文提出一種基于相交多路徑的組播主動式恢復方案。該方案通過為組播樹中的節(jié)點備份父節(jié)點的方式，使得各個組播組成員通過多條相交路徑連接到組播源。當發(fā)生故障時，路由可以快速地切換到未受故障影響的父節(jié)點，進而完成組播路由的快速恢復。

1 背景和相關工作

雖然目前對組播通信的故障恢復的文獻中很少提及，但其必將成為未來通信網(wǎng)絡的一個重要部分。在常規(guī)的組播中，數(shù)據(jù)流分布在整個樹結(jié)構(gòu)上，一個故障就會影響到故障點下游的所有組成員。目前組播主動式恢復方案的研究中，有些借鑒單播中鏈路恢復和路徑恢復的方案，應用于保護組播樹中的源到每個目的地的路徑[2,3],有些利用冗余樹[4]或者雙樹[1]方案。圖1給出四種主要的組播主動式恢復方案的實例。圖中，S是源節(jié)點，實心的節(jié)點是組播組成員。粗實線代表缺省樹中的鏈路，虛線代表在備用路徑的鏈路。不同類型的箭頭表示數(shù)據(jù)流在缺省樹或激活后的備用路徑中的傳輸方向。

WU C等[2,3]研究了鏈路保護和路徑保護方案。在鏈路保護中，每條鏈路的兩個端節(jié)點之間設置了一個備用路由。在路徑保護中，為每個目的地計算一條備用路由，該路徑與組播樹中從數(shù)據(jù)源到目的地的路徑是節(jié)點不相交的。

圖1(c)給出了一個簡單的“冗余樹”(redundant tree)方案[4]的例子?！叭哂鄻洹狈桨敢缶W(wǎng)絡拓撲結(jié)構(gòu)是一種雙連通圖，即任何兩個節(jié)點之間至少有兩條節(jié)點不相交或者鏈路不相交的路徑。如果缺省樹和備用樹只是鏈路不相交，則它是一棵鏈路不相交的備用樹；否則，稱其為節(jié)點不相交備用樹?！叭哂鄻洹狈桨柑岢龅乃惴梢杂嬎銉煽貌幌嘟坏慕M播樹，使得消除網(wǎng)絡中任何節(jié)點 (鏈路)，目的節(jié)點都可通過至少一棵樹連接源點。因此，冗余樹方案可以恢復缺省樹中出現(xiàn)的任何鏈路或節(jié)點的故障，并可恢復不止一個故障。

在更近的研究中,FEI A等人提出 “雙樹”(“dual tree”)方案[1]。第二棵樹是為有容錯需求的組成員建立的備用樹，而不是為了單獨保護組播樹中每一個鏈路或組成員。圖1(d)就是一個節(jié)點不相交備用樹的示意圖。

2 基于相交多路徑的組播主動式恢復方案

2.1 方案的動機

上文描述了現(xiàn)有的組播主動式恢復方案，在管理開銷和網(wǎng)絡連通性要求方面對它們進行深入的比較，如表1所示。

表1 現(xiàn)有組播主動式恢復方案對比

對每條鏈路/路徑單獨進行保護的局部保護方法會增加管理開銷。換句話說，它們在每個組播組中單獨計算和維護每一條鏈路、路徑的備份路由。當檢測到網(wǎng)絡故障時，備份路由也需要單獨的鏈路/路徑的維護和激活，包括備份路由的計算成本和恢復開銷(由備份路由激活時的信息交流引起的)。因此，當網(wǎng)絡中有大量的組播組時，維護和激活成本變得很高。

以組播組為單位進行保護的方案在管理開銷上少于局部保護方法，但卻對網(wǎng)絡連通性有特殊要求?，F(xiàn)實的網(wǎng)絡并不能保證為雙連通網(wǎng)絡，因此，不相關雙樹的構(gòu)建存在失敗的可能性。本研究在節(jié)點個數(shù)為100、平均節(jié)點度為4～5的隨機網(wǎng)絡拓撲 （隨機拓撲的產(chǎn)生見第3節(jié)）的仿真中，針對不同的組播規(guī)模，分別對構(gòu)建鏈路不相關和節(jié)點不相關的兩棵組播樹進行了100次試驗。從仿真結(jié)果（如圖2所示）可以看出，構(gòu)建兩棵不相關的組播樹的成功率極為低下：組成員數(shù)目為5時，鏈路不相關雙樹的平均構(gòu)建成功率僅為53%，隨著組成員數(shù)目的增加，平均構(gòu)建成功率逐漸下降，當組成員數(shù)目為30時已降為7%；節(jié)點不相關雙樹的情況更為嚴峻，平均構(gòu)建成功率均低于鏈路不相關雙樹，組成員數(shù)目為30時，節(jié)點不相關雙樹幾乎無法構(gòu)建成功。雖然成功構(gòu)建不相關雙樹可以為組播組提供100%的保護，然而，一旦構(gòu)建失敗，依靠不相關雙樹的快速自愈方案的保護能力瞬間下降為0%。

現(xiàn)代網(wǎng)絡可以不再將保護方式限制于兩個極端的情況：0%保護或100%保護。事實上，應通過某些共享的鏈路建立從數(shù)據(jù)源到目的地的多條路徑來提供保護[5]。如果在這些路徑中的不相交鏈路中有一個鏈路故障，則方案為組播通信提供了保護；如果由于網(wǎng)絡拓撲的極端情況而無法找出不相交路徑，方案就不能為其中共享鏈路的故障提供保護。因此，基于相交多路徑的組播路由可以有效地適應網(wǎng)絡拓撲，為組播通信提供最大限度的保護。

2.2 方案的描述

針對不相關雙樹構(gòu)建成功率低下的問題，本文提出一種基于相交多路徑的組播主動式恢復方案。該方案在同一時刻為組播樹中每個節(jié)點盡可能提供兩個父節(jié)點（連接不同的鄰居節(jié)點并且使用不同的物理連接）用于接受組播數(shù)據(jù)。通過這種方式，各個目的地通過多條相交路徑連接到組播源，降低了網(wǎng)絡連通性的要求。另外，節(jié)點可以在路由故障時本地處理，非?？焖俚貙?shù)據(jù)流切換到仍然可用的父節(jié)點進行接收。這種本地的處理比任何需要多種原理和多種信息交換的分布式處理要快速許多。

圖3為基于相交路徑的組播路由的一個例子。假設H1是組播通信的數(shù)據(jù)源；H2和H3是兩個目的主機。圖中粗線表示本方案建立的相交多路徑。由于網(wǎng)絡拓撲的限制，有的目的主機(如 H2)可以得到100%保護，有的主機(如H3)只能得到部分保護?？梢钥闯?，相交多路徑保證了構(gòu)建成功率并為組播路由提供一定程度的保護。

本方案包括相交多路徑構(gòu)建算法與恢復消息處理算法兩部分。組播通信中所用的組播樹和備份路徑的計算采用本方案中的相交多路徑構(gòu)建算法；當組播樹中的路由發(fā)生故障時,備用路徑的激活采用恢復處理算法。

2.2.1 相交多路徑構(gòu)建算法

相交多路徑構(gòu)建算法為樹中節(jié)點提供兩個父節(jié)點，其中一個作為缺省父節(jié)點，另一個作為備用父節(jié)點。通過這種方式構(gòu)建組播源到各個組成員的多條相交路徑。對于每個組播組(Si，Gi)，其中，Si為組播源，Gi為組播組成員集合，相交多路徑構(gòu)建算法由節(jié)點Si采用集中式計算，偽代碼描述如下：

算法1相交多路徑構(gòu)建算法

(1)initialize

{初始化集合 Ni(Si)，記錄所有與 Si直連的節(jié)點；初始化鏈路集合 R(Si)、節(jié)點集合 L(Si)并置為空；}

(2)for網(wǎng)絡中不在Ni(Si)中的每個節(jié)點Ai(除去組播源Si)

{檢查Ai是否和 Ni(Si)中兩個或兩個以上的節(jié)點直連；}

(3)if yes

{隨機選擇其中一個節(jié)點作為 Ai的缺省父節(jié)點，另選擇一個節(jié)點作為Ai的備用父節(jié)點,將鏈路加入到R(Si)，并將節(jié)點加入到 L(Si)；}

(4)else

{檢查Ai是否屬于 Gi;}

(5)if yes

{將 Ni(Si)中與 Ai直連的節(jié)點作為 Ai的父節(jié)點，將鏈路加入到 R(Si)，并將節(jié)點加入到 L(Si)；}

end if

end if

(6)repeat step2

{重復 step2，直到 Gi中所有節(jié)點都在 L(Si)中；}

(7)delete useless node

{檢查Ni(Si)中節(jié)點是否存在無下游節(jié)點且本身不屬于 Gi的節(jié)點;}

(8)if yes

{將節(jié)點從Ni(Si)中移出，并將與之相連的鏈路從 R(Si)中移出;}

end if

2.2.2 恢復消息處理算法

當組播樹中的路由發(fā)生故障時，恢復消息處理算法由檢測到故障的子節(jié)點發(fā)起，創(chuàng)建恢復消息激活備用父節(jié)點。收到恢復消息的節(jié)點依次激活備用父節(jié)點，直到再次連接到組播樹中。偽代碼描述如下：

算法2恢復消息處理算法

(1)if檢測到與父節(jié)點的通信故障

{切換備用父節(jié)點為新的缺省父節(jié)點，并向備用父節(jié)點發(fā)送恢復消息Restore_message((Si,Gi),address)，其中address為本節(jié)點地址}

end if

(2)if收到Restore_message((Si,Gi),address)

{檢查本節(jié)點是否處于(Si,Gi)的組播樹中；}

(3)if yes

{將address加入到本節(jié)點的子節(jié)點集合中，不再向備用父節(jié)點發(fā)送恢復消息；}

(4)else

{將address加入到本節(jié)點的子節(jié)點集合中，將備用父節(jié)點設置為缺省父節(jié)點，并向備用父節(jié)點發(fā)送恢復消息 Restore_message((Si,Gi),address),此處 address設置為本節(jié)點地址；}

end if

end if

算法可以處理節(jié)點故障：節(jié)點的故障可以表示為與之直連的鏈路全部發(fā)生故障的情形，受到影響的子節(jié)點不需要判斷故障類型，而只需要通過備用的父節(jié)點激活備用路徑，恢復后的路由自然繞過了故障的節(jié)點。

3 仿真與性能分析

本文致力于組播路由快速恢復方案的研究，關注方案下述幾個方面的性能：首先是快速，從檢測到故障到備份路徑被激活的時間稱作故障恢復時間[2]。很顯然，恢復時間越短就意味著通信更少的中斷。其次需要關注的是組播樹的代價，包括缺省樹的代價和恢復后組播樹的代價兩個部分。缺省樹的代價反映組播傳輸?shù)男阅埽瑳Q定本方案是否可行；恢復后的組播樹一般比原來組播樹有一定代價的增加，代價的增加反映了恢復的質(zhì)量。因此，以平均恢復時間、缺省組播樹的代價、恢復后組播樹的代價這三個重要度量作為評估標準，將本方案與現(xiàn)有的方案進行仿真對比。

現(xiàn)有的組播主動式恢復方案與本文提出的相交多路徑方案均是基于路徑備份的思想。在本方案中，備用路徑通過節(jié)點維護備用父節(jié)點的方式構(gòu)建，當檢測到故障時，恢復消息一次激活各個備用父節(jié)點進而激活整個路徑，恢復的時間涉及到每個節(jié)點的消息處理和父節(jié)點配置。正因如此，在仿真中，用恢復信息激活備用路徑時通過的節(jié)點數(shù)量來衡量恢復時間。仿真中，每條鏈路的代價被配置為1，這樣組播樹的代價就是樹中鏈路的總個數(shù)。

本方案使用參考文獻[6]的方法產(chǎn)生隨機網(wǎng)絡。首先在30×30的網(wǎng)格中隨機選擇 100個網(wǎng)絡節(jié)點；然后根據(jù)概率 p(u,v)=λexp(-d(u,v)/ρL)選擇兩個節(jié)點 u和 v之間是否直連；其中，d(u,v)是 u和v的幾何距離，·g是任意兩個節(jié)點之間的最大距離，λ和ρ是常數(shù)（0<λ，ρ<1）。在隨機網(wǎng)絡中，選定 λ=1.5 和 ρ=0.3，平均節(jié)點度在4和5之間。

[1]已對鏈路/路徑保護方案和“雙樹”方案在故障恢復時間和故障恢復后組播樹的代價增加兩方面進行了性能比較。在隨機網(wǎng)絡中的仿真結(jié)果表明“雙樹”方案優(yōu)于鏈路/路徑保護方案。因此，在本文中，除了相交多路徑方案以外，還對在第1節(jié)介紹的另外2種方案進行了仿真：“冗余樹”方案和“雙樹”方案。在仿真實驗中，隨機生成一個組播組，它由隨機選擇的一個組播源節(jié)點和多個組播組成員節(jié)點構(gòu)成。三種方案各自計算缺省組播樹和備用路徑，記錄缺省樹的代價。另外，隨機選擇組播樹中的一個鏈路作為故障鏈路，應用三種方案的恢復過程?；謴屯瓿珊?，記錄恢復時間和恢復后組播樹的代價。筆者進行了100次重復實驗，將所關注的3個度量取平均值進行比較。

圖4顯示出網(wǎng)絡中不同組播規(guī)模下的平均恢復時間。其中，“冗余樹”方案的平均恢復時間最長，它反映了端到端的路徑備份會顯著延長激活備份路徑的過程，因為故障點首先要通知所有故障點下的目的節(jié)點，然后才進行重新連接。本方案平均恢復時間稍短于“雙樹”方案，原因是本方案在出現(xiàn)故障時進行本地處理，直接發(fā)起備用路徑的激活過程，而“雙樹”方案要對故障點以下的部分中間路由器和組播組目的節(jié)點進行操作。從需要操作的節(jié)點的數(shù)量來說，本方案遠小于其他兩種方案，因此，恢復操作所需的時間也就非常小。另外，從圖4中可以看出，本方案和“雙樹”方案的平均恢復時間會隨著組播規(guī)模的增加而降低，但是“冗余樹”方案則不會。原因是更密集的組播組會幫助前兩者發(fā)現(xiàn)備用路徑，而不會幫助“冗余樹”方案。

圖5顯示了缺省組播樹代價的對比。“冗余樹”方案和“雙樹”方案的缺省樹均是最短路徑樹，因此本方案的缺省樹代價略高于前兩者。圖6顯示了恢復后組播樹代價的對比。在單故障的情況下，三種方案恢復后的組播樹都未產(chǎn)生較大的代價增加。綜合考慮上述三個度量標準，可以看出，本方案優(yōu)于“冗余樹”方案和“雙樹”方案。

在本文中，探討了組播路由快速恢復的問題，討論了現(xiàn)有的幾種組播主動式恢復方案并分析了它們的優(yōu)缺點?，F(xiàn)有的方案大都基于不相交多路徑來建立備用路由，然而不相交多路徑卻存在構(gòu)建成功率低的問題，一旦網(wǎng)絡拓撲無法滿足不相交多路徑的構(gòu)建，則整個方案無法對組播通信提供保護。本文提出了自己的組播路由方案，即基于相交多路徑的組播主動式恢復方案。在此方案中，組播樹中的節(jié)點維護主備兩個父節(jié)點，使得各個目的地通過多條相交路徑連接到組播源。另外，節(jié)點在路由故障時本地處理，快速地將數(shù)據(jù)流切換到仍然可用的備用父節(jié)點。仿真結(jié)果表明，該方案構(gòu)建的組播樹以及故障恢復后的組播樹代價均與現(xiàn)有方案相當，但是可以提供更短的恢復時間。

參考文獻

[1]FEI A,CUI J,GERLA M,et al.A dual-tree scheme for fault-tolerant multicast[C].IEEE ICC 2001,2001,3(6):690-694.

[2]WU C,LEE W,CHU W.A new preplanned self-healing scheme for mu lticast ATM network[C].IEEE ICCT′96,1996,2(5):888-891.

[3]WU C,LEE W,HOU Y.Back-up VP preplanning strategies for survivable multicast ATM networks[C].IEEE ICC′97,1997,1(6):267-271.

[4]MEDARD M,FINN S,BARRY R,et al.Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs[J].IEEE/ACM Transactions on Networking,Oct.1999,7(5):641-652.

[5]WANG Jian Ping,YANG Mei,YANG Bin,et al.Dualhoming based scalable partial multicast protection[J].IEEE Trans.Computers,Sep.2006,55(9):1130-1140.

[6]WAXMAN B M.Routing of multipoint connections[J].IEEE J.Select.Areas Commun,1988,6(9):1617-1622.