Subject: [manet] OLSRv2: which node defines link metric

From: Teco Boot <[email-masked]>
Date: Thu, 24 Nov 2011 07:31:53 +0100

In March 2010, there was a discussion on having the Tx *or* the 
Rx neighbor to decide what the metric of the link between the 
neighbors would be. In the current version, the Rx node decides.
Arguments were that this node knows data rate / modulation (bps) 
and signal / link quality (RSSI/ETX). The Tx node knows the 
data rate / modulation and the number of retries (Best Throughput 
in bps or ETT is seconds). I did some observations on usefulness 
of this information, with 802.11 radios & Minstrel rate selection. 
I did set up some probing for triggering Minstrel.

I saw that Best Throughput was very similar to TCP performance.
ETX (the unidirectional part on Rx side) was a reasonable indication,
but not with a linear conversion. RSSI was a bad indication. But RSSI
responds quickly to changes on RF link.

Anyway, both Tx and Rx nodes have useful information. Tx node sends
the TC message. So what is needed:
a) Rx node sends info to Tx node. Tx node defines link metric and 
advertises it with TC and hello.
b) Tx node sends info to Rx node. Rx node defines link metric and
sends this with hello to Tx node. Tx node advertises it with TC.

Option a) looks more efficient to me. Why is option b) taken?
Thread ended with (from Christopher):
> I will just note that we didn't pick this out of a hat, I recall
> discussions that were agreed on this, and I haven't seen any reason
> so far to suggest a change. (There are minor Tx advantages, but these
> are things that can be handled at the Rx. There are major Rx advantages
> that can't be handled at the Tx without extra signalling.)

I say: if handled at Rx, it needs more complex signalling. And at Tx,
more accurate info may be available (related to info that may be 
available at Rx).

Teco

---

From: "A. Riley Eller" <[email-masked]>
Date: Mon, 28 Nov 2011 13:21:34 -0800

Teco,

What about c) Each node transmits relevant Rx-side link info about each neighbor in hello, computes a link cost independently, and transmits the resulting value in TC.

This has been most effective for me in the past. Especially when using a time-based metric such as EFT (or ETT, which can be seen as a degenerate case of EFT).

Riley

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Teco Boot
Sent: Wednesday, November 23, 2011 10:32 PM
To: [email-masked] IETF
Subject: [manet] OLSRv2: which node defines link metric

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

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 28 Nov 2011 23:11:16 +0100 (CET)

I agree that Rx nodes know the hello loss rate from which it can deduce the average retries number of the link (Tx,Rx) and so deduce the effective bandwidth. But the links advertized in TC are used in the reverse way, thus MPR must be computed on reverse link quality (so easily available on Tx side). But TC advertizement by Rx should be done via Tx link quality information. But if we assume that link metric is symmetric, Rx advertizement would need less local exchanges. 

Does anyone have aspirin?

Philippe

----- Mail original -----
De: "A. Riley Eller" <[email-masked]>
À: "Teco Boot" <[email-masked]>, "[email-masked] IETF" <[email-masked]>
Envoyé: Lundi 28 Novembre 2011 22:21:34
Objet: Re: [manet] OLSRv2: which node defines link metric

Teco,

Riley

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Teco Boot
Sent: Wednesday, November 23, 2011 10:32 PM
To: [email-masked] IETF
Subject: [manet] OLSRv2: which node defines link metric

Teco

---

From: "A. Riley Eller" <[email-masked]>
Date: Mon, 28 Nov 2011 14:28:28 -0800

But I think that you're confusing the effectiveness of the implementation with the effectiveness of the standard. Authors should have the freedom to explore algorithms for computing metrics without waiting for a MANET WG release. I say that the "assume symmetry" option is quite acceptable for the recommended implementation.

-----Original Message-----
From: Philippe Jacquet [mailto:[email-masked]] 
Sent: Monday, November 28, 2011 2:11 PM
To: A. Riley Eller
Cc: Teco Boot; [email-masked] IETF
Subject: Re: [manet] OLSRv2: which node defines link metric

Philippe

----- Mail original -----
De: "A. Riley Eller" <[email-masked]>
À: "Teco Boot" <[email-masked]>, "[email-masked] IETF" <[email-masked]>
Envoyé: Lundi 28 Novembre 2011 22:21:34
Objet: Re: [manet] OLSRv2: which node defines link metric

Teco,

Riley

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Teco Boot
Sent: Wednesday, November 23, 2011 10:32 PM
To: [email-masked] IETF
Subject: [manet] OLSRv2: which node defines link metric

Teco

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 28 Nov 2011 15:28:17 -0800

Hello folks,

I'd given up on the link metric discussion a long time
ago, and maybe some things have changed that escaped
my notice.  I had argued for the inclusion of a "type"
field for the metric -- e.g., "delay", "cost", "ETX",
"least occupancy", "throughput", bit-error rate, ...
This would not be a short list of types, but it would
be manageable.

Without knowing the type, it is possible to have some
seriously bad effects.  For instance, suppose there are
three metrics of interest, and three disjoint paths
between source and destination.  If each node advertises
whatever metric value it chooses, without coordination
or type, it is possible for the source to always pick
the _worst_ path for any of the three metrics.  The
degree of "worstness" can be arbitrarily large.  I'm
certain this can be extended to always picking the
_worst_ path for any of N possible metrics, and also
to many different topologies -- not just disjoint
paths.  I am not sure if the topology can be
completely arbitrary, or how to characterize the
methods by which node advertisements can produce
this terrible behavior.  It's no doubt an interesting
research problem.

I was assured in several conversations that this was
not an issue and that including a type for the metric
was a non-starter.  At that point, I really had to
surrender.  At least the metrics as defined do not
lead to routing loops.

If this has been solved, please send me a URL for
the document so I can read about it, and accept my
apology for the distraction.

Regards,
Charlie P.

On 11/28/2011 2:28 PM, A. Riley Eller wrote:
> De: "A. Riley Eller"<[email-masked]>
> À: "Teco Boot"<[email-masked]>, "[email-masked] IETF"<[email-masked]>
> of this information, with 802.11 radios&  Minstrel rate selection.

---

From: Teco Boot <[email-masked]>
Date: Tue, 29 Nov 2011 07:04:16 +0100

The standard needs a dimensionless metric, all nodes MUST 
support it. In addition, other metric types may be supported.
I did not see a proposal yet.

I have seen designs were user data was nothing related to 
signaling of the network protocols. Adding metric types may 
have such disadvantage.

Teco

---

From: Teco Boot <[email-masked]>
Date: Tue, 29 Nov 2011 07:07:10 +0100

> But I think that you're confusing the effectiveness of the implementation with the effectiveness of the standard. Authors should have the freedom to explore algorithms for computing metrics without…

My experience is that RF links are not symmetric at all, even with homogenous gear.

Teco

---

From: Teco Boot <[email-masked]>
Date: Tue, 29 Nov 2011 07:29:12 +0100

Op 28 nov. 2011, om 23:11 heeft Philippe Jacquet het volgende geschreven:

> I agree that Rx nodes know the hello loss rate from which it can deduce the average retries number of the link (Tx,Rx) and so deduce the effective bandwidth.

Hello loss can be different from unicast data loss at higher data rates. I see data rate decrease with Tx-Rx distance increase. In the grey zone, multicast loss happens to occur more frequent. This is why Tx node may have better info.

> But the links advertized in TC are used in the reverse way, thus MPR must be computed on reverse link quality (so easily available on Tx side). But TC advertizement by Rx should be done via Tx link quality information. But if we assume that link metric is symmetric, Rx advertizement would need less local exchanges. 
> 

I havn't. Let's keep TC send Tx link metrics. 

Teco

---

From: Henning Rogge <[email-masked]>
Date: Tue, 29 Nov 2011 08:43:51 +0100

I think this is not only a matter of 'implementation efficiency', but 
also protocol simplicity.

Which node has 'better' data on a link metric is metric specific, we 
should not choose the internals on the protocol because of this.

The more important question is which node decides on the information in 
the TC and which nodes generates the TC.

Like Teco said, in the current draft the link metric is defined by the 
Rx node, then its transmitted to the Tx node and included into a TC there.

If the metric algorithm measures the necessary data at the receiver 
side, this means the information will have to be forwarded ONCE inside a 
HELLO before it can be put into the TC. If it measures the data on the 
transmitter side, it has to be forwarded TWICE.

If we swap the responsibility of the metric definition, this changes. 
When measuring the data on the receiver side, we still need to forward 
it ONCE in a HELLO to include it into the TC there, if the metric 
algorithm measures it on the transmitter side, it does not need to be 
forwarded at all.

This means defining the metric on the transmitter side will reduce the 
number of 'data forwards' necessary to create the TC by TWO for 
transmitter dependent metrics and will not cost us anything for receiver 
dependent metrics.

This also has some security concerns I think. If metric definition and 
TC generation is done on the same node, it might be easier to guarantee 
that the right value is put into the TC, which simplifies signature 
strategies.

So I support the Teco's suggestion to move the metric definition into 
the node also responsible putting it into the TC.

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: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 29 Nov 2011 09:31:25 -0000

There is a type field (the MPR type extension) for the metric
and has been for a long time now.

-- 
Christopher Dearlove
Technology Leader, Communications Group
Communications and Networks Capability
BAE Systems Advanced Technology Centre
West Hanningfield Road, Great Baddow, Chelmsford, CM2 8HN, UK
Tel: +44 1245 242194  Fax: +44 1245 242124

BAE Systems (Operations) Limited
Registered Office: Warwick House, PO Box 87,
Farnborough Aerospace Centre, Farnborough, Hants, GU14 6YU, UK
Registered in England & Wales No: 1996687

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Charles E. Perkins
Sent: 28 November 2011 23:28
To: [email-masked]
Cc: Philippe Jacquet
Subject: Re: [manet] OLSRv2: which node defines link metric

                    *** WARNING ***

  This message has originated outside your organisation,
  either from an external partner or the Global Internet. 
      Keep this in mind if you answer this message.

Hello folks,

Regards,
Charlie P.

********************************************************************
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: Tue, 29 Nov 2011 09:32:31 -0000

Defining additional specific types is for separate protocol
definition.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Teco Boot
Sent: 29 November 2011 06:04
To: [email-masked]
Cc: Philippe Jacquet; [email-masked]
Subject: Re: [manet] OLSRv2: which node defines link metric

                    *** WARNING ***

Teco

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 29 Nov 2011 09:41:33 -0000

Protocol simplicity argues exactly opposite to you.

Node A transmits. It can't say anything about the metric to or
from node B because it has no idea node B exists.

Node B receives node A's HELLO message. It can say things about
the link from node B to node A. It knows nothing about the link
from node B to node A as there hasn't been any such transmission.
Firthermore even when it transmits its own HELLO message, there
still has been no transmission from node B to node A, as this is
a broadcast transmission. In fact all OLSRv2 transmissiona are
broadcast.

We want (and with the modifications that result from what was
discussed at the meeting, need) to attach a metric as soon as
possible (even if only a maximum value pending more information).

The security argument is also falwed. A nodes relies on so much
from its neighbour - it's address for one thing, and its neighbour
information for another. The concepts of "I can trust all that, but
not the metric" or "I can protect all that, but not the metric"
don't make sense.

This is all apart from that this discussion is years too late. I
can think of little better designed to delay OLSRv2 yet again, or
even delayed to death, than reopening decisions already made by
the WG.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Henning Rogge
Sent: 29 November 2011 07:44
To: [email-masked]
Subject: Re: [manet] OLSRv2: which node defines link metric

Henning Rogge

---

From: Dr John P Mullen <[email-masked]>
Date: Tue, 29 Nov 2011 10:19:22 -0700

HI,

It has been a while, but I've been tracking the discussions.

Several years ago, I published some papers on the nature of wireless links. The issue is that they are stochastic in nature and that no single exchange tells us much. Any receiver might receive or fail to receive a packet from any transmitter at any distance. Also, as Teco pointed out, there is an inverse relationship between reliable transmission range and data  rate. This means that the ratio of transmission range to interference range also depends on data rate. I would agree with Rogge that the receiver knows more than the transmitter. Added to all of this is the fact that conditions would change due to multiple factors in a real-world wireless network.

A MANET has a number of issues related to reliable transmission which, I would say, is a very complex problem and an area of active research. While there is a massive body of knowledge in wireless propagation, the MANET environment adds a sufficient number of issues, which makes most of that body of work only marginally relevant in the MANET situation. Also, because MANETs are used in drastically differing environments, it is entirely possible that there is no single strategy that will work well in all cases. 

I would argue that it would be best to provide a place in the protocol for the quality of a link to be considered, but not try to definitely resolve the issue at this time. 

But, then again, what do I know. 

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Dearlove, Christopher (UK)
Sent: Tuesday, November 29, 2011 2:42 AM
To: Henning Rogge; [email-masked]
Subject: Re: [manet] OLSRv2: which node defines link metric

Node A transmits. It can't say anything about the metric to or from node B because it has no idea node B exists.

Node B receives node A's HELLO message. It can say things about the link from node B to node A. It knows nothing about the link from node B to node A as there hasn't been any such transmission.
Firthermore even when it transmits its own HELLO message, there still has been no transmission from node B to node A, as this is a broadcast transmission. In fact all OLSRv2 transmissiona are broadcast.

We want (and with the modifications that result from what was discussed at the meeting, need) to attach a metric as soon as possible (even if only a maximum value pending more information).

The security argument is also falwed. A nodes relies on so much from its neighbour - it's address for one thing, and its neighbour information for another. The concepts of "I can trust all that, but not the metric" or "I can protect all that, but not the metric"
don't make sense.

This is all apart from that this discussion is years too late. I can think of little better designed to delay OLSRv2 yet again, or even delayed to death, than reopening decisions already made by the WG.

BAE Systems (Operations) Limited
Registered Office: Warwick House, PO Box 87, Farnborough Aerospace Centre, Farnborough, Hants, GU14 6YU, UK Registered in England & Wales No: 1996687

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Henning Rogge
Sent: 29 November 2011 07:44
To: [email-masked]
Subject: Re: [manet] OLSRv2: which node defines link metric

I think this is not only a matter of 'implementation efficiency', but also protocol simplicity.

Which node has 'better' data on a link metric is metric specific, we should not choose the internals on the protocol because of this.

The more important question is which node decides on the information in the TC and which nodes generates the TC.

Like Teco said, in the current draft the link metric is defined by the Rx node, then its transmitted to the Tx node and included into a TC there.

If the metric algorithm measures the necessary data at the receiver side, this means the information will have to be forwarded ONCE inside a HELLO before it can be put into the TC. If it measures the data on the transmitter side, it has to be forwarded TWICE.

If we swap the responsibility of the metric definition, this changes. 
When measuring the data on the receiver side, we still need to forward it ONCE in a HELLO to include it into the TC there, if the metric algorithm measures it on the transmitter side, it does not need to be forwarded at all.

This means defining the metric on the transmitter side will reduce the number of 'data forwards' necessary to create the TC by TWO for transmitter dependent metrics and will not cost us anything for receiver dependent metrics.

This also has some security concerns I think. If metric definition and TC generation is done on the same node, it might be easier to guarantee that the right value is put into the TC, which simplifies signature strategies.

So I support the Teco's suggestion to move the metric definition into the node also responsible putting it into the TC.

Henning Rogge

On 11/24/2011 07:31 AM, Teco Boot wrote:
> In March 2010, there was a discussion on having the Tx *or* the Rx 
> neighbor to decide what the metric of the link between the neighbors 
> would be. In the current version, the Rx node decides.
> Arguments were that this node knows data rate / modulation (bps) and 
> signal / link quality (RSSI/ETX). The Tx node knows the data rate / 
> modulation and the number of retries (Best Throughput in bps or ETT is 
> seconds). I did some observations on usefulness of this information, 
> with 802.11 radios&  Minstrel rate selection.
>> are things that can be handled at the Rx. There are major Rx 
>> advantages that can't be handled at the Tx without extra signalling.)
>

--
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: Rex Buddenberg <[email-masked]>
Date: Tue, 29 Nov 2011 09:38:17 -0800

Chris,

There's some prior art -- albeit at layer 2 -- that applies.

IEEE 802.16 has a maintenance window -- contention access -- for new
subscriber stations that need to enter the network (the rest of the
frame structure is scheduled by the base station).

A wannabe subscriber competes (a la WiFi) to get a knock-knock message
to the base station.  (The starter is deliberately underpowered and gets
an increment each iteration).  This traffic is necessarily unprotected.

Once the base station hears the subscriber station, they exchange
ranging messages -- the kind of metrics you're talking about here.  Tidy
up power, modulation and timing.  Again, the traffic is unprotected.

Still in the contention window, the two stations exchange X.509 certs.
Up to this point, the traffic is vulnerable.  But 802.16 is a big step
forward from 802.11 where the base station is not required to
authenticate itself at all.

After all this foreplay, the base station accepts the subscriber station
and adds it to the schedule (removing it from the contention window).
And, at least in theory, the MAC messages can now all be protected.

Henning's comment is correct -- the ranging messages would not be very
valid outside the homogeneous 802.16 context.  Your observation is
correct -- the metrics are really hard to come by without two-way
interaction.

---

From: Teco Boot <[email-masked]>
Date: Wed, 30 Nov 2011 14:26:48 +0100

Some minor issues in the draft:

In:
> 15.3.2.1.  Updating Metrics
> 
>    For each address in a received HELLO message with an associated TLV
>    with Type = LINK_STATUS and Value = HEARD or Value = SYMMETRIC, an
>    incoming (to the message originator) link metric value is defined
skip
>    For each address in a received HELLO message with an associated TLV
>    with Type = LINK_STATUS and Value = SYMMETRIC, an outgoing (to the
>    message originator) link metric value is defined
> skip
>    For each address in a received HELLO message with an associated TLV
>    with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC,
>    an incoming (to the message originator) neighbor metric value is
>    defined
> skip
>    For each address in a received HELLO message with an associated TLV
>    with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC,
>    an outgoing (to the message originator) neighbor metric value is
>    defined
skip
I guess the 2nd and 4th _outgoing_ metrics are (_from_ the message originator).

In 16.3.1. Invalid Message (TC), are messages invalid if Neighbor_Metric_Outgoing
is not set or one or more of the other bits are set?
> 13.3.2.  Address Block TLVs
skip
>        Each bit of the types and directions sub-field, if set
>    ('1') indicates that the link metric is of the indicated kind and
>    direction.  Any combination of these bits MAY be used.
Alternative: leave 3 unused metric_type bits in TC reserved for future use.
(maybe a bad idea...)

In:
> Appendix D.  Constraints

skip
>    o  N_out_metric MUST equal the minimum value of the L_out_metric
>       values of all corresponding Link Tuples, if any, otherwise
>       N_out_metric = UNKNOWN_METRIC.

It misses: "only for links with L_status = SYMMETRIC".

Some thoughts:
After the Routing Set Calculation, the router has a set of R_next_iface_addr. 
I wonder how this can be used for Routing MPR selection. I would say:
  1) Use the set of second type (multi-hop) R_next_iface_addr as Routing MPRs.
  2) Links to neighbors that are not in R_next_iface_addr are excluded 
     in the TC message, if a TC is sent.
This algorithm removes the need for N_in_metric. And Routing MPR selection 
doesn't need an algorithm in addition to the required shortest path calculation.

When a router is Routing MPR or has attached_networks, it sends TC. For topology 
reduction, the number of routers sending TCs should be kept low. With link 
metrics, this optimization could be reduced. What about using eligible_for_backbone 
adjustment for the link metric? I suggest an ~1% decrement for each Routing MPR 
selector and for having attached networks. An increment is also possible, e.g.
for battery_gets_low.
Problem with this: current draft specifies that the link metric is defined at 
incoming side. So this info has to be send to neighbors first (same problem as Best 
Throughput).

If we add on optional L_in_metric_adjustment address block TLV, in HELLO messages, to 
be used by the receiver to take into account for defining L_in_metric. Could be one 
octet, default 64 and be used something like:
    L_in_metric  = external_L_in_metric * ( 64 + L_in_metric_adjustment ) / 128
This provides the sender some influence on the N_out_metric it sends out in TC 
messages, and as a consequence the to be forwarded traffic. It also may help
reducing the topology.

Teco

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Wed, 30 Nov 2011 14:06:12 -0000

Comments below with >>>

-----Original Message-----
From: Teco Boot [mailto:[email-masked]] 
Sent: 30 November 2011 13:27
To: Dearlove, Christopher (UK)
Cc: Henning Rogge; [email-masked]
Subject: Re: [manet] OLSRv2: which node defines link metric

                    *** WARNING ***

skip
skip

>>> That would be better. I think the original though was that "to" really
>>> meant "from the viewpoint of", but making these to and from works.

skip

>>> Leaving them so that future use could add more metrics to be reported
>>> in a TC message is exactly our intent. The philosophy (it was someone
>>> like Jon Postel who said this) was "be conservative in what you send
>>> and liberal in what you accept". We want to reject messages with
>>> information that shows a broken sender, or which would harm our ability
>>> to do our job, but accept (and ignore) things that we can safely do
>>> that for.

skip

>>> Yes.

Some thoughts:

>>> I'm not sure if this works or not, and for expositional purposes I'm not
>>> happy cross-coupling the MPR and routing calculations. I would just note
>>> that an implementation is free to do whatever it likes as long as it gets
>>> the right answers, and this could well be such an example.

>>> Before a node A even knopw node B exists and can communicate with it,
>>> node B has to transit a HELLO message with node A recorded in it. So
>>> there is no cost in terms of number of messages and timing in the
>>> agreed incoming metrics being used.

>>> With regard to the worsened topology reduction, this could, I agree, be
>>> and issue. I do not have data to quantify that in any way. I would not
>>> however like to try to make any change, either of the form you note or
>>> others for reasons of time, complexity and confidence.

Teco