基于OpenFlow的報文分類算法研究與實現＊

呂 昭，李 韜

（國防科學技術大學計算機學院，湖南長沙410073）

1 引言

隨著互聯網的發展，今天的互聯網業務對互聯網提出了越來越高的傳輸質量要求，為了滿足互聯網新的業務需求，斯坦福大學提出了一種新型網絡交換模型—Open Flow。OpenFlow的開放性和創新的網絡互連概念使其發展迅猛，成為近年來新興的熱門技術。

OpenFlow 1.1規范［1］規定流表項由頭域、計數器和操作組成，其中頭域是一個15元組，是流表項的標識；計數器用來計數流表項的統計數據；操作標明了與該流表項匹配的數據包應該執行的操作。通過將數據流與流表中的流表項匹配，從而決定轉發的目的端口。與傳統的報文頭5元組匹配規則相比，OpenFlow的15元組規則更加增加了數據流匹配的難度［2］。因此，15元組匹配的報文分類是研究OpenFlow報文分類技術的重點和難點。

2 報文分類問題

2.1 報文分類問題描述

由于互聯網應用中多樣化和差異化的需求，網絡設備需要能夠根據網絡中報文字段對報文進行差異化處理。報文分類就是為了滿足網絡的差異化處理而產生的。它是根據報文頭部信息的關鍵字段對報文進行分類，網絡設備針對不同類別的報文可以采取不同的操作［3］。

報文分類的分類器一般都包含一個分類規則庫，該規則庫含有幾百到幾百萬條過濾規則（F1，F2，F3，…，Fn）。每條過濾規則可以含有s個匹配域（Fi［1］，Fi［2］，…，Fi［s］），其中每個匹配域都對應報文的一個頭字段。過濾規則的域有四種表達形式，可以是一個精確的值，也可以是前綴表示（常用于地址匹配）、范圍表示（常用于端口號匹配）或含有通配符表示［4］。

每個頭字段具體的匹配方式由過濾規則相應域的表達形式決定，共有三種不同的匹配方式：

（1）精確匹配：報文頭字段的值與過濾規則匹配域的精確值匹配。

（2）前綴匹配：報文頭字段的值符合過濾規則匹配域規定的前綴。

（3）通配符匹配：報文頭字段的值符合過濾規則規定的任意比特掩碼（Arbitrary Bitmask），如過濾規則01＊1，第三位為0或1時均可以匹配。

當一個報文的d個頭字段與一條過濾規則的全部d個域均匹配時，就稱該報文匹配該規則。由于過濾規則的交疊性，一個報文可能匹配規則庫中的多條過濾規則，因此選取這些過濾規則中優先級最高的規則進行匹配［5］。

2.2 相關工作

按不同的匹配方式可以將報文分類算法進行分類：

適合精確匹配的報文分類算法主要有簡單的線性匹配、基于Hash的匹配等算法。其中簡單的線性匹配實現簡單，但查找效率差，大部分基于精確匹配的報文分類算法都是基于Hash函數的。

適合前綴匹配的報文分類算法主要有基于查找樹的算法，如Grid－of－trie算法、BV和ABV算法以及HiCuts算法與HyperCuts算法等。

適合統配匹配的報文分類算法主要有基于硬件TCAM以及有限狀態機匹配等算法，其中，TCAM算法匹配速度快，但是功耗成本過高。有限狀態機匹配速度沒有TCAM快，但是成本功耗較低，適合大型規則庫。

3 OpenFlow報文分類問題

OpenFlow是一個軟硬件的網絡流轉換接口。它的核心思想很簡單，就是將原本完全由交換機/路由器控制的數據包轉發過程，轉化為由Open－Flow交換機（Open Flow Switch）和控制服務器（Controller）分別完成的獨立過程。轉變背后進行的實際上是控制權的交換。Open Flow交換機會在本地維護一個與轉發表不同的流表（Flow Table），如果要轉發的數據包在流表中有對應項，則直接進行快速轉發；若流表中沒有此項，數據包就會被送到控制服務器進行傳輸路徑的確認，再根據下發結果進行轉發。OpenFlow的開放性和創新的網絡互連概念使其發展迅猛，成為近年來新興的熱門技術。

Open Flow定義的流規則可以通過用戶的需求來設定。OpenFlow靈活的流報文分類可以被看做傳統五域分類的拓展［6］。Open Flow規范1.1對于每一個報文需要匹配的bit數從104增加到278，每個報文對15個字段進行所有的報文規則匹配。15個報文頭字段包括32位的Ingress port，64位的Metadata，18位的源/目的以太網地址，16位的以太網類型，12位的VLAN號，3位的VLAN優先級，20位的MPLS標簽，3位的MPLS流量類，32位的源/目的IP地址，8位的IP協議號，6位的Tos號以及16位的源/目的端口號。規則中字段的每一位可以被指做準確的數字或者是通配符，IP地址字段也可以作為一個前綴［1］。

OpenFlow交換機需要對15個報文頭字段進行分類匹配，并且針對每一個規則，報文頭各個字段都會進行不同的匹配方式，因此給報文分類帶來了更大的困難。針對Open Flow的報文分類問題，把規則字段做一個簡單的分類，其中Ingress port、Metadata、以太網類型、VLAN號、VLAN優先級、MLPS標簽、MPLS流量類、IP協議號、IP Tos號、源/目的端口號均需要進行精確匹配。源/目的以太網地址可以進行通配符匹配，源/目的IP地址可以進行前綴匹配或者通配符匹配。針對前綴匹配問題，已經有人進行了充分的研究，并且前綴匹配實際上是通配符匹配的一種特例。因此，本文將主要研究精確匹配和源/目的以太網地址和源/目的IP地址的通配符匹配。

本文將采用分而治之的思想，如圖1所示。首先將這些字段分為需要進行精確匹配的字段和需要進行通配符匹配的字段。然后，將這兩類字段分別在精確匹配引擎和通配符匹配引擎中進行規則匹配，分別得出匹配結果。最后將這兩個引擎匹配的結果進行匯總，最終匹配到一個優先級最高的規則。這樣分開處理可以有效提高報文分類的效率。

Figure 1 Schematic diagram of packet classification for Open Flow圖1 OpenFlow報文分類示意圖

本文中大部分字段都是基于精確匹配，基于Hash的報文分類算法Bloom Filter［7，8］在基于軟件的設計基礎上［9］，具有很好的性能和效率，能夠支持較大規模的規則庫。因此，精確字段匹配引擎通過Bloom Filter進行設計實現。源/目的以太網地址和源/目的IP地址基于通配符匹配，可以通過TCAM［10］進行匹配。但是，TCAM自身具有功耗大、成本高的缺點，并且不適合大型的規則庫。因此，本文提出了復雜字段匹配采用正則表達式匹配，通過構建有限自動機的方法來進行設計實現。這種方法具有良好的性能和效率，與TCAM相比成本較低，并且適合大型的規則庫［11］。

4 基于Bloom Filter的精確報文分類算法

Bloom Filter基于Hash查找，在報文不命中的情況下分類效率大大高于哈希鏈表方法，對于需要進行精確匹配的字段具有很高的分類效果，并且適合硬件實現。因此，本文實現了一種改進型的計數型鏈表Bloom Filter算法（OF＿CBF Open Flow＿Counter Bloom Filter）進行報文的精確匹配。

4.1 OF＿CBF算法設計

對Bloom Filter進行規則的插入不會產生任何問題，但是對Bloom Filter進行刪除規則操作會存在一定的問題。如果將被刪除數據產生的k個索引值對應的特征向量中的值置為0，則有可能導致數據集合中產生相同索引值的其他元素查詢失敗。為了解決Bloom Filter刪除規則，提出了計數型Bloom Filter［12］的概念。在一個計數型Bloom Filter中，每個索引值對應的特征向量不再是單獨的一位，而是一個計數器。圖2顯示了計數型Bloom Filter的基本結構。其中X、Y、Z為報文規則，特征向量由計數器代替原來的一位表示。其中Hash函數個數k＝2。如圖2所示，當插入一個數據時，索引值對應的計數器數值加1；同樣，當刪除一個數據時，計數器的數值減1。

Figure 2 Counting bloom filter圖2 計數型Bloom Filter

不難發現，計數器的數值反映了產生相同索引值的數據的個數。此時需要考慮的問題是對計數器的大小要選取適當，避免出現數值溢出的情況。

本文針對Bloom Filter查找方面的特點，面向Open Flow的簡單字段進行精確的報文匹配，并且基于網絡處理器的硬件結構，將計數型Bloom Filter與動態鏈表進行有效結合，提出OF＿CBF算法。動態鏈表的作用是存儲規則以便查詢時進行精確匹配。對于每個規則首先執行k次Hash計算，然后根據得到的j（≤k）個Hash key訪問特征向量，以特征向量為紐帶，并行對動態鏈表進行相應的操作，同時使用動態鏈表進行精確匹配可以有效解決假陽性的問題。

OF＿CBF算法有如下特點：

（1）運用計數型Bloom Filter來代替標準的Bloom Filter。計數型Bloom Filter不僅完全具備了標準Bloom Filter的一切性能，而且很好地解決了集合中規則刪除時可能產生的查詢失敗問題。

（2）在計數型Bloom Filter查詢結果的基礎上，引入動態鏈表執行規則的精確匹配。不論是標準Bloom Filter還是計數Bloom Filter，其假陽性的產生是不可避免的，只能通過對某些參數的設置來使其產生的概率最小。在此動態鏈表提供精確匹配的目的是及時對假陽性進行檢測，對錯誤匹配結果做出更正，提高報文分類算法結果的準確性。

圖3是一個OF＿CBF的結構示例，圖中計數器為每一個特征向量對應的計數器，首地址為每一個特征向量對應的存儲規則的動態表項，X、Y為報文規則。

Figure 3 Schematic diagram of OF＿CBF圖3 OF＿CBF結構示意圖

本文提出的OF＿CBF算法針對傳統的計數型鏈表Bloom filter的存儲規則進行了改進，減少了存儲空間。由于添加每個規則，都會產生j個Hash key訪問特征向量，而每個特征向量對應的鏈表均會存儲該規則，這就會造成存儲器的浪費。OF＿CBF算法對這種情況進行了存儲規則操作的優化，只訪問最小的Hash key對應的特征向量，然后將規則存儲在該特征向量對應的鏈表中。這樣就避免了在不同的特征向量對應的動態鏈表中重復存儲同一規則。圖3中實線部分即為特征向量對應存儲的動態鏈表，而虛線即為存儲優化后不用存儲的特征向量。由圖3可以看出這個方法可優化大量的存儲空間。

上述兩個特點很好地反映出OF＿CBF算法的本質。OF＿CBF充分發揮了Bloom Filter基于Hash查找、針對報文的精確匹配的優勢；同時，釆取有效措施盡力彌補其在刪除規則和假陽性等方面的不足，使得Bloom Filter能夠在報文分類領域有新的應用。

4.2 OF＿CBF算法驗證與分析

將算法OF＿CBF用硬件語言實現后，再通過Xilinx公司生產的型號為V5系列的240T上進行綜合實現，并對算法的功能和性能進行驗證。

（1）功能驗證。分別采用不同的Hash函數，首先通過大量隨機報文，以檢驗報文分類結果是否正確。再將規則邊沿的特定報文進行測試，以檢測算法功能的完備性。經過測試，所有報文分類結果均正確無誤，從而驗證了算法功能的正確性。

（2）性能驗證。通過不同Hash函數個數，再添加不同數量的規則來進行算法性能的驗證。表1為不同Hash函數個數情況下，規則庫個數不同時，通過器件進行綜合實現得出的時鐘頻率表。

Table 1 Performance testing of OF＿CBF表1 OF＿CBF算法性能測試對比結果 MHz

通過表1可以看出，隨著Hash函數個數的增加，算法匹配頻率減小，說明算法匹配速度隨著Hash函數個數增加而減小。而隨著規則數目的增加，算法匹配的速度也逐漸減小。

同時可以看出，在4個Hash函數的情況下，當規則庫有100條規則時，均不匹配的報文通過時的平均最快時鐘頻率為425.678 MHz，大于隨機報文匹配的時鐘頻率284.884 MHz。這是由于OF＿CBF的特點是先進行Hash索引，找到對應的特征向量進行查看，對應的特征向量匹配后再進行鏈表的精確匹配。因此，對于OF＿CBF算法不匹配的查找開銷要小于匹配的查找開銷。

假設OF＿CBF存儲有n條規則，特征向量為m bits，計數器a位，存儲器地址b位。對每一條規則我們用k個Hash函數對它進行運算，這些Hash函數的輸出是［1，m］的值，規則字段的最長長度為d。對一個規則進行Hash計算平均得到j個Hash key。設k個Hash函數的運算是并行的，時間開銷為1。

5 基于有限自動機的通配報文分類算法

正則表達式是對字符串操作的一種邏輯公式，是用事先定義好的一些特定字符及這些特定字符的組合，組成一個規則字符串，用這個規則字符串來表達對字符串的一種過濾邏輯［13］。

通過正則表達式進行通配符匹配是可行的［14］。而通過分析，正則表達式的匹配原理是有限自動機的匹配，正則表達式的匹配與有限自動機匹配是等價的，因此有限自動機的匹配實際上可以實現正則表達式的匹配。而有限自動機可以有效地在硬件中實現，因此我們可以通過有限自動機實現報文分類中的通配符匹配。通過一定的算法將正則表達式轉換為有限自動機，從而實現高效的報文匹配操作［15］。

5.1 OF＿FSMP算法設計

綜上所述，通過將報文規則的正則表達式轉換為有限自動機的方法可以有效解決報文分類問題。因此，本文設計實現了基于有限自動機的報文匹配算法——OF＿FSMP算法，用以解決網絡處理器中面向Open Flow的通配符匹配問題。

（1）OF＿FSMP算法結構。OF＿FSMP算法通過存儲器將相應的狀態數、匹配結果以及最終狀態標志位進行存儲。設地址位為n位，則地址位的前（n－1）位為當前的狀態數，第n位當前輸入條件，即當前應該輸入的報文的某一位。而存儲器存儲的信息分為下一跳的狀態數、終止狀態標志位以及結果位。因此，設當前狀態數為state，則mem［state，Pkt［i］］為存儲的下一跳狀態數據結構。以此來跳轉最終輸入匹配結果。

（2）OF＿FSMP算法設計。OF＿FSMP算法主要包含三個步驟：構建自動機、存儲自動機和通過自動機匹配規則。其中，構建狀態機又包含添加規則和刪除規則。構建狀態機和通過存儲器的數據結構存儲狀態機的過程均是通過軟件實現的。報文匹配的過程是通過硬件實現的。圖4是OF＿FSMP算法的流程圖。

Figure 4 Schematic diagram of OF＿FSMP圖4 OF＿FSMP算法結構示意圖

OF＿FSMP算法的匹配報文模塊通過狀態機實現。其中Pkt＿Valid為報文有效信號，當Pkt＿Valid＝1時輸入的Pkt信號有效。Res＿Valid信號為結果有效信號，Ready信號為準備信號，Ready＝1算法可以開始下一次匹配。狀態機如圖5所示。其中，

WAIT狀態為初始等待狀態；若Pkt＿Valid＝1，則轉到INI狀態。

INI狀態為初始化狀態，將查詢狀態置0，轉到PRO狀態。

PRO狀態為查詢過程。通過當前的查詢狀態，將報文的每一位當做輸入，進行查詢狀態的轉換，最終當轉換到最終狀態時，轉到FINISH狀態。否則轉到PRO狀態，繼續進行查詢。

Figure 5 State machine of OF＿FSMP圖5 OF＿FSMP算法狀態機

FINISH狀態為停止狀態，若Ready信號置1，則轉到WAIT狀態。

5.2 OF＿FSMP算法驗證與分析

將算法OF＿FSMP用硬件語言實現后，再通過Xilinx公司生產的型號為V5系列的240T進行綜合實現，并對算法的功能和性能進行驗證。

（1）功能驗證。先通過軟件協同，將系統匹配的規則進行存儲，再測試大量隨機報文。經過測試，所有報文分類結果均正確無誤，從而驗證了算法的功能正確性。

（2）性能驗證。與Net Logic公司33100系列TCAM對比，進行性能驗證。表2是TCAM與通過FPGA綜合實現的OF＿FSMP算法的性能對比情況。

Table 2 Performance testing analysis of TCAM and OF＿FSMP表2 TCAM與OF＿FSMP算法性能對比

通過表2進行縱向比較，我們可以看出隨著規則庫的增加，OF＿FSMP算法的空間消耗變大，匹配速度變慢。這是由于用于匹配的有限自動機規模增加。但是，由于可以通過前期軟件協同優化有限自動機，使其空間消耗變大的趨勢和匹配速度減慢的趨勢越來越小，說明算法比較適合大規模規則庫的擴展。通過表2進行橫向比較，我們可以看出在空間消耗和匹配速度上，OF＿FSMP算法均不如TCAM算法。雖然TCAM具有良好的查詢性能，但其實現1 bit的查詢功能需要10～12個晶體管，而SRAM只需4～6個晶體管［16］。因此，TCAM相比OF＿FSMP算法存在功耗高、價格貴的缺點。

假設OF＿FSMP算法合并后的狀態數為s，則算法最壞情況下的時間復雜度為O（s），即將所有狀態都遍歷了一遍。最好情況下的時間復雜度是1，即為直接匹配。OF＿FSMP算法的空間復雜度為O（s·（2＋log2s））。OF＿FSMP算法實現的硬件開銷較小，并且具有較高的匹配速度，在實際應用下的效率較高。適合針對網絡處理器，面向OpenFlow的通配符匹配進行高效的報文分類。

6 結束語

當前的網絡技術高速發展，網絡流量不斷增加，網絡應用技術不斷更新，為了滿足互聯網新業務的需求，OpenFlow技術營運而生并得到了快速的發展。Open Flow技術對于報文的處理是以報文分類作為支撐的。本文針對OpenFlow報文分類的不同匹配方式，通過Bloom Filter實現了一種面向OpenFlow精確報文分類的算法——OF＿CBF，通過正則表達式和有限自動機的匹配，實現了面向OpenFlow通配符報文分類的算法——OF＿FSMP。這種分而治之的方法可以有效解決OpenFlow基于多元組的靈活的匹配規則。下一步的工作重點是進行大量的報文分類實驗分析，進一步完善優化算法。

［1］ Open FlowSwitch specification 1.1.0［EB/OL］.［2013－07－21］.http：∥www.openflowswitch.org/doucuments/openflow－spec－v1.1.0.pdf.

［2］ Jiang W，Prasanna V K.Scalable packet classification on FPGA［J］.IEEE Transactions on Very Large Scale Integration（VLSI）Systems，2012，20（9）：1668－1680.

［3］ Song H，Lockwood J W.Efficient packet classification for network intrusion detection using FPGA［C］∥Proc of the ACM/SIGDA 13th International Symposium on Field－programmable Gate Arrays，2005：238－245.

［4］ Sun Yi，Liu Tong，Cai Yi－bing，et al.Research on packet classification algorithm［J］.Application Research of Computers，2007，24（4）：5－7.（in Chinese）

［5］ Gao Lei，Tan Ming－feng，Gong Zheng－hu.Survey and evaluation of IP packet classification algorithms［J］.Computer Engineering ＆Science，2006，28（3）：70－73.（in Chinese）

［6］ Ganegedara T，Jiang W，Prasanna V.FRUG：A benchmark for packet forwarding in future networks［C］∥Porc of 2010 Performance Computing and Communications Conference（IPCCC），2010：231－238.

［7］ Dharmapurikar S，Krishnamurthy P，Sproull T S，et al.Deep packet inspection using parallel bloom filters［J］.Micro，IEEE，2004，24（1）：52－61.

［8］ Bin Xiao，Yu Hua.Using parallel bloom filters for multiattribute representation on network services［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21（1）：20－32.

［9］ Bloom B H.Space/time trade－offs in Hash coding with allowable errors［J］.Communications of the ACM，1970，13（7）：422－426.

［10］ Chisvin L，Duckworth R J.Content－addressable and associative memory：Alternatives to the ubiquitous RAM［J］.IEEE Computer，1989，22（7）：51－64.

［11］ Liang Zhong－bin，Lan Ju－long，Xia Bin.Range encoding scheme based on TCAM packet classification［J］.Network and Communication，2010，36（8）：117－119.（in Chinese）

［12］ Guo D，Wu J，Chen H，et al.Theory and network applications of dynamic bloom filters［C］∥Proc of the 25th IEEE INFOCOM’06，2006：1－12.

［13］ Chen Qian.A fast string matching algorithm based on finite automation［J］.Computer Technology and Development，2009（1）：131－133.（in Chinese）

［14］ Aho A V，Corasick M J.Efficient string matching：An aid to bibliographic search［J］.Communications of the ACM，1975，18（6）：333－340.

［15］ Li Gang，Wu Liao－yuan，Zhang Ren－bing，et al.Research on algorithm of finite－automaton－based pattern matching and its applications［J］.Journal of System Simulation，2007，19（12）：2772－2775.（in Chinese）

［16］ Chen Shu－hui，Sun Zhi－gang，Su Jin－shu.Research on range matching for wire－speed hardwares NIDS［J］.Journal of Communications，2006，27（10）：7－12.（in Chinese）

附中文參考文獻：

［4］ 孫毅，劉彤，蔡一兵，等.報文分類算法研究［J］.計算機應用研究，2007，24（4）：5－7.

［5］ 高蕾，譚明峰，龔正虎.IP報文分類算法綜述與評價［J］.計算機工程與科學，2006，28（3）：70－73.

［11］ 梁仲斌，蘭巨龍，夏斌.基于TCAM報文分類的范圍編碼方案［J］.網絡與通信，2010，36（8）：117－119.

［13］ 陳倩.一種基于有限自動機的快速串匹配算法［J］.計算機技術與發展，2009（1）：131－133.

［15］ 李鋼，吳燎原，張仁斌，等.基于有限自動機的模式匹配算法及其應用研究［J］.系統仿真學報，2007，19（12）：2772－2775.

［16］ 陳曙暉，孫志剛，蘇金樹.線速硬件網絡入侵檢測系統的范圍匹配研究［J］.通信學報，2006，27（10）：7－12.