基于OpenFlow的報(bào)文分類算法研究與實(shí)現(xiàn)＊

呂 昭，李 韜

（國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南長沙410073）

1 引言

隨著互聯(lián)網(wǎng)的發(fā)展，今天的互聯(lián)網(wǎng)業(yè)務(wù)對互聯(lián)網(wǎng)提出了越來越高的傳輸質(zhì)量要求，為了滿足互聯(lián)網(wǎng)新的業(yè)務(wù)需求，斯坦福大學(xué)提出了一種新型網(wǎng)絡(luò)交換模型—Open Flow。OpenFlow的開放性和創(chuàng)新的網(wǎng)絡(luò)互連概念使其發(fā)展迅猛，成為近年來新興的熱門技術(shù)。

OpenFlow 1.1規(guī)范［1］規(guī)定流表項(xiàng)由頭域、計(jì)數(shù)器和操作組成，其中頭域是一個15元組，是流表項(xiàng)的標(biāo)識；計(jì)數(shù)器用來計(jì)數(shù)流表項(xiàng)的統(tǒng)計(jì)數(shù)據(jù)；操作標(biāo)明了與該流表項(xiàng)匹配的數(shù)據(jù)包應(yīng)該執(zhí)行的操作。通過將數(shù)據(jù)流與流表中的流表項(xiàng)匹配，從而決定轉(zhuǎn)發(fā)的目的端口。與傳統(tǒng)的報(bào)文頭5元組匹配規(guī)則相比，OpenFlow的15元組規(guī)則更加增加了數(shù)據(jù)流匹配的難度［2］。因此，15元組匹配的報(bào)文分類是研究OpenFlow報(bào)文分類技術(shù)的重點(diǎn)和難點(diǎn)。

2 報(bào)文分類問題

2.1 報(bào)文分類問題描述

由于互聯(lián)網(wǎng)應(yīng)用中多樣化和差異化的需求，網(wǎng)絡(luò)設(shè)備需要能夠根據(jù)網(wǎng)絡(luò)中報(bào)文字段對報(bào)文進(jìn)行差異化處理。報(bào)文分類就是為了滿足網(wǎng)絡(luò)的差異化處理而產(chǎn)生的。它是根據(jù)報(bào)文頭部信息的關(guān)鍵字段對報(bào)文進(jìn)行分類，網(wǎng)絡(luò)設(shè)備針對不同類別的報(bào)文可以采取不同的操作［3］。

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

每個頭字段具體的匹配方式由過濾規(guī)則相應(yīng)域的表達(dá)形式?jīng)Q定，共有三種不同的匹配方式：

（1）精確匹配：報(bào)文頭字段的值與過濾規(guī)則匹配域的精確值匹配。

（2）前綴匹配：報(bào)文頭字段的值符合過濾規(guī)則匹配域規(guī)定的前綴。

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

當(dāng)一個報(bào)文的d個頭字段與一條過濾規(guī)則的全部d個域均匹配時，就稱該報(bào)文匹配該規(guī)則。由于過濾規(guī)則的交疊性，一個報(bào)文可能匹配規(guī)則庫中的多條過濾規(guī)則，因此選取這些過濾規(guī)則中優(yōu)先級最高的規(guī)則進(jìn)行匹配［5］。

2.2 相關(guān)工作

按不同的匹配方式可以將報(bào)文分類算法進(jìn)行分類：

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

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

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

3 OpenFlow報(bào)文分類問題

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

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

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

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

Figure 1 Schematic diagram of packet classification for Open Flow圖1 OpenFlow報(bào)文分類示意圖

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

4 基于Bloom Filter的精確報(bào)文分類算法

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

4.1 OF＿CBF算法設(shè)計(jì)

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

Figure 2 Counting bloom filter圖2 計(jì)數(shù)型Bloom Filter

不難發(fā)現(xiàn)，計(jì)數(shù)器的數(shù)值反映了產(chǎn)生相同索引值的數(shù)據(jù)的個數(shù)。此時需要考慮的問題是對計(jì)數(shù)器的大小要選取適當(dāng)，避免出現(xiàn)數(shù)值溢出的情況。

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

OF＿CBF算法有如下特點(diǎn)：

（1）運(yùn)用計(jì)數(shù)型Bloom Filter來代替標(biāo)準(zhǔn)的Bloom Filter。計(jì)數(shù)型Bloom Filter不僅完全具備了標(biāo)準(zhǔn)Bloom Filter的一切性能，而且很好地解決了集合中規(guī)則刪除時可能產(chǎn)生的查詢失敗問題。

（2）在計(jì)數(shù)型Bloom Filter查詢結(jié)果的基礎(chǔ)上，引入動態(tài)鏈表執(zhí)行規(guī)則的精確匹配。不論是標(biāo)準(zhǔn)Bloom Filter還是計(jì)數(shù)Bloom Filter，其假陽性的產(chǎn)生是不可避免的，只能通過對某些參數(shù)的設(shè)置來使其產(chǎn)生的概率最小。在此動態(tài)鏈表提供精確匹配的目的是及時對假陽性進(jìn)行檢測，對錯誤匹配結(jié)果做出更正，提高報(bào)文分類算法結(jié)果的準(zhǔn)確性。

圖3是一個OF＿CBF的結(jié)構(gòu)示例，圖中計(jì)數(shù)器為每一個特征向量對應(yīng)的計(jì)數(shù)器，首地址為每一個特征向量對應(yīng)的存儲規(guī)則的動態(tài)表項(xiàng)，X、Y為報(bào)文規(guī)則。

Figure 3 Schematic diagram of OF＿CBF圖3 OF＿CBF結(jié)構(gòu)示意圖

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

上述兩個特點(diǎn)很好地反映出OF＿CBF算法的本質(zhì)。OF＿CBF充分發(fā)揮了Bloom Filter基于Hash查找、針對報(bào)文的精確匹配的優(yōu)勢；同時，釆取有效措施盡力彌補(bǔ)其在刪除規(guī)則和假陽性等方面的不足，使得Bloom Filter能夠在報(bào)文分類領(lǐng)域有新的應(yīng)用。

4.2 OF＿CBF算法驗(yàn)證與分析

將算法OF＿CBF用硬件語言實(shí)現(xiàn)后，再通過Xilinx公司生產(chǎn)的型號為V5系列的240T上進(jìn)行綜合實(shí)現(xiàn)，并對算法的功能和性能進(jìn)行驗(yàn)證。

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

（2）性能驗(yàn)證。通過不同Hash函數(shù)個數(shù)，再添加不同數(shù)量的規(guī)則來進(jìn)行算法性能的驗(yàn)證。表1為不同Hash函數(shù)個數(shù)情況下，規(guī)則庫個數(shù)不同時，通過器件進(jìn)行綜合實(shí)現(xiàn)得出的時鐘頻率表。

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

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

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

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

5 基于有限自動機(jī)的通配報(bào)文分類算法

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

通過正則表達(dá)式進(jìn)行通配符匹配是可行的［14］。而通過分析，正則表達(dá)式的匹配原理是有限自動機(jī)的匹配，正則表達(dá)式的匹配與有限自動機(jī)匹配是等價(jià)的，因此有限自動機(jī)的匹配實(shí)際上可以實(shí)現(xiàn)正則表達(dá)式的匹配。而有限自動機(jī)可以有效地在硬件中實(shí)現(xiàn)，因此我們可以通過有限自動機(jī)實(shí)現(xiàn)報(bào)文分類中的通配符匹配。通過一定的算法將正則表達(dá)式轉(zhuǎn)換為有限自動機(jī)，從而實(shí)現(xiàn)高效的報(bào)文匹配操作［15］。

5.1 OF＿FSMP算法設(shè)計(jì)

綜上所述，通過將報(bào)文規(guī)則的正則表達(dá)式轉(zhuǎn)換為有限自動機(jī)的方法可以有效解決報(bào)文分類問題。因此，本文設(shè)計(jì)實(shí)現(xiàn)了基于有限自動機(jī)的報(bào)文匹配算法——OF＿FSMP算法，用以解決網(wǎng)絡(luò)處理器中面向Open Flow的通配符匹配問題。

（1）OF＿FSMP算法結(jié)構(gòu)。OF＿FSMP算法通過存儲器將相應(yīng)的狀態(tài)數(shù)、匹配結(jié)果以及最終狀態(tài)標(biāo)志位進(jìn)行存儲。設(shè)地址位為n位，則地址位的前（n－1）位為當(dāng)前的狀態(tài)數(shù)，第n位當(dāng)前輸入條件，即當(dāng)前應(yīng)該輸入的報(bào)文的某一位。而存儲器存儲的信息分為下一跳的狀態(tài)數(shù)、終止?fàn)顟B(tài)標(biāo)志位以及結(jié)果位。因此，設(shè)當(dāng)前狀態(tài)數(shù)為state，則mem［state，Pkt［i］］為存儲的下一跳狀態(tài)數(shù)據(jù)結(jié)構(gòu)。以此來跳轉(zhuǎn)最終輸入匹配結(jié)果。

（2）OF＿FSMP算法設(shè)計(jì)。OF＿FSMP算法主要包含三個步驟：構(gòu)建自動機(jī)、存儲自動機(jī)和通過自動機(jī)匹配規(guī)則。其中，構(gòu)建狀態(tài)機(jī)又包含添加規(guī)則和刪除規(guī)則。構(gòu)建狀態(tài)機(jī)和通過存儲器的數(shù)據(jù)結(jié)構(gòu)存儲狀態(tài)機(jī)的過程均是通過軟件實(shí)現(xiàn)的。報(bào)文匹配的過程是通過硬件實(shí)現(xiàn)的。圖4是OF＿FSMP算法的流程圖。

Figure 4 Schematic diagram of OF＿FSMP圖4 OF＿FSMP算法結(jié)構(gòu)示意圖

OF＿FSMP算法的匹配報(bào)文模塊通過狀態(tài)機(jī)實(shí)現(xiàn)。其中Pkt＿Valid為報(bào)文有效信號，當(dāng)Pkt＿Valid＝1時輸入的Pkt信號有效。Res＿Valid信號為結(jié)果有效信號，Ready信號為準(zhǔn)備信號，Ready＝1算法可以開始下一次匹配。狀態(tài)機(jī)如圖5所示。其中，

WAIT狀態(tài)為初始等待狀態(tài)；若Pkt＿Valid＝1，則轉(zhuǎn)到INI狀態(tài)。

INI狀態(tài)為初始化狀態(tài)，將查詢狀態(tài)置0，轉(zhuǎn)到PRO狀態(tài)。

PRO狀態(tài)為查詢過程。通過當(dāng)前的查詢狀態(tài)，將報(bào)文的每一位當(dāng)做輸入，進(jìn)行查詢狀態(tài)的轉(zhuǎn)換，最終當(dāng)轉(zhuǎn)換到最終狀態(tài)時，轉(zhuǎn)到FINISH狀態(tài)。否則轉(zhuǎn)到PRO狀態(tài)，繼續(xù)進(jìn)行查詢。

Figure 5 State machine of OF＿FSMP圖5 OF＿FSMP算法狀態(tài)機(jī)

FINISH狀態(tài)為停止?fàn)顟B(tài)，若Ready信號置1，則轉(zhuǎn)到WAIT狀態(tài)。

5.2 OF＿FSMP算法驗(yàn)證與分析

將算法OF＿FSMP用硬件語言實(shí)現(xiàn)后，再通過Xilinx公司生產(chǎn)的型號為V5系列的240T進(jìn)行綜合實(shí)現(xiàn)，并對算法的功能和性能進(jìn)行驗(yàn)證。

（1）功能驗(yàn)證。先通過軟件協(xié)同，將系統(tǒng)匹配的規(guī)則進(jìn)行存儲，再測試大量隨機(jī)報(bào)文。經(jīng)過測試，所有報(bào)文分類結(jié)果均正確無誤，從而驗(yàn)證了算法的功能正確性。

（2）性能驗(yàn)證。與Net Logic公司33100系列TCAM對比，進(jìn)行性能驗(yàn)證。表2是TCAM與通過FPGA綜合實(shí)現(xiàn)的OF＿FSMP算法的性能對比情況。

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

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

假設(shè)OF＿FSMP算法合并后的狀態(tài)數(shù)為s，則算法最壞情況下的時間復(fù)雜度為O（s），即將所有狀態(tài)都遍歷了一遍。最好情況下的時間復(fù)雜度是1，即為直接匹配。OF＿FSMP算法的空間復(fù)雜度為O（s·（2＋log2s））。OF＿FSMP算法實(shí)現(xiàn)的硬件開銷較小，并且具有較高的匹配速度，在實(shí)際應(yīng)用下的效率較高。適合針對網(wǎng)絡(luò)處理器，面向OpenFlow的通配符匹配進(jìn)行高效的報(bào)文分類。

6 結(jié)束語

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

［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－h(huán)u.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－h(huán)ui，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）

附中文參考文獻(xiàn)：

［4］ 孫毅，劉彤，蔡一兵，等.報(bào)文分類算法研究［J］.計(jì)算機(jī)應(yīng)用研究，2007，24（4）：5－7.

［5］ 高蕾，譚明峰，龔正虎.IP報(bào)文分類算法綜述與評價(jià)［J］.計(jì)算機(jī)工程與科學(xué)，2006，28（3）：70－73.

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

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

［15］ 李鋼，吳燎原，張仁斌，等.基于有限自動機(jī)的模式匹配算法及其應(yīng)用研究［J］.系統(tǒng)仿真學(xué)報(bào)，2007，19（12）：2772－2775.

［16］ 陳曙暉，孫志剛，蘇金樹.線速硬件網(wǎng)絡(luò)入侵檢測系統(tǒng)的范圍匹配研究［J］.通信學(xué)報(bào)，2006，27（10）：7－12.