[Olsr-dev] Bug in LQ-Calculation (with patch)

[Sven-Ola Tuecke]

Bernd, Andreas,

(I really should use a spell checker sometimes. Here's a resend)

yep. Formula works only, if winsize can be divided by 4. Because the 
expression already includes a "use old formula if winsize < 8", I would 
simply extend with "also use old formula if 0 == winsize % 4. *And* change 
the default winsize to 8 or 12. No further complaints.

That's also a matter of sensible defaults. The olsrd.org LQ implementation 
currently defaults to the (ETX Measurement) Winsize of 10. Multiplied by 2 
seconds HelloInterval. So stable links after ~ 20 Seconds. Which is fine. At 
least for a small mesh ~ 16 - 32 nodes. Those defaults are for real-mobile 
users (e.g. surfing-by-bike or so).

Here in Berlin we needed to optimize in the past. We have a lot of bad links 
and constantly changing ("weather") conditions all over the day. To cope 
with this, we elongated the measurement period (using a ETX meas Winsize of 
128) to get more exact results. Gets us around the principal measurement 
error of using olsr-message-loss instead of wifi-packet los. OK. Multiplied 
by our default HelloInt=6.0 -> Stable Links after 12 minutes. Reason for new 
formula. Yes - we sayed goodbye to be real mobile - we do not surf by bike 
any more. All of our nodes are in a stable position on the roof or so <ggg>

Ah - calculation is rather often, but should be in the range a standard 
embedded device can handle reals...

// Sven-Ola

"Bernd Petrovitsch" <(spam-protected)> schrieb im Newsbeitrag 
news:(spam-protected)
> On Thu, 2007-09-06 at 11:39 +0200, Andreas Jacobs wrote:
> [...]
>> I think I've found a bug in the calculation of the link quality, which is
>> done the following way:
>>
>> 1) entry->loss_link_quality =
>> 2) (float)(entry->total_packets - entry->lost_packets) /
>> 3) (float)(entry->loss_window_size < (2 * 4) ? entry->loss_window_size:
>> 4) 4 * ((entry->loss_window_size / 4 - 1) * entry->total_packets +
>> entry->loss_window_size) / entry->loss_window_size);
>
> Sven-Ola is the expert on that formula. The last discussion produced the
> result that
> it works only correctly if "windowsize % 4 == 0" and there was IMHO no
> clear agreement
> on how to fix it:
> - I (personally) would simply require "windowsize % 4 == 0" as I see no
> reason that
>  every prime number must be usable for this. If I want "50" there, I
> can as well
>  use "52" (or "48").
>  And I would tell that the user upon startup an exit if it is
> configured wrongly.
>  Of course, defaults and docs must be adapted (if necessary).
>  For a transition period, we could add big fat log messages and a 5
> seconds penalty
>  on startup to motivate folks to fix their config.
> - Sven-Ola would automatically increase(IIRC) the configured number to
> match the
>  above condition.
>  I'm not a friend of automatically tweaking the users/admins config so
> that it
>  works.
>  *eg* Well, we could apply the "transition" thing from above here too.
> - If your "float" fix is correct (Sven-Ola?), I can live with that too,
> if:
>  * it is not calculated that often (since floating point operations
> tend to be
>    slower than bit shifts on integers).
>  * we cast some result back to int somewhere so the not 80% of the
> formula is
>    needlessly float (basic C: if an subexpression is float, the
> expression using the
>    result uses float).
> - Reverting back to the simple one takes a long time to converge if the
> window size
>  is large.
> - Please fill in: _________________________________________
>
>> Please assume a perfect link for now that does not loose any packets. It
>> should have a link quality of 1.
>> If we set loss_window_size to 10 (the default) and wait for a while, then
>> total_packets will become 10, too, and lost_packets will be 0. So the
>> numerator (line 2) will equal 10 and so should the denominator, but the
>> denominator gives only 8, giving a link quality value of 1.25!
>> The reason might be, that "entry->loss_window_size / 4" is an integer
>> division, which gives 10 / 4 = 2 and not 2.5!
>>
>> Proposed solution:
>>
>> Convert that integer division to a floating point division. However, I'm
>> not quite sure, if this is correct, because I haven't fully understood 
>> the
>> formula
>
> Bernd
> -- 
> Firmix Software GmbH                   http://www.firmix.at/
> mobil: +43 664 4416156                 fax: +43 1 7890849-55
>          Embedded Linux Development and Services
>
>
>
> -- 
> Olsr-dev mailing list
> (spam-protected)
> http://lists.olsr.org/mailman/listinfo/olsr-dev