Joint design of tuple space and bitmap for two-dimensional packet classification - XIE Kun; ZHAO Jiao-jiao; ZHANG Da-fang (Tongxin xuebao)
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%.