姜厚海，莊 毅，曹子寧

（南京航空航天大學計算機科學與技術學院，江蘇 南京 211106）

0 引 言

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

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

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

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

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

本文主要工作如下：

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

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

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

1 相關工作

在主動式故障恢復和反應式故障恢復方案方面，國內外學者已經(jīng)有了許多的研究成果。

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

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

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

1）快速恢復：FACAR 預先安裝備份路徑，并在故障鏈路的鄰居交換機上結合使用Fast Failover 故障切換功能進行流的重定向，縮短故障恢復時間。

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

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

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

2.1 網(wǎng)絡模型

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

表1 符號列表

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

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

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

表2 鏈路對應的VLAN ID表

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

圖1 正常路由

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

圖2 典型主動故障恢復

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

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

2.3 問題定義

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

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

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

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

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

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

式（6）表示每個被中斷的流都會被分配到一個唯一的備份路徑上，以確保被中斷的流可以正?；謴?。

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

3 ILP-FACAR算法設計

3.1 備份路徑計算

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

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

算法1 的輸入為網(wǎng)絡拓撲、待保護鏈路和待保護鏈路上的流集合，輸出為待保護鏈路提前配置的備份轉發(fā)規(guī)則的數(shù)量。

算法1ILP-FACAR算法。

輸入：網(wǎng)絡拓撲G=（V，E），待保護鏈路l，l上的流集合F。

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

算法1流程描述如下：

1）流排序和拓撲更新。對待保護鏈路上的流按照帶寬大小進行降序排序，并將待保護鏈路從拓撲中去除，然后更新網(wǎng)絡拓撲。

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

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

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

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

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

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

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

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

輸出：對應交換機的流規(guī)則配置。

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

1）待保護鏈路的上游交換機。針對待保護鏈路的上游交換機，配置一個組表規(guī)則和一個流表規(guī)則。設置一個唯一的組表ID，并在組表規(guī)則第1個動作桶中配置轉發(fā)端口為正常的工作轉發(fā)端口，發(fā)生故障之前，數(shù)據(jù)都從該端口轉發(fā)；在第2 個動作桶中配置轉發(fā)端口為備份路徑的轉發(fā)端口，故障發(fā)生之后，交換機進行端口切換，為流經(jīng)故障鏈路的數(shù)據(jù)包進行VLAN ID 標記，然后數(shù)據(jù)從備用端口轉發(fā)。另外，對于流表規(guī)則的配置，其匹配域為流的源和目的主機的IP地址，轉發(fā)動作為轉發(fā)到提前配置的組表中。

2）備份路徑上的交換機。針對備份路徑上的交換機，除了2 個首尾交換機以外，只需要給其他的交換機下發(fā)一條流表規(guī)則即可，匹配域為待保護路徑的VLAN ID以及輸入端口號，轉發(fā)動作為備份路徑的下一跳交換機。另外，對于備份路徑上的最后一個交換機（不包括目的交換機），需要在數(shù)據(jù)轉發(fā)之前剝除數(shù)據(jù)包中的VLAN ID，最后將數(shù)據(jù)轉發(fā)到目的交換機。

3.3 算法時間復雜度分析

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

4 實驗與分析

4.1 實驗環(huán)境設置

為了評估所提出的FACAR 方案，本文使用支持OpenFlow1.3 的RYU［25］控制器，并使用Mininet［26］來仿真測試網(wǎng)絡的拓撲結構，通過使用3 種不同的拓撲來評估所提出的基于擁塞感知的方案FACAR：圖4中的例子拓撲、真實的網(wǎng)絡拓撲USNET［27］和挪威骨干網(wǎng)拓撲Norway［28］。

圖4 例子拓撲

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

4.2 實驗與結果分析

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

1）故障恢復時間。

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

圖5 3個拓撲中的平均故障恢復時間

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

2）負載平衡性能。

進一步，本文對FACAR 方案故障恢復后的負載平衡性能進行評估。通過2 種主動式故障恢復方案PRM 和Van Adrichem 等人［30］提出的方案（命名為BG）與本文提出的FACAR 進行對比，在網(wǎng)絡拓撲中部署流量，并選擇負載最大的鏈路斷開，然后通過比較3 種方案恢復后的最大鏈路帶寬利用率來評估負載平衡性能。

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

圖6 例子拓撲中最大鏈路利用率

圖7 USNET中最大鏈路利用率

圖8 Norway中最大鏈路利用率

3）TCAM存儲開銷。

最后，對FACAR 方案的備份流表TCAM 資源消耗進行評估。在網(wǎng)絡拓撲中部署流量，并利用3 種主動式故障恢復方法PRM、BG和FACAR 提前為鏈路配置備份路徑，然后計算備份流規(guī)則的數(shù)量。

圖9～圖11 分別顯示了例子拓撲、USNET 和Norway 這3 個網(wǎng)絡拓撲中提前配置的備份流規(guī)則的數(shù)量?？梢钥闯觯S著流的數(shù)量增加，3 種方法所需要配置的流規(guī)則的數(shù)量都在增加，其中增長最快的為BG 方法，因為其備份路徑考慮的是從每個工作節(jié)點到目的節(jié)點，因此相比于PRM 的不相交備份路徑和FACAR 的鏈路保護，BG 方法所需流規(guī)則數(shù)量是最多的。在流的數(shù)量比較少時，PRM 和FACAR 擁有十分相近的備份流規(guī)則數(shù)量，這是因為此時網(wǎng)絡拓撲中受到FACAR 保護的鏈路數(shù)量比較少，需要配置的備份流規(guī)則比較多。當FACAR 為更多的鏈路配置了備份路徑之后，只需要給新的流量配置很少的備份流規(guī)則，而PRM 還是需要為每個流去配置備份路徑，因此隨著流的數(shù)量增加，F(xiàn)ACAR 方案可以更好地節(jié)省TCAM 資源消耗。在流的數(shù)量達到20 時，相比于PRM 和BG方案，F(xiàn)ACAR 的備份流規(guī)則數(shù)量平均減少了46.7%和75%。

圖9 例子拓撲中備份流規(guī)則數(shù)量

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

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

5 結束語

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