A Quad-Trie Conditionally Merged with a Decision Tree for Packet Classification

Trie-based algorithms and decision tree-based algorithms are well-known packet classification solutions which show trade-off between throughput performance and memory requirement. The trie-based algorithms require small memory since each rule is stored exactly once, but they do not provide high throughput because of rule comparison at every rule node. The decision tree-based algorithms provide high throughput since the number of rules compared with an input packet can be controlled as a limited number, but they require excessive amount of memory because of high degree of rule replication. This paper proposes to combine these two types of algorithms. The proposed algorithm primarily constructs a trie and then applies a decision tree for nodes having more rules than a threshold value. Simulation results show that the throughput performance is improved by up to 41 times compared with the trie, and the memory requirement is reduced by up to 38 times compared with the decision tree, so that the performance of both is within a tolerable range for practical implementation.