Network Layer Overview

When you request a webpage from a server halfway around the world, your data doesn't travel in a straight line. It hops through perhaps 15-20 routers, each one making a decision: "Given where this packet needs to go, what's the best next step?"

These decisions happen billions of times per second across millions of routers worldwide. Each decision must be made in microseconds. And somehow, despite the Internet's vast complexity—with networks constantly failing, recovering, congesting, and changing—packets almost always find their way.

Routing is the network layer function responsible for this remarkable feat. It encompasses:

• Path Determination: Discovering routes through the network topology
• Route Selection: Choosing the best path when multiple options exist
• Route Distribution: Sharing routing information between routers
• Adaptation: Responding to network changes, failures, and congestion

This page introduces routing concepts at the network layer level. Subsequent chapters will explore specific routing protocols (RIP, OSPF, BGP) in exhaustive detail.

Before diving into routing mechanisms, we must distinguish two related but fundamentally different network layer functions that are often confused: routing and forwarding.

Forwarding (Data Plane):

Forwarding is the per-packet operation of moving a packet from input to output:

1. Packet arrives on an incoming interface
2. Router reads the destination IP address from the header
3. Router looks up the destination in its forwarding table
4. Router transmits the packet on the specified outgoing interface

Forwarding happens for every packet and must be extremely fast—modern routers forward billions of packets per second. Forwarding is implemented in specialized hardware (ASICs, FPGAs) in high-end routers.

Routing (Control Plane):

Routing is the network-wide process of determining paths:

1. Routers exchange information about reachable networks
2. Each router builds a complete or partial view of the network topology
3. Routing algorithms compute best paths to each destination
4. Results are installed in the forwarding table

Routing happens in the background—not per-packet, but periodically or when topology changes. Routing is implemented in software, running on the router's general-purpose CPU.

The Relationship:

Routing Process          Forwarding Process
     │                        │
     ├─→ Routing Table ─→ Forwarding Table ─→ Packet Switching
     │        │                  │
     │        │                  └─→ Outgoing Interface
     │        │
     │        └─→ Next Hop IP/Interface for each prefix
     │
     └─→ Routing Protocols (OSPF, BGP, etc.)

Routing produces the knowledge ("how do I reach this network?"); forwarding uses that knowledge for each packet ("which port does this packet exit?").

The routing table is the data structure that stores the router's knowledge about how to reach destination networks. Understanding its structure is fundamental to understanding how routing works.

Core Routing Table Fields:

Every routing table entry contains (at minimum):

Example Routing Table (Simplified):

Destination        Next Hop         Interface    Metric   Type
-----------        --------         ---------    ------   ----
0.0.0.0/0          203.0.113.1      eth0         1        Static
10.0.0.0/8         192.168.1.1      eth1         10       OSPF
10.45.0.0/16       192.168.1.2      eth1         5        OSPF
172.16.5.0/24      192.168.2.254    eth2         20       BGP
192.168.1.0/24     0.0.0.0          eth1         0        Connected
192.168.2.0/24     0.0.0.0          eth2         0        Connected

Route Types Explained:

1. Connected Routes: Networks directly attached to the router's interfaces. Next hop is 0.0.0.0 or implicit—packets are delivered directly.

2. Static Routes: Manually configured by administrators. Simple but don't adapt to failures.

3. Dynamic Routes: Learned from routing protocols (OSPF, RIP, BGP, etc.). Automatically adapt to network changes.

4. Default Route: 0.0.0.0/0 matches everything. Used when no more specific route exists—"gateway of last resort."

Longest Prefix Match:

When multiple entries match a destination, the router selects the one with the longest prefix (most specific match):

Destination IP: 10.45.99.50

0.0.0.0/0     → Matches (0 bits)
10.0.0.0/8    → Matches (8 bits)
10.45.0.0/16  → Matches (16 bits) ← SELECTED

This enables hierarchical routing: more specific routes override more general ones.

Routes can be configured manually (static) or learned automatically (dynamic). Each approach has distinct advantages and trade-offs.

Static Routing:

Administrators manually configure routes on each router:

# Cisco IOS
ip route 10.45.0.0 255.255.0.0 192.168.1.1

# Linux
ip route add 10.45.0.0/16 via 192.168.1.1

Dynamic Routing:

Routers run routing protocols that automatically:

• Discover neighbor routers
• Exchange reachability information
• Compute optimal paths
• Adapt to topology changes

When to Use Each:

Hybrid Approaches:

Most real networks use both:

• Static routes for specific, unchanging destinations
• Default static routes for stub networks
• Dynamic routing for the core network
• Redistributing static routes into dynamic protocols

Dynamic routing protocols use algorithms that fall into three major categories, each with distinct approaches to learning topology and computing paths.

1. Distance Vector Algorithms

Based on the Bellman-Ford algorithm, distance vector protocols share routing tables with neighbors:

• Information Shared: Each router tells neighbors "I can reach network X with cost Y"
• View of Network: Local only—knows distances but not complete topology
• Computation: Iterative—routes improve over time as information propagates
• Example Protocols: RIP ($RIPv1$, $RIPv2$), EIGRP (enhanced hybrid)

Distance Vector Operation:

Router A knows:     Router B knows:
 Network X: cost 2  Network X: cost 5
 Network Y: cost 4  Network Y: cost 1

A tells B: "I can reach X with cost 2"
B calculates: Via A, cost to X = link_cost(B→A) + 2
If this is better than 5, B updates its table

2. Link State Algorithms

Based on Dijkstra's SPF (Shortest Path First) algorithm, link state protocols share link information:

• Information Shared: Each router floods "my links and their costs" to all routers
• View of Network: Complete—every router has full topology map
• Computation: Independent—each router computes shortest paths locally using Dijkstra
• Example Protocols: OSPF, IS-IS

Link State Operation:

Each router floods Link State Advertisements (LSAs):
  Router A: "I have links to B (cost 1), C (cost 3)"
  Router B: "I have links to A (cost 1), C (cost 2), D (cost 1)"
  ...
  
Every router builds complete graph.
Each runs Dijkstra to compute shortest paths to all nodes.
Result: All routers agree on shortest paths (consistent routing).

3. Path Vector Algorithms

Designed for inter-domain routing, path vector protocols share complete path information:

• Information Shared: "To reach X, the path is: A → B → C → X"
• View of Network: Path-level—knows the sequence of autonomous systems
• Computation: Policy-based—paths selected by administrator-defined rules
• Example Protocol: BGP (Border Gateway Protocol)

Path Vector Purpose:

Path vector is used for routing between organizations (Autonomous Systems). It enables:

• Loop prevention (reject paths that include yourself)
• Policy enforcement (prefer certain providers, avoid certain paths)
• Scalability (abstracts internal topology of each AS)

When multiple paths to a destination exist, routers must choose. Routing metrics provide a quantitative basis for this choice—they measure the "cost" or "quality" of a path.

Common Routing Metrics:

Hop Count:

The simplest metric—count how many routers the packet must traverse:

Path A: Source → R1 → R2 → Destination (2 hops)
Path B: Source → R3 → Destination (1 hop)
→ Path B preferred (fewer hops)

Limitation: Doesn't account for link speed. A path with 2 hops over Gigabit Ethernet is far faster than 1 hop over a 56 Kbps dialup link.

Bandwidth-Based Metrics:

OSPF (by default) uses a cost inversely proportional to bandwidth:

$$\text{OSPF Cost} = \frac{\text{Reference Bandwidth}}{\text{Interface Bandwidth}}$$

With a reference of 100 Mbps:

• 10 Mbps link → Cost = 10
• 100 Mbps link → Cost = 1
• 1 Gbps link → Cost = 0.1 → rounded to 1

Composite Metrics:

EIGRP computes a sophisticated metric combining multiple factors:

$$\text{EIGRP Metric} = 256 \times \left( K_1 \times \text{Bandwidth} + \frac{K_2 \times \text{Bandwidth}}{256 - \text{Load}} + K_3 \times \text{Delay} \right) \times \left( \frac{K_5}{\text{Reliability} + K_4} \right)$$

By default, only $K_1$ (Bandwidth) and $K_3$ (Delay) are used, simplifying to:

$$\text{Metric} = 256 \times \left( \frac{10^7}{\text{Bandwidth}_{min}} + \sum{\text{Delays}} \right)$$

where Bandwidth is in kbps and Delay is in tens of microseconds.

The Internet's routing architecture divides the world into Autonomous Systems (ASs)—networks under a single administrative control. Routing operates differently within and between these domains.

Autonomous System (AS):

An AS is a collection of IP networks under a single organization's control with a unified routing policy:

• An ISP is typically one AS
• A large enterprise might be one or more ASs
• Each AS has a globally unique AS Number (ASN)
• ASNs are 16-bit (1-65535) or 32-bit (extended)

Two Routing Scopes:

Interior Gateway Protocols (IGPs) — Intra-Domain:

IGPs operate within a single AS:

• Goal: Find shortest/fastest paths to all networks in the AS
• Assumptions: All routers trust each other, common admin policies
• Metrics: Technical (bandwidth, delay, cost)
• Protocols: OSPF, IS-IS, EIGRP, RIP
• Characteristics: Fast convergence, detailed topology knowledge

Exterior Gateway Protocols (EGPs) — Inter-Domain:

EGPs operate between ASs:

• Goal: Exchange reachability information and enforce policy
• Assumptions: ASs don't fully trust each other, competing interests
• Selection: Policy-based (business relationships, contracts)
• Protocol: BGP (the only EGP in use today)
• Characteristics: Scalability, policy flexibility, deliberate stability

When network topology changes—a link fails, a new route appears, a cost changes—routing protocols must update their tables. Convergence is the process of all routers reaching a consistent, up-to-date view of the network.

Convergence Timeline:

1. Detection: Router notices the topology change (interface down, neighbor timeout, LSA received)
2. Propagation: Information about the change spreads to other routers
3. Computation: Each affected router recalculates routes
4. Installation: New routes installed in forwarding tables
5. Stability: All routers agree; network is converged

Convergence Time Matters:

During convergence:

• Routers may have inconsistent views
• Some routes may be black holes (pointing to failed links)
• Routing loops may temporarily form
• Packets may be dropped or delivered out of order

Faster convergence = shorter outage duration.

Factors Affecting Convergence Speed:

Convergence Problems:

Routing Loops During Convergence:

Before failure:  A → B → C → Destination
Link B→C fails.
A still thinks: B is the path
B knows: C is unreachable, but maybe A knows another path?
B sends to A: "Try reaching destination!"
A sends back to B: "Sure, via you!"
→ Packet loops between A and B until TTL expires

Count-to-Infinity (Distance Vector):

In distance vector protocols, routers may slowly increment metrics until reaching "infinity":

A → B → C (B→C fails)

A thinks: Distance to C = 2 (via B)
B knows: C unreachable
B hears from A: "C is distance 2"
B thinks: Maybe I can reach C via A! Cost = 3
B tells A: "C is distance 3"
A thinks: Cost is now 4
... continues until metric reaches infinity (16 in RIP)

Mitigations:

• Split horizon: Don't advertise back to sender
• Poison reverse: Advertise unreachable back to sender
• Hold-down timers: Delay accepting new information after failure
• Triggered updates: Send immediate updates on change

Routing is what turns a collection of individual networks into the Internet—a globally interconnected system where any host can reach any other. Let's consolidate the key insights:

What's Next:

Routing determines paths; but once a path is determined, packets must actually be moved hop-by-hop. The next page covers packet handling—the operations routers perform on each packet: header processing, TTL management, fragmentation, and the forwarding decision itself.