Subject: RE: nsec++

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

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.

Regards,
    Andy

> -----Original Message-----
> From: Roy Arends [mailto:[email-masked]]
> Sent: 04 December 2003 15:02
> To: Andrew Draper
> Cc: Jakob Schlyter; IETF DNSEXT WG
> Subject: RE: nsec++ 
> 
> 
> On Thu, 4 Dec 2003, Andrew Draper wrote:
> 
> > Hi,
> >
> > While not wishing to reopen (too much) the debate about how 
> to encode
> > this efficiently, I have a suggestion which might make the 
> encoding of
> > sparse NSEC records a lot smaller, while being only 
> slightly harder to
> > understand and I think no harder to implement.
> >
> > If the types encoded are sparse then the bitmaps will tend 
> to have a lot
> > of zeros at the start of them.  For example the RDATA for:
> >
> > example.com. IN NSEC host.example.com. 385
> >
> > will be encoded as, I think:
> >
> >       04 'h' 'o' 's' 't'  06 'e' 'x' 'a' 'm' 'p' 'l' 'e'  
> 03 'c' 'o' 'm'  00
> >       01 11  00 00 00 00  00 00 00 00  00 00 00 00  00 00 00 00  02
> >       (all numbers are in hex)
> >
> > which has a lot of superfluous zeros.
> >
> > There are three bits spare in the "bitmap length" byte (if 
> you store bitmap_length-1 instead of just bitmap_length) so 
> it would be much more efficient, for sparse bitmaps, if the 
> block start was allowed to be on any boundary of 32.
> >
> > The encoding of the same RR would then be:
> >
> >       04 'h' 'o' 's' 't'  06 'e' 'x' 'a' 'm' 'p' 'l' 'e'  
> 03 'c' 'o' 'm'  00
> >       0C 00  02
> >
> >
> > If you like this then suggested text is below (I wrote this 
> yesterday so some of the alternative suggested descriptions 
> of bitmap might be better than this one):
> >
> >
> >    The type space is represented using one or more blocks.  
> Each block
> >    starts at a location in type space which is a multiple of 32 and
> >    describes upto 256 active types.  Each block consists of a 13 bit
> >    start type number, a 5 bit length field (from 1 .. 32 octets) and
> >    a bitmap (covering upto 256 type codes) in network bit order
> >    (similar to NXT).
> 
> One of the design requirements, and therefor one of the reasons some
> proposals did not make it is that the bit map must be able to 
> respresent
> every type in one bitmap.
> 
> Your encoding gives us a worst case length of 69632 which is >64K
> 
> 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: Roy Arends <[email-masked]>
Date: Thu, 4 Dec 2003 17:01:37 +0100 (CET)

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