resolver revision dafcb997e390efa4423883dafd100c975c4095d6
d6fa26d0adaec6c910115be34fe7a5a5f402c14fMark AndrewsCopyright (C) 2004 Internet Systems Consortium, Inc. ("ISC")
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinCopyright (C) 1999-2001 Internet Software Consortium.
32098293b78922a5fbd10906afa28624820d3756Tinderbox UserSee COPYRIGHT in the source root or http://isc.org/copyright.html for terms.
5347c0fcb04eaea19d9f39795646239f487c6207Tinderbox User$Id: resolver,v 1.6 2004/03/05 05:04:47 marka Exp $
5347c0fcb04eaea19d9f39795646239f487c6207Tinderbox UserMulti-target Resolver
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein=====================
d6fa26d0adaec6c910115be34fe7a5a5f402c14fMark AndrewsDue to IPv6 and other multiple-path resolving needs, the resolver in
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinBIND 9 needs to be able to handle more than one simulaneous resolving
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeintask for any single request.
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox UserFor instance, following an A6 chain could result in multiple "forks"
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntfor each network providor.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinResolver Overview
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein=================
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe resolver core is divided into several parts, each of which has a
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinfairly simple function (with some exceptions) to simplify the problem.
71c66a876ecca77923638d3f94cc0783152b2f03Mark AndrewsThe most complicated portion is the search algorithm "state machine."
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinFlow of a Request
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein-----------------
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinQuery Management.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinEach query is associated with a given view. The view-based management
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinallows different clients to be provided with different data based on
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinadministrative requirements.
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox UserThis is also the layer where EDNS is handled first. EDNS knowledge is
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox Userhandled in some ways throughout the resolver, but several constraints
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinneed to be handled if the receiving client cannot handle the EDNS
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinformat. (XXX need more)
14a656f94b1fd0ababd84a772228dfa52276ba15Evan HuntWhen a client (caller) issues a query, the first thing that happens is
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinthe list of currently outstanding queries is checked. If another query
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntis already being processed for another client, the new request
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userattaches to the running query and shares the result when it
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinIf no outstanding requests for this query exist, a new query context
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Useris created and an event is passed to an internal "resolver task" for
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox UserIn either case, when the internal resolver task completes the request
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntthe waiting clients are sent an event. Note that the calling clients
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeincan remove their request for various reasons, such as a timeout. The
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userinternal task will continue to work on the request, however. This
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userwill let other clients attach to a query that some work was done for,
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userand it will help to populate the cache in hopes this query will be
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox UserCalling into the resolver may cause the currently running task to do
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Usersome amount of work, rather than handing off to an internal task
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userimmediately. This is more efficient (fewer context switches) but the
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userclient's task will not be blocked for any long-term purposes.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe query management layer is also used for internal queries, from the
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Usersearch algorithm state machine. In this case, the "client" is an
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntinternal resolver task, and all callbacks are within the resolver
14a656f94b1fd0ababd84a772228dfa52276ba15Evan HuntThe next stage in the resolving process is the search algorithm state
a1ad6695ed6f988406cf155aa26376f84f73bcb9Automatic UpdaterSearch Algorithm State Machine.
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox UserThis is where the guts of the resolving takes place. The cache is
2895f101b5585a19015ac2c2c1e1812ac467fa12Automatic Updaterconsulted for an answer, and if deemed good, returned. The
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userauthoritative data is also consulted here.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinMany internal queries may be launched to perform recursive queries on
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntbehalf of clients or the resolver itself. The algorithm is described
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe output of this stage is either to return to query management with
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Useran answer, or to move to the address selection phase.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinAddress Selection.
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox UserGiven that the resolver may have a forwarder list, or may have a
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntnumber of possible IP addresses to consult for more information, some
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox Userselection of which is the best address to use needs to be performed.
af40ebed6257e4ac1996144530b3de317cf4da11Tinderbox UserThis layer does this.
14a656f94b1fd0ababd84a772228dfa52276ba15Evan HuntIt will select from a possible set of IP addresses to send a query
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntto. They are ranked in various ways (round-trip time, reliability,
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntand lameness for a given zone are a few) and the best is selected.
14a656f94b1fd0ababd84a772228dfa52276ba15Evan HuntSome state is maintained to allow retransmission in the case of a
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe output of this goes to message formatting.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserMessage Formatting.
71c66a876ecca77923638d3f94cc0783152b2f03Mark AndrewsThis section will construct a wire message to perform a query.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe output of this section is what is transmitted to the wire in the
71c66a876ecca77923638d3f94cc0783152b2f03Mark Andrewsexternal DNS query section.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinExternal DNS Query.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThis is where a wire message is transmitted to the "best" socket
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Useraddress. Timeouts are handled here, and timing information is
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usergathered when requests complete.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinReceived Message Handling.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinWhen a message arrives from an internal query, the result is evaluated
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userhere. Things like message ID matching the query, query answers
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinquestion, TSIG, DNSSEC, etc are performed here.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserCaching and Evaluation of Result.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinOnce the message format and envelope are examined, some bits are
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeincached (including hints that a given rrset has a zero TTL). Other
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userbits feed back into the search algorithm state machine to continue
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Hunt[ XXX need examples? ]