网络包分类算法仿真测试与比较研究

在深入分析基于树结构和计算几何学点定位算法而衍生的主要分类算法原理的基础上 ,建立了算法性能评估仿真测试平台 .平台包括网络流的软件仿真、算法的软件实现和算法性能参数测试统计三个主要部分 .通过对各算法的时间性能和空间性能及其随分类规则数和分类域数的变化趋势的测量 ,从数量上把握各算法的主要特点及其适用性 ,从而可以将各种算法有机地结合在一起胜任速度越来越高的网络应用需求 ,同时也是进一步研究其它算法的基础 .

并行层压缩树包分类算法

在层压缩树路由算法思想基础上提出了一种新的硬件包分类算法———并行层压缩树包分类算法.该算法是基于独立存储单元和多域并行处理并在FPGA内部实现的高速网络包分类算法,主要包括单通道并行搜索和多通道综合比较两大部分.仿真结果表明在40 MHz的搜索时钟频率下,该算法能够达到每秒2 M包头的处理速度,其空间性能明显优于其他算法,具有O(d)的时间复杂度(d为域的个数)和O(dN)的空间复杂度(N为规则数).

层压缩树包分类算法研究

包分类技术是下一代网络设备的关键技术之一.研究有效的包分类算法是目前网络技术领域的热门课题.层压缩树包分类算法的基本思想是:对路径压缩之后的二叉树进行层压缩,使压缩树中的节点能够按序存储在数组中.通过对数组元素跳跃式的查找快速的对包头进行分类.仿真试验结果表明该算法在较大规则数下能够实现对包头的快速分类,分类速度可以达到每秒处理接近2M个包头,具有O(d)的时间复杂度(d为域的个数);在中等规模规则数下具有O(dN)的空间复杂度,并且其存储量优于其他算法(如Bitmap和区域分割包分类算法).由于层压缩树算法对包头的每个域独立查找,在硬件实现上采用并行查找各个域的处理方式将使该算法的查找性能得到更大的提高.