Address Lookup Using Longest Computer Science Essay

Published:

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

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

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/24

10.50.20.0/22

10.50.0.0/16

Now 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 172.21.10.237

1010 1100.0001 0101.0000 1010.1111 0110 172.21.10.246

Now with the second interface:

1010 1100.0001 0101.0000 1010.1110 1101 172.21.10.237

1010 1100.0001 0101.0000 1010.1110 1110 172.21.10.238

Hence by looking at the both compares ions we can know that longest match is 172.21.10.238.

Thus the packets will be sent to the next-hop using the 172.21.10.238/28 interface.

IP ADDRESS LOOKUP PROBLEM

In class-based addressing scheme, fixed prefix lengths of 8, 16, or 24 bits are used for 32-bit IPv4 address, and thus exact match operation was performed by IP address lookup. But class based addressing scheme encountered some issues like wastage of IP address space due to inflexibility of fixed-length prefixes and also the size of routing tables was massively grown due to the lack of address aggregation. So these issues can be overcome by using classless inter-domain routing (CIDR) scheme. In CIDR scheme allows arbitrary length prefixes. Thus avoiding the wastage of IP addresses space and provides prefix aggregation. But this leads to another problem that an input address can match more than one prefix under CIDR. Hence, the IP address lookup problem now becomes determining the longest prefix matching a given input to forward the input to the most specific network. And this longest matching prefix is also called the best matching prefix (BMP).

Figure 1

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

Let's consider the figure 1, which shows an example network that has a 6-bit address space, whereas IP address in IPv4 is 32 bits. As shown in the figure 1, each router obtains an individual routing table composed of set of prefixes and the corresponding output port by running some routing algorithms.

For the example set of prefixes as shown in figure 1, by searching the routing table for an arbitrary input address, 110100, we obtain M(A) = {1., 1101.}. Of these two matching prefixes obtained, prefix 1101* is identified as the longest matching prefix or the best matching prefix (BMP) as four bits of prefix is matched. And it represents the most specific network that the input has to be forwarded. Hence, the input packet is forwarded toward the network though output port 2 according to the routing table.

TRIE ALGORITHM FOR ADDRESS LOOKUP

Trie is also called as prefix tree. Here prefixes which are to be matched with each incoming packets prefix are stored in tries. And this is how we represent the prefixes in the tree, i.e. prefixes are traced out by following path from top (root) in the trie. Consideration and assumptions made in trie implementation are as follows.

Dark nodes mark prefix ends in the trie structure.

To find best prefix, spell out address in the tree.

Last dark node marks longest matching prefix.

UNIBIT TRIE

A unibit trie is a tree in which each node in an array containing a '0' and '1' pointers. At the root all prefixes that start with '0' are stored in the subtrie pointed to by the '0' and all prefixes that start with a '1' are stored in the subtrie pointed to by the '1'.

By using this technique of unibit trie implementation, we can speed up the IP lookup with different data representations.

For example, let's trace of the following Address using Trie Algorithm implementation: 1011 0010 1000. This is diagrammatically represented in the figure 2 shown below.

Figure 2

MULTIBIT TRIES

Most large memories use DRAM. DRAM has a large latency when compared to register access times (2-5 ns). Since a unibit trie may have to make 32 accesses for a 32 bit prefix, the worst case search time of a unibit trie is at least 32*60=1.92μsec. So, this motivates for multibit trie search. If the number of distinct prefix length is l and l < w then worst case bound for trie is order of l { i.e.; o(l) }. Multibit trie reduces the set of arbitrary length prefixes to a predefined set of lengths. Binary or unibit trie takes branch decision based upon bit by bit inspection. Whereas multibit trie takes branch decision by looking at 2, 3 or 4 bits simultaneously. This technique of multibit tries can be explained numerically by taking an example and by showing it in a tree diagram we can easily differentiate unibit and multibit tries.

Let's consider the example below; Table 1 represents the sample prefix database and Table 2 represents the expanded prefixes which are of varying length.

P1

0*

P2

01000*

P3

011*

P4

1*

P5

100*

P6

1100*

P7

1101*

P8

1110*

P9

1111*

Table1. Sample prefix database

00*

P1

Prefixes

of

length 2

01*

P1

10*

P4

11*

P4

0110*

P3

Prefixes

of

length 4

0111*

P3

1000*

P5

1001*

P5

1100*

P6

1101*

P7

1110*

P8

1111*

P9

01000*

P2

Prefixes of length 5

Table2. Expanded Prefixes

Let's consider 01 11 0 is the destination IP address of the incoming packet at the IP router which runs multibit trie implementation. Figure 3 shows the path tracing of the considered destination IP address.

Figure 3

In binary or unibit trie, bit by bit would have taken 4 memory accesses for the above example. So by taking multibit inspection method and by expanding the prefixes of varying length, it reduced the memory accesses. The search times is also reduced in multibit trie. Here in this above example, it takes only 2 memory accesses for prefix lookup. And even the search complexity which was of order 5 is reduced to order of 3.

BINARY SEARCH ALGORITHM FOR ADDRESS LOOKUP

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

The biggest problem of IP address lookup is that prefixes has a variable length so that longest prefix match should be employed for IP address lookup. Binary search is useful to decrease search times. However, this approach requires a lot of memories for the increased set of prefixes and pointers.

In routers, incoming packets and routing tables are stored in memories. The speed of IP address lookup is limited since memory access times are too slow for the wire speed.

An exact match is to find the output port associated with the prefix in the routing table which is exactly the same s the packet destination address. By exact matching it guarantees address lookup that is done at high speeds. Internet uses the prefixes with different lengths which represent hierarchical addressing modes, So that we must use the longest prefix matching to search for a corresponding address.

PREFIX RANGE SEARCH

The basic idea of prefix range searches is using binary search for IP address lookup. Table 3 shows a sample routing table in which there are 4 prefixes. We only expanded the prefixes by the size of 6 to keep simpler instead of 32. Two strings are padded with 0 and 1 from a single prefix for expressing an interval. A prefix 1*(P1) represent a range 100000 to 111111. Hence, one prefix has two points, a starting point and an endpoint. At this prefix, 100000 is the starting point and 111111 is the endpoint of range of prefix P1.

Prefix

Next Hop

P1

1*

H1

P2

101*

H2

P3

101010*

H3

P4

1011*

H4

Table3. A set of prefixes

The prefixes padded with 0 and 1 are called low entry and high entry, respectively. After adding the strings padded with 1, the entries are sorted in order of value. The result for four prefixes in table 3 is show in Figure 4. The lines are connections between the low and high entries made from the same prefix.

Figure4. The list of entries padded with 0 and 1

A prefix is a unique string not a region. The range of a single prefix is covered by two hop pointers associated with the prefix. Table4 shows the final binary table including the = pointer and the > pointer. The = pointer is returned if incoming addresses are exactly equal to the corresponding entry in the table. The > pointer is the next hop that has a relation with addresses that are greater than the corresponding entry. If the address 101001 finds its next hop in the table, binary search will end up at the second entry and return P2 as a next hop because 101001 is greater than the second entry and less than the third entry in the table4.

=

>

P1) 100000

P1

P1

P2)101000

P2

P2

P3)101010

P3

P3

101011

P3

P4

P4)101100

P4

P4

101101

P4

P2

101111

P2

P1

111111

P1

-

Table4. Binary search table after pre-computation

PYTHON LANGUAGE AS A TOOL FOR IMPLEMENTATIONS

We are implementing our current algorithm in Python language. Python language  is a general-purpose, high level programming language, whose simplicity in design structure and syntax makes language easily understandable and increases code readability, its syntax is said to be clear and expressive and it has the advantage of having rich set of library functions. It also has the feature of supporting multiple programming paradigms, such as object-oriented and functional programming styles.

The main aim of the proposed new algorithm is to deal with performance issues that arise due the address lookup, speed of lookup operation is a major design metric we are considering in this implementation, the one area where we can increase the speed of lookup in routing table and issues related to routing bottlenecks is by adopting better memory management technique which reduces the amount of time a router can spend in searching the address of the next hop by using a destination address information .

And the one way to achieving the Better Memory management is by using python language: Python has powerful features of fully dynamic type system and automatic memory management (data structure).Good programming requires having and using the correct data structures for effective implementation of the algorithm. This is almost universally under-emphasized in research-oriented coding.

Python has lists, tuples, sets, dictionaries, strings and many other types of built in. Lists hold arbitrary data objects and can be sliced, indexed, joined, split, and used as stacks .Dictionaries map from a unique key to anything and form the real basis of language .Heaps are available as operations on top of lists and one has an n-dimensional array structure that supports optimized and flexible broadcasting and matrix operations, the above features of data structure is bet best utilized in our implementation to reduce search time of lookup.

Performance Analysis of IP addresses Lookup techniques:

For different values:

Figure.5

Figure.6: Comparison analysis of lookup Algorithms

Got a fairly performance sensitive needed for fast prefix lookup, and have built two different implementations, viz. Trie implementation and Binary search algorithm. Trie implementation provides faster IP lookup, and much faster insertion, but it dramatically slower initialization, which is our primary concern.

So looking for different ways to optimize either of these tools, we came up to some conclusion that using binary search algorithm would very much appreciate help improving initialization time of the Trie, and search or insert time. And we can observe from the comparison of both lookup algorithms as shown in figure 6, time taken by Trie algorithm for adding node, finding prefix, getting address, for single iteration or to build a list is more than time taken by binary search algorithm.

RESPONSIBALITY OF INDIVIDUALS IN GROUP

Akshay S.Banakar: Worked in designing binary search algorithm and contributed in 35% of coding.

Yogesha S.Nagegowda: Worked in designing better data structure for the algorithm and involved 35% of coding.

Nandeesh Rajashekharappa: Worked in designing the trie algorithm implementation and involved in 30% of coding.