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

無效

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

1、一種快速查找定位和匹配訪問控制列表的方法，其特征在于，包括如下步驟：

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

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

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

2、根據權利要求1所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，所述的hash_table表桶大小prime要滿足關系式且為素數。

3、根據權利要求1所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，所述的prime值為：ACL規則表項大小所對應的數字區間中的素數值。

4、根據權利要求2或3所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，所述的函數計算具體為：累加輸入關鍵字符串key中每個字符對應的ascall碼和每個字符在字符串中的相對位置的乘積項，對上述累加和對prime值進行取模。

5、根據權利要求1所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，每一個hash_table表項為一個結構體，包括一個hash_table型單向鏈表指針list、一個布爾型標識位status和一個字符型關鍵描述字符串指針descrip。

6、根據權利要求1所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，給hash表維護一個鏈表，保存所有沖突的表項。

7、權利要求6所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，還包括如下步驟：由hash_table[index]所指向的結構體中整型標識位status的狀態，判斷當前ACL規則是否存在。

8、根據權利要求7所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，還包括如下步驟：當status為FALSE表明現存的ACL中沒有重復規則即當前配置ACL規則有效，同時將status置TRUE，生成的ACL規則字符串序列或能唯一確定此ACL規則關鍵字記錄到descrip中，標識返回結果為未匹配到相同的ACL規則然后直接結束。

9、根據權利要求8所述的快速查找定位和匹配訪問控制列表的方法，其特征在于，還包括如下步驟：當status為TRUE時表明現存的ACL中可能存在有當前所配置的ACL規則，需進一步判斷，這時通過list單向鏈表逐一比較hash_table桶中descrip字符串序列或者通過前面所述的傳統ACL規則匹配比較方法進行比較，如果匹配到相同的ACL規則，則標識返回結果為匹配到相同的ACL規則然后結束；否則如果未匹配到，則將當前ACL規則按照hash_table結構構造好后添加到list單向鏈表末尾并標識返回結果為未匹配到相同的ACL規則后結束。