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.)