Copyright (C) 1999, 2000 Internet Software Consortium.

See COPYRIGHT in the source root or http://isc.org/copyright.html for terms.

$Id: resolver,v 1.4 2000/08/09 04:37:25 tale 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? ]