A High Performance Parallel IP Lookup Technique Based on Multiprocessor Organization and CREW PRAM

The IP Lookup Process is a key bottleneck in routing due to the increase in routing table size, increasing traffic and migration to IPv6 addresses. The IP routing lookup involves computation of the Longest Prefix Matching for which existing solutions, such as BSD Radix Tries, scale poorly when traffic in the router increases or when employed for IPv6 address lookups. In this paper, we describe a CREW PRAM multiprocessor organization lookup that uses P processor for solving LPM problem. By this technique P-l IP addresses can be looked up simultaneously thus the performance of processors increase in linear manner. First we categorize all prefixes in some groups based on their first two bytes and sort them into their groups. By assuming M prefixes exist in a group then time complexity of insertion algorithm in worst case reduces to 0(Log M + M/2) and the time complexity of search, update and deletion algorithms reduce to log(M) for each prefix.