Based On The Range Of Prefix Of Improved Sub Section And Layer Also The Index IPV6Routing Lookup Algorithm

Under the current rapid pace of development of computer network, IPV4limitations of the shortcomings have been appearing more and more out. In addition to safety and performance of the defect, the most important shortcoming is serious shortage of address space.IPV6has the total number of2128ip address, so it can solve problems of IPV4very well. However, the routing lookup IPV6is still comply with the principles of the longest prefix match, the diffculties have also increased. The current route lookup algorithm is mainly applied to IPV4, if simply applied to IPV6, will result in memory space and read times will be increased frequency, performance will be very low. IPV6routing and the existing search algorithms in theory stage, the performance is not clear. Therefore looking for a good search algorithm of applying to IPV6is particularly pressing.The article analysises the existing routing search algorithm and found that the defect of based on prefix interval binary search, thus the article gives the solution, so forming the theoretical basis of the algorithm. In-depth study of the IPV6address allocation strategy, and download the real IPV6routing table from six different locations of the world, and the article in-depth analysis and research the distribution of address prefix, formed the data support this algorithm.Based on the above theoretical research and data analysis, the algorithm proposed data structure of three parts:the sub-level hierarchical binary search prefix part and the HASH table also index part. And characteristics of each part of the data structure are described in detail, also the construction, update, find and delete mechanism of the algorithm is described in detail. And through the real routing table and routing table simulated, the performance of the algorithm were compared with tests with Radix trie and the Patricia trie in the same hardware and software environment.The result shows that the algorithm in construction speed, memory footprint space and the average search speed and scalability are better than them. The algorithm is easy to application on IPV6backbone routers.