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

鄒曉輝 孫靜

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

關鍵詞：網絡虛擬化； 虛擬網絡映射； 鏈路映射； 多商品流

中圖分類號：TP3932 文獻標識碼：A文章編號：2095-2163（2013）06-0107-02

0引言

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

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

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

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

1底層網絡支持路徑分割的虛擬鏈路映射模型

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

圖1中，左圖為VN請求拓撲，右圖為物理網絡拓撲，因為本文只討論虛擬鏈路映射，所以忽略了節點映射約束。其中六邊型結點代表虛擬節點，虛擬節點之間的連線代表虛擬鏈路，虛擬鏈路上的數字表示其帶寬需求；圓形結點代表底層網絡中的物理節點，物理節點之間的實線連接代表物理鏈路，物理鏈路上的數字表示其可用帶寬，物理節點之間的虛線代表虛擬鏈路映射到的物理路徑。映射結果如圖中所示，即節點映射為{a→A，b→B，c→D}，鏈路映射為{（a，b）→（A，B），（a，b）→{（A，F），（F，C），（C，B）}，（b，c）→{（B，C），（C，D）}，（c，a）→{（D，E），（E，A）}}。由于（a，b）的帶寬需求在一條物理路徑上無法滿足，所以（a，b）多徑映射到兩條物理路徑（A，B）和{（A，F），（F，C），（C，B）}，物理鏈路（B，C）承載了兩個虛擬鏈路（a，b）和（b，c）的網絡流。

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

2.1 多商品流問題

多商品流問題是指多種商品流（或物質）在網絡中從不同的源端向不同的目的端進行傳輸的網絡流問題，是一個多源多匯問題。可以定義如下：

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

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

根據VN鏈路映射與多商品流問題的相似性，VN映射請求拓撲中的具有容量約束的一條虛擬鏈路lvi可以對應多商品流問題中的一個商品流fi，lvi的兩個端點對應fi的源點和匯點，則VN虛擬鏈路映射問題可以建模為多商品流問題進行求解。

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

設計VN映射算法通常基于某個目標函數，如最大化映射收益、最小化映射開銷、提高虛擬網絡請求接受率等。基于多商品流模型的虛擬鏈路映射算法結合某個目標函數與相應的流量分配約束，其求解是線性規劃問題。

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

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

具體映射結果可以采用線性規劃工具glpk求解。對于具體的VN映射請求，可以根據實際情況合理設置目標函數、調整或增加約束條件，從而得到更優化的映射方案。

3結束語

多商品流模型可以用來求解多源多匯問題，如鐵路網車流分配、通信網帶寬分配、多商品物流網絡設計等。對于鏈路映射通常采用k短路徑算法或基于多商品流的線性規劃方法[3-5]。虛擬鏈路的單徑映射是NP-hard問題，當底層網絡支持路徑分割時，虛擬鏈路的多徑映射建模為基于多商品流模型的線性規劃問題降低了映射復雜度。虛擬鏈路的多徑映射，不僅可以實現負載均衡，當底層物理鏈路失效時，還可以通過鏈路遷移[6]，將失效鏈路上的網絡流遷移到其他可用鏈路上，從而提高VN鏈路的可靠性。

參考文獻：

[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]劉志文. 網絡虛擬化環境下資源管理關鍵技術研究[D]. 北京：北京郵電大學，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]. 計算機學報， 2012（12）： 2492-2504.

[6]蔡志平，劉強，呂品，等. 虛擬網絡映射模型及其優化算法[J]. 軟件學報， 2012（12）： 864-877.