Longest Prefix Match Routing

Lessons Discussion
1

This topic is to discuss the following lesson:

2

Isn’t the exact order that Router checks which path to take is:

  1. Prefix Length
  2. AD
  3. Metric

I have tested the first 2 and this seems correct.

https://knowledgebase.paloaltonetworks.com/KCSArticleDetail?id=kA14u000000oMNgCAM&lang=en_US
#:~:text=Administrative%20Distance%20-%20Multiple%20routes%20to,Administrator%20Distance)%20will%20take%20precedence.

3

Hello Robert

The order is indeed AD, Metric, and then prefix length. A router uses the AD and the metric to determine which route ends up being installed in the routing table. The prefix length is then used to determine which of the already installed routes in the routing table will be used to route a particular packet. AD and metric necessarily come before the prefix length. Consider this:

Administrative Distance - When a router learns about a specific route from two or more different sources, it must choose which source to use. This is done by looking at the AD value. The source with the lowest AD is installed in the routing table. All other sources never enter the routing table.

Metric - When a router learns about multiple routes to a specific destination from the same source (i.e. OSPF), it must decide which to install in the routing table. This is determined by the metric. The lower metric wins. If the metric is the same, then depending on the routing protocol used, equal cost load balancing is performed.

Prefix length - As stated in the lesson “Longest prefix match routing is an algorithm where the router prefers the longest prefix in the routing table. In other words, the most specific prefix.” But in order to choose the most specific prefix, the candidate prefixes must be in the routing table! And this is why AD and metric come first and second.

I hope this has been helpful!

Laz

2 Likes
4

Thanks for the answer!

Does it work differently for Static Routes and Dynamic Routes?

For the Static Routes I am getting the following:
image

5

Hello Robert

No, it works exactly the same way.

However, let me clarify. In my previous post, I mentioned that AD and metric are used to determine if a route will enter the routing table or not. This is indeed the case, however, this is only valid when the destinations are identical. For example, a router learns of the following networks via the routing protocols indicated:

  • 192.168.2.0/24 using EIGRP gives next hop IP of 10.10.10.1
  • 192.168.2.0/24 using OSPF gives next hop IP of 10.10.20.1
  • 192.168.2.0/24 using Static with a metric of 5 gives next hop IP of 10.10.30.1
  • 192.168.2.0/24 using Static with a metric of 10 gives next hop IP of 10.10.40.1

Out of all of these, the static routes have the lowest AD, and between those two static routes, it is the route with the smallest metric that will be installed in the routing table. So there will be only one entry in the routing table like so:

S 192.168.2.0/24 [1/5] via 10.10.30.1

However, if you have the following networks advertised:

  • 192.168.2.0/24 using EIGRP gives next hop IP of 10.10.10.1
  • 192.168.2.0/25 using OSPF gives next hop IP of 10.10.20.1
  • 192.168.2.0/26 using Static with a metric of 5 gives next hop IP of 10.10.30.1
  • 192.168.2.0/27 using Static with a metric of 10 gives next hop IP of 10.10.40.1

All four of them will be in the routing table! This is because they are considered different routes because they have different prefix sizes. So any packet that is destined for 192.168.2.1 must choose between those four installed routes. How does it choose which is the best route for a particular destination?

For routes installed in the routing table, the prefix length is always used first to match, regardless of AD or metric.

In the routing table you shared, you see two static routes to 192.168.2.0/24 and 192.168.2.0/29. These are considered two different routes because they specify a different range of addresses. For this reason, they are both put into the routing table. Now I notice that they have different metrics and that’s fine too. If they were the same route (same network address and prefix), then only the one with the lowest metric would be installed. But here they’re two different routes.

So, when a packet destined for 192.168.2.1 arrives on this router, how is it routed? It will match the longest prefix, which is 192.168.2.0/29 so it will be forwarded to 192.168.0.2.

More detailed information on this process can be found at the following Cisco documentation:

I hope this has been helpful!

Laz

2 Likes
6

Hi @lagapidis

To Summarise:

  1. If a route to a given destination is learnt via multiple routing sources including static routes, it’s always the static routes that end up on the routing table. All other sources are discarded.

  2. When there are multiple static routes for the same destination with different metric values, the route with the lowest metric is installed on the routing table.

  3. When a router learns a route to a specific destination via multiple routing protocols, AD becomes the tie-breaker to install a specific route from a specific source.

  4. When a router learns a route to a specific destination via the same source (say OSPF), then metric value is used to determine the route that will be installed in the routing table.

The longest prefix match is only to determine the route from the routing table. Also, there can’t exist duplicate entries within the routing table, so longest prefix match is usually applicable for determining the routing entry (inevitably the network) to which the packet will be forwarded?

Is my understanding correct?

Thanks,
Adi

7

Hello Adhithya

Yes, that is correct, assuming the default ADs are used.

Yes, this is correct.

Yes this too is correct.

Yes. If the metric is the same for multiple routes, then you may have equal cost multipath routing depending on how the particular routing protocol is configured.

For the most part yes, but let me clarify a couple of things.

  1. If you have two entries, such as the following in a routing table:
S        192.168.2.0/24 [1/0] via 192.168.1.4
S        192.168.2.64/27 [1/0] via 192.168.1.3

…they are considered two different entries in the routing table. So any packet destined for 192.168.2.66 will match both, but will be routed using the second entry since it has a longer prefix (/27 compared to /24). So in this case, yes, the longest prefix will determine the entry that will be matched.

  1. Duplicate entries can exist in the routing table, assuming the same source (i.e. EIGRP) and the same metric. In such a case you would have equal cost multipath routing. OSPF as well as EIGRP can be configured to allow such routing. The following routing table example shows how multiple OSPF entries to the same destination may appear if they have an equal cost:
Router# show ip route

Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route, H - NHRP, l - LISP
       a - application route
       + - replicated route, % - next hop override

Gateway of last resort is not set

      10.0.0.0/24 is variably subnetted, 2 subnets, 2 masks
O        10.1.1.0/24 [110/20] via 192.168.1.2, 00:00:22, FastEthernet0/0
                     [110/20] via 192.168.2.2, 00:00:22, FastEthernet0/1

More information on how the routing table is populated, and how entreis are matched, take a look at these two NetworkLessons notes:

I hope this has been helpful!

Laz

1 Like
8

Thank You so much. Loved the way you have explained with screenshots.
Duplicates can exist if the route is learnt via same source with same metrics since the AD will be the same.

Regards,
Adi

1 Like