Subject: [manet] OSPF in MANETs

From: "William Lee" <[email-masked]>
Date: Thu, 8 May 2003 10:56:44 -0500

Are their any disadvantages of using OSPF in a MANET, particularly if the
network is not very dynamic?  How does the performance of OSPF change as
node mobility increases? How does it change if only the links are transient,
but mobility is minimal?
 
William Lee

---

From: "Andreas Yankopolus" <[email-masked]>
Date: Thu, 08 May 2003 12:34:49 -0400

> Are their any disadvantages of using OSPF in a MANET,
> particularly if the network is not very dynamic? 

If the network is not very dynamic, is it really a MANET :-)

> How does the performance of OSPF change as node
> mobility increases? How does it change if only the links
> are transient, but mobility is minimal?

Link flapping causes OSPF to re-flood link state advertisement packets.
The Army used OSPF and BGP4 during a  Force XXI advanced warfighting
experiment (AWE) in 1997. The network bogged down due to the large
number of OSPF updates, many of which resulted from unstable links.

Cheers,

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

---

From: "Pete Sholander" <[email-masked]>
Date: Fri, 09 May 2003 09:34:48 -0400

Phillipe,

You're correct that mu*M*N**2 is a "sharper" estimate of the LS
overhead.  Thanks for the correction.  Also, thanks to Cesar for
pointing out a newer reference to his work.

--Peter Sholander 

>>> "Philippe Jacquet" <[email-masked]> 05/09/03 05:55AM
>>>
Hello,

Even in a static network, OSPF may experience problems.

During a link state period update an OSPF network must exchange
(M*N)**2
node identifiers where N is the number of nodes and M the average
number of
links (neighbors) per node. Each node must flood an LSA message, each
LSA
message contains in average M links, each LSA message must be sent and
acknowledged on all links in the network (ie M*N times). This
broadcast
storm in general makes the network collapsing when the number of nodes
exceeds few dozens.

In a dynamic network, should not the overhead be mu*M*N**2 if the
broadcast
is a link broadcast?

In MANET word, OLSR looks the closest to OSPF. It was made originally
to
improve the link state update overhead in a MANET network. The
broadcast is
made by MPR nodes and via node broadcasts not ink broadcast (i.e.
message
are send only once, not sent separately on each link). The LSA may be
limited to a subset of links (the MPR selector links). These policies
drastically reduce the overhead.

The next step could be to design a wireless extension of OSPF that
could fit
MANET requirements in an hybrid network.

Philippe

----- Original Message -----
From: Pete Sholander <[email-masked]>
To: <[email-masked]>; <[email-masked]>
Sent: Thursday, May 08, 2003 6:34 PM
Subject: Re: [manet] OSPF in MANETs

> William,
>
> This (IMHO) is a good reference on protocol scaling ...
>
> C. Santivanez, "Asymptotic Behavior of Mobile Ad hoc Routing
Protocols
> with respect to Traffic, Mobility and Size", Northeastern University
> CDSP Tech. Report TR-CDSP-00-52, Oct. 2000.
>
> (I think he also published some refereed papers on this topic in the
> past few years, while at BBN.  Try google.com)
>
> The short answer to your questions though is that the O(N) overhead
> roughly scales as (mu)*N**2, where N is the number of nodes and mu
is
> the "link breakage rate", which may be caused by either mobility or
RF
> effects.
>
> So, OSPF may work fine in some MANETs depending on the relative
ratios
> of number of nodes, link breakage rates, and the wireless links
speeds.
> Unmodified OSPFv1 and OSPFv2 are known to work poorly in typical
> military networks.  (I'm not aware of any real-world experimental
> results for the newer OSPFv3.  Other posters may ...)
>
> Hope this helps!
>
> --Pete Sholander
>
> >>> "William Lee" <[email-masked]> 05/08/03 11:56AM >>>
>
> Are their any disadvantages of using OSPF in a MANET, particularly
if
> the
> network is not very dynamic?  How does the performance of OSPF
change
> as

---

From: [email-masked]
Date: Sun, 11 May 2003 20:54:14 -0700

Philippe,

> During a link state period update an OSPF network must exchange (M*N)**2
> node identifiers where N is the number of nodes and M the average number of
> links (neighbors) per node. Each node must flood an LSA message, each LSA
> acknowledged on all links in the network (ie M*N times). This broadcast

First, OSPF sends updates reliably, and therefore does not 
strictly need to generate periodic updates, although it does this
occasionally to add robustness.  Therefore, the update period 
can be much longer than for OLSR (for example) in static networks.
Thus, the use of reliable updates can be a big advantage in static networks.

Second, most people who implement OSPF in MANETs do not use "link broadcast",
i.e., they do not unicast each LSA on each link; they use "node broadcast",
i.e., each node sends an LSA to all neighbors using a single local broadcast.
Each neighbor must ACK the LSA, but ACKs are smaller and can be aggregated,
and can often be implicit.

With node broadcast, we get M*N**2 overhead per period instead of (M*N)**2.

> 
> In a dynamic network, should not the overhead be mu*M*N**2 if the broadcast
> is a link broadcast?

Maybe there is some confusion with mu.  We must assume that mu is the breakage 
rate per link and not per node (since otherwise mu depends on M).
Thus, the breakage rate per node is mu*M.
Since OSPF sends only "full" updates (even if only one link breaks), 
to get the overhead in a dynamic network, 
we multiply mu*M by M*N**2, which gives mu*(M*N)**2. 
However, OSPF has a minimum time MinLSInterval between originations of 
a particular LSA, so the updates will become periodic if mu is large enough.

> 
> In MANET word, OLSR looks the closest to OSPF. It was made originally to
> improve the link state update overhead in a MANET network. The broadcast is
> made by MPR nodes and via node broadcasts not ink broadcast (i.e. message

I agree that the concept of MPRs can be used to reduce the overhead 
of OSPF.  But there are many questions and issues.
One of them regards the concept of "adjacency" in OSPF.
A link (u,v) can be used for routing only if it is an adjacency,
which requires u and v to synchronize their databases.
Since different nodes report different LSAs when MPRs are used,
it is not clear how to form adjacencies when MPRs are used.

In OLSR, no such synchronization is required.  As a result, it is
possible for node i to forward a packet to neighbor j to get to
destination u, even though node j might not (yet) know of a path
to node u.  

Another question is how to compute MPRs in OSPF (e.g., TBRPF computes
MPRs differently from OLSR).  Also, MPRs might not be the best
way to reduce overhead in OSPF. 

Richard

> 
> The next step could be to design a wireless extension of OSPF that could fit
> > C. Santivanez, "Asymptotic Behavior of Mobile Ad hoc Routing Protocols
> > roughly scales as (mu)*N**2, where N is the number of nodes and mu is
> > the "link breakage rate", which may be caused by either mobility or RF
> > effects.
> >
> > So, OSPF may work fine in some MANETs depending on the relative ratios
> > of number of nodes, link breakage rates, and the wireless links speeds.

---

From: "Manral, Vishwas" <[email-masked]>
Date: Mon, 12 May 2003 01:22:05 -0400

Hi Philippe/Richard,

We did do some simulations of various flooding algorithms on OSPF in
wireline networks and measured flooding load based on that. 

Although different this could be of some relevence in this discussion.

Thanks,
Vishwas

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Monday, May 12, 2003 9:24 AM
To: Philippe Jacquet
Cc: [email-masked]
Subject: Re: [manet] OSPF in MANETs 

Philippe,

Second, most people who implement OSPF in MANETs do not use "link
broadcast",
i.e., they do not unicast each LSA on each link; they use "node broadcast",
i.e., each node sends an LSA to all neighbors using a single local
broadcast.
Each neighbor must ACK the LSA, but ACKs are smaller and can be aggregated,
and can often be implicit.

broadcast
> is a link broadcast?

Maybe there is some confusion with mu.  We must assume that mu is the
breakage 

Richard

---

From: "Manral, Vishwas" <[email-masked]>
Date: Mon, 12 May 2003 02:53:41 -0400

Just to add we did use a variant of MRP in one of the simulations. The link
to the document is
http://www.ietf.org/internet-drafts/draft-choudhury-manral-flooding-simulati
on-00.txt

Thanks,
Vishwas

-----Original Message-----
From: Manral, Vishwas 
Sent: Monday, May 12, 2003 10:52 AM
To: [email-masked]'; Philippe Jacquet; [email-masked]'
Cc: [email-masked]
Subject: RE: [manet] OSPF in MANETs 

Hi Philippe/Richard,

Thanks,
Vishwas

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Monday, May 12, 2003 9:24 AM
To: Philippe Jacquet
Cc: [email-masked]
Subject: Re: [manet] OSPF in MANETs 

Philippe,

broadcast

Richard

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Tue, 13 May 2003 08:03:46 -0700

> Sent: Sunday, May 11, 2003 9:11 PM
> To: Joe Macker
> Cc: [email-masked]
> Can you list the candidate strawman proposals for MANET 
> extensions to OSPF?
> Also, if possible, can you list the "set of efforts" that you mention?
> I know about some of the work Fred Baker has done in this 
> area, but it would be 
> nice to get more complete and up-to-date information on the 
> candidate proposals.
> 

Here is one.  We have a paper under review for MILCOM 2003 conference where we define a new "wireless" interface type for OSPF that, from the outside of the subnet, is represented as a point-multipoint network, but from within the wireless multihop network, uses OLSRs MPR mechanism to flood LSAs.  It is a full link state approach (every node floods its LSA) and the bandwidth utilization approaches that of OLSR (draft 7) in the wireless network, significantly outperforming that of the OSPF point-multipoint interface type.

Tom