9 Memory Efficient IPV4/V6 Lookup using Path Compression

With the rapid growth of the Internet, IP-lookup becomes the bottle-neck in network traffic management. Therefore, the design of high speed IP routers has been a major area of research. The focus of this paper is on achieving significant reduction in memory requirements for the longest prefix-match operation needed in IPv4/v6 lookups. The Longest Prefix Matching (LPM) is one of the problems in the uni-bit trie representation, in which the number of nodes and the memory requirement is high for IP lookup. To solve this problem we propose a classic trie-based approach in IP lookup. We propose an algorithm to compress the uni-bit-trie representation of a given routing table by using single-prefix distance bounded path compression algorithm. This algorithm determines the optimal maximum skip distance at each node of the trie to minimize the total memory requirement