resolver revision cf608835a3b057be837bf68bda8abf9550f92294
cf608835a3b057be837bf68bda8abf9550f92294Michael Graff$Id: resolver,v 1.1 1999/04/06 02:50:53 explorer Exp $
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffMulti-target Resolver
cf608835a3b057be837bf68bda8abf9550f92294Michael Graff=====================
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffDue to IPv6 and other multiple-path resolving needs, the resolver in
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffBIND 9 needs to be able to handle more than one simulaneous resolving
cf608835a3b057be837bf68bda8abf9550f92294Michael Grafftask for any single request.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffFor instance, following an A6 chain could result in multiple "forks"
cf608835a3b057be837bf68bda8abf9550f92294Michael Grafffor each network providor.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffResolver Overview
cf608835a3b057be837bf68bda8abf9550f92294Michael Graff=================
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThe resolver core is divided into several parts, each of which has a
cf608835a3b057be837bf68bda8abf9550f92294Michael Grafffairly simple function (with some exceptions) to simplify the problem.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThe most complicated portion is the search algorithm "state machine."
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffFlow of a Request
cf608835a3b057be837bf68bda8abf9550f92294Michael Graff-----------------
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffQuery Management.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffEach query is associated with a given view. The view-based management
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffallows different clients to be provided with different data based on
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffadministrative requirements.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThis is also the layer where EDNS is handled first. EDNS knowledge is
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffhandled in some ways throughout the resolver, but several constraints
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffneed to be handled if the receiving client cannot handle the EDNS
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffformat. (XXX need more)
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffWhen a client (caller) issues a query, the first thing that happens is
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffthe list of currently outstanding query is checked. If another query
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffis already being processed for another client, the new request
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffattaches to the running query and shares the result when it
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffIf no outstanding requests for this query exist, a new query context
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffis created and an event is passed to an internal "resolver task" for
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffIn either case, when the internal resolver task completes the request
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffthe waiting clients are sent an event. Note that the calling clients
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffcan remove their request for various reasons, such as a timeout. The
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffinternal task will continue to work on the request, however. This
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffwill let other clients attach to a query that some work was done for,
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffand it will help to populate the cache in hopes this query will be
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffCalling into the resolver may cause the currently running task to do
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffsome amount of work, rather than handing off to an internal task
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffimmediately. This is more efficient (fewer context switches) but the
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffclient's task will not be blocked for any long-term purposes.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThe query management layer is also used for internal queries, from the
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffsearch algorithm state machine. In this case, the "client" is an
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffinternal resolver task, and all callbacks are within the resolver
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThe next stage in the resolving process is the search algorithm state
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffSearch Algorithm State Machine.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThis is where the guts of the resolving takes place. The cache is
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffconsulted for an answer, and if deemed good, returned. The
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffauthoritative data is also consulted here.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffMany internal queries may be launched to perform recursive queries on
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffbehalf of clients or the resolver itself. The algorithm is described
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThe output of this stage is either to return to query management with
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffan answer, or to move to the address selection phase.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffAddress Selection.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffGiven that the resolver may have a forwarder list, or may have a
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffnumber of possible IP addresses to consult for more information, some
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffselection of which is the best address to use needs to be performed.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThis layer does this.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffIt will select from a possible set of IP addresses to send a query
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffto. They are ranked in various ways (round-trip time, reliability,
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffand lameness for a given zone are a few) and the best is selected.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffSome state is maintained to allow retransmission in the case of a
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThe output of this goes to message formatting.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffMessage Formatting.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThis section will construct a wire message to perform a query.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThe output of this section is what is transmitted to the wire in the
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffexternal DNS query section.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffExternal DNS Query.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffThis is where a wire message is transmitted to the "best" socket
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffaddress. Timeouts are handled here, and timing information is
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffgathered when requests complete.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffReceived Message Handling.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffWhen a message arrives from an internal query, the result is evaluated
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffhere. Things like message ID matching the query, query answers
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffquestion, TSIG, DNSSEC, etc are performed here.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffCaching and Evaluation of Result.
cf608835a3b057be837bf68bda8abf9550f92294Michael GraffOnce the message format and envelope are examined, some bits are
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffcached (including hints that a given rrset has a zero TTL). Other
cf608835a3b057be837bf68bda8abf9550f92294Michael Graffbits feed back into the search algorithm state machine to continue
cf608835a3b057be837bf68bda8abf9550f92294Michael Graff[ XXX need examples? ]