網(wǎng)絡(luò)處理模式匹配算法研究

摘要：主要從多個(gè)角度研究了經(jīng)典的15種單模式和7種多模式匹配算法，并以可編程網(wǎng)絡(luò)處理器為測(cè)試平臺(tái)對(duì)其中的5種單模式和4種多模式匹配算法分別在匹配時(shí)間、占用存儲(chǔ)空間以及預(yù)處理時(shí)間方面進(jìn)行了性能測(cè)試。根據(jù)測(cè)試得出了各自測(cè)試中的最優(yōu)算法。

關(guān)鍵詞：模式匹配； 包分類(lèi)； 網(wǎng)絡(luò)處理器

中圖分類(lèi)號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)12-0310-03

隨著Internet的飛速發(fā)展，接入網(wǎng)絡(luò)系統(tǒng)的構(gòu)件數(shù)量不斷增多，對(duì)傳輸速度和服務(wù)質(zhì)量的需求也不斷提升。其中有三個(gè)關(guān)鍵問(wèn)題一直制約著網(wǎng)絡(luò)性能，即網(wǎng)絡(luò)連接速度、高速的路由交換和數(shù)據(jù)包轉(zhuǎn)發(fā)速率。數(shù)據(jù)包轉(zhuǎn)發(fā)已成為提高線速、解決串行數(shù)據(jù)流處理問(wèn)題的一個(gè)難點(diǎn)。提高數(shù)據(jù)包轉(zhuǎn)發(fā)速率的核心技術(shù)是包分類(lèi)技術(shù)。包分類(lèi)是按照指定的規(guī)則將數(shù)據(jù)包歸類(lèi)為不同的數(shù)據(jù)流，從而得到與數(shù)據(jù)流相對(duì)應(yīng)的處理規(guī)則。當(dāng)網(wǎng)絡(luò)數(shù)據(jù)包到達(dá)時(shí)，首先要對(duì)包進(jìn)行分類(lèi)，查詢到相應(yīng)的處理規(guī)則；然后完成相應(yīng)的處理；最后轉(zhuǎn)發(fā)。不難看出，包分類(lèi)技術(shù)中，采用何種規(guī)則或模式匹配算法是提高數(shù)據(jù)包轉(zhuǎn)發(fā)速率的關(guān)鍵。

通常，高效的模式匹配算法可以從時(shí)間復(fù)雜度、空間復(fù)雜度、更新復(fù)雜度、支持范圍匹配、擴(kuò)展性等幾個(gè)方面來(lái)評(píng)價(jià)查找算法的優(yōu)越性。對(duì)于模式匹配算法，期望時(shí)間復(fù)雜度、空間復(fù)雜度和更新復(fù)雜度越小越好。在許多情況下，分類(lèi)算法無(wú)法使全部性能達(dá)到最優(yōu)，而是應(yīng)該根據(jù)算法的使用場(chǎng)合加以折中。

1模式匹配算法

1．1概述

模式匹配算法就是在主串（text，T[0..n-1]）中搜索是否出現(xiàn)模式串（pattern，P={P₁[0..m1-1]..Pd[0..md-1]}）的一種算法。主串和模式串都屬于有限字符集σ，模式個(gè)數(shù)為d。模式匹配算法可以按多種方式進(jìn)行分類(lèi)。根據(jù)模式串的匹配方式可分為精確匹配、模糊匹配和范圍匹配。同時(shí)Pankaj Gupta等人從算法的角度給出了經(jīng)典的分類(lèi)方法^[1~3]。他們將模式匹配算法分為BS(basic structure algorithm，基本數(shù)據(jù)結(jié)構(gòu)算法)、GA(geometric algorithm，幾何算法)、HA(heuristics algorithm，啟發(fā)式算法)和HW(hardware－based algorithm，硬件算法)四類(lèi)。本文由于要對(duì)大多數(shù)常用的算法在性能上進(jìn)行比較，故考慮到可比性，將從可匹配的維數(shù)上對(duì)單模式匹配算法與多模式算法進(jìn)行分類(lèi)。

1．2單模式匹配算法

單模式匹配算法就是在一趟掃描主串的過(guò)程中只對(duì)一個(gè)模式串進(jìn)行匹配。由于它相對(duì)復(fù)雜度低、執(zhí)行效率高的優(yōu)點(diǎn)，再加之對(duì)它的研究也開(kāi)展得比較早，技術(shù)相對(duì)成熟，如經(jīng)典的KMP、BM算法以及后來(lái)對(duì)它們的改進(jìn)算法，在一些領(lǐng)域如流量計(jì)費(fèi)、搜索引擎、病毒特征碼匹配都有很好的應(yīng)用。根據(jù)文獻(xiàn)[4]對(duì)常用的單模式匹配算法進(jìn)行了分析，如表1所示。

由表1可以得出，常用的單模式匹配算法所采用的思想主要有五種，即基于字符比較（based－on character comparasion）、基于自動(dòng)機(jī)（based－on automaton）、基于hash查表（based－on hash searching）、基于位邏輯運(yùn)算（based－on bitwise）和基于Tries樹(shù)型機(jī)構(gòu)搜索（based－on Tries searching）。那么，究竟哪種算法有最好的執(zhí)行效率，可以絕對(duì)地由時(shí)間復(fù)雜度、空間復(fù)雜度最小來(lái)判斷嗎？這里時(shí)間復(fù)雜度與空間復(fù)雜度只是一個(gè)度量的范圍，表示受幾個(gè)參數(shù)影響，并不是一個(gè)具體值。

1．3多模式匹配算法

與單模式匹配算法相比，多模式匹配算法的優(yōu)勢(shì)在于一趟遍歷可以對(duì)多個(gè)模式進(jìn)行匹配。對(duì)于單模式匹配算法來(lái)說(shuō)，如果要匹配多個(gè)模式，那么有幾個(gè)模式就需要幾趟遍歷，這樣效率太低。多模式匹配算法的產(chǎn)生大大提高了多模式匹配的效率。當(dāng)然多模式匹配算法也適用于單模式的情況。表2給出了常用多模式匹配算法分析。

由圖2~4可以看出，各算法的測(cè)試指標(biāo)在規(guī)則長(zhǎng)度增長(zhǎng)的情況下均呈遞增趨勢(shì)，但也可以看出在規(guī)則快速增長(zhǎng)時(shí)BM算法的增長(zhǎng)較其他算法緩慢。同時(shí)在32位規(guī)則匹配上MRT算法比較有優(yōu)勢(shì)，它們的預(yù)處理時(shí)間也相對(duì)較快。因此可以得出在不太在意存儲(chǔ)器空間的情況下，BM算法是適合作為優(yōu)先考慮的算法。MRT算法適合對(duì)IP地址或MAC地址作快速的匹配。至于對(duì)IPv6地址，BM算法則比較適合。

對(duì)于多模式匹配算法的測(cè)試，將采用Snort v2．4．3系統(tǒng)的規(guī)則集。Snort是公認(rèn)的權(quán)威入侵檢測(cè)系統(tǒng)，把它的規(guī)則集用做測(cè)試多模式匹配算法有一定的普遍性。測(cè)試數(shù)據(jù)與單模式匹配測(cè)試一樣。參加測(cè)試的算法為AC－BM、Sun－Yanggon(SY)、Long－Karp－Rabin(LRK)和recursive flow classification(RFC)；測(cè)試項(xiàng)目為規(guī)則數(shù)與單位匹配時(shí)間、占用儲(chǔ)存單元單位數(shù)、單位預(yù)處理時(shí)間的變化關(guān)系。測(cè)試結(jié)果如圖5~7所示。

分析圖5~7可以得出，RFC在規(guī)則數(shù)遞增的情況下，匹配時(shí)間幾乎沒(méi)有什么增加。可見(jiàn)RFC算法對(duì)規(guī)則數(shù)不敏感，但其占用存儲(chǔ)單元空間太大、預(yù)處理時(shí)間過(guò)長(zhǎng)。如果在使用超大規(guī)模的規(guī)則集系統(tǒng)，同時(shí)存儲(chǔ)空間足夠的情況下可以考慮使用RFC算法。存儲(chǔ)空間比較有限的系統(tǒng)可以考慮使用LRK算法。它在低存儲(chǔ)空間占用的情況下匹配速度也可以接受。綜合三項(xiàng)測(cè)試得出最好的多模式匹配算法是AC－BM算法，它在三項(xiàng)測(cè)試中均有不錯(cuò)的表現(xiàn)。

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

本文利用NP對(duì)模式匹配算法進(jìn)行了詳細(xì)的測(cè)試和分析，從不同的角度分析了主流的單模式和多模式匹配算法并對(duì)算法給出了性能測(cè)試結(jié)果。由于網(wǎng)絡(luò)處理器本身是可編程的，使得它能非常方便地實(shí)現(xiàn)對(duì)各種算法的測(cè)試。為了在測(cè)試過(guò)程中保證各種算法在測(cè)試時(shí)有相應(yīng)的測(cè)試環(huán)境，還可利用網(wǎng)絡(luò)處理器本身的hash單元和可擴(kuò)展的TCAM單元。這樣的話對(duì)一些使用hash函數(shù)匹配的算法就會(huì)有更大的性能提升，而直接使用硬件TCAM算法會(huì)得到最好的性能；再加上網(wǎng)絡(luò)處理器的并行，多線程編程結(jié)構(gòu)可以根據(jù)情況組合多種算法以達(dá)到最優(yōu)的效果。因此在實(shí)際應(yīng)用時(shí)，可對(duì)具體算法加以必要的改進(jìn)和優(yōu)化。在同等的測(cè)試環(huán)境下，由測(cè)試結(jié)果可知，在單項(xiàng)測(cè)試中各算法各有優(yōu)劣。綜合考慮匹配時(shí)間、占用存儲(chǔ)空間以及預(yù)

處理時(shí)間的條件，單模式匹配算法中BM算法要優(yōu)于其他算法，多模式匹配算法中AC－BM算法是性能最好的。根據(jù)網(wǎng)絡(luò)系統(tǒng)的性能要求，選擇具有針對(duì)性的模式匹配算法是非常必要的。

參考文獻(xiàn)：

[1]GUPTA P， McKEOWN N. Algorithms for packet classification[D]. Stanford: Computer System Lab， Stanford University， 1999.

[2]GUPTA P， McKEOWN N. Packet classification on multiplefields[C]//Proc of ACM SIGCOMM’99. Cambridge:[s.n.]， 1999.

[3]GUPTA P， McKEWON N. Packet classification using hierarchical intelligent cuttings[J]. IEEE Micro， 2000，20(1):34-41.

[4]CHARRAS C， LECROQ T. Handbook of exact string－matching algorithms[K]. London: King’s Colledge London Publications， 2004.

[5]CROCHEMORE M， RYTTER W. Text alogrithms[M]. Oxford: Oxford University Press， 1994.

[6]BAEZA－YATES R A， GONNET G H. A new approach to text sear－ching[J]. Communication of ACM， 1992，35(10):74-82.

[7]BOYER R S， MOORE J S. A fast string searching algorithm[J]. Communication of ACM， 1977，20(10):762-772.

[8]CROCHEMORE M. Off－line serial exact string searching in pattern matching algorithms[M]. Oxford: Oxford University Press， 1997:1-53.

[9]石晶林，程勝，孫江明.網(wǎng)絡(luò)處理器原理、設(shè)計(jì)與應(yīng)用[M].北京:清華大學(xué)出版社，2003.

[10]COMER D E. Network systems design using network processors[M].北京:機(jī)械工業(yè)出版社，2004.

[11]KIM S， KIM Y. A fast multiple string－pattern matching algorithm[C]//Proc of the 17th AoM/IAoM Inernational Conference on Computer Science. San Diego:[s.n.]， 1999.

[12]WU S， MANBER U. A fast algorithm for multi－pattern searching， TR94_17[R]. Tuscon: University of Arizona， 1994.

[13]Intel Corporation. Intel exchange architecture(IXA) programmer’s reference manual[K/CD]. 2004.

[14]Intel Corporation. Intel exchange architecture(IXA) hardware refe－rence manual[K/CD]. 2004.

[15]胡越明. Intel網(wǎng)絡(luò)處理器及其應(yīng)用開(kāi)發(fā)[M].北京:清華大學(xué)出版社，2005.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”