| With the rapid development of the Internet, the computer network has infiltrated in various fields. It also plays an increasingly important role as well as increasing economic and social values. At the same time, the IPv4 protocol can not fully meet our needs and the 32-bit IPv4 addresses also become increasingly depleted. IPv6, the key protocol of the Next Generation Internet (NGI), has been gaining wider attention and acceptance of the academia and the industry.Compared with IPv4, IPv6 has many advantages, such as the extremely large address space provided by IPv6 with 128-bit IP address, the simpler packet header with better expansibility, better support for plug and play, quality of service, and mobility. However, the Longest Prefix Matching (LPM) is still needed in IPv6. At present, the majority of existing routing algorithms can only adapt to IPv4 environment with 32-bit prefix. Some of them can not be applied to IPv6. The increase of visiting memory or memory consumption will result in very low performance in the case of IPv6. Therefore, the 128-bit IPv6 address has brought new challenges to routing lookup, and it is imperative to find a high-performance IPv6 routing lookup algorithm with the expansion of IPv6 network.This dissertation sufficiently studies the characteristics of IPv6 address, IPv6 address allocation policy and real world IPv6 backbone BGP routing tables. Combining with the research of prefix range and prefix level, a novel IPv6 routing lookup algorithm is proposed. By testing this algorithm with real routing tables and simulated routing tables, the results reveal that the scalability of it is excellent, which enables to support the routing table with 200K prefixes. Comparing the test results with classical algorithms with the same environment, this algorithm proves to possess obvious advantages in the average search speed and the memory consumption. Moreover, the new algorithm provides good support of IPv6 and can be used in IPv6 backbone network routers. |
PDF Full Text Request