一种基于几何区域分割的网包分类算法

摘要

网包分类算法HyperSplit采用了二分查找树结构进行查找,其决策树深度较大,规则复制较多,无法保证算法的时间性能.针对以上问题,提出了一种基于几何区域分割的网包分类算法MP2S.该算法采用多点切分和冗余覆盖删减的方法压缩决策树深度,引入区间二分查找并提出新的数据结构来优化算法的时间性能.仿真结果表明,MP2S的平均决策树深度约为HyperSplit的60％,内存访问次数比HyperSplit降低了约10％.%HyperSplit,Which is a space-decomposition based packet classification algorithm,uses a binary search tree structure.The depth of its decision tree is big and the rule replication still exists.Therefore,the search performance of HyperSplit cannot be guaranteed.This paper proposed an improved algorithm based on space-decomposition,named MP2 S.The proposed algorithm used multi-point segmentation and rules redundancy deletion to compress the depth of decision tree.It also intro duced a new data structure and the interval binary search to optimize the time performance.Simulation results show that,the average decision tree depth of MP2S is approximately 60％ of HyperSplit,and the memory access is 10％ less.