Algorithm for sorting response in a round-robin DNS configuration

Question

I'm trying to implement a sorting algorithm to ensure my DNS library always works with an ordered list of DNS records, even if the response comes from a Round-Robin configuration.

Let's take the following two responses.

First.

$ dig google.com A

; <<>> DiG 9.6.0-APPLE-P2 <<>> google.com A
;; ...

;; ANSWER SECTION:
google.com.  201 IN A 74.125.39.106
google.com.  201 IN A 74.125.39.105
google.com.  201 IN A 74.125.39.147
google.com.  201 IN A 74.125.39.104
google.com.  201 IN A 74.125.39.103
google.com.  201 IN A 74.125.39.99

;; ...

Second.

$ dig google.com A

; <<>> DiG 9.6.0-APPLE-P2 <<>> google.com A
;; ...

;; ANSWER SECTION:
google.com.  119 IN A 74.125.39.147
google.com.  119 IN A 74.125.39.104
google.com.  119 IN A 74.125.39.103
google.com.  119 IN A 74.125.39.99
google.com.  119 IN A 74.125.39.106
google.com.  119 IN A 74.125.39.105

;; ...

They are equal except for the fact the ANSWER section contains the DNS records in different order. I need to apply a sorting algorithm to normalize the answer section.

I already figured out an initial version of the algorithm, but the more I add tests the more I discover uncovered cases. For example, in the following response the order of the first record must be kept unchanged.

$ dig www.google.com A

; <<>> DiG 9.6.0-APPLE-P2 <<>> www.google.com A
;; ...

;; ANSWER SECTION:
www.google.com.  603039 IN CNAME www.l.google.com.
www.l.google.com. 78 IN A 74.125.39.105
www.l.google.com. 78 IN A 74.125.39.104
www.l.google.com. 78 IN A 74.125.39.147
www.l.google.com. 78 IN A 74.125.39.106
www.l.google.com. 78 IN A 74.125.39.99
www.l.google.com. 78 IN A 74.125.39.103

;; ...

Is there any kind of existing implementation/reference I can read in order to extract a suitable algorithm?

UPDATE: Some clarification to my original question. I don't need a library to get DNS records, I've got it. I need to find an efficient algorithm to sort the answer section of a response.

Also, keep in mind the question is not restricted to an A question. The original DNS query might be a NS query, a CNAME query or whatever you want.

I'm using Ruby, but this is not relevant for the question itself.

Answer 1

Depending on the language you're using, putting all the answers in a hash/dictionary with an array for the leafs according to type/address, would probably be simpler.

I'd recommend tie::sorted::array::lazy if you use perl.

Answer 2

There should be a library available for most programming languages to get a list of ip addresses for a given hostname. It'll be something like gethostbyname which will return an array of IP addresses which you can sort like any standard array. In PHP it's gethostbynamel, In Ruby it's Socket::gethostbyname.

There's no need to go through the process of getting DNS records yourself, but if you really want to then the DNS rules are quite simple. A hostname will either return a CNAME or an A record (presuming we are just dealing with IPv4); an A record will return IP addresses, if you get a CNAME you'll want to use recursion to get the A records of the CNAME result.

Answer 3

1. Get list of IP addresses.
2. Convert IP addresses to integer representation.
3. Sort IP addresses by integer representation.
4. Profit.

Answer 4

Can you please explain why you need to sort them?

Generally the order of DNS records within each section of a packet is irrelevant. Nor is it guaranteed that two successive queries will return the same subset of possible records.