idnits 2.17.1 draft-ietf-manet-olsrv2-metrics-rationale-00.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 (August 1, 2012) is 4285 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-19) exists of draft-ietf-manet-olsrv2-15 Summary: 0 errors (**), 0 flaws (~~), 3 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: February 2, 2013 LIX, Ecole Polytechnique, France 6 P. Jacquet 7 Alcatel-Lucent Bell Labs 8 August 1, 2012 10 Link Metrics for the Mobile Ad Hoc Network (MANET) Routing Protocol 11 OLSRv2 - Rationale 12 draft-ietf-manet-olsrv2-metrics-rationale-00 14 Abstract 16 This document describes the rationale for and design considerations 17 behind how link metrics are included in OLSRv2, in order to allow 18 routing by other than minimum hop count routes. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on February 2, 2013. 37 Copyright Notice 39 Copyright (c) 2012 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 This document may contain material from IETF Documents or IETF 53 Contributions published or made publicly available before November 54 10, 2008. The person(s) controlling the copyright in some of this 55 material may not have granted the IETF Trust the right to allow 56 modifications of such material outside the IETF Standards Process. 57 Without obtaining an adequate license from the person(s) controlling 58 the copyright in such materials, this document may not be modified 59 outside the IETF Standards Process, and derivative works of it may 60 not be created outside the IETF Standards Process, except to format 61 it for publication as an RFC or to translate it into languages other 62 than English. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 68 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 6 69 4. Motivational Scenarios . . . . . . . . . . . . . . . . . . . . 7 70 5. Link Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 9 71 5.1. Link Metric Properties . . . . . . . . . . . . . . . . . . 9 72 5.2. Link Metric Types . . . . . . . . . . . . . . . . . . . . 10 73 5.3. Directional Link Metrics . . . . . . . . . . . . . . . . . 11 74 5.4. Reporting Link and Neighbor Metrics . . . . . . . . . . . 12 75 5.5. Defining Incoming Link Metrics . . . . . . . . . . . . . . 13 76 5.6. Link Metric Values . . . . . . . . . . . . . . . . . . . . 14 77 6. MPRs with Link Metrics . . . . . . . . . . . . . . . . . . . . 16 78 6.1. Flooding MPRs . . . . . . . . . . . . . . . . . . . . . . 16 79 6.2. Routing MPRs . . . . . . . . . . . . . . . . . . . . . . . 18 80 6.3. Relationship Between MPR Sets . . . . . . . . . . . . . . 21 81 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 82 8. Security Considerations . . . . . . . . . . . . . . . . . . . 24 83 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 84 10. Informative References . . . . . . . . . . . . . . . . . . . . 26 85 Appendix A. MPR Routing Property . . . . . . . . . . . . . . . . 27 87 1. Introduction 89 The Optimized Link State Routing Protocol version 1 (OLSRv1) 90 [RFC3626] is a proactive routing protocol for Mobile Ad hoc NETworks 91 (MANETs) [RFC2501]. OLSRv1 finds shortest, defined as minimum number 92 of hops, routes from a router to all possible destinations. 94 Using only minimum hop routes may result in what are, in practice, 95 inferior routes. Some examples are given in Section 4. Thus, one of 96 the distinguishing features of the Optimized Link State Routing 97 Protocol version 2 (OLSRv2) [OLSRv2] is the introduction of the 98 ability to select routes using link metrics other than the number of 99 hops. 101 OLSRv2 essentially first determines local link metrics from 1-hop 102 neighbors, these being defined by a process outside OLSRv2, then 103 distributes required link metric values in HELLO and TC messages, and 104 then finally forms routes with minimum total link metric. Using a 105 definition of route metric other than number of hops is a natural 106 extension that is commonly used in link state protocols. 108 Use of the extensible message format [RFC5444] by OLSRv2 has allowed 109 the addition, by OLSRv2, of link metric information to the HELLO 110 messages defined in the MANET NeighborHood Discovery Protocol (NHDP) 111 [RFC6130] as well as inclusion in the Topology Control (TC) messages 112 defined in [OLSRv2]. 114 A metric-based route selection processes for OLSRv2 could have been 115 handled as an extension to OLSRv2. However in this case, legacy 116 OLSRv2 routers, which would not recognize any link metric 117 information, would still attempt to use minimum hop-count routes. 118 This would mean that, in effect, routers differed over their 119 valuation of links and routes. This would have led to the 120 fundamental routing problem of "looping". Thus if metric-based route 121 selection were to have been considered only as an extension to 122 OLSRv2, then routers which did, and routers which did not, implement 123 the extension would not have been able to interoperate. This would 124 have been a significant limitation of such an extension. Link 125 metrics were therefore included as standard in OLSRv2. 127 This document discusses the motivation and design rationale behind 128 how link metrics were included in OLSRv2. The principal issues 129 involved when including link metrics in OLSRv2 were: 131 o Assigning metrics to links involved considering separate metrics 132 for the two directions of a link, with the receiving router 133 determining the metric from transmitter to receiver. A metric 134 used by OLSRv2 may be either of: 136 * A link metric, the metric of a specific link from an OLSRv2 137 interface of the transmitting router to an OLSRv2 interface of 138 the receiving router. 140 * A neighbor metric, the minimum of the link metrics between two 141 OLSRv2 routers, in the indicated direction. 143 These metrics are necessarily the same when these routers each 144 have a single OLSRv2 interface, but may differ when either has 145 more. HELLO messages may include both link metrics and neighbor 146 metrics. TC messages include only neighbor metrics. 148 o Metrics as used in OLSRv2 were defined to be dimensionless and 149 additive. The assignment of metrics, including their relationship 150 to real parameters such as bandwidth, loss rate and delay, is 151 outside the scope of OLSRv2, which simply uses these metrics in a 152 consistent manner. However by use of a registry of metric types 153 (employing extended types of a single address block TLV type), 154 routers can use only metrics of the physical type that they are 155 configured to use. 157 o The separation of the two functions performed by MPRs in OLSRv1, 158 optimized flooding and reduced topology advertisement for routing, 159 into separate sets of MPRs in OLSRv2 [OLSRv2], denoted "flooding 160 MPRs" and "routing MPRs". Flooding MPRs can be calculated as in 161 [RFC3626], but the use of link metrics in OLSRv2 can improve the 162 MPR selection. Routing MPRs need a metric-aware selection 163 algorithm. The selection of routing MPRs guarantees the use of 164 minimum distance routes using the chosen metric, while using only 165 symmetric 2-hop neighborhood information from HELLO messages and 166 routing MPR selector information from TC messages. 168 o The protocol Information Bases defined in OLSRv2 include required 169 metric values. This has included additions to the protocol 170 Information Bases defined in NHDP [RFC6130] when used by OLSRv2. 172 2. Terminology 174 All terms introduced in [RFC5444], including "message" and "TLV", are 175 to be interpreted as described there. 177 All terms introduced in [RFC6130], including "MANET Interface", 178 "HELLO message", "heard", "link", symmetric link", "1-hop neighbor", 179 "symmetric 1-hop neighbor", "2-hop neighbor", "symmetric 2-hop 180 neighbor", and "symmetric 2-hop neighborhood", are to be interpreted 181 as described there. 183 All terms introduced in [OLSRv2], including "router", "OLSRv2 184 interface", "willingness", "MultiPoint Relay (MPR)", "MPR selector", 185 and "MPR flooding" are to be interpreted as described there. 187 3. Applicability 189 The objective of this document is to retain the design considerations 190 behind how link metrics were included in [OLSRv2]. The document does 191 not prescribe any behavior, but explains some aspects of the 192 operation of OLSRv2. 194 4. Motivational Scenarios 196 The basic situation that suggests the desirability of use of routes 197 other than minimum hop routes is shown in Figure 1. 199 A ----- X ----- B 200 \ / 201 \ / 202 Y ------- Z 204 Figure 1 206 The minimum hop route from A to B is via X. However if the links A to 207 X and X to B are poor (e.g., having low bandwidth or being 208 unreliable) but the links A to Y, Y to Z and Z to B are better (e.g., 209 having reliable high bandwidth) then the route A to B via Y and Z may 210 be preferred to that via X. 212 There are other situations where, even if the avoidance of some links 213 do not show immediately obvious benefits to users, their use should 214 be discouraged. Consider a network with many short range links, and 215 a few long range links. Use of minimum hop routes will immediately 216 lead to heavy use of the long range links. This will be particularly 217 undesirable if those links achieve their longer range through reduced 218 bandwidth, or through being less reliable. However, even if the long 219 range links have the same characteristics as the short range links, 220 it may be better to reserve usage of the long range links for when 221 this usage is particularly valuable - for example when the use of one 222 long range link saves several short range links, rather than the 223 single link saving that is all that is needed for a minimum hop 224 route. 226 A related case is that of a privileged relay. An example is an 227 aerial router in an otherwise ground based network. The aerial 228 router may have a link to many, or even all, other routers. That 229 would lead to all routers attempting to send all their traffic (other 230 than to symmetric 1-hop neighbors and some symmetric 2-hop neighbors) 231 via the aerial router. It may however be important to reserve that 232 capacity for cases where the aerial router is actually essential, 233 such as if the ground based portion of the network is not connected. 235 Other cases may involve attempts to avoid areas of congestion, to 236 route around insecure routers (by preference, but prepared to use 237 them if there is no other alternative) and routers attempting to 238 discourage their use as relays due to, for example, limited battery 239 power. OLSRv2 does have another mechanism to aid in this, a router's 240 willingness to act as an MPR. However there are cases where that 241 cannot help, but where use of non-minimum hop routes could. 243 Similarly note that OLSRv2's optional use of link quality (through 244 its use of [RFC6130]) is not a solution to these problems. Use of 245 link quality as specified in [RFC6130] allows a router to decline to 246 use a link, not only on its own, but on all routers' behalf. It does 247 not, for example, allow the use of a link otherwise determined to be 248 too low quality to be generally useful, as part of a route where no 249 better links exist. These mechanisms (link quality and link metrics) 250 solve distinctly different problems. 252 It should also be noted that the loop-free property of OLSRv2 applies 253 strictly only in the static state. When the network topology is 254 changing, and with possibly lossy messages, it is possible for 255 transient loops to form. However with update rates appropriate to 256 the rate of topology change, such loops will be sufficiently rare. 257 Changing link metrics is a form of network topology change, and 258 should be limited to a rate slower than the message information 259 update rate (defined by the parameters HELLO_INTERVAL, 260 HELLO_MIN_INTERVAL, REFRESH_INTERVAL, TC_INTERVAL and 261 TC_MIN_INTERVAL). 263 5. Link Metrics 265 This section describes the required and selected properties of the 266 link metrics used in OLSRv2, followed by implementation details 267 achieving those properties. 269 5.1. Link Metric Properties 271 Link metrics in OLSRv2 are: 273 o Dimensionless. While they may, directly or indirectly, correspond 274 to specific physical information (such as delay, loss rate or 275 bandwidth), this knowledge is not used by OLSRv2. Instead, 276 generating the metric value is the responsibility of a mechanism 277 external to OLSRv2. 279 o Additive, so that the metric of a route is the sum of the metrics 280 of the links forming that route. Note that this requires a metric 281 where a low value of a link metric indicates a "good" link and a 282 high value of a link metric indicates a "bad" link, where the 283 former will be preferred to the latter. 285 o Directional, the metric from router A to router B need not be the 286 same as the metric from router B to router A, even when using the 287 same OLSRv2 interfaces. At router A, a link metric from router B 288 to router A is referred to as an incoming link metric, while a 289 link metric from router A to router B is referred to as an 290 outgoing link metric. (These are, of course, reversed at router 291 B.) 293 o Specific to a pair of OLSRv2 interfaces, so that if there is more 294 than one link from router A to router B, each has its own link 295 metric in that direction. There is also be an overall metric, a 296 "neighbor metric", from router A to router B (its 1-hop neighbor). 297 This is the minimum value of the link metrics from router A to 298 router B, considering symmetric links only; it is undefined if 299 there are no such symmetric links. A neighbor metric from one 300 router to another is always equal to a link metric in the same 301 direction between OLSRv2 interfaces of those routers. When 302 referring to a specific OLSRv2 interface (for example in a Link 303 Tuple or a HELLO message sent on that OLSRv2 interface) a link 304 metric always refers to a link on that OLSRv2 interface, to or 305 from the indicated 1-hop neighbor OLSRv2 interface, while a 306 neighbor metric may be equal to a link metric to and/or from 307 another OLSRv2 interface. 309 5.2. Link Metric Types 311 There are various physical characteristics that may be used to define 312 a link metric. Some examples, which also illustrate some 313 characteristics of metrics that result, are: 315 o Delay is a straightforward metric, as it is naturally additive, 316 the delay of a multi-link route is the sum of the delays of the 317 links. (This does not directly take into account delays due to 318 routers, rather than links, but these can be divided among 319 incoming and outgoing links.) However, given a limited range of 320 link metric value, more than one type of delay metric may be 321 required, representing different ranges of delay value. 323 o Probability of loss on a link is, as long as probabilities of loss 324 are small and independent, approximately additive. (A slightly 325 more accurate approach is using a negatively scaled logarithm of 326 the probability of not losing a packet.) If losses are not 327 independent then this will be pessimistic. Again, more than one 328 range of values (or more than one scaling of the logarithms) may 329 be needed. 331 o Bandwidth is not additive, it even has the wrong characteristic of 332 being good when high, bad when low; thus a mapping that inverts 333 its ordering must be applied. Such a mapping can, at best, only 334 produce a metric that it is acceptable to treat as additive. 335 Consider, for example, a preference for a route that maximizes the 336 minimum bandwidth link on the route, and then prefers a route with 337 the fewest links of each bandwidth from the lowest. If links may 338 be of three discrete bandwidths, "high", "medium" and low", then 339 this preference can be achieved, on the assumption that no route 340 will have more than 10 links, with metric values of 1, 10 and 100 341 for the three bandwidths. If routes can have more than 10 links, 342 the range of metrics must be increased; this indicates a 343 preference for a wide "dynamic range" of link metric values. 344 Depending on the ratios of the numerical values of the three 345 bandwidths, the same effect may be achieved by using a scaling of 346 an inverse power of the numerical values of the bandwidths. For 347 example if the three bandwidths were 2, 5 and 10 Mbit/s, then a 348 possible mapping would be the fourth power of 10 Mbit/s divided by 349 the bandwidth, giving metric values of 625, 16 and 1 (good for up 350 to 16 links in a route). This mapping can be extended to a system 351 with more bandwidth values, for example giving a 4 Mbit/s 352 bandwidth a metric value of about 39. This may lose the 353 capability to produce an absolutely maximum minimum bandwidth 354 route, but will usually produce either that, or something close 355 (and at times maybe better, is a route of three 5 Mbit/s links 356 really better than one of a single 4 Mbit/s link?) Specific 357 metrics will need to define the mapping (e.g., a power and 358 bandwidth scaling). 360 There are also many other possible metrics, including physical layer 361 information (such as signal to noise ratio, and error control 362 statistics) and information such as packet queuing statistics. 364 In a well-designed network, all routers will use the same physical 365 metric type. It will not produce good routes if, for example, some 366 link metrics are based on bandwidth and some on path loss (except to 367 the extent that these may be correlated). How to achieve this is an 368 administrative matter, outside the scope of OLSRv2. In fact even the 369 actual physical meanings of the metrics is outside the scope of 370 OLSRv2. This is because new metrics may be added in the future, for 371 example as bandwidths increase, and may be based on new, possibly 372 non-physical, considerations, for example financial cost. Each such 373 type will have a metric type number. Initially a single link metric 374 type zero is defined as indicating a dimensionless metric with no 375 predefined physical meaning. 377 An OLSRv2 router is instructed which single link metric type to use 378 and recognize, without knowing whether it represents delay, 379 probability of loss, bandwidth, cost or any other quantity. This 380 recognized link metric type number is a router parameter, and subject 381 to change in case of reconfiguration, or possibly the use of a 382 protocol (outside the scope of OLSRv2) permitting a process of link 383 metric type agreement between routers. 385 The use of link metric type numbers also suggests the possibility of 386 use of multiple link metric types and multiple network topologies. 387 This is a possible future extension to OLSRv2. To allow for that 388 future possibility, the sending of more than one metric, of different 389 physical types, which should otherwise not be done for reasons of 390 efficiency, is not prohibited, but types other than that configured 391 will be ignored. 393 The following three sections assume a chosen single link metric type, 394 of unspecified physical nature. 396 5.3. Directional Link Metrics 398 OLSRv2 uses only "symmetric" (bidirectional) links, which may carry 399 traffic in either direction. A key decision was whether these links 400 should each be assigned a single metric, used in both directions, or 401 a metric in each direction, noting that: 403 o Links can have different characteristics in each direction, use of 404 directional link metrics recognizes this. 406 o In many (possibly most) cases, the two ends of a link will 407 naturally form different views as to what the link metric should 408 be. To use a single link metric requires a coordination between 409 the two that can be avoided if using directional metrics. Note 410 that if using a single metric, it would be essential that the two 411 ends agree as to its value, otherwise it is possible for looping 412 to occur. This problem does not occur for directional metrics. 414 Based on these considerations, directional metrics are used in 415 OLSRv2. Each router must thus be responsible for defining the metric 416 in one direction only. This could have been in either direction, 417 i.e., that a router is responsible for either incoming or outgoing 418 link metrics, as long as the choice is universal. The former 419 (incoming) case is used in OLSRv2 because, in general, receiving 420 routers have more information available to determine link metrics 421 (for example received signal strength, interference levels, and error 422 control coding statistics). 424 Note that, using directional metrics, if router A defines the metric 425 of the link from router B to router A, then router B must use router 426 A's definition of that metric on that link in that direction. 427 (Router B could, if appropriate, use a bad mismatch between 428 directional metrics as a reason to discontinue use of this link, 429 using the link quality mechanism in [RFC6130].) 431 5.4. Reporting Link and Neighbor Metrics 433 Links, and hence link metrics, are reported in HELLO messages. A 434 router must report incoming link metrics in its HELLO messages in 435 order that these are each available at the other end of the link. 436 This means that, for a symmetric link, both ends of the link will 437 know both of the incoming and outgoing link metrics. 439 As well as advertising incoming link metrics, HELLO messages also 440 advertise incoming neighbor metrics. These are used for routing MPR 441 selection (see Section 6.2), which requires use of the lowest metric 442 link between two routers when more than one link exists. This 443 neighbor metric may be using another OLSRv2 interface, and hence the 444 link metric alone is insufficient. 446 Metrics are also reported in TC messages. It can be shown that these 447 need to be outgoing metrics: 449 o Router A must be responsible for advertising a metric from router 450 A to router B in TC messages. This can be seen by considering a 451 route connecting single OLSRv2 interface routers P to Q to R to S. 452 Router P receives its only information about the link from R to S 453 in the TC messages transmitted by router R, which is an MPR of 454 router S (assuming that only MPR selectors are reported in TC 455 messages). Router S may not even transmit TC messages (if no 456 routers have selected it as an MPR and it has no attached networks 457 to report). So any information about the metric of the link from 458 R to S must also be included in the TC messages sent by router R, 459 hence router R is responsible for reporting the metric for the 460 link from R to S. 462 o In a more general case, where there may be more than one link from 463 R to S, the TC message must, in order that minimum metric routes 464 can be constructed (e.g., by router P) report the minimum of these 465 outgoing link metrics, i.e., the outgoing neighbor metric from R 466 to S. 468 In this example, router P also receives information about the 469 existence of a link between Q and R in the HELLO messages sent by 470 router Q. Without the use of metrics, this link may be used by OLSRv2 471 for two hop routing to router R using just HELLO messages sent by 472 router Q. For this property (which accelerates local route formation) 473 to be retained (from OLSRv1) router P must receive the metric from Q 474 to R in HELLO messages sent by router Q. This indicates that router Q 475 must be responsible for reporting the metric for the outgoing link 476 from Q to R. This is in addition to the incoming link metric 477 information that a HELLO message must report. Again, in general, 478 this must be the outgoing neighbor metric, rather than the outgoing 479 link metric. 481 In addition, Section 6.1 offers an additional reason for reporting 482 outgoing neighbor metrics in HELLO messages, without which metrics 483 can properly affect only routing, not flooding. 485 Note that there is no need to report an outgoing link metric in a 486 HELLO message. The corresponding 1-hop neighbor knows that value, it 487 specified it, and for 2-hop neighborhood use neighbor metrics are 488 required (as these will, in general, not use the same OLSRv2 489 interface). 491 5.5. Defining Incoming Link Metrics 493 When a router reports a 1-hop neighbor in a HELLO message it may do 494 so for the first time with link status HEARD. The receiving router 495 will then immediately consider the link to be symmetric and thus will 496 use it. 498 As the router is responsible for defining and reporting incoming link 499 metrics, it must evaluate that metric, and attach that link metric to 500 the appropriate address (which will have link status HEARD) in the 501 next HELLO message reporting that address on that OLSRv2 interface. 502 There will, at this time, be no outgoing link metric available to 503 report. 505 Thus a router must be able to immediately decide on an incoming link 506 metric once it has heard a 1-hop neighbor on an OLSRv2 interface for 507 the first time. This is because, on receiving a HELLO message from 508 this router, that 1-hop neighbor will (unless link quality indicates 509 otherwise) immediately consider the link to be symmetric and use it. 510 It may, depending on the physical nature of the link metric, be too 511 early for an ideal decision as to that metric, however a choice must 512 be made. The metric value may later be refined based on further 513 observation of HELLO messages, other message transmissions between 514 the routers, or other observations of the environment. It will 515 probably be best to over-estimate the metric if initially uncertain 516 as to its value, to discourage, rather than over-encourage, its use. 517 If no information other than the receipt of the HELLO message is 518 available, then a conservative maximum link metric value, in [OLSRv2] 519 denoted MAXIMUM_METRIC, should be used. 521 5.6. Link Metric Values 523 Link metric values are recorded in LINK_METRIC TLVs, defined in 524 [OLSRv2], using a compressed representation that occupies 12 bits. 525 The use of 12 bits is convenient because, when combined with 4 flag 526 bits of additional information, described below, this produced a 2 527 octet value field. However the use of 12 bits was a result from a 528 design to use a modified exponent/mantissa form with the following 529 characteristics: 531 o The values represented are to be positive integers starting 1, 2, 532 ... 534 o The maximum value represented should be close to, but less than 535 2^24 (^ denotes exponentiation in this section). This is so that 536 with a route limited to no more than 255 hops, the maximum route 537 metric is less than 2^32, i.e., can be stored in 32 bits. (The 538 link metric value can be stored in 24 bits.) 540 A representation, modified from an exponent/mantissa form with e bits 541 of exponent and m bits of mantissa, and which has the first of these 542 properties is one that starts at 1, then is incremented by 1 up to 543 2^m, then has a further 2^m increments by 2, then a further 2^m 544 increments by 4, and so on for 2^e sets of increments. 546 The position in the increment sequence, from 0 to 2^m-1, is 547 considered as a form of mantissa, and denoted b. The increment 548 sequence number, from 0 to 2^e-1, is considered as a form of 549 exponent, and denoted a. 551 The value represented by (a,b) can then be shown to be equal to (2^m+ 552 b+1)2^a-2^m. To verify this, note that: 554 o With fixed a, the difference between two values with consecutive 555 values of b is 2^a, as expected. 557 o The value represented by (a,2^m-1) is (2^m+2^m)2^a-2^m. The value 558 represented by (a+1,0) is (2^m+1)(2^(a+1))-2^m. The difference 559 between these two values is 2^(a+1), as expected. 561 The maximum represented value has a = 2^e-1 and b = 2^m-1, and is 562 (2^m+2^m)(2^(2^e-1))-2^m = 2^(2^e+m)-2^m. This is slightly less than 563 2^(2^e+m). The required 24 bit limit can be achieved if 2^e+m = 24. 564 An appropriate pair of values to achieve this is e = 4, m = 8. 566 As noted above, the 12 bit representation shares two octets with 4 567 flag bits. Putting the flag bits first, it is then natural to put 568 the exponent bits in the last four bits of the first octet, and to 569 put the mantissa bits in the second octet. The 12 consecutive bits, 570 using normal network octet ordering (high first) then represent 571 256a+b. Note that the ordering of these 12 bit representation values 572 is the same as the ordering of the 24 bit metric values. In other 573 words two 12 bit metrics fields can be compared for equality/ordering 574 as if they were unsigned integers. 576 The four flag bits each represent one kind of metric, defined by its 577 direction (incoming or outgoing) and whether the metric is a link 578 metric or a neighbor metric. As indicated by the flag bits set, a 579 metric value may be of any combination of these four kinds of metric. 581 6. MPRs with Link Metrics 583 MPRs are used for two purposes in OLSRv2. In both cases it is MPR 584 selectors that are actually used, MPR selectors being determined from 585 MPRs advertised in HELLO messages. 587 o Optimized Flooding. This uses the MPR selector status of 588 symmetric 1-hop neighbor routers from which messages are received 589 in order to determine if these messages are to be forwarded. MPR 590 selector status is recorded in the Neighbor Set (defined in 591 [RFC6130] and extended in [OLSRv2]), and determined from received 592 HELLO messages. 594 o Routing. Non-local link information is based on information 595 recorded in this router's Topology Information Base. That 596 information is based on received TC messages. The neighbor 597 information in these TC messages consists of addresses of the 598 originating router's advertised (1-hop) neighbors, as recorded in 599 that router's Neighbor Set (defined in [RFC6130] and extended in 600 [OLSRv2]). These advertised neighbors include all of the MPR 601 selectors of the originating router. 603 Metrics interact with these two uses of MPRs differently, as 604 described in the following two sections, and which leads to the 605 requirement for two separate sets of MPRs for these two uses when 606 using metrics. The relationship between these two sets of MPRs is 607 considered in Section 6.3. 609 6.1. Flooding MPRs 611 MPR selection for flooding can ignore metrics. Selection using any 612 algorithm that ignores metrics, including any allowed by [OLSRv2], 613 will produce a flooding solution that works. 615 However, that does not mean that metrics cannot be usefully 616 considered in selecting such "flooding MPRs". Consider the network 617 in Figure 2, where numbers are metrics of links in the direction away 618 from router A, towards router D. 620 3 621 A ----- B 622 | | 623 1 | | 1 624 | | 625 C ----- D 626 4 628 Figure 2 630 Which is the better flooding MPR selection by router A: B or C? If 631 the metric represents probability of message loss, then clearly 632 choosing B maximizes the probability of a message sent by A reaching 633 D. This is despite that C has a lower metric in its connection to A 634 than B does. (Similar arguments about a preference for B can be made 635 if, for example, the metric represents bandwidth or delay rather than 636 probability of loss.) 638 However, neither should only the second hop be considered. If this 639 example is modified to that in Figure 3, where the numbers still are 640 metrics of links in the direction away from router A, towards router 641 D: 643 3 644 A ----- B 645 | | 646 1 | | 3 647 | | 648 C ----- D 649 4 651 Figure 3 653 then it is possible that, when A is selecting flooding MPRs, 654 selecting C is preferable to selecting B. If the metrics represent 655 scaled values of delay, or the probability of loss, then selecting C 656 is clearly better. This indicates that the sum of metrics is an 657 appropriate measure to use to choose between B and C. 659 However, this is a particularly simple example. Usually it is not a 660 simple choice between two routers as a flooding MPR, each only adding 661 one router coverage. A more general process, when considering which 662 router to next add as a flooding MPR, should incorporate the metric 663 to that router, and the metric from that router to each symmetric 664 2-hop neighbor, as well as the number of newly covered symmetric 665 2-hop neighbors as well as the other factors used in the example 666 algorithm in [OLSRv2]. 668 A candidate algorithm for flooding MPR selection is described in 669 [OLSRv2]. However, note that in [OLSRv2] (as in [RFC3626]), each 670 router can make its own independent choice of flooding MPRs, and 671 flooding MPR selection algorithms, and still interoperate. 673 Also note that the references above to the direction of the metrics 674 is correct: for flooding, directional metrics outward from a router 675 are appropriate, i.e., metrics in the direction of the flooding. 676 This is an additional reason for including outward metrics in HELLO 677 messages, as otherwise a metric-aware MPR selection for flooding is 678 not possible. The second hop metrics are outgoing neighbor metrics 679 because the OLSRv2 interface used for a second hop transmission may 680 not be the same as that used for the first hop reception. 682 6.2. Routing MPRs 684 The essential detail of the MPR selection specification in [OLSRv2] 685 is that a router must, per OLSRv2 interface, select a set of MPRs 686 such that there is a two hop route from each symmetric 2-hop neighbor 687 of the selecting router to the selecting router, with the 688 intermediate router on each such route being an MPR of the selecting 689 router. 691 It is sufficient, when using an additive link metric rather than a 692 hop count, to require that these "routing MPRs" provide not just a 693 two hop route, but a minimum distance two hop route. In addition, a 694 router is a symmetric 2-hop neighbor even if it is a symmetric 1-hop 695 neighbor, as long as there is a two hop route from it that is shorter 696 than the one hop link from it. (The property that no routes go 697 through routers with willingness WILL_NEVER is retained. Examples 698 below assume that all routers are equally willing, with none having 699 willingness WILL_NEVER.) 701 For example, consider the network in Figure 4. Numbers are metrics 702 of links in the direction towards router A, away from router D. 703 Router A must pick router B as a routing MPR, whereas for minimum hop 704 count routing it could alternatively pick router C. Note that the use 705 of incoming neighbor metrics in this case follows the same reasoning 706 as for the directionality of metrics in TC messages, as described in 707 Section 5.4. 709 2 710 A ----- B 711 | | 712 1 | | 1 713 | | 714 C ----- D 715 3 717 Figure 4 719 In Figure 5, where numbers are metrics of links in the direction 720 towards router A, away from router C, router A must pick router B as 721 a routing MPR, but for minimum hop count routing it would not need to 722 pick any MPRs. 724 1 725 A - B 726 \ | 727 4 \ | 2 728 \| 729 C 731 Figure 5 733 In Figure 6, where numbers are metrics of links in the direction 734 towards router A, away from routers D and E, router A must pick both 735 routers B and C as routing MPRs, but for minimum hop count routing it 736 could pick either. 738 D E 739 |\ /| 740 | \ 3 / | 741 | \ / | 742 1 | \/ | 1 743 | /\ | 744 | / \ | 745 | / 2 \ | 746 |/ \| 747 B C 748 \ | 749 \ / 750 3 \ / 2 751 \ / 752 A 754 Figure 6 756 It is shown in Appendix A that selecting routing MPRs according to 757 this definition, and advertising only such links (plus knowledge of 758 local links from HELLO messages), will result in selection of lowest 759 total metric routes, even if all links (advertised or not) are 760 considered in the definition of a shortest route. 762 However the definition noted above as sufficient for routing MPR 763 selection is not necessary. For example, consider the network in 764 Figure 7, where numbers are metrics of links in the direction towards 765 router A, away from other routers; the metrics from B to C and C to B 766 are both assumed to be 2. 768 1 769 A ----- B 770 \ / 771 4 \ / 2 772 \ / 773 C ----- D ----- E 774 3 5 776 Figure 7 778 Using the above definition, A must pick both B and C as routing MPRs, 779 in order to cover the symmetric 2-hop neighbors C and D, 780 respectively. (C is a symmetric 2-hop neighbor because the route 781 length via B is shorter than the 1-hop link.) 783 However, A only needs to pick B as a routing MPR, because the only 784 reason to pick C as a routing MPR would be so that C can advertise 785 the link to A for routing - to be used by, for example, E. But A 786 knows that no other router should use the link C to A in a shortest 787 route, because routing via B is shorter. So if there is no need to 788 advertise the link from C to A, then there is no reason for A to 789 select C as a routing MPR. 791 This process of "thinning out" the routing MPR selection uses only 792 local information from HELLO messages. Using any minimum distance 793 algorithm, the router identifies shortest routes, whether one, two or 794 more hops, from all routers in its symmetric 2-hop neighborhood. It 795 then selects as MPRs all symmetric 1-hop neighbors that are the last 796 router (before the selecting router itself) on any such route. Where 797 there is more than one shortest distance route from a router, only 798 one such route is required. Alternative routes may be selected so as 799 to minimize the number of last routers - this is the equivalent to 800 the selection of a minimal set of MPRs in the non-metric case. 802 Note that this only removes routing MPRs whose selection can be 803 directly seen to be unnecessary. Consequently if (as is shown in 804 Appendix A) the first approach creates minimum distance routes, then 805 so does this process. 807 The examples in Figure 5 and Figure 6 show that use of link metrics 808 may require a router to select more routing MPRs than when not using 809 metrics, and even require a router to select routing MPRs when 810 without metrics it would not need any routing MPRs. This may result 811 in more, and larger, messages being generated, and forwarded more 812 often. Thus the use of link metrics is not without cost, even 813 excluding the cost of link metric signaling. 815 These examples consider only single OLSRv2 interface routers. 817 However if routers have more than one OLSRv2 interface, then the 818 process is unchanged, other than that if there is more than one known 819 metric between two routers (on different OLSRv2 interfaces), then, 820 considering symmetric links only (as only these are used for routing) 821 the smallest link metric, i.e., the neighbor metric, is used. There 822 is no need to calculate routing MPRs per OLSRv2 interface. That 823 requirement results from the consideration of flooding and the need 824 to avoid certain "race" conditions, which are not relevant to 825 routing, only to flooding. 827 A candidate algorithm for routing MPR selection is described in 828 [OLSRv2]. However, note that in [OLSRv2] (as in [RFC3626]), each 829 router can make its own independent choice of routing MPRs, and 830 routing MPR selection algorithms, and still interoperate. 832 6.3. Relationship Between MPR Sets 834 It would be convenient if the two sets of flooding and routing MPRs 835 were the same. This can be the case if all metrics are equal, but in 836 general, for "good" sets of MPRs they are not. (A reasonable 837 definition of this is that there is no common minimal set of MPRs.) 838 If metrics are asymmetrically valued (the two sets of MPRs use 839 opposite direction metrics), or routers have multiple OLSRv2 840 interfaces (where routing MPRs can ignore this, but flooding MPRs 841 cannot) this is particularly unlikely. However even using a 842 symmetrically valued metric with a single OLSRv2 interface on each 843 router, the ideal sets need not be equal, nor is one always a subset 844 of the other. To show this, consider these examples, where all 845 lettered routers are assumed equally willing to be MPRs, and numbers 846 are bidirectional metrics for links. 848 In Figure 8, A does not require any flooding MPRs. However A must 849 select B as a routing MPR. 851 1 852 A - B 853 \ | 854 4 \ | 2 855 \| 856 C 858 Figure 8 860 In Figure 9, A must select C and D as routing MPRs. However A's 861 minimal set of flooding MPRs is just B. In this example the set of 862 routing MPRs serves as a set of flooding MPRs, but a non-minimal one 863 (although one that might be better, depending on the relative 864 importance of number of MPRs and flooding link metrics). 866 2 867 C --- E 868 / / 869 1 / / 1 870 / 4 / 871 A --- B 872 \ \ 873 1 \ \ 1 874 \ \ 875 D --- F 876 2 878 Figure 9 880 However, this is not always the case. In Figure 10, A's set of 881 routing MPRs must contain B, but need not contain C. A's set of 882 flooding MPRs need not contain B, but must contain C. (In this case, 883 flooding with A selecting B rather than C as a flooding MPR will 884 reach D, but in three hops rather than the minimum two that MPR 885 flooding guarantees.) 887 2 1 888 B - C - D 889 | / 890 1 | / 4 891 |/ 892 A 894 Figure 10 896 7. IANA Considerations 898 This document has no actions for IANA. 900 This section may be removed by the RFC Editor. 902 8. Security Considerations 904 This document does not specify any security considerations. 906 This section may be removed by the RFC Editor. 908 9. Acknowledgements 910 The authors would like to gratefully acknowledge the following people 911 for intense technical discussions, early reviews and comments on the 912 specification and its components (listed alphabetically): Brian 913 Adamson (NRL), Alan Cullen (BAE Systems), Justin Dean (NRL), Stan 914 Ratliff (Cisco), Charles Perkins (Huawei), Henning Rogge (FGAN), and 915 Ulrich Herberg (Fujitsu). 917 10. Informative References 919 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 920 (MANET): Routing Protocol Performance Issues and 921 Evaluation Considerations", RFC 2501, January 1999. 923 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 924 Routing Protocol", RFC 3626, October 2003. 926 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 927 "Generalized MANET Packet/Message Format", RFC 5444, 928 February 2009. 930 [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc 931 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 932 RFC 6130, April 2011. 934 [OLSRv2] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized 935 Link State Routing Protocol version 2", 936 draft-ietf-manet-olsrv2-15.txt (work in progress), 937 May 2012. 939 Appendix A. MPR Routing Property 941 In order that routers can find and use shortest routes in a network 942 while using the minimum reduced topology supported by OLSRv2 (that a 943 router only advertises its MPR selectors in TC messages), routing MPR 944 selection must result in the property that there are shortest routes 945 with all intermediate routers being routing MPRs. 947 This appendix uses the following terminology and assumptions: 949 o The network is a graph of nodes connected by arcs, where nodes 950 correspond to routers with willingness not equal to WILL_NEVER 951 (except possibly at the ends of routes). An arc corresponds to 952 the set of symmetric links connecting those routers; the OLSRv2 953 interfaces used by those links are not relevant. 955 o Each arc has a metric in each direction, being the minimum of the 956 corresponding link metrics in that direction, i.e., the 957 corresponding neighbor metric. This metric must be positive. 959 o A sequence of arcs joining two nodes is referred to as a path. 961 o Node A is an MPR of node B, if corresponding router A is a routing 962 MPR of router B. 964 The required property (of using shortest routes with reduced 965 topology) is equivalent to that for any pair of distinct nodes X and 966 Z there is a shortest path from X to Z, X - Y1 - Y2 - ... - Ym - Z 967 such that Y1 is an MPR of Y2, ... Ym is an MPR of Z. Call such a 968 path a routable path, and call this property the routable path 969 property. 971 The required definition for a node X selecting MPRs is that for each 972 distinct node Z from which there is a two arc path, there is a 973 shorter, or equally short, path which is either Z - Y - X where Y is 974 an MPR of X, or is the one arc path Z - X. Note that the existence of 975 locally known, shorter, but more than two arc paths, which can be 976 used to reduce the numbers of MPRs, is not considered here. (Such 977 reductions are only when the remaining MPRs can be seen to retain all 978 necessary shortest paths, and therefore retains the required 979 property.) 981 Although this appendix is concerned with paths with minimum total 982 metric, not number of arcs (hop count), it proceeds by induction on 983 the number of arcs in a path. Although it considers minimum metric 984 routes with a bounded number of arcs, it then allows that number of 985 arcs to increase so that overall minimum metric paths, regardless of 986 the number of arcs, are considered. 988 Specifically, the routable path property is a corollary of the 989 property that for all positive integers n, and all distinct nodes X 990 and Z, if there is any path from X to Z of n arcs or fewer, then 991 there is a shortest path, from among those of n arcs or fewer, that 992 is a routable path. This may be called the n-arc routable path 993 property. 995 The n-arc routable path property is trivial for n = 1, and directly 996 follows from the definition of the MPRs of Z for n = 2. 998 Proceeding by induction, assuming the n-arc routable path property is 999 true for n = k, consider the case that n = k+1. 1001 Suppose that X - V1 - V2 - ... - Vk - Z is a shortest k+1 arc path 1002 from X to Z. We construct a path which has no more than k+1 arcs, has 1003 the same or shorter length (hence has the same, shortest, length 1004 considering only paths of up to k+1 arcs, by assumption) and is a 1005 routable path. 1007 First consider whether Vk is an MPR of Z. If it is not then consider 1008 the two arc path Vk-1 - Vk - Z. This can be replaced either by a one 1009 arc path Vk-1 - Z or by a two arc path Vk-1 - Wk - Z where Wk is an 1010 MPR of Z, such that the metric from Vk-1 to Z by the replacement path 1011 is no longer. In the former case (replacement one arc path) this now 1012 produces a path of length k, and the previous inductive step may be 1013 applied. In the latter case we have replaced Vk by Wk, where Wk is 1014 an MPR of Z. Thus we need only consider the case that Vk is an MPR of 1015 Z. 1017 We now apply the previous inductive step to the path X - V1 - ... - 1018 Vk-1 - Vk, replacing it by an equal length path X - W1 - ... Wm-1 - 1019 Vk, where m <= k, where this path is a routable path. Then because 1020 Vk is an MPR of Z, the path X - W1 - ... - Wm-1 - Vk - Z is a 1021 routable path, and demonstrates the n-arc routable path property for 1022 n = k+1. 1024 This thus shows that for any distinct nodes X and Z, there is a 1025 routable path using the MPR-reduced topology from X to Z, i.e., that 1026 OLSRv2 finds minimum length paths (minimum total metric routes). 1028 Authors' Addresses 1030 Christopher Dearlove 1031 BAE Systems ATC 1033 Phone: +44 1245 242194 1034 EMail: chris.dearlove@baesystems.com 1035 URI: http://www.baesystems.com/ 1037 Thomas Heide Clausen 1038 LIX, Ecole Polytechnique, France 1040 Phone: +33 6 6058 9349 1041 EMail: T.Clausen@computer.org 1042 URI: http://www.ThomasClausen.org/ 1044 Philippe Jacquet 1045 Alcatel-Lucent Bell Labs 1047 Phone: +33 6 7337 1880 1048 EMail: philippe.jacquet@alcatel-lucent.fr