idnits 2.17.1 draft-laouiti-manet-olsr-address-autoconf-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 21. -- Found old boilerplate from RFC 3978, Section 5.5 on line 775. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 752. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 759. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 765. ** 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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 631 has weird spacing: '...ultiple gatew...' == Line 674 has weird spacing: '...tection and a...' -- 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 (July 18, 2005) is 6850 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: '11' is defined on line 653, but no explicit reference was found in the text == Outdated reference: A later version (-05) exists of draft-bernardos-manet-autoconf-survey-00 == Outdated reference: A later version (-01) exists of draft-ruffino-conn-scenarios-00 == Outdated reference: A later version (-01) exists of draft-mase-manet-autoconf-noaolsr-00 == Outdated reference: A later version (-03) exists of draft-ruffino-manet-autoconf-multigw-00 == Outdated reference: A later version (-01) exists of draft-clausen-manet-olsrv2-00 == Outdated reference: A later version (-14) exists of draft-ietf-manet-smf-00 -- Obsolete informational reference (is this intentional?): RFC 3315 (ref. '10') (Obsoleted by RFC 8415) -- Obsolete informational reference (is this intentional?): RFC 2462 (ref. '11') (Obsoleted by RFC 4862) Summary: 3 errors (**), 0 flaws (~~), 11 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF MANET C. Adjih 3 Internet-Draft S. Boudjit 4 Expires: January 19, 2006 P. Jacquet 5 A. Laouiti 6 P. Muhlethaler 7 INRIA Rocquencourt, France 8 Pr. Mase 9 Information and Communication 10 Network Lab., Niigata University 11 July 18, 2005 13 Address autoconfiguration in Optimized Link State Routing Protocol 14 draft-laouiti-manet-olsr-address-autoconf-01.txt 16 Status of this Memo 18 By submitting this Internet-Draft, each author represents that any 19 applicable patent or other IPR claims of which he or she is aware 20 have been or will be disclosed, and any of which he or she becomes 21 aware will be disclosed, in accordance with Section 6 of BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt. 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 This Internet-Draft will expire on January 19, 2006. 41 Copyright Notice 43 Copyright (C) The Internet Society (2005). 45 Abstract 47 Several MANET routing protocols have been recently promoted to 48 experimental RFCs. However, autoconfiguration of MANET networks is 49 still an unsettled area. This document proposes a protocol for 50 autoconfiguration for both IPv4 or IPv6. Its corner stone is an 51 conflict-detection algorithm. It aims at conceptual simplicity: 52 essentially, each node periodically sends its addresses and an 53 identifier. Conflicts are detected as identifier mismatches. This 54 protocol might be used with any MANET protocol, although it naturally 55 suits the OLSR routing protocol (on which we focus), with a light 56 increase of control message overhead. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 61 1.1 Changes . . . . . . . . . . . . . . . . . . . . . . . . . 3 62 1.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 63 2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5 64 3. Overview of the Method . . . . . . . . . . . . . . . . . . . . 6 65 3.1 Address Assignment . . . . . . . . . . . . . . . . . . . . 6 66 3.2 Duplicate Address Detection . . . . . . . . . . . . . . . 7 67 3.3 Conflict Resolution . . . . . . . . . . . . . . . . . . . 7 68 3.4 Optional: MANET connected to an external network . . . . . 7 69 3.5 Optional: Routing Table Contamination Avoidance . . . . . 7 70 3.6 Optional: Passive Duplicate Detection . . . . . . . . . . 8 71 4. Duplicate Address Detection Algorithms . . . . . . . . . . . . 9 72 4.1 Overview of the Different Solutions . . . . . . . . . . . 9 73 4.2 First approach . . . . . . . . . . . . . . . . . . . . . . 10 74 4.2.1 Rule 1 . . . . . . . . . . . . . . . . . . . . . . . . 10 75 4.2.2 Rule 2 . . . . . . . . . . . . . . . . . . . . . . . . 10 76 4.3 Second approach . . . . . . . . . . . . . . . . . . . . . 11 77 4.3.1 Rule 2B . . . . . . . . . . . . . . . . . . . . . . . 11 78 4.4 Third approach . . . . . . . . . . . . . . . . . . . . . . 11 79 4.4.1 Rule 2C . . . . . . . . . . . . . . . . . . . . . . . 11 80 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 81 6. Security Considerations . . . . . . . . . . . . . . . . . . . 14 82 A. MAD Message Format . . . . . . . . . . . . . . . . . . . . . . 15 83 B. DAD-MPR flooding algorithm . . . . . . . . . . . . . . . . . . 16 84 C. Precisions for third approach . . . . . . . . . . . . . . . . 18 85 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 86 7.1 Normative References . . . . . . . . . . . . . . . . . . . 19 87 7.2 Informative References . . . . . . . . . . . . . . . . . . 19 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 20 89 Intellectual Property and Copyright Statements . . . . . . . . 22 91 1. Introduction 93 Mobile Ad hoc NETworks (MANETs) are infrastructure-free, highly 94 dynamic wireless networks, where central administration or 95 configuration by the user is very difficult. In hardwired networks 96 nodes usually rely on a centralized server and use a dynamic host 97 configuration protocol, like DHCP[10], to acquire an IP address. 98 Such a solution cannot be deployed in MANETs due to the 99 unavailability of any centralized DHCP server. For small scale 100 MANETs, it may be possible to allocate free IP addresses manually. 102 However, the procedure becomes impractical for a large-scale or open 103 systems where mobile nodes are free to join and leave. Most of the 104 autoconfiguration algorithms proposed for ad hoc networks are 105 independent of the routing protocols and therefore, generate a 106 significant overhead. Using the genuine optimization of the 107 underlying routing protocol can significantly reduce the 108 autoconfiguration overhead. 110 Because traditional IP solutions to autoconfiguration cannot be used 111 as is on MANET networks, a MANET-AUTOCONF effort was set with three 112 initial goals, which include the two following: an "IPv6 stateless 113 autoconfiguration mechanism", and a "mechanism promoting address 114 uniqueness in the situation where different ad hoc networks merge". 115 This document proposes a protocol that addresses these two issues. 116 The third one, "stateful address autoconfiguration mechanism", might 117 be addressed by derivative of the method of the draft. 119 This comprehensive scheme centers on one control message and one 120 mechanism, which ensure at the same time conflict avoidance in the 121 2-hop neighborhood of each node, and conflict avoidance in the entire 122 network. This algorithm operates on multiple interfaces and is shown 123 to work in any case of multiple conflicts, especially during network 124 mergers. 126 1.1 Changes 128 Major changes from version 00 to version 01 130 o Changes in the structure of the document, and important editorial 131 changes. 133 o DAD and MPR flooding is ensured in case of multiple interfaces. 135 o The second (now third) approach does not modify the basic OLSR 136 HELLO message format anymore. 138 o Another approach has been added. 140 1.2 Terminology 142 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 143 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 144 document are to be interpreted as described in RFC2119 [14]. 146 For the OLSR description and terminology, the reader should refer to 147 the OLSR RFC [12]. 149 2. Problem Statement 151 The problem solved by the proposed autoconfiguration protocol is the 152 autoconfiguration in MANET networks. The reader is referred to the 153 autoconfiguration survey in [1], for the general problem statement, 154 and a survey of several proposed solutions. 156 Considering the connectivity scenarios listed in [3], our prime 157 objective is the autoconfiguration of isolated MANETs, but extending 158 it to MANETs intermittently connected, or to connected MANETs is 159 intended and already proposed ([5]). 161 More importantly, our main goal is promoting configured address 162 uniqueness in the situation where different ad hoc networks merge. 163 Precisely, the networks may be isolated, may become partitioned, and 164 may merge, ... . Under these hypothesis, the only way to ensure 165 address uniqueness is that, in the critical case of a merge of two 166 networks, the information about the all the addresses of the first 167 network is compared to the information about all the addresses of the 168 second network. That can be done in direct or indirect ways, with 169 centralized or distributed means (and anything in between). 171 3. Overview of the Method 173 With respect to the problem statement, the method is build around a 174 conceptually simple means of ensuring that information about all 175 addresses is checked: each node sends its lists of addresses 176 periodically, and a node identifier. Hence the approach is fully 177 distributed, and introduces an unique new kind of message. It 178 deliberately favors simplicity at the expense of bandwidth 179 efficiency. At least in the case of the OLSR protocol, this is not 180 an issue. 182 More precisely, our proposed auto-configuration algorithm is 183 structured around three building blocks: 185 1. Address assignment: an IP address is selected by the arriving 186 node. 188 2. Duplicate Address Detection (Conflict Detection): each node 189 checks that there is not another node with the same address. 191 3. Conflict resolution: when a node detects that another node is 192 using the same address, it will select a new address. 194 This method may also integrate a number of optional elements, namely: 196 1. Route contamination avoidance and gradual entry (borrowed from 197 [4]). 199 2. Interface with gateways (see also [5]). 201 3. Passive duplicate detection methods. 203 The following sections give an overview of each part of the protocol. 205 3.1 Address Assignment 207 Numerous schemes can be used to select an IP address. For instance, 208 the node can perform a random selection; another technique is that 209 each node may advertise a set of addresses that (it believes) are not 210 used, for potential newcomers as in [2]. Another method, more 211 direct, is that a neighbor node selects this IP address for the 212 arriving node by control message exchanges [14]. 214 Because it is assumed that the MANET network may be isolated, a 215 default method is to choose an address at random inside a given 216 subnet with MANET_PREFIX: the pool of addresses could be for local 217 use only. For example, it could be reserved by the IANA authority 218 for local MANET forwarding ( i.e, those addresses must not be 219 forwarded outside the MANET network, nor reached from outside). 220 Choice may be more subtle, see Section 3.5. Additional addresses may 221 be added, see Section 3.4. 223 3.2 Duplicate Address Detection 225 As highlighted previously, the DAD algorithm uses a single special 226 control message to perform conflict detection. 228 This control packet includes one identifier and all the addresses of 229 the node. This message is periodically transmitted to the entire 230 network. The identifier of each node is assumed unique (with 231 sufficient probability). If a node receives a message with a 232 different identifier than its own, an address duplication is detected 233 and the node selects a new address. 235 This control message is called MAD, for "Multiple Address 236 Declaration". It is an extension of MID messages for OLSR and it 237 also advertises all acquired addresses of the node. Because it is 238 the central part of this method, it is described in the Section 4. 240 3.3 Conflict Resolution 242 When two nodes A1 and A2 are configured with the same IP address and 243 assuming that there is no packet loss, at least one of these two 244 nodes will receive the MAD message of the other node. Thus the nodes 245 where the conflict lies are bound to discover the conflict, and can 246 resolve it by changing addresses. Since a conflicting node knows via 247 the reception of the MAD control messages the already assigned 248 addresses, the new address must be selected at random among the 249 addresses that are believed to be free. 251 3.4 Optional: MANET connected to an external network 253 When a MANET is connected to an external network, in case of IPv6, 254 the node may receive IPv6 router advertisement messages. The intent 255 of MAD messages was to advertise all the addresses of a node, 256 including newly formed global addresses when such an IPv6 router 257 advertisement is received (diffused by a manet multicast), see [14]. 258 A better and more complete protocol to achieve the same goals (and 259 more) is described in [5], and it can be adapted directly to the 260 method presented here. 262 3.5 Optional: Routing Table Contamination Avoidance 264 In the case that node has just changed its address, an useful 265 technique is to perform some routing table contamination avoidance 266 (pioneered in [4]). It consists into letting a node entering 267 gradually in the network, going through several states: at first it 268 is only recognized by its immediate neighbors, but not advertised, 269 and not used for routing. This gives the node opportunity to detect 270 (passively) an address conflict with an existing node, and change its 271 address. 273 3.6 Optional: Passive Duplicate Detection 275 When the OLSR routing protocol is used (version 1 or version 2), it 276 is possible to use a derivative of passive detection techniques found 277 in NOA-OLSR [4] and [2], and pioneered by PACMAN [9]: the topological 278 information diffused by the OLSR routing protocol is sufficient to 279 detect address conflict. The address conflicts are essentially 280 detected in two ways, as analyzed in [9]: inconsistent topological 281 information (essentially, a node discovers that a control message 282 incorrectly advertises that it has a link), and inconsistent message 283 originators (a node discovers that it is credited for originating a 284 message, which actually, it did not transmit). 286 Using passive techniques, one still need to ensure that control 287 messages are propagated properly. Especially in the case of OLSR 288 with multiple interfaces (but also in the cases given in the figures 289 of [9]), it is necessary to ensure that MPR selection is done 290 properly: we propose that MPR selection is ensured by the propagation 291 of MAD messages at only a distance up to two hops from the 292 originator, (4 hops when conflict is detected, as the algorithms 293 proposed here do), which is enough to guarantee sufficient resolution 294 of short range conflict to permit proper MPR selection. 296 Hence MAD messages are sent only in a limited local area, to 297 guarantee proper MPR selection, at limited cost; and longer range 298 conflicts are detected by passive methods. 300 For completing all theoretical conflict cases, and in order to 301 accelerate the detection by passive methods, in the even rarer case 302 when the topology is symmetric, and nodes in conflict have identical 303 message sequence numbers, we suggest that one bit somewhere in the 304 message may be set randomly in the message (or based on node 305 identifier): this gives an additional 50% chance of resolving the 306 conflict at each generated message. (such a bit that might be set, is 307 the last bit of the message sequence number). 309 4. Duplicate Address Detection Algorithms 311 4.1 Overview of the Different Solutions 313 In order to detect address conflicts, each node diffuses periodically 314 a special message that we call a MAD for ``Multiple Address 315 Declaration'' to the entire network[14]. This control packet 316 includes the node addresses and the node identifier. 318 The node identifier is a sequence of bits of fixed length L which is 319 randomly generated. Hence we are using the standard idea that the 320 probability of two nodes having the same node identifier is low, and 321 the probability of at least one address collision with N nodes, which 322 is the well known ``birthday problem'', can be set arbitrarily low by 323 choosing a large enough value of L (eight bytes are enough to code 324 the random identifier if we consider a network with a maximum of 325 10000 nodes [13] [16]). The MAD message format is depicted in the 326 Appendix A 328 A node detects an address conflict when it receives an MAD message 329 having the same address as its own, but with a different identifier. 330 These situations may happen during network mergers. Actually other 331 nodes will detect the conflict. These nodes could announce the 332 conflict using a special control message. However this approach may 333 induce broadcast storm since many nodes may announce the conflict and 334 special care must be taken to avoid this effect. For that reason we 335 do not recommend this way. An efficient manner to notify the address 336 duplication to the nodes in conflict, consists in allowing the MAD 337 packets to reach all the nodes in the network. 339 Depending on which routing protocol is actually used, the MAD 340 messages may be optimized in several kind of ways. Several cases may 341 be identified: 343 o OLSR [12] 345 o OLSRv2 [6] 347 o A protocol with support for an MPR-based flooding (such as [7] and 348 [8]) 350 o A protocol without an MPR-based optimization 352 In the last case, if the protocol has no MPR-based optimization, the 353 sending of MAD messages is done with the default of using pure 354 flooding. Additionally, whenever OLSR is not used, the MAD messages 355 must be encapsulated in proper packets. 357 Otherwise: when MPR-based flooding is present, to save channel 358 bandwidth the MAD packets should be broadcasted using this MPR-based 359 flooding (either as a MPR-CDS or a genuine MPR flooding). Then, of 360 course, MAD messages are used in order to resolve conflicts, but 361 conflicts themselves can lead to improper MPR selection. Hence a few 362 theoretical situations result some conflicts may not be resolved. 363 This is addressed by special relaying rules for MPR-flooding, and 364 three different approaches: 366 o In first one, designed for OLSR, we suggest to ignore the MPR 367 mechanism for MAD relaying in the one-hop neighborhood and 368 instead, the MAD messages are repeated by all neighbors (one-hop 369 pure flooding). Moreover special rules for address conversion are 370 introduced when using the content of MAD messages. One-hop pure 371 flooding is sufficient for OLSR, hence the overhead is limited. 373 o The second one focuses on protocols different from OLSRv1: for 374 MPR-based flooding protocols, and for OLSRv2, it is necessary that 375 MAD messages are repeated by neighbors and also 2-hop neighbors. 376 This method is a derivative of the previous algorithm, and is 377 slightly more expensive, but more general. 379 o In the third one, MAD messages are also relayed by one-hop 380 neighbors, as in the first approach. Moreover, we also modify the 381 MPR election algorithm of OLSR. The calculation will be based on 382 node identifiers to guarantee the uniqueness of the direct 383 neighbors and the 2-hop neighbors. This leads to a correct MPR 384 set, hence, ensures that the MAD messages reach all the nodes. 386 4.2 First approach 388 This approach is based on new rules for MPR flooding for MAD message 389 (details are given in Appendix B). The proof of correctness of this 390 algorithm is given in [15] (including cases with multiple interfaces 391 and multiple conflicts). The two rules are: 393 4.2.1 Rule 1 395 When a node X receives a MAD message and if node X has a symmetric or 396 asymmetric link with a node Y with the same main address as the one 397 contained in the MAD message, then node X relays this MAD message. 398 When relaying the MAD message the Hop-Count field is set to 1. 400 4.2.2 Rule 2 402 When a node X receives a HELLO message from a node Y, this HELLO 403 contains interface addresses of 2-hop neighbors of X(1-hop neighbors 404 of Y). To convert such addresses into main addresses the node X uses 405 MAD messages that are relayed by Y. The rule 2 will actually avoid 406 inconsistent main address conversions for 2-hop neighbors. This is 407 essential in the case of nodes with multiple interfaces. 409 4.3 Second approach 411 In this approach, it is assumed that the rule 2 of the first approach 412 can no longer be applied, because, for instance, the protocol does 413 not use or has not MID/MAD messages. In this case, the rule 2 is 414 replaced the rule 2B, and the details are easily derived from 415 Appendix B: 417 4.3.1 Rule 2B 419 When a node X receives a MAD message, which it has not already 420 retransmitted, with a hop count field equal to one, it relays it. 421 The rule 2B will actually make all the 2-hop neighbors retransmit the 422 message. 424 4.4 Third approach 426 An issue with this first approach is that the conflicts at 2-hop must 427 be resolved before one can be sure that the MAD messages are 428 successfully transmitted within the entire network. An ideal 429 property would be that the MAD messages reach all the nodes in the 430 network irrespectively of potential address duplications. This 431 property can be achieved if the MPR flooding continues to work in 432 presence of address duplication. A solution is then to base the 433 selection of MPR not on addresses but on node identifiers. With the 434 assumption that node identifiers are globally unique in the network, 435 one can be sure that there will not be identifier duplications at two 436 hops of a given node and thus the selection of MPRs will be correct. 437 This solution can be simply implemented, the selection of the MPRs 438 must follow the principle defined in the OLSR protocol except that 439 the base for the selection must be the node identifiers i.e. the 440 2-hop coverage must be considered not on the addresses but on the 441 node identifiers. 443 This is achieved in this section by providing an alternative to the 444 second rule. The Rule 2 is replaced by a Rule 2C: 446 4.4.1 Rule 2C 448 The MPR calculation is modified, by using node identifiers. Each 449 address is converted to a node identifier (using a method described 450 later): as a result the node computing its MPR set, has its 1-hop and 451 2-hop topology represented by links between node identifiers. 453 Details about applying rule 2C in practice are found in Appendix C. 455 5. IANA Considerations 457 One new type of control message is defined in this protocol, for MAD 458 messages. 460 6. Security Considerations 462 This memo does not specify any security considerations. 464 Appendix A. MAD Message Format 466 An example of MAD message format is depicted in the following figure 468 0 1 2 3 469 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 470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 471 | | 472 | Originator node identifier | 473 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 474 | OLSR Interface Address | 475 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 476 | OLSR Interface Address | 477 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 478 | ... | 479 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 481 Figure 1 483 An alternative is to prepend an "Originator node identifier" OLSR 484 message, to MeID messages 486 Appendix B. DAD-MPR flooding algorithm 488 Let us recall the assumptions here. Each node A periodically sends a 489 message M including: 491 o The originator address of A, Orig_A, in the OLSR message header. 493 o The list of interface addresses of node A in the message it self. 495 o The message sequence number, mssn, in the OLSR message header. 497 o The node identifier ID_A (a string of bits) in the message itself. 499 The message is propagated by MPR flooding to the other nodes ; but 500 for DAD-MPR Flooding, the duplicate table of OLSR is modified, so 501 that it also includes the node identifier list in the duplicate 502 tuple. That is, a duplicate tuple, includes the following 503 information: 505 o The originator address (as in OLSR standard duplicate table). 507 o The message sequence number (as in OLSR standard duplicate table). 509 o The list of node identifiers. 511 o The list of interface addresses on which the MAD message was 512 received. 514 The detailed algorithm for DAD-MPR Flooding is the following: 516 o When a node B receives a MAD message M on its interface B(i) from 517 node C with originator Orig_A, with message sequence number mssn, 518 and with node identifier ID_A, it performs the following tasks: 520 1. If a duplicate tuple exists with the same originator Orig_A, 521 the same message sequence number mssn, the ID_A is in the list 522 of node identifiers, and the interface address of B(i) is in 523 the list of interface addresses on which the message has 524 already been received, Then, the message is ignored (it has 525 already been processed). The algorithm stops here. 527 2. Else one of the following situations occurs : 529 1. A duplicate tuple exists with the same originator Orig_A, 530 the same message sequence number mssn, ID_A is in the list 531 of node identifiers, but the address of B(i) is not in the 532 list of interface addresses on which the MAD message has 533 already been received: then, the message must be 534 processed. The address of B(i) is added to the list of 535 interface addresses on which the message has already been 536 received. 538 2. A duplicate tuple exists with the same originator Orig_A 539 and the same message sequence number, but ID_A is not in 540 the list of node identifiers: then, a conflict is detected 541 (address Orig_A is duplicated). ID_A is added to the list 542 of node identifiers. 544 3. A duplicate tuple exists with the same originator Orig_A, 545 but with a different message sequence number and ID_A is 546 not in the list of node identifiers: then, a conflict is 547 detected (address Orig_A is duplicated). A duplicate 548 tuple is created with the originator address, message 549 sequence number and list of node identifiers containing 550 only ID_A. 552 4. No duplicate tuple exists. A new one is created with the 553 originator address Orig_A, message sequence number mssn, 554 list of interface addresses on which the MAD message has 555 already been received containing only the address of B(i), 556 and list of node identifiers containing only ID_A. 558 3. The MAD messages should be relayed if one or more of the 559 following rules are met: 561 1. C had chosen this current receiving node, B, as an MPR. 563 2. Node B has a symmetric or asymmetric link with a node Y 564 with the same main address as the one contained in the MAD 565 message M. In such a case, the Hop-Count field is set to 1 566 before message M retransmission. 568 o When a node X receives a HELLO message from a node Y, this HELLO 569 contains interface addresses of 2-hop neighbors of X. The node X 570 uses MAD messages relayed by Y to convert such addresses into main 571 addresses. 573 Appendix C. Precisions for third approach 575 The goal is to obtain the one hop neighborhood and the two-hop 576 neighborhood with node identifiers in place of addresses. 578 Converting main addresses of neighbor to node identifiers is easily 579 done: when receiving the MAD messages from neighbors, the main 580 address can be identified to be the address of a neighbor, and the 581 node identifier is given. Hence the node may record the information 582 mapping main addresses of neighbors to their identifiers. 584 Converting main addresses of two-hop neighbors to node identifiers is 585 less direct: however the information obtained thanks to the fact that 586 MAD messages from two-hop neighbors are always retransmitted by one- 587 hop neighbors. Such MAD messages are identified by the fact that 588 they arrive with a hop count field (corrected by Rule 1 is 589 necessary), equal to 1 ; in the following, they are called two-hop 590 MAD messages. The receiver node can thus maintain the information 591 Two-Hop Identifier Table: (neighbor address, two-hop neighbor 592 addresses list, two-hop neighbor identifier) in or in addition to, 593 the MID/MAD information base. Now taking advantage of the fact that 594 conflicts at distance 1 to 3 are resolved anyway by Rule 1, it is 595 know that one neighbor will retransmit neighbor MAD message (two-hop 596 MAD messages for the receiver) that have all different addresses: 597 otherwise there would be a 2-hop conflict, necessarily resolved. 598 Thus the mapping deduced from the Two-Hop Identifier Table, (neighbor 599 main address, two-hop neighbor main address) -->two-hop neighbor 600 identifier is unique (and corresponds to reality). 602 Note also, that the information containted in the two-hop identifier 603 table, should be also used for processing Hello messages (converting 604 interface addresses to main addresses) so that the two-hop neighbor 605 main address in the two-hop tuple is the actual main address. 607 7. References 609 7.1 Normative References 611 7.2 Informative References 613 [1] Bernardos, C. and M. Calderon, "Survey of IP address 614 autoconfiguration mechanisms for MANETs", 615 draft-bernardos-manet-autoconf-survey-00 (work in progress), 616 July 2005. 618 [2] Clausen, T. and E. Baccelli, "Simple MANET Address 619 Autoconfiguration", draft-clausen-manet-address-autoconf-00 620 (work in progress), February 2005. 622 [3] Ruffino, S., "Connectivity Scenarios for MANET", 623 draft-ruffino-conn-scenarios-00 (work in progress), 624 February 2005. 626 [4] Mase, K. and C. Adjih, "No Overhead Autoconfiguration OLSR", 627 draft-mase-manet-autoconf-noaolsr-00 (work in progress), 628 May 2005. 630 [5] Ruffino, S. and P. Stupar, "Automatic configuration of IPv6 631 addresses for nodes in a MANET with multiple gateways", 632 draft-ruffino-manet-autoconf-multigw-00 (work in progress), 633 June 2005. 635 [6] Clausen, T., "The Optimized Link-State Routing Protocol version 636 2", draft-clausen-manet-olsrv2-00 (work in progress), 637 July 2005. 639 [7] Perkins, C., "Multicast With Minimal Congestion Using Connected 640 Dominating Sets", draft-perkins-manet-smurf-00 (work in 641 progress), July 2005. 643 [8] Macker, J., "Simplified Multicast Forwarding for MANET", 644 draft-ietf-manet-smf-00 (work in progress), July 2005. 646 [9] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad 647 hoc Networks", March 2003. 649 [10] "R. Droms, Ed.,J. Bound, B. Volz, T. Lemon, C. Perkins, M. 650 Carney, 'Dynamic Host Configuration Protocol for IPv6 651 (DHCPv6)', IETF RFC 3315, July 2003". 653 [11] "S. Thomson, T. Narten, 'IPv6 Stateless Address 654 Autoconfiguration', IETF RFC 2462, December 1998". 656 [12] "T. Clausen, Ed., P. Jacquet, Ed., 'Optimized Link State 657 Routing Protocol', Request for Comments (Experimental) 3626, 658 Internet Engineering Task Force, October 2003". 660 [13] "S.Boudjit, A. Laouiti, P. Muhlethaler, C. Adjih, 'Duplicate 661 address detection and autoconfiguration in OLSR', INRIA 662 Research Report-5475, Jan 2005". 664 [14] "A. Laouiti, S. Boudjit, P. Minet and C. Adjih, 'OLSR for 665 IPv6 networks', Proceedings of Med-Hoc-Net, June 2004,Bodrum, 666 Turkey". 668 [15] "C. Adjih, S.Boudjit, P. Jacquet, A. Laouiti, P. Muhlethaler, 669 'An Advanced Configuration and Duplicate Address Detection 670 mechanism for a multi-interface OLSR Network', INRIA Research 671 Report, Jul 2005". 673 [16] "S. Boudjit, C. Adjih, A. Laouiti, P. Muhlethaler,'Duplicate 674 address detection and autoconfiguration in OLSR', Proceedings 675 of IEEE SAWN 2005, May 2005, Maryland, USA". 677 Authors' Addresses 679 Cedric Adjih 680 INRIA Rocquencourt, France 681 Project HIPERCOM 682 Domaine de Voluceau -Rocquencourt 683 BP 105 684 Le Chesnay 78153 cedex 685 France 687 Phone: +33 1 3963 5215 688 Email: cedric.adjih@inria.fr 690 Saadi Boudjit 691 INRIA Rocquencourt, France 692 Project HIPERCOM 693 Domaine de Voluceau -Rocquencourt 694 BP 105 695 Le Chesnay 78153 cedex 696 France 698 Phone: +33 1 3963 5039 699 Email: saadi.boudjit@inria.fr 700 Philippe Jacquet 701 INRIA Rocquencourt, France 702 Project HIPERCOM 703 Domaine de Voluceau -Rocquencourt 704 BP 105 705 Le Chesnay 78153 cedex 706 France 708 Phone: +33 1 3963 5263 709 Email: philippe.jacquet@inria.fr 711 Anis Laouiti 712 INRIA Rocquencourt, France 713 Project HIPERCOM 714 Domaine de Voluceau -Rocquencourt 715 BP 105 716 Le Chesnay 78153 cedex 717 France 719 Phone: +33 1 3963 5088 720 Email: anis.laouiti@inria.fr 722 Paul Muhlethaler 723 INRIA Rocquencourt, France 724 Project HIPERCOM 725 Domaine de Voluceau -Rocquencourt 726 BP 105 727 Le Chesnay 78153 cedex 728 France 730 Phone: +33 1 3963 5278 731 Email: paul.muhlethaler@inria.fr 733 Pr. Kenichi Mase 734 Information and Communication Network Lab.,Niigata University 735 Niigata University 736 Niigata 950-2181, 737 Japan 739 Phone: +81 25 262 7446 740 Email: mase@ie.niigata-u.ac.jp 741 URI: http://www.net.ie.niigata-u.ac.jp/ 743 Intellectual Property Statement 745 The IETF takes no position regarding the validity or scope of any 746 Intellectual Property Rights or other rights that might be claimed to 747 pertain to the implementation or use of the technology described in 748 this document or the extent to which any license under such rights 749 might or might not be available; nor does it represent that it has 750 made any independent effort to identify any such rights. Information 751 on the procedures with respect to rights in RFC documents can be 752 found in BCP 78 and BCP 79. 754 Copies of IPR disclosures made to the IETF Secretariat and any 755 assurances of licenses to be made available, or the result of an 756 attempt made to obtain a general license or permission for the use of 757 such proprietary rights by implementers or users of this 758 specification can be obtained from the IETF on-line IPR repository at 759 http://www.ietf.org/ipr. 761 The IETF invites any interested party to bring to its attention any 762 copyrights, patents or patent applications, or other proprietary 763 rights that may cover technology that may be required to implement 764 this standard. Please address the information to the IETF at 765 ietf-ipr@ietf.org. 767 Disclaimer of Validity 769 This document and the information contained herein are provided on an 770 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 771 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 772 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 773 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 774 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 775 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 777 Copyright Statement 779 Copyright (C) The Internet Society (2005). This document is subject 780 to the rights, licenses and restrictions contained in BCP 78, and 781 except as set forth therein, the authors retain all their rights. 783 Acknowledgment 785 Funding for the RFC Editor function is currently provided by the 786 Internet Society.