[發明專利]基于現場可編程門陣列的高速模式匹配算法

有效

• 申請號: 200810241135.1
• 申請日: 2008-12-30
• 公開（公告）號: CN101442540A
• 公開（公告）日: 2009-05-27
• 發明（設計）人: 劉曉燕;王霖
• 申請（專利權）人: 北京暢訊信通科技有限公司
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06F17/30
• 代理公司: 北京中海智圣知識產權代理有限公司
• 代理人: 曾永珠;胡 靜

1.一種基于現場可編程門陣列的高速模式匹配方法，其特征在于，包括如下步驟：

步驟1：依據動態擴充AC算法中跳轉函數goto方法及對規則庫壓縮方法將輸入的模式 匹配規則集合文件編譯為符合FPGA讀寫規律的二進制規則庫文件；其中，所述動態擴充AC 算法中跳轉函數goto方法包括：首先構造一個初始的goto函數，再根據這個初始的goto函 數構造failure函數，在構造failure函數過程中根據多模式匹配的AC算法來動態地擴充goto 函數來構造出完整地goto函數和failure函數；

所述多模式匹配的AC算法根據所有的輸入模式構造一個狀態表，當狀態表是一個嚴格 單向的狀態表時，完整的goto函數就是該方法得到的最終結果；否則，構造failure函數，在 AC算法上采用窮舉的方式查找回溯過程，從階數1開始找起，直到遍歷所有狀態；其中，所 述回溯過程為在非確定性有限狀態機NFA中failure函數的一個狀態回指的過程，表明了從狀 態0到該狀態的路徑上的字符串包含了從狀態0到其他狀態的字符串；

所述規則庫壓縮方法包括：將可能發生非0狀態的最小和最大字符之間的狀態變化信息 保存；

步驟2：將編譯好的二進制規則庫文件加載到FPGA的四倍速數據速率靜態隨機存儲器 QDR?SRAM，該規則庫包括狀態跳轉表和狀態信息表兩部分；

步驟3：系統初始化后開始接收數據包，當前系統狀態號初始化為0；

步驟4：判斷接收到的新的數據包是否需要匹配；若需要匹配，則轉至步驟5)；否則， 則轉至步驟16)；

步驟5：取出0狀態的狀態信息，包括最大及最小有效字符、是否命中的標志位、狀態 跳轉表的位置基地址，放入當前狀態信息中；

步驟6：取一個需要匹配的字符；

步驟7：根據當前狀態信息的內容判斷取的字符是否在最小字符和最大字符之間；若是， 則轉至步驟8)；否則，轉至所述步驟6)取下一個需要匹配的字符；

步驟8：根據當前狀態信息中的狀態跳轉表的位置基地址和字符計算該字符對應的狀態 跳轉表的地址；

步驟9：根據所述步驟8得到的狀態跳轉表的地址，取出下一狀態號作為新的當前狀態 號；

步驟10：根據取到的狀態號來計算存放當前狀態信息項的狀態信息表的地址；

步驟11：根據所述步驟10得到的狀態信息表的地址，取出相應的狀態信息放入當前狀 態信息中；

步驟12：根據得到的狀態信息判斷輸入的字符是否匹配；若是，則轉至步驟13)；否則， 則轉至步驟14)；

步驟13：記錄匹配的結果；

步驟14：判斷收到的數據包是否全部完成匹配；若是，則轉至步驟15)；否則，則轉至 所述步驟6)取下一個需要匹配的字符；

步驟15：當整個數據包匹配結束后，把匹配結果與原始的數據包重新組合成新的數據包；

步驟16：把數據包轉發出去，然后初始化當前的狀態號為0，開始新的數據包匹配。

2.根據權利要求1所述的基于現場可編程門陣列的高速模式匹配方法，其特征在于，所 述步驟8的根據當前狀態信息中的狀態跳轉表的位置基地址和字符計算該字符對應的狀態跳 轉表地址的方法為：

狀態跳轉表地址＝狀態跳轉表的位置基地址+(最大字符-最小字符)×一個狀態跳 轉條目占用的字節數。

3.根據權利要求1所述的基于現場可編程門陣列的高速模式匹配方法，其特征在于，所 述步驟10的根據取到的狀態號來計算存放當前狀態信息項的狀態信息表的地址的方法為：

存放當前狀態信息項的狀態信息表的地址＝狀態信息表基地址+當前狀態號×每個 狀態信息條目占用的字節數。