虛擬網絡映射最小費用流模型及算法*

陳曉華，李春芝，陳良育，曾振柄

（1.湖州師范學院信息工程學院 湖州313000；2.華東師范大學軟件學院 上海200062；3.上海大學數學系 上海200444）

1 引言

網絡虛擬化[1]，是未來互聯網、云計算和軟件定義網絡的重要技術[2～6]。多個虛擬網絡能夠共享同一底層物理網絡資源。虛擬化技術分割、整合網絡基礎設施資源，使得在不影響現有網絡情況下部署新的網絡架構、協議以及應用成為可能。

隨著網絡虛擬化技術的發展，多路徑虛擬鏈路映射成為網絡虛擬化的重要技術[7]。基于多商品流的虛擬網絡鏈路映射[8]以底層網絡總體資源消耗最低的方式映射虛擬鏈路，取得較好的系統收益。然而基于多商品流的多路徑鏈路映射算法時間復雜度受虛擬網絡以及底層網絡規模影響較大，難以滿足在線虛擬網絡映射的實時性要求；且虛擬網絡請求是一個動態變化的過程。因此研究虛擬網絡映射動態過程，設計有效的虛擬網絡多路徑鏈路映射算法對于保證在線虛擬網絡映射的實時性具有重要意義。

虛擬網絡多路徑鏈路映射主要研究有：

[8]在底層網絡支持路徑分裂基礎上，首次提出了基于多商品流的虛擬網絡多路徑鏈路映射，與單路徑鏈路映射相比取得了更好的底層網絡資源利用率和系統收益；

·參考文獻[9]提出基于最短路徑疊加的虛擬網絡多路徑鏈路映射，降低了虛擬網絡多路徑映射的時間復雜度，但犧牲了底層資源利用率及系統收益。

2 虛擬網絡映射

2.1 虛擬鏈路映射動態過程實例

圖1中，同時到來4個虛擬網絡請求，如圖1（a）～圖1（d）所示。方案一如圖1（e）所示，選擇基于多商品流的映射方案，底層網絡成功映射VN1，導致物理資源耗盡而無法映射VN2、VN3和VN4。而方案二選擇了另外一種方法，如圖1（f）所示，因為無法找到足夠的物理資源而拒絕了VN1，從而保留了足夠的資源，成功映射VN2、VN3和VN4。從靜態角度看，方案一能夠映射較大資源請求的VN1，比方案二優越；但虛擬網絡映射是動態過程，方案二能夠提高較小規模虛擬網絡映射成功率，影響了底層網絡的整體收益，而且方案一的多商品流算法計算復雜度高，并不適合大規模虛擬網絡及底層網絡環境。

2.2 網絡虛擬化的動態特征及代價收益動態倒置現象

網絡虛擬化動態特征包括虛擬網絡、底層網絡和映射算法的動態特征，具體如下。

·虛擬網絡動態特征：虛擬網絡請求的到來時間、存在時間、虛擬網絡節點個數、虛擬鏈路條數、節點CPU、鏈路帶寬等。

·底層網絡動態特征：隨著虛擬網絡請求的到來和離開，底層網絡剩余CPU、鏈路剩余帶寬資源量和分布將會動態變化。

·映射算法動態特征：隨著虛擬網絡請求資源量的變化，在不同映射算法下，底層網絡資源利用率、虛擬網絡接收率、底層網絡鏈路資源利用率和虛擬網絡拓撲大小是不同的。

從圖1可以看出由于虛擬網絡映射的動態特征，使得虛擬網絡映射存在代價收益動態倒置現象，定義如下：假設有A和B兩種不同虛擬網絡映射算法，從單個虛擬網絡映射的靜態角度看，A能夠映射較小虛擬網絡，B能夠映射較大虛擬網絡，A映射花費的代價要高于B；由于底層網絡資源有限，雖然A花費的代價要高于B，但是A能夠映射較多的較小虛擬網絡，使得系統收益高于B，本文稱之為虛擬網絡映射代價收益動態倒置現象。

2.3 虛擬網絡映射模型

虛擬網絡映射是網絡虛擬化主要問題之一，以下介紹底層網絡、虛擬網絡以及虛擬網絡映射模型。

·底層網絡：本文通過無向圖Gs=（Ns，Ls，，對底層網絡建模，其中，Ns為節點集合，Ls為鏈路集合，為節點屬性集合，為鏈路屬性集合。本文設置節點屬性為CPU處理器資源，鏈路屬性為帶寬資源。

·虛擬網絡：與底層網絡相同，本文通過無向圖Gv=（Nv，Lv，，對虛擬網絡建模，其中，Nv為節點集合，Lv為鏈路集合，為節點屬性集合（CPU處理器資源），為鏈路屬性集合（帶寬資源）。

·虛擬網絡映射：把虛擬節點和鏈路映射到滿足虛擬資源需求的底層節點和路徑，可分為節點映射和鏈路映射。節點映射分為：一個虛擬網絡的不同節點不允許映射到同一節點、一個虛擬網絡的不同節點可映射到一個節點。鏈路映射分為單路徑映射以及多路徑映射。本文在一個虛擬網絡的不同節點不允許映射到同一節點以及多路徑鏈路映射情況下，研究虛擬網絡映射。

3 虛擬鏈路映射最小費用流模型及算法

由于多商品流的多路徑映射時間復雜度高，不適合大規模虛擬網絡及底層網絡的虛擬網絡映射。為了滿足大規模虛擬網絡映射在線請求的實時性要求，本文設計了基于最小費用流的多路徑鏈路映射算法。

3.1 最小費用流模型

無向網絡：無向網絡NG=（V，A，C），其中V是節點集合，A是無向邊集合，C是邊容量集合，對于每條邊（i，j）∈A，對應有一個c（i，j）≥0（或簡寫為cij）為邊的容量。

無向網絡流及流量：在NG中，指定一點為源點（記為s），另一點為匯點（記為t），其余的點叫做中間點，坌（i，j）∈A，f={f（i，j）}，滿 足 下 述 條 件 的f稱 為s到t的無向網絡流。

·容量限制條件：坌（i，j）∈A，0≤fij≤cij。

·方向條件：坌i，j∈V，fij=-fji，可行流具有方向性。

·平衡條件：對于中間點，流出量等于流入量，即每個

v（f）稱為f的流量。

最小費用流模型：給定NG，每一條邊（i，j）∈A，給定一個單位流量的費用b（i，j）≥0（簡記為）bij。最小費用流問題就是給定s、t和流量m，求出從s到t的流f滿足流量v（f）=m，并使得流的總輸送費用b（f）=取最小值，即

3.2 基于最小費用流的多路徑映射算法

步驟1調用最小費用流算法找到一條虛擬鏈路的最小費用流映射，直到完成所有虛擬鏈路映射。

步驟2找到一條未映射的虛擬鏈路lv，取出鏈路兩端點v1、v2以及鏈路流量vbw。

步驟3找出lv映射的兩底層結點s1和s2。

步驟4創建無向網絡NG=（V，A，C），設置每條邊的單位流量費用。

步驟5調用最小費用流算法，如果找到s1到s2帶寬流量為vbw的最小費用流f，則將f分配給lv。

其中，步驟4中不同的NG參數及單位流量費用，會產生不同的映射算法，分別為UNMCF-S和UMMCF-L。bw（i，j）表示底層鏈 路l（i，j）剩余的 帶寬總量，bwl（i，j）表示底層鏈路l（i，j）已經映射的帶寬總量。UNMCF-S設置NG及單位流量費用如下：容量c（i，j）=bw（i，j），如果c（i，j）==0，表示節點i與j不存在鏈路；如果bw（i，j）>0，單位流量費用b（i，j）=1；如果bw（i，j）==0，單 位流量費 用b（i，j）=0。UMMCF-L設置NG及單位流量費用如下：容量c（i，j）=bw（i，j），如果c（i，j）==0，表示節點i與j不存在鏈路；b（i，j）=bwl（i，j）。

算法1的時間復雜度為O（e·n2），其中n為物理網絡的節點數，e為虛擬網絡的邊數。

算法1基于最小費用流的虛擬鏈路映射算法

輸入：虛擬網絡VN,底層網絡SN；

輸出：虛擬網絡多路徑映射結果；

（1）while（VN存在鏈路未分配）do

（2）取一條未分配虛擬鏈路1v：（v1，v2，vbw）；

（3）找到虛擬節點（v1，v2）對應底層節點（s1，s2）；

（4）創建NG，設置每條邊的單位流量費用；

（5）if（調用最小費用流算法找到了s1到s2及帶寬流量vbw的最小費用流f）

（6）映射虛擬鏈路1v到底層網絡最小費用流f；

（7）else return null；

（8）end if

（9）end while

（10）return虛擬鏈路多路徑映射結果

4 性能評估

本節評估虛擬網絡多路徑映射，首先介紹性能評價指標及仿真環境，然后對仿真結果進行說明和評估。

4.1 性能指標

與參考文獻[8]一致，本文定義收益成本比、系統收益、虛擬網絡接收率以及映射時間作為性能指標。

（1）收益成本比

定義R（Gv（t））為系統收益：R（Gv（t））CPU（nv），其中，為接收的虛擬網絡鏈路帶寬總和，為接收的虛擬網絡節點CPU總和。定義C（Gv（t））為虛擬網絡映射代價：C（Gv（t））為接收的虛擬鏈路lv對應底層網絡路徑的帶寬總和，fp為接收的虛擬鏈路lv對應底層網絡路徑上的鏈路；定義平均收益成本比為

（2）系統收益

（3）虛擬網絡接收率

（4）映射時間

定義在T個時間窗內完成虛擬網絡請求映射所花費的時間。

4.2 仿真環境

因為多商品流算法受虛擬網絡以及底層網絡規模影響較大，本文采用GT-ITM工具隨機生成一個由50個節點、約140條鏈路組成的較小底層網絡拓撲。底層網絡節點CPU資源和鏈路帶寬資源服從50～100的均勻分布。每個時間窗為100個時間單元。虛擬網絡請求過程模擬泊松過程，在每個時間窗內虛擬網絡請求到達個數服從均值為20的泊松分布，每個虛擬網絡的生存時間服從均值為5個時間窗的指數分布，每個虛擬網絡請求節點個數服從2～8的均勻分布，每對虛擬網絡節點以0.5的概率相連；設置虛擬網絡節點CPU資源與鏈路帶寬資源需求服從0～40的均勻分布，虛擬網絡映射等待時間為1個時間窗。每次模擬試驗運行約25 000個時間單元，包含5 000個虛擬網絡請求。實驗在10個不同實例運行，取平均值作為結果。為了評價虛擬網絡多路徑鏈路映射結果，本文設置節點映射為貪心算法，多路徑鏈路映射分別采用本文提出的UNMCF-S、UNMCF-L以及多商品流鏈路映射算法MCF[8]。因為最短路徑疊加算法[9]較MCF算法系統收益小，本文不與之比較。

4.3 虛擬網絡映射仿真結果

（1）基于最小費用流的虛擬網絡映射算法提高了系統收益及虛擬網絡接收率

圖2、圖3表明UNMCF-S、UNMCF-L與MCF比較，本文所提算法的系統收益及虛擬網絡接收率得到提高。例如在映射1 000個虛擬網絡時，MCF算法的系統收益為10.739 51，而UNMCF-S算法提高到11.691 41。同時MCF算法的虛擬網絡接收率為0.305 31，而UNMCF-S及UNMCF-L算法的虛擬網絡接收率為0.40，較MCF提高了10%。這是由于虛擬網絡映射具有動態性，本文所提算法能夠映射更多的較小規模虛擬網絡，即提高虛擬網絡接收率，從而提高了系統收益。圖2、圖3也驗證了虛擬網絡映射代價收益動態倒置現象的存在。

（2）基于最小費用流的虛擬網絡映射算法極大地降低了映射時間

基于最小費用流映射算法的時間復雜度低于基于多商品流映射算法，其更適合在線虛擬網絡映射。以圖4可以看出，基于多商品流映射算法需要首先找到是否有解，然后找到最優解，雖然收益成本比值較基于最小費用流映射算法高（如圖5所示），但是映射時間遠遠超過基于最小費用流的映射算法。

5 結束語

本文分析了虛擬網絡映射動態過程，發現了虛擬網絡映射代價收益動態倒置現象。基于此，提出虛擬網絡多路徑鏈路映射的最小費用流模型，設置單位流量映射費用單價，進而設計基于最小費用流的最小代價、最小負載虛擬網絡多路徑鏈路映射算法，提高了虛擬網絡接收率及系統收益，有效降低了算法時間復雜度，保證了在線虛擬網絡映射的實時性要求，適用于在大規模底層網絡上創建虛擬網絡。

致謝本文仿真實驗在C3S2服務器完成，感謝湖州師范學院C3S2計算中心的大力支持。

參考文獻

1 Chowdhury N M M K,Boutaba R.Network virtualization:state of the art and research challenges.IEEE Communications Magazine,2009,47（7）:20～26

2 Anderson T,Peterson L,Shenker S,et al.Overcoming the internet impass through virtualization.IEEE Computer Magazine,2005,38（4）:34～41

3 Sun G,Anand V,Yu H F,et al.Optimal provisioning for elastic service oriented virtual network request in cloud computing.Proceedings of Global Communications Conference（GLOBECOM）,Anaheim,CA,2012:2541～46

4 Drutskoy D,Keller E,Rexford J.Scalable network virtualization in software-defined networks.IEEE Internet Computing,2013,17(2):21～27

5 Sharkh M A,Jammal M,Shami A,et al.Resource allocation in a network-based cloud computing environment:design challenges.IEEE Communications Magazine,2013,51（11）:46～52

6 Wei X L,Chen M,Fan J H,et al.Architecture of the data center network.Journal of Software,2013,24（2）:295～316

7 Fischer A,Botero J,Beck M,et al.Virtual network embedding:a survey.IEEE Communications Surveys and Tutorials,2013,15（4）:1888～1906

8 Yu M,Yi Y,Rexford J,et al.Rethinking virtual network embedding:substrate support for path splitting and migration.Proceedings of Computer Communication Review,2008,38（2）:17～27

9 Zhang Z,Cheng X,Su S,et al.A unified enhanced particle swarm optimization-based virtual network embedding algorithm.International Journal of Communication Systems,2013,26(8):1054～1073