齊寧，汪斌強，王志明

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

1 引言

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

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

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

圖1 RFNet中構建RSCN

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

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

2 相關研究

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

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

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

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

3 RSCN主動保護問題建模

3.1 網絡模型

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

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

3.2 RSCN構建模型

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

1) 主路徑構建

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

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

2) 保護路徑構建

除了進行RSCN主路徑構建之外，針對網絡故障保護，還需要對RSCN的鏈路構建保護路徑。

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

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

其中，Nps?Np, Eps?Ep, Cps代表網絡保護能力。

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

3.3 資源緊迫度

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

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

圖2 網絡聯(lián)通度

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

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

定義 3 鏈路聯(lián)通度：鏈路的鄰接節(jié)點影響度可以反映該鏈路故障對網絡連通性的影響程度，表示成稱之為鏈路聯(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的資源緊迫度，α和β是調節(jié)因子，且 α +β=1。Ψ(x)值越大表示資源x的故障對網絡影響越大。

3.4 構建目標

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

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

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

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

4 RSCN主動保護算法

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

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

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

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

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

算法1 RAPA( Gp,Gr)

輸入： Gp,Gr

輸出： Gs, Gps

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

2) 分解RSCN構建需求 Gr；

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

4.1 RSCN主鏈路構建算法

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

為了得到連接 2個節(jié)點s和t之間的代價最小路，首先需要將 Gp的權值矩陣 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為空，跳轉到4)；

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

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

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

4.2 RSCN保護鏈路構建算法

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

輸入： Gp,Ps,t

輸出： P 's,t

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

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

5 算法分析

5.1 算法復雜度分析

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

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

5.2 實驗設定

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

5.3 RSCN成功運行率

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

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

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

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

5.4 主鏈路利用率

主鏈路平均利用率是構建的RSCN所占主鏈路帶寬之和與物理網絡所有鏈路資源帶寬之和的比值，即

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

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

圖5 主鏈路利用率

5.5 平均網絡鏈路故障損失

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

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

圖6 網絡鏈路故障損失

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

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

6 結束語

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

鑒于IP骨干網網絡故障導致RSCN服務中斷，給用戶帶來不好的用戶體驗，同時還給服務提供者造成經濟損失，本文針對RSCN主動保護問題進行了數(shù)學建模和理論分析。為了盡量避免重要資源故障給網絡帶來的影響，設計了資源緊迫度感知的主路徑構建子算法RSF-awareMLCA；為了提高RSCN的運行成功率和網絡收益，設計了RSCN保護鏈路構建子算法RPLCA；結合2個子算法，設計了RSCN主動保護構建算法 RAPA。最后，分析了算法的復雜度，從RSCN成功運行率、主鏈路利用率和平均網絡鏈路故障損失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] 王浩學, 汪斌強, 于婧等. 一體化承載網絡體系架構研究[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] 齊寧, 汪斌強, 郭佳. 邏輯承載網構建方法的研究[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] 齊寧, 王保進, 汪斌強等. 均衡虛擬網構建算法研究[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.