MBitCuts: optimal bit-level cutting in geometric space packet classification

摘要

Packet classification is one of the main tasks of modern network processors. A challenging problem in this regard is to use an algorithm that can classify packets at a high speed and with a reasonably low memory consumption. Traditional decision tree-based algorithms do not satisfy both requirements. BitCuts algorithm, which has been recently proposed to increase search speed in tree algorithms, is not an exception. We propose MBitCuts as a novel solution that reduces both memory usage and memory access in this algorithm by changing the method of bit selection in the cutting of the geometric subspace model of each tree node. The evaluation results show that the average number of memory accesses and the average memory usage in the proposed method have been reduced by 39% and 87%, respectively. Also, MBitCuts outperforms state-of-the-art tree-based algorithms by simultaneously achieving the best classification speed and the least memory consumption.