摘要
包分类是第四层线速数据包输入处理的核心问题。当前包分类问题研究的重点是最差情况下、可伸缩的、多维的算法。尝试格算法的优点是规模可伸缩,缺点是仅支持两维。在尝试格的基础上,结合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.
出处
《计算机应用与软件》
CSCD
2010年第8期107-113,共7页
Computer Applications and Software
基金
国家重点科技项目(攻关)计划(2000-A32-09)
关键词
第四层交换
包分类
支持百万规则的算法
多维算法
尝试格
Layer 4 switching Packet classification Algorithm for 1M rules Muhi-dimensional algorithm Grid of tries.
