基于openflow协议的高速包分类算法研究

《基于openflow协议的高速包分类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

基于OpenFlow协议的高速包分类算法研究万云凯2015年11月 中图分类号：TP393UDC分类号：004.7基于OpenFlow协议的高速包分类算法研究作者姓名万云凯学院名称计算机学院指导教师嵩天副教授答辩委员会主席廖乐健教授申请学位工学硕士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2016年1月7日 TheResearchonHighSpeedPacketClassificationAlgorithmsbasedonOpenFlowProtocolCandidateName：YunkaiWanSchoolorDepartment:ComputerSchoolFacultyMentor:TianSongChair,ThesisCommittee：LejianLiaoDegreeApplied:MasterofPhilosophyMajor：ComputerScienceandTechnologyDegreeby:BeijingInstituteofTechnologyTheDateofDefence：Jan7,2016 研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究成果。尽我所知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期： 摘要随着互联网技术的发展和互联网应用的增多，数据包分类不再局限于传统的五元组，以软件定义网络为代表的新兴网络技术的发展使得包分类面向更多维度。因此，如何设计出一种适用于新型网络架构的快速有效的包分类算法对互联网的发展和网络服务质量的提高变得至关重要。本文首先介绍了数据包分类问题的背景和国内外的研究现状，阐述了包分类问题的产生与演变，给出了包分类问题的定义，归纳了包分类问题的评价标准，说明了包分类算法的设计原则。然后本文详细描述了各个经典五元组包分类算法的原理，分析了它们的时间、空间性能和应用场合，指出了它们向更多维度扩展的局限性。其次本文介绍了OpenFlow网络，给出了OpenFlow流表包分类的特点，利用这些特点，再结合网络流的局部性原理，本文提出了一种流量自适应的多维度包分类方法。该方法可以根据网络流量的实时分类结果动态调整多维度匹配顺序，优先匹配当前流量所需要的字段，通过忽略通配字段来达到优化查找速度的目的。同时，该方法将多维度字段分组，结合具体字段类型和字段的匹配方式选择最优匹配算法。最后，本文利用虚拟软件在电脑上搭建了OpenFlow实验环境，构建了适用于OpenFlow包分类的规则集，在OpenFlow交换机模拟工具OpenvSwitch中实现了本文所提出的方法，实验结果表明，该方法相比已有的OpenFlow算法性能提高约两倍，相比从五元组包分类算法扩展的方法性能也大大提高。本文方法有着显著的理论价值和实践应用价值，网络对服务质量要求的提高使得数据包的分类越来越细粒度，本文方法不仅可以满足当前的网络需求，而且维度扩展性良好，非常适合应用于各种新型网络。关键词：包分类；软件定义网络；流量自适应；位向量；OpenFlowI AbstractWiththedevelopmentofInternettechnologyandtheincreaseofInternetapplications,packetclassificationisnolongerlimitedtothetraditionalfive-tuple.SoftwareDefinedNetworkanditsimplementation,representedbyOpenFlow,makethepacketclassificationfromfive-tupledimensionstomorepacketheaderfields.ItisveryimportantthathowtodesignafastandefficientpacketclassificationalgorithmforthedevelopmentoftheInternetandtheimprovementofthequalityofnetworkservice.Thispaperfirstintroducesthebackgroundofdatapacketclassificationandtheresearchstatusathomeandabroad,expoundsthegenerationandevolutionandgivesitsdefinition,summarizesitsevaluationcriteria,anddescribesthedesignprincipleofthepacketclassificationalgorithm.Secondly,thispaperintroducestheOpenFlownetwork.UsingthecharacteristicsofOpenFlowpacketclassification,wepresentanOpenFlowalgorithmbasedonbitvectorformultipledimensions.Thisalgorithmexploitsdifferentmatchingalgorithmsondifferentfields,andincreasesthesearchspeedbyignoringsomewildcardmatchingfieldsresultedfromoptimizingtheorderofdifferentmatchingfieldsaccordingtothelocalityoftrafficflow.Finally,thispaperbuildstheOpenFlowexperimentalenvironment,constructstherulesetsuitableforOpenFlowpacketclassificationandimplentsthetheproposedmethod.ExperimentalresultsonOpenvSwitchshowthattheproposedalgorithmcanachieveabouttwotimesspeedupthanthealgorithminOpenvSwitch,and40%speedupandabovethantheotheralgorithmsextendedfromfive-tupleclassifications.Thismethodhassignificanttheoreticalandpracticalvalue,theimprovementofthequalityofservicenetworkmakesthepacketclassificationmoreandmorefine-grained,themethodcannotonlymeettheneedsofthecurrentnetwork,butalsobesuitableforkindsofnewnetworkarchitectureaccordingtoitsgoodscalability.KeyWords:Packetclassification;SoftwareDefinedNetwork;Flowadaptable;Bitvector;OpenFlowII 目录第1章绪论..................................................51.1研究的目的和意义................................................51.2国内外研究现状..................................................61.2.1包分类算法研究现状......................................61.2.2OpenFlow研究现状.......................................71.3本文研究内容....................................................81.4论文结构........................................................9第2章数据包分类问题概述....................................112.1包分类问题的提出与演变.........................................112.2包分类问题的定义...............................................112.3包分类算法评价指标.............................................122.4包分类算法的设计原则...........................................132.5包分类算法的应用...............................................142.6本章小结.......................................................15第3章经典数据包分类算法....................................163.1基于TCAM的算法................................................163.2基于数据结构的算法.............................................163.2.1基于查找树的算法.......................................163.2.2基于哈希的算法..........................................193.3基于空间划分的算法.............................................203.4基于维度分解的算法.............................................223.5各个算法比较与分析.............................................273.6本章小结.......................................................28第4章OPENFLOW数据包分类...................................29III 4.1OpenFlow网络..................................................294.2OpenFlow包分类的特点..........................................314.3网络流的局部特性...............................................324.3.1网络流的定义............................................324.3.2网络流的不平衡现象和局部特性............................334.4本章小结.......................................................33第5章流量自适应的多维包分类算法............................345.1算法思想.......................................................345.2算法设计.......................................................345.3字段内部匹配算法...............................................365.3.1精确匹配字段算法.......................................365.3.2前缀匹配字段算法.......................................405.3.3范围匹配字段算法.......................................425.4本章小结.......................................................42第6章实验论证与性能分析....................................446.1实验环境.......................................................446.1.1组建OpenFlow网络.......................................446.1.2构建OpenFlow规则集.....................................456.2实验论证和算法比较.............................................466.2.1同OpenFlow原有算法的比较...............................466.2.2同五元组扩展算法的比较..................................476.3本章小结.......................................................49结论.........................................................50参考文献.....................................................52攻读学位期间发表论文与研究成果清单...........................56致谢.........................................................57IV 第1章绪论1.1研究的目的和意义伴随着互联网技术的不断发展、互联网应用的不断涌现和互联网构架的不断演进，网络安全和网络服务要求网络流量进行更加细粒度的分类[1-3]，以满足在防火墙(Firewall)[4]、服务质量(QualityofService)[5-6]、策略路由(PolicyRouting)[7]、流量计费(TrafficBilling)[8]等各个领域[9]的需求。数据包分类技术应运而生，它通过识别数据包包头各个字段(Field)的值将它们匹配到预定义的规则集中，然后根据匹配规则的决策(Action)对数据包进行相应的处理，如图1.1所示。与早期网络应用仅依靠目的IP地址进行路由不同的是，数据包分类更加地复杂和多元化，层级不仅仅局限于网络层，字段也不再仅仅包括IP地址，比如还可能包括传输层的端口号。包分类包处理数据包负载包头分类引擎决策规则库图1.1数据包分类模型与此同时，网络功能虚拟化（NetworkFunctionVirtualization）[10-11]以及软件定义网络（SoftwareDefinedNetwork，SDN）[12-13]等一系列前沿网络技术的发展，对数据包分类技术提出了更高的标准和要求。SDN是一种通过将网络控制与网络转发解耦合构建开放可编程的网络体系结构的新型网络体系结构，其核心技术OpenFlow[14]通过将网络设备的控制层面和数据层面分离开来实现网络流量的管理和控制。OpenFlow交换机是OpenFlow网络进行数据包转发和分类的关键部分，在传统网络设备中，交换机和路由器的数据转发需要依赖设备中存储的二层MAC地址转发表或者三层IP地址FIB（ForwardInformationBase，转发信息表），而OpenFlow交换机则依据自身的流表，与前二者的区别是它的表项中含有网络中各个层次的协议字段信息，从而在进行数据转发时可以使用更丰富更灵活的规则。传统的数据包分类大多依据的网络协议字段是五元组（源IP地址，目的IP地址，5 源端口号，目的端口号，网络协议），而OpenFlow包分类则包含更多的协议字段。OpenFlow第一个可用于商业化产品的OpenFlow1.0[15]中就包含了包括数据链路层、网络层、传输层在内的10个协议字段。这些字段数量多、长度不等、匹配方式不同，因此数据包的转发速度和存储效率这两个问题是OpenFlow网络面临的巨大挑战。包分类速度决定着OpenFlow交换机的吞吐能力，已经成为了OpenFlow交换机进行流量处理和分类的瓶颈，因此，设计一个高速有效的OpenFlow包分类算法对整个软件定义网络的发展至关重要。1.2国内外研究现状1.2.1包分类算法研究现状数据包分类技术作为网络分类设备的核心技术，一直受到学术界的关注，从最早的用于路由寻址的IP查找，到用于网络服务的五元组包分类，再到用于新型网络构架的更细粒度的包分类，出现了许多优秀的算法[16-18]。实现最简单的包分类算法是线性算法，但它缺乏可扩充性，查找时间随着规则数目的增长呈线性增长，所以一般不会被采用。包分类算法包括基于硬件实现的算法和基于软件实现的算法。硬件算法主要是基于TCAM（TernaryContentAddressableMemory，三态内容寻址器）的算法[19-21]。TCAM是一种在CAM（ContentAddressableMemroy，内容寻址器）的基础上发展而来的专门用于快速查找的硬件芯片，它能够在很短的时间内完成关键字的匹配查找，速度是SRAM（StaticRandomAccessMemory，静态随机存取存储器）的6倍。TCAM具有查找速度快，操作简单的优点，已经在路由设备中广泛用于路由项的查找。但同时它也具有3个明显的缺点：高成本，高功耗，高更新代价。在当今的网络条件下，交换机需要容纳大量的规则，这对基于TCAM的算法是一个很大的挑战。软件包分类算法大体上可以分为两类：多维联合分类算法和单维组合分类算法[22]。多维联合分类算法主要包括基于数据结构的算法（又分为基于查找树的算法和基于哈希的算法）和基于空间划分的算法。基于查找树的算法主要使用的数据结构是查找树，它将字段区间进行划分，建立成一棵决策树，通过决策树进行包分类查找，主要有分层查找树算法[17]、集合归并查找树算法、查找树网格算法[23]等。基于哈希的算法使用的数据结构是哈希表，这类算法分类速度快，储存空间小，最常见的基于哈希的包分类算法是元组空间查找算法（TupleSpaceSearch）[24]，它先将所有规则按照各字段前缀长度进行分类，划分成不同的元组集合，然后为每个元组集合建立一个哈6 希表，再在这些哈希表中进行哈希查找。但基于哈希的算法的缺点是有可能会发生哈希冲突，当产生冲突时性能会出现严重下降，而且基于哈希的算法在处理前缀匹配的时候也不如基于查找树的算法那样灵活。基于空间划分的算法将包分类问题转化为数学几何中多维空间的点定位问题[25-26]，将一个d维的规则R理解为d维空间的一个超立方体，而数据包头H则对应空间中的一个点，若H落入R所代表的超立方体中，则H与R匹配。其中的典型代表算法是HiCuts算法[27]和HyperCuts算法[28]。单维组合分类算法的主要思想是：单独地对数据包每个字段进行匹配，并对每个字段的匹配结果进行合并从而找到最终匹配的规则，这类算法的代表是位向量算法（BitVector）[16,29]，这类算法性能由于受字段数量的影响较少，可以被用于OpenFlow包分类[30]。软件算法和硬件算法之间没有明确的界限，软件算法本身查找速度较慢，需要硬件的支撑，硬件算法也需要软件进行改进。许多文献使用软件和硬件相互结合的方法来提高算法的性能[20-21]。1.2.2OpenFlow研究现状OpenFlow是一种新型网络协议，其设计目的是在不改变现有的网络设备和环境的前提下，使新的网络框架和协议可以在实际网络中进行验证。OpenFlow的设计思路很简单，网络设备（OpenFlow交换机）维护流表，数据包按照流表进行转发，而流表的生成、维护、管理和修改则交由控制器实现。流表中的流表项已经不再是简单的五元组，而是包含网络各层的协议字段，这些字段在OpenFlow的演进过程中也在不断的变化和增多。自2009年OpenFlow的第一个版本发行以来，OpenFlow经历了长时间的演变过程。OpenFlowv1.0是最早的版本，它指定了OpenFlow中流表的格式和工作方式。这个版本已经充分体现了基于OpenFlow交换机、控制器和OpenFlow协议搭建SDN的设计思想和整体架构。其后，OpenFlow又进行了多个版本的演进，OpenFlowv1.1增加了VLAN和MPLS标签，并开始支持多级流表，即提取流表中不同表项的特征，将匹配过程分解成多个步骤，形成流水线处理方式，从而有效降低流表项的记录条数。OpenFlowv1.2改用TLV（Type,Length,Value；类型，长度，值）结构定义匹配字段，一方面使匹配字段更加地灵活，另一方面也节省了一部分的流表空间，另外，这时候的OpenFlow也开始支持多控制器和IPv6。OpenFlowv1.3对OpenFlow的改动较大，与初始时的版本已经完全不同，一方面，它将流表中的字段增多至30多个，另一方面，它在OpenFlow7 的结构上进行了多处改动，比如增加table-miss流表项，重构版本协商能力等。OpenFlowv1.4在OpenFlowv1.3的基础上又进行了一些改动，增加流表同步机制，多个流表可以使用相同的匹配字段，但彼此之间可以执行不同的动作；另外还在控制层面进行了一些改动，增加了一些流表项的删除机制。图1.2简单描述了OpenFlow的演进过程，整个过程主要围绕两个方面：一方面是控制层增强，系统更加灵活，功能更加齐全；另一方面是转发层增强，可匹配的字段更多，动作也更多。OpenFlow的不断演进也带了一些问题，比如各个版本之间并不能完全兼容。本文中主要采用OpenFlowv1.0进行讲解与实验，这主要有两个原因：一方面是因为OpenFlowv1.0是OpenFlow的第一个稳定版本，也是目前使用和支持最广泛的协议版本；另一方面是因为它可以与现有的商业交换芯片兼容，在现实中已经有一些运用，方便我们进行参考和对比。OF1.0OF1.1OF1.2OF1.3OF1.4-基本框架-多流表-IPv6-重构能力协商-流表同步机制-单流表-组表-多控制器-Meter-Bunding消息-IPv4-MPLS和VLAN-辅助连接图1.2OpenFlow标准版本演进图OpenFlow通过流表的方式将传统的网络协议栈扁平化，在一个流表中包含了多个协议字段信息，这使得数据包的分类更加地灵活，但也给数据包分类技术带来了新的挑战：一方面，包分类的匹配字段数量大大增加，传统的交换机和路由器只需要匹配相对固定的目的IP、目的MAC和VLAN等信息即可完成转发，而OpenFlow交换机因为需要匹配流表中的诸多字段，如果不采用特殊的算法加以处理，那么转发性能会大大降低；另一方面，流表的规模也远远大于以往的包分类规则集，单单依靠增加TCAM的容量已经无法解决问题，需要新的解决方案。1.3本文研究内容本文对包分类算法进行了深入的研究，针对OpenFlow网络的特点和现有包分类算法的不足，设计了一种流量自适应的多维度包分类算法，主要贡献如下：（1）为设计出适用于Openflow协议的包分类算法提出了指导性原则。本文首先对包分类问题进行了概述，讲述了包分类问题的出现与演变，给出了包分类的定义，说明了包分类算法的评价指标，还总结出了包分类算法的设计原则。然后，本文详细8 研究了已有的包分类算法，对其进行分类总结，分析其性能和优缺点。最后，本文还分析了OpenFlow网络的特点，找出了OpenFlow包分类和普通的五元组包分类的不同，为改进现有的算法设计出适用于OpenFlow的包分类算法提供了指导性原则。（2）提出了一种适用于OpenFlow多字段特点的包分类算法。该方法基于位向量设计，对每个字段单独进行匹配然后通过位向量进行合并。利用流量自适应思想，不同分类字段可以根据字段实时使用情况进行排序，优先匹配一些常用字段而避免匹配剩余的通配字段来达到提高速度的目的。该方法中不同字段可以采用不同匹配算法，配置更加灵活。（3）在Linux操作系统下模拟实现了本文所提出的算法，并设计实验测试了其性能。本文算法和已有的包分类算法的对比实验表明，本文算法的包分类速度快于已有的包分类算法，提高大约40%。而且本文算法所使用的内存空间相比已有算法，并没有大量增加，在可以接受的范围之内。1.4论文结构论文的章节安排如下：第一章绪论。我们首先分析了包分类算法的研究目的和意义，然后简单介绍了包分类算法和OpenFlow协议的研究现状，最后叙述了本文的主要工作和贡献。第二章数据包分类问题概述。我们首先讲述分类问题的出现与演变；然后阐述了包分类问题的定义；其次介绍了评价包分类算法的三个指标：分类速率，内存占用和可扩展性，最后讲述了包分类算法的设计原则。第三章经典数据包分类算法。我们首先分类总结了各个经典的包分类算法，对它们的实现原理进行了讲解；然后分析了它们各自的性能和应用场合，并进行了比较。第四章OpenFlow数据包分类。我们首先简单介绍了OpenFlow网络，然后详细介绍了OpenFlow流表的包分类以及它的特点：位数多、字段多且匹配方式多样，最后描述了网络中流的局部特性，为设计OpenFlow包分类算法提供了指导性原则。第五章流量自适应的包分类算法。我们介绍了本文所提出的适用于OpenFlow网络的包分类算法。首选介绍了算法的思想，然后从整体上描述了算法的流程和框架，最后介绍了每种匹配方式所采用的算法，包括基于哈希的算法、基于查找树的算法和基于范围树的算法。第六章实验论证与性能分析。我们首先介绍了实验平台的搭建，包括使用Mininet、OpenvSwitch和Floodlight搭建OpenFlow网络和使用ClassBench和FRuG构建9 OpenFlow规则集，然后通过实验对本文算法进行了分析，包括同OpenFlow已有算法和由五元组扩展而来的算法的时间性能和空间性能的比较。10 第2章数据包分类问题概述2.1包分类问题的提出与演变包分类问题由来已久，应用于路由跳转的IP地址查找[31-32]可以看做是最简单的包分类，因为分类字段只有目的IP地址。IP地址查找算法也比较简单，由于IP地址的匹配方式是最长前缀匹配，所以一般采用基于查找树（Trie）的算法。随着互联网技术的不断发展，人们对互联网的要求不再仅限于数据传输，而是希望互联网可以提供多样化的网络服务，而许多网络服务，都需要用到数据包分类技术。例如，防火墙需要数据包分类技术对数据包进行过滤，QoS需要数据包分类技术为指定的重要网络业务提高服务质量，入侵检测系统（IntrusionDetectionSystem，IDS）[33]需要依靠数据包分类技术来检测检测数据流来采取反应措施。这时的数据包分类已经不在单单依靠IP地址，而是更多的网络协议字段，但一般不超过5个，大部分是五元组，包分类算法也更加的复杂多样。随着网络的进一步发展，人们对数据包分类技术也有了更高的要求。例如，业务感知网络[34]要求网络对网络数据流中的业务进行感知、分析、决策和控制，尤其是针对视频和语音等流媒体业务；数据中心网络（DataCenterNetwork）[35]要求网络有灵活的拓扑和链路容量控制，不同服务间的流量可以进行隔离；软件定义网络要求网络进行虚拟化和可编程化，这些都需要用到更加细粒度的数据包分类。因此，这时候的数据包分类不再局限于五元组等少数几个字段，而是扩展到网络各层的十多个字段，最多甚至可以达到包括IPv6协议字段在内的三十多个字段[36-38]，这给包分类算法带来了极大的挑战。2.2包分类问题的定义数据包分类就是将网上传输的数据包的包头字段和预定义的规则集中的各个规则进行匹配的过程。包分类问题的描述如下：在规则集S中有n条规则，规则用Ri（0≤i的形式储存，当掩码中的某一位为1（某些厂商规定为0）时，相应的关键字的这一位就被屏蔽，不参与比较，即为通配位。假如一个表项的关键字是1011100，掩码是0001111，那么此表项代表的前缀为101****，范围是[1010000,1011111]。这种方式使得TCAM的表项非常灵活，不仅可以进行精确匹配，还可以进行前缀匹配和范围匹配。TCAM的查找速度很快，因为表TCAM内所有表项都可以并行访问，即假如其中有100条规则，那么TCAM一次就能够完成数据包和这100条规则的匹配，而不用先匹配第一条，匹配失败后再匹配第二条，再匹配第三条。因此查找速度不受表项空间数据大小影响，一个时钟周期内就可以完成一次查找。TCAM具有实现简单、查找速度快的优点，同时它也具有一些很明显的缺点：1)相比其它的方法，TCAM要更加的昂贵，而且TCAM的容量要更加的小（一条TCAM表项相当于五六条DRAM表项）。当规则的长度较长时，这两个缺点愈发的明显。2)并行匹配的查找方式虽然增加了TCAM的查找速度，但是也大大增加了TCAM的功耗。实际上不是每次都需要比较所有的表项，所以有许多的操作都是浪费的。3)出于优先级上的考虑，TCAM中前缀长的表项要保存在前缀短的表项之前，当规则集较为复杂时，TCAM的更新会变得很困难。基于TCAM的OpenFlow芯片已被一些厂商研究出来并投入使用，但一般使用在规则集较小的实验场合。由于TCAM本身的局限性，目前市场上容量最大的TCAM也无法满足OpenFlow的需求。3.2基于数据结构的算法3.2.1基于查找树的算法16 查找树（Trie）是一种经常应用在字符串储存和IP地址查找上的数据结构，在数据包分类中，最简单的基于查找树的算法分层查找树（HierarchicalTrie）[17]就是在每一个维度上都建立一个查找树。分层查找树和所有查找树一样，由递归方式生成，算法的基本思想如下：假设规则集S中的规则至多含有k个字段（每个字段也被称为一个维度），首先在第一维上构建一棵二叉查找树，方法是从根结点开始，根据规则域值前缀长度，依次由高位到低位建立二叉树的分枝，称其为F1-Trie，F1-Trie的结点代表各个规则在F1字段上的部分，它可以是一个前缀或一个精确的值，在含有后续规则的结点处可以构建（k-1）字段的分层查找树，每个维度的构造规则同第一维，这样就可以递归生成一个k维的分层查找树。由表3.1的规则集得出的二维分层查找树如图3.1所示，其中灰色结点代表某一规则的前缀，白色结点代表还没找到对应的规则。表3.1查找树规则集规则F1字段F2字段R111001*R211*1**R310*11*R40**01*011F1-Trie000011F2-Trie111R2R4R3R1图3.1二维分层查找树17 当数据包进入分类引擎后，分层查找树算法首先根据包头在第一维上的值H1在F1-Trie上进行遍历，找到一条最佳匹配的前缀，然后根据这个前缀所在的叶子结点去F2-Trie上进行遍历，以此类推，找到最终的最佳匹配规则。本算法直接由查找树向多维度扩展而来，实现简单，但算法的性能会受到回溯时间的影响，尤其是随着维度的增多，算法回溯时间会大大增加，导致性能严重下降。另外，算法也无法直接支持范围匹配。集合归并查找树（Set-pruningTrie）是对分层查找树的优化，它通过对分层查找树中的某些结点进行多次复制来达到避免回溯的目的，从而提高查找速度。其算法思想是：如果在一个字段中存在着指向下一个字段的规则的结点，但是这个结点不是叶子结点，那么就将这个结点指向下一个字段的指针复制到它的子结点中，这样就避免了子结点匹配不成功后要回溯父结点的情况。如图3.2所示，由于结点A不是叶子结点但含有规则前缀，所以从结点A引出的F2-Trie定义为F2-A-Trie，全部被复制到叶子结点B引出的F2-B-Trie上，因此对B引出的F2-B-Trie的搜索，也就包含了对F2-B-Trie和F2-A-Trie的搜索，无需回溯遍历。可以看出，集合归并查找树对查找速度的提升是以牺牲空间为代价的，每个结点不仅要储存自身的信息，还要储存其祖先结点的信息，多次结点的复制使得空间性能下降，当维度增多时，算法性能下降尤其明显。011F1-Trie0A0B00111F2-Trie111R2R2R4R3R1图3.2集合归并查找树网格查找树（GridofTrie）[23]是分层查找树的另外一种优化算法，它不复制结点，18 而是采用指针的方式来解决回溯问题，兼顾了时间和空间性能。如图3.3是根据表3.1建立的网格查找树。网格查找树算法不再复制结点，仅仅是增加指针，额外的开销较小。011F1-Trie000011F2-Trie111R2R4R3R1图3.3网格查找树3.2.2基于哈希的算法哈希算法是利用哈希表（HashTable）来进行快速查找的数据结构，它可以进行快速的查找，但是它只能应用于精确匹配，无法直接用于前缀匹配和范围匹配，因此需要进行一些优化。最经典的基于哈希的包分类算法是元组空间查找算法（TupleSpaceSearch，TSS）[24]，在TSS算法中，将相同字段前缀长度相同的规则称为同一个元组，所有元组组成元组空间，为每个元组建立一个哈希表。由于每个元组在每个字段上的位长度是固定且已知的,所以可以将这些比特串连接(Concatenation)起来组成哈希表中的关键字，通过该关键字就可以找到与该元组对应的规则集合。表3.2是由4位的源IP地址（SA）、目的IP地址（DA）、源端口号（SP）、目的端口号（DP）和16位的协议（PR）组成的五元组的规则集，其中源IP地址和目的IP地址为前缀匹配，源端口号和目的端口号为范围匹配，协议字段为精确匹配。五个字段值的不同长度组成了不同的元组。在表2.3的元组一列中，我们可以看到不同的元组，其中五个字段值的长度都相同的两条规则属于同一元组，如R1和R5，IP地址的元组由前缀长度决定，端口号的元组由嵌套层数决定，协议字段为确定值时元组为1，否则为0。19 表3.2元组空间查找算法规则SADASPDPPR元组R101**001*20-15TCP[1,3,2,0,1]R201**0***0-150-4TCP[2,1,0,1,1]R3011000110-45-15*[4,4,1,1,0]R41100****5-152ICMP[4,0,1,2,1]R51***110*20-15TCP[1,3,2,0,0]由表2.3中可以看出样例规则集中的元组非常复杂，在真实的规则集终将更加的复杂，每个元组都要建立一个哈希表，元组的种类过多会产生很多个哈希表，降低空间和时间性能。一种对元组空间查找算法的优化是剪枝元组空间算法（PrunedTupleSpaceSearch），它首先在个别字段上进行查找以得到一个候选元组子集，从而缩小查找的范围，然后再建立元组，达到候选元组个数和修剪步数之间的平衡，优化算法的性能。3.3基于空间划分的算法基于空间划分的算法将包分类问题转化为数学几何中多维空间的点定位问题，将一个d维的规则R理解为d维空间的一个超立方体，而数据包头H则对应空间中的一个点，若H落入R所代表的超立方体中，则H与R匹配。早期较为经典的基于空间划分的算法是智能层次切割（HierarchicalIntelligentCuttings，HiCuts）算法[27]。HiCuts算法首先将所有字段都转化为范围匹配，采用多级空间分解的方式在每一个字段上把规则集划分为一个个较小的规则子集，然后根据规则子集的划分建立一棵决策树，规则字集存放在决策树的叶子结点上，而在内部结点上则存储分类导向信息。这样整个算法就结合了决策树和线性查找两种分类方式，当数据包到来之后，首先沿着决策树遍历至某一叶子结点，然后在和该叶子结点上的规则进行线性匹配。图3.4是根据表3.3中的规则集使用HiCuts算法进行切割的结果，首先在F1字段上划分，然后对多于2个规则的结点再根据F2字段进行划分。HiCuts算法的优点是在维度较低和规则分布较均匀的情况下，算法占用内存空间较小，规则集更新比较容易；缺点是算法需要大量预处理时间，维度较多的时候情况较复杂，字段的切割需要多重考虑，如果规则分布不均匀也会影响算法的性能。20 表3.3智能层次切割算法规则集规则F1F2R100*00*R20**01*R31**0**R40**1**R51**1**F21118*8110R4R5101沿F1字段切割100R2R3R3011R22*8R4R5R5010R3001R1000沿F2字段切割000010100110R1RF1R42001011101111（a）（b）图3.4智能层次切割算法举例多决策树(HyperCuts)算法[28]通过两个方面对HiCuts算法进行了改进：一方面，HyperCuts算法通过把一些优先级较低的规则如通配规则或前缀较短的规则存储在根结点中来避免叶子结点中含有较多的重复规则；另一方面，HyperCuts算法通过对多个字段同时切割来减少切割次数，从而降低决策树的深度，提高查找速度。对表3.3中的规则集使用HyperCuts算法建立的决策树如图3.5所示，由图中可以看出，HyperCuts算法最小化了决策树的高度，同样也限制叶结点上规则最大数目，使算法得时间性能和空间性能都得到了提高。但HyperCuts算法也存在着一些缺点：内部结点信息更多，需要位数也多，这可能增加内部结点访问内存的次数，另外，HyperCuts算法也和规则集的分布有关，最坏情况下性能下降较多。基于区间划分的四叉树算法AQT（Area-BasedQuadtree）[39]是一种2-D包分类方法[40]，使用四叉树对二维规则集表示的空间进行递归描述，即把一个正方形分成四个相同的小正方形区域，再把含有规则数较多的小正方形再次划分，一直递归下去，直到每个小正方形区域所含有的规则都不超过一个。每个小正方形称为一个子空间，而21 四个小正方形区域组成的大正方形则称为父空间。若一条规则跨越了子空间，则把其存放在父空间之中，和一个子空间相交的所有规则组成的几何称为这个空间的交叉过滤集（CrossingFilterSet，CFS）。在构建AQT时，先计算父空间的CFS并保存在其中，再把这些规则删除，然后递归调用子空间。如图3.6是根据表3.3中规则集构建的AQT。8*8R1R3R4R5R2图3.5HyperCuts算法决策树R5R2R3R4R1图3.6AQT算法决策树FIS树（FatInvertedTree）[41]是通过对线段树（SegmentTree）进行改进从而达到时间性能与空间性能相对平衡的一种包分类算法。线段树是一种通过对区间进行评分来减小查找范围的二叉搜索树，FIS树通过两方面的改进使其更适合于包分类：一方面压缩树的深度使其变胖，这也是每一层的结点或者每个结点内的规则变多；另一方面，树内的指针由子结点指向父结点，将树颠倒了过来。3.4基于维度分解的算法基于维度分解的算法的基本思想是将多维的分类匹配问题分解成多个较简单一维匹配的问题，对数据包的匹配在各个字段上分别执行。基于维度分解的典型算法有22 递归流分类（RecursiveFlowClassification，RFC）算法[42]、交叉积（Crossproducting）算法[43]和位向量（BitVector，BV）算法[16,29]。RFC算法是一种通过对规则集多步映射并进行优化来达到快速分类的目的的算法。RFC算法的主要思想是把包分类视为把s位的包头协议信息映射成T位的规则编号(classID)，即把2S个不同的包头映射为2T条不同的规则（其中T=logN,T<