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 10MB for 10,000 rules.
Yi Jiang Fengjun Shang
College of Computer Science and Technology Chongqing University of Posts and Telecommunications Chongqing 400065, China
国际会议
2006 International Conference on Communications,Circuits and Systems(第四届国际通信、电路与系统学术会议)
广西桂林
英文
1786-1790
2006-06-25（万方平台首次上网日期，不代表论文的发表时间）