Research on Multibit-Trie Tree IP Classification Algorithm

In this article, the authors survey the recent advances in the research of IP classification and introduce some of the typical algorithms. At last, a novel IP classification is proposed based the non-collision hash and multibit-trie tree (NHMTT) algorithm, which is based on non-collision hash trie-tree algorithm and grid of tries algorithm. The core of algorithm has three parts: (1) constructing hash function mainly based on destination port and protocol type field so that the hash function can avoid space explosion problem; (2) transforming grid of tries for the trie-tree pruned and multibit trie-tree in order to reduce space complexity; (3) introducing bitmap algorithm for source port number (or scope). After expanding normally, this doesn't increase the time complex degree of algorithm because we introduce the jumping table. Space complexity consumed and space requirement are less than those of grid-of-tries algorithm. Test results show that the classification rate of NHMTT algorithm is up to 4 million packets per second and the maximum memory consumed is 10 MB for 10,000 rules