98N/ACopyright (C) 1999, 2000 Internet Software Consortium.
98N/AWhat follows is pseudocode for the zone and cache lookup algorithms, as they
98N/Awill work in the RBT DB.
98N/ANote: These algorithms differ in some respects from those discussed in
98N/Athe RFCs and drafts. I believe these algorithms provide better
98N/Aanswers in some cases.
98N/ABIND 9 zone databases are versioned, and every search is done in the
98N/Acontext of some version. There are a number of ways of implementing
98N/Aversioning. The method that's going to be used in the RBT DB is to
98N/Astore a serial number with every rdataset. All rdatasets added as the
98N/Aresult of a single database update have the same serial number. This
98N/Aserial number is not related to the SOA serial, since the SOA serial
98N/Ais under user control and can do weird things. The database serial
98N/Anumber is a monotonically increasing value. When you go to retrieve
98N/Aan rdataset, you may encounter many rdatasets of that type at any
98N/Agiven node. The correct one to return, called the "active rdataset",
98N/Ahas the greatest serial number less than or equal to the serial number
98N/Aused for the search. The version whose serial number is being used in
98N/Athe search is the "target version".
98N/ACache databases are not versioned. A search will always return the
98N/ADKZC == Deepest Known Zone Cut. This is the zone cut closest to the
98N/Adesired name. In a zone, it's either a delegation out of authoritative
98N/Adata, or it's the top of the zone.
98N/AZC == "zone cut", a node not at the zone top which has an active NS
98N/Ardataset, or a node (including the zone top) with an active DNAME
98N/AZone Search Algorithm
98N/A Search rdata type (including ANY)
98N/A The search options parameter is a flags variable. Current
98N/A Glue OK If set, then the caller is
98N/A wants best match results for
98N/A the search name, even if it's
98N/A glue. If not set, the caller
98N/A will get a delegation if the
98N/A search name is glue.
98N/A Glue Validation Section 7.18 of RFC 2136
98N/A requires that certain data that
98N/A is not in the zone and is not
98N/A glue remain stored in the zone.
98N/A A search can never return this
98N/A data, but there might be glue
98N/A mixed in with it. Telling glue
98N/A from non glue involves some
98N/A work, especially since the
98N/A database is versioned. Often,
98N/A however, the caller will know
98N/A the name it's looking for is
98N/A glue, so validation isn't
98N/A the name of the node
98N/A rdataset (not bound if querying for ANY)
98N/A Note: The node, name, and rdataset are optional. If the
98N/A caller doesn't care about them, they won't be set.
98N/A Note: there is no EDNS1 "longest match" support in the algorithm yet,
98N/A though I know how to do it.
Search down from the root of the tree. If, while going down, we
encounter a zone cut node, then search the rdatasets at the zone
cut for active DNAME or NS rdatasets. Note that if we find both
an active DNAME rdataset and an active NS rdataset, then the DNAME
If we found an active DNAME rdataset, the search ends here.
foundname = name of this node
If we found an active NS rdataset
If finding glue is not OK, or we're not searching for
a glue type, then the search ends here.
result = DNS_R_DELEGATION
foundname = name of this node
We remember that this node is the ZC.
We remember this node's name.
We'll ignore any zone cuts found further down
Continue the search down.
If we don't have an exact match to the name
If we're below a zone cut, then we need to return a referral.
result = DNS_R_DELEGATION;
Else If this zone has any wildcards, then
Go looking for a wildcard match for this name.
foundname = wildcard node name
Fall through to searching the wildcard node
If this is a secure zone then
Find the greatest predecessor to this node
that has at least one active rdataset.
Change the type we're search for to NXT
search_must_succeed = yes
If we're here, then we've got a node and are now trying to find
an active rdataset of the desired type, or, in the case of an ANY
query, any active rdataset.
If we're beneath a zone cut
If the caller wants us to validate glue, then see if the
current name is a valid glue name for the ZC.
result = DNS_R_DELEGATION;
If the desired type is KEY, SIG, or NXT, then
foundname = current node name
Search the rdataset list for the desired type. If cname_ok, also
look for a CNAME rdataset. While searching, remember the active NXT
rdataset if we come across it. We must also determine if there are
any active rdatasets at the node.
If there are no active rdatasets at the node, then we've got an
exact name match, but the name doesn't exist in the desired version.
This means we really have a partial match. Goto Partial_Match.
If we didn't find the type we were looking for (including a failed
If (search_must_succeed), then
The database is bad,
e.g. missing NXT records.
Else if we're beneath a zone cut
result = DNS_R_DELEGATION
result = DNS_R_NXRDATASET
If this is a secure zone then
If we found an active NXT rdataset
We have found the type we were looking for or we've found a CNAME.
If we're not doing any ANY query, didn't find the type we were looking
for, but did find a CNAME
Else If we're beneath a zone cut
rdataset = the type we were looking for
Now for the cache lookup algorithm, which is a little different. The
cache algorithm takes an optional "zone DKZC". Say a server is
if we don't find it, the authoritative delegation might be the best
DKZC (since there might not be anything for
rc.vix.com in the cache),
so that's why we allow it to be an argument to the cache search
algorithm. Of course, the cache might have data for
rc.vix.comcached, in which case we should use it and not the DKZC.
DKZC A is "better" than DKZC B if DKZC A is a proper subdomain of DKZC
Go down as far as possible remembering every parent node.
Remember the predecessor too.
If some rdataset for name exists
Look for desired type or CNAME
Indicate this and return.
Indicate we know nothing about this type at this
(Peek at predecessor to see if it has an NXT for the same
zone and which covers the QNAME. If so, return it.)
Go up until we find a node with a DNAME or a zone cut.
XXX DNAME draft says go up until you prove that there are no
ancestor DNAMEs at all XXX
Return a DNAME result with the dname node and node name
XXX what if the zone DKZC is better (
i.e. deeper)? XXX
We know nothing about this name.
XXX DNAME draft says that if we have a zone DKZC, we should
use it now. I say use the best DKZC you've got. XXX
If we get all the way to '.' and we don't even have the
If we have a DKZC from authoritative data
Return NO_KNOWN_AUTHORITY
(this will cause priming of root servers or,
If we have a zone DKZC and it's better than the one we found
Return it (node and name).
Return the cache DKZC (node and name).