IP路由查找和报文分类模型研究

IP路由查找和报文分类作为路由器转发能力和提供高性能区分服务能力的关键因素,是当前路由器转发性能乃至整个网络性能的主要瓶颈。文章以IP路由查找和报文分类问题为研究对象,从空间几何的角度探究其本质,建立了相应数学模型MDCM,并以此为基础,讨论了各类搜索算法在IP路由查找和报文分类问题求解的优缺点,为研究和设计高性能的IP路由查找和报文分类算法提供重要指导。     

报文分类算法研究

阐述了互联网络中报文分类问题的定义、几何意义和最新研究进展.从报文分类算法的实现特征出发,对报文分类问题的各种经典算法进行了分类并逐类地详细介绍.通过对几种典型算法在虚拟环境下进行评测,总结了各种报文分类算法的优缺点和适用环境,并就报文分类问题的研究方向作出展望.     

IP报文分类算法概述

Internet的高速发展要求提供高性能的P流分类算法以更好地为防火墙、QoS、流量工程、资源预留、网络地址转换等提供服务。由于IP报文分类算法的多域特征,因此其具有相当的难度。研究者提出了很多报文分类算法,本文将这些算法概括为5类：基于Trie树的算法、基于空间分割的算法、启发式算法、基于硬件实现的算法和其他算法,并对IP报文分类算法的思想、原理和过程进行了介绍和分析,说明了这些算法之间的联系,并对这些算法在搜索和更新的时间性能、空间性能、适用性范围和优缺点等进行了分析和比较。作为总结,本文还对IP报文分类算法研究的方法和趋势进行了分析和总结。     

基于IXPl200的快速报文分类算法的设计与实现

通过对现有报文分类算法的分析和性能比较，并结合分类规则所具有的特性提出了一种新的基于IXP1200网络处理器的多维报文分类算法，称为PCBNP(packet classification based on network processor)，并达到了报文的线速转发．算法除了通过减少分类的规则数和分类的域宽来加快分类的速度外，还采用重定向排序索引、位向量表示匹配规则等技术来加快分类的速度，特别是利用了规则的动态分布规律来确定查找报文字段的顺序，通过先查找“分布最均匀的字段”来达到在所有的字段被查找之前提前找到报文匹配的过滤规则的目的．算法具有高速、多维和可扩展的特性，与现有的算法比较，该算法在综合性能上优于已有的报文分类算法．     

接入网MAC层QoS系统多维报文分类算法的研究与应用

以HFC网络核心设备双向CM(Cable Modem)为研究背景,首先对报文分类经典算法和最新算法研究进展进行总结和分析,然后依据HFC网络QoS系统需求提出了一种基于B树结构和无冲突Hash函数的BH报文分类算法,并给出了该算法的详细设计和实现过程.通过理论分析得出该算法具有时间复杂度较低和占用内存小的特点,适合于CM等嵌入式应用环境.     

基于IXP1200的快速报文分类算法的设计与实现

通过对现有报文分类算法的分析和性能比较,并结合分类规则所具有的特性提出了一种新的基于IXP1200网络处理器的多维报文分类算法,称为PCBNP(packet classification based on network processor),并达到了报文的线速转发.算法除了通过减少分类的规则数和分类的域宽来加快分类的速度外,还采用重定向排序索引、位向量表示匹配规则等技术来加快分类的速度,特别是利用了规则的动态分布规律来确定查找报文字段的顺序,通过先查找“分布最均匀的字段”来达到在所有的字段被查找之前提前找到报文匹配的过滤规则的目的.算法具有高速、多维和可扩展的特性,与现有的算法比较,该算法在综合性能上优于已有的报文分类算法.     

报文分类技术的研究及其应用

Internet网络应用的发展要求路由器支持诸如服务质量(QoS)、网络入侵检测、传输测量与记账、负载平衡、拥塞控制等多种不同的技术，虽然实现这些不同技术的细节变化可能很大，但一个公共的要求是路由器能够基于报文的头的某些字段对报文进行分类．从已有的研究表明，实现高速多维报文分类算法是非常困难的，它已成为路由器的新的瓶颈，因此吸引了许多研究人员的注意．系统论述了报文分类的相关技术，包括分类的模型、可能分类的字段，评价分类的基本标准等，通过对现有报文分类算法的比较和性能分析并结合分类规则所具有的特性，提出了设计报文分类算法所应遵循的原则和思路，同时还讨论了报文分类在网络技术领域中的应用和还需解决的一些相关问题．     

报文分类算法研究

该文首先对报文分类问题进行了形式化描述,陈述了解决该问题的几种思路并对其进行了性能的边界分析;同时给出了设计高效报文分类算法需要关注的关键问题;对目前常见的报文分类算法作了介绍,分析了这些算法的时间、空间和更新复杂度;并结合常见的报文分类算法的应用指出了各算法的适用范围;最后介绍了其它领域的分类算法的应用,展望了报文分类算法的两个发展方向。     

可扩展报文分类算法研究与评测

针对报文分类算法的可扩展性,深入分析了典型可扩展报文分类算法的时间、空间复杂度;基于ClassBench工具集开发出可扩展报文分类算法评测系统,利用该系统对典型算法在不同模拟场景下进行评测,并对各算法的性能差异和适用条件进行了系统分析。最后,对今后可扩展报文分类算法的发展趋势作出了展望。     

基于跳转表Trie树的IP分类算法

介绍了IP分类技术研究的最新成果及IP分类的典型算法,提出了一种基于跳转表Trie树JTTT的IP分类算法,通过分析比较,该算法无论是时间性能还是空间性能均优于位图交叉算法。同时,FPGA技术的飞速发展和数据处理速度的提高,使得可以用FPGA和SRAM进行处理,文中通过仿真给出了最终的分类效果,最后对提出的算法在虚拟环境下作了评判。     

流分类算法综述

流分类问题是当前国内外研究的热点 ,流分类算法层出不穷 .首先介绍了流分类的重要意义 ,然后简单的介绍了流分类问题涉及到的一些概念性问题 ,最后着重介绍了目前流分类的最新成果 .本文对每一类详细介绍了其中典型的算法 ,并且对各算法的性能进行了分析比较     

一种快速的五元一维包分类算法

包分类算法在网络安全产品中至关重要,该文介绍常见的包分类算法,针对现有包分类算法的不足,构造了一种基于Hash函数的可快速查找、快速定位五元一维包分类算法,并给出算法准确性、快速性的理论证明。     

基于完全无冲突哈希的IP数据包分类算法研究

介绍了IP分类技术研究的最新成果,以及IP分类的典型算法。提出了一种基于完全无冲突哈希和跳转表Trie树(NHJTTT:Nol-collisionHashandJumpingTableTrie-Tree)的IP分类算法,通过分析比较,该文提出的算法无论是时间性能还是空间性能均优于GridofTries算法,文章通过仿真给出了最终的分类效果。最后该文对提出的算法在虚拟环境下作了评判。     

基于RFC算法的快速多维数据包分类算法

数据包分类技术应用于许多网络服务,其性能基本决定了服务的质量。RFC算法是具有代表性的数据包分类算法,分类速度快,但由于存储开销巨大,增加了算法实现的存储消耗,加大了成本。该文在RFC算法的基础上提出了一种利用Hash技术减少存储开销且保持相对快速的数据包分类算法。     

一种新的高维报文分类算法--无相交树算法

报文分类是网络交换设备的基础操作之一，它会在很大程度上影响相关硬件设备和软件系统的功能和性能．目前存在大量的报文分类算法，但大多数都是针对低维分类问题．针对网络管理和网络入侵检测等应用需求的日益增长，该文提出了一种新的高维报文分类算法NI Trie．该算法具有其它报文分类算法所不具备的强表述支持能力和低时间复杂度并存的特点，其期望时间复杂度和期望空间复杂度均达到了同类分类算法的最优或接近最优．它具备较强的软硬件通用能力，可适用于较广的应用领域，实际应用性能良好．