Research on a Double-Hash IP Classification Algorithm

摘要

Packet classification is one of the key issues in traffic measurement. In this paper, we propose a novel IP classification algorithm based on Non-Collision Hash Trie-Tree Algorithm and XOR hash algorithm, namely double-hash algorithm. Hash algorithm allows us to map an element x in a large set into an element h in a small set through the hash function h = f(x) so that we can quickly find the information once we have determined the small set to search for. The XOR hash algorithm introduces XOR operation to obtain a hash key value. The computation of an XOR hash key value consists of three steps: (1) structuring the non-collision hash function, which is constructed mainly based on destination port and protocol type field so that the hash function usually can avoid space explosion problem; (2) introducing multibit Trie-tree based the key value of XOR hash in order to reduce time complexity; (3) lookuping every rule index in order to ensure the validity that we get the final rule index. The test results show that the classification rate of double-hash algorithm is up to 5 million packets per second and the maximum memory consumed is 6MB for 10,000 rules.