拓撲與資源感知的虛擬網(wǎng)絡功能遷移方法

陽 勇，孟相如，康巧燕，韓曉陽

空軍工程大學 信息與導航學院，西安710077

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡應用更新?lián)Q代速度加劇。而傳統(tǒng)網(wǎng)絡中網(wǎng)絡功能大都基于專有硬件，部署和升級都要對硬件設施進行更改，一定程度上增加了運營商的開銷[1]。網(wǎng)絡功能虛擬化（network function virtualization，NFV）是下一代網(wǎng)絡重要技術(shù)之一，通過解耦硬件設備與運行于其上的網(wǎng)絡功能，實現(xiàn)網(wǎng)絡功能的靈活部署、動態(tài)擴展以及軟硬件的發(fā)展周期分離[2]。利用NFV 技術(shù)，網(wǎng)絡功能可以當成一個普通軟件的實例，部署和升級過程不需要重新購置和安裝新的硬件，從而降低運營商的運營成本[3-4]。

在NFV 環(huán)境的網(wǎng)絡中，由于服務功能鏈（service function chain，SFC）請求的到達時間與生存周期的差異性，隨著時間的推移，部分物理節(jié)點將部署大量虛擬網(wǎng)絡功能（virtual network function，VNF），其資源占用率達到瓶頸后，服務質(zhì)量（quality of service，QoS）急劇下降[5]。與此同時，網(wǎng)絡中存在只部署少量VNF 的節(jié)點，其大量資源處于空閑狀態(tài)。若能將部署于負載較重節(jié)點上的VNF 遷移到負載較輕的節(jié)點上，實現(xiàn)物理網(wǎng)絡的負載均衡[6]，則能在充分利用底層網(wǎng)絡資源的同時提高QoS。

目前針對NFV 環(huán)境中網(wǎng)絡的負載均衡問題已有相關(guān)研究[7-15]。文獻[7-9]研究了面向負載均衡的VNF部署問題，其中文獻[7]提出一種基于深度強化學習的雙深度Q 網(wǎng)絡VNF 部署算法，使用機器學習收集網(wǎng)絡的流量信息并計算資源占用閾值，按照基于閾值的策略部署VNF。文獻[8]以負載均衡與鏈路時延為原則，采用Google 對網(wǎng)頁排名的PageRank 算法進行節(jié)點評價，將VNF 部署在綜合能力最大的節(jié)點上。文獻[9]研究了具有布局約束的VNF 部署，每次貪婪地將下一個VNF 部署到當前負載最低且滿足位置約束的服務器上。這類方法在VNF 部署完畢的初期對網(wǎng)絡有較好的負載均衡性能，但難以避免隨著時間的推移依然出現(xiàn)負載失衡問題。文獻[10-12]研究了有關(guān)負載均衡的VNF 遷移，其中文獻[10]提出一種多優(yōu)先級的VNF 遷移開銷與網(wǎng)絡能耗聯(lián)合優(yōu)化算法，針對節(jié)點資源使用情況劃分了5 個分區(qū)，基于貪心算法對其采取不同的遷移策略，低過載節(jié)點進行VNF合并，高過載節(jié)點進行負載均衡。該算法能在降低網(wǎng)絡能耗的同時提高負載均衡程度，但分區(qū)太多加大了算法的復雜程度。文獻[11]提出一種基于多維環(huán)境感知的VNF 快速自適應遷移算法，采用固定閾值的資源感知算法選擇待遷移VNF，利用TOPSIS 算法對節(jié)點進行評價并選擇遷移目的節(jié)點，能保證遷移開銷的基礎上，提升底層網(wǎng)絡的負載均衡程度，但未考慮遷移后收益開銷比問題。文獻[12]提出一種優(yōu)化網(wǎng)絡影響的VNF 遷移方法，以降低SFC 時延為目標，同時兼顧節(jié)點負載與遷移成本，有效提高了SFC 的時效性，但對網(wǎng)絡的負載均衡提升不明顯。文獻[13]提出使用虛擬軟件定義網(wǎng)絡（software defined network，SDN）控制器作為VNF 來實現(xiàn)負載均衡的方法，當?shù)讓泳W(wǎng)絡負載失衡并且流量持續(xù)增加時，添加一個輔助的虛擬SDN 控制器共享高負載節(jié)點的負載，有效降低了高負載節(jié)點資源占用率，但添加SDN控制器加重了運營商的開銷。文獻[14]面向負載均衡對VNF 遷移方法進行了一般步驟的介紹。文獻[15]設計了一種面向NFV 的高性能四層網(wǎng)絡負載均衡機制，但二者均未給出關(guān)于負載均衡的具體方法。

針對上述問題，本文提出一種拓撲與資源感知的VNF 遷移方法（topology and resource-aware virtual network function migration method，TRA-VNFM）實現(xiàn)網(wǎng)絡的負載均衡。首先通過兩級動態(tài)閾值判定算法優(yōu)先對高過載節(jié)點實施VNF 遷移，同時計算出待遷移目的節(jié)點集。然后采用資源感知算法計算部署于過載節(jié)點上的VNF 的遷移權(quán)重，并結(jié)合資源需求確定待遷移VNF。最后通過極值交互的拓撲感知算法綜合考慮物理節(jié)點的各類屬性，選擇出最適合遷移的目的節(jié)點。實驗表明，本文提出的TRA-VNFM 方法在降低SFC 的平均時延和提高網(wǎng)絡收益開銷比的基礎上，對網(wǎng)絡的負載均衡程度有較大提升。本文的主要貢獻有：

（1）設計兩級動態(tài)閾值判定VNF 是否進行遷移，有效提高了網(wǎng)絡的負載均衡程度。

（2）提出節(jié)點就近契合度作為拓撲感知的評價指標，降低了SFC 端到端的平均時延。

（3）將極值交互式多目標決策方法運用于節(jié)點評價中，綜合考慮了各評價指標與其組成的整體對結(jié)果的影響，提升了VNF 遷移方法的性能。

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

1.1 網(wǎng)絡模型

物理網(wǎng)絡由加權(quán)無向圖G=(N,E)表示，N是物理節(jié)點集合，E是物理鏈路集合。任意節(jié)點ns∈N，擁有的資源由三元組表示。其中表示計算資源，表示存儲資源，表示轉(zhuǎn)發(fā)資源。ns的處理速度為proc(ns)。任意一條鏈路es∈E，其帶寬為b(es)，時延為d(es)。

m條虛擬SFC 組成的集合為F=(f1,f2,…,fm)，fi表示第i條虛擬SFC，可用六元組(Ii,Oi,Di,Si,Vi,Li)表示，Ii為源端點，Oi為目的端點，Di為最大允許時延，Si為數(shù)據(jù)包大小，Vi為VNF 集合，Li為虛擬鏈路集合。其中Vi=(vi,1,vi,2,…,vi,n)，vi,j表示fi的第j個VNF，其資源需求用三元組表示，表示計算資源需求，表示存儲資源需求，表示轉(zhuǎn)發(fā)資源需求。Li=(li,0,li,1,…,li,n),li,0表示Ii到vi,1之間的虛擬鏈路，li,n表示vi,n到Oi之間的虛擬鏈路，當j≠0,n時，li,j表示vi,j到vi,j+1之間的虛擬鏈路。Ti,j表示li,j的帶寬需求。

Table 1 Meaning of major variables表1 主要變量含義

1.2 節(jié)點評價指標

（1）節(jié)點ns的k類資源占用率ηk(ns) 。設k∈(cal,mem,for)，分別表示計算、存儲、轉(zhuǎn)發(fā)，對于任意物理節(jié)點ns∈N，其k類資源占用率ηk(ns)定義為當前部署（包括遷入）于ns的VNF 對k類資源的占用量與ns所擁有的k類資源總量的比值，其計算公式為式（1）。

（2）節(jié)點ns對部署于其上的vi,j的處理時延本文采用通用處理器共享算法下的處理時延模型[11]，如式（2）所示。

式中，tproc表示vi,j對數(shù)據(jù)包的處理時間，其計算方式為tproc=Si/proc(ns)。loadns表示節(jié)點ns上處理器負載百分比，即為計算資源占用率ηcal(ns)。loadi表示vi,j的計算資源需求與節(jié)點ns上所占計算資源的比值，即上下同比并令得的物理意義為部署于節(jié)點ns上的vi,j對ns計算資源的占用率。因此節(jié)點ns對vi,j的處理時延計算公式轉(zhuǎn)化為式（3）。

（3）節(jié)點nr的就近契合度。其表示vi,j遷移的目的節(jié)點nr與待遷移fi之間的緊密程度，計算公式設計為式（4）。

式中，ns為遷移的出發(fā)節(jié)點，nr為遷移的目的節(jié)點，為待遷移vi,j所在fi中vi,j+1所部署的物理節(jié)點，為待遷移vi,j所在fi中vi,j-1所部署的物理節(jié)點。若待遷移vi,j為所在fi中第一個VNF，則n-s為源端點，若待遷移vi,j為所在fi中最后一個VNF，則n+s為目的端點。為節(jié)點nr與節(jié)點之間的最短跳數(shù)，同理。TD(nr)為節(jié)點nr的鄰接節(jié)點數(shù)目。就近契合度越大，遷移的目的節(jié)點nr與fi在物理拓撲上聯(lián)系越緊密，反之越松弛。節(jié)點就近契合度可作為VNF 遷移時進行拓撲感知的評價指標。

1.3 方法評價指標

（1）負載均衡指數(shù)α，用來衡量網(wǎng)絡負載均衡的效果，其計算公式設計為式（5）。

（2）收益開銷比γ，計算公式為式（6）：

式中，hop(li,j)表示li,j部署到底層網(wǎng)絡后的跳數(shù)。收益開銷比γ越大的網(wǎng)絡性能越好。

（3）虛擬SFC的平均時延delay，計算公式為式（7）。

式中，delayi表示fi的時延，|F|表示集合F中元素的個數(shù)，即SFC 條數(shù)。在計算delayi時既要考慮節(jié)點的處理延時，還要考慮鏈路的傳輸延時d(es)，因此delayi的計算公式為式（8）：

虛擬SFC 平均時延delay越小的網(wǎng)絡性能越好。

2 VNF 遷移方法

2.1 基于兩級動態(tài)閾值的遷移判定算法

為確定觸發(fā)VNF 遷移的條件，需要對物理節(jié)點設置資源過載閾值；為使遷移盡量對高過載節(jié)點進行，并提升高過載節(jié)點的遷移成功率，需要對節(jié)點的過載程度進行分級，并對不同級別的過載節(jié)點設置不同的遷移判定條件；為使VNF 遷移更適應當前網(wǎng)絡環(huán)境，過載閾值應隨網(wǎng)絡的負載變化而動態(tài)變化?；诖嗽瓌t，本文針對物理節(jié)點的k類資源占用率，設置兩級動態(tài)閾值，其中，針對N中的物理節(jié)點ns：

若ns存在某種資源占用率，則稱之為二級過載節(jié)點。若ns不是二級過載節(jié)點，但存在ηk(ns)>則稱之為一級過載節(jié)點。ns的遷移具體判定過程如圖1 所示。

Fig.1 Migration judgment process based on two-level dynamic threshold圖1 基于兩級動態(tài)閾值的遷移判定過程

首先判斷ns是否為二級過載節(jié)點。若是，則計算其待遷移目的節(jié)點集合Φ是否為空。對于二級過載節(jié)點，Φ定義為將待遷移VNF 遷入后仍然不會二級過載的節(jié)點集合。若Φ不為空，則在Φ中選擇節(jié)點作為遷移的目的節(jié)點并實施VNF 遷移，直到ns不再二級過載。若Φ為空，則說明網(wǎng)絡中各節(jié)點都負載嚴重，無法再對ns進行負載均衡，故不進行VNF遷移。

若ns不是二級過載節(jié)點，或經(jīng)過VNF 遷移后已從二級過載節(jié)點中移除，則判斷其是否為一級過載節(jié)點。若是，則計算其待遷移目的節(jié)點集合Φ是否為空。對于一級過載節(jié)點，Φ定義為將待遷移VNF遷入后仍然不會一級過載的節(jié)點集合。若Φ不為空，則在Φ中選擇節(jié)點作為遷移的目的節(jié)點并實施VNF 遷移，直到ns不再一級過載。若Φ為空，則說明此時底層網(wǎng)絡的負載已較為均衡，無需進行遷移。

為實現(xiàn)過載閾值隨網(wǎng)絡的負載變化而動態(tài)變化，k類資源的一級過載閾值設定為物理網(wǎng)絡中該類資源的均值，即為式（9）：

式中，|N|表示物理節(jié)點集合N中元素的個數(shù)，即物理節(jié)點總個數(shù)。k類資源的二級過載閾值設定為該類資源的一級過載閾值與1 的均值，即為式（10）：

2.2 基于資源感知的待遷移VNF 選擇算法

一個過載的物理節(jié)點上可能部署了多個VNF，需要從中選擇待遷移VNF。引入遷移指數(shù)θi,j(ns)表示節(jié)點ns上的vi,j適合遷移的程度。本算法基于資源感知的動態(tài)權(quán)值計算遷移指數(shù)，保證二級過載資源的權(quán)重大于一級過載資源，一級過載資源的權(quán)重大于不過載資源，占用大過載級別資源越多的VNF遷移指數(shù)越大。

令l∈{1,2}，則k類資源l級過載閾值可表示為定義表示節(jié)點ns的k類資源是否l級過載，即ηk(ns)是否大于。則遷移指數(shù)計算公式設計為式（11）。

通過比較過載節(jié)點上各VNF 的遷移指數(shù)大小，值最大的VNF 進行遷移，若節(jié)點仍然過載，則將剩下的VNF 中值最大的繼續(xù)進行遷移，直到節(jié)點不再過載。

2.3 基于拓撲感知的目的節(jié)點選擇算法

在集合Φ中進行目的節(jié)點選擇是一個多目標決策問題，本文通過極值交互的拓撲感知算法對Φ中節(jié)點進行評價并計算遷入指數(shù)。其中拓撲感知通過使用評價指標實現(xiàn)，遷入指數(shù)用來衡量節(jié)點作為遷移目的節(jié)點的適合程度。最終選擇遷入指數(shù)最大的節(jié)點作為遷移目的節(jié)點。極值交互的拓撲感知算法中節(jié)點評價與遷入指數(shù)計算過程如下：

步驟1確定評價指標。本文對待遷移目的節(jié)點nr的評價指標有計算資源占用率ηcal(nr)，存儲資源占用率ηmem(nr)，轉(zhuǎn)發(fā)資源占用率ηfor(nr)，對待遷移vi,j的處理時延就近契合度，其中ns為遷移的出發(fā)節(jié)點。越小，越大，則節(jié)點nr的遷入指數(shù)越大。令集合φ=

步驟2計算待遷移目的節(jié)點nr的各項評價指標滿意度ρ。評價指標滿意度反映節(jié)點nr的某項評價指標與所有待遷移目的節(jié)點中該項評價指標最優(yōu)值的契合程度，其計算方法如式（13）、式（14）所示，其中a代指ηcal(nr)、ηmem(nr)、ηfor(nr)以及中任意一個評價指標。

步驟3計算待遷移目的節(jié)點nr的總體協(xié)調(diào)度λ(d)。總體協(xié)調(diào)度反映節(jié)點的各項評價指標總體與理論最優(yōu)節(jié)點之間的契合程度，其與各項評價指標滿意度結(jié)合完成對遷移目的節(jié)點的選擇?？傮w協(xié)調(diào)度計算方法如下：

首先計算節(jié)點的各項評價指標與其相應最優(yōu)值之間的歐式距離和d1，如式（15）所示。

然后計算各項評價指標最優(yōu)值與最差值之間的歐式距離和d2，如式（16）所示。

最后結(jié)合d1、d2構(gòu)造總體協(xié)調(diào)度λ(d)，計算方法如式（17）所示。

步驟4計算待遷移目的節(jié)點nr的遷入指數(shù)τ(nr)。設總體協(xié)調(diào)度允許的下限值為λ(d-)，集合φ中各項評價指標滿意度允許的下限值分別為ρ(a-)，的滿意度允許的下限值為若某項評價指標滿意度低于其下限值，則計算出下限值與其的差值，定義為該項評價指標的補差值。若評價指標滿意度高于或等于其下限值，則補差值為0?？傮w協(xié)調(diào)度的補差值亦然。補差值的引入可以增加低于下限值的評價指標滿意度對節(jié)點遷入指數(shù)的影響。設總體協(xié)調(diào)度的補差值為z*，滿意度的補差值分別為z1、z2、z3、z4、z5。則待遷移目的節(jié)點nr的遷入指數(shù)計算公式為式（18）：

待遷移目的節(jié)點nr的遷入指數(shù)τ(nr)隨各項評價指標滿意度與總體協(xié)調(diào)度的增大而增大，隨其補差值的增大而減少，反映了nr作為遷移目的節(jié)點的適合程度。因此在VNF 遷移中，選擇τ最大的節(jié)點作為VNF 遷入的目的節(jié)點。VNF 遷移成功后，再對相關(guān)聯(lián)虛擬鏈路進行重新部署。先將不滿足虛擬鏈路帶寬需求的物理鏈路刪除，然后在剩余物理網(wǎng)絡拓撲中運行k-最短路徑算法重新部署虛擬鏈路。

綜合以上三種算法，拓撲與資源感知的VNF 遷移方法基本流程如下所示。

3 實驗仿真

本文通過Matlab 進行兩組仿真實驗對比TRAVNFM 方法與其他三種VNF 遷移方法的性能。第一組實驗通過比較單次遷移平均時間和總遷移時間，對比四種方法在遷移過程中的性能。第二組實驗通過比較負載均衡指數(shù)、收益開銷比和SFC 平均時延，對比四種方法在遷移后對網(wǎng)絡的優(yōu)化程度。

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

物理網(wǎng)絡是一張有25 個節(jié)點和27 條鏈路的連通圖，為提高系統(tǒng)的穩(wěn)定性，從中設置5 個節(jié)點空閑。實驗各項參數(shù)如表2 所示。其中滿意度下限與協(xié)調(diào)度下限通過多次調(diào)試，最終確定為效果最優(yōu)的表中所示值。

3.2 不同方法對比

本文將TRA-VNFM 方法與其他三種VNF 遷移方法在相同實驗環(huán)境下進行對比，如表3 所示。

3.3 算法性能分析

遷移過程中計算、存儲與轉(zhuǎn)發(fā)資源的一級與二級過載閾值如表4 所示。

為適應物理網(wǎng)絡整體的資源占用變化，每一種資源的過載閾值都隨著SFC 數(shù)量的變化而動態(tài)調(diào)整。隨著SFC 數(shù)量的增加，網(wǎng)絡整體負載上升，過載閾值隨之上升。同時每種資源的二級過載閾值都高于其一級過載閾值，這是為了實現(xiàn)遷移優(yōu)先對高過載節(jié)點進行，并提升高過載節(jié)點的遷移成功率。

Table 2 Simulation parameters表2 仿真參數(shù)

Table 3 Comparison of different VNF migration methods表3 不同VNF 遷移方法對比

第一組實驗結(jié)果如圖2 和圖3 所示。

Table 4 Variation of overload threshold表4 過載閾值變化情況

Fig.2 Average time for single migration圖2 單次遷移平均時間

Fig.3 Total migration time圖3 總遷移時間

圖2 是四種方法的單次遷移平均時間隨服務功能鏈請求增加的變化對比圖，從圖中可以發(fā)現(xiàn)TRAVNFM 與OTRA-VNFM 單次遷移的平均時間小于MJOVME-VNFM 與RT-VNFM。這是因為TRAVNFM 與OTRA-VNFM 在對遷移目的節(jié)點選擇時進行了拓撲感知，選擇了與待遷移SFC 較近的節(jié)點作為遷移的目的節(jié)點，從而降低了單次遷移的時間。在TRA-VNFM 與OTRA-VNFM 的對比中，由于兩者分別采用二級閾值和一級閾值進行遷移判定，遷移次數(shù)和遷移目的節(jié)點具有差異性，導致二者的單次遷移平均時間有所不同。

圖3 是四種方法的總遷移時間隨服務功能鏈請求增加的變化對比圖，TRA-VNFM 與OTRA-VNFM的總遷移時間略小于MJOVME-VNFM 與RT-VNFM。這是因為TRA-VNFM 與OTRA-VNFM 在目的節(jié)點選擇過程中增加了節(jié)點就近契合度作為評價指標，與MJOVME-VNFM 和RT-VNFM 只考慮資源占用率相比，TRA-VNFM 與OTRA-VNFM 雖減小了單次遷移的平均時間，一定程度上也增加了遷移次數(shù)。但TRA-VNFM 與OTRA-VNFM 采用極值交互的多目標決策算法對遷移目的節(jié)點進行選擇，既考慮各評價指標的影響，又考慮其組成的整體產(chǎn)生的影響，因此在總遷移時間方面仍然具有優(yōu)勢。

第二組實驗結(jié)果如圖4～圖6 所示。

Fig.4 Load balancing index圖4 負載均衡指數(shù)

Fig.5 Revenue to expense ratio圖5 收益開銷比

Fig.6 Average delay of SFC圖6 SFC 平均時延

圖4 是四種方法的負載均衡指數(shù)對比圖，TRAVNFM 的負載均衡效果明顯優(yōu)于另外三種方法。這是因為TRA-VNFM 使用了兩級動態(tài)閾值遷移判定條件，相對于后三種方法，TRA-VNFM 優(yōu)先對高負載節(jié)點進行遷移，并提升了高負載節(jié)點的遷移成功率。而高負載節(jié)點的減少會明顯降低節(jié)點資源占用率方差，從而使得網(wǎng)絡的負載均衡指數(shù)增加。

圖5 比較了四種方法的收益開銷比，TRA-VNFM與OTRA-VNFM 相較MJOVME-VNFM 與RT-VNFM得到了更高的收益開銷比。這是因為進行了拓撲感知的TRA-VNFM 與OTRA-VNFM 在對目的節(jié)點進行評價時選擇了與SFC 原部署路徑緊密的節(jié)點作為遷移的目的節(jié)點，使遷移后SFC 的物理長度相較于MJOVME-VNFM 和RT-VNFM 更小，從而具有更小的鏈路開銷，更高的收益開銷比。

圖6 是四種方法的SFC 平均時延對比圖，SFC 的平均時延受到遷移目的節(jié)點的處理時延和重構(gòu)鏈路的傳輸時延影響。而TRA-VNFM 與OTRA-VNFM在進行節(jié)點評價時，既將節(jié)點時延作為評價指標，使遷移目的節(jié)點的處理時延盡可能小，又通過就近契合度，使遷移后SFC 的物理長度盡可能小。因此與MJOVME-VNFM 和RT-VNFM 相比，TRA-VNFM 與OTRA-VNFM 具有更低的SFC 平均時延。

4 結(jié)束語

本文基于NFV 環(huán)境中網(wǎng)絡負載均衡的特點，提出一種拓撲與資源感知的VNF 遷移方法。首先，設置兩級動態(tài)閾值及相應的遷移判定條件，優(yōu)先對高負載節(jié)點進行遷移。其次，使用資源感知算法計算待遷移節(jié)點上各VNF 適合遷移的程度，優(yōu)先遷移對高過載資源占用多的VNF。最后，利用極值交互的拓撲感知算法對待遷移目的節(jié)點進行評價，完成遷移目的節(jié)點的選擇。實驗表明，本文提出的TRA-VNFM方法在降低SFC 的平均時延和提高網(wǎng)絡收益開銷比的基礎上，對網(wǎng)絡的負載均衡程度有較大提升。下一步將對SFC 的生存性進行研究，進一步提高NFV環(huán)境中網(wǎng)絡的性能。