一种适用于流匹配的多阶段无冲突归并算法

流匹配算法是准确实现对高速网络中特定流的流量进行测量的关键。RFC算法是相关算法中速度最快的,但它内存消耗很大,预处理运算量大。针对RFC存在的不足,提出了一种多阶段无冲突归并流匹配算法,该算法采用标记桶方法实现前缀匹配的预处理;采用最小区间分隔法实现范围匹配的预处理,同时算法设计了提前丢包。测试结果表明该算法能支持掩码匹配和范围匹配,内存消耗可控,匹配速度可达2Mpps。