当前，因特网正呈现两方面的新变化，一方面，因特网正日益变得拥挤；另一方面，因特网上的用户正呈现许多不同的种类，它们从安全、性能、可靠性方面对因特网的期望是不同的。 为适应这些新变化，ISP一方面必须升级因特网骨干网络的速度，一方面必须筹划新的有差别的网络服务，以满足不同用户的需要。由于光纤技术和DWDM技术的发展使得链路的速率不再成为瓶颈，而路由器——作为连接链路的节点——的性能会成为主要瓶颈。这主要由于路由器对于每个输入分组需要执行许多操作，包括十分复杂的分类操作：它们需要对每个输入分组执行最长前缀匹配(longest prefix matching)以发现其下一跳(Next Hop，NH)地址；需要对每个输入分组执行多维分组分类以便在执行QoS调度、多目转发(multicast forwarding)、虚拟专用网(Virtual Private Networks，VPN)、基于策略的路由(policy-based routing)等任务时区别对待不同的分组。 分组分类是路由器根据IP分组的多个域，从分类器数据库中匹配每个输入分组，确定分组转发规则的技术。分类器为实现因特网新业务提供了统一的方式，分组分类是因特网提供一切有差别服务和其他新业务的基础，高速分组分类问题是具有重要现实意义和理论价值的研究课题。 单纯根据IP目的地址的"路山查找是因特网环境下一维分组分类的主要形式；包含IP源地址和IP目的地址的二维分组分类，包含IP源地址、IP目的地址、协议域、源端口号和目的端口号的五维分组分类是因特网环境下多维分组分类的主要形式。 针对IP路由查找问题，本文提出基于LSO(Length Segment and Offset table)的高速IP路由查找算法；针对多维分组分类问题，本文提出基于SPLS(Shotter Perfix Length Splitting)的高速分组分类算法。 基于LSO的高速IP路由查找算法属于一维分组分类算法，主要适用于核心路山器(IPv4)环境，同时也兼顾企业级路由器环境。其主要特点是使用可变大小的段表和偏移量表，使得算法能适应SRAM和FPGA芯片内存储器容量的变化，在不同的情况下可以进行不同的选择，当段表长度取较小值时，偏移量表占用存储空间大，这时可以使用图论压缩技术对偏移量表进行压缩。LSO算法不仅适合于硬件实现，而且适合于软件实现，本文给出了该算法的具体实现方法，并对算法的存储代价和查找性能进行了详细的分析和模拟。段表长度可以根据实际路由表进行实时计算，使得存储代价达到最小，本文给出了计算段表长度的简单方法和硬件实现时段表长度的协商机制。用硬件实现时，LSO算法具有查找速率快、更新速率快、所需存储空间少、硬件实现代价低、硬件实现简单等特点，是一种理想的适合于10Gbps端口核心路山器环境的查找机制。 国防科学技术人学研究生院学位论文一 基于SPLS的高速分组分类算法属于多维分组分类算法，SPLS技术是一种以较短前缀长度将大分类器集合分割成许多小分类器子集合，使得分割后的小分类器子集合可以使用己有的快速P路由查找方法进行查找的技术。SPLS以多位键树（multi－bit trie）作为实现时的基本数据结构。若以多重链表实现多位键树，通过分析和模拟，度为4的多位键树（四叉键树）其性能达到最优。为改善性能，可以将节点的所有子节点用连续存储器存储，实验显示，它比使用多重链表实现时性能大大提高，对于20k＜N＜40k的分类器数扼库，其平均分组查找速率达到4．598MppS，存储空间为3MB－6．SMB。为进一步改善性能，可以使用路径压缩键树和级压缩键树减少节点数。将基于SPLS的高速二维分组分类算法扩充至多维时，需要根据具体维的特征进行特殊处理。 另外，本文还设计和实现了一种PNI核心路山器网络层输出控制部件。PNI核心路山器是一种用于高速因特网主干的P路山器，它采用高速分介式路山体系结构和先进的高速交换阵列，线速转发P分组。核心路由器网络层输出控制部件负责从交换模块接收并处理分组。