Internet Engineering Task Force A. Szwabe Internet-Draft A. Nowak, Ed. Intended status: Informational Poznan University of Technology Expires: April 15, 2011 E. Baccelli INRIA J. Yi B. Parrein Nantes University October 12, 2010 Multi-path for Optimized Link State Routing Protocol version 2 draft-szwabe-manet-multipath-olsrv2-00 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 April 15, 2011. Copyright Notice Copyright (c) 2010 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 April 15, 2011 [Page 1]
Internet-Draft Multi-path for OLSRv2 October 2010 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 April 15, 2011 [Page 2]
Internet-Draft Multi-path for OLSRv2 October 2010 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 [I-D.ietf-manet-nhdp], 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 April 15, 2011 [Page 3]
Internet-Draft Multi-path for OLSRv2 October 2010 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 April 15, 2011 [Page 4]
Internet-Draft Multi-path for OLSRv2 October 2010 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. 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 April 15, 2011 [Page 5]
Internet-Draft Multi-path for OLSRv2 October 2010 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=fe<fp paths tend to be arc disjoint; o if id<fe=fp paths tend to be vertex-disjoint; o if id<fe<fp paths also tend to be vertex-disjoint, but when is not possible they tend to be arc disjoint. The on-demand multi-path route calculation algorithm may be described as follows to get N distinct paths: 1. For each path 1 to N do: A. Run Dijkstra algorithm to get the source tree. B. Get the shortest path Pi for the on-demand destination d. C. Apply cost functions fp and fe respectively on edges of Pi and pointing vertices of Pi. 2. Writing the entire route into IP source routing header. For the special case of more than 10 hops (specially large MANET), because IP source routing option accepts only a maximum of 9 addresses (in total, 11 nodes including source and destination nodes = 10 hops), the loose source routing may be used. Table 1 shows an example of the multi-path source routing table, which provides multiple routes to the destination. To compute on-demand multiple paths, another possible solution is instead of increasing the cost of the arc, the related node is deleted from the node set in order to get totally node-disjoint routes. However, in the cases when the nodes are locally sparse i.e a partition of the MANET, deleting some key nodes might prevent from finding new route. It is expected that keeping nodes in the routes calculation process provides more flexibility and better adaptation to the MANET topology. Szwabe, et al. Expires April 15, 2011 [Page 6]
Internet-Draft Multi-path for OLSRv2 October 2010 +---+---------------------+----------------------+ | # | Destination address | Source route | +---+---------------------+----------------------+ | 1 | dest_addr(X) | hop_1(A),hop_2(B)... | | 2 | dest_addr(X) | hop_1(C),hop_2(D)... | | 3 | dest_addr(X) | hop_1(E),hop_2(F)... | | 4 | dest_addr(Y) | hop_1(G),hop_2(H)... | | 5 | ... | ... | +---+---------------------+----------------------+ Table 1: Sample on-demand multi-path source Routing Tuples 6.1. Route Recovery Mechnanism With source routing, the route is defined by the source, and the intermediate nodes just read the next hop information for the packet's source routing header. Therefore, when source routing is used, updated topology information potentially available on intermediate nodes towards the destination is not used in case of topology changes. Thus, route recovery mechanisms such as the one described below is necessary for dynamic scenarios. For instance, before an intermediate node tries to forward a packet to the next hop according to the source route, the node may first checks whether the next hop in the source route is one of its neighbors (by checking the 1-hop neighbor set). If so, the packet is forwarded normally. If not, it is possible that the "next hop" is not available anymore, and the node should thus recompute the route and forward the packet by using the new route. This route recovery mechanism does not introduce extra route discovery procedure or any additional signalling, while effectively avoid unavailable links. 7. Loop Detection Mechanisms A loop detection scheme becomes necessary when packets can switch between multiple paths towards destination. Loop detection can be provided by auxiliary mechanisms such as for instance: o Backpressure-based scheduling [SMN+10]- on each router a scheduler utilizes a multi-path Routing Set jointly with information about backpressure weights. Traffic of each flow is load-balanced among the possible relaying routers in a fully dynamic manner, i.e., according to the most recent network state information. Backpressure-based scheduling requires additional queue level signaling (and introducing corresponding messages) which is beyond Szwabe, et al. Expires April 15, 2011 [Page 7]
Internet-Draft Multi-path for OLSRv2 October 2010 the scope of this document. o Source routing [RFC0791]- each of multiple paths is specified in IP headers as a sequence of relaying OLSRv2 routers' addresses of packets being forwarded along this path. Each router on the path forwards the packet according to this data as long as this data is not outdated due to network topology changes. If used with a route recovery scheme such as the one described in Section 6.1, a node should compare the old source route with the new, recomputed source route (after having performed route recovery). If the new route contains nodes that were already traversed with the old route before reaching the recomputing node, a loop is detected. 8. Security Considerations To be elaborated. 9. IANA Considerations This memo includes no request to IANA. This documents specifies only the extension of OLSRv2, without introducing any new message type. Every IANA request regarding OLSRv2 protocol is explained in [I-D.ietf-manet-olsrv2] and [I-D.ietf-manet-nhdp]. 10. Acknowledgements This work was partly supported by the grant of Poznan University of Technology DS 45-083/10 and the European Commission OPNEX STREP (FP7- 224218, http://opnex.eu) for the proactive multi-path routing and partly by the project SEREADMO of the French research agency (RNRT2803) for source routing approach. The authors also want to thank to following people for their input: o Pawel Misiorek o Maciej Urbanski o Thomas Clausen o Przemyslaw Walkowiak Szwabe, et al. Expires April 15, 2011 [Page 8]
Internet-Draft Multi-path for OLSRv2 October 2010 o Eddy Cizeron o Salima Hamma o Asmaa-Hassiba Adnane 11. References 11.1. Normative References [I-D.ietf-manet-nhdp] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", draft-ietf-manet-nhdp-14 (work in progress), July 2010. [I-D.ietf-manet-olsrv2] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-11 (work in progress), April 2010. [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. 11.2. Informative References [GNT06] Georgiadis, L., Neely, M., and L. Tassiulas, "Resource allocation and cross-layer control in wireless networks", In Foundations and Trends in Networking, pages 271-379, 2006. [SM09] Szwabe, A. and P. Misiorek, "Integration of multi-path Optimized Link State Protocol with max-weight scheduling", Proc. of IEEE International Conference on Information and Multimedia Technology (ICIMT 2009), Jeju Island, Korea, pages 458-462, 2009. [SMN+10] Szwabe, A., Misiorek, P., Nowak, A., and J. Marchwicki, "Implementation of Backpressure-Based Routing Integrated with Max-Weight Scheduling in a Wireless Multi-hop Network", Proc. of 3rd IEEE International Workshop on Wireless and Internet Services (WISe 2010), Denver, USA, Szwabe, et al. Expires April 15, 2011 [Page 9]
Internet-Draft Multi-path for OLSRv2 October 2010 pages 999-1004, 2010. [SS08] Shakkottai, S. and R. Srikant, "Network Optimization and Control", In Foundations and Trends in Networking, pages 1-149, January 2007. [YADP10] Yi, J., Adnane, A-H., David, S., and B. Parrein, "Multipath optimized link state routing for mobile ad hoc networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, January, 2011. Appendix A. Example of Proactive Multi-path Algorithm Execution This appendix shows the process of the Routing Set calculation (performed on the router (1)) in a network of simple topology of 6 routers. The example of a network topology is presented below. +-----------+----------------------------+ | Router ID | Set of symmetric neighbors | +-----------+----------------------------+ | (1) | (2), (3), (4) | | (2) | (1), (3), (5) | | (3) | (1), (2), (4), (5), (6) | | (4) | (1), (3), (6) | | (5) | (2), (3), (6) | | (6) | (3), (4), (5) | +-----------+----------------------------+ Table 2: Network topology 5-----6 / \ / \ / \ / \ 2-----3-----4 \ | / '---1---' Figure 1: Network Topology In the first step, all the neighbors of router (1) except router (2) are temporary excluded from the topology. Table 3 presents Routing Tuples obtained as a result of the Dijkstra's shortest path algorithm execution on the modified topology. Table 4 and Table 5 present the analogous information for the cases of routers (3) and (4) taken as investigated Next-hops, respectively. Table 6 presents the final Szwabe, et al. Expires April 15, 2011 [Page 10]
Internet-Draft Multi-path for OLSRv2 October 2010 Routing Set for router (1). Column names in tables are equivalents of the elements in the OLSRv2 Routing Set (R_dest_addr, R_next_iface_addr, R_local_iface_addr, R_dist). +---+------------------+---------------+-----------------+----------+ | # | Destination | Next-hop | Interface | Distance | | | address | address | address | | +---+------------------+---------------+-----------------+----------+ | 1 | (2) | (2) | A | 1 | | 2 | (5) | (2) | A | 2 | | 3 | (6) | (2) | A | 3 | +---+------------------+---------------+-----------------+----------+ Table 3: Routing Tuples for Next-hop (2). +---+------------------+---------------+-----------------+----------+ | # | Destination | Next-hop | Interface | Distance | | | address | address | address | | +---+------------------+---------------+-----------------+----------+ | 1 | (3) | (3) | A | 1 | | 2 | (5) | (3) | A | 2 | | 3 | (6) | (3) | A | 2 | +---+------------------+---------------+-----------------+----------+ Table 4: Routing Tuples for Next-hop (3). +---+------------------+---------------+-----------------+----------+ | # | Destination | Next-hop | Interface | Distance | | | address | address | address | | +---+------------------+---------------+-----------------+----------+ | 1 | (4) | (4) | A | 1 | | 2 | (5) | (4) | A | 3 | | 3 | (6) | (4) | A | 2 | +---+------------------+---------------+-----------------+----------+ Table 5: Routing Tuples for Next-hop (4). Szwabe, et al. Expires April 15, 2011 [Page 11]
Internet-Draft Multi-path for OLSRv2 October 2010 +---+------------------+---------------+-----------------+----------+ | # | Destination | Next-hop | Interface | Distance | | | address | address | address | | +---+------------------+---------------+-----------------+----------+ | 1 | (2) | (2) | A | 1 | | 2 | (3) | (3) | A | 1 | | 3 | (4) | (4) | A | 1 | | 4 | (5) | (2) | A | 2 | | 5 | (5) | (3) | A | 2 | | 6 | (5) | (4) | A | 3 | | 7 | (6) | (3) | A | 2 | | 8 | (6) | (4) | A | 2 | | 9 | (6) | (2) | A | 3 | +---+------------------+---------------+-----------------+----------+ Table 6: Routing Tuples for router (1). Appendix B. Example of on-demand Multi-path Execution This appendix gives an example of the on-demand multi-path algorithm, which includes the source-based Dijkstra multi-path algorithm, route recovery and loop detection. Figure 2 +---------+----------------------------+ | Node ID | Set of symmetric neighbors | +---------+----------------------------+ | (1) | {(2),(3)} | | (2) | {(1),(3),(4),(5)} | | (3) | {(1),(2),(4)} | | (4) | {(2),(3),(5)} | | (5) | {(2),(4)} | +---------+----------------------------+ Table 7: Network topology for the on-demand example .-----2-----. / / \ \ / / \ \ 1 / \ 5 \ / \ / \ / \ / 3-----------4 Szwabe, et al. Expires April 15, 2011 [Page 12]
Internet-Draft Multi-path for OLSRv2 October 2010 Figure 2: Network Topology for the on-demand example The initial cost of all the links is set to 1. The incremental functions fp and fe are defined as fp(c)=4c and fe(c)=2c in this example. Two routes from node 1 to node 5 are demanded. On the first run of the Dijkstra algorithm, the shortest path 1->2->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 April 15, 2011 [Page 13]
Internet-Draft Multi-path for OLSRv2 October 2010 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 April 15, 2011 [Page 14]