Ulrich Herberg
email: ulrich@herberg.name

Thomas Clausen
email: thomas@thomasclausen.org

Delay Tolerant Networking with OLSRv2

This paper proposes a simple mechanism for enabling basic delay tolerant networking with off-the-shelf MANET routing protocols -with the objective being to enable trading off slightly longer data delivery delays against resilience to a temporary lack of connectivity between a router and the ultimate destination of an IP datagram. As part of testing the benefit of said mechanism, an extreme network mobility model is proposed, entitled the "PopUp model": a router appears in the network, and operates normally -then may disable and disappear from the network to appear later elsewhere. Observed to cause severely degraded performance for MANET routing protocols, this model is used for testing the proposed mechanism in OLSRv2-routed MANETs. The proposed mechanism shows to vastly increase the data delivery ration, with reasonably low increases in delays and control traffic overhead incurred.

I. INTRODUCTION

IP datagram transmission is based on a delivery principle, commonly known as "best effort": if the routing table contains a "valid route" towards the destination of the datagram, then the datagram is transmitted -otherwise, it is silently dropped. In ad hoc networks, such a "best effort" behavior may be undesired: a route may not be available, but will be shortly, e.g., as the routing protocol converges so as to reflect a changed topology in routing tables. A wireless link may at one point have been considered sufficiently reliable, and thus advertised and used as such, yet over time degrade until being declared as lost and possibly advertised as lost also. Destinations reachable via paths containing this now lost link are unreachable, at least until the routing protocol message exchange and table calculations complete, providing different paths through the network.

In networks in which the topology is dynamic and such transient situations are frequent, it may be preferable to slightly alter the "best effort delivery principle" so as to, colloquially speaking, hold on to an un-transmittable IP datagram for a while, hoping that a route will become available shortly -using graph terminology, may choose to buffer an untransmittable IP datagram until its routing table indicates that it is in the same connected component as the intended destination. Doing so may increase the data delivery ratio, at the expense of longer delivery delays ("delay tolerant networking") as well as additional state requirements in routers for the buffering process.

This paper proposes: 1) A modification to the IP datagrams transmission process, allowing for buffering un-transmittable IP datagrams;

2) A network mobility model, entitled "PopUp Networks", wherein devices appear in the network, disappear, move, then re-appear; 3) A comprehensive set of simulations, studying the behavior of an OLSRv2-routed ad hoc network, when exposed to the previous two items. The proposed PopUp network mobility model is presenting an "extreme" type of network behavior, and is so chosen as it generally results in vastly degraded routing protocol performance, unless special measures are taken. The purpose of this paper is to present how, even when faced with such a harsh network mobility model, a relatively simple mechanism can vastly improve the performance an off-the-shelf ad-hoc routing protocol.

A. Paper Outline

The remainder of this paper is organized as follows: section II provides a basic overview of OLSRv2, and section III specifies the proposed modification to the IP datagram transmission mechanism, denoted "Link Buffering", for allowing delay tolerant message delivery. The "PopUp" network mobility model is proposed in section IV. Section V presents a performance evaluation of the delay-tolerance mechanism in OLSRv2-routed networks simulated when exposed to the PopUp network mobility model. Section VI concludes the paper.

II. OLSRV2 OVERVIEW

The Optimized Link State Routing Protocol version 2 (OLSRv2) [?], [?], [?], [?] is a successor to the widely deployed OLSR [?] routing protocol for MANETs. OLSRv2 retains the same basic algorithms as its predecessor, however offers various improvements, e.g., a modular and flexible architecture, and in particular a flexible message format [?] by way of TLVs, allowing extensions, such as for security, to be developed as add-ons to the basic protocol whilst retaining backwards and forwards compatibility. OLSRv2 contains three basic processes: Neighborhood Discovery, MPR Flooding and Link State Advertisements. The basic operation of OLSRv2 is detailed in section II-1 to II-3 below.

1) Neighborhood Discovery (NHDP): The process, whereby each router discovers the routers which are in direct communication range of itself (1-hop neighbors), and detects with which of these it can establish bi-directional communication, as well as detects its 2-hop neighbors. This, by way of a periodic HELLO message exchange, as specified in [?]. NHDP enables routers to apply a hysteresis mechanism for determining when to admit the link to a given neighbor, as well as the ability to signal a link no longer satisfactory as "LOST", triggering recalculation of MPRs and possibly renewed Link State Advertisement.

2) MPR Flooding: The process whereby each router is able to, efficiently, conduct network-wide broadcasts. Each router designates, from among its bi-directional neighbors, a subset (MPR set) such that a message transmitted by the router and relayed by the MPR set is received by all its 2-hop neighbors. MPR selection is encoded in outgoing HELLOs.

3) Link State Advertisement: The process whereby routers are determining which link state information to advertise through the network. Each router must advertise links between itself and its MPR-selector-set, in order to allow all routers to calculate shortest paths. Such link state advertisements, carried in TC messages, are broadcast through the network using the MPR Flooding process. As a router selects MPRs only from among bi-directional neighbors, links advertised in TCs are also bi-directional. TC messages are sent periodically, however certain events may trigger non-periodic TCs.

III. LINK BUFFERING

This section proposes a link buffer mechanism, based on [?], which allows delaying datagram transmission when the ultimate destination is (temporarily) unavailable in a router's routing table -and then transmit that datagram later, once the destination re-appears.

A. IP Buffering

Traditional IP datagram transmission considers, essentially, two "states" for any destination: either a route exists (transmit) or no route exists (drop). The proposed mechanism changes the default behavior of "drop" to "buffer datagrams for expected later delivery". Table I lists the different states, combined with the appropriate action to be taken. Whenever a routing protocol adds or modifies a route to a destination, all buffered IP datagrams to that destination are retransmitted.

B. L2 Buffering

A variant of the mechanism described in section III-A is to consider a third state in addition to "no route" and "route valid", called "route invalid". This state corresponds to the situation where a destination is believed to be present in the network, although the previously selected "next hop" is currently unavailable. This variant requires the link layer (L2) to be aware of, and able to signal to the network layer and the routing table if transmissions to the next hop fail, i.e. the link to the next hop is disconnected. For example, 802.11 [?] applies such a mechanism using acknowledgments: if a frame is not acknowledged by the destination (of the frame, i.e., the ultimate destination or the intended next-hop), the frame is dropped (after a bounded number of failed attempts with an exponential back-off mechanism). If such a L2 mechanism is in place, IP datagrams can also be buffered in the "route invalid" state. If no valid route exists (state "valid route available?"), the behavior depends on whether the router is the source of the datagram or not. If yes, the datagram is buffered, otherwise it is dropped. The rationale for this differentiation is provided in section III-D. D. Buffering at Intermediate Hops IP datagrams may traverse several hops (i.e. several routers) from the source to the destination. Invalid routes can appear at any of these routers -in part, as routing protocols do not converge instantaneously on all routers. Typically, the further a router is away from a destination (in terms of hops), the longer is the convergence time for that destination 1 . Thus, it is possible that a router forwarding an IP datagram still has a valid route to the destination and forwards it, while another router further along the path towards the destination has a fresher information about that destination and is aware that the destination is no longer available.

C. Flow Chart

Consequently, buffering could be performed at any of these "intermediate" routers, however such may lead to a large demand of memory on some routers that are bottlenecks in the network. Consider the example in figure 2, where the gray router (called 'I') buffers datagrams if it does not have a valid routing table entry for their ultimate destinations -requiring vast amount of memory in 'I', or provides a target for denialof-service attacks. While these reasons may make it undesirable to allow buffering in intermediate routers, the performance of this mechanism is also evaluated in section V.

IV. MODEL DESCRIPTION

In order to test the link buffering mechanism presented in section III in extreme conditions (i.e. where the end-toend delivery ratio of IP datagrams is otherwise low without such a mechanism), the "PopUp" network mobility model is proposed.

The PopUp mobility model is defined as follows: every router in a MANET has two conjunct states (as depicted in figure 3): enabled and disabled.

Whenever a router is "enabled", it operates as usual, i.e., it may exchange control messages of a routing protocol, send and receive data traffic etc. In this state, the router does not move. The router remains for a certain time (denoted enabled_time) in this state. It then switches to the "disabled" state which may involve a change in position: the router can move up to a certain upper bounded distance (denoted max_distance) with infinite speed.

If a router is "disabled", it cannot send or receive any messages from the network (neither data nor control traffic). The router can be considered as being "switched off" and is thus completely unresponsive to any network events. The router stays a maximum time of disabled_time in that state until it returns to the "enabled" state. Note that both enabled_time and disabled_time can be infinite, i.e., that a router can remain in either of these states forever.

Figure 4 depicts an exemplary MANET that behaves according to the above-mentioned PopUp mobility model. At time t 0 , routers 1 to 4 do not move and are all enabled which means they operate as expected, possibly exchanging control and data traffic. In the figure in the middle at time t 1 , router 4 becomes This section presents a performance evaluation of unicast data traffic in OLSRv2-routed MANETs, both with and without the link buffering mechanism described in section III. The performance evaluation is undertaken by way of NS2 simulations. Typical metrics such as delivery ratio of data traffic, control traffic overhead, average path length and delay of data traffic are considered.

A. God Routing Protocol

In order to provide an upper bound in terms of delivery ratio for the simulated scenarios, a "God routing protocol" (denoted "GodRP") has been implemented. The routing protocol uses the "God" object of NS2, and calculates routes to all destination based on their position and radio range, instantaneously and without any signaling. The expected performance of the GodRP is close to the best possible routing protocol, which helps to understand how well a routing protocol could theoretically perform2 .

A variation of the GodRP is included in the simulation as well, which performs link buffering as described in section III, denoted "GodRP-LB". Note that the variant with link buffering (LB), does not represent an upper bound in terms of data delivery ratio, illustrated in figure 5. Four routers run a link

1 2 3 4 1 2 3 4 1 2 3 4 t 0 t 1 t 2
Figure 5. GodRP with link buffering ("GodRP-LB") does not represent an upper bound in terms of data delivery ratio for routing protocols with link buffering state routing protocol and are arranged in a "strip" topology at time t 0 . Router 1 sends unicast data traffic to router 4. At time t 1 , the link between router 3 and 4 breaks. Due to the non-zero convergence time of link state routing protocols, router 1 may still have a valid route to 4, so it transmits the datagrams. When router 3 receives the datagrams (after being forwarded by router 2), it may have a fresher information about the disconnected link to 4. If no intermediate buffering is used, it will drop the datagram. However, when using intermediate buffering, the datagram is buffered, and delivered later (at time t 2 ). Using GodRP-LB, the datagram will never be delivered in this example from t 1 : at t 1 , router 1 will be immediately informed about the link disconnection between 3 and 4, so router 1 will buffer all datagrams. Since at t 2 , router 1 is not longer connected to 2, datagrams will not reach their final destination, router 4.

B. Graceful Shutdown

In the performance evaluation, a variation of OLSRv2 with link buffering as considered: if a router is gracefully shutdown when transiting from "enabled" to the "disabled" state, it sends a HELLO to inform neighbors that links to the router shutting down should be considered as unavailable. Figure 6 depicts the graceful shutdown process. At time t 0 , all three routers are in the "enabled" state. In the periodic HELLO messages from router 2, it will list both router 1 and 3 as symmetric (SYM) neighbors. Thus, router 1 will list 2 as symmetric neighbor, and 3 as two-hop neighbor reachable via 2. When router 2 is about to be shut down at time t 1 , it sends a HELLO message with all neighbors listed as LOST. Thus, router 1 will remove the 2-hop neighbor entry, and set the link status towards router 2 to HEARD. In addition, router 1 may trigger a HELLO message (and possibly a TC message, if it was selected as MPR by router 2), advertising the lost link.

Without the graceful shutdown mechanism, router 1 would have listed 2 as symmetric neighbor until the link expired. Thus, the graceful shutdown mechanism effectively reduces the convergence time of the routing protocol.

C. Simulation Settings

NS2 simulations settings are summarized in table II. Routers behave according to the PopUp mobility model as defined in section IV, in a square area of 1000x1000 meters. On average, the data traffic load is five concurrent CBR streams of 3.2 kB/s between random pairs of routers. The simulation time is 300 seconds, and each data point presented is an average over 30 runs of different scenarios, corresponding to the same abstract scenario description. A random seed was used for every simulation.

The following routing protocol variants are compared: OL-SRv2, OLSRv2 with link buffering on L3 only ("OLSRv2-L3-LB"), OLSRv2 with link buffering ("OLSRv2-LB"), OLSRv2 with link buffering and graceful shutdown ("OLSRv2-LBgf"), OLSRv2 with link buffering also at intermediate routers ("OLSRv2-IM-LB"), the God routing protocol ("GodRP"), God routing protocol with link buffering ("GodRP-LB").

At the beginning of the simulation, all routers are in either "disabled" or "enabled" state randomly with a random enabled_time or disabled_time left before the next state transition.

D. Simulation Results

Figure 7 depicts the unicast data delivery ratio. The God routing protocol -not surprisingly -has a higher delivery rate than OLSRv2, which is due to the zero-convergence time and less collisions due to the lack of control traffic. However, even with the GodRP, no more than a 35% of delivery ratio with 70 routers is reached. This is because the network, by design, is not fully connected in the PopUp model. The link buffering variants result in significantly higher delivery ratios, with GodRP with link buffering producing the highest data delivery ratio. OLSRv2 with intermediate link buffering produces a data delivery ratio close to that of GodRP-LB. Due to the nonzero convergence time of OLSRv2, buffered datagrams will be delivered only a bit later than with the link buffering variant of the GodRP (which can be observed in figure 8). OLSRv2 without intermediate link buffering has a significantly lower delivery ratio, whereas the graceful shutdown mechanism has a positive effect on the delivery ratio due to the reduced convergence time. Figure 8 depicts the average delay from the moment a datagram has been sent until it arrives at its destination. The delay largely depends on the selected enabled_time and disabled_time values. All buffering variants have significantly higher delays than standard OLSRv2 (at the benefit of a higher delivery ratio). The different buffering variants lead to similarly high delay, however, the delay of OLSRv2-IM-LB is significantly higher than the other protocols. This can be explained with the increased routing stretch -paths towards the destination are longer, as observed in figure 9. Figure 9 presents the average path length of every data packet from its source to its destination. OLSRv2 has the shortest paths; this can be explained by the lowest delivery ratio amongst the compared protocols (as depicted in figure 7) -destinations further away from the source receive fewer of the transmitted datagrams. For the same reason, the other link buffering variants have a lower path length than GodRP-LB. Comparing GodRP-LB and OLSRv2-IM-LB (which both have similar delivery ratios as shown in figure 7), the path stretch of OLSRv2-IM-LB can be clearly observed. Figure 10 shows the accumulated control traffic overhead over the simulation time (GodRP is not included, because the overhead is 0). Not surprisingly, the different link buffering variants of OLSRv2 have no influence on the control traffic. The graceful shutdown mechanism includes transmitting additional HELLOs before shutdown of a router, plus possibly triggered HELLOs and TCs of neighbors of that router.

Figure 11 shows the total number of dropped frames because of collisions during the simulation. For GodRP, almost no collisions appear, since no control traffic congests the network and only little unicast traffic is injected into the network. OLSRv2 without link buffering has the lowest number of collisions, increasing with a growing number of routers in the network -the increasing amount of control traffic leads to most of the collisions. All link buffering variants have a higher collision ratio, which can be explained by the fact that once a router reappears (i.e. changes its state from "disabled" to "enabled"), all datagrams from different sources that have been buffered while it was "disabled", are retransmitted almost the same time, as soon as valid routes towards that destination router are added to the routers that had buffered the datagrams. Again, collisions due to increasing control traffic explain the difference between the link buffering variants of OLSRv2 and GodRP-LB with higher number of routers. The bottleneck effect, that has been described in section III-D, can be well observed due to the large number of collision when applying intermediate buffering (OLSRv2-IM-LB). The fact that despite the high number of collision with OLSRv2-IM-LB, the delivery ratio (as depicted in figure 7) is still the highest amongst the OLSRv2 variants, can be explained by the retransmission mechanism of 802.11 [?]. Even if more frames are lost due collisions on L2, eventually one may reach the destination if the frame (i.e. the next hop along the route). Figure 12 depicts the total accumulated overhead of unicast data traffic, when counting each L2 (re-)transmission at every router along the path from source to destination.

It can be seen that OLSRv2-IM-LB produces the highest control traffic overhead: The higher delivery ratio despite the higher collision ratio comes at the expense of available bandwidth on the channel. VI. CONCLUSION This paper has proposed a "link buffering" mechanism, allowing a router to delay the transmission of an IP datagram if there is no valid route to the destination of that datagram at transmission time, and which is able to complement an offthe-shelf MANET routing protocol for increasing end-to-end delivery ratio of datagrams, at the expense of higher delay. In order to test that mechanism, a network mobility model, denoted the "PopUp model" is specified: routers can be either "enabled" or "disabled". In the "disabled" state, routers cannot send or receive any data, but are allowed to change position within a bounded distance.

The off-the-shelf MANET routing protocol OLSRv2 is studied, by way of NS2 simulations, with different variations of the link buffering mechanism and when subject to the PopUp model. These simulations have shown that when using a "link buffering" mechanism, the data delivery ratio can be largely improved. Among the variations of the link buffering mechanism are a variant with buffering on layer 3 only (denoted "OLSRv2-L3-LB"), link buffering on layer 2 and 3 (denoted "OLSRv2-LB"), link buffering on intermediate routers (denoted "OLSRv2-IM-LB"), and a variant with a graceful shutdown mechanism (denoted "OLSRv2-LB-gf"). All link buffering variants yield a much higher end-to-end delivery ratio than without using such a mechanism, but also incur an increased end-to-end delay.

Figure 1

 1 Figure 1 depicts the proposed mechanism, for both IP and L2 link buffering. When a datagram is to be forwarded by a router (state "Datagram to be forwarded"), the router verifies whether it has a route towards the destination. If yes, it hands the datagram off for transmission (states "Send datagram" and "Datagram arrives at L2"). If the datagram cannot be sent successfully (e.g. no ACK has been received), the datagram is buffered.If no valid route exists (state "valid route available?"), the behavior depends on whether the router is the source of the datagram or not. If yes, the datagram is buffered, otherwise it is dropped. The rationale for this differentiation is provided in section III-D.

Figure 1 .

 1 Figure 1. Link buffering process for L3 and L2

Figure 2 .

 2 Figure 2. The gray router buffers datagrams that it forwards from the left side to the right side of the network (and vice verse)

Figure 3 .

 3 Figure 3. State diagram of the PopUp model

  Figure 4. Example of the PopUp mobility model

  Figure 6. Graceful shutdown

Figure 7 .

 7 Figure 7. Unicast data delivery ratio

Figure 8 .

 8 Figure 8. Average delay per datagram

  Figure 9. Path length

Figure 10 .

 10 Figure 10. Accumulated control traffic overhead

  Figure 11. Collisions

Figure 12 .

 12 Figure 12. Accumulated unicast traffic overhead (counting each transmission at every router)

Table I LINK BUFFERING STATES AND ACTIONS

 I

	State	Description	Action
	No Route	No routing information is	Buffer IP Datagrams
		available for this destination
	Route Valid A route entry exists for this	Transmit IP Datagrams
		destination, and the link to the
		next hop towards this destina-
		tion is not disconnected

Unless there are unstable links to a "close" destination in terms of hop count, and stable links to a destination far away

In some cases, a perfect routing protocol would perform better by dropping some packets even if actually routable, e.g. to destinations further away in cases of massive load on the channel. This may lead to a higher delivery ratio for destinations close to the router (i.e. neighbors) if the transmissions contend for the channel.


Ulrich Herberg
email: ulrich@herberg.name

Thomas Clausen
email: thomas@thomasclausen.org

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

Keywords: C.2.2 [Network Protocols]: Routing protocols -RPL, LOAD, IETF, LLN, evaluation, simulation, comparison, bidirectional traffic, sensor networks

Routing protocols for sensor networks are often designed with explicit assumptions, serving to simplify design and reduce the necessary energy, processing and communications requirements. Different protocols make different assumptions -and this paper considers those made by the designers of RPL -an IPv6 routing protocol for such networks, developed within the IETF. Specific attention is given to the predominance of bi-directional traffic flows in a large class of sensor networks, and this paper therefore studies the performance of RPL for such flows. As a point of comparison, a different protocol, called LOAD, is also studied. LOAD is derived from AODV and supports more general kinds of traffic flows. The results of this investigation reveal that for scenarios where bi-directional traffic flows are predominant, LOAD provides similar data delivery ratios as RPL, while incurring less overhead and being simultaneously less constrained in the types of topologies supported.

INTRODUCTION

Sensor networks differ from more "traditional networks" in that the devices making up a sensor network have connectivity maintenance and data forwarding as auxiliary tasks to their primary raison d'être, such as data acquisition. Ignoring the applications, the network itself can be described by (i) the devices being many thousands in number, (ii) with very limited internal (memory, CPU), external (communications capacity) and energy resources, and that (ii) the communications channel between devices typically has unattractive characteristics: low-bandwidth, high loss-rates and volatile links with limited persistency over time. The term Low-power Lossy Networks (LLN) is therefore commonly used for describing such networks.

Yet, despite these challenges, routing protocols are required for establishing and maintaining multi-hop connectivity in LLNs, for situations where it is unfeasible or impossible to provision a sensor network deployment such that all devices, necessitating communication between each other, are within direct connectivity.

Background

The Internet Engineering Task Force (IETF) [START_REF]IETF[END_REF] has a long tradition of developing and standardizing routing protocols. Initially, for fixed Internet infrastructures, where the conditions are more lenient than in LLNs: routers generally have abundance of computational capacity and few energy constraints, links are predominantly "good" with few lossesand while Internet routing protocols such as OSPF are able to handle some network topology changes, these are generally rare, and generally occur only as a result of relatively catastrophic events: a cable being cut, for example.

In the late 1990'es, the IETF started investigating MA-NETs [START_REF]IETF MANET working group[END_REF] -Mobile Ad hoc NETworks. Generally thought of as multi-hop wireless networks of mobile devices, a crop of routing protocols were developed and standardized, notably OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] and AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] 1 . Able to manage more dynamic topologies and the characteristics of wireless network interfaces, this work introduced a new dichotomy in routing protocol classification: OLSRv2 [START_REF] Clausen | The Optimized Link-state Routing Protocol version 2. Internet Draft[END_REF] being a classic linkstate routing protocol, optimized for MANETs, it maintains paths to all destinations at all times, and this even before such paths are needed -proactively. AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] approached the same problem in a different fashion, by discovering and maintaining paths to destinations only as needed by application traffic -reactively. For both, however, the assumption was that while the network topology might be dynamic and the wireless connectivity volatile, the devices in the network still had a relative abundance of both computational power and energy.

With the emergence of sensor networks, so did the challenge to the assumption of an abundance of computational power and energy -even transmitting an IPv6 packet with 128-bit long addresses was considered a strain in terms of energy consumption, and so the IETF started investigating adaptations of IPv6 for LLNs: compressing addresses, removing options considered rarely used, simplifying packet processing etc. Routing protocols, even those developed for MANETs, were considered too heavy and work started around 2005 on IPv6-based routing protocols, adapted for LLNs -formalized by the IETF with the creation of a ROLL ("Routing Over Low-power and Lossy networks") Working Group [START_REF]IETF ROLL working group[END_REF] specifically for managing this development work. This Working Group produced a protocol denoted RPL ("Routing Protocol for Low-power and lossy networks") [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF].

Sacrifices

While the development from fixed Internet infrastructure routing protocols such as OSPF and BGP to MANET routing protocols such as OLSR and AODV was accomplished by way of algorithmic optimizations e.g., on the overhead incurred by sharing link-state information network-wide, MA-NET protocols remained relatively general routing protocols -in particular, MANET routing protocols provide full IP support and adhere to the "anybody can communicate with anybody" paradigm.

The development towards LLN routing protocols, on the other hand, came with sacrifices in generality: assumptions as to which options in IPv6 headers were to be supported, as well as optimization of routing protocol operation for specific traffic patterns, considering certain such esoteric enough so as to not merit special attention. The ROLL Working Group, in its design of RPL, made a set of such assumptions, notably that sensor-to-controller traffic (multipointto-point) is predominant, controller-to-sensor traffic (pointto-multipoint) is rare and sensor-to-sensor traffic (point-topoint) is somewhat esoteric. RPL in its design, therefore, optimizes for multipoint-to-point traffic, supports in a less optimized fashion point-to-multipoint and provides some basic mechanisms for point-to-point traffic -essentially transiting such point-to-point traffic between two sensors via the controller.

Motivation

The traffic patterns for which RPL optimizes are, unquestionably, reasonable in some scenarios: data acquisition networks, for example, where sensors monitor an environment and transmit their findings towards a central controller, and where traffic from the controller to a sensor is a rare occurrence. They are, however, not universal. There are scenarios in which sensor-to-sensor traffic is assumed to be the more common pattern, such as [START_REF] Martocci | Building Automation Routing Requirements in Low Power and Lossy Networks[END_REF]. Another example is in utility metering, where a utility company may wish to have a controller inquire household meters as to their consumptionsend a request and expect a reply -or even may use the network to change parameters in household meters (expecting a confirmation). An example hereof is for load management on a power-grid, where a controller may wish to instruct individual households to reduce (or increase) their consumption according to the overall load on the grid. Even data acquisition type networks may have this characteristics: a sensor detecting an abnormal condition may signal thisneeding to be certain that the signal has been received and thus expecting a confirmation.

Thus, even if assuming that point-to-point between sensors inside the network is relatively rare, bi-directional communication between sensors and a controller should be assumed common. In terms of the assumptions on traffic patterns, made in the design of RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF], this entails that equal importance should have been given to point-to-multipoint and multipoint-to-point traffic.

Statement of Purpose

Thus, one purpose of this paper is to explore the performance of LLN routing protocols for scenarios where bidirectional traffic is prevalent, in particular understanding the behavior of RPL, and the viability of the sacrifices made in generality by the design of that protocol, when exposed to this common traffic pattern. A second purpose is to explore how a more general protocol, LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing (LOAD)[END_REF], behaves when exposed to the same traffic patterns -both as a point of comparison, and as a way of exploring the viability of that protocol for LLNs. LOAD is a protocol, derived from AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] by simplifying some mechanisms (detailed in section 3) while retaining the generality of supporting all traffic patterns equally and provisioning all paths to be bidirectional.

The rationale for choosing RPL and LOAD for a performance comparison is that RPL is a new protocol just standardized by the IETF as the standard routing protocol for LLNs, whereas LOAD is closely derived from AODV. AODV has been standardized by the IETF in 2003, and since then, researchers and engineers have gained a profound experience with the protocol. Comparing RPL with LOAD can therefore help to discover weaknesses of either of the protocols and possibly to improve them in a future work.

Paper Outline

Section 2 presents a functional overview of RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. Section 3 similarly provides a functional overview of LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing (LOAD)[END_REF]. Section 4 performs a comparative study of these. Section 5 concludes this paper.

RPL OVERVIEW

The basic construct in RPL is a "Destination Oriented Directed Acyclic Graph" (DODAG), depicted in figure 1. In a converged LLN, each RPL router has identified a stable set of parents, each of which is a potential next-hop on a path towards the "root" (or "controller") of the DODAG, as well as a preferred parent. Each router, which is part of a DODAG (i.e. has selected parents) will emit DODAG Information Object (DIO) messages, using link-local multicast, indicating its respective rank in the DODAG (i.e. distance to the DODAG root according to some metric(s), in the simplest form hop-count). Upon having received a number of such DIO messages, a router calculates its own rank such that it is greater than the rank of each of its parents, select a preferred parent and then start emitting DIO messages.

The DODAG formation thus starts at the DODAG root (initially, the only router which is part of a DODAG), and spreads gradually to cover the whole LLN as DIOs are received, parents and preferred parents are selected and further routers participate in the DODAG. The DODAG root also includes, in DIO messages, a DODAG Configuration Object, describing common configuration attributes for all RPL routers in that network -including their mode of operation, timer characteristics etc. RPL routers in a DODAG include a verbatim copy of the last received DODAG Configuration Object in their DIO messages, permitting also such configuration parameters propagating through the network. A Distance Vector protocol, RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] restricts the ability for a router to change rank. A router can freely assume a smaller rank than previously advertised (i.e. logically move closer to the root) if it discovers a parent advertising a lower rank, and must then disregard all previous parents of higher ranks. The ability for a router to assume a greater rank (i.e. logically move farther from the root) than previously advertised is restricted, to avoid count-to-infinity problems. The root can trigger "global recalculation" of the DODAG by increasing a sequence number, DODAG version, in DIO messages.

The DODAG so constructed is used for installing routes: the "preferred parent" of an RPL router can serve as a default route towards the root, or the root can embed in its DIO messages the destination prefixes, included by DIOs generated by RPL routers through the LLN, to which connectivity is provided by the root. Thus, RPL by way of DIO generation provides "upward routes" or "multipoint-to-point routes" from the sensors inside the LLN and towards the root.

"Downward routes" are enabled by having sensors issue Destination Advertisement Object (DAO) messages, propagating as unicast via parents towards the DODAG root. These describe which prefixes belong to, and can be reached via, which RPL router. In a network, all RPL routers must operate in either of storing-mode or non-storing-mode, specified by way of a "Mode of Operation" (MOP) flag in the DODAG Configuration Object from the root. Depending on the MOP, DAO messages are forwarded differently towards the root:

• In non-storing-mode, an RPL router originates DAO messages, advertising one or more of its parents, and unicasts it to the DODAG root. Once the root has received DAOs from an RPL router, and from all routers on the path between it and the root, it can use source routing for reaching advertised destinations inside the LLN.

• In storing-mode, each RPL router on the path between the originator of a DAO and the root records a route to the prefixes advertised in the DAO, as well as the nexthop towards these (the router from which the DAO was received), then forwards the DAO to its preferred parent.

"Point-to-point routes", for communication between devices inside the LLN and where neither of the communicating devices are the DODAG root, are as default supported by having the source sensor transmit 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 for reaching the destination sensor (downward routes in nonstoring-mode) or simply use hop-by-hop routing (downward routes in storing-mode). In the case of storing-mode, if the source and the destination for a point-to-point communication share a common ancestor other than the DODAG root, a downward route may be available (and used) before reaching the DODAG root.

RPL Message Emission Timing -Trickle

RPL message generation is timer-based, with the root able to configure back-off of message emission intervals using Trickle [START_REF] Levis | Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks[END_REF], specified in [START_REF] Levis | The Trickle Algorithm[END_REF]. Trickle, as used in RPL, stipulates that a RPL router transmits a DIO "every so often"except if receiving a number of DIOs from neighbor routers, enabling the router to determine if its DIO transmission is redundant.

When an RPL router transmits a DIO, there are two possible outcomes: either every neighbor router that hears the message finds that the information contained is consistent with its own state (i.e., the received DODAG version number received corresponds with that which the RPL router has recorded and no better rank is advertised than that which is recorded in the parent set) -or, a recipient RPL router detects that either the sender of the DIO or itself has out-ofdate information. If the sender has out-of-date information, then the recipient RPL router schedules transmission of a DIO to update this information. If the recipient RPL router has out-of-date information, then it updates based on the information received in the DIO.

With Trickle, an RPL router will schedule emission of a DIO at some time, t, in the future. When receiving a DIO containing information consistent with its own information, the RPL router will record that "redundant information has been received" by incrementing a redundancy counter, c. At the time t, if c is below some "redundancy threshold", then it transmits its DIO. Otherwise, transmission of a DIO at this time is suppressed, c is reset and a new t is selected to twice as long time in the future -bounded by a pre-configured maximum value for t. If, on the other hand, the RPL router has received an out-of-date DIO from one of its neighbors, t is reset to a pre-configured minimum value and c is set to zero. In both cases, at the expiration of t, the RPL router will verify if c is below the "redundancy threshold" and if so transmit -otherwise, increase t and stay quiet.

LOAD OVERVIEW

LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing (LOAD)[END_REF] is a protocol, derived from AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] and adapted for LLNs. Thus, the basic operation of LOAD is identical to that of AODV: a device with a packet to deliver to a destination, and which does not have a valid entry in its routing table for that destination, will issue a routerequest (RREQ) message, diffused through the network so as to reach all other devices. When a device forwards this route-request, it records an entry in its routing table towards the originator of that route-request -a reverse route indicating the eventual path from the destination to the originator. If the destination is present in the network, it will eventually receive the route-request -and will respond by a route-reply (RREP), unicast to the originator of the routerequest along the previously installed reverse route. As that route-reply is being forwarded along this reverse route, the devices forwarding it will instill a forward route towards the destination. Once the route-reply arrives at the originator of the corresponding route-request, a bi-directional path is installed, available for use.

When a link is detected to be broken (typically through a link-layer notification of a data-packet failing to be delivered to a next hop), the detecting router may engage in a routerepair operation -essentially a new route-request/route-reply cycle to discover a path to the destination -and if that fails, issue a route-error (RERR) message to inform the source of the failed data-packet of the error.

While this route discovery is performed, any IP-packets to the destination are buffered in the source router. When a route is established, these packets are transmitted -and if no route can be established, they are dropped.

The main differences between AODV and LOAD are:

1. LOAD simplifies the protocol behavior by disallowing that intermediate devices respond with a route-replyeven if they have an active route to the intended destination -thereby eliminating the need for destination sequence numbers.

2. Where in AODV, in case a device detects a link breakage, that device will attempt to transmit the routeerror message to all neighbors which have recently used it as a next-hop on a path to the destination of the undelivered package, LOAD disables that -thereby eliminating the need to a device to maintain a precursor list.

Other, minor, differences include simplification of the packet format, support for compressed IPv6 addresses [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE[END_REF] etc.

LOAD does not impose any specific roles on any specific devices, notably has no controller or root with specific responsibilities for the network operation. Thus, the default traffic pattern supported by LOAD is bi-directional pointto-point traffic. The one sacrifice that LOAD makes with respect to data traffic, in simplifying from AODV, is, that it assumes that a given destination typically is in communication with only a single source at a given time -hence, the suppression of the precursor list.

EVALUATION

In order to understand the performance of both RPL and LOAD in LLNs with bidirectional traffic, a simulation study using the Ns2 simulator has been conducted. Standard evaluation metrics, such as data traffic delivery ratio, control traffic overhead, number of collisions, network convergence time etc. are compared between the two protocols. Energy consumption of the two protocols was out of the scope of this paper, as the energy consumption largely depends on the underlying hardware, and can therefore hardly be quantified in network simulations. As in particular receiving and sending messages on the network interfaces drains energy from the device, the energy consumption is related to the quantity of the control traffic overhead of the routing protocol, as well as data traffic. Section 4.1 describes the simulation settings and section 4.2 presents the results of the evaluation.

Simulation Settings

The specific settings of the scenarios studied are detailed in table 1. For each datapoint, the values have been averaged over 10 runs. Both LOAD and RPL have been implemented in Java, using the AgentJ framework [START_REF] Herberg | Development Framework for Supporting Java NS2 Routing Protocols[END_REF] to hook the Java code into Ns2. The routers were placed randomly in a square area of variable size, with a density of 50 routers per km 2 . Only scenarios were selected where all routers are in the same connected component.

The bidirectional traffic patterns consisted of a "reading scenario", where the controller collects information from all sensors in the network, within 24 hours. Delay of the replies was considered irrelevant, as long as all sensors have replied within the 24 hours. In the Ns2 simulation, the controller sends a single request to each sensor (one datagram, 11 octets payload), to which the sensor replies with a single data packet (100 octets payload).

The settings for RPL are listed in table 2, and for LOAD in table 3. The simulation time was 24 hours for LOAD, and 270 seconds for RPL. The reason for not choosing 24 hours for RPL as well is the required amount of time for conducting the simulation: as DAO messages are sent periodically in the simulation, even if no data traffic occurs in the network, the required amount of time to conduct the simulation would take several days for a single simulation run. Moreover, trace files would grow to hundreds of Gigabytes per simulation. As in LOAD no control traffic is sent when no data traffic is sent, the simulation runs considerably faster, tocols. One possible difference, however, could be fragmentation when using smaller MTUs, such as in 802.15.4, as described in [START_REF] Clausen | A Critical Evaluation of the "IPv6 Routing Protocol for Low Power and Lossy Networks[END_REF].

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. The control traffic overhead of RPL can be extrapolated from 270s to 1 day, as DAO messages are sent periodically.

For RPL, the first traffic request from the controller is sent at 60s after the the start of the simulation, allowing RPL to converge (i.e., to construct the DODAG) before. Once the sensor receives the data request, it replies immediately. The following data request from the controller to the next sensor is sent 0.1 seconds after the previous data request. For simulations with 1000 routers, the last data request from the controller will thus be sent at 160 seconds after the simulation start (60s + 999 • 0.1s).

For LOAD, the traffic requests are sent every 30 seconds, starting at 100 seconds after simulation start, i.e., the last request is sent at 30070 seconds or 8.35 hours after the simulation start. In order to reduce the amount of collisions of frames, a random jitter has been added before forwarding a RREQ on a router, as specified in [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF]. While this is not specified in the current revision of LOAD, it could be added in a future revision, similar to other current ad hoc routing protocols like OLSRv2 [START_REF] Clausen | The Optimized Link-state Routing Protocol version 2. Internet Draft[END_REF].

During the simulation, only a single traffic flow from the controller towards a sensor vice is active, i.e., only a single route has to be maintained on a router running LOAD (assuming that routes expire before the next data packet is transmitted). In the investigated "reading scenario", this does not represent an unrealistic setting, since every sensor is only contacted once in 24 hours by the controller. As a consequence, both RPL in non-storing mode and LOAD require minimal state on the routers.

Simulation Results

This section describes the results of the simulation. Figure 2 shows the maximum and average rank of routers in the DODAG, where the number represents the distance of a router to the controller in terms of hops (i.e. the maximum rank represents the diameter of the network, the average rank represents the average over all routers). The maximum and average ranks grow logarithmically with the number of routers in the network. the time that is needed for all routers that are in the same connected component as the controller to join the DODAG. Since each router starts sending DIOs two seconds after the last change to its Candidate Neighbor Set, the convergence time is roughly two seconds times the maximum rank of the DODAG. The convergence time grows logarithmically with the number of routers in the network. for LOAD. Each forwarding of a broadcast packet is counted separately, e.g., a RREQ in LOAD that is flooded from the controller to n other sensors, counts for n • sizeof (RREQ) bytes. It can be observed that for both protocols, the control traffic overhead increases polynomially with the amount of routers, and that RPL leads to more than twice the amount of the control traffic as LOAD. For RPL, the periodic DAOs account for the majority of the control traffic, whereas the overhead of DIOs is much lower due to the exponentially growing emission intervals of the Trickle timer. For LOAD, the broadcast RREQs lead to a much higher overhead than the unicast RREPs. It has to be noted that the control traffic overhead of LOAD, as for any reactive routing protocol, depends on the data traffic in the network (as well as the validity time of the routes and the dynamicity of the network topology). The control traffic overhead of RPL, as a proactive protocol, does not depend on the data traffic.

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. Figure 6 depicts the extrapolated control traffic amount of DAOs and RREQs (which account for the majority of the control traffic, as described above). The overhead for the RREQs is the same as in figure 5, as the emission of RREQs only depends on the data traffic. The overhead of RPL is two orders of magnitude higher than the overhead of LOAD.

Figure 7 shows the data traffic in number of frames that is sent from the controller to each sensor. Evidently, as one single frame is sent per router, the total overhead consists of n -1 frames for n routers.

However, as shown in figure 8, the cumulative amount of data traffic in terms of bytes is different for RPL and LOAD, where each forwarding of a packet is counted. The overhead Figure 9 shows the path length of the data traffic, for both RPL and LOAD, as well as for a protocol called "God". The God routing protocol uses the "God" object of Ns2, in order to calculate routes to all destinations based on their position and radio range, without any control message exchange and zero convergence time. The expected performance of the GodRP is close to the best possible routing protocol, which helps to understand how well a routing protocol could theoretically perform. It can be observed that LOAD chooses longer paths than RPL, which itself is close to the optimum. Two reasons can explain the longer paths of LOAD:

1. When a router receives a RREQ that is destined to itself, it will reply to the first incoming RREQ and set the reverse route towards the last hop of that RREQ. However, it may happen that shorter paths are available, but that the RREQ for that shorter path arrives only later (and since only a single data packet is sent, the better path will not be used). If the router had waited longer, before replying with a RREQ, it could have chosen a shorter path, at the expense of a higher delay.

2. As LOAD in its basic form applies "Classic Flooding" for distributing the RREQs throughout the network, longer paths occur than e.g., when using MPR flooding, which leads to optimal paths ( [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF]).

An observation concerning the path length can be made for RPL in non-storing mode, which uses source routes for the downward traffic: the maximum length of the source routing header [START_REF] Hui | An IPv6 Routing Header for Source Routes with RPL[END_REF] is limited to 136 octets, including an 8 octet long header. As each IPv6 address has a length of 16 octets, not more than 8 hops from the source to the destination are possible for "raw IPv6". Using address compression [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE[END_REF], the maximum path length may not exceed 64 hops. This excludes scenarios with long "chain-like" topologies. The size of the header with increasing length of the source route is depicted in figure 10. For both protocols, it is close to 100%, which is due to the two-ray ground model applied in the simulations. Unless there are collisions on the MAC layer, no packets are lost. This does, of course, not reflect experience from real wireless communication, and has to be considered when interpreting the simulation results. Simulating realistic channel behavior and propagation models is non-trivial, and better observed in real testbeds than in network simulations. Still, the simulation results allow to validate whether the routing protocol choose correct paths. Figure 12 shows the end-to-end delay of a data traffic transmission. Data traffic is buffered in LOAD when no route is available, until a RREP from the destination has been received (or is dropped after a timeout if no RREP is received). The waiting time depends on the number of hops the RREQs and RREPs have to traverse as well as the time required for relaying a packet at a router, and therefore increases with the number of routers in the network. As no buffering is applied in RPL, the delay is much lower. However, in scenarios where delay is negligible -such as the evaluated "reading" scenario within 24 hours -the higher delay may be acceptable. Finally, figure 13 depicts the number of collisions of frames for both RPL and LOAD. As LOAD applies Classic Flooding for the RREQ, the well-known broadcast storm [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF] leads to a higher collision rate in LOAD. A more efficient flooding mechanism could reduce the amount of collisions (as well as the control traffic overhead).

CONCLUSION

RPL and LOAD represent two different philosophies for routing protocols in LLNs. RPL is optimized for specific topologies and traffic patterns -a central controller with specific responsibilities for topology formation and maintenance, and towards which the majority of traffic flows. Thus, the strength of RPL is proactive construction of a collection tree for forwarding such traffic. LOAD represents a perhaps less optimized protocol, however one wherein the philosophy is an entirely distributed mode of operation, where paths are discovered on demand and so as to be bi-directional.

Observing that a large set of deployment scenarios for sensor networks imply the need of bi-directional traffic flowsutility metering, building automation and data acquisition networks where possible alarm signals need be acknowledged -this paper studies the performance of these two protocols in such scenarios. While both protocols are able to provide reasonably high and definitely comparable data delivery ratios, LOAD yields a consistently lower control traffic overhead than does RPL -all the while being less constrained both in terms of traffic types and topologies supported.

While generalizing from simulation studies always is to be done with utmost care -the adage of "show me a protocol, and I will construct a scenario wherein it performs badly", the results presented in this paper nonetheless suggest that for deployments in which bi-directional traffic flows predominate, LOAD is a more evident candidate routing protocol for LLNs than is RPL.

Figure 1 :

 1 Figure 1: RPL Basic Construct: DODAGs

Figure 2 :Figure 3

 23 Figure 2: Maximum and average rank of routersFigure 3 depicts the average number of parents of each router in the DODAG. Keeping the density of the network

Figure 3 :

 3 Figure 3: Average number of parents per router Figure 4 displays the convergence time of the network, i.e.the time that is needed for all routers that are in the same connected component as the controller to join the DODAG. Since each router starts sending DIOs two seconds after the last change to its Candidate Neighbor Set, the convergence time is roughly two seconds times the maximum rank of the DODAG. The convergence time grows logarithmically with the number of routers in the network.

Figure 4 :Figure 5

 45 Figure 4: Network convergence time Figure 5 depicts the cumulative control traffic overhead over the simulation time, i.e., in 270 s for RPL and in 1 dayfor LOAD. Each forwarding of a broadcast packet is counted separately, e.g., a RREQ in LOAD that is flooded from the controller to n other sensors, counts for n • sizeof (RREQ) bytes. It can be observed that for both protocols, the control traffic overhead increases polynomially with the amount of routers, and that RPL leads to more than twice the amount of the control traffic as LOAD. For RPL, the periodic DAOs account for the majority of the control traffic, whereas the overhead of DIOs is much lower due to the exponentially growing emission intervals of the Trickle timer. For LOAD, the broadcast RREQs lead to a much higher overhead than the unicast RREPs.

Figure 5 :

 5 Figure 5: Control traffic overhead

Figure 6 :

 6 Figure 6: Extrapolated control traffic overhead for 24 hours

Figure 7 :

 7 Figure 7: Traffic sent in frames

Figure 8 :

 8 Figure 8: Traffic sent in bytes

Figure 9 :

 9 Figure 9: Path length

Figure 10 :

 10 Figure 10: Source route overhead Figure 11 depicts the delivery ratio of the data traffic.

Figure 11 :

 11 Figure 11: Delivery ratio

Figure 12 :

 12 Figure 12: Delay

  Figure 13: Collisions

Table 1 :

 1 Ns2 parameters

	Parameter	Value
	Mobility scenarios	No mobility, random distri-
		bution of routers
	Grid size	variable
	Router density	50 / km 2
	Number of routers	63 / 125 / 250 / 500 / 1000
	Communication range	250m
	Radio propagation model Two-ray ground
	Simulation time	RPL: 270 secs/LOAD: 1 day
	Interface type	802.11b 2 (2.4 GHz)

Table 2 :

 2 RPL parameters

	Parameter	Value
	Mode of operation	non-storing
	Rank metric	hop count
	DIOIntervalMin	2 s
	DIOIntervalDoublings	20
	DIORedundancyConstant	∞
	DAOInterval	15s
	Table 3: LOAD parameters
	Parameter	Value
	RREQ jitter	0 -0.5 s
	Route lifetime	5 s
	Address compression	2 octets per IPv6 address

And their successors, OLSRv2[START_REF] Clausen | The Optimized Link-state Routing Protocol version 2. Internet Draft[END_REF] and DYMO[START_REF] Chakeres | Dynamic MANET On-demand (DYMO) Routing[END_REF], which are currently being specified by the IETF.

As both RPL and LOAD are agnostic of the underlying link layer, any other link layer, such as IEEE 802.15.4 could be used, with expected similar behavior of the routing pro-