Study on a Non-collision Hash IP Classification Algorithm
Real time traffic measurement of network is becoming increasingly important for managing and controlling network. Flows-based traffic measurement is one of the methods. How to match the packets with a specific flow is one of key issues in specific flows-based measurement. This paper presents a method for this purpose, namely Non-Collsion Hash and Multibit-trie Tree Classification Algorithm (for short, NCHMTC Algorithm) algorithm, which is based on Non-Collision Hash Trie-Tree Algorithm and Grid of Tries algorithm. The core of algorithm has 3 parts: 1) constructing hash function mainly based on destination/source port and protocol type field so that the hash function can avoid space explosion problem; 2) incorporating two kinds of algorithm, which are the multibit-trie algorithm and the algorithm of Grid of Tries as well as transforming Grid of Tries for the Trie-tree pruned in order to reduce space complexity; 3) incorporating no using mltibit-trie item. Test results show that the classification rate of NCHMTC algorithm is up to 2 million packets per second and the maximum memory consumed is 10MB for 10,000 rules.
Fengjun Shang
College of Computer Science and Technology Chongqing University of Posts and Telecommunications Chongqing 400065, China
国际会议
青岛
英文
2006-07-21（万方平台首次上网日期，不代表论文的发表时间）