蔡進(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ū)分用戶(hù)優(yōu)先級(jí)的故障恢復(fù)算法(Priority_Diff)，該算法為用戶(hù)提供不同的網(wǎng)絡(luò)可靠性級(jí)別，對(duì)高級(jí)用戶(hù)采用提前映射的備份路徑替代故障鏈路，對(duì)低級(jí)用戶(hù)重新映射故障鏈路；設(shè)計(jì)了故障備份鏈路重映射(BLRM)算法，將故障鏈路中的備份資源遷移到相鄰鏈路，增強(qiáng)了備份鏈路的可用性。最后，通過(guò)仿真實(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)在過(guò)去的幾十年里飛速發(fā)展，隨著用戶(hù)業(yè)務(wù)越來(lái)越豐富，傳統(tǒng)網(wǎng)絡(luò)的“傻瓜式網(wǎng)絡(luò)+智能終端”的構(gòu)網(wǎng)方式無(wú)法滿(mǎn)足不同用戶(hù)業(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ā)層分離，是未來(lái)虛擬化網(wǎng)絡(luò)的雛形[4]。

Openflow網(wǎng)絡(luò)是由多個(gè)網(wǎng)絡(luò)域相互連接構(gòu)成，每個(gè)網(wǎng)絡(luò)域包括一個(gè)控制器，一個(gè)或多個(gè)Openflow交換機(jī)以及若干主機(jī)?？刂破鞒休d的是該域內(nèi)的控制資源，主要負(fù)責(zé)運(yùn)行不同的路由協(xié)議，并且計(jì)算出相應(yīng)的路由流表。Openflow交換機(jī)承載的是轉(zhuǎn)發(fā)資源，通過(guò)運(yùn)行在安全通道上的Openflow協(xié)議與控制器通信，根據(jù)控制器產(chǎn)生的流表來(lái)轉(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ò)映射問(wèn)題抽象為混合整數(shù)規(guī)劃問(wèn)題，針對(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)了鏈路映射的過(guò)程，并且提出了一種物理節(jié)點(diǎn)可重復(fù)映射的虛擬網(wǎng)絡(luò)映射算法。但是在真實(shí)環(huán)境下，物理網(wǎng)絡(luò)經(jīng)常由于地震、泥石流等自然原因或者惡意攻擊等非自然原因發(fā)生故障，影響用戶(hù)業(yè)務(wù)的正常運(yùn)行。而上述的這些算法都是針對(duì)物理網(wǎng)絡(luò)的資源利用率最大，沒(méi)有考慮因?yàn)榫W(wǎng)絡(luò)故障而導(dǎo)致的虛擬網(wǎng)絡(luò)可靠性問(wèn)題。

針對(duì)虛擬網(wǎng)絡(luò)的可靠性問(wèn)題，文獻(xiàn)[8]提出了一種虛擬節(jié)點(diǎn)和虛擬鏈路的重映射機(jī)制，不但可以提高虛擬網(wǎng)絡(luò)的接收率而且有利于網(wǎng)絡(luò)的負(fù)載均衡。文獻(xiàn)[9]通過(guò)預(yù)先構(gòu)建備份路徑，將故障的虛擬鏈路遷移到備份路徑。文獻(xiàn)[10]通過(guò)構(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ī)制?？紤]到不同用戶(hù)的網(wǎng)絡(luò)可靠性需求不同，銀行、金融和軍事機(jī)構(gòu)等用戶(hù)要求自己的業(yè)務(wù)24小時(shí)正常運(yùn)行；而像學(xué)校、社交論壇等大部分的普通用戶(hù)對(duì)網(wǎng)絡(luò)的可靠性需求相對(duì)較弱。通過(guò)為不同用戶(hù)提供不同級(jí)別的網(wǎng)絡(luò)可靠性保證，提出了區(qū)分用戶(hù)優(yōu)先級(jí)的故障恢復(fù)算法(Priority_Diff)，即對(duì)受到故障影響的高優(yōu)先級(jí)用戶(hù)的流量遷移到預(yù)先設(shè)定的備份路徑，而對(duì)低優(yōu)先級(jí)用戶(hù)的故障鏈路進(jìn)行重新映射。該算法可以有效兼顧物理網(wǎng)絡(luò)資源利用率和網(wǎng)絡(luò)的容錯(cuò)抗毀特性。同時(shí)，由于物理鏈路上同時(shí)承載著工作資源和備份資源，備份資源故障很可能導(dǎo)致后續(xù)的故障鏈路修復(fù)失敗，為了增強(qiáng)備份鏈路的可用性，本文提出了故障備份鏈路重映射(BLRM)算法。最后通過(guò)仿真實(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)要能夠滿(mǎn)足所承載的虛擬節(jié)點(diǎn)的轉(zhuǎn)發(fā)資源需求，而且該物理節(jié)點(diǎn)所在域也必須能夠滿(mǎn)足虛擬節(jié)點(diǎn)的控制資源需求。除此之外，采用的是最經(jīng)典的映射方式，即虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)是一對(duì)一的映射[11]。滿(mǎn)足的約束條件如式(1)所示。

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

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

根據(jù)上述映射規(guī)則，在圖1所示的實(shí)例中，高優(yōu)先級(jí)用戶(hù)的虛擬網(wǎng)絡(luò)請(qǐng)求1的兩個(gè)虛擬節(jié)點(diǎn),分別映射到物理節(jié)點(diǎn),上，虛擬鏈路(,)對(duì)應(yīng)地映射到物理鏈路(,)上，同時(shí)創(chuàng)建備份路徑(,,)；低優(yōu)先級(jí)用戶(hù)的虛擬網(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ò)映射問(wèn)題由于數(shù)學(xué)模型復(fù)雜、約束條件多是公認(rèn)的NP-hard問(wèn)題[12]，求解算法需要滿(mǎn)足以下條件：很強(qiáng)的收斂性，保證算法能夠在有限次迭代之后找到優(yōu)化目標(biāo)的近似解；低算法復(fù)雜度，保證算法在較短的時(shí)間內(nèi)運(yùn)行完成；高魯棒性，保證求得的解為全局最優(yōu)解，避免陷入局部最優(yōu)解問(wèn)題。

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

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ā)生和最常見(jiàn)的問(wèn)題。為了提高Openflow網(wǎng)絡(luò)的可靠性，本文針對(duì)單鏈路故障問(wèn)題，提出了區(qū)分用戶(hù)優(yōu)先級(jí)的故障恢復(fù)算法，以及增強(qiáng)備份資源有效性的故障備份鏈路重映射算法，構(gòu)建了一套有效的虛擬網(wǎng)絡(luò)故障恢復(fù)機(jī)制。

4.1 區(qū)分用戶(hù)優(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ū)分用戶(hù)優(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ū)分用戶(hù)優(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ò)能夠滿(mǎn)足不同用戶(hù)的多樣化業(yè)務(wù)需求，支持多種路由協(xié)議，保護(hù)用戶(hù)信息的安全，推動(dòng)傳統(tǒng)互聯(lián)網(wǎng)架構(gòu)向下一代架構(gòu)體系演進(jìn)。本文以網(wǎng)絡(luò)中最易發(fā)生的單鏈路故障為前提，基于不同用戶(hù)的網(wǎng)絡(luò)可靠性需求不同，設(shè)計(jì)了區(qū)分用戶(hù)優(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)室專(zhuān)項(xiàng)基金(ISN1104001)，中央高校基本業(yè)務(wù)費(fèi)項(xiàng)目(K5051301003)，高等學(xué)校學(xué)科創(chuàng)新引智計(jì)劃(B08038)和通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室(ITD-U12002)資助課題