Research On High-performance IP Lookup And Packet Classification Algorithms

As a public information carrier,Internet has become one of the most important information infrastructure in the development of human society.Statistics show that the total number of Internet users in China have been more than 560 million,and the Internet popularizing rate is 42%.The sustained and rapid development has inevitably resulted in rapid expansion of network traffic,which becomes a new challege of the Internet transmission capacity.With the development of the high-speed fiber and interface technology,the packet processing capability in routers and other network equipments has become the main bottleneck in the development of high-performance network.The bottleneck mainly includes the following two aspects:Firstly,as the most basic and core functionality,IP lookup speed is becoming a bottleneck.To address this problem,we need to develop new algorithms to sport the high-speed routing forwarding on large-scale routing tables.The official opening of IPv6 requires the IP lookup algorithm must be able to support address scalability.Secondly,in order to ensure the QoS,Internet needs to provide a variety of defferentiated services according to the demand of users.These services include VPN,access control,policy-based routing,traffic statistics,content-based forwarding and so on.Most of these services are based on packet classification.The sustained high-speed growth of Internet traffic has brought great challenges for packet classificaion.To address these problems,this dissertation focuses on developing the high-performance IP lookup and packet classification algorithms,the major contributions are as follows.(1)We propose a novel structure named Compressed Multi-way Prefix Tree(CMPT)based on B+tree to perform dynamic and scalab le high-speed IP address lookup.Our contributions are to design a practical structure for high-speed IP address lookup suitable for both IPv4 and IPv6 addresses,and to develop efficient algorithms for dynamic prefix insertion and deletion.By investigati ng the relationships among routing prefixes,we arrage independent prefixes as the search indexes on internal nodes of CMPT,and by leveraging a nested prefix compression technique,we encode all the routing prefixes on the leaf nodes.For any IP address,the longest prefix matching can be made at leaf nodes without backtracking.For a forwarding table with n prefixes,in the worst case,CMPT requires O(log_mn)search time and O(mlog_mn)dynamic insert and delete time.Performance evaluations using real life IPv4forwarding tables show promising gains in lookup and dynamic update speeds compared with the existing B-tree structures.(2)We propose an high-performance IPv6 lookup algorithm based on GPU acceleration technology:GRv6.To address the limitation that the existing algorithms based on GPU acceleration can only process IPv4 addresses,we propose an IPv6lookup algorithm for software routers based on bloom filters.By using bloom filters,GRv6 stores the forwarding table on GPU,and develops a paralle l bloom filters structure to perform longest prefix matching by utilizing the characteristics of massively parallel of GPU.We further optimize the proposed algorithm by leveraging a thread coalescing technique of CUDA.After optimization,the memory acces s complex of GRv6 is O(1).Based on this architechture,we propose dynamic prefix insertion and deletion algorithms based on counting bloom filters.The experiments on real-life IPv6 routing tables show that GRv6 could achieve 60Gbps throughput for the static routing tables and 40Gbps for dynamic routing tables with dynamic prefixes update.The results show that GRv6 is suitable for OC-768.(3)We propose a multi-dementional packet classification algorithm HAPT based on hierarchical all-match B+tree.By utilizing the property that the IP prefixes in a rule set are nested to each other,the source IP prefix set is used to build an all-match B+tree,which is the first stage of HAPT.According to the keyworks stored in each leaf node of the first stage,we further build another all-match B+tree using the associated destination IP prefix set as the second stage of HAPT.Each tree in the second stage is connected to each leaf node of the first stage.Based on the proposed data structure,we propose multi-dementional packet classification algorithm and dynamic rule update algorithm.By performing multi-way search on each level and complete matching operation of each stage at leaf node,HAPT avoids backtracking search in hierarchical trie algorithm,and efficiently i mproves the packet classification performance.The time complexity of packet classification is O(log_mn),and the time complexity of dynamic rule update is O(mlog_mn).Theoretical analysis and evaluation results show that the proposed multi-dementional packet classification algorithm improves the speed by a factor of 2-4 compared to state-of-the-art algorithm H-trie.(4)We propose a firewall rule preprocessing algorithm to eliminate the correlation of the firewall rules,and optimize firewall rules.Firstly,we propose an algorithm to discover and elimilate correlation between two firewall rules.Based on the characteristic of each detecting field,by computing the differences of each field between two rules,the algorithm rewrites the rules which are not intersected.We then propose a systematic approch to optimize firewall policy and generate a new policy.By traversal the firewall rules,we rewrite each correlated pair and delete inefficacy rules.The generated new policy dose not include correlated ru les,and for any packet there is only one rule matching.Theoretical analysis and experimental results demonstrated that our approach is effective to eliminate correlations in firewall policy.