随着物理链路速度的增长和路由表规模的不断增大,作为路由器的一项核心技术,IP地址查找面临着巨大的性能挑战。首先,IP地址查找必须能够响应越来越多的查询请求,这些请求的数量往往超过了几百万甚至上千万条,而且还在不断增长。其次,IP地址查找还必须考虑数据结构的存储效率,此外,虚拟化路由器、软件定义网络(SDN)和命名数据网络(NDN)等新兴网络技术及未来网络架构的提出与发展也对IP地址查找提出了新的需求。本文提出了两种基于Trie的高性能IP地址查找算法。1)PEST算法。它既采用了x-level extension技术来提高IP地址查找速度,又利用了存储空间连续、占用内存小的Bitmap数组来减少内存空间的消耗,另外,prefix splitting策略使本算法能够顺利扩展应用于地址长度为128位的ipv6地址。2)NewTrie算法。它以2~k-multiway trie为基础,将2~k-multiway trie中的后代数组改进为一个位向量vector,vector中的1和0分别用来表示后代子节点为内部节点或者叶节点,通过使用指令popcnt来计算vector中1的数量和0的数量,这些值分别用来作为后代节点数组或者叶子结点数组的间接索引值。此外,叶向量leafvec的引入减少了冗余的叶子节点,节省了内存空间,s步长跳转策略使得IP地址查找能够在O(1)时间复杂度内完成。实验结果表明,与现有的IP地址查找算法相比较,本文提出的两种不同的基于Trie的算法具有较好的性能。PEST算法能够有效地提高IP地址查找速度,同时降低内存空间的开销;NewTrie算法能够进一步提高IP地址的查找速度,但需要消耗更多的内存空间,总体来看,两种算法都具有良好的可扩展性,能够适应日益更新的互联网时代。