面向軟件定義車聯網的鏈路故障快速恢復方法

顧源，張震，段通

（1.戰略支援部隊信息工程大學 信息技術研究所，鄭州 450002；2.國家數字交換系統工程技術研究中心，鄭州 450002）

0 引言

車聯網（Internet of Vehicles，IoV）是智能交通系統的重要組成部分，通過車聯網與路側基礎設施進行信息交換，可為車輛提供輔助駕駛、異常提醒、躲避擁堵等多種服務信息；但緊耦合的網絡設備操作方式以及對可擴展性、靈活性、可靠性需求的增長導致傳統車聯網難以滿足未來網絡的發展需求［1］。軟件定義網絡（Software Defined Network，SDN）作為一種新型網絡結構，通過三層架構實現了控制平面與數據平面的分離［2］，并由控制平面的控制器實現網絡控制［3］，滿足了車輛的連通性和通信需求［4］，同時具有加入蜂窩網絡和車聯網的潛力［5］。軟件定義車聯網（Software-Defined Internet of Vehicles，SDIV）架構［6］支持車聯網開放統一的接口，數據層與控制層的分開和邏輯上的集中控制使SDIV 架構具有很高的可擴展性和網絡可管理性，如圖1 所示。

圖1 SDIV的三層架構Fig.1 Three-layer architecture of SDIV

圖2 中的車路協同通信是車聯網中一種典型的實時查詢類通信場景，在這種場景下車聯網需與路側基礎設施進行V2I（Vehicle to Infrastructure）通信，從路側的信息服務器（Information Server，IS）中獲取實時道路導航、充電設施位置、交通擁堵等信息。路側單元（RoadSide Unit，RSU）通過無線信道與車聯網相連，同時通過路由器與IS 相連，從而將車聯網所請求的數據信息從IS 發送至車聯網。在SDIV 架構中，RSU 和IS 之間的路由器均為SDN 交換機，而從IS 到RSU 之間的數據流量傳輸路徑也被SDN 控制器所控制，因此具有較高的靈活性。然而，當RSU 與IS 之間的通信系統發生鏈路故障時，SDN 控制器需要根據實時網絡狀態更新交換機的流表規則，以快速恢復傳輸。同時，此類場景中車輛的快速移動特性以及所連RSU 潛在的切換特性需要快速的故障恢復能力，以保持車聯網的服務質量，最終滿足用戶需求。

圖2 實時查詢類通信場景Fig.2 Real-time query communication scenario

對于鏈路故障恢復問題，文獻［7-10］中提前安裝了備份路徑的轉發規則。當鏈路出現故障時，數據平面交換機自動激活備份路徑，在提前配置備份路徑的轉發規則方案中，不涉及SDN 控制器，因此能夠快速地從鏈路故障中恢復。但工作路徑和備份路徑相關，每次改變工作路徑時，都需要重新分配備份路徑，因此容易導致交換機和鏈路帶寬資源耗盡，并不適用于車聯網場景中復雜且動態變化的網絡環境。

文獻［11］中提出了一種基于最短路徑優先算法的響應式鏈路故障恢復方法。該方法將每條路徑上的報文分為高優先級和低優先級，保證了高優先級數據包的最小延遲，還通過在可用路徑上平均分配流量以避免擁塞。因此，隨著網絡規模的擴大，該方法的復雜度也隨之增加。該方法的另一個缺點是為實現機制提供的信息不足；此外，還沒有在標準的互聯網拓撲數據集上進行測試。文獻［12］中表示忽略流表處理時間的基于最短路徑恢復可能無法快速恢復流表時延。

根據文獻［13-14］的研究，SDN 交換機中插入一條流表的延遲為0.5～10 ms。文獻［15-16］中關注了恢復過程中的流表處理時間，考慮了異構網絡中節點具有不同規格的路徑交換延遲問題，并基于處理時間最短的交換機選擇備選路徑。文獻［17］中提出一種考慮恢復過程中的交換機流表處理時間和網絡帶寬的方法。文獻［18］中提出基于社區檢測的方法和基于路徑解剖的方法。文獻［19］中在替代路徑選擇時，鼓勵選擇具有更好的鏈路質量和最小的關鍵交換機數量的路徑。文獻［15-19］考慮了流表更新時延，但沒有綜合考慮路徑開銷和流表更新權衡問題，其中文獻［15-17］從降低每個交換機處理時間的角度，降低恢復時延；文獻［18-19］從減少路徑恢復過程中流表更新數量的角度，降低恢復時延。文獻［20］中考慮了路徑開銷和流表更新權衡問題，并在一定條件下找到最優解和次優解，但沒有將路徑開銷和流表更新次數統一為時間標準后進行權衡，并且只能在系數特定的情況下求解。

基于以上研究現狀，為解決軟件定義車聯網實時查詢類通信場景中的單鏈路障恢復問題，本文引入恢復過程時延和恢復之后路徑傳輸時延作為鏈路參數，并設計相應的路徑恢復方案。本文的主要工作有：1）對故障恢復時延建模，綜合考慮恢復過程時延和恢復之后路徑開銷這兩個關鍵性能指標：2）在流表更新時延可以忽略和流表更新時延不可忽略的情況下，分別提出兩種路徑恢復算法，理論分析和實驗結果表明，本文算法具有較小的計算時延和故障恢復時延。

1 問題描述與模型構建

1.1 問題描述

SDIV 架構下鏈路故障恢復機制的優劣主要由以下性能指標評估：1）恢復過程的時延開銷trecovery，由故障發現時延tdiscovery、openflow 消息通道時延topenflow（包括packet-in 消息上傳及packet-out 消息的下發等）、路徑計算時延tcompute和流表更新時延tupdate構成。其中：tdiscovery和topenflow由通信系統本身的性能決定，無法優化；tupdate則由舊路徑切換到新路徑所需要的流表規則增刪操作次數決定。2）恢復之后的路徑傳輸時延tnewpath，一般由路徑的端到端時延所定義，以實現最小的新路徑傳輸時延。因此在求解鏈路故障恢復問題時，tcompute、tupdate、tnewpath可以優化，且tupdate和tnewpath可以參數化。本文首先將tupdate和tnewpath參數化，并統一到鏈路故障恢復的優化目標中；其次，在求解優化問題的過程中，在最小化tupdate和tnewpath的同時考慮tcompute，尋找統籌上述關鍵性能指標的最優解。

圖3 SDIV架構下鏈路故障恢復機制時延Fig.3 Delay of link faulure recovery mechanism under SDIV architecture

1.2 模型構建

網絡拓撲結構表示為G=(V，E)，其中：V={vi}表示拓撲中的節點集合，vs為路徑上的源節點，vt為路徑上的目的節點；E={ei，j}表示拓撲中的鏈路集合，ei，j表示節點vi和vj之間的邊，efailure表示故障鏈路。Pold={xi，j}定義為拓撲中一系列連續節點組成的舊路徑，本文假設該路徑為一條不包含環路的簡單路徑，每個xi，j為該路徑中相鄰節點vi、vj組成的一段鏈路，其中：xi，j=1 表示路徑經過ei，j；xi，j=0 表示路徑不經過ei，j。對恢復傳輸后的新路徑定義為Pnew={yi，j}，假設該路徑為一條不包含環路的簡單路徑，每個yi，j為該路徑中相鄰節點vi、vj組成的一段鏈路，其中：yi，j=1 表示路徑經過ei，j；yi，j=0 表示路 徑不經過ei，j。用{ci，j}表示鏈 路傳輸時延，新路徑Pnew={yi，j}的路徑傳輸時延為

圖4 是一個含有7 個節點的拓撲，除c2，7=c7，4=2 外，剩余邊的鏈路傳輸時延均為1。如果原傳輸路徑為P1：1-2-3-4，在鏈路e2，3發生故障時，需要重新選擇路徑恢復傳輸，備選路徑有P2：1-2-5-6-4 和P3：1-2-7-4。P2 和P3 的路徑傳輸時延可以由計算得出，分別是4 和5。

圖4 SDIV架構下鏈路故障恢復示例Fig.4 Example of link failure recovery under SDIV architecture

路徑Pold上存在一段故障鏈路efailure。由于tdiscovery、topenflow均由通信系統本身性能決定，無法優化，對于trecovery，主要考慮tupdate。在路徑切換時，相應的SDN 交換機需要在流表中增添或刪除流條目，此類操作的總數是流表規則更新次數。tupdate由舊路徑Pold切換到新路徑Pnew所需要的流表規則更新次數決定。

其中：xi，j表示去掉故障鏈路efailure后，舊路徑中包含的邊數量；wi，jyi，j表示去掉故障鏈路efailure后，新路徑中的每個邊如果與舊路徑中的邊相同就減1，如果與舊路徑中的邊不相同則加1，相當于對兩條路徑上不同邊的數量進行統計。

由于式（1）中第1 項由舊路徑中包含鏈路的數量決定，在備選新路徑比較中固定不變，在求解優化問題過程中可將xi，j項去掉，有：

tupdate為更新次數與每次更新所需時間乘積，用tope表示一次流表更新的時間開銷，tupdate可表示為：

圖4 中拓撲原傳輸路徑為P1：1-2-3-4，在鏈路e2，3發生故障時，需要重新選擇路徑恢復傳輸，備選路徑有P2：1-2-5-6-4 和P3：1-2-7-4。如果選擇P2，需要將經過e2，5、e4，6、e6，4的流表條目添加到對應節點的流表中，此外還要刪除穿過e3，4的流表對應條目，因此需要4 次流表更新，由式（1）也可算出P2 的流表規則操作次數Cope_nonop=4，在后續優化問題過程中，按式（2）將xi，j項去掉后Cope=2。如果選擇P3，則需將經過e2，7、e7，4的流表條目分別添加到節點v2和v7的流表中，并且刪除節點v3中e3，4對應的流表條目，因此需要3 次流表操作，去掉xi，j項后Cope=1。因此P2 的流表更新時延為tupdate=2tope，P3 的流表更新時延為tupdate=tope。

在SDIV 鏈路故障恢復求解過程中，要找到一條總時延開銷最低的路徑，需要滿足min(tupdate+tnewpath)。新路徑Pnew={yi，j}應為一條沒有環路的簡單路徑，并且需要滿足流表的連通性或守恒條件，即：

其中：bi是拓撲中從節點vi的流出，表征流存在狀態。對于從源節點vs到目的節點vt之間的流，有：

綜上，為統籌恢復過程的時延開銷和恢復之后的路徑時延開銷，本文將SDIV 鏈路故障恢復問題（SDIV Link Fault Recovery Problem，SLFRP）描述如下：

圖4 拓撲在原傳輸路徑P1：1-2-3-4 中鏈路e2，3發生故障的情況下，備選路徑P2 的時延開銷為tP2=tupdate+tnewpath=4+2tope，備選路徑P3 的時延開銷為tP3=tupdate+tnewpath=5 +tope，對于該拓撲，只需比較tP2和tP3，選擇總時延最小的路徑作為新路徑即可。

2 故障快速恢復算法

由式（6）可以看出，SLFRP 本質上是在邊權值為wi，jtope+ci，j的新拓撲中求解最短路徑，可通過Dijkstra 算法等最短路徑算法求解。然而，重新運行Dijkstra 算法計算最短路徑的復雜度O(N2)偏高，會導致tcompute過大。由于邊權值的改變，先前構建的原始最短路徑的計算結果又似乎難以復用。為此，本文分析SLFRP 和先前構建的原始最短路徑之間的聯系，力圖最大化復用已有計算結果，提出基于拓撲劃分的路徑恢復算法（Path Recovery Algorithm based on Topology Partition，PRA-TP）和基于單鏈路搜索的路徑恢復算法（Path Recovery Algorithm based on Single Link Search，PRA-SLS）：在流表更新時延tupdate相較于tnewpath不可被忽略的情況下，PRATP 復用鏈路故障產生的兩個子樹節點集合，降低了計算復雜度；在流表更新時延tupdate可被忽略時，PRA-SLS 復用鏈路故障產生的兩個子樹路徑集合，降低了計算復雜度。

2.1 基于拓撲劃分的路徑恢復算法

對于流表更新時延tupdate相較于tnewpath不可被忽略情況下的SLFRP，故障鏈路中斷后，拓撲鏈路權值為wi，jtope+ci，j，與原權值相比發生變化。對于這種情況，PRA-TP 通過復用故障鏈路劃分的原最短路徑生成樹的兩個子樹中節點集合求解問題。在鏈路故障恢復場景中，當以vs和vt為源點和目的點的路徑Pold={xi，j}中的某條鏈路發生故障時，需要找到一條以vs和vt為源點和目的點的新路徑Pnew={yi，j}。Told為鏈路故障前以源點vs為根節點的原最短路徑生成樹，Pold在Told上，表示源點vs到目的節點vt的原最短路徑，Pnew表示恢復傳輸后的新最短路徑。在Pold中選擇某鏈路efailure作為故障鏈路，將故障鏈路efailure從Told中移除，Told被分割成兩個子樹Told_s和Told_t，分別包含源點vs和目的點vt。假設vi為Told_s中的某節點，vj為Told_t中的某節點。ei，j為一條鏈路，頭節點為vi，尾節點為vj，且ei，j∈Eefailure，滿足上述條件的所有ei，j的集合表示為L，即：

用dis_to_vs(i)表示vs到vi的距離，distance(i，j)表示邊ei，j的距離，dis_to_vt(j)表示vj到vt的距離。當且僅 當dis_to_vs(i)、Cost(i，j)、dis_to_vt(j)之和最小的時候鏈路ei，j在最短路徑上，即ei，j∈Pnew當且僅當：

當故障鏈路efailure從Told中移除時，點集V={vi}被分割成點集Vs和點集Vt，其中Vs包含Told_s中全部節點，Vt包含Told_t中全部節點，顯然vs∈Vs，vt∈Vt。對于Vs中任意節點vi，存在一條vi到vs的最短路徑，該路徑中不包含Vt中節點；對于Vt中任意節點vj，也存在一條vj到vt的最短路徑，該路徑中不包含Vs中節點。在計算Pnew時，對原拓撲G=(V，E)刪除故障鏈路，只保留點集Vs中的節點和首尾節點均在點集Vs中的鏈路，得到拓撲Gs=(Vs，Es)，對Gs以vs為根節點生成最短路徑樹Tnew_s，而后對原拓撲G=(V，E)刪除故障鏈路，只保留首尾節點均在Vt中的鏈路和節點，得到Gt=(Vt，Et)，并以vt為根節點生成最短路徑樹Tnew_t，再遍歷L中所有ei，j，計 算dis_to_vs(i)、Cost(i，j)、dis_to_vt(j)之和并比較結果，最小的值即為新最短路徑。

圖4 拓撲中，v1為源點vs，v4為目的點vt，原傳輸路徑Pold：1-2-3-4，故障鏈路為e2，3，原最短路徑生成樹Told以及被故障鏈路劃分的子樹Told_s和Told_t如圖5（a）所示。點集Vs={v1，v2，v5，v6，v7}，點集Vt={v3，v4}，集合L={e6，4，e7，4}。在原拓撲中只保留首尾節點均在Vs中的鏈路，拓撲中剩余點為點集Vs，剩余邊為{e1，2，e2，5，e5，6，e2，7}，生成最短路徑樹Tnew_s。在原拓撲中只保留首尾節點均在Vt中的鏈路，拓撲中剩余點為點集Vt，剩余邊為{e3，4}，對其生成最短路徑樹Tnew_t，Tnew_s和Tnew_t如圖5（b）所示，而后遍歷集合L={e6，4，e7，4}中ei，j，其中：e6，4的時延 為dis_to_vs(6)+distance(6，4)+dis_to_vt(4)=4+2tope，e7，4的時延為dis_to_vs(7)+distance(7，4) +dis_to_vt(4)=5 +tope，二者中更小的即為最短路徑。

圖5 最短路徑樹劃分Fig.5 Shortest path tree partition

為便于描述算法，定義如下操作。

Cost(G)：計算拓撲G中鏈路權重。

Divide(Told，efailure，Told_s，Told_t)：將故障鏈路efailure從Told移除后，分割出兩個子樹，包含源點vs的子樹為Told_s，包含目的點vt的子樹為Told_t。

Distance(T，i)：找到最短路徑生成樹T上，點vi到根節點的距離。

Path(T，i)：返回最短路徑生成樹T上，點vi到根節點的路徑。

CpyNodes(V，G)：拓撲G中所有的點復制到V中。

Relax(i，Cost(ei，j)，j)：遍歷L中的ei，j，找到使Distance(Tnew_s，i)、Cost(ei，j)、Distance(Tnew_t，j)之和最 小的i和j。

2.2 基于單鏈路搜索的路徑恢復算法

對于流表更新時延遠小于路徑傳輸時延情況下的SDIV鏈路故障恢復問題，PRA-SLS 通過復用故障鏈路劃分產生的兩個子樹的路徑集合求解問題。對忽略流表更新時延的SLFRP 可以描述如下：

由于忽略流表更新時延tope，拓撲Gs=(Vs，Es)上的鏈路參數與原拓撲G=(V，E)相比沒有發生變化，拓撲Gs上的最短路徑生成樹也沒有變化，Tnew_s可以直接由原最短路徑樹得出，即Tnew_s=Told_s。對Gt=(Vt，Et)，以vt為根節點生成最短路徑樹Tnew_t，而后遍歷L中所有ei，j，計 算dis_to_vs(i) +Cost(i，j)+dis_to_vt(j)結果并比較，其中值最小的即為新的最短路徑。

2.3 算法時間復雜度分析

假設拓撲G中去掉故障鏈路后有N條鏈路，用故障鏈路劃分拓撲和原最短路徑樹后，Gt中有M條鏈路，集合L中有K條鏈路。PRA-TP 中步驟的時間開銷主要有：1）遍歷拓撲G劃分Gs、Gt和集合L，時間復雜度為O(N)；2）Dijkstra(Gs)的時間復雜度為O((N-M-K)2)；3）Dijkstra(Gt)的時間復雜度為O(M2)；4）遍歷集合L的時間復雜度為O(K)，PRA-TP 的時間復雜度為O((N-M-K)2+M2)，略小于Dijkstra 算法，當Gs和Gt中鏈路數量相同時，時間開銷最小。PRA-SLS 時間開銷主要有：1）遍歷拓撲G，劃分Gs、Gt和集合L，時間復雜度為O(N)；2）Dijkstra (Gt)的時間復雜度為O(M2)；3）遍歷集合L的時間復雜度為O(K)。PRA-SLS 時間復雜度為O(M2)。

3 實驗與結果分析

通過比較算法計算時延和路徑恢復時延，評估路徑恢復方案。選取SNDlib［21］和topology zoo［22］中的不同拓撲進行實驗，拓撲結構描述如表1 所示。

表1 拓撲結構Tab.1 Topology structure

首先比較算法計算時延，實驗環境為Intel Core i7-8700、3.20 GHz、32 GB RAM，Windows 7 操作系統。選擇Dijkstra算法與PRA-TP、PRA-SLS 進行比較。隨機選擇路徑并設置單鏈路故障，由于拓撲較小，為使測量時間更準確，分別對3種算法重復100 次實驗，得到平均算法計算時延。實驗結果如圖6 所示，隨著拓撲規模增大，3 種算法的平均計算時延均隨之增加，其中Dijkstra 算法的平均計算時延最高。相較于Dijkstra 算法，PRA-TP 的平均計算時延降低了25%，PRA-SLS的平均計算時延降低了60%。雖然PRA-TP 需要兩次最短路徑計算，但每次被計算的拓撲均為分割后的拓撲，規模較小，因此整體時延較低；PRA-SLS 只需對一部分拓撲做一次計算，減小了時間開銷，因此時延最低。

圖6 算法計算時延對比Fig.6 Comparison of algorithm calculation delay

在PRA-TP、PRA-SLS 中，不同位置的故障鏈路切割出不同大小的Gs和Gt，會導致計算時延發生變化。在拓撲ta2 和拓撲Gts Ce 中，隨機選擇路徑并設置單鏈路故障，使故障鏈路切割出不同大小的Gs，選擇Dijkstra 算法與PRA-TP、PRA-SLS 進行比較，結果如圖7、8 所示，橫軸 |Es|表示Gs中邊的數量，縱軸為計算時延。實驗結果表明，不同的故障鏈路位置對Dijkstra 算法的時延沒有影響。對于PRA-TP，在Gs中邊的數量極小和接近原拓撲 |E|時，它的計算時延和Dijkstra算法計算時延基本相等；在Gs中邊的數量接近原拓撲中邊的數量一半時，PRA-TP 計算時延最低，相較于Dijkstra 算法相比，計算時延減小了接近一半。對于PRA-SLS，計算時延隨著Gs中邊的數量增多而不斷降低，在Gs中邊的數量接近原拓撲時，PRA-SLS 的計算時延最低，因為PRA-SLS 只需要對Gt進行遍歷，Gt規模越小，時間開銷越小。

圖7 ta2拓撲結構和計算時延Fig.7 ta2 topology structure and calculation delay

為比較路徑恢復時延時，在Mininet 仿真平臺上搭建拓撲ta2，隨機選擇路徑并設置單鏈路故障，使故障鏈路在距離源節點不同位置處，由Ryu 控制器完成鏈路故障檢測、路徑選擇及流表下發。選擇Dijkstra 算法與PRA-TP 進行對比，實驗結果如圖9 所示。實驗結果表明采用了PRA-TP 的恢復時延更短，相較于Dijkstra 算法，PRA-TP 的平均路徑恢復時延降低了40%。這是由于路徑恢復時延主要由故障發現時延、openflow 消息通道時延、算法計算時延和流表更新時延構成。由于實驗中故障發現時延、openflow 消息通道時延相同，同一路徑上的同一處鏈路故障，故障恢復時所需的流表更新時間也一致，因此計算時延更小的算法，恢復時延更短。此外，在拓撲ta2 中，不同位置的鏈路故障，在路徑恢復時，流表更新次數不同，具有不同的流表更新時延，不同的流表更新時延也會影響路徑恢復時延。

圖8 Cts Ce拓撲結構和計算時延Fig.8 Cts Ce topology structure and calculation delay

圖9 路徑恢復時延對比Fig.9 Comparison of path recovery delay

4 結語

本文針對SDIV 架構中車-路實時查詢類通信場景中的單鏈路故障問題，同時考慮恢復過程時延和路徑傳輸時延作為鏈路參數，對單鏈路故障恢復問題中的恢復時延進行建模，而后提出了基于拓撲劃分的路徑恢復算法（PRA-TP）和基于單鏈路搜索的路徑恢復算法（PRA-SLS）。實驗結果表明，本文綜合考慮恢復過程時延和路徑傳輸時延的方法以及兩種算法能有效降低算法計算時延和路徑恢復時延。對于PRA-SLS，故障鏈路位置越接近目的節點，算法計算時延越低，相較于Dijkstra 算法，PRA-SLS 的平均計算時延降低了60%；對于PRA-TP，故障位置劃分的兩個子樹節點數目相近時，算法計算時延和路徑恢復時延最低，相較于Dijkstra 算法，平均計算時延降低了25%，平均路徑恢復時延降低了40%。但本文僅考慮了單鏈路故障的問題，無法應對多鏈路故障的情景，在下一步工作中，將研究多鏈路故障情況下的解決方案。