Antonin Bas
email: antonin@antonin-bas.fr

Jiazi Yi

Thomas Clausen
email: thomas@thomasclausen.org

Expanding Ring Search for Route Discovery in LOADng Routing Protocol

LOADng is an on-demand routing protocol, derived from AODV, simplified for use in lossy, low-power and constrained environments, where the ability for devices to communicate is a commodity to their primary function, and where therefore not only the communications channel offers limited capacity, but also the resources available to the device's communications subsystem are limted.

LOADng simplifies AODV in a number of ways, notably the route discovery process by removing intermediate/gratuitous Route Replies -sacrificing that functionality in order to attain smaller control messages and less router state and processing. Alas, this comes at an expense: in some situations, LOADng produces increased control traffic overhead (as compared to AODV), and more control messages transmissions means tapping into the device's limited resources.

This paper presents a simple mechanism by which to integrate Expanding Ring flooding into LOADng. The mechanism is described, and the result of simulation studies are presented, showing that both in scenarios with "point-to-point" (any-to-any) traffic and in scenarios with "multipoint-to-point" (all traffic sent to the same destination, as in a data acquisition sensor network) traffic, considerable savings in control traffic overhead can be achievedwithout loss in data delivery ratios.

Introduction

For on-demand routing protocols like AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] and its derivatives (LOAD, LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]), the route discovery procedure is the most costly operation in the protocol. To discover a route to a certain destination, a Route Request (RREQ) message is flooded through the network. To reduce the flooding overhead and make use of existing routing information, AODV uses intermediate Route Reply (RREP) messages and Expanding Ring search, with the cost of more complex sequence numbers in the control packet to avoid loops.

LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] is a derivative of AODV, targeting routing in low-power and lossy networks, where the communications channel is characterized by a high risk of packet loss and (typically) very small frame sizes, very limited throughput, and where routers have strict bounds on memory, processing power and energy. This implies a requirement for a routing protocol of extreme simplicity: minimal state can be maintained, protocol operations must be simple, and control traffic must be minimal -both in terms of number of messages exchanged (each transmission takes energy and consumes network capacity better used for data) and in terms of the size of these messages, so as to avoid fragmentation. For example, using 6LoWPAN over 802.15.4 [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], leaves only 81 octets for payload in each frame transmitted -and, over a lossy network, fragmenting a packet naturally increases the risk of one of the frames in that packet being lost, thus loosing the whole packet.

LOADng simplifies AODV in a number of ways, as documented in [START_REF] Clausen | Loadng: Towards aodv version 2[END_REF] -and one of those simplifications is eliminating intermediate RREP, so as to guarantee loop freedom, and reduce the control message size and the complexity of protocol operation for constrained environments. A comparison of LOADng with RPL and AODV has been performed in [START_REF] Clausen | Loadng: Towards aodv version 2[END_REF][START_REF]Efficient data acquisition in sensor networks: Introducing (the) loadng collection tree protocol[END_REF]. To avoid increasing control overhead too much in some scenarios, LOADng also introduces

Paper Outline

The remainder of this paper is organized as follows: section 2 describes the Expanding Ring flooding mechanism, as used in AODV. Section 3 describes LOADng -the derivative of AODV for low-power and lossy networks -as well as the SmartRREQ extension, the simple and efficient mechanism replacing the intermediate RREPs otherwise used in AODV. Section 4 presents how to integrate Expanding Ring search into LOADng -the performance of which is studied by way of network simulations, and presented in section 5. Section 6 concludes this paper.

AODV and Expanding Ring Flooding

The basic operation in AODV is Route Discovery. During Route Discovery, RREQ messages are flooded trough the network, indicating the address to which a route is sought. Upon receiving an RREQ, the router which is responsible for the address listed in the RREQ will respond with an RREP, sent in unicast to the source of the RREQ. In AODV, if an intermediate router receiving the RREQ has a (valid) route to the address listed in the RREQ, it may send an intermediate RREP to the source of the RREQ, as well as a gratuitous RREP to the intended destination (both as unicast), so as to establish a bi-directional route. This permits, in some cases, avoiding an RREQ being flooded through the entire network, with the ambition of reducing the control traffic incurring from Route Discovery, illustrated in figure 1, which shows 5 routers from an N -router network (where N > 5). S initiates an RREQ for D. The neighbors of S: A, B, C already have valid routes to D. Without intermediate RREPs, all routers other than the destination have to retransmit the RREQ, i.e., there are at least N -1 RREQ transmissions. In contrast, with intermediate RREP, route discovery will remain local to the neighborhood of S: A, B, C would generate intermediate RREPs to S. Although in this example, those RREPs would be discarded as providing longer routes, using intermediate RREPs would avoid RREQs being disseminated blindly through the whole network.

Expanding Ring flooding

In AODV, an Expanding Ring flooding mechanism is used for route discovery, in order to further avoid network-wide dissemination of RREQs. A router will at first send an RREQ with a reduced TTL -causing the RREQ to not be flooded through the entire network, but only up to a limited distance. Only if no intermediate RREP results, will the router attempt to flood the entire network. [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] recommends starting with TTL=1, then do successive floods with the TTL increasing by 2 each time until TTL=7 -after which classic flooding is employed.

Note that while this may be an advantage in some cases, this mechanism can be a doubleedged sword, which may cause increased rather than decreased control traffic: if no router closer to the originator of an RREQ than the final destination has a route to the destination, much more control traffic can be generated by such repeated Expanding Ring floods.

LOADng and SmartRREQ

As a reactive distance-vector protocol and a light-weight derivative of AODV, LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] targets routing in low power and constrained environments. It inherits the basic properties and operations of AODV, including generation of Route Requests (RREQs) by a router (originator) for discovering a route to a destination, forwarding of such RREQs until they reach the destination router, generation of Route Replies (RREPs) upon receipt of an RREQ by the indicated destination, and unicast hop-by-hop forwarding of these RREPs towards the originator. If a route is detected broken, i.e., if the forwarding of a data packet to the recorded next hop on the route to the destination is detected to fail, local route repair can be attempted, or a Route Error (RERR) message can be returned to the originator of that data packet.

Compared to AODV, LOADng prohibits intermediate RREPs, in order to reduce the size of control messages1 and to reduce the state and processing required in routers in the network. Replacing intermediate RREPs, LOADng introduces an alternative route discovery scheme, denoted SmartRREQ, which introduces no additional signaling or data in RREQ/RREPs, nor any particular additional processing, yet permits taking the same benefits from the existing routing information present in intermediate routers, similar to what is done by intermediate RREPs. SmartRREQ works as follows: when a router receives an RREQ, it looks in its routing table for an already existing routing entry for the sought destination. If such an entry exists, and if its <next-hop> is not equal to the previous hop address of the RREQ, the RREQ is unicast to the <next-hop> instead of being broadcast.

In figure 2, Router S initiates a route discovery to Router D, while A and B have already available routes to D. On receiving the broadcast RREQ from S, A identifies that it already has a valid route to D, and so proceeds to unicast, rather than broadcast, the RREQ via the recorded path to D.

S A B D

RREQ uni-RREQ uni-RREQ

Expanding Ring flooding for LOADng

Because LOADng intermediate routers are not allowed to generate intermediate RREPs, Expanding Ring flooding in LOADng cannot be simply accomplished by progressively increasing an initially small TTL. Even if an intermediate router already has a valid route to the sought destination, the RREQ would still need to reach the destination -which would mean the TTL would have to be of a value at least equal to the distance between the source of the RREQ and the sought destination. Therefore, the TTL field in the IP header is not used for Expanding Ring flooding in LOADng. Rather, a new field is introduced in RREQ messages, denoted the MNB (Maximum Number of Broadcasts). This field is of the same size (8 bits) and behavior as the TTL field from the IP header, except that it governs only the number of broadcasts of RREQs permitted.

When initiating a route discovery in LOADng and with Expanding Ring flooding enabled, the originating router sets the MNB field to MNB START (similar to AODV TTL START), and sets the timeout for receiving an RREP to twice the value of the LOADng parameter NET TRAVERSAL TIME. If this timeout expires without a matching RREP having been received, a new RREQ is broadcast with a MNB field incremented by MNB INCREMENT. This continues until the MNB set in the RREQ reaches MNB THRESHOLD, beyond which the route discovery can either be declared a failure or continued with a MNB set to LOADng MAX HOP COUNT (i.e., 255), which corresponds to a network-wide flooding. Each time, the timeout for receiving an RREP is twice NET TRAVERSAL TIME.

Unlike the TTL, the MNB is not decreased by one on each hop. When an intermediate router receives an RREQ, it performs the following procedure before transmitting it:

1. If the RREQ message is to be unicast, which with SmartRREQ means that the intermediate router has an available routing tuple to the destination router in the routing table and that the <next-hop> field of the corresponding routing tuple is not equal to the previous hop address of the RREQ, then the RREQ MNB field is left unchanged.

2. If the MNB field has reached 0, then the RREQ is discarded.

3. Otherwise, the RREQ MNB field is decreased by one (and the RREQ is broadcast normally). Unlike for AODV, the RREQ timeout is constant and equal to twice NET TRAVERSAL TIME -which should correspond to the maximum time needed for an RREQ to traverse the whole network. The reason for this is, that regardless of the value of MNB, an RREQ in LOADng must travel all the way from S to D (and an RREP returned): in figure 4, a 5-hops route is found with an RREQ where MNB = 3.

With SmartRREQ, route discovery can be divided into two parts: (i) broadcast RREQ until a router with a valid route to the sought destination is encountered, then (ii) unicast RREQ towards the destination. Expanding Ring flooding tries to limit the number of routers impacted by (i), as well as the number of messages required by (i).

Simulation and Evaluation

This section presents the performance of LOADng using SmartRREQ, with and without Expanding Ring flooding enabled (MNB START = 1, MNB INCREMENT = 3), in two different traffic scenarios: sensor-to-root (multipoint-to-point -MP2P) traffic and sensor-tosensor (point-to-point -P2P) traffic. The performance is evaluated by way of network simulations, using NS2 [START_REF]Network Simulator -ns -2[END_REF], with LOADng implemented in Java and using AgentJ [START_REF] Herberg | Development Framework for Supporting Java NS2 Routing Protocols[END_REF] for interfacing the LOADng implementation with the NS2 network simulator.

Simulations are run with 63, 125, 250 and 500 nodes. Networks are generated randomly in a square area, which grows with the number of nodes so as to maintain a constant density of nodes in the network. For example, with 63 nodes, we use a 1095 × 1095 m 2 area. The transmission radius is set to 250 m. No mobility is considered in the simulations.

The network is subject to point-to-point (P2P) traffic or multipoint-to-point (MP2P) traffic with routers generating 80 second bursts of 512-octet data packets every 5 seconds

The number of layer 2 collisions, the average control overload and the average end-toend delay are measured. The control overload includes RREQ and RREP messages, and the end-to-end delay is defined as the time between data packet generation and its arrival at the destination. The end-to-end delay reflects the time needed to find a route to the destination router, and the time it takes for the data packet to be delivered.

MP2P Performance

For MP2P traffic scenarios, all the routers establish a route to the designated root, and generate data traffic to the root. The data delivery ratio is illustrated in figure 5(a) -noting that identical data delivery ratios are obtained for LOADng with and without Expanding Ring flooding. The number of collisions, overhead and delays are presented in figure 5.

P2P Performance

The network was subject to 100 concurrent and random (source, destination) traffic flows. The data delivery ratio is illustrated in figure 6(a) -noting that identical data delivery ratios are obtained for LOADng with and without Expanding Ring flooding. The number of collisions, overhead and delays are presented in figure 6.

Discussion

In the scenarios studied, the control traffic overhead was noticeably reduced when Expanding Ring flooding was enabled. For multipoint-to-point traffic, LOADng without Expanding Ring flooding generates twice as much control overload as when using Expanding Ring flooding, as shown in figure 5(c). However, this comes at the expense of an increase in end-to-end delays, both for MP2P and P2P traffic, shown in figure 5(d) and figure 6(d), respectively. This is due to the (high) value of the RREQ timeout, which is necessarily equal to two times the NET TRAVERSAL TIME, even if the RREQ MNB value is low. This delay increase is less pronounced for multipoint-to-point traffic, due to the increased likelihood that somebody close has a route to the (single) destination -but may not be acceptable for networks where point-to-point traffic is predominant, and where Expanding Ring search increases route discovery time (and thus data packet delivery delays) dramatically.

Conclusion

Expanding Ring flooding is one of the features from AODV which has not been carried over in the core specification of LOADng, in part because LOADng does not support intermediate/gratuitous RREPs. This paper presents a way in which Expanding Ring flooding can be introduced into LOADng, by way of using SmartRREQ and introducing a single-octet of extra information in RREQ messages -but, without requiring additional router state and signaling. A performance study of networks subjects to MP2P and P2P traffic has been performed, by way of network simulations, comparing LOADng with and without Expanding Ring flooding. Whilst maintaining identical data delivery ratios of 100%, the introduction of Expanding Ring flooding considerably reduces the control traffic overhead, especially when faced with MP2P traffic but also for P2P traffic. The downside to the use of Expanding Ring flooding, as described in this paper, is increased average end-to-end delays.

Thus, Expanding Ring search can be highly advantageous in networks where MP2P traffic is predominant and where a slight increase in average data delivery delays is acceptable.

Figure 1 :

 1 Figure 1: Route Discovery. S initiates an RREQ for D. A, B and C already know routes to D.

Figure 2 :Figure 3 :

 23 Figure 2: LOADng Route Discovery with smart RREQ. S initiates an RREQ for D. A and B already have an available route to D

Figure 4

 4 Figure 4 illustrates situations, where Expanding Ring flooding can decrease control traffic overhead: router S initiates a route discovery for D, the routers with double circles already have a valid routes to D. In figure 4(a), MNB START is set to 1, and the MNB INCREMENT

3 Figure 4 :

 34 Figure 4: An example of Expanding Ring flooding initiated by S for D. The white routers are not visited by RREQs, but would have been without Expanding Ring flooding enabled.

  Average end-to-end delay, in MP2P scenarios

Figure 5 :

 5 Figure 5: The Performance of Expanding Ring search for a MP2P scenario

Figure 6 :

 6 Figure 6: The Performance of Expanding Ring search for a P2P scenario

Low-power and constrained environments, typically, use network interfaces with very tiny MTUs: IEEE 802.15.4 with 6LowPAN, for example, accords an MTU of only 81 octets, rendering very small control messages a necessity, to avoid fragmentation.


Thomas Clausen
email: thomas@thomasclausen.org

Jiazi Yi

Axel Colin De Verdiere

LOADng: Towards AODV Version 2

The Ad hoc On-demand Distance-Vector routing protocol (AODV) was published in 2003 by the IETF, as experimental RFC 3561. This routing protocol was one of four routing protocols, developed by the IETF for use in mobile ad hoc networks (MANETs) -with the other being DSR, TBRPF and OLSR. As operational experiences with these protocols accumulated, the IETF set forth on standardization of OLSRv2, a successor to OLSR, and DYMO -with DYMO being the intended successor to DSR and AODV. Alas, while there was traction for and standardization of OLSRv2, interest in, development, standardization, and use of DYMO in MANETs slowly withered. AODV did, however, attract interest for routing in Low-power Lossy Networks (LLNs) due to its limited state requirements. Since 2005, several proposals for simplifying and adapting AODV specifically for LLNs emerged, in 2011 and 2012 with the use of one such adaptation of AODV in the G3-PLC standard for power line communications in smart grids, and with efforts within the IETF emerging towards a single LOADng specification, as next version of AODV.

This paper presents this development -from AODV, as specified in RFC3561 -to LOADng. While the basic operation remains unchanged, LOADng presents simplifications, and additional features and flexibilities are introduced. This paper studies the impact of these changes "from AODV to LOADng", and observes that LOADng unites simplification, flexibility and performance improvements.

I. INTRODUCTION

With the advancements of micro-controller and wireless technology, the concept of "being online" is no longer exclusively reserved for computers, but expected also for phones, vehicles, televisions, refrigerators, utility meters, etc. "The Internet of Things" assumes objects in our environment to be part of the Internet, communicating with users and with each other -and that these objects have communication as a commodity, rather than as their raison d'être.

Communication in "The Internet of Things" is a challenge, subject to resource constraints, fragile and low-capacity links, dynamic and arbitrary topologies. Among the challenges is routing, requiring efficient protocols, able to converge rapidly even in very large networks, while exchanging limited control traffic and requiring limited memory and processing power.

A. Background and History

Since the late 90s, the IETF1 has embarked upon a path of developing routing protocols for networks with increasingly more fragile and low-capacity links, with less predetermined connectivity properties and with increasingly constrained router resources. In '97, by chartering the MANET working group, then subsequently in 2006 and 2008 by chartering the 6LowPAN and ROLL working groups.

1) MANET Protocol Developments: The MANET working group converged on the development of two protocol families: reactive protocols, including AODV [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]. A distance vector protocol, AODV operates in an on-demand fashion, acquiring and maintaining routes 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. A sizable body of work exists, including [START_REF] Clausen | Comparative study of routing protocols for mobile ad-hoc networks[END_REF], studying the performance of these protocols in different scenarios, and justifying their complementarity [START_REF] Clausen | Analyzing control traffic overhead versus mobility and data traffic activity in mobile ad hoc network protocols[END_REF]. For the purpose of this paper, it suffices to observe that OLSR provides low delays and predictable, constant control overhead -at expense of requiring memory in each router for maintaining complete network topology. AODV limits the memory required for routing state to that for actively used routes -at the expense of delays for the Route Request-Route Reply exchange to take place, and control overhead dependent on data flows.

After acquiring operational experiences, the MANET working group commenced developing successors to OLSR and AODV, denoted OLSRv2 and DYMO. Whereas a relatively large and active community around OLSR thus standardized OLSRv2 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF], [START_REF] Clausen | Representing Multi-Value Time in MANETs[END_REF], [START_REF] Clausen | Mobile Ad Hoc Network Neighborhood Discovery Protocol[END_REF] and [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], the momentum behind DYMO withered in the MANET working group 2 .

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

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

B. Statement of Purpose

A successor to AODV, in this paper denoted LOADng, must support constrained environments, both in terms of computational power and memory, as well as in energy. An example platform is the ESB (Embedded Sensor Board [START_REF]The ESB Embedded Sensor Board[END_REF]), with a Texas Instruments MSP430 low-power micro-controller, an 1MHz CPU, 2kB RAM and 60kB flash ROM. The link layers typically used in LLNs impose strict limitations on packet sizes: in IEEE 802.15.4, the maximum physical layer packet size is 127 bytes, the resulting maximum frame size at the mac-layer is 102 bytes. If link-layer security is used, this may consume up to a further 21 bytes, which leaves just 81 bytes for upper layer protocols.

Flexibility is non-optional: IPv4 and IPv6 addresses are of different lengths, 6LowPAN [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF] proposes "short" addresses of 16 bits, AODV derivatives are used for routing at L2, where address lengths may be different again. Also, extensibility is required, to support e.g.,different link metrics, or future optimizations.

These constraints impose challenges to a routing protocol design, and can be summarized as follows: flexible and extensible, small code footprint and low code complexity, low memory and CPU usage -and, of course, low control traffic overhead.

This paper presents LOADng, designed with the above in mind: a slim core specification satisfying the listed constraints, designed to accommodate extensions. LOADng removes many elements from AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] -including intermediate RREPs, gratuitous RREPs, precursor lists, etc., the rationale behind removing these being detailed in this paper. These elements were originally proposed by [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] as performance optimizations -their removal therefore being justified by a performance comparison between AODV as specified in [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], and LOADng.

C. Paper Outline

The remainder of this paper is organized as follows. In section II, the LOADng core specification is introduced, including its new packet format and main operations. The simulation study is performed in section III, in which AODV and LOADng are compared. Section IV describes the modular approach to be used with LOADng, and we conclude the paper in section V.

II. LOADNG CORE SPECIFICATION

A reactive distance-vector protocol, LOADng inherits the basic properties and operations of AODV, including generation of Route Requests (RREQs) by a router (originator) for discovering a route to a destination, forwarding of such RREQs until they reach the destination router, generation of Route Replies (RREPs) upon receipt of a RREQ by the indicated destination, and unicast hop-by-hop forwarding of these RREPs towards the originator. If a route is detected broken, i.e., if forwarding of a data packet to the recorded next hop on the route to the destination is detected to fail, local route repair can be attempted, or a Route Error (RERR) message can be returned to the originator of that data packet. Compared to AODV, LOADng contains both extensions and simplification.

Extensions in LOADng:

• LOADng is modular. The core specification defines the simple and light-weight core functions of the protocol.

LOADng is extensible, by way of a flexible packet format permitting addition of arbitrary attributes and information via new message types and/or TLVs.

• Optimized Flooding is explicitly supported, reducing the overhead incurred by RREQ forwarding. Jitter is employed, to reduce the probability of losses due to collisions on lower layers [START_REF] Clausen | Jitter Considerations in MANETs[END_REF].

• Address lengths from 1-16 octets are supported 3 . The only requirement is, that within a given routing domain, all addresses are of the same address length.

• Different metrics are supported, to make better use of link information from different layers. Simplifications in LOADng:

• Only the destination is permitted to respond to an RREQ; intermediate routers are explicitly prohibited from responding to RREQs, even if they may have active routes to the sought destination. All messages (RREQ or RREPs) generated by a given router share a single unique, monotonically increasing sequence number. This also eliminates Gratuitous RREPs while ensuring loop freedom. The rationale for this simplification is reduced complexity of protocol operation and reduced message sizes -found to be without significant influence in the performance in section III.

• An LOADng router does not maintain a precursor list, thus when forwarding of a data packet to the recorded next hop on the route to the destination fails, a RERR is sent only to the originator of that data packet. The rationale for this simplification is an assumption that few overlapping routes are in use concurrently, and delay is not a critical issue in a given network.

A. Packet Format

LOADng defines four types of routing packets: Route Request (RREQ) Generated by a router, when presented with a data packet to a destination, for which it has no valid route, and containing the address of the destination for that data packet. Route Reply (RREP) Generated by a router, when it receives and processes a RREQ containing an address for which the router is responsible 4 as a response to a RREQ. Route Reply Acknowledgement (RREP-ACK)

Generated by an LOADng router as a response to a RREP, in order to signal to the neighbor which transmitted the RREP that the RREP was successfully received. Route Error (RERR) Generated by a router when a link on an active route to a destination is detected as broken, by way of inability to forward a data packet towards that destination. Figure 1(a) shows the general format of all types of packets, using the notation from [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF]: Where <tlv-block> contains zero or more Type-Length-Value elements (TLVs), and <message> field is an RREQ, RREP, RREP-ACK or RERR message. An example of RREQ/RREP message is illustrated in figure 1(b). The <metric> field specifies the function, by way of which two messages (say, RREQs) are compared so as to identify which has come through the "best" path. Such a function may be specified so as to use any information available, e.g.,<route-cost> 5 , <weak-links>6 and various TLVs, and must define how a router compares two received messages so as to determine which of them represent the "best" path.

LOADng allows protocol extensions to define additional message types, as well as additional TLV types, for inclusion in the message types defined in the core specification. Combined with the ability to define a <metric> using these TLVs, LOADng is thus accommodating for both functional extensions as well as refinements of core protocol operations for deployments with specific requirements.

B. Main Protocol Operations

LOADng retains the basic protocol operations from AODV, including Route Discovery and Route Maintenance, albeit in a greatly simplified form.

1) Route Discovery: During Route Discovery, RREQ messages are flooded trough the network. In LOADng, only the router, which is responsible for the address listed in the RREQ will respond with an RREP, sent in unicast to the source of the RREQ. This is a departure from AODV, in which an intermediate router, having a (valid) route to the address listed in the RREQ, would send a RREP to the source of the RREQ, as well as a gratuitous RREP to the intended destination (both as unicast). This simplification in LOADng permits eliminating intermediate RREPs, gratuitous RREPs, Destination Sequence Number and Originator Sequence Number in RREQ messages, reducing the per-packed overhead -and without significant influence in the performance.

2) Route Maintenance: Route Maintenance is performed when an actively used route fails. Route failure is detected by way of a data packet not being deliverable to the next hop towards the intended destination. In LOADng, when a route failure is detected, an RERR message is generated, sent as unicast along the route to the source of data packet. On receiving the RERR at the source of data packet, a new Route Discovery should be performed. This is a departure from AODV, in which each router maintains a list of "precursors", containing the IP address for each of its neighbors that are likely to use it for a next hop. When a router detects that data delivery over a link fails, it informs all neighbors, listed in this "precursor list". The simplification in LOADng of employing end-to-end signaling only permits eliminating the precursor list.

III. SIMULATIONS AND RESULTS

In order to understand, in particular, the performance impact of the extensions and simplifications, present in LOADng, ns2simulation results are presented in the below. Simulations were made of a field of 1000 × 1000 meters, with varying numbers of routers placed randomly. For the purpose of this study, router mobility was not considered. The network scenarios were subject to two different traffic patterns: point-to-point traffic (P2P), where (source, destination) pairs were chosen at random in the network, and multipoint-to-point (MP2P), where all routers generate traffic, for which the destination always is a single, fixed router in the network. The latter, e.g., simulating a data collection network.

Each data source transmits five 512-byte data packets per second, in bursts lasting for 80 seconds each, for a total simulation time of 100s. For each data-point in the figures below, 50 randomly generated scenarios, representing the same abstract parameters (density, number of traffic flows) and the results presented are the average hereof.

A. Point-to-point traffic

Figure 2 shows the packet delivery ratios, the average end-to-end delays, the number of collisions occurring in the network, and the routing overhead (in number of bytes), incurring from respectively AODV and LOADng, when the networks were subject to 30 concurrent (source, destination) pairs. Packet delivery ratios and delays are almost identical between the two version of the protocols, whereas LOADng incurs both fewer collisions (due to the use of jitter on flooding) and less control traffic overhead (due to smaller control packets) than does AODV.

B. Multipoint-to-point traffic

Figure 3 shows the packet delivery ratios, the average endto-end delays, and the routing overhead (in number of bytes), incurring from respectively AODV and LOADng, in the MP2P scenarios, i.e., where the network is subject to a heavier data traffic load: n -1 routers, all sending traffic to a single other router in the network. LOADng yields at least 10% higher data delivery ratios than does AODV, while incurring a dramatically lower control traffic overhead.

C. General Observations

The simulations presented accord some general observations: AODV, by way of using "intermediate RREPs" and expanding ring flooding for seeking to shorten delays, end up generating a few fewer control packets than does LOADng. However as LOADng's control packets are significantly smaller than those of AODV, the control traffic overhead of LOADng is substantially lower than that of AODV.

AODV does yield a shorter average delay than does LOADng -as shown in 3(b) for 80 routers or more. Note that in calculating the average delays, only data packets, successfully being delivered to their intended destination, are accounted -and in those high-density scenarios, LOADng delivers ∼50% more packets than does AODV.

IV. LOADNG COMPANION MODULES

As mentioned in section I, LOADng is designed to be modular. The aim is that the LOADng "core" specification be as slim as possible: small code footprint, low state and packet overhead, low processing -not to mention easy to implement and test. This, while remaining as general as possible: providing the ability to discover and maintain usable, short paths between any (source, destination) pair.

Specific scenarios (e.g., traffic patterns, density) and deployments (e.g., public or private, link characteristics, other protocols running on the routers) may benefit from specific optimizations. LOADng is designed so as to be able to accommodate these as plug-in modules, either by way of introducing new packet types, or by way of introducing additional TLVs to LOADng control packets (and specifying their processing)or simply by specifying additional in-router data structures and processing. This section indicates a few such plug-in modules, without intending to be exhaustive.

1) "Precursor Lists": was one feature, removed from AODV in creating LOADng. If many concurrently active routes are expected to transit routers at the same time, and that therefore a link breakage may disrupt many concurrent data flows, it may be justifiable for a router to sacrifice state and complexity to track these flows. In case of a link breakage detected, such a router generate and forward multiple RERR, each towards one of the the sources of these flows. A plug-in module, introducing "Precursor Lists", introduces additional state and processing in a router -which will be generating RERR messages, processed and forwarded by other routers as per LOADng. As this entails no additional signaling, does not impact interoperability, and is beneficial only in specific scenarios, it is not part of the "core" specification.

2) "Path Accumulation": for enabling source routing, an idea extracted from [START_REF] Johnson | The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks for IPv4[END_REF] and also used in [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] relieving intermediate routers from maintaining routing tables for the duration of the data traffic flow 7 . This functionality can be introduced in LOADng by way of introducing a TLV to a RREQ, to be inserted by the source of a RREQ and specifying that it be updated by each intermediate router such that the value of said TLV when received by the destination contains the succession of intermediate routers that have forwarded the RREQ. The <flags> field (figure 1 source instructs intermediate routers to "drop TLVs you don't understand before forwarding them", and TLV processing may specify that the routing table entries, recorded by RREQ/RREP be expired after a short time even if the routes they represent are being used.

3) Multi-path routing, Multicast tree construction, etc.: can likewise be supported by way of adding TLVs and specifying TLV processing, to provide backup route or building multicast tree in the network.

V. CONCLUSION This paper has presented LOADng, a proposed ultra-lightweight, extensible and flexible successor to AODV, applicable also in very constrained environments: low overhead, low computational and memory complexity. A preliminary performance evaluation has been conducted, which has shown LOADng yields comparative performance to that of AODVexcept that LOADng incurs a substantially lower control traffic overhead.

Figure 1 .

 1 Figure 1. LOADng packet and message format examples

Figure 2 .

 2 Figure 2. P2P Simulation Results -AODV and LOADng

Figure 3 .

 3 Figure 3. MP2P Simulation Results -AODV and LOADng

http://www.ietf.org/

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

i.e., IPv6, IPv4, 6LowPAN short addresses, L2 MAC addresses etc. are all supported by LOADng

i.e., an address of a destination, local to that router

In its simplest form, a basic hop count metric.

Links deemed, e.g., by a lower layer, to be marginally useful and which therefore should be avoided if at all possible.

Trading off 'bytes over the media" by way of source routing headers on each packet, for "bytes in memory"....

ACKNOWLEDGMENTS

The authors would like to thank Ulrich Herberg (Fujitsu Labs of America), Cedric Lavenu (EDF R&D), Thierry Lys (ERDF), Yuichi Igarshi and Satoh Hiroki (Hitachi YRL), as well as Charles E. Perkins (Tellabs) and Afshin Niktash (Maxim Integrated Products) for stimulating discussions and feedback on the work presented in this paper.


Jiazi Yi

Thomas Clausen
email: thomas@thomasclausen.org

Axel Colin De Verdiere

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

This paper proposes an extension to the "LLN On-demand Ad hoc Distance-vector Routing Protocol -Next Generation" (LOADng), for efficient construction of a collection tree for data acquisition in sensor networks. The extension uses the mechanisms from LOADng, imposes minimal overhead and complexity, and enables a deployment to efficiently support both "point-to-point" and "multipoint-to-point" traffic, avoiding complications of uni-directional links in the collection tree.

This paper further compares the performance of proposed protocol extension to that of basic LOADng and to the protocol RPL ("IPv6 Routing Protocol for Low power and Lossy Networks").

I. INTRODUCTION

"The Internet of Things" (IoT) assumes objects in our environment to be part of the Internet, communicating with users and with each other -and that these objects have communication as a commodity, rather than as their raison d'être. Communication in "The Internet of Things" is a challenge, subject to resource constraints, fragile and low-capacity links, dynamic and arbitrary topologies. Among the challenges is routing, requiring efficient protocols, able to converge rapidly even in very large networks, while exchanging limited control traffic and requiring limited memory and processing power.

One of the important applications of IoT is for data acquisition in sensor networks: a set of spatially distributed sensors that are used to monitor physical or environmental conditions, etc., and by their own impulse (either periodically or triggered by some event) transmit their data to a data concentrator (sink). These data are transmitted by way of a multi-hop network, and where the intermediary hops (routers) in that network are the sensor devices themselves. The collection of all paths from each sensor to the data concentrator form a collection tree. Traffic in such a collection tree is commonly described as being "multipoint-to-point" traffic, or "upwards" traffic, indicating that all traffic flows from the sensors to the data concentrator.

This paper describes a protocol for constructing such a collection tree in multi-hop sensor networks, where the protocol ensures that the resulting collection tree contains bi-directional paths between each sensor and the data concentrator. The protocol is defined as an extension to the LOADng routing protocol [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], which provides point-to-point routes between any two devices in a sensor network. Deploying both in unison permits efficient construction of both point-to-point routes and collection trees, by way of the same, simple, protocol mechanisms.

A. Background and History

Since the late 90s, the IETF1 has embarked upon a path of developing routing protocols for networks with increasingly more fragile and low-capacity links, with less predetermined connectivity properties and with increasingly constrained router resources. In '97, by chartering the MANET working group, then subsequently in 2006 and 2008 by chartering the 6LowPAN and ROLL working groups.

1) MANET Protocol Developments: The MANET working group has developed of two protocol families: reactive protocols, including AODV [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]. A distance vector protocol, AODV operates in an on-demand fashion, acquiring and maintaining routes only while needed for carrying data, by way of a Route Request-Route Reply exchange. A link state protocol, OLSR uses a periodic control messages exchanges, each router proactively maintaining a routing table with entries for all destinations in the network, which provides low delays but constant control overhead. A sizable body of work exists, including [START_REF] Clausen | Comparative study of routing protocols for mobile ad-hoc networks[END_REF], studying the performance of these protocols in different scenarios, and justifying their complementarity [START_REF] Clausen | Analyzing control traffic overhead versus mobility and data traffic activity in mobile ad hoc network protocols[END_REF].

2) 6LowPAN, ROLL and related Protocol Developments: The 6LowPAN working group was chartered for adapting IPv6 for operation over IEEE 802.15.4, accommodating characteristics of that MAC layer, and with a careful eye on resource constrained devices (memory, CPU, energy, ...). Part of the original charter for this working group was to develop protocols for routing in multi-hop topologies under such constrained conditions, and over this particular MAC. Two initial philosophies to such routing were explored: mesh-under and routeover. The former, mesh-under, would, as part of an adaptation layer between 802.15.4 and IP, provide L2.5 multi-hop routing, presenting an underlying mesh-routed multi-hop topology as a single IP link. The latter, route-over, would expose the underlying multi-hop topology to the IP layer, whereupon IP routing would build multi-hop connectivity. Several proposals for routing were presented in 6LowPAN, for each of these philosophies, including LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF]. LOAD was a derivative of AODV, but adapted for L2-addresses and mesh-under routing, and with some simplifications over AODV (e.g., removal of intermediate router replies and sequence numbers). However, 6LowPAN was addressing other issues regarding adapting IPv6 for IEEE 802.15.4, such as IP packet header compression, and solving the routing issues was suspended, delegated to a working group ROLL, created in 2008 for this purpose. ROLL produced a routing protocol denoted "Routing Protocol for Low-power lossy networks" (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] in 2011 based on the idea of collection tree protocol [START_REF] Gnawali | The Collection Tree Protocol (CTP)[END_REF].

RPL as a collection tree protocol has several well known issues with respect to supporting different kinds of traffic patterns, uni-direction link handling, as well as algorithmic and code complexity [START_REF] Clausen | Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. On the other hand, AODV and its derivatives have been implemented and used widely, such as IEEE 802.11s [START_REF] Hiertz | Principles of ieee 802.11s[END_REF] is based on AODV, and the G3-PLC standard [START_REF] Itu-T G | Narrow-Band OFDM power line communication transceivers -Data link layer specification[END_REF], published in 2011, specifies the use of LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] at the MAC layer, for providing mesh-under routing for utility (electricity) metering networks. Spurred by these experiences, 2011 saw the emergence of LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], as a successor to LOAD, and for deployments where the issues in [START_REF] Clausen | Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] render RPL less applicable.

LOADng, as LOAD is however designed mainly for pointto-point traffic, and not optimized for multipoint-to-point traffic.

B. Statement of Purpose

An extension to LOADng, denoted LOADng Collection Tree Protocol (LOADng-CTP), is proposed in this paper , for building a "collection tree" in environments, constrained in terms of computational power, memory, and in energy. An example of the design target for LOADng-CTP is the ESB (Embedded Sensor Board [START_REF]The ESB Embedded Sensor Board[END_REF]), with a TI MSP430 low-power micro-controller, an 1MHz CPU, 2kB RAM and 60kB flash ROM. The link layers typically used in LLNs impose strict limitations on packet sizes: in IEEE 802.15.4, the maximum physical layer packet size is 127 bytes, the resulting maximum frame size at the mac-layer is 102 bytes. If link-layer security is used, this may consume up to a further 21 bytes, which leaves just 81 bytes for upper layer protocols.

The LOADng-CTP presented in this paper is thus designed to meet the following requirements:

• Effectively build a route from all sensors to the root, and the route from the root to the sensors if required. • Uni-directional links being avoided in these routes.

• Low overhead, easy collection tree maintenance.

• Easy extension to LOADng, such that routers using only LOADng (without collection tree extension) can joint the collection tree. The remainder of this paper is organized as follows: In section II, the LOADng-CTP specification is introduced, including related message format and main operations. The simulation study is performed in section III, in which LOADng, LOADng-CTP and RPL are compared. Section IV concludes this paper .

II. PROTOCOL SPECIFICATION

LOADng Collection Tree Protocol (LOADng-CTP) is based on the operation and packet format of LOADng. Therefore, the current LOADng implementation can be easily extended to the collection tree protocol. In the following, the basic operation of LOADng is introduced briefly, followed by the single message and protocol processin required for collection tree building and maintenance.

A. LOADng Basic Operation

LOADng contains two main operations: Route Discovery and Route Maintenance.

1) Route Discovery: During Route Discovery, RREQ messages are flooded through the network. In LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], only the destination of the RREQ will reply by generating and unicasting a RREP to the originator of the RREQ. All RREQ and RREP messages, generated by a LOADng router, carry a monotonically increasing sequence number, permitting both duplicate detection and detecting which of two messages contains the most "fresh" information.

2) Route Maintenance: Route Maintenance is performed when an actively used route fails. Route failure is detected by way of a data packet not being deliverable to the next hop towards the intended destination. In LOADng, the RERR is unicasted to the source of data packet. On receiving the RERR at the source of data packet, a new Route Discovery can be performed, in order to discover a new route to the intended destination.

B. Message for Collection Tree Protocol

LOADng-CTP introduces two flags to RREQ messages:

• RREQ COLLECTION TREE TRIGGER: when set, a receiving routers will be triggered to discover with which of its neighbors it has bi-directional links. • RREQ COLLECTION TREE BUILD: when set, a receiving router will build the route to the root. In addition, a HELLO message is used, in order to permit verification of bidirectionally of links before admitting these to the collection tree.

C. Collection Tree Building

The collection tree is, then, build by way of the following procedure -initiated by the router wishing to be the root of the collection tree:

1) Collection tree triggering (by the root): The root generates an RREQ with COLLECTION TREE TRIGGER set (henceforth, denoted RREQ TRIGGER). Both the originator and destination of the RREQ TRIGGER are set to the address of the root.

When a RREQ TRIGGER is generated, an RREQ with COLLECTION TREE BUILD set (henceforth, denoted RREQ BUILD) is scheduled to be generated in 2×NET TRAVERSAL TIME.

2) Bi-directional neighbor discovery: On receiving a RREQ TRIGGER, a router:

• Records the address of the sending router (i.e.,the neighbor, from which it received the RREQ TRIGGER) in its neighbor set, with the status HEARD. • If no earlier copy of that same RREQ TRIGGER has been previously received:

-The RREQ TRIGGER is retransmitted, subject to a jitter 2 of RREQ JITTER, to reduce the chance of collisions.

-Schedules generation of a HELLO message, subject to a jitter of HELLO JITTER 3 . When the scheduled HELLO message is generated, it lists the addresses of all the neighbors, from which it has received a RREQ TRIGGER. On receiving a HELLO message, a router:

• If it finds its own address listed in the HELLO message, it records the address of the sending router (i.e.,the neighbor, from which it received the HELLO) in its neighbor set, with the status SYM (bi-directional). Thus, each router will learn with which among its neighbor routers it has a bi-directional (SYM) or uni-directional (HEARD) link.

3) Collection tree building: 2×NET TRAVERSAL TIME after the RREQ TRIGGER, the root generates a RREQ BUILD.

On receiving a RREQ BUILD, a router:

• Verifies if the RREQ BUILD was received from a neighbor with which it has an uni-directional link. If so, the RREQ BUILD is silently discarded. • Otherwise, if no earlier copy of that same RREQ BUILD has been previously received, a new routing entry is inserted into the routing table, with (next hop = previous hop of the RREQ BUILD; destination = root) -The RREQ BUILD is retransmitted, again subject to a jitter of RREQ JITTER. Thus, each router will record a route to the root, and this route will contain only bi-directional links; the collection tree is built, enabling upward traffic.

If also routes from the root to other routers (sensors) inside the network is required, each router receiving a RREQ BUILD will unicast a RREP to the root, transmitted and processed according to [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]. Thus, also downward traffic is enabled.

D. Collection Tree Maintenance

During the process described in section II-C, control messages may be lost. Thus, some routers may not be included in the initial collection tree because of transient transmission failure of collection tree building messages. Furthermore, the routing entries may expire because of not updated timely. Both of those result in that route to the root is not available in some of the sensors.

In this case, a router with data traffic to send to the root will initiate route discovery, according to the usual procedures from [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]. To avoid that RREQ being broadcast through the whole network, and take benefits from that "most of other neighbor routers might have an available route to the root", a Smart Route Request scheme can be employed: if an intermediate 2 According to the recommendations in [START_REF] Clausen | Jitter Considerations in MANETs[END_REF]. 3 Where HELLO JITTER > RREQ JITTER router, receiving the RREQ, does not have an available route to the destination, the RREQ is forwarded as normal. If the intermediate router has a route to the root, that intermediate router will unicast the RREQ to the destination according to the routing table. For the routers that only run LOADng, without collection tree extension (i.e.,they can't be verified as bi-directional neighbors because they can't generate HELLO message on receiving RREQ TRIGGER), they can join the collection tree in the same way.

When a link on an active route to a destination is detected as broken (by way of inability to forward a data packet towards that destination), an RERR (route error) message is unicast to the source of the undeliverable data packet. Both this intermediate router and the source router need to initiate a new route discovery procedure.

III. SIMULATION AND PERFORMANCE ANALYSIS

In order to understand the performance impact of the collection tree extension to LOADng, this section presents a set of ns2 simulations, comparing LOADng, LOADng-CTP and RPL, with the parameters of the trickle timer in RPL is set according to [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] Simulations were made with varying numbers of routers from 63 to 500, equipped with IEEE 802.11 wireless interfaces, and placed statically randomly in a square field while maintaining a consistent network density.

The network is subject to multipoint-to-point (MP2P) traffic with all routers generating an 80 seconds burst of 512-octet data packets every 5 seconds, towards a single destination (sink).

A. Simulation Results

Figure 1 depicts the delivery ratio of three protocols. Both LOADng-CTP and RPL obtain delivery ratios close to 100%, regardless of number of nodes. LOADng, initiating route discovery for every router (network-wide broadcast), incurs a high number of collisions on the media, and thus a lower data delivery ratio, especially in larger scenarios. The data delivery delay is depicted in 2, showing that while LOADng-CTP and RPL have routes a-priori available, the route discovery process of LOADng causes longer delays. From these figures, LOADng-CTP and RPL exhibit identical performances. Figures 3 and 4 depict the control traffic overhead in total number of packets sent, and number of bytes/s , respectively, required for every router to have a route to the root.

The overhead of LOADng-CTP and RPL grow linearly with RPL sending twice as many packets as LOADng-CTP, and RPL sending 10 times more bytes/s as compared to LOADng-CTP, due to the RPL control packets (mainly, the DIOs) being bigger [START_REF] Clausen | Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]: a DIO packet4 takes up to 40 octets in these scenarios, whereas a LOADng-CTP RREQ and RREP packet typically is 10 octets. The overhead of LOADng grows exponentially as the number of nodes increases, up to 700,000 packets for scenarios of 500 nodes (not drawn in the figure). The peer-to-peer based basic LOADng mechanism is not optimized for MP2P traffic. IV. CONCLUSION This paper has presented a simple extension, LOADng-CTP, to the reactive LOADng routing protocol, permitting efficient and on-demand construction of collection trees for supporting MP2P traffic types. The performance of this extension has been studied, revealing delays and data delivery rations, comparable with RPL, are obtained while at the same time yielding considerably lower control traffic overheads. Compared to basic LOADng, the performance of the LOADng-CTP extension yields better performance: lower overhead, higher data delivery ratios, and lower delays.

It is worth noting that all the links used in LOADng-CTP routes are validated as bi-directional, whereas RPL, links in the collection tree are validated only to be uni-directional from root to the sensors (but not validated as bi-directional). While the simulations in this paper do not reveal any ill effect (in part, because most links turned out to be bi-directional), it is expected -and a subject for further study -that in scenarios with a higher number of uni-directional links, LOADng-CTP will outperform RPL.

Another key aspect of LOADng-CTP is, that any router can at any time determine that it needs to act as a data sink for MP2P traffic, and spawn a collection tree construction; this, without requiring that said router be specifically provisioned for this purpose (no extra state, processing power, required).

Figure 2 .Figure 3 .Figure 4 .

 234 Figure 1. Packet delivery ratio

http://www.ietf.org/

Base header of 24 octets, plus other options and addresses.


Jiazi Yi

Thomas Clausen
email: thomas@thomasclausen.org

Vulnerability Analysis of Relay Set Selection Algorithms for the Simplified Multicast Forwarding (SMF) Protocol for Mobile Ad Hoc Networks

After more than a decade of research and standardization, Mobile Ad Hoc NETworks (MANET) are finding their place in real-world deployments, such as in community, tactical and vehicular networks. Becoming so present in "the real world" also means that MANETs, and the protocols operating them, are affronted with a more hostile environment, where misconfiguration, eavesdropping, and attacks must be addressed. A first step in addressing MANET security is understanding the vulnerabilities of MANET protocols, and how an attacker can exploit these.

This paper studies the Relay Set Selection (RSS) algorithms that are commonly used in multicast routing protocol for MANETs, and which are undergoing standardization as part of the Simplified Multicast Forwarding (SMF) protocol, developed within the Internet Engineering Task Force (IETF). Attack vectors for these different RSS algorithms are described, with the purpose of enabling future development of security solutions.

I. INTRODUCTION

Network security is as old as networking, and as vast as authentication, non-repudiation, integrity, etc. In traditional wired networks, security is largely based on maintaining physical control of access to the communication channel (fiber, coaxial cable, etc.). In a wireless MANET environment, routers and hosts are more vulnerable to different threats since:

• Physical access to the wireless medium is not delimited by wired cables, but available to anyone within transmission range. Furthermore, compared to a wired media, a wireless medium is more unreliable and unpredictable, rendering behavioral observation more difficult; • Resources in mobile devices are often constrained, both in terms of CPU power, memory space, battery life, etc. Such limited resource render the network more vulnerable to attacks, especially Denial-of-Service (DoS) attack by maliciously consuming the transmission channel, CPU time, or resulting in memory overflow; • The topology of a MANET is dynamic due to both mobility of routers and variations in the wireless channel. This implies that the use of traditional mechanisms such as checkpoints, firewalls on ingress filtering based on apriory knowledge is less obvious. Given the above, if for MANETs to stand a chance outside the protected confines of research laboratories, security issues have to be addressed. MANET deployments must consider that misconfiguration and malicious routers are present, and that neither physical media control nor a-priori topology knowledge are viable security approaches.

A. Background and History

The "Simple Multicast Forwarding" (SMF) protocol [START_REF] Macker | Simplified Multicast Forwarding[END_REF] is a multicast routing protocol for MANET-wide efficient broadcasting. The protocol employs reduced relay sets for reducing the number of redundant retransmissions of a data packet in the network. Reduced relay sets so used were introduced in and standardized for IP networks by way of the Optimized Link State Routing Protocol (OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF]) in 2003, where they were used for substantially reducing the protocol overhead incurred by diffusion of link state advertisements, in [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] denoted "TC messages". The reduced relay set mechanism in OLSR is based on Multi-Point Relays (MPRs) [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF]. This concept was retained and used in an extension of OSPF for MANET areas [START_REF] Clausen | OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF]. Other experimental routing protocols, including [START_REF] Ogier | Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)[END_REF] and [START_REF] Ogier | Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding[END_REF], have used different reduced relay set mechanisms, and the Internet Engineering Task Force (IETF) is standardizing the next-generation MANET routing protocol OLSRv2 [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], retaining the MPR concept. The experimental reactive MANET routing protocol AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] also uses MANET-wide broadcast of its route requests -for which [START_REF] Clausen | Optimizing Route Length in Reactive Protocols for Ad Hoc Networks[END_REF] showed that using MPRs for flooding route requests resulted not just in reduced channel load, but also in shorter unicast paths.

The success of reduced relay sets for diffusion of routing protocol control traffic lead to work on using the same mechanisms also for user data traffic, including [START_REF] Jacquet | Diffusion mechanisms for multimedia broadcasting in mobile ad hoc networks[END_REF] and [START_REF] Clausen | Investigating broadcast performance in mobile ad-hoc networks[END_REF], ultimately leading to the IETF development of SMF [START_REF] Macker | Simplified Multicast Forwarding[END_REF], as an experimental protocol. SMF provides basic IP multicast routing for MANETs. It consists of two main components: multicast "Duplicate Packet Detection" (DPD) and "Relay Set Selection" (RSS).

• DPD is used in the forwarding process to identify if an incoming packet has been previously received (and forwarded) -and thus should be dropped -or not. DPD is achieved by a router maintaining a record of recently processed multicast packets, and comparing received multicast packets herewith. A duplicate packet detected is silently dropped, and not inserted into the forwarding path of that router -nor delivered to an application.

• RSS yields a reduced relay set for relaying data packets across a MANET. SMF supports several RSS algorithms: E-CDS (Essential Connected Dominating Set), S-MPR (Source-based Multi-Point Relay), and MPR-CDS, based on localized election and derived from those explored for topology diffusion in MANET routing protocols.

B. Statement of Purpose

RSS algorithms for efficient flooding have been well studied for performance and convergence properties. However it is generally assumes that all routers in the networks can be trusted to perform their part in the RSS algorithm properly. In the "Real World", where a wireless channel is accessible to anyone within radio-range, this can not be assumed be that due to router misconfiguration or malice.

This paper analyses the vulnerabilities of the different RSS algorithms, proposed by SMF [START_REF] Macker | Simplified Multicast Forwarding[END_REF]. It is worth noting that SMF, as an experimental protocol, does not prescribe a preferred RSS algorithm, but rather serves to document the different options and encourage experiments and evaluation in order to determine -by way of testing against "the real world" -which eventually becomes preferred. Part of this "testing against the real world" -and the ambition of this paper -is testing how an RSS algorithm stands up against different security threats.

While the paper has the ambition of being through, in matters of security it is prudent to be explicit to not claim completeness of analysis.

C. Paper Outline

The remainder of this paper is organized as follows: section II, describes general threats, commonly applicable to all RSS algorithms; section III, section IV and section V, then specifically studies vulnerabilities to E-CDS, S-MPR and MPR-CDS, respectively. This paper is concluded in section VI.

II. GENERAL THREATS TO RELAY SET SELECTION

A. Eavesdropping

Eavesdropping is a common and easy passive attack in a wireless environment. Once a packet is transmitted, any close receiver can obtain a copy without being detected, for immediate or later decoding. SMF uses a neighborhood discovery protocol, NHDP [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] for providing each router with 1-hop and 2-hop topological information, permitting RSS algorithms to operate. A malicious router can eavesdrop on the NHDP message exchange and thus learn this local topology information, as well as some source and destination addresses of data packets transmitted. Eavesdropping is not direct threat to the network integrity, nor to SMF, but it can provide crucial network information such as identity of communicating routers, link characteristic, router configuration, etc., enabling other attacks.

B. Message Timing Attack

As NHDP is used to provide local topology information for RSS algorithms, NHDP vulnerabilities thus affect SMF. NHDP HELLO messages define two types of timing information:

• Validity time, the time during which the information conveyed by the message should be considered valid. • Interval time, the time after which the next control message from the same router should be expected. For validity time, an attacker can simply eavesdrop on HELLOs, then instantly upon receipt replay the HELLO -but modified to have a low validity time, illustrated in figure 1. Router b broadcasts a HELLO with valiT ime = 6s. Router a receives the HELLO and marks the link between itself and b is valid for 6 seconds. X eavesdrops on the messages, obtains the identity of router b, then transmits the HELLO with valiTime=0.1s. Receipt of this message by a causes a to replace previously received link information, and therefore consider the link between itself and b as invalid after very short time (0.1 second). For SMF, this means that b will not be selected as relay by a even it may provide good connectivity to other parts of the network. A similar attack exists for interval time: a malicious router behaves as above, and also indicate a low interval time. A recipient of a HELLO with interval time so modified will expect a subsequent HELLO within this very short timewhich will not arrive: the recipient decreases the link quality, or may discard this link. Further vulnerabilities to the NHDP exist [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol Version 2 (OLSRV2)[END_REF].

C. Indirect Jamming

For NHDP, a malicious router can -intentionally and frequently -alter the neighborhood information, link state, etc. declared in HELLOs, and thereby cause generation of inordinate amounts of control traffic by legitimate routers and increase the resources required for message processing [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol Version 2 (OLSRV2)[END_REF].

Used by all RSS algorithms, indirect jamming of NHDP is a threat to every SMF router: a malicious router can generate plausible control traffic to in turn trigger receiving routers to generate additional traffic, e.g.,a malicious router can keep changing its router priority to provoke recalculation of and signaling of relay sets.

D. RSSV Attack

SMF uses distributed RSS algorithms that dynamically calculate a topological Connected Dominating Set (CDS), generally assuming 1-hop and 2-hop neighborhood information as provided by NHDP. SMF supports different, and noninteroperable, RSS algorithms -and, hence, SMF routers convey to their neighbors which algorithm(s) they respectively support. To this end, [START_REF] Macker | Simplified Multicast Forwarding[END_REF] defines a "Relay Set Selection Vector" (RSSV), by way of message and address block TLVs [START_REF] Clausen | Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF], to be included in the NHDP HELLOs such that an SMF router can declare which RSS algorithms it, and its immediate neighbors, support 1 . An SMF outer must therefore select relay sets according to compatibility of the algorithms operating in SMF routers in its 1-hop and 2-hop neighborhoods. A potential attack is, therefore, if a router -intentionally or otherwiseshare false RSSV information for itself or for its neighbors.

For example, in figure 2, router a is about to select its relays. The following RSS algorithms are used in different routers:

• E-CDS: router b, d, e • S-MPR: router c, f, g • MPR-CDS: router h All routers, faithfully, declare their RSSV. Based on the messages from routers b, h and c, router a learns what algorithms are supported by both its direct neighbors and its 2-hop neighbors. This allows router a to observe that while router h provides topological coverage to all of the 2-hop routers (d, e, f, g), router h runs an RSS algorithm different from all of d, e, f, g. Therefore, if a selects h as relay, h may not be able to select relays among d, e, f, g and thus packet forwarding beyond d, e, f, g would not happen. Router a also learns that router b runs the same RSS algorithm as the 2hop neighbors d, e, reachable b -and that router c runs the same RSS algorithm as the 2-hop neighbors f, g, reachable via c. Router a can therefore select b and c as relays, knowing that both of these will be able to not only provide coverage to all 2-hop neighbors, but also be able to select proper relays among these 2-hop neighbors. A malicious router, spoofing the RSSV of its 2-hop neighbors, is shown in figure 3: X declares itself with RSSV=MPR-CDS, and further declares that d, e, f, g have RSSV=MPR-CDS. Thus, router a choses X as sole relay: from the information available to a, X provides optimal topological coverage of the 2-hop neighborhood -and by running the same RSS as (declared for) all 2-hop neighbors, should be able to also do proper relay set selection with these. As a consequence, X will "take control" of the multicast traffic in its neighborhood -in this case, be able to prohibit b and c from being selected as relays and, thus, if X isnot actually forwarding traffic or performing RSS, disrupt network connectivity. Furthermore, the indirect jamming attack mentioned in the previous subsection is also applicable to RSSV signaling by changing the RSSV type continuously.

III. E-CDS VULNERABILITIES

The Essential Connected Dominating Set (E-CDS) RSS algorithm produces a common set of relays for all routers in the network. Routers self-select as relays based on priority information and of the 1-hop and 2-hop neighborhood topology. The priority of a router can be e.g.,, a router metrics (such as power level) or simply a tie-breaker such as the router address. Using E-CDS, a router self-select as relay if and only if:

• the router's router priority is greater than the priority of all its two-hop neighbors, OR • there is no path from the highest priority neighbor to all other one and two hop neighbors using only routers with greater priority as relays. A malicious router can disrupt E-CDS selection, by way of link spoofing and identity spoofing, discussed separately.

A. Link Spoofing

Link spoofing implies that a router advertises non-existing links to another router (present in the network or not). Based on NHDP, a malicious router can perform link spoofing by modifying HELLOs.

In figure 4, where solid lines illustrate actual links whereas dotted lines "spoofed" links, router a tries to make E-CDS relay set selection based on the one-hop and two-hop neighborhood information from router b, c, d and e (The router priority is as indicated in figure 4). If the algorithm runs properly, a will choose itself as a relay, because it has the highest priority among its two-hop neighbors. Alas, present is also a malicious router, X, which (i) declares itself with the highest priority in the neighborhood (RtrP ri = 6), and (ii) advertises links (real or spoofed) to all of a's one-hop and two-hop neighbors. By thus presenting itself as a router with high priority and strong connection with other routers, a will not be able to select itself as relay: X appears as providing better coverage and higher priority. The effect of link spoofing depends on the local topology and the ability to eavesdrop: the biggest impact can be achieved when information describing all the 2-hop links of router a is available to X. If some of the 2-hop neighbors of a are 3-hop from the malicious attacker X, shown in figure 5, X can not obtain the identity of router c directly through NHDP -limiting the effect of such an attack. Thus, malicious routers disrupt the network by preventing legit routers from self-selecting as relays. Link-spoofing can also cause routers to (unnecessarily) self-select relays, with the goal of degrading the flooding operation to classic flooding. This is illustrated in figure 6, where solid lines illustrate actual links whereas dotted lines "spoofed" links: router a with low priority (RtrP ri = 2) will not self-select since b both has the highest priority (RtrP ri = 5)in the 2-hop neighborhood, and can provide links to all other neighbors of a by way of relays with higher priority than a. Alas, present is also a malicious router X which (i) declares itself with the lowest priority (RtrP ri = 1), and (ii) spoofs a link to (fictive or present) router z. As a consequence, a has to self-select as relay no route to z, using only routers withs greater priority than a, exists. This will be the case for all the neighbors of X, therefore the E-CDS is by way of this link spoofing attack degraded locally to classical flooding locally (discussed further in section V-A).

B. Identity spoofing

Identity spoofing implies that a malicious router determines and makes use of the identity of other routers, without being authorized to do so. A malicious router can obtain the identity of a legitimate routers by overhearing HELLOs, or source/destination addresses from the data traffic. The malicious router can, then, generates (routing or data) traffic, pretending to be the legitimate router.

As shown in figure 7, at time t 0 , router b sends a HELLO , declaring its priority RtrP ri = 1. Router a hears the HELLO and updates its information bases accordingly. The malicious router X also receives the same HELLO, records the address of b, and the sequence number of the HELLO, and then transmits a HELLO immediately at time t 1 (e.g.,100 ms after t 0 ), with the address of router b, with a higher sequence number (so as to make the message appear legitimate) and with a modified router priority (RtrP ri = 6). On receiving this second HELLO, router a will see it as simply reporting updated information from a. As HELLO are sent periodically, X can time its transmissions such that a will operate with incorrect information for b. In this particular case, it will prevent a from self-selecting as relay.

IV. S-MPR VULNERABILITIES

The Source-based Multipoint Relay (S-MPR) RSS algorithm is derived from [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] and [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], and enables routers to select a reduced relay set (called the routers MPR set) from among their one-hop neighbors such that a message generated by a router and relayed by its MPR Set will be received by all routers 2-hops away. Once a router has selected its MPR set, it signals this (embedded in a HELLO) to the neighbors it has selected as MPR. An S-MPR router forwards a multicast packet if and only if:

• the packet is never before received, AND • the packet was received from a neighbor with which it has a bi-directional link, AND • and the neighbor from which the packet was received has selected the router as an relay. As with E-CDS, a malicious router can, by spoofing the link or the identity of specified routers, disrupt the proper functioning of the S-MPR RSS.

A. Link Spoofing

Routers that run S-MPR select relays from among their one-hop neighbors. To reduce redundant data transmissions, the routers with better connectivity are given priority when considered as relays. Thus, a malicious router can spoof the links to other routers to prevent that other, legitimate, routers be selected. This is illustrated in figure 8, where solid lines illustrate actual links whereas dotted lines "spoofed" links. Router a is selecting its relays from among X and b. If both X and b faithfully declare their neighborhoods, b has to be chosen so as to make sure that a message generated by a and relayed by the selected MPRs reach all routers 2-hops away from a (i.e.,d, e). Alas, X is malicious and spoofs links to d and e -in addition to a link to the fictitious router, c. As a consequence, when a is running S-MPR algorithm, it only choses X as its MPR as it believes that X can provide links to all the two-hop neighbors of b, in addition to the fictitious c. If X then ultimately does not relay multicast traffic d and e are rendered unreachable.

B. Identity Spoofing

By overhearing HELLOs, the identity of other routers in the network may be available for a malicious router. In NHDP, HELLO messages are additive, thus a malicious router can inject vicious incorrect additional information by spoofing the identity of a detected legitimate router. This is illustrated in figure 9, where solid lines illustrate actual links whereas dotted lines "spoofed" links, and where router a is selecting relays from among its one-hop neighbors. Absent any malicious routers, b will be chosen as relay by a's. Alas, present is also a malicious router X, which (i) spoofs the identity of router c, and (ii) declares links to d and (a fictitious or present) f. Consequently, a selects only c as its relay, rendering d ultimately unreachable for multicast traffic from a.

V. MPR-CDS VULNERABILITIES

MPR-CDS [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF] is a derivative from S-MPR which -as E-CDS -results in a common set of relays for all routers in the network. In MPR-CDS, the MPR selection and signaling from S-MPR is performed, but the forwarding rules are different, specifically forwarding does not depend on from which router a packet is received. An MPR-CDS router forwards a multicast packet if and only if:

• the packet is never before received, AND the router's priority is higher than the priority of all its 1-hop neighborhood, OR the router has been selected as an relay by the router that has the highest priority in its 1-hop neighborhood. It is worth noting that the main difference between S-MPR and MPR-CDS is, that while MPR-CDS forms an unique broadcast tree for all sources in the network, S-MPR forms a different broadcast tree for each source in the network.

Nevertheless, as MPR-CDS combines E-CDS and S-MPR, the vulnerabilities of E-CDS and S-MPR, discussed in section III and section IV also apply to MPR-CDS. One additional vulnerability is introduced, though: a simple way of degrading the network into classic flooding.

A. Broadcast Storm

In wireless MANETs, a broadcast storm due to classic flooding causes serious performance degradation: two or more adjacent routers receiving a multicast packet at the same time are likely to also re-transmit at the same time -causing their transmissions to overlap, with as result channel contention and collisions [START_REF] Tseng | The broadcast storm problem in a mobile ad hoc network[END_REF]. Avoiding broadcast storms is one of the reasons why RSS algorithms are used -in SMF as well as in routing protocols such as [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF].

MPR-CDS is vulnerable to being degraded into classical flooding, simply by way of a malicious router (i) declaring itself to have the the highest priority in its neighborhood, and (ii) selecting all its neighbors as MPR, shown in figure 10. Note that this attack works due to the "common set of relays for all routers in the network" philosophy. S-MPR is not vulnerable to this particular attack since the relays selected by the malicious router X are used only by traffic transiting X itself.

VI. CONCLUSION

This paper has described a set of vulnerabilities of relay set selection algorithms as specified by the "Simple Multicast Forwarding" (SMF) protocol for Mobile Ad Hoc Networks. SMF provides a framework, supporting different RSS algorithms and, based on the neighborhood discovery protocols (NHDP) a set of RSS: E-CDS, S-MPR and MPR-CDS.

In addition to vulnerabilities inherited from the feature of wireless medium and its use of NHDP, SMF introduces vulnerabilities by way of those RSS algorithms. Mis-configured routers or malicious attackers can inject inconsistent topology information in the network by link spoofing or identity spoofing, thus result in network disruption or even degrading RSS algorithms to classical flooding. Furthermore, because SMF provides a signaling mechanism (RSSV) to identify various RSS algorithms, the malicious routers have the chance to present conflicting information to disturb the decision of relay set selection.

Figure 1 .

 1 Figure 1. Validity time attack: The malicious router, X, spoofs b and declares a short validity time of the link.

Figure 2 .

 2 Figure 2. Relay set selection considering RSSV: Router a makes the decision based on the RSSV declared by TLVs.

Figure 3 .

 3 Figure 3. Attack on the RSSV to disrupt the relay set selection: The malicious router X spoofs the RSSV of d, e, f, g.

Figure 4 .

 4 Figure 4. E-CDS algorithm disruption by link spoofing. Router a is trying to make relay set selection and malicious router X declares itself with high router priority and spoofs the link to the neighbors of a.

Figure 5 .

 5 Figure 5. Limitation of link spoofing: malicious router X can not obtain the identity of router c directly through NHDP.

Figure 6 .

 6 Figure 6. E-CDS link spoofing attack. Malicious routerX mades router a have to choose itself as relay, which degrades the relay set selection to classical flooding.

Figure 7 .

 7 Figure 7. E-CDS identity spoofing attack. Malicious router X overhears the identity of b at t 0 and sends out a poisoned HELLLO message as b at t 1 .

Figure 8 .

 8 Figure 8. S-MPR link spoofing attack. Malicious router X spoofs links to c, d and e, to mask b from being chosen as relay by a.

X

  Figure 9. S-MPR identity spoofing attack. Router a is running S-MPR algorithm and malicious router X spoofs the identity of router c.

Figure 10 .Figure 11 .

 1011 Figure 10. MPR-CDS

While several RSS are supported in the same network, it is not clearly specified in the current revision of SMF[START_REF] Macker | Simplified Multicast Forwarding[END_REF] whether a router can concurrently support several different RSS at the same time.