包分类算法

包分类算法主要内容包分类问题的产生背景典型的包分类算法Bitmap-RFC算法TIC算法参考文献D.E.Taylor.Survey&TaxonomyofPacketClassificationTechniques.TechnicalReport,DepartmentofComputerScience&Engineering,WashingtonUniversityinSaintLouis,May2004.D.Liu,B.Hua,X.Hu,X.Tang.High-performancePacketClassificationAlgorithmforMany-coreandMultithreadedNetworkProcessor.InProceedingsofCASES2006.H.Cheng,Z.Chen,B.Hua,X.Tang.ScalablePacketClassificationUsingInterpreting:ACross-platformMulti-coreSolution.InProceedingsofPPoPP2008.1.IP分类问题（1）术语：包头H是有K个域的实体，每个域表示成H[i]，每个域为一个比特串。过滤规则F具有K个域，表示为F[i]。与每个F[i]相关联的有一个匹配方式，可以是：精确匹配：F[i]用一个值来表示，若H[i]=F[i]，称H[i]与F[i]精确匹配。前缀匹配：F[i]通过一个前缀来指定，若H[i]与F[i]表示的前缀匹配，称H[i]与F[i]前缀匹配。范围匹配：F[i]通过一个范围指定，即F[i]=[val1,val2]，若满足val1≤H[i]≤val2，称H[i]与F[i]范围匹配。过滤规则F与包头H匹配，当且仅当H的每个域H[i]都与F相应的域F[i]匹配。IP分类问题（2）定义：给定一个具有N条过滤规则的规则库Fdat，与每条规则f相联系有一个代价函数，记为cost(f)，给定一个包头H，最佳规则匹配问题为在Fdat中查找满足下列条件的过滤规则fbest：fbest是H的一个匹配过滤规则；在Fdat中不存在其它的过滤规则f，f与H匹配且满足cost(f)cost(fbest)。IP分类问题是最佳过滤规则匹配问题的一个实例。IP分类问题中与每条规则相联系有一个ACTION，用来表示对满足相应过滤规则的包的处理动作。IP分类问题（3）算法的评价指标：速度，这是评价IP分类算法的最重要标准。算法时间复杂度的3种评价标准：最坏情况：对一个包进行IP分类查找的最长可能时间。平均情况：在随机情况下，对一个包进行分类查找的平均时间。统计情况：在符合某种预先指定的包或过滤规则匹配率的分布下，对一个包进行分类查找的平均时间。占用内存，包括规则库本身以及为高速查找而建立的各种数据结构占用的内存。更新代价：完全更新：重新建立全部的查找数据结构。增量更新：在查找数据结构中增加或删除一条过滤规则。重组或平衡：在适当的时间重组数据结构使其恢复原来的效率。IP分类问题（4）从数学上看，IP分类问题与多维空间中的点定位问题相似，但更加复杂。基本的解决思路：根据数据流的分布特点以及规则集中规则的分布特点设计分类算法。将高维问题转化为二维乃至一维的问题，降低问题的复杂度。2.典型的IP分类算法以Grid-of-Tries为代表的基于Trie树的算法以比特矢量为代表的算法以HiCuts为代表的决策树算法以RFC为代表的算法2.1HierarcicalTrieABCH001DR4R1EGR2R5FR6IR30000111F1目的地址Trie树F2源地址Trie树查找路径规则F1（目的地址）F2（源地址）R1R2R3R4R5R600*0*1*00*0**00*01*0*0*1*1*优点：算法简单、直接、便于硬件实现。缺点：回溯时间长，对规则维数的扩展性差，不能直接支持范围匹配。2.2Set-PruningTrieABCH001DR4R1EGR2R5FR6IR30000111F1目的地址Trie树F2源地址Trie树查找路径R5R211R61ABCH001DR4R1EGR2R5FR6IR30000111F1目的地址Trie树F2源地址Trie树查找路径优点：不需要回溯，查找时间短缺点：空间复杂度高，不易更新。2.3Grid-of-TrieABCH001DR4R1EGR2R5FR6IR30000111F1目的地址Trie树F2源地址Trie树查找路径111ABCH001DR4R1EGR2R5FR6IR30000111F1目的地址Trie树F2源地址Trie树查找路径R5R211R61优点：内存空间小缺点：更新困难，在需要更新时最好重建这棵树。多维IP分类假定所有过滤规则的协议只取三个值：TCP、UDP和通配符（*），对于取值为通配符的过滤规则，将一条规则重复3次，分别对应TCP、UDP和所有其它情况（OTHER）。根据目的端口和源端口的不同组合建立4个哈希表，分别对应（目的端口，源端口）二元组为（DstPort，*）、（DetPort，SrcPort）、（*，SrcPort）和（*，*）的情况。每个哈希表项为一棵GridofTries树，哈希表的索引为相应的端口地址和协议号的某种组合（或函数）。查找时，同时查找4个哈希表，分别用协议号和端口号的某种组合（或函数）作为索引，找到相应的GridofTries树；然后再根据GridofTries树的查找方法找到最小代价的过滤规则；取所有哈希表中的最好结果即为最佳匹配的规则。2.4比特矢量算法001F1F2010011110111001001001001100101100000011011100规则F1（目的地址）F2（源地址）R1R2R3R4R5R600*0*1*00*0**00*01*0*0*1*1*缺点：算法运行时间随N的增大而线性增长，因而可扩展性差。2.5HiCuts算法000001111010100101110011R6R5R3R1111110101100011010001000R2.HF1F28*8,X,42*8,Y,2R2R5R3R6R3R6R1R2R5沿X(F1)方向分割沿Y(F2)方向分割优点：占用内存空间小，规则集更新容易，直接支持范围匹配。缺点：预处理时间较长，分类速度比一些快速包分类算法低。2.6RecursiveFlowClassification（RFC）S为包头中d个域形成的比特串的长度，若S位比特串的每一种可能取值对应一个等价类（用eqID表示），则分类问题可看成是根据包头中S位比特串确定其对应的eqID的问题。当S很大时，从S位比特串直接映射到eqID需要消耗巨大的内存空间。RFC的基本思想是将一次映射转变为多阶段映射，其结果是将一个较大的集合映射成若干个较小的集合，达到减小内存需求的目的。每一阶段映射称为一次缩减（reduction），由多阶段映射构建的数据结构称为缩减树。一个三维规则集例子rule#F1F2R1R2R3R400100101****010100100***F3011011******ACTIONpermitdenypermitpermit012index012...eqIDCBM01000111012001107eqIDChunk0001012...eqIDCBM01000110012011107Chunk1001012...eqIDCBM010011111107Chunk200010index0...8910211eqIDeqIDCBM01000110012010100012...15331617Phase0Phase1P1P2P3eqID0eqID1eqID2OIndexcross-productingtable30011032阶段RFC缩减树域的可能值比特串：用于指示哪些规则匹配该域CBM位串标识由eqID0-eqID2的值级联而成由eqID0-eqID2指示的CBM位串逐位相与而成RFC的特点RFC是目前除硬件方案之外较快的多维包分类算法。易于并行处理处于同一阶段的预处理表或交叉乘积表可被并行地索引；处于不同阶段的表也可被并行地索引。这些表各自独立，可分布于不同的存储单元中。RFC构建的交叉乘积表占用内存空间较多，存储空间消耗随规则集规模增大而迅速增大。3.Bitmap-RFC…001020008910111233…151617Cross-productingTableACompactTableElementArray100000000111100010010203Bitmap000001010011100101BitmapRFC的数据结构16BitBitmapElement216BitBitmap(Ifexisting)Element1Element3Element4………………OrNullPointer(Ifexisting)Element1Element2Element3…………CompactTableAccessoryTable16Bit…………LSBMSBOneentry查找OIndex/sizeofsub-CPT001001010...101010element1element2......otherentryotherentryquotientresidueCompactTableElement......ElementAccessoryTableLSBMSBCompacttable的数据结构设计考虑Elementarray的单元宽度：16比特Bitmapstring长度：32比特的倍数Compacttable的表项：由bitmapstring和elementarray组成，长度不超过16个长字。算法优化实现内存压缩指令选择：POP_COUNT，分支指令数据分配：预处理表及各阶段CCPT表的存放任务划分：multi-processing和context-pipelining延迟隐藏实验设置对IPv4数据包进行四维分类，应用三阶段的RFC和Bitmap-RFC：四个域：源IP地址，目的IP地址，源端口，目的端口，其中IP地址分为低16位和高16位两部分。第一个阶段为6个预处理表，第二阶段为2个交叉乘积表，第三阶段为1个交叉乘积表。源IP低16源IP高16目的IP低16目的IP高16源端口目的端口CPTXCPTYCPTZCCPTX’CCPTY’CCPTZ’实验设置（续）三组规则集（根据现有规则集的特征随机生成），每条规则定义4个域，IP地址采用CIDR前缀表示，端口采用数据范围表示：CL#1:1000条规则CL#2:2000条规则CL#3:3000条规则测试数据包：使用49字节（20字节TCP头+20字节IP头+9字节PPP头)的最小长度数据包作为输入，OC-192线速要求25.5Mpps的分类速度。内存需求比较Num.ofRulesMemoryRequirementofCPTandCCPT(MB)TotalMemoryRequirement(MB)XX’YY’ZZ’RFCBitmap-RFC5,70059.218.525.88.164.116.0149.943.48,05080.725.264.320.1127.739.9273.586.012K106.533.3106.333.2284.971.2498.6138.517K191.059.7185.057.8570.7178.4947.6296.7X,Y,Z:RFC的阶段1(X,Y)和阶段2(Z)交叉乘积表(CPT)X’,Y’,Z’:Bitmap-RFC的阶段1(X’,Y’)和阶段2(Z’)压缩的交叉乘积表(CCPT)不同数据分配下的包分类速率1ME2MEs4MEs8MEs1-SRAM6.499.659.639.5762-SRAM6.5012.9418.6318.153-SRAM6.5012.