基于節點多屬性的虛擬網絡映射算法

張 鑫，王 珺，王曉璇

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

0 引 言

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

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

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

1 相關工作

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

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

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

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

2 虛擬網絡映射問題模型

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

2.1 物理網絡

2.2 虛擬網絡

2.3 虛擬網絡映射問題描述

2.4 虛擬網絡映射問題的主要性能參數

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

2.4.1 虛擬網絡收益

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

(1)

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

2.4.2 網絡映射開銷

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

(2)

2.4.3 物理網絡平均收益

定義如下：

(3)

2.4.4 虛擬網絡請求接受率

定義如下：

(4)

其中，分子表示某單位時間范圍內虛擬網絡映射過程中成功接受到虛擬網絡請求數量，分母表示某單位時間范圍內虛擬網絡映射過程中總的虛擬網絡請求數量。

3 虛擬網絡映射算法描述

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

虛擬網絡映射數學模型如圖1所示。

圖1 虛擬網絡映射數學模型

3.1 節點度量準則

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

(5)

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

傳統虛擬網絡映射算法中關于節點資源評估計算存在諸多不足：

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

現有的虛擬網絡映射算法中對于節點資源計算評估大多基于網絡中的單個節點，未從全局角度考慮網絡拓撲結構，不能真實反映出節點映射階段中物理節點的優先級和重要性。

圖2 網絡拓撲結構I

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

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

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

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

圖3 網絡拓撲結構II

(3)網絡中節點的度。

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

圖4 網絡拓撲結構III

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

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

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

(6)

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

(7)

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

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

N(nv)=Neighbour(nv)

(8)

其中，N(nv)表示網絡中節點的度；Neighbour(nv)表示節點的相鄰節點的數目。

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

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

(9)

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

3.2 節點映射算法步驟

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

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

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

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

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

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

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

3.3 鏈路映射算法步驟

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

3.4 仿真實驗

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

3.4.1 實驗環境

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

3.4.2 仿真結果分析

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

圖5 虛擬網絡請求接受率

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

圖6 虛擬網絡收益/開銷比

4 結束語

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