idnits 2.17.1 draft-ietf-manet-olsrv2-metrics-rationale-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to contain a disclaimer for pre-RFC5378 work, but was first submitted on or after 10 November 2008. The disclaimer is usually necessary only for documents that revise or obsolete older RFCs, and that take significant amounts of text from those RFCs. If you can contact all authors of the source material and they are willing to grant the BCP78 rights to the IETF Trust, you can and should remove the disclaimer. Otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (May 1, 2013) is 4007 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) C. Dearlove 3 Internet-Draft BAE Systems ATC 4 Intended status: Informational T. Clausen 5 Expires: November 2, 2013 LIX, Ecole Polytechnique 6 P. Jacquet 7 Alcatel-Lucent Bell Labs 8 May 1, 2013 10 Link Metrics for the Mobile Ad Hoc Network (MANET) Routing Protocol 11 OLSRv2 - Rationale 12 draft-ietf-manet-olsrv2-metrics-rationale-04 14 Abstract 16 OLSRv2 includes the ability to assign metrics to links and to use 17 those metrics to allow routing by other than minimum hop count 18 routes. This document provides a historic record of the rationale 19 for, and design considerations behind, how link metrics were included 20 in OLSRv2. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on November 2, 2013. 39 Copyright Notice 41 Copyright (c) 2013 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (http://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 This document may contain material from IETF Documents or IETF 55 Contributions published or made publicly available before November 56 10, 2008. The person(s) controlling the copyright in some of this 57 material may not have granted the IETF Trust the right to allow 58 modifications of such material outside the IETF Standards Process. 59 Without obtaining an adequate license from the person(s) controlling 60 the copyright in such materials, this document may not be modified 61 outside the IETF Standards Process, and derivative works of it may 62 not be created outside the IETF Standards Process, except to format 63 it for publication as an RFC or to translate it into languages other 64 than English. 66 Table of Contents 68 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 69 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 70 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 7 71 4. Motivational Scenarios . . . . . . . . . . . . . . . . . . . . 8 72 5. Link Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 10 73 5.1. Link Metric Properties . . . . . . . . . . . . . . . . . . 10 74 5.2. Link Metric Types . . . . . . . . . . . . . . . . . . . . 11 75 5.3. Directional Link Metrics . . . . . . . . . . . . . . . . . 12 76 5.4. Reporting Link and Neighbor Metrics . . . . . . . . . . . 13 77 5.5. Defining Incoming Link Metrics . . . . . . . . . . . . . . 14 78 5.6. Link Metric Values . . . . . . . . . . . . . . . . . . . . 15 79 6. MPRs with Link Metrics . . . . . . . . . . . . . . . . . . . . 17 80 6.1. Flooding MPRs . . . . . . . . . . . . . . . . . . . . . . 17 81 6.2. Routing MPRs . . . . . . . . . . . . . . . . . . . . . . . 19 82 6.3. Relationship Between MPR Sets . . . . . . . . . . . . . . 22 83 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 84 8. Security Considerations . . . . . . . . . . . . . . . . . . . 25 85 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 26 86 10. Informative References . . . . . . . . . . . . . . . . . . . . 27 87 Appendix A. MPR Routing Property . . . . . . . . . . . . . . . . 28 89 1. Introduction 91 The Optimized Link State Routing Protocol version 1 (OLSRv1) 92 [RFC3626] is a proactive routing protocol for Mobile Ad hoc NETworks 93 (MANETs) [RFC2501]. OLSRv1 finds shortest, defined as minimum number 94 of hops, routes from a router to all possible destinations. 96 Using only minimum hop routes may result in what are, in practice, 97 inferior routes. Some examples are given in Section 4. Thus, one of 98 the distinguishing features of the Optimized Link State Routing 99 Protocol version 2 (OLSRv2) [OLSRv2] is the introduction of the 100 ability to select routes using link metrics other than the number of 101 hops. 103 During the development of OLSRv2 the working group and authors 104 repeatedly discussed how and why some choices were made in the 105 protocol specification, particularly at the metric integration level. 106 Some of the issues may be non-intuitive and this document is 107 presented as a record of the considerations and decisions to provide 108 informational discussion about motivation and historic design 109 choices. This document is intended to be useful as a reference if 110 those questions arise again. 112 OLSRv2 essentially first determines local link metrics from 1-hop 113 neighbors, these being defined by a process outside OLSRv2, then 114 distributes required link metric values in HELLO messages and TC 115 messages, and then finally forms routes with minimum total link 116 metric. Using a definition of route metric other than number of hops 117 is a natural extension that is commonly used in link state protocols. 119 Use of the extensible message format [RFC5444] by OLSRv2 has allowed 120 the addition, by OLSRv2, of link metric information to the HELLO 121 messages defined in the MANET NeighborHood Discovery Protocol (NHDP) 122 [RFC6130] as well as inclusion in the Topology Control (TC) messages 123 defined in [OLSRv2]. 125 A metric-based route selection processes for OLSRv2 could have been 126 handled as an extension to OLSRv2. However were this to have been 127 done, OLSRv2 routers that did not implement this extension would not 128 recognize any link metric information, and would attempt to use 129 minimum hop-count routes. This would have meant that, in effect, 130 routers that did and did not implement this extension would differ 131 over their valuation of links and routes. This would have led to the 132 fundamental routing problem of "looping". Thus if metric-based route 133 selection were to have been considered only as an extension to 134 OLSRv2, then routers that did, and routers that did not, implement 135 this extension would not have been able to interoperate. This would 136 have been a significant limitation of such an extension. Link 137 metrics were therefore included as standard in OLSRv2. 139 This document discusses the motivation and design rationale behind 140 how link metrics were included in OLSRv2. The principal issues 141 involved when including link metrics in OLSRv2 were: 143 o Assigning metrics to links involved considering separate metrics 144 for the two directions of a link, with the receiving router 145 determining the metric from transmitter to receiver. A metric 146 used by OLSRv2 may be either of: 148 * A link metric, the metric of a specific link from an OLSRv2 149 interface of the transmitting router to an OLSRv2 interface of 150 the receiving router. 152 * A neighbor metric, the minimum of the link metrics between two 153 OLSRv2 routers, in the indicated direction. 155 These metrics are necessarily the same when these routers each 156 have a single OLSRv2 interface, but may differ when either has 157 more. HELLO messages may include both link metrics and neighbor 158 metrics. TC messages include only neighbor metrics. 160 o Metrics as used in OLSRv2 are defined to be dimensionless and 161 additive. The assignment of metrics, including their relationship 162 to real parameters such as data rate, loss rate and delay, and the 163 management of the choice of metric, is outside the scope of 164 [OLSRv2], which simply uses these metrics in a consistent manner. 165 Within a single MANET, including all components of a temporarily 166 fragmented MANET, a single choice of link metric is used. By use 167 of a registry of metric types (employing extended types of a 168 single Address Block TLV type), routers can be configured to use 169 only a subset of the available metric types. 171 o Node metrics were not included in OLSRv2. Node metrics can be 172 implemented by the addition of the corresponding value to all 173 incoming link metrics by the corresponding router. 175 o The separation of the two functions performed by MultiPoint Relays 176 (MPRs) in OLSRv1, optimized flooding and reduced topology 177 advertisement for routing, into separate sets of MPRs in OLSRv2 178 [OLSRv2], denoted "flooding MPRs" and "routing MPRs". Flooding 179 MPRs can be calculated as in [RFC3626], but the use of link 180 metrics in OLSRv2 can improve the MPR selection. Routing MPRs 181 need a metric-aware selection algorithm. The selection of routing 182 MPRs guarantees the use of minimum distance routes using the 183 chosen metric, while using only symmetric 2-hop neighborhood 184 information from HELLO messages and routing MPR selector 185 information from TC messages. 187 o The protocol Information Bases defined in OLSRv2 include required 188 metric values. This has included additions to the protocol 189 Information Bases defined in NHDP [RFC6130] when used by OLSRv2. 191 2. Terminology 193 All terms introduced in [RFC5444], including "message" and "TLV" 194 (type-length-value), are to be interpreted as described there. 196 All terms introduced in [RFC6130], including "MANET interface", 197 "HELLO message", "heard", "link", "symmetric link", "1-hop neighbor", 198 "symmetric 1-hop neighbor", "2-hop neighbor", "symmetric 2-hop 199 neighbor", "symmetric 2-hop neighborhood", and the symbolic constants 200 SYMMETRIC and HEARD, are to be interpreted as described there. 202 All terms introduced in [OLSRv2], including "router", "OLSRv2 203 interface", "willingness", "MultiPoint Relay (MPR)", "MPR selector", 204 "MPR flooding" and the TLV type LINK_METRIC are to be interpreted as 205 described there. 207 3. Applicability 209 The objective of this document is to retain the design considerations 210 behind how link metrics were included in [OLSRv2]. This document 211 does not prescribe any behavior, but explains some aspects of the 212 operation of OLSRv2. 214 4. Motivational Scenarios 216 The basic situation that suggests the desirability of use of routes 217 other than minimum hop routes is shown in Figure 1. 219 A ----- X ----- B 220 \ / 221 \ / 222 Y ------- Z 224 Figure 1 226 The minimum hop route from A to B is via X. However if the links A to 227 X and X to B are poor (e.g., having low data rate or being 228 unreliable) but the links A to Y, Y to Z and Z to B are better (e.g., 229 having reliable high data rate) then the route A to B via Y and Z may 230 be preferred to that via X. 232 There are other situations where, even if the avoidance of some links 233 does not show immediately obvious benefits to users, their use should 234 be discouraged. Consider a network with many short range links, and 235 a few long range links. Use of minimum hop routes will immediately 236 lead to heavy use of the long range links. This will be particularly 237 undesirable if those links achieve their longer range through reduced 238 data rate, or through being less reliable. However, even if the long 239 range links have the same characteristics as the short range links, 240 it may be better to reserve usage of the long range links for when 241 this usage is particularly valuable - for example when the use of one 242 long range link saves several short range links, rather than the 243 single link saving that is all that is needed for a minimum hop 244 route. 246 A related case is that of a privileged relay. An example is an 247 aerial router in an otherwise ground based network. The aerial 248 router may have a link to many, or even all, other routers. That 249 would lead to all routers attempting to send all their traffic (other 250 than to symmetric 1-hop neighbors and some symmetric 2-hop neighbors) 251 via the aerial router. It may however be important to reserve that 252 capacity for cases where the aerial router is actually essential, 253 such as if the ground based portion of the network is not connected. 255 Link metrics provide a possible solution to these scenarios. For 256 example, in Figure 1 the route A to Y to Z to B could be preferred to 257 A to X to B by making the metrics on the former path 1 and those on 258 the latter path 2. The aerial privileged relay could be used only 259 when necessary by giving its links maximal metric values, with much 260 smaller other metric values, or if the aerial link is to be preferred 261 to N ground links, giving the ground links metric values of 1, while 262 making the sum of the aerial node uplink and downlink metrics equal 263 to N. 265 Other cases may involve attempts to avoid areas of congestion, to 266 route around insecure routers (by preference, but prepared to use 267 them if there is no other alternative) and routers attempting to 268 discourage their use as relays due to, for example, limited battery 269 power. OLSRv2 does have another mechanism to aid in this, a router's 270 willingness to act as an MPR. However there are cases where that 271 cannot help, but where use of non-minimum hop routes could. 273 Similarly, note that OLSRv2's optional use of link quality (through 274 its use of [RFC6130]) is not a solution to these problems. Use of 275 link quality as specified in [RFC6130] allows a router to decline to 276 use a link, not only on its own, but on all routers' behalf. It does 277 not, for example, allow the use of a link otherwise determined to be 278 too low quality to be generally useful, as part of a route where no 279 better links exist. These mechanisms (link quality and link metrics) 280 solve distinctly different problems. 282 It should also be noted that the loop-free property of OLSRv2 applies 283 strictly only in the static state. When the network topology is 284 changing, and when messages can be lost, it is possible for transient 285 loops to form. However with update rates appropriate to the rate of 286 topology change, such loops will be sufficiently rare. Changing link 287 metrics is a form of network topology change, and should be limited 288 to a rate slower than the message information update rate (defined by 289 the parameters HELLO_INTERVAL, HELLO_MIN_INTERVAL, REFRESH_INTERVAL, 290 TC_INTERVAL and TC_MIN_INTERVAL). 292 5. Link Metrics 294 This section describes the required and selected properties of the 295 link metrics used in OLSRv2, followed by implementation details 296 achieving those properties. 298 5.1. Link Metric Properties 300 Link metrics in OLSRv2 are: 302 o Dimensionless. While they may, directly or indirectly, correspond 303 to specific physical information (such as delay, loss rate or data 304 rate), this knowledge is not used by OLSRv2. Instead, generating 305 the metric value is the responsibility of a mechanism external to 306 OLSRv2. 308 o Additive, so that the metric of a route is the sum of the metrics 309 of the links forming that route. Note that this requires a metric 310 where a low value of a link metric indicates a "good" link and a 311 high value of a link metric indicates a "bad" link, and the former 312 will be preferred to the latter. 314 o Directional, the metric from router A to router B need not be the 315 same as the metric from router B to router A, even when using the 316 same OLSRv2 interfaces. At router A, a link metric from router B 317 to router A is referred to as an incoming link metric, while a 318 link metric from router A to router B is referred to as an 319 outgoing link metric. (These are, of course, reversed at router 320 B.) 322 o Specific to a pair of OLSRv2 interfaces, so that if there is more 323 than one link from router A to router B, each has its own link 324 metric in that direction. There is also an overall metric, a 325 "neighbor metric", from router A to router B (its 1-hop neighbor). 326 This is the minimum value of the link metrics from router A to 327 router B, considering symmetric links only; it is undefined if 328 there are no such symmetric links. A neighbor metric from one 329 router to another is always equal to a link metric in the same 330 direction between OLSRv2 interfaces of those routers. When 331 referring to a specific OLSRv2 interface (for example in a Link 332 Tuple or a HELLO message sent on that OLSRv2 interface) a link 333 metric always refers to a link on that OLSRv2 interface, to or 334 from the indicated 1-hop neighbor OLSRv2 interface, while a 335 neighbor metric may be equal to a link metric to and/or from 336 another OLSRv2 interface. 338 5.2. Link Metric Types 340 There are various physical characteristics that may be used to define 341 a link metric. Some examples, which also illustrate some 342 characteristics of metrics that result, are: 344 o Delay is a straightforward metric, as it is naturally additive, 345 the delay of a multi-link route is the sum of the delays of the 346 links. This does not directly take into account delays due to 347 routers (such as due to router queues or transiting packets 348 between router interfaces), rather than links, but these delays 349 can be divided among incoming and outgoing links. 351 o Probability of loss on a link is, as long as probabilities of loss 352 are small and independent, approximately additive. (A slightly 353 more accurate approach is using a negatively scaled logarithm of 354 the probability of not losing a packet.) If losses are not 355 independent then this will be pessimistic. 357 o Data rates are not additive, it even has the wrong characteristic 358 of being good when high, bad when low; thus a mapping that inverts 359 its ordering must be applied. Such a mapping can, at best, only 360 produce a metric that it is acceptable to treat as additive. 361 Consider, for example, a preference for a route that maximizes the 362 minimum data rate link on the route, and then prefers a route with 363 the fewest links of each data rate from the lowest. If links may 364 be of three discrete data rates, "high", "medium", and "low", then 365 this preference can be achieved, on the assumption that no route 366 will have more than 10 links, with metric values of 1, 10 and 100 367 for the three data rates. 369 If routes can have more than 10 links, the range of metrics must 370 be increased; this was one reason for a preference for a wide 371 "dynamic range" of link metric values. Depending on the ratios of 372 the numerical values of the three data rates, the same effect may 373 be achieved by using a scaling of an inverse power of the 374 numerical values of the data rates. For example if the three data 375 rates were 2, 5 and 10 Mbit/s, then a possible mapping would be 376 the fourth power of 10 Mbit/s divided by the data rate, giving 377 metric values of 625, 16 and 1 (good for up to 16 links in a 378 route). This mapping can be extended to a system with more data 379 rate values, for example giving a 4 Mbit/s data rate a metric 380 value of about 39. This may lose the capability to produce an 381 absolutely maximum minimum data rate route, but will usually 382 produce either that, or something close (and at times maybe 383 better, is a route of three 5 Mbit/s links really better than one 384 of a single 4 Mbit/s link?). Specific metrics will need to define 385 the mapping. 387 There are also many other possible metrics, including using physical 388 layer information (such as signal to noise ratio, and error control 389 statistics) and information such as packet queuing statistics. 391 In a well-designed network, all routers will use the same metric 392 type. It will not produce good routes if, for example, some link 393 metrics are based on data rate and some on path loss (except to the 394 extent that these may be correlated). How to achieve this is an 395 administrative matter, outside the scope of OLSRv2. In fact even the 396 actual physical meanings of the metrics is outside the scope of 397 OLSRv2. This is because new metrics may be added in the future, for 398 example as data rates increase, and may be based on new, possibly 399 non-physical, considerations, for example financial cost. Each such 400 type will have a metric type number. Initially a single link metric 401 type zero is defined as indicating a dimensionless metric with no 402 predefined physical meaning. 404 An OLSRv2 router is instructed which single link metric type to use 405 and recognize, without knowing whether it represents delay, 406 probability of loss, data rate, cost or any other quantity. This 407 recognized link metric type number is a router parameter, and subject 408 to change in case of reconfiguration, or possibly the use of a 409 protocol (outside the scope of OLSRv2) permitting a process of link 410 metric type agreement between routers. 412 The use of link metric type numbers also suggests the possibility of 413 use of multiple link metric types and multiple network topologies. 414 This is a possible future extension to OLSRv2. To allow for that 415 future possibility, the sending of more than one metric, of different 416 physical types, which should otherwise not be done for reasons of 417 efficiency, is not prohibited, but types other than that configured 418 will be ignored. 420 The following three sections assume a chosen single link metric type, 421 of unspecified physical nature. 423 5.3. Directional Link Metrics 425 OLSRv2 uses only "symmetric" (bidirectional) links, which may carry 426 traffic in either direction. A key decision was whether these links 427 should each be assigned a single metric, used in both directions, or 428 a metric in each direction, noting that: 430 o Links can have different characteristics in each direction, use of 431 directional link metrics recognizes this. 433 o In many (possibly most) cases, the two ends of a link will 434 naturally form different views as to what the link metric should 435 be. To use a single link metric requires a coordination between 436 the two that can be avoided if using directional metrics. Note 437 that if using a single metric, it would be essential that the two 438 ends agree as to its value, otherwise it is possible for looping 439 to occur. This problem does not occur for directional metrics. 441 Based on these considerations, directional metrics are used in 442 OLSRv2. Each router must thus be responsible for defining the metric 443 in one direction only. This could have been in either direction, 444 i.e., that a router is responsible for either incoming or outgoing 445 link metrics, as long as the choice is universal. The former 446 (incoming) case is used in OLSRv2 because, in general, receiving 447 routers have more information available to determine link metrics 448 (for example received signal strength, interference levels, and error 449 control coding statistics). 451 Note that, using directional metrics, if router A defines the metric 452 of the link from router B to router A, then router B must use router 453 A's definition of that metric on that link in that direction. 454 (Router B could, if appropriate, use a bad mismatch between 455 directional metrics as a reason to discontinue use of this link, 456 using the link quality mechanism defined in [RFC6130]; note that this 457 is a distinct mechanism from the use of link metrics.) 459 5.4. Reporting Link and Neighbor Metrics 461 Links, and hence link metrics, are reported in HELLO messages. A 462 router must report incoming link metrics in its HELLO messages in 463 order that these are each available at the other end of the link. 464 This means that, for a symmetric link, both ends of the link will 465 know both of the incoming and outgoing link metrics. 467 As well as advertising incoming link metrics, HELLO messages also 468 advertise incoming neighbor metrics. These are used for routing MPR 469 selection (see Section 6.2), which requires use of the lowest metric 470 link between two routers when more than one link exists. This 471 neighbor metric may be using another OLSRv2 interface, and hence the 472 link metric alone is insufficient. 474 Metrics are also reported in TC messages. It can be shown that these 475 need to be outgoing metrics: 477 o Router A must be responsible for advertising a metric from router 478 A to router B in TC messages. This can be seen by considering a 479 route connecting single OLSRv2 interface routers P to Q to R to S. 480 Router P receives its only information about the link from R to S 481 in the TC messages transmitted by router R, which is an MPR of 482 router S (assuming that only MPR selectors are reported in TC 483 messages). Router S may not even transmit TC messages (if no 484 routers have selected it as an MPR and it has no attached networks 485 to report). So any information about the metric of the link from 486 R to S must also be included in the TC messages sent by router R, 487 hence router R is responsible for reporting the metric for the 488 link from R to S. 490 o In a more general case, where there may be more than one link from 491 R to S, the TC message must, in order that minimum metric routes 492 can be constructed (e.g., by router P) report the minimum of these 493 outgoing link metrics, i.e., the outgoing neighbor metric from R 494 to S. 496 In this example, router P also receives information about the 497 existence of a link between Q and R in the HELLO messages sent by 498 router Q. Without the use of metrics, this link could be used by 499 OLSRv2 for two hop routing to router R, using just HELLO messages 500 sent by router Q. For this property (which accelerates local route 501 formation) to be retained (from OLSRv1) router P must receive the 502 metric from Q to R in HELLO messages sent by router Q. This indicates 503 that router Q must be responsible for reporting the metric for the 504 outgoing link from Q to R. This is in addition to the incoming link 505 metric information that a HELLO message must report. Again, in 506 general, this must be the outgoing neighbor metric, rather than the 507 outgoing link metric. 509 In addition, Section 6.1 offers an additional reason for reporting 510 outgoing neighbor metrics in HELLO messages, without which metrics 511 can properly affect only routing, not flooding. 513 Note that there is no need to report an outgoing link metric in a 514 HELLO message. The corresponding 1-hop neighbor knows that value, it 515 specified it. Furthermore, for 2-hop neighborhood use, neighbor 516 metrics are required (as these will, in general, not use the same 517 OLSRv2 interface). 519 5.5. Defining Incoming Link Metrics 521 When a router reports a 1-hop neighbor in a HELLO message, it may do 522 so for the first time with link status HEARD. As the router is 523 responsible for defining and reporting incoming link metrics, it must 524 evaluate that metric, and attach that link metric to the appropriate 525 address (which will have link status HEARD) in the next HELLO message 526 reporting that address on that OLSRv2 interface. There will, at this 527 time, be no outgoing link metric available to report, but a router 528 must be able to immediately decide on an incoming link metric once it 529 has heard a 1-hop neighbor on an OLSRv2 interface for the first time. 531 This is because, when receiving a HELLO message from this router, the 532 1-hop neighbor seeing its own address listed with link status HEARD 533 will (unless the separate link quality mechanism indicates otherwise) 534 immediately consider that link to be SYMMETRIC, advertise it with 535 that link status in future HELLO messages, and use it (for MPR 536 selection and data traffic forwarding). 538 It may, depending on the physical nature of the link metric, be too 539 early for an ideal decision as to that metric, however a choice must 540 be made. The metric value may later be refined based on further 541 observation of HELLO messages, other message transmissions between 542 the routers, or other observations of the environment. It will 543 probably be best to over-estimate the metric if initially uncertain 544 as to its value, to discourage, rather than over-encourage, its use. 545 If no information other than the receipt of the HELLO message is 546 available, then a conservative maximum link metric value, denoted 547 MAXIMUM_METRIC in [OLSRv2], should be used. 549 5.6. Link Metric Values 551 Link metric values are recorded in LINK_METRIC TLVs, defined in 552 [OLSRv2], using a compressed (lossy) representation that occupies 12 553 bits. The use of 12 bits is convenient because, when combined with 4 554 flag bits of additional information, described below, this results in 555 a 2 octet value field. However the use of 12 bits, and thus the 556 availability of 4 flag bits, was a consequence of a design to use a 557 modified exponent/mantissa form with the following characteristics: 559 o The values represented are to be positive integers starting 1, 2, 560 ... 562 o The maximum value represented should be close to, but less than 563 2^24 (^ denotes exponentiation in this section). This is so that 564 with a route limited to no more than 255 hops, the maximum route 565 metric is less than 2^32, i.e., can be stored in 32 bits. (The 566 link metric value can be stored in 24 bits.) 568 A representation, modified from an exponent/mantissa form with e bits 569 of exponent and m bits of mantissa, and which has the first of these 570 properties is one that starts at 1, then is incremented by 1 up to 571 2^m, then has a further 2^m increments by 2, then a further 2^m 572 increments by 4, and so on for 2^e sets of increments. This means 573 that the represented value is never in error by more than a half (if 574 rounding) or one (if truncating) part in 2^m, usually less. 576 The position in the increment sequence, from 0 to 2^m-1, is 577 considered as a form of mantissa, and denoted a. The increment 578 sequence number, from 0 to 2^e-1, is considered as a form of 579 exponent, and denoted b. 581 The value represented by (b,a) can then be shown to be equal to (2^m+ 582 a+1)2^b-2^m. To verify this, note that: 584 o With fixed b, the difference between two values with consecutive 585 values of a is 2^b, as expected. 587 o The value represented by (b,2^m-1) is (2^m+2^m)2^b-2^m. The value 588 represented by (b+1,0) is (2^m+1)(2^(b+1))-2^m. The difference 589 between these two values is 2^(b+1), as expected. 591 The maximum represented value has b = 2^e-1 and a = 2^m-1, and is 592 (2^m+2^m)(2^(2^e-1))-2^m = 2^(2^e+m)-2^m. This is slightly less than 593 2^(2^e+m). The required 24 bit limit can be achieved if 2^e+m = 24. 594 Of the possible (e,m) pairs that satisfy this equation, the pair e = 595 4, m = 8 was selected as most appropriate, and is that used by 596 OLSRv2. It uses the previously indicated e+m = 12 bits. An 597 algorithm for converting from a 24 bit value v to a 12 bit pair (b,a) 598 is given in Section 6.2 of [OLSRv2]. 600 As noted above, the 12 bit representation then shares two octets with 601 4 flag bits. Putting the flag bits first, it is then natural to put 602 the exponent bits in the last four bits of the first octet, and to 603 put the mantissa bits in the second octet. The 12 consecutive bits, 604 using network byte order (most significant octet first), then 605 represent 256b+a. Note that the ordering of these 12 bit 606 representation values is the same as the ordering of the 24 bit 607 metric values. In other words, two 12 bit metrics fields can be 608 compared for equality/ordering as if they were unsigned integers. 610 The four flag bits each represent one kind of metric, defined by its 611 direction (incoming or outgoing) and whether the metric is a link 612 metric or a neighbor metric. As indicated by the flag bits set, a 613 metric value may be of any combination of these four kinds of metric. 615 6. MPRs with Link Metrics 617 MPRs are used for two purposes in OLSRv2. In both cases it is MPR 618 selectors that are actually used, MPR selectors being determined from 619 MPRs advertised in HELLO messages. 621 o Optimized Flooding. This uses the MPR selector status of 622 symmetric 1-hop neighbor routers from which messages are received 623 in order to determine if these messages are to be forwarded. MPR 624 selector status is recorded in the Neighbor Set (defined in 625 [RFC6130] and extended in [OLSRv2]), and determined from received 626 HELLO messages. 628 o Routing. Non-local link information is based on information 629 recorded in this router's Topology Information Base. That 630 information is based on received TC messages. The neighbor 631 information in these TC messages consists of addresses of the 632 originating router's advertised (1-hop) neighbors, as recorded in 633 that router's Neighbor Set (defined in [RFC6130] and extended in 634 [OLSRv2]). These advertised neighbors include all of the MPR 635 selectors of the originating router. 637 Metrics interact with these two uses of MPRs differently, as 638 described in the following two sections, and which leads to the 639 requirement for two separate sets of MPRs for these two uses when 640 using metrics. The relationship between these two sets of MPRs is 641 considered in Section 6.3. 643 6.1. Flooding MPRs 645 The essential detail of the "flooding MPR" selection specification is 646 that a router must select a set of MPRs such that a message 647 transmitted by a router, and re-transmitted by all its flooding MPRs, 648 will reach all of the selecting router's symmetric 2-hop neighbors. 650 Flooding MPR selection can ignore metrics and produce a solution that 651 meets the required specification. However, that does not mean that 652 metrics cannot be usefully considered in selecting flooding MPRs. 653 Consider the network in Figure 2, where numbers are metrics of links 654 in the direction away from router A, towards router D. 656 3 657 A ----- B 658 | | 659 1 | | 1 660 | | 661 C ----- D 662 4 664 Figure 2 666 Which is the better flooding MPR selection by router A: B or C? If 667 the metric represents probability of message loss, then clearly 668 choosing B maximizes the probability of a message sent by A reaching 669 D. This is despite that C has a lower metric in its connection to A 670 than B does. (Similar arguments about a preference for B can be made 671 if, for example, the metric represents data rate or delay rather than 672 probability of loss.) 674 However, neither should only the second hop be considered. If this 675 example is modified to that in Figure 3, where the numbers still are 676 metrics of links in the direction away from router A, towards router 677 D: 679 3 680 A ----- B 681 | | 682 1 | | 3 683 | | 684 C ----- D 685 4 687 Figure 3 689 then it is possible that, when A is selecting flooding MPRs, 690 selecting C is preferable to selecting B. If the metrics represent 691 scaled values of delay, or the probability of loss, then selecting C 692 is clearly better. This indicates that the sum of metrics is an 693 appropriate measure to use to choose between B and C. 695 However, this is a particularly simple example. Usually it is not a 696 simple choice between two routers as a flooding MPR, each only adding 697 one router coverage. A more general process, when considering which 698 router to next add as a flooding MPR, should incorporate the metric 699 to that router, and the metric from that router to each symmetric 700 2-hop neighbor, as well as the number of newly covered symmetric 701 2-hop neighbors, and may include other factors. 703 The required specification for flooding MPR selection is in Section 704 18.4 (also using Section 18.3) of [OLSRv2]. which may use the example 705 MPR selection algorithm in Appendix B of [OLSRv2]. However, note 706 that (as in [RFC3626]) each router can make its own independent 707 choice of flooding MPRs, and flooding MPR selection algorithm, and 708 still interoperate. 710 Also note that the references above to the direction of the metrics 711 is correct: for flooding, directional metrics outward from a router 712 are appropriate, i.e., metrics in the direction of the flooding. 713 This is an additional reason for including outward metrics in HELLO 714 messages, as otherwise a metric-aware MPR selection for flooding is 715 not possible. The second hop metrics are outgoing neighbor metrics 716 because the OLSRv2 interface used for a second hop transmission may 717 not be the same as that used for the first hop reception. 719 6.2. Routing MPRs 721 The essential detail of the "routing MPR" selection specification is 722 that a router must, per OLSRv2 interface, select a set of MPRs such 723 that there is a two hop route from each symmetric 2-hop neighbor of 724 the selecting router to the selecting router, with the intermediate 725 router on each such route being a routing MPR of the selecting 726 router. 728 It is sufficient, when using an additive link metric rather than a 729 hop count, to require that these routing MPRs provide not just a two 730 hop route, but a minimum distance two hop route. In addition, a 731 router is a symmetric 2-hop neighbor even if it is a symmetric 1-hop 732 neighbor, as long as there is a two hop route from it that is shorter 733 than the one hop link from it. (The property that no routes go 734 through routers with willingness WILL_NEVER is retained. Examples 735 below assume that all routers are equally willing, with none having 736 willingness WILL_NEVER.) 738 For example, consider the network in Figure 4. Numbers are metrics 739 of links in the direction towards router A, away from router D. 740 Router A must pick router B as a routing MPR, whereas for minimum hop 741 count routing it could alternatively pick router C. Note that the use 742 of incoming neighbor metrics in this case follows the same reasoning 743 as for the directionality of metrics in TC messages, as described in 744 Section 5.4. 746 2 747 A ----- B 748 | | 749 1 | | 1 750 | | 751 C ----- D 752 3 754 Figure 4 756 In Figure 5, where numbers are metrics of links in the direction 757 towards router A, away from router C, router A must pick router B as 758 a routing MPR, but for minimum hop count routing it would not need to 759 pick any MPRs. 761 1 762 A - B 763 \ | 764 4 \ | 2 765 \| 766 C 768 Figure 5 770 In Figure 6, where numbers are metrics of links in the direction 771 towards router A, away from routers D and E, router A must pick both 772 routers B and C as routing MPRs, but for minimum hop count routing it 773 could pick either. 775 D E 776 |\ /| 777 | \ 3 / | 778 | \ / | 779 1 | \/ | 1 780 | /\ | 781 | / \ | 782 | / 2 \ | 783 |/ \| 784 B C 785 \ | 786 \ / 787 3 \ / 2 788 \ / 789 A 791 Figure 6 793 It is shown in Appendix A that selecting routing MPRs according to 794 this definition, and advertising only such links (plus knowledge of 795 local links from HELLO messages), will result in selection of lowest 796 total metric routes, even if all links (advertised or not) are 797 considered in the definition of a shortest route. 799 However the definition noted above as sufficient for routing MPR 800 selection is not necessary. For example, consider the network in 801 Figure 7, where numbers are metrics of links in the direction towards 802 router A, away from other routers; the metrics from B to C and C to B 803 are both assumed to be 2. 805 1 806 A ----- B 807 \ / 808 4 \ / 2 809 \ / 810 C ----- D ----- E 811 3 5 813 Figure 7 815 Using the above definition, A must pick both B and C as routing MPRs, 816 in order to cover the symmetric 2-hop neighbors C and D, 817 respectively. (C is a symmetric 2-hop neighbor because the route 818 length via B is shorter than the 1-hop link.) 820 However, A only needs to pick B as a routing MPR, because the only 821 reason to pick C as a routing MPR would be so that C can advertise 822 the link to A for routing - to be used by, for example, E. But A 823 knows that no other router should use the link C to A in a shortest 824 route, because routing via B is shorter. So if there is no need to 825 advertise the link from C to A, then there is no reason for A to 826 select C as a routing MPR. 828 This process of "thinning out" the routing MPR selection uses only 829 local information from HELLO messages. Using any minimum distance 830 algorithm, the router identifies shortest routes, whether one, two or 831 more hops, from all routers in its symmetric 2-hop neighborhood. It 832 then selects as MPRs all symmetric 1-hop neighbors that are the last 833 router (before the selecting router itself) on any such route. Where 834 there is more than one shortest distance route from a router, only 835 one such route is required. Alternative routes may be selected so as 836 to minimize the number of last routers - this is the equivalent to 837 the selection of a minimal set of MPRs in the non-metric case. 839 Note that this only removes routing MPRs whose selection can be 840 directly seen to be unnecessary. Consequently if (as is shown in 841 Appendix A) the first approach creates minimum distance routes, then 842 so does this process. 844 The examples in Figure 5 and Figure 6 show that use of link metrics 845 may require a router to select more routing MPRs than when not using 846 metrics, and even require a router to select routing MPRs when 847 without metrics it would not need any routing MPRs. This may result 848 in more, and larger, messages being generated, and forwarded more 849 often. Thus the use of link metrics is not without cost, even 850 excluding the cost of link metric signaling. 852 These examples consider only single OLSRv2 interface routers. 853 However if routers have more than one OLSRv2 interface, then the 854 process is unchanged, other than that if there is more than one known 855 metric between two routers (on different OLSRv2 interfaces), then, 856 considering symmetric links only (as only these are used for routing) 857 the smallest link metric, i.e., the neighbor metric, is used. There 858 is no need to calculate routing MPRs per OLSRv2 interface. That 859 requirement results from the consideration of flooding and the need 860 to avoid certain "race" conditions, which are not relevant to 861 routing, only to flooding. 863 The required specification for routing MPR selection is in Section 864 18.5 (also using Section 18.3) of [OLSRv2]. which may use the example 865 MPR selection algorithm in Appendix B of [OLSRv2]. However, note 866 that (as in [RFC3626]) each router can make its own independent 867 choice of routing MPRs, and routing MPR selection algorithm, and 868 still interoperate. 870 6.3. Relationship Between MPR Sets 872 It would be convenient if the two sets of flooding and routing MPRs 873 were the same. This can be the case if all metrics are equal, but in 874 general, for "good" sets of MPRs they are not. (A reasonable 875 definition of this is that there is no common minimal set of MPRs.) 876 If metrics are asymmetrically valued (the two sets of MPRs use 877 opposite direction metrics), or routers have multiple OLSRv2 878 interfaces (where routing MPRs can ignore this, but flooding MPRs 879 cannot) this is particularly unlikely. However even using a 880 symmetrically valued metric with a single OLSRv2 interface on each 881 router, the ideal sets need not be equal, nor is one always a subset 882 of the other. To show this, consider these examples, where all 883 lettered routers are assumed equally willing to be MPRs, and numbers 884 are bidirectional metrics for links. 886 In Figure 8, A does not require any flooding MPRs. However A must 887 select B as a routing MPR. 889 1 890 A - B 891 \ | 892 4 \ | 2 893 \| 894 C 896 Figure 8 898 In Figure 9, A must select C and D as routing MPRs. However A's 899 minimal set of flooding MPRs is just B. In this example the set of 900 routing MPRs serves as a set of flooding MPRs, but a non-minimal one 901 (although one that might be better, depending on the relative 902 importance of number of MPRs and flooding link metrics). 904 2 905 C --- E 906 / / 907 1 / / 1 908 / 4 / 909 A --- B 910 \ \ 911 1 \ \ 1 912 \ \ 913 D --- F 914 2 916 Figure 9 918 However, this is not always the case. In Figure 10, A's set of 919 routing MPRs must contain B, but need not contain C. A's set of 920 flooding MPRs need not contain B, but must contain C. (In this case, 921 flooding with A selecting B rather than C as a flooding MPR will 922 reach D, but in three hops rather than the minimum two that MPR 923 flooding guarantees.) 925 2 1 926 B - C - D 927 | / 928 1 | / 4 929 |/ 930 A 932 Figure 10 934 7. IANA Considerations 936 This document has no actions for IANA. 938 This section may be removed by the RFC Editor. 940 8. Security Considerations 942 An attacker can have an adverse impact on an OLSRv2 network by 943 creating apparently valid messages that contain incorrect link 944 metrics. This could take the form of influencing the choice of 945 routes, or in some cases producing routing loops. This is a more 946 subtle, and likely to be less effective, attack, than other forms of 947 invalid message injection. These can add and remove other and more 948 basic forms of network information, such as the existence of some 949 routers and links. 951 As such, no significantly new security issues arose from the 952 inclusion of metrics in OLSRv2. Defenses to the injection of invalid 953 link metrics are the same as to other forms of invalid message 954 injection, as discussed in the security considerations section of 955 [OLSRv2]. 957 There are possible uses for link metrics in the creation of security 958 countermeasures, to prefer the use of links that have better security 959 properties, including better availability, to those with poorer 960 security properties. This however is beyond the scope of both this 961 document and [OLSRv2]. 963 9. Acknowledgements 965 The authors would like to gratefully acknowledge the following people 966 for intense technical discussions, early reviews and comments on the 967 documents and its components (listed alphabetically): Brian Adamson 968 (NRL), Alan Cullen (BAE Systems), Justin Dean (NRL), Ulrich Herberg 969 (Fujitsu), Stan Ratliff (Cisco), Charles Perkins (Huawei), and 970 Henning Rogge (FGAN). 972 Finally, the authors would like to express their gratitude to (listed 973 alphabetically) Benoit Claise, Adrian Farrel, Stephen Farrell and 974 Suresh Krishnan for their reviews and comments on the later versions 975 of this document. 977 10. Informative References 979 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 980 (MANET): Routing Protocol Performance Issues and 981 Evaluation Considerations", RFC 2501, January 1999. 983 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 984 Routing Protocol", RFC 3626, October 2003. 986 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 987 "Generalized MANET Packet/Message Format", RFC 5444, 988 February 2009. 990 [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc 991 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 992 RFC 6130, April 2011. 994 [OLSRv2] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 995 "The Optimized Link State Routing Protocol version 2", 996 draft-ietf-manet-olsrv2-19.txt (work in progress), 997 March 2013. 999 Appendix A. MPR Routing Property 1001 In order that routers can find and use shortest routes in a network 1002 while using the minimum reduced topology supported by OLSRv2 (that a 1003 router only advertises its MPR selectors in TC messages), routing MPR 1004 selection must result in the property that there are shortest routes 1005 with all intermediate routers being routing MPRs. 1007 This appendix uses the following terminology and assumptions: 1009 o The network is a graph of nodes connected by arcs, where nodes 1010 correspond to routers with willingness not equal to WILL_NEVER 1011 (except possibly at the ends of routes). An arc corresponds to 1012 the set of symmetric links connecting those routers; the OLSRv2 1013 interfaces used by those links are not relevant. 1015 o Each arc has a metric in each direction, being the minimum of the 1016 corresponding link metrics in that direction, i.e., the 1017 corresponding neighbor metric. This metric must be positive. 1019 o A sequence of arcs joining two nodes is referred to as a path. 1021 o Node A is an MPR of node B, if corresponding router A is a routing 1022 MPR of router B. 1024 The required property (of using shortest routes with reduced 1025 topology) is equivalent to that for any pair of distinct nodes X and 1026 Z there is a shortest path from X to Z, X - Y1 - Y2 - ... - Ym - Z 1027 such that Y1 is an MPR of Y2, ... Ym is an MPR of Z. Call such a 1028 path a routable path, and call this property the routable path 1029 property. 1031 The required definition for a node X selecting MPRs is that for each 1032 distinct node Z from which there is a two arc path, there is a 1033 shorter, or equally short, path which is either Z - Y - X where Y is 1034 an MPR of X, or is the one arc path Z - X. Note that the existence of 1035 locally known, shorter, but more than two arc paths, which can be 1036 used to reduce the numbers of MPRs, is not considered here. (Such 1037 reductions are only when the remaining MPRs can be seen to retain all 1038 necessary shortest paths, and therefore retains the required 1039 property.) 1041 Although this appendix is concerned with paths with minimum total 1042 metric, not number of arcs (hop count), it proceeds by induction on 1043 the number of arcs in a path. Although it considers minimum metric 1044 routes with a bounded number of arcs, it then allows that number of 1045 arcs to increase so that overall minimum metric paths, regardless of 1046 the number of arcs, are considered. 1048 Specifically, the routable path property is a corollary of the 1049 property that for all positive integers n, and all distinct nodes X 1050 and Z, if there is any path from X to Z of n arcs or fewer, then 1051 there is a shortest path, from among those of n arcs or fewer, that 1052 is a routable path. This may be called the n-arc routable path 1053 property. 1055 The n-arc routable path property is trivial for n = 1, and directly 1056 follows from the definition of the MPRs of Z for n = 2. 1058 Proceeding by induction, assuming the n-arc routable path property is 1059 true for n = k, consider the case that n = k+1. 1061 Suppose that X - V1 - V2 - ... - Vk - Z is a shortest k+1 arc path 1062 from X to Z. We construct a path which has no more than k+1 arcs, has 1063 the same or shorter length (hence has the same, shortest, length 1064 considering only paths of up to k+1 arcs, by assumption) and is a 1065 routable path. 1067 First consider whether Vk is an MPR of Z. If it is not then consider 1068 the two arc path Vk-1 - Vk - Z. This can be replaced either by a one 1069 arc path Vk-1 - Z or by a two arc path Vk-1 - Wk - Z where Wk is an 1070 MPR of Z, such that the metric from Vk-1 to Z by the replacement path 1071 is no longer. In the former case (replacement one arc path) this now 1072 produces a path of length k, and the previous inductive step may be 1073 applied. In the latter case we have replaced Vk by Wk, where Wk is 1074 an MPR of Z. Thus we need only consider the case that Vk is an MPR of 1075 Z. 1077 We now apply the previous inductive step to the path X - V1 - ... - 1078 Vk-1 - Vk, replacing it by an equal length path X - W1 - ... Wm-1 - 1079 Vk, where m <= k, where this path is a routable path. Then because 1080 Vk is an MPR of Z, the path X - W1 - ... - Wm-1 - Vk - Z is a 1081 routable path, and demonstrates the n-arc routable path property for 1082 n = k+1. 1084 This thus shows that for any distinct nodes X and Z, there is a 1085 routable path using the MPR-reduced topology from X to Z, i.e., that 1086 OLSRv2 finds minimum length paths (minimum total metric routes). 1088 Authors' Addresses 1090 Christopher Dearlove 1091 BAE Systems Advanced Technology Centre 1092 West Hanningfield Road 1093 Great Baddow, Chelmsford 1094 United Kingdom 1096 Phone: +44 1245 242194 1097 EMail: chris.dearlove@baesystems.com 1098 URI: http://www.baesystems.com/ 1100 Thomas Heide Clausen 1101 LIX, Ecole Polytechnique 1102 91128 Palaiseau Cedex 1103 France 1105 Phone: +33 6 6058 9349 1106 EMail: T.Clausen@computer.org 1107 URI: http://www.thomasclausen.org/ 1109 Philippe Jacquet 1110 Alcatel-Lucent Bell Labs 1112 Phone: +33 6 7337 1880 1113 EMail: philippe.jacquet@alcatel-lucent.com