Re: [dnsext] bitmap inference was Re: ... - NXDOMAIN for emptynon-terminals

Brian Dickson <> Wed, 30 March 2011 16:19 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 4D9E03A6B8F for <>; Wed, 30 Mar 2011 09:19:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.539
X-Spam-Status: No, score=-3.539 tagged_above=-999 required=5 tests=[AWL=0.060, BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id wWGPaPFrQhHI for <>; Wed, 30 Mar 2011 09:19:31 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id 14ECC3A6B8B for <>; Wed, 30 Mar 2011 09:19:30 -0700 (PDT)
Received: by fxm15 with SMTP id 15so1318649fxm.31 for <>; Wed, 30 Mar 2011 09:21:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=GXM1piMtopdnpRs2I8cf+GXo9n6D43IfPP+JYue3gmw=; b=LTcPQgPIddhuEJHywssCk7cwlqkj5gvULgBg8Ol2TRZP2C4D4rkIkG0KNytEzJduAp mA34hmSASJbZ0YCpNBIqn98iCteh/T33833cYpfO0m34xYI+TcTlIIvXc/khIrEEI45G n14O+KYYel1LW1uMFiFjnllQb8oO2OY26k2wg=
DomainKey-Signature: a=rsa-sha1; c=nofws;; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=F0rFAV492+o+/bf0ODku5K8iH6u7PeE2JhR0tOkvxnQp1GAoUjPeR6czXjt7rePB3u 145tGY4ENWYOnsRx+vZzDQ+1Aw5fBGJ5gXkjM6zeo++/eVEkFQY0QkxrWA1bIRna07jV sXqr9/tIf4V2MZ6v99+kMXgRHubLGXQY0FRkI=
MIME-Version: 1.0
Received: by with SMTP id l9mr1528304fal.25.1301502069504; Wed, 30 Mar 2011 09:21:09 -0700 (PDT)
Received: by with HTTP; Wed, 30 Mar 2011 09:21:09 -0700 (PDT)
In-Reply-To: <a06240800c9b8ccb5485c@>
References: <> <a06240800c9b78d52751f@> <a06240804c9b79c870558@> <a06240809c9b7b7143e51@> <3B987BF13718424BBA818C248C428E64@local> <a06240800c9b7c543104f@> <A5D8841CEB8F4BF9A007C8B6408C363C@local> <a06240801c9b7d3b57307@> <> <a06240800c9b8ccb5485c@>
Date: Wed, 30 Mar 2011 12:21:09 -0400
Message-ID: <>
From: Brian Dickson <>
To: Edward Lewis <>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: quoted-printable
Subject: Re: [dnsext] bitmap inference was Re: ... - NXDOMAIN for emptynon-terminals
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: DNS Extensions working group discussion list <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 30 Mar 2011 16:19:32 -0000

On Wed, Mar 30, 2011 at 8:10 AM, Edward Lewis <> wrote:
> It's going to happen.  Even if we throw out the "tailored responses" issue,
> there's the element of time.  Although the DNS protocol does not integrate
> time into the data model, there's the real world that does.  Zones get
> updated and reloaded, so a cache will have to deal with inconsistent NSEC/3
> bitmaps.

It might be worth discussing how caches could/should handle NSEC/3
responses when time and/or bitmaps change.

The idea is, to find a happy balance between caching NSEC/3 responses,
associating those with bitmap bits, and limiting cache bloat.

When a cache has no entry for a given tuple (name, class, type),
obviously it has to then query the auth server. If it gets an answer
where the name exists but type doesn't, it should get an NSEC/3 record
as well.

The cache should only return that cached NSEC/3 when it sees queries
that match already-answered (by the auth server) queries, and new
types should result in new queries to the auth server.

The questions that arise are:
- What if the same NSEC/3 answer is returned for the new type?
- What if a different NSEC/3 answer is returned, but which is
consistent with previous NSEC/3 answer(s) already cached for other
- What if a different NSEC/3 answer is returned, but which is not
consistent with previous NSEC/3 answer(s) already cached for other

My suspicion is that:
- It would be reasonable to keep a bitmap of queries/answers for which
a given NSEC/3 has been returned. E.g. If the NSEC/3 has bits clear
on, for example, SOA and NS, and has been returned along with empty
data on queries for SOA and NS for a given name and class, then it
would be reasonable to associate the same NSEC/3 with those types, and
return it for subsequent queries for those tuples.
- It would be reasonable to replace older NSEC/3 answers with newer
NSEC/3 answers, if the type associations (of previous queries/answers
that generated the cached entry) and bitmap of the newer NSEC/3 were
consistent (and thus also implicitly consistent with the bitmap of the
older NSEC/3)
- It would be necessary to retain multiple NSEC/3 answers if there
were inconsistencies between types and bitmaps across those answers

The benefit is, even if the time changes, if the bitmap doesn't
change, or doesn't change in a manner that is inconsistent, that the
number of NSEC/3 records doesn't have to increase, even if additional
queries to the auth server are needed because the particular type's
NSEC/3 hasn't been cached (or associated with the cached entry yet).

A secondary benefit is that a rolling window of TTLs resulting in
refreshing of NSEC/3's rather than expiry of NSEC/3's, can have some
beneficial effect on the auth server(s) without introducing
inconsistencies. A newer NSEC/3 (with newer signature) essentially
restarts the TTL clock when it replaces the older NSEC/3.

Or, the cache could decide to re-query candidate NSEC/3 records for
the types with the older NSEC/3 entries, and only if the new NSEC/3 is
returned, do the replacement. It is a time/space/bandwidth trade-off.