Subject: [manet] SMF in Manet and MPR

From: Henning Rogge <[email-masked]>
Date: Mon, 21 Mar 2022 14:06:39 +0100

Hi,

I am reacting to the talk during the IETF meeting (chat didn't worked
for me for some reason).

My trouble with the MPR optimization for SMF (and a bit with SMF in
general) is that we currently have no good MPR algorithm for
heterogeneous Manet (Manet with multiple different types of radios).

The only described MPR algorithm (OLSRv2 appendix) works separately
for each interface... which means it always selects MPRs on long-range
(and slow) interfaces, which is really not what we want.

Of course there is also the problem that SMF completely ignores
routing metrics... and the problem that we lack a good dataplane for
SMF, which often results in horrible "raw socket trickery"...

So in general I would not suggest to people using SMF because I have
yet to find an use-case where SMF is doing well. Often an
application-specific forwarding strategy is much better than a generic
IP one in terms of multicast in Manet.

Henning Rogge

---

From: "Adamson, Robert B CIV USN NRL (5522) Washington DC (USA)" <[email-masked]>
Date: Mon, 21 Mar 2022 13:28:31 +0000

Hi Henning,

I didn't participate in the discussion you mention but agree that heterogenous MANET is particularly challenging for multicast.  SMF by itself with distributed CDS relay set formation can't optimize (or even approximate it well) without multi-hop signaling.  I have been continuing to experiment (part time as I have opportunity) with the Elastic Multicast concept we presented several years ago.  The current "nrlsmf" implementation includes a variety of Elastic Multicast operating modes.  One of those use the an Elastic Multicast flow advertisement (EM_ADV) message that propagates from multicast sources and builds up an ETX path metric that can be used by "downstream" nodes (and/or receivers) to select (and acknowledge via EM_ACK messages) upstream relays according to that metric.  I also plan to extend the code to support advertising the maximum supportable path bandwidth (and possibly even RTT) for flows in that signaling including report back to the source of available path bandwidth.   That would allow for other metrics to be used in the forwarding tree/mesh selection.  This quickly gets into the application-specific domain if imagine how that information could be used.  It does seem there could be benefit for multiple applications being able leverage a common, underlying signaling approach like this.  Even though my code does not yet use PACKET BB (I was lazy on that while I'm still figuring out what meaningful information signaling messages should include), that could be done and integrated as an add-on to existing MANET signaling.  I.e., as opposed to each application implementing its own independent signaling.

Best regards,

Brian

On 3/21/22, 9:08 AM, "manet on behalf of Henning Rogge" <[email-masked] on behalf of [email-masked]> wrote:

    Hi,

    Henning Rogge

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

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 21 Mar 2022 17:02:08 +0100 (CET)

I apologise that I didn't follow too much Manet these last years. As far as I remember the multiple interface MPR stuff with OLSRv2 were assuming that the interfaces were capable to support the topology control traffic, which was supposed to be the sole source of multicast traffic. But if the multicast traffic is demanding significant capacity, there were in the literature some efficient ways to select the MPR according to the demanded QoS. But this supposes that the traffic comes with QoS requirement TLS. 

I hope it helps,

Philippe

----- Mail original -----
De: "Henning Rogge" <[email-masked]>
À: "[email-masked] IETF" <[email-masked]>
Envoyé: Lundi 21 Mars 2022 14:06:39
Objet: [manet] SMF in Manet and MPR

Hi,

Henning Rogge

---

From: Christopher Dearlove <[email-masked]>
Date: Mon, 21 Mar 2022 18:17:52 +0000

> (and slow) interfaces, which is really not what we want.

This depends on how you set up your link metrics. Flooding MPRs have
the option to use or not use link metrics. But if your interfaces are different
enough that you’d rather use multiple hops on a better interface rather
than fewer hops on a poorer interface, then you should be using link metrics.
If you aren’t, you will have problems. (They probably show up even faster
with routing.)

How to create those metrics? Now that is an unspecified problem. But the
problem is that, not the MPR algorithm itself.

Now is there a problem with the MPR algorithm? No and yes. No, it does
what it should. Yes, in that there are things that it doesn’t consider that
could improve it. One of those is whether it’s better to distribute or
concentrate MPRs, which depends on factors beyond where OLSRv2
could go, including the nature of your MAC layer, on the battery limitations
of your devices, and on your mobility (is a critical node destined to always
be a critical node, or does that keep changing?) Also, when your topology
changes, should you try to make minimal changes to your MPR selection
or should you try to always be maximally efficient? (My implementation,
which I no longer have access to, offered you at least three options there.)

> SMF, which often results in horrible "raw socket trickery"...

And so the problem here is with that SMF predates link metrics, and hasn’t
been updated. It was even worse when I - and others - tried multicasting
by intercepting packets in the stack, wrapping them up as a new OLSR (v1)
message type and reinjecting into UDP (OLSR port), plus the reverse at
reception. Fun days.

---

From: Henning Rogge <[email-masked]>
Date: Tue, 22 Mar 2022 07:29:21 +0100

> If you aren’t, you will have problems. (They probably show up even faster

I don't think metrics can resolve my problem. The problem arises from
calculating the MPRs just from the 2-hop neighborhood.

Let me sketch the problem.... imagine you have a Mesh with both VHF
(slow long range) and UHR (fast short range) radios.

Now imagine your router R has a neighbor A on VHF, which is two-hop
reachable on UHF... if A also has a neighbor even further away, A will
ALWAYS be a MPR, because the neighbor of A is at least three hops away
over UHV.

Unicast routes will still flow over the UHF network, but flooding will
be done over VHF, which is a problem.

> message type and reinjecting into UDP (OLSR port), plus the reverse at

The OLSR implementation from olsr.org has something like this called
BMF... it was a disaster. ^^

Henning Rogge

---

From: Christopher Dearlove <[email-masked]>
Date: Tue, 22 Mar 2022 08:23:41 +0000

Flooding is done over the VHF interface because the whole point of flooding is to reach everyone. And there might be some routers you can only reach using the VHF interface. If you know that you can always reach someone using only UHF flooding, and you consider that flooding via VHF is a disaster, why is it one of your Manet interfaces? Or if you want one hop transmission but not MPR selection why not set willingness zero (never) on that interface?

> On 22 Mar 2022, at 06:31, Henning Rogge <[email-masked]> wrote:
>

---

From: Henning Rogge <[email-masked]>
Date: Tue, 22 Mar 2022 09:37:47 +0100

My point about this issue is that as soon as the router knows that
there is a better way to a one-hop neighbor than the direct one, it
needs to stop using the link neighbor for flooding. But this is not
possible based on NHDP information, only with the help of the full
routing graph... which gives quite a few additional challenges because
of the cyclic dependencies.

It's the same both for TC flooding and Multicast forwarding. Using a
VHF connection to flood them is a waste of precious (VHF) airtime if
we have a multihop UHF connection. It's just getting worse when we add
userspace (multicast) traffic to the issue.

Henning Rogge

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 23 Mar 2022 21:04:28 +0100 (CET)

If you choose the MPR with a given metric then the routing graph will automatically show the shortest path wrt the metric as the consequence of the 2 hop MPR coverage property. If such path does not exist then the flooding cannot be achieved wrt the metric. 

Philippe

----- Mail original -----
De: "Henning Rogge" <[email-masked]>
À: "Christopher Dearlove" <[email-masked]>
Cc: "[email-masked] IETF" <[email-masked]>
Envoyé: Mardi 22 Mars 2022 09:37:47
Objet: Re: [manet] SMF in Manet and MPR

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Wed, 23 Mar 2022 21:41:11 +0100

The problem is there might be a shorter 3-hop path to a single-hop
neighbor than the direct path to it... which leads to a bad MPR
choice.

So I think NHDP-based MPR selection is sub-optimal.

Henning Rogge

---

From: Christopher Dearlove <[email-masked]>
Date: Wed, 23 Mar 2022 21:21:17 +0000

If there’s a shorter route, even if more hops, MPRs will find it. So not suboptimal in that regard.

Flooding will try to travel over a shortest route. It might also flood via other routes, because that’s the nature of flooding.

Flooding might be suboptimal in some regards, though not that one. But of course in NHDP/OLSRv2 to want optimality is to put the cart before the horse. We use the MPR flooding to find out remote information. We couldn’t use it - even if we collected the right metrics - to select MPRs as we already need them.

> On 23 Mar 2022, at 20:41, Henning Rogge <[email-masked]> wrote:
>

---

From: "Adamson, Robert B CIV USN NRL (5522) Washington DC (USA)" <[email-masked]>
Date: Wed, 23 Mar 2022 21:29:38 +0000

I think there is some interesting things that could be done using the MPR approach with some criteria.  For example, you could use source-based MPRs to build a shortest path tree that met certain criteria (e.g., minimum throughput useful to the sender application or some other set of QoS criteria).  This isn't that different to what I was describing with the experimental Elastic Multicast work that rides on top of SMF (MPR-based, ECDS, even classic flooding) as it gets into per-source (and even per flow) semantics ...

On 3/23/22, 3:21 PM, "manet on behalf of Christopher Dearlove" <[email-masked] on behalf of [email-masked]> wrote:

---

From: "Adamson, Robert B CIV USN NRL (5522) Washington DC (USA)" <[email-masked]>
Date: Thu, 24 Mar 2022 10:54:12 +0000

---

From: Christopher Dearlove <[email-masked]>
Date: Thu, 24 Mar 2022 11:56:23 +0000

One of the best and worst things is that you have so many options - and that you can change everything dynamically. Separately parameterised interfaces, in particular message intervals. Link metrics (of different sorts). Willingness. That the MPR selection process is only specified by characteristics. That you can advertise more than the minimum needed. And more.

There’s an RFC or paper we never wrote (fragments of it exist unpublished) discussing parts of this (which overlaps with motivation as to why).

> On 23 Mar 2022, at 21:29, Adamson, Robert B CIV USN NRL (5522) Washington DC (USA) <[email-masked]> wrote:
>

---

From: Philippe Jacquet <[email-masked]>
Date: Thu, 24 Mar 2022 13:07:13 +0100 (CET)

Maybe I was not clear. By shortest path, I meant the smallest number of hops for paths fitting a given metric. If your metric is "second per bit" (inverse of throughput), you will obtain the shortest path with a given throughput constraint. 

If VHF interface cannot fit the metric you will get a path made of UHF interfaces.

Philippe

----- Mail original -----
De: "Henning Rogge" <[email-masked]>
À: "Philippe Jacquet" <[email-masked]>
Cc: "Christopher Dearlove" <[email-masked]>, "[email-masked] IETF" <[email-masked]>
Envoyé: Mercredi 23 Mars 2022 21:41:11
Objet: Re: [manet] SMF in Manet and MPR

Henning Rogge

---

From: Christopher Dearlove <[email-masked]>
Date: Thu, 24 Mar 2022 12:14:41 +0000

Often it’s sufficient just to have a small number of metrics, with ratios between them > N, where N is the maximum number of hops you will ever see. If we have, for example, high, medium and low metrics, any path made up entirely of high metrics will beat any path with even one hop with any other metric. And so on.

But why limit yourself like that? Because if you want the efficiency gain from MPRs, because they guarantee shortest paths, if all metrics are random values then your MPR algorithm will end up selecting too many neighbours - even possibly all neighbours with a two hop neighbour - as MPRs.

This might mean a single metric value per interface type in some cases.

> On 24 Mar 2022, at 12:07, Philippe Jacquet <[email-masked]> wrote:
>