摘要： 位并行算法是一种快速的包分类算法，由于空间占用量过大，不能扩展到大规模规则库。该文从位并行算法出发，比较分析了它的两种改进算法，通过引入位图映射及元组空间的概念，提出了一种新的改进算法，在时间复杂度与空间复杂度上都较位并行算法有很大提高并具有很好的扩展性。在模拟环境下对算法进行了评测，给出了试验数据的分析结果。

关键词: 数据包分类, 位并行, 位图映射, 元组空间

Abstract: Bit-parallelism is a fast scheme for packet classification, but it scales poorly as the filter databases grow in size. By thinking of BV and ABV algorithm, taking the bit-parallelism scheme and adding the ideas of bitmap mapping and tuple space, this paper presents a new algorithm. The new algorithm reduces the complexities of both the time and storage and can scale well with the growth of the filter databases in size. It realizes the algorithm in a virtual environment and analyzes the experimental data.

Key words: packet classification, bit-parallelism, bitmap mapping, tuple space

中图分类号: 

• TP311