王 晗 葉家煒 嚴(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ā)出匹配域中有重疊的請(qǐng)求而動(dòng)作域不一致從而造成網(wǎng)絡(luò)狀態(tài)的不一致，我們稱這些匹配域中有重疊的請(qǐng)求為帶有重疊域的請(qǐng)求。根據(jù)OpenFlow規(guī)范，當(dāng)數(shù)據(jù)包到達(dá)某個(gè)交換機(jī)時(shí)，會(huì)在其流表中查找第一條匹配的流表項(xiàng)，所以如果這些帶重疊域的請(qǐng)求直接發(fā)給SDN控制器時(shí)，會(huì)通過SDN控制器在交換機(jī)中生成相應(yīng)流表項(xiàng)，當(dāng)一個(gè)匹配重疊域的數(shù)據(jù)包到達(dá)交換機(jī)時(shí)它只會(huì)匹配到其中一條流表項(xiàng)并執(zhí)行其動(dòng)作指令，其他流表項(xiàng)的動(dòng)作永遠(yuǎn)不會(huì)被執(zhí)行[4]。

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

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

1 相關(guān)研究

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

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

在基于流表項(xiàng)粒度的方案中，F(xiàn)ortNOX[11]是針對(duì)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動(dòng)作。Flover[13]使用Yices SMT解決器檢查策略間的不一致，但僅限于網(wǎng)絡(luò)安全，對(duì)功能一致性沒有提及。

綜上，相比于基于資源粒度的解決方案，基于流表項(xiàng)粒度的解決方案對(duì)北向應(yīng)用的一致性可以進(jìn)行更細(xì)粒度的控制和檢測，而當(dāng)前基于流表項(xiàng)粒度的解決方案中，盡管用到多種數(shù)學(xué)方法，但對(duì)于帶有重疊域的請(qǐng)求大多按照先到先處理的方式，并且對(duì)動(dòng)作域不同的請(qǐng)求進(jìn)行丟棄。然而動(dòng)作域不同不代表動(dòng)作域的沖突，對(duì)某些帶有重疊域的請(qǐng)求而言，其動(dòng)作行為是可以無沖突共存的。上述基于流表項(xiàng)粒度的文章中沒有明確給出對(duì)重疊域請(qǐng)求進(jìn)行整合的方案，因此我們提出了TS檢查器解決方案，對(duì)來自北向應(yīng)用的請(qǐ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ù)包流通情況。它們?cè)谙嗤瑫r(shí)刻都發(fā)起了向同一交換機(jī)S中插入流表項(xiàng)的請(qǐng)求。請(qǐng)求A和C由路由應(yīng)用程序發(fā)出，請(qǐng)求B由監(jiān)控應(yīng)用程序發(fā)出，為了簡化說明，我們把請(qǐng)求A、B、C抽象成表1所示的流表項(xiàng)，實(shí)際上應(yīng)用請(qǐng)求一般是帶有JSON或XML格式數(shù)據(jù)的POST請(qǐng)求，需要經(jīng)過簡單的解析處理才能轉(zhuǎn)化成一條或多條對(duì)應(yīng)的流表項(xiàng)。

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

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

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

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

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

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

2.1 沖突問題

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

2.2 不公平競爭

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

2.3 重疊問題

對(duì)于請(qǐng)求A和B而言，如果不進(jìn)行處理而直接發(fā)往控制器，那么無論其到達(dá)順序如何，對(duì)于數(shù)據(jù)包X而言，其最終只能執(zhí)行一條流表項(xiàng)的動(dòng)作。如果請(qǐng)求A優(yōu)先到達(dá)，那么計(jì)數(shù)動(dòng)作會(huì)被忽略；如果請(qǐng)求B優(yōu)先到達(dá)，那么轉(zhuǎn)發(fā)動(dòng)作會(huì)被忽略。由此可見，數(shù)據(jù)包X的行為不能同時(shí)滿足路由應(yīng)用和監(jiān)控應(yīng)用的意圖，并且可以看到只要請(qǐ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ā)出請(qǐng)求，這些應(yīng)用包括負(fù)載均衡應(yīng)用、監(jiān)控應(yīng)用、路由應(yīng)用等。在這些請(qǐng)求發(fā)往控制器之前，需要經(jīng)過包括四個(gè)模塊的檢查層的處理，在檢查層處理時(shí)，會(huì)根據(jù)策略判斷當(dāng)前請(qǐng)求被接受或被拒絕。被接受的請(qǐng)求將進(jìn)一步發(fā)往控制器進(jìn)行后續(xù)操作，而對(duì)于被拒絕的請(qǐng)求，會(huì)發(fā)送反饋給相應(yīng)的應(yīng)用。

圖1 總體架構(gòu)

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

整個(gè)檢查層包括四個(gè)模塊，其中進(jìn)行了兩次檢查，由沖突檢查模塊和重疊檢查模塊分別負(fù)責(zé)不同的檢查任務(wù)。為了便于闡述，我們把北向應(yīng)用發(fā)起的請(qǐng)求抽象成帶有負(fù)載的POST請(qǐng)求，并用如下所示的JSON對(duì)象進(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é)檢查到來的請(qǐng)求是否與交換機(jī)中現(xiàn)有流表項(xiàng)(表示了當(dāng)前網(wǎng)絡(luò)狀態(tài))之間是否存在沖突。和當(dāng)前網(wǎng)絡(luò)狀態(tài)一致的請(qǐng)求將被轉(zhuǎn)發(fā)到下一步驟(請(qǐng)求隊(duì)列)進(jìn)行后續(xù)處理，而與當(dāng)前網(wǎng)絡(luò)狀態(tài)沖突的請(qǐng)求則會(huì)被丟棄并發(fā)送相應(yīng)反饋。

3.2 請(qǐng)求隊(duì)列

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

3.3 重疊檢查模塊

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

3.4 整合模塊

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

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

圖2 TS檢查器處理流程

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

4.1 沖突檢測算法

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

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

部分檢查算法基于網(wǎng)絡(luò)局部性，如果交換機(jī)中的某條流表項(xiàng)被一個(gè)數(shù)據(jù)包命中過，那么短期內(nèi)它有很大的概率會(huì)被再次匹配?；诖?，我們?cè)跊_突檢查器中設(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)存儲(chǔ)匹配域中的IP地址，以保證在O(n)時(shí)間內(nèi)完成檢測。具體的沖突檢測算法如算法1所示。沖突檢測器的輸出結(jié)果為接受或拒絕某個(gè)請(qǐng)求，對(duì)于被接受的請(qǐng)求將會(huì)發(fā)往請(qǐng)求隊(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 使用請(qǐng)求隊(duì)列解決不公平競爭問題

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

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

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

4.3 重疊檢測算法

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

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

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

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

經(jīng)過重疊檢測器之后，內(nèi)部數(shù)量大于1的重疊集會(huì)被送到整合器進(jìn)行整合，內(nèi)部數(shù)量等于1的重疊集即只有一條請(qǐng)求的集合將被直接發(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)用請(qǐng)求需要接受整合器的進(jìn)一步處理。整合器會(huì)嘗試去整合每個(gè)重疊集中的應(yīng)用請(qǐng)求，它與重疊檢查器一起可以解決第2節(jié)提到的重疊問題。

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

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

續(xù)表3

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

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

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

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

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

表5 原始請(qǐng)求

表6 整合后的請(qǐng)求

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

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

在本節(jié)中，我們使用Ryu控制器[3]和Mininet評(píng)估TS檢查器的性能。Ryu控制器是提供RESTFul接口的輕量級(jí)控制器。Mininet提供了生成OpenFlow虛擬交換機(jī)、虛擬主機(jī)和網(wǎng)絡(luò)拓?fù)涞沫h(huán)境。在實(shí)驗(yàn)環(huán)境中，為了模擬北向應(yīng)用發(fā)出的請(qǐng)求，我們構(gòu)建了軟件請(qǐng)求生成器去模擬應(yīng)用發(fā)出的POST請(qǐng)求，這些請(qǐng)求先經(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)閷?duì)匹配百分比的設(shè)定取決于實(shí)際場景，在實(shí)驗(yàn)中，用圖3所示的拓?fù)洵h(huán)境，分別模擬了以下場景。

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

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

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

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

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

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

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

5.2 性能驗(yàn)證

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

首先，我們?cè)u(píng)估了沖突檢測器的計(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 請(qǐng)求數(shù)量和重疊檢測與整合時(shí)間的關(guān)系

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

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

6 結(jié) 語

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

下一步我們計(jì)劃探索用于三條及以上請(qǐng)求之間的整合機(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.