DNS: The Internet Naming System

The Domain Name System is a distributed, hierarchical naming service that translates domain names into IP addresses and other structured data, implemented as a client-server application running over UDP (primarily) and TCP (for large responses and zone transfers). The namespace is organized as an inverted tree of domains, each identified by a fully qualified domain name (FQDN) such as `www.example.com`, read right-to-left: the root (unnamed, written as a trailing dot), the top-level domain (TLD) `com`, the second-level domain `example`, and the subdomain/host `www`. Administrative authority over the namespace is delegated: an organization that controls `example.com` can create and manage its own subdomains (`mail.example.com`, `dev.example.com`) without asking anyone's permission, because it owns the corresponding zone. A zone is a contiguous portion of the namespace for which one organization holds authoritative responsibility; zones are stored as sets of resource records (RRs) on authoritative name servers. This is the key structural idea: DNS is not one database but millions of independently administered databases, glued together by delegation pointers (NS records) that tell you which server to ask next. A DNS resolver (also called a local DNS server or recursive resolver) is the client-facing component — typically operated by an ISP, a company, or a public service like Google Public DNS or Cloudflare — that accepts a query from an application (via a stub resolver in the OS), performs the lookup on the client's behalf, and returns a final answer. The distinction between iterative and recursive queries governs who does the walking through the hierarchy, and it is central to understanding both DNS performance and its caching behavior.

Step 1 — Application invokes the stub resolver. A browser or OS library function (e.g., `getaddrinfo`) issues a query for `www.example.com`, type `A` (IPv4 address). This is handed to a local resolver, usually configured via DHCP or manually.

Step 2 — Resolver checks its cache. If a valid (non-expired) answer for this exact name and type is cached, it is returned immediately — no network traffic beyond the client-resolver hop.

Step 3 — Recursive resolution begins. If not cached, the resolver performs a recursive query on behalf of the client: the client asks once and waits for a complete answer, while the resolver internally performs a sequence of iterative queries: 1. Query a root server for `www.example.com`. The root does not know the answer but returns a referral: the NS records (and glue A records) for the `.com` TLD servers. 2. Query a TLD server for `.com`. It also does not know the final answer but refers the resolver to the authoritative name servers for `example.com`. 3. Query the authoritative server for `example.com`. This server actually holds the zone data and returns the final A record (or a CNAME chain leading to one).

Step 4 — Caching. The resolver caches every intermediate answer — the root's referral, the TLD's referral, and the final A record — each tagged with its own TTL, and returns the final answer to the client's stub resolver, which also caches it briefly.

Step 5 — Subsequent queries for the same or related names can be satisfied at any cached layer: if the resolver already knows `example.com`'s authoritative servers, it skips straight to Step 3, avoiding the root and TLD hops entirely. ``` function RESOLVE(name, qtype, cache):

# Step 1: local cache check if cache.has_valid(name, qtype): return cache.get(name, qtype)

# Step 2: start from best known starting point servers = cache.closest_known_servers(name) # defaults to root hints if servers is empty: servers = ROOT_HINTS while true: response = QUERY(servers, name, qtype) # send UDP query to one server if response.has_answer(name, qtype): cache.store(name, qtype, response.answer, response.ttl) return response.answer if response.is_cname() and not qtype == CNAME: cache.store(name, CNAME, response.cname_target, response.ttl) name = response.cname_target # follow alias, restart search servers = cache.closest_known_servers(name) if servers is empty: servers = ROOT_HINTS continue if response.has_referral(): # NS records for a subdomain cache.store(response.zone, NS, response.ns_records, response.ttl) if response.has_glue(): # A records for those NS names cache.store(response.ns_names, A, response.glue_ips, response.ttl) servers = response.glue_ips else: servers = RESOLVE(response.ns_records[0], A, cache) # bootstrap continue return NXDOMAIN or SERVFAIL # no answer, no referral: fail ``` The `RESOLVE` function models a recursive resolver's internal loop: from the client's point of view it is a single call, but internally it is an iterative walk down the tree, with a CNAME-following branch and a glue-record optimization that avoids a chicken-and-egg problem (you cannot resolve the IP of a nameserver by asking that same nameserver if you don't already have its IP — glue records break this circularity by shipping the IP alongside the NS referral).

Time complexity. In the worst case — a completely cold cache — resolving a name requires traversing the tree depth: root → TLD → second-level → ... → target. If the FQDN has $k$ labels (e.g., `www.example.com` has 3), a cold lookup costs $O(k)$ sequential round trips, each dominated by network latency (tens to hundreds of milliseconds). In practice $k$ is small (typically 2–5), so this is effectively $O(1)$ round trips for any realistic domain, bounded by a small constant, not by the size of the namespace. This is the crucial scaling property: resolution cost depends on the depth of the specific name, never on the total number of domains in existence (which is in the billions). With a warm cache, the expected cost collapses further: if the resolver already caches the authoritative NS set for `example.com` (common after the first lookup, since NS TTLs are often hours to days), subsequent lookups for any host under `example.com` cost exactly one round trip. Cache hit rates in production recursive resolvers are typically well above 90%, because request patterns follow a heavy-tailed (Zipfian) popularity distribution — a small number of domains account for most traffic, and these stay cached continuously.

Space complexity. Each authoritative server stores only its own zone: $O(\text{records in that zone})$, not the whole namespace. A resolver's cache is bounded by a configured size and TTL-driven eviction, so a busy resolver's memory usage is $O(\text{distinct names queried within their TTL windows})$, which is large but manageable (millions of entries, easily fitting in server RAM with hash-table lookups giving $O(1)$ average-case cache access).

Correctness argument. The core invariant maintained by the algorithm is: > At every step of `RESOLVE`, the server being queried is either (a) authoritative for `name` or an ancestor domain of it, or (b) able to return a referral strictly closer to `name` in the tree, or (c) the root, which is authoritative for the top of the tree and always knows all TLD delegations. This invariant guarantees termination and progress: each referral moves the query to a server responsible for a longer matching suffix of `name` (referrals only go down the tree, never sideways or up, by construction of how zones delegate subdomains), so the number of referral hops is bounded by the number of labels in the FQDN, $k$. Termination follows because the referral chain is strictly decreasing in "labels remaining to resolve," a well-founded quantity bounded below by zero (reaching the authoritative zone). The algorithm cannot loop indefinitely absent misconfiguration, since a correctly delegated zone always has a well-defined authoritative parent.

Tradeoffs. Caching trades consistency for speed: an updated record is not visible everywhere immediately — it can take up to the old TTL to fully propagate, which is why DNS changes (e.g., moving a website to a new server) are commonly rolled out with a pre-emptive TTL reduction. UDP-based queries trade reliability for speed (no connection setup, but responses can be lost and must be retried, and are vulnerable to spoofing if source ports/query IDs are guessable) — this is why DNSSEC and modern resolvers add cryptographic validation and randomized query IDs/ports as compensating controls, and why large responses (zone transfers, DNSSEC-signed answers) fall back to TCP.

Suppose a company's recursive resolver, with a completely cold cache, must resolve `A` records for `blog.cs-wiki.edu`, and the chain includes a CNAME alias.

Notice why this trace is not trivial: the CNAME forces a second full tree traversal rooted at a completely different TLD (`.net` instead of `.edu`), because `cs-wiki.edu`'s authority says nothing about how to reach `hosting-provider.net`. This is a realistic pattern — many websites use CNAMEs to point at Content Delivery Networks — and it doubles the cold-cache latency compared to a direct A record. Now suppose a second client, moments later, requests `www.cs-wiki.edu` (same domain, different host, no CNAME involved). The resolver's cache already holds the NS/glue records for `.edu` (from step 1, TTL likely hours) and for `cs-wiki.edu` (from step 2). The resolver skips straight to querying `cs-wiki.edu`'s authoritative server directly — one round trip total, versus six for the cold case. This illustrates the amortized efficiency: the expensive traversal happens once per zone, not once per hostname. If a third client requests `blog.cs-wiki.edu` again 30 seconds later, the CNAME (TTL 300s) is still cached, but the final A record for `cdn.hosting-provider.net` (TTL 60s) is also still valid — full cache hit, zero additional network queries, answer returned instantly from the resolver's memory.

DNS emerged directly from the scaling failure of its predecessor: a single flat text file, `HOSTS.TXT`, manually maintained and distributed to every ARPANET host by the Stanford Research Institute's Network Information Center. As the network grew past a few hundred hosts, updates couldn't propagate fast enough and name collisions became common — a textbook illustration of why centralized, non-hierarchical naming does not scale.

Every request to HTTP and the Web begins with a DNS lookup, making DNS latency a direct component of page-load time — this is why browsers and operating systems prefetch DNS for links on a page before a user clicks them. Content Delivery Networks rely on DNS as their steering mechanism: by returning different A/AAAA records to clients in different regions (geo-DNS) or based on real-time load, a CDN routes each user to a nearby edge server without any change to the URL the user types. Email Protocols: SMTP, IMAP, POP3 depend on DNS's MX (Mail Exchange) records to determine which server should receive mail for a domain, and increasingly on TXT records (SPF, DKIM, DMARC) to prevent spoofed sender addresses. Beyond these, DNS underlies service discovery in cloud infrastructure (Kubernetes' internal DNS for service-to-service naming), load balancing at global scale, certificate issuance (domain validation for TLS certificates checks DNS records), and even censorship and network policy enforcement (many national firewalls and parental-control tools intercept or filter DNS queries, which is part of why DNS-over-HTTPS and DNS-over-TLS have gained adoption — to hide query contents from network intermediaries). Understanding DNS is a prerequisite for understanding almost every other layer of the modern internet's application stack.

Ask the tutor: How does DNSSEC's chain of trust actually verify a signature all the way from the root down to `example.com`?