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