The Research And Design Of Route Lookuping Algorithm Based On LPM

Router is a flexible link between subnets and subnets,heterogeneous networks and subnets.Meanwhile,it undertakes important tasks such as data forwarding,routing,and flow control.As one of the core functions of routers,routing lookup has become a major bottleneck in data transmission delay.Improving the forwarding efficiency of the routing lookup algorithm can greatly increase the network data transmission rate and network data throughput.In the context of IPv4 networks being the main body and rapid development of IPv6 networks,Classless Inter-Domain Routing(CIDR)is providing a more flexible address allocation scheme.But it also brings greater designing difficulty of route lookup algorithms.Because of CIDR,routing lookup is changed from excat matching to longest prefix matching with complicated search logic.Compared with 32-bit IPv4,IPv6 has 128-bit binary encoding.The existing algorithms based on IPv4 are not applicable to IPv6 directly.Based on the longest prefix matching LPM(Longest Prefix Matching),the routing lookup algorithm for both IPv4 and IPv6 networks to provide faster search and reasonable system overhead,has extremely high practical value and research significance.In this thesis,routing lookup algorithms for IPv4 and IPv6 networks,focusing on the speed of forwarding table item lookup,the cost of system overhead such as memory,and the speed of table item update execution,is designed and implemented.The main work of this thesis is as follows:(1)Researches on algorithms related to IP technology and routing lookup.By analyzing the core routing table entry data and summarizing the existing classical algorithms focusing on their design concept and data structure,it lays a solid theoretical foundation and data support for subsequent algorithm design.According to the characteristics of different address segments,the data structure design is adopted.(2)A route search algorithm for segment search is designed and implemented.A combination of Trie and hash table structure to realize segment search on IPv4 and IPv6 is applied in the algorithm.A hash bucket structure based on global hashing is deployed on an address prefix of a specific length,dividing the prefix into multiple search intervals.The hash bucket has the characteristics of uniform mapping and high searching rate,which is one of the key structures for fast algorithm search.After determining the prefix interval of the destination address through the hash bucket,Trie structure is used to complete the last interval search.This structure is based on the idea of Multibit Trie and prefix recursion,which can realize multi-bit matching while avoiding traditional Multibit Trie node backtracking problems.A search logic of hash bucket first and then Trie is applied in the algorithm.It can avoid massive invalid searches,locate prefix intervals rapidly and improve the search efficiency significantly.The algorithm is evaluated and tested according to the aspects of memory access times,search and update efficiency and memory usage.The result proves that the algorithm has excellent search and update performance under a reasonable memory occupation.(3)Optimizing the routing lookup algorithm.Like other tree structures,Trie may have the problems of data redundancy and sparse nodes under certain conditions.Structural problems caused by data specificity are optimized by means of pruning node compression to further improve the search efficiency.As for update operation,lock-free programming is used to avoid search thread blocked caused by massive use of read-write locks.The algorithm ensures correct and efficient execution of update operations without sacrificing search efficiency.