draft-ietf-manet-olsrv2-multipath-02.txt   draft-ietf-manet-olsrv2-multipath-03.txt 
Network Working Group J. Yi Network Working Group J. Yi
Internet-Draft LIX, Ecole Polytechnique Internet-Draft LIX, Ecole Polytechnique
Intended status: Experimental B. Parrein Intended status: Experimental B. Parrein
Expires: April 29, 2015 University of Nantes Expires: November 27, 2015 University of Nantes
October 26, 2014 May 26, 2015
Multi-path Extension for the Optimized Link State Routing Protocol Multi-path Extension for the Optimized Link State Routing Protocol
version 2 (OLSRv2) version 2 (OLSRv2)
draft-ietf-manet-olsrv2-multipath-02 draft-ietf-manet-olsrv2-multipath-03
Abstract Abstract
This document specifies a multi-path extension to the Optimized Link This document specifies a multi-path extension for the Optimized Link
State Routing Protocol version 2 (OLSRv2) to discover multiple State Routing Protocol version 2 (OLSRv2) to discover multiple
disjoint paths, so as to improve reliability of the OLSRv2 protocol. disjoint paths, so as to improve reliability of the OLSRv2 protocol.
The interoperability with OLSRv2 is retained. The interoperability with OLSRv2 is retained.
Status of this Memo Status of this Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 29, 2015. This Internet-Draft will expire on November 27, 2015.
Copyright Notice Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
skipping to change at page 2, line 16 skipping to change at page 2, line 16
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3 1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6
5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 7 5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 7
5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 7 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 7
6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 7 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 7
6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 7 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 8
6.1.1. MP_OLSRv2 TLV . . . . . . . . . . . . . . . . . . . . 7 6.1.1. SR_OLSRv2 TLV . . . . . . . . . . . . . . . . . . . . 8
6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 8 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 8
6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8
7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 8 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 9
7.1. MP-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 8 7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 9
7.2. Multi-path Routing Set . . . . . . . . . . . . . . . . . . 9 7.2. Multi-path Routing Set . . . . . . . . . . . . . . . . . . 9
8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 9 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 10
8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 9 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 10
8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 10 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 10
8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10 8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10
8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 11 8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 11
8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 11 8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 12
9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 12 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13
10. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 13
10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 13 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 14
10.2. Multi-path extension based on olsrd . . . . . . . . . . . 14 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 14
10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 14 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 15
11. Security Considerations . . . . . . . . . . . . . . . . . . . 14 11. Security Considerations . . . . . . . . . . . . . . . . . . . 15
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
12.1. HELLO Message-Type-Specific TLV Type Registries . . . . . 15 12.1. HELLO Message-Type-Specific TLV Type Registries . . . . . 15
12.2. TC Message-Type-Specific TLV Type Registries . . . . . . . 15 12.2. TC Message-Type-Specific TLV Type Registries . . . . . . . 16
13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16
14.1. Normative References . . . . . . . . . . . . . . . . . . . 16 14.1. Normative References . . . . . . . . . . . . . . . . . . . 16
14.2. Informative References . . . . . . . . . . . . . . . . . . 16 14.2. Informative References . . . . . . . . . . . . . . . . . . 17
Appendix A. An example of Multi-path Dijkstra Algorithm . . . . . 17 Appendix A. An example of Multi-path Dijkstra Algorithm . . . . . 18
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19
1. Introduction 1. Introduction
The Optimized Link State Routing Protocol version 2 (OLSRv2) The Optimized Link State Routing Protocol version 2 (OLSRv2)
[RFC7181] is a proactive link state protocol designed for use in [RFC7181] is a proactive link state protocol designed for use in
mobile ad hoc networks (MANETs). It generates routing messages mobile ad hoc networks (MANETs). It generates routing messages
periodically to create and maintain a Routing Set, which contains periodically to create and maintain a Routing Set, which contains
routing information to all the possible destinations in the routing routing information to all the possible destinations in the routing
domain. For each destination, there exists an unique Routing Tuple, domain. For each destination, there exists a unique Routing Tuple,
which indicates the next hop to reach the destination. which indicates the next hop to reach the destination.
This document specifies an extension of the OLSRv2 protocol This document specifies an extension of the OLSRv2 protocol
[RFC7181], to provide multiple disjoint paths for a source- [RFC7181], to provide multiple disjoint paths for a source-
destination pair. Because of the characteristics of MANETs destination pair. Because of the characteristics of MANETs
[RFC2501], especially the dynamic topology, having multiple paths is [RFC2501], especially the dynamic topology, having multiple paths is
helpful for increasing network throughput, improving transmission helpful for increasing network throughput, improving forwarding
reliability and load balancing. reliability and load balancing.
The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses
multi-path Dijkstra algorithm to explore multiple disjoint paths from multi-path Dijkstra algorithm by default to explore multiple disjoint
source to the destination based on the topology information obtained paths from a source router to a destination router based on the
through OLSRv2, and forward the datagrams in a load-balancing manner topology information obtained through OLSRv2, and forward the
using source routing. MP-OLSRv2 is designed to be interoperable with datagrams in a load-balancing manner using source routing. MP-OLSRv2
OLSRv2. is designed to be interoperable with OLSRv2.
1.1. Motivation and Experiments to Be Conducted 1.1. Motivation and Experiments to Be Conducted
This document is an experimental extension of OLSRv2 that can This document is an experimental extension of OLSRv2 that can
increase the data forwarding reliability in dynamic and high-load increase the data forwarding reliability in dynamic and high-load
MANET scenarios by transmitting packet over multiple disjoint paths MANET scenarios by transmitting datagrams over multiple disjoint
using source routing. This mechanism is used because: paths using source routing. This mechanism is used because:
o Disjoint paths can avoid single route failures. o Disjoint paths can avoid single route failures.
o Transmitting datagrams through parallel paths can increase o Transmitting datagrams through parallel paths can increase
aggregated throughput and provide load-balancing. aggregated throughput and provide load balancing.
o Certain scenarios require some routers must (or must not) be used. 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 o By having control of the paths at the source, the delay can be
provisioned. provisioned.
o An very important application of this extension is combination o A very important application of this extension is combination with
with Forward Error Correction coding. This requires disjoint Forward Error Correction (FEC) coding. Because the packet drop is
paths. The single path routing is not adapted because the packet normally continuous in a path (for example, due to route failure),
drop is normally continuous, in which forward correction coding is FEC coding is less effective in single path routing protocols. By
not helpful. providing multiple disjoint paths, the application of FEC coding
with multi-path protocol is more resilient to routing failures.
While existed deployments, running code and simulations have proven While existed deployments, running code and simulations have proven
the interest of multi-path extension for OLSRv2 in certain networks, the interest of multi-path extension for OLSRv2 in certain networks,
more experiments and experiences are still needed to understand the more experiments and experiences are still needed to understand the
mechanisms of the protocol. The multipath extension for OLSRv2 is mechanisms of the protocol. The multi-path extension for OLSRv2 is
expected to be revised and improved to the Standard Track, once expected to be revised and improved to the Standard Track, once
sufficient operational experience is obtained. Other than the sufficient operational experience is obtained. Other than general
general experiences including the protocol specification, experiences including the protocol specification, interoperability
interoperability with original OLSRv2 implementations, the with original OLSRv2 implementations, the experiences in the
experiences in the following aspects are highly appreciated: following aspects are highly appreciated:
o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) o Optimal values for the number of multiple paths (NUMBER_OF_PATHS)
to be used. This depends on the network topology and router to be used. This depends on the network topology and router
density. density.
o Optimal values for the cost functions. Cost functions are applied o Optimal values for the cost functions. Cost functions are applied
to punish the costs of used links and nodes so as to obtain to punish the costs of used links and nodes so as to obtain
disjoint paths. What kind of disjointness is desired (node- disjoint paths. What kind of disjointness is desired (node-
disjoint or link-disjoint) may depends on the layer 2 protocol disjoint or link-disjoint) may depends on the layer 2 protocol
used, and can be achieved by setting different sets of cost used, and can be achieved by setting different sets of cost
functions. functions.
o Use of other metric other than hop-count. This multipath o Use of other metrics other than hop-count. This multi-path
extension can be used not only for hop-count metric type, but extension can be used not only for hop-count metric type, but also
other metric types that meet the requirement of OLSRv2, such as other metric types that meet the requirement of OLSRv2, such as
[I-D.ietf-manet-olsrv2-dat-metric]. The metric type used has also [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 co-relation with the choice of cost functions as indicated in the
previous bullet. previous bullet.
o Optimal choice of "key" routers for loose source routing. In some o Optimal choice of "key" routers for loose source routing. In some
cases, loose source routing is used to reduce overhead or for cases, loose source routing is used to reduce overhead or for
interoperability with OLSRv2 routers. Other than the basic rules interoperability with OLSRv2 routers. Other than the basic rules
defined in the following of this document, optimal choices of defined in the following of this document, optimal choices of
routers to put in the loose source routing header can be further routers to put in the loose source routing header can be further
studied. studied.
o Different path-selection schedulers. By default, Round-Robin o Different path-selection schedulers. By default, Round-Robin
scheduling is used to select a path to be used for a datagram. In scheduling is used to select a path to be used for a datagram. In
some scenarios, weighted scheduling can be considered: for some scenarios, weighted scheduling can be considered: for
example, the paths with low costs (higher path quality) can example, the paths with lower costs (higher path quality) can
transfer more datagrams compared to paths with higher costs. transfer more datagrams compared to paths with higher costs.
o The impacts to the delay variation due to multi-path routing. o The impacts of the delay variation due to multi-path routing.
[RFC2991] brings out some concerns of multi-path routing, [RFC2991] brings out some concerns of multi-path routing,
especially variable latencies. Although current experiments especially variable latencies. Although current experiments
result show that multi-path routing can reduce the jitter in result show that multi-path routing can reduce the jitter in
dynamic scenarios, some transport protocols or applications may be dynamic scenarios, some transport protocols or applications may be
sensitive to the packet re-ordering. sensitive to the datagram re-ordering.
o The disjoint multiple path protocol has interesting application o The disjoint multi-path protocol has interesting application with
with Forward Error Correction (FEC) Coding, especially for Forward Error Correction (FEC) Coding, especially for services
services like video/audio streaming. The combination of FEC like video/audio streaming. The combination of FEC coding
coding mechanisms and this extension is thus encouraged. By mechanisms and this extension is thus encouraged. By applying FEC
applying FEC coding, the issue of packet re-ordering can be coding, the issue of packet re-ordering can be alleviated.
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 o In addition to IP source routing based approach, it can be
interesting to try multi-path routing in MANET using label- interesting to try multi-path routing in MANET using label-
switched flow in the future. switched flow in the future.
o The usage of multi-topology information. By using o The use of multi-topology information. By using
[I-D.ietf-manet-olsrv2-multitopology], multiple topologies using [I-D.ietf-manet-olsrv2-multitopology], multiple topologies using
different metric types can be obtained. It is encouraged to different metric types can be obtained. It is encouraged to
experiment the use of multiple metrics for building multiple paths experiment the use of multiple metrics for building multiple paths
also. also.
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in "OPTIONAL" in this document are to be interpreted as described in
skipping to change at page 5, line 47 skipping to change at page 5, line 49
specification as an extension to [RFC7181]. specification as an extension to [RFC7181].
3. Applicability Statement 3. Applicability Statement
As an extension of OLSRv2, this specification is applicable to MANETs As an extension of OLSRv2, this specification is applicable to MANETs
for which OLSRv2 is applicable (see [RFC7181]). It can operate on for which OLSRv2 is applicable (see [RFC7181]). It can operate on
single, or multiple interfaces, to discover multiple disjoint paths single, or multiple interfaces, to discover multiple disjoint paths
from a source router to a destination router. from a source router to a destination router.
MP-OLSRv2 is specially designed for networks with dynamic topology MP-OLSRv2 is specially designed for networks with dynamic topology
and slow data rate links. By providing multiple paths, higher and low data rate links. By providing multiple paths, higher
aggregated bandwidth can be obtained, and the routing process is more aggregated throughput can be obtained, and the routing process is
robust to packet loss. more robust to packet loss.
In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily
replace OLSRv2 completely. The extension can be applied for certain replace OLSRv2 completely. The extension can be applied for certain
applications that are suitable for multi-path routing (mainly video applications that are suitable for multi-path routing (mainly video
or audio streams), based on the information such as DiifServ Code or audio streams), based on the information such as DiifServ Code
Point [RFC2474]. Point [RFC2474].
Compared to OLSRv2, this extension does not introduce new message Compared to OLSRv2, this extension does not introduce new message
type in the air, and is interoperable with OLSRv2 implementations type in the air. Two new message TLV types (one for HELLO message
that do not have this extension. and one for TC message) are 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 4. Protocol Overview and Functioning
This specification requires OLSRv2 [RFC7181] to: This specification requires OLSRv2 [RFC7181] to:
o Identify all the reachable routers in the network. o Identify all the reachable routers in the network.
o Identify a sufficient subset of links in the networks, so that o Identify a sufficient subset of links in the networks, so that
routes can be calculated to all reachable destinations. routes can be calculated to all reachable destinations.
o Provide a Routing Set containing shortest routes from this router o Provide a Routing Set containing shortest routes from this router
to all destinations. to all destinations.
Based on the above information acquired by OLSRv2, the MP-OLSRv2 In addition, the MP-OLSRv2 Routing Process identifies the routers
Routing Process is able to calculate multiple paths to desired that support source routing by adding a new message TLV in HELLO and
destinations based on multi-path Dijkstra algorithm: the Dijkstra TC messages. Based on the above information acquired, every MP-
algorithm is performed multiple times . In each iteration, the cost OLSRv2 Routing Process is aware of a reduced topology map of the
of used links are increased (i.e., punished), so that they can be network and the routers supporting source routing.
avoided to be chosen in the next iteration. The multi-path Dijkstra
algorithm can generate multiple disjoint paths from a source to a A multi-path algorithm is invoked on demand, i.e., only when there is
destination , and such information is kept in Multi-path Routing Set. datagram to be sent from the source to the destination, and there is
The algorithm is invoked on demand, i.e., only when there is data no available routing tuple in the Multi-path Routing Set. The multi-
traffic to be sent from the source to the destination, and there is path Dijkstra algorithm can generate multiple disjoint paths from a
no available routing tuples in the Multi-path Routing Set. 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 The datagram is forwarded based on source routing. When there is a
datagram to be sent to a destination, the source router acquires 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 path from the Multi-path Routing Set (MAY be Round-Robin, or other
scheduling algorithms). The path information is stored in the scheduling algorithms). The path information is stored in the
datagram header as source routing header. datagram header as source routing header.
All the intermediate routers are listed in the source routing header All the intermediate routers are listed in the source routing header
(SRH), unless there are routers that do not support MP-OLSRv2 in the (SRH), unless there are routers that do not support source-route
paths, or the paths are too long to be fully stored in the SRH -- in forwarding in the paths, or the paths are too long to be fully stored
which case, loose source routing is used. The intermediate routers in the SRH -- in which case, loose source routing is used. The
listed in the SRH read the SRH and forward the datagram to the next intermediate routers listed in the SRH read the SRH and forward the
hop as indicated in the SRH. datagram to the next hop as indicated in the SRH.
5. Parameters and Constants 5. Parameters and Constants
In addition to the parameters and constants defined in [RFC7181], In addition to the parameters and constants defined in [RFC7181],
this specification uses the parameters and constants described in this specification uses the parameters and constants described in
this section. this section.
5.1. Router Parameters 5.1. Router Parameters
NUMBER_OF_PATHS The number of paths desired by the router. NUMBER_OF_PATHS The number of paths desired by the router.
skipping to change at page 7, line 29 skipping to change at page 7, line 37
used to increase costs of links belonging to the previously used to increase costs of links belonging to the previously
computed path. computed path.
fe Incremental function of multi-path Dijkstra algorithm. It is fe Incremental function of multi-path Dijkstra algorithm. It is
used to increase costs of links that lead to routers of the used to increase costs of links that lead to routers of the
previous computed path. previous computed path.
MR_HOLD_TIME It is the minimal time that a Multi-path Routing Tuple MR_HOLD_TIME It is the minimal time that a Multi-path Routing Tuple
SHOULD be kept in the Multi-path Routing Set. SHOULD be kept in the Multi-path Routing Set.
MP_OLSR_HOLD_TIME It is the minimal time that a MP-OLSRv2 Router SR_OLSR_HOLD_TIME It is the minimal time that a SR-OLSRv2 Router
Tuple SHOULD be kept in the MP-OLSRv2 Router Set. Tuple SHOULD be kept in the SR-OLSRv2 Router Set.
6. Packets and Messages 6. Packets and Messages
This extension employs the routing control messages HELLO and TC This extension employs the routing control messages HELLO and TC
(Topology Control) as defined in OLSRv2 [RFC7181]. To support source (Topology Control) as defined in OLSRv2 [RFC7181]. To support source
routing, a source routing header is added to each datagram routed by routing, a source routing header is added to each datagram routed by
this extension. Depending on the IP version used, the source routing this extension. Depending on the IP version used, the source routing
header is defined in following of this section. header is defined in following of this section.
6.1. HELLO and TC messages 6.1. HELLO and TC messages
HELLO and TC messages used by MP-OLSRv2 Routing Process share the HELLO and TC messages used by MP-OLSRv2 Routing Process share the
same format as defined in [RFC7181]. In addition, one Message TLV is same format as defined in [RFC7181]. In addition, two new Message
defined, to identify the originator of the HELLO or TC message is TLV types are defined, to identify the originator of the HELLO or TC
running MP-OLSRv2. message that supports source route forwarding. The new message TLV
types are 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. MP_OLSRv2 TLV 6.1.1. SR_OLSRv2 TLV
An MP_OLSRv2 TLV is a Message TLV that signals the message is An SR_OLSRv2 TLV is a Message TLV that signals the message is
generated by an MP-OLSRv2 Routing Process. It does not include any generated by a router that supports source-route forwarding. It can
value. 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 MP-OLSRv2 Routing Process MUST Every HELLO or TC message generated by MP-OLSRv2 Routing Process MUST
have one MP_OLSRv2 TLV. have one SR_OLSRv2 TLV.
Every HELLO or TC message generate by 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. Datagram
6.2.1. Source Routing Header in IPv4 6.2.1. Source Routing Header in IPv4
In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs
loose source routing header, as defined in [RFC0791]. It exists as loose source routing header, as defined in [RFC0791]. It exists as
an option header, with option class 0, and option number 3. an option header, with option class 0, and option number 3.
The source route information is kept in the "route data" field of the The source route information is kept in the "route data" field of the
skipping to change at page 8, line 34 skipping to change at page 9, line 14
The source route information is kept in the "Addresses" field of the The source route information is kept in the "Addresses" field of the
routing header. routing header.
7. Information Bases 7. Information Bases
Each MP-OLSRv2 routing process maintains the information bases as Each MP-OLSRv2 routing process maintains the information bases as
defined in [RFC7181]. Additionally, two more information bases are defined in [RFC7181]. Additionally, two more information bases are
defined for this specification. defined for this specification.
7.1. MP-OLSRv2 Router Set 7.1. SR-OLSRv2 Router Set
The MP-OLSRv2 Router Set recordes the routers running the MP-OLSRv2 The SR-OLSRv2 Router Set records the routers that supports source-
Routing Process. It consists of MP-OLSRv2 Router Tuples: 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:
(MP_OLSR_addr, MP_OLSR_valid_time) (SR_OLSR_addr, SR_OLSR_valid_time)
where: where:
MP_OLSR_addr - it is the network address of the router that runs SR_OLSR_addr - it is the network address of the router that
MP-OLSRv2 Routing Process; supports source-route forwarding;
MP_OLSR_valid_time - it is the time until which the MP-OLSRv2 SR_OLSR_valid_time - it is the time until which the SR-OLSRv2
Router Tuples is considered valid. Router Tuples is considered valid.
7.2. Multi-path Routing Set 7.2. Multi-path Routing Set
The Multi-path Routing Set records the full path information of The Multi-path Routing Set records the full path information of
different paths to the destination. It consists of Multi-path different paths to the destination. It consists of Multi-path
Routing Tuples: Routing Tuples:
(MR_dest_addr, MR_valid_time, MR_path_set) (MR_dest_addr, MR_valid_time, MR_path_set)
skipping to change at page 9, line 39 skipping to change at page 10, line 17
where: where:
PT_cost - the cost of the path to the destination; PT_cost - the cost of the path to the destination;
PT_address[1...n] - the addresses of intermediate routers to be PT_address[1...n] - the addresses of intermediate routers to be
visited numbered from 1 to n. visited numbered from 1 to n.
8. Protocol Details 8. Protocol Details
This protocol is based on OLSRv2, and extended to discover multiple This protocol is based on OLSRv2, and extended to discover multiple
disjoint paths from the source to the destination router. It retains disjoint paths from a source router to a destination router. It
the basic routing control packets formats and processing of OLSRv2 to retains the basic routing control packets formats and processing of
obtain topology information of the network. The main differences OLSRv2 to obtain topology information of the network. The main
between OLSRv2 routing process are the datagram processing at the differences between OLSRv2 routing process are the datagram
source router and datagram forwarding. processing at the source router and datagram forwarding.
8.1. HELLO and TC Message Generation 8.1. HELLO and TC Message Generation
HELLO and TC messages are generated according to the section 15.1 or HELLO and TC messages are generated according to the section 15.1 or
section 16.1 of [RFC7181]. section 16.1 of [RFC7181].
A single Message-Type-Specific TLV with Type := MP_OLSRv2 is added to A single Message-Type-Specific TLV with Type := SR_OLSRv2 MUST be
the message. added to the message.
8.2. HELLO and TC Message Processing 8.2. HELLO and TC Message Processing
HELLO and TC messages are processed according to the section 15.3 and HELLO and TC messages are processed according to the section 15.3 and
16.3 of [RFC7181]. 16.3 of [RFC7181].
For every HELLO or TC message received, if there exists a TLV with For every HELLO or TC message received, if there exists a TLV with
Type := MP_OLSRv2, create or update (if the tuple exists already) the Type := SR_OLSRv2, create or update (if the tuple exists already) the
MP-OLSR Router Tuple with SR-OLSR Router Tuple with
o MP_OLSR_addr = originator of the HELLO or TC message o SR_OLSR_addr = originator of the HELLO or TC message
and set the MP_OLSR_valid_time := current_time + MP_OLSR_HOLD_TIME. and set the SR_OLSR_valid_time := current_time + SR_OLSR_HOLD_TIME.
8.3. Datagram Processing at the MP-OLSRv2 Originator 8.3. Datagram Processing at the MP-OLSRv2 Originator
When the MP-OLSRv2 routing process receives a datagram from upper When the MP-OLSRv2 routing process receives a datagram from upper
layers or interfaces connecting other routing domains, find the layers or interfaces connecting other routing domains, find the
Multi-path Routing Tuple where: Multi-path Routing Tuple where:
o MR_dest_addr = destination of the datagram, and o MR_dest_addr = destination of the datagram, and
o MR_valid_time < current_time. o MR_valid_time < current_time.
If a matching Multi-path Routing Tuple is found, a Path Tuple is 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 chosen from the MR_path_set in Round-robin fashion (if there are
multiple datagrams to be sent). Or else, the Multi-path Dijkstra multiple datagrams to be sent). Or else, the multi-path algorithm
Algorithm defined in Section 8.4 is invoked, to generate the desired defined in Section 8.4 is invoked, to generate the desired Multi-path
Multi-path Routing Tuple. Routing Tuple.
The addresses in PT_address[1...n] of the chosen Path Tuple are thus The addresses in PT_address[1...n] of the chosen Path Tuple are thus
added to the datagram header in order as source routing header, added to the datagram header as source routing header, following the
following the rules: rules:
o Only the addresses exist in MP-OLSR Router Set can be added to the o Only the addresses exist in SR-OLSR Router Set can be added to the
source routing header. source routing header.
o If the length of the path (n) is greater than MAX_SRC_HOPS, only 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 the key routers in the path are kept. By default, the key routers
are uniformly chosen in the path. are uniformly chosen in the path.
o The routers with higher priority (such as higher willingness of o The routers with higher priority (such as higher routing
routing) are preferred. willingness) are preferred.
o The routers that are considered not appropriate for forwarding o The routers that are considered not appropriate for forwarding
indicated by external policies should be avoided. indicated by external policies should be avoided.
8.4. Multi-path Dijkstra Algorithm 8.4. Multi-path Dijkstra Algorithm
The Multi-path Dijkstra Algorithm is invoked when there is no A multi-path algorithm is invoked when there is no available Multi-
available Multi-path Routing Tuple to a desired destination d. The path Routing Tuple to a desired destination d to obtain the multiple
general principle of the algorithm is at step i to look for the paths. This section introduces Multi-path Dijkstra Algorithm as a
shortest path Pi to the destination d. Based on Dijkstra algorithm, default mechanism. The use of other algorithms is not prohibited, as
the main modification consists in adding two cost functions namely long as they can provide a full path from the source to the
incremental functions fp and fe in order to prevent the next steps to destination router. Using different multi-path algorithms will not
use similar path. fp is used to increase costs of arcs belonging to impact the interoperability.
the previously path Pi (or which opposite arcs belong to it). This
encourages future paths to use different arcs but not different The general principle of the Multi-path Dijkstra Algorithm is at step
vertices. fe is used to increase costs of the arcs who lead to i to look for the shortest path Pi to the destination d. Based on
vertices of the previous path Pi. It is possible to choose different Dijkstra algorithm, the main modification consists in adding two cost
fp and fe to get link-disjoint path or node-disjoint routes as functions namely incremental functions fp and fe in order to prevent
necessary. A recommendation of configuration of fp and fe is given the next steps to use similar path. fp is used to increase costs of
in Section 5. 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
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, ..., To get NUMBER_OF_PATHS distinct paths, for each path Pi (i = 1, ...,
NUMBER_OF_PATHS) do: NUMBER_OF_PATHS) do:
1. Run Dijkstra algorithm to get the shortest path Pi for the 1. Run Dijkstra algorithm to get the shortest path Pi for the
destination d. destination d.
2. Apply cost function fp to the links in Pi. 2. Apply cost function fp to the links in Pi.
3. Apply cost function fe to the links who lead to routers used in 3. Apply cost function fe to the links who lead to routers used in
P. P.
A simple example of Multi-path Dijkstra Algorithm is illustrated in A simple example of Multi-path Dijkstra Algorithm is illustrated in
Appendix A. Appendix A.
By invoking the algorithm depicted above, NUMBER_OF_PATHS distinct By invoking the algorithm depicted above, NUMBER_OF_PATHS distinct
paths is obtained, and added to the Multi-path Routing Set, by paths are obtained and added to the Multi-path Routing Set, by
creating a Multi-path Routing Tuple with: creating a Multi-path Routing Tuple with:
o MR_dest_addr := destination d o MR_dest_addr := destination d
o MR_valid_time := current time + MR_HOLD_TIME o MR_valid_time := current time + MR_HOLD_TIME
o Each Path Tuple in the MP_path_set corresponds to a path obtained 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 in multi-path Dijkstra algorithm, with PT_cost := cost of the path
to the destination d. to the destination d.
skipping to change at page 13, line 9 skipping to change at page 13, line 39
o MP_OLSR_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 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. 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 The setting of cost functions fp and fc defines the preference of
obtained multiple disjoint paths. If id is the identity functions, 3 obtained multiple disjoint paths. If id is the identity functions, 3
cases are possible: cases are possible:
o if id=fe<fp paths tend to be link disjoint; o if id=fe<fp: paths tend to be link disjoint;
o if id<fe=fp paths tend to be node-disjoint; o if id<fe=fp: paths tend to be node-disjoint;
o if id<fe<fp paths also tend to be node-disjoint, but when is not o if id<fe<fp: paths also tend to be node-disjoint, but when is not
possible they tend to be arc disjoint. possible they tend to be arc disjoint.
10. Implementation Status 10. Implementation Status
This section records the status of known implementations of the This section records the status of known implementations of the
protocol defined by this specification at the time of posting of this protocol defined by this specification at the time of posting of this
Internet-Draft, and based on a proposal described in [RFC6982]. The Internet-Draft, and based on a proposal described in [RFC6982]. The
description of implementations in this section is intended to assist description of implementations in this section is intended to assist
the IETF in its decision processes in progressing drafts to RFCs. the IETF in its decision processes in progressing drafts to RFCs.
Please note that the listing of any individual implementation here Please note that the listing of any individual implementation here
skipping to change at page 14, line 48 skipping to change at page 15, line 33
MP-OLSRv2 specification. MP-OLSRv2 specification.
The implementations without security mechanisms are vulnerable to The implementations without security mechanisms are vulnerable to
threats discussed in [I-D.clausen-manet-olsrv2-sec-threats]. As threats discussed in [I-D.clausen-manet-olsrv2-sec-threats]. As
[RFC7181], a conformant implementation of MP-OLSRv2 MUST, at minimum, [RFC7181], a conformant implementation of MP-OLSRv2 MUST, at minimum,
implement the security mechanisms specified in [RFC7183] to provide implement the security mechanisms specified in [RFC7183] to provide
integrity and replay protection of routing control messages. integrity and replay protection of routing control messages.
Compared to OLSRv2, the use of source routing header in this Compared to OLSRv2, the use of source routing header in this
specification introduces vulnerabilities related to source routing specification introduces vulnerabilities related to source routing
attacks. Those attacks include bypassing filtering devices, attacks, which include bypassing filtering devices, bandwidth
bandwidth exhaustion of certain routers, etc. To make sure that the exhaustion of certain routers, etc. Those attacks are discussed in
Section 5.1 of [RFC6554] and [RFC5095]. To make sure that the
influence is limited to the OLSRv2/MP-OLSRv2 routing domain, the influence is limited to the OLSRv2/MP-OLSRv2 routing domain, the
source routing header MUST be used only in the current routing source routing header MUST be used only in the current routing
domain. domain.
12. IANA Considerations 12. IANA Considerations
This specification defines two Message TLV Types, which must be This specification defines two Message TLV Types, which must be
allocated from the Message TLV Types repository of [RFC5444]. allocated from the Message TLV Types repository of [RFC5444].
12.1. HELLO Message-Type-Specific TLV Type Registries 12.1. HELLO Message-Type-Specific TLV Type Registries
IANA is requested to create a registry for Message-Type-Specific IANA is requested to create a registry for Message-Type-Specific
Message TLV for HELLO messages, in accordance with Section 6.2.1 of Message TLV for HELLO messages, in accordance with Section 6.2.1 of
[RFC5444], and with initial assignments and allocation policies as [RFC5444], and with initial assignments and allocation policies as
specified in Table 1. specified in Table 1.
+---------+-------------+-------------------+ +---------+-------------+-------------------+
| Type | Description | Allocation Policy | | Type | Description | Allocation Policy |
+---------+-------------+-------------------+ +---------+-------------+-------------------+
| 129 | MP_OLSRv2 | | | 129 | SR_OLSRv2 | |
| 130-223 | Unassigned | Expert Review | | 130-223 | Unassigned | Expert Review |
+---------+-------------+-------------------+ +---------+-------------+-------------------+
Table 1: HELLO Message-Type-specific Message TLV Types Table 1: HELLO Message-Type-specific Message TLV Types
12.2. TC Message-Type-Specific TLV Type Registries 12.2. TC Message-Type-Specific TLV Type Registries
IANA is requested to create a registry for Message-Type-Specific IANA is requested to create a registry for Message-Type-Specific
Message TLV for TC messages, in accordance with Section 6.2.1 of Message TLV for TC messages, in accordance with Section 6.2.1 of
[RFC5444], and with initial assignments and allocation policies as [RFC5444], and with initial assignments and allocation policies as
specified in Table 2. specified in Table 2.
+---------+-------------+-------------------+ +---------+-------------+-------------------+
| Type | Description | Allocation Policy | | Type | Description | Allocation Policy |
+---------+-------------+-------------------+ +---------+-------------+-------------------+
| 128 | MP_OLSRv2 | | | 128 | SR_OLSRv2 | |
| 129-223 | Unassigned | Expert Review | | 129-223 | Unassigned | Expert Review |
+---------+-------------+-------------------+ +---------+-------------+-------------------+
Table 2: TC Message-Type-specific Message TLV Types Table 2: TC Message-Type-specific Message TLV Types
13. Acknowledgments 13. Acknowledgments
The authors would like to thank Sylvain David, Asmaa Adnane, Eddy The authors would like to thank Sylvain David, Asmaa Adnane, Eddy
Cizeron, Salima Hamma, Pascal Lesage and Xavier Lecourtier for their Cizeron, Salima Hamma, Pascal Lesage and Xavier Lecourtier for their
efforts in developing, implementing and testing the specifications. efforts in developing, implementing and testing the specifications.
The authors also appreciate valuable comments and discussions from The authors also appreciate valuable comments and discussions from
Thomas Clausen, Ulrich Herberg, Geoff Ladwig and Henning Rogge. Thomas Clausen, Ulrich Herberg, Justin Dean, Geoff Ladwig and Henning
Rogge.
14. References 14. References
14.1. Normative References 14.1. Normative References
[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981. September 1981.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
skipping to change at page 17, line 4 skipping to change at page 17, line 40
[I-D.clausen-manet-olsrv2-sec-threats] [I-D.clausen-manet-olsrv2-sec-threats]
Clausen, T., Herberg, U., and J. Yi, "Security Threats for Clausen, T., Herberg, U., and J. Yi, "Security Threats for
the Optimized Link State Routing Protocol version 2 the Optimized Link State Routing Protocol version 2
(OLSRv2)", draft-clausen-manet-olsrv2-sec-threats-01 (work (OLSRv2)", draft-clausen-manet-olsrv2-sec-threats-01 (work
in progress), August 2014. in progress), August 2014.
[I-D.ietf-manet-olsrv2-dat-metric] [I-D.ietf-manet-olsrv2-dat-metric]
Rogge, H. and E. Baccelli, "Packet Sequence Number based Rogge, H. and E. Baccelli, "Packet Sequence Number based
directional airtime metric for OLSRv2", directional airtime metric for OLSRv2",
draft-ietf-manet-olsrv2-dat-metric-02 (work in progress), draft-ietf-manet-olsrv2-dat-metric-05 (work in progress),
August 2014. April 2015.
[I-D.ietf-manet-olsrv2-multitopology] [I-D.ietf-manet-olsrv2-multitopology]
Dearlove, C. and T. Clausen, "Multi-Topology Extension for Dearlove, C. and T. Clausen, "Multi-Topology Extension for
the Optimized Link State Routing Protocol version 2 the Optimized Link State Routing Protocol version 2
(OLSRv2)", draft-ietf-manet-olsrv2-multitopology-04 (work (OLSRv2)", draft-ietf-manet-olsrv2-multitopology-05 (work
in progress), July 2014. in progress), February 2015.
[RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", RFC 2460, December 1998. (IPv6) Specification", RFC 2460, December 1998.
[RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black, [RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black,
"Definition of the Differentiated Services Field (DS "Definition of the Differentiated Services Field (DS
Field) in the IPv4 and IPv6 Headers", RFC 2474, Field) in the IPv4 and IPv6 Headers", RFC 2474,
December 1998. December 1998.
[RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking [RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking
(MANET): Routing Protocol Performance Issues and (MANET): Routing Protocol Performance Issues and
Evaluation Considerations", RFC 2501, January 1999. Evaluation Considerations", RFC 2501, January 1999.
[RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and [RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
Multicast Next-Hop Selection", RFC 2991, November 2000. Multicast Next-Hop Selection", RFC 2991, November 2000.
[RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation
of Type 0 Routing Headers in IPv6", RFC 5095,
December 2007.
[RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", RFC 6982, Code: The Implementation Status Section", RFC 6982,
July 2013. July 2013.
[WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein,
"Simulation and performance analysis of MP-OLSR for mobile "Simulation and performance analysis of MP-OLSR for mobile
ad hoc networks", In Proceeding of IEEE Wireless ad hoc networks", In Proceeding of IEEE Wireless
Communications and Networking Conference, 2008. Communications and Networking Conference, 2008.
Appendix A. An example of Multi-path Dijkstra Algorithm Appendix A. An example of Multi-path Dijkstra Algorithm
 End of changes. 63 change blocks. 
139 lines changed or deleted 177 lines changed or added

This html diff was produced by rfcdiff 1.42. The latest version is available from http://tools.ietf.org/tools/rfcdiff/