Subject: Keying queries on information outside the q-tuple (Re: [dnsext] Personal position on adopting the client-subnet option)

From: Alex Bligh <[email-masked]>
Date: Tue, 01 Jun 2010 11:58:43 -0400

--On 31 May 2010 15:37:48 -0700 Colm MacCárthaigh <[email-masked]> 
wrote:

> The engineering problem;
> Open Resolvers and CDN DNS tricks do not work well together - because
> of the much broader client base of open resolvers, the source IP of
> the query towards the CDN has very poor network locality.

Hmmm...

Perhaps we are looking at this the wrong way. My take on your
argument is:

a) there are a substantial number of CDN operators who already
   use information outside the q-tuple to help them look stuff
   up - in this case source IP address, though no doubt they may
   mangle that with BGP or whatever first. Various folks disapprove
   of this ("stupid DNS tricks" or whatever), but presumably
   disapprove less when it's not affecting them and/or the DNS
   protocol.

b) there are a substantial number of "open resolvers" (or
   more precisely caching resolvers topologically distant from the
   stub resolver - whether they are open or not is irrelevant)
   which break the model used in (a) as they do not pass
   on information that is outside the q-tuple; indeed they
   only pass on information inside the q-tuple because that's
   precisely how their caches are keyed. A smaller number of
   people (including me, incidentally) seem to think this model
   is bad (or at least suboptimal in most cases), and that the
   correct model is to push the caching nameserver
   as close to the client as possible.

Now, there are all sorts of ugly hacks possible for the likes
of OpenDNS to achieve something like the result they want already.
To pick an obvious one, they could arrange for their servers
to be spread over the the internet's topology using anycast
IP for the resolving addresses, but unique IPs for outbound
queries. That way the CDNs would see queries from different
places within the topology in different IPs. To the extent anycast
can be made to approximate topological proximity, this would
work. And it's not hard to see how this could be extended so
as to not require lots of physical servers. But I hear off-stage
mutterings of "those who live by stupid DNS tricks shall die
by stupid DNS tricks".

However, let's assume this is just one instance of a requirement
to key a look up on more than the standard q-tuple. Let's also
assume that criteria for any protocol fixes are:
 1. It doesn't require a protocol change for anyone other than
    those in groups (a) or (b) above
 2. It doesn't materially increase load on either clients or
    servers for anyone other than those in groups (a) or (b)
    above, or at least not by any more than fixing the
    problem another way (e.g. my straw man proposal above).
 3. It is written in a generic way, to maximise usefulness for
    anyone else who might want to do this.

So, what about an EDNS option called 'edns-query-hint' or similar.
This contains a list of 2-tuples which are 'things the upstream
server might like to consider when doing a DNS lookup'. So,
for instance this might be
    ((CLIENT_IPV4_SUBNET, 192.0.2.0/24),
     (CLIENT_ASN, 7777))
or whatever. The authoritative server, if it understands the
EDNS option at all, responds with those key types it is
interested in in the reply packet (so in the example above, if
it never looked up on anything bar CLIENT_IPV4_SUBNET, it
returns that). The caching resolver MUST then negatively cache
these, so that it doesn't send further queries at all (in the
case of an EDNS option not understood) or an option other
than one the upstream resolver understands for (say) an hour.
This means the maximum additional load on any authoritative
nameserver is packet elongated by a few tens of bytes per
hour per caching resolver. If an authoritative server replies
that it understands a particular option type, the caching
server MUST use this as an additional key to the query in
its cache (i.e. it can't just reply with TTL as zero); i.e.
it must perform as though all cache entries other than those
returned with that key type were not present, or in other
words act as if it were multiple separate caching resolvers.
The option is point to point. We treat privacy as a higher
layer problem, i.e. we say "Here's what information OpenDNS
passes on to an upstream provider - if you don't like this,
don't sign up". If a caching provider wants to do have some
form of transitive option, that's fine, but it's done hop by hop,
and in general I think it's a bad idea to require any client
code change at all.

I believe this satisfies my slightly arbitrarily chosen
design criteria, in that it puts all the load on the CDNs
and the open servers using it. It may be a nasty hack, but
it's a standardised nasty hack which has very little
collateral damage.

-- 
Alex Bligh

---

From: Colm MacCárthaigh <[email-masked]>
Date: Tue, 1 Jun 2010 09:35:08 -0700

2010/6/1 Alex Bligh <[email-masked]>:>
> or whatever.

I think it would take more work to make such a system as the proposal
that's here already. IP subnets would need all of the CIDR/VLSM
cacheability hints, and other fields would need other heuristics.
Potentially the server might have to implement http
content-negotiation "Vary:" style semantics in its caching. Those are
tractable though, and if someone wrote such a draft with proper
consideration, I'd be in favour of it too.

-- 
Colm

---

From: Alex Bligh <[email-masked]>
Date: Tue, 01 Jun 2010 12:53:20 -0400

Colm,

> cacheability hints, and other fields would need other heuristics.

No they wouldn't. The caching resolver *could* supply CIDR BGP
reachability hints, or it *could* always truncate at /24, or it
*could* always pass on the /32, or it *could* pass on nothing.
It's a matter of local policy. Equally it could put in the
AS number of not. It depends how helpful it wants to be to the
CDN, and how concerned it is (on its user's behalf) about IP
address privacy. So in the above example, the caching
resolver could have chosen to pass
   ((CLIENT_IPV4_SUBNET, 192.0.0.0/17),
    )
or
   ((CLIENT_IPV4_SUBNET, 192.0.2.7/32),
    )
or some combination of those and the ASN or whatever.

The substantial extra work that needs to be done is rewriting
the cache in the caching nameservers to filter by the additional
tags it supplies. I would argue this needs to be done anyway
to do proper caching in your draft.

> consideration, I'd be in favour of it too.

Not sure that's necessary.

-- 
Alex Bligh

---

From: [email-masked]
Date: Tue, 1 Jun 2010 17:06:05 +0000

On Tue, Jun 01, 2010 at 09:34:03AM +1000, Mark Andrews wrote:
> 
> Part of the problem is that caches now go from 1 RRset per name to
> 1 RRset per client.  That is a fundamental change in design
> constraints.

	is there an IETF RFC  on DNS cache design?

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

---

From: John Payne <[email-masked]>
Date: Tue, 1 Jun 2010 13:40:55 -0400

On Jun 1, 2010, at 12:34 AM, Mark Andrews wrote:

> 
> In message <[email-masked]>, John Payne wri
> tes:
>> On May 31, 2010, at 7:48 PM, Mark Andrews <[email-masked]> wrote:
>> 
>>> 
>>> In message =
>> <[email-masked]>, =3D?IS
>>> O-8859-1?Q?Colm_MacC=3DE1rthaigh?=3D writes:
>>>> [1] "The mission of the IETF is make the Internet work better by
>>>> producing high quality, relevant technical documents that influence
>>>> the way people design, use, and manage the Internet"  - IETF mission
>>>> statement.
>>> 
>>> This is not a zero cost solution.  There are down sides to deploying
>>> this technology.  It will require bigger more complicated caches to
>>> support the same number of clients.
>> 
>> When does the IETF limit itself to zero cost solutions?
> 
> It was being presented as all benefit when it has downsides.  Those
> downsides need to be taken into consideration.

Point taken, but the downsides are all at the implementations that are authoring/supporting this draft, no?

---

From: Colm MacCárthaigh <[email-masked]>
Date: Tue, 1 Jun 2010 10:44:21 -0700

> *could* always pass on the /32, or it *could* pass on nothing.

I think you may be missing some of the detail of the proposed option
before us. The option allows for the authoritative server to reply
with cacheability hints for subnets that are greater or larger in size
than the one supplied in the query. That improves caching overall -
and makes it better in at least one respect than the simple scheme you
outline :-) Incidentally all of what you have wrote in that paragraph
is also true of the proposal before us.

Moving back a little, there's nothing wrong with simply using multiple
EDNS options to pass on multiple parameters. E.g.

  DNS QUERY, EDNS0 CLIENT_SUBNET OPTION, EDNS0 CLIENT_AS_NUMBER OPTION

so re-thinking, I'm not sure what the benefit of folding them all into
one option would be. There needs to a registry for the "flags" - we
may as well use the existing EDNS option registry.

> to do proper caching in your draft.

Yes :-) I'm one of the authors of Apache's mod_cache and associated caching
modules there - it's a complex negotiation-friendly cache that is well-deployed
and widely used for a variety of purposes. Based on that experience, I'm not
sure I'd agree that it's substantial, I found coping with that kind of
negotiation
a relatively straightforward matter of hashing, trie data-structures and so on.

-- 
Colm

---

From: Alex Bligh <[email-masked]>
Date: Tue, 01 Jun 2010 16:09:33 -0400

--On 1 June 2010 10:44:21 -0700 Colm MacCárthaigh <[email-masked]> 
wrote:

> before us.

Possibly - I read the latest draft far less thoroughly than I did
the first one. However, the main thing I don't like is that the
option originates at the client. There is a presumption the stub
resolver changes (or at least can change) which I think is both
unnecessary and invidious. If it does, then inevitably the option
starts being passed in more traffic than just caching resolver
to authoritative, and it's one more thing making packets larger,
which is a bad thing in the land of the broken middlebox. If
I've got completely the wrong end of the stick here, I apologise.

-- 
Alex Bligh

---

From: Mark Andrews <[email-masked]>
Date: Wed, 02 Jun 2010 12:50:48 +1000

> 	is there an IETF RFC on DNS cache design?

It's implict in the design.  It the intent was to supply different
answers to different clients then there would have been provision
for it in RFC 1033, RFC 1034 and RFC 1035.
 
Mark

---

From: Wilmer van der Gaast <[email-masked]>
Date: Wed, 2 Jun 2010 15:30:24 +0100

2010/6/1 Alex Bligh <[email-masked]>:
> option originates at the client.

We wouldn't like that either. :-) We also plan to have the resolver
add the option. Sadly the first version of the draft failed to be very
clear about it. An early version of the draft didn't take
transitiveness into account, and when we added awareness of that
later, things became too complicated.

This is one of the parts of the doc that has been rewritten for -01,
see section 4.1 ("Originating the option"). Yesterday, I put a summary
in more specific non-RFC language on the mailing list as well, let me
quote it here:

"""
In very specific language, this is how we intend the option to be used:

* A recursive resolver (often an open resolver, or possibly a resolver
run by an ISP with more peering points than DNS resolver pools) adds
the option to requests. It *can* add it to all requests, but
preferably it keeps track of authorities that support the option and
send it only to them, to improve performance and slightly improve
privacy.
Another option is that the resolver admin keeps a list of
edns-client-subnet-enabled authorities by him/herself. Since the
option will only benefit a small number of large CDNs, this list is
not likely to grow a lot.

* Users who for one reason or the other don't want any of their
address information to be added to requests, and know that their
resolver supports edns-client-subnet, can add the option with a 0/0
address. A compliant edns-client-subnet resolver will respect this. A
resolver that doesn't support edns-client-subnet will just ignore it.
If a resolver somewhere in between is ignorant of the option, it gets
stripped. The edns-client-subnet-enabled resolver later on will add it
again - but not with the user's address, since that address is already
invisible.

* Not really one of the goals of the option, but: if the user knows
the subsequent connection to the address received from the DNS will
use a different route than the DNS request itself, the option allows
for possibly better results from the CDN.
"""

>From how I read your proposal, we're mostly on the same page. We have
thought of putting other pieces of information besides/instead of IP
addresses in the option, but decided to stick with just IP addresses,
since that's the only information the resolver has - sure it can
convert the IP address to an things like AS# or coordinates, but in
our opinion it's better to do that work on the CDN side if it wants to
do so.

IMHO getting a /24 is much more useful than anything else since the
CDN knows better what its network/peering looks like than the
resolver. Having an ASN is nice, but it usually won't tell me, for
example, if the client is on the East Coast or the West Coast Comcast
network.

Regards,

-- 
Wilmer van der Gaast, Traffic SRE/Google Public DNS team.
Google Ireland.

---

From: Alex Bligh <[email-masked]>
Date: Wed, 02 Jun 2010 11:33:55 -0400

Wilmer,

> send it only to them, to improve performance and slightly improve

My argument is that in order to avoid increasing load to most of the rest
of the world, a recursive server using the option MUST keep a negative
cache of those upstream servers who don't understand it, and not send
packets with this option to them in future. Irrespective of the load
argument, negative caching is only sensible as inevitably there will be
authoritative servers that will choke on this option (e.g. if they are
behind a firewall that drops packets with unknown EDNS options). This
means that a reply to a query with the option has to signal that
the option is understood.

> not likely to grow a lot.

This is in essence a manual whitelist. It risks suffering O(n^2)
problems and causes entry problems for new CDNs. I don't like
this, and it's unnecessary since you can easily signal the option
is understood.

> again - but not with the user's address, since that address is already

The current way you have implemented this if I read it right is that
the client can specify any IP address it wants. Given NATs, user
stupidity etc., this is highly prone to error. Personally I think
trying to encode privacy concerns into the DNS protocol (as opposed
to open resolver terms and conditions) is a complete waste of time,
not least as the very next connection is very likely to be an
http request to the same CDN. But even if you made it a separate
configurable packet, configuring it necessarily involves some knob
on the client reconfiguring DNS, which is bad. A far easier solution
for those concerned about privacy is for the open resolver just to
offer a different set of IPs which respect the privacy setting
(or tell users concerned about this aspect of privacy to go
elsewhere, which is what I would do).

> example, if the client is on the East Coast or the West Coast Comcast

Sure. I just thought there was all sorts of dross one might want to
specify: ASN, coordinates, language, whatever. I was trying to sweep
them all up into the same somewhat stinky pile. Not a major concern.

-- 
Alex Bligh

---

From: Nicholas Weaver <[email-masked]>
Date: Wed, 2 Jun 2010 08:59:01 -0700

> elsewhere, which is what I would do).

On one hand, I agree:  'go elsewhere' is a better solution, especially since those using third party resolver services have already agreed to spew all this privacy sensitive information to the third party.

OTOH, I don't think errors are that bad.  Remember, ALL answers returned by the authority are valid answers, just not necessarily OPTIMAL answers.  If a user misconfiguration, user stupidity, etc results in a few seconds more latency on page load, its the user's problem.

> them all up into the same somewhat stinky pile. Not a major concern.

/24 is special, however, and why I personally like this proposal:  Subnet (albeit on a slightly coarser granularity) is leaked already by normal resolvers, and this should only matter to third-party resolvers, while other data might matter for ALL resolvers.

---

From: Alex Bligh <[email-masked]>
Date: Wed, 02 Jun 2010 12:20:40 -0400

--On 2 June 2010 08:59:01 -0700 Nicholas Weaver <[email-masked]> 
wrote:

> On one hand, I agree:  'go elsewhere' is a better solution, especially
> since those using third party resolver services have already agreed to
> spew all this privacy sensitive information to the third party.
>
> OTOH, I don't think errors are that bad.  Remember, ALL answers returned
> by the authority are valid answers, just not necessarily OPTIMAL answers.
> If a user misconfiguration, user stupidity, etc results in a few seconds
> more latency on page load, its the user's problem.

If by errors you mean non-optimal answers, I am not concerned about such
errors at all; it can be no worse than the current situation. I am
concerned about the proposal's large footprint. Specifically, I am
concerned about introducing a complexity into the stub<->recursive path
(which risks hitting all recursive servers and is more fragile due to
middleboxen on the way), when for near zero loss of functionality,
disruption could be limited to the recursive<->authoritative path and (with
negative caching) absolutely minimally impact any authoritative servers who
don't use the information. Currently the proposal risks collateral damage
whereas it need not - it could be essentially private to those who need it.

-- 
Alex Bligh

---

From: Nicholas Weaver <[email-masked]>
Date: Wed, 2 Jun 2010 09:25:41 -0700

On Jun 2, 2010, at 9:20 AM, Alex Bligh wrote:

> 
> 
> --On 2 June 2010 08:59:01 -0700 Nicholas Weaver <[email-masked]> wrote:
> 

Here's the problem:  On one hand, I agree with you.

OTOH, there are several vocal people who insist that if the client desires it, the resolver does not use the client-subnet option in a way which leaks information, which requires that the client, in such cases, be able to say "don't use the option", which of course stresses all them broken middleboxes...

(1.4% or so of Netalyzr tests, for example, are behind middleboxes that block EDNS0)

---

From: Alex Bligh <[email-masked]>
Date: Wed, 02 Jun 2010 12:31:25 -0400

--On 2 June 2010 09:25:41 -0700 Nicholas Weaver <[email-masked]> 
wrote:

> OTOH, there are several vocal people who insist that if the client
> desires it, the resolver does not use the client-subnet option

Well, people being vocal does not mean they are right! But...

> which requires that the client, in such cases, be able to say "don't use
> the option", which of course stresses all them broken middleboxes...

Nope - there are other ways to do this, which are actually SIMPLER for
the client (i.e. do not require an OS change). The most obvious is simply
to use different set of IP addresses for the resolving servers
for those concerned about privacy. Yes, a given open resolver might choose
not to do this, but then they might also choose not to respect incoming
EDNS0 options (despite the standard), to sell all their data to $evilempire
or whatever.

Moreover, didn't we find middleboxes that (by proxying DNS or otherwise)
strip unknown EDNS0 options? In which case the option doesn't guarantee
DNS privacy anyway.

-- 
Alex Bligh

---

From: Nicholas Weaver <[email-masked]>
Date: Wed, 2 Jun 2010 09:33:20 -0700

On Jun 2, 2010, at 9:31 AM, Alex Bligh wrote:

> 
> 
> --On 2 June 2010 09:25:41 -0700 Nicholas Weaver <[email-masked]> wrote:
> 

Good point.

> strip unknown EDNS0 options? In which case the option doesn't guarantee

We aren't checking for that yet myself on Netalyzr (neither unknown RRs nor unknown EDNS0 options), but I think most authorities tested are actually happy with random EDNS0 options, but not all are (George Barwood I think ran a test of that).

---

From: Alex Bligh <[email-masked]>
Date: Wed, 02 Jun 2010 13:07:42 -0400

--On 2 June 2010 09:33:20 -0700 Nicholas Weaver <[email-masked]> 
wrote:

> We aren't checking for that yet myself on Netalyzr (neither unknown RRs
> nor unknown EDNS0 options), but I think most authorities tested are
> actually happy with random EDNS0 options, but not all are (George Barwood
> I think ran a test of that).

I /think/ Ray's tests found something like this (though I have a habit
of false memory when it comes to Ray's tests).

-- 
Alex Bligh

---

From: Ray Bellis <[email-masked]>
Date: Thu, 3 Jun 2010 08:57:28 +0000

> of false memory when it comes to Ray's tests).

:)

We certainly found some units that barfed completely in the presence of
*any* EDNS0 options.  That's consistent with what Nick has seen on Netalyzr.

We didn't check for "unusual" EDNS0 options - the only thing we were
specifically testing for was the EDNS0 buffer size.

Ray

---

From: [email-masked]
Date: Thu, 3 Jun 2010 09:32:34 +0000

> for it in RFC 1033, RFC 1034 and RFC 1035.

	I read general guidelines about how the cache should
	behave -externally- in regard to specific, enumerated RR types
	in those three documents, but I don't see any explicit design 
	documents on cache design, management, and in the case of newer 
	DNS features, behaviour.

	wrt changing the design from a single RRset per name to 
	a single RRset per client (whatever that means)... we have
	seen this movie before, when the concept of an "atomic" RRset
	was created - the atomic unit used to be (and still sort of 
	is) the individual RR.  The RRset is functionally a convience
	for working with DNSSEC.  (yes, we can re-open this rat hole,
	but it might be better left closed - i'm just pointing out
	that we have changed behaviour before -in the ABSENCE of
	a clear cache design spec- and so doing it again doesn't
	seem all that bad.  

	We need an explict cache design spec if we are going to
	argue that this is a "fundamental change in design constraints" -
	to borrow your words.

	IMHO of course.

--bill

---

From: Wilmer van der Gaast <[email-masked]>
Date: Thu, 3 Jun 2010 12:02:27 +0100

> *any* EDNS0 options.  That's consistent with what Nick has seen on Netalyzr.
I've seen this not only with consumer hardware, but also with for
example Citrix Netscalers in certain configurations (when using a DNS
vserver instead of a simple blind 53/UDP one). I've had this problem
myself and there are other examples:

nibbler~$ dig +nsid www.microsoft.com @65.55.37.62

; <<>> DiG 9.6.1-P3 <<>> +nsid www.microsoft.com @65.55.37.62
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: FORMERR, id: 17573
[...]

It seems to be fine with EDNS0 otherwise, but is not aware of the
concept of options *at all*.

Wilmer.