Address Lookup Using Longest

Internet routers basic function is to forward the incoming packets to next hop. And this process to find out an output port of the incoming packet to its corresponding destination IP address is done by IP address lookup. And it has been the major problem for the Internet routers. In this paper we come across two algorithms to find the fastest longest prefix match for IP address lookups.

Implementation of two different algorithms, viz. Trie and binary search algorithms are done using python platform. The paper also deals about the detailed implementation work and the implementation language i.e. Python.These algorithms are described in terms of their data structure and performance.

Performance is evaluated with respect to some pre-defined metrics, viz speed of memory access ,search time data base updating (adding and removing a node) In this paper we also discuss about fastening the initialization, insertion and even the faster IP lookup for forwarding the packets, and are the primary concerns of our algorithms to provide the basis for forwarding and firewall functionality for university border Internet routers.

INTRODUCTION

Internet router's basic function is to forward the incoming packets to next hop. And this process to find out an output port of the incoming packet to its corresponding destination IP address is done by IP address lookup. The IP address has a hierarchical structure of a network identifier and a host identifier, where the network identifier is termed as prefix. IP address lookup searches for a prefix that matches the destination IP address of each incoming packet from the pre-defined routing table.Routing table contains prefix, next hop pairs as the table entry which is based on the routing algorithm used, and these table entries are identical for different types of algorithms. Address in the incoming packet is compared to stored prefixes in the routing table, starting at left of the routing table.

The prefix that matches the largest number of address bits is the desired match in the routing table. And after a match is found the packet is forwarded to the specified next hop address corresponding to the destination IP address. Here problem that occur is large router may have 10,000 or more prefixes. And even the IP address lookup problem will be discussed in later section.As mentioned above the routing table entry is mainly based on the routing algorithms we use. Longest prefix match is a procedure to match the largest number of address bits.

We use many algorithms to find the longest prefix match and these algorithms are used by routers in Internet Protocols networking to select an entry from a routing table.Longest prefix match is used because each entry in a routing table may specify a network, i.e. one destination address may match more than one routing table entry, but the most specific table entry must be matched and this challenge is left to the algorithms. These algorithms will match the most specific table entry with the highest subnet mask is called the longest prefix match. Here the entry has largest number of leading address bits in the table entry which match those of the destination address.For example, consider the router has three prefixes in the routing table:10.50.20.0/2410.50.20.0/2210.50.0.0/16Now if packet comes with the destination address of 10.50.20.10 then according to longest prefix match algorithm the router will select the path of 10.50.20.0/24. Here the prefix length is 24.Now to explain with more detail, let us see how the longest match is done by taking another example.Router A has to send the packet to 172.21.10.237.Router A has 2 interfaces: 172.21.10.246/29 and 172.21.238/28.Router A compares the IP address of the next-hop 172.21.10.237 with the IP address of each its interfaces:1010 1100.0001 0101.0000 1010.1110 1101