Subject: Re: [manet] OSPF in MANETs

From: "Pete Sholander" <[email-masked]>
Date: Thu, 08 May 2003 12:34:33 -0400

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
node mobility increases? How does it change if only the links are
transient,
but mobility is minimal?
 
William Lee
  
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Cesar Santivanez <[email-masked]>
Date: Thu, 08 May 2003 17:56:39 -0400

William,

The `reader-friendly', peer-reviewed version of that tech report
was published on Infocom 2002:

C. Santivanez, Bruce McDonald, Ioannis Stavrakakis, Ram Ramanathan.
``On the Scalability of Ad Hoc Routing Protocols,'' in {\em Proceedings of
IEEE Infocom'2002}, pp. 1688-1697, New York, USA, June 2002.

Also, you may be interested in a modification to OSPF's link state mechanism
that although simply it greatly increases the routing protocol scalability
properties:

C. Santivanez, S. Ramanathan, and I. Stavrakakis,``Making Link State Routing
Scale for Ad Hoc Networks'', In {\em Proceedings of MobiHOC'2001},
Long Beach, CA, Oct.  2001.

Hope this helps

Cesar

--
Cesar Santivanez, Ph.D.
Network Scientist
Internetwork Research
BBN Technologies (A verizon unit)

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 9 May 2003 11:55:26 +0200

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