姜厚海，莊 毅，曹子寧

（南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106）

0 引 言

軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）是一種新的網(wǎng)絡(luò)架構(gòu)［1］，它將傳統(tǒng)交換機(jī)的控制邏輯與數(shù)據(jù)轉(zhuǎn)發(fā)操作分離，運(yùn)營商可以通過控制平面的集中控制器輕松部署網(wǎng)絡(luò)應(yīng)用。在SDN 中，邏輯集中的控制器直接決定交換機(jī)的轉(zhuǎn)發(fā)行為，并通過一些標(biāo)準(zhǔn)化協(xié)議（如OpenFlow［2］等）監(jiān)控網(wǎng)絡(luò)狀態(tài)。這種架構(gòu)通過對(duì)網(wǎng)絡(luò)的集中控制，降低了網(wǎng)絡(luò)管理的復(fù)雜度，實(shí)現(xiàn)了更靈活的網(wǎng)絡(luò)控制并有利于網(wǎng)絡(luò)創(chuàng)新［3-5］。

盡管SDN 控制與轉(zhuǎn)發(fā)分離的思想在當(dāng)下取得了迅速的發(fā)展，但由于關(guān)鍵鏈路擁塞、鏈路帶寬利用不均衡、鏈路或節(jié)點(diǎn)故障等原因，SDN 提供的可靠數(shù)據(jù)傳輸受到了巨大挑戰(zhàn)。其中，單鏈路故障是一個(gè)必須解決的主要問題，因?yàn)閱捂溌饭收鲜蔷W(wǎng)絡(luò)中最常見的問題［6］，其發(fā)生概率高于其他故障幾個(gè)數(shù)量級(jí)。

針對(duì)單鏈路故障，目前的故障恢復(fù)方案可以分為2 類：反應(yīng)式故障恢復(fù)方案和主動(dòng)式故障恢復(fù)方案［7-8］。這2 種策略的主要區(qū)別在于是否提前設(shè)置了受保護(hù)的路徑以及故障恢復(fù)過程是否需要控制器參與。反應(yīng)式故障恢復(fù)方案中，在鏈路發(fā)生故障之后，集中控制器會(huì)收到鏈路中斷的通知，然后根據(jù)當(dāng)前拓?fù)湫畔?duì)備份路徑進(jìn)行動(dòng)態(tài)計(jì)算，并將計(jì)算得到的備份路徑流表規(guī)則下發(fā)到相關(guān)的交換機(jī)上，以轉(zhuǎn)移中斷的流量［9-10］。主動(dòng)式故障恢復(fù)方案中，集中控制器會(huì)在出現(xiàn)任何故障鏈路之前，預(yù)先將備份路徑的轉(zhuǎn)發(fā)規(guī)則下發(fā)到相應(yīng)交換機(jī)上。當(dāng)交換機(jī)之間的鏈路發(fā)生故障而無法傳輸數(shù)據(jù)時(shí)，數(shù)據(jù)平面的交換機(jī)可以自動(dòng)將中斷的流量轉(zhuǎn)發(fā)到備份路徑，無需控制器參與［11-12］。

這2 種故障恢復(fù)方案各有優(yōu)缺點(diǎn)。對(duì)于主動(dòng)式恢復(fù)方案來講，提前安裝備份路徑轉(zhuǎn)發(fā)規(guī)則可以在發(fā)現(xiàn)故障后快速恢復(fù)，但是會(huì)消耗珍貴的三態(tài)內(nèi)容尋址存儲(chǔ)器（Ternary Content Addressable Memory，TCAM）資源，大大增加了網(wǎng)絡(luò)成本［13］。TCAM是一種昂貴且存儲(chǔ)受限的高能耗硬件［14］，根據(jù)文獻(xiàn)［15］顯示TCAM 比基于ARM的存儲(chǔ)硬件貴400倍。另外，提前安裝備份路徑難以保證故障發(fā)生后備份路徑的性能，可能會(huì)在故障恢復(fù)后發(fā)生鏈路擁塞，造成網(wǎng)絡(luò)服務(wù)質(zhì)量（QoS）的下降［16］。而反應(yīng)式故障恢復(fù)方案需要在發(fā)生故障后重新計(jì)算中斷流量的備份路徑，會(huì)增加集中控制器的負(fù)載，并且有較高的恢復(fù)時(shí)延，難以在電信級(jí)別要求的50 ms［17］內(nèi)完成整個(gè)鏈路故障的恢復(fù)過程。

從2 種故障恢復(fù)方案的優(yōu)缺點(diǎn)來看，有必要去設(shè)計(jì)一種新的故障恢復(fù)方案來平衡SDN 中的故障恢復(fù)時(shí)間和存儲(chǔ)成本。針對(duì)主動(dòng)式恢復(fù)方案中流表規(guī)則消耗太多存儲(chǔ)資源的缺陷，人們提出了一種基于流聚合的方案來解決這個(gè)問題。該方案將所有受到故障影響的流量聚合為一個(gè)帶有新標(biāo)簽的大流量，控制器只需要為聚合流提前計(jì)算備份路徑并安裝流表規(guī)則即可。然而，一個(gè)包含所有中斷流的聚合流在重路由的過程中，很可能會(huì)導(dǎo)致恢復(fù)后網(wǎng)絡(luò)中的潛在擁塞。因此，本文提出一種基于流聚合與擁塞避免的SDN快速故障恢復(fù)方案FACAR。該方案支持從單鏈路故障中進(jìn)行本地故障轉(zhuǎn)移，并且可以將流經(jīng)同一鏈路的流量備份到不同的備份鏈路，從而避免故障恢復(fù)后網(wǎng)絡(luò)中的潛在擁塞。

本文主要工作如下：

1）為SDN提供一種有效的快速故障恢復(fù)方案，可以在SDN 交換機(jī)上以低存儲(chǔ)開銷實(shí)現(xiàn)本地快速故障恢復(fù)，同時(shí)，可以避免故障恢復(fù)后網(wǎng)絡(luò)中的潛在擁塞。

2）將故障恢復(fù)方案表示為一個(gè)整數(shù)線性規(guī)劃問題，并提出一種基于貪心的啟發(fā)式算法去選擇最合適的備份路徑。

3）進(jìn)行廣泛的仿真來評(píng)估性能，結(jié)果表明，與現(xiàn)有的SDN 故障恢復(fù)方法相比，可以在滿足快速故障恢復(fù)的基礎(chǔ)上實(shí)現(xiàn)低TCAM 存儲(chǔ)開銷和故障恢復(fù)后的負(fù)載均衡。

1 相關(guān)工作

在主動(dòng)式故障恢復(fù)和反應(yīng)式故障恢復(fù)方案方面，國內(nèi)外學(xué)者已經(jīng)有了許多的研究成果。

Sharma 等人［9］詳細(xì)介紹了反應(yīng)式故障恢復(fù)的過程，在檢測(cè)到故障后，控制器更新拓?fù)洳槊總€(gè)受到故障影響的流計(jì)算工作路徑，通過刪除舊的流表規(guī)則和下發(fā)新的流表規(guī)則來完成流的重定向。他們還比較了主動(dòng)式恢復(fù)和反應(yīng)式恢復(fù)方法的恢復(fù)延遲性能［10］，實(shí)驗(yàn)結(jié)果表明反應(yīng)式故障恢復(fù)策略恢復(fù)延遲在75～130 ms 左右，難以滿足電信級(jí)別要求，而主動(dòng)式故障恢復(fù)策略恢復(fù)延遲可以控制在45 ms 以內(nèi)。Kim 等人［18］提出了一種采用反應(yīng)式策略從多鏈路故障中恢復(fù)的系統(tǒng)，其中控制器使用全局網(wǎng)絡(luò)的拓?fù)湫畔碛?jì)算多條路由路徑以處理多鏈路故障。在文獻(xiàn)［19］中，作者提出一種稱為本地快速重路由的方法，該方法通過將所有受到故障影響的流聚合為一個(gè)流，并在鏈路故障之后通過控制器計(jì)算路徑，使得聚合流可以轉(zhuǎn)發(fā)到故障鏈路的下游交換機(jī)，完成流的重定向。顯然，由于反應(yīng)式故障恢復(fù)策略在發(fā)生故障之后，需要控制器重新計(jì)算工作路徑，使得反應(yīng)式故障恢復(fù)策略在恢復(fù)時(shí)延方面表現(xiàn)不佳，不適用于運(yùn)營商級(jí)網(wǎng)絡(luò)。但是，它可以處理多組件故障的情況，并且不需要存儲(chǔ)額外的轉(zhuǎn)發(fā)規(guī)則，節(jié)省了存儲(chǔ)空間。

主動(dòng)式故障恢復(fù)方案采用故障保護(hù)策略，控制器可以預(yù)先將受保護(hù)的路徑轉(zhuǎn)發(fā)規(guī)則配置到數(shù)據(jù)平面的交換機(jī)中，以便上游鄰居交換機(jī)可以將受故障影響的流從工作路徑切換到受保護(hù)路徑。在這種情況下，故障恢復(fù)時(shí)延幾乎等同于故障檢測(cè)時(shí)間。在文獻(xiàn)［20］中，工作路徑和備份路徑的流表規(guī)則被分配了不同的優(yōu)先級(jí)，如果沒有發(fā)生故障，則優(yōu)先級(jí)較高的工作路徑流表規(guī)則將發(fā)揮作用，否則，工作路徑的流表規(guī)則會(huì)被刪除，優(yōu)先級(jí)較低的備份路徑流表規(guī)則將用于流的重定向。文獻(xiàn)［11］提出一種1:1 保護(hù)機(jī)制，控制器為工作路徑計(jì)算一條不相交的備份路徑，并結(jié)合使用Fast Failover 故障切換功能，如果鏈路發(fā)生故障，交換機(jī)將進(jìn)行切換操作，將受影響的數(shù)據(jù)流重定向到備份路徑，而不需要控制器的參與。上述研究通過預(yù)先配置流的備份路徑實(shí)現(xiàn)快速轉(zhuǎn)移，當(dāng)流的數(shù)量增加時(shí)，無疑會(huì)加大交換機(jī)內(nèi)部存儲(chǔ)空間的消耗。針對(duì)該問題，Zhang 等人［12］提出了一種以更少的備份資源實(shí)現(xiàn)故障恢復(fù)的方法，根據(jù)鏈路重要性將鏈路分為3個(gè)級(jí)別，為最高級(jí)別的鏈路配置2條備份路徑，為中等級(jí)別的鏈路配置1 條備份路徑，最低級(jí)別的鏈路采用反應(yīng)式故障恢復(fù)策略。這種方法雖然減少了備份資源的消耗，但是其覆蓋的保護(hù)范圍并不全面，僅可以滿足重要鏈路上數(shù)據(jù)流的恢復(fù)時(shí)延和傳輸質(zhì)量。Chen等人［21］提出了一種使用流標(biāo)記機(jī)制的主動(dòng)恢復(fù)方案，以較少的備份資源恢復(fù)單鏈路故障。如果發(fā)生鏈路故障，受故障影響的數(shù)據(jù)包將被標(biāo)記VLAN 標(biāo)簽并重定向到故障鏈路的另一端。然而，包含所有中斷數(shù)據(jù)流量的聚合流的重定向可能會(huì)導(dǎo)致恢復(fù)后網(wǎng)絡(luò)中的鏈路擁塞問題。

通過對(duì)已有工作內(nèi)容的總結(jié)與分析，可以發(fā)現(xiàn)之前的鏈路故障恢復(fù)方案的側(cè)重點(diǎn)都有所不同，整體包含3 個(gè)方面：1）鏈路發(fā)生故障后網(wǎng)絡(luò)恢復(fù)需要的時(shí)間長短；2）對(duì)TCAM 存儲(chǔ)資源消耗的多少；3）鏈路故障恢復(fù)后網(wǎng)絡(luò)是否會(huì)發(fā)生鏈路擁塞。綜合考慮這3 個(gè)方面，本文提出一種基于流聚合與擁塞避免的快速故障恢復(fù)方案（Flow Aggregation and Congestion Avoidance for Fast Failure Recovery in SDN，F(xiàn)ACAR），其主要特性如下：

1）快速恢復(fù)：FACAR 預(yù)先安裝備份路徑，并在故障鏈路的鄰居交換機(jī)上結(jié)合使用Fast Failover 故障切換功能進(jìn)行流的重定向，縮短故障恢復(fù)時(shí)間。

2）低存儲(chǔ)開銷：FACAR通過將同一鏈路上的所有流視為一個(gè)或幾個(gè)聚合流，然后僅為聚合流構(gòu)造受保護(hù)的路徑，大大減少備份流表規(guī)則對(duì)存儲(chǔ)資源的占用。

3）擁塞避免：對(duì)于重路由可能會(huì)導(dǎo)致的網(wǎng)絡(luò)擁塞問題，F(xiàn)ACAR 通過綜合考慮網(wǎng)絡(luò)拓?fù)?、故障狀態(tài)以及鏈路負(fù)載來進(jìn)行不同保護(hù)路徑的安裝，以確保重路由后不會(huì)出現(xiàn)網(wǎng)絡(luò)擁塞問題。

2 SDN網(wǎng)絡(luò)模型和故障恢復(fù)策略

2.1 網(wǎng)絡(luò)模型

本文中的SDN網(wǎng)絡(luò)拓?fù)淠Ｐ突硎緸镚=（V，E），其中V表示交換機(jī)集合，E表示鏈路集合。在本文提出的方案中，采用了OpenFlow 協(xié)議提供的虛擬局域網(wǎng)（VLAN）標(biāo)記功能，將網(wǎng)絡(luò)中的每條鏈路用一個(gè)唯一的標(biāo)識(shí)符標(biāo)記，當(dāng)鏈路出現(xiàn)故障后，為所有流經(jīng)故障鏈路的數(shù)據(jù)流打上唯一鏈路標(biāo)識(shí)符，然后利用Fast Failover 組表功能將流量傳輸切換到備份路徑，為了避免故障恢復(fù)后潛在的擁塞問題，可能會(huì)提前配置多條備份路徑，在備份路徑上，通過唯一鏈路標(biāo)識(shí)符對(duì)流進(jìn)行聚合，可以大大減少備份路徑對(duì)流表存儲(chǔ)資源的消耗。本文所用完整的符號(hào)列表如表1所示。

表1 符號(hào)列表

2.2 基于流聚合與擁塞避免的故障恢復(fù)策略

在SDN 網(wǎng)絡(luò)架構(gòu)中，控制器會(huì)利用鏈路層發(fā)現(xiàn)協(xié)議（Link Layer Discovery Protocol，LLDP）獲取網(wǎng)絡(luò)整體的拓?fù)浣Y(jié)構(gòu)并維護(hù)可用的備份路徑信息?；谶@些信息，控制器可以在流的工作路徑上預(yù)先配置備份路徑，以預(yù)防可能發(fā)生的單鏈路故障。當(dāng)數(shù)據(jù)流的首個(gè)數(shù)據(jù)包進(jìn)入網(wǎng)絡(luò)后，源交換機(jī)會(huì)向控制器發(fā)送Packet_in 消息，控制器收到請(qǐng)求后，利用全局的拓?fù)湟晥D為源、目的主機(jī)計(jì)算工作路徑以及每條工作鏈路的備份路徑，將對(duì)應(yīng)鏈路的VLAN ID 作為故障上游交換機(jī)備份路徑的匹配規(guī)則，最后下發(fā)流表安裝指令到所有相關(guān)的交換機(jī)中。在數(shù)據(jù)流正常傳輸過程中，交換機(jī)將數(shù)據(jù)包轉(zhuǎn)發(fā)到Fast Failover 組表中，之后將數(shù)據(jù)包轉(zhuǎn)發(fā)到工作路徑的下一跳交換機(jī)。當(dāng)鏈路出現(xiàn)故障之后，故障上游交換機(jī)會(huì)將原來通過故障鏈路的數(shù)據(jù)包都打上唯一VLAN ID 標(biāo)簽，然后轉(zhuǎn)發(fā)到備份路徑的下一跳交換機(jī)，備份路徑通過匹配VLAN ID 進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)，最后在數(shù)據(jù)包轉(zhuǎn)發(fā)到故障下游交換機(jī)之前去除VLAN ID 標(biāo)簽，由故障下游交換機(jī)繼續(xù)完成正常工作路徑的數(shù)據(jù)包轉(zhuǎn)發(fā)。

下面通過一個(gè)例子來說明本文的故障恢復(fù)策略。在網(wǎng)絡(luò)拓?fù)渲邪? 臺(tái)交換機(jī)（S1、S2、S3、S4、S5）以及6 臺(tái)主機(jī)（H1、H2、H3、H4、H5、H6），網(wǎng)絡(luò)中部署了3 個(gè)數(shù)據(jù)流，分別為H1→H4、H2→H5、H3→H6，每條鏈路附近的2 個(gè)數(shù)據(jù)表示流量負(fù)載和鏈路總帶寬。各鏈路對(duì)應(yīng)的VLAN ID如表2所示。

表2 鏈路對(duì)應(yīng)的VLAN ID表

圖1顯示了鏈路故障前的3個(gè)流量的路由情況。

圖1 正常路由

圖2 顯示了典型的主動(dòng)故障恢復(fù)策略，鏈路S1-S5 的備份路徑為S1-S2-S5。當(dāng)S1-S5 鏈路發(fā)生故障之后，3 條流量會(huì)同時(shí)經(jīng)過備份路徑S1-S2-S5，使鏈路S1-S2 和S2-S5 出現(xiàn)鏈路擁塞問題，承載的流量帶寬超過了鏈路的帶寬。

圖2 典型主動(dòng)故障恢復(fù)

圖3 顯示了本文提出的故障恢復(fù)策略，對(duì)于鏈路S1-S5，部署了2 條備份路徑，其中S1-S2-S5 作為流H1→H4 的備份路徑，S1-S3-S4-S5 作為流H2→H5和H3→H6的備份路徑。通過使用2條備份路徑將故障鏈路S1-S5 上的3 個(gè)流進(jìn)行重路由，并利用流聚合的特性減少了S3、S4 交換機(jī)中的備份轉(zhuǎn)發(fā)規(guī)則的數(shù)目，即只需要為流H2→H5 和流H3→H6 形成的聚合流配置2 個(gè)VLAN ID=3 的匹配轉(zhuǎn)發(fā)規(guī)則。在這種情況下，與為每個(gè)流的鏈路都進(jìn)行備份轉(zhuǎn)發(fā)規(guī)則的典型主動(dòng)故障恢復(fù)方法相比，大大減少了預(yù)置備份轉(zhuǎn)發(fā)規(guī)則的數(shù)目，同時(shí)，避免了故障恢復(fù)后網(wǎng)絡(luò)中的潛在擁塞問題。

圖3 基于流聚合與擁塞避免的故障恢復(fù)

2.3 問題定義

FACAR 方案使用提前安裝備份路徑的方式來實(shí)現(xiàn)鏈路故障快速恢復(fù)，為了避免恢復(fù)后鏈路擁塞，F(xiàn)ACAR 允許將故障鏈路的恢復(fù)流量分流到多個(gè)預(yù)置的備份路徑。在預(yù)先配置備份路徑時(shí)，本文的目標(biāo)是在鏈路故障前最小化配置備份轉(zhuǎn)發(fā)規(guī)則的數(shù)量。對(duì)該問題的正式描述如式（1）所示：

其中，P表示鏈路l上游交換機(jī)sl到鏈路l下游交換機(jī)dl的k條最短的路徑集合，hi表示路徑pi是否被選為備份路徑，m表示鏈路l上流的數(shù)量，xij表示流fj的備份路徑是否為pi，ni表示路徑pi上的交換機(jī)數(shù)量，需要滿足約束條件如下：

式（2）表示集合P中所有備份路徑都必須不包含待保護(hù)鏈路l，其中表示路徑pi是否包含鏈路（sl，dl）。

式（3）表示流量守恒定律，即流入交換機(jī)u的流量會(huì)從u完全流出，以確保流在路徑中的連續(xù)性。

式（4）表示循環(huán)避免約束，即備份路徑pi不包含環(huán)路，以確保流在傳輸路徑中的性能。

式（5）表示分配給備份路徑pi的流的帶寬總和不能超過pi的可用帶寬，以確保鏈路故障恢復(fù)后沒有潛在的擁塞問題，其中bj表示流fj的帶寬，λ表示鏈路利用率上限表示鏈路的帶寬，表示鏈路的負(fù)載。

式（6）表示每個(gè)被中斷的流都會(huì)被分配到一個(gè)唯一的備份路徑上，以確保被中斷的流可以正常恢復(fù)。

通過求解這個(gè)整數(shù)線性優(yōu)化問題ILP，可以獲得所有備份路徑以及備份流表規(guī)則的數(shù)量。然而，從整數(shù)多商品流問題［22］的推導(dǎo)中可知，這個(gè)優(yōu)化問題是NP完全的，對(duì)于大型網(wǎng)絡(luò)，計(jì)算可能無法在多項(xiàng)式時(shí)間內(nèi)完成。因此，為了在多項(xiàng)式時(shí)間內(nèi)解決該優(yōu)化問題，本文設(shè)計(jì)一個(gè)多項(xiàng)式時(shí)間復(fù)雜度為O(kv(n+vlog2v) +k(n+m+v))的啟發(fā)式算法，如下文的算法1所示。

3 ILP-FACAR算法設(shè)計(jì)

3.1 備份路徑計(jì)算

為了解決上文提出的優(yōu)化問題，本文提出一種基于貪心的啟發(fā)式算法，該算法計(jì)算待保護(hù)鏈路的上下游交換機(jī)節(jié)點(diǎn)之間的前k條最短路徑，然后再計(jì)算每條路徑的可用帶寬并按照可用帶寬對(duì)路徑進(jìn)行降序排序，最后選擇滿足條件的路徑對(duì)流進(jìn)行備份。

在FACAR 中，為了實(shí)現(xiàn)故障快速恢復(fù)，利用OpenFlow 協(xié)議的組表功能實(shí)現(xiàn)快速故障轉(zhuǎn)移功能，在檢測(cè)到故障發(fā)生后，故障上游交換機(jī)可以自動(dòng)將中斷的數(shù)據(jù)流繞開故障鏈路轉(zhuǎn)發(fā)到預(yù)先配置的備份路徑上，無需控制器參與，從而可減少故障恢復(fù)時(shí)間。同時(shí)，為了避免故障恢復(fù)后的擁塞，控制器給每個(gè)中斷的流預(yù)先配置備份路徑，并且將分配給相同備份路徑的流匯聚成具有唯一VLAN ID 標(biāo)簽的聚合流。FACAR 采用靈活的流聚合策略，實(shí)現(xiàn)SDN 單鏈路故障的快速恢復(fù)和擁塞避免。

算法1 的輸入為網(wǎng)絡(luò)拓?fù)洹⒋Ｗo(hù)鏈路和待保護(hù)鏈路上的流集合，輸出為待保護(hù)鏈路提前配置的備份轉(zhuǎn)發(fā)規(guī)則的數(shù)量。

算法1ILP-FACAR算法。

輸入：網(wǎng)絡(luò)拓?fù)銰=（V，E），待保護(hù)鏈路l，l上的流集合F。

輸出：鏈路l的備份轉(zhuǎn)發(fā)規(guī)則的數(shù)量。

算法1流程描述如下：

1）流排序和拓?fù)涓?。?duì)待保護(hù)鏈路上的流按照帶寬大小進(jìn)行降序排序，并將待保護(hù)鏈路從拓?fù)渲腥コ?，然后更新網(wǎng)絡(luò)拓?fù)洹?/p>

2）最短K 路徑計(jì)算。采用Yen［23］提出的KShortestPaths算法計(jì)算待保護(hù)鏈路上下游交換機(jī)節(jié)點(diǎn)之間的前k條最短路徑，將它們作為備份路徑的候選路徑，最后按照路徑的跳數(shù)對(duì)這些候選路徑進(jìn)行升序排序。

3）路徑可用帶寬計(jì)算。為每條候選路徑創(chuàng)建一個(gè)空集合，用于存儲(chǔ)當(dāng)候選路徑被選為備份路徑時(shí)被路徑備份的流，并計(jì)算路徑的可用帶寬。

4）備份路徑選擇。迭代每條待保護(hù)鏈路上的流，選擇最短的候選路徑，如果候選路徑可用帶寬滿足流的需求，就選擇當(dāng)前候選路徑作為流的備份路徑，然后將流添加到候選路徑的備份流集合中，并更新該路徑的可用帶寬，否則，選擇下一條最短的候選路徑。

5）配置備份路徑轉(zhuǎn)發(fā)規(guī)則。迭代每條候選路徑，如果候選路徑的備份流集合不為空，表明該候選路徑被選為一條或幾條流的備份路徑，采用下文的算法2進(jìn)行備份路徑上轉(zhuǎn)發(fā)規(guī)則的配置，最后輸出提前配置的備份轉(zhuǎn)發(fā)規(guī)則的數(shù)量。

3.2 備份路徑流規(guī)則安裝

當(dāng)控制器完成待保護(hù)路徑的備份路徑計(jì)算后，采用算法2進(jìn)行備份路徑流規(guī)則的安裝。

算法2備份路徑流規(guī)則配置算法。

輸入：備份路徑pi，pi備份的流集合Ui。

輸出：對(duì)應(yīng)交換機(jī)的流規(guī)則配置。

算法2主要操作描述如下：

1）待保護(hù)鏈路的上游交換機(jī)。針對(duì)待保護(hù)鏈路的上游交換機(jī)，配置一個(gè)組表規(guī)則和一個(gè)流表規(guī)則。設(shè)置一個(gè)唯一的組表ID，并在組表規(guī)則第1個(gè)動(dòng)作桶中配置轉(zhuǎn)發(fā)端口為正常的工作轉(zhuǎn)發(fā)端口，發(fā)生故障之前，數(shù)據(jù)都從該端口轉(zhuǎn)發(fā)；在第2 個(gè)動(dòng)作桶中配置轉(zhuǎn)發(fā)端口為備份路徑的轉(zhuǎn)發(fā)端口，故障發(fā)生之后，交換機(jī)進(jìn)行端口切換，為流經(jīng)故障鏈路的數(shù)據(jù)包進(jìn)行VLAN ID 標(biāo)記，然后數(shù)據(jù)從備用端口轉(zhuǎn)發(fā)。另外，對(duì)于流表規(guī)則的配置，其匹配域?yàn)榱鞯脑春湍康闹鳈C(jī)的IP地址，轉(zhuǎn)發(fā)動(dòng)作為轉(zhuǎn)發(fā)到提前配置的組表中。

2）備份路徑上的交換機(jī)。針對(duì)備份路徑上的交換機(jī)，除了2 個(gè)首尾交換機(jī)以外，只需要給其他的交換機(jī)下發(fā)一條流表規(guī)則即可，匹配域?yàn)榇Ｗo(hù)路徑的VLAN ID以及輸入端口號(hào)，轉(zhuǎn)發(fā)動(dòng)作為備份路徑的下一跳交換機(jī)。另外，對(duì)于備份路徑上的最后一個(gè)交換機(jī)（不包括目的交換機(jī)），需要在數(shù)據(jù)轉(zhuǎn)發(fā)之前剝除數(shù)據(jù)包中的VLAN ID，最后將數(shù)據(jù)轉(zhuǎn)發(fā)到目的交換機(jī)。

3.3 算法時(shí)間復(fù)雜度分析

本文用變量k表示需要計(jì)算的最短路徑數(shù)量，m表示被中斷的流的數(shù)量，v表示網(wǎng)絡(luò)拓?fù)渲薪粨Q機(jī)節(jié)點(diǎn)的數(shù)量，n表示網(wǎng)絡(luò)拓?fù)渲羞叺臄?shù)量。在算法1中，KShortestPaths算法的時(shí)間復(fù)雜度為O(kv(n+vlog2v))［24］，路徑可用帶寬計(jì)算時(shí)間復(fù)雜度為O（kn），備份路徑選擇時(shí)間復(fù)雜度為O（km），配置備份路徑轉(zhuǎn)發(fā)規(guī)則時(shí)間復(fù)雜度為O（kv）。綜上所述，ILP-FACAR 算法時(shí)間復(fù)雜度為O(kv(n+vlog2v) +k(n+m+v))。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

為了評(píng)估所提出的FACAR 方案，本文使用支持OpenFlow1.3 的RYU［25］控制器，并使用Mininet［26］來仿真測(cè)試網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，通過使用3 種不同的拓?fù)鋪碓u(píng)估所提出的基于擁塞感知的方案FACAR：圖4中的例子拓?fù)洹⒄鎸?shí)的網(wǎng)絡(luò)拓?fù)銾SNET［27］和挪威骨干網(wǎng)拓?fù)銷orway［28］。

圖4 例子拓?fù)?/p>

網(wǎng)絡(luò)拓?fù)渲兄边B主機(jī)的交換機(jī)稱為邊緣交換機(jī)，在仿真實(shí)驗(yàn)中，每個(gè)邊緣交換機(jī)連接2～3 臺(tái)主機(jī)，鏈路的帶寬統(tǒng)一設(shè)置為50 Mbit/s，利用Iperf 在主機(jī)之間隨機(jī)產(chǎn)生流量，流量帶寬在［4，6］Mbit/s 范圍內(nèi)均勻分布。實(shí)驗(yàn)運(yùn)行環(huán)境為Ubuntu 18.04.6 LTS，Intel Core i7-10700 CPU，2.90 GHz，8 GB內(nèi)存。

4.2 實(shí)驗(yàn)與結(jié)果分析

本節(jié)通過實(shí)驗(yàn)對(duì)本文提出的FACAR 方案進(jìn)行有效性驗(yàn)證，主要包括以下3 個(gè)方面：故障恢復(fù)時(shí)間、負(fù)載平衡性能、備份流表TCAM 資源消耗，并將FACAR與已有的故障恢復(fù)方法進(jìn)行分析對(duì)比。

1）故障恢復(fù)時(shí)間。

首先，評(píng)估FACAR 方案的故障恢復(fù)時(shí)間，將FACAR與目前流行的反應(yīng)式恢復(fù)方案（RRM）［10］和基于路徑保護(hù)的主動(dòng)式恢復(fù)方案（PRM）［11］進(jìn)行比較。為了獲得故障恢復(fù)時(shí)間，隨機(jī)選擇一條鏈路，使用Iperf隨機(jī)生成流經(jīng)該鏈路的流量，然后斷開該鏈路的連接，在目的主機(jī)使用Wireshark［29］工具來進(jìn)行數(shù)據(jù)包的監(jiān)控。故障恢復(fù)時(shí)間使用在鏈路故障之前接收到最后一個(gè)數(shù)據(jù)分組和鏈路故障之后接收到第一個(gè)數(shù)據(jù)分組之間的時(shí)間差。通過改變選擇的鏈路和流的數(shù)量，進(jìn)行20次實(shí)驗(yàn)?zāi)M，最后結(jié)果如圖5所示。

圖5 3個(gè)拓?fù)渲械钠骄收匣謴?fù)時(shí)間

可以看到，隨著網(wǎng)絡(luò)規(guī)模的增大，3 種方法的平均故障恢復(fù)時(shí)間均有所增加，其中，RRM 消耗的時(shí)間最多，是因?yàn)樗欠磻?yīng)式故障恢復(fù)方案，在發(fā)生故障之后，控制器需要重新計(jì)算流的工作路徑，并且網(wǎng)絡(luò)規(guī)模越大，平均故障恢復(fù)時(shí)間就越長。而2 種主動(dòng)式故障恢復(fù)方案FACAR 和PRM 受到網(wǎng)絡(luò)規(guī)模的影響較小，并且故障恢復(fù)時(shí)間遠(yuǎn)遠(yuǎn)小于反應(yīng)式恢復(fù)方案，因?yàn)樗鼈冊(cè)诎l(fā)生故障之后，不需要控制器參與備份路徑的計(jì)算，故障上游交換機(jī)可以直接將受到故障影響的數(shù)據(jù)流切換到備份路徑上。本文提出的FACAR 方案相比PRM 方案平均故障恢復(fù)時(shí)間增加了11.5%、14.3%和13.8%，這是因?yàn)镕ACAR 方案采用擁塞感知的流聚合方法，將故障鏈路上的流量配置到了不同的備份路徑上，因此在交換機(jī)進(jìn)行端口切換時(shí)，所需時(shí)間略微增加，但仍滿足50 ms 內(nèi)的故障恢復(fù)時(shí)間，可以實(shí)現(xiàn)單鏈路故障的快速恢復(fù)。

2）負(fù)載平衡性能。

進(jìn)一步，本文對(duì)FACAR 方案故障恢復(fù)后的負(fù)載平衡性能進(jìn)行評(píng)估。通過2 種主動(dòng)式故障恢復(fù)方案PRM 和Van Adrichem 等人［30］提出的方案（命名為BG）與本文提出的FACAR 進(jìn)行對(duì)比，在網(wǎng)絡(luò)拓?fù)渲胁渴鹆髁?，并選擇負(fù)載最大的鏈路斷開，然后通過比較3 種方案恢復(fù)后的最大鏈路帶寬利用率來評(píng)估負(fù)載平衡性能。

圖6 ～圖8 分別顯示了例子拓?fù)洹SNET 和Norway 這3 個(gè)網(wǎng)絡(luò)拓?fù)渲泄收匣謴?fù)后的最大鏈路利用率?？梢钥闯?，隨著流的數(shù)量增加，PRM 和BG 方法的最大鏈路利用率隨之增加，當(dāng)達(dá)到一定數(shù)量后，恢復(fù)后的網(wǎng)絡(luò)出現(xiàn)了網(wǎng)絡(luò)擁塞。本文中最大鏈路利用率閾值λ設(shè)置為0.8，當(dāng)鏈路利用率大于0.8 時(shí)，就認(rèn)為該鏈路是擁塞的。整體來看，BG 方法的負(fù)載均衡性能優(yōu)于PRM 方法，這是因?yàn)锽G 方法的備份路徑是從故障節(jié)點(diǎn)上游交換機(jī)到目的交換機(jī)，而PRM 方法的備份路徑是一條與原工作路徑不相交的路徑，后者在故障恢復(fù)時(shí)，通常會(huì)影響更多鏈路上的鏈路利用率，而本文提出的FACAR 方案始終保持一個(gè)更優(yōu)的負(fù)載均衡效果。這是因?yàn)镻RM 和BG 只關(guān)心在故障后進(jìn)行中斷流的快速恢復(fù)，而沒有考慮恢復(fù)后網(wǎng)絡(luò)中的潛在擁塞問題，而FACAR 在安裝備份路徑時(shí)，會(huì)將不同的流備份到不同的路徑上，以避免鏈路故障后，通過故障鏈路的流僅能在一條備份路徑上進(jìn)行恢復(fù)。

圖6 例子拓?fù)渲凶畲箧溌防寐?/p>

圖7 USNET中最大鏈路利用率

圖8 Norway中最大鏈路利用率

3）TCAM存儲(chǔ)開銷。

最后，對(duì)FACAR 方案的備份流表TCAM 資源消耗進(jìn)行評(píng)估。在網(wǎng)絡(luò)拓?fù)渲胁渴鹆髁?，并利? 種主動(dòng)式故障恢復(fù)方法PRM、BG和FACAR 提前為鏈路配置備份路徑，然后計(jì)算備份流規(guī)則的數(shù)量。

圖9～圖11 分別顯示了例子拓?fù)?、USNET 和Norway 這3 個(gè)網(wǎng)絡(luò)拓?fù)渲刑崆芭渲玫膫浞萘饕?guī)則的數(shù)量。可以看出，隨著流的數(shù)量增加，3 種方法所需要配置的流規(guī)則的數(shù)量都在增加，其中增長最快的為BG 方法，因?yàn)槠鋫浞萋窂娇紤]的是從每個(gè)工作節(jié)點(diǎn)到目的節(jié)點(diǎn)，因此相比于PRM 的不相交備份路徑和FACAR 的鏈路保護(hù)，BG 方法所需流規(guī)則數(shù)量是最多的。在流的數(shù)量比較少時(shí)，PRM 和FACAR 擁有十分相近的備份流規(guī)則數(shù)量，這是因?yàn)榇藭r(shí)網(wǎng)絡(luò)拓?fù)渲惺艿紽ACAR 保護(hù)的鏈路數(shù)量比較少，需要配置的備份流規(guī)則比較多。當(dāng)FACAR 為更多的鏈路配置了備份路徑之后，只需要給新的流量配置很少的備份流規(guī)則，而PRM 還是需要為每個(gè)流去配置備份路徑，因此隨著流的數(shù)量增加，F(xiàn)ACAR 方案可以更好地節(jié)省TCAM 資源消耗。在流的數(shù)量達(dá)到20 時(shí)，相比于PRM 和BG方案，F(xiàn)ACAR 的備份流規(guī)則數(shù)量平均減少了46.7%和75%。

圖9 例子拓?fù)渲袀浞萘饕?guī)則數(shù)量

圖10 USNET中備份流規(guī)則數(shù)量

圖11 Norway中備份流規(guī)則數(shù)量

5 結(jié)束語

針對(duì)鏈路故障恢復(fù)后可能發(fā)生的擁塞問題和備份路徑TCAM 資源消耗高的問題，本文提出了一種基于流聚合與擁塞避免的SDN 快速故障恢復(fù)方案FACAR。FACAR 方案基于VLAN ID 的流聚合，通過將同一鏈路上的所有流視為一個(gè)或幾個(gè)聚合流，然后為聚合流構(gòu)造受保護(hù)的路徑，這大大減少了備份流表規(guī)則對(duì)存儲(chǔ)資源的占用并確保網(wǎng)絡(luò)鏈路在故障恢復(fù)后不會(huì)發(fā)生擁塞。本文將FACAR 方案形式化表述為一個(gè)整數(shù)線性規(guī)劃問題，以求解最少配置備份轉(zhuǎn)發(fā)規(guī)則的數(shù)量。為此，本文提出了一種基于貪心的啟發(fā)式算法來配置備份轉(zhuǎn)發(fā)規(guī)則。實(shí)驗(yàn)結(jié)果表明，本文提出的FACAR 方案可以實(shí)現(xiàn)電信級(jí)別要求50 ms 內(nèi)的快速恢復(fù)，而且相比于PRM 和BG 方法，F(xiàn)ACAR 方法可以始終保持很好的負(fù)載均衡。在備份流表TCAM 資源消耗上，F(xiàn)ACAR 方法相比于PRM 和BG 方法，備份流規(guī)則數(shù)量平均減少了46.7%和75%。綜上所述，F(xiàn)ACAR 是一種負(fù)載均衡、低存儲(chǔ)開銷的快速故障恢復(fù)方案。