Subject: Re: [Roll] [manet] Fwd: New Version Notification fordraft-gnawali-roll-etxof-00

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 1 Mar 2010 10:59:33 +0100

Hi Henning:

I share your belief that we can and need to derive more stable
information out of the very dynamic raw data we get from the radio
links. The rank is supposed to be one such information, and because
tuning an adaptive filter is more properly achieved with an heuristical
understanding of the use case, RPL introduces the Objective Functions
that instantiate the generic RPL mechanisms for the specificities of a
use case. The good point here is that there's room for additional OFs
after the RPL spec is released. So (hopefully) you won't hear that RPL
does not work because of such things as hop count, but rather that this
OF applies better than that one for this use case. On the side, I'm sure
that we could learn quite a few things on how to operate our filters
from guys who track curves all day on the stock market ; )

This does not mean that the router should not react upon rapid
variations of the link metrics. The roll fundamentals draft add some
words about that see
http://tools.ietf.org/html/draft-thubert-roll-fundamentals-01#section-6.
2.3. The idea here would be to consider that the filtered metrics are
topological - that is they impact the routing operation - whereas the
transient variations of the link properties are topical - that is the
impact the per packet forwarding decision only.

cheers,

Pascal

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Henning Rogge
Sent: Sunday, February 28, 2010 9:58 PM
To: Marcello Caleffi
Cc: ROLL WG; [email-masked]; Thomas Heide Clausen
Subject: Re: [Roll] [manet] Fwd: New Version Notification
fordraft-gnawali-roll-etxof-00

Am Sonntag 28 Februar 2010 12:33:49 schrieb Marcello Caleffi:
> We should discuss about it. Honestly, I don't know if the 
> post-processing can be independent from the metric dimension, but it
will be a nice idea.
I'm convinced it can be done, especially if the range of raw metric
would be known (0 to 2^24-1 for example). Sliding-Window averaging,
exponential aging, even hysteresis could be considered postprocessing of
the raw link value, not depending what data is represented by the link.

It's similar to ripples objective function I think, just with a little
bit more options.
 
> It was not my intention to discuss against your draft. Until we move 
> towards realistic hypothesis, I am in.
Okay.

> But since there are multiple
> bi-directional connections among the topics: << I want a routing 
> protocol that works also in non-trivial networks <---> routing 
> protocols forward the packets according to routing metrics <---> I 
> need a good routing metric <---> routing metric usually estimates 
> random processes like delivery ratio or round trip time
Packet loss/error rate, delay and bandwith... that are the most common
three generic metric values I think. Signal strength might be a forth
one.

> <---> I need a good estimator >> here I am just exploiting the 
> opportunity provided by your draft to discuss some issues outside from

> my research group.
If you have a good idea how to "smooth/stabilize" the output of a packet
loss measurement without sacrificing lot's of reaction time of the
metric I would be very interested.
The problem with many routing metrics is that they either fluctuate too
much or need to much time to detect change.

Henning Rogge

---

From: Marcello Caleffi <[email-masked]>
Date: Mon, 1 Mar 2010 16:18:12 +0100

Il giorno 28/feb/2010, alle ore 21.58, Henning Rogge ha scritto:

>> We should discuss about it. Honestly, I don't know if the post-processing
>> can be independent from the metric dimension, but it will be a nice idea.
> I'm convinced it can be done, especially if the range of raw metric would be
> known (0 to 2^24-1 for example). Sliding-Window averaging, exponential aging, 
> even hysteresis could be considered postprocessing of the raw link value, not 
> depending what data is represented by the link.
> 
> It's similar to ripples objective function I think, just with a little bit 
> more options.

Of coures you can adopt a blind filtering, however my studies shows that not only the type of raw metric (i.e. rss versus delivery ratios) but also the environment conditions affects the wellness of the filtering. Just as example, if we assume that the shadow-fading effects are the main hostile component in packet delivery, the moving average (Sliding-Window averaging) is the best estimator (trust me, you cannot do better). Otherwise, in presence of correlated hostile effects (i.e. interference or collision in burst networks or node mobility), then exponential aging can (can, since it depends on the parameter setting) outperforms the sliding windows one.

>> bi-directional connections among the topics: << I want a routing protocol
>> that works also in non-trivial networks <---> routing protocols forward
>> the packets according to routing metrics <---> I need a good routing
>> metric <---> routing metric usually estimates random processes like
>> delivery ratio or round trip time
> Packet loss/error rate, delay and bandwith... that are the most common three 
> generic metric values I think. Signal strength might be a forth one.

Both these metrics are random processes. Therefore if one wants deal with routing metric, it is better for him to make a little knowledge about random processes and stochastic theory. Or at least, I need to.

> 
>> <---> I need a good estimator >> here I
>> am just exploiting the opportunity provided by your draft to discuss some
>> issues outside from my research group.
> If you have a good idea how to "smooth/stabilize" the output of a packet loss 
> measurement without sacrificing lot's of reaction time of the metric I would 
> be very interested.
> The problem with many routing metrics is that they either fluctuate too much 
> or need to much time to detect change.

Just a self citation, but there are a lot of other (and better) works about such a topic:
http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=5282393&arnumber=5282423&count=99&index=84&tag=1

Marcello

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 1 Mar 2010 11:56:56 -0800

On Mon, Mar 1, 2010 at 7:18 AM, Marcello Caleffi
<[email-masked]> wrote:
...
> http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=5282393&arnumber=5282423&count=99&index=84&tag=1

Interesting approach. I would be curious to know if these ideas have
been used in practice (in experimental testbeds or deployments).

Have people found issues with the traditional ETX metric estimation
and maintenance in their deployments and experiments? Those would be
the things to avoid in our recommendation on how to compute these
metrics.

- om_p

---

From: Philip Levis <[email-masked]>
Date: Sun, 14 Mar 2010 22:18:05 -0700

On Feb 28, 2010, at 2:19 AM, Marcello Caleffi wrote:

> My two cents.
> I think that ETX is a better metric than hop count (maybe every not stupid metric works better then it), however I think that sometimes we miss the point.
> The ETX estimates the expected transmission count basing on the delivery ratios. A lot of works deal with improving the use of the delivery ratios, but very few deal with improving the delivery ratio estimation, which is the real key point (as it seems to me by my simulations/experiments). So, with stupid delivery ratio estimators you need to differentiate between links with the same ETX metric (in well connected networks you have a lot of '1' links, while in high dynamic/delay tolerant networks you have a lot of 'big value' links) just because these estimators do not do their job.
> Just as example, generally people use the moving average one (counting the hello packets received and normalize to the number of hello sent), which assigns to the sequences '0000011111' and '1111100000' the same directional delivery ratio (0.5).
> However, maybe I am boring the list with uninteresting or out-of-topic considerations , so I stop here.

Marcello,

Sorry for the late reply -- I was traveling for two weeks on my honeymoon. :)

Actually, there has been a good deal of work on this topic. 

Part of the issue is distinguishing ETX the metric (trying to estimate the number of transmissions) from ETX the algorithm (as per DeCouto et al.). There are algorithms for the metric that use a different names, such as RNP, etc. The basic difference between modern approaches and the original ETX is that they use link-layer acknowledgments from the data path, and EWMA rather than a fixed window size.

Some starting points:

Kyu-Han Kim and Kang G. Shin. "On accurate measurement of link quality in multi-hop wireless mesh networks."
http://portal.acm.org/citation.cfm?id=1161095

Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis. "Four Bit Wireless Link Estimation."
http://enl.usc.edu/papers/cache/Fonseca07.pdf

Alberto Cerpa, Jennifer L. Wong, Miodrag Potkonjak, and Deborah Estrin. "Temporal properties of low power wireless links: modeling and implications on multi-hop routing."
http://portal.acm.org/citation.cfm?id=1062689.1062741

Muhammad Hamad Alizai, Olaf Landsiedel, Jó Ágila Bitsch Link, Stefan Götz, and Klaus Wehrle. "Bursty traffic over bursty links."
http://portal.acm.org/citation.cfm?id=1644038.1644046

Phil

---

From: Henning Rogge <[email-masked]>
Date: Mon, 15 Mar 2010 10:06:59 +0100

On Mon March 15 2010 06:18:05 Philip Levis wrote:
> Part of the issue is distinguishing ETX the metric (trying to estimate the
> number of transmissions) from ETX the algorithm (as per DeCouto et al.).
> There are algorithms for the metric that use a different names, such as
> RNP, etc. The basic difference between modern approaches and the original
> ETX is that they use link-layer acknowledgments from the data path,
If you can access layer 1/2 data this is a good idea. But the code will become 
OS or even hardware specific.

> and EWMA rather than a fixed window size.
EWMA is not always better than a fixed window.

> Alberto Cerpa, Jennifer L. Wong, Miodrag Potkonjak, and Deborah Estrin.
> "Temporal properties of low power wireless links: modeling and
> implications on multi-hop routing."
> Muhammad Hamad Alizai, Olaf Landsiedel, Jó Ágila Bitsch Link, Stefan Götz,
> and Klaus Wehrle. "Bursty traffic over bursty links."
Thank you for the links.

Henning Rogge

-- 
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Neuenahrer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-961,   Fax +49 228 9435 685
mailto:[email-masked] http://www.fkie.fraunhofer.de
GPG: E1C6 0914 490B 3909 D944 F80D 4487 C67C 55EC CFE0

---

From: Henning Rogge <[email-masked]>
Date: Mon, 15 Mar 2010 10:40:06 +0100

I tracked down free available alternatives to the ACM links.

> http://portal.acm.org/citation.cfm?id=1161095
http://www.eecs.umich.edu/~kyuhkim/papers/mobicom06Kim.pdf

> http://portal.acm.org/citation.cfm?id=1062689.1062741
http://lecs.cs.ucla.edu/~cerpa/papers/time-estimation-tech-report.pdf
 
> http://portal.acm.org/citation.cfm?id=1644038.1644046
http://ds.informatik.rwth-aachen.de/members/alizai/publications-
mha/pdfs/2009-11-alizai-bursty-traffic-over-bursty-links.pdf

Henning Rogge

---

From: Philip Levis <[email-masked]>
Date: Mon, 15 Mar 2010 09:18:53 -0700

> OS or even hardware specific.

Absolutely. But honestly, I'm less worried about the software engineering of network protocols than their actual efficiency. OSes can evolve to support new interfaces. 

This also gets back to my original point: separating the metric and its computation is valuable. Implementations can use this kind of information when it's available, but when it's not they can use other techniques.

> EWMA is not always better than a fixed window.

In theory, no. In practice, I think it is. By practice, I mean "on unlicensed ISM bands." 

A fixed sized window assumes that channel dynamics only occur on a time scale ~ the size of the window or longer. Clearly this isn't the case with interference. Measurements I've seen of the 2.4GHz band point to signal dynamics on the range of <500ms.

Phil

---

From: Henning Rogge <[email-masked]>
Date: Mon, 15 Mar 2010 18:14:03 +0100

Am Montag 15 März 2010 17:18:53 schrieb Philip Levis:
> > If you can access layer 1/2 data this is a good idea. But the code will
> > become OS or even hardware specific.
> 
> Absolutely. But honestly, I'm less worried about the software engineering
> of network protocols than their actual efficiency. OSes can evolve to
> support new interfaces.
We should worry about both. If we ignore the software side of the problem we 
might design stuff that does not run on most platforms. 

> This also gets back to my original point: separating the metric and its
> computation is valuable. Implementations can use this kind of information
> when it's available, but when it's not they can use other techniques.
>
We have experimented with EWMA based in the Freifunk networks (IEEE 802.11 
based meshs), and we had better experience with the fixed window than the 
EWMA. EWMA is more difficult to adapt to events that don't occur on a regular 
interval.
 
> A fixed sized window assumes that channel dynamics only occur on a time
> scale ~ the size of the window or longer. Clearly this isn't the case with
> interference. Measurements I've seen of the 2.4GHz band point to signal
> dynamics on the range of <500ms.
You don't want your LQ value change quicker than you can transport it to the 
network. That can be a desaster (depending on protocol and network topology).

Henning Rogge

---

From: "Ramrekha, Arvind" <[email-masked]>
Date: Mon, 15 Mar 2010 18:31:43 +0000

> of network protocols than their actual efficiency. OSes can evolve to
-We should worry about both. If we ignore the software side of the problem we
-might design stuff that does not run on most platforms.

I assume that by network protocol efficiency we are talking about efficient routes which are summation of values for link qualities. But what is "good quality". I understand that we want something that is better than hop count but am I wrong when I say that "link quality" or rather "route quality" is relative and depends on the traffic we use? If route quality is actually relative then implementing a fix LTX metric is not a good idea. I understand that using packet loss is an easy way to implement the LTX metric estimation but shouldn't we also look at other metrics that could be more important in cases of multimedia streaming etc?  

Arvind.

________________________________________
From: [email-masked] [[email-masked]] On Behalf Of Henning Rogge [[email-masked]]
Sent: 15 March 2010 17:14
To: [email-masked]
Cc: MANET IETF; Thomas Heide Clausen
Subject: Re: [manet] [Roll] Fwd: New Version Notification for   draft-gnawali-roll-etxof-00

Henning Rogge

This email has been scanned for all viruses by the MessageLabs Email
Security System.

This email has been scanned for all viruses by the MessageLabs Email
Security System.

---

From: Philip Levis <[email-masked]>
Date: Wed, 17 Mar 2010 09:25:25 -0700

> might design stuff that does not run on most platforms.

Very true. 

> EWMA. EWMA is more difficult to adapt to events that don't occur on a regular 

Interesting. I'd love to see what the link behavior of these networks look like. Do you have a writeup of what led you to this conclusion?

> network. That can be a desaster (depending on protocol and network topology).

Ah -- I think this is where we differ. I want the LQ value to be as accurate as possible: the perfect LQ would simply output 0 or 1 (will this packet be delivered). It's then up to the routing protocol to apply hysteresis or smoothing in order to keep the topology stable. Otherwise you've coupled the two designs.

Phil

---

From: Henning Rogge <[email-masked]>
Date: Wed, 17 Mar 2010 17:52:31 +0100

Am Mittwoch 17 März 2010 17:25:25 schrieb Philip Levis:
> > We have experimented with EWMA based in the Freifunk networks (IEEE
> > 802.11 based meshs), and we had better experience with the fixed window
> > than the EWMA. EWMA is more difficult to adapt to events that don't
> > occur on a regular interval.
> 
> Interesting. I'd love to see what the link behavior of these networks look
> like.
My experience in emulation with EWMA is that their two advantages (a single 
tuning parameter and more influence to recent data) is their disadvantage too. 
EWMA values. Because of the higher influence of recent data EWMA-based ETX 
tends to jump up/down more because of it's binary input (packet 
received/lost).

> Do you have a writeup of what led you to this conclusion?
No, sorry.
 
> >> scale ~ the size of the window or longer. Clearly this isn't the case
> >> with interference. Measurements I've seen of the 2.4GHz band point to
> >> signal dynamics on the range of <500ms.
> > 
> > You don't want your LQ value change quicker than you can transport it to
> > the network. That can be a desaster (depending on protocol and network
> > topology).
> 
> Ah -- I think this is where we differ. I want the LQ value to be as
> accurate as possible: the perfect LQ would simply output 0 or 1 (will this
> packet be delivered).
This metric would be nearly useless for multihop networks. ;)

> It's then up to the routing protocol to apply
> hysteresis or smoothing in order to keep the topology stable. Otherwise
> you've coupled the two designs.
I would think that hysteresis is part of the metric generation process. A good 
hysteresis can keep the "speed" of the metric change down to something the 
adhoc network can handle. Unless the "fast time" variations of the metric are 
higher than the hysteresis threshold.

Henning Rogge