idnits 2.17.00 (12 Aug 2021) /tmp/idnits65475/draft-weniger-autoconf-pdad-olsr-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1015. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 992. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 999. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1005. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 4 instances of too long lines in the document, the longest one being 2 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 23, 2006) is 5811 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Experimental RFC: RFC 3626 (ref. '2') -- Possible downref: Normative reference to a draft: ref. '3' -- Obsolete informational reference (is this intentional?): RFC 3041 (ref. '4') (Obsoleted by RFC 4941) -- Obsolete informational reference (is this intentional?): RFC 3315 (ref. '6') (Obsoleted by RFC 8415) -- Obsolete informational reference (is this intentional?): RFC 2462 (ref. '8') (Obsoleted by RFC 4862) == Outdated reference: A later version (-01) exists of draft-jelger-autoconf-mla-00 == Outdated reference: A later version (-04) exists of draft-mase-autoconf-framework-01 == Outdated reference: A later version (-26) exists of draft-ietf-manet-dymo-04 == Outdated reference: A later version (-01) exists of draft-weniger-autoconf-pdad-olsr-00 Summary: 6 errors (**), 0 flaws (~~), 6 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group K. Weniger 3 Internet-Draft Panasonic 4 Expires: December 25, 2006 K. Mase 5 Niigata University 6 June 23, 2006 8 PDAD-OLSR: Passive Duplicate Address Detection for OLSR 9 draft-weniger-autoconf-pdad-olsr-01 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on December 25, 2006. 36 Copyright Notice 38 Copyright (C) The Internet Society (2006). 40 Abstract 42 This draft proposes PDAD-OLSR, a solution for configured address 43 uniqueness maintenance in MANETs running the OLSR protocol. It 44 utilizes the Passive Duplicate Address Detection (PDAD) concept, 45 which enables nodes to passively detect duplicate addresses in the 46 network (e.g., occurring after network merging) by analyzing received 47 routing protocol messages. Due to its passive nature, PDAD-OLSR is 48 very efficient in terms of bandwidth consumption. Moreover, it can 49 prevent the contamination of routing tables with wrong routing 50 information resulting from address conflicts. 52 Table of Contents 54 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. Introduction and Motivation . . . . . . . . . . . . . . . . . 4 56 3. Overview of the Passve DAD Concept . . . . . . . . . . . . . . 6 57 4. PDAD Algorithms for OLSR . . . . . . . . . . . . . . . . . . . 8 58 4.1. Data Structures and Parameters . . . . . . . . . . . . . . 8 59 4.2. PDAD-Source Address (SA) . . . . . . . . . . . . . . . . . 9 60 4.3. PDAD-Sequence Numbers (SN) . . . . . . . . . . . . . . . . 10 61 4.4. PDAD-Sequence Number Difference (SND) . . . . . . . . . . 10 62 4.5. PDAD-Sequence Numbers Equal (SNE) . . . . . . . . . . . . 10 63 4.6. PDAD-SNs Always Increment (SNI) . . . . . . . . . . . . . 11 64 4.7. PDAD-Neighborhood History (NH) . . . . . . . . . . . . . . 11 65 4.8. PDAD-Link States (LS) . . . . . . . . . . . . . . . . . . 12 66 4.9. PDAD-extended Neighborhood History (eNH) . . . . . . . . . 12 67 4.10. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 13 68 4.11. Detecting Sequence Number Wrap-arounds . . . . . . . . . . 14 69 4.12. Support for Multi-Subnet MANET Architecture . . . . . . . 14 70 5. Conflict Resolution and Related Issues . . . . . . . . . . . . 16 71 5.1. Conflict Resolution . . . . . . . . . . . . . . . . . . . 16 72 5.1.1. Option A . . . . . . . . . . . . . . . . . . . . . . . 16 73 5.1.2. Option B . . . . . . . . . . . . . . . . . . . . . . . 16 74 5.2. Preventing Routing Table Contamination . . . . . . . . . . 16 75 5.3. Handling Address Changes . . . . . . . . . . . . . . . . . 17 76 6. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 18 77 6.1. Conflict Resolution Message . . . . . . . . . . . . . . . 18 78 6.2. Changes to TC and HELLO Message . . . . . . . . . . . . . 18 79 7. Security Considerations . . . . . . . . . . . . . . . . . . . 19 80 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 81 8.1. Normative References . . . . . . . . . . . . . . . . . . . 20 82 8.2. Informative References . . . . . . . . . . . . . . . . . . 20 83 Appendix A. Illustration of PDAD Algorithms . . . . . . . . . . . 22 84 A.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . 22 85 A.2. PDAD-SA . . . . . . . . . . . . . . . . . . . . . . . . . 22 86 A.3. PDAD-SN . . . . . . . . . . . . . . . . . . . . . . . . . 22 87 A.4. PDAD-SND . . . . . . . . . . . . . . . . . . . . . . . . . 23 88 A.5. PDAD-SNE . . . . . . . . . . . . . . . . . . . . . . . . . 23 89 A.6. PDAD-SNI . . . . . . . . . . . . . . . . . . . . . . . . . 24 90 A.7. PDAD-NH . . . . . . . . . . . . . . . . . . . . . . . . . 25 91 A.8. PDAD-LS . . . . . . . . . . . . . . . . . . . . . . . . . 25 92 A.9. PDAD-eNH . . . . . . . . . . . . . . . . . . . . . . . . . 26 93 A.10. Effects of Address Conflicts on MPR Selection . . . . . . 26 94 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 95 Intellectual Property and Copyright Statements . . . . . . . . . . 29 97 1. Terminology 99 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 100 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 101 document are to be interpreted as described in [1]. 103 The terminology of OLSR [2] is used. 105 Conflicting address: An address that is not unique in the network, 106 i.e., two MANET network interfaces in the same MANET are configured 107 with the same address. 109 Conflicting nodes: Two or more nodes configured with the same 110 (conflicting) address. 112 2. Introduction and Motivation 114 Address autoconfiguration is a fundamental issue in MANETs, since 115 routing protocols assume that the involved network interfaces are 116 configured with unique IP addresses and manual assignment is often 117 not applicable. Solutions for traditional IP networks such as DHCP 118 [5], DHCPv6 [6], zeroconf [7] or IPv6 Stateless Address 119 Autoconfiguration [8] cannot be applied to MANETs due to their 120 special properties such as the dynamic multi-hop nature. See [3] and 121 [18] for an overview of problems and approaches for MANET address 122 autoconfiguation. 124 Duplicate Address Detection (DAD) is an essential part of address 125 autoconfiguration, especially for stateless protocols. In MANETs, 126 addresses may become duplicate when they are already assigned to 127 nodes, e.g., after optimistic address assignment or after two or more 128 independently configured MANETs merge to one network. This problem 129 is also referred to as configured address uniqueness maintenance 130 problem. Not re-using addresses in different (unconnected) MANETs by 131 constructing MANET-local IP addresses based on pre-configured 132 globally unique IDs such as IEEE MAC addresses may seem to solve this 133 problem without a DAD mechanism, however, for the following reasons 134 we think that this is not a general solution: 136 o Addresses based on pre-configured globally unique IDs are usually 137 not 100\% globally unique, e.g., a IEEE MAC address (or the IP 138 address itself) configured at a specific network interface may be 139 changed by the user, devices with duplicate MAC addresses exist on 140 the market (non-registered or erroneous manufacturing), and some 141 devices may not have globally unique IDs (e.g., sensors) 143 o Addresses based on pre-configured globally unique IDs may have 144 negative implications on privacy [4] 146 o Since this approach requires long addresses to allow the 147 addressing of all existing devices, it is only possible with IPv6, 148 not with IPv4 150 o Long addresses result in a significant increase of signaling 151 traffic, e.g., of the routing protocol. Dynamically assigning 152 locally unique addresses and re-using them in different 153 (unconnected) MANETs is more efficient, since such addresses may 154 be shorter or can easily be compressed to shorter addresses in 155 routing protocol packets. [17] first proposed the compression of 156 addresses in routing protocol messages. OLSRv2 [14] and DYMO [15] 157 support a special form of address compression. 159 In case (large) parts of the address are generated from random 160 numbers (e.g., as proposed in [10]), issue 1 and 2 may not be a 161 problem anymore, but issue 3 and 4 remain. Because of these issues 162 and because different nodes in a network can use different methods 163 for address generation, we think that a DAD solution for the 164 configured address uniqueness maintenance problem is needed. 165 However, the solution should be very bandwidth-efficient to justify 166 its use in cases where the probability of a conflict is very low. 168 This draft proposes a very bandwidth-efficient solution for 169 configured address uniqueness maintenance in a network running the 170 OLSR protocol [2]. The solution is suitable for any kind of 171 addresses exchanged in routing protocol messages, be it MANET-local 172 or globally routable addresses of IPv4 or IPv6. It supports both 173 MANET single- and multi-subnet architecture (see Section 4.12) and is 174 in line with the proposed framework for autoconfiguration [13]. The 175 generation and assignment of addresses is out of scope of this draft. 176 Multiple network interfaces and OLSRv2 are not considered in this 177 version of the draft. 179 3. Overview of the Passve DAD Concept 181 The PDAD concept for MANETs was first proposed in [19] and later 182 refined, analyzed, and integrated in a complete address 183 autoconfiguration solution [17]. The initial solution was modular to 184 support multiple routing protocols, namely OLSR, AODV, and FSR. 185 Later, multiple drafts proposed the use of PDAD in the IETF 186 specifically for OLSR [12] [11] [16]. 188 PDAD defines a set of rather simple algorithms that allows nodes to 189 detect address conflicts in the network based on routing protocol 190 anomalies. A specific combination of algorithms is supposed to to 191 detect all conflicts in the network running a specific routing 192 protocol. The basic idea of PDAD is to exploit the fact that some 193 protocol events occur in case of a duplicate address, but (almost) 194 never in case of a unique address. 196 PDAD-enabled nodes derive information about the state of the routing 197 protocol daemon running on another node's network interface and 198 configured with a specific address (e.g., address A) from incoming 199 routing protocol messages. If the receiver's address equals A, the 200 information related to address A in the incoming message is compared 201 to information associated with the state of the receiver's routing 202 protocol daemon in order to detect a possible conflict of address A. 203 If the receiver's address does not equal A, it compares the 204 information from the message to information associated to the state 205 derived from another recently received routing protocol message 206 containing information about address (address A), i.e., PDAD allows 207 the detection of conflicts by intermediate nodes that have unique 208 addresses. 210 Since the state of a routing protocol daemon is changing over time, a 211 node receiving a routing protocol message must have information about 212 the time this routing protocol message has been sent. Without 213 synchronized clocks and additional information in the messages, this 214 time can only be estimated. Here, it is assumed that the time 215 interval during which a specific routing protocol message is 216 completely disseminated in the network can be estimated to be less 217 than a time span T_D. In this case, routing protocol messages 218 received by a node can never be older than T_D. Note that "complete 219 dissemination" of a message does not mean that the message reaches 220 all nodes, it just means that it is not forwarded anymore in the 221 network. T_D can be quite large (e.g., in the order of minutes) and 222 can be different for different routing protocol messages depending on 223 the maximum number of times a message is fowarded, e.g., for HELLO 224 and TC messages. The stated assumption usually holds quit well in 225 reality, since routing protocols use a duplicate cache, nodes do not 226 store to-be-forwarded routing information for unlimited time and 227 queuing and media access delays are usually somehow bounded. In 228 fact, all well-known ad hoc routing protocols implicitly assume a 229 certain maximum dissemination time T_D, since otherwise they would 230 not be able to distinguish fresh from stale routing information after 231 sequence number wrap-arounds. In case the estimate for the time span 232 T_D is wrong, PDAD may generate false alarms and nodes with unique 233 address may be forced to change their address. 235 4. PDAD Algorithms for OLSR 237 In the following, PDAD algorithms for OLSR [2] are presented. The 238 algorithms were first proposed in [17] and specify what a node has to 239 do to detect duplicate addresses based on incoming routing protocol 240 messages. The algorithms utilize different parameters in TC and 241 HELLO messages such as link states (i.e., neighbor interface 242 addresses), link codes, (message) sequence numbers, and addresses in 243 OLSR routing protocol messages as well as addresses in the IP header. 244 For better undestanding, the algorithms are illustrated in examplary 245 scenarios in Appendix A. A node must implement all of the algorithms 246 to be able to detect all conflicts in the network in all possible 247 scenarios. PDAD-OLSR considers that the MPR selection may be 248 affected by duplicate addresses in the network, which may result in a 249 limited dissemination of routing protocol messages in the network 250 (see Appendix A.10). 252 4.1. Data Structures and Parameters 254 In addition to the OLSR data structures (or information 255 repositories), each node conceptually maintains two tables for PDAD: 256 a Last Received Protocol Messages (LRM) table and a Neighbor History 257 (NH) table. 259 The Last Received Protocol Messages (LRM) table contains information 260 about the last TC and HELLO protocol message received from a specific 261 originator address. It has the following structure: 263 o Originator Address 265 o Message Type 267 o Message Sequence Number 269 o Neighbor Interface Addresses (with corresponding Link Codes if 270 HELLO message) 272 o Receive Time 274 The Neighbor History (NH) table contains the history of neighboring 275 node addresses and is build from received HELLO messages. Entries 276 older than T_D can be deleted. The entries have the following 277 structure: 279 o Neighbor Interface Address 281 o Last time the receiver has selected this Neighbor Interface 282 Address as MPR 284 o Last time the receiver has been selected as MPR by this Neighbor 285 Interface Address 287 o Receive Time of HELLO message 289 The following protocol parameters are used: 291 +-----------+-------------------------------------------+-----------+ 292 | Parameter | Meaning | Default | 293 | name | | value | 294 +-----------+-------------------------------------------+-----------+ 295 | SN_MAX | Maximum message sequence number value | 65535 | 296 | | | | 297 | T_D (TC) | Maximum dissemination time of TC messages | 30s | 298 | | in the network | | 299 | | | | 300 | T_D | Maximum dissemination time of HELLO | 2s | 301 | (HELLO) | messages in the network | | 302 | | | | 303 | SN_RATE | Maximum rate of message sequence number | 5/s | 304 | | incrementation per node | | 305 +-----------+-------------------------------------------+-----------+ 307 4.2. PDAD-Source Address (SA) 309 If a node receives a TC or HELLO message, it compares the source 310 address in the IP header to its own address. If they equal, a 311 conflict of this address is detected. If the message is a HELLO 312 messages, the originator address can be used instead of the source 313 address in the IP header. 315 The rationale behind this algorithm is that the IP source address is 316 always the address of the last forwarder. This is true for OLSR, 317 since it uses application-layer forwarding of TC messages. Note that 318 an originator address in a TC message which is equal to the 319 receiver's address is not an indication for an address conflict, 320 since a node can receive TC messages originated by itself and 321 forwarded by neighboring nodes. 323 Care must be taken when implementing PDAD-SA, since broadcast 324 messages must not be duplicated within the sending node and 325 internally delivered to the IP stack as received message. This would 326 generate false alarms. 328 The algorithm works completely passive and can detect conflicts 329 between neighboring nodes only. 331 4.3. PDAD-Sequence Numbers (SN) 333 If a node receives a TC or HELLO message, it compares the originator 334 address with its own address. If they equal and the sequence number 335 in the message is higher than the receiver's sequence number, a 336 conflict of the originator address is detected. However, false 337 alarms can occur in case of sequence number wrap-arounds. Hence, a 338 conflict must not be assumed if a wrap-around may be the reason for 339 the sequence number inconsistency. A mechanism to detect a possible 340 sequence number wrap-around is described in section Section 4.11. 342 The rationale behind this algorithm are that a node receiving its own 343 TC messages forwarded by other nodes cannot have a sequence number 344 large than the node's internal sequence number counter. It is 345 assumed that no wrap-around has occurred, that sequence numbers are 346 incremented with a certain maximum rate and that each node only 347 increments its own internal sequence number counter. 349 The algorithm works completely passive and can detect conflicts 350 between nodes that are any number of hops away from each other. 352 4.4. PDAD-Sequence Number Difference (SND) 354 If a node receives a TC or HELLO message, it compares the sequence 355 number in the message with the sequence number in the previously 356 received message from the same originator address and with the same 357 message type. If the sequence number difference is higher than a 358 threshold SNDTHRES, a conflict of the originator address is detected. 359 SNDTHRES can be computed as follows: SNDTHRES=(| 360 T_R1-T_R2|+T_D)*SN_RATE with T_R1 and T_R2 the receive time of 361 message 1 and 2, respectively. Note that the computation of the 362 sequence number difference must consider wrap-arounds, e.g., by 363 calculating the difference with min(|SN1-SN2|,SN_MAX-|SN1-SN2|). 365 The rationale behind this algorithm is that there is a relation 366 between the time between a node has originated two TC messages and 367 the sequence number in those TC messages. Therefore, it is assumed 368 that sequence numbers are incremented with a certain maximum rate and 369 that each node only increments its own internal sequence number 370 counter. 372 The algorithm works completely passive and can detect conflicts 373 between nodes that are any number of hops away from each other. 375 4.5. PDAD-Sequence Numbers Equal (SNE) 377 If an intermediate node receives a TC or HELLO message, it searches 378 its LRM table for a message with the same message type value and the 379 same tuple . If a matching 380 entry is found, the node compares the neighbor interface addresses in 381 both messages. A conflict is detected if they differ. Only messages 382 that have arrived within the preceding time span SN_MAX/SN_RATE-T_D 383 should be considered due to possible sequence number wrap-arounds. 385 The rationale behind this algorithm is that the tuple uniquely identifies a messages originated 387 by a specific node. 389 The algorithm works completely passive and can detect conflicts 390 between nodes that are any number of hops away from each other. 392 4.6. PDAD-SNs Always Increment (SNI) 394 If a node receives a HELLO message, it compares the sequence number 395 in the message with the sequence number in the previous HELLO message 396 from the same originator address. If the sequence number in the new 397 message is lower, a conflict of the originator address is detected. 398 Again, this is only true if a sequence number wrap-around cannot be 399 the reason for the inconsistency. A mechanism to detect a possible 400 sequence number wrap-arounds is described in section Section 4.11. 402 The rationale is that HELLO messages sent by a specific node are 403 received in the order they are sent (i.e., with increasing sequence 404 numbers), since they are not forwarded and hence cannot "overtake" 405 each other. 407 The algorithm works completely passive and can only detect conflicts 408 between nodes that are at most two hops away from each other. 410 4.7. PDAD-Neighborhood History (NH) 412 If a node receives a TC message, it checks whether its own address is 413 part of the neighbor interface addresses in the TC message. If this 414 is the case and the link code indicates a bi-directional link, the 415 node searches the originator address in its NH table. If it cannot 416 find the address in the table with a receive time higher than the 417 current time minus T_D, a conflict of the node's address is detected. 418 Otherwise, the node additionally checks whether the NH table 419 indicates that the node has selected the found address as MPR within 420 the last T_D. If this is not the case, a conflict is detected. 422 The rationale behind this algorithm is that a TC message only 423 contains neighbors that have selected the originator address as MPRs 424 and that this requires a bi-directional link. If all addresses in 425 the network are unique, a node having an address equal to one of the 426 neighbor interface addresses in a received TC message must have been 427 a neighbor of the originator address. 429 The algorithm works completely passive and can detect conflicts 430 between nodes that are any number of hops away from each other. 432 4.8. PDAD-Link States (LS) 434 If a node receives a TC message with its own address as originator 435 address, it searches in its NH table for each of the neighbor 436 interface addresses. If at least one address is not found with a 437 receive time higher than the current time minus T_D, a conflict of 438 the originator address is detected. If all addresses have been 439 found, but the NH table indicates that the node's address has not 440 been selected as MPR by the found address within the last T_D, a 441 conflict is detected. 443 The rationale is that if the message has been originated by the 444 receiver, it must only contain addresses of recent neighbor 445 interfaces. 447 The algorithm works completely passive and can detect conflicts 448 between nodes that are any number of hops away from each other. 450 4.9. PDAD-extended Neighborhood History (eNH) 452 If a node receives a TC message, it checks for each neighbor 453 interface address in the message if it is a neighbor. This can be 454 done by checking the OLSR neighborhood or local link information base 455 or the LRM table. For each found neighbor address, the node searches 456 in the LRM table for previously received HELLO message from this 457 address. For each found HELLO message (not older than T_D), it 458 checks whether the originator address of the TC message is contained 459 in the set of neighbor interface addresses of the found HELLO 460 message. If this is not the case, this is a hint for a conflict of 461 the originator address of the HELLO message. If this is the case, 462 the node additionally checks the link codes of the respective 463 neighbor interface addresses in the HELLO message. If they indicate 464 that the originator address of the TC message has not been selected 465 as MPR within the last T_D by the originator address of the HELLO 466 message, this is another hint for a conflict of the originator 467 address of the HELLO message. However, the receiver cannot be sure 468 whether a conflict exists or not, since it is not aware of the 469 complete neighbor history of the respective neighbor. Hence, the 470 receiver forwards the TC message even if it is not selected as MPR 471 and would normally not forward this TC message. The originator of 472 the HELLO message is then able to detect the conflict by applying the 473 PDAD-NH algorithm on the TC message. Note that the forwarded TC 474 message must be marked as "PDAD eNH hint message" (e.g., by a flag) 475 and that PDAD-eNH may not be applied to such TC messages. Otherwise 476 PDAD-eNH on other nodes may suspect a conflict of the address of the 477 hint TC message sender. How the marking is exactly done is TBD. 479 This algorithm is basically the PDAD-NH algorithm executed on behalf 480 of a neighboring node. Minimal additional signaling is needed, which 481 means that this algorithm is not completely passive. A possible 482 optimization to reduce the additional signaling would be to store the 483 neighborhood history of neighbors in each node as learned from 484 received HELLO messages. However, this would require extra amount of 485 memory. 487 The algorithm works semi-passive and can detect conflicts between 488 nodes that are any number of hops away from each other. 490 4.10. Summary 492 This section summarizes the properties of the PDAD algorithms. 494 +---------+-----------+--------------------+------------+-----------+ 495 | Algorit | Relevant | Potentially | Maximum | Completel | 496 | hm | parameter | conflicting nodes | distance | y passive | 497 | | s in | | between | | 498 | | message | | conflictin | | 499 | | | | g nodes | | 500 +---------+-----------+--------------------+------------+-----------+ 501 | PDAD-SA | sequence | originator/forward | 1 hop | yes | 502 | | number, | er and receiver | | | 503 | | IP source | | | | 504 | | address | | | | 505 | | | | | | 506 | PDAD-SN | sequence | originator and | n hops | yes | 507 | | number, | receiver | | | 508 | | originato | | | | 509 | | r address | | | | 510 | | | | | | 511 | PDAD-SN | sequence | both originators | n hops | yes | 512 | D | number, | | | | 513 | | originato | | | | 514 | | r address | | | | 515 | | | | | | 516 | PDAD-SN | sequence | both originators | n hops | yes | 517 | E | number, | | | | 518 | | originato | | | | 519 | | r address | | | | 520 | | | | | | 521 | PDAD-SN | sequence | both originators | 2 hops | yes | 522 | I | number, | | | | 523 | | originato | | | | 524 | | r address | | | | 525 | | | | | | 526 | PDAD-LS | neighbor | originator and | n hops | yes | 527 | | addresses | receiver | | | 528 | | , | | | | 529 | | originato | | | | 530 | | r address | | | | 531 | | | | | | 532 | PDAD-NH | neighbor | neighbor of | n hops | yes | 533 | | addresses | originator and | | | 534 | | , | receiver | | | 535 | | originato | | | | 536 | | r address | | | | 537 | | | | | | 538 | PDAD-eN | neighbor | neighbor of | n hops | no | 539 | H | addresses | originator and | | | 540 | | , | neighbor | | | 541 | | originato | | | | 542 | | r address | | | | 543 +---------+-----------+--------------------+------------+-----------+ 545 4.11. Detecting Sequence Number Wrap-arounds 547 Wrap-arounds occur when the sequence number value reaches SN_MAX and, 548 after another incrementation, starts again from 0. Wrap-around 549 events are rare if SN_MAX is high and the sequence numbers are 550 initialized to a low value. If only unique addresses exist in the 551 network and a message dissemination time of T_D as well as a maximum 552 sequence number increase rate of SN_RATE is assumed, the maximum 553 difference of the sequence number value from receiver and sender 554 point of view is SN_THRES=SN_RATE*T_D. Consequently, a wrap-around 555 can only be the reason for a sequence number inconsistency, if the 556 lower sequence number value s1 is smaller than SN_THRES and the 557 higher sequence number value s2 is bigger than SN_MAX-SN_THRES+s1. 559 4.12. Support for Multi-Subnet MANET Architecture 561 The descriptions in this document assumes a single-subnet MANET 562 architecture, but a multi-subnet MANET architecture as proposed in 563 [9] is supported as well. According to the multi-subnet 564 architecture, all MANET routers are assumed to configure their MANET 565 router's OLSR interfaces (which is a loopback interface) with a 566 unique subnet prefix. Assuming that the interface is configured with 567 an address from this prefix, the mechanisms in this document can be 568 used to ensure the uniqueness of the subnet prefix in the network by 569 additionally masking the host part of the address. In case all OLSR 570 interfaces use the same host part, the masking is not necessary. 572 5. Conflict Resolution and Related Issues 574 5.1. Conflict Resolution 576 If an algorithm detects a conflict of the receivers's address, the 577 node changes its IP address in order to resolve the conflict. If a 578 conflict is detected by an intermediate node, the conflicting nodes 579 must somehow be informed about the conflict so that they are able to 580 change their address. This document described two options for 581 conflict notification. 583 5.1.1. Option A 585 This option requires sending a dedicated message via unicast to the 586 duplicate address. The format for this message is specified in 587 Section 6. The destination address is set to the conflicting 588 address. The very conflicting node that caused the inconsistent 589 routing information in the message triggering the conflict detection 590 should change its address. To achieve that, the message should be 591 sent towards the source address in the IP header of the received 592 routing protocol message that triggered the conflict detection. This 593 node then uses its routing table as usual to forward the message to 594 the correct conflicting node. Controlling the next hop towards the 595 conflicting address can be done by using IPv4 loose source routing, 596 IPv6 routing header, or IPv4/IPv6 tunneling. How this is exactly 597 done is TBD. 599 5.1.2. Option B 601 This option informs all nodes in the network about a detected address 602 conflict by adding conflicting addresses to TC and HELLO messages or 603 marking duplicate addresses as such. It was first proposed in [11]. 604 How the marking is exactly done is TBD. 606 5.2. Preventing Routing Table Contamination 608 To prevent the contamination of the routing table with false routing 609 information emerging from an address conflict, information about 610 duplicate addresses MUST NOT be used for calculating routes. If 611 option A is used, a TC message that was used to detect the conflict 612 must be ignored for routing table calculation or must not be 613 forwarded, so that the routing tables in other nodes are not 614 contaminated. If option B is used, TC messages are forwarded, but 615 addresses marked as duplicate in the message MUST be ignored for 616 routing table calculation. 618 5.3. Handling Address Changes 620 Care must be taken when a node changes its IP address, because the 621 bidirectional link states and the MPR selection states of the OLSR 622 protocol daemon are based on the context of the old address. Hence, 623 a node has to set all its link states to asymmetric and remove all 624 addresses from its MPR selector set. Without these modifications, 625 PDAD-NH would immediately detect a conflict of the new address even 626 if it is unique. 628 6. Message Formats 630 6.1. Conflict Resolution Message 632 The message is encapsulated in an OLSR packet header. The message 633 only contains the conflicting address. The message is send to the 634 conflicting address over the last forwarder of the very routing 635 protocol message that triggered the conflict detection. This can be 636 done by IP tunneling, IPv6 routing header or IPv4 loose source 637 option. Message type is TBD. 639 0 1 2 3 640 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 641 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 642 | Conflicting Address | 643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 645 6.2. Changes to TC and HELLO Message 647 How duplicate addresses are added and marked in TC and HELLO messages 648 is TBD. 650 7. Security Considerations 652 TBD 654 8. References 656 8.1. Normative References 658 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 659 Levels", BCP 14, RFC 2119, March 1997. 661 [2] Clausen, T. and P. Jacquet, "Optimized Link State Routing 662 Protocol (OLSR)", RFC 3626, October 2003. 664 [3] Singh, S., "Address autoconfiguration for MANETs: definition and 665 problem statement", draft-singh-autoconf-adp-03 (work in 666 progress), March 2006. 668 8.2. Informative References 670 [4] Narten, T. and R. Draves, "Privacy Extensions for Stateless 671 Address Autoconfiguration in IPv6", RFC 3041, January 2001. 673 [5] Droms, R., "Dynamic Host Configuration Protocol", RFC 2131, 674 March 1997. 676 [6] Droms, R., Bound, J., Volz, B., Lemon, T., Perkins, C., and M. 677 Carney, "Dynamic Host Configuration Protocol for IPv6 678 (DHCPv6)", RFC 3315, July 2003. 680 [7] Cheshire, S., Aboba, B., and E. Guttman, "Dynamic Configuration 681 of IPv4 Link-Local Addresses", RFC 3927, March 2005. 683 [8] Thomson, S. and T. Narten, "IPv6 Stateless Address 684 Autoconfiguration", RFC 2462, December 1998. 686 [9] Thaler, D., "Multi-Subnet MANETs", 687 draft-thaler-autoconf-multisubnet-manets-00 (work in progress), 688 February 2006. 690 [10] Jelger, C., "MANET Local IPv6 Addresses", 691 draft-jelger-autoconf-mla-00 (work in progress), April 2006. 693 [11] Mase, K. and C. Adjih, "No Overhead Autoconfiguration OLSR", 694 draft-mase-manet-autoconf-noaolsr-01 (work in progress), 695 April 2006. 697 [12] Baccelli, E., "OLSR Passive Duplicate Address Detection", 698 draft-clausen-olsr-passive-dad-00 (work in progress), 699 July 2005. 701 [13] Mase, K., "A common framework for autoconfiguration of stand- 702 alone ad hoc networks", draft-mase-autoconf-framework-01 (work 703 in progress), February 2006. 705 [14] Clausen, T., "The Optimized Link-State Routing Protocol version 706 2", draft-clausen-manet-olsrv2-01 (work in progress), 707 September 2005. 709 [15] Perkins, C. and I. Chakeres, "Dynamic MANET On-demand (DYMO) 710 Routing", draft-ietf-manet-dymo-04 (work in progress), 711 March 2006. 713 [16] Weniger, K., "PDAD-OLSR: Passive Duplicate Address Detection 714 for OLSR", draft-weniger-autoconf-pdad-olsr-00 (work in 715 progress), February 2006. 717 [17] Weniger, K., "PACMAN: Passive Autoconfiguration for Mobile Ad 718 hoc Networks", IEEE Journal of Selected Areas of Communications 719 (JSAC), Vol. 23 No. 3, March 2005. 721 [18] Weniger, K., "Address Autoconfiguration in Mobile Ad Hoc 722 Networks: Current Approaches and Future Directions", IEEE 723 Network Magazine , July 2004. 725 [19] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad 726 hoc Networks", IEEE Wireless Communications and Networking 727 Conference (WCNC), New Orleans, USA, March 2003. 729 Appendix A. Illustration of PDAD Algorithms 731 A.1. Notation 733 Node "A" and its OLSR protocol daemon states are depicted with 734 "A(address,sequence number,{neighbor interface address 1, neighbor 735 interface address 2,...})". Non-relevant values as well as broadcast 736 and multicast addresses are represented by "*". Neighboring nodes 737 are connected with dashes (e.g., "A()----B()"), nodes that are not 738 necessarily neighbors with dashes and points (e.g., "A()-...-B()"). 739 The notation for addresses in the IP header is "[src->dst]". TC 740 messages are depicted with "TC(originator address, message sequence 741 number, {neighbor interface address 1, neighbor interface address 742 1,...})" (HELLO messages accordingly with "HE(..)"). "#(X)" denotes 743 that the node has detected a conflict of address X. 745 A.2. PDAD-SA 747 An example scenario is given in Figure 1. Node A is configured with 748 address 1 and sends a TC (or HELLO) message. Node B is a neighbor of 749 node A and is configured with the same address 1. Upon receiving the 750 message and comparing the IP source address with its own address, it 751 detects a conflict of its own address. 753 ---------- ---------- 754 |A(1,*,{*})|-----|B(1,*,{*})| 755 ---------- ---------- 756 [1->*] 757 TC(1,*,{*}) -> 758 #(1) 760 Figure 1: Example of PDAD-SA 762 A.3. PDAD-SN 764 An example scenario is given in Figure 2. Node A with address 1 765 sends a TC message. Node B is located somewhere in the network and 766 is configured with the same address 1. Upon receiving the TC 767 message, node B compares originator address and sequence number with 768 its own address and sequence number counter. Since the addresses are 769 equal and the sequence number in the message is higher than its own 770 counter, it detects the conflict of its own address (it is assumed 771 that node B has checked that a wrap-around cannot be the reason for 772 the sequence number inconsistency). 774 ----------- ----------- 775 |A(1,90,{*})|-...-|B(1,40,{*})| 776 ----------- ----------- 777 [1->*] 778 TC(1,90,{}) -> 779 #(1) 781 Figure 2: Example of PDAD-SN 783 A.4. PDAD-SND 785 An example scenario is given in Figure 3. Node A with address 1 786 sends a TC message. Its message sequence number counter value is 5. 787 Node C is configured with the same address 1, but its message 788 sequence number counter value is 2000. After receiving the TC 789 message sent by node A, node B stores the information contained in 790 the message. When the TC message sent by node C is received by node 791 B, it compares the sequence number with the sequence number of the 792 last TC message received from the same originator address. Assuming 793 a threshold SDNTHRES lower than 1995, it detects a conflict of 794 address 1. 796 ---------- ---------- ------------- 797 |A(1,5,{*})|-...-|B(*,*,{*})|-...-|C(1,2000,{*})| 798 ---------- ---------- ------------- 799 [1->*] 800 TC(1,5,{}) -> 801 [1->*] 802 <- TC(1,2000,{}) 803 #(1) 805 Figure 3: Example of PDAD-SND 807 A.5. PDAD-SNE 809 An example scenario is given in Figure 4. Node A with address 1 810 sends a TC message. Its message sequence number counter value is 5 811 and the neighbor interface addresses are 3 and 4. Node C is 812 configured with the same address 1 and has the same message sequence 813 number counter value, but the neighbor interface addresses are 6 and 814 7. After receiving the TC message sent by node A, node B stores the 815 information in the message. When the TC message sent by node C is 816 received by node B, it compares the sequence number with the sequence 817 number of the last TC message received from the same originator 818 address. Since they are equal, it compares the neighbor interface 819 addresses. Node B detects a conflict of address 1, because at least 820 one neighbor interface address is different. 822 ------------ ---------- ------------ 823 |A(1,5,{3,4})|-...-|B(*,*,{*})|-...-|C(1,5,{6,7})| 824 ------------ ---------- ------------ 825 [1->*] 826 TC(1,5,{3,4}) -> 827 [1->*] 828 <- TC(1,5,{6,7}) 829 #(1) 831 Figure 4: Example of PDAD-SNE 833 A.6. PDAD-SNI 835 An example scenario is given in Figure 5. Node A with address 1 has 836 a message sequence number counter value of 5. Node B is a neighbor 837 of node A and node C is a neighbor of node B. Node C is also 838 configured with address 1. Its message sequence number counter value 839 is 4. After receiving the HELLO message sent by node A, node B 840 stores the information contained in the message. After the HELLO 841 message sent by node C is received by node B, node B compares the 842 sequence number with the sequence number in the last HELLO message 843 received from the same originator address. Since the second HELLO 844 message has a lower sequence number, node B detects a conflict of 845 address 1 (it is assumed that node B has checked that a wrap-around 846 cannot be the reason for the sequence number inconsistency). 848 ---------- ---------- ---------- 849 |A(1,5,{*})|-----|B(*,*,{*})|-----|C(1,4,{*})| 850 ---------- ---------- ---------- 851 [1->*] 852 HE(1,5,{}) -> 853 [1->*] 854 <- HE(1,4,{}) 855 #(1) 857 Figure 5: Example of PDAD-SNI 859 A.7. PDAD-NH 861 An example scenario is given in Figure 6. Node A has address 1 and a 862 Neighbor History (NH) cache containing the addresses 4 and 5. Node B 863 is located somewhere in the network and is configured with address 2. 864 A Node C is a neighbor of node B and is also configured with address 865 1. Node B sends a TC message. Upon receiving the message, node A 866 notices that its own address is part of the neighbor interface 867 addresses of the TC message. Hence, it checks whether the originator 868 address 2 has recently been a symmetric neighbor by consulting its NH 869 table. Since the check is negative, a conflict of address 1 is 870 detected. 872 ---------- ------------ ---------- 873 |A(1,*,{*})|-...-|B(2,*,{1,*})|-----|C(1,*,{*})| 874 |(NH={4,5})| | | | | 875 ---------- ------------ ---------- 876 [2->*] 877 <- TC(2,*,{1,*}) 878 #(1) 880 Figure 6: Example of PDAD-NH 882 A.8. PDAD-LS 884 An example scenario is given in Figure 7. Node A has address 1 and a 885 Neighbor History (NH) cache containing the addresses 4 and 5. Node B 886 is located somewhere in the network, is also configured with address 887 1, and sends a TC message. Upon receiving the message, node A 888 notices that its own address is equal to the originator address. 889 Hence, it checks whether at least one of the neighbor interface 890 addresses has not recently been a neighbor by consulting its NH 891 table. Since this is the case, a conflict of address 1 is detected. 893 ---------- ------------ 894 |A(1,*,{*})|-...-|B(1,*,{2,3})| 895 |(NH={4,5})| | | 896 ---------- ------------ 897 [1->*] 898 <- TC(1,*,{2,3}) 899 #(1) 901 Figure 7: Example of PDAD-LS 903 A.9. PDAD-eNH 905 An example scenario is given in Figure 8. Node A has address 1 and a 906 Neighbor History (NH) cache containing the addresses 2 and 5. Node B 907 is a neighbor of node A and is configured with address 2. Node C is 908 located somethere in the network and has the address 3. Node D is 909 neighbor of node C and is also configured with address 1. After node 910 A has sent a HELLO message, Node C sends a TC message. Upon 911 receiving the messages, node B notices that a neighbor interface 912 address in the TC message is equal to the address of one of its 913 neighbors (1). It then checks the neighbor interface addresses of 914 this neighbor (1) as learned from the last HELLO message from this 915 address and notices that the originator address of the TC message (3) 916 is not part of this set (2). Hence, it concludes that an address 917 conflict may exist. It marks and forwards the TC message even if it 918 is not elected as MPR node for this TC message. Node A receives the 919 TC message and detects the conflict after applying the PDAD-NH 920 algorithm (since address 3 is not part of node A's NH table). 922 ---------- ------------ ------------ ---------- 923 |A(1,*,{2})|-----|B(2,*,{1,*})|-...-|C(3,*,{1,*})|-----|D(1,*,{*})| 924 |(NH={2,5})| | | | | | | 925 ---------- ------------ ------------ ---------- 926 [1->*] 927 HE(1,*,{2}) -> 928 [3->*] 929 <- TC(3,*,{1,*}) -> 930 [2->*] 931 <- TC'(3,*,{1,*}) 932 #(1) 934 Figure 8: Example of PDAD-eNH 936 A.10. Effects of Address Conflicts on MPR Selection 938 Address conflicts within 4 hops distance may influence MPR selection 939 and may lead to limited dissemination of TC messages. For example, 940 in the scenario shown in Figure 9, node C would not forward TC 941 messages received by node D and vice versa, since both nodes assume 942 that they don't have 2-hop-neighbors (only a 1-hop-neighbor with 943 address 2). The network is virtually partitioned with respect to TC 944 message dissemination. This may be a problem for PDAD algorithms 945 based on TC messages, for instance, PDAD-NH or PDAD-SN cannot detect 946 the conflict of address 1 in the example scenario. However, all 947 conflicts within 4 hops can be detected with the combination of 948 algorithms proposed in this draft. After resolving these conflicts, 949 TC messages are again disseminated correctly and conflicts with more 950 than 4 hops between the conflicting nodes can be detected and 951 resolved. In the example scenario, the conflict of address 2 between 952 node B and node E can be detected by PDAD-eNH. After this conflict 953 has been resolved, the conflict of address 1 between node A and F can 954 be detected, e.g., by PDAD-SN or PDAD-NH. See [17] for more details 955 about this problem. 957 ---- ---- ---- ---- ---- ---- 958 |A(1)|-...-|B(2)|-----|C(3)|-----|D(4)|-----|E(2)|-...-|F(1)| 959 ---- ---- ---- ---- ---- ---- 961 Figure 9: Example of MPR selection influenced by address conflict 963 Authors' Addresses 965 Kilian A. Weniger 966 Panasonic R&D Center Germany 967 Monzastr. 4c 968 Langen 63225 969 Germany 971 Phone: +49 6103 766 137 972 Email: kilian.weniger@eu.panasonic.com 974 Kenichi Mase 975 Niigata University 976 Ikarashi 977 Niigata-shi 950-2181 978 Japan 980 Phone: +81 25 262 7446 981 Email: mase@ie.niigata-u.ac.jp 983 Intellectual Property Statement 985 The IETF takes no position regarding the validity or scope of any 986 Intellectual Property Rights or other rights that might be claimed to 987 pertain to the implementation or use of the technology described in 988 this document or the extent to which any license under such rights 989 might or might not be available; nor does it represent that it has 990 made any independent effort to identify any such rights. Information 991 on the procedures with respect to rights in RFC documents can be 992 found in BCP 78 and BCP 79. 994 Copies of IPR disclosures made to the IETF Secretariat and any 995 assurances of licenses to be made available, or the result of an 996 attempt made to obtain a general license or permission for the use of 997 such proprietary rights by implementers or users of this 998 specification can be obtained from the IETF on-line IPR repository at 999 http://www.ietf.org/ipr. 1001 The IETF invites any interested party to bring to its attention any 1002 copyrights, patents or patent applications, or other proprietary 1003 rights that may cover technology that may be required to implement 1004 this standard. Please address the information to the IETF at 1005 ietf-ipr@ietf.org. 1007 Disclaimer of Validity 1009 This document and the information contained herein are provided on an 1010 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1011 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1012 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1013 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1014 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1015 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1017 Copyright Statement 1019 Copyright (C) The Internet Society (2006). This document is subject 1020 to the rights, licenses and restrictions contained in BCP 78, and 1021 except as set forth therein, the authors retain all their rights. 1023 Acknowledgment 1025 Funding for the RFC Editor function is currently provided by the 1026 Internet Society.