Efficient IP lookup algorithm

Abstract

The rapid growth of traffic in the Internet, backbone links of several gigabits per second are commonly deployed. To handle gigabit-per-second traffic rates, the backbone routers must be able to forward millions of datagrams per second on each of their ports. Fast IP address lookup in the routers, which uses the datagram’s destination address to determine for each datagram the next hop, is therefore crucial to achieve the datagram forwarding rates required. Also the packet may encounter many routers before it reaches its destination. Hence decrease in delay by micro seconds results in immense cut down in the time to reach the destination .IP address lookup is difficult because it requires a Longest Matching Prefix search . Many lookup algorithms are available to find the Longest Prefix Matching; one such is the Elevator-Stairs Algorithm. It provides a total search time of O (w/k + k) by indexing hash table to Practical Algorithm to Retrieve Information Coded in Alphanumeric (PATRICIA), where w is the length of the IP address and k is the level of Trie. Elevator Stairs Algorithm uses linear search at the k-level is modified to binary search at the k-level of Trie. At the kth-level, non branching nodes are added to jump k levels of Trie which reduces the time for searching in the Trie. It provides a better search time over the existing Elevator- Stairs Algorithm, by accomplishing a two-way search in the trie.