多维过滤规则无冲突的高速分组分类算法

High-Speed Packet Classification for Multi-Dimensional Conflict-Free Filters

为了有效地实现防火墙及QoS路由等功能 ,路由器等网络元素必须能高速地对分组分类 .对一维分组分类 ,已有很多成熟方案 ,而多维算法由于实现复杂 ,还没有有效的分类算法 .本文对无过滤规则无冲突的数据库进行了研究 ,提出了基于元组空间多维分组分类算法 :元组空间矢量位映射算法 .对多维和二维分类在最不利情况下分别进行了性能分析 ,指出与已有的方案相比 ,在存贮空间、查找时间等性能上 ,本文提出的算法是效率最佳的 .本文的算法不仅可以由软件实现 。

Routers must perform packet classification at high speeds to support advanced functions such as firewalls and QoS routing.While several efficient solutions are known for the one dimensional IP lookup problem,the mult dimensional packet classification has proved to be far more difficult.Existing filter schemes with fast lookup time do not scale to large filter database.Based on tuple space search,a packet classification algorithm called bitmap vector of tuple space for multi dimensional conflict free filters is presented in this paper.The result of the performance analysis in two dimension and multi dimension shows that the scheme provides better worse case bounds about time and space complexity than what have existed,so the algorithm is more scalable and faster.The novel approach can be easily implemented both from software and hardware which made this algorithm more practical to application.