资源描述：
《包分类算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1SX1416020申慕惠专题：包分类算法(PacketClassification)2主要内容：包分类定义包分类技术的应用领域包分类算法的评价指标包分类算法的分类包分类算法仿真工具介绍包分类数据包分类就是根据网络上传输的数据包的包头信息,将数据包按照一定规则进行分类包头信息P：d元组(p1,p2,...,pd)。经典五元组(目的地址,源地址,协议,目的端口,源端口）d维包分类问题就是在分类器中找到与P匹配的具有最高优先级的规则Rbest(最佳匹配)。分类器(Classifier,也称为规则集),含有N条
2、规则(RuleorFilter)规则。每条规则R[j](1≤j≤N),由三部分组成:--R[filter]：d元组--R[priority]--R[action]举例：规则匹配结果匹配条件优先级匹配处理源IP地址目的IP地址源端口号目的端口号协议类型202.193.10.*202.193.20.*[0,65535]20,21UDP1拒绝202.192.31.*162.120.*.*[0,65535]>1023TCP2允许118.196.21.*155.20.80.*[0,65535]>1023TCP3允许
3、源地址目标地址源端口号目标端口号协议类型动作202.192.31.2162.120.3.45[0,65535]6789TCPR2,允许118.196.21.*155.20.80.*[0,65535]>1023TCPR3,允许规则R1R2R3最佳匹配：在实际应用中，一个数据包可能会匹配多个规则，因此需要在所有匹配的规则中找到优先级最高的一条规则，最高优先级别的规则称为最佳规则Rbest。满足以下条件：•Rbest是与数据包P匹配的规则•在规则库f中不存在其它的规则R，R与P匹配并且满足Rbest[prior
4、ity]>R[priority]，Rbest是在所有与P匹配的规则中，优先级最高，代价函数最低的规则匹配方式：精确匹配：数据包头的字段和规则的对应字段完全相等。即P[j]=R[Fj]，通常用于协议类型字段的匹配前缀匹配：R[Fj]通过一个前缀来指定，若H[i]与R[Fj]表示的前缀匹配，称H[i]与R[Fj]前缀匹配范围匹配：数据包头字段P[j]的值在相应规则域R[Fj]规定范围之内。若R[Fj]=[val1,val2]，满足val1≤P[j]≤val2，称H[j]与R[Fj]范围匹配，通常用于端口号字段
5、的匹配包分类技术的应用领域安全应用–在edge、core路由器中异常包的丢弃，rate控制；在防火墙中实现包的过滤QoS–把包映射到不同的服务VPNs–ISP路由器提供多个VPNs，每一个VPNs需要一个分类器包分类算法的评价指标速度--最坏情况：对一个数据包进行分类查找的最长可能时间--平均情况：在随机情况下，对一个包进行分类查找的平均时间--统计情况：在符合某种预先指定的包或过滤规则匹配率的分布下，对一个包进行分类查找的平均时间占用内存：包括规则库本身以及为高速查找而建立的各种数据结构占用的内存。更新
6、代价：--完全更新：重新建立全部的查找数据结构--增量更新：在查收数据结构中增加或删除一条过滤规则--重组或平衡：在适当的时间重组数据结构使其恢复原来的效率包分类算法的评价指标可扩展性①在分类器的规则个数上具有可扩展性，指分类器的规则个数N可以很大，而不是限定在固定的规则数目上。②在分类的维数上具有可扩展性，指可以包含任意多个分类的字段，而不是限定在固定的某几个字段上。③在分类的层次上具有可扩展性，指分类可包含多层次的分类，理想的算法应该是能够容许匹配任意层内的字段，包括数据链路层、网络层、传输层，在一些
7、特殊的情况下可能要包括应用层的内容。最坏情况下的性能平均的性能分析有时不能完全真实反映分类的性能。包分类算法：穷举分类算法基于Trie分割算法几何区域分割算法元组空间分割算法维度分解算法穷举分类算法主要思想–将待分类的数据包依次和分类规则库内的所有规则进行比较。典型算法–线性查找算法–大规模并行查找算法-基于TCAM硬件穷举分类算法之线性查找算法算法思想–按优先级降序排列分类规则链表–一个数据包顺序地与每个规则进行比较直到找到第一个匹配的规则。–由于规则已经事先按照优先级降序排列，所以第一个匹配的规则即为
8、最佳匹配规则算法复杂度–包分类阶段的空间复杂度为O(N)，时间复杂度为O(N)特点–包分类的时间随着规则数目的增加呈线性增加，适用于规则数目比较少的情况穷举分类算法之大规模并行查找算法TCAM(TernarycontentAddressMemory)标准TCAM单元穷举分类算法之大规模并行查找算法TCAM(TernarycontentAddressMemory)将规则集划分成每个子集只有一条规则优点：时间复杂度O(1),空间复
