随着Internet技术的迅猛发展,路由表,网络速度,网络流量都在持续增长,IP路由查找困难度也随之增加。无类别域间路由选择(CIDR,Classless InterDomain Routing)的使用,使得路由器必须在路由表中找到与IP地址最长匹配的前缀进行路由转发。IP地址查找是路由器转发性能的瓶颈,因此本文对IP路由查找技术进行了深入研究,并分别对两篇文献中提出的算法进行了改进。本文首先对路由系统和IP路由查找技术进行了相关研究,对当前IP路由查找技术的难点进行了分析;然后对当前已有的典型IP路由查找算法进行了分类研究,重点对基于Trie树的算法、基于哈希技术的算法和基于硬件TCAM的算法进行了研究和分析,总结了各种算法的优点和缺点,对本文提出改进算法起到了较大的启发。本文针提出了一种基于Trie树的动态规划算法。该算法可以确定一个最优的前缀划分方式,以使在所有不同的划分方案中,该划分方案可以达到空间最优,哈希结构使用的空间达到最小。实验结果表明,不同划分方式使用的空间差距较大,而本文提出的动态规划算法可使空间达到最优。本文还提出了一种可升级的、支持快速动态更新的基于B+树的IP路由查找算法。该数据结构用最特殊前缀作为关键字来构造B+树,用一个无符号整数来压缩存储包含一个最特殊前缀的所有前缀。和其他可升级的动态算法相比,该算法对路由表中的每一个前缀只存储一次,且查找到叶节点就能找到匹配的最长前缀,而不会往回查找。对于一个有n个前缀的路由表,使用m阶的B+树,该查找结构空间复杂度为O(n),查找时间复杂度为O(log_mn),且前缀插入和删除效率的效率为O(mlog_mn)。实验结果表明,本文提出的基于B+树的IP路由查找算法能有效提升IP查找的速度,且支持IP前缀的动态更新和IPv6地址。