idnits 2.17.1 draft-ietf-manet-nhdp-09.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 958 has weird spacing: '...dr_list is an...' == Line 961 has weird spacing: '...I_manet is a ...' == Line 980 has weird spacing: '...ce_addr is a ...' == Line 983 has weird spacing: '...IR_time speci...' == Line 1017 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 26, 2009) is 5503 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 27, 2009 BAE Systems ATC 6 J. Dean 7 Naval Research Laboratory 8 The OLSRv2 Design Team 9 MANET Working Group 10 March 26, 2009 12 MANET Neighborhood Discovery Protocol (NHDP) 13 draft-ietf-manet-nhdp-09 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 27, 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 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 9 70 4.1. Routers and Interfaces . . . . . . . . . . . . . . . . . . 11 71 4.2. Information Base Overview . . . . . . . . . . . . . . . . 11 72 4.2.1. Local Information Base . . . . . . . . . . . . . . . . 11 73 4.2.2. Interface Information Bases . . . . . . . . . . . . . 12 74 4.2.3. Neighbor Information Base . . . . . . . . . . . . . . 13 75 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 13 76 4.3.1. HELLO Message Generation . . . . . . . . . . . . . . . 14 77 4.3.2. HELLO Message Content . . . . . . . . . . . . . . . . 14 78 4.3.3. HELLO Message Processing . . . . . . . . . . . . . . . 15 79 4.4. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 15 80 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 16 81 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 16 82 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 16 83 5.3. Interface Parameters . . . . . . . . . . . . . . . . . . . 16 84 5.3.1. Message Intervals . . . . . . . . . . . . . . . . . . 16 85 5.3.2. Information Validity Times . . . . . . . . . . . . . . 18 86 5.3.3. Link Quality . . . . . . . . . . . . . . . . . . . . . 18 87 5.3.4. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 19 88 5.4. Router Parameters . . . . . . . . . . . . . . . . . . . . 19 89 5.4.1. Information Validity Time . . . . . . . . . . . . . . 19 90 5.5. Parameter Change Constraints . . . . . . . . . . . . . . . 20 91 5.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 21 92 6. Local Information Base . . . . . . . . . . . . . . . . . . . . 21 93 6.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 21 94 6.2. Removed Interface Address Set . . . . . . . . . . . . . . 22 95 7. Interface Information Base . . . . . . . . . . . . . . . . . . 22 96 7.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 23 97 7.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 24 98 8. Neighbor Information Base . . . . . . . . . . . . . . . . . . 24 99 8.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . 24 100 8.2. Lost Neighbor Set . . . . . . . . . . . . . . . . . . . . 25 101 9. Local Information Base Changes . . . . . . . . . . . . . . . . 25 102 9.1. Adding an Interface . . . . . . . . . . . . . . . . . . . 25 103 9.2. Removing an Interface . . . . . . . . . . . . . . . . . . 26 104 9.3. Adding an Address to an Interface . . . . . . . . . . . . 27 105 9.4. Removing an Address from an Interface . . . . . . . . . . 27 106 10. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 28 107 10.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 29 108 10.1.1. Address Blocks . . . . . . . . . . . . . . . . . . . . 29 109 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 30 110 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 31 111 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 33 112 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 33 113 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 33 114 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 34 115 12.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 35 116 12.3. Updating the Neighbor Set . . . . . . . . . . . . . . . . 36 117 12.4. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 37 118 12.5. Updating the Link Set . . . . . . . . . . . . . . . . . . 37 119 12.6. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 39 120 13. Other Information Base Changes . . . . . . . . . . . . . . . . 40 121 13.1. Link Tuple Symmetric . . . . . . . . . . . . . . . . . . . 41 122 13.2. Link Tuple Not Symmetric . . . . . . . . . . . . . . . . . 41 123 13.3. Link Tuple Heard Timeout . . . . . . . . . . . . . . . . . 42 124 14. Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . 43 125 14.1. Deployment Without Link Quality . . . . . . . . . . . . . 43 126 14.2. Basic Principles of Link Quality . . . . . . . . . . . . . 43 127 14.3. When Link Quality Changes . . . . . . . . . . . . . . . . 44 128 14.4. Updating Link Quality . . . . . . . . . . . . . . . . . . 45 129 15. Proposed Values for Parameters and Constants . . . . . . . . . 46 130 15.1. Message Interval Interface Parameters . . . . . . . . . . 46 131 15.2. Information Validity Time Interface Parameters . . . . . . 46 132 15.3. Information Validity Time Router Parameters . . . . . . . 46 133 15.4. Link Quality Interface Parameters . . . . . . . . . . . . 46 134 15.5. Jitter Interface Parameters . . . . . . . . . . . . . . . 46 135 15.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 47 136 16. Usage with Other Protocols . . . . . . . . . . . . . . . . . . 47 137 17. Security Considerations . . . . . . . . . . . . . . . . . . . 48 138 17.1. Invalid HELLO messages . . . . . . . . . . . . . . . . . . 48 139 17.2. Authentication, Integrity and Confidentiality 140 Suggestions . . . . . . . . . . . . . . . . . . . . . . . 49 141 18. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 50 142 18.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 50 143 18.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 50 144 18.3. Message-Type-specific TLV Type Registries . . . . . . . . 50 145 18.4. Address Block TLV Types . . . . . . . . . . . . . . . . . 51 146 18.5. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 52 147 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 53 148 20. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 53 149 21. References . . . . . . . . . . . . . . . . . . . . . . . . . . 53 150 21.1. Normative References . . . . . . . . . . . . . . . . . . . 53 151 21.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 a 161 local exchange of HELLO messages in order that each router can 162 determine the presence of, and connectivity to, its 1-hop and 163 symmetric 2-hop neighbors. Messages are defined according to the 164 specification [RFC5444]. 166 1-hop and symmetric 2-hop neighborhood information is recorded in the 167 form of Information Bases. These are available for use by other 168 protocols, such as MANET routing protocols, which require information 169 regarding the local network connectivity. This protocol is designed 170 to maintain the information in these Information Bases even in the 171 presence of a dynamic network topology and wireless communication 172 channel characteristics. 174 This protocol makes no assumptions about the underlying link layer, 175 other than support of 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 communication channels (e.g., wireless, lossy, 187 broadcast channels with moderate and shared bandwidth, hidden and 188 exposed terminals and interference from other network devices and the 189 environment) and in more challenging topological conditions (e.g., 190 rapid and unpredictable mobility, dynamic and non-predetermined 191 network membership). 193 Due to the properties of wireless transmissions, communication 194 between two neighboring routers may not be bidirectional; even if 195 router A is able to receive packets from router B, the converse is 196 not guaranteed to be true. Furthermore, because of the localized 197 nature of wireless broadcast communication, neighboring routers 198 within the same communications channel may have different sets of 199 neighbors. That is, when using the same communication channel, even 200 if router A is able to exchange packets with router B and router B is 201 able to exchange packets with router C, then this does not guarantee 202 that router A and router C can exchange packets directly. 204 Each router in a MANET may use more than one communication channel. 206 In particular, between the same pair of routers, more than one 207 distinct communication channel may exist, each with different 208 properties. 210 For use by MANET routing protocols, as well as establishing a 211 router's neighbors, a router may also need to determine whether each 212 communication channel with that neighbor is bidirectional. 214 The set of neighbor routers of a given MANET router may be 215 continuously changing, often due to router mobility or a changing 216 physical environment in which the MANET is located. There is 217 typically no information from lower layers which would enable an IP 218 routing protocol to detect and, as appropriate, react to such 219 changes. Such changes can often take place on a short timescale, 220 such as of the order of seconds, requiring MANET routing protocols to 221 act rapidly to ensure suitable convergence properties. 223 MANET routing protocols, for example [RFC3626] and [RFC5449], often 224 employ relay set reductions in order to conserve network capacity 225 when maintaining network-wide topological information, with 226 calculation of these reduced relay sets employing up to two hop 227 information. 229 The neighborhood discovery protocol specified in this document 230 provides continued tracking of neighborhood changes, link 231 bidirectionality, and local topological information up to two hops. 232 Combined, this allows a MANET routing protocol access to information 233 describing link establishment/disappearance, and provides the 234 necessary topological information for reduced relay set selection and 235 other purposes. 237 2. Terminology 239 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 240 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 241 "OPTIONAL" in this document are to be interpreted as described in 242 [RFC2119]. 244 All terms introduced in [RFC5444], including "packet", "message", 245 "Address Block", "TLV Block" and "TLV", are to be interpreted as 246 described there. 248 Additionally, this document uses the following terminology: 250 Router - A MANET router which implements this neighborhood discovery 251 protocol. 253 Interface - A network device, configured and assigned one or more 254 addresses. 256 Address - An IPv4 or IPv6 address, as assigned to an interface. It 257 corresponds to an address as specified in [RFC5444], and may be 258 either an address or an address prefix. An address without a 259 prefix length is considered to have a prefix length equal to its 260 length (in bits). 262 Origionator address - An address identifying a router, as specified 263 in [RFC5444]; it is a simple address without a prefix length. 265 MANET interface - An interface participating in a MANET and using 266 this neighborhood discovery protocol. A router may have several 267 MANET interfaces. 269 Heard - A MANET interface of router X is considered heard on a MANET 270 interface of a router Y if the latter can receive traffic from the 271 former. 273 Link - A link between two MANET interfaces exists if either can be 274 heard by the other. 276 Symmetric link - A symmetric link between two MANET interfaces 277 exists if both can be heard by the other. 279 1-hop neighbor - A router X is a 1-hop neighbor of a router Y if a 280 MANET interface of router X is heard by a MANET interface of 281 router Y. 283 Symmetric 1-hop neighbor - A router X is a symmetric 1-hop neighbor 284 of a router Y if a symmetric link exists between a MANET interface 285 on router X and a MANET interface on router Y. 287 2-hop neighbor - A router X is a 2-hop neighbor of a router Y if 288 router X is a 1-hop neighbor of a 1-hop neighbor of router Y, but 289 is not router Y itself. 291 Symmetric 2-hop neighbor - A router X is a symmetric 2-hop neighbor 292 of a router Y if router X is a symmetric 1-hop neighbor of a 293 symmetric 1-hop neighbor of router Y, but is not router Y itself. 295 1-hop neighborhood - The 1-hop neighborhood of a router X is the set 296 of the 1-hop neighbors of router X. 298 Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a 299 router X is the set of the symmetric 1-hop neighbors of router X. 301 2-hop neighborhood - The 2-hop neighborhood of a router X is the set 302 of the 2-hop neighbors of router X. (This may include routers in 303 the 1-hop neighborhood 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 numerical value which MUST be the same for all MANET 311 interfaces of all routers in the MANET, at all times. 313 Interface parameter - A boolean or numerical value, specified 314 separately for each MANET interface of each router. A router MAY 315 change interface parameter values at any time, subject to some 316 constraints. 318 Router parameter - A boolean or numerical value, specified for each 319 router, and not specific to an interface. A router MAY change 320 router parameter values at any time, subject to some constraints. 322 Information Base - A collection of information maintained by this 323 protocol, and which is to be made available to MANET routing 324 protocols. An Information Base may be associated with a MANET 325 interface, or with a router. 327 Furthermore, this document uses the following notational conventions: 329 X contains y, or y is contained in X, is an unordered list 330 membership operator, returning true if the unordered list X 331 includes the element y, and returning false otherwise. 333 X contains Y, or Y is contained in X, is an unordered list inclusion 334 operator, returning true if the unordered list X contains all 335 elements y which are contained in Y, and returning false 336 otherwise. 338 a := b is an assignment operator, whereby the left side (a) is 339 assigned the value of the right side (b). a and b may be values, 340 addresses, or unordered lists (they must be of the same type). 342 c = d is a comparison operator, returning true if the value of the 343 left side (c) is equal to the value of the right side (d). c and d 344 may be values, addresses, or unordered lists (they must be of the 345 same type). If c and d are unordered lists, then they are 346 considered to be equal if they contain the same set of elements, 347 regardless of the order in which they are recorded in either list 348 (in which case c is contains d, and d contains c). If c and d are 349 addresses, they are considered equal only if their prefix lengths 350 are also equal. 352 e != f is a comparison operator, returning true where (e = f) would 353 have returned false, and returning false where (e = f) would have 354 returned true. 356 3. Applicability Statement 358 This protocol: 360 o Is applicable to networks, especially wireless networks, in which 361 unknown neighbors can be reached by local broadcast or multicast 362 packets. 364 o Is designed to work in networks with a dynamic topology, and in 365 which messages may be lost, such as due to collisions in wireless 366 networks. 368 o Supports routers that each have one or more participating MANET 369 interfaces. The set of a router's interfaces may change over 370 time. Each interface may have one or more interface addresses, 371 and these may also be dynamically changing. 373 o Provides each router with current local topology information up to 374 two hops away, and makes this local topology information available 375 to MANET routing protocols in Information Bases. 377 o Uses the packet and message formats specified in [RFC5444]. This 378 includes the definition of a HELLO Message Type, used for 379 signalling local topology information. 381 o May interact with, and be extended by, other protocols, such as 382 MANET routing protocols, see Section 16. 384 o Can use relevant link layer information if it is available. 386 o Is designed to work in a completely distributed manner, and does 387 not depend on any central entity. 389 4. Protocol Overview and Functioning 391 The objective of this protocol is, for each router: 393 o To identify 1-hop neighbors and symmetric 1-hop neighbors of this 394 router. 396 o To find the interface addresses of the router's symmetric 2-hop 397 neighbors. 399 o To record this information in Information Bases that can be used 400 by other protocols, of which this neighborhood discovery protocol 401 may be a part. 403 These objectives are achieved using local (1-hop) signaling that: 405 o Advertises the presence of a router and its interface addresses. 407 o Discovers links from neighboring routers. 409 o Performs bidirectionality checks on the discovered links. 411 o Advertises discovered links, and whether each is symmetric, to its 412 1-hop neighbors, and hence discovers symmetric 2-hop neighbors. 414 This specification defines, in turn: 416 o Parameters and constants used by the protocol. Parameters used by 417 this protocol may be, where appropriate, specific to a given MANET 418 interface, or to a MANET router. This protocol allows all 419 parameters to be changed dynamically, and to be set independently 420 for each MANET router or MANET interface, as appropriate. 422 o The Information Bases describing local interfaces, discovered 423 links and their status, current and former 1-hop neighbors, and 424 symmetric 2-hop neighbors. 426 o The format of the HELLO message that is used for local signaling. 428 o The generation of HELLO messages from some of the information in 429 the Information Bases. 431 o The updating of the Information Bases according to received HELLO 432 messages and other events. 434 o The response to other events, such as the expiration of 435 information in the Information Bases. 437 4.1. Routers and Interfaces 439 In order for a router to participate in a MANET, it MUST have at 440 least one, and possibly more, MANET interfaces. Each MANET 441 interface: 443 o Is configured with one or more addresses. These addresses MUST be 444 unique within the router's 2-hop neighborhood. 446 o Has a set of interface parameters, defining the behavior of this 447 MANET interface. Each MANET interface MAY be individually 448 parameterized. 450 o Has an Interface Information Base, recording information regarding 451 links to this MANET interface and symmetric 2-hop neighbors which 452 can be reached through such links. 454 o Generates and processes HELLO messages. 456 In addition to a set of MANET interfaces as described above, each 457 router has: 459 o A Local Information Base, containing the addresses of the 460 interfaces (MANET and non-MANET) of this router. The contents of 461 this Information Base are not changed by signaling. 463 o A Neighbor Information Base, recording information regarding 464 current and recently lost 1-hop neighbors of this router. 466 A router may have both MANET interfaces and non-MANET interfaces. 467 Interfaces of both of these types are recorded in a router's Local 468 Information Base, which is used, but not updated, by the signaling of 469 this protocol. 471 4.2. Information Base Overview 473 Each router maintains the Information Bases described in the 474 following sections. These are used for describing the protocol in 475 this document. An implementation of this protocol MAY maintain this 476 information in the indicated form, or in any other organization which 477 offers access to this information. In particular note that it is not 478 necessary to remove Tuples from Sets at the exact time indicated, 479 only to behave as if the Tuples were removed at that time. 481 4.2.1. Local Information Base 483 Each router maintains a Local Information Base, which contains the 484 router's local configuration information, specifically: 486 o The Local Interface Set, which consists of Local Interface Tuples, 487 each of which represents an interface (MANET or non-MANET) of the 488 router. 490 o The Removed Interface Address Set, which consists of Removed 491 Interface Address Tuples, each of which records a recently used 492 address of an interface (MANET or non-MANET) of the router. 494 The Local Interface Set is used for generating HELLO messages, 495 specifically for determining which interface addresses are to be 496 included and identified as local interfaces. The Removed Interface 497 Address Set is used to avoid incorrectly recording a formerly used 498 address as a symmetric 2-hop neighbor's address. 500 The Local Information Base is used for generating signaling, but is 501 not itself updated by signaling specified in this document. Updates 502 to the Local Information Base are due to changes of the router 503 configuration, and may be allowed to trigger signaling. 505 4.2.2. Interface Information Bases 507 Each router maintains, for each of its MANET interfaces, an Interface 508 Information Base, which contains 1-hop neighborhood and symmetric 509 2-hop neighborhood information collected from this MANET interface, 510 specifically: 512 o A Link Set, which records information about current and recently 513 lost links between this MANET interface and MANET interfaces of 514 1-hop neighbors. The Link Set consists of Link Tuples, each of 515 which contains information about a single link. Link quality 516 information (see Section 14), when used, is recorded in Link 517 Tuples. 519 o A 2-Hop Set, which records the existence of symmetric links 520 between symmetric 1-hop neighbors of this MANET interface and 521 other routers (symmetric 2-hop neighbors). The 2-Hop Set consists 522 of 2-Hop Tuples, each of which records an address of a symmetric 523 2-hop neighbor, and all addresses of the corresponding symmetric 524 1-hop neighbor. 526 The Link Set for a MANET interface is used for generating HELLO 527 messages. Specifically, the Link Set information is included to both 528 allow other routers to identify symmetric links and to populate the 529 2-Hop Set. Recently lost links are recorded in the Link Set for a 530 MANET interface so that they can be advertised in HELLO messages, 531 accelerating their removal from relevant 1-hop neighbors' Link Sets. 533 The Link Set for a MANET interface is itself updated on receiving a 534 HELLO message, including recording symmetric links as indicated 535 above. The 2-Hop Set for a MANET interface is updated as indicated 536 above, and is not itself used in generating HELLO messages. 538 4.2.3. Neighbor Information Base 540 Each router maintains a Neighbor Information Base, which contains 541 collected information about current and recently lost 1-hop 542 neighbors, specifically: 544 o The Neighbor Set consists of Neighbor Tuples, each of which 545 records all addresses of a single 1-hop neighbor. Neighbor Tuples 546 are maintained as long as there are corresponding Link Tuples. 548 o The Lost Neighbor Set consists of Lost Neighbor Tuples, each of 549 which records an address of a recently lost symmetric 1-hop 550 neighbor. 552 The Neighbor Set associates all addresses of each 1-hop neighbor. 553 These addresses may be included when generating a HELLO message, so 554 that other symmetric 1-hop neighbors can record this information in a 555 2-Hop Set. The Neighbor Set can be updated on receiving a HELLO 556 message. 558 The Lost Neighbor Set is used to determine which addresses are to be 559 included in a HELLO message as being lost (of a recently symmetric 560 1-hop neighbor). The Lost Neighbor Set can itself be updated on 561 receiving a HELLO message. 563 4.3. Signaling Overview 565 This protocol contains a signaling mechanism for maintaining the 566 Interface Information Bases and the Neighbor Information Base. If 567 information from the link layer, or any other source, is available 568 and appropriate, it may also be used to update these Information 569 Bases. Such updates are subject to the constraints specified in 570 Appendix B. 572 Signaling consists of a single type of message, known as a HELLO 573 message. Each router generates HELLO messages on each of its MANET 574 interfaces. HELLO messages are generated independently on each MANET 575 interface of a MANET router; the content of a given HELLO message 576 depends on the MANET interface for which it has been generated. 578 Each HELLO message identifies the MANET interface for which it is 579 generated and transmitted; this allows recipients to identify that 580 MANET interface. Each HELLO message also reports the other 581 interfaces (MANET and non-MANET) of the router; this allows 582 recipients to associate a set of addresses with a single 1-hop 583 neighbor. Each HELLO message also includes 1-hop neighbor 584 information from the Information Bases; this allows detection of 585 local symmetric links, and symmetric 2-hop neighbors. 587 4.3.1. HELLO Message Generation 589 HELLO messages are generated by a router for each of its MANET 590 interfaces, and MAY be sent: 592 o Proactively, at a regular interval, known as HELLO_INTERVAL. 593 HELLO_INTERVAL may be fixed, or may be dynamic. For example 594 HELLO_INTERVAL may be backed off due to congestion or network 595 stability. 597 o As a response to a change in the router itself, or its 1-hop 598 neighborhood, for example on first becoming active or in response 599 to a new, lost, or changed status link. 601 o In a combination of these proactive and responsive mechanisms. 603 Jittering of HELLO message generation and transmission, as described 604 in Section 11.2, SHOULD be used if appropriate. 606 HELLO messages MAY be scheduled independently for each MANET 607 interface, or, interface parameters permitting, using the same 608 schedule for all MANET interfaces of a router. 610 4.3.2. HELLO Message Content 612 The content of a HELLO message MUST satisfy the following: 614 o A HELLO message MUST contain all of the addresses in the Local 615 Interface Set of the router to which the MANET interface belongs. 617 o For each MANET interface, within every time interval equal to the 618 corresponding REFRESH_INTERVAL, the HELLO messages sent MUST 619 collectively include all of the relevant information in the 620 corresponding Link Set and the Neighbor Information Base. Note 621 that when determining whether to include information in a HELLO 622 message, the sender MUST consider all times up to the latest time 623 when it may send its next HELLO message on this MANET interface. 625 o A HELLO message MUST include exactly one VALIDITY_TIME Message 626 TLV, as specified in [RFC5497], that indicates the length of time 627 for which the message content is to be considered valid, and is 628 therefore to be included in the receiving router's Interface 629 Information Base. 631 o A periodically generated HELLO message SHOULD include exactly one 632 INTERVAL_TIME Message TLV, as specified in [RFC5497], that 633 indicates the current value of HELLO_INTERVAL for that MANET 634 interface, i.e. the period within which a further HELLO message is 635 guaranteed to be sent on that MANET interface. 637 4.3.3. HELLO Message Processing 639 HELLO messages received by a router are used to update the Interface 640 Information Base for the MANET interface on which that HELLO message 641 is received and the Neighbor Information Base. Specifically: 643 o The router ensures that there is a single Neighbor Tuple 644 corresponding to the originator of that HELLO message. 646 o The router ensures that there is a Link Tuple, with appropriate 647 status (heard or symmetric) and advertised duration, corresponding 648 to the link between the MANET interfaces on which that HELLO 649 message was sent and received. One or more Lost Neighbor Tuples 650 may be created if the HELLO message reports that the link was 651 lost. 653 o If the link between the MANET interfaces on which the HELLO 654 message was sent and received is symmetric, then the router 655 ensures that there are the appropriate 2-Hop Tuples, with 656 advertised duration. 658 The processing defined in this specification handles any unexpected 659 and erroneous information in a HELLO message, maintaining the 660 constraints on Information Base contents specified in Appendix B. 662 4.4. Link Quality 664 Some links in a MANET may be marginal, e.g., due to adverse wireless 665 propagation. In order to avoid using such marginal links, a link 666 quality value is recorded in each Link Tuple. A MANET router 667 considers links for which an insufficient link quality is recorded as 668 lost. Modifying the recorded link quality in a Link Tuple is 669 OPTIONAL. If link quality is not to be modified it MUST be set to 670 indicate an always usable quality link. 672 Link quality information is only used locally and is not used in 673 signaling. Routers may interoperate whether they are using the same, 674 different, or no, link quality information. Link quality information 675 is thus not equivalent to a link metric. 677 5. Protocol Parameters and Constants 679 The parameters and constants used in this specification are described 680 in this section. 682 5.1. Protocol and Port Numbers 684 This protocol specifies HELLO messages, which are included in packets 685 as defined by [RFC5444]. These packets may be sent either using the 686 "manet" protocol number or the "manet" well-known UDP port number, as 687 specified in [RFC5498]. 689 5.2. Multicast Address 691 This protocol specifies HELLO messages, which are included in packets 692 as defined by [RFC5444]. These packets may be locally transmitted 693 using the link local multicast address "LL-MANET-Routers", as 694 specified in [RFC5498]. 696 5.3. Interface Parameters 698 The interface parameters used by this specification may be classified 699 into the following four categories: 701 o Message intervals 703 o Information validity times 705 o Link quality 707 o Jitter 709 These are detailed in the following sections. 711 Different MANET interfaces (on the same or on different routers) MAY 712 employ different interface parameter values, and MAY change their 713 interface parameter values dynamically, subject to the constraints 714 given in this section. A particular case is where all MANET 715 interfaces on all MANET routers within a given MANET employ the same 716 set of interface parameter values. 718 5.3.1. Message Intervals 720 HELLO messages serve two principal functions: 722 o To advertise this router's interface addresses to its 1-hop 723 neighbors. The frequency of these advertisements is regulated by 724 the interface parameters HELLO_INTERVAL and HELLO_MIN_INTERVAL. 726 o To advertise this router's knowledge of each of its 1-hop 727 neighbors. The frequency of the advertisement of each such 728 neighbor is regulated by the interface parameter REFRESH_INTERVAL. 730 Specifically, these parameters are as follows: 732 HELLO_INTERVAL - is the maximum time between the transmission of two 733 successive HELLO messages on this MANET interface. If using 734 periodic transmission of HELLO messages, these SHOULD be at a 735 separation of HELLO_INTERVAL, possibly modified by jitter as 736 specified in [RFC5148]. 738 HELLO_MIN_INTERVAL - is the minimum interval between transmission of 739 two successive HELLO messages, on this MANET interface. (This 740 minimum interval MAY be modified by jitter, as defined in 741 [RFC5148].) 743 REFRESH_INTERVAL - is the maximum interval between advertisements in 744 a HELLO message of each 1-hop neighbor address and its status. In 745 all intervals of length REFRESH_INTERVAL, a router MUST include 746 each 1-hop neighbor address and its status in at least one HELLO 747 message on this MANET interface. (This may be in the same or in 748 different HELLO messages.) 750 The following constraints apply to these interface parameters: 752 o HELLO_INTERVAL > 0 754 o HELLO_MIN_INTERVAL >= 0 756 o HELLO_INTERVAL >= HELLO_MIN_INTERVAL 758 o REFRESH_INTERVAL >= HELLO_INTERVAL 760 o If an INTERVAL_TIME Message TLV as defined in [RFC5497] is 761 included in a HELLO messages, then HELLO_INTERVAL MUST be 762 representable as described in [RFC5497]. 764 If REFRESH_INTERVAL > HELLO_INTERVAL, then a router may distribute 765 its neighbor advertisements between HELLO messages in any manner, 766 subject to the constraints above. 768 For a router to employ this protocol in a purely responsive manner on 769 a MANET interface, REFRESH_INTERVAL and HELLO_INTERVAL SHOULD both be 770 set to a value such that a responsive HELLO message is always 771 expected in a shorter period than this value. 773 If a router has more than one MANET interface, then, even if the 774 router configures different values of HELLO_INTERVAL on each MANET 775 interface, the router SHOULD configure the same value of 776 HELLO_MIN_INTERVAL on all MANET interfaces on which responsive HELLO 777 messages may be sent. 779 5.3.2. Information Validity Times 781 The following interface parameters manage the validity time of link 782 information: 784 L_HOLD_TIME - is the period of advertisement, on this MANET 785 interface, of former 1-hop neighbor addresses as lost in HELLO 786 messages, allowing recipients of these HELLO messages to 787 accelerate removal of this information from their Link Sets. 788 L_HOLD_TIME MAY be set to zero, if accelerated information removal 789 is not required. 791 H_HOLD_TIME - is used as the value in the VALIDITY_TIME Message TLV 792 included in all HELLO messages on this MANET interface. 794 The following constraints apply to these interface parameters: 796 o L_HOLD_TIME >= 0 798 o H_HOLD_TIME >= REFRESH_INTERVAL 800 o If HELLO messages can be lost then both parameters SHOULD be 801 significantly greater than REFRESH_INTERVAL. 803 o H_HOLD_TIME MUST be representable as described in [RFC5497]. 805 5.3.3. Link Quality 807 The following interface parameters manage the usage of link quality 808 (see Section 14): 810 HYST_ACCEPT - is the link quality threshold at or above which a link 811 becomes usable, if it was not already so. 813 HYST_REJECT - is the link quality threshold below which a link 814 becomes unusable, if it was not already so. 816 INITIAL_QUALITY - is the initial quality of a newly identified link. 818 INITIAL_PENDING - if true, then a newly identified link is 819 considered pending, and is not usable until the link quality has 820 reached or exceeded the HYST_ACCEPT threshold. 822 The following constraints apply to these interface parameters: 824 o 0 <= HYST_REJECT <= HYST_ACCEPT <= 1 826 o 0 <= INITIAL_QUALITY <= 1. 828 o If link quality is not updated, then INITIAL_QUALITY >= 829 HYST_ACCEPT. 831 o If INITIAL_QUALITY >= HYST_ACCEPT, then INITIAL_PENDING := false. 833 o If INITIAL_QUALITY < HYST_REJECT, then INITIAL_PENDING := true. 835 5.3.4. Jitter 837 If jitter, as defined in [RFC5148], is used then these parameters are 838 as follows: 840 HP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 841 for periodically generated HELLO messages on this MANET interface. 843 HT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 844 for externally triggered HELLO messages on this MANET interface. 846 For constraints on these interface parameters see [RFC5148]. 848 5.4. Router Parameters 850 The two router parameters defined by this specification are in the 851 category of information validity time. 853 5.4.1. Information Validity Time 855 The following router parameter manages the validity time of lost 856 symmetric 1-hop neighbor information: 858 N_HOLD_TIME - is used as the period during which former 1-hop 859 neighbor addresses are advertised as lost in HELLO messages, 860 allowing recipients of these HELLO messages to accelerate removal 861 of this information from their 2-Hop Sets. N_HOLD_TIME MAY be set 862 to zero, if accelerated information removal is not required. 864 I_HOLD_TIME - is the period for which a recently used local 865 interface address is recorded. 867 The following constraints applies to these router parameters: 869 o N_HOLD_TIME >= 0 871 o I_HOLD_TIME >= 0 873 5.5. Parameter Change Constraints 875 If protocol parameters are changed dynamically, the constraints in 876 this section apply. 878 HELLO_INTERVAL 880 * If the HELLO_INTERVAL for a MANET interface increases, then the 881 next HELLO message on this MANET interface MUST be generated 882 according to the previous, shorter, HELLO_INTERVAL. A number 883 of subsequent HELLO messages MAY be generated according to the 884 previous, shorter, HELLO_INTERVAL (but MUST include times 885 according to current parameters). 887 * If the HELLO_INTERVAL for a MANET interface decreases, then the 888 following HELLO messages on this MANET interface MUST be 889 generated according to this current, shorter, HELLO_INTERVAL. 891 REFRESH_INTERVAL 893 * If the REFRESH_INTERVAL for a MANET interface increases, then 894 the content of subsequent HELLO messages must be organized such 895 that the specification of the old value of REFRESH_INTERVAL is 896 satisfied for a further period equal to the old value of 897 REFRESH_INTERVAL. 899 * If the REFRESH_INTERVAL for a MANET interface decreases, then 900 it MAY be necessary to reschedule HELLO message generation on 901 that MANET interface, in order that the specification of 902 REFRESH_INTERVAL is satisfied from the time of change. 904 HYST_ACCEPT and HYST_REJECT 906 * If HYST_ACCEPT or HYST_REJECT changes, then the appropriate 907 actions for link quality change, as specified in Section 14.3, 908 MUST be taken. 910 L_HOLD_TIME 912 * If L_HOLD_TIME changes, then L_time for all relevant Link 913 Tuples MUST be changed. 915 N_HOLD_TIME 917 * If N_HOLD_TIME changes, then NL_time for all relevant Lost 918 Neighbor Tuples MUST be changed. 920 HP_MAXJITTER 922 * If HP_MAXJITTER changes, then the periodic HELLO message 923 schedule on this MANET interface MAY be changed. 925 HT_MAXJITTER 927 * If HT_MAXJITTER changes, then externally triggered HELLO 928 messages on this MANET interface MAY be rescheduled. 930 5.6. Constants 932 The constant C (time granularity) is used as specified in [RFC5497]. 934 6. Local Information Base 936 A router maintains a Local Information Base that records information 937 about its interfaces (MANET and non-MANET). Each interface MUST have 938 at least one address, and MAY have more than one address. 940 The Local Information Base is not modified by signaling. If a 941 router's interface configuration changes, then the Local Information 942 Base MUST reflect these changes. This MAY also result in signaling 943 to advertise these changes. 945 Interfaces and addresses MAY be excluded from the Local Information 946 Base, and hence from HELLO messages, if they are not to be used for 947 routing. 949 6.1. Local Interface Set 951 A router's Local Interface Set records its local interfaces. It 952 consists of Local Interface Tuples, one per interface: 954 (I_local_iface_addr_list, I_manet) 956 where: 958 I_local_iface_addr_list is an unordered list of the addresses of 959 this interface. 961 I_manet is a boolean flag, describing if this interface is a MANET 962 interface. 964 Local Interface Tuples are removed from the Local Interface Set only 965 when the routers' interface configuration changes, subject to 966 Section 9, i.e. they are not subject to timer-based expiration. 968 6.2. Removed Interface Address Set 970 A router's Removed Interface Address Set records addresses which were 971 recently used as local interface addresses. If a router's interface 972 addresses are immutable then the Removed Interface Address Set is 973 always empty and MAY be omitted. It consists of Removed Interface 974 Address Tuples, one per address: 976 (IR_local_iface_addr, IR_time) 978 where: 980 IR_local_iface_addr is a recently used address of an interface of 981 this router. 983 IR_time specifies when this Tuple expires and MUST be removed. 985 7. Interface Information Base 987 A router maintains an Interface Information Base for each of its 988 MANET interfaces. This records information about links to that MANET 989 interface and symmetric 2-hop neighbors which can be reached in two 990 hops using those links as the first hop. The Interface Information 991 Base includes the Link Set and the 2-Hop Set. 993 An address of a symmetric 2-hop neighbor can also be present as the 994 address of a 1-hop neighbor. This allows the router using this 995 address to be immediately considered as a symmetric 2-hop neighbor if 996 it fails to be a symmetric 1-hop neighbor. 998 An element which specifies a time is considered expired if the 999 current time is greater than or equal to that time. One such 1000 element, present in most Tuples, indicates when expired that the 1001 Tuple itself is considered expired and MUST be removed. Tuples which 1002 do not have such a time element are removed at other times as 1003 specified, for example a Neighbor Tuple is removed when all 1004 corresponding Link Tuples have been removed. 1006 7.1. Link Set 1008 A router's Link Set records links from other routers which are, or 1009 recently were, 1-hop neighbors. It consists of Link Tuples, each 1010 representing a single link: 1012 (L_neighbor_iface_addr_list, L_HEARD_time, L_SYM_time, 1013 L_quality, L_pending, L_lost, L_time) 1015 where: 1017 L_neighbor_iface_addr_list is an unordered list of the addresses of 1018 the MANET interface of the 1-hop neighbor; 1020 L_HEARD_time is the time until which the MANET interface of the 1021 1-hop neighbor would be considered heard if not considering link 1022 quality; 1024 L_SYM_time is the time until which the link to the 1-hop neighbor 1025 would be considered symmetric if not considering link quality; 1027 L_quality is a dimensionless number between 0 (inclusive) and 1 1028 (inclusive) describing the quality of a link; a greater value of 1029 L_quality indicating a higher quality link; 1031 L_pending is a boolean flag, describing if a link is considered 1032 pending (i.e. a candidate, but not yet established, link); 1034 L_lost is a boolean flag, describing if a link is considered lost 1035 due to low link quality; 1037 L_time specifies when this Tuple expires and MUST be removed. 1039 The status of the link, as obtained through HELLO message exchange 1040 and using link quality, is denoted L_status. L_status can take the 1041 values PENDING, HEARD, SYMMETRIC and LOST. The values LOST, 1042 SYMMETRIC and HEARD are defined in Section 18.5. The value PENDING 1043 is never used in a HELLO message, it is only used locally by a 1044 router, and any value distinct from LOST, SYMMETRIC and HEARD may be 1045 used. 1047 L_status is defined by: 1049 1. If L_pending = true, then L_status := PENDING; 1051 2. otherwise, if L_lost = true, then L_status := LOST; 1052 3. otherwise, if L_SYM_time is not expired, then L_status := 1053 SYMMETRIC; 1055 4. otherwise, if L_HEARD_time is not expired, then L_status := 1056 HEARD; 1058 5. otherwise, L_status := LOST. 1060 7.2. 2-Hop Set 1062 A router's 2-Hop Set records addresses of symmetric 2-hop neighbors, 1063 and the symmetric links to symmetric 1-hop neighbors through which 1064 these symmetric 2-hop neighbors can be reached. It consists of 2-Hop 1065 Tuples, each representing a single address of a symmetric 2-hop 1066 neighbor, and a single MANET interface of a symmetric 1-hop neighbor. 1068 (N2_neighbor_iface_addr_list, N2_2hop_iface_addr, N2_time) 1070 where: 1072 N2_neighbor_iface_addr_list is an unordered list of the addresses of 1073 the MANET interface of the symmetric 1-hop neighbor from which 1074 this information was received; 1076 N2_2hop_iface_addr is an address of a symmetric 2-hop neighbor which 1077 has a symmetric link (using any MANET interface) to the indicated 1078 symmetric 1-hop neighbor; 1080 N2_time specifies when this Tuple expires and MUST be removed. 1082 8. Neighbor Information Base 1084 Each router maintains a Neighbor Information Base that records 1085 information about addresses of current and recently symmetric 1-hop 1086 neighbors. 1088 8.1. Neighbor Set 1090 A router's Neighbor Set records all addresses of each 1-hop neighbor. 1091 It consists of Neighbor Tuples, each representing a single 1-hop 1092 neighbor: 1094 (N_neighbor_iface_addr_list, N_symmetric) 1096 where: 1098 N_neighbor_iface_addr_list is an unordered list of the addresses of 1099 a 1-hop neighbor; 1101 N_symmetric is a boolean flag, describing if this is a symmetric 1102 1-hop neighbor. 1104 Neighbor Tuples are removed from the Neighbor Set only when 1105 corresponding Link Tuples expire from the routers' Link Set, i.e. 1106 Neighbor Tuples are not directly subject to timer-based expiration. 1108 8.2. Lost Neighbor Set 1110 A router's Lost Neighbor Set records addresses of routers which 1111 recently were symmetric 1-hop neighbors, but are now advertised as 1112 lost. It consists of Lost Neighbor Tuples, each representing a 1113 single such address: 1115 (NL_neighbor_iface_addr, NL_time) 1117 where: 1119 NL_neighbor_iface_addr is an address of a router which recently was 1120 a symmetric 1-hop neighbor of this router; 1122 NL_time specifies when this Tuple expires and MUST be removed. 1124 9. Local Information Base Changes 1126 The Local Information Base MUST change to respond to changes in the 1127 router's local interface configuration. The router MUST update its 1128 Interface Information Base and Neighbor Information Base in response 1129 to such changes. If any changes in the Interface Information Base or 1130 the Neighbor Information Base satisfy any of the conditions described 1131 in Section 13, then those changes must be applied immediately, unless 1132 noted otherwise. 1134 A router MAY transmit HELLO messages in response to these changes. 1136 9.1. Adding an Interface 1138 If an interface is added to the router then this is indicated by the 1139 addition of a Local Interface Tuple to the Local Interface Set. If 1140 the new interface is a MANET interface then an initially empty 1141 Interface Information Base MUST be created for this new MANET 1142 interface. The actions in Section 9.3 MUST be taken for each address 1143 of this added interface. A HELLO message MAY be sent on all MANET 1144 interfaces, it SHOULD be sent on the new interface if it is a MANET 1145 interface. If using scheduled messages, then a message schedule MUST 1146 be established on the new MANET interface. 1148 9.2. Removing an Interface 1150 If an interface is removed from the router, then this MUST result in 1151 changes to the Local Information Base and to the Neighbor Information 1152 Base as follows: 1154 1. Identify the Local Interface Tuple that corresponds to the 1155 interface to be removed. 1157 2. For each address (henceforth removed address) in the 1158 I_local_iface_addr_list of that Local Interface Tuple, create a 1159 Removed Interface Address Tuple with: 1161 * IR_local_iface_addr := removed address; 1163 * IR_time := current time + I_HOLD_TIME. 1165 3. Remove that Local Interface Tuple from the Local Interface Set. 1167 4. If the interface to be removed is a MANET interface (i.e. with 1168 I_manet = true) then: 1170 1. Remove the Interface Information Base for that MANET 1171 interface; 1173 2. All Neighbor Tuples for which none of the addresses in its 1174 N_neighbor_iface_addr_list are contained in any 1175 L_neighbor_iface_addr_list in any remaining Link Set, are 1176 removed. 1178 If a router removes the Local Interface Tuple that contains the 1179 address which is used to define the router's originator address, as 1180 defined in [RFC5444], then the router MAY change originator address. 1181 If this address may now be used by another router (e.g., if the 1182 address was taken from a prefix no longer delegated to this router, 1183 or if the address was assigned with an expiration timer, and not 1184 renewed before expiration) then this router MUST change its 1185 originator address. 1187 If the removed interface is the last MANET interface of the router, 1188 then there will be no remaining Interface Information Bases, and the 1189 router will longer participate in this protocol. 1191 After removing the interface and making these changes, a HELLO 1192 message MAY be sent on all remaining MANET interfaces. 1194 9.3. Adding an Address to an Interface 1196 If an address is added to an interface then this is indicated by the 1197 addition of an address to the appropriate I_local_iface_addr_list. 1198 The following changes MUST be made to the Information Bases: 1200 1. The Neighbor Tuples, if any, whose N_neighbor_iface_addr_list 1201 contains the added address, are removed. 1203 2. Any Link Tuples, in any Link Set, whose 1204 L_neighbor_iface_addr_list contains: 1206 * the added address; OR 1208 * any address in the N_neighbor_iface_addr_list of any removed 1209 Neighbor Tuple 1211 are removed; apply Section 13.2, but not Section 13.3. 1213 3. Any Lost Neighbor Tuples whose NL_neighbor_iface_addr = the added 1214 address, are removed. 1216 4. Any 2-Hop Tuples whose N2_2hop_iface_addr = the added address, 1217 are removed. 1219 After adding the address and making these changes, a HELLO message 1220 MAY be sent on all MANET interfaces. 1222 These changes, other than to the appropriate I_local_iface_addr_list, 1223 are made in order to maintain consistency of the Information Bases. 1224 Specifically, these changes remove any record of any use of this 1225 address by routers in the 1-hop neighborhood or in the symmetric 1226 2-hop neighborhood of this router. 1228 9.4. Removing an Address from an Interface 1230 If an address (henceforth removed address) is removed from an 1231 interface then: 1233 1. Identify the Local Interface Tuple that corresponds to the 1234 address to be removed. 1236 2. If this is the only address of that interface (the only address 1237 in the corresponding I_local_iface_addr_list) then remove that 1238 interface as specified in Section 9.2. 1240 3. Otherwise: 1242 1. Remove the removed address from this I_local_iface_addr_list. 1244 2. Create a Removed Interface Address Tuple with: 1246 + IR_local_iface_addr := removed address; 1248 + IR_time := current time + I_HOLD_TIME. 1250 If a router removes the address that is used to define the router's 1251 originator address, as defined in [RFC5444], then the router MAY 1252 change originator address. If this address may now be used by 1253 another router (e.g., if the address was taken from a prefix no 1254 longer delegated to this router, or if the address was assigned with 1255 an expiration timer, and not renewed before expiration) then this 1256 router MUST change its originator address. 1258 After removing the address and making these changes, a HELLO message 1259 MAY be sent on all MANET interfaces. 1261 10. Packets and Messages 1263 The packet and message format used by this protocol is defined in 1264 [RFC5444], which is used with the following considerations: 1266 o This protocol specifies one Message Type, the HELLO message. 1268 o A HELLO message MAY use any combination of Message Header options. 1270 o HELLO messages MUST NOT be forwarded. 1272 o HELLO messages MAY be included in multi-message packets as 1273 specified in [RFC5444]. 1275 o Received HELLO messages MUST be parsed in accordance with 1276 [RFC5444]. A HELLO message which is not in conformance with 1277 [RFC5444] MUST be discarded. A HELLO message may also be 1278 discarded for other reasons, see Section 12.1. 1280 o This protocol specifies three Address Block TLVs. It also uses 1281 two Message TLVs defined in [RFC5497]. These five TLV Types are 1282 all defined only with Type Extension = 0. TLVs of other types, 1283 and of these types but without Type Extension = 0, are ignored by 1284 this protocol. All references in this specification to, for 1285 example, an Address Block TLV with Type = LINK_STATUS, are to be 1286 considered as referring to an Address Block TLV with Type = 1287 LINK_STATUS and Type Extension = 0. 1289 10.1. HELLO Messages 1291 A HELLO message MUST contain: 1293 o Exactly one VALIDITY_TIME Message TLV as specified in [RFC5497], 1294 representing H_HOLD_TIME for the transmitting MANET interface. 1295 The options included in [RFC5497] for representing zero and 1296 infinite times MUST NOT be used. 1298 A HELLO message which is transmitted periodically SHOULD contain, and 1299 otherwise MAY contain: 1301 o Exactly one INTERVAL_TIME Message TLV as specified in [RFC5497], 1302 representing HELLO_INTERVAL for the transmitting MANET interface. 1303 The options included in [RFC5497] for representing zero and 1304 infinite times MUST NOT be used. 1306 A HELLO message MAY contain: 1308 o Other Message TLVs. 1310 o One or more Address Blocks, each with an associated Address Block 1311 TLV Block, which MAY contain other Address Block TLVs. 1313 10.1.1. Address Blocks 1315 All addresses in a router's Local Interface Set (i.e. in any 1316 I_local_iface_addr_list) MUST be included in the Address Blocks in 1317 all generated HELLO messages with the following exception. If the 1318 MANET interface on which the HELLO message is to be sent has a single 1319 address with maximum prefix length, then that address MAY be omitted 1320 from being included in any Address Block, provided that this address 1321 is included as the sending address of the IP datagram in which the 1322 HELLO message is included. All addresses of the router's interfaces 1323 included in an Address Block MUST be associated with an Address Block 1324 TLV with Type = LOCAL_IF, as defined in Table 1. 1326 +----------+---------+----------------------------------------------+ 1327 | Name | Value | Description | 1328 | | Length | | 1329 +----------+---------+----------------------------------------------+ 1330 | LOCAL_IF | 1 octet | Specifies that the address is an address | 1331 | | | associated with the MANET interface on which | 1332 | | | the message was sent (THIS_IF) or another | 1333 | | | interface of the sending router (OTHER_IF). | 1334 +----------+---------+----------------------------------------------+ 1336 Table 1: LOCAL_IF TLV definition 1338 Address Blocks MAY contain current or recently lost 1-hop neighbors' 1339 addresses, each of which is associated with one or both Address Block 1340 TLVs as described in Table 2. 1342 +--------------+---------+------------------------------------------+ 1343 | Name | Value | Description | 1344 | | Length | | 1345 +--------------+---------+------------------------------------------+ 1346 | LINK_STATUS | 1 octet | Specifies the status of the link from | 1347 | | | the indicated address (LOST, SYMMETRIC | 1348 | | | or HEARD). | 1349 | OTHER_NEIGHB | 1 octet | Specifies that the address is | 1350 | | | (SYMMETRIC) or was (LOST) of an | 1351 | | | interface of a symmetric 1-hop neighbor | 1352 | | | of the router transmitting the HELLO | 1353 | | | message. | 1354 +--------------+---------+------------------------------------------+ 1356 Table 2: LINK_STATUS and OTHER_NEIGHB TLV definition 1358 An Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC or 1359 Value = LOST also performs the function of an Address Block TLV with 1360 Type = OTHER_NEIGHB and the same value. The latter SHOULD NOT also 1361 be included associated with the same address. If an Address Block 1362 TLV with Type = LINK_STATUS and Value = SYMMETRIC is combined with an 1363 Address Block TLV with Type = OTHER_NEIGHB and Value = LOST 1364 associated with the same address, then the latter MUST be ignored, 1365 and SHOULD NOT be included. See Appendix A. 1367 Other addresses MAY be included in Address Blocks, but MUST NOT be 1368 associated with any of the Address Block TLVs specified in this 1369 specification. 1371 11. HELLO Message Generation 1373 Each MANET interface MUST generate HELLO messages according to the 1374 specification in this section. HELLO messages are generated for each 1375 MANET interface independently. HELLO message generation and 1376 scheduling MUST be according to the interface parameters for that 1377 MANET interface, and MAY be independent for each MANET interface or, 1378 interface parameters permitting, MANET interfaces MAY use the same 1379 schedule. 1381 If transmitting periodic HELLO messages then, following a HELLO 1382 message transmission on a MANET interface, another HELLO message MUST 1383 be transmitted on the same MANET interface after an interval not 1384 greater than HELLO_INTERVAL. Two successive HELLO message 1385 transmissions on the same MANET interface MUST be separated by at 1386 least HELLO_MIN_INTERVAL, except as noted in Section 11.2.1. 1388 11.1. HELLO Message Specification 1390 HELLO messages are generated independently on each MANET interface. 1392 All addresses in any I_local_iface_addr_list MUST be included, except 1393 that: 1395 o If the interface on which the HELLO message is to be sent has a 1396 single address with maximum prefix length then that address MAY be 1397 omitted, provided that this address is included as the sending 1398 address of the IP datagram in which the HELLO message is included. 1400 All such included addresses MUST be associated with an Address Block 1401 TLV with Type := LOCAL_IF and Value according to the following: 1403 o If the address is an address of the sending MANET interface, then 1404 Value := THIS_IF. 1406 o Otherwise, Value := OTHER_IF. 1408 The following addresses of current or former 1-hop neighbors MAY be 1409 included in any HELLO message, respecting the parameter 1410 REFRESH_INTERVAL for each association for that MANET interface: 1412 o Addresses of MANET interfaces of 1-hop neighbors from the Link Set 1413 of the Interface Information Base for this MANET interface (i.e. 1414 from an L_neighbor_iface_addr_list), other than those from Link 1415 Tuples with L_status = PENDING. 1417 o Other addresses of symmetric 1-hop neighbors from the Neighbor Set 1418 of this router's Neighbor Information Base (i.e. from an 1419 N_neighbor_iface_addr_list). 1421 o Addresses of MANET interfaces of previously symmetric or heard 1422 1-hop neighbors connected on this MANET interface from the Link 1423 Set of the Interface Information Base for this MANET interface 1424 (i.e. from an L_neighbor_iface_addr_list with L_status = LOST). 1426 o Other addresses of previously symmetric 1-hop neighbors from the 1427 Lost Neighbor Set of this router's Neighbor Information Base (i.e. 1428 from an NL_neighbor_iface_addr). 1430 Each such address MUST be associated with one or more appropriate 1431 Address Block TLVs. Specifically: 1433 1. For each address (henceforth linked address) which is contained 1434 in an L_neighbor_iface_addr_list of a Link Tuple in the Link Set 1435 for this MANET interface, for which L_status != PENDING, include 1436 the linked address with an associated Address Block TLV with: 1438 * Type := LINK_STATUS; AND 1440 * Value := L_status. 1442 2. For each address (henceforth neighbor address) which is contained 1443 in an N_neighbor_iface_addr_list in a Neighbor Tuple with 1444 N_symmetric = true, and which has not already been included with 1445 an associated Address Block TLV with Type = LINK_STATUS and Value 1446 = SYMMETRIC, include the neighbor address with an associated 1447 Address Block TLV with: 1449 * Type := OTHER_NEIGHB; AND 1451 * Value := SYMMETRIC. 1453 3. For each Lost Neighbor Tuple whose NL_neighbor_iface_addr 1454 (henceforth lost address) has not already been included, include 1455 the lost address with an associated Address Block TLV with: 1457 * Type := OTHER_NEIGHB; AND 1459 * Value := LOST. 1461 If any such addresses have been added to these Information Bases 1462 since the last HELLO message was sent on this MANET interface, or if 1463 their status (as indicated by these TLVs and the values they 1464 associate with that address) have changed since that address was last 1465 reported on this MANET interface, then that address, and the 1466 indicated TLVs, MUST be included in the HELLO message. 1468 If an address of a 1-hop neighbor is specified with more than one 1469 associated Address Block TLV, then these Address Block TLVs MAY be 1470 independently included or excluded from each HELLO message. Each 1471 such Address Block TLV MUST be included associated with that address 1472 in a HELLO message sent on that MANET interface in every interval of 1473 length equal to that MANET interface's parameter REFRESH_INTERVAL. 1474 Address Block TLVs associated with the same address included in the 1475 same HELLO message MAY be applied to the same or different copies of 1476 that address. 1478 11.2. HELLO Message Transmission 1480 HELLO messages are transmitted in the format specified by [RFC5444]. 1482 11.2.1. HELLO Message Jitter 1484 HELLO messages MAY be sent using periodic message generation or 1485 externally triggered message generation. If using data link and 1486 physical layers which are subject to packet loss due to collisions, 1487 HELLO messages SHOULD be jittered as described in [RFC5148]. 1489 Internally triggered message generation (such as due to a change in 1490 local interfaces) MAY be treated as if externally generated message 1491 generation, or MAY be not jittered. 1493 HELLO messages MUST NOT be forwarded, and thus message forwarding 1494 jitter does not apply to HELLO messages. 1496 Each form of jitter described in [RFC5148] requires a parameter 1497 MAXJITTER. These interface parameters may be dynamic, and are 1498 specified by: 1500 o For periodic message generation: HP_MAXJITTER. 1502 o For externally triggered message generation: HT_MAXJITTER. 1504 When HELLO message generation is delayed in order that a HELLO 1505 message is not sent within HELLO_MIN_INTERVAL of the previous HELLO 1506 message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD 1507 be reduced by jitter, with maximum reduction HP_MAXJITTER, as 1508 described in [RFC5148]. In this case HP_MAXJITTER MUST NOT be 1509 greater than HELLO_MIN_INTERVAL. 1511 12. HELLO Message Processing 1513 On receiving a HELLO message, a router MUST first check if the 1514 message is invalid for processing by this router, as defined in 1515 Section 12.1. Otherwise the receiving router MUST update its 1516 appropriate Interface Information Base and its Neighbor Information 1517 Base as specified in Section 12.3 to Section 12.6. These updates 1518 MUST be performed in the order in which they are presented in this 1519 specification. If any changes satisfy any of the conditions 1520 described in Section 13 then the indicated consequences in that 1521 section MUST be applied immediately, unless noted otherwise. 1523 All message processing, including determination of whether a message 1524 is invalid, considers only TLVs with Type Extension = 0. TLVs with 1525 any other type extension are ignored. All references to, for 1526 example, a TLV with Type = LINK_STATUS refer to a TLV with Type = 1527 LINK_STATUS and Type Extension = 0. 1529 12.1. Invalid Message 1531 A received HELLO message is invalid for processing by this router if 1532 any of the following conditions are true: 1534 o The address length as specified in the the Message Header is not 1535 equal to the length of the addresses used by this router. 1537 o The message has a field in its Message Header with 1538 a value other than one. (Note that the message need not have a 1539 field.) 1541 o The message has a field in its Message Header with 1542 a value other than zero. (Note that the message need not have a 1543 field.) 1545 o The message does not have a Message TLV with Type = VALIDITY_TIME 1546 in its Message TLV Block. 1548 o The message has more than one Message TLV with Type = 1549 VALIDITY_TIME in its Message TLV Block. 1551 o The message has more than one Message TLV with Type = 1552 INTERVAL_TIME in its Message TLV Block. 1554 o The message has any Address Block TLV(s) with Type = LOCAL_IF and 1555 any single value v such that v != THIS_IF and v != OTHER_IF. 1557 o Any address (including different copies of an address, in the same 1558 or different Address Blocks) is associated with more than one 1559 value by one or more Address Block TLV(s) with Type = LOCAL_IF. 1561 o Any address (henceforth the local address) associated with an 1562 Address Block TLV with Type = LOCAL_IF is one of the receiving 1563 router's current or recently used addresses (i.e. the local 1564 address is contained in any I_local_iface_addr_list in the Local 1565 Interface Set or the local address = any IR_local_iface_addr in 1566 the Removed Interface Address Set). 1568 o The message has any Address Block TLV(s) with Type = LINK_STATUS 1569 with any single value v such that v != LOST, v != SYMMETRIC, and v 1570 != HEARD. 1572 o Any address (including different copies of an address, in the same 1573 or different Address Blocks) is associated with more than one 1574 value by one or more Address Block TLVs with Type = LINK_STATUS. 1576 o The message has any Address Block TLV(s) with Type = OTHER_NEIGHB 1577 with any single value v such that v != LOST and v != SYMMETRIC. 1579 o Any address (including different copies of an address, in the same 1580 or different Address Blocks) is associated with more than one 1581 value by one or more Address Block TLVs with Type = OTHER_NEIGHB. 1583 An invalid message MUST be silently discarded, without updating the 1584 router's Information Bases. A router MAY recognize additional 1585 reasons for identifying that a message is badly formed, and discard 1586 such messages. 1588 12.2. Definitions 1590 For the purpose of this section, note the following definitions: 1592 o "validity time" is calculated from the Message TLV with Type = 1593 VALIDITY_TIME of the HELLO message as specified in [RFC5497]. 1594 (Note that, as specified by Section 12.1, there must be exactly 1595 one such Message TLV in the HELLO message.) All information in 1596 the HELLO message used by this specification has the same validity 1597 time. 1599 o "Receiving Address List" is the I_local_iface_addr_list 1600 corresponding to the MANET interface on which the HELLO message 1601 was received 1603 o "Sending Address List" is the list of the addresses contained in 1604 the HELLO message with an associated Address Block TLV with Type = 1605 LOCAL_IF and Value = THIS_IF. If the Sending Address List is 1606 otherwise empty, then the Sending Address List contains a single 1607 address (with maximum prefix length) equal to the sending address 1608 of the IP datagram in which the HELLO message was included. 1610 o "Neighbor Address List" is the Sending Address List, plus the 1611 addresses contained in the HELLO message with an associated 1612 Address Block TLV with Type = LOCAL_IF and Value = OTHER_IF. 1614 o EXPIRED indicates that a timer is set to a value clearly preceding 1615 the current time (e.g., current time - 1). 1617 o "Removed Address List" is a list of addresses created by this 1618 HELLO message processing which were formerly reported as local by 1619 the router originating the HELLO message, but which are not 1620 included in the Neighbor Address List. This list is initialized 1621 as empty. 1623 o "Lost Address List" is a subset of the Removed Address List 1624 containing addresses which were formerly considered as symmetric. 1625 This list is initialized as empty. 1627 12.3. Updating the Neighbor Set 1629 On receiving a HELLO message, the router MUST update its Neighbor Set 1630 and populate the Removed Address List and Lost Address List: 1632 1. Find all Neighbor Tuples (henceforth matching Neighbor Tuples) 1633 where: 1635 * N_neighbor_iface_addr_list contains at least one address in 1636 the Neighbor Address List. 1638 2. If there are no matching Neighbor Tuples, then: 1640 1. Create a new Neighbor Tuple with: 1642 + N_neighbor_iface_addr_list := Neighbor Address List; 1644 + N_symmetric := false. 1646 3. If there is one matching Neighbor Tuple, then: 1648 1. If the matching Neighbor Tuple's N_neighbor_iface_addr_list 1649 != Neighbor Address List, then: 1651 1. For each address (henceforth removed address) which is 1652 contained in that N_neighbor_iface_addr_list, but is not 1653 contained in the Neighbor Address List: 1655 1. Add the removed address to the Removed Address List. 1657 2. If N_symmetric = true, then add the removed address 1658 to the Lost Address List. 1660 2. Update the matching Neighbor Tuple by: 1662 - N_neighbor_iface_addr_list := Neighbor Address List. 1664 4. If there are two or more matching Neighbor Tuples, then: 1666 1. For each address (henceforth removed address) which is 1667 contained in the N_neighbor_iface_addr_list of any of the 1668 matching Neighbor Tuples: 1670 1. Add the removed address to the Removed Address List. 1672 2. If N_symmetric = true, then add the removed address to 1673 the Lost Address List. 1675 2. Replace the matching Neighbor Tuples by a single Neighbor 1676 Tuple with: 1678 + N_neighbor_iface_addr_list := Neighbor Address List; 1680 + N_symmetric := false 1682 12.4. Updating the Lost Neighbor Set 1684 On receiving a HELLO message, a router MUST update its Lost Neighbor 1685 Set: 1687 1. For each address (henceforth lost address) which is contained in 1688 the Lost Address List, if no Lost Neighbor Tuple with 1689 NL_neighbor_iface_addr = lost address exists, then add a Lost 1690 Neighbor Tuple with: 1692 * NL_neighbor_iface_addr := lost address; 1694 * NL_time := current time + N_HOLD_TIME. 1696 12.5. Updating the Link Set 1698 On receiving a HELLO message, a router MUST update its Link Set for 1699 the MANET interface on which the HELLO message is received: 1701 1. Remove all addresses in the Removed Address List from the 1702 L_neighbor_iface_addr_list of all Link Tuples. 1704 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now 1705 empty; apply Section 13.2, but not Section 13.3. 1707 3. Find all Link Tuples (henceforth matching Link Tuples) where: 1709 * L_neighbor_iface_addr_list contains one or more addresses in 1710 the Sending Address List. 1712 4. If there is more than one matching Link Tuple, then remove them 1713 all; apply Section 13.2, but not Section 13.3. 1715 5. If no matching Link Tuples remain, then create a new matching 1716 Link Tuple with: 1718 * L_neighbor_iface_addr_list := empty; 1720 * L_HEARD_time := EXPIRED; 1722 * L_SYM_time := EXPIRED; 1724 * L_quality := INITIAL_QUALITY; 1726 * L_pending := INITIAL_PENDING; 1728 * L_lost := false; 1730 * L_time := current time + validity time. 1732 6. The matching Link Tuple, existing or new, is then modified as 1733 follows: 1735 1. If the router finds any address (henceforth receiving 1736 address) in the Receiving Address List in an Address Block in 1737 the HELLO message, then the Link Tuple is modified as 1738 follows: 1740 1. If any receiving address in the HELLO message is 1741 associated with an Address Block TLV with Type = 1742 LINK_STATUS and with Value = HEARD or Value = SYMMETRIC 1743 then: 1745 - L_SYM_time := current time + validity time. 1747 2. Otherwise if any receiving address in the HELLO message 1748 is associated with an Address Block TLV with Type = 1749 LINK_STATUS and Value = LOST then: 1751 1. if L_SYM_time has not expired, then: 1753 1. L_SYM_time := EXPIRED. 1755 2. if L_status = HEARD or L_status = SYMMETRIC, 1756 then: 1758 * L_time := current time + L_HOLD_TIME. 1760 2. L_neighbor_iface_addr_list := Sending Address List. 1762 3. L_HEARD_time := max(current time + validity time, 1763 L_SYM_time). 1765 4. If L_status = PENDING, then: 1767 + L_time := max(L_time, L_HEARD_time). 1769 5. Otherwise if L_status = HEARD or L_status = SYMMETRIC, then: 1771 + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 1773 12.6. Updating the 2-Hop Set 1775 On receiving a HELLO message a router MUST update its 2-Hop Set for 1776 the MANET interface on which the HELLO message was received: 1778 1. Remove all addresses in the Removed Address List from the 1779 N2_neighbor_iface_addr_list of all 2-Hop Tuples. 1781 2. If the Link Tuple whose L_neighbor_iface_addr_list = Sending 1782 Address List, has L_status = SYMMETRIC then: 1784 1. For each address (henceforth 2-hop address) in an Address 1785 Block of the HELLO message, where: 1787 + 2-hop address is not contained in the Neighbor Address 1788 List; 1790 + 2-hop address is not contained in any 1791 I_local_iface_addr_list; AND 1793 + 2-hop address != any IR_local_iface_addr 1795 4. If 2-hop address has an associated Address Block TLV 1796 with: 1798 - Type = LINK_STATUS and Value = SYMMETRIC; OR 1800 - Type = OTHER_NEIGHB and Value = SYMMETRIC, 1802 then, if there is no 2-Hop Tuple such that: 1804 - N2_neighbor_iface_addr_list contains one or more 1805 addresses in the Sending Address List; AND 1807 - N2_2hop_iface_addr = 2-hop address. 1809 then create a 2-Hop Neighbor Tuple with: 1811 - N2_2hop_iface_addr := 2-hop address. 1813 This 2-Hop Tuple (existing or new) is then modified as 1814 follows: 1816 - N2_neighbor_iface_addr_list := Sending Address List; 1818 - N2_time := current time + validity time. 1820 5. Otherwise if the 2-hop address has an Address Block TLV 1821 with: 1823 - Type = LINK_STATUS and Value = LOST or Value = HEARD; 1824 OR 1826 - Type = OTHER_NEIGHB and Value = LOST; 1828 then remove all 2-Hop Tuples with: 1830 - N2_neighbor_iface_addr_list contains one or more 1831 addresses in the Sending Address List; AND 1833 - N2_2hop_iface_addr = 2-hop address. 1835 13. Other Information Base Changes 1837 The Interface and Neighbor Information Bases MUST be changed when 1838 certain events occur. These events may result from HELLO message 1839 processing, or may be otherwise generated (e.g., expiry of timers or 1840 link quality changes). 1842 Events which cause changes in the Information Bases are: 1844 o A Link Tuple's L_status changes to SYMMETRIC. In this case, the 1845 actions specified in Section 13.1 are performed. 1847 o A Link Tuple's L_status changes from SYMMETRIC, or the Link Tuple 1848 is removed. In this case, the actions specified in Section 13.2 1849 are performed. 1851 o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed. 1852 In this case, the actions specified in Section 13.3 are performed. 1854 o Local interface address changes. In this case, the actions 1855 specified in Section 9 are performed. 1857 o Link quality changes. In this case, the actions specified in 1858 Section 14 are performed. 1860 If a Link Tuple is removed, or if L_status changes from SYMMETRIC and 1861 L_HEARD_time expires, then the actions specified in Section 13.2 MUST 1862 be performed before the actions specified in section Section 13.3 are 1863 performed for that Link Tuple. 1865 A router MAY report updated information in response to any of these 1866 changes in HELLO message(s), subject to the constraints in 1867 Section 11. 1869 A router which transmits HELLO messages in response to such changes 1870 SHOULD transmit a HELLO message: 1872 o On all MANET interfaces, if the Neighbor Set changes such as to 1873 indicate the change in symmetry of any 1-hop neighbors (including 1874 addition or removal of symmetric 1-hop neighbors). 1876 o Otherwise, on all those MANET interfaces whose Link Set changes 1877 such as to indicate a change in L_status of any 1-hop neighbors 1878 (including the addition or removal of any 1-hop neighbors, other 1879 than those considered pending). 1881 13.1. Link Tuple Symmetric 1883 If, for any Link Tuple which does not have L_status = SYMMETRIC: 1885 o L_status changes to SYMMETRIC; 1887 (this includes a newly created Link Tuple which is immediately 1888 updated such that L_status = SYMMETRIC) then: 1890 1. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 1891 L_neighbor_iface_addr_list, set: 1893 * N_symmetric := true. 1895 2. Remove all Lost Neighbor Tuples whose NL_neighbor_iface_addr is 1896 contained in that N_neighbor_iface_addr_list. 1898 13.2. Link Tuple Not Symmetric 1900 If for any Link Tuple with L_status = SYMMETRIC: 1902 o L_status changes to any other value; OR 1904 o the Link Tuple is removed; 1906 then: 1908 1. All 2-Hop Tuples for the same MANET interface with: 1910 * N2_neighbor_iface_addr_list contains one or more addresses in 1911 L_neighbor_iface_addr_list; 1913 are removed. 1915 2. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 1916 L_neighbor_iface_addr_list: 1918 1. If there are no remaining Link Tuples for any MANET interface 1919 where: 1921 + L_neighbor_iface_addr_list is contained in 1922 N_neighbor_iface_addr_list; AND 1924 + L_status = SYMMETRIC; 1926 then modify the Neighbor Tuple by: 1928 1. N_symmetric := false. 1930 2. For each address (henceforth neighbor address) in 1931 N_neighbor_iface_addr_list, add a Lost Neighbor Tuple 1932 with: 1934 - NL_neighbor_iface_addr := neighbor address; 1936 - NL_time := current time + N_HOLD_TIME. 1938 13.3. Link Tuple Heard Timeout 1940 If, for any Link Tuple: 1942 o L_HEARD_time expires; OR 1944 o the Link Tuple is removed; 1946 then: 1948 1. For the Neighbor Tuple whose N_neighbor_iface_addr_list contains 1949 L_neighbor_iface_addr_list, if no Link Tuples for any MANET 1950 interface remain where: 1952 * L_neighbor_iface_addr_list is contained in 1953 N_neighbor_iface_addr_list; AND 1955 * L_HEARD_time is not expired; 1957 then remove the Neighbor Tuple. 1959 14. Link Quality 1961 Link quality is a mechanism whereby a router MAY take considerations 1962 other than message exchange into account for determining when a link 1963 is and is not a candidate for being considered as HEARD or SYMMETRIC. 1965 Link quality information for a link is generated (e.g., through 1966 access to signal to noise ratio, packet loss rate, or other 1967 information from the link layer) and used only locally, i.e. is not 1968 included in signaling, and routers may interoperate whether they are 1969 using the same, different, or no, link quality information. 1971 For deployments where no link quality is used, the considerations in 1972 Section 14.1 apply. For deployments where link quality is used, the 1973 general principles of link quality usage are described in 1974 Section 14.2. Section 14.3 and Section 14.4 detail link quality 1975 functioning. 1977 14.1. Deployment Without Link Quality 1979 In order for a router to not employ link quality, the router MUST 1980 define: 1982 o INITIAL_PENDING := false; 1984 o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define 1985 INITIAL_QUALITY := 1). 1987 14.2. Basic Principles of Link Quality 1989 To enable link quality usage, the L_quality value of a Link Tuple is 1990 used in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, 1991 to set the flags L_pending and L_lost of that Link Tuple. Based on 1992 these flags, the link status to advertise for that Link Tuple is 1993 determined as described in Section 7.1. 1995 The use of two thresholds implements link hysteresis, whereby a link 1996 which has HYST_REJECT <= L_quality < HYST_ACCEPT may be either 1997 accepted or rejected (depending on which threshold it has most 1998 recently crossed, or, if neither, on the value of parameter 1999 INITIAL_PENDING). With appropriate values of these parameters, this 2000 prevents over-rapid changes of link status. 2002 The basic principles of link quality usage are as follows: 2004 o A router does not advertise a neighbor interface in any state 2005 until L_quality is acceptable: 2007 * If INITIAL_PENDING = true, then the link is advertised when 2008 link L_quality >= HYST_ACCEPT. 2010 * Otherwise the link is advertised when L_quality >= HYST_REJECT. 2012 A link which is not yet advertised has L_pending = true. 2014 o Once L_quality >= HYST_ACCEPT, the router sets L_pending := false, 2015 indicating that the link can be advertised. 2017 o A link for which L_pending = false is advertised until its 2018 L_quality drops below HYST_REJECT. 2020 o If a link has L_pending = false and L_quality < HYST_REJECT, the 2021 link is LOST and is advertised as such. This link is not 2022 reconsidered as a candidate HEARD or SYMMETRIC link until 2023 L_quality >= HYST_ACCEPT. 2025 o A link which has an acceptable quality may be advertised as HEARD, 2026 SYMMETRIC or LOST according to the exchange of HELLO messages. 2028 In order that these principles can all hold, a router MUST NOT 2029 define: 2031 o INITIAL_PENDING = false and INITIAL_QUALITY < HYST_REJECT; OR 2033 o INITIAL_PENDING = true and INITIAL_QUALITY >= HYST_ACCEPT. 2035 14.3. When Link Quality Changes 2037 If L_quality for a link changes, then the following actions MUST be 2038 taken: 2040 1. If L_quality >= HYST_ACCEPT then the corresponding Link Tuple is 2041 modified by: 2043 1. L_pending := false; 2045 2. L_lost := false; 2047 3. If L_status = HEARD or L_status = SYMMETRIC, then: 2049 + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 2051 2. If L_status != PENDING, and L_quality < HYST_REJECT then the 2052 corresponding Link Tuple is modified by: 2054 1. If L_lost = false, then: 2056 + L_lost := true; 2058 + L_time := min(L_time, current time + L_HOLD_TIME). 2060 Any appropriate action indicted in Section 13 MUST also be taken. 2062 If L_quality for a link is updated based on HELLO message reception, 2063 or on reception of a packet including a HELLO message, then L_quality 2064 MUST be updated prior to the HELLO message processing described in 2065 Section 12. (If the receipt of the HELLO message, or the packet 2066 containing it, creates the Link Tuple, then the Link Tuple MUST be 2067 created with the appropriately updated L_quality value, rather than 2068 with L_quality := INITIAL_QUALITY.) 2070 14.4. Updating Link Quality 2072 A router MAY update link quality based on any information available 2073 to it. Particular cases that MAY be used include: 2075 o Information from the link layer, such as signal to noise ratio or 2076 packet acknowledgement reception and loss information. 2078 o Receipt or loss of control packets. If control packets include a 2079 sequential packet sequence number, as defined in [RFC5444], then 2080 link quality can be updated when a control packet is received, 2081 whether or not it contains a HELLO message. The link quality may 2082 then, for example, be based on whether the last N out of M control 2083 packets on the link were received, or may use a "leaky integrator" 2084 tracking packet reception and loss. 2086 o Receipt or loss of HELLO messages. If the maximum interval 2087 between HELLO messages is known (such as by inclusion in HELLO 2088 messages of a Message TLV with Type := INTERVAL_TIME, as defined 2089 in [RFC5497]) then the loss of HELLO messages can be determined 2090 without the need to receive a later HELLO message. Note that if 2091 this case is combined with the previous case then care must be 2092 taken to avoid "double counting" a lost HELLO message in a lost 2093 packet. 2095 15. Proposed Values for Parameters and Constants 2097 This section lists the parameters and constants used in the 2098 specification of the protocol, and proposed values of each which may 2099 be used when a single value of each is used. 2101 15.1. Message Interval Interface Parameters 2103 o HELLO_INTERVAL := 2 seconds 2105 o HELLO_MIN_INTERVAL := HELLO_INTERVAL/4 2107 o REFRESH_INTERVAL := HELLO_INTERVAL 2109 15.2. Information Validity Time Interface Parameters 2111 o H_HOLD_TIME := 3 x REFRESH_INTERVAL 2113 o L_HOLD_TIME := H_HOLD_TIME 2115 15.3. Information Validity Time Router Parameters 2117 o N_HOLD_TIME := L_HOLD_TIME 2119 o I_HOLD_TIME := N_HOLD_TIME 2121 15.4. Link Quality Interface Parameters 2123 If link quality is changed, then parameter values will depend on the 2124 link quality process. If link quality is not changed, then: 2126 o HYST_ACCEPT := 1 2128 o HYST_REJECT := 0 2130 o INITIAL_QUALITY := 1 2132 o INITIAL_PENDING := false 2134 15.5. Jitter Interface Parameters 2136 o HP_MAXJITTER := HELLO_INTERVAL/4 2138 o HT_MAXJITTER := HP_MAXJITTER 2140 15.6. Constants 2142 o C := 1/1024 second 2144 16. Usage with Other Protocols 2146 Other protocols, such as MANET routing protocols, which use 2147 neighborhood discovery may need to interact with this protocol. This 2148 protocol is designed to permit such interactions, in particular: 2150 o Through accessing, and possibly extending, the information in the 2151 Local Information Base (Section 6), the Interface Information Base 2152 (Section 7) and the Neighbor Information Base (Section 8). These 2153 Information Bases record the interface configuration of the 2154 router, as well as the local connectivity, up to two hops away. 2155 All updates to the elements specified in this document are subject 2156 to the constraints specified in Appendix B. 2158 o Through accessing an outgoing HELLO message prior to it being 2159 transmitted over any MANET interface, and to add information 2160 (e.g., TLVs) as specified in [RFC5444]. This may, for example, be 2161 to allow a security protocol, as suggested in Section 17, to add a 2162 TLV containing a cryptographic signature to the message, or be to 2163 allow inserting relay selection information into a HELLO message 2164 by way of adding a TLV to an outgoing HELLO message prior to it 2165 being transmitted. 2167 o Through accessing an incoming HELLO message, and potentially 2168 discard it prior to processing by this protocol. This may, for 2169 example, allow a security protocol as suggested in Section 17 to 2170 perform verification of HELLO message signatures and prevent 2171 processing of unverifiable HELLO messages by this protocol. 2173 o Through accessing an incoming HELLO message after it has been 2174 completely processed by this protocol. This may, in particular, 2175 allow a protocol which has added information, such as relay 2176 selection information by way of inclusion of appropriate TLVs, 2177 access to such information after appropriate updates have been 2178 recorded in the Information Bases in this protocol. 2180 o Through requesting that a HELLO message be generated at a specific 2181 time. In that case, HELLO message generation MUST still respect 2182 the constraints in Appendix B. 2184 17. Security Considerations 2186 The objective of this protocol is to allow each router in the network 2187 to acquire information describing its 1-hop neighborhood and 2188 symmetric 2-hop neighborhood. This is acquired through message 2189 exchange between neighboring routers. The information is made 2190 available through the Interface Information Bases and Neighbor 2191 Information Base, describing the router's 1-hop neighborhood and 2192 symmetric 2-hop neighborhood. 2194 Under normal circumstances, the information recorded in these 2195 Information Bases is correct, i.e. corresponds to the actual network 2196 topology, apart from any changes which have not (yet) been tracked by 2197 the HELLO message exchanges. 2199 If a router for some reason, whether malice or malfunction, transmits 2200 invalid HELLO messages, incorrect information may be recorded in 2201 other routers' Information Bases. The protocol specification does, 2202 however, prevent inconsistent information from being included in the 2203 protocol sets through the defined processing that maintains the 2204 constraints in Appendix B. The exact consequence of information 2205 inexactness depends on the use of these Information Bases, and should 2206 be reflected in the specification of protocols which use information 2207 provided by NHDP. 2209 This section, therefore, only outlines the ways in which correctly 2210 formed, but still invalid, HELLO messages may appear, in 2211 Section 17.1. In addition, in Section 17.2, the security suggestions 2212 in [RFC5444] are considered for applicability. 2214 17.1. Invalid HELLO messages 2216 A correctly formed, but still invalid, HELLO message may take any of 2217 the following forms. Note that a present or absent address in an 2218 Address Block, does not in and by itself cause a problem. It is the 2219 presence, absence, or incorrectness of associated LOCAL_IF, 2220 LINK_STATUS and OTHER_NEIGHB Address Block TLVs that causes problems. 2222 A router may provide false information about its own identity: 2224 * The HELLO message may contain addresses with an associated 2225 LOCAL_IF Address Block TLV which do not correspond to addresses 2226 of interfaces of the router transmitting the HELLO message. 2228 * The HELLO message may omit addresses, or their associated 2229 LOCAL_IF Address Block TLV, of interfaces of the router 2230 transmitting the HELLO message (other than the allowed omission 2231 of the only local interface address of the MANET interface over 2232 which the HELLO message is transmitted, if that is the case). 2234 * The HELLO message may incorrectly specify the LOCAL_IF Address 2235 Block TLV value associated with one or more local interface 2236 addresses, indicating incorrectly whether they are associated 2237 with the MANET interface over which the HELLO message is 2238 transmitted. 2240 A router may provide false information about the identity of other 2241 routers: 2243 * A present LINK_STATUS Address Block TLV may, incorrectly, 2244 identify an address as being of a MANET interface which is or 2245 was heard on the MANET interface over which the HELLO message 2246 is transmitted. 2248 * A consistently absent LINK_STATUS Address Block TLV may, 2249 incorrectly, fail to identify an address as being of a MANET 2250 interface which is or was heard on the MANET interface over 2251 which the HELLO message is transmitted. 2253 * A present OTHER_NEIGHB Address Block TLV may, incorrectly, 2254 identify an address as being of a router which is or was in the 2255 sending router's symmetric 1-hop neighborhood; 2257 * A consistently absent OTHER_NEIGHB Address Block TLV may, 2258 incorrectly, fail to identify an address as being of a router 2259 which is or was in the sending router's symmetric 1-hop 2260 neighborhood; 2262 * The value of a LINK_STATUS Address Block TLV may incorrectly 2263 indicate the status (LOST, SYMMETRIC or HEARD) of the link from 2264 a 1-hop neighbor. 2266 * The value of an OTHER_NEIGHB Address Block TLV may incorrectly 2267 indicate the status (LOST or SYMMETRIC) of a symmetric 1-hop 2268 neighbor. 2270 17.2. Authentication, Integrity and Confidentiality Suggestions 2272 The security suggestions in [RFC5444] regarding inclusion of a 2273 cryptographic signature in a Message TLV or a Packet TLV can be 2274 applied to this protocol. Failure to verify either form of 2275 cryptographic signature causes a HELLO message to be rejected without 2276 being processed. 2278 The following simplification of the suggestions for end-to-end 2279 authentication and integrity in [RFC5444] may be applied to HELLO 2280 messages: 2282 o As the Message Header fields and 2283 are either omitted or will always have the values 0 and 1, 2284 respectively, an end to end cryptographic signature can be 2285 calculated based on the entire HELLO message, including its 2286 unmodified Message Header. 2288 The security mechanisms suggested in [RFC5444] with respect to 2289 confidentiality can be directly applied to this protocol. 2291 18. IANA Considerations 2293 This specification defines one Message Type, which must be allocated 2294 from the "Message Types" repository of [RFC5444], and three Address 2295 Block TLV Types, which must be allocated from the "Address Block TLV 2296 Types" repository of [RFC5444]. 2298 18.1. Expert Review: Evaluation Guidelines 2300 For the registries where an Expert Review is required, the designated 2301 expert SHOULD take the same general recommendations into 2302 consideration as are specified by [RFC5444]. 2304 18.2. Message Types 2306 This specification defines one Message Type, to be allocated from the 2307 0-223 range of the "Message Types" namespace defined in [RFC5444], as 2308 specified in Table 3. 2310 +-------+------+-----------------+ 2311 | Name | Type | Description | 2312 +-------+------+-----------------+ 2313 | HELLO | TBD1 | Local signaling | 2314 +-------+------+-----------------+ 2316 Table 3: Message Type assignment 2318 18.3. Message-Type-specific TLV Type Registries 2320 IANA is requested to create a registry for Message-Type-specific 2321 Message TLVs for HELLO messages, in accordance with Section 6.2.1 of 2322 [RFC5444], and with initial assignments and allocation policies as 2323 specified in Table 4. 2325 +---------+-------------+-------------------+ 2326 | Type | Description | Allocation Policy | 2327 +---------+-------------+-------------------+ 2328 | 128-223 | Unassigned | Expert Review | 2329 +---------+-------------+-------------------+ 2331 Table 4: HELLO Message-Type-specific Message TLV Types 2333 IANA is requested to create a registry for Message-Type-specific 2334 Address Block TLVs for HELLO messages, in accordance with Section 2335 6.2.1 of [RFC5444], and with initial assignments and allocation 2336 policies as specified in Table 5. 2338 +---------+-------------+-------------------+ 2339 | Type | Description | Allocation Policy | 2340 +---------+-------------+-------------------+ 2341 | 128-223 | Unassigned | Expert Review | 2342 +---------+-------------+-------------------+ 2344 Table 5: HELLO Message-Type-specific Address Block TLV Types 2346 18.4. Address Block TLV Types 2348 This specification defines three Address Block TLV Types, which must 2349 be allocated from the "Address Block TLV Types" namespace defined in 2350 [RFC5444]. IANA are requested to make allocations in the 0-127 range 2351 for these types. This will create three new type extension 2352 registries with assignments as specified in Table 6, Table 7 and 2353 Table 8. Specifications of these Address Block TLVs are in 2354 Section 10.1.1, with Value Constants defined in Section 18.5. 2356 +------------+------+-----------+-----------------------------------+ 2357 | Name | Type | Type | Description | 2358 | | | extension | | 2359 +------------+------+-----------+-----------------------------------+ 2360 | LOCAL_IF | TBD2 | 0 | Specifies that the address is | 2361 | | | | associated with a local interface | 2362 | | | | of the sending router | 2363 | Unassigned | TBD2 | 1-255 | Expert Review | 2364 +------------+------+-----------+-----------------------------------+ 2366 Table 6: Address Block TLV Type assignment: LOCAL_IF 2368 +-------------+------+-----------+----------------------------------+ 2369 | Name | Type | Type | Description | 2370 | | | extension | | 2371 +-------------+------+-----------+----------------------------------+ 2372 | LINK_STATUS | TBD3 | 0 | Specifies the status of the link | 2373 | | | | from the indicated address | 2374 | | | | (LOST, SYMMETRIC or HEARD) | 2375 | Unassigned | TBD3 | 1-255 | Expert Review | 2376 +-------------+------+-----------+----------------------------------+ 2378 Table 7: Address Block TLV Type assignment: LINK_STATUS 2380 +--------------+------+-----------+---------------------------------+ 2381 | Name | Type | Type | Description | 2382 | | | extension | | 2383 +--------------+------+-----------+---------------------------------+ 2384 | OTHER_NEIGHB | TBD4 | 0 | Specifies that the address is | 2385 | | | | (SYMMETRIC) or recently was | 2386 | | | | (LOST) of an interface of a | 2387 | | | | symmetric 1-hop neighbor of the | 2388 | | | | router transmitting the message | 2389 | Unassigned | TBD4 | 1-255 | Expert Review | 2390 +--------------+------+-----------+---------------------------------+ 2392 Table 8: Address Block TLV Type assignment: OTHER_NEIGHB 2394 18.5. LINK_STATUS and OTHER_NEIGHB Values 2396 The values which the LOCAL_IF Address Block TLV can use are the 2397 following: 2399 o THIS_IF := 0 2401 o OTHER_IF := 1 2403 The values which the LINK_STATUS Address Block TLV can use are the 2404 following: 2406 o LOST := 0 2408 o SYMMETRIC := 1 2410 o HEARD := 2 2412 The values which the OTHER_NEIGHB Address Block TLV can use are the 2413 following: 2415 o LOST := 0 2417 o SYMMETRIC := 1 2419 19. Contributors 2421 This specification is the result of the joint efforts of the 2422 following contributors, listed alphabetically. 2424 o Brian Adamson, NRL, USA, 2426 o Cedric Adjih, INRIA, France, 2428 o Thomas Heide Clausen, LIX, France, 2430 o Justin Dean, NRL, USA, 2432 o Christopher Dearlove, BAE Systems ATC, UK, 2433 2435 o Philippe Jacquet, INRIA, France, 2437 20. Acknowledgements 2439 The authors would like to acknowledge the team behind OLSRv1, 2440 specified in RFC3626 for their contributions. 2442 The authors would like to gratefully acknowledge the following people 2443 for intense technical discussions, early reviews and comments on the 2444 specification and its components (listed alphabetically): Alan Cullen 2445 (BAE Systems), Ulrich Herberg (LIX), Satoh Hiroki (Hitachi) Joe 2446 Macker (NRL), Charles E. Perkins (WiChorus), Laurent Viennot (INRIA), 2447 and the entire IETF MANET working group. 2449 21. References 2451 21.1. Normative References 2453 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2454 Requirement Levels", RFC 2119, BCP 14, March 1997. 2456 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 2457 considerations in MANETs", RFC 5148, February 2008. 2459 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2460 "Generalized MANET Packet/Message Format", RFC 5444, 2461 February 2009. 2463 [RFC5497] Clausen, T. and C. Dearlove, "Representing multi-value 2464 time in MANETs", RFC 5497, March 2009. 2466 [RFC5498] Chakeres, I., "IANA Allocations for MANET Protocols", 2467 RFC 5498, March 2009. 2469 21.2. Informative References 2471 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 2472 (MANET): Routing Protocol Performance Issues and 2473 Evaluation Considerations", RFC 2501, January 1999. 2475 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 2476 Routing Protocol", RFC 3626, October 2003. 2478 [RFC5449] Clausen, T., Baccelli, E., Nguyen, D., and P. Jacquet, 2479 "OSPF Multipoint Relay (MPR) Extension for Ad Hoc 2480 Networks", RFC 5449, February 2009. 2482 Appendix A. Address Block TLV Combinations 2484 The algorithm for generating HELLO messages in Section 11 specifies 2485 which 1-hop addresses may be included in the Address Blocks, and with 2486 which associated Address Block TLVs. These Address Block TLVs may 2487 have Type = LINK_STATUS or Type = OTHER_NEIGHB, or both. Address 2488 Block TLVs with Type = LINK_STATUS may have three possible values 2489 (Value = HEARD, Value = SYMMETRIC or Value = LOST), and Address Block 2490 TLVs of TYPE = OTHER_NEIGHB may have two possible values (Value = 2491 SYMMETRIC or Value = LOST). When both Address Block TLVs are 2492 associated with the same address only certain combinations of these 2493 Address Block TLV values are necessary, and are the only combinations 2494 generated by the algorithm in Section 11. These combinations are 2495 indicated in Table 9. 2497 Cells labeled with "Yes" indicate the possible combinations which are 2498 generated by the algorithm in Section 11. Cells labeled with "No" 2499 indicate combinations not generated by the algorithm in Section 11, 2500 but which are correctly parsed and interpreted by the algorithm in 2501 Section 12. The cell labeled with "No*" is actually inconsistent, it 2502 is handled by ignoring the Address Block TLV with Type = 2503 OTHER_NEIGHB. 2505 +----------------+----------------+----------------+----------------+ 2506 | | Type = | Type = | Type = | 2507 | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | 2508 | | (absent) | Value = | Value = LOST | 2509 | | | SYMMETRIC | | 2510 +----------------+----------------+----------------+----------------+ 2511 | Type = | No | Yes | Yes | 2512 | LINK_STATUS | | | | 2513 | (absent) | | | | 2514 | Type = | Yes | Yes | Yes | 2515 | LINK_STATUS, | | | | 2516 | Value = HEARD | | | | 2517 | Type = | Yes | No | No* | 2518 | LINK_STATUS, | | | | 2519 | Value = | | | | 2520 | SYMMETRIC | | | | 2521 | Type = | Yes | Yes | No | 2522 | LINK_STATUS, | | | | 2523 | Value = LOST | | | | 2524 +----------------+----------------+----------------+----------------+ 2526 Table 9: LINK_STATUS and OTHER_NEIGHB TLV combinations 2528 Appendix B. Constraints 2530 Any process which updates the Local Information Base or the Neighbor 2531 Information Base MUST ensure that all constraints specified in this 2532 appendix are maintained. 2534 In each Local Interface Tuple: 2536 o I_local_iface_addr_list MUST NOT be empty. 2538 o I_local_iface_addr_list MUST NOT contain any duplicated addresses. 2540 o I_local_iface_addr_list MUST NOT contain any address which is in 2541 the I_local_iface_addr_list of any other Local Interface Tuple. 2543 In each Removed Interface Address Tuple: 2545 o IR_local_iface_addr MUST NOT contain any address which is in the 2546 I_local_iface_addr_list of any Local Interface Tuple. 2548 o IR_local_iface_addr MUST NOT equal the IR_local_iface_addr of any 2549 other Removed Interface Address Tuple. 2551 In each Link Tuple: 2553 o L_neighbor_iface_addr_list MUST NOT be empty. 2555 o L_neighbor_iface_addr_list MUST NOT contain any address which is 2556 in the I_local_iface_addr_list of any Local Interface Tuple or the 2557 IR_local_iface_addr of any Removed Interface Address Tuple. 2559 o L_neighbor_iface_addr_list MUST NOT contain any duplicated 2560 addresses. 2562 o L_neighbor_iface_addr_list MUST NOT contain any address which is 2563 in the L_neighbor_iface_addr_list of any other Link Tuple in the 2564 same Link Set. 2566 o If L_HEARD_time has not expired then there MUST be a Neighbor 2567 Tuple whose N_neighbor_iface_addr_list contains 2568 L_neighbor_iface_addr_list. 2570 o L_HEARD_time MUST NOT be greater than L_time. 2572 o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are 2573 expired). 2575 o L_quality MUST NOT be less than 0 or greater than 1. 2577 o If L_quality >= HYST_ACCEPT then L_pending MUST be false. 2579 o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST. 2581 o L_pending MUST NOT be set to true if it is currently false. 2583 In each Neighbor Tuple: 2585 o N_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 N_neighbor_iface_addr_list MUST NOT contain any duplicated 2590 addresses. 2592 o N_neighbor_iface_addr_list MUST NOT contain any address which is 2593 in the N_neighbor_iface_addr_list of any other Neighbor Tuple. 2595 o If N_symmetric is = true, then there MUST be one or more Link 2596 Tuples with: 2598 * L_neighbor_iface_addr_list contained in 2599 N_neighbor_iface_addr_list; AND 2601 * L_status = SYMMETRIC. 2603 o If N_symmetric is = false, then there MUST be one or more Link 2604 Tuples with: 2606 * L_neighbor_iface_addr_list contained in 2607 N_neighbor_iface_addr_list. 2609 All such Link Tuples MUST NOT have L_status = SYMMETRIC. At least 2610 one such Link Tuple MUST have L_HEARD_time not expired. 2612 In each Lost Neighbor Tuple: 2614 o NL_neighbor_iface_addr MUST NOT be in the I_local_iface_addr_list 2615 of any Local Interface Tuple or the IR_local_iface_addr of any 2616 Removed Interface Address Tuple. 2618 o NL_neighbor_iface_addr MUST NOT equal the NL_neighbor_iface_addr 2619 of any other Lost Neighbor Tuple. 2621 o NL_neighbor_iface_addr MUST NOT be in the 2622 N_neighbor_iface_addr_list of any Neighbor Tuple with N_symmetric 2623 = true. 2625 In each 2-Hop Tuple: 2627 o There MUST be a Link Tuple associated with the same MANET 2628 interface with: 2630 * L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list; AND 2632 * L_status = SYMMETRIC. 2634 o N2_2hop_iface_addr MUST NOT be in the I_local_iface_addr_list of 2635 any Local Interface Tuple or the IR_local_iface_addr of any 2636 Removed Interface Address Tuple. 2638 o N2_2hop_iface_addr MUST NOT be the N2_2hop_iface_addr of any other 2639 2-Hop Tuple in the same 2-Hop Set and with the same 2640 N2_neighbor_iface_addr_list. 2642 o N2_2hop_iface_addr MUST NOT be in the N2_neighbor_iface_addr_list 2643 of the same 2-Hop Tuple. 2645 Appendix C. HELLO Message Example 2647 An example HELLO message, transmitted by an originator router with a 2648 single MANET interface, is as follows. 2650 The message has full Message Header (four bit flags field value is 2651 15). Its four bit Message Address Length field has value 3 and hence 2652 addresses in the message have length four octets, here being IPv4 2653 addresses. The message is as transmitted with a hop limit of 1 and a 2654 hop count of 0. The overall message length is 49 octets. 2656 The message contains a Message TLV Block with content length 8 octets 2657 containing two Message TLVs, of types VALIDITY_TIME and 2658 INTERVAL_TIME. Each uses a Message TLV with flags octet value 16, 2659 indicating that each has a value. Each has a value length of 1 2660 octet; the values included (0x64 and 0x58) are time codes 2661 representing the default values of parameters H_HOLD_TIME and 2662 HELLO_INTERVAL, respectively (6 seconds and 2 seconds) assuming the 2663 default value of constant C (1/1024 second). 2665 The message has a single Address Block containing 5 addresses. The 2666 flags octet value 128 indicates an address Head but no address Tail, 2667 and no address prefixes. The Head Length of 3 octets indicates 2668 address Mid sections of one octet each (Mid 0 to Mid 4). 2670 The following Address Block TLV Block (content length 14 octets) 2671 includes two Address Block TLVs. The first is a LOCAL_IF Address 2672 Block TLV which (with flags octet value 80) indicates that a single 2673 address, with index 0 (i.e. Head:Mid 0) is the single local 2674 interface address of this router (the 1 octet value THIS_IF indicates 2675 that this address is of this interface). The second is a LINK_STATUS 2676 Address Block TLV which (with flags octet value 48) specifies the 2677 link status values of all reported neighbors in a single multivalue 2678 Address Block TLV which covers the addresses with indexes 1 to 4. 2679 The Address Block TLV value length of 4 octets indicates one octet 2680 per value per address. The last four addresses have associated link 2681 status, the first and second HEARD, the third SYMMETRIC, and the 2682 fourth LOST. 2684 0 1 2 3 2685 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 2686 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2687 | 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| 2688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2689 | Originator Address | 2690 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2691 |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number | 2692 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2693 |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| 2694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2695 |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| 2696 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2697 |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| 2698 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2699 |0 0 0 0 0 0 1 1| Head | 2700 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2701 | Mid 0 | Mid 1 | Mid 2 | Mid 3 | 2702 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2703 | Mid 4 |0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0| LOCAL_IF | 2704 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2705 |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 | 2706 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2707 | 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| 2708 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2709 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 2710 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2711 | LOST | 2712 +-+-+-+-+-+-+-+-+ 2714 Note that this example is for illustrative purposes. The essential 2715 information can be conveyed, more efficiently (assuming that the 2716 local interface address will be supplied by IP, and that the 2717 INTERVAL_TIME TLV is not needed) by the 29 octets: 2719 0 1 2 3 2720 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 2721 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2722 | 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| 2723 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2724 |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| 2725 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2726 |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| 2727 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2728 |0 0 0 0 0 0 1 1| Head | 2729 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2730 | Mid 1 | Mid 2 | Mid 3 | Mid 4 | 2731 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2732 |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| 2733 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2734 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 2735 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2736 | LOST | 2737 +-+-+-+-+-+-+-+-+ 2739 Appendix D. Flow and Congestion Control 2741 This protocol specifies one Message Type, the HELLO message. The 2742 maximum size of a HELLO message is proportional to the size of the 2743 originating router's 1-hop neighborhood. HELLO messages MUST NOT be 2744 forwarded. 2746 A router MUST report its 1-hop neighborhood in HELLO messages on each 2747 of its MANET interfaces at least each REFRESH_INTERVAL. This puts a 2748 lower bound on the control traffic generated by each router in the 2749 network employing this protocol. 2751 A router MUST ensure that two successive HELLO messages sent on the 2752 same MANET interface are separated by at least HELLO_MIN_INTERVAL. 2753 (If using jitter then this may be reduced to a mean minimum value of 2754 HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound 2755 on the control traffic generated by each router in the network 2756 employing this protocol. 2758 Authors' Addresses 2760 Thomas Heide Clausen 2761 LIX, Ecole Polytechnique 2763 Phone: +33 6 6058 9349 2764 EMail: T.Clausen@computer.org 2765 URI: http://www.ThomasClausen.org/ 2766 Christopher Dearlove 2767 BAE Systems ATC 2769 Phone: +44 1245 242194 2770 EMail: chris.dearlove@baesystems.com 2771 URI: http://www.baesystems.com/ 2773 Justin W. Dean 2774 Naval Research Laboratory 2776 Phone: +1 202 767 3397 2777 EMail: jdean@itd.nrl.navy.mil 2778 URI: http://pf.itd.nrl.navy.mil/ 2780 The OLSRv2 Design Team 2781 MANET Working Group