OLSR – Optimized Link-State Routing

THE Routing Standard for Dynamic, Wireless, Ad hoc, MESH networks

The Optimized Link-State Routing Protocol (OLSR, and its successor OLSRv2) is the IETF standardized routing protocol for Mobile Ad hoc NETworks (MANET).

A link state protocol, OLSR (RFC3626) prototyped several innovative techniques and principles, including the concept of Multi-Point Relays (MPRs) for Flooding Reduction and Topology Reduction, an advanced neighborhood discovery mechanism for detecting and tracking link-bi-directionality in wireless environments and across multiple wireless interfaces. Some of these techniques were later revised, adapted for OSPF and included in the OSPF extension for MANETs (see OSPF for MANETs).

OLSRv2 (RFC7181) and its constituent parts (RFC5148, RFC5444, RFC5497, RFC6130 RFC7181, RFC7182, RFC7183, RFC7184, RFC7185, RFC7186, RFC7187, RFC7188) were built on the 10+ years of experience with OLSR, and offer:

High scalability in dense networks by way of Flooding Reduction and Topology Reduction
A modular plug-in security architecture
Flexible, multi-metric routing
Compressed (aggregated) addresses for significantly smaller control messages
Built-in extensibility mechanisms, preserving forward and backwards compatibility
Native and efficient IPv6 support
Flexible and extensive gateway support, for attached networks as well as for global Internet connectivity.

As such, OLSRv2 is more than just a routing protocol – OLSRv2 is the platform for Dynamic, Wireless, Ad hoc, MESH network innovation and experimentation.

A Protocol of World-Firsts

OLSR and OLSRv2 have given rise to, numerous “world-firsts”, including:

OLSR was the first IETF routing protocol to introduce topology reduction and flooding reduction – proving their viability and immense benefit, and being the impulse for introducing these concepts to OSPFv3 by way of OSPF4MANET.
OLSRv2 was the first IETF routing protocol supporting multi-topology routing, before even OSPF, by way of “Multi-Topology Extension for the Optimized Link State Routing Protocol Version 2 (OLSRv2)” (RFC7722).
OLSRv2 was the first IETF routing protocol specifying and experimenting the use of Identity-Based Signatures for authenticating routing messages (RFC7859).

MPRs: Flooding Reduction & Topology Reduction

MPR Flooding Reduction

OLSR being a link state protocol, the basic concept is that Link State Advertisements (LSAs – in OLSR & OLSRv2 called TC Messages) are flooded through the network, allowing each router to compute a topology map – on which a shortest path algorithm (such as Dijkstra’s algorithm) is run so as to calculate shortest paths to each destination in the network

The “Optimized” in “Optimized Link State Routing” stems, in no small part, from the protocol’s use of MultiPoint Relays, MPRs.

By way of the Neighborhood Discovery Protocol (NHDP – RFC6130), each router will, by way of a periodic and per-interface HELLO message exchange, have learned its local topology: bidirectional links to its immediate neighbors (1-hop neighbors), as well as bi-directional links from its 1-hop neighbors and to their neighbors (2-hop neighbors). For a given router, the 1-hop and 2-hop neighbors form the routers “neighborhood”.

Each router can then, autonomously and without any coordination, select a subset from among its 1-hop neighbors, which forms a dominating set over its neighborhood – that dominating set is the MPR set of that router.

Or, more colloquially, each router selects its MPR set from among its 1-hop neighbors such that a packet transmitted by it, and repeated by only the members of its MPR set, will be received by all 2-hop neighbors. This is signaled in next HELLO message exchange, allowing each router to know for which other routers it is, or is not, an MPR – to construct its “MPR Selector Set” (the set of routers, which have selected it as MPR).

This information is, then, used in two ways:

MPR Based Flooding Reduction:
- When receiving a TC message, forward it if and only if it was received from a MPR Selector
- (And, of course, don’t forward a TC message more than once)

MPR Based Topology Reduction:
- Only routers which have a non-empty MPR Selector Set generate TC messages.
- And, when generating a TC message, a router only includes links to destinations listed in the MPR Selector Set

The advantages of this use of MultiPoint Relays, MPRs, is thus fourfold:

The cost of a flooding operation is considerably reduced: The number of retransmissions of a single flooded message, especially in a dense network, is considerably lower when using MPR based Flooding Reduction, than when using classic flooding. On the figure above, the top example depicts “classic flooding”, with the bottom example MPR flooding, and the blue nodes” the relays (and thus, retransmissions) involved in a flooding operation.
The packet loss of a flooding operation is considerably reduced: On the figure above, the top example depicts classic flooding, with the bottom example depicting MPR flooding, and the “red nodes” depicting those nodes which receive more than a single copy of a transmission. In a wireless environment, given that all 1-hop neighbors receive the same transmission at the same time, they potentially do the same carrier sense operation and detect at the same time that the channel is idle – and transmit at the same time. Concurrent transmissions entail collisions, which entails packet loss. Thus, MPR flooding limiting the number of relays also limits the number of colissions.
The number of flooding operations is considerably reduced: Only routers with non-empty MPR Selector Sets generate TC messages. As illustrated in the figure above, all the “blue routers” would generate and flood “I have a link to the router in the center” – with the top example being that of a classic link state routing protocol, and the bottom example that of OLSR and OLSRv2.
The size of each flooded message is considerably reduced: Only the subset of destinations listed in a routers MPR Selector Set (i.e., only the destinations on routers that have selected it as MPR) are included in the flooded TC messages, rather than all destinations on all neighboring routers.

The resulting topology graph in each router is a partial graph, including all destinations (of course) and a subset of all links – a subset which contains the links on all shortest paths.

A World-Wide Community

In addition to being “a routing protocol for MANET”, OLSR and OLSRv2 is a world-wide community, actively contributing to the protocol specification development, to proposing, developing, and specifying protocol extensions, to implementing the protocol specifications on various platforms — and, of course, to deployments of OLSR & OLSRv2. The map below depicts known deployments of OLSR & OLSRv2.

Known OLSR and OLSRv2 Deployments, world-wide.

Among the experiments, uses, and deployments of OLSR and OLSRv2 are as diverse scenarios as tactical networking, emergency networking, and community networks.

BAE Systems Tactical Networking Experiments

FunkFeuer.at Community Network Deployment

Several open-source (and, of course, many many proprietary), independent, implementations of OLSR and OLSRv2 exist, a (very partial) list of public implementations includes:

OLSR.org – supporting both OLSR and OLSRv2
NRL ProtoLib-based OLSR implementation
An implementation of OLSR for Windows Mobile
An OLSRv2 Simulator – developed at Technion University, Israel

International Interoperability Events

During the development of the core OLSR and OLSRv2 specifications, semi-regular interoperability tests & workshops have occurred, the most structured of which have been:

2004 – San Diego
2005 – Paris, France (Ecole Polytechnique)
2006 – Tokyo & Narita, Japan (KEIO University & Niigata University)
2008 – Ottawa, Canada (CRC)
2009 – Vienna (FunkFeuer.at)

The technical output of these events have been retained in the OLSR and OLSRv2 (& constituent parts) specifications.

A Flexible, Modular Platform for Experimentation

The OLSRv2 protocol architecture is built around a flexible, modular, platform, intended to facilitate easy development, implementation, and testing of (forward and backwards compatible) routing protocol extensions. This is obtained, in part, by way of OLSRv2 defining and exposing a comprehensive protocol information base, as well as comprehensive constraints enabling and scoping protocol extensions‘ use (consultation, updating) thereof. An other important component of the flexible, modular platform is the use of “The Generalized Mobile Ad hoc NETwork (MANET) Packet/Message Format” RFC5444.

This has given rise to, numerous extensions, experiments, and even world-firsts around OLSRv2:

OLSRv2 was the first IETF routing protocol supporting multi-topology routing, before even OSPF, by way of “Multi-Topology Extension for the Optimized Link State Routing Protocol Version 2 (OLSRv2)” (RFC7722).
OLSRv2 was the first IETF routing protocol specifying and experimenting the use of Identity-Based Signatures for authenticating routing messages (RFC7859).

Other extensions and experiments, enabled by OLSRv2, include:

An approach at exploiting multiple disjoint paths across a wireless network, with the ambition of providing a communicating pair with aggregate throughput of these paths.
Development of, and experiments with, more evolved link metric types, such as a “Directional Airtime Metric Based on Packet Sequence Numbers for Optimized Link State Routing Version 2 (OLSRv2)” (RFC7779)

Related Publications

Radu, Dan; Cretu, Adrian; Parrein, Benoit; Yi, Jiazi; Avram, Camelia; Astilean, Adina

Flying Ad Hoc Network for Emergency Applications Connected to a Fog System Proceedings Article

In: Barolli, Leonard; Xhafa, Fatos; Javaid, Nadeem; Spaho, Evjola; Kolici, Vladi (Ed.): pp. 675–686, Springer International Publishing, Cham, 2018, ISBN: 978-3-319-75928-9.