可生存性虛擬網絡映射算法的研究

黃麗萍，楊龍祥

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

0 引 言

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

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

1 虛擬網絡映射問題描述

1.1 底層網絡

1.2 虛擬網絡請求

1.3 虛擬網絡映射

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

1.4 可生存性的虛擬網絡映射

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

圖1 虛擬網絡映射實例

2 可生存的虛擬網絡映射算法

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

圖2 可生存的虛擬網絡映射算法分類

2.1 基于提供備份資源的SVNE

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

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

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

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

2.2 基于無備份資源的SVNE

為了保證虛擬網絡的可生存性，之前的很多研究工作都是通過給虛擬網絡分配備份資源。這種方式雖然保護了虛擬網絡，但是會增加基礎設施提供商的成本。以降低基礎設施提供商的成本為目標，許多研究提出在不預備備份資源的前提下解決可生存的虛擬網絡問題。

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

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

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

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

表1 典型算法比較總結

3 總結與展望

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

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

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

未來的研究方向可以關注兩個方面：

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

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

4 結束語

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

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