Jiazi Yi

Thomas Clausen

Yuichi Igarashi
email: yuichi.igarashi.hb@hitachi.com

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

Routing protocol is a critical component of Lowpower and Lossy Networks for Smart Grid. The protocols are used for data forwarding, which includes data acquisition, information dissemination, etc. This paper evaluates two main routing protocols used for Low-power and Lossy Networks: RPL and LOADng, to understand their strengths and limitations. Observations are provided based on analysis of specification and experimental experience, regarding the protocol's routing overhead, traffic pattern, resource requirement, fragmentation, etc. Simulations are further launched to study the performance in different traffic patterns, which include sensor-to-sensor traffic, sensor-to-root traffic and root-to-sensor bidirectional traffic. By evaluating those protocols, the readers could have better understanding of the protocol applicability, and choose the appropriate protocol for desired applications.

I. INTRODUCTION

Advanced Metering Infrastructure (AMI) systems and Smart-Meter networks enable measurement, collection and analysis of energy usage, by way of facilitating fine-grained communication between energy production/distribution entities, and metering (and consumption) entities, represented by electricity meters, heat meters, water meters, gas meters.

A. Background and History

Since the late 90s, the IETF (The Internet Engeering Task Force) has embarked upon a path of developing routing protocols for networks with increasingly more fragile and lowcapacity links, with less pre-determined connectivity properties and with increasingly constrained router resources. In '97, by chartering the Mobile Ad hoc NETwork (MANET) working group, then subsequently in 2006 and 2008 by chartering the 6LowPAN (IPv6 over Low power WPAN) and ROLL (Routing Over Low power and Lossy networks) working groups.

1) MANET Protocol Developments: The MANET working group, which aims at standardizing IP routing protocol for ad hoc networks, converged on the development of two protocol families: reactive protocols, including AODV (Ad hoc Ondemand Distance Vector Routing) [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], and proactive protocols, including Optimized Link State Routing (OLSR) [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF].

After acquiring operational experiences, the MANET working group commenced developing successors to OLSR and AODV, denoted OLSRv2 and DYMO (Dynamic MANET On-demand Routing). Whereas a relatively large and active community around OLSR thus standardized OLSRv2 [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], the momentum behind DYMO withered in the MANET working group 1 .

2) 6LowPAN and ROLL Protocol Developments: The 6LowPAN working group was chartered for adapting IPv6 for operation over IEEE 802.15.4, accommodating characteristics of that MAC layer, and with a careful eye on resource constrained devices (memory, CPU, energy, ...). Part of the original charter for this working group was to develop protocols for routing in multi-hop topologies under such constrained conditions, and over this particular MAC. Several proposals for routing were presented in 6LowPAN, for each of these philosophies, including LOAD (6LoWPAN Ad Hoc Ondemand Distance Vector Routing) [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF]. LOAD was a derivative of AODV, but adapted for L2-addresses and mesh-under routing, and with some simplifications over AODV (e.g., removal of intermediate node replies and sequence numbers). However, 6LowPAN was addressing other issues regarding adapting IPv6 for IEEE 802.15.4, such as IP packet header compression, and solving the routing issues was suspended, delegated to a working group ROLL, created in 2008 for this purpose. ROLL produced a routing protocol denoted "Routing Protocol for Low-power lossy networks" (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] in 2012.

3) Towards LOADng: While LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] development was suspended by the 6LowPAN working group, pending the results from ROLL and experiences with RPL, AODV derivatives live on: IEEE 802.11s [START_REF] Hiertz | Principles of ieee 802.11s[END_REF] is based on AODV, and the G3-PLC (Power Link Communication) standard [START_REF] Itu-T G | Narrow-Band OFDM power line communication transceivers -Data link layer specification[END_REF], published in 2011, specifies the use of [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] at the MAC layer, for providing mesh-under routing for utility (electricity) metering networks. Justifications for using an AODV derivative in preference to RPL include that the former better supports bi-directional data flows such as a request/reply of a meter reading [START_REF] Herberg | A comparative performance study of the routing protocols load and rpl with bi-directional traffic in low-power and lossy networks (lln)[END_REF], as well as algorithmic and code complexity reasons [START_REF] Clausen | A critical evaluation of the "ipv6 routing protocol for low power and lossy networks[END_REF].

In November 2012, ITU G3-PLC Alliance approved unanimously to supersede LOAD, the routing algorithm described in the recommendation ITU-T G.9903, with Lightweight Ondemand Ad hoc Distance-vector Routing (LOADng). Resulting from this decision, ITU-T has ratified the recommendation ITU-T G.9903 Amendment 1 in May 2013 [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF] which includes LOADng in a specific normative annex.

B. Statement of Purpose

This paper evaluates the two routing protocols, LOADng and RPL -two of the major protocols that are standardized and to be used in AMI networks. Their applicability, strength and limitations are illustrated. The following aspects are specially studied, which are also of the great concerns of LLNs in constrained environments:

• The number of routing protocol messages used to maintain the routing tables; this is one important factor in energy consumption, and a lover routing protocol overhead is thus beneficial to prolong the network lifetime. • Support for different kinds of traffic patterns, which include sensor-to-root (multipoint-to-point) traffic, root-tosensor (point-to-multipoint) traffic, and sensor-to-sensor (point-to-point) traffic [START_REF] Martocci | Building Automation Routing Requirements in Low-Power and Lossy Networks[END_REF].

• Support of bi-directional routes. Some application traffic in AMI networks is bi-directional (e.g.,requiring a message exchange between two nodes in the network, typically between the controller and a meter). Furthermore, some upper-layer protocols, not specifically conceived for AMI but for LLNs in general, require acknowledgement message. For example, CoAP (Constrained Application Protocol) proposed by IETF [START_REF] Shelby | Constrained Application Protocol (CoAP)[END_REF] and DLMS/COSEM (Device Language Message specification / COmpanion Specification for Energy Metering) [START_REF]Electricity metering -Data exchange for mter reading, tariff and load control -Part 53: COSEM application layer[END_REF] both supports request/response type application. • Length of the paths discovered by routing protocols. The routing protocol is expected to obtain optimal paths (the shortest one according to link metric used). • Likelyhood of packet fragmentation. In LLNs, the layer 2 frame size is often limited -e.g.,for IEEE 802.15.4, the maximum frame size is 127 octets. This requires not only small message size for routing control messages, but also low overhead in the data packet to reduce the risk of packet fragmentation.

[15] provides initial simulation results on the performance of RPL and LOADng, in a centralized architecture (communication related to the root) and home automation scenarios (less than 50 nodes). However, the traffic patterns, as well as size of the network tested are still limited, and some of the concerns listed above are not addressed.

Based on the previous efforts and experiences, this paper provides some general observations of RPL and LOADng, and evaluates the performance of the two routing protocols in different traffic patterns, and large scale simulation scenarios (up to 500 nodes).

C. Paper Outline

The remainder of this paper is organized as follows. Section II presents a selection of observations of RPL and LOADng, to understand their properties and characteristics when being used in LLNs. In section III, simulations are performed to study the performance of the routing protocols with different traffic patterns. Section IV concludes this paper .

II. RPL AND LOADNG: OBSERVATION

In section I-B, some basic requirements to AMI routing protocols were listed. This section presents an analysis of RPL and LOADng with respect to these requirements. The analysis and observations are based on the protocol specifications, and will -as far as possible -be verified by the performance study in presented in section III.

A. RPL Observations

RPL is a proactive distance-vector protocol. The basic construct in RPL is a Destination Oriented Directed Acyclic Graph (DODAG), with a single RPL Route acting as DODAG root. The DODAG Root has responsibilities in addition to those of other RPL Routers, including initiating, configuring, and managing the DODAG, and (in some cases) acting as a central relay for traffic through and between other RPL Routers in the network. The DODAG is constructed by generation and transmission of DIO (DODAG Information Object) message, indicating the router's rank in the DODAG. Thus, RPL provides "upward" or "multipoint-to-point" routes from sensors inside the network towards the DODAG root. "Downward routes" are enabled by having sensors issue Destination Advertisement Object (DAO) messages, propagating as unicast via preferred parents towards the DODAG Root. "Point-topoint routes", for communication between devices inside the network and where neither of the communicating devices are the DODAG Root, are as default supported by having the source sensor transmit a data packet, via its default route to the DODAG Root (i.e.,using the upward routes), which will then, depending on the "Mode of Operation" for the DODAG, either add a source-route to the received data packet for reaching the destination sensor (downward routes in non-storing mode), or simply use hop-by-hop routing (downward routes in storing mode) for forwarding the data packet.

1) Data traffic flow assumption: RPL makes a-priori assumptions of data traffic types, and explicitly defines three such traffic types: sensor-to-root data traffic (multipoint-topoint, MP2P) is predominant, root-to-sensor data traffic (pointto-multipoint, P2MP) is rare and sensor-to-sensor (point-topoint, P2P) data traffic is extremely rare. While not specifically called out thus in the RPL specification [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF], the resulting protocol design, however, reflects these assumptions in that the mechanism constructing MP2P routes is efficient in terms of control traffic generated and state required, P2MP route construction much less so -and P2P routes subject to potentially significant route stretch (routes going through the DODAG Root in non-storing mode) and over-the-wire overhead from using source routing (from the DODAG Root to the destination) -or, in case of storing mode, considerable memory requirements in all routers also inside the network.

In real applications, there are scenarios where P2P traffic is a common occurrence. For example, in the remote control in building automation, more than 30% percent of traffic can be P2P [START_REF] Martocci | Building Automation Routing Requirements in Low-Power and Lossy Networks[END_REF]. This can cause more network congestion and energy consumption by using RPL.

2) DODAG root requirement: When the Internet was designed, it was with the principle of avoiding a single-pointof-failure: even if one or several routers cease operation, the other routers in the network should be able to make the global network continue to function.

In RPL, the DODAG Root has both a special responsibility and is subject to special requirements. The DODAG Root is responsible for determining and maintaining the configuration parameters for the DODAG, and for initiating DIO emissions. The DODAG Root is also responsible (in both storing and non-storing mode) for being able to, when downward routes are supported, maintain sufficient topological information to be able to construct routes to all destinations in the network.

Although in principle, RPL provides "Floating DODAGs" to provide internal connectivity in case the administratively provisioned DODAG fails, because of the special memory/function requirement of DODAG root, the other routers in the network either may not have enough resources to act as DODAG roots -or, will all have to be provisioned with ressources sufficient to act as DODAG root (ressources which will be unusued during normal network operation). Therefore, the DODAG root represents a potential single-point-of-failure in an RPL routed network.

3) Fragmentation: It is desired that applications in an AMI network originate small packets, in order to avoid linklayer fragmentation [START_REF] Kushalnagar | 6LoWPANs: Overview, Assumptions, Problem Statement, and Goals[END_REF]. In 802.15.4 [START_REF][END_REF] the frame size is only 127 octets, of which up to 25 octets may be used for frame overhead, and another 21 octets for link layer security, leaving 81 octets for layer-2 payload. When using the IPv6 compression mechanism supplied by the compressed IPv6 header consumes (at least)2 octets [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], leaving (at best) 79 octets for layer 3 data payload -such as routing protocol signals and application data -before fragmentation occurs.

While 79 octets may seem sufficient to carry RPL control messages, consider the following: RPL control messages are carried in ICMPv6, and the mandatory ICMPv6 header consumes 4 octets. The DIO base object of RPL consumes another 24 octets. If link metrics are used, that consumes at least another 8 octets -and this, when using a simple hop count metric; other metrics may require more. The DODAG Configuration Object consumes up to a further 16 octets, for a total of 52 octets. Adding a Prefix Information Object for address configuration consumes another 32 octets, for a total of 84 octets, thus exceeding the 79 octets available for layer 3 data payload and causing link-layer fragmentation of such a DIO.

For data traffic, RPL may further increase the probability of fragmentation in downward traffic for storing mode, due to the use of source-routing: for each data packet a fixed source routing ovehead of 8 octets is imposed, plus a variable number of octets for entries in the source route -the exact number of octets depending on the address length and number hops to be traversed. This would reduce the already limited space available for data payload, and increase the risk of fragmentation. Of further note is, that the DODAG root adding a source routing header means that applications cannot know in advance what to expect of the MTU, and thus applications cannot properly design their data traffic to "fit" within an unfragmented frame.

4) Link Bi-directionality: When a DODAG is constructed by RPL, parents (and the preferred parent) are selected based on receipt of DIOs. This, alone, does not guarantee the ability of an RPL Router to successfully communicate with the parent. However, the basic use of links is for "upward" routes, i.e., for the RPL Router to use a parent (the preferred parent) as relay towards the DODAG Root -in the opposite direction of the one in which the DIO was received.

In fact, unidirectional links are no rare occurrence in wireless networks. Although "RPL operations requires bidirectional links" [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF], RPL does not specify exactly what mechanisms should be used, and how they should be used to avoid unidirectional links. There are some solutions mentioned in [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF], such as Bidirectional Forwarding Detection (BFD) or Neighbor Unreachability Detection (NUD).

BFD is explicitly called out as "often not desirable" as it uses a proactive approach, and is not considered (by RPL) as adapted to LLNs. For NUD, it is only invoked when a transmission fails. An RPL Router may detect that its preferred parent is lost by way of NUD, when trying to communicate to the DODAG Root. If that RPL Router has no other parents in its parent set, all it can do is wait: RPL does not provide other mechanisms for an RPL Router to react to such an event. Therefore, RPL adopts neither those mechanisms, and does not specify an alternative mechanism.

5) Loops: RPL "guarantees neither loop free route selection nor tight delay convergence times, but can detect and repair a loop as soon as it is used. RPL uses this loop detection to ensure that packets make forward progress [...] and trigger repairs when necessary" [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. This implies that a loop may only be detected and fixed when data traffic is sent through the network. When a loop is detected and route repair is triggered, data packets have to be buffered. However, with limited memory constraints of LLNs, buffering incoming packets during the route repair may not be possible for all incoming data packets, leading to dropped packets. Depending on the transport protocol, these data packets must be retransmitted by the source (increasing the network load) or be definitely lost.

B. LOADng Observations

LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] is derived from AODV. It includes a core specification and different extensions to improve the performance in specific scenarios (e.g.,collection trees for more efficient data acquisition [START_REF] Yi | Efficient data acquisition in sensor networks:introducing (the) loadng collection tree protocol[END_REF], smart route request [START_REF] Yi | Smart route request for on-demand route discovery in constrained environments[END_REF] and expanding ring search [START_REF] Bas | Expanding ring search for route discovery in loadng routing protocol[END_REF] to reduce overhead). As a reactive protocol, the basic operations of LOADng include generation of Route Requests (RREQs) by a LOADng Router (originator) for when 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.

1) Data traffic flow assumption: LOADng makes no assumption of data traffic type used with the protocol, but provides a general point-to-point mechanism, which is more close to the typical Internet architecture: in the Internet, no single router acts as relay for all traffic. To have more efficient performance when subject to other traffic patterns, such as data acquisition or broadcast, this is supported by way of the protocol being extensible (in a backwards/forward compatible fashion).

2) No Root -No Requirements: No router in a LOADng network plays any special role. All routers exhibit the same behavior (signaling and processing). Even when using a collection tree extension, while there exits a conceptual "root", the router which acts as that conceptual "root" has no additional signaling or processing requirements when compared to other routers in the network.

3) Fragmentation: To reduce the overhead of routing control messages, LOADng makes use of a generalized message format, specially designed for ad hoc networks [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF]. It can not only reduce the overall size of the control packets generated by LOADng, but also permits protocol extensions to be developed. Additionally, by being frugal in included information in LOADng control messages, a typical LOADng control message size is around 30 octets (depending on the length of address used), which easily fits into a single 802.15.4 frame.

For data traffic, LOADng does not require routing-related information (such as a source routing header, or fields to indicate the "direction" of the packet) to be added to the IP header. Thus applications can properly and predictably design their data traffic to "fit" within an unfragmented frame.

4) Link Bi-directionality: LOADng is designed to work in networks wherein uni-directional links occur. In the core specification of LOADng, a bi-directionality check is performed by using "blacklist". When a Route Reply message is sent by a LOADng router, by default, it is expecting a Route Reply Acknowledgment message. If the acknowledgement is not received on time, the "next hop" of this Route Reply is blacklisted, and is not supposed to join the route in a subsequent route discovery process. By doing so, only bidirectional links are used for forwarding data packets in LOADng.

5) Loops: The routing messages in LOADng like Route Request and Route Reply generated by a given LOADng Router share a single unique, monotonically increasing sequence number. Meanwhile, only destination is permitted to respond to a Route Request, which ensures loop freedom.

Table I summarizes the general features of RPL and LOADng.

III. LOADNG AND RPL: PERFORMANCE EVALUATION

This section presents the simulation results for LOADng and RPL (non-storing mode) performance evaluation. Different traffic patterns, including P2P, MP2P, P2MP are studied.

A. Simulation Setup

Simulations were made with varying numbers of routers from 63 to 500, equipped with IEEE 802.11 wireless interfaces. Note that it is not suggested that IEEE 802.11 be used for LLNs, but the general behavior of routing protocols (notably, observing frame sizes, path-lengths, control signal counts etc) can be concluded from simulations using IEEE 802.11. Routers were placed statically uniformly in a square field while maintaining a consistent network density, i.e.,the simulation field grows as the number of routers increases: 1100m×1100m for 63 nodes, 1580m×1580m for 125 nodes, 2230m×2230m for 250 nodes, 3160m×3160m for 500 nodes. Each CBR (Constant Data Rate) traffic emits a data packet with 512 bytes every 5 seconds. For each datapoint, the values have been averaged over 10 runs.

RPL is used in non-storing mode. The reason that storing mode is not tested is because each RPL Router has to store routes for destinations in its sub-DODAG. With constrained memory of LLN devices, it is hard to scale in storing mode. In an experimental testbed, [START_REF] Ko | Evaluating the performance of rpl and 6lowpan in tinyos[END_REF] argues that the network should be limited to 30 routers in RPL storing mode.

B. Simulation Results

1) Point-to-point scenarios: Figure 1 gives the performance of LOADng and RPL in a P2P scenario with 30 concurrent CBR traffic flows. Every CBR traffic flow is originated from a random device (except the root) in the network, to another random device (except the root) in the network. In this scenario, LOADng exhibits a significantly lower overhead, compared to RPL. This is mainly due to the re-active nature of LOADng: the route discovery is initiated only when there is a data packet to be delivered. For RPL, which is a pro-active protocol, control packet transmissions always exist to maintain a routing table to every possible destinations in the network, even there is no data traffic in the network. For those same reasons, LOADng presents slightly higher delay than RPL.

Figure 1(c) illustrates the average path length of the routes discovered by the two protocols. In P2P scenarios, all the data traffic in RPL non-storing mode need to travel through the root (except the destination happens to be somewhere on the route to the root), which results in that the paths offered by RPL are about 60% longer than those offered by LOADng. Because of unnecessary path stretch and higher overhead, RPL has higher loss rate in larger scale scenarios (500 nodes). 2) Multipoint-to-point Scenarios: In MP2P scenarios, there is a single root in the network, to which all other devices in the network send data packets, i.e.,there are n -1 CBR traffics in the network, where n is the number of devices. Three protocol settings are simulated in MP2P scenarios:

• RPL: RFC 6550 [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] with only DIO message enabled;

• LOADng: the LOADng core specification [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF];

• LOADng-CTP: LOADng with collection tree extension [START_REF] Yi | Efficient data acquisition in sensor networks:introducing (the) loadng collection tree protocol[END_REF]. LOADng-CTP is an extension module specially designed for LOADng, and which is compatible with the LOADng core specification.

The performance of different settings is shown in Figure 2. LOADng has the highest overhead because it needs to initiate a route discovery for every route to the root. However, with the collection tree extension, LOADng-CTP greatly reduces the overhead, even when compared to RPL.

3) P2MP and bi-direction scenarios: This scenario simulates a bi-directional "polling application" is simulated, where the root collects information from all devices in the network within in 24 hours -a fairly typical real-world application, say, when a power company needing to inquire all power meters on the last day of each month. The root sends a single request with one data packet (11 octets payload) to each sensor, and the sensor replies with a single data packet (100 octets payload).

The simulated time was 25 hours for LOADng and 270 seconds for RPL. The reason for not choosing 24 hours for RPL as well, is quite simply the required amount of time that would be required for conducting the simulation: as DAO messages are sent periodically 2 in the simulation (5 seconds per packet), even if no data traffic is present in the network, the required amount of time to conduct the simulation would have been several days for a single simulation run, and trace files would grow to hundreds of Gigabytes per simulation. As in LOADng no control traffic is sent when no data traffic is sent, the simulation runs considerably faster, allowing to simulate the 24 hours interval. Despite this difference of simulation time, the results are comparable, as the transmitted data traffic stays the same (0.1 seconds per data request for RPL, and 30 seconds per data request for LOADng). The control traffic overhead of RPL can be extrapolated from 270s to 1 day, as 2 One might argue that sending DAOs periodically is not smart, and that this should not be done. Unfortunately, the RPL specification does not indicate any schedule or events, indicating when DAOs are to be sent. DAO messages are sent periodically.

Figure 3 gives the simulation results of P2MP bi-directional scenarios. It can be concluded from 3(b) that even when RPL only runs for only 270s, it generates a higher overhead than does LOADng. Since the simulation time was much lower for RPL, and DAOs are sent periodically, the expected amount of control traffic for a duration of 1 day can be easily extrapolated, where the overhead of RPL is two orders of magnitude higher than the overhead of LOADng.

Figure 3(d) gives the delay of the two protocols. For LOADng downward traffic, because LOADng needs to wait for the route discovery process before sending out the data traffic, it presents a higher delay than does RPL, as well as a higher delay than LOADng presents for upward traffic. However, for most LLN scenarios where delay is not a crucial issue, this may be acceptable.

IV. CONCLUSION

This paper has evaluated RPL and LOADng, both routing protocols for LLNs, for their applicability also for AMI networks. Based on specification analysis, experimental experience and simulation studies of typical traffic patterns for AMI networks, the strengths and limitations of the two protocols have been explored.

RPL is a proactive protocol, and is optimized for sensorto-root (MP2P) communication, in which case it provides low delay (if no loop occurs). However, RPL also presents several limitations. First, because the protocol is designed with an implicit assumption of MP2P being the predominant traffic pattern, it is not efficient for root-to-sensor (P2MP) traffic, and not appropriate for sensor-to-sensor (P2P) traffic. Indeed, the control signals (DAOs) for supporting P2MP and P2P traffic appears an "afterthought" by way of their emission schedule being unspecified in the RPL specification. Secondly, RPL imposes a special requirement on the root node in the network, which makes it a potential single-point-of-failure, a bottle-neck for traffic, and causes systemic route stretch for P2P traffic. Thirdly, there is a high likelihood of fragmentation and loops when packets are routed by RPL. Finally, because RPL is lack link bi-directionality check mechanisms, it is not appropriate for networks with uni-directional links.

LOADng supports more general traffic patterns, making no a-priori assumptions. Therefore, no node plays a "special role" in the network, from the point of view of the routing protocol. LOADng provides a compressed and flexible packet format, with no risk of control packet fragmentation, and also does not impose source routing (or other signals) in data packets, providing applications with a known, fixed MTU -allowing applications to design their data packets to "fit" within a single frame. Also, LOADng offers loop-free routes, and supports networks with uni-directional links. As a reactive protocol, LOADng has possible higher delay in the route discovery phase, and presents higher overhead if there are too many concurrent P2P traffic flows in the network.

Figure 1 .

 1 Figure 1. Simulation results of P2P scenarios, 30 CBR sources

Figure 3 .

 3 Figure 2. Simulation results of MP2P scenarios

http://tools.ietf.org/wg/manet/minutes?item=minutes81.html


Thomas Clausen
email: thomas@thomasclausen.org

Jiazi Yi

Antonin Bas
email: antonin.bas@polytechnique.edu

Ulrich Herberg
email: ulrich@herberg.name

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

This paper explores the cooperation between the new standards for "Low Power and Lossy Networks" (LLNs): IETF RFC 6971, denoted "Depth-First Forwarding in Unreliable Networks" (DFF) and the ITU-T standardised routing protocol "LOADng" (Lightweight On-demand ad hoc Distance-vector Routing -next generation). DFF is a data-forwarding mechanism for increasing reliability of data delivery in networks with dynamic topology and lossy links, using a mechanism similar to a "depth-first search" for the destination of a packet. LOADng is a reactive on-demand routing protocol used in LLNs. The purpose of this study is to evaluate the benefit of using DFF conjointly with a routing protocol. To this end, the paper compares the performance of LOADng and LOADng+DFF using Ns2 simulations, showing a 20% end-to-end data delivery ratio increase at expense of expected longer path lengths.

I. INTRODUCTION

Low-power and Lossy Networks (LLNs) are composed of devices with strictly limited computational power and storage (1-2MHz CPUs and a couple of KB of memory), communicating over a channel characterised by a high risk of packet losses, (typically) very small frame sizes, and very limited throughput. Transiting data across such a network, especially when multiple hops are present between the source and the destination, is a challenging task: routing protocols finding paths must be frugal in their control traffic and state requirements, as well as in algorithmic complexity -and even once paths have been found, these may be usable only intermittently (e.g., not all packet gets through successfully) or for a very short time due to changes on the channel such as persistent interference (requiring rediscovery of an usable path). Channel failures, resulting in link failures in a routing path can result from a variety of factors such as heterogeneity of sender and receiver hardware, power supply or power control algorithms (leading to different transmission ranges, unidirectional links, or simply that devices are power-cycled asynchronously), the presence of noise or interferences, or even device failure causing a previously selected intermediary router to no longer be available.

The limitations of the devices and the channel capacity in LLNs suggest a routing protocol of extreme simplicity -yet the fragility and transient nature of links suggest the requirement to be able to quickly discover and establish alternative paths when faced with a link failure. These requirements are, seemingly, contradictory. A "standard" proactive routing protocol, such as OSPF (Open Shortest Path First) [START_REF] Moy | OSPF Version 2[END_REF] or OLSR (Optimized Link State Routing) [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF], maintaining a network topology graph would remove a "broken" link from its graph and re-run a shortest path algorithm -incurring the requirement of each routing device being able to store (up to) the complete network topology, as well as being able to re-run the shortest path algorithm on a whim. A "standard" ondemand routing protocol would in the similar situation incur route re-discovery, with additional (flooded) control signals being imposed on the network, as well as additional delays on data packet delivery whilst route re-discovery is ongoing, and either buffering of data packets for that duration or retransmission once a path has been re-discovered.

Different proposed and standardised routing protocols for LLN exist, including RPL (Routing Protocol for Low-power and lossy networks) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] and LOADng (Lightweight Ondemand Ad hoc Distance-vector Routing Protocol -Next Generation) [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF], making different trade-offs and being of different philosophies -yet being united in the fact that when a link, used actively as part of a routing path, fails, then it is up to the routing protocol to recover by discovering alternative paths, with data traffic being either buffered or dropped for the duration of this recovery.

"Depth-First Forwarding in Unreliable Networks" (DFF) [START_REF] Herberg | Depth-First Forwarding (DFF) in Unreliable Networks[END_REF] is an experimental standard which proposes a mechanism for 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 neighbours", while keeping track of (and preventing) packet loops. Thus, DFF operates on the "forwarding plane". While DFF can operate independently, i.e., without a routing protocol (which amounts to simply doing a depth-first exploration of the network), it can also be used conjointly with a routing protocol: the routing protocol can provide an "order of priority" of the neighbours of a device, in which data delivery should be attempted -and DFF can also signal to a routing protocol when data delivery to a destination has (possibly repeatedly) failed via a neighbour but (possibly repeatedly) succeeded via another neighbour.

A. Statement of Purpose

This paper explores the cooperation between DFF and the routing protocol LOADng [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF], with the purpose of uncovering the benefit of using DFF conjointly with a routing protocol. To this end, the paper compares the performance of LOADng and LOADng+DFF. RPL is not further studied in this paper due to the fact that the predominant mode of operation of RPL ("nonstoring mode" [START_REF] Clausen | Observations of RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]) employs source routing -which lends itself poorly1 to on-the-path autonomous routing decisions causing deviations from the established source route and, as such, is incompatible with DFF.

B. Paper Outline

The remainder of this paper is organized as follows: section II briefly describes the routing protocol LOADng, and section III presents an overview of DFF. Section IV outlines how LOADng and DFF are integrated -how the routing protocol provides information for DFF's forwarding decisions, as well as how DFF signals to the routing protocol. It should be noted that there are many different possible ways in which LOADng and DFF (or, indeed, any routing protocol and DFF) can be integrated, and this section outlines only the one studied in this paper. Section V presents a performance evaluation of LOADng with and without DFF. Finally, section VI concludes this paper.

II. LOADNG

LOADng [START_REF] Clausen | LOADng: Towards AODV Version 2[END_REF], [START_REF] Clausen | The Lightweight Ondemand Ad hoc Distance-vector Routing Protocol -Next Generation (LOADng)[END_REF] is a simplified reactive routing protocol, targeting routing in low-power and lossy networks. It has been standardised by the ITU (International Telecommunication Union) [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF] for routing in the "Smart Grid", between electricity meters and other equipment for electricity grid management.

As a reactive protocol, the basic operations of LOADng include generation of Route Requests (RREQs) by a LOADng Router (originator) for when discovering a route to a destination. These RREQs are flooded through the network, each forward of a RREQ installing temporary routing table entries towards the originator of the RREQ. Once an RREQs has has been received the sought the destination LOADng Router, that device will generate a Route Reply (RREPs), which is unicast hop-by-hop towards the originator using the temporary route installed by the received RREQ. This forwarding of an RREP installs routing table entries towards the destination.

If a route is detected broken, i.e., 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. The LOADng specification stipulates that when the transmission of a data packet fails, that data packet is dropped and a RERR is sent back to its source -which can, then, trigger a new route discovery.

Extensions to and options for LOADng exist [START_REF] Yi | Smart Route Request for On-demand Route Discovery in Constrained Environments[END_REF], [START_REF] Bas | Expanding Ring Search for Route Discovery in LOADng Routing Protocol[END_REF] for trying to reduce the impact on the network load of route discovery -but fact remains that in networks where transmission failures are frequent, this behaviour can result in low delivery ratios and possibly high network loads [START_REF] Clausen | LOADng: Towards AODV Version 2[END_REF].

III. DEPTH-FIRST FORWARDING

DFF [START_REF] Herberg | Depth-First Forwarding (DFF) in Unreliable Networks[END_REF] is a forwarding mechanism for improving the data delivery success ratio across unreliable multi-hop networks. It operates solely on the forwarding plane, i.e., does not assume any specific routing protocol to be in operation (or, indeed, that any routing protocol is in operation) -but can, as appropriate and as indicated in section I, interact with a routing protocol. DFF relies on an external mechanism providing each router with a list of its neighbours.

Schematically, the basic operation of DFF is as follows, when a data packet for a destination arrives at the forwarding plane of a router:

1) The router temporarily creates an ordered Candidate Next Hop list for that packet, which does not contain the neighbour from which the data packet was received (if any), from among the neighbours in the routers' neighbour list.

2) The router attempts to forward the data packet to the first neighbour in the resulting Candidate Next Hop list. 3) There are five possible outcomes from this attempt:

• The Candidate Next Hop list is empty, in which case the data packet is returned to the neighbour from which it was initially received, and the process for this router stops. • Delivery to that neighbour succeeds (e.g., as confirmed by an L2 acknowledgement), and that neighbour is the destination for the data packet. The L2 acknowledgement indicates successful data packet delivery to the destination. The process for this router stops. • Delivery to that neighbour fails (e.g., detected by lack of an L2 acknowledgement), in which case that neighbour is removed from the Candidate Next Hop list, and the process resumes at item 2 above. • Delivery to that neighbour succeeds (e.g., as confirmed by an L2 acknowledgement), but the data packet is returned from the neighbour as "undeliverable", in which case that neighbour is removed from the Candidate Next Hop list, and the process resumes at step 2 above, with the resulting Candidate Next Hop list. • Delivery to that neighbour succeeds (e.g., as confirmed by an L2 acknowledgement), the neighbour is not the destination for the data packet. That neighbour will, now, execute this very same procedure (create its own Candidate Next Hop list, and execute this process, starting at step 1). The initial Candidate Next Hop list for a data packet, by default, contains all the neighbours of a router, except for the neighbour from which the data packet was received, but may be smaller. The list is ordered, section 11 in [START_REF] Herberg | Depth-First Forwarding (DFF) in Unreliable Networks[END_REF] suggests several criteria to take into account when ordering that list, including that if a routing protocol is in operation, then the neighbour on the shortest path (as indicated by that routing protocol) must be part of the initial Candidate Next Hop list -and is recommended to be first in that initial Candidate Next Hop List. Link quality, historical information on "good and bad neighbours as next hop" is suggested to be used for ordering remaining neighbours.

DFF contains mechanisms for detecting looping data packets, encoded as flags and sequence numbers in IPv6 Hop-by-Hop header options, carried in each data packet, and specifies processing here. This incurs a small, but fixed, per-datapacket overhead of 8 octets. This paper does not discuss this signalling and processing in further details.

IV. INTEGRATION OF LOADNG AND DFF DFF requires that a router has a list of all its neighbours available for constructing the Candidate Next Hop list for a data packet. [START_REF] Herberg | Depth-First Forwarding (DFF) in Unreliable Networks[END_REF] specifies that an external mechanism is to be in place to provide that list, and suggests the use of NHDP (Neighborhood Discovery Protocol) [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] -which is implemented and used for the purpose of the performance studies in this paper.

The routing protocol LOADng provides, at most, one entry in the routing table for each destination, thus the integration of the requirements for ordering the entries in the Candidate Next Hop list for a data packet is met simply by, if a routing table entry for the destination is present, inserting this first in that list. The remainder of the entries in the Candidate Next Hop list are, simply, all the other neighbours discovered by NHDP (and with status SYMMETRIC), excluding of course the neighbour from which the data packet was received.

Additionally, the two following rules govern the integration of LOADng and DFF, for the purpose of the studies in this paper, specifically when the protocol operations for each are activated:

• When a router receives a data packet from another router, for which it does not have a corresponding entry in the routing table :  -Send data packet according to the DFF forwarding rules, as described in section III -Send an RERR message to the originator of that data packet, as described in section II An RERR message is sent since while DFF will ensure data delivery, this may be by way of an excessively long path; by sending an RERR message, the routing protocol is instructed to "try to find a better path" whilst DFF concurrently attempts delivery of data in transit (thus reducing delays, retransmissions and/or buffer of data traffic).

• If forwarding of a data packet to the next hop, indicated by LOADng (i.e., the first entry in the Candidate Next Hop list) fails (either by way of the packet being returned by DFF, or by an L2 acknowledgement being absent):

-Send data packet according to the DFF forwarding rules, as described in section III -Send an RERR message to the originator of that data packet, as described in section II In this case, an RERR message is sent since, in addition to the reasons listed above, this is indicative of the routing information being inconsistent with the network topology, and therefore needs to be updated. Figure 1 gives an example of DFF with LOADng. Node A is the data source, and node D is the destination. The route originally found by LOADng protocol was A-B-F-D (one of the shortest paths). However, when a data packet arrived at node B, the link B-F was detected broken. By using DFF, a neighbour node from Candidate Next Hop list, node G, for example, is chosen as next hop. The data packet is thus forwarded to node G, which will handle the packet according its routing table information or DFF, and forward it to the destination node D. In the meantime, node B will send an RERR message to node A, to notify the route failure.

V. EVALUATION

In order to evaluate and compare the performance of LOADng with and without DFF, network simulations by way of NS2 are employed. While network simulations are, at best, an approximation of real-world performance (particularly due to the fidelity of their lower layers to reality), they do provide a baseline for comparison and, generally, best-case results, i.e., real-world performance is expected to be no better than that which is obtained through simulations. The reason for using network simulations is, that such allow running experiments with different protocols under identical conditions and parameters (MAC layer, distribution, number of nodes, etc.).

Simulations were conducted using the TwoRayGround propagation model and the IEEE 802.11 MAC. Although there are various low-layer technologies more commonly (and, perhaps, more viably) used for LLNs (power line communication, 802.15.4, low-power wifi, bluetooth low energy, etc.), general behaviour of a protocol can be inferred from simulations using 802.11.

To discover bi-directional links in the network, NHDP is used. For NHDP, a HELLO message interval must be chosen. The shorter the HELLO message interval, the more accurate a list of neighbours can be acquired (and so, the better can DFF do their jobs) but at the expense of increased control traffic overhead. For the purpose of these simulations, a HELLO interval of 1s was (arbitrarily) chosen as it represents a "very frequent HELLO message exchange and therefore a good "worst case" example. In a real deployment, the HELLO interval should be selected so as to correspond to the expected local network topology change rate.

A. Network Topology and Traffic Characteristics

The general network topology of a scenario is as follows: n (from 63 to 500) devices are placed randomly (while ensuring that the network is still connected) in a square field, so that to maintain a constant device density. A (random) device in the network then creates n -1 Constant Bit Rate (CBR) streams, one to each other device and sends one packet of 512 octets every 5 seconds to each of them. As DFF is supposed to be particularly beneficial in lossy networks, the simulations enforce that a packet is lost with a probability of 20%. Simulations were run for 100s each, and for each datapoint 20 different and randomly generated scenarios -all corresponding to the same abstract parameters -were simulated, with the results presented below representing averages from among these.

B. Simulation Results

Figure 2 depicts the data delivery ratios obtained for the two protocols. While neither protocol obtains a perfect data delivery ratio, DFF+LOADng introduces a constant ∼20% improvement over LOADng. This improvement comes with an increased control traffic overhead, as shown in figure 3 this is due to the fact that DFF+LOADng includes operation of NHDP which incurs periodic signalling within each neighbourhood. Figure 5 and 4 depict average end-to-end data delivery delays and path lengths for data traffic. While it may appear be intuitive that DFF incurs longer path lengths (after all, a depthfirst search for a destination will rarely yield the shortest path), section IV introduced the use of DFF as a way of reducing delays. This, therefore, must be balanced with what happens without DFF: data packets are dropped, and not included in the delay or path length statistics, during the time needed by LOADng to recover. Figure 6 depicts the number of collisions incurred (including collisions between control and data traffic). The overhead (see figure 3 of NHDP, necessary for LOADng+DFF, causes an increased number of collisions as compared to LOADngyet this the data packet loss incurred through this is more than offset through the benefits of using DFF, as depicted in figure 2.

VI. CONCLUSION

This paper introduces DFF as a forwarding mechanism for LLNs, and its application to the LOADng protocol. The implementation of DFF is about 200 lines of additional code, compared to about 5000 lines of code for the LOADng prototype. Because DFF requires the information of bi-directional neighbors, NHDP is employed in this study (an additional 200 lines of code). It is important to note that NHDP is not mandatory if external mechanisms can provide the neighborhood information, such as link layer protocols.

Simulation is performed to study the performance of DFF in harsh lossy networks. Simulation results show that with the DFF extension, up to 20-25% of improvement in data delivery ratio can be achieved compared to LOADng, with little cost in delay and path length. This makes DFF an interesting mechanism for scenarios where the data delay is not critical.

In the implementation tested, a basic (or "naive") mechanism is used -DFF treats every bi-directional neighbor equally, without considering which may be the best candidate "next hop" to the final destination. This, however, is intentional, so as to be able to observe what is the worst case when DFF is employed. With this benchmark, it would be interesting to explore more efficient mechanisms for choosing the "best next hop" in the future.

Figure 1 .

 1 Figure 1. An example of DFF. Node A is the source, node D is the destination.

Figure 2 .

 2 Figure 2. Delivery Ratio

  Figure 3. Overhead

Among other things, it would be difficult to use IPSec or similar mechanisms.


Thomas Clausen
email: thomas@thomasclausen.org

Axel Colin De Verdiere

Jiazi Yi

Proceedings of ICCT2013 Performance analysis of Trickle as a flooding mechanism

The Trickle Algorithm" is conceived as an adaptive mechanism for allowing efficient and reliable information sharing among nodes, communicating across a lossy and shared medium. Its basic principle is, for each node, to monitor transmissions from its neighbours, compare what it receives with its current state, and schedule future transmissions accordingly: if an inconsistency of information is detected, or if few or no neighbours have transmitted consistent information "recently", the next transmission is scheduled "soon" -and, in case consistent information from a sufficient number of neighbours is received, the next transmission is scheduled to be "later".

Developed originally as a means of distributing firmware updates among sensor devices, this algorithm has found use also for distribution of routing information in the routing protocol RPL, standardised within the IETF for maintaining a routing topology for low-power and lossy networks (LLNs). Its use is also proposed in a protocol for multicast in LLNs, denoted "Multicast Forwarding Using Trickle". This paper studies the performance of the Trickle algorithm, as it is used in that multicast protocol.

I. INTRODUCTION

Low power and Lossy Networks (LLNs) are typically constituted by a very large number of very small and very cheap devices -each generally equipped with at most a few kilobytes of RAM and around 100kB of ROM -communicating through a very lossy, low-capacity wireless or wired medium (e.g., Power Line Communication -PLC, or lowpower wireless channels, like 802.15.4 PHY). Applications of these networks include utility metering, earthquake monitoring, vehicular networks, factory and home automation, etc.

The main constraints on such networks are channel utilisation, energy consumption, and storage and processing capabilities of each device. Furthermore, the lossy media and minimal routers typically used by LLNs often lead to dynamic network topologies. Protocols for these networks thus have to be specifically designed to use as little energy as possible, minimise channel utilisation and storage -while being as simple (both in terms of algorithmic and implementation complexity) as possible and be able to adapt to a changing network topology. As an example, the unicast routing protocol, LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], standardised as part of [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF], uses a greatly simplified reactive route discovery mechanism to discover and maintain routes only on-demand, emphasising state reduction and implementation simplicity and eliminating rarely beneficial options [START_REF] Clausen | Loadng: Towards aodv version 2[END_REF].

LOADng necessitates dissemination of control messages throughout the entire network, often found to be an an expensive and unreliable task in LLNs when implemented by way of flooding. More generally, a multitude of protocols and applications require the ability to send a message to all devices in a network, e.g., to bring all devices into a common state ("turn off all the light in this room"). In a constrained and dynamic environment, maintaining a multicast tree or multicast mesh structure in such an environment is challenging -and scoped flooding remains a potentially cheaper alternative in some scenarios [START_REF] Macker | Simplified Multicast Forwarding[END_REF].

This underlines the importance of efficient message dissemination techniques, adapted for LLNs. Classic approaches for efficient message dissemination include mechanisms such as Multipoint Relay [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF], Essential Connecting Dominating Set (E-CDS) [START_REF] Ogier | Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding[END_REF], or MPR+SP [START_REF] Cordero | Mpr+sp: Towards a unified mpr-based manet extension for ospf[END_REF] -all of which do require that devices in the network maintain some additional topology knowledge, the acquisition of which incurs extra control message generation and, thus, network load. Alternative, potentially more effective, dissemination algorithms have been proposed for LLNs, including use of "The Trickle Algorithm" [START_REF] Levis | Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks[END_REF] [START_REF] Levis | The Trickle Algorithm[END_REF], an efficient dissemination mechanism first designed for code updates in wireless sensor networks. The use of this algorithm has been proposed within the IETF [START_REF] Hui | Multicast forwarding using trickle[END_REF] -denoted "Trickle Multicast" -as a standard mechanism for efficient message dissemination through an LLN.

This paper evaluates the performance Trickle Multicast, and offers a comparison with classic and MPR flooding.

A. Paper Outline

The remainder of this paper is organised as follows: section II details the operations of Trickle Multicast, and section III outlines classic flooding and MPR Flooding, used as baselines for evaluating the performance of Trickle Multicast. The different mechanisms are evaluated by way of network simulations, which are described in section IV, with the results presented in section VI. This paper is concluded in section VII.

II. TRICKLE MULTICAST

Trickle [START_REF] Levis | Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks[END_REF] was originally conceived a self-adapting algorithm for reliable code propagation in wireless sensor networks. It applies a "polite gossip" policy, where each device periodically transmits a summary of its state (say, the firmware version) to its neighbours, but suppresses this transmission if it has, recently, heard enough neighbours advertising the same state. Furthermore, as the network converges to a consistent situation, where all devices have the same state, the algorithm generates fewer transmissions.

The Trickle algorithm is defined in terms of a received transmission being "consistent" (i.e., the neighbour sending the advertisement has "the same" information as the receiver) or "inconsistent" (i.e., the neighbour sending the advertisement has "different' information than the receiver), with the exact definitions of "consistent" and "inconsistent" being dependent on the protocol using the Trickle algorithm. For firmware updates, for example, a version number equality may imply "consistent" whereas a version number inequality may imply "inconsistent" -or, consistency may be defined as "using a version 3.xx firmware, for any value of xx".

Trickle defines three constants, I min , the minimum interval size, I max , the maximum interval size, defined in terms of doublings of I min , and k, the redundancy constant. Each device maintains two parameters: I, the size of the current transmission interval, t, a time within the current interval, and a counter c, the number of consistent transmission received during this interval. A device implementing Trickle proceeds as follows:

1) At initialization, the device chooses I randomly in [I min , I max ]. 2) An interval start, t is chosen randomly in [I/2, I) and c is reset to 0. The interval finishes a I. The device then listens to incoming transmissions until time t. 3) When the device receives a transmission from one of its neighbours, it determines if either itself or its neighbour has more recent data than the other: a) If the transmission represents a consistent event, i.e., no device has new data for the other, c is incremented. b) Else, if the neighbour device has new data, this device updates its data, resets I to I min and starts a new interval. c) Else, if this device has data unknown to the neighbour device, it directly transmits it to all of its neighbors, without resetting the interval. 4) At time t, the device transmits a summary of its data to all of its neighbours only if c < k. Otherwise, the device doubles the interval size. If this new interval size would be greater than the time specified by I max , Trickle sets the interval size I to be the time specified by I max . Trickle can be used as an optimised flooding algorithm in LLNs, proposed in [START_REF] Hui | Multicast forwarding using trickle[END_REF] and henceforth denoted "Trickle Multicast", for support of IPv6 multicast forwarding in LLNs. This use of Trickle introduces a "seed" and a sequence number for multicast messages dissemination.

"Trickle Multicast" uses a Trickle IPv6 option to carry SeedID1 and Sequence number2 with each multicast message, allowing them to be uniquely identified. Each device also maintains sliding windows (one per known SeedID), which ensures that each message received is processed at most once by the device: an incoming multicast message is accepted if and only if its sequence number is not stored in the corresponding (i.e., identified by the received message's SeedID) sliding window, and the Sequence Number is greater than the lower bound of that sliding window. Devices then advertise their state, expressed through a Trickle ICMPv6 message summarizing the recently received multicast messages, to their neighbours through transmissions regulated by the Trickle algorithm "Trickle Multicast" defines a received summary message to be "consistent" if the recently received multicast messages identified therein are identical to those also received by the recipient of the summary message.

III. BASELINE FLOODING MECHANISMS

As baselines for comparing Trickle Multicast, this section briefly discusses Classic Flooding and MPR Flooding.

A. Classic Flooding

Classic flooding is the simplest form multicast message diffusion: when receiving a multicast message, each device will verify if it has already received a copy hereof. If yes, the message is silently dropped, if no, the message is sent to each of its neighbours. This implies that the only state a router has to maintain is a buffer, retaining identifying information for the recently flooded messages received, and that each flooded data message must contain a message identifier (typically, by way of a sequence number and the address of the source of the flooded message). No explicit control messages are generated, and the only control signalling incurred is the message identifier. On the other hand, since each flooded message is transmitted exactly once by each device in the network, it is a potentially expensive operation [START_REF] Clausen | Investigating data broadcast performance in mobile ad-hoc networks[END_REF], and subject to the infamous "broadcast storm problem" [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF]. Classic Flooding is considered the absolute baseline, against which any more complex flooding mechanisms must provide a measurable improvement.

B. MPR Flooding

With Multipoint Relay Flooding [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF], each device selects a set of relays (its MPRs) from among its direct neighbours. A device, X, selects its MPR Set such that a message transmitted by X and relayed only by the members of its MPR set will be received by all devices 2 hops away, and stipulates that a device relays a multicast message only if received from a device having selected it as MPR. Thus, MPR Flooding reduces the number of redundant copies of messages sent through the network. MPR selection requires that each device maintains, at least, topology up to two hops away from itself, and to this end, participating devices periodically exchange HELLO messages. Furthermore, a greedy algorithm is applied to determine the relay set, which yields an approximation of an optimal connected dominating set -this set is also signalled by each device through HELLO messages.

IV. SIMULATION ENVIRONMENT

In order to evaluate the performance of Trickle Multicast, network simulations by way of NS2 are employed. While network simulations are, at best, an approximation of realworld performance (particularly due to the fidelity of lower layers vs. reality), they do provide a baseline for comparison and, generally, best-case results, i.e., real-world performance is expected to be no better than that which is obtained through simulations. The reason for using network simulations is, that such allow running experiments with different protocols (in this case, Trickle Multicast, Classic Flooding and MPR Flooding) under identical conditions and parameters (MAC layer, distribution, number of nodes, etc.) Simulations were conducted using the TwoRayGround propagation model and the IEEE 802.11 MAC. Although there are various low-layer technologies more commonly (and, perhaps, more viably) used for LLNs (power line communication, 802.15.4, low-power wifi, bluetooth low energy, etc.), general behaviour of a protocol can be inferred from simulations using 802.11.

A. Network Topology and Multicast Traffic Characteristics

The general network topology of a scenario is as follows: n devices are placed randomly (while ensuring that the network is still connected) in a square field of size m × m meters. From among the n devices, x devices are randomly chosen as concurrent multicast data sources, each generating a multicast data packet of 15 octets every 30 seconds, and with each multicast data source generating n -1 multicast data packets.

These data traffic characteristics are not chosen arbitrarily, but rather to reflect the traffic characteristics that one might see if using Trickle Multicast for carrying the multicast portion of the route discovery mechanism of LOADng -as alluded in the introduction as one interesting use of an optimised flooding mechanism in an LLN -where each of x wishes to send a route discovery to all other devices in the network. This, in turn, may represent a set of controllers in a network, wishing to inquire for sensor readings from, or manipulate actuators on, all of these devices.

B. Protocol Parameters

The protocol parameters used for all the simulations are shown in table I. Jitter is used on multicast messages for MPR Flooding and Classic Flooding, according to [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF], so as to reduce the risk of collisions. Trickle has an implicit jitter mechanism, hence [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF] is not used with Trickle Multicast.

C. Scenario Descriptions

Four different kinds of scenarios are studied, comparing the three different mechanisms. For the first scenario, different sets of Trickle parameters are considered, including those recommended by [START_REF] Popa | Applicability statement for the routing protocol for low power and lossy networks (rpl) in ami networks[END_REF] for AMI (Automatic Metering Infrastructure) networks 3 , and reproduced in the following: • the redundancy constant should be set to at least 10. These parameters, given in table II, are recommended for the use of Trickle in RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF], and used as a point of comparison. The scenarios studied are:

Variable Density The performance of Trickle flooding in a given network density depends on the parameters chosen, in particular for k, and I min . These simulations are conducted using an 1000m × 1000m square, with the number of devices varying between 32 and 250. For the purpose of these simulations, a single multicast data source is used (x = 1), and the scenarios are tested with trickle parameters as given by table II.

Fixed Density

This set of simulations compares the three flooding mechanisms in a network of fixed density of 50 devices/km 2 . The number of nodes varies between 15 and 500, and the field dimensions varies correspondingly from 595m×595m to 3162m×3162m For the purpose of these simulations, a single multicast data source is used (x = 1), and for Trickle Multicast, I min = 1s and k=2 is used.

Variable Number of Multicast Sources

This set of simulation compares the three flooding mechanisms when subject to a variable number of multicast sources, ranging from x = 1 to x = 30, in a network with 125 devices distributed across a field of 1581m×1581m. For Trickle Multicast, I min = 1s and k=2 is used.

Loss Resiliance

The inconsistency detection and retransmission mechanism of the Trickle algorithm is supposed to ensure that message losses are eliminated -i.e., that given enough time, all devices will have consistent state information. Thus, this set of simulations compares the performance of the flooding mechanisms in a network subject to (explicit and excessive) message losses: a packet is lost with a certain (independent) probability, ranging from 0.0 to 0. Data delivery ratio This metric measures the success rate of the different flooding mechanism. For a given simulation, it averages the per-source Data delivery ratio, which itself is the average over all the multicast data packets sent by this source of the number of devices which have received that packet, divided by the number of devices other than the source.

Number of multicast data packet transmissions

This metric measures the number of times a given data packet has to be retransmitted in order for it to reach all the devices in the network. For a given simulation, it is computed as the total number of multicast data packets sent.

Total number of transmissions

This metric counts the total number of packets transmitted during the simulation, counted as the source.

In other words, each control or data packet sent adds one to the result.

Network load

The Network load measures the overall load the flooding mechanism has put on the network during the simulation, i.e. the actual number of KB sent, both control and data packets.

Data Delivery Delay

The Data delivery delay represents the time taken, on average, for a multicast data packet to reach all the devices in the network (or, in case all the devices are not reached, all the devices that will ever receive this packet). As such, it is computed as the average over all the multicast data packet generation of the time between the first transmission of the packet and the last time a device receives that packet for the first time (a device receiving a given data packet twice does not increase the delivery delay).

Flooding Path Length This metrics gives a measure of the quality (measured by the hop count) of the paths taken by the multicast data packets from their source to each device in the network. Hence it is the average, over all the data packets originated during the simulation, of the average hop count observed at every receiving device (each packet is counted only once at each device). Although hop count is generally considered a poor metric for routing, it still gives an indication regarding the efficiency of the flooding mechanism.

VI. SIMULATION RESULTS

The evaluation of Trickle Multicast, and the comparison with MPR Flooding and Classic Flooding in each of the four scenarios described in section IV, and with respect to the performance metrics presented in section V is presented and discussed below. For all three mechanisms, identical data delivery ratios (approximately of 100%) were attained. Figure 1 shows that Classic Flooding, as expected, presents the largest number of messages sent and figure 2 that -depending on the parameters chosen -Trickle Multicast can offer the fewest number of data message transmissions.

A. Variable density

Noting that in terms of media occupation and energy consumed for transmitting and receiving it, a more appropriate metric is the "load" of the network, which is the number of octets (control traffic and data traffic) necessary to complete the flooding operations. This is depicted on figure 3, where it can be seen that the "gain" as compared with classic flooding, in terms of fewer messages sent by Trickle Multicast, is greatly diminished by the size of the Trickle Multicast control messages. Note that this graph does not include the overhead for MPR Flooding which, due to the periodic signals for acquiring local topology, is way higher than that of both Trickle Multicast and Classic Flooding.

It is worth noting the sensitivity of the choice of Trickle parameters. First, as expected, the value of I min directly affects the data delivery delay, as depicted in figure 4 whereas the value of k (the redundancy constant) has very little effect on the incurred delay. However, increasing k and decreasing I min negatively affects the overhead incurred. The effect of k is very intuitive, since it represents the number of transmissions a given "area" will do during each transmission interval. Figure 4 also shows that Trickle Multicast consistently incurs higher delivery delay, even when choosing the best possible parameters for the scenario, from among those tested. In particular, the value of I min directly affects the delay -thus forcing a tradeoff between overhead and delay when choosing this parameter. In summary, the performance of Trickle Multicast depends on the choice of parameters, and the set of parameters recommended by [START_REF] Popa | Applicability statement for the routing protocol for low power and lossy networks (rpl) in ami networks[END_REF] exhibits the worst performance from among those tested.

Proceedings of ICCT2013

B. Fixed density

Figures 5, 6, 7, and 8 depict the results for Fixed Density scenarios. For all three mechanisms, identical data delivery ratios (approximately of 100%) were attained.

These simulations suggest that the performance of Trickle flooding is tightly related to the network size, noting that even with the "best" (according to the previous set of simulations) parameters chosen for Trickle, the overall network load remains higher than with classic flooding. This, due to the overhead incurred by the Trickle control messages, which is proportional to the number of devices in the network.

Figure 8 depicts the average path lengths that data packets follow from the source to all destinations. As all mechanisms attain identical data delivery rates close to 100%, path lengths can be compared directly, concluding that "shorter is better". MPR Flooding yields shorter path lengths than both Trickle Multicast Classic Flooding, confirming the observations of [START_REF] Clausen | Optimizing route length in reactive protocols for ad hoc networks[END_REF], with Trickle Multicast attaining systematically longer paths than both Classic Flooding and MPR Flooding. The difference between the average path lengths from MPR Flooding to Trickle Multicast remains moderate, however increases as the network grows larger (up to 37%). This can be an issue for some applications: in LOADng for example, this would increase the length of the discovered paths, thus adversely affecting routing protocol performance.

C. Variable Number of Multicast Sources

Figures 9 and 10, depict the results for Variable Number of Multicast Sources. For all three mechanisms, identical data delivery ratios (approximately of 100%) were attained.

Figure 9 shows that the overhead incurred by Trickle increases dramatically as the number of concurrent Multicast Sources increases. Whereas for the previous scenarios featuring only a single Mutlicast Source, the network load (control and data) incurred by MPR Flooding was dramatically larger than that of Classic Flooding and Trickle Multicast, as soon as there are multiple concurrent Multicast Sources in the network, Classic Flooding incurs a lower network load than Trickle Multicast -and from 6 concurrent Multicast Sources, Trickle Flooding incurs a higher network load than MPR Flooding and Classic Flooding, both.

This sharp increase in network load, incurred by Trickle when faced with multiple Multicast Sources, can be explained by the requirement that all devices must generate the "summary packets" (section II), each of which grows as a function of the number of Multicast Sources as each summary packet carries information about all the current active sources, with their associated sliding windows. Thus, Trickle Multicast is negatively affected by the number of multicast sources.

Figure 10 depicts the data delivery delay. While the delays remain constant and independent of number of Multicast Sources for MPR Flooding and Classic Flooding, Trickle Multicast experiences a decrease in delay as the number of Multicast Sources grow -an 21% decrease between a network with 1 Multicast Source and 30 Multicast Sources. The explanation for this behaviour is, that the Trickle timers are reset more often (due to inconsistencies detected more frequently), causing more frequent (re)transmissions. Even so, the data delivery delays incurred by Trickle Multicast remain, consistently, substantially larger than those incurred by Classic Flooding and MPR Flooding. 11) as the loss rate increases, its data delivery rate (figure 12) stays consistently high -whereas it drops off for Classic Flooding and MPR Flooding. From among the three mechanisms, MPR Flooding is the most vulnerable to lossy links -this, simply, as MPR Flooding optimises flooding by eliminating redundant copies of multicast data packets, present in the network. The gain in loss resilience of Trickle Multicast comes at a cost of increased delay (of up to 1200% compared to classic flooding in the simulations performed).

D. Loss Resilience

VII. CONCLUSION

This paper has evaluated the performance of Trickle Multicast, comparing with that of Classic Flooding and MPR Flooding. Trickle Multicast was found to be resilient to very lossy links, and to maintain an overall high data delivery ratio when faced with such -whereas Classic Flooding and MPR Flooding, both, fail to deliver acceptable delivery ratios in these scenarios. On the other hand, in networks with more reliable links, Trickle Multicast exhibit less excellence.

The simulations have shown that the performance of Trickle Multicast is highly sensitive to the choice of parameters: the simulations showed that the same set of parameters can render Trickle Multicast the best or worst performer in a given scenario -and, in some cases, an inadequate choice of parameters makes Trickle Multicast a far worse solution that Classic Flooding, both in terms of overhead and delay, while not achieving any better multicast data delivery ratio. This poses two challenges in the use of this protocol for real life network scenarios: first, more in-depths experimental studies are be needed for each particular use-cases, in order to understand how to choose the appropriate parameters. Second, the sensitivity exhibited by Trickle Multicast makes it vulnerable to changes in network conditions over the duration of the network lifetime -which, for sensor networks, is an expected operational condition. An additional observation for Trickle Multicast is, that its performance (network load and delays incurred) depends on the number of concurrent Multicast Sources active in the network: while with a single Multicast Source, Trickle Multicast may exhibit a reasonably low overhead, the size of the control signals that Trickle Multicast employs is proportional to the number of Multicast Sources. Thus, the network load incurred by Trickle Multicast rapidly exceeds that incurred when using MPR Flooding and Classic Flooding, when there are more than one Multicast Source.

Thus, to make Trickle Multicast generally applicable for autonomous sensor networks, it is necessary to further investigate how to (i) detect changes in network conditions and (ii) automate the adaptation and installation of such configuration parameters. Furthermore, a deployment should carefully consider the number of Multicast Sources expected in the network (at installation and in the future), in order to understand if the network load incurred by Trickle Multicast is commensurate with the network capacity, and the delays incurred on data delivery are acceptable to application. Finally, any use of Trickle Multicast should consider the implications of the Trickle Multicast trade-offs: as indicated, e.g., if using Trickle Multicast for flooding routing protocol control signals, the longer paths that these control signals will take may cause a routing protocol to discover longer routes and thus ultimately degrade unicast performance.

Figures 1 ,

 1 Figures 1, 2, 3 and 4 depict the results for the Variable Density scenarios -it is important to recall that only a single multicast data source is present in these simulations.For all three mechanisms, identical data delivery ratios (approximately of 100%) were attained. Figure1shows that Classic Flooding, as expected, presents the largest number of messages sent and figure2that -depending on the parameters chosen -Trickle Multicast can offer the fewest number of data message transmissions.Noting that in terms of media occupation and energy consumed for transmitting and receiving it, a more appropriate metric is the "load" of the network, which is the number of octets (control traffic and data traffic) necessary to complete the flooding operations. This is depicted on figure3, where it can be seen that the "gain" as compared with classic flooding, in terms of fewer messages sent by Trickle Multicast, is greatly diminished by the size of the Trickle Multicast control messages. Note that this graph does not include the overhead for MPR Flooding which, due to the periodic signals for acquiring local topology, is way higher than that of both Trickle Multicast and Classic Flooding.It is worth noting the sensitivity of the choice of Trickle parameters. First, as expected, the value of I min directly affects the data delivery delay, as depicted in figure4whereas the value of k (the redundancy constant) has very little effect on the incurred delay. However, increasing k and decreasing I min negatively affects the overhead incurred. The effect of k is very intuitive, since it represents the number of transmissions a given "area" will do during each transmission interval. Figure4also shows that Trickle Multicast consistently incurs higher delivery delay, even when choosing the best possible parameters for the scenario, from among those tested. In particular, the value of I min directly affects the delay -thus forcing a tradeoff between overhead and delay when choosing this parameter. In summary, the performance of Trickle Multicast depends on the choice of parameters, and

Figure 1 .Figure 2 .

 12 Figure 1. Variable Density: Number of multicast data packet transmissions

Figure 3 .

 3 Figure 3. Variable Density: Network Load (control + data, in KB).

Figure 4 .Figure 5 .Figure 6 .

 456 Figure 4. Variable Density: Data Delivery Delays.

Figure 7 .Figure 8 .

 78 Figure 7. Fixed Density: Data Delivery Delays.

Figures 11 and 12

 12 Figures 11 and 12 depict the Loss Resilience of the three mechanisms. While the model for packet loss used was very simple, it does provide some insight into the behaviour of Trickle Multicast in lossy environments. While the data delivery delays for Trickle Multicast grow dramatically (figure11) as the loss rate increases, its data delivery rate (figure12) stays consistently high -whereas it drops off for Classic Flooding and MPR Flooding. From among the three mechanisms, MPR Flooding is the most vulnerable to lossy links -this, simply, as MPR Flooding optimises flooding by eliminating redundant copies of multicast data packets, present in the network.

Figure 9 .Figure 10 .

 910 Figure 9. Variable Number of Multicast Sources: Network Load (control + data).

Figure 11 .Figure 12 .Figure 13 .

 111213 Figure 11. Loss Resiliance: Data Delivery Delays.

  I min should be set to at least 50 times as long as it takes to transmit a link-local multicast packet. During the simulations, a transmission time around 1ms was observed, thus I min = 100ms satisfies this constraint without being overly conservative;• I max should be greater than 2 hours.

	Parameter	Default value	Note
	Trickle Multicast parameters
	Imax	2 16 x I min
	Window size	3	Size of the sliding windows
	MPR Flooding parameters
	HELLO interval	5s
	Neighbor expiration time	25s
	MPR and Classic Flooding parameters
	Jitter	500ms	Maximum jitter value for
			broadcast transmissions
		Table I
	DEFAULT PROTOCOL PARAMETERS FOR SIMULATION

•

  7.A single multicast data source is used (x = 1), in a network with 125 devices distributed across a field of 1581m×1581m. For Trickle Multicast, I min = 1s and k = 2 is used.

	Parameter	Values
	I min	200ms, 500ms, 1s, 1.5s
	k	2, 6
	AMI parameters (from [15])
	I min	100ms
	k	10
		Table II
	TRICKLE PARAMETERS FOR VARIABLE DENSITY SIMULATIONS
	V. PERFORMANCE METRICS
	The metrics used for evaluating the performance Trickle
	Multicast, and compare with that of MPR Flooding and Classic
	Flooding are as follows:

The SeedID is an identifier of the Trickle Multicast router by which the multicast message enters the Trickle Multicast domain; it may be different from the source IP address if, for example, the multicast packet originates from a device outside that domain.

Monotonically increasing, maintained by the Trickle Multicast router identified by the SeedID.

[START_REF] Popa | Applicability statement for the routing protocol for low power and lossy networks (rpl) in ami networks[END_REF] recommends parameters for Trickle when used for "flooding" RPL control traffic -DIOs -in an "Automatic Metering Infrastructure" network.