顧源，張震，段通

（1.戰(zhàn)略支援部隊(duì)信息工程大學(xué) 信息技術(shù)研究所，鄭州 450002；2.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002）

0 引言

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

圖1 SDIV的三層架構(gòu)Fig.1 Three-layer architecture of SDIV

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

圖2 實(shí)時(shí)查詢類通信場(chǎng)景Fig.2 Real-time query communication scenario

對(duì)于鏈路故障恢復(fù)問題，文獻(xiàn)［7-10］中提前安裝了備份路徑的轉(zhuǎn)發(fā)規(guī)則。當(dāng)鏈路出現(xiàn)故障時(shí)，數(shù)據(jù)平面交換機(jī)自動(dòng)激活備份路徑，在提前配置備份路徑的轉(zhuǎn)發(fā)規(guī)則方案中，不涉及SDN 控制器，因此能夠快速地從鏈路故障中恢復(fù)。但工作路徑和備份路徑相關(guān)，每次改變工作路徑時(shí)，都需要重新分配備份路徑，因此容易導(dǎo)致交換機(jī)和鏈路帶寬資源耗盡，并不適用于車聯(lián)網(wǎng)場(chǎng)景中復(fù)雜且動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境。

文獻(xiàn)［11］中提出了一種基于最短路徑優(yōu)先算法的響應(yīng)式鏈路故障恢復(fù)方法。該方法將每條路徑上的報(bào)文分為高優(yōu)先級(jí)和低優(yōu)先級(jí)，保證了高優(yōu)先級(jí)數(shù)據(jù)包的最小延遲，還通過在可用路徑上平均分配流量以避免擁塞。因此，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，該方法的復(fù)雜度也隨之增加。該方法的另一個(gè)缺點(diǎn)是為實(shí)現(xiàn)機(jī)制提供的信息不足；此外，還沒有在標(biāo)準(zhǔn)的互聯(lián)網(wǎng)拓?fù)鋽?shù)據(jù)集上進(jìn)行測(cè)試。文獻(xiàn)［12］中表示忽略流表處理時(shí)間的基于最短路徑恢復(fù)可能無法快速恢復(fù)流表時(shí)延。

根據(jù)文獻(xiàn)［13-14］的研究，SDN 交換機(jī)中插入一條流表的延遲為0.5～10 ms。文獻(xiàn)［15-16］中關(guān)注了恢復(fù)過程中的流表處理時(shí)間，考慮了異構(gòu)網(wǎng)絡(luò)中節(jié)點(diǎn)具有不同規(guī)格的路徑交換延遲問題，并基于處理時(shí)間最短的交換機(jī)選擇備選路徑。文獻(xiàn)［17］中提出一種考慮恢復(fù)過程中的交換機(jī)流表處理時(shí)間和網(wǎng)絡(luò)帶寬的方法。文獻(xiàn)［18］中提出基于社區(qū)檢測(cè)的方法和基于路徑解剖的方法。文獻(xiàn)［19］中在替代路徑選擇時(shí)，鼓勵(lì)選擇具有更好的鏈路質(zhì)量和最小的關(guān)鍵交換機(jī)數(shù)量的路徑。文獻(xiàn)［15-19］考慮了流表更新時(shí)延，但沒有綜合考慮路徑開銷和流表更新權(quán)衡問題，其中文獻(xiàn)［15-17］從降低每個(gè)交換機(jī)處理時(shí)間的角度，降低恢復(fù)時(shí)延；文獻(xiàn)［18-19］從減少路徑恢復(fù)過程中流表更新數(shù)量的角度，降低恢復(fù)時(shí)延。文獻(xiàn)［20］中考慮了路徑開銷和流表更新權(quán)衡問題，并在一定條件下找到最優(yōu)解和次優(yōu)解，但沒有將路徑開銷和流表更新次數(shù)統(tǒng)一為時(shí)間標(biāo)準(zhǔn)后進(jìn)行權(quán)衡，并且只能在系數(shù)特定的情況下求解。

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

1 問題描述與模型構(gòu)建

1.1 問題描述

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

圖3 SDIV架構(gòu)下鏈路故障恢復(fù)機(jī)制時(shí)延Fig.3 Delay of link faulure recovery mechanism under SDIV architecture

1.2 模型構(gòu)建

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)表示為G=(V，E)，其中：V={vi}表示拓?fù)渲械墓?jié)點(diǎn)集合，vs為路徑上的源節(jié)點(diǎn)，vt為路徑上的目的節(jié)點(diǎn)；E={ei，j}表示拓?fù)渲械逆溌芳希琫i，j表示節(jié)點(diǎn)vi和vj之間的邊，efailure表示故障鏈路。Pold={xi，j}定義為拓?fù)渲幸幌盗羞B續(xù)節(jié)點(diǎn)組成的舊路徑，本文假設(shè)該路徑為一條不包含環(huán)路的簡單路徑，每個(gè)xi，j為該路徑中相鄰節(jié)點(diǎn)vi、vj組成的一段鏈路，其中：xi，j=1 表示路徑經(jīng)過ei，j；xi，j=0 表示路徑不經(jīng)過ei，j。對(duì)恢復(fù)傳輸后的新路徑定義為Pnew={yi，j}，假設(shè)該路徑為一條不包含環(huán)路的簡單路徑，每個(gè)yi，j為該路徑中相鄰節(jié)點(diǎn)vi、vj組成的一段鏈路，其中：yi，j=1 表示路徑經(jīng)過ei，j；yi，j=0 表示路 徑不經(jīng)過ei，j。用{ci，j}表示鏈 路傳輸時(shí)延，新路徑Pnew={yi，j}的路徑傳輸時(shí)延為

圖4 是一個(gè)含有7 個(gè)節(jié)點(diǎn)的拓?fù)?，除c2，7=c7，4=2 外，剩余邊的鏈路傳輸時(shí)延均為1。如果原傳輸路徑為P1：1-2-3-4，在鏈路e2，3發(fā)生故障時(shí)，需要重新選擇路徑恢復(fù)傳輸，備選路徑有P2：1-2-5-6-4 和P3：1-2-7-4。P2 和P3 的路徑傳輸時(shí)延可以由計(jì)算得出，分別是4 和5。

圖4 SDIV架構(gòu)下鏈路故障恢復(fù)示例Fig.4 Example of link failure recovery under SDIV architecture

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

其中：xi，j表示去掉故障鏈路efailure后，舊路徑中包含的邊數(shù)量；wi，jyi，j表示去掉故障鏈路efailure后，新路徑中的每個(gè)邊如果與舊路徑中的邊相同就減1，如果與舊路徑中的邊不相同則加1，相當(dāng)于對(duì)兩條路徑上不同邊的數(shù)量進(jìn)行統(tǒng)計(jì)。

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

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

圖4 中拓?fù)湓瓊鬏斅窂綖镻1：1-2-3-4，在鏈路e2，3發(fā)生故障時(shí)，需要重新選擇路徑恢復(fù)傳輸，備選路徑有P2：1-2-5-6-4 和P3：1-2-7-4。如果選擇P2，需要將經(jīng)過e2，5、e4，6、e6，4的流表?xiàng)l目添加到對(duì)應(yīng)節(jié)點(diǎn)的流表中，此外還要?jiǎng)h除穿過e3，4的流表對(duì)應(yīng)條目，因此需要4 次流表更新，由式（1）也可算出P2 的流表規(guī)則操作次數(shù)Cope_nonop=4，在后續(xù)優(yōu)化問題過程中，按式（2）將xi，j項(xiàng)去掉后Cope=2。如果選擇P3，則需將經(jīng)過e2，7、e7，4的流表?xiàng)l目分別添加到節(jié)點(diǎn)v2和v7的流表中，并且刪除節(jié)點(diǎn)v3中e3，4對(duì)應(yīng)的流表?xiàng)l目，因此需要3 次流表操作，去掉xi，j項(xiàng)后Cope=1。因此P2 的流表更新時(shí)延為tupdate=2tope，P3 的流表更新時(shí)延為tupdate=tope。

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

其中：bi是拓?fù)渲袕墓?jié)點(diǎn)vi的流出，表征流存在狀態(tài)。對(duì)于從源節(jié)點(diǎn)vs到目的節(jié)點(diǎn)vt之間的流，有：

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

圖4 拓?fù)湓谠瓊鬏斅窂絇1：1-2-3-4 中鏈路e2，3發(fā)生故障的情況下，備選路徑P2 的時(shí)延開銷為tP2=tupdate+tnewpath=4+2tope，備選路徑P3 的時(shí)延開銷為tP3=tupdate+tnewpath=5 +tope，對(duì)于該拓?fù)洌恍璞容^tP2和tP3，選擇總時(shí)延最小的路徑作為新路徑即可。

2 故障快速恢復(fù)算法

由式（6）可以看出，SLFRP 本質(zhì)上是在邊權(quán)值為wi，jtope+ci，j的新拓?fù)渲星蠼庾疃搪窂?，可通過Dijkstra 算法等最短路徑算法求解。然而，重新運(yùn)行Dijkstra 算法計(jì)算最短路徑的復(fù)雜度O(N2)偏高，會(huì)導(dǎo)致tcompute過大。由于邊權(quán)值的改變，先前構(gòu)建的原始最短路徑的計(jì)算結(jié)果又似乎難以復(fù)用。為此，本文分析SLFRP 和先前構(gòu)建的原始最短路徑之間的聯(lián)系，力圖最大化復(fù)用已有計(jì)算結(jié)果，提出基于拓?fù)鋭澐值穆窂交謴?fù)算法（Path Recovery Algorithm based on Topology Partition，PRA-TP）和基于單鏈路搜索的路徑恢復(fù)算法（Path Recovery Algorithm based on Single Link Search，PRA-SLS）：在流表更新時(shí)延tupdate相較于tnewpath不可被忽略的情況下，PRATP 復(fù)用鏈路故障產(chǎn)生的兩個(gè)子樹節(jié)點(diǎn)集合，降低了計(jì)算復(fù)雜度；在流表更新時(shí)延tupdate可被忽略時(shí)，PRA-SLS 復(fù)用鏈路故障產(chǎn)生的兩個(gè)子樹路徑集合，降低了計(jì)算復(fù)雜度。

2.1 基于拓?fù)鋭澐值穆窂交謴?fù)算法

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

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

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

圖4 拓?fù)渲?，v1為源點(diǎn)vs，v4為目的點(diǎn)vt，原傳輸路徑Pold：1-2-3-4，故障鏈路為e2，3，原最短路徑生成樹Told以及被故障鏈路劃分的子樹Told_s和Told_t如圖5（a）所示。點(diǎn)集Vs={v1，v2，v5，v6，v7}，點(diǎn)集Vt={v3，v4}，集合L={e6，4，e7，4}。在原拓?fù)渲兄槐Ａ羰孜补?jié)點(diǎn)均在Vs中的鏈路，拓?fù)渲惺Ｓ帱c(diǎn)為點(diǎn)集Vs，剩余邊為{e1，2，e2，5，e5，6，e2，7}，生成最短路徑樹Tnew_s。在原拓?fù)渲兄槐Ａ羰孜补?jié)點(diǎn)均在Vt中的鏈路，拓?fù)渲惺Ｓ帱c(diǎn)為點(diǎn)集Vt，剩余邊為{e3，4}，對(duì)其生成最短路徑樹Tnew_t，Tnew_s和Tnew_t如圖5（b）所示，而后遍歷集合L={e6，4，e7，4}中ei，j，其中：e6，4的時(shí)延 為dis_to_vs(6)+distance(6，4)+dis_to_vt(4)=4+2tope，e7，4的時(shí)延為dis_to_vs(7)+distance(7，4) +dis_to_vt(4)=5 +tope，二者中更小的即為最短路徑。

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

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

Cost(G)：計(jì)算拓?fù)銰中鏈路權(quán)重。

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

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

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

CpyNodes(V，G)：拓?fù)銰中所有的點(diǎn)復(fù)制到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 基于單鏈路搜索的路徑恢復(fù)算法

對(duì)于流表更新時(shí)延遠(yuǎn)小于路徑傳輸時(shí)延情況下的SDIV鏈路故障恢復(fù)問題，PRA-SLS 通過復(fù)用故障鏈路劃分產(chǎn)生的兩個(gè)子樹的路徑集合求解問題。對(duì)忽略流表更新時(shí)延的SLFRP 可以描述如下：

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

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

假設(shè)拓?fù)銰中去掉故障鏈路后有N條鏈路，用故障鏈路劃分拓?fù)浜驮疃搪窂綐浜?，Gt中有M條鏈路，集合L中有K條鏈路。PRA-TP 中步驟的時(shí)間開銷主要有：1）遍歷拓?fù)銰劃分Gs、Gt和集合L，時(shí)間復(fù)雜度為O(N)；2）Dijkstra(Gs)的時(shí)間復(fù)雜度為O((N-M-K)2)；3）Dijkstra(Gt)的時(shí)間復(fù)雜度為O(M2)；4）遍歷集合L的時(shí)間復(fù)雜度為O(K)，PRA-TP 的時(shí)間復(fù)雜度為O((N-M-K)2+M2)，略小于Dijkstra 算法，當(dāng)Gs和Gt中鏈路數(shù)量相同時(shí)，時(shí)間開銷最小。PRA-SLS 時(shí)間開銷主要有：1）遍歷拓?fù)銰，劃分Gs、Gt和集合L，時(shí)間復(fù)雜度為O(N)；2）Dijkstra (Gt)的時(shí)間復(fù)雜度為O(M2)；3）遍歷集合L的時(shí)間復(fù)雜度為O(K)。PRA-SLS 時(shí)間復(fù)雜度為O(M2)。

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

通過比較算法計(jì)算時(shí)延和路徑恢復(fù)時(shí)延，評(píng)估路徑恢復(fù)方案。選取SNDlib［21］和topology zoo［22］中的不同拓?fù)溥M(jìn)行實(shí)驗(yàn)，拓?fù)浣Y(jié)構(gòu)描述如表1 所示。

表1 拓?fù)浣Y(jié)構(gòu)Tab.1 Topology structure

首先比較算法計(jì)算時(shí)延，實(shí)驗(yàn)環(huán)境為Intel Core i7-8700、3.20 GHz、32 GB RAM，Windows 7 操作系統(tǒng)。選擇Dijkstra算法與PRA-TP、PRA-SLS 進(jìn)行比較。隨機(jī)選擇路徑并設(shè)置單鏈路故障，由于拓?fù)漭^小，為使測(cè)量時(shí)間更準(zhǔn)確，分別對(duì)3種算法重復(fù)100 次實(shí)驗(yàn)，得到平均算法計(jì)算時(shí)延。實(shí)驗(yàn)結(jié)果如圖6 所示，隨著拓?fù)湟?guī)模增大，3 種算法的平均計(jì)算時(shí)延均隨之增加，其中Dijkstra 算法的平均計(jì)算時(shí)延最高。相較于Dijkstra 算法，PRA-TP 的平均計(jì)算時(shí)延降低了25%，PRA-SLS的平均計(jì)算時(shí)延降低了60%。雖然PRA-TP 需要兩次最短路徑計(jì)算，但每次被計(jì)算的拓?fù)渚鶠榉指詈蟮耐負(fù)?，?guī)模較小，因此整體時(shí)延較低；PRA-SLS 只需對(duì)一部分拓?fù)渥鲆淮斡?jì)算，減小了時(shí)間開銷，因此時(shí)延最低。

圖6 算法計(jì)算時(shí)延對(duì)比Fig.6 Comparison of algorithm calculation delay

在PRA-TP、PRA-SLS 中，不同位置的故障鏈路切割出不同大小的Gs和Gt，會(huì)導(dǎo)致計(jì)算時(shí)延發(fā)生變化。在拓?fù)鋞a2 和拓?fù)銰ts Ce 中，隨機(jī)選擇路徑并設(shè)置單鏈路故障，使故障鏈路切割出不同大小的Gs，選擇Dijkstra 算法與PRA-TP、PRA-SLS 進(jìn)行比較，結(jié)果如圖7、8 所示，橫軸 |Es|表示Gs中邊的數(shù)量，縱軸為計(jì)算時(shí)延。實(shí)驗(yàn)結(jié)果表明，不同的故障鏈路位置對(duì)Dijkstra 算法的時(shí)延沒有影響。對(duì)于PRA-TP，在Gs中邊的數(shù)量極小和接近原拓?fù)?|E|時(shí)，它的計(jì)算時(shí)延和Dijkstra算法計(jì)算時(shí)延基本相等；在Gs中邊的數(shù)量接近原拓?fù)渲羞叺臄?shù)量一半時(shí)，PRA-TP 計(jì)算時(shí)延最低，相較于Dijkstra 算法相比，計(jì)算時(shí)延減小了接近一半。對(duì)于PRA-SLS，計(jì)算時(shí)延隨著Gs中邊的數(shù)量增多而不斷降低，在Gs中邊的數(shù)量接近原拓?fù)鋾r(shí)，PRA-SLS 的計(jì)算時(shí)延最低，因?yàn)镻RA-SLS 只需要對(duì)Gt進(jìn)行遍歷，Gt規(guī)模越小，時(shí)間開銷越小。

圖7 ta2拓?fù)浣Y(jié)構(gòu)和計(jì)算時(shí)延Fig.7 ta2 topology structure and calculation delay

為比較路徑恢復(fù)時(shí)延時(shí)，在Mininet 仿真平臺(tái)上搭建拓?fù)鋞a2，隨機(jī)選擇路徑并設(shè)置單鏈路故障，使故障鏈路在距離源節(jié)點(diǎn)不同位置處，由Ryu 控制器完成鏈路故障檢測(cè)、路徑選擇及流表下發(fā)。選擇Dijkstra 算法與PRA-TP 進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖9 所示。實(shí)驗(yàn)結(jié)果表明采用了PRA-TP 的恢復(fù)時(shí)延更短，相較于Dijkstra 算法，PRA-TP 的平均路徑恢復(fù)時(shí)延降低了40%。這是由于路徑恢復(fù)時(shí)延主要由故障發(fā)現(xiàn)時(shí)延、openflow 消息通道時(shí)延、算法計(jì)算時(shí)延和流表更新時(shí)延構(gòu)成。由于實(shí)驗(yàn)中故障發(fā)現(xiàn)時(shí)延、openflow 消息通道時(shí)延相同，同一路徑上的同一處鏈路故障，故障恢復(fù)時(shí)所需的流表更新時(shí)間也一致，因此計(jì)算時(shí)延更小的算法，恢復(fù)時(shí)延更短。此外，在拓?fù)鋞a2 中，不同位置的鏈路故障，在路徑恢復(fù)時(shí)，流表更新次數(shù)不同，具有不同的流表更新時(shí)延，不同的流表更新時(shí)延也會(huì)影響路徑恢復(fù)時(shí)延。

圖8 Cts Ce拓?fù)浣Y(jié)構(gòu)和計(jì)算時(shí)延Fig.8 Cts Ce topology structure and calculation delay

圖9 路徑恢復(fù)時(shí)延對(duì)比Fig.9 Comparison of path recovery delay

4 結(jié)語

本文針對(duì)SDIV 架構(gòu)中車-路實(shí)時(shí)查詢類通信場(chǎng)景中的單鏈路故障問題，同時(shí)考慮恢復(fù)過程時(shí)延和路徑傳輸時(shí)延作為鏈路參數(shù)，對(duì)單鏈路故障恢復(fù)問題中的恢復(fù)時(shí)延進(jìn)行建模，而后提出了基于拓?fù)鋭澐值穆窂交謴?fù)算法（PRA-TP）和基于單鏈路搜索的路徑恢復(fù)算法（PRA-SLS）。實(shí)驗(yàn)結(jié)果表明，本文綜合考慮恢復(fù)過程時(shí)延和路徑傳輸時(shí)延的方法以及兩種算法能有效降低算法計(jì)算時(shí)延和路徑恢復(fù)時(shí)延。對(duì)于PRA-SLS，故障鏈路位置越接近目的節(jié)點(diǎn)，算法計(jì)算時(shí)延越低，相較于Dijkstra 算法，PRA-SLS 的平均計(jì)算時(shí)延降低了60%；對(duì)于PRA-TP，故障位置劃分的兩個(gè)子樹節(jié)點(diǎn)數(shù)目相近時(shí)，算法計(jì)算時(shí)延和路徑恢復(fù)時(shí)延最低，相較于Dijkstra 算法，平均計(jì)算時(shí)延降低了25%，平均路徑恢復(fù)時(shí)延降低了40%。但本文僅考慮了單鏈路故障的問題，無法應(yīng)對(duì)多鏈路故障的情景，在下一步工作中，將研究多鏈路故障情況下的解決方案。