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

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 adjacent — adjacencies 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. 
  

  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