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

孫 偉 ，羅俊海 ，肖志輝

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

1 引言

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

網絡中通過多路徑傳輸數據可以使網絡健壯性提高、負載均衡、擁塞減少和吞吐量提高。通常從一個源節點到一個目的節點可以有多條路徑，如果有足夠的網絡資源，這些路徑可共享同一鏈路或節點，為了提高傳輸的可靠性和避免共享鏈路或節點的失敗，這些路徑則應是節點或鏈路不相交的。

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

2 SimCT算法

SimCT算法分為3個步驟：

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

（2）網絡節點的邏輯分層；

（3）選擇左（Blue）轉發節點和右（Red）轉發節點。

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

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

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

2.1 分發DFS序號

算法的第一階段是為網絡中各節點分發DFS索引序號和計算節點的全局低點值，具體算法如圖1所示。

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

2.2 網絡節點的邏輯分層

算法的第二個階段是為網絡節點進行邏輯分層，為了限制每一層節點的全局低點值glpv（x），此處定義一個勢值（potential）術語——即同一層節點的glpv的邊界值。節點x的勢值表示為pot（x），根據glpv（x）和pot（x）的關系為節點分層（odd層和even層）。

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

圖1 分發DFS序號和計算glpv值的算法

勢值計算規則如下：

p（x）為節點x的DFS搜索路徑的父節點。分層規則如下：

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

2.3 選擇轉發節點

算法的第3個階段是為每個節點選擇到根節點的左轉發節點（Blue）和右轉發節點（Red）。

如果節點x在even層，則：

如果節點x在odd層，則：

通過SimCT算法組建兩棵不同路徑的顏色樹，網絡中各節點可以通過兩棵不同顏色樹到達根節點。

3 基于SimCT的多播樹的組建

3.1 多播樹的組建

SimCT算法要求網絡拓撲必須為2連接網絡，即點到點之間至少有兩條通過不同節點的路徑，如圖2所示網絡拓撲。如圖3所示，以多播源節點S為根節點使用SimCT算法，組建Red和Blue兩棵顏色樹，節點上所標序號為算法中為各節點分發的DFS序號。

圖2 網絡拓撲示例

圖3 用SimCT算法構造的以多播源節點S為根的顏色樹

為了描述方便，本文把網絡中的路由節點，按照在構建多播樹過程中的不同職責分成3類：源節點、目的節點和中間節點。

源節點：一個源節點對應一棵多播樹，負責發送多播數據，是多播樹的根節點。

目的節點：用于接收從源節點發出的多播數據，多播樹的組建將會連接源節點和所有目的節點，是多播樹的葉子節點。

中間節點：在多播樹中連接源節點和各個目的節點，只負責轉發接收的數據報文，是多播樹的非葉子節點。

網絡中需要接收多播數據的節點，沿著到達多播源節點的顏色樹路徑，發送加入多播組報文。網絡中節點加入多播樹算法如圖4所示。

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

（1）網絡中目的節點需要接收多播數據，則沿Blue樹向源節點方向發送join報文。

圖4 節點加入多播樹算法

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

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

（4）如果join報文沿Blue/Red樹路徑一路轉發到達源節點S，源節點將join報文的發送節點加入到自己的oif_list中，并向join報文接收的方向返回success報文。

（5）中間節點收到success報文，轉發報文至oif_list中各節點。

（6）中間節點接收到failure報文，則將其轉發至oif_list中的各節點，并刪除相應的iif_list和oif_list中的節點。

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

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

（9）中間節點接收到 prune報文，刪除 oif_list中接收prune報文的發送節點，接著檢查oif_list表項中是否還有節點項存在，如果有，則不再轉發prune報文；如oif_list已經為空，則轉發prune報文至iif_list中節點，之后刪除iif_list中相應的節點項。

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

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

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

3.2 單節點/鏈路故障恢復

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

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

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

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

多播保護樹構造的具體報文交互過程如下。

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

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

（3）檢查iif_list是否為空，如不為空，則不再轉發change報文，并向change報文發送節點返回done報文；如iif_list為空，則轉發change報文。

圖7 節點7出現故障后，執行本文恢復方案得到的多播樹

（4）轉發change報文的規則如下：如果中間節點接收的change報文的發送節點是該節點的左轉發節點（Blue樹路徑），則change報文轉發至該中間節點的右轉發節點（Red樹路徑）；其他情況則將change報文轉發至該中間節點的左轉發節點（Blue樹路徑）。

（5）如果中間節點的Blue樹和Red樹路徑對應的轉發節點都不能成功發送change報文，則沿change報文接收的方向返回exit報文。

（6）中間節點接收到done報文后，沿著change報文接收的方向轉發done報文，一直轉發至初始change報文的發送節點，則保護樹構造成功。

（7）中間節點接收到exit報文后，沿著change報文接收的方向轉發exit報文，一直轉發至初始change報文的發送節點，則保護樹構造失敗。

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

圖8 節點5出現故障后，執行本文恢復方案得到的多播樹

（9）中間節點接收到prune報文，刪除oif_list中對應的prune報文的發送節點，接著檢查oif_list中是否還有節點表項存在，如果有，則不再轉發prune報文；如oif_list已經為空，則向iif_list中節點轉發prune報文，之后刪除iif_list中的節點項。

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

4 仿真與性能分析

本文的性能仿真均是在Matlab上實現，仿真中使用的網絡拓撲借鑒Salama博士的隨機網絡拓撲算法[9,10]生成，網絡節點隨機分布的正方形區域大小設定為2 000 km×2 000 km,根據概率來確定和之間是否存在鏈路，其中d(u,v)是u和v之間的歐氏距離，L是任意兩點間的最大距離。α和β是常數，較小的α將增大鏈路的密度，較大的β將導致較高的鏈路密度。通過調整α、β使產生的網絡拓撲滿足2連接的要求，即拓撲中頂點之間必須至少有兩個經過不同節點的路徑，本文仿真中取α=0.15，β=2.2。

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

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

圖9 隨機網絡節點數為100個時，不同多播規模下的多播樹包含節點數

圖10 隨機網絡節點數為200個時，不同多播規模下的多播樹包含節點數

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

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

圖11 隨機網絡節點數為100個時，單節點故障前與故障恢復后的多播樹代價

圖12 隨機網絡節點數為200個時，單節點故障前與故障恢復后的多播樹代價

5 結束語

本文在分析和研究SimCT算法的基礎上，提出了一種基于顏色樹的多播樹生成方法，并提出了一種多播單節點故障時的多播通信的恢復方案。仿真實驗表明，本文所提出的多播樹生成方案相比現有方案可以減少網絡資源的浪費，并且故障恢復后的代價與原多播通信樹相當。本文方案中的故障恢復，主要對單節點/鏈路進行保護，下一步將繼續研究和分析在多個節點/鏈路失敗情況下的故障恢復方法。

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