一种基于范围搜索的并行多维分类算法PRSMC

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (32): 164-167.

一种基于范围搜索的并行多维分类算法PRSMC

吴捷,孙斌,陶志荣

江南计算技术研究所,江苏无锡 214083

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-11 发布日期:2007-11-11
通讯作者: 吴捷

PRSMC：parallel range-based searching multidimensional classification algorithm and implementation

WU Jie,SUN Bin,TAO Zhi-rong

Jiangnan Institute of Computing Technology and Researching,Jiangsu,Wuxi 214083,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-11-11 Published:2007-11-11
Contact: WU Jie

摘要/Abstract

摘要： 针对高速网络应用对基于范围查找的分组分类算法的要求以及高性能并行计算环境的特点,提出了一种高速多维分组分类算法——PRSMC（基于范围搜索的并行多维分类）算法。该算法具有较快的搜索速度和较强的并行性,特别适合在多CPU多核高性能计算机上实现。同时提出了算法的双缓冲并行实现技术,使得在软件环境中具有良好空间和时间性能。性能实验表明该算法具有良好的可扩展性,算法速度较同类基于区域划分的算法有较大提升,平均分类速率能达到1 Mpkt/s左右。

关键词: 分组分类, 范围查找, 高性能并行计算, 多维分类, PRSMC

Abstract: Many high speed Internet applications require high speed multidimensional packet classification algorithm.Based on the characteristics of the parallel super computer of high performance,this paper presents a multidimensional classification algorithm PRSMC（Parallel Range-based Searching Multidimensional Classification）.PRSMC is a high speed,parallel and scalable algorithm and very fit for the “multi-thread and multi-core” feature of the super high performance computer.A dual-buffer technique is also presented which improves the algorithm’s space and time performance a lot.The performance testing result shows that PRSMC has a good scalability and it can reach about 1 Mpkt/s classification speed which is faster than HiCuts,another range-based searching algorithm also using the region cuts technique.

Key words: packet classification, range-based searching, high performance parallel computing, multidimensional classification, Parallel Range-based Searching Multidimensional Classification（PRSMC）

吴捷,孙斌,陶志荣. 一种基于范围搜索的并行多维分类算法PRSMC[J]. 计算机工程与应用, 2007, 43(32): 164-167.

WU Jie,SUN Bin,TAO Zhi-rong. PRSMC：parallel range-based searching multidimensional classification algorithm and implementation[J]. Computer Engineering and Applications, 2007, 43(32): 164-167.