Packet classification is a basic process in most network-based packet processing systems. The key operation in this process is to match the packet header against the rules defined in a rule-set and, finally, to find the best matching rule. One of the well-known algorithms for packet classification is the Kd-tree algorithm. This algorithm produces a binary tree using the tuples created by the length of the prefix of the source and destination IP addresses of the rules. The tree is intended to classify the packets. The efficiency of the mechanism for producing and searching the binary tree in this algorithm is affected by two major disadvantages, namely, redundant nodes and redundant accesses during the search. The former increases memory consumption and the latter slows down packet classification. The proposed idea in this article is to prune redundant nodes by sorting the rules corresponding to each tuple in the tree nodes. The experimental results suggest that the throughput rate of the pruned Kd-tree is 43.64% higher than the Kd-tree. Also, by pruning the structure of the Kd-tree, our proposed method could at best reduce 24% of the memory consumed for the storage of the data structure of the Kd-tree.
