一种基于搜索空间分解的报文分类算法

Packet Classification Algorithm Based on Search Space Decomposition

报文分类算法的关键问题是查找准确且快速,最简单的分类算法就是线性查找,该算法的时间复杂度和空间复杂度均为O(N),线性查找的思想简单、易于实现、空间复杂度好,可以和其它算法混合使用,进而提高算法的分类速度。快速的分类算法采用很复杂的数据结构,牺牲空间来换取时间,甚至过分要求分类的快速性,忽略了空间性。文章根据这一问题进行展开,详细分析了经典的报文分类hicuts算法,分析其时间复杂度和空间复杂度的关系,并提出一种不过分降低分类速度的前提下,有效降低空间复杂度和预处理时间的改进方法。

A key issue with packet classification algorithm is to search accurately and quickly. Line-ar search is the simplest classification algorithm due to its easy rationale and implementation, whosetime complexity and space complexity are O（N）. It can also be mixed with other algorithms to im-prove classification speed. However, fast classification algorithms usually use very complex datastructures to gain speed at the cost of space. Considering this, the paper analyzes in detail the rela-tionship between time complexity and space complexity of the classical hicuts algorithm, and propo-ses an improved classification algorithm which could effectively reduce space complexity and prepro-cessing time without excessive speed decrease.