dnsd - A simple, secure, smart DNS server

dnsd - A simple, secure, smart DNS server

dnsd - A simple, secure, smart DNS server

dnsd was written as an assignment for the following class:

CS328 - TCP/IP Networks
UBC-Okanagan, with Dr. Ramon Lawrence
By Doug Hoyte, April, 2007

  1. What is dnsd?
  2. DNS prediction
  3. Caching
  4. dnsd features
  5. Empirical testing of DNS prediction
  6. Conclusion and future

What is dnsd?

dnsd is a small and simple yet cutting-edge and powerful DNS server written in the nuff programming language. Since the nuff layer system makes the parsing and creation of DNS packets trivial, dnsd is free to focus on implementing sophisticated asynchronous DNS server logic. dnsd's goals are simplicity and security, so we have elected to not support certain features offered by BIND or required in the RFCs. dnsd is not a replacement for BIND mostly due to its lack of secondary server support.

dnsd is meant for individuals needing a flexible, light-weight DNS cache or a simple, safe authoritative DNS server. dnsd is also designed as a forwarding DNS cache that can transparently "poison" certain DNS records with custom values.

dnsd is compact and easy to audit (around 200 lines of code) but still packed with features. Thanks to the nuff programming environment, we can use powerful, high-level abstractions close to the lowest-level unix network APIs. Although dnsd currently only supports UDP through unix DGRAM sockets, enabling dnsd to work over some other nuff transport mode (TCP sockets or raw IP or raw ethernet sockets or ...) would be simple.

dnsd listens on UDP port 53 (by default) through your unix system's DGRAM UDP sockets. It requires root privileges to listen to ports below 1025 but not otherwise. You can specify the port to listen on with the -port switch.

Since dnsd is designed to be simple it does as little as possible by default. You need to specify one or more modes for it to operate in. To do that, use any combination of the following switches when you launch dnsd from the unix command line:

DNS prediction

Have you ever watched the bottom of your web browser, perhaps during slow network conditions, and seen the status momentarily stalled at "Looking up ..."? That is your web browser's way of telling you it is waiting for the results of some DNS query. Often complex web pages will get stalled on several DNS queries when parsing and processing the content. Images or css files in a separate domain, redirects, and many more web features can cause additional DNS queries to be issued. When certain DNS requests can't be issued until the results of another DNS request are delivered, we call this a "DNS dependency tree".

The most innovative feature dnsd provides is an experimental pre-fetching algorithm created by Doug Hoyte and HCSW Labs. To my knowledge, this is the first implementation of our algorithm. The technique uses information gathered from previously observed DNS resolution patterns to guess, in advance, which DNS requests are likely to be issued, and then starts them up "in the background" so they are ready sooner when/if actually needed.

DNS prediction has a fairly limited scope in what it tries to predict. It doesn't try to get inside your head and guess when you are going to check your email, for instance. The algorithm does about all an algorithm can do: it sticks with predicting the behaviour of mere programs and processes.

DNS is rarely ever the bottleneck when surfing the web, of course, but as more and more layers of technology get added to the internet, reducing these round-trip times in aggregate can add up to a suprising improvement in performance. Here is a fairly common DNS dependency tree (note that smart DNS/HTML configurations can reduce or eliminate many of these dependencies):

The DNS dependency tree of an IPv6-enabled browser loading http://cbc.ca

To try to reduce the total waiting time required when processing these DNS dependency trees, dnsd uses an innovative pre-fetching algorithm.

The algorithm uses an "infinitley growing" list of DNS requests. It maintains a pointer to the end of the list and adds every DNS request it services to the end of the list. When it services a request, it starts up an "open window" which is a continuation scheduled to run at some point in the future (specified with the dnsd -predict-window option). Each continuation keeps a pointer to the last request that was issued when the window started. When the continuation runs, it is simply a matter of following the list to the end and determining if any of the subsequent queries are (or should be) a part of the prediction window.

Here is a graphical depiction of the algorithm:

Nuff dnsd DNS Prediction Algorithm

The algorithm also involves maintaining a few hash-tables of possible prediction windows. Any record/type pair can contain a list of "dependencies" each with their own positive score value. Every time we see this dependency during our open window, we add 1 to its score. Every time our window expires without us seeing it, we subtract 1 from its score. Dependencies with a score of 0 are removed. DNS dependencies are only pre-fetched when their score is 2 or higher. Since we have to observe the dependency two separate times, unrelated queries are prevented from becoming associated with DNS dependencies. Because we subtract 1 from their score if we don't see them in later windows, even if they are they won't stay associated for long.


How does DNS caching relate to prediction?

DNS caching assigns a "Time To Live" value to all records. This tells us the latest point in time to consider this record valid. When that time expires, we (or likely our ISP's DNS server) will have to perform another request which will need (at least) a round-trip to the authoritative nameserver for the record. Caching is a brilliant and invaluable component of DNS that enables a DNS admin to control the frequencies of these round-trips.

Our prediction algorithm keeps and uses data regarding queries longer than the TTL expiry time but still never treats a record as valid past its particular TTL expiry time.

In other words, prediction does not change the meaning or behaviour of DNS caching at all. In all forwarding and prediction replies, dnsd is also a regular DNS cache implementation.

dnsd features

Here is a partial list of dnsd's miscellaneous features:

Empirical testing of DNS prediction

For testing purposes, we used the nuff command dnssequence (see the nuff manual pages) to simulate and time the resolution of DNS dependency trees. We resolve these DNS dependency trees 5 times for each resolver and record the total elapsed time for each resolution.

We used special DNS records with a TTL of 0 so DNS caching didn't factor in (NS records were always cached). All comparisons were done sending the queries to a copy of BIND (the standard DNS server on the internet) versus a dnsd instance running on the same system. The dnsd instance was configured to forward its requests to that same local copy of BIND.

We used a 56k dial-up modem for our internet connection because of its consistent and large round-trip times and also because its bandwidth is easy to overwhelm. All runs are the averaged results of 3 identical runs.

Conclusion and future

All material is © Doug Hoyte and/or HCSW Labs unless otherwise noted or implied.