[Tinyos-help] LinkEstimator, link qualities, ETX

[Michiel Konstapel]

Thanks for your input! Great to get feedback "from the source", as it
were. Warning: wall of text coming up.

> > Our thinking was that instead of initializing the qualities and ETX
to zero,
> > wouldn't it be better to set them "halfway"? [...]
> 
> Perhaps values other than 0 are better as initial values. Lets
> consider these CTP/LEEP mechanisms:
> 
> 1. eetx for a link is not available until a link is mature

OK, I see this differs between our version and CVS HEAD. How a link
becomes mature isn't completely clear to me. It's made mature after the
first BLQ_PKT_WINDOW beacons are received?

> 2. you transmit a lot of beacons in the beginning so there are enough
> beacons to bootstrap the values

True, but we have noticed that the outquality increases quite slowly, so
a link which has perfect data delivery still receives a high (4 or more)
ETX estimate from etx = 1/(inq*outq). ETX continues to increase for
several rounds, until inquality and outquality rise high enough to
reflect the link's actual quality. This seems to cause the node to
abandon a perfectly fine link to the sink to try another parent, where
the same thing happens. This continues for a while until the sink's
beacons manage to bring up its outquality to a reasonable level.
However, its ETX difference may then be too small to cause nodes to
switch to it, since a two-hop perfect link won't be replaced by a
one-hop perfect link with a 1.5 threshold.

By initializing the qualities to a "neutral" level, we are trying to
avoid the initial ETX increase. If a link turns out to be bad, the node
finds out quickly enough. DEETX updates will quickly make it switch to
another parent if needed.

> (are you using the router that uses
> Trickle timer to drive the beacons?)

W're using the 2.0.1 Ubuntu release. CtpRoutingEngineP has the following
CVS Id:
/* $Id: CtpRoutingEngineP.nc,v 1.7 2007/04/21 07:02:37 scipio Exp $ */

It seems that's older than the one where the comments refer to Trickle,
though it does use an exponentially increasing beacon interval.

> 3. you will eventually use the link that provides the best delivery
> performance
> 
> So we are talking about initial setup time beyond link maturity? How
> much time?

Setup time isn't too much of an issue as long as we can get a first
packet out the door reasonably quickly, so we can confirm that the node
has joined the network. We are mainly concerned with the initial
"undeserved" ETX boost good links seem to get, which makes it hard to
converge on the best links since it can take many minutes or even hours
to get the qualities up to a decent value, and the ETX back down again,
on beacons alone.

> > Another observation of ours was that after a large number of beacons
(>
> > MAX_PACKET_GAP) is missed, the route qualities are reset, but the
ETX isn't.
> > In cases where a node that is a popular parent (say, the sink) is
turned off
> > for a while, its children will see its ETX skyrocket as they try to
get
> > packets through. When the node comes back online and starts sending
beacons,
> > its old children will reset the link qualities to zero, but leave
the ETX at
> > its inflated value. This means that it will take a very long time
for the
> > node to send enough beacons to make itself look like a viable parent
again.
> > Wouldn't it be better to reset the ETX at the same time as the in
and out
> > qualities? Something like this:
> 
> If you turn the node back on, you are right. But there are some other
> scenarios where what you propose might make things worse - lets say
> the link quality degrades and you slam the eetx value to the ceiling.
> Now, suddenly after more than MAX_PACKET_GAP (lets say after an hour),
> you receive a beacon, and BLQ_PKT_WINDOW consecutive beacons
> immediately after that. Is this link good or bad? If the last known
> etx for this link is a high value, why change it to some arbitrary
> value?

Well, it was good at some point and if it's been gone for an hour,
something on the node or in the environment has changed. The link may
now be good or bad, but if the ETX is left at its high value, no one
will find out. If its ETX is reset, a bad link will be quickly
identified by DEETX, won't it?

I suppose this depends on what failure modes are expected and how they
may be resolved. If one deploys a battery powered network in a field for
taking measurements, a node that's been gone for an hour probably ran
out of juice and won't be back (in which case resetting its ETX won't
matter, either).

However, our networks for sensing/monitoring applications typically
employ a backbone network of wall-powered CTP nodes, which are placed to
ensure good overall links (a link ETX of 2 is considered pretty poor).
Temporary failures should cause nodes to switch parents (for example,
someone parks a truck between a node and its parent, or a node is taken
offline for maintenance), but when a link recovers, so should the tree,
ideally. If a link fails for an extended period of time, this usually
indicates a problem which a technician will need to resolve. When a node
comes back online, presumably the problem has been remedied and other
nodes should be able to use it as a parent again, without having to wait
for several hours of beacons to bring its ETX down. In general, if a
good link completely fails, we can assume that when it comes back, it'll
probably be good again. I understand this may not be a typical scenario
for CTP, though.

> One other detail - if you change inquality, you are changing the
> contribution to etx through the beacons. It is entirely possible that
> we are getting good etx estimate through the data packets while we are
> getting bad etx estimate through the beacons due to potentially
> different timescales at which the channel is sampled through these
> mechanisms. updateNeighborEntryIdx is only concerned with updating the
> beacon based estimate so it would not be appropriate to change eetx
> here because eetx also takes into account data pkt transmission
> statistics.

However, doesn't packetGap > MAX_PACKET_GAP indicate that previous
statistics have expired and can no longer be considered valid?

> > We've done some desktop experiments with INITIAL_QUALITY_ESTIMATE =
180 and
> > INITIAL_EETX_ESTIMATE = 10 and the recovery time improved greatly.
However,
> > we don't have results for larger networks and were wondering if
there might
> > be issues we haven't foreseen.
> 
> I am not entirely convinced that we should optimize this link
> estimator to a scenario in which a link with a good track record
> suddenly becomes unavailable for a while and suddenly it becomes
> available with excellent delivery performance if that optimization is
> done at the expense of poorer response to other types of failure
> scenarios. Does your suggestion make recovery/adaptation worse for
> other types of failure scenarios?

I suppose this is the main point where our expectations may differ from
the more general case, as outlined above. What failure scenarios does
CTP optimize for? An intermittent link would be problematic, if it goes
on and off at longer intervals than the packet gap.

> It would be good to see some numbers across the failure scenarios that
> you considered in your experiments.

At the moment I'm afraid I'm lacking both time and nodes to set up an
experiment, but I hope I'll be able to provide some data later.

Thanks again,
Michiel