Re: [manet] OLSRv2 - suggestions for enhancing message forwarding

[Richard Ogier <[e-mail]>]

Teco,

I am glad you are looking at more efficient strategies for
MPR flooding.  It is probably too late for OLSRv2, but as
Charlie said, it is useful to discuss this for a future
version of OLSR (or another protocol).  Your example with 10
nodes shows that MPR flooding can be very inefficient.
In particular, if every MANET node has both a MANET interface
and another interface with a stub link, then every node
must select all MANET neighbors as MPRs!

Simply using per-node MPRs does not help in this case, which
is why you are proposing different MPR types for:
(1) forwarding on the same interface,
(2) forwarding on all other interfaces, and
(3) forwarding on all interfaces.
I agree this is more efficient than the current specification.
But if there are more than 2 interfaces, and thus more than
1 "other" interfaces, I think it can still be inefficient.
I think that maximum efficiency would require somehow indicating
exactly which of the n interfaces the packet should be forwarded
on.  But of course this is more complex.

Instead of having different MPR types, I would suggest a simpler
scheme in which MPRs are still selected per interface, but all
MPRs are of type "this_interface", so that they only forward on
the same interface.  The decision to forward on other interfaces
would be made by the router doing the forwarding, based on 2-hop
neighbor information.  In this sense, one can say that MPRs of
type "other_interface" are self-selecting MPRs.  It is easy to come
up with an algorithm for making this decision in an efficient way.

Another advantage of this strategy is that Hello messages only need
to list neighbors on the same interface that the Hello is sent on
(like OSPF), in contrast to NDHP, which requires that each Hello list
all neighbors on all interfaces!

Teco's example is why I took a similar approach with OSPF-MDR
(draft-ietf-ospf-manet-mdr).  In OSPF-MDR, CDS nodes (MDRs) are
selected per interface and are used to forward only on the same
interface.

Richard


Teco Boot wrote:

>Here two suggestions for enhancing message forwarding:
>
>
>Missed 1-hop TC:
>================
>
>If the following condition for a received message is true:
>
>   msg-orig-addr is a MPR selector,
>   source address of message is not MPR selector,
>   message is not seen before,
>
>the message is discarded. However, this is a message that 
>should have been received, or is to be received soon. Repair 
>of loss of messages sent from a first hop neighbors could be 
>beneficial for loop prevention.
>
>Suggested change: relay such a message.
>
>
>
>Eliminate useless relaying:
>===========================
>
>If the relaying node has the same set of symmetric neighbors 
>or a subset symmetric neighbors on this link than the MPR 
>selector, relaying messages received from this MPR selector 
>on this link is not useful. 
>
>Suggested change: Do not relay messages from such a MPR 
>selector on the link which the message was received on.
>
>Alternative approach: 
> o  Introduce manually configured interface type: 
>        full-connected [ no | yes ]
> o  Enhance MPR selection and signaling algorithm, 
>    with MPR types:
>         [ no_MPR | MPR_this_interface | 
>           MPR_other_interfaces | MPR_all_interfaces ]
>    MPR selection shall guarantee that all 2-hop neighbors 
>    receive the message at least once. 
>
>Here a scenario where the enhanced MPR selection would 
>benefit a lot:
>
>
>                 **R7
>                 *
>        ________R4
>       /        /
> R1-----------R2-------\
>**     \      |*        |
>*       \     | *R10    |
>*        \    |         |
>*         -----R3-------R5**R8
>R9              *
>                **R6
>
>Lines: low bandwidth - long reach, e.g. UHF low  
>Asterisks: high bandwidth - short range, e.g. UHF high
>
>On |-segment, R1 selects R2 as MPR_all_interfaces and (R4, R3) as 
>MPR_other_interfaces. R2 selects (R1, R3, R4, R5) as MPR_other_interfaces.
>
>Scenario: R9 sends TC message.
>R1 relays TC.
>R4, R2 and R3 receive this TC in parallel, all relay
>    on *-interface. Only R2 relays on |-interface.
>R5 receives TC from R2 and relays on *-interface only.
>
>The TC is sent 2 times (instead of 5) on the |-segment.
>
>
>Thoughts?
>
>Teco.
>
>
>
>_______________________________________________
>manet mailing list
>[e-mail]
>https://www.ietf.org/mailman/listinfo/manet
>
>  
>