RFC 7185
Link Metrics for the Mobile Ad Hoc Network (MANET) Routing Protocol OLSRv2 - Rationale
RFC 7185: Rationale for the Use of Link Metrics in the Optimized Link State Routing Protocol Version 2 (OLSRv2) 🦋
Okay bestie, here's the vibe check on RFC 7185 💅 It's Informational, which means it's a historic record and not a Standards Track spec 📚 It came out in April 2014 with ISSN 2070-1721. Three authors wrote it: C. Dearlove from BAE Systems ATC, T. Clausen from LIX, Ecole Polytechnique, and P. Jacquet from Alcatel-Lucent Bell Labs 💜 The header doesn't list anything it obsoletes or updates, so it's doing its own thing 🌸
Abstract
OLSRv2 can give links metrics and use those metrics to pick routes that aren't just the fewest-hops route 🛣️ This doc is basically the diary of why link metrics got included in OLSRv2 and what design thinking went into it ✨
Status of This Memo
This doc is not an Internet Standards Track spec. It's published just for information 🎀
It's a product of the Internet Engineering Task Force (IETF) and it reflects the consensus of the IETF community 🫶 It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every IESG-approved doc qualifies for any level of Internet Standard, so check Section 2 of RFC 5741 for that 💅
For the latest status, errata, and how to send feedback, go to http://www.rfc-editor.org/info/rfc7185 🔗
Copyright Notice
Copyright (c) 2014 IETF Trust and the people listed as the document authors. All rights reserved 💜
This doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they stand on the publication date. Please read those carefully, because they spell out your rights and restrictions for this doc 📜 Any Code Components pulled out of this doc must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as described in the Simplified BSD License 🧚
This doc may include material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The people who control the copyright in some of that material may not have given the IETF Trust permission to allow modifications outside the IETF Standards Process. Without an adequate license from those copyright holders, this doc may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside that process. The one exception is formatting it for publication as an RFC or translating it into languages other than English 🌈
Table of Contents
1. Introduction ....................................................3
2. Terminology .....................................................5
3. Applicability ...................................................5
4. Motivational Scenarios ..........................................5
5. Link Metrics ....................................................7
5.1. Link Metric Properties .....................................7
5.2. Link Metric Types ..........................................8
5.3. Directional Link Metrics ..................................10
5.4. Reporting Link and Neighbor Metrics .......................10
5.5. Defining Incoming Link Metrics ............................12
5.6. Link Metric Values ........................................12
6. MPRs with Link Metrics .........................................14
6.1. Flooding MPRs .............................................14
6.2. Routing MPRs ..............................................16
6.3. Relationship between MPR Sets .............................19
7. Security Considerations ........................................21
8. Acknowledgements ...............................................21
9. Informative References .........................................21
Appendix A. MPR Routing Property .................................231. Introduction ✨
Okay so the Optimized Link State Routing Protocol version 1 (OLSRv1) [RFC3626] is a proactive routing protocol for mobile ad hoc networks (MANETs) [RFC2501] 🛸 OLSRv1 finds the shortest route from a router to every possible destination, where "shortest" means the fewest hops 🧭
Using only minimum-hop routes can end up giving you routes that are kinda bad in practice 😬 Section 4 has some examples. That's why one of the big features of the Optimized Link State Routing Protocol version 2 (OLSRv2) [RFC7181] is that it lets you pick routes using link metrics instead of just counting hops 💖
While OLSRv2 was being developed, the working group and authors kept going back and forth on how and why certain choices got made in the spec, especially around metric integration 🤔 Some of those choices are honestly non-intuitive, so this doc is a record of the considerations and decisions. It's here for informational discussion about motivation and the historic design choices 📚 If those same questions pop up again, this is the place to look 🫶
OLSRv2 uses the extensible message format [RFC5444] to add link metric info to the HELLO messages defined in the MANET Neighborhood Discovery Protocol (NHDP) [RFC6130], and to the Topology Control (TC) messages defined in [RFC7181] 🎀
Here's the flow: OLSRv2 first works out local link metrics from 1-hop neighbors, which are defined by a process outside OLSRv2 🔍 Then it distributes the link metric values it needs in HELLO and TC messages, and finally it builds routes with the minimum total link metric 🏁 Using a route metric that isn't just hop count is a natural extension, and link state protocols use it all the time 🌟
Now, a metric-based route selection process could have been added to OLSRv2 as an extension. But if that had happened, OLSRv2 routers that didn't implement the extension wouldn't recognize any link metric info and would try to use minimum hop-count routes 😭 Effectively, routers that did implement the extension and routers that didn't would disagree about how valuable links and routes are. That leads to the big routing sin of "looping" 🌀 So if metric-based route selection were only an extension, the two kinds of routers couldn't interoperate, and that would be a serious limitation of the extension. For that reason, link metrics were included as standard in OLSRv2 👑
This doc talks through the motivation and design rationale for how link metrics got included in OLSRv2. The main issues when adding link metrics to OLSRv2 were:
- Assigning metrics to links meant thinking about separate metrics for the two directions of a link. The receiving router works out the metric from transmitter to receiver. A metric used by OLSRv2 may be either of:
- A link metric, which is the metric of one specific link, from an OLSRv2 interface of the transmitting router to an OLSRv2 interface of the receiving router.
- A neighbor metric, which is the minimum of the link metrics between two OLSRv2 routers, in the indicated direction.
These two are necessarily the same when each router has a single OLSRv2 interface, but they can differ when either one has more. HELLO messages may include both link metrics and neighbor metrics. TC messages include only neighbor metrics 💅
- Metrics in OLSRv2 are defined to be dimensionless and additive 📏 Assigning them, including how they relate to real parameters like data rate, loss rate, and delay, and managing which metric gets chosen, is outside the scope of [RFC7181]. That spec just uses the metrics consistently 🧠 Within a single MANET, including all the pieces of a temporarily fragmented MANET, one single link metric choice is used. A registry of metric types (using extended types of a single Address Block TLV type) lets routers be configured to use only a subset of the available metric types 🗂️
- Node metrics were not included in OLSRv2. You can still implement node metrics by adding the corresponding value to all incoming link metrics at the corresponding router 🧩
- OLSRv1 had multipoint relays (MPRs) doing two jobs: optimized flooding, and reduced topology advertisement for routing. OLSRv2 [RFC7181] splits these into separate sets of MPRs, called "flooding MPRs" and "routing MPRs" ✂️ Flooding MPRs can be calculated as in [RFC3626], but using link metrics in OLSRv2 can improve MPR selection. Routing MPRs need a metric-aware selection algorithm. Selecting routing MPRs guarantees minimum distance routes using the chosen metric, while only using symmetric 2-hop neighborhood information from HELLO messages and routing MPR selector information from TC messages 🎯
- The protocol Information Bases defined in OLSRv2 include required metric values 📚 That also means additions to the protocol Information Bases defined in NHDP [RFC6130] when OLSRv2 uses them 💜
2. 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 🦋
3. Applicability 🎀
The goal of this doc is to keep the design considerations behind how link metrics got included in [RFC7181] ✨ It doesn't prescribe any behavior. It just explains some aspects of how OLSRv2 operates 🧚
4. Motivational Scenarios ✨
okay so let's talk about why we'd ever want a route that isn't the shortest one 👀 The basic situation is shown in Figure 1 🦋
A ----- X ----- B
\ /
\ /
Y ------- Z
Figure 1The minimum hop route from A to B goes through X. BUT if the links A to X and X to B are poor (like low data rate or unreliable 💀) and the links A to Y, Y to Z, and Z to B are better (like reliable and high data rate 🔥), then the route A to B via Y and Z may be preferred to the one via X. main character route, no notes 💅
There are also situations where we want to discourage some links, even if avoiding them doesn't give users any obvious benefit 🙈 Picture a network with lots of short-range links and a few long-range ones. Using minimum hop routes will immediately mean heavy use of those long-range links. That's especially messy if those links only reach far by losing data rate or being less reliable. Even if the long-range links are just as good as the short-range ones, it may be smarter to save them for when they're really valuable, like when one long-range link replaces several short-range links, instead of only saving the one link a minimum hop route needs 🧚
A related case is the privileged relay 👑 An example is an aerial router in an otherwise ground-based network. The aerial router might have a link to many, or even all, other routers. That would make every router try to send all its traffic (other than to symmetric 1-hop neighbors and some symmetric 2-hop neighbors) through the aerial router. It may be important to keep that capacity for when the aerial router is actually essential, like when the ground-based part of the network isn't connected at all 🌈
Link metrics can help with these scenarios ✨ For example, in Figure 1, the route A to Y to Z to B could be preferred over A to X to B by making the metrics on the first path 1 and the metrics on the second path 2. For the aerial privileged relay, it could be used only when necessary by giving its links maximal metric values, with much smaller values for everything else. Or, if the aerial link should be preferred over N ground links, you can give the ground links metric values of 1 and make the sum of the aerial node uplink and downlink metrics equal to N 🫶
Other cases might involve avoiding congested areas, routing around insecure routers, or routers that want to discourage being used as relays because of things like limited battery power 🔋 OLSRv2 does have another tool for this: a router's willingness to act as an MPR. But there are cases where that can't help, and where using non-minimum hop routes could 💖
Also, OLSRv2's optional use of link quality (through [RFC6130]) is NOT a solution to these problems 😭 Hmm, wait, let me be precise: it is not a solution here, lowkey. Using link quality as specified in [RFC6130] lets a router decline to use a link, not only for itself but on behalf of all routers. It doesn't, for example, let you use a link that's been judged too low quality to be generally useful as part of a route when no better links exist. So link quality and link metrics solve distinctly different problems, and we shouldn't mix them up 🎀
Something else to note: the loop-free property of OLSRv2 applies strictly only in the static state. When the network topology is changing and messages can be lost, transient loops can form 😬 But with update rates that match the rate of topology change, such loops will be sufficiently rare ✨ Changing link metrics is a form of network topology change, so it should be limited to a rate slower than the message information update rate. That update rate is defined by the parameters HELLO_INTERVAL, HELLO_MIN_INTERVAL, REFRESH_INTERVAL, TC_INTERVAL, and TC_MIN_INTERVAL 🌸
5. Link Metrics 🎀
this section is all about the required and selected properties of the link metrics used in OLSRv2, followed by implementation details that achieve those properties 💅
5.1. Link Metric Properties 💜
okay, so link metrics in OLSRv2 are:
- Dimensionless 🌸 They might correspond, directly or indirectly, to specific physical info (like delay, loss rate, or data rate), but OLSRv2 doesn't use that knowledge. Generating the metric value is the job of a mechanism outside OLSRv2 🙈
- Additive ➕ so the metric of a route is the sum of the metrics of the links forming that route. This requires a metric where a low value means a "good" link and a high value means a "bad" link, and the former will be preferred to the latter 🦋
- Directional ➡️ the metric from router A to router B doesn't have to match the metric from router B to router A, even when they use the same OLSRv2 interfaces. At router A, a link metric from router B to router A is called an incoming link metric, while a link metric from router A to router B is called an outgoing link metric. (These are reversed at router B, of course 🔁)
- Specific to a pair of OLSRv2 interfaces 🧚 so if there's more than one link from router A to router B, each one has its own link metric in that direction. There's 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, and it's 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 direction between OLSRv2 interfaces of those routers. When you're referring to a specific OLSRv2 interface (like in a Link Tuple or a HELLO message sent on that interface), a link metric always refers to a link on that interface to or from the indicated 1-hop neighbor interface. A neighbor metric, on the other hand, may be equal to a link metric to and/or from another OLSRv2 interface ✨
5.2. Link Metric Types 🍓
there are lots of physical characteristics that can define a link metric 🤓 Here are some examples, which also show some of the traits the resulting metrics end up having:
- Delay ⏱️ is super straightforward. Since it's naturally additive, the delay of a multi-link route is the sum of the delays of its links. This doesn't directly count delays caused by routers (like router queues or moving packets between router interfaces) instead of links, but those delays can be split up between incoming and outgoing links 💖
- Probability of loss on a link 📉 is, as long as the 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 aren't independent, then this will be pessimistic 😬
- Data rates are NOT additive 🙅♀️ (sorry, I'm getting loud, but this is important!) They even have the wrong characteristic of being good when high and bad when low. So a mapping that inverts the ordering must be applied. Such a mapping can, at best, only produce a metric that's acceptable to treat as additive 🫠 For example, say you prefer 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, starting from the lowest. If links may be of three discrete data rates, "high", "medium", and "low", then this preference can be achieved, assuming 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, 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 route 🦋). This mapping can be extended to a system with more data rate values. For example, it gives a 4 Mbit/s data rate a metric value of about 39 ✨ It may lose the ability to produce an absolutely maximal minimum data rate route, but it will usually produce either that or something close. (And sometimes maybe even better 🤔 Is a route of three 5 Mbit/s links really better than one of a single 4 Mbit/s link? Iykyk.) Specific metrics will need to define the mapping 💅
There are also many other possible metrics, including ones that use physical-layer information (like signal-to-noise ratio and error-control statistics) and information like packet-queuing statistics 🌈
In a well-designed network, all routers will use the same metric type 💯 It won't produce good routes if, for example, some link metrics are based on data rate and others 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 are outside the scope of OLSRv2 👀 That's because new metrics may be added in the future (for example, as data rates increase), and they may be based on new, possibly non-physical, considerations, like 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 needing to know whether it represents delay, probability of loss, data rate, cost, or any other quantity 🫶 This recognized link metric type number is a router parameter. It's subject to change in case of reconfiguration, or possibly with the use of a protocol (outside the scope of OLSRv2) that lets routers agree on a link metric type 🤝
The use of link metric type numbers also suggests the possibility of using multiple link metric types and multiple network topologies. This is a possible future extension to OLSRv2 🔮 To allow for that future possibility, sending more than one metric of different physical types is not prohibited (even though it should otherwise be avoided for reasons of efficiency). But types other than the configured one will be ignored 🙈
The following three sections assume a chosen single link metric type, of unspecified physical nature 💖
5.3. Directional Link Metrics ✨
okay so OLSRv2 only uses "symmetric" links 🦋 (bidirectional ones) that can carry traffic either way. The big question was whether each link gets one metric shared by both directions, or one metric per direction. ngl this one is giving main character energy 💅
- Links can be different in each direction 🌸, and directional metrics are how we respect that.
- In most cases (maybe all of them, honestly), the two ends of a link will look at the link and form different opinions about what its metric should be. A single shared metric means the two ends have to coordinate, and directional metrics skip that drama entirely. If you did use a single metric, both ends would have to agree on its value, or looping can happen 🌀 That problem just doesn't exist with directional metrics.
So OLSRv2 goes with directional metrics 👑 Each router is only responsible for defining the metric in one direction. It could have been either direction, a router handling incoming or outgoing link metrics, as long as everyone picks the same one. OLSRv2 picks incoming, because receiving routers usually have more info to work with when setting link metrics (like received signal strength, interference levels, and error-control coding statistics) 🧠✨
Here's the key bit: if router A defines the metric of the link from router B to router A, then router B has to use router A's definition of that metric on that link, in that direction. 🫶 (If it makes sense, router B could treat a really bad mismatch between directional metrics as a reason to stop using that link, using the link quality mechanism defined in [RFC6130]. Just know that's a separate thing from link metrics, not the same mechanism 🙈)
5.4. Reporting Link and Neighbor Metrics
okay bestie, links (and so link metrics) get reported in HELLO messages 📣 A router must report its incoming link metrics in its HELLO messages so the other end of the link can actually see them. Which means for a symmetric link, both ends end up knowing both the incoming and outgoing link metrics. iconic 💖
HELLO messages also advertise incoming neighbor metrics ✨ These are used for MPR selection (see Section 6.2), which needs the lowest metric link between two routers whenever more than one link exists between them. The neighbor metric might be using a different OLSRv2 interface, so the link metric alone just isn't enough. 🙅♀️
TC messages report metrics too 🎀 It can be shown that these need to be outgoing metrics:
- Router A has to be responsible for advertising the metric from router A to router B in TC messages. Picture routers P to Q to R to S, each with a single OLSRv2 interface 🧚 Router P only learns about the link from R to S through the TC messages sent by router R, which is an MPR of router S (assuming only MPR selectors get reported in TC messages). Router S might not even send TC messages at all, if nobody picked it as an MPR and it has no attached networks to report 💀 So any info about the metric of the link from R to S has to be included in the TC messages sent by router R. Hence, router R is the one responsible for reporting the metric for the link from R to S.
- In a more general case, with more than one link from R to S, the TC message has to report the minimum of those outgoing link metrics, so that minimum metric routes can be built (e.g., by router P). That minimum is the outgoing neighbor metric from R to S. 🌈
Back to our little crew: router P also hears about a link between Q and R in the HELLO messages sent by router Q 👀 Without metrics, OLSRv2 could use that link for 2-hop routing to router R, using just the HELLO messages from router Q. To keep that property (it speeds up local route formation, and it came over from OLSRv1) 🚀, router P needs to get the metric from Q to R in HELLO messages sent by router Q. That means router Q is responsible for reporting the metric for the outgoing link from Q to R. This is in addition to the incoming link metric info a HELLO message has to report. And again, in general, this should be the outgoing neighbor metric, not the outgoing link metric 🍓
Section 6.1 gives one more reason to report outgoing neighbor metrics in HELLO messages. Without it, metrics could only affect routing, not flooding 🌊
Quick note: you don't need to report an outgoing link metric in a HELLO message 💅 The corresponding 1-hop neighbor already knows that value, because it specified it. And for 2-hop neighborhood use, neighbor metrics are required, since they generally won't use the same OLSRv2 interface. 🫶
5.5. Defining Incoming Link Metrics
when a router reports a 1-hop neighbor in a HELLO message, it might do it for the first time with link status HEARD 👂 Since the router is responsible for defining and reporting incoming link metrics, it has to evaluate that metric and attach it to the right address (the one with link status HEARD) in the next HELLO message that reports that address on that OLSRv2 interface. There won't be an outgoing link metric to report yet, but the router must be able to decide on an incoming link metric right away once it has heard a 1-hop neighbor on an OLSRv2 interface for the first time. no pressure 😭
Why the rush? When the 1-hop neighbor receives a HELLO from this router and sees its own address listed with link status HEARD, it will (unless the separate link quality mechanism says otherwise) immediately consider that link SYMMETRIC 🤝 It'll advertise the link with that status in future HELLO messages and start using it for MPR selection and data traffic forwarding.
It might be too early for an ideal decision, depending on the physical nature of the link metric 🥺 But a choice still has to be made. The metric value can be refined later based on more observations of HELLO messages, other message transmissions between the routers, or other observations of the environment 🔍 It's probably best to over-estimate the metric if you're unsure, so you discourage the link rather than over-encourage it. If the only info you have is that a HELLO message was received, a conservative maximum link metric value should be used, the one denoted MAXIMUM_METRIC in [RFC7181] ✨
5.6. Link Metric Values
link metric values are recorded in LINK_METRIC TLVs (defined in [RFC7181]) using a compressed, lossy representation that takes up 12 bits 💜 12 bits is convenient because, with 4 flag bits of extra info (more on that below), you get a 2-octet value field. But that 12-bit design (and the 4 leftover flag bits) came from using a modified exponent/mantissa form with these properties:
- The values represented are positive integers starting at 1, 2, ...
- The maximum value represented should be close to, but less than,
2^24(^means exponentiation in this section) 🔢 This way, with a route limited to no more than 255 hops, the maximum route metric is less than2^32, i.e., it fits in 32 bits. (The link metric value fits in 24 bits.)
A representation modified from an exponent/mantissa form with e bits of exponent and m bits of mantissa, with the first property above, starts at 1, goes up by 1 until 2^m, then does another 2^m increments of 2, then another 2^m increments of 4, and so on for 2^e sets of increments 📈 That means the represented value is never off by more than a half (if rounding) or one (if truncating) part in 2^m, and usually less than that. 🎯
The position in the increment sequence, from 0 to 2^m-1, is treated as a form of mantissa and called a. The increment sequence number, from 0 to 2^e-1, is treated as a form of exponent and called b.
The value represented by (b,a) works out to (2^m+a+1)2^b-2^m. To verify, note that:
- With b fixed, the gap between two values with consecutive a is
2^b, as expected. - 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 gap between those two is2^(b+1), as expected. ✅
The maximum represented value has b = 2^e-1 and a = 2^m-1, and it comes out to (2^m+2^m)(2^(2^e-1))-2^m = 2^(2^e+m)-2^m. That's just a bit less than 2^(2^e+m). The required 24-bit limit can be hit if 2^e+m = 24. Out of the possible (e,m) pairs that satisfy this, the pair e = 4, m = 8 was picked as most appropriate, and that's what OLSRv2 uses 🎉 It uses the 12 bits we already mentioned (e+m = 12). An algorithm for converting a 24-bit value v into a 12-bit pair (b,a) is given in Section 6.2 of [RFC7181].
As mentioned above, the 12-bit representation shares two octets with 4 flag bits 🦋 Putting the flag bits first, it's natural to put the exponent bits in the last four bits of the first octet, and the mantissa bits in the second octet. The 12 consecutive bits, read in network byte order (most significant octet first), then represent 256b+a. The ordering of these 12-bit values is the same as the ordering of the 24-bit metric values, so two 12-bit metrics fields can be compared for equality or ordering as if they were unsigned integers. chef's kiss 🤌
The four flag bits each represent one kind of metric, defined by its direction (incoming or outgoing) and whether it's a link metric or a neighbor metric 🚩 Whatever flag bits are set tell you which kinds are present, and a metric value can be any combination of these four kinds.
6. MPRs with Link Metrics 👑
okay so MPRs get used for two things in OLSRv2 🎀 In both cases, it's the MPR selectors that actually get used, and those get figured out from the MPRs advertised in HELLO messages.
- Optimized Flooding. This uses the MPR selector status of symmetric 1-hop neighbor routers that messages arrive from, to decide whether those messages get forwarded. MPR selector status is recorded in the Neighbor Set (defined in
[RFC6130]and extended in[RFC7181]) and gets determined from received HELLO messages. 🌊 - Routing. Non-local link information comes from this router's Topology Information Base 🗺️ That info is based on received TC messages. The neighbor info in those TC messages is the addresses of the originating router's advertised (1-hop) neighbors, as recorded in that router's Neighbor Set (defined in
[RFC6130]and extended in[RFC7181]). Those advertised neighbors include all of the originating router's MPR selectors. 💖
Metrics interact with these two uses of MPRs in different ways, as the next two sections explain 🧚 This leads to a requirement for two separate sets of MPRs when you're using metrics, one for each use. How those two sets relate to each other is covered in Section 6.3. 🫶
6.1. Flooding MPRs ✨
okay so the big rule for flooding MPR selection is that a router has to pick a set of MPRs so that a message it sends, which then gets retransmitted by all of its flooding MPRs, reaches every single symmetric 2-hop neighbor of the router doing the picking 💅
here's the tea though: flooding MPR selection can totally ignore metrics and still give you a valid answer that meets the spec 🙄 BUT that doesn't mean metrics are useless here. they can be super helpful 🫶 check out Figure 2, where the numbers are the metrics of the links going away from router A, toward router D 👀
3
A ----- B
| |
1 | | 1
| |
C ----- D
4
Figure 2so the question is: which is the better flooding MPR for router A, B or C? 🤔 if the metric is probability of message loss, then B is the clear winner, because picking B maximizes the chance that a message sent by A actually reaches D 🎯 even though C has the lower metric on its link to A. (similar arguments for B work if the metric is data rate or delay instead of loss, btw 🦋)
but we can't only look at the second hop either 😭 now take that same network and change it to Figure 3, where the numbers are still metrics of links going away from A, toward D:
3
A ----- B
| |
1 | | 3
| |
C ----- D
4
Figure 3in this one it's possible that picking C is better than picking B when A is choosing flooding MPRs 🌈 and if the metrics are scaled delay values or loss probabilities, picking C is clearly the move 👑 which means the sum of metrics is a good way to decide between B and C ✨
BUT (and this is important bestie) this is a super simple example 🙈 in real life it's usually not just picking between two routers that each cover one extra router. when you're deciding which router to add next as a flooding MPR, you want a more general process that looks at the metric to that router, the metric from that router to each symmetric 2-hop neighbor, and how many new symmetric 2-hop neighbors it covers. other factors can get a seat at the table too 🍓
the required spec for flooding MPR selection is in Section 18.4 (also using Section 18.3) of [RFC7181] 📜 and it may use the example MPR selection algorithm in Appendix B of [RFC7181]. also, just like in [RFC3626], each router can make its own independent choice of flooding MPRs and its own flooding MPR selection algorithm and they'll all still interoperate 🤝 no drama!!
one more thing 💖 the directions I mentioned above are correct: for flooding, outward-facing directional metrics from a router are the ones that matter, i.e., the metrics in the direction the flooding is going. this is an extra reason to include outward metrics in HELLO messages, because otherwise metric-aware flooding MPR selection just isn't possible 😤 the second-hop metrics are outgoing neighbor metrics because the OLSRv2 interface used for a second-hop transmission might not be the same one used for the first-hop reception 🦋
6.2. Routing MPRs 🌸
the essential detail for routing MPR selection is that a router has to pick MPRs per OLSRv2 interface so that there's a 2-hop route from each symmetric 2-hop neighbor of the selecting router back to the selecting router, and the intermediate router on each of those routes has to be a routing MPR of the selecting router 💅✨
when you're using an additive link metric instead of a hop count, it's enough to make sure the routing MPRs give you not just any 2-hop route but a minimum distance 2-hop route 🎀 also, a router counts as a symmetric 2-hop neighbor even if it's also a symmetric 1-hop neighbor, as long as there's a 2-hop route to it that's shorter than the 1-hop link 🧚 (the property that no routes go through routers with willingness WILL_NEVER still holds. the examples below assume everyone is equally willing, with nobody at WILL_NEVER 🙌)
let's look at Figure 4 🦋 the numbers are metrics of links going toward router A, away from router D. router A has to pick router B as a routing MPR, whereas with minimum hop count routing it could pick C instead 🤷♀️ and yeah, using incoming neighbor metrics here follows the same logic as the directionality of metrics in TC messages, which you can read about in Section 5.4 📖
2
A ----- B
| |
1 | | 1
| |
C ----- D
3
Figure 4in Figure 5, the numbers are metrics of links going toward router A and away from router C 💜 router A has to pick router B as a routing MPR here, BUT with minimum hop count routing it wouldn't need to pick any MPRs at all 😳
1
A - B
\ |
4 \ | 2
\|
C
Figure 5Figure 6 is giving main character energy 👑 the numbers are metrics of links going toward router A and away from routers D and E. router A has to pick both B and C as routing MPRs, but with minimum hop count routing it could pick either one 💀
D E
|\ /|
| \ 3 / |
| \ / |
1 | \/ | 1
| /\ |
| / \ |
| / 2 \ |
|/ \|
B C
\ |
\ /
3 \ / 2
\ /
A
Figure 6Appendix A shows that if you select routing MPRs using this definition and only advertise those links (plus local link knowledge from HELLO messages), you'll end up with the lowest total metric routes 🎉 and that's true even if all links, advertised or not, get considered when defining a shortest route 🫶
however, the definition I just described is sufficient for routing MPR selection, but it's not necessary 🙈 check out Figure 7, where the numbers are metrics of links going toward router A, away from the other routers. the metrics from B to C and from C to B are both assumed to be 2 ✨
1
A ----- B
\ /
4 \ / 2
\ /
C ----- D ----- E
3 5
Figure 7using the above definition, A would have to pick both B and C as routing MPRs, so it covers the symmetric 2-hop neighbors C and D respectively 😤 (C counts as a symmetric 2-hop neighbor because the route through B is shorter than the 1-hop link.)
BUT A only actually needs to pick B 💅 the only reason to pick C would be so C can advertise the link to A for routing, to be used by something like E. however, A knows no other router should use the link from C to A on a shortest route, because going through B is shorter 🙅♀️ so if there's no need to advertise the link from C to A, there's no reason for A to pick C as a routing MPR. iconic behavior 🦋
this "thinning out" of routing MPR selection only uses local info from HELLO messages 🧠 with any minimum distance algorithm, the router finds the shortest routes (one hop, two hops, or more) from every router in its symmetric 2-hop neighborhood. then it picks as MPRs all the symmetric 1-hop neighbors that are the last router (right before the selecting router itself) on any of those routes 🌈 if there's more than one shortest route to the same router, only one of them is needed. and alternative routes can be chosen to minimize how many distinct last routers there are, which is the same idea as picking a minimal set of MPRs in the non-metric case 💖
just a heads up: this only removes routing MPRs whose selection can be directly seen to be unnecessary 🙃 so if the first approach (as shown in Appendix A) creates minimum distance routes, then this process does too 🥹
Figures 5 and 6 show that using link metrics might make a router select more routing MPRs than it would without metrics, and might even make it select routing MPRs when, without metrics, it wouldn't need any at all 😭 that can mean more, and bigger, messages being generated and forwarded more often 💀 so yes, using link metrics isn't free, even before you count the cost of link metric signaling 💸
these examples only consider routers with a single OLSRv2 interface 🌸 if routers have more than one OLSRv2 interface, the process stays the same, with one addition: if there's more than one known metric between two routers (on different OLSRv2 interfaces), then, looking at symmetric links only (since only those are used for routing), the smallest link metric, i.e., the neighbor metric, is used 🫧 there's no need to calculate routing MPRs per OLSRv2 interface. that requirement only comes up because of flooding and the need to avoid certain "race" conditions, which matter for flooding but not routing 🙌
the required spec for routing MPR selection is in Section 18.5 (also using Section 18.3) of [RFC7181] 📜 and it may use the example MPR selection algorithm in Appendix B of [RFC7181]. and once again, just like in [RFC3626], each router can make its own independent choice of routing MPRs and its own routing MPR selection algorithm and still interoperate 🤝✨
6.3. Relationship between MPR Sets
okay bestie, wouldn't it be so cute if the flooding MPRs and routing MPRs were the same set? 🥺 It would be super convenient 💅 That can happen when all the metrics are equal, but in general, for "good" sets of MPRs, they're just not the same 😭 (A reasonable way to define it: there's no common minimal set of MPRs.) It's especially unlikely when metrics are asymmetric (the two sets use opposite-direction metrics) or when routers have multiple OLSRv2 interfaces (routing MPRs can ignore that, but flooding MPRs can't) 🙈 Even with a symmetric metric and a single OLSRv2 interface on each router, the ideal sets don't have to match, and neither one is always a subset of the other. Let's look at some examples 🦋 In all of them, every lettered router is equally willing to be an MPR, and the numbers are bidirectional link metrics.
In Figure 8, A doesn't need any flooding MPRs. But A has to select B as a routing MPR 💖
1
A - B
\ |
4 \ | 2
\|
C
Figure 8In Figure 9, A must select C and D as routing MPRs. But A's minimal set of flooding MPRs is just B 👀 Here the routing MPRs also work as flooding MPRs, just not in the minimal way. (It might still be the better pick, depending on how much you care about the number of MPRs versus the flooding link metrics ✨)
2
C --- E
/ /
1 / / 1
/ 4 /
A --- B
\ \
1 \ \ 1
\ \
D --- F
2
Figure 9But it isn't always like that 😭 In Figure 10, A's routing MPRs must contain B, but they don't need to contain C. A's flooding MPRs don't need to contain B, but they must contain C. (In this case, if A picks B instead of C as a flooding MPR, flooding still reaches D, but it takes three hops instead of the minimum two that MPR flooding guarantees 💀)
2 1
B - C - D
| /
1 | / 4
|/
A
Figure 107. Security Considerations 🔐
okay, this part is serious, so listen up 🫶 An attacker can really mess with an OLSRv2 network by sending messages that look totally valid but carry wrong link metrics. This could be used to steer route choices or, in some cases, cause routing loops 😱 It's a sneakier and probably less effective attack than other kinds of invalid message injection, which can remove or add more basic network information, like whether certain routers and links even exist.
So no significantly new security issues came in with adding metrics to OLSRv2 🙌 Defending against injected invalid link metrics works the same way as defending against any other invalid message injection, as covered in the Security Considerations section of [RFC7181] ✨
There are also possible uses for link metrics in security countermeasures, like preferring links with better security properties (including better availability) over ones with poorer properties 🛡️ That said, it's beyond the scope of both this document and [RFC7181] 💅
8. Acknowledgements 🎀
The authors want to thank these people (listed alphabetically) for intense technical discussions, early reviews, and comments on the documents and their components: Brian Adamson (NRL), Alan Cullen (BAE Systems), Justin Dean (NRL), Ulrich Herberg (Fujitsu), Charles Perkins (Huawei), Stan Ratliff (Cisco), and Henning Rogge (FGAN) 🫶
They also want to give a big thank you to (listed alphabetically) Benoit Claise, Adrian Farrel, Stephen Farrell, and Suresh Krishnan for reviewing and commenting on the later draft versions of this document 🌸
9. Informative References 📚
[RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking
(MANET): Routing Protocol Performance Issues and
Evaluation Considerations", RFC 2501, January 1999.
[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
[RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, February 2009.
[RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc
Network (MANET) Neighborhood Discovery Protocol (NHDP)",
RFC 6130, April 2011.
[RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg,
"The Optimized Link State Routing Protocol Version 2", RFC
7181, April 2014.Appendix A. MPR Routing Property 🧚
Here's the deal: for routers to find and use shortest routes while running on the minimum reduced topology OLSRv2 supports (where a router only advertises its MPR selectors in TC messages), routing MPR selection has to give you the property that there are shortest routes where every intermediate router is a routing MPR 💖
This appendix uses the following terms and assumptions:
- The network is a graph of nodes connected by arcs. Nodes are routers whose willingness isn't
WILL_NEVER(except maybe at the ends of routes) 🌈 An arc is the set of symmetric links between those routers. The OLSRv2 interfaces those links use don't matter here. - Each arc has a metric in each direction. It's the minimum of the matching link metrics in that direction, which is the neighbor metric. This metric must be positive ✨
- A sequence of arcs joining two nodes is called a path.
- Node A is an MPR of node B if router A is a routing MPR of router B.
The required property (using shortest routes with the reduced topology) is the same as this: for any pair of distinct nodes X and Z, there's a shortest path from X to Z, X - Y1 - Y2 - ... - Ym - Z, where Y1 is an MPR of Y2, ..., Ym is an MPR of Z. We call that kind of path a routable path, and this property the routable path property 🦋
The required definition for a node X selecting MPRs is this: for each distinct node Z that has a two-arc path to X, there's a path that is shorter than or equally short to that two-arc path. That path is either Z - Y - X, where Y is an MPR of X, or the one-arc path Z - X. Note that this appendix doesn't cover locally known shorter paths with more than two arcs that could be used to reduce the number of MPRs 👀 (Those reductions only work when the remaining MPRs can be shown to keep all the necessary shortest paths, and so keep the required property.)
This appendix is about paths with minimum total metric, not minimum number of arcs (hop count), but it works by induction on the number of arcs in a path 🤓 It first looks at minimum metric routes with a bounded number of arcs, then lets that number grow so that overall minimum metric paths, no matter how many arcs they have, are included.
Specifically, the routable path property follows from this one: for all positive integers n and all distinct nodes X and Z, if there's any path from X to Z with n arcs or fewer, then there's a shortest path among those with n arcs or fewer that is a routable path. We call this the n-arc routable path property 💅
The n-arc routable path property is trivial for n = 1, and it follows directly from the definition of Z's MPRs for n = 2.
Using induction, assume the n-arc routable path property holds for n = k, and consider the case n = k+1.
Suppose X - V1 - V2 - ... - Vk - Z is a shortest path from X to Z with k+1 arcs. We build a path with no more than k+1 arcs that has the same or shorter length (so it's also the shortest, looking only at paths of up to k+1 arcs, by assumption) and is a routable path ✨
First, check whether Vk is an MPR of Z. If it isn't, look at the two-arc path Vk-1 - Vk - Z. This can be replaced either by the one-arc path Vk-1 - Z, or by the two-arc path Vk-1 - Wk - Z, where Wk is an MPR of Z and the metric from Vk-1 to Z is no longer on the replacement path. In the first case (the one-arc replacement), we now have a path of length k, so the previous inductive step can be used. In the second case, we've swapped Vk for Wk, which is an MPR of Z. So we only need to consider the case where Vk is an MPR of Z.
Next, apply the previous inductive step to the path X - V1 - ... - Vk-1 - Vk, replacing it with an equal-length path X - W1 - ... - Wm-1 - Vk, where m <= k and 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 it shows the n-arc routable path property for n = k+1 🎉
So for any distinct nodes X and Z, there's a routable path using the MPR-reduced topology from X to Z. That means OLSRv2 finds minimum length paths, meaning minimum total metric routes 💖
Authors' Addresses 💌
Christopher Dearlove
BAE Systems Advanced Technology Centre
West Hanningfield Road
Great Baddow, Chelmsford
United Kingdom
Phone: +44 1245 242194
EMail: chris.dearlove@baesystems.com
URI: http://www.baesystems.com/
Thomas Heide Clausen
LIX, Ecole Polytechnique
91128 Palaiseau Cedex
France
Phone: +33 6 6058 9349
EMail: T.Clausen@computer.org
URI: http://www.thomasclausen.org/
Philippe Jacquet
Alcatel-Lucent Bell Labs
Phone: +33 6 7337 1880
EMail: philippe.jacquet@alcatel-lucent.com📦 where this page comes from
- ietf: rfc7185 2014-04
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms