可生存性虛擬網(wǎng)絡(luò)映射算法的研究

黃麗萍，楊龍祥

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

網(wǎng)絡(luò)虛擬化技術(shù)被視為是構(gòu)建新一代網(wǎng)絡(luò)的重要技術(shù)，可以有效解決網(wǎng)絡(luò)的“僵化”問題[1-4]。在網(wǎng)絡(luò)虛擬化環(huán)境下，傳統(tǒng)的網(wǎng)絡(luò)服務(wù)運(yùn)營商被分為兩個(gè)角色[5-6]，即底層網(wǎng)絡(luò)運(yùn)營商和服務(wù)運(yùn)營商。在網(wǎng)絡(luò)虛擬化中，主要實(shí)體是虛擬網(wǎng)絡(luò)。虛擬網(wǎng)絡(luò)由虛擬節(jié)點(diǎn)和虛擬鏈路兩部分組成，虛擬節(jié)點(diǎn)間通過虛擬鏈路相互連接，每個(gè)虛擬節(jié)點(diǎn)和虛擬鏈路擁有與物理節(jié)點(diǎn)和鏈路相同的屬性。因此，如何有效地分配物理資源給不同的虛擬網(wǎng)絡(luò)，即虛擬網(wǎng)絡(luò)映射問題,是網(wǎng)絡(luò)虛擬環(huán)境下必須解決的難題。該問題已被證明為NP-hard問題[7-9]。為了提高底層網(wǎng)絡(luò)運(yùn)營商的收益，很多研究主要集中于提高虛擬網(wǎng)絡(luò)映射的成功率和底層網(wǎng)絡(luò)資源的利用率等方面。

然而，底層網(wǎng)絡(luò)很容易出現(xiàn)故障。所以，在找到一個(gè)有效的虛擬網(wǎng)絡(luò)映射方法之后，保證虛擬網(wǎng)絡(luò)的可生存性也是非常重要的[10]。針對虛擬網(wǎng)絡(luò)的可靠映射問題，目前主要有兩種機(jī)制，分別是保護(hù)和恢復(fù)機(jī)制[11]。故障保護(hù)機(jī)制是一種預(yù)先準(zhǔn)備的方式，在故障發(fā)生之前就預(yù)先保留一定的備份資源。相反，恢復(fù)機(jī)制則是在故障發(fā)生之后，啟動(dòng)備份恢復(fù)機(jī)制。為了對可生存性虛擬網(wǎng)絡(luò)映射問題的研究提供一個(gè)全面的視野，文中從問題定義、存在挑戰(zhàn)、映射目標(biāo)等方面對可生存性虛擬網(wǎng)絡(luò)映射問題的不同研究算法進(jìn)行綜述。在按照算法不同特性進(jìn)行分類和討論的基礎(chǔ)上，對幾種典型的算法進(jìn)行比較分析，并據(jù)此指出未來的研究趨勢。

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

1.1 底層網(wǎng)絡(luò)

1.2 虛擬網(wǎng)絡(luò)請求

1.3 虛擬網(wǎng)絡(luò)映射

如圖1(a)所示，虛擬網(wǎng)絡(luò)請求的節(jié)點(diǎn)映射方案分別是{a→C,b→D,c→A}，鏈路方案是{(a,b)→(C,D),(a,c)→(C,A),(b,c)→(D,A)}。節(jié)點(diǎn)和鏈路的分配同時(shí)滿足虛擬網(wǎng)絡(luò)請求的約束條件。

1.4 可生存性的虛擬網(wǎng)絡(luò)映射

當(dāng)一個(gè)底層單節(jié)點(diǎn)失效時(shí)，其周圍相連的鏈路也隨即失效，這會(huì)導(dǎo)致映射到這些底層鏈路上的多條虛擬鏈路同時(shí)失效，從而使已經(jīng)映射的虛擬網(wǎng)絡(luò)不能繼續(xù)工作(如圖1所示)。圖1(a)是一個(gè)成功的虛擬網(wǎng)絡(luò)映射。節(jié)點(diǎn)和鏈路映射方法分別是：{a→C,b→D,c→A}和{ab→CD,ac→CA,bc→DA}。虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)和鏈路約束都滿足。圖1(b)表示的是當(dāng)?shù)讓庸?jié)點(diǎn)D發(fā)生故障時(shí)，一個(gè)可存活的虛擬網(wǎng)絡(luò)映射方法。虛擬節(jié)點(diǎn)遷移到底層節(jié)點(diǎn)E上。與b相連的虛擬鏈路ab和bc分別重新映射到(CG)和(CH,HE,EB)上。經(jīng)過節(jié)點(diǎn)遷移和鏈路重新映射，虛擬網(wǎng)絡(luò)重新恢復(fù)正常。

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

2 可生存的虛擬網(wǎng)絡(luò)映射算法

可生存性虛擬網(wǎng)絡(luò)映射算法(SVNE)的主要目的就是在底層網(wǎng)絡(luò)節(jié)點(diǎn)或是鏈路出現(xiàn)故障后，能夠保證運(yùn)行在底層網(wǎng)絡(luò)上的虛擬網(wǎng)絡(luò)的可生存性。圖2是對現(xiàn)有的SVNE研究算法的分類樹。文獻(xiàn)[12]主要解決底層網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)的故障；文獻(xiàn)[13]則集中在單條鏈路故障問題。文獻(xiàn)[14-15]則分別從經(jīng)濟(jì)效益和地點(diǎn)約束進(jìn)行研究。文獻(xiàn)[16]研究了在SVNE中的資源分配效率問題。目前解決可生存性的虛擬網(wǎng)絡(luò)映射問題主要是提供備份資源。文獻(xiàn)[17]提出共享備份方案，允許多條虛擬鏈路共享分配的備份資源。本節(jié)將基于圖2的分類，闡述當(dāng)前為解決SVNE問題所提出的算法。

圖2 可生存的虛擬網(wǎng)絡(luò)映射算法分類

2.1 基于提供備份資源的SVNE

目前主要解決SVNE的方法是分配備份資源。文獻(xiàn)[17]提出強(qiáng)生存性和弱生存性。弱生存性只能保證虛擬節(jié)點(diǎn)在故障出現(xiàn)的時(shí)候保持連接，而強(qiáng)生存性則可以保證原始的虛擬網(wǎng)絡(luò)拓?fù)湓诎l(fā)生故障時(shí)保持連通。

文獻(xiàn)[17]為了從底層鏈路故障問題中快速恢復(fù)，使用了兩種類型的恢復(fù)方法，即鏈路(局部)恢復(fù)和路徑(端到端)恢復(fù)。該文提出一種混合策略啟發(fā)式算法(hybrid policy)解決SVNE。該算法分為三個(gè)分離的階段。第一階段是在虛擬網(wǎng)絡(luò)請求到來前，基礎(chǔ)設(shè)施供應(yīng)商使用路徑選擇算法預(yù)先為每一條底層鏈路計(jì)算一組可能的備份繞道。第二階段是當(dāng)虛擬網(wǎng)絡(luò)請求到達(dá)時(shí)，使用現(xiàn)存的啟發(fā)式算法執(zhí)行節(jié)點(diǎn)映射和鏈路映射。最后一個(gè)階段是當(dāng)?shù)讓渔溌烦霈F(xiàn)故障時(shí)，啟動(dòng)備份繞道優(yōu)化方法，在第一階段選擇的候選備份繞道路徑中為受到影響的鏈路重新路由。該算法降低了計(jì)算復(fù)雜性，在接受率、收益、帶寬效率、執(zhí)行時(shí)間等方面都比一般算法優(yōu)異。

文獻(xiàn)[18]針對多個(gè)節(jié)點(diǎn)故障提出了基于拓?fù)湟庾R的SVNE算法。該算法分為三個(gè)階段。第一階段是虛擬網(wǎng)絡(luò)請求到來前，預(yù)先分配了專用的備份定額，為每個(gè)底層節(jié)點(diǎn)創(chuàng)建了一個(gè)候選集。第二階段是虛擬網(wǎng)絡(luò)請求到來時(shí)，使用基于恢復(fù)性的虛擬網(wǎng)絡(luò)映射來分配虛擬網(wǎng)絡(luò)主要資源，虛擬網(wǎng)絡(luò)中的重要虛擬節(jié)點(diǎn)要被映射到可恢復(fù)性更好的底層節(jié)點(diǎn)上。第三階段是當(dāng)?shù)讓庸?jié)點(diǎn)發(fā)生故障時(shí)，啟動(dòng)利益驅(qū)動(dòng)的再映射算法，恢復(fù)盡可能多的受影響的虛擬網(wǎng)絡(luò)。

文獻(xiàn)[19]提出一種基于底層資源的負(fù)載平衡的分配資源的方法和重新配置備份資源的策略。為了確保從底層鏈路故障中的成功恢復(fù)，對于任意一條虛擬鏈路，一條帶寬等于主要鏈路的備份鏈路也被映射到底層鏈路中，和主要路徑不重疊。不同的備份路徑可以在同一條底層鏈路上共享相同的備份帶寬資源。在故障發(fā)生前，備份路徑上是沒有數(shù)據(jù)傳輸?shù)?，所以可以嘗試用備份流去接受第一次未被接受的VN。該算法的本質(zhì)是重新配置備份資源從而提高接受率。通過這種方式，可以根據(jù)自己的需求重新配置，刪除和添加備份資源。相比于主要資源的遷移，備份資源的重新配置更加簡單且風(fēng)險(xiǎn)低，同時(shí)也提高了資源的利用率。

2.2 基于無備份資源的SVNE

為了保證虛擬網(wǎng)絡(luò)的可生存性，之前的很多研究工作都是通過給虛擬網(wǎng)絡(luò)分配備份資源。這種方式雖然保護(hù)了虛擬網(wǎng)絡(luò)，但是會(huì)增加基礎(chǔ)設(shè)施提供商的成本。以降低基礎(chǔ)設(shè)施提供商的成本為目標(biāo)，許多研究提出在不預(yù)備備份資源的前提下解決可生存的虛擬網(wǎng)絡(luò)問題。

文獻(xiàn)[20]提出一種兩步策略。第一步是預(yù)防策略，第二步是恢復(fù)策略。在第一步中，通過將每一條虛擬鏈路映射到多條路徑上，減輕由底層故障產(chǎn)生的損害，防止虛擬鏈路失去全部的容量。這一步需要解決VNE問題，通過使用模擬退火法，可以找到全局最優(yōu)解。該算法通過迭代產(chǎn)生可能的映射，直到達(dá)到最大的迭代次數(shù)K。在每次迭代中，通過將它和幾個(gè)相似的方法進(jìn)行比較，從而改善當(dāng)前的方法。在第二步中，提出容量恢復(fù)策略。該策略代替分配備份資源，而是將受到損害的虛擬網(wǎng)絡(luò)鏈路重新分配到未受到影響的路徑上。該路徑必須是在第一步中被選來用于分配虛擬鏈路或是在運(yùn)行過程中未受到影響的路徑。該算法與提供備份資源相比，降低了基礎(chǔ)設(shè)施提供商的成本，同時(shí)還提高了虛擬網(wǎng)絡(luò)的接受率。

文獻(xiàn)[21]提出一種基于節(jié)點(diǎn)遷移和鏈路再映射的啟發(fā)式可生存虛擬網(wǎng)絡(luò)映射算法(SVNE-NOLR)。該算法不會(huì)預(yù)先為虛擬網(wǎng)絡(luò)分配備份資源，而是采用具有全局尋優(yōu)能力的人工蜂群算法求取近似最優(yōu)解[22]。如果底層節(jié)點(diǎn)發(fā)生故障，則使用貪婪算法將受到影響的節(jié)點(diǎn)遷移到正常節(jié)點(diǎn)上，然后使用Dijkstra最短路徑算法重新映射受到故障影響的虛擬鏈路。該算法沒有預(yù)留備份資源，不會(huì)產(chǎn)生資源的冗余，并且提高了虛擬網(wǎng)絡(luò)請求的接受率和虛擬網(wǎng)絡(luò)的恢復(fù)率，同時(shí)改善了底層網(wǎng)絡(luò)的負(fù)載強(qiáng)度。

2.3 典型可生存虛擬映射算法的比較總結(jié)

綜上所述，SVNE算法目前主要是從兩個(gè)方向進(jìn)行研究，一個(gè)方向是提供備份資源，在故障發(fā)生時(shí)立即調(diào)度該備份資源，從而恢復(fù)受到影響的虛擬網(wǎng)絡(luò)。提供備份資源也有兩種方式：第一種是主動(dòng)式的。在故障發(fā)生前，準(zhǔn)備好足夠的備份資源；第二種是反應(yīng)式的。當(dāng)故障發(fā)生時(shí)，根據(jù)其需要提供備份資源。另一個(gè)方向是不提供備份資源，而是通過節(jié)點(diǎn)遷移和鏈路再映射或是路徑映射等方式恢復(fù)受到影響的虛擬網(wǎng)絡(luò)。表1為不同分類下典型算法的比較總結(jié)。

表1 典型算法比較總結(jié)

3 總結(jié)與展望

主要討論了虛擬網(wǎng)絡(luò)映射的可生存性問題，即如何使虛擬網(wǎng)絡(luò)從底層節(jié)點(diǎn)或鏈路故障中快速恢復(fù)，并且對現(xiàn)有的一些解決算法進(jìn)行總結(jié)分類。目前，一大部分研究主要是基于提供備份資源來保證虛擬網(wǎng)絡(luò)的可生存性。當(dāng)故障發(fā)生時(shí)，啟動(dòng)備份恢復(fù)機(jī)制，為受到影響的虛擬節(jié)點(diǎn)或是鏈路提供備份資源，保證虛擬網(wǎng)絡(luò)的連通性。還有一些研究是基于無備份資源的前提下保證虛擬網(wǎng)絡(luò)的可生存性。但是在現(xiàn)有的研究中，依然存在一定的局限性。

(1)大部分研究只考慮單個(gè)底層節(jié)點(diǎn)故障或是單條鏈路故障的情況。目前提出的一些算法能夠很好地解決底層網(wǎng)絡(luò)單點(diǎn)故障的問題，完全恢復(fù)受到影響的虛擬網(wǎng)絡(luò)，但是如果發(fā)生了底層網(wǎng)絡(luò)多點(diǎn)故障，則只能恢復(fù)一部分受到影響的虛擬網(wǎng)絡(luò)，算法的性能大大下降。

(2)資源利用率不高。提供備份資源一般有兩種方式，一種是在映射前預(yù)備足夠的備份資源，一種是在發(fā)生故障時(shí)提供相應(yīng)需求的備份資源。第一種方法易造成資源閑置，產(chǎn)生浪費(fèi)。第二種易造成備份資源不足，影響虛擬網(wǎng)絡(luò)的恢復(fù)。這兩種方法都使得資源利用效率不高。

未來的研究方向可以關(guān)注兩個(gè)方面：

(1)多個(gè)節(jié)點(diǎn)故障和多條鏈路故障問題。大部分研究的前提還是針對底層網(wǎng)絡(luò)中單點(diǎn)故障提出的。現(xiàn)有方案雖然可以保證在底層單條鏈路故障的情況下完全恢復(fù)受到影響的虛擬網(wǎng)絡(luò)，但是當(dāng)出現(xiàn)多條鏈路故障時(shí)，恢復(fù)率會(huì)下降，不能保證提供完全的可生存性。

(2)無線虛擬網(wǎng)絡(luò)映射[23-24]的可生存性問題。無線網(wǎng)絡(luò)和有線網(wǎng)絡(luò)的區(qū)別主要在于無線鏈路的廣播特性，因此無線鏈路之間存在干擾。無線網(wǎng)絡(luò)中的節(jié)點(diǎn)還存在移動(dòng)性，影響已成功映射的虛擬網(wǎng)絡(luò)的服務(wù)質(zhì)量。所以，當(dāng)無線底層網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，如何保證虛擬網(wǎng)絡(luò)的可生存性是未來研究的方向之一。

4 結(jié)束語

虛擬網(wǎng)絡(luò)映射的可生存性問題作為網(wǎng)絡(luò)虛擬化環(huán)境下的重要問題已經(jīng)受到研究者的廣泛關(guān)注，找到一種可靠的算法能夠在底層網(wǎng)絡(luò)發(fā)生故障時(shí)保護(hù)受到影響的虛擬網(wǎng)絡(luò)存在許多挑戰(zhàn)。例如針對底層節(jié)點(diǎn)故障提出的預(yù)留備份資源方案和節(jié)點(diǎn)遷移方案，這些方案的目的都是為了保證底層網(wǎng)絡(luò)發(fā)生故障時(shí)虛擬網(wǎng)絡(luò)能夠快速恢復(fù)。但從整體上講，目前該領(lǐng)域的發(fā)展還未成熟，從理論到具體應(yīng)用還有很大的差距。

文中對已有的SVNE算法進(jìn)行研究，提出一種全新的分類方法，詳細(xì)介紹了每一類算法的典型方案，并進(jìn)行對比總結(jié)，最后指出SVNE問題未來的研究方向。