[發(fā)明專利]一種訪問控制列表實(shí)現(xiàn)方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201010567890.6
• 申請(qǐng)日: 2010-12-01
• 公開（公告）號(hào): CN102487374A
• 公開（公告）日: 2012-06-06
• 發(fā)明（設(shè)計(jì)）人: 陳欽樹
• 申請(qǐng)（專利權(quán)）人: 中興通訊股份有限公司
• 主分類號(hào): H04L29/06
• 分類號(hào): H04L29/06;H04L12/56;G06F17/30
• 代理公司: 工業(yè)和信息化部電子專利中心 11010
• 代理人: 肖偉先

1.一種訪問控制列表實(shí)現(xiàn)裝置，其特征在于，包括訪問控制列表生成模塊、存儲(chǔ)器和訪問控制列表查找模塊：

其中，所述訪問控制列表生成模塊用于，將同一維的各規(guī)則區(qū)間映射到一個(gè)數(shù)軸上，分別得到各規(guī)則區(qū)間在該數(shù)軸上的端點(diǎn)，并以所述以各個(gè)規(guī)則對(duì)應(yīng)的區(qū)間的端點(diǎn)為葉子節(jié)點(diǎn)，建立起樹形數(shù)據(jù)結(jié)構(gòu)，所述端點(diǎn)指左端點(diǎn)和右端點(diǎn)之一；

所述存儲(chǔ)器用于存儲(chǔ)所述樹形數(shù)據(jù)結(jié)構(gòu)；

所述訪問控制列表查找模塊用于，提取待查找數(shù)據(jù)包的關(guān)鍵字，以之查找所述樹形數(shù)據(jù)結(jié)構(gòu)，獲取所述待查找數(shù)據(jù)包對(duì)應(yīng)的規(guī)則。

2.根據(jù)權(quán)利要求1所述的訪問控制列表實(shí)現(xiàn)裝置，其特征在于，所述樹形數(shù)據(jù)結(jié)構(gòu)指2-3樹結(jié)構(gòu)。

3.根據(jù)權(quán)利要求1所述的訪問控制列表實(shí)現(xiàn)裝置，其特征在于，所述樹形數(shù)據(jù)結(jié)構(gòu)指二叉樹結(jié)構(gòu)。

4.根據(jù)權(quán)利要求1所述的訪問控制列表實(shí)現(xiàn)裝置，其特征在于，所述訪問控制列表生成模塊還用于，為所述樹形數(shù)據(jù)結(jié)構(gòu)建立備份，并將其保存于所述存儲(chǔ)器中。

5.根據(jù)權(quán)利要求1所述的訪問控制列表實(shí)現(xiàn)裝置，其特征在于：

所述以各個(gè)規(guī)則對(duì)應(yīng)的區(qū)間的端點(diǎn)為葉子節(jié)點(diǎn)，建立起樹形數(shù)據(jù)結(jié)構(gòu)，是指分別對(duì)各個(gè)葉子節(jié)點(diǎn)的高M(jìn)比特部分進(jìn)行哈希運(yùn)算，將運(yùn)算結(jié)果相同的葉子節(jié)點(diǎn)組成一個(gè)樹形數(shù)據(jù)結(jié)構(gòu)，從而得到一個(gè)以上的樹形數(shù)據(jù)結(jié)構(gòu)；

所述提取待查找數(shù)據(jù)包的關(guān)鍵字，以之查找所述樹形數(shù)據(jù)結(jié)構(gòu)，是指對(duì)所述關(guān)鍵字的高M(jìn)比特部分進(jìn)行哈希運(yùn)算，根據(jù)運(yùn)算結(jié)果找到對(duì)應(yīng)的樹形數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找；

0＜M＜N，N為規(guī)則的寬度。

6.根據(jù)權(quán)利要求5所述的訪問控制列表實(shí)現(xiàn)裝置，其特征在于，0＜M＜N/3。

7.根據(jù)權(quán)利要求1至6中任一項(xiàng)所述的訪問控制列表實(shí)現(xiàn)裝置，其特征在于，還包括多維規(guī)則處理模塊；

所述多維規(guī)則處理模塊用于，如果所述待查找數(shù)據(jù)包的規(guī)則為多維，則首先將其規(guī)則分解為多個(gè)一維規(guī)則，對(duì)于其中任一個(gè)一維規(guī)則，交由所述訪問控制列表生成模塊和訪問控制列表查找模塊執(zhí)行，然后將得到的所述待查找數(shù)據(jù)包對(duì)應(yīng)的該一維規(guī)則進(jìn)行規(guī)則合并，得到所述待查找數(shù)據(jù)包對(duì)應(yīng)的多維規(guī)則；多維指二維及二維以上。

8.一種訪問控制列表實(shí)現(xiàn)方法，其特征在于，包括如下步驟：

A、將同一維的各規(guī)則區(qū)間映射到一個(gè)數(shù)軸上，分別得到各規(guī)則區(qū)間在該數(shù)軸上的端點(diǎn)，并以各個(gè)規(guī)則對(duì)應(yīng)的區(qū)間的端點(diǎn)為葉子節(jié)點(diǎn)，建立樹形數(shù)據(jù)結(jié)構(gòu)，并保存所述樹形數(shù)據(jù)結(jié)構(gòu)；

B、提取待查找數(shù)據(jù)包的關(guān)鍵字，以之查找所述樹形數(shù)據(jù)結(jié)構(gòu)，獲取所述待查找數(shù)據(jù)包對(duì)應(yīng)的規(guī)則；

所述端點(diǎn)指左端點(diǎn)和右端點(diǎn)之一。

9.根據(jù)權(quán)利要求8所述的訪問控制列表實(shí)現(xiàn)方法，其特征在于，在步驟A中，分別對(duì)各個(gè)葉子節(jié)點(diǎn)的高M(jìn)比特部分進(jìn)行哈希運(yùn)算，將運(yùn)算結(jié)果相同的葉子節(jié)點(diǎn)組成一個(gè)樹形數(shù)據(jù)結(jié)構(gòu)，從而得到一個(gè)以上的樹形數(shù)據(jù)結(jié)構(gòu)；步驟B中，對(duì)所述關(guān)鍵字的高M(jìn)比特部分進(jìn)行哈希運(yùn)算，根據(jù)運(yùn)算結(jié)果找到對(duì)應(yīng)的樹形數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找；0＜M＜N，N為規(guī)則的寬度。

10.根據(jù)權(quán)利要求8或9所述的訪問控制列表實(shí)現(xiàn)方法，其特征在于，如果所述待查找數(shù)據(jù)包的規(guī)則為多維，則首先將其規(guī)則分解為多個(gè)一維規(guī)則，對(duì)于其中任一個(gè)一維規(guī)則，執(zhí)行所述步驟A和步驟B，得到所述待查找數(shù)據(jù)包對(duì)應(yīng)的該一維規(guī)則，然后進(jìn)行規(guī)則合并，得到所述待查找數(shù)據(jù)包對(duì)應(yīng)的多維規(guī)則；多維指二維及二維以上。