idnits 2.17.1 draft-ietf-manet-olsrv2-multipath-11.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 == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: TC message are generated according to Section 16.1 of [RFC7181]. As least one TC message MUST be generated by an MP-OLSRv2 Routing Process during SR_TC_INTERVAL. The TC message generation based on SR_TC_INTERVAL does not replace the ordinary TC message generation specified in [RFC7181] and MUST not carry any advertised neighbor addresses. This is due to the fact that not all routers will generate TC messages based on OLSRv2. The TC generation based on SR_TC_INTERVAL serves for those routers to advertise SOURCE_ROUTE TLV so that the other routers can be aware of the source-route enabled routers so as to be used as destinations of multipath routing. The SR_TC_INTERVAL is set to a longer value than TC_INTERVAL. -- The document date (July 25, 2016) is 2804 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 465 -- Looks like a reference, but probably isn't: '2' on line 465 == 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 (~~), 3 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: January 26, 2017 University of Nantes 6 July 25, 2016 8 Multi-path Extension for the Optimized Link State Routing Protocol 9 version 2 (OLSRv2) 10 draft-ietf-manet-olsrv2-multipath-11 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 January 26, 2017. 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 . . . . . . . . . . . . . . . . . . . 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. Multi-path 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. Multi-path Calculation . . . . . . . . . . . . . . . . . . 13 75 8.5.1. Requirements of Multi-path Calculation . . . . . . . . 13 76 8.5.2. Multi-path Dijkstra Algorithm . . . . . . . . . . . . 14 77 8.6. Multi-path Routing Set Updates . . . . . . . . . . . . . . 15 78 8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 16 79 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 16 80 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 17 81 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 18 82 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 18 83 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 18 84 11. Security Considerations . . . . . . . . . . . . . . . . . . . 18 85 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 86 12.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 19 87 12.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 19 88 12.3. Routing Type . . . . . . . . . . . . . . . . . . . . . . . 20 89 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 90 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 91 14.1. Normative References . . . . . . . . . . . . . . . . . . . 20 92 14.2. Informative References . . . . . . . . . . . . . . . . . . 21 93 Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 23 94 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 96 1. Introduction 98 The Optimized Link State Routing Protocol version 2 (OLSRv2) 99 [RFC7181] is a proactive link state protocol designed for use in 100 mobile ad hoc networks (MANETs). It generates routing messages 101 periodically to create and maintain a Routing Set, which contains 102 routing information to all the possible destinations in the routing 103 domain. For each destination, there exists a unique Routing Tuple, 104 which indicates the next hop to reach the destination. 106 This document specifies an extension of the OLSRv2 protocol 107 [RFC7181], to provide multiple disjoint paths when appropriate for a 108 source-destination pair. Because of the characteristics of MANETs 109 [RFC2501], especially the dynamic topology, having multiple paths is 110 helpful for increasing network throughput, improving forwarding 111 reliability and load balancing. 113 The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses 114 Multi-path Dijkstra algorithm by default to explore multiple disjoint 115 paths from a source router to a destination router based on the 116 topology information obtained through OLSRv2, and to forward the 117 datagrams in a load-balancing manner using source routing. MP-OLSRv2 118 is designed to be interoperable with OLSRv2. 120 1.1. Motivation and Experiments to Be Conducted 122 This document is an experimental extension of OLSRv2 that can 123 increase the data forwarding reliability in dynamic and high-load 124 MANET scenarios by transmitting datagrams over multiple disjoint 125 paths using source routing. This mechanism is used because: 127 o Disjoint paths can avoid single route failures. 129 o Transmitting datagrams through parallel paths can increase 130 aggregated throughput. 132 o Some scenarios may require some routers must (or must not) be 133 used. 135 o Having control of the paths at the source benefits the load 136 balancing and traffic engineering. 138 o An application of this extension is in combination with Forward 139 Error Correction (FEC) coding applied across packets (erasure 140 coding). Because the packet drop is normally bursty in a path 141 (for example, due to route failure), erasure coding is less 142 effective in single path routing protocols. By providing multiple 143 disjoint paths, the application of erasure coding with multi-path 144 protocol is more resilient to routing failures. 146 While in existing deployments, running code and simulations have 147 proven the interest of multi-path extension for OLSRv2 in certain 148 networks, more experiments and experiences are still needed to 149 understand the effects of the protocol. The multi-path extension for 150 OLSRv2 is expected to be revised and improved to the Standard Track, 151 once sufficient operational experience is obtained. Other than 152 general experiences including the protocol specification and 153 interoperability with original OLSRv2 implementations, the 154 experiences in the following aspects are highly appreciated: 156 o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) 157 to be used. This depends on the network topology and router 158 density. 160 o Optimal values used in the metric functions. Metric functions are 161 applied to increase the metric of used links and nodes so as to 162 obtain disjoint paths. What kind of disjointness is desired 163 (node-disjoint or link-disjoint) may depend on the layer 2 164 protocol used, and can be achieved by setting different sets of 165 metric functions. 167 o Use of different metric types. This multi-path extension can be 168 used with metric types that meet the requirement of OLSRv2, such 169 as [RFC7779]. The metric type used has also impact to the choice 170 of metric functions as indicated in the previous bullet point. 172 o The impact of partial topology information to the multi-path 173 calculation. OLSRv2 maintains a partial topology information base 174 to reduce protocol overhead. Although with existing experience, 175 multiple paths can be obtained even with such partial information, 176 the calculation might be impacted, depending on the MPR selection 177 algorithm used. 179 o Optimal choice of "key" routers for IPv4 loose source routing. In 180 some cases, loose source routing is used to reduce overhead or for 181 interoperability with OLSRv2 routers. Other than the basic rules 182 defined in the following of this document, optimal choices of 183 routers to put in the loose source routing header can be further 184 studied. 186 o Different path-selection schedulers. By default, Round-Robin 187 scheduling is used to select a path to be used for datagrams. In 188 some scenarios, weighted scheduling can be considered: for 189 example, the paths with lower metrics (i.e., higher quality) can 190 transfer more datagrams compared to paths with higher metrics. 192 o The impacts of the delay variation due to multi-path routing. 193 [RFC2991] brings out some concerns of multi-path routing, 194 especially variable latencies. Although current experiment 195 results show that multi-path routing can reduce the jitter in 196 dynamic scenarios, some transport protocols or applications may be 197 sensitive to the datagram re-ordering. 199 o The disjoint multi-path protocol has interesting application with 200 erasure coding, especially for services like video/audio 201 streaming. The combination of erasure coding mechanisms and this 202 extension is thus encouraged. 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 Although there is no work defining how this extension can make use 211 of the multi-topology information base yet, it is encouraged to 212 experiment with the use of multiple metrics for building multiple 213 paths. 215 2. Terminology 217 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 218 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 219 "OPTIONAL" in this document are to be interpreted as described in 220 [RFC2119]. 222 This document uses the terminology and notation defined in [RFC5444], 223 [RFC6130], [RFC7181]. Additionally, it defines the following 224 terminology: 226 OLSRv2 Routing Process - The routing process based on [RFC7181], 227 without multi-path extension specified in this document. 229 MP-OLSRv2 Routing Process - The multi-path routing process based on 230 this specification as an extension to [RFC7181]. 232 3. Applicability Statement 234 As an extension of OLSRv2, this specification is applicable to MANETs 235 for which OLSRv2 is applicable (see [RFC7181]). It can operate on 236 single, or multiple interfaces, to discover multiple disjoint paths 237 from a source router to a destination router. MP-OLSRv2 is designed 238 for networks with dynamic topology by avoiding single route failure. 239 It can also provide higher aggregated throughput and load balancing. 241 In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily 242 replace OLSRv2 completely. The extension can be applied for certain 243 applications that are suitable for multi-path routing (mainly video 244 or audio streams), based on the information such as DiffServ Code 245 Point [RFC2474]. 247 Compared to OLSRv2, this extension does not introduce new message 248 type. A new Message TLV Type is introduced to identify the routers 249 that support forwarding based on source route header. It is 250 interoperable with OLSRv2 implementations that do not have this 251 extension. 253 MP-OLSRv2 supports two different, but interoperable multi-path 254 calculation approaches: proactive and reactive. In the proactive 255 calculation, the paths to all the destinations are calculated before 256 needed. In the reactive calculation, only the paths to desired 257 destination(s) are calculated on demand. The proactive approach 258 requires more computational resources than the reactive one. The 259 reactive approach requires the IP forwarding plane to trigger the 260 multi-path calculation. 262 MP-OLSRv2 forwards datagrams using the source routing header. As 263 there are multiple paths to each destination, MP-OLSRv2 requires the 264 IP forwarding plane to be able to choose which source route to be put 265 in the source routing header based on the path scheduler defined by 266 MP-OLSRv2. For IPv4 networks, implementation of loose source routing 267 is required following [RFC0791]. For IPv6 networks, implementation 268 of strict source routing is required following the source routing 269 header generation and processing defined in [RFC6554]. 271 4. Protocol Overview and Functioning 273 This specification uses OLSRv2 [RFC7181] to: 275 o Identify all the reachable routers in the network. 277 o Identify a sufficient subset of links in the networks, so that 278 routes can be calculated to all reachable destinations. 280 o Provide a Routing Set containing shortest routes from this router 281 to all destinations. 283 In addition, the MP-OLSRv2 Routing Process identifies the routers 284 that support source routing by adding a new Message TLV in HELLO and 285 TC messages. Based on the above information acquired, every MP- 286 OLSRv2 Routing Process is aware of a reduced topology map of the 287 network and the routers supporting source routing. 289 A Multi-path Routing Set containing the multi-path information is 290 maintained. It may either be proactively calculated or reactively 291 calculated: 293 o In the proactive approach, multiple paths to all possible 294 destinations are calculated and updated based on control message 295 exchange. The routes are thus available before they are actually 296 needed. 298 o In the reactive approach, a multi-path algorithm is invoked on 299 demand, i.e., only when there is a datagram to be sent from the 300 source to the destination, and there is no available Routing Tuple 301 in the Multi-path Routing Set. This requires the IP forwarding 302 information base to trigger the multi-path calculation specified 303 in Section 8.5 when no Multi-path Routing Tuple is available. The 304 reactive operation is local in the router and no message 305 transmission delay is introduced. 307 Routers in the same network may choose either proactive or reactive 308 multi-path calculation independently according to their computation 309 resources. The Multi-path Dijkstra algorithm (defined in 310 Section 8.5) is introduced as the default algorithm to generate 311 multiple disjoint paths from a source to a destination, and such 312 information is kept in the Multi-path Routing Set. 314 The datagram is forwarded based on source routing. When there is a 315 datagram to be sent to a destination, the source router acquires a 316 path from the Multi-path Routing Set (MAY be Round-Robin, or other 317 scheduling algorithms). The path information is stored in the 318 datagram header as source routing header. 320 5. Parameters and Constants 322 In addition to the parameters and constants defined in [RFC7181], 323 this specification uses the parameters and constants described in 324 this section. 326 5.1. Router Parameters 327 NUMBER_OF_PATHS The number of paths desired by the router. 329 MAX_SRC_HOPS The maximum number of hops allowed to be put in the 330 source routing header. A value set zero means there is no 331 limitation on the maximum number of hops. In an IPv6 network, it 332 MUST be set to 0 because [RFC6554] supports only strict source 333 routing. All the intermediate routers MUST be included in the 334 source routing header, which makes the number of hops to be kept a 335 variable. In an IPv4 network, it MUST be strictly less than 11 336 and greater than 0 due to the limit of the IPv4 header. 338 CUTOFF_RATIO The ratio that defines the maximum metric of a path 339 compared to the shortest path kept in the OLSRv2 Routing Set. For 340 example, the metric to a destination is R_metric based on the 341 Routing Set. Then the maximum metric allowed for a path is 342 CUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be greater than or 343 equal to 1. Note that setting the value to 1 means looking for 344 equal length paths, which may not be possible in some networks. 346 SR_TC_INTERVAL The maximum time between the transmission of two 347 successive TC messages by a MP-OLSRv2 Routing Process. 349 SR_HOLD_TIME_MULTIPLIER The multiplier to calculate the minimal time 350 that a SR-OLSRv2 Router Tuple SHOULD be kept in the SR-OLSRv2 351 Router Set. 353 6. Packets and Messages 355 This extension employs the routing control messages HELLO and TC 356 (Topology Control) as defined in OLSRv2 [RFC7181] to obtain network 357 topology information. For the datagram, to support source routing, a 358 source routing header is added to each datagram routed by this 359 extension. Depending on the IP version used, the source routing 360 header is defined in this section. 362 6.1. HELLO and TC messages 364 HELLO and TC messages used by MP-OLSRv2 Routing Process use the same 365 format as defined in [RFC7181]. In addition, a new Message TLV type 366 is defined, to identify the originator of the HELLO or TC message 367 that supports source route forwarding. The new Message TLV type is 368 introduced for enabling MP-OLSRv2 as an extension of OLSRv2: only the 369 routers supporting source-route forwarding can be used in the source 370 routing header of a datagram, because adding a router that does not 371 understand the source routing header will cause routing failure. 373 6.1.1. SOURCE_ROUTE TLV 375 SOURCE_ROUTE TLV is a Message TLV signalling that the message is 376 generated by a router that supports source-route forwarding. It can 377 be an MP-OLSRv2 Routing Process, or an OLSRv2 Routing Process that 378 supports source-route forwarding. 380 Every HELLO or TC message generated by a MP-OLSRv2 Routing Process 381 MUST have exactly one SOURCE_ROUTE TLV. 383 +--------------+-----------+----------------------------------------+ 384 | Type | Value | Value | 385 | | Length | | 386 +--------------+-----------+----------------------------------------+ 387 | SOURCE_ROUTE | 1 octet | The parameter SR_HOLD_TIME_MULTIPLIER | 388 | | | (unsigned integer) | 389 +--------------+-----------+----------------------------------------+ 391 Table 1: SOURCE_ROUTE TLV Definition 393 Every HELLO or TC message generated by an OLSRv2 Routing Process MAY 394 have one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process supports 395 source-route forwarding, and is willing to join the source route 396 generated by other MP-OLSRv2 Routing Processes. The existence of 397 SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing 398 Process, i.e., either it adds SOURCE_ROUTE TLV to all its HELLO/TC 399 messages, or it does not add SOURCE_ROUTE TLV to any HELLO/TC 400 messages. 402 6.2. Datagram 404 6.2.1. Source Routing Header in IPv4 406 In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs 407 loose source routing header, as defined in [RFC0791]. It exists as 408 an option header, with option class 0, and option number 3. 410 The source route information is kept in the "route data" field of the 411 loose source route header. 413 6.2.2. Source Routing Header in IPv6 415 In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the 416 source routing header as defined in section 3 of [RFC6554], but with 417 IPv6 Routing Type 254 (experimental). 419 The source route information is kept in the "Addresses" field of the 420 routing header. 422 7. Information Bases 424 Each MP-OLSRv2 routing process maintains the information bases as 425 defined in [RFC7181]. Additionally, a Multipath Information Base is 426 used for this specification. It includes the protocol sets as 427 defined below. 429 7.1. SR-OLSRv2 Router Set 431 The SR-OLSRv2 Router Set records the routers that support source- 432 route forwarding. This includes routers that run MP-OLSRv2 Routing 433 Process, or OLSRv2 Routing Process with source-route forwarding 434 support. The set consists of SR-OLSRv2 Router Tuples: 436 (SR_addr, SR_time) 438 where: 440 SR_addr - is the network address of the router that supports 441 source-route forwarding; 443 SR_time - is the time until which the SR-OLSRv2 Router Tuple is 444 considered valid. 446 7.2. Multi-path Routing Set 448 The Multi-path Routing Set records the full path information of 449 different paths to the destination. It consists of Multi-path 450 Routing Tuples: 452 (MR_dest_addr, MR_path_set) 454 where: 456 MR_dest_addr - is the network address of the destination, either 457 the network address of an interface of a destination router or the 458 network address of an attached network; 460 MP_path_set - contains the multiple paths to the destination. It 461 consists of a set of Path Tuples. 463 Each Path Tuple is defined as: 465 (PT_metric, PT_address[1], PT_address[2], ..., PT_address[n]) 467 where: 469 PT_metric - is the metric of the path to the destination, measured 470 in LINK_METRIC_TYPE defined in [RFC7181]; 472 PT_address[1, ..., n-1] - are the addresses of intermediate routers 473 to be visited numbered from 1 to n-1, where n is the number of 474 routers in the path, i.e., the hop count. 476 8. Protocol Details 478 This protocol is based on OLSRv2, and extended to discover multiple 479 disjoint paths from a source router to a destination router. It 480 retains the basic routing control packets formats and processing of 481 OLSRv2 to obtain topology information of the network. The main 482 differences between OLSRv2 routing process are the datagram 483 processing at the source router and datagram forwarding. 485 8.1. HELLO and TC Message Generation 487 HELLO messages are generated according to Section 15.1 of [RFC7181]. 489 TC message are generated according to Section 16.1 of [RFC7181]. As 490 least one TC message MUST be generated by an MP-OLSRv2 Routing 491 Process during SR_TC_INTERVAL. The TC message generation based on 492 SR_TC_INTERVAL does not replace the ordinary TC message generation 493 specified in [RFC7181] and MUST not carry any advertised neighbor 494 addresses. This is due to the fact that not all routers will 495 generate TC messages based on OLSRv2. The TC generation based on 496 SR_TC_INTERVAL serves for those routers to advertise SOURCE_ROUTE TLV 497 so that the other routers can be aware of the source-route enabled 498 routers so as to be used as destinations of multipath routing. The 499 SR_TC_INTERVAL is set to a longer value than TC_INTERVAL. 501 For both TC and HELLO messages, a single Message TLV with Type := 502 SOURCE_ROUTE MUST be included. 504 8.2. HELLO and TC Message Processing 506 HELLO and TC messages are processed according to section 15.3 and 507 16.3 of [RFC7181]. 509 For the purpose of this section, the following definitions are used: 511 o "validity time" is calculated from the Message TLV with Type = 512 VALIDITY_TIME of the HELLO message or TC message. 514 o "source route hold time multiplier" is defined as being the value 515 of a Message TLV with Type = SOURCE_ROUTE. 517 For every HELLO or TC message received, if there is a Message TLV 518 with Type := SOURCE_ROUTE, create or update (if the Tuple exists 519 already) the SR-OLSR Router Tuple with 521 o SR_addr := originator address of the HELLO or TC message 523 o SR_time := current_time + source route hold time multiplier * 524 validity time, unless the existed SR_time is greater than the 525 newly calculated the SR_time. 527 8.3. MPR Selection 529 Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs 530 following Section 18 of [RFC7181]. In a mixed network with OLSRv2- 531 only routers, the following considerations apply when calculating 532 MPRs: 534 o MP-OLSR routers SHOULD be preferred as routing MPRs. 536 o The number of routing MPRs that run MP-OLSR Routing Process MUST 537 be equal or greater than NUMBER_OF_PATHS if there are enough MP- 538 OLSR symmetric neighbors. Or else, all the MP-OLSR routers are 539 selected as routing MPRs. 541 8.4. Datagram Processing at the MP-OLSRv2 Originator 543 If datagrams without source routing header need to be forwarded using 544 multiple paths (for example, based on the information of DiffServ 545 Code Point [RFC2474]), the MP-OLSRv2 routing process will try to find 546 the Multi-path Routing Tuple where: 548 o MR_dest_addr = destination of the datagram 550 If no matching Multi-path Routing Tuple is found and the Multi-path 551 Routing Set is maintained proactively, it indicates that there is no 552 route available to the desired destination. The datagram is 553 discarded. 555 If no matching Multi-path Routing Tuple is found and the Multi-path 556 Routing Set is maintained reactively, the multi-path algorithm 557 defined in Section 8.5 is invoked, to calculate the Multi-path 558 Routing Tuple to the destination. If the calculation does not return 559 any Multi-path Routing Tuple, the following steps are aborted and the 560 datagram is forwarded following OLSRv2 routing process. 562 If a matching Multi-path Routing Tuple is obtained, the Path Tuples 563 of the Multi-path Routing Tuple are applied to the datagrams using 564 Round-robin scheduling. For example, they are 2 path Tuples (Path-1, 565 Path-2) for destination router D. A series of datagrams (Packet-1, 566 Packet-2, Packet-3, ... etc.) are to be sent router D. Path-1 is then 567 chosen for Packet-1, Path-2 for Packet-2, Path-1 for Packet 3, etc. 568 Other path scheduling mechanisms are also possible and will not 569 impact the interoperability of different implementations. 571 The addresses in PT_address[1, ..., n-1] of the chosen Path Tuple are 572 thus added to the datagram header as the source routing header. For 573 IPv6 networks, strict source routing is used, thus all the 574 intermediate routers in the path are stored in the source routing 575 header following format defined in section 3 of [RFC6554], except the 576 Routing Type field is set to 254 (experimental). 578 For IPv4 networks, loose source routing is used, with following 579 rules: 581 o Only the addresses that exist in SR-OLSR Router Set can be added 582 to the source routing header. 584 o If the length of the path (n) is greater than MAX_SRC_HOPS, only 585 the "key" routers in the path are kept. By default, the key 586 routers are uniformly chosen in the path. If further information 587 such as capacity of the routers (e.g., battery life) or the 588 routers' willingness in forwarding data is available, the routers 589 with higher capacity and willingness are preferred. 591 o The routers that are considered not appropriate for forwarding 592 indicated by external policies should be avoided. 594 8.5. Multi-path Calculation 596 8.5.1. Requirements of Multi-path Calculation 598 The Multi-path Routing Set maintains the information of multiple 599 paths the the destination. The Tuples are generated based on a 600 multi-path algorithm. 602 For each path to a destination, the algorithm must provide: 604 o The metric of the path to the destination, 606 o The list of intermediate routers on the path. 608 For IPv6 networks, as strict source routing is used, only the routers 609 that exist in SR-OLSRv2 Router Set are considered in the path 610 calculation, i.e., only the source-routing supported routers can 611 exist in the path. 613 After the calculation of multiple paths, the metric of paths (denoted 614 c_i for path i) to the destination is compared to the R_metric of the 615 OLSRv2 Routing Tuple ([RFC7181]) to the same destination. If the 616 metric c_i is greater than R_metric * CUTOFF_RATIO, the corresponding 617 path i SHOULD NOT be used. If less than 2 paths are found with 618 metrics less than R_metric * CUTOFF_RATIO, the router SHOULD fall 619 back to OLSRv2 Routing Process without using multipath routing. This 620 can happen if there are too much OLSRv2-only routers in the network, 621 and requiring multipath routing may result in inferior paths. 623 By invoking the multi-path algorithm, NUMBER_OF_PATHS paths are 624 obtained and added to the Multi-path Routing Set, by creating a 625 Multi-path Routing Tuple with: 627 o MR_dest_addr := destination of the datagram 629 o A MP_path_set with calculated Path Tuples. Each Path Tuple 630 corresponds to a path obtained in Multi-path Dijkstra algorithm, 631 with PT_metric := metric of the calculated path and PT_address[1, 632 ..., n-1] := list of intermediate routers. 634 8.5.2. Multi-path Dijkstra Algorithm 636 This section introduces Multi-path Dijkstra Algorithm as a default 637 algorithm. It tries to obtain disjoint paths when appropriate, but 638 does not guarantee strict disjoint paths. The use of other 639 algorithms is not prohibited, as long as the requirements described 640 in Section 8.5.1 are met. Using different multi-path algorithms will 641 not impact the interoperability. 643 The general principle of the Multi-path Dijkstra Algorithm is at step 644 i to look for the shortest path P[i] to the destination d. Compared 645 to the original Dijkstra algorithm, the main modification consists in 646 adding two incremental functions named metric functions fp and fe in 647 order to prevent the next steps resulting in similar paths: 649 o fp(c) is used to increase metrics of arcs belonging to the 650 previous path P[i-1] (with i>1), where c is the value of the 651 previous metric. This encourages future paths to use different 652 arcs but not different vertices. 654 o fe(c) is used to increase metrics of the arcs that lead to 655 intermediate vertices of the previous path P[i-1] (with i>1), 656 where c is the value of the previous metric. The "lead to" means 657 that only one vertex of the arc belongs to the previous path 658 P[i-1], while the the other vertex is not. The "intermediate" 659 means that the source and destination vertices are not considered. 661 Considering the simple example in Figure 1: a path P[i] S--A--D is 662 obtained at step i. For the next step, the metric of link S--A and 663 A--D are to be increased using fp(c), because they belong to the path 664 P[i]. A--B is to be increased using fe(c), because A is an 665 intermediate vetex of path P[i], and B is not part of P[i]. B--D is 666 unchanged. 668 B 669 / \ 670 / \ 671 / \ 672 S---------A-----------D 674 Figure 1 676 It is possible to choose different fp and fe to get link-disjoint 677 paths or node-disjoint paths as desired. A recommendation of 678 configuration of fp and fe is given in Section 9. 680 To get NUMBER_OF_PATHS different paths, for each path P[i] (i = 1, 681 ..., NUMBER_OF_PATHS) do: 683 1. Run Dijkstra algorithm to get the shortest path P[i] for the 684 destination d. 686 2. Apply metric function fp to the metric of links (in both 687 directions) in P[i]. 689 3. Apply metric function fe to the metric of links (in both 690 directions) that lead to routers used in P[i]. 692 A simple example of Multi-path Dijkstra Algorithm is illustrated in 693 Appendix A. 695 8.6. Multi-path Routing Set Updates 697 The Multi-path Routing Set MUST be updated when the Local Information 698 Base, the Neighborhood Information Base, or the Topology Information 699 Base indicate a change (including of any potentially used outgoing 700 neighbor metric values) of the known symmetric links and/or attached 701 networks in the MANET, hence changing the Topology Graph, as 702 described in section 17.7 of [RFC7181]. How the Multi-path Routing 703 Set is updated depends on the set is maintained reactively or 704 proactively: 706 o In reactive mode, all the Tuples in the Multi-path Routing Set are 707 removed. The new arriving datagrams will be processed as 708 specified in Section 8.4; 710 o In proactive mode, the route to all the destinations are updated 711 according to Section 8.5. 713 8.7. Datagram Forwarding 715 In IPv4 networks, datagrams are forwarded using loose source routing 716 as specified in Section 3.1 of [RFC0791]. 718 In IPv6 networks, datagrams are forwarded using strict source routing 719 as specified in Section 4.2 of [RFC6554], except the applied routers 720 are MP-OLSRv2 routers rather than RPL routers. The last hop of the 721 source route MUST remove the source routing header. 723 9. Configuration Parameters 725 This section gives default values and guideline for setting 726 parameters defined in Section 5. Network administrators may wish to 727 change certain, or all the parameters for different network 728 scenarios. As an experimental protocol, the users of this protocol 729 are also encouraged to explore different parameter setting in various 730 network environments, and provide feedback. 732 o NUMBER_OF_PATHS := 3. This parameter defines the number of 733 parallel paths used in datagram forwarding. Setting it to one 734 makes the specification identical to OLSRv2. Setting it to too 735 large values may lead to unnecessary computational overhead and 736 inferior paths. 738 o MAX_SRC_HOPS := 10, for IPv4 networks. For IPv6 networks, it MUST 739 be set to 0, i.e., no constraint on maximum number of hops. 741 o CUTOFF_RATIO := 1.5. It MUST be strictly greater than 1. 743 o SR_TC_INTERVAL := 10 x TC_INTERVAL. It SHOULD be significantly 744 greater than TC_INTERVAL to reduce unnecessary TC message 745 generations. 747 o SR_HOLD_TIME_MULTIPLIER := 32. It MUST be greater than 1 and less 748 than 255. It SHOULD be greater than 30. 750 If Multi-path Dijkstra Algorithm is applied: 752 o fp(c) := 4*c, where c is the original metric of the link. 754 o fe(c) := 2*c, where c is the original metric of the link. 756 The setting of metric functions fp and fc defines the preference of 757 obtained multiple disjoint paths. If id is the identity function, 758 i.e., fp(c)=c, 3 cases are possible: 760 o if id=fe. 925 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 926 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 927 RFC2119, March 1997, 928 . 930 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 931 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 932 Format", RFC 5444, DOI 10.17487/RFC5444, February 2009, 933 . 935 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 936 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 937 RFC 6130, DOI 10.17487/RFC6130, April 2011, 938 . 940 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 941 Routing Header for Source Routes with the Routing Protocol 942 for Low-Power and Lossy Networks (RPL)", RFC 6554, 943 DOI 10.17487/RFC6554, March 2012, 944 . 946 [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 947 "The Optimized Link State Routing Protocol Version 2", 948 RFC 7181, DOI 10.17487/RFC7181, April 2014, 949 . 951 [RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity 952 Protection for the Neighborhood Discovery Protocol (NHDP) 953 and Optimized Link State Routing Protocol Version 2 954 (OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014, 955 . 957 14.2. Informative References 959 [ADHOC11] Yi, J., Adnane, A-H., David, S., and B. Parrein, 960 "Multipath optimized link state routing for mobile ad hoc 961 networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, 962 January, 2011. 964 [GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria, 965 "Experimental performance comparison of single-path and 966 multipath routing in VANETs", In Global Information 967 Infrastructure and Networking Symposium (GIIS), 2014 , 968 vol. 1, no. 6, pp. 15-19, 2014. 970 [I-D.ietf-manet-olsrv2-sec-threats] 971 Clausen, T., Herberg, U., and J. Yi, "Security Threats for 972 the Optimized Link State Routing Protocol version 2 973 (OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-02 (work in 974 progress), May 2016. 976 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 977 (IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460, 978 December 1998, . 980 [RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black, 981 "Definition of the Differentiated Services Field (DS 982 Field) in the IPv4 and IPv6 Headers", RFC 2474, 983 DOI 10.17487/RFC2474, December 1998, 984 . 986 [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking 987 (MANET): Routing Protocol Performance Issues and 988 Evaluation Considerations", RFC 2501, DOI 10.17487/ 989 RFC2501, January 1999, 990 . 992 [RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and 993 Multicast Next-Hop Selection", RFC 2991, DOI 10.17487/ 994 RFC2991, November 2000, 995 . 997 [RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation 998 of Type 0 Routing Headers in IPv6", RFC 5095, 999 DOI 10.17487/RFC5095, December 2007, 1000 . 1002 [RFC5871] Arkko, J. and S. Bradner, "IANA Allocation Guidelines for 1003 the IPv6 Routing Header", RFC 5871, DOI 10.17487/RFC5871, 1004 May 2010, . 1006 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 1007 Code: The Implementation Status Section", RFC 6982, 1008 DOI 10.17487/RFC6982, July 2013, 1009 . 1011 [RFC7722] Dearlove, C. and T. Clausen, "Multi-Topology Extension for 1012 the Optimized Link State Routing Protocol Version 2 1013 (OLSRv2)", RFC 7722, DOI 10.17487/RFC7722, December 2015, 1014 . 1016 [RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric 1017 Based on Packet Sequence Numbers for Optimized Link State 1018 Routing Version 2 (OLSRv2)", RFC 7779, DOI 10.17487/ 1019 RFC7779, April 2016, 1020 . 1022 [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, 1023 "Simulation and performance analysis of MP-OLSR for mobile 1024 ad hoc networks", In Proceeding of IEEE Wireless 1025 Communications and Networking Conference, 2008. 1027 Appendix A. Examples of Multi-path Dijkstra Algorithm 1029 This appendix gives two examples of multi-path Dijkstra algorithm. 1031 A network topology is depicted in Figure 2. 1033 .-----A-----(2) 1034 (1) / \ \ 1035 / / \ \ 1036 S (2) (1) D 1037 \ / \ / 1038 (1) / \ / (2) 1039 B----(3)----C 1041 Figure 2 1043 The capital letters are name of routers. An arbitrary metric with 1044 value between 1 and 3 is used. The initial metrics of all the links 1045 are indicated in the parenthesis. The incremental functions fp(c)=4c 1046 and fe(c)=2c are used in this example. Two paths from router S to 1047 router D are demanded. 1049 On the first run of the Dijkstra algorithm, the shortest path S->A->D 1050 with metric 3 is obtained. 1052 The incremental function fp is applied to increase the metric of the 1053 link S-A and A-D. fe is applied to increase the metric of the link 1054 A-B and A-C. Figure 3 shows the link metrics after the punishment. 1056 .-----A-----(8) 1057 (4) / \ \ 1058 / / \ \ 1059 S (4) (2) D 1060 \ / \ / 1061 (1) / \ / (2) 1062 B----(3)----C 1064 Figure 3 1066 On the second run of the Dijkstra algorithm, the second path 1067 S->B->C->D with metric 6 is obtained. 1069 As mentioned in Section 8.5, the Multi-path Dijkstra Algorithm does 1070 not guarantee strict disjoint path to avoid choosing inferior paths. 1071 For example, given the topology in Figure 4, two paths from node S to 1072 D are desired. On the top of the figure, there is a high cost path 1073 between S and D. 1075 If a algorithm tries to obtain strict disjoint paths, the two paths 1076 obtained will be S--B--D and S--(high cost path)--D, which are 1077 extremely unbalanced. It is undesired because it will cause huge 1078 delay variance between the paths. By using the Multi-path Dijkstra 1079 algorithm, which is based on the punishing scheme, S--B--D and 1080 S--B--C--D will be obtained. 1082 --high cost path- 1083 / \ 1084 / \ 1085 S----B--------------D 1086 \ / 1087 \---C-----/ 1089 Figure 4 1091 Authors' Addresses 1093 Jiazi Yi 1094 Ecole Polytechnique 1095 91128 Palaiseau Cedex, 1096 France 1098 Phone: +33 (0) 1 77 57 80 85 1099 Email: jiazi@jiaziyi.com 1100 URI: http://www.jiaziyi.com/ 1102 Benoit Parrein 1103 University of Nantes 1104 IRCCyN lab - IVC team 1105 Polytech Nantes, rue Christian Pauc, BP50609 1106 44306 Nantes cedex 3 1107 France 1109 Phone: +33 (0) 2 40 68 30 50 1110 Email: Benoit.Parrein@polytech.univ-nantes.fr 1111 URI: http://www.irccyn.ec-nantes.fr/~parrein