基于Openflow網(wǎng)絡(luò)的高可靠性虛擬網(wǎng)絡(luò)映射算法

蔡進(jìn)科 顧華璽 盧 冀 余曉杉

?

基于Openflow網(wǎng)絡(luò)的高可靠性虛擬網(wǎng)絡(luò)映射算法

蔡進(jìn)科*①顧華璽①盧 冀②余曉杉①

①(西安電子科技大學(xué)ISN國(guó)家重點(diǎn)實(shí)驗(yàn)室 西安 710071)②(通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室 石家莊 050081)

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

虛擬網(wǎng)絡(luò)；Openflow；映射算法；可靠性

1 引言

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

Openflow網(wǎng)絡(luò)是由多個(gè)網(wǎng)絡(luò)域相互連接構(gòu)成，每個(gè)網(wǎng)絡(luò)域包括一個(gè)控制器，一個(gè)或多個(gè)Openflow交換機(jī)以及若干主機(jī)。控制器承載的是該域內(nèi)的控制資源，主要負(fù)責(zé)運(yùn)行不同的路由協(xié)議，并且計(jì)算出相應(yīng)的路由流表。Openflow交換機(jī)承載的是轉(zhuǎn)發(fā)資源，通過運(yùn)行在安全通道上的Openflow協(xié)議與控制器通信，根據(jù)控制器產(chǎn)生的流表來轉(zhuǎn)發(fā)數(shù)據(jù)。

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

針對(duì)虛擬網(wǎng)絡(luò)的可靠性問題，文獻(xiàn)[8]提出了一種虛擬節(jié)點(diǎn)和虛擬鏈路的重映射機(jī)制，不但可以提高虛擬網(wǎng)絡(luò)的接收率而且有利于網(wǎng)絡(luò)的負(fù)載均衡。文獻(xiàn)[9]通過預(yù)先構(gòu)建備份路徑，將故障的虛擬鏈路遷移到備份路徑。文獻(xiàn)[10]通過構(gòu)建統(tǒng)一的備份資源池，為虛擬鏈路動(dòng)態(tài)地分配備份資源，提高了物理資源的利用率。上述這些算法分別采用不同的機(jī)制提高虛擬網(wǎng)絡(luò)的可靠性，但是它們或者故障發(fā)生時(shí)才進(jìn)行鏈路重映射，故障修復(fù)率低，或者提前預(yù)留備份資源，成本太高，或者不能應(yīng)對(duì)連續(xù)的多個(gè)網(wǎng)絡(luò)故障。

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

2 基于Openflow網(wǎng)絡(luò)的容錯(cuò)映射模型

2.1 Openflow網(wǎng)絡(luò)描述

2.2 映射描述

如圖1所示，圖1(a)所示為兩個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，方框內(nèi)為該節(jié)點(diǎn)所需要的控制資源和轉(zhuǎn)發(fā)資源，鏈路上的數(shù)字為所需要的帶寬；圖1(b)所示為Openflow網(wǎng)絡(luò)模型，節(jié)點(diǎn)旁的方框內(nèi)為該節(jié)點(diǎn)的轉(zhuǎn)發(fā)資源，控制器旁的方框內(nèi)為該域內(nèi)的控制資源。

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

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

圖1 Openflow網(wǎng)絡(luò)映射實(shí)例

根據(jù)上述映射規(guī)則，在圖1所示的實(shí)例中，高優(yōu)先級(jí)用戶的虛擬網(wǎng)絡(luò)請(qǐng)求1的兩個(gè)虛擬節(jié)點(diǎn),分別映射到物理節(jié)點(diǎn),上，虛擬鏈路(,)對(duì)應(yīng)地映射到物理鏈路(,)上，同時(shí)創(chuàng)建備份路徑(,,)；低優(yōu)先級(jí)用戶的虛擬網(wǎng)絡(luò)請(qǐng)求2的4個(gè)虛擬節(jié)點(diǎn),,,分別映射到物理節(jié)點(diǎn),,,上，虛擬鏈路(,),(,),(,)對(duì)應(yīng)地映射到物理鏈路(,), (,),(,)上。

2.3 映射目標(biāo)

3 虛擬網(wǎng)絡(luò)求解算法

虛擬網(wǎng)絡(luò)映射問題由于數(shù)學(xué)模型復(fù)雜、約束條件多是公認(rèn)的NP-hard問題[12]，求解算法需要滿足以下條件：很強(qiáng)的收斂性，保證算法能夠在有限次迭代之后找到優(yōu)化目標(biāo)的近似解；低算法復(fù)雜度，保證算法在較短的時(shí)間內(nèi)運(yùn)行完成；高魯棒性，保證求得的解為全局最優(yōu)解，避免陷入局部最優(yōu)解問題。

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

00 Initialization(); //對(duì)物理網(wǎng)絡(luò)和仿真參數(shù)進(jìn)行初始化

01 VN_Creation(); //按照泊松分布產(chǎn)生虛擬網(wǎng)絡(luò)構(gòu)建請(qǐng)求

02 For=1 to//迭代次

03 { Update_probability(); //根據(jù)信息素更新虛擬節(jié)點(diǎn)對(duì)物理節(jié)點(diǎn)的映射概率

04 For ant=1 to//每次迭代產(chǎn)生只螞蟻

05 { Node_Map(); //根據(jù)映射概率進(jìn)行節(jié)點(diǎn)映射

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

07 if((local_solution)>(global_solution)) //比較當(dāng)前解和最優(yōu)解的資源剩余量

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

09 }

10 Update_info(); //更新虛擬節(jié)點(diǎn)對(duì)物理節(jié)點(diǎn)的信息素

11 }

4 虛擬網(wǎng)絡(luò)故障恢復(fù)機(jī)制

在骨干網(wǎng)中單鏈路故障占全部故障的70%[14,15]，是最易發(fā)生和最常見的問題。為了提高Openflow網(wǎng)絡(luò)的可靠性，本文針對(duì)單鏈路故障問題，提出了區(qū)分用戶優(yōu)先級(jí)的故障恢復(fù)算法，以及增強(qiáng)備份資源有效性的故障備份鏈路重映射算法，構(gòu)建了一套有效的虛擬網(wǎng)絡(luò)故障恢復(fù)機(jī)制。

4.1 區(qū)分用戶優(yōu)先級(jí)的故障恢復(fù)算法

(1)判斷故障鏈路上所承載虛擬網(wǎng)絡(luò)的優(yōu)先級(jí)；

對(duì)受該故障影響的所有虛擬網(wǎng)絡(luò)逐一運(yùn)行該算法，故障修復(fù)完成。

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

5 實(shí)驗(yàn)結(jié)果及分析

5.1 實(shí)驗(yàn)設(shè)定

本文主要從虛擬網(wǎng)絡(luò)故障修復(fù)率、虛擬網(wǎng)絡(luò)成功運(yùn)行率和工作鏈路資源利用率3個(gè)方面對(duì)故障備份鏈路重映射算法和區(qū)分用戶優(yōu)先級(jí)的故障恢復(fù)算法進(jìn)行驗(yàn)證，仿真結(jié)果如圖2到圖9所示。

圖2 故障備份鏈路重映射算法對(duì)虛擬網(wǎng)絡(luò)故障修復(fù)率的影響

5.2 故障備份鏈路重映射算法驗(yàn)證實(shí)驗(yàn)

5.3 區(qū)分用戶優(yōu)先級(jí)的故障恢復(fù)算法驗(yàn)證實(shí)驗(yàn)

圖3 故障備份鏈路重映射算法對(duì)虛擬網(wǎng)絡(luò)成功運(yùn)行率的影響

圖4 =0.1時(shí)虛擬網(wǎng)絡(luò)故障修復(fù)率

圖5 =0.5時(shí)虛擬網(wǎng)絡(luò)故障修復(fù)率

圖6 =0.1時(shí)虛擬網(wǎng)絡(luò)成功運(yùn)行率

圖7 =0.5時(shí)虛擬網(wǎng)絡(luò)成功運(yùn)行率

圖8 =0.1時(shí)工作鏈路資源利用率

圖9 =0.5時(shí)工作鏈路資源利用率

6 結(jié)論

以O(shè)penflow網(wǎng)絡(luò)為代表的虛擬化網(wǎng)絡(luò)能夠滿足不同用戶的多樣化業(yè)務(wù)需求，支持多種路由協(xié)議，保護(hù)用戶信息的安全，推動(dòng)傳統(tǒng)互聯(lián)網(wǎng)架構(gòu)向下一代架構(gòu)體系演進(jìn)。本文以網(wǎng)絡(luò)中最易發(fā)生的單鏈路故障為前提，基于不同用戶的網(wǎng)絡(luò)可靠性需求不同，設(shè)計(jì)了區(qū)分用戶優(yōu)先級(jí)的故障恢復(fù)算法；為了增強(qiáng)備份鏈路的可用性，提出了故障備份鏈路重映射算法。最后從虛擬網(wǎng)絡(luò)故障修復(fù)率、虛擬網(wǎng)絡(luò)成功運(yùn)行率、工作鏈路資源利用率方面證明了兩種算法的優(yōu)越性。

[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] 呂博, 楊帆, 王振凱, 等. 一種基于區(qū)域劃分的虛擬網(wǎng)映射新算法[J]. 電子與信息學(xué)報(bào), 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] 李文, 吳春明, 陳健, 等. 物理節(jié)點(diǎn)可重復(fù)映射的虛擬網(wǎng)映射算法[J]. 電子與信息學(xué)報(bào), 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] 齊寧, 汪斌強(qiáng), 王志明. 可重構(gòu)服務(wù)承載網(wǎng)容錯(cuò)構(gòu)建算法研究[J]. 電子與信息學(xué)報(bào), 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.

蔡進(jìn)科： 男，1988年生，碩士生，研究方向?yàn)閿?shù)據(jù)中心網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化.

顧華璽： 男，1977 年生，博士，副教授，研究方向?yàn)榫W(wǎng)絡(luò)技術(shù)、片上網(wǎng)絡(luò)以及光互連等.

盧 冀： 男，1981 年生，博士后，研究方向?yàn)樵朴?jì)算、網(wǎng)絡(luò)虛擬化、網(wǎng)絡(luò)服務(wù).

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

蔡進(jìn)科 bestcaicai@126.com

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

國(guó)家自然科學(xué)基金(60803038, 61070046)，國(guó)家重點(diǎn)實(shí)驗(yàn)室專項(xiàng)基金(ISN1104001)，中央高?；緲I(yè)務(wù)費(fèi)項(xiàng)目(K5051301003)，高等學(xué)校學(xué)科創(chuàng)新引智計(jì)劃(B08038)和通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室(ITD-U12002)資助課題