包分类算法ppt课件.ppt

《包分类算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《包分类算法ppt课件.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、包分类算法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值主要内容p包分类问题的产生背景p典型的包分类算法pBitmap-RFC算法pTIC算法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值参考文献pD.E.Taylor.Survey&Taxonomy of Packet Classification Techniques.Technical Report,Department of Computer Science&Engineering,

2、Washington University in Saint Louis,May 2004.pD.Liu,B.Hua,X.Hu,X.Tang.High-performance Packet Classification Algorithm for Many-core and Multithreaded Network Processor.In Proceedings of CASES 2006.pH.Cheng,Z.Chen,B.Hua,X.Tang.Scalable Packet Classification Using Interpreting:A Cross-platform Multi

3、-core Solution.In Proceedings of PPoPP 2008.资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值1.IP分类问题（1）p术语：n包头H是有K个域的实体，每个域表示成Hi，每个域为一个比特串。n过滤规则F具有K个域，表示为Fi。n与每个Fi相关联的有一个匹配方式，可以是：p精确匹配：Fi用一个值来表示，若Hi=Fi，称Hi与Fi精确匹配。p前缀匹配：Fi通过一个前缀来指定，若Hi与Fi表示的前缀匹配，称Hi与Fi前缀匹配。p范围匹配：Fi通过一个范围指定，即Fi=val1,val2

4、，若满足val1 Hi val2，称Hi与Fi范围匹配。n过滤规则F与包头H匹配，当且仅当H的每个域Hi都与F相应的域Fi匹配。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值IP分类问题（2）p定义：n给定一个具有N条过滤规则的规则库Fdat，与每条规则f相联系有一个代价函数，记为cost(f)，给定一个包头H，最佳规则匹配问题为在Fdat中查找满足下列条件的过滤规则fbest：pfbest是H的一个匹配过滤规则；p在Fdat中不存在其它的过滤规则f，f与H匹配且满足cost(f)cost(fbest)。pIP分类问

5、题是最佳过滤规则匹配问题的一个实例。pIP分类问题中与每条规则相联系有一个ACTION，用来表示对满足相应过滤规则的包的处理动作。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值IP分类问题（3）p算法的评价指标：n速度，这是评价IP分类算法的最重要标准。算法时间复杂度的3种评价标准：p最坏情况：对一个包进行IP分类查找的最长可能时间。p平均情况：在随机情况下，对一个包进行分类查找的平均时间。p统计情况：在符合某种预先指定的包或过滤规则匹配率的分布下，对一个包进行分类查找的平均时间。n占用内存，包括规则库本身以及为高速

6、查找而建立的各种数据结构占用的内存。n更新代价：p完全更新：重新建立全部的查找数据结构。p增量更新：在查找数据结构中增加或删除一条过滤规则。p重组或平衡：在适当的时间重组数据结构使其恢复原来的效率。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值IP分类问题（4）p从数学上看，IP分类问题与多维空间中的点定位问题相似，但更加复杂。p基本的解决思路：n根据数据流的分布特点以及规则集中规则的分布特点设计分类算法。n将高维问题转化为二维乃至一维的问题，降低问题的复杂度。资金是运动的价值，资金的价值是随时间变化而变化的，是时间

7、的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.典型的IP分类算法p以Grid-of-Tries为代表的基于Trie树的算法p以比特矢量为代表的算法p以HiCuts为代表的决策树算法p以RFC为代表的算法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.1 Hierarcical Trie优点：算法简单、直接、便于硬件实现。缺点：回溯时间长，对规则维数的扩展性差，不能直接支持范围匹配。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有

8、资金的时间价值2.2 Set-Pruning Trie优点：不需要回溯，查找时间短缺点：空间复杂度高，不易更新。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.3 Grid-of-Trie优点：内存空间小缺点：更新困难，在需要更新时最好重建这棵树。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值多维IP分类p假定所有过滤规则的协议只取三个值：TCP、UDP和通配符（*），对于取值为通配符的过滤规则，将一条规则重复3次，分别对应TCP、UDP

9、和所有其它情况（OTHER）。p根据目的端口和源端口的不同组合建立4个哈希表，分别对应（目的端口，源端口）二元组为（DstPort，*）、（DetPort，SrcPort）、（*，SrcPort）和（*，*）的情况。p每个哈希表项为一棵Grid of Tries树，哈希表的索引为相应的端口地址和协议号的某种组合（或函数）。p查找时，同时查找4个哈希表，分别用协议号和端口号的某种组合（或函数）作为索引，找到相应的Grid of Tries树；然后再根据Grid of Tries树的查找方法找到最小代价的过滤规则；取所有哈希表中的最好结果即为最佳匹配的规则。资金是运动的价值，资金的价值是随时间变化

10、而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.4 比特矢量算法缺点：算法运行时间随N的增大而线性增长，因而可扩展性差。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.5 HiCuts算法优点：占用内存空间小，规则集更新容易，直接支持范围匹配。缺点：预处理时间较长，分类速度比一些快速包分类算法低。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.6 Recursive Flow Classifica

11、tion（RFC）pS为包头中d个域形成的比特串的长度，若S位比特串的每一种可能取值对应一个等价类（用eqID表示），则分类问题可看成是根据包头中S位比特串确定其对应的eqID的问题。p当S很大时，从S位比特串直接映射到eqID需要消耗巨大的内存空间。pRFC的基本思想是将一次映射转变为多阶段映射，其结果是将一个较大的集合映射成若干个较小的集合，达到减小内存需求的目的。p每一阶段映射称为一次缩减（reduction），由多阶段映射构建的数据结构称为缩减树。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值一个三维规则集例

12、子资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值012index012.eqIDCBM01000111012001107eqIDChunk0001012.eqIDCBM01000110012011107Chunk1001012.eqIDCBM010011111107Chunk200010index0.8910211eqIDeqIDCBM01000110012010100012.15331617Phase 0Phase 1P1P2P3eqID0eqID1eqID2OIndexcross-producting table

13、30011032阶段RFC缩减树域的可能值比特串：用于指示哪些规则匹配该域CBM位串标识由eqID0-eqID2的值级联而成由 eqID0-eqID2指示的CBM位串逐位相与而成资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值RFC的特点pRFC是目前除硬件方案之外较快的多维包分类算法。p易于并行处理n处于同一阶段的预处理表或交叉乘积表可被并行地索引；n处于不同阶段的表也可被并行地索引。n这些表各自独立，可分布于不同的存储单元中。pRFC构建的交叉乘积表占用内存空间较多，存储空间消耗随规则集规模增大而迅速增大。资金是运

14、动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值3.Bitmap-RFC资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 Bitmap RFC的数据结构Oneentry资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值查找资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值Compact table的数据结构

15、设计考虑pElement array的单元宽度：16比特pBitmap string长度：32比特的倍数pCompact table的表项：由bitmap string和element array组成，长度不超过16个长字。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值算法优化实现p内存压缩p指令选择：POP_COUNT，分支指令p数据分配：预处理表及各阶段CCPT表的存放p任务划分：multi-processing和context-pipeliningp延迟隐藏资金是运动的价值，资金的价值是随时间变化而变化的，是时

16、间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值实验设置p对IPv4数据包进行四维分类，应用三阶段的RFC和Bitmap-RFC：n四个域：源IP地址，目的IP地址，源端口，目的端口，其中IP地址分为低16位和高16位两部分。n第一个阶段为6个预处理表，第二阶段为2个交叉乘积表，第三阶段为1个交叉乘积表。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值实验设置（续）p三组规则集（根据现有规则集的特征随机生成），每条规则定义4个域，IP地址采用CIDR前缀表示，端口采用数据范围表示：nCL#1:10

17、00条规则nCL#2:2000条规则nCL#3:3000条规则p测试数据包：使用49字节（20字节TCP头+20字节IP头+9字节PPP头)的最小长度数据包作为输入，OC-192线速要求25.5Mpps的分类速度。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值内存需求比较Num.of RulesMemory Requirement of CPT and CCPT(MB)Total Memory Requirement(MB)XXYYZZRFCBitmap-RFC5,70059.218.525.88.164.116.0

18、149.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.7pX,Y,Z:RFC的阶段1(X,Y)和阶段2(Z)交叉乘积表(CPT)pX,Y,Z:Bitmap-RFC的阶段1(X,Y)和阶段2(Z)压缩的交叉乘积表(CCPT)资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值不同数据分配下的包分类速率1 ME2 MEs4 ME

19、s8 MEs1-SRAM6.499.659.639.5762-SRAM6.5012.9418.6318.153-SRAM6.5012.9920.4020.104-SRAM6.5412.8525.6533.35Hybrid-17.0312.6612.6612.63Hybrid-27.13 12.8212.8012.78资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值相对加速比p实验使用最坏情况下的最小数据包作为输入，即每个包都要二次访存。p使用32个线程可以达到25.65Mpps，满足线速分类的要求。p相对加速比接近线性

20、。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值支持OC-192线速所需的最少线程数ClassifierMinimum Number of Threads Classifying rate(Mpps)Single threadMultithreadsCL#1 201.9726.65CL#2201.9425.74CL#3201.9525.77p这个实验使用随机生成的最小数据包作为输入资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值任务划分pCo

21、ntext-pipelining的两种配置1st ME2nd ME3rd MEConf.16 chunksCCPT X,Y,ZConf.23 chunks3 chunks,CCPT XCCPT Y,Z资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值multi-processing和context-pipelining的分类速度(Mpps)比较2 MEs3MEs4 MEs6 MEsMulti-processing12.8519.3225.6533.73Context-pipelining-1 12.31-Context-

22、pipelining-2-15.41-Context-pipelining-3-22.3733.03Context-pipelining-4-29.88资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值延迟隐藏1 ME2 MEs4 MEs8 MEsOverlapped6.5412.8525.6533.35Without overlapped6.1012.1323.9433.10Improvement7.11%7.15%7.14%0.64%资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，

23、其增值的这部分资金就是原有资金的时间价值4.Two-stage Interpreting based Classification（TIC）p三个观察事实：n在定义IP分类规则时，地址用前缀表示，端口用范围表示。大多数分类算法只适用于前缀查找，对于范围查找，必须先进行范围-前缀转换，增加了规则数量。n前缀查找是访存密集的操作，范围查找是计算密集的操作，将两者分开处理有助于提高查找的效率。n对实际分类规则集统计特性的分析表明，在99.9%的情况下，匹配一对给定的的规则数不大于5。即在匹配了一对给定的IP地址后，进一步要匹配的范围个数非常有限。资金是运动的价值，资金的价值是随时间变化而变化的，是时

24、间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值两阶段的基于解释的包分类（TIC）算法p算法要点：n降维：将匹配一对的过程与匹配其余3个域的过程分开，前者使用适合前缀查找的算法，后者使用适合范围查找的算法。n第二阶段用计算代替查找：在预处理阶段先将匹配一对的规则编成代码，第二阶段通过解释执行找到匹配的规则。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值TIC的设计p第一阶段采用RFC算法，找到匹配一对的规则集，实际上得到的是指向对应该规则集的代码块的地址。p第二阶段查找由端口号和协议组成的范围表

25、达式列表，范围被编码成一系列的ALU指令以进一步减小内存需求。p一个解释器从外部存储器装载代码块到内部存储器（如cache），然后解码并顺序执行指令，以找到一个匹配。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值RFC与TIC的访存次数pRFC需要13次访存，TIC至少需要8次访存。p94.9%的情况下，匹配一对地址的候选范围可以编码成一个64字节的代码块，在x86多核结构上TIC只需访存8次。4阶段RFCTIC资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是

26、原有资金的时间价值指令编码pClassBench定义了5种端口范围：WC（Wildcard）、HI（高端）、LO（低端）、AR（任意范围）和EM（精确匹配），以及两种协议范围：WC和EM。p采用CISC风格的指令，总共需要约552=50种操作符。p三种指令格式，分别带有1个、3个和5个操作数。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值源端口和目的端口的分布p12字节的指令非常少见。p平均指令长度为1.8个长字。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就

27、是原有资金的时间价值范围解释器资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值算法实现平台p两种多核体系结构：nIntel Core 2 Duo：p双核，4MB L2 Cache，64B Cache行大小。p用Linux的Pthread库实现TIC。nIntel IXP2800：p16个微引擎，每个微引擎8个硬件线程，4个SRAM控制器，3个DRAM控制器，640W本地存储器，没有cache，SRAM平均访问延迟150个时钟周期，DRAM平均访问延迟300个时钟周期。p用MicroengineC实现TIC。资金是运动的

28、价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值基于体系结构的设计p空间压缩p数据局部性和对齐p数据分割p延迟隐藏资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值空间压缩p空间压缩的好处：n压缩后的数据结构可放到较高等级的存储器中，减小访存延迟。n压缩可使cache或片上存储器存放更多的数据，减少访存次数。n压缩可提高cache或片上存储器的效率（命中率）。n减少访存次数和访存延迟可显著提高CPU的利用率。p两种压缩技术：n两阶段包分类，消除了范围-前缀转

29、换，抑制了规则数的增长。n采用CISC风格的指令编码进一步压缩范围列表占用的空间。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值RFC和TIC的内存需求pTIC算法最多可比RFC算法节省97%的存储空间。pTIC的分类数据结构基本上可以放入4MB的L2 cache中。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值TIC每个阶段的内存需求p第二阶段的代码块大多只有几百KB，完全可以放入L2 cache中。资金是运动的价值，资金的价值是随时间变

30、化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值数据局部性和对齐pIntel Core 2 Duo（具有两级cache）：n应将数据尽可能放入L2 cache。n为利用空间局部性，代码块长度应等于L2 cache行大小。n为避免cache行伪共享和代码块占据两个cache行，代码块首地址必须对齐。n本文选择代码块大小为64B。pIXP2800（没有cache）：n可使用本地存储器存放要执行的代码块。n32B是合适的代码块长度；p取64字节的代码块在很多情况下不必要。p每次读64字节使得SRAM通道利用率提高，SRAM read FIFO增大，从而导致SRA

31、M访存延迟增大。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值代码块大小对算法速度的影响资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值数据分割（IXP2800）p为避免SRAM控制器成为瓶颈，缩减树和代码块被均匀分布到四个SRAM控制器上。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值延迟隐藏pIXP2800（多线程结构）：n尽可能一次发射多条访存指令，例如第一阶

32、段的phase 0中四个访存操作可以一次发射。n重叠访存操作和ALU计算。pIntel Core 2 Duo（多核结构）：n一个CPU核可用作助手线程填充L2 cache，其它CPU核就可快速地执行。n统一的L2 cache可以被用来减少访存延迟。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值仿真实验设置p两个平台：nIntel Xeon 5160，两个酷睿双核核心封装在一个芯片中，22MB L2 cache，3.0GHz主频，1333MHZ总线。nIntel IXP2800，1.2GHz主频，16个微引擎，4个SR

33、AM控制器，每个SRAM通道64MB。p规则集：n使用ClassBench生成10个规则集，规模为2K和4K。p输入包流：n使用最小长度的包（49字节）作为最坏情况下的输入，OC-192线速要求包的处理速度为25.5Mpps。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值加速比实验的结果p在Intel Xeon 5160上的实验：n平均来说，TIC需要3个CPU核达到10Gbps线速及以上。nTIC和RFC在速度上相当，速度差异在个位数内。n如果RFC的内存空间小于L2 cache的大小，则RFC的分类速度高于TIC

34、，否则TIC的分类速度一般高于RFC。p 在IXP2800上的实验：n平均来说，TIC需要4个微引擎达到10Gbps线速。nRFC运行得比TIC快。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值多核结构上的一些编程经验p必须充分利用应用和多核结构的特征来设计和实现一个高效的网络算法。p压缩数据结构并将它们放到尽可能高的存储器等级中，如SRAM、cache、片上存储器等，以弥合CPU和存储器的速度差异。p选择合适的压缩方法，平衡解压缩的复杂度和空间压缩，使得解压缩不会成为新的性能瓶颈。p要特别关注多核结构中的共享资源，因为这些资源有可能成为算法实现中的性能瓶颈。p使用尽可能多的延迟隐藏技术。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值多核软件设计的几个挑战pCPU与memory的速度差距在增大，如何使CPU充分发挥作用？p数据合理分布到多级存储体系p任务合理分配到不同的计算核p核与核之间高效的通信机制