The Design And Realization Of Packet Classification Based On Flow Label In IPv6

Packet classification is the key technologies for the implementation of next-generation Internet network equipments (including MPLS router, firewall, VPN gateway, VOID gateways, etc.) and new network services (including QoS services, security filtering, network address translation, traffic accounting, traffic restrictions, etc.) Research on efficient packet classification algorithm and its implementation is a hot research topic. Packet classification is to extract related field from IP header and search in the filter, and then return the matched filter with highest priority. After that, classify the packet according to the filters into different data streams, and do corresponding operations according to different services, such as forwarding packets, dropped packets, etc..With the rapid development of Internet, IPv6 has become the core protocol of next-generation Internet. With the transition of existing IP network to IPv6, various network services will be transited to run on IPv6. IPv6 has many new features, such as the more concise basic header, better scalability, better support for the Plug and Play, better quality of service, better mobility, and so on. However, IPv6 does not change the basic function of the router data plane-Route Lookup and Packet Classification. IPv6 packet classification problem is also to put forward new challenges.IPv6 defines the concept of flow, which uses flow label to provide a more efficient processing of data packet flow mechanism. This mechanism is especially useful for real-time applications. According to the definition of RFC3697, a router can use the source IP address, destination IP address and flow label to identify a particular stream. Therefore, we can use the flow label field in IPv6 packet to simplify the packet classification problem.This paper presents a flow label based IPv6 packet classification algorithm-Reduced binary tree sorting algorithm. The algorithm uses triples (source IP address, purpose of IP addresses, flow label) instead of the traditional five-tuple (source IP address, purpose of IP address, source port, destination port, protocol) to achieve IPv6 packet classification, in order to achieve simplify packet classification purposes. The main idea is to reduce the dimension by combing the source IP and destination IP, and then organize composite,IP with sorted binary tree. The classification will be done based composite IP and flow label. Sorted binary tree is a method used to organize data type using lexicographic binary tree. Different with the general binary search tree,it does not contain any internal empty nodes, which is able to achieve better spatial performance. It could also achieve better time performance with less decorated nesting and traceback.This paper firstly describes the background and application of the packet classification algorithm, basic principle ofclassical algorithms, and definition and related specification of IPv6 flow label; followed by a discussion of the comparison between the flow label based packet classification scheme and traditional packet classification algorithm. Then the principle of binary tree sorting algorithm is described, based on which the principle, implementation and performance analysis of sorted binary tree is introduced.