idnits 2.17.1 draft-ietf-manet-olsrv2-multipath-15.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 date (May 24, 2017) is 2491 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 481 -- Looks like a reference, but probably isn't: '2' on line 481 == Outdated reference: A later version (-26) exists of draft-ietf-6man-segment-routing-header-06 -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Yi 3 Internet-Draft Ecole Polytechnique 4 Intended status: Experimental B. Parrein 5 Expires: November 25, 2017 University of Nantes 6 May 24, 2017 8 Multipath Extension for the Optimized Link State Routing Protocol 9 version 2 (OLSRv2) 10 draft-ietf-manet-olsrv2-multipath-15 12 Abstract 14 This document specifies a multipath extension for the Optimized Link 15 State Routing Protocol version 2 (OLSRv2) to discover multiple 16 disjoint paths for Mobile Ad Hoc Networks (MANETs). Considering the 17 characteristics of MANETs, especially the dynamic network topology, 18 using multiple paths can increase aggregated throughput and improve 19 the reliability by avoiding single route failures. The 20 interoperability with OLSRv2 is retained. 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 25, 2017. 39 Copyright Notice 41 Copyright (c) 2017 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 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 59 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 60 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 61 5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 8 62 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 8 63 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 9 64 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 9 65 6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . . 9 66 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 9 67 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 9 68 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 10 69 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 10 70 7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 10 71 7.2. Multipath Routing Set . . . . . . . . . . . . . . . . . . 10 72 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 11 73 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 11 74 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 12 75 8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 12 76 8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 12 77 8.5. Multipath Calculation . . . . . . . . . . . . . . . . . . 14 78 8.5.1. Requirements of Multipath Calculation . . . . . . . . 14 79 8.5.2. Multipath Dijkstra Algorithm . . . . . . . . . . . . . 15 80 8.6. Multipath Routing Set Updates . . . . . . . . . . . . . . 16 81 8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 17 82 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 17 83 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 18 84 10.1. Multipath extension based on nOLSRv2 . . . . . . . . . . . 19 85 10.2. Multipath extension based on olsrd . . . . . . . . . . . . 19 86 10.3. Multipath extension based on umOLSR . . . . . . . . . . . 19 87 11. Security Considerations . . . . . . . . . . . . . . . . . . . 19 88 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 89 12.1. Message TLV Types . . . . . . . . . . . . . . . . . . . . 21 90 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 91 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 92 14.1. Normative References . . . . . . . . . . . . . . . . . . . 21 93 14.2. Informative References . . . . . . . . . . . . . . . . . . 22 94 Appendix A. Examples of Multipath Dijkstra Algorithm . . . . . . 24 95 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25 97 1. Introduction 99 The Optimized Link State Routing Protocol version 2 (OLSRv2) 100 [RFC7181] is a proactive link state protocol designed for use in 101 mobile ad hoc networks (MANETs). It generates routing messages 102 periodically to create and maintain a Routing Set, which contains 103 routing information to all the possible destinations in the routing 104 domain. For each destination, there exists a unique Routing Tuple, 105 which indicates the next hop to reach the destination. 107 This document specifies an extension of the OLSRv2 protocol 108 [RFC7181], to provide multiple disjoint paths when appropriate for a 109 source-destination pair. Because of the characteristics of MANETs 110 [RFC2501], especially the dynamic topology, having multiple paths is 111 helpful for increasing network throughput, improving forwarding 112 reliability, and load balancing. 114 Multipath OLSRv2 (MP-OLSRv2) specified in this document uses the 115 Multipath Dijkstra algorithm by default to explore multiple disjoint 116 paths from a source router to a destination router based on the 117 topology information obtained through OLSRv2, and to forward the 118 datagrams in a load-balancing manner using source routing. MP-OLSRv2 119 is designed to be interoperable with OLSRv2. 121 1.1. Motivation and Experiments to Be Conducted 123 This document is an experimental extension of OLSRv2 that can 124 increase the data forwarding reliability in dynamic and high-load 125 MANET scenarios by transmitting datagrams over multiple disjoint 126 paths using source routing. This mechanism is used because: 128 o Disjoint paths can avoid single route failures. 130 o Transmitting datagrams through parallel paths can increase 131 aggregated throughput. 133 o Some scenarios may require some routers must (or must not) be 134 used. 136 o Having control of the paths at the source benefits the load 137 balancing and traffic engineering. 139 o An application of this extension is in combination with Forward 140 Error Correction (FEC) coding applied across packets (erasure 141 coding) [WPMC11]. Because the packet drops are normally bursty in 142 a path (for example, due to route failure), erasure coding is less 143 effective in single path routing protocols. By providing multiple 144 disjoint paths, the application of erasure coding with multipath 145 protocol is more resilient to routing failures. 147 While in existing deployments, running code and simulations have 148 proven the interest of multipath extension for OLSRv2 in certain 149 networks, more experiments and experiences are still needed to 150 understand the effects of the protocol specified in this experimental 151 document. The multipath extension for OLSRv2 is expected to be 152 revised documented as a Standard Track document once sufficient 153 operational experience is obtained. Other than general experiences, 154 including the protocol specification and interoperability with base 155 OLSRv2 implementations, experiences in the following aspects are 156 highly appreciated: 158 o Optimal values for the number of multiple paths (NUMBER_OF_PATHS, 159 Section 5) to be used. This depends on the network topology and 160 router density. 162 o Optimal values used in the metric functions. Metric functions are 163 applied to increase the metric of used links and nodes so as to 164 obtain disjoint paths. What kind of disjointness is desired 165 (node-disjoint or link-disjoint) may depend on the layer 2 166 protocol used, and can be achieved by applying different sets of 167 metric functions. 169 o Use of different metric types. This multipath extension can be 170 used with metric types that meet the requirement of OLSRv2, such 171 as [RFC7779]. The metric type used has also impact to the choice 172 of metric functions as indicated in the previous bullet point. 174 o The impact of partial topology information to multipath 175 calculation. OLSRv2 maintains a partial topology information base 176 to reduce protocol overhead. Experience has shown that multiple 177 paths can be obtained even with such partial information, however, 178 depending on the Multi-Point Relay (MPR) selection algorithm used, 179 the disjointness of the multiple paths might be impacted depending 180 on the Multi-Point Relay (MPR) selection algorithm used. 182 o Use of IPv6 loose source routing. In the current specification, 183 only strict source routing is used for IPv6 based on [RFC6554]. 184 In [I-D.ietf-6man-segment-routing-header], the use of the loose 185 source routing is also proposed in IPv6. In scenarios where the 186 length of the source routing header is critical, the loose source 187 routing can be considered. 189 o Optimal choice of "key" routers for loose source routing. In some 190 cases, loose source routing is used to reduce overhead or for 191 interoperability with OLSRv2 routers. Other than the basic rules 192 defined in the following parts of this document, optimal choices 193 of routers to put in the loose source routing header can be 194 further studied. 196 o Different path-selection schedulers. Depending on the application 197 type and transport layer type, either per-flow scheduler or per- 198 datagram scheduler is applied. By default, the traffic load 199 should be equally distributed in multiple paths. In some 200 scenarios, weighted scheduling can be considered: for example, the 201 paths with lower metrics (i.e., higher quality) can transfer more 202 datagrams or flows compared to paths with higher metrics. 204 o The impacts of the delay variation due to multipath routing. 205 [RFC2991] brings out some concerns of multipath routing, 206 especially variable latencies when per-datagram scheduling is 207 applied. Although current experiment results show that multipath 208 routing can reduce the jitter in dynamic scenarios, some transport 209 protocols or applications may be sensitive to the datagram re- 210 ordering. 212 o The disjoint multipath protocol has interesting application with 213 erasure coding, especially for services like video/audio streaming 214 [WPMC11]. The combination of erasure coding mechanisms and this 215 extension is thus encouraged. 217 o Different algorithms to obtain multiple paths, other than the 218 default Multipath Dijkstra algorithm introduced in Section 8.5.2 219 of this specification. 221 o The use of multi-topology information. By using [RFC7722], 222 multiple topologies using different metric types can be obtained. 223 Although there is no work defining how this extension can make use 224 of the multi-topology information base yet, it is encouraged to 225 experiment with the use of multiple metrics for building multiple 226 paths. 228 Comments are solicited and should be addressed to the MANET working 229 group's mailing list at manet@ietf.org and/or the authors." 231 2. Terminology 233 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 234 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 235 "OPTIONAL" in this document are to be interpreted as described in 236 [RFC2119]. 238 This document uses the terminology and notation defined in [RFC5444], 239 [RFC6130], [RFC7181]. Additionally, it defines the following 240 terminology: 242 OLSRv2 Routing Process - A routing process based on [RFC7181], 243 without multipath extension specified in this document. 245 MP-OLSRv2 Routing Process - A multipath routing process based on 246 this specification as an extension to [RFC7181]. 248 SR-OLSRv2 Routing Process - A OLSRv2 Routing Process that supports 249 source routing (SR), or an MP-OLSRv2 Routing Process. 251 3. Applicability Statement 253 As an extension of OLSRv2, this specification is applicable to MANETs 254 for which OLSRv2 is applicable (see [RFC7181]). It can operate on 255 single or multiple interfaces to discover multiple disjoint paths 256 from a source router to a destination router. MP-OLSRv2 is designed 257 for networks with dynamic topology to avoid single route failure. It 258 can also provide higher aggregated throughput and load balancing. 260 In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily 261 replace OLSRv2 completely. The extension can be applied for certain 262 applications that are suitable for multipath routing (mainly video or 263 audio streams), based on information such as a DiffServ codepoint 264 [RFC2474]. 266 Compared to OLSRv2, this extension does not introduce any new message 267 type. A new Message TLV Type is introduced to identify the routers 268 that support forwarding based on source routing header. It is 269 interoperable with OLSRv2 implementations that do not have this 270 extension: as the MP-OLSRv2 uses source routing, in IPv4 networks the 271 interoperability is achieved using loose source routing headers; in 272 IPv6 networks, it is achieved by eliminating routers that do not 273 support IPv6 strict source routing. 275 MP-OLSRv2 supports two different, but interoperable multipath 276 calculation approaches: proactive and reactive. In the proactive 277 calculation, the paths to all the destinations are calculated before 278 needed. In the reactive calculation, only the paths to desired 279 destination(s) are calculated on demand. The proactive approach 280 requires more computational resources than the reactive one. The 281 reactive approach requires the IP forwarding plane to trigger the 282 multipath calculation. 284 MP-OLSRv2 forwards datagrams using the source routing header. As 285 there are multiple paths to each destination, MP-OLSRv2 requires the 286 IP forwarding plane to be able to choose which source route to be put 287 in the source routing header based on the path scheduler defined by 288 MP-OLSRv2. For IPv4 networks, implementation of loose source routing 289 is required following [RFC0791]. For IPv6 networks, implementation 290 of strict source routing is required following the source routing 291 header generation and processing defined in [RFC6554]. 293 4. Protocol Overview and Functioning 295 This specification uses OLSRv2 [RFC7181] to: 297 o Identify all the reachable routers in the network. 299 o Identify a sufficient subset of links in the networks, so that 300 routes can be calculated to all reachable destinations. 302 o Provide a Routing Set containing the shortest routes from this 303 router to all destinations. 305 In addition, the MP-OLSRv2 Routing Process identifies the routers 306 that support source routing by adding a new Message TLV in HELLO and 307 Topology Control (TC) messages. Based on the above information 308 acquired, every MP-OLSRv2 Routing Process is aware of a reduced 309 topology map of the network and the routers supporting source 310 routing. 312 A Multipath Routing Set containing the multipath information is 313 maintained. It may either be proactively calculated or reactively 314 calculated: 316 o In the proactive approach, multiple paths to all possible 317 destinations are calculated and updated based on control message 318 exchange. The routes are thus available before they are actually 319 needed. 321 o In the reactive approach, a multipath algorithm is invoked on 322 demand, i.e., only when there is a datagram to be sent from the 323 source to the destination, and there is no available Routing Tuple 324 in the Multipath Routing Set. This requires the IP forwarding 325 information base to trigger the multipath calculation specified in 326 Section 8.5 when no Multipath Routing Tuple is available. The 327 reactive operation is local to the router and no additional 328 routing control messages exchange is required. When the paths are 329 being calculated, the datagrams SHOULD be buffered unless the 330 router does not have enough memory. 332 Routers in the same network may choose either proactive or reactive 333 multipath calculation independently according to their computation 334 resources. The Multipath Dijkstra algorithm (defined in Section 8.5) 335 is introduced as the default algorithm to generate multiple disjoint 336 paths from a source to a destination, and such information is kept in 337 the Multipath Routing Set. 339 The datagram is forwarded based on source routing. When there is a 340 datagram to be sent to a destination, the source router acquires a 341 path from the Multipath Routing Set. The path information is stored 342 in the datagram header using the source routing header. 344 5. Parameters and Constants 346 In addition to the parameters and constants defined in [RFC7181], 347 this specification uses the parameters and constants described in 348 this section. 350 5.1. Router Parameters 352 NUMBER_OF_PATHS The number of paths desired by the router. 354 MAX_SRC_HOPS The maximum number of hops allowed to be put in the 355 source routing header. A value set zero means there is no 356 limitation on the maximum number of hops. In an IPv6 network, it 357 MUST be set to 0 because [RFC6554] supports only strict source 358 routing. All the intermediate routers MUST be included in the 359 source routing header, which a various number of hops. In an IPv4 360 network, it MUST be strictly less than 11 and greater than 0 due 361 to the length limit of the IPv4 header. 363 CUTOFF_RATIO The ratio that defines the maximum metric of a path 364 compared to the shortest path kept in the OLSRv2 Routing Set. For 365 example, the metric to a destination is R_metric based on the 366 Routing Set. Then the maximum metric allowed for a path is 367 CUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be greater than or 368 equal to 1. Setting the number low makes it less likely that 369 additional paths will be found -- for example, setting it to 1 370 will only consider equal length paths. 372 SR_TC_INTERVAL The maximum time between the transmission of two 373 successive TC messages by an MP-OLSRv2 Routing Process. 375 SR_HOLD_TIME The minimum value in the TLV with Type = VALIDITY_TIME 376 included in TC messages generated based on SR_TC_INTERVAL. 378 6. Packets and Messages 380 This extension employs the routing control messages HELLO and TC 381 (Topology Control) as defined in OLSRv2 [RFC7181] to obtain network 382 topology information. For the datagram to support source routing, a 383 source routing header is added to each datagram routed by this 384 extension. Depending on the IP version used, the source routing 385 header is defined in this section. 387 6.1. HELLO and TC messages 389 HELLO and TC messages used by the MP-OLSRv2 Routing Process use the 390 same format as defined in [RFC7181]. In addition, a new Message TLV 391 type is defined, to identify the originator of the HELLO or TC 392 message that supports source route forwarding. The new Message TLV 393 type is introduced for enabling MP-OLSRv2 as an extension of OLSRv2: 394 only the routers supporting source-route forwarding can be used in 395 the source routing header of a datagram, because adding a router that 396 does not understand the source routing header will cause routing 397 failure. 399 6.1.1. SOURCE_ROUTE TLV 401 SOURCE_ROUTE TLV is a Message TLV signaling that the message is 402 generated by a router that supports source-route forwarding. It can 403 be an MP-OLSRv2 Routing Process, or an OLSRv2 Routing Process that 404 supports source-route forwarding. 406 Every HELLO or TC message generated by a MP-OLSRv2 Routing Process 407 MUST have exactly one SOURCE_ROUTE TLV without value. 409 Every HELLO or TC message generated by an OLSRv2 Routing Process MUST 410 have exactly one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process 411 supports source-route forwarding, and is willing to join the source 412 route generated by other MP-OLSRv2 Routing Processes. The existence 413 of SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing 414 Process, i.e., either it adds SOURCE_ROUTE TLV to all its HELLO/TC 415 messages, or it does not add SOURCE_ROUTE TLV to any HELLO/TC 416 messages. 418 6.2. Datagram 420 6.2.1. Source Routing Header in IPv4 422 In IPv4 [RFC0791] networks, the MP-OLSRv2 Routing Process employs the 423 loose source routing header, as defined in [RFC0791]. It exists as 424 an option header, with option class 0, and option number 3. 426 The source route information is kept in the "route data" field of the 427 loose source route header. 429 6.2.2. Source Routing Header in IPv6 431 In IPv6 [RFC2460] networks, the MP-OLSRv2 Routing Process employs the 432 source routing header as defined in section 3 of [RFC6554], with IPv6 433 Routing Type 3. 435 The source route information is kept in the "Addresses" field of the 436 routing header. 438 7. Information Bases 440 Each MP-OLSRv2 Routing Process maintains the information bases as 441 defined in [RFC7181]. Additionally, a Multipath Information Base is 442 used for this specification. It includes the protocol sets as 443 defined below. 445 7.1. SR-OLSRv2 Router Set 447 The SR-OLSRv2 Router Set records the routers that support source- 448 route forwarding. This includes routers that run the MP-OLSRv2 449 Routing Process or the OLSRv2 Routing Process with source-route 450 forwarding support. The set consists of SR-OLSRv2 Router Tuples: 452 (SR_addr, SR_time) 454 where: 456 SR_addr - is the originator address of the router that supports 457 source-route forwarding; 459 SR_time - is the time until which the SR-OLSRv2 Router Tuple is 460 considered valid. 462 7.2. Multipath Routing Set 464 The Multipath Routing Set records the full path information of 465 different paths to the destination. It consists of Multipath Routing 466 Tuples: 468 (MR_dest_addr, MR_path_set) 470 where: 472 MR_dest_addr - is the network address of the destination, either 473 the network address of an interface of a destination router or the 474 network address of an attached network; 476 MP_path_set - contains the multiple paths to the destination. It 477 consists of a set of Path Tuples. 479 Each Path Tuple is defined as: 481 (PT_metric, PT_address[1], PT_address[2], ..., PT_address[n]) 483 where: 485 PT_metric - is the metric of the path to the destination, measured 486 in LINK_METRIC_TYPE defined in [RFC7181]; 488 PT_address[1, ..., n-1] - are the addresses of intermediate routers 489 to be visited numbered from 1 to n-1, where n is the number of 490 routers in the path, i.e., the hop count. 492 8. Protocol Details 494 This protocol is based on OLSRv2, and extended to discover multiple 495 disjoint paths from a source router to a destination router. It 496 retains the basic routing control packets formats and processing of 497 OLSRv2 to obtain the topology information of the network. The main 498 differences from the OLSRv2 Routing Process are the datagram 499 processing at the source router and datagram forwarding. 501 8.1. HELLO and TC Message Generation 503 HELLO messages are generated according to Section 15.1 of [RFC7181], 504 plus a single message TLV with Type := SOURCE_ROUTE included. 506 TC messages are generated according to Section 16.1 of [RFC7181] plus 507 a single message TLV with Type := SOURCE_ROUTE included. 509 For the routers that do not generate TC messages according to 510 [RFC7181], at least one TC message MUST be generated by an MP-OLSRv2 511 Routing Process during the SR_TC_INTERVAL (Section 5), which MUST be 512 greater than or equal to TC_INTERVAL. Those TC messages MUST NOT 513 carry any advertised neighbor addresses. This serves for those 514 routers to advertise the SOURCE_ROUTE TLV so that the other routers 515 can be aware of the source-route enabled routers so as to be used as 516 destinations of multipath routing. The validity time associated with 517 the VALIDITY_TIME TLV in such TC messages equals SR_HOLD_TIME, which 518 MUST be greater than the SR_TC_INTERVAL. If the TC message carries 519 an optional INTERVAL_TIME TLV, it MUST have a value encoding the 520 SR_TC_INTERVAL. 522 8.2. HELLO and TC Message Processing 524 HELLO and TC messages are processed according to section 15.3 and 525 16.3 of [RFC7181]. 527 In addition to the reasons specified in [RFC7181] for discarding a 528 HELLO message or a TC message on reception, a HELLO or TC message 529 received MUST be discarded if it has more than one Message TLV with 530 Type = SOURCE_ROUTE. 532 For every HELLO or TC message received, if there is a Message TLV 533 with Type := SOURCE_ROUTE, create or update (if the Tuple exists 534 already) the SR-OLSR Router Tuple with 536 o SR_addr := originator address of the HELLO or TC message 538 o SR_time := current_time + validity time of the TC or HELLO message 539 defined in [RFC7181]. 541 8.3. MPR Selection 543 Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs 544 following Section 18 of [RFC7181]. In a mixed network with OLSRv2- 545 only routers, the following considerations apply when calculating 546 MPRs: 548 o MP-OLSRv2 routers SHOULD be preferred as routing MPRs to increase 549 the possibility of finding disjoint paths using MP-OLSRv2 routers. 551 o The number of routing MPRs that run MP-OLSRv2 Routing Process MUST 552 be equal or greater than NUMBER_OF_PATHS if there are enough MP- 553 OLSRv2 symmetric neighbors. Otherwise all the MP-OLSRv2 routers 554 are selected as routing MPRs, expect the routers with willingness 555 WILL_NEVER. 557 8.4. Datagram Processing at the MP-OLSRv2 Originator 559 If datagrams without source routing header need to be forwarded using 560 multiple paths (for example, based on the information of a DiffServ 561 codepoint [RFC2474]), the MP-OLSRv2 Routing Process will try to find 562 the Multipath Routing Tuple where: 564 o MR_dest_addr = destination of the datagram 566 If no matching Multipath Routing Tuple is found and the Multipath 567 Routing Set is maintained proactively, it indicates that there is no 568 multipath route available to the desired destination. The datagram 569 is forwarded following the OLSRv2 Routing Process. 571 If no matching Multipath Routing Tuple is found and the Multipath 572 Routing Set is maintained reactively, the multipath algorithm defined 573 in Section 8.5 is invoked, to calculate the Multipath Routing Tuple 574 to the destination. If the calculation does not return any Multipath 575 Routing Tuple, the following steps are aborted and the datagram is 576 forwarded following the OLSRv2 Routing Process. 578 If a matching Multipath Routing Tuple is obtained, the Path Tuples of 579 the Multipath Routing Tuple are applied to the datagrams using either 580 per-flow scheduling or per-datagram scheduling, depending on the 581 transport layer protocol and the application used. By default, per- 582 flow scheduling is used, especially for the transport protocols that 583 are sensitive to reordering, such as TCP. The path selection 584 decision is made on the first datagram and all subsequent datagrams 585 of the same flow use the same path. If the path is detected broken 586 before the flow is closed, another path with the most similar metric 587 is used. Per-datagram scheduling is recommended if the traffic is 588 insensitive to reordering such as non-reliable transmission of media 589 traffic, or when erasure coding is applied. In such case, each 590 datagram selects its paths independently. 592 By default, the traffic load should be equally distributed in 593 multiple paths. Other path scheduling mechanisms (e.g., assigning 594 more traffic over better paths) are also possible and will not impact 595 the interoperability of different implementations. 597 The addresses in PT_address[1, ..., n-1] of the chosen Path Tuple are 598 thus added to the datagram header as the source routing header. For 599 IPv6 networks, strict source routing is used, thus all the 600 intermediate routers in the path are stored in the source routing 601 header following the format defined in section 3 of [RFC6554] with 602 Routing Type set to 3. 604 For IPv4 networks, loose source routing is used, with the following 605 rules: 607 o Only the addresses that exist in SR-OLSR Router Set can be added 608 to the source routing header. 610 o If the length of the path (n) is greater than MAX_SRC_HOPS 611 (Section 5) or adding the whole path information exceeds the MTU, 612 only the "key" routers in the path are kept. By default, the key 613 routers are uniformly chosen in the path. If further information 614 such as capacity of the routers (e.g., battery life) or the 615 routers' willingness in forwarding data is available, the routers 616 with higher capacity and willingness are preferred. 618 o The routers that are considered not appropriate for forwarding 619 indicated by external policies should be avoided. 621 It is not recommended to fragment the IP packet if the packet with 622 the source routing header would exceed the minimum MTU along the 623 path. Depending on the size of the routing domain, the MTU should be 624 at least 1280 + 40 (for the outer IP header) + 16 * diameter of the 625 network in number of hops (for the source routing header). If the 626 links in the network have different MTU sizes, by using technologies 627 like Path MTU Discovery, the routers are able to be aware of the MTU 628 along the path. The size of the datagram plus the size of IP headers 629 (including the source routing header) should not exceed the minimum 630 MTU along the path, otherwise, the source routing should not be used. 632 If the destination of the datagrams is out the MP-OLSRv2 routing 633 domain, the datagram must be source routed to the gateway between the 634 MP-OLSRv2 routing domain and the rest of the Internet. The gateway 635 MUST remove the source routing header before forwarding the datagram 636 to the rest of the Internet. 638 8.5. Multipath Calculation 640 8.5.1. Requirements of Multipath Calculation 642 The Multipath Routing Set maintains the information of multiple paths 643 to the destination. The Path Tuples of the Multipath Routing Set 644 (Section 7.2) are generated based on a multipath algorithm. 646 For each path to a destination, the algorithm must provide: 648 o The metric of the path to the destination, 650 o The list of intermediate routers on the path. 652 For IPv6 networks, as strict source routing is used, only the routers 653 that exist in the SR-OLSRv2 Router Set are considered in the path 654 calculation, i.e., only the source-routing supported routers can 655 exist in the path. 657 After the calculation of multiple paths, the metric of paths (denoted 658 c_i for path i) to the destination is compared to the R_metric of the 659 the OLSRv2 Routing Tuple ([RFC7181]) to the same destination. If the 660 metric c_i is greater than R_metric * CUTOFF_RATIO (Section 5), the 661 corresponding path i SHOULD NOT be used. If less than 2 paths are 662 found with metrics less than R_metric * CUTOFF_RATIO, the router 663 SHOULD fall back to OLSRv2 Routing Process without using multipath 664 routing. This can happen if there are too many OLSRv2-only routers 665 in the network, and requiring multipath routing may result in 666 inferior paths. 668 By invoking the multipath algorithm, up to NUMBER_OF_PATHS paths are 669 obtained and added to the Multipath Routing Set by creating a 670 Multipath Routing Tuple with: 672 o MR_dest_addr := destination of the datagram 674 o An MP_path_set with calculated Path Tuples. Each Path Tuple 675 corresponds to a path obtained in the Multipath Dijkstra 676 algorithm, with PT_metric := metric of the calculated path and 677 PT_address[1, ..., n-1] := list of intermediate routers. 679 8.5.2. Multipath Dijkstra Algorithm 681 This section introduces the Multipath Dijkstra Algorithm as a default 682 algorithm. It tries to obtain disjoint paths when appropriate, but 683 does not guarantee strict disjoint paths. The use of other 684 algorithms is not prohibited, as long as the requirements described 685 in Section 8.5.1 are met. Using different multipath algorithms will 686 not impact the interoperability. 688 The general principle of the Multipath Dijkstra Algorithm [ADHOC11] 689 is using Dijkstra algorithm for multiple iterations, and at iteration 690 i to look for the shortest path P[i] to the destination d. After 691 each iteration, the metric of used links is increased. Compared to 692 the original Dijkstra's algorithm, the main modification consists in 693 adding two incremental functions named metric functions fp and fe in 694 order to prevent the next steps resulting in similar paths: 696 o fp(c) is used to increase metrics of arcs belonging to the 697 previous path P[i-1] (with i>1), where c is the value of the 698 previous metric. This encourages future paths to use different 699 arcs but not different vertices. 701 o fe(c) is used to increase metrics of the arcs that lead to 702 intermediate vertices of the previous path P[i-1] (with i>1), 703 where c is the value of the previous metric. The "lead to" means 704 that only one vertex of the arc belongs to the previous path 705 P[i-1], while the other vertex does not. The "intermediate" means 706 that the source and destination vertices are not considered. 708 Considering the simple example in Figure 1: a path P[i] S--A--D is 709 obtained at step i. For the next step, the metric of link S--A and 710 A--D are to be increased using fp(c), because they belong to the path 711 P[i]. A--B is to be increased using fe(c), because A is an 712 intermediate vertex of path P[i], and B is not part of P[i]. B--D is 713 unchanged. 715 B 716 / \ 717 / \ 718 / \ 719 S---------A-----------D 721 Figure 1 723 It is possible to choose different fp and fe to get link-disjoint 724 paths or node-disjoint paths as desired. A recommendation for 725 configuration of fp and fe is given in Section 9. 727 To get NUMBER_OF_PATHS different paths, for each path P[i] (i = 1, 728 ..., NUMBER_OF_PATHS) do: 730 1. Run Dijkstra's algorithm to get the shortest path P[i] for the 731 destination d. 733 2. Apply metric function fp to the metric of links (in both 734 directions) in P[i]. 736 3. Apply metric function fe to the metric of links (in both 737 directions) that lead to routers used in P[i]. 739 A simple example of the Multipath Dijkstra Algorithm is illustrated 740 in Appendix A. 742 8.6. Multipath Routing Set Updates 744 The Multipath Routing Set MUST be updated when the Local Information 745 Base, the Neighborhood Information Base, or the Topology Information 746 Base indicate a change (including of any potentially used outgoing 747 neighbor metric values) of the known symmetric links and/or attached 748 networks in the MANET, hence changing the Topology Graph, as 749 described in section 17.7 of [RFC7181]. How the Multipath Routing 750 Set is updated depends on whether the set is maintained reactively or 751 proactively: 753 o In reactive mode, all the Tuples in the Multipath Routing Set are 754 removed. The new arriving datagrams will be processed as 755 specified in Section 8.4; 757 o In proactive mode, the route to all the destinations are updated 758 according to Section 8.5. 760 8.7. Datagram Forwarding 762 In IPv4 networks, datagrams are forwarded using loose source routing 763 as specified in Section 3.1 of [RFC0791]. 765 In IPv6 networks, datagrams are forwarded using strict source routing 766 as specified in Section 4.2 of [RFC6554], except the applied routers 767 are MP-OLSRv2 routers rather than RPL routers. The last hop of the 768 source route MUST remove the source routing header. 770 9. Configuration Parameters 772 This section gives default values and guidelines for setting 773 parameters defined in Section 5. Network administrators may wish to 774 change certain or all the parameters for different network scenarios. 775 As an experimental protocol, the users of this protocol are also 776 encouraged to explore different parameter setting in various network 777 environments, and provide feedback. 779 o NUMBER_OF_PATHS := 3. This parameter defines the number of 780 parallel paths used in datagram forwarding. Setting it to one 781 makes the specification identical to OLSRv2. Setting it to too 782 large values may lead to unnecessary computational overhead and 783 inferior paths. 785 o MAX_SRC_HOPS := 10, for IPv4 networks. For IPv6 networks, it MUST 786 be set to 0, i.e., no constraint on maximum number of hops. 788 o CUTOFF_RATIO := 1.5. It MUST be greater or equal than 1. 790 o SR_TC_INTERVAL := 10 x TC_INTERVAL. It MUST be greater than or 791 equal to TC_INTERVAL. It SHOULD be significantly greater than 792 TC_INTERVAL to reduce unnecessary TC message generations. 794 o SR_HOLD_TIME := 3 x SR_TC_INTERVAL. It MUST be greater than 795 SR_TC_INTERVAL and SHOULD allow for a small number of lost 796 messages. 798 If Multipath Dijkstra Algorithm is applied: 800 o fp(c) := 4*c, where c is the original metric of the link. 802 o fe(c) := 2*c, where c is the original metric of the link. 804 The setting of metric functions fp and fc defines the preference of 805 obtained multiple disjoint paths. If id is the identity function, 806 i.e., fp(c)=c, 3 cases are possible: 808 o if id=fe. 980 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 981 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 982 RFC2119, March 1997, 983 . 985 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 986 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 987 Format", RFC 5444, DOI 10.17487/RFC5444, February 2009, 988 . 990 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 991 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 992 RFC 6130, DOI 10.17487/RFC6130, April 2011, 993 . 995 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 996 Routing Header for Source Routes with the Routing Protocol 997 for Low-Power and Lossy Networks (RPL)", RFC 6554, 998 DOI 10.17487/RFC6554, March 2012, 999 . 1001 [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 1002 "The Optimized Link State Routing Protocol Version 2", 1003 RFC 7181, DOI 10.17487/RFC7181, April 2014, 1004 . 1006 [RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity 1007 Protection for the Neighborhood Discovery Protocol (NHDP) 1008 and Optimized Link State Routing Protocol Version 2 1009 (OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014, 1010 . 1012 14.2. Informative References 1014 [ADHOC11] Yi, J., Adnane, A-H., David, S., and B. Parrein, 1015 "Multipath optimized link state routing for mobile ad hoc 1016 networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, 1017 January, 2011. 1019 [GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria, 1020 "Experimental performance comparison of single-path and 1021 multipath routing in VANETs", In Global Information 1022 Infrastructure and Networking Symposium (GIIS), 2014 , 1023 vol. 1, no. 6, pp. 15-19, 2014. 1025 [I-D.ietf-6man-segment-routing-header] 1026 Previdi, S., Filsfils, C., Raza, K., Leddy, J., Field, B., 1027 daniel.voyer@bell.ca, d., daniel.bernier@bell.ca, d., 1028 Matsushima, S., Leung, I., Linkova, J., Aries, E., Kosugi, 1029 T., Vyncke, E., Lebrun, D., Steinberg, D., and R. Raszuk, 1030 "IPv6 Segment Routing Header (SRH)", 1031 draft-ietf-6man-segment-routing-header-06 (work in 1032 progress), March 2017. 1034 [I-D.ietf-manet-olsrv2-sec-threats] 1035 Clausen, T., Herberg, U., and J. Yi, "Security Threats to 1036 the Optimized Link State Routing Protocol version 2 1037 (OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-04 (work in 1038 progress), January 2017. 1040 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1041 (IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460, 1042 December 1998, . 1044 [RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black, 1045 "Definition of the Differentiated Services Field (DS 1046 Field) in the IPv4 and IPv6 Headers", RFC 2474, 1047 DOI 10.17487/RFC2474, December 1998, 1048 . 1050 [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking 1051 (MANET): Routing Protocol Performance Issues and 1052 Evaluation Considerations", RFC 2501, DOI 10.17487/ 1053 RFC2501, January 1999, 1054 . 1056 [RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and 1057 Multicast Next-Hop Selection", RFC 2991, DOI 10.17487/ 1058 RFC2991, November 2000, 1059 . 1061 [RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation 1062 of Type 0 Routing Headers in IPv6", RFC 5095, 1063 DOI 10.17487/RFC5095, December 2007, 1064 . 1066 [RFC7722] Dearlove, C. and T. Clausen, "Multi-Topology Extension for 1067 the Optimized Link State Routing Protocol Version 2 1068 (OLSRv2)", RFC 7722, DOI 10.17487/RFC7722, December 2015, 1069 . 1071 [RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric 1072 Based on Packet Sequence Numbers for Optimized Link State 1073 Routing Version 2 (OLSRv2)", RFC 7779, DOI 10.17487/ 1074 RFC7779, April 2016, 1075 . 1077 [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 1078 Code: The Implementation Status Section", BCP 205, 1079 RFC 7942, DOI 10.17487/RFC7942, July 2016, 1080 . 1082 [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, 1083 "Simulation and performance analysis of MP-OLSR for mobile 1084 ad hoc networks", In Proceeding of IEEE Wireless 1085 Communications and Networking Conference, 2008. 1087 [WPMC11] Yi, J., Parrein, B., and D. Radu, "Multipath routing 1088 protocol for manet: Application to H.264/SVC video content 1089 delivery", In Proceeding of 14th International Symposium 1090 on Wireless Personal Multimedia Communications. 1092 Appendix A. Examples of Multipath Dijkstra Algorithm 1094 This appendix gives two examples of Multipath Dijkstra algorithm. 1096 A network topology is depicted in Figure 2. 1098 .-----A-----(2) 1099 (1) / \ \ 1100 / / \ \ 1101 S (2) (1) D 1102 \ / \ / 1103 (1) / \ / (2) 1104 B----(3)----C 1106 Figure 2 1108 The capital letters are the names of routers. An arbitrary metric 1109 with value between 1 and 3 is used. The initial metrics of all the 1110 links are indicated in the parentheses. The incremental functions 1111 fp(c)=4c and fe(c)=2c are used in this example. Two paths from 1112 router S to router D are demanded. 1114 On the first run of the Dijkstra algorithm, the shortest path S->A->D 1115 with metric 3 is obtained. 1117 The incremental function fp is applied to increase the metric of the 1118 link S-A and A-D. fe is applied to increase the metric of the link 1119 A-B and A-C. Figure 3 shows the link metrics after the increment. 1121 .-----A-----(8) 1122 (4) / \ \ 1123 / / \ \ 1124 S (4) (2) D 1125 \ / \ / 1126 (1) / \ / (2) 1127 B----(3)----C 1128 Figure 3 1130 On the second run of the Dijkstra algorithm, the second path 1131 S->B->C->D with metric 6 is obtained. 1133 As mentioned in Section 8.5, the Multipath Dijkstra Algorithm does 1134 not guarantee strict disjoint paths in order to avoid choosing 1135 inferior paths. For example, given the topology in Figure 4, two 1136 paths from node S to D are desired. On the top of the figure, there 1137 is a high cost path between S and D. 1139 If a algorithm tries to obtain strict disjoint paths, the two paths 1140 obtained will be S--B--D and S--(high cost path)--D, which are 1141 extremely unbalanced. It is undesirable because it will cause huge 1142 delay variance between the paths. By using the Multipath Dijkstra 1143 algorithm, which is based on the punishing scheme, S--B--D and 1144 S--B--C--D will be obtained. 1146 --high cost path- 1147 / \ 1148 / \ 1149 S----B--------------D 1150 \ / 1151 \---C-----/ 1153 Figure 4 1155 Authors' Addresses 1157 Jiazi Yi 1158 Ecole Polytechnique 1159 91128 Palaiseau Cedex, 1160 France 1162 Phone: +33 (0) 1 77 57 80 85 1163 Email: jiazi@jiaziyi.com 1164 URI: http://www.jiaziyi.com/ 1165 Benoit Parrein 1166 University of Nantes 1167 IRCCyN lab - IVC team 1168 Polytech Nantes, rue Christian Pauc, BP50609 1169 44306 Nantes cedex 3 1170 France 1172 Phone: +33 (0) 2 40 68 30 50 1173 Email: Benoit.Parrein@polytech.univ-nantes.fr 1174 URI: http://www.irccyn.ec-nantes.fr/~parrein