| 一种高性能包分类渐增式更新算法 |
| |
| 引用本文： | 冯东雷,张勇,白英彩. 一种高性能包分类渐增式更新算法[J]. 计算机研究与发展, 2003, 40(3): 387-392 |
| |
| 作者姓名： | 冯东雷 张勇 白英彩 |
| |
| 作者单位： | 上海交通大学计算机科学与工程系,上海,200030 |
| |
| 基金项目： | 国家重点科技攻关项目计划基金 ( 2 0 0 0 A3 2 0 9)，Intel大学合作项目——上海交通大学IXA国际合作项目基金 |
| |
| 摘 要： | 包分类是第4层线速数据包输入处理的核心问题之一，当前包分类问题研究的重点是最差情况下，规则数达到百万、多维的动态算法。尝试格（grid of tries）算法的优点是查找时间复杂度与规则数无关，空间复杂度接近线性；缺点是没有支持渐增式更新的算法，即它是一种静态算法，并且仅支持二维。在此提出了一种尝试格的渐增式更新算法，使之成为动态算法。最终提高了尝试格算法的综合性能。
|
| 关 键 词： | 第4届交换 包分类 动态算法 更新算法 尝试格 尝试堆 HoT |
An Incremental Update Algorithm of High Performance Packet Classification |
| |
| FENG Dong Lei,ZHANG Yong,and BAI Ying Cai. An Incremental Update Algorithm of High Performance Packet Classification[J]. Journal of Computer Research and Development, 2003, 40(3): 387-392 |
| |
| Authors: | FENG Dong Lei ZHANG Yong and BAI Ying Cai |
| |
| Abstract: | Packet classification is one of the core issues in wire speed packet input processing research The key problem of packet classification is to find a dynamic algorithm with worst case performance for 1000000 rules Grid of tries algorithm is one of the packet classification algorithm with worst case performance, and can scale to 1000000 rules But the weaknesses of the grid of tries are static and 2 dimension algorithm In this paper, an incremental update algorithm for grid of tries, is proposed Thus grid of tries becomes a dynamic algorithm, and the synthetic performance of grid of tries is improved |
| |
| Keywords: | layer 4 switching packet classification dynamic algorithm update algorithm grid of tries heap on tries |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
