2021年Packet classification algorithms.ppt

2021年Packet_classification_algorithms主要内容
包分类问题的产生背景
典型的包分类算法
Bitmap-RFC算法
TIC算法
Packet_classification_algorithms
2021/1/15
1
参考文献
D. E. Taylor. Survey & Taxonomy of Packet Classification Techniques. Technical Report, Department of Computer Science & Engineering, Washington University in Saint Louis, May 2004.
, , , . High-performance Packet Classification Algorithm for Many-core and Multithreaded Network Processor. In Proceedings of CASES 2006.
, , , . Scalable Packet Classification Using Interpreting: A Cross-platform Multi-core Solution. In Proceedings of PPoPP 2008.
Packet_classification_algorithms
2021/1/15
2
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]匹配。
Packet_classification_algorithms
2021/1/15
3
IP分类问题（2）
定义：
给定一个具有N条过滤规则的规则库Fdat，与每条规则f相联系有一个代价函数，记为cost(f)，给定一个包头H，最佳规则匹配问题为在Fdat中查找满足下列条件的过滤规则fbest：
fbest是H的一个匹配过滤规则；
在Fdat中不存在其它的过滤规则f，f与H匹配且满足cost(f)<cost(fbest)。
IP分类问题是最佳过滤规则匹配问题的一个实例。
IP分类问题中与每条规则相联系有一个ACTION，用来表示对满足相应过滤规则的包的处理动作。
Packet_classification_algorithms
2021/1/15
4
IP分类问题（3）
算法的评价指标：
速度，这是评价IP分类算法的最重要标准。算法时间复杂度的3种评价标准：
最坏情况：对一个包进行IP分类查找的最长可能时间。
平均情况：在随机情况下，对一个包进行分类查找的平均时间。
统计情况：在符合某种预先指定的包或过滤规则匹配率的分布下，对一个包进行分类查找的平均时间。
占用内存，包括规则库本身以及为高速查找而建立的各种数据结构占用的内存。
更新代价：
完全更新：重新建立全部的查找数据结构。
增量更新：在查找数据结构中增加或删除一条过滤规则。
重组或平衡：在适当的时间重组数据结构使其恢复原来的效率。
Packet_classification_algorithms
2021/1/15
5
IP分类问题（4）
从数学上看，IP分类问题与多维空间中的点定位问题相似，但更加复杂。
基本的解决思路：
根据数据流的分布特点以及规则集中规则的分布特点设计分类算法。
将高维问题转化为二维乃至一维的问题，降低问题的复杂度。
Packet_classification_algorithms
2021/1/15
6
2. 典型的IP分类算法
以Grid-of-Tries为代表的基于Trie树的算法
以比特矢量为代表的算法
以HiCuts为代表的决策树算法
以RFC为代表的算法
Packet_classification_algorithms
2021/1/15
7
Hierarcical Trie
优点：算法简单、直接、便于硬件实现。
缺点：回溯时间长，对规则维数的扩展性差，不能直接支持范围匹配。
Packet