draft-ietf-manet-olsrv2-multipath-03.txt   draft-ietf-manet-olsrv2-multipath-04.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: November 27, 2015 University of Nantes Expires: January 1, 2016 University of Nantes
May 26, 2015 June 30, 2015
Multi-path Extension for the Optimized Link State Routing Protocol Multi-path Extension for the Optimized Link State Routing Protocol
version 2 (OLSRv2) version 2 (OLSRv2)
draft-ietf-manet-olsrv2-multipath-03 draft-ietf-manet-olsrv2-multipath-04
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 November 27, 2015. This Internet-Draft will expire on January 1, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 31 skipping to change at page 2, line 31
7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 9 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 . . . . . . . . . . . . . 10
8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10 8.3. Datagram Processing at the MP-OLSRv2 Originator . . . . . 10
8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 11 8.4. Multi-path Dijkstra Algorithm . . . . . . . . . . . . . . 11
8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 12 8.5. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 12
9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13 9. Configuration Parameters . . . . . . . . . . . . . . . . . . . 13
10. Implementation Status . . . . . . . . . . . . . . . . . . . . 13 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 14
10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 14 10.1. Multi-path extension based on nOLSRv2 . . . . . . . . . . 14
10.2. Multi-path extension based on olsrd . . . . . . . . . . . 14 10.2. Multi-path extension based on olsrd . . . . . . . . . . . 14
10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 15 10.3. Multi-path extension based on umOLSR . . . . . . . . . . . 15
11. Security Considerations . . . . . . . . . . . . . . . . . . . 15 11. Security Considerations . . . . . . . . . . . . . . . . . . . 15
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
12.1. HELLO Message-Type-Specific TLV Type Registries . . . . . 15
12.2. TC Message-Type-Specific TLV Type Registries . . . . . . . 16
13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16
14.1. Normative References . . . . . . . . . . . . . . . . . . . 16 14.1. Normative References . . . . . . . . . . . . . . . . . . . 16
14.2. Informative References . . . . . . . . . . . . . . . . . . 17 14.2. Informative References . . . . . . . . . . . . . . . . . . 17
Appendix A. An example of Multi-path Dijkstra Algorithm . . . . . 18 Appendix A. Examples of Multi-path Dijkstra Algorithm . . . . . . 18
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19
1. Introduction 1. Introduction
The Optimized Link State Routing Protocol version 2 (OLSRv2) The Optimized Link State Routing Protocol version 2 (OLSRv2)
[RFC7181] is a proactive link state protocol designed for use in [RFC7181] is a proactive link state protocol designed for use in
mobile ad hoc networks (MANETs). It generates routing messages mobile ad hoc networks (MANETs). It generates routing messages
periodically to create and maintain a Routing Set, which contains periodically to create and maintain a Routing Set, which contains
routing information to all the possible destinations in the routing routing information to all the possible destinations in the routing
domain. For each destination, there exists a unique Routing Tuple, domain. For each destination, there exists a unique Routing Tuple,
which indicates the next hop to reach the destination. which indicates the next hop to reach the destination.
This document specifies an extension of the OLSRv2 protocol This document specifies an extension of the OLSRv2 protocol
[RFC7181], to provide multiple disjoint paths for a source- [RFC7181], to provide multiple disjoint paths when appropriate for a
destination pair. Because of the characteristics of MANETs source-destination pair. Because of the characteristics of MANETs
[RFC2501], especially the dynamic topology, having multiple paths is [RFC2501], especially the dynamic topology, having multiple paths is
helpful for increasing network throughput, improving forwarding helpful for increasing network throughput, improving forwarding
reliability and load balancing. reliability and load balancing.
The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses The Multi-path OLSRv2 (MP-OLSRv2) specified in this document uses
multi-path Dijkstra algorithm by default to explore multiple disjoint multi-path Dijkstra algorithm by default to explore multiple disjoint
paths from a source router to a destination router based on the paths from a source router to a destination router based on the
topology information obtained through OLSRv2, and forward the topology information obtained through OLSRv2, and forward the
datagrams in a load-balancing manner using source routing. MP-OLSRv2 datagrams in a load-balancing manner using source routing. MP-OLSRv2
is designed to be interoperable with OLSRv2. is designed to be interoperable with OLSRv2.
skipping to change at page 6, line 13 skipping to change at page 6, line 13
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 DiifServ Code
Point [RFC2474]. Point [RFC2474].
Compared to OLSRv2, this extension does not introduce new message Compared to OLSRv2, this extension does not introduce new message
type in the air. Two new message TLV types (one for HELLO message type in the air. A new Message TLV type is introduced to identify
and one for TC message) are introduced to identify the routers that the routers that support forwarding based on source route header. It
support forwarding based on source route header. It is interoperable is interoperable with OLSRv2 implementations that do not have this
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.
Depending on the IP version used, the source routing header is Depending on the IP version used, the source routing header is
formatted according to [RFC0791] or [RFC6554]. formatted according to [RFC0791] or [RFC6554].
4. Protocol Overview and Functioning 4. Protocol Overview and Functioning
This specification requires OLSRv2 [RFC7181] to: This specification requires OLSRv2 [RFC7181] to:
o Identify all the reachable routers in the network. o Identify all the reachable routers in the network.
o Identify a sufficient subset of links in the networks, so that o Identify a sufficient subset of links in the networks, so that
routes can be calculated to all reachable destinations. routes can be calculated to all reachable destinations.
o Provide a Routing Set containing shortest routes from this router o Provide a Routing Set containing shortest routes from this router
to all destinations. to all destinations.
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
datagram to be sent from the source to the destination, and there is datagram to be sent from the source to the destination, and there is
no available routing tuple in the Multi-path Routing Set. The multi- no available routing tuple in the Multi-path Routing Set. The multi-
path Dijkstra algorithm can generate multiple disjoint paths from a path Dijkstra algorithm can generate multiple disjoint paths from a
source to a destination, and such information is kept in Multi-path source to a destination, and such information is kept in Multi-path
Routing Set. Routing Set.
skipping to change at page 8, line 8 skipping to change at page 8, line 8
This extension employs the routing control messages HELLO and TC This extension employs the routing control messages HELLO and TC
(Topology Control) as defined in OLSRv2 [RFC7181]. To support source (Topology Control) as defined in OLSRv2 [RFC7181]. To support source
routing, a source routing header is added to each datagram routed by routing, a source routing header is added to each datagram routed by
this extension. Depending on the IP version used, the source routing this extension. Depending on the IP version used, the source routing
header is defined in following of this section. header is defined in following of this section.
6.1. HELLO and TC messages 6.1. HELLO and TC messages
HELLO and TC messages used by MP-OLSRv2 Routing Process share the HELLO and TC messages used by MP-OLSRv2 Routing Process share the
same format as defined in [RFC7181]. In addition, two new Message same format as defined in [RFC7181]. In addition, a new Message TLV
TLV types are 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
types are introduced for the interoperability between OLSRv2 and MP- type is introduced for the interoperability between OLSRv2 and MP-
OLSRv2: only the routers supporting source-route forwarding can be OLSRv2: only the routers supporting source-route forwarding can be
used in the source routing header of a datagram, because adding an used in the source routing header of a datagram, because adding an
router that does not understand the source routing header will cause router that does not understand the source routing header will cause
routing failure. routing failure.
6.1.1. SR_OLSRv2 TLV 6.1.1. SR_OLSRv2 TLV
An SR_OLSRv2 TLV is a Message TLV that signals the message is SR_OLSRv2 TLV is a Message TLV that signals the message is generated
generated by a router that supports source-route forwarding. It can by a router that supports source-route forwarding. It can be an MP-
be an MP-OLSRv2 Routing Process, or an OLSRv2 Routing Process that OLSRv2 Routing Process, or an OLSRv2 Routing Process that support
support source-route forwarding. The SR_OLSRv2 TLV does not include source-route forwarding. The SR_OLSRv2 TLV does not include any
any value. value.
Every HELLO or TC message generated by MP-OLSRv2 Routing Process MUST Every HELLO or TC message generated by a MP-OLSRv2 Routing Process
have one SR_OLSRv2 TLV. MUST have one SR_OLSRv2 TLV.
Every HELLO or TC message generate by OLSRv2 Routing Process MAY have Every HELLO or TC message generate by a OLSRv2 Routing Process MAY
one SR_OLSRv2 TLV, if the OLSRv2 Routing Process supports source- have one SR_OLSRv2 TLV, if the OLSRv2 Routing Process supports
route forwarding, and is willing to join the source route generated source-route forwarding, and is willing to join the source route
by other MP-OLSRv2 Routing Processes. The existence of SR_OLSRv2 TLV generated by other MP-OLSRv2 Routing Processes. The existence of
MUST be consistent for a specific OLSRv2 Routing Process, i.e., SR_OLSRv2 TLV MUST be consistent for a specific OLSRv2 Routing
either it adds SR_OLSRv2 TLV to all its HELLO/TC messages, or it does Process, i.e., either it adds SR_OLSRv2 TLV to all its HELLO/TC
not add SR_OLSRv2 TLV to any HELLO/TC message. messages, or it does not add SR_OLSRv2 TLV to any HELLO/TC message.
6.2. Datagram 6.2. Datagram
6.2.1. Source Routing Header in IPv4 6.2.1. Source Routing Header in IPv4
In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs In IPv4 [RFC0791] networks, the MP-OLSRv2 routing process employs
loose source routing header, as defined in [RFC0791]. It exists as loose source routing header, as defined in [RFC0791]. It exists as
an option header, with option class 0, and option number 3. an option header, with option class 0, and option number 3.
The source route information is kept in the "route data" field of the The source route information is kept in the "route data" field of the
skipping to change at page 10, line 28 skipping to change at page 10, line 28
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 and TC messages are generated according to the section 15.1 or
section 16.1 of [RFC7181]. section 16.1 of [RFC7181].
A single Message-Type-Specific TLV with Type := SR_OLSRv2 MUST be A single Message TLV with Type := SR_OLSRv2 MUST be added to the
added to the message. message.
8.2. HELLO and TC Message Processing 8.2. HELLO and TC Message Processing
HELLO and TC messages are processed according to the section 15.3 and HELLO and TC messages are processed according to the section 15.3 and
16.3 of [RFC7181]. 16.3 of [RFC7181].
For every HELLO or TC message received, if there exists a TLV with For every HELLO or TC message received, if there exists a Message TLV
Type := SR_OLSRv2, create or update (if the tuple exists already) the with Type := SR_OLSRv2, create or update (if the tuple exists
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. and set the SR_OLSR_valid_time := current_time + SR_OLSR_HOLD_TIME.
8.3. Datagram Processing at the MP-OLSRv2 Originator 8.3. Datagram Processing at the MP-OLSRv2 Originator
When the MP-OLSRv2 routing process receives a datagram from upper When the MP-OLSRv2 routing process receives a datagram from upper
layers or interfaces connecting other routing domains, find the layers or interfaces connecting other routing domains, find the
Multi-path Routing Tuple where: Multi-path Routing Tuple where:
skipping to change at page 11, line 34 skipping to change at page 11, line 34
willingness) are preferred. willingness) are preferred.
o The routers that are considered not appropriate for forwarding o The routers that are considered not appropriate for forwarding
indicated by external policies should be avoided. indicated by external policies should be avoided.
8.4. Multi-path Dijkstra Algorithm 8.4. Multi-path Dijkstra Algorithm
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 d to obtain the multiple
paths. This section introduces Multi-path Dijkstra Algorithm as a paths. This section introduces Multi-path Dijkstra Algorithm as a
default mechanism. The use of other algorithms is not prohibited, as default mechanism. It tries to obtain disjoint paths when
long as they can provide a full path from the source to the appropriate, but does not guarantee strict disjoint paths. The
destination router. Using different multi-path algorithms will not rationale is explained in Appendix A.
impact the interoperability.
The use of other algorithms is not prohibited, as long as they can
provide a full path from the source to the destination router. 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 Pi to the destination d. Based on i to look for the shortest path Pi to the destination d. Based on
Dijkstra algorithm, the main modification consists in adding two cost Dijkstra algorithm, the main modification consists in adding two cost
functions namely incremental functions fp and fe in order to prevent functions namely incremental functions fp and fe in order to prevent
the next steps to use similar path. fp is used to increase costs of the next steps to use similar path. fp is used to increase costs of
arcs belonging to the previously path Pi (or which opposite arcs arcs belonging to the previously path Pi (or which opposite arcs
belong to it). This encourages future paths to use different arcs belong to it). This encourages future paths to use different arcs
but not different vertices. fe is used to increase costs of the arcs but not different vertices. fe is used to increase costs of the arcs
who lead to vertices of the previous path Pi. It is possible to who lead to vertices of the previous path Pi. It is possible to
skipping to change at page 14, line 30 skipping to change at page 14, line 36
Until April 2014, there are 3 open source implementations of the Until April 2014, there are 3 open source implementations of the
protocol specified in this document, for both testbed and simulation protocol specified in this document, for both testbed and simulation
use. use.
10.1. Multi-path extension based on nOLSRv2 10.1. Multi-path extension based on nOLSRv2
The implementation is conducted by University of Nantes, France, and The implementation is conducted by University of Nantes, France, and
is based on Niigata University's nOLSRv2 implementation. It is an is based on Niigata University's nOLSRv2 implementation. It is an
open source implementation. The code is available at open source implementation. The code is available at
https://github.com/yijiazi/mpolsr_qualnet and
http://jiaziyi.com/index.php/research-projects/mp-olsr . http://jiaziyi.com/index.php/research-projects/mp-olsr .
It can be used for Qualnet simulations, and be exported to run in It can be used for Qualnet simulations, and be exported to run in
testbed. All the specification is implemented in this testbed. All the specification is implemented in this
implementation. implementation.
Implementation experience and test data can be found at [ADHOC11]. Implementation experience and test data can be found at [ADHOC11].
10.2. Multi-path extension based on olsrd 10.2. Multi-path extension based on olsrd
The implementation is conducted under SEREADMO (Securite des Reseaux The implementation is conducted under SEREADMO (Securite des Reseaux
Ad Hoc & Mojette) project, and supported by French research agency Ad Hoc & Mojette) project, and supported by French research agency
(RNRT2803). It is based on olsrd (http://www.olsr.org/) (RNRT2803). It is based on olsrd (http://www.olsr.org/)
implementation, and is open sourced. The code is available at implementation, and is open sourced. The code is available at
https://github.com/yijiazi/mpolsr_testbed and
http://jiaziyi.com/index.php/research-projects/sereadmo . http://jiaziyi.com/index.php/research-projects/sereadmo .
The implementation is for testing the specification in the field. The implementation is for testing the specification in the field.
All the specification is implemented in this implementation. All the specification is implemented in this implementation.
Implementation experience and test data can be found at [ADHOC11]. Implementation experience and test data can be found at [ADHOC11].
10.3. Multi-path extension based on umOLSR 10.3. Multi-path extension based on umOLSR
The implementation is conducted by University of Nantes, France, and The implementation is conducted by University of Nantes, France, and
is based on um-olsr implementation is based on um-olsr implementation
(http://masimum.inf.um.es/fjrm/development/um-olsr/). The code is (http://masimum.inf.um.es/fjrm/development/um-olsr/). The code is
available at http://jiaziyi.com/index.php/research-projects/mp-olsr available at https://github.com/yijiazi/mpolsr_ns2 and
under GNU GPL license. http://jiaziyi.com/index.php/research-projects/mp-olsr under GNU GPL
license.
The implementation is just for network simulation for NS2 network The implementation is just 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
skipping to change at page 15, line 42 skipping to change at page 15, line 48
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]. To make sure that the
influence is limited to the OLSRv2/MP-OLSRv2 routing domain, the influence is limited to the OLSRv2/MP-OLSRv2 routing domain, the
source routing header MUST be used only in the current routing source routing header MUST be used only in the current routing
domain. domain.
12. IANA Considerations 12. IANA Considerations
This specification defines two Message TLV Types, which must be This specification defines one Message TLV Type, which must be
allocated from the Message TLV Types repository of [RFC5444]. allocated from the Message TLV Types repository of [RFC5444].
12.1. HELLO Message-Type-Specific TLV Type Registries IANA is requested to create a registry for Message TLV, in accordance
with Section 6.2 of [RFC5444], and with initial assignments and
IANA is requested to create a registry for Message-Type-Specific allocation policies as specified in Table 1.
Message TLV for HELLO messages, in accordance with Section 6.2.1 of
[RFC5444], and with initial assignments and allocation policies as
specified in Table 1.
+---------+-------------+-------------------+
| Type | Description | Allocation Policy |
+---------+-------------+-------------------+
| 129 | SR_OLSRv2 | |
| 130-223 | Unassigned | Expert Review |
+---------+-------------+-------------------+
Table 1: HELLO Message-Type-specific Message TLV Types
12.2. TC Message-Type-Specific TLV Type Registries
IANA is requested to create a registry for Message-Type-Specific
Message TLV for TC messages, in accordance with Section 6.2.1 of
[RFC5444], and with initial assignments and allocation policies as
specified in Table 2.
+---------+-------------+-------------------+ +--------+-----------+---------------------------------+------------+
| Type | Description | Allocation Policy | | Type | Name | Description | Allocation |
+---------+-------------+-------------------+ | | | | Policy |
| 128 | SR_OLSRv2 | | +--------+-----------+---------------------------------+------------+
| 129-223 | Unassigned | Expert Review | | 9 | SR_OLSRv2 | The originator of the message | |
+---------+-------------+-------------------+ | | | supports source routing | |
| 10-223 | | Unassigned | Expert |
| | | | Review |
+--------+-----------+---------------------------------+------------+
Table 2: TC Message-Type-specific Message TLV Types Table 1: Message TLV Types
13. Acknowledgments 13. Acknowledgments
The authors would like to thank Sylvain David, Asmaa Adnane, Eddy The authors would like to thank Sylvain David, Asmaa Adnane, Eddy
Cizeron, Salima Hamma, Pascal Lesage and Xavier Lecourtier for their Cizeron, Salima Hamma, Pascal Lesage and Xavier Lecourtier for their
efforts in developing, implementing and testing the specifications. efforts in developing, implementing and testing the specifications.
The authors also appreciate valuable comments and discussions from The authors also appreciate valuable comments and discussions from
Thomas Clausen, Ulrich Herberg, Justin Dean, Geoff Ladwig and Henning Thomas Clausen, Ulrich Herberg, Justin Dean, Geoff Ladwig and Henning
Rogge. Rogge.
skipping to change at page 18, line 30 skipping to change at page 18, line 21
[RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", RFC 6982, Code: The Implementation Status Section", RFC 6982,
July 2013. July 2013.
[WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein, [WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein,
"Simulation and performance analysis of MP-OLSR for mobile "Simulation and performance analysis of MP-OLSR for mobile
ad hoc networks", In Proceeding of IEEE Wireless ad hoc networks", In Proceeding of IEEE Wireless
Communications and Networking Conference, 2008. Communications and Networking Conference, 2008.
Appendix A. An example of Multi-path Dijkstra Algorithm Appendix A. Examples of Multi-path Dijkstra Algorithm
This appendix gives an example of multi-path Dijkstra algorithm. The This appendix gives two examples of multi-path Dijkstra algorithm.
network topology is depicted in Figure 1.
A network topology is depicted in Figure 1.
.-----2-----. .-----2-----.
/ / \ \ / / \ \
/ / \ \ / / \ \
1 / \ 5 1 / \ 5
\ / \ / \ / \ /
\ / \ / \ / \ /
3-----------4 3-----------4
Figure 1: Network Topology for the on-demand example Figure 1
The initial cost of all the links is set to 1. The incremental The initial cost of all the links is set to 1. The incremental
functions fp and fe are defined as fp(c)=4c and fe(c)=2c in this functions fp and fe are defined as fp(c)=4c and fe(c)=2c in this
example. Two routes from node 1 to node 5 are demanded. example. Two paths from node 1 to node 5 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 1->2->5
with cost 2 is obtained. with cost 2 is obtained.
The incremental function fp is applied to increase the cost of the The incremental function fp is applied to increase the cost of the
link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of link 1-2 and 2-5, from 1 to 4. fe is applied to increase the cost of
the link 1-3, 2-3, 2-4, 4-5, from 1 to 2. the link 1-3, 2-3, 2-4, 4-5, from 1 to 2.
On the second run of the Dijkstra algorithm, the second path On the second run of the Dijkstra algorithm, the second path
1->3->4->5 with cost 5 is obtained. 1->3->4->5 with cost 5 is obtained.
As mentioned in Section 8.4, the Multi-path Dijkstra Algorithm does
not guarantee strict disjoint path to avoid choosing inferior paths.
For example, given the topology in Figure 2, two paths from node S to
D are desired.
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
unbalanced. It is undesired because it will cause huge delay
variance between the paths. By using the Multi-path Dijkstra
algorithm, which is based on the punishing scheme, S--B--D and
S--B--C--D will be obtained.
---50 hops-------
/ \
/ \
S----B--------------D
\ /
\---C-----/
Figure 2
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
URI: http://www.jiaziyi.com/ URI: http://www.jiaziyi.com/
 End of changes. 28 change blocks. 
79 lines changed or deleted 89 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/