Internet DRAFT - draft-adjih-manet-autoconf-detect
draft-adjih-manet-autoconf-detect
MANET-AUTOCONF C. Adjih
Internet-Draft INRIA Rocquencourt, France
Expires: April 20, 2006 Pr. Mase
Information and Communication
Network Lab., Niigata University
Oct 17, 2005
Conflict Detection in MANET Autoconf
draft-adjih-manet-autoconf-detect-00
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
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.
This Internet-Draft will expire on April 20, 2006.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
Several wireless ad-hoc routing protocols have been and are being
developped for MANET. However, autoconfiguration of MANET networks
is still an unsettled area, and several methods have been proposed to
perform such a task. One of the mecanisms that may be required for
address autoconfiguration, is the detection of address conflicts.
This is specially true for one of scenarios for MANET autoconf, the
Adjih & Mase Expires April 20, 2006 [Page 1]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
case of the merge of MANET networks.
This document specifies a general protocol for the detecting address
conflicts in a MANET network, and hence addresses a subset of the
requirements of a full MANET address autoconfiguration solution. It
is specified as an independent protocol from the MANET routing
protocol, and the address configuration method, and may be used with
any of them. It aims at conceptual simplicity: essentially, a tree
of the nodes is built, from which all the information from all the
existing nodes is known. Conflicts are detected by the node at root
of the tree, or as inconsistent information on the root of the tree.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Problem statement . . . . . . . . . . . . . . . . . . . . . . 5
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6
4. Protocol Principles . . . . . . . . . . . . . . . . . . . . . 7
5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 8
5.1. Root Election . . . . . . . . . . . . . . . . . . . . . . 9
5.2. Parent Selection, Parent and Subtree Advertizement . . . . 9
5.3. Address Conflict Detection and Notification by the Root . 10
5.4. Root Address Conflict Detection and Notification by
one Node . . . . . . . . . . . . . . . . . . . . . . . . . 11
6. Detailed Specifications . . . . . . . . . . . . . . . . . . . 12
6.1. Message format . . . . . . . . . . . . . . . . . . . . . . 12
7. Optimizations . . . . . . . . . . . . . . . . . . . . . . . . 15
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
9. Security Considerations . . . . . . . . . . . . . . . . . . . 17
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 18
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1. Normative References . . . . . . . . . . . . . . . . . . . 19
11.2. Informative References . . . . . . . . . . . . . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21
Intellectual Property and Copyright Statements . . . . . . . . . . 22
Adjih & Mase Expires April 20, 2006 [Page 2]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
1. Introduction
A mobile ad hoc network is a collection of nodes, which collaborate
to each other without depending on centralized control for enabling
wireless communication among nodes. When two nodes are within direct
transmission range, they communicate directly (one hop wireless
communication) ; and otherwise they communicate using other nodes as
intermediary nodes (multihop wireless communication), where the
intermediary nodes act as routers for forwarding IP datagrams.
Accordingly, routing is a key problem for mobile ad hoc networks and
many routing protocols have been proposed.
In IETF, in the MANET working group has specified the characteristics
of such networks and the design guidelines for MANET routing
protocols in [2]. In MANET, two proactive routing protocols, OLSR
[4] and TBRPF [5], and two reactive routing protocols, AODV [3] and
DSR [6] are or will progress to experimental RFC status; in addition,
current work is focusing on defining standard track routing protocols
with DYMO and OLSRv2.
In any case, these routing protocols assume that each node has been
assigned an unique IP address on each of its network interfaces. IP
address autoconfiguration is therefore an important practical issue:
a problem statement of address autoconfiguration in MANET may be
found in [8]. In the recent past, many autoconfiguration methods for
various types of MANET networks have been proposed, and this prompted
the proposal of a MANET-autoconf working group in the IETF.
Many conventional methods are organized independently from routing
protocols so that they can be used for any MANET regardless of the
routing protocols. Some other methods are intended to work jointly
with the routing protocols to improve efficiency of IP address
autoconfiguration and address conflict detection. For example,
information about IP addresses in use can be collected with support
of the routing protocol and can be used in selecting a new free
addresses for a node seeking address allocation. A recent analysis
of some MANET autoconfiguration techniques may be found in the survey
[9].
In the current charter of the proposed MANET-Autoconf working group,
the support of the merge of two or more ad-hoc networks is explictly
included. More precisely, one of the specified goals is to "develop
a mechanism to promote configured address uniqueness in the situation
where different ad hoc networks merge". This document proposes a
protocol for this situation. It aims being independent from the
routing protocol and also being independent from the a MANET autoconf
allocation algorithm. It is understood, of course, this mechanism
and its implementation might be directly integrated with another
Adjih & Mase Expires April 20, 2006 [Page 3]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
proposal, or with the functionning of the routing protocol.
The protocol itself is designed to detect address conflicts: one node
collects the addresses of the other nodes in the network, and is able
to detect whether or not, an address conflict exists. When an
address conflict is detected, the nodes which are in conflict are
notified. An overview of the protocol is given in section Section 5.
This document is structured as follows: the Section 2 highlights the
problem statement for detection of address conflicts in merges. The
section Section 4 the principles and the reasons behind those
principles. The Section 6 gives some details of the specification of
the protocol. Finally, the Section 7 gives an hint of some
optimization and some similar protocols which have introduced some
optimizations.
Adjih & Mase Expires April 20, 2006 [Page 4]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
2. Problem statement
As mentionned previously, several autoconfiguration proposals exist
as Internet Drafts specifying differents methods for MANET
autoconfiguration (such as those reviewed [9]). However, in several
of them, by choice, a specific scenario is not addressed: address
conflict detection in the case where two or more ad-hoc networks join
together.
Handling this scenario is the goal of this conflict detection method.
A problem statement for network merges and partitions, was well
presented in the draft "Ad hoc network autoconfiguration: terminology
and problem statement" [8], and is quoted here:
"- Dealing with network merges and partitions
By the nature of MANET, two or more ad hoc networks which are
initially isolated, can merge together or a single ad hoc network
can get partitioned into two or more separate networks, at any
moment in time. While network partitioning may not cause any
severe problem in the MANET's operation, it may be needed that
network partitioning is detected so that the resources (e.g.
limited number of addressed) can be re-used among the nodes.
Network merger introduces challenges to maintain the address
uniqueness. Normally, once an address is allocated to a node, it
continues using it and at the same time defending its own
addresses from being allocated to any other node.
However, since initially isolated ad hoc networks allocates
addresses independent with each other, there remains some
probability of more than one node using same address once two/more
independent ad hoc networks merge."
Hence address conflicts may occur as a result of the case of the
merge of two or more ad-hoc networks (previously out of range with
each other), as there may have been no preexisting coordination for
their autoconfiguration.
In this document, the "promotion of address uniqueness" is performed
by a protocol which is running in parallel with the routing protocol,
and address autoconfiguration method, and checks, constantly, whether
or not an address conflict exists (checking address uniqueness). In
the case where an address conflict exists and is detected, it is
assumed that the address autoconfiguration method will allocate
another address, and such method is not the subject of this document
(enforcing address uniqueness in case of conflict).
Adjih & Mase Expires April 20, 2006 [Page 5]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
3. Terminology
Terminology:
Address Conflict: When two nodes in the same MANET network share the
same address or candidate address, the situation is described as
an "Address Conflict". The nodes involved are "conflicting nodes"
and their shared address is called "conflicting address".
Address Conflict Detection (ACD): Address conflict detection is the
action of detecting address conflict, the situation where some
nodes are going to use or u sing the same address in the same
MANET network.
Duplicate Address Dectection (DAD): In this document, we avoid using
the term "Duplicate address detection" (DAD), as it already has a
predefined meaning in the IETF, and substitute the previous term
of "Address conflict detection".
Conflict Detection Tree (CDT): The tree which is build in order to
check the address conflicts is termed a "Conflict Detection Tree"
(CDR).
Conflict Detection Tree Root (CDTR): In the protocol, one node is at
the root of the CDT: this node is naturally called the "Conflict
Detection Tree Root" (CDTR). This node has the responsibility to
perform address check.
Adjih & Mase Expires April 20, 2006 [Page 6]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
4. Protocol Principles
This section describes the principles of the protocol, and their
rationale.
For considering address conflict detection, one could start from the
following observation: the detection of the existing of a given
address conflict in a network requires that at least one node,
somewhere, is being aware of that the address is used twice by
different nodes.
This observation can be turned in a solution: we point at one unique
designated node in the network which will get assigned the task of
checking that no address conflicts exist in the network.
This is a choice, and this solution is centralized. Hence note that
several alternative solutions exist; for instance, [13] chooses a
full distributed approach where all nodes get to know all the
addresses and identifiers of other nodes in the network.
In any case, in order to detect conflicts, the designated node should
possess two things: the addresses of all the nodes in the network,
and then a means to check address duplication.
Then all information about addresses should flow to the designated
node. A simple way to organize this flow of addresses to the
designated node, is to use a tree (rooted on this node).
Additionally, when a tree is built, a means exists for detecting
address conflict: if for instance each node in the network attaches
itself only once in the tree, an address conflict will be detected by
the designated node when an address is present twice in the tree.
Adjih & Mase Expires April 20, 2006 [Page 7]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
5. Protocol Overview
The rationale for the principles of protocol were highlighted in the
previous Section 4. In this section, an overview of the functioning
of the protocol is precised.
The protocol operates by exchange of protocol control messages
("Conflict Detection Tree message", CDT messages). The protocol
messages are assumed to transmitted in a similar way to MANET routing
or autoconfiguration protocol messages (messages in UDP packets).
Hence they are broadcast to their neighbors (within the radio range),
and this allows neighbor detection.
As described previously, the basis of the protocol is to build a tree
of the nodes in the MANET: this tree may be based on the actually
topology (depending of the range of control messages) of the network,
as it is built by discovering neighbor nodes through the reception
and diffusion of control messages.
The first step in the construction of the tree, is done by having
each node advertising the choice of its root node, and receiving from
neighbor nodes their choice: the root node is thus elected. Then, at
the same time as one node transmits its choice of root node, it also
transmits its choice of parent node: one neighbor node is chosen as
parent, based, for instance, on the distance of one neighbor to the
selected root (shortest can be preferable). Lastly, at the same time
that the node transmits the previous information, it also transmits
the list of its children: the nodes that had selected itself as
parent. Moreover, it not only transmits the children, but also their
children (its grand-children), as they have advertized their own CDT
control messages: in fact, and to be complete, the node ends up
advertising all the subtrees of its children.
With this mode of operation, the node that was elected as the root
(the CDRT), will obtain the tree of all the nodes in the networks.
It will then be able to detect conflict, by using passive "Duplicate
Address Detection" techniques, such as those proposed in [10], in
[11] and in [12]: a node should be present only once in the tree.
The delicate point is that the topology might evolve: this is handled
by maintaining and transmitting a Parent Selection Sequence Number
(see Section 5.3). Additionally, address conflicts for the root(s)
of a tree should be handled specifically.
Overall, the protocol integrates four distinct functions, detailed in
the following section:
o Root election: it is a mechanism which allows nodes to choose one
node as root (Section 5.1).
Adjih & Mase Expires April 20, 2006 [Page 8]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
o Parent selection, and parent & subtree advertisement (Section 5.2)
o Address conflict detection and notification by the root
(Section 5.3)
o Root Address conflict detection and notification by one node
(Section 5.4)
Note that the overhead of transmitting an entire tree, may be large;
however if the tree does not change, optimizations may be applied
(see Section 7).
5.1. Root Election
The Root election is a common root election algorithm: each node
advertizes a set of information which indicates whether or not it
should have priority for being chosen as root compared to another
node (for instance the IP address may be chosen, and some comparison
defined on them). This information is the "Election Priority" in the
message format Section 6.1, and will be precisely defined in future
versions of this document.
Periodically, each node generates CDT messages. Each node detects
from the control messages of its neighbors which root (CDTR) they
have chosen, and the election priority of that root.
If a node detects that it has higher election priority than all nodes
advertised by its neighbors, it automatically, elects itself as CDTR.
Similarily, upon receiving a CDT message from a neighbor, if a node
had chosen no root, or if its previous root had lower priority, the
node will update its choice of CDTR.
Note that the election priority can be arbitrarily chosen, for
instance it can be chosen to be the sequence of bytes of the IP
address of the node. In the case, where the autoconfiguration method
for address assignement is actually not fully decentralized, the
priority may be given to nodes which have a part in the address
assignement of other nodes (for instance, a MANET DHCP server).
5.2. Parent Selection, Parent and Subtree Advertizement
At the same time that a node chooses a root, it starts a procedure to
select, amongs its neighbors, one node which will be its parent to
reach the root of the tree.
The CDT protocol messages propagate the information of the distance
of each node, and the path to the route. Hence, the selecting node,
attempts choose one neighbor with some small distance to the root of
Adjih & Mase Expires April 20, 2006 [Page 9]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
the tree, and all cases, avoids loops.
Once a parent is selected, the node will advertise, in its CDT
protocol messages, its choice of a parent. This will allow the
parent of the node to detect that new child node. Each node keeps a
sequence number for its parent selection, which is incremented at
each new choice. This Parent Selection Sequence Number is also
advertized.
At the same time, the node will advertise all the neighbors that had
chosen itself as parent in the tree. More, it will actually
advertises the neighbors with their children nodes, their grand-
children and so on, in fact, all the subtree of the nodes. The
subtrees include the proper sequence numbers.
Because links might be unidirectionnal, a selected parent node have
an asymmetrical link to the node, i.e. packets might go from the
selected parent node to the node, but not in the opposite direction.
To handle this situation, the node that has selected a parent will
check whether or not its selected parent advertizes itself as child.
If it is not the case, after some delay, the node selects a new
parent.
5.3. Address Conflict Detection and Notification by the Root
Because the root has the list of all the nodes in the network, it is
able to check whether an address conflict exists: if an address is
present more than twice in the tree, an address conflict is detected.
This task is performed each time it receives a CDT protocol message.
In a MANET environment, the topology may be changing quickly. Hence,
it is expected that nodes may change their parents frequently: then
they could temporily appear to be in two or more places of the tree.
The address conflict detection may then lead to false alarms. False
alarms at the root are not a problem in this protocol, except for the
control packet overhead generated, because the receiver nodes are
performing the final check. Still, to dramatically limit false
alarms, the Parent Selection Sequence Number (PSSN) (and its history)
is used to check if the address redundancy may be due node mobility.
Note that in order to limit forced parent selection changes,
triggered by topology changes, in addition, in the protocol, the CDT
need not to be a shortest path tree.
Upon detection of an address conflict, the root will inform the
proper conflicting nodes (through a message forwarded by the
intermediate nodes in the tree) that such a conflict has been
detected. This message includes the other advertized parent of the
conflicting node, and the associated Parent Selection Sequence
Adjih & Mase Expires April 20, 2006 [Page 10]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
Number.
From this address conflict advertizement message, and from the
history of its recent parent selection, the target node is able to
detect with complete certainty if the conflict is actually a false
alarm, or most of the time, is an actual conflict. In this case, the
node will take proper action.
5.4. Root Address Conflict Detection and Notification by one Node
In case of a conflict of addresses of the CDTR, two (or more) trees
may be created in parallel. Another known mechanism is introduced:
using an identifier, consisting of mostly random bits, to check if a
conflict exists, with a sufficiently low probability. Such an
identifier is included in the header of CDT protocol messages, and
hence each node in the tree is performing this verification, upon
reception of each message.
Upon detection of a conflict, a node will send a conflict detection
notification message to the root of the tree. This message is
forwarded to the root of the tree.
Adjih & Mase Expires April 20, 2006 [Page 11]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
6. Detailed Specifications
6.1. Message format
The CDT protocol exchanges messages in UDP packet. The format chosen
for such messages is illustrated on figure Figure 1, more precisely,
CDT protocol advertizement messages. The message type should be
"CDT_ADVERT".
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Root Node Identifier |
| and Election Priority |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nb. Addr. in path to root (NP)| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |\
| Address #1 in path to CDTR | |
| (Root Node Address) | |
| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
: : |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| Address #NP in path to CDTR | |
| (Parent) | |
| |/
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nb. Children Advertized (NC) | Parent Selection Seq. Num. |\
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| Subtree for child #1 | |
| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
: : |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| Subtree for child #NC | |
| |/
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1
Adjih & Mase Expires April 20, 2006 [Page 12]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
Such messages include the subtrees of child nodes which have a
structure which is described on figure Figure 2. The subtree of a
child node is given as a list of subtree for grand-child, which have
exactly the same format, recursively. Because packet size is
limited, a node may transmit the different subtrees in different
messages, hence, part of the subtrees may be transmitted.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Address of the children node |
| (Parent) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nb. (Grand)-Children (NGC) | Parent Selection Seq. Num. |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Subtree for (grand)-child #1 |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Subtree for (grand)-child #NGC |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2
Additionally, the protocol transmits address conflict notification
messages, with message type "CDT_CONFLICT". Their format is
represented on Figure 3. The same format is used both when the CDTR
advertizes a conflict to a node, and when a node advertise a root-
address conflict. In both case the path is contained in the message.
In the first case, the "Root Node Identifier" and the "Conflicting
Root Node Identifier" are set to identical values and all the address
in conflict are given. In the second case, only the "Node
Identifier" fields are set, and the field "Nb. Nodes in Conflict" is
set to 0 (and no conflicting parent addresses are advertized).
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nb. Addr. in path to node (NP)| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adjih & Mase Expires April 20, 2006 [Page 13]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
| |\
| Address #1 in path to Conflicting Node | |
| | |
| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
: : |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| Address #NP in path to Conflicting Node | |
| | |
| |/
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Root Node Identifier |
| and Election Priority |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Conflicting Root Node Identifier |
| and Election Priority |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Conflicting Address |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nb. Nodes in Conflict (NN) | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Parent Selection Seq. Num. #1 | Reserved |\
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| Parent Address #1 for Conflicting Address | |
| | |
| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
: : |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Parent Selection Seq.Num. #NN | Reserved | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| Parent Address #NN for Conflicting Address | |
| | |
| |/
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3
Adjih & Mase Expires April 20, 2006 [Page 14]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
7. Optimizations
Many optimizations may be applied to the CDT protocol, including the
following:
because the tree is not supposed to change often, it is easy not
to send the whole subtree each time indeed, but only differential
updates.
it is possible to make a more resilent protocol by having
different trees at the same time, or by having not really a tree:
a node may chose different parents. This requires some changes to
the simple mechanism above but can be made.
in case of mobility, some repair-strategy might be used which do
not require re-building a whole tree, but only re-using known
subtrees.
In this version of the document, it was chosen to concentrate on main
mechanisms and postpone the introduction and application of such
optimizations. Moreover, many protocols define similar mechanisms or
protocols, and their design may be reused: for instance the STAR
routing protocol maintains exactly a tree for routing at the source;
TBRPF also maintains trees. In one proposal by Jelger and al. for
Manet Gateway Autoconf, a protocol is also used to maintain a tree to
the gateways. Other extensions to MANET routing protocols exist with
also uses tree in some way, for instance Multicast extensions for
OLSR. In general, many other tree maintance protocols exists in the
routing protocol literature and in the MANET autoconfiguration
litterature. Hence, in the future, it is intended to carefully
review such protocols before introducing an optimization mechanism.
In practice also, many mechanisms detailed in this document may be
provided by an underlying routing protocol implementation or an
underlying MANET autoconfiguration methods, in which case, the
implementation becomes simpler and the protocol overhead is
decreased.
Adjih & Mase Expires April 20, 2006 [Page 15]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
8. IANA Considerations
This document has no actions for IANA
Adjih & Mase Expires April 20, 2006 [Page 16]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
9. Security Considerations
This document presents only framework for conflict detection in MANET
autoconfiguration for stand-alone MANETs and does not specify any
special security measure.
Adjih & Mase Expires April 20, 2006 [Page 17]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
10. Acknowledgements
This work was partly funded by the Strategic Information and
Communications R&D Promotion Programme (SCOPE), Ministry of Internal
Affairs and Communications, Japan.
Adjih & Mase Expires April 20, 2006 [Page 18]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
11. References
11.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
11.2. Informative References
[2] Corson, M. and J. Macker, "Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation
Considerations", RFC 2501, January 1999.
[3] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand
Distance Vector (AODV) Routing", RFC 3561, July 2003.
[4] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
[5] Ogier, R., Templin, F., and M. Lewis, "Topology Dissemination
Based on Reverse-Path Forwarding (TBRPF)", RFC 3684,
February 2004.
[6] Johnson, D., "The Dynamic Source Routing Protocol for Mobile Ad
Hoc Networks (DSR)", draft-ietf-manet-dsr-10 (work in
progress), July 2004.
[7] Ruffino, S., Stupar, P., and T. Clausen, "Autoconfiguration in
a MANET: connectivity scenarios and technical issues",
draft-ruffino-manet-autoconf-scenarios-00 (work in progress),
October 2004.
[8] Singh, S., "Ad hoc network autoconfiguration: terminology and
problem statement", draft-singh-autoconf-adp-01 (work in
progress), October 2005.
[9] Bernardos, C. and M. Calderon, "Survey of IP address
autoconfiguration mechanisms for MANETs",
draft-bernardos-manet-autoconf-survey-00 (work in progress),
July 2005.
[10] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad
hoc Networks", Proceedings IEEE Wireless Communications and
Networking Conference (WCNC) 2003, New Orleans, USA,
March 2003.
[11] Mase, K. and C. Adjih, "No Overhead Autoconfiguration OLSR",
draft-mase-manet-autoconf-noaolsr-00 (work in progress),
Adjih & Mase Expires April 20, 2006 [Page 19]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
May 2005.
[12] Clausen, T. and E. Baccelli, "Simple MANET Address
Autoconfiguration", draft-clausen-manet-address-autoconf-00
(work in progress), February 2005.
[13] Laouiti, A., "Address autoconfiguration in Optimized Link State
Routing Protocol", draft-laouiti-manet-olsr-address-autoconf-01
(work in progress), July 2005.
Adjih & Mase Expires April 20, 2006 [Page 20]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
Authors' Addresses
Cedric Adjih
INRIA Rocquencourt, France
Project HIPERCOM
Domaine de Voluceau -Rocquencourt
BP 105
Le Chesnay 78153 cedex
France
Phone: +33 1 3963 5215
Email: cedric.adjih@inria.fr
Pr. Kenichi Mase
Information and Communication Network Lab.,Niigata University
Niigata University
Niigata 950-2181,
Japan
Phone: +81 25 262 7446
Email: mase@ie.niigata-u.ac.jp
URI: http://www.net.ie.niigata-u.ac.jp/
Adjih & Mase Expires April 20, 2006 [Page 21]
Internet-Draft Conflict Detection in MANET Autoconf Oct 2005
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
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 authors retain all their rights.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Adjih & Mase Expires April 20, 2006 [Page 22]