idnits 2.17.1 draft-ietf-manet-nhdp-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) 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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 1041 has weird spacing: '...dr_list is an...' == Line 1044 has weird spacing: '...I_manet is a ...' == Line 1063 has weird spacing: '...ce_addr is a ...' == Line 1066 has weird spacing: '...IR_time speci...' == Line 1100 has weird spacing: '...dr_list is an...' == (13 more instances...) -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 9, 2009) is 5520 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) ** Downref: Normative reference to an Informational RFC: RFC 5148 Summary: 2 errors (**), 0 flaws (~~), 7 warnings (==), 2 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 4 Intended status: Standards Track C. Dearlove 5 Expires: September 10, 2009 BAE Systems ATC 6 J. Dean 7 Naval Research Laboratory 8 The OLSRv2 Design Team 9 MANET Working Group 10 March 9, 2009 12 MANET Neighborhood Discovery Protocol (NHDP) 13 draft-ietf-manet-nhdp-08 15 Status of This Memo 17 This Internet-Draft is submitted to IETF in full conformance with the 18 provisions of BCP 78 and BCP 79. This document may contain material 19 from IETF Documents or IETF Contributions published or made publicly 20 available before November 10, 2008. The person(s) controlling the 21 copyright in some of this material may not have granted the IETF 22 Trust the right to allow modifications of such material outside the 23 IETF Standards Process. Without obtaining an adequate license from 24 the person(s) controlling the copyright in such materials, this 25 document may not be modified outside the IETF Standards Process, and 26 derivative works of it may not be created outside the IETF Standards 27 Process, except to format it for publication as an RFC or to 28 translate it into languages other than English. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF), its areas, and its working groups. Note that 32 other groups may also distribute working documents as Internet- 33 Drafts. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 The list of current Internet-Drafts can be accessed at 41 http://www.ietf.org/ietf/1id-abstracts.txt. 43 The list of Internet-Draft Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html. 46 This Internet-Draft will expire on September 10, 2009. 48 Copyright Notice 49 Copyright (c) 2009 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents in effect on the date of 54 publication of this document (http://trustee.ietf.org/license-info). 55 Please review these documents carefully, as they describe your rights 56 and restrictions with respect to this document. 58 Abstract 60 This document describes a 1-hop and symmetric 2-hop neighborhood 61 discovery protocol (NHDP) for mobile ad hoc networks (MANETs). 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 66 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 68 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 69 3.1. Usage in Other Protocols . . . . . . . . . . . . . . . . . 10 70 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 10 71 4.1. Routers and Interfaces . . . . . . . . . . . . . . . . . . 11 72 4.2. Information Base Overview . . . . . . . . . . . . . . . . 12 73 4.2.1. Local Information Base . . . . . . . . . . . . . . . . 12 74 4.2.2. Interface Information Bases . . . . . . . . . . . . . 13 75 4.2.3. Neighbor Information Base . . . . . . . . . . . . . . 14 76 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 14 77 4.3.1. HELLO Message Generation . . . . . . . . . . . . . . . 15 78 4.3.2. HELLO Message Content . . . . . . . . . . . . . . . . 15 79 4.3.3. HELLO Message Processing . . . . . . . . . . . . . . . 16 80 4.4. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 17 81 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 17 82 5.1. Interface Parameters . . . . . . . . . . . . . . . . . . . 18 83 5.1.1. Message Intervals . . . . . . . . . . . . . . . . . . 18 84 5.1.2. Information Validity Times . . . . . . . . . . . . . . 19 85 5.1.3. Link Quality . . . . . . . . . . . . . . . . . . . . . 20 86 5.1.4. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 21 87 5.2. Router Parameters . . . . . . . . . . . . . . . . . . . . 21 88 5.2.1. Information Validity Time . . . . . . . . . . . . . . 21 89 5.3. Parameter Change Constraints . . . . . . . . . . . . . . . 21 90 5.4. Constants . . . . . . . . . . . . . . . . . . . . . . . . 23 91 6. Local Information Base . . . . . . . . . . . . . . . . . . . . 23 92 6.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 23 93 6.2. Removed Interface Address Set . . . . . . . . . . . . . . 23 94 7. Interface Information Base . . . . . . . . . . . . . . . . . . 24 95 7.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 24 96 7.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 25 98 8. Neighbor Information Base . . . . . . . . . . . . . . . . . . 26 99 8.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . 26 100 8.2. Lost Neighbor Set . . . . . . . . . . . . . . . . . . . . 26 101 9. Local Information Base Changes . . . . . . . . . . . . . . . . 27 102 9.1. Adding an Interface . . . . . . . . . . . . . . . . . . . 27 103 9.2. Removing an Interface . . . . . . . . . . . . . . . . . . 27 104 9.3. Adding an Address to an Interface . . . . . . . . . . . . 28 105 9.4. Removing an Address from an Interface . . . . . . . . . . 29 106 10. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 29 107 10.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 30 108 10.1.1. Address Blocks . . . . . . . . . . . . . . . . . . . . 31 109 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 32 110 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 32 111 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 34 112 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 34 113 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 35 114 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 35 115 12.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 36 116 12.3. Updating the Neighbor Set . . . . . . . . . . . . . . . . 37 117 12.4. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 38 118 12.5. Updating the Link Set . . . . . . . . . . . . . . . . . . 39 119 12.6. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 40 120 13. Other Information Base Changes . . . . . . . . . . . . . . . . 41 121 13.1. Link Tuple Symmetric . . . . . . . . . . . . . . . . . . . 42 122 13.2. Link Tuple Not Symmetric . . . . . . . . . . . . . . . . . 43 123 13.3. Link Tuple Heard Timeout . . . . . . . . . . . . . . . . . 43 124 14. Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . 44 125 14.1. Deployment Without Link Quality . . . . . . . . . . . . . 44 126 14.2. Basic Principles of Link Quality . . . . . . . . . . . . . 45 127 14.3. When Link Quality Changes . . . . . . . . . . . . . . . . 46 128 14.4. Updating Link Quality . . . . . . . . . . . . . . . . . . 46 129 15. Proposed Values for Parameters and Constants . . . . . . . . . 47 130 15.1. Message Interval Interface Parameters . . . . . . . . . . 47 131 15.2. Information Validity Time Interface Parameters . . . . . . 47 132 15.3. Information Validity Time Router Parameters . . . . . . . 47 133 15.4. Link Quality Interface Parameters . . . . . . . . . . . . 47 134 15.5. Jitter Interface Parameters . . . . . . . . . . . . . . . 48 135 15.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 48 136 16. Security Considerations . . . . . . . . . . . . . . . . . . . 48 137 16.1. Invalid HELLO messages . . . . . . . . . . . . . . . . . . 48 138 16.2. Authentication, Integrity and Confidentiality 139 Suggestions . . . . . . . . . . . . . . . . . . . . . . . 50 140 17. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 50 141 17.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 50 142 17.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 50 143 17.3. Message-Type-specific TLV Type Registries . . . . . . . . 51 144 17.4. Address Block TLV Types . . . . . . . . . . . . . . . . . 51 145 17.5. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 52 147 18. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 53 148 19. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 53 149 20. References . . . . . . . . . . . . . . . . . . . . . . . . . . 54 150 20.1. Normative References . . . . . . . . . . . . . . . . . . . 54 151 20.2. Informative References . . . . . . . . . . . . . . . . . . 54 152 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 54 153 Appendix B. Constraints . . . . . . . . . . . . . . . . . . . . . 55 154 Appendix C. HELLO Message Example . . . . . . . . . . . . . . . . 58 155 Appendix D. Flow and Congestion Control . . . . . . . . . . . . . 60 157 1. Introduction 159 This document describes a neighborhood discovery protocol (NHDP) for 160 a mobile ad hoc network (MANET) [RFC2501]. This protocol uses an 161 exchange of HELLO messages in order that each router can determine 162 the presence of, and connectivity to, its 1-hop and symmetric 2-hop 163 neighbors. Messages are defined as instances of the specification 164 [RFC5444]. 166 1-hop and symmetric 2-hop neighborhood information is recorded in the 167 form of Information Bases. These may be used by other protocols, 168 such as MANET routing protocols, which require information regarding 169 the local network connectivity. This protocol is designed to 170 maintain the information in these Information Bases even in the 171 presence of a dynamic network topology and wireless ad hoc network 172 interface characteristics. 174 This protocol makes no assumptions about the underlying link layer, 175 other than support of link local broadcast or multicast. Link layer 176 information may be used if available and applicable. 178 This protocol is based on the neighborhood discovery process 179 contained in the Optimized Link State Routing Protocol (OLSR) 180 [RFC3626]. 182 1.1. Motivation 184 MANETs differ from more traditional wired and infrastructure based 185 wireless networks, due to their envisioned applicability also over 186 more challenging network interfaces (e.g. wireless, lossy, broadcast 187 interfaces with moderate and shared bandwidth, hidden and exposed 188 terminals and interference from other network interfaces and the 189 environment) and in more challenging topological conditions (e.g. 190 rapid and unpredictable mobility, dynamic and non-predetermined 191 network membership). An approach, often taken by MANET routing 192 protocols, is to collect local topological information up to 2 hops, 193 in order to, for example, optimize their flooding performance within 194 the MANET. 196 Due to the properties of wireless transmissions, communication 197 between two network interfaces on neighboring routers may not be 198 bidirectional; even if router A is able to receive a packets from 199 router B, the converse is not guaranteed to be true. Furthermore, 200 because of the localized nature of wireless broadcast communication, 201 neighboring routers within the same communications channel may have 202 different sets of neighbors. If router A is able to exchange packets 203 with router B and router B is able to exchange packets with router C 204 on the same interface, this does not guarantee that router A and 205 router C can exchange packets directly. 207 Routers in a MANET may have multiple heterogeneous interfaces 208 participating in the same MANET routing protocol, each of which with 209 the characteristics described above. Between the same pair of 210 routers, more than one distinct communications channel (link) may 211 therefore exist, each with different properties. 213 For MANET routing protocols to correctly identify candidate links for 214 inclusion in a routing path, the existence and, in many cases, 215 bidirectionality of such distinct links between a router and its 216 neighbors must be established and monitored. 218 The set of neighbor routers of a given MANET router may be 219 continuously changing, often due to router mobility or a changing 220 physical environment in which the MANET is located. There are 221 typically no signals from lower layers which would enable an IP 222 routing protocol to detect and, as appropriate, react to such 223 changes. Such changes are can often take place on a short timescale, 224 such as of the order of seconds, requiring MANET routing protocols to 225 act rapidly to ensure suitable convergence properties. 227 MANET routing protocols, for example [RFC3626] and [RFC5449], often 228 employ relay set reductions in order to conserve network capacity 229 when maintaining network-wide topological information, with 230 calculation of these reduced relay sets employing up to two hop 231 information. 233 The neighborhood discovery protocol specified in this document 234 provides continued tracking of neighborhood changes, continued 235 bidirectionality tracking of links between neighbors, and local 236 topological information up to two hops. Combined, this allows a 237 MANET routing protocol access to information describing link 238 establishment/disappearance, and provides the necessary topological 239 information for reduced relay set selection and other purposes. 241 2. Terminology 243 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 244 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 245 "OPTIONAL" in this document are to be interpreted as described in 246 [RFC2119]. 248 All terms introduced in [RFC5444], including "packet", "message", 249 "Address Block", "TLV Block" and "TLV", are to be interpreted as 250 described there. 252 Additionally, this document uses the following terminology: 254 Router - A MANET router which implements this neighborhood discovery 255 protocol. 257 Interface - A network device, configured and assigned one or more IP 258 addresses. 260 Address - An IPv4 or IPv6 address, as recorded in the Information 261 Bases specified by this protocol, and included in messages 262 generated by this protocol, may be either an address or an address 263 prefix. The exception to this is addresses described as 264 originator addresses; these must be simple addresses without a 265 prefix length. Non-originator addresses can be represented as a 266 single address object in a message, as defined by [RFC5444]. An 267 address so represented is considered to have a prefix length equal 268 to its length (in bits) when considered as an address object, and 269 a similar convention is used in the Information Bases specified by 270 this protocol. Two addresses (address objects) are considered 271 equal only if their prefix lengths are also equal. 273 MANET interface - An interface participating in a MANET and using 274 this neighborhood discovery protocol. A router may have several 275 MANET interfaces. 277 Heard - A MANET interface of router X is considered heard on a MANET 278 interface of a router Y if the latter can receive traffic from the 279 former. 281 Link - A pair of MANET interfaces from two different routers, where 282 at least one interface is heard by the other. 284 Symmetric link - A link where both MANET interfaces are heard by the 285 other. 287 1-hop neighbor - A router X is a 1-hop neighbor of a router Y if a 288 MANET interface of router X is heard by a MANET interface of 289 router Y. 291 Symmetric 1-hop neighbor - A router X is a symmetric 1-hop neighbor 292 of a router Y if a symmetric link exists between a MANET interface 293 on router X and a MANET interface on router Y. 295 Symmetric 2-hop neighbor - A router X is a symmetric 2-hop neighbor 296 of a router Y if router X is a symmetric 1-hop neighbor of a 297 symmetric 1-hop neighbor of router Y, but is not router Y itself. 299 1-hop neighborhood - The 1-hop neighborhood of a router X is the set 300 of the 1-hop neighbors of router X. 302 Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a 303 router X is the set of the symmetric 1-hop neighbors of router X. 305 Symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of a 306 router X is the set of the symmetric 2-hop neighbors of router X. 307 (This may include routers in the 1-hop neighborhood, or even in 308 the symmetric 1-hop neighborhood, of router X.) 310 Constant - A constant is a numerical value which MUST be the same 311 for all MANET interfaces of all routers in the MANET, at all 312 times. 314 Interface parameter - An interface parameter is a boolean or 315 numerical value, specified separately for each MANET interface of 316 each router. A router MAY change interface parameter values at 317 any time, subject to some constraints. 319 Router parameter - A router parameter is a boolean or numerical 320 value, specified for each router, and not specific to an 321 interface. A router MAY change router parameter values at any 322 time, subject to some constraints. 324 Furthermore, this document uses the following notational conventions: 326 X contains y, or y is contained in X, is an unordered list 327 membership operator, returning true if the unordered list X 328 includes the element y, and returning false otherwise. 330 X contains Y, or Y is contained in X, is an unordered list inclusion 331 operator, returning true if the unordered list X contains all 332 elements y which are contained in Y, and returning false 333 otherwise. 335 a := b is an assignment operator, whereby the left side (a) is 336 assigned the value of the right side (b). a and b may be values, 337 addresses, or unordered lists (they must be of the same type). 339 c = d is a comparison operator, returning true if the value of the 340 left side (c) is equal to the value of the right side (d). c and d 341 may be values, addresses, or unordered lists (they must be of the 342 same type). If c and d are unordered lists, then they are 343 considered to be equal if they contain the same set of elements, 344 regardless of the order in which they are recorded in either list 345 (in which case c is contains d, and d contains c). 347 e != f is a comparison operator, returning true where (e = f) would 348 have returned false, and returning false where (e = f) would have 349 returned true. 351 3. Applicability Statement 353 This protocol: 355 o Provides each router with local topology information up to two 356 hops away. 358 o Makes this local topology information a available to MANET routing 359 protocols in Information Bases, which are defined in this 360 specification. 362 o May interact with other protocols, such as MANET routing 363 protocols, see Section 3.1. 365 o Is applicable to networks, especially wireless networks, in which 366 unknown neighbors (i.e. other routers with which direct link layer 367 communication can be established) can be reached by local 368 broadcast or multicast packets. 370 o Is designed to work in networks with a dynamic topology, and in 371 which messages may be lost, such as due to collisions in wireless 372 networks. 374 o Supports routers that each have one or more participating MANET 375 interfaces. The set of a router's interfaces may change over 376 time. Each interface may have one or more interface addresses, 377 and these may also be dynamically changing. 379 o Can use the link local multicast address "LL-MANET-Routers", and 380 either the "manet" UDP port or the "manet" IP protocol number, all 381 as specified in [manet-iana]. 383 o Uses the packet and message formats specified in [RFC5444]. Such 384 packets may contain messages specified by this protocol as well as 385 other protocols. 387 o Specifies signaling using HELLO messages. The necessary contents 388 of these messages are defined in this specification, and may be 389 extended using the TLV mechanisms described in [RFC5444]. 391 o Can use relevant link layer information if it is available. 393 o Is designed to work in a completely distributed manner, and does 394 not depend on any central entity. 396 3.1. Usage in Other Protocols 398 Other protocols which use neighborhood discovery MAY need to interact 399 with this protocol. This protocol is designed to permit such 400 interactions, in particular: 402 o Through accessing, and possibly extending, the information in the 403 Local Information Base (Section 6), the Interface Information Base 404 (Section 7) and the Neighbor Information Base (Section 8). These 405 Information Bases record the interface configuration of the 406 router, as well as the local connectivity, up to two hops away. 407 All updates to the elements specified in this document are subject 408 to the constraints specified in Appendix B. 410 o Through accessing an outgoing HELLO message prior to it being 411 transmitted over any MANET interface, and to add information (e.g. 412 TLVs) as specified in [RFC5444]. This may, for example, be to 413 allow a security protocol, as suggested in Section 16, to add a 414 TLV containing a cryptographic signature to the message, or be to 415 allow inserting relay selection information into a HELLO message 416 by way of adding a TLV to an outgoing HELLO message prior to it 417 being transmitted. 419 o Through accessing an incoming HELLO message, and potentially 420 discard it prior to processing by this protocol. This may, for 421 example, allow a security protocol, as suggested in Section 16, to 422 perform verification of HELLO message signatures and prevent 423 processing of unverifiable HELLO messages by this protocol. 425 o Through accessing an incoming HELLO message after it has been 426 completely processed by this protocol. This may, in particular, 427 allow a protocol which has added information, such as relay 428 selection information by way of inclusion of appropriate TLVs, 429 access to such information after appropriate updates has been 430 recorded in the Information Bases in this protocol. 432 o Through requesting that a HELLO message be generated at a specific 433 time. In that case, HELLO message generation MUST still respect 434 the constraints in Appendix B. 436 4. Protocol Overview and Functioning 438 The objective of this protocol is, for each router: 440 o To identify other routers which can be heard, and those with which 441 bidirectional links can be established (symmetric 1-hop 442 neighbors). 444 o To agree on the status of such links with the corresponding 445 symmetric 1-hop neighbor. 447 o To find the interface addresses of the router's symmetric 2-hop 448 neighbors. 450 o To record this information in Information Bases that can be used 451 by other protocols, of which this neighborhood discovery protocol 452 may be a part. 454 These objectives are achieved using local (one hop) signaling that: 456 o Advertises the presence of a router and its interfaces. 458 o Discovers links from neighboring routers. 460 o Performs bidirectionality checks on the discovered links. 462 o Advertises discovered links, and whether each is symmetric, to its 463 1-hop neighbors, and hence discovers symmetric 2-hop neighbors. 465 This specification defines, in turn: 467 o Parameters and constants used by the protocol. Parameters used by 468 this protocol may be, where appropriate, specific to a specific 469 MANET interface, or to a MANET router. This protocol allows all 470 parameters to be changed dynamically, and to be set independently 471 for each MANET router or MANET interface, as appropriate. 473 o The Information Bases describing local interfaces, discovered 474 links and their status, current and former 1-hop neighbors, and 475 symmetric 2-hop neighbors. 477 o The format of the HELLO message that is used for local signaling. 479 o The generation of HELLO messages from some of the information in 480 the Information Bases. 482 o The updating of the Information Bases according to received HELLO 483 messages and other events. 485 4.1. Routers and Interfaces 487 In order for a router to participate in a MANET, it MUST have at 488 least one, and possibly more, MANET interfaces. Each MANET 489 interface: 491 o Is characterized by a set of interface parameters, defining the 492 behavior of this MANET interface. Each MANET interface MAY be 493 individually parameterized. 495 o Has an Interface Information Base, recording information regarding 496 links to this MANET interface and symmetric 2-hop neighbors which 497 can be reached through such links. 499 o Generates and processes HELLO messages, according to the interface 500 parameters for that MANET interface. 502 In addition to a set of MANET interfaces as described above, each 503 router has: 505 o A Local Information Base, containing the addresses of the 506 interfaces (MANET and non-MANET) of this router. The contents of 507 this Information Base are not changed by signaling. 509 o A Neighbor Information Base, recording information regarding 510 current and recently lost 1-hop neighbors of this router. 512 A router may have both MANET interfaces and non-MANET interfaces. 513 Interfaces of both of these types are recorded in a router's Local 514 Information Base, which is used, but not updated, by the signaling of 515 this protocol. 517 4.2. Information Base Overview 519 Each router maintains the Information Bases described in the 520 following sections. These are used for describing the protocol in 521 this document. An implementation of this protocol MAY maintain this 522 information in the indicated form, or in any other organization which 523 offers access to this information. In particular note that it is not 524 necessary to remove Tuples from Sets at the exact time indicated, 525 only to behave as if the Tuples were removed at that time. 527 4.2.1. Local Information Base 529 Each router maintains a Local Information Base, which contains: 531 o The Local Interface Set, which consists of Local Interface Tuples, 532 each of which records the addresses of an interface (MANET or non- 533 MANET) of the router. 535 o The Removed Interface Address Set, which consists of Removed 536 Interface Address Tuples, each of which records a recently used 537 address of an interface (MANET or non-MANET) of the router. 539 The Local Interface Set is used for generating HELLO messages, 540 specifically for determining which interface addresses are to be 541 included and identified through inclusion of an appropriate TLV as 542 being a "local interface" of the router at which the HELLO message is 543 generated. The Removed Interface Address Set is used to allow a 544 router to detect if a neighbor is advertising a formerly used 545 address, and to exclude this from inclusion in the Interface 546 Information Bases described below. 548 The Local Information Base is used for generating signaling, but is 549 not itself updated by signaling specified in this document. Updates 550 to the Local Information Base are due to changes of the router 551 configuration, and may be allowed to trigger signaling. 553 4.2.2. Interface Information Bases 555 Each router maintains, for each of its MANET interfaces, an Interface 556 Information Base, which contains: 558 o A Link Set, which records information about current and recently 559 lost links between this interface and MANET interfaces of 1-hop 560 neighbors. The Link Set consists of Link Tuples, each of which 561 contains information about a single link. Recently lost links are 562 recorded so that they can be advertised in HELLO messages, 563 accelerating their removal from relevant 1-hop neighbors' Link 564 Sets. Link quality information (see Section 14), if used and 565 available, is recorded in Link Tuples and may indicate that links 566 are treated as lost. 568 o A 2-Hop Set, which records the existence of bidirectional links 569 between symmetric 1-hop neighbors of this MANET interface and 570 other routers (symmetric 2-hop neighbors). The 2-Hop Set consists 571 of 2-Hop Tuples, each of which records an interface address of a 572 symmetric 2-hop neighbor, and all interface addresses of the 573 corresponding symmetric 1-hop neighbor. The 2-Hop Set is updated 574 by the signaling of this protocol, but is not itself reported in 575 that signaling. 577 The Link Set for a MANET interface is used for generating HELLO 578 messages. Specifically, the Link Set information is included to both 579 allow other routers to detect bidirectionality (if router A 580 advertises router B as heard in a HELLO message and router B receives 581 that HELLO message, then router B knows that bidirectional 582 communication is possible between routers A and B), and to populate 583 the 2-Hop Set (if router C receives a HELLO message from router B 584 advertising a bidirectional link to address A, then router C knows 585 that address A is reachable in two hops via router B). 587 The Link Set for a MANET interface is itself updated upon receipt of 588 a HELLO message, including to record link bidirectionality as 589 indicated above. 591 The 2-Hop Set for a MANET interface is updated as indicated above, 592 and is not itself used in generating HELLO messages. 594 4.2.3. Neighbor Information Base 596 Each router maintains a Neighbor Information Base, which contains: 598 o The Neighbor Set, which records 1-hop neighbors, each of which 599 must be currently heard, although this may be over a link with 600 insufficient link quality. The Neighbor Set consists of Neighbor 601 Tuples, each of which records all interface addresses of a single 602 1-hop neighbor. Neighbor Tuples are maintained as long as there 603 are corresponding current Link Tuples. 605 o The Lost Neighbor Set, which records recently lost symmetric 1-hop 606 neighbors. The Lost Neighbor Set consists of Lost Neighbor 607 Tuples, each of which records an interface address of such a 608 neighbor. These are recorded so that they can be advertised in 609 HELLO messages, accelerating their removal from other routers' 610 2-Hop Sets. 612 The Neighbor Set is used for recording which interface addresses of 613 neighbor routers are associated to the same router, and for including 614 this when generating HELLO messages such that 2-Hop sets in other 615 neighboring routers may record this information. The Neighbor Set 616 can itself be updated on receipt of a HELLO message. 618 The Lost Neighbor Set is used for generating HELLO messages. 619 Specifically, the Lost Neighbor Set is used for determining which 620 addresses are to be included in a HELLO and identified through 621 inclusion of an appropriate TLV as being "lost", i.e. formerly, but 622 no longer, recorded as a symmetric neighbor. The Lost Neighbor Set 623 can itself be updated on receipt of a HELLO message. 625 4.3. Signaling Overview 627 This protocol contains a signaling mechanism for maintaining the 628 Interface Information Bases and the Neighbor Information Base. If 629 information from the link layer, or any other source, is available 630 and appropriate, it may also be used to update these Information 631 Bases. Such updates are subject to the constraints specified in 632 Appendix B. 634 Signaling consists of a single type of message, known as a HELLO 635 message. Each router generates HELLO messages on each of its MANET 636 interfaces. HELLO messages are generated independently on each MANET 637 interface of a MANET router; the content of a given HELLO message 638 depends on the interface for which it has been generated. 640 Each HELLO message identifies the MANET interface for which it is 641 generated and over which it is transmitted. This allows its 642 recipients to identify from which MANET interface this HELLO message 643 has been received. Each HELLO message also reports the other 644 interfaces (MANET and non-MANET) of the router, which allows 645 recipients to associate a set of interface addresses with a single 646 neighbor. Finally, each HELLO message also includes information from 647 the Link Set of the Interface Information Base of the MANET 648 interface, and from the Neighbor Information Base. This serves to 649 allow detection of bidirectional communication between two MANET 650 routers and over a pair of MANET interfaces, as well as to determine 651 symmetric 2-hop neighborhood information. 653 4.3.1. HELLO Message Generation 655 HELLO messages are generated by a router for each of its MANET 656 interfaces, and MAY be sent: 658 o Proactively, at a regular interval, known as HELLO_INTERVAL. 659 HELLO_INTERVAL may be fixed, or may be dynamic. For example 660 HELLO_INTERVAL may be backed off due to congestion or network 661 stability. 663 o As a response to a change in the router itself, or its 1-hop 664 neighborhood, for example on first becoming active or in response 665 to a new, broken, or changed status link. 667 o In a combination of these proactive and responsive mechanisms. 669 Jittering of HELLO message generation and transmission, as described 670 in Section 11.2, SHOULD be used if appropriate. 672 HELLO messages MAY be scheduled independently for each MANET 673 interface, or, interface parameters permitting, using the same 674 schedule for all MANET interfaces of a router. 676 4.3.2. HELLO Message Content 678 Each HELLO message sent on a MANET interface need not contain all of 679 the information appropriate to that MANET interface, however: 681 o A HELLO message MUST contain all of the addresses in the Local 682 Interface Set of the router to which the MANET interface belongs. 684 o For each MANET interface, within every time interval of length 685 equal to the corresponding parameter REFRESH_INTERVAL, the HELLO 686 messages sent MUST collectively include: 688 * All of the relevant information in the Link Set of the 689 Interface Information Base of that MANET interface. 691 * All of the relevant information in the Neighbor Information 692 Base of that router. 694 This applies to otherwise purely responsive routers as well as to 695 proactive routers. In either case it means that all information 696 appropriate to that MANET interface will have always been 697 transmitted, in one or more HELLO messages, since the time 698 REFRESH_INTERVAL ago. Note that this rule applies at all times, 699 not just to times at which HELLO messages are sent. In 700 considering whether to include information in a HELLO message, the 701 sender MUST consider all times up to when it may send its next 702 HELLO message on that MANET interface. 704 o A HELLO message MUST include a VALIDITY_TIME Message TLV, as 705 specified in [timetlv], that indicates the length of time for 706 which the message content is to be considered valid, and is 707 therefore to be included in the receiving router's Interface 708 Information Base. 710 o A periodically generated HELLO message SHOULD include an 711 INTERVAL_TIME Message TLV, as specified in [timetlv], that 712 indicates the current value of HELLO_INTERVAL for that MANET 713 interface, i.e. the period within which a further HELLO message is 714 guaranteed to be sent on that MANET interface. 716 o Additional information may be added by a protocol using this 717 protocol using the TLV mechanisms described in [RFC5444]. For 718 example, if multipoint relays (MPRs) are to be calculated 719 similarly to as in [RFC3626] and signaled to neighbors, then this 720 information may be added to HELLO messages using an Address Block 721 TLV. 723 4.3.3. HELLO Message Processing 725 All HELLO messages received by a router are used to update: 727 o The Interface Information Base for the MANET interface on which 728 that HELLO message is received. 730 o The Neighbor Information Base. 732 Specifically: 734 o The router ensures that there is a single Neighbor Tuple 735 corresponding to the originator of that HELLO message. 737 o If a Link Tuple corresponding to the link on which that HELLO 738 message was received exists, then the duration for which that Link 739 Tuple is kept is extended, otherwise such a Link Tuple is created. 740 If the HELLO message indicates that the receiving MANET interface 741 has been heard, then the link is considered symmetric, or the 742 duration for which that Link Tuple is kept as symmetric is 743 extended. If the HELLO message indicates that the receiving MANET 744 interface is lost, then the link is no longer considered 745 symmetric. In this case one or more Lost Neighbor Tuples may be 746 created. 748 o If the link on which the HELLO message is received is symmetric, 749 then any symmetrically advertised neighbor addresses in the HELLO 750 message are added to the 2-Hop Set for the receiving interface, or 751 if already present, the duration for which the corresponding 2-Hop 752 Tuples are kept are extended. 754 In all cases the processing takes into account unexpected and 755 erroneous information in the HELLO message, maintaining the 756 constraints specified in Appendix B. 758 4.4. Link Quality 760 Some links in a MANET may be marginal, e.g. due to adverse wireless 761 propagation. In order to avoid using such marginal links, a link 762 quality value is recorded with each link in the Link Set. A MANET 763 router considers links for which an insufficient link quality is 764 recorded to be lost. Modifying the recorded link quality of a link 765 in the Link Set is OPTIONAL. If link quality is not to be modified 766 it MUST be set to indicate an always usable quality link. Link 767 quality information is only used locally, it is not used in 768 signaling, and routers may interoperate whether they are using the 769 same, different, or no, link quality information. Link quality 770 information is thus not equivalent to a link metric. 772 5. Protocol Parameters and Constants 774 The parameters and constants used in this specification are described 775 in this section. 777 5.1. Interface Parameters 779 The interface parameters used by this specification may be classified 780 into the following four categories: 782 o Message intervals 784 o Information validity times 786 o Link quality 788 o Jitter 790 These are detailed in the following sections. 792 Different MANET interfaces (on the same or on different routers) MAY 793 employ different interface parameter values, and MAY change their 794 interface parameter values dynamically, subject to the constraints 795 given in this section. A particular case is where all MANET 796 interfaces on all MANET routers within a given MANET employ the same 797 set of interface parameter values. 799 5.1.1. Message Intervals 801 The following interface parameters regulate HELLO message 802 transmissions over a given MANET interface. 804 HELLO messages serve two principal functions: 806 o To advertise this router's interface addresses to its 1-hop 807 neighbors. The frequency of these advertisements is regulated by 808 the interface parameters HELLO_INTERVAL and HELLO_MIN_INTERVAL. 810 o To advertise this router's knowledge of each of its 1-hop 811 neighbors. The frequency of the advertisement of each such 812 neighbor is regulated by the interface parameter REFRESH_INTERVAL. 814 Specifically, these parameters are as follows: 816 HELLO_INTERVAL - is the maximum time between the transmission of two 817 successive HELLO messages on this MANET interface. If using 818 periodic transmission of HELLO messages, these SHOULD be at a 819 separation of HELLO_INTERVAL, possibly modified by jitter as 820 specified in [RFC5148]. 822 HELLO_MIN_INTERVAL - is the minimum interval between transmission of 823 two successive HELLO messages, on this MANET interface. (This 824 minimum interval MAY be modified by jitter, as defined in 825 [RFC5148].) 827 REFRESH_INTERVAL - is the maximum interval between advertisements in 828 a HELLO message of each 1-hop neighbor address and its status. In 829 all intervals of length REFRESH_INTERVAL, a router MUST include 830 all 1-hop neighbor information that it is specified as sending in 831 at least one HELLO message on this MANET interface. 833 The following constraints apply to these interface parameters: 835 o HELLO_INTERVAL > 0 837 o HELLO_MIN_INTERVAL >= 0 839 o HELLO_INTERVAL >= HELLO_MIN_INTERVAL 841 o REFRESH_INTERVAL >= HELLO_INTERVAL 843 o If INTERVAL_TIME Message TLVs as defined in [timetlv] are included 844 in HELLO messages, then HELLO_INTERVAL MUST be representable as 845 described in [timetlv]. 847 If REFRESH_INTERVAL > HELLO_INTERVAL, then a router may distribute 848 its neighbor advertisements between HELLO messages in any manner, 849 subject to the constraints above. 851 For a router to employ this protocol in a purely responsive manner on 852 a MANET interface, REFRESH_INTERVAL and HELLO_INTERVAL SHOULD both be 853 set to a value such that a responsive HELLO message is always 854 expected in a shorter period than this value. 856 If a router has more than one MANET interface, then, even if the 857 router configures different values of HELLO_INTERVAL on each 858 interface, the router SHOULD configure the same value of 859 HELLO_MIN_INTERVAL on all interfaces on which responsive HELLO 860 messages may be sent. 862 5.1.2. Information Validity Times 864 The following interface parameters manage the validity time of link 865 information: 867 L_HOLD_TIME - is the period of advertisement, on this MANET 868 interface, of former 1-hop neighbor addresses as lost in HELLO 869 messages, allowing recipients of these HELLO messages to 870 accelerate removal of this information from their Link Sets. 871 L_HOLD_TIME MAY be set to zero, if accelerated information removal 872 is not required. 874 H_HOLD_TIME - is used as the value in the VALIDITY_TIME Message TLV 875 included in all HELLO messages on this MANET interface. 877 The following constraints apply to these interface parameters: 879 o L_HOLD_TIME >= 0 881 o H_HOLD_TIME >= REFRESH_INTERVAL 883 o If HELLO messages can be lost then both parameters SHOULD be 884 significantly greater than REFRESH_INTERVAL. 886 o H_HOLD_TIME MUST be representable as described in [timetlv]. 888 5.1.3. Link Quality 890 The following interface parameters manage the usage of link quality 891 (see Section 14): 893 HYST_ACCEPT - is the link quality threshold at or above which a link 894 becomes usable, if it was not already so. 896 HYST_REJECT - is the link quality threshold below which a link 897 becomes unusable, if it was not already so. 899 INITIAL_QUALITY - is the initial quality of a newly identified link. 901 INITIAL_PENDING - if true, then a newly identified link is 902 considered pending, and is not usable until the link quality has 903 reached or exceeded the HYST_ACCEPT threshold. 905 The following constraints apply to these interface parameters: 907 o 0 <= HYST_REJECT <= HYST_ACCEPT <= 1 909 o 0 <= INITIAL_QUALITY <= 1. 911 o If link quality is not updated, then INITIAL_QUALITY >= 912 HYST_ACCEPT. 914 o If INITIAL_QUALITY >= HYST_ACCEPT, then INITIAL_PENDING := false. 916 o If INITIAL_QUALITY < HYST_REJECT, then INITIAL_PENDING := true. 918 5.1.4. Jitter 920 If jitter, as defined in [RFC5148], is used then these parameters are 921 as follows: 923 HP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 924 for periodically generated HELLO messages on this MANET interface. 926 HT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 927 for externally triggered HELLO messages on this MANET interface. 929 For constraints on these interface parameters see [RFC5148]. 931 5.2. Router Parameters 933 The two router parameters defined by this specification are in the 934 category of information validity time. 936 5.2.1. Information Validity Time 938 The following router parameter manages the validity time of lost 939 symmetric 1-hop neighbor information: 941 N_HOLD_TIME - is used as the period during which former 1-hop 942 neighbor addresses are advertised as lost in HELLO messages, 943 allowing recipients of these HELLO messages to accelerate removal 944 of this information from their 2-Hop Sets. N_HOLD_TIME MAY be set 945 to zero, if accelerated information removal is not required. 947 I_HOLD_TIME - is the period for which a recently used local 948 interface address is recorded. 950 The following constraints applies to these router parameters: 952 o N_HOLD_TIME >= 0 954 o I_HOLD_TIME >= 0 956 5.3. Parameter Change Constraints 958 This section presents guidelines, applicable if protocol parameters 959 are changed dynamically. 961 HELLO_INTERVAL 963 * If the HELLO_INTERVAL for a MANET interface increases, then the 964 next HELLO message on this MANET interface MUST be generated 965 according to the previous, shorter, HELLO_INTERVAL. Additional 966 subsequent HELLO messages MAY be generated according to the 967 previous, shorter, HELLO_INTERVAL (but MUST include times 968 according to current parameters). 970 * If the HELLO_INTERVAL for a MANET interface decreases, then the 971 following HELLO messages on this MANET interface MUST be 972 generated according to this current, shorter, HELLO_INTERVAL. 974 REFRESH_INTERVAL 976 * If the REFRESH_INTERVAL for a MANET interface increases, then 977 the content of subsequent HELLO messages must be organized such 978 that the specification of the old value of REFRESH_INTERVAL is 979 satisfied for a further period equal to the old value of 980 REFRESH_INTERVAL. 982 * If the REFRESH_INTERVAL for a MANET interface decreases, then 983 it MAY be necessary to reschedule HELLO message generation on 984 that MANET interface, in order that the specification of 985 REFRESH_INTERVAL is satisfied from the time of change. 987 HYST_ACCEPT and HYST_REJECT 989 * If HYST_ACCEPT or HYST_REJECT changes, then the appropriate 990 actions for link quality change, as specified in Section 14.3 991 MUST be taken. 993 L_HOLD_TIME 995 * If L_HOLD_TIME changes, then L_time for all relevant Link 996 Tuples MUST be changed. 998 N_HOLD_TIME 1000 * If N_HOLD_TIME changes, then NL_time for all relevant Lost 1001 Neighbor Tuples MUST be changed. 1003 HP_MAXJITTER 1005 * If HP_MAXJITTER changes, then the periodic HELLO message 1006 schedule on this MANET interface MAY be changed. 1008 HT_MAXJITTER 1010 * If HT_MAXJITTER changes, then externally triggered HELLO 1011 messages on this MANET interface MAY be rescheduled. 1013 5.4. Constants 1015 The constant C (time granularity) is used as specified in [timetlv]. 1017 6. Local Information Base 1019 A router maintains a Local Information Base that records information 1020 about its interfaces (MANET and non-MANET). Each interface MUST have 1021 at least one address, and MAY have more than one address. 1023 The Local Information Base is not modified by signaling. If a 1024 router's interface configuration changes, then the Local Information 1025 Base MUST reflect these changes. This MAY also result in signaling 1026 to advertise these changes. 1028 Interfaces and addresses MAY be excluded from the Local Information 1029 Base, and hence from HELLO messages, if they are not to be used for 1030 routing. 1032 6.1. Local Interface Set 1034 A router's Local Interface Set records its local interfaces. It 1035 consists of Local Interface Tuples, one per interface: 1037 (I_local_iface_addr_list, I_manet) 1039 where: 1041 I_local_iface_addr_list is an unordered list of the addresses of 1042 this interface. 1044 I_manet is a boolean flag, describing if this interface is a MANET 1045 interface. 1047 Local Interface Tuples are removed from the Local Interface Set only 1048 when the routers' interface configuration changes, subject to 1049 Section 9, i.e. they are not subject to timer-based expiration. 1051 6.2. Removed Interface Address Set 1053 A router's Removed Interface Address Set records addresses which were 1054 recently local interface addresses. If a router's interface 1055 addresses are immutable then this set is always empty and MAY be 1056 omitted. It consists of Removed Interface Address Tuples, one per 1057 address: 1059 (IR_local_iface_addr, IR_time) 1061 where: 1063 IR_local_iface_addr is a recently used address of an interface of 1064 this router. 1066 IR_time specifies when this Tuple expires and MUST be removed. 1068 7. Interface Information Base 1070 A router maintains an Interface Information Base for each of its 1071 MANET interfaces. This records information about links to that MANET 1072 interface and symmetric 2-hop neighbors which can be reached in two 1073 hops using those links as the first hop. The Interface Information 1074 Base includes the Link Set and the 2-Hop Set. 1076 A MANET interface address can be present as of both a 1-hop neighbor 1077 and a symmetric 2-hop neighbor. This allows the router with this 1078 MANET interface address to be immediately considered as a symmetric 1079 2-hop neighbor if it fails to be a symmetric 1-hop neighbor. 1081 An element which specifies a time is considered expired if the 1082 current time is greater than or equal to that time. One such element 1083 in most Tuples when expired indicates that the Tuple itself is 1084 considered expired and MUST be removed when that element so 1085 indicates. Tuples which do not have such a time element are removed 1086 at other times as specified, for example a Neighbor Tuple is removed 1087 when all corresponding Link Tuples have been removed. 1089 7.1. Link Set 1091 A router's Link Set records links from other routers which are, or 1092 recently were, 1-hop neighbors. It consists of Link Tuples, each 1093 representing a single link: 1095 (L_neighbor_iface_addr_list, L_HEARD_time, L_SYM_time, 1096 L_quality, L_pending, L_lost, L_time) 1098 where: 1100 L_neighbor_iface_addr_list is an unordered list of the addresses of 1101 the MANET interface of the 1-hop neighbor; 1103 L_HEARD_time is the time until which the MANET interface of the 1104 1-hop neighbor would be considered heard if not considering link 1105 quality; 1107 L_SYM_time is the time until which the link to the 1-hop neighbor 1108 would be considered symmetric if not considering link quality; 1110 L_quality is a dimensionless number between 0 (inclusive) and 1 1111 (inclusive) describing the quality of a link; a greater value of 1112 L_quality indicating a higher quality link; 1114 L_pending is a boolean flag, describing if a link is considered 1115 pending (i.e. a candidate, but not yet established, link); 1117 L_lost is a boolean flag, describing if a link is considered lost 1118 due to link quality; 1120 L_time specifies when this Tuple expires and MUST be removed. 1122 The status of the link, as obtained through HELLO message exchange, 1123 and also taking link quality into account, is denoted L_status. 1124 L_status can take the values PENDING, HEARD, SYMMETRIC and LOST. The 1125 values LOST, SYMMETRIC and HEARD are defined in Section 17.5. The 1126 value PENDING is never used in a HELLO message, it is only used 1127 locally by a router, and any value distinct from LOST, SYMMETRIC and 1128 HEARD may be used. 1130 L_status is defined by: 1132 1. If L_pending = true, then L_status := PENDING; 1134 2. otherwise, if L_lost = true, then L_status := LOST; 1136 3. otherwise, if L_SYM_time is not expired, then L_status := 1137 SYMMETRIC; 1139 4. otherwise, if L_HEARD_time is not expired, then L_status := 1140 HEARD; 1142 5. otherwise, L_status := LOST. 1144 7.2. 2-Hop Set 1146 A router's 2-Hop Set records symmetric 2-hop neighbor interface 1147 addresses, and the symmetric links to symmetric 1-hop neighbors 1148 through which the symmetric 2-hop neighbors can be reached. It 1149 consists of 2-Hop Tuples, each representing a single interface 1150 address of a symmetric 2-hop neighbor, and a single MANET interface 1151 of a symmetric 1-hop neighbor. 1153 (N2_neighbor_iface_addr_list, N2_2hop_iface_addr, N2_time) 1155 where: 1157 N2_neighbor_iface_addr_list is an unordered list of the addresses of 1158 the MANET interface of the symmetric 1-hop neighbor from which 1159 this information was received; 1161 N2_2hop_iface_addr is an address of an interface of a symmetric 1162 2-hop neighbor which has a symmetric link (using any MANET 1163 interface) to the indicated symmetric 1-hop neighbor; 1165 N2_time specifies when this Tuple expires and MUST be removed. 1167 8. Neighbor Information Base 1169 Each router maintains a Neighbor Information Base that records 1170 information about addresses of current and recently symmetric 1-hop 1171 neighbors. 1173 8.1. Neighbor Set 1175 A router's Neighbor Set records all interface addresses of each 1-hop 1176 neighbor. It consists of Neighbor Tuples, each representing a single 1177 1-hop neighbor: 1179 (N_neighbor_iface_addr_list, N_symmetric) 1181 where: 1183 N_neighbor_iface_addr_list is an unordered list of the interface 1184 addresses of a 1-hop neighbor; 1186 N_symmetric is a boolean flag, describing if this is a symmetric 1187 1-hop neighbor. 1189 Neighbor Tuples are removed from the Neighbor Set only when 1190 corresponding Link Tuples expire from the routers' Link Set, i.e. 1191 Neighbor Tuples are not directly subject to timer-based expiration. 1193 8.2. Lost Neighbor Set 1195 A router's Lost Neighbor Set records addresses of all interfaces of 1196 routers which recently were symmetric 1-hop neighbors, but are now 1197 advertised as lost. It consists of Lost Neighbor Tuples, each 1198 representing a single such address: 1200 (NL_neighbor_iface_addr, NL_time) 1202 where: 1204 NL_neighbor_iface_addr is an address of an interface of a router 1205 which recently was a symmetric 1-hop neighbor of this router; 1207 NL_time specifies when this Tuple expires and MUST be removed. 1209 9. Local Information Base Changes 1211 The Local Information Base MUST change to respond to changes in the 1212 router's local interface configuration. The router MUST update its 1213 Interface Information Base and Neighbor Information Base in response 1214 to such changes. If any changes in the Interface Information Base or 1215 the Neighbor Information Base satisfy any of the conditions described 1216 in Section 13, then those changes must be applied immediately, unless 1217 noted otherwise. 1219 A router MAY transmit HELLO messages in response to these changes. 1221 9.1. Adding an Interface 1223 If an interface is added to the router then this is indicated by the 1224 addition of a Local Interface Tuple to the Local Interface Set. If 1225 the new interface is a MANET interface then an initially empty 1226 Interface Information Base MUST be created for this new MANET 1227 interface. The actions in Section 9.3 MUST be taken for each address 1228 of this added interface. A HELLO message MAY be sent on all MANET 1229 interfaces, it SHOULD be sent on the new interface if it is a MANET 1230 interface. If using scheduled messages, then a message schedule MUST 1231 be established on a new MANET interface. 1233 9.2. Removing an Interface 1235 If an interface is removed from the router, then this MUST result in 1236 changes to the Local Information Base and to the Neighbor Information 1237 Base as follows: 1239 1. Identify the Local Interface Tuple that corresponds to the 1240 interface to be removed. 1242 2. For each address (henceforth removed address) in the 1243 I_local_iface_addr_list of that Local Interface Tuple, create a 1244 Removed Interface Address Tuple with: 1246 * IR_local_iface_addr := removed address; 1247 * IR_time := current time + I_HOLD_TIME. 1249 3. Remove that Local Interface Tuple from the Local Interface Set. 1251 4. If the interface to be removed is a MANET interface (i.e. with 1252 I_manet = true) then: 1254 1. Remove the Interface Information Base for that MANET 1255 interface; 1257 2. All Neighbor Tuples for which none of the addresses in its 1258 N_neighbor_iface_addr_list are contained in any 1259 L_neighbor_iface_addr_list in any remaining Link Set, are 1260 removed. 1262 If a router removes the Local Interface Tuple that contains the 1263 interface address which is used to define the router's originator 1264 address, as defined in [RFC5444], then the router MAY change 1265 originator address. If this interface address may now be used by 1266 another router (e.g. if the address was taken from a prefix no longer 1267 delegated to this router, or if the address was assigned with an 1268 expiration timer, and not renewed before expiration) then this router 1269 MUST change originator address. 1271 If the removed interface is the last MANET interface of the router, 1272 then there will be no remaining Interface Information Bases, and the 1273 router will longer participate in this protocol. 1275 After removing the interface and making these changes, a HELLO 1276 message MAY be sent on all remaining MANET interfaces. 1278 9.3. Adding an Address to an Interface 1280 If an address is added to an interface then this is indicated by the 1281 addition of an address to the appropriate I_local_iface_addr_list. 1282 The following changes MUST be made to the Information Bases: 1284 1. The Neighbor Tuples, if any, whose N_neighbor_iface_addr_list 1285 contains the added address, are removed. 1287 2. Any Link Tuples, in any Link Set, whose 1288 L_neighbor_iface_addr_list contains: 1290 * the added address; OR 1292 * any address in the N_neighbor_iface_addr_list of any removed 1293 Neighbor Tuple 1295 are removed; apply Section 13.2, but not Section 13.3. 1297 3. Any Lost Neighbor Tuples whose NL_neighbor_iface_addr = the added 1298 address, are removed. 1300 4. Any 2-Hop Tuples whose N2_2hop_iface_addr = the added address, 1301 are removed. 1303 After adding the address and making these changes, a HELLO message 1304 MAY be sent on all MANET interfaces. 1306 9.4. Removing an Address from an Interface 1308 If an address (henceforth removed address) is removed from an 1309 interface then: 1311 1. Identify the Local Interface Tuple that corresponds to the 1312 interface to be removed. 1314 2. If this is the only address of that interface (the only address 1315 in the corresponding I_local_iface_addr_list) then remove that 1316 interface as specified in Section 9.2. 1318 3. Otherwise: 1320 1. Remove the removed address from this I_local_iface_addr_list. 1322 2. Create a Removed Interface Address Tuple with: 1324 + IR_local_iface_addr := removed address; 1326 + IR_time := current time + I_HOLD_TIME. 1328 If a router removes the interface address that is used to define the 1329 router's originator address, as defined in [RFC5444], then the router 1330 MAY change originator address. If this interface address may now be 1331 used by another router then this router MUST change originator 1332 address. 1334 After removing the address and making these changes, a HELLO message 1335 MAY be sent on all MANET interfaces. 1337 10. Packets and Messages 1339 The packet and message format used by this protocol is defined in 1340 [RFC5444], which is used with the following considerations: 1342 o This protocol specifies one Message Type, the HELLO message. 1344 o A HELLO message MAY use any combination of Message Header options. 1346 o HELLO messages MUST NOT be forwarded. 1348 o HELLO messages MAY be included in multi-message packets as 1349 specified in [RFC5444]. 1351 o Received HELLO messages MUST be parsed in accordance with 1352 [RFC5444]. A HELLO message which is not in conformance with 1353 [RFC5444] MUST be discarded. A HELLO message may also be 1354 discarded for other reasons, see Section 12.1. 1356 o This protocol specifies three Address Block TLVs. It also uses 1357 two Message TLVs defined in [timetlv]. These five TLV Types are 1358 all defined only with Type Extension = 0. TLVs of other types, 1359 and of these types but without Type Extension = 0, are ignored by 1360 this protocol. All references in this protocol to, for example, 1361 an Address Block TLV with Type = LINK_STATUS, are to be considered 1362 as referring to an Address Block TLV with Type = LINK_STATUS and 1363 Type Extension = 0. 1365 10.1. HELLO Messages 1367 A HELLO message MUST contain: 1369 o A VALIDITY_TIME Message TLV as specified in [timetlv], 1370 representing H_HOLD_TIME for the transmitting MANET interface. 1371 The options included in [timetlv] for representing zero and 1372 infinite times MUST NOT be used. 1374 A HELLO message which is transmitted periodically SHOULD contain, and 1375 otherwise MAY contain: 1377 o An INTERVAL_TIME Message TLV as specified in [timetlv], 1378 representing HELLO_INTERVAL for the transmitting MANET interface. 1379 The options included in [timetlv] for representing zero and 1380 infinite times MUST NOT be used. 1382 A HELLO message MAY contain: 1384 o Other Message TLVs. 1386 o One or more Address Blocks, each with an associated Address Block 1387 TLV Block, which MAY contain other Address Block TLVs. 1389 10.1.1. Address Blocks 1391 All addresses in a router's Local Interface Set (i.e. in any 1392 I_local_iface_addr_list) MUST be included in the Address Blocks in 1393 all generated HELLO messages with the following exception. If the 1394 MANET interface on which the HELLO message is to be sent has a single 1395 interface address with maximum prefix length, then that address MAY 1396 be omitted from being included in an Address Block, provided that 1397 this address is included as the sending address of the IP datagram in 1398 which the HELLO message is included. All addresses of the router's 1399 interfaces included in an Address Block MUST be associated with an 1400 Address Block TLV with Type = LOCAL_IF, as defined in Table 1. 1402 +----------+---------+----------------------------------------------+ 1403 | Name | Value | Description | 1404 | | Length | | 1405 +----------+---------+----------------------------------------------+ 1406 | LOCAL_IF | 1 octet | Specifies that the address is an address | 1407 | | | associated with the interface on which the | 1408 | | | message was sent (THIS_IF) or another | 1409 | | | interface of the sending router (OTHER_IF). | 1410 +----------+---------+----------------------------------------------+ 1412 Table 1: LOCAL_IF TLV definition 1414 Address Blocks MAY contain current or recently lost 1-hop neighbors' 1415 interface addresses, each of which is associated with Address Block 1416 TLVs as described in Table 2. 1418 +--------------+---------+------------------------------------------+ 1419 | Name | Value | Description | 1420 | | Length | | 1421 +--------------+---------+------------------------------------------+ 1422 | LINK_STATUS | 1 octet | Specifies the status of the link from | 1423 | | | the indicated address (LOST, SYMMETRIC | 1424 | | | or HEARD). | 1425 | OTHER_NEIGHB | 1 octet | Specifies that the address is | 1426 | | | (SYMMETRIC) or was (LOST) of an | 1427 | | | interface of a symmetric 1-hop neighbor | 1428 | | | of the router transmitting the HELLO | 1429 | | | message. | 1430 +--------------+---------+------------------------------------------+ 1432 Table 2: LINK_STATUS and OTHER_NEIGHB TLV definition 1434 An Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC or 1435 Value = LOST also performs the function of an Address Block TLV with 1436 Type = OTHER_NEIGHB and the same value. The latter SHOULD NOT also 1437 be included. If an Address Block TLV with Type = LINK_STATUS and 1438 Value = SYMMETRIC is combined with an Address Block TLV with Type = 1439 OTHER_NEIGHB and Value = LOST then the latter MUST be ignored, and 1440 SHOULD NOT be included. See Appendix A. 1442 Other addresses MAY be included in Address Blocks, but MUST NOT be 1443 associated with any of the Address Block TLVs specified in this 1444 specification. 1446 11. HELLO Message Generation 1448 Each MANET interface MUST generate HELLO messages according to the 1449 specification in this section. HELLO messages are generated for each 1450 HELLO interface independently. HELLO message generation and 1451 scheduling MUST be according to the interface parameters for that 1452 MANET interface, and MAY be independent for each MANET interface or, 1453 interface parameters permitting, MANET interfaces MAY use the same 1454 schedule. 1456 If transmitting periodic HELLO messages then, following a HELLO 1457 message transmission on a MANET interface, another HELLO message MUST 1458 be transmitted on the same MANET interface after an interval not 1459 greater than HELLO_INTERVAL. Two successive HELLO message 1460 transmissions on the same MANET interface MUST be separated by at 1461 least HELLO_MIN_INTERVAL, except as noted in Section 11.2.1. 1463 11.1. HELLO Message Specification 1465 HELLO messages are generated independently on each MANET interface. 1467 All addresses in any I_local_iface_addr_list MUST be included, except 1468 that: 1470 o If the interface on which the HELLO message is to be sent has a 1471 single interface address with maximum prefix length then that 1472 interface address MAY be omitted, provided that this address is 1473 included as the sending address of the IP datagram in which the 1474 HELLO message is included. 1476 All such included addresses MUST be associated with an Address Block 1477 TLV included with Type := LOCAL_IF and Value according to the 1478 following: 1480 o If the address is an address of the sending interface, then Value 1481 := THIS_IF. 1483 o Otherwise, Value := OTHER_IF. 1485 The following addresses of current or former 1-hop neighbors MAY be 1486 included in any HELLO message: 1488 o Addresses of MANET interfaces of 1-hop neighbors from the Link Set 1489 of the Interface Information Base for this MANET interface, other 1490 than those from Link Tuples with L_status = PENDING. 1492 o Other addresses of symmetric 1-hop neighbors from the Neighbor Set 1493 of this router's Neighbor Information Base. 1495 o Addresses of MANET interfaces of previously symmetric or heard 1496 1-hop neighbors connected on this MANET interface from the Link 1497 Set of the Interface Information Base for this MANET interface. 1498 (These are advertised for a period equal to this interface's 1499 L_HOLD_TIME after loss.) 1501 o Other addresses of previously symmetric 1-hop neighbors from the 1502 Lost Neighbor Set of this router's Neighbor Information Base. 1503 (These are advertised for a period equal to N_HOLD_TIME after 1504 loss.) 1506 Each such address MUST be associated with one or more appropriate 1507 Address Block TLVs, respecting the parameter REFRESH_INTERVAL for 1508 each association for each MANET interface. Specifically: 1510 1. For each address (henceforth linked address) which is contained 1511 in an L_neighbor_iface_addr_list of a Link Tuple in the Link Set 1512 for this MANET interface, for which L_status != PENDING, include 1513 the linked address with an associated Address Block TLV with: 1515 * Type := LINK_STATUS; AND 1517 * Value := L_status. 1519 2. For each address (henceforth neighbor address) which is contained 1520 in an N_neighbor_iface_addr_list in a Neighbor Tuple with 1521 N_symmetric = true, and which has not already been included with 1522 an associated Address Block TLV with Type = LINK_STATUS and Value 1523 = SYMMETRIC, include the neighbor address with an associated 1524 Address Block TLV with: 1526 * Type := OTHER_NEIGHB; AND 1528 * Value := SYMMETRIC. 1530 3. For each Lost Neighbor Tuple whose NL_neighbor_iface_addr 1531 (henceforth lost address) has not already been included, include 1532 the lost address with an associated Address Block TLV with: 1534 * Type := OTHER_NEIGHB; AND 1536 * Value := LOST. 1538 If any such addresses have been added since the last HELLO message 1539 was sent on this MANET interface, or if their status (as indicated by 1540 these TLVs and the values they associate with that address) have 1541 changed since that address was last reported on this MANET interface, 1542 then that address, and the indicated TLVs, MUST be included in the 1543 HELLO message. 1545 If a 1-hop neighbor address is specified with more than one 1546 associated Address Block TLV, then these Address Block TLVs MAY be 1547 independently included or excluded from each HELLO message. Each 1548 such Address Block TLV MUST be included associated with that address 1549 in a HELLO message sent on that MANET interface in every interval of 1550 length equal to that MANET interface's parameter REFRESH_INTERVAL. 1551 Address Block TLVs associated with the same address included in the 1552 same HELLO message MAY be applied to the same or different copies of 1553 that address. 1555 11.2. HELLO Message Transmission 1557 HELLO messages are transmitted in the packet/message format specified 1558 by [RFC5444] using the "LL-MANET-Routers" multicast address specified 1559 by [manet-iana] as destination IP address, using either the "manet" 1560 UDP port, or the "manet" IP protocol number specified in 1561 [manet-iana]. 1563 11.2.1. HELLO Message Jitter 1565 HELLO messages MAY be sent using periodic message generation or 1566 externally triggered message generation. If using data link and 1567 physical layers which are subject to packet loss due to collisions, 1568 HELLO messages SHOULD be jittered as described in [RFC5148]. 1570 Internally triggered message generation (such as due to a change in 1571 local interfaces) MAY be treated as if externally generated message 1572 generation, or MAY be not jittered. 1574 HELLO messages MUST NOT be forwarded, and thus message forwarding 1575 jitter does not apply to HELLO messages. 1577 Each form of jitter described in [RFC5148] requires a parameter 1578 MAXJITTER. These interface parameters may be dynamic, and are 1579 specified by: 1581 o For periodic message generation: HP_MAXJITTER. 1583 o For externally triggered message generation: HT_MAXJITTER. 1585 When HELLO message generation is delayed in order that a HELLO 1586 message is not sent within HELLO_MIN_INTERVAL of the previous HELLO 1587 message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD 1588 be reduced by jitter, with maximum reduction HP_MAXJITTER, as 1589 described in [RFC5148]. In this case HP_MAXJITTER MUST NOT be 1590 greater than HELLO_MIN_INTERVAL. 1592 12. HELLO Message Processing 1594 On receiving a HELLO message, a router MUST first check if the 1595 message is invalid for processing by this router, as defined in 1596 Section 12.1. Otherwise the receiving router MUST update its 1597 appropriate Interface Information Base and its Neighbor Information 1598 Base as specified in Section 12.3 to Section 12.6. These updates 1599 MUST be performed in the order in which they are presented in this 1600 specification. If any changes satisfy any of the conditions 1601 described in Section 13 then the indicated consequences MUST be 1602 applied immediately, unless noted otherwise. 1604 All message processing, including determination of whether a message 1605 is invalid, considers only TLVs with Type Extension = 0. TLVs with 1606 any other type extension are ignored. All references to, for 1607 example, a TLV with Type = LINK_STATUS refer to a TLV with Type = 1608 LINK_STATUS and Type Extension = 0. 1610 12.1. Invalid Message 1612 A received HELLO message is invalid for processing by this router if 1613 any of the following conditions are true. 1615 o The message has a field in its with a 1616 value other than one. (Note that the message need not have a 1617 field.) 1619 o The message has a field in its with a 1620 value other than zero. (Note that the message need not have a 1621 field.) 1623 o The message does not have a Message TLV with Type = VALIDITY_TIME 1624 in its Message TLV Block. 1626 o The message has more than one Message TLV with Type = 1627 VALIDITY_TIME in its Message TLV Block, and these Message TLVs 1628 indicate different validity times, as specified by [timetlv]. 1630 o The message has any Address Block TLV(s) with Type = LOCAL_IF and 1631 any single value v such that v != THIS_IF and v!= OTHER_IF. 1633 o Any address (including different copies of an address, in the same 1634 or different Address Blocks) is associated with more than one 1635 value by one or more Address Block TLV(s) with Type = LOCAL_IF. 1637 o Any address (the local address) associated with an Address Block 1638 TLV with Type = LOCAL_IF is one of the receiving router's current 1639 or recently used interface addresses (i.e. the local address is 1640 contained in any I_local_iface_addr_list in the Local Interface 1641 Set or the local address = any IR_local_iface_addr in the Removed 1642 Interface Address Set). 1644 o The message has any Address Block TLV(s) with Type = LINK_STATUS 1645 with any single value v such that v != LOST, v != SYMMETRIC, and 1646 v!= HEARD. 1648 o Any address (including different copies of an address, in the same 1649 or different Address Blocks) is associated with more than one 1650 value by one or more Address Block TLVs with Type = LINK_STATUS. 1652 o The message has any Address Block TLV(s) with Type = OTHER_NEIGHB 1653 with any single value v such that v!= LOST and v!= SYMMETRIC. 1655 o Any address (including different copies of an address, in the same 1656 or different Address Blocks) is associated with more than one 1657 value by one or more Address Block TLVs with Type = OTHER_NEIGHB. 1659 An invalid message MUST be silently discarded, without updating the 1660 router's Information Bases. A router MAY recognize additional 1661 reasons for identifying that a message is badly formed, and discard 1662 such messages. 1664 12.2. Definitions 1666 For the purpose of this section, note the following definitions: 1668 o "validity time" is calculated from the Message TLV with Type = 1669 VALIDITY_TIME of the HELLO message as specified in [timetlv]. 1670 (Note that, as specified by Section 12.1, there must be such a 1671 Message TLV, and if there is more than one, they must indicate the 1672 same validity time.) All information in the HELLO message has the 1673 same validity time. 1675 o "Receiving Address List" is the I_local_iface_addr_list 1676 corresponding to the MANET interface on which the HELLO message 1677 was received 1679 o "Sending Address List" is the list of the addresses contained in 1680 the HELLO message with an associated Address Block TLV with Type = 1681 LOCAL_IF and Value = THIS_IF. If the Sending Address List is 1682 otherwise empty, then the Sending Address List contains a single 1683 address (with maximum prefix length) equal to the sending address 1684 of the IP datagram in which the HELLO message was included. 1686 o "Neighbor Address List" is the Sending Address List, plus the 1687 addresses contained in the HELLO message with an associated 1688 Address Block TLV with Type = LOCAL_IF and Value = OTHER_IF. 1690 o EXPIRED indicates that a timer is set to a value clearly preceding 1691 the current time (e.g. current time - 1). 1693 o "Removed Address List" is a list of addresses created by this 1694 HELLO message processing which were formerly reported as local by 1695 the router originating the HELLO message, but which are not 1696 included in the Neighbor Address List. This list is initialized 1697 as empty. 1699 o "Lost Address List" is a subset of the Removed Address List 1700 containing addresses which were formerly considered as symmetric. 1701 This list is initialized as empty. 1703 12.3. Updating the Neighbor Set 1705 On receiving a HELLO message, the router MUST update its Neighbor Set 1706 and populate the Removed Address List and Lost Address List: 1708 1. Find all Neighbor Tuples (hereafter matching Neighbor Tuples) 1709 where: 1711 * N_neighbor_iface_addr_list contains at least one address in 1712 the Neighbor Address List. 1714 2. If there are no matching Neighbor Tuples, then: 1716 1. Create a new Neighbor Tuple with: 1718 + N_neighbor_iface_addr_list := Neighbor Address List; 1720 + N_symmetric := false. 1722 3. If there is one matching Neighbor Tuple, then: 1724 1. If the matching Neighbor Tuple's N_neighbor_iface_addr_list 1725 != Neighbor Address List, then: 1727 1. For each address (henceforth removed address) which is 1728 contained in that N_neighbor_iface_addr_list, but is not 1729 contained in the Neighbor Address List: 1731 1. Add the removed address to the Removed Address List. 1733 2. If N_symmetric = true, then add the removed address 1734 to the Lost Address List. 1736 2. Update the matching Neighbor Tuple by: 1738 - N_neighbor_iface_addr_list := Neighbor Address List. 1740 4. If there are two or more matching Neighbor Tuples, then: 1742 1. For each address (henceforth removed address) which is 1743 contained in the N_neighbor_iface_addr_list of any of the 1744 matching Neighbor Tuples: 1746 1. Add the removed address to the Removed Address List. 1748 2. If N_symmetric = true, then add the removed address to 1749 the Lost Address List. 1751 2. Replace the matching Neighbor Tuples by a single Neighbor 1752 Tuple with: 1754 + N_neighbor_iface_addr_list := Neighbor Address List; 1756 + N_symmetric := false 1758 12.4. Updating the Lost Neighbor Set 1760 On receiving a HELLO message, a router MUST update its Lost Neighbor 1761 Set: 1763 1. For each address (henceforth lost address) which is contained in 1764 the Lost Address List, if no Lost Neighbor Tuple with 1765 NL_neighbor_iface_addr = lost address exists, then add a Lost 1766 Neighbor Tuple with: 1768 * NL_neighbor_iface_addr := lost address; 1770 * NL_time := current time + N_HOLD_TIME. 1772 12.5. Updating the Link Set 1774 On receiving a HELLO message, a router MUST update its Link Set for 1775 the MANET interface on which the HELLO message is received: 1777 1. Remove all addresses in the Removed Address List from the 1778 L_neighbor_iface_addr_list of all Link Tuples. 1780 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now 1781 empty; apply Section 13.2, but not Section 13.3. 1783 3. Find all Link Tuples (hereafter matching Link Tuples) where: 1785 * L_neighbor_iface_addr_list contains one or more addresses in 1786 the Sending Address List. 1788 4. If there is more than one matching Link Tuple, then remove them 1789 all; apply Section 13.2, but not Section 13.3. 1791 5. If no matching Link Tuples remain, then create a new matching 1792 Link Tuple with: 1794 * L_neighbor_iface_addr_list := empty; 1796 * L_HEARD_time := EXPIRED; 1798 * L_SYM_time := EXPIRED; 1800 * L_quality := INITIAL_QUALITY; 1802 * L_pending := INITIAL_PENDING; 1804 * L_lost := false; 1806 * L_time := current time + validity time. 1808 6. The matching Link Tuple, existing or new, is then modified as 1809 follows: 1811 1. If the router finds any address (henceforth receiving 1812 address) in the Receiving Address List in an Address Block in 1813 the HELLO message, then the Link Tuple is modified as 1814 follows: 1816 1. If any receiving address in the HELLO message is 1817 associated with an Address Block TLV with Type = 1818 LINK_STATUS and with Value = HEARD or Value = SYMMETRIC 1819 then: 1821 - L_SYM_time := current time + validity time. 1823 2. Otherwise if any receiving address in the HELLO message 1824 is associated with an Address Block TLV with Type = 1825 LINK_STATUS and Value = LOST then: 1827 1. if L_SYM_time has not expired, then: 1829 1. L_SYM_time := EXPIRED. 1831 2. if L_status = HEARD or L_status = SYMMETRIC, 1832 then: 1834 * L_time := current time + L_HOLD_TIME. 1836 2. L_neighbor_iface_addr_list := Sending Address List. 1838 3. L_HEARD_time := max(current time + validity time, 1839 L_SYM_time). 1841 4. If L_status = PENDING, then: 1843 + L_time := max(L_time, L_HEARD_time). 1845 5. Otherwise if L_status = HEARD or L_status = SYMMETRIC, then: 1847 + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 1849 12.6. Updating the 2-Hop Set 1851 On receiving a HELLO message a router MUST update its 2-Hop Set for 1852 the MANET interface on which the HELLO message was received: 1854 1. Remove all addresses in the Removed Address List from the 1855 N2_neighbor_iface_addr_list of all 2-Hop Tuples. 1857 2. If the Link Tuple whose L_neighbor_iface_addr_list = Sending 1858 Address List, has L_status = SYMMETRIC then: 1860 1. For each address (henceforth 2-hop address) in an Address 1861 Block of the HELLO message, where: 1863 + 2-hop address is not contained in the Neighbor Address 1864 List; 1866 + 2-hop address is not contained in any 1867 I_local_iface_addr_list; AND 1869 + 2-hop address != any IR_local_iface_addr 1871 4. If 2-hop address has an associated Address Block TLV 1872 with: 1874 - Type = LINK_STATUS and Value = SYMMETRIC; OR 1876 - Type = OTHER_NEIGHB and Value = SYMMETRIC, 1878 then, if there is no 2-Hop Tuple such that: 1880 - N2_neighbor_iface_addr_list contains one or more 1881 addresses in the Sending Address List; AND 1883 - N2_2hop_iface_addr = 2-hop address. 1885 then create a 2-Hop Neighbor Tuple with: 1887 - N2_2hop_iface_addr := 2-hop address. 1889 This 2-Hop Tuple (existing or new) is then modified as 1890 follows: 1892 - N2_neighbor_iface_addr_list := Sending Address List; 1894 - N2_time := current time + validity time. 1896 5. Otherwise if the 2-hop address has an Address Block TLV 1897 with: 1899 - Type = LINK_STATUS and Value = LOST or Value = HEARD; 1900 OR 1902 - Type = OTHER_NEIGHB and Value =o LOST; 1904 then remove all 2-Hop Tuples with: 1906 - N2_neighbor_iface_addr_list contains one or more 1907 addresses in the Sending Address List; AND 1909 - N2_2hop_iface_addr = 2-hop address. 1911 13. Other Information Base Changes 1913 The Interface and Neighbor Information Bases MUST be changed when 1914 some events occur. These events may result from HELLO message 1915 processing, or may be otherwise generated (e.g. expiry of timers or 1916 link quality changes). 1918 Events which cause changes in the Information Bases are: 1920 o A Link Tuple's L_status changes to symmetric. 1922 o A Link Tuple's L_status changes from symmetric, or the Link Tuple 1923 is removed. 1925 o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed. 1927 o Local interface address changes, as specified in Section 9. 1929 o Link quality changes, as specified in Section 14. 1931 If a Link Tuple is removed, or if L_status changes from symmetric and 1932 L_HEARD_time expires, then Section 13.2 MUST be performed before 1933 Section 13.3 for that Link Tuple. 1935 A router MAY report updated information in response to any of these 1936 changes in HELLO message(s), subject to the constraints in 1937 Section 11. 1939 A router which transmits HELLO messages in response to such changes 1940 SHOULD transmit a HELLO message: 1942 o On all MANET interfaces, if the Neighbor Set changes such as to 1943 indicate the change in symmetry of any 1-hop neighbors (including 1944 addition or removal of symmetric 1-hop neighbors). 1946 o Otherwise, on all those MANET interfaces whose Link Set changes 1947 such as to indicate a change in L_status of any 1-hop neighbors 1948 (including the addition or removal of any 1-hop neighbors, other 1949 than those considered pending). 1951 13.1. Link Tuple Symmetric 1953 If, for any Link Tuple which does not have L_status = SYMMETRIC: 1955 o L_status := SYMMETRIC; 1957 (this includes a newly created Link Tuple which is immediately 1958 updated to have L_status := SYMMETRIC) then: 1960 1. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 1961 L_neighbor_iface_addr_list, set: 1963 * N_symmetric := true. 1965 2. Remove all Lost Neighbor Tuples whose NL_neighbor_iface_addr is 1966 contained in that N_neighbor_iface_addr_list. 1968 13.2. Link Tuple Not Symmetric 1970 If for any Link Tuple with L_status = SYMMETRIC: 1972 o L_status changes to any other value; OR 1974 o the Link Tuple is removed; 1976 then: 1978 1. All 2-Hop Tuples for the same MANET interface with: 1980 * N2_neighbor_iface_addr_list contains one or more addresses in 1981 L_neighbor_iface_addr_list; 1983 are removed. 1985 2. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 1986 L_neighbor_iface_addr_list: 1988 1. If there are no remaining Link Tuples for any MANET interface 1989 where: 1991 + L_neighbor_iface_addr_list is contained in 1992 N_neighbor_iface_addr_list; AND 1994 + L_status = SYMMETRIC; 1996 then modify the Neighbor Tuple by: 1998 1. N_symmetric := false. 2000 2. For each address (henceforth neighbor address) in 2001 N_neighbor_iface_addr_list, add a Lost Neighbor Tuple 2002 with: 2004 - NL_neighbor_iface_addr := neighbor address; 2006 - NL_time := current time + N_HOLD_TIME. 2008 13.3. Link Tuple Heard Timeout 2010 If, for any Link Tuple: 2012 o L_HEARD_time expires; OR 2014 o the Link Tuple is removed; 2016 then: 2018 1. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 2019 L_neighbor_iface_addr_list, if no Link Tuples for any MANET 2020 interface remain where: 2022 * L_neighbor_iface_addr_list is contained in 2023 N_neighbor_iface_addr_list; AND 2025 * L_HEARD_time is not expired; 2027 then remove the Neighbor Tuple. 2029 14. Link Quality 2031 Link quality is a mechanism whereby a router MAY take considerations 2032 other than message exchange into account for determining when a link 2033 is and is not a candidate for being considered as HEARD or SYMMETRIC. 2035 Link quality information for a link is generated (e.g. through access 2036 to signal to noise ratio, packet loss rate, or other information from 2037 the link layer) and used only locally, i.e. is not included in 2038 signaling, and routers may interoperate whether they are using the 2039 same, different, or no, link quality information. 2041 For deployments where no link quality is used, the considerations in 2042 Section 14.1 apply. For deployments where link quality is used, the 2043 general principles of link quality usage are described in 2044 Section 14.2. Section 14.3 and Section 14.4 detail link quality 2045 functioning. 2047 14.1. Deployment Without Link Quality 2049 In order for a router to not employ link quality, the router MUST 2050 define: 2052 o INITIAL_PENDING := false; 2054 o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define 2055 INITIAL_QUALITY := 1). 2057 14.2. Basic Principles of Link Quality 2059 To enable link quality usage, the L_quality value of a Link Tuple is 2060 used in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, 2061 to set the flags L_pending and L_lost of that Link Tuple. Based on 2062 these flags, the link status to advertise for that Link Tuple is 2063 determined as described in Section 7.1. 2065 The use of two thresholds implements link hysteresis, whereby a link 2066 which has HYST_REJECT <= L_quality < HYST_ACCEPT may be either 2067 accepted or rejected (depending on which threshold it has most 2068 recently crossed, or, if neither, on the value of parameter 2069 INITIAL_PENDING). With appropriate values of these parameters, this 2070 prevents over-rapid changes of link status. 2072 The basic principles of link quality usage are as follows: 2074 o A router does not advertise a neighbor interface in any state 2075 until L_quality is acceptable: 2077 * If INITIAL_PENDING = true, then this is such that L_quality >= 2078 HYST_ACCEPT. 2080 * Otherwise this is such that L_quality >= HYST_REJECT. To 2081 ensure this, a router MUST NOT define INITIAL_PENDING = false 2082 and INITIAL_QUALITY < HYST_REJECT. (A router also MUST NOT 2083 define INITIAL_PENDING = true and INITIAL_QUALITY >= 2084 HYST_ACCEPT.) 2086 A link which is not yet advertised has L_pending = true. 2088 o Once L_quality >= HYST_ACCEPT, the router sets L_pending := false, 2089 indicating that the link can be advertised. 2091 o A link for which L_pending = false is advertised until its 2092 L_quality drops below HYST_REJECT. 2094 o If a link has L_pending = false and L_quality < HYST_REJECT, the 2095 link is LOST and is advertised as such. This link is not 2096 reconsidered as a candidate HEARD or SYMMETRIC link until 2097 L_quality >= HYST_ACCEPT. 2099 o A link which has an acceptable quality may be advertised as HEARD, 2100 SYMMETRIC or LOST according to the exchange of HELLO messages. 2102 14.3. When Link Quality Changes 2104 If L_quality for a link changes, then the following actions MUST be 2105 taken: 2107 1. If L_quality >= HYST_ACCEPT then the corresponding Link Tuple is 2108 modified by: 2110 1. L_pending := false. 2112 2. L_lost := false. 2114 3. If L_status = HEARD or L_status = SYMMETRIC, then: 2116 + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME) 2118 2. If L_status != PENDING, and L_quality < HYST_REJECT then the 2119 corresponding Link Tuple is modified by: 2121 1. If L_lost = false, then: 2123 + L_lost := true 2125 + L_time := min(L_time, current time + L_HOLD_TIME) 2127 Any appropriate action indicted in Section 13 MUST also be taken. 2129 If L_quality for a link is updated based on HELLO message reception, 2130 or on reception of a packet including a HELLO message, then L_quality 2131 MUST be updated prior to the HELLO message processing described in 2132 Section 12. (If the receipt of the HELLO message, or the packet 2133 containing it, creates the Link Tuple, then the Link Tuple MUST be 2134 created with the appropriately updated L_quality value, rather than 2135 with L_quality := INITIAL_QUALITY.) 2137 14.4. Updating Link Quality 2139 A router MAY update link quality based on any information available 2140 to it. Particular cases that MAY be used include: 2142 o Information from the link layer, such as signal to noise ratio or 2143 packet acknowledgement reception and loss information. 2145 o Receipt or loss of control packets. If control packets include a 2146 sequential packet sequence number, as defined in [RFC5444], then 2147 link quality can be updated when a control packet is received, 2148 whether or not it contains a HELLO message. The link quality may 2149 then, for example, be based on whether the last N out of M control 2150 packets on the link were received, or may use a "leaky integrator" 2151 tracking packet reception and loss. 2153 o Receipt or loss of HELLO messages. If the maximum interval 2154 between HELLO messages is known (such as by inclusion in HELLO 2155 messages of a Message TLV with Type := INTERVAL_TIME, as defined 2156 in [timetlv]) then the loss of HELLO messages can be determined 2157 without the need to receive a later HELLO message. Note that if 2158 this case is combined with the previous case then care must be 2159 taken to avoid "double counting" a lost HELLO message in a lost 2160 packet. 2162 15. Proposed Values for Parameters and Constants 2164 This section lists the parameters and constants used in the 2165 specification of the protocol, and proposed values of each which may 2166 be used when a single value of each is used. 2168 15.1. Message Interval Interface Parameters 2170 o HELLO_INTERVAL := 2 seconds 2172 o HELLO_MIN_INTERVAL := HELLO_INTERVAL/4 2174 o REFRESH_INTERVAL := HELLO_INTERVAL 2176 15.2. Information Validity Time Interface Parameters 2178 o H_HOLD_TIME := 3 x REFRESH_INTERVAL 2180 o L_HOLD_TIME := H_HOLD_TIME 2182 15.3. Information Validity Time Router Parameters 2184 o N_HOLD_TIME := L_HOLD_TIME 2186 o I_HOLD_TIME := N_HOLD_TIME 2188 15.4. Link Quality Interface Parameters 2190 If link quality is changed, then parameter values will depend on the 2191 link quality process. If link quality is not changed, then: 2193 o HYST_ACCEPT := 1 2195 o HYST_REJECT := 0 2196 o INITIAL_QUALITY := 1 2198 o INITIAL_PENDING := false 2200 15.5. Jitter Interface Parameters 2202 o HP_MAXJITTER := HELLO_INTERVAL/4 2204 o HT_MAXJITTER := HP_MAXJITTER 2206 15.6. Constants 2208 o C := 1/1024 second 2210 16. Security Considerations 2212 The objective of this protocol is to allow each router in the network 2213 to acquire information describing its 1-hop and symmetric 2-hop 2214 neighborhoods. This is acquired through message exchange between 2215 neighboring routers. The information is made available through the 2216 Interface Information Bases and Neighbor Information Base, describing 2217 the router's 1-hop neighborhood and symmetric 2-hop neighborhood. 2219 Under normal circumstances, the information recorded in these 2220 Information Bases is correct, i.e. corresponds to the actual network 2221 topology, apart from any changes which have not (yet) been tracked by 2222 the HELLO message exchanges. 2224 If a router for some reason, whether malice or malfunction, injects 2225 invalid HELLO messages, incorrect information may be recorded in 2226 other routers' Information Bases. The protocol specification does, 2227 however, prevent inconsistent information from being injected in the 2228 protocol sets through the constraints in Appendix B. The exact 2229 consequence of information inexactness depends on the use of these 2230 Information Bases, and should be reflected in the specification of 2231 protocols which use information provided by NHDP. 2233 This section, therefore, only outlines the ways in which correctly 2234 formed, but still invalid, HELLO messages may appear, in 2235 Section 16.1. In addition, in Section 16.2, the security suggestions 2236 in [RFC5444] are considered for applicability. 2238 16.1. Invalid HELLO messages 2240 A correctly formed, but still invalid, HELLO message may take any of 2241 the following forms. Note that a present or absent address in an 2242 Address Block, does not in and by itself cause a problem. It is the 2243 presence, absence, or incorrectness of associated LOCAL_IF, 2244 LINK_STATUS and OTHER_NEIGHB Address Block TLVs that causes problems. 2246 A router may provide false information about its own identity: 2248 * The HELLO message may contain addresses with an associated 2249 LOCAL_IF Address Block TLV which do not correspond to addresses 2250 of interfaces of the router transmitting the HELLO message. 2252 * The HELLO message may omit addresses, or their associated 2253 LOCAL_IF Address Block TLV, of interfaces of the router 2254 transmitting the HELLO message (other than the allowed omission 2255 of the only local interface address of the MANET interface over 2256 which the HELLO message is transmitted, if that is the case). 2258 * The HELLO message may incorrectly specify the LOCAL_IF Address 2259 Block TLV value associated with one or more local interface 2260 addresses, indicating incorrectly whether they are associated 2261 with the MANET interface over which the HELLO message is 2262 transmitted. 2264 A router may provide false information about the identity of other 2265 routers: 2267 * A present LINK_STATUS Address Block TLV may, incorrectly, 2268 identify an address as being of a MANET interface which is or 2269 was heard on the MANET interface over which the HELLO message 2270 is transmitted. 2272 * A consistently absent LINK_STATUS Address Block TLV may, 2273 incorrectly, fail to identify an address as being of a MANET 2274 interface which is or was heard on the MANET interface over 2275 which the HELLO message is transmitted. 2277 * A present OTHER_NEIGHB Address Block TLV may, incorrectly, 2278 identify an address as being of a router which is or was in the 2279 sending router's symmetric 1-hop neighborhood; 2281 * A consistently absent OTHER_NEIGHB Address Block TLV may, 2282 incorrectly, fail to identify an address as being of a router 2283 which is or was in the sending router's symmetric 1-hop 2284 neighborhood; 2286 * The value of a LINK_STATUS Address Block TLV may incorrectly 2287 indicate the status (LOST, SYMMETRIC or HEARD) of the link from 2288 a 1-hop neighbor. 2290 * The value of an OTHER_NEIGHB Address Block TLV may incorrectly 2291 indicate the status (LOST or SYMMETRIC) of a symmetric 1-hop 2292 neighbor. 2294 16.2. Authentication, Integrity and Confidentiality Suggestions 2296 The security mechanisms suggested in [RFC5444] with respect to 2297 authentication and integrity can be applied to this neighborhood 2298 discovery protocol, with the following additional considerations: 2300 o As HELLO messages MUST NOT be forwarded, the fields and are either omitted, or will always have 2302 the values of 0 and 1, respectively. 2304 o Consequently, a cryptographic signature can be calculated based on 2305 the entire HELLO message, including its Message Header, and 2306 included in a Message TLV of an appropriate type. 2308 o As HELLO messages MUST NOT be forwarded, and in case hop-by-hop 2309 packet level authentication and integrity is ensured by including 2310 an appropriate Packet TLV containing a cryptographic signature 2311 across the entire packet, inclusion of an additional Message TLV 2312 containing a cryptographic signature for the HELLO Message may not 2313 be necessary. 2315 The security mechanisms suggested in [RFC5444] with respect to 2316 confidentiality can be directly applied to this neighborhood 2317 discovery protocol. 2319 17. IANA Considerations 2321 This specification defines one Message Type, which must be allocated 2322 from the "Message Types" repository of [RFC5444], and three Address 2323 Block TLV Types, which must be allocated from the "Message TLV Types" 2324 repository of [RFC5444]. 2326 17.1. Expert Review: Evaluation Guidelines 2328 For the registries where an Expert Review is required, the designated 2329 expert SHOULD take the same general recommendations into 2330 consideration as are specified by [RFC5444]. 2332 17.2. Message Types 2334 This specification defines one Message Type, to be allocated from the 2335 0-223 range of the "Message Types" namespace defined in [RFC5444], as 2336 specified in Table 3. 2338 +-------+------+-----------------+ 2339 | Name | Type | Description | 2340 +-------+------+-----------------+ 2341 | HELLO | TBD1 | Local signaling | 2342 +-------+------+-----------------+ 2344 Table 3: Message Type assignment 2346 17.3. Message-Type-specific TLV Type Registries 2348 IANA is requested to create a registry for Message-Type-specific 2349 Message TLVs for HELLO messages, in accordance with Section 6.4 of 2350 [RFC5444], and with initial assignments and allocation policies as 2351 specified in Table 4. 2353 +---------+-------------+-------------------+ 2354 | Type | Description | Allocation Policy | 2355 +---------+-------------+-------------------+ 2356 | 128-223 | Unassigned | Expert Review | 2357 +---------+-------------+-------------------+ 2359 Table 4: HELLO Message-Type-specific Message TLV Types 2361 IANA is requested to create a registry for Message-Type-specific 2362 Address Block TLVs for HELLO messages, in accordance with Section 6.5 2363 of [RFC5444], and with initial assignments and allocation policies as 2364 specified in Table 5. 2366 +---------+-------------+-------------------+ 2367 | Type | Description | Allocation Policy | 2368 +---------+-------------+-------------------+ 2369 | 128-223 | Unassigned | Expert Review | 2370 +---------+-------------+-------------------+ 2372 Table 5: HELLO Message-Type-specific Address Block TLV Types 2374 17.4. Address Block TLV Types 2376 This specification defines three Address Block TLV Types, which must 2377 be allocated from the "Address Block TLV Types" namespace defined in 2378 [RFC5444]. IANA are requested to make allocations in the 0-127 range 2379 for these types. This will create three new type extension 2380 registries with assignments as specified in Table 6, Table 7 and 2381 Table 8. Specifications of these Address Block TLVs are in 2382 Section 10.1.1, with value constants defined in Section 17.5. 2384 +----------+------+-----------+-------------------------------------+ 2385 | Name | Type | Type | Description | 2386 | | | extension | | 2387 +----------+------+-----------+-------------------------------------+ 2388 | LOCAL_IF | TBD2 | 0 | Specifies that the address is | 2389 | | | | associated with a local interface | 2390 | | | | of the sending router | 2391 | | | 1-255 | Expert Review | 2392 +----------+------+-----------+-------------------------------------+ 2394 Table 6: Address Block TLV Type assignment: LOCAL_IF 2396 +-------------+------+-----------+----------------------------------+ 2397 | Name | Type | Type | Description | 2398 | | | extension | | 2399 +-------------+------+-----------+----------------------------------+ 2400 | LINK_STATUS | TBD3 | 0 | Specifies the status of the link | 2401 | | | | from the indicated address | 2402 | | | | (LOST, SYMMETRIC or HEARD) | 2403 | | | 1-255 | Expert Review | 2404 +-------------+------+-----------+----------------------------------+ 2406 Table 7: Address Block TLV Type assignment: LINK_STATUS 2408 +--------------+------+-----------+---------------------------------+ 2409 | Name | Type | Type | Description | 2410 | | | extension | | 2411 +--------------+------+-----------+---------------------------------+ 2412 | OTHER_NEIGHB | TBD4 | 0 | Specifies that the address is | 2413 | | | | (SYMMETRIC) or recently was | 2414 | | | | (LOST) of an interface of a | 2415 | | | | symmetric 1-hop neighbor of the | 2416 | | | | router transmitting the message | 2417 | | | 1-255 | Expert Review | 2418 +--------------+------+-----------+---------------------------------+ 2420 Table 8: Address Block TLV Type assignment: OTHER_NEIGHB 2422 17.5. LINK_STATUS and OTHER_NEIGHB Values 2424 The values which the LOCAL_IF Address Block TLV can use are the 2425 following: 2427 o THIS_IF := 0 2429 o OTHER_IF := 1 2431 The values which the LINK_STATUS Address Block TLV can use are the 2432 following: 2434 o LOST := 0 2436 o SYMMETRIC := 1 2438 o HEARD := 2 2440 The values which the OTHER_NEIGHB Address Block TLV can use are the 2441 following: 2443 o LOST := 0 2445 o SYMMETRIC := 1 2447 18. Contributors 2449 This specification is the result of the joint efforts of the 2450 following contributors, listed alphabetically. 2452 o Brian Adamson, NRL, USA, 2454 o Cedric Adjih, INRIA, France, 2456 o Thomas Heide Clausen, LIX, France, 2458 o Justin Dean, NRL, USA, 2460 o Christopher Dearlove, BAE Systems ATC, UK, 2461 2463 o Philippe Jacquet, INRIA, France, 2465 19. Acknowledgements 2467 The authors would like to acknowledge the team behind OLSRv1, 2468 specified in RFC3626 for their contributions. 2470 The authors would like to gratefully acknowledge the following people 2471 for intense technical discussions, early reviews and comments on the 2472 specification and its components (listed alphabetically): Alan Cullen 2473 (BAE Systems), Ulrich Herberg (LIX), Satoh Hiroki (Hitachi) Joe 2474 Macker (NRL), Charles E. Perkins (WiChorus), Laurent Viennot (INRIA), 2475 and the entire IETF MANET working group. 2477 20. References 2478 20.1. Normative References 2480 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2481 Requirement Levels", RFC 2119, BCP 14, March 1997. 2483 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 2484 considerations in MANETs", RFC 5148, February 2008. 2486 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2487 "Generalized MANET Packet/Message Format", RFC 5444, 2488 February 2009. 2490 [timetlv] Clausen, T. and C. Dearlove, "Representing multi-value 2491 time in MANETs", Work In 2492 Progress draft-ietf-manet-timetlv-08.txt, 2493 September 2008. 2495 [manet-iana] Chakeres, I., "IANA Allocations for MANET Protocols", 2496 Work In Progress draft-ietf-manet-iana-07.txt, 2497 November 2007. 2499 20.2. Informative References 2501 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 2502 (MANET): Routing Protocol Performance Issues and 2503 Evaluation Considerations", RFC 2501, January 1999. 2505 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 2506 Routing Protocol", RFC 3626, October 2003. 2508 [RFC5449] Clausen, T., Baccelli, E., Nguyen, D., and P. Jacquet, 2509 "OSPF Multipoint Relay (MPR) Extension for Ad Hoc 2510 Networks", RFC 5449, February 2009. 2512 Appendix A. Address Block TLV Combinations 2514 The algorithm for generating HELLO messages in Section 11 specifies 2515 which 1-hop addresses may be included in the Address Blocks, and with 2516 which associated Address Block TLVs. These Address Block TLVs may 2517 have Type = LINK_STATUS or Type = OTHER_NEIGHB, or both. Address 2518 Block TLVs with Type = LINK_STATUS may have three possible values 2519 (Value = HEARD, Value = SYMMETRIC or Value = LOST), and Address Block 2520 TLVs of TYPE = OTHER_NEIGHB may have two possible values (Value = 2521 SYMMETRIC or Value = LOST). When both Address Block TLVs are 2522 associated with the same address only certain combinations of these 2523 Address Block TLV values are necessary, and are the only combinations 2524 generated by the algorithm in Section 11. These combinations are 2525 indicated in Table 9. 2527 Cells labeled with "Yes" indicate the possible combinations which are 2528 generated by the algorithm in Section 11. Cells labeled with "No" 2529 indicate combinations not generated by the algorithm in Section 11, 2530 but which are correctly parsed and interpreted by the algorithm in 2531 Section 12. The cell labeled with "No*" is actually inconsistent, it 2532 is handled by ignoring the Address Block TLV with Type = 2533 OTHER_NEIGHB. 2535 +----------------+----------------+----------------+----------------+ 2536 | | Type = | Type = | Type = | 2537 | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | 2538 | | (absent) | Value = | Value = LOST | 2539 | | | SYMMETRIC | | 2540 +----------------+----------------+----------------+----------------+ 2541 | Type = | No | Yes | Yes | 2542 | LINK_STATUS | | | | 2543 | (absent) | | | | 2544 | Type = | Yes | Yes | Yes | 2545 | LINK_STATUS, | | | | 2546 | Value = HEARD | | | | 2547 | Type = | Yes | No | No* | 2548 | LINK_STATUS, | | | | 2549 | Value = | | | | 2550 | SYMMETRIC | | | | 2551 | Type = | Yes | Yes | No | 2552 | LINK_STATUS, | | | | 2553 | Value = LOST | | | | 2554 +----------------+----------------+----------------+----------------+ 2556 Table 9: LINK_STATUS and OTHER_NEIGHB TLV combinations 2558 Appendix B. Constraints 2560 Any process which updates the Local Information Base or the Neighbor 2561 Information Base MUST ensure that all constraints specified in this 2562 appendix are maintained. 2564 In each Local Interface Tuple: 2566 o I_local_iface_addr_list MUST NOT be empty. 2568 o I_local_iface_addr_list MUST NOT contain any duplicated addresses. 2570 o I_local_iface_addr_list MUST NOT contain any address which is in 2571 the I_local_iface_addr_list of any other Local Interface Tuple. 2573 In each Removed Interface Address Tuple: 2575 o IR_local_iface_addr MUST NOT contain any address which is in the 2576 I_local_iface_addr_list of any Local Interface Tuple. 2578 o IR_local_iface_addr MUST NOT equal the IR_local_iface_addr of any 2579 other Removed Interface Address Tuple. 2581 In each Link Tuple: 2583 o L_neighbor_iface_addr_list MUST NOT be empty. 2585 o L_neighbor_iface_addr_list MUST NOT contain any address which is 2586 in the I_local_iface_addr_list of any Local Interface Tuple or the 2587 IR_local_iface_addr of any Removed Interface Address Tuple. 2589 o L_neighbor_iface_addr_list MUST NOT contain any duplicated 2590 addresses. 2592 o L_neighbor_iface_addr_list MUST NOT contain any address which is 2593 in the L_neighbor_iface_addr_list of any other Link Tuple in the 2594 same Link Set. 2596 o If L_HEARD_time has not expired then there MUST be a Neighbor 2597 Tuple whose N_neighbor_iface_addr_list contains 2598 L_neighbor_iface_addr_list. 2600 o L_HEARD_time MUST NOT be greater than L_time. 2602 o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are 2603 expired). 2605 o L_quality MUST NOT be less than 0 or greater than 1. 2607 o If L_quality >= HYST_ACCEPT then L_pending MUST be false. 2609 o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST. 2611 o L_pending MUST NOT be set to true if it is currently false. 2613 In each Neighbor Tuple: 2615 o N_neighbor_iface_addr_list MUST NOT contain any address which is 2616 in the I_local_iface_addr_list of any Local Interface Tuple or the 2617 IR_local_iface_addr of any Removed Interface Address Tuple. 2619 o N_neighbor_iface_addr_list MUST NOT contain any duplicated 2620 addresses. 2622 o N_neighbor_iface_addr_list MUST NOT contain any address which is 2623 in the N_neighbor_iface_addr_list of any other Neighbor Tuple. 2625 o If N_symmetric is = true, then there MUST be one or more Link 2626 Tuples with: 2628 * L_neighbor_iface_addr_list contained in 2629 N_neighbor_iface_addr_list; AND 2631 * L_status = SYMMETRIC. 2633 o If N_symmetric is = false, then there MUST be one or more Link 2634 Tuples with: 2636 * L_neighbor_iface_addr_list contained in 2637 N_neighbor_iface_addr_list. 2639 All such Link Tuples MUST NOT have L_status = SYMMETRIC. At least 2640 one such Link Tuple MUST have L_HEARD_time not expired. 2642 In each Lost Neighbor Tuple: 2644 o NL_neighbor_iface_addr MUST NOT be in the I_local_iface_addr_list 2645 of any Local Interface Tuple or the IR_local_iface_addr of any 2646 Removed Interface Address Tuple. 2648 o NL_neighbor_iface_addr MUST NOT equal the NL_neighbor_iface_addr 2649 of any other Lost Neighbor Tuple. 2651 o NL_neighbor_iface_addr MUST NOT be in the 2652 N_neighbor_iface_addr_list of any Neighbor Tuple with N_symmetric 2653 = true. 2655 In each 2-Hop Tuple: 2657 o There MUST be a Link Tuple associated with the same MANET 2658 interface with: 2660 * L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list; AND 2662 * L_status = SYMMETRIC. 2664 o N2_2hop_iface_addr MUST NOT be in the I_local_iface_addr_list of 2665 any Local Interface Tuple or the IR_local_iface_addr of any 2666 Removed Interface Address Tuple. 2668 o N2_2hop_iface_addr MUST NOT be the N2_2hop_iface_addr of any other 2669 2-Hop Tuple in the same 2-Hop Set and with the same 2670 N2_neighbor_iface_addr_list. 2672 o N2_2hop_iface_addr MUST NOT be in the N2_neighbor_iface_addr_list 2673 of the same 2-Hop Tuple. 2675 Appendix C. HELLO Message Example 2677 An example HELLO message, transmitted by an originator router with a 2678 single MANET interface, is as follows. 2680 The message has full Message Header (four bit flags field value is 2681 15). Its four bit Message Address Length field has value 3 and hence 2682 addresses in the message have length four octets, here being IPv4 2683 addresses. The message is as transmitted with a hop limit of 1 and a 2684 hop count of 0. The overall message length is 49 octets. 2686 The message contains a Message TLV Block with content length 8 octets 2687 containing two Message TLVs, of types VALIDITY_TIME and 2688 INTERVAL_TIME. Each uses a Message TLV with flags octet value 16, 2689 indicating that each has a value. Each has a value length of 1 2690 octet; the values included (0x64 and 0x58) are time codes 2691 representing the default values of parameters H_HOLD_TIME and 2692 HELLO_INTERVAL, respectively (6 seconds and 2 seconds) assuming the 2693 default value of constant C (1/1024 second). 2695 The message has a single Address Block containing 5 addresses. The 2696 flags octet value 128 indicates an address Head but no address Tail, 2697 and no address prefixes. The Head Length of 3 octets indicates 2698 address Mid sections of one octet each (Mid 0 to Mid 4). 2700 The following Address Block TLV Block (content length 14 octets) 2701 includes two Address Block TLVs. The first is a LOCAL_IF Address 2702 Block TLV which (with flags octet value 80) indicates that a single 2703 address, with index 0 (i.e. Head:Mid 0) is the single local 2704 interface address of this router (the 1 octet value THIS_IF indicates 2705 that this address is of this interface). The second is a LINK_STATUS 2706 Address Block TLV which (with flags octet value 48) specifies the 2707 link status values of all reported neighbors in a single multivalue 2708 Address Block TLV which covers the addresses with indexes 1 to 4. 2709 The Address Block TLV value length of 4 octets indicates one octet 2710 per value per address. The last four addresses have associated link 2711 status, the first and second HEARD, the third SYMMETRIC, and the 2712 fourth LOST. 2714 0 1 2 3 2715 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 2716 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2717 | HELLO |1 1 1 1 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1| 2718 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2719 | Originator Address | 2720 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2721 |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number | 2722 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2723 |0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0| 2724 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2725 |0 0 0 0 0 0 0 1|0 1 1 0 0 1 0 0| INTERVAL_TIME |0 0 0 1 0 0 0 0| 2726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2727 |0 0 0 0 0 0 0 1|0 1 0 1 1 0 0 0|0 0 0 0 0 1 0 1|1 0 0 0 0 0 0 0| 2728 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2729 |0 0 0 0 0 0 1 1| Head | 2730 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2731 | Mid 0 | Mid 1 | Mid 2 | Mid 3 | 2732 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2733 | Mid 4 |0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0| LOCAL_IF | 2734 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2735 |0 1 0 1 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 1| THIS_IF | 2736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2737 | LINK_STATUS |0 0 1 1 0 0 0 0|0 0 0 0 0 0 0 1|0 0 0 0 0 1 0 0| 2738 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2739 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 2740 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2741 | LOST | 2742 +-+-+-+-+-+-+-+-+ 2744 Note that this example is for illustrative purposes. The essential 2745 information can be conveyed, more efficiently (assuming that the 2746 local interface address will be supplied by IP, and that the 2747 INTERVAL_TIME TLV is not needed) by the 29 octets: 2749 0 1 2 3 2750 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 2751 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2752 | HELLO |0 0 0 0 0 0 1 1|0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1| 2753 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2754 |0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0| 2755 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2756 |0 0 0 0 0 0 0 1|0 1 1 0 0 1 0 0|0 0 0 0 0 1 0 0|1 0 0 0 0 0 0 0| 2757 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2758 |0 0 0 0 0 0 1 1| Head | 2759 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2760 | Mid 1 | Mid 2 | Mid 3 | Mid 4 | 2761 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2762 |0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1| LINK_STATUS |0 0 0 1 0 1 0 0| 2763 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2764 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 2765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2766 | LOST | 2767 +-+-+-+-+-+-+-+-+ 2769 Appendix D. Flow and Congestion Control 2771 This protocol specifies one Message Type, the HELLO message. The 2772 maximum size of a HELLO message is proportional to the size of the 2773 originating router's 1-hop neighborhood. HELLO messages MUST NOT be 2774 forwarded. 2776 A router MUST report its 1-hop neighborhood in HELLO messages on each 2777 of its MANET interfaces at least each REFRESH_INTERVAL. This puts a 2778 lower bound on the control traffic generated by each router in the 2779 network employing this protocol. 2781 A router MUST ensure that two successive HELLO messages sent on the 2782 same MANET interface are separated by at least HELLO_MIN_INTERVAL. 2783 (If using jitter then this may be reduced to a mean minimum value of 2784 HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound 2785 on the control traffic generated by each router in the network 2786 employing this protocol. 2788 Authors' Addresses 2790 Thomas Heide Clausen 2791 LIX, Ecole Polytechnique 2793 Phone: +33 6 6058 9349 2794 EMail: T.Clausen@computer.org 2795 URI: http://www.ThomasClausen.org/ 2796 Christopher Dearlove 2797 BAE Systems ATC 2799 Phone: +44 1245 242194 2800 EMail: chris.dearlove@baesystems.com 2801 URI: http://www.baesystems.com/ 2803 Justin W. Dean 2804 Naval Research Laboratory 2806 Phone: +1 202 767 3397 2807 EMail: jdean@itd.nrl.navy.mil 2808 URI: http://pf.itd.nrl.navy.mil/ 2810 The OLSRv2 Design Team 2811 MANET Working Group