[發明專利]一種快速查找定位和匹配訪問控制列表的方法

無效

• 申請號: 200710043670.1
• 申請日: 2007-07-11
• 公開（公告）號: CN101345694A
• 公開（公告）日: 2009-01-14
• 發明（設計）人: 李杰;高守瑋
• 申請（專利權）人: 上海未來寬帶技術及應用工程研究中心有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;G06F17/30
• 代理公司: 上海光華專利事務所
• 代理人: 余明偉

技術領域

本發明提供一種快速查找定位和匹配訪問控制列表的方法，屬于計算機通訊技術領域。

背景技術

利用報文的一些特定域組成的規則(Rule)，將報文區分成不同的流。比如我們可以將來自某一個網絡的報文(源IP地址)、并去往某一網絡的報文(以目的IP地址來標識)劃分成一個流。分成流之后，可以針對流進行處理，比如提高優先級，保證帶寬，限制帶寬，丟棄等，這種處理稱為動作。通常將一個規則加上對應動作稱為一個訪問控制列表(ACL：Access?Control?List，下面統稱為ACL)。

一般業界標準的組成規則的域有5個，通常也稱5元組，這5個域是：IP報文的源地址、IP報文的目的地址、IP報文的承載協議類型、TCP(或UDP)的源端口號、TCP(或UDP)的目的端口號。在具體實現中，使用的域還有許多擴展：COS、TOS、DSCP、虛擬局域網索引(VLANID)、分段標記、TCP同步標記、源和目的MAC地址等，以上各個域可以任意組合，并且可以有范圍，比如一個規則可以是：TCP端口1000～2000+IP地址1.1.1.*(*代表不關心的位)。

目前數通領域的許多接入層設備以及核心設備，由于安全性、服務質量和帶寬保證的需要，往往通過配置大量的ACL規則來實現業務要求。面對如此多的ACL規則，如何高效地進行查找定位、添加和刪除操作以及對ACL規則的比較和匹配操作，都是影響這些設備性能的重要因素。

ACL規則組在實際使用中，人們更希望使用一些有意義的字符串助記符來表示，而代替以往使用數字表示的方式。這樣就帶來了一些問題，給ACL規則組的查找定位、添加和刪除操作增加了工作量。以往對于基于數字表示的ACL，通常采用指針數組的方式來索引各個數值所對應的ACL規則組，但對于基于名字方式表示的ACL，目前通常采用循環比對名字字符串的方式來實現ACL規則組的查找定位、添加和刪除操作。這樣要長時間占用CPU和內存資源，顯然效率是非常低下的，勢必要影響設備的使用性能。

另外在配置ACL規則時，通常需要進行ACL規則的有效性和是否重復性的比較檢查，然而組成ACL規則的域除了業界標準的5元組還有許多擴展的域，并且以上各個域可以任意組合，某些值域還可以表示為一個范圍。通常ACL規則的匹配和比較都是每個域進行逐一比較匹配的，這樣對于對性能要求比較高的設備，這種方法顯然是不能滿足需求的。目前實現的快速ACL規則的匹配和比較方法，主要是通過構建一個基于源和目的ip地址和地址掩碼的二叉樹，然后通過對這個二叉樹進行搜索遍歷操作來提高ACL規則組的匹配效率。然而這種方法并不能很好地支持ACL規則中其他擴展域的快速匹配，并且構建這個二叉樹也需要不少時間。

發明內容

本發明所要解決的技術問題是提供一種實現快速查找定位和匹配訪問控制列表的方法，以通過對一個訪問控制列表的名字字符串的hash函數映射來實現快速查找定位。

為了解決上述技術問題，本發明采用了下述技術方案：

本發明的一種快速查找定位和匹配訪問控制列表的方法，包括如下步驟：

步驟1、將要配置的ACL規則的所有匹配域信息字符串序列化，初始化hash_table[MAX_LEN]表；

步驟2、將ACL規則字符串序列作為hash函數的鍵值key，將相應字符串key和hash桶大小值prime帶入函數計算，得到此hash的函數散列值index；

步驟3、根據計算結果index來索引本ACL規則在hash_table表中對應表項。

進一步地，所述的hash_table表桶大小prime要滿足關系式且為素數。

進一步地，所述的prime值為：ACL規則表項大小所對應的數字區間中的素數值。

進一步地，所述的函數計算具體為：累加輸入關鍵字符串key中每個字符對應的ascall碼和每個字符在字符串中的相對位置的乘積項，對上述累加和對prime值進行取模。

進一步地，還包括步驟：給hash表維護一個鏈表，保存所有沖突的表項。

本專利中的hash算法實現簡單，效率較高，hash分布性比較好，另外通過給HASH表維護一個鏈表，保存所有沖突的表項的方法可以很好的平衡實際應用中空間和時間的矛盾問題，在不必浪費巨大空間的情況下很好地提高系統效率。但對于hash分布要求更高的情況可以參考Jenkins?hash等其他hash算法，但缺點是相比本hash算法更耗時。