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

Abstract

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 Prefix 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 prefixes to be compared for each processor has been reduced. In other words each processor needs to find LPM for a specific IP address among N/P of prefixes. 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. ISCBTree is a B-Tree like data structure that reduces the height of prefix tree and logarithmic growing manner with the increasing number of prefixes. By the using of this data structure the number of memory access reduces sharply.