draft-ietf-manet-olsrv2-multipath-08.txt   draft-ietf-manet-olsrv2-multipath-09.txt 
Network Working Group J. Yi Network Working Group J. Yi
Internet-Draft LIX, Ecole Polytechnique Internet-Draft Ecole Polytechnique
Intended status: Experimental B. Parrein Intended status: Experimental B. Parrein
Expires: October 29, 2016 University of Nantes Expires: December 10, 2016 University of Nantes
April 27, 2016 June 8, 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-08 draft-ietf-manet-olsrv2-multipath-09
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 October 29, 2016. This Internet-Draft will expire on December 10, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2016 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
skipping to change at page 2, line 15 skipping to change at page 2, line 15
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 . . . . . . . . . . . . . . . . . . . . . 8
6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 7 6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 8
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 . . . . . . . . . . . . 9
6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 8 6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 9
7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 8 7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 9
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 . . . . . . . . . . . . . 11
8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 10 8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 11
8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 11 8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 11
8.5. Multi-path Calculation . . . . . . . . . . . . . . . . . . 11 8.5. Multi-path Calculation . . . . . . . . . . . . . . . . . . 12
8.5.1. Requirements of Multi-path Calculation . . . . . . . . 11 8.5.1. Requirements of Multi-path Calculation . . . . . . . . 12
8.5.2. Multi-path Dijkstra Algorithm . . . . . . . . . . . . 12 8.5.2. Multi-path Dijkstra Algorithm . . . . . . . . . . . . 13
8.6. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 13 8.6. Multi-path Routing Set Updates . . . . . . . . . . . . . . 14
9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13 8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 15
10. Implementation Status . . . . . . . . . . . . . . . . . . . . 14 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 15
10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 15 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 16
10.2. Multi-path extension based on olsrd . . . . . . . . . . . 15 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 16
10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 16 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 17
11. Security Considerations . . . . . . . . . . . . . . . . . . . 16 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 17
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 11. Security Considerations . . . . . . . . . . . . . . . . . . . 17
12.1. Expert Review: Evaluation Guidlines . . . . . . . . . . . 17 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18
12.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 17 12.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 18
13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17 12.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 18
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19
14.1. Normative References . . . . . . . . . . . . . . . . . . . 17 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
14.2. Informative References . . . . . . . . . . . . . . . . . . 18 14.1. Normative References . . . . . . . . . . . . . . . . . . . 19
Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 20 14.2. Informative References . . . . . . . . . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21 Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
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 28 skipping to change at page 4, line 28
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-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
metric functions. metric functions.
o Use of other metric types. This multi-path extension can be used o Use of other metric types. This multi-path extension can be used
not only for hop-count metric type, but also other metric types not only for hop-count metric type, but also other metric types
that meet the requirement of OLSRv2, such as that meet the requirement of OLSRv2, such as [RFC7779]. The
[I-D.ietf-manet-olsrv2-dat-metric]. The metric type used has also metric type used has also co-relation with the choice of metric
co-relation with the choice of metric functions as indicated in functions as indicated in the previous bullet point.
the previous bullet point.
o The impact of partial topology information to the multi-path
calculation. OLSRv2 maintains a partial topology information base
to reduce protocol overhead. Although with existing experience,
multiple paths can be obtained even with such partial information,
the calculation might be impacted, depending on the MPR selection
algorithm used.
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 datagrams. In scheduling is used to select a path to be used for datagrams. In
skipping to change at page 6, line 37 skipping to change at page 6, line 45
o Provide a Routing Set containing shortest routes from this router o Provide a Routing Set containing shortest routes from this router
to all destinations. to all destinations.
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 Routing Set containing the multi-path information is
a datagram to be sent from the source to the destination, and there maintained. It may either be proactively calculated or reactively
is no available routing tuple in the Multi-path Routing Set. The calculated:
Multi-path Dijkstra algorithm (defined in Section 8.5) can generate
o In the proactive approach, multiple paths to all possible
destinations are calculated and updated based on control message
exchange. The routes are thus available before they are actually
needed.
o In the reactive approach, 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 is no available routing tuple
in the Multi-path Routing Set.
Routers in the same network may choose either proactive or reactive
multi-path calculation independently according to their computation
resources. The Multi-path Dijkstra algorithm (defined in
Section 8.5) is introduced as the default algorithm to 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.
5. Parameters and Constants 5. Parameters and Constants
skipping to change at page 8, line 49 skipping to change at page 9, line 25
In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the In IPv6 [RFC2460] networks, the MP-OLSRv2 routing process employs the
source routing header as defined in [RFC6554], with IPv6 Routing Type source routing header as defined in [RFC6554], with IPv6 Routing Type
3. 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, two more information bases are defined in [RFC7181]. Additionally, a Multipath Information base is
defined for this specification. used for this specification. It includes the protocol sets as
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 MP-OLSRv2 Routing route forwarding. This includes routers that run MP-OLSRv2 Routing
Process, or OLSRv2 Routing Process with source-route forwarding Process, or OLSRv2 Routing Process with source-route forwarding
support. The set consists of SR-OLSRv2 Router Tuples: support. The set consists of SR-OLSRv2 Router Tuples:
(SR_OLSR_addr, SR_OLSR_valid_time) (SR_OLSR_addr, SR_OLSR_valid_time)
skipping to change at page 10, line 21 skipping to change at page 10, line 44
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 messages are generated according to the Section 15.1 of HELLO messages are generated according to the Section 15.1 of
[RFC7181]. [RFC7181].
TC message are generated according to the Section 16.1 of [RFC7181]. TC message are generated according to the Section 16.1 of [RFC7181].
As least one TC message MUST be generated by an MP-OLSRv2 Routing As least one TC message MUST be generated by an MP-OLSRv2 Routing
Process during SR_TC_INTERVAL. Process during SR_TC_INTERVAL. Please note that the TC message
generation based on SR_TC_INTERVAL does not replace the ordinary TC
message generation specified in [RFC7181] and does not carry any
address. This is due to the fact that not all routers will generate
TC messages based on OLSRv2. The TC generation based on
SR_TC_INTERVAL serves for those routers to advertise SOURCE_ROUTE TLV
so that the other routers can be aware of the source-route enabled
routers so as to be used as destinations of multipath routing. The
SR_TC_INTERVAL is set to a longer value than TC_INTERVAL.
For both TC and HELLO messages, a single Message TLV with Type := For both TC and HELLO messages, a single Message TLV with Type :=
SOURCE_ROUTE MUST be added to the message. 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 is a Message TLV For every HELLO or TC message received, if there is a Message TLV
skipping to change at page 11, line 14 skipping to change at page 11, line 45
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 source routing header need to be forwarded using
multiple paths (for example, based on the information of DiffServ multiple paths (for example, based on the information of DiffServ
Code Point [RFC2474]), the MP-OLSRv2 routing process will try to find Code Point [RFC2474]), the MP-OLSRv2 routing process will try to find
the Multi-path Routing Tuple where: the Multi-path Routing Tuple where:
o MR_dest_addr = destination of the datagram o MR_dest_addr = destination of the datagram
If no matching Multi-path Routing Tuple is found, the multi-path If no matching Multi-path Routing Tuple is found and the Multi-path
algorithm defined in Section 8.5 is invoked, to calculate the Multi- Routing Set is maintained proactively, it indicates that there is no
path Routing Tuple to the destination. If the calculation does not route available to the desired destination. The datagram is
return any Multi-path Routing Tuple, the following steps are aborted discarded.
and the datagram is forwarded following OLSRv2 routing process.
The Path Tuples of the Multi-path Routing Tuple obtained are applied If no matching Multi-path Routing Tuple is found and the Multi-path
to the datagrams using Round-robin scheduling. For example, they are Routing Set is maintained reactively, the multi-path algorithm
2 path tuples (Path-1, Path-2) for destination router D. A series of defined in Section 8.5 is invoked, to calculate the Multi-path
datagrams (Packet-1, Packet-2, Packet-3, ... etc.) are to be sent Routing Tuple to the destination. If the calculation does not return
router D. Path-1 is then chosen for Packet-1, Path-2 for Packet-2, any Multi-path Routing Tuple, the following steps are aborted and the
Path-1 for Packet 3, etc. datagram is forwarded following OLSRv2 routing process.
If a matching Multi-path Routing Tuple is obtained, the Path Tuples
of the Multi-path Routing Tuple 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 the source routing header. For IPv6 added to the datagram header as the source routing header. For IPv6
networks, strict source routing is used, thus all the intermediate networks, strict source routing is used, thus all the intermediate
routers in the path are stored in the source routing header following routers in the path are stored in the source routing header following
[RFC6554]. For IPv4 networks, loose source routing is used, with [RFC6554]. For IPv4 networks, loose source routing is used, with
following rules: 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.
skipping to change at page 12, line 6 skipping to change at page 12, line 44
indicated by external policies should be avoided. indicated by external policies should be avoided.
8.5. Multi-path Calculation 8.5. Multi-path Calculation
8.5.1. Requirements of Multi-path Calculation 8.5.1. Requirements of Multi-path Calculation
The Multi-path Routing Set maintains the information of multiple The Multi-path Routing Set maintains the information of multiple
paths the the destination. The tuples are generated based on a paths the the destination. The tuples are generated based on a
multi-path algorithm. multi-path algorithm.
A multi-path algorithm is invoked when there is no available Multi- For each path to a destination, the algorithm must provide:
path Routing Tuple to a desired destination to obtain the multiple
paths. 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 SR-OLSRv2 Router Set are considered in the path that exist in 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.
skipping to change at page 13, line 13 skipping to change at page 13, line 49
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 incremental functions named metric 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: 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 who lead to o fe(c) is used to increase metrics of the arcs that lead to
intermediate vertices (i.e., the source and destination are not intermediate vertices of the previous path P[i-1] (with i>1),
considered) of the previous path P[i-1] (with i>1), where c is the where c is the value of the previous metric. The "lead to" means
value of the previous metric. that only one vertex of the arc belongs to the previous path
P[i-1], while the the other vertex is not. The "intermediate"
means that the source and destination vertices are not considered.
Considering 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
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
intermediate vetex of path P[i], and B is not part of P[i]. B--D is
unchanged.
B
/ \
/ \
/ \
S---------A-----------D
Figure 1
It is possible to choose different fp and fe to get link-disjoint It is possible to choose different fp and fe to get link-disjoint
paths or node-disjoint paths as desired. A recommendation of paths or node-disjoint paths as desired. A recommendation of
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 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 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 Multi-path Dijkstra Algorithm is illustrated in A simple example of Multi-path Dijkstra Algorithm is illustrated in
Appendix A. Appendix A.
8.6. Datagram Forwarding 8.6. Multi-path Routing Set Updates
The Multi-path Routing Set MUST be updated when the Local Information
Base, the Neighborhood Information Base, or the Topology Information
Base indicate a change (including of any potentially used outgoing
neighbor metric values) of the known symmetric links and/or attached
networks in the MANET, hence changing the Topology Graph, as
described in section 17.7 of [RFC7181]. How the Multi-path Routing
Set is updated depends on the set is maintained reactively or
proactively:
o In reactive mode, all the tuples in the Multi-path Routing Set are
removed.
o In proactive mode, the route to all the destinations are updated
according to Section 8.5.
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 [RFC0791].
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]. 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
skipping to change at page 14, line 22 skipping to change at page 15, line 45
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 maximum number of hops.
o CUTOFF_RATIO := 1.5. It MUST be strictly greater than 1. o CUTOFF_RATIO := 1.5. It MUST be strictly greater than 1.
o SR_TC_INTERVAL := 10 x TC_INTERVAL. It SHOULD be significantly o SR_TC_INTERVAL := 10 x TC_INTERVAL. It SHOULD be significantly
greater than TC_INTERVAL to reduce unnecessary TC message greater than TC_INTERVAL to reduce unnecessary TC message
generations. generations.
o SR_OLSR_HOLD_TIME := 3 x SR_TC_INTERVAL o SR_OLSR_HOLD_TIME := 3 x SR_TC_INTERVAL. It MUST be greater than
SR_TC_INTERVAL.
If Multi-path Dijkstra Algorithm is applied: If Multi-path 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, 3 cases are possible:
skipping to change at page 17, line 5 skipping to change at page 18, line 26
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]. Section 5.1 of [RFC6554] and [RFC5095].
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.
12.1. Expert Review: Evaluation Guidlines 12.1. Expert Review: Evaluation Guidelines
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]. consideration as are specified by [RFC5444].
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.
skipping to change at page 18, line 45 skipping to change at page 20, line 19
"Multipath optimized link state routing for mobile ad hoc "Multipath optimized link state routing for mobile ad hoc
networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47, networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47,
January, 2011. 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 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]
Rogge, H. and E. Baccelli, "Packet Sequence Number based
directional airtime metric for OLSRv2",
draft-ietf-manet-olsrv2-dat-metric-12 (work in progress),
December 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-01 (work in (OLSRv2)", draft-ietf-manet-olsrv2-sec-threats-02 (work in
progress), November 2015. progress), May 2016.
[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 44 skipping to change at page 21, line 13
[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 [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>. <http://www.rfc-editor.org/info/rfc7722>.
[RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric
Based on Packet Sequence Numbers for Optimized Link State
Routing Version 2 (OLSRv2)", RFC 7779, DOI 10.17487/
RFC7779, April 2016,
<http://www.rfc-editor.org/info/rfc7779>.
[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 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 1 Figure 2
The capital letters are name of routers. An arbitrary metric with The capital letters are name of routers. An arbitrary metric with
value between 1 and 3 is used. The initial metrics of all the links value between 1 and 3 is used. The initial metrics of all the links
are indicated in the parenthesis. The incremental functions fp(c)=4c are indicated in the parenthesis. The incremental functions fp(c)=4c
and fe(c)=2c are used in this example. Two paths from router S to and fe(c)=2c are used in this example. Two paths from router S to
router D are demanded. 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. fe is applied to increase the metric of the link
A-B and A-C. Figure 2 shows the link metrics after the punishment. A-B and A-C. Figure 3 shows the link metrics after the punishment.
.-----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 2 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 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 3, two paths from node S to For example, given the topology in Figure 4, two paths from node S to
D are desired. On the top of the figure, there is a high cost path D are desired. On the top of the figure, there is a high cost path
between S and D. 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--(high cost path)--D, which are obtained will be S--B--D and S--(high cost path)--D, which are
extremely unbalanced. It is undesired because it will cause huge extremely unbalanced. It is undesired because it will cause huge
delay 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.
--high cost path- --high cost path-
/ \ / \
/ \ / \
S----B--------------D S----B--------------D
\ / \ /
\---C-----/ \---C-----/
Figure 3 Figure 4
Authors' Addresses Authors' Addresses
Jiazi Yi Jiazi Yi
LIX, Ecole Polytechnique Ecole Polytechnique
91128 Palaiseau Cedex, 91128 Palaiseau Cedex,
France France
Phone: +33 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) 240 683 050 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. 31 change blocks. 
80 lines changed or deleted 149 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/