引入?yún)^(qū)塊鏈的SDN 路由一致性檢測(cè)

劉宇宸，唐 菀，楊喜敏，張 艷

（中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074）

0 概述

當(dāng)前網(wǎng)絡(luò)環(huán)境日益復(fù)雜，軟件定義網(wǎng)絡(luò)（Software-Defined Network，SDN）架構(gòu)中的傳統(tǒng)單一控制器結(jié)構(gòu)已不能滿足復(fù)雜多樣的應(yīng)用層需求［1-2］。控制層作為SDN 架構(gòu)中網(wǎng)絡(luò)管理和調(diào)度的智能中心，新下發(fā)的路由策略與數(shù)據(jù)層已有的路由策略之間的一致性問題顯得尤為重要。針對(duì)路由策略的一致性問題，在控制層的研究多數(shù)通過統(tǒng)計(jì)和分析進(jìn)行檢測(cè)［3］，無須對(duì)交換機(jī)或數(shù)據(jù)包進(jìn)行額外處理，可降低網(wǎng)絡(luò)部署復(fù)雜度。

在驗(yàn)證控制層路由策略一致性問題的研究方案中，多數(shù)方案利用算法建模進(jìn)行驗(yàn)證［4］并直接分析控制層。區(qū)塊鏈技術(shù)與SDN 的結(jié)合［5］對(duì)于解決路由策略的一致性問題帶來了新的思路。區(qū)塊鏈去中心化的特性使其能在SDN 平臺(tái)得到應(yīng)用，實(shí)現(xiàn)智能化網(wǎng)絡(luò)資源管理并提升網(wǎng)絡(luò)安全性和可擴(kuò)展性［6］，同時(shí)通過共識(shí)機(jī)制確保路由策略的一致性［7-9］。但是，現(xiàn)有引入?yún)^(qū)塊鏈技術(shù)的研究方案多數(shù)僅針對(duì)多控制器的協(xié)同問題，控制層的路由一致性問題還有待進(jìn)一步解決［10］。

在多控制器結(jié)構(gòu)下，控制器之間的協(xié)同處理［11-12］以及控制層的下發(fā)路由策略會(huì)對(duì)數(shù)據(jù)層造成影響。本文提出基于區(qū)塊鏈的SDN 路由策略一致性檢測(cè)（Routing strategy Consistency Detection based on Blockchain for SDN，RCDB-SDN）方案，利用區(qū)塊鏈存儲(chǔ)流表項(xiàng)信息，結(jié)合共識(shí)機(jī)制對(duì)控制層新制定的流表項(xiàng)集進(jìn)行一致性驗(yàn)證，并在控制器將流表項(xiàng)下發(fā)交換機(jī)前，檢測(cè)出可能會(huì)對(duì)網(wǎng)絡(luò)造成不良影響的流表項(xiàng)。

1 相關(guān)研究

在控制 層的一 致性研究中，ZHOU 等［13］提 出NEAt，通過攔截SDN 應(yīng)用的更新將對(duì)應(yīng)策略制成有向圖，對(duì)違反管理員高級(jí)策略的更新及時(shí)進(jìn)行修復(fù)；ABHASHKUMAR 等［14］設(shè)計(jì)一種多層圖控制平面模型，通過自定義屬性的驗(yàn)證算法直接對(duì)控制層進(jìn)行分析以驗(yàn)證網(wǎng)絡(luò)策略。

在多控制器場(chǎng)景下，基于拜占庭容錯(cuò)（Byzantine Fault Tolerance，BFT）機(jī)制，MA 等［15］提出一種多控制器SDN 網(wǎng)絡(luò)架構(gòu)，數(shù)據(jù)層交換機(jī)由多個(gè)控制器共同管理，并在控制層和數(shù)據(jù)層之間添加一個(gè)代理，以保證流表項(xiàng)的正確下發(fā)。SHAGHAGHI等［16］提出WedgeTail，選取哈希算法，通過比較網(wǎng)絡(luò)中數(shù)據(jù)包的實(shí)際轉(zhuǎn)發(fā)路徑與控制層的預(yù)期轉(zhuǎn)發(fā)路徑來檢測(cè)異常的數(shù)據(jù)包轉(zhuǎn)發(fā)問題，但這可能會(huì)對(duì)網(wǎng)絡(luò)的實(shí)際部署造成嚴(yán)重影響。LEI 等［17］構(gòu)建2VMeri 框架，使用Bloom 過濾器和二維向量標(biāo)簽，驗(yàn)證控制層策略和數(shù)據(jù)層規(guī)則的一致性。

區(qū)塊鏈具有去中心化、持久性等特征，能夠?qū)崿F(xiàn)資源共享，通過共識(shí)機(jī)制、鏈?zhǔn)浇Y(jié)構(gòu)等技術(shù)，可以保證數(shù)據(jù)共享的安全性和可靠性。學(xué)者們對(duì)SDN與區(qū)塊鏈技術(shù)的融合進(jìn)行了大量研究并取得了一系列研究成果。MONDAL 等［18］提出BIND 方案，基于效用博弈論，借助備用路徑解決流表項(xiàng)沖突問題，在多租戶控制器之間引入?yún)^(qū)塊鏈技術(shù)，使得每個(gè)控制器都能公平地替換流表項(xiàng)，確?？刂破鏖g的合作并避免壟斷。FAN 等［10］設(shè)計(jì)并構(gòu)建區(qū)塊鏈協(xié)調(diào)控制器（Blockchain-Coordinating Controller，BCC）來確保SDN 控制器 間的協(xié) 調(diào)。CHATTARAJ 等［19］結(jié)合基于屬性的加密和基于證書的訪問控制協(xié)議，引入實(shí)用拜占庭容錯(cuò)（Practical BFT，PBFT）算法，提出一種支持區(qū)塊鏈的細(xì)粒度訪問控制機(jī)制，提高了SDN 的魯棒性。LI 等［20］設(shè)計(jì)多控制器規(guī)則執(zhí)行驗(yàn)證（BlockREV）機(jī)制，采用區(qū)塊鏈技術(shù)為轉(zhuǎn)發(fā)行為提供不變性和隱私保護(hù)，保證跨域轉(zhuǎn)發(fā)的正確性。

在將區(qū)塊鏈技術(shù)應(yīng)用于SDN 控制層的研究中，GUO 等［21］提出一種基于區(qū)塊鏈的SDN 安全框架，采用LLDP 協(xié)議周期性地獲取網(wǎng)絡(luò)鏈路信息并保證多控制器之間拓?fù)湫畔⒌囊恢滦裕硪环N基于區(qū)塊鏈的SDN 體系結(jié)構(gòu)B-SDN［22］結(jié)合水平和垂直架構(gòu)重新構(gòu)建SDN 網(wǎng)絡(luò)的控制層。RAHMAN 等［23］提出一種分層架構(gòu)并部署SDN-IoT 框架，通過識(shí)別和隔離惡意交換機(jī)來確保安全的簇頭選擇和網(wǎng)絡(luò)通信，并保持控制器集群內(nèi)的一致性。

學(xué)者們針對(duì)傳統(tǒng)SDN 中一致性問題的研究多數(shù)在數(shù)據(jù)層或控制層進(jìn)行改進(jìn)，較少涉及多控制器場(chǎng)景，也不適用于規(guī)模較大的多控制器場(chǎng)景。本文從解決方案、研究特點(diǎn)和主要技術(shù)等方面出發(fā)，歸納傳統(tǒng)SDN 與結(jié)合區(qū)塊鏈技術(shù)［12］的SDN 在一致性問題上的研究現(xiàn)狀，如表1 所示。雖然引入?yún)^(qū)塊鏈技術(shù)能更好地考慮控制器之間的協(xié)同通信、跨域轉(zhuǎn)發(fā)的正確性以及多控制器之間網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)狀態(tài)等信息的一致性，但對(duì)于控制層路由策略與網(wǎng)絡(luò)已有路由策略之間的一致性問題仍需進(jìn)一步探討。因此，本文提出RCDB-SDN 方案，通過引入?yún)^(qū)塊鏈技術(shù)來改進(jìn)基于控制層的路由策略的一致性檢測(cè)。

2 基于區(qū)塊鏈的一致性檢測(cè)

RCDB-SDN 方案在SDN 架構(gòu)中引入?yún)^(qū)塊鏈系統(tǒng)：控制層采用水平分布式架構(gòu)，控制器之間構(gòu)建區(qū)塊鏈網(wǎng)絡(luò)；數(shù)據(jù)層的交換機(jī)被劃分在不同的區(qū)域，每個(gè)區(qū)域分屬于不同的控制器管理。SDN 交換機(jī)中的流表項(xiàng)是網(wǎng)絡(luò)設(shè)備進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的依據(jù)，指導(dǎo)匹配和轉(zhuǎn)發(fā)數(shù)據(jù)包的操作。在OpenFlow 1.3 版本中，流表項(xiàng)由MatchField、Priority、Counter、Instruction、Timeout、Cookie 和Flag 等字段組成。RCDB-SDN 方案架構(gòu)如圖1 所示。

圖1 RCDB-SDN 方案架構(gòu)Fig.1 Architecture of RCDB-SDN scheme

在網(wǎng)絡(luò)運(yùn)行期間，應(yīng)用層通過北向接口向控制層發(fā)送網(wǎng)絡(luò)請(qǐng)求，控制層根據(jù)接收到的網(wǎng)絡(luò)請(qǐng)求制定路由策略并生成流表項(xiàng)集，數(shù)據(jù)層進(jìn)行網(wǎng)絡(luò)流量的轉(zhuǎn)發(fā)和處理。區(qū)塊鏈系統(tǒng)負(fù)責(zé)存儲(chǔ)流表項(xiàng)信息以及對(duì)流表項(xiàng)集進(jìn)行一致性驗(yàn)證。區(qū)塊鏈各節(jié)點(diǎn)在控制層新生成的流表項(xiàng)集被下發(fā)之前對(duì)其進(jìn)行共識(shí)驗(yàn)證，檢測(cè)該流表項(xiàng)集在數(shù)據(jù)層所對(duì)應(yīng)的轉(zhuǎn)發(fā)路徑，以判斷其是否會(huì)導(dǎo)致已有網(wǎng)絡(luò)出現(xiàn)路徑重疊或路徑環(huán)路。

2.1 區(qū)塊鏈與SDN 的融合

在RCDB-SDN 中，區(qū)塊鏈技術(shù)與SDN 的結(jié)合主要體現(xiàn)在以下兩環(huán)節(jié)：

1）區(qū)塊鏈存儲(chǔ)流表項(xiàng)信息，確保流表項(xiàng)數(shù)據(jù)的可信度和完整性。控制層解析要下發(fā)的流表項(xiàng)集，將得到的流表項(xiàng)屬性信息發(fā)送到區(qū)塊鏈系統(tǒng)請(qǐng)求一致性驗(yàn)證，只有通過驗(yàn)證的流表項(xiàng)信息才會(huì)被存儲(chǔ)在區(qū)塊鏈。

2）區(qū)塊鏈節(jié)點(diǎn)對(duì)需要下發(fā)的流表項(xiàng)集采用共識(shí)驗(yàn)證機(jī)制進(jìn)行一致性驗(yàn)證。區(qū)塊鏈每個(gè)節(jié)點(diǎn)都遵循基于投票的PBFT 共識(shí)機(jī)制［24］對(duì)一致性驗(yàn)證請(qǐng)求進(jìn)行決策，并將整個(gè)區(qū)塊鏈系統(tǒng)的最終決策返回控制層，只有在區(qū)塊鏈系統(tǒng)中達(dá)成共識(shí)的流表項(xiàng)集才能下發(fā)。

在進(jìn)行路由策略沖突檢測(cè)時(shí)，以MatchField、Instruction、Priority 三字段作為路由策略的主要特征和參考因素。在OpenFlow 1.3 版本中，完整的MatchField 字段涵蓋了開放系統(tǒng)互聯(lián)（Open System Interconnection，OSI）模型中L1（物理層）至L4（傳輸層）網(wǎng)絡(luò)的特征。但由于考慮全部MatchField 字段過于復(fù)雜，且SDN 應(yīng)用主要處于OSI 模型的L3（網(wǎng)絡(luò)層）至L4 網(wǎng)絡(luò)，選取MatchField 字段中的L3 和L4特征作為研究特征。

一條流表項(xiàng)r和一個(gè)流表項(xiàng)集R分別表示為r=和R=｛r1，r2，…，rn｝，其中，s、t、pi、po、is、id、pr、a 分別表示交換機(jī)ID、流表ID、入端口、出端口、源地址、目的地址、優(yōu)先級(jí)和動(dòng)作，n表示流表項(xiàng)集R中的流表項(xiàng)總數(shù)。

2.2 流表項(xiàng)集上鏈

控制層根據(jù)制定的路由策略生成一組流表項(xiàng)集，只有通過區(qū)塊鏈系統(tǒng)的共識(shí)驗(yàn)證之后才能被下發(fā)到數(shù)據(jù)層并寫入?yún)^(qū)塊鏈。流表項(xiàng)集上鏈流程如圖2 所示，具體步驟如下：

圖2 流表項(xiàng)集上鏈過程Fig.2 Up-chaining process of the set of flow entries

步驟1控制層根據(jù)網(wǎng)絡(luò)請(qǐng)求制定新的路由策略。

步驟2根據(jù)新路由策略生成流表項(xiàng)集合。

步驟3格式化流表項(xiàng)集的相關(guān)屬性信息成一條交易，并打包發(fā)送給區(qū)塊鏈系統(tǒng)。

步驟4區(qū)塊鏈系統(tǒng)采用基于投票的共識(shí)機(jī)制對(duì)交易進(jìn)行共識(shí)驗(yàn)證。

步驟5將驗(yàn)證結(jié)果返回給控制層。

步驟6只有驗(yàn)證通過的流表項(xiàng)集才能被下發(fā)到數(shù)據(jù)層并寫入?yún)^(qū)塊，否則取消整個(gè)流表項(xiàng)集的下發(fā)。

表2 和表3 給出了RCDB-SDN 區(qū)塊結(jié)構(gòu)和交易結(jié)構(gòu)。區(qū)塊結(jié)構(gòu)由區(qū)塊頭和區(qū)塊體組成，區(qū)塊頭包含對(duì)區(qū)塊進(jìn)行描述的屬性，區(qū)塊體是存儲(chǔ)的交易，交易所包含的元素對(duì)應(yīng)流表項(xiàng)集的特征屬性，它們都是在控制層對(duì)所要下發(fā)的流表項(xiàng)集進(jìn)行解析時(shí)獲得。

表2 區(qū)塊結(jié)構(gòu)Table 2 Block structure

表3 交易結(jié)構(gòu)Table 3 Transaction structure

2.3 問題描述

控制層根據(jù)應(yīng)用層的請(qǐng)求所制定的路由策略對(duì)應(yīng)數(shù)據(jù)層的流表項(xiàng)，一組具有相同源IP 和目的IP 的流表項(xiàng)可以表示一條轉(zhuǎn)發(fā)路徑。新的轉(zhuǎn)發(fā)路徑添加到現(xiàn)有網(wǎng)絡(luò)的轉(zhuǎn)發(fā)路徑后，可能會(huì)帶來路徑重疊和路徑環(huán)路問題。

1）路徑重疊：當(dāng)新的轉(zhuǎn)發(fā)路徑與網(wǎng)絡(luò)中已有的轉(zhuǎn)發(fā)路徑重疊，且兩條路徑對(duì)應(yīng)的流表項(xiàng)具有相同的轉(zhuǎn)發(fā)效果時(shí)，會(huì)造成數(shù)據(jù)層交換機(jī)中的流表項(xiàng)存儲(chǔ)冗余。

2）路徑環(huán)路：當(dāng)新的轉(zhuǎn)發(fā)路徑加入現(xiàn)有網(wǎng)絡(luò)后，與已有的轉(zhuǎn)發(fā)路徑構(gòu)成轉(zhuǎn)發(fā)路徑環(huán)路，并且在導(dǎo)致成環(huán)的關(guān)鍵節(jié)點(diǎn)上，數(shù)據(jù)包匹配新制定的流表項(xiàng)，引起網(wǎng)絡(luò)中數(shù)據(jù)包的轉(zhuǎn)發(fā)環(huán)路。

此外，傳統(tǒng)的檢測(cè)方案通過比較實(shí)際轉(zhuǎn)發(fā)路徑與控制層預(yù)設(shè)轉(zhuǎn)發(fā)路徑來檢測(cè)路徑重疊和路徑環(huán)路問題，需要將流表項(xiàng)下發(fā)到數(shù)據(jù)層后再進(jìn)行驗(yàn)證，增加了控制層與數(shù)據(jù)層之間的交互，從而給網(wǎng)絡(luò)帶來額外的處理能耗。

3 基于PBFT 的一致性檢測(cè)

3.1 區(qū)塊鏈共識(shí)驗(yàn)證

基于PBFT 共識(shí)機(jī)制，RCDB-SDN 的區(qū)塊鏈節(jié)點(diǎn)對(duì)需要下發(fā)的流表項(xiàng)集進(jìn)行一致性驗(yàn)證。將網(wǎng)絡(luò)中的所有控制器節(jié)點(diǎn)分為請(qǐng)求節(jié)點(diǎn)Q 和驗(yàn)證節(jié)點(diǎn)V，請(qǐng)求節(jié)點(diǎn)為收到應(yīng)用層網(wǎng)絡(luò)請(qǐng)求并制定新的路由策略及下發(fā)的節(jié)點(diǎn)；驗(yàn)證節(jié)點(diǎn)是對(duì)請(qǐng)求節(jié)點(diǎn)所要下發(fā)的路由策略進(jìn)行一致性驗(yàn)證的所有剩余節(jié)點(diǎn)。從驗(yàn)證節(jié)點(diǎn)中隨機(jī)選取一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)M，對(duì)所要下發(fā)的流表項(xiàng)集進(jìn)行一致性驗(yàn)證和投票的流程如圖3 所示。

圖3 基于投票的流表項(xiàng)共識(shí)驗(yàn)證Fig.3 Consensus verification of flow entries based on voting

請(qǐng)求節(jié)點(diǎn)解析流表項(xiàng)集得到其中每條流表項(xiàng)的特征屬性（包括源地址、目的地址、優(yōu)先級(jí)、交換機(jī)ID、流表ID 等）對(duì)應(yīng)表3 中的交易元素，將所有流表項(xiàng)的特征屬性格式轉(zhuǎn)化成一條交易Tx。主節(jié)點(diǎn)將Tx 打包廣播給所有區(qū)塊鏈節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)檢索存儲(chǔ)的數(shù)據(jù)進(jìn)行一致性驗(yàn)證。在對(duì)區(qū)塊鏈數(shù)據(jù)進(jìn)行檢索時(shí)，為降低遍歷所有數(shù)據(jù)的耗時(shí)，將區(qū)塊鏈所有存儲(chǔ)的區(qū)塊按節(jié)點(diǎn)數(shù)量進(jìn)行平均劃分。每個(gè)節(jié)點(diǎn)只在劃分到的區(qū)塊中進(jìn)行檢索，所有節(jié)點(diǎn)并行地檢索區(qū)塊鏈數(shù)據(jù)，可以加快遍歷整個(gè)區(qū)塊鏈并減少時(shí)延。

根據(jù)一致性驗(yàn)證的結(jié)果，各驗(yàn)證節(jié)點(diǎn)將投票信息反饋給請(qǐng)求節(jié)點(diǎn)。若驗(yàn)證失敗，則返回false，為反對(duì)票；否則返回true，為同意票。按照少數(shù)服從多數(shù)的原則，同意票數(shù)不少于半數(shù)時(shí)，判定該交易有效，請(qǐng)求節(jié)點(diǎn)此次獲得向區(qū)塊鏈中寫區(qū)塊的權(quán)利；否則該交易無效，請(qǐng)求節(jié)點(diǎn)此次無權(quán)寫區(qū)塊。請(qǐng)求節(jié)點(diǎn)根據(jù)投票結(jié)果來決策是否下發(fā)流表項(xiàng)集。若下發(fā)，則在下發(fā)的同時(shí)將流表項(xiàng)集格式化后，打包并寫入?yún)^(qū)塊鏈。

3.2 一致性檢測(cè)

在區(qū)塊鏈系統(tǒng)中，每個(gè)節(jié)點(diǎn)根據(jù)自己檢索的數(shù)據(jù)對(duì)交易進(jìn)行一致性驗(yàn)證，再按照各自的驗(yàn)證結(jié)果投票，匯總投票結(jié)果之后返回控制層進(jìn)行決策。在一致性檢測(cè)中，RCDB-SDN 方案分為針對(duì)路徑重疊和路徑環(huán)路兩部分。

對(duì)于路徑重疊的檢測(cè)，即在檢測(cè)到完全重疊的轉(zhuǎn)發(fā)路徑時(shí)，驗(yàn)證流表項(xiàng)特征屬性的相關(guān)性，判斷是否會(huì)造成流表存儲(chǔ)冗余［25］。對(duì)于路徑環(huán)路的檢測(cè)，采用環(huán)路檢測(cè)算法檢測(cè)構(gòu)建的有向圖是否存在環(huán)路，并在關(guān)鍵節(jié)點(diǎn)上驗(yàn)證流表項(xiàng)特征屬性的相關(guān)性。若路徑環(huán)路存在，則判斷其是否會(huì)造成網(wǎng)絡(luò)轉(zhuǎn)發(fā)環(huán)路。

在構(gòu)建 轉(zhuǎn)發(fā)路徑時(shí)，節(jié) 點(diǎn)Node=，其中，s、pi、po、nextNode 分別表示交換機(jī)ID、入端口、出端口、當(dāng)前節(jié)點(diǎn)的下一跳節(jié)點(diǎn)。一條轉(zhuǎn)發(fā)路徑P的表示形式為P=｛Node1，Node2，…，Noden｝。

3.2.1 路徑重疊檢測(cè)

由于兩條轉(zhuǎn)發(fā)路徑完全重疊，在路徑上各節(jié)點(diǎn)中的流表項(xiàng)具有相同的轉(zhuǎn)發(fā)效果，因此驗(yàn)證兩條轉(zhuǎn)發(fā)路徑的轉(zhuǎn)發(fā)效果是否一致，只須驗(yàn)證兩條路徑上輸出端節(jié)點(diǎn)中的流表項(xiàng)。

控制層對(duì)制定的流表項(xiàng)集R進(jìn)行解析得到特征屬性，結(jié)合區(qū)塊鏈系統(tǒng)的共識(shí)機(jī)制對(duì)其進(jìn)行一致性驗(yàn)證，確保R的下發(fā)不會(huì)造成流表項(xiàng)的存儲(chǔ)冗余。路徑重疊檢測(cè)的流程如圖4 所示，具體步驟如下：

圖4 路徑重疊檢測(cè)Fig.4 Detection of path overlap

步驟1構(gòu)建轉(zhuǎn)發(fā)路徑。控制層根據(jù)上層應(yīng)用下發(fā)的網(wǎng)絡(luò)請(qǐng)求制定路由策略，生成流表項(xiàng)集R并進(jìn)行解析，將獲得的特征屬性格式化成交易Tx，打包發(fā)送到區(qū)塊鏈系統(tǒng)。在區(qū)塊鏈中查找與R途經(jīng)相同交換機(jī)的流表項(xiàng)集R'，獲取并結(jié)合對(duì)應(yīng)流表項(xiàng)集的特征屬性，構(gòu)建兩條轉(zhuǎn)發(fā)路徑P和P'。

步驟2一致性檢測(cè)。檢測(cè)P和P'是否相同。若兩者相同，則存在路徑重疊，此時(shí)返回路徑輸出端節(jié)點(diǎn)NodeT。只有當(dāng)P和P'滿足式（1）時(shí)，才存在這樣一個(gè)輸出端節(jié)點(diǎn)NodeT，其中num 表示路徑中所包含的節(jié)點(diǎn)數(shù)量。

步驟3流表項(xiàng)檢測(cè)。若NodeT 存在，則在兩條轉(zhuǎn)發(fā)路徑上的NodeT 節(jié)點(diǎn)所對(duì)應(yīng)的交換機(jī)中存在流表 項(xiàng)r和r'（r為新制 定的流表項(xiàng)，r'為交換 機(jī)已有 的流表項(xiàng)），通過函數(shù)（fr，r'）驗(yàn)證兩者是否會(huì)引起存儲(chǔ)冗余。當(dāng)r和r'滿足式（2）時(shí)，函數(shù)返回值為true，表明會(huì)引起流表項(xiàng)存儲(chǔ)冗余（用PO 表示）。

步驟4若驗(yàn)證結(jié)果表明不會(huì)引起流表項(xiàng)存儲(chǔ)冗余，則下發(fā)R；反之取消R的下發(fā)。

在上述檢測(cè)流程中，基于解析得到的流表項(xiàng)特征屬性，通過區(qū)塊鏈系統(tǒng)的檢索，在存儲(chǔ)的區(qū)塊中找到與其相對(duì)應(yīng)的流表項(xiàng)屬性并構(gòu)建轉(zhuǎn)發(fā)路徑。轉(zhuǎn)發(fā)路徑的構(gòu)建以及輸出端節(jié)點(diǎn)上的流表項(xiàng)驗(yàn)證是路徑重疊檢測(cè)的關(guān)鍵。

3.2.2 路徑環(huán)路檢測(cè)

控制層對(duì)生成的流表項(xiàng)集R進(jìn)行解析得到特征屬性，借助有向圖的構(gòu)建和環(huán)路檢測(cè)，結(jié)合區(qū)塊鏈系統(tǒng)的共識(shí)機(jī)制完成一致性驗(yàn)證，確保R的下發(fā)不會(huì)造成網(wǎng)絡(luò)中數(shù)據(jù)包轉(zhuǎn)發(fā)環(huán)路。路徑環(huán)路檢測(cè)的流程如圖5 所示，具體步驟如下：

圖5 路徑環(huán)路檢測(cè)Fig.5 Detection of path loop

步驟1構(gòu)建有向圖?？刂茖痈鶕?jù)上層應(yīng)用下發(fā)的網(wǎng)絡(luò)請(qǐng)求制定路由策略，生成流表項(xiàng)集R并進(jìn)行解析，將獲得的特征屬性格式化成交易Tx，打包發(fā)送到區(qū)塊鏈系統(tǒng)。在區(qū)塊鏈中查找和R途徑相同交換機(jī)的流表項(xiàng)集R'，獲取對(duì)應(yīng)的流表項(xiàng)集的特征屬性，結(jié)合R和R'的特征屬性，構(gòu)建有向圖G。

步驟2有向圖G環(huán)路檢測(cè)。有向圖G=，基于深度優(yōu)先搜索來檢測(cè)圖G是否存在一個(gè)環(huán)路（用Ploop表示）。一條邊e表示為，節(jié)點(diǎn)集合V=｛s1，s2，…，sk｝，需要滿足條件?s∈V，?（P.Node.s=s）∨（P'.Node.s=s），邊集合E=｛e1，e2，…，em｝，需要滿足條件?e∈E，?（=e）∨（=e），其中，k和m分別表示V和E中節(jié)點(diǎn)和邊的數(shù)量。

步驟3確定環(huán)路關(guān)鍵節(jié)點(diǎn)KeyNode。若有向圖G存在環(huán)路，則表明兩組流表項(xiàng)集同時(shí)存在會(huì)導(dǎo)致路徑環(huán)路。因此，需要找出環(huán)路關(guān)鍵節(jié)點(diǎn)，在該節(jié)點(diǎn)的轉(zhuǎn)發(fā)操作會(huì)直接決定是否產(chǎn)生網(wǎng)絡(luò)轉(zhuǎn)發(fā)環(huán)路。

步驟4流表項(xiàng)字段相關(guān)性檢測(cè)。檢測(cè)節(jié)點(diǎn)KeyNode 所對(duì)應(yīng)的交換機(jī)上流表項(xiàng)r和r'，驗(yàn)證兩者是否具有相關(guān)性，即r和r'的源IP 地址與目的IP 地址分別是否存在包含與被包含的情況。

步驟5匹配順序檢測(cè)。當(dāng)多條流表項(xiàng)具有相同的優(yōu)先級(jí)與不同的匹配域粒度時(shí)，會(huì)按照流表項(xiàng)添加的先后順序匹配。因此，若r和r'具有相關(guān)性，則進(jìn)一步檢測(cè)兩者同時(shí)存在時(shí)，數(shù)據(jù)包匹配的優(yōu)先次 序。通過函 數(shù)v（r，r'）驗(yàn) 證r和r'，當(dāng)兩者滿足式（4）時(shí)，函數(shù)返回值為true，表明會(huì)導(dǎo)致網(wǎng)絡(luò)轉(zhuǎn)發(fā)環(huán)路（用PL 表示）。

步驟6若驗(yàn)證結(jié)果表明不會(huì)產(chǎn)生路徑環(huán)路，也不會(huì)引起網(wǎng)絡(luò)環(huán)路，則下發(fā)R；反之取消R的下發(fā)。

在上述檢測(cè)流程中：有向圖G的環(huán)路檢測(cè)是路徑環(huán)路檢測(cè)的關(guān)鍵所在，目的在于初步檢測(cè)是否有導(dǎo)致路徑環(huán)路存在的可能；流表項(xiàng)字段與匹配順序檢測(cè)則是驗(yàn)證路徑環(huán)路的重要步驟。

總之，一致性檢測(cè)分為路徑重疊和路徑環(huán)路兩階段。前者通過構(gòu)建轉(zhuǎn)發(fā)路徑進(jìn)行比較，需要的存儲(chǔ)開銷與網(wǎng)絡(luò)中存在的重疊路徑數(shù)量有關(guān)；后者通過構(gòu)建有向圖進(jìn)行驗(yàn)證，考慮與新制定的流表項(xiàng)集存在相關(guān)性的流表項(xiàng)集，存儲(chǔ)開銷較前者更大。

4 實(shí)驗(yàn)與評(píng)估

4.1 實(shí)驗(yàn)平臺(tái)與設(shè)置

考慮到快速構(gòu)建區(qū)塊鏈網(wǎng)絡(luò)的需求，選取Multichain［26］作為實(shí)驗(yàn)的區(qū)塊鏈平臺(tái)。在初始化區(qū)塊鏈時(shí)，確保在沒有新的交易產(chǎn)生時(shí)，區(qū)塊鏈平臺(tái)不會(huì)自動(dòng)添加區(qū)塊，以減少區(qū)塊鏈平臺(tái)在無區(qū)塊寫入時(shí)存儲(chǔ)空間的使用以及無效區(qū)塊的生成。實(shí)驗(yàn)選用Ubuntu 作為系統(tǒng)平臺(tái)、Mininet 作為網(wǎng)絡(luò)模擬器及Opendaylight 作 為SDN 控制器。

基于Multichain 平臺(tái)和Mininet 模擬器構(gòu)建RCDB-SDN 方案模型，使用20 個(gè)交換機(jī)（s1～s20），并依次劃分為5 個(gè)域（D1～D5），由5 個(gè)控制器（c1～c5）分管。在網(wǎng)絡(luò)運(yùn)行期間，每當(dāng)有新的流表項(xiàng)集生成時(shí)，在對(duì)應(yīng)的控制器中將其格式化為一條交易并打包之后，廣播給其他控制器節(jié)點(diǎn)，向每個(gè)控制器節(jié)點(diǎn)發(fā)起驗(yàn)證請(qǐng)求，其余控制器節(jié)點(diǎn)按照RCDB-SDN 方案進(jìn)行檢測(cè)，并將結(jié)果反饋給初始發(fā)起請(qǐng)求的節(jié)點(diǎn)。

仿真實(shí)驗(yàn)搭建的網(wǎng)絡(luò)采用圖6 中的數(shù)據(jù)中心網(wǎng)絡(luò)Fat-Tree［27］拓?fù)浣Y(jié)構(gòu)，并在控制層通過編寫腳本文件生成會(huì)造成路徑重疊和路徑環(huán)路的流表項(xiàng)集。流表項(xiàng)集的下發(fā)次數(shù)為200 和400（對(duì)每一次流表項(xiàng)集的下發(fā)都進(jìn)行檢測(cè)），每類實(shí)驗(yàn)分別有10 組，每組實(shí)驗(yàn)分別在不同的域內(nèi)以及域間模擬會(huì)造成影響的流表項(xiàng)集。取10 組實(shí)驗(yàn)的平均值，評(píng)估當(dāng)網(wǎng)絡(luò)中實(shí)際存在的流表項(xiàng)數(shù)量變化時(shí)，RCDB-SDN 方案對(duì)路徑重疊和路徑環(huán)路的檢測(cè)情況。在每組實(shí)驗(yàn)所下發(fā)的流表項(xiàng)集中，實(shí)際會(huì)造成路徑重疊或者路徑環(huán)路的流表項(xiàng)集與實(shí)際不會(huì)造成影響的流表項(xiàng)集比例為1∶1。

圖6 仿真實(shí)驗(yàn)平臺(tái)的Fat-Tree 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.6 Fat-Tree network topology of simulation platform

在網(wǎng)絡(luò)中流表項(xiàng)集所對(duì)應(yīng)的轉(zhuǎn)發(fā)路徑引發(fā)沖突的情形通常不會(huì)集中出現(xiàn)。因此，在模擬真實(shí)場(chǎng)景時(shí)，每次實(shí)驗(yàn)中會(huì)生成路徑重疊和路徑環(huán)路的流表項(xiàng)集下發(fā)的時(shí)間和周期不固定。

4.2 評(píng)價(jià)指標(biāo)

選取精確率、誤檢率、查全率、漏檢率和消息傳遞次數(shù)等5 項(xiàng)指標(biāo)對(duì)RCDB-SDN 進(jìn)行評(píng)估。精確率指在檢測(cè)到的所有沖突結(jié)果中，真實(shí)沖突所占的比率。誤檢率指在實(shí)際不沖突的結(jié)果中，錯(cuò)誤檢測(cè)成沖突的結(jié)果所占的比率；查全率指檢測(cè)出的真實(shí)沖突結(jié)果占全部真實(shí)沖突的比率；漏檢率指未檢測(cè)出的真實(shí)沖突占全部真實(shí)沖突的比率；消息傳遞次數(shù)用來統(tǒng)計(jì)控制層與數(shù)據(jù)層之間的消息傳遞。

在傳統(tǒng)的沒有引入?yún)^(qū)塊鏈技術(shù)的檢測(cè)方案WedgeTail［16］中，通過比較數(shù)據(jù)包的實(shí)際路徑與控制層的預(yù)設(shè)路徑之間的差異來檢測(cè)異常。將RCDBSDN 方案的路徑重疊和路徑環(huán)路兩部分檢測(cè)與WedgeTail 進(jìn)行比較實(shí)驗(yàn)。

4.3 結(jié)果分析

4.3.1 路徑重疊檢測(cè)

路徑重疊檢測(cè)對(duì)比結(jié)果如圖7 所示。由圖7 可以看出，在分別下發(fā)200 次和400 次流表項(xiàng)集合的兩類實(shí)驗(yàn)下，當(dāng)現(xiàn)有網(wǎng)絡(luò)中的流表項(xiàng)總數(shù)在一定范圍內(nèi)增長時(shí)，RCDB-SDN 結(jié)合區(qū)塊鏈技術(shù)對(duì)路徑重疊檢測(cè)的精確率和誤檢率整體上優(yōu)于WedgeTail［16］。主要原因?yàn)镽CDB-SDN 通過檢索區(qū)塊鏈存儲(chǔ)的所有流表項(xiàng)信息進(jìn)行驗(yàn)證，但由于分區(qū)檢索的緣故，一條轉(zhuǎn)發(fā)路徑對(duì)應(yīng)的流表項(xiàng)可能被劃分到不同的節(jié)點(diǎn)進(jìn)行驗(yàn)證，導(dǎo)致檢測(cè)結(jié)果與實(shí)際結(jié)果不一致。在不同檢測(cè)次數(shù)下，區(qū)塊鏈存儲(chǔ)的流表項(xiàng)信息與網(wǎng)絡(luò)中實(shí)際生效的流表項(xiàng)之間存在的差異會(huì)對(duì)檢測(cè)的精確率產(chǎn)生影響。此外，對(duì)于RCDB-SDN 而言，檢測(cè)精確率和誤檢率受檢測(cè)次數(shù)增加的影響不明顯，反而隨著網(wǎng)絡(luò)中流表項(xiàng)數(shù)量的增加影響較明顯。隨著流表項(xiàng)總數(shù)的增加，在實(shí)際網(wǎng)絡(luò)中流表信息的刪除和更新會(huì)改變流表項(xiàng)數(shù)量，但區(qū)塊鏈系統(tǒng)中存儲(chǔ)的數(shù)據(jù)不會(huì)減少，因此區(qū)塊鏈存儲(chǔ)的流表項(xiàng)信息會(huì)與實(shí)際網(wǎng)絡(luò)中有效的流表項(xiàng)之間出現(xiàn)差異，導(dǎo)致RCDBSDN 的精確率有所下降，誤檢率有所上升，但整體上RCDB-SDN 的精確率依然高于WedgeTail，誤檢率低于WedgeTail。

圖7 路徑重疊檢測(cè)對(duì)比Fig.7 Comparison of path overlap detection

路徑重疊檢測(cè)的查全率和漏檢率如表4 所示。由表4 可以看出，檢測(cè)次數(shù)對(duì)RCDB-SDN 和WedgeTail 兩種方案的查全率和漏檢率影響不大，在分別下發(fā)200 次和400 次流表項(xiàng)集合的兩類實(shí)驗(yàn)下的實(shí)驗(yàn)結(jié)果大致相近，但是前者的查全率高于后者，且隨著流表項(xiàng)數(shù)量增多而愈發(fā)顯著。同時(shí)，通過對(duì)比消息傳遞次數(shù)（如圖8 所示）可以看出：WedgeTail在檢測(cè)到路徑重疊之后，需要反饋信息給控制器，然后由控制器再次下發(fā)指令消息刪除對(duì)應(yīng)的流表項(xiàng)；RCDB-SDN 在流表項(xiàng)下發(fā)之前進(jìn)行檢測(cè)，可以避免這一步驟，使控制層與數(shù)據(jù)層之間的消息傳遞次數(shù)更少。

表4 路徑重疊檢測(cè)的查全率和漏檢率Table 4 Recall and missed detection rate of path overlap detection

4.3.2 路徑環(huán)路檢測(cè)

路徑環(huán)路檢測(cè)對(duì)比結(jié)果如圖9 所示。由圖9 可以看出，當(dāng)網(wǎng)絡(luò)中的流表項(xiàng)總數(shù)在一定范圍內(nèi)增長時(shí)，在分別下發(fā)200 次和400 次流表項(xiàng)集合的兩類實(shí)驗(yàn)下，RCDB-SDN 對(duì)于路徑環(huán)路檢測(cè)的精確率和誤檢率整體 上優(yōu)于WedgeTail［16］。主要原因?yàn)镽CDBSDN 對(duì)區(qū)塊鏈存儲(chǔ)的數(shù)據(jù)分區(qū)之后進(jìn)行檢索，在提高檢索速度的同時(shí)，不同的節(jié)點(diǎn)可能只對(duì)一條轉(zhuǎn)發(fā)路徑所對(duì)應(yīng)的流表項(xiàng)集中的一部分流表項(xiàng)進(jìn)行驗(yàn)證，驗(yàn)證不完全導(dǎo)致檢測(cè)結(jié)果與實(shí)際情況出現(xiàn)偏差。隨著時(shí)間推移，當(dāng)檢測(cè)次數(shù)增加之后，檢測(cè)結(jié)果與實(shí)際情況不一致的可能性會(huì)有所增加。此外，對(duì)于RCDBSDN 而言，路徑環(huán)路檢測(cè)次數(shù)的增加對(duì)精確率和誤檢率有一定影響，但網(wǎng)絡(luò)中流表項(xiàng)總量對(duì)精確率和誤檢率的影響更大。隨著流表項(xiàng)總數(shù)的增加，在RCDBSDN 中，區(qū)塊鏈存儲(chǔ)的流表項(xiàng)信息會(huì)持續(xù)增加，但是實(shí)際網(wǎng)絡(luò)中的流表項(xiàng)由于刪除和更新等操作，與區(qū)塊鏈存儲(chǔ)的數(shù)據(jù)會(huì)逐步出現(xiàn)差異，因此RCDB-SDN 的精確率有所下降而誤檢率有所上升，但整體上其精確率依然高于WedgeTail，誤檢率低于WedgeTail。

圖9 路徑環(huán)路檢測(cè)對(duì)比Fig.9 Comparison of path loop detection

路徑環(huán)路檢測(cè)的查全率和漏檢率如表5 所示。由表5 可以看出，在查全率和漏檢率上，RCDB-SDN和WedgeTail 兩種方案受檢測(cè)次數(shù)的影響較小，在分別下發(fā)200 次和400 次流表項(xiàng)集合的兩類實(shí)驗(yàn)下的實(shí)驗(yàn)結(jié)果大致相近，但是前者的查全率高于后者。

表5 路徑環(huán)路檢測(cè)的查全率和漏檢率Table 5 Recall and missed detection rate of path loop detection

路徑環(huán)路檢測(cè)的消息傳遞次數(shù)如圖10 所示。由圖10 可以看出，相較于WedgeTail 在檢測(cè)到路徑環(huán)路后反饋信息給控制器，并下發(fā)指令刪除對(duì)應(yīng)的流表項(xiàng)，RCDB-SDN 在流表項(xiàng)下發(fā)前就進(jìn)行路徑環(huán)路檢測(cè)，可以在出現(xiàn)路徑環(huán)路時(shí)，有效減少控制層與數(shù)據(jù)層之間的消息傳遞次數(shù)。

圖10 路徑環(huán)路檢測(cè)的消息傳遞次數(shù)Fig.10 Messaging times during path loop detection

綜合兩部分檢測(cè)的實(shí)驗(yàn)結(jié)果來看，由于設(shè)計(jì)的RCDB-SDN 方案在檢測(cè)中對(duì)區(qū)塊鏈進(jìn)行了劃分，因此由不同的節(jié)點(diǎn)各自負(fù)責(zé)區(qū)塊鏈存儲(chǔ)的一部分?jǐn)?shù)據(jù)。當(dāng)實(shí)際會(huì)引起沖突（路徑重疊或路徑環(huán)路）的流表項(xiàng)集恰好被劃分到不同的節(jié)點(diǎn)進(jìn)行檢測(cè)時(shí)，則被檢測(cè)為不會(huì)引起沖突的可能性較大。

另外，由于真實(shí)網(wǎng)絡(luò)中的流表不斷更新，被刪除的流表項(xiàng)卻依然存儲(chǔ)在區(qū)塊鏈中，在借助區(qū)塊鏈對(duì)實(shí)際上不會(huì)引起沖突的流表項(xiàng)集進(jìn)行一致性驗(yàn)證時(shí)，也可能被錯(cuò)誤地檢測(cè)為會(huì)引起網(wǎng)絡(luò)路由信息沖突，導(dǎo)致檢測(cè)結(jié)果的誤差。

5 結(jié)束語

SDN 所具有的轉(zhuǎn)控分離的特點(diǎn)使其可以靈活高效地處理網(wǎng)絡(luò)流量，但當(dāng)SDN 采用多控制器結(jié)構(gòu)時(shí)，控制層根據(jù)應(yīng)用層網(wǎng)絡(luò)請(qǐng)求制定路由策略，生成的流表項(xiàng)可能會(huì)帶來流表項(xiàng)存儲(chǔ)冗余和網(wǎng)絡(luò)流量轉(zhuǎn)發(fā)環(huán)路等問題。本文提出的RCDB-SDN 方案結(jié)合區(qū)塊鏈可追溯、不可篡改的特性，引入共識(shí)機(jī)制檢測(cè)路由策略的一致性，并通過仿真實(shí)驗(yàn)驗(yàn)證了RCDB-SDN 方案對(duì)路徑重疊和路徑環(huán)路檢測(cè)的可行性與有效性。后續(xù)將進(jìn)一步優(yōu)化檢測(cè)方案，當(dāng)區(qū)塊鏈系統(tǒng)存儲(chǔ)的流表項(xiàng)信息與實(shí)際網(wǎng)絡(luò)存儲(chǔ)的有效流表項(xiàng)信息之間的差異越來越大時(shí)，通過改進(jìn)區(qū)塊鏈系統(tǒng)的檢索方式，盡可能地提高檢測(cè)結(jié)果與實(shí)際網(wǎng)絡(luò)之間的一致性。