The Analysis And Research For A Dynamic IP Lookup Architecture GPU-based Software Router

With the accelerated pace of the information society,the importance of information and communication is gradually highlighted.As one of the forms of information and communication,network communication plays an important role.Currently,with the appearance of optical fiber technology,point information transmission speed reach up to hundreds of Gbps,which is able to meet the present amount of information transmission.However,the routers,which act as a transit point for network,limit the overall speed of the network.Currently,actual routing speed can only reach to dozens of Gbps,which is far from meeting the bandwidth requirements for information and communication.Hence,the study focused on fast,efficient routing architecture and the corresponding algorithm is of important significance in the lookup,deletion,insertion and update in routing tables.This paper focused on fast,efficient routing architecture and the corresponding algorithm and the main contributions of this paper are as follows:1)We present a GPU-based parallel multi Hash dynamic IP lookup architecture aims to offset software routers of which low speed is the main shortcut and hardware routers of which weak extensibility,small memory and high price are the main shortcuts.The architecture consists of two parts,the first part is the data transfer from Host to Device side,which includes pass the IP packet header information preprocessed by CPU to the GPU and return the dealt results to the CPU;the second part is the management of IP packet header information processed by GPU.First of all.CUDA provides a data transmission module for Host side and Device side;in addition,we index the IP addresses with the same length according to the distribution characteristics of the prefix length of the IP addresses.At the same time,we use another IP address to present the conflict of sequential storage.After adoption of the Adaptive Optimal XOR Hash function,the collision rate can be ensured to less than 1%.That is.the architecture can ensure more than 99%of the lookup fetch degrees O(1).with the addition of the powerful parallel processing capability of GPU,the lookup speed of the architecture can reach to 10 times faster than software routers,and the update speed can reach a hundredfold than that of the existing GPU-based routers.2)Aim at the structure mentioned above,we propose the theory about constructing Adaptive Optimal XOR Hash on the basis of exsisting Hash theory.The theory is based on bit XOR operation,count the difference between 0 and 1 among the bits of sample data,to achieve the effect of compression according to bit XOR operation of difference values.Although the time complexity of the algorithm is O(n3),because of the update of rules is operated offline,so this time complexity is acceptable.Experimental results show that the method makes the rate of IP address collision become less than 1%,and greatly improve the search speed of structure?3)Aim at the actual engineering demands of enterprises,we design and implement a GPU-based parallel multi Hash routing system.In the process of forwarding the route packets,the system first preprocesses IP header information through the CPU,and passes to GPU after packaging,frameworks above are based on the longest prefix matching algorithm,searches the IP address with is corresponding to the next hop address and returns it to CPU after packeting.Finally,the system forwards specific IP packet according to the specific results.