idnits 2.17.1 draft-ietf-manet-olsrv2-multipath-06.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 (July 21, 2015) is 3203 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 423 -- Looks like a reference, but probably isn't: '2' on line 423 == Outdated reference: A later version (-12) exists of draft-ietf-manet-olsrv2-dat-metric-05 == Outdated reference: A later version (-07) exists of draft-ietf-manet-olsrv2-multitopology-06 == Outdated reference: A later version (-04) exists of draft-ietf-manet-olsrv2-sec-threats-00 -- 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 (~~), 4 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 LIX, Ecole Polytechnique 4 Intended status: Experimental B. Parrein 5 Expires: January 22, 2016 University of Nantes 6 July 21, 2015 8 Multi-path Extension for the Optimized Link State Routing Protocol 9 version 2 (OLSRv2) 10 draft-ietf-manet-olsrv2-multipath-06 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 22, 2016. 36 Copyright Notice 38 Copyright (c) 2015 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 . . . . . . . . . . . . . . . . . . . . . 7 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 . . . . . . . . . . . . 8 65 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8 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 . . . . . . . . . . . . . 10 72 8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10 73 8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 11 74 8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 12 75 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13 76 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 14 77 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 14 78 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 14 79 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 15 80 11. Security Considerations . . . . . . . . . . . . . . . . . . . 15 81 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 82 12.1. Expert Review: Evaluation Guidlines . . . . . . . . . . . 16 83 12.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 16 84 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 85 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 86 14.1. Normative References . . . . . . . . . . . . . . . . . . . 17 87 14.2. Informative References . . . . . . . . . . . . . . . . . . 17 88 Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 19 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 91 1. Introduction 93 The Optimized Link State Routing Protocol version 2 (OLSRv2) 94 [RFC7181] is a proactive link state protocol designed for use in 95 mobile ad hoc networks (MANETs). It generates routing messages 96 periodically to create and maintain a Routing Set, which contains 97 routing information to all the possible destinations in the routing 98 domain. For each destination, there exists a unique Routing Tuple, 99 which indicates the next hop to reach the destination. 101 This document specifies an extension of the OLSRv2 protocol 102 [RFC7181], to provide multiple disjoint paths when appropriate for a 103 source-destination pair. Because of the characteristics of MANETs 104 [RFC2501], especially the dynamic topology, having multiple paths is 105 helpful for increasing network throughput, improving forwarding 106 reliability and load balancing. 108 The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses 109 Multi-path Dijkstra algorithm by default to explore multiple disjoint 110 paths from a source router to a destination router based on the 111 topology information obtained through OLSRv2, and to forward the 112 datagrams in a load-balancing manner using source routing. MP-OLSRv2 113 is designed to be interoperable with OLSRv2. 115 1.1. Motivation and Experiments to Be Conducted 117 This document is an experimental extension of OLSRv2 that can 118 increase the data forwarding reliability in dynamic and high-load 119 MANET scenarios by transmitting datagrams over multiple disjoint 120 paths using source routing. This mechanism is used because: 122 o Disjoint paths can avoid single route failures. 124 o Transmitting datagrams through parallel paths can increase 125 aggregated throughput and provide load balancing. 127 o Certain scenarios require some routers must (or must not) be used. 129 o By having control of the paths at the source, the delay can be 130 provisioned. 132 o A very important application of this extension is in combination 133 with Forward Error Correction (FEC) coding. Because the packet 134 drop is normally bursty in a path (for example, due to route 135 failure), FEC coding is less effective in single path routing 136 protocols. By providing multiple disjoint paths, the application 137 of FEC coding with multi-path protocol is more resilient to 138 routing failures. 140 While in existing deployments, running code and simulations have 141 proven the interest of multi-path extension for OLSRv2 in certain 142 networks, more experiments and experiences are still needed to 143 understand the effects of the protocol. The multi-path extension for 144 OLSRv2 is expected to be revised and improved to the Standard Track, 145 once sufficient operational experience is obtained. Other than 146 general experiences including the protocol specification, 147 interoperability with original OLSRv2 implementations, the 148 experiences in the following aspects are highly appreciated: 150 o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) 151 to be used. This depends on the network topology and router 152 density. 154 o Optimal values used in the cost functions. Cost functions are 155 applied to punish the costs of used links and nodes so as to 156 obtain disjoint paths. What kind of disjointness is desired 157 (node-disjoint or link-disjoint) may depend on the layer 2 158 protocol used, and can be achieved by setting different sets of 159 cost functions. 161 o Use of metrics other than hop-count. This multi-path extension 162 can be used not only for hop-count metric type, but also other 163 metric types that meet the requirement of OLSRv2, such as 164 [I-D.ietf-manet-olsrv2-dat-metric]. The metric type used has also 165 co-relation with the choice of cost functions as indicated in the 166 previous bullet point. 168 o Optimal choice of "key" routers for loose source routing. In some 169 cases, loose source routing is used to reduce overhead or for 170 interoperability with OLSRv2 routers. Other than the basic rules 171 defined in the following of this document, optimal choices of 172 routers to put in the loose source routing header can be further 173 studied. 175 o Different path-selection schedulers. By default, Round-Robin 176 scheduling is used to select a path to be used for a datagram. In 177 some scenarios, weighted scheduling can be considered: for 178 example, the paths with lower costs (higher path quality) can 179 transfer more datagrams compared to paths with higher costs. 181 o The impacts of the delay variation due to multi-path routing. 182 [RFC2991] brings out some concerns of multi-path routing, 183 especially variable latencies. Although current experiment 184 results show that multi-path routing can reduce the jitter in 185 dynamic scenarios, some transport protocols or applications may be 186 sensitive to the datagram re-ordering. 188 o The disjoint multi-path protocol has interesting application with 189 Forward Error Correction (FEC) Coding, especially for services 190 like video/audio streaming. The combination of FEC coding 191 mechanisms and this extension is thus encouraged. By applying FEC 192 coding, the issue of packet re-ordering can be alleviated. 194 o Different algorithms to obtain multiple paths, other than the 195 default Multi-path Dijkstra algorithm introduced in this 196 specification. 198 o In addition to the IP source routing based approach, it can be 199 interesting to try multi-path routing in MANET using label- 200 switched flow in the future. 202 o The use of multi-topology information. By using 203 [I-D.ietf-manet-olsrv2-multitopology], multiple topologies using 204 different metric types can be obtained. It is also encouraged to 205 experiment the use of multiple metrics for building multiple 206 paths. 208 2. Terminology 210 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 211 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 212 "OPTIONAL" in this document are to be interpreted as described in 213 [RFC2119]. 215 This document uses the terminology and notation defined in [RFC5444], 216 [RFC6130], [RFC7181]. Additionally, it defines the following 217 terminology: 219 OLSRv2 Routing Process - The routing process based on [RFC7181], 220 without multi-path extension specified in this document. 222 MP-OLSRv2 Routing Process - The multi-path routing process based on 223 this specification as an extension to [RFC7181]. 225 3. Applicability Statement 227 As an extension of OLSRv2, this specification is applicable to MANETs 228 for which OLSRv2 is applicable (see [RFC7181]). It can operate on 229 single, or multiple interfaces, to discover multiple disjoint paths 230 from a source router to a destination router. 232 MP-OLSRv2 is specially designed for networks with dynamic topology 233 and low data rate links. By providing multiple paths, higher 234 aggregated throughput can be obtained, and the routing process is 235 more robust to packet loss. 237 In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily 238 replace OLSRv2 completely. The extension can be applied for certain 239 applications that are suitable for multi-path routing (mainly video 240 or audio streams), based on the information such as DiifServ Code 241 Point [RFC2474]. 243 Compared to OLSRv2, this extension does not introduce new message 244 type in the air. A new Message TLV type is introduced to identify 245 the routers that support forwarding based on source route header. It 246 is interoperable with OLSRv2 implementations that do not have this 247 extension. 249 MP-OLSRv2 forwards datagrams using the source routing header. 250 Depending on the IP version used, the source routing header is 251 formatted according to [RFC0791] or [RFC6554]. 253 4. Protocol Overview and Functioning 255 This specification requires OLSRv2 [RFC7181] to: 257 o Identify all the reachable routers in the network. 259 o Identify a sufficient subset of links in the networks, so that 260 routes can be calculated to all reachable destinations. 262 o Provide a Routing Set containing shortest routes from this router 263 to all destinations. 265 In addition, the MP-OLSRv2 Routing Process identifies the routers 266 that support source routing by adding a new Message TLV in HELLO and 267 TC messages. Based on the above information acquired, every MP- 268 OLSRv2 Routing Process is aware of a reduced topology map of the 269 network and the routers supporting source routing. 271 A multi-path algorithm is invoked on demand, i.e., only when there is 272 a datagram to be sent from the source to the destination, and there 273 is no available routing tuple in the Multi-path Routing Set. The 274 Multi-path Dijkstra algorithm (defined in Section 8.4) can generate 275 multiple disjoint paths from a source to a destination, and such 276 information is kept in the Multi-path Routing Set. 278 The datagram is forwarded based on source routing. When there is a 279 datagram to be sent to a destination, the source router acquires a 280 path from the Multi-path Routing Set (MAY be Round-Robin, or other 281 scheduling algorithms). The path information is stored in the 282 datagram header as source routing header. 284 All the intermediate routers are listed in the source routing header 285 (SRH), unless there are routers that do not support source-route 286 forwarding in the paths, or the paths are too long to be fully stored 287 in the SRH -- in which case, loose source routing is used. The 288 intermediate routers listed in the SRH read the SRH and forward the 289 datagram to the next hop as indicated in the SRH. 291 5. Parameters and Constants 293 In addition to the parameters and constants defined in [RFC7181], 294 this specification uses the parameters and constants described in 295 this section. 297 5.1. Router Parameters 299 NUMBER_OF_PATHS The number of paths desired by the router. 301 MAX_SRC_HOPS The maximum number of hops allowed to be put in the 302 source routing header. 304 fp Incremental function of the Multi-path Dijkstra algorithm. It 305 is used to increase costs of links belonging to the previously 306 computed path. 308 fe Incremental function of the Multi-path Dijkstra algorithm. It 309 is used to increase costs of links that lead to routers of the 310 previously computed path. 312 MR_HOLD_TIME It is the minimal time that a Multi-path Routing Tuple 313 SHOULD be kept in the Multi-path Routing Set. 315 SR_OLSR_HOLD_TIME It is the minimal time that a SR-OLSRv2 Router 316 Tuple SHOULD be kept in the SR-OLSRv2 Router Set. 318 6. Packets and Messages 320 This extension employs the routing control messages HELLO and TC 321 (Topology Control) as defined in OLSRv2 [RFC7181]. To support source 322 routing, a source routing header is added to each datagram routed by 323 this extension. Depending on the IP version used, the source routing 324 header is defined in this section. 326 6.1. HELLO and TC messages 328 HELLO and TC messages used by MP-OLSRv2 Routing Process share the 329 same format as defined in [RFC7181]. In addition, a new Message TLV 330 type is defined, to identify the originator of the HELLO or TC 331 message that supports source route forwarding. The new Message TLV 332 type is introduced for enabling MP-OLSRv2 as an extension of OLSRv2: 333 only the routers supporting source-route forwarding can be used in 334 the source routing header of a datagram, because adding a router that 335 does not understand the source routing header will cause routing 336 failure. 338 6.1.1. SOURCE_ROUTE TLV 340 SOURCE_ROUTE TLV is a Message TLV that signals that the message is 341 generated by a router that supports source-route forwarding. It can 342 be an MP-OLSRv2 Routing Process, or an OLSRv2 Routing Process that 343 supports source-route forwarding. The SOURCE_ROUTE TLV does not 344 include any value. 346 Every HELLO or TC message generated by a MP-OLSRv2 Routing Process 347 MUST have exactly one SOURCE_ROUTE TLV. 349 Every HELLO or TC message generated by an OLSRv2 Routing Process MAY 350 have one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process supports 351 source-route forwarding, and is willing to join the source route 352 generated by other MP-OLSRv2 Routing Processes. The existence of 353 SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing 354 Process, i.e., either it adds SOURCE_ROUTE TLV to all its HELLO/TC 355 messages, or it does not add SOURCE_ROUTE TLV to any HELLO/TC 356 message. 358 6.2. Datagram 360 6.2.1. Source Routing Header in IPv4 362 In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs 363 loose source routing header, as defined in [RFC0791]. It exists as 364 an option header, with option class 0, and option number 3. 366 The source route information is kept in the "route data" field of the 367 loose source route header. 369 6.2.2. Source Routing Header in IPv6 371 In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the 372 source routing header as defined in [RFC6554], with IPv6 Routing Type 373 3. 375 The source route information is kept in the "Addresses" field of the 376 routing header. 378 7. Information Bases 380 Each MP-OLSRv2 routing process maintains the information bases as 381 defined in [RFC7181]. Additionally, two more information bases are 382 defined for this specification. 384 7.1. SR-OLSRv2 Router Set 386 The SR-OLSRv2 Router Set records the routers that support source- 387 route forwarding. This includes routers that run MP-OLSRv2 Routing 388 Process, or OLSRv2 Routing Process with source-route forwarding 389 support. The set consists of SR-OLSRv2 Router Tuples: 391 (SR_OLSR_addr, SR_OLSR_valid_time) 393 where: 395 SR_OLSR_addr - it is the network address of the router that 396 supports source-route forwarding; 398 SR_OLSR_valid_time - it is the time until which the SR-OLSRv2 399 Router Tuples is considered valid. 401 7.2. Multi-path Routing Set 403 The Multi-path Routing Set records the full path information of 404 different paths to the destination. It consists of Multi-path 405 Routing Tuples: 407 (MR_dest_addr, MR_valid_time, MR_path_set) 409 where: 411 MR_dest_addr - it is the network address of the destination, either 412 the network address of an interface of a destination router or the 413 network address of an attached network; 415 MR_valid_time - it is the time until which the Multi-path Routing 416 Tuple is considered valid; 418 MP_path_set - it contains the multiple paths to the destination. 419 It consists of a set of Path Tuples. 421 Each Path Tuple is defined as: 423 (PT_cost, PT_address[1], PT_address[2], ..., PT_address[n]) 425 where: 427 PT_cost - the cost of the path to the destination; 429 PT_address[1...n] - the addresses of intermediate routers to be 430 visited numbered from 1 to n. 432 8. Protocol Details 434 This protocol is based on OLSRv2, and extended to discover multiple 435 disjoint paths from a source router to a destination router. It 436 retains the basic routing control packets formats and processing of 437 OLSRv2 to obtain topology information of the network. The main 438 differences between OLSRv2 routing process are the datagram 439 processing at the source router and datagram forwarding. 441 8.1. HELLO and TC Message Generation 443 HELLO and TC messages are generated according to the Section 15.1 or 444 Section 16.1 of [RFC7181]. 446 A single Message TLV with Type := SOURCE_ROUTE MUST be added to the 447 message. 449 8.2. HELLO and TC Message Processing 451 HELLO and TC messages are processed according to the section 15.3 and 452 16.3 of [RFC7181]. 454 For every HELLO or TC message received, if there exists a Message TLV 455 with Type := SOURCE_ROUTE, create or update (if the tuple exists 456 already) the SR-OLSR Router Tuple with 458 o SR_OLSR_addr = originator of the HELLO or TC message 460 and set the SR_OLSR_valid_time := current_time + SR_OLSR_HOLD_TIME. 462 8.3. Datagram Processing at the MP-OLSRv2 Originator 464 When the MP-OLSRv2 routing process receives a datagram from upper 465 layers or interfaces connecting other routing domains, find the 466 Multi-path Routing Tuple where: 468 o MR_dest_addr = destination of the datagram, and 469 o MR_valid_time > current_time. 471 If a matching Multi-path Routing Tuple is found, a Path Tuple is 472 chosen from the MR_path_set in Round-robin fashion (if there are 473 multiple datagrams to be sent). Or else, the multi-path algorithm 474 defined in Section 8.4 is invoked, to generate the desired Multi-path 475 Routing Tuple. 477 The addresses in PT_address[1...n] of the chosen Path Tuple are thus 478 added to the datagram header as source routing header, following the 479 rules: 481 o Only the addresses that exist in SR-OLSR Router Set can be added 482 to the source routing header. 484 o If the length of the path (n) is greater than MAX_SRC_HOPS, only 485 the key routers in the path are kept. By default, the key routers 486 are uniformly chosen in the path. 488 o The routers with higher priority (such as higher routing 489 willingness defined in [RFC7181]) are preferred. 491 o The routers that are considered not appropriate for forwarding 492 indicated by external policies should be avoided. 494 8.4. Multi-path Dijkstra Algorithm 496 A multi-path algorithm is invoked when there is no available Multi- 497 path Routing Tuple to a desired destination d to obtain the multiple 498 paths. This section introduces Multi-path Dijkstra Algorithm as a 499 default mechanism. It tries to obtain disjoint paths when 500 appropriate, but does not guarantee strict disjoint paths. The 501 rationale is explained in Appendix A. 503 The use of other algorithms is not prohibited, as long as they can 504 provide a full path from the source to the destination router. Using 505 different multi-path algorithms will not impact the interoperability. 507 The general principle of the Multi-path Dijkstra Algorithm is at step 508 i to look for the shortest path P[i] to the destination d. Compared 509 to the original Dijkstra algorithm, the main modification consists in 510 adding two cost functions named incremental functions fp and fe in 511 order to prevent the next steps resulting in similar paths. fp is 512 used to increase costs of arcs belonging to the previous path P[i-1] 513 (with i>1). This encourages future paths to use different arcs but 514 not different vertices. fe is used to increase costs of the arcs who 515 lead to vertices of the previous path P[i-1] (with i>1). It is 516 possible to choose different fp and fe to get link-disjoint paths or 517 node-disjoint paths as desired. A recommendation of configuration of 518 fp and fe is given in Section 9. 520 To get NUMBER_OF_PATHS different paths, for each path P[i] (i = 1, 521 ..., NUMBER_OF_PATHS) do: 523 1. Run Dijkstra algorithm to get the shortest path P[i] for the 524 destination d. 526 2. Apply cost function fp to the cost of links (in both directions) 527 in P[i]. 529 3. Apply cost function fe to the cost of links (in both directions) 530 that lead to routers used in P[i]. 532 A simple example of Multi-path Dijkstra Algorithm is illustrated in 533 Appendix A. 535 By invoking the algorithm depicted above, NUMBER_OF_PATHS paths are 536 obtained and added to the Multi-path Routing Set, by creating a 537 Multi-path Routing Tuple with: 539 o MR_dest_addr := destination d 541 o MR_valid_time := current time + MR_HOLD_TIME 543 o Each Path Tuple in the MP_path_set corresponds to a path obtained 544 in Multi-path Dijkstra algorithm, with PT_cost := cost of the path 545 to the destination d (which may include one or several additions 546 of the cost functions). 548 8.5. Datagram Forwarding 550 On receiving a datagram with source routing header, the Destination 551 Address field of the IP header is first compared to the addresses of 552 the local interfaces. If a matching local address if found, the 553 datagram is processed from Step 1 to Step 4 as follows. Or else, the 554 datagram is processed from Step 3 to Step 4. 556 1. Obtain the next source address Address[i] in the source route 557 header. How to obtain the next source address depends on the IP 558 version used. In IPv4, the position of the next source address 559 is indicated by the "pointer" field of the source routing header 560 [RFC0791]. In IPv6, the position is indicated by "Segments Left" 561 field of the source routing header. If no next source address is 562 found, the forwarding process is finished and the datagram 563 arrives at its destination. 565 2. Swap Address[i] and destination address in the IP header. 567 3. If the Destination Address of the IP header belongs to one of the 568 router's 1-hop symmetric neighbors, the datagram is forwarded to 569 the neighbor router. Or else: 571 4. Forward the datagram to the destination address according to the 572 OLSRv2 Routing Tuple information through R_local_iface_addr where 574 * R_dest_addr = destination address in the IP header 576 9. Configuration Parameters 578 This section gives default values and guideline for setting 579 parameters defined in Section 5. Network administrators may wish to 580 change certain, or all the parameters for different network 581 scenarios. As an experimental track protocol, the users of this 582 protocol are also encouraged to explore different parameter setting 583 in various network environments, and provide feedback. 585 o NUMBER_OF_PATHS = 3. This parameter defines the number of 586 parallel paths used in datagram forwarding. Setting it to one 587 makes the specification identical to OLSRv2. Setting it to too 588 large values may lead to unnecessary computational overhead and 589 inferior paths. 591 o MAX_SRC_HOPS = 10. 593 o MR_HOLD_TIME = 10 seconds. 595 o MP_OLSR_HOLD_TIME = 10 seconds. 597 o fp(c) = 4*c, where c is the original cost of the link. 599 o fe(c) = 2*c, where c is the original cost of the link. 601 The setting of cost functions fp and fc defines the preference of 602 obtained multiple disjoint paths. If id is the identity function, 603 i.e., fp(c)=c, 3 cases are possible: 605 o if id=fe. 762 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 763 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 764 RFC2119, March 1997, 765 . 767 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 768 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 769 Format", RFC 5444, DOI 10.17487/RFC5444, February 2009, 770 . 772 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 773 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 774 RFC 6130, DOI 10.17487/RFC6130, April 2011, 775 . 777 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 778 Routing Header for Source Routes with the Routing Protocol 779 for Low-Power and Lossy Networks (RPL)", RFC 6554, 780 DOI 10.17487/RFC6554, March 2012, 781 . 783 [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 784 "The Optimized Link State Routing Protocol Version 2", 785 RFC 7181, DOI 10.17487/RFC7181, April 2014, 786 . 788 [RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity 789 Protection for the Neighborhood Discovery Protocol (NHDP) 790 and Optimized Link State Routing Protocol Version 2 791 (OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014, 792 . 794 14.2. Informative References 796 [ADHOC11] Yi, J., Adnane, A-H., David, S., and B. Parrein, 797 "Multipath optimized link state routing for mobile ad hoc 798 networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, 799 January, 2011. 801 [GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria, 802 "Experimental performance comparison of single-path and 803 multipath routing in VANETs", In Global Information 804 Infrastructure and Networking Symposium (GIIS), 2014 , 805 vol. 1, no. 6, pp. 15-19, 2014. 807 [I-D.ietf-manet-olsrv2-dat-metric] 808 Rogge, H. and E. Baccelli, "Packet Sequence Number based 809 directional airtime metric for OLSRv2", 810 draft-ietf-manet-olsrv2-dat-metric-05 (work in progress), 811 April 2015. 813 [I-D.ietf-manet-olsrv2-multitopology] 814 Dearlove, C. and T. Clausen, "Multi-Topology Extension for 815 the Optimized Link State Routing Protocol version 2 816 (OLSRv2)", draft-ietf-manet-olsrv2-multitopology-06 (work 817 in progress), July 2015. 819 [I-D.ietf-manet-olsrv2-sec-threats] 820 Clausen, T., Herberg, U., and J. Yi, "Security Threats for 821 the Optimized Link State Routing Protocol version 2 822 (OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-00 (work in 823 progress), February 2015. 825 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 826 (IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460, 827 December 1998, . 829 [RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black, 830 "Definition of the Differentiated Services Field (DS 831 Field) in the IPv4 and IPv6 Headers", RFC 2474, 832 DOI 10.17487/RFC2474, December 1998, 833 . 835 [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking 836 (MANET): Routing Protocol Performance Issues and 837 Evaluation Considerations", RFC 2501, DOI 10.17487/ 838 RFC2501, January 1999, 839 . 841 [RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and 842 Multicast Next-Hop Selection", RFC 2991, DOI 10.17487/ 843 RFC2991, November 2000, 844 . 846 [RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation 847 of Type 0 Routing Headers in IPv6", RFC 5095, 848 DOI 10.17487/RFC5095, December 2007, 849 . 851 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 852 Code: The Implementation Status Section", RFC 6982, 853 DOI 10.17487/RFC6982, July 2013, 854 . 856 [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, 857 "Simulation and performance analysis of MP-OLSR for mobile 858 ad hoc networks", In Proceeding of IEEE Wireless 859 Communications and Networking Conference, 2008. 861 Appendix A. Examples of Multi-path Dijkstra Algorithm 863 This appendix gives two examples of multi-path Dijkstra algorithm. 865 A network topology is depicted in Figure 1. 867 .-----2-----. 868 / / \ \ 869 / / \ \ 870 1 / \ 5 871 \ / \ / 872 \ / \ / 873 3-----------4 875 Figure 1 877 The initial cost of all the links is set to 1. The incremental 878 functions fp and fe are defined as fp(c)=4c and fe(c)=2c in this 879 example. Two paths from node 1 to node 5 are demanded. 881 On the first run of the Dijkstra algorithm, the shortest path 1->2->5 882 with cost 2 is obtained. 884 The incremental function fp is applied to increase the cost of the 885 link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of 886 the link 1-3, 2-3, 2-4, 4-5, from 1 to 2. 888 On the second run of the Dijkstra algorithm, the second path 889 1->3->4->5 with cost 5 is obtained. 891 As mentioned in Section 8.4, the Multi-path Dijkstra Algorithm does 892 not guarantee strict disjoint path to avoid choosing inferior paths. 893 For example, given the topology in Figure 2, two paths from node S to 894 D are desired. 896 If a algorithm tries to obtain strict disjoint paths, the two paths 897 obtained will be S--B--D and S--50 hops--D, which are extremely 898 unbalanced. It is undesired because it will cause huge delay 899 variance between the paths. By using the Multi-path Dijkstra 900 algorithm, which is based on the punishing scheme, S--B--D and 901 S--B--C--D will be obtained. 903 ---50 hops------- 904 / \ 905 / \ 906 S----B--------------D 907 \ / 908 \---C-----/ 910 Figure 2 912 Authors' Addresses 914 Jiazi Yi 915 LIX, Ecole Polytechnique 916 91128 Palaiseau Cedex, 917 France 919 Phone: +33 1 77 57 80 85 920 Email: jiazi@jiaziyi.com 921 URI: http://www.jiaziyi.com/ 923 Benoit Parrein 924 University of Nantes 925 IRCCyN lab - IVC team 926 Polytech Nantes, rue Christian Pauc, BP50609 927 44306 Nantes cedex 3 928 France 930 Phone: +33 (0) 240 683 050 931 Email: Benoit.Parrein@polytech.univ-nantes.fr 932 URI: http://www.irccyn.ec-nantes.fr/~parrein