自1997年以来，Internet的网络流量、带宽以及物理链路速率约每6个月增长一倍，这使得报文的到达速率激增。但由于路由器需要对每个报文进行费时的处理，因此路由器性能的增长速度难以达到与之相当的水平。此外，Internet网络规模的高速增长要求IP路由查找算法能够处理大容量的路由表。而未来IPv6的应用要求IP路由查找算法能够以良好的性能处理128位的IPv6地址和对海量路由表进行查找。 另一方面，Internet需要根据不同用户的不同需求以及对服务质量的不同期望，提供多种区分服务。包括：防火墙访问控制、虚拟专用网、基于策略的路由、QOS调度、网络入侵检测、网络地址转换、拥塞控制、流量记账、资源预留、负载平衡，以及基于内容的转发等。而上述服务中的大部分都以报文分类作为其基础。但是高速多维报文分类本身是一个公认的难以解决的问题，而且报文速率的快速增长给报文分类算法带来了巨大的压力。 由于IP路由查找算法和IP报文分类算法处于网络中的关键位置，不仅提供了对互连网络的基础支持，而且其对Internet的性能和功能有着重要的影响，所以需要高速的IP路由查找和报文分类算法以适应互联网的发展。因此本文对IP路由查找和报文分类算法进行了深入研究，并针对不同的应用背景和需求提出了四个高性能算法。 本文首先对现有的典型IP路由查找和报文分类算法进行了综述和分类比较，根据它们的空间几何意义提出了IP路由查找与报文分类模型MDCM，并进一步提出了一些重要的结论、方法和原则以指导算法的设计。其中基于最大／最小熵原理和对前缀hash结果分布相似性的实验，提出了选择IP路由查找所用hash函数的最大熵判定法。 本文提出了高速硬件IPv4路由查找算法CAT。该算法突破了现有算法以存储空间和路由更新性能为代价换取查找性能的一般模式，充分运用了Amdahl定律、MDCM信息约束以及CAM和TCAM的器件特性，查找速度快，所需存储空间小。算法使用10ns的CAM和TCAM时即可满足40Gbps链路的的线速转发要求。CAT算法是一种高度并行化的硬件算法，易于流水实现，支持增量更新。由于其具有良好的可扩展性和并行性，容易通过扩展满足对更大容量的路由表和更高速度网络单元的线速转发要求。 软件实现的IP高速路由查找具有广泛的应用背景，本文提出了一个高速动态软件IP路由查找算法LPE_MH。该算法基于有限前缀扩展和多Hash函数技术实现，具有良好的时空性能，支持动态更新。而且LPE_MH算法能够根据报文流的变化动态地调整算法的搜索过程。实验结果表明该算法能够满足OC-192等高速接口的线速转发要求。 高速IPv6路由查找需要解决两个难点：128位的IPv6地址需要更多的访存时间，而海