Iterative Resolution: Walking the Tree from Root Hints to Answer

A stub resolver, the library call behind getaddrinfo, sends a query and expects a response. Between those two events sits a recursive resolver that may have spoken to a dozen servers, and the protocol it speaks to them is a different mode of the same protocol. Understanding the difference between the two modes explains the RD and RA flags, the shape of the response a client sees, and why a resolver’s cache is the only thing standing between the network and a full tree walk per lookup.

Recursion is a service; iteration is the algorithm

The RD flag asks the receiving server to perform the whole lookup on the client’s behalf. A server that sets RA in its response is advertising that it will honour that request. When it does, it becomes a recursive resolver and takes on the work of querying other servers, each of which is asked without RD.

The servers in the walk are authoritative: they answer only from their own zone, never from a cache, and never on behalf of another zone. Their responses are either an answer with AA set, a referral with AA clear, or a negative answer with the zone’s SOA in the authority section. This is why an authoritative server needs no cache and a recursive resolver cannot work without one. The authoritative side is a pure function of its zone file; the recursive side is a cache with a search procedure attached.

The walk starts from a small, fixed set of addresses: the root hints. These are the addresses of the root servers, and they are configuration, not data fetched at runtime, because fetching them would require resolving a name before any resolution is possible. The hints go stale as root server addresses change, so a resolver sends a priming query for the root’s NS RRset when its cached copy expires, and refreshes its address list from the additional section. RFC 8109 permits the RD bit to be either value in that query. The root NS RRset changes rarely and the addresses change more rarely still, but a resolver that never primes will eventually use a decommissioned address and stall.

The shape of one walk

Take a query for www.example.org with an empty cache. The resolver sends it to a root server, which returns a referral to the org servers: an NS RRset for org in the authority section, addresses in the additional section. The resolver sends the same query to an org server, which returns a referral to the example.org servers. It sends the query to one of those, and this time receives the answer with AA set.

Three round trips, four if the additional section lacked glue and the resolver had to resolve a name server’s name first. Each hop costs a round trip to a server chosen by the previous hop, so the latency of a cold lookup is the sum of three network round trips plus the resolver’s own processing. That sum is the reason caches exist and the reason TTLs are the central tuning knob of the whole system.

The referral chain is invisible to the stub. The resolver’s response to the stub is a single message with the answer and RA set; the NS records it collected along the way may appear in the authority section but are not required. A client that inspects the authority section of a recursive response and sees NS records should not read them as evidence of a referral; they are often included only as an artefact of how the resolver built the response.

def walk(qname, qtype, hints, cache, ask):
    """ask(server_ip, qname, qtype) -> parsed response sent with RD clear."""
    zone, servers, target = "", hints, qname
    for _ in range(64):               # depth cap, not a tuning knob
        key = (target, qtype)
        if key in cache and not cache.expired(key):
            return cache.get(key)
        resp = ask(servers[0], target, qtype)

        if resp.answer:
            cname = resp.answer_cname()
            if (cname is not None and qtype != "CNAME" and resp.rcode == 0
                    and not resp.answer_has(cname.target, qtype)):
                target = cname.target  # restart at the target, keep the type
                zone, servers = "", hints
                continue
            cache.put(resp.answer, min_ttl(resp.answer))
            return resp
        if resp.rcode == 3 or (resp.rcode == 0 and not resp.answer
                               and resp.authority_soa):
            cache.put_negative(target, qtype, resp)    # TTL from the SOA
            return resp

        child = resp.authority_ns_owner()              # this must be a referral
        if not child.endswith("." + zone) or child == zone:
            raise ValueError(f"referral to {child!r} does not descend from {zone!r}")
        if target != child and not target.endswith("." + child):
            raise ValueError(f"referral to {child!r} is not on the path to {target!r}")
        servers = resp.additional_addresses() or resolve_addresses(child)
        zone = child
    raise ValueError(f"referral depth exceeded for {qname}")

The depth cap is not arbitrary. A referral chain that fails to descend, or that descends through a server that keeps referring to itself, would otherwise loop forever. The check that each referral descends from the zone just queried, and that it stays on the path to the name being resolved, converts a loop into an error and defends against a malicious server referring the resolver to an unrelated zone.

The additional_addresses() fallback matters too. When the referral carries no glue, because the name servers are out of bailiwick, the resolver must resolve those names before it can use them, which is a nested walk. A chain of such dependencies can in principle be circular: two zones whose name servers are inside each other. That configuration is resolvable only if some parent supplies glue for both sides; without glue the resolver has no starting address, and the depth cap stops it from trying to satisfy the cycle.

What the cache actually stores

The cache stores RRsets, not messages. An RRset is the set of all records with the same owner name, type, and class, and its TTL is a single value that applies to the whole set. Storing per-record TTLs would allow a set to fragment into records with different remaining lifetimes, which produces answers that mix fresh and stale data and violate the atomicity the set is supposed to have. RFC 2181 makes this explicit: records in an RRset must be cached and served together, with the set’s TTL decremented as a unit.

Negative answers are cached too, under a different rule and for a different duration, which is covered in Negative Caching and the NXDOMAIN Distinction. The short version is that a negative answer’s lifetime comes from the SOA’s minimum field and the SOA’s own TTL, whichever is smaller, so a zone can control how long the world remembers that a name does not exist.

Cached referrals are the other large win. The NS RRset for a TLD is cached like any other RRset, so the second lookup under the same TLD skips the root entirely. In steady state a resolver’s cache holds the root’s NS set, the NS sets of the TLDs it has seen, and the NS sets of second-level zones it has already queried, so a cached TLD set removes the root from the next lookup under that TLD. For a name under a TLD that is already cached, the root is consulted only when that delegation NS set has expired, which is the whole reason its TTL matters more than an individual answer’s.

The cache is also where the resolver’s correctness properties live. A response from a server outside the zone it claims to be authoritative for must not be cached as authoritative; a response whose answer does not match the question’s name and type must not be cached at all; and a response that arrives without a matching transaction ID or source port must be discarded. Each of these is a defence against an off-path attacker who can guess a transaction ID but cannot produce a consistent response.

Where the walk stalls

The classic stall is a broken delegation. If the parent’s NS set for a zone points only at servers that are down or lame, the walk has nowhere to go. A resolver that has cached the parent’s NS set will keep using it until the TTL expires, so the failure persists for the TTL even after the delegation is fixed. Lower TTLs on delegation NS sets shorten that window and increase query load; the trade is direct and is why parent-side NS TTLs are often shorter than the child’s apex TTL.

The second stall is a server that answers with a referral to a zone it does not own. The suffix check catches this, but the resolver has no way to know whether the server is malicious or merely misconfigured, so the practical outcome is the same: the query fails and the failure is reported as a server failure rather than as a nonexistent name.

The third is a truncation loop. A response too large for the negotiated UDP size sets TC, the resolver retries over TCP, and if the TCP path is blocked by a middlebox the lookup fails. This is why the truncation boundary and the EDNS payload size negotiation described in EDNS(0) and the Truncation Boundary are not optional details.

The fourth is a CNAME chain that exhausts the resolver’s work budget. Each CNAME restarts the lookup for the target name, and a chain of them multiplies the work. Resolvers cap the chain length at some fixed value and return a server failure past the cap rather than continuing. The chain semantics that make this necessary are covered in Record Semantics: CNAME Exclusivity and RRset Atomicity.

Query minimisation changes the walk

The classic walk sends the full query name to every server in the chain, which means the root learns the full name being looked up. Query name minimisation, defined in RFC 7816, sends progressively longer suffixes: the root is asked for org, the org servers are asked for example.org, and only the example.org servers see www.example.org. Each server learns only the part of the name it needs to answer.

The cost is more queries in some cases, because a minimised query that receives a referral must be re-issued with a longer name rather than reused. The benefit is that the root and TLD servers no longer see the full set of names a resolver’s clients look up, which reduces the value of observing them. Implementations that minimise must handle the case where the referral and the minimised query disagree, and must fall back to the full query when a server returns an answer that does not fit the minimised name.

The same privacy argument, carried to its conclusion, produces the encrypted transports described in Encrypted DNS Transports and Their Trust Boundaries: minimisation limits what each server learns, and encryption limits who else can see the query at all.