Network Working Group J. Yi Internet-Draft LIX, Ecole Polytechnique Intended status: Experimental B. Parrein Expires: January 1, 2016 University of Nantes June 30, 2015 Multi-path Extension for the Optimized Link State Routing Protocol version 2 (OLSRv2) draft-ietf-manet-olsrv2-multipath-04 Abstract This document specifies a multi-path extension for the Optimized Link State Routing Protocol version 2 (OLSRv2) to discover multiple disjoint paths, so as to improve reliability of the OLSRv2 protocol. The interoperability with OLSRv2 is retained. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on January 1, 2016. Copyright Notice Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as Yi & Parrein Expires January 1, 2016 [Page 1] Internet-Draft Multi-Path OLSRv2 June 2015 described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 7 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 7 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 7 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 8 6.1.1. SR_OLSRv2 TLV . . . . . . . . . . . . . . . . . . . . 8 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 8 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 9 7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 9 7.2. Multi-path Routing Set . . . . . . . . . . . . . . . . . . 9 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 10 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 10 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 10 8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10 8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 11 8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 12 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 14 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 14 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 14 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 15 11. Security Considerations . . . . . . . . . . . . . . . . . . . 15 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 14.1. Normative References . . . . . . . . . . . . . . . . . . . 16 14.2. Informative References . . . . . . . . . . . . . . . . . . 17 Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 18 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 Yi & Parrein Expires January 1, 2016 [Page 2] Internet-Draft Multi-Path OLSRv2 June 2015 1. Introduction The Optimized Link State Routing Protocol version 2 (OLSRv2) [RFC7181] is a proactive link state protocol designed for use in mobile ad hoc networks (MANETs). It generates routing messages periodically to create and maintain a Routing Set, which contains routing information to all the possible destinations in the routing domain. For each destination, there exists a unique Routing Tuple, which indicates the next hop to reach the destination. This document specifies an extension of the OLSRv2 protocol [RFC7181], to provide multiple disjoint paths when appropriate for a source-destination pair. Because of the characteristics of MANETs [RFC2501], especially the dynamic topology, having multiple paths is helpful for increasing network throughput, improving forwarding reliability and load balancing. The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses multi-path Dijkstra algorithm by default to explore multiple disjoint paths from a source router to a destination router based on the topology information obtained through OLSRv2, and forward the datagrams in a load-balancing manner using source routing. MP-OLSRv2 is designed to be interoperable with OLSRv2. 1.1. Motivation and Experiments to Be Conducted This document is an experimental extension of OLSRv2 that can increase the data forwarding reliability in dynamic and high-load MANET scenarios by transmitting datagrams over multiple disjoint paths using source routing. This mechanism is used because: o Disjoint paths can avoid single route failures. o Transmitting datagrams through parallel paths can increase aggregated throughput and provide load balancing. o Certain scenarios require some routers must (or must not) be used. o By having control of the paths at the source, the delay can be provisioned. o A very important application of this extension is combination with Forward Error Correction (FEC) coding. Because the packet drop is normally continuous in a path (for example, due to route failure), FEC coding is less effective in single path routing protocols. By providing multiple disjoint paths, the application of FEC coding with multi-path protocol is more resilient to routing failures. Yi & Parrein Expires January 1, 2016 [Page 3] Internet-Draft Multi-Path OLSRv2 June 2015 While existed deployments, running code and simulations have proven the interest of multi-path extension for OLSRv2 in certain networks, more experiments and experiences are still needed to understand the mechanisms of the protocol. The multi-path extension for OLSRv2 is expected to be revised and improved to the Standard Track, once sufficient operational experience is obtained. Other than general experiences including the protocol specification, interoperability with original OLSRv2 implementations, the experiences in the following aspects are highly appreciated: o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) to be used. This depends on the network topology and router density. o Optimal values for the cost functions. Cost functions are applied to punish the costs of used links and nodes so as to obtain disjoint paths. What kind of disjointness is desired (node- disjoint or link-disjoint) may depends on the layer 2 protocol used, and can be achieved by setting different sets of cost functions. o Use of other metrics other than hop-count. This multi-path extension can be used not only for hop-count metric type, but also other metric types that meet the requirement of OLSRv2, such as [I-D.ietf-manet-olsrv2-dat-metric]. The metric type used has also co-relation with the choice of cost functions as indicated in the previous bullet. o Optimal choice of "key" routers for loose source routing. In some cases, loose source routing is used to reduce overhead or for interoperability with OLSRv2 routers. Other than the basic rules defined in the following of this document, optimal choices of routers to put in the loose source routing header can be further studied. o Different path-selection schedulers. By default, Round-Robin scheduling is used to select a path to be used for a datagram. In some scenarios, weighted scheduling can be considered: for example, the paths with lower costs (higher path quality) can transfer more datagrams compared to paths with higher costs. o The impacts of the delay variation due to multi-path routing. [RFC2991] brings out some concerns of multi-path routing, especially variable latencies. Although current experiments result show that multi-path routing can reduce the jitter in dynamic scenarios, some transport protocols or applications may be sensitive to the datagram re-ordering. Yi & Parrein Expires January 1, 2016 [Page 4] Internet-Draft Multi-Path OLSRv2 June 2015 o The disjoint multi-path protocol has interesting application with Forward Error Correction (FEC) Coding, especially for services like video/audio streaming. The combination of FEC coding mechanisms and this extension is thus encouraged. By applying FEC coding, the issue of packet re-ordering can be alleviated. o Other algorithms to obtain multiple paths, other than the default Multi-path Dijkstra algorithm introduced in this specification. o In addition to IP source routing based approach, it can be interesting to try multi-path routing in MANET using label- switched flow in the future. o The use of multi-topology information. By using [I-D.ietf-manet-olsrv2-multitopology], multiple topologies using different metric types can be obtained. It is encouraged to experiment the use of multiple metrics for building multiple paths also. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. This document uses the terminology and notation defined in [RFC5444], [RFC6130], [RFC7181]. Additionally, it defines the following terminology: OLSRv2 Routing Process - The routing process based on [RFC7181], without multi-path extension specified in this document. MP-OLSRv2 Routing Process - The routing process based on this specification as an extension to [RFC7181]. 3. Applicability Statement As an extension of OLSRv2, this specification is applicable to MANETs for which OLSRv2 is applicable (see [RFC7181]). It can operate on single, or multiple interfaces, to discover multiple disjoint paths from a source router to a destination router. MP-OLSRv2 is specially designed for networks with dynamic topology and low data rate links. By providing multiple paths, higher aggregated throughput can be obtained, and the routing process is Yi & Parrein Expires January 1, 2016 [Page 5] Internet-Draft Multi-Path OLSRv2 June 2015 more robust to packet loss. In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily replace OLSRv2 completely. The extension can be applied for certain applications that are suitable for multi-path routing (mainly video or audio streams), based on the information such as DiifServ Code Point [RFC2474]. Compared to OLSRv2, this extension does not introduce new message type in the air. A new Message TLV type is introduced to identify the routers that support forwarding based on source route header. It is interoperable with OLSRv2 implementations that do not have this extension. MP-OLSRv2 forwards datagrams using the source routing header. Depending on the IP version used, the source routing header is formatted according to [RFC0791] or [RFC6554]. 4. Protocol Overview and Functioning This specification requires OLSRv2 [RFC7181] to: o Identify all the reachable routers in the network. o Identify a sufficient subset of links in the networks, so that routes can be calculated to all reachable destinations. o Provide a Routing Set containing shortest routes from this router to all destinations. In addition, the MP-OLSRv2 Routing Process identifies the routers that support source routing by adding a new Message TLV in HELLO and TC messages. Based on the above information acquired, every MP- OLSRv2 Routing Process is aware of a reduced topology map of the network and the routers supporting source routing. A multi-path algorithm is invoked on demand, i.e., only when there is datagram to be sent from the source to the destination, and there is no available routing tuple in the Multi-path Routing Set. The multi- path Dijkstra algorithm can generate multiple disjoint paths from a source to a destination, and such information is kept in Multi-path Routing Set. The datagram is forwarded based on source routing. When there is a datagram to be sent to a destination, the source router acquires a path from the Multi-path Routing Set (MAY be Round-Robin, or other scheduling algorithms). The path information is stored in the Yi & Parrein Expires January 1, 2016 [Page 6] Internet-Draft Multi-Path OLSRv2 June 2015 datagram header as source routing header. All the intermediate routers are listed in the source routing header (SRH), unless there are routers that do not support source-route forwarding in the paths, or the paths are too long to be fully stored in the SRH -- in which case, loose source routing is used. The intermediate routers listed in the SRH read the SRH and forward the datagram to the next hop as indicated in the SRH. 5. Parameters and Constants In addition to the parameters and constants defined in [RFC7181], this specification uses the parameters and constants described in this section. 5.1. Router Parameters NUMBER_OF_PATHS The number of paths desired by the router. MAX_SRC_HOPS The maximum number of hops allowed to be put in the source routing header. fp Incremental function of multi-path Dijkstra algorithm. It is used to increase costs of links belonging to the previously computed path. fe Incremental function of multi-path Dijkstra algorithm. It is used to increase costs of links that lead to routers of the previous computed path. MR_HOLD_TIME It is the minimal time that a Multi-path Routing Tuple SHOULD be kept in the Multi-path Routing Set. SR_OLSR_HOLD_TIME It is the minimal time that a SR-OLSRv2 Router Tuple SHOULD be kept in the SR-OLSRv2 Router Set. 6. Packets and Messages This extension employs the routing control messages HELLO and TC (Topology Control) as defined in OLSRv2 [RFC7181]. To support source routing, a source routing header is added to each datagram routed by this extension. Depending on the IP version used, the source routing header is defined in following of this section. Yi & Parrein Expires January 1, 2016 [Page 7] Internet-Draft Multi-Path OLSRv2 June 2015 6.1. HELLO and TC messages HELLO and TC messages used by MP-OLSRv2 Routing Process share the same format as defined in [RFC7181]. In addition, a new Message TLV type is defined, to identify the originator of the HELLO or TC message that supports source route forwarding. The new Message TLV type is introduced for the interoperability between OLSRv2 and MP- OLSRv2: only the routers supporting source-route forwarding can be used in the source routing header of a datagram, because adding an router that does not understand the source routing header will cause routing failure. 6.1.1. SR_OLSRv2 TLV SR_OLSRv2 TLV is a Message TLV that signals the message is generated by a router that supports source-route forwarding. It can be an MP- OLSRv2 Routing Process, or an OLSRv2 Routing Process that support source-route forwarding. The SR_OLSRv2 TLV does not include any value. Every HELLO or TC message generated by a MP-OLSRv2 Routing Process MUST have one SR_OLSRv2 TLV. Every HELLO or TC message generate by a OLSRv2 Routing Process MAY have one SR_OLSRv2 TLV, if the OLSRv2 Routing Process supports source-route forwarding, and is willing to join the source route generated by other MP-OLSRv2 Routing Processes. The existence of SR_OLSRv2 TLV MUST be consistent for a specific OLSRv2 Routing Process, i.e., either it adds SR_OLSRv2 TLV to all its HELLO/TC messages, or it does not add SR_OLSRv2 TLV to any HELLO/TC message. 6.2. Datagram 6.2.1. Source Routing Header in IPv4 In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs loose source routing header, as defined in [RFC0791]. It exists as an option header, with option class 0, and option number 3. The source route information is kept in the "route data" field of the loss source route header. 6.2.2. Source Routing Header in IPv6 In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the source routing header as defined in [RFC6554], with IPv6 Routing Type 3. Yi & Parrein Expires January 1, 2016 [Page 8] Internet-Draft Multi-Path OLSRv2 June 2015 The source route information is kept in the "Addresses" field of the routing header. 7. Information Bases Each MP-OLSRv2 routing process maintains the information bases as defined in [RFC7181]. Additionally, two more information bases are defined for this specification. 7.1. SR-OLSRv2 Router Set The SR-OLSRv2 Router Set records the routers that supports source- route forwarding. It can be routers that run MP-OLSRv2 Routing Process, or OLSRv2 Routing Process with source-route forwarding support. It consists of SR-OLSRv2 Router Tuples: (SR_OLSR_addr, SR_OLSR_valid_time) where: SR_OLSR_addr - it is the network address of the router that supports source-route forwarding; SR_OLSR_valid_time - it is the time until which the SR-OLSRv2 Router Tuples is considered valid. 7.2. Multi-path Routing Set The Multi-path Routing Set records the full path information of different paths to the destination. It consists of Multi-path Routing Tuples: (MR_dest_addr, MR_valid_time, MR_path_set) where: MR_dest_addr - it is the network address of the destination, either the network address of an interface of a destination router or the network address of an attached network; MR_valid_time - it is the time until which the Multi-path Routing Tuples is considered valid; MP_path_set - it contains the multiple paths to the destination. It consists of Path Tuples. Each Path Tuple is defined as: Yi & Parrein Expires January 1, 2016 [Page 9] Internet-Draft Multi-Path OLSRv2 June 2015 (PT_cost, PT_address[1], PT_address[2], ..., PT_address[n]) where: PT_cost - the cost of the path to the destination; PT_address[1...n] - the addresses of intermediate routers to be visited numbered from 1 to n. 8. Protocol Details This protocol is based on OLSRv2, and extended to discover multiple disjoint paths from a source router to a destination router. It retains the basic routing control packets formats and processing of OLSRv2 to obtain topology information of the network. The main differences between OLSRv2 routing process are the datagram processing at the source router and datagram forwarding. 8.1. HELLO and TC Message Generation HELLO and TC messages are generated according to the section 15.1 or section 16.1 of [RFC7181]. A single Message TLV with Type := SR_OLSRv2 MUST be added to the message. 8.2. HELLO and TC Message Processing HELLO and TC messages are processed according to the section 15.3 and 16.3 of [RFC7181]. For every HELLO or TC message received, if there exists a Message TLV with Type := SR_OLSRv2, create or update (if the tuple exists already) the SR-OLSR Router Tuple with o SR_OLSR_addr = originator of the HELLO or TC message and set the SR_OLSR_valid_time := current_time + SR_OLSR_HOLD_TIME. 8.3. Datagram Processing at the MP-OLSRv2 Originator When the MP-OLSRv2 routing process receives a datagram from upper layers or interfaces connecting other routing domains, find the Multi-path Routing Tuple where: o MR_dest_addr = destination of the datagram, and Yi & Parrein Expires January 1, 2016 [Page 10] Internet-Draft Multi-Path OLSRv2 June 2015 o MR_valid_time < current_time. If a matching Multi-path Routing Tuple is found, a Path Tuple is chosen from the MR_path_set in Round-robin fashion (if there are multiple datagrams to be sent). Or else, the multi-path algorithm defined in Section 8.4 is invoked, to generate the desired Multi-path Routing Tuple. The addresses in PT_address[1...n] of the chosen Path Tuple are thus added to the datagram header as source routing header, following the rules: o Only the addresses exist in SR-OLSR Router Set can be added to the source routing header. o If the length of the path (n) is greater than MAX_SRC_HOPS, only the key routers in the path are kept. By default, the key routers are uniformly chosen in the path. o The routers with higher priority (such as higher routing willingness) are preferred. o The routers that are considered not appropriate for forwarding indicated by external policies should be avoided. 8.4. Multi-path Dijkstra Algorithm A multi-path algorithm is invoked when there is no available Multi- path Routing Tuple to a desired destination d to obtain the multiple paths. This section introduces Multi-path Dijkstra Algorithm as a default mechanism. It tries to obtain disjoint paths when appropriate, but does not guarantee strict disjoint paths. The rationale is explained in Appendix A. The use of other algorithms is not prohibited, as long as they can provide a full path from the source to the destination router. Using different multi-path algorithms will not impact the interoperability. The general principle of the Multi-path Dijkstra Algorithm is at step i to look for the shortest path Pi to the destination d. Based on Dijkstra algorithm, the main modification consists in adding two cost functions namely incremental functions fp and fe in order to prevent the next steps to use similar path. fp is used to increase costs of arcs belonging to the previously path Pi (or which opposite arcs belong to it). This encourages future paths to use different arcs but not different vertices. fe is used to increase costs of the arcs who lead to vertices of the previous path Pi. It is possible to choose different fp and fe to get link-disjoint path or node-disjoint Yi & Parrein Expires January 1, 2016 [Page 11] Internet-Draft Multi-Path OLSRv2 June 2015 routes as necessary. A recommendation of configuration of fp and fe is given in Section 5. To get NUMBER_OF_PATHS distinct paths, for each path Pi (i = 1, ..., NUMBER_OF_PATHS) do: 1. Run Dijkstra algorithm to get the shortest path Pi for the destination d. 2. Apply cost function fp to the links in Pi. 3. Apply cost function fe to the links who lead to routers used in P. A simple example of Multi-path Dijkstra Algorithm is illustrated in Appendix A. By invoking the algorithm depicted above, NUMBER_OF_PATHS distinct paths are obtained and added to the Multi-path Routing Set, by creating a Multi-path Routing Tuple with: o MR_dest_addr := destination d o MR_valid_time := current time + MR_HOLD_TIME o Each Path Tuple in the MP_path_set corresponds to a path obtained in multi-path Dijkstra algorithm, with PT_cost := cost of the path to the destination d. 8.5. Datagram Forwarding On receiving a datagram with source routing header, the Destination Address field of the IP header is first compared to the addresses of the local interfaces. If a matching local address if found, the datagram is processed from Step 1 to Step 4 as follows. Or else, the datagram is processed from Step 3 to Step 4. 1. Obtain the next source address Address[i] in the source route header. How to obtain the next source address depends on the IP version used. In IPv4, the position of the next source address is indicated by the "pointer" field of the source routing header [RFC0791]. In IPv6, the position is indicated by "Segments Left" field of the source routing header. If no next source address is found, the forwarding process is finished. 2. Swap Address[i] and destination address in the IP header. Yi & Parrein Expires January 1, 2016 [Page 12] Internet-Draft Multi-Path OLSRv2 June 2015 3. If the Destination Address of the IP header belongs to one of the router's 1-hop symmetric neighbors, the datagram is forwarded to the neighbor router. Or else: 4. Forward the datagram to the destination address according to the OLSRv2 Routing Tuple information through R_local_iface_addr where * R_dest_addr = destination address in the IP header 9. Configuration Parameters This section gives default values and guideline for setting parameters defined in Section 5. Network administrator may wish to change certain, or all the parameters for different network scenarios. As an experimental track protocol, the users of this protocol are also encouraged to explore different parameter setting in various network environments, and provide feedback. o NUMBER_OF_PATHS = 3. This parameter defines the number of parallel paths used in datagram forwarding. Setting it to one makes the specification identical to OLSRv2. Setting it to too big value can lead to unnecessary computational overhead and inferior paths. o MAX_SRC_HOPS = 10. o MR_HOLD_TIME = 10 seconds. o MP_OLSR_HOLD_TIME = 10 seconds. o fp(c) = 4*c, where c is the original cost of the link. o fe(c) = 2*c, where c is the original cost of the link. The setting of cost functions fp and fc defines the preference of obtained multiple disjoint paths. If id is the identity functions, 3 cases are possible: o if id=fe2->5 with cost 2 is obtained. The incremental function fp is applied to increase the cost of the link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of the link 1-3, 2-3, 2-4, 4-5, from 1 to 2. On the second run of the Dijkstra algorithm, the second path 1->3->4->5 with cost 5 is obtained. Yi & Parrein Expires January 1, 2016 [Page 18] Internet-Draft Multi-Path OLSRv2 June 2015 As mentioned in Section 8.4, the Multi-path Dijkstra Algorithm does not guarantee strict disjoint path to avoid choosing inferior paths. For example, given the topology in Figure 2, two paths from node S to D are desired. If a algorithm tries to obtain strict disjoint paths, the two paths obtained will be S--B--D and S--50 hops--D, which are extremely unbalanced. It is undesired because it will cause huge delay variance between the paths. By using the Multi-path Dijkstra algorithm, which is based on the punishing scheme, S--B--D and S--B--C--D will be obtained. ---50 hops------- / \ / \ S----B--------------D \ / \---C-----/ Figure 2 Authors' Addresses Jiazi Yi LIX, Ecole Polytechnique 91128 Palaiseau Cedex, France Phone: +33 1 77 57 80 85 Email: jiazi@jiaziyi.com URI: http://www.jiaziyi.com/ Benoit Parrein University of Nantes IRCCyN lab - IVC team Polytech Nantes, rue Christian Pauc, BP50609 44306 Nantes cedex 3 France Phone: +33 (0) 240 683 050 Email: Benoit.Parrein@polytech.univ-nantes.fr URI: http://www.irccyn.ec-nantes.fr/~parrein Yi & Parrein Expires January 1, 2016 [Page 19]