崔麗麗，曾學(xué)文，朱小勇

（1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190；2.中國科學(xué)院大學(xué)，北京 100049）

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

有關(guān)研究表明，網(wǎng)絡(luò)中的一條鏈路平均每30 分鐘就會經(jīng)歷一次故障[6]，其概率高于節(jié)點(diǎn)故障，如果不能很好地解決單鏈路故障問題，網(wǎng)絡(luò)數(shù)據(jù)傳輸將會遭遇很高的丟包率，這對數(shù)據(jù)敏感的應(yīng)用來說是災(zāi)難性的，也會影響整體性能。

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

1 相關(guān)工作

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

針對被動(dòng)式恢復(fù)，文獻(xiàn)[9]提出在檢測到故障后，在主路徑上標(biāo)記并回溯數(shù)據(jù)包，向第一個(gè)方便的重路由節(jié)點(diǎn)發(fā)出故障信號，自動(dòng)建立一條迂回路徑。該方案的目標(biāo)是在故障檢測后實(shí)現(xiàn)零丟包，不需要控制器干預(yù)，不足之處為恢復(fù)時(shí)間較長。

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

也有研究提出主動(dòng)恢復(fù)和被動(dòng)恢復(fù)結(jié)合的機(jī)制。文獻(xiàn)[12]提出一種保護(hù)加恢復(fù)式故障恢復(fù)機(jī)制，為所有路徑設(shè)置備份路徑，當(dāng)出現(xiàn)組播鏈路故障后，由備份路徑恢復(fù)組播鏈路傳輸，當(dāng)控制器安裝好新的最優(yōu)路徑后，再遷移至最優(yōu)路徑，不足之處為消耗資源過多。

2 組播樹的恢復(fù)機(jī)制

2.1 問題描述

以下為一個(gè)組播鏈路故障的恢復(fù)實(shí)例。將每個(gè)交換機(jī)記為一個(gè)節(jié)點(diǎn)，以組播匯聚節(jié)點(diǎn)（Rendezvous Point，RP）為根節(jié)點(diǎn)建立組播樹[13]，記故障鏈路中靠近根的節(jié)點(diǎn)為故障鏈路起點(diǎn)（StartNode，SN），記另一個(gè)端節(jié)點(diǎn)為故障鏈路終點(diǎn)（DestinationNode，DN）。

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

圖1 組播鏈路故障恢復(fù)實(shí)例

提前備份路徑對交換機(jī)中流表項(xiàng)有一定的挑戰(zhàn)，需要交換機(jī)有充足的存儲容量。

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

2.2 鏈路權(quán)重

建立一個(gè)組播拓?fù)銰=（N，L），其中，N表示交換機(jī)集合，L表示鏈路集合。對于一條鏈路l∈L，F(xiàn)DN（l）表示通過鏈路l的所有流的數(shù)量（FlowDataNumber，F(xiàn)DN）,可使用抓包工具監(jiān)測數(shù)據(jù)流，獲取FDN值。

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

其中，i、j為節(jié)點(diǎn)名稱，可使用網(wǎng)絡(luò)性能監(jiān)測工具監(jiān)測鏈路，通過獲取鏈路已消耗帶寬Bl（l（i，j））和鏈路最大帶寬Bmax（l（i，j））計(jì)算LBU值。

基于FDN和LBU，為平衡主動(dòng)恢復(fù)所需備份表項(xiàng)的資源開銷和被動(dòng)恢復(fù)所需重新計(jì)算路徑的時(shí)間開銷，將組播鏈路進(jìn)行分類，針對每類鏈路使用對應(yīng)的恢復(fù)策略，鏈路權(quán)重的評估標(biāo)準(zhǔn)如下：

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

按照圖2的示例拓?fù)洌O(shè)α=0.5、β=0.5，16 條鏈路的鏈路權(quán)重值如表1 所示，根據(jù)LW的取值對鏈路分類。其中LW=1的鏈路需要提前備份，LW=0的鏈路待中斷后再重建路徑。

表1 鏈路權(quán)重值

圖2 鏈路權(quán)重示例拓?fù)?/p>

2.3 故障恢復(fù)策略

2.3.1 主動(dòng)恢復(fù)

對于主動(dòng)恢復(fù)（Active Recovery，AR），AR（l）表示網(wǎng)絡(luò)G=（N，L）中的主動(dòng)恢復(fù)鏈路l集合，AR（l）={l|l∈L,LW=1}。

AR（l）是LW=1的所有鏈路的集合，對于LW=1的鏈路來說，每一條鏈路失效都會對大片區(qū)域產(chǎn)生影響，會導(dǎo)致組播樹中的多條鏈路傳輸中斷。因此，針對LW=1的鏈路，為了組播數(shù)據(jù)高效地傳輸，以較短的時(shí)延達(dá)到盡快恢復(fù)組播樹的效果，需要一個(gè)備份機(jī)制對高權(quán)重鏈路進(jìn)行備份。當(dāng)檢測到鏈路中斷時(shí)，采用備份鏈路，將時(shí)延降到最低，重構(gòu)組播樹，恢復(fù)組播數(shù)據(jù)的接收，提升組播的傳輸效率。

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

如圖1 所示，如果斷開，R1、R5、R6 接收數(shù)據(jù)中斷，LW=1，備份路徑為RP1-R2-R5 或者RP1-R2-R6，即想恢復(fù)R5、R6 數(shù)據(jù)的接收，需在R2、RP1 進(jìn)行流表項(xiàng)的備份。

2.3.2 被動(dòng)恢復(fù)

對于被動(dòng)恢復(fù)（Passive Recovery，PR），PR（l）表示網(wǎng)絡(luò)G=（N，L）中的被動(dòng)恢復(fù)鏈路l集合PR（l）={l|l∈L,LW=0}。

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

當(dāng)檢測到某條鏈路故障時(shí)，使用Networkx 中的all_shortest_paths 函數(shù)，尋找故障鏈路起點(diǎn)與目的組播成員間的備份路徑，并按照最小帶寬利用率優(yōu)先的原則，選擇重構(gòu)路徑，恢復(fù)組播數(shù)據(jù)的接收；

當(dāng)故障鏈路起點(diǎn)與目的組播成員間的最短路徑不存在，使用Networkx 中的all_shortest_paths 函數(shù)，尋找RP 與故障鏈路終點(diǎn)間的備份路徑，并按照最小帶寬利用率優(yōu)先的原則，選擇重構(gòu)路徑，完成組播數(shù)據(jù)的繼續(xù)傳輸，被動(dòng)恢復(fù)策略算法如下：

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

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

在控制層面和數(shù)據(jù)轉(zhuǎn)發(fā)層面，分別選擇控制器和交換機(jī)進(jìn)行仿真實(shí)驗(yàn)。表2 為仿真環(huán)境參數(shù)，并選擇表3 中兩種網(wǎng)絡(luò)拓?fù)溥M(jìn)行實(shí)驗(yàn)。

表2 仿真環(huán)境參數(shù)

表3 拓?fù)湫畔⒚枋?/p>

3.2 仿真結(jié)果

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

圖3 基于Fat-tree（K=4）的網(wǎng)絡(luò)拓?fù)?/p>

表4 故障恢復(fù)策略對比

3.2.1 備份流表項(xiàng)占比

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

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

圖4 拓?fù)?實(shí)驗(yàn)結(jié)果

圖5 拓?fù)?實(shí)驗(yàn)結(jié)果

根據(jù)仿真數(shù)據(jù)可以說明，方案LW-MTR 備份流表項(xiàng)對比方案CAFFE 有所減少，可以有效減少鏈路中的負(fù)載，優(yōu)化交換機(jī)中流表項(xiàng)的備份數(shù)量。

3.2.2 路徑恢復(fù)時(shí)間

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

圖6 故障恢復(fù)時(shí)間

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

在拓?fù)? 中，改變組播成員數(shù)量，使故障鏈路的數(shù)量保持一定，并進(jìn)行多次實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)如圖7 所示，方案LW-MTR的路徑恢復(fù)時(shí)間最短，平均比方案CAFFE 減少了4.6 ms，因?yàn)榉桨窪PR 是被動(dòng)恢復(fù)，恢復(fù)時(shí)間較長，方案LW-MTR 平均恢復(fù)時(shí)間比方案DPR 減少了6.8 ms；還可以觀察到，改變組播成員數(shù)量，保持故障鏈路數(shù)量一定，恢復(fù)時(shí)間只是略微增加。

圖7 拓?fù)?實(shí)驗(yàn)結(jié)果

4 結(jié)束語

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