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

The IP Lookup Process is a key bottleneck in routing due to the increase inrouting table size, increasing traıc and migration to IPv6 addresses. The IPaddress lookup involves computation of the Longest Prefix Matching (LPM), whichexisting solutions such as BSD Radix Tries, scale poorly when traıc in the routerincreases or when employed for IPv6 address lookups. In this paper, we describe ahigh performance parallel IP lookup mechanism based on distributed memoryorganization that uses P processor for solving LPM problem. Since multipleprocessors are used, the number of prefixes to be compared for each processor hasbeen reduced. In other words each processor needs to find LPM for a specific IPaddress among N/P of prefixes. In order to reduce the number of memory access ineach processor which is a major bottleneck in IP lookup process, we use ISCB-Treedata structure for the sake of storing the forwarding table in each processor. ISCBTreeis a B-Tree like data structure that reduces the height of prefix tree andlogarithmic growing manner with the increasing number of prefixes. By the using ofthis data structure the number of memory access reduces sharply.

کلیدواژه ها:

IP lookup ، Packet forwarding ، ISCB-Tree ، Router organization ، Parallel processing