軟件定義網絡中控制數據平面一致性的驗證

朱夢迪，束永安

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

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

0 引言

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

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

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

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

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

1 VeriC檢測模型系統設計

VeriC 檢測模型由VeriC 模型對應服務器中的驗證子系統、定位子系統以及交換機的數據包處理子系統共同實現。控制器和交換機通過OpenFlow 協議交互的信息，均會被攔截并保存在模型服務器內。

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

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

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

2 詳細設計

2.1 數據包處理系統

2.1.1 數據包采樣

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

2.1.2 生成交換機矩陣

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

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

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

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

2.1.3 字符注釋

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

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

2.1.4 標記采樣數據包

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

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

算法1 數據包處理算法（Packet processing algorithm）。

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

2.2.1 一致性驗證

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

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

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

2.2.2 故障交換機定位

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

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

3 實驗實現與結果分析

3.1 實驗設置

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

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

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

3.2 結果分析

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

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

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

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

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

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

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

4 結語

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

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