C Dearlove

T Clausen

Internet Engineering Task Force (IETF)

The Optimized Link State Routing Protocol version 2 (OLSRv2) includes the ability to assign metrics to links and to use those metrics to allow routing by other than minimum hop count routes. This document provides a historic record of the rationale for, and design considerations behind, how link metrics were included in OLSRv2.

Introduction

The Optimized Link State Routing Protocol version 1 (OLSRv1) [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] is a proactive routing protocol for mobile ad hoc networks (MANETs) [RFC2501]. OLSRv1 finds the shortest, defined as minimum number of hops, routes from a router to all possible destinations.

Using only minimum hop routes may result in what are, in practice, inferior routes. Some examples are given in Section 4. Thus, one of the distinguishing features of the Optimized Link State Routing Protocol version 2 (OLSRv2) [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF] is the introduction of the ability to select routes using link metrics other than the number of hops.

During the development of OLSRv2, the working group and authors repeatedly discussed how and why some choices were made in the protocol specification, particularly at the metric integration level. Some of the issues may be non-intuitive, and this document is presented as a record of the considerations and decisions to provide informational discussion about motivation and historic design choices. This document is intended to be useful as a reference if those questions arise again.

Use of the extensible message format [START_REF] Clausen | Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] by OLSRv2 has allowed the addition, by OLSRv2, of link metric information to the HELLO messages defined in the MANET Neighborhood Discovery Protocol (NHDP) [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] as well as inclusion in the Topology Control (TC) messages defined in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF].

OLSRv2 essentially first determines local link metrics from 1-hop neighbors, these being defined by a process outside OLSRv2, then distributes required link metric values in HELLO messages and TC messages, and then finally forms routes with minimum total link metric. Using a definition of route metric other than number of hops is a natural extension that is commonly used in link state protocols.

A metric-based route selection process for OLSRv2 could have been handled as an extension to OLSRv2. However, were this to have been done, OLSRv2 routers that did not implement this extension would not recognize any link metric information and would attempt to use minimum hop-count routes. This would have meant that, in effect, routers that did implement and routers that did not implement this extension would differ over their valuation of links and routes. This would have led to the fundamental routing problem of "looping". Thus, if metric-based route selection were to have been considered only as an extension to OLSRv2, then routers that did implement and routers that did not implement this extension would not have been Dearlove, et able to interoperate. This would have been a significant limitation of such an extension. Link metrics were therefore included as standard in OLSRv2.

This document discusses the motivation and design rationale behind how link metrics were included in OLSRv2. The principal issues involved when including link metrics in OLSRv2 were:

o Assigning metrics to links involved considering separate metrics for the two directions of a link, with the receiving router determining the metric from transmitter to receiver. A metric used by OLSRv2 may be either of:

* A link metric, the metric of a specific link from an OLSRv2 interface of the transmitting router to an OLSRv2 interface of the receiving router.

* A neighbor metric, the minimum of the link metrics between two OLSRv2 routers, in the indicated direction.

These metrics are necessarily the same when these routers each have a single OLSRv2 interface but may differ when either has more. HELLO messages may include both link metrics and neighbor metrics. TC messages include only neighbor metrics.

o Metrics as used in OLSRv2 are defined to be dimensionless and additive. The assignment of metrics, including their relationship to real parameters such as data rate, loss rate, and delay, and the management of the choice of metric, is outside the scope of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF], which simply uses these metrics in a consistent manner. o The protocol Information Bases defined in OLSRv2 include required metric values. This has included additions to the protocol Information Bases defined in NHDP [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] when used by OLSRv2.

Terminology

All terms introduced in [RFC5444], including "message" and "TLV" (type-length-value), are to be interpreted as described there.

All terms introduced in [RFC6130], including "MANET interface", "HELLO message", "heard", "link", "symmetric link", "1-hop neighbor", "symmetric 1-hop neighbor", "2-hop neighbor", "symmetric 2-hop neighbor", "symmetric 2-hop neighborhood", and the symbolic constants SYMMETRIC and HEARD, are to be interpreted as described there.

All terms introduced in [RFC7181], including "router", "OLSRv2 interface", "willingness", "multipoint relay (MPR)", "MPR selector", "MPR flooding", and the TLV type LINK_METRIC, are to be interpreted as described there.

Applicability

The objective of this document is to retain the design considerations behind how link metrics were included in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF]. This document does not prescribe any behavior but explains some aspects of the operation of OLSRv2.

Motivational Scenarios

The basic situation that suggests the desirability of use of routes other than minimum hop routes is shown in Figure 1.

A -----X -----B \ / \ / Y -------Z Figure 1
The minimum hop route from A to B is via X. However, if the links A to X and X to B are poor (e.g., have low data rate or are unreliable) but the links A to Y, Y to Z, and Z to B are better (e.g., have reliable high data rate), then the route A to B via Y and Z may be preferred to that via X. There are other situations where the use of some links should be discouraged, even if the avoidance of them does not show immediately obvious benefits to users. Consider a network with many short-range links and a few long-range links. Use of minimum hop routes will immediately lead to heavy use of the long-range links. This will be particularly undesirable if those links achieve their longer range through reduced data rate or through being less reliable. However, even if the long-range links have the same characteristics as the short-range links, it may be better to reserve usage of the longrange links for when this usage is particularly valuable --for example, when the use of one long-range link saves several shortrange links, rather than the single link saving that is needed for a minimum hop route.

A related case is that of a privileged relay. An example is an aerial router in an otherwise ground-based network. The aerial router may have a link to many, or even all, other routers. That would lead to all routers attempting to send all their traffic (other than to symmetric 1-hop neighbors and some symmetric 2-hop neighbors) via the aerial router. It may, however, be important to reserve that capacity for cases where the aerial router is actually essential, such as if the ground-based portion of the network is not connected.

Link metrics provide a possible solution to these scenarios. For example, in Figure 1, the route A to Y to Z to B could be preferred to A to X to B by making the metrics on the former path 1 and those on the latter path 2. The aerial privileged relay could be used only when necessary by giving its links maximal metric values, with much smaller other metric values or, if the aerial link is to be preferred to N ground links, by giving the ground links metric values of 1 while making the sum of the aerial node uplink and downlink metrics equal to N.

Other cases may involve attempts to avoid areas of congestion, attempts to route around insecure routers, and attempts by routers to discourage being used as relays due to, for example, limited battery power. OLSRv2 does have another mechanism to aid in this: a router's willingness to act as an MPR. However, there are cases where that cannot help but where use of non-minimum hop routes could.

Similarly, note that OLSRv2's optional use of link quality (through its use of [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF]) is not a solution to these problems. Use of link quality as specified in [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] allows a router to decline to use a link, not only on its own, but on all routers' behalf. It does not, for example, allow the use of a link otherwise determined to be too low quality to be generally useful as part of a route where no better links exist. These mechanisms (link quality and link metrics) solve distinctly different problems. It should also be noted that the loop-free property of OLSRv2 applies strictly only in the static state. When the network topology is changing and when messages can be lost, it is possible for transient loops to form. However, with update rates appropriate to the rate of topology change, such loops will be sufficiently rare. Changing link metrics is a form of network topology change and should be limited to a rate slower than the message information update rate (defined by the parameters HELLO_INTERVAL, HELLO_MIN_INTERVAL, REFRESH_INTERVAL, TC_INTERVAL, and TC_MIN_INTERVAL).

Link Metrics

This section describes the required and selected properties of the link metrics used in OLSRv2, followed by implementation details achieving those properties.

Link Metric Properties

Link metrics in OLSRv2 are:

o Dimensionless. While they may, directly or indirectly, correspond to specific physical information (such as delay, loss rate, or data rate), this knowledge is not used by OLSRv2. Instead, generating the metric value is the responsibility of a mechanism external to OLSRv2.

o Additive, so that the metric of a route is the sum of the metrics of the links forming that route. Note that this requires a metric where a low value of a link metric indicates a "good" link and a high value of a link metric indicates a "bad" link, and the former will be preferred to the latter.

o Directional, the metric from router A to router B need not be the same as the metric from router B to router A, even when using the same OLSRv2 interfaces. At router A, a link metric from router B to router A is referred to as an incoming link metric, while a link metric from router A to router B is referred to as an outgoing link metric. (These are, of course, reversed at router B.)

o Specific to a pair of OLSRv2 interfaces, so that if there is more than one link from router A to router B, each has its own link metric in that direction. There is also an overall metric, a "neighbor metric", from router A to router B (its 1-hop neighbor). This is the minimum value of the link metrics from router A to router B, considering symmetric links only; it is undefined if there are no such symmetric links. A neighbor metric from one router to another is always equal to a link metric in the same Dearlove, et al.

Informational [Page 7]

RFC 7185

OLSRv2 Link Metrics April 2014 direction between OLSRv2 interfaces of those routers. When referring to a specific OLSRv2 interface (for example, in a Link Tuple or a HELLO message sent on that OLSRv2 interface), a link metric always refers to a link on that OLSRv2 interface to or from the indicated 1-hop neighbor OLSRv2 interface, while a neighbor metric may be equal to a link metric to and/or from another OLSRv2 interface.

Link Metric Types

There are various physical characteristics that may be used to define a link metric. Some examples, which also illustrate some characteristics of metrics that result, are:

o Delay is a straightforward metric; as it is naturally additive, the delay of a multi-link route is the sum of the delays of the links. This does not directly take into account delays due to routers (such as due to router queues or transition of packets between router interfaces) rather than links, but these delays can be divided among incoming and outgoing links.

o Probability of loss on a link is, as long as probabilities of loss are small and independent, approximately additive. (A slightly more accurate approach is using a negatively scaled logarithm of the probability of not losing a packet.) If losses are not independent, then this will be pessimistic.

o Data rates are not additive. They even have the wrong characteristic of being good when high and bad when low; thus, a mapping that inverts the ordering must be applied. Such a mapping can, at best, only produce a metric that is acceptable to treat as additive. Consider, for example, a preference for a route that maximizes the minimum data rate link on the route and then prefers a route with the fewest links of each data rate from the lowest. If links may be of three discrete data rates, "high", "medium", and "low", then this preference can be achieved, on the assumption that no route will have more than 10 links, with metric values of 1, 10, and 100 for the three data rates.

If routes can have more than 10 links, the range of metrics must be increased; this was one reason for a preference for a wide "dynamic range" of link metric values. Depending on the ratios of the numerical values of the three data rates, the same effect may be achieved by using a scaling of an inverse power of the numerical values of the data rates. For example, if the three data rates were 2, 5, and 10 Mbit/s, then a possible mapping would be the fourth power of 10 Mbit/s divided by the data rate, giving metric values of 625, 16, and 1 (good for up to 16 links in a Dearlove, et al.

Informational [Page 8]

RFC 7185

OLSRv2 Link Metrics April 2014 route). This mapping can be extended to a system with more data rate values, for example, giving a 4 Mbit/s data rate a metric value of about 39. This may lose the capability to produce an absolutely maximal minimum data rate route but will usually produce either that, or something close (and at times maybe better, is a route of three 5 Mbit/s links really better than one of a single 4 Mbit/s link?). Specific metrics will need to define the mapping.

There are also many other possible metrics, including using physicallayer information (such as signal-to-noise ratio and error-control statistics) and information such as packet-queuing statistics.

In a well-designed network, all routers will use the same metric type. It will not produce good routes if, for example, some link metrics are based on data rate and some on path loss (except to the extent that these may be correlated). How to achieve this is an administrative matter, outside the scope of OLSRv2. In fact, even the actual physical meanings of the metrics is outside the scope of OLSRv2. This is because new metrics may be added in the future, for example, as data rates increase, and may be based on new, possibly non-physical, considerations, for example, financial cost. Each such type will have a metric type number. Initially, a single link metric type zero is defined as indicating a dimensionless metric with no predefined physical meaning.

An OLSRv2 router is instructed which single link metric type to use and recognize, without knowing whether it represents delay, probability of loss, data rate, cost, or any other quantity. This recognized link metric type number is a router parameter and subject to change in case of reconfiguration or possibly the use of a protocol (outside the scope of OLSRv2) permitting a process of link metric type agreement between routers.

The use of link metric type numbers also suggests the possibility of use of multiple link metric types and multiple network topologies. This is a possible future extension to OLSRv2. To allow for that future possibility, the sending of more than one metric of different physical types, which should otherwise not be done for reasons of efficiency, is not prohibited, but types other than that configured will be ignored.

The following three sections assume a chosen single link metric type, of unspecified physical nature. o In many (possibly most) cases, the two ends of a link will naturally form different views as to what the link metric should be. To use a single link metric requires a coordination between the two that can be avoided if using directional metrics. Note that if using a single metric, it would be essential that the two ends agree as to its value; otherwise, it is possible for looping to occur. This problem does not occur for directional metrics.

Based on these considerations, directional metrics are used in OLSRv2. Each router must thus be responsible for defining the metric in one direction only. This could have been in either direction, i.e., a router is responsible for either incoming or outgoing link metrics, as long as the choice is universal. The former (incoming) case is used in OLSRv2 because, in general, receiving routers have more information available to determine link metrics (for example, received signal strength, interference levels, and error-control coding statistics).

Note that, using directional metrics, if router A defines the metric of the link from router B to router A, then router B must use router A's definition of that metric on that link in that direction.

(Router B could, if appropriate, use a bad mismatch between directional metrics as a reason to discontinue use of this link, using the link quality mechanism defined in [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF]; note that this is a distinct mechanism from the use of link metrics.)

Reporting Link and Neighbor Metrics

Links, and hence link metrics, are reported in HELLO messages. A router must report incoming link metrics in its HELLO messages in order for these link metrics to be available at the other end of the link. This means that, for a symmetric link, both ends of the link will know both of the incoming and outgoing link metrics.

As well as advertising incoming link metrics, HELLO messages also advertise incoming neighbor metrics. These are used for routing MPR selection (see Section 6.2), which requires use of the lowest metric link between two routers when more than one link exists. This neighbor metric may be using another OLSRv2 interface, and hence, the link metric alone is insufficient.

Metrics are also reported in TC messages. It can be shown that these need to be outgoing metrics:

o Router A must be responsible for advertising a metric from router A to router B in TC messages. This can be seen by considering a route connecting single OLSRv2 interface routers P to Q to R to S.

Router P receives its only information about the link from R to S in the TC messages transmitted by router R, which is an MPR of router S (assuming that only MPR selectors are reported in TC messages). Router S may not even transmit TC messages (if no routers have selected it as an MPR and it has no attached networks to report). So any information about the metric of the link from R to S must also be included in the TC messages sent by router R; hence, router R is responsible for reporting the metric for the link from R to S.

o In a more general case, where there may be more than one link from R to S, the TC message must, so that minimum metric routes can be constructed (e.g., by router P), report the minimum of these outgoing link metrics, i.e., the outgoing neighbor metric from R to S.

In this example, router P also receives information about the existence of a link between Q and R in the HELLO messages sent by router Q. Without the use of metrics, this link could be used by OLSRv2 for 2-hop routing to router R, using just HELLO messages sent by router Q. For this property (which accelerates local route formation) to be retained (from OLSRv1), router P must receive the metric from Q to R in HELLO messages sent by router Q. This indicates that router Q must be responsible for reporting the metric for the outgoing link from Q to R. This is in addition to the incoming link metric information that a HELLO message must report. Again, in general, this must be the outgoing neighbor metric, rather than the outgoing link metric.

In addition, Section 6.1 offers an additional reason for reporting outgoing neighbor metrics in HELLO messages, without which metrics can properly affect only routing, not flooding.

Note that there is no need to report an outgoing link metric in a HELLO message. The corresponding 1-hop neighbor knows that value; it specified it. Furthermore, for 2-hop neighborhood use, neighbor metrics are required (as these will, in general, not use the same OLSRv2 interface). When a router reports a 1-hop neighbor in a HELLO message, it may do so for the first time with link status HEARD. As the router is responsible for defining and reporting incoming link metrics, it must evaluate that metric and attach that link metric to the appropriate address (which will have link status HEARD) in the next HELLO message reporting that address on that OLSRv2 interface. There will, at this time, be no outgoing link metric available to report, but a router must be able to immediately decide on an incoming link metric once it has heard a 1-hop neighbor on an OLSRv2 interface for the first time.

This is because, when receiving a HELLO message from this router, the 1-hop neighbor seeing its own address listed with link status HEARD will (unless the separate link quality mechanism indicates otherwise) immediately consider that link to be SYMMETRIC, advertise it with that link status in future HELLO messages, and use it (for MPR selection and data traffic forwarding).

It may, depending on the physical nature of the link metric, be too early for an ideal decision as to that metric; however, a choice must be made. The metric value may later be refined based on further observation of HELLO messages, other message transmissions between the routers, or other observations of the environment. It will probably be best to over-estimate the metric if initially uncertain as to its value, to discourage, rather than over-encourage, its use. If no information other than the receipt of the HELLO message is available, then a conservative maximum link metric value, denoted MAXIMUM_METRIC in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF], should be used.

Link Metric Values

Link metric values are recorded in LINK_METRIC TLVs, defined in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF], using a compressed (lossy) representation that occupies 12 bits. The use of 12 bits is convenient because, when combined with 4 flag bits of additional information, described below, this results in a 2-octet value field. However, the use of 12 bits, and thus the availability of 4 flag bits, was a consequence of a design to use a modified exponent/mantissa form with the following characteristics:

o The values represented are to be positive integers starting 1, 2, ... o The maximum value represented should be close to, but less than 2^24 (^ denotes exponentiation in this section). This is so that with a route limited to no more than 255 hops, the maximum route metric is less than 2^32, i.e., can be stored in 32 bits. (The link metric value can be stored in 24 bits.)

Dearlove, et al.

Informational [Page 12]

A representation that is modified from an exponent/mantissa form with e bits of exponent and m bits of mantissa and that has the first of these properties is one that starts at 1, then is incremented by 1 up to 2^m, then has a further 2^m increments by 2, then a further 2^m increments by 4, and so on for 2^e sets of increments. This means that the represented value is never in error by more than a half (if rounding) or one (if truncating) part in 2^m, usually less.

The position in the increment sequence, from 0 to 2^m-1, is considered as a form of mantissa and denoted a. The increment sequence number, from 0 to 2^e-1, is considered as a form of exponent and denoted b.

The value represented by (b,a) can then be shown to be equal to (2^m+a+1)2^b-2^m. To verify this, note that:

o With fixed b, the difference between two values with consecutive values of a is 2^b, as expected.

o The value represented by (b,2^m-1) is (2^m+2^m)2^b-2^m. The value represented by (b+1,0) is (2^m+1)(2^(b+1))-2^m. The difference between these two values is 2^(b+1), as expected.

The maximum represented value has b = 2^e-1 and a = 2^m-1 and is (2^m+2^m)(2^(2^e-1))-2^m = 2^(2^e+m)-2^m. This is slightly less than 2^(2^e+m). The required 24-bit limit can be achieved if 2^e+m = 24. Of the possible (e,m) pairs that satisfy this equation, the pair e = 4, m = 8 was selected as most appropriate and is that used by OLSRv2. It uses the previously indicated e+m = 12 bits. An algorithm for converting from a 24-bit value v to a 12-bit pair (b,a) is given in Section 6.2 of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF].

As noted above, the 12-bit representation then shares two octets with 4 flag bits. Putting the flag bits first, it is then natural to put the exponent bits in the last four bits of the first octet and to put the mantissa bits in the second octet. The 12 consecutive bits, using network byte order (most significant octet first), then represent 256b+a. Note that the ordering of these 12-bit representation values is the same as the ordering of the 24-bit metric values. In other words, two 12-bit metrics fields can be compared for equality/ordering as if they were unsigned integers.

The four flag bits each represent one kind of metric, defined by its direction (incoming or outgoing) and whether the metric is a link metric or a neighbor metric. As indicated by the flag bits set, a metric value may be of any combination of these four kinds of metric. o Optimized Flooding. This uses the MPR selector status of symmetric 1-hop neighbor routers from which messages are received in order to determine if these messages are to be forwarded. MPR selector status is recorded in the Neighbor Set (defined in [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] and extended in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF]) and determined from received HELLO messages.

o Routing. Non-local link information is based on information recorded in this router's Topology Information Base. That information is based on received TC messages. The neighbor information in these TC messages consists of addresses of the originating router's advertised (1-hop) neighbors, as recorded in that router's Neighbor Set (defined in [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] and extended in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF]). These advertised neighbors include all of the MPR selectors of the originating router.

Metrics interact with these two uses of MPRs differently, as described in the following two sections. This leads to the requirement for two separate sets of MPRs for these two uses when using metrics. The relationship between these two sets of MPRs is considered in Section 6.3.

Flooding MPRs

The essential detail of the "flooding MPR" selection specification is that a router must select a set of MPRs such that a message transmitted by a router and retransmitted by all its flooding MPRs will reach all of the selecting router's symmetric 2-hop neighbors.

Flooding MPR selection can ignore metrics and produce a solution that meets the required specification. However, that does not mean that metrics cannot be usefully considered in selecting flooding MPRs. Consider the network in Figure 2, where numbers are metrics of links in the direction away from router A, towards router D.

Dearlove, et al.

Informational [Page 14]

RFC 7185

OLSRv2 Link Metrics April 2014

3 A -----B | | 1 | | 1 | | C -----D 4 Figure 2
Which is the better flooding MPR selection by router A: B or C? If the metric represents probability of message loss, then clearly choosing B maximizes the probability of a message sent by A reaching D. This is despite C having a lower metric in its connection to A than B does. (Similar arguments about a preference for B can be made if, for example, the metric represents data rate or delay rather than probability of loss.)

However, neither should only the second hop be considered. If this example is modified to that in Figure 3, where the numbers still are metrics of links in the direction away from router A, towards router D, then it is possible that, when A is selecting flooding MPRs, selecting C is preferable to selecting B. ----D 4

3 A -----B | | 1 | | 3 | | C -
Figure 3 If the metrics represent scaled values of delay or the probability of loss, then selecting C is clearly better. This indicates that the sum of metrics is an appropriate measure to use to choose between B and C.

However, this is a particularly simple example. Usually, it is not a simple choice between two routers as a flooding MPR, each only adding one router coverage. When considering which router to next add as a flooding MPR, a more general process should incorporate the metric to that router and the metric from that router to each symmetric 2-hop neighbor as well as the number of newly covered symmetric 2-hop neighbors. Other factors may also be included.

Dearlove, et al.

Informational [Page 15]

RFC 7185

OLSRv2 Link Metrics April 2014

The required specification for flooding MPR selection is in Section 18.4 (also using Section 18.3) of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF], which may use the example MPR selection algorithm in Appendix B of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF]. However, note that (as in [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF]) each router can make its own independent choice of flooding MPRs, and flooding MPR selection algorithm, and still interoperate.

Also note that the references above to the direction of the metrics is correct: for flooding, directional metrics outward from a router are appropriate, i.e., metrics in the direction of the flooding. This is an additional reason for including outward metrics in HELLO messages, as otherwise a metric-aware MPR selection for flooding is not possible. The second-hop metrics are outgoing neighbor metrics because the OLSRv2 interface used for a second-hop transmission may not be the same as that used for the first-hop reception.

Routing MPRs

The essential detail of the "routing MPR" selection specification is that a router must, per OLSRv2 interface, select a set of MPRs such that there is a 2-hop route from each symmetric 2-hop neighbor of the selecting router to the selecting router, with the intermediate router on each such route being a routing MPR of the selecting router.

It is sufficient, when using an additive link metric rather than a hop count, to require that these routing MPRs provide not just a 2-hop route but a minimum distance 2-hop route. In addition, a router is a symmetric 2-hop neighbor even if it is a symmetric 1-hop neighbor, as long as there is a 2-hop route from it that is shorter than the 1-hop link from it. (The property that no routes go through routers with willingness WILL_NEVER is retained. Examples below assume that all routers are equally willing, with none having willingness WILL_NEVER.)

For example, consider the network in Figure 4. Numbers are metrics of links in the direction towards router A, away from router D. Router A must pick router B as a routing MPR, whereas for minimum hop count routing, it could alternatively pick router C. Note that the use of incoming neighbor metrics in this case follows the same reasoning as for the directionality of metrics in TC messages, as described in Section 5.4.

A -----B | | 1 | | 1 | | C -----D 3 Figure 4
In Figure 5, where numbers are metrics of links in the direction towards router A and away from router C, router A must pick router B as a routing MPR, but for minimum hop count routing, it would not need to pick any MPRs.

1 A -B \ | 4 \ | 2 \| C Figure 5
In Figure 6, where numbers are metrics of links in the direction towards router A and away from routers D and E, router A must pick both routers B and C as routing MPRs, but for minimum hop count routing, it could pick either. However, the definition noted above as sufficient for routing MPR selection is not necessary. For example, consider the network in Figure 7, where numbers are metrics of links in the direction towards router A, away from other routers; the metrics from B to C and C to B are both assumed to be 2. ----D -----E 3 5

D E |\ /| | \ 3 / | | \ / | 1 | \/ | 1 | /\ | | / \ | | / 2 \ | |/ \| B C \ | \ / 3 \ / 2 \ /
1 A -----B \ / 4 \ / 2 \ / C -
Figure 7 Using the above definition, A must pick both B and C as routing MPRs, in order to cover the symmetric 2-hop neighbors C and D, respectively. (C is a symmetric 2-hop neighbor because the route length via B is shorter than the 1-hop link.)

However, A only needs to pick B as a routing MPR, because the only reason to pick C as a routing MPR would be so that C can advertise the link to A for routing --to be used by, for example, E. However, A knows that no other router should use the link C to A in a shortest route because routing via B is shorter. So, if there is no need to advertise the link from C to A, then there is no reason for A to select C as a routing MPR.

This process of "thinning out" the routing MPR selection uses only local information from HELLO messages. Using any minimum distance algorithm, the router identifies shortest routes, whether one, two, or more hops, from all routers in its symmetric 2-hop neighborhood. It then selects as MPRs all symmetric 1-hop neighbors that are the last router (before the selecting router itself) on any such route.

Where there is more than one shortest distance route from a router, only one such route is required. Alternative routes may be selected so as to minimize the number of last routers --this is the equivalent to the selection of a minimal set of MPRs in the nonmetric case. The examples in Figures 5 and6 show that use of link metrics may require a router to select more routing MPRs than when not using metrics and even require a router to select routing MPRs when, without metrics, it would not need any routing MPRs. This may result in more, and larger, messages being generated and forwarded more often. Thus, the use of link metrics is not without cost, even excluding the cost of link metric signaling.

These examples consider only single OLSRv2 interface routers. However, if routers have more than one OLSRv2 interface, then the process is unchanged; other than that, if there is more than one known metric between two routers (on different OLSRv2 interfaces), then, considering symmetric links only (as only these are used for routing) the smallest link metric, i.e., the neighbor metric, is used. There is no need to calculate routing MPRs per OLSRv2 interface. That requirement results from the consideration of flooding and the need to avoid certain "race" conditions, which are not relevant to routing, only to flooding.

The required specification for routing MPR selection is in Section 18.5 (also using Section 18.3) of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF], which may use the example MPR selection algorithm in Appendix B of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF]. However, note that (as in [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF]) each router can make its own independent choice of routing MPRs, and routing MPR selection algorithm, and still interoperate.

Relationship between MPR Sets

It would be convenient if the two sets of flooding and routing MPRs were the same. This can be the case if all metrics are equal, but in general, for "good" sets of MPRs, they are not. (A reasonable definition of this is that there is no common minimal set of MPRs.) If metrics are asymmetrically valued (the two sets of MPRs use opposite direction metrics) or routers have multiple OLSRv2 interfaces (where routing MPRs can ignore this but flooding MPRs cannot), this is particularly unlikely. However, even using a symmetrically valued metric with a single OLSRv2 interface on each router, the ideal sets need not be equal, nor is one always a subset of the other. To show this, consider these examples, where all lettered routers are assumed equally willing to be MPRs, and numbers are bidirectional metrics for links.

In Figure 8, A does not require any flooding MPRs. However, A must select B as a routing MPR.

1 A -B \ | 4 \ | 2 \| C Figure 8
In Figure 9, A must select C and D as routing MPRs. However, A's minimal set of flooding MPRs is just B. In this example, the set of routing MPRs serves as a set of flooding MPRs, but a non-minimal one (although one that might be better, depending on the relative importance of number of MPRs and flooding link metrics).

2 C ---E / / 1 / / 1 / 4 / A ---B \ \ 1 \ \ 1 \ \ D ---F 2 Figure 9
However, this is not always the case. In Figure 10,A

An attacker can have an adverse impact on an OLSRv2 network by creating apparently valid messages that contain incorrect link metrics. This could take the form of influencing the choice of routes or, in some cases, producing routing loops. This is a more subtle, and likely to be less effective, attack than other forms of invalid message injection. These can add and remove other and more basic forms of network information, such as the existence of some routers and links.

As such, no significantly new security issues arose from the inclusion of metrics in OLSRv2. Defenses to the injection of invalid link metrics are the same as to other forms of invalid message injection, as discussed in the Security Considerations section of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF].

There are possible uses for link metrics in the creation of security countermeasures to prefer the use of links that have better security properties, including better availability, to those with poorer security properties. This, however, is beyond the scope of both this document and [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF].

RFC

In order for routers to find and use shortest routes in a network while using the minimum reduced topology supported by OLSRv2 (that a router only advertises its MPR selectors in TC messages), routing MPR selection must result in the property that there are shortest routes with all intermediate routers being routing MPRs.

This appendix uses the following terminology and assumptions:

o The network is a graph of nodes connected by arcs, where nodes correspond to routers with willingness not equal to WILL_NEVER (except possibly at the ends of routes). An arc corresponds to the set of symmetric links connecting those routers; the OLSRv2 interfaces used by those links are not relevant.

o Each arc has a metric in each direction, being the minimum of the corresponding link metrics in that direction, i.e., the corresponding neighbor metric. This metric must be positive.

o A sequence of arcs joining two nodes is referred to as a path.

o Node A is an MPR of node B if corresponding router A is a routing MPR of router B.

The required property (of using shortest routes with reduced topology) is equivalent to the following property: for any pair of distinct nodes X and Z, there is a shortest path from X to Z, X -Y1 -Y2 -... -Ym -Z such that Y1 is an MPR of Y2, ..., Ym is an MPR of Z. Call such a path a routable path, and call this property the routable path property.

The required definition for a node X selecting MPRs is that for each distinct node Z from which there is a two-arc path, there is a shorter, or equally short, path that is either Z -Y -X where Y is an MPR of X or is the one-arc path Z -X. Note that the existence of locally known, shorter paths that have more than two arcs, which can be used to reduce the numbers of MPRs, is not considered here. (Such reductions are only when the remaining MPRs can be seen to retain all necessary shortest paths and therefore retain the required property.)

Although this appendix is concerned with paths with minimum total metric, not number of arcs (hop count), it proceeds by induction on the number of arcs in a path. Although it considers minimum metric routes with a bounded number of arcs, it then allows that number of arcs to increase so that overall minimum metric paths, regardless of the number of arcs, are considered. Specifically, the routable path property is a corollary of the property that for all positive integers n and all distinct nodes X and Z, if there is any path from X to Z of n arcs or fewer, then there is a shortest path, from among those of n arcs or fewer, that is a routable path. This may be called the n-arc routable path property.

The n-arc routable path property is trivial for n = 1 and directly follows from the definition of the MPRs of Z for n = 2.

Proceeding by induction, assuming the n-arc routable path property is true for n = k, consider the case that n = k+1.

Suppose that X -V1 -V2 -... -Vk -Z is a shortest k+1 arc path from X to Z. We construct a path that has no more than k+1 arcs, has the same or shorter length (hence has the same, shortest, length considering only paths of up to k+1 arcs, by assumption), and is a routable path.

First, consider whether Vk is an MPR of Z. If it is not, then consider the two-arc path Vk-1 -Vk -Z. This can be replaced either by a one-arc path Vk-1 -Z or by a two-arc path Vk-1 -Wk -Z, where Wk is an MPR of Z, such that the metric from Vk-1 to Z by the replacement path is no longer. In the former case (replacement onearc path), this now produces a path of length k, and the previous inductive step may be applied. In the latter case, we have replaced Vk by Wk, where Wk is an MPR of Z. Thus, we need only consider the case that Vk is an MPR of Z.

We now apply the previous inductive step to the path X -V1 -... -Vk-1 -Vk, replacing it by an equal length path X -W1 -... Wm-1 -Vk, where m <= k, where this path is a routable path. Then, because Vk is an MPR of Z, the path X -W1 -... -Wm-1 -Vk -Z is a routable path and demonstrates the n-arc routable path property for n = k+1.

This thus shows that for any distinct nodes X and Z, there is a routable path using the MPR-reduced topology from X to Z, i.e., that OLSRv2 finds minimum length paths (minimum total metric routes).

  Figure 10

  MPRs are used for two purposes in OLSRv2. In both cases, it is MPR selectors that are actually used, MPR selectors being determined from MPRs advertised in HELLO messages.

	RFC 7185	OLSRv2 Link Metrics	April 2014
	6. MPRs with Link Metrics
	Dearlove, et al.	Informational	[Page 13]

  It is shown in Appendix A that selecting routing MPRs according to this definition and advertising only such links (plus knowledge of local links from HELLO messages) will result in selection of lowest total metric routes, even if all links (advertised or not) are considered in the definition of a shortest route.

	RFC 7185	OLSRv2 Link Metrics	April 2014
		A
		Figure 6
	Dearlove, et al.	Informational	[Page 17]

  Note that this only removes routing MPRs whose selection can be directly seen to be unnecessary. Consequently, if (as is shown in Appendix A) the first approach creates minimum distance routes, then so does this process.

	RFC 7185	OLSRv2 Link Metrics	April 2014
	Dearlove, et al.	Informational	[Page 18]

Acknowledgements

The authors would like to gratefully acknowledge the following people (listed alphabetically) for intense technical discussions, early reviews, and comments on the documents and its components: Brian Adamson (NRL), Alan Cullen (BAE Systems), Justin Dean (NRL), Ulrich Herberg (Fujitsu), Charles Perkins (Huawei), Stan Ratliff (Cisco), and Henning Rogge (FGAN).

Finally, the authors would like to express their gratitude to (listed alphabetically) Benoit Claise, Adrian Farrel, Stephen Farrell, and Suresh Krishnan for their reviews and comments on the later draft versions of this document.

Steering Group (IESG). candidate for any level of Internet Standard; see Section 2 of RFC 5741.


Internet Engineering Task Force (IETF)

This document analyzes common security threats of the Neighborhood Discovery Protocol (NHDP) and describes their potential impacts on Mobile Ad Hoc Network (MANET) routing protocols using NHDP. This document is not intended to propose solutions to the threats described.

Introduction

The Neighborhood Discovery Protocol (NHDP) [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] allows routers to acquire topological information up to two hops away from themselves, by way of periodic HELLO message exchanges. The information acquired by NHDP is used by other protocols, such as the Optimized Link State Routing Protocol version 2 (OLSRv2) [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF] and Simplified Multicast Forwarding (SMF) [START_REF] Macker | Simplified Multicast Forwarding[END_REF]. The topology information, acquired by way of NHDP, serves these routing protocols by detecting and maintaining local 1-hop and 2-hop neighborhood information.

As NHDP is typically used in wireless environments, it is potentially exposed to different kinds of security threats, some of which are of particular significance as compared to wired networks. As radio signals can be received as well as transmitted by any compatible wireless device within radio range, there is commonly no physical protection as otherwise known for wired networks. NHDP does not define any explicit security measures for protecting the integrity of the information it acquires; however, it suggests that the integrity protection be addressed in a fashion appropriate to the deployment of the network. This document is based on the assumption that no additional security mechanism such as IPsec is used in the IP layer, as not all MANET deployments may be able to accommodate such common IP protection mechanisms (e.g., because of limited resources of MANET routers). The document analyzes possible attacks on and misconfigurations of NHDP and outlines the consequences of such attacks/misconfigurations to the state maintained by NHDP in each router (and, thus, made available to protocols using this state). This document is not intended to propose solutions to the threats described. [START_REF] Herberg | Integrity Protection for the Neighborhood Discovery Protocol (NHDP) and Optimized Link State Routing Protocol Version 2 (OLSRv2)[END_REF] provides further information on how to enable integrity protection to NHDP, which can help mitigating the threats described related to identity spoofing.

It should be noted that many NHDP implementations are configurable, and so an attack on the configuration system (such as [START_REF] Herberg | Definition of Managed Objects for the Neighborhood Discovery Protocol[END_REF]) can be used to adversely affect the operation of an NHDP implementation.

The NHDP MIB module [START_REF] Herberg | Definition of Managed Objects for the Neighborhood Discovery Protocol[END_REF] might help monitoring some of the security attacks mentioned in this document. [MGMT-SNAP] provides a snapshot of OLSRv2-routed MANET management as currently deployed, while [MANET-MGMT] is intended to provide specific guidelines on MANET network management considering the various MIB modules that have been written. Yi, et Additionally, this document introduces the following terminology:

NHDP router: A MANET router, running NHDP as specified in [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF].

Attacker: A device that is present in the network and intentionally seeks to compromise the information bases in NHDP routers.

Compromised NHDP router: An attacker that is present in the network and generates syntactically correct NHDP control messages. Control messages emitted by a compromised NHDP router may contain additional information, or omit information, as compared to a control message generated by a non-compromised NHDP router located in the same topological position in the network.

Legitimate NHDP router: An NHDP router that is not a compromised NHDP router.

NHDP Threat Overview

NHDP defines a HELLO messages exchange, enabling each NHDP router to acquire topological information describing its 1-hop and 2-hop neighbors, and specifies information bases for recording this information.

An NHDP router periodically transmits HELLO messages using a linklocal multicast on each of its interfaces with a hop-limit of 1 (i.e., HELLOs are never forwarded). In these HELLO messages, an NHDP router announces the IP addresses as heard, symmetric, or lost neighbor interface addresses.

An Attacker has several ways of harming this neighbor discovery process: it can announce "wrong" information about its identity, postulate nonexistent links, and replay HELLO messages. These attacks are presented in detail in Section 4.

The different ways of attacking an NHDP deployment may eventually lead to inconsistent information bases, not accurately reflecting the correct topology of the MANET. The consequence is that protocols using NHDP will base their operation on incorrect information, causing routing protocols to not be able to calculate correct (or any) paths, degrade the performance of flooding operations based on reduced relay sets, etc. These consequences to protocols using NHDP are described in detail in Section 5.

Detailed Threat Description

For each threat, a description of the mechanism of the corresponding attack is given, followed by a description of how the attack affects NHDP. The impacts from each attack on protocols using NHDP are given in Section 5.

For simplicity in the description, the examples given assume that NHDP routers have a single interface with a single IP address configured. All the attacks apply, however, for NHDP routers with multiple interfaces and multiple addresses as well.

Jamming

One vulnerability, common for all protocols operating a wireless ad hoc network, is that of "jamming", i.e., that a device generates massive amounts of interfering radio transmissions, which will prevent legitimate traffic (e.g., control traffic as well as data traffic) on part of a network. Jamming is a form of interference and overload with the threat consequence of disruption [START_REF] Barbir | Generic Threats to Routing Protocols[END_REF].

Depending on lower layers, this may not affect transmissions: HELLO messages from an NHDP router with "jammed" interfaces may be received by other NHDP routers. As NHDP identifies whether a link to a neighbor is unidirectional or bidirectional, a routing protocol that uses NHDP for neighborhood discovery may ignore a link from a jammed NHDP router to a non-jammed NHDP router. The jammed router (a router with jammed carrier) would appear simply as "disconnected" for the unjammed part of the network, which is able to maintain accurate topology maps.

If a considerable amount of HELLO messages are lost or corrupted due to collisions caused by a jamming attack, neighbor NHDP routers are not able to establish links between themselves any more. Thus, NHDP will present empty information bases to the protocols using it. By exhausting the memory, CPU, and/or channel resources of a router in a DoS attack or a misconfiguration, NHDP routers may not be able to accomplish their specified tasks of exchanging 1-hop and 2-hop neighborhood information, and thereby disturbing the operation of routing protocols using NHDP.

Denial-of-Service

In some MANETs, the routers are powered by battery. Another consequence of a DoS attack in such networks is that the power will be drained quickly by unnecessary processing, transmitting, and receiving of messages.

Eavesdropping and Traffic Analysis

Eavesdropping, sometimes referred to as sniffing, is a common and easy passive attack in a wireless environment. Once a packet is transmitted, any adjacent NHDP router can potentially obtain a copy, for immediate or later processing. Neither the source nor the intended destination can detect this. A malicious NHDP router can eavesdrop on the NHDP message exchange and thus learn the local topology. It may also eavesdrop on data traffic to learn source and destination addresses of data packets, or other header information, as well as the packet payload.

Eavesdropping does not pose a direct threat to the network or to NHDP, in as much as that it does not alter the information recorded by NHDP in its information bases and presented to other protocols. However, eavesdropping can provide network information required for enabling other attacks, such as the identity of communicating NHDP routers, detection of link characteristics, and NHDP router configuration. The compromised NHDP routers may use the obtained information to launch subsequent attacks, and they may also share NHDP routing information with other NHDP or non-NHDP entities.

[RFC4593] would categorize the threat consequence as disclosure.

Yi, et al.

Informational [Page 6]

RFC 7186

Security Threats for NHDP April 2014

Traffic analysis normally follows eavesdropping, which is the process of intercepting messages in order to deduce information from communication patterns. It can be performed even when HELLO messages are encrypted (encryption is not a part of NHDP), for example:

o Triggered HELLO messages: an attacker could figure out that messages are triggered and determine that there was a change of symmetric neighbors of an NHDP router sending the HELLO (as well get the frequency).

o Message size: the message grows exactly by x bytes per neighbor.

Depending on which cipher is used for the encryption, some information about the size could be inferred, and thus the number of neighbors could be guessed.

[RFC4593] would categorize the threat consequence as disclosure.

Incorrect HELLO Message Generation

An NHDP router performs two distinct tasks: it periodically generates HELLO messages, and it processes incoming HELLO messages from neighbor NHDP routers. This section describes security attacks involving the HELLO generation.

Identity Spoofing

Identity spoofing implies that a compromised NHDP router sends HELLO messages, pretending to have the identity of another NHDP router, or even a router that does not exist in the networks. A compromised NHDP router can accomplish this by using an IP address, which is not its own, in an address block of a HELLO message, and associating this address with a LOCAL_IF Address Block TLV [IJNSIA2010].

An NHDP router receiving that HELLO message from a neighbor will assume that it originated from the NHDP router with the spoofed interface address. As a consequence, it will add a Link Tuple to that neighbor with the spoofed address, and include it in its next HELLO messages as a heard neighbor (and possibly as a symmetric neighbor after another HELLO exchange).

Identity spoofing is particularly harmful if a compromised NHDP router spoofs the identity of another NHDP router that exists in the same routing domain. With respect to NHDP, such a duplicated, spoofed address can lead to an inconsistent state up to two hops from an NHDP router. [START_REF] Barbir | Generic Threats to Routing Protocols[END_REF] would categorize the threat consequences as disclosure and deception.

Yi, et al.

Informational [Page 7]

RFC 7186

Security Threats for NHDP April 2014

Figure 1 depicts a simple example. In that example, NHDP router A is in radio range of NHDP router C, but not of the compromised NHDP router X. If X spoofs the address of A, that can lead to conflicts for a routing protocol that uses NHDP, and therefore for wrong path calculations as well as incorrect data traffic forwarding.

. If the compromised NHDP router X spoofs the address of A, NHDP router D will take A as its 1-hop neighbor, and C may think that A is indeed reachable through D.

---. .---. .---. | A |----| C |----| X | '---' '---' '---'
.

---. .---. .---. .---. .---. | A |----| B |----| C |----| D |----| X | '---' '---' '---' '---' '---'
Figure 2 4.4.2. Link Spoofing Similar to identity spoofing, link spoofing implies that a compromised NHDP router sends HELLO messages, signaling an incorrect set of neighbors. This is sometimes referred to as falsification [START_REF] Barbir | Generic Threats to Routing Protocols[END_REF], and in NHDP it may take either of two forms:

o A compromised NHDP router can postulate addresses of non-present neighbor NHDP routers in an address block of a HELLO, associated with LINK_STATUS TLVs.

o A compromised NHDP router can "ignore" otherwise existing neighbors by not advertising them in its HELLO messages.

The effect of link spoofing with respect to NHDP are twofold, depending on the two cases mentioned above:

o If the compromised NHDP router ignores existing neighbors in its advertisements, links will be missing in the information bases maintained by other routers, and there may not be any connectivity for these NHDP routers to or from other NHDP routers in the MANET. o On the other hand, if the compromised NHDP router advertises nonexistent links, this will lead to inclusion of topological information in the information base, describing nonexistent links in the network (which, then, may be used by other protocols using NHDP in place of other, existing, links).

[RFC4593] would categorize the threat consequences as usurpation, deception, and disruption.

Replay Attack

A replay attack implies that control traffic from one region of the network is recorded and replayed in a different region at (almost) the same time, or in the same region at a different time. This may, for example, happen when two compromised NHDP routers collaborate on an attack, one recording traffic in its proximity and tunneling it to the other compromised NHDP router, which replays the traffic. In a protocol where links are discovered by testing reception, this will result in extraneous link creation (basically, a "virtual" link between the two compromised NHDP routers will appear in the information bases of neighboring NHDP routers). [START_REF] Barbir | Generic Threats to Routing Protocols[END_REF] would categorize this as a falsification and interference threat with threat consequences of usurpation, deception, and disruption.

While this situation may result from an attack, it may also be intentional: if data traffic is also relayed over the "virtual" link, the link being detected is indeed valid for use. This is, for instance, used in wireless repeaters. If data traffic is not carried over the virtual link, an imaginary, useless link between the two compromised NHDP routers has been advertised and is being recorded in the information bases of their neighboring NHDP routers.

Compared to incorrect HELLO message attacks described in Section 4.4, the messages used in replay attacks are legitimate messages sent out by (non-malicious) NHDP routers and replayed at a later time or different locality by malicious routers. This makes this kind of attack harder to be detect and to counteract; integrity checks cannot help in this case, as the original message's Integrity Check Value (ICV) was correctly calculated.

Message Timing Attacks

In NHDP, each HELLO message contains a "validity time" (the amount of time that information in that control message should be considered valid before being discarded) and may contain an "interval time" field (the amount of time until the next control message of the same type should be expected) [START_REF] Clausen | Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)[END_REF]. A use of the expected interval between two successive HELLO messages is for determining the link quality in NHDP: if messages are not received within the expected intervals (e.g., a certain fraction of messages are missing), then this may be used to exclude a link from being considered as useful, even if (some) bidirectional communication has been verified. If a compromised NHDP router X spoofs the identity of an existing NHDP router A and sends HELLOs indicating a low interval time, an NHDP router B receiving this HELLO will expect the following HELLO to arrive within the interval time indicated. If that expectation is not met, the link quality for the link A-B will be decreased. Thus, X may cause NHDP router B's estimate of the link quality for the link A-B to fall below the minimum considered useful, so the link would not be used [CPSCOM2011]. [START_REF] Barbir | Generic Threats to Routing Protocols[END_REF] would categorize the threat consequence as usurpation.

Validity Time Attack

A compromised NHDP router X can spoof the identity of an NHDP router A and send a HELLO using a low validity time (e.g., 1 ms). A receiving NHDP router B will discard the information upon expiration of that interval, i.e., a link between NHDP router A and B will be "torn down" by X. The sending of a low validity time can be caused by intended malicious behaviors or simply misconfiguration in the NHDP routers. [START_REF] Barbir | Generic Threats to Routing Protocols[END_REF] would categorize the threat consequence as usurpation.

Indirect Channel Overloading

Indirect Channel Overloading is when a compromised NHDP router X by its actions causes other legitimate NHDP routers to generate inordinate amounts of control traffic. This increases channel occupation and the overhead in each receiving NHDP router that processes this control traffic. With this traffic originating from legitimate NHDP routers, the malicious device may remain undetected in the wider network. It is a form of interference and overload with the threat consequence of disruption [START_REF] Barbir | Generic Threats to Routing Protocols[END_REF]. . compromised NHDP router can spoof packets appearing to be from another legitimate NHDP router that skips some packet sequence numbers. The NHDP router receiving the spoofed packets may degrade the link quality as it appears that several packets have been dropped. Eventually, the router may remove the neighbor when the link quality drops below HYST_REJECT.

---. .---. | X | | X | | X | | X | '---' '---' '---' '--

Impact of Inconsistent Information Bases on Protocols using NHDP

This section describes the impact on protocols that use NHDP when NHDP fails to obtain and represent accurate information, possibly as a consequence of the attacks described in Section 4. This description emphasizes the impacts on the MANET protocols OLSRv2 [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF] and SMF [START_REF] Macker | Simplified Multicast Forwarding[END_REF].

MPR Calculation

MPR selection (as used in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF] and [START_REF] Macker | Simplified Multicast Forwarding[END_REF], for example) uses information about a router's 1-hop and 2-hop neighborhood, assuming that (i) this information is accurate, and (ii) each 1-hop neighbor is apt to act as MPR, depending on the willingness it reports. Thus, a compromised NHDP router may seek to manipulate the 1-hop and 2-hop neighborhood information in a router so as to cause the MPR selection to fail, leading to a flooding disruption of traffic control messages. This can result in incomplete topology advertisement or can degrade the optimized flooding to classical flooding.

Flooding Disruption due to Identity Spoofing

A compromised NHDP router can spoof the identify of other routers in order to disrupt the MPR selection, so as to prevent certain parts of the network from receiving flooded traffic [IJNSIA2010].

In Figure 4, a compromised NHDP router X spoofs the identity of B.

The link between X and C is correctly detected and listed in X's HELLOs. Router A will receive HELLOs indicating links from B:{B-E}, X:{X-C, X-E}, and D:{D-E, D-C}, respectively. For router A, X and D are equal candidates for MPR selection. To make sure the X can be selected as MPR for router A, X can set its willingness to the maximum value.

---. .---. .---. | E |----| D |----| C | '---' '---' '---' | | . | | . .---. .---. .---. | B |----| A |----| X | '---' '---' '---' spoofs B Figure 4
If B and X (i) accept MPR selection and (ii) forward flooded traffic as if they were both B, identity spoofing by X is harmless. However, if X does not forward flooded traffic (i.e., does not accept MPR selection), its presence entails flooding disruption: selecting B over D renders C unreachable by flooded traffic.

.

---. | D | '---' | | .---. .---. .---. .---. .---. | X |----| A |----| B |----| C |----| E |... '---' '---' '---' '---' '---' spoofs E Figure 5
In Figure 5, the compromised NHDP router X spoofs the identity of E, i.e., routers A and C both receive HELLOs from a router identifying itself as E. For router B, routers A and C present the same neighbor sets and are equal candidates for MPR selection. If router B selects only router A as MPR, C will not relay flooded traffic from B or transiting via B, and router X (and routers to the "right" of it) will not receive flooded traffic.

Flooding Disruption due to Link Spoofing

A compromised NHDP router can also spoof links to other NHDP routers, thereby making itself appear as the most appealing candidate to be MPR for its neighbors, possibly to the exclusion of other NHDP routers in the neighborhood. (In particular, this can occur if the compromised NHDP router spoofs links to all other NHDP routers in the neighborhood, plus to one NHDP router outside the neighborhood.) By thus excluding other legitimate NHDP routers from being selected as MPR, the compromised NHDP router will receive and be expected to Yi, et In the network in Figure 6, the compromised NHDP router X spoofs links to the existing router C, as well as to a fictitious W. Router A receives HELLOs from X and B, reporting X: {X-C, X-W}, B: {B-C}. All else being equal, X appears a better choice for MPR than B, as X appears to cover all neighbors of B, plus W.

Figure 6

As router A will not select B as MPR, B will not relay flooded messages received from router A. The NHDP routers on the left of B (starting with C) will, thus, not receive any flooded messages from router A or transiting router A (e.g., a message originating from S).

Broadcast Storm

A compromised NHDP router may attack the network by attempting to degrade the performance of optimized flooding algorithms so as to be equivalent to classic flooding. This can be achieved by forcing an NHDP router into choosing all its 1-hop neighbors as MPRs. In MANETs, a broadcast storm caused by classic flooding is a serious problem that can result in redundancy, contention, and collisions [START_REF] Ni | The Broadcast Storm Problem in a Mobile Ad Hoc Network[END_REF].

As shown in Figure 7, the compromised NHDP router X spoofs the identity of NHDP router B and, spoofs a link to router Y {B-Y} (Y does not have to exist). By doing so, the legitimate NHDP router A has to select the legitimate NHDP router B as its MPR in order for it to reach all its 2-hop neighbors.

Routing Loops

Inconsistent information bases, provided by NHDP to other protocols, can also cause routing loops. In Figure 8, the compromised NHDP router X spoofs the identity of NHDP router E. NHDP router D has data traffic to send to NHDP router A. The topology recorded in the information base of router D indicates that the shortest path to router A is {D->E->A}, because of the link {A-E} reported by X. Therefore, the data traffic will be routed to NHDP router E. As the link {A-E} does not exist in NHDP router E's information bases, it will identify the next hop for data traffic to NHDP router A as being NHDP router D. A loop between the NHDP routers D and E is thus created.

.---.

. By reporting inconsistent topology information in NHDP, the invalid links and routers can be propagated as link state information with traffic control messages and results in route failure. As illustrated in Figure 8, if NHDP router B tries to send data packets to NHDP router E, it will choose router A as its next hop, based on the information about the nonexistent link {A-E} reported by the compromised NHDP router X.

---. .---. .---. .---. | A |----| B |----| C |----| D |----| E | '---' '---' '---' '---' '---' | | .---. | X | '---' spoofs E

Data Sinkhole

With the ability to spoof multiple identities of legitimate NHDP routers (by eavesdropping, for example), the compromised NHDP router can represent a "data sinkhole" for its 1-hop and 2-hop neighbors. Data packets that come across its neighbors may be forwarded to the compromised NHDP router instead of to the real destination. The packet can then be dropped, manipulated, duplicated, etc., by the compromised NHDP router. As shown in Figure 8, if the compromised NHDP router X spoofs the identity of NHDP router E, all the data packets to E that cross NHDP routers A and B will be sent to NHDP router X, instead of to E.

Future Work

This document does not propose solutions to mitigate the security threats described in Section 4. However, this section aims at driving new work by suggesting which threats discussed in Section 4 could be addressed by deployments or applications.

o Section 4.1: Jamming -If a single router or a small area of the MANET is jammed, protocols could be specified that increase link metrics in NHDP for the jammed links. When a routing protocol such as OLSRv2 uses NHDP for neighborhood discovery, other paths leading "around" the jammed area would be preferred, and therefore would mitigate the threat to some extent.

Figure 1 Figure 2

 12 Figure 1

Figure 3 illustrates

 3 Figure3illustrates Indirect Channel Overloading with NHDP. A compromised NHDP router X advertises a symmetric spoofed link to the nonexistent NHDP router B (at time t0). Router A selects X as MPR upon reception of the HELLO then triggers a HELLO at t1. Overhearing this triggered HELLO, the attacker sends another HELLO at t2, advertising the link to B as lost; this causes NHDP router A to

,

  ----| C |----| B |----| A |----

  Figure 7

  Figure 8

  done to facilitate revocation mechanisms in certain MANET use cases where routers have sufficient capabilities to support asymmetric keys. o Section 4.3: Eavesdropping -[RFC7185] adds ICVs to HELLO messages but does not encrypt them. Therefore, eavesdropping of control traffic is not mitigated. Future work could provide encryption of control traffic for sensitive MANET topologies. Note that, other than using a single shared secret key, providing encryption of traffic among a set of neighbors (when that set is potentially undetermined) is nontrivial, especially without multiplying overheads. With traffic analysis, attackers could still deduce the network information like HELLO message triggering and HELLO message size, even though the HELLO messages are encrypted. o Section 4.4.2: Link spoofing -[RFC7185] provides certain protection against link spoofing, but an NHDP router has to "trust" the originator of a HELLO that the advertised links are correct. For example, if a router A reports a link to B, routers receiving HELLOs from A have to trust that B is actually a (symmetric) neighbor of A. New protocol work could address protection of links without overly increasing the space and time overheads. An immediate suggestion for deployments is to protect routers against being compromised and to distribute keys only to trusted routers. o Section 4.5: Replay Attacks -[RFC7185] uses ICVs and timestamps to provide some protection against replay attacks. It is still feasible to replay control messages within a limited time. A suggestion for deployments is to provide time synchronization between routers. New work could provide time synchronization mechanisms for certain MANET use cases or specify a mechanism using nonces instead of timestamps in HELLO messages. o Section 4.4.1: Identity spoofing; Section 4.6: Message timing attacks; Section 4.7: Indirect channel overloading; and Section 4.8: Attack on link quality update -[RFC7185] provides protection against these attacks, assuming the routers are not compromised.7. Security ConsiderationsThis document does not specify a protocol or a procedure. The document, however, reflects on security considerations for NHDP and MANET routing protocols using NHDP for neighborhood discovery.

	RFC 7186	Security Threats for NHDP	April 2014
	o Section 4.2: DoS -A DoS attack using a massive amount of HELLO messages can be mitigated by admitting only trusted routers to the network. [RFC7185] specifies a mechanism for adding Integrity Check Values (ICVs) to HELLO messages and therefore providing an admittance mechanism for NHDP routers to a MANET. (Note that adding ICVs creates a new DoS attack vector, as ICV verification requires CPU and memory resources.) However, using ICVs does not address the problem of compromised routers. Detecting compromised routers could be addressed in new work. [RFC7185] mandates implementation of a security mechanism that is based on shared keys and makes excluding single compromised routers difficult; Yi, et al. Informational [Page 16] work could be Yi, et al. Informational [Page 17]

Acknowledgments

The authors would like to gratefully acknowledge the following people for valuable comments and technical discussions: Teco Boot, Henning Rogge, Christopher Dearlove, John Dowdell, Joseph Macker, and all the other participants of the IETF MANET working group.

RFC 7186

Security Threats for NHDP April 2014 deselect the attacker as MPR, and to send another triggered message at t3. The cycle may be repeated, where the link X-B is advertised alternately as LOST and SYM.

MPRs(X) MPRs()


C Dearlove

T Clausen

7187 BAE Systems ATC Updates: 7181

This specification updates the Optimized Link State Routing Protocol version 2 (OLSRv2) with an optimization to improve the selection of routing multipoint relays. The optimization retains full interoperability between implementations of OLSRv2 with and without this optimization.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. . This document improves one area of the OLSRv2 specification.

One improvement included in OLSRv2, compared to its predecessor described in [START_REF] Clausen | The Optimized Link State Routing Protocol[END_REF], is the use of link metrics, rather than minimum-hop routing. A rationale for how link metrics were included in OLSRv2 is documented in [START_REF] Clausen | Rationale for the Use of Link Metrics in the Optimized Link State Routing Protocol Version 2 (OLSRv2)[END_REF]. However, one aspect of the use of link metrics described in [START_REF] Clausen | Rationale for the Use of Link Metrics in the Optimized Link State Routing Protocol Version 2 (OLSRv2)[END_REF], the removal of some unnecessarily selected routing multipoint relays (MPRs), was not included in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF]. This specification updates OLSRv2 to include this optimization.

Note that this optimization does not impact interoperability: implementations that do and do not implement this optimization will interoperate seamlessly.

Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

Additionally, this document uses the terminology of [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF].

Applicability Statement

This specification updates [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF]. As such, it is applicable to all implementations of this protocol. The optimization presented in this specification is simply permissive; it allows an additional optimization, and there is no requirement for any implementation to

Dearlove & Clausen Standards Track [Page 2]

RFC 7187

OLSRv2 Routing MPR Optimization April 2014 include it. However, inclusion of this optimization is advised; it can, in some cases, create smaller and fewer messages, without ever having the opposite effect.

[RFC7181] defines the properties for the selection of routing MPRs from among a router's symmetric 1-hop neighbors. The properties are o the selected MPRs must consist of a set of symmetric 1-hop neighbors that cover all the symmetric 2-hop neighbors, and o the selected MPRs must do so retaining a minimum distance route (1-hop, if present, or 2-hop) to each symmetric 2-hop neighbor.

The discussion in the latter part of Section 6.2 of [START_REF] Clausen | Rationale for the Use of Link Metrics in the Optimized Link State Routing Protocol Version 2 (OLSRv2)[END_REF] indicates that this requirement is overly prescriptive for routing MPR selection. The update to [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF] described in this specification permits a router to use the described optimization, while still being considered compliant with OLSRv2.

Note that whether or not a router is considered compliant, a router that implements the optimization described in this specification will interoperate successfully with routers that are not implementing this optimization.

Routing MPR Selection

A set of routing MPRs created as specified in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF] This update to OLSRv2 [RFC7181] permits an implementation that is compliant with OLSRv2 to (potentially) eliminate some unneeded routers from the routing MPR sets generated as described in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF], which also eliminates the need to include the corresponding information in generated Topology Control (TC) messages. Because this information is not used when included, this update to OLSRv2 [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF] does not present any additional security considerations, beyond those described in [START_REF] Clausen | The Optimized Link State Routing Protocol Version 2[END_REF].

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 2 4. Routing MPR Selection . . . . . . . . . . . . . . . . . . . . 3 5. Security Considerations . . . . . . . . . . . . . . . . . . .

	RFC 7187	OLSRv2 Routing MPR Optimization	April 2014
	Table of Contents
	1. 4
	6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .	4
	7. References . . . . . . . . . . . . . . . . . . . . . . . . .	4
	7.1. Normative References . . . . . . . . . . . . . . . . . .	4
	7.2. Informative References . . . . . . . . . . . . . . . . .	4
	1. Introduction
	The Optimized Link State Routing Protocol version 2 [RFC7181] is a
	proactive link state routing protocol designed for use in mobile ad
	hoc networks (MANETs) [RFC2501]
	Dearlove & Clausen	Standards Track	[Page 1]

Acknowledgments

The authors would like to gratefully acknowledge Philippe Jacquet (Alcatel-Lucent) for intense technical discussions and comments.