Subject: [Roll] reliability metrics for digital radios

From: Richard Kelsey <[email-masked]>
Date: Fri, 09 Oct 2009 10:07:11 -0400

Below is a discourse on the reliability characteristics of
802.15.4 and similar digital radios and what this means for
link metrics.  Even if the goal is to maximize something
other than reliability, you still need the links to be
reasonably reliable in order to reduce churn and because no
matter what the metric, broken routes have little utility.

Non-radio links, or other types of radios, will have very
different characteristics.  This may make it difficult to
have a good relibility metric that is independent of the
link layer.

----------------
Digital radios

802.15.4 and similar digital radios have the property that
packet reliability falls off fairly quickly over a short
range of signal quality.  A link that is working very
reliabily, with near 100% packet delivery, may degrade
quickly with only a small increase in the local radio noise
or small change in the physical environment.  For example, a
link with consistent, near-100% reliability may disappear
entirely if one of the radios is moved as little as a few
cm.

Very crudely, the packet reliability graph looks something
like this:

100%                    ______________________
                       /
 50%                  /
                     /
  0%________________/                        
                                         
   increasing signal-to-noise (SNR) ratio -->

Nearby radios can be far off to the right on this graph.

As the local environment changes, the SNR for any particular
link moves up and down (left and right on the graph).  This
only matters if the change is sufficient to move the link's
current SNR into the vicinity of the cliff.  If so, the link
may lose a significant percentage of packets.  If not,
almost all packets are delivered.

Links at the cliff or to the left are useless.  Even if some
packets are getting through, a very small change in the
environment can break the link completely.  All links well
to the right are all essentially equivalent; they can be
expected to work every time.  Links just to the right of the
cliff are questionable; they work now but their future
performance is uncertain.

100%                    ______________________
                       /
 50%                  /
                     /
  0%________________/                        
                                         
   <---- useless --------|---- okay -----|--- good --->

In the short term, packet reliability measurements cannot
distinguish between okay and good links, because the short
term differences in reliability are not significant.  They
can be distinguished by comparing the RSSI of incoming
packets with the current noise floor.  Counting chip errors
can help, as chip errors show up somewhat before packets
start to be lost.  Whether or not they show up far enough to
the right to be used to tell the difference between 'good'
and 'okay' links is not clear.

----------------
What does this mean for link reliability metrics?  

One point is that tracking observed packet reliability is of
limited use.  In the short term 'okay' links may look just
like 'good' links and longer term averages may not react
quickly enough to be useful.

The main point is that, if you stick to good links, you will
probably do all right just using hop count.  All good links
will have about the same success rates in the short or long
term.  The trick is to tell the good links from the merely
okay ones.

I believe that the white bit in the four-bit link estimator
[1], has the effect of keeping traffic mostly on good links.
Good links have few chip errors, okay links will likely have
more.  It appears that the four-bit link estimator does not
do any averaging of the white bit.  It would be interesting
to determine how much of its performance is due to the use
of the white bit and how much to its ETX estimation, and if
it could be improved by averaging the white bit over time.

The 'okay' links cannot be ignored, as they are actually
working at the moment and may be the only thing keeping the
network connected.  Any additive metric has to define how
many good links are equivalent to one okay one.  This isn't
easy to do, because we would really prefer to use an okay
link only if there is no path using only good links.  Except
in very unusual topologies, it is unlikely that you will
ever be faced with a choice between one okay link and, say,
five good ones.

The simplest metric that maintains this distinction would be
the number of good links and the number of okay ones, kept
as separate values, with the okay link count having
precedence over the good link count (the good counts are
only considered if the okay counts are equal).  More
fine-grained metrics are obviously possible, and are likely
to provide some benefit, so long as they strongly prefer
good links over okay ones.

                                     -Richard Kelsey

[1] R. Fonseca, O. Gnawali, K. Jamieson, and P. Levis. "Four
Bit Wireless Link Estimation." In the Proceedings of the 6th
Workshop on Hot Topics in Networking (HotNets-VI), 2007.

---

From: Mukul Goyal <[email-masked]>
Date: Fri, 9 Oct 2009 10:53:34 -0500 (CDT)

Some time back, we did the following calculations:

1) use standard formulae to obtain bit error rates (for O-QPSK under AWGN, Raleigh and Rician fading models) for different SNR values
2) convert bit error rates to symbol error rates (using the Hamming distance among valid symbol codes (32 chip long) 802.15.4 uses)
3) convert symbol error rates to packet error rates (assuming 127 byte packets)

The resulting graphs with SNR on x-axis and bit/symbol/packet error rates on y-axis can be seen towards the end of:

www.cs.uwm.edu/~mukul/rssi.doc

They basically confirm what Richard said about the rapid change in packet error rates with slight change in SNR.

Thanks
Mukul
----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: [email-masked]
Sent: Friday, October 9, 2009 9:07:11 AM GMT -06:00 US/Canada Central
Subject: [Roll] reliability metrics for digital radios

----------------
Digital radios

                                         

                                         

----------------

                                     -Richard Kelsey

[1] R. Fonseca, O. Gnawali, K. Jamieson, and P. Levis. "Four
Bit Wireless Link Estimation." In the Proceedings of the 6th
Workshop on Hot Topics in Networking (HotNets-VI), 2007.
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: Jonathan Hui <[email-masked]>
Date: Fri, 9 Oct 2009 09:06:47 -0700

Hi Richard,

I agree that it is useful to discern between "okay" and "good" links.

> it could be improved by averaging the white bit over time.

The current tinyos-2.x implementation on the TI CC2420 uses the  
radio's chip correlation feedback.  It doesn't use the RSSI, let alone  
compare it to the current noise floor. As you suspected, the  
implementation also does not do any averaging over time and given that  
CC2420's chip correlation value has high variability, averaging is  
likely to help.  But in my experience, chip correlation is still a  
better measure of PRR than SNR.  Said differently, chip correlation  
does not adequately distinguish "okay" and "good" links well.

> ever be faced with a choice between one okay link and, say,

Mostly agree with this.  One practical concern we have run into with  
utilizing "okay" links is that network deployment/maintenance becomes  
more complex for the end-user.  If "okay" links are required for  
connectivity, the network will appear to function well at times but  
not others.  For some end-users, it may be better not to function at  
all if "okay" links is all you have when joining a network.

> good links over okay ones.

Maintaining the distinction seems like a reasonable approach.

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Fri, 9 Oct 2009 12:21:52 -0700

On Oct 9, 2009, at 8:53 AM, Mukul Goyal wrote:

> 1) use standard formulae to obtain bit error rates (for O-QPSK under  
> AWGN, Raleigh and Rician fading models) for different SNR values
> 2) convert bit error rates to symbol error rates (using the Hamming  
> distance among valid symbol codes (32 chip long) 802.15.4 uses)
> The resulting graphs with SNR on x-axis and bit/symbol/packet error  
> rates on y-axis can be seen towards the end of:
>
> They basically confirm what Richard said about the rapid change in  
> packet error rates with slight change in SNR.

Yes, the curve is sharp. Figure 8 in this paper[1] shows the curve  
found from direct measurements on two 15.4 nodes using a shielded  
environment and a variable attenuator. It shows a similarly sharp  
curve (theory and practice agree).

But be careful -- both the analysis and measurement assume that there  
is no interference, something which an LLN cannot assume. It is  
possible to have a very high SINR and a poor packet reception ratio.  
While very small swings in signal strength can make wireless links  
transition from poor to good or vice versa, interference can easily  
have a much more gradual effect.

Phil

[1] Kannan Srinivasan, Prabal Dutta, Arsalan Tavakoli, and Philip  
Levis. "An Empirical Study of Low-Power Wireless." To appear in "ACM  
Transactions on Sensor Networks." http://sing.stanford.edu/pubs/tosn.pdf

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 14:46:18 +0200

Hi Richard,

> matter what the metric, broken routes have little utility.

Yes, just to make sure that we are in line, there are two orthogonal  
aspects here:
1) Link UP/DOWN: if indeed, the link quality crosses some threshold it  
can be put in DOWN state locally by the node
2) If the Link stays in DOWN state for some period of time, the node  
may decide to update the metrics in its RA-DIO.

> have a good relibility metric that is independent of the

Yes but ... RPL is L3 thus we want path to be calculated according the  
link reliability (and I think that we all agree on
this requirement), this is what we need to do. And I agree, this is  
not easy, the idea is to have a good enough way to
abstract the link reliability using a single metric. The way to  
compute that metric is implementation specific and L2
dependent, which is fine.

Absolutely. Note that this is also true for some PLC links in some  
conditions. And the goal is not to provide near real time
information but a trend. I looked at many traces and one can clearly  
see a trend for each of them. WE now need to find
the right unit.

> Very crudely, the packet reliability graph looks something

Right. We want to provide a macroscopic view, over some period of  
time. If the link flaps, this should not filter out,
if this becomes fairly common over some period of time, we want to  
reflect this.

> performance is uncertain.

Yes, this might be a way to represent the quality, with a simple 4-bit  
flag.
Alternatively we can use the ETX value derived from L2, thanks to  
probing, ...

> and 'okay' links is not clear.

Well that depends ... the local policy function may say "prefer good  
links"
except if the hop count is reduced by 50% then try to use OK links.

> only considered if the okay counts are equal).

Right

> More

Should we try to use the ETX and couple it with filtering to get the  
result of
distinguishing OK links with Good links ?

Cheers.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 12 Oct 2009 10:26:14 -0400

JP,

   From: JP Vasseur <[email-masked]>
   Date: Mon, 12 Oct 2009 14:46:18 +0200

   > matter what the metric, broken routes have little utility.

   Yes, just to make sure that we are in line, there are two
   orthogonal aspects here:
   1) Link UP/DOWN: if indeed, the link quality crosses some threshold
   it can be put in DOWN state locally by the node
   2) If the Link stays in DOWN state for some period of time, the
   node may decide to update the metrics in its RA-DIO.

My point is that the key metric for reliability is not the
RTX for a message right now, or any similar metric, but an
estimate of the stability of the link itself.  We need to
preferentially use stable links.

This is independent of what a node does when a link actually
does stop working.

   > have a good relibility metric that is independent of the

   Yes but ... RPL is L3 thus we want path to be calculated
   according the link reliability (and I think that we all
   agree on this requirement), this is what we need to
   do. And I agree, this is not easy, the idea is to have a
   good enough way to abstract the link reliability using a
   single metric. The way to compute that metric is
   implementation specific and L2 dependent, which is fine.

There may not be a single metric that we can use.  In
particular, for 802.15.4 radios, both stability and
latency/power must be taken into account.  We have to
strongly prefer links that are stable (to avoid churn) and
links between always-on devices (to minimize battery use and
latency).  These may be specific to 802.15.4, but they are
the overriding concerns for those networks.  I do not see
how they can be collapsed into a single value.  A single
metric is possible, but it will likely have to contain
distinct stability and power/latency values.

   Should we try to use the ETX and couple it with filtering
   to get the result of distinguishing OK links with Good
   links ?

I do not see how ETX can capture the desired information.
ETX averaged over the short term can't measure long term
stability.  ETX averaged over the long term can't tell
you which links are currently usable.  I am not sure what
you mean by 'filtering' here.

                              -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 12 Oct 2009 10:32:09 -0400

Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Fri, 9 Oct 2009 09:06:47 -0700

It make sense to ignore 'okay' links when deploying a
network or determining long-term connectivity.  The whole
point is that reliability depends on having some margin for
link degradation.  By the same token, when it comes to
actually forwarding packets, we cannot afford to ignore
links that have degraded since the network was deployed.

                                -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 12 Oct 2009 14:32:25 -0400

From: Philip Levis <[email-masked]>
   Date: Fri, 9 Oct 2009 12:21:52 -0700

I am sorry, but I am not sure what you are saying.
What is the property of interference that causes this
more gradual effect?
                              -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Mon, 12 Oct 2009 14:54:06 -0700

> preferentially use stable links.

If the DAG can reconfigure very quickly, then the need to prefer  
stable links disappears. E.g., there's a paper appearing in SenSys  
this year (Bursty Traffic over Bursty Links) that finds using very  
transient links can reduce path length and improve throughput.

If the DAG cannot reconfigure or repair quickly, then stable links are  
important. But by constraining a protocol to only using stable links,  
we would lose any possible benefits of rapid recovery. This seems like  
putting the horse before the cart.

Phil

---

From: Philip Levis <[email-masked]>
Date: Mon, 12 Oct 2009 14:57:58 -0700

> What is the property of interference that causes this

I am an 802.15.4 transmitter. I have an 802.11b transmitter that uses X 
% of the channel, such that Y% of transmitted 802.15.4 packets are  
clobbered by 802.11. X may be smaller, greater, or equal to Y,  
depending on all kinds of effects. But the two are proportional, and  
as X can range from zero to close to 100%...

Put another way, a lightly utilized 802.11b network might cause a few  
losses, while a heavily utilized one could cause many losses. And this  
can change quickly.

The same is true for other unlicensed frequency bands, where there can  
be analog and/or digital interferers.

Phil

---

From: Tzeta Tsao <[email-masked]>
Date: Mon, 12 Oct 2009 18:47:13 -0400

Hi Richard,

I wonder if SNR is as useful when the noise is not AWGN, and similarly 
SINR. In addition, there are factors such as coding, even if only 
repetition code, to take into account when translating BER to packet 
error rate.

Of course, the question eventually is still the reliability of the link 
metric. The metric could be stringent to retain only very good links, 
suitable maybe for larger networks. Or, the threshold could be lower 
allowing the use of less reliable links, suitable maybe for smaller 
networks.

My 2c.

Regards,
Tzeta

---

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Oct 2009 05:49:15 +0200

Hi Richard,

> This is independent of what a node does when a link actually

Completely agreeing with you.

> distinct stability and power/latency values.

Again agreeing ... and the metric ID is specifying a set of metrics.  
In any case, applications
will require different metric according to the OF and an OF may  
require multiple metrics.

> you mean by 'filtering' here.

I meant two things:
1) There are many ways to compute the ETX (implementation specific)
2) Short transient issues may not have to be captured by the ETX: some  
transient
events may be filtered out by a node.

What is your preference in term of reliability metric ?

Thanks.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 13 Oct 2009 14:20:14 -0400

From: Philip Levis <[email-masked]>
   Date: Mon, 12 Oct 2009 14:54:06 -0700

That's an interesting paper, but I think it supports my
point that the core routing needs to use stable links
when possible.  In the paper they set up a base tree
using stable links and then opportunistically skip ahead
using transient links as available.  Distinguishing between
stable and bursty links is the key to what they are doing.

I do not think anyone has proposed that we constrain
the protocol to only using stable links.  I do think
that attempting to have at least a tree of stable links
is important.  One possibility would be to have the
preferred parent be one connected by a strong link,
but allow other parents to use less stable, and
hopefully longer, links.  This would allow a middle
ground between reliability and efficiency.

                                -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Oct 2009 18:13:48 -0700

On Oct 9, 2009, at 9:06 AM, Jonathan Hui wrote:

> radio's chip correlation feedback.  It doesn't use the RSSI, let  
> alone compare it to the current noise floor. As you suspected, the  
> implementation also does not do any averaging over time and given  
> that CC2420's chip correlation value has high variability, averaging  
> is likely to help.  But in my experience, chip correlation is still  
> a better measure of PRR than SNR.  Said differently, chip  
> correlation does not adequately distinguish "okay" and "good" links  
> well.

Right -- the assumption is that the real link estimation is with  
packets. Receiving a packet with a very high chip correlation index  
means that the link *at that time* had a high SNR, meaning it is  
likely a good enough link to try (white bit set). If the white bit  
isn't set, then a link has to go through a little bit of packet-based  
estimation before CTP Noe will try using it.

> utilizing "okay" links is that network deployment/maintenance  
> becomes more complex for the end-user.  If "okay" links are required  
> for connectivity, the network will appear to function well at times  
> but not others.  For some end-users, it may be better not to  
> function at all if "okay" links is all you have when joining a  
> network.

I agree that it's reasonable for an implementation to heavily favor  
"good" links over "okay" links (tradeoff potential efficiency for  
stability), or discard the use of okay links altogether. However, user/ 
application preference of behavior in the presence of only OK links  
should be left out of the protocol specification. Some applications  
would prefer "don't work unreliably" and others would prefer "do your  
best."

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 14 Oct 2009 21:48:27 -0700

On Oct 14, 2009, at 6:13 PM, Philip Levis wrote:

> isn't set, then a link has to go through a little bit of packet- 
> based estimation before CTP Noe will try using it.

My experience with chip correlation is that it can be a leading  
indicator of packet loss, but it's ability to discern 'good' links  
from 'okay' links is limited.  In the end, I think a 'link classifier'  
should use whatever information it can get - that leads me to want a  
metric that doesn't really have a 'unit' but instead identifies a  
'class'.

> stability), or discard the use of okay links altogether. However,  
> user/application preference of behavior in the presence of only OK  
> links should be left out of the protocol specification. Some  
> applications would prefer "don't work unreliably" and others would  
> prefer "do your best."

Of course.  I just wanted to say that there are times when you want to  
ignore and other times you don't want to ignore 'okay' links.

--
Jonathan Hui

---

From: JP Vasseur <[email-masked]>
Date: Thu, 15 Oct 2009 06:15:51 -0700

On Oct 14, 2009, at 6:13 PM, Philip Levis wrote:

>> that CC2420's chip correlation value has high variability,  
>> averaging is likely to help.  But in my experience, chip  
>> correlation is still a better measure of PRR than SNR.  Said  
>> differently, chip correlation does not adequately distinguish  
>> "okay" and "good" links well.
>
>> Mostly agree with this.  One practical concern we have run into  
>> with utilizing "okay" links is that network deployment/maintenance  
>> becomes more complex for the end-user.  If "okay" links are  
>> required for connectivity, the network will appear to function well  
>> at times but not others.  For some end-users, it may be better not  
>> to function at all if "okay" links is all you have when joining a  
>> network.
>

Fully agree ! What we need to define though is how to define the  
metric used to characterize good, OK and bad links, with a unit. That  
could be as simple as a flag, could be ETX, or other forms of metric.  
The "how" the metric is computed is left to implementation and also  
depends on the link layer of course.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 15 Oct 2009 06:18:49 -0700

On Oct 14, 2009, at 9:48 PM, Jonathan Hui wrote:

> from 'okay' links is limited.  In the end, I think a 'link  
> classifier' should use whatever information it can get - that leads  
> me to want a metric that doesn't really have a 'unit' but instead  
> identifies a 'class'.

That is the flag approach that I was referring to. Classification  
should then be left to implementation.

> Of course.  I just wanted to say that there are times when you want  
> to ignore and other times you don't want to ignore 'okay' links.
>

True. Should be dictated by circumstances and OF.

Cheers.

JP.