Research On Future Oriented High-performance Packet Lookup And Classification Technology

The emergence of computer networks enables the independent computing resources to be shared.With the development of network technology,device interconnection and information exchange have been a basis of the modern science and technology.As the carrier of global sharing information,the Internet has become an indispensable part of human society.The rapid expansion of network traffic,the iterative upgrade of network functions,and the frequent transactions of network services pose new challenges to the performance of the legacy network.However,with the breakthrough of high-speed link technologies such as optical fiber and high-speed I/O,the packet processing capability of network nodes such as routers,controllers and firewalls has become the main bottleneck for the development of high-performance networks.For the development trend of the future network,the bottleneck of the network node is mainly reflected in three aspects.First,as the basic technology of packet forwarding and network function,the existing packet lookup and classification algorithms are difficult to support the continuing expansion of the network traffic and the routing tables.Second,with the emergence of technologies such as network function virtualization,cloud computing,and multi-path transmission,existing packet lookup and classification algorithms are difficult to support high-frequency updates of routing tables and flow tables.Third,existing packet lookup and classification algorithms are not compatible with future network architectures(eg,named data networking)and packet formats(eg,IPv6 packets).Facing the future-oriented networks,this thesis focuses on the issues mentioned above about high-performance packet lookup(address lookup and name lookup)and classification techniques,and studies this topic from four entry points.1)This thesis proposes a ultra-performance IPv6 lookup approach using hash and binary search,to meet current and future performance requirements.The data structure of this algorithm consists of hash table and hierarchical binary search tree which is a novel data structure.According to the distribution characteristics of the IPv6 prefix length in the real routing tables,the IPv6 prefixes can be classified into different categories.Each prefix uses the maximum common length bits to generate a hash index.However,there are hash conflict and the prefix overlap between the hash index,which means that the matching must be further differentiated.In order to improve the speed of address lookup and prefix update,this thesis designs and implements a novel data structure named hierarchical binary search tree.The design of hierarchical binary search tree is inspired by the treap.Hierarchical binary search tree has the features of both heap and binary search tree.Based on the structure of hash table and hierarchical binary search tree,a series of algorithms including address lookup algorithm,prefix update algorithm and self-balancing algorithm are designed and implemented.In addition,the hash process is further optimized based on the information entropy of the prefix bits.This algorithm is superior to the state-of-the-art in terms of address lookup,prefix update,and memory consumption.2)This thesis proposes a concept of range-vector,and based on this concept,presents a high-performance packet classification algorithm using hash for fast rule update.According to the distribution of the source and destination address prefix lengths of the real rules,the rules can be mapped to different range-vector spaces.When the data packet is classified,it needs to be searched in each range-vector space.It is usually necessary to traverse all range-vector spaces.Based on this observation,this thesis designs and implements a packet classification hash algorithm using the range-vector.Each hash table corresponding to the range-vector uses the largest common length bits to calculate the hash value.This algorithm has a constant level of rule update speed.Since the packet classification is determined according to the highest priority of the matching rules,the classifying process needs to search all hash tables.This thesis defines the priority of the hash table and sorts the hash tables based on their priority.Therefore,the packet classification speed can be further improved without reducing the update performance and increasing the memory consumption.3)This thesis proposes a name lookup algorithm based on conflict-driven encoding.The named data networking transforms the original thin-waist model with the IP address as the core into a new thin-waist model with the data content as the core.Therefore,the forwarding of the data packet is also changed from the original IP address lookup to the name lookup.However,the data name is very different from the IP address.Firstly,the name is a combination of a series of characters;Secondly,the length of the name is theoretically unlimited while the IP address is of fixed length;Finally,the size of the name prefix database is generally much larger than that of the routing table.Therefore,address lookup algorithms for the legacy network cannot scale to the name lookup.The existing name lookup algorithm has low encoding efficiency and lookup speed or does not support fast name prefix update.For this reason,an efficient collision-driven encoding mechanism and an ulta-performance name lookup algorithm are proposed using the hash table and the extended binary search tree.The algorithm does not need to encode the entire name or prefix,but encodes the name components one by one according to the conflict.The encoding content can be minimized,thus the encoding time will be reduced greatly.4)Multi-core systems are becoming more and more universal and will be the foundation platform for future networks.However,the existing packet classification algorithms do not scale well to the multi-core systems.This thesis proposes two optimized multi-thread packet classification algorithms based on different processes and different data structures.The existing software-based packet classification algorithms are mostly single-threaded,and few of them can be scale to multi-threading.Therefore,it is very practical to study multi-thread packet classification algorithm.In this thesis,the data parallel mode and the pipeline parallel mode are rationally applied for the different algorithms.In the addition,this thesis frees the locks of the multi-threading by using atomic operations and hardware synchronization primitives,which achieves the real independent operation of each thread.