唐亞哲,張永琪,顏?zhàn)詧?jiān),朱桂英

(1.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安;2.中國(guó)電力科學(xué)院南京分院,210000,南京)

軟件定義網(wǎng)絡(luò)(SDN)[1-3]是一種新型網(wǎng)絡(luò)體系結(jié)構(gòu),它將控制平面與數(shù)據(jù)平面解耦和,具有精細(xì)的流管理屬性。精細(xì)的流管理雖然可以更加精準(zhǔn)地定義網(wǎng)絡(luò),但是也帶來了控制規(guī)則及其內(nèi)存需求的爆炸性增長(zhǎng)。目前,大部分的SDN硬件交換機(jī)將控制規(guī)則部署在三態(tài)內(nèi)容尋址寄存器(TCAM)中,但TCAM非常昂貴且耗電量大,因此流表的可擴(kuò)展性問題,已經(jīng)成為制約SDN網(wǎng)絡(luò)廣泛部署和應(yīng)用的主要因素之一。

為了更好地解決流表項(xiàng)的可擴(kuò)展性問題,目前的研究大致可以分為以下幾類方案:①對(duì)流表本身進(jìn)行優(yōu)化,設(shè)計(jì)軟硬件結(jié)合的流表結(jié)構(gòu)進(jìn)行擴(kuò)容,文獻(xiàn)[4-6]利用TCAM和其他存儲(chǔ)容器設(shè)計(jì)出了新型混合流表結(jié)構(gòu),這種結(jié)構(gòu)將經(jīng)常使用的流表項(xiàng)存儲(chǔ)在TCAM中,其他的細(xì)粒度流表項(xiàng)存儲(chǔ)在其他內(nèi)存中;②通過壓縮流表項(xiàng)的大小和數(shù)量,使原始流表可以容納更多的流表項(xiàng),文獻(xiàn)[7-10]對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行分層,邊緣層使用精確匹配,中心層進(jìn)行標(biāo)簽聚合匹配;③文獻(xiàn)[11]根據(jù)負(fù)載因子動(dòng)態(tài)調(diào)整交換機(jī)流表中流表項(xiàng)的停滯超時(shí)時(shí)間,來保證流表項(xiàng)的空間與時(shí)間上的動(dòng)態(tài)平衡;④文獻(xiàn)[12]利用SDN控制器網(wǎng)絡(luò)視圖將端到端路徑信息編碼到包地址中。

本文基于布隆過濾器(Bloom Filter)[13]設(shè)計(jì)了新型的細(xì)粒度流表項(xiàng)存儲(chǔ)結(jié)構(gòu),在可接受的匹配速度范圍內(nèi)降低細(xì)粒度流表項(xiàng)的內(nèi)存需求和幾乎恒定的流表項(xiàng)查詢時(shí)間。為了使新的流表結(jié)構(gòu)適應(yīng)于不同的控制器并保持語義一致性,設(shè)計(jì)并實(shí)現(xiàn)了控制器和SDN交換機(jī)之間的中間適配層,以轉(zhuǎn)換相應(yīng)的OpenFlow消息。

1 系統(tǒng)架構(gòu)

本文提出的新型流表系統(tǒng)結(jié)構(gòu)如圖1所示。在數(shù)據(jù)平面設(shè)計(jì)新型混合多流表結(jié)構(gòu),結(jié)合TCAM與Bloom Filter共同存儲(chǔ)流表規(guī)則。Bloom Filter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu),利用位數(shù)組可以很簡(jiǎn)潔地表示一個(gè)集合,并能快速判斷一個(gè)元素是否屬于這個(gè)集合。TCAM成本昂貴,查找速度快;Bloom Filter成本低,空間效率高,二者配合能夠?qū)崿F(xiàn)優(yōu)勢(shì)互補(bǔ)。通過對(duì)規(guī)則占用空間的計(jì)算,將范圍匹配較大的規(guī)則或者高頻流規(guī)則放置在TCAM中進(jìn)行匹配,將精細(xì)匹配的規(guī)則放置在Bloom Filter中匹配,達(dá)到充分利用空間、節(jié)省硬件成本的目的。

圖1 新型流表系統(tǒng)結(jié)構(gòu)示意圖

在新型流表系統(tǒng)中,當(dāng)新的數(shù)據(jù)包到達(dá)交換設(shè)備,如果沒有規(guī)則匹配,則觸發(fā)數(shù)據(jù)報(bào)文上報(bào)行為將數(shù)據(jù)包發(fā)送到控制器,控制器生成規(guī)則之后通過FlowMod消息下發(fā)。中間層通過與控制器建立的連接先收到FlowMod消息,通過解析、計(jì)算等一系列轉(zhuǎn)化生成新的流表添加消息,通過與交換機(jī)的連接發(fā)送至交換機(jī)解析并添加規(guī)則,這樣數(shù)據(jù)包便能夠通過規(guī)則查找進(jìn)行匹配并執(zhí)行相應(yīng)的動(dòng)作。

2 混合多流表結(jié)構(gòu)設(shè)計(jì)

新型流表結(jié)構(gòu)是多級(jí)流表結(jié)構(gòu),該結(jié)構(gòu)的第一級(jí)是TCAM流表,連接多級(jí)Bloom Filter流表。每級(jí)Bloom Filter多流表根據(jù)處理動(dòng)作劃分,原始流表中具有相同動(dòng)作的規(guī)則放在同一級(jí)Bloom Filter流表中。每一級(jí)Bloom Filter流表分為匹配域存儲(chǔ)及動(dòng)作執(zhí)行2個(gè)部分。匹配域存儲(chǔ)部分由多個(gè)Bloom Filter位圖組成,每個(gè)位圖負(fù)責(zé)各自匹配域組合,數(shù)據(jù)包進(jìn)入流表時(shí),只取相關(guān)的包頭部分進(jìn)行哈希值計(jì)算,一旦匹配成功則進(jìn)入動(dòng)作執(zhí)行部分執(zhí)行動(dòng)作。多級(jí)Bloom Filter結(jié)構(gòu)如圖2所示,每級(jí)Bloom Filter流表分為B1,…,Bn多個(gè)Bloom Filter子表;P1,…,Pn為不同的匹配域組合。

圖2 多級(jí)Bloom Filter結(jié)構(gòu)示意圖

數(shù)據(jù)包進(jìn)入交換機(jī)后先在TCAM中進(jìn)行規(guī)則查找,如果規(guī)則匹配成功,就執(zhí)行相應(yīng)的動(dòng)作;如果一直匹配不成功,則默認(rèn)將數(shù)據(jù)包傳到第一級(jí)Bloom Filter中進(jìn)行逐個(gè)匹配。當(dāng)數(shù)據(jù)包經(jīng)過某個(gè)Bloom Filter時(shí),該Bloom Filter只在數(shù)據(jù)包包頭提取自己匹配域存儲(chǔ)部分設(shè)定的匹配域的值,匹配成功即執(zhí)行動(dòng)作;匹配失敗則進(jìn)入下一個(gè)Bloom Filter流表中進(jìn)行重復(fù)的匹配流程。

3 流表中間適配層

OpenFlow規(guī)則主要由匹配域和優(yōu)先級(jí)表征,先查看優(yōu)先級(jí)高的規(guī)則,如果優(yōu)先級(jí)高的規(guī)則失配才查看優(yōu)先級(jí)低的規(guī)則,以匹配域與優(yōu)先級(jí)的共同作用來表征規(guī)則的語義。本文根據(jù)規(guī)則間的幾種不同關(guān)系進(jìn)行處理,進(jìn)行等價(jià)的語義轉(zhuǎn)義使得規(guī)則在Bloom Filter多流表中與在原始流表中等價(jià)。

流表中間適配層的規(guī)則轉(zhuǎn)義與整合過程如下。

步驟1 將每一個(gè)流表項(xiàng)放入不同的子表中,按照優(yōu)先級(jí)從高到低遍歷原始流表的每一條流表項(xiàng),流表項(xiàng)的各個(gè)匹配域非通配,則表示該匹配域有值。流表項(xiàng)按照匹配域的組合情況進(jìn)行分類,如圖3所示。該階段將不考慮通配符的匹配字段。

步驟2 將規(guī)則按照語義進(jìn)行等價(jià)轉(zhuǎn)義。每個(gè)表的匹配域組合情況存放在一個(gè)集合中,遍歷這個(gè)集合,兩兩比較規(guī)則匹配域組合及值,將規(guī)則按規(guī)則間語義無關(guān)、規(guī)則語義部分重疊、規(guī)則匹配域完全覆蓋3種關(guān)系進(jìn)行處理。

圖3 原始流表按照匹配域組合分類成多個(gè)子表

本文采用二元組集合來表征每條流表項(xiàng)的匹配域。例如在表1中,本文定義交換機(jī)入端口號(hào)為Pin,源IP地址為Sip,源端口號(hào)為Sp。F1和F2的匹配域集合分別為A={(Pin,1),(Sip,192.168.1.2)}和B={(Sip,192.168.1.2),(Sip,22)}。

規(guī)則語義無關(guān)是指規(guī)則間匹配域內(nèi)容不重疊,遍歷順序即使與優(yōu)先級(jí)約定的不一致也不會(huì)導(dǎo)致對(duì)數(shù)據(jù)包的錯(cuò)判,數(shù)據(jù)包絕對(duì)不會(huì)同時(shí)匹配到這2條流表項(xiàng),這種情況下不需要進(jìn)行轉(zhuǎn)換。

表1 規(guī)則語義部分重疊示例

規(guī)則語義部分重疊是指2個(gè)表之間的匹配域組合情況存在部分交疊,并且交疊部分的匹配域的值相同。存在一個(gè)數(shù)據(jù)包同時(shí)匹配到這2條流表項(xiàng),發(fā)生沖突。

從集合的角度來看,規(guī)則語義部分重疊的轉(zhuǎn)義分3個(gè)步驟:①獲取2個(gè)流表項(xiàng)的匹配域的公共部分;②通過集合差運(yùn)算獲得具有較高優(yōu)先級(jí)的流表項(xiàng)中匹配域的唯一部分;③從第②步中獲得的唯一匹配域中選擇一個(gè)匹配域(例如(f,v)),并將其添加到(f,!v)形式的較低優(yōu)先級(jí)的流表項(xiàng)的匹配字段中。

規(guī)則匹配域完全覆蓋的解決辦法類似于部分覆蓋,分為2個(gè)步驟:①通過集合差運(yùn)算獲得具有較高優(yōu)先級(jí)的流表項(xiàng)的匹配域的唯一部分,即B-A,由于B?A,所以B-A=B-B∩A;②在第①步中獲得的唯一匹配域中選擇一個(gè)匹配域(例如(f,v)),并將其添加到(f,!v)形式的較低優(yōu)先級(jí)流表項(xiàng)的匹配域中。

步驟3 對(duì)規(guī)則匹配域覆蓋的情況,進(jìn)行去重工作。優(yōu)先級(jí)加匹配域的共同作用,有些規(guī)則可能永遠(yuǎn)無法查看到。這樣的規(guī)則下發(fā)到流表中沒有意義,可以在中間層去重以達(dá)到進(jìn)一步優(yōu)化流表空間的目的。

4 實(shí)驗(yàn)與測(cè)試

本文搭建了多級(jí)流表測(cè)試系統(tǒng),選擇Ryu控制器和Floodlight控制器作為SDN控制器。通過修改和替換部分CPqD源代碼,搭建出基于CPqD OpenFlow1.3軟件的OpenFlow交換機(jī)。主要工作包括:①修改lib模塊,支持OpenFlow實(shí)驗(yàn)信息的交換;②用新的Bloom Filter多級(jí)流表替換原始流表;③更換超時(shí)檢測(cè)邏輯和計(jì)數(shù)器邏輯。在此基礎(chǔ)上進(jìn)行功能和性能評(píng)估的實(shí)驗(yàn)。由于篇幅的限制,本文主要進(jìn)行了性能測(cè)試。由于Bloom Filter交換機(jī)基于CPqD軟件交換機(jī)開發(fā),因此所有的性能測(cè)試都是針對(duì)CPqD軟件交換機(jī)。

4.1 占用空間實(shí)驗(yàn)

流表配置接口進(jìn)行流表規(guī)則的配置,選取CPqD開源OpenFlow1.3交換機(jī)為對(duì)比對(duì)象,在Bloom Filter多流表交換機(jī)、CPqD交換機(jī)中進(jìn)行規(guī)則添加。本實(shí)驗(yàn)選用IP五元組(源IP地址、源端口、目的IP地址、目的端口、傳輸層協(xié)議)進(jìn)行流表匹配域的組合。

對(duì)于任一條規(guī)則,隨著匹配域組合位寬的增加,該規(guī)則占用空間的變化情況如圖4所示。在CPqD交換機(jī)中,一條規(guī)則占用的位寬隨著規(guī)則匹配域位寬的增加呈線性增加,而Bloom Filter的一條規(guī)則占用的位圖寬度并不會(huì)因?yàn)槠ヅ溆虻脑龆嗷蛘邷p少而變化,更具有可擴(kuò)展性。

圖4 CPqD交換機(jī)與Bloom Filter多級(jí)流表的一條規(guī)則占用空間對(duì)比

經(jīng)過統(tǒng)計(jì)計(jì)算得到,在各個(gè)位寬情況下,對(duì)于一條規(guī)則占用的空間,Bloom Filter流表的空間優(yōu)化比率為

η=(MC-MB)/MC

(1)

式中:MC表示CPqD交換機(jī)單條規(guī)則占用的空間;MB表示基于Bloom Filter的多級(jí)流表結(jié)構(gòu)中單條規(guī)則占用的空間。

SDN經(jīng)常進(jìn)行精細(xì)的基于流的匹配,運(yùn)用于如細(xì)粒度流量識(shí)別、帶寬管理等場(chǎng)景。表2中Bloom Filter流表在規(guī)則匹配域位寬增加的情況下優(yōu)化比率提高,最高可達(dá)90.7%,在其他匹配域情況下優(yōu)化比率也在48%以上(在32 b情況下沒有優(yōu)化空間是因?yàn)锽loom Filter的一條規(guī)則不論匹配域?qū)挾葹槎嗌?占用的空間都是恒定在33 b)。

表2 Bloom Filter流表一條規(guī)則占用空間優(yōu)化比率

4.2 數(shù)據(jù)包匹配處理耗時(shí)測(cè)試

測(cè)試時(shí),數(shù)據(jù)包發(fā)生器分別發(fā)送流量到Bloom Filter多級(jí)流表、CPqD多級(jí)流表中,并針對(duì)Bloom Filter多級(jí)流表、CPqD多級(jí)流表添加相同的規(guī)則和規(guī)則匹配域,規(guī)則的執(zhí)行動(dòng)作部分都為丟棄操作。由于僅進(jìn)行查找時(shí)間統(tǒng)計(jì),因此數(shù)據(jù)包匹配成功則進(jìn)行丟棄處理。2種交換機(jī)中都進(jìn)行如下時(shí)間統(tǒng)計(jì)

TN=TD-TE

(2)

式中:TN表示數(shù)據(jù)包匹配處理總時(shí)間;TD表示數(shù)據(jù)包匹配完畢并執(zhí)行動(dòng)作的總時(shí)間;TE表示數(shù)據(jù)包進(jìn)入交換機(jī)的耗時(shí)。在CPqD源碼及Bloom Filter多級(jí)流表都加入相應(yīng)的時(shí)間戳進(jìn)行計(jì)算,統(tǒng)計(jì)后求得平均值。

圖5為CPqD交換機(jī)流表匹配處理耗時(shí)的統(tǒng)計(jì)結(jié)果,可見隨著流表數(shù)的增大,CPqD交換機(jī)查找流表的時(shí)間大大增加。隨著規(guī)模的增大,Bloom Filter多級(jí)流表在同等規(guī)模的規(guī)則數(shù)條件下仍保持3～5 μs的查找時(shí)間。

圖5 CPqD交換機(jī)流表匹配處理耗時(shí)統(tǒng)計(jì)結(jié)果

在不同規(guī)則規(guī)模下,Bloom Filter多級(jí)流表的匹配耗時(shí)優(yōu)化比率為

η=(TC-TB)/TC

(3)

式中:TC表示CPqD交換機(jī)的匹配耗時(shí);TB表示基于Bloom Filter的多級(jí)流表結(jié)構(gòu)的匹配耗時(shí)。

表3給出了Bloom Filter流表數(shù)據(jù)包匹配耗時(shí)優(yōu)化比率,由表3可以看出,Bloom Filter多級(jí)流表的數(shù)據(jù)包匹配耗時(shí)優(yōu)化效果明顯,最多可達(dá)99.4%,極大地優(yōu)化了數(shù)據(jù)包處理的耗時(shí),吞吐率。

提高了匹配流程的 表3 Bloom Filter流表數(shù)據(jù)包匹配耗時(shí)優(yōu)化比率

本次實(shí)驗(yàn)針對(duì)的是SDN軟件交換機(jī)的相關(guān)性能指標(biāo),與采用多級(jí)TCAM架構(gòu)的SDN硬件交換機(jī)相比,Bloom Filter查詢效率仍存在一定的差距,但是從軟件交換機(jī)(在云體系中大量使用)的優(yōu)化角度而言,多級(jí)TCAM昂貴、耗電的缺點(diǎn)使其無法大規(guī)模部署,而基于Bloom Filter的多級(jí)流表很好地在實(shí)際部署與性能之間實(shí)現(xiàn)了平衡,便于大規(guī)模應(yīng)用。

5 結(jié) 語

SDN流表優(yōu)化系統(tǒng)集合了Bloom Filter多級(jí)流表與TCAM,在中間適配層進(jìn)行語義轉(zhuǎn)義并解決了語義沖突問題。基于CPqD軟件交換機(jī)進(jìn)行設(shè)計(jì)和實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明空間優(yōu)化率最多可達(dá)90%以上,數(shù)據(jù)包匹配處理耗時(shí)優(yōu)化率最多可達(dá)88%～99%以上,達(dá)到了雙重優(yōu)化的目的。

針對(duì)Bloom Filter的假陽性問題,本文將誤判率限定在10-7,用以降低誤判帶來的影響。同時(shí),在后續(xù)的工作中本系統(tǒng)將引入沖突檢測(cè)和消除機(jī)制,采用多級(jí)流表順序匹配的方法,該方法通過判定匹配次數(shù)來檢測(cè)是否發(fā)生誤判。后續(xù)工作增加沖突鏈表備份機(jī)制來消除誤判,雖然這在一定程度上增加了查詢開銷和存儲(chǔ)開銷,但考慮到極低的假陽性概率,這些開銷可以忽略不計(jì)。

[1] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks [J]. ACM Sigcomm Computer Communication Review, 2008, 38(2): 69-74.

[2] 左青云, 陳鳴, 趙廣松, 等. 基于OpenFlow的SDN技術(shù)研究 [J]. 軟件學(xué)報(bào), 2013, 24(5): 1078-1097. ZUO Qingyun, CHEN Ming, ZHAO Guangsong. Research on OpenFlow-based SDN technologies [J]. Journal of Software, 2013, 24(5): 1078-1097.

[3] VAUGHAN-NICHOLS S J. OpenFlow: the next generation of the network? [J]. Computer, 2011, 44(8): 13-15.

[4] CURTIS A R, MOGUL J C, TOURRILHES J, et al. DevoFlow: scaling flow management for high-performance networks [C]∥Proceedings of the 2011 ACM SIGCOMM Conference. New York, USA: ACM, 2011: 254-265.

[5] KATTA N, ALIPOURFARD O, REXFORD J, et al. CacheFlow: dependency-aware rule-caching for software-defined networks [C]∥Proceedings of the Symposium on SDN Research. New York, USA: ACM, 2016: 6.

[6] LI X, XIE W. CRAFT: a cache reduction architecture for flow tables in software-defined networks [C]∥Proceedings of the 2017 IEEE Symposium on Computers and Communications. Piscataway, NJ, USA: IEEE, 2017: 967-972.

[7] KANAK A, COLIN D, ERIC R. Shadow MACs: scalable label-switching for commodity ether-net [C]∥Proceedings of the Workshop on Hot Topics in Software Defined Networking. New York, USA: ACM, 2014: 157-162.

[8] ARNE S, HOLGER K. Using MAC addresses as efficient routing labels in data centers [C]∥Proceedings of the Workshop on Hot Topics in Software Defined Networking. New York, USA: ACM, 2014: 115-120.

[9] CASADO M, KOPONEN T, SHENKER S, et al. Fabric: a retrospective on evolving SDN [C]∥Proceedings of the First Workshop on Hot Topics in Software Defined Networks. New York, USA: ACM, 2012: 85-90.

[10]IYER A S, MANN V, SAMINENI N R. SwitchReduce: reducing switch state and controller involvement in OpenFlow networks [C]∥ Proceedings of the IEEE IFIP Networking Conference. Piscataway, NJ, USA: IEEE, 2013: 1-9.

[11]史少平, 莊雷, 楊思錦. 一種基于預(yù)測(cè)與動(dòng)態(tài)調(diào)整負(fù)載因子的SDN流表優(yōu)化算法 [J]. 計(jì)算機(jī)科學(xué), 2017, 44(1): 123-127. SHI Shaoping, ZHUANG Lei, YANG Sijin. SDN optimization algorithm based on prediction and dynamic load factor [J]. Computer Science, 2017, 44(1): 123-127.

[12]ALGHADHBAN A, SHIHADA B. Energy efficient SDN commodity switch based practical flow forwarding method [C]∥Proceedings of the Network Operations and Management Symposium. Piscataway, NJ, USA: IEEE, 2016: 784-788.

[13]ANDREI B, MICHAEL M. Network applications of bloom filters: a survey [J]. Internet Mathematics, 2004, 1(4): 485-509.