Subject: RFC 2782: SRV weight evaluation

From: Stuart Cheshire <[email-masked]>
Date: Fri, 15 Jun 2001 18:45:19 -0700

>   In the presence of records containing weights greater
>   than 0, records with weight 0 should have a very small chance of
>   being selected.

I think we can improve on this. If weights are to have a sensible 
intuitive meaning, then (in the presence of records containing weights 
greater than 0) records with weight 0 should *never* be selected. It 
should make no sense to mix zero and nonzero weights in one RRSet. SRV 
already supports 16-bit weights, so one server can be preferred 65535 
times as much as another -- i.e. one server used for 99.998% of all 
queries and the other used for less than 0.002%. If we really need a way 
to indicate resolution below 0.002%, SRV should use 32-bit weight values.

I suggest the following wording:

>   In the presence of records containing weights greater
>   than 0, records with weight 0 should never be selected.

---

>   To select a target to be contacted next, arrange all SRV RRs
>   (that have not been ordered yet) in any order, except that all
>   those with weight 0 are placed at the beginning of the list.
>
>   Compute the sum of the weights of those RRs, and with each RR
>   associate the running sum in the selected order. Then choose a
>   uniform random number between 0 and the sum computed
>   (inclusive), and select the RR whose running sum value is the
>   first in the selected order which is greater than or equal to
>   the random number selected. The target host specified in the
>   selected SRV RR is the next one to be contacted by the client.
>   Remove this SRV RR from the set of the unordered SRV RRs and
>   apply the described algorithm to the unordered SRV RRs to select
>   the next target host.  Continue the ordering process until there
>   are no unordered SRV RRs.  This process is repeated for each
>   Priority.

Is a "uniform random number between 0 and the sum computed (inclusive)" 
intended to imply a uniform random integer, or a uniform random real (aka 
floating point)? 

If it is a real number, then saying "inclusive" makes no difference, and 
the probability of an SRV record with weight zero being chosen (while 
other SRV records remain at the same priority) is strictly zero, which is 
fine, and logical.

However, floating point calculation is sometimes less efficient to 
implement, and many implementers are likely to select a random *integer* 
(which is also suggested by the use of the word "inclusive"). This leads 
to the following off-by-one bug:

Suppose you have two SRV records, one with weight zero and one with 
weight one:

_smtp._tcp.apple.com 0 IN SRV 0 0 25 dontuse.apple.com
_smtp._tcp.apple.com 0 IN SRV 0 1 25 mailer.apple.com

Sorted List:
dontuse.apple.com Weight 0 Running Sum 0
mailer.apple.com  Weight 1 Running Sum 1

If you now "choose a uniform random integer between 0 and 1 (inclusive)", 
the values 0 and 1 are equally likely:

Value 0 selects dontuse.apple.com (Running Sum 0 is >= Random Integer 0)
Value 1 selects mailer.apple.com  (Running Sum 1 is >= Random Integer 1)

In this example, "mailer" and "dontuse" are equally likely to be selected 
(and hence get half the mail load each) which was probably not what the 
sysadmin had in mind when he or she set up relative weights of zero and 
one. (I realize the desired effect here could have been achieved using 
different priorities, but the point I'm making is that the weights, as 
given in this example, do not yield the intuitive result.)

To give another example, consider this, where each SRV has the same 
weight:

_smtp._tcp.apple.com 0 IN SRV 0 1 25 mailer1.apple.com
_smtp._tcp.apple.com 0 IN SRV 0 1 25 mailer2.apple.com

Sorted List:
mailer1.apple.com Weight 1 Running Sum 1
mailer2.apple.com Weight 1 Running Sum 2

If you now "choose a uniform random integer between 0 and 2 (inclusive)", 
the values 0, 1 and 2 are all equally likely:

Value 0 selects mailer1.apple.com (Running Sum 1 is >= Random Integer 0)
Value 1 selects mailer1.apple.com (Running Sum 1 is >= Random Integer 1)
Value 2 selects mailer2.apple.com (Running Sum 2 is >= Random Integer 2)

Here, "mailer1" gets twice as much load as "mailer2" -- again, probably 
not what the sysadmin had in mind when he or she set up equal relative 
weights.

The problem is the off-by-one bug: If the weights sum to n, then the RFC 
currently says to select one of (n+1) possible different random integers, 
and it is the extra "+1" that is skewing the results. The text can be 
fixed by changing it to say:

> To select a target to be contacted next, arrange all SRV RRs (that
> have not been ordered yet) in any order.
> 
> Compute the sum of the weights of those RRs, and with each RR
> associate the running sum in the selected order. If all RRs have
> weight zero (i.e. the sum is zero), then select any of the RRs at
> random. Otherwise, choose a uniform random integer between 0 and the
> sum computed minus one (inclusive), and select the RR whose running
> sum value is the first in the selected order which is greater than
> the random integer selected. The target host specified in the
> selected SRV RR is the next one to be contacted by the client. Remove
> this SRV RR from the set of the unordered SRV RRs and apply the
> described algorithm to the unordered SRV RRs to select the next
> target host. Continue the ordering process until there are no
> unordered SRV RRs. This process is repeated for each Priority.

Note that the only changes here are:

1. A random integer is selected, instead of a random real
2. The sum is from "zero to n-1", instead of "zero to n"
3. The comparison is "greater than" instead of "greater than or equal"

This modified text produces the mathematically correct result without 
resorting to floating point arithmetic. In fact it is better, because all 
floating point arithmetic is an imprecise approximation of real numbers, 
and usually produces a slightly imprecise result. This integer algorithm 
produces mathematically perfect results, with no rounding errors.

To repeat the above examples again:

First Example

_smtp._tcp.apple.com 0 IN SRV 0 0 25 dontuse.apple.com
_smtp._tcp.apple.com 0 IN SRV 0 1 25 mailer.apple.com

Sorted List:
dontuse.apple.com Weight 0 Running Sum 0
mailer.apple.com  Weight 1 Running Sum 1

Choose a uniform random integer between 0 and n-1 inclusive: The only 
answer is zero.

Value 0 does not select dontuse  (Running Sum 0 not > Random Integer 0)
Value 0 selects mailer.apple.com (Running Sum 1 is  > Random Integer 0)

In this example, "mailer" is used all the time, and dontuse is never 
used. (Correct -- don't mix zero and nonzero weights in one RRSet!)

Second Example

_smtp._tcp.apple.com 0 IN SRV 0 1 25 mailer1.apple.com
_smtp._tcp.apple.com 0 IN SRV 0 1 25 mailer2.apple.com

Sorted List:
mailer1.apple.com Weight 1 Running Sum 1
mailer2.apple.com Weight 1 Running Sum 2

If you now "choose a uniform random integer between 0 and 1", the values 
0 and 1 are all equally likely:

Value 0 selects mailer1.apple.com (Running Sum 1 is > Random Integer 0)
Value 1 selects mailer2.apple.com (Running Sum 2 is > Random Integer 1)

Here, "mailer1" and "mailer2" get equal load. This is correct.

Stuart Cheshire <[email-masked]>
 * Wizard Without Portfolio, Apple Computer
 * Chairman, IETF ZEROCONF
 * www.stuartcheshire.org

to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.

---

From: Andrew Brown <[email-masked]>
Date: Wed, 20 Jun 2001 15:19:47 -0400

>to indicate resolution below 0.002%, SRV should use 32-bit weight values.

as a guess, i'd say that "records with a weight of zero in a record
set with some non-zero weights will end up being selected last in no
particular order".  that is to say, all non-zero weighted records will
be picked first, and then the zero weight ones will be picked.

-- 
|-----< "CODE WARRIOR" >-----|
[email-masked]             * "ah!  i see you have the internet
[email-masked] (Andrew Brown)                that goes *ping*!"
[email-masked]       * "information is power -- share the wealth."