Subject: RE: [Ospf-manet] OSPF extension for MANETs

From: "Henderson, Thomas R" <[email-masked]>
Date: Thu, 2 Mar 2006 15:21:15 -0800

Philippe, some comments below. 

> -----Original Message-----
> From: Philippe Jacquet [mailto:[email-masked]] 
> Sent: Thursday, March 02, 2006 1:19 PM
> To: Richard Ogier
> Cc: [email-masked]
> Subject: Re: [Ospf-manet] OSPF extension for MANETs
> 
> Dear Richard,
> 
> The idea of MPR adjacencies has been discussed from the early 
> beginings 
> of this mailing list.
> 
> Regarding the shortest path via adjacencies the draft says exactly:
> 
>   "Contrary to other types of interfaces, over a wire-
>   less interface routing packets may also be sent over 2-Way 
> links [...]
>
>   Similarly to the broadcast interface, the next hop in the forwarding
>   table may be a neighbor that is not adjacent.  However, 
> when a packet
>   is further than its first hop, the MPR selection process guarantees
>   that the next hop in the SPT will be over an adjacency."
> 
> It means that the shortest path from an arbitrary (wireless) 
> source can 
> always be obtained via the knowledge of
> whole 2-way neighbor set of the source itself and the published 
> adjacencies of the other nodes. It is a well known property 
> of MPRs to 
> achieve that. Therefore any source has a perfect visibility of the 
> quality of the route taken by its packets.

It may be helpful to correct the sentences that Richard pointed out
because they are inconsistent with the above, and I might suggest to
avoid using the term "routing packets" to refer to data packets.

> 
> Of course if one wants that the first hop be systematically an 
> adjacencies, you don't need such a sophisticated example in order to 
> deduce that reduced adjacencies don't work. Indeed every node 
> should be 
> adjacent to any 2-way neighbor nodes since the link (A,B) is the 
> shortest path from A to B, and then B must be be adjacent to A, 
> therefore all 2-way links must be synchronized and published 
> (the basic 
> option).
> 
> Regarding adjacency reduction I would likely claim that the 
> MPR links is 
> the optimal adjacent link set to achieve the property that 
> shortest path 
> contains adjacent links with possible exception of the first hop. The 
> proof is simple: the shortest path to any destination must cover its 
> 2-hop neighborhood and therefore contains an MPR set. Therefore any 
> solution that advertize shortest path cannot do better than MPR links.
> 

I am not so sure of this claim:
- Covering is not the same as providing lowest cost path to all 2-hop
neighbors (I think you are assuming uniform cost).  In other words, your
MPR selection algorithm doesn't necessarily guarantee that the MPRs
selected align with those MPRs that provide lowest cost, because cost is
not an input to the selection algorithm.
- If you are using local (non-advertised) information to compute your
SPT, it may be the case that the paths you compute have the property you
claim (from your vantage point), but once the packet is downstream, it
may take a different path based on the different local information
available at that node; hence, I'm not sure that the above property has
any practical meaning.

Tom 

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

---

From: Philippe Jacquet <[email-masked]>
Date: Sun, 05 Mar 2006 22:24:04 +0100

Hello, Tom,

This property is inherited from MPRs. The shortest path can indeed be 
made of MPR links (with the possible exception of the first hop), and 
this property persists even if the local information is only partially 
advertized in LSAs. The proof of this property can be found in the 
litterature and is rather simple (recursion on the number of hops 
starting from nodes at distance 2).

Thus, in order to ensure that these adjacencies are used, priority 
should indeed be given to adjacencies in next hop packet forwarding. Of 
course if the ties are broken differently in SPT computation in 
different nodes, packets may take alternative routes after the first 
hop, but these different routes will strictly have the same quality, and 
will be made of adjacencies only.

Non-uniform costs of links can be taken into account in MPR selection 
heuristics in a straighforward manner as we discussed before.

Philippe

---

From: Richard Ogier <[email-masked]>
Date: Sun, 05 Mar 2006 16:33:12 -0800

Philippe,  Please see my comments below.

Philippe Jacquet wrote:

> Regarding adjacency reduction I would likely claim that the MPR links 
> is the optimal adjacent link set to achieve the property that shortest 
> path contains adjacent links with possible exception of the first hop. 
> The proof is simple: the shortest path to any destination must cover 
> its 2-hop neighborhood and therefore contains an MPR set. Therefore 
> any solution that advertize shortest path cannot do better than MPR 
> links. 

Of course, you are talking about min-hop paths, which are shortest paths
only if the cost of each link is 1.  (I comment on this limitation below.)
I agree that MPR links are the optimal adjacent links that achieve the
property that a min-hop path contains adjacent links except for the first
hop.  But since you agree that the first hop need not be synchronized,
then why require all the other hops to be synchronized?  By allowing more
"unsynchronized" hops, we can further reduce the set of adjacencies,
as in OSPF-MDR and OR/SP.  The fact that MPR adjacencies can cause
13 times as many new adjacencies (database synchronizations) per second
as OSPF-MDR in a 100 node network cannot be ignored,, since it will
have a serious effect on performance and scalability.

BTW, in a previous email dated 1/23/2006, you equated the number
of synchronizations with the (average) number of adjacencies, which
is very misleading.
The number of synchnronizations is not the number of adjacencies,
but the number of new adjacencies, i.e., the number of adjacency
formations.  So, even if the average number of adjacencies is only
about 3 or 4 times as large, the average rate of new adjacencies is
about 13 times as large in the 100 node scenario that I considered.
The strict requirement that MPRs must contain min-hop paths implies
that MPRs must change very frequently.

> should indeed be given to adjacencies in next hop packet forwarding. 
> Of course if the ties are broken differently in SPT computation in 
> hop, but these different routes will strictly have the same quality, 
> and will be made of adjacencies only.
>

As has been discussed, using non-uniform link costs can result in a larger
number of MPRs, which will result in an even higher rate of new adjacencies.
This is another argument against requiring shortest paths to contain
only adjacent links (except for the first hop).

This whole conversation started because of the following two
erroneous statements in the draft:

"This ensures that the adjacencies over
the whole OSPF network contain the shortest paths"

and

"In wireless ad hoc parts of the OSPF network, routing is performed
over synchronized adjacencies, as in usual OSPF."

I was hoping that one of the authors would agree that these
sentences need to be changed.

Richard

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Sun, 5 Mar 2006 22:12:27 -0800

> Sent: Sunday, March 05, 2006 1:24 PM
> To: Henderson, Thomas R
> Cc: [email-masked]

I think that the above adjustment to shortest path computation may be
what is missing from your draft.  Where it says:
  "However, when a packet is further than its first hop, 
   the MPR selection process guarantees
   that the next hop in the SPT will be over an adjacency."

it seems that you mean
  "However, when a packet must traverse more than one hop, adjacencies
should be
   used to compute the shortest path; the MPR selection process
guarantees
   that shortest paths (minimum hop, or minimum cost if cost is an
element
   of MPR selection) can be formed from MPR links, which are
adjacencies."

But whether this really matters is debatable; Richard has already posted
about the question of limiting the use of routable neighbors to the
first hop only.

> heuristics in a straighforward manner as we discussed before.

Agreed, but do you intend for this extension to be part of OSPF MANET?

Tom

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 07 Mar 2006 14:42:48 +0100

Dear Richard,

Thank you for your comments to the draft. We hope to find time to 
elaborate the draft during the IETF meeting, and will release a version 
updated to reflect the result of the comments and discussions shortly 
after Dallas.

About your technical comments:

You get less synchronizations simply because you omit to synchronize 
with all the links advertized in your LSA's. If you do so, then you will 
get an even larger synchronization rate than with MPR's. Of course you 
can give up advertizing those unsynchronized links, but then you missed 
the shortest path. Either you will get a significant stretch or you will 
have out of track routing: the path cost taken by the packet is not the 
path cost calculated by the source.

This will be the same effect if you add unsynchronized links after the 
first hop in the path.

I forgot to mention that from outside the wireless portion, the shortest 
path to a wireless destination will be exclusively made of synchronized 
links from the very first hop. This will remain true if the packets use 
the wireless portion as a transit network.

Best regards,
Philippe

Richard Ogier wrote:

>> is the optimal adjacent link set to achieve the property that 
>> shortest path contains adjacent links with possible exception of the 
>> first hop. The proof is simple: the shortest path to any destination 
>> must cover its 2-hop neighborhood and therefore contains an MPR set. 
>> Therefore any solution that advertize shortest path cannot do better 
>> than MPR links. 
>
>
>
>> this property persists even if the local information is only 
>> partially advertized in LSAs. The proof of this property can be found 
>> in the litterature and is rather simple (recursion on the number of 
>> hops starting from nodes at distance 2).
>>