idnits 2.17.1 draft-szwabe-manet-multipath-olsrv2-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- -- The document has an IETF Trust Provisions (28 Dec 2009) Section 6.c(ii) Publication Limitation clause. If this document is intended for submission to the IESG for publication, this constitutes an error. 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 (May 2, 2011) is 4740 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Unused Reference: 'RFC0791' is defined on line 370, but no explicit reference was found in the text == Outdated reference: A later version (-19) exists of draft-ietf-manet-olsrv2-11 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force A. Szwabe 3 Internet-Draft A. Nowak, Ed. 4 Intended status: Experimental Poznan University of Technology 5 Expires: November 3, 2011 E. Baccelli 6 INRIA 7 J. Yi 8 B. Parrein 9 Nantes University 10 May 2, 2011 12 Multi-path for Optimized Link State Routing Protocol version 2 13 draft-szwabe-manet-multipath-olsrv2-02 15 Abstract 17 This document specifies an extension of the OLSRv2 protocol providing 18 methods to compute multiple paths for each destination, when such 19 paths are available. 21 Status of this Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. This document may not be modified, 25 and derivative works of it may not be created, and it may not be 26 published except as an Internet-Draft. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on November 3, 2011. 40 Copyright Notice 42 Copyright (c) 2011 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 3 60 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 4 61 5. Proactive Multi-path Computation with OLSRv2 . . . . . . . . . 4 62 5.1. Optimization using MPR Selection . . . . . . . . . . . . . 5 63 6. On-demand Multi-path Computation with OLSRv2 . . . . . . . . . 5 64 6.1. Route Recovery Mechnanism . . . . . . . . . . . . . . . . 7 65 7. Loop Detection Mechanisms . . . . . . . . . . . . . . . . . . 7 66 8. Security Considerations . . . . . . . . . . . . . . . . . . . 8 67 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 68 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8 69 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 70 11.1. Normative References . . . . . . . . . . . . . . . . . . . 9 71 11.2. Informative References . . . . . . . . . . . . . . . . . . 9 72 Appendix A. Example of Proactive Multi-path Algorithm 73 Execution . . . . . . . . . . . . . . . . . . . . . . 10 74 Appendix B. Example of on-demand Multi-path Execution . . . . . . 12 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 77 1. Introduction 79 This document specifies a lightweight extension of the OLSRv2 80 protocol [I-D.ietf-manet-olsrv2], providing multiple paths for each 81 destination, when such paths are available. 83 Multi-path routing increases reliability by detecting the 84 availability of redundant paths. OLSRv2, in its basic specification, 85 does not provide multiple routes for a given destination. On the 86 other hand, the protocol provides every router with enough 87 information to compute multiple routes to any specific destination, 88 if available. 90 Information about multiple paths per source-destination pair enables 91 more successful end-to-end transmissions in a frequently changing 92 network environment (e.g. in the case of a sudden breakdown of a 93 relaying router), and favors throughput maximization in the case when 94 multiple parallel transmissions without interferences (i.e., 95 appropriately distinct to each other) enable bypassing a network 96 capacity bottleneck ([GNT06], [SS08], [SM09]). 98 2. Terminology 100 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 101 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 102 "OPTIONAL" in this document are to be interpreted as described in RFC 103 2119 [RFC2119]. 105 All terms introduced in [RFC6130], including "interface", "network 106 address", "1-hop neighbor", "symmetric 1-hop neighbor" are to be 107 interpreted as described there. 109 All terms introduced in [I-D.ietf-manet-olsrv2], including the terms 110 "Router", "Routing Tuple", "Routing Set", "Network Topology Graph" 111 are to be interpreted as described therein. 113 3. Applicability 115 The extension specified in this document is compliant with any OLSRv2 116 implementation, and provides information about multiple paths per 117 source-destination pair (when they are available), and such without 118 requiring signaling other than that provided by the standard OLSRv2 119 protocol. 121 While multi-path routing may increase throughput and end-to-end 122 transmission reliability, it may also increase the chances of packet 123 forwarding loops. It is thus recommended to use this specification 124 jointly with a routing loop avoidance mechanism, such as the ones 125 described in Section 7. 127 4. Protocol Overview and Functioning 129 This specification provides two modes of operation. In the proactive 130 mode, available redundant paths are systematically precomputed, while 131 in the on-demand mode available redundant paths are computed on the 132 go, as needed. routers in the network MUST all operate the same mode. 133 The following sections specify the functionning of each mode. 135 5. Proactive Multi-path Computation with OLSRv2 137 In this mode, available redundant paths are systematically 138 precomputed, preserving the proactive nature of the standard (i.e. 139 single-path) OLSRv2. Each router identifies all the possible next- 140 hops through which there exists a good enough path to a given 141 destination. 143 Instead of running the Dijkstra's shortest path algorithm with a 144 computing router as the origin of every route (as it is in the case 145 of single-path OLSRv2), the network-based multi-path algorithm 146 examines all the neighbors of the computing router as potential next- 147 hops on the route to a given destination. More precisely, all the 148 remaining neighbors (i.e., all except the examined one) are 149 temporarily 'removed' from the topology graph together with their 150 adjacent links, and the shortest path algorithm is executed with the 151 examined neighbor as a origin. According to the proposed algorithm, 152 the computing router chooses only these neighbors as a next-hop for 153 the given destination router, which are able to determine the 154 remaining part of the route to the destination in a way that does not 155 require backward transmission [SM09]. 157 The proactive multi-path route calculation algorithm may be described 158 as follows [SMN+10]: 160 1. For each neighbor of router m do: 162 A. Delete all neighbors of router m with their adjacent links, 163 except of the selected one. 165 B. Run standard single-path Dijkstra's algorithm for the 166 obtained graph in order to determine Routing Tuples, with the 167 selected neighbor as the next-hop on the route. 169 2. Merge the obtained sets of Routing Tuples of neighboring routers 170 into the final OLSRv2 Routing Set of router m that allows 171 multiple entries for a given destination. 173 As a result of an algorithm execution, the path-computing router 174 obtains a separate set of Routing Tuples for each neighbor, which can 175 be easily used to obtain the modified OLSRv2 Routing Set with 176 multiple entries for a given destination. In contrast to the 177 standard OLSRv2 specification, for which "Routing Set MUST contain 178 the shortest paths for all destinations from all local OLSRv2 179 interfaces using the Network Topology Graph" (see Section 18.2 of 180 [I-D.ietf-manet-olsrv2]), the Multi-path Extension of OLSRv2 allows 181 using paths which MAY be longer than the shortest one for a given 182 source/destination pair. Tables presented in Appendix A contain 183 routing entries which are compatible with standard OLSRv2 Routing 184 Tuples, but allows multiple entries with the same destination 185 addresses. 187 An example presenting an execution of the multi-path algorithm may be 188 also found in Appendix A. 190 5.1. Optimization using MPR Selection 192 For a further optimization, the set of examined neighbors of a 193 computing router may be limited to the set of the router's MPRs. 194 This method is aimed at increasing the route stability as well as the 195 probability that the choice of next-hops for routes to a given 196 destination will lead to parallel transmissions without 197 interferences. Such modification of the Proactive Multi-path 198 algorithm is especially suitable for networks with dense topologies, 199 since it allows to avoid undesirable forwarding through multiple 200 paths sharing the same radio resources. Such extension does not 201 require introducing any modifications into the structure of OLSRv2 202 Routing Tuples. 204 6. On-demand Multi-path Computation with OLSRv2 206 In this mode, available redundant paths are computed on the go, as 207 needed. This mode is recommended in networks with a significant 208 number of long and more occasional flows, and may not be appropriate 209 for networks with a very dynamic topology, though route recovery and 210 loop detection schemes may alleviate issues with this mode in dynamic 211 topologies [YADP10]. 213 The mechanism described in the following is invoked on demand to 214 reach a destination d. Note that it does not incur any signalling in 215 addition to standard OLSRv2 signalling. The general principle of 216 this mechanism is at step i to look for the shortest path Pi to the 217 destination d. Based on Dijkstra algorithm, the main modification 218 consists in adding two cost functions namely incremental functions fp 219 and fe in order to prevent the next steps to use similar path. fp is 220 used to increase costs of arcs belonging to the previously path Pi 221 (or which opposite arcs belong to it). This encourages future paths 222 to use different arcs but not different vertices. fe is used to 223 increase costs of the arcs who lead to vertices of the previous path 224 Pi. Different fp and fe are chosen to get link-disjoint path or 225 node-disjoint routes as necessary. If id is the identity functions, 226 3 cases are possible: 228 o if id=fe2->5 534 is obtained. 536 The incremental function fp is applied to increase the cost of the 537 link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of 538 the link 1-3, 2-3, 2-4, 4-5, from 1 to 2. 540 On the second run of the Dijkstra algorithm, the second path 541 1->3->4->5 is obtained. 543 Authors' Addresses 545 Andrzej Szwabe 546 Poznan University of Technology 547 5 M. Sklodowskiej-Curie Sq. 548 60-965 Poznan 549 Poland 551 Phone: +48 61 665 3958 552 Email: Andrzej.Szwabe@put.poznan.pl 554 Adam Nowak (editor) 555 Poznan University of Technology 556 5 M. Sklodowskiej-Curie Sq. 557 60-965 Poznan 558 Poland 560 Phone: +48 61 665 3958 561 Email: Adam.Nowak@put.poznan.pl 563 Emmanuel Baccelli 564 INRIA 566 Phone: +33-169-335-511 567 Email: Emmanuel.Baccelli@inria.fr 568 URI: http://www.emmanuelbaccelli.org/ 569 Jiazi Yi 570 Nantes University 571 IRCCyN lab - IVC team 572 Polytech'Nantes, rue Christian Pauc, BP50609 573 44306 Nantes cedex 3 574 France 576 Phone: +33 (0) 240 683 050 577 Email: Jiazi.Yi@polytech.univ-nantes.fr 578 URI: http://www.jiaziyi.com/ 580 Benoit Parrein 581 Nantes University 582 IRCCyN lab - IVC team 583 Polytech'Nantes, rue Christian Pauc, BP50609 584 44306 Nantes cedex 3 585 France 587 Phone: +33 (0) 240 683 050 588 Email: Benoit.Parrein@polytech.univ-nantes.fr 589 URI: http://www.irccyn.ec-nantes.fr