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

From: Philippe Jacquet <[email-masked]>
Date: Thu, 02 Mar 2006 22:19:19 +0100

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.

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.

Best regards,
Philippe

Richard Ogier wrote:

> Emmanuel Baccelli wrote:
>
>>
>> Hi all,
>>
>> as discussed, here is a contribution to OSPF extension for MANETs, 
>> incorporating MPR mechanisms for flooding overhead reduction and 
>> adjacency reduction.
>> http://www.lix.polytechnique.fr/~baccelli/MPR-OSPF/draft-baccelli-ospf-mpr-ext.txt 
>>
>>
>> Emmanuel
>>
> Emmanuel,
>
> My first reaction is that it would have been nice to see this
> proposal about a year ago.  My second reaction is that your proposal
> needs to be implemented in GTNetS so it can be compared to
> OSPF-MDR and OR/SP.  (I am not sure who will do this.)
> The design team agreed long ago to compare the proposals
> in GTNetS, and Boeing has put a lot of effort into doing this.
>
> In any case, based on the simulation results that I posted on 2/8/2006,
> your approach in which each router forms an adjacency with each
> MPR neighbor will result in much more overhead than OSPF-MDR,
> as I mentioned in my position draft.  For example, in a dense 100-node
> network (with range equal to 0.5 times the width of the square grid),
> using MPR adjacencies resulted in 13.3 times as many new adjacencies
> per second as 1-connected MDRs.
> This implies 13.3 times as much Database Description (DD) overhead.
> A GTNetS simulation shows that the DD overhead for 1-connected MDRs in
> this scenario is 76.75 kbps, which implies a DD overhead of
> 13.3 * 76.75 = 1,020 kbps for MPR adjacencies.
> (Of course, this is an estimate, so your approach needs to be
> implemented in GTNetS to verify this.)
>
> To make matters worse, your MPR selection algorithm makes no attempt
> to select MPRs persistently, e.g., to give higher priority to neighbors
> that are already adjacent, whereas the ratio of 13.3 assumed
> that MPRs are selected persistently.
>
> There is also an error in your draft.  You stated:
>
> "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."
>
>
> The following example shows that the set of adjacencies does
> not always contain the min-hop paths.
>
>       5
>      / \
>     /   \
>    1 --- 2
>    |     |
>    |     |
>    3 --- 4
>     \   /
>      \ /
>       6
>
>
> In the above example:
> Node 1 selects 3 as MPR to cover 4 and 6.
> Node 2 selects 4 as MPR to cover 3 and 6.
> Node 3 selects 1 as MPR to cover 2 and 5.
> Node 4 selects 2 as MPR to cover 1 and 5.
> Node 5 becomes adjacent with 1 and 2.
> Node 6 becomes adjacent with 3 and 4.
>
> As a result, all neighbor pairs become adjacent
> except for [1, 2] and [3, 4].
>
> The set of adjacencies does form a connected subgraph that
> spans all nodes (which is guaranteed).
> However, the set of adjacencies does not contain a min-hop path
> between nodes 1 and 4 (or between nodes 2 and 3).
>
> For example, if node 1 wanted to route packets to node 4,
> it would have to select node 2 as the next hop, even though
> node 2 is not adjacent (not synchronized).
> This problem can be fixed, but you must use the concept
> of routable neighbors or unsynchronized adjacencies, as used by OSPF-MDR
> or OR/SP. For example, node 2 would be considered routable if there
> exists a path of synchronized adjacencies to node 2.
>
> But then, you are no longer routing only along synchronized
> adjacencies, so you lose one of the advantages that you claim.
>
> Richard
>
>
> _______________________________________________
> 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: Sun, 05 Mar 2006 17:12:01 -0800

Philippe,  One more comment below.

Philippe Jacquet wrote:

> 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 
> therefore all 2-way links must be synchronized and published (the 
> basic option). 

Routing is not needed to send a packet to a 1-hop neighbor, as Emmanuel
has previously pointed out, so of course I wanted an example
that considered at least two hops.  It is possible to select a reduced
set of adjacencies such that the following statement in your draft
is true whenever the destination is at least 2 hops from the source,
so I wanted to see if the statement is true for paths with at least
2 hops.

Richard