Subject: Re: nsec++

From: [email-masked]
Date: Sat, 06 Dec 2003 09:48:54 +1100

> At 05:45 2003-12-05, Andrew Draper wrote:
> 
> > >       In otherword start a new bitmap if you save more than the
> > >       cost of introducing a new bitmap.
> > >
> > >       If the last two octets of the current map are zero it is
> > >       a break even situation so you include the next 32 bit
> > >       window in the current map.
> >
> >This is exactly the algorithm I was intending to describe, both with my 
> >suggested set of MUSTs and with my pseudo-code.  Thanks for describing it 
> >in an easier to understand way.
> >
> >     Andy
> <chair hat off>
> 
> This algorithm only optimizes for space, it has serious penalty for
> searching now I add every 64´th type and you need to search linearly
> through 1024 blocs as you do not know before hand the size
> of any block.
> Is this tradeoff worth it?

	Worst case search has gone from 256 to 2048 blocks for a type
	in 65504-65535.  Bitmap size for worst number of blocks is 6144
	octets.

	You still have to perform a linear search as you need to find
	the right block.

	I suspect the optimisation however will pay off for the common
	cases.

	Zone APEX: 1 block/1 block
	A NS SOA MX RRSIG NSEC DNSKEY
	00 07 62 01 00 00 00 03 80
	00 07 62 01 00 00 00 03 80

	Typical host: 1 block/1 block
	A MX RRSIG NSEC
	00 06 40 01 00 00 00 03
	00 06 40 01 00 00 00 03

	Insecure delegation: 1 block/2 blocks
	A RRSIG NSEC
	00 06 20 00 00 00 00 03
	00 01 20 02 02 00 03

	Secure delegation: 1 block/2 block
	NS DS RRSIG NSEC
	00 06 20 00 00 00 00 13
	00 01 20 02 02 00 13
 
	IN-ADDR.ARPA/IP6.ARPA: 1 block/1 block
	PTR RRSIG NSEC
	00 06 00 08 00 00 00 03
	00 06 00 08 00 00 00 03

	SRV entry: 1 block/1 block
	SRV RRSIG NSEC
	00 06 00 00 00 00 40 03
	02 02 40 03

	TYPE1234: 2 blocks/2 blocks
	RRSIG NSEC TYPE1234
	00 06 00 00 00 00 00 03 04 1b 00 00 00 00 00 00 00 00 00 00
	00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 20

	02 02 00 03 04 c3 00 00 20

	TYPE65535: 2 blocks/2 blocks
	RRSIG NSEC TYPE65535
	00 06 00 00 00 00 00 03 ff 20 00 00 00 00 00 00 00 00 00 00
	00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
	00 01

	02 02 00 03 ff e4 00 00 00 01

> <chair hat on>
> Is this whole thread worth the effort when we have many
> more pressing issues like comment on the protocol document, check
> if the protocol documents reflect all the documents they are
> obsoleting/updating correctly ?
> 
>          Olafur
> 
> 
> 
--
Mark Andrews, Internet Software Consortium
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>