Research on a XOR Hash IP Classification Algorithms

摘要

In this paper, 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 hash algorithm, which is based on XOR hash algorithm. The core of algorithm consists of three parts: (1) concatenating the source/destination IP pairs, source/destination port and protocol, then dividing the packet header into 5 chunks, each of which has 22bits in size; (2) mapping one of chunking into stochastic space and XOR operation on the rest 4 chunks and random number mapped. Because the stochastic space follows even distribution after XOR operation so that its collision is limitary; (3) lookup every rule index in order to ensure the validity so that we get the final rule index. The test results show that the classification rate of double-hash algorithm is up to 2 million packets per second and the maximum memory consumed is 5MB for 10,000 rules.