保持節點相鄰的虛擬網絡映射算法

彭紅姣，潘子輝

（1.南京郵電大學 工程訓練中心，江蘇 南京 210023；2.南京郵電大學 計算機學院，江蘇 南京 210046）

全球互聯網持續高速發展，遠超出互聯網原設計初衷，使現有網絡體系架構不具備可控可管性、服務質量難以保障、可擴展性較差、移動性支持較差等問題越為突出。隨著網絡規模進一步增長，這些問題暴露更為明顯。云計算、物聯網、大數據、人工智能、大流量視頻等新應用和新技術的不斷涌現，也對現有互聯網提出了更高要求。為從根本上解決現有網絡面臨的問題，打破互聯網僵局，研究者們經過不懈努力，認為網絡虛擬化（Network Visualization，NV）[1-5]是一個很有前景的方法，其包括新型網絡更便捷的遷移方案，更易與現有網絡共存。本文研究了其虛擬網絡映射問題并提出一種新算法，與經典的兩步式映射算法進行了比較，并分析其優勢和適用環境，驗證了其可行性。

1 虛擬網絡映射算法研究

1.1 現狀和問題

虛網映射問題是網絡虛擬化最核心的問題之一，也是一個充滿挑戰性的問題[6]。在虛網映射中，虛擬網絡請求各自對應的網絡拓撲往往不盡相同，因此要適應這些不同的拓撲請求。在分配資源時，節點和鏈路需求要同時滿足要求。一般情況下，虛網請求都是動態的，在分配當前物理資源時，不能預知將要到達的虛網請求信息。即使是靜態請求，或所有請求信息也能預知，虛網映射問題仍是一個NP-hard問題，可轉化為多路分離器問題[7-10]。另外，即便已確定節點映射，在流不可分割情況下，即在一個單一路徑上最佳地分配一個虛擬鏈路集，虛擬鏈路的映射仍是一個NP-hard問題，但可轉化為不可分割流問題[11-12]。

至今，研究人員已提出不少提高物理資源利用率的虛網映射算法，可得出某種網絡環境下較為適合的映射結果。由于虛網映射是一個NP-hard問題，需考慮的影響因素非常多，有些算法[13-15]以物理鏈路資源無限大為前提，從而實現更合理的節點映射。另一部分算法[1,16-17]側重于鏈路映射，以尋找最優鏈路映射為目的，而相對的節點映射則采取簡單處理。這兩個偏向都會存在一些問題[18-19]。

假設鏈路資源無限大，節點映射算法通常能取得非常好的效果，這些算法可有效提高物理節點資源的利用率，同時可保證節點相對緊湊（即節點間距離相對較?。?。而實際上，鏈路資源不可能為無限大，這種理想情況并不存在。故此類節點映射算法通常會在鏈路映射上遇到困難，最典型的兩個虛擬節點所映射到的物理節點之間的物理鏈路資源，無法滿足其虛網請求中虛擬鏈路的需求。其次，如果優先選擇帶寬資源較多的節點進行映射，確實能很好地滿足對物理鏈路及物理節點資源的需求。但由于總是優先占用帶寬資源最為充裕的節點，可能會對后來的虛擬網絡請求造成一定影響。另外，如將節點和鏈路映射分別執行，對于虛網請求中相鄰或相近的節點，在映射后其對應的物理節點在物理網絡中距離可能會非常遠。這種分布分散的情況常常會導致虛擬鏈路過多占用網絡資源，致使物理資源利用率降低。本文給出了一種保持節點相鄰的虛擬網絡映射算法，可有效避免上述問題，或減少其所帶來的不利影響。

1.2 經典的兩步式虛擬網絡映射算法

文獻[20]介紹了最為經典的虛擬網絡映射算法——兩步式虛擬網絡映射算法，該算法既簡潔又通用，映射簡化為虛擬節點映射和虛擬鏈路映射。在虛擬節點映射中先使用貪婪算法進行求解，再在虛擬鏈路映射中使用k最短路徑算法進行求解。

定義1映射收益是指映射到物理網絡成功后，虛網請求的收益，由映射的帶寬和CPU資源定義：

其中，B(eν)是映射成功的虛擬網絡帶寬，C(nν)是映射成功的虛擬網絡節點CPU資源，α和β是用于調節帶寬和CPU的權重系數，在本文研究中均設為1。

定義2剩余資源（Available Resource,AR）是指某節點剩余物理資源與連接該節點的鏈路資源總和的乘積：

其中，nP為物理節點，lP為物理鏈路，L(nP)為與物理節點nP直接相連的物理鏈路的集合。

在兩步式虛擬網絡映射算法中，先以時間窗為單位接收虛網請求。再根據映射收益R(GV)對一個時間窗內的虛網請求由高到低排序，收益高優先映射。若映射成功，則更新物理網絡狀態；若映射失敗，則將其列入等待隊列；若失敗次數超過預先設定的值，則放棄該虛擬網絡請求。

在每個虛網映射請求時，先進行節點映射環節。對于請求中的每個虛擬節點(nV)，通過貪婪算法找出能夠滿足其節點CPU需求，以及剩余資源最大物理節點(nP)。若能找到滿足nV條件的nP，則將nV映射到nP上，節點映射成功；否則，節點映射失敗，虛網請求映射失敗。若每個節點映射成功，則虛網請求節點映射成功。尋找物理節點過程考慮了與之相連接的物理鏈路資源，鏈路映射率得到提高。在完成節點映射后，執行鏈路映射。對于虛網請求中的每條虛擬鏈路(lV)，首先確定其兩端點，之后找到其映射的物理節點，通過k最短路徑算法，找到物理節點間的1至k條最短路徑，若其中有任意一條路徑滿足lV的帶寬需求，則將lV映射到該路徑上；若物理路徑均不滿足條件，則不能完成虛擬鏈路映射，無法實現虛網請求映射。只有全部完成每個虛擬鏈路映射，才能完成虛擬鏈路映射環節。兩個環節全部成功后，即可完成整個虛網請求映射。

1.3 虛網請求接收算法改進思路

一旦虛網請求在短時間內涌入，則會出現先到請求阻塞，或低收益請求長時間得不到滿足而產生饑渴現象等問題。為了保證算法高效運行，并取得較高的映射收益，同時避免低收益請求長時間得不到處理，本節提出了一種算法來應對這些困難。

虛擬網絡請求將實時到達，并將它們按照時間窗進行劃分。每個時間窗收到的虛擬網絡請求按收益進行排序，且按收益由高到低設立優先級（優先級數值越大則優先級越低），映射失敗時設其優先級為當前最低優先級加1，從而加入隊列末尾，并設置其count參數加1，count參數達到一定數值后（數值大小視具體情況而定），放棄該請求。當新的時間窗到達時，釋放已完成或者失效的資源，對于新到時間窗內的請求，在計算其優先級后，對其優先級加上[x/2（]x為上一時間窗的請求總數），對于優先級相同的請求，優先處理較早到達的。這樣可在有效確保較高收益的同時，保證低收益請求不會長時間得不到處理。

具體算法，步驟1：令x=0，c=0；步驟2：檢測是否有新的時間窗到達，若沒有，則跳至步驟5；步驟3：釋放已完成或者失效的資源，對時間窗內虛擬網絡請求進行統計，令y為該時間窗內虛擬網絡請求的數量，令c=c+1；步驟4：將該時間窗內虛擬網絡請求按收益從高到低進行排序，分別設其優先級為(1+[x/2])到(y+[x/2])β，且分別設其count[z]為0（z為序號），W[z]=c，令x=y；步驟5：尋找當前優先級最高的虛擬網絡請求（優先級數值最?。?，若結果唯一，跳至步驟7；步驟6：尋找結果中W[z]最小的虛擬網絡請求；步驟7：將該虛擬網絡請求進行映射，若不成功，count[z]=count[z]+1，若count[z]=3，放棄該請求，優先級設為當前最低優先級+1，并跳至步驟2。

例如，第一個時間窗中共有20個虛網請求，按請求收益由高到底給出優先級1至20。若優先級為5的虛擬網絡請求失敗，則將其優先級設為21，從而加入隊列末尾。若在一個時間窗內只能處理10個請求，而第二個時間窗又涌入10個虛擬網絡請求，則將第二個時間窗中的虛擬網絡請求按其受益從大到小優先級分別設為11至20。然后優先處理第一個時間窗中優先級為11的虛擬網絡請求，再處理第二個時間窗中優先級為11的請求，之后再處理第一個時間窗中優先級為12的請求，依此類推。

2 設計保持節點相鄰的虛擬網絡映射算法

本節針對完成映射后相鄰虛擬節點所對應的物理節點過于分散的情況，提出了一種既考慮節點映射又考慮鏈路需求的保持節點相鄰的虛擬網絡映射算法。

如圖1所示，在虛網請求到達時，大多算法會將虛擬節點a、b、c分別映射到物理節點A、F、B。這樣，在虛擬網絡請求中相鄰的兩對節點（a與b，b與c）之間的距離就相對較遠。但如果將虛擬節點a、b、c分別映射到物理節點A、D、E，則既能滿足節點需求，又能滿足鏈路需求，同時在虛擬網絡請求中相鄰的兩對節點在實際物理網絡中仍舊保持相鄰，大大減少了物理鏈路資源的耗費，同時保持節點相鄰可以提高實際工作效率，從而提高了服務質量。

圖1 節點資源優先節點映射。（a）虛擬網絡請求；（b）物理網絡

2.1 物理資源與虛擬網絡請求的描述

物理資源和虛擬網絡請求可用無向加權圖表述。物理資源GP，GP=，其中，NP為物理結點集合，EP為物理鏈路集合，權(nP)指結點nP∈NP的屬性（如計算能力），權(eP)指鏈路eP∈EP的屬性（如帶寬大?。?。同理，虛網請求GV，GV=其中，權為虛擬結點的資源需求為虛擬鏈路的資源需求（如請求分配的計算能力和網絡帶寬等）。將GV部署到GP上的虛網映射記為M:GV→GP，其中，節點映射記為MN:NV→NP，鏈路映射記為ME:EV→EP。

2.2 割與k-割檢驗

定義3（割）[21]N，網絡G=(N,E,AN,AE)的結點集合，對N的一個劃分稱為G的一個割。

其中MN(S)={nP|nP=MN(nV),nV∈S}。

定理1（可行性檢驗定理）[22]當且僅當MN通過所有的k-割檢驗，MN有可行的鏈路映射與之對應，其中k∈[1,[|NV|/2]]。

文獻[30]表明，當節點映射MN通過k-割檢驗時，對應存在可行鏈路映射的概率為93.9%，故可排除掉絕大部分不具備相應可行鏈路映射的節點映射。本文所提算法需要k-割檢驗時，都只進行1-割檢驗，1-割檢驗的實例如圖2所示。

圖2 節點資源優先節點映射

2.3 保持節點相鄰的虛擬網絡映射算法

本節提出的算法在略微降低映射效率的情況下，提升了映射成功率和物理資源，特別是物理鏈路得到高效利用，并使虛網請求中相鄰的節點在實際映射后的物理網路中盡可能保持相鄰，從而提升映射后虛擬網絡的運行效率，提高了服務質量并改善了映射效果。具體算法描述如下文。

圖3 給出了虛擬網絡請求和供映射的物理網絡，虛擬網絡請求a，b，c 三個節點的節點需求分別為20，15，10，其間的鏈路需求分別為10，15，20，供映射的物理網絡A，B，C，D，E 五個節點的節點資源分別為40，30，5，10，20，其間的鏈路資源分別為10，30，20，30，15。根據上述算法，首先尋找虛擬網絡請求中節點需求資源最大的節點，即為a 節點，然后尋找物理網絡中節點資源最多的節點，即為A 節點。經過判斷，A節點的節點資源滿足需求，但是不能通過1-割檢驗，所以去除A節點，再在剩余節點中尋找資源最多的節點，即B節點，其能夠滿足a節點的需求，又能通過1-割檢驗，因此將虛擬節點a映射到物理節點B上，并更新B節點剩余資源為10。之后尋找與a節點相鄰的需求資源最多的虛擬節點，即為b節點，a，b節點間的虛擬鏈路需求為10。之后尋找與物理節點B相鄰且之間鏈路能夠滿足鏈路需求的節點，即為A和C，其中節點資源最多的是A節點。經過判斷，A節點既能滿足b節點需求，又能通過1-割檢驗，因此將b節點映射到A節點上，并更新A節點剩余資源為25。之后尋找虛擬網絡請求中與a節點相鄰的、除b節點外的，且節點資源需求最多的節點，即c節點，a，c節點間的虛擬鏈路需求為20。之后尋找物理資源中與B節點相鄰的、能夠滿足鏈路需求的節點中，節點剩余資源最大的節點，即C節點。經過判斷，C節點不能滿足虛擬節點c的節點需求，而有沒有其他與A相鄰的節點，因此將已映射的虛擬節點a，b，物理節點B，A排除，將剩下的節點繼續回到算法最初開始進行。尋找虛擬請求中需求資源最多的虛擬節點，即c節點。之后尋找物理網絡中節點資源最多的節點，即E 節點。經過判斷，物理節點E 能夠滿足虛擬節點c 的節點資源需求，并且能夠通過1-割檢驗，因此將c節點映射到物理節點E上，從而完成映射。算法具體步驟如

圖3 保持節點相鄰的虛擬網絡映射算法實例

步驟1：記虛擬節點集合為N(nV)，物理節點集合為N(nP)；

步驟2：若集合N(nV)為空，則映射成功，結束算法；若集合N(nV)不為空，則尋找集合N(nV)中節點資源要求最高的虛擬節點，記為節點

步驟3：尋找集合N(nP)中剩余節點資源最多的物理節點，若其能夠滿足節點的需求，并且能夠通過1-割檢驗，則將其記為節點若其能夠滿足節點的需求，但不能夠通過1-割檢驗，則將其排除出集合N(nP)，返回步驟3重新執行；若其不能滿足節點的需求，則映射失??；

步驟6：在N()中尋找需求最大的虛擬節點，記為節點，且節點與節點之間的虛擬鏈路為；

步驟8：尋找集合N中節點資源最多的節點，若其不能滿足節點的需求，則將節點排除出集合N，跳至步驟6；若是能夠滿足節點的需求但不能夠通過1-割檢驗，則將其排除出集合N，返回步驟8重新執行；若最終未能找到可行的節點或已不存在滿足鏈路需求的鏈路，則將虛擬節點排除出集合N，跳至步驟6；若尋找到的節點能夠滿足節點的需求且通過1-割檢驗，則將其記為節點若是集合N中所有虛擬節點都已經通過步驟8 但沒有成功映射，則更新集合N(nV)為還未被映射的虛擬節點集合，跳至步驟2；若是集合N中所有虛擬節點都已經通過步驟8且成功映射，則跳至步驟11；

3 實驗分析

3.1 實驗環境

本文采用自主設計的虛擬網絡映射仿真器進行仿真實驗。其中，網絡拓撲情況（包括虛擬網絡請求虛擬節點個數、虛擬節點的節點資源、鏈路狀況、物理節點、鏈路資源等）由GT-ITM[23]隨機生成。仿真器通過設置不同的參數（如虛擬網絡請求虛擬節點個數取值范圍、虛擬節點的節點資源取值范圍等）來模擬不同的虛擬網絡請求與物理網絡環境。在各種情況下，對保持節點相鄰的虛擬網絡映射算法（以下稱本算法）進行仿真，并將其與經典的兩步式虛擬網絡映射算法（以下稱兩步式算法）進行比較。

3.2 仿真實驗結果與分析

（1）虛擬網絡請求與物理網絡環境情況A

根據表1設置，得到仿真結果如圖4～6所示。從映射結果看，在物理資源充足的網絡環境下，兩種算法都有很高的映射成功率，而在保持節點相鄰、提高物理鏈路利用率、優化映射效果的目標來看，本算法雖然會隨虛擬鏈路存在概率的升高（即虛擬網絡請求的拓撲復雜度升高）而降低效果，但始終比兩步式算法高很多，也就是說映射效果要好很多?？梢钥闯?，兩種算法都比較好地做到了節點壓力的均衡，其中兩步式算法表現更為出色一些。

表1 虛擬網絡請求與底層物理網絡的生成相關參數

圖4 映射成功率隨虛擬鏈路存在概率變化

圖5 虛擬網絡請求仍舊相鄰的比率隨虛擬鏈路存在概率變化

圖6 物理節點利用率的方差隨虛擬鏈路存在概率變化

（2）虛擬網絡請求與物理網絡環境情況B

根據表2設置，得到仿真結果如圖7～9所示。從映射結果看，隨著虛擬網絡請求虛擬節點個數取值范圍的增加（即虛擬網絡請求擴大），尤其是虛擬節點個數超過物理節點個數一半時，兩種算法的映射成功率都有明顯下降。當虛擬網絡請求中虛擬鏈路的需求相對于物理鏈路資源較高時，本算法的映射成功率明顯高于兩步式算法。同時，通過圖8 也可得出，當虛擬網絡請求中虛擬鏈路的需求相對于物理鏈路資源較高時，本算法相對于兩步式算法仍可達到一個較好的虛擬網絡請求中相鄰節點映射后仍舊相鄰的比率，也就是能提高虛擬鏈路的利用率，從而達到一個較好的映射效果。由物理節點利用率的方差均較低可以看出，兩種算法都較好地做到了節點壓力的均衡，而其中兩步式算法表現更為出色一些。

表2 虛擬網絡請求與底層物理網絡的生成相關參數

圖7 映射成功率隨虛擬節點個數取值變化

圖8 虛擬網絡請求中仍舊相鄰的比率隨虛擬節點個數取值變化

圖9 物理節點利用率的方差隨虛擬節點個數取值變化

（3）虛擬網絡請求與物理網絡環境情況C

根據表3設置，仿真結果如圖10～12所示。從映射結果看，虛擬網絡請求中虛擬節點資源的取值變化對這兩種算法各方面影響都不是很大。但是，從圖10 可以明顯地反映出在這種情況下本算法映射成功率普遍高于兩步式算法。同時，由圖11可知，本算法映射在提高物理鏈路利用率、提高服務質量、優化映射結果方面要明顯優于兩步式算法。由圖12 可知，虛擬網絡請求中虛擬節點資源的取值范圍的提高會降低節點壓力的均衡程度，雖然上升幅度很大，但絕對數值卻很小，因此可以說兩種算法在節點壓力均衡上都表現良好。

表3 虛擬網絡請求與底層物理網絡的生成相關參數

圖11 虛擬網絡請求中仍舊相鄰的比率隨虛擬節點資源的取值變化

圖12 物理節點利用率的方差隨虛擬節點資源的取值變化

（4）虛擬網絡請求與物理網絡環境情況D

根據表4設置，仿真結果如圖13～15所示。從映射結果看，在虛擬網絡請求中虛擬鏈路資源需求相對于物理鏈路資源較低時，兩種算法都能保證比較高的映射成功率。而當虛擬鏈路資源相對于物理鏈路資源變得較大時，兩種算法的映射成功率都有明顯下降。由圖13可知，本算法的映射成功率在苛刻的鏈路條件下會高于兩步式算法。而作為本算法的主要目標，由圖14可知，虛擬網絡請求中相鄰節點映射后仍舊相鄰的比率在各種虛擬鏈路條件下都比兩步式算法高得多，可見其在提高物理鏈路資源利用率、優化映射結果、提高服務質量方面做得很好。由圖15反映出的較低物理節點利用率的方差可知，兩種算法在節點壓力均衡方面都表現優良，而本算法只是略微遜色一些。

表4 虛擬網絡請求與底層物理網絡的生成相關參數

圖13 映射成功率隨虛擬網絡請求中虛擬鏈路資源的取值變化

圖14 虛擬網絡請求中仍舊相鄰的比率隨虛擬鏈路資源的取值變化

圖15 物理節點利用率的方差隨虛擬鏈路資源的取值變化

4 結束語

相比于經典兩步式算法，本算法在相對物理資源充足、虛擬網絡請求節點資源需求較大、虛擬網絡請求鏈路資源需求較大等幾種情況下都有不錯的映射成功率。在虛擬網絡請求中，只有虛擬鏈路資源需求相對于實際物理鏈路資源要求苛刻時，才會存在比較低的映射成功率。因此，在絕大多數虛擬網絡映射中，本算法可行性比較高，且在虛擬網絡請求中相鄰節點映射后仍舊相鄰的比率在虛擬網絡請求與物理網絡環境情況中都表現出色，同時在提高物理鏈路資源利用率、優化虛擬網絡映射效果、提高映射后的服務質量方面非常好。在對虛擬網絡映射結果要求較高情況下的適用性很高，并且在保持節點壓力均衡方面也較出色，達到了現今對于網絡負載均衡方面的需求。