呂 昭，李 韜

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

1 引言

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

OpenFlow 1.1規(guī)范［1］規(guī)定流表項(xiàng)由頭域、計(jì)數(shù)器和操作組成，其中頭域是一個(gè)15元組，是流表項(xiàng)的標(biāo)識(shí)；計(jì)數(shù)器用來(lái)計(jì)數(shù)流表項(xiàng)的統(tǒng)計(jì)數(shù)據(jù)；操作標(biāo)明了與該流表項(xiàng)匹配的數(shù)據(jù)包應(yīng)該執(zhí)行的操作。通過(guò)將數(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)文分類問(wèn)題

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

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

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

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

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

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

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

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

2.2 相關(guān)工作

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

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

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

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

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

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

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

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

本文將采用分而治之的思想，如圖1所示。首先將這些字段分為需要進(jìn)行精確匹配的字段和需要進(jìn)行通配符匹配的字段。然后，將這兩類字段分別在精確匹配引擎和通配符匹配引擎中進(jìn)行規(guī)則匹配，分別得出匹配結(jié)果。最后將這兩個(gè)引擎匹配的結(jié)果進(jìn)行匯總，最終匹配到一個(gè)優(yōu)先級(jí)最高的規(guī)則。這樣分開(kāi)處理可以有效提高報(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ī)則庫(kù)。因此，精確字段匹配引擎通過(guò)Bloom Filter進(jìn)行設(shè)計(jì)實(shí)現(xiàn)。源/目的以太網(wǎng)地址和源/目的IP地址基于通配符匹配，可以通過(guò)TCAM［10］進(jìn)行匹配。但是，TCAM自身具有功耗大、成本高的缺點(diǎn)，并且不適合大型的規(guī)則庫(kù)。因此，本文提出了復(fù)雜字段匹配采用正則表達(dá)式匹配，通過(guò)構(gòu)建有限自動(dòng)機(jī)的方法來(lái)進(jìn)行設(shè)計(jì)實(shí)現(xiàn)。這種方法具有良好的性能和效率，與TCAM相比成本較低，并且適合大型的規(guī)則庫(kù)［11］。

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

Bloom Filter基于Hash查找，在報(bào)文不命中的情況下分類效率大大高于哈希鏈表方法，對(duì)于需要進(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ì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

OF＿FSMP算法的匹配報(bào)文模塊通過(guò)狀態(tài)機(jī)實(shí)現(xiàn)。其中Pkt＿Valid為報(bào)文有效信號(hào)，當(dāng)Pkt＿Valid＝1時(shí)輸入的Pkt信號(hào)有效。Res＿Valid信號(hào)為結(jié)果有效信號(hào)，Ready信號(hào)為準(zhǔn)備信號(hào)，Ready＝1算法可以開(kāi)始下一次匹配。狀態(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)為查詢過(guò)程。通過(guò)當(dāng)前的查詢狀態(tài)，將報(bào)文的每一位當(dāng)做輸入，進(jìn)行查詢狀態(tài)的轉(zhuǎn)換，最終當(dāng)轉(zhuǎn)換到最終狀態(tài)時(shí)，轉(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信號(hào)置1，則轉(zhuǎn)到WAIT狀態(tài)。

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

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

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

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

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

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

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

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

當(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íng)運(yùn)而生并得到了快速的發(fā)展。Open Flow技術(shù)對(duì)于報(bào)文的處理是以報(bào)文分類作為支撐的。本文針對(duì)OpenFlow報(bào)文分類的不同匹配方式，通過(guò)Bloom Filter實(shí)現(xiàn)了一種面向OpenFlow精確報(bào)文分類的算法——OF＿CBF，通過(guò)正則表達(dá)式和有限自動(dòng)機(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)文分類算法綜述與評(píng)價(jià)［J］.計(jì)算機(jī)工程與科學(xué)，2006，28（3）：70－73.

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

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

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

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