idnits 2.17.1 draft-mase-manet-autoconf-noaolsr-00.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 2725. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2702. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2709. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2715. ** 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 -- 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 (May 26, 2005) is 6908 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) No issues found here. Summary: 3 errors (**), 0 flaws (~~), 2 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 MANET Pr. Mase 3 Internet-Draft C. Adjih 4 Expires: November 27, 2005 Information and Communication 5 Network Lab., Niigata University 6 May 26, 2005 8 No Overhead Autoconfiguration OLSR 9 draft-mase-manet-autoconf-noaolsr-00 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 November 27, 2005. 36 Copyright Notice 38 Copyright (C) The Internet Society (2005). 40 Abstract 42 This document specifies one method for autoconfiguration for the 43 Optimized Link State Routing (OLSR) protocol for ad hoc networks. 44 OLSR is a routing protocol for mobile ad hoc networks, designed for 45 use in multi-hop wireless ad hoc networks ; and as such it specifies 46 how individual nodes can construct routes to each other. To achieve 47 this, it relies on preliminary assignment of unique IP addresses to 48 OLSR interfaces ; hence the task of assigning addresses to 49 interfaces, and checking their uniqueness is defined externally. 50 This document proposes a complementary method, called "No Overhead 51 Autoconfiguration for OLSR" (NOA-OLSR), to perform this task of 52 ensuring uniqueness (Duplicate Address Detection, DAD) of addresses 53 which have been selected. This method consists of modifications in 54 the OLSR specification. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 59 2. Autoconfiguration Method Overview . . . . . . . . . . . . . . 6 60 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 9 61 4. Autoconfiguration Algorithms . . . . . . . . . . . . . . . . . 11 62 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 11 63 4.2 Address Selection . . . . . . . . . . . . . . . . . . . . 11 64 4.3 Duplicate Address Detection . . . . . . . . . . . . . . . 11 65 4.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . 11 66 4.3.2 Notation . . . . . . . . . . . . . . . . . . . . . . . 12 67 4.3.3 Neighbor Duplicate Address Detection . . . . . . . . . 13 68 4.3.3.1 Rule R1 . . . . . . . . . . . . . . . . . . . . . 13 69 4.3.4 Two-hop duplicate address detection . . . . . . . . . 14 70 4.3.4.1 Rule R2 . . . . . . . . . . . . . . . . . . . . . 14 71 4.3.4.2 Rule R3 . . . . . . . . . . . . . . . . . . . . . 14 72 4.3.5 Multihop duplicate address detection . . . . . . . . . 15 73 4.3.5.1 Multihop DAD with two TC generators . . . . . . . 16 74 4.3.5.2 Multihop DAD with two non-generators . . . . . . . 17 75 4.3.5.3 Multihop DAD with one TC Generator and one 76 Non-Generator . . . . . . . . . . . . . . . . . . 21 77 4.3.5.4 Three-hop DAD, Specific Case . . . . . . . . . . . 24 78 4.4 Sequence Number Consistency . . . . . . . . . . . . . . . 25 79 4.4.1 Minimum Wrap-Around Limit . . . . . . . . . . . . . . 25 80 4.4.2 HELLO Sequence Number Consistency . . . . . . . . . . 25 81 4.4.3 TC Sequence Number Consistency . . . . . . . . . . . . 26 82 4.5 Autoconfiguration State . . . . . . . . . . . . . . . . . 27 83 4.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . 27 84 4.5.2 Functionning . . . . . . . . . . . . . . . . . . . . . 27 85 4.6 Node Familiarity . . . . . . . . . . . . . . . . . . . . . 29 86 5. Autoconfiguration Specifications . . . . . . . . . . . . . . . 30 87 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 30 88 5.2 Information Repository . . . . . . . . . . . . . . . . . . 30 89 5.2.1 Autoconfiguration State . . . . . . . . . . . . . . . 30 90 5.2.2 State Information Base . . . . . . . . . . . . . . . . 30 91 5.2.3 Duplicate Set . . . . . . . . . . . . . . . . . . . . 31 92 5.2.3.1 Message Content Identifier . . . . . . . . . . . . 31 93 5.2.4 Set and Unset Fields . . . . . . . . . . . . . . . . . 32 94 5.3 Address Selection and Address Change . . . . . . . . . . . 32 95 5.3.1 Address Selection . . . . . . . . . . . . . . . . . . 32 96 5.3.2 Address Change . . . . . . . . . . . . . . . . . . . . 33 98 5.4 State Set Update . . . . . . . . . . . . . . . . . . . . . 34 99 5.4.1 Populating the State Set . . . . . . . . . . . . . . . 34 100 5.4.2 State Tuple Update . . . . . . . . . . . . . . . . . . 35 101 5.4.3 Associated State Tuple Retrieval . . . . . . . . . . . 36 102 5.4.4 State Tuple: HELLO information update . . . . . . . . 36 103 5.4.5 State Tuple: TC information update . . . . . . . . . . 37 104 5.4.6 State Tuple: MPR information update . . . . . . . . . 37 105 5.4.7 Familiarity . . . . . . . . . . . . . . . . . . . . . 37 106 5.5 Changes in Message Processing . . . . . . . . . . . . . . 38 107 5.5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . 38 108 5.5.2 Packet Processing and Message Flooding . . . . . . . . 38 109 5.5.2.1 Special Retransmission . . . . . . . . . . . . . . 39 110 5.5.2.2 Special Duplicate Tuple Creation . . . . . . . . . 39 111 5.5.3 Autoconfiguration Message Pre-Processing . . . . . . . 40 112 5.5.3.1 Hello Message Pre-Processing . . . . . . . . . . . 40 113 5.5.3.2 TC Message Pre-Processing . . . . . . . . . . . . 41 114 5.5.4 Autoconfiguration Message Post-Processing . . . . . . 43 115 5.6 Changes in OLSR Message Processing . . . . . . . . . . . . 43 116 5.6.1 Changes in HELLO Message Format . . . . . . . . . . . 43 117 5.6.2 Changes in HELLO Message Processing . . . . . . . . . 44 118 5.6.2.1 State Set Update from HELLO . . . . . . . . . . . 46 119 5.6.3 Changes in HELLO Message Generation . . . . . . . . . 47 120 5.6.4 Changes in TC Message Format . . . . . . . . . . . . . 48 121 5.6.5 Changes in TC Message Processing . . . . . . . . . . . 48 122 5.6.5.1 State Set Update from TC . . . . . . . . . . . . . 49 123 5.6.5.2 Conflict detection based on TC message content . . 49 124 5.6.5.3 Dismissed TC messages . . . . . . . . . . . . . . 50 125 5.6.5.4 Dismissed addresses in TC messages . . . . . . . . 50 126 5.6.6 Changes in TC Message Generation . . . . . . . . . . . 51 127 5.6.7 Message Type for HELLO and TC Messages . . . . . . . . 53 128 5.7 Changes in MPR Computation . . . . . . . . . . . . . . . . 53 129 5.8 Changes in Routing Table Calculation . . . . . . . . . . . 54 130 6. Proposed Values for Constants . . . . . . . . . . . . . . . . 55 131 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 56 132 8. Limitations and interoperability considerations . . . . . . . 57 133 8.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . 57 134 8.2 Interoperability with Standard OLSR . . . . . . . . . . . 58 135 8.2.1 Considerations for Interoperability with Standard 136 OLSR . . . . . . . . . . . . . . . . . . . . . . . . . 58 137 8.2.2 Considerations for Isolation from Standard OLSR 138 Nodes . . . . . . . . . . . . . . . . . . . . . . . . 59 139 9. Requirements notation . . . . . . . . . . . . . . . . . . . . 61 140 10. Security Considerations . . . . . . . . . . . . . . . . . . 62 141 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 63 142 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 64 143 12.1 Normative References . . . . . . . . . . . . . . . . . . . 64 144 12.2 Informative References . . . . . . . . . . . . . . . . . . 64 145 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 65 146 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 147 Intellectual Property and Copyright Statements . . . . . . . . 67 149 1. Introduction 151 A mobile ad hoc network is a collection of nodes, which collaborate 152 to each other without depending on centralized control for enabling 153 wireless communication among nodes. When two nodes are within direct 154 transmission range, they communicate directly (one hop wireless 155 communication) ; and otherwise they communicate using other nodes as 156 intermediary nodes (multihop wireless communication), where the 157 intermediary nodes act as routers for forwarding IP datagrams. 158 Accordingly, routing is a key problem for mobile ad hoc networks and 159 many routing protocols have been proposed. In IETF, in the MANET 160 working group, two proactive routing protocols, OLSR [3] and TBRPF 161 [4], and two reactive routing protocols, AODV [5] and DSR [6] are or 162 will progress to experimental RFC status. However these routing 163 protocols assume that each node has been assigned an unique IP 164 address on each of its network interfaces. IP address 165 autoconfiguration is therefore an important pratical issue and 166 accordingly, many autoconfiguration methods for various types of 167 MANET networks have been proposed. 169 Many conventional methods are organized independently from routing 170 protocols so that they can be used for any MANET regardless of the 171 routing protocols. Some other methods are intended to work jointly 172 with the routing protocols to improve efficiency of IP address 173 autoconfiguration and duplicated address detection. For example, 174 information about IP addresses in use can be collected with support 175 of the routing protocol and can be used in selecting a new free 176 addresses for a node seeking address allocation. Unfortunately, all 177 of these proposed methods are rather expensive as they require 178 significant control message overhead for either avoiding or resolving 179 address conflicts. 181 We propose a novel IP address autoconfiguration method for MANET with 182 proactive routing for OLSR. Our method is an duplicate address 183 detection without overhead based on properties of proactive link 184 state routing protocols. The algorithmic and research related aspect 185 can be find in the joint publication [9]. 187 2. Autoconfiguration Method Overview 189 In this section, an overview of the autoconfiguration method is 190 given, followed by a description of the structure of the document. 192 The autoconfiguration algorithm detailed in this document applies to 193 the OLSR protocol, and changes its operation. The node is assumed to 194 implement the OLSR protocol ([3], thereafter denoted "standard 195 OLSR"), complemented by the modifications specified here 196 (thenceforth, "NOA-OLSR"). The node is also assumed to operate in a 197 OLSR MANET environment in which the limitations and restrictions 198 enumerated in Section 8 are respected. 200 Under these assumptions, an OLSR node running NOA-OLSR will proceed 201 as follows. An address is initially selected for its OLSR interface 202 (manually, or using the autoconfiguration methods suggested in this 203 document). Then, the node runs the OLSR protocol using this address, 204 while at the same time constantly checking that it is not conflicting 205 with the address of another node in the network (using the detection 206 algorithm of this document). Finally, it doesn't run fully OLSR 207 protocol initially, because it might be entering in a network where 208 its address could be already used by another node, and it would 209 possibly break routes of nodes which are already running. Instead, 210 the node goes through several states, in the last of which, only, the 211 node will ultimately run the full OLSR protocol. Similarily, in 212 order to avoid routing table contamination, the other nodes avoid 213 relying on this node initially, and will rely on it for routing and 214 forwarding messages, when it has reached proper states. 216 To sum up, the autoconfiguration of an OLSR node includes in three 217 parts: 219 o Address selection 221 o Ongoing duplicate address detection 223 o Gradual entry in the OLSR network and routing table contamination 224 avoidance 226 Considering the address selection, it is actually a peripherical 227 issue of the protocol described in this document, because it is 228 fairly independent of it. Hence an overview of address selection is 229 provided, along with guidelines, and pointers to relevant references. 231 The ongoing duplicate address detection is the main addition to the 232 OLSR protocol, detailed in section Section 4.3 is , checking for 233 inconsistencies in the routing protocol messages to diagnose 234 duplicate address detection, using variants of the ideas pioneered by 236 [8]: 238 o The first kind of inconsistency is based on information included 239 in OLSR messages (such as HELLO messages and TC messages): many 240 cases of duplicate address in one MANET network result into 241 inconsistent information being received ; topology information, 242 for instance. 244 o The second kind of inconsistency is based on sequence numbers: 245 when two nodes, which selected the same IP address, are present in 246 a network, they would send control messages that will be 247 inconsistent. 249 Finally the protocol introduces a state for each OLSR node, the 250 "autoconfiguration state". As mentioned, it allows one OLSR node 251 with a newly selected address to enter gradually in running OLSR 252 network, by sending messages which will be used by more and more 253 nodes. At the same time, it also prevents routing table calculation 254 contamination by ensuring that routes go through nodes which have 255 been present in the network long enough for the duplicate address 256 detection to have been performed. The description of the 257 autoconfiguration state is given in section Section 4.5. 259 The description of the three parts constitutes the major part of this 260 document. However, they include both algorithm aspects (such as how 261 and why some DAD rule is used), and detailed specifications (such as 262 the information bases used to implement the protocol). The choice 263 was made to divide the document in two parts: first the algorithmic 264 part which describe the ideas used, then the detailed specifications. 265 Including some additional sections, the remaining of this document is 266 organized as follows: 268 o Section 3 collects specific terminology used 270 o Section 4 provides the high-level, algorithmic, part of this 271 document. It includes: 273 * Address selection. 275 * Ongoing duplicate address detection. 277 * Principles behind checking sequence number consistency of 278 messages. 280 * Gradual entry in the OLSR network and routing table 281 contamination avoidance. 283 o Section 5 provides the specification of NOA-OLSR. It includes: 285 * Description of the additions and changes to the information 286 repository of OLSR. 288 * Population of (new) state set. 290 * Constraints of address selection. 292 * Changes in packet processing, in OLSR message processing and 293 OLSR message generation. 295 * Changes in MPR computation and routing table calculation. 297 3. Terminology 299 This section provides definition for terms that have a specific 300 meaning to the protocol specified in this document and that are used 301 throughout the text. 303 Address Conflict: When two nodes in the same MANET network share the 304 same address, the situation is described as an "Address Conflict". 305 The nodes involved are "conflicting nodes" and their shared 306 address is called "conflicting address". Conflicting nodes may 307 each send one message with the same sequence number and same 308 message type: such messages are denoted "conflicting messages". 310 Autoconfiguration State: The current autoconfiguration state of the 311 node, one of HELLO, TOPOLOGY, and NORMAL, which indicates what 312 messages it should (or should not) generate and processing it 313 should (or should not) do (see Section 4.5). 315 Busy Address: An address which is being used by some node in the 316 network (see Section 4.2). 318 Duplicate Address Detection (DAD): Duplicate address detection is the 319 action of detecting address conflict, the situation where some 320 nodes are using the same address in the same MANET network. 322 Duplicate Address Detection Rule (DAD Rule): A duplicate address 323 detection rule is one rule of this document, which used to detect 324 the existence of address conflict (see Section 4.3). 326 Familiar Address (Node): An address is familiar for a node, if the 327 node has seen it in an OLSR message, for a sufficiently long 328 period of time (see Section 4.6 and Section 5.4.7). A node is 329 familiar for another node if it has a familiar address for this 330 other node. An address or a node which is not familiar is said 331 "unfamiliar". 333 Message Content Identifier: A message content identifier is computed 334 internally by the node to differentiate between the content of 335 different messages, independently of the message header (see 336 Section 5.2.3.1). 338 Message Content Identifier Generation Method: The message content 339 identifier generation method, is the method that one node 340 implements to compute a message content identifier from the 341 content of a message (see Section 5.2.3.1). 343 NOA-OLSR: "NOA-OLSR" is the protocol specified by this document. It 344 is the standard OLSR protocol [3] with the additions and changes 345 specified in this document. 347 Routing Table Contamination Avoidance: Routing table contamination 348 avoidance is the idea of preserving the routing table from 349 incorrect information due to address conflict. This is achieved 350 by using the autoconfiguration state (see Section 4.5). 352 Sequence Number Consistency: All OLSR messages have a sequence 353 number. One trademark of duplicate addresses, is sequence numbers 354 of different messages, which could not result from a correct 355 implementation of the OLSR protocol (such as decrease in sequence 356 numbers, etc.). The properties of sequence numbers which would 357 result from the normal OLSR protocol implementation are termed 358 "Sequence number consistency" (see Section 4.4). 360 Standard OLSR: The terms "standard OLSR protocol" refer to the OLSR 361 protocol specified in [3]. The term "standard" is meant to 362 differentiate with the "non-standard" OLSR protocol proposed in 363 this document (thereafter, "NOA-OLSR"). It is not meant to 364 express its normative status within IETF or standardization 365 organizations. 367 TC Generator: A node which generates TC messages (as originator). 369 4. Autoconfiguration Algorithms 371 4.1 Overview 373 This section provides a high-level view of the method used for 374 autoconfiguration of the node: address selection, duplicate address 375 detection based on rules, principles for sequence number consistency, 376 use of the autoconfiguration state. The detailed specifications of 377 the method are in Section 5. 379 4.2 Address Selection 381 When a node is present in a MANET, it can monitor the protocol 382 message exchanges and collect information regarding the addresses in 383 use, the "busy address list". It can then selects its own address 384 from the pool of free addresses by avoiding the busy address list. 385 With OLSR, it is possible for each node to obtain busy address 386 information through routing control messages received from other 387 nodes (such information is available as part of the State Set 388 introduced in Section 4.5). 390 This document doesn't specify how the addresses should be selected, 391 apart from the fact any selected address should not be the "busy 392 address list". 394 Some discussions and references about address selection (including 395 IPv4 and IPv6 stateless address autoconfiguration) can be found, for 396 instance, in the document [7]. 398 4.3 Duplicate Address Detection 400 4.3.1 Overview 402 Duplicate Address Detection is performed passively, i.e., without 403 additional control messages. Some various passive DAD techniques 404 were proposed in [8], we propose some others. 406 In this section, the detection algorithms are detailed. Protocol 407 specifications are given in a later section. 409 In a MANET network with nodes running the OLSR, several different 410 scenarios of address conflicts may occur. There are classified in 411 three separated cases: 413 Neighbor duplicate address detection: in this case, two neighbor 414 nodes (in range of each other) have selected the same address. 416 Two-hop duplicate address detection: in this case, two nodes which 417 have selected the same address are two-hop neighbors. That is, 418 there is another node in the network which is the neighbor of 419 those both nodes. 421 Multihop duplicate address detection: in this case, the two nodes in 422 conflict are separated by two nodes or more. 424 The three cases of duplicate address are different in that they can 425 be detected by different methods: for instance the multihop duplicate 426 address detection requires the use of TC message information, while 427 the first two cases need not. 429 Also, an additional case is added: it's a specific multihop address 430 conflict case, where the address conflict results in deficiencies in 431 the MPR selection. 433 4.3.2 Notation 435 In the Section 4.3, the following conventions are used to describe 436 the duplicate address conflict cases for the algorithms: 438 o Capital letters are used to denote different nodes: such as "A", 439 "B", "C", etc... 441 o Numbers are used to represent different addresses, such as "1", 442 "2", "3", etc... 444 o The following notation is employed to represent the node "A" which 445 has the address "1": "A{1}". In the event of an address conflict, 446 two nodes may be using the same address, such as "A{1}" and "B{1}" 447 for instance. 449 o Each DAD rule is associated to a figure which graphically 450 represents the topology. An example is given on Figure 1: one 451 node "A" with address "1". In the figures which will follow, the 452 nodes which should apply the DAD rule, are highlighted by the mark 453 "**", like "A" is, on the sample figure. 455 +--------------+ 456 | ** Node A{1} | 457 +--------------+ 459 Figure 1 461 4.3.3 Neighbor Duplicate Address Detection 463 In the case of "neighbor duplicate address", two conflicting nodes 464 are neighbors (see Figure 2). This case is special since many 465 different non-OLSR methods could be used to detect the conflict: 466 because the neighbor nodes would receive messages from each other 467 directly, as they would, for instance, if they were connected on a 468 Ethernet network. Thus, most of methods designed for (non-MANET) IP 469 networks, such as IPv4 autoconfiguration detection methods or IPv6 470 DAD, could be used. 472 Still, due to topology changes such methods could fail, or could not 473 be available in a node. Hence a rule to detect conflicts at the OLSR 474 protocol level in this case is proposed. At mininum, the two OLSR 475 nodes should at least periodically generate HELLO messages, hence the 476 following duplicate address detection rule is used: 478 4.3.3.1 Rule R1 480 Rule: R1 (see Figure 2) 482 Context: An HELLO message is received by a node A{1}. 484 Check: Is the address {1}, the address of the originator node ? 486 Action: If it is the case, this node is in conflict and must select a 487 new address. 489 Rationale: A node doesn't receive its own HELLO messages (they are 490 not forwarded), hence the occurence of such an event means that a 491 node with the same address has sent an HELLO. 493 +--------------+ +--------------+ 494 | ** Node A{1} | <---> | ** Node B{1} | 495 +--------------+ +--------------+ 497 Figure 2 499 As mentioned, this rule can be completed by other duplicate address 500 detection mechanisms, not specified in this document, as they are 501 beyond its scope. 503 The detection R1 can be performed using HELLO messages (in any 504 autoconfiguration state, including HELLO_STATE). 506 4.3.4 Two-hop duplicate address detection 508 In this case, the two conflicting nodes are two-hop neighbors, that 509 is: they are not neighbor, but they have a common neighbor (see 510 Figure 3). The rule proposed here relies on the fact that a common 511 neighbor exists, and will receive the HELLO from both nodes. The 512 detection proceeds in three steps: the common neighbor detects the 513 conflict using those HELLOs, then it advertises the conflict in some 514 message(s) (rule R2), and finally, the conflicting nodes change their 515 address upon receiving this conflict advertisement (rule R3). 517 4.3.4.1 Rule R2 519 Rule: R2 (see Figure 3) 521 Context: In node B{2}: an HELLO message from address {1} was received 522 previously, and another HELLO from address {1} is just received by 523 B{2}. 525 Check: Are the sequence numbers of the HELLOs inconsistent (as 526 defined in Section 4.4)? 528 Action: If it is the case, there are two or more neighbors using the 529 same address {1}. B{2} will advertise that the address {1} is 530 conflicting in its HELLO messages. 532 Rationale: If two neighbors of one node have conflicting addresses, 533 the HELLO sequence numbers will be inconsistent. 535 +--------------+ +--------------+ +--------------+ 536 | Node A{1} | <---> | ** Node B{2} | <---> | Node C{1} | 537 +--------------+ +--------------+ +--------------+ 539 Figure 3 541 4.3.4.2 Rule R3 543 Rule: R3 (see Figure 4) 545 Context: In node A{1} (and node C{1}): a neighbor B{2} is advertising 546 that conflict exists with the address {1}. 548 Check: - 549 Action: If it is the case, A{1} is a conflicting node and must select 550 a new address. 552 +--------------+ +--------------+ +--------------+ 553 | ** Node A{1} | <---> | Node B{2} | <---> | ** Node C{1} | 554 +--------------+ +--------------+ +--------------+ 556 Figure 4 558 The detections R2 and R3 can be performed using HELLO messages (in 559 any autoconfiguration state, including HELLO_STATE). 561 4.3.5 Multihop duplicate address detection 563 In this section, DAD rules are proposed to handle the case where the 564 distance between conflicting nodes is three hops or more. In this 565 case, in general, it cannot be assumed that a single node has enough 566 information to detect the conflict using exclusively the HELLO 567 messages. Hence, the logical choice is here to use information 568 inside TC messages. However the duplicate address detection is 569 complicated by the optimizations of the OLSR routing protocol: first, 570 not all nodes originate TC messages ; second, TC messages might 571 include only a subset of neighbors ; third, OLSR messages may be 572 split and as a consequence, an individual TC message from one node 573 might not include all the topology information that the node should 574 periodically refresh. Finally, the MPR selection algorithm can be 575 affected by duplicate addresses, and prevent proper operation of the 576 MPR flooding mechanism, hence prevent proper propagation of the TCs 577 used by DAD. 579 The DAD rules that are specified in the case of multihop DAD are 580 classified depending on the status of the conflicting nodes with 581 respect to TC generation: a node which generates TC messages (when it 582 is a multipoint relay of some node) is called a TC generator. Three 583 cases are possible and are handled: 585 o Both conflicting nodes are TC generators. 587 o One of the conflicting nodes is a TC generator, and the other is 588 not. 590 o None of the conflicting nodes is TC generator. 592 In each of the three cases, the DAD rules allow detection both on the 593 conflicting nodes (which would then change address) and on 594 intermediary nodes (which would then avoid routing table 595 contamination). Finally some DAD rules are used for preventing the 596 following case: 598 o Conflicting nodes are impeding MPR selection. 600 The following four sections handle individually each case. 602 4.3.5.1 Multihop DAD with two TC generators 604 In this case, the two nodes in conflict are both TC generators. Then 605 each of them would ultimately receive one TC with its own originator 606 address, but which it did not generate (for it was generated by the 607 other node). The intermediate nodes would also detect conflict by 608 noticing discrepancy in the sequence numbers or discrepancy in the 609 content of the TC messages with same sequence number. 611 The first rule applies to conflicting nodes (R4 (Section 4.3.5.1.1)), 612 the second applies to other nodes in the network (R5 613 (Section 4.3.5.1.2)). 615 4.3.5.1.1 Rule R4 617 Rule: R4 (see Figure 5) 619 Context: In node A{1} (or node C{1}): a TC with originator address 620 {1} has been received. A{1} keeps track of the TC messages that 621 it has sent. 623 Check: Verify whether A has actually sent that TC: the message 624 sequence number should be the same as one message that A has sent 625 in the past, and then the content should be the same. 627 Action: If it is not the case, A{1} is a conflicting node and must 628 select a new address. 630 +--------------+ +--------------+ +--------------+ 631 | ** Node A{1} | <- .. -> | Node B{2} | <- .. -> | ** Node C{1} | 632 | TC generator | | | | TC generator | 633 +--------------+ +--------------+ +--------------+ 635 Figure 5 637 4.3.5.1.2 Rule R5 638 Rule: R5 (see Figure 6) 640 Context: In node B{2}: an TC message with originator address {1} was 641 received previously by the node, and another TC with originator 642 address {1} is just received by B{2} 644 Check: Are the sequence numbers of the TC messages consistent (as 645 defined in Section 4.4)? Is the content of the TC identical to 646 the one(s) received before? 648 Action: If it not is the case, there are two or more nodes using the 649 same address {1}: then the TC should be forwarded (if it is has 650 not already been), but the content of the TC will be ignored and 651 not processed 653 Rationale: This detects a conflict between TC generators. If the 654 conflicting nodes are sending TC messages with same sequence 655 number, standard MPR flooding might not allow the TC messages to 656 reach the other node. Hence in case of conflict, the TC should be 657 forwarded by default. Also, because a conflict has been detected, 658 the received TC is guaranted to hold information which is 659 inconsistent with the information already processed because it was 660 issued by a different node ; and hence, the content of TC message 661 should be ignored. 663 +--------------+ +--------------+ +--------------+ 664 | Node A{1} | <- .. -> | ** Node B{2} | <- .. -> | Node C{1} | 665 | TC generator | | | | TC generator | 666 +--------------+ +--------------+ +--------------+ 668 Figure 6 670 4.3.5.2 Multihop DAD with two non-generators 672 In this section, DAD rules are given for the case where none of the 673 conflicting nodes is a TC generator. In such a configuration, the 674 conflict is detected by means of by using the TC messages of the 675 multi-point relays of the nodes. As one conflicting node selects 676 some MPR, these MPR will send TC messages indicating this selection: 677 when one of the TC messages reaches the other conflicting node, this 678 node will detect inconsistency by discovering that it did not, 679 actually, select the TC originator as MPR. 681 The DAD for intermediate nodes is, however more complex, because they 682 cannot rely on sequence numbers as in previous section 683 Section 4.3.5.1, nor they can rely on knowledge of the actual MPR 684 selection of every node like the nodes in conflict. Hence to detect 685 occurences of such conflicts, another mechanism is used: it is based 686 on the concept of familiar nodes. A node (an IP address) is familiar 687 for another node, when the last one has had knowledge of existence of 688 the first one for sufficiently long (see Section 4.6). 690 The hypothesis made now is that most conflicts occur because of 691 network merges. In such an address conflict, now, let's assume a 692 node from one network is now sending TC messages including the 693 address of one node (in conflict with this network) from another, 694 newly merged, network. For instance, let us consider Figure 7, and 695 let us assume that A{1}, C{2}, and E{4} were previously part of one 696 network, while B{1} and D{3} (one of its MPRs) were part of another. 697 It is reasonable to assume that D{3} will become the neighbor of few 698 nodes of the first network, which it will advertise. Hence, most 699 likely, the TC messages of D{3}, which advertise the conflicting node 700 B{1}, also include mostly addresses of nodes from the merged network, 701 which would be unfamiliar nodes for A{1}. Thence the DAD rule: 702 ignore the information relative to familiar nodes, when it is inside 703 TC messages from unfamiliar nodes, which also include too many 704 unfamiliar nodes. 706 Another rule is added for neighbors of the node A{1}, such as C{2}: 707 because they have knowledge of the neighborhood of A{1}, they are 708 able to directly check if D{3} is a neighbor of A{1}. 710 4.3.5.2.1 Rule R6 712 Rule: R6 (see Figure 7) 714 Context: In node A{1}: a TC message with originator address {3} has 715 been received. 717 Check: If this TC includes the address {1} of A, A checks whether it 718 had recently selected {3} as MPR. 720 Action: If it is not the case, A{1} is a conflicting node and must 721 select a new address. 723 Rationale: If A{1} has not selected {3} as MPR, then another node 724 with address {1} must have done so, hence there is an address 725 conflict. 727 +--------------+ +--------------+ 728 | ** Node A{1} | | ** Node B{1} | 729 | (non-MPR) | | (non-MPR) | 730 +--------------+ +--------------+ 731 ^ ^ 732 | | 733 V V 734 +--------------+ +--------------+ +--------------+ 735 | Node C{2} | <- .. -> | Node E{4} | <- .. -> | Node D{3} | 736 | TC generator | | | | TC generator | 737 +--------------+ +--------------+ +--------------+ 739 Figure 7 741 4.3.5.2.2 Rule R7 743 Rule: R7 (see Figure 8) 745 Context: In node E{4}: a TC message from originator {2}, which is 746 familiar for E, had been received. It included the familiar (for 747 E) address {1}. Another TC, from originator {3}, an unfamiliar 748 node for E, is including the same familiar address {1}. 750 Check: In this TC, check how many addresses are from familiar nodes. 751 If too little addresses are familiar, then the TC is assumed to 752 include an address {1} which is conflicting. 754 Action: If conflict is assumed, then the information of the TC of {3} 755 about address {1} is ignored (the previous one from {3} will still 756 be used), but all other content is kept. 758 Rationale: This is an heuristic for detecting conflict. Note that in 759 any case, a route to {1} can still be computed using the TC 760 message from {2}. Note also that after some time, {3} and all the 761 nodes advertised by {3} will be familiar to E, ensuring that this 762 rule will no longer apply. 764 +--------------+ +--------------+ 765 | Node A{1} | | Node B{1} | 766 | (non-MPR) | | (non-MPR) | 767 +--------------+ +--------------+ 768 ^ ^ 769 | | 770 V V 771 +--------------+ +--------------+ +--------------+ 772 | Node C{2} | <- .. -> | ** Node E{4} | <- .. -> | Node D{3} | 773 | TC generator | | | | TC generator | 774 +--------------+ +--------------+ +--------------+ 776 Figure 8 778 4.3.5.2.3 Rule R8 780 Rule: R8 (see Figure 9) 782 Context: In node C{2}: a HELLO message from node {1} was previously 783 received, and a TC message from node {3} is now received. 785 Check: If the TC message from {3} includes {1} as MPR selector, the 786 HELLO from {1} should also have included {3} as symmetrical 787 neighbor (actually more: as MPR) 789 Action: If this not the case, then a conflict is assumed for address 790 {1}. Then the information of the TC message of {3} about address 791 {1} is ignored (the previous one from {3} will still be used), but 792 all other content is kept. 794 Rationale: This is another heuristic for detecting conflict, for 795 every node which is neighbor of the conflicting nodes. 797 +--------------+ +--------------+ 798 | Node A{1} | | Node B{1} | 799 | (non-MPR) | | (non-MPR) | 800 +--------------+ +--------------+ 801 ^ ^ 802 | | 803 V V 804 +--------------+ +--------------+ +--------------+ 805 | ** Node C{2} | <- .. -> | Node E{4} | <- .. -> | Node D{3} | 806 | A's neighbor | | | | TC generator | 807 +--------------+ +--------------+ +--------------+ 809 Figure 9 811 4.3.5.3 Multihop DAD with one TC Generator and one Non-Generator 813 In case one of the nodes in conflict is a TC generator while the 814 other one is not, the conflict can be detected by as previously. The 815 TC generator can conduct duplicate address detection by checking the 816 TC messages of the MPR of the other node using DAD rule R6 817 (Section 4.3.5.2.1). The conflicting node that does not generate TC 818 messages, can detect conflict with DAD rule R4 (Section 4.3.5.1.1). 820 However for intermediary nodes, a new case is possible. We still 821 assume most conflicts occur because of network merges. Then it is 822 possible that for one network, one conflicting node is a TC generator 823 in the other network, while the other one is not. Using the same 824 logic as previously, the TC message of that conflicting node would 825 include many unfamiliar nodes, hence one DAD rule is to reject such 826 TC. 828 4.3.5.3.1 Rule R9 830 Rule: R9 (see Figure 10) 832 Context: In node E{4}: a TC from originator familiar node {2} 833 (familiar for E) had been received and it included the (familiar 834 for E) address {1}. Another TC message, from originator {1}, is 835 received. 837 Check: In this TC, check how many addresses are from familiar nodes. 838 If too little addresses are familiar, then the TC is assumed to be 839 from an unfamiliar node from a merged network. 841 Action: If conflict is assumed, then the information of the TC is 842 ignored (the previous one from {2} will still be used). 844 Rationale: This is an heuristic for detecting conflict. Note that in 845 any case, a route to {1} can still be computed using {2} and note 846 that in absence of conflict, anyway, after some time, all the 847 nodes advertised by {1} will be familiar to E, ensuring that this 848 rule will no longer apply. 850 +--------------+ 851 | Node A{1} | 852 | (non-MPR) | 853 +--------------+ 854 ^ 855 | 856 V 857 +--------------+ +--------------+ +--------------+ 858 | Node C{2} | <- .. -> | ** Node E{4} | <- .. -> | Node B{1} | 859 | TC generator | | | | TC generator | 860 +--------------+ +--------------+ +--------------+ 862 Figure 10 864 Additionally, still in the case of network merge, the nodes that are 865 on the border of the network merge can actually use some heuristics 866 for detecting conflicts. Indeed, if a node, is from another 867 (merging) network, it is likely to have many unfamiliar nodes as 868 neighbors. And those unfamiliar nodes will be present in the Hello 869 messages of the node. Hence when a node detects that one of its 870 neighbors has too many other neighbors that are unfamiliar, it can 871 suspect the neighbor is from another network. In case the node is a 872 TC generator, it will then mark the address of the node as 873 unfamiliar. 875 4.3.5.3.2 Rule R10 877 Rule: R10 (see Figure 11) 879 Context: In node C{3}: a TC message is being generated, and it 880 includes neighbor {1}. 882 Check: \myitem{Check:} In the neighborhood of X{1} (which is obtained 883 from the Hello messages, in the two-hop tuple set) check how many 884 addresses are from familiar nodes. If too little addresses are 885 familiar, then the neighbor is assumed to be an node from a merged 886 network. 888 Action: If too little address are familiar, the address {1} is 889 advertised as being "with too many unfamiliar neighbors". 891 Rationale: This is an heuristic to avoid routing table contamination. 892 Note that the address {1} is still advertised and can be used by 893 node A{1} to detect the conflict. 895 +--------------+ 896 | Node X{1} | 897 | | 898 +--------------+ 899 ^ 900 | 901 V 902 +--------------+ +--------------+ +--------------+ 903 | Node A{1} | <- .. -> | Node B{2} | <- .. -> | ** Node C{3} | 904 | | | | | TC generator | 905 +--------------+ +--------------+ +--------------+ 907 Figure 11 909 The following rule uses the information transmitted by the previous 910 one: 912 4.3.5.3.3 Rule R11 914 Rule: R11 (see Figure 12) 916 Context: In node B{2}: a TC message has been received from originator 917 {3} and it includes neighbor {1} marked as ``with too many 918 unfamiliar neighbors'', by rule R10 in node {3}. 920 Check: - 922 Action: The address {1} should be ignored in the processing of the TC 923 message. But the other addresses may still be used, and the TC 924 should still be forwarded.%with std MPR flooding. 926 Rationale: This is an heuristic to avoid routing table contamination, 927 using information from rule R10. 929 +--------------+ 930 | Node X{1} | 931 | | 932 +--------------+ 933 ^ 934 | 935 V 936 +--------------+ +--------------+ +--------------+ 937 | Node A{1} | <- .. -> | ** Node B{2} | <- .. -> | Node C{3} | 938 | | | | | TC generator | 939 +--------------+ +--------------+ +--------------+ 941 Figure 12 943 4.3.5.4 Three-hop DAD, Specific Case 945 It has been noted that in some cases the MPR selection process can 946 fail because of duplicate addresses (see [8]). As a result, the MPR 947 flooding mechanism may fail to deliver a message to the entire 948 network, and then the previous DAD rules may fail to detect the 949 duplicate address detection. This situation is illustrated on 950 Figure 13. A specific rule can be devised to prevent this situation 951 and allow proper MPR selection: on the figure, the node B{2} is able 952 to detect that there is an inconsistency in the neighborhood 953 advertised by {1} and {3}, which may possibly arise from {1} being a 954 duplicate address. In this case, the MPR selection of B would be 955 deficient: so B can still preventively select {3} as MPR by itself. 956 That way, the messages from A{1} going through B will reach D{1} 957 (triggering one of the previous DAD rules). 959 4.3.5.4.1 Rule R12 961 Rule: R12 (see Figure 13) 963 Context: In node B{2}: a HELLO from node {1} had been received, and 964 now an HELLO from node {3} is received. 966 Check: If the HELLO from {3} includes {1} as symmetrical neighbor, 967 the HELLO from {1} should also have included {3} as symmetrical 968 neighbor. 970 Action: If it is not the case, there is an inconsistency and the node 971 B should select {3} as MPR. 973 Rationale: Such inconsistencies should never happen in a static 974 network, unless there is a conflict. Note also that due to 975 topology changes, they may do so even if there is no conflict. In 976 that case, note that the only penalty is an temporary increase of 977 the number of MPR selected. It is still an excellent heuristic 978 that will solve the MPR selection problem when the network is 979 static. 981 +--------------+ +--------------+ 982 | Node A{1} | | Node D{1} | 983 +--------------+ +--------------+ 984 ^ ^ 985 | | 986 V V 987 +--------------+ +--------------+ 988 | ** Node B{2} | <---> | Node C{3} | 989 +--------------+ +--------------+ 991 Figure 13 993 4.4 Sequence Number Consistency 995 In [8], the use of sequence numbers to verify consistency has been 996 used in some general cases. Here, sequence number consistency is 997 checked for the OLSR protocol, and consist really of two cases: HELLO 998 sequence number consistency, and TC sequence number consistency. 1000 4.4.1 Minimum Wrap-Around Limit 1002 In the OLSR protocol [3], it is implicitly assumed that the sequence 1003 number of one node will wrap-around within an interval of time 1004 greater than DUP_HOLD_TIME. Hence this value is a good reference for 1005 the minimum expected interval before a wrap-round the sequence number 1006 of any node in the network, denoted MIN_WRAP_AROUND_INTERVAL. 1008 4.4.2 HELLO Sequence Number Consistency 1010 In case of HELLO messages, it is assumed that they would be received 1011 in the same order as they are transmitted (because they are not 1012 forwarded). In this case, a node observing the HELLO messages from a 1013 neighbor will see that their sequence numbers are permanently 1014 increasing. Now if there are two neighbors B and C of one node A, 1015 the node A will receive alternatively messages from B and C, because 1016 each is transmitting indefinitly. Hence A must receive a sequence of 1017 packets from B, then some packets from C, then some packets from B, 1018 and so on. Let's assume that ultimately a sufficiently long sequence 1019 is received without packet loss, and which then will be in this 1020 order: 1022 o one packet B1 from B (possibly the last one of a sequence of 1023 packets from B) 1025 o some packets from C 1026 o one packet B2 from B (possibly the first one of a sequence of 1027 packets from B) 1029 Now because there was no packet loss, the sequence number of the 1030 packet B2 is the sequence number of the packet B1 plus 1. As a 1031 result, considering the sequence number of any packet from C: 1033 o If it is greater than the sequence number of B1, then: the 1034 sequence number of the packet B2 will be less or equal to the 1035 sequence number of the packets from C. 1037 o Otherwise it is equal to or less than the sequence number of B1. 1039 In both events, A observes a decrease or a repetition of the sequence 1040 numbers of B. 1042 Hence, for HELLO messages, it is sufficient to check if the HELLO 1043 received from one address is equal to, or less than, the sequence 1044 number of the previous HELLO received from this address. 1046 However, because a node may not be constantly a neighbor (and hence, 1047 quite naturally, a large number of successive HELLO messages may not 1048 be received), this condition should be checked only when there was no 1049 wrap-around, hence when the interval between the previous HELLO 1050 received and the last HELLO received from the same address is less 1051 than MIN_WRAP_AROUND_INTERVAL. 1053 4.4.3 TC Sequence Number Consistency 1055 Because TC messages are forwarded with the MPR flooding mechanism, 1056 first, the same message may be received several time, secondly, the 1057 packet order can be changed, especially with the use of jitter. 1058 Hence the algorithm used previously for checking consistency of HELLO 1059 messages (Section 4.4.2) can not be used as is. 1061 Hence the following principles are used: 1063 o The sequence number and the receving time of the last TC message 1064 for each originator is recorded. 1066 o Each time a TC message is received from a given originator, with a 1067 given sequence number, the node checks whether if a TC message 1068 with similar identification already was received. If it was, it 1069 checks that the previous content is identical to the current 1070 content. 1072 o If the sequence number difference (in absolute value) between the 1073 new TC and previous TC from the same originator is above a given 1074 threshold MAX_TC_DIFF_SEQ_NUM, then duplicate address can be 1075 suspected. Such an event is possible, for instance if another 1076 node sends many non-TC messages or cease to be TC generator for 1077 some time ; thus an additional check is performed on the message 1078 rate: an approximation of the message rate is computed as the 1079 "sequence number difference divided by the reception time 1080 difference". If this message rate is greater than a threshold 1081 MAX_MESSAGE_RATE, then the TC Sequence Number are deemed 1082 inconsistent. 1084 If precise adjustement is desired for the values of 1085 MAX_TC_DIFF_SEQ_NUM, and MAX_MESSAGE_RATE (peak rate), it can be 1086 observed that one of the worst case occurs when two nodes are in 1087 conflict, and one is using the same sequence numbers of the other 1088 with a delay a little greater than DUP_HOLD_TIME. 1090 4.5 Autoconfiguration State 1092 4.5.1 Introduction 1094 Each node has an "autoconfiguration state". This state is an 1095 indicator of how long the node has been in the network. The central 1096 idea, is that each time a node selects a new address, it should enter 1097 the network gradually, running a restrained version of the OLSR 1098 protocol. By this way, that the node can detect which addresses are 1099 being used, checking for duplicates of its own address, while 1100 avoiding to disrupt the routing tables of the other nodes, in the 1101 event that its address is actually found to be in conflict. 1103 4.5.2 Functionning 1105 There are exactly 3 autoconfiguration states, in each of which the 1106 behavior of the node is: 1108 HELLO_STATE: When a node newly assigns its own address, it enters the 1109 HELLO_STATE, where it generates HELLO messages, but not topology 1110 control (TC) messages. It does not participate in MPR selection 1111 nor MPR flooding, and does not participate in data packet 1112 forwarding either. It doesn't fill the topology set nor the 1113 routing table. When it detects that it has an address conflict 1114 with other nodes based on received hello messages (rules R1 to R3, 1115 and rule R12), it re-selects a new address based on the busy 1116 address list. When a pre-determined time has elapsed, in this 1117 state, without detecting address conflict, the node enters the 1118 topology state. 1120 TOPOLOGY_STATE: In this state, a node generates HELLO messages, but 1121 not TC messages. It processes TC messages, and performs MPR 1122 selection, but cannot be MPR itself and hence, does not forward TC 1123 messages. It fills the network topology set but not the routing 1124 table, and does not participate in data packet forwarding. When 1125 it detects that it has an address conflict with another node 1126 (based rules R1 to R12 applied to received messages), it re- 1127 selects a new address (using the recommendations of Section 4.2) 1128 and returns to the HELLO_STATE. When a pre-determined time 1129 elapses in the TOPOLOGY_STATE without detecting address conflict, 1130 the node enters the NORMAL_STATE. 1132 NORMAL_STATE: In this state, the node is running the "normal" OLSR 1133 protocol, completed with the algorithms specified in this document 1134 , and without message processing/generation restrictions 1135 associated to the state. More precisely, the node generates both 1136 HELLO messages and TC messages as usual. It processes TC messages 1137 generated by other nodes and forwards them as usual based on MPR 1138 flooding. It fills the topology set, calculates routing tables 1139 and participates in data forwarding. Only nodes in the 1140 NORMAL_STATE are selected as the intermediary nodes (forwarders) 1141 in the routing table calculation. When the node detects that it 1142 has an address conflict with other nodes (according to one of the 1143 rules R1 to R12), it re-selects a new address and enters the 1144 HELLO_STATE. 1146 The behavior in each state is summarized in the following table: 1148 +----------------+----------------+----------------+----------------+ 1149 | State | HELLO_ STATE | TOPOLOGY_ | NORMAL_ STATE | 1150 | | | STATE | | 1151 +----------------+----------------+----------------+----------------+ 1152 | Selectable as | no | no | yes | 1153 | MPR | | | | 1154 | | | | | 1155 | MPR selection | no | yes | yes | 1156 | | | | | 1157 | TC message | no | no | yes | 1158 | forwarding | | | | 1159 | | | | | 1160 | TC message | no | yes | yes | 1161 | processing | | | | 1162 | (MPR flooding) | | | | 1163 | | | | | 1164 | TC message | no | no | yes | 1165 | generation | | | | 1166 | | | | | 1167 | Routing table | no | no | yes | 1168 | (and | | | | 1169 | forwarding) | | | | 1170 | | | | | 1171 | DAD rules | R1, R2, R3, | R1 to R12 | R1 to R12 | 1172 | | and R12 | | | 1173 | | | | | 1174 | State duration | HELLO_ STATE_ | TOPOLOGY_ | forever | 1175 | (if no address | DURATION | STATE_ | | 1176 | change) | | DURATION | | 1177 +----------------+----------------+----------------+----------------+ 1179 4.6 Node Familiarity 1181 The concept of "node familiarity" is introduced for use of some 1182 heuristics in DAD rules. The definition is the following: a node (or 1183 more precisely, an IP address) is "familiar" for another node, when 1184 the last one has had knowledge of existence of the first one for 1185 sufficiently long. An node which is not familiar is "unfamiliar". 1187 In NOA-OLSR, a node (more precisely, an address) considered familiar 1188 when the time elapsed since the first time that its address has 1189 appeared in any OLSR message, is greater than a fixed time interval 1190 NODE_FAMILIAR_TIME (see Section 6). 1192 5. Autoconfiguration Specifications 1194 5.1 Overview 1196 This section provide a low-level view of the changes and additions to 1197 the standard OLSR, necessary to implement NOA-OLSR performing 1198 duplicate address detection. The high-level description of the 1199 method, including algorithms, is in Section 4. 1201 5.2 Information Repository 1203 Though the exchange of OLSR control messages, each node accumulates 1204 information about the network. This information is stored according 1205 to the descriptions in section 4 of the OLSR specification [3], 1206 modified accordingly to the changes proposed to this section. 1208 5.2.1 Autoconfiguration State 1210 Each node has one "autoconfiguration state" (see Section 4.5), which 1211 is one of HELLO_STATE, TOPOLOGY_STATE and NORMAL_STATE. 1213 5.2.2 State Information Base 1215 The State Information Base is the State Set: a set of type which hold 1216 some information relevant to autoconfiguration for each address. 1218 For each address in the network, a 'State Tuple' (S_main_addr, 1219 S_time, S_state, S_last_hello_time, S_last_hello_seq_num, 1220 S_last_tc_time, S_last_tc_seq_num, S_conflict_time, 1221 S_MPR_remember_time, S_MPR_forced_time, S_creation_time) is recorded. 1223 A state tuple primarily records information about the 1224 autoconfiguration state of the node, but also with a set of data 1225 about these addresses, which are used to perform autoconfiguration. 1227 S_main_addr: the address of the node 1229 S_state: the autoconfiguration state of the address (see 1230 Section 4.5) 1232 S_time: the time after which the tuple should be deleted 1234 S_last_hello_time, S_last_hello_seq_num: the last time an HELLO 1235 has been received from this address, and the sequence number of 1236 this last HELLO 1238 S_last_tc_time, S_last_tc_seq_num: the last time an TC has been 1239 received from this address (as originator), and the sequence 1240 number of this last TC 1242 S_conflict_time: the time until which the address is considered to 1243 be in conflict 1245 S_MPR_remember_time: the time after which the node forgets that 1246 this address was selected as MPR by this node. 1248 S_MPR_forced_time: the time during which this address must be 1249 choosen as MPR 1251 S_creation_time: the time at which the state tuple was created 1253 5.2.3 Duplicate Set 1255 In the standard OLSR protocol, each node recorded a "Duplicate Tuple" 1256 which includes the following fields (D_addr, D_seq_num, 1257 D_retransmitted, D_iface_list, D_time) (see section 3.4 of the OLSR 1258 specification [3] where they are documented). 1260 In NOA-OLSR, the following field is added: D_content_id. 1261 D_content_id is used to identify the content of the message which was 1262 received, and is should be a sequence of bytes. Use and requirement 1263 of D_content_id are highlighted in the next section. 1265 5.2.3.1 Message Content Identifier 1267 A message content identifier is used by NOA-OLSR to check whether the 1268 content of a message is identical to one received previously. In 1269 standard OLSR functionning, the message sequence numbers are used for 1270 this purpose ; however in NOA-OLSR, because of the possibility of 1271 duplicate addresses, two messages with same originator address and 1272 same sequence number can be different if they are originated from 1273 conflicting nodes. The message content identifier is used in this 1274 context, to verify whether the message are actually identical. 1276 Each implementation must have a method to generate message content 1277 identifiers from a received message, and such a method is naturally 1278 denoted "Message Content Identifier Generation Method". It is 1279 typically some kind of hash method, and it should met the following 1280 requirements: 1282 It must take in input the message content, and output one "message 1283 content identifier" (whose exact implementation is left to 1284 implementors). The message content is defined as the sequence of 1285 bytes of an OLSR message, excluding the message header (section 1286 3.3.2 of the OLSR specification [3]). 1288 It must consistently generate the same message content identifier, 1289 when it is applied on the same message content. 1291 It should generate different message content identifiers, for 1292 different message contents, with a high probability (typically 1293 larger than the probability of address collision of one node). 1295 Two examples of methods which satisfy the requirements are the 1296 following: 1298 Copy method: the message content identifier is the sequence of 1299 bytes which constitute the message content itself. 1301 Hash method: the message content identifier is a sequence of bytes 1302 obtained after applying a hash function on the sequence of bytes 1303 of the message content. For instance the MD5 Message-Digest 1304 Algorithm [2], suitable at least for networks with less that one 1305 billion of OLSR nodes. 1307 Because the message content identifiers are not transmitted to other 1308 nodes, different nodes can implement different generation methods 1309 without compromising interoperability. 1311 5.2.4 Set and Unset Fields 1313 Several of the newly introduced fields in the miscellanous tuple are 1314 not necessarily initialized at the tuple set creation. Such fields 1315 are: 1317 In state tuples, the fields: S_last_hello_time, 1318 S_last_hello_seq_num, S_last_tc_time, S_last_tc_seq_num, 1319 S_conflict_time, S_MPR_remember_time, S_MPR_forced_time 1321 In duplicate tuples, the field D_content_id 1323 After tuple creation, the node must be able to identify the fact that 1324 the field has been already set or not. How to do so is indeed an 1325 implementation issue, but in the remaining it is assumed that a node 1326 can verify whether a field "is set" which means that a value has been 1327 affected to the field yet. In the opposite case, the field "is not 1328 set". 1330 5.3 Address Selection and Address Change 1332 5.3.1 Address Selection 1334 A node can choose an address using any algorithm, as highlighted in 1335 Section 4.2, subject to one constraint. The only constraint is that 1336 the address MUST NOT select any busy address, that is an address 1337 which has recently been used in the network. 1339 Precisely, a busy address is an address such that: 1341 o There exists a State Tuple in the State Set with: 1343 * S_main_addr == the given address ; and 1345 * S_time is not expired 1347 Hence it is required that either the address selection algorithm 1348 yields addresses which are different from any such addresses, or 1349 alternatively, that the algorithm run until the last address it 1350 generates is no longer busy. In case the algorithm is unable to 1351 generate a new address, the node may stop. 1353 5.3.2 Address Change 1355 Upon detection of a conflict a node MUST change its address, by 1356 selecting a new one as described in Section 5.3.1. 1358 When a node sets a new address (for initialisation, or because it has 1359 just changed its address because of a conflict), the node SHOULD 1360 perform the following steps: 1362 The node sets its autoconfiguration state to HELLO_STATE. 1364 Any potential OLSR message waiting for transmission or forwarding 1365 at the routing protocol level, should be either send with the new 1366 proper address (originator), or should be discarded. 1368 Each link tuple of the Link Set must be modified so that 1369 L_local_iface_addr (which should be the previous address of the 1370 node), is set to new address. 1372 The MPR Selector Set is emptied. 1374 The routing table is emptied. 1376 Additionally, the autoconfiguration state evolves as follows: 1378 Also each time a conflict is detected, the node selects a new 1379 address and restarts from HELLO_STATE. 1381 If the node has been in state HELLO_STATE without address conflict 1382 for a duration greater than HELLO_STATE_DURATION, then: 1384 The node sets its autoconfiguration state to TOPOLOGY_STATE 1386 The node recomputes its MPR set 1388 If the node has been in state TOPOLOGY_STATE without address 1389 conflict for a duration greater than TOPOLOGY_STATE_DURATION, 1390 then: 1392 The node sets its autoconfiguration state to NORMAL_STATE 1394 The node recomputes its MPR set 1396 The node recalculates its routing table 1398 5.4 State Set Update 1400 The State Set records information that the node gathered about all 1401 the addresses which are known in the network. It is updated by a 1402 variety of means at different steps of the OLSR processing. 1404 5.4.1 Populating the State Set 1406 One of the main informations that State Set records is whether an 1407 address has already been seen in the network, and what was the 1408 autoconfiguration state associated with that address. 1410 Because all external addresses of the network come from OLSR messages 1411 received, such messages are the source of information used to 1412 populate the State Set. Because state tuples may be used quite early 1413 in the processing, the node MUST satisfy the following requirements: 1415 o For any address which is to be used, the node must preliminary 1416 update its state tuple with the proper associated 1417 autoconfiguration state if it is know, or with the STATE_UNDEFINED 1418 autoconfiguration state. 1420 More precisely, in the basic functionning of the OLSR protocol, TC 1421 and HELLO messages are exchanged and upon receiving such a message, 1422 and: 1424 o The node should update the state tuple of Sender Interface Address 1425 with STATE_UNDEFINED (as per Section 5.4.2). 1427 o The node should update the state tuple of the Originator Address 1428 with STATE_UNDEFINED (as per Section 5.4.2). 1430 o Depending on the message type, it should perform the following 1431 updates if it is one of the following: 1433 * HELLO_MESSAGE, HELLO_MESSAGE_WITH_STATE: update the state set 1434 according to Section 5.6.2.1 1436 * TC_MESSAGE, TC_MESSAGE_WITH_STATE: update the state set 1437 according to Section 5.6.5.1 1439 5.4.2 State Tuple Update 1441 This section describes the steps taken for the action refered in 1442 other sections as: updating the state tuple for a given address 1443 "Address" with a given state "Autoconfiguration State". The steps 1444 are the following: 1446 o If there exists no state tuple where: 1448 S_main_addr == given Address 1450 then one is created and inserted in the tuple set with the 1451 following values: 1453 * S_main_addr = given Address 1455 * S_creation_time = current time 1457 * S_state = STATE_UNDEFINED 1459 * S_MPR_remember_time is not set 1461 * S_MPR_forced_time is not set 1463 * S_conflict_time is not set 1465 * S_last_hello_time is not set 1467 * S_last_tc_time is not set 1469 o The state tuple (newly created or not) where 1471 S_main_addr == given Address 1473 is then modified as follows: 1475 S_time = current time + NODE_STATE_HOLD_TIME 1477 After that, if the following condition is true: 1479 the given Autoconfiguration State is different from 1480 STATE_UNDEFINED, AND 1482 S_state is different from the given Autoconfiguration State 1484 Then a potential topology change is recorded and the state tuple 1485 is modified as follows: 1487 * S_state = given Autoconfiguration state 1489 A potential topology change implies that both the MPR set and the 1490 routing table SHOULD be recomputed. 1492 5.4.3 Associated State Tuple Retrieval 1494 In many cases, the steps related to autoconfiguration use the state 1495 tuple associated to one address, that is: the state tuple such as 1496 S_main_addr is equal to that address (it is necessarily unique). If 1497 such a state tuple exists, then this is the one which is used when 1498 the "associated state tuple is retrieved". 1500 However, although such a state tuple should exist, it may be the case 1501 that such a state tuple has been deleted, because S_time has expired. 1502 This is because the state set is kept relatively independent from 1503 other processings and from other sets by design. When this case 1504 occurs when the "associated state tuple is retrieved", a new state 1505 tuple is created using the method in Section 5.4.2 (using 1506 STATE_UNDEFINED). 1508 5.4.4 State Tuple: HELLO information update 1510 Each time the handling of a received HELLO message has been finished, 1511 the state tuple of its originator, that is the state tuple where: 1513 S_main_addr == Originator Address 1515 will exist (as an application of the rules Section 5.4.1). The node 1516 should then update or ensure that it had been updated as follows: 1518 S_last_hello_time = current time 1520 S_last_hello_seq_num = HELLO message sequence number 1522 5.4.5 State Tuple: TC information update 1524 Each time the handling of a received TC message has been finished, 1525 the state tuple of its originator, that is the state tuple where: 1527 S_main_addr == Originator Address 1529 will exist (as an application of the rules Section 5.4.1). The node 1530 should then update or ensure that it had been updated as follows: 1532 S_last_tc_time = current time 1534 S_last_tc_seq_num = TC message sequence number 1536 5.4.6 State Tuple: MPR information update 1538 Before recomputing its MPR set, as documented in section 8.3 of the 1539 OLSR specification [3], a node MUST use the current list of MPR to 1540 save the information that those nodes had been choosen as MPR in the 1541 recent past. This is used for DAD rule Section 4.3.5.2.1. 1543 For each address in its MPR set, the associated state tuple is 1544 retrieved (as per Section 5.4.3), and is modified as follows: 1546 o S_MPR_remember_time = current time + MAX_MPR_REMEMBER_TIME 1548 5.4.7 Familiarity 1550 The concept of familiar addresses, which is described in Section 4.6, 1551 is used by NOA-OLSR. In the actual specification, the fact that a 1552 given address is familiar or unfamiliar is determined from the state 1553 set, as follows: 1555 1. If there exists a state tuple in the state set, such as: 1557 S_main_addr = given address, AND 1559 current time > S_creation_time + NODE_FAMILIAR_TIME 1561 then: the address is familiar 1563 2. Otherwise, the address is unfamiliar. 1565 5.5 Changes in Message Processing 1567 5.5.1 Overview 1569 This section gives a description of the changes in the processing of 1570 standard OLSR messages, namely HELLO messages and TC messages. 1572 5.5.2 Packet Processing and Message Flooding 1574 The packet processing algorithm, documented in section 3.4 of the 1575 OLSR specification [3], has been changed. For convenience, such 1576 changes have been denoted "message pre-processing" and "message post- 1577 processing". Hence, an autoconfiguration pre-processing step and an 1578 autoconfiguration post-processing step have been added to the message 1579 processing of the standard OLSR. 1581 Upon receiving a OLSR packet, a node MUST perform a number of tasks 1582 for each encapsulated message, listed in section 3.4 of the OLSR 1583 specification [3]. The steps which have been added or changed are 1584 the following: 1586 1 ... 1588 1 bis {CHANGED:}Depending on whether or not the node has decided to 1589 interoperate with standard OLSR nodes (see Section 8.2), the node 1590 MUST check whether it must reject the message based on 1591 requirements of Section 5.6.7. It the message must be rejected, 1592 the processing of the message stops here. 1594 2 If the time to live of the message is less than or equal to '0' 1595 (zero), the message MUST silently be dropped. {CHANGED:} Even if 1596 the message was sent by the receiving node (i.e., the Originator 1597 Address of the message is the main address of the receiving node), 1598 the node MUST perform the autoconfiguration pre-processing given 1599 indicated in Section 5.5.3. This pre-processing will finish with 1600 one of four statuses: 1602 Address conflict detected The node MUST then stop the processing 1603 of the packet and change its address according to the rules of 1604 Section 5.3.2. 1606 Interrupt message processing The node MUST then skip the 1607 processing of the current message, and proceed to the 1608 processing of the next message (if any) of the packet. 1610 Retransmit message and interrupt message processing The node MUST 1611 first perform a special retransmission of the message according 1612 to the rules listed in Section 5.5.2.1, then skip the 1613 processing of the current message, and proceed to the 1614 processing of the next message (if any) of the packet. 1616 Continue message processing The node MUST continue the processing 1617 of the message. 1619 3 ... 4 (same as in section 3.4 of the OLSR specification [3]) 1621 5 {CHANGED:} the message SHOULD be post-processed according the the 1622 specifications of Section 5.5.4. 1624 5.5.2.1 Special Retransmission 1626 A special retransmission method is used when it is assumed, that, in 1627 presence of address conflict, the MPR flooding mechanism alone would 1628 not necessarily guarantee the proper distribution of one message to 1629 the entire network. This retransmission can be performed as a result 1630 of the message pre-processing steps, it includes creation of a new 1631 duplicate tuple, followed by a retransmission of the message section 1632 3.4.1 of the OLSR specification [3]: 1634 1. A new duplicate tuple is inserted in the duplicate set with the 1635 special duplicate tuple creation documented in Section 5.5.2.2. 1637 2. The TTL of the message is reduced by one. 1639 3. The hop-count of the message is increased by one. 1641 4. The message is broadcast on all interfaces (Notice: the remaining 1642 fields of the message header SHOULD be left unmodified.) 1644 5.5.2.2 Special Duplicate Tuple Creation 1646 This document uses the duplicate set in additional ways differing 1647 from the standard OLSR [3]. Indeed, the duplicate set is also used 1648 for both messages generated by the node and for messages 1649 retransmitted using the Special Retransmission (Section 5.5.2.1) 1650 method. Such use relies on the creation of a duplicate tuple in a 1651 special way by one method, herehence called "Special Duplicate Tuple 1652 Creation". The duplicate tuple is created for a given message, and 1653 refering to the fields of the message, it is created as follows: 1655 D_addr = Originator Address 1657 D_seq_num = Message Sequence Number 1659 D_retransmitted = true 1661 D_time = current time + DUP_HOLD_TIME 1663 D_iface_list contains all the interfaces of the node 1665 D_content_id = computed message content identifier 1666 (Section 5.2.3.1) 1668 5.5.3 Autoconfiguration Message Pre-Processing 1670 This section specifies the message pre-processing which MUST be 1671 implemented. Note that the message pre-processing uses the message 1672 headers but doesn't interpret (parse) the message content ; instead 1673 it considers the message content as a sequence of bytes. 1675 The following steps MUST be followed: 1677 1. If the message is a HELLO_MESSAGE or HELLO_WITH_STATE_MESSAGE, 1678 the node pre-processes the messages according to Section 5.5.3.1. 1680 2. Otherwise, if the message is a TC_MESSAGE or 1681 TC_WITH_STATE_MESSAGE, the node pre-processes the messages 1682 according to Section 5.5.3.2. 1684 3. Otherwise: 1686 1. If the message was sent by the receiving node (i.e., the 1687 Originator Address of the message is the main address of the 1688 receiving node) the message pre-processing finish with status 1689 'Interrupt Message Processing' 1691 2. Otherwise, this pre-processing finishes with status 'Continue 1692 Message Processing'. 1694 5.5.3.1 Hello Message Pre-Processing 1696 The pre-processing of such messages MUST be performed as follows, 1697 checking for the R1 (Section 4.3.3.1). 1699 1. If the Originator Address of the message is the main address of 1700 the receiving node: 1702 1. there is a conflict and the pre-processing finishes with 1703 status 'Address conflict detected' (in accordance to DAD rule 1704 R1 (Section 4.3.3.1)) 1706 2. Otherwise, the pre-processing finishes with status 'Continue 1707 message processing' 1709 5.5.3.2 TC Message Pre-Processing 1711 The pre-processing of such message MUST be performed checking for the 1712 DAD rules R4 (Section 4.3.5.1.1) and R5 (Section 4.3.5.2.2) as 1713 follows: 1715 5.5.3.2.1 Rule R4 check 1717 o If the following condition is true: 1719 Originator Address == main address of the node 1721 o AND if there exists no tuple in the tuple set where: 1723 D_addr == Originator Address, AND 1725 D_seq_num == Message Sequence Number 1727 D_content_id == computed message content identifier 1729 o then, in accordance to rule R4 (Section 4.3.5.1.1), a conflict as 1730 been detected and the pre-processing is finished with status 1731 'Address conflict detected'. 1733 5.5.3.2.2 Rule R5 check 1735 The DAD rule R5 requires checking two conditions, namely, consistency 1736 of sequence numbers of TC messages, and consistency of message 1737 content of TC messages. 1739 The check for consistent sequence numbers is the following: 1741 o If the following condition is true: 1743 * Originator Address is different from main address of the node 1745 AND such TC has never been seen, that is: there exists no tuple in 1746 the duplicate set where: 1748 D_addr == Originator Address, AND 1750 D_seq_num == Message Sequence Number 1752 AND a TC sequence number inconsistency is detected using the rules 1753 of Section 4.4.3, that is, precisely: there exists one tuple in 1754 the state set where: 1756 S_main_addr == Originator Address, AND 1758 S_last_tc_time is set , AND 1760 | Message Sequence Number - S_last_tc_seq_um | > 1761 MAX_TC_DIFF_SEQ_NUM, (where |a| is the absolute value of 'a'), 1762 AND 1764 | Message Sequence Number - S_last_tc_seq_um | > (current time 1765 - S_last_tc_time) * MAX_MESSAGE_RATE 1767 then, in accordance to rule R5 (Section 4.3.5.1.2) a conflict has 1768 been detected between two other nodes, and the pre-processing is 1769 finished with status 'Retransmit message and interrupt message 1770 processing'. 1772 The check for consistent TC message content is the following: 1774 o If the following condition is true: 1776 * Originator Address is different from main address of the node 1778 AND such TC has been seen, that is: there exists at least one 1779 tuple in the duplicate set where: 1781 D_addr == Originator Address, AND 1783 D_seq_num == Message Sequence Number 1785 AND there exists no tuple in the duplicate set where: 1787 D_addr == Originator Address, AND 1789 D_seq_num == Message Sequence Number, AND 1791 D_content_id == computed message content identifier (see 1792 Section 5.2.3.1) 1794 then, in accordance to rule R5 (Section 4.3.5.1.2) a conflict has 1795 been detected between two other nodes, and the pre-processing is 1796 finished with status 'Retransmit message and interrupt message 1797 processing'. 1799 5.5.4 Autoconfiguration Message Post-Processing 1801 The node MUST do the following post-processing, to ensure that any 1802 forwared TC has an associated duplicate tuple with proper 1803 D_content_id: 1805 1. If the message is a TC_MESSAGE or a TC_WITH_STATE_MESSAGE: 1807 * If there exists a duplicate tuple such that: 1809 D_addr == Originator Address, AND 1811 D_seq_num == Message Sequence Number, AND 1813 D_content_id is not set 1815 * Then: 1817 The field D_content_id of this duplicate tuple is set to 1818 the value of the computed message content identifier 1819 (Section 5.2.3.1). 1821 2. Otherwise the post-processing stops. 1823 5.6 Changes in OLSR Message Processing 1825 This section documents the changes to be applied in the general 1826 processing of the OLSR protocol: OLSR message processing for HELLO 1827 and TC messages. 1829 5.6.1 Changes in HELLO Message Format 1831 A new kind of HELLO message is used: it includes now both the 1832 autoconfiguration state of the node which generates the HELLO and the 1833 autoconfiguration state of neighbor interface addresses. The Message 1834 Type of the message is HELLO_WITH_STATE_MESSAGE (see also 1835 Section 5.6.7). 1837 Although another general format might be used, it is choosen to keep 1838 the format of a message HELLO_WITH_STATE is similar to a normal 1839 HELLO, except for the following: the reserved field is split in two 1840 and includes the state of the nodes (for the originator of the HELLO, 1841 and the neighbor nodes), as shown on Figure 14. 1843 0 1 2 3 1844 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 1845 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1846 | Node State | Neigh. State | Htime | Willingness | 1847 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1848 | Link Code | Reserved | Link Message Size | 1849 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1850 | Neighbor Interface Address | 1851 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1852 ... 1854 Figure 14 1856 "Node State" is the autoconfiguration state of the node. "Neighbor 1857 State" ("Neigh. State") is the autoconfiguration state of the 1858 neighbors being advertised. 1860 As a result, only neighbors which all have the same autoconfiguration 1861 state can be sent in the same HELLO_WITH_STATE: this is not 1862 restrictive in practice, because several different HELLO_WITH_STATE 1863 can be generated at the same time (each with different neighbor 1864 state). 1866 The choice if which of HELLO or HELLO_WITH_STATE to use, is specified 1867 in Section 5.6.7. 1869 5.6.2 Changes in HELLO Message Processing 1871 The HELLO Message Processing modifies on the processing described in 1872 section 7.1.1 of the OLSR specification [3], in section 8.2.1 of the 1873 OLSR specification [3], and in section 8.4.1 of the OLSR 1874 specification [3]. 1876 The changes in the HELLO Message Processing are related to the DAD 1877 rules R2 (Section 4.3.4.1), R3 (Section 4.3.4.2), and R12 1878 (Section 4.3.5.4.1). 1880 The "Originator Address" of a HELLO message is the main address of 1881 the node, which has emitted the message. Likewise, the "Neighbor 1882 State" MUST be computed from the Neighbor State field of the HELLO 1883 message (see Section 5.6.1). 1885 The application of the DAD rule R2 (Section 4.3.4.1) is done by 1886 performing the following processing with the message originator 1887 address: 1889 1. The state tuple relative to the Originator Address of the message 1890 is updated (see Section 5.4.2) with autoconfiguration state equal 1891 to the Neighbor State. 1893 2. If that associated state tuple verifies: 1895 * S_last_hello_seq_num is set, AND 1897 * current time - S_last_hello_time < MIN_WRAP_AROUND_INTERVAL, 1898 AND 1900 * S_last_hello_seq_num is equal or greater to the Message 1901 Sequence Number of the received HELLO 1903 then the Originator is conflicting with another node, according 1904 to rule R2 (Section 4.3.4.1), and as a consequence, the state 1905 tuple MUST be updated as follow: 1907 * S_conflict_time = current time + CONFLICT_HOLD_TIME 1909 The application of the DAD rule R3 (Section 4.3.4.2) is done by 1910 checking whether the address of the node is advertised by the means 1911 of Section 5.6.3 in the HELLO of another node, as follows: 1913 1. If inside the same HELLO message from another node, the address 1914 of the node appears more than one time, then: 1916 The node is in conflict and node MUST then stop the processing 1917 of the packet and change its address according to the rules of 1918 Section 5.3.2 1920 The DAD rule @R12@ adds the following processing upon receiving a 1921 HELLO message: 1923 o for each address (henceforth: 2-hop neighbor address), listed in 1924 the HELLO message with Neighbor Type equal to SYM_NEIGH or 1925 MPR_NEIGH: 1927 1. if the main address of the 2-hop neighbor address == main 1928 address of the receiving node: 1930 silently ignore the 2-hop address 1932 2. otherwise if there exists a associated neighbor tuple where: 1934 N_neighbor_main_addr == 2-hop neighbor address, AND 1936 additionally there exists no two hop neighbor tuple where: 1938 N_neighbor_main_addr == 2-hop neighbor address, AND 1940 N_2hop_addr == Originator address 1942 then, a potential conflict is assumed and: 1944 + state tuple associated to the 2-hop neighbor address is 1945 retrieved (see Section 5.4.3), and it is updated as 1946 follows: 1948 + S_MPR_forced_time = current time + CONFLICT_HOLD_TIME 1950 Additionally, the node would now process its own HELLO messages, 1951 because one check has been removed in Section 5.5.2. This should be 1952 avoided, hence now prior to performing the HELLO processing of 1953 section 7.1.1 of the OLSR specification [3], the node should check 1954 that: 1956 The Originator Address of HELLO message is not one of the main 1957 address of node 1959 and if it is not the case, the standard HELLO processing should be 1960 skipped. 1962 5.6.2.1 State Set Update from HELLO 1964 The "Originator Address" of a HELLO message is the main address of 1965 the node, which has emitted the message, and is in the message header 1966 of the message (section 3.3.2 of the OLSR specification [3]). The 1967 "Node State" and the "Neighbor State" are fields inside the HELLO 1968 message and have been added for NOA-OLSR (see Section 5.6.1). Upon 1969 receiving a HELLO, and before any processing of the content (i.e. 1970 before using any of the addresses), the node SHOULD update the state 1971 set as follows: 1973 1. The state tuple associated to Originator Address must be updated 1974 with the autoconfiguration state "Node State" (as per 1975 Section 5.4.2) 1977 2. For each of the neighbor interface address received in the HELLO 1978 message: 1980 1. The state tuple associated to neighbor interface address must 1981 be updated with the autoconfiguration state "Neighbor State" 1983 5.6.3 Changes in HELLO Message Generation 1985 The HELLO Message Generation is the one described in section 6.2 of 1986 the OLSR specification [3], with modifications described in this 1987 section. There are two modifications. The first one is the 1988 application of the the DAD rule Section 4.3.4.2 and is related to 1989 rule Section 4.3.4.1: the address of neighbors which have been 1990 detected to be in conflict are advertised in the HELLO messages. 1991 There are implicitly advertised by a specific means: they are 1992 included twice in the HELLO message. The second modification relates 1993 to the specification of the autoconfiguration states in the messages. 1995 The amendments of section 6.2 of the OLSR specification [3] are 1996 hence: 1998 o The Node State field is set such that it corresponds to the node's 1999 current autoconfiguration state. 2001 o The Neighbor State field is set such that it corresponds to the 2002 autoconfiguration state of all addresses listed in the HELLO 2003 messages. Namely, for any Neighbor Interface Address which is 2004 advertised, it MUST be advertised in an HELLO message such that: 2006 * the associated state tuple (Section 5.4.3) has a S_state 2007 identical to the Neighbor State the message 2009 As a consequence, one node will send at least many different HELLO 2010 as there are different autoconfiguration states of neighbors. 2012 o The following rule is added: any neighbor conflicting address, as 2013 identified by the fact that there is one state tuple where: 2015 S_main_addr == address, AND 2017 S_conflict_time > current time 2019 and for which there exists one associated neighbor tuple where: 2021 N_neighbor_main_addr == S_main_addr 2023 this conflicting address MUST be cited at least once within the 2024 predetemined refreshing period REFRESH_INTERVAL in the following 2025 way: it must figure listed twice (or more) in the same link 2026 message, with proper Neighbor Code, and with either proper Link 2027 Code or LINK_UNSPEC. 2029 5.6.4 Changes in TC Message Format 2031 A new kind of TC message is used: it includes now both the 2032 autoconfiguration state of the node which generates the TC and the 2033 autoconfiguration state of advertised addresses. The Message Type of 2034 the message is TC_WITH_STATE_MESSAGE. A similar change to HELLO 2035 messages (see Section 5.6.1) is performed: use of the reserved field 2036 for storing an extra Node State and Neighbor State (each of them 2037 within one byte) 2039 0 1 2 3 2040 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 2041 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2042 | ANSN | Node State | Neigh. State | 2043 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2044 | Advertised Neighbor Main Address | 2045 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2046 ... 2048 Figure 15 2050 "Node State" is the autoconfiguration state of the node. "Neighbor 2051 State" ("Neigh. State") is the autoconfiguration state of the 2052 neighbors being advertised. 2054 Note that only nodes in STATE_NORMAL are sending TCs, and only nodes 2055 in STATE_TOPOLOGY or STATE_NORMAL are selecting MPR (as per 2056 Section 4.5.2), hence the possible values in the "Node State" and 2057 "Neighbor State" fields are limited. Still, upon receiving a TC 2058 message, the TC processing should not assume this property is 2059 necessarily verified, for possible interoperability reasons. 2061 Additionaly, requirements about which of TC or TC_WITH_STATE to use, 2062 are specified in Section 5.6.7. 2064 5.6.5 Changes in TC Message Processing 2066 The TC Message Processing specified in the section 9.5 of the OLSR 2067 specification [3] is now verifying the DAD rules R6 2068 (Section 4.3.5.2.1), R7 (Section 4.3.5.2.2), R8 (Section 4.3.5.2.3) 2069 and R9 (Section 4.3.5.3.1), and additionally, is adapted in several 2070 ways. The following adaptions SHOULD be added: 2072 o The TC processing of section 9.5 of the OLSR specification [3] and 2073 the additional TC processing in this section, is only performed 2074 when the node is in TOPOLOGY_STATE or NORMAL_STATE. 2076 o The state set should be updated from the TC messages. 2078 o Some TC messages uncover an address conflict involving the 2079 receiving node (rule R6 (Section 4.3.5.2.1)). 2081 o Some TC messages are to be ignored because they are estimated to 2082 include invalid information (rules R9 (Section 4.3.5.3.1)). 2084 o Some information in the TC messages (some addresses) should be 2085 ignored because it is estimated to be invalid (rules R5 2086 (Section 4.3.5.1.2) and @R12@). 2088 Each of these are described in the following sections. 2090 5.6.5.1 State Set Update from TC 2092 The "Originator Address" of a TC message is the main address of the 2093 node, which has emitted the message, and is in the message header of 2094 the message (section 3.3.2 of the OLSR specification [3]). The "Node 2095 State" and the "Neighbor State" are fields inside the TC message and 2096 have been added for NOA-OLSR (see Section 5.6.4). Upon receiving a 2097 TC, and before any processing of the content (i.e. before using any 2098 of the addresses), the node SHOULD update the state set as follows: 2100 1. The state tuple associated to Originator Address must be updated 2101 with the autoconfiguration state "Node State" (as per 2102 Section 5.4.2) 2104 2. For each of the advertised neighbor main address received in the 2105 TC message: 2107 1. The state tuple associated to advertised neighbor address 2108 must be updated with the autoconfiguration state "Neighbor 2109 State" 2111 5.6.5.2 Conflict detection based on TC message content 2113 The rule R6 (Section 4.3.5.2.1) asserts that the node is in conflict, 2114 if it receives a TC which advertises its address in an situation 2115 where it shouldn't. The pratical steps for completing this check are 2116 the following: 2118 o If in the received TC message: 2120 * the advertised address includes the main address of the node, 2121 AND 2123 * the originator address is not in the MPR set of the node, AND 2125 * the associated state tuple of the originator address is such 2126 that at least one of the two following conditions is verified: 2128 + S_MPR_remember_time is not set, or else, 2130 + S_MPR_remember_time < current time 2132 o Then the node is in conflict: it will then stop the processing of 2133 the message and it MUST change its address according to the rules 2134 of Section 5.3.2. 2136 5.6.5.3 Dismissed TC messages 2138 The rule R9 (Section 4.3.5.3.1) require certain TC messages to be 2139 dismissed because they are inconsistent with the collected 2140 information, and would contaminate routing tables. The familiarity 2141 (see Section 4.6) is at the core of the verification of rule R9. 2143 Before further processing a TC , the node MUST first checks whether 2144 the originator address of the TC is familiar (as described 2145 Section 5.4.7). If and only if, it is the case, the following steps 2146 determine whether the TC processing should be interrupted according 2147 to rule R9: 2149 1. The number of familiar addresses Nf and the number of unfamiliar 2150 addresses Nu is computed for TC 2152 2. If the ratio of familiar addresses is too low, that is precisely 2153 if: 2155 Nf < (Nf + Nu) * MIN_TC_FAMILIARITY_RATE 2157 Then: 2159 * the TC message should be ignored 2161 5.6.5.4 Dismissed addresses in TC messages 2163 Upon receiving a TC and prior to TC processing of each address 2164 according to section 9.5 of the OLSR specification [3], the DAD rules 2165 R7 (Section 4.3.5.2.2) and R8 (Section 4.3.5.2.3) require some 2166 addresses to be ignored to prevent routing table contamination. 2168 In application of the rule R7 (Section 4.3.5.2.2), the node SHOULD 2169 ignore any advertised address in a TC message which verifies the 2170 following conditions simultaneously: 2172 o The advertised address is not one interface address of the node, 2173 AND 2175 o The Originator Address of the TC is familiar (as per 2176 Section 5.4.7), AND 2178 o The advertised address is familiar (as per Section 5.4.7), AND 2180 o There exists no topology tuple where: 2182 * Either T_last_addr == advertised address 2184 * or T_dest_addr == advertised address 2186 Additionaly, in application of the rule R8 (Section 4.3.5.2.3), the 2187 node SHOULD ignore any advertised address in a TC message which 2188 verifies the following conditions simultaneously: 2190 o There exists a neighbor tuple where: 2192 * N_neighbor_main_addr == advertised address, AND 2194 * N_status == SYM 2196 and then, 2198 o There exists no two hop tuple where: 2200 * N_neighbor_main_addr == advertised address, AND 2202 * N_2hop_addr == Originator Address 2204 5.6.6 Changes in TC Message Generation 2206 In order to build the topology information base, each node, which has 2207 been selected as MPR, broadcasts Topology Control (TC) messages in 2208 the OLSR protocol. The following changes should be made in the TC 2209 message generation of section 9.3 of the OLSR specification [3]. 2211 The conditions for actually generating TC messages, now additionally 2212 take into account the autoconfiguration state (see Section 4.5.2): 2214 o A node SHOULD only generate messages when it is in STATE_NORMAL 2215 The format of TC messages is different, and hence the TC message 2216 generation should fill properly the extra information: 2218 o The Node State field is set such that it corresponds to the 2219 current autoconfiguration state of the node. 2221 o The Neighbor State field is set such that it corresponds to the 2222 autoconfiguration state of all addresses advertised in the TC 2223 message. Namely, for any address which is advertised, it MUST be 2224 advertised in an TC message such that: 2226 * the associated state tuple (Section 5.4.3) has a S_state 2227 identical to the Neighbor State of the message 2229 As a consequence, one node will send at least as many different 2230 TCs as there are different autoconfiguration states of advertised 2231 addresses. 2233 Finally, the node MUST keep track of the TCs it has sent, and this is 2234 done by adding information in the duplicate set. To do so, after the 2235 generation of each TC message, the node records it by creating a 2236 duplicate tuple. However due to an address conflict, the node may 2237 already have such a tuple for a received TC from a conflicting node, 2238 hence the two steps update: first check whether there is such TC, and 2239 second, if not, create the duplicate tuple. This is done as follows, 2240 before the TC message is actually sent: 2242 1. the message content identifier is computed (as per 2243 Section 5.2.3.1) 2245 2. If there exists a duplicate tuple where: 2247 * D_addr == main address of node 2249 * D_seq_num == TC message sequence number (in message header) 2251 Then the node is in conflict (as an application of rule R4 2252 (Section 4.3.5.1.1)), and 2254 * it will then stop the processing of the message and it MUST 2255 change its address according to the rules of Section 5.3.2 2257 3. Otherwise the node creates a duplicate tuple, accordingly to 2258 Special Duplicate Tuple Creation (Section 5.5.2.2). 2260 5.6.7 Message Type for HELLO and TC Messages 2262 New message types are introduced by NOA-OLSR, for use with the new 2263 HELLO message format in Section 5.6.1, and the new TC message format 2264 inSection 5.6.4. Because these messages simply use "reserved" 2265 (blank) fields in standard OLSR messages, it would be possible to use 2266 the standard message types HELLO_MESSAGE and TC_MESSAGE. However for 2267 interoperability reasons, a node SHOULD NOT do so. Instead it should 2268 decide first whether it wants to interoperate with standard OLSR 2269 implementations, or not interoperate. See Section 8.2 for a 2270 comprehensive discussion of interoperability with standard OLSR. 2272 Depending on whether it chooses to interoperate with the standard 2273 OLSR implementations the node, should originate messages as follows: 2275 Interoperating with standard OLSR: The node MUST generate messages 2276 with HELLO_MESSAGE type and TC_MESSAGE type when the fields "node 2277 state" and the "neighbor state" of the message are both in state 2278 NORMAL. It MUST ignore all the messages with "node state" == 2279 NORMAL_STATE and message type HELLO_WITH_STATE_MESSAGE or 2280 TC_WITH_STATE_MESSAGE. 2282 Never interoperating with standard OLSR: The node MUST generate all 2283 HELLO and TC messages with a message type of 2284 HELLO_WITH_STATE_MESSAGE or TC_WITH_STATE_MESSAGE. It MUST ignore 2285 all the messages with message type HELLO_MESSAGE and TC_MESSAGE. 2287 5.7 Changes in MPR Computation 2289 The MPR computation is changed as follows. First, before any new MPR 2290 computation, it must be kept track of the previous MPR set, as 2291 indicated in Section 5.4.6. 2293 During MPR computation, the node should avoid any node in a state 2294 different from STATE_NORMAL (as Section 4.5.2 specifies). After the 2295 MPR computation has been achieved, yielding a new MPR set, this set 2296 is completed with the MPR enforced by autoconfiguration rules (namely 2297 rule R12 (Section 4.3.5.4.1)), as follows: 2299 The node MUST add to its MPR set, the address S_main_addr of any 2300 state tuple where: 2302 S_main_addr is not already in the newly computed MPR list 2304 S_MPR_forced_time > current time 2305 There exists a neighbor tuple in the neighbor set where: 2307 N_neighbor_main_addr == S_main_addr 2309 N_status == SYM 2311 5.8 Changes in Routing Table Calculation 2313 Standard routing table calculation is described in section 10 of the 2314 OLSR specification [3]. However with the introduction of the 2315 autoconfiguration state, it should now be exclusively be performed 2316 when the node is in NORMAL_STATE (see Section 4.5.2). 2318 The computed routes should also only have forwarders which are in the 2319 NORMAL_STATE, and hence the routing table computation algorithm 2320 should be modified. The property of using only forwarders in the 2321 NORMAL_STATE can be expressed as ensuring that only route entries 2322 where: 2324 R_next_addr is associated to a state tuple (as retrieved by 2325 Section 5.4.3) where S_state == NORMAL_STATE 2327 OR ELSE: R_next_addr == R_dest_addr (i.e. this is a direct 2328 neighbor) 2330 This property can be ensured by: 2332 o in step 3 of the algorithm of section 10 of the OLSR specification 2333 [3], using only 2-hop tuples where N_neighbor_main_addr is 2334 associated to a state tuple (Section 5.4.3) with S_state == 2335 NORMAL_STATE 2337 o in "the second step 3", sub-step 3.1: using only topology tuples 2338 where T_last_addr is associated to a state tuple (Section 5.4.3) 2339 with S_state == NORMAL_STATE 2341 6. Proposed Values for Constants 2343 The proposed values of the specification are documented here. Many 2344 of them are depend on the constants section 18 of the OLSR 2345 specification [3]. 2347 HELLO_STATE_DURATION (= HELLO_INTERVAL) 2349 TOPOLOGY_STATE_DURATION (= TC_INTERVAL) 2351 MAX_MPR_REMEMBER_TIME (= 2 x NEIGHB_HOLD_TIME) 2353 CONFLICT_HOLD_TIME (= NEIGHB_HOLD_TIME) 2355 NODE_FAMILIAR_TIME 2357 MIN_WRAP_AROUND_INTERVAL (= DUP_HOLD_TIME) 2359 MIN_TC_FAMILIARITY_RATE (= 50%) 2361 MAX_TC_DIFF_SEQ_NUM, MAX_MESSAGE_RATE 2363 NODE_STATE_HOLD_TIME (= 10 x DUP_HOLD_TIME) 2365 Codes for Autoconfiguration State (in messages) 2367 o NORMAL_STATE = 0 2369 o TOPOLOGY_STATE = 1 2371 o HELLO_STATE = 2 2373 o UNDEFINED_STATE = 3 2375 In this section, several proposed values are dependent on OLSR 2376 protocol values. However, it is allowed in standard OLSR, to change 2377 some parameters (which will result in changes of "validity time" of 2378 some messages, for instance): then there is an ambiguity about which 2379 parameters should be chosen: the parameters of the receiving node, or 2380 the parameters of the sender node. The values that are proposed here 2381 can be used by default, and can be replaced by more appropriate 2382 values where necessary. 2384 7. IANA Considerations 2386 Two new types of control messages are defined in NOA-OLSR. Because 2387 this document is a draft, some values in the range reserved for 2388 private/local use (see section 22 of the OLSR specification [3]) are 2389 proposed: 2391 HELLO_WITH_STATE_MESSAGE = 130 2393 TC_WITH_STATE_MESSAGE = 131 2395 Values in the range 5-127 might be allocated in the OLSR registry 2396 using standards action, for these new messages. 2398 8. Limitations and interoperability considerations 2400 There are several limitations associated with NOA-OLSR proposed in 2401 this specification. The most important of them is related to the 2402 fact that the node is assumed to work exclusively in an environment 2403 where all nodes have a single interface, but there exists some other 2404 minor limitations which are explained in Section 8.1. The other kind 2405 of limitation is a direct consequence of the previous one: although 2406 an implementation of NOA-OLSR will interoperate with most standard 2407 OLSR implementations, some features of standard OLSR interact 2408 negatively, and unconditional interoperability is not warranted. The 2409 conditions of interoperability are documented in Section 8.1. 2411 8.1 Limitations 2413 The limitations of NOA-OLSR protocol are highlighted in this 2414 document. Some of the limitations will be addressed in future 2415 versions of this document, some are intrinsic to the method, and may 2416 be lifted by added requirements on the OLSR protocol. In this 2417 section, the analysis of these limitations is provided. 2419 In this version of this draft, the first one, the duplicate detection 2420 rules have been specified only the most common case, where the node 2421 has a single interface participating in the MANET. This rules can 2422 naturally be extended to integrate multiple interfaces, but doing so 2423 is not immediatly straightforward, and hence will be the subject of 2424 further specification. Meanwhile, an implementation of this 2425 specification of NOA-OLSR cannot be expected to perform reliably with 2426 several interfaces, and more precisely: 2428 o Some duplicate address conflicts will not be detected. 2430 o The assumptions of some rules are no longer verified. For 2431 instance, rule R1 assumes that a node will not receive the HELLO 2432 messages that it generates. 2434 o The changes in OLSR processing will result, in some cases, in a 2435 general state of the node (including the data of the miscellaneous 2436 information repositories) which is inconsistent and otherwise 2437 impossible in both the standard OLSR and NOA-OLSR. This will 2438 result in unpredictable behavior. 2440 Another present restriction derives from the assumption that TC 2441 messages will include only MPR selectors in rule R6. The rule could 2442 be approprietly relaxed, but for any implementation which doesn't, in 2443 some cases, the node will not interoperate with nodes which are 2444 advertising more than their MPR selector set. Precisely, these are 2445 nodes which include they auxiliary functionning of "Redundant 2446 Topology Information" in section 15 of the OLSR specification [3] 2447 (with TC_REDUNDANCY different from 0, see section 15.1 of the OLSR 2448 specification [3]). 2450 Concerning the intrisic restrictions due to the DAD rules, the most 2451 noticeable is the use of message sequence numbers to detect message 2452 inconsistency (as Section 4.4). This assumes, logically, that the 2453 message sequence numbers will be linearily incremented, however this 2454 is property of the standard OLSR is not stated as a "REQUIREMENT". 2455 Practices such as computing a sequence number from the content of the 2456 message, for instance, would defeat autoconfiguration mechanisms. 2458 Finally, the necessary changes auxiliary functions of OLSR (such as 2459 for options "Non-OLSR Interfaces", section 12 of the OLSR 2460 specification [3]), are not addressed in this documente, and the 2461 impact of NOA-OLSR on auxiliary functionning is not addressed for the 2462 time being. 2464 8.2 Interoperability with Standard OLSR 2466 A node implementing NOA-OLSR protocol relies on some assumptions 2467 given in the previous Section 8.1, hence might not be able to 2468 interoperate successfully with a MANET comprising given standard OLSR 2469 implementations. 2471 Two modes of operation are defined in Section 5.6.7: 2473 o a node that never interoperates with nodes running standard OLSR. 2475 o a node that always interoperates with nodes running the standard 2476 OLSR protocol. 2478 The discussion and logic behind interoperability is found in 2479 Section 8.2.1, and the discussion and logic behind isolation is in 2480 Section 8.2.2. 2482 8.2.1 Considerations for Interoperability with Standard OLSR 2484 A sufficient condition for interoperability between two link state 2485 routing protocols running on the same network, is that they both use 2486 the same topology information and the same algorithm for route 2487 calculation, and also if topology information exchange is not 2488 disrupted. This sufficient condition is verified for the standard 2489 OLSR and NOA-OLSR, when it is implemented as documented here and in 2490 Section 5.6.7. Namely: 2492 o When a node is in the NORMAL_STATE, it will advertise all 2493 information about addresses in NORMAL_STATE inside HELLO and TC 2494 messages which are compliant with standard OLSR. 2496 o When a node is not in the NORMAL_STATE, or alternatively when it 2497 advertises information about addresses which are not in 2498 NORMAL_STATE, it uses messages that the standard OLSR will not 2499 process. 2501 The sufficient conditions are satisfied because: 2503 o As the standard OLSR does, NOA-OLSR uses only nodes in the 2504 NORMAL_STATE for computing routes as forwarders. 2506 o MPR flooding is not disrupted, because: nodes with NOA-OLSR which 2507 are not in NORMAL_STATE are invisible to the standard OLSR. As a 2508 result: 2510 * MPR flooding from Sstandard OLSR nodes: standard OLSR nodes 2511 will never attempt to select as MPR some nodes which are not in 2512 NORMAL_STATE, hence no problem arises. 2514 * MPR flooding from nodes with NOA-OLSR: nodes implementing NOA- 2515 OLSR, that are not in NORMAL_STATE, are not selected as MPR. 2517 Because of some of the current restrictions of NOA-OLSR, it might be 2518 the case that in some networks, one given implementation of modified 2519 OLSR won't interoperate with one given standard OLSR implementation. 2520 This issue is addressed in the next Section 8.2.2. 2522 8.2.2 Considerations for Isolation from Standard OLSR Nodes 2524 It may be desired to isolate an implementation of NOA-OLSR from the 2525 standard OLSR networks. This is a perticuliar instance of the 2526 related problem of separating of a OLSR, MANET or general network in 2527 different administrative entities. 2529 In the OLSR protocol, all links between OLSR interfaces are 2530 discovered by means of neighbor sensing. Then, isolating one node to 2531 another node can be achieved by either of them ignoring the messages 2532 of the other. This results into an asymmetrical link, which will 2533 neither be used for MPR selection, nor MPR flooding nor route 2534 calculation, and in practice, in isolation of the nodes from each 2535 other. 2537 However doing so, requires generally an external mechanism to 2538 exchange information sufficient for one node to determine whether it 2539 want to be isolated from another. In the case of NOA-OLSR, this 2540 information is implicitly provided as follows: 2542 o A node which doesn't wish to interoperate with standard OLSR, 2543 should transmit all its HELLO and TC messages with message type 2544 HELLO_WITH_STATE and TC_WITH_STATE 2546 o A node which wishes to interoperate with standard OLSR, should 2547 transmit all its HELLO and TC messages, when in STATE_NORMAL, , 2548 with message type HELLO_MESSAGE and TC_MESSAGE 2550 These rules must be respected, as enforced by Section 5.6.7. Note 2551 that as a consequence, a node which receives HELLO message from a 2552 node in STATE_NORMAL (or from a standard OLSR node), can deduce which 2553 kind of policy it enforce. 2555 9. Requirements notation 2557 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 2558 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 2559 document are to be interpreted as described in [1]. 2561 10. Security Considerations 2563 As the standard OLSR does not specify any special security measure, 2564 it makes a target for various attacks (see section 20 of the OLSR 2565 specification [3]) ; NOA-OLSR is subject to the same attacks, but 2566 also to other attacks: such as forging messages in order to 2567 deliberatly trigger some DAD rules, hence forcing an address change, 2568 or increasing OLSR control traffic. However the conditions in which 2569 such attacks can be sucessfully conducted are some conditions in 2570 which more severe attacks can be conducted with the standard OLSR 2571 protocol. Hence, in practice, vulnerability of NOA-OLSR protocol 2572 against deliberate attacks, is identical to the vulnerability of the 2573 standard OLSR protocol. 2575 11. Acknowledgements 2577 This work was funded by Strategic Information and Communications R&D 2578 Promotion Programme (SCOPE), Ministry of Internal Affairs and 2579 Communications, Japan. 2581 The authors would also like to thank Sota Yoshida, Masoto Goto, 2582 Takashi Hasegawa for their valuable contributions to NOA-OLSR, along 2583 wth Yasuhiro Owada, and many other students of Information and 2584 Communication Network Laboratory for other various aspects for 2585 developping and testing of this protocol. 2587 (document generation date: Thu May 26 15:00:15 2005) 2589 12. References 2591 12.1 Normative References 2593 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 2594 Levels", BCP 14, RFC 2119, March 1997. 2596 12.2 Informative References 2598 [2] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, 2599 April 1992. 2601 [3] Clausen, T. and P. Jacquet, "Optimized Link State Routing 2602 Protocol (OLSR)", RFC 3626, October 2003. 2604 [4] Ogier, R., Templin, F., and M. Lewis, "Topology Dissemination 2605 Based on Reverse-Path Forwarding (TBRPF)", RFC 3684, 2606 February 2004. 2608 [5] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand 2609 Distance Vector (AODV) Routing", RFC 3561, July 2003. 2611 [6] Johnson, D., "The Dynamic Source Routing Protocol for Mobile Ad 2612 Hoc Networks (DSR)", draft-ietf-manet-dsr-10 (work in progress), 2613 July 2004. 2615 [7] Ruffino, S., Stupar, P., and T. Clausen, "Autoconfiguration in a 2616 MANET: connectivity scenarios and technical issues", 2617 draft-ruffino-manet-autoconf-scenarios-00 (work in progress), 2618 October 2004. 2620 [8] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad 2621 hoc Networks", March 2003. 2623 [9] Mase, K., "No Overhead IP Address Autoconfiguration for Mobile 2624 Ad Hoc Networks with Proactive Routing", Work in progress. 2626 Authors' Addresses 2628 Pr. Kenichi Mase 2629 Information and Communication Network Lab.,Niigata University 2630 Niigata University 2631 Niigata 950-2181, 2632 Japan 2634 Phone: +81 25 262 7446 2635 Email: mase@ie.niigata-u.ac.jp 2636 URI: http://www.net.ie.niigata-u.ac.jp/ 2638 Cedric Adjih 2639 Information and Communication Network Lab.,Niigata University 2640 Niigata University 2641 (Permanent address: INRIA Domaine de Voluceau, Rocquencourt, France) 2642 Niigata 950-2181, 2643 Japan 2645 Email: cedric@net.ie.niigata-u.ac.jp, cedric.adjih@inria.fr 2647 Index 2649 D 2650 Duplicate Address Detection Rule 2651 R1 13 2652 R2 14 2653 R3 14 2654 R4 16 2655 R5 16 2656 R6 18 2657 R7 19 2658 R8 20 2659 R9 21 2660 R10 22 2661 R11 23 2662 R12 24 2664 I 2665 Index 2666 Document structure 7 2668 S 2669 Specification 2670 Busy Address 33 2672 T 2673 terminology 2674 Address Conflict 9 2675 Autoconfiguration State 9 2676 Busy Address 9 2677 Conflicting Address 9 2678 Conflicting Message 9 2679 Conflicting Node 9 2680 DAD Rule 9 2681 Duplicate Address Detection (DAD) 9 2682 familiar address 9 2683 familiar node 9 2684 Message Content Identifier Generation Method 9 2685 Message Content Identifier 9 2686 NOA-OLSR 10 2687 Routing Table Contamination Avoidance 10 2688 Sequence Number Consistency 10 2689 Standard OLSR 10 2690 TC Generator 10 2691 unfamiliar node 9 2693 Intellectual Property Statement 2695 The IETF takes no position regarding the validity or scope of any 2696 Intellectual Property Rights or other rights that might be claimed to 2697 pertain to the implementation or use of the technology described in 2698 this document or the extent to which any license under such rights 2699 might or might not be available; nor does it represent that it has 2700 made any independent effort to identify any such rights. Information 2701 on the procedures with respect to rights in RFC documents can be 2702 found in BCP 78 and BCP 79. 2704 Copies of IPR disclosures made to the IETF Secretariat and any 2705 assurances of licenses to be made available, or the result of an 2706 attempt made to obtain a general license or permission for the use of 2707 such proprietary rights by implementers or users of this 2708 specification can be obtained from the IETF on-line IPR repository at 2709 http://www.ietf.org/ipr. 2711 The IETF invites any interested party to bring to its attention any 2712 copyrights, patents or patent applications, or other proprietary 2713 rights that may cover technology that may be required to implement 2714 this standard. Please address the information to the IETF at 2715 ietf-ipr@ietf.org. 2717 Disclaimer of Validity 2719 This document and the information contained herein are provided on an 2720 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 2721 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 2722 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 2723 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 2724 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2725 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2727 Copyright Statement 2729 Copyright (C) The Internet Society (2005). This document is subject 2730 to the rights, licenses and restrictions contained in BCP 78, and 2731 except as set forth therein, the authors retain all their rights. 2733 Acknowledgment 2735 Funding for the RFC Editor function is currently provided by the 2736 Internet Society.