RoundRobin question

[Kevin Darcy]

William Stacey wrote:

>>at random. The only difference between the two orderings is that the
>>second through _nth_ records of the response are given out randomly in
>>the case of "random", but according to the stored order, rotated, in the
>>case of "cyclic". If you have only 2 A records, the first record is
>>    
>>
>
>I understand random.  But what about cyclic again?  The first record is
>selected randomly - got that so far.   Then each in line?
>www.t.com. 1.1.1.1
>www.t.com. 2.2.2.2
>www.t.com. 3.3.3.3
>
>So for cyclic, random first record is 2.2.2.2 for example.  Then it uses
>3.3.3.3 and 1.1.1.1 in order?  Same order every time 2.2.2.2 is selected
>first?
>
Correct.

>>Why doesn't BIND implement true round robin? Because the developers
>>don't want to bother keeping track of state information above and beyond
>>the actual ordering of the records themselves (and it would be
>>prohibitively expensive to actually rearrange the records in memory
>>every time an answer was given). *If* the developers were interested in
>>    
>>
>
>Saying rrset is an arraylist, removing the first and adding it to the bottom
>is actually really fast (~600ms for 3million operations on a 2gh machine)..
>If rrset is a linked list, this would even be faster as you just move a
>couple pointer around.  So it could be done that way without much fuss I
>would think.  Keeping state would be a bit hacky as you would probably need
>to keep the state with the rrset or rr itself and that would require another
>field in the rr class which may not be great.
>
Trouble is, the resource records are stored in a much more complex data 
structure than a linked list (*names* are stored in a red-black tree, 
but underneath each name is 0 or more RRsets, and then even within an 
RRset there is DNSSEC key/signature information, etc. etc.). But take 
all of this with a grain of salt, since I'm not actually a BIND developer...

>>keeping some state around, I'd like to see an implementation of
>>"permuted" ordering, where every possible permutation of A records is
>>presented with equal frequency. That should eliminate the "spiking"
>>problem -- since the first record of each response will get equal (or
>>very nearly equal) time -- while at the same time minimizing the
>>"failover skewing" problem (since the second record in every response
>>    
>>
>
>Would that not be handled by true round-robin or not sure how permuted
>ordering is different?  TIA
>
No, true round-robin ordering would be ABC/BCA/CAB. Permuted order would 
be ABC/BCA/CAB/ACB/BAC/CBA. Each possible permutation is presented 
equally. If A fails, then there is equal failover to both B and C, which 
does not happen with true round-robin. The downside is you have to track 
even more state for permuted order.

                                                                         
                                       - Kevin