基于三态内容可寻址存储器的包分类算法研究

摘要

计算机网络的迅速发展衍生出了很多新型的网络服务，包分类是所有这类应用的核心技术。包分类根据包头中的相关域将数据包划分到不同的类中进行区分处理。随着网络流量的激增，包分类已成为影响网络传输速率的瓶颈。
　　 目前，数据包分类的方法主要有软件方法和硬件方法两类。软件方法具有较好的灵活性，但分类速度慢；硬件方法可以满足高速处理要求，但灵活性较差。由于三态内容可寻址存储器(TCAM)的高速并行查找特性，已被越来越多地应用到包分类领域。但是基于TCAM实现数据包分类面临区间膨胀的问题，已有算法无法解决编码区间所需的比特数随区间数目线性增长的问题。
　　 本文提出两种基于TCAM硬件的有效包分类算法：区间分组算法RG(RangeGroupingAlgorithm)和扩展的区间分组算法E-RG(ExtendedRangeGroupingAlgorithm)，通过将多个满足一定条件的区间划分到同一组并共用同一个编码段进行编码，来达到减少编码位数的目的。RG算法将彼此独立的区间分到同一组中，并共用同一个编码段进行编码表示，减少了编码所需的位数。E-RG算法大幅放宽了分组的条件，将彼此独立或者相互包含的区间分到同一组，并利用ShadowEncoding编码方法对同组内的区间进行有效编码。通过使更多的区间共用同一码段，E-RG算法使得编码所需的位数大幅降低。通过合理分组和有效编码，RG算法和E-RG算法不仅完全解决了TCAM中普遍存在的“区间膨胀”问题，还对包分类规则的比特宽度进行了高效压缩，大大减少了TCAM的空间开销。
　　 针对预处理操作会降低RG算法和E-RG算法的匹配速度，本文提出了一种并行流水线匹配机制。采用此匹配机制，可以保证在一个TCAM的时钟周期内完成一个数据包的分类操作。
　　 本文在Windows平台上将RG算法、E-RG算法和几个典型的基于TCAM的包分类算法进行了比较。实验结果表明，E-RG算法可以保证在不损失匹配速度（即在一个TCAM时钟周期内分类一个数据包）的前提下，极大地降低TCAM的空间开销，验证了方法的有效性。

目录

声明

摘要

第1章 绪论

1.1 研究背景和意义

1.2 包分类问题的定义

1.3 包分类算法的性能评价指标

1.4 包分类问题的难点

1.5 包分类问题的研究现状

1.6 本文的主要工作和内容安排

第2章 包分类的相关研究工作

2.1 真实规则集的特征

2.2 基于软件的包分类算法

2.2.1 HiCuts

2.2.2 BV

2.2.3 Cross-Producting

2.2.4 RFC

2.3 可用于数据包分类的硬件

2.4 基于TCAM的包分类算法

2.4.1 E-TCAM

2.4.2 ORTC

2.4.3 MR

2.4.4 DRES

2.4.5 TT

2.5 Shadow Encoding编码

2.6 本章小结

第3章 基于TCAM的有效包分类算法

3.1 问题分析

3.2 区间分组算法

3.2.1 分组原因和编码方法

3.2.2 分组算法

3.2.3 分类表和转换表

3.2.4 算法举例

3.3 扩展的区间分组算法

3.3.1 基于Shadow Encoding的区间分组思想

3.3.2 分组算法

3.3.3 分类表和转换表

3.3.4 算法举例

3.4 算法的并行流水线工作模式

3.5 本章小结

第4章 实验评估

4.1 实验设置

4.2 实验结果

4.3 本章小结

第5章 总结与展望

5.1 总结

5.2 未来工作

参考文献

插图

表格

致谢

在读期间发表的学术论文与取得的研究成果