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]