Subject: Extensions to OSPF to Support Mobile Ad Hoc Networking

From: Russ White <[email-masked]>
Date: Wed, 11 Feb 2004 09:52:54 -0500

Y'all:

We are past the new work cutoff, so I'm posting this directly here, rather
than waiting 'til after IETF to do so. I'll post it in the normal way after
IETF is over.

http://www.riw.us/temp/draft-chandra-ospf-manet-00.txt

Abstract:

This document describes extensions to OSPF to support mobile ad hoc
networking. Specifically, the document specifies a mechanism for
link-local signaling, a OSPF-MANET interface, a simple technique to
reduce the size of Hello packets by only transmitting incremental
state changes, and a method for optimized flooding of routing
updates.

:-)

Russ

__________________________________
[email-masked] CCIE <>< Grace Alone

---

From: Richard Ogier <[email-masked]>
Date: Tue, 17 Feb 2004 21:39:57 -0800

Russ and all,

I have some comments on the document
    draft-chandra-ospf-manet-ext-00.txt

I like the use of incremental (or differential) Hellos.
TBRPF also uses differential Hellos to reduce overhead,
and avoids having to report all neighbors
periodically in Hellos.  (As far as I know TBRPF is the
first MANET protocol that has Hellos with this property.)

I also like your use of the sequence number (SCS) that
is incremented only when the neighbor set changes.
This is probably an improvement over the Hello sequence
number of TBRPF, which is incremented with each Hello.

However, one advantage of TBRPF Hellos is that a 1-way
neighbor is not included indefinitely in Hellos.
(A MANET node can have a large number of 1-way neighbors
that never become 2-way.) However, it should be easy to modify
your protocol so that 1-way neighbors are included in Hellos
for only a short time.

I also like the fact that 2-hop neighbor information is
learned via LSAs and not Hellos.  This has been a point
of argument between TBRPF and OLSR for years.
(In OLSR, nodes learn 2-hop neighbor information via Hellos,
and in TBRPF this is learned via topology updates.)

I like the technique in which each node only needs to ACK
each LSA instance once (even if it is received from
multiple neighbors). However, this can still result
in a lot of overhead when topology changes are frequent.

In draft-ogier-manet-ospf-extension-00.txt, I discuss
two promising alternatives to ACKs, which I summarize
below.

The first idea is to identify LSAs that change frequently,
by maintaining an exponential moving average of the time
between successive updates of each LSA. The originator
can identify (via an option bit) such frequently changing
LSAs as "non-ackable".  (This is slightly different from
my draft.)  Non-ackable LSAs are retransmitted periodically
(e.g., every 5 seconds) and thus need not be ACKed, thereby
reducing overhead significantly.

The second idea in my draft is inspired by the Complete
Sequence Numbers messages of IS-IS.  Each node (or as
proposed in my draft, each CDS node) periodically
broadcasts to all neighbors a complete set of Database
Description packets.  If a node receives such a DD packet
from a neighbor that indicates the neighbor has a more recent
instance of some LSAs, the node unicasts a LS Request packet
to the neighbor, to request the newer information.

INRIA has put out a new draft (draft-clausen-manet-ospf-dbx-00.txt)
which presents a variation of this idea that uses a more
compact representation for the Database Description messages.
My objective was to use the OSPF DD and LS Request packets
with little or no modification, but it will be interesting to
see if the more compact representation of INRIA reduces
overhead sufficiently to justify the new message types.

Finally, it appears that you require the formation of full
adjacencies between all pairs of neighbors, which I think
is very inefficient. That's like requiring that adjacencies
be formed between all pairs of nodes in an OSPF broadcast network
(instead of just between the DR and Backup DR and their neighbors).
As discussed in my draft, adjacencies only need to be formed
between CDS nodes and their neighbors.
(A CDS node is a natural generalization of a DR.)
My draft also discusses ways to reduce overhead with
MPRs, e.g., by having each MPR report only a subset
of the LSAs in its database. (It may also be possible to
apply this latter idea to reduce the overhead of the method
described in INRIA's new draft.)

Richard