INTERNET-DRAFT Cedric Adjih
IETF MANET Working Group Saadi Boudjit
Expiration: 14 August 2005 Philippe Jacquet
Anis Laouiti
Paul Muhlethaler
INRIA Rocquencourt, France
14 February 2005
Address autoconfiguration in Optimized Link State Routing Protocol
draft-laouiti-manet-olsr-address-autoconf-00.txt
Status of this Memo
This document is an Internet-Draft and is subject to all provisions
of section 3 of RFC 3667. By submitting this Internet-Draft, the
authors certify that any applicable patent or other IPR claims of
which they are aware have been or will be disclosed, and any of which
they become aware will be disclosed, in accordance with RFC 3668.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Copyright Notice
Copyright(C)The Internet Society (2005).
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 1]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
Abstract
One of the MANET protocols which have been recently promoted to
experimental RFC is the OLSR routing protocol[3]. This document aims
at complementing the OLSR routing protocol specifications to handle
autoconfiguration. The corner stone of this autoconfiguration
protocol is an advanced duplicate address detection algorithm. We
propose a comprehensive autoconfiguration scheme whose basic idea is
to avoid conflicts in the 2-hop neighborhood of each node. We have
designed two algorithms to perform this task. These algorithms are
shown to work in any case of multiple conflicts, especially during
network mergers.
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 2]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Duplicate address detection and MAD message description . . . . . 6
5. Duplicate Address Detection mechanism . . . . . . . . . . . . . . 7
5.1. First algorithm . . . . . . . . . . . . . . . . . . . . . . . . 7
5.1.1. First rule . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.1.2. Second rule . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.1.3. Full algorithm . . . . . . . . . . . . . . . . . . . . . . . 7
5.2. Second algorithm . . . . . . . . . . . . . . . . . . . . . . . 9
6. Address assignment . . . . . . . . . . . . . . . . . . . . . . . 11
7. Pool of addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
8. Resolution of a conflict . . . . . . . . . . . . . . . . . . . . 11
9. Security Considerations . . . . . . . . . . . . . . . . . . . . . 11
10. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
12. Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 13
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 3]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
1. Introduction
Mobile Ad hoc NETworks (MANETs) are infrastructure-free, highly
dynamic wireless networks, where central administration or configura-
tion by the user is very difficult. In hardwired networks nodes usu-
ally rely on a centralized server and use a dynamic host configura-
tion protocol, like DHCP[1], to acquire an IP address. Such a solu-
tion cannot be deployed in MANETs due to the unavailability of any
centralized DHCP server. For small scale MANETs, it may be possible
to allocate free IP addresses manually.
However, the procedure becomes impractical for a large-scale or open
system where mobile nodes are free to join and leave. Most of the
autoconfiguration algorithms proposed for ad hoc networks are inde-
pendent of the routing protocols and therefore, generate a signifi-
cant overhead. Using the genuine optimization of the underlying
routing protocol can significantly reduce the autoconfiguration over-
head.
Research on automatic configuration of IP addresses for MANET is rel-
atively less frequent. The IPv6 and ZEROCONF working groups of the
IETF deal with autoconfiguration issues but with a focus on wired
networks. Automatic address allocation is more difficult in a MANET
environment than in wired networks due to instability of links,
mobility of the nodes, the open nature of the mobile ad hoc networks,
and lack of central administration in the general case. Thus per-
forming a DAD (Duplicate Address Detection) generates more complexity
and more overhead in ad hoc networks than in wired networks where
protocols such as DHCP[1] and SAA [2] can be used.
In this document we will describe an autoconfiguration solution for
the OLSR protocol. This solution is based on an efficient Duplicate
Address Detection (DAD) algorithm which takes advantage of the gen-
uine optimization of the OLSR protocol. We actually propose two
solutions to handle multiple address conflicts. They have the same
main basic idea which is to ensure the absence of conflicts in the
2-hop neighborhood of each node.
2. Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [5].
For the OLSR description and terminology, the reader should refer to
the OLSR RFC [3].
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 4]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
3. Overview
Our proposed autoconfiguration algorithm is based on two steps. In
the first step, an IP address is selected by the arriving node and
this latter can join the ad hoc network. Numerous schemes can be
used to select this IP address for instance the node can perform a
random selection; another technique is that a neighbor node selects
this IP address for the arriving node.
After this first step has been performed, the second step can take
place. The aim of this step is to detect potential address duplica-
tions on run. To perform this task a DAD algorithm is started on
this newly configured node. This DAD algorithm allows the newly con-
figured node to state whether the selected address is duplicated or
not in a proactive manner. If such a case occurs, a node can change
its address with respect to some specified criteria.
In such a case a new address can be chosen. The DAD algorithm uses a
special control packet called MAD for ``Multiple Address Declara-
tion''. This control packet includes the node address and a node
identifier. This packet is broadcast in the network, thus all the
network nodes must receive this packet. The duplicate detection uses
the node identifier. If a node receives an MAD message with a dif-
ferent identifier than its own, an address duplication is detected.
To spare the channel bandwidth the MAD packet should be broadcasted
using the MPR flooding.
On the other hand, duplicated addresses may be the origin of MPR
election and flooding corruption, which may induce errors in packet
delivery, particularly the MAD packets. Consequently, we need first
to ensure the MPR election from those conflictual situations. We
propose two algorithms to achieve this task:
1 In first algorithm, we suggest to ignore the MPR mechanism for
the first hop, and relay each originated MAD message by all
the neighbors to the 2-hop neighbors. In this manner possible
address conflict could be detected and resolved. The direct
consequence is that the MPR set will be fixed.
2 In the second one, we propose to modify the OLSR Hello mes-
sages and the MPR election algorithm. The calculation will be
based on the address and the node identifier to guarantee the
uniqueness of the direct neighbors and the 2-hop neighbors.
This leads to a correct MPR set, hence,we are sure that the
MAD messages reach all the nodes.
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 5]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
In the sequel we first present the MAD message used to detect the
address conflict. Then, we introduce the two proposed DAD algorithms
tailored for OLSR protocol. And, finally we give some address
assignment and conflict resolution issues.
4. Duplicate address detection and MAD message description
In order to detect address conflicts, each node diffuses periodically
a special message that we call a MAD for ``Multiple Address Declara-
tion'' to the entire network[5]. This control packet includes the
node addresses and the node identifier. The node identifier is a
sequence of bits of fixed length L which is randomly generated.
Hence we are using the standard idea that the probability of two
nodes having the same node identifier is low, and the probability of
at least one address collision with N nodes, which is the well known
``birthday problem'', can be set arbitrarily low by choosing a large
enough value of L (eight bytes are enough to code the random identi-
fier if we consider a network with a maximum of 10000 nodes [4]).
The MAD message format is depicted in the following figure.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Originator node identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
A node detects an address conflict when it receives an MAD message
having the same address as its own, but with a different identifier.
These situations may happen during network mergers. Actually other
nodes will detect the conflict. These nodes could announce the con-
flict using a special control message. However this approach may
induce broadcast storm since many nodes may announce the conflict and
special care must be taken to avoid this effect. For that reason we
do not recommend this way. An efficient manner to notify the address
duplication to the nodes in conflict, consists in allowing the MAD
packets to reach all the nodes in the network. To save the channel
bandwidth the MAD packets should be broadcasted using the MPR
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 6]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
flooding. Actually, applying OLSR relaying optimization rules as
they are defined, may not be sufficient to ensure diffusion in some
conflictual cases.
5. Duplicate Address Detection mechanism
Duplicate addresses are detected by the periodic exchange of MAD mes-
sages. We propose two different algorithms to ensure the delivery of
these messages to the participants in the network in order to dis-
cover these conflicts. The first one suggests to modify the MPR
flooding rules for MAD messages diffusion. Where in the second one,
we propose to modify the OLSR MPR election, which is done on the
basis of the node identifier and address interface. This guarantee
correct MPR sets, that cover the 2-hop neighbors even in the presence
of duplicate addresses.
5.1. First algorithm
In this first approach we will add rules to the OLSR MPR flooding.
5.1.1. First rule
The property that we will add is actually extremely simple. We
weaken the relaying condition for nodes who are in the 2-hop neigh-
borhood of a node who is sending an MAD message. When these neighbor
nodes receive an MAD message, they must relay the MAD message irre-
spectively of the relaying conditions of the OLSR MPR flooding algo-
rithm. We call this first rule, rule 1.
5.1.2. Second rule
When a node receives an MAD message from a neighbor node with a given
IP address and a given Node-ID, and another MAD message with the same
address but with a different Node-ID, it must relay this latter MAD
message irrespectively of the MPR flooding rules. We call this sec-
ond rule, rule 2.
5.1.3. Full algorithm
Let us recall the assumptions here.
Each node A periodically sends a message M including:
1 The originator address of A, Orig_A, in the OLSR message
header.
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 7]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
2 The message sequence number, mssn, in the OLSR message header.
3 The node identifier ID_A (a string of bits) in the message
itself.
The message is propagated by MPR flooding to the other nodes ; but
for DAD-MPR Flooding, the duplicate table of OLSR is modified, so
that it also includes the node identifier list in the duplicate
tuple. That is, a duplicate tuple, includes the following informa-
tion:
1 The originator address (as in OLSR standard duplicate table).
2 The message sequence number (as in OLSR standard duplicate ta-
ble).
3 The list of node identifiers.
The detailed algorithm for DAD-MPR Flooding is the following:
1 When a node receives a message M from node B with originator
Orig_A, with message sequence number mssn, and with node iden-
tifier ID_A, it performs the following tasks:
1.1 If a duplicate tuple exists with the same originator
Orig_A, the same message sequence number, and ID_A is in
the list of node identifiers, Then, the message is
ignored (it has already been processed). The algorithm
stops here.
1.2 Else one of the following situations occurs :
1.2.1
A duplicate tuple exists with the same originator
Orig_A and the same message sequence number, but
ID_A is not in the list of node identifiers: then, a
conflict is detected (address Orig_A is duplicated).
ID_A is added to the list of node identifiers.
1.2.2
A duplicate tuple exists with the same originator
Orig_A, but with a different message sequence number
and ID_A is not in the list of node identifiers:
then, a conflict is detected (address Orig_A is
duplicated). A duplicate tuple is created with the
originator address, message sequence number and list
of node identifiers containing only ID_A.
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 8]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
1.2.3
No duplicate tuple exists. A new one is created
with the originator address, message sequence number
and list of node identifiers containing only ID_A.
1.3 The MAD messages should be relayed if one or more of the
following rules are met:
1.3.1
The node B is the source of the MAD message i.e. it
has the originator address Orig_A.
1.3.2
B had chosen this current receiving node as an MPR.
1.3.3
One of the conflicting nodes is a neighbor of the
node detecting the duplication. In such a case, the
TTL value of the MAD message showing the conflict is
set to one before its retransmission. This also
applies even if the current node has not been
selected as an MPR by the previous message sender.
5.2. Second algorithm
An issue with the previous approach is that the conflicts at 2-hop
neighbors must be resolved before one can be sure that the MAD mes-
sages are successfully transmitted within the entire network. An
ideal property would be that the MAD messages reach all the nodes in
the network irrespectively of potential address duplications. This
property can be achieved if the MPR flooding continues to work in
presence of address duplication. A solution is then to base the
selection of MPR not on addresses but on node identifiers. With the
assumption that node identifiers are globally unique in the network,
one can be sure that there will not be identifier duplications at two
hops of a given node and thus the selection of MPRs will be correct.
This solution can be simply implemented, the selection of the MPRs
must follow the principle defined in the OLSR protocol except that
the base for the selection must be the node identifiers i.e. the
2-hop coverage must be obtained not on the addresses but on the node
identifiers.
To be able to do so, hello packets must be modified such that the
following information will be given in the hello message :
1 the node identifier of the originator node of the hello mes-
sage,
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 9]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
2 the node identifier of the nodes (actually the node interface
addresses ) advertised in the hello messages. The modified
Hello message format is specified in the following figure.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Htime | Willingness |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Originator node identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Neighbor identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Neighbor identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Neighbor identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Neighbor identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
: :
(etc.)
The drawback of this mechanism is that it introduces a significant extra
overhead.
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 10]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
6. Address assignment
We have two main ways to allocate an address to a newly arriving
node. The first way is to assign this node a random address in the
pool of addresses that can be allocated and then to rely on the DAD
algorithm to discover potential conflicts. The second way is to ask
for the help of a neighbor node. This neighbor will be able to pro-
pose to the newly arriving node a configuration address. Since a
neighbor node must in principle receive the MAD messages of all nodes
in the network, it can maintain a pool of non-affected addresses. A
newly arriving node can choose between these two approaches.
7. Pool of addresses
The pool of addresses could be for local use only. For example, it
could be reserved by the IANA authority for local MANET forwarding (
i.e, those addresses must not be forwarded outside the MANET network,
nor reached from outside). A second possibility consists in relying
on some machines which will announce the prefix to use for address
autoconfiguration for this MANET network. These machines could be
connected to the internet, and act as gateways. In this case, the
addresses may be global addresses, and could be seen from outside.
8. Resolution of a conflict
When two nodes A1 and A2 are configured with the same IP address and
assuming that there is no packet loss, each of these two nodes will
receive the MAD message of the other node. Thus the nodes where the
conflict lies are bound to discover the conflict. A simple rule to
solve this conflict will be: the node in conflict with the smallest
identifier changes its address. Since this node knows via the recep-
tion of the MAD control messages the already assigned addresses, the
new address must be selected at random among the addresses that are
believed to be free.
9. Security Considerations
This memo does not specify any security considerations.
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 11]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
10. Authors' Addresses
The authors are listed in alphabetical order.
Cedric Adjih
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5215
Email: Cedric.Adjih@inria.fr
Saadi Boudjit
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5039
Email: Saadi.Boudjit@inria.fr
Philippe Jacquet
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5263
Email: Philippe.Jacquet@inria.fr
Anis Laouiti
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5088
Email: Anis.Laouiti@inria.fr
Paul Muhlethaler
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
Email: Paul.Muhlethaler@inria.fr
Adjih Boudjit Jacquet Laouiti Muhlethaler [Page 12]
INTERNET-DRAFT Address Autoconfiguration for OLSR 14 February 2005
11. References
[1] R. Droms, Ed.,J. Bound, B. Volz, T. Lemon, C. Perkins, M. Car-
ney, ``Dynamic Host Configuration Protocol for IPv6 (DHCPv6)'',
IETF RFC 3315, July 2003.
[2] S. Thomson, T. Narten, ``IPv6 Stateless Address Autoconfigura-
tion'', IETF RFC 2462, December 1998.
[3] T. Clausen, Ed., P. Jacquet, Ed., Optimized Link State Routing
Protocol. Request for Comments (Experimental) 3626, Internet Engi-
neering Task Force, October 2003.
[4] S.Boudjit, A. Laouiti, P. Muhlethaler, C. Adjih, "Duplicate
address detection and autoconfiguration in OLSR", INRIA Research
Report-5475, Jan 2005.
[5] A. Laouiti, S. Boudjit, P. Minet and C. Adjih, "OLSR for IPv6
networks", Proceedings of Med-Hoc-Net, June 2004,Bodrum, Turkey.
12. Full Copyright Statement
Copyright(C)The Internet Society (2005). This document is subject to
the rights, licenses and restrictions contained in BCP 78, and except
as set forth therein, the author retains all his rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE REPRESENTS OR
IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGI-
NEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFOR-
MATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES
OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.