Subject: RE: [manet] OSPF extensions for manets

From: "Henderson, Thomas R" <[email-masked]>
Date: Wed, 12 Nov 2003 11:44:12 -0800

Richard,
Embedded are some comments in response.

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]]
> Sent: Sunday, November 09, 2003 10:00 PM
> To: [email-masked]
> Cc: [email-masked]
> Subject: [manet] OSPF extensions for manets
> 
> 
> I would like to offer some comments on:
> 
> draft-spagnolo-manet-ospf-wireless-interface-00.txt  
> 
> and to compare it with the solution in
> 
> http://www.erg.sri.com/projects/tbrpf/docs/draft-ogier-manet-o
> spf-extension-00.txt
> 
> I will refer to these documents as [Spagnolo03] and 
> [Ogier03], respectively.
> I am not saying that either of these solutions is better than 
> the other,
> and hopefully better solutions (or suggestions for improving 
> these) will
> be proposed after the problem statement is accepted.
> 
> The draft [Spagnolo03] extends OSPF to manet interfaces by 
> using the MPR
> flooding mechanism of OSPF to flood LSAs.  I.e., it proposes to list
> MPRs in Hello messages, and to disseminate LSAs using unreliable,
> periodic flooding via MPRs.
> 
> Most of my comments can be grouped into the following three questions:
> 
> 1. Are MPRs the best choice for the relay nodes used for 
> flooding LSAs?
> 2. Is it better to use reliable vs. unreliable flooding of LSAs?
> 3. Should we try to minimize the changes to OSPF?
> 
> I will discuss the third question first. It seems to me that 
> minimizing
> the changes to OSPF would make the extension more acceptable 
> to the OSPF
> working group.  For example, as discussed below and in 
> [Ogier03], it is
> possible to avoid introducing any new packet formats, e.g., to use the
> existing format for OSPF Hello packets, and to avoid introducing a new
> flooding mechanism that requires a new sequence number for suppressing
> duplicates, etc.  OSPF already has a mechanism for suppressing
> duplicates during flooding, and it is possible to use this mechanism.

While it seems like minimizing changes to OSPF is an agreed goal, I
guess we have different views of this.  We decided not to change the
LSA format at all, but we did adopt some new message types.  But is
this really a big deal?  I would argue that even in your proposal,
you are using (overloading) a new message type for Hello because you 
are redefining the semantics of the DR field.  Also, you have proposed
changes (sequence numbers) to LSR messages.

The LSF is identical to an LSU but with the flooding sequence number.  
We are not saying that we believe LSF to be the best possible approach 
to flooding, but we are saying that it was straightforward to implement.

However, differential LSAs do represent a departure from OSPF database
formats and the logic of handling/parsing LSAs when doing SPFs (unless
differential LSAs are converted to regular LSAs upon reception).  We
were able to avoid touching any of this part of the implementation.
One also has to consider that conventional LSAs are needed to be 
circulated outside of the wireless network if it is to interoperate 
with legacy routers.

If a wireless-optimized flooding algorithm is devised that does not 
require a flooding sequence number, so much the better, but this
is not a big concern in my view.  I haven't seen a proposal yet that
didn't change how flooding is done in some manner (whether using a LSF
message or redefining database description, etc.).

> 
> Below I quote a set of bullets from [Spagnolo03] summarizing their
> proposed OSPF extension, and for comparison, after each bullet I
> summarize how the solution in [Ogier03] is different.  
> (S indicates [Spagnolo03] and O indicates [Ogier03].)
> 
>   S    defines a new Wireless Hello message.  The new message adds
>        an MPR list and eliminate backup and designated router fields;
> 
>   O    Does not require any change to the OSPF Hello packet format.
>        The Designated Router field may indicate a CDS (connected
>        dominating set) node instead of a DR.
>        
>   S    implements the MPR selection algorithm and rules for reflood-
>        ing LSAs;
> 
>   O    Implements an algorithm by which nodes select themselves
>        to be a CDS node or an MPR.
> 
>   S    efficiently floods LSAs periodically using a Link State Flood
>        (LSF) message;
> 
>   O    Uses an efficient method for reliable flooding based 
> on periodic
>        Database Description packets, using existing OSPF 
> message types.
> 
>   S    eliminates the formation of full adjacencies on wireless
>        interfaces; all neighbor states beyond 2-Way are not reached,
>        and no database synchronization is performed; and
> 
>   O    Same.
> 
>   S    includes a mechanism for suppressing the redundant flooding of
>        "outside" LSAs (LSAs originated external to the wireless sub-
>        net).
> 
>   O    A similar mechanism for suppressing "outside" LSAs can 
> be employed.
> 
> MPRs seem to be a popular method for flooding in manets, but 
> we need to
> ask whether MPRs are really the best way to flood LSAs in an OSPF
> extension.  Also, there are different ways to compute MPRs: in OLSR,
> nodes select a subset of neighbors as MPRs, but it is also 
> possible for
> nodes to select themselves as MPRs.
> 
> If MPRs are used only to flood LSAs, then a CDS is sufficent for this
> purpose and has the following advantages.  Most of these advantages
> are also shared by self-selected MPRs (which do not require nodes to
> advertise MPRs in Hellos).
> 
> 1. OSPF Hello packets can be used without modification (the DR
>    field would indicate a CDS node, which can be the sending node
>    itself). Each node decides whether it is a CDS node (or an MPR)
>    based on Hellos and LSAs originated by neighbors.
> 
> 2. As shown in reference [Lin03] of [Ogier03], and also by my own
>    simulations, using a CDS or self-selected MPR results in a relay
>    node set (set of nodes that relay a given LSA) that is smaller than
>    or about the same size as using MPRs (depending on the scenario).
> 
> 3. Using a CDS is simpler, since the relay node set is independent
>    of the LSA originator.  And the decision to forward a given LSA/LSU
>    does not depend on which neighbor it was received from.
>    
> 4. Using a CDS or self-selected MPRs can result in faster recovery
>    from link failures, since a node does not have to wait for
>    a neighbor to select it.  In fact, a CDS node or MPR is analogous
>    to a Designated Router (DR), and DRs select themselves in OSPF.
> 

I agree that CDS vs. self-selected MPRs vs. OLSR-style MPRs can be
looked at further.  However, I am not convinced that there will be
huge gains one way or the other.  One argument against CDS or other
solutions for global relay sets, which might be relevant for some 
environments is that it might end up concentrating transmission 
(battery consumption) among fewer nodes.  We chose OLSR-style 
MPRs because the MANET group has already selected it as an appropriate 
flooding optimization for MANETs, and the code was readily available.  

> The solution described in [Spagnolo03] uses unreliable, periodic
> flooding, which is quite different from the OSPF flooding mechanism,
> and requires a new packet type (LSF) that includes a new sequence
> number used to detect duplicates.  
> 
> The solution described in [Ogier03] uses a reliable flooding mechanism
> that does not require a new packet type, and uses the same 
> mechanism as
> OSPF to detect duplicates (based on the LSA sequence number in the
> database). This flooding mechanism makes efficient use of the Database
> Description (DD) and LS Request packets already defined in OSPF.  
> Instead of each node exchanging DD packets separately with each new
> neighbor, each relay node (e.g., CDS node) periodically broadcasts
> to its neighbors (on each manet interface) a set of DD packets, which
> describes the set of LSAs that it is currently responsible for
> reporting (by including the LSA headers with sequence numbers).
> This is similar to the periodic Complete Sequence Numbers 
> (CSN) packets
> of IS-IS. If a node i detects via a DD packet that a neighbor 
> CDS node j
> has a more recent instance of some LSA, then node i can 
> request the LSA
> by sending a LS Request packet to j.  More details can be found in
> [Ogier03] (link given above), including an option for 
> differential LSAs.

There are two issues here:  whether to flood reliably vs. unreliably, 
and whether to devise some concise representation of databases
so that neighbors can make sure that they are in sync.  You have
a proposal that combines the two, and it deserves more thought.

We implemented an unreliable flooding and did not use database
exchange.  Obviously, as Fred pointed out, there are scalability
implications to unreliable flooding.  Perhaps these can be addressed
by having an adaptive flooding interval that is tuned to the amount
of local topology change going on-- perhaps the best approach is to
use some reliability.  But we did find that the performance implications 
on routing were not significant-- forwarding based on the imperfect
information did as well as legacy OSPFv2 forwarding.

We have been considering augmenting the unreliable flooding with a 
reliable flooding mechanism to deal with events like Max Aging of 
LSAs (which aren't lingering around to be periodically reflooded).

So in summary, I think that this issue needs to be looked at some
more from a bandwidth efficiency perspective, but we have observed
that the imperfect information does not generally impact the route
selection performance.

> 
> As I mentioned, I am not saying that this is the best solution.
> It is only work in progress, and hopefully other solutions will
> be proposed.  There are many choices to make, such as whether
> to use a CDS, and if so, what algorithm to use.  
> Comments and suggestions are welcome.
> 

Agreed-- I just hope that we are not too harshly criticized for
adapting what has already been approved as an RFC by this group
to the problem at hand, building an implementation, finding
that it performed fairly well, and putting it on the table for
discussion.  

I also would like the group to consider that there is a new
dimension to this problem.  Not only are we concerned about
efficiency in the MANET environment itself, but we also have
to worry about how this glues into the rest of the OSPF network,
particularly if the wireless network is a transit subnet.
We have to worry about i) the possibility of hundreds or thousands
of external LSAs being injected into the wireless network, and 
ii) how to potentially mask a rapidly changing wireless environment
so that the rest of the OSPF network is not flooded with lots of
LSAs.  My feeling is that solutions to these issues will trump
issues like MPRs vs. CDS and the like.

Tom

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

---

From: Richard Ogier <[email-masked]>
Date: Sun, 16 Nov 2003 19:17:52 -0800

Philippe,

Dear Richard,

I don't think there is any conceptual conflict between MPR, CDS and

overlapping relays. To be short MPR is a practical implementation of CDS.

A CDS is also a practical implementation of a CDS.

Since it is now mature enough, it is proposed in a draft for a wireless

extension of OSPF.

I think CDS is also mature enough.  Also, it is simpler, and allows the
OSPF

Hello to be used without changing its format (as has been discussed).

For those who attended the meeting last Thursday, Fred Baker recommended

using "overlapping relays", which is the same as a CDS.  (The main difference

between an overlapping relay and an MPR is that the former forwards all
LSAs

originating from the same area, whereas the latter forwards only LSAs that

were received from an MPR selector.)

MPRs contain nice features that have been added
by the

working group during the past years such as "willingness to forward"

The same idea has been applied to CDS nodes, and in OSPF this

would just be the "router priority".

parameter, adaptability to link qualities, possibility of drastic reduction

of advertized link set size, etc.

The purpose of the CDS is to optimize the flooding, not to reduce the

set of advertised links. I agree that MPRs are useful for

reducing the set of advertised links. But this problem can be separated

from the flooding problem, and there are other ways to reduce the set

of advertised links (including self-selected MPRs).

I think the primary goal is to extend OSPF within minimal changes

to support manets, and a CDS seems to be the simplest way to

achieve this goal. A method for reducing the set of advertised links

can be proposed as an optional extension.

However they are certainly not yet

absolutely optimal, since optimal CDS selection is an NP hard problem. If

you give me a polynomial algorithm that select a good CDS, I will find

another polynomial algorithm that select a better CDS;-)  However, MPRs
have

shown acceptable performance so far that we did not find practical

algorithms that significantly outperform it.

As you know, given the set of MPRs that forward a given LSA, that set plus

the originator is a CDS.  Thus, there always exists a CDS that requires

only one more transmission than if MPRs are used.  The converse it not true.

In fact, I can easily find an example where an optimal MPR selection results

in 3 times as many transmissions as an optimal CDS selection.

But this is not as important as the other reasons for using a CDS

(simplicity and being able to use the OSPF Hello without changing

its format).

Regards,

Richard

Best regards,

Philippe