一种线速可伸缩的多维包分类算法  

A CLASSIFICATION ALGORITHM FOR MULTI-DIMENSIONAL PACKET WITH SCALABLE WIRE-SPEED

作　　者：冯东雷[1] 沈宇青[1] 姜锋[1] 

机构地区：[1]万达信息股份有限公司,上海200040

出　　处：《计算机应用与软件》2010年第8期107-113,共7页Computer Applications and Software

基　　金：国家重点科技项目(攻关)计划(2000-A32-09)

摘　　要：包分类是第四层线速数据包输入处理的核心问题。当前包分类问题研究的重点是最差情况下、可伸缩的、多维的算法。尝试格算法的优点是规模可伸缩,缺点是仅支持两维。在尝试格的基础上,结合IP包分类的应用背景,提出了一种可伸缩的五维算法——无回溯层次尝试算法。该算法的基本数据结构是基于尝试格的层次尝试。在不降低规则定义能力的前提下,引入合理的假设。并在此基础上,进一步优化数据结构,消除了层次尝试的回溯搜索。实验证明对于百万规模的规则集,该算法在最差情况下可支持1Gbps链路,在平均情况下可支持2.5Gbps链路。Packet classification is the core in level 4 wire-speed packet input processing. The emphasis of packet classification studies at present is placed on the scalable and muhi-dimensional algorithm in worst cases. Grid of tries has the advantage in scalable, but it only sup- ports 2-dimension. A new scalable 5-dimension algorithm, called non-backtracking hierarchical tries, is proposed based on the grid of tries. Its basic data structure is the grid of tries-based hierarchical tries. With the application background of IP packet classification in mind, rea- sonable assumptions are introduced without compromising the capabilities of the rule definition. The data structure of the algorithm is opti- mized based on these assumptions, backtracking search in hierarchical tries is eliminated. Experiment verifies that for the rule set in a scope of million, this algorithm can support 1 Gbps link in worst case and 2.5 Gbps link in average cases.

关 键 词：第四层交换 包分类 支持百万规则的算法 多维算法 尝试格 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]