Subject: RE: nsec++

From: "Andrew Draper" <[email-masked]>
Date: Thu, 4 Dec 2003 16:22:41 -0000

Roy,

The algorithm for calculating the smallest RR is very simple.  It's something like this:

next = 0;
while (there are types with a value >= next)
{
	start = first active type with a value of next or more
	start = start - (start % 32); // round down to multiple of 32

	Create a temporary bitmap containing all types from start to start + 255
	length = 32

	Trim zero octets off the end of the bitmap, reducing length as you do

	Look for three consecutive zeros in the bitmap, at byte offsets 1, 5, 9 etc.
	If you find one then set the length of the bitmap to the address at which
      you found it.

	Output the bitmap, specifying the start address and the length.
	next = start + length * 8
}

I could write it in real C, but I'm sure you get the idea.  Of course the algorithm above could be optimised for processing time.

This looks like a trivial piece of code to me, it certainly isn't discrete mathematics.

If small RRDATA size isn't considered important then I'll shut up, but my experience is that one of the things holding DNSSEC back is that users think it causes enormous increases in packet size.  Putting a bit of thought into saving some bytes seems worth it to me.

Regards,
    Andy

> -----Original Message-----
> From: Roy Arends [mailto:[email-masked]]
> Sent: 04 December 2003 16:02
> To: Andrew Draper
> Cc: Jakob Schlyter; IETF DNSEXT WG
> Subject: RE: nsec++ 
> 
> 
> On Thu, 4 Dec 2003, Andrew Draper wrote:
> 
> > Roy,
> >
> > I think the maximum size of my encoding is the same as the 
> one specified
> > in version 0 of the draft.  Use 256 blocks, each 34 octets 
> long, gives
> > 8704 octets total.
> >
> > All I suggest changing is to allow the start value of each 
> block to be
> > on a multiple of 32 instead of a multiple of 256.
> 
> So the worst case scenario would not be that different. The 
> 'multiplier'
> would now be 32 instead of 256, where you'd have a special graph-like
> algortihm to determine the most optimized presentation.
> 
> You'd have to calculate all possible encodings to determine 
> which one is
> the shortest.
> 
> I don't think RDATA size is really that important to allow 
> for discrete
> mathematics to determine the shortest representation.
> 
> The current one (nsec++) satisfies all requirements. Yours adds
> complexity.
> 
> Roy
> 

--
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: [email-masked]
Date: Fri, 05 Dec 2003 08:09:25 +1100

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 next the next 32 bit window is active include in in the
	current bitmap otherwise the current bitmap is complete.
	Repeat adding 32 bit windows until the bitmap is 256 bits long.
	
	Repeat until all types are accounted for.

	Mark

> I could write it in real C, but I'm sure you get the idea.  Of course the alg
> orithm above could be optimised for processing time.
> 
> If small RRDATA size isn't considered important then I'll shut up, but my exp
> erience is that one of the things holding DNSSEC back is that users think it 
> causes enormous increases in packet size.  Putting a bit of thought into savi
> ng some bytes seems worth it to me.
> 
> Regards,
>     Andy
> 
> 
> 
> 
--
Mark Andrews, Internet Software Consortium
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Rob Austein <[email-masked]>
Date: Thu, 04 Dec 2003 16:34:34 -0500

No offense to Andrew, but my unnecessary complexity meter was reading
yellowish green when the WG decided to go with windowed bitmaps, and
today's discussion of algorithms by which one might determine the most
compact among multiple possible encodings kicks it up into the orange.

---

From: [email-masked]
Date: Fri, 05 Dec 2003 10:07:01 +1100

> compact among multiple possible encodings kicks it up into the orange.

	"Choose the most compact" was never going to fly without
	a differentiator between identically compact results.

	I do however thing that you can describe a algorithm which
	will alway produce the mimimal size and same encoding with
	sliding 256 bit windows.
 
	The second description I sent out is not much more difficult
	to encode / verify than the plain 256 bit window scheme.

	Mark