Subject: Re: RFC 2782: SRV weight evaluation

From: Stuart Cheshire <[email-masked]>
Date: Wed, 11 Jul 2001 21:17:56 -0700

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

Yes, you are right. That was what I meant.

My unstated assumption was that after trying to contact a server and 
failing, that record is removed from the list and the process is 
repeated. After all the non-zero weight records have been tried and 
failed and removed, the zero-weight records are no longer "in the 
presence of records containing weights greater than 0", so they are now 
eligible for selection.

Perhaps this wording is better:

---

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

When there are no more records remaining present in the list with weights 
greater than zero (because all servers with non-zero weights, if any, 
have been tried already, and failed, and therefore removed from the list) 
any records still remaining (i.e. those with weight zero) should then be 
tried in random order.

---

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: "Levon Esibov" <[email-masked]>
Date: Thu, 19 Jul 2001 10:22:39 -0700

Stuart,

We had similar discussion a year ago and agreed to clarify the text to
indicate that the "uniform random number" stands for "uniform random
real number". Please, see the latest update to RFC 2782 at
http://search.ietf.org/internet-drafts/draft-ietf-dnsext-rfc2782bis-01.t
xt.=20

Levon

-----Original Message-----
From: Stuart Cheshire [mailto:[email-masked]]=20
Sent: Friday, June 15, 2001 6:45 PM
To: [email-masked]
Subject: RFC 2782: SRV weight evaluation

>   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=20
intuitive meaning, then (in the presence of records containing weights=20
greater than 0) records with weight 0 should *never* be selected. It=20
should make no sense to mix zero and nonzero weights in one RRSet. SRV=20
already supports 16-bit weights, so one server can be preferred 65535=20
times as much as another -- i.e. one server used for 99.998% of all=20
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)"=20
intended to imply a uniform random integer, or a uniform random real
(aka=20
floating point)?=20

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=20
other SRV records remain at the same priority) is strictly zero, which
is=20
fine, and logical.

However, floating point calculation is sometimes less efficient to=20
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=20
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)",=20
the values 0 and 1 are equally likely:

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

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

To give another example, consider this, where each SRV has the same=20
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)",=20
the values 0, 1 and 2 are all equally likely:

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

Here, "mailer1" gets twice as much load as "mailer2" -- again, probably=20
not what the sysadmin had in mind when he or she set up equal relative=20
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,=20
and it is the extra "+1" that is skewing the results. The text can be=20
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.
>=20
> 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=20
resorting to floating point arithmetic. In fact it is better, because
all=20
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=20
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=20
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.

---

From: Stuart Cheshire <[email-masked]>
Date: Thu, 19 Jul 2001 19:54:35 -0700

>xt. 

I am very puzzled Levon. I mean that sincerely.

I suggested a tiny change to the wording that gives mathematically 
precise results using simple integer arithmetic.

Your response was to change the spec to use real arithmetic.

No computer ever made can do real arithmetic. All computers use floating 
point (or rational) arithmetic which is just an approximation of real 
arithmetic. Any student of numerical analysis will tell you that 
estimating the deviation of floating point arithmetic from real 
arithmetic is very hard, so it is not always even obvious how imprecise 
the approximation is. Also, floating point arithmetic is more costly to 
compute than integer arithmetic on many processors.

Why would you prefer an inaccurate costly algorithm when there is a 
precise cheap one available?

I have enough respect for you that I know it can't be "Not Invented Here" 
syndrome, but I just don't understand your objection.

>   than 0, records with weight 0 should have a very small chance of

If the statistical weight of a record is going to be proportional to its 
"SRV weight" (tautologically true, I hope) then records with weight 0 
should have zero weight. They should *never* be selected, while records 
at the same priority with non-zero weight remain. Why say "a very small 
chance"? That's like saying that a particle with zero mass should have "a 
very small chance" of experiencing gravitational attraction. That's not 
what zero means. Zero does not mean "very small".