基于節點可靠性感知和共享路徑保護的虛擬網映射算法研究

劉光遠，安秀芳，蘇森

（1. 石家莊鐵道大學信息科學與技術學院，河北 石家莊 050043；2. 北京郵電大學網絡與交換技術國家重點實驗室，北京100876）

基于節點可靠性感知和共享路徑保護的虛擬網映射算法研究

劉光遠1，安秀芳1，蘇森2

（1. 石家莊鐵道大學信息科學與技術學院，河北 石家莊 050043；2. 北京郵電大學網絡與交換技術國家重點實驗室，北京100876）

網絡虛擬化技術為目前的網絡架構提供了一種有效的擴展手段。近年來，底層網絡基礎設施失效事件頻發，因此如何提高虛擬網絡的可靠性成為目前該領域一個研究熱點。對在保證虛擬網絡可靠性的同時如何最小化底層網絡映射開銷問題進行研究，設計了一個新的啟發式算法對其進行求解。實驗表明，相比其他算法，所提算法網絡帶寬資源開銷更低。

網絡虛擬化；虛擬網絡映射；啟發式

1 引言

目前，互聯網應用在人們的日常生活中發揮了重要作用[1]，但是其固有的設計規則和多服務提供商的特征，使評估和部署新的網絡應用變得越來越難。近年來，人們提出了網絡虛擬化技術，用來解決“網絡僵化”問題[2,3]。該技術允許多個異構的虛擬網絡共享一個底層物理網絡，因此得到了越來越多的應用，但是虛擬網絡仍需面臨不可預測的底層網絡節點或鏈路失效問題，嚴重的會導致虛擬網絡不再可用。

虛擬網絡映射問題已被證明為 NP難題[4]，早期的虛擬網研究[5～7]以底層網絡資源利用最優為目標，設計不同的啟發式算法，但是均沒有考慮底層網絡節點或鏈路失效時虛擬網絡的可靠性問題。在映射的過程中加入虛擬網絡可靠性約束無疑使該問題變得更加復雜。由于提供虛擬網絡可靠性保證需要消耗更多的底層網絡資源，因此所設計的算法應該在虛擬網絡可靠性和底層網絡資源消耗之間做一個權衡。文獻[8～10]基于完全冗余機制對底層鏈路或節點失效進行了保護，但是資源使用效率還有待提高。本文提出了一個新的可靠虛擬網絡映射算法RVNM，目的是在保證虛擬網絡可靠性的同時最小化底層網絡資源開銷。在節點映射階段，該方法不預留底層網絡保護資源，將底層物理節點按照可靠性和資源負載平衡綜合進行評估并排序，然后將虛擬節點映射到具有高評估值的底層物理節點上，實驗表明該機制可以大大提高虛擬節點的抗毀性。在鏈路映射階段，本文設計了一個新的鏈路映射機制，該機制基于共享路徑保護策略。實驗表明，該機制可在底層網絡帶寬使用方面接近最優。

2 相關工作

由于虛擬節點和虛擬鏈路的約束限制，虛擬網絡映射問題已被證明為NP難題。Yu等[5]重新對底層網絡進行設計，通過路徑分裂和路徑遷移機制使映射問題簡化。Chowdhury等[6]考慮虛擬節點位置需求，為該問題建立一個混合線性規劃模型，并利用線性松弛技術對其進行求解。Lischka等[7]基于子圖同構理論提出了一種虛擬網映射算法以提高虛擬網絡請求接受率。CHENG等[11]基于 PageRank理論提出了一種拓撲感知的虛擬網絡映射算法，該算法提高了底層網絡運營商的收益。盡管如此，以上研究主要將目光集中在底層網絡資源的高效利用上，忽視了由于底層網絡節點和鏈路失效帶來的虛擬網絡可靠性保護問題，因此，虛擬網絡在底層資源失效后無法快速得到恢復，可能造成嚴重的經濟損失。

近年來，有關可靠虛擬網絡映射的相關研究逐漸增多。針對底層網絡單鏈路失效情境，Rahman等[8]基于快速重路由策略，提出了一種1∶1確定性后備鏈路恢復機制，該機制在考慮最大化長期收益的同時盡可能最小化長期懲罰代價，但底層網絡帶寬使用效率較低。針對相似的問題情境，Chen等[9]基于路徑共享機制提出一種主動鏈路保護方法，該方法所消耗的底層網絡帶寬比文獻[8]低，但還有進一步優化的空間，此外該論文僅考慮了鏈路保護的情形而忽略了節點可靠性保護問題。針對底層節點失效情境，Yeow等[10]提出冗余資源共享池的方法，該方法可以達到n：k的冗余保護，但是該方法仍舊消耗了許多底層網絡保護資源。事實上，在真實的網絡中，底層網絡節點失效的可行性很小，所以沒有必要為它們預留那么多的底層保護資源。因此，本文提出了一個新的節點映射機制，該機制在不預留底層網絡保護資源的情況下仍能提高虛擬節點的抗毀性，而且本文所提出的鏈路映射算法，相比文獻[8,9]算法，在底層網絡帶寬資源使用方面接近最優。本文的研究對資源有限的底層網絡來說有重要意義。

3 問題描述

3.1 底層網絡

本文采用文獻[1]給出的虛擬網絡映射模型描述。底層物理網絡拓撲可用帶權無向圖表示，其中，N和E分別表示底層物理網ss節點和鏈路的集合，和分別表示物理網節點的計算能力和鏈路帶寬。底層物理網絡可以是電信網絡或者數據中心網絡資源。圖1(a)給出了一個底層物理網絡拓撲實例，節點附近方框中的數字表示可用的計算資源，鏈路附近的數字表示可用的帶寬資源。

圖1 虛擬網絡映射實例

3.2 虛擬網絡請求

3.3 帶有可靠性保護需求的虛擬網絡映射問題

對于可靠的虛擬網絡節點映射，由于本文的目標是盡可能減少底層網絡資源消耗，所以本文沒有設計基于預留底層保護資源的映射方法，而是設計了不預留底層網絡資源，提高虛擬節點抗毀性的虛擬節點映射方法。對于可靠的虛擬鏈路映射，在完成底層網絡基本虛擬鏈路映射以后，需要針對底層鏈路失效情境，為每個虛擬鏈路選擇保護路徑。給定一個虛擬鏈路euv，首先，應該保證主鏈路和相應保護鏈路不共享任何底層的物理鏈路或節點。直觀上說，本文可以簡單采用冗余機制選取2條底層不相交的路徑進行映射，但是這個方法會浪費大量的底層網絡資源。事實上，由于鏈路保護資源存在共享使用的可能性，所以保護路徑不一定必須預留和主路徑相等的帶寬資源。通常情況下，會被設置為2條可共享保護路徑的主路徑帶寬的最大值，而不是它們2個帶寬之和。本文對簡單的共享路徑保護機制進行改進，其帶寬消耗大大低于現有算法。值得注意的是，相關研究表明單鏈路失效數量占所有失效數量的70%[2,3]，所以本文主要針對單鏈路失效保護問題進行研究。

3.4 目標

本文設計了基于底層網絡資源約束的在線可靠虛擬網絡映射算法。主要目標是在保證虛擬網絡可靠性的同時最小化底層網路資源開銷。因為更少的資源開銷表示底層網絡可以節省更多資源以用于接受更多的虛擬網絡請求。下面給出后面實驗中用到的性能參數及說明，包括平均網絡帶寬消耗、長期帶寬資源利用率、虛擬網絡請求接受率和長期收益開銷比（）。

1)平均網絡帶寬消耗定義為

其中，BW表示底層網絡帶寬消耗。

2)長期帶寬資源利用率定義為

其中，RBW表示預留的保護帶寬資源，PBW表示主帶寬資源。

3)參考文獻[3,4]的工作，虛擬網絡請求接受率被定義為

其中，VNR表示虛擬網絡請求， VNRa表示底層網絡成功接受了虛擬網絡請求。

4）長期收益開銷比通常表示資源使用的效率，被定義為

4 RVNM啟發式算法

本節對本文設計的可靠虛擬網絡映射算法進行描述。該算法包括底層節點可靠性感知的節點映射機制和優化共享路徑保護鏈路映射機制。

4.1 抗毀的虛擬網絡節點映射機制

該算法首先基于底層節點先前的失效次數對底層物理節點進行可靠性評估，失效次數越多表明這個底層節點的可靠性越低。除此之外，算法還考慮了節點負載狀態，因為節點hot-spot問題會導致虛擬網絡請求拒絕數量的增加。而且，當底層hot-spot節點失效后，被影響的虛擬網絡數量通常要多于其他失效節點所帶來的影響。所以，節點映射算法綜合考慮了底層節點可靠性和資源使用負載平衡這2個方面。因此本文給出如下定義

其中，FT(ns)表示節點 ns∈Ns的失效次數，PR(ns)表示節點 ns上已使用資源的百分比。值得注意的是，這里所說的節點資源包括 CPU能力和與節點ns相連的所有鏈路帶寬資源。k表示節點ns上已經映射的虛擬網絡的數量。

在虛擬網絡節點映射階段，算法首先計算每個底層網絡節點的R(ns)值，并對其進行降序排列。然后將虛擬節點依次映射到具有高 R(ns)值的底層網絡節點上，且該節點必須滿足虛擬節點 CPU能力和鏈路能力需求。

4.2 優化共享保護虛擬網絡鏈路映射機制

如 3.1節所述，將虛擬節點全部映射到底層物理節點后，RVNM需要為每個虛擬鏈路選擇一個底層主路徑進行映射。但是即使虛擬節點已經固定，虛擬鏈路最優映射問題仍是 NP難的。因此，為了簡單起見，本文工作集中于底層網絡不支持路徑分裂的情形，通過最短路徑算法找到最小帶寬消耗（最小跳數）的主路徑。本文的工作成果也可應用于其他情境，僅需要底層網絡支持路徑分裂即可。

由于本文考慮的是底層單鏈路失效的虛擬網絡可靠性保護問題，所以為主路徑預留的保護路徑資源有可能實現共享。如果它們的保護路徑占用同樣的鏈路，則必須保證這2個保護路徑對應的主路徑不相交。

算法的最終目標是要找到最小化底層鏈路映射消耗的映射方案，即滿足的主鏈路和保護鏈路的映射方案。

鏈路映射算法的主程序如算法1所示。S 表示最終的鏈路映射結果。如果沒有可用的映射方案，算法返回NULL。

算法中用到的變量說明如下。

L：表示所有的底層鏈路集合。

BW：表示鏈路j上的帶寬總能力。

Cj：表示鏈路j 上的可用帶寬能力。

pj：表示鏈路j上所有主帶寬使用資源。

rj：表示鏈路j上所有保護帶寬使用資源。

pi：承載虛擬鏈路 i 的主路徑。

ri：承載虛擬鏈路 i 的保護路徑。

M：迭代限制次數。

cj：表示計算最小帶寬消耗。

算法1主路徑和保護路徑選擇策略

步驟1按照式(6)計算最小帶寬消耗對應的主路徑pi；如果pi存在，則執行步驟2。

否則，拒絕映射當前虛擬網絡請求，算法返回NULL。

步驟2如果Tgt;M，執行步驟6。

否則，固定主路徑pi、按照式(7)計算最小消耗對應的保護路徑ri。

如果ri存在，則執行步驟3。

否則，執行步驟6。

步驟3計算當前主路徑pi和保護路徑ri資源消耗之和C。

步驟4固定保護路徑ri，按照式(8)重新計算新的最小花費對應的主路徑

否則，執行步驟6。

如果C*＜C,則且返回執行步驟2。

否則，執行步驟 6。

步驟6如果S=NULL，算法返回NULL。

否則，按照方案S更新所有的鏈資源分配并將結果返回。

算法中變量T和S初始化分別被設置為1和NULL。式(6)表示一個計算鏈路消耗函數，鏈路存在更多空閑資源表示其鏈路消耗更低。此外，如果主路徑占用這些鏈路，則底層鏈路資源消耗會更平均，更能達到負載均衡的目的。式(7)中表示鏈路j上預留的保護資源需求，假設j∈ri,?n∈L}，其中，表示虛擬鏈路的集合，該集合中元素的主路徑為n，保護路徑為j。容易看出，在已經分配了保護路徑的鏈路上分配新的保護路徑會占被認為更低的鏈路消耗，從而使保護資源利用率提高。在式(9)中，ε表示一個極小門限值（例如ε=10?3），表示鏈路 l上的保護資源需求。其中，表示虛擬鏈路的集合，該集合中元素的主路徑為 n，保護路徑為l。

為了更好地說明算法，現舉一實例，在某時刻，需要映射虛擬鏈路L，按照RVNM算法執行流程。首先通過最短路徑算法為該虛擬鏈路選擇底層網絡映射的主路徑和保護路徑。然后將保護路徑固定，重新計算一個新的主路徑。如果這個新的主路徑可以使鏈路使用總資源消耗更少（按照算法 1中的公式計算，實質為可以實現保護鏈路共享，從而降低資源消耗），則保留并更新現有的鏈路映射方案。接著再固定主路徑，按照類似的思路重新計算保護路徑以使帶寬資源使用更優（按照算法和計算公式進行執行，由于每個階段都對所有可能的映射方案進行了比較，因此通過迭代可以得到全局最優解，即最優帶寬資源消耗值）。當新的結果比先前結果差或者到達了限定的迭代次數（由于迭代次數或時間的限制，該結果接近最優值），重映射過程就停止。

5 性能評估

本節首先對模擬實驗設置進行了描述，然后給出了實驗數據和分析評估結果。

5.1 實驗設置

為了驗證RVNM的有效性，在先前工作開發的虛擬網絡映射模擬平臺上[11]對算法進行了測試。與早期工作[11～14]相似，底層網絡拓撲由GT-ITM[15]生成，包含100個節點和500條鏈路。底層網絡的節點 CPU能力和鏈路帶寬能力為40～90均勻分布。虛擬節點個數服從 2～7均勻分布。虛擬節點的CPU能力需求為0～15均勻分布，帶寬能力需求在0～40。此外，虛擬網絡請求的到達頻率服從每100個時間單位到達率為4的泊松分布。虛擬網絡的平均生存時間為500個時間單位。模擬實驗共運行大約50 000個時間單位，在這期間大約有2 500個虛擬網絡請求。實驗中算法迭代限制參數M設為6。

實驗中，本文比較了許多參數指標，包括式(1)中定義的平均網絡帶寬花費、式(2)定義的長期帶寬資源利用率、式(3)定義的虛擬網絡請求接受率、式(4)定義的長期收益開銷比和算法成功接受一個虛擬網絡請求的平均時間花費。

實驗中被比較的算法如表1所示，且所有算法都采用相同的輸入。實驗硬件平臺配置為Intel 4.0 GHz內核CPU、8 GB內存、1 TB硬盤,Linux OS 2.8。

表1 比較的算法

5.2 實驗結果及分析

由于采用了新的虛擬網絡節點映射策略，實驗表明，在不預留底層網絡資源的情況下，RVNM提高了虛擬網絡節點的抗毀性，其他2個算法僅考慮了鏈路保護而忽略了節點保護。此外，算法的收益和花費是本文工作主要考慮的因素。下面給出具體的實驗結果和分析。

1)RVNM相比其他2個算法，大大降低了底層網絡帶寬消耗

圖2和圖3分別給出了3個算法的網絡帶寬消耗和帶寬資源利用率的實驗數據結果。HYBIRD算法由于采用確定性路徑保護方法，其帶寬資源消耗明顯高于其他2個基于共享路徑保護的算法，所以在圖3中只比較了另2種算法。相比PARDALIS，RVNM明顯節省了網絡帶寬資源，如圖3所示，其保護資源使用率比PARDALIS 平均降低了10.7%，原因是RVNM算法采用了優化共享鏈路映射機制，更多地保護帶寬能夠被共享，所以底層網絡帶寬能夠得到更好的利用。

圖2 平均網絡資源消耗

圖3 長期帶寬資源利用率

2)RVNM 相比其他算法能獲得更高的虛擬網絡請求接受率和長期收益開銷比

如圖4所示，RVNM算法的虛擬網絡請求接受率高于PARDALIS和HYBRID算法，結果平均分別高出9.6% 和 18.3%。這是因為RVNM算法更好地節省了網絡帶寬資源，從而使更多的空閑資源被用于后續的虛擬網絡請求。

圖4 虛擬網絡請求接受率

如圖5所示，本文提出的算法由最少的資源帶寬消耗，獲得了最好的收益開銷比，從而證明了網絡資源使用的有效性。HYBRID算法由于無視帶寬共享獲得了最差的比較結果。

圖5 長期收益開銷比

3)RVNM 算法在執行時間和資源消耗之間做一平衡

圖6描述了各個算法成功映射一個虛擬網絡請求平均所花費的時間。RVNM的執行結果高于其他2個算法，這主要是因為節點可靠性計算和優化路徑的選擇，但1.8 s的時間復雜度是可以滿足在線虛擬網絡請求的。更重要的是，相比 PARDALIS和HYBRID算法，RVNM算法能提高虛擬節點的抗毀性而不用預留底層保護資源，同時在網絡鏈路映射開銷上分別降低了10%和19%左右，為底層運營商節省了更多的寶貴資源。

圖6 一個虛擬請求的平均完成時間

6 結束語

本文研究了可靠的虛擬網絡映射問題，針對單鏈路失效情境提出了一個新的啟發式算法RVNM。該算法通過節點可靠性感知策略，在不預留底層保護資源的情況下提高了虛擬節點的抗毀性。此外，算法設計的優化共享保護鏈路機制能最小化底層網絡帶寬消耗。實驗表明，該算法是一種有效的可靠虛擬網絡映射算法。今后的工作將進一步研究跨域虛擬網絡映射可靠性問題。

[1]MEEKER M. Internet Trends 2016[EB/OL].http://www. kpcb.com/internet-trends,2016-06-01.

[2]CHOWDHURY N M M K,BOUTABA R. Network virtualization:state of the art and research challenges[J]. Communications Magazine,IEEE,2009,47(7): 20-26.

[3]SU S,ZHANG Z,LIU A X,et al. Energy-aware virtual network embedding[J]. IEEE/ACM Transactions on Networking,2014,22(5):1607-1620.

[4]肖藹玲,王穎,孟洛明,等. 基于知識描述和遺傳算法的跨域虛擬網絡映射[J]. 軟件學報,2014,25(10): 2189-2205.XIAO A L,WANG Y,MENG L M,et al. Knowledge description and genetic algorithm based multi-domain virtual network embedding [J].Journal of Software,2014,25(10): 2189-2205.

[5]YU M,YI Y,REXFORD J,et al. Rethinking virtual network embed-ding: substrate support for path splitting and migration[J]. ACM Sigcomm Computer Communication Review,2008,38(2): 17-29.

[6]CHOWDHURY M,RAHMAN M R,BOUTABA R. ViNEYard:virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE Transactions on Networking,2012,20(1):206-219 .

[7]LISCHKA J,KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]//The 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. c2009: 81-88.

[8]RAHMAN M,AIB I,BOUTABA R. SVNE: survivable virtual network embedding algorithms for network virtualization[J]. IEEE Transactions on Network and Service Management,2014,10 (2): 105-118.

[9]CHEN Y,LI J,WO T,et al. Resilient virtual network service provision in network virtualization environments[C]//IEEE ICPADS. c2010: 51-58.

[10]YEOW W L,WESTPHAL C,KOZAT U. Designing and embedding reliable virtual infrastructures[J]. ACM Sigcomm Computer Communication Review,2011,41(2): 57-64.

[11]CHENG X,SU S,ZHANG Z,et al. Virtual network embedding through topology-aware node ranking[J]. ACM Sigcomm Computer Communication Review,2011,41(2): 39-47.

[12]CHENG X,SU S,ZHANG Z,et al. Virtual network embedding through topology awareness and optimization[J]. Elsevier Computer Networks,2012,56(6): 1797-1813.

[13]SU S,CHENG X,ZHANG Z,et al. Virtual network embedding with survivable routing[J]. Journal of Internet Technology,2014,14(5):741-750.

[14]劉光遠,雙鍇,蘇森. 區分服務 QoP的可生存虛擬網絡映射算法研究[J]. 通信學報,2013,34(12):79-84.LIU G Y,SHUANG K,SU S. Survivable virtual network mapping with differentiated services QoP[J]. Journal on Communications,2013,34(12):79-84.

[15]ZEGURA E W,CALVERT K L,BHATTACHARJEE S. How to model an Internet work[C]//IEEE Infocom,c1996: 594-602.

Virtual network mapping algorithm with node reliability awareness and shared-path protection

LIU Guang-yuan1,AN Xiu-fang1,SU Sen2

(1.School of Information Science and Technology,Shijiazhuang Tiedao University,Shijiazhuang 050043,China;2. State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China)

Network virtualization has been proposed as a promising way for expanding the network architecture. However,how to provide reliable VN against substrate infrastructure failures has become an increasingly important issue. Meanwhile the substrate network resource cost should be minimized under VN reliability guarantees to maximize the revenue for the infrastructure providers (InP). A novel heuristic VN mapping algorithm was presented. Simulation results show that proposed algorithm can gain near optimal network bandwidth usage compared to the previous algorithms.

network virtualization,virtual network mapping,heuristic

s:The National Natural Science Foundation of China (No.61170274,No.61373160),Colleges and Universities in Hebei Province Science and Technology Research Fund (No.QN2016270),Undergraduate Training Programs for Innovation and Entrepreneurship (No.201510107098)

TP393.1

A

2015-10-21；

2016-06-13

國家自然科學基金資助項目（No.61170274,No.61373160）；河北省高等學校科學技術研究基金資助項目（No.QN2016270）；大學生創新創業基金資助項目（No.201510107098）

10.11959/j.issn.1000-436x.2016155

劉光遠（1981-），男，河北石家莊人，博士，石家莊鐵道大學講師，主要研究方向為下一代互聯網與云計算技術。

安秀芳（1993-），女，河北滄州人，主要研究方向為云計算技術。

蘇森（1971-），男，山東菏澤人，北京郵電大學教授、博士生導師，主要研究方向為服務計算、云計算、大數據處理。