Abstract:
To make the packet classification both fast point location and scalable, this paper presents a new efficient packet classification algorithm of computational geometry. It combines cross-producting with linear search. The proposed algorithm can adjust storage usage by controlling the number of filters through one-dimensional searches, with more filters searched by one-dimensional data structure, the storage needed for the cross-producting table can be further decreased. Experimental result shows that the algorithm not only improves storage performance, but also increases time performance.
Key words:
flow classification,
computational geometry,
prefix tree
摘要： 为使包分类具有快速点定位和良好的可扩展性，结合cross-producting表与线性查找提出一种新的基于计算几何的流分类算法。该算法通过控制规则的数目调整存储使用情况，使数据包中越来越多的规则被一维数据结构搜索到，进一步降低算法中cross-producting表需要的存储量。实验结果表明，该算法不仅改进了cross-producting的存储性能，而且能提高时间性能。
关键词:
流分类,
计算几何,
前缀树
CLC Number:
LIU Sha, HOU Zheng-Feng. Improved Flow Classification Algorithm of Computational Geometry Based on Multiple Fields[J]. Computer Engineering, 2010, 36(19): 99-101.
刘杉, 侯整风. 基于多域的计算几何流分类改进算法[J]. 计算机工程, 2010, 36(19): 99-101.