王慕陽 陳立全　王翔 王延松 盧華

摘要

網絡虛擬化技術通過對物理資源的抽象，可以有效解決現有互聯(lián)網架構中存在的網絡結構僵化、可擴展性差等問題。虛擬網絡映射問題是指將用戶發(fā)送的所有虛網請求映射到底層物理網絡中，同時還要滿足虛網請求中對各個資源的限制要求（如節(jié)點計算能力、鏈路帶寬等）。從節(jié)點負載平衡的角度出發(fā)，在基于就近原則的虛網映射算法基礎上，引入節(jié)點負載平衡的反饋機制，引導各個虛網請求更均勻地映射到底層物理網絡中。另外，在k短路徑算法機制中引入了當前鏈路資源占有率作為評價參考標準，這樣可以盡可能均勻地分散鏈路壓力。同時，在檢驗鏈路資源是否滿足虛網請求的過程中，由于優(yōu)先選中的鏈路資源占有率低，所以算法映射成功率高，映射耗時更短，虛擬網絡映射效率得到了有效提高。關鍵詞網絡虛擬化；虛網映射；占有率反饋；負載平衡；鏈路映射

中圖分類號TP242

文獻標志碼A

收稿日期20160725

資助項目國家自然科學基金（61372103）；中興通訊產學研項目（2015ZTE0413）

作者簡介

王慕陽，男，碩士生，主要研究方向為虛擬網絡映射機制與算法。wangmuyang@seu.edu.cn

陳立全（通信作者），男，博士，副教授，博士生導師，主要研究方向為網絡與信息安全.Lqchen@seu.edu.cn

1東南大學信息科學與工程學院，南京，210096

2中興通訊股份有限公司，深圳，518057

0 引言

網絡虛擬化是為解決網絡結構僵化問題而提出的新興網絡技術。

網絡虛擬化技術的核心是虛擬網絡中節(jié)點和鏈路到物理網絡的映射。在實際應用中，底層物理網絡承載多個虛擬網絡，需要消耗相應的物理資源，包括節(jié)點CPU資源、鏈路帶寬等。當有一個新的虛擬網絡請求需要映射到底層物理網絡上時，有些物理節(jié)點和鏈路已經無法滿足新到來的虛網請求的資源需求，無法在其上映射此虛擬網絡。而且，如果虛擬網絡映射不合理，可能會出現各個節(jié)點之間的數據流量需要經過多個節(jié)點的轉發(fā)，增加額外的帶寬資源消耗，甚至會因為所選節(jié)點之間的鏈路已經沒有足夠的帶寬，而導致映射失敗?？梢姡斍疤摂M網絡發(fā)展急需要設計高效的虛擬網絡映射算法來將虛擬網絡的各個節(jié)點和鏈路映射到物理網絡上，并希望在滿足虛網請求的資源需求的同時，盡可能地提高物理網絡的資源利用率，降低虛網映射的成本。

傳統(tǒng)的虛網映射算法較多是基于啟發(fā)式的兩步映射算法[13]。它們一般先進行節(jié)點映射，再進行鏈路映射。但目前的虛網映射算法大多基于對節(jié)點CPU和鏈路資源的貪心算法，這就導致物理網中具有較高CPU資源的節(jié)點及其周邊節(jié)點會被優(yōu)先映射，從而導致該部分節(jié)點已經飽和而其他節(jié)點還尚未映射的情況發(fā)生，甚至會發(fā)生所有虛網競爭同一片物理網資源的情況，這對某一區(qū)域會形成較大的負載壓力。

除此之外，在兩步映射算法中，優(yōu)化方案的重點往往放在了節(jié)點映射算法中，對于鏈路映射算法，如果不支持路徑切割，則通常采用k短路徑算法作為最常見的鏈路算法模型[4]。k短路徑算法一般選取路徑最短的前k個映射方案，再依次驗證這些路徑是否滿足虛網請求中的鏈路資源要求來實現算法。當底層網絡支持路徑切割時，鏈路映射算法大多是基于多商品流的線性規(guī)劃進行求解[5]。

針對各種拓撲結構，文獻[6]提出了一種針對星狀拓撲的離線的兩階段映射方案，文獻[7]提出了針對流量矩陣的在線的兩階段映射算法，文獻[8]提出了針對星狀和輻射狀拓撲結構的離線的一階段映射算法。這三種算法都是以減少映射開銷為優(yōu)化目標，且在各自的拓撲結構中都能取得不錯的效果，但是在其他拓撲結構，或無明顯拓撲特征的網絡中，上述方法的算法性能并不理想。

文獻[9]提出了重映射的概念，這是一種在線的一階段映射算法。它的優(yōu)化目標是當底層物

理網不再滿足虛網需求，或虛網需求發(fā)生改變時，盡可能地降低虛網重新映射的代價。

為了解決上述問題，本文從節(jié)點負載平衡的角度出發(fā)，在基于就近原則的虛網映射算法[10]的基礎上，引入節(jié)點負載平衡的反饋機制，引導各個虛網請求更加均勻地映射到底層物理網絡中，從而有效避免節(jié)點映射階段資源瓶頸的發(fā)生。另外該算法在k短路徑算法機制[11]中引入了當前鏈路資源占有率作為路徑長度的評價參考標準。這樣，在計算路徑長度的時候，就會將剩余鏈路資源較多的物理路徑優(yōu)先映射，就可以盡可能均勻地分散鏈路壓力。同時，在檢驗鏈路資源是否滿足虛網請求的過程中，由于優(yōu)先選中的鏈路資源占有率低，剩余資源較多，所以算法映射成功率高，耗時較短，虛擬網絡映射的效率得到了有效的提高。

1 基于占有率反饋的虛擬網絡映射

1.1 節(jié)點映射方法

完整的節(jié)點映射算法流程如圖1所示。在本文提出的基于占有率反饋的虛擬網絡映射算法中，首先根據當前的虛網請求，計算虛網請求中各個虛網節(jié)點的請求值（rv），將虛網節(jié)點按照其請求值（rv）從大到小順序進行節(jié)點映射。請求值（rv）是指虛網節(jié)點映射所需的物理資源，其定義為

其中Bw是指虛擬鏈路lv的帶寬需求，Ccpu指的是虛網節(jié)點nv的CPU容量需求，L（nv）是指與虛網節(jié)點nv相連的虛擬鏈路lv的集合，α和β是用于平衡CPU和帶寬的權重調節(jié)參數，一般情況下，α和β的取值范圍在1～3之間，默認α和β取1。式（1）定義了虛網請求中一個虛擬節(jié)點的請求值rv，它象征了這個虛擬節(jié)點在虛網請求中的重要程度，也一定程度上代表了該節(jié)點映射的困難程度。因此在節(jié)點映射過程中，將會優(yōu)先映射rv值較高的虛擬節(jié)點。

在虛網請求中，不斷選取尚未映射的虛網節(jié)點進行節(jié)點映射，選取的順序就按照rv值從高到低選取。每次節(jié)點映射時，先從底層物理網中選擇出剩余CPU資源大于此虛網節(jié)點所需CPU資源的所有物理節(jié)點，作為可供映射的物理節(jié)點，然后計算所有選出的物理網節(jié)點的加權資源值（rwv），將選出的物理網節(jié)點按照加權資源值（rwv）從大到小排序，并將加權資源值（rwv）最大的物理節(jié)點作為當前虛網節(jié)點的映射對象。這樣該節(jié)點的映射過程就算成功了，接著進入下一節(jié)點的映射工作。加權資源值（rwv）是指物理節(jié)點提供資源的能力：

其中，Nneigh是針對底層物理網節(jié)點ns的相關系數，Nneigh為大于1的實數，該參數用來定義兩個物理節(jié)點的相近程度，指數m 表示當前虛網請求中已經映射成功并且映射的物理節(jié)點與ns有直接連接的虛網節(jié)點個數.一個物理節(jié)點的Nmneigh值越高，說明該節(jié)點與當前虛網請求中已經映射的物理節(jié)點集合距離較近，聯(lián)系更密切，有較好的帶寬資源。所以在映射過程中，設計的算法會更傾向于映射該節(jié)點，以提高之后的鏈路映射的成功率。Ooccupy表示物理節(jié)點ns已經被其他虛網請求占用的相關參數，Ooccupy為0到1之間的實數，且隨著Ooccupy的減小，反饋作用得到加強。n表示物理節(jié)點被其他虛網請求占用的次數，一個物理節(jié)點Onoccupy的值越小，說明該節(jié)點已經被其他虛網請求映射的次數越多。出于負載平衡的考慮，設計的算法將更傾向于不再映射該節(jié)點，而是選擇其他尚未被映射的物理節(jié)點。

當無法找到滿足虛網節(jié)點CPU需求的物理節(jié)點時，該節(jié)點映射失敗，整個虛網節(jié)點映射失敗。當所有節(jié)點都完成節(jié)點映射時，該虛網節(jié)點映射成功，準備進入鏈路映射階段。

1.2 鏈路映射方法

在鏈路映射階段，如圖2所示，首先選擇當前未鏈路映射的虛網請求，計算其虛網鏈路的鏈路帶寬Rbw，并從大到小進行排序，其中鏈路帶寬Rbw為虛網請求中，虛網鏈路所需的通信帶寬大小。

根據鏈路帶寬Rbw的排序，依次對每條虛網鏈路進行映射。每次鏈路映射時，先計算底層物理網中任意兩個直接相連的物理節(jié)點的鏈路占用系數，將該系數作為這兩個物理節(jié)點的路徑距離，構成一個新的無向圖Gs′（Ns，Ls，Rls ′）。然后找出待映射鏈路的兩個端點節(jié)點，虛擬節(jié)點1和虛擬節(jié)點2，再分別找到其映射的物理節(jié)點1 和物理節(jié)點2，將這兩個節(jié)點作為源節(jié)點和目標節(jié)點在無向

圖G′s中進行k短路徑的求解，尋找出路徑最短的前k條路徑。

最后，依次判斷這前k條最短路徑是否滿足虛網鏈路的帶寬需求。如果滿足，則將滿足帶寬條件的最短路徑作為虛擬鏈路的映射對象，該虛擬鏈路映射成功，繼續(xù)對下一條虛擬鏈路進行映射。如果在鏈路映射過程中，無法找到滿足虛網鏈路帶寬需求的路徑，則此次虛網鏈路映射失敗。如果虛網中所有的虛擬鏈路都映射成功，則該虛網鏈路映射成功。

在上述鏈路映射算法中，鏈路占用系數定義為：鏈路占用系數=1-鏈路可用帶寬鏈路總帶寬+ε，其中ε根據需要取大于零的值，建議取0.5。無向圖Gs′（Ns，Ls，Rls′）中，Ns為底層物理節(jié)點的集合，Ls為底層物理鏈路的集合，Rls′為底層物理鏈路l的路徑距離，其大小為鏈路占用系數的值。

2 仿真實驗與結果分析

在Matlab上建立仿真環(huán)境。模擬的底層物理網絡共有100個物理節(jié)點，任意兩個物理節(jié)點之間存在鏈路的概率為0.5。這些節(jié)點的CPU資源和鏈路的帶寬值在50和100之間隨機分布。虛擬網絡請求的參數設置參照文獻[1213]。虛網請求的到達頻率是每個時間窗5個請求。對于每個虛網請求，虛擬節(jié)點的數目在2至10之間隨機生成。虛擬網絡中每兩個節(jié)點之間的聯(lián)通概率為0.5。虛擬節(jié)點的CPU值在0和20之間隨機分布，而虛擬鏈路的帶寬值是在0到Bw，max之間隨機分布，其中Bw，max默認取50。整個虛網生存周期取10，拒絕次數取3次。在研究鏈路占用率反饋技術對映射時間的影響時，Bw，max的取值范圍為10～90。

圖3顯示當Nneigh就近系數取1，即不考慮就近因素時，虛網接收率明顯較低，且隨著時間窗的增加，虛網請求不斷到來，虛網接收率持續(xù)降低，直到在8～10個時間窗后，部分映射成功的虛網完成映射周期，結束映射并釋放出物理資源，虛網接收率才逐步穩(wěn)定在0.75至0.8之間。而當Nneigh取2或3時，虛網優(yōu)先映射相鄰的節(jié)點，所以鏈路映射成功率較高，虛網接收率始終維持在較高的0.9，說明虛網所能承受的最大虛網個數提高了，在8～10個時間窗內，還沒有虛網釋放物理資源的時候，物理網絡仍然能較好地映射新到的虛網請求，并且2和3的曲線十分接近，說明Nneigh的值不需要過高，過高對映射性能沒有太大的改觀。

圖4顯示當Ooccupy占用系數取1，即不考慮節(jié)點占用率反饋的時候，虛網接收率開始較高，然后隨著虛網的不斷加入，有一個輕微下滑的過程，最終穩(wěn)定在0.89左右，而當引入節(jié)點占用率反饋機制，并取Ooccupy為0.75時，虛網接收率的一直穩(wěn)定維持在0.91左右，這說明隨著虛網的加入，節(jié)點占有率反饋機制很好地分散了節(jié)點負載壓力，有效緩解了資源瓶頸的產生。但是，若取Ooccupy為0.5，可以看出虛網接收率明顯較低，且有一個明顯的下滑過程。經過分析，這是由于Ooccupy系數取得過小，映射算法過于追求將節(jié)點分散映射，而導致將底層物理網資源碎片化，從而大幅降低映射成功率。這一現象在虛網請求數量較多的時候尤為明顯。

圖5顯示各映射算法在虛網鏈路帶寬最大值Bw，max從10增加到90時對算法運行時間的影響.當Bw，max小于30時，底層物理鏈路資源充足，所有鏈路映射幾乎都是一次成功，所以時間很短，但隨著虛網鏈路繼續(xù)增加，雖然總體趨勢都是映射時間大幅增加，但是相比于隱藏跳數算法[14]、基于網絡拓撲結構[1516]的映射算法、k短路徑的映射算法[11]等其他算法，基于占有率反饋的映射算法在Bw，max在50到70之間的映射時間明顯較短，在這一階段，雖然鏈路資源已經相對不足，但所有映射成功的鏈路基本都是在前幾次映射中就成功的，所以本文提出的算法耗時較短。

圖6顯示各映射算法的物理節(jié)點CPU利用率隨時間窗增加的變化情況.從圖6中看出各個算法的底層物理節(jié)點利用率隨著每個時間窗中虛網請求的到來而不斷上升，并最終趨于穩(wěn)定。其中基于就近原則的映射算法[10]的節(jié)點CPU利用率最高，基于占有率反饋的映射算法次之，相較于前者，基于占有率反饋的映射在優(yōu)化目標上犧牲了部分節(jié)點資源利用率以換取物理節(jié)點的負載平衡?；诰W絡拓撲結構的映射算法[1516]和普通的k短路徑映射算法[11]相對于以上兩種算法的節(jié)點CPU利用率則更低。

3 結束語

本文分析了傳統(tǒng)映射算法的特點和可能存在的缺陷，提出了基于占有率反饋的虛擬網絡資源映射方法，詳細介紹了該算法的主要流程和改進的技術特點，并在仿真實驗中給出了該方法的映射性能的展示。本文所提出的算法在節(jié)點映射階段，在追求節(jié)點CPU資源的同時，創(chuàng)新性地考慮了節(jié)點的負載平衡，在基于就近原則的虛網映射算法的基礎上，引入節(jié)點負載平衡的反饋機制，從而引導各個虛網請求更加均勻地映射到底層物理網絡中，避免了物理網絡中的核心節(jié)點資源被過早耗盡。在鏈路映射階段，本算法在k短路徑算法機制中引入了當前鏈路資源占有率作為評價參考標準，這樣做可以盡可能均勻地分散鏈路壓力，同時在檢驗鏈路資源是否滿足虛網請求的過程中，由于優(yōu)先選中的鏈路資源占有率低，剩余資源較多，算法映射成功率高，耗時更短，虛擬網絡映射的效率得到了極大提高。

參考文獻

References

[1] Lu J，Turner J.Efficient mapping of virtual networks onto a shared substrate[J].Washington University in St Louis，2006，35：24552462

[2] Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112

[3] Chen X H，Li C Z，Jiang Y L.A feedback control approach for energy efficient virtual network embedding[J].Computer Communications，2016，80（15）：1632

[4] Hu X B，Wang M，Hu D，et al.A ripplespreading algorithm for the k shortest paths problem[C]∥The 3rd Global Congress on Intelligent Systems，2012：202208

[5] Ciciriello P，Mottola L，Picco G P.Efficient routing from multiple sources to multiple sinks in wireless sensor networks[C]∥Proceedings of 4th European Conference on Wireless Sensor Networks，2007：3450

[6] Kareche S，Ductor S，Guessoum Z，et al.A new robust heuristic for assigning substrate network resources to virtual networks[C]∥International Conference on Advanced Networking Distributed Systems and Applications，2014：4752

[7] Fan J L，Ammar M H.Dynamic topology configuration in service overlay networks：A study of reconfiguration policies[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112

[8] Wei X H，Li H L，Yang K，et al.Topology aware partial virtual cluster mapping algorithm on shared distributed infrastructures[C]∥IEEE Transactions on Parallel and Distributed Systems，2014，25（10）：27212730

[9] Cai Z P，Liu F，Xiao N，et al.Virtual network embedding for evolving networks[C]∥IEEE Global Telecommunications Conference，2010：15

[10] Liu J，Huang T，Chen J Y，et al.A new algorithm based on the proximity principle for the virtual networking embedding problem[J].Journal of Zhejiang University（Science C），2011，12（11）：910918

[11] Wang F，Man Y，Man L C.Intelligent optimization approach for the k shortest paths problem based on genetic algorithm[C]∥10th International Conference on Natural Computation，2014：219224

[12] Gonzlez A，Barra E，Beghelli A，et al.A subgraph mappingbased algorithm for virtual network allocation over flexible grid networks[C]∥17th International Conference on Transparent Optical Network，2015：14

[13] Zegura E W，Calvert K L，Bhattacharjee S.How to model an internetwork[C]∥Proc 15th IEEE International Conference on Computer Communications，1996：594602

[14] Botero J F，Hesselbach X，Fischer A，et al.Optimal mapping of virtual ne tworks with hidden hops[J].Telecommunication Systems，2012，51（4）：273282

[15] Dhanapala D C，Jayasumana A P.Topology preserving maps extracting layout maps of wireless sensor networks from virtual coordinates[J].IEEE/ACM Transactions on Networking，2014，22（3）：784797

[16] Wang Z M，Wu J X，Wang Y，et al.Survivable virtual network mapping using optimal back up topology in virtualized SDN[J].China Communications，2014，11（2）：2637