层压缩树包分类算法研究

摘要：

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

关键词：包分类、层压缩树包分类算法、时间性能曲线、空间性能曲线、仿真测试

所属期刊栏目：27

分类号：TP393(计算技术、计算机技术)

资助基金：中国科学院基金

在线出版日期：2006-06-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1023-1028