有界索引可扩展的基于散列的IPv6地址查找方法

摘要

本发明提供了一种用于在诸如路由器这样的中间网络节点中高效查找地址路由信息的技术。为此，节点利用可用小的有界数目的从属查找来搜索的一个或多个“查找”表(LUT)来定位存储在其存储器中的路由信息，从而减小了传统执行的从属查找的数目。LUT被安排为使得每个表为子网掩码长度在不同的掩码长度范围(“步幅”)内的网络地址提供路由信息。根据该技术，节点通过按前缀长度减小的顺序搜索LUT，直到找到路由信息，来定位网络地址的路由信息。优选地，几个表被并行搜索。LUT中的匹配还可指向小的MTRIE，该MTRIE使得前缀中的最终比特能够被匹配。该最终MTRIE被用相对较小的有界数目的从属查找来搜索。