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

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

軟件定義網(wǎng)絡(luò)(Software-Defined Network，SDN)[1]是一種新興的網(wǎng)絡(luò)技術(shù)，它將傳統(tǒng)網(wǎng)絡(luò)的控制面和數(shù)據(jù)面相分離，并通過(guò)開(kāi)放的軟件定義應(yīng)用程序接口(Application Program Interface，API)實(shí)現(xiàn)網(wǎng)絡(luò)功能的靈活重構(gòu)，構(gòu)建動(dòng)態(tài)、開(kā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ī)模爆炸性增長(zhǎng)，流表的存儲(chǔ)與查找已逐漸成為OpenFlow交換機(jī)的性能瓶頸．并且自O(shè)penFlow 1.1版本起提出了多級(jí)流表的概念，多級(jí)流表的劃分與構(gòu)建仍然是一個(gè)開(kāi)放性問(wèn)題．此外，隨著 40/ 100 Gbit/s 以太網(wǎng)標(biāo)準(zhǔn)的出現(xiàn)，不斷增長(zhǎng)的轉(zhuǎn)發(fā)速率需求對(duì)交換機(jī)的轉(zhuǎn)發(fā)性能和硬件設(shè)計(jì)提出了新的挑戰(zhàn)．因此，針對(duì)高速環(huán)境下OpenFlow的多級(jí)流表研究在近年來(lái)得到了廣泛關(guān)注[3-4]．

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

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

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

1.1 OpenFlow流表

圖1 多級(jí)流表工作流程

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

1.2 符號(hào)描述

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

(1)

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

(2)

(3)

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

(4)

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

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

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

(5)

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

2.1 基本思想

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

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

2.2 算法流程

2.2.1 流類別向量拆分

定義流類別向量α=(b1，b2，…，bd)，對(duì)于某一條流表項(xiàng)e= {f1，f2，…，fd}，若其匹配域fi不為通配符“*”，則將bi置1；反之，則將bi置0．例如，單流表T的所有匹配域?yàn)閧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表利用五元組對(duì)輸入分組進(jìn)行過(guò)濾，則ACL規(guī)則可以表示為α3= (0，1，1，1，1，1)．

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

(6)

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

2.2.2 匹配域間正交分解

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

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

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

3 性能仿真

3.1 軟件仿真

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

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

圖2 不同流表項(xiàng)數(shù)的流表空間壓縮率圖3 不同流表分級(jí)算法性能對(duì)比

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

3.2 FPGA實(shí)現(xiàn)

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

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

4 結(jié) 束 語(yǔ)

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