呂 昭，李 韜

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

1 引言

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

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

2 報文分類問題

2.1 報文分類問題描述

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

報文分類的分類器一般都包含一個分類規(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)報文的一個頭字段。過濾規(guī)則的域有四種表達形式，可以是一個精確的值，也可以是前綴表示（常用于地址匹配）、范圍表示（常用于端口號匹配）或含有通配符表示［4］。

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

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

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

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

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

2.2 相關(guān)工作

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

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

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

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

3 OpenFlow報文分類問題

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

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

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

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

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

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

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

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

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

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

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

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

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

OF＿CBF算法有如下特點：

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

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

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

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

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

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

4.2 OF＿CBF算法驗證與分析

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

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

（2）性能驗證。通過不同Hash函數(shù)個數(shù)，再添加不同數(shù)量的規(guī)則來進行算法性能的驗證。表1為不同Hash函數(shù)個數(shù)情況下，規(guī)則庫個數(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ù)的情況下，當規(guī)則庫有100條規(guī)則時，均不匹配的報文通過時的平均最快時鐘頻率為425.678 MHz，大于隨機報文匹配的時鐘頻率284.884 MHz。這是由于OF＿CBF的特點是先進行Hash索引，找到對應(yīng)的特征向量進行查看，對應(yīng)的特征向量匹配后再進行鏈表的精確匹配。因此，對于OF＿CBF算法不匹配的查找開銷要小于匹配的查找開銷。

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

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

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

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

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

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

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

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

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

OF＿FSMP算法的匹配報文模塊通過狀態(tài)機實現(xiàn)。其中Pkt＿Valid為報文有效信號，當Pkt＿Valid＝1時輸入的Pkt信號有效。Res＿Valid信號為結(jié)果有效信號，Ready信號為準備信號，Ready＝1算法可以開始下一次匹配。狀態(tài)機如圖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)為查詢過程。通過當前的查詢狀態(tài)，將報文的每一位當做輸入，進行查詢狀態(tài)的轉(zhuǎn)換，最終當轉(zhuǎn)換到最終狀態(tài)時，轉(zhuǎn)到FINISH狀態(tài)。否則轉(zhuǎn)到PRO狀態(tài)，繼續(xù)進行查詢。

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

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

5.2 OF＿FSMP算法驗證與分析

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

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

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

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

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

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

6 結(jié)束語

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

附中文參考文獻：

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

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

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

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

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

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