虛擬網(wǎng)絡(luò)映射最小費(fèi)用流模型及算法*

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

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

1 引言

網(wǎng)絡(luò)虛擬化[1]，是未來(lái)互聯(lián)網(wǎng)、云計(jì)算和軟件定義網(wǎng)絡(luò)的重要技術(shù)[2～6]。多個(gè)虛擬網(wǎng)絡(luò)能夠共享同一底層物理網(wǎng)絡(luò)資源。虛擬化技術(shù)分割、整合網(wǎng)絡(luò)基礎(chǔ)設(shè)施資源，使得在不影響現(xiàn)有網(wǎng)絡(luò)情況下部署新的網(wǎng)絡(luò)架構(gòu)、協(xié)議以及應(yīng)用成為可能。

隨著網(wǎng)絡(luò)虛擬化技術(shù)的發(fā)展，多路徑虛擬鏈路映射成為網(wǎng)絡(luò)虛擬化的重要技術(shù)[7]。基于多商品流的虛擬網(wǎng)絡(luò)鏈路映射[8]以底層網(wǎng)絡(luò)總體資源消耗最低的方式映射虛擬鏈路，取得較好的系統(tǒng)收益。然而基于多商品流的多路徑鏈路映射算法時(shí)間復(fù)雜度受虛擬網(wǎng)絡(luò)以及底層網(wǎng)絡(luò)規(guī)模影響較大，難以滿足在線虛擬網(wǎng)絡(luò)映射的實(shí)時(shí)性要求；且虛擬網(wǎng)絡(luò)請(qǐng)求是一個(gè)動(dòng)態(tài)變化的過(guò)程。因此研究虛擬網(wǎng)絡(luò)映射動(dòng)態(tài)過(guò)程，設(shè)計(jì)有效的虛擬網(wǎng)絡(luò)多路徑鏈路映射算法對(duì)于保證在線虛擬網(wǎng)絡(luò)映射的實(shí)時(shí)性具有重要意義。

虛擬網(wǎng)絡(luò)多路徑鏈路映射主要研究有：

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

·參考文獻(xiàn)[9]提出基于最短路徑疊加的虛擬網(wǎng)絡(luò)多路徑鏈路映射，降低了虛擬網(wǎng)絡(luò)多路徑映射的時(shí)間復(fù)雜度，但犧牲了底層資源利用率及系統(tǒng)收益。

2 虛擬網(wǎng)絡(luò)映射

2.1 虛擬鏈路映射動(dòng)態(tài)過(guò)程實(shí)例

圖1中，同時(shí)到來(lái)4個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，如圖1（a）～圖1（d）所示。方案一如圖1（e）所示，選擇基于多商品流的映射方案，底層網(wǎng)絡(luò)成功映射VN1，導(dǎo)致物理資源耗盡而無(wú)法映射VN2、VN3和VN4。而方案二選擇了另外一種方法，如圖1（f）所示，因?yàn)闊o(wú)法找到足夠的物理資源而拒絕了VN1，從而保留了足夠的資源，成功映射VN2、VN3和VN4。從靜態(tài)角度看，方案一能夠映射較大資源請(qǐng)求的VN1，比方案二優(yōu)越；但虛擬網(wǎng)絡(luò)映射是動(dòng)態(tài)過(guò)程，方案二能夠提高較小規(guī)模虛擬網(wǎng)絡(luò)映射成功率，影響了底層網(wǎng)絡(luò)的整體收益，而且方案一的多商品流算法計(jì)算復(fù)雜度高，并不適合大規(guī)模虛擬網(wǎng)絡(luò)及底層網(wǎng)絡(luò)環(huán)境。

2.2 網(wǎng)絡(luò)虛擬化的動(dòng)態(tài)特征及代價(jià)收益動(dòng)態(tài)倒置現(xiàn)象

網(wǎng)絡(luò)虛擬化動(dòng)態(tài)特征包括虛擬網(wǎng)絡(luò)、底層網(wǎng)絡(luò)和映射算法的動(dòng)態(tài)特征，具體如下。

·虛擬網(wǎng)絡(luò)動(dòng)態(tài)特征：虛擬網(wǎng)絡(luò)請(qǐng)求的到來(lái)時(shí)間、存在時(shí)間、虛擬網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)、虛擬鏈路條數(shù)、節(jié)點(diǎn)CPU、鏈路帶寬等。

·底層網(wǎng)絡(luò)動(dòng)態(tài)特征：隨著虛擬網(wǎng)絡(luò)請(qǐng)求的到來(lái)和離開，底層網(wǎng)絡(luò)剩余CPU、鏈路剩余帶寬資源量和分布將會(huì)動(dòng)態(tài)變化。

·映射算法動(dòng)態(tài)特征：隨著虛擬網(wǎng)絡(luò)請(qǐng)求資源量的變化，在不同映射算法下，底層網(wǎng)絡(luò)資源利用率、虛擬網(wǎng)絡(luò)接收率、底層網(wǎng)絡(luò)鏈路資源利用率和虛擬網(wǎng)絡(luò)拓?fù)浯笮∈遣煌摹?/p>

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

2.3 虛擬網(wǎng)絡(luò)映射模型

虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化主要問(wèn)題之一，以下介紹底層網(wǎng)絡(luò)、虛擬網(wǎng)絡(luò)以及虛擬網(wǎng)絡(luò)映射模型。

·底層網(wǎng)絡(luò)：本文通過(guò)無(wú)向圖Gs=（Ns，Ls，，對(duì)底層網(wǎng)絡(luò)建模，其中，Ns為節(jié)點(diǎn)集合，Ls為鏈路集合，為節(jié)點(diǎn)屬性集合，為鏈路屬性集合。本文設(shè)置節(jié)點(diǎn)屬性為CPU處理器資源，鏈路屬性為帶寬資源。

·虛擬網(wǎng)絡(luò)：與底層網(wǎng)絡(luò)相同，本文通過(guò)無(wú)向圖Gv=（Nv，Lv，，對(duì)虛擬網(wǎng)絡(luò)建模，其中，Nv為節(jié)點(diǎn)集合，Lv為鏈路集合，為節(jié)點(diǎn)屬性集合（CPU處理器資源），為鏈路屬性集合（帶寬資源）。

·虛擬網(wǎng)絡(luò)映射：把虛擬節(jié)點(diǎn)和鏈路映射到滿足虛擬資源需求的底層節(jié)點(diǎn)和路徑，可分為節(jié)點(diǎn)映射和鏈路映射。節(jié)點(diǎn)映射分為：一個(gè)虛擬網(wǎng)絡(luò)的不同節(jié)點(diǎn)不允許映射到同一節(jié)點(diǎn)、一個(gè)虛擬網(wǎng)絡(luò)的不同節(jié)點(diǎn)可映射到一個(gè)節(jié)點(diǎn)。鏈路映射分為單路徑映射以及多路徑映射。本文在一個(gè)虛擬網(wǎng)絡(luò)的不同節(jié)點(diǎn)不允許映射到同一節(jié)點(diǎn)以及多路徑鏈路映射情況下，研究虛擬網(wǎng)絡(luò)映射。

3 虛擬鏈路映射最小費(fèi)用流模型及算法

由于多商品流的多路徑映射時(shí)間復(fù)雜度高，不適合大規(guī)模虛擬網(wǎng)絡(luò)及底層網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)映射。為了滿足大規(guī)模虛擬網(wǎng)絡(luò)映射在線請(qǐng)求的實(shí)時(shí)性要求，本文設(shè)計(jì)了基于最小費(fèi)用流的多路徑鏈路映射算法。

3.1 最小費(fèi)用流模型

無(wú)向網(wǎng)絡(luò)：無(wú)向網(wǎng)絡(luò)NG=（V，A，C），其中V是節(jié)點(diǎn)集合，A是無(wú)向邊集合，C是邊容量集合，對(duì)于每條邊（i，j）∈A，對(duì)應(yīng)有一個(gè)c（i，j）≥0（或簡(jiǎn)寫為cij）為邊的容量。

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

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

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

·平衡條件：對(duì)于中間點(diǎn)，流出量等于流入量，即每個(gè)

v（f）稱為f的流量。

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

3.2 基于最小費(fèi)用流的多路徑映射算法

步驟1調(diào)用最小費(fèi)用流算法找到一條虛擬鏈路的最小費(fèi)用流映射，直到完成所有虛擬鏈路映射。

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

步驟3找出lv映射的兩底層結(jié)點(diǎn)s1和s2。

步驟4創(chuàng)建無(wú)向網(wǎng)絡(luò)NG=（V，A，C），設(shè)置每條邊的單位流量費(fèi)用。

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

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

算法1的時(shí)間復(fù)雜度為O（e·n2），其中n為物理網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，e為虛擬網(wǎng)絡(luò)的邊數(shù)。

算法1基于最小費(fèi)用流的虛擬鏈路映射算法

輸入：虛擬網(wǎng)絡(luò)VN,底層網(wǎng)絡(luò)SN；

輸出：虛擬網(wǎng)絡(luò)多路徑映射結(jié)果；

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

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

（3）找到虛擬節(jié)點(diǎn)（v1，v2）對(duì)應(yīng)底層節(jié)點(diǎn)（s1，s2）；

（4）創(chuàng)建NG，設(shè)置每條邊的單位流量費(fèi)用；

（5）if（調(diào)用最小費(fèi)用流算法找到了s1到s2及帶寬流量vbw的最小費(fèi)用流f）

（6）映射虛擬鏈路1v到底層網(wǎng)絡(luò)最小費(fèi)用流f；

（7）else return null；

（8）end if

（9）end while

（10）return虛擬鏈路多路徑映射結(jié)果

4 性能評(píng)估

本節(jié)評(píng)估虛擬網(wǎng)絡(luò)多路徑映射，首先介紹性能評(píng)價(jià)指標(biāo)及仿真環(huán)境，然后對(duì)仿真結(jié)果進(jìn)行說(shuō)明和評(píng)估。

4.1 性能指標(biāo)

與參考文獻(xiàn)[8]一致，本文定義收益成本比、系統(tǒng)收益、虛擬網(wǎng)絡(luò)接收率以及映射時(shí)間作為性能指標(biāo)。

（1）收益成本比

定義R（Gv（t））為系統(tǒng)收益：R（Gv（t））CPU（nv），其中，為接收的虛擬網(wǎng)絡(luò)鏈路帶寬總和，為接收的虛擬網(wǎng)絡(luò)節(jié)點(diǎn)CPU總和。定義C（Gv（t））為虛擬網(wǎng)絡(luò)映射代價(jià)：C（Gv（t））為接收的虛擬鏈路lv對(duì)應(yīng)底層網(wǎng)絡(luò)路徑的帶寬總和，fp為接收的虛擬鏈路lv對(duì)應(yīng)底層網(wǎng)絡(luò)路徑上的鏈路；定義平均收益成本比為

（2）系統(tǒng)收益

（3）虛擬網(wǎng)絡(luò)接收率

（4）映射時(shí)間

定義在T個(gè)時(shí)間窗內(nèi)完成虛擬網(wǎng)絡(luò)請(qǐng)求映射所花費(fèi)的時(shí)間。

4.2 仿真環(huán)境

因?yàn)槎嗌唐妨魉惴ㄊ芴摂M網(wǎng)絡(luò)以及底層網(wǎng)絡(luò)規(guī)模影響較大，本文采用GT-ITM工具隨機(jī)生成一個(gè)由50個(gè)節(jié)點(diǎn)、約140條鏈路組成的較小底層網(wǎng)絡(luò)拓?fù)洹５讓泳W(wǎng)絡(luò)節(jié)點(diǎn)CPU資源和鏈路帶寬資源服從50～100的均勻分布。每個(gè)時(shí)間窗為100個(gè)時(shí)間單元。虛擬網(wǎng)絡(luò)請(qǐng)求過(guò)程模擬泊松過(guò)程，在每個(gè)時(shí)間窗內(nèi)虛擬網(wǎng)絡(luò)請(qǐng)求到達(dá)個(gè)數(shù)服從均值為20的泊松分布，每個(gè)虛擬網(wǎng)絡(luò)的生存時(shí)間服從均值為5個(gè)時(shí)間窗的指數(shù)分布，每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求節(jié)點(diǎn)個(gè)數(shù)服從2～8的均勻分布，每對(duì)虛擬網(wǎng)絡(luò)節(jié)點(diǎn)以0.5的概率相連；設(shè)置虛擬網(wǎng)絡(luò)節(jié)點(diǎn)CPU資源與鏈路帶寬資源需求服從0～40的均勻分布，虛擬網(wǎng)絡(luò)映射等待時(shí)間為1個(gè)時(shí)間窗。每次模擬試驗(yàn)運(yùn)行約25 000個(gè)時(shí)間單元，包含5 000個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求。實(shí)驗(yàn)在10個(gè)不同實(shí)例運(yùn)行，取平均值作為結(jié)果。為了評(píng)價(jià)虛擬網(wǎng)絡(luò)多路徑鏈路映射結(jié)果，本文設(shè)置節(jié)點(diǎn)映射為貪心算法，多路徑鏈路映射分別采用本文提出的UNMCF-S、UNMCF-L以及多商品流鏈路映射算法MCF[8]。因?yàn)樽疃搪窂蒋B加算法[9]較MCF算法系統(tǒng)收益小，本文不與之比較。

4.3 虛擬網(wǎng)絡(luò)映射仿真結(jié)果

（1）基于最小費(fèi)用流的虛擬網(wǎng)絡(luò)映射算法提高了系統(tǒng)收益及虛擬網(wǎng)絡(luò)接收率

圖2、圖3表明UNMCF-S、UNMCF-L與MCF比較，本文所提算法的系統(tǒng)收益及虛擬網(wǎng)絡(luò)接收率得到提高。例如在映射1 000個(gè)虛擬網(wǎng)絡(luò)時(shí)，MCF算法的系統(tǒng)收益為10.739 51，而UNMCF-S算法提高到11.691 41。同時(shí)MCF算法的虛擬網(wǎng)絡(luò)接收率為0.305 31，而UNMCF-S及UNMCF-L算法的虛擬網(wǎng)絡(luò)接收率為0.40，較MCF提高了10%。這是由于虛擬網(wǎng)絡(luò)映射具有動(dòng)態(tài)性，本文所提算法能夠映射更多的較小規(guī)模虛擬網(wǎng)絡(luò)，即提高虛擬網(wǎng)絡(luò)接收率，從而提高了系統(tǒng)收益。圖2、圖3也驗(yàn)證了虛擬網(wǎng)絡(luò)映射代價(jià)收益動(dòng)態(tài)倒置現(xiàn)象的存在。

（2）基于最小費(fèi)用流的虛擬網(wǎng)絡(luò)映射算法極大地降低了映射時(shí)間

基于最小費(fèi)用流映射算法的時(shí)間復(fù)雜度低于基于多商品流映射算法，其更適合在線虛擬網(wǎng)絡(luò)映射。以圖4可以看出，基于多商品流映射算法需要首先找到是否有解，然后找到最優(yōu)解，雖然收益成本比值較基于最小費(fèi)用流映射算法高（如圖5所示），但是映射時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)基于最小費(fèi)用流的映射算法。

5 結(jié)束語(yǔ)

本文分析了虛擬網(wǎng)絡(luò)映射動(dòng)態(tài)過(guò)程，發(fā)現(xiàn)了虛擬網(wǎng)絡(luò)映射代價(jià)收益動(dòng)態(tài)倒置現(xiàn)象。基于此，提出虛擬網(wǎng)絡(luò)多路徑鏈路映射的最小費(fèi)用流模型，設(shè)置單位流量映射費(fèi)用單價(jià)，進(jìn)而設(shè)計(jì)基于最小費(fèi)用流的最小代價(jià)、最小負(fù)載虛擬網(wǎng)絡(luò)多路徑鏈路映射算法，提高了虛擬網(wǎng)絡(luò)接收率及系統(tǒng)收益，有效降低了算法時(shí)間復(fù)雜度，保證了在線虛擬網(wǎng)絡(luò)映射的實(shí)時(shí)性要求，適用于在大規(guī)模底層網(wǎng)絡(luò)上創(chuàng)建虛擬網(wǎng)絡(luò)。

致謝本文仿真實(shí)驗(yàn)在C3S2服務(wù)器完成，感謝湖州師范學(xué)院C3S2計(jì)算中心的大力支持。

參考文獻(xiàn)

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