DNSIND Working Group Matt Crawford Internet Draft Fermilab March 9, 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 Rim). 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", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 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 September 14, 1998 Crawford [Page 1] Internet Draft Binary DNS Labels March 9, 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 [UNK] 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 September 14, 1998 Crawford [Page 2] Internet Draft Binary DNS Labels March 9, 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 surrounded by the delimiters "\[" and "]". The 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 is present, the number of digits in the MUST be just sufficient to contain the number of bits specified by Expires September 14, 1998 Crawford [Page 3] Internet Draft Binary DNS Labels March 9, 1998 the . If there are insignificant bits in a final hexadecimal or octal digit, they MUST be zero. A always has all four parts even if the associated is less than 24, but, like the other forms, insignificant bits MUST be zero. Each number represented by a must be between 0 and 255, inclusive. The number represented by must be between 1 and 256 inclusive. The number represented by must be between 1 and 32 inclusive. 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 Label. \[b11010000011101] \[o64072/14] \[xd074/14] \[208.116.0.0/14] 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. \[b11101/5].\[o640] 3.3. Canonical Representation and Sort Order Both the wire form and the text form of binary labels have a degree of flexibility in their group into multiple consecutive Bit-String Labels. For generating and checking DNS signature records [DNSSEC] binary labels must be in a predictable form. This canonical form is defined as the form which has the fewest possible Bit-String Labels and in which all except possibly the first (least significant) label in any sequence of consecutive Bit-String Labels is of maximum length. For example, the canonical form of any sequence of up to 256 One-Bit Expires September 14, 1998 Crawford [Page 4] Internet Draft Binary DNS Labels March 9, 1998 Labels has a single Bit-String Label, and the canonical form of a sequence of 513 to 768 One-Bit Labels has three Bit-String Labels of which the second and third contain 256 label bits. The canonical sort order of domain names [DNSSEC] is extended to encompass binary labels as follows. Sorting is still label-by- label, from most to least significant, where a label may now be a One-Bit Label or a standard (code 00) label. Any One-Bit Label sorts before any standard label, and a 0 bit sorts before a 1 bit. The absence of a label, as specified in [DNSSEC], sorts before any label. For example, the following domain names are correctly sorted. foo.tld \[b1].foo.tld \[b100].foo.tld \[b101].foo.tld bar.\[b10].foo.tld baz.foo.tld 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. 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 \[b1011].foo.\[b0011].example Has exactly four binary ancestors, which are, from nearest to farthest, Expires September 14, 1998 Crawford [Page 5] Internet Draft Binary DNS Labels March 9, 1998 \[b101].foo.\[b0011].example \[b10].foo.\[b0011].example \[b1].foo.\[b0011].example foo.\[b0011].example 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 CNAME. 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). 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. I expect 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. Expires September 14, 1998 Crawford [Page 6] Internet Draft Binary DNS Labels March 9, 1998 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. [DNSSEC]D. Eastlake, 3rd, C. Kaufman, "Domain Name System Security Extensions", RFC 2065. [KWORD] S. Bradner, "Key words for use in RFCs to Indicate Requirement Levels," RFC 2119. [UNK] P. Vixie, Work in progress. 8. Author's Address Matt Crawford Fermilab MS 368 PO Box 500 Batavia, IL 60510 USA Phone: +1 630 840-3461 EMail: crawdad@fnal.gov Expires September 14, 1998 Crawford [Page 7]