AM-Trie: A Parallel Multidimensional Packet Classification Algorithm Fitting for Network Processor

Nowadays, many high speed Internet applications require high speed multidimensional packet classification algorithms. Based on the uniqueness of Network Processor, this paper presents a multidimensional classification algorithm—AM-Trie (asymmetrical multi-bit trie). AM-Trie is a high speed, parallel and scalable algorithm and very fit for the multi-thread and multi-core feature of the Network Processor. A heuristic field division algorithm is also presented, and it is proved theoretically that it can find out the minimum storage cost solution when the height of the AM-Tire is given. Finally, a prototype is implemented based on Intel IXP 2400 Network Processor. The performance testing result shows that AM-Trie is a high-speed and scalable algorithm; the throughput of the whole system is influenced little by the size of rules and it can reach 2.5 Gbps wire speed.