硕士论文答辩选题依据→研究现状-大学课件-

假设对数据包进行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,完成查找。下面我们来看一个简化的例子。Packet

Classification硕士论文答辩选题依据→研究现状·

RFC（Recursive

Flow

Classification）算法简介eq

IDChunk

No.04567PacketHeader

S

d

个域1[0,2112-1]eq

ID23[0,216-1]Chunk

0/1：源IP低/高16位Chunk

2/3：目的IP低/高16位Chunk

4：协议标志Chunk

5/6：源/目的端口

Chunk

7：服务类型[0,2S-1]计算机科学技术系1右图的RFC缩减树由左边的4条规则构建而成，由于我们的算法核心是对交叉乘积表的压缩，因此这里我们只关心其中的交叉乘积表A，我们发现表A中存储了多个相同的eqID序列，比如前9个表项中都存放了相同的eqID（0），造成内存空间的浪费。实际应用中，这种eqID连续重复存储的现象非常普遍，所以我们就需要避免交叉乘积表中eqID

的连续重复存储，下面我们称不同的eqID为独立元素。（第一阶段，将规则集的3个域（F1-F3）分别映射到（分块0-2）

3个预处理表中。预处理表的表项序号表示规则域的一种取值，比如分块0的表项0表示规则中的F1域取值为“000”，表项内容则为一个eqID。每个预处理表有一张相关联的eqID表，其中CBM位串是用来辅助计算eqID的，它的长度与规则数相同，每一位对应一条规则（第一条规则对应最高位，依次类推），每个不同的CBM位串被赋予一个不同的eqID。确定预处理表中eqID的方法是：从预处理表的第一个表项开始，计算每个表项对应的CBM位串，例如分块0的第一个表项0对应的F1取值为000，只有R4的F1域与它匹配，那么该表项对应的CBM位串为“0001”。该位串第一次出现，因而分配eqID为0。分块0的表项1对应的F1取值为001，R1、R2和R4的F1域与它匹配，那么该表项对应的CBM位串为“1101”。该位串第一次出现，因而分配的eqID值加1。其他表项内的eqID按照上述方法计算。当计算出各分块的eqID表后，就对这些eqID表进行交叉乘积，得到了交叉乘积表A。）Packet

Classification硕士论文答辩选题依据→研究现状·RFF1

C算法F2

简介FR1001010011PermitR2001100011DenyR301*100***PermitR4*********Permit计算机科学技术系1Packet

Classification硕士论文答辩提要选题依据Bitmap

RFC分类算法4

基本出发点&研究意义4

设计思想4

数据结构改进的Bitmap

RFC算法基于Intel

IXP2800网络处理器的仿真实验结论计算机科学技术系1处于同一阶段的预处理表或交叉乘积表能够被并行地索引，并且这些预处理表或交叉乘积表又各自独立，能够分布于不同的存储单元中；处于不同阶段的预处理表或交叉乘积表又能够被互不干扰地并行地索引。Packet

Classification硕士论文答辩Bitmap

RFC分类算法计算机科学技术系1·

基本出发点&研究意义4

RFC算法是目前较快的包分类算法，并且有适合于网络处理器实现的优点；4

RFC占用内存过大，当前内存仍然是比较昂贵的资源，减少内存消耗可以降低应用成本；4

用IXP2800实现算法时，当所需内存大大减小后，有可能用SRAM实现，从而大大加快分类的速度；我们用一个称为Bitmap的0/1比特串记录交叉乘积表中独立元素的连续分布情况，其中每个比特位对应交叉乘积表中的一个表项，当某一位被置1，表示交叉乘积表中与该位对应的表项存储了一个与此前不同的相同独立元素序列，我们只需要将序列的第一个独立元素存储到Element数组中就可以了，数组的各个单元与Bitmap中的每个1相对应，这样我们就避免了相同独立元素的连续存储。在查找时，比如索引值为16，这个表项对应的Bitmap中相应位为1，再统计该比特位是Bitmap中的第几个1，我们统计出来它是第6个1，直接找Element数组中的第6个单元就可以了。下面请看算法的数据结构Packet

Classification硕士论文答辩Bitmap

RFC分类算法·

设计思想计算机科学技术系1算法数据结构由一个压缩表和附表组成，当交叉乘积表中独立元素的数量超超出了我们预定义的Element数组大小时，就要将多余的独立元素存入附表中，并增加一个指针指向附表，因此为了提高算法的效率我们应在合理的内存范围内尽可能增大Element数组的容量，避免出现附表，以降低第二次的访存概率。数据结构的设计也考虑到了基于ixp2800的实现，各个域的宽度都需要与ixp2800的内存宽度相匹配Packet

Classification硕士论文答辩Bitmap

RFC分类算法·

数据结构计算机科学技术系1开发平台：IXA

SDK

4.1

DevWorkBench＋Microengine

C；采用与真实规则集特征相似的仿真规则集；对IPv4数据包进行4维分类。Packet

Classification硕士论文答辩基于Intel

IXP2800网络处理器的仿真实验·

Bitmap

RFC与RFC算法内存空间比较71％68.6％72.2％68.7％计算机科学技术系1根据最小包长计算出要达到线速分类，算法应具备25.5Mpps的分类速度Packet

Classification硕士论文答辩基于Intel

IXP2800网络处理器的仿真实验计算机科学技术系1·

相对加速比POP_Count能在3个时钟周期内计算出Bitmap位串中1的个数FFS的效率就比较低Packet

Classification硕士论文答辩基于Intel

IXP2800网络处理器的仿真实验计算机科学技术系1·

指令选择（POP_COUNT

vs.FFS）43％Packet

Classification硕士论文答辩基于Intel

IXP2800网络处理器的仿真实验·

内存分配计算机科学技术系1Packet

Classification硕士论文答辩基于Intel

IXP2800网络处理器的仿真实验·

任务划分（Multi-Processing

vs.Context-Pipelining）计算机科学技术系1实验结果Bitmap

RFC算法消除了RFC算法60％以上的冗余空间；

Bitmap

RFC算法用较少的ME就能达到10Gbps的分类速度；可惜的是10Gbps的分类速度是在SRAM配置下实现的，其它存储方式还无法满足要求；Multi-Processing任务划分方式要优于Context-Pipelining。Packet

Classification硕士论文答辩基于Intel

IXP2800网络处理器的仿真实验计算机科学技术系1·

延迟隐藏1ME2MEs4MEs8MEsWithout

Pkt

Order6.5412.8525.6533.35