包分类算法

速度，这是评价IP分类算法的最重要标准。算法时间复 杂度的3种评价标准：
最坏情况：对一个包进行IP分类查找的最长可能时间。 平均情况：在随机情况下，对一个包进行分类查找的平均时间。 统计情况：在符合某种预先指定的包或过滤规则匹配率的分布下，对一
个包进行分类查找的平均时间。
占用内存，包括规则库本身以及为高速查找而建立的各 种数据结构占用的内存。
fbest是H的一个匹配过滤规则； 在Fdat中不存在其它的过滤规则f，f与H匹配且满足
cost(f)<cost(fbest)。
IP分类问题是最佳过滤规则匹配问题的一个实例。
IP分类问题中与每条规则相联系有一个ACTION，用来表 示对满足相应过滤规则的包的处理动作。
IP分类问题（3）算法的评价指ຫໍສະໝຸດ ：R2I 0 R3
F2 源地址Trie树
2.2 Set-Pruning Trie
查找路径
B C0
A1
0
H
D
E
F
1
1
R4 0
G0
R5
R6
1
R1 0
R2
F1 目的地址Trie树
I 0 R3
F2 源地址Trie树
优点：不需要回溯，查找 时间短
缺点：空间复杂度高，不 易更新。
查找路径 B
A1
0
H
F1 目的地址Trie树
C0
D 1
0 E1 F 1
R4 1 0
R5 G 1
R5
R6
R1 0
R2
R2
F2 源地址Trie树 0I1
R3
R6
2.3 Grid-of-Trie
查找路径
B C0
A1
0
H
D 1
0 E1
F 1
R4 1 0
R5 G 1
R5
R6
R1 0
R2
R2
F1 目的地址Trie树
F2
源地址Trie树
I
0
1
R3
R6
优点：内存空间小
缺点：更新困难，在 需要更新时最好重建 这棵树。
查找路径
B C0
A1
0
H
F1 目的地址Trie树
D 1 0E 1
R4
0 1
G 1
R5
R1 0
R2
F 1
0I R3
1
R6
F2 源地址Trie树
多维IP分类
假定所有过滤规则的协议只取三个值：TCP、UDP和通配符（*）， 对于取值为通配符的过滤规则，将一条规则重复3次，分别对应TCP、 UDP和所有其它情况（OTHER）。
F1（目的地址） 00* 0* 1* 00* 0* *
F2（源地址） 00* 01* 0* 0* 1* 1*
查找路径
B C0
A1
0
H
优点：算法简单、直 接、便于硬件实现。
缺点：回溯时间长， 对规则维数的扩展性 差，不能直接支持范 围匹配。
F1 目的地址Trie树
D
E
F
1
1
R4 0
0 G
R5
R6
1
R1 0
包分类算法
主要内容
包分类问题的产生背景 典型的包分类算法 Bitmap-RFC算法 TIC算法
参考文献
D. E. Taylor. Survey & Taxonomy of Packet Classification Techniques. Technical Report, Department of Computer Science & Engineering, Washington University in Saint Louis, May 2004.
D.Liu, B.Hua, X.Hu, X.Tang. High-performance Packet Classification Algorithm for Many-core and Multithreaded Network Processor. In Proceedings of CASES 2006.
更新代价：
完全更新：重新建立全部的查找数据结构。 增量更新：在查找数据结构中增加或删除一条过滤规则。 重组或平衡：在适当的时间重组数据结构使其恢复原来的效率。
IP分类问题（4）
从数学上看，IP分类问题与多维空间中的点定位问 题相似，但更加复杂。
基本的解决思路：
根据数据流的分布特点以及规则集中规则的分布特点设 计分类算法。
查找时，同时查找4个哈希表，分别用协议号和端口号的某种组合（或 函数）作为索引，找到相应的Grid of Tries树；然后再根据Grid of Tries 树的查找方法找到最小代价的过滤规则；取所有哈希表中的最好结果 即为最佳匹配的规则。
将高维问题转化为二维乃至一维的问题，降低问题的复 杂度。
2. 典型的IP分类算法
以Grid-of-Tries为代表的基于Trie树的算法 以比特矢量为代表的算法 以HiCuts为代表的决策树算法 以RFC为代表的算法
2.1 Hierarcical Trie
规则 R1 R2 R3 R4 R5 R6
根据目的端口和源端口的不同组合建立4个哈希表，分别对应（目的 端口，源端口）二元组为（DstPort，*）、（DetPort，SrcPort）、 （*，SrcPort）和（*，*）的情况。
每个哈希表项为一棵Grid of Tries树，哈希表的索引为相应的端口地 址和协议号的某种组合（或函数）。
H.Cheng, Z.Chen, B.Hua, X.Tang. Scalable Packet Classification Using Interpreting: A Cross-platform Multi-core Solution. In Proceedings of PPoPP 2008.
范围匹配： 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， 最佳规则匹配问题为在Fdat中查找满足下列条件的过滤 规则fbest：
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]前缀匹配。