王孝龍，劉勤讓，林森杰，黃雅靜

(國家數(shù)字交換系統(tǒng)工程技術研究中心，鄭州 450002)(*通信作者電子郵箱15617730323@163.com)

0 引言

包分類是實現(xiàn)當前網(wǎng)絡路由轉(zhuǎn)發(fā)、訪問控制和服務質(zhì)量等功能的核心技術。近年來，以OpenFlow[1]為代表的通過多匹配域來表達分類特征的協(xié)議已經(jīng)被廣泛應用于各種場景。但是，由于網(wǎng)絡應用多樣化、網(wǎng)絡流量爆炸性增長及對網(wǎng)絡管控系統(tǒng)靈活高效的要求，導致OpenFlow交換機中流表的寬度和規(guī)模面臨著巨大挑戰(zhàn)。因此，如何對網(wǎng)絡中不斷增加的流表進行優(yōu)化壓縮，減少所用的存儲資源一直是學術界研究的熱點。目前，相關的包分類技術主要有基于隨機存取存儲器(Random Access Memory, RAM)的軟件實現(xiàn)方案和基于三態(tài)內(nèi)容尋址寄存器(Ternary Content Addressable Memory, TCAM)的硬件實現(xiàn)方案。

RAM實現(xiàn)方案主要有決策樹優(yōu)化、多維空間切割和基于Hash算法的改進等。決策樹優(yōu)化方案易于實現(xiàn)，主要進行存儲空間和吞吐率之間的權衡[2]。文獻[3]提出自適應二進制切割(Adaptive Binary Cuttings, ABC)方法，可以在決策樹優(yōu)化的每個過程中自適應調(diào)整不同的剪切尺寸，但隨著匹配域增加，在高吞吐率情況下仍難以解決空間過度消耗問題。文獻[4]中的EffiCuts算法針對規(guī)則分割不均問題，引入等密度切割并有選擇地進行剪枝合并和節(jié)點協(xié)同查找，有效減小了節(jié)點個數(shù)和內(nèi)存訪問次數(shù)，不過算法復雜度較高。文獻[5]利用Bloom-filter的特殊Hash結(jié)構(gòu)，在極小誤判概率下實現(xiàn)快速查表，但難以滿足最壞情況下的線速要求。

TCAM的實現(xiàn)方案主要有編碼方式的改進、規(guī)則集優(yōu)化合并和硬件架構(gòu)修改。對于端口號的范圍擴張問題，文獻[6]利用TCAM條目中一些額外位進行編碼，并結(jié)合編碼過程與回退方案的相關性來減少冗余信息，不過這種方法需要對規(guī)則集進行預處理并提取相應特征，實現(xiàn)較為復雜。對于規(guī)則集的合并優(yōu)化，文獻[7]建立非前綴匹配機制，將匹配結(jié)果相同但某些位不同的規(guī)則用三態(tài)位代替，從而進行位交換和位合并，使相同決策的流表條目合并在一起以減少TCAM占用。文獻[8]通過對規(guī)則集具有特征的分析，利用部分匹配域完成規(guī)則匹配，可以實現(xiàn)較高程度的規(guī)則壓縮，但其算法復雜度較高，且更新復雜。在改進TCAM匹配流水線方面，文獻[9]對特定硬件架構(gòu)進行多端口范圍編碼優(yōu)化，利用多條TCAM流水線分別實現(xiàn)不同范圍字段匹配，在一定程度上緩解了范圍擴張問題。

上述研究對規(guī)則集存儲和多匹配域查找方面做出了很大貢獻，但仍難以應對不斷增長的流表規(guī)模擴張。針對該問題，本文提出了一種基于OpenFlow多匹配域的獨立規(guī)則子集位提取(Bit Extraction of Independent rule Subsets，BEIS)的壓縮方案。主要工作有：1)通過對OpenFlow協(xié)議中匹配域間相關關系分析，實現(xiàn)匹配域的合并，縮減表項位寬；2)建立了獨立規(guī)則子集分割算法，基于規(guī)則獨立性對整體規(guī)則集進行分割；3)提出對匹配域進行位提取的壓縮算法，在匹配功能完備的情況下，盡量減小所用位寬，從而進一步減少所用TCAM存儲資源。

1 模型描述

在網(wǎng)絡數(shù)據(jù)傳輸中，包分類是將包頭中的相應字段提取出來，作為關鍵字與分類規(guī)則集中規(guī)則進行匹配，匹配后執(zhí)行相應決策的過程。對于一個具有n條規(guī)則的包分類規(guī)則集U={R1,R2,…,Rn}，U中的第m(1≤m≤n)條規(guī)則為Rm={F1,F2,…,Fk;A}，包含k個匹配域，其中，F(xiàn)i(i=1,2,…,k)的取值可以是前綴、范圍或精確值，A表示匹配該規(guī)則要執(zhí)行的決策，比如轉(zhuǎn)發(fā)、丟棄等操作。本文主要著眼于匹配域Fi的規(guī)則集合，通過對集合中匹配域的相關分析，進行優(yōu)化壓縮。

1.1 匹配域字段預處理

以OpenFlow為代表的多匹配域包分類規(guī)則集中，由于每個規(guī)則所包含的匹配域較多，導致單個表項位寬過大，帶來較多查找資源占用。另一方面，幾乎所有協(xié)議在字段長度上都存在冗余，并且各匹配字段之間也并非完全獨立取值?；谄ヅ溆蜷g相關信息的分析，定義以下幾類邏輯關系[10-11]。

定義1 排斥關系PO。表示協(xié)議中兩個匹配域Fi和Fj(i≠j)，在任意的報文頭部中均不可能同時存在，如TCP和UDP協(xié)議不會同時出現(xiàn)在一個數(shù)據(jù)包的包頭域中，所以TCP源端口地址和UDP源端口地址〈TCP_SRC,UDP_SRC〉為排斥關系。

定義2 共存關系PC。表示協(xié)議中兩個匹配域Fi和Fj(i≠j)，當且僅當Fi存在時，F(xiàn)j必存在，反之亦然。如數(shù)據(jù)包中存在IPv4協(xié)議，就一定同時存在IPv4的源地址和目的地址兩個協(xié)議字段，所以〈IPv4_SRC,IPv4_DST〉為共存關系。

定義3 演進關系PE。表示協(xié)議中兩個匹配域Fi和Fj(i≠j)，其中一個匹配域由另外一個發(fā)展演化而來。比如IPv4協(xié)議到IPv6協(xié)議就是典型的演進關系。

對于OpenFlow1.3 協(xié)議中必須支持的13個匹配域，給出如下的關系矩陣，通過關系矩陣對規(guī)則集中的匹配字段進行壓縮合并，可有效減小所用流表表項位寬。

Π=

通過應用關系矩陣對OpenFlow交換機中存儲的流表寬度進行壓縮，比如〈Fi,Fj〉∈PO，兩者的位寬分別為W(Fi)和W(Fj)，則在表項存儲過程中可將Fi和Fj合并為一個匹配域Fi,j，同時添加一個標志位進行類型區(qū)分，比如標志位為0代表存儲的實際為Fi，標志位為1代表實際為Fj，則合并后匹配域的位寬為:

W(Fi,j)=max(W(Fi),W(Fj))+1

(1)

另外，對于演進關系，文獻[12]給出了由IPv4向IPv6轉(zhuǎn)換的具體方案。

通過以上對匹配域間邏輯關系的分析，可以在一定程度上減少流表中匹配域的數(shù)量，縮減表項位寬，為進一步規(guī)則集的處理提供便利。

1.2 基于匹配域的獨立規(guī)則子集分割

定義4 規(guī)則獨立性。對于規(guī)則集U中的兩條規(guī)則Ri和Rj(i≠j)，如果Ri和Rj之間沒有重疊，即任何一個數(shù)據(jù)包頭最多匹配其中的一條規(guī)則，則稱Ri與Rj相互獨立，記作Ri∩Rj=?。由相互獨立的規(guī)則組成的規(guī)則集稱為獨立規(guī)則集。

圖1中所示的規(guī)則集U1包含R1～R3三條規(guī)則，每條規(guī)則具有兩個匹配域F1、F2。其中，F(xiàn)1能夠區(qū)分規(guī)則R1和R2，二者關于匹配域F1相互獨立。而R1與R3或R2與R3都存在匹配域重疊。例如當數(shù)據(jù)包頭數(shù)據(jù)為〈F1,F2〉=〈2,4〉時，可同時匹配規(guī)則R1與R3，此時就需要考慮各規(guī)則的優(yōu)先級。而通過將規(guī)則R3分離，規(guī)則集U1可以分割為獨立規(guī)則集SI={R1,R2}和獨立規(guī)則補集SD={R3}，而SI中的規(guī)則僅需匹配域F1就可區(qū)分并且無需考慮規(guī)則優(yōu)先級。

圖1 獨立規(guī)則子集分割示意圖

通過將整體規(guī)則集分割為獨立規(guī)則集及其補集，利用規(guī)則獨立性，僅需部分匹配域就可進行規(guī)則區(qū)分，從而減少TCAM存儲空間。本文根據(jù)所用匹配域的不同，首先將規(guī)則集分割為多個不相關的獨立規(guī)則子集；然后對每個獨立規(guī)則子集所用匹配域進行位提取，使得僅需部分匹配域的部分位就可完成匹配查找，進一步減少匹配位寬。

圖2所示為包含五條規(guī)則、具有三個匹配域的規(guī)則集U2，以F1～F3三個匹配域區(qū)分的最大獨立規(guī)則集為SI={R1,R2,R3,R4}，補集SD={R5}；如果基于F1、F2進行分割則可得到SI={R1,R2,R3}，SD={R4,R5}；或者，如果將R3和R5放入補集SD中，則其余規(guī)則基于F3相互獨立。而這三種分割方法所用到的查找資源是不同的。

圖2 多匹配域規(guī)則集分割示意圖

現(xiàn)對整體規(guī)則集U的分割問題描述如下：假設從具有k個匹配域的整體規(guī)則集U中選取匹配域向量M=(M1,M2,…,Mb)作為劃分依據(jù)，將規(guī)則集劃分為b組相互獨立的子規(guī)則集合SI={S1,S2,…,Sb}和一個獨立規(guī)則補集SD。在劃分過程中，本文所提算法中的主要符號和含義如表1所示。

表1 算法中主要符號及含義

具體的劃分方法可表示如下：

P(S,M):U∈

(2)

各個子集之間滿足：

(3)

(4)

由式(2)可知，各個獨立規(guī)則子集之間互不相交，該方法犧牲了規(guī)則間的相關性，減少了信息的冗余復制。在實際應用中，單個匹配域就可實現(xiàn)50%以上規(guī)則集的獨立性，而對于某些特定規(guī)則集，甚至可以達到80%以上，所以，可以通過提取匹配域?qū)⒄w規(guī)則集劃分為獨立規(guī)則子集及其補集。算法1給出了算法的實現(xiàn)過程，首先遍歷所有匹配域，求出單個匹配域所能區(qū)分的最大獨立規(guī)則子集(Maximal Independent Rule Subset, MIRS)。最大獨立規(guī)則子集的求解由函數(shù)MIRS得出，函數(shù)返回i個匹配域下分割的最大子集Si及所用的匹配域組合Mi，具體由算法2描述。然后在整體規(guī)則集中剔除已分割的規(guī)則，再利用剩余匹配域?qū)ζ溥M行分割，此時使所用匹配域個數(shù)動態(tài)增加(一般不超過3個)，靈活調(diào)整后續(xù)匹配位寬。另外，設置已分割規(guī)則集占整體規(guī)則集的閾值Tr，當所用匹配域總數(shù)達到k個或者已分割規(guī)則集數(shù)目達到閾值Tr，終止分割過程。最后，將剩余規(guī)則放入規(guī)則補集SD中。由于具有k個匹配域，所以最多進行k次算法2循環(huán)，通過設置閾值Tr，避免規(guī)則集過度分割，使得實際應用中循環(huán)次數(shù)遠少于k。

算法1 獨立規(guī)則子集分割算法。

輸入U，k，Tr；

輸出 獨立規(guī)則集SI，規(guī)則補集SD。

sum=0;i=1;

whilesum

//當所用匹配域小于k個或分割規(guī)則在閾值Tr以內(nèi)，執(zhí)行循環(huán)

{Si,Mi}=MIRS(U,i)；

//執(zhí)行求解i個匹配域最大獨立規(guī)則集的子程序

pushSiintoSI；

sum=sum+num(Mi)；

//統(tǒng)計所用匹配域個數(shù)

deleteSifromU；

//從整體規(guī)則集中刪除已分割的Si

i=i+1；

end while

pushUtoSD；

//循環(huán)結(jié)束，將剩余規(guī)則放入規(guī)則補集SD中

returnSI，SD；

算法2給出了求解i個匹配域下所能分割最大獨立規(guī)則集的算法步驟。第一層循環(huán)在k個匹配域中選擇不大于i的匹配域組合，具有O(k2)的時間復雜度。第二層循環(huán)遍歷規(guī)則集U中的每組規(guī)則對，確定在當前匹配域組合下能區(qū)分的獨立規(guī)則集，當規(guī)則集U中規(guī)則數(shù)為u=num(U)時，具有O(u2)的復雜度。其次，求解出每種匹配域組合的最大獨立規(guī)則集后，與當前情況進行比較，保留包含規(guī)則數(shù)目最多的方案。最后，在互相沖突的每組規(guī)則子集中，選擇優(yōu)先級最低的規(guī)則放入Si中。最大獨立規(guī)則集的求解是一類NP難問題，通過簡化將其化為圖論中的的連通子圖問題，可以將總的算法時間復雜度減少到了O(k2u2)。

算法2 最大獨立規(guī)則集求解算法。

輸入U，k，i；

輸出 最大獨立規(guī)則集Si，所用匹配域Mi。

function MIRS(U,i)

initializeSi，Mi；

u=num(U);

//獲取規(guī)則集U中的規(guī)則數(shù)

for eachMiwhosenum(Mi)≤i

//遍歷匹配域個數(shù)不大于i的組合

for each pair ruleRm,Rn∈U(m≠n)

ifRm∩Rn=? based onMi

//Rm與Rn基于匹配域組合Mi獨立

else

for each conflict group inSD

select the least priorityRx；

addRxtoSi；

//選取沖突組中最低優(yōu)先級規(guī)則Rx放入Si

1.3 獨立規(guī)則子集匹配域位提取

對于本文中基于多匹配域劃分的獨立規(guī)則子集，可將匹配條目位寬進一步壓縮。如圖3所示，對于獨立規(guī)則集SI={R1=(100*),R2=(1010),R3=(000*),R4=(001*)}。雖然每個規(guī)則包含位數(shù)為4，但通過觀察可得，僅憑第二位和第三位就可分離所有規(guī)則。通過選擇一組適當?shù)奈唬嗷オ毩⒁?guī)則集中的所有規(guī)則均可“完全區(qū)分”。

圖3 獨立規(guī)則集位提取示意圖

算法3 獨立規(guī)則子集位提取算法。

輸入 獨立規(guī)則子集Si，第i個匹配域組合Mi；

輸出 第i個規(guī)則子集位提取標記Bi。

initializeBi；

//初始默認包含所有非三態(tài)位

j=num(Bi)；

//提取Bi的位數(shù)

form=1 toj

flag=0;

//更新標志

returnBi；

2 查找架構(gòu)

本文提出的BEIS方案主要根據(jù)匹配域邏輯關系進行域合并，并基于獨立規(guī)則子集進行位提取。通過如圖4的硬件查找架構(gòu)可實現(xiàn)本壓縮方案。該結(jié)構(gòu)主要分為三層：控制層、中間層及數(shù)據(jù)層?？刂茖荧@取網(wǎng)絡拓撲并下發(fā)流表，中間層運行第1章中的相關算法，將包頭域的處理規(guī)則下放到匹配域合并和位提取模塊，并且將處理后的流表數(shù)據(jù)發(fā)送到相應TCAM單元。數(shù)據(jù)層通過現(xiàn)場可編程門陣列(Field-Programmable Gate Array, FPGA)或網(wǎng)絡處理器(Network Processor, NP)等負責相應匹配域的處理操作，并將包頭數(shù)據(jù)送往TCAM中進行表項查找。根據(jù)獨立規(guī)則集劃分的不同，給不同的子集分配邏輯獨立的TCAM和靜態(tài)隨機存儲器(Static Random Access Memory， SRAM)塊，其中TCAM-Si存儲獨立規(guī)則子集Si中經(jīng)過處理的流表，SRAM中存儲匹配域合并和位提取信息用于假陽性驗證。TCAM-SD存儲未經(jīng)處理的規(guī)則補集SD中的流表。由于匹配域數(shù)量和覆蓋規(guī)則集閾值Tr的限制，所用的TCAM-Si一般不會超過5個。

圖4 查找架構(gòu)

查找過程：當解析模塊將提取的數(shù)據(jù)包頭發(fā)送到本查找模塊，匹配域合并模塊根據(jù)中間層下發(fā)的處理規(guī)則對包頭域進行相應處理，改變包頭中匹配域?qū)挾炔l(fā)送到位提取模塊，同時匹配域合并模塊也將合并后包頭域送往規(guī)則補集TCAM-SD中進行查找。位提取模塊根據(jù)掩碼提取包頭域中相應位并發(fā)往不同的TCAM塊用于查找。查找結(jié)果可分為以下四種情況：1)當且僅當TCAM-SD中匹配時，輸出即為當前查找結(jié)果；2)當且僅當TCAM-Si中匹配時，只需對該條匹配規(guī)則集進行假陽性驗證；3)當TCAM-Si與TCAM-SD都有匹配結(jié)果時，由算法2可知，TCAM-SD優(yōu)先級要高于TCAM-Si的優(yōu)先級，則判定TCAM-SD中的為匹配結(jié)果；4)當多個TCAM-Si均有匹配結(jié)果輸出時，根據(jù)SRAM中存儲的信息鏈接到原始規(guī)則集中的優(yōu)先級判定和假陽性驗證。

3 實驗仿真與評估

本文實驗主要選擇實際應用和仿真產(chǎn)生的兩類規(guī)則集進行所提方案的壓縮效果驗證。由于OpenFlow協(xié)議尚未大規(guī)模部署在實際網(wǎng)絡中，難以獲得大量的流表數(shù)據(jù)對模型進行評估，所以本文測試數(shù)據(jù)選取來自國家寬帶網(wǎng)絡與應用工程技術研究中心的OpenFlow測試流表和ClassBench[13]產(chǎn)生的分類規(guī)則集。同時，相關算法在Matlab 2015a中進行仿真，測試主機為Intel Core i5-3450 3.1 GHz，內(nèi)存8 GB，操作系統(tǒng)Windows 7。

3.1 OpenFlow壓縮性能

本文的BEIS方案通過基于匹配域邏輯關系的合并來減少匹配域個數(shù)，再進行獨立規(guī)則集分割與位提取壓縮查找所用的TCAM表項位寬。為防止獨立規(guī)則集的分割過度，算法1中設置閾值Tr來控制SI所包含的規(guī)則占總體規(guī)則的比例。圖5顯示了在規(guī)則數(shù)N=5 000的情況下，不同閾值Tr在本文方案所分割出的獨立規(guī)則子集個數(shù)及壓縮效果。由圖5可以看出，在Tr值為0.94的條件下，只需3個獨立規(guī)則子集和1個規(guī)則補集就可區(qū)分所有規(guī)則，并且壓縮比率(壓縮后與壓縮前占用空間比率)達到了24%，效果最佳。所以，在實際應用中，可通過調(diào)整閾值Tr來改變分割子集個數(shù)以達到最佳優(yōu)化效果。

圖6顯示了隨著OpenFlow流表規(guī)模的增大，本文方案BEIS、文獻[10]的H-SOFT(Heuristic Storage space Optimisation algorithm for Flow Table)與文獻[11]的匹配域裁剪(Field Trimmer， FT)方案對TCAM空間的壓縮比率。從圖6中可以看出，本文所提方案可實現(xiàn)22%～35%的壓縮比率，分別比H-SOFT和FT方案減少了40%、20%左右的TCAM存儲空間。但是隨著流表規(guī)模的增大，壓縮比率變化較慢，之后甚至有所增加。這是由于規(guī)則集中規(guī)則數(shù)量的增加，導致獨立規(guī)則子集和所需匹配域數(shù)量增加，使得提取位的寬度增加。不過從整體看來，在閾值Tr=0.94的情況下，仍有30%的壓縮比率。

圖5 不同閾值Tr下獨立子集個數(shù)與壓縮比率變化

圖6 不同方案下對OpenFlow流表的壓縮性能對比

3.2 算法運行時間

控制層下發(fā)的流表數(shù)據(jù)都要根據(jù)1.2和1.3節(jié)所提的算法進行處理后發(fā)送到TCAM中，運行算法需要一定的運算開銷。圖7顯示了在實驗硬件環(huán)境下本文BEIS方案(以Tr=0.94為例)、H-SOFT算法和FT算法的運行時間對比。從圖7可以看出，BEIS方案的運行時間要高于H-SOFT算法和FT算法，并且隨著流表規(guī)模的增加，運行時間的增長速度也略高于后兩者。由于本文方案實現(xiàn)了更加細粒度的規(guī)則集分割與位提取，算法運行時搜索了所用匹配域的位空間，所以增加了執(zhí)行時間。雖然引入局部尋優(yōu)策略可以有效減少算法時間，但隨著流表規(guī)模增加，運行時間仍增長較快,所以今后工作會進一步對算法進行優(yōu)化，在滿足功能完整性的同時盡量降低時間復雜度。

3.3 基于ClassBench的壓縮性能分析

為了進一步驗證本文方案對各種規(guī)則集的適用情況，對來自ClassBench的12種分類規(guī)則集(包括ACL1、ACL2、ACL3、ACL4、ACL5、FW1、FW2、FW3、FW4、FW5、IPC1、IPC2)進行測試分析，每種分類規(guī)則集均各自具有10 000條規(guī)則。ClassBench是由華盛頓大學開發(fā)的實驗平臺，它利用現(xiàn)實分類規(guī)則集作為基準，產(chǎn)生模擬真實網(wǎng)絡環(huán)境的實驗規(guī)則庫。圖8給出了本文模型與H-SOFT、FT模型對不同規(guī)則集的壓縮性能對比。

圖7 不同流表規(guī)模下各算法運行時間對比

圖8 基于ClassBench規(guī)則集的壓縮性能對比

從整體來看，本文方案在閾值Tr=0.94時采用更少位完成了對規(guī)則集的區(qū)分，比H-SOFT方案節(jié)省了60%左右的TCAM空間，比FT(β=0.95)方案節(jié)省了40%左右的TCAM空間。對于部分區(qū)分度明顯的規(guī)則集，如訪問控制列表(Access Control List, ACL)，在閾值Tr=0.94時，24位的匹配值就可實現(xiàn)ACL1規(guī)則集很好的區(qū)分效果。但對同樣的10 000規(guī)則集的分類，顯然防火墻(FireWall, FW)規(guī)則集比其他兩類需要更多的位進行區(qū)分，這說明FW規(guī)則集具有更高復雜性。而對于閾值Tr=0.94和Tr=0.99兩種情況，雖然只是減少了5%的規(guī)則覆蓋，但所用的TCAM存儲資源減少了40%左右，所以，在實際應用中，可以通過調(diào)整閾值，靈活調(diào)整所用的匹配位寬與TCAM資源。

4 結(jié)語

本文針對網(wǎng)絡快速發(fā)展帶來的流表位寬和規(guī)模擴張問題，提出了一種基于OpenFlow多匹配域的包分類規(guī)則集壓縮方法。一方面考慮多匹配域間的邏輯關系，利用匹配字段的相關性進行合并，從而減少所用匹配域數(shù)量；另一方面，基于規(guī)則獨立性將多匹配域的包分類規(guī)則集劃分成多個規(guī)模更小、匹配域更少的獨立規(guī)則子集。進一步考慮獨立規(guī)則集的匹配特性，對匹配字段進行位提取，使僅憑部分位就可完成匹配查找操作，從而壓縮規(guī)則存儲空間。實驗結(jié)果表明，對于OpenFlow多匹配域分類規(guī)則集和經(jīng)典五元組包分類規(guī)則集均有明顯的壓縮效果。但本文方案的時間復雜度仍需進一步優(yōu)化，所以后續(xù)的研究思路是設置合適的收斂策略，進一步減少算法的運行時間。