A novel algorithm for packet classification based on network traffic

Packet classification is one of the basic techniques for many applications such as routers, firewalls and differentiated services. However, with the rapid development of the Internet, it has already become a performance bottleneck in network infrastructures. To improve the performance of packet classification, a great number of algorithms have been proposed. Among them, the linear search algorithm is the simplest. Although its performance is very low, many packet classification algorithms still adopt it. The reason is that the simple algorithm can achieve a balance between the storage space and the execution time. This paper presents a novel algorithm called ROBRC (Rule-ordering Optimization Based on Resolving Conflicts) to improve the performance of the linear search algorithm. As there are some rule conflicts in firewall databases, the optimal rule ordering problem is NP-Complete [5]. Facing with this situation, ROBRC cuts conflicting rules to resolve conflicts and thus can rearrange rules easily according to the statistical characteristics of network traffic. Experimental results show that ROBRC improves the average performance of the linear search algorithm at a reasonable cost of memory space.