A Scalable IP Packet Classification Algorithm Using Indexed Pointers

In this paper, a scalable IP packet classification algorithm using indexed pointers has been proposed.According to the distribution of source port, destination port and protocol type fields in the real applications, the algorithm maps the three fields to an eight-bit value and divides the whole rule set into 256 subsets.It assigns each subset an indexed pointer that points to the starting address of its storage space.The algorithm finds the best bit sequence and uses them as root and child nodes by calculating each bit's information entropy value of the combined field of source IP address and destination IP address, then it establishes a Tries lookup tree for each rule subset.By doing so, it requires the least storage space and lookup time without retrospect.The experimental results indicate that the new algorithm is highly efficient.