draft-ietf-manet-olsrv2-multipath-06.txt   draft-ietf-manet-olsrv2-multipath-07.txt 
Network Working Group J. Yi Network Working Group J. Yi
Internet-Draft LIX, Ecole Polytechnique Internet-Draft LIX, Ecole Polytechnique
Intended status: Experimental B. Parrein Intended status: Experimental B. Parrein
Expires: January 22, 2016 University of Nantes Expires: July 23, 2016 University of Nantes
July 21, 2015 January 20, 2016
Multi-path Extension for the Optimized Link State Routing Protocol Multi-path Extension for the Optimized Link State Routing Protocol
version 2 (OLSRv2) version 2 (OLSRv2)
draft-ietf-manet-olsrv2-multipath-06 draft-ietf-manet-olsrv2-multipath-07
Abstract Abstract
This document specifies a multi-path extension for the Optimized Link This document specifies a multi-path extension for the Optimized Link
State Routing Protocol version 2 (OLSRv2) to discover multiple State Routing Protocol version 2 (OLSRv2) to discover multiple
disjoint paths, so as to improve reliability of the OLSRv2 protocol. disjoint paths, so as to improve reliability of the OLSRv2 protocol.
The interoperability with OLSRv2 is retained. The interoperability with OLSRv2 is retained.
Status of this Memo Status of this Memo
skipping to change at page 1, line 35 skipping to change at page 1, line 35
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 22, 2016. This Internet-Draft will expire on July 23, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2016 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
skipping to change at page 2, line 16 skipping to change at page 2, line 16
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3 1.1. Motivation and Experiments to Be Conducted . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6
5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 7 5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 7
5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 7 5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 7
6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 7 6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 7
6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 8 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 7
6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . . 8 6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . . 8
6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 8 6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 8
6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8
7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 9 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 8
7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 9 7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . . 9
7.2. Multi-path Routing Set . . . . . . . . . . . . . . . . . . 9 7.2. Multi-path Routing Set . . . . . . . . . . . . . . . . . . 9
8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 10 8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 10
8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 10 8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 10
8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 10 8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 10
8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10 8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 10
8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 11 8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 11
8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 12 8.5. Multi-path Calculation . . . . . . . . . . . . . . . . . . 11
8.5.1. Requirements of Multi-path Calculation . . . . . . . . 11
8.5.2. Multi-path Dijkstra Algorithm . . . . . . . . . . . . 12
8.6. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 13
9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13
10. Implementation Status . . . . . . . . . . . . . . . . . . . . 14 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 14
10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 14 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 15
10.2. Multi-path extension based on olsrd . . . . . . . . . . . 14 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 15
10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 15 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 15
11. Security Considerations . . . . . . . . . . . . . . . . . . . 15 11. Security Considerations . . . . . . . . . . . . . . . . . . . 16
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
12.1. Expert Review: Evaluation Guidlines . . . . . . . . . . . 16 12.1. Expert Review: Evaluation Guidlines . . . . . . . . . . . 16
12.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 16 12.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 17
13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17
14.1. Normative References . . . . . . . . . . . . . . . . . . . 17 14.1. Normative References . . . . . . . . . . . . . . . . . . . 17
14.2. Informative References . . . . . . . . . . . . . . . . . . 17 14.2. Informative References . . . . . . . . . . . . . . . . . . 18
Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 19 Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21
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.
skipping to change at page 4, line 19 skipping to change at page 4, line 19
OLSRv2 is expected to be revised and improved to the Standard Track, OLSRv2 is expected to be revised and improved to the Standard Track,
once sufficient operational experience is obtained. Other than once sufficient operational experience is obtained. Other than
general experiences including the protocol specification, general experiences including the protocol specification,
interoperability with original OLSRv2 implementations, the interoperability with original OLSRv2 implementations, the
experiences in the following aspects are highly appreciated: experiences in the following aspects are highly appreciated:
o Optimal values for the number of multiple paths (NUMBER_OF_PATHS) o Optimal values for the number of multiple paths (NUMBER_OF_PATHS)
to be used. This depends on the network topology and router to be used. This depends on the network topology and router
density. density.
o Optimal values used in the cost functions. Cost functions are o Optimal values used in the metric functions. Metric functions are
applied to punish the costs 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-disjoint or link-disjoint) may depend on the layer 2 (node-disjoint or link-disjoint) may depend on the layer 2
protocol used, and can be achieved by setting different sets of protocol used, and can be achieved by setting different sets of
cost functions. metric functions.
o Use of metrics other than hop-count. This multi-path extension o Use of other metric types. This multi-path extension can be used
can be used not only for hop-count metric type, but also other not only for hop-count metric type, but also other metric types
metric types that meet the requirement of OLSRv2, such as that meet the requirement of OLSRv2, such as
[I-D.ietf-manet-olsrv2-dat-metric]. The metric type used has also [I-D.ietf-manet-olsrv2-dat-metric]. The metric type used has also
co-relation with the choice of cost functions as indicated in the co-relation with the choice of metric functions as indicated in
previous bullet point. the previous bullet point.
o Optimal choice of "key" routers for loose source routing. In some o Optimal choice of "key" routers for loose source routing. In some
cases, loose source routing is used to reduce overhead or for cases, loose source routing is used to reduce overhead or for
interoperability with OLSRv2 routers. Other than the basic rules interoperability with OLSRv2 routers. Other than the basic rules
defined in the following of this document, optimal choices of defined in the following of this document, optimal choices of
routers to put in the loose source routing header can be further routers to put in the loose source routing header can be further
studied. studied.
o Different path-selection schedulers. By default, Round-Robin o Different path-selection schedulers. By default, Round-Robin
scheduling is used to select a path to be used for a datagram. In scheduling is used to select a path to be used for datagrams. In
some scenarios, weighted scheduling can be considered: for some scenarios, weighted scheduling can be considered: for
example, the paths with lower costs (higher path quality) can example, the paths with lower metrics (i.e., higher quality) can
transfer more datagrams compared to paths with higher costs. transfer more datagrams compared to paths with higher metrics.
o The impacts of the delay variation due to multi-path routing. o The impacts of the delay variation due to multi-path routing.
[RFC2991] brings out some concerns of multi-path routing, [RFC2991] brings out some concerns of multi-path routing,
especially variable latencies. Although current experiment especially variable latencies. Although current experiment
results show that multi-path routing can reduce the jitter in results show that multi-path routing can reduce the jitter in
dynamic scenarios, some transport protocols or applications may be dynamic scenarios, some transport protocols or applications may be
sensitive to the datagram re-ordering. sensitive to the datagram re-ordering.
o The disjoint multi-path protocol has interesting application with o The disjoint multi-path protocol has interesting application with
Forward Error Correction (FEC) Coding, especially for services Forward Error Correction (FEC) Coding, especially for services
like video/audio streaming. The combination of FEC coding like video/audio streaming. The combination of FEC coding
mechanisms and this extension is thus encouraged. By applying FEC mechanisms and this extension is thus encouraged. By applying FEC
coding, the issue of packet re-ordering can be alleviated. coding, the issue of packet re-ordering can be alleviated.
o Different algorithms to obtain multiple paths, other than the o Different algorithms to obtain multiple paths, other than the
default Multi-path Dijkstra algorithm introduced in this default Multi-path Dijkstra algorithm introduced in this
specification. specification.
o In addition to the IP source routing based approach, it can be o The use of multi-topology information. By using [RFC7722],
interesting to try multi-path routing in MANET using label- multiple topologies using different metric types can be obtained.
switched flow in the future. It is also encouraged to experiment the use of multiple metrics
for building multiple paths.
o The use of multi-topology information. By using
[I-D.ietf-manet-olsrv2-multitopology], multiple topologies using
different metric types can be obtained. It is also encouraged to
experiment the use of multiple metrics for building multiple
paths.
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
[RFC2119]. [RFC2119].
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], [RFC7181]. Additionally, it defines the following
skipping to change at page 6, line 10 skipping to change at page 6, line 5
from a source router to a destination router. from a source router to a destination router.
MP-OLSRv2 is specially designed for networks with dynamic topology MP-OLSRv2 is specially designed for networks with dynamic topology
and low data rate links. By providing multiple paths, higher and low data rate links. By providing multiple paths, higher
aggregated throughput can be obtained, and the routing process is aggregated throughput can be obtained, and the routing process is
more robust to packet loss. more robust to packet loss.
In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily
replace OLSRv2 completely. The extension can be applied for certain replace OLSRv2 completely. The extension can be applied for certain
applications that are suitable for multi-path routing (mainly video applications that are suitable for multi-path routing (mainly video
or audio streams), based on the information such as DiifServ Code or audio streams), based on the information such as DiffServ Code
Point [RFC2474]. Point [RFC2474].
Compared to OLSRv2, this extension does not introduce new message Compared to OLSRv2, this extension does not introduce new message
type in the air. A new Message TLV type is introduced to identify type in the air. A new Message TLV type is introduced to identify
the routers that support forwarding based on source route header. It the routers that support forwarding based on source route header. It
is interoperable with OLSRv2 implementations that do not have this is interoperable with OLSRv2 implementations that do not have this
extension. extension.
MP-OLSRv2 forwards datagrams using the source routing header. MP-OLSRv2 forwards datagrams using the source routing header. For
Depending on the IP version used, the source routing header is IPv4 networks, implementation of loose source routing is required
formatted according to [RFC0791] or [RFC6554]. following [RFC0791]. For IPv6 networks, implementation of strict
source routing is required following [RFC6554].
4. Protocol Overview and Functioning 4. Protocol Overview and Functioning
This specification requires OLSRv2 [RFC7181] to: This specification requires OLSRv2 [RFC7181] to:
o Identify all the reachable routers in the network. o Identify all the reachable routers in the network.
o Identify a sufficient subset of links in the networks, so that o Identify a sufficient subset of links in the networks, so that
routes can be calculated to all reachable destinations. routes can be calculated to all reachable destinations.
skipping to change at page 6, line 44 skipping to change at page 6, line 40
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
TC messages. Based on the above information acquired, every MP- TC messages. Based on the above information acquired, every MP-
OLSRv2 Routing Process is aware of a reduced topology map of the OLSRv2 Routing Process is aware of a reduced topology map of the
network and the routers supporting source routing. network and the routers supporting source routing.
A multi-path algorithm is invoked on demand, i.e., only when there is A multi-path algorithm is invoked on demand, i.e., only when there is
a datagram to be sent from the source to the destination, and there a datagram to be sent from the source to the destination, and there
is no available routing tuple in the Multi-path Routing Set. The is no available routing tuple in the Multi-path Routing Set. The
Multi-path Dijkstra algorithm (defined in Section 8.4) can generate Multi-path Dijkstra algorithm (defined in Section 8.5) can generate
multiple disjoint paths from a source to a destination, and such multiple disjoint paths from a source to a destination, and such
information is kept in the Multi-path Routing Set. information is kept in the Multi-path Routing Set.
The datagram is forwarded based on source routing. When there is a The datagram is forwarded based on source routing. When there is a
datagram to be sent to a destination, the source router acquires a datagram to be sent to a destination, the source router acquires a
path from the Multi-path Routing Set (MAY be Round-Robin, or other path from the Multi-path Routing Set (MAY be Round-Robin, or other
scheduling algorithms). The path information is stored in the scheduling algorithms). The path information is stored in the
datagram header as source routing header. datagram header as source routing header.
All the intermediate routers are listed in the source routing header
(SRH), unless there are routers that do not support source-route
forwarding in the paths, or the paths are too long to be fully stored
in the SRH -- in which case, loose source routing is used. The
intermediate routers listed in the SRH read the SRH and forward the
datagram to the next hop as indicated in the SRH.
5. Parameters and Constants 5. Parameters and Constants
In addition to the parameters and constants defined in [RFC7181], In addition to the parameters and constants defined in [RFC7181],
this specification uses the parameters and constants described in this specification uses the parameters and constants described in
this section. this section.
5.1. Router Parameters 5.1. Router Parameters
NUMBER_OF_PATHS The number of paths desired by the router. NUMBER_OF_PATHS The number of paths desired by the router.
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. source routing header. A value set zero means there is no
limitation on the maximum number of hops. In an IPv6 network, it
fp Incremental function of the Multi-path Dijkstra algorithm. It MUST be set to 0. In an IPv4 network, it MUST be strictly less
is used to increase costs of links belonging to the previously than 11.
computed path.
fe Incremental function of the Multi-path Dijkstra algorithm. It CUTOFF_RATIO The ratio that defines the maximum metric of a path
is used to increase costs of links that lead to routers of the compared to the shortest path kept in the OLSRv2 Routing Set. For
previously computed path. example, the metric to a destination is R_metric based on the
Routing Set. Then the maximum metric allowed for a path is
CUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be strictly greater
than 1.
MR_HOLD_TIME It is the minimal time that a Multi-path Routing Tuple SR_TC_INTERVAL The maximum time between the transmission of two
SHOULD be kept in the Multi-path Routing Set. successive TC messages by a MP-OLSRv2 Routing Process.
SR_OLSR_HOLD_TIME It is the minimal time that a SR-OLSRv2 Router SR_OLSR_HOLD_TIME It is the minimal time that a SR-OLSRv2 Router
Tuple SHOULD be kept in the SR-OLSRv2 Router Set. Tuple SHOULD be kept in the SR-OLSRv2 Router Set.
6. Packets and Messages 6. Packets and Messages
This extension employs the routing control messages HELLO and TC This extension employs the routing control messages HELLO and TC
(Topology Control) as defined in OLSRv2 [RFC7181]. To support source (Topology Control) as defined in OLSRv2 [RFC7181]. To support source
routing, a source routing header is added to each datagram routed by routing, a source routing header is added to each datagram routed by
this extension. Depending on the IP version used, the source routing this extension. Depending on the IP version used, the source routing
skipping to change at page 8, line 19 skipping to change at page 8, line 8
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 that supports source route forwarding. The new Message TLV message that supports source route forwarding. The new Message TLV
type is introduced for enabling MP-OLSRv2 as an extension of OLSRv2: type is introduced for enabling MP-OLSRv2 as an extension of OLSRv2:
only the routers supporting source-route forwarding can be used in only the routers supporting source-route forwarding can be used in
the source routing header of a datagram, because adding a router that the source routing header of a datagram, because adding a router that
does not understand the source routing header will cause routing does not 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 that signals that the message is SOURCE_ROUTE TLV is a Message TLV signalling 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. The SOURCE_ROUTE TLV does not supports source-route forwarding. The SOURCE_ROUTE TLV does not
include any value. include any value.
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. MUST have exactly one SOURCE_ROUTE TLV.
Every HELLO or TC message generated by an OLSRv2 Routing Process MAY Every HELLO or TC message generated by an OLSRv2 Routing Process MAY
have one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process supports have one SOURCE_ROUTE TLV, if the OLSRv2 Routing Process supports
skipping to change at page 9, line 37 skipping to change at page 9, line 28
SR_OLSR_valid_time - it is the time until which the SR-OLSRv2 SR_OLSR_valid_time - it is the time until which the SR-OLSRv2
Router Tuples is considered valid. Router Tuples is considered valid.
7.2. Multi-path Routing Set 7.2. Multi-path Routing Set
The Multi-path Routing Set records the full path information of The Multi-path Routing Set records the full path information of
different paths to the destination. It consists of Multi-path different paths to the destination. It consists of Multi-path
Routing Tuples: Routing Tuples:
(MR_dest_addr, MR_valid_time, MR_path_set) (MR_dest_addr, MR_path_set)
where: where:
MR_dest_addr - it is the network address of the destination, either MR_dest_addr - it is the network address of the destination, either
the network address of an interface of a destination router or the the network address of an interface of a destination router or the
network address of an attached network; network address of an attached network;
MR_valid_time - it is the time until which the Multi-path Routing
Tuple is considered valid;
MP_path_set - it contains the multiple paths to the destination. MP_path_set - it contains the multiple paths to the destination.
It consists of a set of Path Tuples. It consists of a set of Path Tuples.
Each Path Tuple is defined as: Each Path Tuple is defined as:
(PT_cost, PT_address[1], PT_address[2], ..., PT_address[n]) (PT_metric, PT_address[1], PT_address[2], ..., PT_address[n])
where: where:
PT_cost - the cost of the path to the destination; PT_metric - the metric of the path to the destination, measured in
LINK_METRIC_TYPE defined in [RFC7181];
PT_address[1...n] - the addresses of intermediate routers to be PT_address[1...n] - the addresses of intermediate routers to be
visited numbered from 1 to n. visited numbered from 1 to n.
8. Protocol Details 8. Protocol Details
This protocol is based on OLSRv2, and extended to discover multiple This protocol is based on OLSRv2, and extended to discover multiple
disjoint paths from 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 basic routing control packets formats and processing of
OLSRv2 to obtain topology information of the network. The main OLSRv2 to obtain topology information of the network. The main
differences between OLSRv2 routing process are the datagram differences between OLSRv2 routing process are the datagram
processing at the source router and datagram forwarding. processing at the source router and datagram forwarding.
8.1. HELLO and TC Message Generation 8.1. HELLO and TC Message Generation
HELLO and TC messages are generated according to the Section 15.1 or HELLO messages are generated according to the Section 15.1 of
Section 16.1 of [RFC7181]. [RFC7181].
A single Message TLV with Type := SOURCE_ROUTE MUST be added to the TC message are generated according to the Section 16.1 of [RFC7181].
message. As least one TC message MUST be generated by an MP-OLSRv2 Routing
Process during SR_TC_INTERVAL.
For both TC and HELLO messages, a single Message TLV with Type :=
SOURCE_ROUTE MUST be added to the message.
8.2. HELLO and TC Message Processing 8.2. HELLO and TC Message Processing
HELLO and TC messages are processed according to the section 15.3 and HELLO and TC messages are processed according to the section 15.3 and
16.3 of [RFC7181]. 16.3 of [RFC7181].
For every HELLO or TC message received, if there exists a 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 Router Tuple with
o SR_OLSR_addr = originator of the HELLO or TC message o SR_OLSR_addr := originator of the HELLO or TC message
and set the SR_OLSR_valid_time := current_time + SR_OLSR_HOLD_TIME. o SR_OLSR_valid_time := current_time + SR_OLSR_HOLD_TIME.
8.3. Datagram Processing at the MP-OLSRv2 Originator 8.3. MPR Selection
When the MP-OLSRv2 routing process receives a datagram from upper Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs
layers or interfaces connecting other routing domains, find the following Section 18 of [RFC7181]. In a mixed network with OLSRv2-
Multi-path Routing Tuple where: only routers, the following considerations apply when calculating
MPRs:
o MR_dest_addr = destination of the datagram, and o MP-OLSR routers SHOULD be preferred as routing MPRs.
o MR_valid_time > current_time.
If a matching Multi-path Routing Tuple is found, a Path Tuple is o The number of routing MPRs that run MP-OLSR Routing Process MUST
chosen from the MR_path_set in Round-robin fashion (if there are be equal or greater than NUMBER_OF_PATHS if there are enough MP-
multiple datagrams to be sent). Or else, the multi-path algorithm OLSR symmetric neighbors. Or else, all the MP-OLSR routers are
defined in Section 8.4 is invoked, to generate the desired Multi-path selected as routing MPRs.
Routing Tuple.
8.4. Datagram Processing at the MP-OLSRv2 Originator
If datagrams without source routing header need to be forwarded using
multiple paths (for example, based on the information of DiffServ
Code Point [RFC2474]), the MP-OLSRv2 routing process will try to find
the Multi-path Routing Tuple where:
o MR_dest_addr = destination of the datagram
If no matching Multi-path Routing Tuple is found, the multi-path
algorithm defined in Section 8.5 is invoked, to calculate the Multi-
path Routing Tuple to the destination. If the calculation does not
return any Multi-path Routing Tuple, the following steps are aborted
and the datagram is forwarded following OLSRv2 routing process.
The Path Tuples of the Multi-path Routing Tuple obtained are applied
to the datagrams using Round-robin scheduling. For example, they are
2 path tuples (Path-1, Path-2) for destination router D. A series of
datagrams (Packet-1, Packet-2, Packet-3, ... etc.) are to be sent
router D. Path-1 is then chosen for Packet-1, Path-2 for Packet-2,
Path-1 for Packet 3, etc.
The addresses in PT_address[1...n] of the chosen Path Tuple are thus The addresses in PT_address[1...n] of the chosen Path Tuple are thus
added to the datagram header as source routing header, following the added to the datagram header as the source routing header. For IPv6
rules: networks, strict source routing is used, thus all the intermediate
routers in the path are stored in the source routing header following
[RFC6554]. For IPv4 networks, loose source routing is used, with
following rules:
o Only the addresses that exist in SR-OLSR Router Set can be added o Only the addresses that exist in SR-OLSR Router Set can be added
to the source routing header. to the source routing header.
o If the length of the path (n) is greater than MAX_SRC_HOPS, only o If the length of the path (n) is greater than MAX_SRC_HOPS, only
the key routers in the path are kept. By default, the key routers the "key" routers in the path are kept. The key routers can be
are uniformly chosen in the path. chosen based on the capacity of the routers (e.g., battery life)
or the router's willingness in forwarding data. If no such
o The routers with higher priority (such as higher routing information is available, the key routers are uniformly chosen in
willingness defined in [RFC7181]) are preferred. the path.
o The routers that are considered not appropriate for forwarding o The routers that are considered not appropriate for forwarding
indicated by external policies should be avoided. indicated by external policies should be avoided.
8.4. Multi-path Dijkstra Algorithm 8.5. Multi-path Calculation
8.5.1. Requirements of Multi-path Calculation
The Multi-path Routing Set maintains the information of multiple
paths the the destination. The tuples are generated based on a
multi-path algorithm.
A multi-path algorithm is invoked when there is no available Multi- A multi-path algorithm is invoked when there is no available Multi-
path Routing Tuple to a desired destination d to obtain the multiple path Routing Tuple to a desired destination to obtain the multiple
paths. This section introduces Multi-path Dijkstra Algorithm as a paths. For each path to a destination, the algorithm must provide:
default mechanism. It tries to obtain disjoint paths when
appropriate, but does not guarantee strict disjoint paths. The
rationale is explained in Appendix A.
The use of other algorithms is not prohibited, as long as they can o The metric of the path to the destination,
provide a full path from the source to the destination router. Using
different multi-path algorithms will not impact the interoperability. o The list of intermediate routers on the path.
For IPv6 networks, as strict source routing is used, only the routers
that exist in SR-OLSRv2 Router Set are considered in the path
calculation, i.e., only the source-routing supported routers can
exist in the path. After the calculation of multiple paths, the
metric of the shortest path (denoted c) to the destination is
compared to the R_metric of the OLSRv2 Routing Tuple ([RFC7181]) to
the same destination. If the metric c is greater than R_metric *
CUTOFF_RATIO, the multipath routing SHOULD NOT be used, and the
router SHOULD fall back to OLSRv2 Routing Process. This can happen
if there are too much OLSRv2-only routers in the network, and
requiring multipath routing brutally may result in inferior paths.
By invoking the multi-path algorithm, NUMBER_OF_PATHS paths are
obtained and added to the Multi-path Routing Set, by creating a
Multi-path Routing Tuple with:
o MR_dest_addr := destination of the datagram
o A MP_path_set with calculated Path Tuples. Each Path Tuple
corresponds to a path obtained in Multi-path Dijkstra algorithm,
with PT_metric := metric of the calculated path and
PT_address[1...n] := list of intermediate routers.
8.5.2. Multi-path Dijkstra Algorithm
This section introduces Multi-path Dijkstra Algorithm as a default
algorithm. It tries to obtain disjoint paths when appropriate, but
does not guarantee strict disjoint paths. The use of other
algorithms is not prohibited, as long as the requirements described
in Section 8.5.1 are met. Using different multi-path algorithms will
not impact the interoperability.
The general principle of the Multi-path Dijkstra Algorithm is at step The general principle of the Multi-path Dijkstra Algorithm is at step
i to look for the shortest path P[i] to the destination d. Compared i to look for the shortest path P[i] to the destination d. Compared
to the original Dijkstra algorithm, the main modification consists in to the original Dijkstra algorithm, the main modification consists in
adding two cost functions named incremental functions fp and fe in adding two incremental functions named metric functions fp and fe in
order to prevent the next steps resulting in similar paths. fp is order to prevent the next steps resulting in similar paths:
used to increase costs of arcs belonging to the previous path P[i-1]
(with i>1). This encourages future paths to use different arcs but o fp(c) is used to increase metrics of arcs belonging to the
not different vertices. fe is used to increase costs of the arcs who previous path P[i-1] (with i>1), where c is the value of the
lead to vertices of the previous path P[i-1] (with i>1). It is previous metric. This encourages future paths to use different
possible to choose different fp and fe to get link-disjoint paths or arcs but not different vertices.
node-disjoint paths as desired. A recommendation of configuration of
fp and fe is given in Section 9. o fe(c) is used to increase metrics of the arcs who lead to
intermediate vertices (i.e., the source and destination are not
considered) of the previous path P[i-1] (with i>1), where c is the
value of the previous metric.
It is possible to choose different fp and fe to get link-disjoint
paths or node-disjoint paths as desired. A recommendation of
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 P[i] (i = 1,
..., NUMBER_OF_PATHS) do: ..., NUMBER_OF_PATHS) do:
1. Run Dijkstra algorithm to get the shortest path P[i] for the 1. Run Dijkstra algorithm to get the shortest path P[i] for the
destination d. destination d.
2. Apply cost function fp to the cost of links (in both directions) 2. Apply metric function fp to the metric of links (in both
in P[i]. directions) in P[i].
3. Apply cost function fe to the cost of links (in both directions) 3. Apply metric function fe to the metric of links (in both
that lead to routers used in P[i]. directions) that lead to routers used in P[i].
A simple example of Multi-path Dijkstra Algorithm is illustrated in A simple example of Multi-path Dijkstra Algorithm is illustrated in
Appendix A. Appendix A.
By invoking the algorithm depicted above, NUMBER_OF_PATHS paths are 8.6. Datagram Forwarding
obtained and added to the Multi-path Routing Set, by creating a
Multi-path Routing Tuple with:
o MR_dest_addr := destination d
o MR_valid_time := current time + MR_HOLD_TIME
o Each Path Tuple in the MP_path_set corresponds to a path obtained
in Multi-path Dijkstra algorithm, with PT_cost := cost of the path
to the destination d (which may include one or several additions
of the cost functions).
8.5. Datagram Forwarding
On receiving a datagram with source routing header, the Destination
Address field of the IP header is first compared to the addresses of
the local interfaces. If a matching local address if found, the
datagram is processed from Step 1 to Step 4 as follows. Or else, the
datagram is processed from Step 3 to Step 4.
1. Obtain the next source address Address[i] in the source route
header. How to obtain the next source address depends on the IP
version used. In IPv4, the position of the next source address
is indicated by the "pointer" field of the source routing header
[RFC0791]. In IPv6, the position is indicated by "Segments Left"
field of the source routing header. If no next source address is
found, the forwarding process is finished and the datagram
arrives at its destination.
2. Swap Address[i] and destination address in the IP header.
3. If the Destination Address of the IP header belongs to one of the
router's 1-hop symmetric neighbors, the datagram is forwarded to
the neighbor router. Or else:
4. Forward the datagram to the destination address according to the In IPv4 networks, datagrams are forwarded using loose source routing
OLSRv2 Routing Tuple information through R_local_iface_addr where as specified in Section 3.1 of [RFC0791].
* R_dest_addr = destination address in the IP header In IPv6 networks, datagrams are forwarded using strict source routing
as specified in Section 4.2 of [RFC6554].
9. Configuration Parameters 9. Configuration Parameters
This section gives default values and guideline for setting This section gives default values and guideline 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 change certain, or all the parameters for different network
scenarios. As an experimental track protocol, the users of this scenarios. As an experimental track protocol, the users of this
protocol are also encouraged to explore different parameter setting protocol are also encouraged to explore different parameter setting
in various network environments, and provide feedback. in various network 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 one
makes the specification identical to OLSRv2. Setting it to too makes the specification identical to OLSRv2. Setting it to too
large values may lead to unnecessary computational overhead and large values may lead to unnecessary computational overhead and
inferior paths. inferior paths.
o MAX_SRC_HOPS = 10. 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.
o MR_HOLD_TIME = 10 seconds. o CUTOFF_RATIO := 1.5. It MUST be strictly greater than 1.
o MP_OLSR_HOLD_TIME = 10 seconds. o SR_TC_INTERVAL := 10 x TC_INTERVAL. It SHOULD be significantly
greater than TC_INTERVAL to reduce unnecessary TC message
generations.
o fp(c) = 4*c, where c is the original cost of the link. o SR_OLSR_HOLD_TIME := 3 x SR_TC_INTERVAL
o fe(c) = 2*c, where c is the original cost of the link. If Multi-path Dijkstra Algorithm is applied:
The setting of cost functions fp and fc defines the preference of 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.
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, 3 cases are possible:
o if id=fe<fp: paths tend to be link disjoint; o if id=fe<fp: paths tend to be link disjoint;
o if id<fe=fp: paths tend to be node-disjoint; o if id<fe=fp: paths tend to be node-disjoint;
o if id<fe<fp: paths also tend to be node-disjoint, but when is not o if id<fe<fp: paths also tend to be node-disjoint, but when is not
possible they tend to be arc disjoint. possible they tend to be arc disjoint.
skipping to change at page 15, line 30 skipping to change at page 16, line 17
The implementation is for network simulation for NS2 network The implementation is for network simulation for NS2 network
simulator. All the specification is implemented in this simulator. All the specification is implemented in this
implementation. implementation.
Implementation experience and test data can be found at [WCNC08]. Implementation experience and test data can be found at [WCNC08].
11. Security Considerations 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. MP-OLSRv2 specification. The implementations without security
mechanisms are vulnerable to threats discussed in
[I-D.ietf-manet-olsrv2-sec-threats].
The implementations without security mechanisms are vulnerable to In a mixed network with OLSRv2-only routers, a compromised router can
threats discussed in [I-D.ietf-manet-olsrv2-sec-threats]. As add SOURCE_ROUTE TLVs in its TC and HELLO messages, which will make
[RFC7181], a conformant implementation of MP-OLSRv2 MUST, at minimum, other MP-OLSR Routing Process believes that it supports source
implement the security mechanisms specified in [RFC7183] to provide routing. This will increase the the possibility of being chosen as
integrity and replay protection of routing control messages. MPRs and be put into the source routing header. The former will make
it possible to manipulate the flooding of TC messages and the latter
will make the datagram pass through the compromised router.
As [RFC7181], a conformant implementation of MP-OLSRv2 MUST, at
minimum, implement the security mechanisms specified in [RFC7183] to
provide integrity and replay protection of routing control messages.
Compared to OLSRv2, the use of source routing header in this Compared to OLSRv2, the use of source routing header in this
specification introduces vulnerabilities related to source routing specification introduces vulnerabilities related to source routing
attacks, which include bypassing filtering devices, bandwidth 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.1 of [RFC6554] and [RFC5095]. To make sure that the Section 5.1 of [RFC6554] and [RFC5095].
influence is limited to the OLSRv2/MP-OLSRv2 routing domain, the
source routing header MUST be used only in the current routing
domain.
12. IANA Considerations 12. 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.
This specification assumes that the TLV renaming specified in
[I-D.ietf-manet-tlv-naming] has been carried out.
12.1. Expert Review: Evaluation Guidlines 12.1. Expert Review: Evaluation Guidlines
For the registry where an Expert Review is required, the designated For the registry where an Expert Review is required, the designated
expert SHOULD take the same general recommendations into expert SHOULD take the same general recommendations into
consideration as are specified by [RFC5444] and consideration as are specified by [RFC5444].
[I-D.ietf-manet-tlv-naming].
12.2. Message TLV Types 12.2. Message TLV Types
This specification updates the Message Type 7 by adding the new Type This specification updates the Message Type 7 by adding the new Type
Extension SOURCE_ROUTE, as illustrated in Table 1. Extension SOURCE_ROUTE, as illustrated in Table 1.
+-----------+--------------+------------------------+---------------+ +-----------+--------------+------------------------+---------------+
| Type | Name | Description | Reference | | Type | Name | Description | Reference |
| Extension | | | | | Extension | | | |
+-----------+--------------+------------------------+---------------+ +-----------+--------------+------------------------+---------------+
| TBD | SOURCE_ROUTE | Indicates the | This | | TBD | SOURCE_ROUTE | Indicates the | This |
| | | originator of the | specification | | | | originator of the | specification |
| | | message supports | | | | | message supports | |
| | | source route | | | | | source route | |
| | | forwarding. No value. | | | | | forwarding. No value. | |
| TBD-223 | | Unassigned | |
| 224-255 | | Reserved for | |
| | | Experimental Use | |
+-----------+--------------+------------------------+---------------+ +-----------+--------------+------------------------+---------------+
Table 1: SOURCE_ROUTE type for RFC 5444 Type 7 Message TLV Type Table 1: SOURCE_ROUTE type for RFC 5444 Type 7 Message TLV Type
Extensions Extensions
13. Acknowledgments 13. Acknowledgments
The authors would like to thank Sylvain David, Asmaa Adnane, Eddy The authors would like to thank Sylvain David, Asmaa Adnane, Eddy
Cizeron, Salima Hamma, Pascal Lesage and Xavier Lecourtier for their Cizeron, Salima Hamma, Pascal Lesage and Xavier Lecourtier for their
efforts in developing, implementing and testing the specification. efforts in developing, implementing and testing the specification.
The authors also appreciate valuable comments and discussions from The authors also appreciate valuable comments and discussions from
Thomas Clausen, Ulrich Herberg, Justin Dean, Geoff Ladwig, Henning Thomas Clausen, Ulrich Herberg, Justin Dean, Geoff Ladwig, Henning
Rogge, Christopher Dearlove and Marcus Barkowsky. Rogge, Christopher Dearlove and Marcus Barkowsky.
14. References 14. References
14.1. Normative References
[I-D.ietf-manet-tlv-naming] 14.1. Normative References
Dearlove, C. and T. Clausen, "TLV Naming in the MANET
Generalized Packet/Message Format",
draft-ietf-manet-tlv-naming-05 (work in progress),
June 2015.
[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, [RFC0791] 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>. <http://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, DOI 10.17487/
RFC2119, March 1997, RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <http://www.rfc-editor.org/info/rfc2119>.
skipping to change at page 18, line 16 skipping to change at page 18, line 43
[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 Global Information
Infrastructure and Networking Symposium (GIIS), 2014 , Infrastructure and Networking Symposium (GIIS), 2014 ,
vol. 1, no. 6, pp. 15-19, 2014. vol. 1, no. 6, pp. 15-19, 2014.
[I-D.ietf-manet-olsrv2-dat-metric] [I-D.ietf-manet-olsrv2-dat-metric]
Rogge, H. and E. Baccelli, "Packet Sequence Number based Rogge, H. and E. Baccelli, "Packet Sequence Number based
directional airtime metric for OLSRv2", directional airtime metric for OLSRv2",
draft-ietf-manet-olsrv2-dat-metric-05 (work in progress), draft-ietf-manet-olsrv2-dat-metric-12 (work in progress),
April 2015. December 2015.
[I-D.ietf-manet-olsrv2-multitopology]
Dearlove, C. and T. Clausen, "Multi-Topology Extension for
the Optimized Link State Routing Protocol version 2
(OLSRv2)", draft-ietf-manet-olsrv2-multitopology-06 (work
in progress), July 2015.
[I-D.ietf-manet-olsrv2-sec-threats] [I-D.ietf-manet-olsrv2-sec-threats]
Clausen, T., Herberg, U., and J. Yi, "Security Threats for Clausen, T., Herberg, U., and J. Yi, "Security Threats for
the Optimized Link State Routing Protocol version 2 the Optimized Link State Routing Protocol version 2
(OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-00 (work in (OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-01 (work in
progress), February 2015. progress), November 2015.
[RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460, (IPv6) Specification", RFC 2460, DOI 10.17487/RFC2460,
December 1998, <http://www.rfc-editor.org/info/rfc2460>. December 1998, <http://www.rfc-editor.org/info/rfc2460>.
[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>. <http://www.rfc-editor.org/info/rfc2474>.
skipping to change at page 19, line 15 skipping to change at page 19, line 34
[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>. <http://www.rfc-editor.org/info/rfc5095>.
[RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", RFC 6982, Code: The Implementation Status Section", RFC 6982,
DOI 10.17487/RFC6982, July 2013, DOI 10.17487/RFC6982, July 2013,
<http://www.rfc-editor.org/info/rfc6982>. <http://www.rfc-editor.org/info/rfc6982>.
[RFC7722] Dearlove, C. and T. Clausen, "Multi-Topology Extension for
the Optimized Link State Routing Protocol Version 2
(OLSRv2)", RFC 7722, DOI 10.17487/RFC7722, December 2015,
<http://www.rfc-editor.org/info/rfc7722>.
[WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein,
"Simulation and performance analysis of MP-OLSR for mobile "Simulation and performance analysis of MP-OLSR for mobile
ad hoc networks", In Proceeding of IEEE Wireless ad hoc networks", In Proceeding of IEEE Wireless
Communications and Networking Conference, 2008. Communications and Networking Conference, 2008.
Appendix A. Examples of Multi-path Dijkstra Algorithm Appendix A. Examples of Multi-path Dijkstra Algorithm
This appendix gives two examples of multi-path Dijkstra algorithm. This appendix gives two examples of multi-path Dijkstra algorithm.
A network topology is depicted in Figure 1. A network topology is depicted in Figure 1.
.-----2-----. .-----A-----(2)
/ / \ \ (1) / \ \
/ / \ \ / / \ \
1 / \ 5 S (2) (1) D
\ / \ / \ / \ /
\ / \ / (1) / \ / (2)
3-----------4 B----(3)----C
Figure 1 Figure 1
The initial cost of all the links is set to 1. The incremental The capital letters are name of routers. An arbitrary metric with
functions fp and fe are defined as fp(c)=4c and fe(c)=2c in this value between 1 and 3 is used. The initial metrics of all the links
example. Two paths from node 1 to node 5 are demanded. are indicated in the parenthesis. The incremental functions fp and
fe are defined as fp(c)=4c and fe(c)=2c in this example. Two paths
from router S to router D are demanded.
On the first run of the Dijkstra algorithm, the shortest path 1->2->5 On the first run of the Dijkstra algorithm, the shortest path S->A->D
with cost 2 is obtained. with metric 3 is obtained.
The incremental function fp is applied to increase the cost of the The incremental function fp is applied to increase the metric of the
link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of link S-A and A-D. fe is applied to increase the metric of the link
the link 1-3, 2-3, 2-4, 4-5, from 1 to 2. A-B and A-C. Figure 2 shows the link metrics after the punishment.
.-----A-----(8)
(4) / \ \
/ / \ \
S (4) (2) D
\ / \ /
(1) / \ / (2)
B----(3)----C
Figure 2
On the second run of the Dijkstra algorithm, the second path On the second run of the Dijkstra algorithm, the second path
1->3->4->5 with cost 5 is obtained. S->B->C->D with metric 6 is obtained.
As mentioned in Section 8.4, the Multi-path Dijkstra Algorithm does As mentioned in Section 8.5, the Multi-path Dijkstra Algorithm does
not guarantee strict disjoint path to avoid choosing inferior paths. not guarantee strict disjoint path to avoid choosing inferior paths.
For example, given the topology in Figure 2, two paths from node S to For example, given the topology in Figure 3, two paths from node S to
D are desired. D are desired. On the top of the figure, there is a high cost path
between S and D.
If a algorithm tries to obtain strict disjoint paths, the two paths If a algorithm tries to obtain strict disjoint paths, the two paths
obtained will be S--B--D and S--50 hops--D, which are extremely obtained will be S--B--D and S--(high cost path)--D, which are
unbalanced. It is undesired because it will cause huge delay extremely unbalanced. It is undesired because it will cause huge
variance between the paths. By using the Multi-path Dijkstra delay variance between the paths. By using the Multi-path 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.
---50 hops------- --high cost path-
/ \ / \
/ \ / \
S----B--------------D S----B--------------D
\ / \ /
\---C-----/ \---C-----/
Figure 2 Figure 3
Authors' Addresses Authors' Addresses
Jiazi Yi Jiazi Yi
LIX, Ecole Polytechnique LIX, Ecole Polytechnique
91128 Palaiseau Cedex, 91128 Palaiseau Cedex,
France France
Phone: +33 1 77 57 80 85 Phone: +33 1 77 57 80 85
Email: jiazi@jiaziyi.com Email: jiazi@jiaziyi.com
 End of changes. 79 change blocks. 
217 lines changed or deleted 258 lines changed or added

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