一種基于改進(jìn)BDD的SDN可靠性評(píng)估算法

姜厚海，莊 毅，曹子寧

（南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106）

0 引 言

軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）是一種新型的網(wǎng)絡(luò)架構(gòu)［1］。SDN 將轉(zhuǎn)發(fā)設(shè)備的數(shù)據(jù)轉(zhuǎn)發(fā)功能與控制功能進(jìn)行了解耦，數(shù)據(jù)轉(zhuǎn)發(fā)層面的交換設(shè)備僅負(fù)責(zé)簡(jiǎn)單的數(shù)據(jù)轉(zhuǎn)發(fā)功能，控制層面的控制器負(fù)責(zé)路由計(jì)算并統(tǒng)一下發(fā)數(shù)據(jù)轉(zhuǎn)發(fā)規(guī)則給交換設(shè)備，通過南向接口協(xié)議（如OpenFlow 等）控制層面與數(shù)據(jù)層面進(jìn)行交互。隨著SDN 相關(guān)技術(shù)研究的快速發(fā)展，其已成為近年來的研究熱點(diǎn)。然而，SDN所具有的一些新特性可能引發(fā)出一系列可靠性問題［2］，如常見的鏈路故障、單點(diǎn)故障、策略沖突等一系列問題對(duì)網(wǎng)絡(luò)可靠性的影響也越來越嚴(yán)重。

網(wǎng)絡(luò)可靠性評(píng)估作為網(wǎng)絡(luò)與高可用性研究領(lǐng)域內(nèi)的有效方法，在各個(gè)網(wǎng)絡(luò)系統(tǒng)中都得到了廣泛應(yīng)用。在通信網(wǎng)絡(luò)中，通常通過評(píng)估端到端的網(wǎng)絡(luò)連通性來分析網(wǎng)絡(luò)可靠性［3］。根據(jù)基于SDN 的數(shù)據(jù)中心性能問題的最新調(diào)查報(bào)告［4］顯示，當(dāng)前針對(duì)SDN網(wǎng)絡(luò)可靠性的研究大多針對(duì)于控制層，很少有研究關(guān)注基于SDN 的數(shù)據(jù)轉(zhuǎn)發(fā)層的網(wǎng)絡(luò)連通可靠性分析?，F(xiàn)有的關(guān)于網(wǎng)絡(luò)連通可靠性的計(jì)算方法可以被分為2 種類型：精確算法和近似算法。常見的精確算法有：狀態(tài)枚舉法［5］、容斥原理法［6］、不交積和法［7］等?，F(xiàn)有精確算法一般只適用于小型、中小型或者某些具有特殊拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)中。因?yàn)殡S著網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目的增多，網(wǎng)絡(luò)中邊的數(shù)量也會(huì)快速增長，使用精確算法的計(jì)算過程中生成的最小路徑或者割集的數(shù)量也會(huì)造成計(jì)算時(shí)間的增長。

由于網(wǎng)絡(luò)連通可靠性的精確計(jì)算已經(jīng)被Ball 等人［8］證明是一個(gè)NP難題，因此，針對(duì)大規(guī)模網(wǎng)絡(luò)的近似算法被廣泛研究。Satitsatian 等人［9］提出了采用下界搜索法求出網(wǎng)絡(luò)的上下邊界值來近似計(jì)算網(wǎng)絡(luò)可靠性。馮海林［10］通過研究網(wǎng)絡(luò)的連通子網(wǎng)絡(luò)數(shù)量與網(wǎng)絡(luò)斷集數(shù)量的關(guān)系，給出網(wǎng)絡(luò)全端可靠性多項(xiàng)式系數(shù)界的計(jì)算公式，從而得到網(wǎng)絡(luò)全端可靠性。Moshnikov 等人［11］采用蒙特卡羅方法用于確定MTBF和故障概率，對(duì)3 級(jí)信息傳輸?shù)木W(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行評(píng)估。陳永等人［12］提出了基于隨機(jī)Petri網(wǎng)的通信可靠性評(píng)價(jià)方法，建立不同模式下的通信可靠性評(píng)價(jià)模型，并對(duì)可靠性進(jìn)行了量化分析，應(yīng)用于高速鐵路無線通信。高尚等人［13］將遺傳算法、禁忌搜索算法、蟻群算法、模擬退火算法等智能算法用于求解網(wǎng)絡(luò)可靠度的優(yōu)化問題，并比較以上算法的優(yōu)缺點(diǎn)。近似方法降低了精確分析法對(duì)于分析現(xiàn)實(shí)網(wǎng)絡(luò)中存在的計(jì)算效率低的問題，但是由于仿真可能造成的偏差以及評(píng)估方法中各種網(wǎng)絡(luò)系統(tǒng)的差異性，往往沒有辦法直接應(yīng)用到新型網(wǎng)絡(luò)技術(shù)上。

隨著網(wǎng)絡(luò)規(guī)模的逐漸擴(kuò)大，利用最小路集或者最小割集計(jì)算網(wǎng)絡(luò)可靠性時(shí)，計(jì)算過程會(huì)變得十分復(fù)雜，導(dǎo)致精確算法的效率急劇下降。這促使了新方法二元決策圖（Binary Decision Diagram，BDD）的出現(xiàn)。BDD 被認(rèn)為是一種高效存儲(chǔ)大型布爾術(shù)語的最先進(jìn)的數(shù)據(jù)結(jié)構(gòu)，由Akers［14］首先提出，Coudert 等人［15］最早將BDD 方法運(yùn)用到了可靠性分析當(dāng)中。實(shí)驗(yàn)表明利用BDD 計(jì)算網(wǎng)絡(luò)可靠性能夠大大提升分析性能［16］，并且所使用的內(nèi)存和計(jì)算時(shí)間要遠(yuǎn)少于其他分析技術(shù)。Hardy 等人［17］針對(duì)BDD 構(gòu)建過程中遇到冗余子圖的問題，提供了一種識(shí)別同構(gòu)子圖的高效識(shí)別方法，提高了BDD 的構(gòu)建速度。Yeh 等人［18］應(yīng)用邊拓展圖和有序二元決策圖相結(jié)合的技術(shù)完成了網(wǎng)絡(luò)的可靠性評(píng)估并大大減少了BDD的規(guī)模。

基于BDD 的網(wǎng)絡(luò)可靠性分析方法一般過程包括使用邊排序算法進(jìn)行排序、根據(jù)變量序構(gòu)建等價(jià)的BDD、網(wǎng)絡(luò)可靠度計(jì)算3個(gè)部分。其中，后2個(gè)部分的計(jì)算時(shí)間復(fù)雜度與BDD 的規(guī)模數(shù)量成多項(xiàng)式的關(guān)系，而BDD 的規(guī)模嚴(yán)重依賴于變量的排序。一個(gè)好的變量排序算法可以大大縮小BDD 的規(guī)模并加快BDD 的構(gòu)建時(shí)間和可靠度計(jì)算時(shí)間。然而，最優(yōu)排序的確定是一個(gè)NP 完全問題［19］，已知最佳變量排序算法的復(fù)雜度為Ο（n23n）。

現(xiàn)有的BDD 變量排序算法可分為啟發(fā)式排序算法和動(dòng)態(tài)排序算法。啟發(fā)式排序算法在構(gòu)建BDD 之前就給出所有變量的排序，而動(dòng)態(tài)排序算法在構(gòu)建過程中動(dòng)態(tài)調(diào)整BDD 變量的排序。通常，啟發(fā)式排序算法擁有更快的構(gòu)建時(shí)間，而動(dòng)態(tài)排序算法擁有更小的BDD規(guī)模。

本文的主要研究工作如下：

1）針對(duì)傳統(tǒng)BDD 排序方法構(gòu)建BDD 模型規(guī)模大和時(shí)間長的缺點(diǎn)，提出一種新的BDD 啟發(fā)式排序算法MP-BFS，實(shí)驗(yàn)結(jié)果表明MP-BFS 比現(xiàn)有經(jīng)典的啟發(fā)式排序算法構(gòu)建的BDD 模型擁有更少的節(jié)點(diǎn)數(shù)和更快的構(gòu)建時(shí)間。

2）針對(duì)現(xiàn)有研究對(duì)SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層可靠性分析不足的問題，本文提出一種SDN 可靠性評(píng)估算法BDD-SDN，對(duì)SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層面的可靠性進(jìn)行精確分析，在仿真環(huán)境下實(shí)現(xiàn)SDN 的網(wǎng)絡(luò)連通可靠性評(píng)估和仿真驗(yàn)證。

1 相關(guān)工作

由于最優(yōu)排序的計(jì)算屬于NP 完全問題，現(xiàn)有的變量排序方法可以分為2 類：動(dòng)態(tài)排序算法和啟發(fā)式排序算法。

動(dòng)態(tài)排序算法是基于交換相鄰變量的排序只會(huì)影響交換2層節(jié)點(diǎn)的思想，致力于獲得更小的BDD規(guī)模。其中由Rudell 提出的篩選算法被視為動(dòng)態(tài)排序中的經(jīng)典算法［8］，其通過利用貪婪算法調(diào)整已經(jīng)提前隨機(jī)生成或者利用啟發(fā)式排序算法生成的變量序，從而減小BDD 的規(guī)模，通常可以找到一個(gè)規(guī)模比較小的變量序。Li 等人［20］在基于變量交換的基礎(chǔ)上提出了一種雙向快速重排序算法，可以按照從后向前和從前向后2 個(gè)方向上同時(shí)執(zhí)行變量交換來尋找變量最佳排序。Kumar 等人［21］通過采用遺傳算法來不斷優(yōu)化變量序，算法將每個(gè)變量序看作一條染色體并通過不斷交叉和編譯來選取最優(yōu)的變量序，并且該算法的初始變量序可以不基于任何之前已有的啟發(fā)式排序算法。Awad等人［22］提出了一種基于元啟發(fā)式的優(yōu)化器來優(yōu)化BDD，該優(yōu)化器的核心是基于遺傳算法和粒子群算法，基于遺傳算法的BDD 重排優(yōu)化器通過交叉、變異算子的隨機(jī)混合來迭代地處理種群，基于群的優(yōu)化器將實(shí)數(shù)向量映射到排列中，以進(jìn)一步構(gòu)建BDD。實(shí)驗(yàn)結(jié)果表明，該優(yōu)化器可以幾乎達(dá)到線性的計(jì)算復(fù)雜度來有效地減小BDD的大小。

基于動(dòng)態(tài)排序算法得到的BDD 規(guī)模通常要小于啟發(fā)式排序算法得到的BDD 規(guī)模，但是通常非常耗時(shí)。網(wǎng)絡(luò)可靠性評(píng)估中通常選擇構(gòu)建時(shí)間更短的啟發(fā)式排序算法，其中，廣度優(yōu)先搜索BFS、深度優(yōu)先搜索DFS 被廣泛應(yīng)用于尋找變量序［17-18，24］。BFS 從源節(jié)點(diǎn)開始，訪問其所有相關(guān)聯(lián)的邊，然后依次從邊相連的節(jié)點(diǎn)繼續(xù)訪問，直到所有的邊和節(jié)點(diǎn)被訪問。然后按照遍歷過程中邊的出現(xiàn)順序，進(jìn)行變量的排序。DFS 從源結(jié)點(diǎn)開始，訪問一條相關(guān)聯(lián)的邊，然后從該相連節(jié)點(diǎn)依次訪問，直到所有的邊和節(jié)點(diǎn)被訪問。此時(shí)，變量的排序就是遍歷過程中邊出現(xiàn)的順序。Du等人［24］提出了一種漸進(jìn)排序算法，在BDD 頂點(diǎn)的每個(gè)分支上進(jìn)行不同的變量排序，雖然不能保證BDD的結(jié)構(gòu)唯一，但是有更高的機(jī)會(huì)產(chǎn)生更小的BDD，并且與經(jīng)典算法產(chǎn)生的BDD 具有相同的屬性。潘竹生等人［25］利用邊界集的思想，提出了一種新的“邊界長度”概念，并設(shè)計(jì)了一種基于邊界長度的邊排序策略，在變量排序過程中盡可能地保持最小邊界長度，這種算法可以產(chǎn)生較好的BDD 規(guī)模并且可以為特定的網(wǎng)絡(luò)邊排序提供重要的參考依據(jù)。在文獻(xiàn)［26］中作者基于Hardy 的分解算法，得到了一種動(dòng)態(tài)排序啟發(fā)式算法，適用于各種網(wǎng)絡(luò)結(jié)構(gòu)，并且在不規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)下可以產(chǎn)生規(guī)模更小的BDD。

綜上所述，當(dāng)前的動(dòng)態(tài)排序算法通常基于變量的交換去動(dòng)態(tài)調(diào)整BDD 規(guī)模，從而尋找更小的BDD 規(guī)模，通常這種算法可以得到構(gòu)建規(guī)模更優(yōu)的BDD，然而通常是十分耗時(shí)的，不利于網(wǎng)絡(luò)可靠性的快速評(píng)估，而當(dāng)前的啟發(fā)式排序算法通常是在構(gòu)建BDD 之前就會(huì)確定變量的排序，并利用該排序快速構(gòu)建BDD，可以更快地完成網(wǎng)絡(luò)的可靠性評(píng)估。本文在BFS 算法基礎(chǔ)上，提出一種名為最小路集-廣度優(yōu)先搜索排序算法（Minimal Path set Breadth-first Search algorithm，MP-BFS）。該算法在保留BFS 算法優(yōu)點(diǎn)的基礎(chǔ)上，通過對(duì)BFS遍歷時(shí)相同層次的變量進(jìn)行統(tǒng)計(jì)排序，優(yōu)先記錄每層出現(xiàn)次數(shù)更多的變量，以此得到一個(gè)更優(yōu)的變量排序；并將改進(jìn)的BDD 方法應(yīng)用于SDN 可靠性評(píng)估中，提出了一種SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層可靠性評(píng)估算法，名為BDD-SDN。實(shí)驗(yàn)結(jié)果表明，本文提出的MP-BFS算法可以明顯縮小BDD的構(gòu)建規(guī)模，更快地完成BDD 的構(gòu)建，使用BDD-SDN網(wǎng)絡(luò)可靠性評(píng)估算法，可對(duì)SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層面進(jìn)行快速、精確的可靠性分析。

2 基于SDN的網(wǎng)絡(luò)可靠性評(píng)估架構(gòu)

本文設(shè)計(jì)的基于SDN 的網(wǎng)絡(luò)可靠性評(píng)估架構(gòu)如圖1所示，由邏輯集中的控制器、OpenFlow交換機(jī)以及網(wǎng)絡(luò)可靠性評(píng)估機(jī)制組成?？刂破魍ㄟ^OpenFlow等協(xié)議管理底層的交換機(jī)，本文提出的SDN網(wǎng)絡(luò)可靠性評(píng)估方法作為運(yùn)行在應(yīng)用層的可靠性評(píng)估機(jī)制實(shí)現(xiàn)。

圖1 基于SDN的網(wǎng)絡(luò)可靠性評(píng)估架構(gòu)

可靠性評(píng)估機(jī)制主要由4 個(gè)功能模塊構(gòu)成，分別是拓?fù)涔芾砟K、路徑計(jì)算模塊、BDD 構(gòu)建模塊和可靠性評(píng)估模塊。

拓?fù)涔芾砟K主要負(fù)責(zé)根據(jù)當(dāng)前網(wǎng)絡(luò)設(shè)備發(fā)現(xiàn)管理和鏈路發(fā)現(xiàn)管理中信息的獲取，維護(hù)當(dāng)前的拓?fù)浣Y(jié)構(gòu)，當(dāng)發(fā)現(xiàn)鏈路信息的連接、斷開或者主機(jī)信息的連接、斷開時(shí)，及時(shí)更新網(wǎng)絡(luò)拓?fù)?。路徑?jì)算模塊主要負(fù)責(zé)計(jì)算源節(jié)點(diǎn)交換機(jī)到目的節(jié)點(diǎn)交換機(jī)的最小路集。最小路集指的是從源節(jié)點(diǎn)到目的節(jié)點(diǎn)無環(huán)路的所有路徑集合。BDD 構(gòu)建模塊主要負(fù)責(zé)將最小路徑轉(zhuǎn)化為布爾函數(shù)，然后根據(jù)本文提出的MP-BFS 算法計(jì)算出變量排序，最后根據(jù)變量排序構(gòu)建BDD?？煽啃栽u(píng)估模塊主要負(fù)責(zé)將構(gòu)建好的BDD 進(jìn)行可靠性計(jì)算，以完成整體SDN的可靠度評(píng)估。

本文對(duì)SDN 網(wǎng)絡(luò)可靠性進(jìn)行定量分析時(shí)基于以下假設(shè)：

1）網(wǎng)絡(luò)中的節(jié)點(diǎn)是無故障的，只可能發(fā)生鏈路故障。

2）網(wǎng)絡(luò)中的鏈路只有2 種狀態(tài)：正常工作和故障，每條鏈路故障統(tǒng)計(jì)相互獨(dú)立且故障概率已知。

3）交換機(jī)與主機(jī)之間的鏈路是無故障的，主機(jī)可以與交換機(jī)正常通信。

SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層可被表示為一個(gè)無向圖G=（V，E），V表示圖中的節(jié)點(diǎn)集合，E表示圖中的鏈路集合，令M=|V|表示無向圖中的節(jié)點(diǎn)數(shù)目，N=|E|表示圖中的鏈路數(shù)目，每條鏈路ei∈E均可能以概率（1.0-pi）失效，其中pi∈［0，1］是鏈路ei的可用概率，也被稱為鏈路ei的可用性。本文中網(wǎng)絡(luò)可靠性被定義為從源節(jié)點(diǎn)到目的節(jié)點(diǎn)網(wǎng)絡(luò)連通的概率。令x=（x1，x2，…，xN）表示當(dāng)前網(wǎng)絡(luò)中所有鏈路的連接狀態(tài)，當(dāng)xi=0時(shí)表示鏈路發(fā)生故障，否則，表示鏈路正常工作。網(wǎng)絡(luò)可靠性可被表示為式（1）：

其中，f（x）是一個(gè)N元的布爾函數(shù)，當(dāng)網(wǎng)絡(luò)連通時(shí)f（x）=1；否則f（x）=0。

3 基于改進(jìn)BDD的SDN可靠性評(píng)估算法

3.1 最小路集-廣度優(yōu)先搜索算法

BDD 是布爾函數(shù)的圖表示形式，是一個(gè)通過對(duì)布爾函數(shù)利用香農(nóng)分解而生成的有向無環(huán)圖（Directed Acyclic Graph，DAG）。對(duì)于布爾函數(shù)f（x），香農(nóng)分解定義如公式（2）［14］：

其中，xi是布爾函數(shù)f的一個(gè)布爾變量，表示xi=1時(shí)計(jì)算的f（x）。通過選擇變量的順序，遞歸地運(yùn)用香農(nóng)分解公式，任何布爾表達(dá)式的真值表都可以用圖形表示為二叉樹的形式。DAG 中有2 種類型的節(jié)點(diǎn)和2 種類型的邊組成，沒有輸出邊的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)，一個(gè)BDD 只有2 個(gè)葉子節(jié)點(diǎn)，分別用0-葉子結(jié)點(diǎn)和1-葉子節(jié)點(diǎn)表示，表示2個(gè)相應(yīng)的常量表達(dá)式。非葉子節(jié)點(diǎn)有2條輸出邊，用high 和low 表示，節(jié)點(diǎn)用相應(yīng)的布爾變量xi標(biāo)記，high 邊指向xi=1 時(shí)的布爾函數(shù)，low邊指向xi=0時(shí)的布爾函數(shù)。

BDD 變量的排序很大程度上決定了BDD 的規(guī)模，一個(gè)好的變量排序算法可以大大縮小BDD 的規(guī)模，加快BDD 的構(gòu)建時(shí)間和可靠度計(jì)算時(shí)間。為此，本文提出一種基于最小路集的啟發(fā)式變量排序算法，名為最小路集-廣度優(yōu)先搜索排序算法。具體過程如算法1所示。其中，源節(jié)點(diǎn)s到目的節(jié)點(diǎn)t的最小路集為Lmini={L1，L2，…，Lm}，m表示最小路徑的數(shù)量。算法流程描述如下：

步驟1 將最小路集Lmini中的每條最小路徑Li的同層鏈路進(jìn)行記錄，同層鏈路指的是廣度優(yōu)先搜索時(shí)屬于同一層次的鏈路，如果此時(shí)Li的同層鏈路已經(jīng)被記錄，那么就對(duì)其計(jì)數(shù)加1，否則，將其計(jì)數(shù)記為1。

步驟2 使用快速排序算法對(duì)記錄中的鏈路按照其計(jì)數(shù)的大小進(jìn)行從大到小的排序。

步驟3 對(duì)變量序列表進(jìn)行檢查，如果當(dāng)前計(jì)數(shù)最多的鏈路對(duì)應(yīng)的變量不在變量序列之中，則將其對(duì)應(yīng)的變量加入變量序列中，依次檢查剩余鏈路，直至當(dāng)前鏈路對(duì)應(yīng)的變量均已加入到變量序列中。

步驟4 對(duì)當(dāng)前變量序列長度進(jìn)行檢查，當(dāng)所有鏈路對(duì)應(yīng)的變量均加入變量序列之后，算法結(jié)束，輸出變量排序π（x1，x2，…，xN），否則，跳轉(zhuǎn)到步驟1選取下一層次的鏈路進(jìn)行統(tǒng)計(jì)信息記錄。

計(jì)算過程中如果有相同計(jì)數(shù)的變量，則根據(jù)計(jì)數(shù)的順序?qū)⒆兞恳来渭尤氲阶兞啃蛄斜碇小?/p>

算法1 MP-BFS算法

輸入：最小路集Lmini

輸出：x1，x2，…，xN變量序列表list

1：i←0 2：list=［］

3：whilei

4：Dict={} /*用于記錄當(dāng)前層次變量的數(shù)目*/

5：for route in L_mini do /*步驟1 遍歷當(dāng)前層次變量，統(tǒng)計(jì)計(jì)數(shù)*/

6：if route［i］in Dict then

7：Dict［route［i］］←Dict［route［i］］+1

8：else Dict［route［i］］←1

9：sort（Dict）by the count /*步驟2 快速排序求得變量順序*/

10：forkin Dict.key（）do /*步驟3添加到結(jié)果列表list中*/

11：ifknot in list then

12：kappend to list

13：if length（list）==N then /*步驟4檢查list中變量個(gè)數(shù)*/

14：break

15：elsei←i+ 1

該算法的思想是基于BFS 排序的，在BFS 排序過程中，僅按照出隊(duì)順序?qū)ψ兞窟M(jìn)行排序，而沒有考慮同層變量在最小路集中的出現(xiàn)頻率，因此，本文將同層變量出現(xiàn)的頻率進(jìn)行統(tǒng)計(jì)排序，并按照從高到低的順序進(jìn)行變量排序。實(shí)驗(yàn)結(jié)果表明，本文提出的啟發(fā)式排序算法優(yōu)于傳統(tǒng)的BFS排序算法和DFS排序算法。

3.2 SDN可靠性評(píng)估算法

當(dāng)BDD 構(gòu)建成功之后，可以在BDD 上采用遞歸的方式從下至上地進(jìn)行可靠性的計(jì)算?？煽啃缘挠?jì)算采用公式（2）的香農(nóng)分解方法，由于和的互斥性，可以將公式（1）分解為公式（3）：

因此，布爾函數(shù)f（x）對(duì)應(yīng)的BDD 可靠性計(jì)算如式（4）：

其中，root 表示BDD 中的根節(jié)點(diǎn)變量，high（root）表示根節(jié)點(diǎn)對(duì)應(yīng)high 邊指向的節(jié)點(diǎn)，low（root）表示根節(jié)點(diǎn)對(duì)應(yīng)low 邊指向的節(jié)點(diǎn)，pi是變量對(duì)應(yīng)的邊的可用概率，1-葉子結(jié)點(diǎn)對(duì)應(yīng)可靠性為1，而0-葉子結(jié)點(diǎn)對(duì)應(yīng)可靠性為0。通過自下而上的遞歸方式，可以計(jì)算出從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)t的連通可靠性。

為了對(duì)SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層進(jìn)行精確、高效的可靠性評(píng)估，本文提出一種基于改進(jìn)BDD 的SDN 可靠性評(píng)估算法，名為BDD-SDN 算法。具體過程如算法2所示，算法的輸入為SDN 拓?fù)鋱D、源節(jié)點(diǎn)s、目的節(jié)點(diǎn)t，算法的輸出為SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層的可靠度。算法流程描述如下：

步驟1 SDN控制器通過LLDP協(xié)議監(jiān)控?cái)?shù)據(jù)平面的鏈路狀態(tài)，將狀態(tài)信息存儲(chǔ)到當(dāng)前網(wǎng)絡(luò)信息庫中，拓?fù)涔芾砀鶕?jù)當(dāng)前網(wǎng)絡(luò)信息庫中信息，維護(hù)當(dāng)前的拓?fù)浣Y(jié)構(gòu)，為可靠性評(píng)估和路由路徑的計(jì)算提供拓?fù)湫畔ⅰ?/p>

步驟2 路徑計(jì)算模塊根據(jù)當(dāng)前數(shù)據(jù)轉(zhuǎn)發(fā)層的拓?fù)湫畔⒑蛿?shù)據(jù)包的源節(jié)點(diǎn)和目的節(jié)點(diǎn)計(jì)算最小路集。

步驟3 將最小路徑中的最小路徑轉(zhuǎn)換為對(duì)應(yīng)的布爾函數(shù)表示形式。

步驟4 使用算法1計(jì)算出從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的變量排序。

步驟5 運(yùn)用步驟4 得到的BDD 變量序和香農(nóng)分解公式（2），將步驟3 得到的布爾函數(shù)表示為源節(jié)點(diǎn)到目的節(jié)點(diǎn)的BDD。

步驟6 根據(jù)構(gòu)造的BDD 以及目標(biāo)網(wǎng)絡(luò)中鏈路的可用概率，利用公式（4）在可靠性評(píng)估模塊中采用自底向上的遞歸方式計(jì)算源節(jié)點(diǎn)到目的節(jié)點(diǎn)的可靠度，實(shí)現(xiàn)對(duì)SDN的可靠性評(píng)估。

算法2 BDD-SDN算法

輸入：SDN拓?fù)鋱D、源節(jié)點(diǎn)s、目的節(jié)點(diǎn)t

輸出：SDN可靠度

1：V=getMessage（SDN topo，node）/*獲取SDN節(jié)點(diǎn)集合*/

2：E=getMessage（SDN topo，link）/*獲取SDN鏈路集合*/

3：（p1，p2，…，pN）=getMessage（SDN topo，prob） /*獲取SDN鏈路可用概率集合*/

4：Lmini=get minimal path sets /*獲取最小路集*/

5：f（x）=transform（Lmini）/*將最小路集轉(zhuǎn)換為對(duì)應(yīng)布爾函數(shù)*/

6：π（x1，x2，…，xN）=use algorithm 1 to calculate the variable ordering

7：BDD=Shannon’s decomposition（f（x），π（x1，x2，…，

8：Rel（f）= use equation（4）to calculate the reliability

3.3 算法時(shí)間復(fù)雜度分析

本文用變量N表示SDN 拓?fù)渲羞叺臄?shù)量，變量M表示SDN 拓?fù)渲薪粨Q機(jī)節(jié)點(diǎn)的數(shù)量，變量k表示最小路集中的路徑數(shù)量，變量p表示最小路集中變量的數(shù)量，則MP-BFS 算法時(shí)間復(fù)雜度為O（k（kp+nlogn）），其中，O（kp）是統(tǒng)計(jì)層次變量的時(shí)間復(fù)雜度，O（nlogn）是快速排序的時(shí)間復(fù)雜度。

4 SDN可靠性評(píng)估示例和實(shí)驗(yàn)仿真

4.1 可靠性評(píng)估示例

以圖2所示的SDN 拓?fù)鋱D為例進(jìn)行說明，拓?fù)渲墟溌肪幪?hào)根據(jù)控制器檢測(cè)到鏈路的順序依次生成，其中與主機(jī)h1相連的交換機(jī)s1為源結(jié)點(diǎn)，與主機(jī)h2相連的交換機(jī)s6為目的節(jié)點(diǎn)，在所有邊的可用概率都為0.9的條件下，計(jì)算SDN網(wǎng)絡(luò)可靠性。具體計(jì)算步驟如下：

圖2 SDN示例拓?fù)鋱D

步驟1 根據(jù)深度優(yōu)先搜索算法得到交換機(jī)s1到交換機(jī)s6的最小路集L={x1x6，x2x3x4x7，x2x3x8，x2x5}。

步驟2 將最小路集L中的最小路徑轉(zhuǎn)換為對(duì)應(yīng)布爾函數(shù)得到f（x）=x1·x6+x2·x3·x4·x7+x2·x3·x8+x2·x5。

步驟3 根據(jù)本文提出的最小路集-廣度優(yōu)先搜索排序算法，x1與x2屬于同層變量，由于x2出現(xiàn)次數(shù)比較多，共出現(xiàn)了3次，x1僅出現(xiàn)一次，因此應(yīng)該將x2、x1依次加入變量序列表中，繼續(xù)考慮下一層變量，發(fā)現(xiàn)x6、x3、x5這3 個(gè)變量，其中x3出現(xiàn)2 次，x5與x6僅出現(xiàn)1 次，x3優(yōu)先加入變量序列表，而x6、x5出現(xiàn)次數(shù)相同，按照順序先入的規(guī)則加入變量序列表，最后按照算法依次加入x4、x8、x7，求得此時(shí)整個(gè)網(wǎng)絡(luò)中的變量排序?yàn)椋簒2

步驟4 根據(jù)布爾函數(shù)f（x）以及當(dāng)前變量序，按照公式（2）進(jìn)行構(gòu)建的BDD，以及利用公式（4）進(jìn)行可靠性計(jì)算的結(jié)果如圖3 所示。可以看到，在當(dāng)前SDN數(shù)據(jù)層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及邊的可用概率為0.9的條件下，網(wǎng)絡(luò)可靠性為0.978998。

圖3 示例拓?fù)湎碌目煽啃栽u(píng)估結(jié)果

4.2 實(shí)驗(yàn)仿真

本文通過Mininet 和Ryu 控制器來模擬SDN 網(wǎng)絡(luò)環(huán)境，使用C++和Colorado大學(xué)開發(fā)的CUDD-3.0.0工具包［27］完成BDD 的構(gòu)建和可靠性計(jì)算。程序運(yùn)行環(huán)境為Ubuntu 18.04.6 LTS，Intel Core i7-10700 CPU，2.90 GHz，8 GB內(nèi)存。

實(shí)驗(yàn)網(wǎng)絡(luò)如圖4 所示，其中包括了許多應(yīng)用于網(wǎng)絡(luò)可靠性分析論文中的網(wǎng)絡(luò)［26，28-29］，常被用來檢驗(yàn)算法的有效性和可行性。網(wǎng)絡(luò)中通信節(jié)點(diǎn)用黑色標(biāo)記，并用s表示源節(jié)點(diǎn)，用t表示目的節(jié)點(diǎn)，假設(shè)各鏈路的可用概率為0.9。本文在SDN網(wǎng)絡(luò)架構(gòu)下的數(shù)據(jù)轉(zhuǎn)發(fā)層進(jìn)行可靠性分析。

圖4 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)鋱D

下面從3 個(gè)指標(biāo)：BDD 規(guī)模大小、BDD 構(gòu)建時(shí)間和可靠性評(píng)估時(shí)間，來比較2 種經(jīng)典啟發(fā)式排序方法BFS和DFS，以及本文提出的MP-BFS算法，對(duì)比結(jié)果分別用圖5～圖7表示。從對(duì)比結(jié)果可以看出，傳統(tǒng)排序算法中BFS 排序在所有實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)渲芯鶅?yōu)于DFS 排序算法，并且在拓?fù)? 中使用DFS 獲得的BDD共有3015 個(gè)節(jié)點(diǎn)，是BFS 排序算法的得到BDD 大小的28 倍。本文算法僅在拓?fù)? 和拓?fù)? 與BFS 算法有相等的BDD 大小，在其余實(shí)驗(yàn)圖中均優(yōu)于DFS 和BFS 排序算法構(gòu)建的BDD，相比于DFS 算法和BFS 算法構(gòu)建的規(guī)模平均縮小了56%和21%，而在拓?fù)? 中本文構(gòu)建的BDD大小只有BFS算法的49%。從構(gòu)建時(shí)間來看，本文算法相比DFS算法和BFS算法分別減少了37%和9%，可靠性計(jì)算時(shí)間分別減少了57%和19%。綜上所述，本文提出的最小路集-廣度優(yōu)先搜索排序算法有著更好的效率和性能，在構(gòu)建BDD規(guī)模、構(gòu)建時(shí)間、可靠性計(jì)算時(shí)間算法均有著不同程度的改善。

圖5 BDD規(guī)模

圖6 BDD構(gòu)建時(shí)間

圖7 可靠性評(píng)估時(shí)間

表1 是SDN 環(huán)境下的可靠性評(píng)估和實(shí)驗(yàn)仿真結(jié)果。其中，“網(wǎng)絡(luò)拓?fù)洹北硎緦?shí)驗(yàn)網(wǎng)絡(luò)的編號(hào)；“節(jié)點(diǎn)數(shù)”表示實(shí)驗(yàn)網(wǎng)絡(luò)中的交換機(jī)的數(shù)目；“鏈路數(shù)”表示實(shí)驗(yàn)網(wǎng)絡(luò)中的鏈路數(shù)目；“最小路徑數(shù)”表示實(shí)驗(yàn)網(wǎng)絡(luò)中從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小路徑數(shù)目；“可靠性”指的是當(dāng)前網(wǎng)絡(luò)的可靠性分析精確值。

表1 SDN可靠性評(píng)估結(jié)果

實(shí)驗(yàn)結(jié)果表明，在SDN 網(wǎng)絡(luò)中基于BDD 的可靠性分析方法是一種快速、有效的連通可靠性分析方法，可以快速對(duì)SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層的網(wǎng)絡(luò)進(jìn)行可靠性評(píng)估，計(jì)算出從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的可靠性。

5 結(jié)束語

本文提出了一種新的BDD 啟發(fā)式排序算法MPBFS，相比于傳統(tǒng)的BFS 和DFS 算法，在BDD 構(gòu)建規(guī)模、構(gòu)建時(shí)間上均有所減少，是一種快速、有效的啟發(fā)式排序算法。同時(shí)，在新型網(wǎng)絡(luò)架構(gòu)SDN 基礎(chǔ)上，基于改進(jìn)的BDD 可靠性評(píng)估算法BDD-SDN，對(duì)SDN 數(shù)據(jù)轉(zhuǎn)發(fā)層進(jìn)行了可靠性評(píng)估，實(shí)現(xiàn)了SDN 網(wǎng)絡(luò)的連通可靠性分析和仿真驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，BDDSDN算法是一種精確、高效的可靠性評(píng)估方法，應(yīng)用于SDN數(shù)據(jù)轉(zhuǎn)發(fā)層面的可靠性評(píng)估時(shí)有著很好的效率。