朱夢迪，束永安

（安徽大學計算機科學與技術學院，合肥 230601）

（?通信作者電子郵箱2524098773@qq.com）

0 引言

軟件定義網(wǎng)絡（Software Defined Network，SDN）是一種將控制平面與數(shù)據(jù)平面分離的新型網(wǎng)絡架構。控制平面通過北向接口協(xié)議集中管理網(wǎng)絡應用程序，通過南向接口協(xié)議管控數(shù)據(jù)平面所有硬件設備的轉發(fā)行為［1］。

與傳統(tǒng)網(wǎng)絡不同的是，SDN 是一個流規(guī)則驅動的網(wǎng)絡［2］。網(wǎng)絡應用程序、操作人員可以制定網(wǎng)絡策略，對應接口會將其轉化成一組邏輯流規(guī)則，然后控制器通過北向接口將邏輯流規(guī)則部署到交換機內(nèi)，最后網(wǎng)絡設備根據(jù)交換機內(nèi)的流表項對數(shù)據(jù)包進行處理，實現(xiàn)對應的網(wǎng)絡策略。

在SDN 中，目前有以下幾方面原因，會導致數(shù)據(jù)包的轉發(fā)行為與控制層流規(guī)則不一致。OpenFlow 協(xié)議［3］的Barrier命令不能百分之百保證控制器下發(fā)到數(shù)據(jù)層的每個流規(guī)則全部可以正確安裝［4-6］；網(wǎng)絡故障中的很大一部分原因是由于數(shù)據(jù)層的硬件問題及軟件錯誤［7］；SDN 的控制平面與數(shù)據(jù)平面之間采用異步通信發(fā)送信息，一些網(wǎng)絡更新命令（如OpenFlow協(xié)議的FlowMod 命令）會使得交換機在更新流表時存在延遲，無法及時更新［5，8］；最后，網(wǎng)絡管理員的錯誤配置，和攻擊者使用一些工具（如ONIE（http：//onie.org/）），均有可能修改交換機內(nèi)部的流表項，導致數(shù)據(jù)層沒有實現(xiàn)相應的網(wǎng)絡策略。

為了解決控制層與數(shù)據(jù)層流規(guī)則不一致的問題，文獻［9-13］均提出各自的方法，用于檢測多個應用程序引起的網(wǎng)絡策略沖突，但是這些方法只能處理控制層流規(guī)則沖突的問題，卻無法檢測到數(shù)據(jù)層的流量轉發(fā)是否符合控制層的策略要求。因此，文獻［14］將數(shù)據(jù)層的可執(zhí)行文件作為自制的檢測工具的輸入，用于檢測數(shù)據(jù)平面是否不合理的網(wǎng)絡配置，但檢測機制無法對網(wǎng)絡狀態(tài)進行實時監(jiān)測；所以，文獻［15］使用探測數(shù)據(jù)包，對數(shù)據(jù)平面的信息進行收集和記錄，可以動態(tài)監(jiān)控轉發(fā)鏈路上是否出現(xiàn)故障交換機，但該種方法探測數(shù)據(jù)包的生成時間較長，無法快速地發(fā)現(xiàn)數(shù)據(jù)層的錯誤。

繼而，文獻［16］提出VeriDP 檢測模型，該模型截取數(shù)據(jù)流中的數(shù)據(jù)包，在采樣數(shù)據(jù)包中添加標簽字段，無需單獨生成探測數(shù)據(jù)包，但該方法的缺點在于控制平面需要提前保存所有正確的轉發(fā)路徑信息，過于消耗內(nèi)存資源。文獻［17］提出2MVeri 模型，但算法時間復雜度相對較高，系統(tǒng)開銷相對較大。因而，本文提出了驗證控制與數(shù)據(jù)平面的一致性（Verifying control-data plane Consistency，VeriC）檢測模型，不僅解決了內(nèi)存消耗大與過濾器誤報的問題，又在準確找出發(fā)生錯誤的交換機的前提下降低系統(tǒng)開銷。

1 VeriC檢測模型系統(tǒng)設計

VeriC 檢測模型由VeriC 模型對應服務器中的驗證子系統(tǒng)、定位子系統(tǒng)以及交換機的數(shù)據(jù)包處理子系統(tǒng)共同實現(xiàn)?？刂破骱徒粨Q機通過OpenFlow 協(xié)議交互的信息，均會被攔截并保存在模型服務器內(nèi)。

VeriC模型借助管道技術實現(xiàn)數(shù)據(jù)包處理子系統(tǒng)的功能，由交換機的快速路徑技術完成，并且與OpenFlow 所用的管道是分離的［16］。VeriC在入口交換機上對數(shù)據(jù)包進行采樣，在數(shù)據(jù)包的轉發(fā)過程中對數(shù)據(jù)包進行標記，每經(jīng)過一個交換機，更新采樣數(shù)據(jù)包標簽字段，隨后將更新后的標簽值發(fā)送到VeriC服務器，分別存儲在上報的標簽值PTg［i］（rePorted Tag）和上報布隆過濾器值BFp（reported Bloom Filter）。

VeriC模型對通過南向接口協(xié)議交互的消息進行攔截，當被采樣數(shù)據(jù)包在出口交換機標記動作完成后，模型服務器根據(jù)初始二維向量、正確的轉發(fā)表、交換機ID以及每個交換機對應的二維矩陣，計算出一組正確的標簽值CTg（Corrected Tag）和正確的布隆過濾器值BFc（corrected Bloom Filter）。每組流規(guī)則對應CTg［i］和BFc，PTg［i］和BFp均會被發(fā)送到驗證子系統(tǒng)進行一致性檢測；若存在異常，標簽值組被進一步發(fā)送到到定位子系統(tǒng)，對故障的交換機進行定位。VeriC模型結構如圖1所示。

圖1 VeriC模型結構Fig.1 VeriC model structure

2 詳細設計

2.1 數(shù)據(jù)包處理系統(tǒng)

2.1.1 數(shù)據(jù)包采樣

在數(shù)據(jù)包處理系統(tǒng)中，首先要對交換機中數(shù)據(jù)包進行采樣［17］。在入口交換機，使用數(shù)據(jù)包字段中的一個位來記錄數(shù)據(jù)包是否被采樣，設最近一次采樣時間為，采樣間隔為。若入口交換機在時間t收到數(shù)據(jù)包，數(shù)據(jù)包的采樣時間滿足式（1），則該數(shù)據(jù)包即為采樣數(shù)據(jù)包：

2.1.2 生成交換機矩陣

數(shù)據(jù)層交換機在初始化時，控制器會為其分配一個受限制的二維矩陣，用于對交換機進行標記［17］。為了使標簽信息能夠準確代表數(shù)據(jù)包的轉發(fā)路徑，在為每臺交換機分配二維矩陣時，需滿足以下要求：

1）二維矩陣中的四個元素均為素數(shù)，降低矩陣的重復率；

2）相鄰交換機是不可交換矩陣，即相鄰交換機的矩陣信息不滿足矩陣乘法交換律；

3）交換機的二維矩陣不可以相同。

2.1.3 字符注釋

為了便于描述，對本文涉及的符號進行注釋，如表1所示。

表1 符號注釋Tab.1 Notations and related meanings

2.1.4 標記采樣數(shù)據(jù)包

對于每個采樣數(shù)據(jù)包，會在包頭中插入BF字段和一個二維向量字段（v1，v2）。其中，BF 字段的初始值為0（見算法1 第1）～2）行），表示采樣數(shù)據(jù)包經(jīng)過交換機ID的集合。采樣數(shù)據(jù)包每經(jīng)過一臺交換機，BF字段就會將新交換機的ID存儲到集合中，當數(shù)據(jù)包到達出口交換機或者要執(zhí)行刪除操作前，將BF字段發(fā)送到控制平面進行保存（見算法1第10）～12）行）。

控制器基于采樣數(shù)據(jù)包的性質(zhì)，首先為二維向量字段（v1，v2）分配初始值（見算法1第3）～5）行），并將初始值上傳到控制層。在控制層中，使用〈inport，outport，header〉作為索引，存儲到同一采樣數(shù)據(jù)包的標簽值集合，其中inport 是采樣數(shù)據(jù)包的入端口編號，outport 是采樣數(shù)據(jù)包的出端口編號，header是采樣數(shù)據(jù)包的包頭信息；然后，當采樣數(shù)據(jù)包經(jīng)過交換機時，二維向量會與交換機對應的二維矩陣相乘，運算值會重新存儲在二維向量字段中（見算法1第6）行）。二維向量字段每次完成更新后，會將標簽字段發(fā)送到模型服務器進行保存（見算法1第7）～9）行）。數(shù)據(jù)包處理算法描述如下。

算法1 數(shù)據(jù)包處理算法（Packet processing algorithm）。

2.2 一致性驗證以及故障定位

2.2.1 一致性驗證

當采樣數(shù)據(jù)包在出口交換機完成轉發(fā)后，會在控制層檢測控制平面與數(shù)據(jù)平面之間流規(guī)則的一致性。如果服務器中存儲的BFp與BFc相同，且二維向量標簽值PTg［ty-1］與控制器中的正確標簽值CTg［tx-1］相等；那么，數(shù)據(jù)包的實際轉發(fā)路徑與控制器中期望數(shù)據(jù)包的轉發(fā)路徑一致（見算法2 第1）～2）行）。

若控制器中BFp與BFc標簽值不同，而tx與ty的值相等，PTg［ty-1］與CTg［tx-1］也相等，則要考慮字段BF的誤報情況：從BF 字段值初始值開始比較，假設在第i臺交換機，發(fā)現(xiàn)BFp與BFc不一致，檢查PTg［i］與CTg［i］或PTg［i-1］與CTg［i-1］是否相等。若相等，表示第i臺交換機在更新BF字段時，出現(xiàn)了誤報的情況，則將正確的值更新到BFp［i］中；若有一組值不相等，直接返回False（見算法2 第3）～12）行）。驗證算法描述如下。

算法2 驗證算法（Verification algorithm）。

2.2.2 故障交換機定位

在驗證算法中，對于返回False 的標簽組，會進入故障定位算法，查找發(fā)生錯誤的交換機。當PTg［i］與CTg［i］不一致，并且BFp［i］與BFc［i］也不相等時，i對應的交換機即為故障位置（見算法3 第1）～4）行）。對于字段BF 的誤報情況，已經(jīng)在驗證算法中實現(xiàn)修正，所以PTg中的標簽值基本不會出現(xiàn)錯誤情況。定位算法描述如下。

算法3 定位算法（Localization algorithm）。

3 實驗實現(xiàn)與結果分析

3.1 實驗設置

本文通過ns-3 模擬器（https：//www.nsnam.org/）對VeriC模型進行了驗證。ns-3 是一個離散事件網(wǎng)絡模擬器，可以在單個計算機上為用戶提供模擬實驗。本文實驗計算機的配置如下：Intel Core i7 CPU 3.6 GHz 處理器，16 GB 內(nèi)存，Ubuntu 16.04操作系統(tǒng)。

本文在ns-3模擬器中仿真一個k值為4的胖樹結構，胖樹拓撲中包含16 臺主機和20 臺交換機。在仿真實驗中，通過式（2）來設置BF字段的存儲位數(shù)。

本文使用gi（x）中的前四個比特位來設置16 位的BF，在ns-3 模擬器中通過UniformRandomVariableClass 來生成并分配給采樣數(shù)據(jù)包的二維初始向量值和每臺交換機的二維矩陣值［17］。

3.2 結果分析

網(wǎng)絡拓撲構建完成之后，首先使16 臺主機實現(xiàn)互通，完成交換機上流表項的全部安裝。然后隨機選擇一些互通的主機對，對于每一組被選中的主機對，在流量轉發(fā)的路徑中隨機抽取一臺交換機，修改交換機內(nèi)部存儲的流表項，觀察實驗結果。已知數(shù)據(jù)層的轉發(fā)路徑與控制平面的不一致，通過對比VeriC的驗證結果，發(fā)現(xiàn)采樣數(shù)據(jù)包上傳的實際標簽值與控制平面中保存的預期標簽值不一致。

本文通過相對假陰性率和絕對假陰性率來展示VeriC 的實驗結果。對交換機中的流表項進行錯誤設置。m是設置錯誤流表項之后，交換機生成的數(shù)據(jù)包數(shù)量。m1是設置錯誤流表項之后，從入口交換機到達目的地數(shù)據(jù)包數(shù)量。m2是設置錯誤流表項之后，從入口交換機到達目的地，并且報文中的實際標簽值與正確標簽值一致的數(shù)據(jù)包數(shù)量。絕對假陰性率為m2/m，相對假陰性率為m2/m1。

本文將VeriC、2MVeri、VeriDP 三種模型的相對假陰性率和絕對假陰性率進行了對比［16-17］，VeriC 檢測模型的相對假陰性率和絕對假陰性率不會因為Bloom 過濾器位數(shù)的增加而改變這是由于VeriC 檢測模型，并不僅僅依據(jù)Bloom 過濾器中保存的交換機ID值，進行一致性檢測，而是根據(jù)每組流規(guī)則對應CTg［i］和BFc，PTg［i］和BFp的值，檢測數(shù)據(jù)層的轉發(fā)行為是否與控制層一致。在兩組標簽值的共同作用下，消除了Bloom 過濾器的誤報情況，使得一致性檢測更加準確，實驗結果如圖2和圖3所示。

VeriC 模型的定位算法，與交換機接口數(shù)、端口對的數(shù)量無關。假設一個網(wǎng)絡中（inport，outport）對的數(shù)量為n，網(wǎng)絡流量數(shù)為m，每臺交換機的端口數(shù)為p，轉發(fā)路徑表中的最大跳數(shù)為h，三種檢測模型的運算開銷如表2所示。

由表2 可知，使用三種檢測模型定位故障交換機時，VeriDP 的內(nèi)存開銷和算法的時間復雜度均最高，而2MVeri、VeriC 模型不需要構建路徑表。2MVeri 算法的時間復雜度為是O（1）+O（ph），VeriC 算法僅為2O（h），2MVeri 模型通過矩陣的逆，定位故障交換機，當一組流規(guī)則轉發(fā)的交換機數(shù)和端口數(shù)越多，算法的時間復雜度也就越高。VeriC檢測模型驗證算法的時間復雜度大于2MVeri 驗證算法，但綜合考慮，VeriC 模型算法的復雜度總和是最小的。

圖2 相對假陰性率Fig.2 Relative false negative rate

圖3 絕對假陰性率Fig.3 Absolute false negative rate

4 結語

本文提出了VeriC 檢測模型，用于檢測控制平面與數(shù)據(jù)層之間流規(guī)則的一致性。VeriC 檢測模型通過對交換機的數(shù)據(jù)包進行采樣，修改采樣數(shù)據(jù)包，記錄數(shù)據(jù)包的轉發(fā)信息，完成控制平面與數(shù)據(jù)層的一致性檢測，最終找出故障交換機。目前，已經(jīng)在胖樹結構上完成了仿真實驗，實驗證明VeriC 模型能100%準確地進行故障定位。

VeriC模型雖然能夠完成一致性檢測，但是基本條件是控制平面流規(guī)則符合一致性檢查。當多個應用程序同時對網(wǎng)絡進行操作時，生成的流規(guī)則之間可能會存在沖突。所以，未來會對控制平面流規(guī)則的一致性進行檢測。