Research On The Packet Labeling And Lookup Technology In The Next Generation Internet

With the fast development of Internet, the Next Generation Internet (NGI) has attracted extensive attention. To achieve more extensive terminal access, and make various heterogeneous networks inter-connect more efficiently, packet labeling and lookup process can be abstracted from four aspects:connectivity layer, flow layer, transport layer and application layer. This dissertation mainly focuses on packet labeling and lookup mechanism in connectivity layer and flow layer. In connectivity layer, packet labeling and lookup process is mainly used to establish packet transmission path, and forward packet, which is usually called routing lookup. In flow layer, packet labeling and lookup process, which called packet classification, is used to support differentiated services for different flows in a variety of scenarios.Currently, IPv6 has gained a wider acceptance to replace its predecessor. And IPv6 have already emerged out of the testing phase. Although IPv6 provides an extremely large address space and several enhancements over IPv4, it changes nothing in the data plane functions of a router. In fact, the 128-bit IPv6 address poses a great challenge to the previous route lookup algorithms, because these algorithms are particularly designed for 32-bit IPv4 address, which had poor scalability to the length of IP address. As a result, a routing lookup algorithm that is gracefully suitable for IPv6 will be promised. Meanwhile, flow label field has been added in IPv6 packet header, which may take new directions for flow labeling and classification. Packet classification based on flow label can effectively reduce difficulties in searching some fields (such as port, protocol, etc), and get rid of the barrier brought by data encryption. Therefore, research on packet labeling technique based on flow label is very important in NGI.This dissertation not only investigates general packet labeling and lookup technology (including connectivity layer and flow layer) and proposes several novel IPv6 packet lookup algorithms, but only investigates packet labeling mechanism towards heterogeneous networks based on flow label. Finally, we also propose a flow-based architecture for the Next Generation Internet. The major contributions and innovations of this dissertation are as follows.(1) This dissertation researches on general lookup model for packet labeling, explores the characteristics of IPv6 address structure, IPv6 address allocation policy, and sufficiently studies the characteristics of classifiers. Based on the above analysis, this dissertation proposes the first IPv6 packet classification benchmark: ClassBenchv6, which is the groundwork for evaluating IPv6 packet classification algorithms and is of a great help to promote IPv6 packet classification algorithm design.(2) This dissertation research on packet labeling and lookup mechanism on connectivity layer and proposes three novel routing lookup algorithms:LPFS-OHT, BTLPT and DBH.LPFS-OHT makes use of the fundamental idea behind LPM (Longest Prefix Matching) and overlap longer prefixes in hash table on shorter prefix. It achieves fast locating for longer prefixes and can stop searching immediately once there is a match in some inner nodes. It has gained 40% performance compared to existing longest prefix first search scheme.The proposed algorithms, BTLPT and DBH, are based on leaf node division framework. It is a novel division framework which can convert a LPM problem into an exact matching problem, minimize the total number of division sets, and support incremental update. Based on this division technique, we propose a novel routing lookup algorithm:BTLPT. BTLPT occupies 50 percent memory of current range based algorithm and can achieve fast lookup speed and update speed. The performance of BTLPT can get rid of address length and thus it is quite suitable for IPv6 routing lookup. Besides, the algorithm DBH is a breakthrough for the traditional static binary search on length algorithm. It is a first dynamic algorithm which can achieve O(logW) lookup performance, and it only has at most 7 hash access numbers in IPv6.(3) This dissertation research on packet labeling and lookup mechanism on flow layer and proposes two novel packet classification algorithms:ODS-BT and H-LCFST.ODS-BT algorithm proposes a novel division technology and it can achieve fast lookup, small memory occupation and incremental update support. The performance of ODS-BT is independent of address length and so it can have quite good scalability in IPv6. H-LCFST is proposed based on sufficiently studies on the characteristics of classifiers and makes use of different data structures to deal with different filters. The proposed heuristic methods can optimize the overall performance for different kinds of classifiers. The evaluation results show that it can accommodate gracefully in different classifiers. In addition, in order to explore the advantage of IPv6 flow label for packet labeling, this dissertation proposes a flow label-based packet labeling technology towards heterogeneous network. We propose a detailed specification for flow label, which provides flexible per-flow and aggregated flow identification ability, and apply it into end-to-end QoS class mapping area. It provides a uniform QoS identification platform for heterogeneous network. In addition, this dissertation also proposes a framework to achieve simulation and verification for the flow label. This work is a good foundation for further application and research on flow label.(4) Based on the above research on packet labeling and lookup mechanism, this dissertation finally proposes a flow-oriented FIA architecture for the Next Generation Internet. The architecture defines a new business model, and establishes a trusted operational network alliance for next-generation Internet. This architecture provides a reasonable, healthy framework for end to end QoS and security system, from both the data flow control plane and data plane. This architecture also provides some solutions for the implementation and goals of NGI, such as "bigger, faster, more secure, more timely, more convenient and manageable and more effective".