Parallel processing priority trie-based IP lookup approach

With the growth of Internet traffic and using Gb/s or 10 Gb/s links in backbone, the speed of forwarding packets in intermediate devices is crucial. Routers must be able to forward millions of packets per second on each of their interfaces. Finding a method that can speed up the IP lookup is one of the challenges in network research. There are two approaches to implement IP lookup, hardware-based and software-based. For software-based approach many algorithms have been proposed based on the tries concept. Some parallel algorithms have been suggested to exploit routers equipped with multi-core CPUs. In this paper, we propose a new approach that was constructed by combining the useful characteristics of the Priority trie and parallel processing. Our method consists of a trie and several subtries based on prefix length. These subtries processed by a specific thread to speed up IP lookup functionality. This proposed data structure inherits simplicity of Priority tries. Simulation results illustrate that our method speeds up IP lookup processing although memory usage has not been increased.