Thomas Clausen
email: thomas@thomasclausen.org

Ulrich Herberg
email: ulrich@herberg.name

Comparative Study of RPL-Enabled Optimized Broadcast in Wireless Sensor Networks

Recent trends have suggested convergence to Wireless Sensor Networks (WSNs) becoming 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. The current effort of this working group is development of a uni-cast routing protocol denoted RPL. RPL constructs a "DAG-like" logical structure with a single root, at which the majority of the traffic flows terminate, and assumes restrictions on network dynamics and traffic generality, in order to satisfy strict constraints on router state and processing.

This paper investigates the possibility for providing (efficient) network-wide broadcast mechanisms in WSNs, using the logical structure already provided by RPL. The aim hereof is to not impose any additional state requirements on WSN routers already running RPL. This paper presents two such broadcast mechanisms for RPL routed WSNs, and evaluates their performances. As part of this evaluation, the paper compares with MPR Flooding -an established efficient flooding optimization, widely used in MANETs.

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 as would be the case with factory set thresholds.

A. WSN Traffic Patterns

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 the devices do not make any a-priori assumptions as the 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 .

A-priori assumptions as to traffic patterns are being used as the primary justification for "in which order to optimize" algorithm development, with unicast routing of the multipointto-point kind having been the primary design target for RPL.

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

C. WSNs and the IETF

The ROLL working group of the IETF is currently developing support for IPv6 routing in WSNs. The objective of this working group is to support WSNs:

• which comprise up to thousands of WSN routers,

• where the majority of the WSN routers have very constrained in-router resources, • where the network to a large degree is "managed" by a (single or few) central "super-WSN routers", and • where handling mobility is not an explicit design criteria. For the latter of these, it is assumed that network dynamics is a consequence of rare, interfering events (say, a sensor getting crushed or running out of battery) necessitating a correction, rather than tracking continuously changing conditions such as due to mobility.

The ROLL working group aims at supporting multipoint-topoint, point-to-multipoint and point-to-point traffic patterns. The emphasis among these is traffic patterns is to optimize for multipoint-to-point traffic, to reasonably support point-tomultipoint traffic and to provide basic features for point-topoint traffic, in that order. D. IPv6 routing for WSNs: RPL RPL -the "Routing Protocol for Low Power and Lossy Networks" (RPL) [START_REF] The | RPL: Routing Protocol for Low Power and Lossy Networks[END_REF] -is an early proposal for an IPv6 routing protocol for WSNs, by the ROLL working group in the IETF. The basic construct in RPL is the DODAG -a destination oriented DAG, rooted in a "controller", in figure 1. 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 one among these as its 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 their 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 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.

1) RPL Operational Requirements: The minimal set of inrouter 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 in case the former preferred parent becomes unreachable.

RPL control 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].

2) RPL Traffic Patterns: The DODAG constructed by RPL is intended to serve as a sort of "backbone topology" for carrying data traffic.

"Upward paths" or "multipoint-to-point paths" from the sensors towards the controller are supported by installing the "preferred parent" in each WSN router as the next hop on the path towards the DODAG root. The DODAG root may in its DIO messages have advertised a set of destination prefixes, to which it provides connectivity. These prefixes can be used to populate the routing table in the WSN routers in the network, or a default-route via the preferred parent and the DODAG root can be instilled.

"Downward paths" or "point-to-single-sensor paths" are supported by having WSN routers, which wish to be reachable, issue Destination Advertisement Object (DAO) messages. These propagate via parents towards the DODAG root, and describe which prefixes belong to, and thus can be reached via, which WSN router. Each intermediate WSN router, forwarding a DAO message towards the root, add its address to a reverse routing stack in the DAO message, thereby providing the DODAG root with the ability to do source routing for reaching destinations in the WSN.

"Sensor-to-sensor paths" 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.

E. Problem Statement

RPL, as currently specified in [START_REF] The | RPL: Routing Protocol for Low Power and Lossy Networks[END_REF], discusses and supports only unicast traffic, albeit two different variations hereof: sensor-to-controller traffic is supported by regular hop-byhop routing, whereas controller-to-sensor unicast traffic is supported by way of source routing. Sensor-to-sensor routing is supported by way of combining these two: hop-by-hop routing to the "DODAG root", and source routing from the DODAG root to the destination sensor.

Thus, RPL supports, at least functionally though not optimally, the WSN traffic patterns identified in section I-A. RPL does, however, not explicitly provide support for any form of "optimized broadcasting" -delivery of the same data packet to all routers in the WSN.

One important application of broadcasting in a WSN is for a controller to request / trigger that all sensors in the WSN transmit their sensor information -e.g. to verify if an extreme/alarming condition, signaled by a single sensor, is confirmed by other sensors in the WSN.

While such a "broadcast" could be accomplished by the DODAG root performing "bulk-unicast" to all sensors in the network, this is hardly efficient. The two "classic" reasons for why this is inefficient apply: (i) when performing broadcasting via bulk-unicast, the same data is being transmitted repeatedly across the same links (especially, over links close to the source, thus creating potentially congested areas), and (ii) it requires that the source of the bulk-unicast knows all possible recipients for the broadcast.

In the case of an RPL-routed WSN, a third reason applies: in order for the DODAG root to be able to reach all sensors by way of an unicast, all WSN routers are required to generate DAO messages -and the DODAG root is required to maintain explicit paths to all sensors, for use as source-routes.

Thus, this paper investigates ways of providing a reasonable optimized broadcast capability for an RPL routed network.

F. Paper Outline

The remainder of this paper is organized as follows: section II suggests two different mechanisms for, by way of using the data structures and topologies already maintained by RPL, providing also support for broadcast traffic in a WSN, and also briefly presents MPR Flooding -an optimized broadcast mechanism, widely employed in wireless ad hoc networksas a point of reference and comparison. Section III provides a comparative performance study of the suggested broadcast mechanisms. Section IV concludes this paper.

II. DATA BROADCASTING IN RPL

This section suggests two mechanisms for exploiting the DODAG, as constructed by RPL, in order to undertake betterthan-classic-flooding for WSN-wide broadcasting. The fundamental hypothesis for these mechanisms is that all broadcast operations 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 transited to the root using unicast, from where the DODAG root will launch the broadcast operation -this is similar to the basic mechanism for sensorto-sensor unicast in [START_REF] The | RPL: Routing Protocol for Low Power and Lossy Networks[END_REF], wherein traffic from the source sensor transits to the DODAG root, for relaying to the destination sensor.

A. Classic Flooding (CF)

A common baseline for broadcast operations is that of classic flooding: each router relays a broadcast packet upon its first receipt by that router; subsequent receipts of the same packet are suppressed and do not cause retransmissions. This has to its merit that no control traffic is required -however also entails (i) that each data packet must be uniquely identifiable (commonly ensured by embedding a unique sequence number in each broadcast packet, emitted by a given source), (ii) that each router must maintain information (state) for each already received and relayed data packet so as to enable suppression of duplicates, and (iii) each data packet is retransmitted by each router in the network -often with a large degree of redundant transmissions as consequence.

Redundant retransmissions causes increased battery drain, both when transmitting and receiving (and discarding) the redundant packets, and increases contention on the wireless media, increasing the probability of data loss due to collisions.

B. MultiPoint Relay Flooding (MPRF)

A common improvement over Classic Flooding is for each router to select and designate a subset of its neighbors (Mul-tiPoint Relays -MPRs [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF]) for relaying broadcast transmissions, thereby reducing the number of redundant retransmissions of each packet. This has been shown to offer dramatic reductions in the network load (fewer transmissions), as well as a dramatic reduction in data loss due to collisions [START_REF] Clausen | Investigating broadcast performance in Mobile Ad-hoc Networks[END_REF].

In order for MPRF to work, a router must select its MPRs such that a message relayed by these MPRs will be received by all routers 2 hops away, as illustrated in figure 2. To this end, each router must maintain, at a minimum, state describing both its neighbor routers, as well as its 2-hop neighbors ("neighbor routers of neighbors"). MPRF is a common approach in wireless ad hoc networks, where it is used e.g. for network-wide broadcast of routing protocol control traffic by [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF], [START_REF] Clausen | SPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF] and [START_REF] Clausen | The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] -as well as for network-wide data broadcast [START_REF] Macker | Simplified Multicast Forwarding[END_REF].

C. Parent Flooding (PF)

Observing that a broadcast is always launched "at the root", RPL lends itself to a first and simple broadcast optimization, restricting a RPL router to retransmit only broadcast packets received from a "parent". Logically, the basic performance hereof should be similar to that of classic flooding: with the broadcast operation initiated from the DODAG root, each router will retransmit the packet upon receipt from a parent. PF does not require any additional control traffic over that which is caused by RPL. PF may apply identification of each broadcast packet, and maintenance of state allowing elimination of duplicate packets, in order to avoid multiple retransmissions of the same packet.

D. Preferred Parent Flooding (PPF)

In order to not incur any additional in-router state requirements for detecting and suppressing retransmission of duplicate packets, 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 accomplishes this.

III. RPL BROADCAST PERFORMANCE STUDY

In order to explore the performance of RPL-enabled broadcast, simulations of MPRF, PF and PPF have been performed using the Ns2 network simulator. The RPL protocol itself, providing the basic DODAG, used by PF and PPF, has been implemented in Java according to [START_REF] The | RPL: Routing Protocol for Low Power and Lossy Networks[END_REF]. The specific scenario settings are detailed in table I; for each datapoint in the results presented in this section, 10 different scenarios -each conforming to the same abstract scenario description -have been simulated, with the results presented being the average from these ten runs. For the purpose of this study, only a single RPL instance with a single DODAG is considered, and only in a static network. At the beginning of the simulation, only the root (which is the WSN router with the ID of 0) starts transmitting DIOs. Upon successful convergence of the DODAG, the root starts sending broadcast data with a data rate of 1280 bytes/s (64 byte long packets, sent every 50 ms). For MPRF, the neighborhood discovery and MPR selection part of the Java based OLSRv2 implementation [START_REF] Herberg | JOLSRv2 -An OLSRv2 implementation in Java[END_REF] has been used (TC message generation disabled).

In the following comparison, PF is analyzed in two versions, with and without duplicate packet detection (PF+DD). PPF never applies duplicate packet detection, and MPR always uses it.

A. Basic Results

Figure 3 depicts the maximum and the average rank of the DODAG, where the number represents the distance of a WSN router to the root in terms of hops (i.e. the maximum rank represents the diameter of the network, and the average rank represents the average over all WSN routers). The maximum and average ranks grow logarithmically with the number of WSN routers in the network.

Figure 4 depicts the average number of parents of each WSN router in the DODAG. Keeping the density of the network constant with increasing number of WSN routers, the average number of parents grows logarithmically. Figure 6 depicts the delivery ratio of broadcast packets. The delivery ratio for MPRF is observed to be higher than both PF and PPF, and furthermore to not be significantly changing when scaling the network (note that the density of the network stays constant in the simulations). This is hardly surprising, considering the lower collision ratio (see figure 5) of MPRF. PF+DD has a higher delivery ratio than 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 (non-preferred) parents. Figure 8 shows the average end-to-end delay for data traffic from the root to every WSN router in the network. MPRF incurs the lowest delay of the four protocols, while PPF incurs a much lower delay than does PF, and a slightly lower than does PF+DD.

B. PPF with Jitter

In the results presented above, data traffic has been promptly forwarded by each WSN router, without delay. As has been shown in [START_REF] Clausen | The Optimized Link State Routing Protocol, Evaluation through Experiments and Simulation[END_REF], [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF], adding a random jitter before retransmitting a broadcast packet can significantly reduce the number of collisions and, therefore, increase the delivery ratio for broadcast packets. In the following, the effect of adding jitter to PPF is investigated.

Figure 9 depicts the collision ratio of frames when using no jitter, and a random jitter uniformly distributed between 0 and 500 ms. With jitter, the collision ratio is much lower than it is As a consequence of the lower collision ratio, the delivery ratio of PPF with jitter is higher than it is without, as depicted in figure 10. Comparing to figure 6, the delivery ratio of PPF still remains consistently below that of MPRF. The drawback of using jitter is a higher end-to-end delay of packets, as depicted in figure 11. With jitter, the delay is considerably higher than it is without. This paper has presented a comparative study of broadcast mechanisms for RPL routed wireless sensor networks. Two broadcast mechanisms, using the rooted DAG-like logical structure, maintained by the uni-cast routing protocol RPL, are introduced, and their performance studied. These two broadcast mechanisms, denoted "Parent Flooding" (PF) and "Preferred Parent Flooding" (PPF) adhere to the "rootoriented" concept of RPL, in that all broadcast operations are to be initiated by the root of the DAG.

PF and PPF are studied and compared by way of network simulations -and as a point of comparison, MPR Flooding (MPRF), known from wireless ad hoc networks, is also subjected to the same network scenarios in the simulator. The simulations have shown that, not unexpectedly, PPF is more efficient than PF without duplicate packet detection (DD). When PF is used with a DD mechanism, the delivery ratio is higher than PPF due to redundant retransmissions; however, this redundancy naturally leads to a higher overhead on the radio channel. Furthermore, PPF does not require maintenance of extra state for storing packet sequence numbers for the DD mechanism.

MPRF, however, remains much more efficient than PPF (and, obviously, PF), obtaining both a consistently lower bandwidth consumption and a consistently higher data delivery rate. On the potential downside, however MPRF requires additional state in each WSN router for duplicate packet suppression.

Compared to PPF, which requires only RPL signaling, MPRF also necessitates a neighborhood discovery mechanism for selecting and designating MPRs -the price of a more efficient broadcast protocol.

Figure 1 .

 1 Figure 1. RPL Basic Construct: DODAGs

Figure 2 .

 2 Figure 2. (a) Classic flooding and (b) MPR Flooding MPRF, as CF, requires identification of each broadcast packet, and maintenance of state allowing elimination of duplicate packets.MPRF is a common approach in wireless ad hoc networks, where it is used e.g. for network-wide broadcast of routing protocol control traffic by[START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF],[START_REF] Clausen | SPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF] and[START_REF] Clausen | The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] -as well as for network-wide data broadcast[START_REF] Macker | Simplified Multicast Forwarding[END_REF].

Figure 3 .

 3 Figure 3. Maximum and average rank of the DODAG

Figure 4 .Figure 5 Figure 5 .

 455 Figure 4. Average number of parents per WSN router in a DODAG

Figure 6 .Figure 7 .

 67 Figure 6. Delivery ratio

Figure 8 .Figure 9 .

 89 Figure 8. Average delay

Figure 10 .

 10 Figure 10. Delivery ratio of PPF with jitter

Figure 11 .

 11 Figure 11. Average delay of PPF with jitter

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


Emmanuel Baccelli
email: emmanuel.baccelli@inria.fr

Thomas Clausen
email: thomas@thomasclausen.org

IPv6 Operation for WAVE -Wireless Access in Vehicular Environments

The IEEE WAVE protocol suite is providing communications services to applications in vehicular networks, by way of promising support for two protocol stacks: the Wave Short Message Protocol (WSMP) and IPv6. While WSMP is developed within the IEEE 1609 family of standards, the authors of this paper assert, that considerations for IPv6 operation for WAVE are less developed, and several issues are left unaddressed by the current IEEE 1609 specifications. This paper reviews these issues and analyzes the main challenges in providing proper IPv6 operation for WAVE networks.

I. INTRODUCTION

The IEEE is currently undertaking standardization of a protocol suite for Wireless Access in Vehicular Environments (WAVE), with the objective of providing vehicles and pedestrians with the ability to communicate with each other and with road-side infrastructure. Possible applications hereof include emergency warning systems, cooperative cruise control and collision warning, as well as toll and parking fee collection. This protocol suite is developed in the IEEE 1609 working group, documented in [START_REF]The Wireless Access in Vehicular Environments (WAVE) Working Group of the Intelligent Transport Systems (ITS) Committee[END_REF], [START_REF]Draft Standard for Wireless Access in Vehicular Environments (WAVE) -Remote Management Services[END_REF], [START_REF]Draft Standard for Wireless Access in Vehicular Environments (WAVE) -Security Services for Applications and Management Messages[END_REF], [START_REF]Draft Standard for Wireless Access in Vehicular Environments (WAVE) -Networking Services[END_REF], [START_REF]IEEE P1609.4: Draft Standard for Wireless Access in Vehicular Environments (WAVE) -Multi-Channel Operation[END_REF], [START_REF][END_REF] and intended for operation over Dedicated Short-Range Communications (DSRC) -a set of wireless communications channels, dedicated for vehicular networking at 5.9GHz.

WAVE is providing communications services to applications, by way of promising support for two protocol stacks, the Wave Short Message Protocol (WSMP) and IPv6, as shown in figure 1. While WSMP is developed within the IEEE 1609 family of standards [START_REF]Draft Standard for Wireless Access in Vehicular Environments (WAVE) -Networking Services[END_REF], considerations for operation of IPv6 for WAVE are less developed. The WAVE architecture specification [START_REF]The Wireless Access in Vehicular Environments (WAVE) Working Group of the Intelligent Transport Systems (ITS) Committee[END_REF] makes reference to the IETF 1 specification of IPv6 [START_REF] Hinden | RFC2460: Internet Protocol, Version 6 (IPv6) Specification[END_REF] and makes minimal observations regarding the use of IPv6 addresses, but no further specific recommendations as to IPv6 operation for WAVE are provided.

The authors of this paper assert that, while the IEEE 1609 family of specifications provides a set of necessary considerations for IPv6 operation over WAVE, these considerations are not sufficient for proper and correct IPv6 operation in this environment. This paper thus provides an analysis of IPv6 operation, as described in the IEEE 1609 family of specifications for WAVE networks, identifies where IPv6 operation for WAVE networks is underspecified, and presents a set of 1 http://www.ietf.org additional recommendations enabling proper IPv6 operation for WAVE networks. While IPv6, as defined in [START_REF] Hinden | RFC2460: Internet Protocol, Version 6 (IPv6) Specification[END_REF], principally concerns the data frame layout (header format, header extensibility, rules governing header construction and processing etc.), IPv6 operation implies operation of a set of basic protocols at the network layer, including NDP [START_REF] Narten | RFC2461: Neigh-bor Discovery for IP Version 6 (IPv6)[END_REF], stateless address autoconfiguration [START_REF] Thomson | RFC2462: IPv6 state-less address autoconfiguration[END_REF]. The IPv6 protocol stack provides additional protocols at other layers, such as the transport layer and the application layer. Most of these protocols make certain assumptions about properties of an underlying link model for their proper operation, and assume certain relationships between assigned IP addresses and communications ability across the underlying data link layer. This is discussed in details in section II, elaborating on the link-model presented by a WAVE system, and presenting IPv6 network layer considerations for WAVE, resulting from the properties of that link-model. This paper , then, in section III presents additional issues for WAVE operation in an IP networking context, including "pseudonymity", transport and application layer challenges. This paper is concluded in section IV.

II. WAVE NETWORK LAYER CHALLENGES WITH THE IPV6 PROTOCOL STACK

IPv6 operation is, beyond the use of the IPv6 frame format [START_REF] Hinden | RFC2460: Internet Protocol, Version 6 (IPv6) Specification[END_REF] on the network layer, generally understood to also imply assumptions of a specific and well-defined link-model reflected in a well-defined addressing model [START_REF] Hinden | RFC3513: Internet Protocol Version 6 (IPv6) Addressing Architecture[END_REF], and operation of a set of supporting protocols [START_REF] Narten | RFC2461: Neigh-bor Discovery for IP Version 6 (IPv6)[END_REF], [START_REF] Thomson | RFC2462: IPv6 state-less address autoconfiguration[END_REF].

The IPv6 addressing model defines different address families (e.g., Link Local or Global addresses), with associated properties. This enables applications or protocols to have certain expectations of communication abilities, corresponding to the addresses they use. For example, an application using a Global address as destination address expects the network to be able to ensure multi-hop communication to that destination address. The network, then, expects such addresses to be assigned in a way such that by inspection of the address, it can be determined if the destination is reachable directly, or reachable only via a (and, in that case, also via which) router.

In an IPv6 network, the supporting Neighbor Discovery Protocol for stateless autoconfiguration (of addresses, default routers etc) and duplicate address detection [START_REF] Narten | RFC2461: Neigh-bor Discovery for IP Version 6 (IPv6)[END_REF], [START_REF] Thomson | RFC2462: IPv6 state-less address autoconfiguration[END_REF], is assumed to be running -and that protocol expects specific link model and addressing model.

Thus, IPv6 operation entails (i) using the IPv6 frame format, (ii) certain assumptions of a well-defined link-model, reflected in an (iii) address model, and (iv) proper operation of NDP. This is detailed further in the following sections.

A. IPv6 Link Model [START_REF] Thaler | RFC4903: Multilink Subnet Issues[END_REF] points out that network protocols and applications are designed with specific assumptions on the nature of an IP link, illustrated in figure 2 and summarized as follows:

• all hosts (H) with network interfaces configured with addresses from within the same prefix p::, and with the same prefix p:: assigned to the interfaces, can communicate directly with one another; i.e.: -IPv6 datagrams are not forwarded at the network layer when communicating between interfaces which are configured with addresses from the same prefix; hence hop-limit in IPv6 datagrams are not decremented when communicating between interfaces which are configured with addresses from within the same prefix, and; multicast/broadcast IPv6 datagrams with a hop-limit of 1 are delivered to all interfaces within the same subnet (assuming the scheduled datagram transmission succeeds).

• link-local multicasts and broadcasts are received by all interfaces configured with addresses from within the same prefix without forwarding. The IPv6 Link Model, in figure 2, axiomatically assumes that neighbor relationships are symmetric: if communication from air interface A to air interface B is possible in one hop, then communication in the reverse direction is also possible -in other words, connectivity between neighbor interfaces is assumed symmetric.

An even shorter summary of the IPv6 link model is to say that an IPv6 link looks like an Ethernet.

B. IPv6 Addressing Model, Address Scopes and Uniqueness

As described in section II-A, the notion of an "IPv6 link" is tied with that of an IPv6 subnet prefix: all interfaces which are configured with the same subnet prefix are considered to be on the same IP link and, thus, for communication between nodes on the same subnet, no forwarding is required and no decrement of TTL/hop-limit is performed. In addition to this relationship between link and prefix, IPv6 introduces address scopes -Link-Local and Global -and mechanisms by which addresses are constructed using Interface IDs.

A Link-Local address is valid for communication with a device on the same link: an IPv6 datagram with a Link-Local source or destination address is not to be forwarded on the network layer, but is to be received by a destination on the same link -or not received at all. The only requirement for an unicast Link-Local address to be useful is, thus, that it is unique on the local link; the same Link-Local address may well be in use on another, disjoint, link, however as IPv6 datagrams with Link-Local addresses are never to be forwarded, no ambiguities exist.

A Global address is valid for communication beyond the local link: an IPv6 datagram with a Global source and destination address can be forwarded on the network layer and, thus, be received by a destination on the same or on a different link -or not received at all. For an unicast Global address to be useful, it must, thus, be unique across the entire network.

It is important that these address uniqueness requirements are universally satisfied. This is ensured in IPv6 by having an interface detect when it connects to a link (typically, by way of a discrete link-layer trigger), upon which it constructs a Link-Local IPv6 address by concatenating the Link-Local Prefix (FE80::/10) with an Interface ID, typically derived from the MAC address of that interface. Duplicate Address Detection (DAD) [START_REF] Thomson | RFC2462: IPv6 state-less address autoconfiguration[END_REF] is then performed, to verify that this address is not already in use on the link. DAD employs Link-Local Multicast, interrogating all other interfaces on the link as to if they are already using that address, by way of Neighbor Solicitation (NS) messages. Absent a reply to this interrogation -by way of Neighbor Advertisement (NA) messages -the address is assumed unique on the link and henceforth used. As all Link-Local addresses share the same Prefix (FE80::/10), this DAD procedure in reality verifies that the chosen Interface ID is unique across the link.

Global addresses are constructed by concatenating the Global prefix of a link with the Interface ID of an interface, verified to be unique during the configuration procedure for Link-Local addresses. The Global Prefix is obtained from a router on the link2 , by way of Router Solicitation / Router Advertisement messages [START_REF] Narten | RFC2461: Neigh-bor Discovery for IP Version 6 (IPv6)[END_REF]. It follows that uniqueness of a Global address for an interface relies on (i) the Interface ID being unique on the link to which the interface is connected, and (ii) unique prefixes being delegated to routers. It follows, then, that a Global address is valid only as long as that interface is connected to the link on which the router providing the Global prefix is present.

An interface must also detect when it disconnects from a link (typically also by way of a discrete link-layer trigger), upon which it must cease to use the previously configured addresses. Thus, in IPv6, a link describes a well-determined set of network interfaces, all able to communicate directly with each other without forwarding, and with all interfaces in a single (link-local multicast) transmission be able to reach all other interfaces on the same link. This set of network interfaces is maintained by way of explicit and discrete signals, allowing an interface to detect its connection to a given link.

A summary description of the IP addressing model is therefore, that (i) addresses are of a specific validity scopes, global or local, where (ii) within validity scope of an address, it must be used by no more than one interface, and (iii) an address of global validity scope assigned to an interface must be topologically correct, i.e., it must match the Global prefix provided by the router on the IP link to which the interface connects.

C. IPv6 Network Layer Considerations Regarding WAVE

As indicated in section I, the IEEE 1609 family of specifications present a minimal set of considerations for IPv6 operation for vehicular networks. Devices in vehicular networks are separated into On-Board Units (OBUs) and Road-Side Units (RSUs), with the latter providing, as needed, infrastructure and configuration support for the former. With respect to IPv6 operation in such networks, the IEEE 1609 family of specifications simply state that:

• IPv6 is provided as a data plane protocol, and that the "standard IPv6 protocol" is used; • Link-Local addresses are derived by the device, are not globally unique and are not usable for routing; • NDP [START_REF] Narten | RFC2461: Neigh-bor Discovery for IP Version 6 (IPv6)[END_REF], otherwise used for populating the neighbor cache, is asserted to generate a substantial and unacceptable amount of traffic, and thus other means for populating the neighbor cache are employed (using ICMPv6 packets for instance); • NDP is, however, not excluded for "cases where it might be needed".

D. WAVE air Interface "Link Model"

The air interfaces of a WAVE system, and the "links" to which they attach, have different characteristics from those described in section II-A, and are therefore detailed in this section. The resulting "WAVE link model" does not provide for a direct mapping to the IPv6 link model, thus considerations for operating IPv6 over this "WAVE link model" are detailed in section II-E.

Symmetric to the IPv6 Link Model in figure 2, figure 3 illustrates the relationship between WAVE air interfaces, and serve for elaborating the "WAVE link model" in the discussions in this section. Each air interface is a (radio) broadcast interface, able to establish a direct link layer communication with air interfaces which are within its coverage area. In figure 3, this coverage area is approximated by a simple disc of fixed radius (light gray discs) -in the real world, both the shape and size of the coverage area is variable as a function of the interface, interference from the environment etc. Referring to figure 3 if, e.g., if N3 transmits, then this transmission may be received by N2 and N4, but not by N1 and N5. This implies that, e.g., N3 and N4 -despite being neighbors and on the same "link"do not share the same view of which other nodes are neighbors and on the same "link": N3 considers that it is on the same "link" as N2 and N4, whereas N4 considers itself to be on the same "link" as N3 and N5.

Thus, a set of air interfaces within a region -even if using the same channels and modulation -may not all be able to communicate to all other air interfaces, without intermediate relaying. A link-local multicast transmission from one air interface may not (even disregarding losses) be able to be received by all other air interfaces; indeed, a multicast transmission from one air interface may not be able to reach the same set of air interfaces as would a multicast transmission from its closest neighbor air interface. This is the case in figure 3, where no two air interfaces can directly transmit to the same set of other air interfaces.

An air interface has an "interference area" which may be greater than its coverage area, i.e. a transmission by N3 in figure 3 will, as indicated above, be correctly received by the interfaces N2 and N4. At the same time, however, this transmission may be propagating to interfaces of N1 and N5 where, while the transmission can not be correctly decoded, it can be detected, and cause interference with other transmissions which could otherwise be correctly received over the air interfaces of N1 and N5 (such as transmissions from N0 and N6). Figure 4 illustrates a situation where, for some reason (powerful transmitter, environmental interference, large antenna, ...), the air interface of N1 has a large enough coverage area for its transmissions to be received and correctly decoded by the air interface N2. The air interface of N2, on the other hand, has a much smaller coverage radius, such that transmissions from the air interface of N2 can not be received and correctly decoded at the air interface of N1. Thus asymmetric -or more precisely, unidirectional -connectivity between the air interface of N1 and the air interface of N2 exists: N2 sees N1 as a neighbor (since the air interface N2 can receive transmissions from the air interface of N1), whereas N1 does see N2 as a neighbor (since the air interface of N1 can not receive transmissions from the air interface of N2).

A vehicular network, naturally, represents a dynamic topology: OBUs move relatively to each other and to RSUs. The resulting network is a highly dynamic graph, where the neighborhood of an air interface is also dynamic and varies over time -due to mobility, and due to changing environmental factors: two air interfaces which were not in communications range a moment ago may become neighbors, and vice-versa.

Thus, neighboring air interfaces may experience distinctly different neighborhoods, may not even agree on if they are or are not neighbors, and may at any time become, or cease to be, neighbors.

Finally, as the set of air interfaces "on a link" are communicating via radio waves rather than electrical wires, there are no implicit physical signals, allowing an air interface to detect its association or disassociation with a given set of other air interfaces "on the same link". And the set of air interfaces "on a link" may be subject to constant and rapid change. In a certain way, it is tempting to add "this is just as well", as the other "on a link" properties expected in the IPv6 Link Model do not hold, as described above.

E. Considerations for IPv6-over-WAVE

Considering the differences between the IPv6 link model, described in section II-A, and the WAVE link model, described in section II-D, verbatim use of the standard IPv6 protocol stack, as the IEEE 1609 family of specifications stipulate, is not sufficient.

1) Air Interface Addresses: addresses for OBUs are specified to be link-local in [START_REF]The Wireless Access in Vehicular Environments (WAVE) Working Group of the Intelligent Transport Systems (ITS) Committee[END_REF]; it is further stated that configuring air interfaces of OBUs with Global Addresses is undesired due to the need to maintain topological correctness of such Global Addresses. This is necessary, but not sufficient, for these interfaces to be configured with "valid" addresses. Link Local addresses assigned to interfaces should in addition be globally unique, i.e., must be derived from some globally unique token. The reason for this is, as vehicles -and so their OBUs -may move, any two OBU air interfaces may at some point in the future become direct neighbors. On the other hand, since there is no guarantee that an arbitrary pair of air interfaces of OBUs will always remain neighbors, no IPv6 subnet prefix can be configured on an interface: vehicle movement may render such two air interfaces unable to communicate, requiring reconfiguration of the on-link IPv6 subnet prefix to respect the IPv6 Link Model assumption that "two interfaces with the same subnet prefix can communicate directly", as described in section II-A. The recently published RFC5889 [START_REF] Baccelli | RFC5889: IP Addressing Model in Ad Hoc Networks[END_REF] describes an IP addressing model for ad-hoc networks; the considerations described herein apply equally to air interfaces in WAVE networks, notably:

• An IP address configured on an air interface should be unique, at least within the routing domain (in this case, the vehicular network at large), and • No on-link subnet prefix is configured on this air interface. .

2) Supporting Protocols Employing Link-Local-Multicast: protocols such as DHCP, NDP and Stateless Address Autoconfiguration, assume the multicast characteristics of the IPv6 Link Model; as stated, these do not hold for the WAVE Link Model. NDP basic mechanisms such as Neighbor Solicitation (NS) do not operate as expected: the set of air interfaces which will receive such a NS is the set of air interfaces which, at the time of emission of the NS, happen to be within radio range. Thus, e.g., Duplicate Address Detection (DAD) will not ensure the desired uniqueness properties of IPv6 Link Local Addresses.

3) Discrete Link Layer Association Triggers: such triggers, otherwise used for initiating IPv6 interface configuration, are absent on the WAVE Link Model. Thus, protocols, including [START_REF] Narten | RFC2461: Neigh-bor Discovery for IP Version 6 (IPv6)[END_REF], [START_REF] Thomson | RFC2462: IPv6 state-less address autoconfiguration[END_REF], and the address configuration assumption that an interface can detect when it "disconnects" and thus should cease using previously used addresses, can not rely on such. Information can thus not be "solicited when events happen" but must be beaconed, and protocols adopted accordingly.

4) Communications Bidirectionality: link bidirectionality cannot be assumed. Experience with air interfaces show that if a device A hears service advertisements from another device B (OBU or RSU), this does not guarantee that device B can hear any service request sent by device A -i.e., it is not uncommon that links are unidirectional. Thus any alternative mechanism to be developed should at least verify link bidirectionality before relying on it.

III. OTHER CHALLENGES WITH WAVE USING THE IPV6 PROTOCOL STACK

The IPv6 protocol stack includes various additional protocols, above the network layer protocols described in section II. Regardless of how the described network layer issues are resolved, attention must be paid to operation of the transport and the application layers. This section briefly overviews some of these additional considerations.

A. Transport

At the transport layer, the IPv6 protocol stack proposes two types of protocols: TCP, a reliable, rate-adapting mechanism enabling end-to-end transport of application data across several IP hops and requiring bi-directional communication between the peers for acknowledgements etc. The second IPv6 transport protocol is UDP, a much simpler protocol providing no rateadapting or reliability mechanism and so no signaling from the destination to the sender in a traffic flow.

It is worth noting that TCP is often very inefficient in wireless ad hoc environments [START_REF] Holland | Analysis of TCP performance over mobile ad hoc networks[END_REF], especially when faced with mobility: TCP was designed to interpret packet loss as traffic congestion and to diminish sending rates in this case, whereas in wireless networks, packet loss may have causes that are other than traffic congestion, such as interfaces moving out of reach, collisions or interference. Also, if a TCP connection is established between two air-interfaces, subsequently moving out of range before the connection is terminated, connection-state remains for timing out (and possibly causing extraneous transmissions), not cleared up by the usual end-ofconnection signaling. Therefore, TCP is usually not employed in VANETs, which leaves UDP as the only viable alternative within the standard IPv6 stack. [START_REF]The Wireless Access in Vehicular Environments (WAVE) Working Group of the Intelligent Transport Systems (ITS) Committee[END_REF] recommends the use of UDP, however the reasons given (in section 6.4.3 of [START_REF]The Wireless Access in Vehicular Environments (WAVE) Working Group of the Intelligent Transport Systems (ITS) Committee[END_REF]) relate to the matching of "the connectionless nature of WAVE transmissions" only. The authors submit that there are also technical reasons for why TCP might be a lesser appropriate choice for this environment.

Applications requiring rate-adapting or end to end transport reliability services may not be satisfied with what the standard IPv6 protocol stack has to offer.

B. Pseudonimity

The IEEE 1609 family of specifications also promise to support MAC address changes to provide pseudonymity, i.e., to ensure that a device's non-temporary identity, and its longterm patterns of behavior, cannot be deduced from its network traffic and are only available to authorized parties.

However, IEEE 1609 specifications do not provide a way to generate or assign pools of globally unique network addresses, aside of basic "random" local generation which is likely to provide duplicate network addresses if devices change their network addresses too frequently. Note that the specifications do not define how frequently MAC address changes should take place in order to provide pseudonymity. Nevertheless, it is doubtful that pseudonymity can be achieved without a significant probability of duplicate network addresses using the current IEEE 1609 specifications.

In the same vein, in order to provide pseudonymity at layers above the network layer (which may be necessary to provide user pseudonymity in the end), similar issues are bound to arise if devices must change their IP addresses frequently. More generally, providing pools of globally unique IDs, dynamically and in a distributed manner, becomes a hard problem if the number of possible IDs is not extremely large.

Therefore, applications' requirements concerning pseudonymity may not be entirely satisfied with what the standard WAVE and IPv6 specifications have to offer so far, and thus, it is presently left to these applications to provide such services (if at all possible). Moreover, one should note that, as quickly mentioned in the IEEE 1609 specifications, frequent MAC or IP address changes will disrupt most applications.

IV. CONCLUSION

This paper has provided an overview of the issues concerning IPv6 use over WAVE, the protocol suite for wireless access in vehicular environments currently developed by the IEEE. While WAVE promises communications services to applications via IPv6 stack support -defined in the IEEE 1609 family of standards -this paper has shown that this support underspecified, and described the issues that are so far left unaddressed concerning IPv6 operation for WAVE. This paper has also analyzed the challenges in designing solutions to overcome these issues, and provided guidelines regarding the design of appropriate solutions.

Figure 1 .

 1 Figure 1. Dual stack, IPv6 and WAVE.

Figure 2 .

 2 Figure 2. IP Link Model: hosts (H) connected to the same link have assigned IP addresses from a common prefix, possibly assigned by a router (R).

•

  IP configuration parameters (global prefixes, ...) are provided in the WAVE Routing Advertisement (WRA) messages; • OBUs advertising services to other OBUs do so using Link-Local addresses: OBUs provide services to direct (1-hop) neighbors only, and therefore acquiring and maintaining topologically correct Global addresses is wasteful; • RSUs are identified by either Link-Local or Global addresses;

Figure 3 .

 3 Figure 3. Nodes (N) with air interfaces. The light grey area indicates the coverage area of each air interface. The dark grey circle indicates the interference area of the air interface of N3.

Figure 4 .

 4 Figure 4. Neighbor asymmetry.

Global addresses are only relevant in case the network can provide multihop communication, i.e. a router is present on the link.


Ulrich Herberg
email: ulrich@herberg.name

Thomas Clausen
email: thomas@thomasclausen.org

Yet Another Autoconf Proposal (YAAP) for Mobile Ad hoc NETworks

This paper addresses the issues of automatic address and prefix configuration of MANET routers. Specifically, the paper analyzes the differences between "classic IP networks" and MANETs, emphasizing the interface, link, topology, and addressing assumptions present in "classic IP networks". The paper presents a model for how this can be matched to the specific constraints and conditions of a MANETi.e., how MANETs can be configured to adhere to the Internet addressing architecture. This sets the stage for development of a MANET autoconfiguration protocol, enabling automatic configuration of MANET interfaces and prefix delegation. This autoconfiguration protocol is characterized by (i) adhering strictly to the Internet addressing architecture, (ii) being able to configure both MANET interface addresses and handle prefix delegation, and (iii) being able to configure both stand-alone MANETs, as well as MANETs connected to an infrastructure providing, e.g., globally scoped addresses/prefixes for use within the MANET. The protocol is specified through timed automatons which, by way of model checking, enable verification of certain protocol properties. Furthermore, a performance study of the basic protocol, as well as an optimization hereto, is conducted based on network simulations.

I. INTRODUCTION

A prerequisite for operation of a routed multi-hop network includes that the network interfaces of routers are appropriately configured with IP addresses, so as to enable exchange of routing protocol control messages. Another prerequisite is that routers providing connectivity for directly connected hosts have prefixes delegated -for configuring these hosts with IP addresses (to make enable these hosts to communicate), and for efficiently sharing information about these through the network routing protocol control messages (to render these hosts reachable also from across the multi-hop network). While these may sound as relatively benign tasks -after all, the Internet works -they are not entirely trivial even in the Internet: prefix delegation is centrally managed, on the top-level by ICANN [START_REF]Internet Corporation for Assigned Numbers (ICANN)[END_REF], by manually "subnetting" by the network operator, otherwise. Router interface configuration for router is a function of the characteristics of these router interfaces and links. Furthermore, the "configuration of the Internet" is relatively stable: an individual link may disappear and reappear, but new links do not often form spontaneously and arbitrarily -a consequence of links typically being both planned and fixed, e.g. in form of cables.

A Mobile Ad hoc NETwork (MANET) is by nature different. A typical "academic" description of a MANET may be "a collection of mobile routers, communicating among themselves over wireless links and thereby forming a spontaneous, dynamic, arbitrary graph" -calling out (wireless) interface characteristics and arbitrary and spontaneous link formation as challenges, in contrast to the "planned and fixed" expectations of the Internet. Fundamentally, in a MANET, any pair of router interfaces may at some point in time be able to communicate directly with each other. An additional assumption commonly made is, that in a MANET there is no network operator. Consequently, MANET router configuration must be such that reconfiguration is rarely needed -and if needed, must occur automatically.

In order to allow proper operation of MANET routing protocols, the interfaces of MANET routers must be appropriately configured with IP addresses -and prefixes must be available on MANET routers wishing to provide connectivity through the MANET to attached hosts. In order to allow proper operation of a MANET as an IP network, i.e., to enable the use of classic IP protocol stacks, and to thereby allow proper integration of MANETs into the larger Internet, the configuration of MANET router interfaces and attached hosts must conform to the Internet architecture. An interface being configured in a given manner entails that the IP protocol stack, as well as applications using that interface, make certain assumptions as to the connectivity over that interface. Failure to satisfy these assumptions may -popularly speaking -break the Internet.

In order to properly set the stage for development of a MANET router autoconfiguration mechanism, the remainder of this section will elaborate on the addressing and connectivity assumptions made for IP networks, formalize the particularities and challenges presented by MANETs in this regard, and discuss an addressing model which is both suitable for MANETs while respecting the IP network assumptionsi.e., such that MANETs do not "break the Internet".

A. The Internet is a Graph: IP Link and Addressing Model

Fundamentally, the Internet consists of three distinct components: hosts, routers and links. Hosts are devices which act as end-points for communication, which run user applications, and which have no responsibility for maintaining the Internet infrastructure. As such, their interest (in the context of network formation) is limited to "being connected to a router" via a link. Routers and links are the core notions in the Internet, where a link is assumed to have the following properties:

• IP datagrams are not forwarded at the network layer when communicating between network interfaces which are on the same link; hence • TTL of IP datagrams is not decremented when communicating between network interfaces on the same link; • IP datagrams with a TTL of 1 can be delivered to all network interfaces on the same link and; • Link-local multicasts and broadcasts are received by all network interfaces on the same link -without forwarding. A router is an entity which determines over which link a given IP datagram is to be forwarded and, in doing so, decrements the TTL of that IP datagram.

When assigning an IP address to a network interface, this network interface is also configured with a subnet prefix, such that the following constraint is respected:

• All network interfaces configured with addresses from within the same prefix p::, and with the same prefix p:: assigned to the interfaces, can communicate directly with one another. It follows from the above that the notion of "IP link" is tied with the notion of an "IP Subnet" (IPv4) or a prefix (IPv6), in that all network interfaces which are configured with the same subnet address or prefix are considered to be on the same IP link and thus that for communication between routers within the same subnet, no forwarding is required and no decrement of TTL/hop-limit is performed.

All network interfaces within the same subnet, are assumed to be connected to the same classic IP link, as described above. The inverse is not necessarily true: in some network configurations, interfaces connected to the same classic IP link may be configured with addresses from within different prefixes or subnets. Specifically for routers, communication is allowed between interfaces of two different routers, known to be on the same link, even if these interfaces are configured to appear within different subnets [START_REF] Hinden | IP Version 6 Addressing Architecture[END_REF].

B. MANETs: The Missing Link

MANET interfaces are a specific class of network interfaces, which exhibit what is commonly denoted as semibroadcast characteristics. This implies that otherwise neighboring routers may experience distinctly different local connectivity. In figure 1, the MANET interface of N2 is able to directly communicate with the MANET interface of N1 and N3 (i.e., no forwarding, TTL is not decremented, a transmission from the MANET interface of N2 is received by the MANET interfaces of both N1 and N3, including link-local broadcasts). Considering the properties listed for an IP link in section I-A, this might imply that the MANET interfaces of N1, N2 and N3 would be connected to the same link. However, the semibroadcast nature of MANET interfaces implies that this is not so: transmissions from N1 will not reach N3 without forwarding -which entails TTL decrement, and that link-local broadcast from the MANET interface of N1 will not reach the MANET interface of N3.

As per the assumptions that connectivity between any pair of MANET interfaces may appear and disappear spontaneously and arbitrarily, any attempt at configuring interfaces "within radio range of each other" to be within the same subnet prefix would be only temporarily sound: connectivity between any such pair of MANET interfaces might disappear at any time, or another MANET interface might appear, with connectivity to one (but not all) otherwise so configured MANET interfaces.

The semi-broadcast nature of MANET interfaces therefore implies that:

• Any two MANET interfaces cannot be assumed to be connected to the same link; thus • The IP address / prefix configuration of MANET interfaces must be such that their configuration (as per the constraint in section I-A) does not indicate that they can be assumed to be connected to the same link.

C. The Morphology of a MANET

A MANET router is a router having at least one MANET interface, i.e. an interface with semi-broadcast characteristics as indicated in section I-B, and otherwise retains the usual characteristics of a router. In particular, a MANET router:

• May have a prefix delegated to it;

• May delegate (part of) that prefix to other subordinate routers; • May have networks attached to it, in particular these networks may be of any type, (including, but not limited to, other MANETs), thus respecting usual routing and addressing hierarchies; these networks may be configured by way of the prefix delegated to the MANET router. A common case of a MANET may look as in figure 2, incidentally similar to the Internet with a "routing domain" (white cloud) and an edge (gray cloud).

D. MANET Interface Addressing

With respect to configuration of MANET routers, the constraints regarding IP address and prefix configuration of network interfaces must be respected, also on the MANET interface(s). This entails that:

• No two MANET interfaces can be assumed to enjoy persistent connectivity to each other; • Connectivity between any two MANET interfaces may appear and disappear at any time, spontaneously and arbitrarily; thus • The IP address / prefix configuration of MANET interfaces must be such that their configuration (as per the constraint in section I-A) does not indicate that they can be assumed to be connected to the same link. A translation of these properties into a set of consideration for IP address configuration of MANET interfaces is that:

• An IP address configured on a MANET interface should be unique, at least within the routing domain (within the MANET -the white cloud in figure 2); and • No on-link subnet prefix is configured on a MANET interface. The latter can be achieved by configuring a prefix length of /128 (for IPv6) or /32 (for IPv4) on the MANET interfacesessentially, configuring a MANET interface to be in a "subnet, containing only itself".

E. Problem Statement

The challenges addressed in this paper are, to provide a MANET autoconfiguration mechanism, which (i) provides MANET interface addresses according to the considerations in section I-D, and (ii) enables prefix-delegation to MANET routers, such that a MANET router so desiring can configure networks and hosts, connected to it via "classic IP links" (the gray cloud in figure 2).

F. Paper Outline

The remainder of this paper is organized as follows: section II discusses autoconfiguration mechanisms, proposed in literature, for MANETs. Section III proposes a novel autoconfiguration mechanism, according to section I-E. Section IV discusses an optimization for this mechanism. Section VI presents a formal verification of the proposed mechanism, by way of model checking, and section VII presents a performance study of the mechanism. This paper is concluded in section VIII.

II. RELATED WORK

Literature abound with MANET autoconfiguration mechanisms, both as academic publications and proposals to standardization bodies -none of which, however, at the time of this writing having been sanctioned as candidate for standardization. [START_REF] Bernardos | Survey of IP address autoconfiguration mechanisms of MANETs[END_REF] provides a comprehensive survey of a large number of such mechanisms, classifying them according to their applicability domain (stand-alone MANETs vs. MANETs attached to an infrastructure) and capability to handle network partitioning and merger. Common for all these proposed mechanisms is, however, that they do not adhere to the considerations described in section I-D. Notably, none of the presented algorithms configures /128 or /32 prefixes to the MANET interfaces; rather, they assume the MANET to be a single subnet. Moreover, they do not consider the separation of routers and hosts, and therefore do not provide prefixes to the routers, which may then be used by attached hosts or networks to that MANET router. Some of the presented algorithms depend on specific MANET routing protocols to be in operation in the MANET and thus are not generally applicable. While autoconfiguration mechanisms from academic publications, such as [START_REF] Thoppian | A distributed protocol for dynamic address assignment in mobile ad hoc networks[END_REF], [START_REF] Tayal | An address assignment for the automatic configuration of mobile ad hoc networks[END_REF], [START_REF] Mohsin | IP address assignment in mobile ad hoc networks[END_REF], present efficient mechanisms to verify uniqueness of addresses by splitting the range of available addresses into parts, none of these mechanism adhere to the considerations described in section I-D.

The autoconfiguration mechanism, proposed in this paper, is inspired by Zerouter [START_REF] Linton | Automatic Router Configuration Protocol[END_REF], [START_REF] Noisette | A framework for Zerouter operations[END_REF], [START_REF] White | Zero-Configuration Subnet Prefix Allocation Using UIAP[END_REF] and IPv6 Stateless Autoconfiguration [START_REF] Thomson | IPv6 stateless address autoconfiguration[END_REF], neither of which are discussed in [START_REF] Bernardos | Survey of IP address autoconfiguration mechanisms of MANETs[END_REF] as these were conceived for use in wired "classic IP" networks and so not directly applicable to MANETs. Zerouter was an early proposal for enabling home users and small companies without dedicated network operation competencies to build arbitrarily complex and large networks without manual interaction. Different approaches were brought forward in the IETF, however none were eventually standardized. Commonly, the different approaches assume that a border router of the network receives available address space from an ISP and injects that address space into the network. That address space is available for use throughout the collection of zerouters, in order to assign addresses to the router interfaces, and to delegate prefixes to the hosts connected to these routers [START_REF] Noisette | A framework for Zerouter operations[END_REF].

III. MANET AUTOCONFIGURATION MECHANISM

The mechanism proposed in this paper respects the considerations given in section I-D, and provides a routing-protocol independent solution to the problem stipulated in section I-E: configuring unique IP addresses for MANET interfaces and providing unique prefixes to MANET routers. It is inspired by the prefix delegation mechanism of Zerouter (as described in section II), specifically by (i) constructing prefixes such that all addresses/prefixes within the MANET can be aggregated (e.g., for injection into an external routing domain as a single entry), and (ii) by the idea of relying on a router (denoted "initiating router") for when a new router arrives in the network. The signaling and interface address configuration mechanism is based on IPv6 stateless autoconfiguration [START_REF] Thomson | IPv6 stateless address autoconfiguration[END_REF].

A. Algorithmic Overview

Each MANET router will acquire a prefix, constructed as d:p:s:: with d being a prefix (possibly of size 0), common for the whole site (e.g., a global prefix assigned administratively to a given site, or provided by an Internet gateway), p being common for all routers in this MANET, and s being unique to a specific router.

The task for a router, appearing in a MANET, can thus be summarized as:

• Acquiring d and p; • Selecting s, unique within the MANET;

• Configuring own MANET interfaces with addresses from within d:p:s:: (and with a prefix length of /128 or /32 as appropriate for IPv6 and IPv4, respectively). A router appearing in a network and wishing to be configured, is denoted a configuring router. Through a Prefix Solicitation (PS) / Prefix Advertisement (PA) message exchange, the router learns of the already configured routers in its vicinity, and selects one as initiator -the router which will assist in acquiring a valid configuration. The configuring router extracts d and p from the PA received from the selected initiator, generates a tentative prefix d:p:s:: 1 and, by way of a Router Solicitation (RS) message requests to its initiator that this tentative prefix be verified unique within the MANET. The initiator then issues and floods an RS, containing the tentative address of its configuring router, through the MANET. If the initiator does not (after due delay and retransmissions) receive a Router Advertisement (RA) indicating that the prefix is already in use, it will transmit an Autoconfiguration Confirmation (AC) message to the configuring router, confirming that the configuring router now "owns" d:p:s:: and can now become a defensive router. If the initiator receives an RA indicating that the tentative prefix is already in use, it informs the configuring router by issuing an RA.

A defensive router has two tasks. First, if receiving a RS containing its own d:p:s::, it must respond by issuing an RA. Second, if receiving a PS, it must respond by a PA, thus accept becoming initiator and act as described above.

The initiator and configuring routers communicate using link-local multicast to the standardized link-local multicast address for MANET routers (LL-MANET-Routers [START_REF] Chakeres | IANA Allocations for Mobile Ad Hoc Network (MANET) Protocols[END_REF]), with the configurator using the unspecified address as source. These two routers identify traffic destined to each other by way of Universally Unique Identifiers (UUIDs) [START_REF] Leach | A Universally Unique IDentifier (UUID) URN Namespace[END_REF], embedded in all messages exchanged between them. UUIDs are 16 octets long, and as they are exchanged in messages only between neighboring routers, they need only be locally unique. Network-wide messages (RS/RA) are "proxyed" by the initiator, which is already configured.

B. Formal Protocol Specification

The protocol is formally specified by way of timed automata, included in this section. The motivation for a formal specification is to prove (or disprove) certain properties, presented in section VI.

Figure 3 shows the timed automaton representing a configuring router. At the initial state, INIT, it starts the PS/PA exchange for acquiring the prefix d:p::. If, after several retries, no PA has been received, the router selects a random s and finishes configuration in the state CONFIGURED. If, however, it receives a PA from the initiator (PA_RECVD), it starts sending RS'es to the initiator (RS_SEND), until it receives an Figure 4 shows the timed automaton representing a defensive router, initiated in the state LISTENING. When the router receives an RS, it checks for a conflict with its own prefix (CONFLICT) -if one is identified, it responds by sending an RA, either via a link-local transmission if the defensive router is the initiator for the configuring router (LOCAL_CONFLICT), or through the MANET otherwise (MANET_CONFLICT). If the tentative prefix does not conflict with its own prefix (NO_CONFLICT), the defensive router either starts the AC timer, if it is the initiator for the configuring router (START_AC_TIMER), or otherwise forwards the RS through the MANET (back to LISTENING).

IV. PROXYING EXTENSION

In this section, an optimization to the protocol proposed in section III is presented, for the purpose of increasing the efficiency of the protocol.

Rather than broadcasting RS'es through the MANET, an intermediate router can reply with an RA on behalf of a conflicting router if that intermediate router already know that there will be a conflict. This may be if the intermediate router already has a route recorded to the prefix contained in the RS (e.g., as provided by a proactive routing protocol such as OLSR [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]), or by an intermediate router temporarily caching RS and RAs previously seen. This may reduce network congestion on a large scale, quantified in section VII.

V. ADDITIONAL CONSIDERATIONS

This section addresses several issues that may occur in the protocol and proposes ways how to solve these problems.

A. Duplicate UUIDs

A question may arise as to the behavior of the protocol in case two MANET routers select the same UUID. While this might seem quite improbable, given that a UUID is 16 bytes long, the ability to generate a truly random UUID depends on the quality of the random number generator available in the router. Typically, routers use a pseudo-random generator algorithm based on a seed and some environmental settings. Thus, when two routers initiate the random generator with the same seed, they may create the same sequence of random numbers. If that is the case, duplicate UUIDs appear.

Consider the example depicted in figure 5 with two configuring routers and one initiator router. The only case when having duplicate UUIDs interferes with the autoconfiguration protocol is when the initiator router sends an AC to one of its configuring routers, and there happen to be two configuring routers in radio range of the initiator, and both of these configuring routers want to configure the same tentative prefix. In the example, both routers conf ig 1 and conf ig 2 send their RS requesting the initiator to verify uniqueness of the same tentative prefix, at close to the same time. The initiator replies by sending an AC to conf ig 1 (assuming there is no prefix conflict in the MANET) and then an RA to conf ig 2 , with the intent of informing conf ig 2 that its tentative prefix already is in use. As both of the two configuring routers have the same UUID and have requested the same tentative prefix, they will both receive the AC -and will therefore both configure with that duplicate prefix. The later arriving RA will be ignored by both routers; they already are configured and thus no longer listening for such.

The objective is to detect a UUID conflict, when it occurs, and once detected avoid entering a CONFIGURED state. To that end, after a router having received an AC or an RA corresponding to its UUID, it will wait a small amount of time. If during that time the router receives a second AC or RA for the same UUID and tentative prefix, the router can deduct that a UUID conflict has occurred and take corrective action: re-seeding its random number generator and restarting the autoconfiguration process.

B. No initiator router exists

This problem occurs when two or more routers want to configure a prefix almost simultaneously when there is not yet an already configured MANET router. In figure 6 an example of that case is depicted. Both routers conf ig 1 and conf ig 2 start sending their PS s almost simultaneously. As there is no configured router yet, no PA replies will arrive. After PS_MAX_TRIES tries, both routers will become initiator routers but not being part of the same MANET (i.e. not having the same prefix part p and not having verified uniqueness of their prefixes). There can be two different cases as soon as the configuring routers from the example become initiators and choose the random prefix p:s:

1) If the routers choose different prefix parts p, they cannot be aggregated using CIDR. They may join the same prefix region by merging. 2) If both routers choose the same prefix part p, they are part of the same prefix region but did not verify the uniqueness of the prefix part s. They could for example passively detect collisions (as proposed by a number of "passive" autoconfiguration algorithms in the survey [START_REF] Bernardos | Survey of IP address autoconfiguration mechanisms of MANETs[END_REF]). To solve this problem, configuring routers can listen for incoming PSs from other routers. The router with the lower UUID waits at least AC_TIMEOUT seconds before continuing the autoconfiguration process. Thus, the adjacent router can get configured in the meantime.

VI. FORMAL VALIDATION USING A MODEL CHECKER

The proposed protocol, as formally specified in section III-B, has been modeled as Timed Automaton and subjected the UPPAAL model checker. This model checker has previously and successfully been applied for other communication protocols (e.g. Zeroconf [START_REF] Gebremichael | Analysis of the zeroconf protocol using UPPAAL[END_REF]).

A. Assumptions and Simplifications of the Model

The model used in the model checker has been slightly simplified in comparison to the specification and the implementation. The following assumptions have been made:

• Simplified broadcasting
When the initiator router broadcast a RS, it instantly received by all other configured routers in the MANET, i.e., assuming a perfect and instantaneous broadcast operation. • No two routers are configured at the same time

If two routers configure in the same time, with no initiator router, no RA or AC exchange can be performed and both routers would become initiator routers without having checked address uniqueness. In an initial model of the protocol, this had happened. So using the model checker, a solution for this problem has been developed (as described in section V-B).

• Routers do not have a MANET prefix

Routers all have addresses of the form x where x ∈ IN .

B. Verification of Properties in UPPAAL

The following properties of the autoconfiguration algorithm were of interest to be proven correct: The algorithm...

• converges: The algorithm should terminate in finite time.

• configures unique prefixes to all MANET interfaces In order to prove the correctness of the above-mentioned properties, they have to be "translated" into logic queries supported by UPPAAL (using Computation tree logic, CTL). The following queries have been verified on the model of the autoconfiguration algorithm: • E<> forall (i : UUIDType) IP[i] != 0 This query checks whether there exists a state (E<>) for every router in the MANET (i : UUIDType), in which that router has a configured IP address. That means that the autoconfiguration algorithm has to facilitate that every router can successfully configure an address. The last statement is weaker than proving that all routers must be configured after a finite time:

• A[] E<> forall (i : UUIDType) IP[i] != 0. UPPAAL does not support to verification of this statement. It is currently unclear whether this behavior of UPPAAL is a deficiency of the particular model checker or generally infeasible due to the state explosion and the huge amount of necessary calculation power.

VII. SIMULATION

In this section, the performance of the proposed autoconfiguration mechanism is studied, by way of network simulation using NS2 and using relatively standard scenario parameters (1km 2 square, no mobility, very light traffic and a varying number of routers randomly distributed across the area, simulations averaged over 20 runs per data point, current timestamp used as seed for random number generator). Further simulation parameters are listed in table 7(a). Routers, and so autoconfiguration operations, are started consecutively on each router every second, e.g. the router with the ID 17 engages the autoconfiguration process 17.0s after simulation start. Each router acquires the MANET prefix either by receiving a Prefix Advertisement (PA) message or, failing that, by choosing a random prefix if it is the first router in the MANET. All routers will, for the purpose of evaluating worst-case performance, want to configure their prefix p:s:: to be 0:1::. Thus, from the second router appearing in a MANET, address collisions will appear. Two different versions of the autoconfiguration algorithm have been tested, the basic version presented in section III and an extended version with proxying, as described in section IV.

A. Simulation results

Both versions of the autoconfiguration protocol resulted in all routers being configured with unique prefixes, eventually. However, the number of messages exchanged and number of messages lost due to collisions differ. In the basic version of the algorithm, RS and RAs are flooded throughout the MANET, whereas in the proxy version, routers cache prefixes extracted from RSs for the duration of the simulation. Additionally, routers store a temporary reverse route back to the initiator when forwarding RSes, so as to enable unicast RAs when possible.

Figure 7(b) depicts the total number of transmissions in both versions for the MANET. Note that this number does not include ARP or MAC overhead. As the proposed mechanism does not rely on routing, no IP forwarding is applied. Messages used in this protocol are forwarded on an application layer, which means that they are counted as a new transmission in the figure, each time a message is forwarded or newly generated.

As can be seen, proxying significantly reduces the number of transmissions. Consequently, the drop rates, depicted in figure 7(c), are lower due to less channel contention.

VIII. CONCLUSION

This paper presents architectural considerations for address configuration of router interfaces and prefix delegation to routers in IP-based MANETs. Special attention is given to understanding how to configure MANET routers so as to, on the one hand, accommodate the particularities of the MANET interface type and the spontaneous and arbitrary nature of "links" in MANETs while, on the other hand, respecting the assumptions and expectations that applications present to an IP-based network. A simple set of principles are presented which, if respected, satisfies both.

An autoconfiguration protocol for MANET interface address assignment and prefix delegation to MANET routers is then presented, inspired by both Zerorouter and IPv6 Stateless Autoconfiguration. This protocol is fully distributed, and enables automatic configuration of both stand-alone MANETs, as well as MANETs connected to an infrastructure. The protocol is specified by way of a set of timed state machines, which enables subjecting it to model checking using the UPPAAL model checker -identifying that the protocol works, notably that (i) there are no deadlocks in the distributed protocol, that all configured routers ultimately ends up with distinct addresses and disjoint prefixes and (iii) that given a network with sufficient addresses available, the protocol will converge to a state where all MANET routers are properly configured.

In order to understand the performance of the protocol, a simulation study is presented, testing a performanceimproving, overhead-reducing extension to the protocol. These performance results show that the protocol has a relatively low overhead, and that using a proxy extension to the base protocol can further reduce packet overhead and drop rate in the network.

Figure 1 .

 1 Figure 1. MANET: routers (N) with MANET interfaces. The light grey area indicates the coverage area of each MANET interface.

Figure 2 .

 2 Figure 2. MANET with attached networks: routers (R) with MANET interfaces (white cloud), some of which with "classic IP links" and attached networks/hosts (gray cloud).

Figure 4 .

 4 Figure 4. State machine of a defensive router

Figure 5 .

 5 Figure 5. Two routers conf ig 1 and conf ig 2 having the same UUID lead to ambiguous destinations of ACs

Figure 6 .

 6 Figure 6. Problem when several routers are configured almost simultaneously without initiator routers

Figure 7 .

 7 Figure 7. NS2 Simulations