互联网产生于19世纪60年代，发展至今早已超出其设计初衷。面对纷繁复杂的应用和日益增长的需求，传统的以TCP/IP为核心的互联网架构在可扩展性、安全性和移动性等方面暴露出越来越多的问题。为从根本上解决这些问题，一些新型互联网协议和架构应运而生。但无论如何变革，互联网服务于信息互联互通的本质不会改变，数据包转发都是核心操作。这其中，路由查找又扮演着至关重要的角色。所谓路由查找，就是根据数据包携带的路由信息在一组预定义的转发规则中查找匹配项以指导该数据包的转发。查找速度、存储效率和可扩展性是主要挑战。本文立足当下，面向未来，围绕现有的TCP/IP网络和网络功能虚拟化、软件定义网络、命名数据网络这三个具有代表性的新型应用场景和网络架构，针对路由查找这一核心问题进行深入研究，开展了七个工作，致力于查找引擎综合性能的提升。　　本文首先围绕TCP/IP网络中的路由查找，即IP地址查找（简称IP查找）展开研究。针对现有方案在压缩存储时难以兼顾更新和查找优化的现状，本文深入到模型层面进行探究，提出了一种基于前缀拆分的并行查找模型。不仅能利用IP前缀间的局部相似性从根本上压缩存储，还能在模型层面提供并行操作的支持。此外，路由更新被成功分流，能减少大量无用操作、降低更新开销。实验表明，拆分模型以牺牲一定的片外存储为代价，可换取片上存储超90％的压缩比，还能实现更新效率和查找性能的显著提升。　　在IP查找引擎的硬件部署平台方面，基于可编程门阵列(FPGA)的流水线结构正逐步成为首选。其中，均衡各流水级的存储开销和子流水线间的负载是关键挑战。现有方案需要付出较高的代价才能实现理想的平衡度，在大规模转发表或IPv6的场景下表现差强人意。鉴于此，本文基于前缀拆分、子树旋转、联合最优步长计算等一系列平衡优化，提出了一种存储高效且平衡的双向流水线结构，在获得与现有方案同等理想的平衡度时所需流水级的数量减少了75％～85.7％。此外，在查找延时、单次查找平均访存、存储效率、更新开销以及多流水间的负载均衡等方面也都表现出了明显的优势。　　在软件平台方面，基于图形处理单元(GPU)的并行计算架构发展迅速。虽然现有方案已经实现实现O(1)的查找算法，但仅支持IPv4，且难以实现批量更新的完全并行处理。这就限制了更新性能，同时也导致系统吞吐率的不稳定。本文先提出一种线索化的线段树结构及相应的更新机制以解决批量更新完全并行的瓶颈，同时最大限度地消除冗余访存，使更新效率提升近9倍。当现有方案的查找吞吐率因更新频率增加而下降超50％时，该方案的吞吐率甚至只下降了4％。接着，本文进一步探索查找加速以及对IPv6的支持，提出了一种基于GPU加速的多步长前缀树结构。通过紧凑的编码设计和步长优化来调整树形，配合高效的线下/线上协同更新机制，再借助多流流水线实现优化，不仅可实现每秒10亿和6.5亿次的IPv4/IPv6地址查找速度，还能在高频更新下保持稳定。　　虚拟化路由器是实现网络功能虚拟化的基础设施，也是其核心理念的体现。在虚拟化路由器中，路由查找需处理多个转发表的维护和查找问题（简称多表查找）。现有方案通过预留存储位来管理虚拟路由器实例号(VID)，存在扩展性瓶颈。另一方面，目前尚没有研究工作专门讨论GPU加速多表查找。鉴于此，本文针对GPU加速的场景提出了一种新型数据结构——TailTrie。引入有限状态机实现VID的动态管理，再采用双数组前缀树进行压缩，不仅将存储开销的增长趋势由线性优化为亚线性，还支持动态插入实例。借助GPU可在控制查找延时低于100μs的前提下实现亿次每秒级的IPv4/IPv6地址查找。　　在软件定义网络中，OpenFlow交换机是核心基础设施，采用流表来维护包处理规则。路由查找（即流表查找）需解决的关键问题是多域规则匹配。针对现有方案在规则域或者规则数增多时难以同时保持高时、空效率的现状，本文提出了迭代降维定理，并以此为基础设计了迭代哈希算法，可实现时、空高效且可扩展的多域规则匹配。实验表明，相比于现有的决策树算法，该算法存储开销减少80％，执行规则匹配时能提速5倍以上。　　在命名数据网络中，路由查找涉及两种包、三张表，但核心操作都是名字查找。现有方案借助GPU加速来满足线速要求，但数据拷贝和批处理导致的查找延时较大。鉴于此，本文另辟蹊径，首次尝试利用FPGA来加速名字查找，提出了层次化的对齐迁移数组结构。先将名字前缀树逐层转化为一系列状态迁移以提升存储效率，然后引入多点探测、并行验证的机制实现进一步存储压缩，最后根据前缀长度的分布规律完成流水线映射。实验表明，相比于现有的GPU加速方案，该方案的存储开销可减少90％。此外，查找吞吐率略有提升，而查找延时下降了近3个数量级。　　综上所述，本文首先对IP查找模型进行深入研究，再分别探索新兴软、硬件平台上的IP查找加速。同时还兼顾三种新型场景，致力于解决路由查找问题的关键技术挑战。不仅实现了各场景下路由查找引擎的综合性能提升，一些探索性的研究也为未来工作的开展指明了方向。