基于Openflow網絡的高可靠性虛擬網絡映射算法

蔡進科 顧華璽 盧 冀 余曉杉

?

基于Openflow網絡的高可靠性虛擬網絡映射算法

蔡進科*①顧華璽①盧 冀②余曉杉①

①(西安電子科技大學ISN國家重點實驗室 西安 710071)②(通信網信息傳輸與分發技術重點實驗室 石家莊 050081)

該文基于Openflow網絡提出了具有容錯能力的虛擬網絡映射模型，并且采用蟻群算法對其進行求解。針對虛擬網絡的故障恢復機制，提出了區分用戶優先級的故障恢復算法(Priority_Diff)，該算法為用戶提供不同的網絡可靠性級別，對高級用戶采用提前映射的備份路徑替代故障鏈路，對低級用戶重新映射故障鏈路；設計了故障備份鏈路重映射(BLRM)算法，將故障鏈路中的備份資源遷移到相鄰鏈路，增強了備份鏈路的可用性。最后，通過仿真實驗，從虛擬網絡故障修復率、虛擬網絡成功運行率和工作鏈路資源利用率3個方面驗證了所提算法的優越性。

虛擬網絡；Openflow；映射算法；可靠性

1 引言

互聯網在過去的幾十年里飛速發展，隨著用戶業務越來越豐富，傳統網絡的“傻瓜式網絡+智能終端”的構網方式無法滿足不同用戶業務的多樣化需求，與三網融合的趨勢相違背。網絡虛擬化技術[1]的出現為打破傳統的網絡架構提供了一條有效的途徑，被認為是下一代互聯網架構的發展趨勢[2,3]。源自于斯坦福大學“Clean slate”研究計劃的Openflow網絡將網絡的控制層和轉發層分離，是未來虛擬化網絡的雛形[4]。

Openflow網絡是由多個網絡域相互連接構成，每個網絡域包括一個控制器，一個或多個Openflow交換機以及若干主機。控制器承載的是該域內的控制資源，主要負責運行不同的路由協議，并且計算出相應的路由流表。Openflow交換機承載的是轉發資源，通過運行在安全通道上的Openflow協議與控制器通信，根據控制器產生的流表來轉發數據。

Openflow網絡的主要思想是利用網絡虛擬化技術將物理網絡劃分為多個虛擬網絡，這些虛擬網絡都共享同樣的底層物理網絡資源，各個虛擬網絡可以運行不同的路由協議，提供不同的服務。虛擬網絡的構建請求包括虛擬節點請求和虛擬鏈路請求兩部分，為虛擬網絡選擇合理的映射算法不但關系到物理網絡的資源利用率，而且影響虛擬網絡的性能。文獻[5]將虛擬網絡映射問題抽象為混合整數規劃問題，針對不同的應用環境分別提出了D-ViNE 和R-ViNE兩種算法。文獻[6]基于負載平衡路由和小區劃分結構的思想設計了一種具有優秀時延和吞吐量性能的虛擬網映射算法。文獻[7]在K短路徑的基礎上改進了鏈路映射的過程，并且提出了一種物理節點可重復映射的虛擬網絡映射算法。但是在真實環境下，物理網絡經常由于地震、泥石流等自然原因或者惡意攻擊等非自然原因發生故障，影響用戶業務的正常運行。而上述的這些算法都是針對物理網絡的資源利用率最大，沒有考慮因為網絡故障而導致的虛擬網絡可靠性問題。

針對虛擬網絡的可靠性問題，文獻[8]提出了一種虛擬節點和虛擬鏈路的重映射機制，不但可以提高虛擬網絡的接收率而且有利于網絡的負載均衡。文獻[9]通過預先構建備份路徑，將故障的虛擬鏈路遷移到備份路徑。文獻[10]通過構建統一的備份資源池，為虛擬鏈路動態地分配備份資源，提高了物理資源的利用率。上述這些算法分別采用不同的機制提高虛擬網絡的可靠性，但是它們或者故障發生時才進行鏈路重映射，故障修復率低，或者提前預留備份資源，成本太高，或者不能應對連續的多個網絡故障。

本文針對Openflow網絡提出了具有一定容錯能力的虛擬網絡映射模型，并且采用蟻群算法對其進行求解，同時針對已成功映射的虛擬網絡設計了故障恢復機制。考慮到不同用戶的網絡可靠性需求不同，銀行、金融和軍事機構等用戶要求自己的業務24小時正常運行；而像學校、社交論壇等大部分的普通用戶對網絡的可靠性需求相對較弱。通過為不同用戶提供不同級別的網絡可靠性保證，提出了區分用戶優先級的故障恢復算法(Priority_Diff)，即對受到故障影響的高優先級用戶的流量遷移到預先設定的備份路徑，而對低優先級用戶的故障鏈路進行重新映射。該算法可以有效兼顧物理網絡資源利用率和網絡的容錯抗毀特性。同時，由于物理鏈路上同時承載著工作資源和備份資源，備份資源故障很可能導致后續的故障鏈路修復失敗，為了增強備份鏈路的可用性，本文提出了故障備份鏈路重映射(BLRM)算法。最后通過仿真實驗從虛擬網絡故障修復率、虛擬網絡成功運行率、工作鏈路資源利用率方面驗證了所提算法的優越性。

2 基于Openflow網絡的容錯映射模型

2.1 Openflow網絡描述

2.2 映射描述

如圖1所示，圖1(a)所示為兩個虛擬網絡請求，方框內為該節點所需要的控制資源和轉發資源，鏈路上的數字為所需要的帶寬；圖1(b)所示為Openflow網絡模型，節點旁的方框內為該節點的轉發資源，控制器旁的方框內為該域內的控制資源。

(1)節點映射：在Openflow網絡中，不僅物理節點要能夠滿足所承載的虛擬節點的轉發資源需求，而且該物理節點所在域也必須能夠滿足虛擬節點的控制資源需求。除此之外，采用的是最經典的映射方式，即虛擬節點和物理節點是一對一的映射[11]。滿足的約束條件如式(1)所示。

(2)鏈路映射：以映射成功的物理節點為端點，利用最短路算法，將每條虛擬鏈路都映射到一條物理路徑上，該物理路徑上的每一段物理鏈路都必須能夠滿足所承載虛擬鏈路的帶寬需求，約束條件如式(3)所示。

圖1 Openflow網絡映射實例

根據上述映射規則，在圖1所示的實例中，高優先級用戶的虛擬網絡請求1的兩個虛擬節點,分別映射到物理節點,上，虛擬鏈路(,)對應地映射到物理鏈路(,)上，同時創建備份路徑(,,)；低優先級用戶的虛擬網絡請求2的4個虛擬節點,,,分別映射到物理節點,,,上，虛擬鏈路(,),(,),(,)對應地映射到物理鏈路(,), (,),(,)上。

2.3 映射目標

3 虛擬網絡求解算法

虛擬網絡映射問題由于數學模型復雜、約束條件多是公認的NP-hard問題[12]，求解算法需要滿足以下條件：很強的收斂性，保證算法能夠在有限次迭代之后找到優化目標的近似解；低算法復雜度，保證算法在較短的時間內運行完成；高魯棒性，保證求得的解為全局最優解，避免陷入局部最優解問題。

本文首次采用了蟻群算法[13]來求解在Openflow網絡模型下的虛擬網絡映射問題。蟻群算法是通過模擬現實世界中螞蟻覓食的尋路過程而提出的一種智能算法，它的基本原理是：螞蟻在尋找食物的過程中會在經過的路徑留下信息素作為標記。信息素具有揮發性，由于螞蟻在離食物較短的路徑來回的頻率更快，因此在該路徑留下的信息素更多，后續螞蟻選擇該條路徑的概率就越大，通過這種正反饋螞蟻可以找到從蟻巢到食物的最短路徑。利用蟻群算法求解虛擬網絡映射問題的步驟如下：

00 Initialization(); //對物理網絡和仿真參數進行初始化

01 VN_Creation(); //按照泊松分布產生虛擬網絡構建請求

02 For=1 to//迭代次

03 { Update_probability(); //根據信息素更新虛擬節點對物理節點的映射概率

04 For ant=1 to//每次迭代產生只螞蟻

05 { Node_Map(); //根據映射概率進行節點映射

06 Link_Map(); //根據最短路算法進行鏈路映射

07 if((local_solution)>(global_solution)) //比較當前解和最優解的資源剩余量

08 global_solution=local_solution; //將剩余資源量最大的解作為最優解保存

09 }

10 Update_info(); //更新虛擬節點對物理節點的信息素

11 }

4 虛擬網絡故障恢復機制

在骨干網中單鏈路故障占全部故障的70%[14,15]，是最易發生和最常見的問題。為了提高Openflow網絡的可靠性，本文針對單鏈路故障問題，提出了區分用戶優先級的故障恢復算法，以及增強備份資源有效性的故障備份鏈路重映射算法，構建了一套有效的虛擬網絡故障恢復機制。

4.1 區分用戶優先級的故障恢復算法

(1)判斷故障鏈路上所承載虛擬網絡的優先級；

對受該故障影響的所有虛擬網絡逐一運行該算法，故障修復完成。

4.2 故障備份鏈路重映射算法

5 實驗結果及分析

5.1 實驗設定

本文主要從虛擬網絡故障修復率、虛擬網絡成功運行率和工作鏈路資源利用率3個方面對故障備份鏈路重映射算法和區分用戶優先級的故障恢復算法進行驗證，仿真結果如圖2到圖9所示。

圖2 故障備份鏈路重映射算法對虛擬網絡故障修復率的影響

5.2 故障備份鏈路重映射算法驗證實驗

5.3 區分用戶優先級的故障恢復算法驗證實驗

圖3 故障備份鏈路重映射算法對虛擬網絡成功運行率的影響

圖4 =0.1時虛擬網絡故障修復率

圖5 =0.5時虛擬網絡故障修復率

圖6 =0.1時虛擬網絡成功運行率

圖7 =0.5時虛擬網絡成功運行率

圖8 =0.1時工作鏈路資源利用率

圖9 =0.5時工作鏈路資源利用率

6 結論

以Openflow網絡為代表的虛擬化網絡能夠滿足不同用戶的多樣化業務需求，支持多種路由協議，保護用戶信息的安全，推動傳統互聯網架構向下一代架構體系演進。本文以網絡中最易發生的單鏈路故障為前提，基于不同用戶的網絡可靠性需求不同，設計了區分用戶優先級的故障恢復算法；為了增強備份鏈路的可用性，提出了故障備份鏈路重映射算法。最后從虛擬網絡故障修復率、虛擬網絡成功運行率、工作鏈路資源利用率方面證明了兩種算法的優越性。

[1] Chowdhury N M M K and Boutaba R. A survey of network virtualization[J]., 2010, 54(5): 862-876.

[3] Bless R and Werle C. Network virtualization from a signaling perspective[C]. IEEE ICC Workshops Proceedings, Dresden, Germany, June 14-18, 2009: 1-6.

[4] Sherwood R, Chan M, Gibb G,.. Carving research slices out of your production network with openflow[J]., 2010, 40(1): 129-130.

[5] Chowdhury N, Rahman M, and Boutaba R. Virtual network embedding with coordinated node and link mapping[C]. IEEE INFOCOM Proceedings, Rio de Janeiro, Brazil, Apr. 19-25, 2009: 783-791.

[6] 呂博, 楊帆, 王振凱, 等. 一種基于區域劃分的虛擬網映射新算法[J]. 電子與信息學報, 2011, 33(10): 2347-2352.

Lü Bo, Yang Fan, Wang Zhen-kai,.. A novel virtual network mapping algorithm based on regionalization[J].&, 2011, 33(10): 2347-2352.

[7] 李文, 吳春明, 陳健, 等. 物理節點可重復映射的虛擬網映射算法[J]. 電子與信息學報, 2011, 33(4): 908-914.

Li Wen, Wu Chun-ming, Chen Jian,.. Virtual network mapping algorithm with repeatable mapping over substrate nodes[J].&, 2011, 33(4): 908-914.

[8] Butt N, Chowdhury M, and Boutaba R. Topology-awareness and re-optimization mechanism for virtual network embedding[C]. Proceedings of 9th International Networking Conference, Chennai, India, 2010:27-39.

[9] Raihan M, Issam A, and Boutaba R. Survivable virtual network embedding[C]. Proceedings of the 9th International Networking Conference, Chennai, India, 2010: 40-52.

[10] Yeow W L, Wsestphal C, and Kozat U C. Designing and embedding reliable virtual infrastructures[J]., 2011, 41(2): 57-64.

[11] Chowdhury M, Raihan M, and Boutaba R. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping[J]./, 2012, 20(1): 206-219.

[12] Houidi I, Louati W, and Zeghlache D. A distributed virtual network mapping algorithm[C]. IEEE International Conference on Communications,France, 2008: 5634-5640.

[13] Fajjari I, Saadi N A, Pujolle G,.. VNE-AC: virtual network embedding algorithm based on ant colony metaheuristic[C]. IEEE International Conference on Communications, Kyoto, 2011: 1-6.

[14] Iannaccone G, Chuah C, Mortier R,.. Analysis of link failures in an IP backbone[C]. Proceedings of ACM SIGCOMM Internet Mensurenient Workshop 2002, Marseille, France, 2002: 237-242.

[15] Markopulou A, Iannaccone G, and Bhattacharyya S. Characterization of failures in an IP backbone[C]. Proceedings of INFOCOM 2004, Hong Kong, China, 2004: 2307-2317.

[16] Zegura E, Calvert K, and Bhattacharjee S. How to model an Internetwork[C]. IEEE INFOCOM Proceedings, San Francisco, Mar. 24-28, 1996: 594-602.

[17] 齊寧, 汪斌強, 王志明. 可重構服務承載網容錯構建算法研究[J]. 電子與信息學報, 2012, 34(2): 468-473.

Qi Ning, Wang Bin-qiang, and Wang Zhi-ming. Research on reconfigurable service carrying network resilient construction algorithms[J].&, 2012, 34(2): 468-473.

蔡進科： 男，1988年生，碩士生，研究方向為數據中心網絡、網絡虛擬化.

顧華璽： 男，1977 年生，博士，副教授，研究方向為網絡技術、片上網絡以及光互連等.

盧 冀： 男，1981 年生，博士后，研究方向為云計算、網絡虛擬化、網絡服務.

Highly Reliable Virtual Network Mapping Algorithm Based on Openflow Network

Cai Jin-ke①Gu Hua-xi①Lu Ji②Yu Xiao-shan①

①(,,’710071,)②(..,050081,)

A fault tolerant virtual network mapping model based on Openflow network is proposed, and it is solved by the ant colony algorithm. In view of the virtual network fault recovery mechanism, a distinction user priority failure recovery algorithm named Priority_Diff is proposed, and the algorithm provides users different network reliability levels. The failed link is replaced by a backup path for advanced users, and remapped for low-level users. In addition, a failed Backup Link ReMapping (BLRM) algorithm is proposed, and the backup resources in the failed link are migrated to the adjacent link, which improves the availability of the backup link. Finally, the performance parameters, including virtual network failure repairing ratio, virtual network success running ratio, and working link resource utilization are evaluated by simulation experiments, and the results demonstrate the superiority of the proposed algorithms.

Virtual network; Openflow; Mapping algorithm; Reliability

TP393

A

1009-5896(2014)02-0396-07

10.3724/SP.J.1146.2013.00367

蔡進科 bestcaicai@126.com

2013-03-22收到，2013-08-12改回

國家自然科學基金(60803038, 61070046)，國家重點實驗室專項基金(ISN1104001)，中央高校基本業務費項目(K5051301003)，高等學校學科創新引智計劃(B08038)和通信網信息傳輸與分發技術重點實驗室(ITD-U12002)資助課題