摘要：

在高速网络环境下,实现数据包的快速准确分类对新型网络发展具有重要意义。为此,从维度分解的角度出发,结合单步映射方式,利用哈希方法进行多维合并,提出一种新的哈希多维流分类算法。在完成准确包分类的基础上,通过引入哈希流表对规则与数据流的映射关系进行高速缓存,以加快算法的查找速度。实验结果表明,该算法的平均内存访问次数较HSM算法和RFC算法分别降低了86%和60%,在规则数目大于2 500的情况下,空间占用较RFC算法节约近8%。

关键词: 流分类, 哈希表, 维度分解, 单步映射, 高速缓存, 多维

Abstract:

In the high-speed network environment,to achieve fast and accurate packet classification is of great significance to the novel network.This paper designs and implements the Hash algorithm based on dimension decomposition(HDD) on the basis of the ideological of dimension decomposition and in combination with single step mapping and hash method.The algorithm first considers accurate packet classification,then significantly accelerates searching and improves performance by introducing a hash table for mapping between the rules and the data stream.Experimental results show that the number of average memory accesses of HDD algorithm is lower than Hierarchical Space Mapping(HSM) algorithm and Recursive Flow Classification(RFC) algorithm respectively by 86% and 60%,what’s more,HDD algorithm saves 8% of space usage than RFC algorithm when the rule number is more than 2 500.

Key words: flow classification, Hash table, dimension decomposition, single step mapping, cache, multi-dimensions

中图分类号: 

• TP311