Who actually "recurses" in a recursive DNS lookup?

Question

I'm trying to understand the difference between iterative and recursive DNS lookups. Fundamentally, I think of iterative as being like calling a department store looking for a product, and when they don't have it, they give you the number of another one of their branches to call and then you call the other branch yourself. Versus recursive, which is like calling the department store, and when they don't have what you're after, they call the other branch on your behalf looking for the product. Thing is, I'm getting conflicting views about this when it comes to DNS. When I think of recursive, I think of something that looks like this:

But while reading articles on the web, and even doing a Google image search for DNS recursive, I see far more examples that look like this:

To me, this second example looks more iterative than it does recursive, because each of the "other DNS servers" is telling the "preferred DNS server" the address of the next machine to lookup, rather than looking it up on behalf of the preferred DNS server. The only recursive element I see is that the preferred DNS server does lookups on behalf of the DNS client, but from here on, it sure looks iterative though.

So I guess my question is, does "recursive" DNS lookup really only mean recursive in the sense of the preferred DNS server doing something on the client's behalf, but really iterative from here on in? The majority of results I'm seeing in Google image search are leading me to believe this, which then begs the question, is the first image in this post just plain wrong?

Answer 1

Your last paragraph is correct.

The "Recursion Desired" (RD) flag sent by the client in the DNS request header (see RFC 1035) asks the server "please give me the complete answer to this question".

That server than iteratively asks the chain of name servers for the correct answer. Those queries shouldn't themselves have the RD bit set.

Ultimately the recursive server's response will have the "Recursion Available" (RA) flag set, indicating that the answer was indeed fully answered. Conversely an authoritative server will not set the RA flag.

IMHO, it's a poor choice of terminology.

For what it's worth, that first diagram you've found is fundamentally incorrect. The root servers do not perform queries to any other server, they only issue referrals to other servers.

Answer 2

As far as I understand it, "recursive lookup" is solely from the view of the original querier. So, if it asks a DNS server and gets a completely resolved answer back, then it is a "recursive query". If that server in turn does recursive or iterative lookups is, well, not something the original querier has to care about.

Answer 3

The first of the two diagrams in your question is incorrect. Root servers don't send queries to other servers. If the root servers did in fact forward queries like shown in that diagram the DNS system would be a lot more vulnerable to DoS attacks than it really is.

The second diagram is mostly correct but too simplified to show you the recursive nature of lookups. The diagram is still detailed enough though that we can point out where recursion happens.

The DNS server next to the number 12 the one denoted Preferred DNS server is where recursion happens. The term Preferred DNS server is not standard terminology. That server would usually be called a caching DNS recursor or some abbreviation of that.

When looking at the network traffic it does indeed look iterative. The recursion is entirely internal to the DNS recursor. If you look at the implementation of a DNS recursor you will find some recursive structure in how requests are handled.

The recursion may be easy to spot if the implementation uses a thread per request and the lookups are implemented using recursive function calls. But more efficient designs don't use a thread per request and the recursion is instead found inside the data structures used by the DNS recursor.

The reason that recursion is needed is due to how the references between the authoritative DNS servers are implemented. This is best illustrated with an example. In the diagram you see the authoritative DNS server for microsoft.com point to the authoritative DNS server for example.microsoft.com. This is done using a NS record which points to a hostname. So for example the authoritative server for microsoft.com could tell the DNS recursor that ms.example.net is authoritative for example.microsoft.com.

At that point the DNS recursor would have to resolve ms.example.net before it would be able to proceed with the resolution of example.microsoft.com.

In order to resolve one hostname it first has to resolve a different hostname. That is recursion. In order for this to not lead to infinite recursion, DNS has glue records which are sent along with NS records in certain cases.