Research On IP Packet Classification Algorithm

With the development of new network traffic, it is urgent to accelerate the speed of the transmission of the network. In order to adapt to the new situation, Internet Service Providers (ISP) needs not only to improve the speed of the backbone network, but also provides new differentiated network services that can meet demands of the .different clients. The link speed hasn't been performance bottleneck because of improving in fiber optics and Dense Wavelength-Division Multiplexing (DWDM), but Internet Protocol (IP) routers can be main performance bottleneck because of requiring many complex operations such as fast packet classification.High-speed router requires the packet classification equipment to process packets in wire-speed. Thus, it is very hard to design packet classification algorithms and it has become a big bottleneck of the actions in routers. With the increasing development of the network application,IP packet classification algorithms must have strong scalable abilities in the aspects of the number of dimension, quantity and width of each dimension. Thus, it makes design of packet classification algorithm more difficult. It has become the obstable of IP network extension.Packet classification is a technique to match each incoming packet at a muter against a database of classifier and specify forwarding rules for the packets. The classifiers are a powerful and uniform way to implement new network services. The study on IP packet classification algorithm has practical significance and theory value. Router must not only forward the IP packet according to the destination IP address, but also differentiate the different data flow. One dimensional IP packet classification algorithms are used to slove the former task and multiple dimensional IP packet classification algorithms are used to slove the the latter task. Generally speaking, in order to provide different service for different flow,IP packet classification algorithms classify the different packets into different flow according to the source IP address, destination IP address,source port, destination port and protocol field.In this paper, first, the backgroundof IP packet classification algorithms are introduced. Then, packet classification problems are described in math expression. IP packet classification algorithms analyzed in detail and compared the search time and memory cost in different algorithms. In order to extend the original Area-based Quad Tree (AQT) algorithm into five dimesional packet classification algorithm, the non-collision hash function is used to cope with source port, destination port and protocol field. A novel IP packet classification algorithm Non-Collision Hash Area-based Quad Tree (NCHAQT) is proposed. The basic ideas, the process of preprocessing and packet match are analyzed indetails. And, the priority of ruls is clearly defined. From the theoretic analysis and simulation experiments, it is a good algorithm with high comprehensive performance.