A Study Of Packet Classification And The Implementation Of Its Prototype

A traditional router performs two main tasks in forwarding a packet: looking up the destination address of the packets in the routing table, then switching the packet from the input port to the output port. While with the continuous development of the Internet and the speed up of commercialization, the best effort service provided by the traditional IP networks no longer satisfies the users. So the Internet Service Providers hope that networks can provide better services, such as QoS, SLA, firewall, VPN, etc. Although the enhanced services vary greatly, they all require the router to classify the packets according to the packet headers. This technique is called the packet classification. Another reason for the researching of packet classification is the development of high-speed networks. So far packet classification has been a bottleneck to achieve high performance route lookups. Packet classification was brought forward as an absolutely necessary part of some network services. Therefore the implementation of the technique relies on certain network service to some extent. But the technique itself is independent, so it can be studied neglecting the influence of the network services. Besides, as a "hot" technique, new algorithms on packet classification emerge continuously. But most of them focus on the theoretic analysis. This limits the implementation of these algorithms. According to the above, this thesis studies the present research results and makes some extension. An independent algorithm frame is put forward as an attempt to study and solve the problem. The main contents in the thesis are: Firstly in Chapter 1, the thesis summarizes the research background, research status quo domestically and abroad, and the content arrangement of the thesis. In chapter two, the thesis begins with the emergence of the packet classification problem and illustrates the necessity of the classification. Then the thesis introduces some concepts in packet classification and gives our understanding. After that, based on the present research and its difficulty, the thesis gives the principles in solving the problem and the considerations in algorithm design. In chapter three, the thesis analyses the present algorithms on packet classification. Following a summary introduction, the thesis analyses and compares the performance among the algorithms. The analysis points out the necessity and the direction of further research. Keep to the principles and the considerations mentioned above, in chapter four, the thesis puts forward a dynamic DS-Tree algorithm on the basis of the FIS algorithm, which can deal with multi-dimension problem, have a preferable worst-case search speed, occupy relatively small memory, and support dynamic update. A theoretic analysis on algorithm performance is also carried on. In chapter five, the thesis firstly introduces the practical basis of the packet classification prototype system--Netfilter/Iptables framework, which exists in the whole system. Secondly, it introduces the design and implementation of the DS-Tree algorithm based classification prototype system. The aspects in the design include user space, kernel space and the interaction technique between them. Last, some test, comparison and analysis are made between the prototype system and the linear-index iptables system. In chapter six, the thesis analyses the different network service models. Based on different implementing structures, we drew some conclusions and point out the status and effect of packet classification techniques in certain network models. This chapter illustrates the practical importance of the packet classification techniques. In the last chapter, chapter seven, there is a summary of the thesis. Besides, a prospect is made on the development of packet classification techniques and their implementation in future network. According to the shortages in the thesis, we suggest some possible methods and directions in future research work.