Subject: [manet] New revision of OLSRv2 metric draft released

From: Henning Rogge <[email-masked]>
Date: Wed, 18 Sep 2013 10:20:41 +0200

Hi,

I finally found the time to update the metric draft I presented in
Berlin to revision 3. The new draft got a completely new structure to
improve readability and adds a few chapters that deal with other sources
of packet loss for metric calculation.

While I changed the title of the draft to reflect the difference to the
ETT metric described in literature, I kept the file name to keep the
revision history together. The filename can easily be changed if the WG
decides to adopt this draft.

http://www.ietf.org/id/draft-rogge-baccelli-olsrv2-ett-metric-03.txt
http://tools.ietf.org/html/draft-rogge-baccelli-olsrv2-ett-metric-03

Henning Rogge

-- 
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-961,   Fax +49 228 9435 685
mailto:[email-masked] http://www.fkie.fraunhofer.de

---

From: Teco Boot <[email-masked]>
Date: Wed, 18 Sep 2013 14:20:05 +0200

Great to see this progress!
Quick comments:

>    airtime  - the time a transmitted packet blocks a shared medium,
>       e.g., a wireless link.
Applies to non-shared also.

>    DAT  - Directional Airtime Metric, the link metric described in this
>       document, which is a directional variant of ETT.

... which does not take lost ACK's into account.

> the link-layer multicast transmission should not have a higher
>    reception probability than the slowest unicast transmission.
Only true if RTS_CTS is not used.
Also packet size plays its role.

> e.g. set the multicast data-rate to 6 MBit/s if you
>    use IEEE 802.11g only.

Isn't 6Mbps the lowest rate for 11a/g?
Maybe your intention is to use lowest 11g for multicast and allow lower 11b for unicast.

> Maximum packet loss is 15 of 16 packets (without link-
>    layer retransmissions), the unicast data-rate can be between 16
>    bits/s and 4 GBit/s. 
Isn't it DAT_MAXIMUM_LOSS := 16?
Isn't it a DAT_MAXIMUM_BITRATE := 16777216? With loss = 1 this results in maximum L_in_metric. See below.
I like the 16bit/s to 4Gbit/s range. But this needs some exponential encoding to fit in 24-bits field.

>    Instead of measuring the symmetric probability of a bidirectional
>    transmission of a packet over a link and back

"loss" is missing.

> There are multiple
>    reasons for this decision:

Main reason is that typically wireless links are not symmetric because for example deviation in Tx power, Rx sensitivity and noise/interference levels.

>    The Directional Airtime Metric does not integrate the packet size
>    into the link cost.  Doing so is not feasible in most link-state
>    routing protocol implementations, multiplying all link costs with the
>    size of a packet would not change the dijkstra result anyways.

I agree, but argumentation fails. Dijkstra can be run for all packet sizes, or classes of sizes.

>    The queue based packet loss estimator has been tested for a long time
>    in the OLSR.org ETX implementation, see Appendix A.  The output is a
>    time-stable average of the packet loss.

My experience is that hysteresis is implemented rather ugly. No config options, only at zero loss / ETX near to 1.
Dampening is OK (the time-stable average).

> the current packet loss rate is calculated by
>    storing packet reception and packet loss events.

"packet" is "MANET protocol packet" 

> this metric uses a fixed length double
>    queue to average the incoming events, one queue for received packets
>    and one for the total number of packets sent by the other side of the
>    link.
Not sure if it is correct. Maybe it is (updates are *marked*):
this metric uses a fixed length double queue to *measure and average the loss* events, one set of counters for received packets and one set of counters for the *estimated* packets sent by the other side of the link.

>    In addition to the queued packet loss, this metric uses a timer to
>    detect a total link-loss.
Loss of recent hello's. Link may still work.

>  For every NHDP HELLO interval in which the
>    metric received no packet from a neighbor, scales the number of
>    received packets in the queue
"scales incoming packet loss" in the queue?

> large enough to
>       take the delay for message aggregation into account.
And jitter.

> 3.  If diff > DAT_SEQNO_RESTART_DETECTION, then:

With DAT_SEQNO_RESTART_DETECTION = 8 and > 8 losses, what happens?
Maybe add restriction that DAT_SEQNO_RESTART_DETECTION > DAT_MAXIMUM_LOSS

>        1.  L_DAT_hello_time := current time + (L_DAT_hello_interval *
>            DAT_HELLO_TIMEOUT_FACTOR).

For all packets? Or only for hello packets?

>        4.  If bitrate < DAT_MINIMUM_BITRATE, then:
Maybe add:  If bitrate > DAT_MAXIMUM_BITRATE

>        5.  L_in_metric := (2^24 / DAT_MAXIMUM_LOSS) * loss / (bitrate /
>            DAT_MINIMUM_BITRATE).

So it is: 2^24 * ( loss / DAT_MAXIMUM_LOSS) * ( DAT_MINIMUM_BITRATE / bitrate )

              1 .. 16        16
Or:   2^24 * --------- * ------------
                16        16 .. 2^24

With max_bitrate := 2^24.
 
Teco

Op 18 sep. 2013, om 10:20 heeft Henning Rogge <[email-masked]> het volgende geschreven:

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

---

From: Henning Rogge <[email-masked]>
Date: Wed, 18 Sep 2013 16:50:29 +0200

> So it is: 2^24 * ( loss / DAT_MAXIMUM_LOSS) * ( DAT_MINIMUM_BITRATE / bitrate )

Ouch, you are right...

too much change in a single step.

I think a gigabit/s effective throughput should be within the metrics
limits... so we might need to increase the minimum datarate.

Have to rework the numbers.

Henning

---

From: Teco Boot <[email-masked]>
Date: Wed, 18 Sep 2013 17:38:27 +0200

> Have to rework the numbers.

Why not add some tuning parameters? There is no over the air part, so each node can have whatever config without breaking the protocol. Although I recommend same guidelines in a single network and some of it should be included in your draft.
Can be used for other metrics, if available. Could be costs (€), delay (satcom) etc. 
OK, 802.11 would have no costs and low delay. But in the network there could be for example ethernet bridges over satcom (high costs, high delay). The network administrator has to incorporate all of this. Every now and then it keeps me busy. Hard job...

Teco

---

From: Henning Rogge <[email-masked]>
Date: Thu, 19 Sep 2013 13:37:07 +0200

On 09/18/2013 02:20 PM, Teco Boot wrote:
> Great to see this progress! Quick comments:
> 
> 

Added to the next revision.

>> DAT  - Directional Airtime Metric, the link metric described in 
>> this document, which is a directional variant of ETT.
> 

It doesn't measure the ACK loss, but I am unsure there will be a lot of
situations where you get a symmetric link, have high ACK loss and low
packet loss.

But you are right... its a price we pay for a metric without a TLV to
communicate packet loss to the other side of the link.

> Only true if RTS_CTS is not used. Also packet size plays its role.

Still, ACKs are always very small... and RTS/CTS also protect the ACK.

>> e.g. set the multicast data-rate to 6 MBit/s if you use IEEE 
>> 802.11g only.
> 
> Isn't 6Mbps the lowest rate for 11a/g? Maybe your intention is to
> use lowest 11g for multicast and allow lower 11b for unicast.

I think we had the problem that some drivers started with 6 MBit/s
unicasts but allowed 1 MBit/s broadcast.

>> transmission of a packet over a link and back There are multiple 
> Main reason is that typically wireless links are not symmetric 
> because for example deviation in Tx power, Rx sensitivity and 
> noise/interference levels.

Yes.

>> routing protocol implementations, multiplying all link costs with 
>> the size of a packet would not change the dijkstra result anyways.
> 

Yes, you could run a dijkstra for all possible packet sizes (more than a
1000 runs on a typical IP network). They also would get you exactly the
same result on every run if you multiply the link costs with the packet
size.

>> The queue based packet loss estimator has been tested for a long 
>> time in the OLSR.org ETX implementation, see Appendix A.  The 
>> output is a time-stable average of the packet loss.
> 
> My experience is that hysteresis is implemented rather ugly. No 
> config options, only at zero loss / ETX near to 1. Dampening is OK 
> (the time-stable average).

This draft doesn't implement the hysteresis part of the OLSR.org ETX metric.

> Loss of recent hello's. Link may still work.

It detects the loss of packets by detecting the timout of a Hello. The
idea is that if you didn't got ANY packet for a Hello interval, you know
you have lost at least one packet.

>> large enough to take the delay for message aggregation into 
>> account.
> And jitter.

Good point.

> Maybe add restriction that DAT_SEQNO_RESTART_DETECTION > 

This is for router reboot detection.

If you use the packet sequence number to calculate packet loss, you run
into trouble if a router reboots and starts with a new packet sequence
number which is lower than the old one.

You suddenly detect the incoming packets as "outdated" or "already
received" packets and don't advance the Queue content correctly.

DAT_SEQNO_RESTART_DETECTION makes sure that if the difference between
your last received packets sequence number and the new sequence number
is too large and if your ONLY receive packet sequence numbers that large
(and none that doesn't trigger the reboot detection) you assume the
neighbor has rebooted and reset your "last received packet sequence
number" field.

> For all packets? Or only for hello packets?

As the draft says, for ALL packets.

The idea is you are looking for a Hello Interval with no received packet
at all.

> Maybe add:  If bitrate > DAT_MAXIMUM_BITRATE

With "too high" bitrates the link cost metric will just drop to a
fractional between one and zero, which should be turned to 1 during the
conversion into exponential encoding.

> Why not add some tuning parameters? There is no over the air part, so
> each node can have whatever config without breaking the protocol. 
> Although I recommend same guidelines in a single network and some of 
> it should be included in your draft. Can be used for other metrics, 
> if available. Could be costs (€), delay (satcom) etc.

> OK, 802.11 would have no costs and low delay. But in the network 
> there could be for example ethernet bridges over satcom (high costs,
>  high delay). The network administrator has to incorporate all of 
> this. Every now and then it keeps me busy. Hard job...

I am not sure this belongs into this metric draft. An admin can
add/multiply anything he wants onto the raw metric, as long as it is
being done in a meaningful and consistent way. It doesn't matter which
metric you start with.

Henning Rogge

---

From: Teco Boot <[email-masked]>
Date: Thu, 19 Sep 2013 17:26:58 +0200

> communicate packet loss to the other side of the link.

My experience is that ACK loss is low and I expect DAT would work better than ETT in many cases. So I am quite happy with your proposal.

> Still, ACKs are always very small... and RTS/CTS also protect the ACK.

I was wrong.
My point is that unicast with RTS_CTS has higher reception probability than multicast.
This helps achieving the requirement that multicast_loss >= unicast_loss.

> unicasts but allowed 1 MBit/s broadcast.

Hmm. Bug?

The advice to set multicast to a higher rate is useful: DAT would work better, multicast would have less overhead and grey zone problems are reduced. But link range would be decreased.

> same result on every run if you multiply the link costs with the packet

I agree we should go into this direction.
But when metrics are available for each frame size, we could have many distinct topologies.
Maybe adjust your arguments a bit, for example into "Doing so will need metrics exchange for each (class of) packet size(s) and as a result the overhead would be large."

> This draft doesn't implement the hysteresis part of the OLSR.org ETX metric.

Maybe add a few words on dampening (the data rate part) and hysteresis (reduce frequency of topology changes).

> you have lost at least one packet.

Yes, I understand. But is this a "total link-loss"? Maybe just wording.

> neighbor has rebooted and reset your "last received packet sequence

I understand the need for it.
But with 8 < #_losses < 16, restart detection is triggered, isn't it?

> The idea is you are looking for a Hello Interval with no received packet

Yes. But setting L_DAT_hello_time should only be set at hello reception, I think.
Same for next step:
    5.   L_DAT_lost_hello_messages := 0.

Maybe DAT would work as you designed, but it is not that obvious. You postpone L_DAT_hello_time by reception of non-hello packets and set L_DAT_lost_hello_messages to zero while hello's were lost.

> conversion into exponential encoding.

Yes, but better specify that it must do so. 

> being done in a meaningful and consistent way. It doesn't matter which

I agree it is more BCP kind of stuff.
This DAT mechanism doesn't have an over the air component. So could be seen as BCP also.

Teco

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 29 Sep 2013 22:21:32 +0200

> situations where you get a symmetric link, have high ACK loss and low

I'd really like to see actual experimental data to confirm that.
Especially with heterogeneous nodes (some nodes with nice antennas,
and some with poor ones).

Henning, my intuition is the same as yours -- most marginal links are
unidirectional, so they will be dropped early, and the few marginal
links that remain are likely to be roughly symmetric.  But intuitions
are sometimes wrong -- I really think you ought to publish some hard
data before you push this draft for RFC.

-- Juliusz

---

From: Teco Boot <[email-masked]>
Date: Mon, 30 Sep 2013 12:31:25 +0200

> and some with poor ones).
I is not the antennas that make the difference. RF path is symmetric.
It is the difference in Tx power, Rx sensitivity, noise floor etc. 

> data before you push this draft for RFC.
Can you specify what you would like to see? Link asymmetry? Or data on ACK loss and how this relates to MANET protocol packet loss?

Teco