基于标记位图的流分类算法及应用研究

《基于标记位图的流分类算法及应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于标记位图的流分类算法及应用研究ResearchandApplicationAlgorithmBasedonofFlowClassificationMarkedBitmap2012年9月合肥工业大学本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士学位论文质量要求。答辩委员会签名：(工作单位、职称)主席：旁5知嗍粤{玖大写么埋委员：亏芬盘》励妃≯乜厶冶私织懈马杰^劾复办苏锾魂耥铆2z竺婚¨0、弘徘，Jjl西务】枞。引吼1乏～独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成

2、果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得金8巴王些太堂或其他教育机构的学位或证二}}而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签字：虿化山签字日期：1DfL年I。月乡0日学位论文版权使用授权书本学位论文作者完全了解金胆王些太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金胆王业太堂可以将学位论文的全部或部分论文

3、内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文者签名：毒lK山导师签名：签字日期：加l≥年f0月岁。日学位论文作者毕业后去向：工作单位：通讯地址：签字日期：70／笋／，。月乡。日电话：邮编：／石叮U摘要随着Internet的高速发展和新型网络服务的出现，要求防火墙、安全网关等网络设备具有更强的数据处理能力。流分类技术能有效支持全方位的网络服务、提高网络设备的性能，是高速网络的关键技术之一。本文介绍了流分类技术的背景和研究现状，探讨

4、了UTM网关等防火墙相关技术，介绍了经典的流分类算法，包括Grid．of-tries算法，RFC算法，TSS算法，BV算法，ABV算法等，分析和比较了这些算法的空间和时间复杂度。ABV算法是一种改进的BV算法，该算法通过聚合因子将BV算法中的BV位图转化为聚合位图，减少了查找时问。但ABV算法要同时存储聚合位图和BV位图，在大规模规则库中其内存占用过大。针对这一问题，本文提出了一种改进的流分类算法一一MBV算法。MBV算法将ABV算法中的聚合位图转化为标记位图，使用少量的位数来代替原位图中大量连续的“0”位，使

5、得位图长度大大缩减，减少了空间消耗，提高了算法的效率。对Linux防火墙下Netfilter架构的核心函数和数据结构进行分析，探讨了Netfilter的钩子点的原理和运行机制，基于Netfilter架构将MBV算法应用在UTM网关的流分类模块上，并对MBV算法的性能进行了测试和分析。实验结果表明，MBV算法在空间上的消耗远远低于ABV算法，适合于大规模规则库的分类。关键词：流分类，ABV，MBV，标记位图AbstractWiththerapidgrowthofnetworktrafjfiCandthedevel

6、opmentofnewnetworkservices，thestrongerabilityofdataprocessingofnetworkdevicessuchasfirewallandsecuritygatewayisrequired．Flowclassificationisabletosupportafullrangeofnetworkservicesandimprovetheperformanceofnetworkdevices，whichisoneofthemostimportanttechnolog

7、iesforhigh—speednetwork．ThisdissertationintroducesthecurrentresearchesandthebackgroundofflowclassificationaswellastherelatedtechnologyoffirewallandUTMgateway，anddescribestheclassicalflowclassificationalgorithms，suchasGrid‘of-triesalgorithm，RFCalgorithm，TSSal

8、gorithm，BValgorithmandABValgorithm．Thenthetimecomplexityandspacecomplexityofthesealgorithmsareanalyzedandcompared．ABValgorithmisanimprovementofBValgorithm．IttransformsBVbitmapintoaggregatedbitma