[rbldnsd] The round-robin problem

[furio ercolessi]

On Mon, Nov 17, 2003 at 08:10:15AM +0300, Michael Tokarev wrote:
> Michael Tokarev wrote:
> >furio ercolessi wrote:
> >
> >>I noticed that rbldnsd (0.99) does not seem to do round robin rotation
> >>of A records.  This can be a problem with zones that have the A
> >>records of the nameservers within the zone itself, as it leads to
> >>unbalancing.
> >
> >Hmm.. not only it leads to unbalancing.  By using nameservers in the
> []
> >Also, you're missing the point here.  The list of nameservers
> ...
> 
> Ghrm.  It's me who's missing the point.  You're not talking about
> glue records as I thought before.  You're talking about any kinds
> of repeated records in `generic' dataset.  

Yes! Sorry if my message was not clear.
The authoritative NS records for sbl.spamhaus.org are in the spamhaus.org 
zone, which is served by another set of (Bind) nameservers.  The problem
are the A records  [this was done by design, to move as much load as 
possible on the larger array of SBL servers - but then this was before 
Ultradns came to rescue so it should not be so important now].

> And indeed, they aren't
> being "rotated" in any way, and that's no good.  I see what you
> mean finally (well.. i hope ;).
> 
> And while we're at it, a simple (programmer's) question: I've an
> array with N elements.  N may be large (as it is not practical to
> allocate something on the stack of this size).  And i want to
> enumerate every element of the array, like for(i=0; i<N; ++i),
> but in pseudo-random order.  What's the simplest way to do so?
> 
> At least, I may allocate a bitmap (one bit for each element),
> set it to all-zeros initially, and until i'm done, get next
> random index i in range 0..(N-1), check whenever i'th bit in
> bitmap is set, continue if set, and "emit" i'th element of the
> array (setting i'th bit in bitmap).  This looks clumsy at best.
> 
> Or, allocate another array of N elements, copy original array
> into it, and again while any elements left, get random index
> in range 0..N-1, emit ith element, let a[i] = a[N-1] (if i != N-1)
> and decrease N.  Looks much better, but requires a copy of the
> original array, or an array of indexes of the same size N...

If you want to do these things fast and without allocating memory,
you can use a Linear Congruential Generator to walk through
your integers in a pseudorandom order.  That is, you obtain
a pseudorandom permutation p(0)..p(N-1) of the integers 0..N-1 by
choosing arbitrarily a p(0) in [0..N-1] and then applying
		p(i) = (a*p(i-1) + c) mod N	, i=1..N-1
and accessing your data as a[p(i)].  a and c are positive integers.
They must be chosen properly in order to visit each integer
once and only once in a complete cycle of length N (the cycle
will be closed, i.e. p(N)=p(0)).  If Martin Greenberger in 1961
was correct, this will happen when:
*  c is prime relatively to N  (c and N have no common factors other than 1)
*  a-1 is a multiple of x for every prime x dividing N
*  a-1 is a multiple of 4, if N is a multiple of 4

Example: N=10.  Choose c=3 (relative prime with 10).
Choose a=11 (a-1 multiple of 2, multiple of 5).
Choose a starting point p(0)=4  (arbitrary).  You get:

p(1) = ( 11*4 + 3 ) mod 10 = 47 mod 10 = 7
p(2) = ( 11*7 + 3 ) mod 10 = 80 mod 10 = 0
p(3) = ( 11*0 + 3 ) mod 10 =  3 mod 10 = 3
p(4) = ( 11*3 + 3 ) mod 10 = 36 mod 10 = 6
p(5) = ( 11*6 + 3 ) mod 10 = 69 mod 10 = 9
p(6) = ( 11*9 + 3 ) mod 10 =102 mod 10 = 2
p(7) = ( 11*2 + 3 ) mod 10 = 25 mod 10 = 5
p(8) = ( 11*5 + 3 ) mod 10 = 58 mod 10 = 8
p(9) = ( 11*8 + 3 ) mod 10 = 91 mod 10 = 1
p(10)= ( 11*1 + 3 ) mod 10 = 14 mod 10 = 4 = p(0) [cycle closed]

Ok, not really random (it goes with stride 3), but it gets better
for larger N and larger c.
http://www.math.utah.edu/~alfeld/Random/Random.html contain a Java
applet to play with.
http://www.library.cornell.edu/nr/bookcpdf/c7-1.pdf illustrates the
standard tricks to improve random number generators, and tips on
the choice of a and c.  

All this is quite offtopic, but you asked the question ;-)

furio

> 
> Ok.  I think this record rotation may easily be done.  Hopefully
> this week.

That would be great!

furio