肖軍弼，孟祥澤+，田愛(ài)寶，陳 松

(1.中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與科學(xué)技術(shù)學(xué)院，山東 青島 266580； 2.中國(guó)石油大學(xué)(華東) 信息化建設(shè)處，山東 青島 266580)

0 引 言

近年來(lái)，互聯(lián)網(wǎng)業(yè)務(wù)不斷擴(kuò)大，物聯(lián)網(wǎng)、云計(jì)算等新興領(lǐng)域快速發(fā)展，網(wǎng)絡(luò)業(yè)務(wù)的繁雜和傳統(tǒng)網(wǎng)絡(luò)架構(gòu)的短板為網(wǎng)絡(luò)服務(wù)的運(yùn)行和維護(hù)帶來(lái)了巨大難題[1]。為解決傳統(tǒng)網(wǎng)絡(luò)中故障恢復(fù)時(shí)間過(guò)長(zhǎng)的問(wèn)題，探索新的網(wǎng)絡(luò)架構(gòu)及運(yùn)行模式，給業(yè)務(wù)提供優(yōu)質(zhì)可靠的運(yùn)行環(huán)境。研究重點(diǎn)利用SDN(software defined networking)[2]架構(gòu)的強(qiáng)大管控優(yōu)勢(shì)，收集鏈路信息，快速定位鏈路故障，并改進(jìn)故障恢復(fù)的方法，減少故障恢復(fù)所需時(shí)間并提高網(wǎng)絡(luò)的服務(wù)質(zhì)量[3]。相比于傳統(tǒng)網(wǎng)絡(luò)中生成樹協(xié)議STP(spanning tree protocol)或快速生成樹協(xié)議RSTP(rapid spanning tree protocol)[4]復(fù)雜、僵化的恢復(fù)方案，能夠?qū)崟r(shí)監(jiān)控網(wǎng)絡(luò)狀態(tài)，并在第一時(shí)間對(duì)故障進(jìn)行自愈操作，保障業(yè)務(wù)的正常運(yùn)行，降低故障恢復(fù)時(shí)間，提高網(wǎng)絡(luò)通信安全和服務(wù)質(zhì)量。本文的主要內(nèi)容包含如下兩個(gè)方面：

(1)針對(duì)SDN網(wǎng)絡(luò)中流表數(shù)量過(guò)多、冗余鏈路計(jì)算復(fù)雜的問(wèn)題，本文研究UGLA算法，將拓?fù)渲械沫h(huán)路劃分成單獨(dú)的環(huán)路域，環(huán)路域內(nèi)部依靠MPLS標(biāo)簽匹配基礎(chǔ)流表轉(zhuǎn)發(fā)，實(shí)現(xiàn)故障恢復(fù)主備份路徑策略，降低交換機(jī)中的流表數(shù)量。

(2)為保障業(yè)務(wù)的服務(wù)質(zhì)量，在劃分出環(huán)路域的基礎(chǔ)之上，對(duì)環(huán)路域之間的邏輯鏈路進(jìn)行鏈路評(píng)估，計(jì)算域間最優(yōu)轉(zhuǎn)發(fā)路徑，結(jié)合環(huán)路域內(nèi)部的基礎(chǔ)轉(zhuǎn)發(fā)流表，保證故障恢復(fù)通信的低丟包率、低延遲、高轉(zhuǎn)發(fā)速率，保障業(yè)務(wù)正常運(yùn)行。

1 相關(guān)工作

由于涉及整個(gè)網(wǎng)絡(luò)的協(xié)調(diào)，傳統(tǒng)的分布式網(wǎng)絡(luò)難以捕獲細(xì)粒度狀態(tài)，而現(xiàn)代網(wǎng)絡(luò)的動(dòng)態(tài)特性又使得獲取網(wǎng)絡(luò)拓?fù)湫畔⒂葹槔щy。因此，科學(xué)有效管理網(wǎng)絡(luò)的重要性日益凸顯，獲取準(zhǔn)確的網(wǎng)絡(luò)拓?fù)鋵?duì)于網(wǎng)絡(luò)交換機(jī)、體系結(jié)構(gòu)和協(xié)議的設(shè)計(jì)至關(guān)重要[5]。

Zhangchao W等[6]針對(duì)分布式網(wǎng)絡(luò)結(jié)構(gòu)難以捕獲的問(wèn)題，通過(guò)簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議(simple network management protocol，SNMP)監(jiān)控網(wǎng)絡(luò)設(shè)備的性能，解決了由于不同廠商生產(chǎn)的底層設(shè)備產(chǎn)生的兼容性問(wèn)題，實(shí)現(xiàn)設(shè)備的集中統(tǒng)一管理。趙偉等[7]采用LLDP協(xié)議(link layer discovery protocol，LLDP)為與其直接相鄰的設(shè)備提供鄰居信息，解決了利用MIB生成網(wǎng)絡(luò)拓?fù)浯嬖谡`差的問(wèn)題，增強(qiáng)了拓?fù)滏溌窢顟B(tài)獲取的實(shí)時(shí)性。Huang H等[8]將BFD檢測(cè)狀態(tài)與OpenFlow組表相結(jié)合，一旦BFD協(xié)議檢測(cè)到鏈路故障，OpenFlow協(xié)議就會(huì)根據(jù)故障狀態(tài)執(zhí)行相應(yīng)的動(dòng)作，但該方法缺乏對(duì)故障主動(dòng)檢測(cè)能力。

Zhao G等[9,10]在SDN架構(gòu)中利用控制器的集中控制功能，可以準(zhǔn)確發(fā)現(xiàn)故障點(diǎn)，根據(jù)故障節(jié)點(diǎn)所在位置，進(jìn)行重路由，繞過(guò)故障節(jié)點(diǎn)，但該方法存在故障流量匹配項(xiàng)過(guò)多，不易處理的問(wèn)題。針對(duì)網(wǎng)絡(luò)規(guī)模擴(kuò)大，故障標(biāo)記不易區(qū)分的問(wèn)題，黃睿等[11,12]將大規(guī)模網(wǎng)絡(luò)根據(jù)接入、匯聚和核心劃分出不同的區(qū)域，區(qū)域內(nèi)采用不同的恢復(fù)策略，鏈路故障時(shí)通過(guò)重路由方式恢復(fù)，鏈路擁塞時(shí)通過(guò)QoS降低數(shù)據(jù)丟包率。為降低控制器重新計(jì)算轉(zhuǎn)發(fā)路徑的時(shí)間，居建濤等[13]在SDN網(wǎng)絡(luò)中計(jì)算出數(shù)據(jù)流轉(zhuǎn)發(fā)節(jié)點(diǎn)的備份路徑，同時(shí)在鏈路故障時(shí)切換流表優(yōu)先級(jí)，實(shí)現(xiàn)快速繞行轉(zhuǎn)發(fā)。該方法提前計(jì)算好轉(zhuǎn)發(fā)路徑，以主備份形式存儲(chǔ)于交換機(jī)中，降低了中斷時(shí)間。為了進(jìn)一步降低中斷時(shí)間，Van Adrichem N.L.M等[14,15]制定傳輸策略，數(shù)據(jù)流在鏈路上正常傳輸時(shí)不做處理，當(dāng)鏈路發(fā)生故障時(shí)，OpenFlow故障恢復(fù)組表自動(dòng)切換到備份路徑轉(zhuǎn)發(fā)，此過(guò)程不需要控制器參與，解決了故障恢復(fù)過(guò)程中通信中斷的問(wèn)題，但主備份路徑需要提前規(guī)劃，需要一個(gè)最優(yōu)的路徑計(jì)算方法來(lái)制定轉(zhuǎn)發(fā)策略。

基于上述分析，目前的故障恢復(fù)研究盡管已經(jīng)取得了諸多成就，但在檢測(cè)精度、故障分類和故障恢復(fù)質(zhì)量上仍存在問(wèn)題。本文采用SDN架構(gòu)實(shí)施對(duì)SDN網(wǎng)絡(luò)的故障恢復(fù)，當(dāng)鏈路出現(xiàn)故障時(shí)，采用OpenFlow協(xié)議的故障恢復(fù)組表功能，結(jié)合BFD和LLDP兩種鏈路檢測(cè)協(xié)議進(jìn)行檢測(cè)鏈路故障，實(shí)現(xiàn)對(duì)故障位置的精確定位。在故障類型分類部分采用分域治之的方式，將大規(guī)模網(wǎng)絡(luò)分解成可實(shí)現(xiàn)故障恢復(fù)的環(huán)路，在環(huán)路內(nèi)實(shí)施主備份策略，對(duì)故障流量精確分類。故障恢復(fù)部分采用OpenFlow組表和SDN控制器聯(lián)合恢復(fù)的方法，將已發(fā)出的數(shù)據(jù)包做回溯轉(zhuǎn)發(fā)，減少丟包率，然后利用控制器修改流表優(yōu)先級(jí)，實(shí)現(xiàn)控制器和OpenFlow聯(lián)合恢復(fù)流量轉(zhuǎn)發(fā)，降低故障流量轉(zhuǎn)發(fā)延時(shí)，提高網(wǎng)絡(luò)健壯性。

2 基于拓?fù)浞钟虻墓收匣謴?fù)方法

2.1 網(wǎng)絡(luò)分域

作為SDN網(wǎng)絡(luò)架構(gòu)的特性，控制和數(shù)據(jù)平面分離解決了網(wǎng)絡(luò)中彈性不足和可擴(kuò)展性差等問(wèn)題，交換機(jī)轉(zhuǎn)發(fā)依賴于控制器正確和及時(shí)的配置。本文基于SDN的集中控制方法，研究并實(shí)現(xiàn)一種網(wǎng)絡(luò)拓?fù)洵h(huán)路計(jì)算方法無(wú)向圖環(huán)路算法(undirected graph loop algorithm，UGLA)，將網(wǎng)絡(luò)中的環(huán)路融合，提前計(jì)算轉(zhuǎn)發(fā)路徑并下發(fā)到交換機(jī)中，轉(zhuǎn)發(fā)策略分為環(huán)路內(nèi)轉(zhuǎn)發(fā)策略和環(huán)路間轉(zhuǎn)發(fā)策略。通過(guò)將轉(zhuǎn)發(fā)策略分為域內(nèi)轉(zhuǎn)發(fā)和域間轉(zhuǎn)發(fā)，極大降低了匹配項(xiàng)的復(fù)雜度，減少流表數(shù)量，提高交換機(jī)處理速率。

在當(dāng)前網(wǎng)絡(luò)架構(gòu)中，一般情況下網(wǎng)絡(luò)鏈路中都存在鏈路冗余。UGLA分域算法將當(dāng)前網(wǎng)絡(luò)拓?fù)渲械沫h(huán)路作為最小轉(zhuǎn)發(fā)單元，稱為環(huán)路域。通過(guò)計(jì)算域與域之間的轉(zhuǎn)發(fā)路徑，簡(jiǎn)化了復(fù)雜網(wǎng)絡(luò)，提高了計(jì)算效率。本文引入了最短路徑算法，計(jì)算一個(gè)拓?fù)渲械乃协h(huán)路，每個(gè)環(huán)路中包含的節(jié)點(diǎn)是組成最小環(huán)的必要節(jié)點(diǎn)。判斷環(huán)路的基本思想如下，在一個(gè)圖G中，若存在環(huán)路，則環(huán)路中的所有頂點(diǎn)的度大于或等于2。

步驟1 度為1的節(jié)點(diǎn)不能夠產(chǎn)生環(huán)路，首先刪除圖中所有度為1的節(jié)點(diǎn)和該節(jié)點(diǎn)所連接的邊，如果產(chǎn)生新的度為1的節(jié)點(diǎn)，則繼續(xù)刪除，刪除的節(jié)點(diǎn)按連接關(guān)系加入到轉(zhuǎn)發(fā)域中。

步驟2 選擇一個(gè)度為2的節(jié)點(diǎn)作為起始節(jié)點(diǎn)開始計(jì)算最小環(huán)路，度為2的節(jié)點(diǎn)至多只有一個(gè)環(huán)路。

步驟3 檢查剩余節(jié)點(diǎn)的度，若剩余圖中的所有節(jié)點(diǎn)的度都大于2，則將剩余的節(jié)點(diǎn)融合至一個(gè)環(huán)路域內(nèi)。

步驟4 若剩余圖中的所有節(jié)點(diǎn)的度存在等于2的，則以選擇的節(jié)點(diǎn)作為起始節(jié)點(diǎn)，斷掉兩條邊中的一條，以該條邊的對(duì)端頂點(diǎn)作為目的節(jié)點(diǎn)，計(jì)算最短路徑。若最短路徑存在，說(shuō)明該最短路徑能夠形成一個(gè)最小環(huán)路，可以進(jìn)行環(huán)路融合；若不存在最短路徑，說(shuō)明該節(jié)點(diǎn)只作為中間轉(zhuǎn)發(fā)節(jié)點(diǎn)，只要鄰居節(jié)點(diǎn)的度為2，就將該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)遞歸方式加入到同一轉(zhuǎn)發(fā)域中。計(jì)算完成后刪除該起始節(jié)點(diǎn)，并清除環(huán)路中的度為2的節(jié)點(diǎn)，重復(fù)步驟2到步驟4，直到所有節(jié)點(diǎn)都被訪問(wèn)。

步驟5 在環(huán)路域間建立連接，一個(gè)節(jié)點(diǎn)可以屬于多個(gè)不同的域，而域與域之間是否能夠建立連接，取決于域內(nèi)節(jié)點(diǎn)所包含域的集合是否包含對(duì)端域。

基于以上步驟，我們?cè)O(shè)計(jì)了一種基于最小環(huán)路的UGLA融合算法，如算法1所示。

算法1: 拓?fù)浞钟蛩惴?輸入: 拓?fù)鋱D信息G(V,E) 輸出: 域集合Domain (1)function E(V) (2) ifV.length == 1 then (3) return[e1,…,en]; //與節(jié)點(diǎn)V相連的邊 (4) else (5) return[e];//與節(jié)點(diǎn)v1,v2相連的邊 (6) end if (7)end function (8)function D(V) (9) result ← 0 (10) result ← result +E(V) (11) returnresult;//節(jié)點(diǎn)的度 (12)end function (13)function PRE-TREATED(G(V,E)) (14) result ← G(V,E) (15) for allv ∈ result.V do (16) if D(v) == 1 then (17) result → V.delete(v) (18) result → E.delete(E(v)) (19) end if (20) end for (21) returnresult (22)end function (23)function UGLA(G(V,E)) (24) Domain ← {} (25) V’ ← [];//已訪問(wèn)節(jié)點(diǎn) (26) whileV’.length < V.length do (27) v ← V.get(1) (28) if D(v) == 2 then (29) E.delete(E(v,v.dst)) (30) path=Dijkstra(v,v.dst) (31) end if (32) ifpath != 0 then (33) Domain.add(name,path.V) (34) V’.add(path.V) (35) end if (36) end while (37) returnDomain (38)end function

為了更直觀展示算法工作流程，下面將使用一個(gè)簡(jiǎn)單的示例對(duì)上述過(guò)程加以詳細(xì)的說(shuō)明。在圖1所示的拓?fù)渲?，總共?4臺(tái)交換機(jī)設(shè)備，根據(jù)圖中的連接關(guān)系可以得出該拓?fù)鋱D具有環(huán)路，進(jìn)行環(huán)路融合。該拓?fù)鋱D大致可以分為5個(gè)域，分別是{S1,S2}組成的轉(zhuǎn)發(fā)域Group1;{S3,S4,S5}組成的環(huán)路域Loop1;{S4,S5,S6,S7}組成的環(huán)路域Loop2;{S8,S9,S10}組成的轉(zhuǎn)發(fā)域Group2;{S11,S12,S13,S14}組成的環(huán)路域Loop3。下面按照5個(gè)域生成的計(jì)算步驟進(jìn)行詳細(xì)的說(shuō)明。

圖1 初始拓?fù)浣Y(jié)構(gòu)

首先根據(jù)步驟1，先檢查圖中所有度為1的節(jié)點(diǎn)，當(dāng)前拓?fù)鋱D中度為1的節(jié)點(diǎn)為S1，刪除掉該節(jié)點(diǎn)和邊，新產(chǎn)生了一個(gè)度為1的節(jié)點(diǎn)S2，繼續(xù)刪除S2節(jié)點(diǎn)和其直連的邊，并將S1和S2加入到一個(gè)轉(zhuǎn)發(fā)域Group1中，形成轉(zhuǎn)發(fā)域Group1，拓?fù)鋱D如圖2所示。

圖2 融合轉(zhuǎn)發(fā)域Group1

在刪除掉度為1的節(jié)點(diǎn)和邊后，拓?fù)鋱D中不存在度為1的節(jié)點(diǎn)，下面將開始計(jì)算環(huán)路。選擇度為2的節(jié)點(diǎn)作為起始節(jié)點(diǎn)開始計(jì)算包含該節(jié)點(diǎn)的最小環(huán)路，當(dāng)前選擇節(jié)點(diǎn)S3作為起始節(jié)點(diǎn)。根據(jù)步驟2～步驟4刪除S3-S5的連接，通過(guò)最短路徑算法求取S3-S5的最短路徑，最終求得路徑S3-S4-S5為最小路徑，因此將{S3,S4,S5}加入到一個(gè)環(huán)路域中，生成環(huán)路域Loop1，拓?fù)鋱D如圖3所示。

圖3 融合環(huán)路域Loop1

刪除節(jié)點(diǎn)S3和環(huán)路域中度為2的節(jié)點(diǎn)，進(jìn)行循環(huán)步驟2～步驟4的處理。選擇S4初始節(jié)點(diǎn)，經(jīng)過(guò)計(jì)算將{S4,S5,S6,S7}加入同一環(huán)路域，生成環(huán)路域Loop2，拓?fù)鋱D如圖4所示。

圖4 融合環(huán)路域Loop2

刪除初始節(jié)點(diǎn)S4，清理掉該環(huán)路域中度為2的節(jié)點(diǎn){S5,56}，由于清除完成后S7度為1，將S7清除并保留與S7直連節(jié)點(diǎn)S8的度進(jìn)行下面的計(jì)算。以S9為初始節(jié)點(diǎn)，斷掉S9-S8的鄰邊，計(jì)算S9-S8的最短路徑。經(jīng)過(guò)計(jì)算，S9到S8不存在最短路徑，說(shuō)明未形成環(huán)路，將S9刪除，并同步刪除新產(chǎn)生度為1的節(jié)點(diǎn){S8,S10}，至此{(lán)S8,S9,S10}加入到轉(zhuǎn)發(fā)域中，產(chǎn)生轉(zhuǎn)發(fā)域Group2，生成的拓?fù)鋱D如圖5所示。

圖5 融合轉(zhuǎn)發(fā)域Group2

前面的步驟已訪問(wèn)了S1-S10，剩下的{S11,S12,S13,S14}所有節(jié)點(diǎn)的度都大于2，因此將這些節(jié)點(diǎn)加入到同一個(gè)環(huán)路域中，生成環(huán)路域Loop3。通過(guò)各個(gè)域之間建立連接關(guān)系，轉(zhuǎn)發(fā)域Group1通過(guò)S2與環(huán)路域Loop1中的S3直連，Loop1中的{S4,S5}與Loop2中的{S4,S5}相交，轉(zhuǎn)發(fā)域Group2通過(guò)S8與環(huán)路域Loop2的S7直連，通過(guò)S10與環(huán)路域Loop3的S11直連。通過(guò)以上關(guān)系建立網(wǎng)絡(luò)鏈路連接，最終拓?fù)鋱D如圖6所示。

圖6 最終域間邏輯拓?fù)?/p>

通過(guò)融合的環(huán)路域和轉(zhuǎn)發(fā)域可以簡(jiǎn)化拓?fù)浣Y(jié)構(gòu)，方便流量調(diào)度，其最重要的一個(gè)優(yōu)勢(shì)是簡(jiǎn)化了流表數(shù)量。對(duì)于轉(zhuǎn)發(fā)域來(lái)說(shuō)，轉(zhuǎn)發(fā)域中的節(jié)點(diǎn)只能組成一條鏈路，域間轉(zhuǎn)發(fā)時(shí)，在域中傳輸每臺(tái)設(shè)備只需要兩條流表，用來(lái)控制發(fā)送和接收數(shù)據(jù)的轉(zhuǎn)發(fā)；域內(nèi)轉(zhuǎn)發(fā)時(shí)，每臺(tái)設(shè)備需要一條流表匹配目的節(jié)點(diǎn)，實(shí)現(xiàn)域內(nèi)轉(zhuǎn)發(fā)。對(duì)于環(huán)路域來(lái)說(shuō)，每個(gè)環(huán)路域至少包含兩條轉(zhuǎn)發(fā)路徑，可以將這兩條路徑作為主備份路徑安裝進(jìn)交換機(jī)，在鏈路故障時(shí)進(jìn)行故障恢復(fù)，域間轉(zhuǎn)發(fā)時(shí)，設(shè)備中的匹配方式通過(guò)域名匹配，需要兩條流表控制轉(zhuǎn)發(fā)出口。

綜上所述，交換機(jī)流表數(shù)量與交換機(jī)設(shè)備所屬于的域成正比，單域設(shè)備只有一種轉(zhuǎn)發(fā)方式，總共兩條流表；多域設(shè)備需要按域轉(zhuǎn)發(fā)，一條發(fā)送一條接收，因此流表數(shù)量是域數(shù)量的兩倍。在用到所有設(shè)備的情況下，流表數(shù)量與設(shè)備數(shù)量之間的關(guān)系如下

普通流表數(shù)量=N*2*流數(shù)量 分域流表數(shù)量=N*2+域數(shù)量*2*流數(shù)量

以示例拓?fù)錇槔?，總共?4臺(tái)設(shè)備，分成了5個(gè)環(huán)路域，流表數(shù)量變化如圖7所示。

圖7 流表數(shù)量對(duì)比

隨著流數(shù)量的增加，分域流表數(shù)量增加的速度遠(yuǎn)遠(yuǎn)低于普通流表數(shù)量，當(dāng)前拓?fù)洵h(huán)境下，當(dāng)流數(shù)量達(dá)到8條時(shí)，流表數(shù)量較普通SDN下發(fā)流表數(shù)量減少了50%以上，達(dá)到了減少交換機(jī)流表數(shù)量的目的。

2.2 分域調(diào)度

隨著用戶數(shù)量的不斷增加，網(wǎng)絡(luò)業(yè)務(wù)類型和業(yè)務(wù)流量不斷增長(zhǎng)，導(dǎo)致當(dāng)前網(wǎng)絡(luò)呈現(xiàn)高冗余性。物理網(wǎng)絡(luò)上端到端具有多條可達(dá)路徑，如何在該網(wǎng)絡(luò)上制定合理的調(diào)度策略，以實(shí)現(xiàn)網(wǎng)絡(luò)業(yè)務(wù)的正常運(yùn)行并保證服務(wù)質(zhì)量，是當(dāng)前網(wǎng)絡(luò)管理工作中的一項(xiàng)重大挑戰(zhàn)。本文在進(jìn)行環(huán)路融合后，引入路徑評(píng)估方法，在下發(fā)轉(zhuǎn)發(fā)配置前評(píng)估所有轉(zhuǎn)發(fā)路徑，選擇最優(yōu)轉(zhuǎn)發(fā)路徑進(jìn)行轉(zhuǎn)發(fā)流量，保障網(wǎng)絡(luò)業(yè)務(wù)的服務(wù)質(zhì)量。

在環(huán)路融合后，每個(gè)環(huán)路域或轉(zhuǎn)發(fā)域融合成一個(gè)節(jié)點(diǎn)，域與域之間通過(guò)邏輯鏈路連接，每段鏈路具有兩個(gè)權(quán)值，包含域中節(jié)點(diǎn)的數(shù)量和域中鏈路轉(zhuǎn)發(fā)的鏈路帶寬。通過(guò)計(jì)算一條轉(zhuǎn)發(fā)路徑，使鏈路帶寬滿足業(yè)務(wù)需求并且經(jīng)過(guò)的域節(jié)點(diǎn)數(shù)量最少，提高業(yè)務(wù)的服務(wù)質(zhì)量。

我們假定一條流從源設(shè)備到目的設(shè)備經(jīng)過(guò)了多個(gè)域，設(shè)這條路徑為p，該路徑包含了多個(gè)域節(jié)點(diǎn)，每個(gè)域流向下一個(gè)域所經(jīng)過(guò)的節(jié)點(diǎn)數(shù)量為hi；域與域之間通過(guò)鏈路連接，每條鏈路具有兩個(gè)帶寬值，帶寬總?cè)萘繛閏i，鏈路已使用帶寬為bi，存儲(chǔ)方式如式(1)～式(3)

H=[h1,h2,…,hi,…,hn]

(1)

C=[c1,c2,…,ci,…,cn]

(2)

B=[b1,b2,…,bi,…,bn]

(3)

其中，下標(biāo)n表示域的總數(shù)，h1表示流經(jīng)過(guò)的融合域1流向融合域2所經(jīng)過(guò)的設(shè)備節(jié)點(diǎn)數(shù)量，即轉(zhuǎn)發(fā)跳數(shù)。ci、bi分別表示域鏈路上的帶寬總?cè)萘亢鸵咽褂玫膸挕８鶕?jù)轉(zhuǎn)發(fā)策略的不同，每條流可能經(jīng)過(guò)的域數(shù)量不同，因此該數(shù)組為可變長(zhǎng)數(shù)組。

通過(guò)參數(shù)f(src,dst,band)表示一條流的需求，從源端交換機(jī)src轉(zhuǎn)發(fā)到目的交換機(jī)dst，業(yè)務(wù)所需帶寬是band。算法先用深度優(yōu)先探索(depth-first-search，DFS)進(jìn)行全路徑計(jì)算，提取出所有可達(dá)路徑。遍歷路徑上的每條鏈路，檢查鏈路剩余帶寬是否滿足業(yè)務(wù)需求，剩余帶寬的計(jì)算方式見式(4)。滿足帶寬需求的轉(zhuǎn)發(fā)路徑將會(huì)保留下來(lái)，進(jìn)行之后的篩選，不滿足需求的路徑會(huì)被排除

R=[r1,r2,…,ri,…,rn]=C-B

(4)

全路徑算法選出所有可達(dá)路徑，經(jīng)過(guò)計(jì)算帶寬余量后，會(huì)留下符合標(biāo)準(zhǔn)的一條或多條轉(zhuǎn)發(fā)路徑。每條轉(zhuǎn)發(fā)路徑都包含以下數(shù)組，H數(shù)組記錄了路徑經(jīng)過(guò)每個(gè)域的跳數(shù)，C數(shù)組記錄了轉(zhuǎn)發(fā)路徑上鏈路帶寬的總量，B數(shù)組記錄了轉(zhuǎn)發(fā)路徑上已使用的鏈路帶寬，數(shù)組長(zhǎng)度與路徑長(zhǎng)度相等。首先計(jì)算路徑的所有跳數(shù)，使用式(5)。選擇滿足需求路徑中Hop最小的鏈路作為轉(zhuǎn)發(fā)鏈路，然后挑選一條域相交數(shù)量較少的鏈路作為備份鏈路

(5)

經(jīng)過(guò)計(jì)算Hop值后，有可能會(huì)產(chǎn)生Hop值相同的鏈路，需要計(jì)算鏈路的容納度和平滑度，選擇最優(yōu)的鏈路作為轉(zhuǎn)發(fā)路徑。鏈路容納度是一條轉(zhuǎn)發(fā)路徑中鏈路剩余帶寬的最小值，計(jì)算方法如式(6)

Contain=min{ri} (ri∈R)

(6)

選擇容納度最大的鏈路，使該轉(zhuǎn)發(fā)路徑具有更多的帶寬資源來(lái)容納數(shù)據(jù)，防止突發(fā)流量對(duì)鏈路的影響。最后如果鏈路的容納度也相同就需要進(jìn)行最終的鏈路平滑度計(jì)算，保證轉(zhuǎn)發(fā)路徑中鏈路的帶寬均勻分布，減少來(lái)自不同節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)產(chǎn)生的擁塞。具體步驟如下。

步驟1 當(dāng)前鏈路已經(jīng)計(jì)算出了鏈路的容納度，首先需要計(jì)算轉(zhuǎn)發(fā)路徑的各個(gè)鏈路剩余帶寬與容納度的差值，獲取與路徑對(duì)應(yīng)的一組鏈路差值對(duì)比數(shù)據(jù)。對(duì)于路徑p上的一條鏈路，其容納度為Contain，每段鏈路的差值公式為di，計(jì)算方式如式(7)

di=ri-Contain

(7)

步驟2 根據(jù)計(jì)算出的鏈路差值數(shù)據(jù)，計(jì)算差值的平滑度，可根據(jù)式(8)計(jì)算一個(gè)評(píng)估值Smooth，評(píng)估參數(shù)Smooth值越小說(shuō)明該鏈路的帶寬分布更加均勻，不會(huì)因某一個(gè)節(jié)點(diǎn)出現(xiàn)擁塞而影響所有鏈路的轉(zhuǎn)發(fā)，能夠?yàn)闃I(yè)務(wù)提供更加穩(wěn)定的服務(wù)

(8)

通過(guò)最終的平滑度公式可以計(jì)算出一條波動(dòng)性較小的轉(zhuǎn)發(fā)路徑，業(yè)務(wù)在該路徑上傳輸流量時(shí)能夠避免一些因突發(fā)流量造成的鏈路擁塞問(wèn)題，達(dá)到了業(yè)務(wù)保障的效果，提高了業(yè)務(wù)的服務(wù)質(zhì)量。

3 實(shí)驗(yàn)與結(jié)果

為了直觀展示該流程，本文在模擬網(wǎng)絡(luò)環(huán)境下，將UGLA算法和鏈路評(píng)估引入到故障恢復(fù)技術(shù)中，并與傳統(tǒng)的SDN故障恢復(fù)技術(shù)和基于OpenFlow組表恢復(fù)方法進(jìn)行對(duì)比，以此對(duì)本文提出的策略進(jìn)行測(cè)試評(píng)估。

本綜合實(shí)驗(yàn)以Floodlight開源控制器[16]作為控制核心，用于檢測(cè)鏈路故障和計(jì)算下發(fā)故障恢復(fù)策略。網(wǎng)絡(luò)拓?fù)淙鐖D8所示，整體網(wǎng)絡(luò)由13臺(tái)設(shè)備組成，為了更好地展現(xiàn)故障恢復(fù)性能，拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)成多環(huán)路鏈接，提高鏈路冗余度。

圖8 實(shí)驗(yàn)測(cè)試拓?fù)?/p>

通過(guò)Mininet[17]構(gòu)建了一個(gè)13臺(tái)交換機(jī)組成的網(wǎng)絡(luò)，鏈路上具有2 ms延遲效果，用于模擬物理設(shè)備間的通信延遲，每段鏈路都有不同的帶寬值，用于驗(yàn)證帶寬在路徑選擇中的作用。

首先通過(guò)網(wǎng)絡(luò)分域計(jì)算當(dāng)前拓?fù)渲械沫h(huán)路，并計(jì)算出每個(gè)域的最小帶寬和總節(jié)點(diǎn)數(shù)量，這兩個(gè)數(shù)值將作為鏈路評(píng)估所使用的參數(shù)。根據(jù)UGLA計(jì)算方法所得的環(huán)路域如圖9所示，經(jīng)過(guò)計(jì)算精簡(jiǎn)了當(dāng)前拓?fù)浣Y(jié)構(gòu)。

圖9 環(huán)域融合邏輯拓?fù)?/p>

根據(jù)當(dāng)前的環(huán)路域拓?fù)浣Y(jié)構(gòu)，生成域內(nèi)轉(zhuǎn)發(fā)流表，保證每個(gè)域內(nèi)的流量能夠正常通行。例如，在Loop1域中下發(fā)基礎(chǔ)流表后，交換機(jī){S1,S2,S3,S4,S5}能夠處理帶有Loop1標(biāo)簽的MPLS流量，使該流量在當(dāng)前環(huán)路域中沿順時(shí)針或逆時(shí)針轉(zhuǎn)發(fā)。

經(jīng)過(guò)基礎(chǔ)流表的配置，最后只缺少匹配具體數(shù)據(jù)流的流表，用于流量的流入和流出，鏈路評(píng)估算法正是用來(lái)生成該數(shù)據(jù)流的流表。假定一條數(shù)據(jù)流為S1發(fā)送至S12，帶寬需求是10 M。算法為了選擇一條轉(zhuǎn)發(fā)路徑，首先要確定該數(shù)據(jù)流的基本屬性，其源地址是S1，屬于環(huán)路域Loop1，目的地址是S12，屬于環(huán)路域Loop7。根據(jù)環(huán)路域拓?fù)渖系膮?shù)，計(jì)算出滿足當(dāng)前需求的路徑總共有4條，分別是{Loop1,Loop2,Loop6,Loop7}、{Loop1,Loop3,Loop6,Loop7}、{Loop1,Loop2,Loop4,Loop6,Loop7}、{Loop1,Loop3,Loop5,Loop6,Loop7}。

經(jīng)過(guò)篩選，最終決策出{Loop1,Loop2,Loop6,Loop7}作為該數(shù)據(jù)流的主要轉(zhuǎn)發(fā)路徑，{Loop1,Loop3,Loop6,Loop7}作為備份轉(zhuǎn)發(fā)路徑，最終生成流表下發(fā)至交換機(jī)中。

本文設(shè)計(jì)了兩個(gè)應(yīng)用場(chǎng)景，利用基于SDN的故障恢復(fù)來(lái)處理域內(nèi)故障和域間故障。計(jì)算出主要轉(zhuǎn)發(fā)路徑為{Loop1,Loop2,Loop6,Loop7}，確定物理拓?fù)渲袛?shù)據(jù)流的正常傳輸路徑為{S1,S4,S7,S6,S11,S12}。

當(dāng)發(fā)生域內(nèi)故障時(shí)，例如域Loop1內(nèi)的{S1,S4}和Loop2內(nèi)的{S5,S6}都發(fā)生斷路，系統(tǒng)啟動(dòng)域內(nèi)故障恢復(fù)功能，此時(shí)不需要控制器參與調(diào)控，交換機(jī)會(huì)自動(dòng)切換到域內(nèi)備份路徑，并告知控制器故障點(diǎn)位置。經(jīng)過(guò)域內(nèi)故障恢復(fù)策略，此時(shí)的數(shù)據(jù)流轉(zhuǎn)發(fā)路徑變更為{S1,SS,S3,S5,S9,S10,S13,S12}，故障恢復(fù)轉(zhuǎn)發(fā)路徑如圖10所示。

圖10 域內(nèi)故障恢復(fù)

由于環(huán)路域Loop1中的{S1,S4}出現(xiàn)故障，數(shù)據(jù)流從備份路徑{S1,S2,S3,S5}轉(zhuǎn)發(fā)到環(huán)路域Loop2的S5，S5同時(shí)屬于環(huán)路域1、2、3、6，S5將標(biāo)簽剝離至Loop6。由于Loop6中的{S5,S6}發(fā)生了斷路，因此環(huán)路域Loop6的轉(zhuǎn)發(fā)路徑由{S5,S6}切換至{S5,S9,S10}。

通過(guò)域內(nèi)故障恢復(fù)處理，能夠完成對(duì)域內(nèi)故障的數(shù)據(jù)流量轉(zhuǎn)發(fā)，在增加少量延遲的代價(jià)上，實(shí)現(xiàn)故障反應(yīng)快、轉(zhuǎn)發(fā)丟包率低的效果。

當(dāng)發(fā)生域間故障時(shí)，例如Loop2中的{S4,S5}和{S7,S8}出現(xiàn)斷路，導(dǎo)致環(huán)路域Loop2與Loop6的連接中斷，出現(xiàn)這種情況時(shí)，需要控制器參與故障的恢復(fù)，以實(shí)現(xiàn)降低延遲的效果，故障恢復(fù)轉(zhuǎn)發(fā)路徑如圖11所示。

圖11 域間故障恢復(fù)

根據(jù)數(shù)據(jù)流主要轉(zhuǎn)發(fā)路徑，當(dāng)數(shù)據(jù)流轉(zhuǎn)發(fā)到交換機(jī)S7時(shí)，交換機(jī)S7發(fā)現(xiàn)鏈路{S7,S6}出現(xiàn)故障，啟用故障恢復(fù)組表切換備份路徑回傳到S4并標(biāo)記該流量為域Loop2故障流量。交換機(jī)S4發(fā)現(xiàn)鏈路{S4,S5}出現(xiàn)故障，且該數(shù)據(jù)流為故障流量，啟動(dòng)域間故障恢復(fù)功能，將該數(shù)據(jù)流發(fā)回域Loop1內(nèi)并打上域間故障的標(biāo)記。鏈路評(píng)估計(jì)算所得的備份路徑開始工作，切換域轉(zhuǎn)發(fā)路徑為{Loop1,Loop3,Loop6,Loop7}，此時(shí)轉(zhuǎn)發(fā)路徑為{S1,S4,S7,S4,S1,S2,S3,S5,S6,S11,S12}。

僅通過(guò)OpenFlow協(xié)議恢復(fù)會(huì)使當(dāng)前轉(zhuǎn)發(fā)路徑每次都需要轉(zhuǎn)發(fā)到S4和S7交換機(jī)然后回溯，浪費(fèi)網(wǎng)絡(luò)帶寬資源。本設(shè)計(jì)引入控制器協(xié)同工作，在S4上報(bào)故障的同時(shí)，控制器給S4的上游設(shè)備下發(fā)配置，匹配故障流量修改轉(zhuǎn)發(fā)路徑，引導(dǎo)流量不再經(jīng)過(guò)S4和S7，減少網(wǎng)絡(luò)資源浪費(fèi)。

當(dāng)發(fā)生域內(nèi)故障時(shí)，本文設(shè)計(jì)與其它故障恢復(fù)方法進(jìn)行性能對(duì)比，鏈路傳輸速率如圖12所示。

圖12 域內(nèi)故障恢復(fù)轉(zhuǎn)發(fā)速率對(duì)比

傳輸延遲對(duì)比如圖13所示。

圖13 域內(nèi)故障恢復(fù)延遲對(duì)比

該數(shù)據(jù)表明，控制器恢復(fù)方式雖然會(huì)選擇最優(yōu)轉(zhuǎn)發(fā)路徑，但是在故障時(shí)需要等待流表失效，才能進(jìn)行路徑切換。OpenFlow方法恢復(fù)故障只在本地有效，所有流量必須轉(zhuǎn)發(fā)到故障點(diǎn)才能觸發(fā)故障恢復(fù)組表功能，延遲時(shí)間過(guò)長(zhǎng)，且流表數(shù)量比控制器調(diào)度路徑更多。本文提出的恢復(fù)方式采取分域轉(zhuǎn)發(fā)，減少了流表數(shù)量，同時(shí)故障也只在域內(nèi)處理。

當(dāng)發(fā)生域間故障時(shí)，鏈路傳輸速率如圖14所示。

圖14 域間故障恢復(fù)轉(zhuǎn)發(fā)速率對(duì)比

傳輸延遲如圖15所示。

圖15 域間故障恢復(fù)傳輸延遲對(duì)比

該數(shù)據(jù)表明，OpenFlow組表恢復(fù)方式和本文提出的恢復(fù)策略均能很好恢復(fù)故障，并且加入了控制器的引導(dǎo)，在故障后降低了傳輸延遲。

綜上所述，相比于基于SDN控制器恢復(fù)的技術(shù)，故障反應(yīng)時(shí)間更快，降低了故障恢復(fù)過(guò)程中的丟包率，流表數(shù)量更少，實(shí)現(xiàn)了故障即時(shí)恢復(fù)的需求；相比于基于OpenFlow協(xié)議恢復(fù)技術(shù)，降低了流表數(shù)量，通過(guò)交換機(jī)上報(bào)故障點(diǎn)使控制器能夠感知故障位置，控制器及時(shí)選擇最優(yōu)路徑進(jìn)行轉(zhuǎn)發(fā)流量，降低了傳輸延遲。本文提出的基于SDN的故障檢測(cè)及恢復(fù)技術(shù)實(shí)現(xiàn)了SDN網(wǎng)絡(luò)中故障流量的快速恢復(fù)，通過(guò)OpenFlow組表和控制器的協(xié)同工作以更低的延遲和丟包率傳輸故障流量，鏈路評(píng)估算法提升了故障流量的傳輸速率，整網(wǎng)的可靠性和可用性大大增強(qiáng)。

4 結(jié)束語(yǔ)

近年來(lái)，計(jì)算機(jī)技術(shù)蓬勃發(fā)展，互聯(lián)網(wǎng)業(yè)務(wù)不斷擴(kuò)大，物聯(lián)網(wǎng)、云計(jì)算等新興領(lǐng)域逐步成長(zhǎng)為大型行業(yè)。業(yè)務(wù)的增多導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜，為網(wǎng)絡(luò)管理人員帶來(lái)了繁瑣的維護(hù)工作。為實(shí)現(xiàn)控制器自動(dòng)恢復(fù)網(wǎng)絡(luò)中出現(xiàn)的故障，減少網(wǎng)絡(luò)管理人員的維護(hù)工作，本文研究和設(shè)計(jì)的基于SDN的故障恢復(fù)方法，依靠控制器強(qiáng)大的管控優(yōu)勢(shì)和可編程的開放性，針對(duì)鏈路故障實(shí)施故障恢復(fù)策略，保證冗余鏈路故障時(shí)，通信能夠正常進(jìn)行。同時(shí)還加入了鏈路帶寬評(píng)估方法，計(jì)算最佳的域間轉(zhuǎn)發(fā)路徑，滿足鏈路故障時(shí)業(yè)務(wù)的帶寬需求，降低傳輸延遲，提高業(yè)務(wù)服務(wù)質(zhì)量。

本文的方法優(yōu)勢(shì)如下：

(1)保持傳輸通暢：本文充分利用了OpenFlow協(xié)議的特性，實(shí)現(xiàn)故障恢復(fù)的自動(dòng)化切換機(jī)制，在恢復(fù)過(guò)程中確保通信不中斷。

(2)提高傳輸質(zhì)量：本文充分利用了控制器在SDN架構(gòu)中的核心控制功能，當(dāng)鏈路出現(xiàn)故障時(shí)，控制器會(huì)介入恢復(fù)過(guò)程，提前將故障數(shù)據(jù)流引導(dǎo)至正常轉(zhuǎn)發(fā)路徑上，節(jié)約網(wǎng)絡(luò)資源、降低傳輸延遲。

(3)降低流表數(shù)量：本文使用UGLA對(duì)當(dāng)前拓?fù)溥M(jìn)行分域，流量的匹配僅通過(guò)MPLS標(biāo)簽標(biāo)識(shí)，極大降低了交換機(jī)中的流表數(shù)量，節(jié)約了交換機(jī)存儲(chǔ)資源和流表的匹配效率。