Round robin not cyclic

[Kevin Darcy]

peter.ekowicki at fairchildsemi.com wrote:

> Hello,
> I have been investigating the use of round robin in BIND.  I have
> noticed a major discrepancy in round-robin behavior depending on which
> BIND version I am using.  If I have multiple A records for a host, BIND
> 8.2 and above will return a random order of those addresses every time I
> send a query to the nameserver.  Versions below BIND 8.2 will return a
> cyclic ordering.  8.2 and above does not remember what the last response
> it gave was, and therefore does not give out the addresses equally.  For
> example, using the same zone files with a host with 3 A records and 9
> seperate queries, I got the following results:
> BIND 8.1.2 = 3 hits for address A, 3 hits for address B, 3 hits for
> address C
> BIND 8.2.3 = 4 hits for address A, 4 hits for address B, 1 hit for
> address C
>
> I tried BIND 9 and got the same results as 8.2.3.  I also tried the
> rrset-order option in named.conf and got the same results (cyclic and
> random displayed identical behavior although fixed did work as
> advertised).  I have also tried using TTL's of 1 and 3600.  Is there a
> reason this was changed or is there a way to get the old behavior to
> work in the more recent versions of BIND?

The code was changed so that the nameserver doesn't have to keep track of
state regarding which "position" the rotary is in at any given point in
time. The way things are now in the current releases of BIND 8 and BIND 9,
RRset ordering is "stateless", which is easier to program and takes up less
memory in persistent data structures.

As Mark pointed out, generally one wouldn't *want* pure
"round-robin" anyway -- among other things, it can lead to "failover
skewing", i.e. when one node fails, the next one in the rotation gets up to
twice as much traffic as usual. Over the long haul, it doesn't really
matter whether you use round-robin, cyclic or random -- the traffic will
get spread evenly no matter which of those sorting order/algorithms you
use.

Having said that, though, for the *short* haul, "random" and "cyclic", by
their random nature, can experience traffic spikes. Round-robin is a
"fair" algorithm, inasmuch it guarantees that each node in the list will be
presented first in answers equally, and therefore that in the absence of
any node failures, each node should get an equal number of connection
attempts (or whatever the purpose of the name-resolution happens to be),
regardless of what the nameserver's internal dice-rolls/coin-flips happen
to be. Thus no spiking. So I'm somewhat disappointed that round-robin was
dropped as an RRset-sorting option. I'm sure there are certain
applications/environments in which it could be quite useful.

Another "fair" algorithm, which doesn't suffer nearly as much from failover
skewing, is something I call "permuted" order, i.e. work through every
permutation of the list (e.g. ABC/BCA/CAB/ACB/CBA/BAC). Unfortunately, this
requires keeping track of more state even that round-robin. I experimented
briefly with adding permuted order to the BIND 8 codebase, but it never
came to full fruition (the interaction with Dynamic Update, for instance,
was a tough nut to crack, if I recall, as was on-the-fly rrset-order
reconfiguration).


- Kevin