LOADng – The Lightweight On-demand Ad hoc Distance vector routing protocol, Next Generation

Introduction

The Lightweight On-demand Ad hoc Distance-vector Routing Protocol – Next Generation (LOADng) is a routing protocol, derived from AODV and extended for use in Mobile Ad hoc NETworks (MANETs) and Low-power and Lossy Networks (LLNs).

The LOADn control messages are carried by way of the Generalized MANET Packet/Message Format (RFC5444). Using the generalized message format, control messages can include TLV (Type-Length-Value) elements, permitting protocol extensions to be easily developed. LOADng supports routing using arbitrary additive metrics, which can be specified as extensions to this protocol.

LOADng has been ratified by ITU-T recommendation “G9903: Narrowband orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks” and has been deployed in G3-PLC Smart Grid.

Basic Route Discovery – Route Requests & Route Replies

As a reactive protocol, the basic operations of LOADng include:

  • generation of Route Requests (RREQs) by a LOADng Router (originator) for discovering a route to a destination,
  • forwarding of such RREQs until they reach the destination LOADng Router,
  • generation of Route Replies (RREPs) upon receipt of an RREQ by the indicated destination, and
  • unicast hop-by-hop forwarding of these RREPs towards the originator.

Figure 1 gives an example of RREQ message flooding. Router S initiates a route discovery to Router D. The RREQ message generated by Router S is retransmitted by other routers and flooded in the network until it reaches the destination router D. All the intermediate routers will set up a “reverse route” to Router S.

Please note that LOADng prohibits the intermediate route reply, i.e., even if the intermediate router has a route to the destination, it MUST NOT reply to the RREQ message, but simply forward the RREQ message.

Figure 1: LOADng Route Request Flooding and Route Installation

Figure 1: LOADng Route Request Flooding and Route Installation

Figure 2 shows how unicast RREP message forwarding works. When the RREQ message reaches the destination router D, D will generate an RREP message. The RREP is unicast to the route discovery originator S following the reverse route established during the RREQ flooding. All the routers receiving the RREP message will establish a “forward route” to Router D.

LOADng - RREP Unicast Forwarding and Route Installation

Figure 2: LOADng Route Reply Unicast Forwarding and Route Installation

Route Maintenance

If a route is detected to be broken, e.g. if forwarding of a data packet to the recorded next hop on the route towards the intended destination is detected to fail, a Route Error (RERR) message is returned to the originator of that data packet to inform the originator about the route breakage.

Protocol Extensions

LOADng specifies a slim core that supports basic point-to-point route establishment that is suitable for common scenarios. To improve the protocol performance in special scenarios, such as data collection or existence of extremely unreliable links, different extensions are developed.

Smart Route Request

In some network types, such as sensor networks, it is common to have sensor-to-root (multipoint-to-point — or MP2P) traffic. While eliminating intermediate RREPs can reduce the size of control message and simplify the protocol process, the side effect of blindly flooding RREQ cannot be ignored in this kind of scenarios.

Smart Route Request is thus proposed to replace intermediate route reply while retaining the loop-freedom nature and security mechanism of LOADng. When Smart Route Request is used, if an intermediate LOADng router has already a routing entry to the destination, it will retransmit the RREQ message to the destination by unicast, instead of multicast. More details about the Smart Route Request can be found at:

Jiazi Yi, Thomas Clausen, Antonin Bas: Smart Route Request for On-demand Route Discovery in Constrained Environments. In: 2012 IEEE International Conference on Wireless Information Technology and Systems, 2012.

Expanding Ring Search

The expanding ring search aims at reducing the flooding area of RREQ messages so as to reduce the message overhead. A router will at first send an RREQ with a reduced TTL (Time-To-Live) — causing the RREQ to not be flooded through the entire network, but only up to a limited distance. If the destination sought receives the RREQ, or an intermediate router has a path to the sought destination, an RREP (possibly intermediate/gratuitous) is generated and a network-wide flooding is avoided. If no RREP is received by the originator in expected delay, another RREQ message is, after a brief delay, generated with increased TTL to eventually cover the entire network. More details about the expanding ring search can be found at:

Antonin Bas, Jiazi Yi, Thomas Clausen: Expanding Ring Search for Route Discovery in LOADng Routing Protocol. In: The 1st International Workshop on Smart Technologies for Energy, Information and Communication, 2012.

Collection Tree Protocol

The point-to-point traffic pattern supported by LOADng matches the basic traffic model of the Internet. However, in many deployments of LLNs, another important traffic pattern, called sensor-to-root, or multipoint-to-point, exists. In such traffic scenarios, there is one or more devices that plays the role as “root” — data sink for all traffic — and where all the other devices in the network communicate with the root. If paths from all the other devices to the root are required, it is more efficient to build a “collection tree” (i.e., a directed graph in which all edges are oriented toward and terminate at one root router) and to discover and maintain the set of point-to-point routes from all other routers to that “root”. The collection tree extension aims at building bi-directional routes between the root router and all other routers. More details about the collection tree extension can be found at:

Jiazi Yi, Thomas Clausen: Collection Tree Extension of Reactive Routing Protocol for Low-Power and Lossy Networks. In: Hindawi International Journal of Distributed Sensor Networks, vol. 2014, no. Article ID 352421, pp. 12, 2014.
 
Jiazi Yi, Thomas Clausen, Axel Colin de Verdiere: Efficient Data Acquisition in Sensor Networks:Introducing (the) LOADng Collection Tree Protocol. In: IEEE WiCom 2012, The 8th IEEE International Conference on Wireless Communications, Networking and Mobile Computing., 2012.

Depth First Forwarding

Depth-First Forwarding in Unreliable Networks (DFF) is an experimental data forwarding standard by the IETF, which proposes a mechanism for rapid and localized recovery in case of link failure. Colloquially speaking, if a device fails in its attempt to forward a packet to its intended next-hop, then DFF suggests a heuristics for “trying another of that devices’ neighbors”, while keeping track of (and preventing) packet loops.

LOADng is extended to support DFF by adding neighbor discovery mechanisms using HELLO messages. The simulation results show that the DFF could effectively increase the packet delivery ratio at the cost of increasing end-to-end delay and longer path length. More details can be found at:

Jiazi Yi, Thomas Clausen, Ulrich Herberg: Depth First Forwarding for Low Power and Lossy Networks: Application and Extension. In: Proceedings of IEEE World Forum on Internet of Things WF-IoT 2014, 2014.
 
Thomas Clausen, Jiazi Yi, Antonin Bas, Ulrich Herberg: A Depth First Forwarding (DFF) Extension for the LOADng Routing Protocol. In: ASON 2013 Sixth International Workshop on Autonomous Self-Organizing Networks, 2013.

Interoperability Tests

Five interoperability test events have been organised to improve the protocol specification and verify that interoperable implementations can be developed based on the document. A detailed interop report can be found at Interoperability Report for the Lightweight On-demand Ad hoc Distance-vector Routing Protocol – Next Generation (LOADng).

  • Interop 01: The first LOADng interoperability test event was held at Hitachi YRL in Yokohama, Japan, from October 17th to October 19th, 2011. The interoperability tests were conducted according to the specification in LOADng-00. Ecole Polytechnique, Hitachi YRL and EDF R&D participated in the tests. Three implementations (1 from Ecole Polytechnique and 2 from Hitachi YRL) were tested.
  • Interop 02: The second LOADng interoperability test event was held at Fujitsu Laboratories of America (FLA), San Jose, USA, on April 13th, 2012. The interoperability tests were conducted according to the specification in LOADng-03. Ecole Polytechnique and Fujitsu Lab of America (FLA) participated in the tests. Two implementations (1 from Ecole Polytechnique and 1 from Fujitsu FLA) were tested.
  • Interop 03: The third LOADng interoperability test event was performed at the Los Angeles Airport Hilton, USA, on June 6th, 2012.  The interoperability tests were conducted according to the specification in LOADng-04. Ecole Polytechnique and Fujitsu Lab of America (FLA) participated in the tests. Two implementations: 1 from Ecole Polytechnique and 1 from Fujitsu FLA were tested.
  • Interop 04: The fourth LOADng interoperability test event was held at Hyatt Hotel, Vancouver, August 2nd, 2012. The interoperability tests were conducted according to the specification in LOADng-05. Ecole Polytechnique and Fujitsu Lab of America (FLA) participated in the tests. Two implementations (1 from Ecole Polytechnique and 1 from Fujitsu FLA) were tested.
  • Interop 05: The fifth LOADng interoperability test even was performed at Sagemcom Rueil-Malmaison, France from August 2nd to August 5th, 2016. Ecole Polytechnique, Sagemcom and Nexans participated in the tests. Two implementations (1 from Sagemcom and 1 from Nexans) were tested. The LOADng protocol tested was based on specification “G3-PLC over Medium Voltage Lines: Implementation Guidelines“.

A World-Wide Community

  • Initiated by an industrial need, satisfied by us, used world-wode
  • Links to known implementations
  • Link to ITU standard

Related Publications

Clausen, Thomas; YI, Jiazi; Cordero, Juan Antonio; Igarashi, Yuichi

Use 'em or Lose 'em: On Unidirectional Links in Reactive Routing Protocols Journal Article

In: Elsevier Ad Hoc Networks, vol. 73, pp. 51-64, 2018.

Abstract | Links | BibTeX

Clausen, Thomas; Yi, Jiazi; Herberg, Ulrich

Lightweight On-demand Ad hoc Distance-vector Routing-Next Generation (LOADng): Protocol, Extension, and Applicability Journal Article

In: Computer Networks, vol. 126, pp. 125-140, 2017.

Abstract | Links | BibTeX

Yi, Jiazi; Clausen, Thomas; Herberg, Ulrich

Depth-First Forwarding for Unreliable Networks: Extensions and Application Journal Article

In: IEEE Internet of Things Journal, vol. 2015, no. 06, 2015.

Abstract | Links | BibTeX

Yi, Jiazi; Clausen, Thomas

Collection Tree Extension of Reactive Routing Protocol for Low-Power and Lossy Networks Journal Article

In: Hindawi International Journal of Distributed Sensor Networks, vol. 2014, no. Article ID 352421, pp. 12, 2014.

Abstract | Links | BibTeX

Yi, Jiazi; Clausen, Thomas; Herberg, Ulrich

Depth First Forwarding for Low Power and Lossy Networks: Application and Extension Proceedings Article

In: Proceedings of IEEE World Forum on Internet of Things WF-IoT 2014, 2014.

Abstract | Links | BibTeX

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

An Adaptive Jitter Mechanism for Reactive Route Discovery in Sensor Networks Journal Article

In: Sensors, vol. 14, no. 8, pp. 14440, 2014, ISSN: 1424-8220, (http://www.mdpi.com/1424-8220/14/8/14440).

Abstract | Links | BibTeX

Clausen, Thomas; Yi, Jiazi

Path Accumulation Extensions for the LOADng Routing Protocol in Sensor Networks Proceedings Article

In: Hsu, RobertC. -H.; Wang, Shangguang (Ed.): Internet of Vehicles – Technologies and Services, pp. 150-159, Springer International Publishing, 2014, ISBN: 978-3-319-11166-7.

Abstract | Links | BibTeX

Clausen, Thomas; Yi, Jiazi; Bas, Antonin; Herberg, Ulrich

A Depth First Forwarding (DFF) Extension for the LOADng Routing Protocol Proceedings Article

In: ASON 2013 Sixth International Workshop on Autonomous Self-Organizing Networks, 2013.

Abstract | Links | BibTeX

Yi, Jiazi; Clausen, Thomas; Igarashi, Yuichi

Evaluation of Routing Protocol for Low Power and Lossy Networks: LOADng and RPL Proceedings Article

In: 2013 IEEE Conference on Wireless Sensors, 2013.

Abstract | Links | BibTeX

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

Jitter Considerations in On-demand Route Discovery for Mobile Ad Hoc Networks Proceedings Article

In: The 16th International Conference on Network-Based Information Systems (NBiS-2013), 2013.

Abstract | Links | BibTeX

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; Yi, Jiazi; Clausen, Thomas

Optimization of jitter configuration for reactive route discovery in wireless mesh networks Proceedings Article

In: Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt), 2013 11th International Symposium on, 2013, ISBN: 978-1-61284-824-2.

Abstract | Links | BibTeX

Yi, Jiazi; Clausen, Thomas; Bas, Antonin

Smart Route Request for On-demand Route Discovery in Constrained Environments Proceedings Article

In: 2012 IEEE International Conference on Wireless Information Technology and Systems, 2012.

Abstract | Links | BibTeX

Bas, Antonin; Yi, Jiazi; Clausen, Thomas

Expanding Ring Search for Route Discovery in LOADng Routing Protocol Proceedings Article

In: The 1st International Workshop on Smart Technologies for Energy, Information and Communication, 2012.

Abstract | Links | BibTeX

Yi, Jiazi; Clausen, Thomas; de Verdiere, Axel Colin

Efficient Data Acquisition in Sensor Networks:Introducing (the) LOADng Collection Tree Protocol Proceedings Article

In: IEEE WiCom 2012, The 8th IEEE International Conference on Wireless Communications, Networking and Mobile Computing., 2012.

Abstract | Links | BibTeX

Clausen, Thomas; Yi, Jiazi; de Verdiere, Axel Colin

LOADng: Towards AODV Version 2 Proceedings Article

In: 2012 IEEE 76th Vehicular Technology Conference, 2012.

Abstract | Links | BibTeX

Herberg, Ulrich; Clausen, Thomas

A Comparative Performance Study of the Routing Protocols LOAD and RPL with Bi-Directional Traffic in Low-power and Lossy Networks (LLN) Proceedings Article

In: Proceedings of the Eighth ACM International Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN), 2011.

Abstract | Links | BibTeX

Clausen, Thomas; Jacquet, Philippe; Viennot, Laurent

Optimizing Route Length in Reactive Protocols for Ad Hoc Networks Proceedings Article

In: In Proceeding of The First Annual Mediterranean Ad Hoc Networking Workshop., 2002.

Abstract | Links | BibTeX

Viennot, Laurent; Jacquet, Philippe; Clausen, Thomas

Analyzing Control Traffic Overhead in Mobile Ad-hoc Network Protocols versus Mobility and Data Traffic Activity Proceedings Article

In: In Proceedings of the 1st IFIP Annual Mediterranean Ad Hoc Networking Workshop (MedHocNet’02, 2002.

Abstract | Links | BibTeX

Leave a Reply

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