Subject: RE: nsec++

From: "Andrew Draper" <[email-masked]>
Date: Fri, 5 Dec 2003 10:45:39 -0000

> > 	If you want to start at 32 bit boundraries you stop the
> > 	current bitmap if you have a 32 bit subwindow that is all
> > 	zeros.
> > 	
> > 	It takes 4 octets to represent a empty 32 bit subwindow.
> > 	It takes 2 octets to start a new window.
> > 
> > 	The algorithm would be:
> > 
> 	Find the first/next active 32 bit window.  If the last three
> 	octets of this 32 bit window are zero the bitmap is complete,
> 	remove trailing zero octets.  If the next the next 32 bit
> 	window is active include in in the current bitmap otherwise
> 	the current bitmap is complete, remove trailing zero octets.
> 	If the last three octets of this 32 bit window are zero the
> 	current bitmap is complete, remove trailing zero octets.
> 	Repeat adding 32 bit windows until the bitmap is 256 bits
> 	long.
>  	
>  	Repeat until all types are accounted for.
> 
> 	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

--
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/>

---

From: Ólafur Guðmundsson<[email-masked]>
Date: Fri, 05 Dec 2003 11:36:55 -0500

At 05:45 2003-12-05, Andrew Draper wrote:

>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?

<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

---

From: Paul Vixie <[email-masked]>
Date: 05 Dec 2003 18:22:49 +0000

> <chair hat off> This algorithm only optimizes for space, it has serious
> penalty for searching now I add every 64=B4th 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?

when i participated in the discussions with michael graff that led to his
draft on this topic, these other alternatives were considered and dropped.
i now realize that it was foolish of us to not document the roads untaken.

> <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 ?

the community now embodied by DNSEXT (but previously DNSIND et al) has a
rather poor record when it comes to measuring importance.  18 months ago we
made the decision not to complicate the NXT format with support for n>128
type codes since it would delay deployment.  16 months later we decided
that it wasn't reasonable to go to proposed standard without that support.

let's do this:  let the debate rage on.  let the people who are interested
in this topic discuss it.  let the draft author judge consensus for now.
when it's time to roll out the next -bis docset then the then-current draft
will be frozen and incorporated.

let's not do this:  let leadership mean deciding what (not) to discuss.
-- 
Paul Vixie

---

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

> 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

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

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Thu, 11 Dec 2003 16:21:07 +0100

> let's not do this:  let leadership mean deciding what (not) to discuss.

Well eh... leadership... who me ?  ;-)

Given that I have not seen major support on the list in favour of
'more compression', few people worried about additional comlexity and
we really need to get this done I propose to keep the document with
the specification as is and go for last call early next week.

If you have editorial issues please mail them to Jakob ASAP, maybe 
we can do another document roll.

-- Olaf

---------------------------------| Olaf M. Kolkman
---------------------------------| RIPE NCC