虛擬網絡映射模型和算法研究

鄒曉輝等

摘要：虛擬網絡映射是網絡虛擬化的關鍵問題之一，其目的是在滿足虛擬網絡資源需求的前提下，為該虛擬網絡分配合適的底層網絡節點和鏈路資源，從而在共享的物理網絡基礎設施之上構建彼此隔離的多重異構虛擬網絡，為網絡基礎創新研究提供實驗環境和平臺，為網絡新應用提供承載服務。論述了虛擬網絡映射模型和映射算法，并提出基于最小割集理論設計VN映射算法。

關鍵詞：網絡虛擬化； 虛擬網絡映射； 節點映射； 鏈路映射

中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2014）01-0045-03

0引言

計算機網絡產生于20世紀60年代，從最初的軍事網，到后來的科研網、商業網和民用網，計算機網絡無處不在，整個世界通過互聯網實現通信和資源共享。為了應對全球網絡規模的不斷擴張，20世紀90年代出現了諸如IPV6等促進網絡發展的新技術，但由于互聯網是由不同的異構自制域（AS）組成的，改造的高成本使得在所有AS上部署新架構非常困難，許多新技術也因此并未得到廣泛部署和應用。

2004年，Anderson和Peterson等提出采用網絡虛擬化（Network Virtualization）思想來克服當前互聯網在網絡基礎創新上所面臨的難點難關。網絡虛擬化是指在共享的底層物理網絡基礎設施之上構建彼此隔離的多重異構虛擬網絡，這些虛擬網絡可以運行各自的協議、擁有各自的架構，從而為網絡基礎創新研究提供實驗環境和平臺，同時也為當前互聯網向未來網絡演進提供可行途徑。網絡虛擬化是近幾年來國內外學者的一個重要研究方向，研究中，虛擬網絡映射是其最基本的問題之一。一個虛擬網絡（Virtual Network，VN）由虛擬節點和連接虛擬節點的虛擬鏈路構成拓撲，是底層物理網絡（Substrate Network，SN）的一個資源片。虛擬網絡映射也稱為虛擬網絡植入（virtual network embedding），將虛擬節點映射至底層物理網絡節點，將虛擬鏈路映射至底層的一條或多條物理路徑。

本文第2節對虛擬網絡映射問題進行了建模，給出了VN映射算法的目標函數和時間窗模型；第3節論述了如何采用啟發式算法和整數規劃方法進行VN映射，從是否同時映射虛擬節點和虛擬鏈路的角度，闡述了分離型映射算法和整合型映射算法；第4節對全文進行了歸納并對VN映射算法的研究進行了展望。

1虛擬網絡映射問題

虛擬網絡映射將合適的物理網絡資源片分配給虛擬網絡請求，而將虛擬網絡則部署到底層物理網絡資源上，同時要求分配給虛擬網絡的物理網絡資源片必須滿足虛擬網絡資源約束。虛擬網絡資源約束包括節點資源約束（如計算能力、部署位置等）和鏈路資源約束（如鏈路帶寬、延遲約束等）。此外，虛擬網絡映射還要解決在線請求、準入控制、拓撲多樣性等問題[1]。

1.1虛擬網絡映射模型

虛擬網絡映射就是一個滿足約束的圖匹配問題，因而可用無向有權圖對底層物理網絡和虛擬網絡請求進行描述和建模。

現將底層物理網絡形式化，表示為無向有權圖GS=（NS，LS，ASN，ASL）。其中，NS表示底層節點集合，LS表示底層鏈路集合，ASN表示底層節點屬性集合（如節點的計算能力、物理位置），ASL表示底層鏈路屬性集合（如鏈路帶寬、延遲特性）。虛擬網絡請求可以形式化為無向有權圖GV=（NV，LV，CVN，CVL），其中Nv表示虛擬節點集合，Lv表示虛擬鏈路集合，CVN表示虛擬節點約束集合，CVL表示虛擬鏈路約束集合。

進行虛擬網絡映射時，不同VN請求的虛擬節點可以映射到同一個SN物理節點，同一個VN請求的虛擬節點只能映射到不同的SN物理節點。VN請求的一條鏈路可以映射至SN的一個物理路徑（當SN不支持路徑切割時）或多個物理路徑（當SN支持路徑切割時），每個物理路徑可具有一個或多個相連的物理鏈路，而一個物理鏈路可以同時承載多個虛擬鏈路的網絡流。

1.2目標函數

1.3時間窗模型

在虛擬網絡映射算法中，考慮SN資源有限的情況，通常采取時間窗模型[3]，來解決VN映射的在線請求和準入控制問題。

時間窗模型將在線到達的虛擬網絡請求轉化為離線式映射處理問題，以時間窗為單位周期性執行VN映射。在一個時間窗開始時，釋放上個時間窗內離開的VN請求占用的資源，收集該時間窗內的VN請求（新到達的和重新排隊的），并將該時間窗內的VN請求按照其映射收益（或其它度量標準）從大到小實現排序，再按序映射至物理網絡。對一個時間窗內的VN請求，可以采用批處理的方式先映射該時間窗內所有VN請求的虛擬節點，如果某個VN請求的節點映射不成功，當其重映射次數小于重映射閾值（算法中設置）時，即將該VN請求送至下個時間窗的等待隊列，否則，該VN請求被拒絕；然后對該時間窗內所有完成節點映射的VN請求采用批處理的方式進行虛擬鏈路映射，鏈路映射不成功的VN請求則被送至下個時間窗的等待隊列或者被拒絕。對一個時間窗內的VN請求進行處理時，也可以在完成一個VN請求的節點和鏈路映射之后，再進行下一個VN請求的節點和鏈路映射，不能成功映射的VN請求，將被送至下個時間窗的等待隊列或者被拒絕。

通過計算一個或多個時間窗內成功映射的虛擬網絡請求總數與到達的虛擬網絡請求總數比值，即可得到虛擬網絡請求接受率，用其來衡量VN映射算法的優劣。

2虛擬網絡映射算法

虛擬網絡映射通常要滿足節點資源約束、鏈路資源約束、拓撲約束、目標約束等，其優化問題通常是NP-hard的，可以采用啟發式算法或建模為整數規劃問題進行求解。

2.1啟發式算法和整數規劃方法

啟發式算法主要采用圖搜索的方式，從局部出發，根據反饋不斷尋找滿足目標的虛擬節點和路徑，構建虛擬網絡。文獻[5]提出了一種保持節點緊湊的虛擬網絡映射算法，將符合虛擬節點資源約束的所有物理節點作為候選宿主并將其組織成簇，在分簇過程中候選宿主節點除了要滿足計算能力等約束外，還需要通過1_割檢驗，使得該算法求解的節點映射存在可行的鏈路映射與之對應的概率極大。文中定義了虛擬節點平均分布距離，設計了啟發式算法求解最緊湊節點映射問題，然后將鏈路映射建模為多商品流問題，由此獲得對應的最優鏈路映射方案。該算法求解的VN映射使虛擬節點分布更加緊湊，占用的資源較少，且增大了收益/開銷比。但是該算法不適合于有節點位置約束的VN映射問題，由于映射過于集中在局部網絡資源，不利于負載均衡，在某種程度上可能降低VN請求接受率。文獻[6]提出了基于經典的蟻群算法和遺傳算法的VN映射算法，并與已有的VN映射算法在映射收益、映射開銷和VN請求接受率等方面進行了比較，為采用經典人工智能算法優化VN映射問題提供了參考。

虛擬網絡映射問題可以建模為混合整數規劃問題，從全局角度求解虛擬網絡構建問題。為降低求解復雜性，通常將整數規劃問題松馳為線性規劃問題求解。文獻[4]是一個具有節點位置約束的VN映射問題，通過將具有位置約束的虛擬節點引入到SN模型圖中，構建增廣圖，并采用混合整數規劃方法對VN映射問題進行建模。為降低求解難度，將整數約束松弛為線性約束，求解節點映射，再將所有虛擬節點映射到底層物理節點；而后采用多商品流算法進行鏈路映射（當底層不支持路徑切割時，采用k短路徑算法）。文中采用線性規劃工具glpk求解VN映射的線性規劃問題和多商品流問題。在某些情況下，采用松弛整數規劃求解VN映射，性能或許較差，此時應考慮合理設置目標函數、調整或增加約束條件，從而得到更優化的映射方案。

2.2分離型映射算法和整合型映射算法

基于對一個VN請求的節點映射和鏈路映射是否交替進行的不同狀況，可以將VN映射算法歸結為分離型映射算法和整合型映射算法兩類，現對其展開分析探討如下。

分離型映射算法是，首先映射完成所有虛擬節點，然后再映射虛擬鏈路，可參見文獻[3-5]。文獻[3]中，將節點映射和鏈路映射分為兩個階段。在節點映射階段，基于貪婪策略，將虛擬節點請求按其收益進行排序，優先映射收益大的虛擬節點；對每個虛擬節點進行映射時，即在底層網絡中尋找滿足其資源約束的候選宿主集合，并將所有候選宿主按其CPU能力和周圍鏈路帶寬的乘積進行評分，再將虛擬節點映射到評分最高的候選宿主上。在鏈路映射階段，則采用基于多商品流的線性規劃方法。而對于某些分離型映射算法，在映射虛擬節點時可能并未考慮跟鏈路有關的因素，當映射某兩個虛擬節點間的具有帶寬約束的虛擬鏈路時，就會發生找不到滿足帶寬需求的物理路徑的可能，從而導致映射失敗。

整合型映射算法則是，在映射虛擬節點的同時進行虛擬鏈路映射，如果找不到合適的鏈路映射，則回溯至上一次節點映射方案重新映射節點。文獻[7]提出了子圖同構檢測方法，在底層網絡中逐步構建滿足VN約束的子圖，子圖構建時，需要先定位節點，再尋找可行鏈路，如果找不到可行鏈路，則回溯至上一步，重新映射節點，直至完成所有虛擬節點和虛擬鏈路的映射。當VN請求規模較大時，多次回溯就可能使算法性能變得較差。

3結束語

已有的文獻大多基于不同的優化目標來設計VN映射算法，卻對在VN映射的同時要確保物理網絡的良好連通性較少付諸考慮，未來的研究可以嘗試基于割集理論，從最小割集的角度來設計VN映射算法，以此來獲取物理網絡負載的均衡和連通性，并使得底層網絡基礎設施可以容納更多虛擬網絡、提高資源利用率。

網絡虛擬化的概念雖然已經提出很長時間，但當前與虛擬網絡相關的大部分研究多是停留在實驗室仿真階段，基本上都使用GT-ITM工具生成底層物理網絡和虛擬網絡請求拓撲。VN映射是網絡虛擬化最關鍵的問題之一，只有設計高效的VN映射算法才能推進網絡虛擬化技術在實際網絡中的實施和部署，從而加快網絡技術的創新。

參考文獻：

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

[2]卿蘇德，廖建新，朱曉民，等. 網絡虛擬化環境中虛擬網絡的嵌套映射算法[J]. 軟件學報， 2012，23（11）： 3045-3058.

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

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

[5]劉新剛，懷進鵬，高慶一，等. 一種保持結點緊湊的虛擬網絡映射方法[J]. 計算機學報， 2012， 35（12）： 2492-2504.

[6]CHANG X L， MI X M， MUPPALA J K. Performance evaluation of artificial intelligence algorithms for virtual network embedding[J]. Engineering Applications of Artificial Intelligence， 2013， 26（10）： 2540-2550.

[7]LISCHKA J， KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection. ACM SIGCOMM，2009 Workshop， 81-88.