基于可靠性的服務(wù)功能鏈構(gòu)建算法

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

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

1 引言

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

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

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

2 模型

考慮一個與文獻[12]中相同的網(wǎng)絡(luò)拓撲，如圖1所示。

圖1 網(wǎng)絡(luò)拓撲

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

圖2 模型示意

3 路徑可靠性的計算

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

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

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

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

算法1重點抽樣算法

初始化

主循環(huán)

結(jié)果

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

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

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

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

證明

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

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

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

證畢。

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

證明

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

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

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

3.2.1 路徑失效概率上界

證明

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

證畢。

3.2.2 路徑失效概率下界

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

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

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

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

證明[17]

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

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

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

證畢。

4 最可靠路徑的選擇

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

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

算法2選路算法

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

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

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

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

5 仿真計算

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

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

圖4 最終鏈路選定

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

圖5 各算法可靠性對比

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

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

6 結(jié)束語

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