contrib/bind9/doc/rfc/rfc2673.txt

   1
   2
   3
   4
   5
   6
   7 Network Working Group                                        M. Crawford
   8 Request for Comments: 2673                                      Fermilab
   9 Category: Standards Track                                    August 1999
  10
  11
  12                 Binary Labels in the Domain Name System
  13
  14 Status of this Memo
  15
  16    This document specifies an Internet standards track protocol for the
  17    Internet community, and requests discussion and suggestions for
  18    improvements.  Please refer to the current edition of the "Internet
  19    Official Protocol Standards" (STD 1) for the standardization state
  20    and status of this protocol.  Distribution of this memo is unlimited.
  21
  22 Copyright Notice
  23
  24    Copyright (C) The Internet Society (1999).  All Rights Reserved.
  25
  26 1.  Introduction and Terminology
  27
  28    This document defines a "Bit-String Label" which may appear within
  29    domain names.  This new label type compactly represents a sequence of
  30    "One-Bit Labels" and enables resource records to be stored at any
  31    bit-boundary in a binary-named section of the domain name tree.
  32
  33    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
  34    "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
  35    document are to be interpreted as described in [KWORD].
  36
  37 2.  Motivation
  38
  39    Binary labels are intended to efficiently solve the problem of
  40    storing data and delegating authority on arbitrary boundaries when
  41    the structure of underlying name space is most naturally represented
  42    in binary.
  43
  44 3.  Label Format
  45
  46    Up to 256 One-Bit Labels can be grouped into a single Bit-String
  47    Label.  Within a Bit-String Label the most significant or "highest
  48    level" bit appears first.  This is unlike the ordering of DNS labels
  49    themselves, which has the least significant or "lowest level" label
  50    first.  Nonetheless, this ordering seems to be the most natural and
  51    efficient for representing binary labels.
  52
  53
  54
  55
  56
  57
  58 Crawford                    Standards Track                     [Page 1]
  59 \f
  60 RFC 2673        Binary Labels in the Domain Name System      August 1999
  61
  62
  63    Among consecutive Bit-String Labels, the bits in the first-appearing
  64    label are less significant or "at a lower level" than the bits in
  65    subsequent Bit-String Labels, just as ASCII labels are ordered.
  66
  67 3.1.  Encoding
  68
  69       0                   1                   2
  70       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2     . . .
  71      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-//+-+-+-+-+-+-+
  72      |0 1|    ELT    |     Count     |           Label ...         |
  73      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+//-+-+-+-+-+-+-+
  74
  75    (Each tic mark represents one bit.)
  76
  77
  78    ELT       000001 binary, the six-bit extended label type [EDNS0]
  79              assigned to the Bit-String Label.
  80
  81    Count     The number of significant bits in the Label field.  A Count
  82              value of zero indicates that 256 bits are significant.
  83              (Thus the null label representing the DNS root cannot be
  84              represented as a Bit String Label.)
  85
  86    Label     The bit string representing a sequence of One-Bit Labels,
  87              with the most significant bit first.  That is, the One-Bit
  88              Label in position 17 in the diagram above represents a
  89              subdomain of the domain represented by the One-Bit Label in
  90              position 16, and so on.
  91
  92              The Label field is padded on the right with zero to seven
  93              pad bits to make the entire field occupy an integral number
  94              of octets.  These pad bits MUST be zero on transmission and
  95              ignored on reception.
  96
  97    A sequence of bits may be split into two or more Bit-String Labels,
  98    but the division points have no significance and need not be
  99    preserved.  An excessively clever server implementation might split
 100    Bit-String Labels so as to maximize the effectiveness of message
 101    compression [DNSIS].  A simpler server might divide Bit-String Labels
 102    at zone boundaries, if any zone boundaries happen to fall between
 103    One-Bit Labels.
 104
 105 3.2.  Textual Representation
 106
 107    A Bit-String Label is represented in text -- in a zone file, for
 108    example -- as a <bit-spec> surrounded by the delimiters "\[" and "]".
 109    The <bit-spec> is either a dotted quad or a base indicator and a
 110    sequence of digits appropriate to that base, optionally followed by a
 111
 112
 113
 114 Crawford                    Standards Track                     [Page 2]
 115 \f
 116 RFC 2673        Binary Labels in the Domain Name System      August 1999
 117
 118
 119    slash and a length.  The base indicators are "b", "o" and "x",
 120    denoting base 2, 8 and 16 respectively.  The length counts the
 121    significant bits and MUST be between 1 and 32, inclusive, after a
 122    dotted quad, or between 1 and 256, inclusive, after one of the other
 123    forms.  If the length is omitted, the implicit length is 32 for a
 124    dotted quad or 1, 3 or 4 times the number of binary, octal or
 125    hexadecimal digits supplied, respectively, for the other forms.
 126
 127    In augmented Backus-Naur form [ABNF],
 128
 129      bit-string-label =  "\[" bit-spec "]"
 130
 131      bit-spec         =  bit-data [ "/" length ]
 132                        / dotted-quad [ "/" slength ]
 133
 134      bit-data         =  "x" 1*64HEXDIG
 135                        / "o" 1*86OCTDIG
 136                        / "b" 1*256BIT
 137
 138      dotted-quad      =  decbyte "." decbyte "." decbyte "." decbyte
 139
 140      decbyte          =  1*3DIGIT
 141
 142      length           =  NZDIGIT *2DIGIT
 143
 144      slength          =  NZDIGIT [ DIGIT ]
 145
 146      OCTDIG           =  %x30-37
 147
 148      NZDIGIT          =  %x31-39
 149
 150    If a <length> is present, the number of digits in the <bit-data> MUST
 151    be just sufficient to contain the number of bits specified by the
 152    <length>.  If there are insignificant bits in a final hexadecimal or
 153    octal digit, they MUST be zero.  A <dotted-quad> always has all four
 154    parts even if the associated <slength> is less than 24, but, like the
 155    other forms, insignificant bits MUST be zero.
 156
 157    Each number represented by a <decbyte> must be between 0 and 255,
 158    inclusive.
 159
 160    The number represented by <length> must be between 1 and 256
 161    inclusive.
 162
 163    The number represented by <slength> must be between 1 and 32
 164    inclusive.
 165
 166
 167
 168
 169
 170 Crawford                    Standards Track                     [Page 3]
 171 \f
 172 RFC 2673        Binary Labels in the Domain Name System      August 1999
 173
 174
 175    When the textual form of a Bit-String Label is generated by machine,
 176    the length SHOULD be explicit, not implicit.
 177
 178 3.2.1.  Examples
 179
 180    The following four textual forms represent the same Bit-String Label.
 181
 182                              \[b11010000011101]
 183                              \[o64072/14]
 184                              \[xd074/14]
 185                              \[208.116.0.0/14]
 186
 187    The following represents two consecutive Bit-String Labels which
 188    denote the same relative point in the DNS tree as any of the above
 189    single Bit-String Labels.
 190
 191                              \[b11101].\[o640]
 192
 193 3.3.  Canonical Representation and Sort Order
 194
 195    Both the wire form and the text form of binary labels have a degree
 196    of flexibility in their grouping into multiple consecutive Bit-String
 197    Labels.  For generating and checking DNS signature records [DNSSEC]
 198    binary labels must be in a predictable form.  This canonical form is
 199    defined as the form which has the fewest possible Bit-String Labels
 200    and in which all except possibly the first (least significant) label
 201    in any sequence of consecutive Bit-String Labels is of maximum
 202    length.
 203
 204    For example, the canonical form of any sequence of up to 256 One-Bit
 205    Labels has a single Bit-String Label, and the canonical form of a
 206    sequence of 513 to 768 One-Bit Labels has three Bit-String Labels of
 207    which the second and third contain 256 label bits.
 208
 209    The canonical sort order of domain names [DNSSEC] is extended to
 210    encompass binary labels as follows.  Sorting is still label-by-label,
 211    from most to least significant, where a label may now be a One-Bit
 212    Label or a standard (code 00) label.  Any One-Bit Label sorts before
 213    any standard label, and a 0 bit sorts before a 1 bit.  The absence of
 214    a label sorts before any label, as specified in [DNSSEC].
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226 Crawford                    Standards Track                     [Page 4]
 227 \f
 228 RFC 2673        Binary Labels in the Domain Name System      August 1999
 229
 230
 231    For example, the following domain names are correctly sorted.
 232
 233                          foo.example
 234                          \[b1].foo.example
 235                          \[b100].foo.example
 236                          \[b101].foo.example
 237                          bravo.\[b10].foo.example
 238                          alpha.foo.example
 239
 240 4.  Processing Rules
 241
 242    A One-Bit Label never matches any other kind of label.  In
 243    particular, the DNS labels represented by the single ASCII characters
 244    "0" and "1" do not match One-Bit Labels represented by the bit values
 245    0 and 1.
 246
 247 5.  Discussion
 248
 249    A Count of zero in the wire-form represents a 256-bit sequence, not
 250    to optimize that particular case, but to make it completely
 251    impossible to have a zero-bit label.
 252
 253 6.  IANA Considerations
 254
 255    This document defines one Extended Label Type, termed the Bit-String
 256    Label, and requests registration of the code point 000001 binary in
 257    the space defined by [EDNS0].
 258
 259 7.  Security Considerations
 260
 261    All security considerations which apply to traditional ASCII DNS
 262    labels apply equally to binary labels.  he canonicalization and
 263    sorting rules of section 3.3 allow these to be addressed by DNS
 264    Security [DNSSEC].
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282 Crawford                    Standards Track                     [Page 5]
 283 \f
 284 RFC 2673        Binary Labels in the Domain Name System      August 1999
 285
 286
 287 8.  References
 288
 289    [ABNF]   Crocker, D. and P. Overell, "Augmented BNF for Syntax
 290             Specifications: ABNF", RFC 2234, November 1997.
 291
 292    [DNSIS]  Mockapetris, P., "Domain names - implementation and
 293             specification", STD 13, RFC 1035, November 1987.
 294
 295    [DNSSEC] Eastlake, D., 3rd, C. Kaufman, "Domain Name System Security
 296             Extensions", RFC 2065, January 1997
 297
 298    [EDNS0]  Vixie, P., "Extension mechanisms for DNS (EDNS0)", RFC 2671,
 299             August 1999.
 300
 301    [KWORD]  Bradner, S., "Key words for use in RFCs to Indicate
 302             Requirement Levels," BCP 14, RFC 2119, March 1997.
 303
 304 9.  Author's Address
 305
 306    Matt Crawford
 307    Fermilab MS 368
 308    PO Box 500
 309    Batavia, IL 60510
 310    USA
 311
 312    Phone: +1 630 840-3461
 313    EMail: crawdad@fnal.gov
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338 Crawford                    Standards Track                     [Page 6]
 339 \f
 340 RFC 2673        Binary Labels in the Domain Name System      August 1999
 341
 342
 343 10.  Full Copyright Statement
 344
 345    Copyright (C) The Internet Society (1999).  All Rights Reserved.
 346
 347    This document and translations of it may be copied and furnished to
 348    others, and derivative works that comment on or otherwise explain it
 349    or assist in its implementation may be prepared, copied, published
 350    and distributed, in whole or in part, without restriction of any
 351    kind, provided that the above copyright notice and this paragraph are
 352    included on all such copies and derivative works.  However, this
 353    document itself may not be modified in any way, such as by removing
 354    the copyright notice or references to the Internet Society or other
 355    Internet organizations, except as needed for the purpose of
 356    developing Internet standards in which case the procedures for
 357    copyrights defined in the Internet Standards process must be
 358    followed, or as required to translate it into languages other than
 359    English.
 360
 361    The limited permissions granted above are perpetual and will not be
 362    revoked by the Internet Society or its successors or assigns.
 363
 364    This document and the information contained herein is provided on an
 365    "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
 366    TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
 367    BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
 368    HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
 369    MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
 370
 371 Acknowledgement
 372
 373    Funding for the RFC Editor function is currently provided by the
 374    Internet Society.
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394 Crawford                    Standards Track                     [Page 7]
 395 \f