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

From: Thomas Heide Clausen <[email-masked]>
Date: Tue, 23 Feb 2010 08:07:36 +0100

Just a FYI: in the [manet] WG, an ETx metrics specification was  
published recently, based on the exhaustive operational experiences  
from the FunkFeuer network:

	http://tools.ietf.org/html/draft-funkfeuer-manet-olsrv2-etx

I understand that the above I-D is being revised and an update is  
expected shortly.

I thought that it might be useful to cross-post this information -- it  
would seem that there's both similarity and complementarity here.

(and, for some reason, the only URL for draft-gnawali-roll-etxof that  
I could make work is this: https://datatracker.ietf.org/doc/draft-gnawali-roll-etxof/ 
  )

Sincerely,

Thomas

On Feb 23, 2010, at 06:03 AM, Omprakash Gnawali wrote:

> ---------- Forwarded message ----------
> From: IETF I-D Submission Tool <[email-masked]>
> Date: Mon, Feb 22, 2010 at 8:56 PM
> Subject: New Version Notification for draft-gnawali-roll-etxof-00
> To: [email-masked]
> Cc: [email-masked]
>
>
>
> A new version of I-D, draft-gnawali-roll-etxof-00.txt has been
> successfuly submitted by Omprakash Gnawali and posted to the IETF
> repository.
>
> Filename:        draft-gnawali-roll-etxof
> Revision:        00
> Title:           The ETX Objective Function for RPL
> Creation_date:   2010-02-22
> WG ID:           Independent Submission
> Number_of_pages: 7
>
> Abstract:
> The ETX metric of a wireless link is the expected number of
> transmissions required to successfully transmit and acknowledge a
> packet on the link.  The Routing Protocol for Low Power and Lossy
> Networks (RPL) allows the use of objective functions to construct
> routes that optimize or constrain a routing metric on the paths.
> This specification describes ETXOF, an objective function that
> minimizes ETX.  The RPL path computation using ETXOF results in
> minimum-ETX paths from the nodes to the DAG roots, i.e., paths that
> minimize the number of packet transmissions for packet delivery from
> nodes in the network to the DAG root.
>
>
>
> The IETF Secretariat.
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: "L. Aaron Kaplan" <[email-masked]>
Date: Fri, 26 Feb 2010 18:47:29 +0100

On Feb 26, 2010, at 6:16 PM, Omprakash Gnawali wrote:

> We can definitely learn from the experience at Funkfeuer.

We will document it in a draft :)

> Specifically, regarding ETX, it was interesting that there was a need
> to represent better than ETX=1 links. However, I wonder if it is
> better to use different metrics to differentiate these links rather
> than overloading the meaning of ETX. It is always good to get insights
> from practice on these issues...

I agree... however , we have an operational issue here... the network is quite
distributed and community owned (so we can not reach every node with a central 
root account). Therefore updating is a pain in the neck. 
Every update step has to be somewhat compatible.

Well.. already discussed with Emmanuel, Thomas and Henning that we will document the successes and learned lessons of Funkfeuer.

:)

Best regards,
L. Aaron Kaplan
(funkfeuer.at)

---

From: Omprakash Gnawali <[email-masked]>
Date: Fri, 26 Feb 2010 09:16:17 -0800

- om_p

On 2/22/10, Thomas Heide Clausen <[email-masked]> wrote:
> I could make work is this:
> https://datatracker.ietf.org/doc/draft-gnawali-roll-etxof/
>   )
>
> Sincerely,
>
> Thomas
>
>

---

From: Marcello Caleffi <[email-masked]>
Date: Sun, 28 Feb 2010 11:19:50 +0100

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.

Best,
Marcello

Il giorno 26/feb/2010, alle ore 18.16, Omprakash Gnawali ha scritto:

> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet

---

From: Henning Rogge <[email-masked]>
Date: Sun, 28 Feb 2010 11:41:10 +0100

Am Sonntag 28 Februar 2010 11:19:50 schrieb Marcello Caleffi:
> 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).
We did some experiments at Freifunk/Funkfeuer with an ETX metric based on 
exponential aging to favor the recent data input, but discovered it dit not 
work well so we got back to a flat average of a certain time interval. This 
works well for our fixed networks, but could be better for mobile ones.

It would be an interesting experiment to do the averaging with a slight bias 
towards the new values, but this could have a negative side effect too. If you 
have an fluctuating link you get more fluctiation in the ETX result if you 
favor a small part of your input data.

A better approach might be to calculate the standard deviation of the data 
points and use this as a penalty for the total link cost to favor stable links 
over unstable one. Without more statistics it's difficult too say that a 
"0000011111" event is better than the "1111100000" event. Both could just be 
the result of an instable and fluctuating link.

Henning Rogge

---

From: Marcello Caleffi <[email-masked]>
Date: Sun, 28 Feb 2010 11:54:06 +0100

Dear Henning,
the exponential moving average is another common estimator for delivey ratios. And I'm not surprised to read that it performed worse in a fixed network (in absence of congestion, I suppose). The main issue with the exponential aging is that the forgetting weight is fixed and it has to be set by the user, i.e. is not adaptive. The same thing happens for a biased estimator, until the estimator is not adaptive.
You right saying that without more statistics is hard to establish (from a statistically point of view) which is better among "0000011111" and "1111100000", however there are adaptive estimators (not too complex in terms of memory or computational cycles) which can exploits the correlation among trials. If my whole contact history is composed by 'ones', and I started to receives '0's, is hard to think that nothing happened.
Maybe we could make some experiments in your network. However, the important thing for me is to discuss about it.
Talking about how to use the delivery ratios (i.e. how to compute and standardize the ETX metric) before to correctly (from an operational, a statistical and a standardization point of view) compute the delivery ratios is questionable in my mind.

Best,
Marcello

---

From: Henning Rogge <[email-masked]>
Date: Sun, 28 Feb 2010 12:12:49 +0100

Am Sonntag 28 Februar 2010 11:54:06 schrieb Marcello Caleffi:
> Dear Henning,
> the exponential moving average is another common estimator for delivey
> ratios. And I'm not surprised to read that it performed worse in a fixed
> network (in absence of congestion, I suppose). The main issue with the
> exponential aging is that the forgetting weight is fixed and it has to be
> set by the user, i.e. is not adaptive. The same thing happens for a biased
> estimator, until the estimator is not adaptive.
Yes, there is no easy way to fix a metric for all cases.

> You right saying that
> without more statistics is hard to establish (from a statistically point
> of view) which is better among "0000011111" and "1111100000", however
> there are adaptive estimators (not too complex in terms of memory or
> computational cycles) which can exploits the correlation among trials. If
> my whole contact history is composed by 'ones', and I started to receives
> '0's, is hard to think that nothing happened.
Or maybe a bird just got into your transmission path. Better wait a few 
moments before changing the metric output of the algorithm to see if it was 
just a glitch.

> Maybe we could make some experiments in your network.
That would be a little bit difficult because Freifunk/Funkfeuer networks are 
distributed over cities and used by their owners to get internet access. But 
we have a limited test setup in Vienna that use a second IP range and port to 
run two OLSR instances on the same hardware.

> However, the important thing for me is to discuss about it.
One thing we were talking about in Funkfeuer was something we call "metric 
postprocessing". If we have a metric implementation that outputs a 
dimensionless metric value, we could add another layer of algorithms to use 
statistics to stabilize and enhance the raw metric output, independant to the 
metric itself.

> Talking about how to use the delivery ratios (i.e. how
> to compute and standardize the ETX metric) before to correctly (from an
> operational, a statistical and a standardization point of view) compute
> the delivery ratios is questionable in my mind.
The draft I have sent to the MANET working group is a description of the 
metric we have been using in the Freifunk/Funkfeuer networks for years. So we 
can say "yes, this does work" and "it works thousands times better than 
hopcount". It's not meant as the "final and best approach to ETX", but it is a 
working algorithm to compute a metric with few resources (most of our hardware 
are embedded routers with 200-300 MHz CPUs and 16 MB ram). It's better to have 
a draft like this than to public a routing protocol without any documented 
alternative to hopcount (which does not work) which happened for OLSRv1. Even 
today I hear people on conferences talking about "OLSR does not work, see our 
little trick works better" and using hopcount. Why do they use hopcount ? 
Because the RFC says so.

Henning Rogge

---

From: Marcello Caleffi <[email-masked]>
Date: Sun, 28 Feb 2010 12:33:49 +0100

> moments before changing the metric output of the algorithm to see if it was 

This is true :).

> run two OLSR instances on the same hardware.

Maybe we can discuss it in private.

> statistics to stabilize and enhance the raw metric output, independant to the 

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.

> little trick works better" and using hopcount. Why do they use hopcount ? 

It was not my intention to discuss against your draft. Until we move towards realistic hypothesis, I am in.
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 <---> 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.

By the way, thank you for your contribute.
Marcello

---

From: Henning Rogge <[email-masked]>
Date: Sun, 28 Feb 2010 21:58:27 +0100

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.
 
> 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