基于節(jié)點多屬性的虛擬網(wǎng)絡映射算法

張 鑫，王 珺，王曉璇

(南京郵電大學 江蘇省無線通信實驗室，江蘇 南京 210003)

0 引 言

隨著互聯(lián)網(wǎng)規(guī)模和應用范圍越來越廣泛，傳統(tǒng)的TCP/IP網(wǎng)絡結(jié)構(gòu)難以應對日益復雜和多樣化的信息社會的發(fā)展。同時智能手機、平板電腦的普及，使得互聯(lián)網(wǎng)服務提供商需要面臨更加復雜和多樣化的用戶需求與業(yè)務，而現(xiàn)有的網(wǎng)絡體系無法快速、便捷地實現(xiàn)業(yè)務和服務的更新與迭代。針對當前互聯(lián)網(wǎng)發(fā)展所面臨的困境，Stanford Nick McKeown教授等顛覆傳統(tǒng)的網(wǎng)絡結(jié)構(gòu)，提出一種新型、革命式的網(wǎng)絡模型，即軟件定義網(wǎng)絡(software defined network，SDN)及OpenFlow協(xié)議[1-2]。SDN與TCP/IP網(wǎng)絡相比較，能夠?qū)崿F(xiàn)控制平面和轉(zhuǎn)發(fā)平面的分離，網(wǎng)絡具備可編程的特性。因此SDN網(wǎng)絡模型主要包括SDN網(wǎng)絡應用、SDN Controller、支持OpenFlow協(xié)議網(wǎng)絡設備、南北向接口等。

目前，網(wǎng)絡虛擬化技術受到工業(yè)界和學術界的高度青睞，它不僅是解決互聯(lián)網(wǎng)發(fā)展瓶頸的關鍵技術，也是云計算的核心技術。同時集中控制網(wǎng)絡架構(gòu)SDN日益成熟和完善，尤其在云計算數(shù)據(jù)中心等場景下，為了實現(xiàn)動態(tài)調(diào)整與快速部署，必須實現(xiàn)業(yè)務部署的自動化。采用集中控制的方式，網(wǎng)絡運營商可以通過控制器編程，實現(xiàn)自動化動態(tài)業(yè)務部署，縮短業(yè)務部署周期與成本。近些年，隨著IaaS(Infrastructure as a Service)的發(fā)展，大多數(shù)主流的數(shù)據(jù)中心網(wǎng)絡基本采用基于SDN網(wǎng)絡模型構(gòu)建虛擬網(wǎng)絡實現(xiàn)網(wǎng)絡虛擬化。

網(wǎng)絡虛擬化技術聚焦的重點是在共享的、資源有限的物理網(wǎng)絡中實現(xiàn)、分配各種不同用戶或者組織要求的邏輯網(wǎng)絡，同時保證每個邏輯網(wǎng)絡之間能夠隔離并且安全、正常地對外提供應用與服務。同時具體實現(xiàn)網(wǎng)絡虛擬化技術又面臨很多問題，首先就是邏輯網(wǎng)絡映射到物理網(wǎng)絡，即虛擬網(wǎng)絡映射問題。目前虛擬網(wǎng)絡映射問題已經(jīng)得到廣泛關注，同時因其映射過程中會受到各種條件的限制，因此屬于NP-hard問題。

1 相關工作

文獻[3]在不限制地理位置的條件下，底層物理網(wǎng)絡支持路徑遷移與路徑分裂的特性，節(jié)點映射階段利用Greedy算法來映射，鏈路映射階段采取多商品流算法完成鏈路映射。文獻[4]基于馬爾可夫隨機游動模型，利用K-核分解技術將虛擬網(wǎng)絡劃分為核心網(wǎng)絡和邊緣網(wǎng)絡，優(yōu)先考慮生存時間最短的虛擬網(wǎng)絡請求(區(qū)別于以收入為導向的調(diào)度策略)。文獻[5]在節(jié)點映射階段引入網(wǎng)絡拓撲屬性，即在考慮CPU和帶寬的同時考慮節(jié)點的度(度是節(jié)點最基本最重要的拓撲屬性，可衡量在拓撲結(jié)構(gòu)中節(jié)點的相對影響和相對重要性，反映了與網(wǎng)絡剩余部分的連接程度，節(jié)點的度等于其與鄰居節(jié)點的直接鏈路數(shù))，以增強節(jié)點與其他節(jié)點聯(lián)系能力的影響。

文獻[6]基于一種QoSMap機制，通過選擇高質(zhì)量保證的物理鏈路滿足虛擬網(wǎng)絡的QoS要求，同時基于一跳距離的中繼路由節(jié)點構(gòu)建備份路徑，最終為虛擬鏈路映射提供服務質(zhì)量保證。文獻[7]在離線且未考慮節(jié)點映射階段，提出將隱藏跳數(shù)(虛擬鏈路映射到的底層路徑經(jīng)過的中間物理節(jié)點)納入到鏈路映射階段。算法將虛擬網(wǎng)絡請求分成有特定資源請求和無明確資源請求兩類，先處理有特定需求的請求，使得虛擬網(wǎng)絡映射過程中剩余網(wǎng)絡資源較多。

文獻[8]從已有算法平等地對待底層網(wǎng)絡的節(jié)點和鏈路資源，實際上這些物理資源中某些資源相比其他的資源更重要，這些關鍵資源的耗盡會對未來的請求接受率有較大的影響。拓撲感知映射在已有算法的成本函數(shù)中引入比例因子，對資源進行區(qū)分。引入重優(yōu)化機制，周期性的重優(yōu)化機制不適用于實際的網(wǎng)絡，文獻中提出當有虛擬網(wǎng)絡請求被拒絕時執(zhí)行重優(yōu)化算法，以有效地均衡負載。文獻[9]基于圖論和數(shù)據(jù)結(jié)構(gòu)的理論基礎，采取廣度優(yōu)先搜索的原則完成虛擬網(wǎng)絡的鏈路映射，盡可能使得虛擬網(wǎng)絡中節(jié)點映射到物理網(wǎng)絡中，其位置上仍然能夠保持在同一個區(qū)域內(nèi)，最終使得BFS-VNE虛擬網(wǎng)絡映射算法在相應的虛擬網(wǎng)絡映射算法性能參數(shù)上優(yōu)于其他虛擬網(wǎng)絡映射算法。同時文獻[10-11]中分別描述目前現(xiàn)有的虛擬網(wǎng)絡映射模型及K最短路徑算法。目前一些虛擬網(wǎng)絡映射算法已經(jīng)開始考慮確保網(wǎng)絡正常穩(wěn)定接納虛擬網(wǎng)絡請求，例如文獻[12-15]。

現(xiàn)有的虛擬網(wǎng)絡映射算法僅僅考慮單個節(jié)點所具有的CPU資源和帶寬資源，同時未能從鄰居節(jié)點及相關節(jié)點來全局考慮整個網(wǎng)絡拓撲，導致后續(xù)的鏈路映射成功率下降，使得虛擬網(wǎng)絡請求的數(shù)目變少，網(wǎng)絡運營商的網(wǎng)絡收益下滑。文中將基于節(jié)點多個屬性，改進傳統(tǒng)的節(jié)點映射度量方法，提出基于節(jié)點屬性的虛擬網(wǎng)絡映射方法。

2 虛擬網(wǎng)絡映射問題模型

虛擬網(wǎng)絡映射問題就是將網(wǎng)絡服務提供商需要的虛擬網(wǎng)絡請求，映射到滿足其計算和鏈路資源的網(wǎng)絡運營商的物理網(wǎng)絡中。

2.1 物理網(wǎng)絡

2.2 虛擬網(wǎng)絡

2.3 虛擬網(wǎng)絡映射問題描述

2.4 虛擬網(wǎng)絡映射問題的主要性能參數(shù)

虛擬網(wǎng)絡映射問題最主要解決的是物理網(wǎng)絡資源利用效率，希望能夠接受更多的虛擬網(wǎng)絡請求，同時進一步提高網(wǎng)絡基礎設施提供商的收益，其有關性能參數(shù)定義如下所述。

2.4.1 虛擬網(wǎng)絡收益

由某時間段全部映射成功的虛擬網(wǎng)絡請求的節(jié)點CPU計算資源和鏈路的帶寬資源的總和決定，在某個時刻一個虛擬網(wǎng)絡請求所帶來的網(wǎng)絡收益可以表示為：

(1)

其中，調(diào)節(jié)系數(shù)α∈(0,1)，一般情況取α=0.5；c(nv)表示某一時刻虛擬網(wǎng)絡Gv中節(jié)點nv的CPU計算資源數(shù)值；b(lv)表示虛擬網(wǎng)絡鏈路lv的帶寬資源數(shù)值。

2.4.2 網(wǎng)絡映射開銷

虛擬網(wǎng)絡映射過程中全部的虛擬網(wǎng)絡請求所需要的資源消耗即底層網(wǎng)絡為滿足虛擬網(wǎng)絡中節(jié)點、鏈路資源約束而消耗的物理網(wǎng)絡資源，可以表示為：

(2)

2.4.3 物理網(wǎng)絡平均收益

定義如下：

(3)

2.4.4 虛擬網(wǎng)絡請求接受率

定義如下：

(4)

其中，分子表示某單位時間范圍內(nèi)虛擬網(wǎng)絡映射過程中成功接受到虛擬網(wǎng)絡請求數(shù)量，分母表示某單位時間范圍內(nèi)虛擬網(wǎng)絡映射過程中總的虛擬網(wǎng)絡請求數(shù)量。

3 虛擬網(wǎng)絡映射算法描述

本節(jié)分析現(xiàn)有虛擬網(wǎng)絡映射算法存在的缺點與不足，同時在原有Two-Stage虛擬網(wǎng)絡映射算法的基礎上實現(xiàn)MNA-VNE虛擬網(wǎng)絡映射算法。首先介紹傳統(tǒng)虛擬網(wǎng)絡映射過程中節(jié)點綜合資源評估計算，針對現(xiàn)有評估準則中的缺陷進行改進與優(yōu)化，同時提出新的虛擬網(wǎng)絡映射算法。

虛擬網(wǎng)絡映射數(shù)學模型如圖1所示。

圖1 虛擬網(wǎng)絡映射數(shù)學模型

3.1 節(jié)點度量準則

傳統(tǒng)的虛擬網(wǎng)絡映射算法中，節(jié)點映射階段中節(jié)點的度量不僅取決于單個節(jié)點所具有剩余CPU計算資源，同時也需要考慮網(wǎng)絡中剩余鏈路帶寬資源，因此網(wǎng)絡中衡量節(jié)點資源的計算公式為：

(5)

其中，NR(n)表示節(jié)點n的綜合資源數(shù)值；CPU(n)表示節(jié)點n的CPU資源數(shù)值；BW(m)表示節(jié)點n連接的鏈路帶寬資源之和。

傳統(tǒng)虛擬網(wǎng)絡映射算法中關于節(jié)點資源評估計算存在諸多不足：

(1)節(jié)點的計算資源屬性。

現(xiàn)有的虛擬網(wǎng)絡映射算法中對于節(jié)點資源計算評估大多基于網(wǎng)絡中的單個節(jié)點，未從全局角度考慮網(wǎng)絡拓撲結(jié)構(gòu)，不能真實反映出節(jié)點映射階段中物理節(jié)點的優(yōu)先級和重要性。

圖2 網(wǎng)絡拓撲結(jié)構(gòu)I

從圖2可以計算得出，物理節(jié)點A與物理節(jié)點D的NR值相等，傳統(tǒng)的虛擬網(wǎng)絡映射算法無法區(qū)分節(jié)點A和D的優(yōu)先級，認為節(jié)點A的鄰居節(jié)點具備更多的CPU計算資源，當有虛擬網(wǎng)絡請求到達時，虛擬節(jié)點應該優(yōu)先選擇物理節(jié)點A作為映射的節(jié)點。

(2)節(jié)點的帶寬資源約束。

未能考慮與節(jié)點相連接的鏈路帶寬資源相加不能準確地反映該節(jié)點在映射過程中的優(yōu)先級及重要性，同時也會在映射過程中造成鏈路瓶頸，從而導致后續(xù)鏈路映射無法進行。

從圖3中可得出，物理節(jié)點A和物理節(jié)點B：90*(10+10)=30*(20+20+20)=1 800。由于NR(A)=NR(B)，虛擬網(wǎng)絡映射過程中的虛擬節(jié)點e將會在節(jié)點A與節(jié)點B中進行選擇。如果選擇了節(jié)點A在其后的鏈路映射中，如果要求鏈路帶寬需要大于10，由于節(jié)點A的鏈路帶寬不符合節(jié)點F的帶寬要求，必須重新進行節(jié)點映射。

圖3 網(wǎng)絡拓撲結(jié)構(gòu)II

(3)網(wǎng)絡中節(jié)點的度。

根據(jù)圖4可知，當一個虛擬網(wǎng)絡請求到達物理網(wǎng)絡中，虛擬網(wǎng)絡映射過程中需要完成節(jié)點映射，物理網(wǎng)絡中節(jié)點A的相鄰節(jié)點數(shù)目為3，而節(jié)點F的相鄰節(jié)點數(shù)目為4，因此虛擬節(jié)點g在完成虛擬網(wǎng)絡映射過程中，會優(yōu)先考慮節(jié)點F，因為物理網(wǎng)絡中節(jié)點F周圍的節(jié)點資源更加豐富，以便后續(xù)的鏈路映射能夠更好地完成。

圖4 網(wǎng)絡拓撲結(jié)構(gòu)III

針對上述不足，首先給出節(jié)點映射階段中的幾個概念，然后重新定義一種基于節(jié)點多屬性的評估公式，以更好地進行虛擬節(jié)點的映射。

首先，計算節(jié)點的計算資源屬性。節(jié)點的計算資源值不僅與單個節(jié)點自身的CPU計算資源有關，而且還與其鄰居節(jié)點的CPU計算資源有關。定義如下：

RC(nv)=CPU(nv)+CPU(nv)·

(6)

然后，改進節(jié)點的鏈路帶寬資源屬性。針對鏈路帶寬資源存在的不足，對其進行重新修改，改進公式如下：

(7)

其中，BW(nv)表示該節(jié)點的鏈路帶寬資源值；bw(lv)表示滿足該節(jié)點的映射鏈路帶寬值；θi為鏈路帶寬的加權系數(shù)，根據(jù)實際網(wǎng)絡具體情況設置。例如網(wǎng)絡中鏈路帶寬資源分布在[1,100]之間，考慮鏈路帶寬資源豐富的加權系數(shù)越大，[1,10]范圍內(nèi)為0.1，(10,20]范圍內(nèi)為0.2，依次類推。

最后，考慮節(jié)點的拓撲屬性。充分考慮節(jié)點的鄰居節(jié)點的數(shù)目對虛擬網(wǎng)絡映射的影響，因此用節(jié)點的度表示該節(jié)點鄰居節(jié)點的個數(shù)，其定義如下：

N(nv)=Neighbour(nv)

(8)

其中，N(nv)表示網(wǎng)絡中節(jié)點的度；Neighbour(nv)表示節(jié)點的相鄰節(jié)點的數(shù)目。

綜上，得出基于節(jié)點多屬性的評估方法：

NR(nv)=RC(nv)*BW(nv)*N(nv)

(9)

其中，NR(nv)表示該節(jié)點的屬性綜合度量值；RC(nv)表示節(jié)點的計算資源值；BW(nv)表示節(jié)點的鏈路帶寬資源值；N(nv)表示節(jié)點的度。

3.2 節(jié)點映射算法步驟

文中提出的MNA-VNE虛擬網(wǎng)絡映射算法是在原有兩階段虛擬網(wǎng)絡映射算法基礎上的改進與優(yōu)化。下面主要介紹MNA-VNE虛擬網(wǎng)絡映射算法的節(jié)點映射算法與鏈路映射算法。

節(jié)點映射階段算法的詳細描述及流程如下：

Step1：對到達的每一個虛擬網(wǎng)絡請求按照網(wǎng)絡收益值從大到小依次排序，其具體公式為：R(Gv,t)=α∑CPU(nv)+(1-α)∑BW(lv)，其中α∈(0,1)，CPU(nv)為虛擬網(wǎng)絡請求中節(jié)點nv的CPU計算資源值，BW(lv)為該節(jié)點nv某條鏈路帶寬，并選取收益值最大的虛擬網(wǎng)絡請求進行映射。

Step2：對虛擬網(wǎng)絡請求中的每個節(jié)點按式9進行計算，然后需要針對物理網(wǎng)絡中的物理節(jié)點按式9進行計算評估，將物理節(jié)點按照NR(ns)數(shù)值從大到小依次排序形成一個隊列，如果虛擬網(wǎng)絡中NR(nv)的最大值小于等于物理網(wǎng)絡中節(jié)點NR(ns)的最大值，則滿足節(jié)點映射的條件，將虛擬節(jié)點nv映射到物理節(jié)點ns上。

Step3：第一個虛擬節(jié)點映射成功之后，優(yōu)先選擇剛剛已經(jīng)完成映射過的物理節(jié)點進行映射，如果不滿足虛擬網(wǎng)絡映射的資源需求，則將虛擬網(wǎng)絡中第二個映射節(jié)點的資源能力值與該物理節(jié)點鄰居節(jié)點進行比較，如果符合映射要求，則將虛擬節(jié)點映射到該物理節(jié)點的鄰居節(jié)點，否則將從Step2的隊列中選取最大滿足要求的節(jié)點，并將其映射到該物理節(jié)點上。

Step4：如果在虛擬網(wǎng)絡映射中，虛擬網(wǎng)絡中節(jié)點NR(nv)的最大值大于物理網(wǎng)絡中節(jié)點NR(ns)的最大值，則該虛擬網(wǎng)絡映射無法進行，虛擬網(wǎng)絡映射失敗。

Step5：重復上述Step1，將之前已經(jīng)映射的物理網(wǎng)絡中物理節(jié)點的剩余資源再一次進行計算，并再一次按照從大到小排序，最后直到虛擬網(wǎng)絡請求中所有節(jié)點映射完成。

3.3 鏈路映射算法步驟

在3.2節(jié)的節(jié)點映射算法的基礎上，實現(xiàn)虛擬網(wǎng)絡中的鏈路映射。虛擬網(wǎng)絡鏈路映射過程中將繼續(xù)根據(jù)最短路徑算法的思想實現(xiàn)虛擬鏈路的部署，首先排除不滿足其虛擬網(wǎng)絡帶寬資源需求的物理網(wǎng)絡鏈路，在此基礎上采用K最短路徑算法完成鏈路映射。

3.4 仿真實驗

將MNA-VNE算法與文獻[3]和文獻[9]中的虛擬網(wǎng)絡映射算法進行仿真實驗對比及理論分析。其中文獻[3]的Greedy-VNE和文獻[9]的BFS-VNE均采用式5中的節(jié)點資源評估準則，并利用Python Matplotlib繪圖，將所得實驗數(shù)據(jù)在虛擬網(wǎng)絡請求接受率、網(wǎng)絡收益/開銷比兩個性能指標上進行比較。

3.4.1 實驗環(huán)境

仿真實驗中設置一個中等規(guī)模的物理網(wǎng)絡，其中包括100個物理節(jié)點和大概500條物理鏈路。為了能夠與上述虛擬網(wǎng)絡映射算法進行比較與分析，其虛擬網(wǎng)絡請求等一系列參數(shù)均按照文獻[3]中GT-ITM實驗中的參數(shù)進行設置。同時每次仿真實驗運行80 000單位時間，取10次實驗結(jié)果的平均值(單位時間為ms)。

3.4.2 仿真結(jié)果分析

由圖5可以得出，這3種虛擬網(wǎng)絡映射算法在仿真實驗初始階段的虛擬網(wǎng)絡請求接受率比較穩(wěn)定。但隨著仿真時間的不斷推移，3種算法的虛擬網(wǎng)絡請求接受率都出現(xiàn)了不同程度的下降，其中Greedy-VNE算法下降得最快。主要原因是剛開始實現(xiàn)虛擬網(wǎng)絡映射時，由于網(wǎng)絡中剩余的CPU計算資源與鏈路帶寬資源較為充裕，物理網(wǎng)絡中有足夠的物理網(wǎng)絡資源能夠滿足其虛擬網(wǎng)絡的資源請求，但隨著到達的虛擬網(wǎng)絡請求的數(shù)量越來越多，物理網(wǎng)絡中的可用資源在逐漸減少，最終導致虛擬網(wǎng)絡請求接受率逐步下降。由于MNA-VNE算法在節(jié)點映射階段采用全新的度量評估方法，充分考慮網(wǎng)絡節(jié)點拓撲，同時采用物理節(jié)點可重映射的方法，代替部分鏈路映射，減少了底層物理網(wǎng)絡中鏈路帶寬資源的消耗，從而得到更多的虛擬網(wǎng)絡請求。因此，當虛擬網(wǎng)絡映射過程到最后時，MNA-VNE虛擬網(wǎng)絡映射算法相比其他兩種算法具有明顯的優(yōu)勢。

圖5 虛擬網(wǎng)絡請求接受率

從圖6可以看出，3種算法的網(wǎng)絡收益開銷比隨著仿真時間不斷增加，都出現(xiàn)了不同程度的下降。其主要原因是隨著虛擬網(wǎng)絡請求數(shù)目的增多，物理網(wǎng)絡可以接受的虛擬網(wǎng)絡請求數(shù)目越來越少，剩余的物理網(wǎng)絡資源可能無法滿足虛擬網(wǎng)絡請求的資源需要，虛擬網(wǎng)絡請求中的鏈路映射需要消耗更多的時間和資源，導致虛擬網(wǎng)絡映射的開銷增加。由于MNA-VNE算法采用物理節(jié)點可重用，進一步降低物理網(wǎng)絡中鏈路帶寬資源的消耗，使得網(wǎng)絡資源開銷減少，從而接受到更多的虛擬網(wǎng)絡請求，增加了底層網(wǎng)絡的收益，從而提升了網(wǎng)絡收益/開銷比。所以從圖中的曲線變化走勢可以得出，MNA-VNE虛擬網(wǎng)絡映射算法在虛擬網(wǎng)絡收益/開銷比性能參數(shù)上優(yōu)于其他兩種虛擬網(wǎng)絡映射算法。

圖6 虛擬網(wǎng)絡收益/開銷比

4 結(jié)束語

在傳統(tǒng)兩階段靜態(tài)虛擬網(wǎng)絡映射算法的基礎上，充分考慮網(wǎng)絡中節(jié)點所具有的多種屬性，具體包括節(jié)點的資源屬性及網(wǎng)絡拓撲屬性，并且采取物理節(jié)點可重用技術，盡可能考慮鏈路映射過程，提出MNA-VNE虛擬網(wǎng)絡映射算法。該算法考慮單個節(jié)點的鄰居節(jié)點的資源屬性，提高了后續(xù)鏈路映射的成功率。仿真實驗表明，MNA-VNE虛擬網(wǎng)絡映射算法在虛擬網(wǎng)絡請求接收率、網(wǎng)絡收益/開銷比等性能參數(shù)上更具有優(yōu)勢。