The Network Layer & IP Routing

An IP address is a 32-bit (IPv4) or 128-bit (IPv6) number assigned to a network interface, not a machine. A laptop with Wi-Fi and Ethernet has two interfaces, each with its own IP address. The address is not a random identifier — it encodes topology: addresses are allocated in contiguous blocks to organizations, and those blocks are allocated in larger blocks to regions, ISPs, and continents. This hierarchy is what makes routing tables feasible.

An IPv4 address like 192.168.1.42 is written in dotted-decimal notation: four 8-bit octets in base 10 separated by dots. In binary, it is 11000000.10101000.00000001.00101010. The key insight is that the address is split into a network prefix (the high-order bits, shared by all addresses in the same subnet) and a host part (the low-order bits, identifying the specific interface within that subnet).

A subnet mask or prefix length specifies where the split is. The notation /24 means the first 24 bits are the network prefix. The network 192.168.1.0/24 contains 2^8 = 256 addresses (192.168.1.0 through 192.168.1.255). Two interfaces on the same /24 subnet can communicate at layer 2 (Ethernet/ARP) without involving a router. Communication to any other prefix must go through the default gateway (a router).

The brilliant structural property: because addresses are hierarchically allocated, a router in Tokyo does not need a separate entry for every one of the ~4 billion IPv4 addresses. It only needs to know which next hop covers large prefixes — and then let routers closer to the destination worry about the details. This aggregation is what makes global routing tables manageable (around 900,000 prefixes today for IPv4, not 4 billion individual entries).

# Python: parse and inspect an IPv4 address
import ipaddress

net = ipaddress.ip_network('192.168.1.0/24')
print(net.network_address)   # 192.168.1.0
print(net.broadcast_address) # 192.168.1.255
print(net.prefixlen)         # 24
print(net.num_addresses)     # 256

# Check if a host is in the subnet
host = ipaddress.ip_address('192.168.1.42')
print(host in net)           # True

# The subnet mask in dotted form
print(net.netmask)           # 255.255.255.0

Classless Inter-Domain Routing (CIDR), introduced in 1993, replaced the old class-based system (Class A/B/C) with a flexible prefix-length scheme. Before CIDR, the world was divided into a small number of fixed-size blocks: Class A (8-bit prefix, 16 million hosts), Class B (16-bit prefix, 65,536 hosts), Class C (24-bit prefix, 256 hosts). This was catastrophically wasteful — a company needing 300 addresses had to get a Class B (65,536 addresses) and waste almost all of them. CIDR allows any prefix length, so you can allocate exactly a /23 (512 addresses) or a /28 (16 addresses).

Subnetting is the practice of dividing a larger allocated block into smaller pieces for internal organization. An ISP might receive 10.0.0.0/8 and subdivide it into /16 blocks for customers, who further subdivide into /24 blocks for departments. The hierarchy mirrors organizational structure.

Longest-prefix matching (LPM) is the fundamental forwarding rule: when a router looks up a destination address, it matches it against all prefixes in its forwarding table and picks the most specific (longest prefix) match. This is what makes hierarchical allocation work: a router can have both 0.0.0.0/0 (the default route, matches everything) and 192.168.1.0/24 (a specific subnet). A packet to 192.168.1.5 matches both, but the /24 is longer, so it wins. This allows more-specific exceptions to coexist with aggregate routes.

In hardware, LPM is implemented with specialized data structures (TCAM — ternary content-addressable memory) that can search a million-entry forwarding table in a single clock cycle. This is why your home router can forward packets at wire speed despite having a full routing table.

# Pseudocode: longest-prefix match in a forwarding table
# Table: list of (prefix, prefix_len, next_hop)
forwarding_table = [
    ('0.0.0.0',   0,  'gateway'),      # default route
    ('10.0.0.0',  8,  'isp-link'),
    ('10.1.0.0',  16, 'datacenter'),
    ('10.1.2.0',  24, 'rack-42'),
]

def lookup(dest_ip, table):
    best_prefix_len = -1
    best_next_hop = None
    dest_int = ip_to_int(dest_ip)          # convert to 32-bit integer
    for (prefix, plen, next_hop) in table:
        prefix_int = ip_to_int(prefix)
        mask = (0xFFFFFFFF << (32 - plen)) & 0xFFFFFFFF
        if (dest_int & mask) == (prefix_int & mask):
            if plen > best_prefix_len:     # longest match wins
                best_prefix_len = plen
                best_next_hop = next_hop
    return best_next_hop

# lookup('10.1.2.55') -> 'rack-42'   (matches /24, /16, /8, /0 but /24 wins)
# lookup('10.2.3.4')  -> 'isp-link'  (matches /8 and /0, /8 wins)

IPv4's 32-bit address space yields ~4.3 billion unique addresses. In the 1980s this seemed infinite. By the early 1990s it was clear it was not — the explosive growth of the internet, combined with classful allocation waste, meant exhaustion was coming. The Internet Assigned Numbers Authority (IANA) allocated the last IPv4 /8 blocks to regional registries in 2011.

Stopgaps delayed the crisis: Network Address Translation (NAT) allows an entire home or office network to share a single public IP address, with the NAT device rewriting source addresses and tracking sessions. This breaks the end-to-end principle (a remote host cannot initiate a connection to a NATted host), but it bought a decade of breathing room. Private address spaces (10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16) are used internally and never appear on the global internet.

IPv6 was standardized in 1998 (RFC 2460) to solve the problem permanently. Its 128-bit address space contains 2^128 ≈ 3.4 × 10^38 addresses — enough to assign billions of addresses to every atom on Earth's surface. IPv6 addresses are written as eight groups of four hex digits separated by colons: 2001:0db8:85a3:0000:0000:8a2e:0370:7334. Consecutive all-zero groups can be compressed with :: once per address: 2001:db8::1.

IPv6 also simplifies the packet header (fixed 40-byte header, no checksum — left to upper layers, no fragmentation at routers), adds mandatory IPsec support hooks, and includes built-in autoconfiguration (SLAAC — Stateless Address Autoconfiguration). The transition has been painfully slow — as of 2024, roughly 40-45% of Google traffic is over IPv6 — because it requires upgrading every router, firewall, and application that inspects IP addresses.

Key structural differences: IPv6 has no broadcast (replaced by multicast and anycast). The link-local prefix fe80::/10 is used for neighbor discovery (replacing ARP). The loopback is ::1. Global unicast addresses start with 2000::/3.

# IPv4 header (simplified) — 20 bytes minimum
#  0                   1                   2                   3
#  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
# |Version|  IHL  |Type of Service|          Total Length         |
# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
# |         Identification        |Flags|      Fragment Offset    |
# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
# |  Time to Live |    Protocol   |         Header Checksum       |
# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
# |                       Source Address                          |
# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
# |                    Destination Address                        |
# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

# IPv6 header — exactly 40 bytes, simpler
# Version(4) | Traffic Class(8) | Flow Label(20)
# Payload Length(16) | Next Header(8) | Hop Limit(8)
# Source Address (128 bits)
# Destination Address (128 bits)
# No checksum, no fragmentation fields, no options in base header

This is one of the most important conceptual distinctions in networking, and it maps directly onto how modern routers are built.

Forwarding (the data plane) is the per-packet, real-time action: given an incoming packet, look up the destination IP in the forwarding table (FIB — Forwarding Information Base), and send the packet out the correct interface toward the next hop. This happens at line rate — tens to hundreds of millions of packets per second on a modern router — in specialized hardware (ASICs, NPUs, TCAM). The forwarding table is essentially a read-only lookup structure; the data plane does not think, it just executes.

Routing (the control plane) is the distributed computation that builds the forwarding table. Routing protocols (OSPF, RIP, BGP) run as software processes on the router's general-purpose CPU. They exchange messages with neighboring routers, run graph algorithms, and periodically install updated routes into the FIB. This happens on a timescale of seconds to minutes, not microseconds.

The analogy: forwarding is like a postal clerk reading the address on a letter and dropping it in the right bin (takes milliseconds, done a million times a day). Routing is like the process that decided which bin corresponds to which region — done once, updated when the post office network changes.

In Software-Defined Networking (SDN), this separation is made explicit and radical: the control plane is physically separated from the data plane and moved to a centralized controller (like OpenFlow). Individual switches become simple forwarding elements that execute rules pushed by the controller. This allows network-wide optimization that is impossible when every router computes its own local view.

The TTL (Time-to-Live) field in the IP header is a forwarding-level loop prevention mechanism: every router decrements TTL by 1, and if it reaches 0, the packet is dropped and an ICMP Time Exceeded message is sent back. traceroute exploits this by sending packets with TTL=1, 2, 3, ... to elicit ICMP responses from successive hops.

# Simplified forwarding logic in pseudocode (what a router does per packet)
function forward_packet(packet):
    if packet.ttl <= 0:
        send ICMP(TIME_EXCEEDED) to packet.src
        drop packet
        return

    packet.ttl -= 1
    recalculate_checksum(packet)   # IPv4 only; IPv6 has no header checksum

    next_hop = longest_prefix_match(packet.dst, forwarding_table)
    if next_hop is None:
        send ICMP(DEST_UNREACHABLE) to packet.src
        return

    out_interface = next_hop.interface
    next_hop_mac = arp_lookup(next_hop.ip, out_interface)  # layer 2
    encapsulate_and_send(packet, next_hop_mac, out_interface)

Link-state routing is based on a seductively simple idea: if every router knows the complete topology of the network, every router can independently compute the shortest paths to all destinations using a classical graph algorithm.

Here is how it works in practice (as in OSPF — Open Shortest Path First):

1. Neighbor discovery: each router uses Hello packets to discover its directly connected neighbors and measure the cost (usually bandwidth-derived) of each link.
2. LSA flooding: each router creates a Link-State Advertisement (LSA) describing its local connectivity ("I am Router A, my neighbors are B (cost 2) and C (cost 5)") and floods it to the entire network. Every router forwards each LSA it receives out all interfaces except the one it arrived on, exactly once.
3. Topology database: each router accumulates LSAs until it has a complete picture of the entire network as a weighted graph.
4. Dijkstra's algorithm: each router runs Dijkstra independently on its local topology database to compute shortest-path trees rooted at itself, then installs the results as forwarding entries.

Dijkstra's algorithm (for those needing a refresher): maintain a set of "settled" nodes (shortest path known) and a priority queue of candidates. Initialize: dist[source] = 0, dist[all others] = ∞. Repeatedly extract the minimum-distance unsettled node u, add it to settled, and relax its neighbors: if dist[u] + cost(u,v) < dist[v], update dist[v] and record that the best predecessor of v is u. Time complexity: O((V + E) log V) with a binary heap.

Convergence: when a link fails, the routers on either end flood a new LSA with an infinite-cost entry. All routers receive this within seconds (flooding is fast), rerun Dijkstra, and install new routes. Convergence is fast and loop-free because all routers compute from the same consistent topology snapshot.

Drawback: flooding O(N^2) messages in a large network is expensive. LSPs (link-state packets) are suppressed with sequence numbers to prevent loops and reduplication. OSPF uses areas to limit flooding scope — routers within an area have full topology knowledge; inter-area routing is summarized.

import heapq

def dijkstra(graph, source):
    """
    graph: dict of {node: [(neighbor, cost), ...]}
    Returns: (dist dict, prev dict for path reconstruction)
    """
    dist = {node: float('inf') for node in graph}
    prev = {node: None for node in graph}
    dist[source] = 0
    pq = [(0, source)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:        # stale entry in heap
            continue
        for (v, cost) in graph[u]:
            alt = dist[u] + cost
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heapq.heappush(pq, (alt, v))
    return dist, prev

# Example: small network
graph = {
    'A': [('B', 2), ('C', 5)],
    'B': [('A', 2), ('C', 1), ('D', 4)],
    'C': [('A', 5), ('B', 1), ('D', 1)],
    'D': [('B', 4), ('C', 1)],
}
dist, prev = dijkstra(graph, 'A')
# dist = {'A': 0, 'B': 2, 'C': 3, 'D': 4}
# Next hop from A to D: A -> B -> C -> D

Distance-vector routing takes the opposite philosophy: each router knows only its immediate neighbors, and routers iteratively share their current best-distance vectors with each other until the whole network converges. The classical protocol is RIP (Routing Information Protocol); the algorithm is distributed Bellman-Ford.

The core Bellman-Ford recurrence: the shortest distance from node v to destination d is:

dist[v][d] = min over all neighbors u of (cost(v,u) + dist[u][d])

In the protocol: each router periodically sends its entire distance vector (the table of distances it currently believes to all destinations) to each neighbor. Upon receiving a neighbor's vector, a router updates its own table using the recurrence above. This continues until no more updates propagate — which is guaranteed in a finite network without negative cycles.

Convergence is slow for bad news — the infamous count-to-infinity problem. Suppose A-B-C are in a line. C fails. B sets its distance to C as ∞. But before B tells A, A sends its vector to B: "I can reach C in 2 hops via B." B thinks: "Great, A can reach C in 2, so I can reach it in 3!" and updates its table. A then learns from B: "B says C is 3 hops away, so I can reach C in 4!" This loop continues until the distance counts to infinity (typically 16 in RIP, where 16 = unreachable).

Solutions:

• Split horizon: never advertise a route back on the interface you learned it from.
• Poison reverse: actively advertise infinity for routes learned on the same interface.
• Triggered updates: send updates immediately when something changes, not just on schedule.
• Hold-down timers: after learning a route is gone, ignore better-looking routes for a while.

DV routing has lower overhead than link-state (each router only talks to its neighbors), but converges more slowly and has worse failure behavior. RIP still runs in some small networks. EIGRP (Cisco's Enhanced IGRP) is a hybrid that avoids count-to-infinity with a diffusing computation.

# Distributed Bellman-Ford (one router's update step)
# Each router maintains: dist[dest] = (cost, next_hop)
# On receiving neighbor n's distance vector dv_n:

def receive_distance_vector(self, neighbor, dv_n, link_cost_to_neighbor):
    updated = False
    for dest, neighbor_cost in dv_n.items():
        candidate = link_cost_to_neighbor + neighbor_cost
        if candidate < self.dist.get(dest, float('inf')):
            self.dist[dest] = candidate
            self.next_hop[dest] = neighbor
            updated = True

    # Split horizon: don't advertise back what we learned from neighbor
    if updated:
        self.send_dv_to_all_neighbors(exclude=neighbor)

# Count-to-infinity illustrated:
# t=0: A->C=1, B->C=2 (B routes through A)
# t=1: C fails. A sets dist[C]=inf.
# t=2: B still has dist[C]=2. A hears B->C=2: updates dist[C]=3 (via B).
# t=3: B hears A->C=3: updates dist[C]=4 (via A). Loop!

A flat routing scheme — one routing protocol for all ~70,000 networks on the internet — would be infeasible. The scale problem is obvious: no router could store routes to every subnet, and the messaging overhead of global link-state flooding or DV exchange would overwhelm every link. But there is also a policy problem: the internet is not owned by one entity. Companies, universities, governments, and ISPs each own and operate their own networks, and they have complex commercial and political relationships that affect which routes they are willing to carry traffic on.

The solution is hierarchical routing organized around Autonomous Systems (ASes). An AS is a network (or collection of networks) under a single administrative authority, identified by a globally unique AS Number (ASN) (originally 16-bit, now 32-bit, allocated by IANA/regional registries). Google is AS15169. Comcast is AS7922. Each AS runs whatever internal routing protocol it likes (OSPF, EIGRP, RIP, IS-IS — called Interior Gateway Protocols, IGP). Between ASes, a single standard protocol is used: BGP.

The division of routing into intra-AS (IGP) and inter-AS (BGP) is fundamental:

• IGP: optimize for shortest path, minimal convergence time, full topology knowledge within the AS.
• BGP: propagate reachability announcements ("AS 15169 can reach prefix 8.8.8.0/24") and enforce policy (business agreements, peering vs transit, traffic engineering).

The physical topology of an AS is invisible outside it. From the outside, an AS is a black box that announces prefixes. This encapsulation is what allows the internet's routing system to scale — the global BGP table carries ~900,000 prefixes (aggregated blocks), not entries for every individual host.

# No code needed here — the key structure is conceptual.
# Typical AS topology:
#
#  [Stub AS]  --customer-->  [Transit ISP AS]  <--peer-->  [Peer ISP AS]
#     |                           |                              |
#  (end-user)              (carries transit)            (carries transit)
#
# Routing policy example:
# - Transit provider: accept all your routes, carry traffic to/from internet.
# - Peering: exchange routes for each other's customers only, no transit.
# - Customer: pay for transit, your routes are accepted and propagated.
#
# A BGP route announcement carries:
#   NLRI (prefix), AS_PATH, NEXT_HOP, LOCAL_PREF, MED, communities
#
# A router receiving prefix P via two paths:
#   Path 1: AS_PATH = [701, 3356, 15169]  (3 hops)
#   Path 2: AS_PATH = [7922, 15169]       (2 hops)
# Prefers Path 2 (shorter AS_PATH) — all else equal.

Border Gateway Protocol (BGP), currently at version 4 (RFC 4271), is the inter-domain routing protocol of the internet. It is an Exterior Gateway Protocol (EGP) designed around policy rather than optimal paths. Every AS boundary router runs BGP and maintains persistent TCP connections (port 179) to its BGP peers (neighboring AS routers).

BGP is a path-vector protocol: each route announcement carries not just the destination prefix and a cost, but the full AS_PATH — the sequence of AS numbers the announcement has traversed. This has two critical properties:

1. Loop prevention: if a router sees its own AS number in the AS_PATH of an incoming announcement, it rejects it.
2. Policy expression: operators can inspect the AS_PATH (and other attributes) to implement complex routing policies.

BGP route selection is a long decision process applied when multiple paths exist for the same prefix:

1. Highest LOCAL_PREF (set locally to prefer certain exit paths)
2. Shortest AS_PATH
3. Lowest origin type (IGP < EGP < incomplete)
4. Lowest MED (Multi-Exit Discriminator, a hint from the neighboring AS)
5. eBGP over iBGP paths
6. Lowest IGP cost to next hop
7. Oldest route (stability), then lowest router ID as tiebreaker

iBGP vs eBGP: eBGP (external BGP) runs between routers in different ASes. iBGP (internal BGP) runs between routers within the same AS to distribute externally learned routes. iBGP has a critical rule: routes learned via iBGP are not re-advertised to other iBGP peers (to prevent loops). This requires a full mesh of iBGP sessions within an AS (or a route reflector hierarchy).

BGP convergence is slow — minutes in the worst case — because it relies on TCP (for reliability) and incremental updates. Path exploration after a failure can create transient routing loops. This is why internet outages (a major AS going down, a BGP misconfiguration) can last minutes.

BGP security is a deep concern: the protocol itself has no origin authentication. A malicious or misconfigured AS can announce prefixes it does not own, hijacking traffic. The 2010 China Telecom incident (AS4134 announcing ~37,000 foreign prefixes) redirected global traffic through China for 18 minutes. RPKI (Resource Public Key Infrastructure) is the modern fix: cryptographic certificates tie prefixes to authorized origin ASes.

# BGP UPDATE message structure (simplified)
# Sent over TCP to announce or withdraw routes

bgp_update = {
    'withdrawn_routes': ['203.0.113.0/24'],  # prefixes to remove
    'path_attributes': {
        'ORIGIN': 'IGP',                      # how the route was learned
        'AS_PATH': [64501, 64502, 15169],     # ASes traversed
        'NEXT_HOP': '198.51.100.1',           # where to forward to
        'LOCAL_PREF': 100,                    # preference (higher = better)
        'MED': 50,                            # metric for neighbor
        'COMMUNITIES': ['64501:100'],         # policy tags
    },
    'nlri': ['8.8.8.0/24', '8.8.4.0/24'],   # prefixes being announced
}

# BGP state machine (simplified)
# IDLE -> CONNECT -> ACTIVE -> OPENSENT -> OPENCONFIRM -> ESTABLISHED
# In ESTABLISHED state: exchange KEEPALIVE (every 60s) and UPDATE messages
# Missing 3 KAs = HOLD_TIMER expires = session reset

Internet Control Message Protocol (ICMP) is the network layer's error-reporting and diagnostic protocol (RFC 792 for v4, RFC 4443 for v6). ICMP messages are carried inside IP packets but are conceptually part of the network layer (not the transport layer). They are generated by routers and hosts to report conditions that the IP layer cannot handle silently.

Key ICMP message types:

• Echo Request / Echo Reply (type 8/0): the basis of ping. A host sends an Echo Request; the destination replies with Echo Reply. Round-trip time gives network latency.
• Destination Unreachable (type 3): generated by a router that cannot forward a packet, or a host that has no application listening on the destination port. The code field gives the reason (network unreachable, host unreachable, port unreachable, fragmentation needed but DF bit set).
• Time Exceeded (type 11): generated when TTL reaches 0. This is the mechanism traceroute exploits.
• Redirect (type 5): a router tells a host to use a better gateway for a particular destination.

traceroute works by sending a series of UDP packets (or ICMP Echo Requests on Windows) with TTL=1, 2, 3, ... The router at hop k decrements TTL to 0, drops the packet, and sends back an ICMP Time Exceeded. By recording the source IP and timestamp of each ICMP response, traceroute reconstructs the path. Some routers are configured to not generate ICMP Time Exceeded messages (rate-limited or firewalled), producing * * * lines.

# Python: send a ping (ICMP Echo Request) using raw sockets
# (requires root/admin privileges)
import socket, struct, time, os

def checksum(data):
    s = 0
    for i in range(0, len(data), 2):
        w = (data[i] << 8) + (data[i+1] if i+1 < len(data) else 0)
        s = (s + w) & 0xFFFF
    return ~s & 0xFFFF

def ping(dest, seq=1):
    sock = socket.socket(socket.AF_INET, socket.SOCK_RAW, socket.IPPROTO_ICMP)
    # ICMP Echo Request: type=8, code=0, id=PID, seq=seq
    pid = os.getpid() & 0xFFFF
    header = struct.pack('bbHHh', 8, 0, 0, pid, seq)  # checksum=0 for now
    payload = struct.pack('d', time.time())
    chk = checksum(header + payload)
    header = struct.pack('bbHHh', 8, 0, socket.htons(chk), pid, seq)
    sock.sendto(header + payload, (dest, 0))
    recv, addr = sock.recvfrom(1024)
    rtt = (time.time() - struct.unpack('d', recv[28:36])[0]) * 1000
    print(f'Reply from {addr[0]}: time={rtt:.2f}ms')