计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (15): 1-5.DOI: 10.3778/j.issn.1002-8331.2009.15.001

• 博士论坛 • 上一篇    下一篇

Bitmap结构在高性能网络算法设计中的应用

杨保华1,2,亓亚烜2,3,薛一波2,3,李 军2,3   

  1. 1.清华大学 自动化系,北京 100084
    2.清华大学 信息技术研究院,北京 100084
    3.清华信息科学与技术国家实验室,北京 100084
  • 收稿日期:2008-12-08 修回日期:2009-01-22 出版日期:2009-05-21 发布日期:2009-05-21
  • 通讯作者: 杨保华

Bitmap data structure:Towards high-performance network algorithms designing

YANG Bao-hua1,2,QI Ya-xuan2,3,XUE Yi-bo2,3,LI Jun2,3   

  1. 1.Department of Automation,Tsinghua University,Beijing 100084,China
    2.Research Institute of Information Technology,Tsinghua University,Beijing 100084,China
    3.National Laboratory for Information Science and Technology,Tsinghua University,Beijing 100084,China
  • Received:2008-12-08 Revised:2009-01-22 Online:2009-05-21 Published:2009-05-21
  • Contact: YANG Bao-hua

摘要: 基于Bitmap数据结构的数据压缩技术是一种针对线性存储结构的有效压缩方法,虽被广泛用于网络处理的多个领域(路由查找、网包分类等),却一直缺乏深入的分析。给出了Bitmap结构能提高算法空间性能的理论根据。总结了Bitmap结构在典型网络处理算法中的各种应用,给出了Bitmap结构的数学模型,并通过实例分析了Bitmap结构的优势和不足。Bitmap技术是一种能有效改善网络处理算法存储空间性能的通用技术,并给未来高性能网络处理算法设计提出以及现有算法的改进都提供了启发思路。

Abstract: Bitmap is an efficient data compression technology for linear storage structures.It has been used in various cases to improve the performance of network processing.This paper proves the effectiveness of bitmap technology in storage requirement reduction for data structures of existing algorithms.A mathematical model is provided to illustrate the benefits of the bitmap technology,and experiment results also demonstrates the compression ability of bitmap technology.This paper also analyzes the advantages and disadvantages of using the bitmap technology,to indicate that bitmap,as an efficient technology for improving storage performance,provides an implicational guideline for future algorithms designing.