TS檢查器：SDN中的兩步?jīng)_突檢測整合機(jī)制

王 晗 葉家煒 嚴(yán) 明(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

0 引 言

軟件定義網(wǎng)絡(luò)(SDN)與OpenFlow[1]的出現(xiàn)和興起為網(wǎng)絡(luò)管理提供了便捷支持。在SDN架構(gòu)中，數(shù)據(jù)平面和控制平面的解耦可以讓網(wǎng)絡(luò)開發(fā)者通過在Docker[2]容器或虛擬機(jī)中開發(fā)北向應(yīng)用程序和調(diào)用SDN控制器提供的北向接口來操縱網(wǎng)絡(luò)設(shè)備[3]。然而，這種高度可編程的架構(gòu)也面臨著一些問題，這些北向應(yīng)用程序因?yàn)樵陂_發(fā)中相互獨(dú)立，故可能因?yàn)榘l(fā)出匹配域中有重疊的請求而動作域不一致從而造成網(wǎng)絡(luò)狀態(tài)的不一致，我們稱這些匹配域中有重疊的請求為帶有重疊域的請求。根據(jù)OpenFlow規(guī)范，當(dāng)數(shù)據(jù)包到達(dá)某個(gè)交換機(jī)時(shí)，會在其流表中查找第一條匹配的流表項(xiàng)，所以如果這些帶重疊域的請求直接發(fā)給SDN控制器時(shí)，會通過SDN控制器在交換機(jī)中生成相應(yīng)流表項(xiàng)，當(dāng)一個(gè)匹配重疊域的數(shù)據(jù)包到達(dá)交換機(jī)時(shí)它只會匹配到其中一條流表項(xiàng)并執(zhí)行其動作指令，其他流表項(xiàng)的動作永遠(yuǎn)不會被執(zhí)行[4]。

因此，北向應(yīng)用程序發(fā)出的請求在被發(fā)送到SDN控制器之前需要經(jīng)過檢查和處理，以消除沖突并保證動作域的一致性。目前針對這種沖突檢測的方案有基于資源粒度和基于流表項(xiàng)粒度兩種方式?？紤]到基于資源粒度的檢測方法無法滿足細(xì)粒度的需求，在本文中，我們提出了基于流表項(xiàng)粒度的TS(Two-Stage)檢查器。TS檢查器是位于應(yīng)用層和控制層之間的檢查層，負(fù)責(zé)過濾、處理北向應(yīng)用程序發(fā)往控制器的所有請求。對于北向應(yīng)用程序發(fā)出的請求，要經(jīng)過TS檢查器的兩次檢查，其中包括四個(gè)模塊，經(jīng)過這些模塊處理，帶有重疊域且動作行為沖突的請求會被檢測并截?cái)啵瑒幼餍袨橐恢碌恼埱髸徽?，之后發(fā)給SDN控制器。

本文提出的TS檢查器支持基于最近最多匹配的部分檢查算法完成沖突檢測，使用基于RingBuffer實(shí)現(xiàn)的線程安全的請求隊(duì)列來緩沖存儲北向請求，在檢查、合并帶重疊域的請求時(shí)，使用字典樹數(shù)據(jù)結(jié)構(gòu)從而保證處理的高效性。我們在Mininet[5]環(huán)境下驗(yàn)證了TS檢查器的部分檢查算法的正確性和檢查器各模塊的性能。

1 相關(guān)研究

關(guān)于檢測SDN環(huán)境下流沖突的方案大體可以分為基于資源粒度和基于流表項(xiàng)粒度兩種?；谫Y源粒度的方案通過把來自北向應(yīng)用程序的請求抽象成策略或意圖從而在資源層次進(jìn)行意圖間的沖突檢測，而基于流表項(xiàng)粒度的方案的思想則是檢測每條流表項(xiàng)，通過和交換機(jī)中現(xiàn)有流表項(xiàng)逐一進(jìn)行對比。

在基于資源粒度的方案中，AuYoung等[8-9]提出的Corybantic及其后續(xù)Athens，將Athens作為北向模塊和控制器之間的攔截者和代理者，接收并處理應(yīng)用程序模塊發(fā)來的操作網(wǎng)絡(luò)資源的抽象意圖，例如虛擬機(jī)的放置等。這需要在對應(yīng)用意圖進(jìn)行抽象且在Athens和應(yīng)用之間建立新的通信接口，而且不能解決細(xì)粒度的資源分配問題。PGA團(tuán)隊(duì)[14]針對網(wǎng)絡(luò)提出了新的抽象模型——圖，但是這種抽象模型不支持set動作。Pyretic[7]在SDN環(huán)境下提出的新的開發(fā)語言和網(wǎng)絡(luò)架構(gòu)，通過引入順序操作符和并行操作符解決沖突問題。但是Pyretic對網(wǎng)絡(luò)開發(fā)人員帶來的新技術(shù)的挑戰(zhàn)，并且這種新型架構(gòu)對于現(xiàn)存的網(wǎng)絡(luò)應(yīng)用而言難以遷移和擴(kuò)展。

在基于流表項(xiàng)粒度的方案中，F(xiàn)ortNOX[11]是針對NOX控制器的擴(kuò)展，它通過基于角色的源認(rèn)證和別名設(shè)置規(guī)則減少來實(shí)時(shí)檢測流表項(xiàng)之間的沖突。VeriFlow[12]是位于SDN控制器和網(wǎng)絡(luò)設(shè)備之間的一層，通過生成等價(jià)集和轉(zhuǎn)發(fā)圖來檢測變量之間的沖突。FlowChecker[10]把流表編碼成二分決策圖并且使用模型檢查器來檢測單個(gè)交換機(jī)內(nèi)的錯(cuò)誤配置，但它也不支持set動作。Flover[13]使用Yices SMT解決器檢查策略間的不一致，但僅限于網(wǎng)絡(luò)安全，對功能一致性沒有提及。

綜上，相比于基于資源粒度的解決方案，基于流表項(xiàng)粒度的解決方案對北向應(yīng)用的一致性可以進(jìn)行更細(xì)粒度的控制和檢測，而當(dāng)前基于流表項(xiàng)粒度的解決方案中，盡管用到多種數(shù)學(xué)方法，但對于帶有重疊域的請求大多按照先到先處理的方式，并且對動作域不同的請求進(jìn)行丟棄。然而動作域不同不代表動作域的沖突，對某些帶有重疊域的請求而言，其動作行為是可以無沖突共存的。上述基于流表項(xiàng)粒度的文章中沒有明確給出對重疊域請求進(jìn)行整合的方案，因此我們提出了TS檢查器解決方案，對來自北向應(yīng)用的請求進(jìn)行沖突檢測和整合。

2 問題描述

考慮如下場景，應(yīng)用層的路由應(yīng)用程序負(fù)責(zé)計(jì)算生成轉(zhuǎn)發(fā)路徑，監(jiān)控應(yīng)用程序負(fù)責(zé)統(tǒng)計(jì)數(shù)據(jù)包流通情況。它們在相同時(shí)刻都發(fā)起了向同一交換機(jī)S中插入流表項(xiàng)的請求。請求A和C由路由應(yīng)用程序發(fā)出，請求B由監(jiān)控應(yīng)用程序發(fā)出，為了簡化說明，我們把請求A、B、C抽象成表1所示的流表項(xiàng)，實(shí)際上應(yīng)用請求一般是帶有JSON或XML格式數(shù)據(jù)的POST請求，需要經(jīng)過簡單的解析處理才能轉(zhuǎn)化成一條或多條對應(yīng)的流表項(xiàng)。

表1 來自兩個(gè)應(yīng)用的三條請求

根據(jù)OpenFlow規(guī)范，每條流表項(xiàng)都隱式地包含一個(gè)計(jì)數(shù)器[4]，在本文中為了便于闡述問題，我們將計(jì)數(shù)器行為視為一個(gè)顯式的count動作，實(shí)際上當(dāng)動作域沒有任何設(shè)定時(shí)就會執(zhí)行count動作。

如果此時(shí)，交換機(jī)S中存在如表2所示的一條流表項(xiàng)。

表2 交換機(jī)S中的一條流表項(xiàng)

在這個(gè)場景下，如果對應(yīng)用程序請求不作檢測處理而直接交給控制器，那么會有兩個(gè)問題：1)請求C和id=5的流表項(xiàng)存在沖突，對滿足src_ip=192.0.0.1/32條件的數(shù)據(jù)流其動作行為不一致，現(xiàn)存流表項(xiàng)的動作是丟棄，而請求C的動作是轉(zhuǎn)發(fā)到3號端口；2)請求A和請求B存在重疊域，即src_ip=20.0.0.1/32且dst_ip=20.0.0.2/32，對于滿足重疊域條件的數(shù)據(jù)包，只能執(zhí)行轉(zhuǎn)發(fā)或計(jì)數(shù)其中一個(gè)動作，并且執(zhí)行的具體動作也因請求A、B到達(dá)的先后順序而未知，而實(shí)際上轉(zhuǎn)發(fā)和計(jì)數(shù)分別是由路由應(yīng)用和監(jiān)控應(yīng)用負(fù)責(zé)的，并且是兩個(gè)互不沖突的動作，所以可以被整合，請求B和C同理。

因此，在上述場景下，對于這些帶有重疊域并可能和現(xiàn)存流表項(xiàng)沖突的請求，我們可以歸納出在原有架構(gòu)中存在如下所述的三個(gè)問題。

2.1 沖突問題

如果一個(gè)來自北向應(yīng)用的請求交換機(jī)中某條現(xiàn)有流表項(xiàng)存在匹配域的交集并且因動作域不一致而產(chǎn)生沖突，我們稱之為沖突問題。在上述場景中，請求C與id=5的流表項(xiàng)間存在沖突問題。沖突問題在文獻(xiàn)[10-12]中得到了足夠的重視。它們使用了不同的數(shù)學(xué)公式或方法以消除和當(dāng)前網(wǎng)絡(luò)狀態(tài)有沖突的請求從而保證網(wǎng)絡(luò)安全。在本文中，我們受到啟發(fā)并提出更高效地解決沖突問題的方案。

2.2 不公平競爭

在請求A和B是幾乎同時(shí)發(fā)出的前提下，受實(shí)際網(wǎng)絡(luò)因素控制，最終到達(dá)控制器的順序總有先后之分，按照先到先處理的原則，對于滿足其重疊匹配域的數(shù)據(jù)包X而言，其最終動作取決于優(yōu)先到達(dá)控制器并生成的相應(yīng)流表項(xiàng)的請求。在這種情況下，對于后到達(dá)控制器的請求是不公平的，并且請求到達(dá)的先后順序是受實(shí)際網(wǎng)絡(luò)情況影響而不可預(yù)測的。我們稱這種幾乎同時(shí)發(fā)出卻因到達(dá)時(shí)間的微小差別造成的現(xiàn)象為不公平競爭。在本文中，我們使用請求隊(duì)列來存儲短時(shí)間內(nèi)到達(dá)的多個(gè)請求，通過批處理來解決部分不公平競爭的問題。

2.3 重疊問題

對于請求A和B而言，如果不進(jìn)行處理而直接發(fā)往控制器，那么無論其到達(dá)順序如何，對于數(shù)據(jù)包X而言，其最終只能執(zhí)行一條流表項(xiàng)的動作。如果請求A優(yōu)先到達(dá)，那么計(jì)數(shù)動作會被忽略；如果請求B優(yōu)先到達(dá)，那么轉(zhuǎn)發(fā)動作會被忽略。由此可見，數(shù)據(jù)包X的行為不能同時(shí)滿足路由應(yīng)用和監(jiān)控應(yīng)用的意圖，并且可以看到只要請求中包含重疊域，則最終行為必不能滿足原始意圖。我們稱這個(gè)由重疊域帶來的問題為重疊問題，這也是被大多數(shù)基于流表項(xiàng)粒度的沖突解決方案所忽略的問題。

為了解決上述三個(gè)問題，我們提出了TS檢查器。

3 架構(gòu)設(shè)計(jì)

在本節(jié)中，我們將詳細(xì)介紹TS檢查器。SDN架構(gòu)把網(wǎng)絡(luò)抽象成三層，從北到南依次為：應(yīng)用層、控制層、基礎(chǔ)設(shè)備層。和位于控制層與基礎(chǔ)設(shè)備層之間進(jìn)行攔截的VeriFlow不同[12]，我們把TS檢查器定位于應(yīng)用層與控制層之間。如圖1所示，在應(yīng)用層有多個(gè)部署于Docker的獨(dú)立應(yīng)用向控制器發(fā)出請求，這些應(yīng)用包括負(fù)載均衡應(yīng)用、監(jiān)控應(yīng)用、路由應(yīng)用等。在這些請求發(fā)往控制器之前，需要經(jīng)過包括四個(gè)模塊的檢查層的處理，在檢查層處理時(shí)，會根據(jù)策略判斷當(dāng)前請求被接受或被拒絕。被接受的請求將進(jìn)一步發(fā)往控制器進(jìn)行后續(xù)操作，而對于被拒絕的請求，會發(fā)送反饋給相應(yīng)的應(yīng)用。

圖1 總體架構(gòu)

與Athens和Pyretic方案不同，我們的檢查層方案僅需對現(xiàn)有應(yīng)用進(jìn)行微小改動——添加反饋處理模塊，而這可以通過補(bǔ)丁或擴(kuò)展的方式實(shí)現(xiàn)。

整個(gè)檢查層包括四個(gè)模塊，其中進(jìn)行了兩次檢查，由沖突檢查模塊和重疊檢查模塊分別負(fù)責(zé)不同的檢查任務(wù)。為了便于闡述，我們把北向應(yīng)用發(fā)起的請求抽象成帶有負(fù)載的POST請求，并用如下所示的JSON對象進(jìn)行描述。

“requests”: [{

“id”: “00070”,

“idle_time”: “3600”,

“hard_time”: “3600”,

“priority”: “20”,

“match”: {

“src_ip”: “192.168.1.1/32”

“eth_type”: “0x800”

},

“actions”: “drop”

},]

下面將分別描述四個(gè)模塊的主要功能。

3.1 沖突檢查模塊

這是第一個(gè)檢查步驟，負(fù)責(zé)檢查到來的請求是否與交換機(jī)中現(xiàn)有流表項(xiàng)(表示了當(dāng)前網(wǎng)絡(luò)狀態(tài))之間是否存在沖突。和當(dāng)前網(wǎng)絡(luò)狀態(tài)一致的請求將被轉(zhuǎn)發(fā)到下一步驟(請求隊(duì)列)進(jìn)行后續(xù)處理，而與當(dāng)前網(wǎng)絡(luò)狀態(tài)沖突的請求則會被丟棄并發(fā)送相應(yīng)反饋。

3.2 請求隊(duì)列

請求隊(duì)列是一個(gè)基于環(huán)形隊(duì)列實(shí)現(xiàn)的先進(jìn)先出的隊(duì)列，用于存放被沖突檢查模塊過濾后的請求。

3.3 重疊檢查模塊

在此模塊中執(zhí)行第二次檢查，負(fù)責(zé)檢查隊(duì)列中的請求之間是否存在重疊域，若有重疊域存在，則請求被發(fā)往下一個(gè)模塊，否則會被標(biāo)志為有效請求并跳過整合模塊被直接發(fā)往SDN控制器。上述三個(gè)模塊共同構(gòu)成了消費(fèi)者- 生產(chǎn)者模式，沖突檢查模塊負(fù)責(zé)向請求隊(duì)列中輸入數(shù)據(jù)，而重疊檢查模塊負(fù)責(zé)批量消費(fèi)請求隊(duì)列中的數(shù)據(jù)。

3.4 整合模塊

嘗試整合帶有重疊域的請求。如果這些帶重疊域請求的動作域指令是相互沖突的，則被丟棄并發(fā)送相應(yīng)反饋，否則就通過策略去整合請求，將整合之后的請求發(fā)給SDN控制器。

四個(gè)步驟的處理流程可以用圖2概括。

圖2 TS檢查器處理流程

4 系統(tǒng)實(shí)現(xiàn)

4.1 沖突檢測算法

在檢查層對請求進(jìn)行的第一步處理是進(jìn)行沖突檢測。沖突檢測用于檢測一個(gè)新到來的請求是否與交換機(jī)中現(xiàn)有流表項(xiàng)規(guī)則有沖突。因?yàn)榻粨Q機(jī)中現(xiàn)有流表項(xiàng)規(guī)則表示了當(dāng)前網(wǎng)絡(luò)狀態(tài)，這個(gè)步驟對于消除與網(wǎng)絡(luò)狀態(tài)沖突的請求從而維護(hù)網(wǎng)絡(luò)狀態(tài)一致性必不可少。

文獻(xiàn)[10-13]各自使用了不同的方法去完成沖突檢測的任務(wù)，它們?nèi)炕跈z查新插入請求或流表項(xiàng)與交換機(jī)中所有流表項(xiàng)之間的沖突。這些方法很完善但在某些場景下并非必要且是低效的。根據(jù)網(wǎng)絡(luò)局部性理論[15]可知，近期內(nèi)被命中的流表項(xiàng)短時(shí)間內(nèi)很可能被再次命中。所以對于某些對時(shí)延性要求較高而對網(wǎng)絡(luò)狀態(tài)一致性并不具有嚴(yán)格要求的場景而言，我們提出了用戶可配置的基于最近最多匹配的部分檢查這一折衷算法，使用者可以根據(jù)場景需求選擇部分檢查的覆蓋率，當(dāng)覆蓋率為100%時(shí)退化為全部檢查。

部分檢查算法基于網(wǎng)絡(luò)局部性，如果交換機(jī)中的某條流表項(xiàng)被一個(gè)數(shù)據(jù)包命中過，那么短期內(nèi)它有很大的概率會被再次匹配?；诖?，我們在沖突檢查器中設(shè)計(jì)了最近最多匹配的緩存數(shù)據(jù)結(jié)構(gòu)(LRM)，它用于保存每個(gè)交換機(jī)最近最頻繁被匹配到的流表項(xiàng)。為找到最近最多匹配的流表項(xiàng)，可使用流表項(xiàng)中的idle字段。根據(jù)OpenFlow規(guī)范，idle字段表示距離上一次被匹配的時(shí)間間隔，這反映了此條流表項(xiàng)的活躍度。

在沖突檢測算法中，我們使用Trie字典樹數(shù)據(jù)結(jié)構(gòu)存儲匹配域中的IP地址，以保證在O(n)時(shí)間內(nèi)完成檢測。具體的沖突檢測算法如算法1所示。沖突檢測器的輸出結(jié)果為接受或拒絕某個(gè)請求，對于被接受的請求將會發(fā)往請求隊(duì)列模塊。

算法1 沖突檢測算法input：acomingrequest，flowentries’idstoredinLRMforfidinLRM： flow=get＿flow(fid) trie=build＿trie(flow->match)ifrequest．matchisintrie： request＿queue．push(request)else： reject(request)

4.2 使用請求隊(duì)列解決不公平競爭問題

經(jīng)過沖突檢測器過濾的請求被發(fā)往請求隊(duì)列。請求隊(duì)列在檢查層的作用是存儲請求便于后續(xù)的重疊檢查器進(jìn)行處理。請求隊(duì)列的上游是沖突檢測器，下游是重疊檢測器，上游的處理時(shí)間是O(n)，并且在實(shí)際實(shí)現(xiàn)中可以將沖突檢測器實(shí)現(xiàn)為多線程并行處理，而下游處理時(shí)間是O(n2)。一方面請求隊(duì)列可以作為緩沖隊(duì)列去緩解消費(fèi)速度落后于生產(chǎn)速度的情況，另一方面，正如在第3節(jié)中提到的，請求隊(duì)列可以通過緩存極短時(shí)間內(nèi)到達(dá)的多個(gè)請求，在滿足實(shí)時(shí)性要求的同時(shí)便于下游進(jìn)行批處理從而消除部分不公平競爭的問題。即對于被處理的同一批請求，在其優(yōu)先級相同的情況下，不會因?yàn)槠涞竭_(dá)時(shí)間先后的微小差距而被區(qū)別對待。當(dāng)請求隊(duì)列中有數(shù)據(jù)時(shí)，便會通過信號量方式通知下游重疊檢查器，重疊檢查器會取出當(dāng)前請求隊(duì)列中所有請求，進(jìn)行后續(xù)處理。

Corybantic和Athens解決方案對于何時(shí)進(jìn)行一次策略整合沒有給出明確的說明[8-9]，它們的重點(diǎn)在于整合的決策算法。而請求隊(duì)列可以解決這個(gè)問題。

為實(shí)現(xiàn)請求隊(duì)列，我們底層使用了RingBuffer環(huán)形隊(duì)列結(jié)構(gòu)，配合鎖和信號量以保證線程安全和對下游線程的喚醒。

4.3 重疊檢測算法

在沖突檢查步驟中，僅僅篩選出了與當(dāng)前網(wǎng)絡(luò)狀態(tài)不沖突的應(yīng)用請求，而面對在短時(shí)間內(nèi)收到的一批應(yīng)用請求時(shí)，其匹配域中很可能存在重疊從而導(dǎo)致需要進(jìn)行進(jìn)一步整合。重疊檢測器就是為了解決這個(gè)問題。

在實(shí)現(xiàn)算法上，重疊檢測算法與沖突檢測算法相似，不同的是，沖突檢測算法是比較單個(gè)輸入請求與交換機(jī)流表項(xiàng)，而重疊檢測算法的輸入是一批請求，重疊檢測器需要從這些請求中過濾掉其動作指令相互矛盾的請求，將可整合的請求發(fā)往之后的整合步驟進(jìn)行進(jìn)一步處理。

因?yàn)榇蠖鄶?shù)重疊域是由于IP地址的交集造成的，我們這里以源IP地址為例進(jìn)行說明。IPv4地址為32位，而在OpenFlow協(xié)議中可以使用通配符匹配，故在字典樹中我們使用高度最多為32位的字典樹即可存儲IP地址。

起初，字典樹數(shù)據(jù)結(jié)構(gòu)為空，當(dāng)收到請求隊(duì)列的喚醒信號時(shí)，它去獲取請求隊(duì)列中的全部請求，假設(shè)此時(shí)共有k個(gè)請求，重疊檢查器會去遍歷這k個(gè)請求，嘗試向字典樹中插入每個(gè)請求的源IP地址，并用tag位記錄其優(yōu)先級。在插入前，檢查器會檢測當(dāng)前字典樹中是否有其前綴IP地址。若沒有，則直接插入；若已有前綴IP地址發(fā)現(xiàn)，當(dāng)前請求則會被記錄到由其前綴IP地址的請求構(gòu)成的集合中。即當(dāng)k個(gè)請求遍歷結(jié)束之后，會有多個(gè)集合生成，每個(gè)集合中至少有一條或多條應(yīng)用請求，同一集合中的應(yīng)用請求之間具有重疊域關(guān)系，稱之為重疊集。若重疊集中只有一條請求，說明不存在與之重疊的請求。

經(jīng)過重疊檢測器之后，內(nèi)部數(shù)量大于1的重疊集會被送到整合器進(jìn)行整合，內(nèi)部數(shù)量等于1的重疊集即只有一條請求的集合將被直接發(fā)到SDN控制器，提前結(jié)束了整個(gè)檢查流程。重疊檢測算法見算法2。

算法2 重疊檢測算法input：queuedrequestsfromRequestQueuetrie=Noneoverlap＿sets=Noneforrequestinqueued＿requests： node=in＿trie(trie，request) ifnode： overlap＿sets．set＿of＿(node)．a(chǎn)ppend(request) else： overlap＿sets．a(chǎn)dd({request}) trie=insert＿trie(trie，request)forr＿setinoverlap＿sets： iflen(r＿set)is1： transfer＿to＿controller(r＿set) else： transfer＿to＿next＿stage(r＿set)

4.4 整合算法

重疊檢查器挑選出了需要被整合的重疊集，其中的應(yīng)用請求需要接受整合器的進(jìn)一步處理。整合器會嘗試去整合每個(gè)重疊集中的應(yīng)用請求，它與重疊檢查器一起可以解決第2節(jié)提到的重疊問題。

在整合含有重疊域的請求時(shí)，需要分析每個(gè)請求的action字段以判斷請求之間是否存在相互矛盾的動作。根據(jù)OpenFlow規(guī)范，有drop、forward、set等顯式的動作，如表3所示[4]。如果我們把count動作也視為顯式動作，那么這四種動作之間的動作域關(guān)系表可以用表4展示。

表3 OpenFlow協(xié)議動作域

續(xù)表3

表4 動作域關(guān)系表

正如表4所示，對任意兩個(gè)請求的動作關(guān)系存在三種可能情況。No表示不存在矛盾，所以請求可以被整合。Yes表示存在矛盾，所以相關(guān)請求要么被丟棄要么按照預(yù)先約定的策略進(jìn)行處理。Maybe表示需要根據(jù)具體的動作目標(biāo)來進(jìn)一步判斷是否存在矛盾沖突。例如forward動作，它可能有多個(gè)目標(biāo)端口，當(dāng)其目標(biāo)端口不同時(shí)，則相互沖突，否則就視為一致。

實(shí)際環(huán)境中在一個(gè)重疊集中可能會存在超過兩條的應(yīng)用請求，但在本文中，我們的目標(biāo)是先解決兩個(gè)含重疊域的請求的整合，后續(xù)的工作將會將重點(diǎn)放在對三條及以上的請求的整合處理。因此在整合器這一步中我們暫時(shí)只處理包含兩條請求的重疊集。

假設(shè)重疊集中含有A、B兩個(gè)請求，直接將A和B請求發(fā)往SDN控制器會引起問題，正如第2節(jié)所描述的。整合器會按照策略生成一條新的請求C，請求C通過計(jì)算A和B的匹配域交集作為C的匹配域，A和B的動作域并集作為C的動作域，A和B中較高的優(yōu)先級作為C的優(yōu)先級。然后將請求三元組發(fā)給SDN控制器。至此，TS檢查器結(jié)束。

為了更清楚地解釋整合算法，我們以表5中的請求A和B為例，首先forward動作和set動作可以共存，所以兩個(gè)請求可以被整合。根據(jù)整合算法，請求A和請求B的匹配域交集為{src_ip=192.0.0.1/32, dst_ip=192.0.0.0/16}，其動作域的并集為{set_field:401->vlan_id, forward:1}。于是新生成的請求C和原請求A和B如表6所示。整合算法見算法3。

表5 原始請求

表6 整合后的請求

算法3 整合算法input：overlappingsetswhichhavetworequestsaccepted＿requests={}forrequestsinoverlappingsets： a，b=request ifcontradict(a．a(chǎn)ctions，b．a(chǎn)ctions)： reject(a，b) sendfeedbacktoapplicationsofa，b else： c=newrequest common＿match=intersection(a．match，b．match) c．match=common＿match c．a(chǎn)ctions=Union(a．a(chǎn)ctions，b．a(chǎn)ctions) c．priority=max(a．priority，b．priority) accepted＿requests．a(chǎn)ppend([c，a，b])transfer＿to＿controller(accepted＿requests)

到目前為止，TS檢查器結(jié)束所有檢查步驟。新到來的請求必須經(jīng)過沖突檢查器以保證其行為和當(dāng)前流表項(xiàng)一致，然后經(jīng)過重疊檢查器進(jìn)行請求間的重疊檢測。經(jīng)過這兩個(gè)步驟的檢查，被接受的請求會被發(fā)往SDN控制器，而帶有重疊域的請求被送往整合器，其會選擇具有可合并動作域的請求進(jìn)行整合，隨即將整合結(jié)果發(fā)往SDN控制器，對于不可進(jìn)行整合的請求將會被拒絕并且發(fā)送反饋給相應(yīng)應(yīng)用。

5 實(shí)驗(yàn)驗(yàn)證

在本節(jié)中，我們使用Ryu控制器[3]和Mininet評估TS檢查器的性能。Ryu控制器是提供RESTFul接口的輕量級控制器。Mininet提供了生成OpenFlow虛擬交換機(jī)、虛擬主機(jī)和網(wǎng)絡(luò)拓?fù)涞沫h(huán)境。在實(shí)驗(yàn)環(huán)境中，為了模擬北向應(yīng)用發(fā)出的請求，我們構(gòu)建了軟件請求生成器去模擬應(yīng)用發(fā)出的POST請求，這些請求先經(jīng)過解析器解析后可以映射成多條即將插入到交換機(jī)中的流表項(xiàng)，之后經(jīng)過TS檢查器層過濾，將過濾結(jié)果發(fā)給SDN控制器。在實(shí)驗(yàn)環(huán)境中，我們使用的服務(wù)器為Dell R730，搭配了2個(gè)主頻為2.4 GHz的Intel Xeon CPU，并劃分成24個(gè)邏輯CPU。

5.1 正確性驗(yàn)證

在正確性驗(yàn)證中，我們主要驗(yàn)證了基于最近最多匹配的部分檢查算法。因?yàn)閷ζヅ浒俜直鹊脑O(shè)定取決于實(shí)際場景，在實(shí)驗(yàn)中，用圖3所示的拓?fù)洵h(huán)境，分別模擬了以下場景。

圖3 拓?fù)浣Y(jié)構(gòu)

場景1：數(shù)據(jù)包流量平均分布于6臺主機(jī)之間。

場景2：50%的流量集中于主機(jī)A與主機(jī)D之間，50%的數(shù)據(jù)包流量平均分布于其他主機(jī)通信。

場景3：90%的流量集中于主機(jī)A與D之間，10%的流量平均分布于其他主機(jī)間。

在三種場景中，我們先后設(shè)置沖突檢測器的匹配百分比為60%和100%，并對比了三種場景下沖突檢測器的過濾結(jié)果，如圖4所示，縱坐標(biāo)為檢測出有沖突的請求數(shù)。

圖4 過濾結(jié)果對比

可以看出，在場景3中60%和100%的匹配百分比過濾結(jié)果相差無幾，而在場景1和場景2中，卻存在明顯差距。由此可以看到基于最近最多匹配的部分檢查算法適用于流量集中于部分鏈路的情況。

5.2 性能驗(yàn)證

在性能驗(yàn)證中，我們對TS檢查器層的沖突檢測器和重疊檢測器及整合器分別進(jìn)行了不同流表項(xiàng)和請求數(shù)量時(shí)的測試。我們構(gòu)建了一個(gè)SDN控制器、三個(gè)ovs交換機(jī)，每個(gè)交換機(jī)分別連接2個(gè)主機(jī)的拓?fù)洵h(huán)境。

首先，我們評估了沖突檢測器的計(jì)算時(shí)間。因?yàn)闆_突檢測器中使用了基于最近最多匹配的部分檢查算法，所以其處理時(shí)間取決于不同場景下指定的匹配百分比。我們分別測試了100%匹配、66%匹配、33%匹配和20%匹配。從圖5可以看出，隨著流表項(xiàng)數(shù)量的增加，所耗費(fèi)的檢查時(shí)間呈線性增長。并且隨著匹配百分比的升高，耗費(fèi)的檢查時(shí)間也逐漸增長。

圖5 流表項(xiàng)數(shù)量與沖突檢測時(shí)間的關(guān)系

之后我們驗(yàn)證了重疊檢測器和整合器這兩個(gè)步驟共同耗費(fèi)的處理時(shí)間。如圖6所示，隨著重疊集數(shù)量的增加，處理時(shí)間線性增加。這其中大部分時(shí)間用于構(gòu)建和更新字典樹，也就是在重疊檢測器這一步驟中，而整合器步驟耗時(shí)很短。

圖6 請求數(shù)量和重疊檢測與整合時(shí)間的關(guān)系

最后我們測試了一個(gè)完整的處理流程，使用三個(gè)請求生成器分別模擬三個(gè)應(yīng)用先后生成了1 000個(gè)請求，三個(gè)交換機(jī)中的流表項(xiàng)數(shù)量分別為6 000，并且設(shè)置沖突檢測器的匹配百分比為30%。如表7所示，在此環(huán)境中，對于每個(gè)請求而言沖突檢測器處理耗時(shí)小于1 ms，重疊檢測器和整合器耗時(shí)略多，但仍然小于1 ms。

表7 檢查步驟與耗費(fèi)時(shí)間

6 結(jié) 語

我們設(shè)計(jì)、實(shí)現(xiàn)并評估了TS檢查器——一個(gè)用于在SDN架構(gòu)中檢測沖突并進(jìn)行整合以保證網(wǎng)絡(luò)狀態(tài)一致性的機(jī)制。TS檢查器作為檢查層位于應(yīng)用層與控制層之間，為高效完成沖突檢測，使用字典樹數(shù)據(jù)結(jié)構(gòu)和基于最近最多匹配的部分檢查算法來減少某些場景下的平均檢查時(shí)間。設(shè)計(jì)了請求隊(duì)列以輔助下游實(shí)現(xiàn)請求間的重疊檢查和整合。在整合階段，我們提出了整合兩個(gè)含重疊域請求的方法。最后使用Mininet驗(yàn)證了設(shè)計(jì)，并進(jìn)行了性能評估。

下一步我們計(jì)劃探索用于三條及以上請求之間的整合機(jī)制，并且將TS檢查器擴(kuò)展到多控制器環(huán)境中。

[1] OpenFlow: a southbound protocol[OL]. https://www.opennetworking.org/sdn-resources/openflow.

[2] Docker: an app engine[OL]. https://www.docker.com/.

[3] Ryu controller: an open source SDN controller[OL]. https://osrg.github.io/ryu/.

[4] OpenFlow switch specification[OL]. https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.4.0.pdf.

[5] Mininet[OL]. http://mininet.org/.

[6] Anderson C J, Foster N, Guha A, et al. NetKAT: semantic foundations for networks[C]// ACM Sigplan-Sigact Symposium on Principles of Programming Languages. ACM, 2014:113- 126.

[7] Monsanto C, Reich J, Foster N, et al. Composing software-defined networks[C]// Usenix Conference on Networked Systems Design and Implementation. USENIX Association, 2013:1- 14.

[8] Mogul J C, AuYoung A, Banerjee S, et al. Corybantic: towards the modular composition of SDN control programs[C]//Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks. ACM, 2013: 1- 7.

[9] AuYoung A, Ma Y, Banerjee S, et al. Democratic resolution of resource conflicts between sdn control programs[C]//Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. ACM, 2014: 391- 402.

[10] Al-Shaer E, Al-Haj S. FlowChecker: Configuration analysis and verification of federated OpenFlow infrastructures[C]//Proceedings of the 3rd ACM workshop on Assurable and usable security configuration. ACM, 2010: 37- 44.

[11] Porras P, Shin S, Yegneswaran V, et al. A security enforcement kernel for OpenFlow networks[C]//Proceedings of the first workshop on Hot topics in software defined networks. ACM, 2012: 121- 126.

[12] Khurshid A, Zhou W, Caesar M, et al. Veriflow: Verifying network-wide invariants in real time[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 467- 472.

[13] Son S, Shin S, Yegneswaran V, et al. Model checking invariant security properties in OpenFlow[C]//Communications (ICC), 2013 IEEE International Conference on. IEEE, 2013: 1974- 1979.

[14] Prakash C, Lee J, Turner Y, et al. Pga: Using graphs to express and automatically reconcile network policies[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 29- 42.

[15] Jain R. Characteristics of destination address locality in computer networks: a comparison of caching schemes[J]. Computer networks and ISDN systems, 1990, 18(4): 243- 254.