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

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:

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

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.

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

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: "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.
 
Okay.

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

---

From: Teco Boot <[email-masked]>
Date: Wed, 24 Mar 2010 17:24:36 +0100

Hi Henning, (and other authors of funkfeuer-manet-olsrv2-etx-01).

Thanks for the new version.
Here some comments, also for more background on my remarks during the meeting.

1) What is ETX?
In the document, the term ETX is used for estimated number or transmissions and for loss rates. Those two are highly related, but it is not the same. Loss rate of 0.5 results in ETX of 4. Using the LQ for loss may be confusing, as it is used in NHDP for link admission.

2) Relation with NHDP LQ
The ETX draft ETX-LQ uses a different scheme than NHDP-LQ.
ETX-LQ uses only hello messages, where NHDP uses all RFC5444 packets or other information.
I understand the background, but maybe think about using the NHDP method or justify the current implemented approach? Is it suggested or permitted to use ETX-LQ for NHDP-LQ?

3) Symmetric links
The ETX metric is symmetric, where loss ratio is not. There is some justification, as an ACK mechanism may be in place, and ACK loss result in retransmits also. I don't have evidence, but as I see it, ACK loss is very low related to data packet loss (very small frames, lower data rate). I suggest to update to mechanism to support asymmetric links (which results to asymmetric paths).

4) Applicability to link layer technology with ARQ (ACK)
ETX assumes frames are retransmitted in case of loss. Not all link types work this way (e.g. Ethernet). ETX doesn't fail here, but adding a section on when retransmissions take place would make things more clear. To support other link types, ETX could be more responsiveness or NHDP-LQ should handle this.

5) Relation with ETT, RSSI, data-rate etc.
Having ETX, I am sure there will be a demand for better metrics. The question is, how to support a heterogeneous network. For this reason, I don't like the protocol aspect of the current ETX proposal. Only if both sides of the link support ETX, it will work. If one is enhanced to use something else, ETX is disabled or a negotiation is needed or some policy is used. I wouldn't go that way.
The easiest solution is to get rid of the R_etx TLV, and use the detected loss ratio for the L_in_metric. This will better support asymmetric links also.

6) Elimination of bad performing links
My experience is that the switch-over from one hop to two hops using ETX is to late. With perfect asymmetric links and no ACK loss, the switch takes place after 30% packet loss (ETX=2). Then, max_retries >= 4 is needed for SingleHopPDR above 99%. For a 100% / 50% asymmetry, max_retries needs to be >= 7. In a somewhat larger network, max_retries of 10 or higher doesn't provide PDR of 99%.
It would help to have a flexible ETX calculation algorithm for tuning to improve PDR. Then, it is important that the ETX calculation takes place on a single node, for preventing compatibility problems.

Regards, Teco

---

From: Henning Rogge <[email-masked]>
Date: Mon, 29 Mar 2010 11:25:06 +0200

On Wed March 24 2010 17:24:36 Teco Boot wrote:
> In the document, the term ETX is used for estimated number or transmissions
> and for loss rates. Those two are highly related, but it is not the same.
ETX is one way to define a loss rate. It's not the only way.

> Loss rate of 0.5 results in ETX of 4. Using the LQ for loss may be
> confusing, as it is used in NHDP for link admission.
I don't see that the draft mentions linkquality (LQ) anywhere.

> The ETX draft ETX-LQ uses a different scheme than NHDP-LQ.
What is ETX-LQ, what is NHDP-LQ ?

> ETX-LQ uses only hello messages, where NHDP uses all RFC5444 packets or
> other information. I understand the background, but maybe think about
> using the NHDP method or justify the current implemented approach? Is it
> suggested or permitted to use ETX-LQ for NHDP-LQ?
Do you mean only using HELLOs for linkcost estimation ?
 
> 3) Symmetric links
> The ETX metric is symmetric, where loss ratio is not. There is some
> justification, as an ACK mechanism may be in place, and ACK loss result in
> retransmits also. I don't have evidence, but as I see it, ACK loss is very
> low related to data packet loss (very small frames, lower data rate). I
> suggest to update to mechanism to support asymmetric links (which results
> to asymmetric paths).
The metric describes what we use in the Freifunk networks. We use a symmetric 
metric and I have no experience at this point how much better/worse an 
asymmetric metric would work.
 
> ETX assumes frames are retransmitted in case of loss. Not all link types
> work this way (e.g. Ethernet). ETX doesn't fail here, but adding a section
> on when retransmissions take place would make things more clear. To
> support other link types, ETX could be more responsiveness or NHDP-LQ
> should handle this.
I don't think the FF-ETX algorithm does make any assumptions about the link 
layer below.

> Having ETX, I am sure there will be a demand for better metrics. The
> question is, how to support a heterogeneous network.
I think supporting multiple metrics for the same path calculation is out of 
scope of this document.

> For this reason, I
> don't like the protocol aspect of the current ETX proposal. Only if both
> sides of the link support ETX, it will work. If one is enhanced to use
> something else, ETX is disabled or a negotiation is needed or some policy
> is used.
You need this "protocol" part for all symmetric metrics. It would be easy to 
generalize this "transmit your asymmetric cost to the other side without 
publishing it as a metric" TLV into the Dearlove metric draft (and into 
OLSRv2) so that it don't need to be introduced here.

> I wouldn't go that way. The easiest solution is to get rid of the
> R_etx TLV, and use the detected loss ratio for the L_in_metric. This will
> better support asymmetric links also.
But this would be a different metric. Yes, we can easily do this, but not in a 
draft/rfc describing the metric we HAVE experience with.
 
> My experience is that the switch-over from one hop to two hops using ETX is
> to late. With perfect asymmetric links and no ACK loss, the switch takes
> place after 30% packet loss (ETX=2). Then, max_retries >= 4 is needed for
> SingleHopPDR above 99%. For a 100% / 50% asymmetry, max_retries needs to
> be >= 7. In a somewhat larger network, max_retries of 10 or higher doesn't
> provide PDR of 99%. It would help to have a flexible ETX calculation
> algorithm for tuning to improve PDR. Then, it is important that the ETX
> calculation takes place on a single node, for preventing compatibility
> problems.
There is still lot's of improvement for a better ETX metric. Maybe we could 
start a second draft to use the experience described in this one to create a 
better one.

Henning Rogge

---

From: Teco Boot <[email-masked]>
Date: Mon, 29 Mar 2010 14:10:51 +0200

Hi Henning,

> ETX is one way to define a loss rate. It's not the only way.

OK, but ETX is a method but also a metric type. On latter, ETX is
the # of transmissions, not the loss ratio.

the
> I don't see that the draft mentions linkquality (LQ) anywhere.

That is the problem !!
Using something like "loss ratio" will do also.
It confuses me when ETX is used for "loss ratio" or "link quality".

> What is ETX-LQ, what is NHDP-LQ ?

NHDP-LQ: loss ratio as defined in NHDP.
ETX-LQ: loss ratio in the ETX draft.

> Do you mean only using HELLOs for linkcost estimation ?

I was wrong. The draft ETX uses all RFC5444 control packets (packet seqnum).
Is it implemented this way in FF?
For example you wrote: 
  The easiest way (not the best) to calculate ETX is to measure the amount of 
  loss in both directions of the link with probing packets (hello messages for 
  example).
(http://www.ietf.org/mail-archive/web/roll/current/msg02190.html)

The question is, is the algorithm equal to the NHDP suggested
scheme (14.4)? 
Is it acceptable to use the 14.4 first mentioned available source of 
information (link-layer)? If so, the algorithm is a more detailed
specification of what NHDP already defines.

> I don't think the FF-ETX algorithm does make any assumptions about the link 

Yes, it is. ETX assumes a retry mechanism. This is often used in wireless media,
but not all. For wired media, it isn't used these days anymore.
No problem with it, but why not mention the assumption?

> I think supporting multiple metrics for the same path calculation is out of 

But the proposal introduces the problem! That is why I suggest removal of
the limitation. It is not needed.
Use ETX for calculating the L_in_metric, using whatever algorithm. The
algorithm may use other info also.

> start a second draft to use the experience described in this one to create a 

OK.
Is this ETX implementation implemented in current FF? Or is it a translation 
for OLSRv1-ETX to a proposal for OLSRv2?

Regards, Teco

---

From: Henning Rogge <[email-masked]>
Date: Mon, 29 Mar 2010 14:23:26 +0200

On Mon March 29 2010 14:10:51 Teco Boot wrote:
> >> In the document, the term ETX is used for estimated number or
> >> transmissions and for loss rates. Those two are highly related, but it
> >> is not the same.
> > 
the RFC use ETX as a measurement of "cost" with a range of 1 to infinity. So 
it's not directly loss rate (which has a maximum of 100%) but the reciprocal 
value of the "successful transmission probability".
 
> It confuses me when ETX is used for "loss ratio" or "link quality".
ETX (expected transmission count) is used for "link COST", not quality in the 
draft.
 
> ETX-LQ: loss ratio in the ETX draft.
The draft is only about linkcost for path calculation in the coming OLSRv2 
RFC, not the hysteresis LQ of NHDP.

> I was wrong. The draft ETX uses all RFC5444 control packets (packet
> seqnum). Is it implemented this way in FF?
Yes. We use each incoming OLSR package to support our link cost calculation.

> For example you wrote:
>   The easiest way (not the best) to calculate ETX is to measure the amount
> of loss in both directions of the link with probing packets (hello
> messages for example).
No. The NHDP mechanism only use incoming Hellos for calculating the quality 
value.

> specification of what NHDP already defines.
NHDP is about hysteresis of the link state, the funkfeuer draft is about 
calculating the link cost for dijkstra.
 
> >> justification, as an ACK mechanism may be in place, and ACK loss result
> >> in retransmits also. I don't have evidence, but as I see it, ACK loss
> >> is very low related to data packet loss (very small frames, lower data
> >> rate). I suggest to update to mechanism to support asymmetric links
> >> (which results to asymmetric paths).
> > 
> > The metric describes what we use in the Freifunk networks. We use a
> > symmetric metric and I have no experience at this point how much
> > better/worse an asymmetric metric would work.
> > 
> >> work this way (e.g. Ethernet). ETX doesn't fail here, but adding a
> >> section on when retransmissions take place would make things more
> >> clear. To support other link types, ETX could be more responsiveness or
> >> NHDP-LQ should handle this.
> > 
> > I don't think the FF-ETX algorithm does make any assumptions about the
> > link layer below.
> 
> Yes, it is. ETX assumes a retry mechanism. This is often used in wireless
> media, but not all. For wired media, it isn't used these days anymore.
I think it should be in the original ETX paper we have as a reference. But we 
could include this in the summary.

> > I think supporting multiple metrics for the same path calculation is out
> > of scope of this document.
> 
Sorry, you misunderstand the draft.

The draft is a proposal how to calculate L_in_metric.
 
> >> something else, ETX is disabled or a negotiation is needed or some
> >> policy is used.
> > 
> > You need this "protocol" part for all symmetric metrics. It would be easy
> > to generalize this "transmit your asymmetric cost to the other side
> > without publishing it as a metric" TLV into the Dearlove metric draft
> > (and into OLSRv2) so that it don't need to be introduced here.
> > 
> >> R_etx TLV, and use the detected loss ratio for the L_in_metric. This
> >> will better support asymmetric links also.
> > 
> > But this would be a different metric. Yes, we can easily do this, but not
> > in a draft/rfc describing the metric we HAVE experience with.
> > 
> >> My experience is that the switch-over from one hop to two hops using ETX
> >> is to late. With perfect asymmetric links and no ACK loss, the switch
> >> takes place after 30% packet loss (ETX=2). Then, max_retries >= 4 is
> >> needed for SingleHopPDR above 99%. For a 100% / 50% asymmetry,
> >> max_retries needs to be >= 7. In a somewhat larger network, max_retries
> >> of 10 or higher doesn't provide PDR of 99%. It would help to have a
> >> flexible ETX calculation algorithm for tuning to improve PDR. Then, it
> >> is important that the ETX calculation takes place on a single node, for
> >> preventing compatibility problems.
> > 
> > There is still lot's of improvement for a better ETX metric. Maybe we
> > could start a second draft to use the experience described in this one
> > to create a better one.
> 
> OK.
> Is this ETX implementation implemented in current FF? Or is it a
> translation for OLSRv1-ETX to a proposal for OLSRv2?
We don't have running OLSRv2 code, it's a translation of what we do with out 
OLSRv1 code.

Henning Rogge

---

From: Teco Boot <[email-masked]>
Date: Mon, 29 Mar 2010 15:44:34 +0200

> value of the "successful transmission probability".

Text on ETX in the draft: 
"Router A computes R_etx as the measured proportion of [RFC5444] packets
 successfully arriving from B" (section 4)
"linkcost" (R_etx, 8.1)
"Loss rate of incoming [RFC5444] packets." (R_etx, 13.2).
Maybe confusion is because you (and me..) are half way a transition from
LQ / NLQ to ETX encoding of LQ. 

(skipped)

> No. The NHDP mechanism only use incoming Hellos for calculating the quality 

No, NHDP uses all control packets.

> calculating the link cost for dijkstra.

Yes, but the algorithm would be the same.

> could include this in the summary.

Yes, it is in the paper:
  ETX makes at least two assumptions about the link layer. First, ETX only 
  makes sense for networks with link-layer retransmission, such as 802.11b.

> The draft is a proposal how to calculate L_in_metric.

When ETX is used for L_in_metric, why using a transfer of the ETX? This would 
incorporate lost ACKs, which is unimportant or even harmful.

And on the transfer of information, analyse link cost calculation from
router A to router B. A measures loss ratio, sends this to B with R_etx. On B,
this info is stored as D_etx, and used for calculating L_in_metric. Then, this
is send back to A again, where it *could be* send to other nodes with TC messages. 
B is one of the TC receivers also. 
Doesn't seem straightforward to me.

> We don't have running OLSRv2 code, it's a translation of what we do with out 

Great. Now we can discuss any improvement, to get it right this time.

Regards, Teco

---

From: Ulrich Herberg <[email-masked]>
Date: Mon, 29 Mar 2010 15:55:03 +0200

Teco, Henning,

On Mon, Mar 29, 2010 at 3:44 PM, Teco Boot <[email-masked]> wrote:
> [...]

Neither is true. The link quality mechanism allows to "take
considerations other than message exchange into account for
determining when a link is and is not a candidate for being considered
as HEARD or SYMMETRIC.".

The ID then mentions different sample possibilities:
   -- Receipt or loss of control packets.
   -- Receipt or loss of HELLO messages.

Any other means can be used as well (e.g. L2 information)

Ulrich

---

From: Henning Rogge <[email-masked]>
Date: Mon, 29 Mar 2010 15:57:48 +0200

On Mon March 29 2010 15:44:34 Teco Boot wrote:
> > the RFC use ETX as a measurement of "cost" with a range of 1 to infinity.
> > So it's not directly loss rate (which has a maximum of 100%) but the
> > reciprocal value of the "successful transmission probability".
> 
Okay, this one should be changed.

> "linkcost" (R_etx, 8.1)
Thats okay.

> "Loss rate of incoming [RFC5444] packets." (R_etx, 13.2).
The algorithm use a reciprocal value of the loss rate to calculate the 
linkcost.

> LQ / NLQ to ETX encoding of LQ.
Maybe.
 
> > No. The NHDP mechanism only use incoming Hellos for calculating the
> > quality value.
> 
Okay, I have just reread the NHDP draft and it says the packet sequence number 
could be used for "link quality" estimation, but not how. The funkfeuer draft 
does describe this.

> Yes, but the algorithm would be the same.
Yes, I know. Should not be that difficult to use a generic linkcost for 
hysteresis in NHDP.

> >>>> ETX assumes frames are retransmitted in case of loss. Not all link
> >>>> types work this way (e.g. Ethernet). ETX doesn't fail here, but
> >>>> adding a section on when retransmissions take place would make things
> >>>> more clear. To support other link types, ETX could be more
> >>>> responsiveness or NHDP-LQ should handle this.
> >>> 
> >> Yes, it is. ETX assumes a retry mechanism. This is often used in
> >> wireless media, but not all. For wired media, it isn't used these days
> >> anymore. No problem with it, but why not mention the assumption?
> > 
> > I think it should be in the original ETX paper we have as a reference.
> > But we could include this in the summary.
> 
> Yes, it is in the paper:
> >>> I think supporting multiple metrics for the same path calculation is
> >>> out of scope of this document.
> >> 
> >> But the proposal introduces the problem! That is why I suggest removal
> >> of the limitation. It is not needed.
> When ETX is used for L_in_metric, why using a transfer of the ETX? This
> would incorporate lost ACKs, which is unimportant or even harmful.
Because that's the way the algorithm we described works. And that's what we 
have tested for years.

> router A to router B. A measures loss ratio, sends this to B with R_etx. On
> B, this info is stored as D_etx, and used for calculating L_in_metric.
> Then, this is send back to A again, where it *could be* send to other
> nodes with TC messages. B is one of the TC receivers also.
If you want to use a symmetric metric you need, it. If not, you don't.
Can we please stop discussing about his point, unless you plan to ban 
symmetric metrics for OLSRv2.
 
> > We don't have running OLSRv2 code, it's a translation of what we do with
> > out OLSRv1 code.
> 
Unfortunately we don't even know if it gets worse or better with the change. 
That's why this 'improved' metric should be another draft I think.

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 29 Mar 2010 15:02:34 +0100

>> No. The NHDP mechanism only use incoming Hellos for calculating the
quality 

> No, NHDP uses all control packets.

Actually, NHDP doesn't specify. OLSR (v1) which used the same link
quality concept had two such mechanisms, one which considered HELLO
messages and one which considered packets. These were an alternative
to direct setting of link quality, e.g. using SNR. Note that neither
HELLOs nor packets handle the main reason for link quality in 802.11
networks (not the only case of course) which is the "grey zone"
problem (between broadcast and unicast packets). Only SNR or something
like it will handle that.

NHDP is less prescriptive. Yes, it notes the HELLO and packet
mechanisms,
but it doesn't mandate any particular use thereof, and in particular
doesn't mandate the leaky integetor used in OLSRv1, while of course
still permitting it, and mentioning it as an option. (As I recall it
also mentions n out of m as an option.)

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 29 Mar 2010 15:10:34 +0100

> symmetric metrics for OLSRv2.

I need to catch up on what's in the ETX draft. but there are two points
the ETX metric needs to take account of in order to be compatible with
OLSRv2:

- OLSRv2 will use an inherently asymmetric metric, because that needs
  no extra signalling. Of course a symmetric metric can be an asymmetric
  metric, it's the same each way, and we allow more efficient signalling
  in this case. But this, as previously noted, makes ETX a protocol, not
  simply a metric, as it has to signal information in order to establish
  a symmetric value.

- OLSRv2 requires that a link has a metric almost immediately. You may
not
  have finished information exchange for ETX at that point. If you
haven't
  you'll need a "holding" value - the obvious candidte is the maximum
  possible metric. (This is an argument in favour of making the default
  value - note that this is the default signalled value, having no more
  significance than "if no metric TLV, use this value" - the maximum,
  which is not the current proposal, but that's the most flexible part
of
  the proposal.)

Both of these have been said before, but need to be taken on board
(maybe
they wholly or partly have been) before the subject is closed.

---

From: Henning Rogge <[email-masked]>
Date: Tue, 30 Mar 2010 07:54:48 +0200

>   simply a metric, as it has to signal information in order to establish
So do we want to provide the necessary framework for symmetric metrics 
directly in the OLSRv2 RFC ? It might be a good idea to add a TLV for this 
when the metric draft is included into OLSRv2 so that all symmetric metrics 
use the same "transport asymmetric linkcost" TLV to calculate the final 
symmetric value.

Otherwise each symmetric metric will have to get a TLV for this for 
themselves.

The third option would be to say that OLSRv2 does not support symmetric 
metrics.

I would favor option 1 or two.

> they wholly or partly have been) before the subject is closed.
You can adapt the packet-sequence number based ETX to one that will give you a 
metric value as soon as you received the first packet from a neighbor.

You just need a "brake" to prevent the ETX jumping to 1.0 after the first 
package (for example just assume you got a few 'lost' packages when receiving 
a new neighbor).

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 30 Mar 2010 09:37:33 +0100

> directly in the OLSRv2 RFC ?

There already is a framework to transmit a metric as having the same
value
in each direction (whether that be symmetric or a coincidence) without
repeating the value. That I think is sufficient.

> package (for example just assume you got a few 'lost' packages when
receiving 

Does the ETX draft say this? (Still my apologies for not having
read it to this level of detail.)

---

From: Henning Rogge <[email-masked]>
Date: Tue, 30 Mar 2010 10:45:25 +0200

On Tue March 30 2010 10:37:33 Dearlove, Christopher (UK) wrote:
> value in each direction (whether that be symmetric or a coincidence) without
I don't talk about communicating the symmetric value to all other nodes in 
Hello/TCs. Many symmetric metrics are just made from to parts measured on both 
sides of the link. To calculate the metric value that will be transmitted in 
the Hello/TC-messages, both sides of the link most exchange the intermediate 
result to the other side.

> > You can adapt the packet-sequence number based ETX to one that will
> > give you a metric value as soon as you received the first packet from a
> > neighbor. You just need a "brake" to prevent the ETX jumping to 1.0 after
> > the package (for example just assume you got a few 'lost' packages when
> > receiving a new neighbor).
> 
No, not in the current revision.

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 30 Mar 2010 09:51:24 +0100

> result to the other side.

Avoiding that additional protocol exchange is something we do not
want to do in the base OLSRv2 draft. Any message exchange will be
specific to a particular metric, and that's exactly what we want
to avoid. If a separate draft tries something and it doesn't get
it right, or general enough, that's not a problem (especially if
the separate draft is Experimental). But embedding that in the
main draft would be a bad idea, even apart from the additional
delays.

If a separate draft is adding a TLV for data exchange, I would
however suggest that thought is given to other metrics, and how
defining a TLV reserves a block of values with different type
extensions (in a similar way - though there is a subtlety over
blocks of 4 - that a metric type does)