基于Hash和CAM的IPv6路由查找算法  

IPv6 Routing Lookup Algorithm Based on Hash and CAM

作　　者：王瑞青[1] 杜慧敏[2] 王亚刚[1] 

机构地区：[1]西安邮电学院计算机学院,西安710061 [2]西安邮电学院电子工程学院,西安710061

出　　处：《计算机工程》2012年第8期50-53,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60976020)

摘　　要：分析实际网络中的IPv6前缀分布规律与增长趋势,提出一种基于Hash和内容可寻址存储器(CAM)的IPv6路由查找算法。将长度能被8整除的前缀存储在8个Hash表中,发生Hash冲突的前缀存储在CAM中,长度不能被8整除的前缀按照一定的组织方式存储在随机存取存储器中。分析结果表明,该算法具有较高的存储利用率、查找速率及更新速率,并且易于扩展和硬件实现。This paper presents an IPv6 lookup algorithm based on Hash and Content Addressable Memory（CAM） by analyzing the prefix length distribution of routing table and the growth trend of routing table entries. The prefixes whose length can be divided by 8 are stored in 8 Hash tables, and the remaining prefixes are stored into expanded Random Access Memory（RAM）, Analysis result shows that the algorithm has high efficient storage utilization, searching rate and updating rate. It is easy to be scalded in hardware.

关 键 词：IPV6路由查找 哈希压缩 两级查找 流水线 内容可寻址存储器 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]