[發明專利]一種基于模糊匹配的快速查表方法

在審

• 申請號: 201410335259.1
• 申請日: 2014-07-15
• 公開（公告）號: CN104092613A
• 公開（公告）日: 2014-10-08
• 發明（設計）人: 畢研山;楊浩民;姜凱;曹剛
• 申請（專利權）人: 山東超越數控電子有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 姜明

技術領域

本發明涉及一種查表方法，特別涉及一種基于模糊匹配的快速查表方法。

背景技術

在網絡交換設備中，報文的轉發、根據策略執行對應操作都是通過查表實現的。對三層交換架構來說，現有的查表方法是五元組哈希查表法，具體方法是提取出IP報文的五元組（SIP/DIP/PROTOCOL/SPORT/DPORT），做hash（哈希）運算，將hash運算的結果作為存放轉發策略的表項地址。這種查表法速度較快，能夠滿足線速轉發的要求，因而在交換設備中大量使用。但此查表法的缺陷是只能實現精確匹配。在模糊匹配的情況下，需要有一種新的匹配算法來實現高速的查表功能。

發明內容

為了解決現有技術的問題，本發明提供了一種基于模糊匹配的快速查表方法，其能夠滿足模糊匹配的快速查表需求。

本發明所采用的技術方案如下：

一種基于模糊匹配的快速查表方法，包括以下步驟：

A、首先確定表項中各關鍵字段的首特征值及尾特征值；

B、由首尾特征值的共同部分字段作為模糊匹配表項基地址，模糊匹配范圍作為偏移地址，基地址與偏移地址共同組成表項地址，存放表項內容；

C、執行查表操作，根據匹配范圍確定表項基地址，在基地址基礎上計算報文映射地址，如果映射地址在表項地址范圍內，說明查找成功。

查表條件為從A到B之間的范圍時，將條件A與條件B的共同部分字段作為表項基地址，條件A與條件B存在差異的字段的范圍作為表項偏移地址，基地址+偏移地址表征了表項內容存放的物理地址。

查表操作時，根據差異字段的長度范圍，對接收的報文進行數據切割，分為共同特征段和關鍵字段；將切割后的共同特征段與表項中的共同特征段進行比較，如果相同，則繼續比較關鍵字段，將待匹配關鍵字與首特征關鍵字相減，如果結果在匹配長度范圍內，則表項命中。

本發明提供的技術方案帶來的有益效果是：

本發明的一種基于模糊匹配的快速查表方法，其能夠滿足模糊匹配的快速查表需求。

附圖說明

為了更清楚地說明本發明實施例中的技術方案，下面將對實施例描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。

圖1為本發明的一種基于模糊匹配的快速查表方法的工作原理圖。

具體實施方式

為使本發明的目的、技術方案和優點更加清楚，下面將結合附圖對本發明實施方式作進一步地詳細描述。

本發明的一種基于模糊匹配的快速查表方法，一般包括以下步驟：

A、首先確定表項中各關鍵字段的首特征值及尾特征值；

B、由首尾特征值的共同部分字段作為模糊匹配表項基地址，模糊匹配范圍作為偏移地址，基地址與偏移地址共同組成表項地址，存放表項內容；

C、執行查表操作，根據匹配范圍確定表項基地址，在基地址基礎上計算報文映射地址，如果映射地址在表項地址范圍內，說明查找成功。

如附圖1所示，虛線上方是存放在模糊匹配表項中的匹配條件，下發是待匹配報文，接收到待匹配報文后，首先根據匹配長度信息對報文進行切割，分為共同特征段和關鍵字段，其次將切割后的共同特征段與表項中的共同特征段進行比較，如果相同，則繼續比較關鍵字段，將待匹配關鍵字與首特征關鍵字相減，如果結果在匹配長度范圍內，則表項命中。

以上所述僅為本發明的較佳實施例，并不用以限制本發明，凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護范圍之內。