Subject: [DNSOP] Possible slower response with minimization

From: Bob Harold <[email-masked]>
Date: Mon, 20 Oct 2014 17:03:19 -0400

I support the idea of qname minimization, but I think there is a common
case where it will cause additional DNS round trips, slowing the response
and increasing the number of packets and queries the servers must handle.

Consider “www.host.group.department.example.com” where the company’s
servers are authoritative for the zones:

example.com
department.example.com
group.department.example.com

Without minimization (typical today):

1. Query root for “www.host.group.department.example.com”, get list of
“com” servers.
2. Query a com server for “www.host.group.department.example.com”, get list
of “example.com” servers.
3. Query an example.com server for “www.host.group.department.example.com”,
get answer.

With minimization:

1. Query root for “com”, get list of “com” servers.
2. Query a com server for “example.com”, get list of “example.com” servers.
3. Query an example.com server for “department.example.com”, get list of “
department.example.com” servers (which happens to be the same as the list
of “example.com” servers).
4. Query a “department.example.com” server (likely the same server as step
3) for “group.department.example.com”, get list of “
group.department.example.com” servers.
5. Query a “group.department.example.com” server for “host.group.example.com”,
get probably just an A and/or AAAA record, indicating there is no zone cut
at that level.
6. Query a “group.department.example.com” server for “
www.host.group.department.example.com”, get answer.

Note that it takes twice as many queries, and each depends on the previous,
so it is twice as many round trips.

I realize that caching will reduce the extra queries in many cases, but can
we estimate the impact of this somehow, to determine if it is significant?

-- 

Bob Harold
DNS hostmaster, University of Michigan

---

From: Tim Wicinski <[email-masked]>
Date: Mon, 20 Oct 2014 17:06:53 -0400

I think part of the work on qname-minimization will spend some time 
studying performance, as well as operational issues as Peter brought up.

It could very well be that what Peter pointed out will be true and there 
are operational issues that could cause acceptance.  But part of this 
work will be to understand and document these effects, correct?

tim
(finally back home and catching up)

On 10/20/14 5:03 PM, Bob Harold wrote:
> case where it will cause additional DNS round trips, slowing the
> response and increasing the number of packets and queries the servers
> must handle.
>
> Consider “www.host.group.department.example.com
> <http://www.host.group.department.example.com>” where the company’s
> example.com <http://example.com>
> department.example.com <http://department.example.com>
> group.department.example.com <http://group.department.example.com>
>
> 1. Query root for “www.host.group.department.example.com
> <http://www.host.group.department.example.com>”, get list of “com” servers.
> 2. Query a com server for “www.host.group.department.example.com
> <http://www.host.group.department.example.com>”, get list of
> “example.com <http://example.com>” servers.
> 3. Query an example.com <http://example.com> server for
> “www.host.group.department.example.com
> <http://www.host.group.department.example.com>”, get answer.
>
> With minimization:
>
> 2. Query a com server for “example.com <http://example.com>”, get list
> of “example.com <http://example.com>” servers.
> 3. Query an example.com <http://example.com> server for
> “department.example.com <http://department.example.com>”, get list of
> “department.example.com <http://department.example.com>” servers (which
> happens to be the same as the list of “example.com <http://example.com>”
> servers).
> 4. Query a “department.example.com <http://department.example.com>”
> server (likely the same server as step 3) for
> “group.department.example.com <http://group.department.example.com>”,
> get list of “group.department.example.com
> <http://group.department.example.com>” servers.
> 5. Query a “group.department.example.com
> <http://group.department.example.com>” server for
> “host.group.example.com <http://host.group.example.com>”, get probably
> just an A and/or AAAA record, indicating there is no zone cut at that level.
> 6. Query a “group.department.example.com
> <http://group.department.example.com>” server for
> “www.host.group.department.example.com
> <http://www.host.group.department.example.com>”, get answer.
>
> Note that it takes twice as many queries, and each depends on the
> previous, so it is twice as many round trips.
>
> I realize that caching will reduce the extra queries in many cases, but
> can we estimate the impact of this somehow, to determine if it is
> significant?
>
> --
>
> Bob Harold
>
> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 20 Oct 2014 17:26:29 -0400

If we are going there, I would want to know how common the configurations are.

There is zero additional overhead for www.example.com

Outside this list how common are hierarchies more than 4 levels deep in practice?

This isn't a functionality issue, it's purely performance. So I suggest a 5% minimum occurrence threshold for considering any corner cases. And made up examples don't count

Sent from my difference engine

> On Oct 20, 2014, at 5:06 PM, Tim Wicinski <[email-masked]> wrote:
> 
> 
> 
> I think part of the work on qname-minimization will spend some time studying performance, as well as operational issues as Peter brought up.
> 
> It could very well be that what Peter pointed out will be true and there are operational issues that could cause acceptance.  But part of this work will be to understand and document these effects, correct?
> 
> tim

---

From: Paul Vixie <[email-masked]>
Date: Mon, 20 Oct 2014 14:30:11 -0700

there's a cart/horse proble in this thread.

right now we're arguing whether to adopt it.

if we adopt it then its goods and bads will become relevant.

that said:

> Bob Harold <mailto:[email-masked]>
> Monday, October 20, 2014 2:03 PM
>
> I support the idea of qname minimization, but I think there is a
> common case where it will cause additional DNS round trips, slowing
> the response and increasing the number of packets and queries the
> servers must handle.
>

i argue that caching will equalize these logic paths over a very short
stretch of wall time.

-- 
Paul Vixie

---

From: Doug Barton <[email-masked]>
Date: Mon, 20 Oct 2014 21:19:16 -0700

> Consider “www.host.group.department.example.com

Your analysis is correct, but only for a cold cache. Once the resolver 
has cached the NS records for group.department.example.com the penalty 
no longer applies.

One thing that may be a worthwhile consideration though is a way to 
cache that host.group.... is not a zone cut. That would further reduce 
the penalty.

FWIW, I also have some concerns about empty non-terminals, but none of 
that slows me down in terms of supporting WG adoption. I think it's a 
worthy idea, and I'll do what I can to help.

Doug

---

From: Masataka Ohta <[email-masked]>
Date: Tue, 21 Oct 2014 14:14:49 +0900

Doug Barton wrote:

> Your analysis is correct, but only for a cold cache. Once the
> resolver has cached the NS records for group.department.example.com
> the penalty no longer applies.

As the choice between privacy and latency is on resolver side,
moderate latency is not harmful.

Note that DNSSEC with cold cache should mean prohibitively
long initial latency, which means those who try to use DNSSEC
must give up security of privacy.

> FWIW, I also have some concerns about empty non-terminals,

Right, NXDOMAIN returned by some broken implementation to
empty non-terminals MUST NOT be interpreted that the
terminals does not exist.

					Masataka Ohta

---

From: Ray Bellis <[email-masked]>
Date: Tue, 21 Oct 2014 09:26:00 +0000

> terminals does not exist.

Can we name and shame these broken implementations?

It would be a massive shame if this important and useful clarification to DNS semantics couldn't be used just because of a few broken implementations.

Ray

---

From: Masataka Ohta <[email-masked]>
Date: Tue, 21 Oct 2014 19:11:50 +0900

> Can we name and shame these broken implementations?

I don't know about a specific example.

But, considering that people here was having lengthy debates
on how should the response to empty non-terminals until I pointed
out relevant part of rfc1034 means there should have been, and,
more importantly, will again be,  some.

> It would be a massive shame if this important and useful
> clarification to DNS semantics couldn't be used just because
> of a few broken implementations.

It is clearly specified in rfc1034:

   The domain name space is a tree structure.  Each node and leaf
   on the tree corresponds to a resource set (which may be empty).

						Masataka Ohta

---

From: Ray Bellis <[email-masked]>
Date: Tue, 21 Oct 2014 11:25:18 +0000

> On 21 Oct 2014, at 11:11, Masataka Ohta <[email-masked]> wrote:
> 

That’s a matter of interpretation.

To me, that _clearly_ indicates that the name exists (given that the “label” is a property of the node, which clearly does exists) and therefore that NXDOMAIN is inappropriate.

Ray

---

From: Edward Lewis <[email-masked]>
Date: Tue, 21 Oct 2014 09:43:19 -0400

Adopt it.

Then argue about it.

I think it is worthwhile to talk about.  IMHO it isn’t a protocol change, but a change to how a recursive element looks for an answer in the existing protocol.

On Oct 20, 2014, at 17:30, Paul Vixie <[email-masked]> wrote:

>> 	Bob Harold	Monday, October 20, 2014 2:03 PM
>> I support the idea of qname minimization, but I think there is a common case where it will cause additional DNS round trips, slowing the response and increasing the number of packets and queries the servers must handle.
> 
> i argue that caching will equalize these logic paths over a very short stretch of wall time.
> 
> -- 
> Paul Vixie

---

From: Masataka Ohta <[email-masked]>
Date: Tue, 21 Oct 2014 23:03:08 +0900

Ray Bellis wrote:

> To me, that _clearly_ indicates that the name exists (given that the
> “label” is a property of the node, which clearly does exists) and
> therefore that NXDOMAIN is inappropriate.

Yes, it is, even for those who debated a lot here without reading
rfc1034 or those who read the rfc so long ago that they don't
remember its content, but only after the text is presented to them.

The problem is that, for those who don't fully understand/remember
DNS, empty non terminals can be a pitfall with high probability,
against which new proposals should be protected.

						Masataka Ohta

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Sat, 25 Oct 2014 17:57:50 +0200

On Mon, Oct 20, 2014 at 05:26:29PM -0400,
 Phillip Hallam-Baker <[email-masked]> wrote 

> If we are going there, I would want to know how common the

Yes, actual numbers seen from a real resolver would be useful.

> Outside this list how common are hierarchies more than 4 levels deep

ip6.arpa, and other infrastructure domains?

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Sat, 25 Oct 2014 17:56:45 +0200

On Mon, Oct 20, 2014 at 05:03:19PM -0400,
 Bob Harold <[email-masked]> wrote 

> With minimization:

Besides the fact that it is true only for a cold cache (as mentioned
by others in this thread), it depends on how minimisation is
implemented. One possible way is "aggressive minimisation" (the
algorithm you describe), but another one is "lazy minimisation"
(sending the full qname at the beginning and learning the zone cuts,
then switching to minimisation). If it is realistic (I did not analyze
the idea in detail), lazy minimisation will bring less privacy but
will improve performances.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Sat, 25 Oct 2014 18:05:16 +0200

On Tue, Oct 21, 2014 at 02:14:49PM +0900,
 Masataka Ohta <[email-masked]> wrote 

> moderate latency is not harmful.

I fully agree. Qname minimisation is an _unilateral_ decision. Any
resolver can make its own trade-off, depending on its administrator's
choices.

dataminimisation: on|off (programmers, pick the best default value)

> terminals does not exist.

Full agreement again and I suggest everyone to consider
draft-vixie-dnsext-resimprove-00, section 3 (an useful thing for qname
minimisation but also against current "random qnames" attacks
<https://indico.dns-oarc.net//contributionDisplay.py?contribId=37&sessionId=3&confId=20>).

---

From: Paul Vixie <[email-masked]>
Date: Sat, 25 Oct 2014 11:08:35 -0700

> Stephane Bortzmeyer <mailto:[email-masked]>
> Saturday, October 25, 2014 9:05 AM

i disagree with this. broken implementations who emit NXDOMAIN for empty
non-terminals cannot be used as an excuse not to develop and deploy
correct protocol and software enhancements. the internet has hundreds of
years to run yet, and these broken implementations are (a) shrinking not
growing, and (b) subject to rapid replacement when they start to
encounter problems with correct enhancements to their habitat.
> <https://indico.dns-oarc.net//contributionDisplay.py?contribId=37&sessionId=3&confId=20>).

stephane, i believe you misunderstood the sense of ohta-san's remarks.

-- 
Paul Vixie

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Sat, 25 Oct 2014 21:31:41 +0200

On Sat, Oct 25, 2014 at 06:05:16PM +0200,
 Stephane Bortzmeyer <[email-masked]> wrote 
 a message of 24 lines which said:

> Full agreement again 

Paul Vixie was right, I've read your sentence too fast. I focused on
the "broken implementation" part (on which we agree, these
implementations are awfully broken) and missed the meaning of the
double negation. So, to rephrase it, my opinion is:

NXDOMAIN returned by some broken implementation to empty non-terminals
is a bug. A NXDOMAIN MUST be interpreted as "the node in the domain
tree, AND ALL ITS SUBNODES, do not exist".

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 27 Oct 2014 10:13:20 -0400

On Sat, Oct 25, 2014 at 2:08 PM, Paul Vixie <[email-masked]> wrote:

>
>
>   Stephane Bortzmeyer <[email-masked]>
>  Masataka Ohta <[email-masked]> <[email-masked]> wrote
> non-terminals cannot be used as an excuse not to develop and deploy correct
> protocol and software enhancements. the internet has hundreds of years to
> run yet, and these broken implementations are (a) shrinking not growing,
> and (b) subject to rapid replacement when they start to encounter problems
> with correct enhancements to their habitat.
>

I agree with the sentiment. But there is a way to get the implementations
to converge and that is to build something on top that consumes DNS
Authoritative date and makes particular assumptions that is widely enough
used to create an incentive.

---

From: Mark Andrews <[email-masked]>
Date: Tue, 28 Oct 2014 09:00:29 +1100

In message <CAMm+Lwh=75oXwbubuB19rYhhMbfO=[email-masked]>, Phillip 
> used to create an incentive.

People will learn.

There were nameservers that returned NXDOMAIN to AAAA queries.  These have
basically gone as they caused operational problems

There are nameservers that return NXDOMAIN to unknown EDNS options.  See
the bind-users archives.  These will go as people report them.

There are nameservers that return NXDOMAIN to empty non terminals.  These
too will go as soon as that start causing operational problems.  At the
moment NXDOMAIN and NODATA don't cause a issue for most applications.

Mark
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Warren Kumari <[email-masked]>
Date: Mon, 27 Oct 2014 18:09:49 -0400

>> Outside this list how common are hierarchies more than 4 levels deep

Surprisingly enough, not an insignificant number -- but this is
mitigated by what the queries are (see below)

> ip6.arpa, and other infrastructure domains?

There is a long tail, but:
~51% of lookups are of length 3 (www.example.com)
~23% of lookups are of length 5 (this was surprising to me, but is
largely dominated by Akamai - www.example.com.akadns.net)
~15% of lookups are of length 4 (usually service.something.largecompany.com)

This means that lengths 3, 4, 5 account for ~89% of lookups. If you
include lengths of 1 and 2 you get  >96%
Many of these (like the akamai ones, .com, etc) look like they would
cache every well...

In the long tail there are the ip6.arpa, in-addr.arpa, some dnsbls and
then a bunch of anti-virus / web-filter stuff (things like <really
long b64(?) encoded string>.sophosxl.com or <some opaque
string>.avts.mcafee.com), and some "obviously" broken queries
www.www.www.www.www.www.www.www.www.cnn.com)

So, while looking at this I stumbled across something, um, odd...
wkumari@vimes:~$ dig ns +noall +comments apple.com.akadns.net
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 27395
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 1

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
'kay...

wkumari@vimes:~$ dig ns +noall +comments com.akadns.net
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 3341
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 1

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096

Er... wouldn't this break with qnm? (obviously fixable, but an
interesting data point). It has been a long day, so perhaps I'm
missing something as well...

W

-- 
I don't think the execution is relevant when it was obviously a bad
idea in the first place.
This is like putting rabid weasels in your pants, and later expressing
regret at having chosen those particular rabid weasels and that pair
of pants.
   ---maf

---

From: Doug Barton <[email-masked]>
Date: Mon, 27 Oct 2014 15:44:12 -0700

> missing something as well...

Yeah, I was thinking about this same concept over the weekend. 
Minimalization is definitely a privacy benefit when dealing at the root 
and TLD levels, and fortunately those are the easiest cases to detect. 
:) I think it's less useful when you've navigated "into" the 
domain-holder's space. As y'all know that border is harder to determine 
in the ccTLD space.

We already have projects that have bravely gone into these details ... 
https://wiki.mozilla.org/Public_Suffix_List comes to mind of course. It 
shouldn't be too difficult to code using that information as a third 
alternative to "on" or "off" for qnm.

Using that kind of intelligence would go a long way towards reducing the 
complaints about qnm adding inefficiency. In fact unless I'm missing 
something it would largely eliminate them. There is no benefit to 
sending the whole query to the root or TLD servers, and lots of privacy 
benefits for not doing so. OTOH, there is a lot of benefit to sending 
the whole query to the domain holder's servers, and minimal privacy 
negatives. Sounds like a win-win to me.

Doug

---

From: Mark Andrews <[email-masked]>
Date: Tue, 28 Oct 2014 09:44:26 +1100

In message <CAHw9_iLzKsqSWLV+BdcG_R-d9Jd-=[email-masked]>, Warren K
> missing something as well...

Yes, there are lots of broken nameservers out there.  This doesn't
have to remain the case.  Audit all the servers for the zone delegated
from TLD and SLD infrastructure zones and with and without www
prepended.

Report the errors found and request that they contact their nameserver
/ firewall vendor for a fix.

Repeat 3 months later with a warning that the delegation will be
removed if the issue is not fixed for those contacted on the previous
run.

Repeat 3 months late and remove all delegations which have had the
2 previous message.

Repeat at 3 monthly interval to catch new instances.

Unlike bad delegations.  You don't get many regressions.  Once a
nameserver is fixed it tends to stay fixed.

This gives them 6 months to deploy a fix.

---

From: Tony Finch <[email-masked]>
Date: Tue, 28 Oct 2014 10:16:47 +0000

> mitigated by what the queries are (see below)

Large organizations in countries with special-purpose 2LDs easily get
quite long, e.g. www.pubs.sp.phy.cam.ac.uk, and that involves only four
zones so it's a good example of a situation where qname minimization would
do badly.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Trafalgar: Cyclonic in northwest, otherwise mainly northerly or northwesterly
5 or 6. Slight or moderate. Showers in northwest. Good.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 29 Oct 2014 15:53:03 +0100

On Mon, Oct 27, 2014 at 06:09:49PM -0400,
 Warren Kumari <[email-masked]> wrote 

> wkumari@vimes:~$ dig ns +noall +comments com.akadns.net

[Example of a nameservcer replying NXDOMAIN for an ENT.]

> Er... wouldn't this break with qnm?

Depending on how it is implemented, yes, may be, or no. Remember that
QNAME m12n is not a protocol but a general principle, that different
resolvers may implement slightly differently.

> It has been a long day, so perhaps I'm missing something as well...

The issue is described in draft-vixie-dnsext-resimprove-00 (section 3)
and partially in draft-ietf-dnsop-qname-minimisation-00 (section 3).

---

From: Warren Kumari <[email-masked]>
Date: Wed, 29 Oct 2014 11:02:10 -0400

> [Example of a nameservcer replying NXDOMAIN for an ENT.]

Yes, I'm just surprised that Akamai suffers from it.

> and partially in draft-ietf-dnsop-qname-minimisation-00 (section 3).

Yup. Just expected better from akamai.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 29 Oct 2014 16:02:15 +0100

On Mon, Oct 27, 2014 at 03:44:12PM -0700,
 Doug Barton <[email-masked]> wrote 
 a message of 86 lines which said:

> https://wiki.mozilla.org/Public_Suffix_List comes to mind of
> course. 

[See also the DBOUND effort
<https://www.ietf.org/mailman/listinfo/dbound>, which seems currently
dead.]

> Using that kind of intelligence would go a long way towards reducing
> the complaints about qnm adding inefficiency.

My personal feeling is that it is not worth the extra complication
(and dependance towards a far-from-perfect external list).

---

From: David C Lawrence <[email-masked]>
Date: Wed, 29 Oct 2014 14:23:19 -0400

Warren Kumari:
> Stephane Bortzmeyer <[email-masked]>:

It is definitely considered a bug and has had a CR open for it for
almost 10 years, but since there has been no noticeable, practical
operational impact it has never had any time spent on addressing it.

qname-minimisation would change that of course, and personally I don't
mind.  It's nice to finally close out CRs from the long long ago.

Incidentally, the logic of how a name is resolved by Akamai's
nameservers varies depending on the type of service the zone is
providing.  This bug is particular to only one type of service.