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

（國家數(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àn)和、確認(rèn)應(yīng)答和序列號(hào)、超時(shí)重傳[2]等技術(shù)來保障數(shù)據(jù)傳輸?shù)目煽啃浴Ｈ欢@種方式容易造成數(shù)據(jù)分組的“粘連”，從而導(dǎo)致數(shù)據(jù)被截?cái)嗷騻鬏斿e(cuò)誤等后果，同時(shí)，超時(shí)重傳的超時(shí)周期比較長，當(dāng)數(shù)據(jù)分組發(fā)生丟失而采用超時(shí)重傳技術(shù)進(jìn)行恢復(fù)時(shí)，會(huì)增加大量傳輸時(shí)延。多協(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ò)管理難度大、可擴(kuò)展性不足、成本高等問題仍然突出。盡管學(xué)術(shù)界和工業(yè)界針對(duì)數(shù)據(jù)傳輸問題研究開發(fā)了許多協(xié)議以及檢測防護(hù)技術(shù)，但仍需面對(duì)數(shù)據(jù)流傳輸?shù)目煽啃詥栴}?！盀楫?dāng)前互聯(lián)網(wǎng)設(shè)計(jì)新型體系結(jié)構(gòu)是解決這些問題的根本途徑”這一觀點(diǎn)[3]得到學(xué)術(shù)界的一致認(rèn)可。網(wǎng)絡(luò)功能虛擬化（NFV，network functions virtualization）[4-5]等新興技術(shù)應(yīng)運(yùn)而生，NFV不僅可增強(qiáng)網(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憑借其拓展性強(qiáng)、配置靈活且成本低等特性逐漸代替了傳統(tǒng)的中間件盒子[8]。然而，網(wǎng)絡(luò)服務(wù)的可靠性受網(wǎng)絡(luò)功能的影響，網(wǎng)絡(luò)功能故障導(dǎo)致的網(wǎng)絡(luò)服務(wù)失效甚至網(wǎng)絡(luò)癱瘓的事件時(shí)有發(fā)生。例如2012年12 月，谷歌公司因負(fù)載均衡器的配置不當(dāng)導(dǎo)致包括 Gmail和 Chrome 在內(nèi)的多個(gè)谷歌服務(wù)受到影響[9]。因此，如何提高服務(wù)功能鏈的可靠性成為近年來研究的熱點(diǎn)。

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

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

2 模型

考慮一個(gè)與文獻(xiàn)[12]中相同的網(wǎng)絡(luò)拓?fù)?，如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)?/p>

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

圖2 模型示意

3 路徑可靠性的計(jì)算

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

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

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

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

算法1重點(diǎn)抽樣算法

初始化

主循環(huán)

結(jié)果

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

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

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

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

證明

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

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

min+2個(gè)節(jié)點(diǎn)來使A2中的一對(duì)節(jié)點(diǎn)失效，則可得時(shí)，Pr（F）的下界為

證畢。

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

證明

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

3.2 底層節(jié)點(diǎn)失效概率隨機(jī)

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

3.2.1 路徑失效概率上界

證明

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

證畢。

3.2.2 路徑失效概率下界

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

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

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

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

證明[17]

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

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

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

證畢。

4 最可靠路徑的選擇

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

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

算法2選路算法

4.2 底層節(jié)點(diǎn)失效概率隨機(jī)

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

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

算法3s-t路徑可靠性估計(jì)算法

5 仿真計(jì)算

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

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

圖4 最終鏈路選定

在與文獻(xiàn)[12]算法和文獻(xiàn)[13]算法進(jìn)行對(duì)比時(shí)，本文對(duì)擴(kuò)大樣本進(jìn)行了大量實(shí)驗(yàn)，實(shí)驗(yàn)都采用50個(gè)點(diǎn)的拓?fù)洌瑢?duì)比結(jié)果如圖5所示。由圖5可知，與文獻(xiàn)[12]算法相比,本文中算法2的路徑選擇可靠性的提高了 15%以上；而與文獻(xiàn)[13]算法相比，算法2在可靠性保障方面也有所提升。

圖5 各算法可靠性對(duì)比

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

圖6 不同算法所需時(shí)間對(duì)比

6 結(jié)束語

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