Informatics Publishing Limited

Pankaj Gupta ¹, Deepak Jain ¹, Nikhil Anthony ¹, Pranav Gupta ¹, Harsh Bhojwani ¹, Uma Nagaraj ¹

Affiliations
1 Department of Computer Engineering, MAE, Pune-412 105, IN

Abstract

Internet address lookup is a challenging problem because of increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP routing lookup requires computing the best matching prefix, for which standard solutions like hashing were believed to be inapplicable. The best existing solution we know of, BSD radix tries, scales badly as IP moves to 128 bit addresses. This paper presents a novel algorithm “Distributed memory organization” for lookup of 128 bit IPv6 addresses and “Asymmetric Linear search” on hash tables organized by prefix lengths. Our scheme scales very well when traffic on routers is unevenly distributed and in genera it requires only 3-4 lookups, independent of the address bits and table size. Thus it scales very well for IPv4 and IPv6 under such network conditions. Using the proposed techniques a router can achieve a much higher packet forwarding rate and throughput.

Keywords

Best Matching Prefix, Longest Prefix Match, IP Lookup, Ipv6, Distributed Memory Organization, Mutating Binary Search.

Full Text