Copyright (C) 1999-2001  Internet Software Consortium.
See COPYRIGHT in the source root or http://isc.org/copyright.html for terms.

$Id: resolver,v 1.5 2001/01/09 21:46:52 bwelling Exp $

Multi-target Resolver
=====================
Due to IPv6 and other multiple-path resolving needs, the resolver in
BIND 9 needs to be able to handle more than one simulaneous resolving
task for any single request.

For instance, following an A6 chain could result in multiple "forks"
for each network providor.


Resolver Overview
=================

The resolver core is divided into several parts, each of which has a
fairly simple function (with some exceptions) to simplify the problem.
The most complicated portion is the search algorithm "state machine."


Flow of a Request
-----------------

Query Management.

Each query is associated with a given view.  The view-based management
allows different clients to be provided with different data based on
administrative requirements.

This is also the layer where EDNS is handled first.  EDNS knowledge is
handled in some ways throughout the resolver, but several constraints
need to be handled if the receiving client cannot handle the EDNS
format.  (XXX need more)

When a client (caller) issues a query, the first thing that happens is
the list of currently outstanding queries is checked.  If another query
is already being processed for another client, the new request
attaches to the running query and shares the result when it
completes.

If no outstanding requests for this query exist, a new query context
is created and an event is passed to an internal "resolver task" for
handling.

In either case, when the internal resolver task completes the request
the waiting clients are sent an event.  Note that the calling clients
can remove their request for various reasons, such as a timeout.  The
internal task will continue to work on the request, however.  This
will let other clients attach to a query that some work was done for,
and it will help to populate the cache in hopes this query will be
repeated.

Calling into the resolver may cause the currently running task to do
some amount of work, rather than handing off to an internal task
immediately.  This is more efficient (fewer context switches) but the
client's task will not be blocked for any long-term purposes.

The query management layer is also used for internal queries, from the
search algorithm state machine.  In this case, the "client" is an
internal resolver task, and all callbacks are within the resolver
itself.

The next stage in the resolving process is the search algorithm state
machine.


Search Algorithm State Machine.

This is where the guts of the resolving takes place.  The cache is
consulted for an answer, and if deemed good, returned.  The
authoritative data is also consulted here.

Many internal queries may be launched to perform recursive queries on
behalf of clients or the resolver itself.  The algorithm is described
elsewhere.

The output of this stage is either to return to query management with
an answer, or to move to the address selection phase.


Address Selection.

Given that the resolver may have a forwarder list, or may have a
number of possible IP addresses to consult for more information, some
selection of which is the best address to use needs to be performed.
This layer does this.

It will select from a possible set of IP addresses to send a query
to.  They are ranked in various ways (round-trip time, reliability,
and lameness for a given zone are a few) and the best is selected.
Some state is maintained to allow retransmission in the case of a
timeout.

The output of this goes to message formatting.


Message Formatting.

This section will construct a wire message to perform a query.

The output of this section is what is transmitted to the wire in the
external DNS query section.


External DNS Query.

This is where a wire message is transmitted to the "best" socket
address.  Timeouts are handled here, and timing information is
gathered when requests complete.


Received Message Handling.

When a message arrives from an internal query, the result is evaluated
here.  Things like message ID matching the query, query answers
question, TSIG, DNSSEC, etc are performed here.


Caching and Evaluation of Result.

Once the message format and envelope are examined, some bits are
cached (including hints that a given rrset has a zero TTL).  Other
bits feed back into the search algorithm state machine to continue
processing.


[ XXX need examples? ]
