蘭巨龍，金子晉，孫鵬浩，江逸茗，王月

（國家數字交換系統(tǒng)工程技術研究中心，河南 鄭州 450002）

1 引言

隨著電子商務、數據中心、社交網絡等新型網絡業(yè)務的迅猛發(fā)展，目前的信息網絡已難以承載不同用戶的多樣化需求[1]。傳統(tǒng) IP網絡架構中，TCP協(xié)議通過校驗和、確認應答和序列號、超時重傳[2]等技術來保障數據傳輸的可靠性。然而這種方式容易造成數據分組的“粘連”，從而導致數據被截斷或傳輸錯誤等后果，同時，超時重傳的超時周期比較長，當數據分組發(fā)生丟失而采用超時重傳技術進行恢復時，會增加大量傳輸時延。多協(xié)議標簽交換（MPLS，multi-protocol label switching）作為IP網絡的下一代傳輸技術，由因特網工程任務組（IETF，Internet engineering task force）提出。但是MPLS環(huán)境下網絡管理難度大、可擴展性不足、成本高等問題仍然突出。盡管學術界和工業(yè)界針對數據傳輸問題研究開發(fā)了許多協(xié)議以及檢測防護技術，但仍需面對數據流傳輸的可靠性問題。“為當前互聯網設計新型體系結構是解決這些問題的根本途徑”這一觀點[3]得到學術界的一致認可。網絡功能虛擬化（NFV，network functions virtualization）[4-5]等新興技術應運而生，NFV不僅可增強網絡服務的靈活性，而且有利于提升網絡整體效能。在NFV中，基于軟件的虛擬網絡功能（VNF，virtual network function）[6]根據需求按一定的邏輯順序組合構成服務功能鏈[7]（SFC，service function chain）來向用戶提供相應的網絡服務。VNF憑借其拓展性強、配置靈活且成本低等特性逐漸代替了傳統(tǒng)的中間件盒子[8]。然而，網絡服務的可靠性受網絡功能的影響，網絡功能故障導致的網絡服務失效甚至網絡癱瘓的事件時有發(fā)生。例如2012年12 月，谷歌公司因負載均衡器的配置不當導致包括 Gmail和 Chrome 在內的多個谷歌服務受到影響[9]。因此，如何提高服務功能鏈的可靠性成為近年來研究的熱點。

對此，文獻[10]通過對 SDN/NFV（software defined networking/network functions virtualization）技術的分析，提出通過組合虛擬安全應用模塊來構建安全服務鏈（SSC，security service chain）的技術思想，但并未給出服務構建策略。文獻[11]基于軟件定義網絡環(huán)境提出一種靈活可配的安全服務鏈動態(tài)組合機制，但未考慮多節(jié)點協(xié)同組合的情況。文獻[12]在假設網絡節(jié)點具有安全服務能力的條件下，研究了節(jié)點間的路由問題，提出一種多點到點的節(jié)點樹路由算法，在算法所得解中單個交換機路由規(guī)則的最大數量是有界的且與網絡大小一致。該算法復雜度低，可在動態(tài)網絡環(huán)境下應用，但是在可靠性保障方面效果并不突出。文獻[13] 提出了一種基于 NFV環(huán)境的數據中心網絡可靠性感知延遲約束路由優(yōu)化框架READ（reliability-aware and delay-constrained），采用一種復雜的混合整數線性規(guī)劃來得到一個最優(yōu)的VNF部署和路由策略，以最大限度地保障數據傳輸可靠性；同時，提出了啟發(fā)式算法—— GSP來降低算法的復雜性并獲得有效的路由方案，然而該算法對復雜度的降低效果仍有待提高。

在現有的研究基礎上，本文側重于節(jié)點間的路由選路問題，在每個流所需的服務都被實現且網絡節(jié)點具有安全服務能力的情況下（即不考慮容量、帶寬等條件的限制），提出一種新的選路算法。首先，排除部分冗余事件來確定路徑失效的上下界；其次，引入多個新的指標，量化節(jié)點的失效概率，將失效概率轉化為長度；最后采用最短路徑算法來進行網絡節(jié)點間路由的可靠性分析，從而給出確切的選路方案。

2 模型

考慮一個與文獻[12]中相同的網絡拓撲，如圖1所示。

圖1 網絡拓撲

為了方便模型的建立及表述，本文將這一拓撲抽象為圖2形式，其中，實心點表示網絡節(jié)點（下文中簡稱為節(jié)點），空心點表示為其提供服務的底層（PM，physical machine）（下文中簡稱為底層節(jié)點）。假設每個底層節(jié)點為節(jié)點提供的服務是可取代的（可以理解為一個或多個可提供服務的備份底層節(jié)點），則只要有至少一個底層節(jié)點向其提供服務，節(jié)點就能發(fā)揮功能。

圖2 模型示意

3 路徑可靠性的計算

假設p為底層節(jié)點失效的概率，n為節(jié)點數，如果每個節(jié)點都只有一個底層節(jié)點為其提供服務，則路徑失效的概率為然而，若每個節(jié)點擁有提供服務的多個底層節(jié)點，計算路徑失效的概率是一個NP-hard問題[14]。不過，仍然可以通過一個（,ε δ）近似算法來估算路徑的失效概率。對于最小化問題，首先給出最優(yōu)解的一個下界，然后把算法的運行結果與這個下界進行比較。最大化問題則先給出一個上界然后把算法的運行結果與這個上界比較。文獻[15]中的蒙特卡洛算法證明，在此背景下路徑失效的概率為其中，E[I]是I的期望值，當循環(huán)次數足夠多時，E[I]可以被近似地估算為1-δ。

如果每個節(jié)點擁有相同個數底層節(jié)點，且每個底層節(jié)點失效的概率一致，則抽取節(jié)點vi的概率為如果節(jié)點v被選中，將其擁有的底層節(jié)點全部

i設為失效；對于其他的底層節(jié)點，仍然遵循其自身的失效概率。定義U為所有失效底層節(jié)點的集合，當且僅當U中底層節(jié)點失效時，測試vi是否為中第一個失效的，若是，定義I=1,若不是則I=0。對這一過程重復次，然后計算路徑失效的概率為具體步驟如算法1所示。

如果采用蒙特卡洛算法[16]，當路徑的失效概率太低時，迭代的次數會非常龐大，而采用重點抽樣的方法進行估算，會使迭代次數減少。

算法1重點抽樣算法

初始化

主循環(huán)

結果

然而，算法1只能估算某條特定路徑的失效概率，并不能用來尋找最可靠的路徑。因此，下文會引入新的指標，來尋找最可靠路徑。

3.1 底層節(jié)點失效概率小且相同

其中，Pr（x）表示事件x發(fā)生的概率。由于容斥公式的第j項有項求和，直接計算路徑失效概率是很困難的。因此，需要減少式（4）中的項數，并根據底層節(jié)點的失效概率小且相同這一條件，進一步簡化計算。

為了減少式（4）中的項，首先需要去除一些冗余事件。例如，若事件iF發(fā)生當且僅當事件Fj發(fā)生，那么事件iF就是冗余的。定義當事件iF冗余時，節(jié)點vi為可移除節(jié)點，為節(jié)點vi所獨有的底層節(jié)點個數。

證明

定義集合A為除多余節(jié)點以外的節(jié)點；1A?A為集合A中恰好擁有個底層節(jié)點的節(jié)點，則為剩余節(jié)點的集合，其中每個元素 擁 有ns

min+1或者更多個底層節(jié)點，則可得當時，Pr（F）的上界為對于A中的任意一對節(jié)點擁有的底層節(jié)點數至少有個，因此，至少需要移除個節(jié)點來使1A中的一對節(jié)點失效；至少需要移除ns

min+2個節(jié)點來使A2中的一對節(jié)點失效，則可得時，Pr（F）的下界為

證畢。

另外，如果每個節(jié)點都擁有ns個不同的底層節(jié)點，每個底層節(jié)點的失效概率為且不相關，那么路徑失效的概率滿足

證明

若節(jié)點vi和vj擁有相同的底層節(jié)點，那么必同時失效且因此，在計算路徑失效概率時，這些擁有相同底層節(jié)點的節(jié)點可以用一個節(jié)點來代替。定義為路徑中的節(jié)點，其中它們的底層節(jié)點至少有一個不相同，則式（4）中的第一項可轉化為又節(jié)點一共擁有至少個底層節(jié)點，則這2個節(jié)點同時失效的概率為對于式（4）中的第2項，有

3.2 底層節(jié)點失效概率隨機

當底層節(jié)點失效的概率隨機時，計算路徑失效的概率十分困難，因此，本文首先對路徑的失效概率范圍進行限定，然后尋找最可靠的路徑。

3.2.1 路徑失效概率上界

證明

定義事件S為節(jié)點有效，如果節(jié)點vi及∪kvk沒有共用的底層節(jié)點，那么事件Si即節(jié)點vi有效與事件Sk即節(jié)點∪kvk有效是不相關的；相反，若節(jié)點vi及∪kvk共享了一個或者多個底層節(jié)點，那么事件與事件相關。因此

證畢。

3.2.2 路徑失效概率下界

首先，將為多個節(jié)點提供服務的底層節(jié)點替換為多個獨立的新的底層節(jié)點，每個新的底層節(jié)點只為一個節(jié)點提供服務，顯然，這不影響原路徑的失效概率。對圖，考慮節(jié)點為節(jié)點vi的底層節(jié)點，其中Bi為節(jié)點擁有的底層節(jié)點的集合，為其失效的概率，定義為由提供服務的節(jié)點數目，完成替換后，底層節(jié)點的失效概率為

若底層節(jié)點失效的概率不相關，則節(jié)點vi失效的概率為

由此，可得路徑失效概率的下界為

其中，P為路徑上節(jié)點的集合。

證明[17]

定義BP為路徑P中節(jié)點擁有的底層節(jié)點集合，為由底層節(jié)點提供服務的節(jié)點集合，且

同時，定義Bs為所有有效節(jié)點（即所有服務層節(jié)點及底層節(jié)點）的集合，Bf為所有失效的節(jié)點的集合，則若路徑P中每個節(jié)點擁有的底層節(jié)點至少有一個在集合Bs中，那么路徑P連通，不論底層節(jié)點是否失效；若路徑P中某一節(jié)點所擁有的所有底層節(jié)點都在集合Bf中，則路徑P失效，不論底層節(jié)點是否失效；若路徑中節(jié)點除外的其他底層節(jié)點都失效，則路徑P連通當且僅當有效。用個獨立且失效概率為的節(jié)點來代替那么所有個節(jié)點都有效的概率為

對每個底層節(jié)點都采用上述操作，最終，可以得到路徑失效概率的下界為

證畢。

4 最可靠路徑的選擇

4.1 底層節(jié)點失效概率小且相同

將擁有底層節(jié)點數小于k的節(jié)點以及與其相連的邊都移除，得到一個新的圖顯然，為了使路徑的可靠性最高，被移除的節(jié)點在選路時并不會被用到。定義V′′V′? 為擁有k個底層節(jié)點的節(jié)點，則本文的目標是找到一條路徑P，定義其包含節(jié)點的集合為VP，使VPV′′∩ 最小。定義Si為節(jié)點iV′′∈ 擁有底層節(jié)點的集合，定義一個變量xij，xij=1，當且僅當邊（i,j）

算法2選路算法

4.2 底層節(jié)點失效概率隨機

如前文所述，可求得某一路徑失效的上下界。在本節(jié)中將那些為多個節(jié)點提供服務的底層節(jié)點替換為多個獨立的新的底層節(jié)點，從而將一個尋找最可靠路徑的問題轉化為一個標準的最短路徑問題。由此，本文提出以下算法，用以估算路徑失效的概率。對于vi∈V，定義為節(jié)點vi的失效概率，底層節(jié)點的失效概率為其中，底層節(jié)點為個節(jié)點提供服務

同時，假定vi失效的概率獨立且為將穿過節(jié)點vi的距離設為那么，尋找最可靠路徑的問題可以轉化為一個標準的最短路徑問題。具體步驟如算法3所示。

算法3s-t路徑可靠性估計算法

5 仿真計算

對本文提出算法進行模擬選路，并對算法可靠性、算法實現所需時間等指標進行仿真評估，同時與其他算法進行比較。本文仿真環(huán)境為Win7操作系統(tǒng)，CPU型號為Core i7-4710HQ，主頻2.50 GHz。在仿真時，如果最可靠路徑受到容量帶寬等條件的限制無法實現，將自動選擇次優(yōu)路徑。采用mininet工具搭建一個如圖3所示的網絡拓撲，其中橫軸表示經度，縱軸表示緯度，*表示網絡節(jié)點， 表示底層節(jié)點，網絡拓撲由37個節(jié)點和52條邊組成，其中，s表示源節(jié)點，t表示目的節(jié)點。

首先，假設每個節(jié)點都由離它最近的2個底層節(jié)點提供服務，每個底層節(jié)點失效的情況獨立且概率為1%。由于底層節(jié)點失效概率很小且相同，所以可以通過算法2獲得最可靠路徑。

圖4 最終鏈路選定

在與文獻[12]算法和文獻[13]算法進行對比時，本文對擴大樣本進行了大量實驗，實驗都采用50個點的拓撲，對比結果如圖5所示。由圖5可知，與文獻[12]算法相比,本文中算法2的路徑選擇可靠性的提高了 15%以上；而與文獻[13]算法相比，算法2在可靠性保障方面也有所提升。

圖5 各算法可靠性對比

在實驗過程中，針對底層節(jié)點失效概率小且相同的情況，最可靠路徑的選擇可在5 s內完成；對于本文中算法2的近似求解可以在1 s內完成；而對于算法 3，采用啟發(fā)式算法得到的路徑的選擇需要幾秒鐘來實現。相信在更為專業(yè)的實驗環(huán)境下，本文算法能得到更快的實現。同時，在對文獻[12]算法與文獻[13]算法的實驗進行復現時，所得實驗時間如圖6所示，從圖6中可知，本文算法實現所需時間較另2種算法均有大幅減少。因此，本文算法具有一定的實際應用價值。

圖6 不同算法所需時間對比

6 結束語

目前的信息網絡已難以承載不同用戶的多樣化需求，針對這一現狀，本文基于目前發(fā)展日新月異的NFV環(huán)境，提出了一種多點到點傳輸的路徑可靠性算法。該算法對服務功能鏈的選定進行量化分析，從而滿足用戶對于服務功能鏈的可靠性需求，性能指標提升較大且算法實現所需時間較少。目前，有關網絡服務功能鏈部署問題的研究正不斷興起，下一步將繼續(xù)完善本文研究，在考慮資源、帶寬等方面影響的情況下，從多個方向完善服務功能鏈可靠性的研究。