idnits 2.17.1 draft-ietf-manet-nhdp-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 21. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 2152. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2163. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2170. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2176. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == Line 695 has weird spacing: '...dr_list is a ...' == Line 698 has weird spacing: '...I_manet is a ...' == Line 732 has weird spacing: '...dr_list is a ...' == Line 735 has weird spacing: '...RD_time is th...' == Line 739 has weird spacing: '...YM_time is th...' == (11 more instances...) == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- 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 30, 2007) is 6148 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) == Outdated reference: A later version (-17) exists of draft-ietf-manet-packetbb-04 == Outdated reference: A later version (-07) exists of draft-ietf-manet-iana-04 == Outdated reference: A later version (-08) exists of draft-ietf-manet-timetlv-00 == Outdated reference: A later version (-04) exists of draft-ietf-manet-jitter-00 ** Downref: Normative reference to an Informational draft: draft-ietf-manet-jitter (ref. '4') Summary: 3 errors (**), 0 flaws (~~), 12 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique, France 4 Intended status: Standards Track C. Dearlove 5 Expires: December 1, 2007 BAE Systems Advanced Technology 6 Centre 7 J. Dean 8 Naval Research Laboratory 9 The OLSRv2 Design Team 10 MANET Working Group 11 May 30, 2007 13 MANET Neighborhood Discovery Protocol (NHDP) 14 draft-ietf-manet-nhdp-03 16 Status of this Memo 18 By submitting this Internet-Draft, each author represents that any 19 applicable patent or other IPR claims of which he or she is aware 20 have been or will be disclosed, and any of which he or she becomes 21 aware will be disclosed, in accordance with Section 6 of BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt. 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 This Internet-Draft will expire on December 1, 2007. 41 Copyright Notice 43 Copyright (C) The IETF Trust (2007). 45 Abstract 47 This document describes a 1-hop and symmetric 2-hop neighborhood 48 discovery protocol (NHDP) for mobile ad hoc networks (MANETs). 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 53 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 54 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 7 55 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 8 56 4.1. Nodes and Interfaces . . . . . . . . . . . . . . . . . . . 8 57 4.2. Information Base Overview . . . . . . . . . . . . . . . . 9 58 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 10 59 4.3.1. HELLO Message Generation . . . . . . . . . . . . . . . 10 60 4.3.2. HELLO Message Content . . . . . . . . . . . . . . . . 11 61 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 12 62 5.1. Interface Parameters . . . . . . . . . . . . . . . . . . . 12 63 5.1.1. Message Intervals . . . . . . . . . . . . . . . . . . 12 64 5.1.2. Information Validity Times . . . . . . . . . . . . . . 13 65 5.1.3. Link Quality . . . . . . . . . . . . . . . . . . . . . 14 66 5.1.4. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 14 67 5.2. Node Parameters . . . . . . . . . . . . . . . . . . . . . 15 68 5.2.1. Information Validity Time . . . . . . . . . . . . . . 15 69 5.3. Parameter Change Constraints . . . . . . . . . . . . . . . 15 70 5.4. Constants . . . . . . . . . . . . . . . . . . . . . . . . 16 71 6. Local Information Base . . . . . . . . . . . . . . . . . . . . 17 72 6.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 17 73 7. Interface Information Base . . . . . . . . . . . . . . . . . . 18 74 7.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 18 75 7.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 19 76 8. Node Information Base . . . . . . . . . . . . . . . . . . . . 20 77 8.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . 20 78 8.2. Lost Neighbor Set . . . . . . . . . . . . . . . . . . . . 20 79 9. Local Information Base Changes . . . . . . . . . . . . . . . . 21 80 9.1. Adding an Interface . . . . . . . . . . . . . . . . . . . 21 81 9.2. Removing an Interface . . . . . . . . . . . . . . . . . . 21 82 9.3. Adding an Address to an Interface . . . . . . . . . . . . 22 83 9.4. Removing an Address from an Interface . . . . . . . . . . 22 84 10. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 23 85 10.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 23 86 10.1.1. Local Interface Block . . . . . . . . . . . . . . . . 23 87 10.1.2. Neighbor Address Blocks . . . . . . . . . . . . . . . 24 88 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 26 89 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 26 90 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 27 91 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 27 93 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 29 94 12.1. Updating the Neighbor Set . . . . . . . . . . . . . . . . 29 95 12.2. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 31 96 12.3. Updating the Link Set . . . . . . . . . . . . . . . . . . 31 97 12.4. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 32 98 13. Other Information Base Changes . . . . . . . . . . . . . . . . 34 99 13.1. Link Tuple Not Symmetric . . . . . . . . . . . . . . . . . 34 100 13.2. Link Tuple Symmetric . . . . . . . . . . . . . . . . . . . 35 101 13.3. Link Tuple Heard Timeout . . . . . . . . . . . . . . . . . 36 102 14. Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . 37 103 14.1. Deployment Without Link Quality . . . . . . . . . . . . . 37 104 14.2. Basic Principles of Link Quality . . . . . . . . . . . . . 37 105 14.3. When Link Quality Changes . . . . . . . . . . . . . . . . 38 106 14.4. Updating Link Quality . . . . . . . . . . . . . . . . . . 39 107 15. Proposed Values for Parameters and Constants . . . . . . . . . 40 108 15.1. Message Interval Interface Parameters . . . . . . . . . . 40 109 15.2. Information Validity Time Interface Parameters . . . . . . 40 110 15.3. Information Validity Time Node Parameters . . . . . . . . 40 111 15.4. Link Quality Interface Parameters . . . . . . . . . . . . 40 112 15.5. Jitter Interface Parameters . . . . . . . . . . . . . . . 40 113 15.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 40 114 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 41 115 16.1. Message Types . . . . . . . . . . . . . . . . . . . . . . 41 116 16.2. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 41 117 16.3. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 41 118 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 43 119 17.1. Normative References . . . . . . . . . . . . . . . . . . . 43 120 17.2. Informative References . . . . . . . . . . . . . . . . . . 43 121 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 44 122 Appendix B. HELLO Message Example . . . . . . . . . . . . . . . 45 123 Appendix C. Constraints . . . . . . . . . . . . . . . . . . . . 47 124 Appendix D. Security Considerations . . . . . . . . . . . . . . 49 125 Appendix D.1. Invalid HELLO messages . . . . . . . . . . . . . . . 49 126 Appendix E. Flow and Congestion Control . . . . . . . . . . . . 51 127 Appendix F. Contributors . . . . . . . . . . . . . . . . . . . . 52 128 Appendix G. Acknowledgements . . . . . . . . . . . . . . . . . . 53 129 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 54 130 Intellectual Property and Copyright Statements . . . . . . . . . . 55 132 1. Introduction 134 This document describes a neighborhood discovery protocol (NHDP) for 135 a mobile ad hoc network (MANET) [7]. This protocol uses an exchange 136 of HELLO messages in order that each node can determine the presence 137 and status of its 1-hop and symmetric 2-hop neighbors. This protocol 138 is designed to maintain this information in the presence of a dynamic 139 network topology. 141 The information maintained by this protocol may be used by other 142 protocols, such as MANET routing protocols, for determining local 143 connectivity and node configuration. 145 This specification describes both the HELLO message exchange, the 146 messages being defined as instances of the specification [1], and the 147 information storage required for neighborhood discovery. 149 This protocol makes no assumptions about the underlying link layer, 150 other than support of link local multicast. Link layer information 151 may be used if available and applicable. 153 This protocol is based on the neighborhood discovery process 154 contained in the Optimized Link State Routing Protocol (OLSR) [6]. 156 2. Terminology 158 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 159 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 160 document are to be interpreted as described in RFC2119 [5]. 162 The terms "packet", "message", "address", "address block", "TLV", and 163 "TLV block" in this document are to be interpreted as described in 164 [1]. 166 Additionally, this document uses the following terminology: 168 Node - A MANET router which implements this neighborhood discovery 169 protocol. 171 Interface - A network device, configured and assigned one or more IP 172 addresses. 174 MANET interface - An interface participating in a MANET and using 175 this neighborhood discovery protocol. A node may have several 176 MANET interfaces. 178 Heard - A MANET interface of node X is considered heard on a MANET 179 interface of a node Y if the latter can receive traffic from the 180 former. 182 Link - A pair of MANET interfaces from two different nodes, where at 183 least one interface is heard by the other. 185 Symmetric link - A link where both MANET interfaces are heard by the 186 other. 188 1-hop neighbor - A node X is a 1-hop neighbor of a node Y if a MANET 189 interface of node X is heard by a MANET interface of node Y. 191 Symmetric 1-hop neighbor - A node X is a symmetric 1-hop neighbor of 192 a node Y if a symmetric link exists between a MANET interface on 193 node X and a MANET interface on node Y. 195 Symmetric 2-hop neighbor - A node X is a symmetric 2-hop neighbor of 196 a node Y if node X is a symmetric 1-hop neighbor of a symmetric 197 1-hop neighbor of node Y, but is not node Y itself. 199 1-hop neighborhood - The 1-hop neighborhood of a node X is the set 200 of the 1-hop neighbors of node X. 202 Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a 203 node X is the set of the symmetric 1-hop neighbors of node X. 205 Symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of a 206 node X is the set of the symmetric 2-hop neighbors of node X. 207 (This may include nodes in the 1-hop neighborhood, or even in the 208 symmetric 1-hop neighborhood, of node X.) 210 Constant - A constant is a numerical value which MUST be the same 211 for all MANET interfaces of all nodes in the MANET, at all times. 213 Interface parameter - An interface parameter is a boolean or 214 numerical value, specified separately for each MANET interface of 215 each node. A node MAY change interface parameter values at any 216 time, subject to some constraints. 218 Node parameter - A node parameter is a boolean or numerical value, 219 specified for each node. A node MAY change node parameter values 220 at any time, subject to some constraints. 222 3. Applicability Statement 224 This neighborhood discovery protocol supports nodes which each have 225 one or more interfaces participating in the MANET [7]. It provides 226 each node with local topology information up to two hops away. This 227 information is made available to other protocols through Interface 228 Information Bases and a Node Information Base, described in Section 7 229 and Section 8. 231 The protocol is designed to work in networks with a dynamic topology, 232 and where messages may be lost, such as due to collisions in wireless 233 networks. If relevant link layer information is available then it 234 may be used by this protocol. 236 This protocol is designed to work in a completely distributed manner, 237 and does not depend on any central entity. It does not require any 238 changes to the format of IP packets, thus any existing IP protocol 239 stack can be used as is. It can use the link local multicast address 240 and MANET UDP port specified in [2]. 242 This protocol uses the packet and message formats specified in [1]. 243 HELLO messages specified by this protocol may be extended using the 244 TLV mechanisms described in [1]. For example, if multipoint relays 245 (MPRs) are to be calculated similarly to as in OLSR [6] and signaled 246 to neighbors, then this information may be added to HELLO messages 247 using an address block TLV. HELLO messages can also be transmitted 248 in packets with messages from other protocols that also use [1]. 250 4. Protocol Overview and Functioning 252 This protocol specifies local (one hop) signaling that: 254 o Advertises the presence of a node and its interfaces. 256 o Discovers links from adjacent nodes. 258 o Performs bidirectionality checks on the discovered links. 260 o Advertises discovered links, and whether each is symmetric, to its 261 1-hop neighbors, and hence discovers symmetric 2-hop neighbors. 263 o Maintains information bases describing discovered links, their 264 MANET interface addresses and status, current and former 1-hop 265 neighbors, and symmetric 2-hop neighbors. 267 4.1. Nodes and Interfaces 269 In order for a node to participate in a MANET, it MUST have at least 270 one, possibly more, MANET interfaces. Each MANET interface: 272 o Is characterized by a set of interface parameters, defining the 273 behavior of this interface. Each MANET interface MAY be 274 individually parameterized to accommodate the characteristics 275 experienced and the behavior desired on that interface. 277 o Has an Interface Information Base, recording information regarding 278 links to this MANET interface and symmetric 2-hop neighbors which 279 can be reached through such links. Each MANET interface has its 280 own Interface Information Base. 282 o Generates and processes HELLO messages, according to the interface 283 parameters for that interface. 285 In addition to a set of MANET interfaces as described above, each 286 node has: 288 o A Local Information Base, containing the IP addresses of the 289 interfaces of this node. 291 o A Node Information Base, recording information regarding current 292 and recently lost symmetric 1-hop neighbors of this node. 294 A node may have both MANET interfaces and non-MANET interfaces. 295 Interfaces of both of these types are recorded in a node's Local 296 Information Base, which is used, but not updated, by the signaling of 297 this protocol. 299 4.2. Information Base Overview 301 Each node maintains a Local Information Base, which contains: 303 o The Local Interface Set, which consists of Local Interface Tuples, 304 each of which records the addresses of an interface of the node. 306 Each node maintains, for each of its MANET interfaces, an Interface 307 Information Base, which contains: 309 o A Link Set, which consists of Link Tuples, each of which records 310 information about a current or recently lost link from a MANET 311 interface of a 1-hop neighbor to this MANET interface. A Link 312 Tuple for a lost link is maintained for purposes of advertisement 313 in HELLO messages and hence accelerated removal of this link from 314 the relevant 1-hop neighbors' Link Sets. Link quality 315 information, if used and available, may be recorded in a Link 316 Tuple; if this indicates that a link is of too low quality to be 317 currently useable, then that link is also treated as lost. 319 o A 2-Hop Set, which consists of 2-Hop Tuples, each of which records 320 a MANET interface of a symmetric 1-hop neighbor, and an address of 321 a symmetric 2-hop neighbor of this node. The former MANET 322 interface must have a symmetric link to this interface, and the 323 former node must be a symmetric 1-hop neighbor of the latter node. 324 The 2-Hop Set is updated by the signaling of this protocol, but is 325 not itself reported in that signaling. 327 Each node maintains a Node Information Base, which contains: 329 o The Neighbor Set, which consists of Neighbor Tuples, each of which 330 records all interface addresses of a 1-hop neighbor. There MUST 331 be a current link from a MANET interface of this 1-hop neighbor to 332 a MANET interface of this node, although this link MAY be 333 currently considered as lost due to insufficient link quality. 334 Neighbor Tuples are maintained in the Neighbor Set as long as 335 there are corresponding current Link Tuples in the Link Set. A 336 Neighbor Tuple allows all addresses of all interfaces of a 1-hop 337 neighbors to be associated with each other, including addresses of 338 interfaces not represented in the Link Set. Neighbor Tuples allow 339 all addresses of interfaces of symmetric 1-hop neighbors to be 340 included in HELLO messages on all MANET interfaces of this node. 342 o The Lost Neighbor Set, which consists of Lost Neighbor Tuples, 343 each of which records an address of an interface of a recently 344 lost symmetric 1-hop neighbor. Lost Neighbor Tuples allow 345 advertising such addresses as lost, in order that these addresses 346 can be removed from other nodes' 2-Hop Sets. 348 These sets are used for describing the protocol in this document. An 349 implementation of this protocol MAY maintain this information in the 350 indicated form, or in any other organization which offers access to 351 this information. 353 This protocol contains a signaling mechanism for maintaining the 354 Interface Information Bases and the Node Information Base. If 355 information from the link layer, or any other source, is available 356 and appropriate, it may be used to update these. Such updates are 357 subject to the constraints specified in Appendix C. 359 Some links in a MANET may be marginal, e.g. due to adverse wireless 360 propagation. In order to avoid using such marginal links, a link 361 quality is associated with each link in the Link Set, and links with 362 insufficient link quality are considered lost. Modifying the link 363 quality of a link is OPTIONAL. If link quality is not to be modified 364 it MUST be set to indicate an always usable quality link. Link 365 quality information is only used locally, it is not used in 366 signaling, and nodes may interoperate whether they are using the 367 same, different, or no, link quality information. 369 4.3. Signaling Overview 371 Signaling consists of a single type of message, known as a HELLO 372 message. Each node generates HELLO messages for each of its MANET 373 interfaces. Each HELLO message identifies that MANET interface, and 374 reports the other interfaces of the node. Each HELLO message 375 includes information from the Link Set of the Interface Information 376 Base of the MANET interface, and from the Node Information Base of 377 the node. 379 4.3.1. HELLO Message Generation 381 HELLO messages are generated by a node for each of its MANET 382 interfaces, and MAY be sent: 384 o Proactively, at a regular interval, known as HELLO_INTERVAL. 385 HELLO_INTERVAL may be fixed, or may be dynamic. For example 386 HELLO_INTERVAL may be backed off due to congestion or network 387 stability. 389 o As a response to a change in the node itself, or its 1-hop 390 neighborhood, for example on first becoming active or in response 391 to a new, broken, or changed status link. 393 o In a combination of these proactive and responsive mechanisms. 395 Jittering of HELLO message generation and transmission, as described 396 in Section 11.2, MAY be used if appropriate. 398 HELLO messages are generated independently on each MANET interface of 399 a node. HELLO messages MAY be scheduled independently for each MANET 400 interface, or, interface parameters permitting, using the same 401 schedule for all MANET interfaces of a node. 403 4.3.2. HELLO Message Content 405 Each HELLO message sent over a MANET interface need not contain all 406 of the information appropriate to that MANET interface, however: 408 o A HELLO message MUST contain all of the addresses in the Local 409 Interface Set of the node to which the MANET interface belongs. 411 o Within every time interval of length REFRESH_INTERVAL, the HELLO 412 messages sent on each MANET interface of a node must collectively 413 include: 415 * All of the information in the Link Set of the Interface 416 Information Base of that MANET interface (other than link 417 quality and information relating to pending links). 419 * All of the information in the Node Information Base of that 420 node. 422 This applies to otherwise purely responsive nodes as well as 423 proactive nodes. In either case it means that all information 424 appropriate to that MANET interface will have always been 425 transmitted, in one or more HELLO messages, since the time 426 REFRESH_INTERVAL ago. 428 o A HELLO message MUST include a VALIDITY_TIME message TLV that 429 indicates the length of time for which the message content is to 430 be considered valid, and included in the receiving node's 431 Interface Information Base. 433 o A periodically generated HELLO message SHOULD include an 434 INTERVAL_TIME message TLV that indicates the current value of 435 HELLO_INTERVAL for that MANET interface, i.e. the period within 436 which a further HELLO message is guaranteed to be sent on that 437 MANET interface. 439 5. Protocol Parameters and Constants 441 The parameters and constants used in this specification are described 442 in this section. 444 5.1. Interface Parameters 446 The interface parameters used by this specification may be classified 447 into the following four categories: 449 o Message intervals 451 o Information validity times 453 o Link quality 455 o Jitter 457 These are detailed in the following sections. 459 Different MANET interfaces (on the same or on different nodes) MAY 460 employ different interface parameter values, and may change their 461 interface parameter values dynamically, subject to the constraints 462 given in this section. A particular case is where all MANET 463 interfaces on all MANET nodes within a given MANET employ the same 464 set of interface parameter values. 466 5.1.1. Message Intervals 468 The following interface parameters regulate HELLO message 469 transmissions over a given MANET interface. 471 HELLO messages serve two principal functions: 473 o To advertise this nodes own addresses to its 1-hop neighbors. The 474 frequency of these advertisements is regulated by the interface 475 parameters HELLO_INTERVAL and HELLO_MIN_INTERVAL. 477 o To advertise this nodes knowledge of each of its 1-hop neighbors. 478 The frequency of the advertisement of each such neighbor is 479 regulated by the interface parameter REFRESH_INTERVAL. 481 Specifically, these parameters are as follows: 483 HELLO_INTERVAL - is the maximum time between the transmission of two 484 successive HELLO messages on this MANET interface. If using 485 periodic transmission of HELLO messages, these SHOULD be at a 486 separation of HELLO_INTERVAL, possibly modified by jitter as 487 specified in [4]. 489 HELLO_MIN_INTERVAL - is the minimum interval between transmission of 490 two successive HELLO messages, on this MANET interface. (This 491 minimum interval MAY be modified by jitter, as defined in [4].) 493 REFRESH_INTERVAL - is the maximum interval between advertisements in 494 a HELLO message of each 1-hop neighbor address and its status. In 495 all intervals of length REFRESH_INTERVAL, a node MUST include all 496 1-hop neighbor information which it is specified as sending in at 497 least one HELLO message on this MANET interface. 499 The following constraints apply to these interface parameters: 501 o HELLO_INTERVAL > 0 503 o HELLO_MIN_INTERVAL >= 0 505 o HELLO_INTERVAL >= HELLO_MIN_INTERVAL 507 o REFRESH_INTERVAL >= HELLO_INTERVAL 509 o If INTERVAL_TIME TLVs as defined in [3] are included in HELLO 510 messages, then HELLO_INTERVAL MUST be representable as described 511 in [3]. 513 If REFRESH_INTERVAL > HELLO_INTERVAL, then a node may distribute its 514 neighbor advertisements between HELLO messages in any manner, subject 515 to the constraints above. 517 For a node to employ this protocol in a purely responsive manner on a 518 MANET interface, REFRESH_INTERVAL and HELLO_INTERVAL SHOULD both be 519 set to a value such that a responsive HELLO message is always 520 expected in a shorter period than this. 522 5.1.2. Information Validity Times 524 The following interface parameters manage the validity time of link 525 information: 527 L_HOLD_TIME - is the period of advertisement, on this MANET 528 interface, of former 1-hop neighbor addresses as lost in HELLO 529 messages, allowing recipients of these HELLO messages to 530 accelerate removal of information from their Link Sets. 531 L_HOLD_TIME can be set to zero if accelerated information removal 532 is not required. 534 H_HOLD_TIME - is used as the value in the VALIDITY_TIME TLV included 535 in all HELLO messages on this MANET interface. 537 The following constraints apply to these interface parameters: 539 o L_HOLD_TIME >= 0 541 o H_HOLD_TIME >= REFRESH_INTERVAL 543 o If HELLO messages can be lost then both SHOULD be significantly 544 greater than REFRESH_INTERVAL. 546 o H_HOLD_TIME MUST be representable as described in [3]. 548 5.1.3. Link Quality 550 The following interface parameters manage the usage of link quality: 552 HYST_ACCEPT - is the link quality threshold at or above which a link 553 becomes usable, if it was not already so. 555 HYST_REJECT - is the link quality threshold below which a link 556 becomes unusable, if it was not already so. 558 INITIAL_QUALITY - is the initial quality of a newly identified link. 560 INITIAL_PENDING - if true, then a newly identified link is 561 considered pending, and is not usable until the link quality has 562 reached or exceeded the HYST_ACCEPT threshold. 564 The following constraints apply to these interface parameters: 566 o 0 <= HYST_REJECT <= HYST_ACCEPT <= 1 568 o 0 <= INITIAL_QUALITY <= 1. 570 o If link quality is not updated, then INITIAL_QUALITY >= 571 HYST_ACCEPT. 573 o If INITIAL_QUALITY >= HYST_ACCEPT, then INITIAL_PENDING == false. 575 o If INITIAL_QUALITY < HYST_REJECT, then INITIAL_PENDING == true. 577 5.1.4. Jitter 579 If jitter, as defined in [4], is used then these parameters are as 580 follows: 582 HP_MAXJITTER - represents the value of MAXJITTER used in [4] for 583 periodically generated HELLO messages on this MANET interface. 585 HT_MAXJITTER - represents the value of MAXJITTER used in [4] for 586 externally triggered HELLO messages on this MANET interface. 588 For constraints on these interface parameters see [4]. 590 5.2. Node Parameters 592 Only one node parameter is defined by this specification, in the 593 category of information validity time. 595 5.2.1. Information Validity Time 597 The following node parameter manages the validity time of lost 598 symmetric 1-hop neighbor information: 600 N_HOLD_TIME - is used as the period during which former 1-hop 601 neighbor addresses are advertised as lost in HELLO messages, 602 allowing recipients of these HELLO messages to accelerate removal 603 of information from their 2-Hop Sets. N_HOLD_TIME can be set to 604 zero if accelerated information removal is not required. 606 The following constraint applies to this node parameter: 608 o N_HOLD_TIME >= 0 610 5.3. Parameter Change Constraints 612 This section presents guidelines, applicable if protocol parameters 613 are changed dynamically. 615 HELLO_INTERVAL 617 * If the HELLO_INTERVAL for a MANET interface increases, then the 618 next HELLO message on this MANET interface MUST be generated 619 according to the previous, shorter, HELLO_INTERVAL. Additional 620 subsequent HELLO messages MAY be generated according to the 621 previous, shorter, HELLO_INTERVAL. 623 * If the HELLO_INTERVAL for a MANET interface decreases, then the 624 following HELLO messages on this MANET interface SHOULD be 625 generated according to this current, shorter, HELLO_INTERVAL. 627 REFRESH_INTERVAL 629 * If the REFRESH_INTERVAL for a MANET interface increases, then 630 the content of subsequent HELLO messages must be organized such 631 that the specification of the old value of REFRESH_INTERVAL is 632 satisfied for a further period equal to the old value of 633 REFRESH_INTERVAL. 635 * If the REFRESH_INTERVAL for a MANET interface decreases, then 636 it MAY be necessary to reschedule HELLO message generation on 637 that MANET interface, in order that the specification of 638 REFRESH_INTERVAL is satisfied from the time of change. 640 HYST_ACCEPT and HYST_REJECT 642 * If HYST_ACCEPT or HYST_REJECT changes, then the appropriate 643 actions for link quality change, as specified in Section 14.3 644 MUST be taken. 646 L_HOLD_TIME 648 * If L_HOLD_TIME changes, then L_time for all relevant Link 649 Tuples SHOULD be changed. 651 N_HOLD_TIME 653 * If N_HOLD_TIME changes, then NL_time for all relevant Lost 654 Neighbor Tuples SHOULD be changed. 656 HP_MAXJITTER 658 * If HP_MAXJITTER changes, then the periodic HELLO message 659 schedule on this MANET interface MAY be changed. 661 HT_MAXJITTER 663 * If HT_MAXJITTER changes, then externally triggered HELLO 664 messages on this MANET interface MAY be rescheduled. 666 5.4. Constants 668 The constant C is used as specified in [3]. 670 6. Local Information Base 672 A node maintains a Local Information Base that records information 673 about its local interfaces (MANET interfaces or otherwise). Each 674 such interface MUST have at least one address, and MAY have more than 675 one address. All addresses have an associated prefix length, which 676 is included with all addresses in the Local Information Base. If an 677 address otherwise does not have a prefix length then it is considered 678 to be equal to the address length. Two addresses are considered 679 equal if and only if their associated prefix lengths are also equal. 681 The Local Information Base is not modified by this protocol. This 682 protocol MAY respond to changes of this Local Information Base which 683 MUST reflect corresponding changes in the node's interface 684 configuration. 686 6.1. Local Interface Set 688 A node's Local Interface Set records its local interfaces. It 689 consists of Local Interface Tuples, one per interface: 691 (I_local_iface_addr_list, I_manet) 693 where: 695 I_local_iface_addr_list is a list of the addresses of this 696 interface. 698 I_manet is a boolean flag, describing if this interface is a MANET 699 interface. 701 7. Interface Information Base 703 A node maintains an Interface Information Base for each of its MANET 704 interfaces. This records information about links to that MANET 705 interface and symmetric 2-hop neighbors which can be reached in two 706 hops using those links as the first hop. The Interface Information 707 Base includes the Link Set and the 2-Hop Set. 709 A MANET interface address can be present in both the Link Set and as 710 of a symmetric 2-hop neighbor. This allows the node with this MANET 711 interface address to be immediately considered as a symmetric 2-hop 712 neighbor if it fails to be a symmetric 1-hop neighbor. 714 All addresses MUST have an associated prefix length, which is 715 included in all addresses in the Interface Information Base. Prefix 716 lengths are indicated in HELLO messages using the PREFIX_LENGTH TLV 717 specified in [1]; if an address has no such TLV, then its prefix 718 length is equal to the address length. Two addresses are considered 719 equal if and only if their associated prefix lengths are also equal. 721 7.1. Link Set 723 A node's Link Set records links from other nodes which are, or 724 recently were, 1-hop neighbors. It consists of Link Tuples, each 725 representing a single link: 727 (L_neighbor_iface_addr_list, L_HEARD_time, 728 L_SYM_time, L_quality, L_pending, L_lost, L_time) 730 where: 732 L_neighbor_iface_addr_list is a list of the addresses of the MANET 733 interface of the 1-hop neighbor; 735 L_HEARD_time is the time until which the MANET interface of the 736 1-hop neighbor would be considered heard if not considering link 737 quality; 739 L_SYM_time is the time until which the link to the 1-hop neighbor 740 would be considered symmetric if not considering link quality; 742 L_quality is a dimensionless number between 0 (inclusive) and 1 743 (inclusive) describing the quality of a link; a greater value of 744 L_quality indicating a higher quality link; 746 L_pending is a boolean flag, describing if a link is considered 747 pending (i.e. a candidate, but not yet established, link); 749 L_lost is a boolean flag, describing if a link is considered lost 750 due to link quality; 752 L_time specifies when this Tuple expires and MUST be removed. 754 The status of the link, as obtained through HELLO message exchange, 755 and also taking link quality into account, denoted L_status, is 756 defined by: 758 1. If L_pending is true, then L_status = PENDING; 760 2. otherwise, if L_lost is true, then L_status = LOST; 762 3. otherwise, if L_SYM_time is not expired, then L_status = 763 SYMMETRIC; 765 4. otherwise, if L_HEARD_time is not expired, then L_status = HEARD; 767 5. otherwise, L_status = LOST. 769 7.2. 2-Hop Set 771 A node's 2-Hop Set records symmetric 2-hop neighbors, and the 772 symmetric links to symmetric 1-hop neighbors through which the 773 symmetric 2-hop neighbors can be reached. It consists of 2-Hop 774 Tuples, each representing a single interface address of a symmetric 775 2-hop neighbor, and a single MANET interface of a symmetric 1-hop 776 neighbor. 778 (N2_neighbor_iface_addr_list, N2_2hop_iface_addr, N2_time) 780 where: 782 N2_neighbor_iface_addr_list is a list of the addresses of the MANET 783 interface of the symmetric 1-hop neighbor from which this 784 information was received; 786 N2_2hop_iface_addr is an address of an interface of a symmetric 787 2-hop neighbor which has a symmetric link (using any MANET 788 interface) to the indicated symmetric 1-hop neighbor; 790 N2_time specifies when this Tuple expires and MUST be removed. 792 8. Node Information Base 794 Each node maintains a Node Information Base that records information 795 about addresses of current and recently symmetric 1-hop neighbors. 797 All addresses MUST have an associated prefix length, which is 798 included in all addresses in the Node Information Base. Prefix 799 lengths are indicated in HELLO messages using the PREFIX_LENGTH TLV 800 specified in [1]; if an address has no such TLV, then its prefix 801 length is equal to the address length. Two addresses are considered 802 equal if and only if their associated prefix lengths are also equal. 804 8.1. Neighbor Set 806 A node's Neighbor Set records all interface addresses of each 1-hop 807 neighbor. It consists of Neighbor Tuples, each representing a single 808 1-hop neighbor: 810 (N_neighbor_iface_addr_list, N_symmetric) 812 where: 814 N_neighbor_iface_addr_list is a list of the interface addresses of a 815 1-hop neighbor; 817 N_symmetric is a boolean flag, describing if this is a symmetric 818 1-hop neighbor. 820 8.2. Lost Neighbor Set 822 A node's Lost Neighbor Set records addresses of all interfaces of 823 nodes which recently were symmetric 1-hop neighbors, but are now 824 advertised as lost. It consists of Lost Neighbor Tuples, each 825 representing a single such address: 827 (NL_neighbor_iface_addr, NL_time) 829 where: 831 NL_neighbor_iface_addr is an address of an interface of a node which 832 recently was a symmetric 1-hop neighbor of this node; 834 NL_time specifies when this Tuple expires and MUST be removed. 836 9. Local Information Base Changes 838 The Local Information Base MUST change to respond to changes in the 839 node's interfaces. The node MUST update its Interface and Node 840 Information Bases in response to such changes. If any changes in the 841 Interface and Node Information Bases satisfy any of the conditions 842 described in Section 13, then those changes must be applied 843 immediately, unless noted otherwise. 845 A node MAY transmit HELLO messages in response to these changes. 847 9.1. Adding an Interface 849 If an interface is added to the node then this is indicated by the 850 addition of a Local Interface Tuple to the Local Interface Set. If 851 the new interface is a MANET interface then an initially empty 852 Interface Information Base MUST be created for this new MANET 853 interface. The actions in Section 9.3 MUST be taken for each address 854 of the added interface. A HELLO message MAY be sent on all MANET 855 interfaces, it SHOULD be sent on the new interface if it is a MANET 856 interface. If using scheduled messages, then a message schedule MUST 857 be established on a new MANET interface. 859 9.2. Removing an Interface 861 If a MANET interface is removed from the node, then this MUST result 862 in removal of information from the Local Information Base and the 863 Neighborhood Information Base as follows: 865 1. Remove the Local Interface Tuple that corresponds to the 866 interface to be removed from the Local Interface Set. 868 2. If the interface to be removed is a MANET interface (i.e. with 869 I_manet == true) then: 871 1. Remove the Interface Information Base for that MANET 872 interface; 874 2. All Neighbor Tuples for which none of the addresses in its 875 N_neighbor_iface_addr_list are found in any 876 L_neighbor_iface_addr_list in any remaining Link Set, are 877 removed. 879 If a node removes the Local Interface Tuple that contains the 880 interface address that is used to define the node's originator 881 address, as defined in [1], then the node MAY change originator 882 address. 884 If the removed interface is the last MANET interface of the node, 885 then there will be no remaining Interface Information Bases, and the 886 node will longer participate in this protocol. 888 A HELLO message MAY be sent on all remaining MANET interfaces. 890 9.3. Adding an Address to an Interface 892 If an address is added to an interface then this is indicated by the 893 addition of an address to the appropriate I_local_iface_addr_list. 894 The following changes MUST be made to the Information Bases: 896 1. The Neighbor Tuples, if any, whose N_neighbor_iface_addr_list 897 contains the added address, are removed. 899 2. Any Link Tuples, in any Link Set, whose 900 L_neighbor_iface_addr_list contains: 902 * the added address; OR 904 * any address in the N_neighbor_iface_addr_list of the removed 905 Neighbor Tuples, if any 907 are removed; apply Section 13.1, but not Section 13.3. 909 3. Any Lost Neighbor Tuples whose NL_neighb_iface_addr is the added 910 address, are removed. 912 4. Any 2-Hop Tuples whose N2_2hop_iface_addr is the added address, 913 are removed. 915 A HELLO message MAY be sent on all MANET interfaces. 917 9.4. Removing an Address from an Interface 919 If an address is removed from an interface then this is indicated by 920 the removal of an address from the appropriate 921 I_local_iface_addr_list. If this list is now empty then the 922 corresponding Local Interface Tuple MUST be removed. 924 If a node removes the interface address that is used to define the 925 node's originator address, as defined in [1], then the node MAY 926 change originator address. 928 A HELLO message MAY be sent on all MANET interfaces. 930 10. Packets and Messages 932 The packet and message format used by this protocol is defined in 933 [1], which is used with the following considerations: 935 o This protocol specifies one message type, the HELLO message. 937 o HELLO message header options MAY be used as specified by a 938 protocol which uses this neighborhood discovery protocol. 940 o HELLO messages MUST NOT be forwarded. 942 o HELLO messages MAY be included in multi-message packets as 943 specified in [1]. 945 o Packet header options MAY be used as specified by a protocol which 946 uses this neighborhood discovery protocol. 948 10.1. HELLO Messages 950 A HELLO message MUST contain: 952 o A VALIDITY_TIME message TLV as specified in [3], representing 953 H_HOLD_TIME for the transmitting MANET interface. 955 o An address block, with an associated TLV block, known as the Local 956 Interface Block, as specified in Section 10.1.1. 958 A HELLO message which is transmitted periodically SHOULD contain, and 959 otherwise MAY contain: 961 o An INTERVAL_TIME message TLV as specified in [3], representing 962 HELLO_INTERVAL for the transmitting MANET interface. 964 A HELLO message MAY contain: 966 o One or more address blocks, each with an associated TLV block, 967 known as Neighbor Address Blocks, as specified in Section 10.1.2. 969 o Other message TLVs. 971 10.1.1. Local Interface Block 973 The first address block, plus following TLV block, in a HELLO message 974 is known as the Local Interface Block. The Local Interface Block is 975 not distinguished in any way other than by being the first address 976 block in the HELLO message. 978 The Local Interface Block MUST contain all of the addresses in that 979 node's Local Interface Set. Those addresses, if any, which correspond 980 to interfaces other than the MANET interface for which the HELLO 981 message is transmitted MUST be associated with a corresponding TLV 982 with Type == OTHER_IF as specified in Table 1. Addresses of the 983 MANET interface on which the HELLO message is transmitted MUST NOT be 984 associated with such a TLV. 986 Note that a Local Interface Block MAY include more than one address 987 for each MANET interface, and hence a HELLO message MAY contain more 988 than one address without an OTHER_IF TLV. 990 +--------------+-----------------+----------------------------------+ 991 | Name | Value Length | Description | 992 +--------------+-----------------+----------------------------------+ 993 | OTHER_IF | 0 bits | Specifies that the address, in | 994 | | | the Local Interface Block of the | 995 | | | message, is an address | 996 | | | associated with an interface | 997 | | | other than the MANET interface | 998 | | | on which the message is | 999 | | | transmitted | 1000 +--------------+-----------------+----------------------------------+ 1002 Table 1 1004 10.1.2. Neighbor Address Blocks 1006 Address blocks, each with a following TLV block, in a HELLO message, 1007 after the Local Interface Block, are known as Neighbor Address 1008 Blocks. These Neighbor Address Blocks are not distinguished in any 1009 way other than by not being the first address block in the HELLO 1010 message. A HELLO message MAY contain no Neighbor Address Blocks. 1012 A Neighbor Address Block contains current or recently lost 1-hop 1013 neighbors' interface addresses, each of which is associated with 1014 address block TLVs as described in Table 2. Other addresses MAY be 1015 included in Neighbor Address Blocks, but MUST NOT be associated with 1016 any of the TLVs specified in Table 2. 1018 +--------------+-----------------+----------------------------------+ 1019 | Name | Value Length | Description | 1020 +--------------+-----------------+----------------------------------+ 1021 | LINK_STATUS | 8 bits | Specifies the status of the link | 1022 | | | from the indicated address | 1023 | | | (LOST, SYMMETRIC or HEARD) | 1024 | | | | 1025 | OTHER_NEIGHB | 8 bits | Specifies that the address is | 1026 | | | (SYMMETRIC) or was (LOST) of an | 1027 | | | interface of a symmetric 1-hop | 1028 | | | neighbor of the node | 1029 | | | transmitting the HELLO message | 1030 +--------------+-----------------+----------------------------------+ 1032 Table 2 1034 A TLV with Type == LINK_STATUS and (Value == SYMMETRIC or Value == 1035 LOST) also performs the function of a TLV with Type == OTHER_IF and 1036 the same value. The latter SHOULD NOT also be included. If a TLV 1037 with Type == LINK_STATUS and Value == SYMMETRIC is combined with a 1038 TLV with Type == OTHER_IF and Value == LOST then the latter MUST be 1039 ignored, and SHOULD NOT be included. See Appendix A. 1041 11. HELLO Message Generation 1043 Each MANET interface MUST generate HELLO messages according to the 1044 specification in this section. HELLO message generation and 1045 scheduling MUST be according to the interface parameters for that 1046 MANET interface and MAY be independent for each MANET interface or, 1047 interface parameters permitting, MANET interfaces MAY use the same 1048 schedule. 1050 If transmitting periodic HELLO messages then, following a HELLO 1051 message transmission on a MANET interface, another HELLO message MUST 1052 be transmitted on the same MANET interface after an interval not 1053 greater than HELLO_INTERVAL. Two successive HELLO message 1054 transmissions on the same MANET interface MUST be separated by at 1055 least HELLO_MIN_INTERVAL, except as noted in Section 11.2.1. 1057 11.1. HELLO Message Specification 1059 HELLO messages are generated independently on each MANET interface. 1061 A HELLO message MUST include a Local Interface Block, as specified in 1062 Section 10.1.1, as its first address block. 1064 Other addresses which MUST be included in Neighbor Address Blocks, as 1065 specified in Section 10.1.2, in HELLO messages sent over a given 1066 MANET interface are: 1068 o Addresses of MANET interfaces of 1-hop neighbors from the Link Set 1069 of the Interface Information Base for this MANET interface. 1071 o Other addresses of symmetric 1-hop neighbors from the Neighbor Set 1072 of this node's Node Information Base. 1074 o Addresses of MANET interfaces of previously symmetric or heard 1075 1-hop neighbors connected on this MANET interface from the Link 1076 Set of the Interface Information Base for this MANET interface. 1077 (These are advertised for a period equal to this interface's 1078 L_HOLD_TIME after loss.) 1080 o Other addresses of previously symmetric 1-hop neighbors from the 1081 Lost Neighbor Set of this node's Node Information Base. (These 1082 are advertised for a period equal to N_HOLD_TIME after loss.) 1084 The addresses, and their associated TLVs, which may be included in 1085 any HELLO message sent on this MANET interface (respecting 1086 REFRESH_INTERVAL for this MANET interface) are: 1088 1. For each address (henceforth linked address) which appears in a 1089 Link Tuple in the Link Set for this MANET interface, for which 1090 L_status does not equal PENDING, include the linked address with 1091 an associated TLV with: 1093 * Type = LINK_STATUS; AND 1095 * Value = L_status. 1097 2. For each address (henceforth neighbor address) which appears in 1098 an N_neighbor_iface_addr_list in a Neighbor Tuple with 1099 N_symmetric == true, and which has not already been included with 1100 an associated TLV with (Type == LINK_STATUS and Value == 1101 SYMMETRIC), include the neighbor address with an associated TLV 1102 with: 1104 * Type = OTHER_NEIGHB; AND 1106 * Value = SYMMETRIC. 1108 3. For each Lost Neighbor Tuple whose NL_neighbor_iface_addr 1109 (henceforth lost address) has not already been included, include 1110 the lost address with an associated TLV with: 1112 * Type = OTHER_NEIGHB; AND 1114 * Value = LOST. 1116 If an address is specified with more than one associated TLV, then 1117 these TLVs MAY be independently included or excluded from each HELLO 1118 message. Each such TLV MUST be included associated with that address 1119 in a HELLO message sent on that MANET interface in every interval of 1120 length equal to that MANET interface's parameter REFRESH_INTERVAL. 1121 TLVs associated with the same address included in the same HELLO 1122 message MAY be applied to the same or different copies of that 1123 address. 1125 11.2. HELLO Message Transmission 1127 HELLO messages are transmitted in the packet/message format specified 1128 by [1] using the "LL MANET Routers" multicast address specified by 1129 [2] as destination IP address, using the MANET UDP port specified in 1130 [2]. 1132 11.2.1. HELLO Message Jitter 1134 HELLO messages MAY be sent using periodic message generation or 1135 externally triggered message generation. If using data link and 1136 physical layers which are subject to packet loss due to collisions, 1137 HELLO messages SHOULD be jittered as described in [4]. 1139 Internally triggered message generation (such as due to a change in 1140 local interfaces) MAY be treated as if externally generated message 1141 generation, or MAY be not jittered. 1143 HELLO messages MUST NOT be forwarded, and thus message forwarding 1144 jitter does not apply to HELLO messages. 1146 Each form of jitter described in [4] requires a parameter MAXJITTER. 1147 These interface parameters may be dynamic, and are specified by: 1149 o For periodic message generation: HP_MAXJITTER, which MUST be 1150 significantly less than HELLO_INTERVAL. 1152 o For externally triggered message generation: HT_MAXJITTER. If 1153 HELLO messages are also periodically generated, then HT_MAXJITTER 1154 also MUST be significantly less than HELLO_INTERVAL. 1156 When HELLO message generation is delayed in order that a HELLO 1157 message is not sent within HELLO_MIN_INTERVAL of the previous HELLO 1158 message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD 1159 be reduced by jitter, with maximum reduction HP_MAXJITTER. In this 1160 case HP_MAXJITTER MUST NOT be greater than HELLO_MIN_INTERVAL. 1162 12. HELLO Message Processing 1164 On receiving a HELLO message, a node MUST first check if any address 1165 in its Local Interface Block is one of its interface addresses (i.e. 1166 is in any I_local_iface_addr_list in the Local Interface Set). If so 1167 then the HELLO message MUST be discarded. 1169 Otherwise the receiving node MUST update its appropriate Interface 1170 Information Base and its Node Information Base according to this 1171 section. If any changes satisfy any of the conditions described in 1172 Section 13 then the indicated consequences MUST be applied 1173 immediately, unless noted otherwise. 1175 For the purpose of this section, note the following definitions: 1177 o "validity time" is calculated from the VALIDITY_TIME TLV of the 1178 HELLO message as specified in [3]. 1180 o "Receiving Address List" is the I_local_iface_addr_list 1181 corresponding to the MANET interface on which the HELLO message 1182 was received 1184 o "Neighbor Address List" is the list of the addresses contained in 1185 the Local Interface Block of the HELLO message. 1187 o "Sending Address List" is the list of the addresses contained in 1188 the Local Interface Block of the HELLO message which do not have 1189 an associated TLV with Type == OTHER_IF. 1191 o EXPIRED indicates that a timer is set to a value clearly preceding 1192 the current time (e.g. current time - 1). 1194 o "Removed Address List" is a list of addresses created by this 1195 HELLO message processing which were formerly reported as local by 1196 the node originating the HELLO message, but which are not included 1197 in the Neighbor Address List. This list is initialized as empty. 1199 o "Lost Address List" is a subset of the Removed Address List 1200 containing addresses which were formerly considered as symmetric. 1201 This list is initialized as empty. 1203 12.1. Updating the Neighbor Set 1205 On receiving a HELLO message, the node MUST update its Neighbor Set 1206 and populate the Removed Address List and Lost Address List: 1208 1. Find all Neighbor Tuples (hereafter matching Neighbor Tuples) 1209 where: 1211 * N_neighbor_iface_addr_list contains at least one address in 1212 the Neighbor Address List. 1214 2. If there are no matching Neighbor Tuples, then: 1216 1. Create a new Neighbor Tuple with: 1218 + N_neighbor_iface_addr_list = Neighbor Address List; 1220 + N_symmetric = false. 1222 3. If there is one matching Neighbor Tuple, then: 1224 1. If the N_neighbor_iface_addr_list of the matching Neighbor 1225 Tuple is not equal to the Neighbor Address List, then: 1227 1. For each address (henceforth removed address) which is in 1228 the N_neighbor_iface_addr_list, but not in the Neighbor 1229 Address List: 1231 1. Add the removed address to the Removed Address List. 1233 2. If N_symmetric == true, then add the removed address 1234 to the Lost Address List. 1236 2. Update the matching Neighbor Tuple by: 1238 - N_neighbor_iface_addr_list = Neighbor Address List. 1240 4. If there are two or more matching Neighbor Tuples, then: 1242 1. For each address (henceforth removed address) which is in the 1243 N_neighbor_iface_addr_list of any of the matching Neighbor 1244 Tuples: 1246 1. Add the removed address to the Removed Address List. 1248 2. If N_symmetric == true, then add the removed address to 1249 the Lost Address List. 1251 2. Replace the matching Neighbor Tuples by a single Neighbor 1252 Tuple with: 1254 + N_neighbor_iface_addr_list = Neighbor Address List; 1256 + N_symmetric = false 1258 12.2. Updating the Lost Neighbor Set 1260 On receiving a HELLO message, a node MUST update its Lost Neighbor 1261 Set: 1263 1. For each address (henceforth lost address) in the Lost Neighbor 1264 List, if no Lost Neighbor Tuple with NL_neighbor_iface_addr == 1265 lost address exists, then add a Lost Neighbor Tuple with: 1267 * NL_neighbor_iface_addr = lost address; 1269 * NL_time = current time + N_HOLD_TIME. 1271 12.3. Updating the Link Set 1273 On receiving a HELLO message, a node MUST update its Link Set for the 1274 MANET interface on which the HELLO message is received: 1276 1. Remove all addresses in the Removed Address List from the 1277 L_neighbor_iface_addr_list of all Link Tuples. 1279 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now 1280 empty; apply Section 13.1, but not Section 13.3. 1282 3. Find all Link Tuples (hereafter matching Link Tuples) where: 1284 * L_neighbor_iface_addr_list contains one or more addresses in 1285 the Sending Address List. 1287 4. If there is more than one matching Link Tuple, then remove them 1288 all; apply Section 13.1, but not Section 13.3. 1290 5. If no matching Link Tuples remain, then create a new matching 1291 Link Tuple with: 1293 * L_neighbor_iface_addr_list = empty; 1295 * L_HEARD_time = EXPIRED; 1297 * L_SYM_time = EXPIRED; 1299 * L_quality = INITIAL_QUALITY; 1301 * L_pending = INITIAL_PENDING; 1303 * L_lost = false; 1304 * L_time = current time + validity time. 1306 6. The matching Link Tuple, existing or new, is then modified as 1307 follows: 1309 1. If the MANET interface finds any address (henceforth 1310 receiving address) in the Receiving Address List in a 1311 Neighbor Address Block in the HELLO message, then the Link 1312 Tuple is modified as follows: 1314 1. If any receiving address in the HELLO message is 1315 associated with a TLV with Type == LINK_STATUS and (Value 1316 == HEARD or Value == SYMMETRIC) then: 1318 - L_SYM_time = current time + validity time. 1320 2. Otherwise if any receiving address in the HELLO message 1321 is associated with a TLV with Type == LINK_STATUS and 1322 Value == LOST then: 1324 1. if L_SYM_time has not expired, then: 1326 1. L_SYM_time = EXPIRED. 1328 2. if L_status == HEARD or SYMMETRIC, then: 1330 * L_time = current time + L_HOLD_TIME. 1332 2. L_neighbor_iface_addr_list = Sending Address List. 1334 3. L_HEARD_time = max(current time + validity time, L_SYM_time). 1336 4. If L_status == PENDING, then: 1338 + L_time = max(L_time, L_HEARD_time). 1340 5. Otherwise if L_status == HEARD or SYMMETRIC, then: 1342 + L_time = max(L_time, L_HEARD_time + L_HOLD_TIME). 1344 12.4. Updating the 2-Hop Set 1346 On receiving a HELLO message a node MUST update its 2-Hop Set for the 1347 MANET interface on which the HELLO message was received: 1349 1. Remove all addresses in the Removed Address List from the 1350 N2_neighbor_iface_addr_list of all 2-Hop Tuples. 1352 2. If the Link Tuple with L_neighbor_iface_addr_list == Sending 1353 Address List has L_STATUS == SYMMETRIC then: 1355 1. For each address (henceforth 2-hop address) in a Neighbor 1356 Address Block of the HELLO message, which is not in the 1357 Neighbor Address List or in any I_local_iface_addr_list: 1359 1. If the 2-hop address has an associated TLV with: 1361 - Type == LINK_STATUS and Value == SYMMETRIC; OR 1363 - Type == OTHER_NEIGHB and Value == SYMMETRIC, 1365 then, if there is no 2-Hop Tuple such that: 1367 - N2_neighbor_iface_addr_list contains one or more 1368 addresses in the Sending Address List; AND 1370 - N2_2hop_iface_addr == 2-hop address. 1372 then create a 2-Hop Neighbor Tuple with: 1374 - N2_2hop_iface_addr = 2-hop address. 1376 This 2-Hop Tuple (existing or new) is then modified as 1377 follows: 1379 - N2_neighbor_iface_addr_list = Sending Address List; 1381 - N2_time = current time + validity time. 1383 2. Otherwise if the 2-hop address has a TLV with: 1385 - Type == LINK_STATUS and (Value == LOST or Value == 1386 HEARD); OR 1388 - Type == OTHER_NEIGHB and Value == LOST; 1390 then remove all 2-Hop Tuples with: 1392 - N2_neighbor_iface_addr_list contains one or more 1393 addresses in the Sending Address List; AND 1395 - N2_2hop_iface_addr == 2-hop address. 1397 13. Other Information Base Changes 1399 The Interface and Node Information Bases MUST be changed when some 1400 events occur. These events may result from HELLO message processing, 1401 or may be otherwise generated (e.g. expiry of timers or link quality 1402 changes). 1404 Events which cause changes in the Information Bases are: 1406 o A Link Tuple's state changes from symmetric, or the Link Tuple is 1407 removed. 1409 o A Link Tuple's state changes to symmetric. 1411 o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed. 1413 o Local interface address changes, as specified in Section 9. 1415 o Link quality changes, as specified in Section 14. 1417 A node MAY report updated information in response to any of these 1418 changes in HELLO message(s), subject to the constraints in 1419 Section 11. 1421 A node which transmits HELLO messages in response to such changes 1422 SHOULD transmit a HELLO message: 1424 o On all MANET interfaces, if the Neighbor Set changes such as to 1425 indicate the change in symmetry of any 1-hop neighbors (including 1426 addition or removal of symmetric 1-hop neighbors). 1428 o Otherwise, on all those MANET interfaces whose Link Set changes 1429 such as to indicate a change in status of any 1-hop neighbors 1430 (including the addition or removal of any 1-hop neighbors, other 1431 than those considered pending). 1433 13.1. Link Tuple Not Symmetric 1435 If for any Link Tuple with L_status == SYMMETRIC: 1437 o L_status changes to any other value; OR 1439 o the Link Tuple is removed; 1441 then: 1443 1. All 2-Hop Tuples for the same MANET interface with: 1445 * N2_neighbor_iface_addr_list contains one or more addresses in 1446 L_neighbor_iface_addr_list; 1448 are removed. 1450 2. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 1451 L_neighbor_iface_addr_list: 1453 1. If there are no remaining Link Tuples for any MANET interface 1454 with: 1456 + L_neighbor_iface_addr_list contained in 1457 N_neighbor_iface_addr_list; AND 1459 + L_status == SYMMETRIC; 1461 then modify the Neighbor Tuple by: 1463 1. N_symmetric = false. 1465 2. For each address (henceforth neighbor address) in 1466 N_neighbor_iface_addr_list, add a Lost Neighbor Tuple 1467 with: 1469 - NL_neighbor_iface_addr = neighbor address; 1471 - NL_time = current time + N_HOLD_TIME. 1473 13.2. Link Tuple Symmetric 1475 If, for any Link Tuple which does not have L_status == SYMMETRIC: 1477 o L_status changes to SYMMETRIC; 1479 (this includes a newly created Link Tuple which is immediately 1480 updated to have L_status == SYMMETRIC) then: 1482 1. For the Neighbor Tuple whose N_neighbor_iface_addr_list includes 1483 L_neighbor_iface_addr_list, set: 1485 * N_symmetric = true. 1487 2. Remove all Lost Neighbor Tuples whose LN_neighbor_iface_addr is 1488 included in that N_neighbor_iface_addr_list. 1490 13.3. Link Tuple Heard Timeout 1492 If, for any Link Tuple: 1494 o L_HEARD_time expires; OR 1496 o the Link Tuple is removed; 1498 then: 1500 1. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 1501 L_neighbor_iface_addr_list, if no Link Tuples for any MANET 1502 interface remain with: 1504 * L_neighbor_iface_addr_list contained in 1505 N_neighbor_iface_addr_list; 1507 * L_HEARD_time is not expired; 1509 then remove the Neighbor Tuple. 1511 14. Link Quality 1513 Link quality is a mechanism whereby a node MAY take considerations 1514 other than message exchange into account for determining when a link 1515 is and is not a candidate for being considered as HEARD or SYMMETRIC. 1517 For deployments where no link quality is used, the considerations in 1518 Section 14.1 apply. For deployments were link quality is used, the 1519 general principles of link quality usage are described in 1520 Section 14.2. Section 14.3 and Section 14.4 detail link quality 1521 functioning. 1523 Link quality is used only locally by a node, and nodes may fully 1524 interoperate whether they are using the same, different or no link 1525 quality methods. 1527 14.1. Deployment Without Link Quality 1529 In order for a node to not employ link quality, the node MUST define: 1531 o INITIAL_PENDING = false; 1533 o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define 1534 INITIAL_QUALITY = 1). 1536 14.2. Basic Principles of Link Quality 1538 To enable link quality usage, the L_quality value of a Link Tuple is 1539 used in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, 1540 to set the flags L_pending and L_lost of that Link Tuple. Based on 1541 these flags, the link status to advertise for that Link Tuple is 1542 determined as described in Section 7.1. 1544 The use of two thresholds implements link hysteresis, whereby a link 1545 which has HYST_REJECT <= L_quality < HYST_ACCEPT may be either 1546 accepted or rejected (depending on which threshold it has most 1547 recently crossed, or if neither the value of INITIAL_QUALITY). With 1548 appropriate values of these parameters, this prevents over-rapid 1549 changes of link status. 1551 The basic principles of link quality usage are as follows: 1553 o A node does not advertise a neighbor interface in any state until 1554 L_quality is acceptable: 1556 * If INITIAL_PENDING == true, then this is such that L_quality >= 1557 HYST_ACCEPT. 1559 * Otherwise this is such that L_quality >= HYST_REJECT. To 1560 ensure this, a node MUST NOT define INITIAL_PENDING == false 1561 and INITIAL_QUALITY < HYST_REJECT. (A node also MUST NOT 1562 define INITIAL_PENDING == true and INITIAL_QUALITY >= 1563 HYST_ACCEPT.) 1565 * A link which is not yet advertised has L_pending == true. 1567 o Once L_quality >= HYST_ACCEPT, the L_pending flag is set false, 1568 indicating that the link can be advertised. 1570 o A link for which L_pending == false is advertised until its 1571 L_quality drops below HYST_REJECT. 1573 o If a link has L_pending == false and L_quality < HYST_REJECT, the 1574 link is LOST and is advertised as such. This link is not 1575 reconsidered as a candidate HEARD or SYMMETRIC link until 1576 L_quality >= HYST_ACCEPT. 1578 o A link which has an acceptable quality may be advertised as HEARD, 1579 SYMMETRIC or LOST according to the exchange of HELLO messages. 1581 14.3. When Link Quality Changes 1583 If L_quality for a link changes, then the following actions MUST be 1584 taken: 1586 1. If L_quality >= HYST_ACCEPT then the corresponding Link Tuple is 1587 modified by: 1589 1. L_pending = false. 1591 2. L_lost = false. 1593 3. If L_status == HEARD or L_status == SYMMETRIC, then: 1595 + L_time = max(L_time, L_HEARD_time + L_HOLD_TIME) 1597 2. If L_status is not equal to PENDING, and L_quality < HYST_REJECT 1598 then the corresponding Link Tuple is modified by: 1600 1. If L_lost == false, then: 1602 + L_lost = true 1604 + L_time = min(L_time, current time + L_HOLD_TIME) 1606 Any appropriate action indicted in Section 13 MUST also be taken. 1608 If L_quality for a link is updated based on HELLO message reception, 1609 or on reception of a packet including a HELLO message, then L_quality 1610 MUST be updated prior to the HELLO message processing described in 1611 Section 12. (If the receipt of the HELLO message, or the packet 1612 containing it, creates the Link Tuple then instead the Link Tuple 1613 MUST be created with the updated, from INITIAL_QUALITY, L_quality 1614 value.) 1616 14.4. Updating Link Quality 1618 A node MAY update link quality based on any information available to 1619 it. Particular cases that MAY be used include: 1621 o Information from the link layer, such as signal to noise ratio. 1623 o Receipt or loss of packets. If packets include a packet sequence 1624 number as defined in [1], then packets on a link SHOULD have 1625 sequential packet sequence numbers, whether or not they include 1626 HELLO messages. Link quality can be updated when a packet is 1627 received based on, for example, whether the last N out of M 1628 packets on the link were received, or a "leaky integrator" 1629 tracking packets. 1631 o Receipt or loss of HELLO messages. If the maximum interval 1632 between HELLO messages is known (such as by inclusion of a message 1633 TLV with Type == INTERVAL_TIME, as defined in [3], in HELLO 1634 messages) then the loss of HELLO messages can be determined 1635 without the need to receive a HELLO message. Note that if this 1636 case is combined with the previous case then care must be taken to 1637 avoid "double counting" a lost HELLO message in a lost packet. 1639 15. Proposed Values for Parameters and Constants 1641 This section lists the parameters and constants used in the 1642 specification of the protocol, and proposed values of each which may 1643 be used when a single value of each is used. 1645 15.1. Message Interval Interface Parameters 1647 o HELLO_INTERVAL = 2 seconds 1649 o HELLO_MIN_INTERVAL = HELLO_INTERVAL/4 1651 o REFRESH_INTERVAL = HELLO_INTERVAL 1653 15.2. Information Validity Time Interface Parameters 1655 o H_HOLD_TIME = 3 x REFRESH_INTERVAL 1657 o L_HOLD_TIME = H_HOLD_TIME 1659 15.3. Information Validity Time Node Parameters 1661 o N_HOLD_TIME = L_HOLD_TIME 1663 15.4. Link Quality Interface Parameters 1665 If link quality is changed, then parameter values will depend on the 1666 link quality process. If link quality is not changed, then: 1668 o HYST_ACCEPT = 1 1670 o HYST_REJECT = 0 1672 o INITIAL_QUALITY = 1 1674 o INITIAL_PENDING = false 1676 15.5. Jitter Interface Parameters 1678 o HP_MAXJITTER = HELLO_INTERVAL/4 1680 o HT_MAXJITTER = HP_MAXJITTER 1682 15.6. Constants 1684 o C = 0.0625 second (1/16 second) 1686 16. IANA Considerations 1688 16.1. Message Types 1690 This specification defines one message type, which must be allocated 1691 from the "Assigned Message Types" repository of [1]. 1693 +--------------+------+--------------------------------------+ 1694 | Name | Type | Description | 1695 +--------------+------+--------------------------------------+ 1696 | HELLO | TBD | Local signaling | 1697 +--------------+------+--------------------------------------+ 1699 16.2. TLV Types 1701 This specification defines three Address Block TLV types, which must 1702 be allocated from the "Assigned Address Block TLV Types" repository 1703 of [1]. 1705 +--------------+------+---------------------------------------------+ 1706 | Name | Type | Description | 1707 +--------------+------+---------------------------------------------+ 1708 | OTHER_IF | TBD | Specifies that the address, in the Local | 1709 | | | Interface Block, is an address associated | 1710 | | | with an interface other than the MANET | 1711 | | | interface on which the message is | 1712 | | | transmitted | 1713 | | | | 1714 | LINK_STATUS | TBD | Specifies the status of the link from the | 1715 | | | indicated address (LOST, SYMMETRIC or | 1716 | | | HEARD) | 1717 | | | | 1718 | OTHER_NEIGHB | TBD | Specifies that the address is (SYMMETRIC) | 1719 | | | or recently was (LOST) of an interface of a | 1720 | | | symmetric 1-hop neighbor of the node | 1721 | | | transmitting the message | 1722 +--------------+------+---------------------------------------------+ 1724 16.3. LINK_STATUS and OTHER_NEIGHB Values 1726 The values which the LINK_STATUS TLV can use are the following: 1728 o LOST = 0 1730 o SYMMETRIC = 1 1732 o HEARD = 2 1733 The values which the OTHER_NEIGHB TLV can use are the following: 1735 o LOST = 0 1737 o SYMMETRIC = 1 1739 17. References 1741 17.1. Normative References 1743 [1] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized 1744 MANET Packet/Message Format", Work In 1745 Progress draft-ietf-manet-packetbb-04.txt, January 2007. 1747 [2] Chakeres, I., "Internet Assigned Numbers Authority (IANA) 1748 Allocations for the Mobile Ad hoc Networks (MANET) Working 1749 Group", Work In Progress draft-ietf-manet-iana-04.txt, May 2007. 1751 [3] Clausen, T. and C. Dearlove, "Representing multi-value time in 1752 MANETs", Work In Progress draft-ietf-manet-timetlv-00.txt, 1753 April 2007. 1755 [4] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 1756 considerations in MANETs", Work In 1757 Progress draft-ietf-manet-jitter-00.txt, April 2007. 1759 [5] Bradner, S., "Key words for use in RFCs to Indicate Requirement 1760 Levels", RFC 2119, BCP 14, March 1997. 1762 17.2. Informative References 1764 [6] Clausen, T. and P. Jacquet, "The Optimized Link State Routing 1765 Protocol", RFC 3626, October 2003. 1767 [7] Macker, J. and S. Corson, "Mobile Ad hoc Networking (MANET): 1768 Routing Protocol Performance Issues and Evaluation 1769 Considerations", RFC 2501, January 1999. 1771 Appendix A. Address Block TLV Combinations 1773 The algorithm for generating HELLO messages in Section 11 specifies 1774 which addresses may be included in the address blocks after the Local 1775 Interface Block, and with which associated TLVs. These TLVs may have 1776 Type == LINK_STATUS or Type == OTHER_NEIGHB, or both. TLVs with Type 1777 == LINK_STATUS may have three possible values (Value == HEARD, Value 1778 == SYMMETRIC or Value == LOST), and TLVs of TYPE == OTHER_NEIGHB may 1779 have two possible values (Value == SYMMETRIC or Value == LOST). When 1780 both TLVs are associated with the same address only certain 1781 combinations of these TLV values are necessary, and are the only 1782 combinations generated by the algorithm in Section 11. These 1783 combinations are indicated in Table 5. 1785 Cells labeled with "Yes" indicate the possible combinations which are 1786 generated by the algorithm in Section 11. Cells labeled with "No" 1787 indicate combinations not generated by the algorithm in Section 11, 1788 but which are correctly parsed and interpreted by the algorithm in 1789 Section 12. 1791 +----------------+----------------+----------------+----------------+ 1792 | | Type == | Type == | Type == | 1793 | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | 1794 | | (absent) | Value == | Value == LOST | 1795 | | | SYMMETRIC | | 1796 +----------------+----------------+----------------+----------------+ 1797 | Type == | No | Yes | Yes | 1798 | LINK_STATUS | | | | 1799 | (absent) | | | | 1800 | | | | | 1801 | Type == | Yes | Yes | Yes | 1802 | LINK_STATUS, | | | | 1803 | Value == HEARD | | | | 1804 | | | | | 1805 | Type == | Yes | No | No | 1806 | LINK_STATUS, | | | | 1807 | Value == | | | | 1808 | SYMMETRIC | | | | 1809 | | | | | 1810 | Type == | Yes | Yes | No | 1811 | LINK_STATUS, | | | | 1812 | Value == LOST | | | | 1813 +----------------+----------------+----------------+----------------+ 1815 Table 5 1817 Appendix B. HELLO Message Example 1819 An example HELLO message, transmitted by an originator node with a 1820 single MANET interface, is as follows. The message uses IPv4 (four 1821 octet) addresses without prefix TLVs. The message is transmitted 1822 with a full message header (message semantics octet is 0) with a hop 1823 limit of 1 and a hop count of 0. The overall message length is 50 1824 octets. 1826 The message contains a message TLV block with content length 8 octets 1827 containing two message TLVs, of types VALIDITY_TIME and 1828 INTERVAL_TIME. Each uses a TLV with semantics value 4, indicating 1829 that no start and stop indexes are included, and each has a value 1830 length of 1 octet. The values included (0x68 and 0x50) are time 1831 codes representing the default values of parameters H_HOLD_TIME and 1832 HELLO_INTERVAL, respectively (6 seconds and 2 seconds) assuming a 1833 default value of constant C (0.0625 second). 1835 The first address block contains 1 local interface address. The 1836 semantics octet value 2 indicates no address tail, and the head 1837 length of 4 octets indicates no address mid sections. This address 1838 block has no TLVs (TLV block content length 0 octets). 1840 The second, and last, address block contains 4 neighbor interface 1841 addresses. The semantics octet value 2 indicates no address tail, 1842 the head length of 3 octets indicates address mid sections of one 1843 octet each. The following TLV block (content length 7 octets) 1844 includes one LINK_STATUS TLV which reports the link status values of 1845 all reported neighbors in a single multivalue TLV: the first two 1846 addresses are HEARD, the third address is SYMMETRIC and the fourth 1847 address is LOST. The TLV semantics value of 20 indicates, in 1848 addition to that this is a multivalue TLV, that no start and stop 1849 indexes are included, since values for all addresses are included. 1850 The TLV value length of 4 octets indicates one octet per value per 1851 address. 1853 0 1 2 3 1854 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 1855 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1856 | HELLO |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0| 1857 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1858 | Originator Address | 1859 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1860 |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number | 1861 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1862 |0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0| VALIDITY_TIME |0 0 0 0 0 1 0 0| 1863 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1864 |0 0 0 0 0 0 0 1|0 1 1 0 1 0 0 0| INTERVAL_TIME |0 0 0 0 0 1 0 0| 1865 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1866 |0 0 0 0 0 0 0 1|0 1 0 1 0 0 0 0|0 0 0 0 0 0 0 1|0 0 0 0 0 0 1 0| 1867 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1868 |0 0 0 0 0 1 0 0| Head | 1869 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1870 | Head (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0| 1871 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1872 |0 0 0 0 0 0 1 0|0 0 0 0 0 0 1 1| Head | 1873 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1874 | Head (cont) | Mid | Mid | Mid | 1875 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1876 | Mid |0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1| LINK_STATUS | 1877 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1878 |0 0 0 1 0 1 0 0|0 0 0 0 0 1 0 0| HEARD | HEARD | 1879 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1880 | SYMMETRIC | LOST | 1881 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1883 Appendix C. Constraints 1885 Any process which updates the Local Information Base or the 1886 Neighborhood Information Base MUST ensure that all constraints 1887 specified in this appendix are maintained. 1889 In each Local Interface Tuple: 1891 o I_local_iface_addr_list MUST NOT be empty. 1893 o I_local_iface_addr_list MUST NOT contain any address which is in 1894 the I_local_iface_addr_list of any other Local Interface Tuple. 1896 In each Link Tuple: 1898 o L_neighbor_iface_addr_list MUST NOT be empty. 1900 o L_neighbor_iface_addr_list MUST NOT contain any address which is 1901 in the I_local_iface_addr_list of any Local Interface Tuple. 1903 o L_neighbor_iface_addr_list MUST NOT contain any address which is 1904 in the L_neighbor_iface_addr_list of any other Link Tuple in the 1905 same Link Set. 1907 o If L_HEARD_time has not expired then there MUST be a Neighbor 1908 Tuple whose N_neighbor_iface_addr_list contains 1909 L_neighbor_iface_addr_list. 1911 o L_HEARD_time MUST NOT be greater than L_time. 1913 o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are 1914 expired). 1916 o L_quality MUST NOT be less than 0 or greater than 1. 1918 o If L_quality >= HYST_ACCEPT then L_pending MUST be false. 1920 o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST. 1922 o L_pending MUST NOT be set to true if it is currently false. 1924 In each Neighbor Tuple: 1926 o N_neighbor_iface_addr_list MUST NOT contain any address which is 1927 in the I_local_iface_addr_list of any Local Interface Tuple. 1929 o N_neighbor_iface_addr_list MUST NOT contain any address which is 1930 in the N_neighbor_iface_addr_list of any other Neighbor Tuple. 1932 o If N_symmetric == true, then there MUST be one or more Link Tuples 1933 with: 1935 * L_neighbor_iface_addr_list contained in 1936 N_neighbor_iface_addr_list; AND 1938 * L_status == SYMMETRIC. 1940 o If N_symmetric == false, then there MUST be one or more Link 1941 Tuples with: 1943 * L_neighbor_iface_addr_list contained in 1944 N_neighbor_iface_addr_list. 1946 All such Link Tuples MUST NOT have L_status == SYMMETRIC. At 1947 least one such Link Tuple MUST have L_HEARD_time not expired. 1949 In each Lost Neighbor Tuple: 1951 o NL_neighbor_iface_addr MUST NOT be in the I_local_iface_addr_list 1952 of any Local Interface Tuple. 1954 o NL_neighbor_iface_addr MUST NOT equal the NL_neighbor_iface_addr 1955 of any other Lost Neighbor Tuple. 1957 o NL_neighbor_iface_addr MUST NOT be in the 1958 N_neighbor_iface_addr_list of any Neighbor Tuple with N_symmetric 1959 == true. 1961 In each 2-Hop Tuple: 1963 o There MUST be a Link Tuple associated with the same MANET 1964 interface with: 1966 * L_neighbor_iface_addr_list == N2_neighbor_iface_addr_list; AND 1968 * L_status == SYMMETRIC. 1970 o N2_2hop_iface_addr MUST NOT be in the I_local_iface_addr_list of 1971 any Local Interface Tuple. 1973 o N2_2hop_iface_addr MUST NOT be the N2_2hop_iface_addr of any other 1974 2-Hop Tuple in the same 2-Hop Set and with the same 1975 N2_neighbor_iface_addr_list. 1977 o N2_2hop_iface_addr MUST NOT be in the N2_neighbor_iface_addr_list 1978 of the same 2-Hop Tuple. 1980 Appendix D. Security Considerations 1982 The objective of this protocol is to allow each node in the network 1983 to acquire information describing its 1-hop and symmetric 2-hop 1984 neighborhoods. This is acquired through message exchange between 1985 neighboring nodes. The information is made available through a 1986 collection of sets, describing the node's 1-hop neighborhood and 1987 symmetric 2-hop neighborhood. 1989 Under normal circumstances, the information recorded in these sets is 1990 correct - i.e. corresponds to the actual network topology, apart from 1991 any changes which have not (yet) been tracked by the HELLO message 1992 exchanges. 1994 If some node for some reason, malice or malfunction, injects invalid 1995 HELLO messages, incorrect information may be recorded in the sets 1996 maintained. The protocol specification does, however, prevent 1997 inconsistent information from being injected in the protocol sets 1998 through the constraints in Appendix C. The exact consequence of 1999 information inexactness depends on the use of these sets, and should 2000 be reflected in the specification of protocols which use information 2001 provided by NHDP. 2003 This appendix, therefore, only outlines the ways in which correctly 2004 formed, but still invalid, HELLO messages may appear. 2006 Appendix D.1. Invalid HELLO messages 2008 A correctly formed, but still invalid, HELLO message may take any of 2009 the following forms: 2011 A node may provide false information about its own identity: 2013 * The Local Interface Block of the HELLO message may contain 2014 addresses which do not correspond to addresses of interfaces of 2015 the node transmitting the HELLO message. 2017 * The Local Interface Block of the HELLO message may omit 2018 addresses of interfaces of the local node transmitting the 2019 HELLO message. 2021 * The Local Interface Block may contain additional OTHER_IF TLVs, 2022 indicating incorrectly that an address is associated with an 2023 interface other than that over which the HELLO message is 2024 transmitted. 2026 * The Local Interface Block may omit OTHER_IF TLVs, thereby 2027 indicating incorrect addresses associated with the MANET 2028 interface over which the HELLO message is transmitted. 2030 A node may provide false information about the identity of other 2031 nodes: 2033 * A present or absent address in a Neighbor Block, does not in 2034 and by itself cause a problem. It is the presence, absence, or 2035 incorrectness of associated LINK_STATUS and OTHER_NEIGHB TLVs 2036 that causes problems. 2038 * A present LINK_STATUS TLV may, incorrectly, identify an address 2039 as being of a MANET interface which is or was heard on the 2040 MANET interface over which the HELLO message is transmitted. 2042 * A consistently absent LINK_STATUS TLV may, incorrectly, fail to 2043 identify an address as being of a MANET interface which is or 2044 was heard on the MANET interface over which the HELLO message 2045 is transmitted. 2047 * A present OTHER_NEIGHB TLV may, incorrectly, identify an 2048 address as being of a node which is or was in the sending 2049 node's symmetric 1-hop neighborhood; 2051 * A consistently absent OTHER_NEIGHB TLV may, incorrectly, fail 2052 to identify an address as being of a node which is or was in 2053 the sending node's symmetric 1-hop neighborhood; 2055 * The value of a LINK_STATUS TLV may incorrectly indicate the 2056 status (LOST, SYMMETRIC or HEARD) of the link from a 1-hop 2057 neighbor. 2059 * The value of an OTHER_NEIGHB TLV may incorrectly indicate the 2060 status (LOST or SYMMETRIC) of a symmetric 1-hop neighbor. 2062 Appendix E. Flow and Congestion Control 2064 This protocol specifies one message type, the HELLO message. The 2065 maximum size of a HELLO message is proportional to the size of the 2066 originating node's 1-hop neighborhood. HELLO messages MUST NOT be 2067 forwarded. 2069 A node MUST report its 1-hop neighborhood in HELLO messages on each 2070 of its MANET interfaces at least each REFRESH_INTERVAL. This puts a 2071 lower bound on the control traffic generated by each node in the 2072 network employing this protocol. 2074 A node MUST ensure that two successive HELLO messages sent on the 2075 same MANET interface are separated by at least HELLO_MIN_INTERVAL. 2076 (If using jitter then this may be reduced to a mean minimum value of 2077 HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound 2078 on the control traffic generated by each node in the network 2079 employing this protocol. 2081 Appendix F. Contributors 2083 This specification is the result of the joint efforts of the 2084 following contributors -- listed alphabetically. 2086 o Brian Adamson, NRL, USA, 2088 o Cedric Adjih, INRIA, France, 2090 o Emmanuel Baccelli, Hitachi Labs Europe, France, 2091 2093 o Thomas Heide Clausen, PCRI, France, 2095 o Justin Dean, NRL, USA, 2097 o Christopher Dearlove, BAE Systems, UK, 2098 2100 o Philippe Jacquet, INRIA, France, 2102 Appendix G. Acknowledgements 2104 The authors would like to acknowledge the team behind OLSRv1, 2105 specified in RFC3626 for their contributions. 2107 The authors would like to gratefully acknowledge the following people 2108 for intense technical discussions, early reviews and comments on the 2109 specification and its components: Joe Macker (NRL), Alan Cullen (BAE 2110 Systems), and the entire IETF MANET working group. 2112 Authors' Addresses 2114 Thomas Heide Clausen 2115 LIX, Ecole Polytechnique, France 2117 Phone: +33 6 6058 9349 2118 Email: T.Clausen@computer.org 2119 URI: http://www.ThomasClausen.org/ 2121 Christopher M. Dearlove 2122 BAE Systems Advanced Technology Centre 2124 Phone: +44 1245 242194 2125 Email: chris.dearlove@baesystems.com 2126 URI: http://www.baesystems.com/ 2128 Justin W. Dean 2129 Naval Research Laboratory 2131 Phone: +1 202 767 3397 2132 Email: jdean@itd.nrl.navy.mil 2133 URI: http://pf.itd.nrl.navy.mil/ 2135 The OLSRv2 Design Team 2136 MANET Working Group 2138 Full Copyright Statement 2140 Copyright (C) The IETF Trust (2007). 2142 This document is subject to the rights, licenses and restrictions 2143 contained in BCP 78, and except as set forth therein, the authors 2144 retain all their rights. 2146 This document and the information contained herein are provided on an 2147 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 2148 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 2149 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 2150 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 2151 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2152 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2154 Intellectual Property 2156 The IETF takes no position regarding the validity or scope of any 2157 Intellectual Property Rights or other rights that might be claimed to 2158 pertain to the implementation or use of the technology described in 2159 this document or the extent to which any license under such rights 2160 might or might not be available; nor does it represent that it has 2161 made any independent effort to identify any such rights. Information 2162 on the procedures with respect to rights in RFC documents can be 2163 found in BCP 78 and BCP 79. 2165 Copies of IPR disclosures made to the IETF Secretariat and any 2166 assurances of licenses to be made available, or the result of an 2167 attempt made to obtain a general license or permission for the use of 2168 such proprietary rights by implementers or users of this 2169 specification can be obtained from the IETF on-line IPR repository at 2170 http://www.ietf.org/ipr. 2172 The IETF invites any interested party to bring to its attention any 2173 copyrights, patents or patent applications, or other proprietary 2174 rights that may cover technology that may be required to implement 2175 this standard. Please address the information to the IETF at 2176 ietf-ipr@ietf.org. 2178 Acknowledgment 2180 Funding for the RFC Editor function is provided by the IETF 2181 Administrative Support Activity (IASA).