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

Packet Classification Algorithm Based on Search Space Decomposition

作　　者：隋然 张杰鑫 邰铭 

机构地区：[1]全军后勤信息中心,北京100842 [2]数学工程与先进计算国家重点实验室,河南郑州450001

出　　处：《信息工程大学学报》2015年第5期608-612,635,共6页Journal of Information Engineering University

基　　金：数学工程与先进计算国家重点实验室开放课题(2013A03;2013A10)

摘　　要：报文分类算法的关键问题是查找准确且快速,最简单的分类算法就是线性查找,该算法的时间复杂度和空间复杂度均为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.

关 键 词：报文分类 算法 空间分解 决策树 

分 类 号：TN918.1[电子电信—通信与信息系统]