應對災難風險的多虛擬機快速協同撤離機制研究

鮑寧海 李國平 冉 琴 岳渤涵

(重慶郵電大學通信與信息工程學院 重慶 400065)

1 引言

近年來，網絡虛擬化技術的不斷發展和應用打破了傳統互聯網的僵化結構，為各類新興業務的迅速推廣提供了極大的便利。通過對計算、存儲和帶寬資源的抽象、匯聚與分配，底層的物理網絡資源可以在不同的互聯網業務提供商之間靈活共享，從而使眾多基于虛擬網的應用得以廣泛部署[1]。

虛擬網(Virtual Network,VN)通常是一定數量的虛擬節點和虛擬鏈路的集合。其中，每個虛擬節點以虛擬機的形式映射于一個物理節點中，實現計算和存儲資源的匯聚，而每條虛擬鏈路映射于兩個虛擬節點間的物理通路上，提供虛擬機之間的連通[2]。由于虛擬網各組件間的密切關聯性，任何虛擬節點或虛擬鏈路的損毀都可能造成大量的業務中斷和數據丟失，因此，虛擬網的生存性將成為影響未來網絡運行和業務發展的重要問題。

本文針對大規模災難事件(如地震、海嘯等)對多個物理網絡節點及相關鏈路造成的嚴重威脅，重點研究同一虛擬網中多個風險虛擬機的快速協同撤離機制，以減少單個虛擬網的撤離完成時長和損毀風險。

虛擬網生存性策略可分為網絡組件抗毀和在線業務抗毀兩類。前者可以采用虛擬網備份映射或重構來實現[3,4]，后者主要通過虛擬機在線遷移來完成[5]。而虛擬機的在線遷移技術又主要分為預復制遷移和后復制遷移兩類，可廣泛應用于在線系統維護、負載均衡、資源優化、能耗管理等領域[6]。

預復制遷移是先將原虛擬機的磁盤數據和主要內存頁復制到目的虛擬機，再以迭代方式將原虛擬機產生的內存臟頁(發生變化的內存信息)傳遞到目的虛擬機直到剩余臟頁量或迭代次數滿足要求，最后通過宕機切換將原虛擬機CPU狀態和剩余臟頁復制到目的虛擬機并啟動目的虛擬機。后復制遷移則是首先通過宕機切換將原虛擬機CPU狀態和少量必要內存頁復制到目的虛擬機并啟動目的虛擬機，然后再將剩余的內存頁和磁盤數據主動復制并推送至目的虛擬機。

在虛擬機遷移技術的研究中，宕機時長和總遷移時長通常被用作衡量虛擬機在線遷移性能和效率的重要參考指標[7]。為減小虛擬機的預復制遷移時長，文獻[8]通過預測迭代周期內的臟頁數量，對遷移帶寬進行動態預留和調整。文獻[9]根據內存臟碼率對遷移帶寬和預復制迭代次數進行優化，提高網絡帶寬利用率，減小總遷移時長。文獻[10]通過虛擬機遷移次序和遷移帶寬的調度與優化，最小化預復制遷移時長。文獻[11]采用速率感知的帶寬共享傳輸滿足預復制遷移的宕機時長和總遷移時長約束。文獻[12]提出一種增強型距離自適應預復制遷移帶寬分配算法，以降低遷移阻塞率。

為有效降低在線遷移過程中的傳輸負載，文獻[13]針對后復制遷移，利用遠程失效頁面過濾技術提高遷移內容的有效性。文獻[14]提出一種分散集中式后復制遷移策略，利用多個中間節點作為緩存代理，解決目標主機接收速率過慢的問題。文獻[15]提出一種反向增量檢查機制，保障后復制遷移中斷后虛擬機的快速恢復，避免宕機時長和總遷移時長的惡化。

針對關聯性多虛擬機遷移問題，文獻[16]通過并行預復制遷移策略優化遷移帶寬分配，獲得低于串行預復制遷移的平均宕機時長、總遷移時長，以及遷移阻塞率。文獻[17]根據關聯虛擬機業務流量的相關性確定遷移次序，減小預復制遷移的平均宕機時長。文獻[18]通過多虛擬機遷移帶寬和預復制迭代次數的聯合優化，對虛擬機宕機時長和總遷移時長進行平衡和折中。

顯然，在現有研究工作中，預復制遷移技術受到了更多的關注[8–12,16–18]。在預復制遷移過程中，由于原虛擬機始終保有CPU狀態，可在遷移中斷時迅速恢復，能為在線遷移提供更高的可靠性。然而，原虛擬機產生的大量臟頁將不可避免地增加遷移負載，因此，基于預復制遷移的研究工作大多集中在臟頁迭代周期規劃和網絡帶寬資源優化上，以便在宕機時長與總遷移時長上獲得較好的折中[8–12]。而后復制遷移技術由于避免了大量臟頁的產生和傳遞，遷移負載顯著減小，從而獲得更短的總遷移時長，因此，基于后復制遷移的研究工作主要集中在對內存頁的壓縮、標識，以及網絡資源的有效利用上，以進一步提高在線遷移的效率或可靠性[13–15]。

從以上分析可以看出，相對于預復制遷移，后復制遷移更適合虛擬機的快速緊急遷移。然而，在大規模災難風險下，虛擬網快速撤離的關鍵不是單個虛擬機的遷移完成時間，而是該虛擬網中所有風險虛擬機最終完成遷移的時間?，F有關于多虛擬機遷移的研究大多采用預復制遷移技術，主要目標還是通過迭代調度和資源優化解決宕機時長和總遷移時長的平衡問題[16–18]，并未就大規模災難風險場景下的虛擬網生存性問題進行針對性研究。因此，本文基于后復制遷移技術，提出一種應對災難風險的多虛擬機快速協同撤離機制。

2 問題描述及網絡模型

2.1 問題描述

大規模災難事件可能對通信網基礎設施造成嚴重的破壞，并對映射于災難風險區內的大量虛擬機及其相關業務構成極大的威脅。如何快速撤離這些風險虛擬機已成為虛擬網抗毀的一個重要問題。特別是，當虛擬網的多個甚至全部虛擬機均處于災難風險區時，虛擬網的生存性將取決于所有風險虛擬機是否能夠實現快速協同撤離，而目前對該問題的研究尚待深入。

針對以上情況，本文假設一次大規模災難事件導致多個具有地理關聯性的物理網絡節點(及其鄰接鏈路)陷入災難風險區。當任何一個虛擬網有一個或多個虛擬機映射于風險物理節點上時，需要對該虛擬網進行快速撤離。虛擬網撤離問題主要包括虛擬網重構和虛擬機在線遷移兩個子問題，二者均屬于NP-hard問題[2,6]。由于大量虛擬網業務的運行依賴于各虛擬機的協同工作，虛擬網及其業務的生存性將取決于最后一個風險虛擬機的遷移結束時間。因此，本文以減少單個虛擬網的撤離完成時長，降低損毀風險為目標，重點研究同一虛擬網中多個風險虛擬機的快速協同撤離機制。

2.2 網絡模型

3 方案描述

為應對大規模災難風險對虛擬網及其業務造成的嚴重威脅，本文提出一種多虛擬機快速協同撤離(Multi-virtual-machine Rapid Cooperative Evacuation,MRCE)機制。該機制將虛擬網的撤離過程分為兩個階段，即首先在風險區外對虛擬網進行重構，實現虛擬網的組件抗毀，再通過多虛擬機協同遷移，實現虛擬網的業務抗毀。

3.1 虛擬網重構

在廣域網中，節點資源相對于帶寬資源更易于升級與擴容，因此，假設每個物理節點中的計算資源和存儲資源都是足夠的。為在重構虛擬鏈路長度與虛擬機遷移通路長度上取得平衡，實現網絡帶寬資源的優化利用，首先建立物理節點代價函數，如式(5)所示。其中，表 示虛擬節點nv到物理節點ns的 最短距離(跳數)，表示虛擬網Gv中所有虛擬節點到中物理節點ns的最短距離和。

通過式(5)，在風險區域外尋找代價最小的物理節點作為錨點，并將距離錨點H(≤2)跳內的區域劃為的節點重構區域。然后，在重構區域內根據最大資源優先原則均衡分配節點資源，即優先將具有最大節點資源需求的虛擬節點映射到具有最大可用節點資源的物理節點上。最后，利用最短路算法在風險區域外重構中的虛擬鏈路。

3.2 多虛擬機協同遷移

在網絡帶寬資源有限的情況下，虛擬機的遷移數據量是影響遷移完成時間的重要因素，因此，本文采用后復制遷移技術，避免大量臟頁的產生和迭代傳輸，并假設遷移數據均為總量確定的必要數據，不涉及數據清理、過濾及壓縮等問題。

本文中多虛擬機協同遷移的主要目標是減小單個虛擬網的撤離完成時長。在為風險虛擬機建立遷移通路時，過小的遷移帶寬將導致該虛擬機的遷移完成時長超長，從而影響整個虛擬網的撤離完成時長。為解決這一問題，首先引入虛擬機基礎遷移帶寬約束條件，如式(6)所示。其中，Tmax表示虛擬機的最大遷移完成時長門限，τmax表示虛擬機的最大宕機時長，Di表 示風險虛擬機mi的待遷移數據量，Bi表 示mi的遷移帶寬。

由于虛擬網的撤離完成時長取決于最后一個風險虛擬機的遷移結束時間，當式(6)中的Bi取最小值時，該虛擬網中各風險虛擬機的遷移完成時長相同，且均為Tmax。然而，在動態變化的網絡資源環境下，如果固定采用m in(Bi)作為遷移帶寬，嚴格執行多虛擬機的同步遷移，可能會犧牲網絡帶寬的資源利用率。因此，通過選擇合適的基礎遷移帶寬，并根據網絡資源狀態對其進行調整和升級，提高風險虛擬網的撤離效率。為解決可能出現的遷移帶寬升級受限的問題，采用多通路策略提高帶寬升級的靈活性。同時，為使同一虛擬網中各風險虛擬機的遷移完成時長盡可能一致，還需對各虛擬機的遷移帶寬進行協同調整。

3.3 啟發式算法

根據以上方案描述，本文設計了相應的MRCE啟發式算法，用于實現大規模災難風險下虛擬網的快速撤離。其中，子算法-1完成虛擬網重構，子算法-2完成多虛擬機協同遷移的初始配置。

(1)MRCE算法

步驟1 將所有風險虛擬網放入集合R，并按其所含風險虛擬機數量升序排列，初始化當前時間tc=0，每個虛擬機已遷移數據量=0，遷移完成時間=∞；

步驟2 如果集合R/=?，調用子算法-1對R中的每個風險虛擬網進行重構，調用子算法-2為重構虛擬網中的每個風險虛擬機分配遷移通路和帶寬，將遷移帶寬分配成功的虛擬網移入集合E中，跳轉到步驟3，否則，跳轉到步驟8；

步驟3 如果集合E/=?，對E中虛擬網的各風險虛擬機 mi執行后復制遷移，跳轉到步驟4，否則，跳轉到步驟2；

步驟5 如果該mi為所屬虛擬網內第1個完成遷移的虛擬機，根據式(11)計算該虛擬網內其他mi的遷移完成時差并放入集合U，跳轉到步驟7，否則，跳轉到步驟6；

步驟6 如果該 mi為所屬虛擬網內最后一個完成遷移的虛擬機，將該虛擬網從E中刪除，跳轉到步驟7，否則，跳轉到步驟7；

步驟7 更新U中所有的并刪除=0的記錄，如果U/=?，將降序排列，依次將相應的虛擬機遷移帶寬升級至上限，跳轉到步驟2，否則，跳轉到步驟2；

步驟8 算法結束。

(2)子算法-1

步驟2 依次為中的虛擬節點按最大節點資源需求優先原則，在節點重構區域內選取具有最大可用資源的物理節點進行重映射；

步驟5 風險虛擬網Gv重構失敗，釋放已重構的虛擬節點及虛擬鏈路資源，跳轉到步驟6；

步驟6 算法結束。

(3)子算法-2

步驟1 初始化k=1，分別為中的每個風險虛擬機 mi計算一條滿足式(6)約束的最短遷移通路，如果成功，跳轉到步驟2，否則，跳轉到步驟6；

步驟3 如果集合M/=?，令k=k+1，跳轉到步驟4，否則，跳轉到步驟6；

步驟4 依次為M中每個mi計算一條最短通路作為增量遷移通路，根據式(9)計算增量帶寬如果，將該mi從M中刪除，跳轉到步驟5，否則，令，跳轉到步驟5；

步驟5 如果k ＜K，跳轉到步驟3，否則，跳轉到步驟6；

步驟6 算法結束。

根據以上算法步驟分析，MRCE的時間復雜度為O(|Nv|2·|Ns|·log2|Ns|+|Nv|·K·|Ns|·log2|Ns|)，其中，Ns與Nv分別表示物理網Gs和虛擬網Gv的最大節點數，K表示單個虛擬機的最大遷移通路數，|Ns|·log2|Ns|為最短路算法的時間復雜度。

4 仿真測試與分析

本文對提出的多虛擬機快速協同撤離算法(MRCE)進行仿真測試，并采用常規后復制遷移算法(Regular Post-Copy Migration,RPCM)和基于自適應帶寬升級的后復制遷移算法(Adaptive bandwidth Upgraded Post-copy Migration,AUPM)進行風險虛擬網撤離的性能對比。3種算法均采用相同的虛擬網重構策略，其中，RPCM為每個虛擬機尋找最短遷移通路并分配最大可用遷移帶寬，而AUPM在RPCM的基礎上，根據網絡帶寬資源狀態，對遷移帶寬進行盡力而為的動態升級。

仿真采用的物理網絡拓撲包含24個節點和43條鏈路，如圖1所示。假設各物理節點均擁有充足的計算和存儲資源，各物理鏈路的帶寬資源均為240 Gbps。圖中陰影部分代表3個獨立的災難風險模型，分別包含(3,4,5)，(9,12,13)和(16,17,22)3組物理節點及其相鄰物理鏈路。

圖1 物理網絡拓撲

隨機產生90套初始業務模型，每套包含500個虛擬網絡，且隨機分布(映射)于上述物理網絡中。其中，每個虛擬網絡隨機產生3～5個虛擬節點，任意兩個虛擬節點間以0.5的概率建立虛擬鏈路，虛擬鏈路帶寬在0.5～3 Gbps間隨機產生。采用后復制遷移技術對風險虛擬機進行遷移，每個虛擬機的待遷移數據量在5～10 GB間隨機產生，宕機時長在0.5～1.5 s間隨機產生[9]。

在以上仿真環境中，分別對MRCE,RPCM和AUPM進行仿真測試，性能指標主要包括風險虛擬網的平均撤離完成時長、撤離完成時長標準差，以及撤離完成率。最終仿真結果對3個災難風險模型和90套隨機業務模型取平均?？紤]到我國的地震監測系統已具備一定程度的預警能力(十幾秒至幾十秒的預警時間)，但網絡組件的損毀時間仍舊難以確定。因此，以10 s為基數設立6個考察周期，分別在算法執行后的10 s,20 s,30 s,40 s,50 s,60 s時間點對以上性能指標進行考察記錄。

在MRCE中，虛擬機最大遷移完成時長門限Tmax的選取對網絡帶寬資源利用率有較大的影響。如果Tmax取值過大，則虛擬機的遷移效率降低，可能造成虛擬網的平均撤離完成時長過大；如果Tmax取值過小，則虛擬機的基礎遷移帶寬需求較大，可能造成過高的遷移帶寬阻塞率。因此，首先考察MRCE在不同Tmax設置下的平均撤離完成時長和遷移帶寬阻塞率，并用T10,T20,T30,T40,T50,T60分別代表Tmax取值為10 s,20 s,30 s,40 s,50 s,60 s時MRCE的相應指標。

如圖2和圖3所示，在10～60 s考察周期內，MRCE的平均撤離完成時長隨著Tmax取值的增加不斷變大，而其遷移帶寬阻塞率卻隨著Tmax的增加而降低。顯然，由式(6)可知，增大Tmax的取值等同于放松對基礎遷移帶寬的約束，使得虛擬機更容易找到可用的遷移通路。然而，當網絡中的帶寬資源較為緊張，且碎片化較為嚴重時，過小的基礎遷移帶寬會使以 min(Ti)為基準的增量帶寬策略變得低效，從而導致虛擬網的撤離完成時長變大。圖3數據顯示，在此仿真環境下，當Tmax≥40 s時，遷移帶寬阻塞率較低，且數值變化明顯趨緩，因此在后續的仿真測試中，采用40 s作為MRCE的虛擬機最大遷移完成時長門限。

圖2 T max對平均撤離完成時長的影響

圖3 T max對遷移帶寬阻塞率的影響

風險虛擬網平均撤離完成時長如圖4所示。在10 s的考察時間點，MRCE和AUPM的平均撤離完成時長均高于RPCM，其原因包括兩個方面：其一是在撤離開始的初期，包含風險虛擬機數量最少的虛擬網將被優先撤離，特別是僅包含單個風險虛擬機的虛擬網，能以最小代價盡快脫離風險區。而對此類風險虛擬網來說，MRCE的協同撤離策略和AUPM的自適應升級策略的優勢不夠突出。其二是在每一個考察時間點，虛擬網的平均撤離完成時長只統計當前已完成撤離的虛擬網，而RPCM在10 s周期內完成撤離的虛擬網數量遠小于MRCE和AUPM，且完成撤離的主要是僅包含單一風險虛擬機的虛擬網。從圖4中可以發現，在20 s及以后的考察時間點，MRCE的平均撤離完成時長有稍許增加但非常平穩，AUPM的平均撤離完成時長逐漸增長但較緩慢，而RPCM的平均撤離完成時長增長較為迅速。顯然，相對于RPCM,AUPM的自適應升級策略能夠更好地提高網絡帶寬資源利用率，縮短風險虛擬機的遷移完成時長，從而在一定程度上縮短風險虛擬網的撤離完成時長。而MRCE的協同撤離策略通過壓縮同一虛擬網中風險虛擬機間的遷移完成時差，能夠進一步減小各風險虛擬網的撤離完成時長。

圖4 不同考察時間下的平均撤離完成時長

風險虛擬網的撤離完成時長標準差如圖5所示。在10 s考察時間點，RPCM的撤離完成時長標準差與MRCE的接近且稍低于AUPM。其原因除了前面提到的RPCM在該考察周期內完成撤離的虛擬網數量少且主要包含單一風險虛擬機以外，另一個原因是在撤離初期，風險區外的網絡資源相對較充足，帶寬資源碎片化情況不嚴重，因此，RPCM在此期間完成虛擬網撤離所耗費的時長較短且差距不大。然而，隨著包含多風險虛擬機的虛擬網開始大量撤離，以及風險區外網絡帶寬資源的減少，RPCM的撤離完成時長標準差迅速上升。雖然AUPM可以通過自適應帶寬升級提高帶寬資源利用率，但對縮短同一虛擬網內不同風險虛擬機的遷移完成時差并無確定性的作用，即遷移帶寬升級的結果可能使時差減小，也可能使時差增大。隨著風險區外可用帶寬資源的逐漸短缺和碎片化，AUPM的自適應帶寬升級效率逐漸降低，這使得不同風險虛擬網撤離完成時長的差距逐漸變大。相對于RPCM和AUPM，MRCE通過基礎遷移帶寬的選取和增量遷移帶寬的配置，以及基于虛擬機遷移完成時差的遷移帶寬動態升級，能夠在不同的網絡帶寬資源狀態下獲得較為穩定的撤離完成時長標準差。

圖5 不同考察時間下的撤離完成時長標準差

風險虛擬網的撤離完成率可以直觀反映災難風險下虛擬網的抗毀能力。如圖6所示，相對于AUPM和RPCM，MRCE在各個階段都能取得更好的撤離完成率。該結果表明，在災難損毀時間不確定的情況下，MRCE能夠更快更多地完成虛擬網的撤離。值得注意的是，隨著考察時間的不斷推移，3種算法的撤離完成率也在不斷增長，但增長率有逐漸變緩的趨勢。這是因為隨著風險區外的虛擬網(已重構且完成撤離)不斷增多，該區域的帶寬資源消耗也在不斷增加，可用于虛擬機遷移的帶寬資源大量減少，從而限制了并行撤離的虛擬網數量。因此，在大量風險虛擬網的撤離過程中，撤離完成率越高，其增長率下降越明顯。

5 結束語

為應對大規模災難事件對虛擬網生存性造成的嚴重威脅，本文研究并提出一種多虛擬機快速協同撤離機制。該機制采用風險虛擬網的重構實現網絡組件的抗毀，采用風險虛擬機的后復制遷移實現在線業務的抗毀。特別針對同一虛擬網的多個或全部虛擬機均受到災難威脅的情況，通過虛擬機最大遷移完成時限設定，約束虛擬網撤離完成時長，通過虛擬機遷移完成時長預估和基礎遷移帶寬分配，協調各虛擬機的遷移速度，通過虛擬機遷移完成時差評估和遷移帶寬動態升級，進一步壓縮虛擬網撤離完成時長。仿真測試證明，與常規后復制遷移算法和基于自適應帶寬升級的后復制遷移算法相比，多虛擬機快速協同撤離算法能夠在不同考察周期內獲得較好的虛擬網撤離完成率和平均撤離完成時長。本文提出的虛擬網抗毀機制主要針對自然災難風險，在應對未知或不可測風險(如軍事打擊、意外事件)，以及更為嚴苛的時間約束等問題上，還有較大的研究空間。