计算机应用 ›› 2010, Vol. 30 ›› Issue (11): 3053-3055.

• 网络与通信 • 上一篇    下一篇

基于规则集压缩的高效包分类算法

毕夏安1,谢高岗2,张大方3   

  1. 1. 湖南大学信息科学与工程学院
    2. 中国科学院计算技术研究所
    3. 湖南大学计算机与通信学院
  • 收稿日期:2010-04-26 修回日期:2010-06-21 发布日期:2010-11-05 出版日期:2010-11-01
  • 通讯作者: 毕夏安
  • 基金资助:
    国家重点基础研究发展计划(973);面向业务的网络监控技术研究,湖南省科技计划重点项目

Efficient packet classification algorithm based on rules compression

  • Received:2010-04-26 Revised:2010-06-21 Online:2010-11-05 Published:2010-11-01
  • Contact: Bi Xia-an

摘要: 研究发现快速包分类算法EGT-PC由于压缩特里树路径带来规则集的大量冗余备份降低了算法的查找时间和存储空间等性能。根据规则数据库中规则相对聚集的特性,设计出适合该算法的规则集压缩机制,提出新的包分类算法——EGT-SC。实验表明,在查找时间和存储空间上新算法的性能都有明显的提高。

关键词: 包分类, 规则集, 前缀匹配, 五元组, 特里树

Abstract: This paper found out the fast packet classification algorithm EGT-PC's search time and storage space performance were decreased by the rules' redundant copies. According to the rules aggregation character, a new rules compression mechanism for the origin algorithm was designed, then a new packet classification algorithm EGT-SC was put forward. The experiments show that the new algorithm improves search time and storage space performance significantly.

Key words: packet classification, rule database, prefix match, five tuples, Tire trees