[Olsr-dev] Thoughts about an ETX-FF-Metric plugin

Thu Jun 19 17:09:20 CEST 2008

On 6/19/08, Henning Rogge <(spam-protected)> wrote:
>
> Am Donnerstag 19 Juni 2008 14:18:44 schrieb Markus Kittenberger:
>
> > imo its a bad idea to start routing again over a link 15 seconds after he
> > was disastrous, even when the link is disastrous every 30 seconds, just
> > because we have forgotten this already,..
>
> That's right... especially for networks with mobile nodes.
>
>
> > if al link only once is lossy for some seconds, my approach would let him
> > recover to nearly the LQ he had before quite fast.
>
>
> > ...
>
> The example looks fine. :)
>
>
> > > hmm... maybe we could use the "hello-timeout" value here...
> > ack
> >
> > > The algorithm should work for small networks too... and in small
> networks
> > > you have only a few packets per second.
> >
> > it will work in small networks, if the base for calculating the LQ values
> > which goes into the exponential window is >= the hello timeout
> > and if the algorithm for the first averageing (on interval doubling)
> checks
> > how much data it has before deciding which fields it averages,..
>
>
> Let's see... we have to tuning parameters for links. Hello-Interval (should
> be
> related to the mobility of the node and it's neighbors) and Hello-Timeout
> (something like the "maximum memory" of a link).
>
> Do you think we could use this two arguments to get reasonable values for
> your
> model ?

this two parameters are very important for the size/layout of the first
linear window,.. and the first averaging function,..

one question, how do you now the hello timeout of your neighbours, do they
put them into their hello messages?

the exponentially part of the window, has it`s own tuning paramters, which
once we found good values should be quite ok for most networks
maybe one total history length/duration parameter makes sense (in seconds)
(may be useful for example if you know you`ve got some (too long shots) of
5ghz bridges which tend to repeatedly-completely fall out in bad weather
situations)
(the old window size could be even used as input for this
(total_history_duration=hello_interval*window_size)

I will see if I can implement this algorithm during the weekend or maybe
> next
> week.

i can deliver a pseudocode sample, or working simulation in java(script) or
so, but as i only code in c only about 1% of my coding time, i think it`s
better you implement it in c,.. (-;

> MArkus
> >
> > #
> > for the event of an restarting neighbouring olsrd, detectable through
> > (unexpectedly) new/low sequence numbers, the link sensing could handle
> > this, with deleting the history (at least the parts containing 100% loss

i prefer do delete only the affected parts of history (timeslots younger or
equal than the last received packet, which is quite equivalent to deleting
every timeslot younger or equal to the youngest timeslot having lq > 0, when
a large jump is detected)

deleting the fron part of the history, has also the side effect (depending
on implementation) of (indirectly) reducing the weight of the remaining
parts, as the get rerated/moved from 48 seconds time slot (which will stay
the same for 48 seconds) maybe even down to 12 second time slots, which will
be summarized soon,..
(i´m not sure if this is a good side effect or not, or negligible)

also a question is how to handle large jumps caused by anything else than
a reboot (changing antenna, someone standing in front of antenna,.. (-;)

if this difference (from a reboot) is detectable depends on whether the
olsrd starts with sequence number 0 or with a random number,..

> due to the reboot of the device)
>
> If it was just a reboot we might just "jump" to the new sequence number, no
> need to kill the history.

the problem is that when the algorithm finds out it was a reboot he has
already filled parts of the history with the low lq values, he generated
with every lq timeout

If it was a long downtime, the link will have timed out and we will start
> with
> a fresh history.

ack, otherwise it would be gone anyways

of course it may make sense to keep history longer then the link timeout,
depending non how short the link timeout is

a link timeout (at which definitely no route will use this neighbour) makes
much sense with this history algorithm,..
than for example while after 12 seconds the lq has dropped to 50% of his
"original" value
it still has LQ of about 37,5% after 30 seconds
after 66 seconds 25%
and after 138 seconds it`s still 12,5%

in this case ETX values drop linear and not quadratic as usual, as on a
completely dead link the nlq is freezed,.. while in reality (if its no
unidirectional link) the lq at the neighbour drops too,..

using a steeper history with only 13 timeslots
(3,3,3,3,6,6,12,12,24,24,48,48,96)
(history duration of this layout is 288 seconds instead of 282 secnds in 16
slots (3,3,3,3,6,6,6,12,12,12,24,24,24,48,48,48))

improves this just negligible to this values:
30: 36,1%
66 23,6%
138 11,5%

so this helps nearly nothing, while having side effects at the
whole history,..
in fact imo dead links are better handled with a simple link timeout,..
(below is an adjustment of the algorithm to handle this and nearly dead
links (e.g. 90% loss) better)

dispite the fact that this history function remembers/weights bad thing
better than good times, when starting with a histroy full of "good times",
it clearly takes the full 280 seconds to reach lq 0,
and connot compete against a shorter history in this special case,..

a method to improve this algorithm on lowering the lq deeper on desastrous
situations (this includes but is not limited to dead links) would be to use
the very old part (last quarter (= last 3-4 time slots)) of the history only
when their values are lower than the newer parts:
that means oLQ would be split into an old and a new part, comparing them
before deciding whether to use the old parts,..

this would reach lq 0 in 96 seconds (ignoring last 3 of 13), respectively
114 seconds (ignoring last 4 of 16)
after only 48 seconds the LQ would consist of 1/6 of the old "good" value
and to 5/6 of the new "desastrous" value , respectively after 66 seconds the
LQ would be 12,5% on the 16 slot layout

so this function 1. gives bad time slots a heigher weight, and forgets the
good old times, when operating in bad times (-;, but remembers multiple/long
bad times quite long
the conclusion, is an completely pessimistic link sensing, which will only
generate compareable (to <= 0.5.5) lq result on perfect and/or stable links.

but this behaviour the target, and if its too pessimistic, there are some
parameters, which (when misused) can even make it optimistic,..

but remember the old etx code would perform much, much worse on dead links,
98% after 30 seconds, 95% after 75 seconds,..
i would call that blindly optimistic,..

but i think i`ve defined so many parameters so far, that it`s time for an
simulation (-;

> I'm very interested in this idea because it's independant of the
> link-quality
> metric we use. Even with better metrics we could still use this algorithm
> to "smooth" the incoming data.

i know (-;

and it does more than just smoothing (-;

Henning
>
>
> *************************************************
> Diplom Informatiker Henning Rogge
> Forschungsgesellschaft für
> Angewandte Naturwissenschaften e. V. (FGAN)
> Neuenahrer Str. 20, 53343 Wachtberg, Germany
> Tel.: 0049 (0)228 9435-961
> Fax: 0049 (0)228 9435-685
> E-Mail: (spam-protected)
> Web: www.fgan.de
> ************************************************
> Sitz der Gesellschaft: Bonn
> Registergericht: Amtsgericht Bonn VR 2530
> Vorstand: Dr. rer. nat. Ralf Dornhaus (Vors.), Prof. Dr. Joachim Ender
> (Stellv.)
>
> --
> Olsr-dev mailing list
> (spam-protected)
> http://lists.olsr.org/mailman/listinfo/olsr-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20080619/152258c9/attachment.html>