節(jié)點可靠感知的差異保護虛擬航空網(wǎng)絡映射算法

繆競成, 呂 娜,*, 高 旗, 陳柯帆

(1. 空軍工程大學信息與導航學院, 陜西 西安 710077;2. 中國人民解放軍94860部隊, 江蘇 南京 210000)

0 引 言

航空網(wǎng)絡是由大規(guī)模有人或無人飛行器組成的無線多跳自組織網(wǎng)絡,能夠為馬賽克戰(zhàn)下的協(xié)同作戰(zhàn)提供高效的通信服務[1]。作為航空網(wǎng)絡的基本組成節(jié)點,有人或者無人飛行器由于環(huán)境干擾、電子阻斷、物理摧毀等因素,會短時間或者永久失效。為了應對節(jié)點故障,航空網(wǎng)絡必須及時調(diào)度網(wǎng)絡資源,替換故障節(jié)點,以保證任務順利完成。但是,傳統(tǒng)航空網(wǎng)絡受限于“煙囪式”、“一站式”的體系設計思路,垂直集成的網(wǎng)絡僵化問題日益突出[2-3]。其現(xiàn)有的網(wǎng)絡靈活性、開放性和互操作性水平,難以在節(jié)點故障下快速調(diào)度網(wǎng)絡資源,從而及時恢復網(wǎng)絡服務。

網(wǎng)絡虛擬化作為解決網(wǎng)絡僵化問題的未來網(wǎng)絡關鍵技術(shù),能夠克服網(wǎng)絡結(jié)構(gòu)變化,靈活調(diào)度網(wǎng)絡資源[4]。因此,網(wǎng)絡虛擬化可以為承載戰(zhàn)術(shù)任務的航空網(wǎng)絡提供具備更高靈活性、互操作性的資源共享水平。網(wǎng)絡虛擬化環(huán)境下的航空網(wǎng)絡中,不同的戰(zhàn)術(shù)任務應用能夠共享具有統(tǒng)一網(wǎng)絡資源的物理網(wǎng)絡。同時,在實際應用中,軟件定義網(wǎng)絡被認為是支持網(wǎng)絡虛擬化的理想平臺[5]。它能夠通過網(wǎng)絡控制器,根據(jù)不同的任務應用需求靈活提供端到端的服務切片,進而減少虛擬化通道的開銷[6]。

虛擬網(wǎng)絡映射[7]是實現(xiàn)網(wǎng)絡虛擬化的關鍵環(huán)節(jié),也是網(wǎng)絡虛擬化面臨的重大挑戰(zhàn)之一。它需要在虛擬節(jié)點和鏈路的資源約束條件下,將不同的虛擬網(wǎng)絡映射到統(tǒng)一的底層物理網(wǎng)絡中,已經(jīng)被證明是多項式復雜程度的非確定性(nondeterminism polynominal-hard, NP-hand)問題。現(xiàn)有的大量研究[8-13]旨在設計高效的啟發(fā)式算法,以提高虛擬網(wǎng)絡的映射成功率和底層物理網(wǎng)絡的資源利用率。但是,這些研究主要集中于有線網(wǎng)絡,并且假設底層物理網(wǎng)絡無故障[8-10]。同時,無線虛擬網(wǎng)絡映射研究主要考慮鏈路干擾和噪聲[11-12],較少關注物理網(wǎng)絡節(jié)點或鏈路故障問題[13]。其中,文獻[13]針對無線傳感器網(wǎng)絡虛擬化中的鏈路故障問題,基于多目標遺傳算法為虛擬鏈路重新選擇合適的路徑,但是沒有考慮節(jié)點故障和無線干擾對虛擬網(wǎng)絡映射的影響。由于無線傳輸?shù)臄?shù)據(jù)重傳特性,無線傳輸?shù)墓?jié)點故障問題比鏈路故障問題更為突出。另一方面,節(jié)點故障會導致所映射的虛擬節(jié)點和承載的虛擬鏈路無法提供正常服務,進而嚴重降低虛擬網(wǎng)絡的映射成功率和物理網(wǎng)絡的資源利用率。因此,在航空網(wǎng)絡虛擬化的無線網(wǎng)絡環(huán)境下,針對節(jié)點故障問題,研究高效可靠的虛擬網(wǎng)絡映射算法具有重要意義。

目前,針對節(jié)點故障的虛擬網(wǎng)絡映射算法主要基于有線網(wǎng)絡,分為重構(gòu)策略[14-16]和保護策略[17-19]。重構(gòu)策略是指物理節(jié)點故障后,對不能正常服務的虛擬節(jié)點和虛擬鏈路進行重新映射。文獻[15]針對軟件定義網(wǎng)絡中的單節(jié)點故障問題,提出采用區(qū)塊鏈技術(shù)及時檢測故障節(jié)點的映射算法。文獻[16]針對多個虛擬網(wǎng)絡組節(jié)點故障問題,提出基于平均估計和優(yōu)先級的兩種重構(gòu)方法。上述基于重構(gòu)策略的映射算法,存在恢復時延長且成功率難以保證的問題。保護策略是指提前預備網(wǎng)絡資源,為關鍵虛擬節(jié)點和相關虛擬鏈路提供保護備份,從而在節(jié)點故障后快速恢復關鍵虛擬節(jié)點和相關虛擬鏈路。文獻[17]為彈性光網(wǎng)絡虛擬化提出一種針對單節(jié)點故障的保護策略,以最小重映射成本為目標,構(gòu)建輔助拓撲保護節(jié)點。為了降低備份資源消耗,可利用P圈保護技術(shù)恢復虛擬網(wǎng)絡映射中節(jié)點或者鏈路故障[18,20]。文獻[18]構(gòu)建P圈為虛擬鏈路映射路徑上的物理節(jié)點提供有效保護。上述節(jié)點保護策略需要預置網(wǎng)絡資源進行節(jié)點保護,一定程度上影響到虛擬網(wǎng)絡的初始映射,從而降低了映射成功率?？梢缘贸?無論是選擇重構(gòu)策略或者保護策略,都會分別存在恢復時延長或者消耗資源過多、進而降低映射成功率的問題。因此,可以采用重構(gòu)與保護的混合策略,達到以較低的資源消耗和恢復時延提高節(jié)點故障下虛擬網(wǎng)絡映射成功率的目的。同時,對于無線網(wǎng)絡虛擬化環(huán)境,無論是重構(gòu)策略還是保護策略,都必須考慮無線干擾。

綜上所述,縮短恢復時延,降低資源消耗,提高節(jié)點干擾可靠性,是針對節(jié)點故障的無線虛擬網(wǎng)絡映射算法的關鍵研究點。本文針對航空網(wǎng)絡虛擬化中的節(jié)點故障問題,提出一種節(jié)點可靠感知的差異保護虛擬航空網(wǎng)絡映射(node reliability-aware protection-differentiated virtual airborne network embedding, NRPD-VANE)算法。首先,為了提高節(jié)點干擾可靠性,采用新的節(jié)點重要度評價方法,在節(jié)點映射時,綜合感知無線干擾、網(wǎng)絡資源和故障可能,選擇可靠的物理節(jié)點映射虛擬節(jié)點;其次,為了縮短恢復時延和降低消耗資源,采用重構(gòu)與保護的混合策略:針對映射虛擬節(jié)點的物理節(jié)點故障問題,重新映射虛擬節(jié)點及其鏈路,重新選擇高可靠的物理節(jié)點和路徑;針對虛擬鏈路映射路徑節(jié)點故障問題,對于路徑上的不可靠節(jié)點,根據(jù)物理節(jié)點重要度,采用P圈保護技術(shù)預置網(wǎng)絡資源,進行分級差異保護。實驗表明,本文提出的算法在保持較低恢復時延的同時,提高了映射成功率。

1 網(wǎng)絡模型及評價指標

1.1 網(wǎng)絡模型

(1) 航空網(wǎng)絡虛擬化模型。航空網(wǎng)絡受限于“煙囪式”、“一站式”的體系設計思路,網(wǎng)絡拓撲結(jié)構(gòu)日益復雜僵化。網(wǎng)絡虛擬化技術(shù)可以克服結(jié)構(gòu)變化,靈活調(diào)度網(wǎng)絡資源。受到軟件定義航空集群機載戰(zhàn)術(shù)網(wǎng)絡[21]和虛擬智能工業(yè)無線網(wǎng)絡[6]的啟發(fā),設計如圖1所示的航空網(wǎng)絡虛擬化模型。模型由下及上為物理層、虛擬層和應用層。

圖1 航空網(wǎng)絡虛擬化模型Fig.1 Model of airborne network virtualization

首先,在物理層中,有人或無人飛行器以編隊形式大量部署在作戰(zhàn)空域。其中,長機裝載支持軟件定義網(wǎng)絡的設備,進而組成大規(guī)模的無線多跳網(wǎng)絡,稱為航空底層網(wǎng)絡(airborne substrate network, ASN)。其次,在虛擬層中,管理者統(tǒng)一抽象ASN的網(wǎng)絡資源,服務于戰(zhàn)術(shù)任務應用。其中,戰(zhàn)術(shù)云代表戰(zhàn)術(shù)數(shù)據(jù)中心,具備強大算力,能夠傳達部署戰(zhàn)術(shù)任務和收集處理態(tài)勢信息,運行虛擬網(wǎng)絡映射算法,以重疊的方式編排多個戰(zhàn)術(shù)任務應用切片。最后,在應用層中,多樣化戰(zhàn)術(shù)任務應用可以抽象為相互隔離、邏輯自定義的航空虛擬網(wǎng)絡(airborne virtual network, AVN),并配備專用軟件定義網(wǎng)絡控制器,以支持AVN更改拓撲,定制應用服務需求。例如,AVN1抽象于某偵察任務,由飛行器節(jié)點2、3、4、5和云端接入節(jié)點1以及之間的無線鏈路組成。虛擬層的管理者將AVN1的虛擬節(jié)點和鏈路映射至ASN的相應物理節(jié)點和路徑中。因此,AVN1能夠利用統(tǒng)一的航空網(wǎng)絡資源,高效收集態(tài)勢信息,及時完成任務。

(2) ASN和AVN。ASN用賦權(quán)無向圖GS=(NS,LS)表示,NS和LS分別表示物理節(jié)點集合和物理鏈路集合。物理節(jié)點n的屬性包括傳輸功率tpS和位置loc(n)。其中,tpS包括編隊內(nèi)傳輸功率tpb(n)和編隊間傳輸功率tp(n)。物理鏈路的lS屬性包括鏈路傳輸帶寬b(lS)和相對位置loc(lS)。同時,pS表示一條無環(huán)物理路徑。同樣,AVN用賦權(quán)無向圖GV=(NV,LV)表示,NV和LV分別表示虛擬節(jié)點集合和虛擬鏈路集合。虛擬節(jié)點v的屬性包括位置loc(v)和映射范圍φV。虛擬鏈路lV的屬性為傳輸速率TR(lV)。在AVN的映射過程中,同一虛擬網(wǎng)絡的不同虛擬節(jié)點應映射到不同的物理節(jié)點上,且一個虛擬節(jié)點只能映射至一個物理節(jié)點。

(3) 虛擬網(wǎng)絡映射過程和節(jié)點故障影響。虛擬網(wǎng)絡映射包括節(jié)點映射和鏈路映射,要在滿足節(jié)點和鏈路資源的約束條件下,將虛擬節(jié)點和鏈路分別映射到物理網(wǎng)絡的相關節(jié)點和路徑上。物理節(jié)點故障會同時影響到已經(jīng)映射的虛擬節(jié)點和鏈路,從而導致虛擬網(wǎng)絡映射失敗。如圖2所示,AVN1和AVN2共同映射到ASN上。虛擬鏈路上的數(shù)字代表傳輸速率,物理鏈路上的數(shù)字代表傳輸帶寬,物理節(jié)點旁的數(shù)字代表編隊間傳輸功率。以AVN1為例,節(jié)點映射方案為{x→C,y→E,z→B},鏈路映射方案為{(x,y)→(C,G,E),(x,z)→(C,D,B)}。同時,物理節(jié)點E出現(xiàn)故障后,其鄰接物理鏈路隨之失效。對于AVN1,虛擬節(jié)點y和虛擬鏈路(x,y)失效。對于AVN2,由于E為虛擬鏈路(a,c)的所映射路徑(F,E,G)上的轉(zhuǎn)發(fā)節(jié)點,虛擬鏈路(a,c)失效。

圖2 AVN映射過程和節(jié)點故障影響Fig.2 Embedding process of AVN and impacts of node failure

1.2 主要評價指標

(1) 映射成功率。虛擬網(wǎng)絡映射成功率是表示映射效率的重要指標。其表達式如下所示:

(1)

式中:NUMEmb(t)是在t時刻已經(jīng)成功映射并在節(jié)點故障下正常運行的虛擬網(wǎng)絡集合數(shù);NUMv(t)是t時刻到達的虛擬網(wǎng)絡請求集合數(shù);δ為無限接近于零的常數(shù)。

(2) 平均恢復時延。平均恢復時延能夠衡量因物理節(jié)點故障而失效的虛擬節(jié)點和鏈路的恢復速度。與式(1)類似,對于成功恢復的受影響的虛擬節(jié)點和鏈路,平均恢復時延表示為在t時刻其總恢復時延與總數(shù)目之間的比值。

(3) 平均收益開銷比。平均收益開銷比表示虛擬網(wǎng)絡映射收益與映射成本之間的比值,是衡量資源利用效率的重要指標,具體表示如下:

(2)

式中:T表示虛擬網(wǎng)絡的總持續(xù)時間;VNmap(t)是t時刻已經(jīng)成功映射的虛擬網(wǎng)絡集合;R(GV,t)和C(GV,t)分別表示為

(3)

(4)

式中:R(GV,t)表示t時刻虛擬網(wǎng)絡映射的收益;β表示平衡節(jié)點功率資源和鏈路帶寬資源的系數(shù);p(n)|v→n表示映射虛擬節(jié)點v、物理節(jié)點n使用的功率資源;b(lS)|lV→pS表示映射虛擬鏈路lV、物理路徑pS上某鏈路lS使用的帶寬資源;|pS|為pS上的鏈路集合數(shù);C(GV,t)表示t時刻虛擬網(wǎng)絡映射的成本,相比于R(GV,t),需要考慮映射路徑上占用的所有鏈路帶寬資源;α與β類似,同為系數(shù)。

2 NRPD-VANE算法

本文提出的NRPD-VANE算法,采用新的節(jié)點重要度評價方法,綜合感知無線干擾、網(wǎng)絡資源和故障可能,全面評價物理節(jié)點的重要度,為虛擬節(jié)點映射可靠的物理節(jié)點。同時,根據(jù)物理節(jié)點重要度,對虛擬鏈路映射路徑上的不可靠物理節(jié)點實行差異化保護。

2.1 節(jié)點可靠感知

為了提高節(jié)點干擾的可靠性,節(jié)點映射需要綜合感知無線干擾和故障可能下的物理節(jié)點狀態(tài)信息,考慮無線干擾、網(wǎng)絡資源和故障可能,以評價物理節(jié)點的重要程度,從而為虛擬節(jié)點選擇重要度高(即相對可靠)的物理節(jié)點。

虛擬節(jié)點重要度NoV(v)和物理節(jié)點重要度NoV(n),分別表示為

(5)

(6)

式中:Lv為虛擬節(jié)點v的鄰接虛擬鏈路集合;Ln為物理節(jié)點n的鄰接物理鏈路集合;SF(n)為故障因子,表示物理節(jié)點的故障程度;TR(lS)為物理節(jié)點鄰接鏈路lS在復雜干擾條件下可能達到的傳輸速率。TR(lS)和SF(n)的具體表示分別為

(7)

(8)

式中:g(lS)為鏈路lS的信道增益;Inf(n)為節(jié)點n受到的干擾的功率大小;Inf(lS)為鏈路lS受到干擾的功率大小。該式利用香農(nóng)公式,考慮了環(huán)境干擾和網(wǎng)絡資源。其中,環(huán)境干擾體現(xiàn)在節(jié)點和鏈路受到的干擾功率,網(wǎng)絡資源體現(xiàn)在節(jié)點功率資源p(n)和鄰接鏈路帶寬資源b(lS);h為物理節(jié)點n的故障次數(shù);σ為常數(shù);Φ為故障的物理節(jié)點集合;dij為物理節(jié)點ni和nj之間的跳數(shù)距離。當h=0時,物理節(jié)點ni在映射當前虛擬網(wǎng)絡之前沒有故障,故SF(ni)=1,ni在一定程度上是可靠的;當h>0時,ni至少出現(xiàn)過一次故障,同時故障的次數(shù)越多或者越處于故障節(jié)點集合的中心,SF(ni)越小,即ni越不可靠。

綜合式(6)、式(7)和式(8),物理節(jié)點重要度NoV(n)表示為

(9)

物理節(jié)點重要度綜合考慮了無線干擾、網(wǎng)絡資源和故障可能,全面量化評價了物理節(jié)點在無線干擾和故障可能下的重要度。

2.2 節(jié)點差異化保護

鏈路映射將AVN的虛擬鏈路映射到ASN的物理路徑上。路徑節(jié)點故障會導致虛擬鏈路失效。根據(jù)節(jié)點可靠感知得到物理節(jié)點重要度,采用P圈保護技術(shù),對路徑上的不可靠節(jié)點進行差異化保護。

2.2.1 路徑節(jié)點故障問題及P圈保護策略

對于路徑上的不可靠節(jié)點,P圈技術(shù)能夠預備網(wǎng)絡資源進行主動保護,提供徑上保護和跨徑保護兩種保護策略,資源配置效率高、恢復速度快。

(1) 徑上保護

將映射路徑上的不可靠節(jié)點置于P圈之上。如圖3(a)所示,P圈{D,B,F,I,E,D}為不可靠節(jié)點E提供保護。當節(jié)點E出現(xiàn)故障后,{D,E,I}可由{D,B,F,I}替換,映射路徑可恢復工作。

圖3 P圈的兩種保護策略Fig.3 Two protection strategies of P-Cycle technology

(2) 跨徑保護

將映射路徑上的不可靠節(jié)點置于備份路徑的跨接路徑之上。如圖3(b)所示,P圈{D,B,F,I,E,G,C,D}為跨接路徑{D,E,I}上的不可靠節(jié)點E提供保護。當節(jié)點E出現(xiàn)故障后,{D,E,I}可由{D,B,F,I}或{D,C,G,I}替換。

相比于徑上保護,跨徑保護可以提供雙重保護路徑,但需要預置更多的網(wǎng)絡資源。在資源有限的物理網(wǎng)絡中,對所有不可靠的映射路徑節(jié)點采用跨徑保護,將會消耗大量網(wǎng)絡資源,影響其他正常虛擬網(wǎng)絡的成功映射。同時,如果都采用徑上保護,難以對不可靠節(jié)點進行充分的保護,降低故障恢復成功率。所以,為路徑節(jié)點提供有效的分級保護,具有重要意義。同時,P圈的建立,需要尋找節(jié)點故障影響下的可靠路徑。

2.2.2 路徑節(jié)點差異保護

對于映射路徑上的物理節(jié)點,根據(jù)節(jié)點重要度NoV(n),將節(jié)點風險程度NoV%(n)定義為

(10)

本文根據(jù)節(jié)點風險程度NoV%(n),分級確定不可靠節(jié)點的保護策略PS(n),定義如下:

(11)

式中:數(shù)字0表示節(jié)點無保護;數(shù)字1表示節(jié)點徑上保護;數(shù)字2表示節(jié)點跨徑保護;Γ1和Γ2均表示保護策略的選擇變量,可根據(jù)網(wǎng)絡虛擬化環(huán)境進行設定。

PS(n)=0時,路徑節(jié)點風險較低,不配置保護路徑,節(jié)點故障時,重新尋找可靠節(jié)點為路徑替換故障節(jié)點;PS(n)=1,路徑節(jié)點風險較高,構(gòu)建P圈,配置如圖3(a)所示的單條保護路徑;PS(n)=2時,路徑節(jié)點風險很高,構(gòu)建P圈,配置如圖3(b)所示的雙重保護路徑。

在式(11)中,對于路徑節(jié)點n,當節(jié)點風險程度NoV%(n)不大于Γ2時,PS(n)=1或PS(n)=2,相應地需要構(gòu)建P圈進行徑上保護或跨徑保護。本文采用最短路徑Dijkstra算法構(gòu)建P圈保護路徑,其鏈路權(quán)值定義為

(12)

2.3 算法流程

如算法1所示,NRPD-VANE算法流程分為可靠映射(第1行至第21行)和故障恢復(第22行至第25行)兩個階段。在可靠映射階段,本文采用一階段式映射,即在節(jié)點映射的同時考慮鏈路映射,以提高虛擬網(wǎng)絡映射的長期收益。對于節(jié)點映射(第3行至第6行),采用貪婪式映射方法,選擇重要度最大的虛擬節(jié)點和物理節(jié)點進行匹配。對于鏈路映射(第7行至第20行),采用文獻[3]中的無線鏈路映射方法,為虛擬鏈路尋找可靠路徑。同時,由式(11)確定路徑上風險節(jié)點的差異保護策略。在故障恢復階段,在節(jié)點故障時,對受到影響的虛擬節(jié)點和鏈路,依據(jù)差異保護策略進行恢復。

NRPD-VANE算法的時間復雜度主要包括可靠映射的時間復雜度和故障恢復的時間復雜度。由于故障恢復的最大時間復雜度在于重新進行可靠映射,即將所有虛擬節(jié)點和鏈路重新映射。所以,NRPD-VANE算法的時間復雜度主要由可靠映射的時間復雜度決定?？煽坑成涞臅r間復雜度主要包括節(jié)點映射時間復雜度和鏈路映射時間復雜度。節(jié)點映射時間復雜度為O(|NS|2),其中|NS|表示物理節(jié)點總數(shù)。鏈路映射時間復雜度為O(|LV||NS|(|LS|+|NS|log2(|NS|))),其中|LS|和|LV|分別為物理鏈路和虛擬鏈路總數(shù)。由于采用一階段式映射,故可靠映射的時間復雜度為O(|NV|(|NS|2+|LV||NS|(|LS|+|NS|log2(|NS|)))),其中|NV|為虛擬節(jié)點總數(shù)。因此,本文所提NRPD-VANE算法的總時間復雜度為O(|NV|(|NS|2)+|LV||NS|·(LS+|NS|log2(|NS|))))。

3 實驗仿真

本節(jié)通過映射成功率、平均收益開銷比、平均恢復時延等3個重要評價指標,進行不同算法的對比,驗證所提NRPD-VANE算法的綜合性能。

3.1 仿真環(huán)境設置

ASN和AVN的網(wǎng)絡拓撲由改進的Salam網(wǎng)絡拓撲隨機生成算法[22]生成。該網(wǎng)絡生成算法使用K均值聚類提高網(wǎng)絡拓撲連通性和均勻性,同時具有豐富的網(wǎng)絡拓撲數(shù)據(jù)。ASN在200 km×200 km范圍內(nèi)生成均勻分布的50個節(jié)點和139條鏈路。物理節(jié)點設定具有足夠的編隊內(nèi)傳輸功率資源,其編隊間傳輸功率資源tp(n)服從[50, 100]的均勻分布,單位為W。無線鏈路的帶寬資源服從[20, 50]的均勻分布,單位為MHz。AVN到達服從泊松分布,到達時間單元為100,到達個數(shù)期望為5。AVN的生存時間服從期望為1 000個時間單元的指數(shù)分布。虛擬節(jié)點的數(shù)目服從[3, 5]的均勻分布,假設任意虛擬節(jié)點的映射范圍為100 km。虛擬鏈路的傳輸速率需求服從[3, 8]的均勻分布,單位為Mbit/s。

在式(3)、式(4)、式(8)和式(12)中,α、β、σ和γ均設為1。式(7)中,g(lS)=d-k,其中d為無線鏈路終端節(jié)點之間的歐式距離,k表示信道衰落系數(shù),k設為4。每個物理節(jié)點設有故障值Inf(n)+10-4Rf(n),其中Rf(n)服從[1, 10]的均勻分布。仿真實驗運行總時間為20 000個時間單元。為了消除隨機因素影響,共進行10次實驗,取其平均值作為最終仿真結(jié)果。仿真設定,每過2 000個時間單元,故障值最高的物理節(jié)點會發(fā)生故障,同時以50%的概率在故障發(fā)生后的1 000個時間單元內(nèi)恢復。

3.2 不同算法對比

本文對比分析了4種針對節(jié)點故障的虛擬網(wǎng)絡映射算法(見表1),且都是在相同的ASN上接受處理AVN。由于部分算法是在有線網(wǎng)絡中考慮節(jié)點故障,為了消除有線虛擬網(wǎng)絡映射方法對仿真結(jié)果的影響,所有有線虛擬網(wǎng)絡節(jié)點映射方法均采用文獻[3]作為基本的虛擬網(wǎng)絡映射方法。同時,部分算法未考慮節(jié)點故障對虛擬節(jié)點映射節(jié)點和鏈路映射路徑上節(jié)點的影響,則統(tǒng)一設定為重新映射受到影響的虛擬節(jié)點或鏈路。

表1 算法對比

在仿真環(huán)境中,干擾表示tpb(n)/Inf(n)=1, 即由S/N=101g(tpb(n)/Inf(n))為0 dB。實驗結(jié)果如圖4～圖7所示。在圖4～圖6中,對于NRPD-VANE算法,Γ1=10%,Γ2=20%。圖7表示NRPD-VANE算法在不同的Γ1和Γ2下映射成功率的變化情況。

圖4 不同算法的映射成功率變化情況Fig.4 Change of the embedding success rate of different algorithms

圖4為4種算法在相同實驗條件下映射成功率隨時間的變化圖。SVNE-ORP算法的映射成功率較低,穩(wěn)定狀態(tài)保持在0.46左右。這是因為,SVNE-ORP算法需要為虛擬節(jié)點及其鄰接鏈路預置備份虛擬節(jié)點及相關鏈路,消耗大量網(wǎng)絡資源,沒有足夠資源映射新到達的虛擬網(wǎng)絡。VNM-CNLP算法只為虛擬鏈路、消耗網(wǎng)絡資源配置P圈,相比于SVNE-ORP算法消耗較少的網(wǎng)絡資源,故其映射成功率高于SVNE-ORP算法,穩(wěn)定狀態(tài)保持在0.53左右。Fast-ReNoVatE算法不為虛擬節(jié)點或鏈路預置節(jié)點,有相對足夠的網(wǎng)絡資源對新到達的虛擬網(wǎng)絡進行映射,故映射成功率保持在0.57左右。本文提出的NRPD-VANE算法,為虛擬節(jié)點選擇可靠性高的物理節(jié)點,同時采用混合保護策略,重映射節(jié)點故障影響的虛擬節(jié)點,差異化保護路徑節(jié)點,降低了配置P圈的網(wǎng)絡資源消耗。而Fast-ReNoVatE算法由于只采用重映射的方式,在網(wǎng)絡資源利用率接近飽和的仿真中后期,在受到節(jié)點故障影響時,難以成功恢復失效的虛擬節(jié)點或鏈路。故NRPD-VANE算法的映射成功率在穩(wěn)定狀態(tài)下最高,保持在0.63左右。

圖5為4種算法平均收益開銷比的比較。SVNE-ORP算法需要消耗網(wǎng)絡資源,為虛擬節(jié)點及鄰接虛擬鏈路配置物理節(jié)點和路徑,進行備份保護,具有較大的映射開銷。同時,SVNE-ORP算法具有較低的映射成功率,收益也相對較低。根據(jù)式(2)可知,SVNE-ORP算法的平均收益開銷比較低,穩(wěn)定狀態(tài)只保持在0.41左右。VNM-CNLP算法只為虛擬鏈路消耗資源配置P圈,減小了開銷,平均收益開銷比得到了一定程度的提高,穩(wěn)定狀態(tài)保持在0.45左右。Fast-ReNoVatE算法只采用重構(gòu)策略,開銷較少,平均收益開銷比有進一步的提高,穩(wěn)定狀態(tài)保持在0.48左右。本文所提的NRPD-VANE算法,采用差異化保護,提高了資源利用率,相比于SVNE-ORP算法和VNM-CNLP算法降低了開銷,同時映射成功率最高,相比于Fast-ReNoVatE算法增加了收益,故平均收益開銷比最高,穩(wěn)定狀態(tài)保持在0.52左右。

圖5 不同算法的平均收益開銷比變化情況Fig.5 Change of the average revenue to cost ratio of different algorithms

圖6比較了4種算法在相同實驗條件下的平均恢復時延。

圖6 不同算法的平均恢復時延變化情況Fig.6 Change of the average recovery delay of different algorithms

由圖6可知,Fast-ReNoVatE算法的平均恢復時延較長,穩(wěn)定狀態(tài)保持在29.2 ms左右。這是因為Fast-ReNoVatE算法在節(jié)點故障時只采用重映射策略,需要花費一定的時間為受到影響的虛擬節(jié)點或鏈路找到合適的物理節(jié)點或路徑。VNM-CNLP算法為虛擬鏈路預置網(wǎng)絡資源構(gòu)建P圈保護路徑,在節(jié)點故障時只需要激活P圈,花費的時間較少,平均恢復時延較短,穩(wěn)定狀態(tài)保持在14.3 ms左右。SVNE-ORP算法為關鍵虛擬節(jié)點及其鄰接鏈路預配置備用物理節(jié)點及路徑,節(jié)點故障時只需要激活節(jié)點及路徑,平均恢復時延更短,穩(wěn)定狀態(tài)保持在12.5 ms左右。本文提出的NRPD-VANE算法,平均恢復時延穩(wěn)定狀態(tài)保持在13.3 ms左右。相比VNM-CNLP算法,對虛擬鏈路的對應路徑節(jié)點進行差異保護,提高了資源利用率,有更多網(wǎng)絡資源以便重新映射受到節(jié)點故障影響的虛擬節(jié)點,故穩(wěn)定狀態(tài)下的平均恢復時延減少。相比SVNE-ORP算法,未給虛擬節(jié)點進行備份保護,故平均恢復時延有所升高。

圖7比較了NRPD-VANE算法在不同Γ1和Γ2下的映射成功率。

圖7 不同的Γ1和Γ2下映射成功率的變化情況Fig.7 Change of the embedding success rate under different Γ1 and Γ2

在圖7中,藍色圓形標記的折線表示NRPD-VANE算法對路徑上的不可靠節(jié)點只采用跨徑保護策略,其穩(wěn)定狀態(tài)的映射成功率隨Γ1變化的情況。當Γ1達到15%左右時,NRPD-VANE算法能夠達到的穩(wěn)定狀態(tài)下映射成功率最高,約為0.61。同時,紅色方框標記的折線表示只采用徑上保護策略時穩(wěn)定狀態(tài)的映射成功率隨Γ2變化的情況。當Γ2達到25%左右時,NRPD-VANE算法能達到的穩(wěn)定狀態(tài)下映射成功率最高,約為0.60。結(jié)合圖4可知,只采用徑上保護或跨徑保護,難以進一步提高節(jié)點故障影響下的映射成功率。所以,本文設置Γ1=10%和Γ2=20%,可以使NRPD-VANE算法的映射成功率穩(wěn)定狀態(tài)達到0.63左右。

4 結(jié) 論

為解決航空網(wǎng)絡虛擬化節(jié)點故障下的可靠映射問題,本文提出一種網(wǎng)絡虛擬化環(huán)境下的節(jié)點差異保護映射算法。該算法的優(yōu)勢與特點如下:首先,節(jié)點映射綜合感知了故障可能、環(huán)境干擾和網(wǎng)絡資源,為虛擬節(jié)點尋找可靠的物理節(jié)點。然后,鏈路映射根據(jù)節(jié)點重要度,采用P圈保護技術(shù),為映射路徑上的不可靠節(jié)點提供差異化保護,提高了資源利用率。最后,由仿真對比可知,所提算法在具有較低的故障恢復時延的同時,在一定程度上提高了映射成功率和平均收益開銷比,具有工程應用價值。