一种快速查找IPV6路由的系统及方法

摘要

本发明涉及一种快速查找IPV6路由的系统及方法，包括一个路由存储表，所述路由存储表包括一个一级线性索引表和一个以上的存储模块；所述一级线性索引表用于存储一个以上的索引值，每个索引值对应一个存储模块；其中，每个索引值为一个路由前缀的第4-16比特的值；所述存储模块用于存储17比特之后的路由前缀；所述方法根据IPV6路由前缀的层次关系和IPV6路由前缀长度的分布规律将17比特之后的路由前缀添加到相应存储模块中；本发明提供了一个一级的线性索引，提高了路由查找的效率；根据路由前缀长度的分布规律和前缀层次关系选择无冲突哈希表和多比特树，减少了比较次数，且该方法的稳定性较好。

主权项

一种快速查找IPV6路由的系统，其特征在于，包括一个路由存储表，所述路由存储表包括一个一级线性索引表和一个以上的存储模块；所述一级线性索引表用于存储一个以上的索引值，每个索引值对应一个存储模块；其中，每个索引值为一个路由前缀的第4‑16比特的值；所述存储模块用于存储17比特之后的路由前缀；所述一级线性索引表为一个数组，数组里存储指针，所述指针指向存储模块；所述存储模块包括一个或一个以上的存储单元，存储单元包括一个单独的多比特树或一个以上的无冲突哈希表，每个无冲突哈希表附带若干个多比特树；所述每个无冲突哈希表包括一个一级哈希表和若干个二级哈希表；一级哈希表包含若干个表项，每个表项包含三个单元，第一单元存储二级哈希表可存储元素个数m，第二单元存储调节参数a的值，第三单元存储指向二级哈希表的数组指针p；二级哈希表包含若干个存储单元，用于存储路由前缀；一级哈希表的每个表项的数组指针p指向的二级哈希表的长度为2m。