Subject: Re: OSPF WG Direction with respect to MANET Requirements

From: Vishwas Manral <[email-masked]>
Date: Mon, 1 Dec 2003 09:45:56 +0200

Tom,

That solves it, exactly the same solution as I had pointed to you in a
private mail to you. I guess we could declare the link up once we have done
periodic flooding atleast once after the link has reached 2-way, this help
minimize the probability of loops/because of which the OSPF DB exchange has
been made to go thru so many states.

I am still thinking of how we could add one-way neighbors. The following
procedure would only work if there is a two way path between 2 neighbors,
even if not directly.

Assume three STA's A, B and C all in the same area. Assume B can see packets
from A but not from B. C has a two way neighbor relationship with A and B.

Now if we add a link in B's LSA(to one way neighbor A) with link cost
0xFFFF, the link will never be used for forwarding between B to A. A can
have a link to B with the original cost. This way a route will be present
from A to B, but not the otherway around.

To do this, we assume C signals via the Wireless Hello to A that B is a
oneway neighbor to A. When A gets this hello, it goes to state two-way with
B. Whenever C removes B from the list of oneway hello to A, the adjacency
will be declared down.

The assumption above is that another path to the one way neighbor exists, if
not directly.

Thanks,
Vishwas

-----Original Message-----
From: Mailing List [mailto:[email-masked]]On Behalf Of
Henderson, Thomas R
Sent: Friday, November 28, 2003 10:06 PM
To: [email-masked]
Subject: Re: OSPF WG Direction with respect to MANET Requirements

> -----Original Message-----
> From: Vishwas Manral [mailto:[email-masked]]
> Sent: Thursday, November 27, 2003 6:05 AM
> To: [email-masked]
> Subject: Re: OSPF WG Direction with respect to MANET Requirements
>
>
> Tom,
>
> I checked the link you sent a bit.
>
> I may be wrong here but if we model our interfaces as P2MP,
> we will not have
> a transit link from the Manet Area at all, as we are not
> going above 2-way
> state in which case the only link for the P2MP network will
> be (as per 2328)
>
>                 o   A single Type 3 link (stub network) is added with
>                     Link ID set to the router's own IP interface
>                     address, Link Data set to the mask 0xffffffff
>                     (indicating a host route), and cost set to 0.

We do the additional step as in Point-to-Multipoint:

                o   For each fully adjacent neighbor associated with the
                    interface, add an additional Type 1 link (point-to-
                    point) with Link ID set to the Router ID of the
                    neighboring router, Link Data set to the IP
                    interface address and cost equal to the interface's
                    configured output cost.

This probably should be clarified further in the draft in section 12--
basically, on a wireless subnet, once neighbors get to state 2-Way
(seeing themselves in each other's Hellos) they are considered "fully
adjacent" from the perspective of generating LSAs (since they skip
database exchange) and can advertise Type 1 links between them.

Tom

---

From: Richard Ogier <[email-masked]>
Date: Tue, 16 Dec 2003 09:16:41 -0800

Hello,

I would like to comment on the Henderson draft
(draft-spagnolo-manet-ospf-wireless-interface-00.txt)
and also point out the following draft, which describes another
approach for extending OSPF to support MANET interfaces:

http://www.ietf.org/internet-drafts/draft-ogier-manet-ospf-extension-00.txt

The above draft does not give a detailed specification, but discusses
techniques that can be used as a basis for designing an extension of
OSPFv3 to support MANET interfaces. This is my first post to the
OSPF mailing list, but I have been working with the MANET WG for
about 3 years, where I worked on the design of TBRPF.

The goal of my draft is exactly as stated by Fred Baker in the problem
statement draft and in his recent posts. In particular, I completely
agree with his post of December 1. For example, it is not necessary
to define a MANET area or cloud, but the existing notion of an OSPF
area can be used to insulate non-MANET routers from MANET routers.
In addition, the existing notion of an OSPF *stub* area can be used to
insulate MANET routers from having to flood large numbers of LSAs
originating from outside the MANET (as per Section 12.4.3.1 of
RFC 2328).

I will summarize my draft at the end of this email, but will
first comment on the Henderson draft.
My main comment on the Henderson draft is that it uses a completely
different mechanism (OLSR flooding using MPRs) for flooding LSAs,
whereas it is possible to use something that is much closer to OSPF,
without giving up efficiency.

Below I quote a set of bullets from the Henderson draft, summarizing
their proposed OSPF extension, and for comparison, after each bullet
I summarize how my proposed solution is different.
(H indicates the Henderson draft and O indicates the Ogier draft.)

  H    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 DR (and Backup DR) field indicates a CDS (connected
       dominating set) node instead of a DR.

  H    implements the MPR selection algorithm and rules for reflood-
       ing LSAs;

  O    Uses a CDS for flooding LSAs (called "overlapping relays" in
       Fred Baker's presentation). A CDS node is a simple, natural
       generalization of a DR.

  H    efficiently floods LSAs periodically using a Link State Flood
       (LSF) message (with a new flooding sequence number for duplicate
       detection);

  O    Uses an efficient method for reliable flooding using only OSPF
       message types, based on periodic Database Description packets.
       Duplicate detection of LSAs is done as in OSPF, based on the
       LS sequence number.

  H    eliminates the formation of full adjacencies on wireless
       interfaces; all neighbor states beyond 2-Way are not reached,
       and no database synchronization is performed;

  O    The draft provides a modified definition of full adjacency between
       a CDS node and its neighbors, to provide some synchronization.
       (Whether to require this is TBD.)

  H    includes a mechanism for suppressing the redundant flooding of
       "outside" LSAs (LSAs originated external to the wireless sub-
       net).

  O    Not addressed in the draft, but the existing notion of an OSPF
       stub area can be used to suppress flooding of "outside" LSAs.

For convenience, a bullet presentation is included below that
summarizes my draft.
The purpose of this draft is to discuss and recommend candidate
techniques for extending OSPF to support MANET interfaces. The draft
may contain some new ideas, but the draft is mainly based on old ideas.
The approach tries to minimize the changes to OSPF, while achieving
the goal of reducing control traffic.

As suggested by Russ White on Nov 28, it might be a good idea to
form a separate mailing list to discuss this problem
(since I can imagine having lengthy technical discussions).

Regards,
Richard Ogier

---------------------------------------------------------------------
       OSPF Extension for Manets Using Reliable Flooding

         draft-ogier-manet-ospf-extension-00.txt

                    Richard Ogier
                  SRI International

---------------------------------------------------------------------
Objectives and Issues

* OSPF generates too much control traffic in manets.
  - Link State ACKs
  - Database Exchange with each new neighbor

* Unreliable, periodic flooding is wasteful of bandwidth.

* To reduce control traffic, we need an efficient mechanism for
  reliable flooding of LSA in manets.

* Minimize changes to OSPF: make only necessary changes (otherwise we
  are really designing a new protocol).

* Some questions:
  - How to select relay nodes used for flooding LSAs?
  - How to flood LSAs reliably?

---------------------------------------------------------------------
Choice for Relay Nodes

* Connected Dominating Set (CDS)
  - Independent of originator
  - Called  "overlapping relays" in Fred Baker's presentation.
  - A natural generalization of a DR.

* Multipoint Relays (MPRs)
  - Dependent on originator
  - Useful if a min-hop path must exist that uses only MPRs as
    intermediate nodes.  (Not necessary for OSPF extension.)
  - Can be neighbor-selected (as in OLSR) or self-selected.

---------------------------------------------------------------------
Advantages of Using a CDS vs. MPRs

* 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 based on Hellos and LSAs
  originated by neighbors.

* Using a CDS is simpler since it is originator-independent.
  - Each CDS node is responsible for relaying all LSAs.
  - Full adjacencies can be formed between each CDS node and its
    neighbors.

* A CDS node selects itself, similar to a DR in OSPF. This can result
  in faster recovery from link failures.

---------------------------------------------------------------------
Suppression of LSA ACKs

* A simple way to reduce ACK traffic (if the efficient flooding
  mechanism described on the next slide is not used).

* An OSPF router can suppress LSA ACKs for received LSAs that are
  updated frequently (as may be the case in a highly mobile network).

---------------------------------------------------------------------
Reliable Flooding Using Periodic Database Description Packets

* Each router originates an LSA when it changes.

* To flood the LSA, each CDS node transmits each LSA once.

* Duplicate detection is done as in OSPF - based on the LSA
  sequence number in the database.

* No new message type is required. OSPF Database Description (DD)
  and LS Request packets are used, but in a more efficient manner.

* No ACKs, no NACKs.

* Each CDS node periodically (e.g., every 5 or 10 sec) broadcasts
  a complete set of DD packets on each manet interface.  Similar to
  the Periodic Complete Sequence Numbers packets of IS-IS.

* Since a DD packet contains only LSA headers, this generates much
  less overhead than periodic flooding of LSAs.

* Periodic DD packets accomplish two purposes:
  - The reliable delivery of LSAs to neighbors (without ACKs).
  - The exchange of LSAs between each CDS node and its neighbors
    (without requiring a separate Database Exchange with each neighbor)

* If a node receives a DD packet that indicates a CDS neighbor has a
  more recent instance of an LSA, the node sends a LS Request for
  that LSA to the CDS neighbor.

* LSAs and DD packets are always broadcast (to all neighbors) on manet
  interfaces.  LS Requests are unicast to a single CDS neighbor.

* The number of LS Requests can be reduced by using a redundant
  CDS, so that each node is a neighbor of at least two CDS nodes.
  The Backup DR field can be used to identify a redundant CDS node.

* The number of LS Requests can be reduced by having each CDS node
  transmit each LSA multiple times. (The number of times can depend
  on recent history of LS Requests.)

--------------------
Differential LSAs (optional)

* A differential LSA reports only differences (new links lost links,
  and metric changes) between the current instance and a previous
  instance of an LSA, instead of reporting the entire LSA.

* Example: If a node has 100 neighbors and loses one of them, it
  would be wasteful to generate a full LSA with 99 neighbor IDs, when
  the loss could be reported in a differential LSA containing a single
  neighbor ID.

* The checksum in the differential LSA is the checksum for the entire
  LSA.

* LS Request would also include a sequence number to indicate the
  current instance.

* Differential LSAs achieve the greatest overhead reduction
  in dense, mobile networks.

---------------------------------------------------------------------
Conclusions

* Recommend using a CDS for flooding LSAs within a MANET:
  - A simple, natural generalization of a DR.
  - No change required for OSPF Hello packet format (the DR field
    is used to identify a CDS node).

* Flooding of LSAs in a MANET does not require a new message type -
  the LS sequence number can/should be used for duplicate detection.

* Periodic Database Description packets can be used for efficient
  reliable flooding (similar to IS-IS).

* If LSA ACKs are used (instead of Periodic DD packets), LSA ACKs
  can be suppressed for LSAs that are updated frequently.

* Differential LSAs can be defined as an option, to reduce overhead
  in dense, mobile networks.

---------------------------------------------------------------------

Richard Ogier
SRI International