硕士论文答辩.pptVIP

选题依据→研究现状 RFC（Recursive Flow Classification）算法简介 选题依据→研究现状 RFC算法简介 提 要 选题依据 Bitmap RFC分类算法 基本出发点研究意义 设计思想 数据结构 改进的Bitmap RFC算法 基于Intel IXP2800网络处理器的仿真实验 结论 Bitmap RFC分类算法 基本出发点研究意义 RFC算法是目前较快的包分类算法，并且有适合于网络处理器实现的优点； RFC占用内存过大，当前内存仍然是比较昂贵的资源，减少内存消耗可以降低应用成本； 用IXP2800实现算法时，当所需内存大大减小后，有可能用SRAM实现，从而大大加快分类的速度； Bitmap RFC分类算法 设计思想 Bitmap RFC分类算法 数据结构 基于Intel IXP2800网络处理器的仿真实验 Bitmap RFC与RFC算法内存空间比较 基于Intel IXP2800网络处理器的仿真实验 相对加速比 基于Intel IXP2800网络处理器的仿真实验 指令选择（POP_COUNT vs. FFS） 基于Intel IXP2800网络处理器的仿真实验 内存分配 基于Intel IXP2800网络处理器的仿真实验 任务划分（Multi-Processing vs. Context-Pipelining） 基于Intel IXP2800网络处理器的仿真实验 延迟隐藏 Packet Classification 硕士论文答辩 计算机科学技术系 * 硕士论文答辩 June 3, 2006 计算机科学技术系 Packet Header d个域 eqID eqID Chunk No. 0 1 2 3 4 5 6 7 S [0,2112-1] [0,216-1] Chunk 0/1：源IP低/高16位 Chunk 2/3：目的IP低/高16位 Chunk 4 ：协议标志 Chunk 5/6：源/目的端口 Chunk 7 ：服务类型 [0,2S-1] Permit *** *** *** R4 Permit *** 100 01* R3 Deny 011 100 001 R2 Permit 011 010 001 R1 Action F3 F2 F1 Rule# 71％ 68.6％ 72.2％ 68.7％ 43％ 0.64% 7.14% 7.15% 7.11% Improvement 33.10 23.94 12.13 6.10 Without overlapped 33.35 25.65 12.85 6.54 Overlapped 8MEs 4MEs 2MEs 1ME 0.48% 1.95% 2.88% 3.32% Overhead 33.19 25.17 12.63 6.33 With Pkt Order 33.35 25.65 12.85 6.54 Without Pkt Order 8MEs 4MEs 2MEs 1ME 包序维持 假设对数据包进行d维分类，用S表示包头中d个域所形成的比特串的长度，那么比特串的值应在[0, 2S －1] 中，共有2S种情况。如果将每种情况对应一个等价类（用eqID表示），分类问题就可以看成是根据包头中长为S的比特串的值来确定其对应eqID的问题； 按照这种思想进行分类，最直观的做法是预先计算出所有2S个不同的eqID，存入一个线性表中，在查找时根据到来的数据包头S比特串的值只需一次内存访问就可以查找到结果，但S一般很大， 2S就会占用较大的内存，RFC算法采用分阶段递归实现上述的映射，将包头S比特串进行分块，每一块对应包头域的一部分，比如这里的分块 0对应了源IP地址低16位，其他分块也对应了包头域的不同部分，对于分块0，它存储的eqID的取值范围就在[0, 216－1]之间，这样就可以用一个大小为216的线性表(我们称为预处理表)来存储源IP地址低16位对应的eqID，如果按照原来一次内存映射的方法，则需要大小为2112的线性表，显然不现实。这样RFC通过分块缩小了原来的取值空间，再对各个分块内的eqID进行交叉乘积就可以得到下一阶段交叉乘积表，依次递归得到最终的交叉乘积表。RFC构成的数据结构称为缩减树。 查找时，根据到来的数据包包头分别索引不同的分块，取出各自的eqID进行交叉乘积，索引下一阶段的交叉乘积表，最后就能找到匹配的eqID,完成查找。下面我们来看一个简化的例子。 处于同一阶段的预处理表或交叉乘积表能够被并行地索引，并且这些预处理表或交叉乘积表又各自独立，能够分布于不同的存储单元中； 处于不同阶段的预处理表或交叉乘积表又能够被互不干扰地并行地索引。 我们用一个称为Bitmap的0/1比特串记录交叉乘积表中独立元素