Yoann Desmouceaux
email: yoann.desmouceaux@polytechnique.edu

Pierre Pfister
email: ppfister@cisco.com

Jérôme Tollet
email: jtollet@cisco.com

Mark Townsley
email: mark.townsley@polytechnique.edu

Thomas Clausen
email: thomas.clausen@polytechnique.edu

SRLB: The Power of Choices in Load Balancing with Segment Routing

Network load-balancers generally either do not take application state into account, or do so at the cost of a centralized monitoring system. This paper introduces a load-balancer running exclusively within the IP forwarding plane, i.e. in an application protocol agnostic fashion -yet which still provides application-awareness and makes real-time, decentralized decisions. To that end, IPv6 Segment Routing is used to direct data packets from a new flow through a chain of candidate servers, until one decides to accept the connection, based on its local state. This way, applications themselves naturally decide on how to share incoming connections, while incurring minimal network overhead, and no out-of-band signaling.

Tests on different workloads -including realistic workloads such as replaying actual Wikipedia access traffic towards a set of replica Wikipedia instances -show significant performance benefits, in terms of shorter response times, when compared to a traditional random load-balancer.

I. INTRODUCTION

Virtualization and containerization has enabled scaling of application performance by way of (i) running multiple instances of the same application within a (distributed) data center, and (ii) employing a load-balancer for dispatching queries between these instances.

For the purpose of this paper, it is useful to distinguish between two categories of such load-balancers:

1) Network-level load-balancers, which operate at Layer-4a simple approach being to rely on Equal Cost Multi-Path (ECMP) [START_REF] Thaler | Multipath issues in unicast and multicast nexthop selection[END_REF] to homogeneously distribute network flows between the application instances. These approaches generally do not take application state into account, which can lead to suboptimal server utilization. 2) Application-aware load-balancers, which are bound to a specific type of application or application-layer protocol, and make informed decisions on how to assign servers to incoming requests. These approaches generally incur a cost from monitoring the state of each application instance, and sometimes also terminate network connections (such as an HTTP proxy).

A desirable load-balancer would combine the best of these two categories: be application or application-layer protocol agnostic (i.e. operate at Layer-4) and incur no monitoring overhead -yet be able to make informed dispatching decisions depending on the state of the applications.

A. Statement of Purpose

The purpose of this paper is to propose SRLB, a loadbalancing approach that provides application-state awareness, yet is both application and application-layer protocol independent and does not rely on centralized monitoring or transmission of application state.

A key philosophical argument behind this design goal is that an application instance itself is best positioned to know if it should be accepting an incoming query, or if doing so would degrade performance -and, thus, SRLB discards the traditional design by which queries are unconditionally assigned to an application instance by the load-balancer. Rather, SRLB offers a received query to several application instance candidates, only one of which accepts and processes the query.

What enables this is IPv6 Segment Routing (SR) [START_REF] Filsfils | The segment routing architecture[END_REF] which allows specifying to the network that it should do more than just forward a data packet towards its destination: SR permits directing data packets through an (ordered) set of intermediaries, and instructing these intermediaries what to do with a received data packet. For example, one instruction could be "process the contained query, if you can". All this within the IP forwarding plane, i.e. in an application-layer protocol agnostic fashion.

The role of the load balancer, then, simply becomes to monitor TCP flows, to ensure that data packets belonging to the same flow are delivered to the same application instance as the one which accepted the first packet of the flow.

In this way, SRLB enables that query acceptance decisions are made strictly locally, based on real-time information on the state of the application instance.

B. Related Work

Among existing Layer-4 load-balancing approaches, [START_REF] Eisenbud | Maglev: A fast and reliable software network load balancer[END_REF] (Maglev) and [START_REF] Patel | Ananta: cloud scale load balancing[END_REF] (Ananta) aim at being able to scale the number of load-balancer instances at will, and make use of ECMP to distribute flows between those instances. They also make use of consistent hashing, for ensuring that data packets within a given flow are directed to the same application instance -regardless of the selected load-balancer instance forwarding a data packet, and with minimal disruption when the set of application servers changes. However, flows are distributed to application instances regardless of their current load.

Conversely, [START_REF] Handigol | Plug-n-serve: Load-balancing web traffic using openflow[END_REF], [START_REF] Wang | Openflow-based server load balancing gone wild[END_REF] use Software Defined Networking (SDN) on a controller, to monitor the application instance load and network load -and then install network rules to direct flows to these application instances.

[7] lists three standard load-balancing techniques used for dispatching queries among Web servers: DNS round-robin, dispatchers that perform NAT or destination IP rewrite, and redirect-based approaches. Application-aware load-balancing includes [START_REF] Zhang | Flexsplit: A workloadaware, adaptive load balancing strategy for media clusters[END_REF], [START_REF] Ciardo | Equiload: a load balancing policy for clustered web servers[END_REF], [START_REF] Zhang | Workloadaware load balancing for clustered web servers[END_REF], which assign queries as a function of their estimated size so that each application instance becomes equally loaded. In [START_REF] Sharifian | A content-based load balancing algorithm with admission control for cluster web servers[END_REF], a feedback approach is used to estimate the parameters of a queuing model representing the system, before making a load-balancing decision.

Layer-7 (application-layer protocol aware) load-balancers, e.g. [START_REF]HAProxy: the reliable, high-performance TCP/HTTP load balancer[END_REF] (HAProxy), also propose application-awareness by estimating the load on each application instance and assigning new queries accordingly. Load estimates are obtained by tracking open connections through the load-balancer to the backend servers, thus do not take other generated loads into account -e.g. internal traffic or traffic coming from other loadbalancers.

C. Segment Routing

In IPv6 Segment Routing (SR) [START_REF] Filsfils | The segment routing architecture[END_REF], each data packet indicates not only the destination to which the network is expected to carry the packet, but also an ordered sequence of instructions or operations (called segments), that the network is expected to execute on that packet. When a segment is "completely processed", that segment is (conceptually) discarded and the next segment (if any) is processed by the network, before the data packet is delivered to the final destination.

As SR is a network layer service, segments are expressed by way of IPv6 addresses, and the simplest possible sequence of segments interprets into "forward the packet to A, then B, then C" -i.e. source routing -but SR enables also traffic engineering, service chaining, etc. The SR information is expressed as an IPv6 Extension Header, comprising a list of segments and a counter SegmentsLeft -indicating the number of remaining segments to be processed.

D. Paper Outline

The remainder of this paper is organized as follows. Section II describes how Segment Routing can be used to perform Service Hunting, that is, in-network service selection. Section III describes two simple example connection acceptance policies. SRLB is then evaluated: section IV describes the experimental platform that has been used, section V provides an evaluation with a synthetic workload, and a realistic workload consisting of a Wikipedia replica is analyzed in section VI. Finally, section VII concludes this paper.

II. SERVICE HUNTING

This section introduces a new general concept, Service Hunting, which uses SR to direct network packets from a new flow through a set of candidate servers until one accepts the connection.

A. Overview

Service Hunting assumes an IPv6 data center, in which applications are identified by virtual IP addresses (VIPs), and can be replicated among several servers, identified by their physical addresses. Servers run a virtual router (for instance, VPP [START_REF]Vector Packet Processing (VPP)[END_REF]), which dispatches packets between physical NICs and application-bound virtual interfaces. Located at the edge of the data center, the load-balancer advertises routes for the VIPs.

When a query (typically, a TCP SYN packet as part of a connection request) for a VIP arrives at the load-balancer, the load-balancer will select a set of candidate servers which host an instance of the sought-after application, and insert an SR header into the IPv6 data packet accordingly. The SR header will contain a list of segments, each indicating that the query can be processed by either of these instances, and with the VIP as the last segment.

When the query reaches a candidate server, the corresponding segment in the SR header indicates that the virtual router may either forward the packet (i.e. start processing the next segment), or may directly deliver it to the virtual interface corresponding to the application instance. This is a purely local decision to accept or not the query, and is based on a policy shared only between the virtual router and the application instance, running on the same compute node. To guarantee satisfiability, however, the penultimate segment indicates that the application must not refuse a query.

In order to ensure that packets part of the same flow are treated by the same application instance, upon having accepted a query, the server hosting the application instance must signal this to the load balancer. This is done by inserting an SR header containing its own IP address, and the IP address of the load-balancer, in the connection acceptance packet (typically, a TCP SYN-ACK). An example of the whole procedure with 3 servers is given in figure 1.

B. Server Selection Policy

When the load-balancer receives a query, different policies can be used to select the list of candidate servers to include in the SR header. Parameters of importance for this selection include the number of candidate servers to include, and the A simple and lightweight approach consists of selecting server addresses at random. While any number of random server addresses can be inserted in the SR segment list, [START_REF] Mitzenmacher | The power of two choices in randomized load balancing[END_REF] demonstrates a decreased marginal benefit from more than two servers, when the goal is load balancing. Thus, for the purpose of the experimental verification in this paper, two servers will be chosen at random from among all servers hosting a given application instance.

C. Connection Acceptance Policy

To perform Service Hunting, SRLB assumes an application agent, locally available to the virtual router in each server, which in real time informs the virtual router as to if the application instance wishes to accept queries. The application agent may make this decision based on coarse-grained information (e.g. CPU load, memory footprint) available from the operating system; or on more fine-grained information, if the application exposes real-time metrics about its load state (idle threads, etc.). Done through shared memory, this incurs no system calls or synchronization, thus imposes a negligible run-time cost.

III. EXAMPLE CONNECTION ACCEPTANCE POLICIES

This section describes two simple policies that can be used to decide whether or not to accept new connections. These policies assume a standard master-slave threading model for the application. Section IV will then show how these policies can be applied in the case of an HTTP server such as Apache.

A. Static policy

Let n be the number of worker threads of the application, and c a threshold parameter between 0 and n + 1. In Algorithm 1, we introduce a simple policy, SR c , whereby the first server accepts the connection if and only if less than c worker threads are busy (recall that the second server always accepts the connection). When c = 0, all requests are satisfied by the second servers in the SR lists; when c = n + 1, all requests are satisfied by the first ones. These two cases reduce to a standard random load-balancing scheme. All choices of c between these two extremes yield an improvement over random load-balancing. Indeed, a server with c or more busy threads will be assigned a connection only if both itself and the first server in the SR list have more than c busy threads. The chance for this to happen is the square of the probability that one server has more than c busy threads, thus allowing for a better repartition of the load between all servers.

The choice of the parameter c has a direct influence on the behavior of the global system. Small values of c will yield better results under light loads, and high ones will yield better results under heavy loads. Indeed, if the chosen value is too small as compared to the load, the second server will receive almost all connections, and vice-versa. If the load pattern is known by the operator, the parameter c can be manually selected so as to maximize the load-balancing efficiency. If this is not the case, a dynamic policy can be used in order to automatically tune the value of the parameter.

B. Dynamic policy

This section introduces a dynamic policy, SR dyn , that can be used when the typical request load is unknown. The underlying intuition is the following: if the rejection ratio of the connection acceptance function is 0 (or 1), only the first (or second) candidates in SR lists serve requests, falling back to standard randomized load-balancing. To maximize utility, this policy aims to maintain a rejection ratio of 1 2 , by dynamically adapting the value of c so that this ratio stays close to 1 2 . The detailed procedure is described in Algorithm 2. Previous acceptance decisions are recorded over a fixed window of queries. When the end of the window is reached, if the number of accepted queries is significantly below (or above) 1 2 , the value of c is incremented (or decremented).

IV. EXPERIMENTAL PLATFORM

The experimental platform used for evaluating SRLB is composed of a load-balancer, a server agent for the Apache HTTP server, and an overall system.

A. Load-Balancer

The load-balancer performing SR header insertion and flow steering is implemented as a VPP plugin [START_REF]Vector Packet Processing (VPP)[END_REF]. While this choice is not significant to the performance results presented in this paper, it is convenient as VPP embeds an IPv6 Segment Routing stack and is kernel-bypass virtual routing capable.

B. Apache HTTP Server Agent

A server agent for the Apache HTTP server [START_REF]The Apache HTTP server project[END_REF] has been implemented as a VPP plugin, accessing Apache's scoreboard shared memory 1 to allow the virtual router to access the state of the application instance. Apache uses a worker thread model: a pool of worker threads is started in advance, and received queries are dispatched to those threads. Thus, a simple exposed metric is the state of each worker thread, allowing to count the number of busy/idle threads, and use this to decide on connection acceptance, using one of the policies described in section III.

C. System Set-up

The experiments, described in sections V and VI, are conducted on a common platform. A traffic generator and a load balancer reside in one physical machine. Twelve application instances of an Apache HTTP server reside each in a 2-core VM, all of which are hosted in another physical machine, running a 24-core Intel Xeon E5-2690 CPU. VPP instances running in the load-balancer and on the 12 application servers were bridged on the same link, with routing tables statically configured.

Finally, the Apache servers were configured to use the mpm_prefork module, each with 32 worker threads and with a TCP backlog of 128. The tcp_abort_on_overflow parameter of the Linux kernel was enabled, triggering a TCP RST when the backlog of TCP connections exceeds queue capacity, rather than silently dropping the packet and waiting for a SYN retransmit. This allows that, under heavy load, the application response delays are measured, and not possible TCP SYN retransmit delays.

V. POISSON TRAFFIC

A. Traffic and Workload Patterns

To evaluate the efficiency of the connection acceptance policies from section III under different loads, SRLB was tested against a simple CPU-intensive web application, consisting of a PHP script running a for loop, and whose duration follows an exponential distribution of mean 100 ms. The traffic generator sends a Poisson stream of queries (HTTP requests), with rate λ. A bootstrap step consisted of identifying λ 0 , the max rate sustainable by the 12-servers swarm, i.e. the smallest value of λ for which some TCP connections were dropped.

B. Connection Acceptance Policies Tested

With ρ = λ/λ 0 as the normalized request rate, for 24 values of ρ in the range (0, 1), a Poisson stream of 20000 queries with rate ρ was injected in the load-balancer, using the policies SR 4 , SR 8 , SR 16 , SR dyn . As baseline, the same tests were run with a policy RR where queries are randomly assigned to one server, without Service Hunting.

C. Experimental Results

Figure 2 depicts mean response times for each tested request rate and for each policy, and show that, among those, SR 4 yields the best response time profile, up to 2.3× better than RR for ρ = 0.88. SR 8 and SR 16 likewise perform better than RR for all loads, but with a lesser impact. SR dyn offers results close to the best static policy, SR 4 , showing that a manual policy tuning is not needed to obtain good performance.

Figure 3 shows the CDF of the page response time for the 20000 queries batch with ρ = 0.88, for each policy. RR exhibits a very dispersed distribution of response times, whereas the different SR c policies yield lower, and less dispersed, response times.

This can be explained by inspecting the evolution of the mean instantaneous load (the number of busy worker threads), as well as the corresponding fairness index: (where x i (t) is the load of server i at time t) of each server, depicted in figure 4 2 . As SR 4 better spreads queries between all servers (the fairness index is closer to 1), and servers are individually less loaded, better response times result.

For lighter loads, the same kind of behavior can be observed, except that high SR c policies exhibit no benefits as compared to RR. Figure 5 shows the CDF of the page load time for an experiment where ρ = 0.61: SR 16 yields no improvement over RR, and SR 8 yields a relatively small improvement, however the SR 4 policy provides a substantial improvement in response times -and SR dyn remains able to successfully match SR 4 , the best static policy.

VI. WIKIPEDIA REPLAY A. Traffic and Workload Patterns

To evaluate the performance of SRLB when exposed to a realistic workload, an experiment was constructed to reproduce a typical Web-service. Thus an instance of MediaWiki 3 (version 1.28), as well as a MySQL server and the memcached 2 These values have been smoothed through an Exponential Window Moving Average filter, of parameter α = 1 -exp(-δt) where δt is the interval of time in seconds between two successive data points. 3 cache daemon, were installed on each of the 12 servers. The wikiloader tool from [START_REF] Van Baaren | Wikibench: A distributed, wikipedia based web application benchmark[END_REF], and a dump of the database of the English version of Wikipedia from [START_REF] Urdaneta | Wikipedia workload analysis for decentralized hosting[END_REF], were used to populate the MySQL databases, resulting in each server containing an individual replica of the English Wikipedia.

A traffic generator, able to replay a MediaWiki access trace with millisecond granularity and to record response times, was developed, and experiments were run using 24 hours of traces from [START_REF] Urdaneta | Wikipedia workload analysis for decentralized hosting[END_REF]. These traces correspond to 10% of all queries received by Wikipedia during this timeframe, from among which only traffic to the English Wikipedia was extracted and used for the experiment.

A first experiment was to identify the maximum achievable rate for the testbed. Using RR, the testbed could sustain 50% of the peak load while exhibiting reasonable response times (smaller than one second).

B. Connection Acceptance Policies Tested

Given the superior performance of SR 4 in the experiments from section V-C, 50% of the 24-hour trace was replayed

C. Experimental Results

The experiment allowed classifying queries into two groups: (i) requests for static pages, which are not CPU-intensive, and for which response times were of the order of a millisecond, and (ii) requests for wiki pages, that trigger memcached or MySQL and thus are more CPU-intensive.

Static page response times were found to be equivalent, regardless of if SR 4 or RR were used. However, the load times of wiki pages, identifiable by the string /wiki/index.php in their URL, exhibited interesting differences.

Figure 6 depicts the wiki page request rate and the median wiki page load time for both RR and SR 4 during the 24h replay 4 . It can be observed that at the off-peak period around 8:00 UTC, when the system was lightly loaded and subject to a request rate of around 60 pages per second, RR and SR 4 yielded very similar performance. However as the request rate increased, when using the application-unaware RR policy observed page load times increased notably -whereas when using SR 4 , a comparably much smaller increase in page load times incurred.

To understand the variability of the response times along the 24 hours, figure 6 depicts deciles 1-9 of the wiki page load time distribution, for each 10 minutes bin. Again, SR 4 shows less variability under higher loads than does RR.

Finally, as an indicator of "global good behavior", figure 8 depicts the CDF of the wiki page load times over the whole day. Overall, the median response time went from 0.25s with RR to 0.20s with SR 4 . Furthermore, the tail of the distribution is steeper with the application-aware SR 4 scheme, with the third quartile going from 0.48s to 0.28s.

VII. CONCLUSION

This paper has introduced SRLB, a distributed load balancing system which, while remaining application and application-layer protocol agnostic, is able to perform application-instance state aware query assignment by way of Service Hunting within the IP forwarding plane. This allows SRLB to offer -not impose -queries to application 4 Data has been binned in 10 minutes slots.

instances, leaving the decision to accept (or not) a query to those. SRLB thus does not employ any out-of-band signaling, nor requires any central monitoring, nor imposes any load balancing policy. As a flexible framework, SRLB is able to accommodate a broad spectrum of policies. As a baseline, this paper has tested a naive random query dispatch policy -and has compared with a static and a dynamic query acceptance policy, enabled by the Service Hunting features of SRLB developed in this paper. Evaluation of those policies, conducted using a simulated Poisson workload, as well as on a Wikipedia replica, shows that SRLB is able to better spread the load between all servers than a random load-balancer.

Figure 1 .

 1 Figure 1. Service Hunting from client c to application a with 3 servers s 1 , s 2 , s 3 . The path (source, segments, destination) is indicated between curly braces. The active segment is underlined.

Figure 2 .

 2 Figure 2. Average page load time for the Poisson workload as a function of the normalized request rate ρ: RR vs different SRc policies (4, 8, 16, and dynamic).

Figure 3 .

 3 Figure 3. CDF of page load time over 20000 queries for the Poisson workload: RR vs different SRc policies, ρ = 0.88

Figure 4 .Figure 5 .

 45 Figure 4. Instantaneous server load for a run of 20000 queries of the Poisson workload (mean and fairness over the 12 servers): RR vs SR 4 policy, ρ = 0.88

Figure 7 .

 7 Figure 7. Wikipedia replay: decile 1, . . . , 9 of load time for wiki pages over 24 hours (10 mins bins). RR vs SR 4 policy.

Figure 8 .

 8 Figure 8. Wikipedia replay: CDF of wiki page load time over 24 hours. RR vs SR 4 policy.

  Algorithm 1 Static Connection Acceptance Policy SR c

	for each packet with SegmentsLef t = 2 do
	b ← number of busy threads
	if b < c then
	SegmentsLef t ← 0
	forward packet to application
	else
	SegmentsLef t ← 1
	forward packet to second server in SR list
	end if
	end for
	for each packet with SegmentsLef t = 1 do
	SegmentsLef t ← 0
	forward packet to application
	end for
	scheme according to which they are selected. Possibilities for
	such schemes include random selection and consistent hashing.

  Algorithm 2 Dynamic Connection Acceptance Policy SR dyn c ← 1 {or other initial value} accepted ← 0 attempt ← 0 windowSize ← 50 {or other window size} for each packet with SegmentsLef t = 2 do attempt ← attempt + 1 if attempt = windowSize then {end of window reached, adapt c if needed and reset window} if accepted/windowSize < 0.4 and c < n then c ← c + 1 else if accepted/windowSize > 0.6 and c > 0 then

	c ← c -1
	end if
	attempt ← 0
	accepted ← 0
	end if
	{use SRc policy with current value of c}
	b ← number of busy threads
	if b < c then
	accepted ← accepted + 1
	SegmentsLef t ← 0
	forward packet to application
	else
	SegmentsLef t ← 1
	forward packet to second server in SR list
	end if
	end for
	for each packet with SegmentsLef t = 1 do
	SegmentsLef t ← 0
	forward packet to application
	end for

  https://www.mediawiki.org/wiki/Download Figure6. Wikipedia replay: query rate and median load time for wiki pages over 24 hours (10 mins bins). RR vs SR 4 policy.

	Median response time (s)	0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9	00:00	04:00	08:00	12:00	16:00 RR wiki pages SR 4 wiki pages	20:00
					Time of day (UTC)
	Queries per second	60 70 80 90 100 110 120					wiki pages
		50	00:00	04:00	08:00	12:00	16:00	20:00
					Time of day (UTC)
	Decile 1-9 response time (s)	0 0.2 0.4 0.6 0.8 1	00:00	04:00	08:00	12:00	16:00 RR wiki pages	20:00
					Time of day (UTC)
	Decile 1-9 response time (s)	0 0.2 0.4 0.6 0.8 1	00:00	04:00	08:00	12:00	16:00 SR 4 wiki pages	20:00
					Time of day (UTC)

This shared memory, internal by default, can be exposed as a named file by specifying the ScoreBoardFile directive in the server configuration.


Jiazi Yi

Thomas Clausen
email: thomas@thomasclausen.org

Ulrich Herberg
email: ulrich@herberg.name

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

Data delivery across a multi-hop low-power and lossy networks (LLNs) is a challenging task: devices participating in such a network have strictly limited computational power and storage, and the communication channels are of low capacity, time-varying and with high loss rates. Consequently, routing protocols finding paths through such a network 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, or for a very short time due to changes on the channel. Routing protocols exist for such networks, balancing reactivity to topology and channel variation with frugality in resource requirements. Complementary component to routing protocols for such LLNs exist, intended not to manage global topology, but to react rapidly to local data delivery failures and (attempt to) successfully deliver data while giving a routing protocol time to recover globally from such a failure. Specifically, this paper studies the "Depth-First Forwarding (DFF) in Unreliable Networks" protocol, standardised within the IETF in June 2013. Moreover, this paper proposes optimisations to that protocol, denoted DFF++, for improved performance and reactivity whilst remaining fully interoperable with DFF as standardised, and incurring neither additional data sets nor protocol signals to be generated.

I. INTRODUCTION

Low-power and Lossy Networks (LLNs) are often deployed with constrained devices, under challenging and unreliable environments. Typical communication and data processing modules are equipped with CPU in several MHz processing power, and tens of KBytes of memory. In addition, the communication medium connecting all those devices is "lossy": the communication channels are of low capacity, time-varying and with high loss rates.

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. To discover appropriate paths in such networks, protocols such as Light-weight On-demand Ad hoc Distance-vector Routing Protocol -Next Generation (LOADng) [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocolnext generation[END_REF] and IPv6 Routing Protocol for Low-power and Lossy Networks (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] have been developed.

Those routing protocols for LLNs are designed to limit the routing overhead imposed to networks as much as possible, and to be adapted to the varying nature of communication medium. However, even once paths were found, those paths might be unusable from time to time due to different reasons: presence of noise or interferences, low power supply in certain devices, uni-directional links, etc. From a routing protocol point of view, when such link failure is detected, it needs some extra signalling and/or time to recover and discover new, valid routes. During this recovery phase, data packets being sent over the broken link, must either be buffered and wait for the route recovery, or be dropped because of lack of memory in constrained devices.

To alleviate the effects of inevitable random link failures in LLNs, a set of data forwarding mechanisms have been proposed [START_REF] Cespedes | Comparison of data forwarding mechanisms for ami networks[END_REF]. Those mechanisms that work in the "forwarding plane" use data packet to detect loops, update routing tables, and reroute data packet through alternative paths when the primary routes are broken. By doing so, the packets that are originally forwarded through failed links can be recovered, instead of being dropped.

"Depth-First Forwarding in Unreliable Networks" (DFF) [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF] is an experimental data forwarding standard which proposes a mechanism for rapid and localised 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. 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 application of DFF in LLNs. One key issue of DFF -selecting appropriate next-hop candidates for forwarding data packets, is specially discussed. Based on experiments and observations, an optimisation to the DFF standard [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF], denoted DFF++, is proposed. It offers a procedure to choose next hops based on previously processed packets, and reduces unnecessary explorations in the depth-first search. The extension is of very low impact to DFF protocol: it does not introduce additional protocol signalling and data sets, while remaining completely interoperable with DFF as standardised in [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF].

B. Paper Outline

The remainder of this paper is organised as follows. Section II provides a brief overview of DFF, as defined in [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF], and section III studies, by way of an example, one of the cardinal points of the performance of DFF: the ordering of the elements of Candidate Next Hop List. Section III also identifies a set of inconveniences in a "naive" (but, perfectly valid, according to [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF]) ordering. [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF] stipulates some basic constraints on how the Candidate Next Hop List is to be ordered, but otherwise leaves the exact approach and order unspecified. This paper, therefore, proceeds by proposing a simple and no-overhead optimisation to DFF, denoted DFF++, in section IV. This optimisation remains fully interoperable with DFF. Both DFF and DFF++ are evaluated in section V. As DFF, and as a consequence DFF++, are able to operate both independently and conjointly with a unicast routing protocol, this evaluation will study the performance of DFF/DFF++ alone and when used with LOADng [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF], [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocolnext generation[END_REF]. Finally, this paper is concluded in section VI. [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 of this paper , interact with a routing protocol. DFF relies on an external mechanism providing each router with a list of its neighbours.

II. DEPTH FIRST FORWARDING DFF

In order to support the loop detection and duplicate detection, each router running DFF maintains a Processed Set, which lists sequence numbers of previously received packets, as well as a list of Next Hops to which the packet has been sent successively as part of the depth-first forwarding mechanism.

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 router's 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: a) 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. b) 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.

c) 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 step 2 above. d) 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. e) 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.

III. ORDERING THE CANDIDATE NEXT HOP LIST

Section II, has introduced the basic operations of DFF, indicating that a key operational parameter is the ordering of elements in the Candidate Next Hop List for a data packet. To elaborate on this parameter, this section will consider the example in figure 1, where device A sends a data packet to device D, and which arrives at B -the sole neighbour of A.

A. Ideal Ordering and Default Ordering

The ideal ordering of the elements in the Candidate Next Hop List for that data packet in B would list F and G first, followed by E. The ideal list would not include C at all. Absent topological information (maintained by some external process), however, B would by default populate the initial Candidate Next Hop List with all of its bi-directional neighbours, except for A, would not be able to determine that E should be listed after F and G, nor that C should be excluded from the list. This, would lead to a "blind" search for all the DFF forwarded data packets. Indeed, in this example constructing the Candidate Next Hop List lexicographically -{C, E, F, G} -would lead to the worst possible search order.

B. Ordering with Unicast Routing Protocol

If a unicast routing protocol is in place, as suggested by section 11 in [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF], that routing protocol would provide B with information that F (or G) is the next hop identified on the shortest path to D, and therefore allow B to ensure that the first element in the Candidate Next Hop List for a data packet for D would be F. Unless if the routing protocol provides multiple paths or a complete topology in each device -unlikely, given that the application space is constrained devices with limited memory -the remainder of the list would have to be constructed without any additional guidance from the routing protocol as to a specific order of elements. A simple lexicographical order of the remaining elements, as in the above, would result in {F, C, E, G}.

C. When Links Break

The Candidate Next Hop List order, obtained when using a unicast routing protocol as illustrated above, is better than without -but is still not ideal. Consider that with the Candidate Next Hop List being {F, C, E, G}, and data packets being successfully transmitted from A to D along the path A-B-F-D. Now, the link between device B and F breaks -which would be detected by B when trying to forward a data packet to F. B would then remove F from the Candidate Next Hop List, and forward it to the next entry -C. As C is not on any route route to device D, the packet would eventually be returned to device B, after having traversed the network indicated in the "cloud" in figure 1, and B would be able to remove C from the Candidate Next Hop List for that data packet.

D. Candidate Next Hop List Per Packet

[4] specifies that the Candidate Next Hop List is constructed per data packet. [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF] also specifies that DFF may signal to the routing protocol when delivery to a next hop, indicated by the routing protocol, fails such that the routing protocol can take corrective action (e.g., remove the entries from the routing table, corresponding to the failed next hop, and initiate recovery as specified by the routing protocol). In the example above, if DFF signals to the routing protocol that F has failed, and if the routing protocol then removes routing table entries indicating F as next hop, then for all subsequent data packets to D (until the routing protocol recovers and establishes a new entry in the routing table), the initial Candidate Next Hop List will be {C, E, G} -back to the "worst case" default ordering.

IV. DFF++: THE DESTINATION FIELD EXTENSION

As introduced in section II, when data delivery of a data packet fails, DFF removes the failed "next hop entry" from the Candidate Next Hop List for that data packet, and forwards the data packet to the next entry (if any) in that list. Section III illustrated, by way of an example, that while DFF thus may eventually succeed in delivering data packets to the intended destination, the efficiency of that operation -the path-length and number of forwards of a data packet -depends on the ordering of entries in that Candidate Next Hop List. As the Candidate Next Hop List is constructed per-packet, several subsequent data packets to the same destination may take the same "detour" through the network (or, in the example in figure 1, all explore the same "blind alley" in the network by way of C) -either persistently, or, if a unicast routing protocol is also operating in the network, until such time that that unicast routing protocol has recovered from the failure and provided a new entry for the destination in the routing table. This section proposes a simple extension to DFF, henceforth denoted DFF++, for establishing "memory" across several data packets for the same destination. In the interest of being frugal with required state, this extension (i) piggy-bags off information already maintained by DFF, and (ii) maintains information only temporarily, for as long as DFF otherwise maintains information pertaining to forwarded packets.

A. State

In order to support loop and duplicate detection, each device running DFF maintains a Processed Set, which records sequence numbers of previously received data packets, as well as a list of next hops to, which each data packet has been successively sent, as part of the depth-first forwarding mechanism. Without going into the details of the loop and duplicate detection mechanisms in DFF (refer to [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF]), the "Processed Set" consists of "Processed Tuples", of the form:

(P_orig_address, P_seq_number, P_prev_hop, P_next_hop_neighbor_list, P_time)

where:

• P_orig_address is the originator address of the received packet; • P_seq_number is the sequence number of the received packet; • P_prev_hop is the address of the previous hop of the packet; • P_next_hop_neighbor_list is a list of addresses of next hops to which the packet has been sent previously, as part of the depth-first forwarding mechanism; • P_time specifies when this tuple expires and must be removed. The proposed DFF++ extensions adds an element to each such tuple, thus:

(P_orig_address, P_seq_number, P_prev_hop, P_next_hop_neighbor_list, P_time, P_dest_address)

where:

• P_dest_address indicates the destination address of the received packet. The proposed DFF++ extension also imposes an additional constraint on P next hop neighbor, which is that:

• P_next_hop_neighbor must be ordered such that the last element (P_next_hop_neighbor_list[LAST]) of that list contains the last neighbour, to which delivery to P dest address was attempted (and all previous entries in that list contain successively earlier attempts, with the first element of the list containing the first neighbour, to which delivery was attempted).

B. Processing

On receiving a data packet, not destined to itself, DFF++ defines the following process for selecting an ordered Candidate Next Hop List (CNHL), within the constraints and guidelines from section 11 in [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF].

Find the (unique) Processed Tuple, where:

• P_dest_address == the destination address of the data packet; AND • which has the greatest P_time. Using that tuple, the CHNL is constructed thus (where ⊕ indicates list concatenation, \ indicates list exclusion, RT(address) is the next hop on the shortest path to the destination from the routing table -if any, and NS indicates the set of neighbours of the device):

1) CNHL = RT( P_dest_address) 2) CHNL = CHNL ⊕ P_next_hop_neighbor_list[LAST] 3) CHNL = CHNL ⊕ {NS\ {P_prev_hop} \ P_next_hop_neighbor_list} 4) CHNL = CHNL ⊕ P_next_hop_neighbor_list
Where 1) satisfies the requirement from [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF] that first element in the CNHL is the next hop, indicated by a routing table (if present). Items 2) and 3) capture "pick up where the most recent data packet delivery to the same destination left off". Specifically, 2) is the neighbour, last tried for the most recent packet to the same destination, and which is not yet confirmed as having failed (in which case there would be a subsequent entry in the list, except if all neighbours had been tried and failed), 3) includes all other so far untried (by the most recent data packet delivery for this destination) neighbours. Finally, 4) -which is an optional step in DFF++ -includes all previously (by the most recent data packet delivery) tried neighbours -excluding, of course, the one from which the data packet was received -capturing the fact that a previous failure may have been due to transient losses.

C. Impact

Adding and using P dest address, as described above, allows construction of the Candidate Next Hop List to make use of information on previous data packet forwards to the same destination.

Returning to the example in figure 1, one of the issues raised in section III-C, and detailed in section III-D, is alleviated:

1) The initial Candidate Next Hop List for the first data packet arriving at B for destination D will -using the same ordering (routing table entry first, then the the "worst-case" lexicographical order) be {F, C, E, G}. 2) Initial delivery is attempted via F (which is added to the end of P next hop neighbor list) and fails, and delivery via C is attempted (which is added to the end P next hop neighbor list). 3) Delivery via C also fails (no path via C to D), and delivery is now attempted via E (which is added to the end of P next hop neighbor list) -as there is a valid path to D via E, delivery succeeds, and the P next hop neighbor [LAST] for that processing tuple now contains E. 4) Other data packet for D, arriving at B, before the routing protocol (if any) has recovered and provided an entry in the routing table for D, will, using the DFF++ Candidate Next Hop List construction rules given in section IV-B, result in a Candidate Next Hop List of:

• If they arrive after step 3), {E, G} -thus avoiding the "broken link" to F, as well as the "blind alley" that would be attempting delivery via C. • If they arrive after step 2) but before step 3), {C, E, G} -thus avoiding the "broken link" to F, but not the "blind alley" that would be attempting delivery via C • If they arrive before step 2), {F, C, E, G} -thus offering no improvement over DFF, but also no additional penalty.

Note that DFF++ avoids the problem of repeatedly attempting delivery to a given destination via "blind alleys" and over "recently detected broken links", but does not attempt at offering "shortest paths" -that remains under the auspices of a routing protocol (if any) in the network. Also, DFF++ does not affect interoperability: the extension does not introduce any new signals or any new external behaviours, but simply offers guidance for how to order the Candidate Next Hop List for a data packet. The specification of DFF [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF] specifically encourages an intelligent ordering, and DFF++ does just that. As that ordering of the Candidate Next Hop List for a data packet concerns only internal processing of a device, DFF and DFF++ remain interoperable. DFF++ can furthermore be deployed with exactly the same (or no) unicast routing protocols as DFF.

V. SIMULATION AND ANALYSES

In order to evaluate the performance of DFF++, and compare its performance to that of 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 it allows 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 behaviours of a protocol can be inferred from simulations using 802.11.

DFF and DFF++ were evaluated both in isolation (without a concurrently operating unicast routing protocol) and when used in conjunction with the Lightweight On-Demand Ad hoc Distance-vector Next Generation (LOADng) routing protocol, standardised for use in, e.g., SmartGrid/SmartMeter Automatic Metering Infrastructure (AMI) networks [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF], [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocolnext generation[END_REF] -and, compared with LOADng operating alone in the same networks, so as to evaluate the benefits of DFF and DFF++, respectively. In total, five different protocol combinations were evaluated:

• DFFonly: DFF according to [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF], with Neighbourhood Discovery Protocol (NHDP) [START_REF] Clausen | Mobile Ad Hoc Network Neighborhood Discovery Protocol[END_REF] used for bi-directional neighbour discovery, suggested by [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF]. • DFF++only: As described in section IV, with [START_REF] Clausen | Mobile Ad Hoc Network Neighborhood Discovery Protocol[END_REF].

• LOADng: LOADng, according to [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocolnext generation[END_REF].

• LOADngDFF: LOADng with DFF ([4], [START_REF] Clausen | Mobile Ad Hoc Network Neighborhood Discovery Protocol[END_REF] and [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocolnext generation[END_REF]).

• LOADngDFF++: LOADng with DFF++ ([1] + the process described in section IV and with [START_REF] Clausen | Mobile Ad Hoc Network Neighborhood Discovery Protocol[END_REF]).

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, such that to maintain a constant device density. There are n -1 Constant Bit Rate (CBR) streams in the network. The original node of the CBR stream (chosen randomly) sends one packet of 512 octets every 5 seconds to a destination (chosen randomly). 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 generate scenarios -all corresponding to the same abstract parameterswere simulated, with the results presented below representing averages from among these.

For NHDP [START_REF] Clausen | Mobile Ad Hoc Network Neighborhood Discovery Protocol[END_REF], 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 and 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 deployment, the HELLO interval should be selected so as to correspond to the expected local network topology change rate.

B. Simulation Results

Figure 2 depicts the packet deliver ratio of the different protocols combination. When DFF (DFFonly and DFF++only) is running without an external routing protocol, DFF++ offers a significant improvement of the packet delivery ratio over DFF. The lower performance, experienced when running without an external routing protocol is due to depth first searching being inefficient, worst case causing a complete transversal of the network graph for each data packet. DFF, used with LOADng, yields about 20 percentage points improvement of the delivery ratio, as compared to LOADng alone, and DFF++ used with LOADng further improves the data delivery ratioalbeit marginally so. Figure 3 depicts the average end-to-end delays -and it should be noted, particularly for this figure, that only data packets that successfully arrive the destination are accounted in the statistics. DFF and DFF++ alone exhibit significantly greater delays than when running with LOADng -balance with the data delivery ratio in figure 2, this is noteworthy: combining DFF/DFF++ yields lower delays and better data delivery. LOADng alone exhibits a slightly lower delay than when compared with DFF and DFF++ -which is compensated by the fact that inclusion of DFF/DFF++ increases the data delivery ratios obtained by approximately 20 percentage points.

Figure 4 depicts the average path length (of successfully delivered packets), i.e., the number of hops required for a packet to reach its destination. When running without an external routing protocol, the "blind" depth-first search of DFF causes 6-7 times as long paths as LOADng -with DFF++ offering shorter path lengths than DFF. When combined with LOADng, both DFF and DFF++ yield significantly shorter

Figure 1 .

 1 Figure 1. An example of DFF. device A sends packets to device D. Dahsed line is broken link.

Figure 2 .

 2 Figure 2. Average data packet delivery ratio

Figure 5 illustrate the control packet overhead. For DFF and DFF++ without an external routing protocol, the overhead is constituted from locally exchanged HELLO messages, generated by NHDP to discover the bi-directional neighbours. When introducing LOADng (either alone, or in conjunction with DFF/DFF++), the protocol overhead of that routing protocol for route discovery (see [START_REF] Clausen | Loadng: Towards aodv version 2[END_REF] for details) is also imposed on the network, and causes additional MAC layer collisions.

VI. CONCLUSION

This paper studies the application of depth-first forwarding in LLNs, and presented a minimal-impact optimisation to DFF [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF], denoted DFF++. DFF++ is fully interoperable with DFF; it offers a procedure for ordering the Candidate Next Hop List for a data packet to be forwarded at a device. Using DFF++ alleviates some problems of DFF, such as repeatedly trying to forward traffic down "blind alleys" and across recently detected broken links. Performance studies comparing DFF and DFF++ alone (without a concurrently operating unicast routing protocol) have revealed the benefits of this optimisation to be significant: DFF++ attains a higher Neither DFF nor DFF++ attempt to offer "shortest paths" -that remains under the auspices of a routing protocol, and both DFF and DFF++ are intended to operate concurrently with a unicast routing protocol. For the purpose of this study, the unicast 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] has been tested with and without DFF/DFF++. A first observation is that the performance of both DFF and DFF++ is significantly improved by operating conjointly with LOADng. A second observation is, that the data delivery ration of LOADng also is significantly improved by the use of either of DFF and DFF++ -but that LOADng with DFF++ offers a moderate, but consistently better, performance when compared to LOADng with DFF.

DFF++ attains these performance improvements without introducing new control signals, minimal additional state (a single IP address added to an existing data set) and low implementation complexity -and, remains completely interoperable with DFF, as specified in [START_REF] Herberg | Depth-first forwarding (dff) in unreliable networks[END_REF].


Thomas Clausen

Jiazi Yi

Path Accumulation Extensions for the LOADng Routing Protocol in Sensor Networks

The "Light-weight On-demand Ad-hoc Distance-vector Routing Protocol -Next Generation" (LOADng) is a simple, yet e cient and flexible routing protocol, specifically designed for use in lossy networks with constrained devices. A reactive protocol, LOADng -as a basic mode of operation -o↵ers discovery and maintenance of hop-by-hop routes and imposes a state in intermediate routers proportional to the number of tra c paths served by that intermediate router. This paper o↵ers an extension to LOADng, denoted LOADng-PA (Path Accumulation). LOADng-PA is designed with the motivation of requiring even less state in each intermediate router, and with that state being independent on the number of concurrent tra c flows carried. Another motivation the design of LOADng-PA is one of monitoring and managing networks: providing more detailed topological visibility of tra c paths through the network, for either tra c or network engineering purposes.

Introduction

Since the late 90s, the Internet Engineering Task Force (IETF) 1 has embarked upon a path of developing routing protocols for networks with increasingly more fragile and low-capacity links, with less pre-determined connectivity properties and with increasingly constrained router resources. In '97, by chartering the MANET (Mobile Ad hoc Networks) 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.

The MANET working group converged on the development of two protocol families: reactive protocols, including AODV (Ad hoc On-demand 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][START_REF] Clausen | Optimized Link State Routing Protocol (OLSR) Version 2[END_REF]. A distance vector protocol, AODV operates in an on-demand fashion, acquiring and maintaining paths only while needed for carrying data, by way of a Route Request/Route Reply exchange. A link state protocol, OLSR is based on periodic control messages exchanges, and each router proactively maintaining a routing table with entries for all destinations in the network, which provides low delays but constant control overhead.

LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] is a protocol derived from AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], simplified for LLNs, and standardised by the ITU-T as part of the G3-PLC standard [START_REF] Itu-T G | Narrow-Band OFDM power line communication transceivers -Data link layer specification[END_REF] for mesh-under routing for utility (electricity) metering networks. The emergence of LLNs thus triggered a renewed interest in AODV-derived protocols for specific scenarios, resulting in continued work within the IETF [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] and [START_REF] Clausen | Experience with the loadng routing protocol for llns[END_REF] for the purpose of standardisation of a successor to LOAD -denoted LOADng (the Lightweight Ondemand Ad hoc Distance-vector Routing Protocol -Next Generation). LOADng incorporates the experiences from deploying LOAD -including, but not only, in LLNs -and has been accepted as part of an update to the G3-PLC ITU-T standard for communication in the "smart grid" [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF].

The Lightweight On-demand Ad hoc Distance vector Routing

Protocol -Next Generation (LOADng) Overview

A reactive protocol, the basic operations of LOADng [START_REF] Clausen | LOADng: Towards AODV Version 2[END_REF][START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] include generation of Route Requests (RREQs) by a LOADng Router (originator) and flooded through the network when discovering a route to a destination, and Route Replies (RREPs) generated by the sought destination ad transmitted to the originator by way of unicasts. When an intermediate router forwards a RREQ, it installs temporary routing table information towards the originator of the RREQs -the "reverse route" from the destination to the originator. When the sought destination receives a RREQ, it will respond by an unicast RREP, which is forwarded along this installed reverse route -and the forwarding of which will serve to install a "forward route" from the originator to the destination. Thus, for each bidirectional path through a LOADng router, four entries are thus maintained in the routing table: for directions, an entry is recorded for the "next hop" and for the "destination" via that "next hop". One of the key features of LOADng is, that it combines simplicity with extensibility: the core protocol provides mechanisms for discovering and maintaining bi-directional routes between pairs of routers, but o↵ers the ability to develop functional extensions, optimising its behaviour and performance for specific deployments, topologies and tra c patterns.

LOADng provides the information required for hop-by-hop routing of data packets: a router will know the next hop towards the destination, for a data packet, but not the full path that the packet will take. To this end, the header of a data packet contains only the destination address, relying on intermediate routers to be able to make forwarding decisions based on their local knowledge of the routing topology. This provides agility for each router to make a local decision (e.g., if local connectivity changes more frequently than routing updates can be propagated globally through the network) and, e.g., enables "fast re-routing" mechanisms to engage and improve data packet delivery when a data packet arrives at a router without, or with outdated, topological information [START_REF] Clausen | A depth first forwarding (d↵) extension for the loadng routing protocol[END_REF][START_REF] Yi | Depth first forwarding for low power and lossy networks: Application and extension[END_REF].

The LOADng Collection Tree Protocol (LOADng-CTP) is of the protocol extensions, developed for LOADng [START_REF] Yi | Collection Tree Extension of Reactive Routing Protocol for Low-Power and Lossy Networks[END_REF]. This extension permits e cient construction of a bi-directional collection tree, rooted in one router and covering the entire network. LOADng-CTP permits reducing the number of RREQ flooding operations from (n-1) to 2 in order to construct bi-directional paths between the root and all other routers in the network, but otherwise incurs the same state requirements as described above. This extension is applicable for deployments where a central controller, or monitoring entity is present and operating the network, e.g., as is the case in a smart grid management, or for home/building/factory automation.

The Case for Source Routing and Path Accumulation

There are, however, potential downsides to hop-by-hop routing combined with a reactive protocol: by their very nature, reactive protocols acquires and maintains only topological information about actively used paths -and, at that -at their basic form only "next hops" along those paths. Thus, no router has access to a "global view" of the network topology, or even of which destinations are reachable through which paths. This may be unfortunate in some scenarios, e.g., for management purposes: paths from a central unit (e.g., a monitoring station) to a set of devices (e.g., sensor devices) may, all pass through a faulty intermediate router rendering the network inoperative -and absence of a topological view of the paths actually used, this faulty router may be di cult to identify. Also, lack of such global information renders establishing path-diversity, i.e., that data packets (as far as possible) are not concentrated across a few unfortunate routers (which may, if battery-driven, see their energy depleted prematurely, or experience congestion) or across a few unfortunate links (which may incur higher media contention and losses) hard to accomplish. A final downside is, and probably the most critical issue for memory-constrained devices, of hop-by-hop routing is, that with hop-by-hop routing and a reactive protocol, the state required in each router is proportional to the number of active paths passing through that router. Thus, any individual device in the network may, worst case, be required to maintain a routing table with entries to many (or all) destinations, as illustrated in figure 1(a): each of the white routers on top establishes a (bi-directional) path to each of the white routers in the bottom, requiring the two intermediate black routers to, each, maintain entries for each of the white routers in the network (plus, for each other, of course). In large networks with a topology in which a router finds itself an intermediary of a large number of active paths, this may put undue requirements on some routers. Figure 1(b) shows an example of such a network topology: if the root (0) is a network controller or monitoring station, and as such needs establishing bi-directional paths to all destinations in the network for command-and-control, then the two routers immediately below it (1 and 2), each, will need to maintain routing table entries for all destinations in their respective sub-trees. While, in such a case, the root (0) typically can be provisioned with su cient resources, in an unplanned network, or a network evolving over time, it may not be possible to determine which non-root routers will thus become "choke-points" and therefore will also need to be provisioned to be able to maintain this much routing state.

The alternative to hop-by-hop routing is source-routing: the router, by which a data packet enters a routing domain, inserts the complete path information (for transversing that routing domain -which may be the complete path, up to and including the destination) into the data packet header. Consequently, intermediate routers need only inspect this information when making forwarding decisions. In order for a router to be able to insert complete path information into data packet headers, su cient topological information must be available to construct the complete path -the task of acquiring this topological information is denoted path accumulation.

Literature contains a few examples of such path accumulation mechanism for reactive protocols: Dynamic Source Routing [START_REF] Johnson | The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks for IPv4[END_REF] and AODV-PA [START_REF] Gwalani | Aodv-pa: Aodv with path accumulation[END_REF], both, use aggressive caching mechanisms to reduce the cost of route discovery. Because the routers need not only keep the routing tuples to the destinations of the route discovery, but also the routing tuples of the intermediate routers, those protocols requires maintaining more state in all routers, possibly exceeding the memory capacity of devices in a sensor network.

Paper Outline

This paper explores path accumulation extensions to LOADng, intended toin topologies and with tra c patterns where it is appropriate -alleviate these di culties, and (i) eliminate the requirements of routers in a strangulation point, (ii) provide visibility of the paths used and (iii) enable tra c engineering, e.g., for path diversity. Consequently, the remainder of this paper is organised as follows: section 2 specifies the the path accumulation extension. The performance of LOADng with this path accumulation is, then, studied, and compared with core LOADng, by way of network simulations, and results are presented in section 3. This paper is concluded in section 4.

Each of the two message types used for route discovery by LOADng -RREQ and RREP -provide an option for doing path accumulation, by way of inclusion of appropriate TLVs and addresses, as the message is forwarded. While doing path accumulation in either message will result in the source learning the full path used, and while the same TLVs and general mechanism can be applied to either RREQ or RREP, the two approaches are not equivalent, and are therefore discussed independently in sections 2.1 and 2.2 below. Either way, once a path is established by way of Path Accumulation, user data is forwarded by way of source routing, carrying the complete path in each data packet: essentially, trading o↵ router state for channel occupation.

RREQ Path Accumulation (RREQ-PA)

As indicated in section 1.1, a router seeking a path to a destination initiates Route Discovery by generating an RREQ, flooded through the network. Augmenting the RREQ so as to support Path Accumulation (RREQ-PA) requires including a flag, requesting that intermediate routers include path information when receiving the RREQ and prior to either forwarding or replying (by way of an RREP).

The regular LOADng processing of RREQs, specified in [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], can be modified slightly, so as to reduce the amount to state is required in each intermediate router: LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] stipulates that while forwarding RREQs, temporary "reverse path information" towards the source is installed in each intermediate router so as to facilitate forwarding of RREPs. The destination for an RREQ extend with RREQ-PA, will know the exact path that the RREQ took, and will be able to use this path for source-routing the RREP back to the initiator of the Route Discovery process. Figure 2(a) gives an example of RREQ-PA route discovery from A to D.

If the initiator of the Route Discovery process conveys additional requestssuch as multiple disjoint paths, or paths avoiding/passing specific routers, the destination for a RREQ extended with RREQ Path Accumulation will be able to make intelligent decisions as to which RREQs to respond to.

The benefits of this operation are that (i) either end of the path will know the full path, all intermediaries -although only the initiator of the Route Discovery process will know if the path is actually bi-directional; (ii) tra c engineering is possible -the destination router can wait and receive multiple RREQs, and elect to send RREPs in response to multiple RREQs, for example so as to ensure that multiple non-overlapping paths are made available for carrying tra c, and (iii) no intermediate routers are required to maintain any state.

The downside to RREQ-PA is, that the over-the-channel overhead can get large: RREQs are flooded through the network, and each additional octet added is amplified by the number of routers which are participating in the network, consuming channel capacity and energy, both.

Either way, once a path is established by way of RREQ-PA, user data is forwarded by way of source routing, carrying the complete path in each data packet: essentially, trading o↵ router state for channel occupation. An alternative, somewhat lighter, approach is to do path accumulation by way of RREPs: a router, seeing a path to a destination generates an RREQ, which is augmented by way of a flag requesting only the destination router to process the RREQ di↵erently: The regular LOADng processing of RREQs, specified in [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], is maintained, reverse paths installed, etc., by all intermediate routers.

When the destination router receives an RREQ indicating "path accumulation requested", it will generate an RREP -which, also, will contain that "path accumulation requested" flag -and send it in unicast along the reverse path installed when forwarding the RREQ. Then all the intermediate routers are accumulated in RREP messages. Figure 2(b) depicts an example of RREP-PA from A to D. Processing of an RREP in intermediate routers is changed, in a fashion similar to that of RREQ processing in section 2.1: on receiving a RREP, add the address of the router, and a distance to the source of the RREP. When the router, which initiated the Route Discovery process, receives this RREP, it will have acquired the complete path traveled between itself and the destination.

The benefits results of this operation are that (i) the source -but not the destination -acquires a full path, (ii) intermediate routers need only one entry towards the source -which, in case of path accumulation being used for providing a topological view of the network to a root means, that each intermediate router will maintain exactly one entry for the "upwards route" towards that root, and (iii) the size of RREQs, which are flooded through the network, does not change as compared to LOADng -which was otherwise the case for RREQ-PA.

The potential downside to RREP-PA is, that neither tra c engineering nor path diversity is enabled: (i) the destination router, responding to an RREQ, is not able to, in any meaningful way, select to respond to one RREQ over another (except for, that is, the metrics contained in the RREQ [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], since the RREQs do not carry any detailed path information, and (ii) when generating the RREP, this is forwarded in unicast and by way of the (unique) "reverse path" installed as part of RREQ processing.

In order to understand the performance impact of the path accumulation extension to LOADng, this section presents a set of ns2 simulations, comparing LOADng with and without path accumulation. Of particular interest is, of course, the size of routing table required, as well as the increase in control message size.

Simulation Settings

Simulations were made with static scenarios of 63 to 500 routers, randomly placed in a square field, but maintaining a constant density of routers. From among the routers, one is designated as "root" and the network is subject to traffic between the root and each other router in the network: sensor-to-root tra c, emulating a smart meeter sending its reading to a "controller", and SCADA-like bidirectional data exchange every 5 seconds, lasting for 80 seconds each. The simulations were undertaken using the TwoRayGround propagation model and the IEEE 802.11 MAC2 .

As discussed in section 1.2, path accumulation is proposed, in part, to reduce memory requirements in intermediate routers, and in part to provide a topological view of the network to a central management station in the network. As a consequence, the performance LOADng-CTP alone, as described in section 1.1, is compared with LOADng-CTP combined with RREQ-PA and RREP-PA.

Simulation Results and Discussions

For packet delivery ratio and end-to-end delay, all three protocols combinations exhibit similar performance, depicted in [START_REF] Yi | Collection Tree Extension of Reactive Routing Protocol for Low-Power and Lossy Networks[END_REF].

Figure 3(a) shows the average number of routing table entries required for the three protocol combinations. As expected, with path accumulation, the average number of routing table entries is (almost) constant -opposed to LOADng-CTP, where each router maintains state for its entire sub-tree. For the same reason, LOADng-CTP exhibits significant variance on the number of routing table entries, as shown in figure 3(b).

The overhead of RREQ messages (each RREQ retransmission is counted) is presented in figure 4. The number of RREQs retransmitted is generally the same, however as expected, RREQ-PA incurs larger RREQ messages, with as consequence up to twice as many bytes sent across the network as the LOADng-CTP and RREP-PA.

The overhead of RREP message transmission is given in figure 5, with RREQ-PA as expected exhibiting larger RREP messages and, thus, the most bytes sent across the network.

Based on the simulation results and the discussion in section 1, the characteristics of three protocol settings are summarised qualitatively in table 1.

Conclusion

Hop-by-hop routing requires each intermediate router to maintain routing entries -for a protocol such as LOADng, the worst case becomes four entries per active tra c flow it carries. In certain topologies, such as where there are "bottlenecks" or where all tra c originates/terminates in a single location in the network, the memory requirements that come from maintaining these entries by intermediate routers may be non-trivial to satisfy: in sensor networks, smart grid deployments, etc., devices typically measure their memory in KB (so as to keep the price, energy consumption, down), and "adding memory" to devices in such networks, once deployed, is impossible. Furthermore certain network deployments may require either control over which paths are used for data tra c, so as to enable tra c engineering, or information as to which paths have been used, e.g., for debugging. A reactive protocol, a core optimisation of LOADng is, that it not provides any devices with a complete topology map, but only provisions relevant "next-hop" information in intermediate routers on active paths.

This paper proposes a path accumulation extensions for LOADng (LOAng-PA), which addresses these issues. Using LOADng-PA path information is accumulated when an intermediate router forwards an RREQ or RREP message, and carried within that message towards the sought destination or to the originator of the route discovery process. Consequently, path diversity, tra c engineering, and path/topology visibility can be provided -and source routing used, eliminating the requirement of (worst case) recording four entries per active tra c flow carried across an intermediate router.

This paper has explored two di↵erent path accumulation extensions to LOADng, has enumerated their advantages and inconveniences, and has provided a performance study, by way of network simulations, quantifying their respective benefits. A key result is, that LOADng-PA e↵ectively is able to reduce the size of routing tables in intermediate routers -with the cost of slightly increasing the routing overhead, which is also quantified in this paper.

  Bi-directional tra c in a collection tree network.

Fig. 1 .

 1 Fig. 1. Example network topologies.

Fig. 2 .

 2 Fig. 2. RREQ-PA and RREP-PA examples. A is the source and D is the destination

Fig. 3 .

 3 Fig. 3. Routing table information

Fig. 5 .

 5 Fig. 5. RREP overhead

Table 1 .

 1 Characteristics of LOADng path accumulation

	4. RREQ overhead
	.
	LOADng-CTP RREQ-PA RREP-PA
	Source routing	no	yes	yes
	Network topology at the root	no	yes	yes
	Tra c engineering	no	yes	yes
	Path diversity	no	yes	no
	RREQ overhead	low	high	low
	RREP overhead	low	high	medium
	Sensor memory requirement	high	low	low

http://www.ietf.org

IEEE 802.11b is, of course, not suggested as a viable interface for LLNs, but serves to illustrate general protocol behaviours