694 Routing Review: Longest Prefix Matching
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:
- Routing Fundamentals - What routers do, routing table structure
- Routing Connectivity - How routes enable connectivity
694.1 Learning Objectives
By the end of this chapter, you will be able to:
- Apply Longest Prefix Matching: Determine next-hop routers using routing table lookups
- Understand Route Specificity: Explain why /24 routes beat /8 routes for matching destinations
- Debug Routing Decisions: Trace how routers select routes step-by-step
- Avoid Common Misconceptions: Understand that prefix length always beats metrics
694.2 Prerequisites
Required Chapters: - Routing Fundamentals - Core routing concepts - Networking Fundamentals - Network basics
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!694.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?
Question: A router has these routes: - 172.16.0.0/12 via 10.0.0.1 - 172.16.50.0/24 via 10.0.0.2 - 0.0.0.0/0 via 10.0.0.254
For destination 172.16.50.100, which next hop is selected?
Explanation: B. Routers pick the longest prefix match. /24 is more specific than /12 and /0, so the 172.16.50.0/24 route wins and forwards to 10.0.0.2.
694.4 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 SA 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:
Why This Route Configuration?
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.7M hosts - e.g., 8.0.0.0/8)
/0 = 0.0.0.0 (4.3B 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.5When 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).
694.5 Route Summarization
Route summarization reduces routing table size and protocol overhead - especially important for IoT gateways managing many sensor networks.
Question: A gateway routes traffic for four contiguous subnets: 192.168.0.0/24 through 192.168.3.0/24. What is the best single summary route to advertise upstream?
Explanation: C. A /22 covers four /24 networks (4 x 256 addresses). Route summarization reduces routing table size and control-plane overhead - useful for gateways managing many IoT subnets.
694.6 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
694.7 Summary
Longest prefix matching is the fundamental algorithm routers use to select routes:
- Specificity wins: A /24 route always beats a /8 route, regardless of metrics
- Metrics are secondary: Only compared when prefix lengths are identical
- Default route is last resort: 0.0.0.0/0 matches everything but loses to any more specific route
- 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.
694.8 What’s Next
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.
Continue to: Routing Review: Convergence and Loop Prevention