Subject: [dnsext] Suggested fallbacks...

From: Nicholas Weaver <[email-masked]>
Date: Fri, 21 Aug 2009 11:20:38 -0700

I think at this point we can presume "UDP Fragmentation is a problem  
for some".

So stupid quesiton: Why not just have the resolver discover for itself  
when its the problem, and do something about it?

The resolver already needs to keep track of EDNS0 fallback for every  
particular authority, no?  (If you don't you get bad behavior where a  
non-EDNS-liking authority will see eg, 3 second latency.  We  
experienced this in Netalyzr's F&F testing).

So why not do the following:

EDNS@4096.  If failed, fallback to EDNS@1400.  If success, and the  
response was > 1500B, record the server as "MTU > 1500"

EDNS@1400.  If success but truncated, mark that server as EDNS@1400,  
and on truncation, you fall back to TCP, of course.

and then the rest of Bind's current policy or a similar policy.

Its only one additional state in the fallback chain, but it allows one  
key addition...

Keep a global count of the following:

# of servers where you've gotten a reply where MTU > 1500B

# of servers which have been marked as EDNS1400

When the # of EDNS1400 servers - MTU-1500B servers > B (B = 5 is a  
good number, this is a threshold-random-walk count, but 10 is good for  
paranoia), the resolver now presumes it is behind a broken middlebox  
and changes its default EDNS0 MTU from 4096 to 1400, as its learned  
the presence of a broken middlebox.

When in EDNS@1400 mode, if a reply is truncated, don't just fallback  
to TCP, but also, with a random probability P, also conduct a UDP  
query with EDNS@4096 (which is not for returning but for path probing).

If the probe succeeds at MTU>1500, add 1 to a second counter.  If it  
fails, subtract one (but don't let the count get below -10).  If it  
succeeds but the reply was <1500, do nothing.

If this second count ever gets about another threshold (again, 5 is a  
good one, 10 for paranoia), the middlebox has gone away and gotten  
fixed, so return to EDNS@4096 and reset all counters and server status.

Why?

This is effectively learning: the resolver is able to quickly (with  
timeout events to only 5 servers!) discover that it is behind a broken  
middlebox which is causing fragmented DNS traffic to fail, and if so,  
change to a default behavior which prevents this problem.

It is also able to quickly learn when the broken middlebox gets fixed,  
allowing it to automatically fallback to normal behavior.

It won't reduce the number of TCP queries when behind a broken  
middlebox, but it eliminates the timeout latency for these queries  
(which is the far bigger concern:  Which is worse, an additional 2  
RTTs for a large-response query, or 2 RTTs plus a no-response  
timeout?  You're still going to have the TCP hit anyway...).

Its a single sided, resolver only change.

The resolver needs to keep per authority state, but it already needs  
to keep per authority state on EDNS0 behavior, and this is only  
effectively a couple more bits to that state.  If you don't want to  
keep exact per-authority state, use a couple of small bloom filter for  
the global status of authorities, so you can even do this with bounded  
state.

It automatically "unlearns", so if the middlebox gets fixed, this gets  
fixed.

EDNS@1400 is likely to be a "safe" number, but you could do learning  
at a couple of other points as well (EDNS@1000, EDNS@512).

And now, you won't see the severe latency issues you might otherwise  
have with DNSSEC and large replies.  You will still see TCP load on  
the authorities, but really, so what?

Thoughts?

---

From: Michael Graff <[email-masked]>
Date: Mon, 24 Aug 2009 16:04:53 -0500

Nicholas Weaver wrote:
> I think at this point we can presume "UDP Fragmentation is a problem for
> some".
> 
> 
> non-EDNS-liking authority will see eg, 3 second latency.  We experienced
> this in Netalyzr's F&F testing).

This is a cache, and a short-lived cache at times.  IMHO, any design
that relies on discovering and performance is based on remembering such
data is flawed.

> response was > 1500B, record the server as "MTU > 1500"

Please define "the server" here.  do you mean the remote server?  That
is, the thing that answered?

If so, I don't think this makes a lot of sense.  I would suspect that
the limiting factor on what can be received is not on the sending end
(as this tracking would imply) but on the receiving end.  Therefore,
learning the safe fallback might help, but it should be "what I can
safely receive" not "what that server over there, that I now need to
maintain state about, can send me."

I don't think it's practical to expect to maintain state on every auth
server I might speak to.

- --Michael

---

From: Nicholas Weaver <[email-masked]>
Date: Mon, 24 Aug 2009 14:36:24 -0700

On Aug 24, 2009, at 2:04 PM, Michael Graff wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Nicholas Weaver wrote:

Then you get REALLY cruddy performance:  This is data that should  
already be cached per authority.  Bind does do this already, but I've  
seen the results when a resolver does not and the authority ignores/ 
fails on EDNS: its ugly.

> is, the thing that answered?

Authority.

> maintain state about, can send me."

Its the observation that you are doing a TRW count: the # of remote  
authorities you can contact where you CAN get a >1500B response vs the  
# of authorities you can't.

When the difference between the two exceeds a threshold, you have  
learned you are behind a broken middlebox.  This is a long-lived  
property,

> I don't think it's practical to expect to maintain state on every auth

A:  Don't you do this already?  All those cached NS records are state  
about each authority you may talk to.

B:  If you are so afraid of per-authority state, just use two bloom  
filters, one thats "This authority can give me a >1500B response" and  
"this authority can NOT give me a >1500B response".

For this purpose, the single-sided error of a bloom filter is no  
problem, you aren't using this to actually decide a local property of  
a given authority, but just to track whether it has already been  
included in the trouble/OK count or not.

So although I'll argue the per-authority state should already be  
there, if not, you don't need per-authority state but can used bounded  
state just as well.

---

From: Doug Barton <[email-masked]>
Date: Mon, 24 Aug 2009 14:58:58 -0700

> I don't think it's practical to expect to maintain state on every auth

Why not? BIND at least already keeps a running record of RTT for each
authority you query. This would just be one more data point, and
unlike RTT it would be static (for all practical purposes).

Doug

---

From: Michael Graff <[email-masked]>
Date: Mon, 24 Aug 2009 18:55:34 -0500

> unlike RTT it would be static (for all practical purposes).

It keeps a cache of them yes, but I don't think this cache is infinite,
nor can it really be.  Imagine if it was; I could kill your server
trivially with a IPv6 tunnel.

- --Michael

---

From: Nicholas Weaver <[email-masked]>
Date: Mon, 24 Aug 2009 18:09:46 -0700

WHich means you have all the information you need basically.  TRW- 
based learning can handle a lot of fuzzyness.

On Aug 24, 2009, at 4:55 PM, Michael Graff wrote:

> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.8 (Darwin)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iEYEARECAAYFAkqTKHUACgkQ+NNi0s9NRJ1tcwCghOy0e+wiulj5F6YjmCzp1wOm
> iqQAoJpytTs0O22l/KLhGvMBL5IDDD8o
> =aqXk
> -----END PGP SIGNATURE-----
>