一种新的快速报文分类算法——RC-FST  

A New Fast Packet Classification Algorithm: RC FST

作　　者：谭兴晔[1] 张勇 雷振明[1] 

机构地区：[1]北京邮电大学ATM中心,北京100876 [2]Intel中国研究中心,北京100020

出　　处：《计算机应用研究》2005年第4期62-64,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(69896240)

摘　　要：RC FST算法利用IP地址高 8比特前缀建立Hash压缩索引表,将分类规则集分成多个子集,并针对每个子集建立快速搜索树,而这些规模相对小的本地搜索树更利于实现快速建立、查找和优化。为提高搜索树性能,在规则分割等问题上也提出了独到的解决方法,该算法查找速度快 (50Mbps)、支持分类规则数据库大、可扩展性好,适于硬件流水线方式实现,具有很高的实用价值。Presents a new classification algorithm called RC FST (Rules Cuttings Fast Search Trees) which splits the set of filter rules into several subsets by the Hash compression index table built based on the first 8bit prefix of IP and constructs fast search trees for each subset. These search trees with smaller sized filters can be more quickly constructed and searched. Furthermore, some novel methods for the building of search trees and the partition of filters are described in this paper. RC FST can provide an order of magnitude improvement over existing classification algorithms and be easily implemented in hardware using a pipeline.

关 键 词：报文分类 RC.FST 前缀对 Hash压缩索引表 搜索树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]