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

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 14 Apr 2010 16:55:27 -0700

On Wed, Mar 17, 2010 at 9:52 AM, Henning Rogge <[email-masked]> wrote:
> 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.
>
>> >> 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).
>>
>> 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.

I finished doing experiments comparing ewma link estimator and fixed
window estimator with a window size of 10.

Here are the results:
http://stuff.stanford.edu/~om_p/ctp/ewmawindowle.html

The summary is window ETX seems too sensitive causing high churn and
resulting in poor path selection. EWMA seems to work much better.

- om_p

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Apr 2010 17:15:31 -0700

> resulting in poor path selection. EWMA seems to work much better.

Om,

These are interesting results, but are probably also dependent on the parameters used. For example, we settled on an alpha of 0.9 for EWMA in CTP based on a lot of experiments. Maybe the right thing to do is experiment with window sizes, find the "best" window size, then compare that with EWMA?

Phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 14 Apr 2010 19:12:57 -0700

> These are interesting results, but are probably also dependent on the parameters used. For example, we settled on an alpha of 0.9 for EWMA in CTP based on a lot of experiments. Maybe the right thin…

Sorry, it wasn't the intention to say window ETX is always worse than
EWMA. Agree - the results are dependent on the experiment parameters.
I expect things to be "smoother" with larger windows. Maybe I should
try a window size of 16 next time. On quiet channels there does not
seem to be much difference. The focus of future study should be noisy
channels.

- om_p

---

From: Henning Rogge <[email-masked]>
Date: Thu, 15 Apr 2010 08:13:19 +0200

On Thu April 15 2010 01:55:27 Omprakash Gnawali wrote:
> >> > 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).
> > 
> >> >> 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).
> >> 
> >> accurate as possible: the perfect LQ would simply output 0 or 1 (will
> >> this packet be delivered).
> > 
> > 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.
> 
10 seems to be a very low ETX window size.
 
> resulting in poor path selection. EWMA seems to work much better.
Using all incoming packets to calculate the ETX value and using a fixed sliding 
window of binary events (received/lost) is not a good idea.

Packet transmission over a link does not happen in constant intervals, so the 
your metric will jump up/down very quickly if you receive/loose a burst of 
packets.

I'm not surprised that ETX does not behave well in this scenario.

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: Thu, 15 Apr 2010 09:01:44 +0200

On Thu April 15 2010 08:56:20 Yoav Ben-Yehezkel wrote:
> I agree that doing a windowing mechanism on "failure rates" (i.e.
> #retransmissions over a fixed time window) instead of a windowing
> mechanism on "number of failures" without any time normalization would
> make more sense as a meaningful metric.
It might be interesting if EWMA over "failure rates" behaves as well (or 
better) than sliding window over failure rates.

Henning Rogge

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 15 Apr 2010 09:12:27 -0700

> I'm not surprised that ETX does not behave well in this scenario.

Earlier you had mentioned that Window ETX has been used in a
deployment (Freifunk?) and it showed great improvement over EWMA ETX.
It will be great if you can send the precise details of that estimator
and the experiment/deployment scenario so I can evaluate it on the
15.4 on the 54-node testbed. There are probably many ways to improve
the Window ETX but I am afraid I don't have the cycles to explore that
rather large design space. I am simply offering to provide a data
point or two on mechanisms that are known to work on other
environments or experiments.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 15 Apr 2010 09:21:07 -0700

> make more sense as a meaningful metric.

My implementation used a fixed window (10) of the number of packets
success/failure. I wasn't sure that is what you were referring to with
"number of failures".

Failure rate makes sense but there are may other design choices that
make sense as well. If you have experimental parameters and evidence,
which makes this approach to make more sense, it will be great if you
can share them, especially the experiment setup parameters (the
estimator as well as network on which such ideas were tested) so that
my experiments aren't too far off from yours.

- om_p

---

From: Philip Levis <[email-masked]>
Date: Thu, 15 Apr 2010 09:24:42 -0700

> my experiments aren't too far off from yours.

I think the basic difference is whether the link quality is measured with data packets or periodic beacons. The standard mesh approach is the latter, while your experiment used the former?

Phil

---

From: Henning Rogge <[email-masked]>
Date: Thu, 15 Apr 2010 18:24:29 +0200

> environments or experiments.
We have used packet based ETX for a long time (with a window size of 128), but 
it was not 'time stable' (because the it averaged the arrival of packets, not 
the arrival rate). We tried to replace it with an ETX based on EWMA, but it 
didn't worked well for our scenario, either converging to slowly or jumping 
up/down too much (the code had no working hysteresis at this point).

At the moment we are using a ETX with a sliding window which counts the 
received and lost packets during each second, then add them all together and 
use them to calculate the average rate, this seems to be working very well 
(and is very easy to do in integer arithmetics).

I was thinking about using an EWMA over a "rate within the last second" value, 
but I fear that it breaks down if it get's not enough packets within a second. 
This would mean the 'inaccurate' new measurement will influence the total ETX 
value too much.

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

---

From: Henning Rogge <[email-masked]>
Date: Thu, 15 Apr 2010 18:27:27 +0200

Am Donnerstag 15 April 2010 18:24:42 schrieb Philip Levis:
> I think the basic difference is whether the link quality is measured with
> data packets or periodic beacons. The standard mesh approach is the
> latter, while your experiment used the former?
In OLSR you can measure the arrival rate of all OLSR packets instead of using 
only the Hello messages. This allow you for a better estimation of link 
quality for larger meshs (more TCs !).

Henning Rogge

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 15 Apr 2010 09:56:20 +0300

Thanks,
Yoav

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Henning Rogge
Sent: Thursday, April 15, 2010 9:13 AM
To: [email-masked]
Cc: MANET IETF; Marcello Caleffi; Thomas Heide Clausen
Subject: Re: [Roll] [manet] Fwd: New Version Notification for
draft-gnawali-roll-etxof-00

On Thu April 15 2010 01:55:27 Omprakash Gnawali wrote:
> >> > 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.
> >
> > 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).
> >
> >> >> 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).
> >>
> >> 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.
> >
> > 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"

> resulting in poor path selection. EWMA seems to work much better.
Using all incoming packets to calculate the ETX value and using a fixed
sliding window of binary events (received/lost) is not a good idea.

Packet transmission over a link does not happen in constant intervals, so
the your metric will jump up/down very quickly if you receive/loose a
burst of packets.

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: Omprakash Gnawali <[email-masked]>
Date: Thu, 15 Apr 2010 09:52:13 -0700

> I think the basic difference is whether the link quality is measured with data packets or periodic beacons. The standard mesh approach is the latter, while your experiment used the former?

I was using data and control packets. This might be one major
difference between the standard mesh approach and CTP-ewma/window
approach.

- om_p

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 15 Apr 2010 19:31:48 +0300

Yes. That was my intention and I think also the MANET RFC spoke of some
TIME_INTERVAL.

I'm sorry Omprakash that I have no inputs that I can share with you other
than my intuition from past experience of a somewhat similar mechanism in
a proprietary protocol (for measuring management packet rates), so I know
the windowed estimation of rates works pretty well. The only issue is to
select a large enough time-window size to have a reasonable amount of
samples.

Thanks,
Yoav

-----Original Message-----
From: Philip Levis [mailto:[email-masked]]
Sent: Thursday, April 15, 2010 7:25 PM
To: Omprakash Gnawali
Cc: Yoav Ben-Yehezkel; MANET IETF; [email-masked]; Thomas Heide Clausen
Subject: Re: [manet] [Roll] Fwd: New Version Notification for

Phil