PERFORMANCE EVALUATION OF FAST IP-ADDRESS LOOKUP SCHEMES

Abstract

IP address lookup is becoming critical because of increasing routing table sizes, speed, and traffic in the Internet. Given a set S of prefixes and an IP address D, the IP address lookup problem is to find the longest matching prefix of D in set S. The interest is primarily motivated by building multi gigabit routers. Now this problem is addressed by using a LPC trie, a trie structure with combined path and level compression. This data structure enables us to build efficient and easily searchable implementation of an IP routing table. The memory usage is similar to that of a balanced binary search tree, but the expected average depth is smaller. The LPC-trie is well suited to modern language environments with efficient memory allocation and garbage collection. An implementation in the Java programming language is presented and shows that the structure compares favorably to a balanced binary search trees. Tables from the core routers namely, Mae-East, Funet-Table, Mae-West are used in the evaluation to ensure the .test with realistic data. This dissertation work is aimed to study various IP-Address Lookup Schemes and to evaluate the performance of these schemes.