鄒曉輝 孫靜

摘要：網(wǎng)絡(luò)虛擬化是解決網(wǎng)絡(luò)僵化問題和更好地共享底層網(wǎng)絡(luò)資源的一種有效途徑，虛擬網(wǎng)絡(luò)映射是實施網(wǎng)絡(luò)虛擬化的關(guān)鍵問題之一。虛擬網(wǎng)絡(luò)映射包括節(jié)點映射和鏈路映射兩個方面，其目標(biāo)是為虛擬網(wǎng)絡(luò)請求分配合適的底層網(wǎng)絡(luò)節(jié)點和鏈路資源。闡述了底層網(wǎng)絡(luò)支持路徑分割時，如何基于多商品流模型實現(xiàn)VN鏈路映射。

關(guān)鍵詞：網(wǎng)絡(luò)虛擬化； 虛擬網(wǎng)絡(luò)映射； 鏈路映射； 多商品流

中圖分類號：TP3932 文獻(xiàn)標(biāo)識碼：A文章編號：2095-2163（2013）06-0107-02

0引言

資源虛擬化通過整合底層基礎(chǔ)設(shè)施的分散資源，為上層服務(wù)提供統(tǒng)一的資源池，實現(xiàn)底層資源共享和透明訪問，提高資源利用率，簡化資源管理。目前，計算虛擬化、存儲虛擬化技術(shù)等已經(jīng)相對成熟，并在實踐中得到廣泛應(yīng)用。網(wǎng)絡(luò)虛擬化作為解決網(wǎng)絡(luò)僵化問題和更好地共享底層網(wǎng)絡(luò)資源的一種有效途徑，近幾年來已經(jīng)得到業(yè)界和國內(nèi)外學(xué)者的廣泛關(guān)注，但由于網(wǎng)絡(luò)資源的特殊性，網(wǎng)絡(luò)虛擬化的實質(zhì)性研究還處于起步階段。

在網(wǎng)絡(luò)虛擬化技術(shù)中，虛擬網(wǎng)絡(luò)映射問題是非常重要的研究方向之一。網(wǎng)絡(luò)虛擬化通過共享底層網(wǎng)絡(luò)基礎(chǔ)設(shè)施（Substrate Network，SN），可以在其上部署多重異構(gòu)的虛擬網(wǎng)絡(luò)（Virtual Network，VN），各VN彼此隔離，并分別運(yùn)行各自的協(xié)議、擁有各自的架構(gòu)。VN由虛擬節(jié)點和虛擬鏈路構(gòu)成，VN映射問題就是為各VN請求分配SN的節(jié)點和鏈路資源，將虛擬節(jié)點和虛擬鏈路分別映射至合適的底層物理節(jié)點和物理路徑上。整個虛擬網(wǎng)絡(luò)映射問題可以分解為節(jié)點映射和鏈路映射兩個方面。

由于物理資源的有限性，隨著虛擬網(wǎng)絡(luò)請求的部署和服務(wù)結(jié)束后資源的釋放，形成了很多資源碎片。當(dāng)SN支持路徑分割時，為充分利用這些資源碎片和避免出現(xiàn)瓶頸鏈路，可以將一條VN鏈路的帶寬需求進(jìn)行分割，并將一條虛擬鏈路分流到具有相同起點和終點的多條物理路徑上，實現(xiàn)多徑映射[1]。多徑映射還可以提高VN鏈路的可靠性，當(dāng)一條物理路徑發(fā)生擁塞或失效時，可以將該路徑上的網(wǎng)絡(luò)流量遷移到其它路徑上。

本文第1節(jié)給出了當(dāng)SN支持路徑分割時的虛擬鏈路映射模型，第2節(jié)闡述了多商品流問題原理及基于多商品流模型的虛擬鏈路映射，第3節(jié)對本文進(jìn)行了總結(jié)。

1底層網(wǎng)絡(luò)支持路徑分割的虛擬鏈路映射模型

設(shè)VN請求的虛擬鏈路集合LV={lv1，lv2，…，lvk}，lvi=（nvsi，nvti，di），lvi表示集合中的第i個虛擬鏈路，其中nvsi和nvti為虛擬鏈路lvi的兩個端點，di表示虛擬鏈路lvi的帶寬需求。nvsi和nvti分別映射到底層物理節(jié)點Nsi，Nti。設(shè)Pi=（pi1，pi2，…，pih）為Nsi和Nti之間的物理路徑集合，在底層網(wǎng)絡(luò)支持路徑分割的情況下，可以將虛擬鏈路lvi的帶寬需求分布到Pi的多條物理路徑上，由多條物理路徑承載虛擬鏈路的網(wǎng)絡(luò)流量，可以表示為M（lvi）=（pi1，pi2，…，pih）。每條物理路徑可以包含多個相連的物理鏈路，即pij={（Nsi，Nij1），（Nij1，Nij2），…，（Nijm，Nti）}，其中1≤j≤h，每個物理鏈路用其部分帶寬容量承載映射到其上的虛擬鏈路，并且在帶寬容量有限的情況下每個物理鏈路可以承載多個虛擬鏈路的網(wǎng)絡(luò)流。圖1為底層網(wǎng)絡(luò)支持路徑分割的虛擬鏈路映射示例。

圖1中，左圖為VN請求拓?fù)?，右圖為物理網(wǎng)絡(luò)拓?fù)洌驗楸疚闹挥懻撎摂M鏈路映射，所以忽略了節(jié)點映射約束。其中六邊型結(jié)點代表虛擬節(jié)點，虛擬節(jié)點之間的連線代表虛擬鏈路，虛擬鏈路上的數(shù)字表示其帶寬需求；圓形結(jié)點代表底層網(wǎng)絡(luò)中的物理節(jié)點，物理節(jié)點之間的實線連接代表物理鏈路，物理鏈路上的數(shù)字表示其可用帶寬，物理節(jié)點之間的虛線代表虛擬鏈路映射到的物理路徑。映射結(jié)果如圖中所示，即節(jié)點映射為{a→A，b→B，c→D}，鏈路映射為{（a，b）→（A，B），（a，b）→{（A，F(xiàn)），（F，C），（C，B）}，（b，c）→{（B，C），（C，D）}，（c，a）→{（D，E），（E，A）}}。由于（a，b）的帶寬需求在一條物理路徑上無法滿足，所以（a，b）多徑映射到兩條物理路徑（A，B）和{（A，F(xiàn)），（F，C），（C，B）}，物理鏈路（B，C）承載了兩個虛擬鏈路（a，b）和（b，c）的網(wǎng)絡(luò)流。

2基于多商品流的虛擬鏈路映射

2.1 多商品流問題

多商品流問題是指多種商品流（或物質(zhì)）在網(wǎng)絡(luò)中從不同的源端向不同的目的端進(jìn)行傳輸?shù)木W(wǎng)絡(luò)流問題，是一個多源多匯問題。可以定義如下：

設(shè)G=（N，L）表示一商品流網(wǎng)絡(luò)，其中N表示網(wǎng)絡(luò)節(jié)點的集合，L表示網(wǎng)絡(luò)鏈路的集合，鏈路（u，v）∈L的容量為C（u，v）。設(shè)有k個商品流fi（1≤i≤k）經(jīng)過網(wǎng)絡(luò)G，商品流fi的源節(jié)點和目的節(jié)點分別為si和ti，需求為di，fi（u，v）表示商品流fi在鏈路（u，v）上分布的流量值。則多商品流問題是一個滿足以下約束條件[2]的流量分配問題：

其中，式（1）是網(wǎng)絡(luò)鏈路容量約束，表示所有商品流fi（1≤i≤k）分布到鏈路（u，v）上的流量之和不能超過鏈路（u，v）的容量；式（2）是商品流fi需求約束，表示所有鏈路上承載的商品流fi的流量之和滿足商品流fi的需求；式（3）是流守恒約束，表示在網(wǎng)絡(luò)的中間節(jié)點進(jìn)口流量總和等于出口流量總和。

根據(jù)VN鏈路映射與多商品流問題的相似性，VN映射請求拓?fù)渲械木哂腥萘考s束的一條虛擬鏈路lvi可以對應(yīng)多商品流問題中的一個商品流fi，lvi的兩個端點對應(yīng)fi的源點和匯點，則VN虛擬鏈路映射問題可以建模為多商品流問題進(jìn)行求解。

2.2基于多商品流模型的虛擬鏈路映射

設(shè)計VN映射算法通?；谀硞€目標(biāo)函數(shù)，如最大化映射收益、最小化映射開銷、提高虛擬網(wǎng)絡(luò)請求接受率等。基于多商品流模型的虛擬鏈路映射算法結(jié)合某個目標(biāo)函數(shù)與相應(yīng)的流量分配約束，其求解是線性規(guī)劃問題。

如前所述，忽略VN請求的節(jié)點約束，將VN請求表示成虛擬鏈路的集合，即R={（nvs1，nvt1，d1），（nvs2，nvt2，d2），…，（nvsk，nvtk，dk）}，把底層物理網(wǎng)絡(luò)SN形式化為無向有權(quán)圖GS=（NS，LS，ASL），其中NS表示底層節(jié)點集合，LS表示底層鏈路集合，ASL表示底層鏈路屬性集合（如鏈路帶寬），虛擬鏈路lvi的兩個端點nvsi和nvti分別映射到底層節(jié)點Nsi，Nti。令c（u，v）為物理鏈路（u，v）的單位帶寬代價，（u，v）∈LS，令r（u，v）表示物理鏈路（u，v）的可用帶寬，fi（u，v）表示物理鏈路（u，v）承載的第i個虛擬鏈路的流量。

基于多商品流問題的約束條件，以最小化映射開銷為目標(biāo)，基于多商品流模型的虛擬鏈路映射線性規(guī)劃如下：

具體映射結(jié)果可以采用線性規(guī)劃工具glpk求解。對于具體的VN映射請求，可以根據(jù)實際情況合理設(shè)置目標(biāo)函數(shù)、調(diào)整或增加約束條件，從而得到更優(yōu)化的映射方案。

3結(jié)束語

多商品流模型可以用來求解多源多匯問題，如鐵路網(wǎng)車流分配、通信網(wǎng)帶寬分配、多商品物流網(wǎng)絡(luò)設(shè)計等。對于鏈路映射通常采用k短路徑算法或基于多商品流的線性規(guī)劃方法[3-5]。虛擬鏈路的單徑映射是NP-hard問題，當(dāng)?shù)讓泳W(wǎng)絡(luò)支持路徑分割時，虛擬鏈路的多徑映射建模為基于多商品流模型的線性規(guī)劃問題降低了映射復(fù)雜度。虛擬鏈路的多徑映射，不僅可以實現(xiàn)負(fù)載均衡，當(dāng)?shù)讓游锢礞溌肥r，還可以通過鏈路遷移[6]，將失效鏈路上的網(wǎng)絡(luò)流遷移到其他可用鏈路上，從而提高VN鏈路的可靠性。

參考文獻(xiàn)：

[1]YU ML， YI Y， REXFORD J， et al. Rethinking virtual network embedding： Substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review， 2008，38（2）.

[2]劉志文. 網(wǎng)絡(luò)虛擬化環(huán)境下資源管理關(guān)鍵技術(shù)研究[D]. 北京：北京郵電大學(xué)，2012-5.

[3]ZHANG M， YANG Q， WU C，et al. Hierarchical virtual network mapping algorithm for large-scale network virtualization. IET Commun.， 2012，6.

[4]CHOWDHURY M， RAHMAN MR， BOUTABA R. Virtual network embedding with coordinated node and link mapping. IEEE INFOCOM 2009， 2009.

[5]劉新剛，懷進(jìn)鵬，高慶一，等. 一種保持結(jié)點緊湊的虛擬網(wǎng)絡(luò)映射方法[J]. 計算機(jī)學(xué)報， 2012（12）： 2492-2504.

[6]蔡志平，劉強(qiáng)，呂品，等. 虛擬網(wǎng)絡(luò)映射模型及其優(yōu)化算法[J]. 軟件學(xué)報， 2012（12）： 864-877.