唐菀，馮偉，楊喜敏，田野

(中南民族大學 計算機科學學院，武漢 430074)

當前，學術(shù)界和工業(yè)界對業(yè)務(wù)可擴展、網(wǎng)絡(luò)資源虛擬化方面進行了大量研究，以期探尋能適應互聯(lián)網(wǎng)技術(shù)及業(yè)務(wù)高速發(fā)展的網(wǎng)絡(luò)架構(gòu).一種新的網(wǎng)絡(luò)架構(gòu)——軟件定義網(wǎng)絡(luò)(Software-Defined Networking，SDN)應運而生，SDN解耦網(wǎng)絡(luò)的控制邏輯和數(shù)據(jù)轉(zhuǎn)發(fā)邏輯，實現(xiàn)對網(wǎng)絡(luò)的集中管控，利用可編程特性支持網(wǎng)絡(luò)業(yè)務(wù)的創(chuàng)新[1-3].OpenFlow協(xié)議為SDN南向交互的事實通信標準，在支持OpenFlow協(xié)議的交換機中存儲著一個或多個流表.每一個流表由多條表項組成，支持抽象轉(zhuǎn)發(fā)和控制規(guī)范，實現(xiàn)數(shù)據(jù)流線性匹配.隨著業(yè)務(wù)控制需求增加和網(wǎng)絡(luò)規(guī)模擴大，流表空間有限的存儲和有效利用等成為近些年基于OpenFlow的SDN網(wǎng)絡(luò)關(guān)鍵問題，受到業(yè)界研究者廣泛關(guān)注.希望本文的工作對SDN中流表存儲優(yōu)化的研究提供借鑒，能對流表一致性和流表安全性問題的解決有一定啟發(fā).

1 流表空間問題描述

SDN中的OpenFlow流表空間有限性存儲和有效性管理問題，根據(jù)側(cè)重點不同，可歸納為以下三方面：

(1)硬件電路復雜、價格不菲，且存儲容量不足.OpenFlow交換機中存儲流表的三態(tài)內(nèi)容尋址寄存器(Ternary Content Addressable Memory, TCAM)硬件電路復雜，價格較為昂貴.此外，TCAM支持表項的并行查找，大量的匹配操作使得其功耗開銷大，故商用SDN交換機中流表存儲空間十分有限，如Pica8 P-3290交換機支持存儲最大的TCAM表項數(shù)為2000條[4-6].

(2)大量業(yè)務(wù)和固有流表超時機制會帶來大量流表存儲的需求.SDN提供基于流的細粒度控制，一條數(shù)據(jù)流可能匹配多條細粒度表項，分組分類流表的規(guī)模不斷擴大；OpenFlow固有的流表超時機制會導致大量無用表項滯留在交換機中，使交換機需存儲的流表數(shù)顯著增加.過多的流表存儲導致流表更新的速度降低[1]，流表匹配率下降.

(3)流表表項匹配域擴大，結(jié)構(gòu)越來越復雜.OpenFlow協(xié)議采用扁平化設(shè)計，囊括1～4層的協(xié)議信息，表項匹配域不斷擴大，從OpenFlow1.0所支持的12個匹配字段，不斷擴展到OpenFlow1.5的45個匹配字段.表項結(jié)構(gòu)也變得越來越復雜[7,8]，對TCAM流表空間優(yōu)化管理帶來巨大挑戰(zhàn)，大量多元匹配影響了流表查詢效率，從而大大降低了OpenFlow流表空間有效利用率.

現(xiàn)有針對OpenFlow流表空間有限存儲和有效利用問題的解決方案較為零散，本文通過對相關(guān)文獻資料提出的研究方案進行定性分析，發(fā)現(xiàn)主要的研究工作大多是從硬件、軟件或硬軟件結(jié)合的3個角度來優(yōu)化OpenFlow流表空間管理，因此將這些解決方案歸納為3類：

1)流表存儲機制改進——結(jié)合網(wǎng)絡(luò)通信和業(yè)務(wù)流的差異性，將流表匹配或業(yè)務(wù)處理作為約束和優(yōu)化目標，改進流表存儲體系，使流表表項不再單一存儲在交換機硬件TCAM中，如CacheFlow[9]；

2)基于軟件的流表擴容——通過算法或策略來聚合壓縮流表表項，對流表實現(xiàn)軟件上的間接擴容，如FFTA[10]；

3)流表超時時間管理——結(jié)合數(shù)據(jù)流量特征對流表超時時間進行管理，如時間序列預測[11]，通過優(yōu)化流表固定的超時時間，依據(jù)流表超時機制來刪除部分冗余或即將超時的表項.

針對流表空間的有限存儲和有效利用，3類流表空間管理優(yōu)化方案主要采用TCAM存儲所需流表數(shù)量和流表線性查詢效率兩個評價指標.通過監(jiān)測時間周期內(nèi)活動表項(即流表中能和任意一條或多條數(shù)據(jù)流成功匹配的表項)數(shù)目，對TCAM存儲空間利用率進行對比分析.線性查詢效率是通過計算和統(tǒng)計時間周期內(nèi)數(shù)據(jù)包的平均匹配耗時時間，對比驗證優(yōu)化方案的可行性和有效性.流表存儲機制改進方案利用流表空間利用率作為反饋來評價此類存儲機制改進的有效性，目標是減少TCAM中存儲所需流表的數(shù)量.基于軟件的流表擴容通過壓縮或聚合流表表項來保證OpenFlow交換機存儲空間的有效性，同時對流表查詢效率進行驗證.流表超時時間管理方案結(jié)合流量的差異性特征，通過優(yōu)化流表超時時間及時或提前刪除無效表項，使得流表存儲空間利用率和匹配率兩方面都有一定的提升[9-11].

2 流表存儲機制改進

流表存儲機制改進方案變更原有流表存儲方式，對流表存儲空間實現(xiàn)擴容.采用軟硬件結(jié)合的方式將當前常用表項存儲在交換機硬件TCAM中，而剩余表項存儲在交換機或其他遠程設(shè)備上.依據(jù)流表表項存放位置和管理方式的不同，可分為層級存儲、分布存儲和其他存儲3種存儲機制改進.

2.1 層級存儲

層級存儲將流表進行分類并存儲在兩類不同的存儲介質(zhì)中，將常用表項或粗粒度表項存放在TCAM中，不常用流表則存放在交換機緩存中.KATTA N等[9]提出CacheFlow機制，該機制依據(jù)流表間的依賴關(guān)系設(shè)計相應緩存算法，將大部分不常用的流表存儲在CacheMaster結(jié)構(gòu)中，OpenFlow交換機保存能匹配大部分數(shù)據(jù)包的少數(shù)流表.MARSCIO A等[12]提出內(nèi)存交換機制，將TCAM和RAM(Random Access Memory)作為交換機內(nèi)存存儲系統(tǒng)，利用此兩層存儲介質(zhì)分別存儲最近最常匹配的流表和最少匹配的流表.

2.2 分布存儲

分布存儲將流表分散地存儲在各網(wǎng)絡(luò)設(shè)備中，如交換機或遠程設(shè)備.依據(jù)數(shù)據(jù)流路由請求和資源利用情況，控制平面為交換機選擇安裝合適且適量的表項.MA H等設(shè)計的分布式存儲DSFoF[13]將流表存放于多個較小容量的TCAM交換機之中.KANIZO Y等引入Palette[5]，基于圖論原理及算法，將表項分割為多個均等的子表項并下發(fā)到傳輸路徑的交換機中，同時保證了路由傳輸和最小化資源的利用.此類方法在保證SDN處理性能的前提下，采用流表分布存儲，減少網(wǎng)絡(luò)中單交換機所存儲的最大流表數(shù)量.

2.3 其他存儲方案

劉中金等[14]引入多級流表模型，計算單一流表的多元匹配域映射增益，并將匹配域提取出來在新一級流表中進行壓縮存儲，解決單一流表字段過長的問題.唐亞哲等[15]基于布隆過濾器(Bloom Filter)設(shè)計新型流表存儲結(jié)構(gòu)，使用一級TCAM流表連接多級Bloom Filter流表.傳統(tǒng)的流表替換算法LRU(Least Recently Used)、FIFO、RANDOM等，分別采用不同的刪除策略對流表表項進行刪除[16]，其中LRU最常用，但其數(shù)據(jù)存儲和查詢維護復雜度較高.

YU M等通過DIFANE機制實現(xiàn)域內(nèi)交換機集中存儲方式[17].SDN控制器下發(fā)分區(qū)規(guī)則對網(wǎng)絡(luò)區(qū)域進行劃分，每個分區(qū)包含一個權(quán)威交換機和若干普通交換機，權(quán)威交換機具備部分控制功能.SDN控制器預先下發(fā)權(quán)威規(guī)則給權(quán)威交換機，當域內(nèi)普通交換機接收到新的數(shù)據(jù)流時，會將其轉(zhuǎn)向分區(qū)內(nèi)的權(quán)威交換機，權(quán)威交換機依據(jù)權(quán)威規(guī)則直接對數(shù)據(jù)包執(zhí)行轉(zhuǎn)發(fā)策略而不發(fā)往原交換機.權(quán)威交換機集中存儲流表，減少了非權(quán)威交換機存儲的流表數(shù)量，并通過去除控制器處理時延提高數(shù)據(jù)包的處理效率.

流表存儲體系改進方案變更了原有流表線性存儲方式，提高了SDN網(wǎng)絡(luò)流管理的適應性和穩(wěn)定性.層級存儲基于流表分類，通過有效的存儲設(shè)計和管理，流表的查詢效率有所提高.分布存儲使得流表存儲分布較為均衡，可減少單交換機中的流表數(shù)量，但在滿足真實業(yè)務(wù)需求時，路由計算和表項刷新對于控制器負載提出較高要求.其他方案包括DIFANE和多級流表等，能一定程度上提高數(shù)據(jù)的處理效率，但此類方案對流表結(jié)構(gòu)提升了管理難度，易導致流表性能降低.

3 基于軟件的流表擴容

基于軟件的流表擴容是通過聚合或壓縮方式對流表結(jié)構(gòu)、大小和數(shù)量進行縮減，實現(xiàn)流表的間接擴容，提高流表空間有效利用率.根據(jù)作用對象不同，主要分為表項聚合和表項壓縮兩大類.

表1 基于軟件的流表擴容方案

如表1所示，表項聚合針對流表多元匹配字段，采用前綴聚合或非前綴聚合方法對表項進行聚合，改進表項復雜的數(shù)據(jù)結(jié)構(gòu)，優(yōu)化流表存儲空間；表項壓縮通過拆分流表，將表項分割為多個子表，減少每次匹配的匹配域的長度，另外一些研究[24,25]通過引入標識減少表項的比特大小或合并壓縮表項來達到優(yōu)化流表空間的目的.

3.1 表項聚合

表項聚合方式不依賴于網(wǎng)絡(luò)數(shù)據(jù)流的特征規(guī)律，將具有相關(guān)性的多流表表項合并為一個表項，依據(jù)聚合位置的不同，主要分為前綴聚合和非前綴聚合.前綴聚合[18]主要用于IP路由，合并具有相同轉(zhuǎn)發(fā)目的地的表項，而OpenFlow具有多元匹配域，且是變長結(jié)構(gòu)，需要依據(jù)實際需求進行非前綴聚合，采用如啟發(fā)式等聚合算法對相關(guān)字段進行聚合，分類如表2所示.

表2 表項聚合方案分類對比

MEINERS C R等提出適用于數(shù)據(jù)包分類的TCAM表項壓縮算法TCAM razor[18]和Bit weaving[19].TCAM razor采用前綴聚合，通過判定圖、貪心算法動態(tài)編碼和前綴聚合冗余消除來壓縮數(shù)據(jù)包分類器中的TCAM表項，但只能采用構(gòu)造前綴聚合的方式來聚合表項.而Bit weaving可實現(xiàn)對已聚合表項的再一次聚合，解決了TCAM razor只能進行前綴聚合的不足.

FFTA[10]、FTRS[20]、IDFA[21]等均是基于SDN而設(shè)計的表項聚合方案.FFTA為一種高效的表項聚合算法，基于Bit Weaving 技術(shù)，通過構(gòu)建二叉樹將非前綴規(guī)則劃分為多個可置換的前綴分區(qū)，采用基于優(yōu)化路由表構(gòu)造器(Optimal Routing Table Constructor，ORTC)算法進行聚合.FTRS和IDFA通過基于目的IP地址的聚合，其中，IDFA采用分解和重排技術(shù)對局域網(wǎng)IP和隨機IP進行聚合，得到壓縮比分別為26.3%和43%，而實驗驗證FTRS能有效地聚合流表表項，保證了SDN控制器的處理性能.

3.2 表項壓縮

表項壓縮采用壓縮算法對流表結(jié)構(gòu)、大小和數(shù)量進行壓縮處理.常用的表項壓縮降低了表項規(guī)模，依據(jù)作用對象不同可分為表項分割、標識改進和合并3類壓縮方式.

GE J等[22]提出啟發(fā)式流表存儲空間優(yōu)化算法H-SOFT，通過表項間的共生關(guān)系和互斥關(guān)系將大表項劃分為多個規(guī)模較小的子表項，再將子表項依據(jù)表項中的多元匹配域情況分割為多個字段，以達到節(jié)省流表存儲空間的目的.孫鵬浩等[23]利用信息熵對各表項匹配域間的冗余關(guān)系和相關(guān)度進行分析建模，得到匹配域提取目標進行裁剪，減少流表長度.

其他相關(guān)工作主要通過改進表項標識、資源復用等來解決流表空間存儲有限的問題[24-26].BANERJEE S等[24]采用兩層標簽Tag來替換原始流表表項，關(guān)聯(lián)到數(shù)據(jù)流的標簽和路由標識標簽，通過標簽標識的方法生成流表表項，從而減少流表表項所占比特數(shù).KANNAN K等[25]依據(jù)原始流表在入口交換機上的數(shù)據(jù)包頭部加入流ID，中間傳輸?shù)慕粨Q機也通過存儲流ID來匹配和轉(zhuǎn)發(fā)數(shù)據(jù)包，減少了標識流所需的比特位數(shù)，使TCAM能容納較多的流表表項.基于資源復用的方案[26]也是通過壓縮合并表項來優(yōu)化存儲問題，設(shè)計基于Mask值和Range值的流表關(guān)聯(lián)度算法，計算待增表項與已存表項的關(guān)聯(lián)度，將待增表項與最大關(guān)聯(lián)度的已存表項進行合并.

基于軟件的流表擴容主要通過表項聚合和表項壓縮等手段來解決流表容量不足的問題.表項聚合分析流表多元匹配域中存在的冗余信息，對不同的匹配字段進行聚合，利用較少的表項實現(xiàn)原有的表項規(guī)則，但表項聚合可能破壞流表語義，丟失部分粒度控制信息，并不具有較強的通用性.表項壓縮主要針對流表大小、規(guī)模進行優(yōu)化，使TCAM能容納更多的流表表項，此類方案針對流表表項壓縮需求，利用流表的邏輯結(jié)構(gòu)特征，結(jié)合流表結(jié)構(gòu)的冗余性和可壓縮性實現(xiàn)流表空間的優(yōu)化，但表項壓縮算法的設(shè)計與實現(xiàn)較為復雜，不適用于小規(guī)模的表項壓縮.

4 流表超時時間管理

OpenFlow流表超時時間管理是通過超時時間來控制流表表項的生存時間.OpenFlow協(xié)議提供兩種超時時間：硬超時時間(hard_timeout)和停滯等待超時時間(idle_timeout)，表項在交換機中的生存時間超過了預設(shè)定硬超時時間就會被刪除，在停滯等待時間內(nèi)流表表項未匹配到任何數(shù)據(jù)包也將會被刪除(說明：后文中未指明具體超時時間的情況下，“超時時間”指停滯等待超時時間).基于流表超時時間管理對表項進行刪除的方案主要分為時間序列預測、資源特征感知和其他針對流表超時時間的方案.時間序列預測主要是通過流表的匹配情況來調(diào)整流表超時時間，實現(xiàn)流表更新，提高流表空間的有效利用率和流表表項的匹配率；資源特征感知結(jié)合數(shù)據(jù)流特征或流表、控制器資源來對超時時間進行調(diào)整；其他方案主要通過提前刪除無效流表表項、調(diào)整或轉(zhuǎn)換超時時間等來優(yōu)化流表空間存儲和利用的問題.

4.1 時間序列預測

基于預測機制是結(jié)合歷史流量或表項信息，通過時間序列預測的方式動態(tài)調(diào)整當前表項的超時時間，刪除近期不會被匹配的流表表項，從而達到存儲表項和下發(fā)表項數(shù)量的均衡，保證流表空間的有效性，過程如圖1所示.

圖1 時間序列預測處理圖

KIM E D等[16]利用自回歸模型來預測下一采樣時刻流表中新到達流的數(shù)量，并估計下一采樣周期內(nèi)存活的流表表項數(shù)量.然后，在采樣時刻動態(tài)刷新當前所有表項的超時時間來容納新的流.LIU Y等[27]基于KIM E D提出的方案，考慮控制器刷新交換機中表項成本，通過調(diào)整采樣周期內(nèi)新到達流的超時時間，而非在采樣時刻刷新所有流表表項的超時時間，從而優(yōu)化流表存儲空間，防止下一周期內(nèi)流表溢出.

但是，自回歸算法對數(shù)據(jù)依賴性強，需收集大量歷史數(shù)據(jù)才能得出預測結(jié)果.史少平等[28]采用二次移動平均(Second Moving Average，SMA)算法對歷史流表表項數(shù)量進行了分析，預測下一采樣周期內(nèi)新增的流表表項的數(shù)量，并對流表超時時間做出調(diào)整.在數(shù)據(jù)波動較大時，SMA算法比自回歸算法預測準確度更高.

4.2 資源特征感知

除了時間序列預測，還可通過結(jié)合資源特征，如數(shù)據(jù)流特征或網(wǎng)絡(luò)資源等使用情況，對流表超時時間作動態(tài)調(diào)整，表3給出相關(guān)文獻的研究工作.

表3 資源特征感知方案對比

梁昊馳[29]針對即時消息流信息，建立ON/OFF模型，以控制器處理資源有限性為約束，建立優(yōu)化問題來求解滿足該條件的合理超時時間，但該方案在處理過程中沒有考慮不同數(shù)據(jù)流類型的差異性.TimeoutX[30]和基于數(shù)據(jù)流特征的智能更新算法[31]從全局網(wǎng)絡(luò)資源使用情況出發(fā)，結(jié)合數(shù)據(jù)流差異性特征，為不同的表項設(shè)定不同的超時時間.

ZHU H等[32]在控制中添加緩存模塊來記錄上一次流表表項到期時間，新安裝流表時間與其比較作為差值，來確定流表超時時間；結(jié)合流表空間資源利用狀況作為負載反饋，來調(diào)整最大超時時間.VISHNOI A等[33]提出SmartTime系統(tǒng)，利用啟發(fā)式算法來計算最合適的超時時間.ZHANG L L等[34]將流表處理建模為排隊，借助排隊論定量分析超時時間對流截斷次數(shù)和阻塞概率的影響，利用AHTM算法設(shè)定合理的硬超時時間，基于硬超時時間的調(diào)整機制在網(wǎng)絡(luò)應用中靈活性較差，不能很好地滿足傳輸要求.

4.3 其他管理方案

還有一些研究則是提前刪除無效的流表表項，而非在超時時間到達之后才進行刪除.HE C H等[35]在解析完TCP數(shù)據(jù)頭部信息后，利用P4交換機中的Learn Table來探測和解析TCP流中的最后發(fā)送的數(shù)據(jù)包中的FIN和RST位來判定TCP連接是否即將關(guān)閉，以提前移除相應的流表表項，而不必等到停滯等待超時時間才進行刪除.KANNAN K等[36]基于超時時間提前移除最近一段時間內(nèi)不會被匹配的流表表項.此外，還可以基于流表字段超時時間的特點，對超時時間進行轉(zhuǎn)化或調(diào)整.王敢甫等[37]依據(jù)流表超時時間的特點，提出流表表項的動靜態(tài)轉(zhuǎn)化機制，將靜態(tài)流表表項轉(zhuǎn)化為動態(tài)流表表項.

基于流表表項超時時間管理的機制，通過調(diào)整表項固有的超時時間來提高流表匹配率，從而有效利用流表空間.時序預測機制結(jié)合歷史流和表項信息來設(shè)定超時時間，但未以控制層和轉(zhuǎn)發(fā)層處理性能作為約束前提，且在實際操作中選取和實現(xiàn)能反映大部分數(shù)據(jù)信息、設(shè)計簡單、運行速率高的預測算法較為困難和復雜.資源特征感知方案在結(jié)合數(shù)據(jù)流特征、流表資源和控制器資源約束時未能對數(shù)據(jù)流作出更為細致的分類，并且調(diào)整超時時間的算法設(shè)計復雜，不能改善流表查詢效率和匹配率.其余方案提前刪除無效表項，或從網(wǎng)絡(luò)傳輸、流表匹配特性對表項超時時間作調(diào)整，在實際網(wǎng)絡(luò)應用中，對于不同特征的數(shù)據(jù)流和更細粒度的控制需求，如何智能而有效地優(yōu)化超時時間，還有待深入研究和驗證.

5 總結(jié)與展望

基于OpenFlow協(xié)議的SDN架構(gòu)給網(wǎng)絡(luò)部署、管理帶來了顯著的靈活性和創(chuàng)造性，但不斷擴展的網(wǎng)絡(luò)業(yè)務(wù)需求對OpenFlow交換機的流表空間提出了更高的要求.

流表空間的有限性和有效性管理問題可通過基于緩存機制、表項壓縮和超時時間等3類方案進行優(yōu)化，本文對這些方案的特點分別進行了歸納總結(jié).3類方案從TCAM存儲流表容量和流表表項線性查詢效率等方面進行了相關(guān)驗證，在保證數(shù)據(jù)流正常傳輸?shù)那疤嵯?，在不同的程度上可有效地解決流表空間管理問題.此外，OpenFlow流表作為SDN南向通信的核心部件，在部署應用中的空間優(yōu)化還需要結(jié)合以下幾方面作進一步研究：

(1)設(shè)計時間復雜度低、執(zhí)行效率高、盡可能少地影響其他網(wǎng)絡(luò)性能的緩存算法、壓縮聚合算法和預測算法.在面向大規(guī)模網(wǎng)絡(luò)時，真實網(wǎng)絡(luò)中的性能需求、海量數(shù)據(jù)、可擴展性和路由是制約SDN發(fā)展的重要因素，優(yōu)化算法或策略需要真實有效地反映實際的業(yè)務(wù)需求；

(2)兼顧流表空間利用率、流表查詢效率和匹配率.在面對細粒度業(yè)務(wù)流控制需求時，對流表的空間優(yōu)化盡可能同時保證查詢效率與匹配率；

(3)保證表項規(guī)則的一致性和SDN安全需求設(shè)計.流表空間保證表項規(guī)則的存儲，故存儲安全和表項一致性關(guān)系到整個網(wǎng)絡(luò)的可靠性，例如：緩存機制中的存儲安全性設(shè)計對管理流和抵抗某些網(wǎng)絡(luò)攻擊具有一定的意義.

基于OpenFlow的SDN交換機中，流表空間的有限性和有效利用是軟件定義網(wǎng)絡(luò)技術(shù)的核心問題之一，鑒于當前流表的復雜性和日益劇增的網(wǎng)絡(luò)業(yè)務(wù)類型及流量，如何管理和優(yōu)化流表空間依舊亟待探索和解決.