Introduction

In order to understand the problem of IP address lookup, we need first to start with the IP address architecture.

Classful addressing

The IPv4 IP address is 32 bit of zeroes and ones that is divided into 4 octets. Each octet consists of 8 bits that are separated by dots. For example, the IP address of Lancaster University website 10010100 01011000 00010001 00101011 corresponds in dotted-decimal notation to 148.88.17.43

IP addresses are hierarchical. Specifically, IP addresses consist of two-level hierarchy, usually referred to as a network part and a host part. The network top level part of an IP address identifies the network to which the host is attached; all hosts attached to the same network share the same network part in their IP address. The host bottom part then identifies each host uniquely on that particular network. The network part corresponds to the first left bits of the IP address, called the address prefix. We will write prefixes as bit strings of up to 32 bits in IPv4 followed by an asterisk (*). For example, the prefix 10010100* represents all the 2²⁴ addresses that begin with the bit pattern 10010100. Alternatively, prefixes can be indicated using the dotted-decimal notation, so the same prefix can be written as 148.0.0.0/8, where the number after the slash indicates the length of the prefix.

Since routing occurs at the network level to locate the destination network, routers only forward packets based on network level IP addresses. Thus, all hosts attached to the same network and share the same network part in their IP address can be stored in the router’s forwarding table by a single network IP address, known as address aggregation. An example of a router’s forwarding table is shown in Table 1. Each entry in the forwarding table contains a destination address prefix, next-hop IP address, and output interface number. The forwarding information is located by searching for the prefix that matches the corresponding bits of the destination address.

Destination address prefix	Next-hop IP address	Output interface
0.0.0.0/0	200.10.4.1	Gigabit 3
170.0.0.0/12	202.4.5.8	Gigabit 4
170.14.0.0/16	204.13.9.50	Gigabit 1
15.3.7.0/23	15.30.128.7	Ethernet 0

Table 1: “Router Forwarding Table Example”

The Internet addressing was first designed using a rather simple allocation scheme known as classful addressing. Basically, classful addressing defines three main different sizes of networks: A, B, or C.

Class A: The network part consists of 8 bits and the first octet value is between (0 and 127) which means the networks size can be up to 2⁷ = 128 and the host part consists of (32 – 8 = 24 bits) which means these networks can support at max 2²⁴ – 2 hosts devices (i.e. two addresses are not usable the first one is the network address and the broadcast address).

Class B: The network part consists of 16 bits and the first octet value is between (128 and 191) which means the networks size can be up to 2¹⁴ = 65536 and the host part consists of (32 – 16 = 16 bits) which means these networks can support at max 2¹⁶ – 2 = 65534 hosts devices.

Class C: The network part consists of 24 bits and the first octet value is between (192-223) which means the networks size can be up to 2²¹ and the host part consists of (32 – 24 = 8 bits) which means these networks can support at max 2⁸ – 2 = 254 hosts devices.

It is obvious that the original scheme was inflexible and wasteful. For example if a company has 255 host devices, then a class C IP address won’t be sufficient. It needs to buy either class B or A. As a result, and a huge amount of IP addresses will not be used. Moreover, with the continues growth of internet IP address space was getting exhausted very rapidly. One possible work around was to give the allocate bundles of class C addresses instead of giving class B or A. This causes a massive growth of forwarding table entries.

Classless Inter-Domain Routing (CIDR) addressing

The CIDR addressing scheme was introduced in 1993 to remedy the inefficiencies of classful addressing. With CIDR, variable prefix length is allowed rather than constraining them to be 8, 16, or 24 bits long. This results in IP address space is better conserved. By using route summarization, different blocks of networks can be aggregated together to reduce the growth of forwarding tables. To understand how this works, consider the networks from 170.0.0.0/16 through 170.15.0.0/16 and in a router all these networks are reachable through the same ISP as shown in Fig. 1.

Fig. 1: “Prefix Aggregation Example”

The leftmost 12 bits of all the addresses in this range are the same (10101010 0000). Thus, these 16 networks can be aggregated into one route summary represented by the 12-bit prefix, which in decimal notation gives 170.0.0.0/12. Indicating the prefix length is necessary in decimal notation, because the same value may be associated with prefixes of different lengths; for instance, 170.0.0.0/12 (10101010 0000*) is different from 170.0.0.0/14 (10101010 000000*).

Address aggregation does not reduce entries in the router’s forwarding table for all cases. Consider the scenario where a customer owns the network 170.14.0.0/16 and changes its ISP, but does not want to renumber its network. Now, all the networks from 170.0.0.0/16 through 170.15.0.0/16 can be reached through the same ISP, except for the network 170.14.0.0/16. We cannot perform aggregation as before, and instead of only one entry, 16 entries need to be stored in the forwarding table. One solution is aggregating in spite of the exception networks and additionally storing entries for the exception networks. In this example, this will result in only two entries in the forwarding table: 170.0.0.0/12 and 170.14.0.0/16 (See table 1). However, now some addresses (i.e. 170.14.5.1) will match both entries because of the prefixes overlap. In order to always make the correct forwarding decision, routers need to do more than search for a prefix that matches. Since exceptions in the aggregations may exist, a router must find the most specific match, which is the longest matching prefix. In summary, the address lookup problem in routers requires searching the forwarding table for the longest prefix that matches the destination address of a packet.

Obviously, the longest prefix match is harder than the exact match used for class-based addressing because the destination address of an arriving packet does not carry with it the information to determine the length of the longest matching prefix. Hence, we need to search among the space of all prefix lengths, as well as the space of all prefixes of a given length.

Many algorithms have been proposed to address the longest prefix match problem. This web based tutorial provides a survey of these techniques. But before that, we introduce some performance metrics for the comparison of these lookup algorithms.

• Lookup Speed: The growth of link bandwidth requires faster IP lookups. For example, links running at 10 Gbps can carry 31.25 million packets per second (mpps) (assuming minimum sized 40-byte IP packets which is a TCP-acknowledgment packets). The amount of time that it takes for a lookup can be calculated as follows:

Lookup time = (40 bytes x 8bits/byte) / 10Gbps = 32 ns

That means the number of memory accesses is very crucial in determining the lookup  speed.

• Storage Requirement: Small storage means fast memory access speed through cache memory and low power consumption. Therefore, the amount of memory consumed by the data structures of the algorithm is also important.
• Scalability: The ability of an algorithm to scale both in speed and memory in order to handle large forwarding tables is required. While core routers presently contain as many as 200,000 prefixes, it is expected to increase to 500,000 to 1 million prefixes with the possible use of host routes and multicast routes [1].
• Update Time: Currently, the core routers may receive a peak of a few hundred BGP (Border Gateway Protocol) updates per second. Thus, the route changes require updating the forwarding table data structure, in the order of milliseconds or less. These requirements are still several orders of magnitude less than the lookup speed requirements. Nevertheless, it is important for an algorithm to support incremental updates and should interfere little with normal lookup operations.

Unless otherwise specified, we use the sample forwarding table shown below as a running example for the different algorithms.

Prefix	Forwarding Information
*	P1
1*	P2
00*	P3
101*	P4
111*	P5
1000*	P6
11101*	P7
111001	P8
1000011	P9

Table 2: “Prefix Table Example”

We also use the following three parameters:

N = Number of prefixes in a router’s forwarding table.

W = Length of the prefixes in bits (Maximum is 32 for IPv4 and 128 for IPv6).

S = Memory space required for each node.