16  Longest Prefix Matching

In 60 Seconds

Longest prefix matching is how routers select routes when multiple entries match a destination: the most specific route (longest subnet mask) always wins. A /24 route always beats a /8 route regardless of metrics. This chapter walks through step-by-step route lookup examples and common misconceptions.

This chapter focuses on how routers select which route to use when multiple matches exist. The key algorithm is longest prefix matching - routers always choose the most specific route available.

Key concept: Think of it like addressing a letter. “123 Main Street, Anytown, USA” is more specific than “Anytown, USA” which is more specific than “USA”. Routers work the same way - more specific routes always win.

If you need foundational routing concepts first, see:

“Longest prefix matching sounds complicated, but it is actually simple,” said Sammy the Sensor. “When a router gets a packet, it checks its routing table for matching routes. If multiple routes match, it picks the most specific one – the one with the longest subnet mask.”

“Think of it like mailing a letter,” explained Max the Microcontroller. “If you write ‘USA’ on the envelope, the post office knows which country. But if you write ‘Springfield, Illinois, USA’, the post office can deliver it to a specific city. The more specific address always wins.”

“In routing terms, 192.168.1.0/24 is more specific than 192.168.0.0/16,” added Lila the LED. “Even if the /16 route has a lower metric, the /24 route wins because it is more specific. This is the number one misconception students have – they think lower metrics always win, but prefix length is king!”

“For IoT gateway routers, this matters when you have a default route (0.0.0.0/0) and specific routes to your sensor subnets,” said Bella the Battery. “Traffic to your sensors uses the specific route, and everything else goes through the default route to the internet.”

16.1 Learning Objectives

By the end of this chapter, you will be able to:

  • Apply longest prefix matching to determine next-hop routers using routing table lookups
  • Justify route specificity explaining why /24 routes beat /8 routes regardless of metrics
  • Trace routing decisions step-by-step through a router’s forwarding algorithm
  • Refute common misconceptions demonstrating that prefix length always overrides metrics

16.2 Prerequisites

Required Chapters:

Technical Background:

  • CIDR notation (e.g., 192.168.1.0/24)
  • Routing table structure
  • Next-hop forwarding concepts

Estimated Time: 30 minutes

The Misconception: Many networking students believe that routers always prefer routes with lower metrics (administrative distance or cost values), regardless of other factors. This leads to confusion when a route with metric 100 is chosen over a route with metric 10.

Why It’s Wrong: Longest prefix match ALWAYS takes precedence over metrics. Routers only compare metrics when choosing between routes with identical prefix lengths. Specificity (prefix length) beats cost (metric) every time.

Real-World Impact: In a 2019 enterprise network outage, a network administrator configured a default route (0.0.0.0/0) with metric 10 and a specific route (10.0.0.0/8) with metric 100, expecting traffic to prefer the lower-metric default route. Instead, all traffic to 10.x.x.x destinations correctly used the /8 route due to longest prefix match. When the administrator “fixed” the issue by deleting the /8 route, ~5,000 office IoT devices lost connectivity to their cloud management platform (10.20.30.40), causing a 4-hour outage affecting building access, HVAC, and lighting systems.

The Numbers:

  • Outage duration: 4 hours (until /8 route restored)
  • Devices affected: 5,000+ IoT sensors and controllers
  • Estimated cost: $250,000 in lost productivity and emergency contractor fees
  • Root cause: Misunderstanding routing algorithm precedence (prefix length -> metric -> administrative distance)

How to Think About It: Routing decision hierarchy: 1. First: Longest prefix match (most specific route wins) 2. Second: Metric comparison (only for equal-length prefixes) 3. Third: Administrative distance (only for equal prefix + equal metric from different protocols)

Routes with different prefix lengths never compare metrics. A /32 route with metric 1000 beats a /8 route with metric 1.

Correct Mental Model:

Destination: 10.20.30.40

Route A: 10.20.30.0/24 via 192.168.1.1 metric 100
Route B: 10.0.0.0/8 via 192.168.2.1 metric 10
Route C: 0.0.0.0/0 via 192.168.3.1 metric 1

Winner: Route A (/24 is most specific)
Metrics 100, 10, and 1 are NEVER compared!

16.3 Routing Table Lookup Fundamentals

Scenario: Your IoT gateway has learned routes from multiple sources and must forward a sensor packet to destination 172.16.50.100. The routing table shows three possible matches with different prefix lengths.

Think about:

  1. Why does the router choose the /24 route instead of the /12 or /0 routes?
  2. How does longest prefix matching ensure packets reach the most specific destination?

Key Insight: Routers always select the most specific (longest prefix) matching route. The /24 route matches 24 bits (more specific than /12’s 12 bits or /0’s 0 bits), directing packets to next hop 10.0.0.2. This ensures fine-grained routing control - like preferring a street address over just a city name.

Verify Your Understanding:

  • What happens when you remove the /24 route - which route becomes the next choice?
  • How do default routes (0.0.0.0/0) serve as a “catch-all” for internet-bound traffic?

16.4 Interactive: Prefix Length Comparator

Use this tool to explore how prefix length determines route selection:

16.5 Longest Prefix Match vs Metrics

Scenario: A smart building’s IoT gateway monitors 200 temperature and humidity sensors across two floors. The gateway sends environmental data to Google Cloud Platform (8.8.8.8 for DNS lookups). Your network administrator has configured a special route to optimize traffic to Google’s infrastructure (8.0.0.0/8) through a dedicated peering connection (10.0.0.5), while maintaining a default route (10.0.0.1) for general internet traffic.

Router’s Routing Table:

Destination        Next Hop     Interface  Metric  Type
192.168.1.0/24     Connected    eth0       0       C
192.168.2.0/24     Connected    eth1       0       C
8.0.0.0/8          10.0.0.5     eth1       20      S
0.0.0.0/0          10.0.0.1     eth1       100     S

A sensor at 192.168.1.50 sends a DNS query to 8.8.8.8 (Google Public DNS). The router must decide which path to use.

Think about:

  1. Which routes in the table match the destination 8.8.8.8?
  2. Between matching routes, how does the router choose the best one?
  3. Does the metric difference (20 vs 100) influence the decision, or does something else take precedence?

Key Insight: Longest prefix match ALWAYS wins over metric. When multiple routes match a destination, routers choose the most specific route (longest prefix) regardless of metric. Here, both 8.0.0.0/8 and 0.0.0.0/0 match 8.8.8.8, but /8 is more specific than /0. Metrics only matter when comparing routes with identical prefix lengths. Result: Traffic goes via 10.0.0.5 (8.0.0.0/8 route, metric 20) - not via 10.0.0.1 despite the metric difference.

Step-by-Step Forwarding Decision:

Step 1: Packet arrives at router
-- Source: 192.168.1.50 (temperature sensor)
-- Destination: 8.8.8.8 (Google DNS)
-- Router examines DESTINATION IP only (source irrelevant for forwarding)

Step 2: Search routing table for matching routes
-- 192.168.1.0/24 on eth0? -> NO (8.8.8.8 not in 192.168.1.0-192.168.1.255)
-- 192.168.2.0/24 on eth1? -> NO (8.8.8.8 not in 192.168.2.0-192.168.2.255)
-- 8.0.0.0/8 via 10.0.0.5? -> YES (8.8.8.8 in 8.0.0.0-8.255.255.255)
-- 0.0.0.0/0 via 10.0.0.1? -> YES (default matches ALL addresses)

Step 3: Two routes match - apply longest prefix match
-- Route A: 8.0.0.0/8 -> prefix length = 8 bits
-- Route B: 0.0.0.0/0 -> prefix length = 0 bits
-- 8 > 0, so 8.0.0.0/8 is MORE SPECIFIC

Step 4: Select most specific route
-- Winner: 8.0.0.0/8 via 10.0.0.5
-- Forward to next hop: 10.0.0.5
-- Out interface: eth1

Metric comparison NOT NEEDED (different prefix lengths)

Why Longest Prefix Match Beats Metrics:

Flowchart showing longest prefix match priority for packet destined to 8.8.8.8: router finds two matching routes (8.0.0.0/8 metric 20 and 0.0.0.0/0 metric 100), compares prefix lengths (8 bits vs 0 bits), selects 8.0.0.0/8 as winner, and forwards to 10.0.0.5 without comparing metrics

Flowchart diagram
Figure 16.1: Longest prefix match priority flowchart: prefix length always beats metric in route selection.

Why This Route Configuration?

What is the quantitative benefit of using a dedicated Google peering route versus the default internet gateway?

IoT sensor traffic characteristics:

  • 200 sensors sending readings to Google Cloud Storage every 60 seconds
  • Payload per reading: 500 bytes (temperature, humidity, timestamp, device ID)
  • DNS lookups to 8.8.8.8: 1 per minute (for NTP time sync)

Via Google peering (8.0.0.0/8 → 10.0.0.5):

  • Latency per packet: 5-10 ms (direct peering)
  • Data volume: \(\frac{200 \times 500 \text{ bytes}}{60 \text{ sec}} = 1.67 \text{ KB/sec} = 13.3 \text{ kbps}\)
  • Bandwidth utilization: \(\frac{13.3 \text{ kbps}}{1 \text{ Gbps}} = 0.0013\%\) (plenty of headroom)
  • Round-trip time (RTT): \(2 \times 7 \text{ ms} = 14 \text{ ms}\)

Via default gateway (0.0.0.0/0 → 10.0.0.1):

  • Latency per packet: 20-50 ms (15 hops through internet)
  • Bandwidth utilization: \(\frac{13.3 \text{ kbps}}{100 \text{ Mbps}} = 0.013\%\)
  • Round-trip time (RTT): \(2 \times 35 \text{ ms} = 70 \text{ ms}\)

Impact on sensor responsiveness:

  • Google peering: 14 ms RTT means acknowledgment received in 0.014 seconds
  • Default route: 70 ms RTT = 0.070 seconds (5x slower)
  • For time-critical building automation (HVAC adjustments), 56 ms difference enables:
    • \(\frac{1}{0.070} \approx 14\) updates/second (default route)
    • \(\frac{1}{0.014} \approx 71\) updates/second (Google peering) = 5x faster response

Cost-benefit calculation:

  • Google peering cost: $500/month dedicated connection
  • Data volume: \(13.3 \text{ kbps} \times 2.6 \times 10^6 \text{ sec/month} / 8 \approx 4.3 \text{ GB/month}\)
  • Alternative (shared link): \(4.3 \text{ GB} \times \$0.12/\text{GB} = \$0.52/\text{month}\)
  • Premium paid: \(\$500 - \$0.52 = \$499.48\) for 5x latency improvement

Key insight: The 8.0.0.0/8 specific route provides 5x lower latency at a fixed monthly cost. For latency-sensitive IoT applications (building automation, industrial control), the dedicated peering justifies the premium. For non-latency-sensitive applications (daily sensor readings), the default route’s $0.52/month cost is more appropriate.

Optimized Traffic Engineering:

ISP peering arrangement:
-- Google peering via 10.0.0.5 (8.0.0.0/8)
   -- Direct connection to Google's network
   -- Lower latency: 5-10ms (1-2 hops to Google)
   -- Higher bandwidth: Dedicated 1Gbps link
   -- Better for GCP traffic (Cloud Storage, Compute Engine, DNS)

-- Default internet via 10.0.0.1 (0.0.0.0/0)
   -- General internet gateway
   -- Higher latency: 20-50ms (10-15 hops)
   -- Shared bandwidth: 100Mbps
   -- For all other destinations (AWS, Azure, general websites)

Verify Your Understanding:

  • If you remove the 8.0.0.0/8 route, where does traffic to 8.8.8.8 go? (Via default route 10.0.0.1 - now the only match)
  • If two routes both have /24 prefix but different metrics, which wins? (Lower metric wins - only when prefix lengths are equal)
  • Does the source IP (192.168.1.50) influence forwarding? (No - routers only examine destination IP for forwarding decisions)
Show Routing Algorithm Details

Routing Decision Algorithm:

def forward_packet(dest_ip, routing_table):
    """
    Router forwarding decision using longest prefix match.
    Metrics only matter when prefix lengths are equal.
    """
    # Step 1: Find all matching routes
    matching_routes = []
    for route in routing_table:
        if dest_ip_in_network(dest_ip, route.network, route.prefix_len):
            matching_routes.append(route)

    if not matching_routes:
        return "DROP"  # No route to destination

    # Step 2: Find longest prefix length
    max_prefix_len = max(r.prefix_len for r in matching_routes)

    # Step 3: Filter to only longest prefix routes
    longest_prefix_routes = [r for r in matching_routes
                             if r.prefix_len == max_prefix_len]

    # Step 4: If multiple routes with same longest prefix, compare metrics
    if len(longest_prefix_routes) > 1:
        best_route = min(longest_prefix_routes, key=lambda r: r.metric)
    else:
        best_route = longest_prefix_routes[0]

    return f"Forward to {best_route.next_hop} via {best_route.interface}"

# Apply to scenario
routes = [
    Route("192.168.1.0/24", None, "eth0", 0),
    Route("192.168.2.0/24", None, "eth1", 0),
    Route("8.0.0.0/8", "10.0.0.5", "eth1", 20),
    Route("0.0.0.0/0", "10.0.0.1", "eth1", 100)
]

result = forward_packet("8.8.8.8", routes)
# Output: "Forward to 10.0.0.5 via eth1"

Prefix Length Hierarchy (Specificity):

Most specific -> Least specific:

/32 = 255.255.255.255  (1 host - e.g., 8.8.8.8/32)
/24 = 255.255.255.0    (256 hosts - e.g., 8.8.8.0/24)
/16 = 255.255.0.0      (65,536 hosts - e.g., 8.8.0.0/16)
/8  = 255.0.0.0        (16,777,216 hosts - e.g., 8.0.0.0/8)
/0  = 0.0.0.0          (4,294,967,296 hosts - default route)

Router always chooses most specific match (longest prefix).

When Metrics Matter:

Scenario: Two equal-prefix routes
-- Route A: 8.0.0.0/8 via 10.0.0.5 metric 20
-- Route B: 8.0.0.0/8 via 10.0.0.6 metric 100

Forwarding decision:
1. Both match 8.8.8.8
2. Both have /8 prefix (equal specificity)
3. Compare metrics: 20 < 100
4. Choose Route A (lower metric wins)

Result: Forward to 10.0.0.5

When Metrics DON’T Matter:

Scenario: Different-prefix routes (current example)
-- Route A: 8.0.0.0/8 via 10.0.0.5 metric 20
-- Route B: 0.0.0.0/0 via 10.0.0.1 metric 100

Forwarding decision:
1. Both match 8.8.8.8
2. Different prefix lengths: /8 vs /0
3. Longest prefix wins: /8 > /0
4. Metrics NOT compared (different specificity)

Result: Forward to 10.0.0.5 (regardless of metrics)

Key Takeaway: Longest prefix match ensures traffic takes the most specific route available, enabling sophisticated traffic engineering. ISPs and enterprises use this to optimize traffic to major cloud providers while maintaining default routes for everything else. Metrics only matter when choosing between equally-specific routes (same prefix length).

16.6 Route Summarization

Route summarization reduces routing table size and protocol overhead - especially important for IoT gateways managing many sensor networks.

## Key Concepts

  • Longest Prefix Match: Router algorithm that selects the most specific (longest prefix) matching route for any destination
  • Prefix Length: Number of bits in the network portion of a CIDR address (e.g., /24 = 24 bits)
  • Route Specificity: More specific routes (longer prefixes) always take precedence over less specific ones
  • Default Route: The 0.0.0.0/0 route that matches all destinations - used when no more specific route exists
  • Metric: Cost value used to compare routes only when prefix lengths are equal
  • Route Summarization: Combining multiple specific routes into a single aggregate route to reduce table size

Common Pitfalls

Reading about routing protocols is much less effective than configuring them. For each protocol reviewed (RIP, OSPF, RPL), configure it in a simulator to reinforce conceptual understanding.

Fundamental routing concepts from enterprise networking apply to IoT but with different constraints. For each concept reviewed, identify how IoT device limitations (RAM, CPU, battery) modify its practical application.

Routing metrics (ETX, RANK, composite metrics) involve calculations that must be understood, not memorized. Review the mathematical basis of each metric to build intuition for routing protocol behavior.

16.7 Summary

Longest prefix matching is the fundamental algorithm routers use to select routes:

  1. Specificity wins: A /24 route always beats a /8 route, regardless of metrics
  2. Metrics are secondary: Only compared when prefix lengths are identical
  3. Default route is last resort: 0.0.0.0/0 matches everything but loses to any more specific route
  4. Route summarization: Combines contiguous subnets to reduce table size (four /24s = one /22)

Understanding this algorithm prevents common misconfigurations where administrators expect low-metric routes to win over high-metric specific routes.

Common Mistake: Expecting Metrics to Override Longest Prefix Match

The Mistake: Network engineers configure a low-metric default route (0.0.0.0/0 with metric 10) and a high-metric specific route (172.16.0.0/16 with metric 100), expecting traffic to prefer the default route due to lower metric. The router instead always uses the /16 route, causing confusion and potential connectivity issues.

Why This Happens: Many networking courses teach “lower metrics are preferred” without emphasizing that prefix length comparison happens BEFORE metric comparison. Students internalize “metric = priority” and forget about longest prefix match.

Real-World Impact:

Case Study: A smart city IoT deployment in Seattle (2020) experienced a critical outage affecting 2,500 traffic cameras and environmental sensors.

Configuration:

# Traffic engineer's intent: "Prefer high-speed internet gateway for most traffic"
ip route 0.0.0.0/0 via 203.0.113.1 metric 10      # Internet gateway (1 Gbps)
ip route 172.16.0.0/16 via 10.0.0.1 metric 100    # Legacy city network (100 Mbps)

# Engineer's assumption: Traffic to 172.16.x.x will use default route (metric 10 < 100)
# Reality: Traffic to 172.16.x.x ALWAYS uses 172.16.0.0/16 route (longest prefix wins)

The Problem:

  • City’s SCADA servers lived in 172.16.0.0/16 legacy network
  • Engineer expected traffic to route via fast internet gateway (metric 10)
  • Router correctly used /16 route (longest prefix match) via slow 100 Mbps link
  • Congestion on 100 Mbps link caused 15-minute latency spikes
  • 2,500 IoT devices couldn’t send telemetry; dashboards showed “all offline”

Outage Duration: 6 hours (until /16 route removed and proper route added)

Cost:

  • Emergency contractor fees: $45,000
  • Traffic signal timing disruption: estimated $120,000 in congestion costs
  • Reputational damage: negative press coverage

The Correct Understanding:

Routing Decision Hierarchy:

1. Longest Prefix Match (PREFIX LENGTH) <- ALWAYS FIRST
   |
2. Metric Comparison (COST) <- ONLY for equal-length prefixes
   |
3. Administrative Distance (TRUST) <- ONLY for equal prefix + equal metric

Worked Example:

Routing Table:

Destination        Next Hop      Metric  Prefix Length
0.0.0.0/0          203.0.113.1   10      0 bits
172.16.0.0/16      10.0.0.1      100     16 bits
172.16.50.0/24     10.0.0.2      200     24 bits

Packet to 172.16.50.100:

Step 1: Find Matching Routes

  • 0.0.0.0/0 matches? YES (matches all addresses)
  • 172.16.0.0/16 matches? YES (172.16.50.100 is in 172.16.0.0-172.16.255.255)
  • 172.16.50.0/24 matches? YES (172.16.50.100 is in 172.16.50.0-172.16.50.255)

Step 2: Compare Prefix Lengths (NOT METRICS)

  • 0.0.0.0/0 -> 0 bits
  • 172.16.0.0/16 -> 16 bits
  • 172.16.50.0/24 -> 24 bits <- LONGEST

Winner: 172.16.50.0/24 via 10.0.0.2 (metric 200 is IRRELEVANT)

Metrics are NEVER compared because prefix lengths differ!

Visual Decision Tree:

Packet arrives: Destination 172.16.50.100
|
+- Find all matching routes:
|  +- 0.0.0.0/0 (metric 10) [match]
|  +- 172.16.0.0/16 (metric 100) [match]
|  +- 172.16.50.0/24 (metric 200) [match]
|
+- Compare PREFIX LENGTHS:
|  +- /0 vs /16 vs /24
|  +- /24 is longest (most specific)
|
+- SELECT: 172.16.50.0/24 via 10.0.0.2
   (Metrics 10, 100, 200 NEVER compared!)

When Metrics Matter:

Scenario: Equal-Length Prefixes

Routing Table:
172.16.50.0/24    10.0.0.2    metric 50   (primary)
172.16.50.0/24    10.0.0.3    metric 100  (backup)

Packet to 172.16.50.100:
1. Both routes have /24 prefix (EQUAL length)
2. Compare metrics: 50 < 100
3. Select: 10.0.0.2 (lower metric wins)

How to Avoid This Mistake:

Verification Checklist:

  1. List all matching routes for your destination
  2. Identify longest prefix (highest /XX number)
  3. That route wins - regardless of metrics
  4. Only if prefix lengths are equal -> compare metrics

Configuration Best Practice:

Wrong Approach (expecting metrics to override prefix length):

# This does NOT work as intended
ip route 0.0.0.0/0 via 203.0.113.1 metric 10      # Hoping this catches everything
ip route 172.16.0.0/16 via 10.0.0.1 metric 100    # Ignored for 172.16.x.x destinations!

Correct Approach (if you want all 172.16.x.x traffic via internet):

# Option 1: Don't add the /16 route at all
ip route 0.0.0.0/0 via 203.0.113.1 metric 10      # Catches everything including 172.16.x.x

# Option 2: If /16 route needed, make it explicit
ip route 0.0.0.0/0 via 203.0.113.1 metric 10      # General internet
ip route 172.16.0.0/12 via 10.0.0.1 metric 100    # Use /12 instead of /16 if intent is different range

Debugging Command:

# Check which route the router will actually use
ip route get 172.16.50.100

# Output shows:
# 172.16.50.100 via 10.0.0.2 dev eth1 src 192.168.1.1
#     cache

# This confirms 172.16.50.0/24 route is selected (longest prefix)

Key Takeaways:

  1. Longest prefix ALWAYS wins - regardless of metric values
  2. Metrics only matter when comparing routes with EQUAL prefix lengths
  3. More specific routes (longer prefixes) override less specific routes even with worse metrics
  4. Test your routing expectations with ip route get <destination> before deploying
  5. Document routing intent clearly so future admins don’t misinterpret metric values

16.8 What’s Next

Previous Up Next
Routing Fundamentals Routing Fundamentals Routing Convergence

Now that you understand how routers select routes, the next chapter explores distance vector convergence and TTL-based loop prevention - critical concepts for understanding how routing protocols stabilize after topology changes.

This chapter builds upon:

This chapter connects to:

Real-world applications:

  • Configuring specific routes for IoT sensor subnets
  • Traffic engineering via route aggregation
  • Troubleshooting “destination unreachable” errors
  • Designing hierarchical addressing for large deployments

Algorithm Details:

  • CIDR Calculator: CIDR.xyz
  • Longest Prefix Match Tutorial: GeeksforGeeks
  • Trie Data Structures: Used for efficient LPM in hardware routers

Tools:

Related Topics:

Continue to: Routing Review: Convergence and Loop Prevention