MANET Autoconfiguration (AUTOCONF) K. Mase Internet-Draft Information and Communication Expires: August 11, 2006 Network Lab., Niigata University C. Adjih Project HYPERCOM, INRIA Domaine de Voluceau, Rocquencourt, France February 7, 2006 A common framework for autoconfiguration of stand-alone ad hoc networks draft-mase-autoconf-framework-01 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 August 11, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract We consider the unique local address autoconfiguration problem for stand-alone ad hoc networks (MANETs). Specifically, we consider two cases. First, a node without a pre-assigned and valid local address acquires a new local address and becomes a member of a new or Mase & Adjih Expires August 11, 2006 [Page 1] Internet-Draft Framework February 2006 existing MANET. Second, two or more MANETs merge. In the first case, a mechanism of IP address generation based on a stateful or stateless method is needed. We also should have MANET-wide duplicate address detection (MANET-DAD) on newly generated address (tentative address) for suppressing occurrence of duplicate addresses regardless of whether stateful or stateless method is employed for address generation (pre-service MANET-DAD). In the second case, duplicate address may occur as the result of a merger of two formerly independent networks. We should have MANET-DAD on addresses in use for resolving duplicate addresses and suppressing routing information contamination due to existence of duplicate addresses (in-service MANET-DAD). To realize pre-service MANET-DAD and in-service MANET- DAD, we define autoconfiguration states that are common for both proactive and reactive routing protocol. Each node exists in one of the autoconfiguration states at any time. The specific MANET-DAD algorithm is beyond the scope of this document. Mase & Adjih Expires August 11, 2006 [Page 2] Internet-Draft Framework February 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2. Requirements . . . . . . . . . . . . . . . . . . . . . . . 7 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4. Autoconfiguration states . . . . . . . . . . . . . . . . . . . 10 4.1. Autoconfiguration states . . . . . . . . . . . . . . . . . 10 5. Effect of autoconfiguration states . . . . . . . . . . . . . . 13 6. Proposed Values for Constants . . . . . . . . . . . . . . . . 14 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 8. Security Considerations . . . . . . . . . . . . . . . . . . . 16 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 17 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 10.1. Normative References . . . . . . . . . . . . . . . . . . . 18 10.2. Informative References . . . . . . . . . . . . . . . . . . 18 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 Intellectual Property and Copyright Statements . . . . . . . . . . 21 Mase & Adjih Expires August 11, 2006 [Page 3] Internet-Draft Framework February 2006 1. Introduction This document discusses autoconfiguration of unique local (MANET- local) address for stand-alone MANET. Autoconfiguration methods are generally classified into stateless and stateful methods. Conventional statefull and stateless autoconfiguration methods cannot be used for stand-alone mobile ad hoc networks (MANETs), since such networks do not depend on a central server and multihop communication is involved. A number of autoconfiguration solutions to prevent address conflict have been proposed for stand-alone MANETs [1],[7]-[22]. Some of these proposals discuss MANET-wide duplicated address detection (MANET-DAD) only in initial address generation and do not discuss potential occurrence of address conflict when network mergers occur. Some of these proposals discuss MANET-DAD to deal with address conflict in case of a merger. The aim of this document is not to provide another solution for the MANET autoconfiguration problem, but to give a common framework, that may be useful for designing solutions regardless of wether the underlying routing protocol is proactive or reactive. The baselines of this framework are as follows: - Each node should perform MANET-DAD both before and after assignment of a valid address in a MANET. This is termed "pre- service MANET-DAD" and "in-service MANET-DAD" respectively. - MANET-DAD functions could be embedded in routing control messages regardless of pre-service MANET-DAD or in-service MANET- DAD. With regard to the first baseline above, pre-service MANET-DAD is useful to suppress occurrences of an address conflict regardless of whether stateless or stateful address assignment methods are employed and in-service MANET-DAD is useful to suppress occurrences of address conflict and the resulting possible routing information contamination in case of network mergers. To realize pre-service and in-service MANET-DAD systematically, we use the concept of autoconfiguration states. This was first proposed in [7] and is extended in this document. The second baseline is useful to reduce pre-service MANET- DAD and in-service MANET-DAD overhead and to allow inter-working between nodes in pre-service MANET-DAD and those in in-service MANET- DAD when they coexist.It is also useful to suppress routing infomation contamination. A pioneering example of pre-service MANET- DAD for a reactive routing protocols was proposed in [8]. A pioneering example of in-service MANET-DAD for both proactive and reactive routing protocols was proposed in [1]. These useful but individual schemes can be systematically included as the elements in the proposed framework. A functionality and mechanism of "Duplicate address detection(DAD)" for link-local address are defined in the Mase & Adjih Expires August 11, 2006 [Page 4] Internet-Draft Framework February 2006 traditional IETF terms-RFC(2461/2462) [3] and [4]. The mechanisms defined in this document, i.e., "pre-service MANET-DAD" is identical in functionality (but not mechanism) to DAD, and "in-service MANET- DAD" is similar to functionality(but not mechanism),that is used in [6], necessary for MANETs. Mase & Adjih Expires August 11, 2006 [Page 5] Internet-Draft Framework February 2006 2. Terminology 2.1. General This section provides definitions for terms that have a specific meaning to the protocol specified in this document and that are used throughout the text. Some fundamental definitions are taken from [3], [4]. IP - Internet Protocol Version 4 or 6. node - a device that implements IP. link - a communication facility or medium over which nodes can communicate at the link layer, i.e., the layer immediately below IP. interface - a node's attachment to a link. neighbors - nodes attached to the same link. address - an IP-layer identifier for an interface. MANET-local address - a unique-local address having scope that is limited to the MANET. tentative address - an address whose uniqueness in a MANET is being verified, prior to its assignment to an interface. A tentative address is not considered assigned to an interface in the usual sense. An interface discards received packets addressed to a tentative address, but accepts routing control packets related to MANET-wide Duplicate Address Detection for the tentative address. address generation - Adress generation is a procedure for a node, that has currently no address, to obtain a tentative address in the MANET -either of its own accord or with support of other nodes. address conflict - When two nodes in the same MANET network share the same address or tentative address, the situation is described as an "Address Conflict". The nodes involved are "conflicting nodes" and their shared address is called the "conflicting address". MANET-wide Duplicate Address Detection (MANET-DAD) - MANET-wide Duplicate address detection is the action of detecting address conflict in the MANET, the situation where some nodes are going to use or using the same address in the same MANET network. Mase & Adjih Expires August 11, 2006 [Page 6] Internet-Draft Framework February 2006 pre-service MANET-DAD - Pre-service MANET-DAD is the procedure to verify that a tentative address is out of address conflict with other MANET nodes. in-service MANET-DAD - In-service MANET-DAD is the procedure to continuously verify that a used address is out of address conflict with other MANET nodes. autoconfiguration state - The current autoconfiguration state of the node, one of NO_ADDRESS, ADVERTISING and NORMAL, which indicates what messages it should (or should not) generate and what processing it should (or should not) do. familiar address (Node) - An address is familiar to a node, if the node has seen it in control messages for a sufficiently long period of time. A node recognizes the other node with a familiar address as the familiar node. An address or a node which is not familiar is denoted "unfamiliar". routing information contamination - Erroneous updates of routing information due to address conflict. 2.2. Requirements 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 [2]. Mase & Adjih Expires August 11, 2006 [Page 7] Internet-Draft Framework February 2006 3. Overview We consider the MANET-local address autoconfiguration problem for stand-alone MANETs. Specifically, we consider two cases. - In the first case, a node without a pre-assigned address acquires an address and becomes a member of a new or existing MANET. - In the second case, two or more MANETs merge. For the first case, a mechanism of address generation is needed, and a number of address generation methods have been proposed in literature. These are classified into stateful and stateless methods. In this case, a node first obtains an address (tentative address) using a proper address generation method, - be that either a stateful or stateless method. It then verifies that the tentative address is not part of an address conflict with (not currently used by) other nodes. This procedure is termed "pre-service MANET-DAD" in this document. We SHOULD have pre-service MANET-DAD on a tentative address for suppressing occurrence of duplicate addresses in the address assignment regardless of whether stateful or stateless methods is employed. Note that the necessity of pre-service MANET- DAD for MANETs with reactive routing protocol has been well known [8] and this method can be applied to MANETs with proactive routing protocol. In this case, however, existing nodes in the MANET must process control messages, specific for pre-service DAD, in addition to those for routing, giving rise to additional overhead. A new pre- service DAD method embeded in routing control messages for MANETs with proactive routing protocol was proposed recently [7]. In the second case, two or more already configured MANETs merge resulting address conflict. To cope with this situation, a node in an existing MANET SHOULD continuously verify possible address conflict with other MANET nodes. This procedure is termed "in- service MANET-DAD" in this document. "Weak DAD" [14] and "passive DAD" [1] are examples of in-service MANET-DAD. When an address conflict is detected, a node with a duplicate address MUST obtain a new address to resolve the address conflict. This is accomplished using the address generation mentioned before. During duplicate address detection and resolution in the above case, some nodes may share the same address transiently and, therefore, routing information may not be correctly maintained. Specifically, a route entry may erroneously be updated based on control messages including information from different nodes with the same duplicate address. We call this problem "routing information contamination". We SHOULD have in-service MANET-DAD for detecting duplicate addresses as well as for suppressing routing contamination due to existence of Mase & Adjih Expires August 11, 2006 [Page 8] Internet-Draft Framework February 2006 duplicate addresses. To systematically realize pre-service MANET-DAD and in-service MANET-DAD, we define autoconfiguration states that are common for both proactive and reactive routing protocols. Each node is in one of the autoconfiguration states at any time. Specific pre- service and in-service MANET-DAD algorithms are beyond the scope of this document. Mase & Adjih Expires August 11, 2006 [Page 9] Internet-Draft Framework February 2006 4. Autoconfiguration states A set of autoconfiguration states are defined, that are common for both reactive and proactive routing protocols, in order to realize pre-service MANET-DAD and in-service MANET-DAD. Each node has an "autoconfiguration state" at any time. This state is an indicator of how long the node has been in the network. The central idea is that each time a node generates a new address(tentative address), it should enter the network gradually, running a restrained version of the routing protocol. This way, the node can detect which addresses are being used, checking for duplicates of its own tentative address, while avoiding disrupting the routing information of the other nodes in the MANET in the event that its address is actually found to be in conflict. To do this, we need autoconfiguration states 4.1. Autoconfiguration states There are exactly 3 autoconfiguration states, which define the behavior of the node as follows: NO_ADDRESS_STATE : In this state a node does not have its own address, and it MUST NOT process and forward routing control messages generated by other nodes. It MUST NOT participate in data forwarding. It MAY generate a tentative address by means of a pre-determined address generation method. When it generates its tentative address, it enters the ADVERTISING_STATE. ADVERTISING_STATE - In this state, a node MUST NOT forward routing control messages generated by other nodes. It MUST NOT participate in data forwarding. It SHOULD perform pre-service MANET-DAD using the control messages,that can be embeded in the routing control messages to avoide introducing additional control messages. Specific pre-service MANET-DAD methods are beyond the scope of this document. To distinguish between normal routing control messages and those of autoconfiguration, a flag in the control message MAY be used to represent autoconfiguration state. For example, 0/1 in a routing control message indicates that the originating node is in NORMAL_STATE /ADVERTISING_STATE, respectively. When the node detects that it has an address conflict with other nodes, it MUST re-enter NO_ADDRESS_STATE. When pre-service MANET-DAD is completed using, ex, timer, in ADVERTISING_STATE without an address conflict being detected, the node enters the NORMAL_STATE. ADVERTISING STATES may have substates with regard to the scope of adverting, such as LOCAL_AD_state and GLOBAL_AD_state. Mase & Adjih Expires August 11, 2006 [Page 10] Internet-Draft Framework February 2006 NORMAL_STATE : In this state, the node is running the "normal" routing protocol without message processing/generation restrictions associated to the state. More precisely, the node generates routing control messages as usual. It processes routing control messages generated by other nodes and forwards these as specified by the routing protocol. It also participates in data forwarding. Only nodes in NORMAL_STATE are selected as the intermediary nodes (forwarders). A node in this state SHOULD perform in-service MANET-DAD using the control messages that can be embeded in the routing control messages. Specific in-service MANET-DAD method is beyond the scope of this document. When the node detects that it has an address conflict with other nodes, it MUST return the NO_ADDRESS_STATE. The behavior in each state is summarized in Table I and the state transition diagram is given in Fig.1 Table I. Autoconfiguration states +----------------+----------------+----------------+----------------+ | State | NO_ADDRESS_ | ADVERTISING | NORMAL_STATE | | | STATE | | | +----------------+----------------+----------------+----------------+ | Address | yes | no | no | | Generation | | | | | | | | | | Routing control| no | yes | yes | | message | | | | | forwarding | | | | | | | | | | Routing control| no | yes | yes | | message | | | | | processing | | | | | | | | | | Routing control| no | no | yes | | message | | | | | generation | | | | | | | | | | Routing table | no | no | yes | | calculation | | | | | (and | | | | | forwarding) | | | | | | | | | | State duration | as long as |ADVERTISING_ | forever | | (if no address | no address |STATE_ DURATION | | | change) | | | | +----------------+----------------+----------------+----------------+ Mase & Adjih Expires August 11, 2006 [Page 11] Internet-Draft Framework February 2006 (Address generation) (In-service MANET-DAD) +--------------+Duplicate address +--------------+ | NO_ADDRESS | detected | NORMAL | +----------| _STATE |<-------------------| _STATE |<--+ | +--------------+ +--------------+ | | ^ Full routing | | | Duplicate address | | Tentative address| detected | | generated +------------+ Time-out| | | | | +--------------------------------------------------------+ | | | ADVERTISING_STATE | | | | | | | | +--------------+ +-------------+ | | | | | LOCAL_AD | Time-out | GLOBAL_AD | | | +--->| | _STATE |<-----------------| _STATE | |---+ | +--------------+ +-------------+ | +--------------------------------------------------------+ (Pre-service MANET-DAD) No forwarding Fig.1 Autoconfiguration state transition diagram. Mase & Adjih Expires August 11, 2006 [Page 12] Internet-Draft Framework February 2006 5. Effect of autoconfiguration states Pre-service MANET-DAD is performed when a node is in the ADVERTISING_STATE. Pre-service MANET-DAD is effective at reducing potential address conflicts and the resulting routing table contamination when a new node joins a MANET. This state is, however, not only effective for enabling pre-service MANET-DAD. When a node is in ADVERTISING_STATE, other nodes in the MANET have a chance to learn information about the node, such as address and sequence number. Specifically, we assume that each node continuously collects information about other nodes, regardless of their states. As a result, each node is "familiar" with other nodes in NORMAL_STATE within the connected MANET. When network merger occurs, a node may find unfamiliar nodes, allowing it to detect the network merger. Thus, network merger of multiple different MANETs can be detected without a sophisticated network merger detection method such as based on network ID as proposed in the literature [10]. This learning mechanism may be useful for easing the design of an in-service MANET- DAD algorithm. Specific in-service MANET-DAD algorithms are beyond the scope of this document. Mase & Adjih Expires August 11, 2006 [Page 13] Internet-Draft Framework February 2006 6. Proposed Values for Constants The proposed values of the specification are documented here[6]. Parameter Name Value -------------------------- -------------------------------------- ADVERTISING_STATE_DURATION NET_TRAVERSAL_TIME NET_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * NET_DIAMETER NODE_TRAVERSAL_TIME 40 millisecond NET_DIAMETER 35 Mase & Adjih Expires August 11, 2006 [Page 14] Internet-Draft Framework February 2006 7. IANA Considerations This document has no actions for IANA. Mase & Adjih Expires August 11, 2006 [Page 15] Internet-Draft Framework February 2006 8. Security Considerations This document presents only framwork of autoconfiguration for stand- alone MANETs and does therefore not specify any special security measure. However, introduction of autoconfiguration states may be useful to realize some security measures. For example, node authentification may be done during the ADVERTISING_STATE. Mase & Adjih Expires August 11, 2006 [Page 16] Internet-Draft Framework February 2006 9. Acknowledgements This work was funded by Strategic Information and Communications R&D Promotion Programme (SCOPE), Ministry of Internal Affairs and Communications, Japan. The authors would like to gratefully acknowledge Thomas Clausen (Ecole Polytechnique), Shubranshu Singth(Samsung AIT) and Kilian Weniger(Panasonic R&D Center) for intense technical discussions, early reviews and comments on this work. Mase & Adjih Expires August 11, 2006 [Page 17] Internet-Draft Framework February 2006 10. References 10.1. Normative References [1] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad Hoc Networks," in Proceedings of IEEE WCNC 2003, New Orleans, USA, Mar. 2003. [2] Brander, S. "Key words for use in RFCs to Indicate Requirement Levels," RFC2119, Mar. 1997. [3] Narten, T., E. Nordmark and W. Simpson,"Neighbor Discovery for IP Version 6 (IPv6)," RFC2461, Dec. 1998. [4] Thomson, S. and T. Narten,"IPv6 Stateless Address Autoconfiguration," RFC2462, Dec. 1998. [5] Perkins, C. E., E. Belding-Royer and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing," RFC3561, July 2003. [6] Cheshire, S., B. Aboba and E. Guttman, "Dynamic Configuration of IPv4 Link-Local Addresses," RFC3927, May 2005. 10.2. Informative References [7] Mase, K. and C. Adjih, "No Ovrhead Autoconfiguration OLSR", draft-mase-manet-atuoconf-noaolsr-00 (work in progress), May 2005. [8] Perkins, C. E., J. T. Malinen, R. Wakikawa, E. M. Belding- Royer, and Y. Sun, "IP Address Autoconfiguration for Ad Hoc Networks," draft-ietf-manet-autoconf-01.txt, Nov. 2001, work in progress. [9] Mohsin, M. and R. Prakash, "IP Address Assignment in a Mobile Ad Hoc Network," MILCOM 2002. [10] Nesargi, S. and R. Prakash, "MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network," in Proc. of IEEE INFOCOM 2002, New York, June 2002. [11] Boleng, J., "Efficient Network Layer Addressing for Mobile Ad Hoc Networks," in Proc. of Int. Conf. on Wireless Networks (ICWN '02), pp. 271-277, Las Vegas, June 2002. [12] Weniger, K. and M. Zitterbart, "IPv6 Autoconfiguration in Large Scale Mobile Ad-Hoc Networks," in Proc. of European Wireless 2002, vol. 1, pp. 142-148, Florence, Feb. 2002. Mase & Adjih Expires August 11, 2006 [Page 18] Internet-Draft Framework February 2006 [13] Zhou, H., L. M. Ni, and M. W. Mutka, "Prophet Address Allocation for Large Scale MANETs," INFOCOM 2003. [14] Vaidya N. H., "Weak Duplicate Address Detection in Mobile Ad Hoc Networks," in Proc. of ACM MobiHoc 2002, pp. 206-216, Lausanne, Switzerland, June 2002. [15] Jeong, J., "Ad Hoc IP Address Autoconfiguration," Internet Draft, draft-jeong-adhoc-ip-addr-autoconf-00.txt, Nov. 2003, work in progress. [16] Mase, K., S. Narita, and S. Yoshida, "Efficient IP address Assignment in Mobile Ad Hoc Networks," pp. 504-508, WPMC, 2003. [17] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [18] Perkins, C. E., Belding-Royer, E., and S. Das, "Ad hoc On- Demand Distance Vector (AODV) Routing", RFC 3561, July 2003. [19] 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. [20] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad hoc Networks", March 2003. [21] Singh, S., J. Kim, C. E. Perkins, P. M. Ruiz, and T. Clausen, "Ad Hoc Network Autoconfiguration: Definition and Problem Statement", draft-singh-autoconf-adp-00.txt (work in progress), Feb. 2005. [22] Bernardos, C. and M. Calderon, "Survey of IP address autoconfiguration mechnisms ofr MANETs", draft-bernardos-manet-autoconf-survey-00 (work in progress), July 2005. Mase & Adjih Expires August 11, 2006 [Page 19] Internet-Draft Framework February 2006 Authors' Addresses Kenichi Mase Information and Communication Network Lab., Niigata University Phone: +81 25 262 7446 Email: mase@ie.niigata-u.ac.jp URI: http://www.net.ie.niigata-u.ac.jp/ Cedric Adjih Project HYPERCOM, INRIA Domaine de Voluceau, Rocquencourt, France Phone: +33 1 3963 5215 Email: cedric.adjih@inria.fr Mase & Adjih Expires August 11, 2006 [Page 20] Internet-Draft Framework February 2006 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 (2006). 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. Mase & Adjih Expires August 11, 2006 [Page 21]