idnits 2.17.1 draft-ietf-manet-olsrv2-multipath-01.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 (September 15, 2014) is 3510 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 378 -- Looks like a reference, but probably isn't: '2' on line 378 == Outdated reference: A later version (-12) exists of draft-ietf-manet-olsrv2-dat-metric-02 == Outdated reference: A later version (-07) exists of draft-ietf-manet-olsrv2-multitopology-04 -- 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 LIX, Ecole Polytechnique 4 Intended status: Experimental B. Parrein 5 Expires: March 19, 2015 University of Nantes 6 September 15, 2014 8 Multi-path Extension for the Optimized Link State Routing Protocol 9 version 2 (OLSRv2) 10 draft-ietf-manet-olsrv2-multipath-01 12 Abstract 14 This document specifies a multi-path extension to 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 March 19, 2015. 36 Copyright Notice 38 Copyright (c) 2014 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 . . . . . . . . . . . . . . . . . . . 6 59 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 6 60 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 7 61 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 7 62 6.1.1. MP_OLSRv2 TLV . . . . . . . . . . . . . . . . . . . . 7 63 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 7 64 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 8 65 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8 66 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 8 67 7.1. MP-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 8 68 7.2. Multi-path Routing Set . . . . . . . . . . . . . . . . . . 8 69 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 9 70 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 9 71 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 9 72 8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10 73 8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 10 74 8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 11 75 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 12 76 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 77 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 13 78 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 13 79 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 14 80 11. Security Considerations . . . . . . . . . . . . . . . . . . . 14 81 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 82 12.1. HELLO Message-Type-Specific TLV Type Registries . . . . . 15 83 12.2. TC Message-Type-Specific TLV Type Registries . . . . . . . 15 84 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15 85 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 86 14.1. Normative References . . . . . . . . . . . . . . . . . . . 15 87 14.2. Informative References . . . . . . . . . . . . . . . . . . 16 88 Appendix A. An example of Multi-path Dijkstra Algorithm . . . . . 17 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 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 an 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 for a source- 103 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 transmission 106 reliability and load balancing. 108 The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses 109 multi-path Dijkstra algorithm to explore multiple disjoint paths from 110 source to the destination based on the topology information obtained 111 through OLSRv2, and forward the datagrams in a load-balancing manner 112 using source routing. MP-OLSRv2 is designed to be interoperable with 113 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 packet over multiple disjoint paths 120 using source routing. This mechanism is used because: 122 o Disjoint paths can avoid single route failure. 124 o By having control of the paths at the source, the delay can be 125 provisioned. 127 o Certain scenarios require some routers must (or must not) be used. 129 o An very important application of this extension is combination 130 with Forward Error Correction coding. This requires disjoint 131 paths. The single path routing is not adapted because the packet 132 drop is normally continuous, in which forward correction coding is 133 not helpful. 135 While existed deployments, running code and simulations have proven 136 the interest of multi-path extension for OLSRv2 in certain networks, 137 more experiments and experiences are still needed to understand the 138 mechanisms of the protocol. The multipath extension for OLSRv2 is 139 expected to be revised and improved to the Standard Track, once 140 sufficient operational experience is obtained. Other than the 141 general experiences including the protocol specification, 142 interoperability with original OLSRv2 implementations, the 143 experiences in the following aspects are highly appreciated: 145 o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) 146 to be used. This depends on the network topology and router 147 density. 149 o Optimal values for the cost functions. Cost functions are applied 150 to punish the costs of used links and nodes so as to obtain 151 disjoint paths. What kind of disjointness is desired (node- 152 disjoint or link-disjoint) may depends on the layer 2 protocol 153 used, and can be achieved by setting different sets of cost 154 functions. 156 o Optimal choice of "key" routers for loose source routing. In some 157 cases, loose source routing is use to reduce overhead or for 158 interoperability with OLSRv2. Other than the basic rules defined 159 in the following of this document, optimal choices of routers to 160 put in the source routing header can be further studied. 162 o Use of other metric other than hop-count. This multipath 163 extension can be used not only for hop-count metric type, but 164 other metric types that meet the requirement of OLSRv2, such as 165 [I-D.ietf-manet-olsrv2-dat-metric]. The metric type used has also 166 co-relation with the choice of cost functions as indicated in the 167 previous bullet. 169 o The impacts to the delay variation due to multi-path routing. 170 [RFC2991] brings out some concerns of multi-path routing, 171 especially variable latencies. Although current experiments 172 result show that multi-path routing can reduce the jitter in 173 dynamic scenarios, some transport protocols or applications may be 174 sensitive to the packet re-ordering. 176 o The disjoint multiple path protocol has interesting application 177 with Forward Error Correction (FEC) Coding, especially for 178 services like video/audio streaming. The combination of FEC 179 coding mechanisms and this extension is thus encouraged. 181 o In addition to IP source routing based approach, it can be 182 interesting to try multi-path routing in MANET using label- 183 switched flow in the future. 185 o The usage of multi-topology information. By using 186 [I-D.ietf-manet-olsrv2-multitopology], multiple topologies using 187 different metric types can be obtained. It is encouraged to 188 experiment the use of multiple metrics for building multiple paths 189 also. 191 2. Terminology 193 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 194 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 195 "OPTIONAL" in this document are to be interpreted as described in 196 [RFC2119]. 198 This document uses the terminology and notation defined in [RFC5444], 199 [RFC6130], [RFC7181]. Additionally, it defines the following 200 terminology: 202 OLSRv2 Routing Process - The routing process based on [RFC7181], 203 without multi-path extension specified in this document. 205 MP-OLSRv2 Routing Process - The routing process based on this 206 specification as an extension to [RFC7181]. 208 3. Applicability Statement 210 As an extension of OLSRv2, this specification is applicable to MANETs 211 for which OLSRv2 is applicable (see [RFC7181]). It can operate on 212 single, or multiple interfaces, to discover multiple disjoint paths 213 from a source router to a destination router. 215 MP-OLSRv2 is specially designed for networks with dynamic topology 216 and slow data rate links. By providing multiple paths, higher 217 aggregated bandwidth can be obtained, and the routing process is more 218 robust to packet loss. 220 In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily 221 replace OLSRv2 completely. The extension can be applied for certain 222 applications that are suitable for multi-path routing (mainly video 223 or audio streams), based on the information such as DiifServ Code 224 Point [RFC2474]. 226 Compared to OLSRv2, this extension does not introduce new message 227 type in the air, and is interoperable with OLSRv2 implementations 228 that do not have this extension. 230 4. Protocol Overview and Functioning 232 This specification requires OLSRv2 [RFC7181] to: 234 o Identify all the reachable routers in the network. 236 o Identify a sufficient subset of links in the networks, so that 237 routes can be calculated to all reachable destinations. 239 o Provide a Routing Set containing shortest routes from this router 240 to all destinations. 242 Based on the above information acquired by OLSRv2, the MP-OLSRv2 243 Routing Process is able to calculate multiple paths to certain 244 destinations based on multi-path Dijkstra algorithm: the Dijkstra 245 algorithm is performed multiple times . In each iteration, the cost 246 of used links are increased (i.e., punished), so that they can be 247 avoided to be chosen in the next iteration. The multi-path Dijkstra 248 algorithm can generate multiple disjoint paths from a source to a 249 destination , and such information is kept in Multi-path Routing Set. 250 The algorithm is invoked on demand, i.e., only when there is data 251 traffic to be sent from the source to the destination, and there is 252 no available routing tuples in the Multi-path Routing Set. 254 The datagram is forwarded based on source routing. When there is a 255 datagram to be sent to a destination, the source router acquires a 256 path from the Multi-path Routing Set (in Round-Robin fashion here) . 257 The path information is stored in the datagram header as source 258 routing header. 260 All the intermediate routers are listed in the source routing header 261 (SRH), unless there are routers that do not support MP-OLSRv2 in the 262 paths, or the paths are too long to be fully stored in the SRH -- in 263 which case, loose source routing is used. The intermediate routers 264 listed in the SRH read the SRH and forward the datagram to the next 265 hop indicated in the SRH. 267 5. Parameters and Constants 269 In addition to the parameters and constants defined in [RFC7181], 270 this specification uses the parameters and constants described in 271 this section. 273 5.1. Router Parameters 274 NUMBER_OF_PATHS The number of paths desired by the router. 276 MAX_SRC_HOPS The maximum number of hops allowed to put in the 277 source routing header. 279 fp Incremental function of multi-path Dijkstra algorithm. It is 280 used to increase costs of links belonging to the previously 281 computed path. 283 fe Incremental function of multi-path Dijkstra algorithm. It is 284 used to increase costs of links who lead to routers of the 285 previous computed path. 287 MR_HOLD_TIME It is the minimal time that a Multi-path Routing Tuple 288 SHOULD be kept in the Multi-path Routing Set. 290 MP_OLSR_HOLD_TIME It is the minimal time that a MP-OLSRv2 Router 291 Tuple SHOULD be kept in the MP-OLSRv2 Router Set. 293 6. Packets and Messages 295 This extension employs the routing control messages HELLO and TC 296 (Topology Control) as defined in OLSRv2 [RFC7181]. To support source 297 routing, a source routing header is added to each datagram routed by 298 this extension. Depending on the IP version used, the source routing 299 header is defined in following of this section. 301 6.1. HELLO and TC messages 303 HELLO and TC messages used by MP-OLSRv2 Routing Process share the 304 same format as defined in [RFC7181]. In addition, one Message TLV is 305 defined, to identify the originator of the HELLO or TC message is 306 running MP-OLSRv2. 308 6.1.1. MP_OLSRv2 TLV 310 An MP_OLSRv2 TLV is a Message TLV that signals the message is 311 generated by an MP-OLSRv2 Routing Process. It does not include any 312 value. 314 Every HELLO or TC message generated by MP-OLSRv2 Routing Process MUST 315 has one MP_OLSRv2 TLV. 317 6.2. Datagram 318 6.2.1. Source Routing Header in IPv4 320 In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs 321 loose source routing, as defined in [RFC0791]. It exists as an 322 option header, with option class 0, and option number 3. 324 The source route information is kept in the "route data" field of the 325 loss source route header. 327 6.2.2. Source Routing Header in IPv6 329 In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the 330 source routing header as defined in [RFC6554], with IPv6 Routing Type 331 3. 333 The source route information is kept in the "Addresses" field of the 334 routing header. 336 7. Information Bases 338 Each MP-OLSRv2 routing process maintains the information bases as 339 defined in [RFC7181]. Additionally, two more information bases are 340 defined for this specification. 342 7.1. MP-OLSRv2 Router Set 344 The MP-OLSRv2 Router Set recordes the routers running the MP-OLSRv2 345 Routing Process. It consists of MP-OLSRv2 Router Tuples: 347 (MP_OLSR_addr, MP_OLSR_valid_time) 349 where: 351 MP_OLSR_addr - it is the network address of the router that runs 352 MP-OLSRv2 Routing Process; 354 MP_OLSR_valid_time - it is the time until which the MP-OLSRv2 355 Router Tuples is considered valid. 357 7.2. Multi-path Routing Set 359 The Multi-path Routing Set records the full path information of 360 different paths to the destination. It consists of Multi-path 361 Routing Tuples: 363 (MR_dest_addr, MR_valid_time, MR_path_set) 364 where: 366 MR_dest_addr - it is the network address of the destination, either 367 the network address of an interface of a destination router or the 368 network address of an attached network; 370 MR_valid_time - it is the time until which the Multi-path Routing 371 Tuples is considered valid; 373 MP_path_set - it contains the multiple paths to the destination. 374 It consists of Path Tuples. 376 Each Path Tuple is defined as: 378 (PT_cost, PT_address[1], PT_address[2], ..., PT_address[n]) 380 where: 382 PT_cost - the cost of the path to the destination; 384 PT_address[1...n] - the addresses of intermediate router to be 385 visited numbered from 1 to n. 387 8. Protocol Details 389 This protocol is based on OLSRv2, and extended to discover multiple 390 disjoint paths from the source to the destination router. It retains 391 the basic routing control packets formats and processing of OLSRv2 to 392 obtain topology information of the network. The main differences 393 between OLSRv2 routing process is the datagram processing at the 394 source router and datagram forwarding. 396 8.1. HELLO and TC Message Generation 398 HELLO and TC messages are generated according to the section 15.1 or 399 section 16.1 of [RFC7181]. 401 A single Message-Type-Specific TLV with Type := MP_OLSRv2 is added to 402 the message. 404 8.2. HELLO and TC Message Processing 406 HELLO and TC messages are processed according to the section 15.3 and 407 16.3 of [RFC7181]. 409 For every HELLO or TC message received, if there exists a TLV with 410 Type := MP_OLSRv2, create or update (if the tuple exists already) the 411 MP-OLSR Router Tuple with 413 o MP_OLSR_addr = originator of the HELLO or TC message 415 and set the MP_OLSR_valid_time := current_time + MP_OLSR_HOLD_TIME. 417 8.3. Datagram Processing at the MP-OLSRv2 Originator 419 When the MP-OLSRv2 routing process receives a datagram from upper 420 layers or interfaces connecting other routing domains, find the 421 Multi-path Routing Tuple where: 423 o MR_dest_addr = destination of the datagram, and 425 o MR_valid_time < current_time. 427 If a matching Multi-path Routing Tuple is found, a Path Tuple is 428 chosen from the MR_path_set in Round-robin fashion (if there are 429 multiple datagrams to be sent). Or else, the Multi-path Dijkstra 430 Algorithm defined in Section 8.4 is invoked, to generate the desired 431 Multi-path Routing Tuple. 433 The addresses in PT_address[1...n] of the chosen Path Tuple are thus 434 added to the datagram header in order as source routing header, 435 following the rules: 437 o Only the addresses exist in MP-OLSR Router Set can be added to the 438 source routing header. 440 o If the length of the path (n) is greater than MAX_SRC_HOPS, only 441 the key routers in the path are kept. By default, the key routers 442 are uniformly chosen in the path. 444 o The routers with higher priority (such as higher willingness of 445 routing) are preferred. 447 o The routers that are considered not appropriate for forwarding 448 indicated by external policies should be avoided. 450 8.4. Multi-path Dijkstra Algorithm 452 The Multi-path Dijkstra Algorithm is invoked when there is no 453 available Multi-path Routing Tuple to a desired destination d. The 454 general principle of the algorithm is at step i to look for the 455 shortest path Pi to the destination d. Based on Dijkstra algorithm, 456 the main modification consists in adding two cost functions namely 457 incremental functions fp and fe in order to prevent the next steps to 458 use similar path. fp is used to increase costs of arcs belonging to 459 the previously path Pi (or which opposite arcs belong to it). This 460 encourages future paths to use different arcs but not different 461 vertices. fe is used to increase costs of the arcs who lead to 462 vertices of the previous path Pi. It is possible to choose different 463 fp and fe to get link-disjoint path or node-disjoint routes as 464 necessary. A recommendation of configuration of fp and fe is given 465 in Section 5. 467 To get NUMBER_OF_PATHS distinct paths, for each path Pi (i = 1, ..., 468 NUMBER_OF_PATHS) do: 470 1. Run Dijkstra algorithm to get the shortest path Pi for the 471 destination d. 473 2. Apply cost function fp to the links in Pi. 475 3. Apply cost function fe to the links who lead to routers used in 476 P. 478 A simple example of Multi-path Dijkstra Algorithm is illustrated in 479 Appendix A. 481 By invoking the algorithm depicted above, NUMBER_OF_PATHS distinct 482 paths is obtained, and added to the Multi-path Routing Set, by 483 creating a Multi-path Routing Tuple with: 485 o MR_dest_addr := destination d 487 o MR_valid_time := current time + MR_HOLD_TIME 489 o Each Path Tuple in the MP_path_set corresponds to a path obtained 490 in multi-path Dijkstra algorithm, with PT_cost := cost of the path 491 to the destination d. 493 8.5. Datagram Forwarding 495 On receiving a datagram with source routing header, the Destination 496 Address field of the IP header is first compared to the addresses of 497 the local interfaces. If a matching local address if found, the 498 datagram is processed as follows: 500 1. Obtain the next source address Address[i] in the source route 501 header. How to obtain the next source address depends on the IP 502 version used. In IPv4, the position of the next source address 503 is indicated by the "pointer" field of the source routing header 504 [RFC0791]. In IPv6, the position is indicated by "Segments Left" 505 field of the source routing header. If no next source address is 506 found, the forwarding process is finished. 508 2. Swap Address[i] and destination address in the IP header. 510 3. Forward the datagram to the destination address according to the 511 OLSRv2 Routing Tuple information through R_local_iface_addr where 513 * R_dest_addr = destination address in the IP header 515 If no matching address is found: 517 o If the Destination Address of the IP header belongs to one of the 518 router's 1-hop symmetric neighbors, the datagram is forwarded to 519 the neighbor router. 521 o Or else, the datagram is forwarded according OLSRv2 routing 522 process. 524 9. Configuration Parameters 526 This section gives default values and guideline for setting 527 parameters defined in Section 5. Network administrator may wish to 528 change certain, or all the parameters for different network 529 scenarios. As an experimental track protocol, the users of this 530 protocol are also encouraged to explore different parameter setting 531 in various network environments, and provide feedback. 533 o NUMBER_OF_PATHS = 3. This parameter defines the number of 534 parallel paths used in datagram forwarding. Setting it to one 535 makes the specification identical to OLSRv2. Setting it to too 536 big value can lead to unnecessary computational overhead and 537 inferior paths. 539 o MAX_SRC_HOPS = 10. 541 o MR_HOLD_TIME = 10 seconds. 543 o fp(c) = 4*c, where c is the original cost of the link. 545 o fe(c) = 2*c, where c is the original cost of the link. 547 The setting of cost functions fp and fc defines the preference of 548 obtained multiple disjoint paths. If id is the identity functions, 3 549 cases are possible: 551 o if id=fe2->5 789 with cost 2 is obtained. 791 The incremental function fp is applied to increase the cost of the 792 link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of 793 the link 1-3, 2-3, 2-4, 4-5, from 1 to 2. 795 On the second run of the Dijkstra algorithm, the second path 796 1->3->4->5 with cost 5 is obtained. 798 Authors' Addresses 800 Jiazi Yi 801 LIX, Ecole Polytechnique 802 91128 Palaiseau Cedex, 803 France 805 Phone: +33 1 77 57 80 85 806 Email: jiazi@jiaziyi.com 807 URI: http://www.jiaziyi.com/ 809 Benoit Parrein 810 University of Nantes 811 IRCCyN lab - IVC team 812 Polytech Nantes, rue Christian Pauc, BP50609 813 44306 Nantes cedex 3 814 France 816 Phone: +33 (0) 240 683 050 817 Email: Benoit.Parrein@polytech.univ-nantes.fr 818 URI: http://www.irccyn.ec-nantes.fr/~parrein