可重構(gòu)服務(wù)承載網(wǎng)主動保護算法研究

齊寧，汪斌強，王志明

（1. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002；2. 中國人民解放軍61062部隊，北京 100091）

1 引言

互聯(lián)網(wǎng)由于基于IP分組交換、資源統(tǒng)計復(fù)用和“盡力而為”服務(wù)模式的特點，輔以O(shè)verlay、CDN、VPN、MPLS等技術(shù)大大拓展了其所能承載的業(yè)務(wù)范圍，一定程度上滿足了規(guī)?；慕换ナ綌?shù)據(jù)業(yè)務(wù)、音視頻業(yè)務(wù)和多播業(yè)務(wù)等承載要求，但并未從根本上解決互聯(lián)網(wǎng)面臨的問題，眾多業(yè)務(wù)仍需通過構(gòu)建物理專網(wǎng)的形式來運營，也使得目前的互聯(lián)網(wǎng)體系難以支撐網(wǎng)絡(luò)融合的需求。

深入分析產(chǎn)生上述問題的原因，一方面在當前的互聯(lián)網(wǎng)體系架構(gòu)下，部署新的服務(wù)和技術(shù)需要對網(wǎng)絡(luò)系統(tǒng)進行升級和改造，而互聯(lián)網(wǎng)龐大的規(guī)模導(dǎo)致這種改造成本過高。另一方面，互聯(lián)網(wǎng)是由眾多異構(gòu)的自治域組成，分別由不同的互聯(lián)網(wǎng)服務(wù)提供商（ISP）建設(shè)、運營和管理，僅僅一個ISP部署應(yīng)用新技術(shù)只能獲得很少的收益，而要其他ISP都同意這樣做是非常困難的。因此，雖然目前互聯(lián)網(wǎng)應(yīng)用上的創(chuàng)新層出不窮，但是在網(wǎng)絡(luò)技術(shù)本身的創(chuàng)新卻處于停滯不前的僵化境地[1]。

基于上述分析，擺脫傳統(tǒng)網(wǎng)絡(luò)技術(shù)體系的束縛，著眼于網(wǎng)絡(luò)服務(wù)的創(chuàng)新視角，以用戶業(yè)務(wù)需求為驅(qū)動，提出了面向服務(wù)承載的可重構(gòu)柔性網(wǎng)絡(luò)（RFNet,reconfigurable flexible network）技術(shù)體系[2,3]，將網(wǎng)絡(luò)基礎(chǔ)設(shè)施提供和服務(wù)提供2大功能實體在邏輯上分離?；A(chǔ)設(shè)施提供商建設(shè)、管理和維護物理網(wǎng)絡(luò)基礎(chǔ)設(shè)施；服務(wù)提供商基于可重構(gòu)路由交換平臺[2,3]，對現(xiàn)有和未來可能出現(xiàn)的用戶業(yè)務(wù)進行科學聚類，針對某一類業(yè)務(wù)根據(jù)其業(yè)務(wù)特性需求，通過構(gòu)建可重構(gòu)服務(wù)承載網(wǎng)（RSCN, reconfigurable service carrying network）的方式（如圖1所示）為終端用戶提供滿足業(yè)務(wù)特性需求的通信服務(wù)。物理網(wǎng)絡(luò)負責提供網(wǎng)絡(luò)資源，服務(wù)承載網(wǎng)負責提供特定價值的服務(wù)，從而在共享由不同基礎(chǔ)設(shè)施提供商提供的底層物理網(wǎng)絡(luò)資源基礎(chǔ)上，能同時支持多個不同服務(wù)提供商的異質(zhì)的網(wǎng)絡(luò)體系結(jié)構(gòu)并存，為用戶提供多樣化的網(wǎng)絡(luò)服務(wù)。比如構(gòu)建了支持視頻業(yè)務(wù)的服務(wù)承載網(wǎng)后，可以為終端用戶提供高質(zhì)量的視頻點播、IPTV、視頻會議、視頻電話等業(yè)務(wù)，并且可以根據(jù)網(wǎng)絡(luò)資源狀況對用戶接入數(shù)量進行控制，以保障網(wǎng)絡(luò)服務(wù)質(zhì)量。通過將網(wǎng)絡(luò)服務(wù)提供從基礎(chǔ)設(shè)施提供中分離出來，可重構(gòu)柔性網(wǎng)絡(luò)技術(shù)使得網(wǎng)絡(luò)服務(wù)的創(chuàng)新變得更加靈活，這種邏輯上的分離使得二者可以獨立地演進，可以在支持現(xiàn)有服務(wù)的同時靈活地部署新的網(wǎng)絡(luò)服務(wù)。

圖1 RFNet中構(gòu)建RSCN

由于IP骨干網(wǎng)網(wǎng)絡(luò)故障的時有發(fā)生[4,5]，從而造成RSCN服務(wù)中斷，給用戶帶來不好的用戶體驗，同時還給服務(wù)提供者造成經(jīng)濟損失，特別是一些重要的應(yīng)用，如有線電視網(wǎng)絡(luò)，鏈路故障造成的負面影響更是不可估量。因此，如何對已構(gòu)建的RSCN提供可靠有效的保護機制亟待解決，這就迫切需要研究RSCN主動保護模型和機制，在檢測到故障后，能夠迅速采取措施，將流量切換到保護路徑，盡量減小損失。

本文主要解決的問題包括RFNet資源重要程度的描述、RSCN主動保護模型建模、主路徑和保護路徑構(gòu)建算法等。本文組織結(jié)構(gòu)如下：第2節(jié)對國內(nèi)外相關(guān)研究現(xiàn)狀進行論述；第3節(jié)對RSCN主動保護問題進行建模，并給出刻畫資源緊迫程度的方法；第4節(jié)論述RSCN主路徑和保護路徑構(gòu)建算法；第5節(jié)對本文提出的算法進行理論和仿真分析；第6節(jié)是結(jié)束語。

2 相關(guān)研究

針對RSCN的構(gòu)建方法，主要集中在虛擬網(wǎng)和邏輯承載網(wǎng)構(gòu)建算法的研究[2,6,7]。文獻[6]利用混合整數(shù)規(guī)劃，針對不同應(yīng)用場景，有效結(jié)合節(jié)點映射和鏈路映射過程，分別提出了確定型虛擬網(wǎng)映射算法(D-ViNE)和隨機虛擬網(wǎng)映射算法(R-ViNE)。文獻[8]提出了兩階段虛擬網(wǎng)映射算法，首先進行節(jié)點映射，然后利用最短路算法，并基于多商品流問題進行路徑集映射。文獻[9]以構(gòu)建成本為約束條件，以構(gòu)建收益最大化為目標，研究虛擬網(wǎng)構(gòu)建映射問題。文獻[7]基于鏈路負載均衡度和節(jié)點負載均衡度提出自適應(yīng)的均衡虛擬網(wǎng)構(gòu)建方法。文獻[2]以映射路徑上所有節(jié)點的平均強度最小為目標，采用啟發(fā)式算法構(gòu)建邏輯承載網(wǎng)。以上虛擬網(wǎng)和邏輯承載網(wǎng)構(gòu)建算法主要針對虛擬網(wǎng)構(gòu)建進行最小代價或最短路徑優(yōu)化，沒有考慮節(jié)點或鏈路發(fā)生故障及擁塞時的處理策略。

為此，文獻[3]針對網(wǎng)絡(luò)的動態(tài)性，提出了帶遷移同時考慮網(wǎng)絡(luò)均衡的邏輯承載網(wǎng)構(gòu)建方法。文獻[10]基于流量均衡實現(xiàn)虛擬網(wǎng)的拓撲設(shè)計，采用周期性地節(jié)點優(yōu)化策略進行虛擬網(wǎng)重映射，但文中提出的算法首先假設(shè)資源提供能力沒有限制，且節(jié)點映射算法復(fù)雜度較高，難以實際運用。文獻[11]以提高傳統(tǒng)虛擬網(wǎng)映射算法的需求接收率和負載均衡為目的，設(shè)計了虛節(jié)點和虛鏈路的重映射機制。文獻[12]通過預(yù)計算備份鏈路，在發(fā)生鏈路故障時將主路徑的數(shù)據(jù)遷移到備份鏈路上，從而避免服務(wù)中斷。上述算法基于網(wǎng)絡(luò)均衡對虛擬網(wǎng)構(gòu)建進行重新優(yōu)化映射，或者沒有考慮如何避免物理網(wǎng)絡(luò)發(fā)生故障后對RFNet造成的影響，或者提前計算每條物理鏈路備份路徑并預(yù)留帶寬，成本太高。

其他還有一些針對 IP-over-WDM 分層網(wǎng)絡(luò)的可生存性機制的研究工作：文獻[13]基于圖論設(shè)計了高效可擴展的網(wǎng)絡(luò)故障保護機制 SMART，通過縮小已經(jīng)映射的子圖降低邏輯拓撲的復(fù)雜度，從而有效地計算出自愈拓撲映射；文獻[14]擴展了最大流最小割理論，提出了新的連接矩陣，采用規(guī)劃和限界技術(shù)最大化保護鏈路連接度，從而提供較強的網(wǎng)絡(luò)保護能力；文獻[15]針對IP-over-WDM網(wǎng)絡(luò)的可生存性映射算法，基于整數(shù)規(guī)劃、人工智能搜索算法和圖論設(shè)計了優(yōu)化算法。然而，這些算法并不適用于RFNet，首先RSCN的構(gòu)建請求是實時的，RSCN保護模型本質(zhì)是個在線問題，而不像上述文章將網(wǎng)絡(luò)生存性研究抽象成離線問題；其次，設(shè)計目標不同，本文要求在網(wǎng)絡(luò)構(gòu)建成本盡可能小的情況下，進行RSCN保護路徑的規(guī)劃，在網(wǎng)絡(luò)故障發(fā)生后，確保已經(jīng)構(gòu)建的RSCN能夠保持聯(lián)通，從而保證網(wǎng)絡(luò)收益的最大化，而上述文章的目標主要是保證物理網(wǎng)絡(luò)的連通性。

針對RSCN主動保護問題，本文的解決思路是，首先結(jié)合節(jié)點和鏈路的聯(lián)通度，對不同網(wǎng)絡(luò)資源在網(wǎng)絡(luò)中的重要性進行刻畫，在RSCN主路徑和保護路徑的構(gòu)建過程中盡量避免使用易成為瓶頸的資源；在構(gòu)建RSCN主路徑時，以構(gòu)建代價最小為目標，從而保證物理資源的充分利用；在構(gòu)建RSCN保護路徑時不僅要考慮構(gòu)建代價，還要盡量避免占用緊迫程度較高的資源，從而避免易發(fā)生網(wǎng)絡(luò)故障的資源成為備份資源，提高保護路徑的可靠性。

3 RSCN主動保護問題建模

3.1 網(wǎng)絡(luò)模型

有權(quán)無向圖 Gp= ( Np,Ep)表示物理承載網(wǎng)絡(luò)，其中， Np和 Ep分別表示物理網(wǎng)絡(luò)中節(jié)點和鏈路的集合，對于每個 n ∈Np，CN(n)表示物理節(jié)點n能夠提供的能力，如節(jié)點交換能力；同樣，對于每個e∈Ep，表示物理鏈路e能夠提供的能力，如鏈路帶寬。 M B( e)表示經(jīng)過鏈路e的所有RSCN虛鏈路分配的主帶寬； P B( e)表示經(jīng)過鏈路e的所有RSCN虛鏈路分配的保護帶寬； R( e)表示物理鏈路的剩余帶寬。則 R ( e) = CE(e) - M B( e) - P B( e)；同樣可以定義物理節(jié)點剩余能力 R ( n)。

有權(quán)無向圖 Gr= ( Nr, Er)表示 RSCN構(gòu)建需求，其中， Nr和 Er分別表示RSCN構(gòu)建需求中虛節(jié)點和虛鏈路的集合，對于每個表示構(gòu)建請求中對節(jié)點承載能力的約束；對于每個表示構(gòu)建請求中對鏈路承載能力的約束。

3.2 RSCN構(gòu)建模型

由于在RSCN構(gòu)建時需要考慮保護路徑，因此，RSCN構(gòu)建問題包括2個步驟。

1) 主路徑構(gòu)建

一個 RSCN主路徑構(gòu)建問題可以描述成從 Gr到 Gp子集的一個滿足 Gr中約束條件的映射 Gs，如式（1）所示。

由于一個 RSCN構(gòu)建請求中節(jié)點位置是確定的，RSCN構(gòu)建問題可以簡化成鏈路映射，仍是個NP難問題[16]，可以利用啟發(fā)式算法求解。

2) 保護路徑構(gòu)建

除了進行RSCN主路徑構(gòu)建之外，針對網(wǎng)絡(luò)故障保護，還需要對RSCN的鏈路構(gòu)建保護路徑。

對于虛鏈路re，為了保證在鏈路故障時其故障鏈路上的數(shù)據(jù)流能得到保護，必須保證 er的保護路徑和主路徑?jīng)]有重復(fù)映射鏈路?？梢岳胟最短路算法或雙重主路徑方法[12]求解保護路徑。但是，直接利用上述算法并沒有對保護資源進行區(qū)別對待，可能產(chǎn)生更多瓶頸資源，從而導(dǎo)致網(wǎng)絡(luò)故障波及范圍擴張，對后續(xù)RSCN的可用性產(chǎn)生惡性循環(huán)。為此必須對網(wǎng)絡(luò)資源進行刻畫，具體見3.3節(jié)描述。同時，考慮到經(jīng)濟性和實用性，保護路徑不需預(yù)留與主路徑等同的帶寬，可按照服務(wù)提供商與基礎(chǔ)設(shè)施提供商的協(xié)定預(yù)留相應(yīng)能力的資源。

一個 RSCN保護路徑構(gòu)建問題可以描述成從Gr到 Gp子集的一個滿足 Gr中服務(wù)提供商與基礎(chǔ)設(shè)施提供商的協(xié)定保護帶寬的映射 Gps，如式(2)所示。

其中，Nps?Np, Eps?Ep, Cps代表網(wǎng)絡(luò)保護能力。

不失一般性，本文研究單鏈路故障的情況。因此，可以考慮將共享保護路徑的資源進行聚合，進一步提高資源利用率。

3.3 資源緊迫度

為了對不同網(wǎng)絡(luò)資源在網(wǎng)絡(luò)中的重要性進行刻畫，本文首先提出資源緊迫度（RSF, resource stress factor）的概念，主要包括 2個元素：聯(lián)通度（CF,connectivity factor）和飽和度（SF, saturation factor）。

如圖2所示的網(wǎng)絡(luò)中，由于許多鏈路都經(jīng)過節(jié)點e，一旦節(jié)點e發(fā)生故障，將導(dǎo)致大面積的網(wǎng)絡(luò)癱瘓，網(wǎng)絡(luò)的聯(lián)通性所受影響最大。因此，節(jié)點 e對網(wǎng)絡(luò)聯(lián)通程度的影響最大，其故障導(dǎo)致的網(wǎng)絡(luò)聯(lián)通性破壞程度也最大。為此，引入如下概念。

圖2 網(wǎng)絡(luò)聯(lián)通度

定義1 節(jié)點影響度：在網(wǎng)絡(luò)pG 中，設(shè)節(jié)點in的度數(shù)為id，則向量為節(jié)點對鄰接點的影響度向量，稱之為節(jié)點影響度。

定義 2 節(jié)點聯(lián)通度：物理網(wǎng)絡(luò)資源的節(jié)點 CF刻畫了由于節(jié)點故障給剩余網(wǎng)絡(luò)造成分割的程度。設(shè)A( Gp)為Gp的鄰接矩陣，則向量 N CF = N I · A(Gp)為各節(jié)點對網(wǎng)絡(luò)聯(lián)通性的影響程度， N CF( ni)的值越大，節(jié)點聯(lián)通度越大，采用式（3）對其進行歸一化后，稱之為節(jié)點聯(lián)通度。

定義 3 鏈路聯(lián)通度：鏈路的鄰接節(jié)點影響度可以反映該鏈路故障對網(wǎng)絡(luò)連通性的影響程度，表示成稱之為鏈路聯(lián)通度。

定義 4 飽和度：用于刻畫當節(jié)點或鏈路發(fā)生故障時，有多少 RSCN會受到影響。如式（4）所示。

其中，SF(x)表示資源x的飽和度，x可以是節(jié)點資源，也可以是鏈路資源，k表示資源x承載RSCN的個數(shù)，xPM 表示資源x中已分配資源的百分比。

定義 5 資源緊迫度：綜合考慮節(jié)點聯(lián)通度、鏈路聯(lián)通度和飽和度，由此得到資源緊迫度，如式（5）所示。

其中，Ψ(x)表示x的資源緊迫度，α和β是調(diào)節(jié)因子，且 α +β=1。Ψ(x)值越大表示資源x的故障對網(wǎng)絡(luò)影響越大。

3.4 構(gòu)建目標

本文的目標是在滿足RSCN構(gòu)建請求約束條件的前提下，充分利用剩余網(wǎng)絡(luò)資源，對RSCN的主路徑和保護路徑進行合理規(guī)劃，從而保證在網(wǎng)絡(luò)故障時，RSCN故障損失盡可能小。為此，結(jié)合資源緊迫度以及資源初始價值，給出改進后的RSCN構(gòu)建代價函數(shù)，如式（6）所示。

其中，c( em)和c( nm)分別代表構(gòu)建的RSCN主路徑所占用的物理鏈路和節(jié)點的初始代價， c( eb)和c( nb)分別代表構(gòu)建的 RSCN保護路徑所占用的物理鏈路和節(jié)點的初始代價。由式（5）可知，資源緊迫度越高，占用其資源構(gòu)建RSCN時付出的代價越高。

此外，還需要保證網(wǎng)絡(luò)故障發(fā)生后的RSCN故障損失盡可能小，為此，假設(shè)鏈路l的故障恢復(fù)時間為 R T( l)，則鏈路l發(fā)生故障后，受其影響的RSCN故障損失如式（7）所示。

其中，M ( l)表示映射到鏈路l上的RSCN虛鏈路集合， B W( es)表示虛鏈路 es分配的帶寬。

4 RSCN主動保護算法

不失一般性，本文將RSCN構(gòu)建需求分解為由RSCN中鄰接的2個節(jié)點和連接這2個節(jié)點的鏈路帶寬的基本需求，由三元組(,,)s t d表示，其中，s、t為鄰接節(jié)點，d為帶寬需求，每一個三元組稱為一個元需求。

完成對需求的分解之后，RSCN主動保護構(gòu)建算法（RAPA, RSCN active protection algorithm）簡化為對元需求逐一求解的過程。元需求主路徑映射實際上就是在pG 中確定一條連接s和t的路徑，記為,stP ，且,stP 滿足：

其中，b(e)表示分配給相鄰節(jié)點的鏈路帶寬。保護路徑映射是在pG 中另外確定一條連接s和t的路徑，記為,'stP ，且,'stP 滿足：

其中，'b(e)表示分配給相鄰節(jié)點的保護帶寬，pb表示保護帶寬需求。

分解之后，原先較大規(guī)模的全圖映射問題轉(zhuǎn)換為求解多個單一鏈路的映射問題，從而將RSCN構(gòu)建的復(fù)雜問題簡化。RAPA包括2個子算法：資源緊迫度感知的主路徑構(gòu)建算法（RSF-awareMLCA,RSF-aware main link construction algorithm）和RSCN保護鏈路構(gòu)建算法（RPLCA, RSCN protection link construction algorithm），RAPA描述如下。

算法1 RAPA( Gp,Gr)

輸入： Gp,Gr

輸出： Gs, Gps

1) 初始化 Gs← N ULL ， Gps← N ULL ；

2) 分解RSCN構(gòu)建需求 Gr；

對每一個RSCN構(gòu)建元需求 Rmeta= ( s, t, d)，執(zhí)行3)到 5)步：

4.1 RSCN主鏈路構(gòu)建算法

對于每個RSCN構(gòu)建元需求，可能存在多條可達路徑，應(yīng)該選擇構(gòu)建代價最小的路徑作為備選路徑。

為了得到連接 2個節(jié)點s和t之間的代價最小路，首先需要將 Gp的權(quán)值矩陣 W ( Gp)做如下改進：

然后利用最短路算法，找出代價最小路徑。RSF-awareMLCA描述如下。

子算法1 RSF -awareMLCA( Gp,Rmeta)

輸入： Gp,Rmeta

輸出：,stP

1) 初始化,stP 為空；

2) 按照式（8）更新W(p)G，利用最短路算法尋找滿足 ,s t之間帶寬需求且代價最小的路Ps,t，如果這樣的路徑不存在，置Ps,t為空，跳轉(zhuǎn)到4)；

3) 更新Ps,t路徑上節(jié)點和鏈路的剩余服務(wù)能力；

4) 若Ps,t非空返回主路徑構(gòu)建結(jié)果Ps,t；若Ps,t為空，無法RSCN構(gòu)建元需求。

算法第2)步更新權(quán)值矩陣，并且基于新的權(quán)值矩陣計算出 ,s t間的最短路Ps,t；第3) 承載能力。對于元需求，如果找不到最小代價路，則RSCN主路徑構(gòu)建失敗。

4.2 RSCN保護鏈路構(gòu)建算法

傳統(tǒng)的思路是在構(gòu)建RSCN之前，對每條物理鏈路均計算出保護路徑，當發(fā)生鏈路故障后，可以從保護路徑集中選擇合適鏈路進行保護，這種方式并不能保證形成最優(yōu)的保護路徑，浪費很多鏈路資源，降低了鏈路利用率；本文的思路是當RSCN構(gòu)建請求到達后，進行主路徑構(gòu)建映射的同時，即進行保護路徑的構(gòu)建。構(gòu)建保護路徑時不僅要考慮構(gòu)建代價，還要盡量避免占用緊迫程度較高的資源，從而避免易發(fā)生網(wǎng)絡(luò)故障的資源成為備份資源；對于保護帶寬的設(shè)置，由于同時發(fā)生鏈路故障的可能性很低，可以將共享同一條保護鏈路的所有RSCN鏈路中保護帶寬最高值作為預(yù)留帶寬值。RPLCA描述如下。

輸入： Gp,Ps,t

輸出： P 's,t

1) 去除 Gp中 Ps,t經(jīng)過的所有鏈路，并按照式（8）更新權(quán)值矩陣；

2) 按照式（9）給出的帶寬滿足條件，利用最短路算法尋找 s, t之間的最小代價路，如果這樣的路徑不存在，置為空，跳轉(zhuǎn)到4)；

5 算法分析

5.1 算法復(fù)雜度分析

對于RSF-awareMLCA子算法，假設(shè)pG中有n個節(jié)點，則對每個元需求進行權(quán)值矩陣更新和最短路算法的最壞時間復(fù)雜度都是 O ( n2)；因此RSF-awareCA算法的最壞時間復(fù)雜度為 O ( n2)。算法消耗的存儲空間主要用于存儲最短路徑，因此空間復(fù)雜度為 O ( n)。

對于RSLFRA子算法，算法第1)步更新權(quán)值矩陣的時間復(fù)雜度為 O ( n2)；算法第2)步最短路算法的最壞時間復(fù)雜度為 O ( n2)；映射的保護路徑最多有 n -1條鏈路，所以第3)步更新路徑服務(wù)承載能力的最壞時間復(fù)雜度為 O ( n)；因此 RSLFRA算法的最壞時間復(fù)雜度為 O ( n2)。算法消耗的存儲空間主要用于存儲最短路徑，因此空間復(fù)雜度為 O ( n)。

5.2 實驗設(shè)定

仿真實驗在配置 Pentium 4 3.06GHz CPU和1GB內(nèi)存的普通PC上進行，實驗利用BRITE工具在100×100的空間下隨機產(chǎn)生由100個節(jié)點組成的物理網(wǎng)絡(luò)拓撲，BRITE參數(shù)設(shè)置如下：HS=LS=100，N=100，Model=WaxMan，Node Placement=Random，alpha=0.15，beta=0.2，m=2，Growth Type=Incremental，BWdist=Unif，MaxBW=100，MinBW=50。因此，任意2個節(jié)點的連接概率是0.5，帶寬資源在50到100間均勻分布。RSCN構(gòu)建請求的到達過程服從時間單位為 100，強度 λr=5的泊松過程，鏈路故障發(fā)生過程服從強度為λf的泊松過程，鏈路故障恢復(fù)時間服從θ=20的指數(shù)分布；每個RSCN的生存時間服從θ=400的指數(shù)分布。RSCN節(jié)點需求個數(shù)在5到10之間均勻分布，任意2個虛節(jié)點的連接概率為0.5，帶寬需求在0到50之間均勻分布。實驗過程中α和β均取0.5，節(jié)點初始價值設(shè)為1，鏈路初始價值設(shè)為連接鏈路兩端點的歐式距離。算法比較BACA[7]、SVNE-Hybrid[12]、不考慮保護機制的RSF-awareMLCA和采用主動保護機制的RAPA在構(gòu)建成功率、主鏈路利用率和平均網(wǎng)絡(luò)鏈路故障損失3個方面的差異。鑒于MATLAB具有強大的函數(shù)庫，仿真用MATLAB編寫完成，為了使結(jié)果更準確，仿真共進行10次，取所有實驗結(jié)果的平均值。

5.3 RSCN成功運行率

RSCN成功運行率是仿真運行后RSCN構(gòu)建成功且不受故障影響中斷服務(wù)的個數(shù)占構(gòu)建請求數(shù)的百分比，即

RSCN成功運行率可以反映構(gòu)建方法的有效性和故障保護能力，成功運行率越高表明構(gòu)建方法越有效且保護能力越強，圖3和圖4分別是和這2種情況下構(gòu)建請求數(shù)從0到300時的RSCN成功運行率結(jié)果。

圖3 λf/λr為0.1的RSCN成功運行率

圖4 λf/λr為0.5的RSCN成功運行率

5.4 主鏈路利用率

主鏈路平均利用率是構(gòu)建的RSCN所占主鏈路帶寬之和與物理網(wǎng)絡(luò)所有鏈路資源帶寬之和的比值，即

在完成RSCN構(gòu)建后，平均網(wǎng)絡(luò)鏈路利用率可以反映RSCN構(gòu)建的網(wǎng)絡(luò)資源利用效率，圖5是仿真運行時間為10 000單位時間，不同取值情況下的平均鏈路利用率實驗結(jié)果。

由實驗結(jié)果可知， 鏈路故障率較低時，幾種算法的鏈路利用率相差不大，其中，RAPA利用率最高，RSF-awareMLCA和SVNE-Hybrid次之，BACA利用率最低；隨著鏈路故障率的增大，各算法的鏈路利用率都呈現(xiàn)下降趨勢，其中，BACA最為明顯，這是由于算法構(gòu)建RSCN時沒有考慮關(guān)鍵資源，且沒有故障保護機制，受鏈路故障影響較大；RAPA的鏈路利用率下降最慢，該算法在故障發(fā)生時能夠切換RSCN故障鏈路到保護路徑，且構(gòu)建RSCN時充分考慮了資源的緊迫程度；SVNE-Hybrid次之，這是由于該算法的故障保護機制占用了較多的保護鏈路資源，減少了主路徑剩余提供能力。

圖5 主鏈路利用率

5.5 平均網(wǎng)絡(luò)鏈路故障損失

平均網(wǎng)絡(luò)鏈路故障損失是網(wǎng)絡(luò)鏈路故障損失與成功運行的RSCN個數(shù)的比值，即

平均網(wǎng)絡(luò)鏈路故障損失可以反映RSCN構(gòu)建和保護機制的經(jīng)濟性，圖6是仿真運行時間為10 000單位時間，不同取值情況下的平均網(wǎng)絡(luò)鏈路故障損失實驗結(jié)果。

圖6 網(wǎng)絡(luò)鏈路故障損失

由實驗結(jié)果可知，鏈路故障率較低時，幾種算法的網(wǎng)絡(luò)鏈路故障損失相差不大，其中，RAPA的平均網(wǎng)絡(luò)鏈路故障損失最低，RSF-awareMLCA和SVNE-Hybrid略高，BACA平均網(wǎng)絡(luò)鏈路故障損失最高；隨著鏈路故障率的增大，各算法的平均網(wǎng)絡(luò)鏈路故障損失都呈現(xiàn)上升趨勢，其中BACA最為明顯，這是由于BACA構(gòu)建RSCN時沒有考慮關(guān)鍵資源，且沒有故障保護機制，受鏈路故障影響的RSCN數(shù)目較多，故障損失最大；RAPA的故障上升最慢，該算法在故障發(fā)生時能夠切換RSCN故障鏈路到保護路徑，且構(gòu)建RSCN時充分考慮了資源的緊迫程度；SVNE-Hybrid居中，盡管該算法提供了較多資源進行故障保護，但是其RSCN構(gòu)建成功率較RAPA較低，因此平均鏈路故障損失較RAPA略高。

從上述實驗數(shù)據(jù)可知，只有 RAPA在構(gòu)建RSCN時充分考慮了資源的緊迫程度，并且為RSCN主路徑映射了相應(yīng)的保護路徑，且保護鏈路帶寬盡可能??；在故障發(fā)生時能夠?qū)SCN故障鏈路快速切換到保護路徑，RSCN成功運行率、主鏈路利用率和平均網(wǎng)絡(luò)鏈路故障損失明顯優(yōu)于其他 3種構(gòu)建方法。

6 結(jié)束語

互聯(lián)網(wǎng)設(shè)計之初的目標使得眾多業(yè)務(wù)仍需通過構(gòu)建物理專網(wǎng)的形式來運營，也使得目前的互聯(lián)網(wǎng)體系難以支撐未來三網(wǎng)融合的需求?？芍貥?gòu)柔性網(wǎng)絡(luò)體系架構(gòu)能夠快速、靈活和高效地為用戶業(yè)務(wù)提供多樣化的網(wǎng)絡(luò)服務(wù)，推動傳統(tǒng)互聯(lián)網(wǎng)技術(shù)向新一代網(wǎng)絡(luò)體系平滑演進。

鑒于IP骨干網(wǎng)網(wǎng)絡(luò)故障導(dǎo)致RSCN服務(wù)中斷，給用戶帶來不好的用戶體驗，同時還給服務(wù)提供者造成經(jīng)濟損失，本文針對RSCN主動保護問題進行了數(shù)學建模和理論分析。為了盡量避免重要資源故障給網(wǎng)絡(luò)帶來的影響，設(shè)計了資源緊迫度感知的主路徑構(gòu)建子算法RSF-awareMLCA；為了提高RSCN的運行成功率和網(wǎng)絡(luò)收益，設(shè)計了RSCN保護鏈路構(gòu)建子算法RPLCA；結(jié)合2個子算法，設(shè)計了RSCN主動保護構(gòu)建算法 RAPA。最后，分析了算法的復(fù)雜度，從RSCN成功運行率、主鏈路利用率和平均網(wǎng)絡(luò)鏈路故障損失3個方面驗證了本文提出的算法的優(yōu)越性。

RSCN的生存性還有很多問題有待研究與探索，需進一步研究跨域RSCN域間鏈路故障的保護機制。

[1] TURNER J, TAYLOR D. Diversifying the Internet[A]. Proceedings ofthe IEEE Conference on Global Telecommunications[C]. St Louis USA, 2005. 755 -760.

[2] 王浩學, 汪斌強, 于婧等. 一體化承載網(wǎng)絡(luò)體系架構(gòu)研究[J]. 計算機學報, 2009, 3(32):371-376.WANG H X, WANG B Q, YU J, et al. Research on architecture of universal carrying network [J]. Chinese Journal of Computers, 2009,3(32):371-376.

[3] 齊寧, 汪斌強, 郭佳. 邏輯承載網(wǎng)構(gòu)建方法的研究[J]．計算機學報，2010, 9(33):1533-1540.QI N, WANG B Q, GUO J. Research on construction methods of logical carrying network[J]. Chinese Journal of Computers,2010,9(33):1533-1540.

[4] IANNACCONE G, CHUAH C, MORTIER R, et al. Analysis of link failures in an IP backbone[A]. Proceedings of ACM SIGCOMM Internet Mensurenient Workshop 2002[C]. Marseille, France, 2002.237-242.

[5] MARKOPULOU A, IANNACCONE G, BHATTACHARYYA S.Characterization of failures in an IP backbone[A]. Proceedings of INFOCOM 2004[C]. Hong Kong, China, 2004. 2307-2317.

[6] MASHARAF N M, RAHMAN M R, BOUTABA R. Virtual network embedding with coordinated node and link mapping[A]. Proceedings of the 28th Conference on Computer Communications, Rio de Janeiro[C]. USA, IEEE, 2009. 783-791.

[7] 齊寧, 王保進, 汪斌強等. 均衡虛擬網(wǎng)構(gòu)建算法研究[J]. 電子與信息學報, 2011, 33(6): 1301-1306.QI N, WANG Q, WANG B J, et al. Research on balanced construction algorithm of virtual network[J]. Journal of Electronics and Information Technology, 2011, 33(6): 1301-1306.

[8] YU M L, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[A]. Proceedings of ACM SIGCOMM on Computer Communication[C]. Seattle, WA, USA, 2008. 17-29.

[9] CAPONE A, ELIAS J, MARTIGNON F. Routing and resource optimization in service overlay networks [J]. Elsevier Computer Networks,2009, 53(2):180-190.

[10] ZHU Y, AMMAR M. Algorithms for assigning substrate network resources to virtual network components[A]. Proceedings of IEEE INFOCOM[C]. Barcelona, Catalunya, Spain, 2006. 1-12.

[11] NABEEL B, CHOWDHURY N M, BOUTABA R. Topology-awareness and reoptimization mechanism for virtual network embedding[A]. Proceedings of the 9th International Networking Conference[C]. Chennai, India, 2010. 27-39.

[12] RAIHAN M, ISSAM A, BOUTABA R. Survivable virtual network embedding[A]. Proceedings of the 9th International Networking Conference[C]. Chennai, India, 2010. 40-52.

[13] MACIEJ K, PATRICK T. Survivable routing of mesh topologies.in IP-over-WDM networks by recursive graph contraction[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(5): 922-933.

[14] LEE K, MODIANO E. Cross-layer survivability in wdm-based networks[A]. IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil. 2009.1017-1025.

[15] KRISHNAIYAN T, MUHAMAD S, LARRY X. Circuits/cutsets duality and a unified algorithmic framework for survivable logical topology design in ip-over-wdm optical networks[A]. Proceedings of IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil. 2009.

[16] KOLLIOPOULOS S, STEIN C. Improved approximation algorithms for unsplittable flow problems[A]. Proceedings of IEEE Symposium on Foundations of Computer Science[C]. 1997.