， ， ，

(1.北京信息科技大學(xué) 計算中心 北京 100192； 2.河南財政金融學(xué)院(龍子湖校區(qū))信息技術(shù)系 河南 鄭州 450014； 3.北京郵電大學(xué) 電子工程系 北京 100876)

0 引言

隨著移動通信和互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，數(shù)據(jù)信息處理方法變得多種多樣，這導(dǎo)致了多種業(yè)務(wù)類型(如互聯(lián)網(wǎng)應(yīng)用服務(wù)、云平臺租用等)并存的異構(gòu)通信網(wǎng)絡(luò)的產(chǎn)生.針對異構(gòu)網(wǎng)絡(luò)融合，多是采用在現(xiàn)有互聯(lián)網(wǎng)架構(gòu)上進行修補的方式，致使當前互聯(lián)網(wǎng)變得非常臃腫復(fù)雜，為了改善這一現(xiàn)象，網(wǎng)絡(luò)虛擬化[1]的思路應(yīng)運而生，其中軟件定義網(wǎng)絡(luò)(software-defined network，SDN)技術(shù)的誕生[2]，為網(wǎng)絡(luò)虛擬化的實施提供了方法.

面向容錯的虛擬網(wǎng)絡(luò)映射是指在發(fā)生網(wǎng)絡(luò)故障時，虛擬網(wǎng)絡(luò)仍然能夠保持正常工作的一種物理網(wǎng)絡(luò)資源分配方式[3-4].網(wǎng)絡(luò)故障恢復(fù)對于用戶來說是透明的，用戶感知不到網(wǎng)絡(luò)資源的切換.可生存性的虛擬網(wǎng)絡(luò)映射一般采用為節(jié)點和鏈路分配冗余資源的方式來應(yīng)對網(wǎng)絡(luò)故障問題，這給網(wǎng)絡(luò)供應(yīng)商帶來了額外的花銷，并且當網(wǎng)絡(luò)不發(fā)生故障時，為虛擬鏈路提供1∶1的冗余資源無疑是一種巨大的浪費.所以，相對于專用備份，一些備份資源共享的方案被提出.文獻[5]提出按需共享和預(yù)分配共享兩種共享方案，這兩種方式均支持用于故障恢復(fù)的帶寬共享，但是用于業(yè)務(wù)的主用帶寬相互獨立.為了提高備份資源的利用率，提高虛擬網(wǎng)絡(luò)(virtual networks，VN)的接受率，一種支持節(jié)點遷移的生存性映射方案被提出.在發(fā)生網(wǎng)絡(luò)單節(jié)點故障后，可以將受影響的虛擬節(jié)點遷移和映射至備份物理節(jié)點，或者各個虛擬節(jié)點在VN范圍內(nèi)進行內(nèi)部遷移，以減少備份帶寬，實現(xiàn)VN自身內(nèi)的帶寬資源共享.但是,現(xiàn)在關(guān)于無線網(wǎng)絡(luò)的研究還較少，尤其是視頻業(yè)務(wù)的急劇增加，用戶對無線網(wǎng)絡(luò)的要求越來越高[4]，因此無線網(wǎng)的性能優(yōu)化問題也亟待解決.文獻[5]從應(yīng)用層面、云層面、頻譜層面和合作層面服務(wù)于特定的用戶，通過業(yè)務(wù)切片實現(xiàn)無線網(wǎng)絡(luò)的虛擬化管理.文獻[6]對于無線傳感網(wǎng)絡(luò)虛擬化進行了研究，并利用虛擬化技術(shù)實現(xiàn)對設(shè)備的靈活管理.文獻[7]基于5G提出了一種以網(wǎng)絡(luò)切片管理為核心的管理方案，借助網(wǎng)絡(luò)功能虛擬化技術(shù)實現(xiàn)網(wǎng)絡(luò)切片創(chuàng)建與修改的完全自動化.文獻[8]通過分析無線虛擬網(wǎng)絡(luò)的相關(guān)特性，提出一種針對鏈路可靠性的映射算法，并且通過引入Q因子解決了因為拓撲分配效率低而造成的虛擬請求接受率低的問題.文獻[9]提出了一種改進的基于Q-learning算法的虛擬演進分析核心網(wǎng)的功能部署方法，與傳統(tǒng)虛擬化網(wǎng)絡(luò)功能部署方法相比，該方法在降低網(wǎng)絡(luò)時延的同時，可提高虛擬化網(wǎng)絡(luò)功能部署的受益和請求接受率.文獻[10]提出了一種在SDN下保證小流時延的QoS機制，降低了小流時延的傳輸時延.文獻[11]設(shè)計了一個利用聚類分析算法進行虛擬網(wǎng)絡(luò)劃分的方法，用于提高SDN資源的利用效率.上述文獻多數(shù)從IP層或應(yīng)用層對網(wǎng)絡(luò)性能進行改善，由于多個虛擬網(wǎng)絡(luò)共享底層設(shè)施，隨機失效就會導(dǎo)致大量的虛擬網(wǎng)絡(luò)崩潰，將會使租用虛擬網(wǎng)絡(luò)的網(wǎng)絡(luò)服務(wù)提供商蒙受巨大經(jīng)濟損失[12-15].

本文給出了一種面向容錯的網(wǎng)絡(luò)虛擬化資源管理與映射算法，首先將無線設(shè)備納入虛擬化架構(gòu)中，然后基于最小割集理論，在路徑選擇過程中考慮備用路徑，提高映射的可靠性，最后給出仿真結(jié)果和分析.

1 虛擬資源抽象模型

1.1 虛擬化網(wǎng)絡(luò)資源抽象

對于鏈路資源，主要考慮的是鏈路上的帶寬資源.當有用戶發(fā)出虛擬請求，只需考慮底層物理鏈路帶寬是否滿足請求虛擬帶寬.若鏈路映射支持路徑分割，則一條虛擬路徑可以映射到兩點間的多條路徑，只需帶寬和滿足虛擬請求帶寬.鏈路剩余資源定義為

其中：B和W分別為有線和無線鏈路帶寬資源，當鏈路為有線時，λ=1，當鏈路為無線時，λ=0；γ為無線物理鏈路帶寬擴張因子，與該物理鏈路長度、信道質(zhì)量有關(guān).

1.2 虛擬網(wǎng)絡(luò)映射問題描述

本文借助備份路由的思路來分析虛擬映射網(wǎng)絡(luò)的容錯.由于路徑選擇算法有較高的算法復(fù)雜度，在進行故障鏈路重映射時會有較高的時延，從而造成用戶數(shù)據(jù)的丟失.在虛擬請求到達之前，采用路徑選擇算法為每一條底層鏈路計算一組備份路徑，可以縮短重映射時延.路徑選擇算法可以是k條最短路徑算法或者是列生成算法和原始對偶方法.本文中采用的是k條最短路徑算法.這樣，對于每一條底層鏈路來說，都有一組備份路徑相對應(yīng)，可以用備份鏈路集來表示.底層鏈路與備份路徑具有相同的起始節(jié)點和終止節(jié)點，在故障發(fā)生時，可以從備份鏈路集中選擇合適的備份鏈路進行鏈路重映射.當一個底層鏈路發(fā)生故障時，必須為其選擇一條備份路徑，該路徑與故障鏈路具有相同的起始節(jié)點和終止節(jié)點.由于網(wǎng)絡(luò)的連接性，一條鏈路l擁有多條可供選擇的備份路徑x.在底層網(wǎng)絡(luò)中，跳數(shù)每增加一個，將會造成更多的帶寬花費和引入更多的時延，所以在本文中將跳數(shù)作為衡量備份路徑優(yōu)劣的指標.為了提高備份路由集的質(zhì)量，將符合跳數(shù)標準的路徑納入到備份路由集之中.

定義一個函數(shù)P(Gs,l,h)={xhop(x)=h,h≥1},該函數(shù)返回與鏈路l的起始節(jié)點相同的跳數(shù)為h的路徑的集合Px.圖1中，P(Gs,AB,2)={ADB,ACB}，鏈路AB的跳數(shù)為2的備份路徑的集合為ADB和ACB兩條路徑.

圖1 備份鏈路Fig.1 Backup chains

另外，定義一個函數(shù)Cov(Gs,l,h)，該函數(shù)返回鏈路l的跳數(shù)小于等于h的路徑的集合Covx，其中h為大于等于1的整數(shù).例如，鏈路AB跳數(shù)大于2的備份路徑集合Cov(Gs,AB,2)={AB,ADB,ACB}.那么，如果定義了性能指標h,則滿足條件的備份鏈路集可以表示為C(Gs,l,h)=Cov(Gs,l,h)-P(Gs,l,1).如圖1所示，當h=3時，鏈路AB的備份鏈路集為Cov(Gs,AB,3),其值為跳數(shù)小于等于3的以A和B為節(jié)點的路徑的集合減去路徑AB本身，一共有3組，分別為ACB、ADB和ACDB.當鏈路AB發(fā)生故障時，AB所承載的流量可由3組中的任意一條路徑承載.

2 面向容錯的虛擬映射算法

2.1 魯棒性虛擬映射算法描述

當?shù)讓渔溌钒l(fā)生故障時，能否成功進行鏈路的重映射取決于底層鏈路備份路由集合的資源狀態(tài).如果備份路由集合的路徑擁有足夠的可用資源，并且處于良好的工作狀態(tài)，那么當鏈路發(fā)生故障時，重映射成功的概率比較高.如果備份路由集合沒有足夠的資源為底層鏈路提供流量的重路由，那么底層鏈路重映射成功的概率比較低.所以，在進行鏈路映射時，將關(guān)鍵鏈路映射至具有良好資源狀態(tài)的備份路由集的底層鏈路上，將會提高鏈路故障的恢復(fù)率.針對系統(tǒng)的魯棒性，具有容錯能力的映射過程方法如下.

1) 節(jié)點映射階段

(1)

≥2,

(2)

δ(na,nb)=1.

(3)

式(1)為虛擬節(jié)點映射的目標函數(shù)，首先根據(jù)用戶位置選擇覆蓋范圍內(nèi)若干備選節(jié)點，然后根據(jù)節(jié)點的映射能力為虛擬請求分配最佳節(jié)點;式(2)表示物理節(jié)點a、b之間的路徑數(shù)大于1條，即路徑ab有備選路徑;式(3)表示物理節(jié)點a、b屬于統(tǒng)一社區(qū).

2) 鏈路映射階段

目標函數(shù)為

MaximizeR/C.

(4)

約束條件為

(5)

(6)

(7)

(8)

式(4)為虛擬映射的目標函數(shù)，該式表示了物理網(wǎng)絡(luò)接受虛擬請求，并且完成一次虛擬映射時的收益與成本的關(guān)系，反映了虛擬映射對于物理資源的使用效率；式(5)為鏈路帶寬資源約束條件；式(6)為連接性約束條件；式(7)表示鏈路的二進制約束；式(8)為魯棒性約束，表示該約束下虛擬映射具有魯棒性.

2.2 依概率選擇的魯棒性提升

定義鏈路生存概率S(l)來表示如果鏈路發(fā)生故障時，能夠通過重映射來恢復(fù)的概率.在進行鏈路映射時，通過計算鏈路生存概率S(l)來選擇生存概率較高的路徑，從而提高虛擬網(wǎng)絡(luò)映射的鏈路可生存性.S(l)的大小取決于鏈路l的備份路由集合可承載的流量A(l)與l已承載流量U(l)之間的關(guān)系，如果U(l)遠遠大于A(l)，那么當l發(fā)生故障時，其備份路由集可以滿足l的重路由需求，即鏈路生存概率S(l)值較高.A(l)和U(l)的值可由以下公式計算獲得,

3 仿真結(jié)果

在本節(jié)仿真中，對于底層物理網(wǎng)絡(luò)，我們在25*25的范圍內(nèi)隨機生成100個節(jié)點，節(jié)點的CPU資源和鏈路的帶寬資源都是100到150的均勻分布，每對節(jié)點的連接概率是0.3.而相對于虛擬請求，每個虛擬拓撲的節(jié)點數(shù)量是一個[5,15]的整數(shù)均勻分布，它們抵達底層網(wǎng)絡(luò)的時間間隔服從泊松分布，其均值為每10個單位時間內(nèi)有一個請求，并且虛擬請求的被服務(wù)時間是一個均值為1 000個單位時間的指數(shù)分布.對于每一個虛擬請求，它的虛擬節(jié)點的CPU資源服從均勻分布，其范圍為(0,20],鏈路也服從均勻分布，范圍是(0,50]，并且每兩個節(jié)點間的連接概率均為0.5.

圖2 基于收益成本比的虛擬網(wǎng)絡(luò)映射Fig.2 Virtual net mapping based on ratio of cost and benefit

如圖2所示，收入支出比R/C表示了虛擬請求的收益和成本之比，是虛擬映射算法的重要評價指標.通過仿真可以看出，當請求數(shù)目固定的情況下，隨著每個請求的節(jié)點個數(shù)的增多，虛擬網(wǎng)絡(luò)的收益和成本之比是下降的.網(wǎng)絡(luò)映射平均數(shù)反映了節(jié)點壓力，拓撲識別有效利用底層網(wǎng)絡(luò)資源，雖然備用路徑的選擇增加了物理實體網(wǎng)絡(luò)的資源耗損，當節(jié)點壓力增大后，收益和成本之比卻沒有大幅度增加，且壓力越大算法越穩(wěn)定.由此可以看出魯棒性映射算法更加高效.

如圖3所示，由觀測收入支出比R/C可以看出，隨著虛擬請求平均節(jié)點數(shù)目的增加，即虛擬請求規(guī)模的增大，改進后的魯棒性算法與改進前相比，具有更好的資源利用率.在相同的虛擬請求下，魯棒性虛擬映射算法得出的映射方案占用底層資源更少，意味著其占用的底層鏈路資源更少，這樣當?shù)讓渔溌钒l(fā)生故障時，受影響的虛擬鏈路會更少，其容錯性相比改進前虛擬映射算法也更高.

如圖4所示，隨著底層物理網(wǎng)絡(luò)故障率的增大，改進前和改進后收入支出比均在下降，說明隨著鏈路故障增多，底層物理網(wǎng)絡(luò)節(jié)點的連接度越來越小，映射一個虛擬請求需要的底層資源越來越多，因此R/C是呈下降狀態(tài).同時從圖中可以看出，改進后的魯棒性算法與改進前相比收入支出比更高，說明魯棒性虛擬映射算法對故障的容忍度更高，對于網(wǎng)絡(luò)中的突發(fā)故障，具有更高的容錯性能.

圖3 不同虛擬映射壓力下的魯棒性虛擬映射算法Fig.3 Virtual mapping algorithm of robust in different pressures of virtual mapping

圖4 不同容錯故障下的魯棒性虛擬映射算法Fig.4 Virtual mapping algorithm of robust for different fault tolerance

4 結(jié)束語

為了提高網(wǎng)絡(luò)的容錯性，本文將連通性作為判定指標，從理論上分析了隨機網(wǎng)絡(luò)下的連通性判定問題，從容錯的角度全面分析了虛擬路由通信安全問題.仿真驗證表明，在節(jié)點壓力較大、容錯故障率較高的情況下，改進后的算法具有更高的虛擬請求成功率和更低的資源占用率.