Subject: [DNSOP] I-D Action: draft-ietf-dnsop-nxdomain-cut-01.txt

From: [email-masked]
Date: Thu, 10 Mar 2016 12:59:49 -0800

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Domain Name System Operations of the IETF.

        Title           : NXDOMAIN really means there is nothing underneath
        Authors         : Stephane Bortzmeyer
                          Shumon Huque
	Filename        : draft-ietf-dnsop-nxdomain-cut-01.txt
	Pages           : 10
	Date            : 2016-03-10

Abstract:
   This document states clearly that when a DNS resolver receives a
   response with response code of NXDOMAIN, it means that the domain
   name which is thus denied AND ALL THE NAMES UNDER IT do not exist.

   REMOVE BEFORE PUBLICATION: this document should be discussed in the
   IETF DNSOP (DNS Operations) group, through its mailing list.  The
   source of the document, as well as a list of open issues, is
   currently kept at Github [1].

   This documents clarifies RFC 1034 and modifies a bit RFC 2308 so it
   updates both of them.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-ietf-dnsop-nxdomain-cut/

There's also a htmlized version available at:
https://tools.ietf.org/html/draft-ietf-dnsop-nxdomain-cut-01

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-ietf-dnsop-nxdomain-cut-01

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 10 Mar 2016 22:07:04 +0100

On Thu, Mar 10, 2016 at 12:59:49PM -0800,
 [email-masked] <[email-masked]> wrote 

> 	Filename        : draft-ietf-dnsop-nxdomain-cut-01.txt
...
> https://www.ietf.org/rfcdiff?url2=draft-ietf-dnsop-nxdomain-cut-01

Main change: reorganisation of the text so that the normative section
2 is written in a purely protocol-behaviour way, without any reference
to the implementation. Section 5 now discuss implementation.

---

From: Ted Lemon <[email-masked]>
Date: Fri, 11 Mar 2016 04:26:19 +0000

> to the implementation. Section 5 now discuss implementation.

This seems like the right thing to do.   However, I think that this document still goes too far in terms of assuming a particular implementation, in the sense that it appears to assume that the cache is a tree.   If the cache is a hash, the requirement at the beginning of section two is actually expensive to implement, depending on how thorough one wants to be, and also depending on whether we rely on DNSSEC or not.

I think this document could be made a lot simpler if it simply said what it says in the abstract, without placing new requirements on DNS caches.   Right now it says DNS caches SHOULD take an NXDOMAIN on a particular domain as applying to all names under it.   This is certainly a valid thing to do, and I can think of ways to do it reasonably efficiently even wish a hashed cache, but reasonably is still O(number of labels) instead of O(1).   If you just say what the abstract says and nothing more, that allows implementations to be "more efficient," as you suggest, without requiring implementations to be less efficient.   Granted, it's a SHOULD, but I think that still goes too far.   You should just say that NXDOMAIN means what you want it to mean, and leave it at that.

BTW, is this even in charter for DNSOP?   I suppose the theory is that it falls under item 4 in the charter, but that seems like a stretch to me.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 11 Mar 2016 21:17:51 +0100

On Fri, Mar 11, 2016 at 04:26:19AM +0000,
 Ted Lemon <[email-masked]> wrote 
 a message of 13 lines which said:

> However, I think that this document still goes too far in terms of
> assuming a particular implementation, in the sense that it appears
> to assume that the cache is a tree.

It is certainly not the goal. Can you tell exactly where it is
assumed? Section 2 is supposed to be implementation-neutral. Section 5
discusses implementations but does not assume or recommend a specific
one. Section 1 uses the word "tree" but to describe the abstract data
structure (you will certainly agree that domain names are a tree...)
not the actual implementation.

> If the cache is a hash, the requirement at the beginning of section
> two is actually expensive to implement,

This is exactly what section 5 says (last paragraph).

> I think this document could be made a lot simpler if it simply said
> what it says in the abstract, without placing new requirements on
> DNS caches.

I disagree here. This is (if approved) a normative document. It does
place "new" requirments. (I write "new" between quotes because
resolvers with NXDOMAIN cut behavior are, IMHO, legal even today, the
original RFCs are not perfectly clear.)

> BTW, is this even in charter for DNSOP?  I suppose the theory is
> that it falls under item 4 in the charter, but that seems like a
> stretch to me.

It is a change in the behaviour of the majority of resolvers, but not
a change in the protocol. So, yes, it is "to address operational
issues with the DNS protocols by extending or performing protocol
maintenance on them"

---

From: Ted Lemon <[email-masked]>
Date: Fri, 11 Mar 2016 20:52:20 +0000

> assumed? Section 2 is supposed to be implementation-neutral.

Right here:

   When an iterative caching DNS resolver receives a response NXDOMAIN,
   it SHOULD store it in its cache and all names and RRsets at or below
   that node SHOULD then be considered to be unreachable.  Subsequent
   queries for such names SHOULD elicit an NXDOMAIN response.

"At or below" assumes a tree.   Just because it isn't explicitly mentioned doesn't mean that it's not saying that!

> This is exactly what section 5 says (last paragraph).

Yes, it does say that, and I agree with what it says--I'm just proposing that the document be changed so that it's not necessary to say that.

> original RFCs are not perfectly clear.)

This is what I'm saying: it shouldn't be making requirements on the resolver.   It should just clarify that if you get an NXDOMAIN for name K, any name that is a subdomain of K can be assumed also to return an NXDOMAIN.

> issues with the DNS protocols by extending or performing protocol

Any protocol change that changes the operation of the DNS in any way can be justified on this basis.   If that is what this section of the charter means, then we can make nearly any change to the protocol that we want and still be in charter.   I think more reasonably what this section of the charter means is that you can update the protocol to address an operational problem.   But this draft isn't really adressing an operational problem: your motivation for doing this is to support DPRIVE, not because anybody is going to notice a reduction in the number of queries even if this is widely implemented.   It's not even addressing a serious problem in DPRIVE.   If it's just to address a subset of possible PRSD attacks, the protocol clarification without the requirement is already sufficient, because the clarification adds a tool for implementors who are motivated to use this technique to address that problem, but is not required of implementors who want to approach it in a different way.

---

From: Paul Vixie <[email-masked]>
Date: Fri, 11 Mar 2016 15:46:14 -0800

Ted Lemon wrote:
> "At or below" assumes a tree. Just because it isn't explicitly
> mentioned doesn't mean that it's not saying that!

i took the words "at or below" to mean "in-bailiwick". caches that are 
not organized as tree-like data structures still have to be able to find 
the closest encloser, which means they do know ancestor/descendent 
relationships, even if the data structure itself is otherwise flatishly 
hashlike.

-- 
P Vixie

---

From: Shumon Huque <[email-masked]>
Date: Fri, 11 Mar 2016 19:09:54 -0500

> doesn't mean that it's not saying that!

Perhaps we can make it explicit that the tree here is conceptual, and
not an implementation required data structure?

The domain name space is certainly defined in terms of a tree structure.
And the cache being a subset of the data in the domain name space -- it
is much easier to reason about it in terms of that tree structure and to
describe things in those terms (names under/above, descendent names,
subtrees etc). In fact, the DNS algorithm description in RFC 1034 clearly
states an assumption that the cache is a tree structure, so the precedent
is already well established: see section 4.3.2 which says "The following
algorithm assumes that the RRs are organized in several tree structures,
one for each zone, and another for the cache:" ...

Personally, I would be okay with removing the "Implementation
Considerations"
section.

On the question of "SHOULD", I was hoping we'd get rough consensus
that this is a good goal, in terms of making the entire DNS ecosystem
more efficient - why should resolvers make unnecessary outbound
queries for name that don't exist, and why should authoritative servers
receive those queries? But I understand the concern that there might be
implementation challenges for some.

-- 
Shumon Huque

---

From: Ted Lemon <[email-masked]>
Date: Sat, 12 Mar 2016 04:13:34 +0000

> not an implementation required data structure?

That's not the point.   The point is that if the _cache_ is represented as a tree, then you can talk about names being "under" other names; if it's not, then that relationship doesn't exist _in the cache_ even though it _does_ exist in the namespace.

> subtrees etc).

Absolutely right.   The problem is that are not just reasoning about it: we are placing a requirement on implementations.

> implementation challenges for some.

That's up to the chairs to decide, but I certainly don't think we _should_ have consensus on this point without having some sense of whether there is any measurable real-world increase in efficiency.   This is easy to implement, as is any proposal; the question is, do we want to slow down _every_ query in order to speed up a very tiny number of queries?   A hashed implementation will, for every query, have to check every label in the question, starting from the root, a cached NXDOMAIN record, and almost every time will find nothing.   So this is really quite a significant increase in overhead.   Whereas the increase in efficiency even for caches that use a tree data structure will be down in the noise.

What this might be is a quick speed hack for dealing with PRSD attacks in caches that use trees.   So I support _allowing_ this behavior.   I just don't support requiring it, and if you do, you should really do some measurements to show that there is a _significant_ speed improvement to justify such a requirement.   Otherwise, I think that this change is out of charter, because there's no operational issue that this new _requirement_ addresses, even if the clarification has some value operationally.

---

From: Ted Lemon <[email-masked]>
Date: Sat, 12 Mar 2016 04:18:29 +0000

> relationships, even if the data structure itself is otherwise flatishly

The most straightforward way to implement this is to say "FOO.BAR.COM"'s closest encloser is BAR.COM, and then look BAR.COM up in the cache.   Which is fine when you _need_ to do that.   It's not fine to do it on every query even when it otherwise would not have been necessary (which would be the vast majority of cases).   But to implement this algorithm you need to start at the room, so first look at ".", then at "COM", then at "BAR.COM".   That's three hash lookups if there's a cached NXDOMAIN, and four if there isn't.   Blech.

---

From: Paul Vixie <[email-masked]>
Date: Fri, 11 Mar 2016 22:58:46 -0800

Ted Lemon wrote:
> The most straightforward way to implement this is to say
> "FOO.BAR.COM"'s closest encloser is BAR.COM, and then look BAR.COM up
> in the cache. Which is fine when you _need_ to do that. It's not fine
> to do it on every query even when it otherwise would not have been
> necessary (which would be the vast majority of cases). But to
> implement this algorithm you need to start at the room, so first look
> at ".", then at "COM", then at "BAR.COM". That's three hash lookups
> if there's a cached NXDOMAIN, and four if there isn't. Blech.

Ted, I think you're reading it wrong. The implementation doesn't matter 
at all. As Co-Chair Woolf kindly and classily 2x4'd me last year, an RFC 
should be of the form "if you want to do X, here's a way to do it 
interoperably."

This specification should express the basic idea that after an NXDOMAIN 
has been received from an authority server for name X, then the receiver 
of that NXDOMAIN is allowed to (note: "allowed to"; this is optional, 
and is just an optimization) treat it as also applying to any name that 
is in-bailiwick for X. (Sometimes that will be expressed as "at or below 
X" or "a subdomain of X".)

If an implementation doesn't perform this optimization, then for names 
below X, it will forward queries to an authority, who WILL answer with 
NXDOMAIN unless the name-below-X has actually been created in the time 
since the NXDOMAIN for X itself was received.

Like all other forms of negative caching, this is just a speedup, and if 
a cache is implemented in a way that makes "is there a negative cache 
element for whose owner name this qname is in-bailiwick?" too expensive, 
then that negative caching implementation will probably not perform this 
optimization.

There is a specification clarification here: QUERY for an empty 
non-terminal name must yield response RCODE=0 ANCOUNT=0 even for 
QTYPE=255. I've always interpreted RFC 1034+1035 that way but not every 
implementer did. This clarification is nec'y for the optimization being 
described, since otherwise an empty non-terminal could hide all of its 
subdomains from implementations of the optimization under discussion.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Sun, 13 Mar 2016 18:29:37 +0000

> X" or "a subdomain of X".)

This is what the specification _should_ say, not what it _does_ say.

> then that negative caching implementation will probably not perform this

If it's a speed hack, there shouldn't be any normative language associated with implementing it.   I'm objecting to the normative language, not the clarification that allows the speed hack.   I agree with the clarification.

---

From: Paul Vixie <[email-masked]>
Date: Sun, 13 Mar 2016 12:32:53 -0700

> This is what the specification _should_ say, not what it _does_ say.

you've caught me out as to not having read drafts after -00. what i did 
read was this:

http://tools.ietf.org/html/draft-vixie-dnsext-resimprove-00

which says:

> 3. Stopping Downward Cache Search on NXDOMAIN
>
>    3.1. In virtually all existing resolvers, a cached NXDOMAIN is not
>    considered "proof" that there can be no child domains underneath.
>    This is due to an ambiguity in RFC 1034 that failed to distinguish
>    empty nonterminal domain names from nonexistent names.  For DNSSEC,
>    the IETF had to distinguish this case, but the implication on non-
>    DNSSEC resolvers wasn't fully realized.
>
>    3.2. When searching downward in its cache, an iterative caching DNS
>    resolver should stop searching if it encounters a cached NXDOMAIN.
>    The response to the triggering query should be NXDOMAIN.
>
>    3.3. When an iterative caching DNS resolver stores an NXDOMAIN in its
>    cache, all names and RRsets at or below that node should be deleted
>    since they will have become unreachable.
>
>    3.4. By implication, a stream of queries FOO.TLD, BAR.FOO.TLD where
>    FOO.TLD does not exist would normally cause both queries to be
>    forwarded to TLD's nameservers. Following this recommended practice,
>    the second query and indeed any other query for names at or below
>    FOO.TLD would not be forwarded.

my reason for quoting this here will be apparent below.

> If it's a speed hack, there shouldn't be any normative language
> associated with implementing it. I'm objecting to the normative
> language, not the clarification that allows the speed hack. I agree with
> the clarification.

i argue that in resimprove-00 (which is superceded by the bortzmeyer 
nxdomain work, as to this nxdomain topic), we ought to have written "can 
be deleted" rather than "should be deleted", since deletion is a storage 
optimization that has no on-the-wire effect.

as to the word "downward" in the face of modern caches which aren't 
nec'ily hierarchical, i think i chose the right word, since 1034+1035 
describe system properties by use of phrases like "search downward". the 
hierarchical nature of the cache is not a necessary property of actual 
caches, but the responder's behaviour is described that way. to fix this 
would be awkward:

3.3 When searching its cache, an iterative caching DNS resolver should 
discover any cached NXDOMAIN for which the QNAME is in-bailiwick, and in 
this case, the response should be NXDOMAIN, even if there are other data 
stored in the cache at owner subdomains of the cached NXDOMAIN.

what i'm urging here is great caution both for the authors and the 
reviewers. improving the readability of this topic over what we wrote in 
resimprove-00 seems necessary but is not a simple proposition.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Mon, 14 Mar 2016 02:55:50 +0000

> resimprove-00 seems necessary but is not a simple proposition.

I don't think this is actually all that complicated.   The problem is that you are trying to give implementation advice, and you just shouldn't be doing that.   Stop giving implementation device and it gets easy:

Names subsidiary to a cached NXDOMAIN MAY be assumed to be nonexistent for <interval>.  Some cache implementations may be able to realize performance improvements for queries under cached NXDOMAINs by making this assumption.   Implementors of caches are expected to be smart enough to figure out whether this is true of their implementation.

That's obviously not detailed enough, and the last point doesn't need to be stated explicitly, but that's the basic point you want to get across.   Anything more than that is too much.   The reason the WG is getting pushback from me on this is precisely that the draft gives implementation advice that I know is not universally applicable, and quite unnecessarily states that advice in the form of a strong normative recommendation.   This is not something the WG should be doing.   Implementation advice should never be even a little bit normative.

---

From: abby pan <[email-masked]>
Date: Mon, 14 Mar 2016 02:59:02 +0000

Ted Lemon <[email-masked]>于2016年3月11日周五 下午12:26写道：

>
> I think this document could be made a lot simpler if it simply said what
> it says in the abstract, without placing new requirements on DNS caches.
>  Right now it says DNS caches SHOULD take an NXDOMAIN on a particular
> domain as applying to all names under it.   This is certainly a valid thing
> to do, and I can think of ways to do it reasonably efficiently even wish a
> hashed cache, but reasonably is still O(number of labels) instead of O(1).
>  If you just say what the abstract says and nothing more, that allows
> implementations to be "more efficient," as you suggest, without requiring
> implementations to be less efficient.   Granted, it's a SHOULD, but I think
> that still goes too far.   You should just say that NXDOMAIN means what you
> want it to mean, and leave it at that.
>

another choice :  Authority Server return NODATA/NXDOMAIN as nxdomain cut,
but no change on DNS cache.  Some impact on NSEC/NSEC3 records.

- no names under foo.example => NXDOMAIN  at  foo.example

- zone with bar.foo.example, where foo.example does not exist => NODATA
or  NOERROR + NULL Answer    at  foo.example

-- 

Best Regards
Pan Lanlan

---

From: Mark Andrews <[email-masked]>
Date: Mon, 14 Mar 2016 15:01:09 +1100

In message <[email-masked]>
, abby pan writes:
> Ted Lemon <[email-masked]>
> 
> >
> > domain as applying to all names under it.   This is certainly a valid
> > thing to do, and I can think of ways to do it reasonably efficiently
> > even wish a hashed cache, but reasonably is still O(number of labels)
> > instead of O(1).
> > implementations to be "more efficient," as you suggest, without
> > requiring implementations to be less efficient.   Granted, it's a
> > SHOULD, but I think that still goes too far.   You should just say
> > that NXDOMAIN means what you want it to mean, and leave it at that.
> >
>

If you want to signal NOERROR + bottom of zone you need a new rcode
and signaling that you support the new rcode.  The above imply is
just wrong as it changes what NXDOMAIN means.

> or  NOERROR + NULL Answer    at  foo.example

Well a explict NODATA rcode would be useful and again signaling of support
for the new rcode is needed.

NXDOMAIN at a empty non terminal only came about as the result of
bad wording in RFC 2535.  "no names" should have been "no names
with data" (the difference is crucial in determining which rcode
is returned).  Only RFC 2535 nameservers are allowed to return
NXDOMAIN for a empty non-terminal and they should few and far between
these days.  Every other NXDOMAIN at a empty non terminal is the
result of miss-interpreting STD 13 or a operational error e.g.
missing delegation in a parent zone.

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

---

From: Paul Vixie <[email-masked]>
Date: Sun, 13 Mar 2016 21:22:09 -0700

> missing delegation in a parent zone.

i'd still like to see a standards track clarification. djb wrote a name 
server which responds with nxdomain for empty nonterminals, and upon 
re-reading the scriptures, i found that his interpretation wasn't 
completely unreasonable.

-- 
P Vixie

---

From: Mark Andrews <[email-masked]>
Date: Mon, 14 Mar 2016 15:38:01 +1100

> re-reading the scriptures, i found that his interpretation wasn't 

Then please explain how RFC 1034 Section 4.3.2. Algorithm can return
a Name Error for a empty non-terminal.  I don't see it unless there
is a missing delegation and that is a configuration error.  I have
zero problems with a cache returning Name Error if there is a
configuration error.

---

From: Paul Vixie <[email-masked]>
Date: Sun, 13 Mar 2016 21:52:40 -0700

Mark Andrews wrote:
> ... please explain how RFC 1034 Section 4.3.2. Algorithm can return

i see no ambiguity in RFC 1034 4.3.2.

however, the wording of RFC 1035 4.1.1 could be clearer:

>                 3               Name Error - Meaningful only for
>                                 responses from an authoritative name
>                                 server, this code signifies that the
>                                 domain name referenced in the query does
>                                 not exist.

of course, name error is also meaningful for responses from a caching 
recursive name server, so perhaps this text should be treated suspiciously.

see also this text from [ibid] 6.2.2:

> All of these data structures can be implemented an identical tree
> structure format, with different data chained off the nodes in different
> parts: in the catalog the data is pointers to zones, while in the zone
> and cache data structures, the data will be RRs.  In designing the tree
> framework the designer should recognize that query processing will need
> to traverse the tree using case-insensitive label comparisons; and that
> in real data, a few nodes have a very high branching factor (100-1000 or
> more), but the vast majority have a very low branching factor (0-1).

100-1000, eh?

-- 
P Vixie

---

From: Mark Andrews <[email-masked]>
Date: Mon, 14 Mar 2016 16:42:58 +1100

> however, the wording of RFC 1035 4.1.1 could be clearer:

Lots of STD 13 could be clearer. :-)
 
> >                                 domain name referenced in the query does

Which defines the code point and says it applies to non-existing
names.  RFC 1035 also references RFC 1034 thusly:

    This RFC describes the details of the domain system and protocol, and
    assumes that the reader is familiar with the concepts discussed in a
    companion RFC, "Domain Names - Concepts and Facilities" [RFC-1034].

So given that, how can you get to Name Error for a empty non terminal
from this description of the code point?

> > more), but the vast majority have a very low branching factor (0-1).

100-100000000 would be a better description.

---

From: abby pan <[email-masked]>
Date: Mon, 14 Mar 2016 08:17:26 +0000

> missing delegation in a parent zone.

the point is : change NXDOMAIN means, indicated with subtree info, yes or
no ?

if dns cache deal with the nxdomain cut,  that is yes.

we can change the NXDOMAIN means on authority server response, not create
new rcode ( same benefit at draft-ietf-dnsop-qname-minimisation , reduce
flush domaintree/hashtable on dns cache )
-- 

Best Regards
Pan Lanlan

---

From: Mark Andrews <[email-masked]>
Date: Mon, 14 Mar 2016 23:10:36 +1100

In message <[email-masked]>
, abby pan writes:
>
> Mark Andrews <[email-masked]>
>
> >

No, we can't change what NXDOMAIN means.  We can add a new rcode
that say a name is at bottom of zone and is not a delegation.

> flush domaintree/hashtable on dns cache )

NXDOMAIN at foo.example => no names under foo.example
no names under foo.example =/> NXDOMAIN at foo.example

Mark

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Mon, 14 Mar 2016 13:36:20 +0100

On Mon, Mar 14, 2016 at 02:55:50AM +0000,
 Ted Lemon <[email-masked]> wrote 
 a message of 14 lines which said:

> The reason the WG is getting pushback from me on this is precisely
> that the draft gives implementation advice

No, it does not.

---

From: Ted Lemon <[email-masked]>
Date: Mon, 14 Mar 2016 16:31:47 +0000

> No, it does not.

Yes, it does.   You are not calling it implementation advice, but that's what it is.   A normative requirement to do a particular optimization is nothing other than implementation advice.

---

From: 神明達哉 <[email-masked]>
Date: Mon, 14 Mar 2016 11:59:19 -0700

At Mon, 14 Mar 2016 16:31:47 +0000,
Ted Lemon <[email-masked]> wrote:

> > No, it does not.
>
> Yes, it does.   You are not calling it implementation advice, but
> that's what it is.   A normative requirement to do a particular
> optimization is nothing other than implementation advice.

I guess one key point to discuss is how strongly we recommend the
nxdomain-cut behavior.  Specific wording matters include whether to
use RFC2119 keywords seems to be minor technicality we can easily
address if and once we can reach consensus on the key part.

On giving an almost fresh read of draft-ietf-dnsop-nxdomain-cut-01, my
impression about the key question is that the draft recommends the
behavior quite strongly.  While it allows some implementation to
ignore the recommendation, the overall tone of the draft sounds like
the recommended nxdomain-cut behavior is "the correct" one (from
Section 3) and implementations should basically follow unless there's
very strong reason not to do so.

My interpretation on the complaint of Ted is that he considers
nxdomain-cut to be a completely optional optimization but the overall
wording of the draft is too strong for such purely optional
recommendation.

If this observation is correct, I think what we should first agree on
is the real intent of the draft:
A. nxdomain-cut is "the correct behavior" and implementations SHOULD
   generally support the behavior.  Other behaviors are allowed but
   should be considered minor exceptions.
B. nxdomain-cut is a completely optional optimization.  It's totally
   up to an individual implementation whether to support it.

If the intent is B, I tend to agree with Ted; the current draft
doesn't convey that intent appropriately, so the wording should be
weakened a lot more.

If the intent is A, then we should first agree on whether that intent
is reasonable.  Right now I personally don't have a strong opinion on
this one, though.

p.s. in my understanding Unbound adopts hash-based data structure for
cached RRsets.  If it still supports nxdomain-cut as described in
Section 8, an argument against the proposal by referring to that type
of implementation might sound less convincing.

--
JINMEI, Tatuya

---

From: Ted Lemon <[email-masked]>
Date: Mon, 14 Mar 2016 20:12:24 +0000

I think that's a good summary, Jinmei-san--thank you!

I have no idea how you would implement this efficiently with a hashed cache: either you search every parent domain of a particular name before answering to see if there's an NXDOMAIN higher in the hierarchy, or else when you get an NXDOMAIN for a name you traverse the entire hash table looking for subdomains.   Neither of these can be done efficiently.

---

From: Robert Edmonds <[email-masked]>
Date: Mon, 14 Mar 2016 18:39:55 -0400

> of implementation might sound less convincing.

My understanding is that Unbound employs at least two hash-based data
structures, one for whole messages (msg-cache-* parameters) and one for
individual RRsets (rrset-cache-* parameters).

It's also my understanding that Unbound already implements the
resimprove-00 §3 behavior when configured with "harden-below-nxdomain:
yes", but it defaults to off (only?) because "it is not an RFC".

-- 
Robert Edmonds

---

From: Robert Edmonds <[email-masked]>
Date: Mon, 14 Mar 2016 18:59:24 -0400

> yes", but it defaults to off (only?) because "it is not an RFC".

Actually, I was misremembering this. Unbound's harden-below-nxdomain
behavior is much more conservative than resimprove, since it only
considers NXDOMAINs that are DNSSEC-secure. But it still does use an
"upwards" algorithm (successively strip labels off the QNAME) in a
hash-based cache to find an applicable NXDOMAIN.

-- 
Robert Edmonds

---

From: "John Levine" <[email-masked]>
Date: 15 Mar 2016 00:07:08 -0000

>I have no idea how you would implement this efficiently with a hashed cache: either you search every parent domain of
>a particular name before answering to see if there's an NXDOMAIN higher in the hierarchy, or else when you get an
>NXDOMAIN for a name you traverse the entire hash table looking for subdomains.   Neither of these can be done
>efficiently.

How deep do you expect the name tree to get?  I rarely see anything
more than four levels deep, and three times through the loop isn't
a whole lot.

R's,
John

---

From: Shumon Huque <[email-masked]>
Date: Mon, 14 Mar 2016 20:29:19 -0400

> hash-based cache to find an applicable NXDOMAIN.

Yup, the DNSSEC-only behavior of Unbound is mentioned in the current
draft:

  The Unbound resolver has a configuration
   parameter called "harden-below-nxdomain" [2], which if set to "yes"
   turns on NXDOMAIN cut behavior ("only DNSSEC-secure nxdomains are
   used", see Section 7).  The PowerDNS recursor has optional partial
   support for NXDOMAIN cut, for the root domain only, with its "root-
   nx-trust" setting, described as [3] "If set, an NXDOMAIN from the
   root-servers will serve as a blanket NXDOMAIN for the entire TLD the
   query belonged to.  The effect of this is far fewer queries to the
   root-servers.".

Whether or not to limit this to secure responses is one of the open
questions. A few people have expressed fears that resimprove will make
it easier for attackers faking (unsigned) NXDOMAIN responses to prune
out large parts of a victim's cache.

-- 
Shumon Huque

---

From: Robert Edmonds <[email-masked]>
Date: Mon, 14 Mar 2016 20:31:45 -0400

> to the implementation. Section 5 now discuss implementation.

Hi,

I agree with Ted Lemon's comments in this thread.

Could the rule be relaxed so that the process of considering whether a
cached NXDOMAIN in a parent zone is applicable to the name being looked
up can be delayed until immediately prior to transmitting a query to an
authoritative server? I.e., what would have traditionally been a cache
miss can now be transformed into a cache hit at the last instant. That
would move the O(number of labels) lookup from a hot path to a cold
path, and there would be no need to argue about exactly how many
nanoseconds the O(number of labels) lookup costs, because you were going
to wait at least a few milliseconds on the network anyway.

If you do it that way, however, a newly cached NXDOMAIN doesn't affect
previous positively cached responses at all. This idea was brought up
earlier and dismissed:

Stephane Bortzmeyer wrote:
> On Thu, Nov 12, 2015 at 06:13:04PM +0000,
> Wessels, Duane <[email-masked]> wrote 
> a message of 57 lines which said:
> 
> > Perhaps a recursive might be designed to negatively cache an entire
> > zone (including TLD) but continue answering positively cached
> > answers in the zone until they expire normally.
> 
> Clever algorithm but I'm afraid it will make debugging more
> difficult. Such a behaviour will be highly non-intuitive for the
> user. (One of the motivations for NXDOMAIN cut is to make DNS behave
> according to its data model, which is a tree.)

(https://mailarchive.ietf.org/arch/msg/dnsop/JchUb-CvQVodkXJmxs1SR_0aIf8)

But I'm not sure it should be dismissed so easily. The data model is a
tree, yes, but caching up to the maximum TTL value allowed is permitted
and widely expected, to the point that flushing the cache and trying
again is often one of the first debugging steps performed. And debugging
the DNS is already highly unintuitive and can already produce answers
of... constrasting levels of coherence... especially when load-balancing
is used for recursive service.

-- 
Robert Edmonds

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 01:32:07 +0000

> hash-based cache to find an applicable NXDOMAIN.

So it does this for every query?

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 01:34:37 +0000

> more than four levels deep, and three times through the loop isn't

Er, if on average you have to do three hash lookups instead of one, and hash lookups are the main expense to answering a query, then that would be 66% performance reduction on average on _every_ query.   That's pretty significant.   Am I missing something?   Why does this sound like "not a whole lot" to you?

---

From: "John R Levine" <[email-masked]>
Date: 14 Mar 2016 21:47:29 -0400

> Er, if on average you have to do three hash lookups instead of one, and 
> hash lookups are the main expense to answering a query, then that would 
> be 66% performance reduction on average on _every_ query.  That's pretty 
> significant.  Am I missing something?  Why does this sound like "not a 
> whole lot" to you?

Because DNS caches aren't compute bound.

Regards,
John Levine, [email-masked], Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail.

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 01:59:35 +0000

> Because DNS caches aren't compute bound.

And this in turn is why CPU utilization on large DNS caches tends to be close to zero, I suppose...

---

From: Paul Vixie <[email-masked]>
Date: Mon, 14 Mar 2016 19:59:36 -0700

Ted Lemon wrote:
> Er, if on average you have to do three hash lookups instead of one,
> and hash lookups are the main expense to answering a query, then that
> would be 66% performance reduction on average on _every_ query. That's
> pretty significant. Am I missing something? Why does this sound like
> "not a whole lot" to you?

i think if flattened hashing is an inefficient way to implement a dns
cache, then it should and will fall out of favour. in 2002 or so, for a
non-open-source project, we (vernon schryver and myself) implemented a
dns cache as a recursive hash table in the general style of bind4/bind8,
but with strong module boundaries, and arrays for sparse child-sets that
morphed into variable sized hash tables when density increased. this is
where resimprove-00's nxdomain treatment was first implemented, and it
worked well, and it the whole thing was extremely fast, as well as 
memory efficient.

so whenever i hear words like "that'll be slow for flat-hash dns caches" 
it reminds me of the joke that begins "doctor, it hurts when i do $this" 
and ends with "well, then don't do $this".

-- 
P Vixie

---

From: Robert Edmonds <[email-masked]>
Date: Mon, 14 Mar 2016 23:25:42 -0400

Paul Vixie wrote:
> worked well, and it the whole thing was extremely fast, as well as memory
> efficient.
> 
> so whenever i hear words like "that'll be slow for flat-hash dns caches" it
> reminds me of the joke that begins "doctor, it hurts when i do $this" and
> ends with "well, then don't do $this".

OTOH, modern non-cryptographic hash functions (e.g., xxHash, CityHash,
etc.) are extremely fast. If the cost of performing a few extra hashes
and extra hash table lookups add significant expense to answering a
query, then the rest of the system has been impressively well-optimized.

-- 
Robert Edmonds

---

From: "W.C.A. Wijngaards" <[email-masked]>
Date: Tue, 15 Mar 2016 12:15:30 +0100

Hi,

> hash-based cache to find an applicable NXDOMAIN.

The dnssec choice was made for security, but also in the hope that newer
implementations that support dnssec also have correct NXDOMAIN
semantics.  And thus the nxdomain cut can be safely applied to them.
(This hope has proven to be wrong, i.e. Cloudflare, but I believe fixed
now).

Unbound implements a label-strip search through the hash table, but only
on a cache-miss.  This means existing positive information will stay in
cache until TTL.  It also mitigates performance issues.  The TTL-view is
similar to having multiple resolvers that feed off of another in the
face of this zone change.

The nxdomain feature combines well with the new qname minimisation
feature, because the qname minimisation feature tends to pull in the
higher NXDOMAIN cut for future responses.

The current implementation does nxdomain cuts everywhere, if enabled
(not just high up in the tree).  If RFC, default sounds plausible, eg.
with qname minimisation that needs the same NXDOMAIN-correctness
property for authority servers.

Best regards, Wouter

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 11:39:03 +0000

> and ends with "well, then don't do $this".

This sounds like a really good rejoinder until you realize that we are talking about an optimization that is likely to produce very little actual benefit in practice other than in the presence of certain kinds of PRSD attacks.   So the current draft makes an algorithm which apparently works well for several implementations work less well in order to get a benefit the magnitude of which is unclear, but likely small.

As a matter of principle, of course, what you are saying is true.   However, remember that what we are debating here is not whether to clarify the rules for handling NXDOMAINs, but rather whether to add normative language strongly urging implementations to do this optimization.   We all, I think, agree that the clarification is good.   By your argument, we should not add the normative language--we should just clarify the spec, and then see what happens.   If we see widespread implementation of this optimization, then we can conclude that it was worth doing.   If nobody implements it, or only tree-structured caches implement it, then we can conclude that whatever benefit may have come from doing the optimization wasn't sufficient to justify widespread implementation.

More likely, though, what we will see if we make this clarification without adding normative language, is that implementors make intelligent use of the optimization, as Wouter suggests, based on what will work most efficiently with their implementation.   So once again I urge the working group to make this a clarification and not a normative requirement, so that smart implementors can do what makes the most sense in the context of their implementations.

---

From: "John R Levine" <[email-masked]>
Date: 15 Mar 2016 07:50:34 -0400

> ends with "well, then don't do $this".

Beyond that, there are some obvious tradeoffs.  Unless your DNS cache is 
100% compute bound, if a few extra local hashes avoid upstream queries, it 
is likely to be an overall performance win.

Regards,

---

From: "John Levine" <[email-masked]>
Date: 15 Mar 2016 12:52:08 -0000

>query, then the rest of the system has been impressively well-optimized.

Perhaps we could compare it to the cost of a DNSSEC validation.

R's,
John

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 12:48:48 +0000

> is likely to be an overall performance win.

John, have you ever heard of "livelock"?

I think you are thinking about this in terms of per-query performance, but caches that handle large amount of traffic do not measure performance per query: they measure performance at a particular query load.   This means that although any given query is never CPU bound, when figuring out how many DNS cache servers you are going to have to install, you still very definitely need to account for CPU utilization.   Unless you simply aren't seeing any significant query load, you figure out what your steady-state query load is, and you figure out what your maximum query load is, and you figure out from that how many servers you need to deploy.   If you triple the per-query CPU load, then you need to buy three times as many servers.

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 13:03:26 +0000

> Perhaps we could compare it to the cost of a DNSSEC validation.

Which is why DNSSEC validation is most effectively done by the resolver, not the intermediate cache, much as we might wish it to be otherwise (e.g. for cache poisoning protection).

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 14:25:06 +0100

On Fri, Mar 11, 2016 at 08:52:20PM +0000,
 Ted Lemon <[email-masked]> wrote 

> mentioned doesn't mean that it's not saying that!

For the record, I fully agree with the explanations of Shumon Huque
<https://mailarchive.ietf.org/arch/msg/dnsop/WaaprcPTpMnDEwheVin0Zz4Lg8Q>
and Paul Vixie
<https://mailarchive.ietf.org/arch/msg/dnsop/LAYTX-rBH5qqOjy_dIaCh1esjyw>
Whether you like it or not, domain names are a tree. A DNS server can
choose its data structures as it wishes but it will still have in some
cases to understand the tree semantics.

I suggest to add in section 1.1 "Terminology":

The domain name space is conceptually defined in terms of a tree
structure. The implementation of a DNS resolver/cache MAY use a tree
or other data structures. Sometimes, this document mentions tree
operations, because it is the way domain names are defined, but it
does not imply that the inner implementation of the server uses a
tree.

>  But this draft isn't really adressing an operational problem: your
>  motivation for doing this is to support DPRIVE,

Not at all and it is not mentioned anywhere. I even do not see the
relationship with the work of DPRIVE (encryption of the DNS). There is
some relationship with other work done at DNSOP (QNAME minimisation)
but the main motivation, as explained in the draft is a better
efficiency of the caches (see section 3).

If you want the whole truth, there is another motivation,
undocumented, an aestethic motivation: NXDOMAIN cut is more beautiful,
because it respects the tree structure of the DNS.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 14:28:38 +0100

On Mon, Mar 14, 2016 at 11:59:19AM -0700,
 神明達哉 <[email-masked]> wrote 

>    should be considered minor exceptions.

Agree. That's the whole point of the draft. Slide 3 at the Yokohama
meeting
<https://www.ietf.org/proceedings/94/slides/slides-94-dnsop-9.pdf>

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 13:34:07 +0000

> Agree. That's the whole point of the draft. Slide 3 at the Yokohama meeting

I believe that Jinmei-san was proposing one of two positions the working group could take, so you aren't agreeing with him--you are saying what your opinion is as to what the working group's position should be.   And the slide you've referenced as a supporting document is a slide from a presentation you wrote which does not say anything about making this a normative requirement!

I think that you should explain what the interoperability problem is that this proposed normative requirement addresses, and otherwise we should drop it and let implementors decide how best to treat this.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 14:36:58 +0100

On Mon, Mar 14, 2016 at 08:31:45PM -0400,
 Robert Edmonds <[email-masked]> wrote 
 a message of 59 lines which said:

> Could the rule be relaxed so that the process of considering whether
> a cached NXDOMAIN in a parent zone is applicable to the name being
> looked up can be delayed until immediately prior to transmitting a
> query to an authoritative server?

The current version of the draft allows this behavior, it was one of
the changes between -00 and -01. -00 was written in a way that could
have been interpreted as "delete data NOW".

> The data model is a tree, yes, but caching up to the maximum TTL
> value allowed is permitted

Yes.

> and widely expected,

I'm not sure about "widely expected". It seems to me it confuses many
people when QNAME=example elicits NXDOMAIN but a later
QNAME=foobar.example succeeds.

Anyway, keeping cached date as long as the TTL is positive, even if
they are under a NXDOMAIN cut, is allowed (that's the point of a
SHOULD, after all). May be adding at the end of section 5
"Implementation considerations":

Another reason why a resolver could find useful to send positive
responses located under a NXDOMAIN cut, is the case where the resolver
already has cached data (and the TTL is of course not expired) and
continues to serve it. [End of addition]

For the "cache efficiency" and "protection against random QNAME
attacks" motivations, it would change nothing (if the data is cached,
the resolver won't bother the upstream server). But I still find it
disturbing and contrary to the tree model of domain names.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 14:39:01 +0100

On Mon, Mar 14, 2016 at 08:12:24PM +0000,
 Ted Lemon <[email-masked]> wrote 
 a message of 7 lines which said:

> I have no idea how you would implement this efficiently with a
> hashed cache: either you search every parent domain of a particular
> name before answering to see if there's an NXDOMAIN higher in the
> hierarchy, or else when you get an NXDOMAIN for a name you traverse
> the entire hash table looking for subdomains.   Neither of these can
> be done efficiently.

Personal curiosity: how could you implement DNSSEC with a cache where
tree operations (such as finding the parent) are unbearably slow?

---

From: Tony Finch <[email-masked]>
Date: Tue, 15 Mar 2016 13:40:14 +0000

John Levine <[email-masked]> wrote:
>
> How deep do you expect the name tree to get?

ip6.arpa :-)

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Trafalgar: Westerly or southwesterly 4 or 5, increasing 6 at times, becoming
variable 3 or 4 later. Moderate or rough. Fair. Moderate or good.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 14:45:49 +0100

On Tue, Mar 15, 2016 at 11:39:03AM +0000,
 Ted Lemon <[email-masked]> wrote 
 a message of 14 lines which said:

> This sounds like a really good rejoinder until you realize that we
> are talking about an optimization that is likely to produce very
> little actual benefit in practice

Side question: why did you not raise the point during the discussions
of draft-fujiwara-dnsop-nsec-aggressiveuse or
draft-wkumari-dnsop-cheese-shop? If this optimisation is useless, we
could drop these drafts as well.

> other than in the presence of certain kinds of PRSD attacks.

By the way, I assume "PRSD attacks" are "random QNAME attacks" but I
don't find a lot of occurrences for this term.

And, no, the problem is not just the random QNAME attacks but, also,
like for the two drafts mentioned above, a better efficiency of the
global DNS (the case of the junk traffic at the root being of course
the most obvious: I assume this is why PowerDNS has a "NXDOMAIN cut"
option just for the root).

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 14:52:37 +0100

On Sun, Mar 13, 2016 at 06:29:37PM +0000,
 Ted Lemon <[email-masked]> wrote 
 a message of 27 lines which said:

> associated with implementing it.

Next time, all the caching provisions of RFC 1034 and 1035 will be
called "speed hacks". After all, the DNS would work as well without
caches.

"NXDOMAIN cut" is not purely an internal optimization because it
changes the observable behavior of a resolver. It therefore has an
effect on other servers. It reveals brokenness in other servers (the
one who reply NXDOMAIN for an ENT). It is not just a matter for the
implementer.

---

From: Tony Finch <[email-masked]>
Date: Tue, 15 Mar 2016 14:03:24 +0000

Ted Lemon <[email-masked]> wrote:
>
> I have no idea how you would implement this efficiently with a hashed
> cache:

There's an easy way which I think is a clear optimization:

When there is a cache miss, before recursing, search the cache for a
parent NXDOMAIN entry. If you find one, add an NXDOMAIN cache entry for
the QNAME, and return that, otherwise recurse as usual.

This uses the same memory for the cache as it would without nxdomain-cut,
and requires the same quantity of hash lookups (one) when there is a cache
hit.

Note that when recursing you have to search up the cache anyway, to find
the authoritative servers that can answer this query. So you can combine
the NXDOMAIN search with the NS search, so it doesn't cost any more CPU.

When you get an NXDOMAIN response at a parent of existing cache entries,
don't clean the cache eagerly, allow normal TTL cleaning to deal with
them lazily.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Dover, Wight, Portland, Plymouth: East or northeast 4 or 5, increasing 6 at
times. Slight or moderate. Mainly fair. Moderate or good, occasionally poor.

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 14:12:20 +0000

> the QNAME, and return that, otherwise recurse as usual.

I don't see a problem with this, but I also don't see any argument for making a normative requirement to implement it.   Do you?

---

From: Tony Finch <[email-masked]>
Date: Tue, 15 Mar 2016 14:15:43 +0000

Ted Lemon <[email-masked]> wrote:

> I don't see a problem with this, but I also don't see any argument for
> making a normative requirement to implement it.  Do you?

It neatly avoids a lot of wasteful authoritative queries.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Forties: Northeast 3 or 4. Slight. Fog banks. Moderate or poor, occasionally
very poor.

---

From: Shumon Huque <[email-masked]>
Date: Tue, 15 Mar 2016 10:16:52 -0400

> one who reply NXDOMAIN for an ENT). It is not just a matter for the

More generally, it also reduces demands on authoritative servers by
not sending them a set of unnecessary queries.

I have not viewed this as a 'speed hack', or in fact any hack, but as a
way to make the entire DNS ecosystem more efficient by correctly
interpreting the NXDOMAIN signal. To regurgitate part of my earlier
message: "why should resolvers make unnecessary outbound queries
for names that don't exist, and why should authoritative servers receive
those queries?"

As an implementation note, doing this only on a cache miss sounds to me
like a reasonable choice. Given the current thread, we should probably
revise the draft to remove text that 'sounds' like implementation advice.
I also favor "SHOULD", but let's see where WG deliberations lead us.

-- 
Shumon Huque

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 14:36:48 +0000

> It neatly avoids a lot of wasteful authoritative queries.

This is an interesting statement.   Do you have any numbers on this, or is this based on intuition?

In order to measure this, you would need to measure it on a fairly active cache, not on the authoritative server.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 15:53:39 +0100

On Tue, Mar 15, 2016 at 10:16:52AM -0400,
 Shumon Huque <[email-masked]> wrote 
 a message of 93 lines which said:

> As an implementation note, doing this only on a cache miss sounds to
> me like a reasonable choice.

Reasonable for the "traffic intensity and protection against random
QNAME attacks", yes. But still inelegant (it violates the tree model
of domain names).

> Given the current thread, we should probably revise the draft to
> remove text that 'sounds' like implementation advice.

I'm not convinced if we have just one person, who sees in the draft
things that nobody else sees.

---

From: Shumon Huque <[email-masked]>
Date: Tue, 15 Mar 2016 10:54:56 -0400

> cache, not on the authoritative server.
I haven't seen any measurement studies. But at a recent DNS-OARC
meeting, Bert Hubert mentioned that PowerDNS were driven
to implement this based on a real operational problem: too many
NXDOMAIN eliciting queries from one of their large resolvers to the
F.ROOT server resulting in them being response rate limited.

-- 
Shumon Huque

---

From: "John Levine" <[email-masked]>
Date: 15 Mar 2016 15:03:28 -0000

>QNAME attacks", yes. But still inelegant (it violates the tree model

I'm confused.  If the query finds an entry in the cache, why wouldn't
it use it?

R's,
John

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 16:11:58 +0100

On Tue, Mar 15, 2016 at 03:03:28PM -0000,
 John Levine <[email-masked]> wrote 
 a message of 12 lines which said:

> If the query finds an entry in the cache, why wouldn't it use it?

00:00:00 Cache receives a reply with a AAAA record for foobar.example, with a TTL of 86400

01:00:00 Cache receives a reply NXDOMAIN when asking QNAME=example

02:00:00 Cache receives a AAAA request for foobar.example

With today's software, the cache will reply (the TTL is not over). I
find that a violation of the tree model of the DNS. I find more
elegant if cache replies NXDOMAIN.

Note that both behaviour will have the same result for the upstream
servers: in both cases, the cache won't send a query to them.

---

From: Tony Finch <[email-masked]>
Date: Tue, 15 Mar 2016 15:18:45 +0000

> is this based on intuition?

Based on discussions of attack traffic and junk queries.

I've had a look at the contents of one of my caches and sadly it isn't
very easy to analyze, e.g. there's some search-path-related junk under
com.ac.uk and net.ac.uk but no negative entries for com.ac.uk or net.ac.uk
themselves (because, no qname minimization).

One analysis I can do fairly easy is count the number of cache entries in
nonexistent TLDs; this cache has 4617 out of 1945116 total names.

We have a relatively well policed network, and I don't get to see the
worst traffic from the student accommodation or the mail servers, so I'm
smugly unsurprised my numbers are relatively unconvincing :-)

sed -E '/^([0-9a-z_.-]+)[.][ 	].*/!d;
	s//\1/;
	s/^.*[.]//' named_dump.db |
perl -e 'my %root;
	for (qw('"$(
			dig axfr . |
			sed -E '/^([a-z0-9-]+)[.][ 	].*/!d;
				s//\1/' |
			uniq)"')) {
		$root{$_} = 1
	}
	my ($y,$n);
	while (<>) {
		chomp;
		if ($root{$_}) { ++$y }
		else { ++$n }
	}
	END {
		print "y $y\nn $n\n"
	}'

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Shannon, Rockall: Southeast 4 or 5, increasing 6 at times. Moderate or rough.
Fair. Good.

---

From: Tony Finch <[email-masked]>
Date: Tue, 15 Mar 2016 15:27:50 +0000

> QNAME attacks", yes. But still inelegant (it violates the tree model

However it is (sort of) consistent with existing cache behaviour in other
similar circumstances, e.g. when there is a delegation change or a zone
cut is removed or introduced, caches do not eagerly invalidate RRsets
under the change.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Southeast Iceland: Southerly or southwesterly 4 or 5, increasing 6 at times in
northwest. Moderate or rough. Occasional rain in northwest. Good, occasionally
poor in northwest.

---

From: "John R Levine" <[email-masked]>
Date: 15 Mar 2016 11:31:15 -0400

> elegant if cache replies NXDOMAIN.

Seems to me this is a theological argument about the meaning of TTL. I 
understand the TTL to be the server telling the client "here is the 
answer, and you can believe it for TTL seconds."

If your DNS data changes hourly, why would you use a TTL of a day?

Or if you want the more consistent behavior, when a cache gets an 
NXDOMAIN, it can at that time flush any entries with names under the it. 
I suppose that means that we need a cache where you can look down the tree 
as well as up.  Ugh.

R's,
John

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 15 Mar 2016 16:34:56 +0100

On Tue, Mar 15, 2016 at 11:31:15AM -0400,
 John R Levine <[email-masked]> wrote 
 a message of 21 lines which said:

> it can at that time flush any entries with names under the it. I
> suppose that means that we need a cache where you can look down the
> tree as well as up.

Which was exactly what was proposed in draft-vixie-dnsext-resimprove:
"When an iterative caching DNS resolver stores an NXDOMAIN in its
cache, all names and RRsets at or below that node should be deleted
since they will have become unreachable."

---

From: "John R Levine" <[email-masked]>
Date: 15 Mar 2016 11:59:35 -0400

> since they will have become unreachable."

There's nothing wrong with doing that.  I just don't see why it's any 
more correct than believing the TTL that the server provided.

Regards,

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 09:03:02 -0700

Ted Lemon wrote:
> little actual benefit in practice other than in the presence of
> certain kinds of PRSD attacks.   So the current draft makes an
> algorithm which apparently works well for several implementations
> work less well in order to get a benefit the magnitude of which is
> unclear, but likely small.

i figured that if the perceived cost of implementing it (e.g., multiple 
hash table lookups using label stripping) it is high, and the perceived 
benefit of having implemented it (e.g., resistance to certain PRSD 
attacks) then it won't be implemented.

a non-implementing recursive will likely not care that nxdomain applies 
to both the qname and all possible subdomains, but i see no harm in 
clarifying the specification in that way, nor in pointing out the 
possible optimization, which each implementer will have to evaluate.

> As a matter of principle, of course, what you are saying is true.
> However, remember that what we are debating here is not whether to
> clarify the rules for handling NXDOMAINs, but rather whether to add
> normative language strongly urging implementations to do this
> optimization.  ...

i have no desire to defend that normative language. but my reason for 
lacking that desire has nothing to do with cache data structures. 
rather, it's my view that normative language should be as rare as it can be.

> ...   We all, I think, agree that the clarification is good.   By
> your argument, we should not add the normative language--we should
> just clarify the spec, and then see what happens.

i think the document should point out the possibility of the 
optimization, and not just leave this as an implication for the reader 
to discover. but that possibility need not be worded prescriptively nor 
as a recommendation. rather, a normal cost:benefit analysis should be 
assumed, and the benefit of this optimization stated clearly.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 16:45:26 +0000

> F.ROOT server resulting in them being response rate limited.

And the clue-by-four hits me in the face.  Ouch.   Yes, right, we are not doing an extra cache lookup to look for the parent NXDOMAIN because we are already doing a cache search on that name to figure out who's authoritative for it.   So indeed, as you and John and possibly Paul said, the performance hit for doing that part of the search isn't an issue.

So then the main issue that I have is the normative requirement to not answer out of the cache when I have a valid cache entry for a name that happens to have a cached NXDOMAIN above it in the hierarchy.   If I don't have to do that, then there's no performance issue; if I do have to do that, then my objection still applies.   There's no benefit to the root servers in this normative requirement, because these queries are being answered out of the cache.

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 09:51:51 -0700

Ted Lemon wrote:
> This is an interesting statement. Do you have any numbers on this,
> oris this based on intuition?
>
> In order to measure this, you would need to measure it on a fairly
> active cache, not on the authoritative server.

my intuition is that treating nxdomain as a cache traversal ending 
condition will have very limited impact on authority servers unless 
those caches are also doing qname minimization.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 16:53:35 +0000

Oh, here's some text that our engineering team proposes:

> A plain reading of the first paragraph of section 2, which section 5 supports, is that *all* subsequent queries for information beneath the NXDOMAIN name point SHOULD return NXDOMAIN.  In particular, this includes queries that would otherwise have been cache hits.  It is this last bit that I object to.

OLD:
   When an iterative caching DNS resolver receives a response NXDOMAIN,
   it SHOULD store it in its cache and all names and RRsets at or below
   that node SHOULD then be considered to be unreachable.  Subsequent
   queries for such names SHOULD elicit an NXDOMAIN response."

NEW:

   When an iterative caching DNS resolver receives a response NXDOMAIN, it SHOULD store it in its cache.  For the lifetime of the NXDOMAIN negative cache entry, the resolver SHOULD NOT make queries to the authoritative servers for cache misses involving names at or beneath the owner name of the NXDOMAIN negative cache entry, and SHOULD return an NXDOMAIN.  The resolver MAY return NXDOMAIN for any query at or beneath the NXDOMAIN owner name, i.e. already cached entries beneath the NXDOMAIN owner name MAY become unreachable."

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 09:59:26 -0700

> more correct than believing the TTL that the server provided.

an authoritative nxdomain proves that there is nothing below that qname. 
this obviates all prior positive responses for that qname -- you 
wouldn't say that we should continue to send positive responses for 
other data perhaps based on qtype as a differentiator, because the 
definition of nxdomain is qtype-independent, i.e., it applies to a name.

for the same reason and in the same way, nxdomain applies to all 
subdomains. it is not just talking about the qname.

-- 
P Vixie

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 10:06:22 -0700

>> A plain reading of the first paragraph of section 2, which section
>> 5supports, is that *all* subsequent queries for information beneath the
>> NXDOMAIN name point SHOULD return NXDOMAIN. In particular, this includes
>> queries that would otherwise have been cache hits. It is this last bit
>> that I object to.

well, it's deliberate, so the objection is live.

you have to do the "rm -rf $qname" when you receive the nxdomain. once 
that nxdomain expires, you're free to make new queries for subdomains of 
the now-expired nxdomain. but having the nxdomain status of subdomains 
change without authority action would violate the data model. if sub.dom 
starts generating cached nxdomains because an nxdomain was received for 
dom, then sub.dom should not be able to generate non-subdomains without 
some newer result from the authority.

> it SHOULD store it in its cache. For the lifetime of the NXDOMAIN
> negative cache entry, the resolver SHOULD NOT make queries to the
> authoritative servers for cache misses involving names at or beneath the
> owner name of the NXDOMAIN negative cache entry, and SHOULD return an
> NXDOMAIN. The resolver MAY return NXDOMAIN for any query at or beneath
> the NXDOMAIN owner name, i.e. already cached entries beneath the
> NXDOMAIN owner name MAY become unreachable."

see above.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 17:23:55 +0000

> you have to do the "rm -rf $qname" when you receive the nxdomain.

The draft says you have to do this, yes.   That's what I'm objecting to.   Is there some reason why this is required for interoperability?

---

From: 神明達哉 <[email-masked]>
Date: Tue, 15 Mar 2016 11:58:53 -0700

At Tue, 15 Mar 2016 13:34:07 +0000,
Ted Lemon <[email-masked]> wrote:

> I believe that Jinmei-san was proposing one of two positions the
> working group could take, so you aren't agreeing with him

Correct (perhaps I wasn't clear enough in my message).

Now that I'm more certain that the intent of the draft is above "A",
I'd suggest:

- make it even clearer in the draft
- explain why this can't just be up to the implementor's choice (I know
  it's discussed in the thread, but I don't think it's super clear in
  the current text of the draft).

We can then discuss whether that's the wg consensus.  I personally
don't have a strong opinion, but I don't think that part of discussion
is over yet.

--
JINMEI, Tatuya

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 12:32:36 -0700

Ted Lemon wrote:
> The draft says you have to do this, yes. That's what I'm objecting
> to.Is there some reason why this is required for interoperability?

no. it's not an interoperability matter.

however, how you'd go about justifying the removal of all rrsets at some 
name when you learn that this name does not exist, without also removing 
all rrsets of all subdomains, will be interesting.

if i had rrsets cached at a name, and then i heard an nxdomain for that 
name, and then that nxdomain expired, i would not "feel alright about" 
answering with the old rrsets. why would subdomains be different?

noting as before: all of this is implied by the base dns specification, 
so this really is a clarification as to impact, not a protocol change.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Tue, 15 Mar 2016 19:51:40 +0000

> no. it's not an interoperability matter.

If it's not an interoperability matter, then there shouldn't really be any normative language.

> answering with the old rrsets. why would subdomains be different?

This is all certainly true as far as it goes.   However, if every NXDOMAIN requires a full cache traversal, as it will for any hashed cache with the restriction you've proposed, then NXDOMAIN suddenly becomes  a _really_ powerful DoS attack.   The best part is that there don't even have to be any entries in the cache to prune: every time you get an NXDOMAIN you're going to have to traverse the whole hash.   So all I have to do to bring a server to its knees is send it a bunch of queries for names in .COM that don't exist.   This is _seriously_ not a good idea.

It is worth noting that there's a generally accepted principle, which has been tossed in my face one or two times on this mailing list, that the DNS is not required to be consistent.   A zone's contents for any serial number are expected to be the same, but caches don't cache zones--they cache answers.   At the level of answers, as opposed to zones, consistency is always on a best-effort basis.   Arguing that not pruning the tree when you get an NXDOMAIN is inelegant isn't sufficient to justify the proposed normative language, true though it may be.

---

From: Mark Andrews <[email-masked]>
Date: Wed, 16 Mar 2016 09:59:43 +1100

> definition of nxdomain is qtype-independent, i.e., it applies to a name.

If proves that from the instance of the zone as served by that
server at that time.  It says zero about latest zone as that cache
has no way to learn if the answer is from the latest zone.

Removing  cached records assumes the NXDOMAIN response is from the
latest zone.  Now that may well be a reasonable assumption to make
but we need to acknowledge that it is a assumption.

> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 16:27:56 -0700

this is getting pretty good. anyone who stopped reading before now, may 
want to delve back in at this point.

Ted Lemon wrote:
> If it's not an interoperability matter, then there shouldn't really
> beany normative language.

i think hop-by-hop interoperability (which is what ietf normally 
measures, since the bits on the wire have senders and receivers) is the 
wrong way to understand end-to-end utility and correctness in the dns.

an authority server operator experiencing a PRSD DDoS might wish to add 
a zone cut or even remove a name in order to manage their defense costs. 
when they hand out authoritative content to recursive servers, they will 
find that some recursive servers will honor the clarified subdomain 
semantics of nxdomain and others will not. this is not an 
interoperability problem, but it's a very real problem well deserving 
our attention here.

> This is all certainly true as far as it goes. However, if every
> NXDOMAIN requires a full cache traversal, as it will for any hashed
> cache with the restriction you've proposed, then NXDOMAIN suddenly
> becomes a _really_ powerful DoS attack.  ...

you're distracting me. i used to be a programmer and this is an 
interesting problem. as others have pointed out up-thread, you don't 
have to do the purge at nxdomain time; you can purge lazily when you are 
responding on an affected qname; or you can purge never and just send 
the nxdomain instead of the unreachable content, and let the unreachable 
content expire naturally (TTL or LRU or whatever.) or you can refactor 
your cache to be a hierarchy of hash tables rather than a flat hash table.

however, back to the topic at hand, the implementation costs are not 
germane to system correctness. if nominum CNS and/or nlnetlabs Unbound 
can't implement the clarified nxdomain semantics, then they just won't. 
your customers and your investors can decide what this means to them.

note that interposing a new zone cut should ideally also cause a purge, 
either real or effective. this is nowhere written down, but has the same 
reasoning: a new authority ought to be given a fresh chance to populate 
caches. this is related to, and similar to, but not the same as the 
ns-rrset reverification logic proposed in resimprove-00, and will cause 
very similar implementation problems for flat-hash caches.

> It is worth noting that there's a generally accepted principle,
> which has been tossed in my face one or two times on this mailing
> list, that the DNS is not required to be consistent.  ...

inconsistency is in that sense a known hazard, but not a benefit. we 
call the system "best efforts" because we know it won't be consistent 
but we want everyone involved to do their best anyway.

-- 
P Vixie

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 16:55:18 -0700

Mark Andrews wrote:
> In message<[email-masked]>, Paul Vixie writes:

if that assumption weren't also being made by all implementations of 
negative caching to date, and was thus not specific to the subdomain 
clarification for nxdomain treatment, i'd agree, we ought to mention it.

instead i'll say, perhaps it's time to revise RFC 2308 along these 
lines. i think a higher cost system than DNS which was willing to trade 
resources to get coherence, all answers would be SOA.SERIAL tagged.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Wed, 16 Mar 2016 00:23:00 +0000

> want to delve back in at this point.

I on the other hand am a little frustrated because a while back I thought we agreed, and now it appears that we don't.

> interoperability problem, but it's a very real problem well deserving

The obvious place to do a PRSD attack is on a subdomain that contains valid data, so that you can't NXDOMAIN the parent domain.   So adding a zone cut appears unlikely to help.   Do you know of a situation where it would?

> your cache to be a hierarchy of hash tables rather than a flat hash table.

You can't really purge lazily.   TTL or LRU are your best bets.   Purging lazily requires you to take the performance hit John and I were arguing about.   Sure, it can be done, but ouch.

> your customers and your investors can decide what this means to them.

This is the core of our disagreement, I think.   You appear now to be saying that system correctness demands that a cache purge subdomains of an NXDOMAIN.  That simply isn't true.   An answer whose TTL hasn't expired is a valid answer.   A caching server that responds to a query for a cached name with the data that was cached is operating correctly.   The product name is Vantio Cacheserve 7, by the way, and to quote a well-loved customer, it is faster than greased bat****.

> very similar implementation problems for flat-hash caches.

I agree that this will produce a more consistent view of the DNS, but these consistency changes will occur by happenstance, not reliably, so they don't really make the view through a cache significantly more correct.   And there are better ways to make bouillabaisse than to boil the ocean--this would be a very expensive way to get a not very big improvement in consistency.

> but we want everyone involved to do their best anyway.

It's true that inconsistency is not a benefit, but it's standard operating procedure, and we have to deal with it every day.   One reason we have to deal with it is that, quite annoyingly, DNS caches cache NXDOMAINs.   Ping a nonexistent host, add its name to the authoritative server, and ping it again, and you will get a "host unknown" error both times, because the NXDOMAIN from the first ping attempt was cached.   This is bad behavior that we have codified into a standard because it improves performance.

So if you want to tell me that, for the sake of correctness, I have to go purge entries out of my hashed cache because I got an NXDOMAIN, then I will tell you for the sake of correctness that we should never cache NXDOMAINs, and we will both glare at each other sternly until one of us cracks a smile.   This is a silly argument.   If correctness were our first and only concern, DDoS attacks would be even easier than they are.

---

From: Tony Finch <[email-masked]>
Date: Wed, 16 Mar 2016 00:25:12 +0000

> all rrsets of all subdomains, will be interesting.

There's a risk of interesting attacks if you require rm -rf $qname
and the implementation blocks.

Tony.

---

From: Mark Andrews <[email-masked]>
Date: Wed, 16 Mar 2016 11:46:52 +1100

> resources to get coherence, all answers would be SOA.SERIAL tagged.

There really is no reason for authoritative servers which are not
using AXFR/IXFR for zone transfers to keep SOA serials in sync.
Even if you are using AXFR/IXFR you don't need all the authoritative
servers to keep the serials in sync, you just need to not cross the
streams.

Current examples of configurations that don't keep the serials in
sync include:

* Parallel inline signers feeding from the same unsigned source
  don't keep serials in sync as there is no need.

* Microsoft AD managed zones don't keep the serials in sync.

* There are a number of database to zone converters operated by
  TLDs that don't keep serials in sync.

Mark

---

From: George Michaelson <[email-masked]>
Date: Wed, 16 Mar 2016 10:50:55 +1000

I don't personally think cacheing NXDOMAIN is bad per se: the question
is with what negative cache time, and what consequence in the context
of a change in zone delegation structure in order to achieve DDoS
mitigation. When there is no DDoS you want the cache to do its job.
When there is, you want to be able to control the cache behaviour.
Hard, in an unconstrained hinted distributed system.

Since the TTL is set in the parent of the delegation, the defence is
both requiring of consideration by the parent, of the TTL to assert
over the zone, *and* ownership of a time machine to adjust this down,
when under attack.

I'm delighted to seek funds to do the time machine part. Somebody else
is going to have to get funded to do the cache coherence and flushing
protocol in- or out- of band.

How about if under load, a cache is permitted to convert NXDOMAIN ttl
to 1/nth of the apparent ttl, based on some understood algorithm which
relates to a load threshold?

ie, under load, the cache deliberately lowers retention on negative
cache state, so it can adapt to changes in that negativity?

-G

---

From: Ted Lemon <[email-masked]>
Date: Wed, 16 Mar 2016 01:05:03 +0000

>I don't personally think cacheing NXDOMAIN is bad per se:

Nor do I.   I was using that argument to contrast with Paul's position on NXDOMAIN subdomain purging.   If we care so much about consistency that we are willing to purge subdomains when we get an NXDOMAIN that contains them, then we care enough to not cache NXDOMAINs.   And of course, we do not care enough to not cache NXDOMAINs, nor should we, because not caching NXDOMAINs would probably melt the root and TLD servers at this point.

---

From: Paul Vixie <[email-masked]>
Date: Tue, 15 Mar 2016 18:07:35 -0700

Ted Lemon wrote:
> I on the other hand am a little frustrated because a while back I
> thought we agreed, and now it appears that we don't.

i wrongly remembered this as an optimization rather than a clarification.

> You can't really purge lazily. TTL or LRU are your best bets. Purging
> lazily requires you to take the performance hit John and I were
> arguingabout. Sure, it can be done, but ouch.

if the purge burden is one label-stripping cache management action per 
transmitted response, then the cost is small compared to the network i/o 
cost. even given your live-lock observation, this level of 
implementation detail is not something that dns as a system notices.

> This is the core of our disagreement, I think. You appear now to be
> saying that system correctness demands that a cache purge subdomains of
> an NXDOMAIN.  ...

no. it requires the effect of a purge, or "an effective purge". as long 
as what happens on the wire is the same as what would have happened in 
the event of an actual purge, then whether you actually purged or not 
makes no difference to dns at the system level. besides which, the 
nominum and nlnetlabs software teams are at the top echelon of the 
field, and i think they will be better than i at designing their code.

> ... That simply isn't true. An answer whose TTL hasn't expired is a
> valid answer. A caching server that responds to a query for a cached
> name with the data that was cached is operating correctly. ...

two days ago i might have agreed with you. but putting resimprove-00 
into the blender and making me drink it has made me obstreperous as 
follows: if an answer of <name,type=1,rrset> is in cache and you hear a 
question for <name,type=2> and forward it and you then hear nxdomain, 
then would you purge the <name,type=1,rrset> element when caching the 
nxdomain for <name>, or would you retain the old type=1 element, such 
that when the nxdomain expires, you could once again answer questions 
for <name,type=1> using the <name,type=1,rrset> you started out with?

if so, then we should talk about what best efforts means when applied to 
distributed cache coherency. if not, then we should talk about why you 
would treat previously cached <sub.name,type,rrset> values, since the 
meaning of the nxdomain in the context of <sub.name> is the same as the 
meaning of the nxdomain in the context of <name>. in other words, let's 
first agree on what exactly it is that we disagree about.

> It's true that inconsistency is not a benefit, but it's standard
> operating procedure, and we have to deal with it every day.

well, so is spam, and so are outages, but we do all we can reasonably do 
to minimize those activities. i'm not saying minimize at all imaginable 
costs, of course. engineering economics says minimize at all reasonable 
or in-budget costs. where a cost would require upgrading somebody else's 
network, we say that's not in-budget. where a cost would require adding 
logic to our own product or patching or upgrading technology in our own 
network, we can at least argue as to what the budget should be.

saying that the dns specification ought not specify visible on-the-wire 
behaviour by a recursive server after it receives an nxdomain, because 
that will make life harder for recursive servers whose caches are 
implemented as flat hash tables, when there are extant recursive servers 
who don't use flat hash tables and thus see no special burden, would 
strike me as at best "odd." since the specification as written already 
implies this behavious for subdomains, and is universally already 
implemented for domains, you are arguing from a position of weakness: 
you're asking for lassitude due to code you already deployed, and to 
accommodate you, we would have to loosen, not merely clarify, the 
specification.

> ... One reason we have to deal with it is that, quite annoyingly, DNS
> caches cache NXDOMAINs.   Ping a nonexistent host, add its name to
> the authoritative server, and ping it again, and you will get a
> "host unknown" error both times, because the NXDOMAIN from the first
> ping attempt was cached.   This is bad behavior that we have codified
> into a standard because it improves performance.

since it is identically true of positive cache elements that they can be 
annoying since they allow use of old data even after the authority has 
changed its zone contents, i must be missing the point, because i do not 
see this as "bad behavior". the system was designed to operate at scale, 
and it has. if you can design system with equal or better scale that has 
better coherency, i promise to review your work and comment on it. be 
aware that trying to remember who heard what so that you can send them 
change notifications asynchronously requires even more 
crypto-authentication work than dnssec, which is Hard To Deploy.

> So if you want to tell me that, for the sake of correctness, I have
> to go purge entries out of my hashed cache because I got an NXDOMAIN,
> then I will tell you for the sake of correctness that we should never
> cache NXDOMAINs, and we will both glare at each other sternly until
> one of us cracks a smile.  ...

negative caching is like response rate limiting: we can't operate the 
network at current or projected scale without them. the incorrectness 
(specifically: the incoherence) we allow due to caching (of both 
positive and negative elements) was a trade-off for scale. if you want a 
different trade-off, please propose one, being aware that i'll be 
reviewing its scaling properties.

caching is in some sense optional, since authority servers can send low 
TTL's (usually 1 second, since 0 is badly implemented by a lot of the 
older servers i wrote which are still in production use.) an authority 
server can also limit negative caching intervals by transmitting their 
SOA with negative responses, and setting SOA.MINIMUM to a low value.

i don't advise turning off caching; i'm simply saying that if you want 
to turn it off, you can do so, either by transmitting low-cacheability 
data from an authority, or by not implementing a cache in a recursive.

note that i'm not requiring that you actually purge, only that you 
effectively purge. i don't know if that changes your appreciation.

i cracked a smile at about 2am. thanks for that.

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Wed, 16 Mar 2016 01:17:09 +0000

> reviewing its scaling properties.

I agree.   I was simply pointing out that you are being inconsistent: you demand that the view of the DNS be consistent when an NXDOMAIN is cached, but do not further demand that NXDOMAINs not be cached in order to promote consistency.   A cached NXDOMAIN will prevent a more current view of the network from being seen, if the missing domain name comes into existence during the lifetime of the cached NXDOMAIN.

> effectively purge. i don't know if that changes your appreciation.

Unfortunately it does not.   I haven't heard an argument that makes me understand why it is important that we make this a normative requirement.

> i cracked a smile at about 2am. thanks for that.

:)

---

From: Ted Lemon <[email-masked]>
Date: Wed, 16 Mar 2016 01:27:18 +0000

> for <name,type=1> using the <name,type=1,rrset> you started out with?

Sorry, I didn't mean to blow past this point.  The correct answer depends on whether the two answers arrived in the correct order.   If they did, purging the cached answer is a no-brainer.   If they did not, caching the NXDOMAIN and purging the cached answer is wrong.   But this has nothing to do with nxdomain-cut.   RFC 2308 doesn't give any guidance on this; it seems obvious though that the spirit of the current state of the art is that the cached RRset should be purged--an out of order answer is quite a bit less likely than an in-order answer, and consistency is not paramount.

---

From: Ted Lemon <[email-masked]>
Date: Wed, 16 Mar 2016 01:36:21 +0000

It occurs to me that given Andrew's draft which is being discussed on another thread, draft-sullivan-dns-class-useless, it might be worth anticipating whether an NXDOMAIN for class=X should also result in an NXDOMAIN answer for the same name with class Y, where Y != X.   In practice I don't think DNS caches will forward such queries by default, so this may not be an important question to answer, but perhaps it should be included nevertheless?

---

From: Andrew Sullivan <[email-masked]>
Date: Tue, 15 Mar 2016 21:44:01 -0400

On Wed, Mar 16, 2016 at 01:36:21AM +0000, Ted Lemon wrote:
>  it might be worth anticipating whether an NXDOMAIN for class=X should also result in an NXDOMAIN answer for the same name with class Y, where Y != X.  
> 

FWIW, I believe that, according to the matching rules in STD 13,
NXDOMAIN is class-bound.  This is in fact related to the argument
about how the class selector fails to do what we'd have needed it to:
if you ask a name server that serves two different classes for the
same name about that name, it will need to figure out which class you
are asking about before it can start the label-by-label matching.
There is no guarantee that there's an answer in every class for a name
that is in one class.  (If there were, the DNS would be broken today:
the root servers won't give you delegation information about non-IN
classes, as far as I can tell.)

Best regards,

A

-- 
Andrew Sullivan
[email-masked]

---

From: Ted Lemon <[email-masked]>
Date: Wed, 16 Mar 2016 01:58:03 +0000

> classes, as far as I can tell.)

Thanks.   The two streams crossed in my head when I read Paul's comment earlier, and I had a bit of a wibble about whether there was some new clever DDoS attack to be had here, but further sober reflection and some questions answered by a colleague suggest that there is not.   But even if there were, based on your kind and learned interpretation of the holy writ, it appears that this would not be the place to address it.   :)

---

From: "Ralf Weber" <[email-masked]>
Date: Wed, 16 Mar 2016 10:04:36 +0100

Moin!

> for names that don't exist, and why should authoritative servers receive
In the grand scheme of things it doesn't matter. Authoritative servers get
unnecessary queries all the time. Look at any off Geoff Houstons
presentation on how DNS resolvers are behaving which I think he describes
as Obsessive–compulsive disorder. I see the same every week as an
authoritative for an open resolver scan where I for one open resolver
that has been asked once I see immediate multiple queries and after some
hours yet more despite nobody has asked for it again.

Yet with all this the amount of queries an authoritative server gets is a
tiny fraction of the queries the resolver gets. Most resolvers these days
have more than 90% cache hit rate in the mobile space even above 95%,
and the remaining 10 to 20th queries a resolver sends to an authority
are distributed amongst hundreds of thousands of authoritative servers,
so an authoritative server getting couple queries more really is a drop
in the ocean.

As for a lot more queries (random subdomain/qname or waterfall attacks or
whatever you call them) I don't think this would help as it is easy to
modify those to not add a label.

So long
-Ralf

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 16 Mar 2016 14:41:36 +0100

On Tue, Mar 15, 2016 at 05:23:55PM +0000,
 Ted Lemon <[email-masked]> wrote 
 a message of 8 lines which said:

> The draft says you have to do this, yes.

No, it does not.  draft-vixie-dnsext-resimprove-00 did but
draft-ietf-dnsop-nxdomain-cut-01 does not. You may disagree with the
contents but, please, do not misrepresent what's in the draft.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 16 Mar 2016 14:48:13 +0100

On Wed, Mar 16, 2016 at 10:50:55AM +1000,
 George Michaelson <[email-masked]> wrote 
 a message of 84 lines which said:

> How about if under load, a cache is permitted to convert NXDOMAIN
> ttl to 1/nth of the apparent ttl, based on some understood algorithm
> which relates to a load threshold?

IMHO, it is already allowed to do so at will. TTL have always been
_maximum_ time to live and a cache is free to _decrease_ the TTL (more
properly: to remove data before the TTL expiration) when it lacks
memory or for any other reason.

---

From: 神明達哉 <[email-masked]>
Date: Wed, 16 Mar 2016 10:44:47 -0700

At Wed, 16 Mar 2016 14:41:36 +0100,

> contents but, please, do not misrepresent what's in the draft.

In my understanding the latest major concern is about the first
paragraph of Section 2:

and specifically when the caching resolver has already cached a
positive answer for a subdomain (e.g., sub.example.com) of the owner
name (e.g. example.com) of the NXDOMAIN answer.  If the caching
resolver needs to be compliant to the SHOULD of the last sentence, it
will need to check whether there's a super domain of sub.example.com
that is cached with NXDOMAIN on receiving a query for sub.example.com
(and it will need to return NXDOMAIN without involving other external
queries).  In a sense that could be interpreted as a delayed form of
'rm -rf *.example.com'.  But in any event, I suspect that the main
objection is about the requirement of applying this SHOULD in such
cases because of the additional search overhead.

It may be just for convenience of a particular set of implementations
and we might dismiss the objection as such.  But on the other hand I
don't see a strong reason for not being lenient in this case.
Allowing the already cached positive answer for sub.example.com
doesn't cause additional external queries; in either case the query is
answered immediately from the cache but the answer just happens to be
positive instead of NXDOMAIN.  Personally I don't think it's that
harmful.  After all we can't even be sure if the NXDOMAIN is really
the newer information just because it arrives after the positive
answer.  So, if this makes some implementors happier I think it's
worth considering.

On the other hand, if it's about what the resolver should do when
sub.example.com hasn't been cached while there's cached NXDOMAIN for
example.com, arguments such as DoS mitigation can apply and it can be
more controversial.  But my latest impression in this thread is that
everyone is basically okay to follow the SHOULD in this case.

So I wonder: should we as wg keep requiring the SHOULD for the already
cached subdomains or can we loosen the requirement specifically for
that case?

--
JINMEI, Tatuya

---

From: Shumon Huque <[email-masked]>
Date: Wed, 16 Mar 2016 14:16:56 -0400

> cached subdomains or can we loosen the requirement specifically for

I've already stated I'm okay with relaxing the SHOULD for the case of
already
cached subdomains. It looks like Stephane and Paul might still oppose, but
this seems to be the easiest way to get consensus.

-- 
Shumon Huque

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Mar 2016 09:57:02 +1100

In message <[email-masked]>
>    queries for such names SHOULD elicit an NXDOMAIN response.

It is a SHOULD not a MUST.  Having a existing cache entry is a reasonable
exception to the SHOULD.

Or we could add "except when there is a existing cache entry
indicating data existed at one of the names between the cached
NXDOMAIN indication and the current QNAME".  This however may lead
to more discussions about the costs of testing for this.

Or we could add "There may be a cached name with data between the
cached NXDOMAIN and the current QNAME or at the current QNAME.  It
is implementation specific if this prevents the NXDOMAIN being
returned due to the cached NXDOMAIN."

Mark

---

From: Ted Lemon <[email-masked]>
Date: Thu, 17 Mar 2016 02:24:41 +0000

>On Wed, Mar 16, 2016 at 1:44 PM, 神明達哉 <[email-masked]<mailto:[email-masked]>> wrote:

> I've already stated I'm okay with relaxing the SHOULD for the case of already

I would be satisfied with this outcome.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 17 Mar 2016 11:13:59 +0100

On Thu, Mar 17, 2016 at 09:57:02AM +1100,
 Mark Andrews <[email-masked]> wrote 
 a message of 82 lines which said:

> It is a SHOULD not a MUST.  Having a existing cache entry is a
> reasonable exception to the SHOULD.

Yes. So, it's already allowed by the draft.

To make it clearer-than-clear, We could add after the last paragraph
of "Implementation considerations", something like:

Another reason to have a SHOULD and not a MUST is if a cache prefers
serving cached data (not yet expired) which is below the NXDOMAIN cut,
even after receiving a NXDOMAIN for a name located above the cached
data.

---

From: Tony Finch <[email-masked]>
Date: Thu, 17 Mar 2016 10:31:24 +0000

> I would be satisfied with this outcome.

Yes, it seems sensible to me.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Lundy, Fastnet, Irish Sea: East or northeast 4 or 5, becoming variable 3 or 4
in Irish Sea. Slight or moderate, becoming rough in southwest Fastnet. Fair.
Moderate or good.

---

From: Tony Finch <[email-masked]>
Date: Thu, 17 Mar 2016 10:44:58 +0000

Mark Andrews <[email-masked]> wrote:
> In message <[email-masked]>, =?UTF-8?B?56We5piO6YGU5ZOJ?= writes:
> >

The second SHOULD in the quote above seems to be explicitly saying that
those cache entries should be made unreachable, so I think it would be
unreasonable to interpret the SHOULD as meaning "don't implement this
requirement".

(Really, I think if a spec uses words like SHOULD, it ought to include a
discussion of when it is reasonable not to implement that requirement and
what are the consequences of not doing so.)

I think the spec needs to make an explicit distinction between conforming
behaviour for names already in the cache and names not in the cache.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Fisher: Northwesterly 4 or 5, increasing 6 or 7 at times later. Slight
becoming moderate, occasionally rough later. Fog patches. Moderate or good,
occasionally very poor.

---

From: Ted Lemon <[email-masked]>
Date: Thu, 17 Mar 2016 13:07:56 +0000

>behaviour for names already in the cache and names not in the cache.

The issue here is that there is no interoperability problem that these SHOULDs are addressing, so you can't have a discussion about the exceptions.   What this normative requirement is doing is giving explicit implementation advice, not saying what must be done for correct operation of the protocol.   That's the problem.   What this document should be doing is telling implementations that they are permitted to assume that names under an NXDOMAIN are also NXDOMAIN.   The way to do that is with a MAY, not a SHOULD:

Iterative caching resolvers MAY assume upon receiving an NXDOMAIN that all names below the name that elicited the NXDOMAIN response in the DNS hierarchy are also nonexistent, for the duration of the lifetime of the NXDOMAIN response.

All the rest of this verbiage is in the document essentially because the authors want to explicitly recommend one implementation strategy over another, not because there is actually any normative requirement.   If you just state this clarification as I've suggested , it can be a one page draft, and accomplish exactly what is needed.

---

From: Paul Vixie <[email-masked]>
Date: Thu, 17 Mar 2016 10:55:09 -0700

Tony Finch wrote:
> Mark Andrews<[email-masked]>  wrote:
>> In message<[email-masked]>, =?UTF-8?B?56We5piO6YGU5ZOJ?= writes:

because of how these documents are read and interpreted, i think 
requirements is the wrong word.

we should describe the positive benefits to the dns system (without 
mentioning any benefit or cost to any implementor or implementation style).

"As implied by STD 13 and as made explicit herein, an authoritative 
response of code 3 (NXDOMAIN) asserts the nonexistence of both its QNAME 
and all possible subdomains. DNS coherence can be systemically improved 
if, after receiving such a response and before receiving some new 
response indicating the existence of some RRset at or below that QNAME, 
a recursive server answers with code 3 (NXDOMAIN) for all questions 
which are equal to or subdomains of that QNAME, even if the recursive 
server has unexpired RRsets stored at subdomains of that QNAME. As to 
whether the resources held by such cached RRsets are reclaimed, or 
whether they are allowed to expire naturally, this specification makes 
no recommendation."

very few people are going to listen to a SHOULD or a MUST here, and 
those who listen will likely treat those words as equivilent. so let's 
not speak either word. we should describe the positive benefits of 
following this implication of STD 13, and then get off the stage.

-- 
P Vixie

---

From: Paul Vixie <[email-masked]>
Date: Thu, 17 Mar 2016 10:59:23 -0700

Ted Lemon wrote:
> The issue here is that there is no interoperability problem that
> these SHOULDs are addressing, so you can't have a discussion about
> the exceptions.

as a hop by hop matter, this is true. as an end to end matter, this is 
false.

in any case i think this SHOULD/MUST discussion is wrong headed, and 
i've explained my reasoning up-thread. (code is law, specifications are 
advice.)

-- 
P Vixie

---

From: Paul Vixie <[email-masked]>
Date: Thu, 17 Mar 2016 23:10:12 -0700

i've been a bit anxious about ted's use of the word "normative", so i 
looked it up:

> adjective
> 1. of or relating to a norm, especially an assumed norm regarded as
> the standard of correctness in behavior, speech, writing, etc.
> 2. tending or attempting to establish such a norm, especially by the
> prescription of rules: normative grammar.
> 3. reflecting the assumption of such a norm or favoring its
 > establishment: a normative attitude.

as this document is a clarification, it would be strange to have it 
place new constraints on implementations. but it's the word 
"prescriptive" that makes me want to run screaming down the hall to get 
away from the MUST vs. SHOULD discussion.

let the authors describe, please, what they can see, and then let the 
readers interpret and implement. thus the text below, which is factual, 
and no more.

> whether they are allowed to expire naturally, this specification makes

no SHOULD, no MUST. just, what we see. there are a million or more 
better ways to say it than what i wrote above, so let's say it better, 
but let's not say SHOULD or MUST. let's honour mike padlipsky on the 
matter, say that this document clarifies rather than specifies, and 
speak descriptively, not prescriptively.

it would be misleading to omit the description of positive coherence, 
but wrongheaded to make our observations into a burden on the 
implementer merely because this implication was not universally clear at 
first, and not explicit until now.

(so, ted, we appear to agree after all.)

-- 
P Vixie

---

From: Ted Lemon <[email-masked]>
Date: Fri, 18 Mar 2016 14:05:57 +0000

> (so, ted, we appear to agree after all.)

Sweet! 

Sorry for the excessive use of vernacular... :)

---

From: 神明達哉 <[email-masked]>
Date: Fri, 18 Mar 2016 10:02:07 -0700

At Thu, 17 Mar 2016 10:55:09 -0700,

> whether they are allowed to expire naturally, this specification makes

I can't speak for the authors, and I have no objection to this
proposed text personally, but I suspect this text will lose the
author's intent of recommending the nxdomain-cut behavior *quite
strongly*.

If the wg agrees to dropping the sense, this text is probably just
good enough.

If the wg wants to keep the sense of strong recommendation, I'm afraid
this proposed text is too weak.  In that case, and if the use of
RFC2119 keywords is the major blocking issue in that case, then we
should discuss whether we can still keep the sense of strong
recommendation without using 2119 keywords.

--
JINMEI, Tatuya

---

From: Paul Vixie <[email-masked]>
Date: Fri, 18 Mar 2016 12:15:08 -0700

>> (so, ted, we appear to agree after all.)

to be clear, we disagree that the flat hash nature of some recursive 
servers is a good enough reason to not say SHOULD here. our agreement on 
not saying SHOULD is a coincidence. as a clarification, i'm sure that 
this document should not be prescribing, merely observing.

-- 
P Vixie