The Research Of The IP Routing Lookup Scheme Based On Trie

With the fast progress of Internet, the number of web users is increasing, and multimedia applications is widely and widely. Hence for improving Internet performance, it orders the core router to be able to forward ten million of packets per second. Fast routing lookup has become the bottleneck of high speed packet forwarding. Thus how to improve search and update performance is the key. Besides, IPv6 technology has been more and more mature, and is being applied into many domains. And it also order to improve the performance of routing lookup.The article summarizes the route looking-up algorithm existed, analyzes and points out the advantages and drawbacks of the algorithms. It is found that trie data structure is the key to achieve a high speed for routing lookup and packet forwarding. According to trie data structure is opt to being applied to hardware technology, we present the LMP (Longest Prefix Match) algorithm based on trie.Some nodes in the algorithm contained two routing entries, which can decrease the number of nodes. That makes the minimal number of memory accesses. According to the prefix length distributions, we make some improvement, which can efficiently lower the tree height. Generally speaking, the proposed scheme not only achieve rapid lookup speed, but also bring a better updata performance. Because the tree can bu updated without being reconstructed from scratch when the routing table is changed. The approach is equally attractive for IPv6. Thus, it can be applied into both IPv4 and IPv6 network.Finally, the author draws a conclusion and discusses some issue for further research.