面向動態(tài)環(huán)境的虛擬光網(wǎng)絡(luò)資源優(yōu)化算法*

張順利,邵蘇杰

(1.晉中學(xué)院 信息技術(shù)與工程系,山西 晉中 030619;2.北京郵電大學(xué) 計(jì)算機(jī)學(xué)院,北京 100876)

0 引 言

隨著5G、設(shè)備到設(shè)備通信等技術(shù)的快速發(fā)展和應(yīng)用[1-3],網(wǎng)絡(luò)帶寬的需求量快速增加。采用網(wǎng)絡(luò)虛擬化技術(shù)構(gòu)建的新型彈性光網(wǎng)絡(luò)(Elastic Optical Networks,EONs),逐漸成為下一代極具前景的光傳送網(wǎng)[4]。在EONs環(huán)境下,服務(wù)提供商(Service Provider,SP) 通過從底層設(shè)施提供商(Infrastructure Provider,InP) 租用光網(wǎng)絡(luò)資源,也稱為底層網(wǎng)絡(luò)(Substrate Network,SN) 資源,創(chuàng)建虛擬網(wǎng)絡(luò)(Virtual Network,VN)為最終用戶提供定制服務(wù),無需對底層設(shè)施進(jìn)行大量投資[5]。所以,EONs環(huán)境下的資源分配是一個(gè)研究重點(diǎn)。文獻(xiàn)[6]基于光纖的并行傳輸特性,提高了光網(wǎng)絡(luò)的資源利用率。文獻(xiàn)[7]采用動態(tài)定價(jià)策略,從經(jīng)濟(jì)學(xué)角度提升了資源的經(jīng)濟(jì)收益。文獻(xiàn)[8]針對空分復(fù)用彈性光數(shù)據(jù)中心網(wǎng)絡(luò),提出了基于鏈路和節(jié)點(diǎn)特征的資源分配算法。文獻(xiàn)[9-11]分別從光路可靠性、多業(yè)務(wù)部署維度提升了網(wǎng)絡(luò)的可用性、安全性以及服務(wù)質(zhì)量。但是,隨著EONs應(yīng)用范圍的增加,虛擬網(wǎng)絡(luò)及其承載服務(wù)的規(guī)模、數(shù)量、復(fù)雜度也快速增加。例如,部分虛擬網(wǎng)服務(wù)的流量需求與日期、業(yè)務(wù)成熟度等因素相關(guān),文獻(xiàn)[6-11]不能有效解決流量需求變化場景下的資源分配問題。為解決所需資源與獲得資源不匹配問題,文獻(xiàn)[12]設(shè)計(jì)了資源感知的虛擬網(wǎng)絡(luò)重構(gòu)策略。為解決高密度網(wǎng)絡(luò)環(huán)境下資源分配效率低的問題,文獻(xiàn)[13]根據(jù)容量和可行性比率構(gòu)建虛擬網(wǎng)鏈路縮減網(wǎng)絡(luò)模型,提出了貪婪鏈路縮減算法。但是,在虛擬網(wǎng)鏈路縮減階段,需要多次迭代計(jì)算虛擬網(wǎng)鏈路容量和可行性比率,時(shí)間復(fù)雜度較高。尤其是在網(wǎng)絡(luò)動態(tài)環(huán)境下,增加了資源分配算法的復(fù)雜度。同時(shí),當(dāng)虛擬網(wǎng)絡(luò)生命周期結(jié)束,網(wǎng)絡(luò)資源的數(shù)量和利用率都會發(fā)生動態(tài)變化,容易造成虛擬網(wǎng)服務(wù)不可用、部分底層網(wǎng)絡(luò)資源負(fù)載過重、網(wǎng)絡(luò)資源浪費(fèi)等問題。

為解決此問題,本文提出了面向動態(tài)環(huán)境的虛擬光網(wǎng)絡(luò)資源優(yōu)化算法(Resource Optimization Algorithm for Virtual Optical Networks under Dynamic Environment,ROAVONDE)。為實(shí)現(xiàn)虛擬網(wǎng)絡(luò)之間更好的協(xié)調(diào),獲得最優(yōu)化的虛擬網(wǎng)絡(luò)映射拓?fù)?引入人工鏈路來重建底層網(wǎng)絡(luò)拓?fù)?并基于此將虛擬節(jié)點(diǎn)連接到其等價(jià)類中選定的底層節(jié)點(diǎn),提出隨機(jī)舍入優(yōu)化算法對虛擬節(jié)點(diǎn)最優(yōu)遷移策略進(jìn)行求解。為降低算法時(shí)間復(fù)雜度,充分利用節(jié)點(diǎn)之間的競爭關(guān)系,提出一種虛擬網(wǎng)絡(luò)劃分算法,將所有虛擬網(wǎng)絡(luò)拓?fù)鋭澐譃閗個(gè)子VN。與已有算法的比較結(jié)果驗(yàn)證了本文算法較好地提升了底層網(wǎng)絡(luò)的資源利用率和虛擬網(wǎng)的映射成功率。

1 問題描述

1.1 底層網(wǎng)絡(luò)

圖1 虛擬網(wǎng)絡(luò)資源分配示意Fig.1 Virtual network resource allocation

1.2 虛擬網(wǎng)絡(luò)請求

底層節(jié)點(diǎn)nS的剩余CPU容量RN(nS)和底層鏈路eS的剩余帶寬容量RE(eS)定義如公式(1)和公式(2)所示:

RN(nS)=c(nS)-∑?nV↓nSc(nV)

(1)

RE(eS)=b(eS)-∑?eV↓eSb(eV)

(2)

式中:nV↓nS表示nV的資源由nS分配;eV↓eS表示eV的資源由eS分配。

1.3 資源分配

虛擬網(wǎng)絡(luò)映射定義如公式(3)所示,表示虛擬網(wǎng)GV(NV,EV)資源由底層網(wǎng)絡(luò)GS(NS,ES)分配。虛擬網(wǎng)絡(luò)映射可分解為節(jié)點(diǎn)映射和鏈路映射[12-13]。

M:GV(NV,EV)?GS(NS,ES)

(3)

節(jié)點(diǎn)映射的形式化描述如公式(4)所示,約束條件如公式(5)和公式(6)所示,其中dis(i,j)表示兩個(gè)節(jié)點(diǎn)i和j位置之間的物理距離。

MN(nV)∈NS

(4)

c(nV)≤RN(MN(nV))

(5)

dis(loc(nV),loc(MN(nV)))≤D(nV)

(6)

(7)

(8)

2 線性規(guī)劃模型

2.1 網(wǎng)絡(luò)重構(gòu)

虛擬節(jié)點(diǎn)選擇底層節(jié)點(diǎn)的約束包括資源約束和位置約束。為協(xié)調(diào)所有虛擬網(wǎng)絡(luò)以獲得最優(yōu)的虛擬網(wǎng)絡(luò)映射拓?fù)浣Y(jié)構(gòu),以虛擬節(jié)點(diǎn)的位置和資源需求為約束來重構(gòu)底層網(wǎng)絡(luò)[14-15]。本文以位置約束作為資源競爭特征,為每個(gè)虛擬節(jié)點(diǎn)構(gòu)建等價(jià)類,從而為每個(gè)虛擬節(jié)點(diǎn)選擇最優(yōu)的底層節(jié)點(diǎn)。

EC(nV)={nS∈NS|dis(loc(nV),loc(nS))≤D(nV)}

(9)

2.2 線性規(guī)劃模型

虛擬網(wǎng)映射拓?fù)鋬?yōu)化問題可以表述為線性規(guī)劃商品流問題。一個(gè)具有源節(jié)點(diǎn)si∈NV和目的節(jié)點(diǎn)ti∈NV的商品流就等于一條虛擬鏈路eV(i,j)∈EV。最優(yōu)VN 映射拓?fù)涞木€性規(guī)劃公式(Linear Programming Formulation for Optimal VN mapping Topologies,LPF_OVNT)的目標(biāo)函數(shù)如公式(10)所示:

(10)

s.t. C1:RN(m)≥δwmc(w),?w∈NV,?m∈NS

C6:δwm≥0,?w∈NV,m∈NS

3 優(yōu)化算法

資源優(yōu)化算法包括無劃分的隨機(jī)舍入優(yōu)化算法、帶劃分的隨機(jī)舍入優(yōu)化算法兩種,下面進(jìn)行詳細(xì)描述。

3.1 無劃分的隨機(jī)舍入優(yōu)化算法

無劃分的隨機(jī)舍入優(yōu)化算法具體描述如下:

1 重建底層和虛擬網(wǎng)絡(luò),得到新網(wǎng)絡(luò)GS′=(NS′,ES′)

2 使用模擬退火算法求解滿足LPF_OVNT約束的公式(10)的解

8 end for

9psum←∑x∈EC(nV)px

12 end for

13 使用px取值最大的底層節(jié)點(diǎn)為當(dāng)前虛擬節(jié)點(diǎn)分配資源

14 end for

15 使用多商品流算法映射遷移的虛擬節(jié)點(diǎn)的虛擬鏈路

16 更新 SN 剩余資源容量

3.2 帶劃分的隨機(jī)舍入優(yōu)化算法

為了利用小型拓?fù)涞撵`活性,將所有 VN 分解為多個(gè)子虛擬網(wǎng)絡(luò)(subVN)。為實(shí)現(xiàn)這個(gè)目標(biāo),本文將有資源競爭的VN節(jié)點(diǎn)放置在同一個(gè)subVN中,提出帶劃分的隨機(jī)舍入優(yōu)化算法(ROAVONDE-with-Divide)(subVN的數(shù)量設(shè)置為k)。

帶劃分的隨機(jī)舍入優(yōu)化算法包括4個(gè)關(guān)鍵步驟:

步驟1為虛擬節(jié)點(diǎn)生成備選底層節(jié)點(diǎn)集合(算法第1～7行)。首先根據(jù)節(jié)點(diǎn)坐標(biāo)范圍為每個(gè)虛擬節(jié)點(diǎn)尋找底層節(jié)點(diǎn)集,然后按照資源容量對每個(gè)底層節(jié)點(diǎn)集進(jìn)行排序。

步驟2將所有虛擬節(jié)點(diǎn)劃分為k個(gè)子網(wǎng)(算法第8～24行):①根據(jù)資源的競爭關(guān)系,連接所有虛擬節(jié)點(diǎn)。每個(gè)鏈路的權(quán)重表示兩個(gè)虛擬節(jié)點(diǎn)的競爭實(shí)力。因?yàn)閮蓚€(gè)底層節(jié)點(diǎn)在各自集合中的序號之和表示鏈路的權(quán)重。序號越小,表明這兩個(gè)節(jié)點(diǎn)在各種集合的順序越前。所以鏈路的權(quán)重越小,競爭力越強(qiáng)(第8～14行)。②將虛擬節(jié)點(diǎn)劃分為k個(gè)集合(第 15～24 行)。首先,將所有虛擬節(jié)點(diǎn)按節(jié)點(diǎn)度數(shù)遞減排序,然后取出度數(shù)最大的虛擬節(jié)點(diǎn)和它的連接節(jié)點(diǎn),創(chuàng)建一個(gè)新的集合并放入其中。重復(fù)這樣做,直到創(chuàng)建了k個(gè)新集合。最后,將剩余的虛擬節(jié)點(diǎn)根據(jù)與k個(gè)集合中所有中心節(jié)點(diǎn)的距離放入最近的集合中。

步驟3將虛擬鏈路放入相關(guān)子網(wǎng)(算法第25～29行)。將屬于單個(gè)子網(wǎng)的鏈路放入對應(yīng)的子網(wǎng)內(nèi),將不屬于單個(gè)子網(wǎng)的鏈路放入待映射鏈路集合Erest。

步驟4執(zhí)行節(jié)點(diǎn)映射和鏈路映射(第30～33行),根據(jù)無劃分的隨機(jī)舍入優(yōu)化算法為每個(gè)subVN分配底層網(wǎng)絡(luò)資源,最后使用多商品流算法映射Erest中的虛擬鏈路。

帶劃分的隨機(jī)舍入優(yōu)化算法具體描述如下:

步驟1 為虛擬節(jié)點(diǎn)生成備選底層節(jié)點(diǎn)集合

2 fornS∈NV

5 end for

6 end for

步驟2 將所有虛擬節(jié)點(diǎn)劃分為k個(gè)子網(wǎng)

10 if這兩個(gè)底層節(jié)點(diǎn)是相同的

11X=這兩個(gè)底層節(jié)點(diǎn)在各自集合中的序號之和

13 end for

14 end for

15 form=0 tok-1

19k++;

20 end for

24 end for

步驟3 將虛擬鏈路放入相關(guān)子網(wǎng)

27 else

29 end for

步驟4 執(zhí)行節(jié)點(diǎn)映射和鏈路映射

30 for each subVN

31 使用無劃分的隨機(jī)舍入優(yōu)化算法分配資源

32 end for

33 使用多商品流算法映射Erest中的虛擬鏈路

4 仿真與分析

4.1 仿真環(huán)境

本文實(shí)現(xiàn)了一個(gè) VN 嵌入模擬器來評估算法。底層和虛擬拓?fù)湟约癡N到達(dá)過程參數(shù)與已有研究類似[13-15]。隨機(jī)舍入優(yōu)化算法中的線性規(guī)劃問題使用 GLPK 來解決。使用GT-ITM拓?fù)渖善鱽砩删W(wǎng)絡(luò)拓?fù)鋄16]。從邊等于100的正方形區(qū)域中隨機(jī)提取底層網(wǎng)絡(luò)的位置。底層網(wǎng)絡(luò)配置為每次實(shí)驗(yàn)有100個(gè)節(jié)點(diǎn),每對底層節(jié)點(diǎn)以0.5的概率隨機(jī)連接。節(jié)點(diǎn)的CPU和鏈路的帶寬資源遵循50～100個(gè)單位的均勻分布。每個(gè)VN請求中,從邊等于100的正方形區(qū)域中隨機(jī)抽取虛擬網(wǎng)絡(luò)的位置。VN節(jié)點(diǎn)的數(shù)量由2～10之間的均勻分布隨機(jī)確定,每對虛擬節(jié)點(diǎn)以0.5的概率隨機(jī)連接,節(jié)點(diǎn)上的 CPU 資源遵循1～20的均勻分布。鏈路上的帶寬資源遵循1～50的均勻分布。VN 請求的到達(dá)服從泊松分布,每個(gè)請求的平均時(shí)間窗口為 1.5,請求的持續(xù)時(shí)間遵循平均20個(gè)時(shí)間窗口的指數(shù)分布,每個(gè)時(shí)間窗口的時(shí)長為10 s。

表1列出了用于性能分析對比的4種算法。算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide用于分析基于資源競爭特征重構(gòu)底層網(wǎng)絡(luò)以及網(wǎng)絡(luò)劃分對算法性能的影響,算法RDVNFE(Reducing Dense Virtual Networks for Fast Embedding)是根據(jù)網(wǎng)絡(luò)特征進(jìn)行網(wǎng)絡(luò)重構(gòu)的最新研究成果[13],算法RDVNFEO(Reducing Dense Virtual Networks for Fast Embedding and Optimization)在文獻(xiàn)[13]的基礎(chǔ)上采用經(jīng)典的優(yōu)化策略對網(wǎng)絡(luò)資源進(jìn)行優(yōu)化。

表1 評估算法Tab.1 Evaluation algorithms

4.2 算法運(yùn)行時(shí)長分析

將虛擬網(wǎng)劃分為3～6個(gè)子網(wǎng)絡(luò),分析算法VONROADE-with-Divide的性能可知,劃分?jǐn)?shù)量為4時(shí)算法的性能較優(yōu)。算法RDVNFE不對底層網(wǎng)絡(luò)上的資源進(jìn)行重新優(yōu)化,算法RDVNFEO周期性地對利用率超過閾值的底層資源上承載的虛擬網(wǎng)絡(luò)資源進(jìn)行重分配,不需要對網(wǎng)絡(luò)進(jìn)行重構(gòu)和求解,所以,將劃分?jǐn)?shù)量為4的算法VONROADE-with-Divide與算法VONROADE-without-Divide進(jìn)行比較,分析虛擬網(wǎng)劃分對網(wǎng)絡(luò)優(yōu)化時(shí)長的影響。

算法運(yùn)行時(shí)長結(jié)果如圖2所示,可知隨著虛擬節(jié)點(diǎn)數(shù)量的增加兩種算法的運(yùn)行時(shí)長都在增加,說明虛擬節(jié)點(diǎn)數(shù)量增加后,需要優(yōu)化的網(wǎng)絡(luò)資源數(shù)量也快速增加;算法VONROADE-without-Divide的運(yùn)行時(shí)間較長,而且隨著網(wǎng)絡(luò)規(guī)模增加,運(yùn)行時(shí)間增加較快;算法VONROADE-with-Divide運(yùn)行時(shí)間較短,而且隨著網(wǎng)絡(luò)規(guī)模增加,運(yùn)行時(shí)間的增加比較緩慢,說明算法VONROADE-with-Divide可以降低網(wǎng)絡(luò)優(yōu)化的時(shí)間開銷。

圖2 算法運(yùn)行時(shí)長Fig.2 Algorithm runtime analysis

4.3 網(wǎng)絡(luò)優(yōu)化性能分析

對于每個(gè)網(wǎng)絡(luò)場景,性能分析的結(jié)果是20個(gè)隨機(jī)實(shí)例的平均值。算法性能指標(biāo)與時(shí)間的關(guān)系如圖3～7所示。平均收益是所有已映射的虛擬網(wǎng)計(jì)算資源和帶寬資源的加權(quán)求和與時(shí)長的比值,平均開銷是為完成虛擬網(wǎng)資源分配而使用所有底層網(wǎng)絡(luò)的計(jì)算資源和帶寬資源加權(quán)求和與時(shí)長的比值。平均收益、平均開銷的單位都使用“a.u.”(arbitrary units的縮寫),表示任意單位。

圖3 隨時(shí)間變化的VN請求接受率Fig.3 VN request acceptance rate over time

圖4 資源分配的平均收益Fig.4 Average revenue on resource allocation

圖5 資源分配的平均開銷Fig.5 Average cost of resource allocation

通過對實(shí)驗(yàn)結(jié)果的分析,本文總結(jié)了下面5個(gè)主要觀察結(jié)果:

1)算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide通過協(xié)調(diào)所有虛擬網(wǎng)絡(luò)獲得最優(yōu)的虛擬網(wǎng)絡(luò)映射拓?fù)?可以獲得更高的接受率和收益。從圖3可以看出,本文算法ROAVONDE-without-Divide下虛擬網(wǎng)請求的平均接受率收斂均值約62%,算法 RDVNFE 的平均接受率收斂均值約56%,所以算法ROAVONDE-without-Divide的平均接受率比算法 RDVNFE 提升了約11%。更高的收入和更好的接受率表明本文算法可以將底層網(wǎng)絡(luò)資源分配給更多的虛擬網(wǎng)絡(luò)請求。

2)在圖3～5中,成本增加率低于VN請求接受率和平均收益的增加率。由于本文算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide可以協(xié)調(diào)所有虛擬網(wǎng)絡(luò)以獲得最優(yōu)的虛擬網(wǎng)絡(luò)映射拓?fù)?使得虛擬網(wǎng)絡(luò)能夠被分配到最優(yōu)的底層網(wǎng)絡(luò)資源,從而降低了底層網(wǎng)絡(luò)資源的成本。

3)從圖6和圖7可以看出,本文算法提高了網(wǎng)絡(luò)資源的利用率。本文算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide比算法 RDVNFE和算法RDVNFEO提高了節(jié)點(diǎn)利用率和鏈路利用率,原因是本文算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide提高了VN請求接受率,使用了更多的底層網(wǎng)絡(luò)資源。相比現(xiàn)有算法 RDVNFE,本文算法ROAVONDE-without-Divide下節(jié)點(diǎn)資源均利用率提升了約 61%,鏈路資源平均利用率提升了約27%,說明本文算法ROAVONDE-without-Divide可以為虛擬網(wǎng)絡(luò)分配更加優(yōu)化的鏈路資源。

圖6 隨時(shí)間變化的節(jié)點(diǎn)資源平均利用率Fig.Average utilization rate of node resources over time

圖7 隨時(shí)間變化的鏈路資源平均利用率Fig.7 Average utilization rate of link resources over time

4)算法ROAVONDE-with-Divide 在 VN 請求接受率和平均收益方面不如算法 ROAVONDE-without-Divide,但算法ROAVONDE-with-Divide在VN請求接受率和平均收益方面優(yōu)于算法RDVNFE和RDVNFEO。在算法運(yùn)行時(shí)間方面,算法ROAVONDE-with-Divide優(yōu)于算法ROAVONDE-without-Divide。 因此,如果網(wǎng)絡(luò)規(guī)模較大,可以使用算法ROAVONDE-with-Divide提升虛擬網(wǎng)映射的效率。

5 結(jié)束語

在EONs環(huán)境下,為解決動態(tài)環(huán)境下底層網(wǎng)絡(luò)資源利用率低的問題,本文提出了一種面向動態(tài)環(huán)境的虛擬光網(wǎng)絡(luò)資源優(yōu)化算法,通過仿真實(shí)驗(yàn)驗(yàn)證了該算法在虛擬網(wǎng)請求接受率、底層網(wǎng)絡(luò)資源利用率方面優(yōu)于現(xiàn)有算法。

由于資源分配的競爭關(guān)系與價(jià)格相關(guān),下一步工作將基于本文研究成果,進(jìn)一步從經(jīng)濟(jì)學(xué)的角度分析具有價(jià)格競爭關(guān)系的資源分配策略。