司机安全培训

《司机安全培训》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、包分类算法主要内容包分类问题的产生背景典型的包分类算法Bitmap-RFC算法TIC算法参考文献D.E.Taylor.Survey&TaxonomyofPacketClassificationTechniques.TechnicalReport,DepartmentofComputerScience&Engineering,WashingtonUniversityinSaintLouis,May2004.D.Liu,B.Hua,X.Hu,X.Tang.High-performancePacketClassificationAlgorithmforMany-c

2、oreandMultithreadedNetworkProcessor.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]相关联的有一个匹配方式，可以是

3、：精确匹配：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，最佳规则匹配问题为在

4、Fdat中查找满足下列条件的过滤规则fbest：fbest是H的一个匹配过滤规则；在Fdat中不存在其它的过滤规则f，f与H匹配且满足cost(f)

5、匹配率的分布下，对一个包进行分类查找的平均时间。占用内存，包括规则库本身以及为高速查找而建立的各种数据结构占用的内存。更新代价：完全更新：重新建立全部的查找数据结构。增量更新：在查找数据结构中增加或删除一条过滤规则。重组或平衡：在适当的时间重组数据结构使其恢复原来的效率。IP分类问题（4）从数学上看，IP分类问题与多维空间中的点定位问题相似，但更加复杂。基本的解决思路：根据数据流的分布特点以及规则集中规则的分布特点设计分类算法。将高维问题转化为二维乃至一维的问题，降低问题的复杂度。2.典型的IP分类算法以Grid-of-Tries为代表的基于Trie树的算法

6、以比特矢量为代表的算法以HiCuts为代表的决策树算法以RFC为代表的算法2.1HierarcicalTrie优点：算法简单、直接、便于硬件实现。缺点：回溯时间长，对规则维数的扩展性差，不能直接支持范围匹配。2.2Set-PruningTrie优点：不需要回溯，查找时间短缺点：空间复杂度高，不易更新。2.3Grid-of-Trie优点：内存空间小缺点：更新困难，在需要更新时最好重建这棵树。多维IP分类假定所有过滤规则的协议只取三个值：TCP、UDP和通配符（*），对于取值为通配符的过滤规则，将一条规则重复3次，分别对应TCP、UDP和所有其它情况（OTHER

7、）。根据目的端口和源端口的不同组合建立4个哈希表，分别对应（目的端口，源端口）二元组为（DstPort，*）、（DetPort，SrcPort）、（*，SrcPort）和（*，*）的情况。每个哈希表项为一棵GridofTries树，哈希表的索引为相应的端口地址和协议号的某种组合（或函数）。查找时，同时查找4个哈希表，分别用协议号和端口号的某种组合（或函数）作为索引，找到相应的GridofTries树；然后再根据GridofTries树的查找方法找到最小代价的过滤规则；取所有哈希表中的最好结果即为最佳匹配的规则。2.4比特矢量算法缺点：算法运行时间随N的增大而

8、线性增长，因而可扩展性差。2.5HiCuts算法优点