idnits 2.17.1 draft-yi-manet-olsrv2-multipath-02.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 29, 2014) is 3559 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 375 -- Looks like a reference, but probably isn't: '2' on line 375 == Outdated reference: A later version (-12) exists of draft-ietf-manet-olsrv2-dat-metric-01 == 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: January 30, 2015 University of Nantes 6 July 29, 2014 8 Multi-path Extension for the Optimized Link State Routing Protocol 9 version 2 (OLSRv2) 10 draft-yi-manet-olsrv2-multipath-02 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 January 30, 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 . . . . . . . . . . . . 7 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 . . . . . . . . . . . . . . . . . . . . 12 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 . . . . . . . . . . . 13 80 11. Security Considerations . . . . . . . . . . . . . . . . . . . 14 81 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 82 12.1. HELLO Message-Type-Specific TLV Type Registries . . . . . 14 83 12.2. TC Message-Type-Specific TLV Type Registries . . . . . . . 14 84 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 85 13.1. Normative References . . . . . . . . . . . . . . . . . . . 15 86 13.2. Informative References . . . . . . . . . . . . . . . . . . 15 87 Appendix A. An example of Multi-path Dijkstra Algorithm . . . . . 16 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 17 90 1. Introduction 92 The Optimized Link State Routing Protocol version 2 (OLSRv2) 93 [RFC7181] is a proactive link state protocol designed for use in 94 mobile ad hoc networks (MANETs). It generates routing messages 95 periodically to create and maintain a Routing Set, which contains 96 routing information to all the possible destinations in the routing 97 domain. For each destination, there exists an unique Routing Tuple, 98 which indicates the next hop to reach the destination. 100 This document specifies an extension of the OLSRv2 protocol 101 [RFC7181], to provide multiple disjoint paths for a source- 102 destination pair. Because of the characteristics of MANETs 103 [RFC2501], especially the dynamic topology, having multiple paths is 104 helpful for increasing network throughput, improving transmission 105 reliability and load balancing. 107 The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses 108 multi-path Dijkstra algorithm to explore multiple disjoint paths from 109 source to the destination based on the topology information obtained 110 through OLSRv2, and forward the datagrams in a load-balancing manner 111 using source routing. MP-OLSRv2 is designed to be interoperable with 112 OLSRv2. 114 1.1. Motivation and Experiments to Be Conducted 116 This document is an experimental extension of OLSRv2 that can 117 increase the data forwarding reliability in dynamic and high-load 118 MANET scenarios by transmitting packet over multiple disjoint paths 119 using source routing. This mechanism is used because: 121 o Disjoint paths can avoid single route failure. 123 o By having control of that paths at the source, the delay can be 124 provisioned. 126 o Certain scenarios require some routers must (or must not) be used. 128 o An very important application of this extension is combination 129 with Forward Error Correction coding. This requires disjoint 130 paths. The single path routing is not adapted because the packet 131 drop is normally continuous, in which forward correction coding is 132 not helpful. 134 While existed deployments, running code and simulations have proven 135 the interest of multipath extension for OLSRv2 in certain networks, 136 more experiments and experiences are still needed to understand the 137 mechanisms of the protocol. The multipath extension for OLSRv2 is 138 expected to be revised and improved to the Standard Track, once 139 sufficient operational experience is obtained. Other than the 140 general experiences including the protocol specification, 141 interoperability with original OLSRv2 implementations, the 142 experiences in the following aspects are highly appreciated: 144 o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) 145 to be used. This depends on the network topology and router 146 density. 148 o Optimal values for the cost functions. Cost functions are applied 149 to punish the costs of used links and nodes so as to obtain 150 disjoint paths. What kind of disjointness is desired (node- 151 disjoint or link-disjoint) may depends on the layer 2 protocol 152 used, and can be achieved by setting different sets of cost 153 functions. 155 o Optimal choice of "key" routers for loose source routing. In some 156 cases, loose source routing is use to reduce overhead or for 157 interoperability with OLSRv2. Other than the basic rules defined 158 in the following of this document, optimal choices of routers to 159 put in the source routing header can be further studied. 161 o Use of other metric other than hop-count. This multipath 162 extension can be used not only for hop-count metric type, but 163 other 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. 168 o The impacts to the delay variation due to multi-path routing. 169 [RFC2991] brings out some concerns of multi-path routing, 170 especially variable latencies. Although current experiments 171 result show that multi-path routing can reduce the jitter in 172 dynamic scenarios, some transport protocols or applications may be 173 sensitive to the packet re-ordering. 175 o The disjoint multiple path protocol has interesting application 176 with Forward Error Correction (FEC) Coding, especially for 177 services like video/audio streaming. The combination of FEC 178 coding mechanisms and this extension is thus encouraged. 180 o In addition to IP source routing based approach, it can be 181 interesting to try multi-path routing in MANET using label- 182 switched flow in the future. 184 o The usage of multi-topology information. By using 185 [I-D.ietf-manet-olsrv2-multitopology], multiple topologies using 186 different metric types can be obtained. It is encouraged to 187 experiment the use of multiple metrics for building multiple paths 188 also. 190 2. Terminology 192 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 193 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 194 "OPTIONAL" in this document are to be interpreted as described in 195 [RFC2119]. 197 This document uses the terminology and notation defined in [RFC5444], 198 [RFC6130], [RFC7181]. Additionally, it defines the following 199 terminology: 201 OLSRv2 Routing Process - The routing process based on [RFC7181], 202 without multi-path extension specified in this document. 204 MP-OLSRv2 Routing Process - The routing process based on this 205 specification as an extension to [RFC7181]. 207 3. Applicability Statement 209 As an extension of OLSRv2, this specification is applicable to MANETs 210 for which OLSRv2 is applicable (see [RFC7181]). It can operate on 211 single, or multiple interfaces, to discover multiple disjoint paths 212 from a source router to a destination router. 214 MP-OLSRv2 is specially designed for networks with dynamic topology 215 and slow data rate links. By providing multiple paths, higher 216 aggregated bandwidth can be obtained, and the routing process is more 217 robust to packet loss. 219 In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily 220 replace OLSRv2 completely. The extension can be applied for certain 221 applications that are suitable for multi-path routing (mainly video 222 or audio streams), based on the information such as DiifServ Code 223 Point [RFC2474]. 225 Compared to OLSRv2, this extension does not introduce new message 226 type in the air, and is interoperable with OLSRv2 implementations 227 that do not have this extension. 229 4. Protocol Overview and Functioning 231 This specification requires OLSRv2 [RFC7181] to: 233 o Identify all the reachable routers in the network. 235 o Identify a sufficient subset of links in the networks, so that 236 routes can be calculated to all reachable destinations. 238 o Provide a Routing Set containing shortest routes from this router 239 to all destinations. 241 Based on the above information acquired by OLSRv2, the MP-OLSRv2 242 Routing Process is able to calculate multiple paths to certain 243 destinations based on multi-path Dijkstra algorithm: the Dijkstra 244 algorithm is performed multiple times . In each iteration, the cost 245 of used links are increased (i.e., punished), so that they can be 246 avoided to be chosen in the next iteration. The multi-path Dijkstra 247 algorithm can generate multiple disjoint paths from a source to a 248 destination , and such information is kept in Multi-path Routing Set. 249 The algorithm is invoked on demand, i.e., only when there is data 250 traffic to be sent from the source to the destination, and there is 251 no available routing tuples in the Multi-path Routing Set. 253 The datagram is forwarded based on source routing. When there is a 254 datagram to be sent to a destination, the source router acquires a 255 path from the Multi-path Routing Set (in Round-Robin fashion here) . 256 The path information is stored in the datagram header as source 257 routing header. The intermediate routers listed in the source 258 routing header (SRH) read the SRH and forward the datagram to the 259 next hop indicated in the SRH. 261 5. Parameters and Constants 263 In addition to the parameters and constants defined in [RFC7181], 264 this specification uses the parameters and constants described in 265 this section. 267 5.1. Router Parameters 269 NUMBER_OF_PATHS The number of paths desired by the router. 271 MAX_SRC_HOPS The maximum number of hops allowed to put in the 272 source routing header. 274 fp Incremental function of multi-path Dijkstra algorithm. It is 275 used to increase costs of links belonging to the previously 276 computed path. 278 fe Incremental function of multi-path Dijkstra algorithm. It is 279 used to increase costs of links who lead to routers of the 280 previous computed path. 282 MR_HOLD_TIME It is the minimal time that a Multi-path Routing Tuple 283 SHOULD be kept in the Multi-path Routing Set. 285 MP_OLSR_HOLD_TIME It is the minimal time that a MP-OLSRv2 Router 286 Tuple SHOULD be kept in the MP-OLSRv2 Router Set. 288 6. Packets and Messages 290 This extension employs the routing control messages HELLO and TC 291 (Topology Control) as defined in OLSRv2 [RFC7181]. To support source 292 routing, a source routing header is added to each datagram routed by 293 this extension. Depending on the IP version used, the source routing 294 header is defined in following of this section. 296 6.1. HELLO and TC messages 298 HELLO and TC messages used by MP-OLSRv2 Routing Process share the 299 same format as defined in [RFC7181]. In addition, one Message TLV is 300 defined, to identify the originator of the HELLO or TC message is 301 running MP-OLSRv2. 303 6.1.1. MP_OLSRv2 TLV 305 An MP_OLSRv2 TLV is a Message TLV that signals the message is 306 generated by an MP-OLSRv2 Routing Process. It does not include any 307 value. 309 Every HELLO or TC message generated by MP-OLSRv2 Routing Process MUST 310 has one MP_OLSRv2 TLV. 312 6.2. Datagram 314 6.2.1. Source Routing Header in IPv4 316 In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs 317 loose source routing, as defined in [RFC0791]. It exists as an 318 option header, with option class 0, and option number 3. 320 The source route information is kept in the "route data" field of the 321 loss source route header. 323 6.2.2. Source Routing Header in IPv6 325 In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the 326 source routing header as defined in [RFC6554], with IPv6 Routing Type 327 3. 329 The source route information is kept in the "Addresses" field of the 330 routing header. 332 7. Information Bases 334 Each MP-OLSRv2 routing process maintains the information bases as 335 defined in [RFC7181]. Additionally, two more information bases are 336 defined for this specification. 338 7.1. MP-OLSRv2 Router Set 340 The MP-OLSRv2 Router Set recordes the routers running the MP-OLSRv2 341 Routing Process. It consists of MP-OLSRv2 Router Tuples: 343 (MP_OLSR_addr, MP_OLSR_valid_time) 345 where: 347 MP_OLSR_addr - it is the network address of the router that runs 348 MP-OLSRv2 Routing Process; 350 MP_OLSR_valid_time - it is the time until which the MP-OLSRv2 351 Router Tuples is considered valid. 353 7.2. Multi-path Routing Set 355 The Multi-path Routing Set records the full path information of 356 different paths to the destination. It consists of Multi-path 357 Routing Tuples: 359 (MR_dest_addr, MR_valid_time, MR_path_set) 361 where: 363 MR_dest_addr - it is the network address of the destination, either 364 the network address of an interface of a destination router or the 365 network address of an attached network; 367 MR_valid_time - it is the time until which the Multi-path Routing 368 Tuples is considered valid; 370 MP_path_set - it contains the multiple paths to the destination. 371 It consists of Path Tuples. 373 Each Path Tuple is defined as: 375 (PT_cost, PT_address[1], PT_address[2], ..., PT_address[n]) 377 where: 379 PT_cost - the cost of the path to the destination; 381 PT_address[1...n] - the addresses of intermediate router to be 382 visited numbered from 1 to n. 384 8. Protocol Details 386 This protocol is based on OLSRv2, and extended to discover multiple 387 disjoint paths from the source to the destination router. It retains 388 the basic routing control packets formats and processing of OLSRv2 to 389 obtain topology information of the network. The main differences 390 between OLSRv2 routing process is the datagram processing at the 391 source router and datagram forwarding. 393 8.1. HELLO and TC Message Generation 395 HELLO and TC messages are generated according to the section 15.1 or 396 section 16.1 of [RFC7181]. 398 A single Message-Type-Specific TLV with Type := MP_OLSRv2 is added to 399 the message. 401 8.2. HELLO and TC Message Processing 403 HELLO and TC messages are processed according to the section 15.3 and 404 16.3 of [RFC7181]. 406 For every HELLO or TC message received, if there exists a TLV with 407 Type := MP_OLSRv2, create or update (if the tuple exists already) the 408 MP-OLSR Router Tuple with 410 o MP_OLSR_addr = originator of the HELLO or TC message 412 and set the MP_OLSR_valid_time := current_time + MP_OLSR_HOLD_TIME. 414 8.3. Datagram Processing at the MP-OLSRv2 Originator 416 When the MP-OLSRv2 routing process receives a datagram from upper 417 layers or interfaces connecting other routing domains, find the 418 Multi-path Routing Tuple where: 420 o MR_dest_addr = destination of the datagram, and 422 o MR_valid_time < current_time. 424 If a matching Multi-path Routing Tuple is found, a Path Tuple is 425 chosen from the MR_path_set in Round-robin fashion (if there are 426 multiple datagrams to be sent). Or else, the Multi-path Dijkstra 427 Algorithm defined in Section 8.4 is invoked, to generate the desired 428 Multi-path Routing Tuple. 430 The addresses in PT_address[1...n] of the chosen Path Tuple are thus 431 added to the datagram header in order as source routing header, 432 following the rules: 434 o Only the addresses exist in MP-OLSR Router Set can be added to the 435 source routing header. 437 o If the length of the path (n) is greater than MAX_SRC_HOPS, only 438 the key routers in the path are kept. By default, the key routers 439 are uniformly chosen in the path. 441 o The routers with higher priority (such as higher willingness of 442 routing) are preferred. 444 o The routers that are considered not appropriate for forwarding 445 indicated by external policies should be avoided. 447 8.4. Multi-path Dijkstra Algorithm 449 The Multi-path Dijkstra Algorithm is invoked when there is no 450 available Multi-path Routing Tuple to a desired destination d. The 451 general principle of the algorithm is at step i to look for the 452 shortest path Pi to the destination d. Based on Dijkstra algorithm, 453 the main modification consists in adding two cost functions namely 454 incremental functions fp and fe in order to prevent the next steps to 455 use similar path. fp is used to increase costs of arcs belonging to 456 the previously path Pi (or which opposite arcs belong to it). This 457 encourages future paths to use different arcs but not different 458 vertices. fe is used to increase costs of the arcs who lead to 459 vertices of the previous path Pi. It is possible to choose different 460 fp and fe to get link-disjoint path or node-disjoint routes as 461 necessary. A recommendation of configuration of fp and fe is given 462 in Section 5. 464 To get NUMBER_OF_PATHS distinct paths, for each path Pi (i = 1, ..., 465 NUMBER_OF_PATHS) do: 467 1. Run Dijkstra algorithm to get the shortest path Pi for the 468 destination d. 470 2. Apply cost function fp to the links in Pi. 472 3. Apply cost function fe to the links who lead to routers used in 473 P. 475 A simple example of Multi-path Dijkstra Algorithm is illustrated in 476 Appendix A. 478 By invoking the algorithm depicted above, NUMBER_OF_PATHS distinct 479 paths is obtained, and added to the Multi-path Routing Set, by 480 creating a Multi-path Routing Tuple with: 482 o MR_dest_addr := destination d 484 o MR_valid_time := current time + MR_HOLD_TIME 486 o Each Path Tuple in the MP_path_set corresponds to a path obtained 487 in multi-path Dijkstra algorithm, with PT_cost := cost of the path 488 to the destination d. 490 8.5. Datagram Forwarding 492 On receiving a datagram with source routing header, the Destination 493 Address field of the IP header is first compared to the addresses of 494 the local interfaces. If no matching address is found, the datagram 495 is forwarded according OLSRv2 routing process. If a matching local 496 address if found, the datagram is processed as follows: 498 1. Obtain the next source address Address[i] in the source route 499 header. How to obtain the next source address depends on the IP 500 version used. In IPv4, the position of the next source address 501 is indicated by the "pointer" field of the source routing header 502 [RFC0791]. In IPv6, the position is indicated by "Segments Left" 503 field of the source routing header. If no next source address is 504 found, the forwarding process is finished. 506 2. Swap Address[i] and destination address in the IP header. 508 3. Forward the datagram to the destination address according to the 509 OLSRv2 Routing Tuple information through R_local_iface_addr where 510 * R_dest_addr = destination address in the IP header 512 9. Configuration Parameters 514 This section gives default values and guideline for setting 515 parameters defined in Section 5. Network administrator may wish to 516 change certain, or all the parameters for different network 517 scenarios. As an experimental track protocol, the users of this 518 protocol are also encouraged to explore different parameter setting 519 in various network environments, and provide feedback. 521 o NUMBER_OF_PATHS = 3. This parameter defines the number of 522 parallel paths used in datagram forwarding. Setting it to one 523 makes the specification identical to OLSRv2. Setting it to too 524 big value can lead to unnecessary computational overhead and 525 inferior paths. 527 o MAX_SRC_HOPS = 10. 529 o MR_HOLD_TIME = 10 seconds. 531 o fp(c) = 4*c, where c is the original cost of the link. 533 o fe(c) = 2*c, where c is the original cost of the link. 535 The setting of cost functions fp and fc defines the preference of 536 obtained multiple disjoint paths. If id is the identity functions, 3 537 cases are possible: 539 o if id=fe2->5 744 with cost 2 is obtained. 746 The incremental function fp is applied to increase the cost of the 747 link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of 748 the link 1-3, 2-3, 2-4, 4-5, from 1 to 2. 750 On the second run of the Dijkstra algorithm, the second path 751 1->3->4->5 with cost 5 is obtained. 753 Authors' Addresses 755 Jiazi Yi 756 LIX, Ecole Polytechnique 757 91128 Palaiseau Cedex, 758 France 760 Phone: +33 1 77 57 80 85 761 Email: jiazi@jiaziyi.com 762 URI: http://www.jiaziyi.com/ 764 Benoit Parrein 765 University of Nantes 766 IRCCyN lab - IVC team 767 Polytech Nantes, rue Christian Pauc, BP50609 768 44306 Nantes cedex 3 769 France 771 Phone: +33 (0) 240 683 050 772 Email: Benoit.Parrein@polytech.univ-nantes.fr 773 URI: http://www.irccyn.ec-nantes.fr/~parrein