Subject: [dnsext] Selecting which name server IP address to query

From: Matthew Dempsky <[email-masked]>
Date: Fri, 22 May 2009 10:18:33 -0700

What algorithm do existing DNS caches use for deciding what IP
addresses to send queries to?

E.g., suppose example.com has the following NS, A, and AAAA records:

    example.com. NS a.ns.example.com.
    example.com. NS b.ns.example.com.
    example.com. NS c.ns.example.com.
    example.com. NS d.ns.exmaple.com.

    a.ns.example.com. A 42.0.0.1
    a.ns.example.com. A 42.0.0.2
    a.ns.example.com. AAAA 2001::1
    a.ns.example.com. AAAA 2001::2

    b.ns.example.com. A 42.0.0.3
    b.ns.example.com. AAAA 2001::3

    c.ns.example.com. A 42.0.0.4

    d.ns.example.com. AAAA 2001::5

How do existing DNS caches decide which IP addresses to query for a
name in .example.com?  I can imagine a lot of variations on how caches
handle the above data set, and I'm just curious to know what existing
practices are.  I haven't noticed any RFCs describing the expected
behavior in this situation, but I might have missed it.

E.g., dnscache does not support sending queries over IPv6, so it only
uses the A records.  It puts all four of them into a list (limited to
the first 16 addresses found), randomly shuffles the list weighing
each address equally, and then cycles through the resulting list until
a name server responds (giving up after a few iterations of the
complete list).  Also, in the case of d.ns.example.com, it will think
the parent server is missing A glue records and spend some extra time
trying to track down A records for it until it can cache an
authoritative NODATA response for d.ns.example.com/A.

Thanks.

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Florian Weimer <[email-masked]>
Date: Fri, 22 May 2009 19:50:30 +0200

* Matthew Dempsky:

> I haven't noticed any RFCs describing the expected
> behavior in this situation,

RFC 3484 mostly covers this (at least the cold cache case).

---

From: Matt Larson <[email-masked]>
Date: Fri, 22 May 2009 15:14:34 -0400

> RFC 3484 mostly covers this (at least the cold cache case).

Well, yes, it describes the cold case, but it doesn't describe
commonly implemented algorithms for name server selection in iterative
resolvers, which is I believe what Matthew was asking about.

BIND's iterative resolver measures round trip time to servers, keeps
state and chooses the server responding the fastest for subsequent
queries to zones served by that server.  There is a brief description
of this algorithm here:

  http://www.dns.net/dnsrd/trick.html#which-server-queried

Last I knew, Microsoft's iterative resolver (in its Windows Server
products) had a similar RTT-based algorithm.  I believe Unbound also
has an RTT-based algorithm (which I should know definitively, but
don't).

Matthew is correct that there isn't guidance documented anywhere, to
my knowledge.  The only place in the DNS specifications that touch on
this that I'm aware of is Section 5.3.3 of RFC 1034.  Note that this
entire problem is essentially summarized in that RFC as:

   2. Find the best servers to ask.

This is yet another gaping hole in the DNSSEC spec, causing each new
implementor to reinvent the wheel.

Matt

---

From: bert hubert <[email-masked]>
Date: Fri, 22 May 2009 22:53:59 +0200

> queries to zones served by that server.  There is a brief description

PowerDNS is both cool (I think) and weird in this respect. PowerDNS
measures RTT, and selects the server with the lowest RTT. Unknown
servers have a 0 RTT.

The measured RTT decays over time, so a server that 'used to be slow'
gets a chance to prove itself after a while (because it is considered
to become 'faster' over time). A timeout is accounted as a 1000ms RTT.
In addition, servers that don't answer get throttled anyhow.

What is not cool is that statistics are kept per nameserver *name* -
which is somewhat of a chicken and egg problem. When confronted with
10 nameserver names, PowerDNS may remember one of them being really
fast, only to discover later on that we forgot its IP address.

The statistics per name are counted as the fastest IP address we used
to know for that name. These decay individually, so all IP addresses
get a chance over time. This includes IPv6 addresses on a strictly
equal basis.

>   2. Find the best servers to ask.

Guidance is fine by me, but I'd hate for an RFC to stifle innovation
by proscribing certain behaviour. This is as true as it is for
legislation ('real laws') as it is for standards.

> implementor to reinvent the wheel.

For DNSSEC, you'd also care about being 'security lame' etc, further
complicating things.

     Bert

---

From: Paul Vixie <[email-masked]>
Date: Sat, 23 May 2009 00:16:17 +0000

> From: bert hubert <[email-masked]>
> Date: Fri, 22 May 2009 22:53:59 +0200
> 
> gets a chance to prove itself after a while (because it is considered to
> become 'faster' over time).  A timeout is accounted as a 1000ms RTT.  In
> addition, servers that don't answer get throttled anyhow.

since many servers have a legitimate TTL in the 5 to 10 second range, what
does this do to your server selection if nonanswer is recorded as 1 second
for the purpose of comparison?

> which is somewhat of a chicken and egg problem.  When confronted with 10
> nameserver names, PowerDNS may remember one of them being really fast,
> only to discover later on that we forgot its IP address.
> 

since multiple addresses used to (before anycasting and loadbalancing) mean
a multihomed server, it's good in my opinion to treat the addresses
separately for most purposes.  one optimization that always seemed useful
to me is that if one of a server's addresses is SERVFAIL'ing for a zone,
it's not necessary to query any of the server's other addresses when making
queries in that zone.  (but it's only an optimization -- so if your NS RR
has expired and you don't know what other addresses belong to the same
server and you have to go get a SERVFAIL from each of them in turn, it's no
big deal.)

> > Matthew is correct that there isn't guidance documented anywhere, to my
> > knowledge.  The only place in the DNS specifications that touch on this
> > that I'm aware of is Section 5.3.3 of RFC 1034.  Note that this entire
> > problem is essentially summarized in that RFC as:
> >

agreed.  the algo described above for powerdns is basically what BIND has
done since 1986, but i always thought of it as a BCP or FYI, and not an STD.

---

From: JINMEI Tatuya / 神明達哉 <[email-masked]>
Date: Sun, 24 May 2009 21:21:37 -0700

At Fri, 22 May 2009 10:18:33 -0700,

>     d.ns.example.com. AAAA 2001::5

I don't know how much of detail you'd like to know, but you may be
interested in the description and analysis of this paper:
http://www.sonycsl.co.jp/~kjc/papers/placement.pdf

I also described BIND9's selection algorithm in more detail in a book
I coauthored.  In case you're interested in this level of details (it
should be easily applicable to your example) I've pasted the relevant
part below (it includes latex markups and some unresolvable references
but I believe it's reasonably readable) where "dns-server-selection"
is the paper I referenced above.

---
JINMEI, Tatuya
Internet Systems Consortium, Inc.

The BIND9 caching server implementation maintains a \textit{smoothed
round trip time} (SRTT) for each remote authoritative server address to
determine in which order the caching server should try the
authoritative servers of a given
zone~\cite{dns-server-selection}\footnote{As noted in
  \cite{dns-server-selection}, older versions of BIND9 did not use an SRTT.}.
The selection algorithm prefers remote servers with
smaller SRTT values since they should be more responsive than others.
In particular, it ensures that a server that is likely to
be down or unreachable will not be tried first for some period,
thereby making the entire resolution process faster.

Here is an example of server address selection.  Assume a caching
server tries to resolve a name under the \verb;example; domain and
gets the following response from the root server:

\begin{verbatim}
  example.  NS ns1.example.
  example.  NS ns2.example.

  ns1.example.  A    192.0.2.1          (15ms)
  ns1.example.  AAAA 2001:db8::1        (10ms)
  ns2.example.  A    192.0.2.2          (20ms)
  ns2.example.  AAAA 2001:db8::2        (30ms)
\end{verbatim}

Also suppose the current SRTT values of each address are the ones
shown with the glue records, which are 15ms, 10ms, 20ms, and 30ms
(from top to bottom).

Then the address selection routine in the BIND9 implementation
constructs a temporary data structure corresponding to these addresses
with their known SRTT values as follows: The names of the nameservers
(i.e., the RDATA of the NS records) compose a list, and each entry of the list
is also a list of IPv4 and IPv6 addresses (i.e., the RDATA of the glue
A and AAAA records).  Each entry of the address list also stores the known
SRTT value of the address. 

Next the address selection routine sorts the addresses as follows: 

\begin{itemize}
  \item It first sorts the list of addresses for each nameserver 
  in ascending order regarding SRTT.  That is, the
  \textit{nearest} address will be placed at the head of the list.
  \item Then the routine sorts the list of the nameservers based on
  the SRTT of the head entry of their address lists.
\end{itemize}

The next step is to choose an address in this list for an outgoing
query.  The decision is made as follows: It begins with the head entry
of the address list in the head entry of the nameserver list.  The
chosen address entry is marked, and is used as the destination address of
the query.  The entry of the nameserver list that contains the chosen
address is remembered for possible retries of the same query.  In the
second try, due to some failure in the first attempt, the search moves
to the next entry to the recorded entry of the nameserver list, and
chooses the first unmarked address entry within its internal list.
Again, the chosen address entry is marked, and this address is used as
the source address.  When the search reaches the end of the nameserver
list, it moves back to the head entry of the list and finds the
first unmarked entry within its internal list.

As a result, the first query will be sent to \verb;2001:db8::1;.  If
it fails due to an erroneous response or timeout, \verb;192.0.2.2;,
\verb;192.0.2.1;, and \verb;2001:db8::2; will be tried in this order.
It should be noted that the second
query will be sent to \verb;192.0.2.2;, while its SRTT is larger than
that of \verb;192.0.2.1;.  This probably comes from the observation
that the same server name (such as \verb;ns1.example;) is likely to
specify the same server, and that if one of the addresses does
not work others will likely not either.

Sending a query to the selected address may fail for various reasons.
One common case is that the querying server runs a dual-stack kernel supporting
both IPv4 and IPv6 but does not have IPv6 connectivity.
Usually the server implementation will notice the failure from the
result of the sending system call (which is \verb;sendmsg(); in the case
of BIND9)
and can move to a different address quickly.
In addition, the SRTT of the address for which \verb;sendmsg(); fails
is penalized so that the preference level of this address for
succeeding queries will be lowered.

The BIND9 implementation initializes the SRTT of each server address with a
random value.
Considering some top level authoritative servers have IPv6 addresses
(i.e., AAAA glue records) as was seen in Section \ref{chap2-3subsec:edns0},
this means that an IPv6 address can be the first candidate even
on a caching server without IPv6 connectivity.  The immediate fall back
described above is thus crucial for smooth operation.
In fact, until version 9.2.5 and 9.3.1, BIND9 did not handle erroneous
results of \verb;sendmsg();, occasionally causing a few seconds of
delay in name resolution under the \verb;com; domain.  This had been
a well-known trouble for some period of time.