INTERNET-DRAFT Emmanuel Baccelli IETF MANET Working Group Thomas Clausen Expiration: 11 January 2006 Julien Garnier LIX, Ecole Polytechnique, France 1 July 2005 OLSR Passive Duplicate Address Detection draft-clausen-olsr-passive-dad-00.txt 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 January 12, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This draft discusses ways to perform duplicate address detection with OLSR. Methods using passive detection through OLSR messages monitoring are described and briefly evaluated. Baccelli, Clausen, Garnier [Page 1] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Duplicate Address Detection with OLSR . . . . . . . . . . . . . . 4 2.1. Mismatching Neighborhood in a HELLO Message . . . . . . . . . . 5 2.2. MPR Selection Abnormality in a HELLO Message . . . . . . . . . 5 2.3. Link-State Mismatch in a TC Message . . . . . . . . . . . . . . 5 2.4. TC Sequence Number Mismatch . . . . . . . . . . . . . . . . . . 6 2.5. Interface Mismatch in an MID Message . . . . . . . . . . . . . 6 3. Scope of Passive Mechanisms . . . . . . . . . . . . . . . . . . . 6 4. Resolving Duplicate Address Conflicts . . . . . . . . . . . . . . 7 5. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 7. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 9 9. Security Considerations . . . . . . . . . . . . . . . . . . . . . 9 10. Copyright . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Baccelli, Clausen, Garnier [Page 2] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 1. Introduction Usually, duplicate address detection is performed when configuring network interfaces in order to ensure that unique addresses are assigned to each interface in the network. Such mechanisms commonly operate with the premises that a node "intelligently" selects an address which it supposes to be unique, followed by a duplicate address detection cycle, through which it verifies that no other active interfaces on the same network has been or is in the process of being configured with the same address. Even assuming that such a mechanism is present in a MANET, allowing MANET nodes to initially configure their interfaces with addresses unique within the network, additional complications arise: two or more MANETs may merge to form a single network, and a formerly connected MANET may partition. Thus, unless it is ensured that all MANET interfaces are assigned globally unique addresses, addressing conflicts may at any point -- not just during initial network configuration. In this draft, we investigate the task of performing duplicate address detection when otherwise independent OLSR networks merge. We benefit from the information already exchanged by OLSR, and identify a number of mechanisms through which a node may detect a conflict between the address assigned to one of its interfaces, and an address assigned to an interface on another node. The mechanisms proposed are, thus, entirely passive, creating no additional information exchange on the network. 1.1. Terminology 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 RFC2119 [5]. Several references are made to the OLSR terminology -- that was first described and employed in [1]. Among others, this document uses the following terminology: - Node: a device capable of participating in a MANET. - Neighbor Node: A node X is a neighbor node of node Y if node Y can hear node X. - Multipoint Relay (MPR): A node which is selected by its neighbor, node X, to "re-transmit" all the broadcast messages Baccelli, Clausen, Garnier [Page 3] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 it emits. - HELLO messages: A node performs link sensing (the discovery of its neighborhood) via the periodic exchange of HELLO messages with its neighbors. - TC messages: A node shares link state information with the whole network through sending and receiving TC messsages. - MID messages: In case a node features several OLSR interfaces, it announces this fact to the other nodes in the network with an MID message. 1.2. Applicability This draft describes and discusses ways to perform passive duplicate address detection with OLSR. 2. Duplicate Address Detection with OLSR In this section, we present different mechanisms through which an OLSR node can detect if an address currently assigned to one of its interfaces is concurrently being used by an interface on another node. We note that none of the mechanisms presented here impose any additional information exchange between nodes beyond what is already performed by OLSR. The duplicate address detection mechanisms are based on inspecting received OLSR control messages, as well as the receiving nodes state, to determine if an address on the receiving node is duplicated else- where in the network. More precisely, a node can inspect a received message to detect (i) if the message appears to have been sent from an interface the receiving node or (ii) if the message contains information about interfaces of the receiving node. In either of these cases, the information contained in the received OLSR message is compared to the state recorded in the receiving node, allowing the receiving node to detect a potential duplicate of one of its addresses. With this in mind, the following subsections will inspect the three main OLSR message types: HELLO, TC and MID-messages. Baccelli, Clausen, Garnier [Page 4] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 2.1. Mismatching Neighborhood in a HELLO Message With HELLO messages, an OLSR node declares its presence to its neigh- borhood and its view of this neighborhood. Therefore, if a node receives a HELLO message on one of its interfaces, where the HELLO message appears to come from the node itself, a potential address duplication may incur. Since HELLO messages are never forwarded in OLSR, an OLSR node should not receive a copy of a HELLO message with any of its own interface addresses as originator (note that this ignores the situation where a node has two radio interfaces running OLSR on the same channel). Therefore, should a node receive a HELLO message with one of its own interface addresses listed as originator, there's a likely collision: two adjacent nodes may have interfaces configured with the same address. This can be confirmed by inspecting the neighborhood being advertised in the supected HELLO message: this HELLO message will include a neighborhood that is different from the node receiving the HELLO. 2.2. MPR Selection Abnormality in a HELLO Message With HELLO messages, a node also announces which neighbors it selects as MPR. Therfore, another intuitive diagnostic on HELLO messages is to consider MPR selection: an MPR node must be selected from among neighbors with which a symmetric link exist. Thus, if a node A has a recorded asymmetric link with node B, and receives a HELLO from node B declaring its selection as MPR, then a conflict exists as indi- cated: a second node A', adjacent to B, has the same address as A. This could, however, be a false conclusion. On establishment of the link between A and B, node A receives a HELLO from B, bringing node A to see the link to B as ASYM. In the next HELLO from node A, node B will see its own address listed and conclude that the link is symmet- ric. Node B may, then, select A as MPR and include this selection in the next HELLO message. In this way, node A will receive an MPR selection from a node with which it has only an asymmetric link, without this being an indication of address conflicts in the network. 2.3. Link-State Mismatch in a TC Message With TC Messages, an OLSR node announces local link state to the whole MANET. Thus, if a node A receives a TC message, declaring the address of one of node A's interfaces as MPR selector, the originator of that TC-message must be a direct neighbor of node A. If it is not Baccelli, Clausen, Garnier [Page 5] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 the case, it may be an indication that the address of node A's inter- face is dupliucated somewhere in the network. 2.4. TC Sequence Number Mismatch TC messages feature a sequence number in order indicate how recent the link state information is, and detect duplicates. Therefore if a node A receives a TC message with the address of one of its own interfaces listed as originator address address and with a sequence number very different from the sequence number that node A currently is using, it can be an indication that the address of this interface of node A is concurrently being assigned to another interface in the OLSR network. 2.5. Interface Mismatch in an MID Message With an MID message, an OLSR node with multiple interfaces declares its interface configuration to the other nodes in the network. If a node A receives a MID messages, in which the address of one of its own interfaces is listed, the remaining addresses listed in the MID must also belong to node A. Alternatively, if node A, receives an MID-message containing one or more addresses belonging to node A but also listing addresses which do not belong to node A, then at least one address is assigned to more than one node. 3. Scope of Passive Mechanisms Passive mechanisms, such as those described in this draft, are based on the monitoring of the control messages of the routing protocol. These aim at detecting anomalies in this traffic, that can hint to possible address collisions. However, this approach has a few short- comings, both in terms of false alarms and in terms undetected dupli- cations. In the rare case of a totally symmetric "mirrored" MANET (A-B-C-D- C'-B'-A'), routing message monitoring may not be sufficient to detect the duplicate addresses. In this case, the duplicate nodes cannot detect the collision with each other since the routing messages pro- duced by the left side of the network are identical to the routing messages produced by the right side of the network (because the topology is symmetric). Sequence number mismatch monitoring may help in this case, but it may also crash the network further, as such mis- matches may invalidate the link state information with each TC trans- mission, alternatively from the right side and the left side of the Baccelli, Clausen, Garnier [Page 6] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 network. Another example is with the sequence number mechanism. This technique is not completely reliable in order to detect duplicate addresses, as delayed delivery can cause an outdated control message that is received to be possibly wrongly interpreted as a case of address duplication. This category of false alarm is more likely to be caused by TC or MID messages rather than HELLO messages, as they feature only one hop scope, suppressing delays due to forwarding. Such cases challenge the passive approach to DAD. Therefore other techniques maybe employed in addition to passive mechanisms in order to increase the reliability of the DAD. These techniques can be called active, or semi-passive, depending on how much additional overhead is produced by the mechanism. Semi-passive techniques involve deeper analysis of the link state information traffic, such as tracking and processing the history of such traffic, in order to prevent errors. However, these techniques come with much more processing and memory needs, a fact that must be carefully evaluated. Active techniques involve sending specific DAD information or mes- sages, in addition to the routing control overhead. For instance, flooding a neighbor solicitation message is part of such a technique. These can be more efficient than passive waiting, but they neverthe- less come with greater overhead, a fact that must also be carefully evaluated. 4. Resolving Duplicate Address Conflicts The purpose of the mechanisms, described in this paper, is to detect when two or more interfaces in the network have been configured with the same address -- that a duplicate address conflict exists in the network. The logical next-step to having detected this situation is to resolve it -- to reconfigure nodes such that each interface par- ticipating in the OLSR network has a network-wide unique address. Resolving a duplicate address conflict is, functionally, orthogonal to detecting a duplicate address conflict and, depending on the specificities of the network, different mechanisms can be employed. In this section, we briefly outline a few general approaches to resolving duplicate address conflict. The objective, however, remains to remove conflicting interfaces from the OLSR network, while disrupting the network operation as little as possible. The simplest solution, once a duplicate address conflict is detected, is for a node to simply disable the local interface(s) which are Baccelli, Clausen, Garnier [Page 7] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 conflicting. If these interfaces then wish to enter the network again, a new initial autoconfiguration cycle must be initiated. The advantage of this method is its simplicity and fact that no lengthy election procedure must be completed before duplicate address con- flicts are resolved. The disadvantage is, that when a conflict arises, all conflicting interfaces are potentially disabled without consideration to traffic (or even necessity: when two interfaces are conflicting, it suffices to disable one of them, not both). A more elegant class of solutions to resolving a duplicate address conflict would be for the node(s) which detect a conflict to "negoti- ate" which interface should yield -- possibly based on metrics such as active traffic flows for a given interface etc. This negotiation would take form of a broadcast of information (a "CONFLICT" message), containing necessary information for a recipient to decide if it should yield and disable a given interface, or not. 5. Authors' Addresses Thomas Heide Clausen, Project PCRI Pole Commun de Recherche en Informatique du plateau de Saclay, CNRS, Ecole Polytechnique, INRIA, Universite Paris Sud, Ecole polytechnique, Laboratoire d'informatique, 91128 Palaiseau Cedex, France Phone: +33 1 69 33 40 73, Email: T.Clausen@computer.org Emmanuel Baccelli HITACHI Labs Europe/ Project PCRI, Pole Commun de Recherche en Informatique du plateau de Saclay, CNRS, Ecole Polytechnique, INRIA, Universite Paris Sud, Ecole polytechnique, Laboratoire d'informatique, 91128 Palaiseau Cedex, France Phone: +33 1 69 33 40 73, Email: Emmanuel.Baccelli@inria.fr Julien Garnier, Project PCRI Pole Commun de Recherche en Informatique du plateau de Saclay, CNRS, Ecole Polytechnique, INRIA, Universite Paris Sud, Ecole polytechnique, Baccelli, Clausen, Garnier [Page 8] INTERNET-DRAFT OLSR Passive DAD 11 July 2005 Laboratoire d'informatique, 91128 Palaiseau Cedex, France Phone: +33 1 69 33 40 73, Email: Julien.Garnier@polytechnique.fr 6. References [1] T. Clausen, P. Jacquet, ``RFC 3626: Optimized Link State Routing Protocol," Request for Comments (Experimental), Internet Engineer- ing Task Force, October 2003. [2] E. Baccelli, T. Clausen, J. Garnier, ``Duplicate Address Detection in OLSR Networks," WPMC Proceedings, September 2005. 7. Changes This is the initial version of this specification. 8. IANA Considerations This document does currently not specify IANA considerations. 9. Security Considerations This document does not specify any security considerations. 10. Copyright Copyright (C) The Internet Society (2004). 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. 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 INFOR- MATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.