cancel
Showing results for 
Search instead for 
Did you mean: 
cancel
30530
Views
20
Helpful
4
Replies

Please explain how the longest prefix matching works

mahmoodmkl
Level 7
Level 7

Hi,

Please need your support to understand how the router does the longest prefix matching process.

I sort of confused about this.

Thanks

1 Accepted Solution

Accepted Solutions

Hi Mahmoud,

I apologize for keeping you waiting - I had a busy day.

So if i understand correctly the destination IP is ANDED with NETMASK of the potential routes in the routing table and is assume that the destination IP is extracted from the packet and in the IP packet i assume we dont have subnet mask info.

That is correct.

So from the above example not only the router is ANDING but also need to compare the prefix of that NETMASK which was used for ANDING.

I do not understand this formulation. Let me say it in my own words:

Not only does the router need to perform a binary ANDing between the packet's destination IP address and a netmask from a particular routing table row, but it also needs to verify the result of this binary ANDing operation to the network address in the same row.

Think of this: An IP address consists of two parts, a network prefix part, and a host suffix part. The boundary between these two parts is defined by a network mask (a netmask) whose bits set to '1' correspond to the network prefix bits in the IP address, and whose bits set to '0' correspond to the host suffix bits in the IP address.

Furthermore, whenever given an IP address and a netmask, you can always say whether the IP address is - in the combination with the particular netmask value - a network address, a host address, or a broadcast address:

  • If the host suffix part of the IP address contains only bits set to '0', it is a network address (the numerically lowest IP address with the given prefix)
  • Otherwise, if the host suffix part of the IP address contains only bits set to '1', it is a broadcast address (the numerically highest IP address with the given prefix)
  • Otherwise, it is a host address.

In addition, the binary ANDing between an IP address and a netmask always produces a network address. Why? This is because the bits from the IP address that correspond to netmask bits set to '1' - and these are by definition network prefix bits - will be simply copied from the IP address into the result (1-AND-1 = 1, 0-AND-1 = 0). The remaining bits that correspond to netmask bits set to '0' - and these are host bits - will be zeroed out. So the result contains a copy of the network prefix of a certain length from the original IP address, with all remaining bits zeroed out, and this is by definition a network address. In essence, binary ANDing an IP address with a netmask extracts the network prefix of a certain length from the IP address, and fills the rest with zeros.

This is why a router performs binary ANDing between a packet's destination IP address and a netmask from a particular routing table row: It extracts the network prefix of a certain length from the destination IP, fills the rest with zeros, and compares this result to the network address in the same routing table row whose own network prefix has the same length. The router is essentially comparing the prefix of the destination IP to a prefix of a known network in its routing table. If these two values match then we obvously have a route that could be used to forward the packet.

From the above example the router didnt match the first 2 routes is because the after the AND operation the prefix didnt match the destination IP address and last enrty was chossen even though it had the shortest prefix lengt

It is true that out of all networks in the routing table in my previous example, 10.0.0.0/8 is the one with the shortest prefix. However, it is also the first one whose prefix (in this case, 8-bit long prefix) matches the same-length prefix of 10.10.10.10, and thus, it is the longest prefix match for this particular destination.

Let's modify the routing table a little:

Row 1: Network 10.0.0.0 / 255.255.255.0
Row 2: Network 10.0.0.0 / 255.255.0.0
Row 3: Network 10.0.0.0 / 255.0.0.0
Row 4: Network 0.0.0.0 / 0.0.0.0

Now, in this table, both the 3rd and 4th rows are matching the destination because 10.10.10.10 ANDed with 255.0.0.0 = 10.0.0.0, 10.10.10.10 ANDed with 0.0.0.0 = 0.0.0.0. However, because the routing table is sorted according to the network's prefix lengths, the 3rd row has a longer prefix than the 4th row, and it will be the first one that produces a match with the destination of 10.10.10.10 when trying to find a match row-by-row from the top, so this one would be the longest prefix match for 10.10.10.10.

Best regards,
Peter

View solution in original post

4 Replies 4

Mark Malone
VIP Alumni
VIP Alumni

Good extract explaining it from cisco doc

http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/8651-21.html#classless

Making Forwarding Decisions

Let's look at the three routes we just installed in the routing table, and see how they look on the router.

router# show ip route
     ....
     D   192.168.32.0/26 [90/25789217] via 10.1.1.1
     R   192.168.32.0/24 [120/4] via 10.1.1.2
     O   192.168.32.0/19 [110/229840] via 10.1.1.3
     ....

If a packet arrives on a router interface destined for 192.168.32.1, which route would the router choose? It depends on the prefix length, or the number of bits set in the subnet mask. Longer prefixes are always preferred over shorter ones when forwarding a packet.

In this case, a packet destined to 192.168.32.1 is directed toward 10.1.1.1, because 192.168.32.1 falls within the 192.168.32.0/26 network (192.168.32.0 to 192.168.32.63). It also falls within the other two routes available, but the 192.168.32.0/26 has the longest prefix within the routing table (26 bits verses 24 or 19 bits).

Likewise, if a packet destined for 192.168.32.100 arrives on one of the router's interfaces, it's forwarded to 10.1.1.2, because 192.168.32.100 doesn't fall within 192.168.32.0/26 (192.168.32.0 through 192.168.32.63), but it does fall within the 192.168.32.0/24 destination (192.168.32.0 through 192.168.32.255). Again, it also falls into the range covered by 192.168.32.0/19, but 192.168.32.0/24 has a longer prefix length.

Peter Paluch
Cisco Employee
Cisco Employee

Hi Mahmood,

The longest prefix match means that out of all routes in a routing table, the router should choose the one that has the longest prefix and at the same time this prefix matches the prefix of the destination IP address.

The length of the prefix is determined by a network mask, and the longer the prefix is, the higher the netmask is. Therefore, a router keeps its routing table sorted so that all known networks with the prefix length of /32 (255.255.255.255) are at the top of the routing table. Below them, the router puts all known networks with the prefix length of /31 (255.255.255.254), then all known networks with the prefix length of /30 (255.255.255.252), and so on, until it comes to all known networks with the prefix length of /1 (128.0.0.0) and finally all known networks with the prefix length of /0 (0.0.0.0; this is actually a default route). Assuming your router knows about networks 10.0.0.0/8, 10.0.0.0/16, and 10.0.0.0/24, the routing table would be sorted as follows:

Row 1: Network 10.0.0.0 / 255.255.255.0
Row 2: Network 10.0.0.0 / 255.255.0.0
Row 3: Network 10.0.0.0 / 255.0.0.0

Then, when a packet comes in, destined to, say, 10.10.10.10, the router will start at the top of the routing table, performing a bitwise AND between the destination IP and the netmask of the route in that table row. This operation will "extract" the prefix of a certain length determined by the netmask from the destination IP address, and fill the rest with binary zeros. Then, the router compares the resulting address to the network address in that table row, and if they match, the router has found the best matching routing table entry. If they do not match, the router goes to the next row in the table and repeats the whole process. Because the table is sorted according to the prefix lengths, most specific networks being at the top, the first found match is the longest match.

So with our destination IP address of 10.10.10.10 and the routing table shown above, the process would be:

Row 1: 10.10.10.10 & 255.255.255.0 = 10.10.10.0, differs from 10.0.0.0
Row 2: 10.10.10.10 & 255.255.0.0 = 10.10.0.0, differs from 10.0.0.0
Row 3: 10.10.10.10 & 255.0.0.0 = 10.0.0.0, matches 10.0.0.0 :)

Please note that the show ip route output is not sorted according to network masks. However, the router still keeps the routing table sorted internally so than when doing a lookup, it goes from the most specific network to the least specific network as shown above.

Feel welcome to ask further!

Best regards,
Peter

Hi Peter,

Thanks for your precious reply.

Row 1: Network 10.0.0.0 / 255.255.255.0
Row 2: Network 10.0.0.0 / 255.255.0.0
Row 3: Network 10.0.0.0 / 255.0.0.0

Then, when a packet comes in, destined to, say, 10.10.10.10, the router will start at the top of the routing table, performing a bitwise AND between the destination IP and the netmask of the route in that table row. This operation will "extract" the prefix of a certain length determined by the netmask from the destination IP address, and fill the rest with binary zeros. Then, the router compares the resulting address to the network address in that table row, and if they match, the router has found the best matching routing table entry. If they do not match, the router goes to the next row in the table and repeats the whole process. Because the table is sorted according to the prefix lengths, most specific networks being at the top, the first found match is the longest match.

So if i understand correctly the destination IP is ANDED with NETMASK of the potential routes in the routing table and is assume that the destination IP is extracted from the packet and in the IP packet i assume we dont have subnet mask info.

So from the above example not only the router is ANDING but also need to compare the prefix of that NETMASK which was used for ANDING.

From the above example the router didnt match the first 2 routes is because the after the AND operation the prefix didnt match the destination IP address and last enrty was chossen even though it had the shortest prefix lengt,hope  i am correct in asuming this.

Thanks a lot and eagerly waiting for your comments.

Hi Mahmoud,

I apologize for keeping you waiting - I had a busy day.

So if i understand correctly the destination IP is ANDED with NETMASK of the potential routes in the routing table and is assume that the destination IP is extracted from the packet and in the IP packet i assume we dont have subnet mask info.

That is correct.

So from the above example not only the router is ANDING but also need to compare the prefix of that NETMASK which was used for ANDING.

I do not understand this formulation. Let me say it in my own words:

Not only does the router need to perform a binary ANDing between the packet's destination IP address and a netmask from a particular routing table row, but it also needs to verify the result of this binary ANDing operation to the network address in the same row.

Think of this: An IP address consists of two parts, a network prefix part, and a host suffix part. The boundary between these two parts is defined by a network mask (a netmask) whose bits set to '1' correspond to the network prefix bits in the IP address, and whose bits set to '0' correspond to the host suffix bits in the IP address.

Furthermore, whenever given an IP address and a netmask, you can always say whether the IP address is - in the combination with the particular netmask value - a network address, a host address, or a broadcast address:

  • If the host suffix part of the IP address contains only bits set to '0', it is a network address (the numerically lowest IP address with the given prefix)
  • Otherwise, if the host suffix part of the IP address contains only bits set to '1', it is a broadcast address (the numerically highest IP address with the given prefix)
  • Otherwise, it is a host address.

In addition, the binary ANDing between an IP address and a netmask always produces a network address. Why? This is because the bits from the IP address that correspond to netmask bits set to '1' - and these are by definition network prefix bits - will be simply copied from the IP address into the result (1-AND-1 = 1, 0-AND-1 = 0). The remaining bits that correspond to netmask bits set to '0' - and these are host bits - will be zeroed out. So the result contains a copy of the network prefix of a certain length from the original IP address, with all remaining bits zeroed out, and this is by definition a network address. In essence, binary ANDing an IP address with a netmask extracts the network prefix of a certain length from the IP address, and fills the rest with zeros.

This is why a router performs binary ANDing between a packet's destination IP address and a netmask from a particular routing table row: It extracts the network prefix of a certain length from the destination IP, fills the rest with zeros, and compares this result to the network address in the same routing table row whose own network prefix has the same length. The router is essentially comparing the prefix of the destination IP to a prefix of a known network in its routing table. If these two values match then we obvously have a route that could be used to forward the packet.

From the above example the router didnt match the first 2 routes is because the after the AND operation the prefix didnt match the destination IP address and last enrty was chossen even though it had the shortest prefix lengt

It is true that out of all networks in the routing table in my previous example, 10.0.0.0/8 is the one with the shortest prefix. However, it is also the first one whose prefix (in this case, 8-bit long prefix) matches the same-length prefix of 10.10.10.10, and thus, it is the longest prefix match for this particular destination.

Let's modify the routing table a little:

Row 1: Network 10.0.0.0 / 255.255.255.0
Row 2: Network 10.0.0.0 / 255.255.0.0
Row 3: Network 10.0.0.0 / 255.0.0.0
Row 4: Network 0.0.0.0 / 0.0.0.0

Now, in this table, both the 3rd and 4th rows are matching the destination because 10.10.10.10 ANDed with 255.0.0.0 = 10.0.0.0, 10.10.10.10 ANDed with 0.0.0.0 = 0.0.0.0. However, because the routing table is sorted according to the network's prefix lengths, the 3rd row has a longer prefix than the 4th row, and it will be the first one that produces a match with the destination of 10.10.10.10 when trying to find a match row-by-row from the top, so this one would be the longest prefix match for 10.10.10.10.

Best regards,
Peter

Getting Started

Find answers to your questions by entering keywords or phrases in the Search bar above. New here? Use these resources to familiarize yourself with the community: