| 并行层压缩树包分类算法 |
| |
| 引用本文： | 戴雪龙,王永纲,张万生.并行层压缩树包分类算法[J].中国科学技术大学学报,2006,36(3):297-303. |
| |
| 作者姓名： | 戴雪龙 王永纲 张万生 |
| |
| 作者单位： | 中国科学技术大学近代物理系快电子学实验室,安徽,合肥,230026 |
| |
| 基金项目： | 中国科学院留学回国人员择优资助项目 |
| |
| 摘 要： | 在层压缩树路由算法思想基础上提出了一种新的硬件包分类算法--并行层压缩树包分类算法.该算法是基于独立存储单元和多域并行处理并在FPGA内部实现的高速网络包分类算法,主要包括单通道并行搜索和多通道综合比较两大部分.仿真结果表明在40 MHz的搜索时钟频率下,该算法能够达到每秒2 M包头的处理速度,其空间性能明显优于其他算法,具有O（d）的时间复杂度（d为域的个数）和O（dN）的空间复杂度（N为规则数）.
|
| 关 键 词： | 包分类 层压缩树包分类算法 时间性能曲线 空间性能曲线 verilogHDL仿真 |
| 文章编号： | 0253-2778(2006)03-0297-07 |
| 收稿时间： | 03 10 2005 12:00AM |
| 修稿时间： | 10 20 2005 12:00AM |
Packet classification using parallel level compression trie |
| |
| DAI Xue-long,WANG Yong-gang,ZHANG Wan-sheng.Packet classification using parallel level compression trie[J].Journal of University of Science and Technology of China,2006,36(3):297-303. |
| |
| Authors: | DAI Xue-long WANG Yong-gang ZHANG Wan-sheng |
| |
| Institution: | Fast Electronic Lab, Department of Modern Physics, University of Science and Technology of China, Hefei 230026.China |
| |
| Abstract: | Parallel level compression trie packet classification algorithm,which is based on the idea of level compression routing algorithm and uses the independent memory and the parallel processing multi-fields,is one of the most effective hardware algorithms for fast network packet classification.It mainly consists of single-channel parallel search and multi-channel integrated comparison.The results of simulation show that the algorithm can classify about 2 M packet headers per second on 40 MHz search clock with the time complexity O(d) and space complexity O(dN). |
| |
| Keywords: | packet classification level compression trie algorithm time complexity space complexity verilogHDL simulation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
