The Network Layer
Routing Fundamentals
Building the table. Which paths exist, which
JrCodex·8 min read
Jr Codex Computer Networks Notes
Level: Intermediate Prerequisites: Chapter 2: IPv4, IPv6 and Address Exhaustion Time to complete: ~20 minutes
Table of Contents
- Routing vs Forwarding
- The Routing Table
- Longest Prefix Match
- What a Router Actually Does
- Static vs Dynamic Routes
- Route Aggregation
- Summary & Next Steps
1. Routing vs Forwarding
Two Different Activities
─────────────────────────────────────────
ROUTING — the CONTROL PLANE
Building the table. Which paths exist, which
are best. Runs protocols with other routers
(Chapter 4). Slow, periodic, thoughtful.
Milliseconds to seconds.
FORWARDING — the DATA PLANE
Using the table. One packet arrives, look up
its destination, send it out an interface.
Fast, per-packet, mechanical.
Nanoseconds.
─────────────────────────────────────────
Why the Split Matters
─────────────────────────────────────────
Forwarding happens millions of times per second
and is implemented in dedicated HARDWARE.
Routing happens occasionally and runs in SOFTWARE
on the router's CPU.
So a router can have a complex routing protocol
and still forward at line rate — the expensive
thinking is done in advance, and the per-packet
path is a lookup.
It is the same split as a database's query
planning versus execution (DBMS Notes, Module 6).
─────────────────────────────────────────
2. The Routing Table
$ ip route
default via 192.168.1.1 dev eth0 proto dhcp metric 100
10.8.0.0/24 via 192.168.1.5 dev eth0
169.254.0.0/16 dev eth0 scope link metric 1000
192.168.1.0/24 dev eth0 proto kernel scope link src 192.168.1.10Reading an Entry
─────────────────────────────────────────
DESTINATION the network this entry covers
(a prefix, Chapter 1)
NEXT HOP the router to send it to
("via"), or nothing if the network
is directly attached
INTERFACE which physical port to send out of
METRIC the cost — lower wins when two
entries tie
─────────────────────────────────────────
The Two Kinds of Entry
─────────────────────────────────────────
DIRECTLY CONNECTED
192.168.1.0/24 dev eth0
"This network is on the other end of eth0."
ARP for the destination itself (Module 2,
Chapter 4) and deliver directly.
VIA A NEXT HOP
default via 192.168.1.1
"I do not know where this is. Give it to
192.168.1.1, who knows more than I do."
ARP for the NEXT HOP's MAC, not the
destination's.
─────────────────────────────────────────
THE DEFAULT ROUTE
─────────────────────────────────────────
0.0.0.0/0 — a prefix length of ZERO, so it
matches EVERY address.
It is the "everything else" entry, and it is why
your laptop's routing table has four lines rather
than a million: it knows its own LAN, and hands
the rest to the gateway.
Only routers in the internet's core carry a full
table — currently around a million prefixes — and
they have no default route, because there is
nowhere left to send "everything else".
─────────────────────────────────────────
3. Longest Prefix Match
The Rule
─────────────────────────────────────────
When several entries match a destination, use
the one with the LONGEST PREFIX — the most
specific.
Destination: 10.1.5.200
0.0.0.0/0 matches (everything does)
10.0.0.0/8 matches, more specific
10.1.0.0/16 matches, more specific still
10.1.5.0/24 matches, MOST specific ◄── WINS
─────────────────────────────────────────
def longest_prefix_match(dest_ip, table):
"""table: list of (prefix_str, prefix_len, next_hop, interface)."""
d = to_int(dest_ip)
best = None
for prefix, length, next_hop, iface in table:
mask = (0xFFFFFFFF << (32 - length)) & 0xFFFFFFFF if length else 0
if (d & mask) == (to_int(prefix) & mask):
if best is None or length > best[1]: # LONGER prefix wins
best = (prefix, length, next_hop, iface)
return best
table = [
("0.0.0.0", 0, "192.168.1.1", "eth0"), # default
("10.0.0.0", 8, "192.168.1.5", "eth0"),
("10.1.0.0", 16, "192.168.1.6", "eth0"),
("10.1.5.0", 24, "192.168.1.7", "eth0"),
]
print(longest_prefix_match("10.1.5.200", table)) # ('10.1.5.0', 24, ...)
print(longest_prefix_match("10.2.0.9", table)) # ('10.0.0.0', 8, ...)
print(longest_prefix_match("8.8.8.8", table)) # ('0.0.0.0', 0, ...) — defaultWhy This Rule Is Exactly Right
─────────────────────────────────────────
It lets GENERAL rules coexist with SPECIFIC
exceptions, with no ordering and no conflicts.
"Send everything to the ISP, except 10.0.0.0/8
which goes to the VPN, except 10.1.5.0/24 which
goes to the branch office."
Three entries, no priority list, and the correct
answer falls out of the prefix lengths.
It is also what makes route aggregation possible
(Section 6).
─────────────────────────────────────────
4. What a Router Actually Does
Per Packet, In Order
─────────────────────────────────────────
1. RECEIVE the frame. Check the FCS (Module 2,
Chapter 2). Corrupt ──► DISCARD.
2. STRIP the Ethernet header. EtherType 0x0800
──► hand the packet to IP.
3. IS IT FOR ME? Destination IP matches one of my
own ──► process it locally, stop.
4. DECREMENT THE TTL. Now zero ──► DISCARD, and
send ICMP Time Exceeded back to the source
(Chapter 5).
5. LOOK UP the destination with longest prefix
match ──► next hop and interface.
No match and no default ──► DISCARD, send ICMP
Destination Unreachable.
6. CHECK THE MTU of the outgoing interface. Too
big and DF is set ──► DISCARD, send ICMP
Packet Too Big (Module 1, Chapter 3).
7. RECOMPUTE the IP header checksum — the TTL
changed (Chapter 2).
8. RESOLVE the next hop's MAC via ARP, build a
NEW Ethernet frame, and transmit.
─────────────────────────────────────────
WHAT CHANGES AND WHAT DOES NOT
─────────────────────────────────────────
CHANGES at every hop:
source MAC the router's outgoing
interface
destination MAC the next hop's
TTL decremented
header checksum recomputed
NEVER CHANGES:
source IP the original sender
destination IP the final destination
the payload
This is the single most important thing to
understand about routing. IP addresses are
end-to-end; MAC addresses are hop-by-hop.
(NAT breaks this rule deliberately — Chapter 5.)
─────────────────────────────────────────
5. Static vs Dynamic Routes
STATIC
─────────────────────────────────────────
Configured by hand.
+ predictable, no protocol overhead, no CPU cost
+ full administrative control
- does not adapt to failures — a dead link stays
in the table
- does not scale; every change is manual
Right for: default routes, small stub networks,
a deliberate exception to dynamic routing.
DYNAMIC
─────────────────────────────────────────
Routers exchange information and build tables
themselves (Chapter 4).
+ adapts automatically to topology changes
+ scales to enormous networks
- protocol overhead and CPU cost
- convergence time during which routing is wrong
- more to understand and to misconfigure
Right for: anything with redundant paths or more
than a handful of routers.
ADMINISTRATIVE DISTANCE
─────────────────────────────────────────
When two SOURCES offer a route to the same
prefix, which is believed? Lower distance wins.
Directly connected 0
Static route 1
eBGP 20
OSPF 110
RIP 120
So a static route (1) overrides anything OSPF
learns (110) — which is exactly why a
hand-configured route is a reliable override, and
also why a forgotten static route causes
mysterious, persistent misrouting.
─────────────────────────────────────────
6. Route Aggregation
The Problem It Solves
─────────────────────────────────────────
The internet's routing table is around a million
prefixes and grows continuously.
Every core router must hold ALL of it, in fast
memory, and search it for every packet.
Without aggregation it would be far larger and
the internet would not scale.
─────────────────────────────────────────
The Mechanism
─────────────────────────────────────────
An ISP owns four adjacent /24s:
203.0.113.0/24
203.0.113.1.0/24 ← contiguous blocks
203.0.114.0/24
203.0.115.0/24
Rather than advertising four routes, it
advertises ONE:
203.0.112.0/22
Every router elsewhere stores one entry instead
of four. Inside the ISP, the specific /24s are
still known and used.
─────────────────────────────────────────
import ipaddress
nets = [ipaddress.ip_network(n) for n in
["203.0.112.0/24", "203.0.113.0/24", "203.0.114.0/24", "203.0.115.0/24"]]
print(list(ipaddress.collapse_addresses(nets)))
# [IPv4Network('203.0.112.0/22')] — four routes become oneWhy CIDR and Aggregation Are the Same Idea
─────────────────────────────────────────
Aggregation only works because addresses are
allocated HIERARCHICALLY and CONTIGUOUSLY — which
is what CIDR enabled (Chapter 1).
It is also why address blocks are handed out in
large contiguous chunks to ISPs rather than
scattered: scattered allocation cannot be
aggregated, and the global table would explode.
Address policy and routing scalability are the
same problem.
─────────────────────────────────────────
7. Summary & Next Steps
Key Takeaways
- Routing builds the table in software occasionally; forwarding uses it in hardware millions of times a second — the split is what allows complexity and line rate together.
- Longest prefix match lets general rules and specific exceptions coexist without any priority ordering, and the default route's /0 is what keeps ordinary tables tiny.
- At every hop the MAC addresses, TTL and header checksum change while the source and destination IP addresses never do.
- Route aggregation depends on hierarchical contiguous address allocation, which is why address policy and routing scalability are the same problem.
Concept Check
- What changes and what stays the same in a packet as it crosses five routers?
- Why does longest prefix match remove the need for an ordered rule list?
- Why must address blocks be allocated in large contiguous chunks rather than scattered?
Next Chapter
→ Chapter 4: Routing Algorithms
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to Computer Networks Index