Jiazi Yi

Juan Antonio

Cordero Fuertes

Thomas Clausen
email: thomas@thomasclausen.org

Jitter Considerations in On-demand Route Discovery for Mobile Ad Hoc Networks

Jittering (a small, random variation in timing of control message emission) is widely used in protocols for wireless communication, in order to avoid simultaneous packet transmissions over the same channel by adjacent nodes in the network. Used for both regularly scheduled packets, for event-triggered packets, and for scheduled resets in the network, jittering is a particularly important mechanism when a network event may cause multiple adjacent nodes to react concurrently. Introduced in the proactive MANET routing protocol OLSR, the "LLN On-demand Ad hoc Distance-vector Routing Protocol -Next Generation" (LOADng), a derivative of AODV, is specified so as to also use jitter for flooding Route Request (RREQ) messages during route discovery. This use of jitter in RREQ flooding is, however, not without drawbacks, which are identified and addressed in this paper within the framework of a more general study of jitter mechanisms used for route discovery in reactive routing protocols. The paper studies the behavior of route discovery when using "naive" jitter (simply, delaying RREQ retransmission by a small uniformly distributed random delay), in order to identify and analyze the problems hereof, mostly related to route sub-optimality and excessive control traffic overhead. A Window Jitter mechanism is then proposed to address these issues -with the performance hereof, when compared to "naive" jitter being evaluated by way of modeling, theoretical analysis and experiments. The paper shows that the use of Window Jitter improves indeed the efficiency of route discovery in AODV and overcome the drawbacks identified for "naive" jitter.

I. INTRODUCTION

Since the late nineties, the Internet Engineering Task Force has been investing substantial efforts on the research, design, development and standardization of routing protocols for networks operating in increasingly challenging conditions, communication through more fragile and low-capacity links, with less pre-determined connectivity properties and with increasingly constrained router resources.

1) MANET Protocol Developments: The MANET working group converged on development of two protocol families: reactive protocols, including AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], and proactive protocols, including the Optimized Link State Routing (OLSR) protocol [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF]. A distance vector protocol, AODV operates in an on-demand fashion, acquiring and maintaining routes only while needed for carrying data, by way of a Route Request-Route Reply exchange. A link state protocol, OLSR is based on periodic control messages exchanges, each router proactively maintaining a routing table with entries for all destinations in the network. A sizable body of work exists, including [START_REF] Clausen | Comparative study of routing protocols for mobile ad-hoc networks[END_REF], studying the performance of these protocols in different scenarios, and justifying their complementarity [START_REF] Clausen | Analyzing control traffic overhead versus mobility and data traffic activity in mobile ad hoc network protocols[END_REF]. For the purpose of this paper , it suffices to observe that OLSR, as a link state protocol, provides low delays and predictable, constant control overhead -at expense of requiring memory in each router for maintaining complete network topology. AODV limits the memory required for routing state to that for actively used routes -at the expense of delays for the Route Request-Route Reply exchange to take place, and control overhead dependent on data flows.

After acquiring operational experience, the MANET working group commenced developing successors to OLSR and AODV, denoted OLSRv2 and DYMO respectively. Whereas a relatively large and active community around OLSR standardized OLSRv2 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] and [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], the momentum behind DYMO withered in the MANET working group. However, other derivatives of AODV have been implemented and used widely: IEEE 802.11s [START_REF] Hiertz | Principles of ieee 802.11s[END_REF], for example, is based on AODV, and the G3-PLC standard [START_REF] Itu-T G | Narrow-Band OFDM power line communication transceivers -Data link layer specification[END_REF], published in 2011, specifies the use of LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] (a simplified version of AODV) at the MAC layer, for providing mesh-under routing for utility (electricity) metering networks. Spurred by these experiences, 2011 saw the emergence of LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], as a successor to LOAD.

2) Jitter: In a wireless network, simultaneous packet transmissions by nearby nodes should be avoided because such might cause loss of transmissions on receivers due to collisions on the wireless channel. Depending on the characteristics of the medium access control (MAC) layer, in particular whether the retransmission of the unacknowledged transmissions is supported, such collisions may result in longer delays or even packet losses. A MAC protocol can, in some instances, handle this way of by collision detection and link-layer packet retransmissions, however, it is in other cases necessary to also have collision-avoidance mechanism in place at the network or higher layers also. In [START_REF] Clausen | The optimized link state routing protocol, evaluation through experiments and simulation[END_REF], jitter (adding a small, random delay on transmissions) is introduced on the interval between the periodic exchange of control messages. In RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], the use of jitter is recommended for MANETs as one collisionavoidance mechanism for MANET routing protocol control traffic.

[12] introduces an analytical model for investigating the impact of the standardized jitter mechanism on network-wide packet dissemination, and studied and quantified the additional delay incurred, the reduction in number of transmissions, and the effect of jitter in packet size. [START_REF] Friedman | Jittering Broadcast Transmissions in MANETs: Quantification and Implementation Strategies[END_REF] presents the relationship between the maximal jitter duration and the probability of successful transmission, and different strategies of implementing jitter mechanisms are compared. [START_REF] Friedman | Jittering Broadcast Transmissions in MANETs: Quantification and Implementation Strategies[END_REF] concludes that implementing jitter at any layer above IP (e.g. at the transport or application layer) brings virtually no benefits.

A. Statement of Purpose

This paper studies the impact of jitter in route discovery in reactive routing protocols. Route discovery in reactive routing protocols uses flooding of Route Request (RREQ) messages through the network, in order to discover available routes from (requesting) sources to (requested) destinations. An intermediate node receiving an RREQ for the first time will process and, immediately, retransmit it. Using jitter permits reducing the probability that adjacent nodes will retransmit at the same time.

In addition to collision avoidance by way of a random delay on transmission of RREQ messages, this paper also considers:

• Route discovery of optimal routes. When RREQ messages are flooded through the network, the route cost (e.g.,hop count or any other link metrics) is also recorded. The destination of the RREQ will reply it with a Route Reply (RREP) message. However, the RREQ copy that arrives first may not always be the one which has traversed the most optimal path with respect to the metric used -and this is exacerbated by "naive" use of jitter. The contribution of this paper is double. First, the impact of using jitter in route discovery in reactive routing protocols is studied, and problems arising from a too "naive" use of jitter are identified and quantified: additional overhead and sub-optimal paths. Second, a strategy denoted Window Jitter, is proposed, which retains the benefits of jitter while alleviating the issues identified from its naive application.

The remainder of this paper is organized as follows: section II provides a background by way of introducing the principal mechanisms of reactive routing protocols and of jitter. Section III analyzes the use of jitter for RREQ flooding in reactive routing protocols, and discusses the problems arising from the use of uniform jitter for this purpose. Window Jitter is proposed in section IV, followed by performance studies and comparations in section V. The paper is concluded in section VI.

II. REACTIVE PROTOCOLS AND APPLICATION OF JITTER

This section presents, in section II-A, a summary of the main mechanisms of reactive routing protocols, and describes, in section II-B, the basics principles of jitter applied for flooding, according to [START_REF] Clausen | Jitter Considerations in MANETs[END_REF].

A. Reactive Routing Protocol Principles and Overview

AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] and its derivatives (LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF], LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]) specify two principal operations: Route Discovery and Route Maintenance.

1) Route Discovery: During Route Discovery, RREQ messages are flooded through the network until they reach the sought destination -at which point that destination generates an RREP, which is unicast along the reverse path to the source of that RREQ. In AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], intermediate routers can, furthermore, generate an RREP as reply to a received RREQ, provided that they have a "sufficiently recent" and valid route to the sought destination already. Additionally, an intermediate router generating an RREP also sends a gratuitous RREP to the sought destination, thus installing the complete forward and reverse paths. Protocols such as LOAD and LOADng do away with the intermediate/gratuitous RREPs, so that only the destination of the RREQ can reply, in order to simplify protocol operation and reduce the size of control messages.

2) Route Maintenance: Route Maintenance is performed when an actively used route fails, i.e., when a data packet cannot be delivered to the next hop towards the intended destination. When detecting that a route has failed, a Route Error (RERR) message is generated to notify the route failure.

B. Jitter Technique for Flooding

Due to the shared nature of a wireless medium, simultaneous packet transmissions are likely to cause packet losses due to collisions. In order to prevent or minimize these collisions, RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] recommends the use of jitter for different cases in which packets may be expected to be sent concurrently. One of the main examples of concurrent transmissions is packet flooding, i.e., the procedure by which a packet is sent to all nodes in a network by way of having each node retransmit that packet exactly once on first receipt.

Without jitter, a node receiving a packet to be forwarded retransmits it immediately after processing. Instead, RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] recommends that each node adds a small, random delay before forwarding a flooded packet, in order to avoid collisions with other , neighbouring nodes that may have received the same packet which might forward it over the same wireless channel as part of the flooding procedure. The recommendation from RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] is that delays be selected following an uniform distribution between 0 and a maximum jitter value, J m . Figure 1 illustrates this use of jitter for flooding.

Other than prevention of packet collisions from simultaneous transmissions (from B and C, in figure 1), the use of jitter in flooding has two immediate additional effects: (i) the flooding process is slowed, and (ii) nodes need larger buffers to store packets which have been received, but not yet forwarded. The tradeoff between these drawbacks and the reduction in the probability of collisions can be controlled by way of the length of the jitter interval, J m .

III. USE OF JITTER FOR ROUTE DISCOVERY IN REACTIVE ROUTING PROTOCOLS

This section discusses the use of jitter, as specified in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], for flooding of RREQ messages from a reactive protocol during route discovery. Section III-A describes, by way of an example, some drawbacks, incurred by the use of jitter for RREQ flooding, in terms of routing performance. This is related to the "longer paths get first" phenomenon, which is presented and described. Section III-B provides a probabilistic analysis of this phenomenon, which is further addressed in the remainder of this paper.

A. Intuition

In a reactive routing protocol, RREQ messages from a source are flooded through the network in order to identify a route towards the intended destination. Deliberate jittering of RREQ retransmissions, in the way specified in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], is recommended by e.g.,LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]. However, the fact that RREQ messages reach their destination with a random delay has some drawbacks, in terms of path sub-optimality and/or control traffic inefficiency. Consider the topology shown in Figure 2(a), and assume that node A floods (broadcasts) an RREQ to identify a route towards D. Under normal operation of a reactive routing protocol, i.e. without jitter, the RREQ would reach D through the path p 2 = {A, E, D} faster than through the path p 1 = {A, B, C, D}, assuming that processing times and transmission times at each intermediate node(T i ), are similar. In fact, because the jitter T j is generally up to tens milliseconds, it is much greater than the processing time and transmission time (generally less than 1 millisecond, i.e., T j >> T i ) in networks without significant congestion. For simplicity, only the delay caused by jitter is considered in the following analysis. The simulation results in V confirmed this assumption.

If a uniform random distribution [0, J m ] is used at each hop, to determine an additional delay before retransmission, the message copy sent through the longer path (in number of hops), p 1 , may reach the destination faster than the message copy over p 2 with a non-negligible probability, for instance if assigned jitter values are those shown in Figure 2(b).

In this case, node D would reply to the Route Request from A with a Route Reply (RREP) that advertises path p 1 , which is suboptimal. When the RREQ traversing p 2 would reach D, D would reply again to A's Route Request with the (shorter) path p 2 . This implies that A would get, and possibly use for a certain amount of time, a suboptimal path towards D (p 1 ), and it would need two RREP from D in order to learn the optimal path from A to D. If D was not the destination of the requested route, but only an intermediate node towards that destination, then D would retransmit twice the RREQ as it is received from p 2 and p 1 .

This example illustrates that the use of uniform random distribution for jitter values when forwarding RREQ messages during route discovery in a reactive routing protocol may lead to cases in which "transmissions over longer paths get first" -this effect is hereafter denominated delay inversion caused by jitter, as it turns longer (worse) paths into paths which are traversed faster. These delay inversions are harmful due to at least three undesirable effects: (i) increase of sub-optimality of reported routes, (ii) growth of unnecessary RREQ flooded traffic, and (iii) growth of unnecessary RREP (unicast) traffic.

B. Analysis

This section provides a quantitative probabilistic analysis of the delay inversion effect. Let T j be the random variable for jitter values, then T j ∼ U nif orm[0, J m ] according to RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF]. The delay caused by uniform jitter in an RREQ message traversing a path of n hops, T (n) 1 , can be then be computed as follows:

T (n) 1 = n i=1 Tj i (1)
Given two paths between a source X and a destination Y , with lengths n and m, let D (n,m) 1 be the inter-path delay difference, i.e., the difference between jitter delays suffered by an RREQ flooded through two paths between X and Y , of n and m hops. It is a random variable that depends on the random variables for the jitter values in the way shown in [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF].

D (n,m) 1 = T (n) 1 -T (m) 1 = n i=1 Tj i - m j=1 Tj j (2)
The probability of inversion, that is, the probability that the delay inversion ("longer paths get first" effect) occurs in the RREQ flooding, corresponds to P (D

(n,m) 1 > 0| n<m ), whose expression is detailed in (3). P T (m) 1 < T (n) 1 = P D (n,m) 1 > 0 = ∞ 0 f D (n,m) 1 (t)dt (3)
The probability density function (PDF) of D

(n,m) 1 , f D (n,m) 1 (t)
, has the following expression:

f D (n,m) 1 (t) = n+m i=1 fT j i (t + mJm) (4)
where ⊗ denotes the convolution. This expression can be computed by using the well-known result for the PDF of the sum, S n , of n independent uniform random variables U nif orm[0, 1] [14]:

fS n (x) = 1 (n -1)! n k=0 (-1) k n k (x -k) n-1 + (5)
Note that f Sn (x) = 0 for x > n and x < 0. Notation z + denotes the positive part of z, i.e., z + = z if z > 0, z + = 0 otherwise. Then, the probability of delay inversion between two paths with lengths n and m (n < m), becomes P (D

(n,m) 1 > 0)| n<m . The expression of P 1 ≡ P (D (n,m) 1 > 0) is computed in (6): P1 = 1 (n + m)! n+m k=0 (-1) k n + m k (n + 2m -k) n+m - -(m -k) n+m + (6)
Figure 3(a) illustrates the theoretical values for the probability of inversion for different values of n and m, i.e., the probability that a path of m hops performs faster forwarding than a path of length n. Expression [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF] indicates that the delay inversion occurs, under the conditions specified in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], with a significant probability. Two aspects can be highlighted from this analysis: (i) from ( 6), the probability of inversion does not depend on the length of the jitter interval, J m , meaning that it cannot be addressed by modifying the jitter interval length; and (ii) from Figures 3(b) , probability of inversion does not only depend on the difference between path lengths, ∆ = m -n, but also on the absolute values of path lengths n and m: as paths become longer, more random jitter values are assigned to an RREQ message and it is more likely that delay inversions occur.

IV. THE WINDOW JITTER

This section presents a mechanism for substantially reducing the number of situations in which RREQ messages from a source reach the destination faster through a longer (and sub-optimal) path rather than through a shorter path. As this effect cannot be addressed by way of the J m parameter, this section proposes to modify the distribution of jitter valuesthe window jitter distribution.

A. Rationale and Definition

With the uniform distribution for jitter values specified in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], the longer the path that a flooded RREQ traverses, the longer is the interval of possible delay values

T (n) 1
for that flooded RREQ. From (1), the upper bound for total jitter delay grows linearly with the length of the path, but the lower bound stays fixed at zero. This is corrected in the modified distribution by introducing a minimum jitter interval in each hop. Jitter values are then instances of a random variable T * j ∼ U nif orm[αJ m , J m ], where α ∈ (0, 1) and αJ m is a minimum jitter value. Note that α = 0 corresponds to the jitter distribution specified in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], α = 1 would imply a deterministic delay (of length J m ), and α = 0 implies that the lower bound for the RREQ delay grows linearly with the length of the traversed path.

Figure 4 shows the probability density functions (PDFs) for the jitter value as specified in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] (T j ) and the window jitter random variable (T * j ). The most obvious consequence of using the random variable T * j instead of the random variable T j for assigning jitter values is, that the average value of jitter increases from E{T j } = 1 2 J m to E{T * j } = 1+α 2 J m . Upper bound (worst case) for the delay caused by jitter, however, is J m in both cases.

1/((1-α)•J m ) J m pdf T j * α•J m 0 1/J m J m pdf T j

B. Analysis

The analysis performed in section III-B for T j can be repeated for T * j , and that brings the following expressions for the total jitter delay, T (n) 2 :

T (n) 2 = n i=1 T * j i (7)
And the inter-path delay difference for the window jitter distribution, D (n,m) 2

: D (n,m) 2 = T (n) 2 -T (m) 2 = n i=1 T * j i + m j=1 -T * j j (8)
It is immediate to observe that variable D

(n,m) 2

has the following PDF:

f D (n,m) 2 (t) = n+m i=1 f T * j i (t + mJm) (9)
Without loss of generality, and for the sake of simplicity, it can be assumed in the following that J m = 1. Then, also using (5), the PDF detailed in (9) can be expressed in the terms of Proposition 1:

Proposition 1. f D (n,m) 2 (t) = 1 1 -α 1 (n + m -1)! × × n+m k=0 (-1) k n + m k t -nα + m 1 -α -k n+m-1 + ( 10
)
for t-αn+m > 0) corresponds to:

P2 = 1 (n + m)! n+m k=0 (-1) k n + m k (n + m -k) n+m - - k * k=0 (-1) k n + m k m -nα 1 -α -k n+m ( 11
)
where k * = m-nα 1-α + , for α ≤ n m . P 2 = 0 otherwise (i.e., for α > n m ).

Proof: From the definition of probability, P (D

2 > 0) = ∞ 0 f D2 (x)dx, which is: P2 = ∞ 0 dt n+m k=0 (-1) k n+m k t-nα+m 1-α -k n+m-1 + (1 -α)(n + m -1)! = = n+m k=0 (-1) k n+m k ∞ 0 dt t-nα+m 1-α -k n+m-1 + (1 -α)(n + m -1)! (12)
The integrand of ( 12) is zero when t-nα+m

1-α

> n + m ⇐⇒ t > n -mα, and n -mα > 0 (see Proposition 1), therefore ( 12) can be rewritten as follows:

P2 = n+m k=0 (-1) k n+m k M 0 dt t-nα+m 1-α -k n+m-1 + (1 -α)(n + m -1)! ( 13
)
where M ≡ max{0, n -mα}. Consider the integral

I 0 ≡ M 0 dt t-nα+m 1-α -k n+m-1 +
. The integrand of I 0 is non-zero when:

t -nα + m 1 -α -k > 0 =⇒ t > k(1 -α) + nα -m ≡ t0 (14)
and zero otherwise. Therefore, integration limits of I 0 can be modified as follows:

I0 = max{0,n-mα} max{0,t 0 } dt t -nα + m 1 -α -k n+m-1 (15)
t 0 depends on k. It is worth to observe that:

• t 0 < n -mα, ∀k : 0 ≤ k ≤ n + m. And n -mα > 0 iif α > n m . • t 0 > 0 ⇐⇒ k(1 -α) + nα -m > 0, for k min = 0 and k max = n + m. This implies that α ≤ n m and α > m n . • For α ≤ n m , α ≤ m n , there is a k * = m-nα 1-α + ≥ 0 such that t 0 > 0, ∀k > k * .
Which implies that I 0 can be expressed as:

I0 = max{0,n-mα} max{0,t 0 } dt t -nα + m 1 -α -k n+m-1 (16)
Then, ( 13) can be computed to Proposition 2, while α ≤ for different combinations of path lengths n and m. In the analysis, hopcount metric is considered, i.e., the routes with less hops are more preferred. α is set to 1 2 , to have a balance between the randomness of jitter, and the "width" of window to reduce delay inversion effect.

It can be observed in figure 5.a that transition from values close to 0 to 1 (i.e., from situations in which RREQ transmissions over the n-path are never faster than those over the m-path, to situation in which are always faster) is significantly more steep with the modified (generalized) distribution of jitter values than with the distribution of RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] (see figure 3(a)). As the ideal situation would be that D As in figure 3(b), theoretical values (lines) and simulations (points, each of them averaged over 200 samples) are displayed together. It can be observed that the values are substantially lower than those achieved with T j ∼ U nif orm[0, J m ]: for very similar (∆ = m-n = 1, which is the most frequent case) and long paths (n = 5), the probability reduces in a factor 5 and stays below the 6%; the relative variation becomes still more significant as paths are shorter.

C. Generalization: Another Perspective

The uniform distribution between 0 and J m specified in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] is the maximum entropy distribution among those assigning continuous jitter values between 0 and J m [START_REF] Karmeshu | Entropy Measures, Maximum Entropy Principle and Emerging Applications[END_REF]. This implies that the use of this distribution maximizes the randomness of the total delay suffered by an RREQ message sent along a certain path.

The window jitter described in this section reduces randomness and introduces a (deterministic) dependency of the total RREQ delay to the length n of the traversed path. When assigning jitter values according to the distribution of random variable T * j , the total delay caused by jitter in a path of n hops belongs to the interval [nαJ m , nJ m ] (α = 0). The trade-off between randomness and path length deterministic dependence can be controlled by way of parameter α ∈ (0, 1): the closer α is to 1, the more deterministic becomes the total delay of an RREQ message with respect to the path length.

Each additional hop in the path traversed by an RREQ message causes at least an additional delay of αJ m before being delivered to the requested destination. This is done in order to increase the probability that the RREQ message traverses first a shorter path, in number of hops, rather than a longer path, considered worse for routing. This model thus assumes that shorter paths are preferable to longer paths, that is, a hop count metric is implicitly assumed.

The window jitter principle can, naturally, be extended to non-trivial link metrics, e.g., based on probability of successful transmission (ETX [START_REF] De Couto | A highthroughput path metric for multi-hop wireless routing[END_REF]). Given a link quality indicator LQ ∈ (0, 1) (LQ -→ 1 for high quality links), jitter values would be assigned under a generalized window jitter distribution uniformly within the interval [(1 -LQ)J m , J m ], in order to reduce the probability of delay inversion or, equivalently, increase the probability that an RREQ message is forwarded faster by routers receiving it on better links. Note that the window jitter distribution presented and analyzed in sections IV-A and IV-B corresponds to the particular case of LQ = 1 -α for all available links.

V. NETWORK SIMULATION AND ANALYSIS

The window jitter distribution proposed in section IV is implemented, studied and evaluated by way of network simulations over different scenarios, under several different configurations. These simulations permit validating the theoretical results obtained in sections III and IV, comparing in practice the performance of AODV RREQ flooding when using the original distribution of RFC 5148 and the proposed window jitter distribution. Simulations also allow to identify the networking and jitter elements that have impact in this performance. Section V-A presents the setting of the performed network simulations. Section V-B describes the main results obtained in the experiments.

A. Simulation Setting

In order to understand the impact in flooding performance of different jitter settings, ns2-simulation results are presented in the below. Simulations were made of a field of 1000 × 1000 meters, with varying numbers of routers placed randomly, equipped with 802.11b radio interface and with 250m range. For the purpose of this study, router mobility was not considered. The metric is based on hop-count.

Each simulation lasts for 100 seconds. Thirty random routers in the network initiate route discovery to another random destination every two seconds. The number of collisions, average overhead, average route discovery delay and average path length are measured.

Different jitter settings are compared:

• No jitter.

• Standard RFC 5148 jitter, J m = 100ms. Jitter is selected within [0, 100] ms (mean, 50ms). For each of the five settings, two different strategies of RREQ forwarding scheme are considered:

• Shortest-path RREQ forwarding. The routers attempt to build the shortest path to the destination, i.e., the intermediate routers will forward the RREQ with shorter path, even if this RREQ has been already processed before.

This approach is used in most of the implementations like [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]. • Shortest-delay RREQ forwarding. The routers only forward the RREQ that arrives first. All the following RREQ messages are ignored, even if it traveled through a better path. This might result in non-optimal paths.

B. Simulation Results

1) Shortest-path RREQ forwarding: The first observation that can be from the shortest-path RREQ forwarding results is that the use of standard jitter, with the distribution specified in RFC 5148, does not have an outstanding impact on the RREQ flooding performance, when compared with the nojitter setting -neither in terms of collisions, control overhead or data path length. Differences can be observed, in contrast, between window jitter settings and the other settings.

Figure 6(a) shows the number of collision with different density of nodes (routers). The setting with no jitter has the highest number of collisions, slightly higher than the standard jitter settings, because adjacent nodes are more likely to retransmit received RREQs at the same time. The window jitter (50-100 ms, 100-150 ms) settings have significantly less collisions, especially in high-density scenarios. This is because the use of the window jitter setting enables forwarding routers to reduce the number of transmissions (i.e., overhead) by reducing the cases of delay inversion, as shown in Figure 6 Concerning the evolution of route discovery delay (i.e., the time between RREQ transmission and reception of the corresponding RREP) with respect to the network density in the shortest-path RREQ forwarding strategy (Figure 7(b)), it is interesting to observe that the impact of the evaluated jitter settings is different for low-density and high-density networks. In the first case, the average route discovery delay for each jitter setting is strongly related to the mean of the jitter random variable: with higher jitter means present higher average delays in the route discovery processes. For denser networks, in contrast, window jitter distributions present a better performance in terms of route delivery delay than standard jitter distributions, regardless of the mean value of the jitter random variable. The use of standard jitter distributions (or the immediate retransmission of RREQ messages, without jitter) in dense networks leads to an explosion of control traffic when the shortest-path RREQ forwarding strategy is used. This control traffic explosion can be indirectly observed in the evolution of the number of packet collisions in the network (Figure 6(a)) and the data packet delivery ratio (Figure 7(a))as the control traffic load grows beyond the network capacity, a more significant fraction of transmitted data packets cannot be correctly delivered even when routes are available, due to the increasing number of packet collisions.

By reducing substantially the probability of delay inversion, the use of window jitter distributions improves the quality of the selected routes (see Figure 7(c)) and allows to reduce the number of Route Replies sent in response to a Route Request. This alleviates the control traffic load of the network and decreases the number of packet collisions, therefore reducing significantly the average delay for route discovery processes.

2) Shortest-delay RREQ forwarding: As a comparison study, the shortest-delay RREQ forwarding approach is also simulated. Because only the first RREQ is forwarded, the network tends to have the same overhead, therefore the number of collisions is similar in different jitter settings, as shown in Figure 8(a) -the number of collisions in no-jitter settings, in contrast, is obviously higher. In this situation of similar control traffic overhead, those settings using windows jitter distributions have longer average route discovery delay, as expected (Figure 8(b)) -they have also higher mean values for the jitter values.

However, because the intermediate nodes simply forward the RREQ that arrives first, and all the following RREQs are ignored, the no jitter and normal jitter settings got sub-optimal routes. In the meantime, with window jitter, a much shorter routes can be explored, as illustrated in Figure 8(c). This is more interesting for less time-critical but power-constrained networks (such as sensor networks).

VI. CONCLUSION

The use of jitter for flooding has proved beneficial for wireless networks: by adding a random delay before forwarding a broadcast message, the number of collisions can be substantially reduced. Proactive routing protocols, such as OLSR, has found the use of an uniformly distributed jitter on flooded link-state messages to dramatically improve performance, and this has therefore been recommended in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF].

Alas, in case of route discovery in reactive routing protocols, this recommendation is less beneficial: using an uniform distribution of jitter for when flooding RREQ messages for the delays has some very undesirable effects, including that, with non-negligible probability, the route discovery process of such reactive protocols may result suboptimal routes towards requested destinations. This paper has identified and quantified this effect, called delay inversion.

In order to reduce the probability and impact of delay inversion, this paper proposes a modified jitter distributionwindow jitter: in its most general version, it consists of taking the quality of traversed links into account in the computation of jitter delays before retransmission of RREQ by intermediate nodes. This, in a way such that messages are forwarded faster over better links, and therefore a higher probability of the route discovery process resulting optimal routes. Theoretical analysis of window jitter (with hop count metrics, although the results generalise to also other metrics) shows that, despite its simplicity, this modification is able to, very substantially, reduce the probability of experiencing the effect of delay inversion, manifested by sub-optimal routes resulting from the route discovery process, with the cost of slightly increasing the route discovery delay. The benefits of the window jitter distribution, as compared to the uniform jitter distribution recommended in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], are also confirmed by way of simulations.

Figure 1 .

 1 Figure1. Use of jitter for flooding. Node A transmits a broadcast packet. Node B and C receive the packet at the same time and have roughly the same processing time. A collision will occur without jitter (the shadow in the shared channel). With jitter, the probability of a packet collision can be substantially reduced.

  Topology example. Node A tries to broadcast an RREQ message through the network, through paths p 1 and p 2 .

Figure 2 .

 2 Figure 2. An example of delay inversion

Figure 3 (

 3 Figure 3(a) illustrates the theoretical values for the probability of inversion for different values of n and m, i.e., the probability that a path of m hops performs faster forwarding than a path of length n.Figure 3(b) displays the same probability for different values of path length m, for cases in which n < m. Both the theoretical values and the results from a discrete-event simulation (each point corresponding to the averaged value over 200 samples) are displayed. Note that both Figures 3(b) shows bidimensional cuts of the surface presented in Figure 3(a) -these cuts result from the intersection of this surface with planes π 1 : {m = ct.} and π 2 : {∆ = m -n = ct.}, respectively.Expression[START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF] indicates that the delay inversion occurs, under the conditions specified in RFC 5148[START_REF] Clausen | Jitter Considerations in MANETs[END_REF], with a significant probability.

Figure 3 . 1 >

 31 Figure 3. (a) Theoretical value of P 1 ≡ P (D (n,m) 1 > 0), for 1 ≤ n ≤ 6, 1 ≤ m ≤ 6; (b) Restriction of P 1 for m = 1, 2, 3, 4, 5, n < m (theoretical values in lines, simulations in points).

  0

Figure 4 .

 4 Figure 4. PDFs of random variables T j based on RFC 5148 [5] and T * j

∈Proposition 2 .

 2 [0, n + m], and 0 otherwise. Therefore, the probability of delay inversion with paths of length n and m, P (D (n,m) 2 > 0)| n<m , can be computed as indicated in Proposition 2: The expression of P 2 ≡ P (D (n,m) 2

Figures 5

 5 Figures 5(a) and 5(b) show the value of D (n,m) 2

Figure 5 . 2 >

 52 Figure 5. For α = 1 2 , (a) Theoretical value of P 2 ≡ P (D (n,m) 2 > 0), for 1 ≤ n ≤ 6, 1 ≤ m ≤ 6; (b) Restriction of P 2 for m = 1, 2, 3, 4, 5, n < m (theoretical values in lines, simulations in points).

Figure 5 (

 5 Figure 5(b) shows the probability of delay inversion for the modified distribution of jitter values, depending on the difference ∆ = m -n, for different values of n and m.As in figure3(b), theoretical values (lines) and simulations (points, each of them averaged over 200 samples) are displayed together. It can be observed that the values are substantially lower than those achieved with T j ∼ U nif orm[0, J m ]: for very similar (∆ = m-n = 1, which is the most frequent case) and long paths (n = 5), the probability reduces in a factor 5 and stays below the 6%; the relative variation becomes still more significant as paths are shorter.

  (b).

Figure 6 .

 6 Figure 6. Simulation results of shortest-path RREQ forwarding

Figure 7 .Figure 8 .

 78 Figure 7. Simulation results of shortest-path RREQ forwarding

•

  Standard RFC 5148 jitter, J m = 200ms. Jitter is selected within [0, 200] ms (mean, 100ms).

	• Window jitter, α = 1 2 , J m = 100ms. Jitter is selected
	within [50, 100] ms (mean, 75ms).
	• Window jitter, α = 2 3 , J m = 150ms. Jitter is selected
	within [100, 150] ms (mean, 125ms).


Juan Antonio Cordero

Jiazi Yi

Thomas Clausen
email: thomas@thomasclausen.org

Optimization of Jitter Configuration for Reactive Route Discovery in Wireless Mesh Networks

Jitter is a small, random variation of timing before message emission that is widely used in non-synchronized wireless communication. It is employed to avoid collisions caused by simultaneous transmissions by adjacent nodes over the same channel. In reactive (on-demand) routing protocols, such as AODV and LOADng, it is recommended to use jitter during the flooding of Route Request messages. This paper analyzes the cost of jitter mechanisms in route discovery of on-demand routing protocols, and examines the drawbacks of the standard and commonly used uniformly distributed jitter. The main studied drawback is denominated delay inversion effect. Two variations on the jitter mechanism -window jitter and adaptive jitter-are proposed to address this effect, which take the presence and the quality of traversed links into consideration to determine the perhop forwarding delay. These variations allow to effectively reduce the routing overhead, and increase the quality of the computed paths with respect to the standard uniform jitter mechanism. Simulations are also performed to compare the performance of different jitter settings in various network scenarios.

I. INTRODUCTION

Since the late nineties, the MANET (Mobile Ad-hoc Networks) working group of the Internet Engineering Task Force 1 has been investing substantial efforts in developing routing protocols for MANET and wireless mesh networks.

In this kind of self-organized and decentralized networks, channel collisions (i.e., collisions due to the simultaneous transmission of adjacent nodes over the same channel) constitute an important source of packet losses.

A. Packet Collisions and Jittering Techniques

Different ways have been explored to address this issue and minimize its impact in wireless multi-hop networks. Classic MAC (Medium Access Control) collision avoidance mechanisms [START_REF] Kleinrock | Packet switching in radio channels: Part i -carrier sense multiple-access modes and their throughput-delay characteristics[END_REF] [START_REF] Karn | Maca, a new channel access method for packet radio[END_REF] are not suited to current wireless mesh scenarios and are unable to solve all possible cases of collisions (e.g., broadcast or multicast transmissions, collisions between non-neighboring nodes). Recent research efforts [START_REF] Yu | Multi-channel assignment in wireless sensor networks: A game theoretic approach[END_REF], [START_REF] Wu | Realistic and efficient multichannel communications in wireless sensor networks[END_REF] have focused on other alternatives, such as the use of multi-channel assignments in wireless sensor networks. These approaches are able to reduce the problem of collisions in potentially dense networking scenarios, at the cost of adding an additional complexity layer (or relying on previous knowledge of the network topology) and renoncing to the semibroadcast capability [START_REF] Chakeres | Mobile Ad hoc Network Architecture[END_REF] of the wireless network. 1 IETF MANET working group: http://datatracker.ietf.org/wg/manet/.

According to IETF, the problem of packet collisions in a wireless multi-hop mesh network can be further alleviated by introducing jitter (a small, random delay on transmissions) in the network layer. In RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], the use of jitter is recommended for MANETs and wireless mesh networks as a simple collision avoidance mechanism for routing protocol control traffic, such as periodically scheduled packets, or event-triggered packets.

For reactive protocols such as AODV (On-demand Ad hoc Distance Vector routing protocol [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF]) and LOADng (Lightweight On-demand Ad hoc Distance Vector Routing protocol -Next Generation [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]), jitter is recommended during route discovery. Route Request messages are flooded in the network until they reach their destination. In these flooding processes, concurrent retransmissions of the same message by adjacent nodes cause collisions.

B. Related Work

After the standardization of jittering techniques by the IETF [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], and their implementation in different routing protocols, there has been some research to evaluate and discuss the impact of these techniques in the performance of the protocols making use of them. [START_REF] Cordero | Impact of jitter-based techniques on flooding over wireless ad hoc networks: Model and analysis[END_REF] introduced an analytical model for investigating the impact of the standardized jitter mechanism on network-wide packet dissemination, and studied and quantified the additional delay incurred, the reduction in number of transmissions, and the effect of jitter in packet size. [START_REF] Friedman | Jittering Broadcast Transmissions in MANETs: Quantification and Implementation Strategies[END_REF] presented the relationship between the maximal jitter duration and the probability of successful transmission, and provided a comparison between different strategies of implementing jitter mechanisms. [START_REF] Friedman | Jittering Broadcast Transmissions in MANETs: Quantification and Implementation Strategies[END_REF] concluded that implementing jitter at any layer above IP (e.g. at the transport or application layer) brings virtually no benefits. Finally, [START_REF] Yi | Jitter Considerations in On-Demand Route Discovery for Mobile Ad Hoc Networks[END_REF] began to explore variations in the jitter distribution, in a research workline that is continued in this paper.

C. Statement of Purpose

This paper studies the optimization of jitter mechanisms for route discovery of reactive protocols. During route discovery, Route Request messages are flooded through the network in order to discover available routes from (requesting) source to (requested) destinations. A Route Request message is rebroadcast immediately after first received by an intermediate node.

Jitter is thus used to reduce the probability that neighboring nodes will transmit at the same time.

With the method introduced in [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], jitter values are distributed uniformly between 0 and a maximum value J m . While this can reduce the collisions by randomizing the adjacent transmission, the uniform distributed jitter also brings side effects, in particular more routing overhead and sub-optimal paths.

In this paper, the jitter behavior is first analyzed to investigate its impact on network performance. Two variations on the mechanism described in RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] -window jitter and adaptive jitter-are then proposed to reduce the routing overhead and discover better quality (closer to optimal) paths. Different settings are implemented and compared in simulations.

D. Paper Outline

The remainder of this paper is organized as follows: section II introduces the background of reactive protocols for mesh networks and the jitter technique used for message flooding. In section III, the drawback of uniform distributed jitter, named delay inversion effect, is analyzed, and followed by the proposal of adaptive jitter mechanism. A performance study and a comparison of different jitter mechanisms are presented in section IV. The paper is concluded in section V.

II. REACTIVE PROTOCOLS AND APPLICATION OF JITTER

This section describes the basic operations of the reactive protocol in wireless ad hoc and mesh networks. Then the jitter mechanism and its impact on flooding performance are briefly introduced and discussed.

A. Basic Operations of On-demand Routing Protocols

In reactive protocols, routes are computed on demand, i.e., only when a data transmission to an unknown destination is expected. Acquisition and maintenance of routes are based on two mechanisms: route discovery and route maintenance.

1) Route Discovery: Route REQuest (RREQ) messages are flooded through the network until they reach the sought destination -at which point that destination generates an RREP (Route REPly), which is unicast along the reverse path to the RREQ source. RREQ and RREP messages carry a monotonically-increasing sequence number, permitting both duplicate detection and detecting which of two messages contains the most "fresh" information. Two flooding modes are possible: the shortest-delay mode and the shortest-path mode. Depending on the flooding mode, RREQ forwarding and RREP generating rules may be slightly different.

Under the shortest-delay mode, routers in the network only forward the first RREQ message received from a given source to a given destination -forthcoming RREQs with the same pair (src, sequence number) will be dropped, even if they advertise better paths than the first one. The requested destination behaves similarly: it only sends back one RREP upon the first reception of an RREQ from a given source.

Routes discovered in this mode may be thus suboptimal, but they are acquired with minimal delay.

In contrast, under the shortest-path mode, routers may forward or reply to an RREQ message several times, if the traversed route is better than the one traversed by previously forwarded/replied RREQs. This improves the quality of the acquired routes, at the cost of increasing considerably the overhead associated to route discovery processes.

2) Route Maintenance: It is performed when an actively used route fails, i.e., when a data packet cannot be delivered to the next hop towards the intended destination. On detecting that a route has failed, a Route Error (RERR) message is generated. On receiving such an RERR message, the source of the failed data packet can initiate a new Route Discovery procedure to re-establish connectivity.

B. Jitter Technique for Route Request (RREQ) Flooding

Simultaneous packet transmissions -as those performed in reactive protocols during Route Discovery processes-are likely to cause packet losses in wireless mesh networks, due to collisions between concurrent transmissions of routers having (at least) a common neighbor. In order to prevent or minimize these collisions, RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] recommends the use of jitter for different cases in which packets may be expected to be sent concurrently. Several well-known reactive protocols (e.g., AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF], LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF]) use or provide support to jitter when flooding RREQ packets over a wireless mesh network.

Without jitter, a router receiving an RREQ packet to be forwarded retransmits it immediately after processing. As retransmissions in neighboring routers are triggered by this single event (the reception of the RREQ packet), there is a high probability of collision. Instead, when using jitter, every receiving node adds a small, random delay before rebroadcasting the RREQ packet. RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] recommends that delays are selected following an uniform distribution between 0 and a maximum jitter value, J m . Note that this is the maximum entropy distribution among those assigning continuous jitter values between 0 and J m [START_REF]Entropy Measures, Maximum Entropy Principle and Emerging Applications[END_REF]: the use of this distribution thus maximizes the randomness of the total delay suffered by an RREQ packet sent along a certain path.

Other than prevention of packet collisions from simultaneous transmissions, the use of jitter in flooding has two immediate additional effects:

(i) the RREQ flooding, and therefore the route discovery, is slowed, and (ii) nodes need larger buffers to store packets that have been received, but not yet forwarded. The trade-off between these drawbacks and the reduction in the probability of collisions can be controlled by way of the length of the jitter interval, J m [START_REF] Cordero | Impact of jitter-based techniques on flooding over wireless ad hoc networks: Model and analysis[END_REF].

III. JITTER: UNIFORM, WINDOW AND ADAPTIVE DISTRIBUTIONS

This section analyzes the delay inversion effect, a side effect of uniform distributed jitter observed when performing Route Request (RREQ) flooding. Two variations on jitter distribution -window jitter and adaptive jitter-are then proposed and examined to alleviate this side effect.

A. The Delay Inversion Effect

The fact that RREQ messages reach their destination with a uniformly-distributed delay at each intermediate hop presents some drawbacks, in terms of path sub-optimality and/or control traffic inefficiency.

Consider the topology shown in Figure 1, and assume that node A floods (broadcasts) an RREQ to identify a route towards D. Under normal operation of a reactive routing protocol (without jitter), the RREQ would reach D through the path p 2 = {A, E, D} faster than through the path p 1 = {A, B, C, D}, assuming that processing times at each intermediate node, before retransmission, are similar. If a uniform random distribution [0, J m ] is used at each hop to determine an additional delay before retransmission, the message copy sent through the longer path (in number of hops), p 1 , may reach the destination faster than the message copy over p 2 with a non-negligible probability. The example of Figure 2 illustrates this case. Consider the transmission of an RREQ packet from A, received simultaneously at B and E. Although the RREQ needs to traverse two hops (B and C) to reach D via p 1 , and only one (E) via p 2 , the RREQ sent across p 1 would be received first at D if j E > j B + j C , as shown in Figure 2.

Router D would reply to the Route Request from A with an RREP that advertises path p 1 , which is suboptimal. When the RREQ traversing p 2 reaches D, D would reply again to A's Route Request with the (shorter) path p 2 . This implies that A would get, and possibly use for a certain amount of time, a suboptimal path towards D (p 1 ), and it would need two RREP from D in order to learn the optimal path from A to D. If D was not the destination of the requested route, but only an intermediate router towards that destination, then D would retransmit the RREQ twice as it is received from p 1 and then p 2 .

This example illustrates that the use of uniform random distribution for jitter values when forwarding RREQ packets during route discovery in a reactive routing protocol may lead to cases in which "transmissions over longer paths get first". This effect is hereafter denominated delay inversion caused by jitter, and is more frequent in long paths (in number of hops), due to the fact that the range in which total jitter values are possible (adding all per-hop jitter values) has a linearly growing upper bound (nJ m , where n is the path hop length) and a fixed lower bound set to 0 [START_REF] Yi | Jitter Considerations in On-Demand Route Discovery for Mobile Ad Hoc Networks[END_REF]. Delay inversions are harmful due to at least three undesirable effects:

(i) increase of sub-optimality of reported routes, (ii) growth of unnecessary RREQ broadcast traffic, and (iii) growth of unnecessary RREP (unicast) traffic.

B. The Window Jitter

The window jitter distribution modifies the uniform distribution of RFC 5148 by introducing a minimum jitter interval in each hop. Jitter values are then instances of a random variable

T J W ∼ U nif orm[αJ m , J m ],
where α ∈ (0, 1) and αJ m is a minimum jitter value. Note that α = 0 corresponds to the uniform jitter distribution specified in RFC 5148, α = 1 would imply a deterministic delay (of length J m ). The fact that α = 0 entails that the lower bound for the RREQ delay grows linearly with the length of the traversed path.

Figure 3 shows the probability density functions (PDFs) for the jitter value as specified in RFC 5148 (T J U ) and the modified jitter random variable (T J W ). The window jitter reduces the randomness and increases the (deterministic) dependency of the total RREQ delay to the length n of the traversed path. When assigning jitter values according to the distribution of random variable J w , the total delay caused by jitter in a path of n hops belongs to the interval [nαJ m , nJ m ] (α = 0). The trade-off between randomness and path length deterministic dependence can be controlled by way of parameter α ∈ (0, 1): the closer α is to 1, the more deterministic becomes the total delay of an RREQ packet with respect to the path length.

0 1/((1-α)•J m ) J m pdf TJ W α•J m 0 1/J m J m pdf TJ U
Under the window jitter distribution, each additional hop in the path traversed by an RREQ packet causes at least an additional delay of αJ m . As shown analytically in [START_REF] Yi | Jitter Considerations in On-Demand Route Discovery for Mobile Ad Hoc Networks[END_REF],

this increases the probability that the RREQ packet traverses faster through a "shorter" path, in number of hops, rather that through a "longer" path, which is considered worse for routing. This model thus assumes that longer paths are preferable to shorter paths, that is, a hop count metric is implicitly assumed.

C. The Adaptive Jitter for Non-Trivial Metrics

The window jitter principle can be naturally extended to non-trivial link metrics, for instance based on probability of successful transmission (ETX [START_REF] De Couto | A highthroughput path metric for multi-hop wireless routing[END_REF]) or available bandwidth in the link. This extension of window jitter to link metrics other than hop count is denominated adaptive jitter.

Given a link quality indicator LQ ∈ (0, 1) (LQ -→ 1 for high quality links), jitter values are selected uniformly within the interval [(1 -LQ)J m , J m ]. This reduces the probability of delay inversion or, equivalently, increases the probability that an RREQ packet is forwarded faster by routers receiving it on better links.

Note that the window jitter distribution presented in section III-B corresponds to the particular case of LQ = 1 -α for all available links.

IV. SIMULATIONS AND RESULTS

To evaluate the performance of different jitter mechanisms, simulations are performed. In this section, the simulation results are presented with further discussion.

A. Simulation Setup

The performance of the three different jitter configurations (standard, window and adaptive) is evaluated in shortest-delay mode and shortest-path mode of RREQ flooding (see section II-A1) for different network scenarios. Network scenarios are characterized by triplets (N, ρ, metric), where:

• N stands for the network population (number of nodes),

• ρ stands for the network density (number of nodes per km 2 ), and • metric identifies the link metric model -uniform (hop count, in which all available links have cost 1) or random (links have a random integer cost from 1 to 10). Values for each network profile are averaged over 20 samples, each sample corresponding to a random distribution of nodes over the network grid, in which RREQs are sent from a fixed random source to a fixed random destination. Each value related to a distribution corresponds to the average of 10 RREQ floodings simulated between source and destination.

The following aspects are used to evaluate the performance of different jitter mechanisms:

• Number of collisions. A collision is counted when a router receives two transmissions simultaneously. • Optimality index. It measures the quality of discovered paths. Given a source s and a destination d, the optimality index for a path between s and d is the quotient of the cost of this path and the cost of the shortest (minimal) path between s and d. • Routing overhead. The number of RREQ or RREP retransmissions.

• Route discovery delay. In shortest-delay mode, it is the time required to obtain the first path. In shortest-path mode, it is the time to discover the best path.

B. Impact of Parameters and Considerations

Jitter distribution is characterized by way of two parameters: the maximum jitter value, J m (used in all three configurations); and the α parameter (α ∈ (0, 1), used only in window and adaptive jitter variations), such that αJ m is the nonzero minimum jitter value. It is assumed that J m has the same value for all routers in the network, and satisfies the recommendations of RFC 5148 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF]. In the window jitter, α is a fixed value, the same for all routers in the network; in the adaptive jitter, α = 1 -LQ depends on the link quality value and therefore may change during the network operation.

The effect of these two parameters in the performance of each configuration is relatively straightforward. In [START_REF] Yi | Jitter Considerations in On-Demand Route Discovery for Mobile Ad Hoc Networks[END_REF] it was proven that changes in the absolute value of J m have no impact in the delay inversion effect. For simplicity, simulations in this section assume J m = 1sec.

As indicated in section III-B, the value of α traduces the trade-off between randomness and (deterministic) influence of the path quality. Consequently, as α approaches 1, forwarding delays become more deterministic (and longer), the delay inversion effect becomes more rare and collisions are more likely (and inversely when α -→ 0). As this behavior is immediate from the parameter definition, this section focuses on the comparison between the different configurations, rather than on the impact of the variation of these parameters. For simplicity and clarity in the evaluation, the figures are shown for J m = 1sec (for all configurations) and α = 0.5 (for window jitter).

C. Simulation Results and Discussion

1) Uniform link metrics: The simulation of the shortestpath mode of route discovery in networks with uniform link cost (hop count) shows that window jitter configuration is able to reduce significantly the number of collisions caused by RREQ flooding, when compared to the standard jitter configuration. Figure 4 shows that the collision reduction becomes more relevant as the network density grows. This reduction is due to the fact that the use of window jitter, compared with standard jitter, increases the probability that the first RREQ received by an intermediate router (or a destination) has traversed the shortest path (according to the metric in use) available, and therefore no additional RREQ retransmissions need to be performed (and no additional Route Replies need to be sent after the first one) over a path with better quality than the one previously advertised. The better the quality of the first advertised path, the fewer control packets (RREQ and RREP) involved in a single Route Discovery process, and the less likely packet collisions. Improvement of discovered route quality can be observed through of the optimality index in shortest-delay mode. Figure 5 illustrates the optimality index of window jitter and uniform jitter depending on the network density. When routers are only allowed forward the first RREQ received from a given source towards a given destination, the use of window jitter improves significantly the quality of the routes identified through RREQ flooding. This confirms the results from the theoretical analysis of [START_REF] Yi | Jitter Considerations in On-Demand Route Discovery for Mobile Ad Hoc Networks[END_REF] about the probability of delay inversion in standard jitter and window jitter. As mentioned in section III-B, window jitter relies on the principle that RREQs traversing less hops are preferable (better) to RREQs traversing more hops, and therefore the later should be delayed with respect to the former -it implicitly assumes a constant link metric, and it is able to provide a significant improvement in the route discovery performance when no more information about link quality is available.

2) Shortest-delay mode over non-trivial link metrics: The advantages of window jitter with respect to standard jitter, however, become less significant when link metrics are not uniform: the ability to identify better paths by introducing fixed minimum delays (αJ m ) per hop degrades, as Figura 6 indicates. For these cases, the use of the adaptive jitter presented in section III-C reveals more adequate, according to simulation results. This is because routers using adaptive jitter can take the actual link metric (e.g., ETX, bandwidth, etc.) into consideration, rather than the single presence of these links in the path.

Figure 6(a) shows that adaptive jitter clearly outperforms window jitter and standard jitter in terms of optimality index. As shown in Figure 6(b) for random link quality values, this benefit from the adaptive jitter is compatible with a low level of packet collisions (similar to the level achieved with window jitter, and significantly lower than the level achieved with standard jitter) in networks with heterogeneous link qualities (i.e., non-uniform metrics). Discrimination of RREQs based on quality of traversed links is performed by introducing pre-forwarding delays. This entails a trade-off between RREQ path optimality and RREQ forwarding delay, as it can be observed in Figure 7 for the three considered jitter configurations: in general, the better the path indicated in the first RREQ received by the intended destination, the more delay between the RREQ transmission by the source and its reception in the destination. This can be observed, in particular, for networks of constant node density (Figure 7(b)). Results from Figure 7(a) indicate, in addition, that additional delay caused by adaptive jitter with respect to window jitter strongly depends on the network density: as more paths are available to reach the destination (because the network is denser), heterogeneity of the quality of the involved links in flooding is also higher and the adaptive jitter configuration allows to deliver Route Requests (RREQs) faster, while window jitter configuration cannot reduce the per-hop delay beyond a minimum value αJ m .

3) Shortest-path mode over non-trivial link metrics: The use of adaptive jitter in the shortest-path mode of route discovery is also beneficial, although not due to the same reasons (RREQ path quality improvement, mainly) as in the shortest-delay mode. The fact that routers are able to forward RREQs indefinitely, any time that they receive a RREQ with a better route than the last forwarded RREQ, entails that RREQ flooding ideally provides the optimal route between source and destination, if it terminates successfully (without packet losses, collisions or inaccuracies in link quality estimation). However, the shortest-path mode with static jitter configurations (standard jitter, window jitter) presents a relevant drawback: as every packet may forward each RREQ several times, and the source may send several RREP to the same destination, probability of packet collisions and route discovery failure also increases -more significantly for dense networks. Figures 8(a) and 8(b) show the evolution of RREQ retransmissions and RREP transmissions per route discovery, when the network density increases. It can be observed that the use of adaptive jitter, by increasing the quality of the firstly-discovered paths, entails a reduction in the number of control packets per route discovery (RREQ retransmissions and Route Replies) up to 30%, with respect to the static configurations.

Figure 9 shows the average RREQ delays for the different jitter configurations when using shortest-path (sh-p) and shortest-delay (sh-d) modes. For any given configuration, delay for the shortest-path mode is always longer or equal to the delay for the shortest-delay mode: in the later, the flooding terminates when the destination receives the first RREQ; in the former, the flooding terminates when the destination receives the RREQ through the best path, which can correspond to the first or to a posterior reception. More interestingly, two observations can be drawn from Figure 9. In first term, RREQ delay caused by adaptive jitter decreases with the network density (a result consistent with what was shown in Figure 7), while, in contrast, standard and window jitter present in the shortest-path mode a roughly constant delay with respect to network density. In second term, the gap between RREQ delays in shortest-path and shortest-delay modes, i.e., the additional delay caused by reception in the destination of better RREQ packets later to the first, is different for each configuration. The adaptive jitter configuration has the smallest gap between modes, which is consistent with the previous observation about the quality of first-received RREQs at the destination. The significant difference between modes when using window jitter is another indication, in turn, of the poor performance achieved by this configuration in networks with diverse link qualities -as the non-trivial link metrics scenarios considered in this section.

V. CONCLUSION

The use of jitter for packet flooding has been proved beneficial in wireless mesh networks. The addition of a random delay before retransmission of a flooded packet helps reducing the number of collisions due to concurrent wireless transmissions from neighboring nodes. Jitter techniques for flooding, as specified in RFC 5148, present however significant side-effects when employed in route discovery processes of reactive routing protocols, that need to be taken into account: in previous work [START_REF] Yi | Jitter Considerations in On-Demand Route Discovery for Mobile Ad Hoc Networks[END_REF], it was identified the delay inversion effect, by which the use of jitter may lead the network to select suboptimal routes between sources and destinations.

This paper explores and evaluates different settings in the statistical distribution of jitter values in order to minimize this effect, following the work started in [START_REF] Yi | Jitter Considerations in On-Demand Route Discovery for Mobile Ad Hoc Networks[END_REF]. Two modifications over the distribution of RFC 5148 are studied via network graph simulations: the window jitter distribution and the adaptive jitter distribution. For both configurations, the impact in the RREQ flooding performance is measured for different link metrics, showing that they are able to improve substantially the quality of the discovered routes (and therefore, reducing the amount of involved control packets and the probability of collisions), at the cost of increasing the delay of RREQ flooding. Depending on the intended application (e.g., data collection and transmission with long sampling periods in wireless sensor networks), this additional delay may be a reasonable price for acquiring and using better routing paths.

Window jitter outperforms standard jitter in hop-count networks, but performs poorly when link quality values are heterogeneous. In these scenarios, the adaptive jitter presents clear advantages with respect to the two static configurations (standard and window jitter). When route discovery is performed in shortest-delay mode, adaptive jitter enables routers to discover significantly better paths than those obtained otherwise. Under the shortest-path mode, route quality is similar for all settings, but adaptive jitter reduces the number of RREQs and RREPs up to 30%. There is still a trade-off between route quality and flooding delay, meaning that the use of adaptive jitter entails slower flooding processes than standard or window jitter, but this additional delay becomes less significant as the network density grows: in dense networks, adaptive jitter causes flooding delays comparable to window jitter, with a substantially less overhead and optimal paths. This property makes it more interesting in resource constrained networks, such as battery charged mesh networks and sensor networks.

Figure 1 .

 1 Figure 1. Topology example. Node A tries to broadcast an RREQ message through the network, through paths p 1 and p 2 .

Figure 2 .

 2 Figure 2. Example of jitter values assignement for an RREQ from A towards D, in the topology of Figure 1. RREQ through longer path {A, B, C, D} travels faster than the one through shorter path {A, E, D} .

Figure 3 .

 3 Figure 3. PDF of random variables T J U (RFC 5148), T J W (window jitter).

  Collisions per Route Request (RREQ) Flooding (Fixed grid length l=1000m, uniform link metric, shortest-path mode) Standard Jitter, mean µ Standard Jitter, std.dev. σ Window Jitter, α=0.5, mean µ Window Jitter, α=0.5, std.dev. σ

Figure 4 .

 4 Figure 4. Number of collisions, shortest-path RREQ forwarding

Figure 5 .

 5 Figure 5. Optimality index, shortest-delay RREQ forwarding

Figure 6 .

 6 Figure 6. Shortest-delay RREQ flooding

Figure 7 .

 7 Figure 7. Route discovery delay, shortest-delay RREQ forwarding

Figure 8 .

 8 Figure 8. Route overhead per route discovery, shortest-path RREQ forwarding

Figure 9 .

 9 Figure 9. Route discovery delay, shortest-path and shortest-delay RREQ forwarding


Jiazi Yi

Thomas Clausen
email: thomas@thomasclausen.org

Antonin Bas
email: antonin@antonin-bas.fr

Smart Route Request for On-demand Route Discovery in Constrained Environments

A derivative of AODV, denoted LOADng, is proposed for use in very constrained environment, sacrificing a number of features from AODV for the benefit of smaller control messages and simpler processing logic. Among these sacrifices is intermediate route replies. This paper presents an alternative to intermediate router replies, denoted Smart Route Request, which provides an optimization similar to that attainable by intermediate route requests, but without imposing additional processing complexity or additional signaling. A performance study is presented, showing that the use of Smart Route Requests can effectively reduce the control traffic overhead from Route Requests, while retaining the simplicity of LOADng. LOADng with Smart Route Requests effectively reduces control traffic overhead and on-link traffic collisions, and this especially for multipoint-to-point traffic.

I. INTRODUCTION

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

The MANET working group converged on the development of two protocol families: reactive protocols, including AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], and proactive protocols, including Optimized Link State Routing (OLSR) [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF]. A distance vector protocol, AODV operates in an on-demand fashion, acquiring and maintaining routes only while needed for carrying data, by way of a Route Request-Route Reply exchange.

After acquiring operational experiences, the MANET working group commenced developing successors to OLSR and AODV, denoted OLSRv2 and DYMO. Whereas a relatively large and active community around OLSR thus standardized OLSRv2 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF], [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF], [START_REF] Clausen | Representing Multi-Value Time in MANETs[END_REF], [START_REF] Clausen | Mobile Ad Hoc Network Neighborhood Discovery Protocol[END_REF] and [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], the momentum behind DYMO withered in the MANET working group 2 . However, other derivatives of AODV have been implemented and used widely, such as IEEE 802.11s [START_REF] Hiertz | Principles of ieee 802.11s[END_REF], and the G3-PLC standard [START_REF] Itu-T G | Narrow-Band OFDM power line communication transceivers -Data link layer specification[END_REF], published in 2011, specifies the use of LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] (a simplified version of AODV) at the MAC layer, for providing mesh-under routing for utility (electricity) metering networks. Spurred by these experiences, 2011 saw the emergence of LOADng [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocolnext generation[END_REF], as a successor to LOAD.

A. Statement of Purpose

For on-demand routing protocols, like AODV and its derivatives (LOAD, LOADng), the route discovery process is the most costly operation in terms of control traffic overhead: a Route Request (RREQ) message is flooded through the whole network, with the sought destination replying by unicasting a Route Reply (RREP). In order to reduce the RREQ flooding overhead, AODV makes use of intermediate RREPs: a router, which is not the sought destination but which has a valid route to the destination, does not re-flood the RREP but rather transmits in unicast an intermediate RREP to the source, and a gratuitous RREP to the sought destination. Thus, AODV makes use of existing routing information present in the network to "cut short" the RREQ flooding process -at the expense of more sequence numbers in control packets (and more complex processing) in order to avoid generating loops. LOAD and LOADng eliminate intermediate RREP, and permit only the sought destination to reply to a RREQ, so as to prevent loops -with the motivation being that in constrained environments, it is necessary to be draconian in reducing the control message sizethe state that a router needs to maintain, and to and the complexity of protocol operation. Alas, it is evident that in certain scenarios, this elimination to not existing routing information can cause more control messages to be required for protocol operation.

This paper presents a simple mechanism, SmartRREQ, whereby the benefits of intermediate RREPs as known from AODV are enabled, whilst avoiding the inconveniences of larger control messages and additional state and processing complexity.

B. Paper Outline

The remainder of this paper is organized as follows: section II briefly introduces LOADng, by way of emphasizing the differences with AODV. Section III discusses intermediate RREQs, and introduces SmartRREQ. Section IV presents a performance evaluation of LOADng with and without the use of SmartRREQ, and finally section V concludes this paper.

II. ON-DEMAND ROUTING IN CONSTRAINED ENVIRONMENT: LOADNG

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

Compared to AODV, LOADng is extended to:

• Be modular, with a core specification defining simple and light-weight core functions of the protocol.

• Support optimized flooding of RREQs for control traffic reduction, and employs jitter to reduce the probability of losses due to collisions on lower layers [START_REF] Clausen | Jitter Considerations in MANETs[END_REF].

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

• Supports different routing metrics. Different metrics are supported, to make better use of link information from different layers. Compared to AODV, LOADng is simplified to:

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

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

III. EFFICIENT ROUTE DISCOVERY AND SMART ROUTE REQUEST

Reducing the overhead, delay and complexity of the route discovery process (RREQ/RREP exchange) is key to adapting on-demand routing protocols for use in constrained environments. In this section, the route discovery processes used in AODV and LOAD/LOADng are described, and the SmartRREQ mechanism is proposed.

A. Intermediate Route Replies: to be, or not to be.....

During the Route Discovery process of AODV, an intermediate router can generate an intermediate RREP in response to

an RREQ, if it has a valid route to the destination sought -and must also generate a gratuitous RREP and send this to the desired destination in order to establish a complete and bi-directional route. In order to avoid routing loops when permitting intermediate routers to generate intermediate RREPs, an RREQ in AODV carries an RREQ ID, destination sequence number, and originator sequence number in RREQ messages -recorded and maintained by intermediate routers, and used for when processing RREQs and RREPs.

In LOADng, intermediate RREPs are prohibited, so as to reduce the control message size and guarantee loop freedom. A router, receiving an RREQ, is either the ultimate destination -and, if so, must respond by an RREP -or is an intermediate router -and, if so, has to rebroadcast the RREQ, even if it otherwise has a valid route to the destination. [START_REF] Clausen | Loadng: Towards aodv version 2[END_REF] shows that LOADng is more adapted to constrained environments with lower routing overhead and less collisions.

While eliminating intermediate and gratuitous RREPs reduce the size of RREQ/RREPs, it might result in more RREQ (re-)transmissions. Consider the obvious case where a set of routers in the same part of the network topology, for example, all seek a route to a gateway: not using the topology information in intermediate routers will cause all RREQs to have to transverse the network, and RREPs to be sent back.

In some network types, such as sensor networks, it is common to have sensor-to-root (multipoint-to-point -or MP2P) traffic. While eliminating intermediate RREP can reduce the size of control message and simplify the protocol process, the side effect of blindly flooding RREQ cannot be ignored in this kind of scenarios.

B. Smart Route Request

To avoid blindly flooding RREQ in scenarios where MP2P traffic prevails, SmartRREQs is proposed. Retaining the lightweight nature of LOADng, and incurring no additional signaling, SmartRREQ takes benefits of existing routing information in intermediate routers.

On receiving an RREQ message, an intermediate router (neither source nor destination) performs the following procedure: 1) If the intermediate router has a valid route to the destination, AND the <next-hop> field of the corresponding routing tuple is not equal to the previous hop address of the RREQ, then the RREQ is unicast to the <next-hop>. 2) Otherwise the RREQ is broadcast as usual to all its neighbors. This is illustrated in figure 1: S solicitates a route to D. A and B already have routes to D, and upon receiving the RREQ initiated by S will unicast the RREQ, according to their routing table. When the RREQ arrives the destination, the RREP is unicast as to the source. With this, in some scenarios such as MP2P networks, in which the neighbor routers have already available routes to the destination, an RREQ message will stay local, rather than being flooded to the whole network. The RREQs will be unicast to the destination only. If an intermediate router detects a broken link when trying to send an unicast RREQ, then it should broadcast the RREQ instead.

IV. SIMULATION AND EVALUATION

The proposed SmartRREQ is implemented, studied and evaluated by way of network simulations using NS2. Simulations were made with from 50 to 500 routers, using IEEE 802.11 wireless interfaces, and placed statically and randomly in a square field of varying size.

The network is subject to point-to-point (P2P) traffic or multipoint-to-point (MP2P) traffic with routers generating 80 second bursts of 512-octet data packets every 5 seconds. The simulation results in different scenarios comparing LOADng with or without SmartRREQ, as well as comparing to AODV4 are be presented in this section.

A. Point-to-Point Traffic

For the purpose of studying P2P traffic performance, 50 to 100 routers were distributed randomly in a field of 1000m×1000m. The network was subject to 30 concurrent and random (source, destination) traffic flows. Given the low traffic load in these scenarios, LOADng, LOADng with Smart RREQ and AODV all attain identical packet delivery ratios of almost 100%.

Figures 2(a) and 2(b) show the number of collisions and the average control traffic overhead measured in number of bytes sent over the network, respectively. A first observation is, that LOADng transmits much fewer bytes across the network than AODV, and that using SmartRREQ reduces this overhead further. Additionally, LOADng yields fewer collisions than does AODV, and fewer still when using also SmartRREQ due to less control packets being flooded through the networks. The increased overhead and collisions from AODV is, in part, due to larger messages and in part due to AODVs use of expanding ring flooding. The average end-to-end delay is shown in figure 2(c). Compared to LOADng, using SmartRREQ yields a lower delay, due to the reduced number of collisions (which can result in more MAC layer retransmission). Alas, the delays are not quite as low as that attained by AODV: when using SmartRREQ, even if an intermediate router has a valid route to the destination, an RREQ will have travel (albeit in unicast) to the ultimate destination and an RREP returned, whereas for AODV an intermediate RREP is generated and immediately sent back from the intermediate router. Another reason of the longer delay of LOADng is because jitter [START_REF] Clausen | Jitter Considerations in MANETs[END_REF] is used, which introduces random delay at each transmission of RREQ message to reduce collision.

B. Multipoint-to-Point Traffic

For MP2P scenarios, larger networks and higher traffic loads are tested. The network has from 50-500 routers, with a single fixed router designated as the "root" -to which all the other routers send a data packet of 512-octet every 5 seconds. For all scenarios, the same router density is maintained, i.e.,, as the number of routers increase, so does the network field size.

The packet delivery ratio is shown in figure 3(a), showing that while the LOADng delivery ratio drops significantly , to as low as about 20% in a 500 router big network, using SmartRREQ and AODV, delivery ratios of 100% are attained. In fact, in MP2P scenarios, since every router has to maintain a route to the root, when one router initiates an RREQ message, its neighbors have a high probability of still having an active route to the root (as illustrated in figure 1). Thus, a network-wide RREQ flooding can be avoided, and the routing overhead significantly reduced. Due to the the high overhead and collision rate of blind RREQ flooding, LOADng also incurs also higher delays, as illustrated in figure 3(d).

V. CONCLUSION The proposed on-demand routing protocol for constrained environments, LOADng, sacrifices the intermediate/gratuitous RREPs of AODV, in order to provide a simpler protocol with smaller control messages, less state and complexity -and while still ensuring loop freedom. Alas, for some common scenarios, such as data acquisition networks, wherein all traffic terminates at a central collection point, this sacrifice is also at the expense of performance.

This paper proposes SmartRREQ as an alternative to the intermediate/gratuitous RREP of AODV. Maintaining the same mode of operation as LOADng, wherein only the ultimate destination for an RREQ is allowed to generate an RREP, SmartRREQ allows an intermediate router, which has a path to the sought destination, to retransmit a received RREQ in unicast to that destination, thereby eliminating flooding when possible. This requires no extra signaling or overhead, nor any extra processing, as compared to LOADng.

Figure 1 .

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

Figure 2 .

 2 Figure 2. Simulation results of P2P scenarios

Figure 3 .

 3 Figure 3. Simulation results of MP2P scenarios

http://www.ietf.org/

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

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

With Expanding Ring and intermediate/gratuitous RREPs.

This mechanism has been tested by way of network simulations, for which it is worth observing, that for all tested scenarios, LOADng with SmartRREQ attains the same data delivery ratios as does AODV, with identical or lower overheads (and less router state and simpler processing). AODV does, however, yield slightly lower delays. Compared to LOADng without SmartRREQ, significant improvements are obtained, according to all metrics studied. This allows the conclusion that SmartRREQ is an indispensable component for use in LOADng -yielding all gains and no griefs.