網(wǎng)絡(luò)的一個重要問題是可生存性(survivability)?？缮嫘允侵赶到y(tǒng)在攻擊、故障、意外事件影響下能夠及時完成任務(wù)的能力。網(wǎng)絡(luò)的可生存性又稱為網(wǎng)絡(luò)快速恢復(fù)能力，用于描述一個網(wǎng)絡(luò)在應(yīng)對節(jié)點或鏈路失效時的性能。有兩類方法可以提供網(wǎng)絡(luò)的快速恢復(fù)能力。一種方法稱為被動式(reactive)恢復(fù)，又稱為按需(on-demand)恢復(fù)，當(dāng)網(wǎng)絡(luò)中檢測到故障時，繞過故障的鏈路/節(jié)點，重新尋找新的路由來完成服務(wù)的恢復(fù)[1]。該方案的主要缺點是恢復(fù)延遲漫長，不利于很多即時通信。另一種方法是主動式(preactive)恢復(fù)，它預(yù)先計算兩條不相交的路徑，一條被指定為主路徑,另一條是備用路徑[1]。當(dāng)主路徑因其中的鏈路或節(jié)點故障而失效時，備份路徑被激活，自動成為新的主路徑。對比于被動式恢復(fù)方法，該方法能夠減少恢復(fù)時間，但在很多情況下，它需要執(zhí)行復(fù)雜的恢復(fù)操作和花費較多的網(wǎng)絡(luò)資源。
　組播是一種一對多的傳輸方式，需要將數(shù)據(jù)同時從源發(fā)送到一組目的主機。設(shè)計組播通信的快速恢復(fù)方案更富有挑戰(zhàn)性，因為一個鏈路/節(jié)點的失效將會影響到很多組播目的主機。許多文獻都提出了針對單一節(jié)點/鏈路失效提供保護的組播主動式恢復(fù)方案，這些方案要求計算從數(shù)據(jù)源到目的地的不相交的多條路徑。目前廣泛受到關(guān)注的兩種保護方案是：局部保護方案和組播組保護方案。兩者的保護范圍不同，前者是按照單播主動式故障恢復(fù)方案將多播樹中源節(jié)點列目的節(jié)點的路徑抽取出來，并分別為它們建立保護路徑；后者則是通過計算兩個鏈路不相交組播樹，其中一個作為主要的組播樹，而另一個作為備份組播樹，以整個組播樹為保護對象。
　以上兩種方案均存在不足：局部保護方案需要較高的維護與管理代價，而且可能出現(xiàn)路由環(huán)路；組播組保護方案近年來研究得比較多，然而, 找到兩個鏈路/節(jié)點不相交的兩棵組播樹在大型組播通信中是很困難的，甚至是不可能實現(xiàn)的。
　針對現(xiàn)有方案中不相交的多路徑構(gòu)建成功率低下的不足，本文提出一種基于相交多路徑的組播主動式恢復(fù)方案。該方案通過為組播樹中的節(jié)點備份父節(jié)點的方式，使得各個組播組成員通過多條相交路徑連接到組播源。當(dāng)發(fā)生故障時，路由可以快速地切換到未受故障影響的父節(jié)點，進而完成組播路由的快速恢復(fù)。
1 背景和相關(guān)工作
　雖然目前對組播通信的故障恢復(fù)的文獻中很少提及，但其必將成為未來通信網(wǎng)絡(luò)的一個重要部分。在常規(guī)的組播中，數(shù)據(jù)流分布在整個樹結(jié)構(gòu)上，一個故障就會影響到故障點下游的所有組成員。目前組播主動式恢復(fù)方案的研究中，有些借鑒單播中鏈路恢復(fù)和路徑恢復(fù)的方案，應(yīng)用于保護組播樹中的源到每個目的地的路徑[2,3],有些利用冗余樹[4]或者雙樹[1]方案。圖1給出四種主要的組播主動式恢復(fù)方案的實例。圖中，S是源節(jié)點，實心的節(jié)點是組播組成員。粗實線代表缺省樹中的鏈路，虛線代表在備用路徑的鏈路。不同類型的箭頭表示數(shù)據(jù)流在缺省樹或激活后的備用路徑中的傳輸方向。
　WU C等[2,3]研究了鏈路保護和路徑保護方案。在鏈路保護中，每條鏈路的兩個端節(jié)點之間設(shè)置了一個備用路由。在路徑保護中，為每個目的地計算一條備用路由，該路徑與組播樹中從數(shù)據(jù)源到目的地的路徑是節(jié)點不相交的。
　圖1(c)給出了一個簡單的“冗余樹”(redundant tree)方案[4]的例子。“冗余樹”方案要求網(wǎng)絡(luò)拓撲結(jié)構(gòu)是一種雙連通圖，即任何兩個節(jié)點之間至少有兩條節(jié)點不相交或者鏈路不相交的路徑。如果缺省樹和備用樹只是鏈路不相交，則它是一棵鏈路不相交的備用樹；否則，稱其為節(jié)點不相交備用樹。“冗余樹”方案提出的算法可以計算兩棵不相交的組播樹，使得消除網(wǎng)絡(luò)中任何節(jié)點(鏈路)，目的節(jié)點都可通過至少一棵樹連接源點。因此，冗余樹方案可以恢復(fù)缺省樹中出現(xiàn)的任何鏈路或節(jié)點的故障，并可恢復(fù)不止一個故障。

   在更近的研究中, FEI A等人提出“雙樹”(“dual tree”)方案[1]。第二棵樹是為有容錯需求的組成員建立的備用樹，而不是為了單獨保護組播樹中每一個鏈路或組成員。圖1(d)就是一個節(jié)點不相交備用樹的示意圖。
2 基于相交多路徑的組播主動式恢復(fù)方案
2.1 方案的動機
　上文描述了現(xiàn)有的組播主動式恢復(fù)方案，在管理開銷和網(wǎng)絡(luò)連通性要求方面對它們進行深入的比較，如表1所示。

　對每條鏈路/路徑單獨進行保護的局部保護方法會增加管理開銷。換句話說，它們在每個組播組中單獨計算和維護每一條鏈路、路徑的備份路由。當(dāng)檢測到網(wǎng)絡(luò)故障時，備份路由也需要單獨的鏈路/路徑的維護和激活，包括備份路由的計算成本和恢復(fù)開銷(由備份路由激活時的信息交流引起的)。因此，當(dāng)網(wǎng)絡(luò)中有大量的組播組時，維護和激活成本變得很高。
   以組播組為單位進行保護的方案在管理開銷上少于局部保護方法，但卻對網(wǎng)絡(luò)連通性有特殊要求?，F(xiàn)實的網(wǎng)絡(luò)并不能保證為雙連通網(wǎng)絡(luò)，因此，不相關(guān)雙樹的構(gòu)建存在失敗的可能性。本研究在節(jié)點個數(shù)為100、平均節(jié)點度為4~5的隨機網(wǎng)絡(luò)拓撲（隨機拓撲的產(chǎn)生見第3節(jié)）的仿真中，針對不同的組播規(guī)模，分別對構(gòu)建鏈路不相關(guān)和節(jié)點不相關(guān)的兩棵組播樹進行了100次試驗。從仿真結(jié)果（如圖2所示）可以看出，構(gòu)建兩棵不相關(guān)的組播樹的成功率極為低下：組成員數(shù)目為5時，鏈路不相關(guān)雙樹的平均構(gòu)建成功率僅為53%，隨著組成員數(shù)目的增加，平均構(gòu)建成功率逐漸下降，當(dāng)組成員數(shù)目為30時已降為7%；節(jié)點不相關(guān)雙樹的情況更為嚴(yán)峻，平均構(gòu)建成功率均低于鏈路不相關(guān)雙樹，組成員數(shù)目為30時，節(jié)點不相關(guān)雙樹幾乎無法構(gòu)建成功。雖然成功構(gòu)建不相關(guān)雙樹可以為組播組提供100%的保護，然而，一旦構(gòu)建失敗，依靠不相關(guān)雙樹的快速自愈方案的保護能力瞬間下降為0%。

　現(xiàn)代網(wǎng)絡(luò)可以不再將保護方式限制于兩個極端的情況：0%保護或100%保護。事實上，應(yīng)通過某些共享的鏈路建立從數(shù)據(jù)源到目的地的多條路徑來提供保護[5]。如果在這些路徑中的不相交鏈路中有一個鏈路故障，則方案為組播通信提供了保護；如果由于網(wǎng)絡(luò)拓撲的極端情況而無法找出不相交路徑，方案就不能為其中共享鏈路的故障提供保護。因此，基于相交多路徑的組播路由可以有效地適應(yīng)網(wǎng)絡(luò)拓撲，為組播通信提供最大限度的保護。
2.2 方案的描述
　針對不相關(guān)雙樹構(gòu)建成功率低下的問題，本文提出一種基于相交多路徑的組播主動式恢復(fù)方案。該方案在同一時刻為組播樹中每個節(jié)點盡可能提供兩個父節(jié)點（連接不同的鄰居節(jié)點并且使用不同的物理連接）用于接受組播數(shù)據(jù)。通過這種方式，各個目的地通過多條相交路徑連接到組播源，降低了網(wǎng)絡(luò)連通性的要求。另外，節(jié)點可以在路由故障時本地處理，非?？焖俚貙?shù)據(jù)流切換到仍然可用的父節(jié)點進行接收。這種本地的處理比任何需要多種原理和多種信息交換的分布式處理要快速許多。
   圖3為基于相交路徑的組播路由的一個例子。假設(shè)H1是組播通信的數(shù)據(jù)源； H2和H3是兩個目的主機。圖中粗線表示本方案建立的相交多路徑。由于網(wǎng)絡(luò)拓撲的限制，有的目的主機(如H2)可以得到100%保護，有的主機(如H3)只能得到部分保護?？梢钥闯?，相交多路徑保證了構(gòu)建成功率并為組播路由提供一定程度的保護。

　本方案包括相交多路徑構(gòu)建算法與恢復(fù)消息處理算法兩部分。組播通信中所用的組播樹和備份路徑的計算采用本方案中的相交多路徑構(gòu)建算法；當(dāng)組播樹中的路由發(fā)生故障時,備用路徑的激活采用恢復(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)絡(luò)中不在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
   {重復(fù)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ù)消息處理算法
　當(dāng)組播樹中的路由發(fā)生故障時，恢復(fù)消息處理算法由檢測到故障的子節(jié)點發(fā)起，創(chuàng)建恢復(fù)消息激活備用父節(jié)點。收到恢復(fù)消息的節(jié)點依次激活備用父節(jié)點，直到再次連接到組播樹中。偽代碼描述如下：
   算法2 恢復(fù)消息處理算法
   (1) if 檢測到與父節(jié)點的通信故障
   {切換備用父節(jié)點為新的缺省父節(jié)點，并向備用父節(jié)點發(fā)送恢復(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ā)送恢復(fù)消息；}
   (4) else
   {將address加入到本節(jié)點的子節(jié)點集合中，將備用父節(jié)點設(shè)置為缺省父節(jié)點，并向備用父節(jié)點發(fā)送恢復(fù)消息Restore_message((Si,Gi),address),此處address設(shè)置為本節(jié)點地址；}
   end if
   end if
   算法可以處理節(jié)點故障：節(jié)點的故障可以表示為與之直連的鏈路全部發(fā)生故障的情形，受到影響的子節(jié)點不需要判斷故障類型，而只需要通過備用的父節(jié)點激活備用路徑，恢復(fù)后的路由自然繞過了故障的節(jié)點。
3 仿真與性能分析
　本文致力于組播路由快速恢復(fù)方案的研究，關(guān)注方案下述幾個方面的性能：首先是快速，從檢測到故障到備份路徑被激活的時間稱作故障恢復(fù)時間[2]。很顯然，恢復(fù)時間越短就意味著通信更少的中斷。其次需要關(guān)注的是組播樹的代價，包括缺省樹的代價和恢復(fù)后組播樹的代價兩個部分。缺省樹的代價反映組播傳輸?shù)男阅?，決定本方案是否可行；恢復(fù)后的組播樹一般比原來組播樹有一定代價的增加，代價的增加反映了恢復(fù)的質(zhì)量。因此，以平均恢復(fù)時間、缺省組播樹的代價、恢復(fù)后組播樹的代價這三個重要度量作為評估標(biāo)準(zhǔn)，將本方案與現(xiàn)有的方案進行仿真對比。
　現(xiàn)有的組播主動式恢復(fù)方案與本文提出的相交多路徑方案均是基于路徑備份的思想。在本方案中，備用路徑通過節(jié)點維護備用父節(jié)點的方式構(gòu)建，當(dāng)檢測到故障時，恢復(fù)消息一次激活各個備用父節(jié)點進而激活整個路徑，恢復(fù)的時間涉及到每個節(jié)點的消息處理和父節(jié)點配置。正因如此，在仿真中，用恢復(fù)信息激活備用路徑時通過的節(jié)點數(shù)量來衡量恢復(fù)時間。仿真中，每條鏈路的代價被配置為1，這樣組播樹的代價就是樹中鏈路的總個數(shù)。

　參考文獻[1]已對鏈路/路徑保護方案和“雙樹”方案在故障恢復(fù)時間和故障恢復(fù)后組播樹的代價增加兩方面進行了性能比較。在隨機網(wǎng)絡(luò)中的仿真結(jié)果表明“雙樹”方案優(yōu)于鏈路/路徑保護方案。因此，在本文中，除了相交多路徑方案以外，還對在第1節(jié)介紹的另外2種方案進行了仿真：“冗余樹”方案和“雙樹”方案。在仿真實驗中，隨機生成一個組播組，它由隨機選擇的一個組播源節(jié)點和多個組播組成員節(jié)點構(gòu)成。三種方案各自計算缺省組播樹和備用路徑，記錄缺省樹的代價。另外，隨機選擇組播樹中的一個鏈路作為故障鏈路，應(yīng)用三種方案的恢復(fù)過程?；謴?fù)完成后，記錄恢復(fù)時間和恢復(fù)后組播樹的代價。筆者進行了100次重復(fù)實驗，將所關(guān)注的3個度量取平均值進行比較。
　圖4顯示出網(wǎng)絡(luò)中不同組播規(guī)模下的平均恢復(fù)時間。其中，“冗余樹”方案的平均恢復(fù)時間最長，它反映了端到端的路徑備份會顯著延長激活備份路徑的過程，因為故障點首先要通知所有故障點下的目的節(jié)點，然后才進行重新連接。本方案平均恢復(fù)時間稍短于“雙樹”方案，原因是本方案在出現(xiàn)故障時進行本地處理，直接發(fā)起備用路徑的激活過程，而“雙樹”方案要對故障點以下的部分中間路由器和組播組目的節(jié)點進行操作。從需要操作的節(jié)點的數(shù)量來說，本方案遠小于其他兩種方案，因此，恢復(fù)操作所需的時間也就非常小。另外，從圖4中可以看出，本方案和“雙樹”方案的平均恢復(fù)時間會隨著組播規(guī)模的增加而降低，但是“冗余樹”方案則不會。原因是更密集的組播組會幫助前兩者發(fā)現(xiàn)備用路徑，而不會幫助“冗余樹”方案。

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

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