網絡處理模式匹配算法研究

摘要：主要從多個角度研究了經典的15種單模式和7種多模式匹配算法，并以可編程網絡處理器為測試平臺對其中的5種單模式和4種多模式匹配算法分別在匹配時間、占用存儲空間以及預處理時間方面進行了性能測試。根據測試得出了各自測試中的最優算法。

關鍵詞：模式匹配； 包分類； 網絡處理器

中圖分類號：TP393文獻標志碼：A

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

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

通常，高效的模式匹配算法可以從時間復雜度、空間復雜度、更新復雜度、支持范圍匹配、擴展性等幾個方面來評價查找算法的優越性。對于模式匹配算法，期望時間復雜度、空間復雜度和更新復雜度越小越好。在許多情況下，分類算法無法使全部性能達到最優，而是應該根據算法的使用場合加以折中。

1模式匹配算法

1．1概述

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

1．2單模式匹配算法

單模式匹配算法就是在一趟掃描主串的過程中只對一個模式串進行匹配。由于它相對復雜度低、執行效率高的優點，再加之對它的研究也開展得比較早，技術相對成熟，如經典的KMP、BM算法以及后來對它們的改進算法，在一些領域如流量計費、搜索引擎、病毒特征碼匹配都有很好的應用。根據文獻[4]對常用的單模式匹配算法進行了分析，如表1所示。

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

1．3多模式匹配算法

與單模式匹配算法相比，多模式匹配算法的優勢在于一趟遍歷可以對多個模式進行匹配。對于單模式匹配算法來說，如果要匹配多個模式，那么有幾個模式就需要幾趟遍歷，這樣效率太低。多模式匹配算法的產生大大提高了多模式匹配的效率。當然多模式匹配算法也適用于單模式的情況。表2給出了常用多模式匹配算法分析。

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

對于多模式匹配算法的測試，將采用Snort v2．4．3系統的規則集。Snort是公認的權威入侵檢測系統，把它的規則集用做測試多模式匹配算法有一定的普遍性。測試數據與單模式匹配測試一樣。參加測試的算法為AC－BM、Sun－Yanggon(SY)、Long－Karp－Rabin(LRK)和recursive flow classification(RFC)；測試項目為規則數與單位匹配時間、占用儲存單元單位數、單位預處理時間的變化關系。測試結果如圖5~7所示。

分析圖5~7可以得出，RFC在規則數遞增的情況下，匹配時間幾乎沒有什么增加。可見RFC算法對規則數不敏感，但其占用存儲單元空間太大、預處理時間過長。如果在使用超大規模的規則集系統，同時存儲空間足夠的情況下可以考慮使用RFC算法。存儲空間比較有限的系統可以考慮使用LRK算法。它在低存儲空間占用的情況下匹配速度也可以接受。綜合三項測試得出最好的多模式匹配算法是AC－BM算法，它在三項測試中均有不錯的表現。

3結束語

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

處理時間的條件，單模式匹配算法中BM算法要優于其他算法，多模式匹配算法中AC－BM算法是性能最好的。根據網絡系統的性能要求，選擇具有針對性的模式匹配算法是非常必要的。

參考文獻：

[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]石晶林，程勝，孫江明.網絡處理器原理、設計與應用[M].北京:清華大學出版社，2003.

[10]COMER D E. Network systems design using network processors[M].北京:機械工業出版社，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網絡處理器及其應用開發[M].北京:清華大學出版社，2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”