longest prefix-matching

Unanswered Question
May 4th, 2009

Hi Guys,


We hear that the router forwards the traffic based on the longer prefix match.


For example the router has four prefixes installed in the routing table as below.


10.50.20.0 /24, 10.50.20.0 /22, 10.50.0.0 /16, and 10.0.0.0 /8


now if packet comes with the a destination address of 10.50.20.10 then if we consider the logic of longest prefix matching then the router will select the path of 10.50.20.0/24..


My confusion is how does the router know that it should use this path..may be i am missing small thing over here.


Please explain.


Thanks

Mahmood

  • 1
  • 2
  • 3
  • 4
  • 5
Overall Rating: 5 (1 ratings)
Loading.
thotsaphon Mon, 05/04/2009 - 01:15

Mohammed,

Router is always preferred longer prefixes. So 10.50.20.10 is matched all of them. But 10.50.20.0 /24 will win because the prefix length is 24.


HTH,

Toshi

Giuseppe Larosa Mon, 05/04/2009 - 01:22

Hello Mahmood,


for the router the ipv4 address is a 32bit integer.

using binary math it compares the address with each prefix


see each prefix as made of a prefix and a subnet mask

the router finds with an exor what prefixes match and from the prefix length it knows what is the most specific


Hope to help

Giuseppe



mahmoodmkl Mon, 05/04/2009 - 02:31

Hi


Thanks for the reply.


U mean to say that the router is going to perform AND operation with all the subnet masks present in the routing table and the address..?


i didnt understand the line below

see each prefix as made of a prefix and a subnet mask

the router finds with an exor what prefixes match and from the prefix length it knows what is the most specific


Thanks

Mahmood



Giuseppe Larosa Mon, 05/04/2009 - 10:27

Hello Mahmood,

Rick has provided a lot of useful examples.


simply said the longest prefix is the most specific prefix if you think of it in this way you can easily solve doubts.

between a /22 and /24 who is the more specific ?

It is the /24 because it expresses a smaller block of ip addresses :

for a prefix with prefix lenght prefixlen the block of ip addresses is expressed as (the size of the block)


2^M where M=32-prefixlen


So it is 2^8 for a /24 to be compared with

2^10 for a /22.


Hope to help

Giuseppe


mahmoodmkl Mon, 05/04/2009 - 03:34

Hi


I agree that it will prefer the longest prefix..my confusion is why it is not prefering the /22 route..may be i am not able to perform the AND operation correctly.

Can someone please explain.


Thanks

Mahmood

thotsaphon Mon, 05/04/2009 - 04:51

Mahmood,

My confusion is why it is not prefering the /22 route.

Longest prefix is what the router first uses to make forwarding decisions.


Toshi

Richard Burts Mon, 05/04/2009 - 09:02

Mahmood


This is an important but subtle issue. First lets review a basic principle and then lets go through some examples that illustrate how it works using the example that you started with.


Longest prefix is describing how many bits in the destination address match how many bits in the entries in the routing table. So if the routing table has the entries that you describe in your original post (/24, /22, /16, and /8) then /24 is longer than /22, and /22 is longer than /16, and /16 is longer than /8.


I like the example in your original post of 10.52.20.10 and the best fit (longest prefix match) was 10.50.20.0/24. So let us consider a few more examples: what if the destination address was 10.50.22.16? This does not match 10.50.20.0/24 but it does match 10.50.20.0/22 so this is the longest match and is the entry in the routing table that would be used.


And what if the destination address were 10.50.40.67? It does not match either 10.50.20.0/24 or 10.50.20.0/22 and it does match 10.50.0.0/16 so this is the longest match and is the entry in the routing table that will be used.


And what if the destination address were 10.90.23.46? It does not match 10.50.20.0/24 or 10.50.20.0/22, or 10.50.0.0/16 and it does match 10.0.0.0/8. So this is is the longest match and is the entry in the routing table that will be used.


[edit] in re-reading this thread I notice this part of your question:"

I agree that it will prefer the longest prefix..my confusion is why it is not prefering the /22 route". The answer is that it would match both /22 and /24 and that /24 is longer than /22.


HTH


Rick

mahmoodmkl Mon, 05/04/2009 - 22:42

Hi,


Rick thanks for the reply..can u please explain the below line..


Longest prefix is describing how many bits in the destination address match how many bits in the entries in the routing table.


Thanks

Mahmood



Richard Burts Tue, 05/05/2009 - 08:43

Mahmood


I was trying to express the concept of how many bits of the destination address are exact matches for bits in the entries in the routing table. So to use your original example of 10.50.20.10, does this address match 8 (10.0.0.0), or does it match 16 (10.50.0.0), or does it match 22 (10.50.20.0) or does it match 24 (10.50.20.0)? Since the first 24 bits or the address are an exact match for an entry in the routing table then /24 is the longest prefix match.


HTH


Rick

lamav Tue, 05/05/2009 - 09:03

Mahmood:


00001010.00000000.00000000.00000000 ===> 10.0.0.0/8



00001010.00110010.00000000.00000000 ===> 10.50.0.0/16



00001010.00110010.00010100.00000000 ===> 10.50.20.0/22



00001010.00110010.00010100.00000000 ===> 10.50.20.0/24




00001010.00110010.00010100.00001010 ===> 10.50.20.10



Now, compare the destination address of 10.50.20.10 BIT-FOR-BIT with the routes in the routing table. It is clear that the longest match occurs between the destination address and 10.50.20.0/24. Yes, it is true that it also matches 10.50.20.0/22, BUT ONLY ON 22 BITS. The 4th choice, 10.50.20.0/24 will allow the 23rd and 24th bit of the destination address to be compared with it and it will also have an exact match with the route's 23rd and 24th bit (0 and 0). Therefore, 10.50.20.0/24 is the longest match.


HTH


Victor

Actions

This Discussion