Longest Prefix Match Routing

ReneMolenaar · March 31, 2022, 1:29pm

This topic is to discuss the following lesson:

ITSubs · January 31, 2023, 6:38pm

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

Prefix Length
AD
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.

lagapidis · February 2, 2023, 6:31am

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

ITSubs · February 2, 2023, 3:18pm

Thanks for the answer!

Does it work differently for Static Routes and Dynamic Routes?

For the Static Routes I am getting the following:

lagapidis · February 6, 2023, 6:54am

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

adisprobox · March 5, 2024, 4:15am

Hi @lagapidis

To Summarise:

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.
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.
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.
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

lagapidis · March 6, 2024, 9:37am

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.

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.

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

adisprobox · March 7, 2024, 6:49am

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

sainiranjan.gurijala · May 12, 2024, 5:03am

What if both OSPF and EIGRP have same administrative distance (90) and advertising routes with same prefix length (192.168.0.0/24 or 192.168.0.0/24), what route (protocol) would be selected? And why?

R2#show ip protocols
*** IP Routing is NSF aware ***

Routing Protocol is "ospf 1"
  Outgoing update filter list for all interfaces is not set
  Incoming update filter list for all interfaces is not set
  Router ID 2.2.2.2
  Number of areas in this router is 1. 1 normal 0 stub 0 nssa
  Maximum path: 4
  Routing for Networks:
  Routing on Interfaces Configured Explicitly (Area 0):
    Loopback0
    GigabitEthernet0/0
  Passive Interface(s):
    GigabitEthernet0/1
    GigabitEthernet0/2
    GigabitEthernet0/3
    Loopback0
    RG-AR-IF-INPUT1
  Routing Information Sources:
    Gateway         Distance      Last Update
    1.1.1.1               90      00:00:06
  Distance: (default is 90)

Routing Protocol is "eigrp 1"
  Outgoing update filter list for all interfaces is not set
  Incoming update filter list for all interfaces is not set
  Default networks flagged in outgoing updates
  Default networks accepted from incoming updates
  EIGRP-IPv4 Protocol for AS(1)
    Metric weight K1=1, K2=0, K3=1, K4=0, K5=0
    Soft SIA disabled
    NSF-aware route hold timer is 240
    Router-ID: 2.2.2.2
    Topology : 0 (base)
      Active Timer: 3 min
      Distance: internal 90 external 170
      Maximum path: 4
      Maximum hopcount 100
      Maximum metric variance 1

  Automatic Summarization: disabled
  Maximum path: 4
  Routing for Networks:
    10.0.0.0
    192.168.1.0
  Passive Interface(s):
  Passive Interface(s):
    Loopback0
  Routing Information Sources:
    Gateway         Distance      Last Update
    10.0.0.1              90      00:31:51
  Distance: internal 90 external 170

Router 1 config

interface Loopback0
 ip address 192.168.0.1 255.255.255.0
 ip ospf network point-to-point
 ip ospf 1 area 0
!
interface GigabitEthernet0/0
 ip address 10.0.0.1 255.255.255.0
 ip ospf network point-to-point
 ip ospf 1 area 0
!
router eigrp 1
 network 10.0.0.0
 network 192.168.0.0
 passive-interface default
 no passive-interface GigabitEthernet0/0
 eigrp router-id 1.1.1.1
!
router ospf 1
 router-id 1.1.1.1
 passive-interface default
 no passive-interface GigabitEthernet0/0
 distance 90

Router 2 Config

interface Loopback0
 ip address 192.168.1.1 255.255.255.0
 ip ospf network point-to-point
 ip ospf 1 area 0
!
interface GigabitEthernet0/0
 ip address 10.0.0.2 255.255.255.0
 ip ospf network point-to-point
 ip ospf 1 area 0
!
router eigrp 1
 network 10.0.0.0
 network 192.168.1.0
 passive-interface default
 no passive-interface GigabitEthernet0/0
 eigrp router-id 2.2.2.2
!
router ospf 1
 router-id 2.2.2.2
 passive-interface default
 no passive-interface GigabitEthernet0/0
 distance 90

lagapidis · May 13, 2024, 6:51am

Hello Sai

If you have configured two routing protocols like OSPF and EIGRP to be assigned the same administrative distance, then a Cisco IOS router will choose the protocol that has the lowest DEFAULT administrative distance.

So if you configure OSPF and EIGRP to both have an administrative distance of 90, the router must still choose between them. EIGRP has a default AD of 90 while OSPF has a default AD of 110. So a Cisco IOS router will prefer the EIGRP route over the OSPF route, even though the ADs are configured to be the same. More on this can be found in this NetworkLessons note.

I hope this has been helpful!

Laz

sainiranjan.gurijala · May 14, 2024, 2:27am

Thank you very much. It’s helpful.