繆宇霆，吳春明，楊強(qiáng)，姜明

（1. 浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 浙江 杭州310027；2. 浙江大學(xué) 電氣工程學(xué)院, 浙江 杭州 310027；3. 杭州電子科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 浙江 杭州 310027）

1 引言

當(dāng)今的互聯(lián)網(wǎng)信息產(chǎn)業(yè)正處于高速發(fā)展?fàn)顟B(tài)。在傳統(tǒng)的網(wǎng)絡(luò)體系結(jié)構(gòu)下，依靠拓展鏈路傳輸帶寬，提高節(jié)點(diǎn)處理能力，增加節(jié)點(diǎn)存儲容量，融入網(wǎng)絡(luò)控制協(xié)議等升級擴(kuò)展技術(shù)已經(jīng)難以滿足日益擴(kuò)大的用戶業(yè)務(wù)承載需求，并且隨之產(chǎn)生了一系列網(wǎng)絡(luò)復(fù)雜度快速提高和數(shù)據(jù)傳輸效率顯著降低的問題?？芍貥?gòu)柔性網(wǎng)絡(luò)[1～3]——一種面向服務(wù)提供的新型網(wǎng)絡(luò)體系結(jié)構(gòu)的出現(xiàn)，可以使互聯(lián)網(wǎng)擺脫傳統(tǒng)網(wǎng)絡(luò)技術(shù)的束縛，解決當(dāng)前互聯(lián)網(wǎng)面臨的2大問題：1) 網(wǎng)絡(luò)是剛性的，只能依靠升級和擴(kuò)展；2) 網(wǎng)絡(luò)資源是共享的，彼此之間會互相干擾。

在可重構(gòu)柔性網(wǎng)絡(luò)中，用戶業(yè)務(wù)與網(wǎng)絡(luò)服務(wù)的關(guān)系從傳統(tǒng)的緊耦合變?yōu)樗神詈希核鶚?gòu)建網(wǎng)絡(luò)提供服務(wù)的方式是基于網(wǎng)絡(luò)自身的能力，而不是特定的用戶業(yè)務(wù)需求，從而實(shí)現(xiàn)了用戶與服務(wù)分離；每種網(wǎng)絡(luò)服務(wù)可以支持多種特性相似的用戶業(yè)務(wù)，新的業(yè)務(wù)可以利用原有的網(wǎng)絡(luò)服務(wù)作為支撐，使得網(wǎng)絡(luò)需要升級的幾率大幅降低。

可重構(gòu)柔性網(wǎng)絡(luò)技術(shù)利用構(gòu)建可重構(gòu)服務(wù)承載網(wǎng)的方式來提供相應(yīng)的網(wǎng)絡(luò)服務(wù)。在服務(wù)承載網(wǎng)中，網(wǎng)絡(luò)服務(wù)提供的質(zhì)量直接影響用戶需求的滿足程度和用戶請求的響應(yīng)速率。因此，服務(wù)承載網(wǎng)需要在底層網(wǎng)絡(luò)發(fā)生故障時(shí)快速愈合，才能盡可能快地恢復(fù)正常的網(wǎng)絡(luò)服務(wù)供應(yīng)，維持終端用戶繼續(xù)正常地獲取他們所訂閱的服務(wù)。

本文研究了服務(wù)承載網(wǎng)的快速愈合機(jī)理并提出了服務(wù)承載網(wǎng)的快速愈合算法。該算法區(qū)別于傳統(tǒng)的對失效服務(wù)承載網(wǎng)進(jìn)行全局重映射的方法，它通過引入多商品流問題[4](multi-commodity flow problem)的解決策略，將服務(wù)承載網(wǎng)愈合的問題轉(zhuǎn)化為多商品流問題，通過解一次多商品流問題愈合多個(gè)損壞的服務(wù)承載網(wǎng)，以實(shí)現(xiàn)承載網(wǎng)發(fā)生故障時(shí)的快速愈合，從而使得服務(wù)承載網(wǎng)具有快速可重構(gòu)這一特性。該方法可以提高服務(wù)承載網(wǎng)的愈合成功率，降低愈合時(shí)的時(shí)間消耗，并且可以保持整個(gè)底層網(wǎng)絡(luò)在服務(wù)承載網(wǎng)愈合之后的負(fù)載均衡。

2 相關(guān)工作

通常，服務(wù)承載網(wǎng)可被認(rèn)為是一種面向不同用戶提供差異化服務(wù)的虛擬網(wǎng)絡(luò)，用于滿足用戶對服務(wù)的個(gè)性化需求。利用網(wǎng)絡(luò)虛擬化技術(shù)可構(gòu)建多個(gè)提供異質(zhì)服務(wù)的承載網(wǎng)，并同時(shí)共享底層物理網(wǎng)絡(luò)的資源。因此，可以認(rèn)為網(wǎng)絡(luò)虛擬化技術(shù)是實(shí)現(xiàn)服務(wù)承載網(wǎng)構(gòu)建、運(yùn)行和維護(hù)的重要技術(shù)實(shí)現(xiàn)方式。

眾所周知，目前基于網(wǎng)絡(luò)虛擬化技術(shù)的服務(wù)承載網(wǎng)構(gòu)建問題大部分是 NP完全(NP-complete)問題。近年來啟發(fā)式算法和線性規(guī)劃方法的出現(xiàn)[5～10]，初步解決了此類問題存在計(jì)算復(fù)雜度高的問題。目前，網(wǎng)絡(luò)虛擬化技術(shù)在服務(wù)承載網(wǎng)構(gòu)建方面的應(yīng)用研究仍集中在如何實(shí)現(xiàn)網(wǎng)絡(luò)映射和優(yōu)化資源利用方面，且已存在較多成熟機(jī)制與算法，但對于在故障情形下的服務(wù)承載網(wǎng)愈合問題尚缺乏有效手段。已有的用于解決服務(wù)承載網(wǎng)愈合問題的解決方案仍采用全局重新映射的方法。該方法利用文獻(xiàn)[7]中提出的構(gòu)網(wǎng)算法，將失效的服務(wù)承載網(wǎng)依次進(jìn)行節(jié)點(diǎn)重映射和鏈路重映射。其愈合效果等效于將整個(gè)服務(wù)承載網(wǎng)在底層物理網(wǎng)絡(luò)之上進(jìn)行一次重新映射。這將導(dǎo)致服務(wù)承載網(wǎng)愈合速度慢，且將嚴(yán)重影響和干擾其他虛擬網(wǎng)的正常運(yùn)行和端到端的服務(wù)提供。

本文認(rèn)為，可重構(gòu)服務(wù)承載網(wǎng)的快速愈合問題既是承載網(wǎng)重構(gòu)（重映射）問題，同時(shí)也與其自身抗毀性相關(guān)。近幾年來，雖然服務(wù)承載網(wǎng)抗毀方面的研究也取得了較多成果[11～13]，但仍然存在諸多不足之處。文獻(xiàn)[11]提出了一種基于分布式 Agent的虛擬資源自管理機(jī)制，用于監(jiān)控運(yùn)行于底層網(wǎng)絡(luò)上方的服務(wù)承載網(wǎng)是否發(fā)生故障，并且也提出了承載網(wǎng)“愈合”的概念，但是并沒有給出具體的愈合方法。文獻(xiàn)[12]設(shè)計(jì)出了一種基于共享備用資源的服務(wù)承載網(wǎng)保護(hù)方法，該方法按照預(yù)先給每個(gè)承載網(wǎng)分配一定數(shù)量的備用網(wǎng)絡(luò)資源，用于避免在底層網(wǎng)絡(luò)發(fā)生故障時(shí)帶來的承載網(wǎng)失效問題。這種方法可以看作是一種離線的服務(wù)承載網(wǎng)保護(hù)方法，不能很好地解決在線的承載網(wǎng)失效問題。文獻(xiàn)[13]給出的網(wǎng)絡(luò)環(huán)境中錯(cuò)誤診斷的策略主要基于及時(shí)發(fā)現(xiàn)并解決底層網(wǎng)絡(luò)中出現(xiàn)的硬件故障的方法來恢復(fù)失效的服務(wù)承載網(wǎng)。當(dāng)某些硬件故障受客觀條件限制不能被及時(shí)修復(fù)時(shí)，就會降低服務(wù)承載網(wǎng)恢復(fù)的效率。

總的來說，成熟的服務(wù)承載網(wǎng)愈合方法還未被研究，現(xiàn)存的愈合方法基本上等價(jià)于傳統(tǒng)的構(gòu)網(wǎng)算法，即在底層網(wǎng)絡(luò)發(fā)生故障時(shí)對失效的服務(wù)承載網(wǎng)進(jìn)行全局重映射；此外，服務(wù)承載網(wǎng)抗毀性方面的研究大部分又基本上是基于共享資源保護(hù)方面的策略，并未具體實(shí)現(xiàn)服務(wù)承載網(wǎng)的愈合方法。本文針對服務(wù)承載網(wǎng)愈合方法研究的不足，提出了基于多商品流問題思想的可重構(gòu)服務(wù)承載網(wǎng)快速愈合算法，旨在提高服務(wù)承載網(wǎng)的愈合能力，加快服務(wù)承載網(wǎng)在遭遇故障時(shí)的愈合速率，以及縮小服務(wù)承載網(wǎng)在愈合時(shí)的重構(gòu)規(guī)模。

3 問題描述

隨著網(wǎng)絡(luò)虛擬化研究的深入，網(wǎng)絡(luò)映射問題的定義已經(jīng)變得非常成熟。本節(jié)給出了物理網(wǎng)絡(luò)，服務(wù)承載網(wǎng)以及服務(wù)承載網(wǎng)映射問題的公式化定義，以便在第4節(jié)更加清晰地描述可重構(gòu)服務(wù)承載網(wǎng)的快速愈合機(jī)制。為了方便起見，本文采用文獻(xiàn)[8]中提出的網(wǎng)絡(luò)映射的問題描述。

3.1 物理網(wǎng)絡(luò)

3.2 服務(wù)承載網(wǎng)

3.3 服務(wù)承載網(wǎng)到物理網(wǎng)絡(luò)的映射

服務(wù)承載網(wǎng) Gv到物理網(wǎng)絡(luò) Gp的映射M可以定義如下：找到一個(gè) Gp的子圖 Gp'= ( Np',Lp')，使得所有的虛擬節(jié)點(diǎn)都被映射到不同的物理節(jié)點(diǎn)，并且所有的虛擬鏈路都被映射到由若干物理鏈路構(gòu)成的無環(huán)物理路徑，即：

其中， Np'表示物理節(jié)點(diǎn)的子集， Pp'表示物理網(wǎng)絡(luò)中的無環(huán)物理路徑的集合。M可以進(jìn)一步分解為節(jié)點(diǎn)映射以及鏈路映射：

若M( Gv)滿足以下2個(gè)限制條件：

則M是一個(gè)合法的網(wǎng)絡(luò)映射。

4 可重構(gòu)服務(wù)承載網(wǎng)的快速愈合機(jī)制

服務(wù)承載網(wǎng)在滿足用戶需求的程度和響應(yīng)用戶請求的速率這2個(gè)方面都有著極高的要求。因此，服務(wù)承載網(wǎng)必須在底層網(wǎng)絡(luò)發(fā)生故障時(shí)快速愈合，才能盡可能快地恢復(fù)正常的網(wǎng)絡(luò)服務(wù)供應(yīng)，從而使終端用戶正常地獲取他們所訂閱的服務(wù)。在研究可重構(gòu)服務(wù)承載網(wǎng)快速愈合機(jī)制的過程中，僅僅設(shè)計(jì)出一種服務(wù)承載網(wǎng)的快速愈合算法還不能滿足復(fù)雜多變的網(wǎng)絡(luò)環(huán)境，必須加入一套輔助快速愈合算法運(yùn)行的機(jī)制，才能保證可重構(gòu)服務(wù)承載網(wǎng)快速愈合算法達(dá)到迅速、可靠、高效的預(yù)期目標(biāo)。本節(jié)將詳細(xì)介紹可重構(gòu)服務(wù)承載網(wǎng)快速愈合機(jī)制的3個(gè)重要組成部分：底層物理網(wǎng)絡(luò)設(shè)備可靠性的評估方法，服務(wù)承載網(wǎng)的快速愈合算法和未能實(shí)時(shí)愈合的服務(wù)承載網(wǎng)的排隊(duì)策略。

4.1 物理網(wǎng)絡(luò)設(shè)備可靠性評估

服務(wù)承載網(wǎng)快速愈合的問題在某種程度上也可以看作是網(wǎng)絡(luò)重映射的問題，目的是把一些映射在發(fā)生故障的物理設(shè)備（物理節(jié)點(diǎn)、鏈路）之上的虛擬節(jié)點(diǎn)、鏈路重映射到正常工作的物理設(shè)備。如果在進(jìn)行重映射之后，無法保障這些新的用于支持虛擬節(jié)點(diǎn)、鏈路的物理設(shè)備的可靠性，那勢必會影響到服務(wù)承載網(wǎng)愈合后的正常工作。因此，必須盡可能地把這些失效的虛擬節(jié)點(diǎn)、鏈路映射到可靠性高的物理設(shè)備之上，以保證服務(wù)承載網(wǎng)愈合的穩(wěn)定性。為此，本文設(shè)計(jì)了2個(gè)集中式的容器用來分別記錄整個(gè)底層網(wǎng)絡(luò)中曾經(jīng)發(fā)生過故障的物理節(jié)點(diǎn)和物理鏈路，稱之為節(jié)點(diǎn)容器和鏈路容器，并采用基于“局部性原理(locality principle)”的“最近最少故障(least recent failed)”策略來評估這些物理設(shè)備的可靠性。如圖1所示，該策略規(guī)定，最近一次發(fā)生故障的物理設(shè)備的標(biāo)識符會被記錄在容器頂端(圖中標(biāo)記為top)。

圖1 可靠性評估示例

圖1(a)給出了圖1(b)中所示的底層網(wǎng)絡(luò)的節(jié)點(diǎn)容器和鏈路容器，初始狀態(tài)均為空。在t1時(shí)刻，節(jié)點(diǎn) N1發(fā)生故障，根據(jù)評估策略，N1的標(biāo)識符被加入到節(jié)點(diǎn)容器的頂端，與N1相連的鏈路L1, L2受到N1故障的影響而無法正常使用，所以被對應(yīng)地加入到鏈路容器的頂端；在 t2時(shí)刻，節(jié)點(diǎn) N2第一次發(fā)生故障，因此N2的標(biāo)識符被加入節(jié)點(diǎn)容器中并被記錄在頂端，與N2相連的鏈路L3也被加入到鏈路容器的頂端，L1, L2相應(yīng)地下降一個(gè)位置；t3時(shí)刻的情況類似t1，節(jié)點(diǎn)容器頂端被N1的標(biāo)識符占據(jù)，因?yàn)镹1又發(fā)生了一次新的故障，同時(shí)L1, L2也被移動到鏈路容器的頂端。

物理節(jié)點(diǎn)n或物理鏈路l的可靠性可以按如下方法定義：其中，|V |和|E|分別表示物理網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的總數(shù)， p os[ n], p os[ l]代表物理節(jié)點(diǎn)n或物理鏈路l在各自容器中的位置索引。如圖1(a)所示，物理節(jié)點(diǎn) N 1的位置索引為 1， N2的位置索引為 2，即pos[ N1]= 1 , p os[ N2] = 2 ；物理鏈路 L1, L2的位置索引均為 1， L3的位置索引為 2，即 p os[ L1] =pos[ L2]= 1 , p os[ L3] = 2 。根據(jù)式(6)可知，rN1= 0 .2，rN2= 0 .4，rL1= rL2= 0 .25，rL3= 0 .5。顯然，如果某個(gè)物理節(jié)點(diǎn)或某條物理鏈路從未發(fā)生過故障，那么它也不可能被記錄在該容器中，此時(shí)本文規(guī)定這樣的物理設(shè)備的可靠性固定為1。

4.2 服務(wù)承載網(wǎng)的快速愈合算法

通常來說，底層網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路的故障會導(dǎo)致當(dāng)前的網(wǎng)絡(luò)映射（虛擬節(jié)點(diǎn)、鏈路映射）不能正常使用，從而發(fā)生服務(wù)承載網(wǎng)無法正常提供服務(wù)的情況。本文的核心工作是研究失效服務(wù)承載網(wǎng)的快速愈合算法。該算法會盡可能多地保留原有的可用網(wǎng)絡(luò)映射，從而避免將失效的服務(wù)承載網(wǎng)進(jìn)行全局重映射。首先討論由物理鏈路故障造成服務(wù)承載網(wǎng)失效的問題，再討論由物理節(jié)點(diǎn)故障造成服務(wù)承載網(wǎng)失效的問題。因?yàn)槲锢砉?jié)點(diǎn)的故障同時(shí)也會導(dǎo)致所有連接到它的物理鏈路也發(fā)生故障。

4.2.1 物理鏈路故障

當(dāng)承載虛擬鏈路的物理鏈路發(fā)生故障時(shí)，這些虛擬鏈路所對應(yīng)的服務(wù)承載網(wǎng)就會無法正常工作。應(yīng)對這種情況最直接的方法是找出所有因鏈路故障而發(fā)生狀況的服務(wù)承載網(wǎng)，并將這些承載網(wǎng)依次進(jìn)行重映射，包括重映射每個(gè)承載網(wǎng)的所有虛擬節(jié)點(diǎn)和虛擬鏈路，并完全忽略那些沒有受影響的虛擬節(jié)點(diǎn)、鏈路映射。值得注意的是，在通常情況下，大多數(shù)發(fā)生狀況的服務(wù)承載網(wǎng)中的虛擬節(jié)點(diǎn)、鏈路映射依然可以正常工作。如果底層網(wǎng)絡(luò)的管理者把這些可用的網(wǎng)絡(luò)映射先保存起來用于重用，將是一個(gè)不錯(cuò)的選擇。更重要的是，虛擬鏈路通常是被映射在一些由連續(xù)的物理鏈路構(gòu)成物理路徑之上。這意味著虛擬鏈路通常只是被部分映射在某條物理鏈路之上。因此，單個(gè)物理鏈路故障極有可能只是引發(fā)了用于承載虛擬鏈路的物理路徑的某一段不能正常使用。如圖 2所示，物理鏈路發(fā)生故障導(dǎo)致虛擬鏈路映射在其上方的片段不能正常工作，而映射在物理鏈路上的部分則不受影響。事實(shí)上，一個(gè)失效的服務(wù)承載網(wǎng)中的大部分網(wǎng)絡(luò)映射是可重用的，這也為提高服務(wù)承載網(wǎng)的愈合的效率，實(shí)現(xiàn)其可重構(gòu)的特點(diǎn)提供了可能。

圖2 虛擬鏈路部分故障

在得到一組可行解之后，只需要把不同的商品流所經(jīng)過的物理路徑加入到它們所對應(yīng)的服務(wù)承載網(wǎng)映射中，即可完成服務(wù)承載網(wǎng)的愈合。

利用多商品流問題解決服務(wù)承載網(wǎng)的愈合問題可以有效地在愈合過程中減輕底層網(wǎng)絡(luò)的負(fù)載，并且顯著地提高服務(wù)承載網(wǎng)愈合的成功率，因?yàn)檫@種方法允許將一條虛擬鏈路映射到多條物理路徑之上[8]。更重要的是，以上r個(gè)服務(wù)承載網(wǎng)的愈合只需要通過解一次多商品流問題即可解決，這也在很大程度上提高了服務(wù)承載網(wǎng)的愈合效率。

服務(wù)承載網(wǎng)愈合問題等價(jià)地轉(zhuǎn)化為多商品流問題解決還需要考慮以下3個(gè)方面的問題。

1) 數(shù)據(jù)分組的亂序：多商品流問題的解決方案允許將一條虛擬鏈路映射到多條物理路徑之上，從而帶來了數(shù)據(jù)分組從源到匯傳輸?shù)倪^程中發(fā)生亂序(out-of-order)的可能。所需要做的額外工作是在愈合機(jī)制中加入一些防止數(shù)據(jù)分組在進(jìn)行傳輸時(shí)發(fā)生亂序的控制方案[14～16]。

2) 可行解不存在：如果當(dāng)前網(wǎng)絡(luò)中的資源緊張，不存在滿足式(7)中限制的多商品流可行解時(shí)，可以選擇減小總流量F的方法，從而先愈合部分服務(wù)承載網(wǎng)。底層網(wǎng)絡(luò)管理者可以根據(jù)服務(wù)承載網(wǎng)所提供網(wǎng)絡(luò)服務(wù)的類型，適當(dāng)減小總流量F的大小。例如，若服務(wù)承載網(wǎng) 1V和 2V提供的是非實(shí)時(shí)響應(yīng)的服務(wù)，則可以從F中去掉這2個(gè)流量。在F減小之后，再用多商品流問題的解愈合剩下的服務(wù)承載網(wǎng)。

3) 流的選擇：利用多商品流解決服務(wù)承載網(wǎng)的愈合問題有可能產(chǎn)生多組可行解，即在源和匯之間存在多種傳輸商品流的方案。這時(shí)需要選擇可靠性最高的一種。假設(shè)一個(gè)商品流的傳輸方案需要經(jīng)過n個(gè)物理節(jié)點(diǎn)和l條物理鏈路，那么該商品流傳輸方案的可靠性φ定義為

其中，ir和jr分別代表物理節(jié)點(diǎn)和鏈路的可靠性（式6），其中， ir和jr的大小均不大于1。式(8)意味著如果多商品流問題的解所經(jīng)過的物理節(jié)點(diǎn)和鏈路越少，那么這條商品流的可靠性就越高。這是因?yàn)槿绻唐妨鱾鬏斅肪€上的任意一個(gè)節(jié)點(diǎn)或鏈路發(fā)生故障，這條商品流就不可能達(dá)到預(yù)期的流量，所以它所經(jīng)過路線上的任何一個(gè)節(jié)點(diǎn)或鏈路都不能發(fā)生故障，才能保證這條商品流的正常傳輸。

服務(wù)承載網(wǎng) v1，v2各虛擬鏈路的需求帶寬以及底層網(wǎng)絡(luò)PN的物理鏈路帶寬如圖3所示。為更方便地描述服務(wù)承載網(wǎng)的愈合過程，圖中不考慮物理節(jié)點(diǎn)的能力值物理鏈路發(fā)生故障引發(fā) v1，v2的虛擬鏈路映射不可用。服務(wù)承載網(wǎng)快速愈合算法會在節(jié)點(diǎn)B和F之間解一個(gè)流量大小為的多商品流問題，并得到一組可行解：流量為3的流 f1通過物理路徑傳輸；流量為4的流 f2通過物理路徑傳輸，這2條物理路徑各自傳輸?shù)牧髁看笮【鶠?。最后更新與這2個(gè)商品流對應(yīng)的虛擬鏈路映射，得到至此，服務(wù)承載網(wǎng) v1，v2愈合完成。

圖3 鏈路故障引發(fā)的服務(wù)承載網(wǎng)愈合

4.2.2 物理節(jié)點(diǎn)故障

在討論完由物理鏈路故障導(dǎo)致服務(wù)承載網(wǎng)失效及其愈合算法之后，服務(wù)承載網(wǎng)因物理節(jié)點(diǎn)故障發(fā)生失效，并進(jìn)行愈合的問題就變得相對簡單。概括地講，只需要把那些映射在故障物理節(jié)點(diǎn)上的虛擬節(jié)點(diǎn)轉(zhuǎn)移到其他合適的物理節(jié)點(diǎn)，再更新那些因重映射虛擬節(jié)點(diǎn)而發(fā)生變化的虛擬鏈路映射即可完成服務(wù)承載網(wǎng)的愈合。

選擇合適的物理節(jié)點(diǎn)進(jìn)行虛擬節(jié)點(diǎn)重映射需要考慮以下3個(gè)方面的問題。

1) 可靠性：新物理節(jié)點(diǎn)的可靠性直接影響到服務(wù)承載網(wǎng)愈合的過程可靠程度。如果新的物理節(jié)點(diǎn)經(jīng)常發(fā)生故障，則需要再次更換物理節(jié)點(diǎn)用作虛擬節(jié)點(diǎn)的重映射。

2) 資源：應(yīng)該盡可能地把虛擬節(jié)點(diǎn)轉(zhuǎn)移到那些擁有更多資源的物理節(jié)點(diǎn)上，這樣可以有效的保持底層網(wǎng)絡(luò)的負(fù)載均衡，并且提高網(wǎng)絡(luò)資源的利用率。物理節(jié)點(diǎn)n的資源 nR定義如下：

3) 距離：新的物理節(jié)點(diǎn)與發(fā)生故障的物理節(jié)點(diǎn)的距離對服務(wù)承載網(wǎng)的愈合也存在一定的影響。如果距離發(fā)生故障的節(jié)點(diǎn)太近，有可能會存在可用物理鏈路過少的隱患；如果距離發(fā)生故障的節(jié)點(diǎn)太遠(yuǎn)，則在服務(wù)承載網(wǎng)愈合之后，會存在數(shù)據(jù)分組傳輸距離過遠(yuǎn)的問題。

綜合1)和2)，定義物理節(jié)點(diǎn)的價(jià)值：

其中，l→n表示物理鏈路l與物理節(jié)點(diǎn)n相鄰接，rn 與 rl的定義見4.1節(jié)；根據(jù)3)，本文限定新物理節(jié)點(diǎn)的選擇范圍H，H代表新物理節(jié)點(diǎn)與距離故障物理節(jié)點(diǎn)之間的跳數(shù)。選擇H范圍內(nèi)具有最高節(jié)點(diǎn)價(jià)值ψ的物理節(jié)點(diǎn)，用于虛擬節(jié)點(diǎn)的重映射。虛擬節(jié)點(diǎn)重映射完成之后，虛擬節(jié)點(diǎn)映射的變化會導(dǎo)致原來與該虛擬節(jié)點(diǎn)相關(guān)的虛擬鏈路不可用，必須對這些虛擬鏈路也進(jìn)行重映射，才能完成服務(wù)承載網(wǎng)的愈合。先記錄下與發(fā)生故障的物理節(jié)點(diǎn)存在虛擬鏈路映射關(guān)系的物理節(jié)點(diǎn)，然后在選擇完新的物理節(jié)點(diǎn)之后，恢復(fù)新物理節(jié)點(diǎn)與那些被記錄的物理節(jié)點(diǎn)之間的虛擬鏈路映射?？梢圆捎弥苯又赜成涞姆椒ㄟM(jìn)行一對一（一條虛擬鏈路對一條物理路徑）的映射，也可以采用多商品流的思想進(jìn)行一對多（一條虛擬鏈路對多條物理路徑）的映射。重映射方法的選擇取決于網(wǎng)絡(luò)中資源的數(shù)量。

假設(shè)有一條物理節(jié)點(diǎn) Np發(fā)生故障，有k個(gè)虛擬節(jié)點(diǎn)映射在 Np上，記為這k個(gè)虛擬節(jié)點(diǎn)分別包含在r個(gè)不同的服務(wù)承載網(wǎng)中，記為V1, V 2 ,… ,Vr( r = k)（r = k 是因?yàn)橥环?wù)承載網(wǎng)的虛擬節(jié)點(diǎn)必須映射到不同的物理節(jié)點(diǎn)）。物理節(jié)點(diǎn)Np的故障會導(dǎo)致這k個(gè)虛擬節(jié)點(diǎn)的映射變得不可用，同時(shí)這k個(gè)服務(wù)承載網(wǎng)也將不再正常工作。本文將進(jìn)行k次恢復(fù)工作，對于第 i(1 ≤ i≤k)次恢復(fù)，愈合算法都會選擇與 Np距離在H之內(nèi)，并具有最高ψ值的物理節(jié)點(diǎn)用來重映射虛擬節(jié)點(diǎn)，并更新受到影響的虛擬鏈路，來完成對應(yīng)服務(wù)承載網(wǎng) Vi的愈合工作。在服務(wù)承載網(wǎng) Vi愈合之后，都會更新網(wǎng)絡(luò)中各個(gè)物理節(jié)點(diǎn)的ψ值，來為下一個(gè)承載網(wǎng)Vi+1的愈合做好準(zhǔn)備。

服務(wù)承載網(wǎng) v1各虛擬鏈路的需求帶寬以及底層網(wǎng)絡(luò)PN的物理鏈路帶寬如圖4所示。為更方便地描述服務(wù)承載網(wǎng)的愈合過程，圖中同樣不考慮物理節(jié)點(diǎn)的能力值。物理節(jié)點(diǎn)F發(fā)生故障引發(fā)服務(wù)承載網(wǎng) v1的虛擬節(jié)點(diǎn)映射 M1( b ) = F 不可用?？焖儆纤惴ㄔ诰嚯xF固定為 2跳的范圍內(nèi)( H = 2 )選擇節(jié)點(diǎn)B或節(jié)點(diǎn)C用作虛擬節(jié)點(diǎn)重映射。假設(shè)2個(gè)節(jié)點(diǎn)的可靠性分別為 rB=0.5， rC=1。底層網(wǎng)絡(luò)中剩余的4條物理鏈路的可靠性均為1。根據(jù)式(10)可知節(jié)點(diǎn)B和節(jié)點(diǎn)C價(jià)值的大小關(guān)系為ψB＜ψC。虛擬節(jié)點(diǎn)b映射到C之后( M1( b) = C )，愈合算法隨之更新轉(zhuǎn)移虛擬節(jié)點(diǎn)而發(fā)生變化的虛擬鏈路映射，將更新為從而完成v1的整個(gè)愈合過程。

圖4 節(jié)點(diǎn)故障引發(fā)的服務(wù)承載網(wǎng)愈合

4.3 未能實(shí)時(shí)愈合的服務(wù)承載網(wǎng)的排隊(duì)策略

在詳細(xì)介紹完服務(wù)承載網(wǎng)的快速愈合算法之后，還必須為那些受物理網(wǎng)絡(luò)資源限制，未能及時(shí)愈合的服務(wù)承載網(wǎng)建立一套合理的排隊(duì)調(diào)度策略，用于盡快處理那些服務(wù)承載網(wǎng)等待愈合的請求。利用一個(gè)優(yōu)先級隊(duì)列來存儲承載網(wǎng)等待愈合的請求，這些請求按照到達(dá)的時(shí)間順序被加入到隊(duì)列中。該隊(duì)列采用一種稱為“可恢復(fù)優(yōu)先(restorable first)”的調(diào)度策略來進(jìn)行管理：底層網(wǎng)絡(luò)的管理者會周期性地按序處理隊(duì)列中的若干請求，一次周期內(nèi)處理請求的數(shù)量取決于底層網(wǎng)絡(luò)的處理能力。如果當(dāng)前請求所指向的服務(wù)承載網(wǎng)可以愈合，則該請求會得到迅速響應(yīng)，并在服務(wù)承載網(wǎng)愈合之后被移出隊(duì)首；否則，該請求會被移動到隊(duì)尾。這種調(diào)度策略可以第一時(shí)間判斷當(dāng)前的網(wǎng)絡(luò)資源是否能滿足隊(duì)首的服務(wù)承載網(wǎng)愈合請求，從而在整體上降低了愈合請求的平均等待時(shí)間。

圖5詳細(xì)描述了“可恢復(fù)優(yōu)先”調(diào)度策略的工作流程。假設(shè)在一個(gè)底層網(wǎng)絡(luò)的處理周期T內(nèi)可以處理2個(gè)服務(wù)承載網(wǎng)愈合請求，并且請求隊(duì)列在初始狀態(tài)存有4個(gè)請求： 1m（隊(duì)首）， 2m， 3m和 4m，分別代表第1到第4個(gè)請求。在第1個(gè)處理周期內(nèi)，m1得到處理并被彈出隊(duì)列，因其對應(yīng)的服務(wù)承載網(wǎng)已成功愈合。m 2被移動到隊(duì)尾，代表目前網(wǎng)絡(luò)中的資源還不能支持其對應(yīng)承載網(wǎng)的愈合工作；在第 2個(gè)處理周期內(nèi)， m 3和 m 4都被彈出隊(duì)列，代表它們對應(yīng)的承載網(wǎng)都可以成功愈合。并且又有一個(gè)新的請求 m 5按照到達(dá)隊(duì)列的時(shí)間先后順序被加入到隊(duì)尾，代表 m 5對應(yīng)在承載網(wǎng)在愈合算法執(zhí)行后未能成功恢復(fù)。

圖5 愈合請求隊(duì)列調(diào)度

5 實(shí)驗(yàn)數(shù)據(jù)與性能評估

在本節(jié)中，本文通過C++編程語言實(shí)現(xiàn)了服務(wù)承載網(wǎng)的快速愈合算法，并通過大量的仿真實(shí)驗(yàn)對其在愈合成功率、愈合效率以及對底層網(wǎng)絡(luò)負(fù)載均衡的影響3個(gè)方面進(jìn)行了性能評估。本文還將服務(wù)承載網(wǎng)的快速愈合算法與傳統(tǒng)的應(yīng)對服務(wù)承載網(wǎng)故障時(shí)的全局重映射方法進(jìn)行了對比，并通過實(shí)驗(yàn)數(shù)據(jù)說明本文提出的算法比傳統(tǒng)的全局重映射算法在性能上有了一定的提高。

5.1 實(shí)驗(yàn)環(huán)境部署

1) 底層物理網(wǎng)絡(luò)：底層物理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)由GT-ITM[17]拓?fù)渖晒ぞ呱桑何锢砭W(wǎng)絡(luò)包含50個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)之間的連接概率為25%，即物理網(wǎng)絡(luò)包含300條物理鏈路。物理節(jié)點(diǎn)的能力和物理鏈路的帶寬在區(qū)間[15,20]內(nèi)服從均勻分布。在進(jìn)行仿真實(shí)驗(yàn)的過程中，物理節(jié)點(diǎn)故障次數(shù)和物理鏈路故障次數(shù)的比例為 1:4。這些故障均發(fā)生在事先預(yù)定的時(shí)間點(diǎn)。物理節(jié)點(diǎn)和鏈路的初始可靠性均為 1。物理設(shè)備故障：在實(shí)驗(yàn)的過程中，預(yù)設(shè)了 50次物理設(shè)備故障，包括10次物理節(jié)點(diǎn)故障和40次物理鏈路故障。這些故障會在每個(gè)固定的時(shí)間按順序發(fā)生，并且發(fā)生過故障的節(jié)點(diǎn)和鏈路在實(shí)驗(yàn)過程中不會被修復(fù)。

2) 服務(wù)承載網(wǎng)：在仿真實(shí)驗(yàn)環(huán)境中，假設(shè)同時(shí)存在 50個(gè)擁有隨機(jī)拓?fù)浣Y(jié)構(gòu)的服務(wù)承載網(wǎng)運(yùn)行在共享的底層網(wǎng)絡(luò)之上。這些承載網(wǎng)的虛擬節(jié)點(diǎn)的能力需求以及虛擬鏈路的帶寬需求在區(qū)間[5,10]內(nèi)服從均勻分布。在仿真實(shí)驗(yàn)的過程中，通過服務(wù)承載網(wǎng)快速愈合算法來恢復(fù)因物理設(shè)備故障導(dǎo)致的承載網(wǎng)。

5.2 仿真實(shí)驗(yàn)數(shù)據(jù)

仿真實(shí)驗(yàn)比較了服務(wù)承載網(wǎng)快速愈合算法和傳統(tǒng)的全局重映射方法在成功率，效率以及負(fù)載均衡3個(gè)方面的性能。從實(shí)驗(yàn)圖表來看，仿真實(shí)驗(yàn)會在第10次、第20次、第30次、第40次以及第50次物理發(fā)生故障的時(shí)間點(diǎn)上對比兩者在這3個(gè)方面的性能。

1)愈合成功率：服務(wù)承載網(wǎng)愈合的成功率SR定義如下，

其中，F(xiàn)v代表失效的承載網(wǎng)個(gè)數(shù)，Sv代表通過愈合算法成功恢復(fù)的承載網(wǎng)個(gè)數(shù)。如圖6所示，快速愈合算法在整個(gè)服務(wù)承載網(wǎng)的愈合過程中保持了約85%的平均恢復(fù)成功率，而傳統(tǒng)的全局重映射算法的平均成功率僅有大約70%。特別是當(dāng)物理網(wǎng)絡(luò)故障越來越多時(shí)，全局重映射算法的愈合成功率急劇下降。這是因?yàn)楫?dāng)物理網(wǎng)絡(luò)中的資源緊缺時(shí)，快速愈合算法大量地重用了先前的網(wǎng)絡(luò)映射，并允許虛擬鏈路進(jìn)行一對多的映射，充分利用了網(wǎng)絡(luò)中的剩余資源。而全局重映射算法只能進(jìn)行虛擬鏈路的一對一映射，導(dǎo)致網(wǎng)絡(luò)中一些剩余的帶寬不能被充分利用，所以愈合成功率會大幅度下降。

圖6 服務(wù)承載網(wǎng)愈合成功率

2) 愈合效率：在本文的仿真實(shí)驗(yàn)中，通過比較2種算法在愈合每個(gè)失效的服務(wù)承載網(wǎng)時(shí)所消耗的平均時(shí)間來進(jìn)行算法的效率評估。從圖7顯示的實(shí)驗(yàn)結(jié)果可以看到，使用快速愈合算法進(jìn)行愈合的服務(wù)承載網(wǎng)的平均愈合時(shí)間約為0.5s左右，而使用全局重映射算法進(jìn)行愈合的服務(wù)承載網(wǎng)的平均愈合時(shí)間為0.7s左右，快速愈合算法的運(yùn)行效率比全局重映射算法的效率提高了近30%。這是因?yàn)榭焖儆纤惴梢栽谝淮芜\(yùn)行的過程中愈合多個(gè)服務(wù)承載網(wǎng)，而全局重映射算法只能一次愈合一個(gè)服務(wù)承載網(wǎng)。

圖7 服務(wù)承載網(wǎng)愈合效率

3) 負(fù)載均衡：底層網(wǎng)絡(luò)的負(fù)載均衡Ω包含物理節(jié)點(diǎn)的負(fù)載均衡NΩ以及物理鏈路的負(fù)載均衡LΩ，本文用標(biāo)準(zhǔn)差的形式來定義這3種負(fù)載均衡，定義如下：

其中， D Ni表示物理節(jié)點(diǎn) N i用于虛擬節(jié)點(diǎn)映射之后的剩余能力，代表底層網(wǎng)絡(luò)中所有n個(gè)物理節(jié)點(diǎn)剩余能力的平均值；類似地， D Li表示物理鏈路 Li用于虛擬鏈路映射之后的剩余帶寬，代表底層網(wǎng)絡(luò)中所有l(wèi)個(gè)物理鏈路剩余帶寬的平均值。顯然，根據(jù)標(biāo)準(zhǔn)差的特點(diǎn)，虛擬節(jié)點(diǎn)和虛擬鏈路分配在各個(gè)物理節(jié)點(diǎn)和物理鏈路之上的程度越是平均，底層網(wǎng)絡(luò)的負(fù)載就越是均衡。對應(yīng)地，ΩN, ΩL,Ω三者的值就越趨近于0。在仿真實(shí)驗(yàn)中，參數(shù)α的值由物理節(jié)點(diǎn)和物理鏈路發(fā)生故障的比例決定。因?yàn)楣?jié)點(diǎn)故障和鏈路故障發(fā)生次數(shù)的比例為1:4，所以α=20%。圖8給出了在服務(wù)承載網(wǎng)愈合之后，底層網(wǎng)絡(luò)中節(jié)點(diǎn)、鏈路以及全局負(fù)載的變化趨勢。從圖中可以看到2種算法在對物理節(jié)點(diǎn)負(fù)載的變化趨勢方面的影響基本相同，這是因?yàn)?種算法所采用的虛擬節(jié)點(diǎn)重映射策略基本相同，都是選擇一個(gè)適當(dāng)?shù)奈锢砉?jié)點(diǎn)用作虛擬節(jié)點(diǎn)重映射。由于快速愈合算法允許虛擬鏈路進(jìn)行一對多的映射，可以將虛擬鏈路相對平均地分配在各條物理鏈路之上，充分利用了網(wǎng)絡(luò)中的剩余帶寬，所以在服務(wù)承載網(wǎng)愈合之后，物理鏈路負(fù)載的增長趨勢較為緩慢；而全局重映射算法只能進(jìn)行一對一的鏈路映射，不能充分利用網(wǎng)絡(luò)中的剩余帶寬，所以在服務(wù)承載網(wǎng)愈合之后，物理鏈路負(fù)載的增長趨勢比較明顯。在本文的實(shí)驗(yàn)環(huán)境中，有80%的故障都來自物理鏈路，所以底層網(wǎng)絡(luò)的全局負(fù)載主要受物理鏈路負(fù)載的影響。因此，兩者的增長趨勢也較為接近。

4) 網(wǎng)絡(luò)規(guī)模變化：圖9～圖11分別給出了當(dāng)網(wǎng)絡(luò)規(guī)模發(fā)生變化時(shí)，即底層網(wǎng)絡(luò)物理節(jié)點(diǎn)和服務(wù)承載網(wǎng)的數(shù)量分別同時(shí)增加10%、20%、30%、40%、50%時(shí)（物理節(jié)點(diǎn)依然保持25%連接率），2個(gè)算法在底層網(wǎng)絡(luò)50次故障全部發(fā)生之后在愈合成功率，效率以及對底層網(wǎng)絡(luò)全局負(fù)載 3個(gè)方面的變化趨勢。從實(shí)驗(yàn)結(jié)果可見，隨著網(wǎng)絡(luò)規(guī)模逐漸的增大，2個(gè)算法在愈合成功率和負(fù)載均衡方面的差異越來越小。這是因?yàn)樵诖笠?guī)模網(wǎng)絡(luò)環(huán)境中底層網(wǎng)絡(luò)資源豐富，當(dāng)?shù)讓泳W(wǎng)絡(luò)發(fā)生故障時(shí)，并不會導(dǎo)致網(wǎng)絡(luò)資源的稀缺，快速愈合算法在網(wǎng)絡(luò)資源稀缺時(shí)體現(xiàn)的性能優(yōu)勢相對弱化，所以在愈合成功率和負(fù)載均衡方面的差異變??；相反，當(dāng)小規(guī)模網(wǎng)絡(luò)發(fā)生故障時(shí)，很可能引起底層網(wǎng)絡(luò)資源的稀缺，而快速愈合算法可以充分利用底層網(wǎng)絡(luò)剩余資源，所以快速愈合算法在小規(guī)模網(wǎng)絡(luò)環(huán)境中的性能更加突出。此外，服務(wù)承載網(wǎng)愈合效率，即愈合平均時(shí)間，是由算法的復(fù)雜度所決定。因?yàn)?2個(gè)算法的復(fù)雜度相同，所以當(dāng)網(wǎng)絡(luò)的規(guī)模逐步從10%擴(kuò)大到50%時(shí)，2個(gè)算法在愈合效率方面的差異變化并不明顯。

圖8 底層網(wǎng)絡(luò)全局負(fù)載

圖9 網(wǎng)絡(luò)規(guī)模變化下的服務(wù)承載網(wǎng)愈合成功率

圖10 網(wǎng)絡(luò)規(guī)模變化下的服務(wù)承載網(wǎng)愈合效率

圖11 網(wǎng)絡(luò)規(guī)模變化下的底層網(wǎng)絡(luò)負(fù)載

6 結(jié)束語

本文研究了可重構(gòu)服務(wù)承載網(wǎng)的快速愈合機(jī)制，通過部分調(diào)整失效的虛擬節(jié)點(diǎn)或鏈路映射來愈合失效的服務(wù)承載網(wǎng)，避免了從全局上進(jìn)行服務(wù)承載網(wǎng)重映射的繁瑣工作。該方法基于網(wǎng)絡(luò)流的思想，將服務(wù)承載網(wǎng)的愈合問題轉(zhuǎn)化為多商品流問題加以解決，并通過解一次多商品流問題同時(shí)恢復(fù)所有失效的承載網(wǎng)，極大地提高了服務(wù)承載網(wǎng)愈合的成功率和效率，并且保持了底層網(wǎng)絡(luò)的負(fù)載均衡。通過大量的仿真實(shí)驗(yàn)數(shù)據(jù)表明，該算法與傳統(tǒng)的全局重映射方法相比，能更高效地提高服務(wù)承載網(wǎng)的愈合成功率和愈合效率，并可顯著降低對底層網(wǎng)絡(luò)負(fù)載的影響。

[1] ANDERSON T, PETERSON L, SHENKER S, et al. Overcoming the Internet impasse through virtualization[J]. IEEE Computer Magazine,2005, 38(4): 34-41.

[2] GENI[EB/OL]. http://www.geni.net/.

[3] BAVIER A, FEAMSTER N, HUANG M, et al. In VINI veritas: realistic and controlled network experimentation[A]. Proc ACM SIGCOMM[C]. Pisa, Italy, 2006.

[4] AHUJA R K, MAGNANTI T L, ORILIN J B. Network Flows: Theory,Algorithms, and Applications[M]. Prentice Hall, 1993.

[5] SZETO W, IRAQI Y, BOUTABA R, A multi-commodity flow based approach to virtual network resource allocation[A]. Proc of IEEE Global Telecommunications Conference (GLOBECOM’03)[C]. San Francisco, CA (USA), 2003. 3004-3008.

[6] FAN J, AMMAR M. Dynamic topology configuration in service overlay networks-a study of reconfiguration policies[A]. Proc of IEEE INFOCOM06[C]. Barcelona, Spain, 2006. 1-12.

[7] ZHU Y, AMMAR M. Algorithms for assigning substrate network resources to virtual network components[A]. Proc of IEEE INFOCOM06[C]. Barcelona, Spain, 2006. 1-12.

[8] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[A]. Proc of ACM SIGCOMM[C]. 2008. 17-29.

[9] CHOWDHURY N M M K, RAHMAN M R, BOUTABA R. Virtual network embedding with coordinated node and link mapping[A]. Proc of IEEE INFOCOM09[C]. Rio de Janeiro, Brazil, 2009. 783-791.

[10] LISCHKA J, KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection[A]. Proc of ACM SIGCOMM[C].Barcelona, Spain, 2009.

[11] FAJJARI I, AIARI M, BRAHAM O. Towards an automatic piloting virtual network architecture[A]. Proc of IFIP International Conference on New Technologies, Mobility and Security (NTMS)[C]. Paris,France, 2011.

[12] GUO T, WANG N, MOESSNER K. Shared backup network provision for virtual network embedding[A]. Proc of IEEE ICC2011[C]. Kyoto,Japan, 2011.

[13] YALIAN P, XUESONG Q, SHUNLI Z. Fault diagnosis in network virtualization environment[A]. Proc of 18th Conference on Telecommunications (ICT)[C]. Ayia Napa, Cyprus, 2011.

[14] AVRAMOPOULOS I, SYRIVELIS D, REXFORD J, et al. Secure Availability Monitoring Using Stealth Probes[R]. Princeton University,Technical Report TR-769-06, 2006.

[15] FELDMANN A, GREENBERG A, LUND C, et al. Netscope: tra_c engineering for IP networks[J]. IEEE Network Magazine, 2000,14(2):11-19.

[16] AUGUSTIN B, CUVELLIER X, ORGOGOZO B, et al. Avoiding traceroute anomalies with paris traceroute[A]. Proc of Internet Measurement Conference[C]. New York, NY, USA: ACM Press, 2006.153-158.

[17] ZEGURA E W, CALVERT K L, BHATTACHARJEE S. How to model an internetwork[A]. Proc of IEEE INFOCOM[C]. Francisco,CA , USA, 1996.594-602.