Internet Engineering Task Force A. Szwabe Internet-Draft A. Nowak, Ed. Intended status: Experimental Poznan University of Technology Expires: November 3, 2011 E. Baccelli INRIA J. Yi B. Parrein Nantes University May 2, 2011 Multi-path for Optimized Link State Routing Protocol version 2 draft-szwabe-manet-multipath-olsrv2-02 Abstract This document specifies an extension of the OLSRv2 protocol providing methods to compute multiple paths for each destination, when such paths are available. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, and it may not be published except as an Internet-Draft. 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 November 3, 2011. Copyright Notice Copyright (c) 2011 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 Szwabe, et al. Expires November 3, 2011 [Page 1] Internet-Draft Multi-path for OLSRv2 May 2011 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 described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 3 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 4 5. Proactive Multi-path Computation with OLSRv2 . . . . . . . . . 4 5.1. Optimization using MPR Selection . . . . . . . . . . . . . 5 6. On-demand Multi-path Computation with OLSRv2 . . . . . . . . . 5 6.1. Route Recovery Mechnanism . . . . . . . . . . . . . . . . 7 7. Loop Detection Mechanisms . . . . . . . . . . . . . . . . . . 7 8. Security Considerations . . . . . . . . . . . . . . . . . . . 8 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 11.1. Normative References . . . . . . . . . . . . . . . . . . . 9 11.2. Informative References . . . . . . . . . . . . . . . . . . 9 Appendix A. Example of Proactive Multi-path Algorithm Execution . . . . . . . . . . . . . . . . . . . . . . 10 Appendix B. Example of on-demand Multi-path Execution . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 Szwabe, et al. Expires November 3, 2011 [Page 2] Internet-Draft Multi-path for OLSRv2 May 2011 1. Introduction This document specifies a lightweight extension of the OLSRv2 protocol [I-D.ietf-manet-olsrv2], providing multiple paths for each destination, when such paths are available. Multi-path routing increases reliability by detecting the availability of redundant paths. OLSRv2, in its basic specification, does not provide multiple routes for a given destination. On the other hand, the protocol provides every router with enough information to compute multiple routes to any specific destination, if available. Information about multiple paths per source-destination pair enables more successful end-to-end transmissions in a frequently changing network environment (e.g. in the case of a sudden breakdown of a relaying router), and favors throughput maximization in the case when multiple parallel transmissions without interferences (i.e., appropriately distinct to each other) enable bypassing a network capacity bottleneck ([GNT06], [SS08], [SM09]). 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 RFC 2119 [RFC2119]. All terms introduced in [RFC6130], including "interface", "network address", "1-hop neighbor", "symmetric 1-hop neighbor" are to be interpreted as described there. All terms introduced in [I-D.ietf-manet-olsrv2], including the terms "Router", "Routing Tuple", "Routing Set", "Network Topology Graph" are to be interpreted as described therein. 3. Applicability The extension specified in this document is compliant with any OLSRv2 implementation, and provides information about multiple paths per source-destination pair (when they are available), and such without requiring signaling other than that provided by the standard OLSRv2 protocol. While multi-path routing may increase throughput and end-to-end transmission reliability, it may also increase the chances of packet Szwabe, et al. Expires November 3, 2011 [Page 3] Internet-Draft Multi-path for OLSRv2 May 2011 forwarding loops. It is thus recommended to use this specification jointly with a routing loop avoidance mechanism, such as the ones described in Section 7. 4. Protocol Overview and Functioning This specification provides two modes of operation. In the proactive mode, available redundant paths are systematically precomputed, while in the on-demand mode available redundant paths are computed on the go, as needed. routers in the network MUST all operate the same mode. The following sections specify the functionning of each mode. 5. Proactive Multi-path Computation with OLSRv2 In this mode, available redundant paths are systematically precomputed, preserving the proactive nature of the standard (i.e. single-path) OLSRv2. Each router identifies all the possible next- hops through which there exists a good enough path to a given destination. Instead of running the Dijkstra's shortest path algorithm with a computing router as the origin of every route (as it is in the case of single-path OLSRv2), the network-based multi-path algorithm examines all the neighbors of the computing router as potential next- hops on the route to a given destination. More precisely, all the remaining neighbors (i.e., all except the examined one) are temporarily 'removed' from the topology graph together with their adjacent links, and the shortest path algorithm is executed with the examined neighbor as a origin. According to the proposed algorithm, the computing router chooses only these neighbors as a next-hop for the given destination router, which are able to determine the remaining part of the route to the destination in a way that does not require backward transmission [SM09]. The proactive multi-path route calculation algorithm may be described as follows [SMN+10]: 1. For each neighbor of router m do: A. Delete all neighbors of router m with their adjacent links, except of the selected one. B. Run standard single-path Dijkstra's algorithm for the obtained graph in order to determine Routing Tuples, with the selected neighbor as the next-hop on the route. Szwabe, et al. Expires November 3, 2011 [Page 4] Internet-Draft Multi-path for OLSRv2 May 2011 2. Merge the obtained sets of Routing Tuples of neighboring routers into the final OLSRv2 Routing Set of router m that allows multiple entries for a given destination. As a result of an algorithm execution, the path-computing router obtains a separate set of Routing Tuples for each neighbor, which can be easily used to obtain the modified OLSRv2 Routing Set with multiple entries for a given destination. In contrast to the standard OLSRv2 specification, for which "Routing Set MUST contain the shortest paths for all destinations from all local OLSRv2 interfaces using the Network Topology Graph" (see Section 18.2 of [I-D.ietf-manet-olsrv2]), the Multi-path Extension of OLSRv2 allows using paths which MAY be longer than the shortest one for a given source/destination pair. Tables presented in Appendix A contain routing entries which are compatible with standard OLSRv2 Routing Tuples, but allows multiple entries with the same destination addresses. An example presenting an execution of the multi-path algorithm may be also found in Appendix A. 5.1. Optimization using MPR Selection For a further optimization, the set of examined neighbors of a computing router may be limited to the set of the router's MPRs. This method is aimed at increasing the route stability as well as the probability that the choice of next-hops for routes to a given destination will lead to parallel transmissions without interferences. Such modification of the Proactive Multi-path algorithm is especially suitable for networks with dense topologies, since it allows to avoid undesirable forwarding through multiple paths sharing the same radio resources. Such extension does not require introducing any modifications into the structure of OLSRv2 Routing Tuples. 6. On-demand Multi-path Computation with OLSRv2 In this mode, available redundant paths are computed on the go, as needed. This mode is recommended in networks with a significant number of long and more occasional flows, and may not be appropriate for networks with a very dynamic topology, though route recovery and loop detection schemes may alleviate issues with this mode in dynamic topologies [YADP10]. The mechanism described in the following is invoked on demand to reach a destination d. Note that it does not incur any signalling in addition to standard OLSRv2 signalling. The general principle of Szwabe, et al. Expires November 3, 2011 [Page 5] Internet-Draft Multi-path for OLSRv2 May 2011 this mechanism 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. Different fp and fe are chosen to get link-disjoint path or node-disjoint routes as necessary. If id is the identity functions, 3 cases are possible: o if id=fe2->5 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 is obtained. Authors' Addresses Andrzej Szwabe Poznan University of Technology 5 M. Sklodowskiej-Curie Sq. 60-965 Poznan Poland Phone: +48 61 665 3958 Email: Andrzej.Szwabe@put.poznan.pl Adam Nowak (editor) Poznan University of Technology 5 M. Sklodowskiej-Curie Sq. 60-965 Poznan Poland Phone: +48 61 665 3958 Email: Adam.Nowak@put.poznan.pl Emmanuel Baccelli INRIA Phone: +33-169-335-511 Email: Emmanuel.Baccelli@inria.fr URI: http://www.emmanuelbaccelli.org/ Szwabe, et al. Expires November 3, 2011 [Page 13] Internet-Draft Multi-path for OLSRv2 May 2011 Jiazi Yi Nantes University IRCCyN lab - IVC team Polytech'Nantes, rue Christian Pauc, BP50609 44306 Nantes cedex 3 France Phone: +33 (0) 240 683 050 Email: Jiazi.Yi@polytech.univ-nantes.fr URI: http://www.jiaziyi.com/ Benoit Parrein Nantes University 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 Szwabe, et al. Expires November 3, 2011 [Page 14]