路由器作为子网与子网、异种网络与子网之间相互联系的灵活纽带,承担着数据转发、路由选择、网络与流量控制等重要任务。作为路由器核心功能之一的路由查找,开始成为数据传输时延的一大瓶颈。改善路由查找算法的效率,可以大幅提高网络数据传输速率和网络数据吞吐量。在IPv4网络为主体,IPv6网络飞速发展的背景下,无类别域间路由CIDR（Classless InterDomain Routing）在提供更加灵活的地址分配方案的同时,也为路由查找算法的设计带来了更大的困难。由于CIDR的引入,路由查找从精确配匹转变为最长前缀匹配,查找逻辑复杂化。与32位的IPv4相比,IPv6具有128位二进制编码。原有的IPv4路由查找算法很难直接适应于IPv6。基于最长前缀匹配LPM（Longest Prefix Matching）,适应IPv4和IPv6网络,且查找转发速度更快、系统开销可控的路由查找算法具有极高的实用价值和研究意义。本文将围绕转发表项查找速度、内存等系统开销成本、表项更新执行速度等方面,设计并实现一种能够适用于IPv4和IPv6网络的路由查找算法。本文主要工作如下:（1）对IP技术和路由查找相关算法进行研究与分析。通过对主干核心路由表项数据和经典路由查找算法的设计理念、数据结构进行分析与汇总,为之后算法设计奠定坚实的理论基础和数据支持。针对不同地址段的特性,采用相适应的数据结构设计。（2）设计并实现了一种分段查找的路由查找算法。算法采用Trie和哈希表结构相结合的方式实现在IPv4和IPv6上的分段查找。本文设计一种基于全域哈希的哈希桶结构并部署在特定长度的地址前缀上,从而将前缀划分为多个查找区间。这种哈希结构具有映射均匀、查找速率高等特性,是实现算法快速查找的重要结构之一。经由哈希桶结构确定目的地址所在前缀区间之后,本文采用Trie结构完成末段的区间查找。该Trie结构基于Multibit Trie和前缀递推思想,在规避传统Multibit Trie的节点回溯等问题的同时,实现多比特的匹配工作。本算法使用先哈希桶再Trie的查找逻辑,能够避免大量无效查找,快速定位前缀区间,明显提高查找效率。本文从内存访问次数、查找更新效率、内存占用等方面对算法进行评估与测试。结果证明,算法在合理的内存占用下,具有较优的查找与更新性能。（3）对路由查找算法进行优化。Trie和其他树状结构相似,在一定条件下会出现数据冗余、节点稀疏等问题。本文将就由于数据特殊性引发的结构问题采用树枝裁剪、节点压缩等方式进行优化,进一步提高查找效率。在更新操作上,本文采用无锁化编程,避免使用大量读写锁对查找线程造成阻塞。算法在不牺牲查找效率的提前下,保证更新操作的正确与高效执行。