Subject: RE: nsec++

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

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).

   Blocks with no types present MUST NOT be included.  Blocks MUST NOT
   overlap.  There MUST NOT be more than three leading zero octets in
   the bitmap.  Trailing zero octets in the bitmap MUST be removed.  
   Blocks MUST be presented in increasing numerical order.

   Where two encodings are possible, the encoding which produces the
   smallest RRDATA size MUST be chosen.  If two encodings produce the
   same RRDATA size then the one which uses the smallest number of
   blocks MUST be chosen.

        [ This last rule is required to handle edge cases such as
            NSEC host.example.com. 256 511   
          or
            NSEC host.example.com. 264 288 
          An alternative would be to say "The start type of a
          block MUST be 256 or more greater than the start
          address of the previous block" but this is less efficient ]

   The format of each block is as shown below:

                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   /     Start Type      | Length  |    Bitmap of active types     /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   /             Bitmap of active types (continued) ...            
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The Start Type field indicates the numeric value of the first bit
   represented in the bitmap.  The least significant 5 bits are always
   zero and are not stored in the RR.  A value of 1 in this field
   indicates that the first bit in the bitmap represents type 32, a
   value of 1024 indicates that the first bit represents type 32768.

   The Length field holds the number of octet in the bitmap of active
   types, minus 1.  A value of 0 in this field therefore indicates
   that the bitmap is one octet long, a value of 31 indicates that the
   bitmap is 32 octets.

   The Bitmap field is divided up into octets, one for each type.
   The presence of the first type is indicated by the least significant
   bit in the first octet, the next type by the second least significant
   bit etc.  The second octet (if present) indicates the presence of
   the 9th to 16th types etc.

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