Routing Fundamentals

Longest Prefix Match

Sections: 

Overview: 

  • The longest prefix match is a fundamental routing concept that refers to the process a router uses to determine the best possible route for a packet based on the most specific match between the packet's destination IP address and the routing table entries
  • The longest prefix refers to the route with the most bits that match the destination address
  • Longest Prefix Match Importance:
    • Ensures precision in routing 
      • Supports subnetting and summary routes

      How Longest Prefix Match Works

      Scenario: In this scenario, we will compare three routes and determine which route is the longest prefix match for a given destination IP address

      Routes

      • 192.168.1.0/24
      • 192.168.0.0/16
      • 192.168.1.128/25

      Destination IP

      • 192.168.1.130

      Step 1: Convert Routes to Binary 

      • 192.168.1.0/24
        • Binary: 11000000.10101000.00000001.00000000
      • 192.168.0.0/16
        • Binary: 11000000.10101000.00000000.00000000
      • 192.168.1.128/25
        • Binary: 11000000.10101000.00000001.10000000

      Step 2: Convert Destination IP to Binary 

      • 192.168.1.130
        • Binary: 11000000.10101000.00000001.10000010

      Step 3: Choose the Route with the most matching bits (0s and 1s) to the destination IP 

      • 192.168.1.0/24
        • Matches the first 24 bits 
      • 192.168.0.0/16
        • Matches the first 16 bits
      • 192.168.1.128/25
        • Matches the first 25 bits

      Based on the calculation the longest prefix match route for destination IP 192.168.1.130 is 192.168.1.128/25

      Lab Topology

      Scenario: In this lab scenario, I have added routers 4 - 8 for the longest prefix match concept lab

      Configuration

      Notes:

      • I have created 3 static routes onto R4's routing table pointing towards the 10.4.4.0 network that R8 belongs in
      • Longest Prefix Match Steps
        • 10.4.0.0/16
          • Route Binary: 00001010.00000100.00000000.00000000
          • Destination IP Binary: 00001010.00000100.00000100.11111110
        • 10.4.4.0/24
          • Route Binary: 00001010.00000100.00000100.00000000
          • Destination IP Binary: 00001010.00000100.00000100.11111110
        • 10.4.4.0/26
          • Route Binary: 00001010.00000100.00000100.00000000
          • Destination IP Binary: 00001010.00000100.00000100.11111110
      • Examining the following static routes we can predict that the traffic destined to R8 at IP 10.4.4.254 will pass through the 10.4.4.0/24 route as it's the longest prefix match route matching on 24 bits
      • Issuing a traceroute from PC2, we can see that the longest prefix match route R4 chooses to reach R8 is through route 10.4.4.0/24 via next-hop of R5 at IP address 208.45.0.2