资源描述：
《基于决策树的递归包分类算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、文章编号:基于决策树的递归包分类算法张艳军叫陈友U郭莉I,程学旗1(1.中国科学院计算技术研究所，北京10()080;2.屮国科学院研究生院，北京100039)摘要：包分类速度已经成为网络传输的瓶颈，提高算法性能是解决传输瓶颈的必然耍求.该文提出了一种新的包分类算法SRC(SensitiveRecursiveClassification).它建立在决策树基础之上在以FW,ACL为种子的规则库屮进行实验，结果表明:SRC内存使川比Hicuts减少3到10倍，最坏查找速度比Hicuts提高5倍以上;SRC的内存使用比EGT-PC减少2到8倍，最坏查找速度比EGT-PC提高4倍以
2、上.关键词：包分类；决策树；映射中图分类号：文献标识码：ARecursivePacketClassificationAlgorithmBasedonDecisionTreeZHANGYan-junU2,CHENYouU29GUOLi1,CHENGXue-qi1(1.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing,China;2.GraduateUniversity,ChineseAcademyofSciences,Beijing,China)Abstract:Computationalcompl
3、exityisnottheonlychallengingaspectofthepacketclassificationproblem.Increasingly,trafficinlargeISPnetworksandtheInternetbackbonetravelsoverlinkswithtransactionrateinexcessofonebillionbitspersecond.ThispaperintroducesaclassificationalgorithmcalledSRC(SensitiveRecursiveClassification).Itisbas
4、edonadecisiontreestructure.Doingmanyexperiments,especiallyinFWandACL,weverifiedthatSRCuses3to10timeslessmemorythanHiCuts,whiletheworstcasesearchtimeisupto5timessmaller.ComparedwithEGT-PC,SRCuses2to8timeslessmemorywhiletheworstcasesearchtimeisupto4timessmaller.Keywords:packetclassification;
5、decisiontree;mapping1引言随着网络速度的捉高和服务需求种类的增加,越來越多的网络服务需要包分类技术•包分类是下-•代因特网网络设备(例如MPLS路山器，防火墙,VPN网关,VoIP网关等)和新型网络服务(例如养分服务，包安全过滤，流暈记帐，流暈限制服务等)实现的关键技术网络链路速度的增长对包分类性能提出了更高的要求,10Gb/s的链路速度需要包分类器毎秒处理3100万个大小为40字节的包.在一定内存空间上研究有效的包分类算法及其实现技术是丨I前网络技术领域的热门话题.作者简介：张艳军(1975-)，男，硕士生，研究方向是网络与信息安全Emaikzhang
6、yanjun@software.ict.ac.cn陈友(1981-),男，硕士生，研究方向是网络与信息安全郭莉(1969・)，女，高级工程师，研究方向为网络与信息安全，人规模字符串匹配程学旗(1971・)，男，研究员，研究方向为网络信息安全、人规模信息检索与信息挖掘网络包分类就是根据网络上传送包的包头信息,山分类器(Classifier)对包进行分类，找出每一•个包匹配的规则(Rule),以区分其所属的网流(Flow).在因特网的分层模型中，要传输的数据被各层协议的包头依次封装着，每一层的包头祁包含着若干域(Field),它们分别携带着该层协议的特征数据.包分类规则可以涉及
7、到从数据链路层到应用层的任何域，它对所涉及的域及域的取值或取值范围加以定义.若干个涉及相同域的包分类规则的集合构成包分类器.2SRC算法2.1SRC算法思想SRC算法是基于决策树的基础上建立起來的.决策树的分支策略按照HiCuts[l]算法川到的分支策略思想，即对分类器中的每个规则，按照其域值所在的区间范围来划分.而在叶结点上采用一种类似于RFC[2]算法的处理方式.由于Hicuts算法是在一定的内存使用上建立的，因此叶结点中包含的分类规则数口被限定为小于某一特定值.由于要提高算法的性能，这一特定值一般都比较小.这
