Research On IP Lookup Algorithm Based On Dynamic Programming And B+ Tree

With the rapid development of Internet technology,the routing table continues to grow,as well as the speed of the network and the network traffic.As a result,IP routing lookup becomes more and more difficult.With the technology of Classless Inter Domain Routing(CIDR)is used in internet routers,router rmust lookup the longest matching prefix in routing table as the next forwarding address.Therefore,IP address lookup becomes the bottleneck of router forwarding performance.Thispapermakesadeepresearch on IP routing technology,and proposed two improved algorithms.This paper researches the technology of routing and IP routing lookup,the difficulty of the current IP routing technology is analyzed;and the typical IP routing lookup algorithm on theclassified research,focusing on the technology based on hash algorithm based on Trie treealgorithm and TCAM algorithm based on the hardware the research and analysis.This paper summarizes the advantages anddisadvantagesofthesealgorithms,andputsforwardtheimproved algorithm plays a great inspiration to the.This paper presents a dynamic programming algorithm based on Trie tree.The algorithmcandetermineanoptimalprefixpartition,sothatinallthe differentclassificationschemes,theschemecanachievetheoptimaluse of space,space to achieve the minimum hash structure.Experimental results show that the spatial disparity using different classification methods of the large,dynamic programming algorithm is proposed in this paper can make the space to achieve the optimal.This paper proposes a scalable and dynamic IP routing lookup algorithm based on B+tree.The data structure with the special prefix as the key to construct the B+tree,with an unsigned integer to compress the store contains one of the most special prefixesprefixes.Compared with other scalable dynamic algorithm,the algorithm for each prefix in the routing table is stored only once,and to find the leaf node will be able to find the longest prefix matching,and not look back.For a n prefix routing table,use the m order B+treesearch structure,the space complexity is O(n),find the time complexity is O(log_mn),and theprefix insertion and deletion efficiency efficiency for O(mlog_mn).The experimental results show that the IP routing lookup algorithm of B+tree can effectively improve the search speedbased on IP is proposed in this paper,which supports IP dynamic update and IPv6 addressprefix.