DNS Balancer

The below text describes an earlier research project of mine, concerning DNS balancing. Using the approach that's shown below I've coded a production-grade "real" DNS request proxy/balancer, named dnspb. It is described in its separate page at http://www.kubat.nl/pages/dnspb

Crossroads, my pet open source project, is a balancer for TCP services, such as database connections, SMTP, HTTP. I've received many mails asking whether UDP balancing - and mainly for DNS - can be integrated into Crossroads. The answer was always: no, that's out of scope. My reasoning is that UDP is a totally different ballgame than TCP: it's connection-less, messages may arrive out of order, delivery is not guaranteed, there's no way to see whether your back end is alive, and so on.

But does that mean that a DNS balancer is not feasible? Nah, of course it can be done, but IMHO it's more of a specific balancer, hand-crafted for the purpose, instead of a generic balancer, which Crossroads attempts to be. So just to test this hypothesis, I wrote a small DNS balancer, which is shown here.

Download the sources!

If you want to try it out: You can download all the code as dns-balance.tar.gz. Unpack the archive, cd into the unpacked directory dns-balance and hit make. You will need GNU Make and a C++ compiler on your system. A working DNS balancer is constructed as build/dns-balance. Fire it up as user root as:

build/dns-balance -v IP1 IP2 IP3 ...

where the IP's are IP addresses of your DNS servers. (If you just type build/dns-balance then you get some usage information.) You must start it as user root because the DNS balancer has to get control of port 53, which is a priviledged port. If you have only one DNS server in your network, just state one IP address. In that case the balancer actually becomes just a forwarder. The flag -v is included in this example so that the actions of dns-balance are shown. You wouldn't need this flag in a "production" setting.

Once the balancer is running, start a second window and try it out, using:

nslookup www.kubat.nl 127.0.0.1

Here the extra argument 127.0.0.1 is the IP address of the DNS server that nslookup should use, which is of course the balancer.

The code of the DNS balancer is distributed under the GPL V3 license. In short this means that there's no warranty and that you're free to do anything you like with it, provided that you redistribute the original sources, and if applicable: your modifications. If you do make modifications, I'd like to hear about it - just drop me a mail. The same of course applies incase you have questions or suggestions.

Concepts

How DNS lookups work

When a client wants to resolve a host name, then it sends a UDP message to its name server, to port 53. Nothing spectacular so far. But here's the catch: since UDP is connection-less, there is no connection to get the response. The name server has no way of reporting back, unless the two (client and name server) use a trick.

Here's the trick: When the client sends the request, it of course uses a local UDP port to connect to the remote DNS port which is 53. Let's say that the local port is 12345. Having sent the request, the client now starts listening to this same local port 12345. It becomes a server process. The trick is that the client expects that the DNS server will report back to the same port; which in fact means that "on the second leg" of the chitchat, the DNS server becomes a client process that connects to the original client which is now a server on port 12345. Huh?

Maybe the following simple ASCII art will explain.

  FIRST LEG: Client asks the DNS server
       client                                      DNS server
  sending port 12345  -----------------------> listening port 53
		      "Look up a host for me"		


  SECOND LEG: DNS sever answers					     
       client                                      DNS server
  listening port 12345  <---------------------- sending port 53
                        "It's at IP P.Q.R.S"

This in turn means that the DNS server must maintain a list of its pending requests: which client IP requested what host, using which client port? Using that information, the DNS server can determine the "right" client to send a reply.

This approach also means that the client is responsible for error discovery and recovery. If the DNS server fails to answer on the local port 12345 within say 3 seconds, then the client assumes that this request has been lost, and will retry. After a given number of retries the client gives up. This is fortunately already a built-in feature of clients.

How the DNS balancer should behave

When a DNS balancer is placed between the client and the DNS server, then the flow is of course in principle the same. The client will think that the balancer is the DNS server, and the DNS server will think that the balancer is the client. At the crossing point there is however more to think about. The above described "first leg" now consists of two sub-parts: the client asks the balancer, and the balancer asks the DNS server. Let's assume that the local port on the client is 12345, and that the balancer will use a local port 34567:

  FIRST LEG: Request for look up

   client A		       balancer	                DNS server X 
  sending port --------> listening  sending port ------>  listening
     12345		  port 53     34567		   port 53

Once the balancer has forwarded the request to the DNS server, it's already listening to two ports: 53 (the main DNS port which is open for new requests), and 34567, on which the DNS server's reply is expected. The trick is of course that once the response arrives, the balancer must match it with the request. The approach is that the balancer has a list of outstanding requests, which after the above first leg states that a UDP message that is received on on port 34567, from DNS server X, should be forwarded to client A, port 12345. Once the DNS server's response arrives and the balancer makes the match, the "second leg" looks as follows (read from right to left):

  SECOND LEG: Resolved address

   client A		       balancer		         DNS server X
   listening <----------- sending    listening <---------- sending
   port 12345		  port 53   port 34567		   port 53

Dns-balance in fact uses yet another security measure to match a DNS server's reply with a client's request: the transaction ID of DNS requests. Each UDP message that a client sends out, has a (random) 16-bits transaction ID in it. The DNS server's answer must match that ID.

That's why it's a custom balancer!

Balancing DNS requests over UDP will only work if the above scheme is strictly followed. The balancer must expect a resolution message on the same local port where the original request was sent (and hence: it must start a listener on that port after sending the request), and it must report back to the client over its local port 53 (the port where the client's request came in). All such features are not part of UDP itself, they are part of the DNS lookup scheme.

That's why I think there is no generic UDP balancer. That's why I don't think that UDP balancing can be part of generic software, such as Crossroads.

Onward to the code!

The code in dns-balance.tar.gz is organized as follows: under src/ you will find all the sources that are required for the program. Classes are organized under their own subdirectory. E.g., there's a class Message that represents a UDP datagram. Its header file is src/message/message and the implementation is in src/message/*.cc.

Used variables, constants and what they mean

The central include file src/dns-balance includes necessary system headers, and defines a few constants, which mean the following:

dns_port is the basic DNS listen port, 53.
dns_timeout is the number of seconds after which a request is considered "stale". When the DNS balancer fails to receive a "leg-2" answer from a true DNS server within this time, it will assume that there will be no request anymore. E.g., given the above figure: the balancer will stop listening to port 34567 if there is no answer within dns_timeout seconds. Purging this information also means that the local port is freed up for next requests.
verbose is a boolean variable, which causes debug information to be generated when it's "true".
MSG_LEN is the maximum length of a UDP datagram. There is no way of knowing in advance how big a lookup request or a resolved answer will be. The balancer will accept messages up to MSG_LEN size.
PORT_MIN and PORT_MAX are the minimum and maximum values for the balancer's local ports. E.g., given the above figure: the balancer has allocated the local port 34567 for its chitchat with a DNS server. That number lies in this range.
PORT_TRIES is maximum number that the balancer will try to allocate a local port. The allocation is done using a random generator. If the balancer tries PORT_TRIES times but all tried local ports are occupied, then it will assume that it's out of local ports, and will give up servicing the client.
TID_TYPE is the type of a DNS transaction ID. On all systems that I know, it will be a unsigned short which means a 16-bit integer value. Constant TID_OFFSET is the offset in a UDP message where the transaction ID is expected.

Function main()

The function main() is contained in src/dns-balance.cc. It drives the entire process. The code is quite self-explanatory.

Classes and methods

Here is a very basic overview of the balancer's classes and what they are for. Details are of course in the code - "use the source, Luke."

Class Backend represents the back ends (DNS servers) on the command line. Per instance, an IP address is converted to a struct in_addr address (which is the internal byte representation of a dotted-decimal string). Function main() has a vector of back ends which take turns.
Class Crosslist is the administration that the balancer uses to match a DNS server answer with a client. There is a method add() using which information is added (client's address, back end's address, the transaction ID, and local port), and a find() (to find the client's address given a local port, a back end's address, and a transaction ID).
Class Message represents a UDP datagram. Its constructor reads the message and stores the client's remote address and remote port, and the contained transaction ID. There is also a method send() to send the message to a given address and port over a given socket.
Class Portset is a list of ports and sockets that the balancer is listening to. New ports are added using addport(). Method listen() performs the system call select() to wait for activity. The method remove() removes a given port from the listen set. This method is invoked when a DNS response has been forwarded to the client during "leg 2". The method remove() also cleans up "stale" listening ports that have timed out.

How good is this code?

The code works in a proof of concept setting. It's "production ready", but has not been extensively tested. But it's a good starting point if you want to make this a production-grade DNS balancer.

Here are some points for improvements:

The balancer isn't aware of the back end state (i.e., whether DNS servers are alive, how fast they are responding, etc.). The balancer could match the time that a client request is forwarded to a DNS back end, with the time of the response. That way the usability of back ends could be estimated.
Finding a local port is done using the very basic random generator combo srand() / rand(). This might be improved if deemed necessary to provide better protection against DNS cache poisoing. This argument of course only applies if the DNS balancer has DNS servers as clients (because the balancer would then be an attack point for poison).
For extra protection against DNS cache poisoning, the balancer could "make up" its own transaction ID and use it for upstream requests. At the moment the balancer uses transaction ID's that are supplied by the client, and passes them on unaltered.
The balancer neither forks, nor threads: it's just one action loop that reads network data and immediately processes them. Given the nature of UDP, I feel that this is quite sufficient: UDP handling is non-blocking, so that handling socket connections is almost instantaneous. However a thorough loadtest would be needed to verify this assumption. (Introducing threads might even lower the performace due to threading overhead!)