Routing Concepts: How Routers Determine the Best Path

When you send an email from New York to Tokyo, click a link to a website hosted in Frankfurt, or stream a video from a server in Singapore, your data doesn't magically teleport. Instead, it embarks on a journey—hopping across dozens of intermediate networks, traversing undersea cables, satellite links, and fiber optic highways, navigating through congestion and failures, all to arrive at its destination typically within milliseconds.

This remarkable journey is orchestrated by routing—the process by which network devices determine the optimal path for data to travel from source to destination. Routing is to the Internet what air traffic control is to aviation, what GPS navigation is to driving—but operating at a scale and speed that dwarfs both combined.

Every second, the global Internet processes billions of routing decisions. Each packet you send triggers a cascade of independent choices by routers along the way, each making split-second determinations about where to send your data next. Understanding routing is understanding the fundamental mechanism that makes global connectivity possible.

Routing is the process of selecting a path for traffic in a network or between networks. More precisely, it is the mechanism by which routers determine the next destination for each packet, ultimately guiding data from its origin to its final destination across potentially many intermediate networks.

The Formal Definition

Routing is the process by which a router examines the destination address of an incoming packet, consults its routing information base, and determines the optimal outgoing interface and next-hop address for forwarding that packet toward its destination.

This definition contains several critical elements:

1. Destination address examination: Routers make decisions based on the destination IP address in packet headers
2. Routing information base: Routers maintain structured knowledge about network reachability
3. Optimal selection: Among potentially many paths, routers choose based on defined criteria
4. Outgoing interface determination: The physical or logical port through which to send the packet
5. Next-hop identification: The immediate next router or destination in the packet's journey

Why Routing Exists

Routing exists because of a fundamental reality of large-scale networks: no single device can maintain a direct connection to every other device.

Consider the scale:

• The IPv4 Internet has ~4 billion possible addresses
• The IPv6 Internet has ~340 undecillion possible addresses
• The Internet consists of over 70,000 autonomous systems
• An enterprise network might have thousands of subnets

Maintaining direct point-to-point connections between all possible endpoints would be impossible. Instead, we build networks hierarchically, with specialized devices (routers) connecting different network segments and making intelligent decisions about how to forward traffic between them.

One of the most important conceptual distinctions in networking is between routing and forwarding. While often used interchangeably in casual conversation, they represent fundamentally different operations occurring at different timescales and involving different mechanisms.

Routing (Control Plane)

Routing is the process of building and maintaining routing tables. It involves:

• Exchanging reachability information between routers
• Computing optimal paths to all known destinations
• Responding to network topology changes
• Implementing routing policies and preferences

Routing operates on a timescale of seconds to minutes. When a link fails, routing protocols detect this and reconverge—a process that might take anywhere from sub-second (with fast failover) to several minutes (in complex scenarios).

Forwarding (Data Plane)

Forwarding is the act of moving packets from input to output. It involves:

• Receiving a packet on an interface
• Looking up the destination in the forwarding table
• Determining the output interface and next-hop
• Transmitting the packet

Forwarding operates on a timescale of nanoseconds to microseconds. A modern router might forward hundreds of millions of packets per second.

The Relationship

Think of it this way:

• Routing is like planning a road trip—studying maps, choosing which highways to take, deciding on detours for construction. You do this once before (and occasionally during) your journey.

• Forwarding is like driving through an intersection—checking the road sign, turning the wheel, proceeding. You do this constantly, at every decision point.

┌─────────────────────────────────────────────────────────────────┐
│                      ROUTER ARCHITECTURE                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│    ┌─────────────────────────────────────────────────────┐     │
│    │              CONTROL PLANE (Routing)                │     │
│    │                                                     │     │
│    │  ┌──────────┐  ┌──────────┐  ┌──────────────────┐  │     │
│    │  │ Routing  │  │ Routing  │  │    Routing       │  │     │
│    │  │ Protocols│──│Algorithm │──│    Table         │  │     │
│    │  │(OSPF,BGP)│  │(Dijkstra)│  │ (RIB)            │  │     │
│    │  └──────────┘  └──────────┘  └────────┬─────────┘  │     │
│    │                                        │           │     │
│    └────────────────────────────────────────┼───────────┘     │
│                                              │                 │
│                                              ▼                 │
│    ┌─────────────────────────────────────────────────────┐     │
│    │               DATA PLANE (Forwarding)               │     │
│    │                                                     │     │
│    │  ┌──────────┐  ┌──────────────────┐  ┌──────────┐  │     │
│    │  │  Input   │  │    Forwarding    │  │  Output  │  │     │
│    │  │Interface │──│    Table (FIB)   │──│Interface │  │     │
│    │  │          │  │  (Hardware ASIC) │  │          │  │     │
│    │  └──────────┘  └──────────────────┘  └──────────┘  │     │
│    │                                                     │     │
│    └─────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

This architectural separation is fundamental to modern router design and enables both high-performance forwarding and sophisticated routing logic.

When a router receives a packet, it must make a routing decision. This process, while conceptually simple, involves several sophisticated steps that network engineers must deeply understand.

Step-by-Step Routing Decision

Longest Prefix Matching

The most critical step is the forwarding table lookup. Routers use longest prefix matching (LPM) to find the most specific route for a destination.

Consider a router with these forwarding table entries:

Now, for a packet destined for 10.20.30.200:

1. Does it match 0.0.0.0/0? Yes (matches everything) — prefix length: 0
2. Does it match 10.0.0.0/8? Yes — prefix length: 8
3. Does it match 10.20.0.0/16? Yes — prefix length: 16
4. Does it match 10.20.30.0/24? Yes — prefix length: 24
5. Does it match 10.20.30.128/25? Yes (200 ≥ 128) — prefix length: 25

The router selects 10.20.30.128/25 because it has the longest matching prefix (25 bits). The packet is forwarded to 10.4.4.4 via eth4.

What If No Match Is Found?

If no routing table entry matches the destination address:

1. With default route (0.0.0.0/0): Packet is sent to the default gateway
2. Without default route: Router generates an ICMP "Destination Network Unreachable" message and discards the packet

The default route acts as the "route of last resort"—if the router doesn't know a specific path to the destination, it forwards the packet to a router that might know better. This is how most end-user traffic reaches the Internet: local routers have specific routes for local networks and a default route pointing toward their ISP.

A fundamental distinction in routing is between direct delivery and indirect delivery. Understanding this distinction clarifies how packets ultimately reach their destinations.

Direct Delivery

Direct delivery occurs when the destination host is on the same network segment as the sender. No router is needed—the packet is delivered directly at the link layer.

How a host determines direct delivery:

1. Apply the subnet mask to both source and destination addresses
2. If the network portions match, the destination is directly reachable
3. Resolve the destination's MAC address using ARP (IPv4) or Neighbor Discovery (IPv6)
4. Encapsulate and transmit directly to the destination

Example:

• Source: 192.168.1.100/24
• Destination: 192.168.1.200/24
• Network comparison: 192.168.1.0 = 192.168.1.0 ✓
• Result: Direct delivery via ARP resolution

Indirect Delivery

Indirect delivery occurs when the destination is on a different network. The sending host must transmit the packet to a router (typically its default gateway), which then makes routing decisions to move the packet closer to the destination.

How indirect delivery works:

1. Host determines destination is not directly reachable (network IDs don't match)
2. Host looks up its default gateway (router) from its network configuration
3. Host resolves the router's MAC address using ARP/ND (not the final destination's)
4. Packet is sent to the router with:
   • Layer 2 destination: Router's MAC address
   • Layer 3 destination: Final destination's IP address
5. Router receives packet, makes routing decision, forwards toward destination
6. Process repeats at each hop until final network is reached
7. Last router performs direct delivery to final destination

Example:

• Source: 192.168.1.100/24 (default gateway: 192.168.1.1)
• Destination: 8.8.8.8 (Google DNS)
• Network comparison: 192.168.1.0 ≠ 8.0.0.0 ✗
• Result: Send to default gateway for indirect delivery

The global Internet is too vast for a single routing system. Instead, it's organized into Autonomous Systems (AS)—independent routing domains, each under single administrative control.

What is an Autonomous System?

An Autonomous System is a connected group of IP networks under the control of one or more operators that has a single, clearly defined external routing policy. In practical terms:

• An enterprise network is typically one AS
• An ISP is typically one AS
• A large cloud provider might be one AS (or several)
• A university network is typically one AS

Each AS is identified by a unique Autonomous System Number (ASN). Originally 16-bit (allowing 65,536 ASNs), now 32-bit (allowing over 4 billion).

Interior vs. Exterior Routing

The AS structure creates a natural hierarchy for routing:

Interior Gateway Protocols (IGPs)

Routing within an AS. The administrator has full control, can optimize for their specific needs, and trusts all routers in the domain.

• Examples: OSPF, IS-IS, EIGRP (Cisco), RIP
• Optimizes for: Speed, capacity, reliability, low latency
• Scale: Hundreds to thousands of routers
• Trust model: All routers trusted (same organization)

Exterior Gateway Protocols (EGPs)

Routing between ASes. Involves negotiation between different organizations, policy considerations, and commercial relationships.

• Example: BGP (Border Gateway Protocol)—the only EGP in use today
• Optimizes for: Policy compliance, business relationships, security
• Scale: 70,000+ ASes, millions of routes
• Trust model: Limited trust, routes filtered and validated

The Internet's Hierarchical Structure

┌───────────────────────────────────────────────────────────────────────┐
│                         TIER 1 ISPs (Global Backbone)                 │
│    ┌─────────┐    ┌─────────┐    ┌─────────┐    ┌─────────┐          │
│    │ Lumen   │════│  NTT    │════│ Cogent  │════│ GTT     │          │
│    │ AS3356  │    │ AS2914  │    │ AS174   │    │ AS3257  │          │
│    └────┬────┘    └────┬────┘    └────┬────┘    └────┬────┘          │
│         │              │              │              │                │
│         └──────────────┼──────────────┼──────────────┘                │
│                        │              │                               │
│    ════════════════════╪══════════════╪════════════════════           │
│                        │              │                               │
│         TIER 2 ISPs (Regional)        │                               │
│    ┌─────────┐    ┌────┴────┐    ┌────┴────┐                         │
│    │Regional │    │Regional │    │Regional │                         │
│    │  ISP A  │    │  ISP B  │    │  ISP C  │                         │
│    └────┬────┘    └────┬────┘    └────┬────┘                         │
│         │              │              │                               │
│    ═════╪══════════════╪══════════════╪═════════════                  │
│         │              │              │                               │
│         TIER 3 ISPs (Local) / Enterprise / Content                    │
│    ┌────┴────┐    ┌────┴────┐    ┌────┴────┐    ┌─────────┐          │
│    │ Local   │    │Enterprise│   │University│   │ Content │          │
│    │   ISP   │    │ Network │    │ Network │    │Provider │          │
│    └─────────┘    └─────────┘    └─────────┘    └─────────┘          │
│                                                                       │
└───────────────────────────────────────────────────────────────────────┘

Routing within each box: IGP (OSPF, IS-IS)
Routing between boxes: EGP (BGP)

Routers don't inherently know how to reach every destination. They must learn about networks, and this learning happens through several mechanisms.

How Routes Enter a Routing Table

There are three primary ways a router learns about routes:

Administrative Distance

When a router learns about the same destination from multiple sources, it must decide which to trust. This is determined by Administrative Distance (AD)—a measure of the trustworthiness of a routing information source.

Lower AD = More trusted. If the same prefix is learned via both OSPF and BGP, the OSPF route is preferred because OSPF has a lower AD.

This hierarchy reflects practical trust levels—you trust what you configured directly (connected, static) most, then interior protocols (managed within your organization), then exterior protocols (involving other organizations).

What makes a routing system 'good'? Network architects evaluate routing designs against several key properties.

Desirable Routing Properties

Trade-offs in Routing Design

These properties often conflict:

Optimality vs. Stability

The absolutely optimal path might change frequently as network conditions fluctuate. Constantly chasing optimality creates instability. Most routing protocols use dampening mechanisms to avoid hyperreactivity.

Simplicity vs. Optimality

Simple routing (like static routes) is easy to understand but suboptimal. Sophisticated routing (like link-state protocols with traffic engineering) achieves better paths but adds complexity.

Robustness vs. Efficiency

Robust routing requires redundancy—multiple paths, frequent hello messages, state synchronization. This consumes bandwidth and processing resources that could otherwise carry data.

Speed vs. Accuracy

Routers can make fast decisions with incomplete information, or slower decisions with more verification. Fast reconvergence after failures is valuable, but hasty routing can install suboptimal or incorrect routes.

We've established the foundational understanding of what routing is and why it matters. Let's consolidate these concepts:

What's Next

With the conceptual foundation in place, we'll next examine the routing table in detail—the data structure that stores routing decisions and enables routers to make split-second forwarding choices. Understanding routing table structure is essential for troubleshooting, optimization, and protocol comparison.