论文部分内容阅读
下一代网络(NGN)将是以IP为核心的高速网络。由于IP网络固有的缺陷，其QoS得不到很好保证。通过对网络中的流量进行准确测量，并以此为依据进行网络控制和管理，可以显著提高网络的QoS。然而，在高速网络中，要想测量全部的流几乎是不可能的。目前，基于特定流的流量测量已成为高速网络流量测量的一个新的研究方向。因此流匹配算法是对高速网络中特定流进行准确测量的关键。
目前可用于流匹配的算法有很多。论文对多种IP数据包分类算法进行了较为全面的分析比较。通过研究，我们发现递归流分类(RFC)算法的分类速度较快，且适合于硬件实现，它的最大缺点是内存消耗大。研究还发现Hash算法用于流匹配具有预处理时间短、内存消耗低、支持匹配规则数多等优点，但常规的Hash算法用于流匹配时冲突率较高。
论文针对RFC算法的不足，提出了一种多阶段无冲突归并(MPNCM)流匹配算法。MPNCM流匹配算法采用标记桶实现最长前缀匹配，用最小区间划分进行范围匹配，同时增加了提前丢包的处理。该算法在平均匹配速度和内存消耗上优于RFC算法。由于MPNCM内存消耗仍然较大且不能支持较大的匹配规则集，论文又进一步研究了Hash算法，提出了一种随机矩阵映射(SMM)Hash算法。SMMHash算法采用了随机矩阵映射，使计算出的Hash关键值服从均匀分布且能减少自相关冲突，因此该算法在冲突率、匹配时间等方面都优于常规Hash算法，并且支持的匹配规则数可达5万条以上。
MPNCM算法和SMMHash算法具有不同的应用场合，MPNCM算法适用于硬件实现，用于匹配规则数少，匹配速度要求高的环境。而Hash算法适合于软件实现，用于匹配规则数较多的场合。