Subject: [manet] OLSRv2 and forwarding based on MPR

From: "Teco Boot" <[email-masked]>
Date: Mon, 6 Apr 2009 23:06:57 +0200

Other questions, now on forwarding.
-08 - page 26 describes the algorithm.

After:
> 2.  Otherwise:
>      1.  Create a Received Tuple in the Received Set for the
>          receiving interface with:

Comes:
>      2.  If a Forwarded Tuple exists with:

This is strange. If the tuple was not received before, how can the Forwarded
Tuple exist? (assume no buggy olsr code:-)

And the message is not forwarded if the upstream node was not the MPR
selector, correct?
For forwarding in the same segment (same interface), this would be correct.
But I think that forwarding on other interfaces must take place under many
more conditions. I would say, if a message is processed, other nodes in the
neighborhood should also receive this message. Within the segment, it's OK
that only MPRs take care of forwarding. But for other segments, I do not see
a relation with MPRs, especially when MPRs are per interface.

                 _R4
                /
  R1-----------R2-------\
        \       |        |
         -------R3-------R5
                *
                **R6

Line:     segment 1
Asterisk: segment 2
R2 is MPR for R1 (link to R4 and R5, R3 has not).
R3 does not forward TC from R1, as R1 is not MPR selector.
Ditto for TC from R2 and R5.
But who forwards the TC to R6?

I guess I overlook something here.

Teco.

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 07 Apr 2009 09:14:39 +0200

Dear Teco,

In your example R6 is indeed in N2(I) of R1, since it can be reached via 
R3. Thus R3 is MPR of R1. R3 must be on I from R1 to be on N(I), but R6 
does not need to be on I in order to be on N2(I). N2(I) contains all 
nodes that can be reached from those that are in N(I), indifferently of 
the interface.

Best regards,
Philippe

Teco Boot a écrit :
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
> 
>

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 7 Apr 2009 09:56:00 +0100

> Tuple exist? (assume no buggy olsr code:-)

Because there's a Received Set per interface. It even says so in what
you've
quoted. This case can happens if you haven't previously received on this
interface, but have on another and the forwarded. No buggy OLSRv2 code
needed.

********************************************************************
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, 7 Apr 2009 15:31:37 +0100

(This is not properly threaded, as it seems this email system
doesn't like Richard as well as Charlie. I was actually
checking the archive for any postings by Charlie.)

Richard Ogier
> The race condition that Philippe described can also occur with
> a single interface under certain conditions. For example,
> suppose a MAC protocol is used that decides to "multicast" 
> a packet by unicasting it to each neighbor, one at a time.

This is also a well-known result. But I do not view it as a
real issue here, as I believe the cases of interest will use
real wireless broadcast. The general multiple unicasting
solution does not scale well (though there are approaches
- I've implemented at least one) that can win back some of
your loss.

> (In some cases, this might be more efficient if there are only 2 or 3
> neighbors.)

And you know who they are. As one of the points of NHDP is
to find your neighbours, which rules out this approach.

> So it might be worthwhile to modify the MPR selection or the
> MPR flooding mechanism in order to allow the above situation.

In this case, I don't think so. In others, this can be so.

---

From: Richard Ogier <[email-masked]>
Date: Tue, 07 Apr 2009 22:47:30 -0700

I guess the main limitation of the race condition is that MPRs must
be selected per interface, as discussed.  Not only would selecting
MPRs per node (for all interfaces) result in more efficient flooding
(see the example below), but it would also allow Flooding MPRs to be
the same as Routing MPRs in draft-dearlove-olsrv2-metrics-03, thus
greatly simplifying the protocol.  This would also result in flooding
of topology updates along the routing paths in the reverse direction
(reverse path forwarding), which provides the benefit that updates
related to the path to destination D are received from the next hop
to D (so you know the next hop has the information it needs).

I know there are methods to avoid the race condition.  Philippe
mentioned one, and I know of others.
My point is that (in my opinion) the benefits of being able to
select MPRs per node instead of per interface are great enough
to justify using such an approach.  At least the WG should be
able to consider and experiment with such an alternative.

You can say that OLSRv2 is stable, but that is without metrics.
Your approach to metrics, using Routing MPRs in addition to
Flooding MPRs, appears to be a patch that avoids modifying
the existing flooding mechanism in OLSRv2, whereas if one started
from scratch, the above simplified approach might be better
(in which Flooding MPRs are the same as Routing MPRs).

As shown in the following (obvious) example, having to select MPRs
per interface can be very inefficient in a network that has several
interfaces.
In the example, each link is a separate interface; thus node A must
select all neighbors as MPRs, even though only one MPR is necessary.

  A
 /|\
B C D
 \|/
  E

Richard

---

From: "Teco Boot" <[email-masked]>
Date: Wed, 8 Apr 2009 09:18:01 +0200

Hi Phillipe,

Got it. I had the "per interface" in mind. 
Now I know MPR selection is for EACH interface and selects MPRs for ALL
2-hop neighbors reachable via that interface. 

However, I think this could be highly redundant. Assume the following
topology:

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

Lines: low bandwidth - long reach, e.g. UHF low  
Asterisk: high bandwidth - short range, e.g. UHF high

Now R1 selects (R4, R2, R3) as MPR on |-segment.
R2 and R3 select R5.
Assume CPU is faster as transmission delay.

Scenario: R9 sends TC message.
R1 relays TC.
R4, R2 and R3 receives this TC in parallel, all are MPR.
All schedule TC transmission, it is queued for jitter and or carrier usage.
Transmission is one by one (luckily no collisions).
R5 receives TC from R2 or R3, whatever is received first. R5 is MPR for both
R2 and R3.
R5 schedules TC transmission.

Is it correct that this TC is sent on the |-segment ***5 times***?

Forwarding is straightforward (olsrv2-08 page 27):
>> 3.  For each OLSRv2 interface of the router
           *********************
So I think the answer is YES. If so, this is really bad!!

Again, maybe I overlook something.

Teco.

|-----Oorspronkelijk bericht-----
|Van: Philippe Jacquet [mailto:[email-masked]]
|Verzonden: dinsdag 7 april 2009 9:15
|Aan: Teco Boot
|CC: 'manet'
|Onderwerp: Re: [manet] OLSRv2 and forwarding based on MPR
|
|Dear Teco,
|
|In your example R6 is indeed in N2(I) of R1, since it can be reached via
|R3. Thus R3 is MPR of R1. R3 must be on I from R1 to be on N(I), but R6
|does not need to be on I in order to be on N2(I). N2(I) contains all
|nodes that can be reached from those that are in N(I), indifferently of
|the interface.
|
|Best regards,
|Philippe
|
|Teco Boot a écrit :
|> Other questions, now on forwarding.
|> -08 - page 26 describes the algorithm.
|>
|> After:
|>> 2.  Otherwise:
|>>      1.  Create a Received Tuple in the Received Set for the
|>>          receiving interface with:
|>
|> Comes:
|>>      2.  If a Forwarded Tuple exists with:
|>
|> This is strange. If the tuple was not received before, how can the
|Forwarded
|> Tuple exist? (assume no buggy olsr code:-)
|>
|>
|> And the message is not forwarded if the upstream node was not the MPR
|> selector, correct?
|> For forwarding in the same segment (same interface), this would be
|correct.
|> But I think that forwarding on other interfaces must take place under
|many
|> more conditions. I would say, if a message is processed, other nodes
|in the
|> neighborhood should also receive this message. Within the segment,
|it's OK
|> that only MPRs take care of forwarding. But for other segments, I do
|not see
|> a relation with MPRs, especially when MPRs are per interface.
|>
|>                  _R4
|>                 /
|>   R1-----------R2-------\
|>         \       |        |
|>          -------R3-------R5
|>                 *
|>                 **R6
|>
|> Line:     segment 1
|> Asterisk: segment 2
|> R2 is MPR for R1 (link to R4 and R5, R3 has not).
|> R3 does not forward TC from R1, as R1 is not MPR selector.
|> Ditto for TC from R2 and R5.
|> But who forwards the TC to R6?
|>
|> I guess I overlook something here.
|>
|>
|> Teco.
|>
|>
|>
|>
|>
|>
|>
|>
|>
|> _______________________________________________
|> manet mailing list
|> [email-masked]
|> https://www.ietf.org/mailman/listinfo/manet
|>
|>

---

From: Richard Ogier <[email-masked]>
Date: Tue, 14 Apr 2009 21:15:37 -0700

>to find your neighbours, which rules out this approach.

But the underlying link layer can perform its own neighbor discovery and 
thus know about (and unicast packets to) neighbors that OLSRv2 has not 
yet discovered, so my point is still valid in that case.

Also, as Teco has shown, the underlying link layer can be a multihop 
network, in which a packet sent at the same time by two routers (B and 
C) can arrive at two neighbors (D and E) in different orders, thus 
causing flooding failure due to the race condition.

I was surprised that the draft states "OLSRv2 makes no assumptions about 
the underlying link layer".  I think it is clear that SOME assumptions 
are needed, unless the rule for forwarding TC messages is modified.

But frankly, I prefer that the race condition be avoided using the known 
solution that Philippe mentioned, so that the above cases can be 
supported, and so that multiple interfaces can be supported without 
having to select a full set of MPRs for each interface, thus improving 
efficiency.

The known solution is to wait a short interval, e.g., up to 100 ms, and 
then forward a given message only if the neighbor with the largest RID 
from which the message has been received (so far) is an MPR selector.  
Some MANET implementations delay the forwarding of topology updates 
anyway, to allow multiple updates to be coalesced in a single packet.

As Philippe mentioned, this solution can cause some redundant 
transmissions, but at least it works without making any assumptions 
about the link layer!  Also, efficiency is potentially improved for 
multiple interfaces as mentioned above, by allowing MPRs to be selected 
per node.

Richard

---

From: "Teco Boot" <[email-masked]>
Date: Wed, 15 Apr 2009 09:41:25 +0200

Before we step into solution space, I want to see full agreement on the
problem. If so, we shall describe limitations of MPR flooding in the OLSRv2
document. 

Text proposal:
MPR flooding in OLSRv2 makes the assumption about the underlying link layer
that all receivers of a transmitted packet has the same time of arrival.
This may not be true for all types of link layers, e.g. where
pseudo-broadcast is used or in multi-hop sub-IP networks.

The alternative would be fixing the problem.

Side remark here, I think agreement on the problem means opening the
discussion on MPR selection per interface. It would be a MAY (or SHOULD),
and not a MUST.

<for later discussions>

On solution space:

The first one I think of is using jitter (MUST instead of MAY). Jitter
timing should be (far) larger than the differences in time of arrival. The
problem with this is delayed flooding of important information (e.g. loop
avoidance messages). And slowing down convergence in general.

Forwarding based on RouterID as Richard suggests may have bad side effects.
I think it could initiate flooding back to the originator.

There could be solutions based on clock synchronization. Not sure on going
that way.

Before making decisions here, we have to carefully quantify effects of the
remedies.

</for later discussions>

Teco.

|-----Oorspronkelijk bericht-----
|Van: [email-masked] [mailto:[email-masked]] Namens
|Richard Ogier
|Verzonden: woensdag 15 april 2009 6:16
|Aan: Dearlove, Christopher (UK)
|CC: manet
|Onderwerp: Re: [manet] OLSRv2 and forwarding based on MPR
|
|Dearlove, Christopher (UK) wrote:
|
|>(This is not properly threaded, as it seems this email system
|>doesn't like Richard as well as Charlie. I was actually
|>checking the archive for any postings by Charlie.)
|>
|>Richard Ogier
|>
|>
|>>The race condition that Philippe described can also occur with
|>>a single interface under certain conditions. For example,
|>>suppose a MAC protocol is used that decides to "multicast"
|>>a packet by unicasting it to each neighbor, one at a time.
|>>
|>>
|>
|>This is also a well-known result. But I do not view it as a
|>real issue here, as I believe the cases of interest will use
|>real wireless broadcast. The general multiple unicasting
|>solution does not scale well (though there are approaches
|>- I've implemented at least one) that can win back some of
|>your loss.
|>
|>
|>
|>>(In some cases, this might be more efficient if there are only 2 or 3
|>>neighbors.)
|>>
|>>
|>
|>And you know who they are. As one of the points of NHDP is
|>to find your neighbours, which rules out this approach.
|>
|>
|>
|
|But the underlying link layer can perform its own neighbor discovery and
|thus know about (and unicast packets to) neighbors that OLSRv2 has not
|yet discovered, so my point is still valid in that case.
|
|Also, as Teco has shown, the underlying link layer can be a multihop
|network, in which a packet sent at the same time by two routers (B and
|C) can arrive at two neighbors (D and E) in different orders, thus
|causing flooding failure due to the race condition.
|
|I was surprised that the draft states "OLSRv2 makes no assumptions about
|the underlying link layer".  I think it is clear that SOME assumptions
|are needed, unless the rule for forwarding TC messages is modified.
|
|But frankly, I prefer that the race condition be avoided using the known
|solution that Philippe mentioned, so that the above cases can be
|supported, and so that multiple interfaces can be supported without
|having to select a full set of MPRs for each interface, thus improving
|efficiency.
|
|The known solution is to wait a short interval, e.g., up to 100 ms, and
|then forward a given message only if the neighbor with the largest RID
|from which the message has been received (so far) is an MPR selector.
|Some MANET implementations delay the forwarding of topology updates
|anyway, to allow multiple updates to be coalesced in a single packet.
|
|As Philippe mentioned, this solution can cause some redundant
|transmissions, but at least it works without making any assumptions
|about the link layer!  Also, efficiency is potentially improved for
|multiple interfaces as mentioned above, by allowing MPRs to be selected
|per node.
|
|Richard
|
|
|
|_______________________________________________
|manet mailing list
[email-masked]
|https://www.ietf.org/mailman/listinfo/manet

---

From: Thomas Heide Clausen <[email-masked]>
Date: Wed, 15 Apr 2009 09:47:12 +0200

Teco,

> pseudo-broadcast is used or in multi-hop sub-IP networks.

But, that's incorrect. The present proposed algorithm in the I-D does  
not require this, but works correctly.

> The alternative would be fixing the problem.

I believe that the problem was identified years back, fixed then --  
and that this fix still applies?

> discussion on MPR selection per interface. It would be a MAY (or  

I disagree.

> avoidance messages). And slowing down convergence in general.

I disagree. L2s differ, the choice of jitter should too. This is  
documented in 5148.

Thomas

---

From: "Teco Boot" <[email-masked]>
Date: Wed, 15 Apr 2009 10:32:57 +0200

Hi Thomas,

Can you comment on the separate thread, describing the problem?
http://www.ietf.org/mail-archive/web/manet/current/msg11061.html

I changed the subject to "MPR selection per interface - race conditions"

FYI, B and C has other neighbors enforcing MPR for A (same as multi
interface scenario).

Again, I might overlook the fix. I am afraid there isn't.
And I am not a "believer" :-)

Teco.

|-----Oorspronkelijk bericht-----
|Van: Thomas Heide Clausen [mailto:[email-masked]]
|Verzonden: woensdag 15 april 2009 9:47
|Aan: Teco Boot
|CC: 'Richard Ogier'; 'Dearlove, Christopher (UK)'; 'manet'
|Onderwerp: [SPAM] Re: [manet] OLSRv2 and forwarding based on MPR
|Urgentie: Laag
|
|Teco,
|
|On Apr 15, 2009, at 09:41 AM, Teco Boot wrote:
|
|> Before we step into solution space, I want to see full agreement on
|> the
|> problem. If so, we shall describe limitations of MPR flooding in
|> the OLSRv2
|> document.
|>
|> Text proposal:
|> MPR flooding in OLSRv2 makes the assumption about the underlying
|> link layer
|> that all receivers of a transmitted packet has the same time of
|> arrival.
|> This may not be true for all types of link layers, e.g. where
|> pseudo-broadcast is used or in multi-hop sub-IP networks.
|
|But, that's incorrect. The present proposed algorithm in the I-D does
|not require this, but works correctly.
|
|> The alternative would be fixing the problem.
|
|I believe that the problem was identified years back, fixed then --
|and that this fix still applies?
|
|> Side remark here, I think agreement on the problem means opening the
|> discussion on MPR selection per interface. It would be a MAY (or
|> SHOULD),
|> and not a MUST.
|
|I disagree.
|
|> <for later discussions>
|>
|> On solution space:
|>
|> The first one I think of is using jitter (MUST instead of MAY). Jitter
|> timing should be (far) larger than the differences in time of
|> arrival. The
|> problem with this is delayed flooding of important information
|> (e.g. loop
|> avoidance messages). And slowing down convergence in general.
|
|I disagree. L2s differ, the choice of jitter should too. This is
|documented in 5148.
|
|Thomas
|
|>
|> Forwarding based on RouterID as Richard suggests may have bad side
|> effects.
|> I think it could initiate flooding back to the originator.
|>
|> There could be solutions based on clock synchronization. Not sure
|> on going
|> that way.
|>
|> Before making decisions here, we have to carefully quantify effects
|> of the
|> remedies.
|>
|> </for later discussions>
|>
|>
|> Teco.
|>
|>
|>
|>
|> |-----Oorspronkelijk bericht-----
|> |Van: [email-masked] [mailto:[email-masked]] Namens
|> |Richard Ogier
|> |Verzonden: woensdag 15 april 2009 6:16
|> |Aan: Dearlove, Christopher (UK)
|> |CC: manet
|> |Onderwerp: Re: [manet] OLSRv2 and forwarding based on MPR
|> |
|> |Dearlove, Christopher (UK) wrote:
|> |
|> |>(This is not properly threaded, as it seems this email system
|> |>doesn't like Richard as well as Charlie. I was actually
|> |>checking the archive for any postings by Charlie.)
|> |>
|> |>Richard Ogier
|> |>
|> |>
|> |>>The race condition that Philippe described can also occur with
|> |>>a single interface under certain conditions. For example,
|> |>>suppose a MAC protocol is used that decides to "multicast"
|> |>>a packet by unicasting it to each neighbor, one at a time.
|> |>>
|> |>>
|> |>
|> |>This is also a well-known result. But I do not view it as a
|> |>real issue here, as I believe the cases of interest will use
|> |>real wireless broadcast. The general multiple unicasting
|> |>solution does not scale well (though there are approaches
|> |>- I've implemented at least one) that can win back some of
|> |>your loss.
|> |>
|> |>
|> |>
|> |>>(In some cases, this might be more efficient if there are only 2
|> or 3
|> |>>neighbors.)
|> |>>
|> |>>
|> |>
|> |>And you know who they are. As one of the points of NHDP is
|> |>to find your neighbours, which rules out this approach.
|> |>
|> |>
|> |>
|> |
|> |But the underlying link layer can perform its own neighbor
|> discovery and
|> |thus know about (and unicast packets to) neighbors that OLSRv2 has
|> not
|> |yet discovered, so my point is still valid in that case.
|> |
|> |Also, as Teco has shown, the underlying link layer can be a multihop
|> |network, in which a packet sent at the same time by two routers (B
|> and
|> |C) can arrive at two neighbors (D and E) in different orders, thus
|> |causing flooding failure due to the race condition.
|> |
|> |I was surprised that the draft states "OLSRv2 makes no assumptions
|> about
|> |the underlying link layer".  I think it is clear that SOME
|> assumptions
|> |are needed, unless the rule for forwarding TC messages is modified.
|> |
|> |But frankly, I prefer that the race condition be avoided using the
|> known
|> |solution that Philippe mentioned, so that the above cases can be
|> |supported, and so that multiple interfaces can be supported without
|> |having to select a full set of MPRs for each interface, thus
|> improving
|> |efficiency.
|> |
|> |The known solution is to wait a short interval, e.g., up to 100
|> ms, and
|> |then forward a given message only if the neighbor with the largest
|> RID
|> |from which the message has been received (so far) is an MPR selector.
|> |Some MANET implementations delay the forwarding of topology updates
|> |anyway, to allow multiple updates to be coalesced in a single packet.
|> |
|> |As Philippe mentioned, this solution can cause some redundant
|> |transmissions, but at least it works without making any assumptions
|> |about the link layer!  Also, efficiency is potentially improved for
|> |multiple interfaces as mentioned above, by allowing MPRs to be
|> selected
|> |per node.
|> |
|> |Richard
|> |
|> |
|> |
|> |_______________________________________________
|> |manet mailing list
|> [email-masked]
|> |https://www.ietf.org/mailman/listinfo/manet
|>
|> _______________________________________________
|> manet mailing list
|> [email-masked]
|> https://www.ietf.org/mailman/listinfo/manet

---

From: "Stan Ratliff (sratliff)" <[email-masked]>
Date: Wed, 15 Apr 2009 10:13:01 -0400

> 
> But frankly, I prefer that the race condition be avoided 
> using the known solution that Philippe mentioned, so that the 
> above cases can be supported, and so that multiple interfaces 
> can be supported without having to select a full set of MPRs 
> for each interface, thus improving efficiency.
> 

I agree with Richard - OLSR should be capable of supporting multiple
interfaces with a single set of MPR's. I know this discussion has come
up *extremely* late in the process, but it's something the WG should
pursue. As to the mechanics of *how* to pursue it (e.g. should the
current draft be held up, or should this take the form of a subsequent
draft), I have no opinion. 

Regards,
Stan

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] 
> On Behalf Of Richard Ogier
> Sent: Wednesday, April 15, 2009 12:16 AM
> To: Dearlove, Christopher (UK)
> Cc: manet
> Subject: Re: [manet] OLSRv2 and forwarding based on MPR
> 
> >(This is not properly threaded, as it seems this email 
> system doesn't 
> >like Richard as well as Charlie. I was actually checking the archive 
> >for any postings by Charlie.)
> >
> >Richard Ogier
> >  
> >
> >>The race condition that Philippe described can also occur with a 
> >>single interface under certain conditions. For example, 
> suppose a MAC 
> >>protocol is used that decides to "multicast"
> real issue 
> >here, as I believe the cases of interest will use real wireless 
> >broadcast. The general multiple unicasting solution does not 
> scale well 
> >(though there are approaches
> >- I've implemented at least one) that can win back some of your loss.
> >
> >  
> >
> to find your 
> >neighbours, which rules out this approach.
> >
> >  
> >
> 
> But the underlying link layer can perform its own neighbor 
> discovery and thus know about (and unicast packets to) 
> neighbors that OLSRv2 has not yet discovered, so my point is 
> still valid in that case.
> 
> Also, as Teco has shown, the underlying link layer can be a 
> multihop network, in which a packet sent at the same time by 
> two routers (B and
> C) can arrive at two neighbors (D and E) in different orders, 
> thus causing flooding failure due to the race condition.
> 
> I was surprised that the draft states "OLSRv2 makes no 
> assumptions about the underlying link layer".  I think it is 
> clear that SOME assumptions are needed, unless the rule for 
> forwarding TC messages is modified.
> 
> But frankly, I prefer that the race condition be avoided 
> using the known solution that Philippe mentioned, so that the 
> above cases can be supported, and so that multiple interfaces 
> can be supported without having to select a full set of MPRs 
> for each interface, thus improving efficiency.
> 
> The known solution is to wait a short interval, e.g., up to 
> 100 ms, and then forward a given message only if the neighbor 
> with the largest RID from which the message has been received 
> (so far) is an MPR selector.  
> Some MANET implementations delay the forwarding of topology 
> updates anyway, to allow multiple updates to be coalesced in 
> a single packet.
> 
> transmissions, but at least it works without making any 
> assumptions about the link layer!  Also, efficiency is 
> potentially improved for multiple interfaces as mentioned 
> above, by allowing MPRs to be selected per node.
> 
> Richard
> 
> 
>

---

From: Richard Ogier <[email-masked]>
Date: Wed, 15 Apr 2009 10:45:01 -0700

>I think it could initiate flooding back to the originator.

I can see how this could happen, but simulations should be performed to
see if it is really a problem.  One way to avoid this is to use the
(well-known) MPR-CDS approach, so that a router forwards a message only
if its largest-RID neighbor is an MPR selector (or the router itself has
a larger RID than all of its neighbors).  This way the forwarding rule
does not depend on the order in which packets are received from
neighbors.  The drawback is that messages are not flooded along
shortest paths, but on average they are flooded along nearly shortest
paths.  (If flooding along shortest paths is desired, a router can
in addition forward messages based on the current rule.)

Philippe wrote:

>|If propagation jitters are too large then protocols must be designed as
>|in DTNRG that addresses issues about traffic buffering and outdated
>|topology informations. Maybe more on http://www.dtnrg.org/wiki

I agree with Teco that the cases we are talking about are not DTN cases.
The above DTNRG site includes the following sentence, which is not what
we are talking about:

> Members of DTNRG are concerned with how to address the architectural 
> and protocol design principles arising from the need to provide 
> interoperable communications with and among extreme and 
> performance-challenged environments where continuous end-to-end 
> connectivity cannot be assumed.

Richard

---

From: jacquet <[email-masked]>
Date: Thu, 16 Apr 2009 14:08:00 +0200

Richard,

Sorry my last posting was too much elliptic. Regarding DTNRG charter I 
was merely looking to the sentence:

"Said another way, we are concerned with interconnecting highly 
heterogeneous networks together even if end-to-end connectivity may 
never be available."

In the case presented by Teco, I thought that the "switch" interface was 
providing very heterogeneous performances. But it is not the case, and 
the jitter should solve the race problem as mentioned by Thomas.

Going back to per node MPR selection versus per interface selection 
(this was not the point of Teco posting, based on only one interface), 
my main point was that merging all interfaces for MPR selection may 
degenerate in DTN situation wrt flooding when interfaces present very 
heterogeneous performance.

In this case I would favor per interface strategy. Let assume that one 
interface has the longest range. As a natural consequence most MPR will 
be chosen on this interface. And if this interface is very poor and very 
slow, then the flooding will be very slow and unreliable. MPR-CDS would 
not help here.

If we would go to a per node strategy then we should probably introduce 
some limitations on  performance discrepancies among interfaces, and 
consequently limit the use of MANET.

Best regards,
Philippe

---

From: Richard Ogier <[email-masked]>
Date: Thu, 16 Apr 2009 22:58:21 -0700

jacquet wrote:

> In the case presented by Teco, I thought that the "switch" interface 
> was providing very heterogeneous performances. But it is not the case, 
> and the jitter should solve the race problem as mentioned by Thomas.
>
> interface has the longest range. As a natural consequence most MPR 
> will be chosen on this interface. And if this interface is very poor 
> and very slow, then the flooding will be very slow and unreliable. 
> MPR-CDS would not help here.

Even in the above case, it is still not necessary to define a complete 
set of MPRs per interface, as I will explain.  All you need is to define 
an ordering on MANET segments (as Teco defined).  The ordering can be 
based on both speed and network addresses, so that faster segments are 
always preferred, and network addresses are used to break ties. (Metrics 
can also be used to select MPRs, but what I am proposing should work 
even if metrics are not used.)

The modified MPR property (from Section 14) that I proposed on 4/9 can 
be rewritten using the above ordering on MANET segments/interfaces. 
Informally, the property is as follows:  The MPRs for a given interface 
must cover each 2-hop neighbor through that interface that is not also a 
2-hop neighbor through a "better" interface.

This works on the last example you described (on 4/9), since both B and 
C will select E as MPR (assuming E is on the better interface).

I will show that this also works on the case you described above, which 
can be represented by the following example, in which *** indicates the 
fast/better segment.

A --- B --- C
 *   / \   *
  * /   \ *
   D *** E

In the naive per-node solution, A would select only B as MPR, so that 
flooding is through the slow segment.
But with the proposed strategy, since *** is the better segment and E is 
a 2-hop neighbor of A through that segment, A must select D as MPR.

In this case, A also selects B as MPR to cover C.  But if C is removed 
from the network, then A would not select B (since E is covered by D 
through the better interface), in contrast to the per-interface strategy.

Richard

>
> If we would go to a per node strategy then we should probably 
> introduce some limitations on  performance discrepancies among 
> interfaces, and consequently limit the use of MANET.
>
> Best regards,
> Philippe
>
> Richard Ogier a écrit :
>
>> Teco Boot wrote:
>>

---

From: "Teco Boot" <[email-masked]>
Date: Fri, 17 Apr 2009 09:45:17 +0200

Philippe, Thomas, all,

Philippe wrote:
|In the case presented by Teco, I thought that the "switch" interface was
|providing very heterogeneous performances. But it is not the case, and
|the jitter should solve the race problem as mentioned by Thomas.

The comments from Thomas were:
....
> But, that's incorrect. The present proposed algorithm in the 
> I-D does not require this, but works correctly.
....
> I disagree. L2s differ, the choice of jitter should too. This is
....
I am lost. First, text update is not needed (it works ALWAYS), then jitter
solves the problem (there is NO problem?).

My suggestion is rewording in the OLSRv2 text:
 - There IS an assumption on the underlying link layer
 - Explain what the assumption is (separate section)
 - Make jitter a SHOULD, reference to the assumption
 - Make "per interface MPR selection" a SHOULD, reference
   to the assumption

Now we have two remedies for the race condition. The update on text would
not slow down progress that much. Acceptable?

Teco.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 20 Apr 2009 10:16:17 +0100

Stan
> interfaces with a single set of MPR's.

It is. You select MPRs per interface, but then you use a single
MPR set that combines them all into a single set for use. Only
the selecting node is aware of the per interface stuff, the
communication to other nodes simply reports MPR status. That's
true in 3626 and in OLSRv2.

(Of course you should intelligently select the MPRs so that you
don't pick an over-large set. There are several possible ways to
do this.)

---

From: Richard Ogier <[email-masked]>
Date: Wed, 22 Apr 2009 20:50:00 -0700

This is a reply to Teco's message, but first I will respond
to the following to clarify the goal and terminology.

Christopher Dearlove wrote:

> MPR set that combines them all into a single set for use.

I have no problem with selecting a set of MPRs for each interface.
The objection that some of us have is requiring the set of MPRs for
each interface to cover all 2-hop neighbors for that interface, even
if some of those 2-hop neighbors can be covered by MPRs for another
interface.  I refer to this requirement by saying that the draft
requires a "complete" set of MPRs per interface.
When I say "per-node MPRs", I just mean the MPR set for each
interface need not be complete, as long as the union of the
MPR sets covers all 2-hop neighbors.

One reason given for requiring a complete set of MPRs per interface
is the race condition, but it has been noted that the race condition
can be fixed by using jitter.
Another reason given by Philippe is the possibility of flooding
over the slowest interfaces.  However, that can be avoided by
giving priority to the fastest interfaces when selecting MPRs.

Currently, there are NO assumptions on the underlying link layer.
As noted, there must at least be some limit on the propagation
delay, e.g., it must be less than the flooding jitter.
But if flooding jitter is used, this also fixes the race
condition for multiple interfaces, so it is not necessary to
select a complete set of MPRs per interface.

I mostly agree with Teco's suggested changes (see his message below),
but here is a modified list of suggested changes based on the above
considerations:

 - Flooding jitter SHOULD be used.
 - Flooding jitter MUST be used if any link has the property
   that a packet transmitted simultaneously by two routers B and C
   can be received in different orders by two common neighbors
   D and E.
 - If flooding jitter is NOT used, the router MUST select a
   complete set of MPRs per interface.
 - If flooding jitter is used, then the MPR set for each
   interface need not be complete, as long as all 2-hop
   neighbors are covered by the union of the MPR sets.

I also mentioned a solution that avoids the race condition
without jitter and without selecting a complete set of MPRs
per interface (by defining an ordering on MANET segments,
and using an MPR-CDS), but the above suggestions are similar
to Teco's suggestions and do not require much change to
the draft.

Richard

---

From: "Teco Boot" <[email-masked]>
Date: Thu, 23 Apr 2009 08:39:17 +0200

Hi Richard, all,

Thanks for the clarifications. 

I still do not agree on 
>> Currently, there are NO assumptions on the underlying link layer

I came up with a scenario where MPR selection per interface and no jitter
does not work. I waited over a week for comments (what do I overlook ??). No
one did response with a clear answer (Thomas Clausen "believed" is was
solved, maybe he thought of jitter). If time permits, I'll build a
demonstrator. I would not say MPR is broken, but there are corner cases
where it fails.

I am fine with better specification where to use jitter (the MUST) and where
it is not needed (e.g. no hidden terminal problems, no multi-hop underlying
link layer, no out of order message reception)

Teco.

|-----Oorspronkelijk bericht-----
|Van: Richard Ogier [mailto:[email-masked]]
|Verzonden: donderdag 23 april 2009 5:50
|Aan: Teco Boot
|CC: 'manet'
|Onderwerp: Re: [manet] OLSRv2 and forwarding based on MPR
|
|This is a reply to Teco's message, but first I will respond
|to the following to clarify the goal and terminology.
|
|Christopher Dearlove wrote:
|
|> It is. You select MPRs per interface, but then you use a single
|> MPR set that combines them all into a single set for use.
|
|
|I have no problem with selecting a set of MPRs for each interface.
|The objection that some of us have is requiring the set of MPRs for
|each interface to cover all 2-hop neighbors for that interface, even
|if some of those 2-hop neighbors can be covered by MPRs for another
|interface.  I refer to this requirement by saying that the draft
|requires a "complete" set of MPRs per interface.
|When I say "per-node MPRs", I just mean the MPR set for each
|interface need not be complete, as long as the union of the
|MPR sets covers all 2-hop neighbors.
|
|One reason given for requiring a complete set of MPRs per interface
|is the race condition, but it has been noted that the race condition
|can be fixed by using jitter.
|Another reason given by Philippe is the possibility of flooding
|over the slowest interfaces.  However, that can be avoided by
|giving priority to the fastest interfaces when selecting MPRs.
|
|Currently, there are NO assumptions on the underlying link layer.
|As noted, there must at least be some limit on the propagation
|delay, e.g., it must be less than the flooding jitter.
|But if flooding jitter is used, this also fixes the race
|condition for multiple interfaces, so it is not necessary to
|select a complete set of MPRs per interface.
|
|I mostly agree with Teco's suggested changes (see his message below),
|but here is a modified list of suggested changes based on the above
|considerations:
|
| - Flooding jitter SHOULD be used.
| - Flooding jitter MUST be used if any link has the property
|   that a packet transmitted simultaneously by two routers B and C
|   can be received in different orders by two common neighbors
|   D and E.
| - If flooding jitter is NOT used, the router MUST select a
|   complete set of MPRs per interface.
| - If flooding jitter is used, then the MPR set for each
|   interface need not be complete, as long as all 2-hop
|   neighbors are covered by the union of the MPR sets.
|
|I also mentioned a solution that avoids the race condition
|without jitter and without selecting a complete set of MPRs
|per interface (by defining an ordering on MANET segments,
|and using an MPR-CDS), but the above suggestions are similar
|to Teco's suggestions and do not require much change to
|the draft.
|
|Richard
|
|
|Teco Boot wrote:
|
|>Philippe, Thomas, all,
|>
|>Philippe wrote:
|>|In the case presented by Teco, I thought that the "switch" interface
|was
|>|providing very heterogeneous performances. But it is not the case, and
|>|the jitter should solve the race problem as mentioned by Thomas.
|>
|>The comments from Thomas were:
|>....
|>
|>
|>>But, that's incorrect. The present proposed algorithm in the
|>>I-D does not require this, but works correctly.
|>>
|>>
|>....
|>
|>
|>>I disagree. L2s differ, the choice of jitter should too. This is
|>>documented in 5148.
|>>
|>>
|>....
|>I am lost. First, text update is not needed (it works ALWAYS), then
|jitter
|>solves the problem (there is NO problem?).
|>
|>
|>My suggestion is rewording in the OLSRv2 text:
|> - There IS an assumption on the underlying link layer
|> - Explain what the assumption is (separate section)
|> - Make jitter a SHOULD, reference to the assumption
|> - Make "per interface MPR selection" a SHOULD, reference
|>   to the assumption
|>
|>Now we have two remedies for the race condition. The update on text
|would
|>not slow down progress that much. Acceptable?
|>
|>
|>Teco.
|>
|>
|>_______________________________________________
|>manet mailing list
|>[email-masked]
|>https://www.ietf.org/mailman/listinfo/manet
|>
|>
|>

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Thu, 23 Apr 2009 09:55:37 +0100

I suggest you read the mathematical literature on the
subject. Thomas was not referring to jitter in his
answer, but to that per interface selection solves the
problem that otherwise multiple interfaces break the
timing assumption that is included in those proofs.

-- 
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 07:39
To: 'Richard Ogier'
Cc: 'manet'
Subject: Re: [manet] OLSRv2 and forwarding based on MPR

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

Hi Richard, all,

I still do not agree on 
>> Currently, there are NO assumptions on the underlying link layer

I came up with a scenario where MPR selection per interface and no
jitter
does not work. I waited over a week for comments (what do I overlook
??). No
one did response with a clear answer (Thomas Clausen "believed" is was
solved, maybe he thought of jitter). If time permits, I'll build a
demonstrator. I would not say MPR is broken, but there are corner cases
where it fails.

I am fine with better specification where to use jitter (the MUST) and
where
it is not needed (e.g. no hidden terminal problems, no multi-hop
underlying
link layer, no out of order message reception)

Teco.

|>|providing very heterogeneous performances. But it is not the case,
and

---

From: Richard Ogier <[email-masked]>
Date: Sun, 26 Apr 2009 22:29:27 -0700

>>>Currently, there are NO assumptions on the underlying link layer

I was just referring to the statement "OLSRv2 makes no assumptions about
the underlying link layer" on page 5 of the draft.  You and I are in
agreement that some assumptions on the underlying link layer ARE NEEDED.
It is ludicrous how the authors are avoiding admitting this!
In my last post on 4/22, I tried hard to clarify where jitter is
needed, for both the single-interface and multiple-interface cases.
Christopher's short response on 4/23 (to both of us) does not
address the valid points we are making.  We all understand how
selecting a complete set of MPRs per interface solves the race condition
problem when there is no jitter.  But as you point out, jitter is needed
anyway even for the single-interface case.  Similarly, jitter can solve
the problem with multiple interfaces.  (If the authors disagree with
this, then they should say so and we can discuss it.)
Therefore, WHY SHOULD WE REQUIRE A COMPLETE SET OF MPRS PER INTERFACE
IF THIS CAN BE AVOIDED USING JITTER?   By removing this requirement,
we allow a more flexible and more efficient selection of MPRs.

>demonstrator. I would not say MPR is broken, but there are corner cases

Yes, your scenario (with a single interface and multihop link layer)
clearly shows that MPR selection per interface and no jitter can fail
even for a single interface. (Christopher did not address this in his
recent message.)  I'm not sure what Thomas meant, but Philippe stated
the following on 4/16:

"In the case presented by Teco, I thought that the "switch" interface 
was providing very heterogeneous performances. But it is not the case, 
and the jitter should solve the race problem as mentioned by Thomas."

>link layer, no out of order message reception)

I agree.  At a minimum, the authors need to specify assumptions
for the link layer.  It would be great if they also specified jitter
conditions under which the complete-MPR-set-per-interface requirement
can be relaxed, but I doubt that will happen.  If we focus on the
link layer assumptions, I think we will convince either the authors
or the WG.  The key is to not give up and not let them get away
with vague arguments.  The truth shall prevail!

Richard