大流量网络下串匹配算法优化研究

《大流量网络下串匹配算法优化研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、国内图书分类号：TP309学校代码：10213国际图书分类号：004.4密级：公开工学硕士学位论文大流量网络下串匹配算法的优化研究硕士研究生：范宇健导师：张宏莉教授申请学位：工学硕士学科、专业：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2013年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP309U.D.C:004.4DissertationfortheMasterDegreeinEngineeringOPTIMIZATIONOFSTRINGMATCHALGORITHMINLARGEFLOWNETWOR

2、KCandidate：FanYujianSupervisor：Prof.ZhangHongLiAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerScienceandTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：June,2013Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学硕士学位论文摘

3、要字符串匹配算法一直是计算机科学领域中一个比较经典的研究方向。在IPv6协议逐步代替IPv4协议的过程中，由于地址空间的扩大，可以接入更多的设备，致使在互联网上将会产生更多的数据信息。在信息安全系统中，模式集合的不断扩展、网络流量的不断增加，这都对字符串匹配算法的性能提出了更高的要求。本文首先对相关研究背景进行了介绍，研究了多种经典的字符串匹配算法的原理，并给出了它们的优势和不足，以及适用的场合。然后介绍了当前多核处理器逐渐普及的形势，由于传统的字符串匹配算法并不能灵活的移植到多核处理器上，本文提出了一种基于自动机的并行字符串匹配算法PS

4、MBD，它避免了一些常见的并行方法的缺陷，通过对模式集合按照首字符进行分类，可以让处理器的所有核心同时处理待匹配文本，而不会产生冲突，达到了速度上的提升。由于其使用了自动机这种存储结构，所以常见的压缩自动机内存的方法都可以移植过来，在算法的优化上比较灵活。随后，本文针对特定应用中模式集合的特征优化字符串匹配算法，在分析了信息安全系统中模式集合与待匹配文本的特征之后，提出了一种基于分类思想的字符串匹配算法AWXF，它结合了AC算法和WM算法的特性，将模式集合按照模式串的长度进行划分，达到了时间消耗和内存占用上的平衡。尤其是针对WM算法部分，

5、本文提出了大规模模式集合下优化的方法，对速度的提升起到了关键作用。最后，本文对上述两种算法进行了性能测试。实验数据表明，PSMBD算法无论在命中率高或者低的情况下，都有良好的性能提升。针对AWXF算法，通过离线测试，进行初始化时间、内存占用量和匹配时间的对比，通过在线测试，进行CPU利用率的比较，测试结果表明，AWXF算法将优于其上一代CDWH算法。关键字：字符串匹配；并行算法；自动机；AC算法；WM算法；特征子串-I-哈尔滨工业大学硕士学位论文AbstractStringmatchhasbeenaclassicresearchdirec

6、tioninthefieldofcomputerscience.DuringtheIPv6protocolreplaceIPv4protocolprocess,duetotheexpansionoftheaddressspace,moredevicescanbeconnected,sothattherewillproducemoredataontheInternet.Totheinformationsecuritysystem,expandingthepatternsset,networktrafficincreasing,theyall

7、requestthestringmatchingalgorithmputforwardahigherperformance.Thisarticlefirstexplainsthebackgroundoftheresearch,studiesavarietyofclassicalstringmatchalgorithmtheory,andgivestheirstrengthsandweaknesses,aswellasfortheoccasion.Thenitintroducesthecurrentsituationoftheincreas

8、ingpopularityofmulti-coreprocessors,duetothetraditionalstringmatchalgorithmdoesnotmigrationtomul