The Research Of The Comprehensive And Efficient IP Lookup Algorithm Based On Trie

With the growth of physical link speed and the increasement of routing table size,as one of the core technologies of router,IP lookup faces huge performance challenges.First of all,IP lookup has to be able to respond to more and more query requests,which tend to be more than a few million or even tens of millions,and are growing.Second,IP lookup must consider the storage efficiency of data structure,in addition,emerging network technologies and the future network architecture add new requirements to IP lookup,such as:virtualization routers,software defined network(SDN)and named data networking(NDN)and so on.This paper presents two high performance IP lookup algorithms based on Trie.one)PEST algorithm.it uses the x-level extension to improve IP lookup speed,and utilizing Bitmap array which has continuous storage space and less memory possession to reduce the consumption of memory space,in addition,the prefix splitting strategy makes our algorithm apply to the ipv6 address which length is 128smoothly.The experimental results illustrate that PEST has a good performance in the average of IP lookup speed and consumption of memory space;two)NewTrie algorithm.It is based on the 2~k-multiway trie.we translate the descendant internal node array to a bit vector.The 1 and 0 of the bit vector represent the descendant internal node and leaf node respectively.With the use of popcnt instruction,we can get the number of 1 and 0 in the bit vector,and the value of the 1 and 0 can be used as the indirect index of the descendant internal node array or leaf array.In addition,the introduction of leaf vector-leafvec reduce redundant leaf nodes and saved the memory space,the direct table enables IP lookup to be comp leted within O(1)time complexity.In general,the research of this paper has significant theoretical and practical application value.Comparing with the existing IP lookup algorithm,the two kinds of different algorithm which are based on trie can effecti vely improve the IP lookup speed or reduce the memory space overhead,and has good scalability.No matter PEST or NewTrie,both of them can adapt to the daily updating age.