Subject: Re: [Ospf-manet] out-of-track routes

From: Philippe Jacquet <[email-masked]>
Date: Sun, 02 Jul 2006 12:24:08 +0200

I think there is no confusion. Routing is included in link 
synchronization. RFC 2328 was intended for link advertizement in 
broadcast interface. I don't think it specifically allows advertizing 
non synchronized links. In a route the first link can be in a broadcast 
interface and direct synchronization can be omitted, but mechanically 
the other links on the routes are those that are advertized and 
synchronized. Otherwise you will allow out of track routing as described 
by Emmanuel. I would say that RFC 2328 allows clique synchronization and 
MDR is not a natural extension of this because of out of track routing.

Indeed the current optimizations in topology reduction in MDR proposed 
by Richard allow out of track routing, while MPR-OSPF does not. As 
pointed out by Tom, Full topology advertizement lead to overhead at 
least as large as full link synchronization. Even much more, if we use 
the optimization in synchronization database that we proposed two years 
ago andwhich seems to have been recently revived by Richard.

Best regards,
Philippe.
Henderson, Thomas R wrote:

>Emmanuel, some comments inline below:
>
>  
>
>>-----Original Message-----
>>From: Emmanuel Baccelli [mailto:[email-masked]] 
>>Sent: Thursday, June 29, 2006 8:39 AM
>>To: [email-masked]
>>Subject: Re: [Ospf-manet] out-of-track routes
>>
>>Acee Lindem wrote:
>>
>>    
>>
>>>>Allowing "out-of-track" routing that does not change the predicted 
>>>>end-to-end cost is of course compatible with RFC 2328. But 
>>>>out-of-track routing that changes the predicted end-to-end 
>>>>        
>>>>
>>cost is in 
>>    
>>
>>>>contradiction with RFC 2328, and with other related documents that 
>>>>built on the fact that actual route costs can be calculated. So 
>>>>concerning the design of a solution for OSPF operation on 
>>>>        
>>>>
>>MANETs, I 
>>    
>>
>>>>think we should evaluate this issue further.
>>>>
>>>>RFC 2328 allows implicitely to route over non-adjacencies on 
>>>>broadcast network because a broadcast network implies de 
>>>>        
>>>>
>>facto mesh 
>>    
>>
>>>>connectivity between routers on that network, and thus a 
>>>>        
>>>>
>>router can 
>>    
>>
>>>>predict the cost of the route that will actually be taken 
>>>>        
>>>>
>>by packets, 
>>    
>>
>>>>even if non-adjacencies are used on broadcast networks.
>>>>
>>>>However, mesh connectivity cannot be assumed on MANETs and 
>>>>        
>>>>
>>therefore 
>>    
>>
>>>>allowing to route over non-adjacencies in this environment 
>>>>        
>>>>
>>makes it 
>>    
>>
>>>>impossible for a router to predict the cost of the route that will 
>>>>actually be taken by packets through a MANET. There may be an 
>>>>exception with the first hop of a route originated inside a MANET, 
>>>>which, even if it is not an adjacency, does not prevent 
>>>>        
>>>>
>>the router to 
>>    
>>
>>>>predict the cost of route taken further on.
>>>>        
>>>>
>>>
>>>I don't see the problem here. You don't need an adjacency 
>>>      
>>>
>>to know the 
>>    
>>
>>>cost of
>>>a p2mp link (whether it be static or derived dynamically 
>>>      
>>>
>>based on the 
>>    
>>
>>>radio
>>>characteristics).
>>>
>>>      
>>>
>>What I am talking about is the fact that in RFC 2328, even though a 
>>route may use some links that are not an adjacencies, we have the 
>>assurance that the cost of the route will anyways be the one 
>>calculated 
>>from the start. I think this is an important fact. If we choose an 
>>approach that changes this fact, we should be aware of the 
>>consequences, 
>>and there is a risk that MDR changes this fact.
>>    
>>
>
>I feel that two issues are being confounded here.  There are two
>mechanisms that we are considering for OSPF MANET.  The first allows a
>reduced set of adjacencies, which can be thought of as control-plane
>topology control.  The second allows a reduced set of advertised
>neighbors in router-LSAs, which can be thought of as data-plane topology
>control.  
>
>The cost of a path results from the links advertised in the LSAs and
>used by routers to build their forwarding tables, without regard for
>whether such advertised links are directly adjacent.  This is the point
>that Acee made in his reply.  Philippe previously raised on this list
>some concern about the overall quality (not cost) of paths that include
>non-adjacent links, under the assumption that a link that is in Full is
>more likely to be of higher quality than one that can only reach 2-Way.
>But I think a good implementation can make the effort to ensure that
>only good quality neighbors are advertised and used.  In any case, both
>the MPR-based and MDR-based drafts assume that some links used for
>forwarding packets are non-adjacent, and this concept is used in OSPF
>broadcast interface, as has been pointed out by Richard many times.
>
>Now, considering costs of paths, we should be discussing the partial
>topology LSAs and leave adjacencies out of the discussion.  The concern
>you seem to be raising is that a downstream node could choose to use a
>link that was not advertised in its router-LSA, thereby changing the
>path and cost that was computed upstream.  In your MPR-based draft, if
>link costs are uniform, this will not happen by nature of the MPR
>selection property and the use of hybrid nodes (which synchronize with
>every neighbor) at the MANET boundary.  This was previously discussed on
>the list.  Now, there are two points to consider: i) in what cases, can
>MPR- or MDR-based approaches change the path (cost) as predicted by an
>upstream node, and ii) whether this makes any difference.  
>
>For the first point, a changing path cost may occur for MPR-based
>approaches if link costs are not uniform, because in that case, you lose
>the property that MPR relationships are aligned with shortest paths
>(unless you change how MPRs are selected).  The same thing can also
>occur in MDR when link costs are non-uniform, but if the neighbors could
>advertise their costs also in Hellos (extending the existing LLS TLV in
>Hellos), then Richard's proposed min-cost LSAs could guarantee min-cost
>paths even in the case of non-uniform link costs.
>
>For the second point, whether this makes any difference, I see above
>that you say this is an important fact, but I am skeptical; can you
>provide an example where a problem might arise from downstream nodes
>improving upon the path computed upstream?   Moreover, it seems to me
>that both drafts perform similarly in this regard; that there is no
>greater "risk" with MDR.
>
>Tom
>
>_______________________________________________
>Ospf-manet mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/ospf-manet
>
>
>  
>

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 06 Jul 2006 08:50:40 -0700

Philippe,

Philippe Jacquet wrote:

> synchronization.

It looks like you didn't understand Tom's message. (It might help if
you address specific comments of Tom that you disagree with.)
There was some confusion:  Emmanuel's point was that a router
may not be able to predict the route (or its cost) that is actually
taken by packets, if packets can be routed over non-adjacent links.
Tom and Acee pointed out that this issue has to do with
(partial-topology) LSAs, not adjacencies, since non-adjacent links
can be advertised in LSAs.

Tom explained how "out-of-track" routing can occur with both MPRs
and MDRs when link costs are non-uniform, and how it can be avoided
in both cases by selecting LSAs that provide min-cost paths.
With MPRs, this means MPRs must be selected based on link costs,
which can increase the number of MPRs and thus affect flooding
overhead.  With MDRs, min-cost LSAs can be used that are decoupled
from the flooding mechanism.

As Tom pointed out, if there is out-of-track routing, downstream nodes
will only improve upon the path computed upstream, which should not be
a problem. The important thing is that loops are avoided.

In fact, with hop-by-hop (datagram) routing as in OSPF, when the
topology is changing frequently, a router can never predict the
exact cost of the path that will actually be taken.

> RFC 2328 was intended for link advertizement in broadcast interface. I 
> don't think it specifically allows advertizing non synchronized links. 
> In a route the first link can be in a broadcast interface and direct 
> synchronization can be omitted, but mechanically the other links on 
> the routes are those that are advertized and synchronized. Otherwise 
> you will allow out of track routing as described by Emmanuel. I would 
> say that RFC 2328 allows clique synchronization and MDR is not a 
> natural extension of this because of out of track routing. 

OSPF *does* implicitly advertise non-adjacent links in network-LSAs,
which has been mentioned several times.  In OSPF, an intermediate
hop can also be a non-adjacent link over a broadcast network.
OSPF-MDR generalizes these properties to multihop wireless networks.

Richard

> the optimization in synchronization database that we proposed two 
> years ago andwhich seems to have been recently revived by Richard.
>
> Best regards,
> Philippe.
>>> From: Emmanuel Baccelli [mailto:[email-masked]] Sent: 
>>> Thursday, June 29, 2006 8:39 AM
>>> To: [email-masked]
>>> calculated from the start. I think this is an important fact. If we 
>>> choose an approach that changes this fact, we should be aware of the 
>>> consequences, and there is a risk that MDR changes this fact.
>>>   
>>
>>

---

From: Philippe Jacquet <[email-masked]>
Date: Fri, 07 Jul 2006 18:05:16 +0200

> can be advertised in LSAs.

I am not sure that RFC 2328 actually allows to advertize non adjacent 
links. It seems to me that advertized links are still adjacent.

> from the flooding mechanism.
I think Tom is confusing with the fact that MPR can also be selected on 
min-cost basis and this will prevent out-of-track routing also when 
enabling min-cost routing.  MDR does not allow this since it does not 
select adjacent nodes over link cost, and the option where you advertize 
only MDR adjacent links will clearly result in out of track routing. 
Min-cost LSAs try to put routing path back on track but they have too 
many drawbacks (overhead, some links may be advertized on one side only, 
LSA content may vary with time due to other LSA contents that also 
vary...).

Advertizing all links may solve partially the problem but as you know 
this will lead to a very high LSA overhead. MPR solve the problem more 
efficiently.

> a problem. The important thing is that loops are avoided.

Traffic engineering needs actual costs not upper bound. For example a 
VoIP traffic may be rejected if the estimated delay is higher than 
tolerance. Of course one can play on the granularity of cost 
information. Changing a 10.5 delay into a 10.51 delay may not be worthy.

> exact cost of the path that will actually be taken.
When the topology is changing frequently, the LSA are updated more 
frequently, but nodes have always a clear view of  route costs. I don't 
think you are advocating for a fuzzy sight OSPF.

Best regards,
Philippe

---

From: Richard Ogier <[email-masked]>
Date: Fri, 07 Jul 2006 11:38:35 -0700

> links. It seems to me that advertized links are still adjacent. 

I will answer this with the following paragraph that you removed from

> I think Tom is confusing with the fact that MPR can also be selected 
> on min-cost basis and this will prevent out-of-track routing also when 
> select adjacent nodes over link cost, and the option where you 
> advertize only MDR adjacent links will clearly result in out of track 
> routing. Min-cost LSAs try to put routing path back on track but they 
> have too many drawbacks (overhead, some links may be advertized on one 
> side only, LSA content may vary with time due to other LSA contents 
> that also vary...). 

OK, we are in agreement that min-cost LSAs can avoid out-of-track
routing as can MPRs selected based on min-cost.  You claim min-cost
LSAs have disadvantages (which can be tested in simulations and/or
fixed by modifying the selection algorithm) whereas I claim that MPRs
based on min-cost also have disadvantages, including:
1. Selecting MPRs based on cost affects the flooding mechanism (not
decoupled) and thus can increase flooding overhead.
2. Requires that node i must know the cost of the reverse link (k,j)
where k is a 2-hop neighbor and j is a 1-hop neighbor, thus requiring
more link costs to be advertised in Hellos.
3. More delay in reacting to topology changes, as has been discussed
before. (Can be tested in simulations.)
4. More overhead since each MPR link must be synchronized.

Also, one can use MPR-based LSAs with MDR flooding, where the MPRs
are selected only to create LSAs and are not used for flooding.
It might be good to simulate this, along with other methods that
OSPF-MDR can use for partial-topology LSAs.

> tolerance.

Let's say the tolerance is 100 msec and the upper bound is 100 msec.
If the actual delay turns out to be 50 msec, this should be OK. In any
case, you have not yet explained why it is not OK.
MPR based routing also gives an upper bound unless MPRs
are selected based on cost.
Maybe you are just saying that min-cost routes should always
be calculated, in which case I agree this is best, but
one can trade this off to reduce overhead.

> Of course one can play on the granularity of cost information. 
> Changing a 10.5 delay into a 10.51 delay may not be worthy.
>
>>
> frequently, but nodes have always a clear view of  route costs. I 
> don't think you are advocating for a fuzzy sight OSPF.

The topology can change while the packet is en route. Also, there is 
some delay
in flooding LSAs, especially in high mobility networks in which routers must
wait MinLSInterval between LSA originations.  So you cannot assume that each
router always has perfect topology information.

Richard

---

From: Philippe Jacquet <[email-masked]>
Date: Fri, 07 Jul 2006 21:49:03 +0200

> >> OSPF-MDR generalizes these properties to multihop wireless networks.

I don't understand here. When OSPF *explicitly* advertizes a  link, then 
this link is synchronized?

>> on min-cost basis and this will prevent out-of-track routing also 
>> when enabling min-cost routing.  MDR does not allow this since it 
>> does not select adjacent nodes over link cost, and the option where 
>> you advertize only MDR adjacent links will clearly result in out of 
>> track routing. Min-cost LSAs try to put routing path back on track 
>> but they have too many drawbacks (overhead, some links may be 
>> advertized on one side only, LSA content may vary with time due to 
>> other LSA contents that also vary...). 
>
>
>

But less overhead than with your min-cost LSA. MPR are optimal with this 
respect. And explicit advertzizement and synchronization also allows 
that both sides are advertized contrary to your scheme where the status 
of a link can flip-flop.

>> this will lead to a very high LSA overhead. MPR solve the problem 
>> more efficiently.
>>

I mean that if tolerance is 100 ms and estimated delay is 150 ms then 
you reject a call that may be feasible (if actual delay is less than 100 
ns). In general  wrong cost estimate makes wrong traffic engineering.

> router always has perfect topology information.
I would think that if OSPF allows non-optimal routes during temporary 
situations, the aim is still to have an exact picture most of the time.

---

From: Richard Ogier <[email-masked]>
Date: Fri, 07 Jul 2006 18:17:09 -0700

Philippe Jacquet wrote:

>>> I am not sure that RFC 2328 actually allows to advertize non 
>>> adjacent links. It seems to me that advertized links are still 
>>> adjacent. 
>>
>>
>>
>>
> I don't understand here. When OSPF *explicitly* advertizes a  link, 
> then this link is synchronized?

I mean that a network-LSA implies there exists a direct link between
any two routers attached to the same broadcast network, even though
this link is only indirectly synchronized.  Note that such an unsynchronized
link can be an intermediate hop of a path, not just the first hop.
My point is that OSPF and OSPF-MDR both allow intermediate
hops to be unsynchronized.

> But less overhead than with your min-cost LSA. MPR are optimal with 
> this respect. And explicit advertzizement and synchronization also 
> allows that both sides are advertized contrary to your scheme where 
> the status of a link can flip-flop.

There is actually more overhead with MPRs because of the requirement
that every MPR link be synchronized.  (Recall my simulations that showed
there are about 13 times as many new adjacencies per second in a 100
node network.)

It is easy to ensure that both sides of a link are advertised with 
min-cost LSAs,
just as it is easy to do this with MPR-based LSAs.   In the latter case, 
you make
sure that both sides of each MPR link are advertised (i.e., the MPR selector
and the selected MPR).   This can be done similarly with min-cost LSAs.

Regarding flip-flopping, in the worst case this can only occur once
per topology change (i.e., we are not talking about infinite flip-flopping).
As I previously discussed, this will not occur in highly mobile networks
due to the asynchronous nature of LSA updates, and will not add significant
overhead in low mobility networks.  This can be tested in simulations.

BUT MORE IMPORTANTLY, I suggest that we agree to decouple LSAs
from flooding as follows.   MPR-based LSAs can be used with
both MPR flooding and MDR flooding.  Min-cost LSAs can also
be used with both MPR flooding and MDR flooding.  In fact,
it is better to decouple LSAs from flooding even if MPRs are
used for both!   For example, one can compute two sets of MPRs:
one set which ignores link costs for the purpose of flooding,
and another set which considers link costs for the purpose of
creating LSAs.  In this way, we can achieve a smaller, more stable
set of MPRs for flooding (by ignoring link cost), while allowing
min-cost routing.   This also allows us to select the flooding
mechanism independently of the method for partial-topology LSAs.

Richard

>>> Advertizing all links may solve partially the problem but as you 
>>> know this will lead to a very high LSA overhead. MPR solve the 
>>> problem more efficiently.
>>>
>>> Traffic engineering needs actual costs not upper bound. For example 
>>> a VoIP traffic may be rejected if the estimated delay is higher than 
>>> tolerance.
>>
>>
>>
>>
> you reject a call that may be feasible (if actual delay is less than 
> 100 ns). In general  wrong cost estimate makes wrong traffic engineering.
>
>>
>>

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Sat, 8 Jul 2006 13:20:46 -0700

> enabling min-cost routing.  

Philippe, I think the only confusion I have is in what you and Emmanuel
are specifically advocating.  

>From Emmanuel's original post, it seems that he was mainly objecting to
forwarding over non-advertised links since the predicted path cost might
change, but not to "out-of-track" routing; quoting Emmanuel again:

> out-of-track 
> routing that changes the predicted end-to-end cost is in 
> contradiction 
> with RFC 2328, and with other related documents that built on 
> the fact 
> that actual route costs can be calculated. So concerning the 
> design of a 
> solution for OSPF operation on MANETs, I think we should 
> evaluate this 
> issue further.

I simply pointed out that i) both current drafts (MPR-based and
MDR-based) are subject to this path cost changing if LSAs do not
advertise sufficient links to obtain min-cost routing, and that ii) it
had nothing to do with whether the links were adjacent or not, only
whether they were advertised or not, and iii) that both the MPR-based
and MDR-based approaches can avoid this by using min-cost LSAs.

More lately, it seems that you are protesting both out-of-track routing
and forwarding behavior that changes that predicted path cost, and
advocating a design that avoids both.  But your MPR-based draft (version
-01) makes no mention of cost; it selects MPRs based on hop counts.
Should I interpret this to mean that you plan to change your draft
accordingly?  

Tom

---

From: Richard Ogier <[email-masked]>
Date: Sun, 09 Jul 2006 09:36:04 -0700

Philippe,

We can debate the drawbacks of MPR-based LSAs (including selecting
MPRs based on link cost) vs. the drawbacks of min-cost LSAs (including
possible enhancements), but methods for partial-topology LSAs should
probably be a future topic (perhaps a goal for the next meeting).

The only reason I simulated partial-topology LSAs was so that
the flooding mechanisms could be compared in larger networks
(e.g., 100 nodes), since using full-topology LSAs is not scalable.

A more important issue to discuss now is whether we can
agree to decouple partial-topology LSAs from the flooding
mechanism.  This would allow us to select the flooding
mechanism (including adjacencies) independently of the method
for partial-topology LSAs.  By decoupling, I mean that the links
included in LSAs need not be related to the MPRs or MDRs or adjacencies
(and need not be synchronized), although we can certainly assign a
lower cost to synchronized links (which makes them more likely
to be advertised).  For example, decoupling allows two sets of
MPRs to be selected, one for flooding which ignores link costs,
and one for LSAs which considers link costs.  (I mentioned the
reason for doing this in my last message.)

So far, you do not seem open to such a decoupling, since you prefer to
require that all hops of a route (except the first hop) be synchronized,
even though OSPF does not require this.
But simulations indicate that such a requirement will prevent a scalable
solution.  This is especially true when link costs are not uniform,
which will increase the number of MPRs and the rate of new adjacencies
(assuming that MPRs are selected to provide min-cost paths).

Another question is whether min-cost routes must always be provided,
or whether a partial topology may be advertised (via LSAs) that does
not always provide min-cost routes.  For flexibility, some of us
already agreed that this should be optional, so that path optimality
can be traded off to improve scalability.  But of course, one option
should provide min-cost routing with partial-topology LSAs
(to achieve min-cost routing in a scalable manner).

Richard

---

From: "Joe Macker" <[email-masked]>
Date: Sun, 9 Jul 2006 13:51:46 -0400

I, for one, am in favor of decoupling if that is what is being argued. 

>From: Richard Ogier [mailto:[email-masked]] 
>Sent: Sunday, July 09, 2006 12:36 PM
>To: Philippe Jacquet
>Cc: [email-masked]
>We can debate the drawbacks of MPR-based LSAs (including 
>selecting MPRs based on link cost) vs. the drawbacks of 
>min-cost LSAs (including possible enhancements), but methods 
>for partial-topology LSAs should probably be a future topic 
>(perhaps a goal for the next meeting).
>
>A more important issue to discuss now is whether we can agree 
>to decouple partial-topology LSAs from the flooding mechanism. 
> This would allow us to select the flooding mechanism 
>(including adjacencies) independently of the method for 
>partial-topology LSAs.  By decoupling, I mean that the links 
>included in LSAs need not be related to the MPRs or MDRs or 
>adjacencies (and need not be synchronized), although we can 
>certainly assign a lower cost to synchronized links (which 
>makes them more likely to be advertised).  For example, 
>decoupling allows two sets of MPRs to be selected, one for 
>flooding which ignores link costs, and one for LSAs which 
>considers link costs.  (I mentioned the reason for doing this 
>in my last message.)
>
>So far, you do not seem open to such a decoupling, since you 
>prefer to require that all hops of a route (except the first 
>hop) be synchronized, even though OSPF does not require this.
>But simulations indicate that such a requirement will prevent 
>a scalable solution.  This is especially true when link costs 
>are not uniform, which will increase the number of MPRs and 
>the rate of new adjacencies (assuming that MPRs are selected 
>to provide min-cost paths).
>
>Another question is whether min-cost routes must always be 
>provided, or whether a partial topology may be advertised (via 
>LSAs) that does not always provide min-cost routes.  For 
>flexibility, some of us already agreed that this should be 
>optional, so that path optimality can be traded off to improve 
>scalability.  But of course, one option should provide 
>min-cost routing with partial-topology LSAs (to achieve 
>min-cost routing in a scalable manner).
>
>Richard
>
>
>

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Sun, 9 Jul 2006 13:13:22 -0700

> From: Joe Macker [mailto:[email-masked]] 
> Sent: Sunday, July 09, 2006 10:52 AM
> To: [email-masked]
> Subject: RE: [Ospf-manet] out-of-track routes
> 

I agree that they could be decoupled.  I am not yet convinced it is the
best design to do so  (maybe it is the best compromise design).  I
thought about this approach last year and it seemed that the added
complexity/interoperability issues were probably not worth it since it
wasn't clear that there would be a benefit.

It should be clear that if we were to move towards allowing this
decoupling and, for example, allow for either MPRs or CDS to be selected
for flooding, that there are going to be some interoperability
implications.  One of the benefits of the MDR proposal, in my view, is
that it allows for individual routers to run different variants of both
the CDS algorithm and the neighbor advertisement algorithm without
affecting correct operation of the network.  Because each CDS variant
includes what was called the "essential CDS", and because a minimal
requirement for LSA construction is to include all adjacencies, one is
guaranteed that even if different routers use different CDS variants or
different neighbor advertisement approaches, the network is guaranteed
to move towards synchronization in steady state and to provide
reachability to all destinations. 

If we say, for example, that flooding is completely decoupled from LSAs,
and agree to support both MPRs and CDS, then there are a couple of
implications:

i) routers in a flooding domain need to agree on which algorithm they
are using for flooding, because if one router is building CDS while
another is selecting MPRs, the overall flooding may not work.  Then, we
need to allow this to be signaled in the Hellos, and provide for cases
where routers do not agree, and then probably we need to have a MUST
algorithm that is the default in case of disagreement, and then we will
have moved our current disagreement to "which one is the default
algorithm"?

ii) there needs to be some technique to guarantee that the LSAs
advertised by all routers are consistent enough that reachability is
guaranteed.  For example, if A advertises a link to B but B does not
advertise link to A, there is likely to be a problem.  Note that this is
not a problem if all adjacencies are included in the LSAs, since the
adjacency graph is connected.  This is the main problem that Smart
Peering seems to have, by the way; Smart Peering was an example of a
decoupled algorithm.

Tom

---

From: Richard Ogier <[email-masked]>
Date: Sun, 09 Jul 2006 14:45:05 -0700

Tom,

To clarify, when I suggested decoupling LSAs from the flooding mechanism,
I was not suggesting that we agree to support both MPRs and MDRs.
I was suggesting that we can agree to decouple LSAs from flooding now,
and later decide whether to use MPRs or MDRs.  For example, the
MDR solution already decouples LSAs from flooding, as you implied
below. Perhaps the requirement that all Full neighbors be advertised
appears to imply coupling, but I am talking about the selection
aside from this minimum requirement. (The requirement that all
Full neighbors must be advertised can be applied regardless
of the flooding mechanism.)
By decoupling LSAs from flooding, we can discuss the flooding
mechanism separately from methods for creating LSAs, and vice versa.
I am *not* suggesting that we decouple the selection of adjacencies
from the selection of flooding relays.

A decoupled LSA algorithm is simply one that can be applied regardless
of the flooding mechanism.  For example, MPR-based LSAs can be applied
to MDR flooding (by selecting MPRs only for the purpose of deciding
which neighbors to advertise).  Since Full neighbors must be
advertised, they should be given the highest priority when selecting
MPRs.  

Regarding your point (ii) below, it is easy to ensure
that if A advertises a link to B, then B advertises a link to A,
and I am working on modifying the min-cost LSA algorithm to ensure
this and to address other issues mentioned by Philippe.

BTW, this is an unfortunate requirement of OSPF, which apparently
cannot be changed if we want to be interoperable with legacy OSPF.
In MANETs, it should not be necessary for each link to be advertised
by both endpoints (and it would be undesirable to do so if the link
cost in one direction is very large) as long as there exists
routes in both directions between any pair of routers.

Richard

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 10 Jul 2006 07:42:11 +0200

Decoupling flooding from synchronization may be interesting. For example 
MPR flooding + MPR-LSA would save a good amount of bandwidth. According 
to simulations, advertizing full LSAs already generates much more 
overhead than synchronization over full adjacencies itself.  We have 
basically three following components that may look interesting to 
decouple: reduced flooding+ reduced adjacencies +reduced topology. 
However according to strict OSPF rules it seems that reduced adjacencies 
and reduced topology are difficult to decouple but one could give higher 
priority to some adjacencies than others as suggested by Richard.

Best regards,
Philippe

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Sun, 9 Jul 2006 22:43:28 -0700

> Sent: Sunday, July 09, 2006 2:45 PM
> To: Henderson, Thomas R
> Cc: Joe Macker; [email-masked]
> Subject: Re: decoupling flooding from neighborhood 
> advertisement (was RE: [Ospf-manet] out-of-track routes)
> 
(snip)
> Perhaps the requirement that all Full neighbors be advertised

Agreed, but the point is that if there is a requirement to include all
Full neighbors, then this is a type of coupling.  If there is no
requirement to include all Full neighbors, then we need to have some
other type of requirement to guarantee connectivity.  You mentioned that
you are working to modify the min-cost LSA algorithm to do this; maybe
it will work out.  However, my point is that by dropping the requirement
to include Full neighbors, you introduce another requirement somewhere
else, and it may constrain what neighborhood advertisement algorithms
are allowed to interoperate.  For instance, will everyone in the network
be required to run min-cost, or will it be interoperable with other
approaches, and what is the basis for guaranteeing connectivity in
general?  

Tom

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Sun, 9 Jul 2006 22:55:24 -0700

> From: Philippe Jacquet [mailto:[email-masked]] 
> Sent: Sunday, July 09, 2006 10:42 PM
> To: Henderson, Thomas R
> advertisement (was RE:[Ospf-manet] out-of-track routes)
> 
> Decoupling flooding from synchronization may be interesting. 

Philippe, can you clarify what you mean by the above?  I read the
sentence by itself to mean that flooding (i.e., the first transmission)
is decoupled from the subgraph that performs retransmissions
(synchronized adjacencies).  However, the below seems to indicate that
you are referring to topology when you say synchronization.

> For example 
> MPR flooding + MPR-LSA would save a good amount of bandwidth. 

If you are saying to use currently specified MPRs for flooding and
adjacencies, and a second (min-cost) MPR selection for LSA
advertisements (what Richard suggested earlier), then yes, I agree that
it looks interesting to consider this, as well as whether MDRs for
flooding/adjacencies could be combined with MPR-based LSA link
selection.

> According 

It seems to me to be harder to decouple flooding from adjacencies since
retransmissions occur along adjacencies.

Tom

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 10 Jul 2006 08:37:34 +0200

Tom

By flooding I mean the sequence of spontaneous transmissions and 
retransmissions not trigered by LSA acknowledgement that follow an LSA 
generation. We know that this is the solution of the major problems in 
wireless OSPF. By synchronization, I mean the subgraph on which database 
are synchronized and where LSA are retransmitted on absence of 
acknowledgement. Is it what you mean? Clearly they can be decoupled. If 
synchronization is decoupled from flooding then we have an efficient 
partial solution with MPR flooding +MPR LSA to address flooding and 
reduced topology.

---

From: Richard Ogier <[email-masked]>
Date: Mon, 10 Jul 2006 10:10:00 -0700

Henderson, Thomas R wrote:

>Full neighbors, then this is a type of coupling.
>
But not the type of coupling I was talking about.  By a decoupled LSA 
algorithm I simply
meant that it can be applied regardless of the method of selecting 
flooding relays
and adjacencies.

>If there is no
>other type of requirement to guarantee connectivity.
>
Of course, the LSA algorithm should guarantee not only connectivity, but 
also
guarantee that shortest paths are calculated (if shortest path routing 
is desired).

>You mentioned that
>it will work out.
I assume you mean to ensure that if A advertises a link to B, then B 
will advertise
a link to A.  This is not strictly required to ensure connectivity in 
general,
but it happens to be required if one uses the SPF calculation in RFC 2328 .
Yes, there are simple ways to achieve this, but my whole point is that we
don't have to decide on the exact LSA algorithm now if we agree to
decouple it from flooding.

>However, my point is that by dropping the requirement
I am not suggesting that we drop the requirement to include Full neighbors.
For example, one possible LSA algorithm is to include all Full neighbors and
no other neighbors.  This algorithm can be applied to any method for 
selecting
flooding relays and adjacencies, so in my view it is decoupled.

Richard

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 10 Jul 2006 11:40:53 -0700

> Sent: Sunday, July 09, 2006 11:38 PM
> To: Henderson, Thomas R
> Cc: [email-masked]
> Subject: Re: decoupling flooding from neighborhood advertisement
> 
> acknowledgement. Is it what you mean? 

OK, thanks, that is what I thought you meant.

> Clearly they can be 
> decoupled. 

Agreed, if you just put the LSA onto the retransmission list as usual
but move its initial flood and corresponding multicast ACK onto the new
flooding structure, then it should work.  I take back this statement,

>  We have 

I agree that these three could be decoupled, but we should be careful
that we do not compromise wireless performance or duplicate a lot of
effort in the decoupled components.  That is, I'd like to see a specific
proposal for how to do this before deciding that the decoupling is a
good thing. 

Tom

---

From: Richard Ogier <[email-masked]>
Date: Mon, 10 Jul 2006 13:23:50 -0700

Tom,

Henderson, Thomas R wrote:

>> >retransmissions occur along adjacencies

I agree with your original statement, or at least that
decoupling adjacencies from flooding is unwise.
In all 3 proposals, adjacencies are aligned with the
flooding relays, and I think we should keep it that way.
This makes sense, since LSAs are retransmitted on adjacencies
when no ack is received.  Although it is possible to
not align adjacencies with flooding relays, this could
result in an LSA being retransmitted to a neighbor that
does not forward the LSA, instead of to a relay that
would forward the LSA immediately. (This would still work,
but would take longer to reach all nodes.)

In a previous message, you said that requiring all Full
neighbors to be included in LSAs is a type of coupling.
On the other hand, you said that Smart Peering is a decoupled
solution.  But in Smart Peering, MPRs are required to be
Full neighbors, so isn't this also a type of coupling?

Again, the only type of decoupling that I am suggesting
(and maybe "decoupling" is not the correct word) is
to consider LSA selection algorithms that can be applied
regardless of, and whose specification is independent of,
the method used for selecting flooding relays and adjacencies.
Whether or not you call this "decoupling", it simplifies
the design process and results in a more flexible and
extensible design.   Requiring all Full neighbors to be
included in the LSA does not violate this, since such
a rule can be applied regardless of the method used
for selecting flooding relays and adjacencies
(even though the resulting LSAs will differ for the
different methods).

Richard

---

From: Acee Lindem <[email-masked]>
Date: Mon, 10 Jul 2006 17:43:28 -0400

Hi guys,

> from the selection of flooding relays.

I agree.

> routes in both directions between any pair of routers.

Let's talk about this within the context of LSA sdvertisement reduction
(decoupled from flooding optimization and adjacency reduction :^).
I know the argument for this (smaller LSAs that change less frequently)
but I'm not a big fan (at least not at this time).  In my opinion, It 
would be
preferable to be able to solve bi-directional requirement with simply
eliminating the check.

Thanks,
Acee

>>> From: Joe Macker [mailto:[email-masked]] Sent: Sunday, 
>>> July 09, 2006 10:52 AM
>>> To: [email-masked]

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 10 Jul 2006 14:32:54 -0700

> Sent: Monday, July 10, 2006 1:24 PM
> To: Henderson, Thomas R
> Cc: Philippe Jacquet; [email-masked]
> Subject: Re: [Ospf-manet] RE: decoupling flooding from 
> neighborhoodadvertisement
> 
(snip)
> Full neighbors, so isn't this also a type of coupling?

Yes, by the same measure, it is also coupled-- I was referring to the
fact that adjacencies are trimmed independent of the MPRs elected, but
you are correct to point out that MPRs are built on top of this
adjacency subgraph and not independently of it.  I recall that we
discussed (perhaps on the list) whether to fully decouple these and it
seemed like sentiment was against allowing non-adjacent neighbors to
become MPRs.

> (even though the resulting LSAs will differ for the

OK, we seem to be more or less in sync with this clarification.

Tom

---

From: Acee Lindem <[email-masked]>
Date: Mon, 10 Jul 2006 18:38:46 -0400

Philippe Jacquet wrote:

>>> From: Philippe Jacquet [mailto:[email-masked]] Sent: 
>>> Sunday, July 09, 2006 10:42 PM
>>> To: Henderson, Thomas R
>>> (was RE:[Ospf-manet] out-of-track routes)
>>>
> wireless OSPF. By synchronization, I mean the subgraph on which 
> database are synchronized and where LSA are retransmitted on absence 
> of acknowledgement. Is it what you mean? Clearly they can be decoupled

Philippe,

Heretofore, we haven't gone down this path. I don't think we need
to since we have solutions that keep flooding along adjacencies that perform
well. What is the compelling reason to do so?

Thanks,
Acee

> . If synchronization is decoupled from flooding then we have an 
> efficient partial solution with MPR flooding +MPR LSA to address 
> flooding and reduced topology.

>
>>  
>>
>>> For example MPR flooding + MPR-LSA would save a good amount of 
>>> bandwidth.   
>>
>>
>>> According to simulations, advertizing full LSAs already generates 
>>> much more overhead than synchronization over full adjacencies 
>>> itself.  We have basically three following components that may look 
>>> interesting to decouple: reduced flooding+ reduced adjacencies 
>>> +reduced topology. However according to strict OSPF rules it seems 
>>> that reduced adjacencies and reduced topology are difficult to 
>>> decouple but one could give higher priority to some adjacencies than 
>>> others as suggested by Richard.
>>>   
>>
>>

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 11 Jul 2006 17:47:16 +0200

>seemed like sentiment was against allowing non-adjacent neighbors to

I don't remember well this discussion, wasn't it related to some 
specific implementation?  If flooding messages with sequence number were 
not authorised on non-adjacent neighbors, then I would assume that data 
would be even less allowed on such links, since data without sequence 
number is more prone to loops. In OSPF-MPR we answered the question by 
systematically synchronizing MPR links. But for me, flooding should go 
even on non-adjacent links.

---

From: Richard Ogier <[email-masked]>
Date: Tue, 11 Jul 2006 09:00:33 -0700

Acee Lindem wrote:

>> MPRs. Regarding your point (ii) below, it is easy to ensure

I assume you mean to eliminate the check in Step 2b of the SPF calculation
in RFC 2328, in which a link (V,W) can be used only if W's LSA contains
a link back to V.  I assume this check cannot be eliminated since we want
to be interoperable with legacy OSPF, so I am OK with just requiring
that if V advertises a link to W, then W must advertise a link to V.

Richard

---

From: Acee Lindem <[email-masked]>
Date: Tue, 11 Jul 2006 14:02:43 -0400

> that if V advertises a link to W, then W must advertise a link to V.

I was referring to this check but I meant the opposite of what I wrote 
:^( - I
meant I think we should solve the problem WITHOUT simply removing
the check. Sorry for the confusion.

Thanks,
Acee