DNSIND Working Group                                       Matt Crawford
Internet Draft                                                  Fermilab
                                                       February 19, 1998

                  Binary Labels in the Domain Name System

Status of this Memo

    This document is an Internet Draft.  Internet Drafts are working
    documents of the Internet Engineering Task Force (IETF), its Areas,
    and its Working Groups.  Note that other groups may also distribute
    working documents as Internet Drafts.

    Internet Drafts are draft documents valid for a maximum of six
    months.  Internet Drafts may be updated, replaced, or obsoleted by
    other documents at any time.  It is not appropriate to use Internet
    Drafts as reference material or to cite them other than as a
    ``working draft'' or ``work in progress.''

    To learn the current status of any Internet-Draft, please check the
    ``1id-abstracts.txt'' listing contained in the Internet Drafts
    Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net
    (Europe), ftp.isi.edu (US  West  Coast), or munnari.oz.au (Pacific

    Distribution of this memo is unlimited.

1.  Introduction and Terminology

    This document defines a ''Bit-String Label'' which may appear within
    domain names.  This new label type compactly represents a sequence
    of ''One-Bit Labels'' and enables resource records to be stored at any
    bit-boundary in a binary-named section of the domain name tree.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
    document are to be interpreted as described in [KWORD].

2.  Motivation

    Binary labels are intended to efficiently solve the problem of
    storing data and delegating authority on arbitrary boundaries when
    the structure of underlying name space is most naturally represented
    in binary.  A new catch-all Additional Section processing rule

Expires August 24, 1998         Crawford                        [Page 1]

Internet Draft             Binary DNS Labels           February 19, 1998

    provides a form of longest-match lookup which is useful when the
    name space is like Internet addresses.

3.  Label Format

    Up to 256 One-Bit Labels can be grouped into a single Bit-String
    Label.  Within a Bit-String Label the most significant or "highest
    level" bit appears first.  This is unlike the ordering of DNS labels
    themselves, which has the least significant or "lowest level" label
    first.  Nonetheless, this ordering seems to be the most natural and
    efficient for representing binary labels.

    Among consecutive Bit-String Labels, the bits in the first-appearing
    label are less significant or "at a lower level" than the bits in
    subsequent Bit-String Labels, just as ASCII labels are ordered.

3.1.  Encoding

       0                   1                   2
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2     . . .
      |0 1|    ELC    |     Count     |           Label ...         |

    (Each tic mark represents one bit.)

    ELC       The six-bit Extended Label Code assigned to the Bit-String
              Label.  [TBA.  0?]

    Count     The number of significant bits in the Label field.  A
              Count value of zero indicates that 256 bits are
              significant.  (Thus the null label representing the DNS
              root cannot be represented as a Bit String Label.)

    Label     The bit string representing a sequence of One-Bit Labels,
              with the most significant bit first.  That is, the One-Bit
              Label in position 17 in the diagram above represents a
              subdomain of the domain represented by the One-Bit Label
              in position 16, and so on.

              The Label field is padded on the right with zero to seven
              pad bits to make the entire field occupy an integral
              number of octets.  These pad bits MUST be zero on
              transmission and ignored on reception.

Expires August 24, 1998         Crawford                        [Page 2]

Internet Draft             Binary DNS Labels           February 19, 1998

    A sequence of bits may be split into two or more Bit-String Labels,
    but the division points have no significance and need not be
    preserved.  An excessively clever server implementation might split
    Bit-String Labels so as to maximize the effectiveness of message
    compression [DNSIS].  A simpler server might divide Bit-String
    Labels at zone boundaries, if any zone boundaries happen to fall
    between One-Bit Labels.

3.2.  Textual Representation

    A Bit-String Label is represented in text -- in a zone file, for
    example -- as a <bit-spec> surrounded by the delimiters "\[" and
    "]".  The <bit-spec> is either a dotted quad or a base indicator and
    a sequence of digits appropriate to that base, optionally followed
    by a slash and a length.  The base indicators are "b", "o" and "x",
    denoting base 2, 8 and 16 respectively.  The length counts the
    significant bits and MUST be between 1 and 32, inclusive, after a
    dotted quad, or between 1 and 256, inclusive, after one of the other
    forms.  If the length is omitted, the implicit length is 32 for a
    dotted quad or 1, 3 or 4 times the number of binary, octal or
    hexadecimal digits supplied, respectively, for the other forms.

    In ABNF [ABNF],

      bit-string-label =  "\[" bit-spec "]"

      bit-spec         =  bit-data [ "/" length ]
                        / dotted-quad [ "/" slength ]

      bit-data         =  "x" 1*64HEXDIG
                        / "o" 1*86OCTDIG
                        / "b" 1*256BIT

      dotted-quad      =  decbyte "." decbyte "." decbyte "." decbyte

      decbyte          =  NZDIGIT *2DIGIT

      length           =  NZDIGIT *2DIGIT

      slength          =  NZDIGIT [ DIGIT ]

      OCTDIG           =  %x30-37

      NZDIGIT          =  %x31-39

    If a <length> is present, the number of digits in the <bit-data>
    MUST be just sufficient to contain the number of bits specified by

Expires August 24, 1998         Crawford                        [Page 3]

Internet Draft             Binary DNS Labels           February 19, 1998

    the <length>.  If there are insignificant bits in a final
    hexadecimal or octal digit, they MUST be zero.  A <dotted-quad>
    always has all four parts even if the associated <slength> is less
    than 24, but, like the other forms, insignificant bits MUST be zero.

    Each number represented by a <decbyte> must be between 0 and 255,

    The number represented by <length> must be between 1 and 256

    The number represented by <slength> must be between 1 and 32

    When the textual form of a Bit-String Label is generated by machine,
    the length SHOULD be explicit, not implicit.

3.2.1.  Examples

    The following four textual forms represent the same Bit-String


    The following represents two consecutive Bit-String Labels which
    denote the same relative place in the DNS tree as any of the above
    single Bit-String Labels.


4.  Processing Rules

    A One-Bit Label never matches any other kind of label.  In
    particular, the DNS labels represented by the single ASCII
    characters "0" and "1" do not match One-Bit Labels represented by
    the bit values 0 and 1.

    When an authoritative server processes a query which includes a
    Bit-String Label in the QNAME, a special "longest-match" processing
    rule is invoked in two cases.  The following definition will be
    helpful in explaining the longest-match rule.

Expires August 24, 1998         Crawford                        [Page 4]

Internet Draft             Binary DNS Labels           February 19, 1998

    A "binary ancestor" of a given domain name "D" is another domain
    name "A" which is a suffix of D obtainable by removing one or more
    least-significant One-Bit Labels from D.  Among several binary
    ancestors of D which satisfy a certain condition, the "nearest
    binary ancestor" is that binary ancestor which is obtained by
    removing the fewest One-Bit Labels from D.

    As an example, the domain name


    Has exactly four binary ancestors, which are, from nearest to


    The first case in which the longest-match rule MUST be invoked is
    when a match to the QNAME becomes impossible at a certain One-Bit
    Label (that is, the algorithm of RFC1034's section 4.3.2 reaches
    step 3.c. [DNSCF]), and the "*" label does not exist at that point.
    Let Q1 be the label at which the match to QNAME became impossible,
    and let Q2 be the nearest binary ancestor of Q1 which has an RRs
    which match QTYPE.  The server MUST copy those RRs from Q2 to the
    Additional Section of the reply.  The RCODE is set as in RFC1034: to
    Name Error if the failing QNAME is the name from the original query,
    or to No Error if the failing QNAME was obtained by following a

    The second case of application of the longest-match rule is when the
    whole of QNAME is matched (step 3.a. of the above-referenced
    algorithm), but no RRs are present which match the QTYPE.  Again,
    RRs which match QTYPE MUST copied from the nearest binary ancestor
    which has such RRs to the Additional Section of the reply.  The
    RCODE MUST be set to No Error.

    In both cases, if the server reaches a zone boundary before finding
    a suitable binary ancestor, it MUST copy the SOA record of the zone
    to the additional section.  If and only if the server is
    authoritative for the parent zone also, then it MAY continue
    searching for the nearest binary ancestor in the parent zone.  If
    appropriate RRs are found at a binary ancestor in an ancestor zone,
    they MUST be placed after the SOA record(s) of the lower zone(s).

Expires August 24, 1998         Crawford                        [Page 5]

Internet Draft             Binary DNS Labels           February 19, 1998

5.  Discussion

    A Count of zero in the wire-form represents a 256-bit sequence, not
    to optimize that particular case, but to make it completely
    impossible to have a zero-bit label.  The only sensible meaning I
    can attach to a zero-bit label is a synonym for the DNS root, and
    such a thing must not exist.  (IMHO, of course.)  This point is not
    universally agreed.

    It is expected that the primary use of the "*" label below a One-Bit
    Label will be to block the action of the longest-match rule.

    Paul Vixie is preparing a draft defining what I have tentatively
    called "extended label codes" in section 3.1..

    Does the longest-match rule need examples?  Motivation?

6.  Acknowledgments

    Jerry Scharf suggested the backslash, which was an improvement over
    my very lame initial notation.  Paul Vixie suggested that the
    dotted-quad notation be supported.  They should not be assumed to
    support every choice represented in this draft, however.

7.  References

    [ABNF]  D. Crocker, Ed., P. Overell, "Augmented BNF for Syntax
            Specifications: ABNF", RFC 2234.

    [DNSCF] P.V. Mockapetris, "Domain names - concepts and facilities",
            RFC 1034.

    [DNSIS] P.V. Mockapetris, "Domain names - implementation and
            specification", RFC 1035.

    [KWORD] S. Bradner, "Key words for use in RFCs to Indicate
            Requirement Levels," RFC 2119.

Expires August 24, 1998         Crawford                        [Page 6]

Internet Draft             Binary DNS Labels           February 19, 1998

8.  Author's Address

    Matt Crawford
    Fermilab MS 368
    PO Box 500
    Batavia, IL 60510

    Phone: +1 630 840-3461

    EMail: crawdad@fnal.gov

Expires August 24, 1998         Crawford                        [Page 7]