Subject: [manet] Comment on draft-dearlove-olsrv2-metrics-02

From: Henning Rogge <[email-masked]>
Date: Tue, 29 Jul 2008 08:06:30 +0200

Hello everyone,

I have read the draft on routing metric handling in OLSRv2 and think that the 
integration of routing metrics should be a really important part of the NHDP 
and OLSRv2 protocol.

I'm working with the German Freifunk community on improving their 
multiplatform OLSRv1 routing daemon (see www.olsr.org) and hopcount based 
routing has never been able to create a stable MANET based on IEEE 802.11 
network links. Only the implementation of a proprietary protocol extension to 
transmit an ETX based routing metric seems to allow larger networks (our 
largest OLSR nets have 700+ routers) to provide stable network access.

I am sceptic about the idea to reduce the transmitted TC-set to a 'routing MPR 
set', because this reduce the amount of redundancy in the topology set and 
might create unstable routes on larger networks, but this have to be tested 
on a real MANET. If the reduced routing set creates stable routes, it would 
be a great way to reduce the necessary airtime of OLSRv2.

Henning Rogge

*************************************************
Diplom-Informatiker Henning Rogge
Forschungsgesellschaft für
Angewandte Naturwissenschaften e. V. (FGAN) 
Neuenahrer Str. 20, 53343 Wachtberg, Germany
Tel.: 0049 (0)228 9435-961
Fax: 0049 (0)228 9435-685
E-Mail: [email-masked]
Web: www.fgan.de
************************************************
Sitz der Gesellschaft: Bonn
Registergericht: Amtsgericht Bonn VR 2530
Vorstand: Dr. rer. nat. Ralf Dornhaus (Vors.), Prof. Dr. Joachim Ender 
(Stellv.)
_______________________________________________
manet mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/manet

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 30 Jul 2008 11:59:17 +0200

Dear Henning,

That's a great idea. Surely Freifunk experience in metric handling will 
provide a central help to this initiative. ETX is using link quality via 
hello loss rate? I would like to experiment it on OLSRv2. Do you have 
more details about it?

Thanks and best regards,
Philippe

---

From: Philip Levis <[email-masked]>
Date: Wed, 30 Jul 2008 13:09:37 +0100

On Jul 30, 2008, at 10:59 AM, Philippe Jacquet wrote:

> Dear Henning,
>
> That's a great idea. Surely Freifunk experience in metric handling  
> will provide a central help to this initiative. ETX is using link  
> quality via hello loss rate? I would like to experiment it on  
> OLSRv2. Do you have more details about it?

Can you be more precise by what you mean by ETX? I don't mean to be  
dense, but the acronym tends to be used in two ways. The first use is  
a metric -- Estimated Transmissions -- which can be computed in a  
bunch of ways. The second use is a particular algorithm developed at  
MIT for computing this value.

The ETX algorithm computes the ETX metric by measuring a sliding  
window of beacons. Note that his is insufficient for 802.11b due to  
variable bitrates, so you need to either run ETX on each bitrate  
independently or just run it at one of them and then use a dynamic  
bitrate selection algorithm.

There are several other algorithms for computing the ETX metic. These  
days, consensus seems to be that directly using data traffic is  
greatly superior to beacons. You use beacons for discovery and rough  
estimates, but use whether you receive L2 acks to directly measure the  
estimated transmissions. One major problem with beacons is bursty  
links will perform terribly: while the PRR might be 80% (ETX = 1.25),  
this can be because there are 2-second periods of 0% PRR, leading to  
huge numbers of retransmissions. Most wireless networks tend to be  
bursty.

If you're interested in this, I can send you some sample source code  
and some references.

Phil

---

From: Henning Rogge <[email-masked]>
Date: Wed, 30 Jul 2008 14:38:36 +0200

> bitrate selection algorithm.
Okay, I will try to be more precise...

The ETX algorithm of MIT propose that if you have a signal with a constant 
period you can calculate the lossrate by looking at the number of signals you 
receive in a certain timewindow.
We used this idea by applying it on the Hello packages of OlsrV1.

Algorithm described on the webpage (v 0.4.10)
---------------------------------------------
(see http://www.olsr.org/docs/README-Link-Quality.html )

Each olsr node has a (roughly) fixed Hello rate, so the idea behind the old 
olsrd-ETX algorithm was to use a binary array filled with 1 everytimes it 
receives a Hello and a 0 if a hello is lost (detected by a timeout).
The number of 1's compared to the length of the array is a measurement for the 
Link quality, the reciprocal value of this is an approximation of the ETX 
(expected transmissions).
The algorithm was tweaked a lot between 0.4.8 and 0.5.5 and got some 
strange "bugfixes" and "workarounds", so we decided to write a new/clean 
implementation.

Default "Linkcost" algorithm for 0.5.6_rc
-----------------------------------------
(we don't call it ETX anymore because we can implement metrics in a plugin 
now)

The new implementation stores a variable LQ (between 0 and 1) for each link. 
The idea is that the LQ value is the average of the pasts 0/1 results of 
Hellos.
Instead of using an array we use an exponential moving average.

    LQ(t+1) = alpha * LQ(t) + (1-alpha * new_value)

new_value is 1 if a hello is received and 0 if a hello is lost. This 
way "recent" hellos should have a greater impact on the LQ value than hellos 
a long time ago.

> estimated transmissions.
At the moment Olsrd is a pure layer3 programm, so we have no access to L2 
acks.

> One major problem with beacons is bursty  
Yes, that's a problem. There is still lots of work to be done.

> If you're interested in this, I can send you some sample source code
I would like to see your sample code.

Henning Rogge

Diplom Informatiker Henning Rogge

---

From: Philip Levis <[email-masked]>
Date: Wed, 30 Jul 2008 13:52:38 +0100

> We used this idea by applying it on the Hello packages of OlsrV1.

Note that the MIT algorithm is based on a fixed, sliding window. In  
contrast, your algorithm below uses EWMA. There's some evidence the  
EWMA is superior (it's more adaptive), but I've found that it's very  
hard to tune in practice. Highly adaptive EWMA settings can cause  
tremendous churn in the network. The fixed window approach seems to be  
more stable.

> Algorithm described on the webpage (v 0.4.10)

Doesn't L2 tell you if the packet was acked? This doesn't violate  
layers, any more than TCP telling you a connection closed does. The  
trick of course is wireless link layers that don't have ACKs. But most  
standardized ones do.

> I would like to see your sample code.

Note that this is in a C dialect. The basic thing to know is that the  
system is entirely event-driven, so no function blocks. Instead, you  
have callbacks. This source file is for a link estimator that uses a  
hybrid of beacons and layer 2 acks. Beacons provide rough estimates  
and data packets refine the estimates. It also has the issue of  
maintaining a fixed-size neighbor table, so there are some functions  
for pinning entries, etc:

http://tinyos.cvs.sourceforge.net/tinyos/tinyos-2.x/tos/lib/net/4bitle/LinkEstimatorP.nc?revision=1.8&view=markup

This paper describes how it works:

http://sing.stanford.edu/pubs/hotnets07-4b.pdf

Phil

---

From: Henning Rogge <[email-masked]>
Date: Wed, 30 Jul 2008 15:12:29 +0200

> tremendous churn in the network. The fixed window approach seems to be
That would fit with out experimental results. We are moving away from EWMA at 
the moment because we had problems to tune the algorithm in real networks (it 
was working well in simulation).

> trick of course is wireless link layers that don't have ACKs. But most
Olsrd does not handle the normal traffic, it just sets kernel routes. Because 
of this the only traffic Olsrd sends is broadcast (for olsr protocol 
messages).

Henning

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 30 Jul 2008 15:28:29 +0200

One possibility to cope with variable bit rate is to give an estimated 
bit time transmission which is equal to ETX divided by bitrate. If bit 
rate varies with retry number one may have a formula of the kind

1/br_1+p/br_2+p^2/br_3+...+p^km/br_km
where p is the hello loss rate and br_k is the bitrate at the k-th 
retransmission and km the maximum retransmission number the interface 
allows.

It also would ease the comparison between interfaces with different 
bitrates, in multiple interface situation.

Philippe

Philip Levis a écrit :
>> quality via hello loss rate? I would like to experiment it on OLSRv2. 
>> Do you have more details about it?
> 
> dense, but the acronym tends to be used in two ways. The first use is a 
> metric -- Estimated Transmissions -- which can be computed in a bunch of 
> ways. The second use is a particular algorithm developed at MIT for 
> computing this value.
> 
> The ETX algorithm computes the ETX metric by measuring a sliding window 
> of beacons. Note that his is insufficient for 802.11b due to variable 
> bitrates, so you need to either run ETX on each bitrate independently or 
> just run it at one of them and then use a dynamic bitrate selection 
> algorithm.
> 
> days, consensus seems to be that directly using data traffic is greatly 
> superior to beacons. You use beacons for discovery and rough estimates, 
> but use whether you receive L2 acks to directly measure the estimated 
> transmissions. One major problem with beacons is bursty links will 
> perform terribly: while the PRR might be 80% (ETX = 1.25), this can be 
> because there are 2-second periods of 0% PRR, leading to huge numbers of 
> retransmissions. Most wireless networks tend to be bursty.
> 
> If you're interested in this, I can send you some sample source code and 
> some references.
> 
> Phil
> 
>

---

From: Philip Levis <[email-masked]>
Date: Wed, 30 Jul 2008 14:34:16 +0100

On Jul 30, 2008, at 2:28 PM, Philippe Jacquet wrote:

> One possibility to cope with variable bit rate is to give an  
> estimated bit time transmission which is equal to ETX divided by  
> bitrate. If bit rate varies with retry number one may have a formula  
> of the kind
>
> retransmission and km the maximum retransmission number the  
> interface allows.
>

Absolutely. One of the first extensions to ETX, called ETT (Estimated  
Time of Transmission), incorporated what bitrate would be used. E.g.,  
a PRR of 50% at 11Mbps is faster than a PRR of 95% at 1Mbps. It turns  
out that there can be weird inconsistencies in the PRR vs. bitrate  
curve, due to things like inter-symbol interference and selective  
fading. As far as I know, though, ETT is measured using a single bit  
rate -- the one expected to be used -- rather than a composite, however.

Phil

---

From: Hongwei Zhang <[email-masked]>
Date: Thu, 31 Jul 2008 14:19:45 -0400

A follow up on Phil's comment on the drawbacks of beacon-based link 
estimation:

we have done some detailed study on the error of beacon-based link 
estimation in both mote networks and 802.11b networks. Please find below 
two articles on these studies:

    http://www.cs.wayne.edu/~hzhang/group/TR/DNC-TR-08-02.pdf  
    http://www.cs.wayne.edu/~hzhang/group/publications/LOF-journal.pdf  

As far as the Internet Draft is concerned, perhaps it does not have to 
specify the specific method of estimating certain metrics, instead it 
only needs to provide the right interface for incorporating different 
estimation methods. IMHO, how to share/diffuse control information (as 
was the original focus of the MANET focus?) may well be an orthogonal 
issue w.r.t. what control information/metric to use in routing and how 
to get that information.

Hongwei
---
http://www.cs.wayne.edu/~hzhang/

Philip Levis wrote:

> estimates, but use whether you receive L2 acks to directly measure 
> the  estimated transmissions. One major problem with beacons is 
> bursty  links will perform terribly: while the PRR might be 80% (ETX = 
> 1.25),  this can be because there are 2-second periods of 0% PRR, 
> leading to  huge numbers of retransmissions. Most wireless networks 
> tend to be  bursty.
>

---

From: "Mullen, John" <[email-masked]>
Date: Thu, 31 Jul 2008 15:37:20 -0600

Hi,

I agree that a better approach would be to provide a framework for link quality estimation for several reasons, but I think two are especially important.

I feel a MANET protocol should not be implementation-specific. For one, as in the case of Internet protocols, the underlying technology may be of very different sorts, even in the same network.  Moreover, technology is evolving very quickly. While issues that make link quality estimation difficult, such as shadowing, multipath fading, and terrain effects, will continue to exist, the suite of technological solutions will grow. Specifying a particular method might make the protocol less generally useful and prone to early obsolesce.

Another issue is the nature of the application. For example, in a military application, there would be the competing issues of rapid communications and discovery by the enemy.  In a forest fire, terrain is a big factor and there tend to be very large voids in the middle of the area to be connected. Urban fire fighting, EMT, and police require rapid, reliable communications, but deal with very complicated terrain and may need to deal with security issues. Technological solutions that work in one setting might be useless in another. Focusing on the higher-level MANET issues means that user can select lower-level solutions that best fit their needs.

John P. Mullen
(575) 646-2958
[email-masked]

________________________________
From: [email-masked] [mailto:[email-masked]] On Behalf Of Hongwei Zhang
Sent: Thursday, July 31, 2008 12:20 PM
To: Philip Levis
Cc: Philippe Jacquet; [email-masked]
Subject: Re: [manet] Comment on draft-dearlove-olsrv2-metrics-02

A follow up on Phil's comment on the drawbacks of beacon-based link estimation:

we have done some detailed study on the error of beacon-based link estimation in both mote networks and 802.11b networks. Please find below two articles on these studies:
http://www.cs.wayne.edu/~hzhang/group/TR/DNC-TR-08-02.pdf
http://www.cs.wayne.edu/~hzhang/group/publications/LOF-journal.pdf
As far as the Internet Draft is concerned, perhaps it does not have to specify the specific method of estimating certain metrics, instead it only needs to provide the right interface for incorporating different estimation methods. IMHO, how to share/diffuse control information (as was the original focus of the MANET focus?) may well be an orthogonal issue w.r.t. what control information/metric to use in routing and how to get that information.

Hongwei
---

Philip Levis wrote:

Dear Henning,

That's a great idea. Surely Freifunk experience in metric handling  will provide a central help to this initiative. ETX is using link  quality via hello loss rate? I would like to experiment it on  OLSRv2. Do you have more details about it?

Can you be more precise by what you mean by ETX? I don't mean to be  dense, but the acronym tends to be used in two ways. The first use is  a metric -- Estimated Transmissions -- which can be computed in a  bunch of ways. The second use is a particular algorithm developed at  MIT for computing this value.

The ETX algorithm computes the ETX metric by measuring a sliding  window of beacons. Note that his is insufficient for 802.11b due to  variable bitrates, so you need to either run ETX on each bitrate  independently or just run it at one of them and then use a dynamic  bitrate selection algorithm.

There are several other algorithms for computing the ETX metic. These  days, consensus seems to be that directly using data traffic is  greatly superior to beacons. You use beacons for discovery and rough  estimates, but use whether you receive L2 acks to directly measure the  estimated transmissions. One major problem with beacons is bursty  links will perform terribly: while the PRR might be 80% (ETX = 1.25),  this can be because there are 2-second periods of 0% PRR, leading to  huge numbers of retransmissions. Most wireless networks tend to be  bursty.

If you're interested in this, I can send you some sample source code  and some references.

Phil

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