一种基于哈希表和扩展存储器的高性能IPv6地址查找方法

摘要

一种基于哈希表查找和扩展存储器查找的IPv6地址查找方案，包括1个查找分类器，1个更新分类器，7个并行的哈希处理单元，6个扩展存储器处理单元、7个哈希冲突处理单元和1个优先级比较单元。前6个哈希处理单元与对应的扩展存储器进行两级关联，并和对应的哈希冲突处理单元分别构成6路处理模块，第7个哈希处理单元和其对应的哈希冲突处理单元构成1路处理模块，7路模块并行对IPv6地址进行查找以确定其下一跳信息。本发明根据IPv6地址前缀的分布规律，结合哈希查找和扩展存储器查找的原理，使IPv6地址在1-2个存储周期可以完成查找操作。本发明查找和更新性能高、可扩展性强，是一种适合高性能IPv6路由器的查找方案。

主权项

一种基于哈希表查找和扩展存储器查找的IPv6地址查找方法，实现该方法使用1个查找分类器；1个更新分类器；7个并行的哈希处理单元Hash16、Hash24、Hash32、Hash40、Hash48、Hash56、Hash64，其分别存放长度为16、24、32、40、48、56、64比特哈希前缀项的哈希表；6个扩展存储器RAM17_23、RAM25_31、RAM33_39、RAM41_47、RAM49_55、RAM57_63，其存放扩展前缀项所对应的下一跳值，其中扩展前缀为两个长度能被8整除哈希前缀项之间的所有前缀；7个哈希冲突处理单元CPE16_23、CPE24_31、CPE32_39、CPE40_47、CPE48_55、CPE56_63、CPE64；1个优先级比较单元；其特征在于对IPv6地址进行查找，并对IPv6路由表项进行更新，具体步骤为：a.根据IPv6路由表分布规律的统计，将路由表项分为两种：一种是长度可以被8整除的前缀，一种是长度不能被8整除的前缀；b.对两种路由表项分别用哈希表和扩展存储器进行存储，具体是将长度可以被8整除的路由前缀用哈希表进行存储，将长度不能被8整除的路由前缀用哈希表和扩展存储器做两级存储；使用哈希冲突处理单元处理哈希冲突项；c.优先级比较器选择出最长匹配前缀所对应的下一跳信息；d.由哈希处理单元Hash16、Hash24、Hash32、Hash40、Hash48、Hash56与对应的扩展存储器RAM17_23、RAM25_31、RAM33_39、RAM41_47、RAM49_55、RAM57_63进行两级关联，并和对应的哈希冲突处理单元CPE16_23、CPE24_31、CPE32_39、CPE40_47、CPE48_55、CPE56_63分别构成6路处理模块，第7个哈希处理单元hash64和其对应的哈希冲突处理单元CPE64构成1路处理模块，在查找过程中，7路处理模块并行对目的IPv6地址进行查找以确定其匹配前缀项，在7路处理模块查找出的全部匹配前缀中，通过优先级比较器进行比较以实现最长前缀匹配，最长匹配前缀所对应的下一跳信息为查找结果；e.在更新过程中，通过哈希计算和扩展存储器地址计算进行路由表项更新， 包括路由表初始化、插入表项、删除表项和修改表项，具体步骤为：路由表初始化及表项插入过程为：①通过需要更新的路由表项确定需要更新表项的位置：先判断需要更新路由前缀的长度是否可以被8整除；②如果可以被8整除，通过更新分类器选择出d步骤所描述7个处理模块中所对应的处理模块，将此前缀进行哈希计算，用所得哈希值索引哈希表，如果索引到的哈希表项已经放入其它路由信息，则将该前缀所对应的路由信息放入哈希冲突处理单元中进行处理，如果索引到的哈希表项是空项，则将对应的路由信息放入该项中；③如果前缀长度不可以被8整除，通过更新分类器选择出对应的处理模块，先将该前缀的扩展前缀哈希项做哈希计算，用所得哈希值索引哈希表，若该表项为空，则将所分配的扩展存储器单元的首地址存入该表项，然后将所对应的路由信息放入所分配的扩展存储器单元的对应位置，若该表项不为空且该前缀的扩展前缀哈希项不同于已插入前缀的扩展前缀哈希项，则将该前缀所对应的路由信息插入到已分配的扩展存储器单元中，如该表项不为空且该前缀的扩展前缀哈希项和已插入前缀的扩展前缀哈希项相同，则将该前缀放入哈希冲突处理单元中进行处理。表项删除及修改过程为：①通过更新分类器选择出对应的处理模块；②利用查找方法，查找到待更新的路由表项，然后将该表项的路由信息进行删除或者修改。