draft-ietf-manet-olsrv2-multipath-15.txt   rfc8218.txt 
Network Working Group J. Yi Internet Engineering Task Force (IETF) J. Yi
Internet-Draft Ecole Polytechnique Request for Comments: 8218 Ecole Polytechnique
Intended status: Experimental B. Parrein Category: Experimental B. Parrein
Expires: November 25, 2017 University of Nantes ISSN: 2070-1721 University of Nantes
May 24, 2017 August 2017
Multipath Extension for the Optimized Link State Routing Protocol Multipath Extension for the
version 2 (OLSRv2) Optimized Link State Routing Protocol Version 2 (OLSRv2)
draft-ietf-manet-olsrv2-multipath-15
Abstract Abstract
This document specifies a multipath extension for the Optimized Link This document specifies a multipath 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 for Mobile Ad Hoc Networks (MANETs). Considering the disjoint paths for Mobile Ad Hoc Networks (MANETs). Considering the
characteristics of MANETs, especially the dynamic network topology, characteristics of MANETs, especially the dynamic network topology,
using multiple paths can increase aggregated throughput and improve using multiple paths can increase aggregated throughput and improve
the reliability by avoiding single route failures. The the reliability by avoiding single route failures. The
interoperability with OLSRv2 is retained. interoperability with OLSRv2 is retained.
Status of this Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering This document is not an Internet Standards Track specification; it is
Task Force (IETF). Note that other groups may also distribute published for examination, experimental implementation, and
working documents as Internet-Drafts. The list of current Internet- evaluation.
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document defines an Experimental Protocol for the Internet
and may be updated, replaced, or obsoleted by other documents at any community. This document is a product of the Internet Engineering
time. It is inappropriate to use Internet-Drafts as reference Task Force (IETF). It represents the consensus of the IETF
material or to cite them other than as "work in progress." community. It has received public review and has been approved for
publication by the Internet Engineering Steering Group (IESG). Not
all documents approved by the IESG are a candidate for any level of
Internet Standard; see Section 2 of RFC 7841.
This Internet-Draft will expire on November 25, 2017. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc8218.
Copyright Notice Copyright Notice
Copyright (c) 2017 IETF Trust and the persons identified as the Copyright (c) 2017 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
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3 1.1. Motivation and Experiments to Be Conducted . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 7
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 8
5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 8 5. Parameters and Constants . . . . . . . . . . . . . . . . . . 9
5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 8 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 9
6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 9 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . 10
6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 9 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 10
6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . . 9 6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . 10
6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . 11
6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 9 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 11
6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 10 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 11
7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 10 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 11
7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 10 7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . 11
7.2. Multipath Routing Set . . . . . . . . . . . . . . . . . . 10 7.2. Multipath Routing Set . . . . . . . . . . . . . . . . . . 12
8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 11 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . 12
8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 11 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 12
8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 12 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 13
8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 12 8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 13
8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 12 8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 14
8.5. Multipath Calculation . . . . . . . . . . . . . . . . . . 14 8.5. Multipath Calculation . . . . . . . . . . . . . . . . . . 15
8.5.1. Requirements of Multipath Calculation . . . . . . . . 14 8.5.1. Requirements of Multipath Calculation . . . . . . . . 15
8.5.2. Multipath Dijkstra Algorithm . . . . . . . . . . . . . 15 8.5.2. Multipath Dijkstra Algorithm . . . . . . . . . . . . 16
8.6. Multipath Routing Set Updates . . . . . . . . . . . . . . 16 8.6. Multipath Routing Set Updates . . . . . . . . . . . . . . 18
8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 17 8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 18
9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 17 9. Configuration Parameters . . . . . . . . . . . . . . . . . . 18
10. Implementation Status . . . . . . . . . . . . . . . . . . . . 18 10. Security Considerations . . . . . . . . . . . . . . . . . . . 19
10.1. Multipath extension based on nOLSRv2 . . . . . . . . . . . 19 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
10.2. Multipath extension based on olsrd . . . . . . . . . . . . 19 11.1. Message TLV Types . . . . . . . . . . . . . . . . . . . 20
10.3. Multipath extension based on umOLSR . . . . . . . . . . . 19 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
11. Security Considerations . . . . . . . . . . . . . . . . . . . 19 12.1. Normative References . . . . . . . . . . . . . . . . . . 21
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 12.2. Informative References . . . . . . . . . . . . . . . . . 22
12.1. Message TLV Types . . . . . . . . . . . . . . . . . . . . 21 Appendix A. Examples of Multipath Dijkstra Algorithm . . . . . . 24
13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 25
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 26
14.1. Normative References . . . . . . . . . . . . . . . . . . . 21
14.2. Informative References . . . . . . . . . . . . . . . . . . 22
Appendix A. Examples of Multipath Dijkstra Algorithm . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25
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 a 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]
[RFC7181], to provide multiple disjoint paths when appropriate for a to provide multiple disjoint paths when appropriate for a source-
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 forwarding helpful for increasing network throughput, improving forwarding
reliability, and load balancing. reliability, and load-balancing.
Multipath OLSRv2 (MP-OLSRv2) specified in this document uses the Multipath OLSRv2 (MP-OLSRv2), specified in this document, uses the
Multipath Dijkstra algorithm by default to explore multiple disjoint Multipath Dijkstra Algorithm by default to explore multiple disjoint
paths from a source router to a destination router based on the paths from a source router to a destination router based on the
topology information obtained through OLSRv2, and to forward the topology information obtained through OLSRv2 and to forward the
datagrams in a load-balancing manner using source routing. MP-OLSRv2 datagrams in a load-balancing manner using source routing. MP-OLSRv2
is designed to be interoperable with 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 datagrams over multiple disjoint MANET scenarios by transmitting datagrams over multiple disjoint
paths 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. aggregated throughput.
o Some scenarios may require some routers must (or must not) be o Some scenarios may require that some routers must (or must not) be
used. used.
o Having control of the paths at the source benefits the load o Having control of the paths at the source benefits the load-
balancing and traffic engineering. balancing and traffic engineering.
o An application of this extension is in combination with Forward o An application of this extension is in combination with Forward
Error Correction (FEC) coding applied across packets (erasure Error Correction (FEC) coding applied across packets (erasure
coding) [WPMC11]. Because the packet drops are normally bursty in coding) [WPMC11]. Because the packet drops are normally bursty in
a path (for example, due to route failure), erasure coding is less a path (for example, due to route failure), erasure coding is less
effective in single path routing protocols. By providing multiple effective in single path routing protocols. By providing multiple
disjoint paths, the application of erasure coding with multipath disjoint paths, the application of erasure coding with multipath
protocol is more resilient to routing failures. protocol is more resilient to routing failures.
While in existing deployments, running code and simulations have In existing deployments, while running code and simulations have
proven the interest of multipath extension for OLSRv2 in certain proven the interest of multipath extension for OLSRv2 in certain
networks, more experiments and experiences are still needed to networks [GIIS14][WCNC08][ADHOC11], more experiments and experiences
understand the effects of the protocol specified in this experimental are still needed to understand the effects of the protocol specified
document. The multipath extension for OLSRv2 is expected to be in this Experimental RFC. The multipath extension for OLSRv2 is
revised documented as a Standard Track document once sufficient expected to be revised and documented as a Standards Track RFC once
operational experience is obtained. Other than general experiences, sufficient operational experience is obtained. Other than general
including the protocol specification and interoperability with base experiences, including the protocol specification and
OLSRv2 implementations, experiences in the following aspects are interoperability with base OLSRv2 implementations, experiences in the
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,
Section 5) to be used. This depends on the network topology and see Section 5) to be used. This depends on the network topology
router density. and router density.
o Optimal values used in the metric functions. Metric functions are o Optimal values used in the metric functions. Metric functions are
applied to increase the metric of used links and nodes so as to applied to increase the metric of used links and nodes so as to
obtain disjoint paths. What kind of disjointness is desired obtain disjoint paths. What kind of disjointness is desired (node
(node-disjoint or link-disjoint) may depend on the layer 2 disjoint or link disjoint) may depend on the Layer 2 protocol used
protocol used, and can be achieved by applying different sets of and can be achieved by applying different sets of metric
metric functions. functions.
o Use of different metric types. This multipath extension can be o Use of different metric types. This multipath extension can be
used with metric types that meet the requirement of OLSRv2, such used with metric types that meet the requirement of OLSRv2, such
as [RFC7779]. The metric type used has also impact to the choice as [RFC7779]. The metric type used also has an impact on the
of metric functions as indicated in the previous bullet point. choice of metric functions as indicated in the previous bullet
point.
o The impact of partial topology information to multipath o The impact of partial topology information to multipath
calculation. OLSRv2 maintains a partial topology information base calculation. OLSRv2 maintains a partial topology information base
to reduce protocol overhead. Experience has shown that multiple to reduce protocol overhead. Experience has shown that multiple
paths can be obtained even with such partial information, however, paths can be obtained even with such partial information; however,
depending on the Multi-Point Relay (MPR) selection algorithm used, depending on the Multipoint Relay (MPR) selection algorithm used,
the disjointness of the multiple paths might be impacted depending the disjointness of the multiple paths might be impacted depending
on the Multi-Point Relay (MPR) selection algorithm used. on the Multipoint Relay (MPR) selection algorithm used.
o Use of IPv6 loose source routing. In the current specification, o Use of IPv6 loose source routing. In the current specification,
only strict source routing is used for IPv6 based on [RFC6554]. only strict source routing is used for IPv6 based on [RFC6554].
In [I-D.ietf-6man-segment-routing-header], the use of the loose In [IPv6-SRH], the use of the loose source routing is also
source routing is also proposed in IPv6. In scenarios where the proposed in IPv6. In scenarios where the length of the source
length of the source routing header is critical, the loose source routing header is critical, the loose source routing can be
routing can be considered. considered.
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 parts of this document, optimal choices defined in the following parts of this document, optimal choices
of routers to put in the loose source routing header can be of routers to put in the loose source routing header can be
further studied. further studied.
o Different path-selection schedulers. Depending on the application o Different path-selection schedulers. Depending on the application
type and transport layer type, either per-flow scheduler or per- type and transport layer type, either a per-flow scheduler or per-
datagram scheduler is applied. By default, the traffic load datagram scheduler is applied. By default, the traffic load
should be equally distributed in multiple paths. In some should be equally distributed in multiple paths. In some
scenarios, weighted scheduling can be considered: for example, the scenarios, weighted scheduling can be considered: for example, the
paths with lower metrics (i.e., higher quality) can transfer more paths with lower metrics (i.e., higher quality) can transfer more
datagrams or flows compared to paths with higher metrics. datagrams or flows compared to paths with higher metrics.
o The impacts of the delay variation due to multipath routing. o The impacts of the delay variation due to multipath routing.
[RFC2991] brings out some concerns of multipath routing, [RFC2991] brings out some concerns of multipath routing,
especially variable latencies when per-datagram scheduling is especially variable latencies when per-datagram scheduling is
applied. Although current experiment results show that multipath applied. Although current experiment results show that multipath
routing can reduce the jitter in dynamic scenarios, some transport routing can reduce the jitter in dynamic scenarios, some transport
protocols or applications may be sensitive to the datagram re- protocols or applications may be sensitive to the datagram
ordering. reordering.
o The disjoint multipath protocol has interesting application with o The disjoint multipath protocol has an interesting application
erasure coding, especially for services like video/audio streaming with erasure coding, especially for services like video/audio
[WPMC11]. The combination of erasure coding mechanisms and this streaming [WPMC11]. The combination of erasure coding mechanisms
extension is thus encouraged. and this extension is thus encouraged.
o Different algorithms to obtain multiple paths, other than the o Different algorithms to obtain multiple paths, other than the
default Multipath Dijkstra algorithm introduced in Section 8.5.2 default Multipath Dijkstra Algorithm introduced in Section 8.5.2
of this specification. of this specification.
o The use of multi-topology information. By using [RFC7722], o The use of multitopology information. By using [RFC7722],
multiple topologies using different metric types can be obtained. multiple topologies using different metric types can be obtained.
Although there is no work defining how this extension can make use Although there is no work defining how this extension can make use
of the multi-topology information base yet, it is encouraged to of the multitopology information base yet, experimentation with
experiment with the use of multiple metrics for building multiple the use of multiple metrics for building multiple paths is
paths. encouraged.
Comments are solicited and should be addressed to the MANET working Comments are solicited and should be addressed to the MANET working
group's mailing list at manet@ietf.org and/or the authors." group's mailing list at manet@ietf.org and/or the authors.
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 BCP
[RFC2119]. 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
This document uses the terminology and notation defined in [RFC5444], This document uses the terminology and notation defined in [RFC5444],
[RFC6130], [RFC7181]. Additionally, it defines the following [RFC6130], and [RFC7181]. Additionally, it defines the following
terminology: terminology:
OLSRv2 Routing Process - A routing process based on [RFC7181], OLSRv2 Routing Process: A routing process based on [RFC7181],
without multipath extension specified in this document. without multipath extension specified in this document.
MP-OLSRv2 Routing Process - A multipath routing process based on MP-OLSRv2 Routing Process: A Multipath Routing Process based on this
this specification as an extension to [RFC7181]. specification as an extension to [RFC7181].
SR-OLSRv2 Routing Process - A OLSRv2 Routing Process that supports SR-OLSRv2 Routing Process: An OLSRv2 Routing Process that supports
source routing (SR), or an MP-OLSRv2 Routing Process. Source Routing (SR) or an MP-OLSRv2 Routing Process.
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. MP-OLSRv2 is designed from a source router to a destination router. MP-OLSRv2 is designed
for networks with dynamic topology to avoid single route failure. It for networks with dynamic topology to avoid single route failure. It
can also provide higher aggregated throughput and load balancing. can also provide higher aggregated throughput and load-balancing.
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 multipath routing (mainly video or applications that are suitable for multipath routing (mainly video or
audio streams), based on information such as a DiffServ codepoint audio streams) based on information such as a Diffserv codepoint
[RFC2474]. [RFC2474].
Compared to OLSRv2, this extension does not introduce any new message Compared to OLSRv2, this extension does not introduce any new message
type. A new Message TLV Type is introduced to identify the routers type. A new Message TLV Type is introduced to identify the routers
that support forwarding based on source routing header. It is that support forwarding based on the source routing header. It is
interoperable with OLSRv2 implementations that do not have this interoperable with OLSRv2 implementations that do not have this
extension: as the MP-OLSRv2 uses source routing, in IPv4 networks the extension: as the MP-OLSRv2 uses source routing, in IPv4 networks the
interoperability is achieved using loose source routing headers; in interoperability is achieved using loose source routing headers; in
IPv6 networks, it is achieved by eliminating routers that do not IPv6 networks, it is achieved by eliminating routers that do not
support IPv6 strict source routing. support IPv6 strict source routing.
MP-OLSRv2 supports two different, but interoperable multipath MP-OLSRv2 supports two different but interoperable multipath
calculation approaches: proactive and reactive. In the proactive calculation approaches: proactive and reactive. In the proactive
calculation, the paths to all the destinations are calculated before calculation, the paths to all the destinations are calculated before
needed. In the reactive calculation, only the paths to desired they are needed. In the reactive calculation, only the paths to
destination(s) are calculated on demand. The proactive approach desired destination(s) are calculated on demand. The proactive
requires more computational resources than the reactive one. The approach requires more computational resources than the reactive one.
reactive approach requires the IP forwarding plane to trigger the The reactive approach requires the IP forwarding plane to trigger the
multipath calculation. multipath calculation.
MP-OLSRv2 forwards datagrams using the source routing header. As MP-OLSRv2 forwards datagrams using the source routing header. As
there are multiple paths to each destination, MP-OLSRv2 requires the there are multiple paths to each destination, MP-OLSRv2 requires the
IP forwarding plane to be able to choose which source route to be put IP forwarding plane to be able to choose which source route to be put
in the source routing header based on the path scheduler defined by in the source routing header based on the path scheduler defined by
MP-OLSRv2. For IPv4 networks, implementation of loose source routing MP-OLSRv2. For IPv4 networks, implementation of loose source routing
is required following [RFC0791]. For IPv6 networks, implementation is required following [RFC791]. For IPv6 networks, implementation of
of strict source routing is required following the source routing strict source routing is required following the source routing header
header generation and processing defined in [RFC6554]. generation and processing defined in [RFC6554].
4. Protocol Overview and Functioning 4. Protocol Overview and Functioning
This specification uses OLSRv2 [RFC7181] to: This specification uses 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 the shortest routes from this o Provide a Routing Set containing the shortest routes from this
router to all destinations. router to all destinations.
In addition, the MP-OLSRv2 Routing Process identifies the routers In addition, the MP-OLSRv2 Routing Process identifies the routers
that support source routing by adding a new Message TLV in HELLO and that support source routing by adding a new Message TLV in HELLO and
Topology Control (TC) messages. Based on the above information Topology Control (TC) messages. Based on the above information
acquired, every MP-OLSRv2 Routing Process is aware of a reduced acquired, every MP-OLSRv2 Routing Process is aware of a reduced
topology map of the network and the routers supporting source topology map of the network and the routers supporting source
routing. routing.
A Multipath Routing Set containing the multipath information is A Multipath Routing Set containing the multipath information is
maintained. It may either be proactively calculated or reactively maintained. It may be either proactively calculated or reactively
calculated: calculated:
o In the proactive approach, multiple paths to all possible o In the proactive approach, multiple paths to all possible
destinations are calculated and updated based on control message destinations are calculated and updated based on control message
exchange. The routes are thus available before they are actually exchange. The routes are thus available before they are actually
needed. needed.
o In the reactive approach, a multipath algorithm is invoked on o In the reactive approach, a multipath algorithm is invoked on
demand, i.e., only when there is a datagram to be sent from the demand, i.e., only when there is a datagram to be sent from the
source to the destination, and there is no available Routing Tuple source to the destination and there is no available Routing Tuple
in the Multipath Routing Set. This requires the IP forwarding in the Multipath Routing Set. This requires the IP forwarding
information base to trigger the multipath calculation specified in information base to trigger the multipath calculation specified in
Section 8.5 when no Multipath Routing Tuple is available. The Section 8.5 when no Multipath Routing Tuple is available. The
reactive operation is local to the router and no additional reactive operation is local to the router and no additional
routing control messages exchange is required. When the paths are exchange of routing control messages is required. When the paths
being calculated, the datagrams SHOULD be buffered unless the are being calculated, the datagrams SHOULD be buffered unless the
router does not have enough memory. router does not have enough memory.
Routers in the same network may choose either proactive or reactive Routers in the same network may choose either proactive or reactive
multipath calculation independently according to their computation multipath calculation independently according to their computation
resources. The Multipath Dijkstra algorithm (defined in Section 8.5) resources. The Multipath Dijkstra Algorithm (defined in Section 8.5)
is introduced as the default algorithm to generate multiple disjoint is introduced as the default algorithm to generate multiple disjoint
paths from a source to a destination, and such information is kept in paths from a source to a destination, and such information is kept in
the Multipath Routing Set. the Multipath 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 Multipath Routing Set. The path information is stored path from the Multipath Routing Set. The path information is stored
in the datagram header using the source routing header. in the datagram header using the source routing header.
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.
MAX_SRC_HOPS The maximum number of hops allowed to be put in the MAX_SRC_HOPS: The maximum number of hops allowed to be put in the
source routing header. A value set zero means there is no source routing header. A value set to 0 means there is no
limitation on the maximum number of hops. In an IPv6 network, it limitation on the maximum number of hops. In an IPv6 network, it
MUST be set to 0 because [RFC6554] supports only strict source MUST be set to 0 because [RFC6554] supports only strict source
routing. All the intermediate routers MUST be included in the routing. All the intermediate routers MUST be included in the
source routing header, which a various number of hops. In an IPv4 source routing header, which is a various number of hops. In an
network, it MUST be strictly less than 11 and greater than 0 due IPv4 network, it MUST be strictly less than 11 and greater than 0
to the length limit of the IPv4 header. due to the length limit of the IPv4 header.
CUTOFF_RATIO The ratio that defines the maximum metric of a path CUTOFF_RATIO: The ratio that defines the maximum metric of a path
compared to the shortest path kept in the OLSRv2 Routing Set. For compared to the shortest path kept in the OLSRv2 Routing Set. For
example, the metric to a destination is R_metric based on the example, the metric to a destination is R_metric based on the
Routing Set. Then the maximum metric allowed for a path is Routing Set. Then, the maximum metric allowed for a path is
CUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be greater than or CUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be greater than or
equal to 1. Setting the number low makes it less likely that equal to 1. Setting the number low makes it less likely that
additional paths will be found -- for example, setting it to 1 additional paths will be found -- for example, setting it to 1
will only consider equal length paths. will mean only equal length paths are considered.
SR_TC_INTERVAL The maximum time between the transmission of two SR_TC_INTERVAL: The maximum time between the transmission of two
successive TC messages by an MP-OLSRv2 Routing Process. successive TC messages by an MP-OLSRv2 Routing Process.
SR_HOLD_TIME The minimum value in the TLV with Type = VALIDITY_TIME SR_HOLD_TIME: The minimum value in the TLV with Type = VALIDITY_TIME
included in TC messages generated based on SR_TC_INTERVAL. included in TC messages generated based on SR_TC_INTERVAL.
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 as
(Topology Control) as defined in OLSRv2 [RFC7181] to obtain network defined in OLSRv2 [RFC7181] to obtain network topology information.
topology information. For the datagram to support source routing, a For the datagram to support source routing, a source routing header
source routing header is added to each datagram routed by this is added to each datagram routed by this extension. Depending on the
extension. Depending on the IP version used, the source routing IP version used, the source routing header is defined in this
header is defined in this section. section.
6.1. HELLO and TC messages 6.1. HELLO and TC messages
HELLO and TC messages used by the MP-OLSRv2 Routing Process use the HELLO and TC messages used by the MP-OLSRv2 Routing Process use the
same format as defined in [RFC7181]. In addition, a new Message TLV same format as defined in [RFC7181]. In addition, a new Message TLV
type is defined, to identify the originator of the HELLO or TC Type is defined to identify the originator of the HELLO or TC message
message that supports source route forwarding. The new Message TLV that supports source-route forwarding. The new Message TLV Type is
type is introduced for enabling MP-OLSRv2 as an extension of OLSRv2: introduced for enabling MP-OLSRv2 as an extension of OLSRv2: only the
only the routers supporting source-route forwarding can be used in routers supporting source-route forwarding can be used in the source
the source routing header of a datagram, because adding a router that routing header of a datagram because adding a router that does not
does not understand the source routing header will cause routing understand the source routing header will cause routing failure.
failure.
6.1.1. SOURCE_ROUTE TLV 6.1.1. SOURCE_ROUTE TLV
SOURCE_ROUTE TLV is a Message TLV signaling that the message is The SOURCE_ROUTE TLV is a Message TLV signaling that the message is
generated by a router that supports source-route forwarding. It can generated by a router that supports source-route forwarding. It can
be an MP-OLSRv2 Routing Process, or an OLSRv2 Routing Process that be an MP-OLSRv2 Routing Process or an OLSRv2 Routing Process that
supports source-route forwarding. supports source-route forwarding.
Every HELLO or TC message generated by a MP-OLSRv2 Routing Process Every HELLO or TC message generated by a MP-OLSRv2 Routing Process
MUST have exactly one SOURCE_ROUTE TLV without value. MUST have exactly one SOURCE_ROUTE TLV without value.
Every HELLO or TC message generated by an OLSRv2 Routing Process MUST Every HELLO or TC message generated by an OLSRv2 Routing Process MUST
have exactly one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process have exactly one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process
supports source-route forwarding, and is willing to join the source supports source-route forwarding, and be willing to join the source
route generated by other MP-OLSRv2 Routing Processes. The existence route generated by other MP-OLSRv2 Routing Processes. The existence
of SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing of SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing
Process, i.e., either it adds SOURCE_ROUTE TLV to all its HELLO/TC Process, i.e., either it adds SOURCE_ROUTE TLV to all its HELLO/TC
messages, or it does not add SOURCE_ROUTE TLV to any HELLO/TC messages or it does not add SOURCE_ROUTE TLV to any HELLO/TC
messages. messages.
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 the In IPv4 [RFC791] networks, the MP-OLSRv2 Routing Process employs the
loose source routing header, as defined in [RFC0791]. It exists as loose source routing header, as defined in [RFC791]. It exists as an
an option header, with option class 0, and option number 3. 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
loose source route header. loose source routing header.
6.2.2. Source Routing Header in IPv6 6.2.2. Source Routing Header in IPv6
In IPv6 [RFC2460] networks, the MP-OLSRv2 Routing Process employs the In IPv6 [RFC8200] networks, the MP-OLSRv2 Routing Process employs the
source routing header as defined in section 3 of [RFC6554], with IPv6 source routing header, as defined in Section 3 of [RFC6554], with
Routing Type 3. IPv6 Routing Type 3.
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, a Multipath Information Base is defined in [RFC7181]. Additionally, a Multipath Information Base is
used for this specification. It includes the protocol sets as used for this specification. It includes the protocol sets as
defined below. defined below.
7.1. SR-OLSRv2 Router Set 7.1. SR-OLSRv2 Router Set
The SR-OLSRv2 Router Set records the routers that support source- The SR-OLSRv2 Router Set records the routers that support source-
route forwarding. This includes routers that run the MP-OLSRv2 route forwarding. This includes routers that run the MP-OLSRv2
Routing Process or the OLSRv2 Routing Process with source-route Routing Process or the OLSRv2 Routing Process with source-route
forwarding support. The set consists of SR-OLSRv2 Router Tuples: forwarding support. The set consists of SR-OLSRv2 Routing Tuple:
(SR_addr, SR_time) (SR_addr, SR_time)
where: where:
SR_addr - is the originator address of the router that supports SR_addr is the originator address of the router that supports
source-route forwarding; source-route forwarding.
SR_time - is the time until which the SR-OLSRv2 Router Tuple is SR_time is the time until which the SR-OLSRv2 Routing Tuple is
considered valid. considered valid.
7.2. Multipath Routing Set 7.2. Multipath Routing Set
The Multipath Routing Set records the full path information of The Multipath Routing Set records the full path information of
different paths to the destination. It consists of Multipath Routing different paths to the destination. It consists of Multipath Routing
Tuples: Tuple:
(MR_dest_addr, MR_path_set) (MR_dest_addr, MR_path_set)
where: where:
MR_dest_addr - is the network address of the destination, either MR_dest_addr is the network address of the destination; it is
the network address of an interface of a destination router or the either the network address of an interface of a destination router
network address of an attached network; or the network address of an attached network.
MP_path_set - contains the multiple paths to the destination. It MP_path_set contains the multiple paths to the destination and it
consists of a set of Path Tuples. consists of a set of Path Tuples.
Each Path Tuple is defined as: Each Path Tuple is defined as:
(PT_metric, PT_address[1], PT_address[2], ..., PT_address[n]) (PT_metric, PT_address[1], PT_address[2], ..., PT_address[n])
where: where:
PT_metric - is the metric of the path to the destination, measured PT_metric is the metric of the path to the destination, measured
in LINK_METRIC_TYPE defined in [RFC7181]; in LINK_METRIC_TYPE defined in [RFC7181].
PT_address[1, ..., n-1] - are the addresses of intermediate routers PT_address[1, ..., n-1] are the addresses of intermediate routers
to be visited numbered from 1 to n-1, where n is the number of to be visited, numbered from 1 to n-1, where n is the number of
routers in the path, i.e., the hop count. routers in the path, i.e., the hop count.
8. Protocol Details 8. Protocol Details
This protocol is based on OLSRv2, and extended to discover multiple This protocol is based on OLSRv2 and is extended to discover multiple
disjoint paths from a source router to a destination router. It disjoint paths from a source router to a destination router. It
retains the basic routing control packets formats and processing of retains the formats of the basic routing control packets and the
OLSRv2 to obtain the topology information of the network. The main processing of OLSRv2 to obtain the topology information of the
differences from the OLSRv2 Routing Process are the datagram network. The main differences from the OLSRv2 Routing Process are
processing at the source router and datagram forwarding. the datagram processing at the source router and datagram forwarding.
8.1. HELLO and TC Message Generation 8.1. HELLO and TC Message Generation
HELLO messages are generated according to Section 15.1 of [RFC7181], HELLO messages are generated according to Section 15.1 of [RFC7181],
plus a single message TLV with Type := SOURCE_ROUTE included. plus a single message TLV with Type := SOURCE_ROUTE included.
TC messages are generated according to Section 16.1 of [RFC7181] plus TC messages are generated according to Section 16.1 of [RFC7181],
a single message TLV with Type := SOURCE_ROUTE included. plus a single message TLV with Type := SOURCE_ROUTE included.
For the routers that do not generate TC messages according to For the routers that do not generate TC messages according to
[RFC7181], at least one TC message MUST be generated by an MP-OLSRv2 [RFC7181], at least one TC message MUST be generated by an MP-OLSRv2
Routing Process during the SR_TC_INTERVAL (Section 5), which MUST be Routing Process during the SR_TC_INTERVAL (Section 5), which MUST be
greater than or equal to TC_INTERVAL. Those TC messages MUST NOT greater than or equal to TC_INTERVAL. Those TC messages MUST NOT
carry any advertised neighbor addresses. This serves for those carry any advertised neighbor addresses. This serves for those
routers to advertise the SOURCE_ROUTE TLV so that the other routers routers to advertise the SOURCE_ROUTE TLV so that the other routers
can be aware of the source-route enabled routers so as to be used as can be aware of the routers that are source-route enabled so as to be
destinations of multipath routing. The validity time associated with used as destinations of multipath routing. The validity time
the VALIDITY_TIME TLV in such TC messages equals SR_HOLD_TIME, which associated with the VALIDITY_TIME TLV in such TC messages equals
MUST be greater than the SR_TC_INTERVAL. If the TC message carries SR_HOLD_TIME, which MUST be greater than the SR_TC_INTERVAL. If the
an optional INTERVAL_TIME TLV, it MUST have a value encoding the TC message carries an optional INTERVAL_TIME TLV, it MUST have a
SR_TC_INTERVAL. value encoding the SR_TC_INTERVAL.
8.2. HELLO and TC Message Processing 8.2. HELLO and TC Message Processing
HELLO and TC messages are processed according to section 15.3 and HELLO and TC messages are processed according to Sections 15.3 and
16.3 of [RFC7181]. 16.3 of [RFC7181].
In addition to the reasons specified in [RFC7181] for discarding a In addition to the reasons specified in [RFC7181] for discarding a
HELLO message or a TC message on reception, a HELLO or TC message HELLO message or a TC message on reception, a HELLO or TC message
received MUST be discarded if it has more than one Message TLV with received MUST be discarded if it has more than one Message TLV with
Type = SOURCE_ROUTE. Type = SOURCE_ROUTE.
For every HELLO or TC message received, if there is a Message TLV For every HELLO or TC message received, if there is a Message TLV
with Type := SOURCE_ROUTE, create or update (if the Tuple exists with Type := SOURCE_ROUTE, create or update (if the Tuple exists
already) the SR-OLSR Router Tuple with already) the SR-OLSR Routing Tuple with:
o SR_addr := originator address of the HELLO or TC message o SR_addr := originator address of the HELLO or TC message
o SR_time := current_time + validity time of the TC or HELLO message o SR_time := current_time + validity time of the TC or HELLO message
defined in [RFC7181]. defined in [RFC7181].
8.3. MPR Selection 8.3. MPR Selection
Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs
following Section 18 of [RFC7181]. In a mixed network with OLSRv2- following Section 18 of [RFC7181]. In a mixed network with
only routers, the following considerations apply when calculating OLSRv2-only routers, the following considerations apply when
MPRs: calculating MPRs:
o MP-OLSRv2 routers SHOULD be preferred as routing MPRs to increase o MP-OLSRv2 routers SHOULD be preferred as routing MPRs to increase
the possibility of finding disjoint paths using MP-OLSRv2 routers. the possibility of finding disjoint paths using MP-OLSRv2 routers.
o The number of routing MPRs that run MP-OLSRv2 Routing Process MUST o The number of routing MPRs that run the MP-OLSRv2 Routing Process
be equal or greater than NUMBER_OF_PATHS if there are enough MP- MUST be equal to or greater than NUMBER_OF_PATHS if there are
OLSRv2 symmetric neighbors. Otherwise all the MP-OLSRv2 routers enough MP-OLSRv2 symmetric neighbors. Otherwise, all the
are selected as routing MPRs, expect the routers with willingness MP-OLSRv2 routers are selected as routing MPRs, except the routers
WILL_NEVER. with willingness WILL_NEVER.
8.4. Datagram Processing at the MP-OLSRv2 Originator 8.4. Datagram Processing at the MP-OLSRv2 Originator
If datagrams without source routing header need to be forwarded using If datagrams without a source routing header need to be forwarded
multiple paths (for example, based on the information of a DiffServ using multiple paths (for example, based on the information of a
codepoint [RFC2474]), the MP-OLSRv2 Routing Process will try to find Diffserv codepoint [RFC2474]), the MP-OLSRv2 Routing Process will try
the Multipath Routing Tuple where: to find the Multipath Routing Tuple where:
o MR_dest_addr = destination of the datagram o MR_dest_addr = destination of the datagram
If no matching Multipath Routing Tuple is found and the Multipath If no matching Multipath Routing Tuple is found and the Multipath
Routing Set is maintained proactively, it indicates that there is no Routing Set is maintained proactively, it indicates that there is no
multipath route available to the desired destination. The datagram multipath route available to the desired destination. The datagram
is forwarded following the OLSRv2 Routing Process. is forwarded following the OLSRv2 Routing Process.
If no matching Multipath Routing Tuple is found and the Multipath If no matching Multipath Routing Tuple is found and the Multipath
Routing Set is maintained reactively, the multipath algorithm defined Routing Set is maintained reactively, the multipath algorithm defined
in Section 8.5 is invoked, to calculate the Multipath Routing Tuple in Section 8.5 is invoked to calculate the Multipath Routing Tuple to
to the destination. If the calculation does not return any Multipath the destination. If the calculation does not return any Multipath
Routing Tuple, the following steps are aborted and the datagram is Routing Tuple, the following steps are aborted and the datagram is
forwarded following the OLSRv2 Routing Process. forwarded following the OLSRv2 Routing Process.
If a matching Multipath Routing Tuple is obtained, the Path Tuples of If a matching Multipath Routing Tuple is obtained, the Path Tuples of
the Multipath Routing Tuple are applied to the datagrams using either the Multipath Routing Tuple are applied to the datagrams using either
per-flow scheduling or per-datagram scheduling, depending on the per-flow or per-datagram scheduling, depending on the transport layer
transport layer protocol and the application used. By default, per- protocol and the application used. By default, per-flow scheduling
flow scheduling is used, especially for the transport protocols that is used, especially for the transport protocols that are sensitive to
are sensitive to reordering, such as TCP. The path selection reordering, such as TCP. The path-selection decision is made on the
decision is made on the first datagram and all subsequent datagrams first datagram and all subsequent datagrams of the same flow use the
of the same flow use the same path. If the path is detected broken same path. If the path breaks before the flow is closed, another
before the flow is closed, another path with the most similar metric path with the most similar metric is used. Per-datagram scheduling
is used. Per-datagram scheduling is recommended if the traffic is is recommended if the traffic is insensitive to reordering such as
insensitive to reordering such as non-reliable transmission of media unreliable transmission of media traffic or when erasure coding is
traffic, or when erasure coding is applied. In such case, each applied. In such a case, each datagram selects its paths
datagram selects its paths independently. independently.
By default, the traffic load should be equally distributed in By default, the traffic load should be equally distributed in
multiple paths. Other path scheduling mechanisms (e.g., assigning multiple paths. Other path-scheduling mechanisms (e.g., assigning
more traffic over better paths) are also possible and will not impact more traffic over better paths) are also possible and will not impact
the interoperability of different implementations. the interoperability of different implementations.
The addresses in PT_address[1, ..., n-1] of the chosen Path Tuple are The addresses in PT_address[1, ..., n-1] of the chosen Path Tuple are
thus added to the datagram header as the source routing header. For thus added to the datagram header as the source routing header. For
IPv6 networks, strict source routing is used, thus all the IPv6 networks, strict source routing is used; thus, all the
intermediate routers in the path are stored in the source routing intermediate routers in the path are stored in the source routing
header following the format defined in section 3 of [RFC6554] with header following the format defined in Section 3 of [RFC6554] with
Routing Type set to 3. the Routing Type set to 3.
For IPv4 networks, loose source routing is used, with the following For IPv4 networks, loose source routing is used with the following
rules: rules:
o Only the addresses that exist in SR-OLSR Router Set can be added o Only the addresses that exist in the SR-OLSR Router Set can be
to the source routing header. added to the source routing header.
o If the length of the path (n) is greater than MAX_SRC_HOPS o If the length of the path (n) is greater than MAX_SRC_HOPS
(Section 5) or adding the whole path information exceeds the MTU, (Section 5) or if adding the whole path information exceeds the
only the "key" routers in the path are kept. By default, the key MTU, only the "key" routers in the path are kept. By default, the
routers are uniformly chosen in the path. If further information key routers are uniformly chosen in the path. If further
such as capacity of the routers (e.g., battery life) or the information, such as the capacity of the routers (e.g., battery
routers' willingness in forwarding data is available, the routers life) or the routers' willingness in forwarding data, is
with higher capacity and willingness are preferred. available, the routers with higher capacity and 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.
It is not recommended to fragment the IP packet if the packet with It is not recommended to fragment the IP packet if the packet with
the source routing header would exceed the minimum MTU along the the source routing header would exceed the minimum MTU along the
path. Depending on the size of the routing domain, the MTU should be path. Depending on the size of the routing domain, the MTU should be
at least 1280 + 40 (for the outer IP header) + 16 * diameter of the at least 1280 + 40 (for the outer IP header) + 16 * diameter of the
network in number of hops (for the source routing header). If the network in number of hops (for the source routing header). If the
links in the network have different MTU sizes, by using technologies links in the network have different MTU sizes, by using technologies
like Path MTU Discovery, the routers are able to be aware of the MTU like Path MTU Discovery, the routers are able to be aware of the MTU
along the path. The size of the datagram plus the size of IP headers along the path. The size of the datagram plus the size of IP headers
(including the source routing header) should not exceed the minimum (including the source routing header) should not exceed the minimum
MTU along the path, otherwise, the source routing should not be used. MTU along the path; otherwise, the source routing should not be used.
If the destination of the datagrams is out the MP-OLSRv2 routing If the destination of the datagrams is out of the MP-OLSRv2 routing
domain, the datagram must be source routed to the gateway between the domain, the datagram must be source routed to the gateway between the
MP-OLSRv2 routing domain and the rest of the Internet. The gateway MP-OLSRv2 routing domain and the rest of the Internet. The gateway
MUST remove the source routing header before forwarding the datagram MUST remove the source routing header before forwarding the datagram
to the rest of the Internet. to the rest of the Internet.
8.5. Multipath Calculation 8.5. Multipath Calculation
8.5.1. Requirements of Multipath Calculation 8.5.1. Requirements of Multipath Calculation
The Multipath Routing Set maintains the information of multiple paths The Multipath Routing Set maintains the information of multiple paths
skipping to change at page 14, line 43 skipping to change at page 16, line 7
(Section 7.2) are generated based on a multipath algorithm. (Section 7.2) are generated based on a multipath algorithm.
For each path to a destination, the algorithm must provide: For each path to a destination, the algorithm must provide:
o The metric of the path to the destination, o The metric of the path to the destination,
o The list of intermediate routers on the path. o The list of intermediate routers on the path.
For IPv6 networks, as strict source routing is used, only the routers For IPv6 networks, as strict source routing is used, only the routers
that exist in the SR-OLSRv2 Router Set are considered in the path that exist in the SR-OLSRv2 Router Set are considered in the path
calculation, i.e., only the source-routing supported routers can calculation, i.e., only the source-routing-supported routers can
exist in the path. exist in the path.
After the calculation of multiple paths, the metric of paths (denoted After the calculation of multiple paths, the metric of paths (denoted
c_i for path i) to the destination is compared to the R_metric of the c_i for path i) to the destination is compared to the R_metric of the
the OLSRv2 Routing Tuple ([RFC7181]) to the same destination. If the OLSRv2 Routing Tuple ([RFC7181]) to the same destination. If the
metric c_i is greater than R_metric * CUTOFF_RATIO (Section 5), the metric c_i is greater than R_metric * CUTOFF_RATIO (Section 5), the
corresponding path i SHOULD NOT be used. If less than 2 paths are corresponding path i SHOULD NOT be used. If less than two paths are
found with metrics less than R_metric * CUTOFF_RATIO, the router found with metrics less than R_metric * CUTOFF_RATIO, the router
SHOULD fall back to OLSRv2 Routing Process without using multipath SHOULD fall back to OLSRv2 Routing Process without using multipath
routing. This can happen if there are too many OLSRv2-only routers routing. This can happen if there are too many OLSRv2-only routers
in the network, and requiring multipath routing may result in in the network, and requiring multipath routing may result in
inferior paths. inferior paths.
By invoking the multipath algorithm, up to NUMBER_OF_PATHS paths are By invoking the multipath algorithm, up to NUMBER_OF_PATHS paths are
obtained and added to the Multipath Routing Set by creating a obtained and added to the Multipath Routing Set by creating a
Multipath Routing Tuple with: Multipath Routing Tuple with:
o MR_dest_addr := destination of the datagram o MR_dest_addr := destination of the datagram.
o An MP_path_set with calculated Path Tuples. Each Path Tuple o An MP_path_set with calculated Path Tuples. Each Path Tuple
corresponds to a path obtained in the Multipath Dijkstra corresponds to a path obtained in the Multipath Dijkstra
algorithm, with PT_metric := metric of the calculated path and Algorithm, with PT_metric := metric of the calculated path and
PT_address[1, ..., n-1] := list of intermediate routers. PT_address[1, ..., n-1] := list of intermediate routers.
8.5.2. Multipath Dijkstra Algorithm 8.5.2. Multipath Dijkstra Algorithm
This section introduces the Multipath Dijkstra Algorithm as a default This section introduces the Multipath Dijkstra Algorithm as a default
algorithm. It tries to obtain disjoint paths when appropriate, but algorithm. It tries to obtain disjoint paths when appropriate, but
does not guarantee strict disjoint paths. The use of other it does not guarantee strict disjoint paths. The use of other
algorithms is not prohibited, as long as the requirements described algorithms is not prohibited, as long as the requirements described
in Section 8.5.1 are met. Using different multipath algorithms will in Section 8.5.1 are met. Using different multipath algorithms will
not impact the interoperability. not impact the interoperability.
The general principle of the Multipath Dijkstra Algorithm [ADHOC11] The general principle of the Multipath Dijkstra Algorithm [ADHOC11]
is using Dijkstra algorithm for multiple iterations, and at iteration is to use the Dijkstra Algorithm for multiple iterations and to look
i to look for the shortest path P[i] to the destination d. After for the shortest path P[i] to the destination d at iteration i.
each iteration, the metric of used links is increased. Compared to After each iteration, the metric of used links is increased.
the original Dijkstra's algorithm, the main modification consists in Compared to the original Dijkstra's algorithm, the main modification
adding two incremental functions named metric functions fp and fe in consists in adding two incremental functions, named metric functions
order to prevent the next steps resulting in similar paths: fp and fe, in order to prevent the next steps resulting in similar
paths:
o fp(c) is used to increase metrics of arcs belonging to the o fp(c) is used to increase metrics of arcs belonging to the
previous path P[i-1] (with i>1), where c is the value of the previous path P[i-1] (with i>1), where c is the value of the
previous metric. This encourages future paths to use different previous metric. This encourages future paths to use different
arcs but not different vertices. arcs but not different vertices.
o fe(c) is used to increase metrics of the arcs that lead to o fe(c) is used to increase metrics of the arcs that lead to
intermediate vertices of the previous path P[i-1] (with i>1), intermediate vertices of the previous path P[i-1] (with i>1),
where c is the value of the previous metric. The "lead to" means where c is the value of the previous metric. The "lead to" means
that only one vertex of the arc belongs to the previous path that only one vertex of the arc belongs to the previous path
P[i-1], while the other vertex does not. The "intermediate" means P[i-1] while the other vertex does not. The "intermediate" means
that the source and destination vertices are not considered. that the source and destination vertices are not considered.
Considering the simple example in Figure 1: a path P[i] S--A--D is Consider the simple example in Figure 1: a path P[i] S--A--D is
obtained at step i. For the next step, the metric of link S--A and obtained at step i. For the next step, the metric of link S--A and
A--D are to be increased using fp(c), because they belong to the path A--D are to be increased using fp(c) because they belong to the path
P[i]. A--B is to be increased using fe(c), because A is an P[i]. A--B is to be increased using fe(c) because A is an
intermediate vertex of path P[i], and B is not part of P[i]. B--D is intermediate vertex of path P[i], and B is not part of P[i]. B--D is
unchanged. unchanged.
B B
/ \ / \
/ \ / \
/ \ / \
S---------A-----------D S---------A-----------D
Figure 1 Figure 1
It is possible to choose different fp and fe to get link-disjoint It is possible to choose a different fp and fe to get link-disjoint
paths or node-disjoint paths as desired. A recommendation for paths or node-disjoint paths as desired. A recommendation for
configuration of fp and fe is given in Section 9. configuration of fp and fe is given in Section 9.
To get NUMBER_OF_PATHS different paths, for each path P[i] (i = 1, To get NUMBER_OF_PATHS different paths, for each path
..., NUMBER_OF_PATHS) do: P[i] (i = 1, ..., NUMBER_OF_PATHS):
1. Run Dijkstra's algorithm to get the shortest path P[i] for the 1. Run Dijkstra's algorithm to get the shortest path P[i] for the
destination d. destination d.
2. Apply metric function fp to the metric of links (in both 2. Apply metric function fp to the metric of links (in both
directions) in P[i]. directions) in P[i].
3. Apply metric function fe to the metric of links (in both 3. Apply metric function fe to the metric of links (in both
directions) that lead to routers used in P[i]. directions) that lead to routers used in P[i].
A simple example of the Multipath Dijkstra Algorithm is illustrated A simple example of the Multipath Dijkstra Algorithm is illustrated
in Appendix A. in Appendix A.
8.6. Multipath Routing Set Updates 8.6. Multipath Routing Set Updates
The Multipath Routing Set MUST be updated when the Local Information The Multipath Routing Set MUST be updated when the Local Information
Base, the Neighborhood Information Base, or the Topology Information Base, the Neighborhood Information Base, or the Topology Information
Base indicate a change (including of any potentially used outgoing Base indicate a change (including a change of any potentially used
neighbor metric values) of the known symmetric links and/or attached outgoing neighbor metric values) of the known symmetric links and/or
networks in the MANET, hence changing the Topology Graph, as attached networks in the MANET, hence, changing the Topology Graph as
described in section 17.7 of [RFC7181]. How the Multipath Routing described in Section 17.7 of [RFC7181]. How the Multipath Routing
Set is updated depends on whether the set is maintained reactively or Set is updated depends on whether the set is maintained reactively or
proactively: proactively:
o In reactive mode, all the Tuples in the Multipath Routing Set are o In reactive mode, all the Tuples in the Multipath Routing Set are
removed. The new arriving datagrams will be processed as removed. The new arriving datagrams will be processed as
specified in Section 8.4; specified in Section 8.4.
o In proactive mode, the route to all the destinations are updated o In proactive mode, the routes to all the destinations are updated
according to Section 8.5. according to Section 8.5.
8.7. Datagram Forwarding 8.7. Datagram Forwarding
In IPv4 networks, datagrams are forwarded using loose source routing In IPv4 networks, datagrams are forwarded using loose source routing
as specified in Section 3.1 of [RFC0791]. as specified in Section 3.1 of [RFC791].
In IPv6 networks, datagrams are forwarded using strict source routing In IPv6 networks, datagrams are forwarded using strict source routing
as specified in Section 4.2 of [RFC6554], except the applied routers as specified in Section 4.2 of [RFC6554], except the applied routers
are MP-OLSRv2 routers rather than RPL routers. The last hop of the are MP-OLSRv2 routers rather than RPL routers. The last hop of the
source route MUST remove the source routing header. source route MUST remove the source routing header.
9. Configuration Parameters 9. Configuration Parameters
This section gives default values and guidelines for setting This section gives default values and guidelines for setting
parameters defined in Section 5. Network administrators may wish to parameters defined in Section 5. Network administrators may wish to
change certain or all the parameters for different network scenarios. change certain or all the parameters for different network scenarios.
As an experimental protocol, the users of this protocol are also As an experimental protocol, the users of this protocol are also
encouraged to explore different parameter setting in various network encouraged to explore different parameter settings in various network
environments, and provide feedback. environments and provide feedback.
o NUMBER_OF_PATHS := 3. This parameter defines the number of o NUMBER_OF_PATHS := 3. This parameter defines the number of
parallel paths used in datagram forwarding. Setting it to one parallel paths used in datagram forwarding. Setting it to 1 makes
makes the specification identical to OLSRv2. Setting it to too the specification identical to OLSRv2. Setting it to too large of
large values may lead to unnecessary computational overhead and a value may lead to unnecessary computational overhead and
inferior paths. inferior paths.
o MAX_SRC_HOPS := 10, for IPv4 networks. For IPv6 networks, it MUST o MAX_SRC_HOPS := 10, for IPv4 networks. For IPv6 networks, it MUST
be set to 0, i.e., no constraint on maximum number of hops. be set to 0, i.e., no constraint on the maximum number of hops.
o CUTOFF_RATIO := 1.5. It MUST be greater or equal than 1. o CUTOFF_RATIO := 1.5. It MUST be greater than or equal to 1.
o SR_TC_INTERVAL := 10 x TC_INTERVAL. It MUST be greater than or o SR_TC_INTERVAL := 10 x TC_INTERVAL. It MUST be greater than or
equal to TC_INTERVAL. It SHOULD be significantly greater than equal to TC_INTERVAL. It SHOULD be significantly greater than
TC_INTERVAL to reduce unnecessary TC message generations. TC_INTERVAL to reduce unnecessary TC message generations.
o SR_HOLD_TIME := 3 x SR_TC_INTERVAL. It MUST be greater than o SR_HOLD_TIME := 3 x SR_TC_INTERVAL. It MUST be greater than
SR_TC_INTERVAL and SHOULD allow for a small number of lost SR_TC_INTERVAL and SHOULD allow for a small number of lost
messages. messages.
If Multipath Dijkstra Algorithm is applied: If the Multipath Dijkstra Algorithm is applied:
o fp(c) := 4*c, where c is the original metric of the link. o fp(c) := 4*c, where c is the original metric of the link.
o fe(c) := 2*c, where c is the original metric of the link. o fe(c) := 2*c, where c is the original metric of the link.
The setting of metric functions fp and fc defines the preference of The setting of metric functions fp and fc defines the preference of
obtained multiple disjoint paths. If id is the identity function, obtained multiple disjoint paths. If id is the identity function,
i.e., fp(c)=c, 3 cases are possible: i.e., fp(c)=c, three cases are possible:
o if id=fe<fp: only increase the metric of related links; o if id=fe<fp, only increase the metric of related links;
o if id<fe=fp: apply equal increase to the metric of related nodes o if id<fe=fp, apply equal increase to the metric of related nodes
and links; and links;
o if id<fe<fp: apply greater increase to the metric of related o if id<fe<fp, apply greater increase to the metric of related
links. links.
Increasing the metric of related links or nodes means avoiding the Increasing the metric of related links or nodes means avoiding the
use of such links or nodes in the next path to be calculated. use of such links or nodes in the next path to be calculated.
10. Implementation Status 10. Security Considerations
The RFC Editor is advised to remove the entire section before
publication, as well as the reference to RFC 7942.
This section records the status of known implementations of the
protocol defined by this specification at the time of posting of this
Internet-Draft, and based on a proposal described in [RFC7942]. The
description of implementations in this section is intended to assist
the IETF in its decision processes in progressing drafts to RFCs.
Please note that the listing of any individual implementation here
does not imply endorsement by the IETF. Furthermore, no effort has
been spent to verify the information presented here that was supplied
by IETF contributors. This is not intended as, and must not be
construed to be, a catalog of available implementations or their
features. Readers are advised to note that other implementations may
exist.
According to [RFC7942], "this will allow reviewers and working groups
to assign due consideration to documents that have the benefit of
running code, which may serve as evidence of valuable experimentation
and feedback that have made the implemented protocols more mature.
It is up to the individual working groups to use this information as
they see fit".
Until April 2015, there are 3 open source implementations of the
protocol specified in this document, for both testbed and simulation
use.
10.1. Multipath extension based on nOLSRv2
The implementation is conducted by University of Nantes, France, and
is based on Niigata University's nOLSRv2 implementation. It is an
open source implementation. The code is available at
https://github.com/yijiazi/mpolsr_qualnet and
http://jiaziyi.com/index.php/research-projects/mp-olsr .
It can be used for Qualnet simulations, and be exported to run in a
testbed. All the specification is implemented in this
implementation.
Implementation experience and test data can be found at [ADHOC11].
10.2. Multipath extension based on olsrd
The implementation is conducted under SEREADMO (Securite des Reseaux
Ad Hoc & Mojette) project, and supported by French research agency
(RNRT2803). It is based on olsrd (http://www.olsr.org/)
implementation, and is open sourced. The code is available at
https://github.com/yijiazi/mpolsr_testbed and
http://jiaziyi.com/index.php/research-projects/sereadmo .
The implementation is for testing the specification in the field.
All the specification is implemented in this implementation.
Implementation experience and test data can be found at [ADHOC11] and
[GIIS14].
10.3. Multipath extension based on umOLSR
The implementation is conducted by University of Nantes, France, and
is based on um-olsr implementation
(http://masimum.inf.um.es/fjrm/development/um-olsr/). The code is
available at https://github.com/yijiazi/mpolsr_ns2 and
http://jiaziyi.com/index.php/research-projects/mp-olsr under GNU GPL
license.
The implementation is for network simulation for NS2 network
simulator. All the specification is implemented in this
implementation.
Implementation experience and test data can be found at [WCNC08].
11. Security Considerations
As an extension of [RFC7181], the security considerations and As an extension of [RFC7181], the security considerations and
security architecture illustrated in [RFC7181] are applicable to this security architecture illustrated in [RFC7181] are applicable to this
MP-OLSRv2 specification. The implementations without security MP-OLSRv2 specification. The implementations without security
mechanisms are vulnerable to threats discussed in mechanisms are vulnerable to threats discussed in [RFC8116].
[I-D.ietf-manet-olsrv2-sec-threats].
In a mixed network with OLSRv2-only routers, a compromised router can In a mixed network with OLSRv2-only routers, a compromised router can
add SOURCE_ROUTE TLVs in its TC and HELLO messages, which will make add SOURCE_ROUTE TLVs in its TC and HELLO messages, which will make
other MP-OLSRv2 Routing Processes believe that it supports source other MP-OLSRv2 Routing Processes believe that it supports source
routing. This will increase the possibility of being chosen as MPRs routing. This will increase the possibility of being chosen as MPRs
and put into the source routing header. The former will make it and put into the source routing header. The former will make it
possible to manipulate the flooding of TC messages and the latter possible to manipulate the flooding of TC messages and the latter
will make the datagram pass through the compromised router. will make the datagram pass through the compromised router.
As with [RFC7181], a conformant implementation of MP-OLSRv2 MUST, at As with [RFC7181], a conformant implementation of MP-OLSRv2 MUST, at
minimum, implement the security mechanisms specified in [RFC7183] to minimum, implement the security mechanisms specified in [RFC7183] to
provide integrity and replay protection of routing control messages. provide integrity and replay protection of routing control messages.
The MP-OLSRv2 Routing Process MUST drop datagrams entering or exiting The MP-OLSRv2 Routing Process MUST drop datagrams entering or exiting
a OLSRv2/MP-OLSRv2 routing domain that contain a source routing an OLSRv2/MP-OLSRv2 routing domain that contain a source routing
header. Compared to OLSRv2, the use of the source routing header in header. Compared to OLSRv2, the use of the source routing header in
this specification introduces vulnerabilities related to source this specification introduces vulnerabilities related to source
routing attacks, which include bypassing filtering devices, bandwidth routing attacks, which include bypassing filtering devices, bandwidth
exhaustion of certain routers, etc. Those attacks are discussed in exhaustion of certain routers, etc. Those attacks are discussed in
Section 5 of [RFC6554] and [RFC5095]. The influence is limited to Section 5 of [RFC6554] and [RFC5095]. The influence is limited to
the OLSRv2/MP-OLSRv2 routing domain, because the source routing the OLSRv2/MP-OLSRv2 routing domain because the source routing header
header is used only in the current routing domain. is used only in the current routing domain.
If the multiple paths are calculated reactively, the datagrams SHOULD If the multiple paths are calculated reactively, the datagrams SHOULD
be buffered while the paths are being calculated. Because the path be buffered while the paths are being calculated. Because the path
calculation is local and no control message is exchanged, the calculation is local and no control message is exchanged, the
buffering time should be trivial. However, depending on the CPU buffering time should be trivial. However, depending on the CPU
power and memory of the router, a maximum buffer size SHOULD be set power and memory of the router, a maximum buffer size SHOULD be set
to avoid occupying too much memory of the router. When the buffer is to avoid occupying too much memory of the router. When the buffer is
full, the oldest datagrams are dropped. A possible attack that a full, the oldest datagrams are dropped. A possible attack that a
malicious application could launch is that it initiates a large malicious application could launch would be one in which it initiates
amount of datagrams to all the other routers in the network, thus a large amount of datagrams to all the other routers in the network,
triggering path calculation to all the other routers and during which thus triggering path calculation to all the other routers and during
the datagrams are buffered. This might flush other legitimate which the datagrams are buffered. This might flush other legitimate
datagrams. But the impact of the attack is transient: once the path datagrams. But the impact of the attack is transient: once the path
calculation is finished, the datagrams are forwarded and the buffer calculation is finished, the datagrams are forwarded and the buffer
goes back to empty. goes back to empty.
12. IANA Considerations 11. IANA Considerations
This section adds one new Message TLV, allocated as a new Type This section adds one new Message TLV, allocated as a new Type
Extension to an existing Message TLV. Extension to an existing Message TLV.
12.1. Message TLV Types 11.1. Message TLV Types
This specification updates the IANA registry "Message TLV Types" -- This specification updates the "Type 7 Message TLV Type Extensions"
Message Type 7 by adding the new Type Extension SOURCE_ROUTE, as registry [RFC7181] by adding the new Type Extension SOURCE_ROUTE, as
illustrated in Table 1. illustrated in Table 1.
+-----------+--------------+------------------------+---------------+ +-----------+--------------+------------------------+---------------+
| Type | Name | Description | Reference | | Type | Name | Description | Reference |
| Extension | | | | | Extension | | | |
+-----------+--------------+------------------------+---------------+ +-----------+--------------+------------------------+---------------+
| TBD | SOURCE_ROUTE | Indicates that the | This | | 2 | SOURCE_ROUTE | Indicates that the | This |
| | | originator of the | specification | | | | originator of the | specification |
| | | message supports | | | | | message supports | |
| | | source route | | | | | source-route | |
| | | forwarding. No value. | | | | | forwarding. No value. | |
+-----------+--------------+------------------------+---------------+ +-----------+--------------+------------------------+---------------+
Table 1: SOURCE_ROUTE type for RFC 5444 Type 7 Message TLV Type Table 1: SOURCE_ROUTE Type for Type 7 Message TLV Type Extensions
Extensions
13. Acknowledgments
The authors would like to thank Sylvain David, Asmaa Adnane, Eddy
Cizeron, Salima Hamma, Pascal Lesage and Xavier Lecourtier for their
efforts in developing, implementing and testing the specification.
The authors also appreciate valuable discussions with Thomas Clausen,
Ulrich Herberg, Justin Dean, Geoff Ladwig, Henning Rogge , Marcus
Barkowsky and especially Christopher Dearlove for his multiple rounds
of reviews during the working group last calls.
14. References 12. References
14.1. Normative References 12.1. Normative References
[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791,
DOI 10.17487/RFC0791, September 1981, DOI 10.17487/RFC0791, September 1981,
<http://www.rfc-editor.org/info/rfc791>. <https://www.rfc-editor.org/info/rfc791>.
[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, DOI 10.17487/ Requirement Levels", BCP 14, RFC 2119,
RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message "Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, DOI 10.17487/RFC5444, February 2009, Format", RFC 5444, DOI 10.17487/RFC5444, February 2009,
<http://www.rfc-editor.org/info/rfc5444>. <https://www.rfc-editor.org/info/rfc5444>.
[RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc
Network (MANET) Neighborhood Discovery Protocol (NHDP)", Network (MANET) Neighborhood Discovery Protocol (NHDP)",
RFC 6130, DOI 10.17487/RFC6130, April 2011, RFC 6130, DOI 10.17487/RFC6130, April 2011,
<http://www.rfc-editor.org/info/rfc6130>. <https://www.rfc-editor.org/info/rfc6130>.
[RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6
Routing Header for Source Routes with the Routing Protocol Routing Header for Source Routes with the Routing Protocol
for Low-Power and Lossy Networks (RPL)", RFC 6554, for Low-Power and Lossy Networks (RPL)", RFC 6554,
DOI 10.17487/RFC6554, March 2012, DOI 10.17487/RFC6554, March 2012,
<http://www.rfc-editor.org/info/rfc6554>. <https://www.rfc-editor.org/info/rfc6554>.
[RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg,
"The Optimized Link State Routing Protocol Version 2", "The Optimized Link State Routing Protocol Version 2",
RFC 7181, DOI 10.17487/RFC7181, April 2014, RFC 7181, DOI 10.17487/RFC7181, April 2014,
<http://www.rfc-editor.org/info/rfc7181>. <https://www.rfc-editor.org/info/rfc7181>.
[RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity [RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity
Protection for the Neighborhood Discovery Protocol (NHDP) Protection for the Neighborhood Discovery Protocol (NHDP)
and Optimized Link State Routing Protocol Version 2 and Optimized Link State Routing Protocol Version 2
(OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014, (OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014,
<http://www.rfc-editor.org/info/rfc7183>. <https://www.rfc-editor.org/info/rfc7183>.
14.2. Informative References [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[ADHOC11] Yi, J., Adnane, A-H., David, S., and B. Parrein, 12.2. Informative References
"Multipath optimized link state routing for mobile ad hoc
networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, [ADHOC11] Yi, J., Adnane, A., David, S., and B. Parrein, "Multipath
January, 2011. optimized link state routing for mobile ad hoc networks",
Elsevier Ad Hoc Networks, Volume 9, Number 1, pp 28-47,
DOI 10.1016/j.adhoc.2010.04.007, January 2011.
[GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria, [GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria,
"Experimental performance comparison of single-path and "Experimental performance comparison of single-path and
multipath routing in VANETs", In Global Information multipath routing in VANETs", In the Global Information
Infrastructure and Networking Symposium (GIIS), 2014 , Infrastructure and Networking Symposium (GIIS), Volume 1,
vol. 1, no. 6, pp. 15-19, 2014. Number 6, pp 15-19, DOI 10.1109/GIIS.2014.6934283,
September 2014.
[I-D.ietf-6man-segment-routing-header]
Previdi, S., Filsfils, C., Raza, K., Leddy, J., Field, B.,
daniel.voyer@bell.ca, d., daniel.bernier@bell.ca, d.,
Matsushima, S., Leung, I., Linkova, J., Aries, E., Kosugi,
T., Vyncke, E., Lebrun, D., Steinberg, D., and R. Raszuk,
"IPv6 Segment Routing Header (SRH)",
draft-ietf-6man-segment-routing-header-06 (work in
progress), March 2017.
[I-D.ietf-manet-olsrv2-sec-threats]
Clausen, T., Herberg, U., and J. Yi, "Security Threats to
the Optimized Link State Routing Protocol version 2
(OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-04 (work in
progress), January 2017.
[RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 [IPv6-SRH] Previdi, S., Ed., Filsfils, C., Raza, K., Leddy, J.,
(IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460, Field, B., Voyer, D., Bernier, S., Matsushima, S., Leung,
December 1998, <http://www.rfc-editor.org/info/rfc2460>. I., Linkova, J., Aries, E., Kosugi, T., Vyncke, E.,
Lebrun, D., Steinberg, D., and R. Raszuk, "IPv6 Segment
Routing Header (SRH)", Work in Progress,
draft-ietf-6man-segment-routing-header-07, July 2017.
[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,
DOI 10.17487/RFC2474, December 1998, DOI 10.17487/RFC2474, December 1998,
<http://www.rfc-editor.org/info/rfc2474>. <https://www.rfc-editor.org/info/rfc2474>.
[RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking
(MANET): Routing Protocol Performance Issues and (MANET): Routing Protocol Performance Issues and
Evaluation Considerations", RFC 2501, DOI 10.17487/ Evaluation Considerations", RFC 2501,
RFC2501, January 1999, DOI 10.17487/RFC2501, January 1999,
<http://www.rfc-editor.org/info/rfc2501>. <https://www.rfc-editor.org/info/rfc2501>.
[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, DOI 10.17487/ Multicast Next-Hop Selection", RFC 2991,
RFC2991, November 2000, DOI 10.17487/RFC2991, November 2000,
<http://www.rfc-editor.org/info/rfc2991>. <https://www.rfc-editor.org/info/rfc2991>.
[RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation [RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation
of Type 0 Routing Headers in IPv6", RFC 5095, of Type 0 Routing Headers in IPv6", RFC 5095,
DOI 10.17487/RFC5095, December 2007, DOI 10.17487/RFC5095, December 2007,
<http://www.rfc-editor.org/info/rfc5095>. <https://www.rfc-editor.org/info/rfc5095>.
[RFC7722] Dearlove, C. and T. Clausen, "Multi-Topology Extension for [RFC7722] 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)", RFC 7722, DOI 10.17487/RFC7722, December 2015, (OLSRv2)", RFC 7722, DOI 10.17487/RFC7722, December 2015,
<http://www.rfc-editor.org/info/rfc7722>. <https://www.rfc-editor.org/info/rfc7722>.
[RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric [RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric
Based on Packet Sequence Numbers for Optimized Link State Based on Packet Sequence Numbers for Optimized Link State
Routing Version 2 (OLSRv2)", RFC 7779, DOI 10.17487/ Routing Version 2 (OLSRv2)", RFC 7779,
RFC7779, April 2016, DOI 10.17487/RFC7779, April 2016,
<http://www.rfc-editor.org/info/rfc7779>. <https://www.rfc-editor.org/info/rfc7779>.
[RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running [RFC8116] Clausen, T., Herberg, U., and J. Yi, "Security Threats to
Code: The Implementation Status Section", BCP 205, the Optimized Link State Routing Protocol Version 2
RFC 7942, DOI 10.17487/RFC7942, July 2016, (OLSRv2)", RFC 8116, DOI 10.17487/RFC8116, May 2017,
<http://www.rfc-editor.org/info/rfc7942>. <https://www.rfc-editor.org/info/rfc8116>.
[RFC8200] Deering, S. and R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", STD 86, RFC 8200,
DOI 10.17487/RFC8200, July 2017,
<https://www.rfc-editor.org/info/rfc8200>.
[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 Proceedings of the IEEE Wireless
Communications and Networking Conference, 2008. Communications and Networking Conference (WCNC),
DOI 10.1109/WCNC.2008.395, 2008.
[WPMC11] Yi, J., Parrein, B., and D. Radu, "Multipath routing [WPMC11] Yi, J., Parrein, B., and D. Radu, "Multipath Routing
protocol for manet: Application to H.264/SVC video content Protocol for MANET: Application to H.264/SVC Video Content
delivery", In Proceeding of 14th International Symposium Delivery", Proceedings of the 14th International Symposium
on Wireless Personal Multimedia Communications. on Wireless Personal Multimedia Communications, 2011.
Appendix A. Examples of Multipath Dijkstra Algorithm Appendix A. Examples of Multipath Dijkstra Algorithm
This appendix gives two examples of Multipath Dijkstra algorithm. This appendix gives two examples of the Multipath Dijkstra Algorithm.
A network topology is depicted in Figure 2. A network topology is depicted in Figure 2.
.-----A-----(2) .-----A-----(2)
(1) / \ \ (1) / \ \
/ / \ \ / / \ \
S (2) (1) D S (2) (1) D
\ / \ / \ / \ /
(1) / \ / (2) (1) / \ / (2)
B----(3)----C B----(3)----C
Figure 2 Figure 2
The capital letters are the names of routers. An arbitrary metric The capital letters are the names of routers. An arbitrary metric
with value between 1 and 3 is used. The initial metrics of all the with value between 1 and 3 is used. The initial metrics of all the
links are indicated in the parentheses. The incremental functions links are indicated in the parentheses. The incremental functions
fp(c)=4c and fe(c)=2c are used in this example. Two paths from fp(c)=4c and fe(c)=2c are used in this example. Two paths from
router S to router D are demanded. router S to router D are demanded.
On the first run of the Dijkstra algorithm, the shortest path S->A->D On the first run of the Dijkstra Algorithm, the shortest path S->A->D
with metric 3 is obtained. with metric 3 is obtained.
The incremental function fp is applied to increase the metric of the The incremental function fp is applied to increase the metric of the
link S-A and A-D. fe is applied to increase the metric of the link link S-A and A-D, and fe is applied to increase the metric of the
A-B and A-C. Figure 3 shows the link metrics after the increment. link A-B and A-C. Figure 3 shows the link metrics after the
increment.
.-----A-----(8) .-----A-----(8)
(4) / \ \ (4) / \ \
/ / \ \ / / \ \
S (4) (2) D S (4) (2) D
\ / \ / \ / \ /
(1) / \ / (2) (1) / \ / (2)
B----(3)----C B----(3)----C
Figure 3 Figure 3
On the second run of the Dijkstra algorithm, the second path On the second run of the Dijkstra Algorithm, the second path
S->B->C->D with metric 6 is obtained. S->B->C->D with metric 6 is obtained.
As mentioned in Section 8.5, the Multipath Dijkstra Algorithm does As mentioned in Section 8.5, the Multipath Dijkstra Algorithm does
not guarantee strict disjoint paths in order to avoid choosing not guarantee strict disjoint paths in order to avoid choosing
inferior paths. For example, given the topology in Figure 4, two inferior paths. For example, given the topology in Figure 4, two
paths from node S to D are desired. On the top of the figure, there paths from node S to D are desired. On the top of the figure, there
is a high cost path between S and D. is a high cost path between S and D.
If a algorithm tries to obtain strict disjoint paths, the two paths If an algorithm tries to obtain strict disjoint paths, the two paths
obtained will be S--B--D and S--(high cost path)--D, which are obtained will be S--B--D and S--(high cost path)--D, which are
extremely unbalanced. It is undesirable because it will cause huge extremely unbalanced. It is undesirable because it will cause huge
delay variance between the paths. By using the Multipath Dijkstra delay variance between the paths. By using the Multipath Dijkstra
algorithm, which is based on the punishing scheme, S--B--D and Algorithm, which is based on the punishing scheme, S--B--D and
S--B--C--D will be obtained. S--B--C--D will be obtained.
--high cost path- --high cost path-
/ \ / \
/ \ / \
S----B--------------D S----B--------------D
\ / \ /
\---C-----/ \---C-----/
Figure 4 Figure 4
Acknowledgments
The authors would like to thank Sylvain David, Asmaa Adnane, Eddy
Cizeron, Salima Hamma, Pascal Lesage, and Xavier Lecourtier for their
efforts in developing, implementing, and testing the specification.
The authors also appreciate valuable discussions with Thomas Clausen,
Ulrich Herberg, Justin Dean, Geoff Ladwig, Henning Rogge, Marcus
Barkowsky, and especially Christopher Dearlove for his multiple
rounds of reviews during the working group last calls.
Authors' Addresses Authors' Addresses
Jiazi Yi Jiazi Yi
Ecole Polytechnique Ecole Polytechnique
91128 Palaiseau Cedex, 91128 Palaiseau Cedex
France France
Phone: +33 (0) 1 77 57 80 85 Phone: +33 (0) 1 77 57 80 85
Email: jiazi@jiaziyi.com Email: jiazi@jiaziyi.com
URI: http://www.jiaziyi.com/ URI: http://www.jiaziyi.com/
Benoit Parrein Benoit Parrein
University of Nantes University of Nantes
IRCCyN lab - IVC team IRCCyN Lab - IVC team
Polytech Nantes, rue Christian Pauc, BP50609 Polytech Nantes, rue Christian Pauc, BP50609
44306 Nantes cedex 3 44306 Nantes cedex 3
France France
Phone: +33 (0) 2 40 68 30 50 Phone: +33 (0) 2 40 68 30 50
Email: Benoit.Parrein@polytech.univ-nantes.fr Email: Benoit.Parrein@polytech.univ-nantes.fr
URI: http://www.irccyn.ec-nantes.fr/~parrein URI: http://www.irccyn.ec-nantes.fr/~parrein
 End of changes. 161 change blocks. 
451 lines changed or deleted 377 lines changed or added

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