No subject
Tue Apr 2 00:56:56 UTC 2013
4.3.2. Algorithm
The actual algorithm used by the name server will depend on the local OS
and data structures used to store RRs. The following algorithm assumes
that the RRs are organized in several tree structures, one for each
zone, and another for the cache:
1. Set or clear the value of recursion available in the response
depending on whether the name server is willing to provide
recursive service. If recursive service is available and
requested via the RD bit in the query, go to step 5,
otherwise step 2.
2. Search the available zones for the zone which is the nearest
ancestor to QNAME. If such a zone is found, go to step 3,
otherwise step 4.
3. Start matching down, label by label, in the zone. The
matching process can terminate several ways:
a. If the whole of QNAME is matched, we have found the
node.
If the data at the node is a CNAME, and QTYPE doesn't
match CNAME, copy the CNAME RR into the answer section
of the response, change QNAME to the canonical name in
the CNAME RR, and go back to step 1.
Otherwise, copy all RRs which match QTYPE into the
answer section and go to step 6.
b. If a match would take us out of the authoritative data,
we have a referral. This happens when we encounter a
node with NS RRs marking cuts along the bottom of a
zone.
Copy the NS RRs for the subzone into the authority
section of the reply. Put whatever addresses are
available into the additional section, using glue RRs
if the addresses are not available from authoritative
data or the cache. Go to step 4.
c. If at some label, a match is impossible (i.e., the
corresponding label does not exist), look to see if a
the "*" label exists.
If the "*" label does not exist, check whether the name
we are looking for is the original QNAME in the query
Mockapetris [Page 24]
RFC 1034 Domain Concepts and Facilities November 1987
or a name we have followed due to a CNAME. If the name
is original, set an authoritative name error in the
response and exit. Otherwise just exit.
If the "*" label does exist, match RRs at that node
against QTYPE. If any match, copy them into the answer
section, but set the owner of the RR to be QNAME, and
not the node with the "*" label. Go to step 6.
4. Start matching down in the cache. If QNAME is found in the
cache, copy all RRs attached to it that match QTYPE into the
answer section. If there was no delegation from
authoritative data, look for the best one from the cache, and
put it in the authority section. Go to step 6.
5. Using the local resolver or a copy of its algorithm (see
resolver section of this memo) to answer the query. Store
the results, including any intermediate CNAMEs, in the answer
section of the response.
6. Using local data only, attempt to add other RRs which may be
useful to the additional section of the query. Exit.
AND....
5.3.3. Algorithm
The top level algorithm has four steps:
1. See if the answer is in local information, and if so return
it to the client.
2. Find the best servers to ask.
3. Send them queries until one returns a response.
4. Analyze the response, either:
a. if the response answers the question or contains a name
error, cache the data as well as returning it back to
the client.
b. if the response contains a better delegation to other
servers, cache the delegation information, and go to
step 2.
c. if the response shows a CNAME and that is not the
answer itself, cache the CNAME, change the SNAME to the
canonical name in the CNAME RR and go to step 1.
d. if the response shows a servers failure or other
bizarre contents, delete the server from the SLIST and
go back to step 3.
Step 1 searches the cache for the desired data. If the data is in the
cache, it is assumed to be good enough for normal use. Some resolvers
have an option at the user interface which will force the resolver to
ignore the cached data and consult with an authoritative server. This
is not recommended as the default. If the resolver has direct access to
a name server's zones, it should check to see if the desired data is
present in authoritative form, and if so, use the authoritative data in
preference to cached data.
Step 2 looks for a name server to ask for the required data. The
general strategy is to look for locally-available name server RRs,
starting at SNAME, then the parent domain name of SNAME, the
grandparent, and so on toward the root. Thus if SNAME were
Mockapetris.ISI.EDU, this step would look for NS RRs for
Mockapetris.ISI.EDU, then ISI.EDU, then EDU, and then . (the root).
These NS RRs list the names of hosts for a zone at or above SNAME. Copy
the names into SLIST. Set up their addresses using local data. It may
be the case that the addresses are not available. The resolver has many
choices here; the best is to start parallel resolver processes looking
Mockapetris [Page 34]
RFC 1034 Domain Concepts and Facilities November 1987
for the addresses while continuing onward with the addresses which are
available. Obviously, the design choices and options are complicated
and a function of the local host's capabilities. The recommended
priorities for the resolver designer are:
1. Bound the amount of work (packets sent, parallel processes
started) so that a request can't get into an infinite loop or
start off a chain reaction of requests or queries with other
implementations EVEN IF SOMEONE HAS INCORRECTLY CONFIGURED
SOME DATA.
2. Get back an answer if at all possible.
3. Avoid unnecessary transmissions.
4. Get the answer as quickly as possible.
If the search for NS RRs fails, then the resolver initializes SLIST from
the safety belt SBELT. The basic idea is that when the resolver has no
idea what servers to ask, it should use information from a configuration
file that lists several servers which are expected to be helpful.
Although there are special situations, the usual choice is two of the
root servers and two of the servers for the host's domain. The reason
for two of each is for redundancy. The root servers will provide
eventual access to all of the domain space. The two local servers will
allow the resolver to continue to resolve local names if the local
network becomes isolated from the internet due to gateway or link
failure.
In addition to the names and addresses of the servers, the SLIST data
structure can be sorted to use the best servers first, and to insure
that all addresses of all servers are used in a round-robin manner. The
sorting can be a simple function of preferring addresses on the local
network over others, or may involve statistics from past events, such as
previous response times and batting averages.
Step 3 sends out queries until a response is received. The strategy is
to cycle around all of the addresses for all of the servers with a
timeout between each transmission. In practice it is important to use
all addresses of a multihomed host, and too aggressive a retransmission
policy actually slows response when used by multiple resolvers
contending for the same name server and even occasionally for a single
resolver. SLIST typically contains data values to control the timeouts
and keep track of previous transmissions.
Step 4 involves analyzing responses. The resolver should be highly
paranoid in its parsing of responses. It should also check that the
response matches the query it sent using the ID field in the response.
Mockapetris [Page 35]
RFC 1034 Domain Concepts and Facilities November 1987
The ideal answer is one from a server authoritative for the query which
either gives the required data or a name error. The data is passed back
to the user and entered in the cache for future use if its TTL is
greater than zero.
If the response shows a delegation, the resolver should check to see
that the delegation is "closer" to the answer than the servers in SLIST
are. This can be done by comparing the match count in SLIST with that
computed from SNAME and the NS RRs in the delegation. If not, the reply
is bogus and should be ignored. If the delegation is valid the NS
delegation RRs and any address RRs for the servers should be cached.
The name servers are entered in the SLIST, and the search is restarted.
If the response contains a CNAME, the search is restarted at the CNAME
unless the response has the data for the canonical name or if the CNAME
is the answer itself.
Details and implementation hints can be found in [RFC-1035].
> -----Original Message-----
> From: bind-users-bounce at isc.org [mailto:bind-users-bounce at isc.org] On
> Behalf Of Patrick Reany
> Sent: Friday, October 04, 2002 4:25 PM
> To: comp-protocols-dns-bind at isc.org
> Subject: Basic DNS resolving theory
>
>
> Do I have the correct model of DNS resolving?
>
> Host machine asks for DNS resolution.
> Host's resolver passes request to first DNS
> server (listed in its TCP/IP configuration), a local
> caching server. If it resolves then the IP address
> is returned, else, if it is a name server it passes
> the resolution on to a root server, which passes
> back to the resolver on the host the IP address
> of a top level domain server. The resolver then
> passes the request on to this server, which in
> turn passes back the address of an authoritative
> server. Then the resolver passes the request on to
> the authoritative server, which returns to the
> resolver the resolved IP address, assuming that
> such a resolution exists.
>
> If I got this chain of event and transfers
> right, what role does the name server
> play that the caching server does not?
>
> Am I right that on the enterprise LAN there
> are the
> host resolvers,
> caching servers, and
> name servers;
> and on the Internet there are the
> root servers,
> top-level domain servers, and
> authoritative servers?
>
> What is the analog of "authoritative server to zone,"
> and "name server to domain"?
>
> TIA.
>
> Patrick
More information about the bind-users
mailing list