idnits 2.17.1 draft-ietf-manet-olsrv2-multipath-09.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 (June 8, 2016) is 2872 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 435 -- Looks like a reference, but probably isn't: '2' on line 435 == Outdated reference: A later version (-04) exists of draft-ietf-manet-olsrv2-sec-threats-02 -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) -- Obsolete informational reference (is this intentional?): RFC 6982 (Obsoleted by RFC 7942) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 5 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: December 10, 2016 University of Nantes 6 June 8, 2016 8 Multi-path Extension for the Optimized Link State Routing Protocol 9 version 2 (OLSRv2) 10 draft-ietf-manet-olsrv2-multipath-09 12 Abstract 14 This document specifies a multi-path 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 December 10, 2016. 36 Copyright Notice 38 Copyright (c) 2016 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 . . . . . . . . . . . . . . . . . . . 5 57 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 58 5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 7 59 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 7 60 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 8 61 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 8 62 6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . . 8 63 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 8 64 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 9 65 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 9 66 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 9 67 7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 9 68 7.2. Multi-path Routing Set . . . . . . . . . . . . . . . . . . 9 69 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 10 70 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 10 71 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 11 72 8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 11 73 8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 11 74 8.5. Multi-path Calculation . . . . . . . . . . . . . . . . . . 12 75 8.5.1. Requirements of Multi-path Calculation . . . . . . . . 12 76 8.5.2. Multi-path Dijkstra Algorithm . . . . . . . . . . . . 13 77 8.6. Multi-path Routing Set Updates . . . . . . . . . . . . . . 14 78 8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 15 79 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 15 80 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 16 81 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 16 82 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 17 83 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 17 84 11. Security Considerations . . . . . . . . . . . . . . . . . . . 17 85 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 86 12.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 18 87 12.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 18 88 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19 89 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 90 14.1. Normative References . . . . . . . . . . . . . . . . . . . 19 91 14.2. Informative References . . . . . . . . . . . . . . . . . . 20 92 Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 21 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 95 1. Introduction 97 The Optimized Link State Routing Protocol version 2 (OLSRv2) 98 [RFC7181] is a proactive link state protocol designed for use in 99 mobile ad hoc networks (MANETs). It generates routing messages 100 periodically to create and maintain a Routing Set, which contains 101 routing information to all the possible destinations in the routing 102 domain. For each destination, there exists a unique Routing Tuple, 103 which indicates the next hop to reach the destination. 105 This document specifies an extension of the OLSRv2 protocol 106 [RFC7181], to provide multiple disjoint paths when appropriate for a 107 source-destination pair. Because of the characteristics of MANETs 108 [RFC2501], especially the dynamic topology, having multiple paths is 109 helpful for increasing network throughput, improving forwarding 110 reliability and load balancing. 112 The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses 113 Multi-path Dijkstra algorithm by default to explore multiple disjoint 114 paths from a source router to a destination router based on the 115 topology information obtained through OLSRv2, and to forward the 116 datagrams in a load-balancing manner using source routing. MP-OLSRv2 117 is designed to be interoperable with OLSRv2. 119 1.1. Motivation and Experiments to Be Conducted 121 This document is an experimental extension of OLSRv2 that can 122 increase the data forwarding reliability in dynamic and high-load 123 MANET scenarios by transmitting datagrams over multiple disjoint 124 paths using source routing. This mechanism is used because: 126 o Disjoint paths can avoid single route failures. 128 o Transmitting datagrams through parallel paths can increase 129 aggregated throughput and provide load balancing. 131 o Certain scenarios require some routers must (or must not) be used. 133 o By having control of the paths at the source, the delay can be 134 provisioned. 136 o A very important application of this extension is in combination 137 with Forward Error Correction (FEC) coding. Because the packet 138 drop is normally bursty in a path (for example, due to route 139 failure), FEC coding is less effective in single path routing 140 protocols. By providing multiple disjoint paths, the application 141 of FEC coding with multi-path protocol is more resilient to 142 routing failures. 144 While in existing deployments, running code and simulations have 145 proven the interest of multi-path extension for OLSRv2 in certain 146 networks, more experiments and experiences are still needed to 147 understand the effects of the protocol. The multi-path extension for 148 OLSRv2 is expected to be revised and improved to the Standard Track, 149 once sufficient operational experience is obtained. Other than 150 general experiences including the protocol specification, 151 interoperability with original OLSRv2 implementations, the 152 experiences in the following aspects are highly appreciated: 154 o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) 155 to be used. This depends on the network topology and router 156 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 setting different sets of 163 metric functions. 165 o Use of other metric types. This multi-path extension can be used 166 not only for hop-count metric type, but also other metric types 167 that meet the requirement of OLSRv2, such as [RFC7779]. The 168 metric type used has also co-relation with the choice of metric 169 functions as indicated in the previous bullet point. 171 o The impact of partial topology information to the multi-path 172 calculation. OLSRv2 maintains a partial topology information base 173 to reduce protocol overhead. Although with existing experience, 174 multiple paths can be obtained even with such partial information, 175 the calculation might be impacted, depending on the MPR selection 176 algorithm used. 178 o Optimal choice of "key" routers for loose source routing. In some 179 cases, loose source routing is used to reduce overhead or for 180 interoperability with OLSRv2 routers. Other than the basic rules 181 defined in the following of this document, optimal choices of 182 routers to put in the loose source routing header can be further 183 studied. 185 o Different path-selection schedulers. By default, Round-Robin 186 scheduling is used to select a path to be used for datagrams. In 187 some scenarios, weighted scheduling can be considered: for 188 example, the paths with lower metrics (i.e., higher quality) can 189 transfer more datagrams compared to paths with higher metrics. 191 o The impacts of the delay variation due to multi-path routing. 192 [RFC2991] brings out some concerns of multi-path routing, 193 especially variable latencies. Although current experiment 194 results show that multi-path routing can reduce the jitter in 195 dynamic scenarios, some transport protocols or applications may be 196 sensitive to the datagram re-ordering. 198 o The disjoint multi-path protocol has interesting application with 199 Forward Error Correction (FEC) Coding, especially for services 200 like video/audio streaming. The combination of FEC coding 201 mechanisms and this extension is thus encouraged. By applying FEC 202 coding, the issue of packet re-ordering can be alleviated. 204 o Different algorithms to obtain multiple paths, other than the 205 default Multi-path Dijkstra algorithm introduced in this 206 specification. 208 o The use of multi-topology information. By using [RFC7722], 209 multiple topologies using different metric types can be obtained. 210 It is also encouraged to experiment the use of multiple metrics 211 for building multiple paths. 213 2. Terminology 215 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 216 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 217 "OPTIONAL" in this document are to be interpreted as described in 218 [RFC2119]. 220 This document uses the terminology and notation defined in [RFC5444], 221 [RFC6130], [RFC7181]. Additionally, it defines the following 222 terminology: 224 OLSRv2 Routing Process - The routing process based on [RFC7181], 225 without multi-path extension specified in this document. 227 MP-OLSRv2 Routing Process - The multi-path routing process based on 228 this specification as an extension to [RFC7181]. 230 3. Applicability Statement 232 As an extension of OLSRv2, this specification is applicable to MANETs 233 for which OLSRv2 is applicable (see [RFC7181]). It can operate on 234 single, or multiple interfaces, to discover multiple disjoint paths 235 from a source router to a destination router. 237 MP-OLSRv2 is specially designed for networks with dynamic topology 238 and low data rate links. By providing multiple paths, higher 239 aggregated throughput can be obtained, and the routing process is 240 more robust to packet loss. 242 In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily 243 replace OLSRv2 completely. The extension can be applied for certain 244 applications that are suitable for multi-path routing (mainly video 245 or audio streams), based on the information such as DiffServ Code 246 Point [RFC2474]. 248 Compared to OLSRv2, this extension does not introduce new message 249 type in the air. A new Message TLV type is introduced to identify 250 the routers that support forwarding based on source route header. It 251 is interoperable with OLSRv2 implementations that do not have this 252 extension. 254 MP-OLSRv2 forwards datagrams using the source routing header. For 255 IPv4 networks, implementation of loose source routing is required 256 following [RFC0791]. For IPv6 networks, implementation of strict 257 source routing is required following [RFC6554]. 259 4. Protocol Overview and Functioning 261 This specification requires OLSRv2 [RFC7181] to: 263 o Identify all the reachable routers in the network. 265 o Identify a sufficient subset of links in the networks, so that 266 routes can be calculated to all reachable destinations. 268 o Provide a Routing Set containing shortest routes from this router 269 to all destinations. 271 In addition, the MP-OLSRv2 Routing Process identifies the routers 272 that support source routing by adding a new Message TLV in HELLO and 273 TC messages. Based on the above information acquired, every MP- 274 OLSRv2 Routing Process is aware of a reduced topology map of the 275 network and the routers supporting source routing. 277 A Multi-path Routing Set containing the multi-path information is 278 maintained. It may either be proactively calculated or reactively 279 calculated: 281 o In the proactive approach, multiple paths to all possible 282 destinations are calculated and updated based on control message 283 exchange. The routes are thus available before they are actually 284 needed. 286 o In the reactive approach, a multi-path algorithm is invoked on 287 demand, i.e., only when there is a datagram to be sent from the 288 source to the destination, and there is no available routing tuple 289 in the Multi-path Routing Set. 291 Routers in the same network may choose either proactive or reactive 292 multi-path calculation independently according to their computation 293 resources. The Multi-path Dijkstra algorithm (defined in 294 Section 8.5) is introduced as the default algorithm to generate 295 multiple disjoint paths from a source to a destination, and such 296 information is kept in the Multi-path Routing Set. 298 The datagram is forwarded based on source routing. When there is a 299 datagram to be sent to a destination, the source router acquires a 300 path from the Multi-path Routing Set (MAY be Round-Robin, or other 301 scheduling algorithms). The path information is stored in the 302 datagram header as source routing header. 304 5. Parameters and Constants 306 In addition to the parameters and constants defined in [RFC7181], 307 this specification uses the parameters and constants described in 308 this section. 310 5.1. Router Parameters 312 NUMBER_OF_PATHS The number of paths desired by the router. 314 MAX_SRC_HOPS The maximum number of hops allowed to be put in the 315 source routing header. A value set zero means there is no 316 limitation on the maximum number of hops. In an IPv6 network, it 317 MUST be set to 0. In an IPv4 network, it MUST be strictly less 318 than 11. 320 CUTOFF_RATIO The ratio that defines the maximum metric of a path 321 compared to the shortest path kept in the OLSRv2 Routing Set. For 322 example, the metric to a destination is R_metric based on the 323 Routing Set. Then the maximum metric allowed for a path is 324 CUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be strictly greater 325 than 1. 327 SR_TC_INTERVAL The maximum time between the transmission of two 328 successive TC messages by a MP-OLSRv2 Routing Process. 330 SR_OLSR_HOLD_TIME It is the minimal time that a SR-OLSRv2 Router 331 Tuple SHOULD be kept in the SR-OLSRv2 Router Set. 333 6. Packets and Messages 335 This extension employs the routing control messages HELLO and TC 336 (Topology Control) as defined in OLSRv2 [RFC7181]. To support source 337 routing, a source routing header is added to each datagram routed by 338 this extension. Depending on the IP version used, the source routing 339 header is defined in this section. 341 6.1. HELLO and TC messages 343 HELLO and TC messages used by MP-OLSRv2 Routing Process share the 344 same format as defined in [RFC7181]. In addition, a new Message TLV 345 type is defined, to identify the originator of the HELLO or TC 346 message that supports source route forwarding. The new Message TLV 347 type is introduced for enabling MP-OLSRv2 as an extension of OLSRv2: 348 only the routers supporting source-route forwarding can be used in 349 the source routing header of a datagram, because adding a router that 350 does not understand the source routing header will cause routing 351 failure. 353 6.1.1. SOURCE_ROUTE TLV 355 SOURCE_ROUTE TLV is a Message TLV signalling that the message is 356 generated by a router that supports source-route forwarding. It can 357 be an MP-OLSRv2 Routing Process, or an OLSRv2 Routing Process that 358 supports source-route forwarding. The SOURCE_ROUTE TLV does not 359 include any value. 361 Every HELLO or TC message generated by a MP-OLSRv2 Routing Process 362 MUST have exactly one SOURCE_ROUTE TLV. 364 Every HELLO or TC message generated by an OLSRv2 Routing Process MAY 365 have one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process supports 366 source-route forwarding, and is willing to join the source route 367 generated by other MP-OLSRv2 Routing Processes. The existence of 368 SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing 369 Process, i.e., either it adds SOURCE_ROUTE TLV to all its HELLO/TC 370 messages, or it does not add SOURCE_ROUTE TLV to any HELLO/TC 371 message. 373 6.2. Datagram 374 6.2.1. Source Routing Header in IPv4 376 In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs 377 loose source routing header, as defined in [RFC0791]. It exists as 378 an option header, with option class 0, and option number 3. 380 The source route information is kept in the "route data" field of the 381 loose source route header. 383 6.2.2. Source Routing Header in IPv6 385 In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the 386 source routing header as defined in [RFC6554], with IPv6 Routing Type 387 3. 389 The source route information is kept in the "Addresses" field of the 390 routing header. 392 7. Information Bases 394 Each MP-OLSRv2 routing process maintains the information bases as 395 defined in [RFC7181]. Additionally, a Multipath Information base is 396 used for this specification. It includes the protocol sets as 397 defined below. 399 7.1. SR-OLSRv2 Router Set 401 The SR-OLSRv2 Router Set records the routers that support source- 402 route forwarding. This includes routers that run MP-OLSRv2 Routing 403 Process, or OLSRv2 Routing Process with source-route forwarding 404 support. The set consists of SR-OLSRv2 Router Tuples: 406 (SR_OLSR_addr, SR_OLSR_valid_time) 408 where: 410 SR_OLSR_addr - it is the network address of the router that 411 supports source-route forwarding; 413 SR_OLSR_valid_time - it is the time until which the SR-OLSRv2 414 Router Tuples is considered valid. 416 7.2. Multi-path Routing Set 418 The Multi-path Routing Set records the full path information of 419 different paths to the destination. It consists of Multi-path 420 Routing Tuples: 422 (MR_dest_addr, MR_path_set) 424 where: 426 MR_dest_addr - it is the network address of the destination, either 427 the network address of an interface of a destination router or the 428 network address of an attached network; 430 MP_path_set - it contains the multiple paths to the destination. 431 It consists of a set of Path Tuples. 433 Each Path Tuple is defined as: 435 (PT_metric, PT_address[1], PT_address[2], ..., PT_address[n]) 437 where: 439 PT_metric - the metric of the path to the destination, measured in 440 LINK_METRIC_TYPE defined in [RFC7181]; 442 PT_address[1...n] - the addresses of intermediate routers to be 443 visited numbered from 1 to n. 445 8. Protocol Details 447 This protocol is based on OLSRv2, and extended to discover multiple 448 disjoint paths from a source router to a destination router. It 449 retains the basic routing control packets formats and processing of 450 OLSRv2 to obtain topology information of the network. The main 451 differences between OLSRv2 routing process are the datagram 452 processing at the source router and datagram forwarding. 454 8.1. HELLO and TC Message Generation 456 HELLO messages are generated according to the Section 15.1 of 457 [RFC7181]. 459 TC message are generated according to the Section 16.1 of [RFC7181]. 460 As least one TC message MUST be generated by an MP-OLSRv2 Routing 461 Process during SR_TC_INTERVAL. Please note that the TC message 462 generation based on SR_TC_INTERVAL does not replace the ordinary TC 463 message generation specified in [RFC7181] and does not carry any 464 address. This is due to the fact that not all routers will generate 465 TC messages based on OLSRv2. The TC generation based on 466 SR_TC_INTERVAL serves for those routers to advertise SOURCE_ROUTE TLV 467 so that the other routers can be aware of the source-route enabled 468 routers so as to be used as destinations of multipath routing. The 469 SR_TC_INTERVAL is set to a longer value than TC_INTERVAL. 471 For both TC and HELLO messages, a single Message TLV with Type := 472 SOURCE_ROUTE MUST be added to the message. 474 8.2. HELLO and TC Message Processing 476 HELLO and TC messages are processed according to the section 15.3 and 477 16.3 of [RFC7181]. 479 For every HELLO or TC message received, if there is a Message TLV 480 with Type := SOURCE_ROUTE, create or update (if the tuple exists 481 already) the SR-OLSR Router Tuple with 483 o SR_OLSR_addr := originator of the HELLO or TC message 485 o SR_OLSR_valid_time := current_time + SR_OLSR_HOLD_TIME. 487 8.3. MPR Selection 489 Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs 490 following Section 18 of [RFC7181]. In a mixed network with OLSRv2- 491 only routers, the following considerations apply when calculating 492 MPRs: 494 o MP-OLSR routers SHOULD be preferred as routing MPRs. 496 o The number of routing MPRs that run MP-OLSR Routing Process MUST 497 be equal or greater than NUMBER_OF_PATHS if there are enough MP- 498 OLSR symmetric neighbors. Or else, all the MP-OLSR routers are 499 selected as routing MPRs. 501 8.4. Datagram Processing at the MP-OLSRv2 Originator 503 If datagrams without source routing header need to be forwarded using 504 multiple paths (for example, based on the information of DiffServ 505 Code Point [RFC2474]), the MP-OLSRv2 routing process will try to find 506 the Multi-path Routing Tuple where: 508 o MR_dest_addr = destination of the datagram 510 If no matching Multi-path Routing Tuple is found and the Multi-path 511 Routing Set is maintained proactively, it indicates that there is no 512 route available to the desired destination. The datagram is 513 discarded. 515 If no matching Multi-path Routing Tuple is found and the Multi-path 516 Routing Set is maintained reactively, the multi-path algorithm 517 defined in Section 8.5 is invoked, to calculate the Multi-path 518 Routing Tuple to the destination. If the calculation does not return 519 any Multi-path Routing Tuple, the following steps are aborted and the 520 datagram is forwarded following OLSRv2 routing process. 522 If a matching Multi-path Routing Tuple is obtained, the Path Tuples 523 of the Multi-path Routing Tuple are applied to the datagrams using 524 Round-robin scheduling. For example, they are 2 path tuples (Path-1, 525 Path-2) for destination router D. A series of datagrams (Packet-1, 526 Packet-2, Packet-3, ... etc.) are to be sent router D. Path-1 is then 527 chosen for Packet-1, Path-2 for Packet-2, Path-1 for Packet 3, etc. 529 The addresses in PT_address[1...n] of the chosen Path Tuple are thus 530 added to the datagram header as the source routing header. For IPv6 531 networks, strict source routing is used, thus all the intermediate 532 routers in the path are stored in the source routing header following 533 [RFC6554]. For IPv4 networks, loose source routing is used, with 534 following rules: 536 o Only the addresses that exist in SR-OLSR Router Set can be added 537 to the source routing header. 539 o If the length of the path (n) is greater than MAX_SRC_HOPS, only 540 the "key" routers in the path are kept. The key routers can be 541 chosen based on the capacity of the routers (e.g., battery life) 542 or the router's willingness in forwarding data. If no such 543 information is available, the key routers are uniformly chosen in 544 the path. 546 o The routers that are considered not appropriate for forwarding 547 indicated by external policies should be avoided. 549 8.5. Multi-path Calculation 551 8.5.1. Requirements of Multi-path Calculation 553 The Multi-path Routing Set maintains the information of multiple 554 paths the the destination. The tuples are generated based on a 555 multi-path algorithm. 557 For each path to a destination, the algorithm must provide: 559 o The metric of the path to the destination, 561 o The list of intermediate routers on the path. 563 For IPv6 networks, as strict source routing is used, only the routers 564 that exist in SR-OLSRv2 Router Set are considered in the path 565 calculation, i.e., only the source-routing supported routers can 566 exist in the path. 568 After the calculation of multiple paths, the metric of paths (denoted 569 c_i for path i) to the destination is compared to the R_metric of the 570 OLSRv2 Routing Tuple ([RFC7181]) to the same destination. If the 571 metric c_i is greater than R_metric * CUTOFF_RATIO, the corresponding 572 path i SHOULD NOT be used. If less than 2 paths are found with 573 metrics less than R_metric * CUTOFF_RATIO, the router SHOULD fall 574 back to OLSRv2 Routing Process without using multipath routing. This 575 can happen if there are too much OLSRv2-only routers in the network, 576 and requiring multipath routing brutally may result in inferior 577 paths. 579 By invoking the multi-path algorithm, NUMBER_OF_PATHS paths are 580 obtained and added to the Multi-path Routing Set, by creating a 581 Multi-path Routing Tuple with: 583 o MR_dest_addr := destination of the datagram 585 o A MP_path_set with calculated Path Tuples. Each Path Tuple 586 corresponds to a path obtained in Multi-path Dijkstra algorithm, 587 with PT_metric := metric of the calculated path and 588 PT_address[1...n] := list of intermediate routers. 590 8.5.2. Multi-path Dijkstra Algorithm 592 This section introduces Multi-path Dijkstra Algorithm as a default 593 algorithm. It tries to obtain disjoint paths when appropriate, but 594 does not guarantee strict disjoint paths. The use of other 595 algorithms is not prohibited, as long as the requirements described 596 in Section 8.5.1 are met. Using different multi-path algorithms will 597 not impact the interoperability. 599 The general principle of the Multi-path Dijkstra Algorithm is at step 600 i to look for the shortest path P[i] to the destination d. Compared 601 to the original Dijkstra algorithm, the main modification consists in 602 adding two incremental functions named metric functions fp and fe in 603 order to prevent the next steps resulting in similar paths: 605 o fp(c) is used to increase metrics of arcs belonging to the 606 previous path P[i-1] (with i>1), where c is the value of the 607 previous metric. This encourages future paths to use different 608 arcs but not different vertices. 610 o fe(c) is used to increase metrics of the arcs that lead to 611 intermediate vertices of the previous path P[i-1] (with i>1), 612 where c is the value of the previous metric. The "lead to" means 613 that only one vertex of the arc belongs to the previous path 614 P[i-1], while the the other vertex is not. The "intermediate" 615 means that the source and destination vertices are not considered. 617 Considering the simple example in Figure 1: a path P[i] S--A--D is 618 obtained at step i. For the next step, the metric of link S--A and 619 A--D are to be increased using fp(c), because they belong to the path 620 P[i]. A--B is to be increased using fe(c), because A is an 621 intermediate vetex of path P[i], and B is not part of P[i]. B--D is 622 unchanged. 624 B 625 / \ 626 / \ 627 / \ 628 S---------A-----------D 630 Figure 1 632 It is possible to choose different fp and fe to get link-disjoint 633 paths or node-disjoint paths as desired. A recommendation of 634 configuration of fp and fe is given in Section 9. 636 To get NUMBER_OF_PATHS different paths, for each path P[i] (i = 1, 637 ..., NUMBER_OF_PATHS) do: 639 1. Run Dijkstra algorithm to get the shortest path P[i] for the 640 destination d. 642 2. Apply metric function fp to the metric of links (in both 643 directions) in P[i]. 645 3. Apply metric function fe to the metric of links (in both 646 directions) that lead to routers used in P[i]. 648 A simple example of Multi-path Dijkstra Algorithm is illustrated in 649 Appendix A. 651 8.6. Multi-path Routing Set Updates 653 The Multi-path Routing Set MUST be updated when the Local Information 654 Base, the Neighborhood Information Base, or the Topology Information 655 Base indicate a change (including of any potentially used outgoing 656 neighbor metric values) of the known symmetric links and/or attached 657 networks in the MANET, hence changing the Topology Graph, as 658 described in section 17.7 of [RFC7181]. How the Multi-path Routing 659 Set is updated depends on the set is maintained reactively or 660 proactively: 662 o In reactive mode, all the tuples in the Multi-path Routing Set are 663 removed. 665 o In proactive mode, the route to all the destinations are updated 666 according to Section 8.5. 668 8.7. Datagram Forwarding 670 In IPv4 networks, datagrams are forwarded using loose source routing 671 as specified in Section 3.1 of [RFC0791]. 673 In IPv6 networks, datagrams are forwarded using strict source routing 674 as specified in Section 4.2 of [RFC6554]. 676 9. Configuration Parameters 678 This section gives default values and guideline for setting 679 parameters defined in Section 5. Network administrators may wish to 680 change certain, or all the parameters for different network 681 scenarios. As an experimental track protocol, the users of this 682 protocol are also encouraged to explore different parameter setting 683 in various network environments, and provide feedback. 685 o NUMBER_OF_PATHS := 3. This parameter defines the number of 686 parallel paths used in datagram forwarding. Setting it to one 687 makes the specification identical to OLSRv2. Setting it to too 688 large values may lead to unnecessary computational overhead and 689 inferior paths. 691 o MAX_SRC_HOPS := 10, for IPv4 networks. For IPv6 networks, it MUST 692 be set to 0, i.e., no constraint on maximum number of hops. 694 o CUTOFF_RATIO := 1.5. It MUST be strictly greater than 1. 696 o SR_TC_INTERVAL := 10 x TC_INTERVAL. It SHOULD be significantly 697 greater than TC_INTERVAL to reduce unnecessary TC message 698 generations. 700 o SR_OLSR_HOLD_TIME := 3 x SR_TC_INTERVAL. It MUST be greater than 701 SR_TC_INTERVAL. 703 If Multi-path Dijkstra Algorithm is applied: 705 o fp(c) := 4*c, where c is the original metric of the link. 707 o fe(c) := 2*c, where c is the original metric of the link. 709 The setting of metric functions fp and fc defines the preference of 710 obtained multiple disjoint paths. If id is the identity function, 711 i.e., fp(c)=c, 3 cases are possible: 713 o if id=fe. 863 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 864 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 865 RFC2119, March 1997, 866 . 868 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 869 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 870 Format", RFC 5444, DOI 10.17487/RFC5444, February 2009, 871 . 873 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 874 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 875 RFC 6130, DOI 10.17487/RFC6130, April 2011, 876 . 878 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 879 Routing Header for Source Routes with the Routing Protocol 880 for Low-Power and Lossy Networks (RPL)", RFC 6554, 881 DOI 10.17487/RFC6554, March 2012, 882 . 884 [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 885 "The Optimized Link State Routing Protocol Version 2", 886 RFC 7181, DOI 10.17487/RFC7181, April 2014, 887 . 889 [RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity 890 Protection for the Neighborhood Discovery Protocol (NHDP) 891 and Optimized Link State Routing Protocol Version 2 892 (OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014, 893 . 895 14.2. Informative References 897 [ADHOC11] Yi, J., Adnane, A-H., David, S., and B. Parrein, 898 "Multipath optimized link state routing for mobile ad hoc 899 networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, 900 January, 2011. 902 [GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria, 903 "Experimental performance comparison of single-path and 904 multipath routing in VANETs", In Global Information 905 Infrastructure and Networking Symposium (GIIS), 2014 , 906 vol. 1, no. 6, pp. 15-19, 2014. 908 [I-D.ietf-manet-olsrv2-sec-threats] 909 Clausen, T., Herberg, U., and J. Yi, "Security Threats for 910 the Optimized Link State Routing Protocol version 2 911 (OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-02 (work in 912 progress), May 2016. 914 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 915 (IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460, 916 December 1998, . 918 [RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black, 919 "Definition of the Differentiated Services Field (DS 920 Field) in the IPv4 and IPv6 Headers", RFC 2474, 921 DOI 10.17487/RFC2474, December 1998, 922 . 924 [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking 925 (MANET): Routing Protocol Performance Issues and 926 Evaluation Considerations", RFC 2501, DOI 10.17487/ 927 RFC2501, January 1999, 928 . 930 [RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and 931 Multicast Next-Hop Selection", RFC 2991, DOI 10.17487/ 932 RFC2991, November 2000, 933 . 935 [RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation 936 of Type 0 Routing Headers in IPv6", RFC 5095, 937 DOI 10.17487/RFC5095, December 2007, 938 . 940 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 941 Code: The Implementation Status Section", RFC 6982, 942 DOI 10.17487/RFC6982, July 2013, 943 . 945 [RFC7722] Dearlove, C. and T. Clausen, "Multi-Topology Extension for 946 the Optimized Link State Routing Protocol Version 2 947 (OLSRv2)", RFC 7722, DOI 10.17487/RFC7722, December 2015, 948 . 950 [RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric 951 Based on Packet Sequence Numbers for Optimized Link State 952 Routing Version 2 (OLSRv2)", RFC 7779, DOI 10.17487/ 953 RFC7779, April 2016, 954 . 956 [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, 957 "Simulation and performance analysis of MP-OLSR for mobile 958 ad hoc networks", In Proceeding of IEEE Wireless 959 Communications and Networking Conference, 2008. 961 Appendix A. Examples of Multi-path Dijkstra Algorithm 963 This appendix gives two examples of multi-path Dijkstra algorithm. 965 A network topology is depicted in Figure 2. 967 .-----A-----(2) 968 (1) / \ \ 969 / / \ \ 970 S (2) (1) D 971 \ / \ / 972 (1) / \ / (2) 973 B----(3)----C 975 Figure 2 977 The capital letters are name of routers. An arbitrary metric with 978 value between 1 and 3 is used. The initial metrics of all the links 979 are indicated in the parenthesis. The incremental functions fp(c)=4c 980 and fe(c)=2c are used in this example. Two paths from router S to 981 router D are demanded. 983 On the first run of the Dijkstra algorithm, the shortest path S->A->D 984 with metric 3 is obtained. 986 The incremental function fp is applied to increase the metric of the 987 link S-A and A-D. fe is applied to increase the metric of the link 988 A-B and A-C. Figure 3 shows the link metrics after the punishment. 990 .-----A-----(8) 991 (4) / \ \ 992 / / \ \ 993 S (4) (2) D 994 \ / \ / 995 (1) / \ / (2) 996 B----(3)----C 998 Figure 3 1000 On the second run of the Dijkstra algorithm, the second path 1001 S->B->C->D with metric 6 is obtained. 1003 As mentioned in Section 8.5, the Multi-path Dijkstra Algorithm does 1004 not guarantee strict disjoint path to avoid choosing inferior paths. 1005 For example, given the topology in Figure 4, two paths from node S to 1006 D are desired. On the top of the figure, there is a high cost path 1007 between S and D. 1009 If a algorithm tries to obtain strict disjoint paths, the two paths 1010 obtained will be S--B--D and S--(high cost path)--D, which are 1011 extremely unbalanced. It is undesired because it will cause huge 1012 delay variance between the paths. By using the Multi-path Dijkstra 1013 algorithm, which is based on the punishing scheme, S--B--D and 1014 S--B--C--D will be obtained. 1016 --high cost path- 1017 / \ 1018 / \ 1019 S----B--------------D 1020 \ / 1021 \---C-----/ 1023 Figure 4 1025 Authors' Addresses 1027 Jiazi Yi 1028 Ecole Polytechnique 1029 91128 Palaiseau Cedex, 1030 France 1032 Phone: +33 (0) 1 77 57 80 85 1033 Email: jiazi@jiaziyi.com 1034 URI: http://www.jiaziyi.com/ 1036 Benoit Parrein 1037 University of Nantes 1038 IRCCyN lab - IVC team 1039 Polytech Nantes, rue Christian Pauc, BP50609 1040 44306 Nantes cedex 3 1041 France 1043 Phone: +33 (0) 2 40 68 30 50 1044 Email: Benoit.Parrein@polytech.univ-nantes.fr 1045 URI: http://www.irccyn.ec-nantes.fr/~parrein