论文部分内容阅读
计算机网络的迅速发展衍生出了很多新型的网络服务,包分类是所有这类应用的核心技术。包分类根据包头中的相关域将数据包划分到不同的类中进行区分处理。随着网络流量的激增,包分类已成为影响网络传输速率的瓶颈。
目前,数据包分类的方法主要有软件方法和硬件方法两类。软件方法具有较好的灵活性,但分类速度慢;硬件方法可以满足高速处理要求,但灵活性较差。由于三态内容可寻址存储器(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的空间开销,验证了方法的有效性。