The Research Of IPv6 Routing Lookup Algorithm Based On Hash Table And Multibit Trie

With the exponential growth of Internet access device and the spring up of various new network businesses, the IPv4 protocol become increasingly unable to meet the demand. The primary issue of IPv4 is narrow address space, therefore IPv6 possessing a 128-bit address is gradually developed and will gain a long-term development with its great advantage, then it will be bound to replace IPv4.Because of the development of IPv6, the routers now must support IPv6 addressing scheme and address format. One of the main functions of the router is choosing and forwarding the received IP packets. In the present case of link speed has been achieved the fiber speed, the factor of limiting the speed of packet forwarding is routing table lookup algorithm. But the existing routers and routing lookup mechanisms are designed based on IPv4, if we directly applied their to IPv6 and the lookup performance will far from satisfactory, so we need to design a routing lookup algorithm that can be applied to IPv6.In this paper, by way of analyzing the now available routing lookup algorithms, discussing the advantages and disadvantages of each algorithms, as well as comparing performance of the existing IPv4 algorithms ported to IPv6, we find that a high-speed routing lookup algorithm which supporting IPv6 is fit to use several data structures. Choosing the advantages of each algorithm structure, we could design an IPv6 routing lookup algorithm with high lookup speed, efficient update and supporting longer address prefixes.With the combination of hash table and multibit Trie after sufficient and thorough analysis of the now available IPv4 routing algorithm, especially simple and efficient LFT (level forwarding table), the characteristics of IPv6 address and the prefix particularity of real live IPv6 backbone routing table, a hierarchical hash routing lookup algorithm for IPv6 is proposed which using the 32bits prefix as the lookup starting point to achieve faster search just need one memory access. This proposed scheme uses simple data structure, performs faster and supports update easily, and improve the IPv6 backbone network forwarding speed to meet the development demand for IPv6.