What is the longest prefix matching in routing?

Whether small or large, networks have a common purpose of transferring data packets from the source to the destination: this is known as routing. For this to happen, every nodeA node is a connection point in a network. must be uniquely identifiable. This unique identifier for a node on the Internet is its IP addressIP dddresses are unique 32-bit numbers written using dotted-quad (dotted decimal) notation and are of the following form: Network address: Host address..

Note: There are two types of IP addresses: IPv4 and IPv6. To learn more about these, refer to this Answer. This article, however, focuses only on IPv4.

Due to the Internet's vastness, approximately $4.3$ billion IP addresses are assigned to various devices communicating on it. Unfortunately, creating a routing table for every node that has to contain $4.3$ billion entries is highly infeasible.

What is an IP prefix and suffix?

IP addresses are divided into two parts: the prefix and suffix. The prefix represents the network address, whereas the suffix represents the host address. The exact number of bits reserved for the prefix and suffix depends on the routing protocol.

Longest prefix matching

To remedy the highly infeasible approach mentioned above, the Internet deploys Classless Inter-Domain Routing (CIDR). CIDR allows a flexible division between the Network and Host addresses within an IP Address. This division is clarified using an explicit mask detailing the number of bits for the prefix (the Network address part).

An example of the IP Address $12.34.158.0$ with a 23-bit prefix is shown below:

Having variable lengths for the prefixes and suffixes means they can't find exact IP address matches in the routing tables at once. Rather, the CIDR stores all the different prefixes in the routing table, and then finds the longest prefix that matches the destination's IP Address. This is known as the longest prefix matching.

An example of this is illustrated below.

Example

The illustrations below depict how the longest prefix matching is performed when multiple prefixes overlap for an example network.

After converting the prefixes from their dotted quad notation to their bits, the routing table looks as follows:

Note: The bits are different for all of the ports are represented using asterisks.

Let's suppose a packet with the following prefix is received at a router: $11001001\;10001111\;00000101\;11010010$.

Taking a look at these bits, we see that:

• The first 21 bits match all the prefixes in the routing table above. Therefore, we must look at the next bit.

• The first 22 bits match the prefixes at Port 2, 3, and 4. Therefore, we must look at the next bit again.

• The first 23 bits match the prefixes at Port 2 and 3. This still doesn't help us make a decision.

• The first 24 bits, though, match only one prefix (at Port 3). This is where the packet will be forwarded.