動態(tài)路徑分裂的虛擬網(wǎng)絡重構算法*

謝 楓，孟相如，孟慶微，于興超

（1.空軍工程大學信息與導航學院，西安 710077；2.山東省濟南市章丘區(qū)第七中學，濟南 250206）

0 引言

網(wǎng)絡虛擬化是解決網(wǎng)絡“僵化”的有效方法［1-3］，該方法支持多個虛擬網(wǎng)絡（VN，Virtual Network）在同一個底層物理網(wǎng)絡上運行。虛擬網(wǎng)絡映射［4］是網(wǎng)絡虛擬化研究中的關鍵，主要是根據(jù)虛擬網(wǎng)絡的需求為其合理地分配資源。然而，受到人為或自然因素的影響，底層物理網(wǎng)絡經(jīng)常發(fā)生節(jié)點或鏈路故障，導致承載的虛擬網(wǎng)絡故障［5］。若故障虛擬網(wǎng)絡沒有及時恢復，不僅影響正常的網(wǎng)絡服務，還會產(chǎn)生相應的賠償金，因此，降低底層物理網(wǎng)絡故障帶來的影響，對于保證虛擬網(wǎng)絡的成功運行具有重要意義。

針對底層物理網(wǎng)絡故障引起的虛擬網(wǎng)絡故障，目前主要的解決策略為資源備份與即時遷移策略。文獻［6］根據(jù)不同服務的保護質(zhì)量，為每條虛擬鏈路預留一條或多條不相交的物理路徑作為保護路徑。文獻［7-8］在為虛擬鏈路進行資源備份時，引入備份資源共享的方法，提高物理資源的使用率。文獻［9］將整個底層物理網(wǎng)絡資源的一部分直接劃歸為備份資源，發(fā)生故障時，將故障虛擬網(wǎng)絡遷移到備份資源上，保證虛擬網(wǎng)絡的正常運行。但資源備份策略必然降低物理網(wǎng)絡資源的利用率，因此，文獻［10-11］采用即時遷移策略，當故障發(fā)生后，將故障虛擬網(wǎng)絡遷移到剩余的物理網(wǎng)絡資源上，充分利用物理網(wǎng)絡資源，但是在選擇待遷移的目標節(jié)點時，并沒有考慮其位置與所在區(qū)域的負載情況，同時，目標物理路徑的選取都局限于單物理路徑，從而影響了算法的性能。

針對已有算法存在的問題，本文提出一種動態(tài)路徑分裂的虛擬網(wǎng)絡重構算法（DPS-VNRA）。該算法首先根據(jù)故障虛擬網(wǎng)絡可能產(chǎn)生的賠償金、剩余的生存時間，以及故障虛擬鏈路與節(jié)點個數(shù)確定重構順序；同時，考慮到在后期為故障虛擬鏈路尋找一條滿足其資源需求的獨立物理路徑較為困難，本文借鑒文獻［12-14］中路徑分裂的思想，引入一種動態(tài)路徑分裂的方法，該方法可以對每條故障虛擬鏈路進行合理的分裂，分別遷移到獨立的物理路徑上，以提高故障虛擬鏈路的恢復率；對于故障虛擬節(jié)點，在為其選取待遷移的目標物理節(jié)點時，結合就近原則與底層物理網(wǎng)絡的負載情況，在故障虛擬節(jié)點恢復的基礎上，進一步優(yōu)化映射的結果。仿真結果表明，該算法降低了底層物理網(wǎng)絡故障的影響，提高了虛擬網(wǎng)絡的請求接受率與成功運行率。

1 問題建模

1.1 物理網(wǎng)絡與虛擬網(wǎng)絡

1.2 故障描述與重構模型

1.2.1 物理節(jié)點故障與重構模型

圖1 故障虛擬網(wǎng)絡重構示意圖

1.2.2 物理鏈路故障與重構模型

1.3 評價指標

1.3.1 虛擬網(wǎng)絡的請求接受率

虛擬網(wǎng)絡的請求接受率為在時間T 內(nèi)，映射成功的虛擬網(wǎng)絡數(shù)目與虛擬網(wǎng)絡總數(shù)目之比

式中，VNmaps（T）為映射成功的虛擬網(wǎng)絡數(shù)目，VNmapt（T）為虛擬網(wǎng)絡的總數(shù)目，δ 為趨近于0 的正數(shù)。

1.3.2 虛擬網(wǎng)絡的成功運行率

虛擬網(wǎng)絡的成功運行率為在時間T 內(nèi)，成功運行的虛擬網(wǎng)絡數(shù)目與虛擬網(wǎng)絡總數(shù)目之比

1.3.3 虛擬網(wǎng)絡的收益開銷比

在t 時刻，每成功映射一個虛擬網(wǎng)絡所產(chǎn)生的收益定義為

在t 時刻，每接受一個虛擬網(wǎng)絡，底層物理網(wǎng)絡的開銷定義為

式中，參數(shù)β 用于調(diào)整節(jié)點開銷和鏈路開銷的權重，本文取值為1。h（ev）是虛擬鏈路映射到物理鏈路上經(jīng)過的跳數(shù)。

假設在ts時刻，虛擬網(wǎng)絡Gv發(fā)生故障，若Gv重構成功，則收益不變，開銷可能發(fā)生變化，若失敗，則定義為，同時釋放占用的物理網(wǎng)絡資源，產(chǎn)生賠償金，且賠償金存在的時間區(qū)間為為正常情況下Gv的結束時間。賠償金定義為

式中，μ 為賠償系數(shù)，本文取0.5。

虛擬網(wǎng)絡的收益開銷比定義為

2 算法設計

當?shù)讓游锢砭W(wǎng)絡在t 時刻發(fā)生故障之后，首先統(tǒng)計發(fā)生故障的虛擬網(wǎng)絡，根據(jù)排序算法確定重構順序。對每個故障虛擬網(wǎng)絡，先進行故障情況2 和3的恢復，再進行故障情況1 的恢復。若失敗，則釋放占用的物理網(wǎng)絡資源，產(chǎn)生賠償金。

2.1 故障虛擬網(wǎng)絡重構排序設計

本文從3 個方面來考慮虛擬網(wǎng)絡的重構順序：一是故障虛擬網(wǎng)絡可能產(chǎn)生的賠償金大?。欢琴r償金存在的時間長短；三是故障虛擬網(wǎng)絡的重構難度，采用虛擬網(wǎng)絡中故障節(jié)點與鏈路數(shù)目之和nf表示。綜上所述，定義虛擬網(wǎng)絡的重構排序函數(shù)（RSF，Sort Function of Reconfiguration）

2.3 酒糟有機肥不同用量對烤后煙葉化學成分的影響 從表3可以看出，各處理中部烤后煙葉主要化學成分指標除鉀外均無顯著差異，含有酒糟有機肥2 250 kg/hm2配施20%化肥的處理鉀含量顯著低于其他處理，其糖和淀粉含量均高于其他2個處理；3個處理的氯含量較低，均低于對照，其他化學成分含量各處理間以及各處理與對照間均無顯著差異。

2.2 故障虛擬鏈路遷移算法

1）對故障虛擬鏈路按照帶寬需求從高到底進行排列，依次選取進行遷移。

2）針對所選的故障虛擬鏈路，先將物理鏈路中不滿足其帶寬資源需求的物理鏈路刪除，再使用最短路徑算法尋找其兩端節(jié)點所對應的目標物理節(jié)點之間的物理路徑，若存在，進行遷移，否則進行路徑分裂遷移。

3）對于進行路徑分裂遷移的故障虛擬鏈路，使用最短路徑算法找出兩端物理節(jié)點之間所有的m條獨立的物理路徑l，按路徑中最小的可用帶寬bwmin（l）從大到小排列，再定義滿足路徑可分裂的條件為

表明如果序列中前k 條物理路徑的bwmin（li）之和大于等于bw（），則可以分裂成k 條虛擬鏈路，每條虛擬鏈路的帶寬需求分別為，將其按順序分別映射到前k 條物理路徑上。同時，k≤3 表明最多分裂成3 條虛擬鏈路進行遷移，避免因分裂過多而導致虛擬鏈路故障頻發(fā)。若無法滿足上述條件，則虛擬鏈路遷移失敗。

故障虛擬鏈路遷移算法如表1 所示。

2.3 故障虛擬節(jié)點遷移算法

2）因為節(jié)點的遷移會引發(fā)鄰接鏈路的遷移，所以在選取目標物理節(jié)點時必須兼顧鄰接鏈路的資源負載情況，定義物理節(jié)點的區(qū)域負載（RL，Regional Load）為：

進一步定義物理節(jié)點的適應值函數(shù)（NFF，Node Fitness Function）為：表示物理節(jié)點上承載的虛擬網(wǎng)絡個數(shù)，NM（）為與相鄰的虛擬節(jié)點對應的目標物理節(jié)點集合，

3）按2 中的排序對每個物理節(jié)點進行嘗試，直到鄰接虛擬鏈路遷移成功，否則虛擬節(jié)點遷移失敗。鄰接虛擬鏈路的遷移方法與2.2 節(jié)的方法一致

故障虛擬節(jié)點遷移算法如下頁表2 所示。

3 算法性能評估

本文主要通過仿真實驗，以文獻［15］中的映射算法為基礎，分別在故障發(fā)生次數(shù)較少和較多的情況下，對表3 中4 種算法的性能進行比較。比較的指標為虛擬網(wǎng)絡的請求接受率、成功運行率和收益開銷比。

表2 故障虛擬節(jié)點遷移算法

表3 算法介紹

3.1 仿真環(huán)境設置

本文在仿真平臺MATLAB 下進行實驗評估。用于仿真的底層物理網(wǎng)絡、虛擬網(wǎng)絡拓撲以及故障發(fā)生模型的參數(shù)設置如下：

底層物理網(wǎng)絡拓撲：節(jié)點個數(shù)為100，均勻分布在1 000×1 000 的底層網(wǎng)絡平面上，節(jié)點間相連的可能性為50%。節(jié)點的可用計算資源和鏈路可用帶寬服從［50，100］的均勻分布。

虛擬網(wǎng)絡拓撲：每個虛擬網(wǎng)絡的節(jié)點個數(shù)服從［2，10］的均勻分布，節(jié)點間相連的可能性為50 %，節(jié)點的計算資源需求與鏈路帶寬需求服從［15，30］的均勻分布。虛擬網(wǎng)絡到達時間服從參數(shù)為0.1 的Poisson 分布，平均100 時間單位內(nèi)有10 個請求到達。虛擬網(wǎng)絡的生存時間服從參數(shù)為300 個時間單位的指數(shù)分布。

故障發(fā)生模型：物理網(wǎng)絡在故障較少和較多的情況下，發(fā)生故障的時間分別服從參數(shù)為0.05 和0.15 的Poisson 分布，持續(xù)時間均服從參數(shù)為150 個時間單位的指數(shù)分布。其節(jié)點故障和鏈路故障發(fā)生的概率分別為0.2 與0.8。仿真時間為3 000 個時間單位，在兩種情況下分別進行10 次實驗，取平均值作為最終結果。

3.2 仿真結果分析

3.2.1 請求接受率

圖2 請求接受率

如圖2 所示，在底層物理網(wǎng)絡故障較多的情況下，4 種算法的請求接受率都低于故障較少的情況。其中，DPS-VNRA 與IP-DR 不采用資源備份策略，在映射階段就可以充分利用底層物理網(wǎng)絡資源，接受更多的虛擬網(wǎng)絡，故請求接受率更高。同時，DPS-VNRA 由于在故障恢復的同時進行底層物理網(wǎng)絡的負載均衡，所以，該算法的請求接受率優(yōu)于IP-DR。而DPS-VNRA-B 與IP-DR-B 都將一部分底層物理網(wǎng)絡資源劃歸為備份資源，在映射階段無法使用，所以請求接受率較低。

3.2.2 成功運行率

圖3 成功運行率

如圖3 所示，虛擬網(wǎng)的成功運行率隨故障的增多而下降，都低于相同情況下的請求接受率。DPS-VNRA 在故障虛擬網(wǎng)絡重構時采用了動態(tài)路徑分裂的方法，提高了故障虛擬鏈路的恢復率，同時考慮就近原則，將故障虛擬節(jié)點遷移到區(qū)域負載輕且承載虛擬網(wǎng)絡少的物理節(jié)點上，一方面增加鄰接虛擬鏈路遷移成功的概率，另一方面也減少了因某個物理節(jié)點故障而引發(fā)大量虛擬網(wǎng)絡故障的情況，提高了虛擬網(wǎng)絡成功運行的概率。IP-DR 只采用就近原則策略，容易加劇底層物理網(wǎng)絡負載與分布不均的情況，導致大量虛擬網(wǎng)絡發(fā)生故障，所以IP-DR 的成功運行率低于DPS-VNRA。隨著故障發(fā)生次數(shù)的增多，剩余物理網(wǎng)絡資源無法滿足故障虛擬網(wǎng)絡的重構需求，所以，DPS-VNRA 與IP-DR 的成功運行率與請求接受率之間的差距加大。而DPS-VNRA-B 與IP-DR-B 由于采用備份資源策略，有充足的物理網(wǎng)絡資源進行故障虛擬網(wǎng)絡的重構，所以在兩種故障情況下，二者的運行成功率都相近且與請求接受率無明顯差距，甚至優(yōu)于IP-DR，但受限于較低的請求接受率，一直低于DPS-VNRA。同時，當故障發(fā)生次數(shù)的增多，DPS-VNRA-B 與 IP-DR-B 的成功運行率與DPS-VNRA 之間的差距減小。

3.2.3 收益開銷比

如圖4 所示，在兩種故障情況下，DPS-VNRA-B 與IP-DR-B 的收益開銷比都是最優(yōu)的。而DPS-VNRA 由于采用了動態(tài)路徑分裂的方法，使分裂的虛擬鏈路映射到較長的物理路徑上，導致鏈路映射開銷增大，所以收益開銷比與DPS-VNRA-B與IP-DR-B 相比有所降低。IP-DR 因為存在較多故障虛擬網(wǎng)絡無法恢復，產(chǎn)生了大量的賠償金，所以收益開銷比較低。

圖4 收益開銷比

4 結論

本文著重研究了由底層物理網(wǎng)絡故障導致的故障虛擬網(wǎng)絡的恢復問題，提出了一種動態(tài)路徑分裂的虛擬網(wǎng)絡重構算法。該算法首先確定故障虛擬網(wǎng)絡的重構順序，其次采用動態(tài)路徑分裂方法以提高故障虛擬鏈路的恢復率，同時在確保故障虛擬節(jié)點恢復的情況下，結合負載均衡與就近原則，一方面優(yōu)化底層物理網(wǎng)絡的負載情況，減小了大量虛擬網(wǎng)絡出現(xiàn)故障的情況，也保證了較小的資源開銷。仿真結果表明，該算法與之前所提算法相比，提高了虛擬網(wǎng)絡的請求接受率與成功運行率，但由于采用了動態(tài)路徑分裂的方法，導致鏈路映射的開銷增大，收益開銷比有所下降，略低于備份算法。所以在下一步的研究中，將進一步考慮如何減小重構過程中的資源開銷，同時設計合理的備份算法與之結合，進一步提高算法的性能。