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

From: "Teco Boot" <[email-masked]>
Date: Thu, 23 Apr 2009 12:09:35 +0200

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.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Thu, 23 Apr 2009 11:18:56 +0100

The missed 1-hop TC has an inherent contradiction, that
combination of characteristics should not occur. Taking
special action to relay such a message is not appropriate.

I'm afraid I'm not going to work through your second case.
I'm not interested in ad hoc "this might work" modifications
of the MPR flooding until backed by a mathematical proof that
there are no problems. We've seen enough examples of ideas
that look plausible but actually fail.

-- 
Christopher Dearlove
Technology Leader, Communications Group
Networks, Security and Information Systems Department
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 Teco Boot
Sent: 23 April 2009 11:10
To: [email-masked]
Subject: [manet] OLSRv2 - suggestions for enhancing message forwarding

                    *** 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.

Missed 1-hop TC:
================

Alternative approach: 

                 **R7
                 *
        ________R4
       /        /
 R1-----------R2-------\
**     \      |*        |
*       \     | *R10    |
*        \    |         |
*         -----R3-------R5**R8
R9              *
                **R6

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.

Thoughts?

Teco.

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

********************************************************************
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: "Teco Boot" <[email-masked]>
Date: Wed, 29 Apr 2009 09:10:58 +0200

On the second case, think of:
 - There is no symmetric neighbor on this interface
 - There is only one symmetric neighbor on this interface,
   and the to be relayed message was received on this interface
 - All neighbors on this interface report full connectivity
   to all other neighbors on this interface, and the to be 
   relayed message was received on this interface
The check is: does relay the message on this interface results to
reception on a node, that did not received the message before? 
If the answer is no, the message SHOULD NOT be relayed on this
interface. Looks like a no-brainer to me.

There is no need for mathematical proof for the enhanced MPR 
selection mechanism, as it complies with the MPR selection
criteria. It is just more selective.
> For each OLSRv2 interface a router MUST select a set of MPRs.  This
> set MUST have the properties that:
>
> o  All of the selected MPRs are willing symmetric 1-hop neighbors,
>    AND;
>
> o  If the selecting router sends a message on that OLSRv2 interface,
>    and that message is successfully forwarded by all of the selected
>    MPRs for that interface, then all symmetric strict 2-hop neighbors
>    of the selecting router through that OLSRv2 interface will receive
>    that message on a symmetric link.

Maybe there is an additional requirement for MPR selection that I am
not aware of. In that case, it shall be added in the draft.

If not, I prefer modifying the OLSRv2 mechanism for supporting the 4 mode
MPR selection status. Nodes are free to use it or not; i.e. use only the
no_MPR and
MPR_all_interfaces.
Populating the Advertised Neighbor Set is not affected, all MPR selectors
must be included; i.e. MPR_this_interface, MPR_other_interfaces and
MPR_all_interfaces.

Teco.

|
|I'm afraid I'm not going to work through your second case.
|I'm not interested in ad hoc "this might work" modifications
|of the MPR flooding until backed by a mathematical proof that
|there are no problems. We've seen enough examples of ideas
|that look plausible but actually fail.
|
|--
|Christopher Dearlove
|Technology Leader, Communications Group
|Networks, Security and Information Systems Department
|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 Teco Boot
|Sent: 23 April 2009 11:10
|To: [email-masked]
|Subject: [manet] OLSRv2 - suggestions for enhancing message forwarding
|
|
|                    *** 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.
|
|
|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
[email-masked]
|https://www.ietf.org/mailman/listinfo/manet
|
|
|********************************************************************
|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: Richard Ogier <[email-masked]>
Date: Wed, 29 Apr 2009 22:16:06 -0700

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 30 Apr 2009 07:46:30 -0700

Although the scheme I suggested in my last post would be a major
change to OLSRv2, I would like to add that Teco's suggestion (below)
is a minor change that can easily be included in OLSRv2.
As Teco showed, this change can greatly improve flooding
efficiency, and the use of the new MPR types (this_interface
and other_interfaces) is optional, so routers can ignore it.
I assume this can be incorporated in a backward compatible manner.

Richard