Research And Design Of Routing Lookup Algorithm Based On Ip Network

A router is an important node device that makes up the Internet.The network layer in the ISO/OSI seven-layer model is responsible for forwarding data in the network.It connects the different networks and forwards the best exports for its packets.The speed of the router forwarding packets determines the transmission speed of all packets passing through the router.At present,the data transmitted on the link can already be carried by fiber,the transmission speed can reach 400Gbps,so the performance bottleneck of the current router is the routing search algorithm.The router's search efficiency determines the performance of the router and determines the data throughput of the Internet.Most of the traffic on the Internet or by the IPv4 network bearer,the study of IPv4-based routing algorithm has its practical significance.How to solve the longest prefix matching problem is the core problem of designing the route search algorithm.At present,many scholars focus on the longest prefix matching problem of routing search algorithm.IPv6 as the next generation of IPv4 technology,with 128-bit address length.It is on the IPv6 network in the core router to deal with a heavier burden,higher requirements.The existing IPv4-based route lookup algorithm can not adapt to new requirements or inefficiencies after extending to IPv6.It needs to establish a new IPv6-based route lookup algorithm.This paper mainly focuses on the routing algorithm based on IPv4 and IPv6 routing,and gives the routing algorithm for IPv4 and IPv6 respectively.The main tasks include:1.The analysis of IPv4 address structure and its development history,through the core router routing table data analysis,found that the IPv4 address prefix distribution presents a certain characteristic:the address prefix length of 24 entries up to.In this paper,a hierarchical routing algorithm is proposed,which combines the hash table and the multi-bit tree.The algorithm divides the routing lookup phase into two stages:the hash table lookup phase and the multi-bit tree structure search phase The In order to reduce access to the memory,a fixed-height multi-bit tree structure is proposed:4-3Trie,which limits the number of times the memory is accessed during route lookup is within an acceptable range.The algorithm analysis and experimental simulation show that the algorithm improves the searching efficiency and has good performance of routing performance by utilizing the characteristics of IPv4 address prefix distribution.2.The analysis of the IPv6 address structure,from the Internet core router routing table to obtain the routing prefix distribution data analysis,found that the address prefix length of 16 times the maximum number of entries,especially the address prefix length of 48 entries up to,Followed by an entry with an address prefix length of 32.At the same time analysis also found that in the routing table prefix to 20,24,26,28 and 2a at the beginning of the table accounted for the vast majority.Based on this analysis,a hierarchical routing algorithm for IPv6 is proposed,and H16,H32,H48c,H48c and H64 are proposed.A hash function and a set of hash conflict resolution strategies.At the same time,the algorithm also proposes a 6-5-4Trie structure,which controls the height of the tree in an acceptable range,and the algorithm reduces the sparseness of the tree to reduce the waste of the storage space as much as possible while compressing the tree height.The algorithm analysis and experimental simulation show that the algorithm has advantages in searching speed and storage space,and can meet the performance requirements of core router.Routing algorithm is complex,many scholars have carried out in-depth study,we are in the previous study on the basis of the improvement and exploration.Related research results have been hired,will be published in the core journals at home and abroad.