一种采用启发式分割点计算的包分类算法

陈兵; 潘宇科; 丁秋林

doi:10.3724/SP.J.1146.2008.00626

一种采用启发式分割点计算的包分类算法

doi: 10.3724/SP.J.1146.2008.00626

基金项目:

国家部级基金资助课题

计量
- 文章访问数: 3142
- HTML全文浏览量: 113
- PDF下载量: 931
- 被引次数: 0
出版历程
- 收稿日期: 2008-05-16
- 修回日期: 2009-02-17
- 刊出日期: 2009-07-19

A Heuristic Lookup Partition Algorithm for Packet Classification

摘要

摘要: 针对区域分割包分类算法存在的规则分布差异较大的缺陷，该文提出一种基于启发式分割点计算的区域分割包分类算法。首先依据规则集的分布规律进行分割点计算，然后再进行结构化建树。规则检索时间主要包括分割点匹配时间和分割点内规则的线性查找时间。该算法能够尽量将规则平分到各分割点，减少了规则分布的差异。仿真实验结果表明该算法降低了规则数增加对算法性能的影响，支持规则集的实时更新。
- 电信网络;包分类;区域分割;分类器
Abstract: Regional partition packet classification algorithm is one of the most effective algorithms. To solve the unsymmetrical distribution problem of regional partition for packet classification, a heuristic lookup partition algorithm is proposed after analysing the character of rules sets. The main research work on the algorithm in this paper includes two parts: the method of lookup partition to ensure the symmetrical distribution of rules, and the construction of decision tree based on the partition found. The time cost of this algorithm is composed by the time for lookup partition and the time for line-search in the partition found. The results of simulation show that the algorithm is not sensitive to the increasement of rules, meanwhile it supports the incremental updating on-line.

HTML全文

参考文献(1)

Taylor D E. Survey and taxonomy of packet classificationtechniques[J].ACM Computing Surveys.2005, 37(3):238-275[2]陆晟, 龚俭. 一种新的高维报文分类算法-----无相交树算法[J].计算机学报, 2003, 26(11): 1502-1509.Lu Sheng and Gong Jian. A multi-dimension packetclassification algorithm: Nonintersection trie[J]. ChineseJournal of Computers, 2003, 26(11): 1502-1509.[3]Buddhikor M M, Suri S, and Waldvogel M. Spacedecomposition techniques for fast layer-4 switching[C].Proc.of Conf. on Protocols for High Speed Networks. Salem,Massachusetts, USA,August 1999: 25-41.[4]Feldtnan A and Muthukrishnan S. Tradeoffs for packetclassification[C]. Proc. of Infocom. Israel, March 2000:193-202 .[5]Gupta P and Mckeown N. Packet classification usinghierarchical intelligent cuttings[J].IEEE Micro.2000, 20(1):34-41[6]Singh S, Baboescu F, Varghese G, and Wang J. Packetclassification using multidimensional cutting. Proceedings ofACM SIGCOMM[C]. Karlsruhe, Germany, 2003: 238-275.[7]颜天信, 王永刚等. 并行区域分割包分类算法[J]. 小型微型计算机系统, 2005, 26(11): 1898-1902.Yan Tian-xin and Wang Yong-gang, et al.. Packetclassifi-cation using parallel regional partition[J]. Mini-MicroSystems, 2005, 26(11): 1898-1902.[8]王永刚, 石江涛等. 网络包分类算法仿真测试与比较研究[J].中国科学技术大学学报, 2004, 34(4): 400-409.Wang Yong-gang and Shi Jiang-tao, et al.. Simulated testingand comparison of algorithms for packet classification [J].Journal of University of Science and Technology of China,2004, 34(4): 400-409.[9]Masatoshi Kakiuchi, Naoto Morishima, and Hideki Sunahara.Design and implementation of a parameter filter based onvirtual bounding rectangles[J]. Systems and Computers inJapan, 2007, 38(13): 92-103.[10]田立勤, 林闯等. 基于IXP1200 的快速报文分类算法的设计与实现[J]. 计算机研究与发展, 2003, 40(11): 1616-1625.Tian Li-qin and Lin Chuang, et al.. Design andimplementation of fast packet classification based onIXP1200[J]. Journal of Computer Research and Development,2003, 40(11): 1616-1625.[11]Kounavis M E, Kumar A, Yavatkar R, and Vin H. Two stagepacket classification using most specific filter matching andtransport level sharing[J]. Computer Networks: TheInternational Journal of Computer and TelecommunicationsNetworking, 2007, 51(18): 4951-4978.

施引文献

资源附件(0)

访问统计