唐亞哲,張永琪,顏自堅,朱桂英

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

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

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

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

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

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

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

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

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

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

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

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

3 流表中間適配層

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

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

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

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

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

本文采用二元組集合來表征每條流表項的匹配域。例如在表1中,本文定義交換機入端口號為Pin,源IP地址為Sip,源端口號為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)先級約定的不一致也不會導致對數(shù)據(jù)包的錯判,數(shù)據(jù)包絕對不會同時匹配到這2條流表項,這種情況下不需要進行轉(zhuǎn)換。

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

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

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

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

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

4 實驗與測試

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

4.1 占用空間實驗

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

對于任一條規(guī)則,隨著匹配域組合位寬的增加,該規(guī)則占用空間的變化情況如圖4所示。在CPqD交換機中,一條規(guī)則占用的位寬隨著規(guī)則匹配域位寬的增加呈線性增加,而Bloom Filter的一條規(guī)則占用的位圖寬度并不會因為匹配域的增多或者減少而變化,更具有可擴展性。

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

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

η=(MC-MB)/MC

(1)

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

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

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

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

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

TN=TD-TE

(2)

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

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

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

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

η=(TC-TB)/TC

(3)

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

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

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

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

5 結(jié) 語

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

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

[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]. 軟件學報, 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]史少平, 莊雷, 楊思錦. 一種基于預測與動態(tài)調(diào)整負載因子的SDN流表優(yōu)化算法 [J]. 計算機科學, 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.