Research On Novel Routing Look-up Algorithm For High-performance Network

With the rapid development of Internet technology,data center network(DCN)and software defined network(SDN)emerge as the times require.Which have imposed higher requirements on the speed and efficiency of network route forwarding.Mainly manifested in: Firstly,in a large-scale network,the efficiency of route forwarding in the SDN controller will directly affect the blocking delay of network data packets and the service quality of end users.Secondly,there are tens of thousands of servers in the DCN.Which makes the size of routing tables larger,resulting in the increase of look-up time.Moreover,the longest prefix matching lookup is needed when routing forwarding.Therefor,the lookup process is carried out in the two dimensions of the routing table capacity and address length.This is the bottleneck of the efficiency of routing and forwarding.In this paper,the DCN and SDN are characterized by considerable increase in routing table entries,substantial rise in network traffic and higher demands on route forwarding speed.To address these issues,TWO efficient prefix-matching algorithms that combines the strengths of the hash and Trie methods is proposed to look up and forward the packets more efficiently.Basic ideas:(1)In the process of routing retrieval,a large number of packets are routed to the query,and the process itself has high concurrency.Surrounding the technology of high performance routing lookup is studied,this paper puts forward two kinds of routing lookup algorithm based on GPU acceleration technology,based on hash table(CUCKOO FILTER)lookup algorithm of acceleration and LCTrie acceleration of tree search algorithm,and compared and analyzed the advantages and disadvantages of the two methods.The routing lookup algorithm based on GPU parallel acceleration is nearly 30 times faster than the algorithm based on CPU processing,which proves the implementation of the GPU architecture as the platform based on the routing lookup algorithm.(2)the present study designs a hash offset-trie match on longest prefix(HOTMLP)algorithm.The routing table matching on longest prefix is divided into common prefix match and feature prefix match in this routing algorithm.Common parts of all route prefixes are stored using the hash table to reduce storage space and matching step size.The exact prefix-matching entry is identified using the Trie method.Theoretical analysis demonstrates that the proposed algorithm looks up faster,updates more easily,and stores the data with less space.Achieving the longest prefix match via HOTMLP has a complexity of “O(n+2)”.In the worst case,the largest number of “n” is 8 for the IPV4 address and 32 for the IPV6 address.Experimental results prove that the proposed algorithm is able to meet the requirements of the core route on routing lookup efficiency and throughput reaches 70 Gpbs on PC(Personal Computer).(3)The algorithm proposed in this paper achieves the three advantages of search speed,update speed and space utilization.It supports the processing of tens of millions of packets per second,and is suitable for data traffic center network.It is also suitable for lookup and forwarding of a large number of flow tables under SDN.