联合元组空间和位图设计的二维分组分类算法

Joint design of tuple space and bitmap for two-dimensional packet classification

基于维度分解思想,设计并实现了一种联合元组空间和位图技术的二维分组分类算法(TB,joint tuple space and bitmap)。TB算法首先分别对源IP地址和目的IP地址进行单维匹配,然后在单维匹配的结果上运用交叉组合形成访问元组空间的路线,最后通过位图过滤技术进一步减少访问元组空间的个数,获得最终匹配的多维规则。相比传统的元组空间算法,TB结构清晰简洁易于更新和实现,TB算法拥有更好的时间和空间性能。实验证明,TB算法平均访问内存次数低于代表算法RSFR约26.6%,空间性能平均低于RSFR算法35.1%。

Based on dimension decomposition idea,a high-performance two-dimensional packet classification algorithm by jointing tuple space and bitmap technology,called TB,was designed and implemented.Firstly,TB processes one-dimension matching for SIP and DIP respectively,then it forms tuple space access route by applying the cross-combination method to the matching results in the first step,finally,to reduce the number of required accessing tuple space,TB obtains the multi-dimensional matched rule by adapting bitmap filtering technique to filter tuple space.Compared to traditional tuple space algorithm,the structure of TB is clearer,more concise and easier to update and implement,TB also has better time and space performance.The experimental results show that TB algorithm saves 35.1% of the space requirement than RSFR algorithm and the number of average memory accesses lower than RSFR 26.6%.