idnits 2.17.1 draft-ietf-manet-olsrv2-multipath-13.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 10, 2017) is 2540 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 469 -- Looks like a reference, but probably isn't: '2' on line 469 == 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 11, 2017 University of Nantes 6 May 10, 2017 8 Multipath Extension for the Optimized Link State Routing Protocol 9 version 2 (OLSRv2) 10 draft-ietf-manet-olsrv2-multipath-13 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, so as to improve reliability of the OLSRv2 protocol. 17 The interoperability with OLSRv2 is retained. 19 Status of this Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at http://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on November 11, 2017. 36 Copyright Notice 38 Copyright (c) 2017 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3 55 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 56 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 57 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 58 5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 8 59 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 8 60 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 8 61 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 9 62 6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . . 9 63 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 9 64 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 9 65 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 9 66 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 10 67 7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 10 68 7.2. Multipath Routing Set . . . . . . . . . . . . . . . . . . 10 69 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 11 70 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 11 71 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 11 72 8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 12 73 8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 12 74 8.5. Multipath Calculation . . . . . . . . . . . . . . . . . . 14 75 8.5.1. Requirements of Multipath Calculation . . . . . . . . 14 76 8.5.2. Multipath Dijkstra Algorithm . . . . . . . . . . . . . 15 77 8.6. Multipath Routing Set Updates . . . . . . . . . . . . . . 16 78 8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 16 79 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 17 80 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 18 81 10.1. Multipath extension based on nOLSRv2 . . . . . . . . . . . 18 82 10.2. Multipath extension based on olsrd . . . . . . . . . . . . 18 83 10.3. Multipath extension based on umOLSR . . . . . . . . . . . 19 84 11. Security Considerations . . . . . . . . . . . . . . . . . . . 19 85 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 86 12.1. Message TLV Types . . . . . . . . . . . . . . . . . . . . 20 87 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 88 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 89 14.1. Normative References . . . . . . . . . . . . . . . . . . . 21 90 14.2. Informative References . . . . . . . . . . . . . . . . . . 22 91 Appendix A. Examples of Multipath Dijkstra Algorithm . . . . . . 23 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25 94 1. Introduction 96 The Optimized Link State Routing Protocol version 2 (OLSRv2) 97 [RFC7181] is a proactive link state protocol designed for use in 98 mobile ad hoc networks (MANETs). It generates routing messages 99 periodically to create and maintain a Routing Set, which contains 100 routing information to all the possible destinations in the routing 101 domain. For each destination, there exists a unique Routing Tuple, 102 which indicates the next hop to reach the destination. 104 This document specifies an extension of the OLSRv2 protocol 105 [RFC7181], to provide multiple disjoint paths when appropriate for a 106 source-destination pair. Because of the characteristics of MANETs 107 [RFC2501], especially the dynamic topology, having multiple paths is 108 helpful for increasing network throughput, improving forwarding 109 reliability, and load balancing. 111 Multipath OLSRv2 (MP-OLSRv2) specified in this document uses the 112 Multipath Dijkstra algorithm by default to explore multiple disjoint 113 paths from a source router to a destination router based on the 114 topology information obtained through OLSRv2, and to forward the 115 datagrams in a load-balancing manner using source routing. MP-OLSRv2 116 is designed to be interoperable with OLSRv2. 118 1.1. Motivation and Experiments to Be Conducted 120 This document is an experimental extension of OLSRv2 that can 121 increase the data forwarding reliability in dynamic and high-load 122 MANET scenarios by transmitting datagrams over multiple disjoint 123 paths using source routing. This mechanism is used because: 125 o Disjoint paths can avoid single route failures. 127 o Transmitting datagrams through parallel paths can increase 128 aggregated throughput. 130 o Some scenarios may require some routers must (or must not) be 131 used. 133 o Having control of the paths at the source benefits the load 134 balancing and traffic engineering. 136 o An application of this extension is in combination with Forward 137 Error Correction (FEC) coding applied across packets (erasure 138 coding) [WPMC11]. Because the packet drop is normally bursty in a 139 path (for example, due to route failure), erasure coding is less 140 effective in single path routing protocols. By providing multiple 141 disjoint paths, the application of erasure coding with multipath 142 protocol is more resilient to routing failures. 144 While in existing deployments, running code and simulations have 145 proven the interest of multipath extension for OLSRv2 in certain 146 networks, more experiments and experiences are still needed to 147 understand the effects of the protocol. The multipath extension for 148 OLSRv2 is expected to be revised and improved to the Standards Track 149 once sufficient operational experience is obtained. Other than 150 general experiences including the protocol specification and 151 interoperability with base OLSRv2 implementations, the experiences in 152 the following aspects are highly appreciated: 154 o Optimal values for the number of multiple paths (NUMBER_OF_PATHS, 155 Section 5) to be used. This depends on the network topology and 156 router density. 158 o Optimal values used in the metric functions. Metric functions are 159 applied to increase the metric of used links and nodes so as to 160 obtain disjoint paths. What kind of disjointness is desired 161 (node-disjoint or link-disjoint) may depend on the layer 2 162 protocol used, and can be achieved by applying different sets of 163 metric functions. 165 o Use of different metric types. This multipath extension can be 166 used with metric types that meet the requirement of OLSRv2, such 167 as [RFC7779]. The metric type used has also impact to the choice 168 of metric functions as indicated in the previous bullet point. 170 o The impact of partial topology information to multipath 171 calculation. OLSRv2 maintains a partial topology information base 172 to reduce protocol overhead. Although with existing experience, 173 multiple paths can be obtained even with such partial information, 174 the calculation might be impacted, depending on the Multi-Point 175 Relay (MPR) selection algorithm used. 177 o Use of IPv6 loose source routing. In the current specification, 178 only strict source routing is used for IPv6 based on [RFC6554]. 179 In [I-D.ietf-6man-segment-routing-header], the use of the loose 180 source routing is also proposed in IPv6. In scenarios where the 181 length of the source routing header is critical, the loose source 182 routing can be considered. 184 o Optimal choice of "key" routers for loose source routing. In some 185 cases, loose source routing is used to reduce overhead or for 186 interoperability with OLSRv2 routers. Other than the basic rules 187 defined in the following parts of this document, optimal choices 188 of routers to put in the loose source routing header can be 189 further studied. 191 o Different path-selection schedulers. By default, round-robin 192 scheduling is used to select a path to be used for datagrams. In 193 some scenarios, weighted scheduling can be considered: for 194 example, the paths with lower metrics (i.e., higher quality) can 195 transfer more datagrams compared to paths with higher metrics. 197 o The impacts of the delay variation due to multipath routing. 198 [RFC2991] brings out some concerns of multipath routing, 199 especially variable latencies. Although current experiment 200 results show that multipath routing can reduce the jitter in 201 dynamic scenarios, some transport protocols or applications may be 202 sensitive to the datagram re-ordering. 204 o The disjoint multipath protocol has interesting application with 205 erasure coding, especially for services like video/audio streaming 206 [WPMC11]. The combination of erasure coding mechanisms and this 207 extension is thus encouraged. 209 o Different algorithms to obtain multiple paths, other than the 210 default Multipath Dijkstra algorithm introduced in this 211 specification. 213 o The use of multi-topology information. By using [RFC7722], 214 multiple topologies using different metric types can be obtained. 215 Although there is no work defining how this extension can make use 216 of the multi-topology information base yet, it is encouraged to 217 experiment with the use of multiple metrics for building multiple 218 paths. 220 2. Terminology 222 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 223 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 224 "OPTIONAL" in this document are to be interpreted as described in 225 [RFC2119]. 227 This document uses the terminology and notation defined in [RFC5444], 228 [RFC6130], [RFC7181]. Additionally, it defines the following 229 terminology: 231 OLSRv2 Routing Process - A routing process based on [RFC7181], 232 without multipath extension specified in this document. 234 MP-OLSRv2 Routing Process - A multipath routing process based on 235 this specification as an extension to [RFC7181]. 237 SR-OLSRv2 Routing Process - A OLSRv2 Routing Process that supports 238 source routing, or an MP-OLSRv2 Routing Process. 240 3. Applicability Statement 242 As an extension of OLSRv2, this specification is applicable to MANETs 243 for which OLSRv2 is applicable (see [RFC7181]). It can operate on 244 single or multiple interfaces to discover multiple disjoint paths 245 from a source router to a destination router. MP-OLSRv2 is designed 246 for networks with dynamic topology by avoiding single route failure. 247 It can also provide higher aggregated throughput and load balancing. 249 In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily 250 replace OLSRv2 completely. The extension can be applied for certain 251 applications that are suitable for multipath routing (mainly video or 252 audio streams), based on information such as a DiffServ codepoint 253 [RFC2474]. 255 Compared to OLSRv2, this extension does not introduce any new message 256 type. A new Message TLV Type is introduced to identify the routers 257 that support forwarding based on source routing header. It is 258 interoperable with OLSRv2 implementations that do not have this 259 extension: as the MP-OLSRv2 uses source routing, in IPv4 networks the 260 interoperability is achieved by using the loose source routing 261 header; in IPv6 networks, it is achieved by eliminating routers that 262 do not support IPv6 strict source routing. 264 MP-OLSRv2 supports two different, but interoperable multipath 265 calculation approaches: proactive and reactive. In the proactive 266 calculation, the paths to all the destinations are calculated before 267 needed. In the reactive calculation, only the paths to desired 268 destination(s) are calculated on demand. The proactive approach 269 requires more computational resources than the reactive one. The 270 reactive approach requires the IP forwarding plane to trigger the 271 multipath calculation. 273 MP-OLSRv2 forwards datagrams using the source routing header. As 274 there are multiple paths to each destination, MP-OLSRv2 requires the 275 IP forwarding plane to be able to choose which source route to be put 276 in the source routing header based on the path scheduler defined by 277 MP-OLSRv2. For IPv4 networks, implementation of loose source routing 278 is required following [RFC0791]. For IPv6 networks, implementation 279 of strict source routing is required following the source routing 280 header generation and processing defined in [RFC6554]. 282 4. Protocol Overview and Functioning 284 This specification uses OLSRv2 [RFC7181] to: 286 o Identify all the reachable routers in the network. 288 o Identify a sufficient subset of links in the networks, so that 289 routes can be calculated to all reachable destinations. 291 o Provide a Routing Set containing the shortest routes from this 292 router to all destinations. 294 In addition, the MP-OLSRv2 Routing Process identifies the routers 295 that support source routing by adding a new Message TLV in HELLO and 296 TC messages. Based on the above information acquired, every MP- 297 OLSRv2 Routing Process is aware of a reduced topology map of the 298 network and the routers supporting source routing. 300 A Multipath Routing Set containing the multipath information is 301 maintained. It may either be proactively calculated or reactively 302 calculated: 304 o In the proactive approach, multiple paths to all possible 305 destinations are calculated and updated based on control message 306 exchange. The routes are thus available before they are actually 307 needed. 309 o In the reactive approach, a multipath algorithm is invoked on 310 demand, i.e., only when there is a datagram to be sent from the 311 source to the destination, and there is no available Routing Tuple 312 in the Multipath Routing Set. This requires the IP forwarding 313 information base to trigger the multipath calculation specified in 314 Section 8.5 when no Multipath Routing Tuple is available. The 315 reactive operation is local in the router and no additional 316 routing control messages exchange is required. When the paths are 317 being calculated, the datagrams SHOULD be buffered unless the 318 router does not have enough memory. 320 Routers in the same network may choose either proactive or reactive 321 multipath calculation independently according to their computation 322 resources. The Multipath Dijkstra algorithm (defined in Section 8.5) 323 is introduced as the default algorithm to generate multiple disjoint 324 paths from a source to a destination, and such information is kept in 325 the Multipath Routing Set. 327 The datagram is forwarded based on source routing. When there is a 328 datagram to be sent to a destination, the source router acquires a 329 path from the Multipath Routing Set (MAY be round-robin, or other 330 scheduling algorithms). The path information is stored in the 331 datagram header using the source routing header. 333 5. Parameters and Constants 335 In addition to the parameters and constants defined in [RFC7181], 336 this specification uses the parameters and constants described in 337 this section. 339 5.1. Router Parameters 341 NUMBER_OF_PATHS The number of paths desired by the router. 343 MAX_SRC_HOPS The maximum number of hops allowed to be put in the 344 source routing header. A value set zero means there is no 345 limitation on the maximum number of hops. In an IPv6 network, it 346 MUST be set to 0 because [RFC6554] supports only strict source 347 routing. All the intermediate routers MUST be included in the 348 source routing header, which makes the number of hops to be kept a 349 variable. In an IPv4 network, it MUST be strictly less than 11 350 and greater than 0 due to the length limit of the IPv4 header. 352 CUTOFF_RATIO The ratio that defines the maximum metric of a path 353 compared to the shortest path kept in the OLSRv2 Routing Set. For 354 example, the metric to a destination is R_metric based on the 355 Routing Set. Then the maximum metric allowed for a path is 356 CUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be greater than or 357 equal to 1. Note that setting the value to 1 means looking for 358 equal length paths, which may not be possible in some networks. 360 SR_TC_INTERVAL The maximum time between the transmission of two 361 successive TC messages by an MP-OLSRv2 Routing Process. 363 SR_HOLD_TIME The minimum value in the TLV with Type = VALIDITY_TIME 364 included in TC messages generated based on SR_TC_INTERVAL. 366 6. Packets and Messages 368 This extension employs the routing control messages HELLO and TC 369 (Topology Control) as defined in OLSRv2 [RFC7181] to obtain network 370 topology information. For the datagram to support source routing, a 371 source routing header is added to each datagram routed by this 372 extension. Depending on the IP version used, the source routing 373 header is defined in this section. 375 6.1. HELLO and TC messages 377 HELLO and TC messages used by the MP-OLSRv2 Routing Process use the 378 same format as defined in [RFC7181]. In addition, a new Message TLV 379 type is defined, to identify the originator of the HELLO or TC 380 message that supports source route forwarding. The new Message TLV 381 type is introduced for enabling MP-OLSRv2 as an extension of OLSRv2: 382 only the routers supporting source-route forwarding can be used in 383 the source routing header of a datagram, because adding a router that 384 does not understand the source routing header will cause routing 385 failure. 387 6.1.1. SOURCE_ROUTE TLV 389 SOURCE_ROUTE TLV is a Message TLV signaling that the message is 390 generated by a router that supports source-route forwarding. It can 391 be an MP-OLSRv2 Routing Process, or an OLSRv2 Routing Process that 392 supports source-route forwarding. 394 Every HELLO or TC message generated by a MP-OLSRv2 Routing Process 395 MUST have exactly one SOURCE_ROUTE TLV without value. 397 Every HELLO or TC message generated by an OLSRv2 Routing Process MUST 398 have exactly one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process 399 supports source-route forwarding, and is willing to join the source 400 route generated by other MP-OLSRv2 Routing Processes. The existence 401 of SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing 402 Process, i.e., either it adds SOURCE_ROUTE TLV to all its HELLO/TC 403 messages, or it does not add SOURCE_ROUTE TLV to any HELLO/TC 404 messages. 406 6.2. Datagram 408 6.2.1. Source Routing Header in IPv4 410 In IPv4 [RFC0791] networks, the MP-OLSRv2 Routing Process employs the 411 loose source routing header, as defined in [RFC0791]. It exists as 412 an option header, with option class 0, and option number 3. 414 The source route information is kept in the "route data" field of the 415 loose source route header. 417 6.2.2. Source Routing Header in IPv6 419 In IPv6 [RFC2460] networks, the MP-OLSRv2 Routing Process employs the 420 source routing header as defined in section 3 of [RFC6554], with IPv6 421 Routing Type 3. 423 The source route information is kept in the "Addresses" field of the 424 routing header. 426 7. Information Bases 428 Each MP-OLSRv2 Routing Process maintains the information bases as 429 defined in [RFC7181]. Additionally, a Multipath Information Base is 430 used for this specification. It includes the protocol sets as 431 defined below. 433 7.1. SR-OLSRv2 Router Set 435 The SR-OLSRv2 Router Set records the routers that support source- 436 route forwarding. This includes routers that run the MP-OLSRv2 437 Routing Process or the OLSRv2 Routing Process with source-route 438 forwarding support. The set consists of SR-OLSRv2 Router Tuples: 440 (SR_addr, SR_time) 442 where: 444 SR_addr - is the original address of the router that supports 445 source-route forwarding; 447 SR_time - is the time until which the SR-OLSRv2 Router Tuple is 448 considered valid. 450 7.2. Multipath Routing Set 452 The Multipath Routing Set records the full path information of 453 different paths to the destination. It consists of Multipath Routing 454 Tuples: 456 (MR_dest_addr, MR_path_set) 458 where: 460 MR_dest_addr - is the network address of the destination, either 461 the network address of an interface of a destination router or the 462 network address of an attached network; 464 MP_path_set - contains the multiple paths to the destination. It 465 consists of a set of Path Tuples. 467 Each Path Tuple is defined as: 469 (PT_metric, PT_address[1], PT_address[2], ..., PT_address[n]) 470 where: 472 PT_metric - is the metric of the path to the destination, measured 473 in LINK_METRIC_TYPE defined in [RFC7181]; 475 PT_address[1, ..., n-1] - are the addresses of intermediate routers 476 to be visited numbered from 1 to n-1, where n is the number of 477 routers in the path, i.e., the hop count. 479 8. Protocol Details 481 This protocol is based on OLSRv2, and extended to discover multiple 482 disjoint paths from a source router to a destination router. It 483 retains the basic routing control packets formats and processing of 484 OLSRv2 to obtain the topology information of the network. The main 485 differences from the OLSRv2 Routing Process are the datagram 486 processing at the source router and datagram forwarding. 488 8.1. HELLO and TC Message Generation 490 HELLO messages are generated according to Section 15.1 of [RFC7181], 491 plus a single message TLV with Type := SOURCE_ROUTE included. 493 TC message are generated according to Section 16.1 of [RFC7181] plus 494 a single message TLV with Type := SOURCE_ROUTE included. At least 495 one TC message MUST be generated by an MP-OLSRv2 Routing Process 496 during the SR_TC_INTERVAL (Section 5), which is greater than 497 TC_INTERVAL. 499 TC message generation based on SR_TC_INTERVAL does not replace the 500 ordinary TC message generation specified in [RFC7181] and MUST NOT 501 carry any advertised neighbor addresses. This is due to the fact 502 that not all routers will generate TC messages based on OLSRv2. The 503 TC generation based on SR_TC_INTERVAL serves for those routers to 504 advertise the SOURCE_ROUTE TLV so that the other routers can be aware 505 of the source-route enabled routers so as to be used as destinations 506 of multipath routing. The validity time associated with the 507 VALIDITY_TIME TLV in such TC messages equals SR_HOLD_TIME, which MUST 508 be greater than the SR_TC_INTERVAL. 510 8.2. HELLO and TC Message Processing 512 HELLO and TC messages are processed according to section 15.3 and 513 16.3 of [RFC7181]. 515 In addition to the reasons specified in [RFC7181] for discarding a 516 HELLO message or a TC message on reception, a HELLO or TC message 517 received MUST be discarded if it has more than one Message TLV with 518 Type = SOURCE_ROUTE. 520 For every HELLO or TC message received, if there is a Message TLV 521 with Type := SOURCE_ROUTE, create or update (if the Tuple exists 522 already) the SR-OLSR Router Tuple with 524 o SR_addr := originator address of the HELLO or TC message 526 o SR_time := current_time + validity time of the TC or HELLO message 527 defined in [RFC7181], unless the existing SR_time is greater than 528 the newly calculated the SR_time. 530 8.3. MPR Selection 532 Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs 533 following Section 18 of [RFC7181]. In a mixed network with OLSRv2- 534 only routers, the following considerations apply when calculating 535 MPRs: 537 o MP-OLSRv2 routers SHOULD be preferred as routing MPRs to increase 538 the possibility of finding disjoint paths using MP-OLSRv2 routers. 540 o The number of routing MPRs that run MP-OLSRv2 Routing Process MUST 541 be equal or greater than NUMBER_OF_PATHS if there are enough MP- 542 OLSRv2 symmetric neighbors. Otherwise all the MP-OLSRv2 routers 543 are selected as routing MPRs, expect the routers with willingness 544 WILL_NEVER. 546 8.4. Datagram Processing at the MP-OLSRv2 Originator 548 If datagrams without source routing header need to be forwarded using 549 multiple paths (for example, based on the information of a DiffServ 550 codepoint [RFC2474]), the MP-OLSRv2 Routing Process will try to find 551 the Multipath Routing Tuple where: 553 o MR_dest_addr = destination of the datagram 555 If no matching Multipath Routing Tuple is found and the Multipath 556 Routing Set is maintained proactively, it indicates that there is no 557 multipath route available to the desired destination. The datagram 558 is forwarded following the OLSRv2 Routing Process. 560 If no matching Multipath Routing Tuple is found and the Multipath 561 Routing Set is maintained reactively, the multipath algorithm defined 562 in Section 8.5 is invoked, to calculate the Multipath Routing Tuple 563 to the destination. If the calculation does not return any Multipath 564 Routing Tuple, the following steps are aborted and the datagram is 565 forwarded following the OLSRv2 Routing Process. 567 If a matching Multipath Routing Tuple is obtained, the Path Tuples of 568 the Multipath Routing Tuple are applied to the datagrams using round- 569 robin scheduling. For example, there are 2 path Tuples (Path-1, 570 Path-2) for destination router D. A series of datagrams (Packet-1, 571 Packet-2, Packet-3, ... etc.) are to be sent router D. Path-1 is then 572 chosen for Packet-1, Path-2 for Packet-2, Path-1 for Packet 3, etc. 573 Other path scheduling mechanisms are also possible and will not 574 impact the interoperability of different implementations. 576 The addresses in PT_address[1, ..., n-1] of the chosen Path Tuple are 577 thus added to the datagram header as the source routing header. For 578 IPv6 networks, strict source routing is used, thus all the 579 intermediate routers in the path are stored in the source routing 580 header following the format defined in section 3 of [RFC6554] with 581 Routing Type set to 3. 583 For IPv4 networks, loose source routing is used, with the following 584 rules: 586 o Only the addresses that exist in SR-OLSR Router Set can be added 587 to the source routing header. 589 o If the length of the path (n) is greater than MAX_SRC_HOPS 590 (Section 5) or adding the whole path information exceeds the MTU, 591 only the "key" routers in the path are kept. By default, the key 592 routers are uniformly chosen in the path. If further information 593 such as capacity of the routers (e.g., battery life) or the 594 routers' willingness in forwarding data is available, the routers 595 with higher capacity and willingness are preferred. 597 o The routers that are considered not appropriate for forwarding 598 indicated by external policies should be avoided. 600 It is not recommended to fragment the IP packet if the packet with 601 the source routing header would exceed the minimum MTU along the 602 path. Depending on the size of the routing domain, the MTU should be 603 at least 1280 + 40 (for the outer IP header) + 16 * diameter of the 604 network in number of hops (for the source routing header). If the 605 links in the network have different MTU sizes, by using technologies 606 like Path MTU Discovery, the routers are able to be aware of the MTU 607 along the path. The size of the datagram plus the size of IP headers 608 (including the source routing header) should not exceed the minimum 609 MTU along the path, otherwise, the source routing should not be used. 611 If the destination of the datagrams is out the MP-OLSRv2 routing 612 domain, the datagram must be source route to the gateway between the 613 MP-OLSRv2 routing domain and the rest of the Internet. The gateway 614 MUST remove the source routing header before forwarding the datagram 615 to the rest of the Internet. 617 8.5. Multipath Calculation 619 8.5.1. Requirements of Multipath Calculation 621 The Multipath Routing Set maintains the information of multiple paths 622 to the destination. The Path Tuples of the Multipath Routing Set 623 (Section 7.2) are generated based on a multipath algorithm. 625 For each path to a destination, the algorithm must provide: 627 o The metric of the path to the destination, 629 o The list of intermediate routers on the path. 631 For IPv6 networks, as strict source routing is used, only the routers 632 that exist in the SR-OLSRv2 Router Set are considered in the path 633 calculation, i.e., only the source-routing supported routers can 634 exist in the path. 636 After the calculation of multiple paths, the metric of paths (denoted 637 c_i for path i) to the destination is compared to the R_metric of the 638 the OLSRv2 Routing Tuple ([RFC7181]) to the same destination. If the 639 metric c_i is greater than R_metric * CUTOFF_RATIO (Section 5), the 640 corresponding path i SHOULD NOT be used. If less than 2 paths are 641 found with metrics less than R_metric * CUTOFF_RATIO, the router 642 SHOULD fall back to OLSRv2 Routing Process without using multipath 643 routing. This can happen if there are too many OLSRv2-only routers 644 in the network, and requiring multipath routing may result in 645 inferior paths. 647 By invoking the multipath algorithm, up to NUMBER_OF_PATHS paths are 648 obtained and added to the Multipath Routing Set by creating a 649 Multipath Routing Tuple with: 651 o MR_dest_addr := destination of the datagram 653 o An MP_path_set with calculated Path Tuples. Each Path Tuple 654 corresponds to a path obtained in the Multipath Dijkstra 655 algorithm, with PT_metric := metric of the calculated path and 656 PT_address[1, ..., n-1] := list of intermediate routers. 658 8.5.2. Multipath Dijkstra Algorithm 660 This section introduces the Multipath Dijkstra Algorithm as a default 661 algorithm. It tries to obtain disjoint paths when appropriate, but 662 does not guarantee strict disjoint paths. The use of other 663 algorithms is not prohibited, as long as the requirements described 664 in Section 8.5.1 are met. Using different multipath algorithms will 665 not impact the interoperability. 667 The general principle of the Multipath Dijkstra Algorithm [ADHOC11] 668 is using Dijkstra algorithm for multiple iterations, and at iteration 669 i to look for the shortest path P[i] to the destination d. After 670 each iteration, the metric of used links is increased. Compared to 671 the original Dijkstra's algorithm, the main modification consists in 672 adding two incremental functions named metric functions fp and fe in 673 order to prevent the next steps resulting in similar paths: 675 o fp(c) is used to increase metrics of arcs belonging to the 676 previous path P[i-1] (with i>1), where c is the value of the 677 previous metric. This encourages future paths to use different 678 arcs but not different vertices. 680 o fe(c) is used to increase metrics of the arcs that lead to 681 intermediate vertices of the previous path P[i-1] (with i>1), 682 where c is the value of the previous metric. The "lead to" means 683 that only one vertex of the arc belongs to the previous path 684 P[i-1], while the other vertex does not. The "intermediate" means 685 that the source and destination vertices are not considered. 687 Considering the simple example in Figure 1: a path P[i] S--A--D is 688 obtained at step i. For the next step, the metric of link S--A and 689 A--D are to be increased using fp(c), because they belong to the path 690 P[i]. A--B is to be increased using fe(c), because A is an 691 intermediate vertex of path P[i], and B is not part of P[i]. B--D is 692 unchanged. 694 B 695 / \ 696 / \ 697 / \ 698 S---------A-----------D 700 Figure 1 702 It is possible to choose different fp and fe to get link-disjoint 703 paths or node-disjoint paths as desired. A recommendation for 704 configuration of fp and fe is given in Section 9. 706 To get NUMBER_OF_PATHS different paths, for each path P[i] (i = 1, 707 ..., NUMBER_OF_PATHS) do: 709 1. Run Dijkstra's algorithm to get the shortest path P[i] for the 710 destination d. 712 2. Apply metric function fp to the metric of links (in both 713 directions) in P[i]. 715 3. Apply metric function fe to the metric of links (in both 716 directions) that lead to routers used in P[i]. 718 A simple example of the Multipath Dijkstra Algorithm is illustrated 719 in Appendix A. 721 8.6. Multipath Routing Set Updates 723 The Multipath Routing Set MUST be updated when the Local Information 724 Base, the Neighborhood Information Base, or the Topology Information 725 Base indicate a change (including of any potentially used outgoing 726 neighbor metric values) of the known symmetric links and/or attached 727 networks in the MANET, hence changing the Topology Graph, as 728 described in section 17.7 of [RFC7181]. How the Multipath Routing 729 Set is updated depends on whether the set is maintained reactively or 730 proactively: 732 o In reactive mode, all the Tuples in the Multipath Routing Set are 733 removed. The new arriving datagrams will be processed as 734 specified in Section 8.4; 736 o In proactive mode, the route to all the destinations are updated 737 according to Section 8.5. 739 8.7. Datagram Forwarding 741 In IPv4 networks, datagrams are forwarded using loose source routing 742 as specified in Section 3.1 of [RFC0791]. 744 In IPv6 networks, datagrams are forwarded using strict source routing 745 as specified in Section 4.2 of [RFC6554], except the applied routers 746 are MP-OLSRv2 routers rather than RPL routers. The last hop of the 747 source route MUST remove the source routing header. 749 9. Configuration Parameters 751 This section gives default values and guidelines for setting 752 parameters defined in Section 5. Network administrators may wish to 753 change certain or all the parameters for different network scenarios. 754 As an experimental protocol, the users of this protocol are also 755 encouraged to explore different parameter setting in various network 756 environments, and provide feedback. 758 o NUMBER_OF_PATHS := 3. This parameter defines the number of 759 parallel paths used in datagram forwarding. Setting it to one 760 makes the specification identical to OLSRv2. Setting it to too 761 large values may lead to unnecessary computational overhead and 762 inferior paths. 764 o MAX_SRC_HOPS := 10, for IPv4 networks. For IPv6 networks, it MUST 765 be set to 0, i.e., no constraint on maximum number of hops. 767 o CUTOFF_RATIO := 1.5. It MUST be greater or equal than 1. 769 o SR_TC_INTERVAL := 10 x TC_INTERVAL. It SHOULD be significantly 770 greater than TC_INTERVAL to reduce unnecessary TC message 771 generations. 773 o SR_HOLD_TIME := 32 x TC_INTERVAL. It MUST be greater than 774 SR_TC_INTERVAL. It SHOULD be greater than 30 x TC_INTERVAL. 776 If Multipath Dijkstra Algorithm is applied: 778 o fp(c) := 4*c, where c is the original metric of the link. 780 o fe(c) := 2*c, where c is the original metric of the link. 782 The setting of metric functions fp and fc defines the preference of 783 obtained multiple disjoint paths. If id is the identity function, 784 i.e., fp(c)=c, 3 cases are possible: 786 o if id=fe. 957 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 958 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 959 RFC2119, March 1997, 960 . 962 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 963 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 964 Format", RFC 5444, DOI 10.17487/RFC5444, February 2009, 965 . 967 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 968 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 969 RFC 6130, DOI 10.17487/RFC6130, April 2011, 970 . 972 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 973 Routing Header for Source Routes with the Routing Protocol 974 for Low-Power and Lossy Networks (RPL)", RFC 6554, 975 DOI 10.17487/RFC6554, March 2012, 976 . 978 [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 979 "The Optimized Link State Routing Protocol Version 2", 980 RFC 7181, DOI 10.17487/RFC7181, April 2014, 981 . 983 [RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity 984 Protection for the Neighborhood Discovery Protocol (NHDP) 985 and Optimized Link State Routing Protocol Version 2 986 (OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014, 987 . 989 14.2. Informative References 991 [ADHOC11] Yi, J., Adnane, A-H., David, S., and B. Parrein, 992 "Multipath optimized link state routing for mobile ad hoc 993 networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, 994 January, 2011. 996 [GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria, 997 "Experimental performance comparison of single-path and 998 multipath routing in VANETs", In Global Information 999 Infrastructure and Networking Symposium (GIIS), 2014 , 1000 vol. 1, no. 6, pp. 15-19, 2014. 1002 [I-D.ietf-6man-segment-routing-header] 1003 Previdi, S., Filsfils, C., Raza, K., Leddy, J., Field, B., 1004 daniel.voyer@bell.ca, d., daniel.bernier@bell.ca, d., 1005 Matsushima, S., Leung, I., Linkova, J., Aries, E., Kosugi, 1006 T., Vyncke, E., Lebrun, D., Steinberg, D., and R. Raszuk, 1007 "IPv6 Segment Routing Header (SRH)", 1008 draft-ietf-6man-segment-routing-header-06 (work in 1009 progress), March 2017. 1011 [I-D.ietf-manet-olsrv2-sec-threats] 1012 Clausen, T., Herberg, U., and J. Yi, "Security Threats to 1013 the Optimized Link State Routing Protocol version 2 1014 (OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-04 (work in 1015 progress), January 2017. 1017 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1018 (IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460, 1019 December 1998, . 1021 [RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black, 1022 "Definition of the Differentiated Services Field (DS 1023 Field) in the IPv4 and IPv6 Headers", RFC 2474, 1024 DOI 10.17487/RFC2474, December 1998, 1025 . 1027 [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking 1028 (MANET): Routing Protocol Performance Issues and 1029 Evaluation Considerations", RFC 2501, DOI 10.17487/ 1030 RFC2501, January 1999, 1031 . 1033 [RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and 1034 Multicast Next-Hop Selection", RFC 2991, DOI 10.17487/ 1035 RFC2991, November 2000, 1036 . 1038 [RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation 1039 of Type 0 Routing Headers in IPv6", RFC 5095, 1040 DOI 10.17487/RFC5095, December 2007, 1041 . 1043 [RFC7722] Dearlove, C. and T. Clausen, "Multi-Topology Extension for 1044 the Optimized Link State Routing Protocol Version 2 1045 (OLSRv2)", RFC 7722, DOI 10.17487/RFC7722, December 2015, 1046 . 1048 [RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric 1049 Based on Packet Sequence Numbers for Optimized Link State 1050 Routing Version 2 (OLSRv2)", RFC 7779, DOI 10.17487/ 1051 RFC7779, April 2016, 1052 . 1054 [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 1055 Code: The Implementation Status Section", BCP 205, 1056 RFC 7942, DOI 10.17487/RFC7942, July 2016, 1057 . 1059 [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, 1060 "Simulation and performance analysis of MP-OLSR for mobile 1061 ad hoc networks", In Proceeding of IEEE Wireless 1062 Communications and Networking Conference, 2008. 1064 [WPMC11] Yi, J., Parrein, B., and D. Radu, "Multipath routing 1065 protocol for manet: Application to H.264/SVC video content 1066 delivery", In Proceeding of 14th International Symposium 1067 on Wireless Personal Multimedia Communications. 1069 Appendix A. Examples of Multipath Dijkstra Algorithm 1071 This appendix gives two examples of Multipath Dijkstra algorithm. 1073 A network topology is depicted in Figure 2. 1075 .-----A-----(2) 1076 (1) / \ \ 1077 / / \ \ 1078 S (2) (1) D 1079 \ / \ / 1080 (1) / \ / (2) 1081 B----(3)----C 1083 Figure 2 1085 The capital letters are the names of routers. An arbitrary metric 1086 with value between 1 and 3 is used. The initial metrics of all the 1087 links are indicated in the parentheses. The incremental functions 1088 fp(c)=4c and fe(c)=2c are used in this example. Two paths from 1089 router S to router D are demanded. 1091 On the first run of the Dijkstra algorithm, the shortest path S->A->D 1092 with metric 3 is obtained. 1094 The incremental function fp is applied to increase the metric of the 1095 link S-A and A-D. fe is applied to increase the metric of the link 1096 A-B and A-C. Figure 3 shows the link metrics after the increment. 1098 .-----A-----(8) 1099 (4) / \ \ 1100 / / \ \ 1101 S (4) (2) D 1102 \ / \ / 1103 (1) / \ / (2) 1104 B----(3)----C 1106 Figure 3 1108 On the second run of the Dijkstra algorithm, the second path 1109 S->B->C->D with metric 6 is obtained. 1111 As mentioned in Section 8.5, the Multipath Dijkstra Algorithm does 1112 not guarantee strict disjoint paths in order to avoid choosing 1113 inferior paths. For example, given the topology in Figure 4, two 1114 paths from node S to D are desired. On the top of the figure, there 1115 is a high cost path between S and D. 1117 If a algorithm tries to obtain strict disjoint paths, the two paths 1118 obtained will be S--B--D and S--(high cost path)--D, which are 1119 extremely unbalanced. It is undesirable because it will cause huge 1120 delay variance between the paths. By using the Multipath Dijkstra 1121 algorithm, which is based on the punishing scheme, S--B--D and 1122 S--B--C--D will be obtained. 1124 --high cost path- 1125 / \ 1126 / \ 1127 S----B--------------D 1128 \ / 1129 \---C-----/ 1131 Figure 4 1133 Authors' Addresses 1135 Jiazi Yi 1136 Ecole Polytechnique 1137 91128 Palaiseau Cedex, 1138 France 1140 Phone: +33 (0) 1 77 57 80 85 1141 Email: jiazi@jiaziyi.com 1142 URI: http://www.jiaziyi.com/ 1144 Benoit Parrein 1145 University of Nantes 1146 IRCCyN lab - IVC team 1147 Polytech Nantes, rue Christian Pauc, BP50609 1148 44306 Nantes cedex 3 1149 France 1151 Phone: +33 (0) 2 40 68 30 50 1152 Email: Benoit.Parrein@polytech.univ-nantes.fr 1153 URI: http://www.irccyn.ec-nantes.fr/~parrein