路由器是组成互联网的重要节点设备,位于ISO/OSI七层模型中的网络层,负责网络中数据的转发工作。它将不同的网络连接起来,并为经过它的数据包选择最佳的出口进行转发。路由器转发数据包的快慢,决定了经过路由器的所有数据包的传输速度。目前,链路上传输的数据已经可以通过光纤来承载,其传输速度可以达到400Gbps,因此当前路由器的性能瓶颈在于路由查找算法。路由器的查找效率决定了路由器的性能,决定了互联网的数据吞吐量。互联网上大多数的流量还是由IPv4网络承载,研究基于IPv4的路由查找算法有其现实意义。如何解决最长前缀匹配问题,是设计路由查找算法的核心问题,目前众多学者主要围绕路由查找算法的最长前缀匹配问题展开研究。IPv6作为IPv4的下一代技术,具有128位的地址长度。它对IPv6网络中的核心路由器处理负担更重、要求更高。已有的基于IPv4的路由查找算法,扩展到IPv6后无法适应新的需求或效率低下,需要建立新的基于IPv6的路由查找算法。论文主要围绕基于IPv4、IPv6路由查找算法展开,分别给出了适用于IPv4和IPv6的路由查找算法。主要工作包括:1、分析了 IPv4的地址结构及其发展史,通过对核心路由器中路由表数据的分析,发现了 IPv4地址前缀分布呈现一定特点:地址前缀长度为24的表项最多。论文针对这个特性,提出了一种哈希表和多比特树相结合的分阶段路由查找算法,算法将路由查找阶段分为两个阶段,分别是哈希表查找阶段和多比特树结构查找阶段。为了减少对存储器的访问,还提出了一种固定高度的多比特树结构:4-3Trie,该结构将路由查找时访问存储器的次数限定在了可接受的范围之内。算法分析和实验仿真表明,该算法通过利用IPv4地址前缀分布的特点,提高了查找效率,具有良好的路由查找性能。2、分析了 IPv6地址结构,通过对从Internet核心路由器的路由表中获取了路由前缀分布数据分析,发现地址前缀长度为16倍数的表项最多,其中尤以地址前缀长度为48的表项最多,其次是地址前缀长度为32的表项。同时分析还发现,在路由表中前缀中以20、24、26、28和2a开头的表项占了绝大多数。在此分析基础上,综合运用了哈希表和多比特树两种结构,提出了一种适用于IPv6的分阶段的路由查找算法,给出了 H16、H32、H32c、H48、H48c和H64六个哈希函数和一套哈希冲突解决策略。同时算法还提出了 6-5-4Trie结构,将树的高度控制在了可接受的范围,并且,算法在压缩树高度的同时,尽可能的降低树的稀疏程度来减少存储空间的浪费。算法分析和实验仿真证明,该算法在查找速度和存储空间上都有优势,能够满足核心路由器的性能要求。路由查找算法是复杂的,众多学者对其进行了深入的研究,我们是在前人研究的基础上进行了改进和探索。相关研究成果已被录用,即将在国内外的核心期刊上发表。