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]