Network Working Group K. Weniger Internet-Draft Panasonic Expires: December 25, 2006 K. Mase Niigata University June 23, 2006 PDAD-OLSR: Passive Duplicate Address Detection for OLSR draft-weniger-autoconf-pdad-olsr-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 December 25, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This draft proposes PDAD-OLSR, a solution for configured address uniqueness maintenance in MANETs running the OLSR protocol. It utilizes the Passive Duplicate Address Detection (PDAD) concept, which enables nodes to passively detect duplicate addresses in the network (e.g., occurring after network merging) by analyzing received routing protocol messages. Due to its passive nature, PDAD-OLSR is very efficient in terms of bandwidth consumption. Moreover, it can Weniger & Mase Expires December 25, 2006 [Page 1] Internet-Draft PDAD June 2006 prevent the contamination of routing tables with wrong routing information resulting from address conflicts. Table of Contents 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Introduction and Motivation . . . . . . . . . . . . . . . . . 4 3. Overview of the Passve DAD Concept . . . . . . . . . . . . . . 6 4. PDAD Algorithms for OLSR . . . . . . . . . . . . . . . . . . . 8 4.1. Data Structures and Parameters . . . . . . . . . . . . . . 8 4.2. PDAD-Source Address (SA) . . . . . . . . . . . . . . . . . 9 4.3. PDAD-Sequence Numbers (SN) . . . . . . . . . . . . . . . . 10 4.4. PDAD-Sequence Number Difference (SND) . . . . . . . . . . 10 4.5. PDAD-Sequence Numbers Equal (SNE) . . . . . . . . . . . . 10 4.6. PDAD-SNs Always Increment (SNI) . . . . . . . . . . . . . 11 4.7. PDAD-Neighborhood History (NH) . . . . . . . . . . . . . . 11 4.8. PDAD-Link States (LS) . . . . . . . . . . . . . . . . . . 12 4.9. PDAD-extended Neighborhood History (eNH) . . . . . . . . . 12 4.10. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.11. Detecting Sequence Number Wrap-arounds . . . . . . . . . . 14 4.12. Support for Multi-Subnet MANET Architecture . . . . . . . 14 5. Conflict Resolution and Related Issues . . . . . . . . . . . . 16 5.1. Conflict Resolution . . . . . . . . . . . . . . . . . . . 16 5.1.1. Option A . . . . . . . . . . . . . . . . . . . . . . . 16 5.1.2. Option B . . . . . . . . . . . . . . . . . . . . . . . 16 5.2. Preventing Routing Table Contamination . . . . . . . . . . 16 5.3. Handling Address Changes . . . . . . . . . . . . . . . . . 17 6. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 18 6.1. Conflict Resolution Message . . . . . . . . . . . . . . . 18 6.2. Changes to TC and HELLO Message . . . . . . . . . . . . . 18 7. Security Considerations . . . . . . . . . . . . . . . . . . . 19 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 8.1. Normative References . . . . . . . . . . . . . . . . . . . 20 8.2. Informative References . . . . . . . . . . . . . . . . . . 20 Appendix A. Illustration of PDAD Algorithms . . . . . . . . . . . 22 A.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . 22 A.2. PDAD-SA . . . . . . . . . . . . . . . . . . . . . . . . . 22 A.3. PDAD-SN . . . . . . . . . . . . . . . . . . . . . . . . . 22 A.4. PDAD-SND . . . . . . . . . . . . . . . . . . . . . . . . . 23 A.5. PDAD-SNE . . . . . . . . . . . . . . . . . . . . . . . . . 23 A.6. PDAD-SNI . . . . . . . . . . . . . . . . . . . . . . . . . 24 A.7. PDAD-NH . . . . . . . . . . . . . . . . . . . . . . . . . 25 A.8. PDAD-LS . . . . . . . . . . . . . . . . . . . . . . . . . 25 A.9. PDAD-eNH . . . . . . . . . . . . . . . . . . . . . . . . . 26 A.10. Effects of Address Conflicts on MPR Selection . . . . . . 26 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 Intellectual Property and Copyright Statements . . . . . . . . . . 29 Weniger & Mase Expires December 25, 2006 [Page 2] Internet-Draft PDAD June 2006 1. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [1]. The terminology of OLSR [2] is used. Conflicting address: An address that is not unique in the network, i.e., two MANET network interfaces in the same MANET are configured with the same address. Conflicting nodes: Two or more nodes configured with the same (conflicting) address. Weniger & Mase Expires December 25, 2006 [Page 3] Internet-Draft PDAD June 2006 2. Introduction and Motivation Address autoconfiguration is a fundamental issue in MANETs, since routing protocols assume that the involved network interfaces are configured with unique IP addresses and manual assignment is often not applicable. Solutions for traditional IP networks such as DHCP [5], DHCPv6 [6], zeroconf [7] or IPv6 Stateless Address Autoconfiguration [8] cannot be applied to MANETs due to their special properties such as the dynamic multi-hop nature. See [3] and [18] for an overview of problems and approaches for MANET address autoconfiguation. Duplicate Address Detection (DAD) is an essential part of address autoconfiguration, especially for stateless protocols. In MANETs, addresses may become duplicate when they are already assigned to nodes, e.g., after optimistic address assignment or after two or more independently configured MANETs merge to one network. This problem is also referred to as configured address uniqueness maintenance problem. Not re-using addresses in different (unconnected) MANETs by constructing MANET-local IP addresses based on pre-configured globally unique IDs such as IEEE MAC addresses may seem to solve this problem without a DAD mechanism, however, for the following reasons we think that this is not a general solution: o Addresses based on pre-configured globally unique IDs are usually not 100\% globally unique, e.g., a IEEE MAC address (or the IP address itself) configured at a specific network interface may be changed by the user, devices with duplicate MAC addresses exist on the market (non-registered or erroneous manufacturing), and some devices may not have globally unique IDs (e.g., sensors) o Addresses based on pre-configured globally unique IDs may have negative implications on privacy [4] o Since this approach requires long addresses to allow the addressing of all existing devices, it is only possible with IPv6, not with IPv4 o Long addresses result in a significant increase of signaling traffic, e.g., of the routing protocol. Dynamically assigning locally unique addresses and re-using them in different (unconnected) MANETs is more efficient, since such addresses may be shorter or can easily be compressed to shorter addresses in routing protocol packets. [17] first proposed the compression of addresses in routing protocol messages. OLSRv2 [14] and DYMO [15] support a special form of address compression. In case (large) parts of the address are generated from random Weniger & Mase Expires December 25, 2006 [Page 4] Internet-Draft PDAD June 2006 numbers (e.g., as proposed in [10]), issue 1 and 2 may not be a problem anymore, but issue 3 and 4 remain. Because of these issues and because different nodes in a network can use different methods for address generation, we think that a DAD solution for the configured address uniqueness maintenance problem is needed. However, the solution should be very bandwidth-efficient to justify its use in cases where the probability of a conflict is very low. This draft proposes a very bandwidth-efficient solution for configured address uniqueness maintenance in a network running the OLSR protocol [2]. The solution is suitable for any kind of addresses exchanged in routing protocol messages, be it MANET-local or globally routable addresses of IPv4 or IPv6. It supports both MANET single- and multi-subnet architecture (see Section 4.12) and is in line with the proposed framework for autoconfiguration [13]. The generation and assignment of addresses is out of scope of this draft. Multiple network interfaces and OLSRv2 are not considered in this version of the draft. Weniger & Mase Expires December 25, 2006 [Page 5] Internet-Draft PDAD June 2006 3. Overview of the Passve DAD Concept The PDAD concept for MANETs was first proposed in [19] and later refined, analyzed, and integrated in a complete address autoconfiguration solution [17]. The initial solution was modular to support multiple routing protocols, namely OLSR, AODV, and FSR. Later, multiple drafts proposed the use of PDAD in the IETF specifically for OLSR [12] [11] [16]. PDAD defines a set of rather simple algorithms that allows nodes to detect address conflicts in the network based on routing protocol anomalies. A specific combination of algorithms is supposed to to detect all conflicts in the network running a specific routing protocol. The basic idea of PDAD is to exploit the fact that some protocol events occur in case of a duplicate address, but (almost) never in case of a unique address. PDAD-enabled nodes derive information about the state of the routing protocol daemon running on another node's network interface and configured with a specific address (e.g., address A) from incoming routing protocol messages. If the receiver's address equals A, the information related to address A in the incoming message is compared to information associated with the state of the receiver's routing protocol daemon in order to detect a possible conflict of address A. If the receiver's address does not equal A, it compares the information from the message to information associated to the state derived from another recently received routing protocol message containing information about address (address A), i.e., PDAD allows the detection of conflicts by intermediate nodes that have unique addresses. Since the state of a routing protocol daemon is changing over time, a node receiving a routing protocol message must have information about the time this routing protocol message has been sent. Without synchronized clocks and additional information in the messages, this time can only be estimated. Here, it is assumed that the time interval during which a specific routing protocol message is completely disseminated in the network can be estimated to be less than a time span T_D. In this case, routing protocol messages received by a node can never be older than T_D. Note that "complete dissemination" of a message does not mean that the message reaches all nodes, it just means that it is not forwarded anymore in the network. T_D can be quite large (e.g., in the order of minutes) and can be different for different routing protocol messages depending on the maximum number of times a message is fowarded, e.g., for HELLO and TC messages. The stated assumption usually holds quit well in reality, since routing protocols use a duplicate cache, nodes do not store to-be-forwarded routing information for unlimited time and Weniger & Mase Expires December 25, 2006 [Page 6] Internet-Draft PDAD June 2006 queuing and media access delays are usually somehow bounded. In fact, all well-known ad hoc routing protocols implicitly assume a certain maximum dissemination time T_D, since otherwise they would not be able to distinguish fresh from stale routing information after sequence number wrap-arounds. In case the estimate for the time span T_D is wrong, PDAD may generate false alarms and nodes with unique address may be forced to change their address. Weniger & Mase Expires December 25, 2006 [Page 7] Internet-Draft PDAD June 2006 4. PDAD Algorithms for OLSR In the following, PDAD algorithms for OLSR [2] are presented. The algorithms were first proposed in [17] and specify what a node has to do to detect duplicate addresses based on incoming routing protocol messages. The algorithms utilize different parameters in TC and HELLO messages such as link states (i.e., neighbor interface addresses), link codes, (message) sequence numbers, and addresses in OLSR routing protocol messages as well as addresses in the IP header. For better undestanding, the algorithms are illustrated in examplary scenarios in Appendix A. A node must implement all of the algorithms to be able to detect all conflicts in the network in all possible scenarios. PDAD-OLSR considers that the MPR selection may be affected by duplicate addresses in the network, which may result in a limited dissemination of routing protocol messages in the network (see Appendix A.10). 4.1. Data Structures and Parameters In addition to the OLSR data structures (or information repositories), each node conceptually maintains two tables for PDAD: a Last Received Protocol Messages (LRM) table and a Neighbor History (NH) table. The Last Received Protocol Messages (LRM) table contains information about the last TC and HELLO protocol message received from a specific originator address. It has the following structure: o Originator Address o Message Type o Message Sequence Number o Neighbor Interface Addresses (with corresponding Link Codes if HELLO message) o Receive Time The Neighbor History (NH) table contains the history of neighboring node addresses and is build from received HELLO messages. Entries older than T_D can be deleted. The entries have the following structure: o Neighbor Interface Address o Last time the receiver has selected this Neighbor Interface Address as MPR Weniger & Mase Expires December 25, 2006 [Page 8] Internet-Draft PDAD June 2006 o Last time the receiver has been selected as MPR by this Neighbor Interface Address o Receive Time of HELLO message The following protocol parameters are used: +-----------+-------------------------------------------+-----------+ | Parameter | Meaning | Default | | name | | value | +-----------+-------------------------------------------+-----------+ | SN_MAX | Maximum message sequence number value | 65535 | | | | | | T_D (TC) | Maximum dissemination time of TC messages | 30s | | | in the network | | | | | | | T_D | Maximum dissemination time of HELLO | 2s | | (HELLO) | messages in the network | | | | | | | SN_RATE | Maximum rate of message sequence number | 5/s | | | incrementation per node | | +-----------+-------------------------------------------+-----------+ 4.2. PDAD-Source Address (SA) If a node receives a TC or HELLO message, it compares the source address in the IP header to its own address. If they equal, a conflict of this address is detected. If the message is a HELLO messages, the originator address can be used instead of the source address in the IP header. The rationale behind this algorithm is that the IP source address is always the address of the last forwarder. This is true for OLSR, since it uses application-layer forwarding of TC messages. Note that an originator address in a TC message which is equal to the receiver's address is not an indication for an address conflict, since a node can receive TC messages originated by itself and forwarded by neighboring nodes. Care must be taken when implementing PDAD-SA, since broadcast messages must not be duplicated within the sending node and internally delivered to the IP stack as received message. This would generate false alarms. The algorithm works completely passive and can detect conflicts between neighboring nodes only. Weniger & Mase Expires December 25, 2006 [Page 9] Internet-Draft PDAD June 2006 4.3. PDAD-Sequence Numbers (SN) If a node receives a TC or HELLO message, it compares the originator address with its own address. If they equal and the sequence number in the message is higher than the receiver's sequence number, a conflict of the originator address is detected. However, false alarms can occur in case of sequence number wrap-arounds. Hence, a conflict must not be assumed if a wrap-around may be the reason for the sequence number inconsistency. A mechanism to detect a possible sequence number wrap-around is described in section Section 4.11. The rationale behind this algorithm are that a node receiving its own TC messages forwarded by other nodes cannot have a sequence number large than the node's internal sequence number counter. It is assumed that no wrap-around has occurred, that sequence numbers are incremented with a certain maximum rate and that each node only increments its own internal sequence number counter. The algorithm works completely passive and can detect conflicts between nodes that are any number of hops away from each other. 4.4. PDAD-Sequence Number Difference (SND) If a node receives a TC or HELLO message, it compares the sequence number in the message with the sequence number in the previously received message from the same originator address and with the same message type. If the sequence number difference is higher than a threshold SNDTHRES, a conflict of the originator address is detected. SNDTHRES can be computed as follows: SNDTHRES=(| T_R1-T_R2|+T_D)*SN_RATE with T_R1 and T_R2 the receive time of message 1 and 2, respectively. Note that the computation of the sequence number difference must consider wrap-arounds, e.g., by calculating the difference with min(|SN1-SN2|,SN_MAX-|SN1-SN2|). The rationale behind this algorithm is that there is a relation between the time between a node has originated two TC messages and the sequence number in those TC messages. Therefore, it is assumed that sequence numbers are incremented with a certain maximum rate and that each node only increments its own internal sequence number counter. The algorithm works completely passive and can detect conflicts between nodes that are any number of hops away from each other. 4.5. PDAD-Sequence Numbers Equal (SNE) If an intermediate node receives a TC or HELLO message, it searches its LRM table for a message with the same message type value and the Weniger & Mase Expires December 25, 2006 [Page 10] Internet-Draft PDAD June 2006 same tuple . If a matching entry is found, the node compares the neighbor interface addresses in both messages. A conflict is detected if they differ. Only messages that have arrived within the preceding time span SN_MAX/SN_RATE-T_D should be considered due to possible sequence number wrap-arounds. The rationale behind this algorithm is that the tuple uniquely identifies a messages originated by a specific node. The algorithm works completely passive and can detect conflicts between nodes that are any number of hops away from each other. 4.6. PDAD-SNs Always Increment (SNI) If a node receives a HELLO message, it compares the sequence number in the message with the sequence number in the previous HELLO message from the same originator address. If the sequence number in the new message is lower, a conflict of the originator address is detected. Again, this is only true if a sequence number wrap-around cannot be the reason for the inconsistency. A mechanism to detect a possible sequence number wrap-arounds is described in section Section 4.11. The rationale is that HELLO messages sent by a specific node are received in the order they are sent (i.e., with increasing sequence numbers), since they are not forwarded and hence cannot "overtake" each other. The algorithm works completely passive and can only detect conflicts between nodes that are at most two hops away from each other. 4.7. PDAD-Neighborhood History (NH) If a node receives a TC message, it checks whether its own address is part of the neighbor interface addresses in the TC message. If this is the case and the link code indicates a bi-directional link, the node searches the originator address in its NH table. If it cannot find the address in the table with a receive time higher than the current time minus T_D, a conflict of the node's address is detected. Otherwise, the node additionally checks whether the NH table indicates that the node has selected the found address as MPR within the last T_D. If this is not the case, a conflict is detected. The rationale behind this algorithm is that a TC message only contains neighbors that have selected the originator address as MPRs and that this requires a bi-directional link. If all addresses in the network are unique, a node having an address equal to one of the neighbor interface addresses in a received TC message must have been Weniger & Mase Expires December 25, 2006 [Page 11] Internet-Draft PDAD June 2006 a neighbor of the originator address. The algorithm works completely passive and can detect conflicts between nodes that are any number of hops away from each other. 4.8. PDAD-Link States (LS) If a node receives a TC message with its own address as originator address, it searches in its NH table for each of the neighbor interface addresses. If at least one address is not found with a receive time higher than the current time minus T_D, a conflict of the originator address is detected. If all addresses have been found, but the NH table indicates that the node's address has not been selected as MPR by the found address within the last T_D, a conflict is detected. The rationale is that if the message has been originated by the receiver, it must only contain addresses of recent neighbor interfaces. The algorithm works completely passive and can detect conflicts between nodes that are any number of hops away from each other. 4.9. PDAD-extended Neighborhood History (eNH) If a node receives a TC message, it checks for each neighbor interface address in the message if it is a neighbor. This can be done by checking the OLSR neighborhood or local link information base or the LRM table. For each found neighbor address, the node searches in the LRM table for previously received HELLO message from this address. For each found HELLO message (not older than T_D), it checks whether the originator address of the TC message is contained in the set of neighbor interface addresses of the found HELLO message. If this is not the case, this is a hint for a conflict of the originator address of the HELLO message. If this is the case, the node additionally checks the link codes of the respective neighbor interface addresses in the HELLO message. If they indicate that the originator address of the TC message has not been selected as MPR within the last T_D by the originator address of the HELLO message, this is another hint for a conflict of the originator address of the HELLO message. However, the receiver cannot be sure whether a conflict exists or not, since it is not aware of the complete neighbor history of the respective neighbor. Hence, the receiver forwards the TC message even if it is not selected as MPR and would normally not forward this TC message. The originator of the HELLO message is then able to detect the conflict by applying the PDAD-NH algorithm on the TC message. Note that the forwarded TC message must be marked as "PDAD eNH hint message" (e.g., by a flag) Weniger & Mase Expires December 25, 2006 [Page 12] Internet-Draft PDAD June 2006 and that PDAD-eNH may not be applied to such TC messages. Otherwise PDAD-eNH on other nodes may suspect a conflict of the address of the hint TC message sender. How the marking is exactly done is TBD. This algorithm is basically the PDAD-NH algorithm executed on behalf of a neighboring node. Minimal additional signaling is needed, which means that this algorithm is not completely passive. A possible optimization to reduce the additional signaling would be to store the neighborhood history of neighbors in each node as learned from received HELLO messages. However, this would require extra amount of memory. The algorithm works semi-passive and can detect conflicts between nodes that are any number of hops away from each other. 4.10. Summary This section summarizes the properties of the PDAD algorithms. +---------+-----------+--------------------+------------+-----------+ | Algorit | Relevant | Potentially | Maximum | Completel | | hm | parameter | conflicting nodes | distance | y passive | | | s in | | between | | | | message | | conflictin | | | | | | g nodes | | +---------+-----------+--------------------+------------+-----------+ | PDAD-SA | sequence | originator/forward | 1 hop | yes | | | number, | er and receiver | | | | | IP source | | | | | | address | | | | | | | | | | | PDAD-SN | sequence | originator and | n hops | yes | | | number, | receiver | | | | | originato | | | | | | r address | | | | | | | | | | | PDAD-SN | sequence | both originators | n hops | yes | | D | number, | | | | | | originato | | | | | | r address | | | | | | | | | | | PDAD-SN | sequence | both originators | n hops | yes | | E | number, | | | | | | originato | | | | | | r address | | | | | | | | | | Weniger & Mase Expires December 25, 2006 [Page 13] Internet-Draft PDAD June 2006 | PDAD-SN | sequence | both originators | 2 hops | yes | | I | number, | | | | | | originato | | | | | | r address | | | | | | | | | | | PDAD-LS | neighbor | originator and | n hops | yes | | | addresses | receiver | | | | | , | | | | | | originato | | | | | | r address | | | | | | | | | | | PDAD-NH | neighbor | neighbor of | n hops | yes | | | addresses | originator and | | | | | , | receiver | | | | | originato | | | | | | r address | | | | | | | | | | | PDAD-eN | neighbor | neighbor of | n hops | no | | H | addresses | originator and | | | | | , | neighbor | | | | | originato | | | | | | r address | | | | +---------+-----------+--------------------+------------+-----------+ 4.11. Detecting Sequence Number Wrap-arounds Wrap-arounds occur when the sequence number value reaches SN_MAX and, after another incrementation, starts again from 0. Wrap-around events are rare if SN_MAX is high and the sequence numbers are initialized to a low value. If only unique addresses exist in the network and a message dissemination time of T_D as well as a maximum sequence number increase rate of SN_RATE is assumed, the maximum difference of the sequence number value from receiver and sender point of view is SN_THRES=SN_RATE*T_D. Consequently, a wrap-around can only be the reason for a sequence number inconsistency, if the lower sequence number value s1 is smaller than SN_THRES and the higher sequence number value s2 is bigger than SN_MAX-SN_THRES+s1. 4.12. Support for Multi-Subnet MANET Architecture The descriptions in this document assumes a single-subnet MANET architecture, but a multi-subnet MANET architecture as proposed in [9] is supported as well. According to the multi-subnet architecture, all MANET routers are assumed to configure their MANET router's OLSR interfaces (which is a loopback interface) with a unique subnet prefix. Assuming that the interface is configured with an address from this prefix, the mechanisms in this document can be used to ensure the uniqueness of the subnet prefix in the network by Weniger & Mase Expires December 25, 2006 [Page 14] Internet-Draft PDAD June 2006 additionally masking the host part of the address. In case all OLSR interfaces use the same host part, the masking is not necessary. Weniger & Mase Expires December 25, 2006 [Page 15] Internet-Draft PDAD June 2006 5. Conflict Resolution and Related Issues 5.1. Conflict Resolution If an algorithm detects a conflict of the receivers's address, the node changes its IP address in order to resolve the conflict. If a conflict is detected by an intermediate node, the conflicting nodes must somehow be informed about the conflict so that they are able to change their address. This document described two options for conflict notification. 5.1.1. Option A This option requires sending a dedicated message via unicast to the duplicate address. The format for this message is specified in Section 6. The destination address is set to the conflicting address. The very conflicting node that caused the inconsistent routing information in the message triggering the conflict detection should change its address. To achieve that, the message should be sent towards the source address in the IP header of the received routing protocol message that triggered the conflict detection. This node then uses its routing table as usual to forward the message to the correct conflicting node. Controlling the next hop towards the conflicting address can be done by using IPv4 loose source routing, IPv6 routing header, or IPv4/IPv6 tunneling. How this is exactly done is TBD. 5.1.2. Option B This option informs all nodes in the network about a detected address conflict by adding conflicting addresses to TC and HELLO messages or marking duplicate addresses as such. It was first proposed in [11]. How the marking is exactly done is TBD. 5.2. Preventing Routing Table Contamination To prevent the contamination of the routing table with false routing information emerging from an address conflict, information about duplicate addresses MUST NOT be used for calculating routes. If option A is used, a TC message that was used to detect the conflict must be ignored for routing table calculation or must not be forwarded, so that the routing tables in other nodes are not contaminated. If option B is used, TC messages are forwarded, but addresses marked as duplicate in the message MUST be ignored for routing table calculation. Weniger & Mase Expires December 25, 2006 [Page 16] Internet-Draft PDAD June 2006 5.3. Handling Address Changes Care must be taken when a node changes its IP address, because the bidirectional link states and the MPR selection states of the OLSR protocol daemon are based on the context of the old address. Hence, a node has to set all its link states to asymmetric and remove all addresses from its MPR selector set. Without these modifications, PDAD-NH would immediately detect a conflict of the new address even if it is unique. Weniger & Mase Expires December 25, 2006 [Page 17] Internet-Draft PDAD June 2006 6. Message Formats 6.1. Conflict Resolution Message The message is encapsulated in an OLSR packet header. The message only contains the conflicting address. The message is send to the conflicting address over the last forwarder of the very routing protocol message that triggered the conflict detection. This can be done by IP tunneling, IPv6 routing header or IPv4 loose source option. Message type is TBD. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Conflicting Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6.2. Changes to TC and HELLO Message How duplicate addresses are added and marked in TC and HELLO messages is TBD. Weniger & Mase Expires December 25, 2006 [Page 18] Internet-Draft PDAD June 2006 7. Security Considerations TBD Weniger & Mase Expires December 25, 2006 [Page 19] Internet-Draft PDAD June 2006 8. References 8.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [3] Singh, S., "Address autoconfiguration for MANETs: definition and problem statement", draft-singh-autoconf-adp-03 (work in progress), March 2006. 8.2. Informative References [4] Narten, T. and R. Draves, "Privacy Extensions for Stateless Address Autoconfiguration in IPv6", RFC 3041, January 2001. [5] Droms, R., "Dynamic Host Configuration Protocol", RFC 2131, March 1997. [6] Droms, R., Bound, J., Volz, B., Lemon, T., Perkins, C., and M. Carney, "Dynamic Host Configuration Protocol for IPv6 (DHCPv6)", RFC 3315, July 2003. [7] Cheshire, S., Aboba, B., and E. Guttman, "Dynamic Configuration of IPv4 Link-Local Addresses", RFC 3927, March 2005. [8] Thomson, S. and T. Narten, "IPv6 Stateless Address Autoconfiguration", RFC 2462, December 1998. [9] Thaler, D., "Multi-Subnet MANETs", draft-thaler-autoconf-multisubnet-manets-00 (work in progress), February 2006. [10] Jelger, C., "MANET Local IPv6 Addresses", draft-jelger-autoconf-mla-00 (work in progress), April 2006. [11] Mase, K. and C. Adjih, "No Overhead Autoconfiguration OLSR", draft-mase-manet-autoconf-noaolsr-01 (work in progress), April 2006. [12] Baccelli, E., "OLSR Passive Duplicate Address Detection", draft-clausen-olsr-passive-dad-00 (work in progress), July 2005. [13] Mase, K., "A common framework for autoconfiguration of stand- Weniger & Mase Expires December 25, 2006 [Page 20] Internet-Draft PDAD June 2006 alone ad hoc networks", draft-mase-autoconf-framework-01 (work in progress), February 2006. [14] Clausen, T., "The Optimized Link-State Routing Protocol version 2", draft-clausen-manet-olsrv2-01 (work in progress), September 2005. [15] Perkins, C. and I. Chakeres, "Dynamic MANET On-demand (DYMO) Routing", draft-ietf-manet-dymo-04 (work in progress), March 2006. [16] Weniger, K., "PDAD-OLSR: Passive Duplicate Address Detection for OLSR", draft-weniger-autoconf-pdad-olsr-00 (work in progress), February 2006. [17] Weniger, K., "PACMAN: Passive Autoconfiguration for Mobile Ad hoc Networks", IEEE Journal of Selected Areas of Communications (JSAC), Vol. 23 No. 3, March 2005. [18] Weniger, K., "Address Autoconfiguration in Mobile Ad Hoc Networks: Current Approaches and Future Directions", IEEE Network Magazine , July 2004. [19] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad hoc Networks", IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, USA, March 2003. Weniger & Mase Expires December 25, 2006 [Page 21] Internet-Draft PDAD June 2006 Appendix A. Illustration of PDAD Algorithms A.1. Notation Node "A" and its OLSR protocol daemon states are depicted with "A(address,sequence number,{neighbor interface address 1, neighbor interface address 2,...})". Non-relevant values as well as broadcast and multicast addresses are represented by "*". Neighboring nodes are connected with dashes (e.g., "A()----B()"), nodes that are not necessarily neighbors with dashes and points (e.g., "A()-...-B()"). The notation for addresses in the IP header is "[src->dst]". TC messages are depicted with "TC(originator address, message sequence number, {neighbor interface address 1, neighbor interface address 1,...})" (HELLO messages accordingly with "HE(..)"). "#(X)" denotes that the node has detected a conflict of address X. A.2. PDAD-SA An example scenario is given in Figure 1. Node A is configured with address 1 and sends a TC (or HELLO) message. Node B is a neighbor of node A and is configured with the same address 1. Upon receiving the message and comparing the IP source address with its own address, it detects a conflict of its own address. ---------- ---------- |A(1,*,{*})|-----|B(1,*,{*})| ---------- ---------- [1->*] TC(1,*,{*}) -> #(1) Figure 1: Example of PDAD-SA A.3. PDAD-SN An example scenario is given in Figure 2. Node A with address 1 sends a TC message. Node B is located somewhere in the network and is configured with the same address 1. Upon receiving the TC message, node B compares originator address and sequence number with its own address and sequence number counter. Since the addresses are equal and the sequence number in the message is higher than its own counter, it detects the conflict of its own address (it is assumed that node B has checked that a wrap-around cannot be the reason for the sequence number inconsistency). Weniger & Mase Expires December 25, 2006 [Page 22] Internet-Draft PDAD June 2006 ----------- ----------- |A(1,90,{*})|-...-|B(1,40,{*})| ----------- ----------- [1->*] TC(1,90,{}) -> #(1) Figure 2: Example of PDAD-SN A.4. PDAD-SND An example scenario is given in Figure 3. Node A with address 1 sends a TC message. Its message sequence number counter value is 5. Node C is configured with the same address 1, but its message sequence number counter value is 2000. After receiving the TC message sent by node A, node B stores the information contained in the message. When the TC message sent by node C is received by node B, it compares the sequence number with the sequence number of the last TC message received from the same originator address. Assuming a threshold SDNTHRES lower than 1995, it detects a conflict of address 1. ---------- ---------- ------------- |A(1,5,{*})|-...-|B(*,*,{*})|-...-|C(1,2000,{*})| ---------- ---------- ------------- [1->*] TC(1,5,{}) -> [1->*] <- TC(1,2000,{}) #(1) Figure 3: Example of PDAD-SND A.5. PDAD-SNE An example scenario is given in Figure 4. Node A with address 1 sends a TC message. Its message sequence number counter value is 5 and the neighbor interface addresses are 3 and 4. Node C is configured with the same address 1 and has the same message sequence number counter value, but the neighbor interface addresses are 6 and 7. After receiving the TC message sent by node A, node B stores the information in the message. When the TC message sent by node C is received by node B, it compares the sequence number with the sequence number of the last TC message received from the same originator Weniger & Mase Expires December 25, 2006 [Page 23] Internet-Draft PDAD June 2006 address. Since they are equal, it compares the neighbor interface addresses. Node B detects a conflict of address 1, because at least one neighbor interface address is different. ------------ ---------- ------------ |A(1,5,{3,4})|-...-|B(*,*,{*})|-...-|C(1,5,{6,7})| ------------ ---------- ------------ [1->*] TC(1,5,{3,4}) -> [1->*] <- TC(1,5,{6,7}) #(1) Figure 4: Example of PDAD-SNE A.6. PDAD-SNI An example scenario is given in Figure 5. Node A with address 1 has a message sequence number counter value of 5. Node B is a neighbor of node A and node C is a neighbor of node B. Node C is also configured with address 1. Its message sequence number counter value is 4. After receiving the HELLO message sent by node A, node B stores the information contained in the message. After the HELLO message sent by node C is received by node B, node B compares the sequence number with the sequence number in the last HELLO message received from the same originator address. Since the second HELLO message has a lower sequence number, node B detects a conflict of address 1 (it is assumed that node B has checked that a wrap-around cannot be the reason for the sequence number inconsistency). ---------- ---------- ---------- |A(1,5,{*})|-----|B(*,*,{*})|-----|C(1,4,{*})| ---------- ---------- ---------- [1->*] HE(1,5,{}) -> [1->*] <- HE(1,4,{}) #(1) Figure 5: Example of PDAD-SNI Weniger & Mase Expires December 25, 2006 [Page 24] Internet-Draft PDAD June 2006 A.7. PDAD-NH An example scenario is given in Figure 6. Node A has address 1 and a Neighbor History (NH) cache containing the addresses 4 and 5. Node B is located somewhere in the network and is configured with address 2. A Node C is a neighbor of node B and is also configured with address 1. Node B sends a TC message. Upon receiving the message, node A notices that its own address is part of the neighbor interface addresses of the TC message. Hence, it checks whether the originator address 2 has recently been a symmetric neighbor by consulting its NH table. Since the check is negative, a conflict of address 1 is detected. ---------- ------------ ---------- |A(1,*,{*})|-...-|B(2,*,{1,*})|-----|C(1,*,{*})| |(NH={4,5})| | | | | ---------- ------------ ---------- [2->*] <- TC(2,*,{1,*}) #(1) Figure 6: Example of PDAD-NH A.8. PDAD-LS An example scenario is given in Figure 7. Node A has address 1 and a Neighbor History (NH) cache containing the addresses 4 and 5. Node B is located somewhere in the network, is also configured with address 1, and sends a TC message. Upon receiving the message, node A notices that its own address is equal to the originator address. Hence, it checks whether at least one of the neighbor interface addresses has not recently been a neighbor by consulting its NH table. Since this is the case, a conflict of address 1 is detected. ---------- ------------ |A(1,*,{*})|-...-|B(1,*,{2,3})| |(NH={4,5})| | | ---------- ------------ [1->*] <- TC(1,*,{2,3}) #(1) Figure 7: Example of PDAD-LS Weniger & Mase Expires December 25, 2006 [Page 25] Internet-Draft PDAD June 2006 A.9. PDAD-eNH An example scenario is given in Figure 8. Node A has address 1 and a Neighbor History (NH) cache containing the addresses 2 and 5. Node B is a neighbor of node A and is configured with address 2. Node C is located somethere in the network and has the address 3. Node D is neighbor of node C and is also configured with address 1. After node A has sent a HELLO message, Node C sends a TC message. Upon receiving the messages, node B notices that a neighbor interface address in the TC message is equal to the address of one of its neighbors (1). It then checks the neighbor interface addresses of this neighbor (1) as learned from the last HELLO message from this address and notices that the originator address of the TC message (3) is not part of this set (2). Hence, it concludes that an address conflict may exist. It marks and forwards the TC message even if it is not elected as MPR node for this TC message. Node A receives the TC message and detects the conflict after applying the PDAD-NH algorithm (since address 3 is not part of node A's NH table). ---------- ------------ ------------ ---------- |A(1,*,{2})|-----|B(2,*,{1,*})|-...-|C(3,*,{1,*})|-----|D(1,*,{*})| |(NH={2,5})| | | | | | | ---------- ------------ ------------ ---------- [1->*] HE(1,*,{2}) -> [3->*] <- TC(3,*,{1,*}) -> [2->*] <- TC'(3,*,{1,*}) #(1) Figure 8: Example of PDAD-eNH A.10. Effects of Address Conflicts on MPR Selection Address conflicts within 4 hops distance may influence MPR selection and may lead to limited dissemination of TC messages. For example, in the scenario shown in Figure 9, node C would not forward TC messages received by node D and vice versa, since both nodes assume that they don't have 2-hop-neighbors (only a 1-hop-neighbor with address 2). The network is virtually partitioned with respect to TC message dissemination. This may be a problem for PDAD algorithms based on TC messages, for instance, PDAD-NH or PDAD-SN cannot detect the conflict of address 1 in the example scenario. However, all conflicts within 4 hops can be detected with the combination of algorithms proposed in this draft. After resolving these conflicts, Weniger & Mase Expires December 25, 2006 [Page 26] Internet-Draft PDAD June 2006 TC messages are again disseminated correctly and conflicts with more than 4 hops between the conflicting nodes can be detected and resolved. In the example scenario, the conflict of address 2 between node B and node E can be detected by PDAD-eNH. After this conflict has been resolved, the conflict of address 1 between node A and F can be detected, e.g., by PDAD-SN or PDAD-NH. See [17] for more details about this problem. ---- ---- ---- ---- ---- ---- |A(1)|-...-|B(2)|-----|C(3)|-----|D(4)|-----|E(2)|-...-|F(1)| ---- ---- ---- ---- ---- ---- Figure 9: Example of MPR selection influenced by address conflict Weniger & Mase Expires December 25, 2006 [Page 27] Internet-Draft PDAD June 2006 Authors' Addresses Kilian A. Weniger Panasonic R&D Center Germany Monzastr. 4c Langen 63225 Germany Phone: +49 6103 766 137 Email: kilian.weniger@eu.panasonic.com Kenichi Mase Niigata University Ikarashi Niigata-shi 950-2181 Japan Phone: +81 25 262 7446 Email: mase@ie.niigata-u.ac.jp Weniger & Mase Expires December 25, 2006 [Page 28] Internet-Draft PDAD June 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. Weniger & Mase Expires December 25, 2006 [Page 29]