基于维度分解的哈希多维快速流分类算法  

Fast Flow Classification Algorithm of Hash in Multi-dimensions Based on Dimensions Decomposition

作　　者：佟海奇 包秀国[1,2] 庹宇鹏[3] 袁庆升[2] 叶建伟[4] 

机构地区：[1]北京邮电大学信息与通信工程学院,北京100876 [2]国家计算机网络应急技术处理协调中心,北京100029 [3]中国科学院信息工程研究所,北京100093 [4]哈尔滨工业大学计算机学院,哈尔滨150001

出　　处：《计算机工程》2015年第8期55-60,共6页Computer Engineering

基　　金：国家"863"计划基金资助项目(2012BAH01B01);国家自然科学基金资助项目(61100188)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]