Subject: RFC 2782: Off-by-one bug in weighting algorithm

From: Stuart Cheshire <[email-masked]>
Date: Sat, 13 May 2000 18:45:57 -0700

> 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.

When the RFC says "choose a uniform random number..." it doesn't say whether
it should be a real number or an integer. 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, most implementers are likely to select a random *integer* (which is
also suggested by the use of the word "inclusive") and 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 backup.apple.com
_smtp._tcp.apple.com 0 IN SRV 0 1 25 mailer.apple.com

Sorted List:
backup.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 backup.apple.com (Running Sum 0 is >= 0)
Value 1 selects mailer.apple.com (Running Sum 1 is >= 1)

In this example, "mailer" and "backup" 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 >= 0)
Value 1 selects mailer1.apple.com (Running Sum 1 is >= 1)
Value 2 selects mailer1.apple.com (Running Sum 2 is >= 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 numbers, 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.

Stuart Cheshire <[email-masked]>

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

---

From: Robert Elz <[email-masked]>
Date: Mon, 15 May 2000 01:33:47 +1000

Date:        Sat, 13 May 2000 18:45:57 -0700
    From:        Stuart Cheshire <[email-masked]>
    Message-ID:  <[email-masked]>

  | When the RFC says "choose a uniform random number..." it doesn't say whether
  | it should be a real number or an integer. 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.

The intent was that it be a real number, without requiring the
actual use of floating point arithmetic.  Using integer arithmetic
the same basic effect needs to be achieved.

One way might be to use 32 bit integers, with the weight values
multiplied by 10000 (ie: effectively fixed point arithmetic).

Simply doing dumb integer arithmetic on the basic weight values is
likely to produce anomalies, as you noticed.

kre