A High Performance Parallel IP Lookup Technique Using Distributed Memory Organization and ISCB-Tree Data Structure

The IP Lookup Process is a key bottleneck in routing due to the increase in routing table size, increasing tra?c and migration to IPv6 addresses. The IP address lookup involves computation of the Longest Pre?x Matching (LPM), which existing solutions such as BSD Radix Tries, scale poorly when tra?c in the router increases or when employed for IPv6 address lookups. In this paper, we describe a high performance parallel IP lookup mechanism based on distributed memory organization that uses P processor for solving LPM problem. Since multiple processors are used, the number of pre?xes to be compared for each processor has been reduced. In other words each processor needs to ?nd LPM for a speci?c IP address among N/P of pre?xes. In order to reduce the number of memory access in each processor which is a major bottleneck in IP lookup process, we use ISCB-Tree data structure for the sake of storing the forwarding table in each processor. ISCB-Tree is a B-Tree like data structure that reduces the height of pre?x tree and logarithmic growing manner with the increasing number of pre?xes. By the using of this data structure the number of memory access reduces sharply.