Internet Engineering Task Force A. Szwabe
Internet-Draft A. Nowak, Ed.
Intended status: Experimental Poznan University of Technology
Expires: November 3, 2011 E. Baccelli
INRIA
J. Yi
B. Parrein
Nantes University
May 2, 2011
Multi-path for Optimized Link State Routing Protocol version 2
draft-szwabe-manet-multipath-olsrv2-02
Abstract
This document specifies an extension of the OLSRv2 protocol providing
methods to compute multiple paths for each destination, when such
paths are available.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. This document may not be modified,
and derivative works of it may not be created, and it may not be
published except as an Internet-Draft.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 3, 2011.
Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
Szwabe, et al. Expires November 3, 2011 [Page 1]
Internet-Draft Multi-path for OLSRv2 May 2011
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 3
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 4
5. Proactive Multi-path Computation with OLSRv2 . . . . . . . . . 4
5.1. Optimization using MPR Selection . . . . . . . . . . . . . 5
6. On-demand Multi-path Computation with OLSRv2 . . . . . . . . . 5
6.1. Route Recovery Mechnanism . . . . . . . . . . . . . . . . 7
7. Loop Detection Mechanisms . . . . . . . . . . . . . . . . . . 7
8. Security Considerations . . . . . . . . . . . . . . . . . . . 8
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9
11.1. Normative References . . . . . . . . . . . . . . . . . . . 9
11.2. Informative References . . . . . . . . . . . . . . . . . . 9
Appendix A. Example of Proactive Multi-path Algorithm
Execution . . . . . . . . . . . . . . . . . . . . . . 10
Appendix B. Example of on-demand Multi-path Execution . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13
Szwabe, et al. Expires November 3, 2011 [Page 2]
Internet-Draft Multi-path for OLSRv2 May 2011
1. Introduction
This document specifies a lightweight extension of the OLSRv2
protocol [I-D.ietf-manet-olsrv2], providing multiple paths for each
destination, when such paths are available.
Multi-path routing increases reliability by detecting the
availability of redundant paths. OLSRv2, in its basic specification,
does not provide multiple routes for a given destination. On the
other hand, the protocol provides every router with enough
information to compute multiple routes to any specific destination,
if available.
Information about multiple paths per source-destination pair enables
more successful end-to-end transmissions in a frequently changing
network environment (e.g. in the case of a sudden breakdown of a
relaying router), and favors throughput maximization in the case when
multiple parallel transmissions without interferences (i.e.,
appropriately distinct to each other) enable bypassing a network
capacity bottleneck ([GNT06], [SS08], [SM09]).
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119].
All terms introduced in [RFC6130], including "interface", "network
address", "1-hop neighbor", "symmetric 1-hop neighbor" are to be
interpreted as described there.
All terms introduced in [I-D.ietf-manet-olsrv2], including the terms
"Router", "Routing Tuple", "Routing Set", "Network Topology Graph"
are to be interpreted as described therein.
3. Applicability
The extension specified in this document is compliant with any OLSRv2
implementation, and provides information about multiple paths per
source-destination pair (when they are available), and such without
requiring signaling other than that provided by the standard OLSRv2
protocol.
While multi-path routing may increase throughput and end-to-end
transmission reliability, it may also increase the chances of packet
Szwabe, et al. Expires November 3, 2011 [Page 3]
Internet-Draft Multi-path for OLSRv2 May 2011
forwarding loops. It is thus recommended to use this specification
jointly with a routing loop avoidance mechanism, such as the ones
described in Section 7.
4. Protocol Overview and Functioning
This specification provides two modes of operation. In the proactive
mode, available redundant paths are systematically precomputed, while
in the on-demand mode available redundant paths are computed on the
go, as needed. routers in the network MUST all operate the same mode.
The following sections specify the functionning of each mode.
5. Proactive Multi-path Computation with OLSRv2
In this mode, available redundant paths are systematically
precomputed, preserving the proactive nature of the standard (i.e.
single-path) OLSRv2. Each router identifies all the possible next-
hops through which there exists a good enough path to a given
destination.
Instead of running the Dijkstra's shortest path algorithm with a
computing router as the origin of every route (as it is in the case
of single-path OLSRv2), the network-based multi-path algorithm
examines all the neighbors of the computing router as potential next-
hops on the route to a given destination. More precisely, all the
remaining neighbors (i.e., all except the examined one) are
temporarily 'removed' from the topology graph together with their
adjacent links, and the shortest path algorithm is executed with the
examined neighbor as a origin. According to the proposed algorithm,
the computing router chooses only these neighbors as a next-hop for
the given destination router, which are able to determine the
remaining part of the route to the destination in a way that does not
require backward transmission [SM09].
The proactive multi-path route calculation algorithm may be described
as follows [SMN+10]:
1. For each neighbor of router m do:
A. Delete all neighbors of router m with their adjacent links,
except of the selected one.
B. Run standard single-path Dijkstra's algorithm for the
obtained graph in order to determine Routing Tuples, with the
selected neighbor as the next-hop on the route.
Szwabe, et al. Expires November 3, 2011 [Page 4]
Internet-Draft Multi-path for OLSRv2 May 2011
2. Merge the obtained sets of Routing Tuples of neighboring routers
into the final OLSRv2 Routing Set of router m that allows
multiple entries for a given destination.
As a result of an algorithm execution, the path-computing router
obtains a separate set of Routing Tuples for each neighbor, which can
be easily used to obtain the modified OLSRv2 Routing Set with
multiple entries for a given destination. In contrast to the
standard OLSRv2 specification, for which "Routing Set MUST contain
the shortest paths for all destinations from all local OLSRv2
interfaces using the Network Topology Graph" (see Section 18.2 of
[I-D.ietf-manet-olsrv2]), the Multi-path Extension of OLSRv2 allows
using paths which MAY be longer than the shortest one for a given
source/destination pair. Tables presented in Appendix A contain
routing entries which are compatible with standard OLSRv2 Routing
Tuples, but allows multiple entries with the same destination
addresses.
An example presenting an execution of the multi-path algorithm may be
also found in Appendix A.
5.1. Optimization using MPR Selection
For a further optimization, the set of examined neighbors of a
computing router may be limited to the set of the router's MPRs.
This method is aimed at increasing the route stability as well as the
probability that the choice of next-hops for routes to a given
destination will lead to parallel transmissions without
interferences. Such modification of the Proactive Multi-path
algorithm is especially suitable for networks with dense topologies,
since it allows to avoid undesirable forwarding through multiple
paths sharing the same radio resources. Such extension does not
require introducing any modifications into the structure of OLSRv2
Routing Tuples.
6. On-demand Multi-path Computation with OLSRv2
In this mode, available redundant paths are computed on the go, as
needed. This mode is recommended in networks with a significant
number of long and more occasional flows, and may not be appropriate
for networks with a very dynamic topology, though route recovery and
loop detection schemes may alleviate issues with this mode in dynamic
topologies [YADP10].
The mechanism described in the following is invoked on demand to
reach a destination d. Note that it does not incur any signalling in
addition to standard OLSRv2 signalling. The general principle of
Szwabe, et al. Expires November 3, 2011 [Page 5]
Internet-Draft Multi-path for OLSRv2 May 2011
this mechanism is at step i to look for the shortest path Pi to the
destination d. Based on Dijkstra algorithm, the main modification
consists in adding two cost 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 arcs belonging to the previously path Pi
(or which opposite arcs belong to it). This encourages future paths
to use different arcs but not different vertices. fe is used to
increase costs of the arcs who lead to vertices of the previous path
Pi. Different fp and fe are chosen to get link-disjoint path or
node-disjoint routes as necessary. If id is the identity functions,
3 cases are possible:
o if id=fe<fp paths tend to be arc disjoint;
o if id<fe=fp paths tend to be vertex-disjoint;
o if id<fe<fp paths also tend to be vertex-disjoint, but when is not
possible they tend to be arc disjoint.
The on-demand multi-path route calculation algorithm may be described
as follows to get N distinct paths:
1. For each path 1 to N do:
A. Run Dijkstra algorithm to get the source tree.
B. Get the shortest path Pi for the on-demand destination d.
C. Apply cost functions fp and fe respectively on edges of Pi
and pointing vertices of Pi.
2. Writing the entire route into IP source routing header.
For the special case of more than 10 hops (specially large MANET),
because IP source routing option accepts only a maximum of 9
addresses (in total, 11 nodes including source and destination nodes
= 10 hops), the loose source routing may be used. Table 1 shows an
example of the multi-path source routing table, which provides
multiple routes to the destination.
To compute on-demand multiple paths, another possible solution is
instead of increasing the cost of the arc, the related node is
deleted from the node set in order to get totally node-disjoint
routes. However, in the cases when the nodes are locally sparse i.e
a partition of the MANET, deleting some key nodes might prevent from
finding new route. It is expected that keeping nodes in the routes
calculation process provides more flexibility and better adaptation
to the MANET topology.
Szwabe, et al. Expires November 3, 2011 [Page 6]
Internet-Draft Multi-path for OLSRv2 May 2011
+---+---------------------+----------------------+
| # | Destination address | Source route |
+---+---------------------+----------------------+
| 1 | dest_addr(X) | hop_1(A),hop_2(B)... |
| 2 | dest_addr(X) | hop_1(C),hop_2(D)... |
| 3 | dest_addr(X) | hop_1(E),hop_2(F)... |
| 4 | dest_addr(Y) | hop_1(G),hop_2(H)... |
| 5 | ... | ... |
+---+---------------------+----------------------+
Table 1: Sample on-demand multi-path source Routing Tuples
6.1. Route Recovery Mechnanism
With source routing, the route is defined by the source, and the
intermediate nodes just read the next hop information for the
packet's source routing header. Therefore, when source routing is
used, updated topology information potentially available on
intermediate nodes towards the destination is not used in case of
topology changes. Thus, route recovery mechanisms such as the one
described below is necessary for dynamic scenarios.
For instance, before an intermediate node tries to forward a packet
to the next hop according to the source route, the node may first
checks whether the next hop in the source route is one of its
neighbors (by checking the 1-hop neighbor set). If so, the packet is
forwarded normally. If not, it is possible that the "next hop" is
not available anymore, and the node should thus recompute the route
and forward the packet by using the new route.
This route recovery mechanism does not introduce extra route
discovery procedure or any additional signalling, while effectively
avoid unavailable links.
7. Loop Detection Mechanisms
A loop detection scheme becomes necessary when packets can switch
between multiple paths towards destination. Loop detection can be
provided by auxiliary mechanisms such as for instance:
o Backpressure-based scheduling [SMN+10]- on each router a scheduler
utilizes a multi-path Routing Set jointly with information about
backpressure weights. Traffic of each flow is load-balanced among
the possible relaying routers in a fully dynamic manner, i.e.,
according to the most recent network state information.
Backpressure-based scheduling requires additional queue level
signaling (and introducing corresponding messages) which is beyond
Szwabe, et al. Expires November 3, 2011 [Page 7]
Internet-Draft Multi-path for OLSRv2 May 2011
the scope of this document.
o Source routing [RFC0791]- each of multiple paths is specified in
IP headers as a sequence of relaying OLSRv2 routers' addresses of
packets being forwarded along this path. Each router on the path
forwards the packet according to this data as long as this data is
not outdated due to network topology changes. If used with a
route recovery scheme such as the one described in Section 6.1, a
node should compare the old source route with the new, recomputed
source route (after having performed route recovery). If the new
route contains nodes that were already traversed with the old
route before reaching the recomputing node, a loop is detected.
8. Security Considerations
To be elaborated.
9. IANA Considerations
This memo includes no request to IANA.
This documents specifies only the extension of OLSRv2, without
introducing any new message type. Every IANA request regarding
OLSRv2 protocol is explained in [I-D.ietf-manet-olsrv2] and
[RFC6130].
10. Acknowledgements
This work was partly supported by the grant of Poznan University of
Technology DS 45-083/10 and the European Commission OPNEX STREP (FP7-
224218, http://opnex.eu) for the proactive multi-path routing and
partly by the project SEREADMO of the French research agency
(RNRT2803) for source routing approach.
The authors also want to thank to following people for their input:
o Pawel Misiorek
o Maciej Urbanski
o Thomas Clausen
o Przemyslaw Walkowiak
Szwabe, et al. Expires November 3, 2011 [Page 8]
Internet-Draft Multi-path for OLSRv2 May 2011
o Eddy Cizeron
o Salima Hamma
o Asmaa-Hassiba Adnane
11. References
11.1. Normative References
[I-D.ietf-manet-olsrv2]
Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-11 (work in progress), April 2010.
[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc
Network (MANET) Neighborhood Discovery Protocol (NHDP)",
RFC 6130, April 2011.
11.2. Informative References
[GNT06] Georgiadis, L., Neely, M., and L. Tassiulas, "Resource
allocation and cross-layer control in wireless networks",
In Foundations and Trends in Networking, pages 271-379,
2006.
[SM09] Szwabe, A. and P. Misiorek, "Integration of multi-path
Optimized Link State Protocol with max-weight scheduling",
Proc. of IEEE International Conference on Information and
Multimedia Technology (ICIMT 2009), Jeju Island, Korea,
pages 458-462, 2009.
[SMN+10] Szwabe, A., Misiorek, P., Nowak, A., and J. Marchwicki,
"Implementation of Backpressure-Based Routing Integrated
with Max-Weight Scheduling in a Wireless Multi-hop
Network", Proc. of 3rd IEEE International Workshop on
Wireless and Internet Services (WISe 2010), Denver, USA,
pages 999-1004, 2010.
[SS08] Shakkottai, S. and R. Srikant, "Network Optimization and
Control", In Foundations and Trends in Networking, pages
Szwabe, et al. Expires November 3, 2011 [Page 9]
Internet-Draft Multi-path for OLSRv2 May 2011
1-149, January 2007.
[YADP10] Yi, J., Adnane, A-H., David, S., and B. Parrein,
"Multipath optimized link state routing for mobile ad hoc
networks", In Elsevier Ad Hoc Journal, vol.9, n. 1, 28-47,
January, 2011.
Appendix A. Example of Proactive Multi-path Algorithm Execution
This appendix shows the process of the Routing Set calculation
(performed on the router (1)) in a network of simple topology of 6
routers. The example of a network topology is presented below.
+-----------+----------------------------+
| Router ID | Set of symmetric neighbors |
+-----------+----------------------------+
| (1) | (2), (3), (4) |
| (2) | (1), (3), (5) |
| (3) | (1), (2), (4), (5), (6) |
| (4) | (1), (3), (6) |
| (5) | (2), (3), (6) |
| (6) | (3), (4), (5) |
+-----------+----------------------------+
Table 2: Network topology
5-----6
/ \ / \
/ \ / \
2-----3-----4
\ | /
'---1---'
Figure 1: Network Topology
In the first step, all the neighbors of router (1) except router (2)
are temporary excluded from the topology. Table 3 presents Routing
Tuples obtained as a result of the Dijkstra's shortest path algorithm
execution on the modified topology. Table 4 and Table 5 present the
analogous information for the cases of routers (3) and (4) taken as
investigated Next-hops, respectively. Table 6 presents the final
Routing Set for router (1).
Column names in tables are equivalents of the elements in the OLSRv2
Routing Set (R_dest_addr, R_next_iface_addr, R_local_iface_addr,
Szwabe, et al. Expires November 3, 2011 [Page 10]
Internet-Draft Multi-path for OLSRv2 May 2011
R_dist).
+---+------------------+---------------+-----------------+----------+
| # | Destination | Next-hop | Interface | Distance |
| | address | address | address | |
+---+------------------+---------------+-----------------+----------+
| 1 | (2) | (2) | A | 1 |
| 2 | (5) | (2) | A | 2 |
| 3 | (6) | (2) | A | 3 |
+---+------------------+---------------+-----------------+----------+
Table 3: Routing Tuples for Next-hop (2).
+---+------------------+---------------+-----------------+----------+
| # | Destination | Next-hop | Interface | Distance |
| | address | address | address | |
+---+------------------+---------------+-----------------+----------+
| 1 | (3) | (3) | A | 1 |
| 2 | (5) | (3) | A | 2 |
| 3 | (6) | (3) | A | 2 |
+---+------------------+---------------+-----------------+----------+
Table 4: Routing Tuples for Next-hop (3).
+---+------------------+---------------+-----------------+----------+
| # | Destination | Next-hop | Interface | Distance |
| | address | address | address | |
+---+------------------+---------------+-----------------+----------+
| 1 | (4) | (4) | A | 1 |
| 2 | (5) | (4) | A | 3 |
| 3 | (6) | (4) | A | 2 |
+---+------------------+---------------+-----------------+----------+
Table 5: Routing Tuples for Next-hop (4).
Szwabe, et al. Expires November 3, 2011 [Page 11]
Internet-Draft Multi-path for OLSRv2 May 2011
+---+------------------+---------------+-----------------+----------+
| # | Destination | Next-hop | Interface | Distance |
| | address | address | address | |
+---+------------------+---------------+-----------------+----------+
| 1 | (2) | (2) | A | 1 |
| 2 | (3) | (3) | A | 1 |
| 3 | (4) | (4) | A | 1 |
| 4 | (5) | (2) | A | 2 |
| 5 | (5) | (3) | A | 2 |
| 6 | (5) | (4) | A | 3 |
| 7 | (6) | (3) | A | 2 |
| 8 | (6) | (4) | A | 2 |
| 9 | (6) | (2) | A | 3 |
+---+------------------+---------------+-----------------+----------+
Table 6: Routing Tuples for router (1).
Appendix B. Example of on-demand Multi-path Execution
This appendix gives an example of the on-demand multi-path algorithm,
which includes the source-based Dijkstra multi-path algorithm, route
recovery and loop detection.
Figure 2
+---------+----------------------------+
| Node ID | Set of symmetric neighbors |
+---------+----------------------------+
| (1) | {(2),(3)} |
| (2) | {(1),(3),(4),(5)} |
| (3) | {(1),(2),(4)} |
| (4) | {(2),(3),(5)} |
| (5) | {(2),(4)} |
+---------+----------------------------+
Table 7: Network topology for the on-demand example
.-----2-----.
/ / \ \
/ / \ \
1 / \ 5
\ / \ /
\ / \ /
3-----------4
Szwabe, et al. Expires November 3, 2011 [Page 12]
Internet-Draft Multi-path for OLSRv2 May 2011
Figure 2: Network Topology for the on-demand example
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
example. Two routes from node 1 to node 5 are demanded.
On the first run of the Dijkstra algorithm, the shortest path 1->2->5
is obtained.
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
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
1->3->4->5 is obtained.
Authors' Addresses
Andrzej Szwabe
Poznan University of Technology
5 M. Sklodowskiej-Curie Sq.
60-965 Poznan
Poland
Phone: +48 61 665 3958
Email: Andrzej.Szwabe@put.poznan.pl
Adam Nowak (editor)
Poznan University of Technology
5 M. Sklodowskiej-Curie Sq.
60-965 Poznan
Poland
Phone: +48 61 665 3958
Email: Adam.Nowak@put.poznan.pl
Emmanuel Baccelli
INRIA
Phone: +33-169-335-511
Email: Emmanuel.Baccelli@inria.fr
URI: http://www.emmanuelbaccelli.org/
Szwabe, et al. Expires November 3, 2011 [Page 13]
Internet-Draft Multi-path for OLSRv2 May 2011
Jiazi Yi
Nantes University
IRCCyN lab - IVC team
Polytech'Nantes, rue Christian Pauc, BP50609
44306 Nantes cedex 3
France
Phone: +33 (0) 240 683 050
Email: Jiazi.Yi@polytech.univ-nantes.fr
URI: http://www.jiaziyi.com/
Benoit Parrein
Nantes University
IRCCyN lab - IVC team
Polytech'Nantes, rue Christian Pauc, BP50609
44306 Nantes cedex 3
France
Phone: +33 (0) 240 683 050
Email: Benoit.Parrein@polytech.univ-nantes.fr
URI: http://www.irccyn.ec-nantes.fr
Szwabe, et al. Expires November 3, 2011 [Page 14]