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 LOADng 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:

: . .

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:

: . .

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:

: . .
 
: . .

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:

: . .
 
: . .

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

Desmouceaux, Yoann; Cordero, Juan Antonio; Clausen, Thomas

Reliable B.I.E.R. with Peer Caching Journal Article Forthcoming

Forthcoming.

Abstract | BibTeX

Desmouceaux, Yoann; Clausen, Thomas; Cordero, Juan Antonio; Townsley, Mark W

Reliable Multicast with B.I.E.R. Journal Article Forthcoming

IEEE/KICS Journal of Communications and Networks (JCN), 20 (2), pp. 182-197, Forthcoming.

Abstract | Links | BibTeX

Cordero, Juan Antonio

Multi-Path TCP Performance Evaluation in Dual-Homed (Wired/Wireless) Devices Journal Article

Journal of Network and Computer Applications , 70 , pp. 131-139, 2016, ISSN: 1084-8045.

Abstract | Links | BibTeX

Yi, Jiazi; Clausen, Thomas; Igarashi, Yuichi

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

2013 IEEE Conference on Wireless Sensors, 2013.

Abstract | Links | BibTeX

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

Performance analysis of Trickle as a flooding mechanism Inproceedings

IEEE 15th International Conference on Communication Technology, 2013.

Abstract | Links | BibTeX

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

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

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

Abstract | Links | BibTeX

Herberg, Ulrich; Clausen, Thomas

Study of Multipoint-to-Point and Broadcast Traffic Performance in the 'IPv6 Routing Protocol for Low Power and Lossy Networks' (RPL) Journal Article

Journal of Ambient Intelligence and Humanized Computing, Springer, ISSN 1868-5137, Volume 2, Number 4, 2011, (http://link.springer.com/article/10.1007/s12652-011-0046-2).

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) Inproceedings

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

Abstract | Links | BibTeX

Cordero, Juan Antonio

Link-State Routing Optimization for Compound Autonomous Systems in the Internet PhD Thesis

École polytechnique, 2011.

Abstract | Links | BibTeX

Clausen, Thomas; Herberg, Ulrich

Comparative Study of RPL-Enabled Optimized Broadcast in Wireless Sensor Networks Inproceedings

Proceedings of the 6th International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), 2010.

Abstract | Links | BibTeX

Cordero, Juan Antonio

Adjacency Persistency in OSPF MANET Inproceedings

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

Abstract | Links | BibTeX

Clausen, Thomas; Viennot, Laurent; Olesen, Tue; Larsen, Nikolai

Investigating data broadcast performance in mobile ad-hoc networks Inproceedings

Wireless Personal Multimedia Communications, 2002. The 5th International Symposium on, pp. 786-790 vol.2, 2002, ISSN: 1347-6890.

Abstract | Links | BibTeX

Clausen, Thomas; Jacquet, Philippe; Viennot, Laurent

Investigating the impact of partial topology in proactive MANET routing protocols Inproceedings

Wireless Personal Multimedia Communications, 2002. The 5th International Symposium on, pp. 1374-1378 vol.3, 2002, ISSN: 1347-6890.

Abstract | Links | BibTeX

Clausen, Thomas; Jacquet, Philippe; Viennot, Laurent

Comparative Study of Routing Protocols for Mobile Ad-hoc NETworks Inproceedings

Proceedings of the IFIP MedHocNet, September 2002, Sardinia, Italy, 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 Inproceedings

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

Abstract | Links | BibTeX

Clausen, Thomas; Hansen, Gitte; Christensen, Lars; Behrmann, Gerd

The Optimized Link State Routing Protocol Evaluation through Experiments and Simulation Inproceedings

IN PROCEEDING OF WIRELESS PERSONAL MULTIMEDIA COMMUNICATIONS, IEEE, 2001.

Abstract | Links | BibTeX