徐一凡，孟旭東

(1.南京郵電大學(xué)，江蘇 南京 210003;2.江蘇省電信網(wǎng)絡(luò)融合實(shí)驗(yàn)室，江蘇 南京 210003)

1 概 述

5G網(wǎng)絡(luò)中通過虛擬化將一個(gè)物理網(wǎng)絡(luò)分成多個(gè)切片網(wǎng)絡(luò)來應(yīng)對不同的應(yīng)用場景[1]。網(wǎng)絡(luò)切片是一組虛擬網(wǎng)絡(luò)功能(virtualized network function，VNF)及其資源組成的一個(gè)完整的邏輯網(wǎng)絡(luò)[2]。5G中使用NFV的管理和編排(management and orchestration，MANO)模塊來實(shí)現(xiàn)切片的部署和管理。

在歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)(European telecommunication standards institute，ETSI)定義的NFV架構(gòu)框架中，包括VNF，網(wǎng)絡(luò)功能虛擬化基礎(chǔ)設(shè)施(network function virtualization infrastructure，NFVI)和MANO框架[3]。VNF是網(wǎng)絡(luò)功能的軟件實(shí)現(xiàn)，NFVI是VNF部署的環(huán)境,是硬件和軟件資源的組合，可以跨越分散的地理位置，其節(jié)點(diǎn)稱為NFVI存在點(diǎn)(NFVI-PoP)。

NFV MANO框架能夠在滿足運(yùn)營商要求(例如性能和可靠性)的同時(shí)，實(shí)現(xiàn)資源，VNF和網(wǎng)絡(luò)服務(wù)(network service，NS)的自動(dòng)化管理[4]。它包含三個(gè)功能塊：虛擬化基礎(chǔ)設(shè)施管理器(virtualized infrastructure manager，VIM)，VNFM和NFVO。MANO模塊通過一組已定義好的參考點(diǎn)與NFV架構(gòu)框架中的其他功能模塊進(jìn)行通信[5]。

在MANO中，VIM負(fù)責(zé)對整個(gè)NFVI資源的管理和監(jiān)控，例如管理配置硬件資源和虛擬化資源，收集和報(bào)告資源故障和性能信息等。VNFM負(fù)責(zé)VNF的生命周期管理，包括VNF的實(shí)例化，VNF容量的縮放，VNF更新和改進(jìn)，VNF的終結(jié)(釋放VNF占用的NFVI資源)。NFVO負(fù)責(zé)在操作域內(nèi)NS的管理和相應(yīng)策略的制定，并且通過與VNFM的協(xié)作確保VNF實(shí)例滿足性能與可靠性要求[6]。

鑒于MANO功能模塊所涵蓋的角色，它在物理網(wǎng)絡(luò)中的部署位置對切片的性能有重要影響。因?yàn)镸ANO功能塊之間通過廣域網(wǎng)(wide area network，WAN)鏈路進(jìn)行通信，所以在實(shí)際的切片網(wǎng)絡(luò)中，延遲是難以避免的。這些延遲因地點(diǎn)不同而有所不同，并隨著網(wǎng)絡(luò)流量的改變而改變[7]。MANO的管理功能無法承受高延遲，例如，延遲會(huì)阻止頻繁收集和分析來自VNF實(shí)例和VIM的監(jiān)控?cái)?shù)據(jù)[8]。另外，對于VNF故障管理來說，需要快速的故障通知和恢復(fù)，以盡量減少故障的影響并保持切片中網(wǎng)絡(luò)服務(wù)的可靠性[9]。所以說降低延遲對于整個(gè)切片的管理的影響非常重要。

另外，MANO模塊的部署位置也會(huì)影響整個(gè)切片的運(yùn)營成本，當(dāng)系統(tǒng)中有很多的VNFM時(shí)這一點(diǎn)尤為明顯。實(shí)際上，資源成本(包括計(jì)算和帶寬資源成本)因網(wǎng)絡(luò)運(yùn)營商的不同，地點(diǎn)和時(shí)間的不同而有所差異，并且網(wǎng)絡(luò)流量在系統(tǒng)中動(dòng)態(tài)變化[10]。因此，相應(yīng)地調(diào)整VNFM的數(shù)量和位置可以為切片的運(yùn)營節(jié)約大量的成本。所以MANO功能塊的映射確實(shí)是一個(gè)需要解決的重要問題。

因?yàn)閂IM的部署問題是NFVI設(shè)計(jì)的一部分，所以暫且不考慮。另外，忽略NFVO以縮小問題的范圍。所以文中主要討論的是切片系統(tǒng)中VNFM的位置映射問題。VNFM的位置問題可以映射到虛擬網(wǎng)絡(luò)映射問題(virtual network embedding，VNE)來解決[11]。VNE問題是NP-Hard問題，目前在研究中是通過啟發(fā)式的算法(例如遺傳算法)來解決這個(gè)問題[12-13]。

文中旨在找到VNFM的最佳數(shù)量和位置，以在每個(gè)時(shí)刻都可以在延遲和性能限制下最大限度地降低運(yùn)營成本。文中的主要貢獻(xiàn)包括：

(1)建立了VNFM映射(VNFM embedding，VNFME)數(shù)學(xué)模型。主要側(cè)重于動(dòng)態(tài)VNFME(即隨著映射策略隨著時(shí)間的推移而變化)的研究，并提出了此問題的ILP公式。

(2)提出了一種基于禁忌搜索的映射算法來解決VFNME問題。禁忌搜索是一種使用自適應(yīng)內(nèi)存的高效鄰域搜索方法。根據(jù)該問題的特殊性，詳細(xì)設(shè)計(jì)了算法步驟。

2 VNFM映射模型

2.1 問題描述

5G網(wǎng)絡(luò)切片通過網(wǎng)絡(luò)資源與部署位置解耦、切片內(nèi)資源動(dòng)態(tài)伸縮調(diào)整，不僅可以提高5G網(wǎng)絡(luò)服務(wù)的靈活性和資源利用率，而且降低了5G網(wǎng)絡(luò)的部署與運(yùn)營成本[14]。也就是說，在切片中，網(wǎng)絡(luò)服務(wù)和VNF可以在保證效率成本的同時(shí)，隨時(shí)隨地按需實(shí)例化，并進(jìn)行彈性的容量縮放以滿足不斷變化的網(wǎng)絡(luò)需求。因此，切片中VNF實(shí)例的數(shù)量、類型(如防火墻)和位置可能隨時(shí)間變化。而對于VNFM來說，在任何時(shí)候，它的數(shù)量都應(yīng)該適應(yīng)部署在系統(tǒng)中的VNF實(shí)例，并保證其管理功能的可靠性，以實(shí)現(xiàn)切片系統(tǒng)的最佳性能。

由于VNF實(shí)例部署在跨地理分布的NFVI-PoP上，因此NFVI-PoP網(wǎng)絡(luò)成為影響切片性能和運(yùn)營成本的重要因素。如圖1，VNFM通過Ve-Vnfm-vnf，Ve-Vnfm-em，Vi-Vnfm和Or-Vnfm等參考點(diǎn)與VNF實(shí)例，網(wǎng)元管理器(element manager，EM)，VIM和NFVO交互。另一方面，實(shí)際中VNFM與這些功能塊之間通過WAN鏈路進(jìn)行通信，故VNFM在切片中的映射在確定各個(gè)參考點(diǎn)的延遲方面起著至關(guān)重要的作用。因此，計(jì)劃外的VNFM位置會(huì)導(dǎo)致計(jì)劃外的延遲，從而對系統(tǒng)的性能和可靠性產(chǎn)生負(fù)面影響。為了保證性能，每個(gè)參考點(diǎn)可以受到延遲限制的約束。

圖1 ETSI NFV框架架構(gòu)

因此，VNFM的位置和數(shù)量對整個(gè)切片的性能以及成本至關(guān)重要。文中將相關(guān)問題稱為VNFM映射(VNFME)問題。VNFME問題具體定義如下：給定VNF實(shí)例的位置和NFVO的位置，目標(biāo)是找到：(1)管理VNF實(shí)例所需的最佳VNFM數(shù)量；(2)VNFM的類型(例如通用VNFM，用于管理來自特定VNF的VNFM等)；(3)VNFM在NFVI-PoP上的最佳位置。文中旨在滿足切片系統(tǒng)中的通信延遲和容量限制(VNFM的容量限制)的同時(shí)，以最低的運(yùn)營成本實(shí)現(xiàn)此目標(biāo)。

VNFME分為靜態(tài)和動(dòng)態(tài)。在靜態(tài)VNME中，映射和與VNF實(shí)例的關(guān)聯(lián)是永久性的，不會(huì)隨著時(shí)間而改變，這適用于系統(tǒng)中的更改(例如VNF實(shí)例數(shù)量)對于重新調(diào)整VNFM放置無關(guān)緊要的情況。但是，在實(shí)際的切片系統(tǒng)中，由于資源變化情況復(fù)雜，靜態(tài)的映射策略并不能很好地適應(yīng)這些變化，常常導(dǎo)致VNFM的數(shù)量和位置的錯(cuò)誤配置。相比之下，動(dòng)態(tài)VNFME旨在使VNFM數(shù)量和映射更好地適應(yīng)變化。

2.2 系統(tǒng)模型

模型通過一組快照進(jìn)行操作，定義一個(gè)快照t作為固定時(shí)間間隔內(nèi)系統(tǒng)狀態(tài)的表示。系統(tǒng)狀態(tài)(如VNF實(shí)例的數(shù)量，系統(tǒng)中的延遲)可能因快照而異。因此，當(dāng)系統(tǒng)從一個(gè)快照轉(zhuǎn)移到下一個(gè)時(shí)，該模型考慮四種機(jī)制來適應(yīng)系統(tǒng)以響應(yīng)變化：添加新的VNFM以應(yīng)付VNF實(shí)例的增加；刪除現(xiàn)有的VNFM降低成本；將現(xiàn)有的VNFM遷移到新的位置；將VNF實(shí)例重新分配給另一個(gè)VNFM。

假設(shè)NFVO部署在給定的NFVI-PoP上。用hp∈{0,1}表示它的位置，如果NFVO被放置在p∈P，則hp等于1，否則等于0。

2.3 問題表述

將VNFME制定為ILP問題，目標(biāo)是根據(jù)單個(gè)快照制定映射策略,以最小化切片的運(yùn)營成本。對于靜態(tài)VNFME，只在一個(gè)快照t上操作，代表系統(tǒng)的永久狀態(tài)，從系統(tǒng)的永久配置中推導(dǎo)公式。而對于動(dòng)態(tài)VNFME，是對系統(tǒng)中的每對連續(xù)快照t-1和t進(jìn)行操作。更確切地說，給定快照t-1和t，在快照t-1結(jié)束時(shí)，決定VNFM的位置以及它們與VNF實(shí)例v在快照t上關(guān)聯(lián)。所有在M(t)中的VNFM的放置決定允許是否添加新的VNFM，以及保留，刪除或遷移現(xiàn)有的VNFM。Mk(t)定義如下：

(1)

其中，F(xiàn)k(t)是一系列可以被添加到系統(tǒng)中的快照t上類型為k的新VNFM的集合，比如：

(2)

運(yùn)營成本的定義分為四個(gè)不同的部分，定義如下：

生命周期管理成本(Clif(t))：表示快照t上系統(tǒng)執(zhí)行所有VNF實(shí)例的生命周期管理所消耗的網(wǎng)絡(luò)通信帶寬的成本：

(3)

其中

計(jì)算資源成本(Ccom(t))：表示在快照t上分配給VNFM的計(jì)算資源成本：

(4)

在此假設(shè)VNFM需要單個(gè)計(jì)算資源單元。這個(gè)假設(shè)是由于缺乏關(guān)于MANO功能模塊的資源分配的可用數(shù)據(jù)。

遷移成本(Cmig(t))：表示在從快照t-1轉(zhuǎn)換到快照t的同時(shí)，將VNFM從一個(gè)NFVI-PoP遷移到另一個(gè)NFVI-PoP時(shí)所隱含的成本。

(5)

重新分配成本(Crea(t))：當(dāng)從快照t-1轉(zhuǎn)換到快照t時(shí)，系統(tǒng)中剩余的VNF實(shí)例可能會(huì)重新分配給新的VNFM。按如下方式計(jì)算重新分配這些VNF實(shí)例的成本：

(6)

最后，優(yōu)化問題的目標(biāo)是最小化以上四個(gè)成本的加權(quán)和，表示如下：

MinClif(t)+Ccom(t)+Crea(t)+Cmig(t)

(7)

在靜態(tài)情況下，式7不包括Crea(t)和Cmig(t)。

約束條件如下：

(a)每個(gè)VNF實(shí)例應(yīng)該分配給一個(gè)VNFM，如式8所示：

(8)

(b)VNF實(shí)例分配給處于同一個(gè)NFVI-PoP上的VNFM，如式9所示：

yv,m,k,p(t)≤xm,k,p(t),

?k∈K,v∈Vk(t),m∈Mk(t),p∈P

(9)

(c)確保分配給每個(gè)VNFM的VNF實(shí)例數(shù)量不超過其容量，如式10所示：

?k∈K,v∈Vk(t),m∈Mk(t),p∈P

(10)

(d)VNFM只能位于一個(gè)NFVI-PoP。這個(gè)約束由式11定義：

(11)

(e)確保VNFM僅在管理至少一個(gè)VNF實(shí)例時(shí)處于活動(dòng)狀態(tài)，如式12所示：

?k∈K,v∈Vk(t),m∈Mk(t),p∈P

(12)

(f)每個(gè)VNF實(shí)例有兩個(gè)延遲限制來控制其分配的VNFM的參考點(diǎn)上的延遲。通過式13和式14來執(zhí)行這些約束：

(yv,m,k,p(t)lv,q+yv,m,k,p(t)lv,p)δp,q(t)≤φv(t),

?k∈K,v∈Vk(t),m∈Mk(t),(p,q)∈E

(13)

(yv,m,k,p(t)hq+yv,m,k,p(t)hp)δp,q(t)≤ωv(t),

?k∈K,v∈Vk(t),m∈Mk(t),(p,q)∈E

(14)

(g)式15保證每條邊上的使用帶寬不超過其容量：

Blif(p,q)+Blif(q,p)+Bmig(p,q)+Bmig(q,p)+

Brea(p,q)+Brea(q,p)≤γp,q(t),

?(p,q)∈E

(15)

其中

在靜態(tài)情況下，式15不包括Brea(t)和Bmig(t)。

3 算法描述

禁忌搜索是一種元啟發(fā)式算法，用于指導(dǎo)局部搜索過程以找到組合優(yōu)化問題的近似最優(yōu)解。它從初始解開始探索搜索空間，并迭代地執(zhí)行移動(dòng)以從當(dāng)前解決方案轉(zhuǎn)移到其鄰域中的另一個(gè)解決方案，直到滿足終止標(biāo)準(zhǔn)[15]。文中設(shè)計(jì)的算法步驟如圖2所示。

圖2 基于禁忌搜索的VNFM映射算法偽代碼

3.1 初始映射策略

3.2 鄰域移動(dòng)

文中的禁忌搜索算法采用四種移動(dòng)類型來生成鄰域解，定義如下：

VNF重新分配：隨機(jī)選擇一個(gè)VNF實(shí)例將其重新分配給另一個(gè)VNFM。新的VNFM可能處于活動(dòng)狀態(tài)或不活動(dòng)狀態(tài)。如果是不活動(dòng)的，則VNFM被激活。如果舊VNFM不再有與其關(guān)聯(lián)的VNF實(shí)例，則停用。

VNFM重新定位：隨機(jī)選擇活動(dòng)的VNFM并移動(dòng)到另一個(gè)NFVI-PoP。選擇新的位置，以便不違反所有分配的VNF實(shí)例的延遲限制。

批量VNF重新分配：隨機(jī)抽取活躍的VNFM。然后，如果剩余的活動(dòng)VNFM具有足夠的容量來管理其分配的VNF實(shí)例，同時(shí)滿足它們的延遲約束，則重新分配VNF實(shí)例，并且停用所選VNFM。

3.3 禁忌列表和渴望水平條件

禁忌搜索使用稱為禁忌表的內(nèi)存結(jié)構(gòu)來記錄有關(guān)最近搜索歷史的信息，這可以避免局部最優(yōu)化，并防止對先前得到的最優(yōu)解的重復(fù)訪問。在后面的迭代中，如果移動(dòng)已經(jīng)存在于禁忌表中則被禁止。此外，如果禁忌表中的移動(dòng)達(dá)到渴望水平條件，則被解禁并可以重新選擇。

3.4 評價(jià)函數(shù)

在每次迭代中，禁忌搜索算法評估一組候選移動(dòng)并選擇生成最優(yōu)鄰域解的移動(dòng)。該算法使用分層目標(biāo)函數(shù)(f)來評估鄰域解，其中主要目標(biāo)首先被最小化，然后對于相同的主要目標(biāo)值，次要目標(biāo)被最小化。主要目標(biāo)被定義為由模型目標(biāo)函數(shù)和與解相關(guān)的總懲罰之和。次要目標(biāo)是活動(dòng)的VNFM與其相關(guān)的VNF實(shí)例之間的延遲總和。最終目標(biāo)是最大化Pm(t)對于所有活動(dòng)的VNFM，然后檢測并消除重疊覆蓋。

3.5 終止準(zhǔn)則

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

4.1 仿真環(huán)境

仿真實(shí)驗(yàn)使用配置為12 GB內(nèi)存，64位Win10操作系統(tǒng)，Intel Core i5處理器的計(jì)算機(jī)進(jìn)行評估，使用MATLAB進(jìn)行編程，實(shí)驗(yàn)中的物理網(wǎng)絡(luò)及虛擬網(wǎng)絡(luò)拓?fù)涠疾捎肎T-ITM生成。

預(yù)設(shè)參數(shù)信息如下：

表1 仿真參數(shù)

4.2 結(jié)果分析

文中將從成本和VNFM數(shù)量這兩個(gè)方面對基于禁忌搜索的VNFM映射算法的性能進(jìn)行評估。為了更加直觀地了解此算法的性能，將使用此算法獲得的結(jié)果與基于貪婪算法獲取的初始結(jié)果和基于遺傳算法的映射算法取得的結(jié)果進(jìn)行比較。圖3為三種算法在不同的VNF實(shí)例數(shù)量的情況下，其最優(yōu)映射策略下切片運(yùn)營總成本的對比?？梢钥闯?，提出的基于禁忌搜索的VNFM映射算法總能在初始解的基礎(chǔ)上產(chǎn)生更優(yōu)的解，一定程度上降低了切片的運(yùn)營成本，驗(yàn)證了該算法的有效性。同時(shí)可以看出這些解與基于遺傳算法產(chǎn)生的解相比基本一致，有時(shí)甚至更加優(yōu)秀。

圖3 三種算法總成本對比

圖4 C1和C2不同比例對所需VNFM數(shù)量的影響

圖4描述的是VNF實(shí)例的數(shù)量和C1，C2在VNF總量中所占不同比重對切片系統(tǒng)中所需的VNFM數(shù)量的影響。可以看出，隨著VNF數(shù)量的增加，VNFM容量有限，所以VNFM數(shù)量必然也需要增加以管理更多的VNF，但是隨著C1類型的VNF所占比重的增加，系統(tǒng)所需VNFM的數(shù)量更多，并且其增長速率也更高。這是因?yàn)镃1類型的VNF的性能和延遲要求較高，所以對管理它的VNFM的性能要求也就相應(yīng)的高。要想保證切片系統(tǒng)的性能，系統(tǒng)只能使用相匹配的高性能的專用VNFM來管理，或者減少通用型VNFM的容量來保證其管理性能的可靠性，所以相比于性能要求不高的C2類型的VNF，C1類型的VNF需要更多的VNFM來管理。

圖5為不同快照中隨著系統(tǒng)中VNF實(shí)例數(shù)量的變化，動(dòng)態(tài)VNFME與靜態(tài)VNFME產(chǎn)生的切片運(yùn)營總成本對比?？梢钥闯?，動(dòng)態(tài)VNFME產(chǎn)生的成本要低于靜態(tài)情況，并且隨著VNF數(shù)量的變化，動(dòng)態(tài)VNFM下成本的變化相對應(yīng)較為平緩。而靜態(tài)的VNFME顯然無法很好地適應(yīng)切片系統(tǒng)狀態(tài)的變化，并且成本也更高。

圖5 動(dòng)態(tài)VNFME與靜態(tài)VNFME總成本對比

5 結(jié)束語

介紹并研究了5G網(wǎng)絡(luò)切片中的VNFME問題。通過分析實(shí)際網(wǎng)絡(luò)切片系統(tǒng)中的延遲與成本因素，建立了問題的整數(shù)線性規(guī)劃最優(yōu)化模型，并提出了禁忌搜索算法來獲得最優(yōu)的映射策略。實(shí)驗(yàn)結(jié)果表明，禁忌搜索算法總能得到使切片運(yùn)營成本最小的映射策略。并且在動(dòng)態(tài)VNFME中，相對于靜態(tài)VNFME，該算法可以使策略適應(yīng)系統(tǒng)中的變化，從而使切片運(yùn)營成本顯著降低。