Efficient tri-ary search tree based packet classification algorithm

With the increasing development of wireless network technology, the traffic in the Internet grows rapidly recently. Meanwhile, ISPs have to provide more value added services. Therefore, efficient packet classification algorithms are highly demanded. In this paper, a novel tri-ary search tree for multi-dimensional classifiers is developed. The data structure, search strategy and its improvement idea are presented. This technique can avoid the memory blowup and its search speed is reasonable, compared with other related schemes. The memory complexity and the search complexity of it may reach O(WN) and O(log₃N), where W and N represent the width of multi-dimensional field and the number of the rules respectively. The experiments provide the evidence that it has outstanding performance.