基于鏈路權重的SDN 組播鏈路恢復機制

崔麗麗，曾學文，朱小勇

（1.中國科學院聲學研究所國家網絡新媒體工程技術研究中心，北京 100190；2.中國科學院大學，北京 100049）

組播在網絡層實現“盡力而為”的一對一組的傳輸功能，可以極大地減輕網絡負載，但也存在傳輸效率低、安全性差、不易部署等問題[1-2]。軟件定義網絡（Software Defined Network，SDN）[3]為組播方式提供了解決思路。SDN 由控制器和數據轉發設備（如交換機、路由器）兩部分組成，通過抽象底層網絡協議，以實現控制和轉發的分離[4]，從而簡化網絡模型[5]。

有關研究表明，網絡中的一條鏈路平均每30 分鐘就會經歷一次故障[6]，其概率高于節點故障，如果不能很好地解決單鏈路故障問題，網絡數據傳輸將會遭遇很高的丟包率，這對數據敏感的應用來說是災難性的，也會影響整體性能。

因此，組播鏈路故障快速恢復技術存在一定研究價值，針對以上問題，提出一種基于鏈路權重的組播樹恢復策略（Multicast Tree Recovery Strategy based on Link Weight，LW-MTR）。

1 相關工作

組播鏈路故障恢復方法可分為主動式和被動式[7]。主動式方法在故障發生之前計算備份路徑，當出現故障時，轉換至備份路徑，恢復數據傳輸[8]，時延較短，但造成了一定的資源損耗；被動式方法是在鏈路中斷之后，重新尋找新的路徑，消耗資源少，但時延較長。顯然，針對備份表項的資源開銷和恢復路徑的時間開銷需要策略進行有效權衡。針對兩種策略，已有不少學者作出研究。

針對被動式恢復，文獻[9]提出在檢測到故障后，在主路徑上標記并回溯數據包，向第一個方便的重路由節點發出故障信號，自動建立一條迂回路徑。該方案的目標是在故障檢測后實現零丟包，不需要控制器干預，不足之處為恢復時間較長。

針對主動式恢復，文獻[10]提出一種擁塞感知的快速故障恢復方案(CAFFE)，該方案不僅可以從廣泛的故障場景中快速恢復受影響的流量，而且可以避免恢復后網絡中潛在的擁塞。CAFFE 通過在鄰居交換機檢測到故障時立即繞道而行來實現快速恢復，所有這些路徑都是CAFFE 預先設置的，允許交換機自動恢復傳輸，而不需要等待控制器的響應。文獻[11]提出基于分段路由的主動式鏈路故障恢復方案（SR-PLFR），將通過同一鏈路的受影響流視為聚合流，為之計算備份路徑，并將其轉化為混合整數非線性規劃模型，把工作路徑和備份路徑劃分成段，以滿足硬件要求。但是，這兩種恢復策略均存在消耗資源較多的問題。

也有研究提出主動恢復和被動恢復結合的機制。文獻[12]提出一種保護加恢復式故障恢復機制，為所有路徑設置備份路徑，當出現組播鏈路故障后，由備份路徑恢復組播鏈路傳輸，當控制器安裝好新的最優路徑后，再遷移至最優路徑，不足之處為消耗資源過多。

2 組播樹的恢復機制

2.1 問題描述

以下為一個組播鏈路故障的恢復實例。將每個交換機記為一個節點，以組播匯聚節點（Rendezvous Point，RP）為根節點建立組播樹[13]，記故障鏈路中靠近根的節點為故障鏈路起點（StartNode，SN），記另一個端節點為故障鏈路終點（DestinationNode，DN）。

如圖1 所示，8 個交換機和10 條鏈路構成組播樹。其中，RP 與組播源相連，R5、R6、R7 與組播成員直連，3 條通信路徑分別為RP-R1-R3-R6，RP-R2-R4-R7，RP-R2-R5。當中斷，即R2 為SN，R4為DN時，R4、R7中斷了數據流的接收。有3條恢復路徑，分別是R2-R5-R4（需R2、R5增加一條流表項完成備份）、RP-R1-R3-R4和RP-R1-R4，其中RPR1-R3-R4 比RP-R1-R4 多產生一個備份流表項。

圖1 組播鏈路故障恢復實例

提前備份路徑對交換機中流表項有一定的挑戰，需要交換機有充足的存儲容量。

但是，有些鏈路并不需要提前備份路徑，因此文中研究的重點在于平衡主動恢復所需備份表項的資源開銷和被動恢復所需重新計算路徑的時間開銷，文中的研究按照鏈路權重（LinkWeight，LW），將組播鏈路分為兩類，針對LW=1，找到最佳的備份方式；針對LW=0，即無需備份的鏈路，找到快速恢復鏈路的方法，平衡資源開銷和時間開銷，達到組播樹的全局最優恢復。

2.2 鏈路權重

建立一個組播拓撲G=（N，L），其中，N表示交換機集合，L表示鏈路集合。對于一條鏈路l∈L，FDN（l）表示通過鏈路l的所有流的數量（FlowDataNumber，FDN）,可使用抓包工具監測數據流，獲取FDN值。

定義1 在網絡G中，設鏈路l（i，j）能提供的最大帶寬為Bmax（l（i，j）），Bl（l（i，j））表示鏈路已消耗帶寬，則l（i，j）鏈路帶寬利用率（Link Bandwidth Utilization，LBU）如下：

其中，i、j為節點名稱，可使用網絡性能監測工具監測鏈路，通過獲取鏈路已消耗帶寬Bl（l（i，j））和鏈路最大帶寬Bmax（l（i，j））計算LBU值。

基于FDN和LBU，為平衡主動恢復所需備份表項的資源開銷和被動恢復所需重新計算路徑的時間開銷，將組播鏈路進行分類，針對每類鏈路使用對應的恢復策略，鏈路權重的評估標準如下：

其中，α+β=1，α∈[0,1]，β∈[0,1]，α和β用來調節FDN和LBU之間的權重，需要注意的是，。因此，LW的最大值為1，最小值為0。將LW二值化，[0,0.4]定義為LW=0，(0.4，1]定義為LW=1。

按照圖2的示例拓撲，設α=0.5、β=0.5，16 條鏈路的鏈路權重值如表1 所示，根據LW的取值對鏈路分類。其中LW=1的鏈路需要提前備份，LW=0的鏈路待中斷后再重建路徑。

表1 鏈路權重值

圖2 鏈路權重示例拓撲

2.3 故障恢復策略

2.3.1 主動恢復

對于主動恢復（Active Recovery，AR），AR（l）表示網絡G=（N，L）中的主動恢復鏈路l集合，AR（l）={l|l∈L,LW=1}。

AR（l）是LW=1的所有鏈路的集合，對于LW=1的鏈路來說，每一條鏈路失效都會對大片區域產生影響，會導致組播樹中的多條鏈路傳輸中斷。因此，針對LW=1的鏈路，為了組播數據高效地傳輸，以較短的時延達到盡快恢復組播樹的效果，需要一個備份機制對高權重鏈路進行備份。當檢測到鏈路中斷時，采用備份鏈路，將時延降到最低，重構組播樹，恢復組播數據的接收，提升組播的傳輸效率。

采用Networkx[14]中的all_shortest_paths 函數，利用Dijkstra 算法，將AR中工作鏈路起點到目的組播成員所有備份路徑放在AllBackupPath。然后按照備份交換機數量增序排列，如果備份交換機數量相同，則按照帶寬利用率增序排列，備份路徑選擇策略算法如下：

如圖1 所示，如果斷開，R1、R5、R6 接收數據中斷，LW=1，備份路徑為RP1-R2-R5 或者RP1-R2-R6，即想恢復R5、R6 數據的接收，需在R2、RP1 進行流表項的備份。

2.3.2 被動恢復

對于被動恢復（Passive Recovery，PR），PR（l）表示網絡G=（N，L）中的被動恢復鏈路l集合PR（l）={l|l∈L,LW=0}。

PR（l）是LW=0的所有鏈路的集合，即鏈路l具有較低權重的鏈路。即通過鏈路l的流的數量很少或這些流對時延和丟包率的需求不高，因此，不需要對這些鏈路提前備份以免造成資源過度消耗。

當檢測到某條鏈路故障時，使用Networkx 中的all_shortest_paths 函數，尋找故障鏈路起點與目的組播成員間的備份路徑，并按照最小帶寬利用率優先的原則，選擇重構路徑，恢復組播數據的接收；

當故障鏈路起點與目的組播成員間的最短路徑不存在，使用Networkx 中的all_shortest_paths 函數，尋找RP 與故障鏈路終點間的備份路徑，并按照最小帶寬利用率優先的原則，選擇重構路徑，完成組播數據的繼續傳輸，被動恢復策略算法如下：

如圖1 所示，如果中斷，只影響R5 接收數據，LW=0，鏈路中斷之后采用被動恢復的方法，重建恢復路徑RP1-R2-R5。

3 仿真實驗

3.1 仿真環境

在控制層面和數據轉發層面，分別選擇控制器和交換機進行仿真實驗。表2 為仿真環境參數，并選擇表3 中兩種網絡拓撲進行實驗。

表2 仿真環境參數

表3 拓撲信息描述

3.2 仿真結果

假設所有鏈路的故障率相同，為仿真鏈路故障，在Mininet 中采用“link node1 node2 down”指令使node1node2 鏈路中斷，為獲取LBU值，采用Iperf 軟件監測鏈路，獲取鏈路已消耗帶寬Bl（l（i，j））和鏈路最大帶寬Bmax（l（i，j））。采用Wireshark 抓包，獲取FDN值。采用備份流表項占比、路徑恢復時間兩個指標作為評價標準，并與現有的方法進行對比，如表4所示。

圖3 基于Fat-tree（K=4）的網絡拓撲

表4 故障恢復策略對比

3.2.1 備份流表項占比

在主動式恢復中，需要提前備份路徑，因此產生了一定程度上的資源消耗，使用BF（Backup Flow Table Entry）表示備份路徑所需的總流表項數，WF（Work Flow Table Entry）表示工作路徑所需的總流表項數，記備份流表項占比PBF=BF/（BF+WF）；備份PBF數值越大，代表備份流表項占總消耗資源的比重越大，一定程度上為鏈路帶來了較重的負載。

考慮到數據的可靠性，采取多次實驗取平均值。如圖4 所示，改變組播成員數量，當接收者不斷增加時，通過鏈路的數據流的數量和鏈路的帶寬利用率都會增加，由公式可知，鏈路權重變大，故而需要提前備份的路徑增加，備份流表項占比不斷增加。因為被動恢復不需要提前備份路徑，只在鏈路故障之后才會重新計算，所以方案DPR的備份流表項占比低于方案CAFFE和LW-MTR，比方案CAFFE 減少大約27.2%，比方案LW-MTR 減少大約10.1%。對比方案CAFFE，方案LW-MTR 備份路徑流表項占比減少大約17.1%。在拓撲2上進行了相同的實驗，如圖5所示，相比方案LW-MTR備份流表項占比減少15.1%。

圖4 拓撲1實驗結果

圖5 拓撲2實驗結果

根據仿真數據可以說明，方案LW-MTR 備份流表項對比方案CAFFE 有所減少，可以有效減少鏈路中的負載，優化交換機中流表項的備份數量。

3.2.2 路徑恢復時間

故障恢復時間(Failure Recovery Time)[19]包括故障檢測時間（Fault Detection Time，TFD）和路徑恢復時間（Path Recovery Time，TPR），如圖6 所示。

圖6 故障恢復時間

為縮短故障恢復時間，可從減少故障檢測時間和路徑恢復時間兩個方面入手，文中的研究內容為減少路徑恢復時間。在目的節點上，采用Wireshark抓包，以觀察數據流的傳輸。記錄檢測到鏈路中斷后的時間T1，并獲取鏈路中斷后恢復接收第一個數據包的到達時間T2，路徑恢復時間即為T2-T1。

在拓撲2 中，改變組播成員數量，使故障鏈路的數量保持一定，并進行多次實驗。實驗數據如圖7 所示，方案LW-MTR的路徑恢復時間最短，平均比方案CAFFE 減少了4.6 ms，因為方案DPR 是被動恢復，恢復時間較長，方案LW-MTR 平均恢復時間比方案DPR 減少了6.8 ms；還可以觀察到，改變組播成員數量，保持故障鏈路數量一定，恢復時間只是略微增加。

圖7 拓撲2實驗結果

4 結束語

文中提出了基于鏈路權重的SDN 組播鏈路故障恢復機制。為平衡備份表項的資源開銷和恢復路徑的時間開銷，首先根據鏈路帶寬利用率和數據流的數量定義鏈路權重，然后針對不同的鏈路提出了兩種策略，針對鏈路權重LW=1的鏈路，采用主動恢復的方式，針對鏈路權重LW=0的鏈路，采用被動恢復的方式，并與現有方法進行了對比，采用備份流表項占比和路徑恢復時間作為評價指標。仿真實驗結果顯示，該方案在備份流表項占比和路徑恢復時間上有明顯優勢。