一种高性能包分类渐增式更新算法  

An Incremental Update Algorithm of High Performance Packet Classification

作　　者：冯东雷[1] 张勇[1] 白英彩[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《计算机研究与发展》2003年第3期387-392,共6页Journal of Computer Research and Development

基　　金：国家重点科技攻关项目计划基金 ( 2 0 0 0 A3 2 0 9) ;Intel大学合作项目--上海交通大学IXA国际合作项目基金

摘　　要：包分类是第 4层线速数据包输入处理的核心问题之一 当前包分类问题研究的重点是最差情况下 ,规则数达到百万、多维的动态算法 尝试格 (gridoftries)算法的优点是查找时间复杂度与规则数无关 ,空间复杂度接近线性 ;缺点是没有支持渐增式更新的算法 ,即它是一种静态算法 ,并且仅支持二维 在此提出了一种尝试格的渐增式更新算法 ,使之成为动态算法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

关 键 词：第4届交换 包分类 动态算法 更新算法 尝试格 尝试堆 HOT 

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