軟件定義網(wǎng)絡(luò)中一種兩步式多級流表構(gòu)建算法

鄭 凌，邱智亮，孫士勇，潘偉濤，王偉娜，張之義

(1. 西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實驗室，陜西 西安 710071；2. 中國電子科技集團(tuán)公司第五十四研究所 通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實驗室，河北 石家莊 050081)

軟件定義網(wǎng)絡(luò)(Software-Defined Network，SDN)[1]是一種新興的網(wǎng)絡(luò)技術(shù)，它將傳統(tǒng)網(wǎng)絡(luò)的控制面和數(shù)據(jù)面相分離，并通過開放的軟件定義應(yīng)用程序接口(Application Program Interface，API)實現(xiàn)網(wǎng)絡(luò)功能的靈活重構(gòu)，構(gòu)建動態(tài)、開放、可控的網(wǎng)絡(luò)環(huán)境，極大地改善了網(wǎng)絡(luò)的擴(kuò)展能力和靈活性．OpenFlow[2]是SDN最重要的南向接口標(biāo)準(zhǔn)，其主要思想是在數(shù)據(jù)平面上采用基于流表(Flow Table)的轉(zhuǎn)發(fā)機(jī)制，并提供了數(shù)據(jù)面和控制面的標(biāo)準(zhǔn)接口．如今，隨著網(wǎng)絡(luò)新型業(yè)務(wù)的快速發(fā)展，流表匹配域不斷增加、流表規(guī)模爆炸性增長，流表的存儲與查找已逐漸成為OpenFlow交換機(jī)的性能瓶頸．并且自O(shè)penFlow 1.1版本起提出了多級流表的概念，多級流表的劃分與構(gòu)建仍然是一個開放性問題．此外，隨著 40/ 100 Gbit/s 以太網(wǎng)標(biāo)準(zhǔn)的出現(xiàn)，不斷增長的轉(zhuǎn)發(fā)速率需求對交換機(jī)的轉(zhuǎn)發(fā)性能和硬件設(shè)計提出了新的挑戰(zhàn)．因此，針對高速環(huán)境下OpenFlow的多級流表研究在近年來得到了廣泛關(guān)注[3-4]．

文獻(xiàn)[5]提出了一種哈希表和三態(tài)內(nèi)容尋址存儲器(Ternary Content Addressable Memory，TCAM)相結(jié)合的多級流表實現(xiàn)方式，但是該方法依賴于流表中匹配域的類型，只能實現(xiàn)TCAM與哈希表互相交替的流水結(jié)構(gòu)．文獻(xiàn)[6]針對數(shù)據(jù)平面轉(zhuǎn)發(fā)提出了可重構(gòu)匹配流表(Reconfigurable Match Table，RMT)模型，該模型實現(xiàn)了一個可重新配置的流表，支持任意的數(shù)據(jù)位寬和深度，具備了協(xié)議無關(guān)和可編程的靈活性．但是這種思想在硬件實現(xiàn)時需要消耗大量的靜態(tài)隨機(jī)存取存儲器(Static Random Access Memory，SRAM)和TCAM資源，不具備實際工程的可實現(xiàn)性．文獻(xiàn)[7]提出了一種SDN流表化簡機(jī)制(Flow Table Reducation Scheme，F(xiàn)TRS)，該算法針對IP表項進(jìn)行前綴聚合，能夠在不影響網(wǎng)絡(luò)功能的前提下，減少流表項的條數(shù)，從而壓縮流表的存儲空間．但是這種方法僅能應(yīng)用于IP查找，難以適應(yīng)OpenFlow的多字段匹配需求．考慮到OpenFlow匹配域的特征，文獻(xiàn)[8]提出了一種啟發(fā)式流表空間優(yōu)化算法(Heuristic Storage space Optimization algorithm for Flow Table，H-SOFT)，該算法分析了OpenFlow流表結(jié)構(gòu)定義字段之間的共存和沖突關(guān)系，通過分級消除流表中的互斥字段從而降低流表的存儲空間．文獻(xiàn)[9]提出了一種OpenFlow多級流表結(jié)構(gòu)及其映射算法，將單一流表映射到多級流表中進(jìn)行高效存儲和查找．但是該方法難以對流表中的匹配域進(jìn)行均勻的拆分，導(dǎo)致流表空間壓縮性能不夠理想，且硬件開銷較大．文獻(xiàn)[10]提出了一種平衡時空的自適應(yīng)多級流表構(gòu)建方法，該方法根據(jù)每個匹配域的重復(fù)率對流表進(jìn)行分級，并且在一片TCAM中為每一級流表分配一定的空間用于存儲流表項．但是該方法僅使用了一片TCAM進(jìn)行多級流表的存儲，因而不能進(jìn)行流水操作，帶來了較大的時延，無法實現(xiàn)硬件交換機(jī)端口的線速處理．

針對OpenFlow流表面臨的這些問題，文中提出了一種兩步式多級流表構(gòu)建方法，通過流表匹配域的流類別拆分和正交分解兩個步驟實現(xiàn)多級OpenFlow流表的構(gòu)建，能夠?qū)崿F(xiàn)流表存儲空間的有效壓縮，同時保證了多級流表查找的硬件可實現(xiàn)性和流水線處理速度，支持 100 Gbit/s 線速處理．

1 OpenFlow多級流表結(jié)構(gòu)

1.1 OpenFlow流表

圖1 多級流表工作流程

最初的OpenFlow 1.0版本將轉(zhuǎn)發(fā)規(guī)則存放在一張單級流表中，但當(dāng)網(wǎng)絡(luò)規(guī)則變的很復(fù)雜時，這種單流表結(jié)構(gòu)不僅會造成流表資源的浪費(fèi)，而且還限制了應(yīng)用層業(yè)務(wù)規(guī)則的制定．因此，在OpenFlow 1.1版本中提出了基于流水線工作方式的多級流表概念，多級流表的工作流程如圖1所示．分組進(jìn)入交換機(jī)后，將從流表0開始依次匹配，流表項將以優(yōu)先級從高到低的順序與數(shù)據(jù)包進(jìn)行匹配，當(dāng)數(shù)據(jù)包成功匹配到一條流表項后，根據(jù)流表項中的指令進(jìn)行相應(yīng)操作(例如跳轉(zhuǎn)至后續(xù)的某一流表繼續(xù)處理，增加或者修改該數(shù)據(jù)包對應(yīng)的動作集合，更新元數(shù)據(jù)等)．當(dāng)數(shù)據(jù)包已經(jīng)處于最后一個流表時，其對應(yīng)的動作集合(Action Set)中的所有動作指令將被執(zhí)行(例如轉(zhuǎn)發(fā)至某一端口、修改數(shù)據(jù)包某一字段、丟棄數(shù)據(jù)包等)．

1.2 符號描述

流表T，是包含多個流表項e的集合，每條流表項可以包含多個匹配域(Match Field)．用符號f表示流表中的匹配域，如OpenFlow協(xié)議定義的IP源地址(IPSRC)，IP目地地址(IPDST)，以太網(wǎng)源地址(ETHSRC)等字段都稱為匹配域．設(shè)流表T共有n條流表項，每條流表項由d個匹配域{f1，f2，…，fd}構(gòu)成，令si表示匹配域fi的位寬(例如，IPV4SRC的位寬為 32 bit，ETHDST的位寬為 48 bit)，則單級流表T的總存儲空間為

(1)

如果將流表T分解為K個子流表{H1，H2, …，HK}，則對于第k個子流表，其中 1≤k≤K，設(shè)其包含了Nk條表項，每條流表項包含了Mk個匹配域，令sk，j表示第k個子流表的第j個匹配域所占用的存儲空間，則K個子流表所占用的總存儲空間為

(2)

(3)

由式(3)可知，分級之后的流表存儲空間小于分級之前的，因此，通過流表分級的方式能夠減少流表存儲空間，提高流表資源的利用率．使用流表空間壓縮率作為指標(biāo)衡量流表分級算法的性能．定義流表空間壓縮率p為將單流表劃分為多級流表之后節(jié)省的流表空間的比率，則

(4)

設(shè)已知交換機(jī)可接受的查找處理時延為D，系統(tǒng)的時鐘頻率為fCLK，則最大流表級數(shù)K=DfCLK．

流表分級問題從而轉(zhuǎn)化為如下的最優(yōu)化問題: 已知交換機(jī)中，原始單級流表T，交換機(jī)可接受的最大流表級數(shù)K為DfCLK，求多級流表的集合H= {H1，H2…，HK}，使得

H=argminp(H1，H2，…，HK) ．

(5)

2 兩步式多級流表構(gòu)建算法

2.1 基本思想

雖然OpenFlow標(biāo)準(zhǔn)給出了13個必選的匹配域，但是在實際的應(yīng)用場景中，用戶通常并不需要同時用到全部的13個匹配域?qū)α鬟M(jìn)行匹配．在特定應(yīng)用中，只需要關(guān)注某些特定的字段．例如，在橋接路由器中，橋接分組只關(guān)注二層字段的匹配; 路由分組只關(guān)心IP地址的匹配; 而訪問控制列表(Access Control List， ACL)采用五元組對輸入分組進(jìn)行過濾．由此可見，可以根據(jù)不同的數(shù)據(jù)流處理邏輯的功能，將一張包含所有匹配項的流表，劃分成多個相互獨(dú)立，且具備不同數(shù)據(jù)流處理功能的邏輯流表．例如，將橋接轉(zhuǎn)發(fā)，路由轉(zhuǎn)發(fā)，以及ACL各維護(hù)一張表，這樣能夠優(yōu)化流表中通配符所占用的空間，節(jié)約流表所需的存儲空間．

此外，由于SDN對業(yè)務(wù)流的細(xì)粒度分類需求，通過匹配域的正交組合而產(chǎn)生的流表項會導(dǎo)致流表中存在很多重復(fù)的內(nèi)容，也會使得流表的規(guī)模顯著增加．例如，在服務(wù)質(zhì)量保證(Quality of Service，QoS)中，需要根據(jù)輸入分組的源IP地址以及目的IP地址得出分組要入隊的隊列號，從而實現(xiàn)對不同數(shù)據(jù)流的區(qū)分服務(wù)．假設(shè)源IP地址包含了M種匹配，目的IP地址包含了N種匹配，則在單級流表中就需要M×N條表項．這種正交組合會導(dǎo)致流表項數(shù)爆炸性增長．而如果把單流表的流表項通過匹配域的正交分解形成多個流表，可以壓縮各匹配域中的重復(fù)值，也能夠在很大程度上節(jié)省流表的物理存儲空間．例如，將源IP地址，目的IP地址分別存儲在2個流表中以流水線的方式進(jìn)行查找，查找得到的中間結(jié)果使用元數(shù)據(jù)(metadata)進(jìn)行傳遞，則只需要存儲M+N條表項，從而降低存儲流表所需的空間．綜上所述，可以通過流類別拆分和匹配域間正交分解兩個步驟來實現(xiàn)多級流表的構(gòu)建．

2.2 算法流程

2.2.1 流類別向量拆分

定義流類別向量α=(b1，b2，…，bd)，對于某一條流表項e= {f1，f2，…，fd}，若其匹配域fi不為通配符“*”，則將bi置1；反之，則將bi置0．例如，單流表T的所有匹配域為{ETHDST，IPV4SRC，IPV4DST，TCP/UDPSRC，TCP/UDPDST，IPPROTO}，橋接轉(zhuǎn)發(fā)只關(guān)注目的MAC地址，可將橋接轉(zhuǎn)發(fā)規(guī)則表示為α1= (1，0，0，0，0，0)．路由轉(zhuǎn)發(fā)需要關(guān)注源IP和目的IP地址，因此，路由轉(zhuǎn)發(fā)規(guī)則可以表示為α2= (0，1，1，0，0，0)．而ACL表利用五元組對輸入分組進(jìn)行過濾，則ACL規(guī)則可以表示為α3= (0，1，1，1，1，1)．

根據(jù)流類別向量的不同，可將單級流表T拆分為多級流表．為了衡量拆分某個流類別向量后能夠壓縮的流表空間，定義分級收益C(αi)為

(6)

其中，ni為流類別向量αi所對應(yīng)的規(guī)則數(shù)．每次迭代時，優(yōu)先選取分級收益最高的流類別向量作為新的一級子流表．在子流表存儲時，需要根據(jù)該子流表對應(yīng)的查找算法，選取合適硬件存儲器進(jìn)行存儲，具體描述如下．

2.2.2 匹配域間正交分解

通過分解流表項中匹配域間的正交組合關(guān)系，壓縮匹配域中的重復(fù)表項，進(jìn)一步對流表進(jìn)行分級．主要思想是統(tǒng)計出流表中每個匹配域fi的重復(fù)率，其定義為整個流表中匹配域fi中包含內(nèi)容重復(fù)的次數(shù)，記為R(fi)．每次迭代時，以貪心的方式選取重復(fù)率最高的匹配域提取出來作為一級子流表進(jìn)行壓縮存儲，從而實現(xiàn)對流表規(guī)模的進(jìn)一步壓縮．直到流表級數(shù)達(dá)到最大流表級數(shù)約束K，或者全部匹配域均已提取完畢時，算法停止，具體描述如下．

(6) 繼續(xù)遍歷集合S，直到集合S中所有元素遍歷完畢或者多級流表H的級數(shù)等于K．

通過正交分解進(jìn)行流表分級時，流表項中各個字段之間的組合關(guān)系也隨之消失．為了保證子流表分級前后數(shù)據(jù)包匹配結(jié)果的一致性，需要通過metadata傳遞查找的中間結(jié)果，最后根據(jù)各級流表查找得出的元數(shù)據(jù)集合查找動作表，得出最終的action．而metadata只需在action表中存儲前級表項查找得到的序號即可，因此，metadata的存儲開銷非常?。?/p>

3 性能仿真

3.1 軟件仿真

由于OpenFlow還沒有廣泛部署于實際網(wǎng)絡(luò)中，所以外界難以獲取實際OpenFlow網(wǎng)絡(luò)中的流表信息．文中的實驗數(shù)據(jù)來源于ISN國家重點(diǎn)實驗室研發(fā)的高性能同軸電纜寬帶接入(HIgh-performance Network Over Coax，HINOC)[11]網(wǎng)絡(luò)中的流分類規(guī)則集，并結(jié)合OpenFlow 1.3版本的必選匹配域加以擴(kuò)充，生成不同規(guī)模的流表測試集，包括從INPORT到UDPDST的13個匹配域，能夠在一定程度上反映實際OpenFlow網(wǎng)絡(luò)中的流表情況．文中實驗數(shù)據(jù)均是在該實驗條件下得出的．

首先分析文中提出算法的流表存儲空間壓縮性能，其中流表壓縮率指標(biāo)的定義由式(4)給出．不同流表級數(shù)N以及不同的流表規(guī)模下的仿真結(jié)果如圖2所示．可以看出，相對于單級流表結(jié)構(gòu)，文中方法分級之后能夠節(jié)省60%以上的流表空間．在相同的表項數(shù)量下，流表劃分的級數(shù)越多，流表的空間壓縮率越高．這是因為隨著流表級數(shù)增加，流表中不關(guān)注的字段表項以及字段內(nèi)重復(fù)的表項被壓縮的越多，從而節(jié)省更多的存儲空間．但是，為了實現(xiàn)流水線方式的查找，多級流表需要存儲在相互獨(dú)立的硬件存儲器中，因此，更多的流表級數(shù)會消耗更多的硬件資源，同時更長的流水線也會增加控制邏輯的復(fù)雜度．因此，在實際應(yīng)用中，要視實際的硬件資源情況來確定流表的級數(shù)．此外，從圖中可以看出，在流表級數(shù)相同的情況下，隨著流表規(guī)模的增大，流表壓縮率的變化較為平緩．這表明在測試集中，文中提出的算法的流表空間壓縮性能對于流表規(guī)模變化不敏感，具有較高的穩(wěn)定性．

圖2 不同流表項數(shù)的流表空間壓縮率圖3 不同流表分級算法性能對比

接下來分析不同流表分級算法之間的流表空間壓縮率性能對比，對比方法包括FTMS[9]算法以及H-SOFT[8]算法，流表規(guī)模設(shè)置為16K以及128K條表項，仿真結(jié)果如圖3所示．從圖中可以看出，各方法的流表壓縮率隨著流表級數(shù)的增加而增加．當(dāng)流表級數(shù)較小時 (K=2，3)，F(xiàn)TMS算法的流表壓縮性能較差．這是由于這種方法每次分級時只提取出一個匹配域作為一級流表進(jìn)行壓縮存儲，這種方式無法實現(xiàn)多個匹配域的均勻拆分，導(dǎo)致在流表級數(shù)較低時性能會受到嚴(yán)重影響．H-SOFT算法是一種啟發(fā)式的流表分級算法，該算法首先對流表的匹配域進(jìn)行分析，刪除表項中的互斥字段從而節(jié)省空間．從圖3中可以看出，在不同的流表級數(shù)和流表規(guī)模下，文中算法均具有較好的流表壓縮性能．當(dāng)流表級數(shù)N=8，流表規(guī)模為128K條表項時，相對于FTMS算法，文中算法性能提高了51.5%; 相對于H-SOFT算法，文中算法性能提高了21.4%．當(dāng)流表級數(shù)繼續(xù)增大時 (N=10)，幾乎所有字段都被拆分出來作為一級單獨(dú)的流表，此時各種算法性能較為接近．

3.2 FPGA實現(xiàn)

在現(xiàn)場可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA)平臺上驗證了該多級流表構(gòu)建與查找算法，實驗環(huán)境為Xilinx Virtex 7 xc7vx690t，ISE 14.6以及Modelsim 10.4．FPGA多級流表模塊設(shè)計如圖4所示，主要包括幀解析模塊，流表管理模塊，分組處理模塊以及多級流表模塊．當(dāng)一個分組到達(dá)時，分組頭部進(jìn)入幀解析模塊中提取待匹配的字段信息，而分組數(shù)據(jù)傳送至分組處理模塊中進(jìn)行緩存．分組頭部字段提取出之后進(jìn)入多級流表模塊，以流水線的方式依次匹配各個子流表．多級流表模塊包括TCAM、SRAM和FPGA片內(nèi)隨機(jī)存取存儲器(Random Access Memory，RAM)．FPGA片內(nèi)RAM根據(jù)查找算法的不同，分為精確匹配模塊、前綴匹配模塊和范圍匹配模塊．精確匹配模塊使用哈希表查找，前綴匹配模塊使用比特向量(Bit Vector，BV)[12]算法進(jìn)行查找，范圍匹配算法使用范圍比特向量編碼(Range Bit Vector Encoding，RBVE)[13]算法進(jìn)行查找．多級流表匹配結(jié)束后得到的匹配結(jié)果通過指令碼傳遞到分組處理模塊中，分組處理模塊從輸出緩存中提取出分組數(shù)據(jù)并執(zhí)行相應(yīng)的操作．流表管理模塊負(fù)責(zé)表項的配置，更新和管理．仿真的輸入數(shù)據(jù)為64字節(jié)的以太網(wǎng)最短幀突發(fā)，仿真結(jié)果顯示在一定的流水線時延之后，查找結(jié)果能夠連續(xù)輸出，與輸入數(shù)據(jù)的速率相同，說明文中方法能夠?qū)崿F(xiàn)流表的線速查找．ISE綜合工具顯示該設(shè)計的最高時鐘頻率能夠達(dá)到197MHz．在具體硬件實現(xiàn)中，只需系統(tǒng)時鐘在150MHz以上，即可滿足150MPPS(Million Packets Per Second)的分組處理能力，實現(xiàn) 100 Gbit/s 的線速處理．

圖4 多級流表模塊的FPGA實現(xiàn)

4 結(jié) 束 語

針對SDN中多級流表的分級和查找問題，提出了一種兩步式多級流表構(gòu)建方法．通過對流表進(jìn)行流類別拆分和字段間正交分解兩個步驟將單級流表構(gòu)建為多級流表，在保證硬件可實現(xiàn)性的前提下，充分利用了流水操作提高了數(shù)據(jù)吞吐量．軟件仿真與FPGA驗證的結(jié)果表明，該方法能夠?qū)崿F(xiàn)流表存儲空間的有效壓縮，并且能夠滿足 100 Gbit/s 的線速查找要求．