Subject: Re: [manet] OSPF extensions for manet

From: [email-masked]
Date: Thu, 13 Nov 2003 12:20:02 -0800

Tom,

Thank you for your comments.  
See my comments below.

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

It might not be a big deal, but I don't think the OSPF working group
would want to add more new message types or formats than necessary.
If you propose to add message types or change formats, I think you
need to justify that it is necessary.
Thus, redefining "designated router" to be an overlapping relay
is much less of a change than defining a new Hello 
format that advertises MPRs.
In fact, we can even use the term "designated router" to 
refer to "overlapping relays".  Thus, a manet can have
several DRs. 

Also, it might not be justified to add a new message type for
flooding if it is possible to use the existing OSPF mechanism
for detecting duplicates (based on LSA sequence number),
as I have proposed to do.

The differential LSAs that I proposed are optional.  
The protocol would work well without them, but using them
can greatly reduce overhead.  Therefore, adding this
new message format is justified.

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

What I am proposing, using a CDS (or overlapping relays)
with reliable flooding, avoids using a LSF, and I think
this is as close as we can get to OSPF.
Of course, some changes are necessary, but I am talking about
minimizing the changes.  

(snip)

> 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 

This is a good point that I have thought about.
Do MPRs *ensure* that traffic concentration is avoided?
Or is it possible that the same node will tend to be 
an MPR for many neighbors, so that traffic will still 
be concentrated at the few nodes that are MPRs.
(And if MPRs are more spread out, then I argue that this
will result in more redundancy in flooding, but this 
needs to be investigated using simulations.)

With a CDS, we know exactly where traffic is concentrated
(at the CDS nodes).  So, by dynamically changing the
router priority (i.e., the priority for being selected
as a DR), we can dynamically change the CDS in a controlled
manner, and thus fairly distribute the battery consumption
among all nodes.  There are papers that talk about this.

I will end here, but you have some good comments below that
we can discuss later.

Regards,
Richard

> 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