Subject: [manet] Some comments on draft-funkfeuer-manet-olsrv2-etx-01

From: Georg Wittenburg <[email-masked]>
Date: Wed, 11 May 2011 16:10:58 +0200

Dear authors, all,

after carefully reading draft-funkfeuer-manet-olsrv2-etx-01, here are some 
comments that I would like to share with the community.

Regarding the current text:

- Naming conventions: In Sec. 4, ETX is defined as (R_etx * D_etx) where R_etx 
and D_etx are the loss rates over the link. I feel that R_etx and D_etx are 
badly labeled since these names do not adequately reflect the meaning of these 
variables. Furthermore, in the original ETX paper "A High-Throughput Path 
Metric for Multi-Hop Wireless Routing" by De Couto et al. in MobiCom '03, ETX 
is defined as (1 / (d_f * d_r)) where d_f and d_r are the forward and reverse 
delivery ratios respectively. Given the long time that this paper has been 
around, it may well make sense to stick to the established formalism and 
naming scheme.

- Size of HELLO messages: Sec. 8.1 states that HELLO messages should be 
generated as specified in draft-ietf-manet-olsrv2 which in turn refers to RFC 
6130. In the absence of other traffic, the delivery ratios of these HELLO 
messages will be the only input to the ETX metric. The problem is that packet 
delivery ratios differ depending on the size of the transmitted packet. If 
small packets are used to estimate link quality, this estimate will be flawed 
if the link is used for large packets later on, i.e, packets that make full 
use of the MTU. A workaround would be to require that if HELLO packets are to 
be used for link quality estimation then they must be padded to correspond in 
size to the average data packet, or MTU.

- Order of processing: Secs. 8.2 and 8.3 independently state that link metric 
processing is carried out *after* OLSR-related processing. In my (unrelated) 
experiments I found it beneficial to *first* update the link metrics and then 
continue with layer 3 packet processing. The rationale is simply that routing 
decisions should be based on the most up-to-date information. Hence, I suggest 
to rephrase Secs. 8.2 and 8.3 to first update the data structures related to 
link metric processing, and only afterwards hand off packets to be processed by 
OLSR. Similarly, periodic metric computation has the drawbacks of a) inducing 
delays before the updated metrics are available to other components, and b) 
the computational load of having to recalculate all links at the same time. 
Wouldn't it be beneficial to trigger per-link recomputations based on link-
related events (number of transmitted packets, sudden changes in the loss 
ratios) and merely use periodic timers as fallbacks?

Regarding possible additions:

- Convergence time: Has it been considered to add weights to the list of 
measured loss ratios in order to optimize the convergence time after major 
changes to a link?

- Useless links: Has it been considered to have an upper bound on the ETX 
value above which links are considered as being too bad to be useful?

- Modulation issues: How does this metric deal with packets that are send at 
different transmission rates using different encodings? For instance, if a link 
is measured using broadcast packets, then the metric may well be flawed for 
high-speed streams of unicast packets.

I hope these comments are helpful.

Best regards,

	Georg

-- 
Dr. Georg Wittenburg
Postdoctoral Researcher
INRIA / École Polytechnique, HIPERCOM Team
Laboratoire d'Informatique de l'École Polytechnique (LIX)
Route de Saclay, 91128 Palaiseau (CEDEX)
Phone: +33-(0)1-69334126, Fax: +33-(0)1-69334044
http://www.lix.polytechnique.fr/~wittenburg/

---

From: Henning Rogge <[email-masked]>
Date: Wed, 11 May 2011 16:55:52 +0200

> comments that I would like to share with the community.
At first, thank you for the feedback on the draft...

> - Naming conventions: In Sec. 4, ETX is defined as (R_etx * D_etx) where
> R_etx and D_etx are the loss rates over the link. I feel that R_etx and
> D_etx are badly labeled since these names do not adequately reflect the
> meaning of these variables. Furthermore, in the original ETX paper "A
> High-Throughput Path Metric for Multi-Hop Wireless Routing" by De Couto et
> al. in MobiCom '03, ETX is defined as (1 / (d_f * d_r)) where d_f and d_r
> are the forward and reverse delivery ratios respectively. Given the long
> time that this paper has been around, it may well make sense to stick to
> the established formalism and naming scheme.
I see no problem renaming both variables to stay consistent with another 
naming scheme.
 
> generated as specified in draft-ietf-manet-olsrv2 which in turn refers to
> RFC 6130. In the absence of other traffic, the delivery ratios of these
> HELLO messages will be the only input to the ETX metric.
That is not right... there will be more TC messages in the network (especially 
in larger networks) than Hellos, so they will contribute to the size of the 
packets too.

> The problem is
> that packet delivery ratios differ depending on the size of the
> transmitted packet. If small packets are used to estimate link quality,
> this estimate will be flawed if the link is used for large packets later
> on, i.e, packets that make full use of the MTU. A workaround would be to
> require that if HELLO packets are to be used for link quality estimation
> then they must be padded to correspond in size to the average data packet,
> or MTU.
The funkfeuer metric drafts suggests to use all RFC 5444 packets for link loss 
estimation, not only a certain message type. Your suggestion would make it 
necessary to pad all RFC5444 packets to the maximum MTU, which might be a 
considerable overhead.
 
> - Order of processing: Secs. 8.2 and 8.3 independently state that link
> metric processing is carried out *after* OLSR-related processing. In my
> (unrelated) experiments I found it beneficial to *first* update the link
> metrics and then continue with layer 3 packet processing. The rationale is
> simply that routing decisions should be based on the most up-to-date
> information.
Routing decissions are done for unicast traffic, which is independent from the 
OLSR/NHDP processing. Even if the metric processing is done after the packet 
processing, it could still be done before a potential dijkstra calculation, 
which would update the routing table.

> Hence, I suggest to rephrase Secs. 8.2 and 8.3 to first
> update the data structures related to link metric processing, and only
> afterwards hand off packets to be processed by OLSR.
Incoming packets don't trigger direct metric updates, so the order of both 
operations don't matter that much for the FUnkfeuer ETX metric.

> Similarly, periodic
> metric computation has the drawbacks of a) inducing delays before the
> updated metrics are available to other components, and b) the
> computational load of having to recalculate all links at the same time.
> Wouldn't it be beneficial to trigger per-link recomputations based on
> link- related events (number of transmitted packets, sudden changes in the
> loss ratios) and merely use periodic timers as fallbacks?
We use the timer approach to implement a sliding window, which always contains 
the total reception/loss for the last few seconds (ETX_MEMORY_LENGTH).
I am not sure this can be done easily without the timer approach.

> measured loss ratios in order to optimize the convergence time after major
Yes, but this metric has been mostly used in non-moving mesh networks where 
weights would only add computational overhead.

It might be a tuning parameter for moving networks, but I am not able to guess 
a good value for the weight distribution.
 
> value above which links are considered as being too bad to be useful?
We do this in the Freifunk/Funkfeuer meshs, but in NHDP/OLSRv2 this would be 
the job of the link hysteresis (which easily could be implemented based on the 
link cost value).

> - Modulation issues: How does this metric deal with packets that are send
> at different transmission rates using different encodings? For instance,
> if a link is measured using broadcast packets, then the metric may well be
> flawed for high-speed streams of unicast packets.
ETX metrics do not consider link speed, so our metric would not encode this 
difference into the link cost.

> I hope these comments are helpful.
Yes, they are. :)

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: Georg Wittenburg <[email-masked]>
Date: Fri, 13 May 2011 16:23:19 +0200

Dear Henning, all,

On Thursday 12 May 2011 08:07:31 Henning Rogge wrote:
> [...]
> That is not right... there will be more TC messages in the network
> (especially in larger networks) than Hellos, so they will contribute to
> the size of the packets too.

OK. But the point below still remains, doesn't it?

> > then they must be padded to correspond in size to the average data
> > packet, or MTU.
> 
> The funkfeuer metric drafts suggests to use all RFC 5444 packets for link
> loss estimation, not only a certain message type. Your suggestion would
> make it necessary to pad all RFC5444 packets to the maximum MTU, which
> might be a considerable overhead.

I agree. However, it still remains true that link loss estimation that relies 
excessively on small packets will lead to suboptimal results. I'm aware that 
the original ETX paper doesn't cover this, but it doesn't mean that it 
shouldn't be addressed in this draft.

How about, for example, only incrementing the respective counters for packets 
whose size is above a certain threshold, say MTU / 2 (or even MTU / 4)?

> [...]
> > measured loss ratios in order to optimize the convergence time after
> > major changes to a link?
> 
> It might be a tuning parameter for moving networks, but I am not able to
> guess a good value for the weight distribution.

Neither am I. :) In this case, I just suggest that the wording in this draft 
is chosen in such a way, that amendments regarding highly volatile or moving 
networks can be made easily later on through a second complementary draft.

> We do this in the Freifunk/Funkfeuer meshs, but in NHDP/OLSRv2 this would
> be the job of the link hysteresis (which easily could be implemented based
> on the link cost value).

But since the link cost value depends on the metric used, it would be up to 
this draft to suggest values for this, wouldn't it?

> > if a link is measured using broadcast packets, then the metric may well
> > be flawed for high-speed streams of unicast packets.
> 

Yes, link speed, just as packet size, is not covered by the original ETX 
proposal. I'm aware that properly considering link speed greatly increases the 
complexity of the problem. The best workaround that I see is to be relatively 
conservative in what is considered a useful link (see above).

Best,

	Georg

---

From: Emmanuel Baccelli <[email-masked]>
Date: Fri, 13 May 2011 17:27:47 +0200

Hi Georg,

On Fri, May 13, 2011 at 4:24 PM, Georg Wittenburg <[email-masked]
> wrote:

> shouldn't be addressed in this draft.

So far, this draft documents how the guys from the wireless community
networks (FREIFUNK, FUNKFEUER etc.) have been using ETX in OLSR in their
networks, and translating that in OLSRv2 formats.

While I agree we should let some flexibility in, and try to not preclude
things like you describe, in my opinion the first priority should be to
specify actual operational experience with OLSR and ETX.

Emmanuel

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

---

From: Teco Boot <[email-masked]>
Date: Fri, 13 May 2011 17:53:53 +0200

> whose size is above a certain threshold, say MTU / 2 (or even MTU / 4)?

How can packet sizes of lost packets be measured?

Teco

---

From: David Young <[email-masked]>
Date: Fri, 13 May 2011 11:46:30 -0500

> whose size is above a certain threshold, say MTU / 2 (or even MTU / 4)?

Suppose that there is a function that for a certain bit error rate (BER)
maps the packet size to the delivery ratio.  If we know the delivery
ratio at two or more packet sizes, it seems that we can fit a curve to
those ratios and derive the BER from the curve.  Then we can use the BER
to roughly predict the delivery ratio at each packet size.

> conservative in what is considered a useful link (see above).

You can probably derive a much better metric than ETX by tapping into
information that the rate adaptation collects.  More than one 802.11
rate adaptation in the literature has tried to optimize the so-called
goodput of a link by choosing a suitable bitrate for each packet based
on packet properties such as size.  Advantages of collecting information
from the rate adaptation are that you avoid duplicating any code or
computational effort, and you collect the information from a more
suitable (IMO) place in the network stack.  All the world's MANETs are
not built on 802.11, it is true, but the same general principles apply:
don't needlessly compute the same metric twice, and collect the link
metric at the most suitable place.

Dave

-- 
David Young             OJC Technologies
[email-masked]      Urbana, IL * (217) 344-0444 x24

---

From: Henning Rogge <[email-masked]>
Date: Sat, 14 May 2011 20:33:05 +0200

Answer to Georg Wittenburg, Teco Boot and David Young...

Am Freitag 13 Mai 2011, 16:23:19 schrieb Georg Wittenburg:
> I agree. However, it still remains true that link loss estimation that
> relies excessively on small packets will lead to suboptimal results. I'm
> aware that the original ETX paper doesn't cover this, but it doesn't mean
> that it shouldn't be addressed in this draft.
> 
> How about, for example, only incrementing the respective counters for
> packets whose size is above a certain threshold, say MTU / 2 (or even MTU
> / 4)?
What if no OLSR packets are that large ? Do we add padding to get at least one 
or multiple large packets each second ?
 
> > be the job of the link hysteresis (which easily could be implemented
> > based on the link cost value).
> 
We had some discussion about this, but it seems that most people here don't 
like to use the link metric to do the hysteresis.

In Freifunk/Funkfeuer, we ignore each link with an link quality below 0.1 in 
one direction.
 
Am Freitag 13 Mai 2011, 17:53:53 schrieb Teco Boot:
> > How about, for example, only incrementing the respective counters for
> > packets whose size is above a certain threshold, say MTU / 2 (or even
> > MTU / 4)?
> 
Maybe with a second packet sequence number that is only increased for large 
packets ?

> metric at the most suitable place.
Doing this on one operation system with different wireless cards is hard... 
doing it for multiple operation systems and different cards will get you 
insane pretty quickly...

I personally like the idea to get the rate control data of the mac80211 stack 
in linux, unfortunately that only solves the problem for a very special case, 
and only for unicast traffic.

If you rely on the rate control, you need to send unicast probing packets to 
all of your neighbors regularly if you have no traffic in this direction.

Henning Rogge

-- 
1) You can't win.
2) You can't break even.
3) You can't leave the game.
— The Laws of Thermodynamics, summarized

-- 
1) You can't win.
2) You can't break even.
3) You can't leave the game.
— The Laws of Thermodynamics, summarized

---

From: Georg Wittenburg <[email-masked]>
Date: Wed, 18 May 2011 22:16:06 +0200

Hi Henning, Teco, David, all,

On Saturday 14 May 2011 20:33:15 Henning Rogge wrote:
> > > The funkfeuer metric drafts suggests to use all RFC 5444 packets for
> > > link loss estimation, not only a certain message type. Your suggestion
> > > would make it necessary to pad all RFC5444 packets to the maximum MTU,
> > > which might be a considerable overhead.
> > 
> What if no OLSR packets are that large ? Do we add padding to get at least
> one or multiple large packets each second ?

Sounds like an acceptable trade-off. Another option would be to include data 
packets in the link loss estimation. Was there any particular reason why you 
decided against including them?

> > > We do this in the Freifunk/Funkfeuer meshs, but in NHDP/OLSRv2 this
> > > would be the job of the link hysteresis (which easily could be
> > > implemented based on the link cost value).
> > 
> > But since the link cost value depends on the metric used, it would be up
> > to this draft to suggest values for this, wouldn't it?
> 
> In Freifunk/Funkfeuer, we ignore each link with an link quality below 0.1
> in one direction.
> 

I don't see the problem here. Both sender and receiver can increment their 
respective packet counters based on the packets (above a certain size, or 
matching other conditions) which they see and ETX should just work as 
expected. Am I overlooking something?

> I personally like the idea to get the rate control data of the mac80211
> stack in linux, unfortunately that only solves the problem for a very
> special case, and only for unicast traffic.
> 
> If you rely on the rate control, you need to send unicast probing packets
> to all of your neighbors regularly if you have no traffic in this
> direction.

Best,

	Georg

---

From: David Young <[email-masked]>
Date: Wed, 18 May 2011 15:35:39 -0500

> doing it for multiple operation systems and different cards will get you 

Let us cross our fingers and hope that each OS provides a uniform API.
:-)

> all of your neighbors regularly if you have no traffic in this direction.

It seems to me, too, that that is a problem with using a rate
adaptation.  One hopes that there are probe packets or else that the
inherent background unicast traffic keeps the rate adaptation fresh.  I
think that having to induce some unicast traffic may be a reasonable
trade-off for being able to derive a link metric from the rate
adaptation.

FWIW, I have lingering doubts whether or not a link metric can be
updated or link metrics propagated nearly as quickly as the channel
makes a substantial change of state.  From N hops away, a single metric
for a link may not be nearly as useful in a routing decision as the
historical range or distribution of metrics on a link.  People have
experimented with "opportunistic" routing/forwarding, I think this is
why.

Dave

---

From: Henning Rogge <[email-masked]>
Date: Thu, 19 May 2011 08:16:03 +0200

On Wed May 18 2011 22:16:06 Georg Wittenburg wrote:
> > What if no OLSR packets are that large ? Do we add padding to get at
> > least one or multiple large packets each second ?
> 
> Sounds like an acceptable trade-off. 
We could use some kind of dummy message (maybe with TTL 0 so it will be 
automatically dropped) for the padding I think.

> Another option would be to include
> data packets in the link loss estimation. Was there any particular reason
> why you decided against including them?
Data traffic is send as unicast, so it includes retransmissions and a different 
modulation in WLAN. Its not intuitively clear how to combine this with 
broadcast measurements.
 
> > Maybe with a second packet sequence number that is only increased for
> > large packets ?
> 
The receiver on a link must estimate the number of lost packets. Our draft 
does this by looking at the packet sequence number to detect missing packets.

If you only want to count packets of a certain size this does not work.
 
Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Thu, 19 May 2011 08:17:56 +0200

> Let us cross our fingers and hope that each OS provides a uniform API.
And that all drivers use the API... ;)

> trade-off for being able to derive a link metric from the rate
It would be necessary to do so if no unicast traffic is on a link.
 
> experimented with "opportunistic" routing/forwarding, I think this is
I think this hysteresis/history of a link could be directly included into 
metric calculation of a link. The Draft is doing it in a very limited way by 
averaging over a certain period of time.

Henning Rogge

---

From: Georg Wittenburg <[email-masked]>
Date: Tue, 24 May 2011 15:37:30 +0200

Hi Henning, all,

> > I don't see the problem here. Both sender and receiver can increment
> > their respective packet counters based on the packets (above a certain
> > size, or matching other conditions) which they see and ETX should just
> > work as expected. Am I overlooking something?
> 

I see. And I agree with you that in this case you would indeed need a second 
counter just for relevant packets. Possibly another TLV, if the overhead is 
acceptable.

Best,

	Georg