Internet DRAFT - draft-nhkim-arod-autoconf
draft-nhkim-arod-autoconf
IETF AUTOCONF(BOF) N. Kim
Internet-Draft Y. Lee
Expires: May 5, 2006 S. Ahn
Information and Communications
University, Computer Networks Lab
November 2005
AROD: An address autoconfiguration with Address Reservation and
Optimistic Duplicated address detection for mobile ad hoc networks
draft-nhkim-arod-autoconf-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 May 5, 2006.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
Every node must configure its network interface with a unique address
in order to communicate with other nodes. Having a centralized DHCP
server that provides addresses to nodes, we can easily and
automatically obtain addresses. However, in a mobile ad hoc network,
difficulties exist in supporting address autoconfiguration due to the
Kim, et al. Expires May 5, 2006 [Page 1]
Internet-Draft AROD November 2005
lack of the centralized servers. We therefore propose a distributed
address autoconfiguration approach for a mobile ad hoc network using
address reservation and optimistic Duplicated Address Detection. The
reserved address helps to reduce the allocation latency, and the
optimistic DAD guarantees the uniqueness of addresses with smaller
communication overhead.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. AROD scheme . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1. Network Initialization . . . . . . . . . . . . . . . . . . 7
3.2. The Address Autoconfiguration Phases . . . . . . . . . . . 7
3.2.1. Allocation Phase . . . . . . . . . . . . . . . . . . . 7
3.2.2. Reservation Phase . . . . . . . . . . . . . . . . . . 8
3.3. Address Borrowing Mechanism . . . . . . . . . . . . . . . 9
4. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Security Consideration . . . . . . . . . . . . . . . . . . . . 11
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
Intellectual Property and Copyright Statements . . . . . . . . . . 13
Kim, et al. Expires May 5, 2006 [Page 2]
Internet-Draft AROD November 2005
1. Introduction
A Mobile Ad hoc Network (MANET) is a spontaneous and arbitrary
network that consists of a group of mobile wireless devices; it lacks
any fixed infrastructure or administration, and possesses a network
topology that may change quickly and unexpectedly as a result of the
mobility of nodes.
In a common wired network, a DHCP(Dynamic Host Configuration
Protocol) server is most commonly used for automatic network
configurations like IP address, subnet mask and default gateway.
However, the MANET lacks any inherently fixed infrastructure or
centralized administration, such as a DHCP server. Because we cannot
apply infrastructure-based autoconfiguration mechanisms to MANET [1],
we need an automatic method to allocate addresses in the MANET.
In prior studies of address autoconfiguration for MANETs, they
suggest mechanisms to avoid address conflicts before joining a MANET.
For example, in the Strong Duplicated Address Detection (DAD) scheme
[2], a new node joining a MANET randomly selects an IP address and
then determines whether other nodes in the MANET are currently using
the selected address. If the new node receives a message from
another node indicating the address is currently being used (i.e.,
NACK), the DAD process is repeated until a unique address can be
obtained. In MANETconf [3], an agent node selected by the new node
performs DAD and assigns the address to the new node. MANETconf uses
a modified DAD that utilizes ACKs as well as NACKs, which may lead to
the ACK explosion problem.
A conflict free allocation method, Prophet [4], is also suggested.
It uses a special function generating disjoint integer sequence .
Prophet succeeds in reducing configuration time and communication
overhead, but it incurs difficulty in designing the special function
guaranteeing the uniqueness of allocated addresses in a distributed
network environment.
First and foremost, autoconfiguration should guarantee the uniqueness
of allocated addresses. All nodes of a network normally require a
unique address to operate. A MANET node also needs a unique address
to communicate with other nodes. If conflicts exist between
addresses, this may cause problems such as transferring and
maintaining the wrong routing information. This incorrect
information may further result in the misrouting or malfunction of
applications. Since this kind of conflict may affect network
performance, guaranteeing the uniqueness of addresses is of the
utmost importance.
Duplicate Address Detection (DAD) is the simplest and strongest
Kim, et al. Expires May 5, 2006 [Page 3]
Internet-Draft AROD November 2005
method to guarantee the uniqueness among allocated addresses.
However, as discussed previously, it requires much longer
configuration time. In this document, we present a distributed
address autoconfiguration scheme reducing address configuration
latency using a reserved address. Moreover, the proposed scheme uses
an optimistic Duplicate Address Detection (DAD) to guarantee the
uniqueness of allocation addresses and to reduce communication
overhead.
Kim, et al. Expires May 5, 2006 [Page 4]
Internet-Draft AROD November 2005
2. Terminology
Mobile Ad hoc Networks(MANET)
- A spontaneous and arbitrary network that consists of a group of
mobile wireless devices; it lacks any fixed infrastructure or
administration, and possesses a network topology that may change
quickly and unexpectedly as a result of the mobility of nodes
Duplicate Address Detection(DAD)
- The process that a MANET node confirms the uniqueness of an
address. That is, DAD means that a simple mehod finding duplicated
addresses in a network.
Reserved Address
- An address that the DAD process is performed in advance. MANET
node can keep the reserved address to give a new node it.
Optimistic Duplicate Address Detection(DAD)
- Usually, DAD performs infinitely until the unique address is
obtained. However, in this document, we define the Optimistic DAD
that performs with one address. Although there is address conflict,
we do not perform DAD with another address because it is not
necessary that all MANET nodes keep the reserved address.
type 1 MANET node
- A node which has a reserved address. That is, it has an extra
address except its own address.
type 2 MANET node
-the MANET node that lacks a reserved address, it has only the
address in use.
Kim, et al. Expires May 5, 2006 [Page 5]
Internet-Draft AROD November 2005
3. AROD scheme
DAD means the process which confirms whether a candidate address is
already being used or not by other nodes. Actually, this checking is
performed 3 times [2]. The DAD takes several seconds to complete
because the process waits to receive all responses from all nodes in
the network, for example, if the maximum hop count of the network is
10 and the maximum one-hop round trip time is 0.15 second, then DAD
timeout must be at least 1.5 second, let say 2 seconds. Therefore,
it takes around 6 seconds to obtain a unique address because the DAD
process is generally executed 3 times.
In addition, there are instances when these methods go through the
address conflict between the randomly selected address and existing
addresses, and therefore increases the address allocation latency
time because a DAD repeats until it retrieves a new address without
conflict.
For fast allocation and low communication overhead, we suggest a
novel distributed address autoconfiguration scheme which uses the
address reservation and optimistic DAD. The configuration time can
be reduced by the pre-confirmed addresses, and communication overhead
can be minimized by reducing the number of DAD trials.
In this document, we define three types of the MANET node: 1) the
MANET node which has a reserved address, it has an extra address
except its own address; 2) the MANET node that lacks a reserved
address, it has only the address in use; and 3) a new node.
AROD allows fast address allocation for a newly arrived node using a
reserved address that is kept in existing MANET nodes. For example,
if a new node arrives at a MANET and it must find its agent node
among its neighbors. Then the new node selects the agent and
requests an address. If the agent node is a type 1 node, it can
immediately allocate its reserved address to the new node.
However, if the agent node is a type 2 MANET node, it can not
immediately allocate an address to a new node. For this case, we
propose an address borrowing mechanism: a type 2 MANET node can
borrow an address from a type 1 MANET node. When a new node directly
gets an address form an agent node, AROD shows better result. That
is, a type 1 node is better than a type 2 node as an agent node for a
new node. However, although a type 2 node is selected as an agent, a
new node fast getting an address than getting from DAD such as Strong
DAD and MANETconf because the borrowing mechanism needs one
broadcasting but DAD needs one or more broadcasting.
After the allocation, in order to make the agent node and new node to
Kim, et al. Expires May 5, 2006 [Page 6]
Internet-Draft AROD November 2005
become a type 1 node, the agent node chooses two random addresses,
and performs DAD with the addresses to check the uniqueness of the
addresses. If the agent node succeeds in getting two reserved
addresses without negative messages, the agent node and new node is
considered a type 1 MANET node. If the agent node succeeds in
obtaining one reserved address, the agent node becomes a type 1 node,
and the new node remains a type 2 node. If the agent node fails to
retrieve the reserved addresses, the agent node and new node are
considered a type 2 MANET node.
Existing autoconfiguration schemes with DAD repeatedly performs DAD
until a new node or agent node gets an address; however, AROD only
performs DAD once although the agent node fails to obtain reserved
addresses because it is not necessary that all nodes become a type 1
MANET node. A type 2 MANET node has the chance to become a type 1
MANET node when it is selected as an agent node by a new node. Thus,
our DAD is referred to as the optimistic DAD. The optimistic DAD
allows low communication overhead and guarantees uniqueness of
allocated address. More details of the proposed scheme are as
follows.
3.1. Network Initialization
When a node comes to the MANET, it must find an agent node that can
allocate an address among its neighbors. If the new node succeeds in
finding one or more agent nodes before timeout, it can obtain an
address through the agent node. However, if the new node fails to
find an agent node before timeout which means there are no neighbors
around the new node, it must configure itself and prepare a reserved
address for the next new node. That is, because the first node of a
MANET cannot receive any response, it must perform DAD for itself in
order to configure its network interface and also prepare a reserved
address. The MANET has now completed the network initialization. If
one or more first nodes start the network initialization, each first
node consists of a MANET, and then each MANET is merged after a
while.
3.2. The Address Autoconfiguration Phases
Our address autoconfiguration protocol can be divided into two parts:
one is an Allocation Phase, and the other is a Reservation Phase.
3.2.1. Allocation Phase
Let's assume that new node i is not the first node and that there are
some nodes surrounding node i. First, node i finds its agent node
among its one hop neighbors, and then receives one or more responses
before timeout. At that time, neighbors' response messages include
Kim, et al. Expires May 5, 2006 [Page 7]
Internet-Draft AROD November 2005
their number of reserved addresses. Node i selects one node that
sends out the response as its agent node for address allocation; we
assumes j is the agent node of node i. Node i requires an address,
and node j immediately gives its reserved address. After node i has
obtained an address, it turns into a type 2 MANET node.
When the new node selects an agent among its neighbor nodes, it
usually waits a while and then selects an agent node having a
reserved address. If the node just selects an agent node that
doesn't have a reserved address, it takes longer to obtain an address
because the agent node must execute the address borrowing mechanism.
However, if the new node waits for a certain amount of time, it may
receive multiple responses from agent nodes that have a reserved
address. Therefore, the new node can select a type 1 MANET node
instead of a type 2 MANET node as its agent node. On the other hand,
there are instances when the waiting time is useless, particularly
when all the neighbors of the new node are type 2 MANET nodes.
3.2.2. Reservation Phase
Let's consider the above example. After the address allocation,
agent node j randomly chooses two addresses, and performs DAD with
those in order to prepare its reserved address and node i's. When
node k, a type 1 MANET node, receives the message getting reserved
addresses from node j, node k must check whether or not the addresses
in the message conflict with its address or reserved address. If
node k finds the address conflict, node k must send a negative
message with the duplicate address.
There are three cases for the Reservation Phase of j. The first case
is that node j finds two available addresses without negative
messages. In this case, node j keeps one address for its reserved
address, and gives one address to node i. Node i then uses the
address as its reserved address. Now node i and j become type 1
nodes. The second case is that node j gets one available address, in
this case, node j keeps the address for its reserved address, and
sends a negative message to node i. Then node j becomes a type 1
node and node i remains a type 2 node. Finally, node j fails to get
both reserved addresses, it sends a negative message to node i. Then
node i and j are considered a type 2 MANET node. The Reservation
Phase is now complete.
In the Reservation Phase, we need not to retry DAD, because it is not
necessary all MANET nodes are the type 1 nodes. Due to this
property, our DAD is referred to as optimistic DAD. The DAD occurs
only when the new node comes to join the MANET. The type 2 MANET
nodes have the chance to get the reserved addresses when the new node
comes to a MANET, and those would be selected as an agent node by the
Kim, et al. Expires May 5, 2006 [Page 8]
Internet-Draft AROD November 2005
new node.
3.3. Address Borrowing Mechanism
For instance, we can consider a type 2 MANET node j as an agent of a
new node x. That is, it was selected as an agent by a new node x.
Therefore, node j can not allocate immediately address to node x. In
this case, should node x wait while node j gets a reserved address?
If node x waits for the process of node j, it will take as long to
obtain an address as the Strong DAD [2] or MANETconf [3]. To reduce
latency time, node j borrows a reserved address from type 1 MANET
nodes instead of getting addresses through DAD.
Node j floods a borrow message and node m receives the borrowing
address request from node j. After node j borrows a reserved address
from node m, it sends an acknowledgement to node m. At the same time
node j allocates the address to node x. Finally, node j must perform
DAD to get the reserved addresses. In that case, node j randomly
selects three addresses and performs DAD for node x, node m and
itself; node m waits without performing a DAD until node j pays back
an address or it receives a fail message from node j. If node m
receives the address from node j, node m becomes a type 1 node again.
However, node m receives a fail message, node m is considered a type
2 node.
In the worst case scenario, node j can not borrow an address from any
other node. In that case, node j waits until the timer expires; it
should then perform the DAD for node x, until it obtains an address.
Kim, et al. Expires May 5, 2006 [Page 9]
Internet-Draft AROD November 2005
4. Discussion
All address autoconfiguration schemes may show better results with a
large address space, such as IPv6. If the address size 128bit, then
the conflict ratio among candidate addresses is almost zero although
any random function is used to select addresses. Therefore, the
configuration time and communication overhead are not affected by the
number of nodes in a network. Also, IPv6 easily guarantees the
uniqueness of allocated addresses with its huge address space.
However, the conflict confirmation procedure, such as DAD, is
inevitably required to avoid the unexpected conflicts. In fact, IPv4
is nowadays a dominant network protocol considering the global
connectivity [5], and the address space may vary from networks to
networks. Therefore, address autoconfiguration must show stable
performance regardless of the address space.
To configure an address in MANET, we suggested a distributed address
autoconfiguration with address reservation and optimistic DAD to
satisfy low address allocation latency time, low communication
overheads, and the uniqueness of allocated addresses. The reserved
addresses can help to reduce address allocation time, and the address
borrowing mechanism can guarantee relatively fast allocation even if
a new node fails in directly getting an address from its agent.
Moreover, the optimistic DAD contributed to reducing communication
overheads and guaranteeing the uniqueness of allocated address.
Kim, et al. Expires May 5, 2006 [Page 10]
Internet-Draft AROD November 2005
5. Security Consideration
This document does not consider security issue.
6. References
[1] Singh, S. and J. Kim, "Ad hoc network autoconfiguration:
definition and problem statement",
I-D draft-singh-autoconf-adp-00.txt, August 2005.
[2] Perkins, C., Malinen, J., Wakikawa, R., Belding-Royer, E., and
Y. Sun, "IP Address Autoconfiguration for Ad Hoc Networks",
I-D draft-ietf-manetautoconf-01.txt, November 2001.
[3] Nesargi, S. and R. Prakash, "MANETconf: Configuration of Hosts
in a Mobile Ad Hoc Network", IEEE INFOCOM 2002 , June 2002.
[4] Zhou, H., Ni, L., and M. Mutka, "Prophet Address Allocation for
Large Scale MANETs", IEEE INFOCOM 2003 , March 2003.
[5] Ruffino, S., Stupar, P., Clausen, T., and S. Singh,
"Connectivity Scenarios for MANET",
I-D draft-ruffino-conn-scenarios-00.txt, August 2005.
Kim, et al. Expires May 5, 2006 [Page 11]
Internet-Draft AROD November 2005
Authors' Addresses
Namhoon Kim
Information and Communications University, Computer Networks Lab
Munji Ro 119
Daejeon, Yuseong Gu 305-732
Korea Rep.
Phone: +82 042 866 6251
Fax: +82 042 866 6222
Email: nhkim@icu.ac.kr
Younghee Lee
Information and Communications University, Computer Networks Lab
Munji Ro 119
Daejeon, Yuseong Gu 305-732
Korea Rep.
Phone: +82 042 866 6112
Fax: +82 042 866 6222
Email: yhlee@icu.ac.kr
Soyeon Ahn
Information and Communications University, Computer Networks Lab
Munji Ro 119
Daejeon, Yuseong Gu 305-732
Korea Rep.
Phone: +82 042 866 6251
Fax: +82 042 866 6222
Email: syahn@icu.ac.kr
Kim, et al. Expires May 5, 2006 [Page 12]
Internet-Draft AROD November 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.
Kim, et al. Expires May 5, 2006 [Page 13]
