Ulrich Herberg
email: ulrich@herberg.name

Thomas Clausen
email: thomas@thomasclausen.org

Jerome Milan
email: jerome.milan@lix.polytechnique.fr

Digital Signatures for Admittance Control in the Optimized Link State Routing Protocol version 2

Public community Mobile Ad Hoc NETworks (MANETs), such as the "Funkfeuer" or "Freifunk" networks, scale up to several hundreds of routers, connecting users with each other, and with the Internet. As MANETs are typically operated over wireless channels (e.g. WiFi), access to these networks is granted to anyone in the radio range of another router in the MANET, and running the same MANET routing protocol. In order to protect the stability of the networks from malicious intruders, it is important to ensure that only trusted peers are admitted to participate in the control message exchange, and to provide means for logically "disconnecting" a non-trustworthy peer.

This paper presents the concept of admittance control for the Optimized Link State Routing Protocol version 2 (OLSRv2), and suggests a security extension based on digital signatures. Due to the flexible message format of OLSRv2, this extension keeps compatibility with the core OLSRv2 specification. Several standard digital signature algorithms (RSA, DSA, ECDSA), as well as HMAC, are compared in terms of message overhead and CPU time for generating and processing 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. Routing integrity is thus 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 [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 the successor of the widely used OLSR [START_REF] Clausen | RFC3626: Optimized Link State Routing Protocol (OLSR)[END_REF] routing protocol for MANETs. A proactive link state protocol, OLSRv2 retains the same basic algorithms as its predecessor, Neighbor Discovery and Link State Advertisement manifest themselves through HELLO and TC messages, generated periodically. HELLOs and TCs, both, advertise links between the router generating the message and (a subset of) its neighbors -possibly also indicating additional information pertaining to each such link. HELLOs are used for detecting bi-directionality of links, and list all neighbors, each associated with a status flag (HEARD, SYM). HELLOs are exchanged only with direct neighbors. TCs are used for sharing link-state information network-wide, and list only neighbors with which a symmetric link has been identified (by the Neighborhood Discovery process). TCs include a sequence number, used to allow recipients to exclude outdated information, incremented when the set of advertised links changes. TCs are delivered through the network using MPR Flooding.

MPR flooding is a process for each router to efficiently perform network-wide broadcasts. Each router designates, a subset (MPR set) from among the neighbors with which a bi-directional link has been identified, such that a message transmitted by the router and relayed by the MPR set is received by all its 2-hop neighbors. MPR selection is signaled by a router by associating a flag (MPR) to the selected neighbors in outgoing HELLOs. The set of routers having selected a given router as MPR is the MPR-selector-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].

MPR selection further serves to allow designation of which links are to be included in TC messages: a router must (at least) include links to all its MPR-selector-set. Thus, the schematic operation of OLSRv2 is illustrated in figure 1.

B. OLSRv2 Security Problem Statement

Correct operation of OLSRv2 assumes that each router is able to acquire a consistent topology map, reflecting the effective network topology. In OLSRv2, this implies 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.

In figure 1, router a selects b as MPR in order to cover c. b, therefore, advertises the link b-a in TCs. If a, in its HELLOs, "pretends to be" (spoofs the identity of) d, then b will instead advertise the link b-d. If b spoofs the identity of d when generating TCs, the link d-a is advertised. As neither b-d nor d-a exist in the network, this will cause incorrect topology maps in routers -with potential consequences including routing loops, parts of the network being disconnected or traffic to the same destination from different parts of the network terminating in different routers [START_REF] Clausen | Vulnerability Analysis of the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF]. 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.

Symmetric attacks exist by instead of spoofing the identity of itself, a router spoofs the identity of its neighborsi.e spoofs links in the network: e.g., if b sends TCs advertising a link b-d without having a neighbor spoofing the identity of d, this will have similar effects.

C. Paper Outline

The remainder of this paper is organized as follows: section II presents the general idea of "admittance control" in OLSRv2, allowing a router to employ cryptographic signatures to detect, and take proper actions, against identity spoofing. Section III expresses this in terms of an extension to OLSRv2, and section IV studies the performance of an OLSRv2 network when using this extension and with various cryptographic algorithms. [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. This paper , therefore, in place of the usual network performance metrics (overhead, bandwidth, ...) studies per-message processing overhead, both for when generating and receiving messages. The paper is concluded in section V.

II. ADMITTANCE CONTROL

The objective in this paper is to provide a mechanism, akin to that which is employed in "classic" routed networks as described in I: a way of ensuring that only trusted peers are admitted to participate in the control message exchange between routers -and, thus, also a way for a router to logically "disconnect" a non-trustworthy peer. Absent the ability to physically control access to the channel between routers, the mechanism employs logical "admittance control" by including cryptographic signatures in control messages (HELLO and TCs), and requires their verification prior to accepting a control message for processing or forwarding.

Verification of a cryptographic signature, associated with a control message, allows the recipient to assert that (i) the control message has not been altered while in transit and (ii) the originator of the control message is in possession of a cryptographic key for generating a valid signature. Concerning (ii), a cryptographic algorithm employing symmetric shared keys supports simple discrimination between "trusted" and "untrusted" routers. Employing asymmetric keys enables discrimination between individual trusted routers, thus prohibiting a "trusted router" from spoofing the identity of another router (trusted or not) in the network.

Associating signatures with control messages is not without effect on network performance: generation and verification of signatures incurs a computational overhead in each router, and inclusion of signatures in control messages increase the number of bits to transmit over the wireless interface. These effects are, for a selection of cryptographic algorithms, quantified in this paper .

A. Resilience Evaluation

The admittance control mechanism enables routers to determine if a received control message originates from a "trusted router", discarding information received from non-trusted routers. This leaves two remaining vulnerabilities uncovered: (i) recording control traffic from a "trusted router" for later replaying (possibly elsewhere in the network) and (ii) trusted routers misbehaving, e.g. by spoofing links.

For (i), a countermeasure in the form of synchronized timestamps can be employed, included in each control message; for (ii), inclusion of signatures for both ends of an advertised link can be considered. Synchronized time-stamps and per-link signatures are, however, the subject for a subsequent article.

III. SPECIFICATION

Introducing admittance control to OLSRv2 requires specification of (i) a way of associating signatures to control messages and (ii) the necessary processing for generating and verifying signatures (and, appropriate actions to take in case verification fails). Compared to its predecessor, OLSRv2 facilitates this through the use of [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] as packet and message format, and through explicit "hooks" 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] for recognizing external reasons for rejecting a message as malformed.

A. Signature TLV Structure

[2] enables a generic way for protocol extensions to add information to control messages by way of inclusion Type-Length-Value (TLV) objects. Thus, a security extension can associate a signature to a HELLO or TC by including a "Signature TLV" in the control message: <sign-tlv> := <hash-fkt><sign_algo><sign> where: <hash-fkt> and <sign_algo> identify the choice of hash function and signature algorithm, respectively, and <sign> contains the digital signature, calculated thus: sign = sign_algo(hash-fkt(message)) Verification of a message is a boolean operation, acting as a black-box for the routing protocol and returning true if the message signature verifies, false otherwise: verified = verif(message, <sign-tlv>)

B. Message Generation and Processing

As enabled by [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], subsequent to the usual HELLO and TC generation, outgoing messages are signed and a <sign-tlv> included. Upon receipt of a HELLO or TC, a message is identified as malformed and, thus, not processed, if verif(...) for that message returns false. For TC messages, per-hop mutable fields (hop-count and hop-limit) are set to 0 for calculating <sign> and verif(...).

Note that due to the packet and message format of OL-SRv2 [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF], using this signature extension keeps compatibility with the "core" OLSRv2 specification. A router, that uses OLSRv2 without the extension, does not know the TLV type and will consequently ignore the information contained in these TLVs. It it thus able to correctly process signed control messages, however, its HELLOs and TCs will be rejected by all routers applying the security extension, since the messages not signed.

IV. PERFORMANCE STUDY

Introduction of signatures provides a measure of "admittance control" to OLSRv2 -at the expense of increased control message sizes and per-message-generation/processing overhead, dependent on the cryptographic algorithms employed. This additional overhead is quantified by way of NS2 simulations, using with a selection of cryptographic algorithms: RSA-1024, DSA-1024 and ECDSA-160. The signature-lengths in these algorithms have been chosen so as to provide similar resilience against attacks, with an 80-bit security level [START_REF]Recommendation for Key Management -Part 1: General[END_REF].

RSA [START_REF] Kaliski | PKCS 1: RSA Cryptography Specifications Version 2.0[END_REF], DSA [START_REF]Digital Signature Standard[END_REF] and ECDSA [START_REF] Johnson | The Elliptic Curve Digital Signature Algorithm (ECDSA)[END_REF] employ asymmetric keys, i.e. permit by verification of the signature to also verify the identity of the router generating the message. For comparison, the symmetric HMAC-801 [START_REF] Krawczyk | HMAC: Keyed-Hashing for Message Authentication[END_REF] algorithm is also included. The results presented in this section are all normalized wrt. OLSRv2, i.e. only the additional overhead incurring from the security extension is depicted.

Simulations have been conducted using JOLSRv2 [START_REF] Herberg | JOLSRv2 -An OLSRv2 implementation in Java[END_REF] using relatively standard scenario parameters (1km2 square, 100m segments of random walk at 2-8 m s , 0-5s pause-time and 5 concurrent CBR streams of 3.2kb/s). The number of routers was varied between 10 and 50, and each value has been averaged over 15 simulation runs. In addition to the additional control traffic overhead, the in-router message generation/processing overhead has also been measured. JOLSRv2 uses AgentJ [START_REF] Herberg | Integrating Java Support for Routing Protocols in Ns2[END_REF] for interfacing with NS2. AgentJ/NS2 permits a single thread execution at a time, without preemption, thereby allowing instrumenting the signature generation and verification code to record the time spent on each such operation 2 . For the simulations, an Intel Core 2 CPU with 2.1 GHz and 4 GB of RAM was used.

A. Simulation Results

Table I summarizes the average measured time for generating and processing control messages, as well as the average overhead, incurred by each of the four signature processes. For OLSRv2 without signatures, these values would all be zero.

As a first observation, HMAC-80 requires significantly less time than ECDSA, DSA and RSA for generating a message signature. For verification of a message signature, HMAC likewise spends substantially less time than ECDSA and DSA, whereas RSA is close to HMAC in the time it requires for a verification. Verification of RSA signatures is faster than both ECDSA and DSA, however with much greater overhead as well. These figures are hardly surprising; the characteristics of the various signature algorithms are well-known [START_REF]Digital Signature Standard[END_REF].

Figure 2 depicts the cumulative time each router spends, over the duration of 100 seconds, on generating message signatures in JOLSRv2. As the number of routers grow in the network, so does the time each router spends in total on generating signatures. The reason for this is, that OLSRv2 enables "triggered message generation", i.e. that message generation may result from some external event, in addition to periodical messages. Thus, with more routers being present in the network, more links are detected as appearing/disappearing -and therefore more messages, and corresponding signatures, are generated.

The corresponding cumulative processing time in each router is depicted in figure 3. Each router generates HELLOs, which must be processed 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. Finally, as indicated above, triggered messages as more links appear/disappear in the network also cause more messages with signatures to verify. A couple of general observations can be made concerning the results. While HMAC and RSA do not need a significant amount of time for signature verification, ECDSA routers spend almost 8% of their time verifying signatures, while DSA spends more than 10%. This might still appear reasonable -but it has to be kept in mind that the simulation was performed on relatively fast hardware 3 , whereas devices in an OLSRv2 network may be far less powerful than that, such as smartphones or even sensors. Thus, one might be tempted to use RSA signatures if CPU ressources is the primary concern and ECDSA otherwise. That said, ECDSA scales better than RSA (e.g., increasing from 80-bit security level to 128-bit level will lengthen ECDSA keys by about 40% and RSA keys by 200%), which should be taken into account when elevating the security level.

Figure 4 depicts the cumulative overhead in the network, due to the inclusion of message signatures. Intuitively, as the per-message overhead is constant, the cumulative overhead would be a function of the number of control messages -itself a function of simulation time and number of routers. That the curves in figure 4 grow slightly faster than linearly with the number of routers is, as stated previously, due to triggered messages.

V. CONCLUSION

This paper has presented a general extension to OLSRv2 for providing "admittance control" in an OLSRv2 network: enabling admitting "trusted routers" and excluding "non-trusted" 3 Albeit using the less than optimal Java multi-precision arithmetic. routers from participating in the control message exchange between routers, thereby providing a mode-of-operation of an OLSRv2 network, similar to that which is otherwise employed for preserving network integrity in routed networks.

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. The signature algorithms used were RSA-1024, DSA-1024 and ECDSA-160 -chosen and parameterized in order to provide for comparable resilience.

Figure 1 .

 1 Figure 1. Basic OLSRv2 Operation but offers various improvements, e.g. a modular and flexible architecture allowing extensions to be developed as add-ons to the basic protocol.OLSRv2 contains three basic processes: Neighborhood Discovery, Link State Advertisement and MPR Flooding. Neighbor Discovery and Link State Advertisement manifest themselves through HELLO and TC messages, generated periodically. HELLOs and TCs, both, advertise links between the router generating the message and (a subset of) its neighbors -possibly also indicating additional information pertaining to each such link. HELLOs are used for detecting bi-directionality of links, and list all neighbors, each associated with a status flag (HEARD, SYM). HELLOs are exchanged only with direct neighbors. TCs are used for sharing link-state information network-wide, and list only neighbors with which a symmetric link has been identified (by the Neighborhood Discovery process). TCs include a sequence number, used to allow recipients to exclude outdated information, incremented when the set of advertised links changes. TCs are delivered through the network using MPR Flooding.MPR flooding is a process for each router to efficiently perform network-wide broadcasts. Each router designates, a subset (MPR set) from among the neighbors with which a bi-directional link has been identified, such that a message transmitted by the router and relayed by the MPR set is received by all its 2-hop neighbors. MPR selection is signaled by a router by associating a flag (MPR) to the selected neighbors in outgoing HELLOs. The set of routers having selected a given router as MPR is the MPR-selector-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].MPR selection further serves to allow designation of which links are to be included in TC messages: a router must (at least) include links to all its MPR-selector-set. Thus, the schematic operation of OLSRv2 is illustrated in figure1.

Figure 2 .Figure 3 .

 23 Figure 2. Cumulative time per router spent on generating message signatures.

Figure 4 .

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

Note that HMAC, strictly speaking, is not a signature algorithm, but a Message Authentication Code. As such, it does not offer per-principal authentication nor non-repudiation. In the rest of the paper , we will not make this distinction and will abusively refer to HMAC as a signature method.

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".


Thomas Clausen

Ulrich Herberg

Vulnerability Analysis of the Optimized Link State Routing Protocol version 2 (OLSRv2)

Keywords: OLSRv2, MANET, Vulnerability Analysis, Security

Mobile Ad hoc NETworks (MANETs) are leaving the confines of research laboratories, to find place in real-world deployments. Outside specialized domains (military, vehicular, etc.), citywide community-networks are emerging, connecting regular Internet users with each other, and with the Internet, via MANETs. Growing to encompass more than a handful of "trusted participants", the question of preserving the MANET network connectivity, even when faced with careless or malicious participants, arises, and must be addressed.

A first step towards protecting a MANET is to analyze the vulnerabilities of the routing protocol, managing the connectivity. By understanding how the algorithms of the routing protocol operate, and how these can be exploited by those with ill intent, countermeasures can be developed, readying MANETs for wider deployment and use.

This paper takes an abstract look at the algorithms that constitute the Optimized Link State Routing Protocol version 2 (OLSRv2), and identifies for each protocol element the possible vulnerabilities and attacks -in a certain way, provides a "cookbook" for how to best attack an operational OLSRv2 network, or for how to proceed with developing protective countermeasures against these attacks.

I. INTRODUCTION

OLSRv2 (the Optimized Link State Routing Protocol version 2) [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 (Mobile Ad hoc NETworks). 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.

The developments reflected in OLSRv2 have been motivated by increased real-world deployment experiences, e.g. from networks such as FunkFeuer [7], and the requirements presented for continued successful operation of these networks. With participation in such networks increasing (the FunkFeuer community network has, e.g., roughly 400 individual participants), operating with the assumption, that participants can be "trusted" to behave in a non-destructive way, is utopia. Taking the Internet as an example, as participation in the network increases and becomes more diverse, more efforts are required to preserve the integrity and operation of the network. Most SMTP-servers were, e.g., initially available for use by all and sundry on the Internet -with an increased populace on the Internet, the recommended practice is to require authentication and accounting for users of such SMTP servers [START_REF] Hutzler | Email Submission Operations: Access and Accountability Requirements[END_REF].

A first step towards hardening against attacks disrupting the connectivity of a network, is to understand the vulnerabilities of routing protocol, managing the connectivity. This paper Thomas Clausen and Ulrich Herberg are with the "Laboratoire d'Informatique de l'X" (LIX) at Ecole Polytechnique, UMR CNRS, 7161 Paris, France, email: Thomas@ThomasClausen.org, Ulrich@Herberg.name therefore analyzes OLSRv2, to understand its inherent vulnerabilities and resiliences. The authors do not claim completeness of the analysis, but hope that the identified attacks as presented form a meaningful starting-point for OLSRv2 security.

A. OLSRv2 Overview

OLSRv2 contains three basic processes: Neighborhood Discovery, MPR Flooding and Link State Advertisements.

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). 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.

2) MPR Flooding: The process whereby each router is able to, efficiently, conduct network-wide broadcasts. Each router designates, from among its bi-directional neighbors, a subset (MPR set) such that a message transmitted by the router and relayed by the MPR set is received by all its 2-hop neighbors. MPR selection is encoded in outgoing HELLOs. The set of routers having selected a given router as MPR is the MPR-selector-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 ink state advertisements are 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 TC are also bi-directional. TC messages are sent periodically, however certain events may trigger non-periodic TCs.

B. Link State Vulnerability Taxonomy

Proper functioning of 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. An OLSRv2 network can be disrupted by breaking either of these assumptions, 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.

C. OLSRv2 Attack Vectors

Besides "radio jamming", attacks on OLSRv2 consist of a malicious router injecting "correctly looking, but invalid, control traffic" (TCs, HELLOs) into the network. A malicious router can either (a) lie about itself (its ID, its willingness to serve as MPR), henceforth Identity Spoofing or (b) lie about its relationship to other routers (pretend existence of links to other routers), henceforth Link Spoofing. Such attacks will infine cause disruption in the Link State Advertisement process, through targeting the MPR Flooding mechanism, or by causing incorrect link state information to be included in TCs, causing routers to have incomplete, inaccurate or inconsistent topology maps. In a different class of attacks, a malicious router injects control traffic, tuned to cause an in-router resource exhaustion, e.g. by causing the algorithms calculating routing tables or MPR sets to be invoked continuously, preventing the internal state of the router from converging.

D. Paper Outline

The remainder of this paper is organized as follows: section II, III, and IV each represents a class of disruptive attacks against OLSRv2, detailing a number of attacks in each class. Section V summarizes the identified vulnerabilities in an OLSRv2 network, and section VI summarizes the ways OLSRv2 has inherent resilience to. The paper is concluded in section VII.

II. TOPOLOGY MAP ACQUISITION

Topology Map Acquisition relates to the ability for a -any -given router in the network to acquire a representation of the network connectivity. A router, unable to acquire a topology map, is incapable of calculating routing paths and participating in forwarding data. Topology map acquisition can be hindered by (a) TC messages to not being delivered to (all) routers in the network, such as what happens in case of Flooding Disruption, or (b) in case of "jamming" of the communication channel.

A. Flooding Disruption

MPR selection (section I-A2) uses information about a router's 1-hop and 2-hop neighborhood, assuming that (i) this information is accurate, and (ii) all 1-hop neighbors are equally apt as MPR. Thus, a malicious router will seek to manipulate the 1-hop and 2-hop neighborhood information in a router such as to cause the MPR selection to fail. In figure 2, X (gray) spoofs the identity of x (white), i.e. a and c both receive HELLOs from a router identifying as x. For b, a and c present the same neighbor sets, and are equal candidates for MPR selection. If b selects only a as MPR, c will not relay flooded traffic from or transiting via b, and the (white) router x (and routers to the "right" of it) will not receive flooded traffic.

2) Flooding Disruption due to Link Spoofing: In the network in figure 3, the malicious router X spoofs links to the existing router c, as well as to a fictitious w. a receives HELLOs from X and b, reporting X:{X-c, X-w}, b:{b-c}. All else being equal, X appears a better choice as MPR than b, as X appears to cover all neighbors of b, plus w.

B. Radio Jamming

Radio Jamming is an attack, in which access to the communication channel between routers is hindered by, e.g., a powerful transmitter is generating "white noise" on the channel. Due to the ease of access to the channel, this is particularly possible in wireless networks. Jamming affects reception, thus interfaces on a "jammed" channel are unable to receive HELLO and TCs. Depending on lower layers, this may not affect transmissions: HELLOs and TCs from a router with "jammed" interfaces may be received by other routers. As the Neighborhood Discovery process of OLSRv2 identifies and uses only bi-directional links for the Link State Advertisement process, a link from a jammed router to a non-jammed router would not be considered, and the jammed router appear simply as "disconnected" for the un-jammed part of the networkwhich is able to maintain accurate topology maps.

III. EFFECTIVE TOPOLOGY

Link-state protocols assume that each router can acquire an accurate topology map, reflecting the effective network topology. This implies that the routing protocol, through its message exchange, identifies a path from a source to a destination, and this path is valid for forwarding data traffic.

A. Incorrect Forwarding

In OLSRv2, routers send TCs and HELLOs using link-local transmissions; the routing process in each router retransmits received messages, destined for network-wide diffusion. If the router is not configured to enable forwarding, this will not affect acquisition of a topology map by the routing protocol -but will cause a discrepancy between the effective topology and the topology map.

B. Wormholes

A wormhole, depicted in the example in figure 4, may be established between two collaborating devices, connected by an out-of-band channel; these devices send traffic through the "tunnel" to their alter-ego, which "replays" the traffic. Thus, router d and router s appear as-if direct neighbors and reachable from each other in 1 hop through the tunnel, with the path through the MANET being 100 hops long. The impact of a wormhole depends on its detailed behavior. If the wormhole relays control traffic, but not data traffic, the considerations in section III-A applies. If it relays control and data traffic alike, it is identical to a usable link: the routing protocol will generate a topology map reflecting this as the effective network topology. The efficiency of the topology so obtained depends on (i) the wormhole characteristics, (ii) how the wormhole presents itself and (iii) how paths are calculated. If the cost of the wormhole "link" represents the actual cost of transit, then the wormhole may in the worst case cause no degradation in performance, in the best case improve performance by offering a better path. If the wormhole "misrepresents" the cost of transit, then the presence of the wormhole results in a degradation in performance as compared to using the non-wormhole path. Conversely, if the "link" presented by the wormhole has better characteristics, the wormhole results in improved performance.

An additional consideration with regards to wormholes is, that it may be undesirable to have data traffic transit such a path: an attacker could, by introducing a wormhole, acquire the ability to record and inspect transiting data traffic.

C. Sequence Number Attacks

OLSRv2 uses two different sequence numbers in TCs, to (i) avoid processing and forwarding the same message more than once (Message Sequence Number), and (ii) to ensure that old information, arriving late due to e.g. long paths other delays, is not allowed to overwrite fresher information (Advertised Neighbor Sequence Number -ANSN).

For (i), an attack may consist of a malicious router spoofing the identity of another router in the network, and transmitting a large number of TCs, each with different Message Sequence Numbers. Subsequent TCs with the same sequence numbers, originating from the router whose identity was spoofed, would thence be ignored, until eventually information concerning these "spoofed" TC messages expires.

For (ii), an attack may consist of a malicious router spoofing the identity of another router in the network, and transmitting a single TC, with an ANSN significantly larger than that which was last used by the legitimate router. Routers will retain this larger ANSN as "the most fresh information" and discard subsequent TCs with lower sequence numbers as being "old".

D. Message Timing Attacks

In OLSRv2, each control message may contain "validity time" and "interval time" fields, identifying the time for which information in that control message should be considered valid until discarded, and the time until the next control message of the same type should be expected [START_REF] Clausen | RFC5497: Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)[END_REF].

1) Interval Time Attack: A use of the expected interval between two successive HELLO messages is for determining the link quality in Neighbor Discovery process, as described in [START_REF] Clausen | RFC3626: Optimized Link State Routing Protocol (OLSR)[END_REF]: if messages are not received with the expected intervals (e.g. a certain fraction of messages are missing), then this may be used to exclude a link from being considered as useful, even if (some) bi-directional communication has been verified. If a malicious router X spoofs the identity of an existing router a, and sends HELLOs indicating a very low interval time, a router b receiving this HELLO will expect the following HELLO to arrive within the interval time indicated -or otherwise, decrease the link quality for the link a-b. Thus, X may cause b's estimate of the link quality for the link a-b to fall below the limit, where it is no longer considered as useful and, thus, not used.

2) Validity Time Attack: A malicious router, X, can spoof the identity of a router a and send a HELLO using a very low validity time (e.g. 1 ms). A receiving router b will discard the information upon expiration of that interval, i.e. a link between router a and b will be "torn down" by X.

E. Indirect Jamming

Indirect Jamming is when a malicious router X by its actions causes legitimate routers to generate inordinate amounts of control traffic. This increases channel occupation, and the overhead in each receiving router processing this control traffic. With this traffic originating from legitimate routers, the malicious device may remain undetected to the wider network.

1) Indirect Jamming: Neighborhood Discovery: Indirect Jamming of the Neighborhood Discovery process will cause additional MPR set calculations; are "triggered HELLOs" enabled, an increased HELLO frequency occurs.

2) Indirect Jamming: Link State Advertisement: Similar to III-E1, figure 6 illustrates indirect jamming of the Link State Advertisement process. A malicious router X may "flip" between selecting a as MPR, and between advertising the link a-X as lost. This leads a to update its set of advertised neighbors (as the MPR Selector Set of a changes), increase the corresponding ANSN, and advertise this in a subsequent TC -which X uses to trigger another "status flip".

Each such TC with an updated ANSN causes all routers in the network to recalculate their routing tables; are "triggered TCs" enabled, an increased TC frequency occurs. Inconsistent topology maps can occur by a malicious router employing either of identity spoofing or link spoofing for conducting an attack against an OLSRv2 network.

A. Identity spoofing

Identity spoofing can be employed by a malicious router via the Neighborhood Discovery process and via the Link State Advertisement process; either of which causing inconsistent topology maps in routers in the network.

1) Inconsistent Topology Maps due to Neighborhood Discovery: In order to minimize the risk of detection, the malicious router (gray circle) in figure 7 elects to not participate in the Link State Advertisement procedure, thus it does not select any MPRs and does not accept being elected as MPR (by advertising a willingness of zero). By not participating in the Link State Advertisement process, its presence is known only to c, d and e. X elects to spoof the identity of a, b, f and g, i.e. routers whose identity it spoofs will not receive control messages, and thus not allowing them to detect that these identities are also advertised elsewhere in the network. Traffic transiting d, from either side, to destination a, b, f and g will, rather than being forwarded to the intended destination, be delivered to the malicious router. In figure 7, c is the only router receiving control traffic indicating two topologic locations of the identities a, b. However this is not an unusual situation: a valid link might indeed exist between routers a and d as well as between routers b and d, e.g. through another channel. This creates a situation wherein two or more routers have inconsistent topology maps: traffic for an identified destination is, depending on where in the network it appears, delivered to different routers.

2) Inconsistent Topology Maps due to Link State Advertisements: An inconsistent topology map may also occur when the malicious router takes part in the Link State Advertisement process: spoofing an identity and selecting MPRs causes a link to the spoofed identities of the malicious router to be advertised through the network. In figure 8, the malicious router X spoofs the address of a. If X selects f as MPR, all routers in the network will be informed about the link f-a by way the TCs originating from f. Assuming that (the real) a selects b as MPR, the link b-a will also be advertised through the network.

b and c will calculate paths to a via b. e and f will calculate paths to a via f -i.e. through the malicious router X. e and f are thus disconnected from the real a. d will have the choice of selecting a path in to a in either direction.

In general, the following observations can be made: (i) the network will be split in two, with those routers closer to b than to X reaching a, and those routers closer to X than to b will be unable to reach a; (ii) routers beyond b, i.e. routers beyond one hop away from a will be unable to detect this identity spoofing.

The impact of combining identity spoofing with Link State Advertisements is greater than the impact of section IV-A1, as it causes alterations to the topology maps of all routers in the network. The attack is also easier to detect: with the malicious router advertised through the network, routers whose identities spoofed can detect this. When a receives a TC message from f advertising the link f-a, it can deduce that "something is wrong" as a does not have f recorded as a direct neighbor.

B. Link Spoofing

Link spoofing can be employed by a malicious router via the Neighborhood Discovery process and via the Link State Advertisement process; either of which causing inconsistent topology maps in routers in the network.

1) Inconsistent Topology Maps due to Neighborhood Discovery: The malicious router X in figure 3 spoofs two links to c and w. Consequently, a selects X as its MPR -and therefore router X is the sole router expected to advertise links to a. s selects a as MPR, thus a is expected to advertise the link a-S through the network, i.e. using the MPR flooding process.

The topology maps acquired by the various routers in this example are: 2) Inconsistent Topology Maps due to Link State Advertisements: The malicious router X in figure 10 spoofs links to the existing a, by participating in the Link State Advertisement process and including the link X-a in its advertisements. As TC messages are flooded through the network, all routers will receive and record information describing the link X-a. If a has selected b as MPR, a will likewise flood this link state information through the network, and all routers will receive and record information describing a link b-a.

Routers b, c and d will calculate a shortest path via a different router than routers f and g, thus leading to network split in two. This is similar to the impact of section IV-A2, and when a receives a TC message from X advertising the link X-a, it can likewise deduce that "something is wrong" as a does not have X recorded as a direct neighbor. VI. INHERENT OLSRV2 RESILIENCE While OLSRv2 does not specifically include security features (such as encryption), it has some inherent resilience against part of the attacks described in this paper. In particular, it provides the following resilience:

V. VULNERABILITY SUMMARY

• Sequence numbers: OLSRv2 employs message sequence numbers, specific per router identity and message type. Routers keep an "information freshness" number (ANSN), incremented each time the content of a Link State Advertisement from a router changes. This allows rejecting "old" information and duplicate messages, and provides some protection against "message replay". This also presents an attack vector (section III-C).

• Ignoring uni-directional links: The Neighborhood Discovery process detects and admits only bi-directional links for use in MPR selection and Link State Advertisement. Jamming attacks (section II-B) may affect only reception of control traffic, however OLSRv2 will correctly recognize, and ignore, such a link as not bidirectional.

• Message interval bounds: The frequency of control messages, with minimum intervals imposed for HELLO and TCs. This may limit the impact from an indirect jamming attack (section III-E). • Additional reasons for rejecting control messages: The OLSRv2 specification includes a list of reasons, for which an incoming control message should be rejected as malformed -and allows that a protocol extension may recognize additional reasons for OLSRv2 to consider a message malformed. This allows -together with the flexible message format [START_REF] Clausen | RFC5444: Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] -addition of security mechanisms, such as digital signatures, while remaining compliant with the OLSRv2 standard specification.

VII. CONCLUSION

This paper has presented a detailed analysis of security threats to the Optimized Link State Routing Protocol version 2 (OLSRv2), by taking an abstract look at the algorithms and message exchanges that constitute the protocol, and for each protocol element identifying the possible vulnerabilities and how these can be exploited. In particular, 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 (consistent) topology maps. An OLSRv2 network can be effectively disrupted by breaking either of these assumptions, 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 substantially inconsistent topology maps.

The disruptive attacks to OLSRv2, presented in this paper, are classified in either of these categories. For each, it is demonstrated, whether OLSRv2 has an inherent protection against the attack. Thomas has a particular affinity for "applicable research", and enjoys working with industrial partners and standardisation bodies. He is, thus co-chair of the MANET AUTOCONF working group within the IETF, as well as the author and editor of several standard track and other documents within the IETF.

Ulrich Herberg graduated in computer science from TU Munich in 2007, and then joined Ecole Polytechnique (France), where he is currently a PhD student. His research interests cover routing and security issues in MANETs, auto-configuration, and delaytolerant networks.

1 )

 1 Flooding Disruption due to Identity Spoofing: In figure 1, a malicious router X spoofs the identity of b. The link between X and c is correctly detected and listed in X's HELLOs. a will receive HELLOs indicating a links, respectively b:{ b-e }, X:{ X-c, X-e }, and d:{ d-e, d-c }. For a, X and d are equal candidates for MPR selection.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Identity Spoofing: The malicious router spoofs address of router b.

Fig. 3 .

 3 Fig. 3. Link Spoofing: Flooding Disruption As a will not select b as MPR, b will not relay flooded messages received from a. The routers left of b (starting with c) will, thus, not receive any flooded messages from or transiting a (e.g. a message originating from s).

Fig. 4 .

 4 Fig.4. Wormholing between two collaborating devices not participating in the routing protocol, "tunneling" traffic between s and d over an "out-of-band" channel.

Fig. 5 .

 5 Fig. 5. Indirect Jamming in Neighborhood Discovery

Fig. 6 .

 6 Fig.6. Indirect Jamming in Link State Advertisement

Fig. 7 .

 7 Fig. 7. Identity Spoofing: maximizing disruptive impact while minimizing risk of detection.

Fig. 8 .

 8 Fig. 8. Identity Spoofing due to Link State Advertisements

•

  a and b: accurate topology map due to the Neighborhood Discovery process providing topological information up to 2 hops away. • c: as in figure 9(a). Link state advertisements from a are not forwarded by b. Existence of s and the link a-s is not known beyond b. Existence of a and the link b-a and is known to b through the Neighborhood Discovery process. • d and beyond: as illustrated in figure 9(b). • s: accurate Topology Map corresponding to the network in figure 3. This may contain the dotted routers c and w, only if X participates in the Link State Advertisement process (section IV-B2).

  Inconsistent Topology Map in router c. b c d (b) Inconsistent Topology Map in routers d and beyond.

Fig. 9 .

 9 Fig. 9. Perceived Topology Maps with malicious router X performing Link Spoofing in the Neighborhood Discovery Process.

Fig. 10 .

 10 Fig.10. Link Spoofing: The malicious router X advertises a spoofed link to router a in its TC messages, thus all routers will record the links X-a and b-a.

Thomas

  Clausen is a graduate of Aalborg University, Denmark (M.Sc., PhD -civilingeniør, cand. polyt), Thomas spent a number of years at INRIA where he, among other things, spent his time developing and standardising OLSR. In 2004 he joined faculty at Ecole Polytechnique, France's premiere technical university.

Table I

 I summarizes the vulnerabilities in OLSRv2, as presented in this paper. For each, a note indicates if OLSRv2 provides some inherent resilience; further discussion of the resilience of OLSRv2 is given in section VI.

	Attack	Section OLSRv2 Resilience?
		Topology Map Acquisition
	Flooding disruption	II-A	None
	Radio Jamming	II-B	Partly: Considers only bidirectional
			links
		Effective Topology
	Incorrect Forwarding III-A	None
	Wormholes	III-B	none
	Sequence Numbers	III-C	Partly: rejecting "old" messages
	Message Timing	III-D	None
	Indirect Jamming	III-E	Yes: minimum and maximum intervals
		Inconsistent Topology
	Identity Spoofing	IV-A	None
	Link Spoofing	IV-B	None
			TABLE I
	VULNERABILITY SUMMARY OF OLSRV2


Emmanuel Baccelli

Thomas Heide Clausen
email: thomas.clausen@polytechnique.fr

Philippe Jacquet

Dang-Quan Nguyen
email: .nguyen@inria.fr

Jacquet

Dang-Quan

Integrating VANETs in the Internet Core with OSPF : the MPR-OSPF Approach

Solutions for mobile ad hoc routing have matured over the last decade. Building atop these foundations, new challenges are set for MANETs, such as integration in the Internet core. On this topic, this paper designs and evaluates MPR-OSPF, an extension of the OSPF protocol enabling its operation on networks that may include both MANET nodes and usual fixed routers. Automatic integration of different types of vehicular ad hoc networks (VANETs) in the IP infrastructure is then possible using the classic OSPF framework. Techniques used therefore are derived from OLSR, the MANET routing protocol that is the most compatible with traditional IP environments.

I. INTRODUCTION

Mobile Ad hoc Networks have attracted considerable attention over the last decade, both in academic and industrial environments. MANETs were initially designed as networks isolated from the Internet (at most, MANETs would be connected via a gateway), and the main challenge was that of providing efficient routing inside MANETs, as the new characteristics implied by ad hoc mobility made traditional solutions inappropriate.

Two families of solutions have been developed in order to address this challenge. On one hand, the reactive routing protocols (such as AODV [START_REF] Perkins | Ad Hoc On-Demand Distance Vector Routing[END_REF] and DSR [START_REF] Johnson | The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks[END_REF]) and on the other hand the proactive routing protocols (such as OLSR [START_REF] Clausen | Optimized Link State Routing Protocol[END_REF]). These protocols have been the subject of intensive attention from the community in the recent years, and have been extensively experimented in various scenarii by means of simulations as well as actual deployments.

As MANET routing has matured, focus is now put on another challenge: integrating MANETs inside the Internet core, by means of designing a wireless extension for OSPF [START_REF] Coltun | OSPF for IPv6. Internet Engineering Task Force (IETF) Request For Comments[END_REF] enabling router ad hoc mobility. In order to guarantee full compatibility with legacy OSPF, a natural solution is to base this extension on MANETs' proactive link state approach, since OSPF is itself proactive and link state. In this paper we therefore design MPR-OSPF, a wireless extension for OSPFv3 based on OLSR, the MANET proactive protocol that has emerged as the simplest and most robust solution for mobile ad hoc routing.

A. Paper Outline

The paper is organized as follows. We first overview OLSR and the techniques it employs (it is however assumed that the reader is familiar with OSPF). Then, we describe the base of MPR-OSPF: the specification of a new OSPFv3 interface type tailored for MANETs. This new interface is plugging into OSPF several techniques derived from the IETF [START_REF]The Internet Engineering Task Force (IETF[END_REF] developed MANET protocol OLSR, while retaining the basic OSPF framework. The performance of MPR-OSPF is then evaluated and compared to that of alternative approaches also under development, such as MDR [START_REF] Ogier | MANET Extension of OSPF using CDS Flooding[END_REF] and OR [START_REF] Chandra | Extensions to OSPF to Support Mobile Ad Hoc Networking[END_REF].

MDR and OR propose OSPF extensions based on novel techniques, which deviate further from the generic OSPF framework. Qualitative arguments are then made about key differences in the design of MPR-OSPF compared with these other approaches. Finally, simulation results are given in order to make quantitative comparisons based on criteria including control traffic overhead, and delivery ratio in different node density and mobility scenarii.

We conclude from this qualitative and quantitative evaluation that MPR-OSPF is simple and efficient, as compared to the other proposed approaches. Moreover, we conclude that contrary to the other proposed approaches, MPR-OSPF ensures that its efficiency on MANETs is not at the price of altering traditional OSPF properties, and that in particular it preserves shortest path routing over synchronized links.

II. THE OLSR PROTOCOL

In this section we briefly outline OLSR, the proactive ad hoc routing solution standardized in the IETF [START_REF]The Internet Engineering Task Force (IETF[END_REF]. The essential facts about the protocol that are interesting in the context of this paper are given in the following. For further details on OLSR, refer to [START_REF] Clausen | Optimized Link State Routing Protocol[END_REF].

As a proactive link-state routing protocol, OLSR (Optimized Link State Routing) employs periodic exchange of control messages in order to accomplish topology discovery and maintenance. This exchange results in a topology map being present in each node in the network, from which a routing table can be Basically, OLSR employs two types of control messages: HELLO messages and TC (Topology Control) messages. HELLO messages have local scope and are exchanged periodically between neighbor nodes only, essentially tracking the status of links between neighbors. On the other hand, TC messages have larger scope and are emitted periodically to diffuse link-state information throughout the entire network. This operation of diffusing a message to the entire network -also called flooding -is optimized in OLSR with a mechanism called MPR flooding (MPR stands for Multi-Point Relay, see [START_REF] Qayyum | Multipoint Relaying: An Efficient Technique for Flooding in Mobile Wireless Networks[END_REF] for an analysis of this particular technique). This optimization reduces drastically the cost of performing a flooding operation, through having each node select a minimal set of "relay nodes" (called MPRs), responsible for relaying flooded packets. As shown in Fig. 1, from the local point of view of a node flooding a packet -i.e. the center node in the figure -this corresponds to only the minimal number of neighbors (the black nodes) relaying the broadcast, instead of basically all the neighbors.

III. OVERVIEW OF MPR-OSPF

MPR-OSPF specifies an OSPFv3 interface type tailored for mobile ad hoc networks: the OSPF MANET interface. It is assumed that the reader is familiar with the OSPF protocol and related terminology [START_REF] Coltun | OSPF for IPv6. Internet Engineering Task Force (IETF) Request For Comments[END_REF]. The OSPF MANET interface makes use of flooding reduction, topology reduction and adjacency reduction mechanisms based on multi-point relaying (see previous section). The following outlines the design of this new interface type. For more details on MPR-OSPF, see [START_REF] Baccelli | OSPF MPR Extension for Ad Hoc Networks[END_REF].

Efficient Flooding with MPR. OSPF MANET interfaces use the MPR flooding technique, whereby only some OSPF MANET neighbors (those selected as MPR for flooding) are responsible for retransmitting a routing packet flooded over an OSPF MANET interface. This mechanism drastically reduces the number of (re)transmissions during flooding procedures, while still providing a natural high resilience in face of (i) transmission errors which are inherent to the use of wireless links, and (ii) obsolete two-hop neighbor information which is frequently caused by the mobility of routers [START_REF] Qayyum | Multipoint Relaying: An Efficient Technique for Flooding in Mobile Wireless Networks[END_REF] [START_REF] Adjih | On the Robustness and Stability of Connected Dominating Sets[END_REF].

MPR Topology Reduction. OSPF MANET interfaces use a topology reduction mechanism called MPR topology reduction, whereby only necessary wireless links towards OSPF MANET neighbors (those concerned by MPR selection) are listed in LSAs. OSPF MANET routers periodically generate and flood Router-LSAs describing their selection of wireless links as point-to-point links to (current) OSPF MANET neighbors. This mechanism greatly reduces the size of LSAs originated by OSPF MANET routers, while still keeping OSPF's traditional properties: robust routing and optimal paths using synchronized adjacencies [START_REF] Baccelli | Partial Topology in an MPRbased Solution for Wireless OSPF on Mobile Ad Hoc Networks[END_REF].

Multicast Transmissions of Protocol Packets. In order to reduce the overhead, multicast is used for most protocol packet transmissions over OSPF MANET interfaces, taking advantage of broadcast capabilities of the wireless medium. In particular, LSA acknowledgements are sent via multicast over these interfaces, and retransmissions over the same interfaces are considered as implicit acknowledgements. Intelligent jitter management delaying packets' (re)transmissions may also be used to increase the chance to bundle several packets in a single transmission, or to avoid superfluous retransmissions due to packet collisions. MPR Adjacency Reduction. Furthermore, OSPF MANET routers may form adjacencies with a subset of its OSPF MANET neighbors (instead of all of them). However, no Designated Router or Backup Designated Router are elected on an OSPF MANET. Instead, routers must at least bring up adjacencies with their MPR and MPR selectors. Some select routers (called synch routers) must also bring up adjacencies with their other OSPF MANET neighbors. However other routers (most of them) do not have to bring up adjacencies with OSPF MANET neighbors other than their MPR and MPR selectors. This reduces the amount of control traffic needed for database synchronization, while ensuring that LSAs still describe synchronized adjacencies only.

IV. QUALITATIVE COMPARISON OF MPR-OSPF WITH ALTERNATIVE APPROACHES

Aside from MPR-OSPF, other approaches are also being developed to specify a MANET interface for OSPF, including Overlapping Relays (OR [START_REF] Chandra | Extensions to OSPF to Support Mobile Ad Hoc Networking[END_REF]) and MANET Designated Routers (MDR [START_REF] Ogier | MANET Extension of OSPF using CDS Flooding[END_REF]). This section compares these different approaches, from a qualitative point of view.

The MDR approach. This approach uses a biconnected dominating set (CDS) to reduce flooding overhead: only members of the CDS flood new LSAs back out the receiving interface. Adjacencies are formed only between members of the CDS and a subset of their neighbors. The CDS is constructed using the 2-hop neighbor information provided by a modified Hello protocol, which also allows differential Hellos that report only changes in neighbor states. A manually configurable option can further modify router-LSAs to provide partial topology information that still ensures reachability. For more information about MDR, see [START_REF] Ogier | MANET Extension of OSPF using CDS Flooding[END_REF].

While both approaches are valid a priori, there is a main qualitative difference between MPR-OSPF and MDR concerning the properties of the routes that are provided. On one hand, MPR-OSPF (i) advertizes only synchronized adjacencies in LSAs and (ii) provides enough link information to derive shortest paths throughout the network, even if partial topology is used. On the other hand, the MDR approach (i) does not guarantee that links advertized in LSAs are all synchronized adjacencies, and (ii) does not guarantee that shortest paths can be derived, unless full topology information is used [START_REF] Baccelli | Partial Topology in an MPRbased Solution for Wireless OSPF on Mobile Ad Hoc Networks[END_REF]. MDR's lacks in these domains may cause issues within the OSPF framework, as several mechanisms traditionally working along with OSPF are based on such guarantees regarding the quality of provided routes (e.g traffic engineering protocols). Moreover, MDR's use of unsynchronized adjacencies increases the probability of routing loops, which further degrades the quality of the routes provided by this solution.

The OR approach. This approach uses a modified MPR scheme to reduce flooding overhead: Overlapping Relays. A combination of scheduled retransmissions are set by neighbors which do not flood -these retransmissions are not fired only if the whole neighborhood has been covered and has acknowledged the flood before the scheduled time. OR uses a modified Hello protocol, which signals MPR selection and allows for incremental Hellos, that report only changes in the neighborhood. Finally, OR makes use of a mechanism called Smart Peering (SP), which reduces the number of adjacencies that are brought up, based on reachability information: an adjacency is not brought up with a neighbor which is aleady reachable in the routing table. For more information about OR, see [START_REF] Chandra | Extensions to OSPF to Support Mobile Ad Hoc Networking[END_REF].

As MPR-OSPF, the OR approach advertizes only synchronized adjacencies in LSAs. However, OR's adjacency reduction mechanism does not guarantee that enough link information is available to derive shortest paths throughout the network. Nevertheless, if their respective adjacency reduction mechanisms are not used, OR and MPR-OSPF approaches both provide a route quality that is similar to that of traditional OSPF. OR and MPR-OSPF approaches then differ only "technically", by (i) employing different flooding reduction mechanisms, and (ii) while MPR-OSPF uses a topology reduction mechanisms, OR does not. Therefore, it makes sense to compare OR and MPR-OSPF more precisely, and in order to do that, quantitative evaluation is needed. The next section provides such an evaluation.

V. SIMULATION RESULTS OF THE MPR-OSPF EXTENSION FOR MANETS

This section compares, on a quantitative point of view, MPR-OSPF with OR, the alternative approach featuring similar route quality (see previous section). Simulation results using GTNetS [17] are presented, based on OSPFv3 Zebra code [START_REF] Gnu Zebra | Free Routing Software distributed under GNU General Public Licence[END_REF]. The parameters of the simulations reported in this paper are given in appendix.

The figures 2 through 9 compare the delivery ratio and the control traffic overhead in kbits per second generated by the OR protocol on one hand and the MPR-OSPF protocol on the other hand, without their respective adjacency reduction mechanisms for fair comparison (see previous section). Such evaluations are presented in scenarii featuring 20, 30, 40 and finally 50 nodes in the network, with varying radio range.

These results show that while MPR-OSPF and OR provide similar delivery ratio in every simulated scenario, MPR-OSPF consistently outperforms OR in terms of overhead, by saving up to 60% overhead needed by OR to function.

VI. CONCLUSION

In this document we have presented MPR-OSPF, an extension to OSPFv3 tailored for mobile ad hoc networks, accompanied by simulation results detailing the performance characteristics of the protocol. MPR-OSPF offers a basic plug-in of MANET matured techniques (based on MPR) in the OSPF framework, enabling OSPF to run efficiently over wireless MANET interfaces. The evaluations of the extension presented in this document show that MPR-OSPF is an excellent solution that outperforms alternative solutions, while remaining simple and robust, based on the marriage of OSPF with its natural counterpart in MANETs: OLSR.

PARAMETERS OF THE SIMULATIONS

The OR implementation used follows the specifications of [START_REF] Chandra | Extensions to OSPF to Support Mobile Ad Hoc Networking[END_REF], without the Smart Peering option. The MPR-OSPF implementation used follows the specifications of [START_REF] Baccelli | OSPF MPR Extension for Ad Hoc Networks[END_REF], without the adjacency reduction option.

The user traffic pattern used is CBR: 10 packets per second overall the network, each packet is 40 bytes long. Each node participates equally to the user traffic, by sending to each other node in the network the same fraction of the overall user traffic. The delivery ratio is then computed as the average of the delivery ratio for each node in the network. The other parameters used for the simulations that are reported in this paper are the following:

• Full IEEE 802.11b : selected ranges 40m, 60m, ... 300m, with alpha : 0.5

Fig. 1 .

 1 Fig. 1. Multipoint Relays of a node. A node (center) floods a message that is forwarded only by the neighbors it has selected as its MPRs (the black nodes). The range of the neighborhood of the node is depicted by the circle.

Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .

 2345 Fig. 2. Overhead with MPR-OSPF, compared with OR. 20 nodes.

Fig. 6 .Fig. 7 .Fig. 8 .Fig. 9 .

 6789 Fig. 6. Delivery ratio with MPR-OSPF, compared with OR. 20 nodes.

•

  Field dimensions : 500m x 500m • Number of nodes : 20, 30, 40, 50 nodes localized randomly on the field (uniform distribution)

• Mobility model: Random Waypoint, max speed 16m/s, pause 1s • HelloInterval : 2s • DeadInterval : 6s • RxmtInterval: 7s • MinLSInterval : 5s • MinLSArrival : 1s • AckInterval : 500ms


Thomas Heide Clausen

Emmanuel Baccelli
email: emmanuel.baccelli@inria.fr

Julien Garnier
email: julien.garnier@polytechnique.fr

Duplicate Address Detection in OLSR Networks

Commonly, duplicate address detection is performed when configuring network interfaces in order to ensure that unique addresses are assigned to each interface in the network. Such mechanisms commonly operate with the premises that a node "intelligently" selects an address which it supposes to be unique, followed by a duplicate address detection cycle, through which it verifies that no other active interfaces on the same network has been or is in the process of being configured with the same address. Even assuming that such a mechanism is present in a MANET, allowing MANET nodes to initially configure their interfaces with addresses unique within the network, additional complications arise: two or more MANETs may merge to form a single network, and a formerly connected MANET may partition. Thus, unless it is ensured that all MANET interfaces are assigned globally unique addresses, addressing conflicts may at any point -not just during initial network configuration.

In this paper, we investigate the task of performing duplicate address detection when otherwise independent OLSR networks merge. We benefit from the information already exchanged by OLSR, and identify a number of mechanisms through which a node may detect a conflict between the address assigned to one of its interfaces, and an address assigned to an interface on another node. The mechanisms proposed are, thus, entirely passive, creating no additional information exchange on the network.

I. INTRODUCTION

A Mobile Ad hoc NETwork (MANET) is a collection of independant nodes, communicating over a wireless medium, whereby they form a multi-hop connected network with no assumptions of an a-priori network infrastructure. Due to the nature of the communications interfaces, protocols governing the connectivity and operation of such MANETs must be designed such that they restrict the amount of information exchange required between the nodes -in other words: the available bandwidth within the MANET should as far as possible be preserved for data communication. Thus, routing protocols for MANETs should be designed with minimal control-traffic overhead as a key criteria. An additional constraint on MANET routing protocols is, that nodes in a MANET may move freely, thus dynamically changing the topology of the network. As such, a MANET routing protocol must also satisfy the requirement of being able to respond to potentially frequently changing topologies -while still aim to minimize the information exchange.

A. The Optimized Link-State Routing Protocol

A premiere routing protocols for MANETs is the Optimized Link-State Routing protocol, OLSR [START_REF] Clausen | Rfc 3626: The optimized link-state routing protocol[END_REF]. Designed for low-bandwidth high-dynamics networks, OLSR employs periodic optimized flooding of link-state information using multi-point relays [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF]. Additionally, OLSR employs partial link-state information, ensuring that all destinations, but only a subset of links sufficient to ensure shortest-paths, are known by all nodes in the OLSR network.

In this section, we will expose attributes of OLSR, relevant for performing duplicate address detection in case two or more OLSR-networks merge. Thus, the three relevant messages, exchanged between OLSR nodes, are briefly described below. The information exchanged in these messages will be employed in section II.

1) HELLO messages: HELLO messages are employed by OLSR to detect local link-state changes and perform bidirectionally checks of links, and are thus exchanged between neighbor nodes only. A node will, periodically, generate and transmit a HELLO message, containing three lists: a set of neighbor node interfaces which have been "heard", but where bidirectionally hasn't yet been confirmed (status: ASYM), a set of neighbor node interfaces with which bidirectionally has been confirmed (status: SYM) and a list of neighbor nodes which are designated as multi-point relays (status: MPR). The MPR designation implies (for the purpose of this paper) two things: that the link to an MPR designated node is symmetric (i.e. the MPR nodes form a subset of the SYM nodes), and that the MPR node will generate and diffuse link-state information advertising the link between themselves (the MPR) and the node which selected it (the MPR selector).

2) TC messages: TC messages in OLSR are the functional equivalent of OSPF LSA-messages in that they diffuse link-state information throughout the network. Thus, an MPR node will periodically generate a TCmessage, in which it lists its MPR selectors. Since all nodes will select MPRs from among their symmetric neighbors, all nodes -as well as the links nodes and their MPRs -will be diffused throughout the net. Since TC messages are diffused periodically, a sequence-number is included in each TC message, allowing recipients to determine which of two TCs from the same node is the most recent.

3) MID messages: In OLSR networks, nodes may have multiple interfaces, each with a distinct address, participating in the MANET. Such nodes with multiple interfaces will, periodically, generate MID messages and diffuse to the entire network, listing the set of interface addresses which participate in the OLSR network.

B. Duplicate Address Detection in OLSR networks

Typically, addresses are assigned in ways which (try to) ensure uniqueness: no two interfaces within the same network should carry the same address. In traditional, wired, networks this has been ensured by state-full centralized servers [START_REF] Droms | Rfc 2131: Dynamic host configuration protocol[END_REF] or through stateless autoconfiguration [START_REF] Thomson | Rfc 2462: Ipv6 stateless address autoconfiguration[END_REF] -the former assuming that a centralized server is always present and reachable in the network, the latter that all interfaces in the network share a broadcast/multicast link, over which they are reachable and able to participate in a distributed address assignment algorithm.

In an OLSR network, these approaches fail: no centralized entity can be assumed -indeed, is contrary to the definition of a manet -and even if one was present, mobility and the potentially fragile nature of radio-links would imply that this centralized entity could be reached by all interfaces at all times. Similarly, the requirement that interfaces share a broadcast/multicast link fails: an OLSR promotes multi-hop communication through the deployment of a routing protocol among the nodes -which depends on interfaces already having uniquely configured address in order to operate.

Several proposals for initial address configuration exist [START_REF] Clausen | A simple address autoconfiguration mechanism for olsr[END_REF], [START_REF] Mase | No overhead autoconfiguration olsr[END_REF] etc., providing different ways for nodes within an OLSR network to initially acquire unique addresses. A common thing for these proposals is, however, that the nodes acquiring address must form a multi-hop connected network.

However with OLSR networks being inherently mobile, network partitioning, where a set of nodes loose connectivity from the rest of the nodes, and network merger of formerly independent or partitioned networks may occur. In the situation where two network merge, there is a non-zero probability that nodes in the two networks may have configured their interfaces with the same addresses -or more precisely, there's no guarantee that network interfaces across the two networks have unique addresses. Thus, as a supplement to a mechanism ensuring initial uniqueness of interface addresses, a mechanism is required to ensure that interface address uniqueness is preserved in the face of network mergers.

The purpose of this paper is to present ways in which an OLSR node can detect address conflicts in the case where already configured OLSR networks merge. More specifically, we present ways in which a node can detect if an address, currently assigned to one of its own interfaces, is concurrently used on another interface in the network. We note, that the approaches taken for detection of duplicate addresses is completely passive: no additional information exchange is required between the nodes -all that is required is for the nodes participating in the network to be running OLSR, and for the duplicate address detection mechanism to have access to the internal state of the OLSR routing daemon.

C. Paper Outline

The remainder of this paper is organized as follows: section II describes the different mechanisms, already present in OLSR, which can be exploited to provide the ability to detect when an address is concurrently assigned to more than one interface. Specifically, the methods do not incur any additional information exchange and, for all but one do not incur any additional storage requirements to the OLSR nodes. Once an address conflict is determined, conflict resolution can be performed, with the goal of removing any conflicting address assignments. Some additional considerations regarding the applicability and scope of the discussed mechanisms are included in section III. Section IV how resolving a conflict, once detected, can be performed, followed by section V, which concludes this paper.

II. PERFORMING DAD IN OLSR NETWORKS

In this section, we present different mechanisms through which an OLSR node can detect if the address, currently assigned to one of its interfaces, is concurrently being used by an interface on another node. We note that none of the mechanisms presented here impose any additional information exchange between nodes beyond what is already performed by OLSR.

The duplicate address detection mechanisms are based on inspecting received OLSR control messages, as well as the receiving nodes state, to determine if an address on the receiving node is duplicated elsewhere in the network. More precisely, a node can inspect a received message to detect (i) if the message appears to have been sent from an interface the receiving node or (ii) if the message contains information about interfaces of the receiving node. In either of these cases, the information contained in the received OLSR message is compared to the state recorded in the receiving node, allowing the receiving node to detect a potential duplicate of one of its addresses.

With this in mind, the following subsections will inspect the three OLSR message types described briefly in section I-A: HELLO, TC and MID-messages. In the illustrations in this section, nodes are identified by addresses "A", "B", "C", ... If an address is duplicated, two nodes will appear in the figure with the same address. The node being the center from which the mechanism is described is indicated by a double-circle.

A. HELLO: Mismatching neighborhood

A node which receives a HELLO message on one of its interfaces, where the HELLO message appears to come from the node itself, a potential address duplication may incur: since HELLO messages are never forwarded in OLSR, an OLSR node should not receive a copy of a HELLO message with any of its own interface-addresses as originators 1 . Should a node receive a HELLO message with one of its own interface addresses listed as originator, there's a likely collision: two adjacent nodes have interfaces configured with the same address, as illustrated in figure 1. From the point of view of the leftmost node "A" (indicated by a double-circle), this can be confirmed by inspecting the neighborhood being advertised in the HELLO message: the HELLO message will include nodes B and C as neighbors, whereas neither are neighbors of the node receiving the HELLO. Thus, it can be detected by the leftmost node in figure 1 that one of its interface addresses is also being used elsewhere in the network.

B. HELLO: MPR Selection Abnormality

A second intuitive diagnostic on HELLO messages could be to consider MPR selection: an MPR node must be selected from among neighbors with which a symmetric link exist. Thus, a hypothesis could be that if the leftmost node "A" on figure 2, which has a recorded asymmetric link with node "B", receives a HELLO from node B declaring it as MPR, then a conflict exists as indicated: a second node "A'", adjacent to "B", has the same address as "A". This would, however, be a false conclusion. On establishment of the link between "A" and "B" node "A" receives a HELLO from "B", bringing node "A" to see the link to "B" as ASYM. In the next HELLO from node "A", node "B" will see its own address listed and conclude that the link is symmetric. Node "B" may, then, select "A" as MPR and include this selection in the next HELLO message. In this way, node "A" will receive an MPR selection from a node with which it has only an asymmetric link, without this being an indication of address conflicts in the network.

C. TC: Sequence Number Mismatch

If a node, "A", receives a TC message with the address of one of its own interfaces listed as originator address address and with a sequence number very different from the sequence number that node "A" currently is using, this can be an indication that an interface of node "A" is concurrently being assigned to another interface in the OLSR network. This situation is illustrated in figure 3 A Symetric Link Asymetric Link Transmission Node detects duplicate TC {seq. number very different from X} A Seq. = X Fig. 3. Node A detects an address duplication as it receives a TC message with its own address listed as originator address and with a sequence number that is very different from the current sequence numbers it uses.

D. TC: Link-State Mismatch

If a node, "A", receives a TC message, declaring the address of one of node "A"'s interfaces as MPR selector, the originator of that TC-message must be a direct neighbor of node "A". Considering, however, the situation illustrated in figure 4: the rightmost node "A" selects node "C" as MPR, and thus node "C" will advertise "A" in its TC messages. From the point of view of the leftmost node "A", an address conflict will be detected thus: a TC will be received from node "C", advertising a link between node "C" and node "A", yet in the leftmost node "A" no such link exists.

E. MID: Interface Mismatch

The final message type in OLSR is MID messages, through which a node with multiple interfaces declares its interface configuration to the other nodes in the network. If a node, "A", receives a MID messages, in which the address of one of its own interfaces is listed, the remaining addresses listed in the MID must also belong to node "A". Alternatively, if a node, "A", receives an MID-message, containing one or more addresses, belonging to node "A" but also listing addresses which do not belong to node "A", then at least one address is assigned to more than one node. This is illustrated in figure 5, in which one node has the addresses "A", "A1" and "A2, whereas the other node has the addresses "A", "A3" and "A4".

III. APPLICABILITY AND SCOPE

Passive mechanisms, such as those presented in this paper, are based on the monitoring of the control messages of the routing protocol. These aim at detecting anomalies in this traffic, that can hint to possible address collisions. However, this approach has a few shortcomings, both in terms of false alarms and in terms undetected duplications. In the rare case of a totally symmetric MANET, such as the one as depicted in figure 6, routing message monitoring may not be sufficient to detect the duplicate addresses. In figure 6, the duplicate nodes cannot detect the collision with each other since the routing messages produced by the left side of the network are identical to the routing messages produced by the right side of the network (because the topology is symmetric). Sequence number mismatch monitoring may help in this case, but it may also crash the network further, as such mismatches may invalidate the link state information with each TC transmission, alternatively from the right side and the left side of the network. Another example is with the sequence number mechanism. This technique is not completely reliable in order to detect duplicate addresses, as delayed delivery can cause an outdated control message that is received to be possibly wrongly interpreted as a case of address duplication. This category of false alarm is more likely to be caused by TC or MID messages rather than HELLO messages, as they feature only one hop scope, suppressing delays due to forwarding.

Such cases challenge the passive approach to DAD. Therefore other techniques maybe employed in addition to passive mechanisms in order to increase the reliability of the DAD. These techniques can be called active, or semi-passive, depending on how much additional overhead is produced by the mechanism.

Semi-passive techniques involve deeper analysis of the link state information traffic, such as tracking and pro-cessing the history of such traffic, in order to prevent errors. However, these techniques come with much more processing and memory needs, a fact that must be carefully evaluated.

Active techniques involve sending specific DAD information or messages, in addition to the routing control overhead. For instance, flooding a neighbor solicitation message is part of such a technique. These can be more efficient than passive waiting, but they nevertheless come with greater overhead, a fact that must also be carefully evaluated.

IV. RESOLVING DUPLICATE ADDRESS CONFLICTS

The purpose of the mechanisms, described in this paper, is to detect when two or more interfaces in the network have been configured with the same address -that a duplicate address conflict exists in the network. The logical next-step to having detected this situation is to resolve it -to reconfigure nodes such that each interface participating in the OLSR network has a network-wide unique address.

Resolving a duplicate address conflict is, functionally, orthogonal to detecting a duplicate address conflict and, depending on the specificities of the network, different mechanisms can be employed. In this section, we briefly outline a few general approaches to resolving duplicate address conflict. The objective, however, remains to remove conflicting interfaces from the OLSR network, while disrupting the network operation as little as possible.

The simplest solution, once a duplicate address conflict is detected, is for a node to simply disable the local interface(s) which are conflicting. If these interfaces then wish to enter the network again, a new initial autoconfiguration cycle must be initiated. The advantage of this method is its simplicity and fact that no lengthy election procedure must be completed before duplicate address conflicts are resolved. The disadvantage is, that when a conflict arises, all conflicting interfaces are potentially disabled without consideration to traffic (or even necessity: when two interfaces are conflicting, it suffices to disable one of them, not both).

A more elegant class of solutions to resolving a duplicate address conflict would be for the node(s) which detect a conflict to "negotiate" which interface should yield -possibly based on metrics such as active traffic flows for a given interface etc. This negotiation would take form of a broadcast of information (a "CONFLICT" message), containing necessary information for a recipient to decide if it should yield and disable a given interface, or not.

V. CONCLUSION AND FUTURE WORK

In this paper we have given an overview of the issues with duplicate address detection in OLSR networks. Us-ing the proactive nature of the routing protocol, monitoring the routing control messages allows detection of many cases of duplicate addresses in the OLSR networks. This simple passive approach has, however, some shortcomings, both in terms of false alarms and in terms of undetected duplications under some very specific network conditions with exactly-symmetric networks. Thus, while passive duplicate address detection in OLSR networks provides a simple and overhead-free mechanism for detecting a large class of duplicate address conflicts, it might be beneficial to complement passive duplicate address detection with an active mechanism -possibly combined with an active mechanism for duplicate address conflict resolution.

Fig. 1 .

 1 Fig.1. Node A detects an address duplication as it receives a HELLO message with its own address listed as originator address.

Fig. 2 .

 2 Fig.2. Node A detects an address duplication as it receives a HELLO message with its own address listed as MPR from a neighbor B with which it has no symmetric link.

Fig. 4 .

 4 Fig.4. Node A detects an address duplication as it receives a TC message with its own address listed as originator address and with listed addresses that are not in its neighborhood, or MPR selection.

Fig. 5 .Fig. 6 .

 56 Fig.5. Node A detects an address duplication as it receives an MID message with its own address listed as originator, and with listed addresses that are different from its own.

This ignores the situation where a node has two radio interfaces running OLSR on the same channel.