OSPF for MANETs

Introduction

OSPF (Open Shortest Path First) is one of the main intra-domain routing protocols in the Internet. OSPF4MANET is a research effort, extending OSPF in a way such that it can be used also in networks exhibiting a more dynamic topology than traditional wired networks. This includes, in particular, OSPF Autonomous Systems containing areas which look like wireless mesh networks, mobile ad hoc networks — with the general case being more complex internetworks containing both wired and wireless mesh networks.

Wired/wireless internetwork

Wired/wireless internetwork

A MANET interface for OSPF

OSPF4MANET focuses on the design, development and performance evaluation of a “MANET interface” for wireless networks, to be added to the other interfaces defined in the specifications of OSPF (OSPFv2 in RFC2328, OSPFv3 for IPv6 in RFC5340) for wired networks. The resulting extended version of OSPF is thus expected to operate in a compound autonomous system, federating both wired and wireless networks.

OSPF basics

As explicitly stated in its name, OSPF is designed to route data packets over the “Shortest Path First“, i.e., the route with least cost (according to a certain metric) available between source to destination in a given network topology.

A link-state routing protocol, OSPF requires that all routers in a network hold a complete, consistent view of the network topology. Based on this topology knowledge, routers are able to compute network-wide optimal routes to all possible destinations, and thus to take consistent forwarding decisions for any received data packet.

OSPF ensures consistency of topology information held by all routers by enforcing pair-wise synchronization between routers: two routers having synchronized their link-state database, and updating subsequently changes to the other, are said to be adjacentadjacencies are thus the links over which link-state updates are sent.

OSPF operation thus can be summarized in two main principles:

  1. Control traffic (link-state advertisements, LSAs) is sent over synchronized links (adjacencies).
  2. User traffic (data packets) is sent over shortest paths, computed among synchronized links.

OSPF4MANET has the double objective of preserving these two core principles of OSPF while adapting the protocol operation to the specific conditions of wireless mesh and mobile ad hoc networks. Other alternatives have been explored, designed, implemented and evaluated as complementary proposals.

OSPF sends user traffic over shortest paths, and control traffic over synchronized links — OSPF4MANET preserves both properties in MANET scenarios

Techniques for the OSPF extension for MANETs

The MANET extension of OSPF relies on the optimization of information exchange and the use of reduced network overlays to improve the operations related to link-state routing: (i) neighbor sensing, (ii) LSA flooding, (iii) adjacency synchronization, and (iv) local topology description for shortest path tree computation. Different techniques for decentralized overlay construction and maintenance are proposed, evaluated and implemented in the MANET extension for OSPF for the different link-state operations:

  • Multi-Point Relays (MPRs), in which a router selects among its 1-hop neighbors a subset of relays, able to reach all its 2-hop neighbors, based on the neighborhood information collected via Hello exchange.
  • Synchronized Link Overlay Triangular (SLOT), in which pairs of routers agree to include the link between them in a distributed overlay for link-state synchronization purposes, based on the neighborhood information collected via Hello exchange. This overlay is expected to connect all routers in the network by reducing the number of involved links and the rate of link change. 

    slotu-example

    SLOT overlay (blue) in a wireless mesh network (red for links).

  • Smart Peering (SP), specified in RFC5820, in which routers synchronize the link between them if a global path of synchronized links between them does not (yet) exist. This technique relies on global topology information stored in the network-wide link-state database.

Some of these techniques are inspired in mechanisms used and tested in the Optimized Link State Routing protocol (OLSR – RFC3626 and OLSRv2 – RFC7181). The combination of these techniques for the different link-state operations has led to the design and analysis of variants of the MANET extension of OSPF, and for exploration of different trade-offs between link-state control traffic and quality of computed data paths, resulting in the design and standardization of MPR-OSPF, an extension to OSPFv3.

MPR-OSPF

MPR-OSPF is the extension of OSPF for MANET that preserves the two core principles of OSPF routing in wireless mesh scenarios. It is standardized in RFC5449. MPR-OSPF uses the notion of Multi-Point Relaying for optimizing the main OSPF tasks over MANETs. Based on the 2-hop neighborhood information collected via Hello messages, a router selects (i) a set of Flooding MPRs, expected to reach every 2-hop neighbor of the router, and (ii) a set of Path MPRs, expected to include neighbors involved in the shortest paths from every 2-hop neighborhood of the router to the router itself. These two sets are the same for the hop count metric, and may differ if other metrics are used.

  • Adjacencies. A node becomes adjacent to its multi-point relays (Flooding MPRs and Path MPRs) and its MPR selectors (i.e., those neighbors that selected the node as Flooding or Path MPR). Adjacency selection is persistent, meaning that once two neighboring nodes have been synchronized, the adjacency is maintained as far as the nodes remain neighbors.
  • Flooding. A router only forwards LSAs coming from Flooding MPR selectors, and only sends LSA acknowledgements if the LSA was sent by an adjacent neighbor.
  • Topology description. A router advertises Path MPRs and Path MPR selectors in its Router-LSAs. Both are adjacent neighbors according to the adjacency rule; advertising them in Router-LSAs is thus compliant with OSPFv3 specification (RFC5340).
  • Neighbor sensing. Hello messages report, for every neighbor of the sending router, its status as Flooding MPR, its status as Path MPR and the cost of node-to-neighbor and neighbor-to-node links.

MPR-OSPF is the MANET extension of OSPF that reduces control traffic (flooding, adjacency-forming, topology description) while preserving the core principles of OSPF operation

Other MANET extensions of OSPF

If the two core principles of OSPF routing are not respected when operating over MANETs, other configurations become possible. The combination of other overlay generation techniques lead to different MANET extensions of OSPF that explore additional trade-offs between optimality of user data paths, reduction of control traffic and preservation of OSPF legacy.

  • SLOT-OSPF explores total decoupling of adjacency forming (based on the SLOT technique) from flooding and topology description (based on Flooding MPRs and Path MPRs, respectively). This allows to reduce substantially the overall control traffic, at the expense of seriously degrading the quality of user traffic routing.
  • MPR+SP also decouples adjacencies from flooding/topology description. However, although it does not synchronize all reported links, it reports in Router-LSAs all adjacent links. MPR+SP thus uses Smart Peering for adjacency-forming purposes, performs flooding over Flooding MPRs (computed over the Smart Peering overlay) and reports both Path MPRs and Smart Peering neighbors in Router-LSAs. Use of SP reduces to the minimum the control traffic due to link-state synchronization. Inclusion of Path MPRs ensures that theoretical shortest paths are included in the reported link-state, and inclusion of adjacent Smart Peering links ensures that synchronized links are taken into account in shortest path computation.

How to extend OSPF? What to preserve, what to remove?

Evaluation of the different configurations and extensions, MPR-OSPF (RFC5449), the others (MPR+SP, SLOT-OSPF), together with other IETF standards (e.g. OR/SP, RFC5820), allow to examine the impact of the core principles of OSPF (P1–shortest, synchronized paths for user traffic, P2–synchronized links for control traffic) in routing performance in mobile ad hoc networks. Evaluation of these variants and MPR-OSPF allows to observe that:

  1. Ensuring that reported links allow to compute “shortest paths” computation for user traffic proves beneficial,
  2. Synchronization of all reported paths (in Router-LSAs) is costly and not necessarily effective,
  3. Reporting (in Router-LSAs) synchronized links has a positive impact in routing quality.

Implementation

  • OSPFv3 Extension for Wireless Ad-hoc Networks. Source code (C++) and corresponding documentation are publicly available at the INRIA GForge repository.

Related Publications

Cordero, Juan Antonio; Yi, Jiazi; Clausen, Thomas; Baccelli, Emmanuel

Enabling Multihop Communication in Spontaneous Wireless Networks Book Chapter

In: Haddadi, Hamed; Bonaventure, Olivier (Ed.): Recent Advances in Networking, Chapter 9, pp. 413-457, ACM SIGCOMM, 2013.

Links | BibTeX

Cordero, Juan Antonio; Philipp, Matias; Baccelli, Emmanuel

Routing across Wired and Wireless Mesh Networks: Experimental Compound Internetworking with OSPF Proceedings Article

In: Proceedings of the 8th IEEE International Wireless Communications and Mobile Computing Conference (WCMC 2012), 2012.

Abstract | Links | BibTeX

Cordero, Juan Antonio; Jacquet, Philippe; Baccelli, Emmanuel

Impact of Jitter-based Techniques on Flooding over Wireless Ad hoc Networks: Model and Analysis Proceedings Article

In: pp. 2059-2067, IEEE Proceedings of the 31st Annual IEEE International Conference on Computer Communications (INFOCOM 2012)., Orlando, FI, United States., 2012, ISSN: 0743-166X.

Abstract | Links | BibTeX

Cordero, Juan Antonio; Baccelli, Emmanuel; Jacquet, Philippe; Clausen, Thomas

Wired / Wireless Compound Networking Book Chapter

In: Wang, Xin (Ed.): Mobile Ad-Hoc Networks: Applications, Chapter 16, InTech, 2011, ISBN: 978-953-307-416-0.

Links | BibTeX

Cordero, Juan Antonio; Clausen, Thomas; Baccelli, Emmanuel

MPR+SP: Towards a Unified MPR-based MANET Extension for OSPF Proceedings Article

In: Hawaii International Conference on System Sciences, 2011.

Abstract | Links | BibTeX

Baccelli, Emmanuel; Cordero, Juan Antonio; Jacquet, Philippe

Optimization of Critical Data Synchronization via Link Overlay RNG in Mobile Ad Hoc Networks Proceedings Article

In: pp. 402-411, IEEE Proceedings of the 7th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS’2010)., San Francisco, CA, United States., 2010, ISSN: 2155-6806.

Abstract | Links | BibTeX

Cordero, Juan Antonio

Adjacency Persistency in OSPF MANET Proceedings Article

In: Proceedings of the 4th IET China-Ireland International Conference on Information and Communication Technologies (CIICT’2010)., 2010.

Abstract | Links | BibTeX

Cordero, Juan Antonio; Baccelli, Emmanuel; Jacquet, Philippe

OSPF over Multi-Hop Ad Hoc Wireless Communications Journal Article

In: International Journal of Computer Networks and Communications , vol. 2, no. 5, pp. 38-56, 2010, ISSN: 0975-2293.

Abstract | Links | BibTeX

Cordero, Juan Antonio

MPR-based Pruning Techniques for Shortest Path Tree Computation Proceedings Article

In: Proceedings of the 18th IEEE International Conference on Software Telecommunications and Computer Networks (SoftCom)., 2010.

Abstract | Links | BibTeX

Baccelli, Emmanuel; Cordero, Juan Antonio; Jacquet, Philippe

Using Relative Neighborhood Graphs for Reliable Database Synchronization in MANETs Proceedings Article

In: pp. 1-6, Proceedings of the 5th IEEE SECON Workshop on Wireless Mesh Networks (WiMesh 2010)., Boston, MA, United States., 2010.

Abstract | Links | BibTeX

Baccelli, Emmanuel; Cordero, Juan Antonio; Jacquet, Philippe

Multi-Hop Relaying Techniques with OSPF on Ad Hoc Networks Proceedings Article

In: Proceedings of the 4th IEEE International Conference on Systems and Networks Communications (ICSNC – SoftNet 2009), 2009.

Abstract | Links | BibTeX

Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe; Nguyen, Dang

RFC5449 - OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks Miscellaneous

2009, (http://tools.ietf.org/html/rfc5449).

Abstract | Links | BibTeX

Cordero, Juan Antonio

On MPR-OSPF Specification and Implementation in Quagga/GTNetS Technical Report

INRIA Research Report, no. 6827, 2009.

Links | BibTeX

Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe; Nguyen, Dang

Integrating VANETs in the Internet Core with OSPF: the MPR-OSPF Approach Proceedings Article

In: International Conference on ITS Telecommunications (ITST), Sophia Antipolis, France, June 2007, 2007.

Abstract | Links | BibTeX

Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe

Ad-hoc and Internet Convergence: Adapting OSPF-style Database Exchanges for Ad-hoc Networks, Proceedings Article

In: Proceedings of the Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs), London, UK., Proceedings of the Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs), London, UK., 2004.

Abstract | Links | BibTeX

Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe

OSPF-style Database Exchange and Reliable Synchronization in the Optimized Link State Routing Protocol Proceedings Article

In: IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), San Jose, USA, Oct. 2004, 2004.

Abstract | Links | BibTeX

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.