Subject: [dhcwg] RFC 3315 message re-transmission query

From: ravi kumar <[email-masked]>
Date: Tue, 3 Nov 2009 16:32:26 +0530

Thanks a lot to people in forum for promptly answering my queries.
I have one more query regarding calculation of Retransmission time-out in
Section-14 of RFC 3315:

 RT for the first message transmission is based on IRT:
      RT = IRT + RAND*IRT
   RT for each subsequent message transmission is based on the previous
   value of RT:
      RT = 2*RTprev + RAND*RTprev

Do RTprev value used in subsequent calculation of RT, include randomization
added by RAND ?
I guess should not be the case, because the retransmission algorithm is
exponential back-off algorithm and incase RAND is added multiple levels in
calculation of RT,this exponential nature is lost.
I have done simple Math in calculating maximum and min waittimes for REQUEST
message, by considering "RTPrev includes RAND" :
0.9 ---   1.1
1.711 --- 2.31
3.249 --- 4.851
6.1731 -- 10.1871
11.72889 --- 21.39291
22.284891 --- 44.925111                            -> The time difference
here is very large here

I consider Retransmission wait times to be exponential wait times, with
randomization factor included to minimize synchronization of messages
transmitted by DHCP clients. In that case, calculation of RT should involve
RTPrev (without Random factor) + Random factor.

Please correct me if I am wrong in my assumption.

regards
Ravi

---

From: Johan Bosaeus <[email-masked]>
Date: Tue, 3 Nov 2009 13:43:15 +0100

> calculation of RT,this exponential nature is lost.

I don't think the exponential back-off is really lost. It's just that the 
exponential back-off is overloaded with a randomization that is sort of 
proportional to the backoff. I.e. the more attempts you do, the larger the 
back-off and the larger the randomization is.

> I have done simple Math in calculating maximum and min waittimes for
> REQUEST message, by considering "RTPrev includes RAND" :
> 0.9 ---   1.1
> 1.711 --- 2.31
> 3.249 --- 4.851
> 6.1731 -- 10.1871
> 11.72889 --- 21.39291

Isn't is so that the standard recommends a maximum of 30 seconds backoff. From 
that point the maximum spread is +-3 seconds.

- Johan

-- 
Johan Bosaeus
Weird Solutions
tel: +46 8 758 3700
fax: +46 8 758 3687
http://www.weird-solutions.com

---

From: ravi kumar <[email-masked]>
Date: Wed, 4 Nov 2009 12:17:37 +0530

Agreed. My question is more related to calculation of RT values, when RT <
MRT.

On Tue, Nov 3, 2009 at 6:13 PM, Johan Bosaeus <[email-masked]>wrote:

> _______________________________________________
> dhcwg mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dhcwg
>

---

From: "David W. Hankins" <[email-masked]>
Date: Wed, 11 Nov 2009 19:00:51 -0800

>  RT for the first message transmission is based on IRT:

Yes, with the proviso that in Solicit RAND is strictly greater than
zero (so, between 0 and 0.1 non-inclusive).

>       RT = 2*RTprev + RAND*RTprev

That is as the RFC says, here is our code for the timeout-advance
function (comments elided):

        client->RT += client->RT + dhc6_rand(client->RT);

        if ((client->MRT != 0) && (client->RT > client->MRT))
                client->RT = client->MRT + dhc6_rand(client->MRT);

dhc6_rand() is a function that returns a negative-to-positive range
integer based on the input (input 100, get a random number in the
range [-9..9]) to conform to being "between -0.1 and +0.1" times the
value.

> Do RTprev value used in subsequent calculation of RT, include randomization

Yes.  RTprev is the previous RT derived and carried.

As you can see above this is what the ISC dhclient does.

> calculation of RT,this exponential nature is lost.

The RT is linear (X=2X + Y), but that linearly growing addition to the
timeout means that the delay becomes exponentially larger (0, 1, 3, 9,
21 is not linear).  So I am not sure what you are asking?

> message, by considering "RTPrev includes RAND" :

Although RFC 3315 isn't clear on the subject, it refers to RAND
as being a value "between" -0.1 and 0.1.  It does not specify that
it is inclusive, therefore strictly adhering to the definition of the
term 'between', it is non-inclusive.  To be between -0.1 and 0.1 the
value cannot be either -0.1 or 0.1.  But it may be zero (except again
in Solicit).

But this is a pretty small matter, and probably is not a compatibility
issue. ;)

First, it is much worse in systems with integer math limitations (not
performing floating operations, and potentially granular to seconds).
There is basically no random dispersion until the RTprev is greater
than 10, it always follows 1,2,4,8,16, and then starts to show some
dispersion ([31..33] because 16 / 10 is 1.6 so values [-1..1] become
possible).

Second, although the spread in seconds might be large, the probability
of any given number between that spread depends upon the granularity
of the client's clock (or the math being applied to the client's
clock), throughout the progression of their RT value.

Which we can't govern, and often neither can the DHCPv6 software
implementer.  You just get what you're given sometimes.

RFC 3315 doesn't mandate a clock granularity.  In some places
(OPTION_ELAPSED_TIME for example) it refers to 1/100ths of a second.
So it is even possible that implementers will only maintain centi-
second granular timing even though their systems are more capable.

This vastly reduces the number of 'steps' a client may reach between
the RT value ranges, so it increases the probability of collisions.

Avoiding clients broadcasting all at the same time being the object
of the backoff timer.

Basically in summary you are looking at the range of dispersion being
very wide.  This is a good thing when you consider that the clock
granularity may unfortunately be arbitrarily large.  What you want to
look at in terms of the health of the RT-advancement function is how
many possible RT values are in-between the ranges you specify
(considering the granularity of the values being used as clocks) on
average.  There may only be 22 steps between [22...44] if the system
can only do whole seconds, which is a worst case scenario, but it
mixes into the 'average' of the client population you see on your
networks.

> Please correct me if I am wrong in my assumption.

I'm not sure which is the assumption but hopefully I have made it
more clear:  RTprev is the RT value previous derived and carried, not
any interim value that is not otherwise declared in the RFC to have a
name.

But whatever you actually do it will probably not affect
compatibility. :)

-- 
David W. Hankins	"If you don't do it right the first time,
Software Engineer		     you'll just have to do it again."
Internet Systems Consortium, Inc.		-- Jack T. Hankins