[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: nsec++
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 namedroppers-request@ops.ietf.org with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>