Ulrich Herberg
email: ulrich@herberg.name

Thomas Clausen
email: thomas@thomasclausen.org

Robert Cole
email: robert.g.cole@us.army.mil

MANET Network Management and Performance Monitoring for NHDP and OLSRv2

Keywords: OLSRv2, MANET, management, control, MIB, SNMP, performance monitoring

Mobile Ad Hoc NETworks (MANETs) are generally thought of as infrastructureless and largely "un-managed" network deployments, capable of accommodating highly dynamic network topologies. Yet, while the network infrastructure may be "un-managed", monitoring the network performance and setting configuration parameters once deployed, remains important in order to ensure proper "tuning" and maintenance of a MANET. This paper describes a management framework for the MANET routing protocol OLSRv2, and its constituent protocol NHDP. It does so by presenting considerations for "what to monitor and manage" in an OLSRv2 network, and how. The approach developed is based on the Simple Network Management Protocol (SNMP), and thus this paper details the various Management Information Bases (MIBs) for router status monitoring and control -as well as a novel approach to history-based performance monitoring. While SNMP may not be optimally designed for MANETs, it is chosen due to it being the predominant protocol for IP network management -and thus, efforts are made in this paper to "adapt" the management tools within the SNMP framework for reasonable behavior also in a MANET environment.

I. INTRODUCTION

Mobile Ad hoc Network (MANET) routing protocols are commonly assumed to be entirely self-managing: routers, running such a distributed protocol, perceive the topology of the MANET by means of control message exchange. Any change to the topology is reflected in the local routing tables of each router after a bounded convergence time, which allows forwarding of data traffic towards its intended destination. Usually, no human interaction is required, as all variable parameters required by the routing protocol are either negotiated in the control traffic exchange, or are only of local importance to each router (i.e. do not influence interoperability). However, external management and monitoring of a MANET routing protocol may be desirable to optimize parameters of the routing protocol. Such an optimization may lead to a more stable perceived topology and to a lower control traffic overhead, and therefore to a higher delivery success ratio of data packets, a lower end-to-end delay, and less unnecessary bandwidth and energy usage. This paper proposes a management framework to manage and control performance related objects on MANET routers running the Optimized Link State Routing Protocol version 2 (OLSRv2), which is currently in the process of being standardized by the MANET working group of the IETF 1 . 1 The Internet Engineering Taskforce: http://www.ietf.org

A. OLSRv2 Overview

The Optimized Link State Routing Protocol version 2 (OL-SRv2) [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF], [START_REF] Clausen | RFC5497: Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)[END_REF], [START_REF] Clausen | I-D: MANET Neighborhood Discovery Protocol (NHDP)[END_REF], [START_REF] Clausen | I-D: The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] is a successor to the widely deployed OLSR [START_REF] Clausen | RFC3626: Optimized Link State Routing Protocol (OLSR)[END_REF] routing protocol for MANETs. OLSRv2 retains the same basic algorithms as its predecessor, however offers various improvements, e.g. a modular and flexible architecture allowing extensions, such as for security, to be developed as add-ons to the basic protocol. OLSRv2 contains three basic processes: Neighborhood Discovery, MPR Flooding and Link State Advertisements. The basic operation of OLSRv2 is detailed in section I-A1 to I-A3 below, followed by a description of the flexible message format used by OLSRv2, in section I-A4, and a discussion of the configuration and operation of OLSRv2 routers in section I-A5.

1) Neighborhood Discovery (NHDP): The process, whereby each router discovers the routers which are in direct communication range of itself (1-hop neighbors), and detects with which of these it can establish bi-directional communication. Each router sends HELLOs, listing the identifiers of all the routers from which it has recently received a HELLO, as well as the "status" of the link (HEARD, verified bi-directional -called SYM). A router a receiving a HELLO from a neighbor b in which b indicates to have recently received a HELLO from a considers the link a-b to be bi-directional. As b lists identifiers of all its neighbors in its HELLO, a learns the "neighbors of its neighbors" (2-hop neighbors) through this process. HELLOs are sent periodically, however certain events may trigger non-periodic HELLOs. NHDP enables each router interface to apply a hysteresis function which, in addition to the message exchange, may constrain when a link is considered as "usable" or not: for example, a router may elect to not consider, and thus not advertise, a link as SYM or HEARD unless a certain ratio of HELLOs are received, unless the SNR reaches a given threshold etc. Symmetrically, a router may decide to stop advertising a link as SYM or HEARD, subject to similar such constraints.

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

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

4) Flexible Message Format: OLSRv2 employs the format specified in [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF], for all protocol messages, thereby enabling scope-limited message flooding, compact (aggregated) address representation, also of non-contiguous network addresses, and the ability to associate any number of arbitrary attributes to either of control messages or addresses, by way of inclusion of Type-Length-Value objects (TLVs). The TLV structure permits any given message to be parsed correctly by allowing an implementation to "skip over" TLVs not recognized, thus enabling extensions to be developed that embed information into existing OLSRv2 control messages.

5) OLSRv2 Router Configuration: The configuration of an OLSRv2 router consists of the set of prefixes "owned", and thus advertised, by the router, as well as interfaces of that router, participating in the OLSRv2 routing protocol. For each such interface, a set of parameters apply; other than the IP address(es) of each interface, these parameters consist of control message emission intervals, as well as the hysteresis values and link quality estimation. It is important to note that agreement between OLSRv2 routers on the values for any of these is not required for interoperability. Link quality and hysteresis affect only which links a given router permits to become SYM or HEARD. Control message emission intervals and message content validity are encoded in outgoing control messages, by way of TLVs, such that a recipient router can process correctly these regardless of its own configuration.

B. Paper Outline

The remainder of this paper is organized as follows: Section II describes the motivation for the proposed SNMP-based management framework for OLSRv2-routed MANETs. The architecture of this framework is presented in section III. Section IV describes the construction and functioning of NHDP and OLSRv2 MIBs, while section V proposes the related REPORT-MIB -a convenient tool for performance management. This paper is concluded in section VI.

II. PROBLEM STATEMENT

As indicated in section I-A5, OLSRv2 imposes very minimal constraints on valid router configuration parameters, in order for OLSRv2 routers to interoperate. Fundamentally, the only parameter upon which agreement is required is C -a constant, used to fix the scale and granularity of validity and interval time values, as included in protocol control messages. [START_REF] Clausen | RFC5497: Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)[END_REF] proposes a value for this constant. As control messages carry validity time and interval time values, a recipient OL-SRv2 router can behave appropriately, even if it uses vastly different values itself, as long as the recipient and sender use the same value for C. Link admittance, by way of the hysteresis values and link quality estimation, require no agreement; these are used for an individual router to determine a suitable threshold for "considering that a link could be a candidate for being advertised as usable".

Still, external monitoring and management may be desirable in an OLSRv2 network. A network may benefit from having its control message emission tuned according to the network dynamics: in a mostly static network, i.e. a network in which the topology remains stable over long durations, the control message emission frequency could be decreased in order to consume less bandwidth or less energy. Conversely, of course, in a highly dynamic network, the emission frequency could be increased for improved responsiveness. Concerning the hysteresis and link quality estimation, a management application might detect a region of an OLSRv2 network with a high link density -but also a high degree of "flapping": links coming "up" (SYM) only to disappear as LOST shortly thereafter. Detecting such behavior, on a global level and for multiple routers in the same region, could enable appropriately "tuning" the thresholds towards more stable links and, thus, a more stable routing structure in the network.

These are but two examples, and have as common that a more "global view" of the network, than that of a single OLSRv2 router, is required -i.e. entail that a Network Management System is able to inquire as to various performance values of the network, and to set various router parameters. Thus, a first-order task is to identify suitable management data for an OLSRv2 routed MANET, and to describe these by way of MIBs for use by an SNMP Network Management System.

In the following sections, the proposed MIBs for managing OLSRv2 networks and monitoring performance of these networks are described in detail.

III. OLSRV2 MANAGEMENT ARCHITECTURE

The proposed architecture of the OLSRv2 management system is depicted in figure 1. As is standard for SNMP management architectures, a Network Management System interacts with the various components of the device models directly over the network. However, frequent polling for object values in such a system involves a frequent and bandwidth-consuming message exchange. Further, due to highly variable network delays, it is not possible for a management application to determine the time associated with object values obtained via polling. In order to specifically address the issues associated with running SNMP for Performance Management over low bandwidth and high latency networks, typical of MANETs, the proposed Performance Management architecture is based upon a proxy capability, denoted REPORT-MIB [START_REF] Cole | I-D: Definition of Managed Objects for Performance Reporting[END_REF]. This proxy is located in close proximity to the managed devices and offers remote generation of performance reports established via the management application using Remote Monitoring (RMON) style control and reporting. The proxy then polls (locally) for the current values of the relevant objects necessary for the generation of the performance reporting.

IV. NHDP AND OLSRV2 MIBS

This section describes the design of the NHDP-MIB [START_REF] Herberg | I-D: Definition of Managed Objects for the Neighborhood Discovery Protocol[END_REF] and the OLSRv2-MIB [START_REF] Herberg | I-D: Definition of Managed Objects for the Optimized Link State Routing Protocol version 2[END_REF]. As the protocols themselves are designed in a similar fashion, so are their associated MIBs. At the highest level, both the NHDP-MIB and the OLSRv2-MIB are organized into the following groups:

• Configuration Group -switches, tables, objects which are initialized to default settings or set through the management interface defined by the MIB. • State Group -automatically generated object values which define the current operating state of the NHDP or OLSRv2 protocol process in the router. • Performance Group -automatically generated object values which help to assess the performance of the NHDP and OLSRv2 protocol. • Notification Group -objects defining triggers and associated notification messages allowing for asynchronous tracking of pre-defined events on the managed device. • Conformance Group -groupings of the above objects defining various compliance levels to the MIBs.

The Configuration Group for the NHDP-MIB and OLSRv2-MIB includes objects which control message intervals (e.g. for HELLOs), information validity times (e.g. hold times), link quality (e.g. thresholds to determine usefulness of the links), and message jitter. For the OLSRv2-MIB, additional configuration information include objects related to hop limits and routers' willingness measures to act as MPRs. Details on the actions these objects have on the respective protocols are found in [START_REF] Clausen | I-D: MANET Neighborhood Discovery Protocol (NHDP)[END_REF] and [START_REF] Clausen | I-D: The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF].

Regarding the State Group, both protocols are defined in terms of the various databases developed by the protocols in order for their proper function. The state tables in the OLSRv2 and NHDP MIBs are linked through two constructs (or TEXTUAL CONVENTIONS) developed within the MIBs as illustrated in figure 2. Within the NHDP and OLSRv2 protocol definitions, the various Information Bases provide information on discovered address sets, which are associated with discovered interfaces, which belong to discovered (or local) routers. The two TEXTUAL CONVENTIONS are used as indexes into the various State Tables of the NHDP-MIB. Further, as the related State Tables rely on the same indexing, it is relatively straightforward for a network management application to cross-reference data from the two MIBs.

Finally, the MIBs define two levels of Conformance; a Basic Compliance which includes only Configuration Group objects and a Full Compliance which includes Configuration, State, Performance and Notification Group objects. V. PERFORMANCE MANAGEMENT Apart from objects for monitoring and controlling parameters and data sets in NHDP and OLSRv2 (specified in section IV), we propose a number of objects which permit operators to analyze the performance of NHDP and OLSRv2. This section describes the different types of objects and their intent for NHDP and OLSRv2.

A. Object Types

Some of the objects (denoted "base objects") explicitly appear in the NHDP-MIB and OLSRv2-MIB while others are obtainable through a combination of base objects from the MIB and reports available through the REPORT-MIB.

The full list of base objects in the NHDP-MIB and the OLSRv2-MIB is comprised of different counters (e.g. for counting the total number of transmitted HELLO messages, number of changes to the neighbor set and to the 2-hop set, etc.) and other object types.

In order to infer performance problems in an OLSRv2 network, it may not be sufficient to access base objects describing the total number of events, but objects describing the development of events over time. These objects, denoted "derived objects", are not specified in the NHDP-MIB and OLSRv2-MIB, but can be acquired using the REPORT-MIB. The REPORT-MIB allows operators to create reports "offline", possibly on another, more powerful device than the router running NHDP and OLSRv2. Notably, histories (based on timestamps) can be created over all of the performance related base objects.

For example, it is possible to create a histogram of intervals between transmitted HELLO messages, separated by periodic and triggered HELLOs. The histogram would display the distribution of intervals between two consecutive HELLOs of the same type (triggered or periodical) using a given bin size.

Moreover, the NHDP and OLSRv2 MIBs in combination with the REPORT-MIB allow operators to display the changes of the frequency by displaying the changes of histograms over time. The total duration of recorded events is split into a given number of equal bins. Then, a histogram is created for each bin and the "distances" are calculated between each two adjacent histograms in time (e.g. using the Bhattacharyya distance [START_REF] Bhattacharyya | On a measure of divergence between two statistical populations defined by their probability distributions[END_REF]). Note that while visualizing a change in the frequency of events may help the network administrator to understand changing properties of the network, it is out of scope of the MIB, and of this paper to automatically determine whether such a change indicates a performance problem or is part of the natural change of topology of the network.

B. Derived Objects in NHDP and OLSRv2

As described in section V-A, changes of the frequency of certain events may indicate performance issues in the MANET. Notably unstable neighbors or 2-hop neighbors and frequent changes of sets may have a negative influence on the performance of NHDP and OLSRv2, wherefore a number of derived objects have been specified in the MIBs that allow management applications to acquire information related to the stability of NHDP and OLSRv2. The following list describes several derived objects from the MIBs that are relevant for NHDP and OLSRv2 networks:

1) Frequency changes of message scheduling: A change in the message scheduling frequency can appear if, e.g., suddenly many triggered control messages are sent, whereas only few such triggered messages were sent in the past. This can indicate a sudden change in the topology perceived by a router.

2) Frequency changes of Neighbor Set modifications: Changes of frequency of neighbor-set modifications can indicate a performance problem. A neighbor-set modification is defined as a new neighbor that is added, a neighbor that is removed, or a neighbor that changes its symmetry status.

3) Frequency of changes of the online status of a neighbor: If a neighbor changes its "online" status very frequently (i.e. a neighbor tuple for that neighbor is alternatively added and removed again in a very short time), this may indicate a performance problem.

4) Frequency of changes of the online status of a 2-hop neighbor: Similar to the frequency of changes of the online status of a neighbor, an object in the MIB allows to track the frequency of change of the online status of 2-hop neighbors.

5) Frequency of changes of the link over which a neighbor is reachable: If a neighbor changes the interface over which it is reachable frequently, that can cause performance issues: (i) more in-router resources for updating the internal data structures, and (ii) additional control traffic messaging may be required (e.g. when sending triggered HELLO messages).

Such flapping of a neighbor may, for example, stem from inappropriate hysteresis values of the link quality selection of NHDP. Analyzing the frequency of neighbor flaps facilitates to modify the values to stabilize the link formation and removal on the OLSRv2 interfaces.

6) Frequency of changes of the neighbor over which a 2hop neighbor is reachable: Similar to the link-flapping of a neighbor as described above, a two-hop neighbor can flap between several one-hop neighbors, which may induce (i) routing set recalculation on all routers in the MANET, (ii) MPR set recalculations in the 2-hop neighborhood, and (iii) transmission of triggered control messages. The reason is that each time the 2-hop neighbor flaps between neighbors, a new MPR selection may be necessary.

7) Frequency of routing set recalculations and MPR set recalculations: The MIB provides two derived objects for observing routing-set and MPR-set recalculations over time. Both operations are costly in terms of in-router resources (such as memory and CPU time), and too frequent recalculations may reduce the life-time of the MANET when using batterypowered routers. The MIB objects allow an administrator to "tune" parameters of OLSRv2 in order to reduce the number of unnecessary recalculations.

VI. CONCLUSION

The MANET routing protocol OLSRv2 does not require any external interaction once deployed, as routers are able to accommodate frequently changing network topologies in a self-organizing manner, as well as to accommodate OL-SRv2 routers with heterogenous configuration in the same network. However, it is often desirable to monitor the network performance and to "tweak" parameters for improving the performance of an existing deployment of the routing protocol. This paper proposes a management and monitoring architecture for OLSRv2 routers based on SNMP, which allows a Network Management System (i) to acquire the state of the router (i.e. all parameters and information bases of the routing protocol), (ii) to modify parameters during runtime, and (iii) to generate offline performance reports. As for (i) and (ii), two Management Information Bases (MIBs) are proposed for OLSRv2 and for the neighborhood discovery part of OLSRv2, called NHDP. (iii) is derived through the creation of an external proxy service, the REPORT-MIB, typically running on the same machine as the agents (exposing the information defined by the OLSRv2-MIB and NHDP-MIB). The rationale is to avoid frequent polling over the network, leading to a frequent and bandwidth-consuming message exchange.

This paper specifies a number of performance reports that concern the stability of the nearby topology of a router. When some of the router parameters in OLSRv2 and NHDP (such as the link quality related parameters) are unwisely set with respect to the characteristics of a given network, the local topology may "flap" between several possible configurations, thus leading to additional control traffic overhead, in-router calculations and deteriorated performance. Detecting such behavior, on a global level and for multiple routers in the same region, could enable appropriately "tuning" the parameters towards a more stable routing structure in the network.

Fig. 1 .

 1 Fig. 1. The OLSRv2 management model

Fig. 2 .

 2 Fig. 2. The linkage between the OLSRv2 and the NHDP MIBs


Thomas Clausen
email: thomas@thomasclausen.org

Ulrich Herberg
email: ulrich@herberg.name

Multipoint-to-Point and Broadcast in RPL

Recent trends in Wireless Sensor Networks (WSNs) have suggested converging to such being IPv6-based. To this effect, the Internet Engineering Task Force has chartered a Working Group to develop a routing protocol specification, enabling IPv6-based multi-hop Wireless Sensor Networks. This routing protocol, denoted RPL, has been under development for approximately a year, and this paper takes a critical look at the state of advancement hereof: it provides a brief algorithmic description of the protocol, and discusses areas where -in the authors view -further efforts are required in order for the protocol to become a viable candidate for general use in WSNs. Among these areas is the lack of a proper broadcast mechanism. This paper suggests two such broadcast mechanisms, both aiming at (i) exploiting the existing routing state of RPL, while (ii) requiring no additional state maintenance, and studies the performance of RPL and of these suggested mechanisms.

I. INTRODUCTION

The general context for routing in Wireless Sensor Networks (WSNs) is small, cheap devices whose primary function is data acquisition, and for which communications capabilities are a "commodity to their primary function" -a necessary, but in preference unobtrusive, functionality, specifically targeted to the precise goal which the WSN is deployed to satisfy. As an example, a WSN deployed for environmental monitoring might contain a set of temperature sensors, sending "notifications" to a central controller when the temperature exceeds certain thresholds -and occasional "keepalive" messages otherwise, to let the controller know that the sensors are still operational. Traffic from the controller to the individual sensors may be limited to "setting the thresholds" -possibly rarely, such as at system deployment, or even never such as would be the case with factory set thresholds.

A. WSN Traffic Flows

The communications requirements for WSNs are in contrast to "traditional networks", wherein communications devices (network interfaces, switches, routers) have carrying data traffic as their sole raison d'être, and in which devices do not make any a-priori assumptions such as the characteristics of the traffic they will be carrying. WSNs assume an a-priori knowledge of the traffic patterns to optimize for -with sensorto-controller traffic (multipoint-to-point) being predominant, controller-to-sensor traffic (point-to-multipoint) being rare and sensor-to-sensor traffic being somewhat esoteric 1 .

B. WSN Trade-off's

Low-power consumption, minute physical sizes, low pricepoints and ruggedness against the environment are among the industrial or commercial keywords, often associated with wireless sensors -and which entail challenging constraints (in terms of the computational power, permanent and temporary storage and in the characteristics (capacity) of the wireless interfaces) for designing routing algorithms. WSN routing protocols are therefore inherently compromises: trade-offs are made in adapting to the specific constraints under which they are to operate -the first of these is usually "generality". WSN routing protocols generally and narrowly consider only the traffic characteristics of their target environment as "valid", and discard all other traffic characteristics in the name of satisfying operational constraints; two of the most common such constraints brought forward are strict bounds on in-router state and on control traffic. A second trade-off is often in route optimality: stretched (non-optimal) routing paths are an acceptable trade-off for lower control traffic from a routing protocol, with the hypothesis that traffic flows will be such that the impact of such stretched paths will be negligible.

The perceived optimal routing protocol might thus be described as a routing protocol which requires zero in-router state and zero control traffic overhead, while providing nonstretched routing paths. Such a protocol is possible, although may not be desirable. Consider the example in figure 1a. The network connectivity is as indicated by the dotted lines, with the source and destination indicated by Source (node C) and Destination (node I), respectively. A "perceived optimal routing protocol" would be, as illustrated in figure 1b, simply flooding data traffic. Such entails no control traffic overhead and no in-router state, and a packet from C will arrive at I via a path of length 2 (i.e. a routing path stretch of 1). Data transmission between C and I via a path such as the one indicated in figure 1c appears intuitively better. While the routing path stretch is 3 (6 hops), at least routers D and E do not retransmit. An even worse situation is possible, as illustrated in figure 1e: all routers still retransmitting and receiving as many copies of a packet as in flooding -but with a routing path stretch of 4.

A flooding operation, as in figure 1b, would in this case entail 8 transmissions (i.e. (n -1) transmissions, with n being the number of nodes in the network) -just as "bad"2 for battery consumption and media occupation as if the path length had been of 8, as in figure 1e. On the other hand, the routing path in figure 1e did not appear "by magic": a (more or less optimal) routing protocol has provided this path, and in order to do so generated a certain amount of control traffic.

As a measure of success, "routing path stretch" is an inappropriate metric, when used alone. In deployments with heavy unicast traffic, it might be reasonable to trade off more state and more control traffic in order to obtain shorter paths, whereas in scenarios where such unicast traffic is light, a longer path may be a reasonable trade-off in order to reduce state and control traffic. If in a network unicast traffic is both light and rare, simple flooding, and so trading off "route stretching" (or, more appropriately, "total number of transmissions on the wireless medium in order to successfully deliver the data packet at the destination") and state for simpler logic in the router and no control traffic, might be reasonable, as might flooding be reasonable if the majority of traffic is (very light) broadcast.

C. Paper Outline

The remainder of this paper is organized as follows: section II provides an overview of the activities of the IETF ROLL working group, chartered to develop routing protocols for IPv6-based sensor networks, as well as provides a description and critical discussion of the RPL routing protocol, developed within that working group. RPL provides relatively well defined and well understood support for multipointto-point traffic -and is currently developing mechanisms for supporting point-to-multipoint traffic as well. Section III suggests a couple of different mechanisms for providing also support for broadcast traffic in a WSN, by way of using the data structures and topologies already maintained by RPL. Section IV provides a performance study of the multipointto-point performance of RPL, as well as a comparative study of the suggested broadcast mechanisms. Section V concludes this paper.

II. STATE OF THE ART: ROLL AND RPL

ROLL is the abbreviation of an IETF Working Group named "Routing Over Low power and Lossy networks". This working group has as objective to develop a routing protocol for WSNlike networks, based on IP.

The unofficial goal, which this Working Group tries to attain, is to prevent fragmentation in the WSN market by providing an IP-based routing standard and solicit broad industrial support behind that standard. To this end, the Working Group is operating with a very tight schedule and an objective of completing the standardization effort early 2010, satisfying only whatever requirements have been expressed within that time-frame.

The current proposal by the ROLL Working Group is denoted "Routing Protocol for Low Power and Lossy Networks" (RPL), an early draft version hereof exists [START_REF]RPL: Routing Protocol for Low Power and Lossy Networks[END_REF]. The objective of this protocol is to target networks which "comprise up to thousands of nodes", where the majority of the nodes have very constrained resources, where the network to a large degree is "managed" by a (single or few) central "supernodes", and where handling mobility is not an explicit design criteria. Supported traffic patterns include multipoint-to-point, pointto-multipoint and point-to-point traffic. The emphasis among these traffic patterns is to optimize for multipoint-to-point traffic, to reasonably support point-to-multipoint traffic and to provide basic features for point-to-point traffic, in that order.

The basic construct in RPL is the DODAG -a destination oriented DAG, rooted in a "controller", in figure 2. In the converged state, each WSN router has identified a stable set of parents, on a path towards the "root" of the DODAG, as well as a preferred parent. Each router, which is part of a DODAG (i.e. has selected parents) will emit DODAG Information Object (DIO) messages, using link-local multicasting, indicating its respective Rank in the DODAG (i.e. their position -distance according to some metric(s), in the simplest form hop-count -with respect to the root). Upon having received a (number of such) DIO messages, a router will calculate its own rank such that it is greater than the rank of each of its parents, and will itself start emitting DIO messages. Thus, the DODAG formation starts at the root, and spreads gradually to cover the whole network. As a Distance Vector protocol, RPL [START_REF]RPL: Routing Protocol for Low Power and Lossy Networks[END_REF] contains rules restricting the ability for a router to change its rank. Specifically, a router is allowed to assume a smaller rank than previously advertised (i.e. to logically move closer to the root) if it discovers a parent advertising a lower rank (and it must then disregard all previous parents with higher ranks), while the ability for a router to assume a greater rank (i.e. to logically move farther from the root) in case all its former parents disappear, is restricted to avoid count-to-infinity problems. The root can trigger "global recalculation" of the DODAG by way of increasing a sequence number in the DIO messages.

A. RPL Data Traffic Flows

The DODAG so constructed is used for installing routes in the WSN routers: the "preferred parent" can serve as a default route towards the root, or the root can embed in its DIO messages the destination prefixes, also included by DIOs generated by WSN routers through the WSN, to which it can provide connectivity. Thus, RPL provides "upward routes" or "multipoint-to-point routes" from the sensors towards the controller.

"Downward routes" are installed by having the sensors issue Destination Advertisement Object (DAO) messages, which propagate via parents towards the routes, and which describe which prefixes belong to, and can be reached via, which WSN router. Each intermediate WSN router, forwarding a DAO message towards the root, adds its address to a reverse routing stack in the DAO message, thereby providing the source with the ability to do source routing for reaching addresses in the WSN.

Sensor-to-sensor routes are as default supported by having the source sensor transmit via its default route to the root, which will add a source-route to the received data for reaching the destination sensor.

B. RPL Operational Requirements

The minimal set of in-router state, required in a WSN router running RPL is, (i) the identifier of the DODAG root, (ii) the address and rank of the preferred parent, (iii) the configuration parameters shared by the DODAG root (notably, destination prefixes and message emission timers) and (iv) the maximum rank that the WSN router has itself advertised. For redundancy, a WSN router running RPL can maintain information describing additional parents (up to and including all its parents), which may allow rapidly changing its preferred parent (and thus its "next hop") in case the former preferred parent becomes unreachable.

RPL message generation is timer-based, with the root able to configure suitable back-off of message emission intervals using trickle timers [START_REF] Lewis | Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks[END_REF].

C. RPL Discussion

In its basic form, RPL is a fairly simple-to-understand and simple-to-implement distance-vector protocol. The DODAG formation mechanism, using DIO messages, is currently well understood, and despite the specification hereof in [START_REF]RPL: Routing Protocol for Low Power and Lossy Networks[END_REF] remaining somewhat ambiguous, the authors of this paper managed to develop and test an implementation "from scratch" within about a week.

The DODAG formation mechanism is not without potential issues, however. First, parents (and the preferred parent) are selected based on receipt of DIO messages, without verification of the ability for a WSN router to successfully communicate with the parent -i.e. without any bidirectionality check of links. In a wireless environment, unidirectional links are no rare occurrence, and can simply happen as illustrated in figure 3: the gray device, X, illustrates a source of environmental interference, preventing route b from successfully receive transmissions from a. This may, however, not prevent b from transmitting DIOs, received by a and which may contain As b is a "useless" next-hop for a, due to the interference from X, this is a bad choice. RPL suggests using Neighbor Unreachability Detection (NUD) [START_REF] Narten | Neighbor Discovery for IP version 6 (IPv6)[END_REF] to detect and recover from this situation, when it occurs that a tries (and fails) to actually use b for forwarding traffic. NUD is based upon observing if a data packet is making forward progress towards the destination, either by way of indicators from upper-layer protocols (such as TCP), from lower-layer protocols (such as Link Layer ACKs) or -failing these two -by unicast probing. A couple of problems can be noted regarding this approach.

First, absent all WSN routers consistently advertising their reachability through DAO messages, a protocol requiring bidirectional flows between the communicating devices, such as TCP, will be unable to operate. Even if such bi-directional flows are enabled, the source detecting, by way of an upper layer protocol, that no forward progress is possible, is of restricted use: the source can not know if it is its "preferred parent" (next hop) which is unreachable, or if it is a problem further along the path (even outside the WSN). Thus, any corrective action that the source might take (changing preferred parent, moving to a higher rank within the limits allowed, etc.) may be unable to alleviate the problem, and corrective actions may even be counter-productive (poison the sub-dag, for example).

Second, there is a change that the radio range of a unicast (as would be used for data delivery via the next hop towards the root) would differ from the radio range of DIOs, which are sent using link-local multicast 3 .

Third, upon having been notified by NUD that the "next hop" is unreachable, a WSN router must discard the preferred parent and select another preferred parent -hoping that this time, the preferred parent is actually reachable.

Fourth, the selection of parents and preferred parent is based on receipt of DIO messages only, and is based on the rank of the candidate parents. Absent other complementary mechanisms (which are currently not specified as part of [START_REF]RPL: Routing Protocol for Low Power and Lossy Networks[END_REF]), a WSN router may receive, transiently (e.g. due to a fortunate environmental reflection), a DIO from another router, much closer to the root -and as a consequence change its parent set and rank to this new more attractive parent. If no stable link exist, this may cause delivery failures.

The Destination Advertisement mechanism, for providing downward routes "from the root to the sensors", remains in a state of flux. While the basic properties of the Destination Advertisement mechanism, given a stable underlying DODAG, appear easy to understand, it does have several inconveniences: all sensor-to-sensor routes transit the root, possibly causing congestion in the wireless spectrum near the root, as well as draining energy from the intermediate routers on an unnecessarily long path. Several solutions are proposed to alleviate this, including allowing intermediate WSN routers, otherwise only forwarding DAO messages towards the root, to record routing state, and allowing these intermediate WSN routers to act as "shortcuts". Another proposed solution is to use proper sensor-to-sensor routing protocols, derived off e.g. AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF]. Presently, the DAO mechanism is not fully specified and, thus, difficult to implement and test properly.

Finally, the current specification of RPL does not provide support for "broadcasting" of any form. Unicast traffic to and from the root can be enabled, as previously described, however is inefficient in case the root has data to deliver to all (or a sufficiently large subset) of the WSN routers in the network.

III. DATA BROADCASTING IN RPL

In its current form, RPL does not specify any method for performing data broadcasting through a WSN. This section suggests mechanisms for exploiting the DODAG as constructed by RPL in order to undertake better-than-classicflooding WSN-wide broadcasting.

The fundamental hypothesis for these mechanisms is similar to that for sensor-to-sensor communication in RPL: all broadcasts are launched from the root of the DODAG. If a sensor needs to undertake a network-wide broadcast, the assumption is that this broadcast is sent to the root using unicast, from where the root will launch the broadcast operation.

A. Parent Flooding (PF)

As a first intuitive optimization over classic flooding, and observing that a broadcast is always launched "at the root", parent-based flooding proposes to restrict a RPL router to retransmit only the first copy 4 of each broadcast packet, received from a "parent". Logically, the basic performance hereof should be similar to that of classic flooding, considering that the broadcast operation in both cases is launched from the DODAG root.

B. Preferred Parent Flooding (PPF)

As a way of getting rid of the "Duplicate Set" for avoiding multiple retransmissions of the same packet, and thus not incur any additional in-router state requirements in WSN routers, preferred parent flooding utilizes the existing relationship between RPL routers to ensure that no router will forward a broadcast packet more than once: as each RPL router is required to select exactly one Preferred Parent, restricting retransmissions of broadcast packets to only those received from the RPL router's preferred parent.

IV. RPL DODAG PERFORMANCE STUDY

This section presents results of a simulation study of RPL with the Ns2 simulator. Several properties of the DIO mechanism, as well as unicast and multicast data traffic have been analyzed.

A. Simulation Settings

RPL has been implemented in Java. The specific settings of the scenarios studied are detailed in table I. For each datapoint, the values have been averaged over 10 runs.

1) DIO settings:

The implementation reflects a basic version of the RPL protocol: only upward routes, and a single RPL instance with a single DODAG are considered. Since nodes are not mobile in the simulation, the sequence number (and thus the DODAG iteration) will not change during the simulation. At the beginning of the simulation, only the root (which is the node with the ID of 0) starts transmitting DIOs. Nodes other than the root receiving a DIO start sending DIOs exactly two seconds after no more change in their Candidate Neighbor Set has been detected. Each DIO contains the DODAG Configuration suboption.

The simulations have been performed in two variations:

• with periodic DIO transmission: DIOs are sent periodically with an interval of two seconds minus a jitter of maximum 0.5 s (as defined in [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF]) • with a trickle timer: I_min is 2 s and I_doublings is 20. During the simulation, the trickle timer is never reset.

B. Results

This section describes the results of the Ns2 simulation. Figure 4 shows the maximum and average rank of routers in the DODAG, where the number represents the distance of a node to the root in terms of hops (i.e. the maximum rank represents the diameter of the network, the average rank represents the average over all nodes). The maximum and average ranks grow logarithmically with the number of nodes in the network.

Figure 5 depicts the average number of parents of each node in the DODAG. Keeping the density of the network constant with increasing number of nodes, the average number of parents grows logarithmically. Figure 9 depicts the delivery ratio of packets that have arrived at the root. It can be seen that it is constantly very high, only few packets are lost due to collisions on lower layers. 2) Multicast Data traffic: Figure 12 depicts the delivery ratio of packets that have been broadcasted from the root. Parent Flooding (PF) has a higher delivery ratio than Preferred Parent Flooding (PPF), due to the redundancy of transmissions: when a node receives the same broadcast packet from several of its parents, chances are higher that at least one of the packets will reach the node, while if the one transmission from the preferred parent in PPF is lost due to a collision, the node will not forward the other incoming packets from its (nonpreferred) parents. However, PF requires more state than PPF for updating the information about received packets to remove duplicate packets.

Figure 13 illustrates the total retransmission overhead in bytes of broadcasted messages originating at the root, counting each retransmission at every node in the DODAG. The overhead is much lower for PPF than for PF.

V. CONCLUSION

This paper has presented a critical review of RPL -the currently proposed routing protocol for IPv6-based Wireless Sensor Networks (WSNs), as developed within the Internet Engineering Task Force. A distance vector protocol constructing routing paths from sensors to a central "controller", RPLs basic mechanism is one of DAG formation, with that DAG The review reveals areas where, in the authors opinion, further work is required -in particular with respect to tracking of uni-directional links, to point-to-multipoint routes (controllerto-sensor routes) and data broadcasting in a WSN. The paper then suggests a simple zero-in-router-state broadcast protocol, utilizing the DAGs already constructed by RPL.

The paper concludes by a performance study of the "multipoint-to-point" (sensor-to-controller) routing performance RPL, as well as of the suggested data broadcasting mechanisms.

Figure 1 .

 1 Figure 1. "Route Stretching" vs "number of transmissions"

Figure 2 .

 2 Figure 2. RPL Basic Construct: DODAGs

Figure 3 .

 3 Figure 3. Unidirectional link due to radio interferrence

Figure 4 .

 4 Figure 4. Maximum and average rank of routers in the DODAG

Figure 5 .Figure 6

 56 Figure 5. Average number of parents per node in a DODAG

Figure 6 .

 6 Figure 6. Convergence time

Figure 8 Figure 7 . 1 )

 871 Figure8depicts the collision ratio of the DIO messages. Since the RPL implementation using the trickle timer sends

Figure 9 .

 9 Figure 9. Delivery ratio Figure 10 illustrates the average path length in number of hops that a data traffic traverses before reaching the root. As expected, it grows logarithmically with the number of nodes, and is very similar to the average rank as depicted in figure 4.

  Figure 10. Path length

Figure 13 .

 13 Figure 12. Delivery ratio

Note that while this may be commonly assumed, this is not a universal distribution of traffic patterns in WSNs -there are scenarios in which sensornode to sensor-node traffic is assumed a more common occurrence, such as[START_REF] Martocci | Building Automation Routing Requirements in Low Power and Lossy Networks[END_REF].

Actually, even worse: in order to prevent "looping" packets, state would have to be maintained in each sensor node, ensuring that each such packet would be retransmitted no more than once.

Such is the case for some implementations of IEEE 802.11b. IEEE 802.11b is, of course, not suggested as a viable radio interface for WSNs, but serves to illustrate that such asymmetric designs exist.

Necessitating the maintenance of a Duplicate Set for detecting which packets have already been retransmitted.


Thomas Clausen
email: thomas@thomasclausen.org

Ulrich Herberg
email: ulrich@herberg.name

Router and Link Admittance Control in the Optimized Link State Routing Protocol version 2 (OLSRv2)

Keywords: OLSRv2, MANET, security, router, link admittance control, digital signatures

This paper presents security mechanisms for router and link admittance control in OLSRv2. Digitally signing OL-SRv2 control messages allows recipient routers to -individually -choose to admit or exclude the originating router for when populating link-state databases, calculating MPR sets etc. By additionally embedding signatures for each advertised link, recipient routers can also control admittance of each advertised link in the message, rendering an OLSRv2 network resilient to both identity-spoofing and link-spoofing attacks.

The flip-side of the coin when using such a link-admittance mechanism is, that the number of signatures to include in each OLSRv2 control message is a function of the number of links advertised. For HELLO messages, this is essentially the number of neighbor routers, for TC messages, this is the number of MPR Selectors of the originator of the message. Also, upon receipt of a control message, these signatures are to be verified. This paper studies the impact of adding a link-admittance control mechanism to OLSRv2, both in terms of additional control-traffic overhead and additional in-router processing resources, using several cryptographic algorithms, such as RSA and Elliptic Curve Cryptography for very short signatures.

I. INTRODUCTION

Network integrity in routed networks is largely preserved by physically controlling access to the communications channel between routers: know thy peers, trust thy peers -and be able to disconnect thy peers if they are not worthy of the trust, e.g. if the topology they present does not match expectations, i.e., routing integrity is protected by admitting only trusted peers, assuming that these, once admitted, are well behaving.

In a MANET (Mobile Ad hoc NETwork), often operated over wireless interfaces, this is less obvious: physical access to the media between routers is not delimited by a cable, but is available to anyone within transmission range; the network topology is time-varying, either due to router mobility or due to time-varying characteristics of the channel -consequently, determining that a peer does not present an "expected topology" and subsequently "disconnecting" it is difficult. As such, MANETs do not introduce particularly new security issues for routing protocols, but rather render existing security issues easier to exploit and, therefore, require re-examining countermeasures for routing protocol resilience.

A. OLSRv2 Overview

The Optimized Link State Routing Protocol version 2 (OLSRv2) [START_REF] Clausen | RFC5148: Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF], [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF], [START_REF] Clausen | RFC5497: Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)[END_REF], [START_REF] Clausen | I-D: MANET Neighborhood Discovery Protocol (NHDP)[END_REF], [START_REF] Clausen | I-D: The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] is a successor to the widely deployed OLSR [START_REF] Clausen | RFC3626: Optimized Link State Routing Protocol (OLSR)[END_REF] routing protocol for MANETs. OLSRv2 retains the same basic algorithms as its predecessor, however offers various improvements, e.g. a modular and flexible architecture allowing extensions, such as for security, to be developed as add-ons to the basic protocol. OLSRv2 contains three basic processes: Neighborhood Discovery, MPR Flooding and Link State Advertisements. The basic operation of OLSRv2 is illustrated in figure 1. Ignoring the gray router X, the different elements of OLSRv2, the processes for Neighborhood Discovery, MPR Flooding, and Link State Advertisement, are detailed below. This is followed by a description of the flexible message format used by OLSRv2, as well as the inherent extensibility specifically enabling extensions such as those developed in this paper.

1) Neighborhood Discovery: The process, whereby each router discovers the routers which are in direct communication range of itself (1-hop neighbors), and detects with which of these it can establish bi-directional communication. Each router sends HELLOs, listing the identifiers of all the routers from which it has recently received a HELLO, as well as the "status" of the link (HEARD, verified bi-directional -called SYM). A router a receiving a HELLO from a neighbor b in which b indicates to have recently received a HELLO from a considers the link a-b to be bi-directional. As b lists identifiers of all its neighbors in its HELLO, a learns the "neighbors of its neighbors" (2-hop neighbors) through this process. HELLOs are sent periodically, however certain events may trigger nonperiodic HELLOs.

2) MPR Flooding: The process whereby each router is able to, efficiently, conduct network-wide broadcasts. Each router designates, from among its bi-directional neighbors, a subset (MPR set) such that a message transmitted by the router and relayed by the MPR set is received by all its 2-hop neighbors (i.e., the MPR set "covers" all 2-hop neighbors). MPR selection is encoded in outgoing HELLOs. The set of routers having selected a given router as MPR is the MPRselector-set of that router. A study of the MPR flooding algorithm can be found in [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF].

3) Link State Advertisement: The process whereby routers are determining which link state information to advertise through the network. Each router must advertise links between itself and its MPR-selector-set, in order to allow all routers to calculate shortest paths. Such link state advertisements, carried in TC messages, are broadcast through the network using the MPR Flooding process. As a router selects MPRs only from among bi-directional neighbors, links advertised in TCs are also bi-directional. TC messages are sent periodically, however certain events may trigger non-periodic TCs. In order to be able to discriminate between fresh and stale information, Link State Advertisements, emitted by a given router, include a sequence number incremented each time that router changes the set of links advertised.

4) Flexible Message Format: OLSRv2 employs the format specified in [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF], for all protocol messages. This format enables scope-limited message flooding by way of <hop-limit> and <hop-count> message header fields, modified each time a message is forwarded. The message body format enables compact (aggregated) address representation, also of non-contiguous network addresses, by way of address blocks, and has the ability to associate any number of arbitrary attributes to each such address, by way of inclusion of Type-Length-Value objects (TLVs), referencing the address to which they correspond. Such TLVs are denoted "Address Block TLVs"1 . An example of an attribute that may be associated with an address in OLSRv2, is Link Status = SYM in HELLOs, to indicate that a link between the originator of the message and the indicated address has been verified to be bi-directional. Another example of such an attribute, associated by an OLSRv2 router to specific addresses in HELLO messages is an MPR TLV, indicating a router's MPR selection.

Furthermore, the message body can contain any number of arbitrary attributes not specifically associated to any address, this also by way of inclusion of TLVs. Such TLVs are denoted "Message TLVs". An example of an attribute that may be included in a message in OLSRv2, and which is not associated with any address, is the sequence number included in TCs.

The TLV structure permits any given message to be parsed correctly by allowing an implementation to "skip over" TLVs not recognized, thus enabling extensions to be developed that embed information into existing OLSRv2 control messages.

5) Inherent Protocol Extensibility: [START_REF] Clausen | I-D: MANET Neighborhood Discovery Protocol (NHDP)[END_REF], [START_REF] Clausen | I-D: The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] are conceived to enable protocol extensions to be developed for OLSRv2. This is, in addition to the message format described above, accomplished by allowing that subsequent to the usual control message (HELLO and TC) generation, outgoing messages can be handed off to a protocol extension for further processing. Amongst other things, such an extension can insert addresses, Address Block TLVs and Message TLVs. Moreover, upon receipt of a control message, and prior to the usual processing according to that message type, incoming messages can be processed by a protocol extension -including processing of information from that message (extension specific TLVs, for example), as well as allowing a protocol extension to identify the received message as malformed, and thus prohibit processing of that message by OLSRv2.

B. OLSRv2 Vulnerability Taxonomy

As link state protocol, OLSRv2 assumes that (i) each router can acquire and maintain a topology map, accurately reflecting the effective network topology; and (ii) that the network converges, i.e. that all routers in the network will have sufficiently identical topology maps. Network connectivity can be disrupted by causing either of these assumptions to not hold, specifically (a) routers may be prevented from acquiring a topology map of the network; (b) routers may acquire a topology map, which does not reflect the effective network topology; and (c) two or more routers may acquire inconsistent topology maps.

In OLSRv2, this translates into that: (i) the links designated by HELLOs to be advertised in TCs reflect actual links in the network; (ii) that the TCs advertise these actual links; and (iii) that TCs are correctly relayed, i.e. that the MPR flooding process operates correctly. [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] provides a detailed security analysis of OLSRv2, observing how, and with which consequences, a disruptive attack might be conducted against an OLSRv2 network. A common, and not surprising, observation from [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] is, that identity spoofing and link spoofing, i.e., that a router in its control traffic either pretends to have the identity of another router or pretends to have (non-existing) links to another router, are major vectors for disruptive attacks on an OLSRv2 network.

C. Problem Statement

Returning to figure 1, router a selects b as MPR in order to cover c. Router b, therefore, advertises the link b-a in TCs, throughout the network. If a malicious router, X (gray circle) is a neighbor of a and spoofs the identity of c (more generally, of all neighbors of b), then a will not select b as MPR. This has as consequences that (i) b will not advertise b-a; and (ii) the MPR flooding process is disrupted: TCs transiting through a will not be relayed by b to reach the right-hand side of the network. This is an illustration of the effect of identity spoofing.

A possible countermeasure to such an identity spoofing attack is for a protocol extension to admit only control messages originating from routers, whose identity can be verified to not be spoofed, for processing by OLSRv2 -router admittance control.

Router admittance control assumes a transitive trust relationship between routers: d receiving a TC from b declaring a link b-a, and which d (by way of a router admittance control protocol extension) is able to verify was indeed sent from b, will have to trust that b is correctly behaving (i.e., has not been compromised) and that b has properly verified the identity of a (the "other end of the link", advertised in the TCs received from b) as well as the properties associated herewith. Router admittance control does not permit the recipient of a TC to verify that the content of the TC is valid.

Still in figure 1, should b be malicious or compromised, but still in possession of credentials to generate TCs which pass verification by a router admittance protocol extension, it might in its TCs also advertise a fictitious link b-d. c would receive this and, thus, transit traffic destined for d via b, rather than through "to the right" to where d is located. This is an illustration of the effect of link spoofing.

A possible countermeasure to such a link spoofing attack is for a protocol extension to admit only links, where it can be verified by the recipient that both ends have "signed off" for the existence of that link -link admittance control.

D. Paper Outline

The remainder of this paper is organized as follows: Section II describes a basic router admittance control mechanism for OLSRv2. Section III introduces a link admittance control mechanism, allowing per-link verification without assuming transitive trust, also for OLSRv2. Section IV provides a specification of the protocol extension, notably the TLVs and their content, necessary for enabling router and link admittance control, and how the proposed extensions integrate into the OLSRv2 protocol architecture. As the protocol extensions proposed in this paper rely on cryptographic signatures, section V briefly discusses the applicability of shared and public key cryptographic systems for this purpose, and section VI discusses the use of timestamps in the protocol extensions proposed. Section VII studies the performance of the proposed security mechanisms, with particular emphasis on (i) control traffic overhead incurred, and (ii) additional in-router resource requirements, as a consequence of these security mechanisms. This paper is concluded in section VIII.

II. ROUTER ADMITTANCE CONTROL

Router admittance control in OLSRv2 is enabled in [START_REF] Clausen | I-D: MANET Neighborhood Discovery Protocol (NHDP)[END_REF], [START_REF] Clausen | I-D: The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] by allowing a protocol extension to, upon receipt of a control message and prior to the usual processing hereof, determine if the message originates from a router using a "spoofed identity". Thus, each router must be able to include sufficient credentials in each control message to allow a recipient to make such a determination.

To this end, this paper assumes that (i) each router identity (IP address) is also associated with a cryptographic key, (ii) this key is used for generating and including a cryptographic signature in each outgoing control message, and (iii) that this signature is verified by a receiving router, prior to the control message being processed by OLSRv2. The cryptographic signature is carried in control messages by way of a TLV, specified in section IV.

More precisely, for router admittance control, each router will, for each outgoing control message:

• calculate sign(ownID, TimeStamp, <msg>);

where <msg> is the control message, including all headers, but with the mutable fields <hop-limit> and <hop-count> (if present) set to zero, and TimeStamp is current at the time of signature generation; • add this signature, as well as TimeStamp, by way of a Signature-TLV and Timestamp-TLV (section IV), to the control message. Each router will, for each incoming control message and prior to it being delivered to OLSRv2 for processing:

• verify the included Signature-TLV;

• consider the message as malformed (and, thus, prohibit its processing by OLSRv2) if either of:

no Signature-TLV is present in the received message;

the verification fails, i.e. the signature does not correspond to the message originator and content; if clocks are synchronized and Replay Attacks are of concern, the included TimeStamp is "too old" (refer also to section VI).

• otherwise, consider the message as correctly formed according to the Router Admittance Control protocol extension. If a message is so considered "correctly formed", it implies that the originator of the message either is not "spoofing" its identity -or, that the originator has managed to acquire the credentials, necessary for generating a signature corresponding to a spoofed identity.

III. FINE-GRAINED SECURITY: LINK ADMITTANCE CONTROL

In order to allow a router receiving a control message to verify "both sides" of the link, (i) both sides must be able to establish that the link exists, and (ii) information "signing off" for this must be included in the control message. The TLV format in [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] enables that that information can be associated with each address, advertised in a control message.

For each address (the other end of the link) advertised in a control message, the originating router includes a signature embedding its own address, the address of the peer, the timestamp of emission, and any additional attributes that the originating router has associated with that link, by way of TLV inclusion, e.g., if the link is HEARD or SYM (for HELLO messages) or if an address is routable (for TC messages). The signature so included is, thus: sign(t, ownID, peerID, own-attribute-list). The router also signs the message as described in section II, thus notably including its own timestamp in the message as well. Additionally, the router includes the most recent signature previously received for this link from the peer, the corresponding timestamp received from the peer, as well as the attribute list for this link received from the peer (i.e., the information which the peer used for calculating the signature).

A router receiving such a message can, then, verify if (i) the two routers agree on the attributes associated with the link, and (ii) do so at approximately the same time 2 .

Consider the example depicted in figure 2. At t 0 , router a sends a HELLO; it has no neighbors and thus the HELLO is empty. When b receives this HELLO, it will -as usual in OLSRv2 -advertise a as HEARD in its next HELLO, at t 1 and associate its signature sign(t 1 , b, a, HEARD) to this advertisement, by way of a TLV. Any router receiving this HELLO can verify only that b claims information about the link a-b.

At t 2 , router a will proceed in a similar fashion, advertising b as SYM, associating its own signature sign(t 2 , a, b, SYM). The router will also include the information shown inside the "box": the last received signature for this link, received from b, sign(t 1 , b, a, HEARD), and the information necessary for a third-party to be able to verify the signature of b: the timestamp t 1 , and the attribute list corresponding to this link as received from b (HEARD). Any router receiving this HELLO can by verifying the signatures observe that a and b at this point have claimed different information about a (a describes the link as SYM, b describes it as HEARD).

At t 3 , router b may consider advertising a as SYM, and associating its own signature sign(t 3 , b, a, SYM). The router will also include the information shown inside the "box": the last received signature for this link, received from a, sign(t 2 , a, b, SYM) and the information necessary for a third-party to be able to verify the signature of a: the timestamp t 2 , and the attribute list corresponding to this link as received from a (SYM). Any router receiving this HELLO can by verifying the signatures observe that at t 2 and t 3 , respectively, both a and b have claimed claimed that the link a-b is symmetric. If t 2 and t 3 are sufficiently close, a recipient may conclude that a symmetric link exists between a-b, and that both a and b have "signed off" herefore. The link can therefore be considered as "trusted", and thus reflected in the link-and neighbor-sets of OLSRv2.

The main impact, in terms of protocol operation, is that if link admittance control is used when admitting routers to the 2-hop set, then one further HELLO message exchange is required in order for a router to be able to detect 2-hop links as "signed off" as symmetric by both ends.

IV. PROTOCOL EXTENSION SPECIFICATION: ROUTER AND LINK ADMITTANCE CONTROL

In the following, the router and link admittance control protocol extension, proposed by this paper, is specified, in particular the TLV types introduced, as well as the interaction between this protocol extension and OLSRv2.

A. TLV Specification

Three TLVs are required: a timestamp TLV, a signature TLV and an attributes TLV. The timestamp TLV and the signature TLV, both, can be used as Message TLVs (i.e. included in the header of a control message) and as Address Block TLVs (i.e. associated with one or more addresses in the message body). This section specifies the content of <value> in the three proposed TLVs, for use in the format described in [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF].

1) Timestamp TLV:

<timestamp> := <time-value> where: <time-value> contains the timestamp. A timestamp is essentially "freshness information", and may e.g. correspond to a UNIX-timestamp, GPS timestamp or a simple sequence number. For the performance study of section VII, the timestamp is a four-byte long integer, counting the seconds from the start of the simulation.

2) Signature TLV: <sign-tlv> := <hash-fkt><sign_algo><sign> where: <hash-fkt> and <sign_algo> are 1-octet long fields identifying the choice of hash function and signature algorithm, respectively, and <sign> contains the digital signature.

3) Attributes TLV:

<attributes> := {<attribute-value>} *
Recalling that for each address included in a message, two signatures are ultimately included. If the message is originated by router a and contains an address of a peer b, then for the link a-b a signature generated by both a and b is included. In order for a third-party c to be able to verify also the signature from the peer b, the exact information over which the peer b calculated this signature needs to be available to c. In figure 2 at t 2 , for example, this information is included in the box: the timestamp (t 1 ) and the attribute list (HEARD). This information has been received by a by way of TLVs, and the signature (sign(t 1 , b, a, HEARD)) can be verified by a using the identities of both routers a and b as well as the timestamp (t 1 ) from the timestamp TLV and the attribute (HEARD) from the attributes TLV.

B. OLSRv2 Interaction

Due to the flexible nature of the specification of OLSRv2, the router and link admittance control extension, presented in this paper, can be designed as an independent module. This module is invoked when an incoming control message has been successfully parsed, and before further processing by OLSRv2, as well as whenever an outgoing message is about to be sent. This simple architecture allows combination of other OLSRv2 extensions with this router and link admittance control extension, without encumbering such other extensions. The flow of incoming and outgoing messages between the different modules is depicted in figure 3. V. CRYPTOGRAPHIC KEYS Using cryptographic signatures in control messages allows the recipient of a message to (i) verify the integrity upon receipt, (ii) verify if the originator is to be admitted to the network, and (iii) verify the identity of originator of the control message. For (i) and (ii), a "pre-shared secret", such as a secret passphrase or a symmetric key, suffices: only routers possessing the secret are able to correctly sign control messages and addresses within, which allows exclusion of "all but pre-approved routers". However, (iii) requires asymmetric keys for allowing per-principal authentication. As the link admittance control extension, presented in this paper, relies on bi-directional verification of links between routers, perprincipal authentication is a requirement.

For assuring the reliability of the admittance control system, it is paramount that the cryptographic keys are only accessible by the router that they are allocated to. Furthermore, it has to be ensured that the keys cannot be derived from any information exchanged between the routers, i.e., that the cryptographic algorithm is not vulnerable to attacks, other than brute-force with sufficient efforts for such a brute-force attack being appropriate for deployment requirements.

VI. TIMESTAMPS

The router and link admittance control extension can provide protection against identity-spoofing and link-spoofing of unadmitted routers (i.e. routers not able to correctly sign messages), but malicious routers can still record and replay messages (see [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] for details on such "replay attacks"). These replay attacks can be partly avoided by introducing "freshness" information, such as timestamps or nonces, in messages. A message which is replayed some time after the recording, can be detected as being "old" (at least, when the clocks of the routers are roughly synchronized).

In the protocol extension proposed in this paper, both whole messages and individual links are candidates for "being replayed". Consider a router X which has been compromised (i.e., the attacker has access to appropriate credentials to generate correctly signed messages). If no timestamps were included in the per-link signatures, X could record such perlink signatures and include them later in its messages, spoofing links to non-existing neighbors.

VII. PERFORMANCE STUDY

This section presents a performance study, by way of simulations with NS2 [9], of the link admittance control mechanism, in comparison to a simple router admittance control mechanism, both in terms of message overhead and CPU time. Simulations have been conducted with JOLSRv2 [10] using relatively standard scenario parameters (1km 2 square, 0-300m segments of random walk at 2-8 m s , and 0-5s pause-time). The number of routers was varied between 10 and 50, and each value has been averaged over 20 simulation runs. The performance parameters studied are the extra control traffic overhead and the in-router message generation/processing overhead incurred by the mechanisms presented in this paper. JOLSRv2 uses AgentJ [START_REF] Herberg | Development Framework for Supporting Java NS2 Routing Protocols[END_REF] for interfacing with NS2. AgentJ/NS2 permits single thread execution, without preemption, allowing instrumenting the signature generation and verification code to record the time spent on each such operation 3 . For the simulations, an Intel Core 2 CPU with 2.1 GHz and 4 GB of RAM was used.

A. Overhead of Link Admittance Control

Using router admittance control, described in section II, only a single signature is included per control message. Using link admittance control, described in section III, up to two signatures are included per advertised address. Thus, the message size will grow with the density of the network, as depicted in figure 5 using RSA-1024 [START_REF] Kaliski | PKCS 1: RSA Cryptography Specifications Version 2.0[END_REF], DSA-1024 [START_REF]Digital Signature Standard[END_REF], ECDSA-160 [START_REF] Johnson | The Elliptic Curve Digital Signature Algorithm (ECDSA)[END_REF], and HMAC-80 [START_REF] Krawczyk | HMAC: Keyed-Hashing for Message Authentication[END_REF] 4 , with the numbers being the key length in bits for each respective algorithm. For RSA, DSA and HMAC, the implementations directly provided by Java 6 have been used, whereas ECDSA is a custom implementation. In the following, only ECDSA and RSA are considered for the comparison, exploring their differences in terms of (i) message overhead and (ii) CPU time for processing and generating signatures.

Figure 4 depicts the cumulative overhead in the network, due to inclusion of message signatures and address signatures. In this figure, as well as in the following, the overhead only considers the size of the signatures, and not the content of the HELLO or TC message themselves. Thus, for an unsigned message, the overhead would be 0. For the router admittance control mechanism (denoted "RA"), the per-message overhead is constant, and the cumulative overhead is a function of the number of control messages -itself a function of simulation time and number of routers. Note that the length of the control message does not influence the length of the signature, since the signature is always calculated over an SHA1 hash of the message. With link admittance control (denoted "LA"), the total overhead grows polynomial with increased number of routers and increased density in the network, as up to two signatures are added per advertised neighbor in a control message. As RSA-1024 signatures are longer than the corresponding ECDSA-160 signatures, the total overhead with RSA grows considerably faster.

Using smaller signatures (e.g., as provided by ECDSA) is, in terms of message size, particularly beneficial for link admittance control. Longer signatures (such as RSA) leads to (i) higher bandwidth consumption for control traffic, and therefore (ii) higher energy consumption 5 , as well as (iii) the possibility that the IP packet gets fragmented when its size is greater than the MTU of the underlying link layer. This can be well observed in figure 5; assuming an MTU of 1500 bytes (e.g. for Ethernet), messages signed with RSA would be fragmented (with the associated risk of any one fragment being lost causing the whole message to be lost) with about five neighbors, whereas ECDSA would allow roughly three times more neighbors.

B. In-Router Resource Requirements

This section analyses the CPU time for creating and parsing signatures in control messages in OLSRv2 using the router admittance and the link admittance control mechanisms respectively.

Figure 6 depicts the cumulative time each router spends, over the duration of 100 seconds, on generating signatures in JOLSRv2, with router admittance (denoted "RA") and link admittance (denoted "LA"), both. For router admittance control, the time each router spends in total on generating signatures is constant, since every router periodically creates HELLO and TC messages, independently of the size of the network. As expected, using link admittance control significantly increases the amount of CPU time required for generating control messages, since the number of signatures per message to be generated increases with the density of the network. ECDSA and RSA have similar time consumption for generating signatures. 5 [START_REF] Pottie | Wireless integrated network sensors[END_REF] states "The energy cost of transmitting 1Kb a distance of 100 meters is approximately 3 joules. By contrast, a general-purpose processor with 100MIPS/W power could efficiency execute 3 million instructions for the same amount of energy", indicating that shorter (but more computationally intensive) signatures for certain applications, such as energy constrained devices, may be preferential. The corresponding cumulative processing time in each router is depicted in figure 7. Each router generates HELLOs, which must be processed, and so its signatures verified, by its neighbors. Thus, increasing the network density increases the number of HELLOs that a given router receives and, therefore, the number of signatures to verify. Depending on the network topology and MPR selection, additional routers may also incur additional TCs, whose processing and signature verification is to be conducted by each other router in the network. Link admittance control significantly increases the amount of CPU time spent for verifying signatures for control messages. RSA signatures are very fast to verify, while verifying ECDSA signatures consumes a considerable amount of CPU time. Since every signature has to be verified before it can be forwarded, the total amount of time spent in each router for verifying signatures is considerably higher than for generating messages. VIII. CONCLUSION When OLSRv2 routers use digitally signed control messages for admittance control, these routers can verify the identity of control message originators and the integrity of the messages. However, a router has to trust the message originator that the advertised links in the HELLO or TC message are valid. This paper specifies a router and link admittance control protocol extension to OLSRv2 , which allows a router to verify each advertised link from incoming control messages, by signing "both ends of the link". The router and link admittance control protocol extension is generic, in that it is not tied to any specific cryptographic system. Indeed, the mechanism operates as long as the choice of cryptographic system allows for perprincipal authentication and signature generation.

A performance study of this extension is presented, quantifying the impact in terms of increased control traffic overhead and increased per-message generation and processing time, exemplified by using two relatively common cryptographic systems: RSA, for its performance in verification of signatures, and ECDSA for its short signature lengths for the same "strength" of signatures. It is argued that using shorter signatures may be advantageous when using such a router and link admittance security mechanism, since the additional overhead grows linear with the density of the network. Using longer signatures leads to (i) higher bandwidth consumption for control traffic, and therefore (ii) higher energy consumption, as well as (iii) the possibility that the IP packet gets fragmented when its size is greater than the MTU of the underlying link layer.

It is observed, however, that regardless of the choice of cryptographic system, this router and link admittance control protocol extension is no "free lunch": other than the size increase in control messages, the time required for signature generation and verification is -unsurprisingly -not negligible.

Fig. 1 .

 1 Fig. 1. Basic OLSRv2 operation.

Fig. 2 .

 2 Fig.2. Example of link admittance control in the Neighborhood Discovery process of OLSRv2: attributes listed in "boxes" are those received from the "peer" in a previous HELLO message.

Fig. 3 .

 3 Fig. 3. Message flow between NHDP, OLSRv2 and the security extension.

Fig. 4 .

 4 Fig. 4. Total overhead incurring due to signature inclusion.

Fig. 5 .

 5 Fig. 5. Link admittance control: Signature overhead per control message with increasing number of advertised neighbors.

Fig. 6 .

 6 Fig. 6. Cumulative time per router spent on generating message signatures.

Fig. 7 .

 7 Fig. 7. Cumulative time per router spent on verifying message signatures.

In order to avoid repetition of attributes, an Address Block TLV can reference a single, a range or all addresses in a given address block, see[START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] for details.

Timestamps are included to counter replay attacks. Using timestamps requires roughly synchronized system clocks. A similar mechanism using nonces could be possible, when clocks are not assumed to be synchronized.

For completeness: AgentJ rewrites System.currentTimeMillis() such as to return the "simulator time", whereas System.nanoTime() is not rewritten and therefore returns the "wall clock time".

Note that HMAC, strictly speaking, is not a signature algorithm, but a Message Authentication Code, see section V.

ACKNOWLEDGEMENTS

The authors would like to thank Jérôme Milan (LIX, Ecole Polytechnique) for providing the ECDSA implementation and for his assistance with its integration into JOLSRv2.