一种访问控制列表实现方法及装置

摘要

本发明公开了一种成本和功耗低的访问控制列表实现装置，包括访问控制列表生成模块、存储器、访问控制列表查找模块和多维规则处理模块。访问控制列表生成模块用于，分别对各个规则区间左端点的高M比特部分进行哈希运算，将运算结果相同的端点作为叶子节点组成同一个树形数据结构，得到若干树形数据结构并存储在存储器中；访问控制列表查找模块用于，提取待查找数据包的关键字，对高M比特部分进行哈希运算，找到对应的树形数据结构进行查找，获取对应的规则，其中，0＜M＜N，N为规则的宽度；多维规则处理模块用于，将多维规则分解为多个一维规则，分别查找其规则，然后将多个一维规则进行合并。本发明还相应公开了一种访问控制列表实现方法。

主权项

一种访问控制列表实现装置,其特征在于，包括访问控制列表生成模块、存储器和访问控制列表查找模块:其中，所述访问控制列表生成模块用于，将同一维的各规则区间映射到一个数轴上，分别得到各规则区间在该数轴上的端点，并以各个规则对应的区间的端点为叶子节点，建立起树形数据结构，所述端点指左端点和右端点之一；所述存储器用于存储所述树形数据结构；所述访问控制列表查找模块用于，提取待查找数据包的关键字，以之查找所述树形数据结构，获取所述待查找数据包对应的规则；其中，所述以各个规则对应的区间的端点为叶子节点，建立起树形数据结构，是指分别对各个叶子节点的高M比特部分进行哈希运算，将运算结果相同的叶子节点组成一个树形数据结构，从而得到一个以上的树形数据结构；所述提取待查找数据包的关键字，以之查找所述树形数据结构，是指对所述关键字的高M比特部分进行哈希运算，根据运算结果找到对应的树形数据结构进行查找；0<M<N，N为规则的宽度。