Subject: [DNSOP] Fwd: New Version Notification for draft-muks-dnsop-dns-thundering-herd-00.txt

From: Mukund Sivaraman <[email-masked]>
Date: Thu, 25 Jun 2020 22:20:49 +0530

On Thu, Jun 25, 2020 at 09:32:39AM -0700, [email-masked] wrote:
> 
> A new version of I-D, draft-muks-dnsop-dns-thundering-herd-00.txt
> has been successfully submitted by Mukund Sivaraman and posted to the
> IETF repository.
> 
> Name:		draft-muks-dnsop-dns-thundering-herd
> Revision:	00
> Title:		The DNS thundering herd problem
> Document date:	2020-06-25
> Group:		Individual Submission
> Pages:		6
> URL:            https://www.ietf.org/internet-drafts/draft-muks-dnsop-dns-thundering-herd-00.txt
> Status:         https://datatracker.ietf.org/doc/draft-muks-dnsop-dns-thundering-herd/
> Htmlized:       https://tools.ietf.org/html/draft-muks-dnsop-dns-thundering-herd-00
> Htmlized:       https://datatracker.ietf.org/doc/html/draft-muks-dnsop-dns-thundering-herd
> 
> 
> Abstract:
>    This document describes an observed regular pattern of spikes in
>    queries that affects caching resolvers, and recommends software
>    mitigations for it.

For whoever is interested, this is a description of a pattern of queries
noticed at busy public resolvers that has led to issues in at least 4
different sites in the last 2 months.

The current revision is a work in progress. We are still developing some
mitigations for NIOS, and some more introductory text also has to be
added.

		Mukund

---

From: Paul Wouters <[email-masked]>
Date: Thu, 25 Jun 2020 14:29:03 -0400 (EDT)

> mitigations for NIOS, and some more introductory text also has to be

I would add a more explicit section on using prefetching of frequently
asked queries, which mitigates (eliminates) the period when an answer is not
available in the cache.

Paul

---

From: dagon <[email-masked]>
Date: Thu, 25 Jun 2020 19:14:51 +0000

> mitigations for NIOS, and some more introductory text also has to be

This might be another mitigation:

3) "EFMB Caching: Endless Forms Most Beautiful Caching" [0]

    Since DNS messages are often disposed of in tens of ms, and
    authorities express TTL in whole second increments, recursive
    pools might adjust the 'smaller TTLs' (perhaps defined as <5 min)
    to any prime number within, say, +/-10% or more of the answer TTL.
    So a 60 second TTL become perhaps 53, 59, 61, 67, or 71 etc.

    Such adjustment is picked uniquely (perhaps using L2 internals or
    UUIDs) by nodes in a recursive farm.  Upon expiration, the herd of
    expired recursives forms an in-order refresh to the authority,
    spaced by seconds or more.  The software changes for this behavior
    appear minimal, as it slightly adjusts a TTL just prior to
    caching, with reference to some UUID, MAC, etc.

    This avoids the need to share cache additions among a recursive
    pool---an expensive and complex task that amplifies mass cache
    ejection attacks cause by, e.g., Facebook's session-specific
    dynamic domains.

    Using your "thundering herd" metaphor, this is like the natural
    selection of prime numbers in insect swarming populations (e.g.,
    13-year cicadas are common, since the 2- 4- and 6- year cicada
    populations coincided with periodic predator increases, and were
    not selected over generations.  (Cf.
    https://cims.nyu.edu/~eve2/predprey.pdf ).

This is a very interesting problem, so thanks for addressing this,
even if this idea doesn't prove useful.

[0] Darwin: "whilst this planet has gone cycling on according to the
fixed law of gravity, from so simple a beginning endless forms most
beautiful and most wonderful have been, and are being, evolved."  So
too has DNS followed seemingly fixed basic laws, and yet changed
endlessly to address complex problems, real or perceived.

-- 
David Dagon
[email-masked]
D970 6D9E E500 E877 B1E3  D3F8 5937 48DC 0FDC E717

---

From: Robert Edmonds <[email-masked]>
Date: Thu, 25 Jun 2020 16:07:25 -0400

> different sites in the last 2 months.

This seems like a description of a resolver implementation vulnerable to
the infamous VU#457875. Perhaps an update to the standards track RFC
5452 ("Measures for Making DNS More Resilient against Forged Answers")
would be more appropriate than a new document? That document mentions
the security problem caused by having multiple outstanding queries for
the same question but doesn't clearly state a requirement to
de-duplicate, perhaps because that mitigation was already very common in
resolver implementations at the time the document was published.

-- 
Robert Edmonds

---

From: Paul Wouters <[email-masked]>
Date: Thu, 25 Jun 2020 16:14:02 -0400

> resolver implementations at the time the document was published.

This puzzled me too. Isn’t this a long solved problem? But apparently not, if this is now showing up as it apparently does.

It would be interesting to know which dns implementations are failing here.

Paul

---

From: Paul Vixie <[email-masked]>
Date: Fri, 26 Jun 2020 01:02:51 +0000

> asked queries, which mitigates (eliminates) the period when an answer is not

i'm sorry in advance for anybody who is now hearing this for the 100th time.

please don't pre-fetch. feel free to pre-discard; TTL is a maximum, and if you 
want to randomly subtract from TTL upon every reuse, you'll remain compliant. 
if the data turns out to be important it'll return. but prospective pre-fetch 
means you may be creating network load for no purpose -- the data may not come 
back again, or if it does, it may have changed, in which case you don't want 
the stale stuff that pre-fetch would have brought you.

this solves the thundering herd problem but without creating new problems. the 
goal is de-synchronization. random subtractions to TTL in cache accomplishes 
it.

-- 
Paul

---

From: Mukund Sivaraman <[email-masked]>
Date: Fri, 26 Jun 2020 17:31:11 +0530

Hi Paul

> asked queries, which mitigates (eliminates) the period when an answer is not

The resolvers in question had prefetching functionality enabled. It
didn't help mitigate the problem. These are very busy public resolvers,
and their clients for the most part are static participants (in other
words, clients don't join and leave the group in large numbers in the
TTL interval). So the clients align themselves into herds at the expiry
time, and they show up in a spike that is instantaneous. The frequency
of these spikes was observed to be equal to the TTL of the
answer. Prefetching does not happen as there's often no lone client that
comes in a few seconds before the answer expires. The answer expires and
the spike causes nuisance.

Your suggestion to mention prefetching is good though and I will add
notes on what happens with prefetching.

		Mukund

---

From: Mukund Sivaraman <[email-masked]>
Date: Fri, 26 Jun 2020 17:53:42 +0530

Hi Robert

> resolver implementations at the time the document was published.

I've been familiar with de-duplication in fctx_match() in BIND (and only
what was the obvious benefit, i.e., just de-duplication of work). I was
not aware of VU#457875; thank you for pointing to it.

The draft describes a query pattern problem. De-duplication of queries
is one mitigation that helps upstream NS query spikes. The spikes on the
resolver side are also a nuisance, and they can be smoothed.  It is also
not just one herd - with the popularity of apps, there are several
address queries that happen for names that humans don't normally observe
or enter anywhere, to do with analytics, image webservers, etc. These
are high frequency (TTLs of 60s and under). So the resolver gets hit
again and again by different groups of clients in spikes, whereas they
can be a smoother query curve.

		Mukund

---

From: Mukund Sivaraman <[email-masked]>
Date: Fri, 26 Jun 2020 17:58:36 +0530

> i'm sorry in advance for anybody who is now hearing this for the 100th time.

IIRC I read a message from the PowerDNS folks to dns-operations@
sometime ago that prefetch didn't help or show any observable effect in
practical deployment, as much as it is assumed to.

		Mukund