6  Addressing, Naming, and Discovery

6.1 The Anchor: The Bootstrap Problem

When a laptop wakes up in a café and opens a browser, something remarkable has already happened in the first few hundred milliseconds. The laptop started with nothing — zero address, zero route, zero knowledge of who its router is or where the DNS server lives. Within a second, it has acquired an IP address, located its default gateway, resolved a human-readable name into a machine-routable address, and opened a TCP connection to a machine it has never met. Each step depended on the previous step’s result. None of them could have been skipped.

This is the bootstrap problem. A device joining a network must solve a chicken-and-egg puzzle: to talk, it needs an address; to get an address, it must talk. To reach a service, it needs the server’s address; to learn the address, it must query a name server whose address remains unknown. Every answer depends on a previous answer that the device has yet to obtain.

The binding constraint that shapes every addressing, naming, and discovery system is this: names must be human-readable, addresses must be machine-routable, and the mapping between them changes over time. The namespace is administratively fragmented; authority is distributed. The Internet’s namespace is administratively fragmented by design, and its address space is a contested resource that runs out.

Four decision problems flow from this constraint:

  1. How should addresses be assigned — statically by an administrator, dynamically by a server, or self-configured by the device?
  2. How should names be mapped to addresses at scale — in a central file, a flat directory, or a hierarchical delegation tree?
  3. How should address exhaustion be handled — ration, share, or redesign the address space?
  4. Where should the boundaries between naming, addressing, and routing be drawn — and what happens when those boundaries move?

Jon Postel, writing the Internet Protocol specification in 1981, framed the first constraint without knowing that the answer he chose — 32 bits, in classful blocks — would become the Internet’s most entrenched interface:

“The internet protocol provides for transmitting blocks of data called datagrams from sources to destinations, where sources and destinations are hosts identified by fixed length addresses.” — Postel, 1981 (Postel 1981)

Twelve years later, Jerome Saltzer would give the retrospective framing that clarified what Postel’s generation had implicitly committed to:

“There are four useful kinds of network objects: services, nodes, network attachment points, and paths.” — Saltzer, 1993 (Saltzer 1993)

Saltzer’s taxonomy was retrospective. Postel and the DNS designers worked before these four kinds of identifiers were consciously separated. Much of this chapter traces how those separations were forced into existence by failures.

6.2 Act 1: “It’s 1981. ARPANET Must Become a Network of Networks.”

By 1981, ARPANET had grown from four nodes to over two hundred and had begun connecting to other packet-switched networks: SATNET, the Packet Radio Network, and early research networks in Europe. Vint Cerf and Bob Kahn’s 1974 paper had proposed an internetworking protocol; Jon Postel was now writing the specification that would be mandated across the entire network on a single flag day: January 1, 1983.

“The internet protocol is specifically limited in scope to provide the functions necessary to deliver a package of bits (an internet datagram) from a source to a destination over an interconnected system of networks.” — Postel, 1981 (Postel 1981)

What the pioneers saw: A handful of research networks, each with fewer than a thousand hosts, each administered by a few dozen people who mostly knew each other. The hard problem was heterogeneity — connecting networks with different MTUs, different link-layer formats, different latencies. Address scarcity was inconceivable: 4 billion addresses seemed inexhaustible for a network expected to reach at most 10,000 hosts.

What remained invisible from the pioneers’ vantage point: Commercial Internet adoption would explode in the 1990s, pushing host counts into the millions by 1995 and billions by 2015. The 32-bit address space that seemed infinite in 1981 would become the Internet’s scarcest resource. And the classful structure — dividing the space into fixed Class A, B, and C blocks — would prove catastrophically wasteful.

6.2.1 The Solution: 32-Bit Classful Addresses

Postel’s design gave every host a 32-bit address split into a network portion and a host portion at a class boundary:

  • Class A (1.x.x.x – 126.x.x.x): 8-bit network, 24-bit host. 128 possible networks, each with 16.7 million hosts.
  • Class B (128.x.x.x – 191.x.x.x): 16-bit network, 16-bit host. 16,384 networks, each with 65,534 hosts.
  • Class C (192.x.x.x – 223.x.x.x): 24-bit network, 8-bit host. 2 million networks, each with 254 hosts.

A router inspecting a packet’s destination address needed only to examine the first few bits to determine the class, then extract the network portion. Lookup tables keyed on network numbers, not on individual addresses. Every host and every router knew the rules; no per-address state was required.

Postel applied disaggregation by separating the internet layer’s addressing from the link layer’s addressing. IP addresses were universal; MAC addresses were local. A gateway translated between them per hop. And he applied decision placement by pushing routing decisions to each gateway independently — there was no central authority, only shared rules for interpreting the address fields.

6.2.2 Invariant Analysis: IP Classful Addressing (1981)

Invariant IP Answer (1981) Gap?
State Stateless — each datagram independent Routers carry one entry per classful network
Time Prescribed TTL field bounds datagram lifetime No timing feedback to endpoints
Coordination Decentralized — gateways decide via shared rules Address allocation centralized at IANA
Interface 32-bit addresses with fixed class boundaries Class sizes mismatch real organization sizes

The Interface gap is the one that would matter most. An organization with 2,000 hosts exceeded a Class C (254 hosts) and was forced into a Class B (65,534 hosts) — wasting ~63,000 addresses per allocation. An organization with 30 hosts still needed a full Class C, wasting 224 addresses. The fixed class sizes were a compromise optimized for routing lookup simplicity, at the expense of allocation efficiency. Every wasted address contributed to eventual exhaustion.

6.2.3 Environment → Measurement → Belief

Layer What IP Has What’s Missing
Environment The global allocation of all 2^32 addresses —
Measurement The destination address in each datagram Address demand and waste both invisible
Belief “This destination lives in network N; forward to the next hop for N” Address exhaustion invisible until IANA’s pool drains

The E→M gap is structurally filtered — the router sees only individual packets, not the allocation pattern. Address waste accumulated invisibly at the allocation layer (IANA assigning Class Bs faster than predicted) while the data plane operated normally. The failure would be invisible to routers until the allocation pool ran dry.

6.2.4 “The Gaps Didn’t Matter… Yet.”

In 1981 the Internet had a few hundred hosts. In 1985, about 2,000. In 1988, when the Morris Worm hit, ~60,000. The 32-bit space was 4 billion. Class B was still being handed out to anyone who asked. Routing tables held a few hundred entries. Address waste was a budget concern, not a crisis.

By 1990, commercial Internet adoption began. By 1992, Class B allocation was doubling annually. The IETF projected depletion by 1994 and convened the ROAD (Routing and Addressing) group to triage the situation. Two pressures were fusing: routing-table size (operational, felt by backbone operators whose routers ran out of memory) and allocation waste (accounting, felt by IANA). Each pressure demanded a different fix. The community would need both.

6.2.5 Transition: What Broke

Two invariants broke simultaneously. The Interface answer — 32 bits carved into three fixed classes — made efficient allocation impossible; Class B was too big for most organizations, Class C too small, and there was nothing in between. The State answer — one forwarding-table entry per classful network — made routing scale poorly; every new allocation added a backbone route. The two failures had the same root cause: the address space’s structure was frozen into the protocol, and the protocol required replacing every host and router on Earth to change.

6.3 Act 2: “It’s 1983. The HOSTS.TXT File Is Collapsing Under Its Own Weight.”

In the early ARPANET era, every host downloaded a single file — HOSTS.TXT, maintained by Elizabeth Feinler’s team at SRI-NIC — that mapped human-readable names to IP addresses. Every time a new host joined, SRI edited the file. Every host on the network periodically re-fetched the master copy. By 1982, the file was several megabytes, updates arrived slowly, and name collisions (two organizations wanting the same short name) were common. The system was breaking.

Paul Mockapetris, working at USC’s Information Sciences Institute, was asked to design a replacement. His 1983 drafts became RFC 1034 and RFC 1035 in 1987 (Mockapetris 1987a, 1987b).

“The domain name space has a tree structure. Each node and leaf on the tree corresponds to a resource set. The domain system makes no distinctions between the uses of the interior nodes and leaves, and this memo uses the term ‘domain name’ to refer to any node in the tree.” — Mockapetris, 1987 (Mockapetris 1987a)

What Mockapetris saw: Administrative authority over names needed to match organizational boundaries. Stanford should control stanford.edu without coordinating with MIT. The root should delegate to top-level domains, which should delegate to organizations, which should delegate to sub-organizations. Centralized maintenance was doomed; distributed delegation could scale.

What remained invisible from the pioneers’ vantage point: The DNS would become the most queried database on the planet, handled by recursive resolvers processing billions of queries per second. Its trust model — plaintext queries, no authenticity — would become an attack surface exploited by cache poisoning, surveillance, and censorship.

6.3.1 The Solution: Hierarchical Delegation with Caching

DNS organized the namespace as a tree. Each zone (e.g., stanford.edu) had authoritative name servers that answered queries about names within that zone. A parent zone held NS records pointing to a child zone’s servers — delegating authority downward. A resolver trying to resolve www.cs.stanford.edu would walk the tree: query a root server for edu, query edu for stanford.edu, query stanford.edu for cs.stanford.edu, query cs.stanford.edu for www.cs.stanford.edu. Each step returned a referral to the next authoritative server.

Caching collapsed this walk into a single lookup for popular names. Every record carried a Time To Live (TTL)1 — the authoritative server’s declaration of how long the answer could be trusted. A resolver cached the answer for TTL seconds, serving subsequent queries locally.

Mockapetris applied disaggregation by separating naming authority (who owns the name) from routing authority (who owns the address). He applied decision placement by delegating authority hierarchically rather than centralizing at a root. And he applied closed-loop reasoning through TTL: caches periodically refresh beliefs against authority, bounding staleness.

6.3.2 Invariant Analysis: DNS (1987)

Invariant DNS Answer (1987) Gap?
State Caches at resolvers; authoritative records at zone servers Authenticity absent — caches are poisonable
Time TTL prescribed by authoritative server Cached answers stale between authority changes
Coordination Hierarchical delegation, zone-by-zone Cross-zone integrity proof absent
Interface Resource records (A, NS, MX, CNAME) over UDP/53 Plaintext — every query visible on path

The State gap is the foundation of DNS’s later security problems. A resolver trusts any response that matches its outstanding query ID. An attacker who can guess the query ID and forge a response can inject false records that stay cached for TTL seconds. Dan Kaminsky demonstrated this attack in 2008: a single off-path attacker could poison a resolver’s cache in seconds (Kaminsky 2008). The Interface gap — plaintext queries — would become a privacy problem once recursive resolvers became concentration points for surveillance.

6.3.3 Environment → Measurement → Belief

Layer What DNS Has What’s Missing
Environment True name-to-address bindings at authoritative zones —
Measurement Query responses matching transaction IDs Cryptographic authenticity absent
Belief Cached records, trusted for TTL seconds Trust extends to whoever answers first

The E→M gap is accidentally noisy in design, structurally exploitable in practice. The trust model assumed a cooperative network where off-path attackers lacked visibility into queries. Once the Internet commercialized, this assumption collapsed.

6.3.4 “The Gaps Didn’t Matter… Yet.”

Through the 1990s, DNS operated quietly. Cache poisoning was theoretical. Privacy was a secondary concern when browser queries leaked far more information than DNS lookups. The system handled millions of names with microsecond lookups. Mockapetris’s design worked.

Kaminsky’s 2008 attack made authenticity urgent. Snowden’s 2013 revelations made confidentiality urgent. DNSSEC (RFC 4033 (Arends et al. 2005)) retrofitted authenticity through signed records; DoT (DNS-over-TLS, RFC 7858 (Hu et al. 2016)) and DoH (DNS-over-HTTPS, RFC 8484 (Hoffman and McManus 2018)) retrofitted confidentiality through encrypted transport. Both retrofits preserved DNS’s hierarchical model but added new trust chains and new concentration points.

DNSSEC’s trust chain extends the existing delegation hierarchy: the root zone is signed by the Root KSK (Key Signing Key), each TLD is signed by its own KSK whose fingerprint (DS record) is published in the root, and each zone below is signed similarly. A resolver validating www.example.com walks the chain from root → com → example.com, verifying signatures at each step. The trust model is hierarchical just like DNS itself — and shares the same vulnerability: whoever controls a zone’s key signs anything that zone says.

DoT and DoH change the transport but not the trust model. Queries travel over TLS (DoT) or HTTPS (DoH) between the client and the recursive resolver. The resolver still performs DNS lookups in plaintext, and the recursive resolver still sees every query. The confidentiality boundary moves from the network path to the resolver itself — which is why DoH deployments concentrated queries at a handful of providers (Cloudflare, Google, Quad9) and sparked debates about centralization.

6.4 Act 3: “It’s 1993. The Routing Tables Are Going to Overflow.”

By 1992, three crises collided. Class B allocations were doubling annually — of 16,384 possible, 7,354 had been assigned, with depletion forecast for 1994. Backbone routing tables carried one entry per classful network and were approaching 10,000 entries, straining the memory of contemporary routers. And the total address space was forecast to exhaust by 2005-2010.

Vince Fuller, Tony Li, Jessica Yu, and Kannan Varadhan proposed Classless Inter-Domain Routing (CIDR) as an emergency measure (Fuller et al. 1993).

What Fuller and Li saw: The fixed class boundaries were the wrong interface. Address allocation and routing-table structure had been conflated. If address blocks could be any size and routing could aggregate adjacent blocks, both problems would ease at once. An ISP assigned a /16 could serve 256 customers with /24s — and advertise only one prefix to the backbone.

What remained invisible: CIDR bought time while leaving exhaustion intact. Provider-aggregated addressing would lock customers to their providers: changing ISPs meant renumbering. And backbone tables would grow anyway as multihoming and traffic engineering forced de-aggregation — today’s table holds over 900,000 prefixes.

6.4.1 Which Invariant Broke?

Invariant What Broke Concrete Consequence
Interface Fixed class boundaries 2,000-host org wasted 63,000 Class B addresses
State One route per classful network Backbone routers approaching memory limits

The coupled failure is what made CIDR urgent: any fix to one problem had to avoid worsening the other. Simply giving every org a Class A would solve routing (fewer entries) but destroy allocation (only 126 Class As exist). Giving every org a bag of Class Cs would solve allocation (more fine-grained) but destroy routing (thousands of entries per org). The answer had to change the interface itself — to decouple allocation granularity from routing granularity.

6.4.2 The Solution: Variable-Length Prefixes

CIDR replaced the fixed Class A/B/C boundaries with an explicit prefix length: 192.0.2.0/24 meant “the 24-bit prefix 192.0.2, covering 256 addresses.”2 Any length from /8 to /32 was valid. A site needing 500 hosts received a /23 (512 addresses) — right-sized, not class-padded. An ISP received a short prefix (say /16) and subdivided it into customer prefixes (say /24s). The ISP advertised the /16 to the backbone; the 256 customer prefixes aggregated into that one announcement.

Fuller and Li applied disaggregation by separating address allocation from the routing structure’s class boundaries. The /n notation became a new interface between allocation and forwarding — one that could be tuned to organizational and topological reality rather than frozen into the protocol.

Route aggregation turned the disaggregation inside out: where addresses had been disaggregated from classes, routes were re-aggregated by provider. An ISP holding 10.0.0.0/8 could subdivide internally into any number of customer prefixes, but the backbone saw only the /8. The aggregation boundary sat at the provider edge, where administrative authority met routing policy. This alignment — topology matching allocation — was the key architectural shift CIDR enabled.

6.4.3 Invariant Analysis: CIDR (1993)

Invariant CIDR Answer (1993) Gap?
State Per-prefix routes, arbitrary lengths De-aggregation can re-inflate tables
Time Prefix allocations persist for years BGP churn propagates slowly
Coordination Hierarchical: IANA → RIRs → LIRs → end sites Policy disputes over de-aggregation
Interface a.b.c.d/n notation Provider lock-in; renumbering pain

6.4.4 Environment → Measurement → Belief After CIDR

Layer What CIDR Has What’s Missing
Environment Global address allocation + topology —
Measurement BGP route announcements with prefix lengths Allocation efficiency opaque
Belief “Forward packets matching prefix P to neighbor N” Aggregation incentives absent when de-aggregation wins traffic

The E→M gap shifted: CIDR gave routers a richer forwarding key (prefix length became part of the match), but the protocol lacked any incentive for operators to aggregate. Multihomed customers and traffic-engineering tricks would later de-aggregate prefixes deliberately, re-inflating the backbone table from ~30,000 entries in 2000 to over 900,000 today.

6.4.5 “The Gaps Didn’t Matter… Yet.”

CIDR’s immediate impact was dramatic. Routing tables that had been growing exponentially flattened briefly in 1994-1995. Class B allocation slowed. The crisis was postponed.

But the total address pool kept shrinking. By 1995, exhaustion was still forecast — just pushed from 2005 to 2020. A permanent fix required either a larger address space (IPv6) or a way to share addresses (NAT). Both would arrive. CIDR was the bridge that kept IPv4 functional while the long-term answers were designed and deployed.

6.5 Act 4: “It’s 1993-1997. Devices Need to Bootstrap Without Human Intervention.”

CIDR solved allocation efficiency. But who handed addresses to individual laptops, printers, and workstations as they joined a network? In 1983, administrators edited configuration files by hand. By 1993, networks were too large and too dynamic for manual configuration. Two protocols — one for Layer 2/Layer 3 binding, one for address acquisition — solved the bootstrap problem.

6.5.1 ARP: Binding IP to MAC (Plummer, 1982)

David Plummer’s Address Resolution Protocol (Plummer 1982) answered a precise question: given an IP address on the local subnet, what MAC address should I put in the Ethernet frame? The protocol was elegant. When host A wanted to send to host B on the same subnet, A broadcast an ARP request: “Who has IP 192.0.2.42?” Every host on the subnet received the broadcast. The host owning that IP replied with its MAC address. A cached the (IP, MAC) binding for future packets.

Plummer applied decision placement as fully distributed — no central binding service existed. Any host could answer any query about itself. The broadcast domain was the coordination boundary.

6.5.2 DHCP: Dynamic Address Assignment (Droms, 1997)

Ralph Droms’s Dynamic Host Configuration Protocol (Droms 1997) solved the address acquisition half. The protocol’s DORA exchange — Discover, Offer, Request, Acknowledge — let a host with no IP address broadcast a request for one.

  1. Discover — the client broadcasts “I need an address” (source IP 0.0.0.0, destination 255.255.255.255)
  2. Offer — one or more DHCP servers reply with an available IP, subnet mask, router, DNS server, and lease time
  3. Request — the client selects one offer and broadcasts its choice (so other servers see the selection)
  4. Acknowledge — the chosen server commits the lease

Each lease had a finite duration. At 50% of the lease (T1), the client attempted to renew with its current server. At 87.5% (T2), it broadcast a renewal request to any server. If no renewal succeeded by lease expiry, the client released the address.

Droms applied closed-loop reasoning through leases: the DHCP server’s belief about “who has which address” periodically refreshes against client reality. A client that crashes simply lets its lease expire; the address returns to the pool.

6.5.3 Invariant Analysis: DHCP + ARP (1997)

Invariant DHCP/ARP Answer Gap?
State Lease table at DHCP server; ARP cache at each host ARP caches trust any replier
Time Leases prescribe duration; ARP caches expire by local policy Stale ARP entries cause silent failures
Coordination DHCP server centralized per subnet; ARP broadcast-based ARP has no authentication — spoofing possible
Interface DORA message exchange; ARP request/reply opcodes Broadcast-dependent — requires L2 adjacency

The ARP gap is structural and severe. ARP lacks authentication: any host replies to any request, and any host sends unsolicited (gratuitous) ARP replies. An attacker on the same subnet can poison neighbors’ ARP caches to redirect traffic through the attacker’s machine — a man-in-the-middle attack. Mitigations (DHCP snooping, Dynamic ARP Inspection) moved the trust boundary from hosts to switches, but the protocol itself remains unauthenticated.

6.5.4 Environment → Measurement → Belief

Layer What DHCP/ARP Have What’s Missing
Environment Actual (IP, MAC) bindings and address availability —
Measurement Broadcast queries and unsolicited advertisements Cryptographic binding proof absent
Belief Lease table (DHCP); cached (IP, MAC) pairs (ARP) Trust extends to any broadcast responder

The E→M gap is physically bounded for ARP: the broadcast domain defines what can be sensed, and anything beyond it remains unauthenticated. For DHCP, the gap is accidentally noisy — misconfigured rogue servers offer incorrect addresses, which is why DHCP snooping exists to filter at the switch.

6.5.5 Before/After: HOSTS.TXT vs DHCP

What Changed HOSTS.TXT Era DHCP Era
Address assignment Manual admin edit Automatic via DORA
Churn tolerance Hours to days Seconds
Server location One file per organization Per-subnet DHCP server
Failure mode Stale local file Expired lease, client falls offline

The shift collapsed the address-assignment loop from days to seconds. A visitor plugging a laptop into a conference-room Ethernet port in 1997 was online within two round trips. The cost was new state in the network — lease tables that had to be kept consistent, snooping infrastructure to reject rogue servers, and relay agents for subnets with no local DHCP server.

6.6 Act 5: “It’s 1999. Home Broadband Explodes. Every House Needs an Address It Can’t Afford.”

By the late 1990s, home Internet adoption was accelerating beyond anything the IETF had planned for. Each ISP subscriber needed an IP address; many households wanted multiple devices online simultaneously. Class B exhaustion was imminent. IPv6 was still years from deployment. Pyda Srisuresh and Kjeld Egevang formalized a workaround that had been spreading through vendor implementations since 1994: Network Address Translation.

“NAT is a method by which IP addresses are mapped from one realm to another, in an attempt to provide transparent routing to hosts.” — Srisuresh and Egevang, 2001 (Srisuresh and Egevang 2001)

What Srisuresh saw: One public IP address was shared among dozens of internal devices if a box at the network edge rewrote packet headers in flight. Outbound packets had their source (ip, port) replaced with the NAT’s public (ip, port). Inbound packets had the reverse rewrite applied. Private address space (RFC 1918 (Rekhter et al. 1996)) was used inside, and the NAT translated to public space at the boundary.

What remained invisible: NAT would silently ossify the Internet. Protocols that relied on endpoint addressability — VoIP, P2P file sharing, inbound SSH — would require workarounds. New transport protocols would be forced to run over UDP because only UDP and TCP reliably traversed NATs. The end-to-end principle would quietly collapse.

6.6.1 The Solution: Per-Flow Translation at the Edge

A NAT box maintained a translation table keyed on the 5-tuple of each connection. When an internal host opened a connection:

  1. The NAT allocated an unused public (ip, port) pair
  2. It stored the mapping (private_src, public_src) → (remote_dst) in its table
  3. It rewrote outbound packets’ source to the public tuple
  4. On inbound return packets, it looked up the public (ip, port) and rewrote back to the private destination

Entries aged out on idle timeouts (typically 2 hours for TCP, 5 minutes for UDP). Unknown inbound packets — those not matching an existing entry — were dropped.

6.6.2 Invariant Analysis: NAT (2001)

Invariant NAT Answer (2001) Gap?
State Per-flow translation entries keyed by 5-tuple Soft state — connections die on NAT reboot
Time Idle timeouts expire entries Long-lived idle connections drop silently
Coordination Unilateral at network edge No endpoint signaling — breaks assumptions
Interface Public (ip, port) exposed; private realm hidden End-to-end principle broken

6.6.3 How NAT Broke the End-to-End Principle

Saltzer, Reed, and Clark (1984) had argued that network intelligence should live at the endpoints (Saltzer et al. 1984): the network should transport bits, and applications should implement semantics. NAT put connection state inside the network. Consequences cascaded:

  • P2P and VoIP failed. A host behind NAT lacked an inbound-reachable address. Two hosts each behind NAT were mutually unreachable. STUN (Session Traversal Utilities for NAT, RFC 5389 (Rosenberg et al. 2008)), TURN (Traversal Using Relays around NAT, RFC 5766 (Mahy et al. 2010)), and ICE (Interactive Connectivity Establishment, RFC 8445 (Keranen et al. 2018)) emerged as workarounds: rendezvous servers to discover public addresses and relays to tunnel traffic.
  • Protocol ossification set in. Any new transport beyond TCP or UDP was dropped by NATs unaware of its protocol number. QUIC — a new transport designed in 2013 — runs over UDP specifically because NATs accept UDP.
  • The middlebox era began. NAT normalized the idea that boxes in the path could rewrite traffic. Firewalls, load balancers, and DPI appliances followed.

The Interface gap is the deepest wound NAT inflicted. The Internet’s original architectural promise — any endpoint can reach any other endpoint — was quietly abandoned. Replacements (STUN/TURN/ICE) restored some reachability at the cost of complexity and centralization.

6.6.4 Environment → Measurement → Belief for NAT

Layer What NAT Has What’s Missing
Environment True connections between endpoints —
Measurement 5-tuples of packets crossing the boundary Application semantics opaque
Belief “This (pub_ip, pub_port) maps to this (priv_ip, priv_port)” Internal host’s inbound expectations invisible

The E→M gap is structurally filtered in a new way: NAT sees only packets, not application intent. A VoIP endpoint expecting inbound SIP INVITE messages lacks any protocol-level path to signal that expectation to the NAT. Application-layer gateways (ALGs) were bolted on to parse specific protocols (FTP, SIP, H.323) and open pinholes dynamically — a brittle workaround that added protocol-specific logic to what was supposed to be a protocol-agnostic box.

6.6.5 “The Gaps Didn’t Matter… Until They Defined the Internet.”

For residential users browsing the Web, NAT was invisible. For the 90%+ of residential broadband connections behind NAT by the late 2000s, client-initiated connections worked fine. NAT bought twenty years of IPv4 life.

The cost was paid by protocol designers. Every new application had to assume NAT was in the path. Every inbound service required port forwarding, UPnP, or an external rendezvous. The Internet’s architecture had been rewritten — not by a standards body, but by millions of home routers shipped with NAT enabled by default.

Carrier-Grade NAT (CGNAT) extended the workaround further: by the 2010s, many mobile carriers placed a second layer of NAT between subscribers and the public Internet. A smartphone connecting to a server traverses the home NAT, the carrier’s CGNAT, and the server’s load balancer. Three layers of translation. The end-to-end principle had been replaced entirely with a stack of rendezvous services.

6.7 Act 6: “It’s 1998. The Address Space Must Change.”

Steve Deering and Bob Hinden had been designing IPv6 since 1994 (Deering and Hinden 1998). The design was complete in 1998. The deployment would take 25 years.

What Deering and Hinden saw: The 32-bit address space was fundamentally insufficient. A clean redesign could expand to 128 bits (enough for 340 undecillion addresses — ~10^28 per person on Earth), simplify the header (fixed 40 bytes, no checksum), replace ARP with a cleaner neighbor discovery protocol (NDP), and enable stateless address autoconfiguration (SLAAC).

What remained invisible: IPv4 was already too entrenched to displace. Every application, every middlebox, every socket API assumed IPv4. Running dual-stack (both protocols simultaneously) cost operators money. Without a compelling pain point for early adopters, IPv6 adoption would stall for two decades.

6.7.1 The Solution: 128-Bit Addresses and Self-Configuration

IPv6 addresses were 128 bits, written as eight 16-bit hex groups (2001:db8::1). The header was simplified — extension headers handled options, the checksum was removed (relying on link-layer and transport-layer checks), and fragmentation moved entirely to end hosts.

SLAAC (RFC 4862 (Thomson et al. 2007)) let hosts self-configure: routers periodically broadcast Router Advertisements announcing the subnet’s prefix, and hosts appended their own interface identifier (often derived from MAC address) to form a globally unique address. DHCP was optional. A host booting on a new subnet listened for a Router Advertisement, generated its address, and was online.

NDP (RFC 4861 (Narten et al. 2007)) replaced ARP with ICMPv6-based Neighbor Solicitation messages. Duplicate Address Detection prevented two hosts from picking the same interface identifier.

Deering and Hinden applied disaggregation by separating address space (128 bits, provider-aggregated hierarchy) from address acquisition (SLAAC, host-driven). They applied closed-loop reasoning through Router Advertisement lifetimes: prefixes advertised for a bounded duration, allowing graceful transitions.

6.7.2 Invariant Analysis: IPv6 (1998)

Invariant IPv6 Answer (1998) Gap?
State Per-interface addresses + aggregated prefixes MAC-derived IIDs leak device identity
Time Router Advertisement prefix lifetimes Missed RAs cause address expiration
Coordination Host self-config via RAs Dual-stack forever during transition
Interface 128-bit addrs; NDP replaces ARP Incompatible with IPv4 — no in-place upgrade

6.7.3 The Ossification Problem

IPv6 was technically ready in 1998. Google’s IPv6 client measurement crossed 5% in 2014 and 40% in 2023. Why 25 years?

  1. Early-adopter incentive absent. NAT made IPv4 work well enough for most users. The pain of address exhaustion fell on ISPs and cloud providers, sparing end users.
  2. Dual-stack cost. Operators had to run both protocols simultaneously, doubling configuration, monitoring, and security surface.
  3. Application assumptions. Hardcoded IPv4 literals, sockaddr_in structures, log parsers expecting dotted-quad format — millions of small code changes.
  4. Middlebox inertia. Every NAT, firewall, load balancer, and DPI box needed IPv6 support. Many got it slowly or never.

The lesson: the interface invariant, once deployed at scale, becomes the next generation’s binding constraint. IPv4’s 32-bit format is the most ossified interface in the Internet. Changing it required a quarter-century transition — not because the new design was bad, but because the old interface was entrenched.

6.7.4 Environment → Measurement → Belief for IPv6

Layer What IPv6 Has What’s Missing
Environment True reachability of every IPv6-capable endpoint —
Measurement Router Advertisements, NDP, link-local scope Dual-stack makes measurement ambiguous
Belief “I have a valid global address from this prefix” Path quality unknown until connection attempt completes

The E→M gap for IPv6 is accidentally noisy during transition: dual-stack hosts run both protocols and use Happy Eyeballs (RFC 8305 (Schinazi and Pauly 2017)) to race connections over both paths, selecting whichever responds first. The measurement signal — which path is working — is only available after attempting a connection. Applications discover which stack is healthier only by trying both.

6.7.5 “The Gaps Didn’t Matter… Because Nobody Deployed.”

The punchline of IPv6’s first two decades was unusual. The gaps in the design were mostly irrelevant because the deployment itself never reached the scale that would stress them. IPv6 became a lesson in sociotechnical constraints: the strongest technical answer stalls for twenty years when the migration path is too expensive. Transition mechanisms (6to4, Teredo, NAT64, dual-stack) proliferated — each one adding complexity without delivering the flag-day switch that IPv4 itself had enjoyed in 1983.

6.7.6 Before/After: IPv4 vs IPv6

What Changed IPv4 + NAT IPv6
Address length 32 bits 128 bits
Address acquisition DHCP SLAAC (or DHCPv6)
L2/L3 binding ARP (broadcast) NDP (ICMPv6 multicast)
End-to-end reachability Broken by NAT Preserved (in principle)
Deployment mode Immediate flag-day (1983) 25-year dual-stack transition

The last row is the most important one. IPv4 succeeded because every stakeholder was forced onto it simultaneously in January 1983. IPv6 had no equivalent forcing function; the transition depended on each operator’s independent cost-benefit calculation. The design tradeoffs of IPv6 are largely irrelevant to its deployment story — the bottleneck was always institutional, not technical.

6.8 The Grand Arc: From Classful Addresses to Named Services

6.8.1 The Evolving Anchor

Era Meta Constraint Binding Invariant State Answer Coordination Answer
1981 Flag-day deployment Interface (32-bit format) Stateless forwarding Decentralized gateways
1987 Administrative fragmentation Coordination (delegation) TTL-bounded caches Hierarchical zones
1993 Routing-table limits State (prefix count) Variable-length prefixes IANA→RIR→LIR hierarchy
1997 Dynamic networks Coordination (bootstrap) DHCP leases + ARP caches Centralized per subnet
2001 IPv4 exhaustion Interface (workaround) Per-flow translation Unilateral at edge
1998/2023 Exhaustion permanence Interface (redesign) SLAAC + aggregated prefixes Host self-config

6.8.2 Three Design Principles Applied Across the Arc

Disaggregation appears wherever a new interface was created to separate concerns. DNS separated naming authority from routing authority. CIDR separated address allocation from routing-class structure. IPv6 separated address acquisition (SLAAC) from address management (DHCPv6). Each separation gained flexibility — and each created an interface that could ossify. CIDR’s /n interface remained fluid; IPv4’s 32-bit format ossified completely.

Decision placement shifted across eras. IP forwarding was maximally distributed (every gateway decides). DNS placed authority hierarchically (zones delegate downward). DHCP centralized per subnet (one server, many clients). NAT unilateralized at the network edge (NAT decides alone, endpoints don’t know). IPv6 pushed decisions back to hosts (SLAAC lets the host choose its own address). The trend oscillates — each system’s placement reflects its binding constraint.

Closed-loop reasoning appears through TTL (DNS), leases (DHCP), and prefix lifetimes (IPv6 RAs). Each mechanism bounds the staleness of belief against authoritative truth. The loop period encodes a tradeoff: short TTLs improve freshness but increase query load; long leases reduce churn but tolerate stale state longer.

6.8.3 The Dependency Chain

flowchart TD
  A["<b>IP Classful (1981)</b><br/>Interface: 32-bit + classes"]:::constraint
  B["Routing table explosion"]:::failure
  C["Class B exhaustion"]:::failure
  D["<b>CIDR (1993)</b><br/>Variable-length prefixes"]:::fix
  E["Address exhaustion persists"]:::failure
  F["<b>NAT (2001)</b><br/>Translate at edge"]:::fix
  G["End-to-end broken"]:::failure
  H["<b>IPv6 (1998)</b><br/>128-bit addresses"]:::fix
  I["25-year adoption stall"]:::failure
  J["<b>HOSTS.TXT</b>"]:::constraint
  K["File growth, collisions"]:::failure
  L["<b>DNS (1987)</b><br/>Hierarchical delegation"]:::fix
  M["Cache poisoning"]:::failure
  N["<b>DNSSEC (2005)</b><br/>Signed records"]:::fix

  A --> B
  A --> C
  B --> D
  C --> D
  D --> E
  E --> F
  E --> H
  F --> G
  H --> I
  J --> K
  K --> L
  L --> M
  M --> N

  classDef constraint fill:#dbeafe,stroke:#2563eb
  classDef failure fill:#fecaca,stroke:#dc2626
  classDef fix fill:#bbf7d0,stroke:#16a34a

6.8.4 Pioneer Diagnosis Table

Year Pioneer Invariant Diagnosed Contribution
1981 Postel Interface (IP format) RFC 791 — 32-bit addresses, classful structure, flag-day deployment
1982 Plummer Coordination (L2/L3 binding) RFC 826 — broadcast-based ARP
1987 Mockapetris Coordination (namespace) RFC 1034/1035 — hierarchical DNS with caching
1993 Fuller/Li State (table growth) RFC 1519 — variable-length prefixes, route aggregation
1997 Droms Coordination (bootstrap) RFC 2131 — DORA exchange, lease-based DHCP
1998 Deering/Hinden Interface (address space) RFC 2460 — 128-bit IPv6, SLAAC-ready
2001 Srisuresh Interface (workaround) RFC 3022 — per-flow NAT translation
2005 Arends et al. State (authenticity) RFC 4033 — DNSSEC signed records
2016-18 Hu/Hoffman Interface (confidentiality) RFC 7858/8484 — DNS over TLS/HTTPS

6.8.5 Innovation Timeline

flowchart TD
    subgraph sg1["Foundations"]
        A1["1981 — Postel: IP classful addressing (RFC 791)"]
        A2["1982 — Plummer: ARP (RFC 826)"]
        A3["1984 — RARP (RFC 903)"]
        A4["1987 — Mockapetris: DNS (RFC 1034/1035)"]
        A1 --> A2 --> A3 --> A4
    end
    subgraph sg2["Scaling Crises"]
        B1["1993 — Fuller/Li: CIDR (RFC 1519)"]
        B2["1997 — Droms: DHCP (RFC 2131)"]
        B3["1998 — Deering/Hinden: IPv6 (RFC 2460)"]
        B1 --> B2 --> B3
    end
    subgraph sg3["Workarounds"]
        C1["2001 — Srisuresh: NAT formalized (RFC 3022)"]
        C2["2005 — DNSSEC (RFC 4033-4035)"]
        C1 --> C2
    end
    subgraph sg4["Retrofits"]
        D1["2016 — DoT (RFC 7858)"]
        D2["2018 — DoH (RFC 8484)"]
        D3["2023 — IPv6 >40% adoption (Google stats)"]
        D1 --> D2 --> D3
    end
    sg1 --> sg2 --> sg3 --> sg4

Addressing, Naming, and Discovery — Innovation Timeline

6.9 Generative Exercises

TipExercise 1: Designing Bootstrap for IoT at Scale

Imagine a smart-city deployment with 10 million sensors joining and leaving the network daily. DHCP assumes a stable server per subnet and a slow churn rate. What breaks at 10M devices? Which invariant fails first — State (lease table size), Time (DORA exchange latency), or Coordination (single server per subnet)? Sketch a redesign that preserves the bootstrap semantics but handles 100× the churn.

TipExercise 2: Naming Without a Hierarchy

DNS delegates authority hierarchically. Content-centric networking proposes naming content directly (“/ucsb/cs176c/ch05”) without binding to a host address. What happens to the four invariants if names identify content rather than hosts? Where does authority live? What does caching mean? What does TTL bound?

TipExercise 3: The Next Interface Ossification

IPv4’s 32-bit address format took 25 years to partially replace. Which of today’s deployed interfaces is the next candidate for two-decade ossification? Candidates: TCP’s 16-bit port numbers, IPv6’s /64 subnet assumption, TLS’s certificate chain, HTTP’s URL syntax, DNS’s 63-character label limit. Pick one, argue why it will or will not ossify, and design the transition path.

  1. Time to Live (TTL) was originally intended as a time limit in seconds but is implemented as a hop count — each router decrements it by 1, and the packet is discarded when TTL reaches 0. DNS TTL is different: it specifies how many seconds a resolver may cache a record before re-querying.↩︎

  2. A /24 prefix means the first 24 of the 32 address bits identify the network; the remaining 8 bits identify hosts within that network, supporting up to 2^8 - 2 = 254 hosts (two addresses reserved for network and broadcast).↩︎