wiki:AuthServerQueryLogic

Authoritative Query Logic

The authoritative-only server algorithm is:

  1. If QTYPE is DS, search the available zones for the zone which is the nearest ancestor to QNAME's parent,go to step 1.1.Otherwise search the available zones for the zone which is the nearest ancestor to QNAME. If such a zone is found, set the AA bit in the reply and continue to step 2. If the zone is not found, then:
    1. If we were looking up the target of a previously-discovered CNAME, set Rcode to NOERROR and exit.
    2. If we were looking up the original QNAME of the query, set Rcode to REFUSED and exit.

1.1. If such a zone is found:

  1. If an RRset matching QTYPE is found, add it and it's RRSIG to the answer section, then add the NS records for the enclosing zone to the authority section. Go to step 7.
  2. If thus RRset is not found, if zone is secure and support NSEC, go to 1.1.a,if zone is secure and support NSEC3, go to 1.1.b,else go to step 6. 1.1.a. Add the SOA of the zone and it's RRSIG to the authority section,and the NSSEC RR that covered the QNAME and it's RRSIG to the authority section. 1.1.a. Add the SOA of the zone and it's RRSIG to the authority section,and the NSSEC3 RR that covered the QNAME and it's RRSIG to the authority section.
  1. Determine whether we are authoritative for QNAME.
    1. If the number of labels in QNAME is equal to the number of labels in the enclosing zone name, we are authoritative; go to step 3.
    2. If the difference between the number of labels in the enclosing zone and the number of labels in QNAME is greater than zero, then check each intermediate node starting immediately below the enclosing zone and continuing down to QNAME, checking for NS, DS, or DNAME records. If any NS records are found, this is a referral: go to step 2c. If any DNAME records are found, go to step 5. If no NS or DNAME records are found, go to step 3.
    3. If we were looking up the original QNAME of the query, clear the AA bit in the reply. Place the NS records for the subzone into the authority section of the reply. check whether a DS record was found, if so, add ds and its signatures to authority secion, else if the zone is secured and support nsec, go to 2.c.Ⅰ;else if the zone is secured and support nsec3 goto 2.c.Ⅱ; else, go to setp7. 2.c.1. Add nsec rr(MUST be exist) and its signautre matching the delegation ns name to authority section. 2.c.2. If the nsec3 rr matching the delegation ns name exists, add it and its signatures to authority section; else(no matching nsec3 rr), the delegated zone must be OPT-OUT, add covered nsec3 rr(opt-out flag must be set) and its signature to authority section.
  1. Check for the existence of matching data at QNAME.
    1. If an RRset matching QNAME/QTYPE is found, add it to the answer section, then (if QTYPE was not NS) add the NS records for the enclosing zone to the authority section. Go to step 7.
    2. If an RRset matching QNAME/CNAME is found, add it and its signature to the answer section.
    3. If ANY RRset matching QNAME is found, regardless of RRtype, if zone is secured, add matching nsec/nsec3 rrset and its signature to authority section. goto step 6.
    4. If any RRsets are found with a name which is a subdomain of QNAME, if the zone is secured by nsec, add nsec rr covering qname and its signature to authority section; if the zone is secured by nsec3, add nsec3 rr matching qname(must exist) to authority section. go to step 6.
    5. If none of the above are found, go to step 4.
  1. No match has been found. If zone is secure by NSEC, an covered NSEC RR proving that there is no exact match for QNAME,should add those to the authority section. if the zone is secured by nsec3, add nsec3 rr matching qname's closest enclosure name and nsec3 rr covering qname's next closer name and their signatures to authority section. then check wildcard match. search qname's wildcard name(add "*" to qname's closest enclosure name) and qtype: if found, modify the wildcard rrset name to qname and add it and its signature to answer section; if wildcard name found but no type match, add the nsec3 rr matching wildcard name and its signature to authority section; if wildcard name not found, add nsec3 rr covering wildcard name to authority section.
    1. If the difference between the number of labels in QNAME and the name of the enclosing zone is greater than zero, then for each intermediate node starting immediately above QNAME and working up to the enclosing zone, prepend a '*' label and check for the existence of an RRset with that name. If found, go to step 4b; otherwise, set Rcode to NXDOMAIN ,if zone is secure and support NSEC,an NSEC RR proving that the zone contains no RRsets that would match QNAME,via wildcard name expansion,should add those to the authority section ;if zone is secure and support NSEC3, up to three NSEC3 RRs proves that a wildcard that could have matched QNAME does not exit,MUST add those to the authority section.And go to step 6.
    2. If the wildcard label is found to exist, match records at that node against QTYPE. If any match, copy them into the answer section (but with the owner of the RRset set to be QNAME), then add the NS records for the enclosing zone (with signatures if zone is secure) to the authority section, if zone is secure and support NSEC, an NSEC RR and associated RRSIG RR(s) proving that the zone does not contain a closer match for QNAME MUST add in the autority section;if zone is secure and support NSEC3, an NSEC3 RR that proof the wildcard match was valid must be add in the autority section,and go to step 7. If no records match QTYPE, proceed to step 4c.
    3. If the wildcard node contains data of RRtype CNAME, copy the CNAME RRset into the answer section, but set its owner to be QNAME, then go back to step 1, but with QNAME set to the target of the CNAME RR.If zone is secure and support NSEC, an NSEC RR proving that there is no exact match for QNAME,an NSEC RR proving that the zone contains no RRsets that would match QNAME,via wildcard name expansion,should add those to the authority section ;if zone is secure and support NSEC3, up to three NSEC3 RRs proves both that QNAME does not exist and that a wildcard that could have matched QNAME does not exit,MUST add those to the authority section.Go to step 6.

  1. A DNAME record has been found above QNAME. Copy the DNAME RRset into the answer section.
    1. If the length of the DNAME target plus the portion of the QNAME below the origin of the DNAME is greater than the legal size for a domain name, set Rcode to YXDOMAIN and exit. Otherwise, perform the substitution and continue to step 5b.
    2. If the query has EDNS0 version info indicating knowledge of DNAME, add the NS record for the enclosing zone to the authority section and go to step 7. Otherwise continue to step 5c.
    3. Create a CNAME record mapping from QNAME to the target created by the substitution in step 5a, add it to the answer section, and go back to step 1 (but with QNAME set to the target of the synthesized CNAME RR).
  1. No data has been found. Add the SOA for the enclosing zone (with signature if zone is secure) to the authority section of the reply,and exit.
  1. For each RRset which has been added to the answer or authority section and has an RRtype requiring additional data (NS, MX, SRV, NAPTR...), use local data to attempt to provide that data. For referrals (i.e., RRtype NS) this may include glue data, if authoritative data are not available. (Note that glue records must exactly match the name in the NS RR, without CNAME or wildcard processing, and that glue records do not include signatures. Glue is mandatory; if it does not fit, set the TC flag.) Any additional data which has already been provided in the answer section (for instance, if the original query happened to be for the address of the DNS server), it should be omitted from the additional section. If authoritative data are available, then if the corresponding zones are secure, include signatures. Exit.

BIND 10 implementation

BIND 10 implements the above algorithm by maintaining a queue, for each query, of discrete query tasks (stored in QueryTask objects) which contain (among other data):

  • A q-tuple of data to be fetched from the best available data source
  • The section of the reply (answer, authoritative, or additional) into which the data are to be written once fetched from the data source.
  • The state of the query at the time the task was added to the queue (getting answers, getting additional, getting authority, chasing CNAME, etc)

For example, consider a query for www.foo.com/IN/A. A QueryTask is created for www.foo.com/IN/A, in get-answer state, with data to be added to the answer section. It is added to the task queue.

  1. doQuery() pulls an item off the task queue.
  2. findClosestEnclosure() discovers a data source which is authoritative for foo.com; the QueryTask is dispatched to that data source.
  3. www.foo.com/IN/A does not exist, but www.foo.com/IN/CNAME does, pointing to www.bar.com. The CNAME is added to the answer section. A new QueryTask is created for www.bar.com/IN/A, in follow-CNAME state, with data to be added to the answer section. This QueryTask is added to the task queue.
  4. doQuery() pulls the next item off the task queue.
  5. findClosestEnclosure() discovers a data source which is authoritative for bar.com. www.bar.com/IN/A exists, and is added to the answer section.
  6. There are no more items in the task queue, so a new QueryTask is created for bar.com/IN/NS, in get-authority state, with data to be added to the authority section. This query task is dispatched to the data source known to be authoritative for bar.com. For each NS record returned in the RRset, two new QueryTasks are created, for the NSname/IN/A and NSname/IN/AAAA, in get-additional state, with data to be added to the additional section.
  7. doQuery() continues processing these query tasks until the task queue is empty, then returns.

Detailed state table and/or psuedocode to follow.

Last modified 6 years ago Last modified on Nov 2, 2011, 2:11:46 AM