12.4 The Resolver Search Algorithm and Negative Caching

In this trace, we'll show you the BIND 4.9 and BIND 8 search algorithm and the impact of negative caching. We could look up galt.cs.purdue.edu like the last trace, but it wouldn't show you the search algorithm. Instead, we will look up foo.bar, a name that doesn't exist. In fact, we will look it up twice:

1)  datagram from cujo.horror.movie.edu 1109, fd 6, len 25

2)  req: nlookup(foo.bar) id 19220 type=1 class=1

3)  req: found 'foo.bar' as '' (cname=0)

4)  forw: forw -> D.ROOT-SERVERS.NET 53 ds=7 nsid=2532 id=19220

                                             0ms retry 4sec

5)

6)  datagram from D.ROOT-SERVERS.NET 53, fd 5, len 25

7)  ncache: dname foo.bar, type 1, class 1

8)  send_msg -> cujo.horror.movie.edu 1109 (UDP 6) id=19220

9)

10) datagram from cujo.horror.movie.edu 1110, fd 6, len 42

11) req: nlookup(foo.bar.horror.movie.edu) id 19221 type=1 class=1

12) req: found 'foo.bar.horror.movie.edu' as 'horror.movie.edu'

                                             (cname=0)

13) forw: forw -> carrie.horror.movie.edu 53 ds=7 nsid=2533

                                      id=19221 0ms retry 4sec



14) datagram from carrie.horror.movie.edu 53, fd 5, len 42

15) ncache: dname foo.bar.horror.movie.edu, type 1, class 1

16) send_msg -> cujo.horror.movie.edu 1110 (UDP 6) id=19221

Look up foo.bar again:

17) datagram from cujo.horror.movie.edu 1111, fd 6, len 25

18) req: nlookup(foo.bar) id 15541 type=1 class=1

19) req: found 'foo.bar' as 'foo.bar' (cname=0)

20) ns_req: answer -> cujo.horror.movie.edu 1111 fd=6 id=15541

                                                size=25 Local

21)

22) datagram from cujo.horror.movie.edu 1112, fd 6, len 42

23) req: nlookup(foo.bar.horror.movie.edu) id 15542 type=1 class=1

24) req: found 'foo.bar.horror.movie.edu' as

                           'foo.bar.horror.movie.edu' (cname=0)

25) ns_req: answer -> cujo.horror.movie.edu 1112 fd=6 id=15542

                                                  size=42 Local

Let's look at the resolver search algorithm. The first name looked up (line 2) is exactly the name we typed in. Since the name had at least one dot, it is looked up without modification. When that name lookup failed, horror.movie.edu was appended to the name and looked up. (Resolvers before BIND 4.9 would try appending both horror.movie.edu and movie.edu.)

Line 7 shows caching the negative answer (ncache). If the same name is looked up again in the next few minutes (line 19), the name server still has the negative response in its cache, so the server can answer immediately that the name doesn't exist. (If you don't believe this hand waving, compare lines 3 and 19. On line 3, nothing was found for foo.bar, but line 19 shows the whole name being found.)