Subject: [manet] OSPF extensions for manets

From: Richard Ogier <[email-masked]>
Date: Sun, 09 Nov 2003 21:59:52 -0800

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

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.

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.

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.

Regards,
Richard

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

---

From: "Tao Lin" <[email-masked]>
Date: Mon, 10 Nov 2003 13:21:34 -0500

Hi Richard,

I went over your OSPF extension draft carefully and have following comments.

First of all, thanks for incorporating our idea of relay node set (RNS)
framework into your draft.  There is a mistake in the citation.  The correct
reference information for our RNS framework is

T. Lin, S. F. Midkiff, and J. S. Park, "A Framework For Wireless Ad Hoc
Network," IEEE WCNC 2003.

Moreover, there are some other papers published that discuss the use of CDS
algorithm to reduce broadcast overhead and
support link state protocols such as OSPF in MANET (See below).  I would
suggest that these papers should also be read and/or cited as well.  At
least our IPCCC paper shows that the broadcast scheme using a CDS is a
promising approach to reduce the control overhead dramatically compared to
the blind broadcast scheme, which is used by the designated routers in OSPF.

1. B. Das and V. Bhargavan, "Routing in ad-hoc networks using minimum
connected dominating sets," in Proc. of IEEE International Conference on
Communications, vol. 1, pp. 376-380, 1997.

2. U.C. Kozat, G. Kondylis,  B. Ryu, M.K. Marina, "Virtual dynamic backbone
for mobile ad hoc networks," in Proc. of IEEE International Conference on
Communications (ICC), vol. 1, pp. 250-255, 2001.

3. T. Lin, S. F. Midkiff, and J. S. Park, "Approximation Algorithms for
Minimal Connected Dominating Sets and Application with Routing protocol in
Wireless Ad Hoc Network," in Proc. of IEEE International Performance
Computing and Communications Conference (IPCCC), pp. 157-164, April, 2003.

Actually, we have implemented (in Linux) an OSPF extension protocol for
MANET using the similar idea.  We have also created an ns2 simulation model
and are currently using that model to develop complete performance results.
A paper summarizing the work and simulation results is in progress.  The
paper can be distributed when it is allowed.

  Thank you!

  Tao Lin
  Ph.D. Candidate
  Laboratory for Advanced Networking (VT-LAN)
  ECE Dept.
  Virginia Tech