包分类算法研究.ppt

包分类 数据包分类就是根据网络上传输的数据包的包头信息,将数据包按照一定规则进行分类 包头信息P：d元组(p1,p2,...,pd)。 经典五元组(目的地址,源地址,协议,目的端口,源端口） d维包分类问题就是在分类器中找到与P匹配的具有最高优先级的规则Rbest(最佳匹配)。 分类器(Classifier,也称为规则集),含有N条规则(Rule orFilter)规则。每条规则R[j](1≤j≤N),由三部分组成: --R[filter]：d元组 --R[priority] --R[action] 举例： 最佳匹配：在实际应用中，一个数据包可能会匹配多个规则，因此需要在所有匹配的规则中找到优先级最高的一条规则，最高优先级别的规则称为最佳规则Rbest。 满足以下条件： ? Rbest是与数据包P匹配的规则 ? 在规则库f中不存在其它的规则R，R与P匹配并且满足Rbest [priority]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]范围匹配，通常用于端口号字段的匹配 包分类技术的应用领域 安全应用 – 在edge、core路由器中异常包的丢弃，rate控制；在防火墙中实现包的过滤 QoS – 把包映射到不同的服务 VPNs – ISP路由器提供多个VPNs，每一个VPNs需要一个分类器 包分类算法的评价指标 包分类算法的评价指标 可扩展性 ① 在分类器的规则个数上具有可扩展性，指分类器的规则个数 N 可以很大，而不是限定在固定的规则数目上。 ② 在分类的维数上具有可扩展性，指可以包含任意多个分类的字段，而不是限定在固定的某几个字段上。 ③ 在分类的层次上具有可扩展性，指分类可包含多层次的分类，理想的算法应该是能够容许匹配任意层内的字段，包括数据链路层、网络层、传输层，在一些特殊的情况下可能要包括应用层的内容。 最坏情况下的性能 平均的性能分析有时不能完全真实反映分类的性能。 包分类算法： 穷举分类算法 基于Trie分割算法 几何区域分割算法 元组空间分割算法 维度分解算法 穷举分类算法 主要思想 – 将待分类的数据包依次和分类规则库内的所有规则进行比较。 典型算法 – 线性查找算法 – 大规模并行查找算法-基于TCAM硬件 穷举分类算法之线性查找算法 算法思想 – 按优先级降序排列分类规则链表 – 一个数据包顺序地与每个规则进行比较直到找到第一个匹配的规则。 – 由于规则已经事先按照优先级降序排列，所以第一个匹配的规则即为最佳匹配规则 算法复杂度 – 包分类阶段的空间复杂度为O(N)，时间复杂度为O(N) 特点 – 包分类的时间随着规则数目的增加呈线性增加，适用于规则数目比较少的情况 穷举分类算法之大规模并行查找算法 TCAM(Ternary content Address Memory) 穷举分类算法之大规模并行查找算法 TCAM(Ternary content Address Memory)将规则集划分成每个子集只有一条规则 优点： 时间复杂度O(1),空间复杂度O(N).查找速度快 缺点： 成本高 不支持范围匹配 包分类算法： 穷举分类算法 基于Trie分割算法 几何区域分割算法 元组空间分割算法 维度分解算法 基于Trie分割的分类算法 主要思想 – 建立层次式的Trie结构，将分类规则分割，存储于不同的Trie分支 – 查找时依次在不同层次的Trie上有哪些信誉好的足球投注网站 典型算法 – 基本分层Trie树 – 集合归并Trie树 – 网格Trie树 基本分层Trie树 主要思想 – 根据规则集合建立一个分层二叉树结构 – d维分层树是对一维树结构的简单扩展，采用递归方式生成 –从根结点开始，根据规则域值前缀长度，依次由高比特位到低比特位建立二叉树的分枝 优点 – 算法简单、直接 缺点： – 回溯时间长，对规则维数的扩展性差，不能直接支持范围匹配 基本分层Trie树 根据下表F1字段建立分层查找树 基本分层Trie树 建立以00*为前序的第二层查找树 基本分层Trie树 建立以0*为前序的第二层查找树 基本分层Trie树 建立以*为前序的第二层查找树 基本分层Trie树 建立以1*为前