idnits 2.17.1 draft-ietf-manet-nhdp-13.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. 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 -- 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 (July 12, 2010) is 5035 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: 1 error (**), 0 flaws (~~), 1 warning (==), 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: January 13, 2011 BAE Systems ATC 6 J. Dean 7 Naval Research Laboratory 8 The OLSRv2 Design Team 9 MANET Working Group 10 July 12, 2010 12 Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP) 13 draft-ietf-manet-nhdp-13 15 Abstract 17 This document describes a 1-hop and symmetric 2-hop neighborhood 18 discovery protocol (NHDP) for mobile ad hoc networks (MANETs). 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on January 13, 2011. 37 Copyright Notice 39 Copyright (c) 2010 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 This document may contain material from IETF Documents or IETF 53 Contributions published or made publicly available before November 54 10, 2008. The person(s) controlling the copyright in some of this 55 material may not have granted the IETF Trust the right to allow 56 modifications of such material outside the IETF Standards Process. 57 Without obtaining an adequate license from the person(s) controlling 58 the copyright in such materials, this document may not be modified 59 outside the IETF Standards Process, and derivative works of it may 60 not be created outside the IETF Standards Process, except to format 61 it for publication as an RFC or to translate it into languages other 62 than English. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 67 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 68 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 69 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 70 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 10 71 4.1. Routers and Interfaces . . . . . . . . . . . . . . . . . . 11 72 4.2. Information Base Overview . . . . . . . . . . . . . . . . 12 73 4.2.1. Local Information Base . . . . . . . . . . . . . . . . 12 74 4.2.2. Interface Information Bases . . . . . . . . . . . . . 13 75 4.2.3. Neighbor Information Base . . . . . . . . . . . . . . 14 76 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 14 77 4.3.1. HELLO Message Generation . . . . . . . . . . . . . . . 15 78 4.3.2. HELLO Message Content . . . . . . . . . . . . . . . . 15 79 4.3.3. HELLO Message Processing . . . . . . . . . . . . . . . 17 80 4.4. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 17 81 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 18 82 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 18 83 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 18 84 5.3. Interface Parameters . . . . . . . . . . . . . . . . . . . 18 85 5.3.1. Message Intervals . . . . . . . . . . . . . . . . . . 19 86 5.3.2. Information Validity Times . . . . . . . . . . . . . . 21 87 5.3.3. Link Quality . . . . . . . . . . . . . . . . . . . . . 21 88 5.3.4. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 22 89 5.4. Router Parameters . . . . . . . . . . . . . . . . . . . . 22 90 5.4.1. Information Validity Time . . . . . . . . . . . . . . 22 91 5.5. Parameter Change Constraints . . . . . . . . . . . . . . . 23 92 5.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 24 93 6. Local Information Base . . . . . . . . . . . . . . . . . . . . 24 94 6.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 25 95 6.2. Removed Interface Address Set . . . . . . . . . . . . . . 25 96 7. Interface Information Bases . . . . . . . . . . . . . . . . . 26 97 7.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 26 98 7.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 27 99 8. Neighbor Information Base . . . . . . . . . . . . . . . . . . 28 100 8.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . 28 101 8.2. Lost Neighbor Set . . . . . . . . . . . . . . . . . . . . 28 102 9. Local Information Base Changes . . . . . . . . . . . . . . . . 29 103 9.1. Adding an Interface . . . . . . . . . . . . . . . . . . . 29 104 9.2. Removing an Interface . . . . . . . . . . . . . . . . . . 29 105 9.3. Adding a Network Address to an Interface . . . . . . . . . 30 106 9.4. Removing a Network Address from an Interface . . . . . . . 31 107 10. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 31 108 10.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 32 109 10.1.1. Address Blocks . . . . . . . . . . . . . . . . . . . . 32 110 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 34 111 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 34 112 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 37 113 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 37 114 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 37 115 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 38 116 12.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 39 117 12.3. Updating the Neighbor Set . . . . . . . . . . . . . . . . 40 118 12.4. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 41 119 12.5. Updating the Link Set . . . . . . . . . . . . . . . . . . 42 120 12.6. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 43 121 13. Other Information Base Changes . . . . . . . . . . . . . . . . 45 122 13.1. Link Tuple Symmetric . . . . . . . . . . . . . . . . . . . 46 123 13.2. Link Tuple Not Symmetric . . . . . . . . . . . . . . . . . 46 124 13.3. Link Tuple Heard Timeout . . . . . . . . . . . . . . . . . 47 125 14. Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . 47 126 14.1. Deployment Without Link Quality . . . . . . . . . . . . . 48 127 14.2. Basic Principles of Link Quality . . . . . . . . . . . . . 48 128 14.3. When Link Quality Changes . . . . . . . . . . . . . . . . 49 129 14.4. Updating Link Quality . . . . . . . . . . . . . . . . . . 50 130 15. Proposed Values for Parameters and Constants . . . . . . . . . 50 131 15.1. Message Interval Interface Parameters . . . . . . . . . . 50 132 15.2. Information Validity Time Interface Parameters . . . . . . 51 133 15.3. Information Validity Time Router Parameters . . . . . . . 51 134 15.4. Link Quality Interface Parameters . . . . . . . . . . . . 51 135 15.5. Jitter Interface Parameters . . . . . . . . . . . . . . . 51 136 15.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 51 137 16. Usage with Other Protocols . . . . . . . . . . . . . . . . . . 51 138 17. Security Considerations . . . . . . . . . . . . . . . . . . . 54 139 17.1. Invalid HELLO Messages . . . . . . . . . . . . . . . . . . 55 140 17.2. Authentication, Integrity and Confidentiality 141 Suggestions . . . . . . . . . . . . . . . . . . . . . . . 56 142 18. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 57 143 18.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 57 144 18.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 57 145 18.3. Message-Type-Specific TLV Type Registries . . . . . . . . 57 146 18.4. Address Block TLV Types . . . . . . . . . . . . . . . . . 58 147 18.5. LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Values . . . . . . 59 148 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 60 149 20. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 60 150 21. References . . . . . . . . . . . . . . . . . . . . . . . . . . 61 151 21.1. Normative References . . . . . . . . . . . . . . . . . . . 61 152 21.2. Informative References . . . . . . . . . . . . . . . . . . 61 153 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 61 154 Appendix B. Constraints . . . . . . . . . . . . . . . . . . . . . 62 155 Appendix C. HELLO Message Example . . . . . . . . . . . . . . . . 65 156 Appendix D. Flow and Congestion Control . . . . . . . . . . . . . 67 157 Appendix E. Interval and Timer Illustrations . . . . . . . . . . 68 158 E.1. HELLO Message Generation Timing . . . . . . . . . . . . . 68 159 E.2. HELLO Message Processing Timing . . . . . . . . . . . . . 74 160 E.3. Other HELLO Message Timing . . . . . . . . . . . . . . . . 75 161 Appendix F. Topology Pictures . . . . . . . . . . . . . . . . . . 77 162 F.1. Example 1: Standard Single Interface Topology . . . . . . 77 163 F.2. Example 2: Dual Addressed Interface on 1-Hop Neighbor . . 78 164 F.3. Example 3: Dual Addressed Interface on 2-Hop Neighbor . . 79 165 F.4. Example 4: Dual Addressed Interfaces . . . . . . . . . . . 79 166 F.5. Example 5: Dual Interface on 2-Hop Neighbor . . . . . . . 80 167 F.6. Example 6: Dual interface on 1-Hop Neighbor . . . . . . . 80 168 F.7. Example 7: Dual Interface on 1-Hop and 2-Hop Neighbors . . 81 169 F.8. Example 8: Dual Interface Locally and on 1-Hop Neighbor . 82 170 F.9. Example 9: Dual Interface on All Routers . . . . . . . . . 82 171 F.10. Example 10: Dual Addressed Dual Interfaces on All 172 Routers . . . . . . . . . . . . . . . . . . . . . . . . . 83 173 F.11. Example 11: Single Addressed Dual Interface Locally . . . 84 175 1. Introduction 177 This document describes a neighborhood discovery protocol (NHDP) for 178 a mobile ad hoc network (MANET) [RFC2501]. This protocol uses a 179 local exchange of HELLO messages in order that each router can 180 determine the presence of, and connectivity to, its 1-hop and 181 symmetric 2-hop neighbors. Messages are defined and sent in packets 182 according to the specification [RFC5444]. 184 1-hop neighborhood information is recorded for use by MANET routing 185 protocols to determine direct (1-hop) connectivity to neighboring 186 routers. 2-hop symmetric neighborhood information is recorded so as 187 to enable MANET routing protocols to employ flooding reduction 188 techniques, e.g., to select reduced relay sets for use for network 189 wide link state advertisements. 191 1-hop and symmetric 2-hop neighborhood information is recorded in the 192 form of Information Bases. These are available for use by other 193 protocols, such as MANET routing protocols, which require information 194 regarding the local network connectivity. This protocol is designed 195 to maintain the information in these Information Bases even in the 196 presence of a dynamic network topology and wireless communication 197 channel characteristics. 199 This protocol makes no assumptions about the underlying link layer, 200 other than support of local broadcast or multicast for communication 201 to 1-hop neighbor routers. Link layer information may be used if 202 available and applicable. 204 This protocol is based on the neighborhood discovery process 205 contained in the Optimized Link State Routing Protocol (OLSR) 206 [RFC3626]. 208 1.1. Motivation 210 MANETs differ from more traditional wired and infrastructure-based 211 wireless networks, due to their envisioned applicability also over 212 more challenging communication channels (e.g., wireless, lossy, 213 broadcast channels with moderate and shared bandwidth, hidden and 214 exposed terminals and interference from other network devices and the 215 environment) and in more challenging topological conditions (e.g., 216 rapid and unpredictable mobility, dynamic and non-predetermined 217 network membership). 219 Due to the properties of wireless transmissions, communication 220 between two neighboring routers may not be bi-directional; even if 221 router A is able to receive packets from router B, the converse is 222 not guaranteed to be true. Furthermore, because of the localized 223 nature of wireless broadcast communication, neighboring routers 224 within the same communications channel may have different sets of 225 neighbors. That is, when using the same communication channel, even 226 if router A is able to exchange packets with router B and router B is 227 able to exchange packets with router C, then this does not guarantee 228 that router A and router C can exchange packets directly. 230 Each router in a MANET may use more than one communication channel. 231 In particular, between the same pair of routers, more than one 232 distinct communication channel may exist, each with different 233 properties. This may, for example, be the case where MANET routers 234 are equipped with multiple distinct wireless interfaces, operating at 235 different frequencies. 237 For use by MANET routing protocols, as well as for establishing a 238 router's neighbors, a router may also need to determine whether each 239 communication channel with that neighbor is bi-directional. 241 The set of neighbor routers of a given MANET router may be 242 continuously changing, often due to router mobility or a changing 243 physical environment in which the MANET is located. There is 244 typically no information from lower layers which would enable an IP 245 routing protocol to detect and, as appropriate, react to such 246 changes. Such changes can often take place on a short timescale, 247 such as of the order of seconds, requiring MANET routing protocols to 248 act rapidly to ensure suitable convergence properties. 250 MANET routing protocols, for example [RFC3626] and [RFC5449], often 251 employ relay set reductions in order to conserve network capacity 252 when maintaining network-wide topological information, with 253 calculation of these reduced relay sets employing up to two hop 254 information. 256 The neighborhood discovery protocol specified in this document 257 provides continued tracking of neighborhood changes, link bi- 258 directionality, and local topological information up to two hops. 259 Combined, this allows a MANET routing protocol access to information 260 describing link establishment/disappearance, and provides the 261 necessary topological information for reduced relay set selection and 262 other purposes. 264 2. Terminology 266 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 267 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 268 "OPTIONAL" in this document are to be interpreted as described in 269 [RFC2119]. 271 All terms introduced in [RFC5444], including "packet", "message", 272 "Address Block", "TLV Block", "TLV", "address", "address prefix", and 273 "address object" are to be interpreted as described therein. 275 Additionally, this document uses the following terminology: 277 Network Address - An address plus an associated prefix length. This 278 may be an address with an associated maximum prefix length, or an 279 address prefix including a prefix length. A Network Address thus 280 represents a range of addresses. 282 Router - A MANET router which implements this neighborhood discovery 283 protocol. 285 Interface - A network device, configured and assigned one or more 286 addresses. 288 MANET interface - An interface participating in a MANET and using 289 this neighborhood discovery protocol. A router may have several 290 MANET interfaces. 292 Heard - A MANET interface of router X is considered heard on a MANET 293 interface of a router Y if the latter can receive control 294 messages, according to this specification, from the former. 296 Link - A link between two MANET interfaces exists if either can be 297 heard by the other. 299 Symmetric link - A symmetric link between two MANET interfaces 300 exists if both can be heard by the other. 302 1-hop neighbor - A router X is a 1-hop neighbor of a router Y if a 303 MANET interface of router X is heard by a MANET interface of 304 router Y. 306 Symmetric 1-hop neighbor - A router X is a symmetric 1-hop neighbor 307 of a router Y if a symmetric link exists between a MANET interface 308 on router X and a MANET interface on router Y. 310 2-hop neighbor - A router X is a 2-hop neighbor of a router Y if 311 router X is a 1-hop neighbor of a 1-hop neighbor of router Y, but 312 is not router Y itself. 314 Symmetric 2-hop neighbor - A router X is a symmetric 2-hop neighbor 315 of a router Y if router X is a symmetric 1-hop neighbor of a 316 symmetric 1-hop neighbor of router Y, but is not router Y itself. 318 1-hop neighborhood - The 1-hop neighborhood of a router X is the set 319 of the 1-hop neighbors of router X. 321 Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a 322 router X is the set of the symmetric 1-hop neighbors of router X. 324 2-hop neighborhood - The 2-hop neighborhood of a router X is the set 325 of the 2-hop neighbors of router X. (This may include routers in 326 the 1-hop neighborhood of router X.) 328 Symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of a 329 router X is the set of the symmetric 2-hop neighbors of router X. 330 (This may include routers in the 1-hop neighborhood, or even in 331 the symmetric 1-hop neighborhood, of router X.) 333 Constant - A numerical value which MUST be the same for all MANET 334 interfaces of all routers in the MANET, at all times. 336 Interface parameter - A boolean or numerical value, specified 337 separately for each MANET interface of each router. A router MAY 338 change interface parameter values at any time, subject to some 339 constraints. 341 Router parameter - A boolean or numerical value, specified for each 342 router, and not specific to an interface. A router MAY change 343 router parameter values at any time, subject to some constraints. 345 Information Base - A collection of information maintained by this 346 protocol, and which is to be made available to MANET routing 347 protocols. An Information Base may be associated with a MANET 348 interface, or with a router. 350 Furthermore, this document uses the following notational conventions: 352 X contains y, or y is contained in X, is an unordered list 353 membership operator. X is an unordered list and y is an element. 354 "X contains y" or "y is contained in X" returns true if the 355 unordered list X includes the element y, and returns false 356 otherwise. 358 X contains Y, or Y is contained in X, is an unordered list inclusion 359 operator. X and Y are both unordered lists. "X contains Y" or "Y 360 is contained in X" returns true if the unordered list X contains 361 all elements y which are contained in Y, and returns false 362 otherwise. 364 A overlaps B, if A and B are network addresses, and the range of 365 addresses represented by A, and the range of addresses represented 366 by B both contain at least one common address. (This is only 367 possible if one range is a sub-range of the other.) 369 a := b, is an assignment operator, whereby the left side (a) is 370 assigned the value of the right side (b). a and b may be values, 371 network addresses, or unordered lists (they must be of the same 372 type). 374 c = d, is a comparison operator, returning true if the value of the 375 left side (c) is equal to the value of the right side (d). c and d 376 may be values, network addresses, or unordered lists (they must be 377 of the same type). If c and d are unordered lists, then they are 378 considered to be equal if c contains d and d contains c (i.e., 379 they contain the same set of elements, regardless of the order in 380 which they are recorded in the lists). If c and d are network 381 addresses, they are considered equal only if both addresses and 382 prefix lengths are equal (i.e., they represent the same ). 384 e != f, is a comparison operator, returning not (e = f). i.e., 385 returning true where (e = f) would have returned false, and 386 returning false where (e = f) would have returned true. 388 3. Applicability Statement 390 This protocol: 392 o Is applicable to networks, especially wireless networks, in which 393 unknown neighbors can be reached by local broadcast or multicast 394 packets. 396 o Is designed to work in networks with a dynamic topology, and in 397 which messages may be lost, such as due to collisions in wireless 398 networks. 400 o Supports routers that each have one or more participating MANET 401 interfaces. The set of a router's interfaces may change over 402 time. Each interface may have one or more associated network 403 addresses, and these may also be dynamically changing. 405 o Provides each router with current local topology information up to 406 two hops away, and makes this local topology information available 407 to MANET routing protocols in Information Bases. 409 o Uses the packet and message formats specified in [RFC5444]. This 410 includes the definition of a HELLO Message Type, used for 411 signaling local topology information. 413 o Allows "external" and "internal" extensibility as enabled by 414 [RFC5444]. 416 o May interact with, and be extended by, other protocols, such as 417 MANET routing protocols, see Section 16. 419 o Can use relevant link layer information if it is available. 421 o Is designed to work in a completely distributed manner, and does 422 not depend on any central entity. 424 4. Protocol Overview and Functioning 426 The objective of this protocol is, for each router: 428 o To identify 1-hop neighbors and symmetric 1-hop neighbors of this 429 router. 431 o To find the interface network addresses of the router's symmetric 432 2-hop neighbors. 434 o To record this information in Information Bases and thus make this 435 information available to other protocols that use this 436 neighborhood discovery protocol. 438 o To be available for use by other protocols, which MAY extend the 439 information in these Information Bases, including adding new Sets 440 to Information Bases, new elements to protocol Tuples and new TLVs 441 to be included in outgoing HELLO messages and processed when in 442 incoming HELLO messages. 444 These objectives are achieved using local (1-hop) signaling that: 446 o Advertises the presence of a router and its interface network 447 addresses. 449 o Discovers links from neighboring routers. 451 o Performs bi-directionality checks on the discovered links. 453 o Advertises discovered links, and whether each is symmetric, to its 454 1-hop neighbors, and hence discovers symmetric 2-hop neighbors. 456 This specification defines, in turn: 458 o Parameters and constants used by the protocol. Parameters used by 459 this protocol may, where appropriate, be specific to a given MANET 460 interface, or to a MANET router. This protocol allows all 461 parameters to be changed dynamically, and to be set independently 462 for each MANET router or MANET interface, as appropriate. 464 o The Information Bases describing local interfaces, discovered 465 links and their status, current and former 1-hop neighbors, and 466 symmetric 2-hop neighbors. 468 o The format of the HELLO message that is used for local signaling. 470 o The generation of HELLO messages from some of the information in 471 the Information Bases. 473 o The updating of the Information Bases according to received HELLO 474 messages and other events. 476 o The response to other events, such as the expiration of 477 information in the Information Bases. 479 4.1. Routers and Interfaces 481 In order for a router to participate in a MANET, it MUST have at 482 least one, and possibly more, MANET interfaces. 484 Each MANET interface: 486 o Is configured with one or more network addresses. All addresses 487 represented by these network addresses MUST be unique to this 488 router. All such addresses MUST be unique to this MANET 489 interface, except that an address can be used by more than one 490 MANET interface on the same router if those MANET interfaces are 491 "isolated" from each other (no MANET interface on another router 492 can communicate to, from, or one to and one from, two MANET 493 interfaces using overlapping network addresses). 495 o Has a set of interface parameters, defining the behavior of this 496 MANET interface. Each MANET interface MAY be individually 497 parameterized. 499 o Has an Interface Information Base, recording information regarding 500 links to this MANET interface and symmetric 2-hop neighbors which 501 can be reached through such links. 503 o Generates and processes HELLO messages. 505 In addition to a set of MANET interfaces as described above, each 506 router has: 508 o A Local Information Base, containing the network addresses of the 509 interfaces (MANET and non-MANET) of this router. The contents of 510 this Information Base are not changed by signaling. 512 o A Neighbor Information Base, recording information regarding 513 current and recently lost 1-hop neighbors of this router. 515 A router may have both MANET interfaces and non-MANET interfaces. 516 Interfaces of both of these types are recorded in a router's Local 517 Information Base, which is used, but not updated, by the signaling of 518 this protocol. 520 4.2. Information Base Overview 522 Each router maintains the Information Bases described in the 523 following sections. These are used for describing the protocol in 524 this document. An implementation of this protocol MAY maintain this 525 information in the indicated form, or in any other organization which 526 offers access to this information. In particular, note that it is 527 not necessary to remove Tuples from Sets at the exact time indicated, 528 only to behave as if the Tuples were removed at that time. 530 Information in the Local Information Base is defined locally, and 531 included in HELLO messages. Information in the Interface Information 532 Base and the Neighbor Information Base is determined from received 533 HELLO messages; some of this information may also be included in 534 transmitted HELLO messages. Such information has a limited duration 535 in which it is considered valid. This duration is determined from 536 the VALIDITY_TIME TLV in the HELLO message in which the information 537 is received, which in turn is set by the router that originated the 538 HELLO message, using its corresponding interface parameter 539 H_HOLD_TIME. 541 Appendix E illustrates the relationship between message reception, 542 included VALIDITY_TIME TLVs, and the duration for which information 543 received in a HELLO message is considered valid. Appendix F 544 illustrates some example topologies and how they correspond to 545 information in the Information Bases. 547 4.2.1. Local Information Base 549 Each router maintains a Local Information Base, which contains the 550 router's local configuration information, specifically: 552 o The Local Interface Set, which consists of Local Interface Tuples, 553 each of which represents an interface (MANET or non-MANET) of the 554 router. 556 o The Removed Interface Address Set, which consists of Removed 557 Interface Address Tuples, each of which records a recently used 558 network address of an interface (MANET or non-MANET) of the 559 router. 561 The Local Interface Set is used for generating HELLO messages, 562 specifically for determining which interface network addresses are to 563 be included and identified as local interfaces. The Removed 564 Interface Address Set is used to avoid incorrectly recording a 565 formerly used network address as a symmetric 2-hop neighbor's network 566 address. 568 The Local Information Base is used for generating signaling, but is 569 not itself updated by signaling specified in this document. Updates 570 to the Local Information Base are due to changes of the router 571 configuration, and may be allowed to trigger signaling. 573 4.2.2. Interface Information Bases 575 Each router maintains, for each of its MANET interfaces, an Interface 576 Information Base, which contains 1-hop neighborhood and symmetric 577 2-hop neighborhood information collected from this MANET interface, 578 specifically: 580 o A Link Set, which records information about current and recently 581 lost links between this MANET interface and MANET interfaces of 582 1-hop neighbors. The Link Set consists of Link Tuples, each of 583 which contains information about a single link. Link quality 584 information (see Section 14), when used, is recorded in Link 585 Tuples. 587 o A 2-Hop Set, which records the existence of symmetric links 588 between symmetric 1-hop neighbors of this MANET interface and 589 other routers (symmetric 2-hop neighbors). The 2-Hop Set consists 590 of 2-Hop Tuples, each of which records a network address of a 591 symmetric 2-hop neighbor, and all network addresses of the 592 corresponding symmetric 1-hop neighbor. 594 The Link Set for a MANET interface is used for generating HELLO 595 messages. Specifically, the Link Set information is included to both 596 allow other routers to identify symmetric links and to populate the 597 2-Hop Set. Recently lost links are recorded in the Link Set for a 598 MANET interface so that they can be advertised in HELLO messages, 599 accelerating their removal from relevant 1-hop neighbors' Link Sets. 601 The Link Set for a MANET interface is itself updated on receiving a 602 HELLO message, including recording symmetric links as indicated 603 above. The 2-Hop Set for a MANET interface is updated as indicated 604 above, and is not itself used in generating HELLO messages. 606 4.2.3. Neighbor Information Base 608 Each router maintains a Neighbor Information Base, which contains 609 collected information about current and recently lost 1-hop 610 neighbors, specifically: 612 o The Neighbor Set consists of Neighbor Tuples, each of which 613 records all network addresses of a single 1-hop neighbor. 614 Neighbor Tuples are maintained as long as there are corresponding 615 Link Tuples. 617 o The Lost Neighbor Set consists of Lost Neighbor Tuples, each of 618 which records a network address of a recently lost symmetric 1-hop 619 neighbor. 621 The Neighbor Set associates all network addresses of each 1-hop 622 neighbor. These network addresses may be included when generating a 623 HELLO message, so that other symmetric 1-hop neighbors can record 624 this information in a 2-Hop Set. The Neighbor Set can be updated on 625 receiving a HELLO message. 627 The Lost Neighbor Set is used to determine which network addresses 628 are to be included in a HELLO message as being lost (of a recently 629 symmetric 1-hop neighbor). The Lost Neighbor Set can itself be 630 updated on receiving a HELLO message. 632 4.3. Signaling Overview 634 This protocol contains a signaling mechanism for maintaining the 635 Interface Information Bases and the Neighbor Information Base. If 636 information from the link layer, or any other source, is available 637 and appropriate, it may also be used to update these Information 638 Bases. Such updates are subject to the constraints specified in 639 Appendix B. 641 Signaling consists of a single type of message, known as a HELLO 642 message. Each router generates HELLO messages on each of its MANET 643 interfaces. HELLO messages are generated independently on each MANET 644 interface of a MANET router; the content of a given HELLO message 645 depends on the MANET interface for which it has been generated. 647 Each HELLO message: 649 o Identifies, as far as is required, the MANET interface for which 650 it is generated and transmitted; this allows recipients of that 651 HELLO message to identify that MANET interface from among those it 652 may hear. 654 o Reports the network addresses of other interfaces (MANET and non- 655 MANET) of the router; this allows recipients of that HELLO message 656 to associate a set of network addresses with a single 1-hop 657 neighbor. 659 o Includes 1-hop neighbor information from the Information Bases; 660 this allows detection of local symmetric links, and symmetric 661 2-hop neighbors. 663 HELLO message generation, and the validity of the information 664 recorded as a consequence of processing a HELLO message, is affected 665 by timers and validity information included in HELLO messages through 666 TLVs. The relationship between message timers and intervals is 667 illustrated in Appendix E. 669 4.3.1. HELLO Message Generation 671 HELLO messages are generated by a router for each of its MANET 672 interfaces, and MAY be sent: 674 o Proactively, at a regular interval, known as HELLO_INTERVAL. 675 HELLO_INTERVAL may be fixed, or may be dynamic. For example 676 HELLO_INTERVAL may be backed off due to congestion or network 677 stability. 679 o As a response to a change in the router itself, or its 1-hop 680 neighborhood, for example on first becoming active or in response 681 to a new, lost, or changed status link. 683 o In a combination of these proactive and responsive mechanisms. 685 Jittering of HELLO message generation and transmission SHOULD be used 686 as described in Section 11.2, unless the medium access control 687 mechanism in use prevents any simultaneous transmissions by 688 potentially interefering routers. 690 HELLO messages MAY be scheduled independently for each MANET 691 interface, or, interface parameters permitting, using the same 692 schedule for all MANET interfaces of a router. 694 4.3.2. HELLO Message Content 696 The content of a HELLO message MUST satisfy the following: 698 o A HELLO message MUST contain all of the network addresses in the 699 Local Interface Set of the router on which the HELLO message is 700 being generated. This includes: 702 o At least one network address of each MANET interface of the 703 router. 705 o Network addresses that include all source addresses of any IP 706 datagrams sent by the router on any MANET interface. 708 o All other network addresses of the router which are to be made 709 known to any other router for any reason. 711 o For each MANET interface, within every time interval equal to the 712 corresponding REFRESH_INTERVAL, sent HELLO messages MUST 713 collectively include all of the relevant information in the 714 corresponding Link Set and the Neighbor Information Base. Note 715 that when determining whether to include information in a HELLO 716 message, the sender MUST consider all times up to the latest time 717 when it may send its next HELLO message on this MANET interface. 719 o For each MANET interface, within every time interval equal to the 720 corresponding REFRESH_INTERVAL, sent HELLO messages MUST 721 collectively include all of the relevant information in the 722 corresponding Link Set and the Neighbor Information Base. 724 o When determining whether to include a given piece of neighbor 725 information in a HELLO message, it is not sufficient to consider 726 whether that information has been sent in the interval of length 727 REFRESH_INTERVAL up to the current time. Instead, the router MUST 728 consider the interval of length REFRESH_INTERVAL that will end at 729 the latest possible time at which the next HELLO message will be 730 sent on this MANET interface. (Normally, this will be 731 HELLO_INTERVAL past the current time, but MAY be earlier if this 732 router elects to divide its neighbor information among more than 733 one HELLO message in order to reduce the size of its HELLO 734 messages.) All neighbor information MUST be sent in this 735 interval, i.e., the router MUST ensure that this HELLO message 736 includes all neighbour information that has not already been 737 included in any HELLO messages sent since the start of this 738 interval (normally the current time - (REFRESH_INTERVAL - 739 HELLO_INTERVAL)). 741 o A HELLO message MUST include exactly one VALIDITY_TIME Message 742 TLV, as specified in [RFC5497], that indicates the length of time 743 for which the message content is to be considered valid, and is 744 therefore to be included in the receiving router's Interface 745 Information Base. 747 o A periodically generated HELLO message SHOULD include exactly one 748 INTERVAL_TIME Message TLV, as specified in [RFC5497], that 749 indicates the current value of HELLO_INTERVAL for that MANET 750 interface, i.e., the period within which a further HELLO message 751 is guaranteed to be sent on that MANET interface. 753 4.3.3. HELLO Message Processing 755 HELLO messages received by a router are used to update the Interface 756 Information Base for the MANET interface over which that HELLO 757 message was received, as well as the Neighbor Information Base of the 758 router. Specifically: 760 o The router ensures that there is a single Neighbor Tuple 761 corresponding to the originator of that HELLO message. 763 o The router ensures that there is a Link Tuple, with appropriate 764 status (heard or symmetric) and advertised duration, corresponding 765 to the link between the MANET interfaces on which that HELLO 766 message was sent and received. One or more Lost Neighbor Tuples 767 may be created if the HELLO message reports that the link was 768 lost. 770 o If the link between the MANET interfaces on which the HELLO 771 message was sent and received is symmetric, then the router 772 ensures that there are the appropriate 2-Hop Tuples, with 773 advertised duration. 775 The processing defined in this specification handles any unexpected 776 and erroneous information in a HELLO message, maintaining the 777 constraints on Information Base contents specified in Appendix B. 779 4.4. Link Quality 781 Some links in a MANET may be marginal, e.g., due to adverse wireless 782 propagation. In order to avoid using such marginal links, a link 783 quality value is recorded in each Link Tuple. A MANET router 784 considers links for which an insufficient link quality is recorded as 785 lost. Modifying the recorded link quality in a Link Tuple is 786 OPTIONAL. If link quality is not to be modified it MUST be set to 787 indicate an always usable quality link. 789 Note that Link Quality is a "link admittance" mechanism, allowing a 790 router to determine that a given link is too unstable to even 791 consider for use. It is specifically not a link metric nor a 792 substitute for one. 794 Link quality information is only used locally and is not used in 795 signaling. Routers may interoperate whether they are using the same, 796 different, or no, link quality information. Link quality information 797 is thus not equivalent to a link metric. 799 Link quality information is defined in this specification as a 800 normalised, dimensionless, value in the interval zero to one, 801 inclusive, where the greater the value, the better the link quality. 802 See Section 14 for further details. 804 5. Protocol Parameters and Constants 806 The parameters and constants used in this specification are described 807 in this section. 809 5.1. Protocol and Port Numbers 811 This protocol specifies HELLO messages, which are included in packets 812 as defined by [RFC5444]. These packets may be sent either using the 813 "manet" protocol number or the "manet" well-known UDP port number, as 814 specified in [RFC5498]. 816 5.2. Multicast Address 818 This protocol specifies HELLO messages, which are included in packets 819 as defined by [RFC5444]. These packets may be locally transmitted 820 using the link local multicast address "LL-MANET-Routers", as 821 specified in [RFC5498]. 823 5.3. Interface Parameters 825 The interface parameters used by this specification may be classified 826 into the following four categories: 828 o Message intervals 830 o Information validity times 832 o Link quality 834 o Jitter 836 These are detailed in the following sections. 838 Different MANET interfaces (on the same or on different routers) MAY 839 employ different interface parameter values, and MAY change their 840 interface parameter values dynamically, subject to the constraints 841 given in this section. A particular case is where all MANET 842 interfaces on all MANET routers within a given MANET employ the same 843 set of interface parameter values. 845 5.3.1. Message Intervals 847 HELLO messages serve two principal functions: 849 o To advertise network addresses of this router's interface to its 850 1-hop neighbors. The frequency of these advertisements is 851 regulated by the interface parameters HELLO_INTERVAL and 852 HELLO_MIN_INTERVAL. 854 o To advertise this router's knowledge of each of its 1-hop 855 neighbors. The frequency of the advertisement of each such 856 neighbor is regulated by the interface parameter REFRESH_INTERVAL. 858 Specifically, these parameters are as follows: 860 HELLO_INTERVAL - is the maximum time between the transmission of two 861 successive HELLO messages on this MANET interface. If using 862 periodic transmission of HELLO messages, these SHOULD be at a 863 separation of HELLO_INTERVAL, possibly modified by jitter as 864 specified in [RFC5148]. 866 HELLO_MIN_INTERVAL - is the minimum interval between transmission of 867 two successive HELLO messages, on this MANET interface. (This 868 minimum interval MAY be modified by jitter, as defined in 869 [RFC5148].) 871 REFRESH_INTERVAL - is the maximum interval between advertisements, 872 in a HELLO message on this MANET interface, of each 1-hop neighbor 873 network address and its status. In all intervals of length 874 REFRESH_INTERVAL, a router MUST include each 1-hop neighbor 875 network address and its status in at least one HELLO message on 876 this MANET interface. (This may be in the same or in different 877 HELLO messages.) 879 REFRESH_INTERVAL thus represents the frequency at which a piece of 880 information, as received in HELLO messages, can be expected to be 881 refreshed. Thus, the REFRESH_INTERVAL is used as a basis for 882 determining when such information expires in receiving routers (see 883 Section 5.3.2). HELLO_INTERVAL represents the frequency of HELLO 884 message emissions. Logically, HELLO_INTERVAL cannot be greater than 885 the REFRESH_INTERVAL, otherwise information cannot be refreshed in a 886 timely manner. 888 HELLO messages can, however, be sent with a higher frequency. A 889 possible use for sending HELLO messages at such a higher frequency 890 includes sending partial HELLO messages (e.g., accommodating 891 constraints on packet sizes from the underlying medium) refreshing 892 only part of the information in each HELLO message. Another use is 893 for a router to send "empty HELLO messages", advertising its own 894 presence frequently in smaller HELLO messages (e.g., in case HELLO 895 message exchange success rates are used for link quality estimation, 896 or to enable rapid detection by new routers in the neighborhood) in 897 between HELLO messages refreshing neighbor information in other 898 routers. 900 The following constraints apply to these interface parameters: 902 o HELLO_INTERVAL > 0 904 o HELLO_MIN_INTERVAL >= 0 906 o HELLO_INTERVAL >= HELLO_MIN_INTERVAL 908 o REFRESH_INTERVAL >= HELLO_INTERVAL 910 o If an INTERVAL_TIME Message TLV as defined in [RFC5497] is 911 included in a HELLO messages, then HELLO_INTERVAL MUST be 912 representable as described in [RFC5497]. 914 If REFRESH_INTERVAL > HELLO_INTERVAL, then a router may distribute 915 its neighbor advertisements between HELLO messages in any manner, 916 subject to the constraints above. 918 In the absence of any changes to the local neighborhood, a router 919 will send a HELLO message on a MANET interface after a (possibly 920 jittered) interval of length HELLO_INTERVAL. For a router to employ 921 this protocol in a purely responsive manner on a MANET interface, 922 i.e., for the router to only send HELLO messages on that MANET 923 interface as a response to external events, HELLO_INTERVAL (and hence 924 also REFRESH_INTERVAL) SHOULD be set sufficiently large, i.e., such 925 that a responsive HELLO message is always expected with a shorter 926 period than this value. 928 If a router has more than one MANET interface, then, even if the 929 router configures different values of HELLO_INTERVAL on each MANET 930 interface, the router SHOULD configure the same value of 931 HELLO_MIN_INTERVAL on all MANET interfaces on which responsive HELLO 932 messages may be sent. (This ensures that changes observed on one 933 MANET interface are reported on other MANET interfaces, so that 1-hop 934 neighbors connected to the latter can maintain up to date 2-hop 935 neighborhood information.) 937 5.3.2. Information Validity Times 939 The following interface parameters manage the validity time of link 940 information: 942 L_HOLD_TIME - is the period of advertisement, on this MANET 943 interface, of former 1-hop neighbor network addresses as lost in 944 HELLO messages, allowing recipients of these HELLO messages to 945 accelerate removal of this information from their Link Sets. 946 L_HOLD_TIME MAY be set to zero, if accelerated information removal 947 is not required. 949 H_HOLD_TIME - is used as the Value in the VALIDITY_TIME Message TLV 950 included in all HELLO messages on this MANET interface. It is 951 then used by each router receiving such a HELLO message to 952 indicate the validity of the information taken from that HELLO 953 message and recorded in the receiving router's Information Bases. 955 Note that as each item of neighbor information is included in HELLO 956 messages within an interval of length REFRESH~_INTERVAL, contrainst 957 on H_HOLD_TIME are based on REFRESH_INTERVAL, not on HELLO_INTERVAL. 959 The following constraints apply to these interface parameters: 961 o L_HOLD_TIME >= 0 963 o H_HOLD_TIME >= REFRESH_INTERVAL 965 o If HELLO messages can be lost then both parameters SHOULD be 966 significantly greater than REFRESH_INTERVAL. 968 o H_HOLD_TIME MUST be representable as described in [RFC5497]. 970 5.3.3. Link Quality 972 The following interface parameters manage the usage of link quality 973 (see Section 14): 975 HYST_ACCEPT - is the link quality threshold at or above which a link 976 becomes usable, if it was not already so. 978 HYST_REJECT - is the link quality threshold below which a link 979 becomes unusable, if it was not already so. 981 INITIAL_QUALITY - is the initial quality of a newly identified link. 983 INITIAL_PENDING - if true, then a newly identified link is 984 considered pending, and is not usable until the link quality has 985 reached or exceeded the HYST_ACCEPT threshold. 987 The following constraints apply to these interface parameters: 989 o 0 <= HYST_REJECT <= HYST_ACCEPT <= 1 991 o 0 <= INITIAL_QUALITY <= 1. 993 o If link quality is not updated, then INITIAL_QUALITY >= 994 HYST_ACCEPT. 996 o If INITIAL_QUALITY >= HYST_ACCEPT, then INITIAL_PENDING := false. 998 o If INITIAL_QUALITY < HYST_REJECT, then INITIAL_PENDING := true. 1000 5.3.4. Jitter 1002 If jitter, as defined in [RFC5148], is used then these parameters are 1003 as follows: 1005 HP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 1006 for periodically generated HELLO messages on this MANET interface. 1008 HT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 1009 for externally triggered HELLO messages on this MANET interface. 1011 For constraints on these interface parameters see [RFC5148]. 1013 5.4. Router Parameters 1015 The two router parameters defined by this specification are in the 1016 category of information validity time. 1018 5.4.1. Information Validity Time 1020 The following router parameter manages the validity time of lost 1021 symmetric 1-hop neighbor information: 1023 N_HOLD_TIME - is used as the period during which former 1-hop 1024 neighbor network addresses are advertised as lost in HELLO 1025 messages, allowing recipients of these HELLO messages to 1026 accelerate removal of this information from their 2-Hop Sets. 1027 N_HOLD_TIME MAY be set to zero, if accelerated information removal 1028 is not required. 1030 I_HOLD_TIME - is the period for which a recently used local 1031 interface network address is recorded. 1033 The following constraints applies to these router parameters: 1035 o N_HOLD_TIME >= 0 1037 o I_HOLD_TIME >= 0 1039 5.5. Parameter Change Constraints 1041 If protocol parameters are changed dynamically, the constraints in 1042 this section apply. 1044 HELLO_INTERVAL 1046 o If the HELLO_INTERVAL for a MANET interface increases, then the 1047 next HELLO message on this MANET interface MUST be generated 1048 according to the previous, shorter, HELLO_INTERVAL. A number 1049 of subsequent HELLO messages MAY be generated according to the 1050 previous, shorter, HELLO_INTERVAL (but MUST include times 1051 according to current parameters). This ensures that "promises" 1052 as to timely transmission of a future HELLO message is kept 1053 until these previous promises have expired. 1055 o If the HELLO_INTERVAL for a MANET interface decreases, then the 1056 following HELLO messages on this MANET interface MUST be 1057 generated according to this current, shorter, HELLO_INTERVAL. 1059 REFRESH_INTERVAL 1061 o If the REFRESH_INTERVAL for a MANET interface increases, then 1062 the content of subsequent HELLO messages must be organized such 1063 that the specification of the old value of REFRESH_INTERVAL is 1064 satisfied for a further period equal to the old value of 1065 REFRESH_INTERVAL. 1067 o If the REFRESH_INTERVAL for a MANET interface decreases, then 1068 it MAY be necessary to reschedule HELLO message generation on 1069 that MANET interface, in order that the specification of 1070 REFRESH_INTERVAL is satisfied from the time of change. 1072 HYST_ACCEPT and HYST_REJECT 1074 o If HYST_ACCEPT or HYST_REJECT changes, then the appropriate 1075 actions for link quality change, as specified in Section 14.3, 1076 MUST be taken. 1078 L_HOLD_TIME 1080 o If L_HOLD_TIME changes, then the expiry times of all relevant 1081 Link Tuples MUST be changed. 1083 N_HOLD_TIME 1085 o If N_HOLD_TIME changes, then the expiry times of all relevant 1086 Lost Neighbor Tuples MUST be changed. 1088 HP_MAXJITTER 1090 o If HP_MAXJITTER changes, then the periodic HELLO message 1091 schedule on this MANET interface MAY be changed. 1093 HT_MAXJITTER 1095 o If HT_MAXJITTER changes, then externally triggered HELLO 1096 messages on this MANET interface MAY be rescheduled. 1098 5.6. Constants 1100 The constant C (time granularity) is used as specified in [RFC5497]. 1102 6. Local Information Base 1104 A router maintains a Local Information Base that records information 1105 about its interfaces (MANET and non-MANET). Each interface of a 1106 router MUST be identified by at least one network address. Such 1107 network addresses MAY be specific to that interface, or MAY in some 1108 circumstances be used by more than one interface as specified below. 1110 The Local Information Base is not modified by signaling. If a 1111 router's interface configuration changes, then the Local Information 1112 Base MUST reflect these changes. This MAY also result in signaling 1113 to advertise these changes. 1115 It is not necessary to include all addresses of an interface in the 1116 Local Information Base, and hence in HELLO messages. However any 1117 address that may be the source address of an IP datagram sent from 1118 that interface MUST be included (and at least one address MUST be 1119 included). A protocol using this specification MAY add additional 1120 requirements to these, e.g., that any address that may be the 1121 destination address of an IP datagram is also included. 1123 The addresses assigned to an interface are "owned" by the router, and 1124 MUST NOT be used by any other router as an interface address. If an 1125 address has a prefix length and represents a range of addresses, this 1126 applies to all addresses in that range (i.e., such ranges MUST NOT 1127 overlap). 1129 The addresses assigned to different interfaces on the same router 1130 MUST be distinct (hence network address ranges MUST NOT overlap) 1131 except that: 1133 o The same address MAY be assigned to any number of non-MANET 1134 interfaces as well as to one (or more if the following condition 1135 also applies) MANET interface. 1137 o The same address MAY be assigned to two (or more if each pair 1138 satisfies this condition) MANET interfaces if those two MANET 1139 interfaces cannot communicate to, from, or one to and one from, 1140 any other MANET interface of another router. 1142 6.1. Local Interface Set 1144 A router's Local Interface Set records its local interfaces. It 1145 consists of Local Interface Tuples, one per interface: 1147 (I_local_iface_addr_list, I_manet) 1149 where: 1151 I_local_iface_addr_list - is an unordered list of the network 1152 addresses of this interface. 1154 I_manet - is a boolean flag, describing if this interface is a MANET 1155 interface. 1157 Local Interface Tuples are removed from the Local Interface Set only 1158 when the routers' interface configuration changes, subject to 1159 Section 9, i.e., they are not subject to timer-based expiration. 1161 6.2. Removed Interface Address Set 1163 A router's Removed Interface Address Set records network addresses 1164 which were recently used as local interface network addresses. If a 1165 router's interface network addresses are immutable then the Removed 1166 Interface Address Set is always empty and MAY be omitted. It 1167 consists of Removed Interface Address Tuples, one per network 1168 address: 1170 (IR_local_iface_addr, IR_time) 1172 where: 1174 IR_local_iface_addr - is a recently used network address of an 1175 interface of this router. 1177 IR_time - specifies when this Tuple expires and MUST be removed. 1179 7. Interface Information Bases 1181 A router maintains an Interface Information Base for each of its 1182 MANET interfaces. This records information about links to that MANET 1183 interface and symmetric 2-hop neighbors which can be reached in two 1184 hops using those links as the first hop. Each Interface Information 1185 Base includes a Link Set and a 2-Hop Set. 1187 A network address of a symmetric 2-hop neighbor can also be present 1188 as the network address of a 1-hop neighbor. This allows the router 1189 using this network address to be immediately considered as a 1190 symmetric 2-hop neighbor if it fails to be a symmetric 1-hop 1191 neighbor. 1193 An element which specifies a time is considered expired if the 1194 current time is greater than or equal to that time. One such 1195 element, present in most Tuples, indicates when expired that the 1196 Tuple itself is considered expired and MUST be removed. Tuples which 1197 do not have such a time element are removed at other times as 1198 specified, for example a Neighbor Tuple is removed when all 1199 corresponding Link Tuples have been removed. 1201 7.1. Link Set 1203 An interface's Link Set records links from other routers which are, 1204 or recently were, 1-hop neighbors. It consists of Link Tuples, each 1205 representing a single link: 1207 (L_neighbor_iface_addr_list, L_HEARD_time, L_SYM_time, 1208 L_quality, L_pending, L_lost, L_time) 1210 where: 1212 L_neighbor_iface_addr_list - is an unordered list of the network 1213 addresses of the MANET interface of the 1-hop neighbor; 1215 L_HEARD_time - is the time up to which the MANET interface of the 1216 1-hop neighbor would be considered heard if not considering link 1217 quality; 1219 L_SYM_time - is the time up to which the link to the 1-hop neighbor 1220 would be considered symmetric if not considering link quality; 1222 L_quality - is a dimensionless number between 0 (inclusive) and 1 1223 (inclusive) describing the quality of a link; a greater value of 1224 L_quality indicating a higher quality link; 1226 L_pending - is a boolean flag, describing if a link is considered 1227 pending (i.e., a candidate, but not yet established, link); 1229 L_lost - is a boolean flag, describing if a link is considered lost 1230 due to low link quality; 1232 L_time - specifies when this Tuple expires and MUST be removed. 1234 The status of the link, as obtained through HELLO message exchange 1235 and using link quality, is denoted L_status. L_status can take the 1236 Values PENDING, HEARD, SYMMETRIC and LOST. The values LOST, 1237 SYMMETRIC and HEARD are defined in Section 18.5. The Value PENDING 1238 is never used in a HELLO message, it is only used locally by a 1239 router, and any Value distinct from LOST, SYMMETRIC and HEARD may be 1240 used. 1242 L_status is defined by: 1244 1. If L_pending = true, then L_status := PENDING; 1246 2. otherwise, if L_lost = true, then L_status := LOST; 1248 3. otherwise, if L_SYM_time is not expired, then L_status := 1249 SYMMETRIC; 1251 4. otherwise, if L_HEARD_time is not expired, then L_status := 1252 HEARD; 1254 5. otherwise, L_status := LOST. 1256 7.2. 2-Hop Set 1258 An interface's 2-Hop Set records network addresses of symmetric 2-hop 1259 neighbors, and the symmetric links to symmetric 1-hop neighbors 1260 through which these symmetric 2-hop neighbors can be reached. It 1261 consists of 2-Hop Tuples, each representing a single network address 1262 of a symmetric 2-hop neighbor, and a single MANET interface of a 1263 symmetric 1-hop neighbor. 1265 (N2_neighbor_iface_addr_list, N2_2hop_addr, N2_time) 1267 where: 1269 N2_neighbor_iface_addr_list - is an unordered list of the network 1270 addresses of the MANET interface of the symmetric 1-hop neighbor 1271 from which this information was received; 1273 N2_2hop_addr - is a network address of a symmetric 2-hop neighbor 1274 which has a symmetric link (using any MANET interface) to the 1275 indicated symmetric 1-hop neighbor; 1277 N2_time - specifies when this Tuple expires and MUST be removed. 1279 8. Neighbor Information Base 1281 Each router maintains a Neighbor Information Base that records 1282 information about network addresses of current and recently symmetric 1283 1-hop neighbors. 1285 8.1. Neighbor Set 1287 A router's Neighbor Set records all network addresses of each 1-hop 1288 neighbor. It consists of Neighbor Tuples, each representing a single 1289 1-hop neighbor: 1291 (N_neighbor_addr_list, N_symmetric) 1293 where: 1295 N_neighbor_addr_list - is an unordered list of the network addresses 1296 of a 1-hop neighbor; 1298 N_symmetric - is a boolean flag, describing if this is a symmetric 1299 1-hop neighbor. 1301 Neighbor Tuples are removed from the Neighbor Set only when 1302 corresponding Link Tuples expire from the routers' Link Set, i.e., 1303 Neighbor Tuples are not directly subject to timer-based expiration. 1305 8.2. Lost Neighbor Set 1307 A router's Lost Neighbor Set records network addresses of routers 1308 which recently were symmetric 1-hop neighbors, but which are now 1309 advertised as lost. It consists of Lost Neighbor Tuples, each 1310 representing a single such network address: 1312 (NL_neighbor_addr, NL_time) 1314 where: 1316 NL_neighbor_addr - is a network address of a router which recently 1317 was a symmetric 1-hop neighbor of this router; 1319 NL_time - specifies when this Tuple expires and MUST be removed. 1321 9. Local Information Base Changes 1323 The Local Information Base MUST be updated in response to changes in 1324 the router's local interface configuration. These MAY also change 1325 the Interface Information Base and the Neighbor Information Base. If 1326 any changes to the latter Information Bases satisfy any of the 1327 conditions described in Section 13, then those changes MUST be 1328 applied immediately, unless noted otherwise below. 1330 A router MAY transmit HELLO messages in response to these changes. 1332 9.1. Adding an Interface 1334 If an interface is added to the router, then this is indicated by the 1335 addition of a Local Interface Tuple to the Local Interface Set. If 1336 the new interface is a MANET interface, then an initially empty 1337 Interface Information Base MUST be created for this new MANET 1338 interface. The actions in Section 9.3 MUST be taken for each network 1339 address of this added interface. A HELLO message MAY be sent on all 1340 MANET interfaces, it SHOULD be sent on the new interface if it is a 1341 MANET interface. If using scheduled messages, then a message 1342 schedule MUST be established on the new MANET interface. 1344 9.2. Removing an Interface 1346 If an interface is removed from the router, then this MUST result in 1347 changes to the Local Information Base and to the Neighbor Information 1348 Base as follows: 1350 1. Identify the Local Interface Tuple that corresponds to the 1351 interface to be removed. 1353 2. For each network address (henceforth removed address) in the 1354 I_local_iface_addr_list of that Local Interface Tuple, if that 1355 network address is not in the I_local_iface_addr_list of any 1356 other Local Interface Tuple, then create a Removed Interface 1357 Address Tuple with: 1359 o IR_local_iface_addr := removed address; 1361 o IR_time := current time + I_HOLD_TIME. 1363 3. Remove that Local Interface Tuple from the Local Interface Set. 1365 4. If the interface to be removed is a MANET interface (i.e., with 1366 I_manet = true) then: 1368 1. Remove the Interface Information Base for that MANET 1369 interface; 1371 2. All Neighbor Tuples for which none of the network addresses 1372 in its N_neighbor_addr_list are contained in any 1373 L_neighbor_iface_addr_list in any remaining Link Tuple, are 1374 removed. 1376 If the removed interface is the last MANET interface of the router, 1377 then there will be no remaining Interface Information Bases, and the 1378 router will no longer participate in this protocol. 1380 After removing the interface and making these changes, a HELLO 1381 message MAY be sent on all remaining MANET interfaces. 1383 9.3. Adding a Network Address to an Interface 1385 If a network address is added to an interface then this is indicated 1386 by the addition of a network address to the appropriate 1387 I_local_iface_addr_list. The following changes MUST be made to the 1388 Information Bases: 1390 1. Remove any Removed Interface Address Tuple whose 1391 IR_local_iface_addr is the added network address. 1393 2. Remove any Neighbor Tuples whose N_neighbor_addr_list contains a 1394 network address that overlaps the added network address. 1396 3. Remove any Link Tuples, in any Link Set, for which either: 1398 o L_neighbor_iface_addr_list contains any network address in the 1399 N_neighbor_addr_list of any removed Neighbor Tuple; OR 1401 o L_neighbor_iface_addr_list contains a network address that 1402 overlaps the added network address. 1404 Apply Section 13.2, but not Section 13.3. 1406 4. Remove any Lost Neighbor Tuples whose NL_neighbor_addr overlaps 1407 the added network address. 1409 5. Remove any 2-Hop Tuples whose N2_2hop_addr overlaps the added 1410 network address. 1412 After adding the network address and making these changes, a HELLO 1413 message MAY be sent on all MANET interfaces. 1415 These changes, other than to the appropriate I_local_iface_addr_list, 1416 are made in order to maintain consistency of the Information Bases. 1417 Specifically, these changes remove any record of any use of this 1418 network address by routers in the 1-hop neighborhood or in the 1419 symmetric 2-hop neighborhood of this router. 1421 9.4. Removing a Network Address from an Interface 1423 If a network address (henceforth removed address) is removed from an 1424 interface then: 1426 1. Identify the Local Interface Tuple that corresponds to the 1427 removed address. 1429 2. If this is the only network address of that interface (the only 1430 network address in the corresponding I_local_iface_addr_list) 1431 then remove that interface as specified in Section 9.2. 1433 3. Otherwise: 1435 1. Remove the removed address from this I_local_iface_addr_list. 1437 2. If the removed address is not in the I_local_iface_addr_list 1438 of any other Local Interface Tuple, then create a Removed 1439 Interface Address Tuple with: 1441 o IR_local_iface_addr := removed address; 1443 o IR_time := current time + I_HOLD_TIME. 1445 After removing the network address and making these changes, a HELLO 1446 message MAY be sent on all MANET interfaces. 1448 10. Packets and Messages 1450 The packet and message format used by this protocol is defined in 1451 [RFC5444], which is used with the following considerations: 1453 o This protocol specifies one Message Type, the HELLO message. 1455 o A HELLO message MAY use any combination of Message Header options 1456 specified in [RFC5444]. 1458 o HELLO messages MUST NOT be forwarded, i.e., a , if 1459 present, MUST have the value 1. 1461 o HELLO messages MAY be included in multi-message packets as 1462 specified in [RFC5444]. 1464 o Received HELLO messages MUST be parsed in accordance with 1465 [RFC5444]. A HELLO message which is not in conformance with 1466 [RFC5444] MUST be discarded without being processed. A HELLO 1467 message can also be discarded without being processed for other 1468 reasons, see Section 12.1. 1470 o This protocol specifies three Address Block TLVs. It also uses 1471 two Message TLVs defined in [RFC5497]. These five TLV Types are 1472 all defined only with Type Extension = 0. TLVs of other types, 1473 and of these types but without Type Extension = 0, are ignored by 1474 this protocol. All references in this specification to, for 1475 example, an Address Block TLV with Type = LINK_STATUS, are to be 1476 considered as referring to an Address Block TLV with Type = 1477 LINK_STATUS and Type Extension = 0. 1479 10.1. HELLO Messages 1481 A HELLO message MUST contain: 1483 o Exactly one VALIDITY_TIME Message TLV as specified in [RFC5497], 1484 representing H_HOLD_TIME for the transmitting MANET interface. 1485 The options included in [RFC5497] for representing zero and 1486 infinite times MUST NOT be used. 1488 A HELLO message which is transmitted periodically SHOULD contain, and 1489 otherwise MAY contain: 1491 o Exactly one INTERVAL_TIME Message TLV as specified in [RFC5497], 1492 representing HELLO_INTERVAL for the transmitting MANET interface. 1493 The options included in [RFC5497] for representing zero and 1494 infinite times MUST NOT be used. 1496 A HELLO message MAY contain: 1498 o Other Message TLVs. 1500 o One or more Address Blocks, each with an associated Address Block 1501 TLV Block, which MAY contain other Address Block TLVs. 1503 10.1.1. Address Blocks 1505 All network addresses in a router's Local Interface Set (i.e., in any 1506 I_local_iface_addr_list) MUST be represented as address objects (see 1507 [RFC5444]), and included in the Address Blocks in all generated HELLO 1508 messages, with the following permitted exception: 1510 o If the MANET interface on which the HELLO message is to be sent 1511 has a single address with maximum prefix length (i.e., /32 for 1512 IPv4, /128 for IPv6), then that address MAY be omitted from being 1513 included in any Address Block, provided that this address is 1514 included as the sending address of the IP datagram in which the 1515 HELLO message is included. 1517 All network addresses of the router's interfaces included in any 1518 Address Block(s) MUST be associated with an Address Block TLV with 1519 Type = LOCAL_IF, as defined in Table 1. 1521 +----------+---------+----------------------------------------------+ 1522 | Name | Value | Description | 1523 | | Length | | 1524 +----------+---------+----------------------------------------------+ 1525 | LOCAL_IF | 1 octet | Specifies that the network address is | 1526 | | | associated with the MANET interface on which | 1527 | | | the message was sent (THIS_IF) or another | 1528 | | | interface of the sending router (OTHER_IF). | 1529 +----------+---------+----------------------------------------------+ 1531 Table 1: LOCAL_IF TLV definition 1533 Address Blocks MAY contain current or recently lost 1-hop neighbors' 1534 network addresses, represented as address objects (see [RFC5444]), 1535 each of which is associated with one or both Address Block TLVs as 1536 described in Table 2. 1538 +--------------+---------+------------------------------------------+ 1539 | Name | Value | Description | 1540 | | Length | | 1541 +--------------+---------+------------------------------------------+ 1542 | LINK_STATUS | 1 octet | Specifies the status of the link from | 1543 | | | the indicated network address and to the | 1544 | | | MANET interface over which the HELLO | 1545 | | | message is transmitted (LOST, SYMMETRIC | 1546 | | | or HEARD). | 1547 | OTHER_NEIGHB | 1 octet | Specifies that the network address is | 1548 | | | (SYMMETRIC) or was (LOST) of a MANET | 1549 | | | interface of a symmetric 1-hop neighbor | 1550 | | | of the router transmitting the HELLO | 1551 | | | message. | 1552 +--------------+---------+------------------------------------------+ 1554 Table 2: LINK_STATUS and OTHER_NEIGHB TLV definition 1556 An Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC or 1557 Value = LOST also performs the function of an Address Block TLV with 1558 Type = OTHER_NEIGHB and the same Value. Including the latter 1559 associated with the same address object is discouraged for efficiency 1560 reasons. If an Address Block TLV with Type = LINK_STATUS and Value = 1561 SYMMETRIC is combined with an Address Block TLV with Type = 1562 OTHER_NEIGHB and Value = LOST associated with the same address 1563 object, then the latter MUST be ignored, and SHOULD NOT be included. 1564 See Appendix A. 1566 Other network addresses MAY be represented as address objects (see 1567 [RFC5444]) and included in Address Blocks, but MUST NOT be associated 1568 with any of the Address Block TLVs specified in this specification. 1570 11. HELLO Message Generation 1572 Each MANET interface MUST generate HELLO messages according to the 1573 specification in this section. HELLO messages are generated for each 1574 MANET interface independently. HELLO message generation and 1575 scheduling MUST be according to the interface parameters for that 1576 MANET interface, and MAY be independent for each MANET interface or, 1577 interface parameters permitting, MANET interfaces MAY use the same 1578 schedule. 1580 If transmitting periodic HELLO messages then, following a HELLO 1581 message transmission on a MANET interface, another HELLO message MUST 1582 be transmitted on the same MANET interface after an interval not 1583 greater than HELLO_INTERVAL. Two successive HELLO message 1584 transmissions on the same MANET interface MUST be separated by at 1585 least HELLO_MIN_INTERVAL, except as noted in Section 11.2.1. 1587 11.1. HELLO Message Specification 1589 HELLO messages are generated independently on each MANET interface. 1591 All network addresses in any I_local_iface_addr_list MUST be 1592 included, represented as address objects (see [RFC5444]), except 1593 that: 1595 o If the interface on which the HELLO message is to be sent has a 1596 single address with maximum prefix length (i.e., /32 for IPv4, 1597 /128 for IPv6) then that address MAY be omitted, provided that 1598 this address is included as the sending address of the IP datagram 1599 in which the HELLO message is included. 1601 All such included address objects MUST be associated with an Address 1602 Block TLV with Type := LOCAL_IF and Value according to the following: 1604 o If the address object represents a network address of the sending 1605 MANET interface, then Value := THIS_IF. 1607 o Otherwise, Value := OTHER_IF. 1609 If such a network address is included in more than one 1610 I_local_iface_addr_list, then, for efficiency reasons, it is 1611 encouraged that the corresponding address object is associated with 1612 only one Value using an Address Block TLV with Type := LOCAL_IF, this 1613 MUST be Value := THIS_IF if the address object represents a network 1614 address of the sending MANET interface. 1616 The following network addresses of current or former 1-hop neighbors 1617 MAY be represented as address objects (see [RFC5444]) and included in 1618 any HELLO message, respecting the parameter REFRESH_INTERVAL for each 1619 association for that MANET interface, and according to the following: 1621 o Network addresses of MANET interfaces of 1-hop neighbors from the 1622 Link Set of the Interface Information Base for this MANET 1623 interface (i.e., from an L_neighbor_iface_addr_list), other than 1624 those from Link Tuples with L_status = PENDING. 1626 o Other network addresses of symmetric 1-hop neighbors from the 1627 Neighbor Set of this router's Neighbor Information Base (i.e., 1628 from an N_neighbor_addr_list). 1630 o Network addresses of MANET interfaces of previously symmetric or 1631 heard 1-hop neighbors connected on this MANET interface from the 1632 Link Set of the Interface Information Base for this MANET 1633 interface (i.e., from an L_neighbor_iface_addr_list with L_status 1634 = LOST). 1636 o Other network addresses of previously symmetric 1-hop neighbors 1637 from the Lost Neighbor Set of this router's Neighbor Information 1638 Base (i.e., from an NL_neighbor_addr). 1640 Each such address object (see [RFC5444]) MUST be associated with one 1641 or more appropriate Address Block TLVs. Specifically: 1643 1. For each address object (henceforth linked address) which 1644 represents a network address contained in an 1645 L_neighbor_iface_addr_list of a Link Tuple in the Link Set for 1646 this MANET interface, for which L_status != PENDING, include the 1647 linked address with an associated Address Block TLV with: 1649 o Type := LINK_STATUS; AND 1651 o Value := L_status. 1653 2. For each address object (henceforth neighbor address) which 1654 represents a network address contained in an N_neighbor_addr_list 1655 in a Neighbor Tuple with N_symmetric = true, and which has not 1656 already been included with an associated Address Block TLV with 1657 Type = LINK_STATUS and Value = SYMMETRIC, include the neighbor 1658 network address with an associated Address Block TLV with: 1660 o Type := OTHER_NEIGHB; AND 1662 o Value := SYMMETRIC. 1664 3. For each Lost Neighbor Tuple whose NL_neighbor_addr (henceforth 1665 lost address) has not already been represented as an address 1666 object and included, include lost address with an associated 1667 Address Block TLV with: 1669 o Type := OTHER_NEIGHB; AND 1671 o Value := LOST. 1673 If any such network addresses have been added to these Information 1674 Bases since the last HELLO message was sent on this MANET interface, 1675 or if their status (as indicated by these TLVs and the Values they 1676 associate with that network address) have changed since that network 1677 address was last reported on this MANET interface, then that network 1678 address, and the indicated TLVs, SHOULD be included in the HELLO 1679 message. 1681 If the address object (see [RFC5444]) representing a network address 1682 of a 1-hop neighbor is specified with more than one associated 1683 Address Block TLV, then these Address Block TLVs MAY be independently 1684 included or excluded from each HELLO message. Each such Address 1685 Block TLV MUST be included associated with the address object 1686 representation of that network address in a HELLO message sent on 1687 that MANET interface in every interval of length equal to that MANET 1688 interface's parameter REFRESH_INTERVAL. Address Block TLVs 1689 associated with the same address object included in the same HELLO 1690 message MAY be applied to the same or different copies of that 1691 address object. 1693 An implementation of this protocol MAY limit the information included 1694 in each HELLO message, for example to acommodate smaller MTU sizes. 1695 HELLO messages remain constrained by the above requirements, in 1696 particular that all local interface information MUST be included in 1697 all HELLO messages, and that all neighbor information MUST be sent 1698 within each interval of length REFRESH_INTERVAL. This neighbor 1699 information MAY, however, be sent in the same or in different HELLO 1700 messages. 1702 11.2. HELLO Message Transmission 1704 HELLO messages are transmitted in the format specified by [RFC5444]. 1706 11.2.1. HELLO Message Jitter 1708 HELLO messages MAY be sent using periodic message generation or 1709 externally triggered message generation. If using data link and 1710 physical layers which are subject to packet loss due to collisions, 1711 HELLO messages SHOULD be jittered as described in [RFC5148]. 1713 Internally triggered message generation (such as due to a change in 1714 local interfaces) MAY be treated as if externally generated message 1715 generation, or MAY be not jittered. 1717 HELLO messages MUST NOT be forwarded, and thus message forwarding 1718 jitter does not apply to HELLO messages. 1720 Each form of jitter described in [RFC5148] requires a parameter 1721 MAXJITTER. These interface parameters may be dynamic, and are 1722 specified by: 1724 o For periodic message generation: HP_MAXJITTER. 1726 o For externally triggered message generation: HT_MAXJITTER. 1728 When HELLO message generation is delayed in order that a HELLO 1729 message is not sent within HELLO_MIN_INTERVAL of the previous HELLO 1730 message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD 1731 be reduced by jitter, with maximum reduction HP_MAXJITTER, as 1732 described in [RFC5148]. In this case HP_MAXJITTER MUST NOT be 1733 greater than HELLO_MIN_INTERVAL. 1735 12. HELLO Message Processing 1737 On receiving a HELLO message, a router MUST first check if the 1738 message is invalid for processing by this router, as defined in 1739 Section 12.1 and, if so, discard the message without further 1740 processing. Otherwise, for each received and valid HELLO message the 1741 receiving router MUST update its appropriate Interface Information 1742 Base and its Neighbor Information Base as specified in Section 12.3 1743 to Section 12.6. These updates MUST be performed in the order in 1744 which they are presented in this specification. If any changes 1745 satisfy any of the conditions described in Section 13 then the 1746 indicated consequences in that section MUST be applied immediately, 1747 unless noted otherwise. 1749 All message processing, including determination of whether a message 1750 is invalid, considers only TLVs with Type Extension = 0. TLVs with 1751 any other type extension are ignored. All references to, for 1752 example, a TLV with Type = LINK_STATUS refer to a TLV with Type = 1753 LINK_STATUS and Type Extension = 0. 1755 12.1. Invalid Message 1757 A received HELLO message is invalid for processing by this router if 1758 any of the following conditions are true: 1760 o The address length as specified in the Message Header is not equal 1761 to the length of the addresses used by this router. 1763 o The message has a field in its Message Header with 1764 a value other than one. (Note that the message does not need to 1765 have a field.) 1767 o The message has a field in its Message Header with 1768 a value other than zero. (Note that the message does not need to 1769 have a field.) 1771 o The message does not have a Message TLV with Type = VALIDITY_TIME 1772 in its Message TLV Block. 1774 o The message has more than one Message TLV with Type = 1775 VALIDITY_TIME in its Message TLV Block. 1777 o The message has more than one Message TLV with Type = 1778 INTERVAL_TIME in its Message TLV Block. 1780 o The message has any Address Block TLV(s) with Type = LOCAL_IF and 1781 any single Value v such that v != THIS_IF and v != OTHER_IF. 1783 o Any address object (including different address objects 1784 representing the same network address, in the same or different 1785 Address Blocks) is associated with more than one Value by one or 1786 more Address Block TLV(s) with Type = LOCAL_IF. 1788 o Any address object (henceforth local address) associated with an 1789 Address Block TLV with Type = LOCAL_IF represents one of the 1790 receiving router's current or recently used network addresses 1791 (i.e., local address overlaps any network address in any 1792 I_local_iface_addr_list in the Local Interface Set or any 1793 IR_local_iface_addr in the Removed Interface Address Set). 1795 o The message has any Address Block TLV(s) with Type = LINK_STATUS 1796 with any single Value v such that v != LOST, v != SYMMETRIC, and v 1797 != HEARD. 1799 o The message has any Address Block TLV(s) with Type = OTHER_NEIGHB 1800 with any single Value v such that v != LOST and v != SYMMETRIC. 1802 o Any address object (including different copies of an address 1803 object, in the same or different Address Blocks) is associated 1804 with an Address Block TLV with Type = LOCAL_IF and with an Address 1805 Block TLV with Type = LINK_STATUS. 1807 o Any address object (including different copies of an address 1808 object, in the same or different Address Blocks) is associated 1809 with an Address Block TLV with Type = LOCAL_IF and with an Address 1810 Block TLV with Type = OTHER_NEIGHB. 1812 o Any address object (including different copies of an address 1813 object, in the same or different Address Blocks) is associated 1814 with more than one Value by one or more Address Block TLVs with 1815 Type = LINK_STATUS. 1817 o Any address object (including different copies of an address 1818 object, in the same or different Address Blocks) is associated 1819 with more than one Value by one or more Address Block TLVs with 1820 Type = OTHER_NEIGHB. 1822 A router MAY recognize additional reasons for identifying that a 1823 message is badly formed and therefore invalid for processing, e.g., 1824 to allow a security protocol as suggested in Section 17 to perform 1825 verification of HELLO message signatures and prevent processing of 1826 unverifiable HELLO messages by this protocol. 1828 An invalid message MUST be silently discarded, without updating the 1829 router's Information Bases. 1831 12.2. Definitions 1833 For the purpose of this section, note the following definitions: 1835 o "validity time" is calculated from the Message TLV with Type = 1836 VALIDITY_TIME of the HELLO message as specified in [RFC5497]. 1837 (Note that, as specified by Section 12.1, there must be exactly 1838 one such Message TLV in the HELLO message.) All information in 1839 the HELLO message used by this specification has the same validity 1840 time. 1842 o "Receiving Address List" is the I_local_iface_addr_list 1843 corresponding to the MANET interface on which the HELLO message 1844 was received 1846 o "Sending Address List" is an unordered list of network addresses 1847 of the MANET interface over which the HELLO message was sent, 1848 i.e., is an unordered list of the network addresses represented by 1849 address objects contained in the HELLO message with an associated 1850 Address Block TLV with Type = LOCAL_IF and Value = THIS_IF. If 1851 the Sending Address List is otherwise empty, then the Sending 1852 Address List contains a single network address with maximum prefix 1853 length (i.e., /32 for IPv64, /128 for IPv6) with address equal to 1854 the sending address of the IP datagram in which the HELLO message 1855 was included. 1857 o "Neighbor Address List" is an unordered list of all the network 1858 addresses of all the interfaces of the router which generated the 1859 HELLO message, i.e., is the Sending Address List, plus the network 1860 addresses represented by address objects contained in the HELLO 1861 message with an associated Address Block TLV with Type = LOCAL_IF 1862 and Value = OTHER_IF. 1864 o "EXPIRED" indicates that a timer is set to a value clearly 1865 preceding the current time (e.g., , current time - 1). 1867 o "Removed Address List" is a list of network addresses created by 1868 this HELLO message processing which were formerly reported as 1869 local by the router originating the HELLO message, but which are 1870 not included in the Neighbor Address List. This list is 1871 initialized as empty. 1873 o "Lost Address List" is a subset of the Removed Address List 1874 containing network addresses which were formerly considered as 1875 symmetric. This list is initialized as empty. 1877 12.3. Updating the Neighbor Set 1879 On receiving a HELLO message, the router MUST update its Neighbor Set 1880 and populate the Removed Address List and Lost Address List: 1882 1. Find all Neighbor Tuples (henceforth matching Neighbor Tuples) 1883 where N_neighbor_addr_list contains any network address which 1884 overlaps with any network address in the Neighbor Address List. 1886 2. If there are no matching Neighbor Tuples, then: 1888 1. Create a new Neighbor Tuple with: 1890 o N_neighbor_addr_list := Neighbor Address List; 1892 o N_symmetric := false. 1894 3. If there is one matching Neighbor Tuple, then: 1896 1. If the matching Neighbor Tuple's N_neighbor_addr_list != 1897 Neighbor Address List, then: 1899 1. For each network address (henceforth removed address) 1900 which is contained in that N_neighbor_addr_list, but is 1901 not contained in the Neighbor Address List: 1903 1. Add removed address to the Removed Address List. 1905 2. If N_symmetric = true, then add removed address to 1906 the Lost Address List. 1908 2. Update the matching Neighbor Tuple by: 1910 o N_neighbor_addr_list := Neighbor Address List. 1912 4. If there are two or more matching Neighbor Tuples, then: 1914 1. For each network address (henceforth removed address) which 1915 is contained in the N_neighbor_addr_list of any of the 1916 matching Neighbor Tuples but is not contained in the Neighbor 1917 Address List: 1919 1. Add removed address to the Removed Address List. 1921 2. If N_symmetric = true, then add removed address to the 1922 Lost Address List. 1924 2. Replace the matching Neighbor Tuples by a single Neighbor 1925 Tuple with: 1927 o N_neighbor_addr_list := Neighbor Address List; 1929 o N_symmetric := false 1931 12.4. Updating the Lost Neighbor Set 1933 On receiving a HELLO message, a router MUST update its Lost Neighbor 1934 Set: 1936 1. For each network address (henceforth lost address) which is 1937 contained in the Lost Address List, if no Lost Neighbor Tuple 1938 with NL_neighbor_addr = lost address exists, then add a Lost 1939 Neighbor Tuple with: 1941 o NL_neighbor_addr := lost address; 1943 o NL_time := current time + N_HOLD_TIME. 1945 12.5. Updating the Link Set 1947 On receiving a HELLO message, a router MUST update its Link Set for 1948 the MANET interface on which the HELLO message is received: 1950 1. Remove all network addresses in the Removed Address List from the 1951 L_neighbor_iface_addr_list of all Link Tuples. 1953 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now 1954 empty; apply Section 13.2, but not Section 13.3. 1956 3. Find all Link Tuples (henceforth matching Link Tuples) where: 1958 o L_neighbor_iface_addr_list contains one or more network 1959 addresses in the Sending Address List. 1961 4. If there is more than one matching Link Tuple, then remove them 1962 all; apply Section 13.2, but not Section 13.3. 1964 5. If no matching Link Tuples remain, then create a new matching 1965 Link Tuple with: 1967 o L_neighbor_iface_addr_list := empty; 1969 o L_HEARD_time := EXPIRED; 1971 o L_SYM_time := EXPIRED; 1973 o L_quality := INITIAL_QUALITY; 1975 o L_pending := INITIAL_PENDING; 1977 o L_lost := false; 1979 o L_time := current time + validity time. 1981 6. The matching Link Tuple, existing or new, is then modified as 1982 follows: 1984 1. If the router finds any network address (henceforth receiving 1985 address) in the Receiving Address List in an Address Block in 1986 the HELLO message, then the Link Tuple is modified as 1987 follows: 1989 1. If any receiving address in the HELLO message is 1990 associated with an Address Block TLV with Type = 1991 LINK_STATUS and with Value = HEARD or Value = SYMMETRIC 1992 then: 1994 o L_SYM_time := current time + validity time. 1996 2. Otherwise if any receiving address in the HELLO message 1997 is associated with an Address Block TLV with Type = 1998 LINK_STATUS and Value = LOST then: 2000 1. if L_SYM_time has not expired, then: 2002 1. L_SYM_time := EXPIRED. 2004 2. if L_status = HEARD, then: 2006 o L_time := current time + L_HOLD_TIME. 2008 2. L_neighbor_iface_addr_list := Sending Address List. 2010 3. L_HEARD_time := max(current time + validity time, 2011 L_SYM_time). 2013 4. If L_status = PENDING, then: 2015 o L_time := max(L_time, L_HEARD_time). 2017 5. Otherwise if L_status = HEARD or L_status = SYMMETRIC, then: 2019 o L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 2021 12.6. Updating the 2-Hop Set 2023 On receiving a HELLO message a router MUST update its 2-Hop Set for 2024 the MANET interface on which the HELLO message was received: 2026 1. Remove all network addresses in the Removed Address List from the 2027 N2_neighbor_iface_addr_list of all 2-Hop Tuples. 2029 2. If the Link Tuple whose L_neighbor_iface_addr_list = Sending 2030 Address List, has L_status = SYMMETRIC then: 2032 1. For each network address (henceforth 2-hop address) in an 2033 Address Block of the HELLO message, where: 2035 o 2-hop address is not contained in the Neighbor Address 2036 List; 2038 o 2-hop address is not contained in any 2039 I_local_iface_addr_list; AND 2041 o 2-hop address != any IR_local_iface_addr 2043 perform the following processing: 2045 1. If 2-hop address has an associated Address Block TLV 2046 with: 2048 o Type = LINK_STATUS and Value = SYMMETRIC; OR 2050 o Type = OTHER_NEIGHB and Value = SYMMETRIC, 2052 then, if there is no 2-Hop Tuple such that: 2054 o N2_neighbor_iface_addr_list contains one or more 2055 network addresses in the Sending Address List; AND 2057 o N2_2hop_addr = 2-hop address. 2059 then create a 2-Hop Neighbor Tuple with: 2061 o N2_2hop_addr := 2-hop address. 2063 This 2-Hop Tuple (existing or new) is then modified as 2064 follows: 2066 o N2_neighbor_iface_addr_list := Sending Address List; 2068 o N2_time := current time + validity time. 2070 2. Otherwise if 2-hop address has an Address Block TLV with: 2072 o Type = LINK_STATUS and Value = LOST or Value = HEARD; 2073 OR 2075 o Type = OTHER_NEIGHB and Value = LOST; 2077 then remove all 2-Hop Tuples with: 2079 o N2_neighbor_iface_addr_list contains one or more 2080 network addresses in the Sending Address List; AND 2082 o N2_2hop_addr = 2-hop address. 2084 13. Other Information Base Changes 2086 The Interface and Neighbor Information Bases MUST be changed when 2087 certain events occur. These events may result from HELLO message 2088 processing, or may be otherwise generated (e.g., expiry of timers or 2089 link quality changes). 2091 Events which cause changes in the Information Bases are: 2093 o A Link Tuple's L_status changes to SYMMETRIC. In this case, the 2094 actions specified in Section 13.1 are performed. 2096 o A Link Tuple's L_status changes from SYMMETRIC, or the Link Tuple 2097 is removed. In this case, the actions specified in Section 13.2 2098 are performed. 2100 o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed. 2101 In this case, the actions specified in Section 13.3 are performed. 2103 o Local interface network address changes. In this case, the 2104 actions specified in Section 9 are performed. 2106 o Link quality changes. In this case, the actions specified in 2107 Section 14 are performed. 2109 If a Link Tuple is removed, or if L_status changes from SYMMETRIC and 2110 L_HEARD_time expires, then the actions specified in Section 13.2 MUST 2111 be performed before the actions specified in Section 13.3 are 2112 performed for that Link Tuple. 2114 A router MAY report updated information in response to any of these 2115 changes in HELLO message(s), subject to the constraints in 2116 Section 11. 2118 A router which transmits HELLO messages in response to such changes 2119 SHOULD transmit a HELLO message: 2121 o On all MANET interfaces, if the Neighbor Set changes such as to 2122 indicate the change in symmetry of any 1-hop neighbors (including 2123 addition or removal of symmetric 1-hop neighbors). 2125 o Otherwise, on all those MANET interfaces whose Link Set changes 2126 such as to indicate a change in L_status of any 1-hop neighbors 2127 (including the addition or removal of any 1-hop neighbors, other 2128 than those considered pending). 2130 13.1. Link Tuple Symmetric 2132 If, for any Link Tuple which does not have L_status = SYMMETRIC: 2134 o L_status changes to SYMMETRIC; 2136 then: 2138 1. For the Neighbor Tuple whose N_neighbor_addr_list contains 2139 L_neighbor_iface_addr_list, set: 2141 o N_symmetric := true. 2143 2. Remove all Lost Neighbor Tuples whose NL_neighbor_addr is 2144 contained in that N_neighbor_addr_list. 2146 This includes any newly created Link Tuples whose status is 2147 immediately updated such that L_status = SYMMETRIC. (Note that in 2148 this specification all Link Tuples are created such that their 2149 L_status is not SYMMETRIC, but a Link Tuple may be immediately 2150 updated by subsequent processing of the same HELLO message that 2151 caused the creation of the Link Tuple such that the Link Tuple's 2152 L_status changes to SYMMETRIC.) 2154 13.2. Link Tuple Not Symmetric 2156 If for any Link Tuple with L_status = SYMMETRIC: 2158 o L_status changes to any other value; OR 2160 o the Link Tuple is removed; 2162 then: 2164 1. All 2-Hop Tuples for the same MANET interface with: 2166 o N2_neighbor_iface_addr_list contains one or more network 2167 addresses in L_neighbor_iface_addr_list; 2169 are removed. 2171 2. For the Neighbor Tuple whose N_neighbor_addr_list contains 2172 L_neighbor_iface_addr_list: 2174 1. If there are no remaining Link Tuples for any MANET interface 2175 where: 2177 o L_neighbor_iface_addr_list is contained in 2178 N_neighbor_addr_list; AND 2180 o L_status = SYMMETRIC; 2182 then modify the Neighbor Tuple by: 2184 1. N_symmetric := false. 2186 2. For each network address (henceforth neighbor address) in 2187 N_neighbor_addr_list, add a Lost Neighbor Tuple with: 2189 o NL_neighbor_addr := neighbor address; 2191 o NL_time := current time + N_HOLD_TIME. 2193 13.3. Link Tuple Heard Timeout 2195 If, for any Link Tuple: 2197 o L_HEARD_time expires; OR 2199 o the Link Tuple is removed; 2201 then: 2203 1. For the Neighbor Tuple whose N_neighbor_addr_list contains 2204 L_neighbor_iface_addr_list, if no Link Tuples for any MANET 2205 interface remain where: 2207 o L_neighbor_iface_addr_list is contained in 2208 N_neighbor_addr_list; AND 2210 o L_HEARD_time is not expired; 2212 then remove the Neighbor Tuple. 2214 14. Link Quality 2216 Link quality is a mechanism whereby a router MAY take considerations 2217 other than message exchange into account for determining when a link 2218 is and is not a candidate for being considered as HEARD or SYMMETRIC. 2219 As such, it is a "link admission" mechanism. 2221 Link quality information for a link is generated (e.g., through 2222 access to signal to noise ratio, packet loss rate, or other 2223 information from the link layer) and used only locally, i.e., is not 2224 included in signaling, and routers may interoperate whether they are 2225 using the same, different, or no, link quality information. Link 2226 quality information is specified as a normalised, dimensionless 2227 figure in the interval zero to one, inclusive, a higher value 2228 indicating a better link quality. 2230 For deployments where no link quality is used, the considerations in 2231 Section 14.1 apply. For deployments where link quality is used, the 2232 general principles of link quality usage are described in 2233 Section 14.2. Section 14.3 and Section 14.4 detail link quality 2234 functioning. 2236 14.1. Deployment Without Link Quality 2238 In order for a router to not employ link quality, the router MUST 2239 define: 2241 o INITIAL_PENDING := false; 2243 o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define 2244 INITIAL_QUALITY := 1). 2246 14.2. Basic Principles of Link Quality 2248 To enable link quality usage, the L_quality value of a Link Tuple is 2249 used in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, 2250 to set the flags L_pending and L_lost of that Link Tuple. Based on 2251 these flags, the link status to advertise for that Link Tuple is 2252 determined as described in Section 7.1. 2254 The use of two thresholds implements link hysteresis, whereby a link 2255 which has HYST_REJECT <= L_quality < HYST_ACCEPT may be either 2256 accepted or rejected (depending on which threshold it has most 2257 recently crossed, or, if neither, on the value of parameter 2258 INITIAL_PENDING). With appropriate values of these parameters, this 2259 prevents over-rapid changes of link status. 2261 The basic principles of link quality usage are as follows: 2263 o A router does not advertise a neighbor interface in any state 2264 until L_quality is acceptable: 2266 o If INITIAL_PENDING = true, then the link is advertised when 2267 link L_quality >= HYST_ACCEPT. 2269 o Otherwise the link is advertised when L_quality >= HYST_REJECT. 2271 A link which is not yet advertised has L_pending = true. 2273 o Once L_quality >= HYST_ACCEPT, the router sets L_pending := false, 2274 indicating that the link can be advertised. 2276 o A link for which L_pending = false is advertised until its 2277 L_quality drops below HYST_REJECT. 2279 o If a link has L_pending = false and L_quality < HYST_REJECT, the 2280 link is LOST and is advertised as such. This link is not 2281 reconsidered as a candidate HEARD or SYMMETRIC link until 2282 L_quality >= HYST_ACCEPT. 2284 o A link which has an acceptable quality may be advertised as HEARD, 2285 SYMMETRIC or LOST according to the exchange of HELLO messages. 2287 In order that these principles can all hold, a router MUST NOT 2288 define: 2290 o INITIAL_PENDING = false and INITIAL_QUALITY < HYST_REJECT; OR 2292 o INITIAL_PENDING = true and INITIAL_QUALITY >= HYST_ACCEPT. 2294 14.3. When Link Quality Changes 2296 If L_quality for a link changes, then the following actions MUST be 2297 taken: 2299 1. If L_quality >= HYST_ACCEPT then the corresponding Link Tuple is 2300 modified by: 2302 1. L_pending := false; 2304 2. L_lost := false; 2306 3. If L_status = HEARD or L_status = SYMMETRIC, then: 2308 o L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 2310 2. If L_status != PENDING, and L_quality < HYST_REJECT then the 2311 corresponding Link Tuple is modified by: 2313 1. If L_lost = false, then: 2315 o L_lost := true; 2317 o L_time := min(L_time, current time + L_HOLD_TIME). 2319 As a result of this processing, the L_STATUS of a Link Tuple may 2320 change. In this case, the processing actions corresponding to this 2321 change, as specified in in Section 13, MUST also be taken. 2323 If L_quality for a link is updated based on HELLO message reception, 2324 or on reception of a packet including a HELLO message, then L_quality 2325 MUST be updated prior to the HELLO message processing described in 2326 Section 12. (If the receipt of the HELLO message, or the packet 2327 containing it, creates the Link Tuple, then the Link Tuple MUST be 2328 created with the appropriately updated L_quality value, rather than 2329 with L_quality := INITIAL_QUALITY.) 2331 14.4. Updating Link Quality 2333 A router MAY update link quality based on any information available 2334 to it. Particular cases that MAY be used include: 2336 o Information from the link layer, such as signal to noise ratio or 2337 packet acknowledgment reception and loss information. 2339 o Receipt or loss of control packets. If control packets include a 2340 sequential packet sequence number, as defined in [RFC5444], then 2341 link quality can be updated when a control packet is received, 2342 whether or not it contains a HELLO message. The link quality may 2343 then, for example, be based on whether the last N out of M control 2344 packets on the link were received, or may use a "leaky integrator" 2345 tracking packet reception and loss. 2347 o Receipt or loss of HELLO messages. If the maximum interval 2348 between HELLO messages is known (such as by inclusion in HELLO 2349 messages of a Message TLV with Type := INTERVAL_TIME, as defined 2350 in [RFC5497]) then the loss of HELLO messages can be determined 2351 without the need to receive a later HELLO message. Note that if 2352 this case is combined with the previous case then care must be 2353 taken to avoid "double counting" a lost HELLO message in a lost 2354 packet. 2356 15. Proposed Values for Parameters and Constants 2358 This section lists the parameters and constants used in the 2359 specification of the protocol, and proposed values of each which MAY 2360 be used when a single value of each is used. 2362 15.1. Message Interval Interface Parameters 2364 o HELLO_INTERVAL := 2 seconds 2366 o HELLO_MIN_INTERVAL := HELLO_INTERVAL/4 2367 o REFRESH_INTERVAL := HELLO_INTERVAL 2369 15.2. Information Validity Time Interface Parameters 2371 o H_HOLD_TIME := 3 x REFRESH_INTERVAL 2373 o L_HOLD_TIME := H_HOLD_TIME 2375 15.3. Information Validity Time Router Parameters 2377 o N_HOLD_TIME := L_HOLD_TIME 2379 o I_HOLD_TIME := N_HOLD_TIME 2381 15.4. Link Quality Interface Parameters 2383 If link quality is changed, then parameter values will depend on the 2384 link quality process. If link quality is not changed, then: 2386 o HYST_ACCEPT := 1 2388 o HYST_REJECT := 0 2390 o INITIAL_QUALITY := 1 2392 o INITIAL_PENDING := false 2394 15.5. Jitter Interface Parameters 2396 o HP_MAXJITTER := HELLO_INTERVAL/4 2398 o HT_MAXJITTER := HP_MAXJITTER 2400 15.6. Constants 2402 o C := 1/1024 second 2404 16. Usage with Other Protocols 2406 Other protocols, such as MANET routing protocols, which use 2407 neighborhood discovery, may need to interact with this protocol. 2408 This protocol is designed to permit such interactions, in particular: 2410 o Through accessing, and possibly extending, the information in the 2411 Local Information Base (Section 6), the Interface Information Base 2412 (Section 7) and the Neighbor Information Base (Section 8). These 2413 Information Bases record the interface configuration of the 2414 router, as well as the local connectivity, up to two hops away. 2416 All updates to the elements specified in this document are subject 2417 to the constraints specified in Appendix B. 2419 o Through accessing an outgoing HELLO message prior to it being 2420 transmitted over any MANET interface, and to add information 2421 (e.g., , TLVs) as specified in [RFC5444]. This may, for example, 2422 be to allow a security protocol, as suggested in Section 17, to 2423 add a TLV containing a cryptographic signature to the message, or 2424 be to allow inserting relay selection information into a HELLO 2425 message by way of adding a TLV to an outgoing HELLO message prior 2426 to it being transmitted. 2428 o Through accessing an incoming HELLO message, and potentially 2429 discarding it prior to processing by this protocol. This may, for 2430 example, allow a security protocol as suggested in Section 17 to 2431 perform verification of HELLO message signatures and prevent 2432 processing of unverifiable HELLO messages by this protocol. 2434 o Through accessing an incoming HELLO message after it has been 2435 completely processed by this protocol. This may, in particular, 2436 allow a protocol which has added information, such as relay 2437 selection information by way of inclusion of appropriate TLVs, 2438 access to such information after appropriate updates have been 2439 recorded in the Information Bases in this protocol. 2441 o Through requesting that a HELLO message be generated at a specific 2442 time. In that case, HELLO message generation MUST still respect 2443 the constraints in Appendix B. 2445 Address objects in HELLO messages are processed according to their 2446 associated Address Block TLVs. All such address objects are to be 2447 processed according to this specification are associated with Address 2448 Block TLVs with Type of LOCAL_IF, OTHER_NEIGHB or LINK_STATUS (and 2449 type extension zero). Address objects not associated with an Address 2450 Block TLV of any of these Types are therefore not processed by the 2451 protocol described in this specification. 2453 A protocol, such as a MANET routing protocol, interacting with this 2454 protocol may need to add information to HELLO messages. This may be 2455 in form of associating TLVs (of Type other than LOCAL_IF, 2456 OTHER_NEIGHB or LINK_STATUS) to address objects already included by 2457 this specification. 2459 A protocol, such as a MANET routing protocol, interacting with this 2460 protocol may also add information to HELLO messages by inserting 2461 address objects not already included by this specification. Such 2462 address objects are in the following called "inserted addresses". 2463 These inserted addresses may added to Address Blocks already present 2464 by virtue of the HELLO message generation in this specification, or 2465 may appear in new Address Blocks. In both cases, the following MUST 2466 be observed: 2468 o An inserted address MUST NOT be associated with an Address Block 2469 TLV of Type LOCAL_IF, OTHER_NEIGHB or LINK_STATUS. Consequently, 2470 the processing in this specification will ignore such address 2471 objects. 2473 o Each inserted address MUST be associated with an Address Block 2474 TLV, to be defined by the specification of the protocol inserting 2475 the address object. In this way, all addresses present in a HELLO 2476 message are associated with an Address Block TLV defining their 2477 semantics. 2479 Informally speaking, Address Block TLVs define the semantics of 2480 address objects in an Address Block. If an address object in an 2481 Address Block does not have any Address Block TLVs associated, that 2482 address object has no semantics. Consequently, all protocols using 2483 the protocol defined in this specification MUST respect the 2484 following: 2486 o An address object in an Address Block, which is not associated 2487 with any Address Block TLV, MUST be silently ignored; the mere 2488 presence of an address object without an associated Address Block 2489 TLV in a HELLO message MUST NOT cause any processing. 2491 A protocol interacting with this protocol MAY also add an originator 2492 address to HELLO messages, as specified in [RFC5444]. Such an 2493 originator address MUST be unique to the originating router, it MAY 2494 be a local interface address of the router. It SHOULD be used 2495 consistently, but SHOULD NOT be constrained in any other way. 2497 Strict adherence to these points will enable unambiguous co-existence 2498 of future "extensions" to HELLO messages. 2500 In some cases, a protocol interacting with the protocol defined in 2501 this specification, may need to recognize which HELLO messages to 2502 process and which HELLO messages to discard. It is the 2503 responsibility of that protocol to ensure that such messages are 2504 suitably identifiable, e.g., through inclusion of a Message TLV or 2505 through recognizing an administrative configuration (such as address 2506 ranges). Note that such a protocol interacting with this protocol 2507 MAY specify such interaction by recognizing an additional reason for 2508 discarding a message. As suggested in Section 17 this might, for 2509 example, be a security protocol discarding a message which does not 2510 carry a Message TLV containing a cryptographic signature. 2512 17. Security Considerations 2514 The objective of this protocol is to allow each router in the network 2515 to acquire information describing its 1-hop neighborhood and 2516 symmetric 2-hop neighborhood. This is acquired through HELLO message 2517 exchange between neighboring routers. This information is made 2518 available through the Interface Information Bases and Neighbor 2519 Information Base, describing the router's 1-hop neighborhood and 2520 symmetric 2-hop neighborhood. 2522 Under normal circumstances, the information recorded in these 2523 Information Bases is correct, i.e., corresponds to the actual network 2524 topology, apart from any changes which have not (yet) been tracked by 2525 the HELLO message exchanges. 2527 If a router for some reason, whether malice or malfunction, transmits 2528 invalid HELLO messages, incorrect information may be recorded in 2529 other routers' Information Bases. This protocol specification does, 2530 however, prevent inconsistent information from being included in the 2531 Information Bases through the specified processing, which maintains 2532 the constraints in Appendix B. The exact consequence of information 2533 inexactness depends on the use of these Information Bases, and SHOULD 2534 therefore be reflected in the specification of protocols which use 2535 information provided by this neighborhood discovery protocol. 2537 This section, therefore, firstly outlines the ways in which correctly 2538 formed, but still invalid, HELLO messages may appear, in 2539 Section 17.1. 2541 Injection of invalid HELLO messages into a network may be prevented 2542 in a number of ways. If, for example, a network is deployed in a 2543 site to which access is strictly regulated, so that physical access 2544 and proximity to the network is prevented, then further security 2545 mechanisms to protect against malicious routers injecting invalid 2546 HELLO messages may not be required. Similarly, if the link layer 2547 over which the network is formed provides appropriate 2548 confidentiality, authentication, and integrity, then this may, for a 2549 given deployment, suffice to appropriately protect against disclosure 2550 of information to an eavesdropper, and against a malicious router 2551 injecting invalid HELLO messages. In the latter case the link layer 2552 would discard frames that fail the link layer checks, without 2553 attempting to deliver such frames to IP. Finally, certain usage may 2554 be of a nature where disruption of service is of no consequence, or 2555 at least not of sufficient consequence to warrant deployment of 2556 additional security mechanisms. 2558 A further point to stress, and which follows from the discussions 2559 above is, that it will not be the case that "one size security fits 2560 all". Different deployments may have different requirements. For 2561 example in a deployment of a low value sensor network, authentication 2562 using a simple message authentication code and shared symmetric keys 2563 may suffice, while anything beyond that may require too many 2564 computational resources to be viable. Conversely, in, for example, a 2565 community network, verifying not only that the originator of a HELLO 2566 message "has the right key" but also the precise identity of the 2567 originator may be required to be proved, and computational resources 2568 may be available to make such a requirement feasible. 2570 Section 17.2, therefore, does not specify a single "one-size-fits- 2571 all" mechanism, but rather details how the security suggestions in 2572 [RFC5444] are considered for applicability within the context of this 2573 protocol, and with the purpose of aiding deployment-specific security 2574 mechanisms to be developed. 2576 17.1. Invalid HELLO Messages 2578 A correctly formed, but still invalid, HELLO message may take any of 2579 the following forms. Note that a present or absent address object in 2580 an Address Block, does not by itself cause a problem. It is the 2581 presence, absence, or incorrectness of associated LOCAL_IF, 2582 LINK_STATUS and OTHER_NEIGHB Address Block TLVs that causes problems. 2584 A router may provide false information about its own identity: 2586 o The HELLO message may contain address objects with an 2587 associated LOCAL_IF Address Block TLV which do not correspond 2588 to addresses of interfaces of the router transmitting the HELLO 2589 message. 2591 o The HELLO message may omit network addresses, or their 2592 associated LOCAL_IF Address Block TLV, of interfaces of the 2593 router transmitting the HELLO message (other than the allowed 2594 omission of the only local interface network address of the 2595 MANET interface over which the HELLO message is transmitted, if 2596 that is the case). 2598 o The HELLO message may incorrectly specify the LOCAL_IF Address 2599 Block TLV Value associated with one or more local interface 2600 network addresses, indicating incorrectly whether they are 2601 associated with the MANET interface over which the HELLO 2602 message is transmitted. 2604 A router may provide false information about the identity of other 2605 routers: 2607 o A present LINK_STATUS Address Block TLV may, incorrectly, 2608 identify a network address as being of a MANET interface which 2609 is or was heard on the MANET interface over which the HELLO 2610 message is transmitted. 2612 o A consistently absent LINK_STATUS Address Block TLV may, 2613 incorrectly, fail to identify a network address as being of a 2614 MANET interface which is or was heard on the MANET interface 2615 over which the HELLO message is transmitted. 2617 o A present OTHER_NEIGHB Address Block TLV may, incorrectly, 2618 identify a network address as being of a router which is or was 2619 in the sending router's symmetric 1-hop neighborhood. 2621 o A consistently absent OTHER_NEIGHB Address Block TLV may, 2622 incorrectly, fail to identify a network address as being of a 2623 router which is or was in the sending router's symmetric 1-hop 2624 neighborhood. 2626 o The Value of a LINK_STATUS Address Block TLV may incorrectly 2627 indicate the status (LOST, SYMMETRIC or HEARD) of the link from 2628 a 1-hop neighbor. 2630 o The Value of an OTHER_NEIGHB Address Block TLV may incorrectly 2631 indicate the status (LOST or SYMMETRIC) of a symmetric 1-hop 2632 neighbor. 2634 17.2. Authentication, Integrity and Confidentiality Suggestions 2636 The security suggestions in [RFC5444] regarding inclusion of a 2637 cryptographic signature in a Message TLV or a Packet TLV can be 2638 applied to this protocol. Failure to verify either form of 2639 cryptographic signature should cause a HELLO message to be rejected 2640 without being processed. 2642 The following simplification of the suggestions for end-to-end 2643 authentication for integrity in [RFC5444] may be applied to HELLO 2644 messages: 2646 o As the Message Header fields and 2647 are either omitted or will always have the values 0 and 1, 2648 respectively, an end to end cryptographic signature can be 2649 calculated based on the entire HELLO message, including its 2650 unmodified Message Header. 2652 The security mechanisms suggested in [RFC5444] with respect to 2653 confidentiality can be directly applied to this protocol. 2655 18. IANA Considerations 2657 This specification defines one Message Type, which must be allocated 2658 from the "Message Types" repository of [RFC5444], and three Address 2659 Block TLV Types, which must be allocated from the "Address Block TLV 2660 Types" repository of [RFC5444]. 2662 18.1. Expert Review: Evaluation Guidelines 2664 For the registries where an Expert Review is required, the designated 2665 expert SHOULD take the same general recommendations into 2666 consideration as are specified by [RFC5444]. 2668 18.2. Message Types 2670 This specification defines one Message Type, to be allocated from the 2671 0-223 range of the "Message Types" namespace defined in [RFC5444], as 2672 specified in Table 3. 2674 +------+-------------------------+ 2675 | Type | Description | 2676 +------+-------------------------+ 2677 | TBD1 | HELLO : Local signaling | 2678 +------+-------------------------+ 2680 Table 3: Message Type assignment 2682 18.3. Message-Type-Specific TLV Type Registries 2684 IANA is requested to create a registry for Message-Type-specific 2685 Message TLVs for HELLO messages, in accordance with Section 6.2.1 of 2686 [RFC5444], and with initial assignments and allocation policies as 2687 specified in Table 4. 2689 +---------+-------------+-------------------+ 2690 | Type | Description | Allocation Policy | 2691 +---------+-------------+-------------------+ 2692 | 128-223 | Unassigned | Expert Review | 2693 +---------+-------------+-------------------+ 2695 Table 4: HELLO Message-Type-specific Message TLV Types 2697 IANA is requested to create a registry for Message-Type-specific 2698 Address Block TLVs for HELLO messages, in accordance with Section 2699 6.2.1 of [RFC5444], and with initial assignments and allocation 2700 policies as specified in Table 5. 2702 +---------+-------------+-------------------+ 2703 | Type | Description | Allocation Policy | 2704 +---------+-------------+-------------------+ 2705 | 128-223 | Unassigned | Expert Review | 2706 +---------+-------------+-------------------+ 2708 Table 5: HELLO Message-Type-specific Address Block TLV Types 2710 18.4. Address Block TLV Types 2712 This specification defines three Address Block TLV Types, which must 2713 be allocated from the "Address Block TLV Types" namespace defined in 2714 [RFC5444]. IANA are requested to make allocations in the 0-127 range 2715 for these types. This will create three new type extension 2716 registries with assignments as specified in Table 6, Table 7 and 2717 Table 8. Specifications of these Address Block TLVs are in 2718 Section 10.1.1, with Value Constants defined in Section 18.5. 2720 +----------+------+-----------+------------------------+------------+ 2721 | Name | Type | Type | Description | Allocation | 2722 | | | extension | | policy | 2723 +----------+------+-----------+------------------------+------------+ 2724 | LOCAL_IF | TBD2 | 0 | Specifies that the | | 2725 | | | | network address is | | 2726 | | | | associated with this | | 2727 | | | | local interface of the | | 2728 | | | | sending router | | 2729 | | | | (THIS_IF = 0) or | | 2730 | | | | another local | | 2731 | | | | interface of the | | 2732 | | | | sending router | | 2733 | | | | (OTHER_IF = 1) | | 2734 | LOCAL_IF | TBD2 | 1-255 | Unassigned | Expert | 2735 | | | | | Review | 2736 +----------+------+-----------+------------------------+------------+ 2738 Table 6: Address Block TLV Type assignment: LOCAL_IF 2740 +-------------+------+-----------+---------------------+------------+ 2741 | Name | Type | Type | Description | Allocation | 2742 | | | extension | | policy | 2743 +-------------+------+-----------+---------------------+------------+ 2744 | LINK_STATUS | TBD3 | 0 | Specifies the | | 2745 | | | | status of the link | | 2746 | | | | from the indicated | | 2747 | | | | network address | | 2748 | | | | (LOST = 0, | | 2749 | | | | SYMMETRIC = 1, or | | 2750 | | | | HEARD = 2) | | 2751 | LINK_STATUS | TBD3 | 1-255 | Unassigned | Expert | 2752 | | | | | Review | 2753 +-------------+------+-----------+---------------------+------------+ 2755 Table 7: Address Block TLV Type assignment: LINK_STATUS 2757 +--------------+------+-----------+--------------------+------------+ 2758 | Name | Type | Type | Description | Allocation | 2759 | | | extension | | policy | 2760 +--------------+------+-----------+--------------------+------------+ 2761 | OTHER_NEIGHB | TBD4 | 0 | Specifies that the | | 2762 | | | | network address is | | 2763 | | | | (SYMMETRIC = 1) or | | 2764 | | | | recently was (LOST | | 2765 | | | | = 0) of an | | 2766 | | | | interface of a | | 2767 | | | | symmetric 1-hop | | 2768 | | | | neighbor of the | | 2769 | | | | router | | 2770 | | | | transmitting the | | 2771 | | | | message | | 2772 | OTHER_NEIGHB | TBD4 | 1-255 | Unassigned | Expert | 2773 | | | | | Review | 2774 +--------------+------+-----------+--------------------+------------+ 2776 Table 8: Address Block TLV Type assignment: OTHER_NEIGHB 2778 18.5. LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Values 2780 Note: This section does not require any IANA action, as the required 2781 information is included in the descriptions of the Address Block TLVs 2782 allocated in Section 18.4. This information is recorded here for 2783 clarity, and for use elsewhere in this specification. 2785 The Values which the LOCAL_IF Address Block TLV can use are the 2786 following: 2788 o THIS_IF := 0 2790 o OTHER_IF := 1 2792 The Values which the LINK_STATUS Address Block TLV can use are the 2793 following: 2795 o LOST := 0 2797 o SYMMETRIC := 1 2799 o HEARD := 2 2801 The Values which the OTHER_NEIGHB Address Block TLV can use are the 2802 following: 2804 o LOST := 0 2806 o SYMMETRIC := 1 2808 19. Contributors 2810 This specification is the result of the joint efforts of the 2811 following contributors, listed alphabetically. 2813 o Brian Adamson, NRL, USA, 2815 o Cedric Adjih, INRIA, France, 2817 o Thomas Heide Clausen, LIX, France, 2819 o Justin Dean, NRL, USA, 2821 o Christopher Dearlove, BAE Systems ATC, UK, 2822 2824 o Philippe Jacquet, INRIA, France, 2826 20. Acknowledgments 2828 The authors would like to acknowledge the team behind OLSRv1, 2829 specified in RFC3626 for their contributions. 2831 The authors would like to gratefully acknowledge the following people 2832 for intense technical discussions, early reviews and comments on the 2833 specification and its components (listed alphabetically): Alan Cullen 2834 (BAE Systems), Ulrich Herberg (LIX), Satoh Hiroki (Hitachi) Joe 2835 Macker (NRL), Charles E. Perkins (WiChorus), Laurent Viennot (INRIA), 2836 and the entire IETF MANET working group. 2838 21. References 2840 21.1. Normative References 2842 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2843 Requirement Levels", RFC 2119, BCP 14, March 1997. 2845 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 2846 considerations in MANETs", RFC 5148, February 2008. 2848 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2849 "Generalized MANET Packet/Message Format", RFC 5444, 2850 February 2009. 2852 [RFC5497] Clausen, T. and C. Dearlove, "Representing multi-value 2853 time in MANETs", RFC 5497, March 2009. 2855 [RFC5498] Chakeres, I., "IANA Allocations for MANET Protocols", 2856 RFC 5498, March 2009. 2858 21.2. Informative References 2860 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 2861 (MANET): Routing Protocol Performance Issues and 2862 Evaluation Considerations", RFC 2501, January 1999. 2864 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 2865 Routing Protocol", RFC 3626, October 2003. 2867 [RFC5449] Clausen, T., Baccelli, E., Nguyen, D., and P. Jacquet, 2868 "OSPF Multipoint Relay (MPR) Extension for Ad Hoc 2869 Networks", RFC 5449, February 2009. 2871 Appendix A. Address Block TLV Combinations 2873 The algorithm for generating HELLO messages in Section 11 specifies 2874 which 1-hop neighbor network addresses may be included in the Address 2875 Blocks, and with which associated Address Block TLVs. These Address 2876 Block TLVs may have Type = LINK_STATUS or Type = OTHER_NEIGHB, or 2877 both. Address Block TLVs with Type = LINK_STATUS may have three 2878 possible Values (Value = HEARD, Value = SYMMETRIC or Value = LOST), 2879 and Address Block TLVs of TYPE = OTHER_NEIGHB may have two possible 2880 Values (Value = SYMMETRIC or Value = LOST). When both Address Block 2881 TLVs are associated with the same network address only certain 2882 combinations of these Address Block TLV Values are necessary, and are 2883 the only combinations generated by the algorithm in Section 11. 2885 These combinations are indicated in Table 9. 2887 Cells labeled with "Yes" indicate the possible combinations which are 2888 generated by the algorithm in Section 11. Cells labeled with "No" 2889 indicate combinations not generated by the algorithm in Section 11, 2890 but which are correctly parsed and interpreted by the algorithm in 2891 Section 12. The cell labeled with "No*" is actually inconsistent, it 2892 is handled by ignoring the Address Block TLV with Type = 2893 OTHER_NEIGHB, but SHOULD NOT be used. 2895 +----------------+----------------+----------------+----------------+ 2896 | | Type = | Type = | Type = | 2897 | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | 2898 | | (absent) | Value = | Value = LOST | 2899 | | | SYMMETRIC | | 2900 +----------------+----------------+----------------+----------------+ 2901 | Type = | No | Yes | Yes | 2902 | LINK_STATUS | | | | 2903 | (absent) | | | | 2904 | Type = | Yes | Yes | Yes | 2905 | LINK_STATUS, | | | | 2906 | Value = HEARD | | | | 2907 | Type = | Yes | No | No* | 2908 | LINK_STATUS, | | | | 2909 | Value = | | | | 2910 | SYMMETRIC | | | | 2911 | Type = | Yes | Yes | No | 2912 | LINK_STATUS, | | | | 2913 | Value = LOST | | | | 2914 +----------------+----------------+----------------+----------------+ 2916 Table 9: LINK_STATUS and OTHER_NEIGHB TLV combinations 2918 Appendix B. Constraints 2920 Any process which updates the Local Information Base or the Neighbor 2921 Information Base MUST ensure that all constraints specified in this 2922 appendix are maintained. 2924 In each Local Interface Tuple: 2926 o I_local_iface_addr_list MUST NOT be empty. 2928 o I_local_iface_addr_list MUST NOT contain any duplicated network 2929 addresses. 2931 o If I_manet = true, then I_local_iface_addr_list MUST NOT contain 2932 any network address which overlaps any network address in the 2933 I_local_iface_addr_list of any other Local Interface Tuple with 2934 I_manet = true, unless it is known that the corresponding MANET 2935 interfaces will always communicate with separate sets of MANET 2936 interfaces on other routers. 2938 In each Removed Interface Address Tuple: 2940 o IR_local_iface_addr MUST NOT contain any network address which is 2941 in the I_local_iface_addr_list of any Local Interface Tuple. 2943 o IR_local_iface_addr MUST NOT equal the IR_local_iface_addr of any 2944 other Removed Interface Address Tuple. 2946 In each Link Tuple: 2948 o L_neighbor_iface_addr_list MUST NOT be empty. 2950 o L_neighbor_iface_addr_list MUST NOT contain any network address 2951 which overlaps any network address in the I_local_iface_addr_list 2952 of any Local Interface Tuple or the IR_local_iface_addr of any 2953 Removed Interface Address Tuple. 2955 o L_neighbor_iface_addr_list MUST NOT contain any duplicated network 2956 addresses. 2958 o L_neighbor_iface_addr_list MUST NOT contain any network address 2959 which is in the L_neighbor_iface_addr_list of any other Link Tuple 2960 in the same Link Set. 2962 o If L_HEARD_time has not expired then there MUST be a Neighbor 2963 Tuple whose N_neighbor_addr_list contains 2964 L_neighbor_iface_addr_list. 2966 o L_HEARD_time MUST NOT be greater than L_time. 2968 o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are 2969 expired). 2971 o L_quality MUST NOT be less than 0 or greater than 1. 2973 o If L_quality >= HYST_ACCEPT then L_pending MUST be false. 2975 o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST. 2977 o L_pending MUST NOT be set to true if it is currently false. 2979 In each Neighbor Tuple: 2981 o N_neighbor_addr_list MUST NOT contain any network address which 2982 overlaps any network address in the I_local_iface_addr_list of any 2983 Local Interface Tuple or the IR_local_iface_addr of any Removed 2984 Interface Address Tuple. 2986 o N_neighbor_addr_list MUST NOT contain any duplicated network 2987 addresses. 2989 o N_neighbor_addr_list MUST NOT contain any network address which is 2990 in the N_neighbor_addr_list of any other Neighbor Tuple. 2992 o If N_symmetric is = true, then there MUST be one or more Link 2993 Tuples with: 2995 o L_neighbor_iface_addr_list contained in N_neighbor_addr_list; 2996 AND 2998 o L_status = SYMMETRIC. 3000 o If N_symmetric is = false, then there MUST be one or more Link 3001 Tuples with: 3003 o L_neighbor_iface_addr_list contained in N_neighbor_addr_list. 3005 All such Link Tuples MUST NOT have L_status = SYMMETRIC. At least 3006 one such Link Tuple MUST have L_HEARD_time not expired. 3008 In each Lost Neighbor Tuple: 3010 o NL_neighbor_addr MUST NOT overlap any network address in the 3011 I_local_iface_addr_list of any Local Interface Tuple or the 3012 IR_local_iface_addr of any Removed Interface Address Tuple. 3014 o NL_neighbor_addr MUST NOT equal the NL_neighbor_addr of any other 3015 Lost Neighbor Tuple. 3017 o NL_neighbor_addr MUST NOT be in the N_neighbor_addr_list of any 3018 Neighbor Tuple with N_symmetric = true. 3020 In each 2-Hop Tuple: 3022 o There MUST be a Link Tuple associated with the same MANET 3023 interface with: 3025 o L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list; AND 3027 o L_status = SYMMETRIC. 3029 o N2_2hop_addr MUST NOT overlap any network address in the 3030 I_local_iface_addr_list of any Local Interface Tuple or the 3031 IR_local_iface_addr of any Removed Interface Address Tuple. 3033 o N2_2hop_addr MUST NOT be the N2_2hop_addr of any other 2-Hop Tuple 3034 in the same 2-Hop Set and with the same 3035 N2_neighbor_iface_addr_list. 3037 o N2_2hop_addr MUST NOT be in the N2_neighbor_iface_addr_list of the 3038 same 2-Hop Tuple. 3040 Appendix C. HELLO Message Example 3042 HELLO messages are instances of [RFC5444] messages, and this protocol 3043 supports any combination of message header options and address 3044 encodings, enabled by [RFC5444] that convey the required information. 3045 As a consequence, there is no single way to represent how all HELLO 3046 messages look. This appendix illustrates two HELLO message with 3047 similar content, the exact values included are explained in the 3048 following text. 3050 The HELLO message's four bit Message Flags (MF) field has value 7 3051 indicating that the message header contains hop limit, hop count and 3052 message sequence number fields. Its four bit Message Address Length 3053 (MAL) field has value 3 indicating addresses in the message have 3054 length four octets, here being IPv4 addresses. The message is as 3055 transmitted, with a hop limit of 1 and a hop count of 0. The overall 3056 message length is 45 octets. 3058 The message contains a Message TLV Block with content length 8 octets 3059 containing two Message TLVs, of types VALIDITY_TIME and 3060 INTERVAL_TIME. Each uses a Message TLV with Flags octet (MTLVF) 3061 value 16, indicating that each has a Value, and each has a Value 3062 Length of 1 octet. The Values included are time codes (as defined in 3063 [RFC5497]) representing the parameters H_HOLD_TIME and 3064 HELLO_INTERVAL, respectively. 3066 The message has a single Address Block containing 5 addresses. The 3067 Address Block Flags octet (ABF) value 128 indicates an address Head 3068 but no address Tail, and no address prefixes. The Head Length of 3 3069 octets indicates address Mid sections of one octet each (Mid 0 to Mid 3070 4). 3072 The following Address Block TLV Block (content length 14 octets) 3073 includes two Address Block TLVs. The first is a LOCAL_IF Address 3074 Block TLV with Flags octet (ATLVF) value 80, which indicates that a 3075 single address, with index 0 (i.e., the address Head:Mid 0) is the 3076 single local interface address of this router (the 1 octet Value 3077 THIS_IF indicates that this address is of this interface). The 3078 second is a LINK_STATUS Address Block TLV with Flags octet (ATLVF) 3079 value 52, which specifies the link status values of all reported 3080 neighbors in a single multivalue Address Block TLV that covers the 3081 addresses with indexes 1 to 4, inclusive. The Address Block TLV 3082 Value Length of 4 octets indicates one octet per Value per address. 3083 The last four addresses thus are of neighbors, each an with 3084 associated link status: the first and second HEARD, the third 3085 SYMMETRIC, and the fourth LOST. 3087 0 1 2 3 3088 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 3089 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3090 | HELLO | MF=7 | MAL=3 | Message Length = 45 | 3091 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3092 | Hop Limit = 1 | Hop Count = 0 | Message Sequence Number | 3093 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3094 | Message TLV Block Length = 8 | VALIDITY_TIME | MTLVF = 16 | 3095 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3096 | Value Len = 1 | Value (Time) | INTERVAL_TIME | MTLVF = 16 | 3097 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3098 | Value Len = 1 | Value (Time) | Num Addrs = 5 | ABF = 128 | 3099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3100 | Head Len = 3 | Head | 3101 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3102 | Mid 0 | Mid 1 | Mid 2 | Mid 3 | 3103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3104 | Mid 4 | Address TLV Block Length = 14 | LOCAL_IF | 3105 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3106 | ATLVF = 80 | Index = 0 | Value Len = 1 | THIS_IF | 3107 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3108 | LINK_STATUS | ATLV = 52 | Strt Indx = 1 | Stop Indx = 4 | 3109 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3110 | Value Len = 4 | HEARD | HEARD | SYMMETRIC | 3111 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3112 | LOST | 3113 +-+-+-+-+-+-+-+-+ 3115 Note that this example is for illustrative purposes. The essential 3116 information can be conveyed, more efficiently (assuming that the 3117 local interface address will be supplied by IP, and that the 3118 INTERVAL_TIME TLV is not needed) by the 29 octets: 3120 0 1 2 3 3121 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 3122 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3123 | 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| 3124 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3125 |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| 3126 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3127 |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| 3128 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3129 |0 0 0 0 0 0 1 1| Head | 3130 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3131 | Mid 1 | Mid 2 | Mid 3 | Mid 4 | 3132 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3133 |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| 3134 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3135 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 3136 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3137 | LOST | 3138 +-+-+-+-+-+-+-+-+ 3140 Note that the above example assumes that H_HOLD_TIME and C have their 3141 default values of 6 seconds and 1/1024 second, and thus result in a 3142 time code of 100 (hexadecimal 64). 3144 Appendix D. Flow and Congestion Control 3146 This protocol specifies one Message Type, the HELLO message. The 3147 maximum size of a HELLO message is proportional to the size of the 3148 originating router's 1-hop neighborhood. HELLO messages MUST NOT be 3149 forwarded. 3151 A router MUST report its 1-hop neighborhood in HELLO messages on each 3152 of its MANET interfaces at least each REFRESH_INTERVAL. This puts a 3153 lower bound on the control traffic generated by each router in the 3154 network employing this protocol. 3156 A router MUST ensure that two successive HELLO messages sent on the 3157 same MANET interface are separated by at least HELLO_MIN_INTERVAL. 3158 (If using jitter then this may be reduced to a mean minimum value of 3159 HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound 3160 on the control traffic generated by each router in the network 3161 employing this protocol. 3163 Appendix E. Interval and Timer Illustrations 3165 This informative appendix illustrates the relationship between 3166 message timers and intervals. (The adjustments to this timing when 3167 using timing jitter, as defined in [RFC5148], are not shown.) 3169 E.1. HELLO Message Generation Timing 3171 Figure 1 illustrates a basic HELLO message schedule for a router, on 3172 a MANET interface, employing strictly periodic transmission of HELLO 3173 messages. The router transmits a HELLO message each HELLO_INTERVAL. 3174 Each HELLO message contains all 1-hop neighbor network addresses of 3175 the router that are to be reported in any such HELLO message. (The 3176 parameter REFRESH_INTERVAL, not shown, is in this example equal to 3177 the parameter HELLO_INTERVAL.) 3179 The router includes a VALIDITY_TIME TLV in each HELLO message, 3180 encoding the parameter H_HOLD_TIME, the duration for which 3181 information received in the HELLO message should be considered valid 3182 by receiving routers. Receiving routers will, when recording the 3183 information received in the HELLO message, each use this for setting 3184 the L_HEARD_time, L_SYM_time and L_time elements of their 3185 corresponding Link Tuple, and the N2_time in the corresponding 2-Hop 3186 Tuple for each network address. Only L_time is illustrated in 3187 Figure 1. 3189 H_HOLD_TIME: |-----------------------------| ... 3191 HELLO_INTERVAL: |---------|---------|---------| ... 3193 Time: ---*---------*---------*---------*------> 3195 ^ ^ ^ ^ 3196 | | | | 3197 HELLO (a, b, c, d) | | | 3198 | | | 3199 HELLO (a, b, c, d) | | ... 3200 | | 3201 HELLO (a, b, c, d) | 3202 | 3203 HELLO (a, b, c, d) 3205 L_time: |-----------------------------| 3206 |-------------------- ... 3207 |---------- ... 3208 | ... 3210 Figure 1: HELLO message generation: regular schedule 3212 Figure 2 illustrates a message schedule similar to Figure 1, where 3213 the router announces its own presence more frequently by sending 3214 additional HELLO messages. HELLO messages are still sent regularly, 3215 at a reduced interval defined by a new value of HELLO_INTERVAL. 3216 However REFRESH_INTERVAL has not been reduced. Each 1-hop neighbor 3217 network address included in these HELLO messages need be advertised 3218 only once within each REFRESH_INTERVAL. Consequently the additional 3219 HELLO messages due to the reduced value of HELLO_INTERVAL may 3220 therefore be empty. (This is not the only allowed distribution of 3221 1-hop neighbor network addresses, they could, for example, be sent 3222 alternately a, b and c, d.) 3224 H_HOLD_TIME: |-----------------------------| ... 3226 REFRESH_INTERVAL: |---------|---------|---------| ... 3228 HELLO_INTERVAL: |----|----|----|----|----|----| ... 3230 Time: ---*---------*---------*---------*------> 3232 ^ ^ ^ ^ ^ ^ ^ 3233 | | | | | | | 3234 HELLO (a, b, c, d) | | | | | | 3235 | | | | | | 3236 HELLO () | | | | | 3237 | | | | | 3238 HELLO (a, b, c, d) | | | | 3239 | | | | ... 3240 HELLO () | | | 3241 | | | 3242 HELLO (a, b, c, d) | | 3243 | | 3244 HELLO () | 3245 | 3246 HELLO (a, b, c, d) 3248 L_time: |-----------------------------| 3249 |------------------------- ... 3250 |-------------------- ... 3251 |--------------- ... 3252 |---------- ... 3253 |----- ... 3254 | ... 3256 Figure 2: HELLO message generation: regular schedule with different 3257 HELLO_INTERVAL and REFRESH_INTERVAL 3259 HELLO messages may also be sent in response to events. The minimal 3260 interval between two successive HELLO message transmissions by a 3261 router is HELLO_MIN_INTERVAL, setting an upper bound of the HELLO 3262 message emission rate. Hence, for each HELLO message transmission, a 3263 router must wait at least HELLO_MIN_INTERVAL before the next HELLO 3264 message transmission. Similarly, the maximum interval between two 3265 successive HELLO message transmissions is HELLO_INTERVAL, setting a 3266 lower bound on the message transmission rate. Hence, for each HELLO 3267 message transmission, the router must ensure that the next HELLO 3268 message transmission must not wait more than HELLO_INTERVAL. 3270 Figure 3 illustrates a message schedule similar to Figure 1, but with 3271 HELLO messages responding to events at maximum rate, i.e., with HELLO 3272 messages being sent each HELLO_MIN_INTERVAL. Note that when a HELLO 3273 message is sent, it is assumed that the following messages may all be 3274 scheduled at an interval of HELLO_INTERVAL, and hence each HELLO 3275 message contains all 1-hop neighbor network addresses. In each HELLO 3276 message in this example, a new 1-hop neighbor network address is 3277 added, reflecting the changes occurring since the last HELLO message 3278 was sent. HELLO messages are sent at the maximum allowed rate in 3279 order to signal these changes as rapidly as possible. 3281 H_HOLD_TIME: |-----------------------------| ... 3283 HELLO_INTERVAL: |---------|---------|---------| ... 3285 HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... 3287 Time: ---*---------*---------*---------*------> 3289 ^ ^ ^ ^ ^ ^ ^ 3290 | | | | | | | 3291 HELLO () | | | | | | 3292 | | | | | | 3293 HELLO (a) | | | | | 3294 | | | | | 3295 HELLO (a, b) | | | | 3296 | | | | ... 3297 HELLO (a, b, c) | | | 3298 | | | 3299 HELLO (a, b, c, d) | | 3300 | | 3301 HELLO (a, b, c, d, e) | 3302 | 3303 HELLO (a, b, c, d, e, f) 3305 L_time: |-----------------------------| 3306 |------------------------- ... 3307 |-------------------- ... 3308 |--------------- ... 3309 |---------- ... 3310 |----- ... 3311 | ... 3313 Figure 3: HELLO message generation: regular schedule with responsive 3314 messages 3316 Figure 4 shows the same example as Figure 3, but with an increased 3317 REFRESH_INTERVAL, and showing partial HELLO messages which include 3318 only the necessary network addresses. 3320 H_HOLD_TIME: |-----------------------------| ... 3322 REFRESH_INTERVAL: |-------------------|---------- ... 3323 |-------------------|----- ... 3324 |-------------------| ... 3325 |--------------- ... 3326 |---------- ... 3327 |----- ... 3328 | ... 3330 HELLO_INTERVAL: |---------|---------|---------| ... 3332 HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... 3334 Time: ---*---------*---------*---------*------> 3336 ^ ^ ^ ^ ^ ^ ^ 3337 | | | | | | | 3338 HELLO () | | | | | | 3339 | | | | | | 3340 HELLO (a) | | | | | 3341 | | | | | 3342 HELLO (b) | | | | 3343 | | | | ... 3344 HELLO (c) | | | 3345 | | | 3346 HELLO (a, d) | | 3347 | | 3348 HELLO (b, e) | 3349 | 3350 HELLO (c, f) 3352 L_time: |-----------------------------| 3353 |------------------------- ... 3354 |-------------------- ... 3355 |--------------- ... 3356 |---------- ... 3357 |----- ... 3358 | ... 3360 Figure 4: HELLO message generation: regular schedule with responsive 3361 messages and different HELLO_INTERVAL and REFRESH_INTERVAL 3363 Figure 5 summarizes the overall relationship between the intervals 3364 governing HELLO message transmissions by a router. 3366 H_HOLD_TIME: |------------------------------------| 3368 REFRESH_INTERVAL: |----------------| 3370 HELLO_INTERVAL: |----------| 3372 HELLO_MIN_INTERVAL: |---| 3374 Time: -----------------------------------------------> 3376 ^ ^ ^ ^ ^ 3377 | | | | | 3378 | | | | Time up to which 3379 HELLO message | | | received HELLO 3380 transmission | | | message content 3381 | | | is valid. 3382 | | | 3383 | | Time before which all 3384 | | neighbor information must 3385 | | be transmitted in HELLO 3386 | | messages (one or more) 3387 | | 3388 | Latest time for next HELLO message 3389 | transmission 3390 | 3391 Earliest time for next HELLO message 3392 transmission 3394 Figure 5: HELLO message generation intervals 3396 E.2. HELLO Message Processing Timing 3398 Figure 6 illustrates the Link Set timers when receiving a HELLO 3399 message not including the network address of the receiving MANET 3400 interface. 3402 VALIDITY_TIME: |--------------------------| 3404 L_time: |--------------------------| 3406 L_HEARD_time: |--------------------------| 3408 L_SYM_time: *-| (i.e., expired) 3410 Time: ---*--------------------------------> 3411 ^ 3412 | 3413 HELLO () received 3415 Figure 6: HELLO message processing: network address not present 3417 Figure 7 illustrates the Link Set timers when, following the received 3418 HELLO message illustrated in Figure 6, a router receives a HELLO 3419 message including the network address (a) of the receiving interface 3420 with link status = HEARD (or SYM). 3422 VALIDITY_TIME: |--------------------------| 3423 |--------------------------| 3425 L_time: |--------------------------| 3426 |--------------------------| 3428 L_HEARD_time: |--------------------------| 3429 |--------------------------| 3431 L_SYM_time: *-| (i.e., expired) 3432 L_SYM_time: |--------------------------| 3434 Time: -*-----*---------------------------------> 3435 ^ ^ 3436 | | 3437 HELLO () received | 3438 | 3439 HELLO (a:HEARD) received 3441 Figure 7: HELLO message processing: network address present 3443 Figure 8 illustrates the Link Set timers when, following the received 3444 HELLO messages illustrated in Figure 7, a router receives a HELLO 3445 message including the network address (a) of the receiving interface 3446 with link status = LOST. 3448 VALIDITY_TIME: |--------------------------| 3449 |--------------------------| 3450 |--------------------------| 3452 L_time: |--------------------------| 3453 |--------------------------| 3454 |--------------------------| 3456 L_HEARD_time: |--------------------------| 3457 |--------------------------| 3458 |--------------------------| 3460 L_SYM_time: *-| (i.e., expired) 3461 |--------------------------| 3462 *-| (i.e., expired) 3464 Time: -*-----*-----*---------------------------------> 3465 ^ ^ ^ 3466 | | | 3467 HELLO () received | | 3468 | | 3469 HELLO (a:HEARD) received | 3470 | 3471 HELLO (a:LOST) received 3473 Figure 8: HELLO message processing: network address lost 3475 E.3. Other HELLO Message Timing 3477 There are three other timing parameters which are used by a router to 3478 control HELLO message generation and processing. 3480 Figure 9 illustrates the time, with duration L_HOLD_TIME, during 3481 which the appropriate network addresses of a formerly, but no longer, 3482 symmetric 1-hop neighbor, as connected by this MANET interface, are 3483 advertised as LOST using a LINK_STATUS TLV in HELLO messages on this 3484 MANET interface, thus allowing that 1-hop neighbor to update its Link 3485 Set accordingly. 3487 L_HOLD_TIME: |----------------------------| 3489 Time: ---*----------------------------------> 3490 ^ ^ 3491 | | 3492 Formerly symmetric 1-hop neighbor | 3493 ceases to be symmetric on this | 3494 MANET interface | 3495 | 3496 Time up to which network addresses of 3497 this neighbor connected using this MANET 3498 interface are advertised in HELLO 3499 messages on this MANET interface 3500 using a LINK_STATUS TLV, Value = LOST 3502 Figure 9: HELLO message generation: advertisement of formerly 3503 symmetric 1-hop neighbor on this MANET interface as lost 3505 Figure 10 illustrates the time, with duration N_HOLD_TIME, during 3506 which all network addresses of a formerly, but no longer, symmetric 3507 1-hop neighbor, are advertised as LOST in HELLO messages on all MANET 3508 interfaces using an OTHER_NEIGHB TLV (if not also reported using a 3509 LINK_STATUS TLV) thus allowing all other symmetric 1-hop neighbors to 3510 update their 2-Hop Sets accordingly. 3512 L_HOLD_TIME: |----------------------------| 3514 Time: ---*----------------------------------> 3515 ^ ^ 3516 | | 3517 Formerly symmetric 1-hop neighbor | 3518 ceases to be symmetric | 3519 | 3520 Time up to which network addresses of 3521 this neighbor are advertised in HELLO 3522 messages on all MANET interfaces 3523 using an OTHER_NEIGHB TLV, 3524 Value = LOST 3526 Figure 10: HELLO message generation: advertisement of formerly 3527 symmetric 1-hop neighbor on any MANET interface as lost 3529 Figure 11 illustrates the time, with duration I_HOLD_TIME, during 3530 which a formerly, but no longer, used local interface network address 3531 is excluded from being considered as a 2-hop neighbor network address 3532 (in order that a router is not recorded as its own 2-hop neighbor 3533 during that period). 3535 I_HOLD_TIME: |----------------------------| 3537 Time: ---*-----------------------------------> 3538 ^ ^ 3539 | | 3540 Formerly used local interface | 3541 network address ceases to be | 3542 assigned to a local interface | 3543 | 3544 Time up to which this network 3545 address is excluded from being 3546 included in this router's 2-Hop Set 3548 Figure 11: Local interface removed network address 3550 Appendix F. Topology Pictures 3552 This appendix illustrates various examples of physical topologies, as 3553 well as how these are logically recorded by NHDP from the point of 3554 view of the router A. This representation is a composite of 3555 information which would be contained within A's various Information 3556 Bases after NHDP has been running for sufficiently long time for the 3557 state to converge. 3559 Note that the examples given in this appendix are NOT exhaustive, but 3560 are selected to be illustrative of NHDP neighborhood representations 3561 of physical MANET topologies. 3563 The example topologies presented contain 3 physical routers A, B and 3564 C. Each of these routers has one or two distinct interfaces, denoted 3565 "top" and "bottom". Each interface has one or two addresses, and 3566 symmetric connectivity between a pair of interfaces is illustrated by 3567 these being connected by a line. 3569 In all examples, the topology is described as it is recorded by NHDP 3570 in router A. 3572 F.1. Example 1: Standard Single Interface Topology 3574 In Figure 12, each router has a single interface, each with a single 3575 IP address. This is the simplest possible network, and the resulting 3576 representation is given to the right in Figure 12. 3578 __________ __________ 3579 | | | 3580 {1} {2} {3} 3581 | | | {1}--------{2}--------{3} 3582 +--'--+ +--'--+ +--'--+ 3583 | A | | B | | C | 3584 +-----+ +-----+ +-----+ 3586 Figure 12: Standard single interface topology (left), and 3587 corresponding NHDP representation (right) 3589 The Local Information Set in A contains a single Local Interface 3590 Tuple which has an I_local_iface_addr_list of {1}. This value is 3591 denoted with a {1} on the leftmost part of the resulting 3592 representation. 3594 The Interface Information Base has only one Link Set, which 3595 represents the "top" interface of A, or {1}. This Link Set's only 3596 Link Tuple has an L_neighbor_iface_addr_list containing {2}; this 3597 corresponds to the dashed line from {1} to {2} to the right in 3598 Figure 12. The 2-Hop Set contains a single 2-Hop Tuple, with 3599 N2_neighbor_iface_addr_list being {2} and N2_hop_addr being {3}; this 3600 corresponds to the dashed line from {2} to {3} to the right in 3601 Figure 12. 3603 The descriptions of the following examples in this appendix will be 3604 derived similarly, and use the same notational conventions. 3606 F.2. Example 2: Dual Addressed Interface on 1-Hop Neighbor 3608 In Figure 13, the network is identical to that in Example 1, except 3609 that the middle router, B, has two IP addresses on its single 3610 interface. 3612 __________ __________ 3613 | | | 3614 {1} {2,4} {3} 3615 | | | {1}-------{2,4}-------{3} 3616 +--'--+ +--'--+ +--'--+ 3617 | A | | B | | C | 3618 +-----+ +-----+ +-----+ 3620 Figure 13: Single interfaces, with 1-hop neighbor B having two 3621 addresses (left), and corresponding NHDP representation (right) 3623 The content of the Interface Information Base is in this case 3624 identical to Example 1, except that L_neighbor_iface_addr_list is 3625 {2,4} and N2_neighbor_iface_addr_list is {2,4}. 3627 F.3. Example 3: Dual Addressed Interface on 2-Hop Neighbor 3629 In Figure 14, the network is identical to that in Example 1, except 3630 that the rightmost router, C, has two IP addresses on its interface. 3632 __________ __________ 3633 | | | 3634 {1} {2} {3,4} +----{3} 3635 | | | {1}--------{2}---+ 3636 +--'--+ +--'--+ +--'--+ +----{4} 3637 | A | | B | | C | 3638 +-----+ +-----+ +-----+ 3640 Figure 14: Single interfaces, with 2-hop neighbor C having two 3641 addresses (left), and corresponding NHDP representation (right) 3643 The content of the Interface Information Base is in this case 3644 identical to than in Example 1, except that the 2-Hop Set contains an 3645 extra 2-Hop Tuple with N2_neighbor_iface_addr_list being {2} and 3646 N2_hop_addr being {4}. These two 2-Hop Tuples are illustrated by the 3647 two lines from {2} to {3} and (2) to {4}, respectively. 3649 F.4. Example 4: Dual Addressed Interfaces 3651 In Figure 15, the network is identical to that in Example 1, except 3652 that all routers have two IP addresses on their interface. The Local 3653 Information Base in router A is the same as in Example 1, except that 3654 I_local_iface_addr_list is {1,5}. 3656 __________ __________ 3657 | | | 3658 {1,5} {2,6} {3,4} +----{3} 3659 | | | {1,5}------{2,6}--+ 3660 +--'--+ +--'--+ +--'--+ +----{4} 3661 | A | | B | | C | 3662 +-----+ +-----+ +-----+ 3664 Figure 15: Single interfaces, all routers having two addresses 3665 (left), and corresponding NHDP representation (right) 3667 The content of the Interface Information Base is in this case a 3668 combination of the Interface Information Bases from Example 1, 3669 Example 2 and Example 3. 3671 F.5. Example 5: Dual Interface on 2-Hop Neighbor 3673 In Figure 16, all routers have a single IP address on each interface, 3674 and with the 2-hop neighbor having two interfaces. 3676 __________ __________ 3677 | | | 3678 {1} {2} {3} +----{3} 3679 | | | {1}--------{2}---+ 3680 +--'--+ +--'--+ +-----+ +----{4} 3681 | A | | B | | C | 3682 +-----+ +-----+ +-----+ 3683 | 3684 {4} 3686 Figure 16: Single addresses, with 2-hop neighbor C having two 3687 interfaces (left), and corresponding NHDP representation (right) 3689 The Interface Information Base is identical to that in Example 3; 3690 NHDP does not distinguish topologically between this example and 3691 Example 3. 3693 F.6. Example 6: Dual interface on 1-Hop Neighbor 3695 In Figure 17, all routers have a single IP address on each interface, 3696 and with the 1-hop neighbor having two interfaces. 3698 __________ 3699 | | 3700 {1} {2} +-----+ 3701 | | {1}-------| {2} |------{4} 3702 +--'--+ +--'--+ +-----+ | {5} | 3703 | A | | B | | C | +-----+ 3704 +-----+ +-----+ +-----+ 3705 | | 3706 {5} {4} 3707 |__________| 3709 Figure 17: Single addresses, with 1-hop neighbor B having two 3710 interfaces (left), and corresponding NHDP representation (right) 3712 The Local Information Base is identical to that in Example 1. 3714 The Interface Information Base has only one Link Set containing one 3715 Link Tuple with L_neighbor_iface_addr_list being {2}. The 2-Hop Set 3716 contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being 3717 {2} and N2_hop_addr being {4}. 3719 The Neighbor Information Base contains a Neighbor Set containing a 3720 single Neighbor Tuple, which represents router B, with 3721 N_neighbor_addr_list being {2,5}. This entry is represented on the 3722 right of Figure 17 by boxing {2} with {5}. 3724 Note that router A does not have information indicating which of 3725 router B's interfaces is connected to router C. However, router A 3726 knows that the address {4} (and thus router C) is reachable by using 3727 {2} as next hop. 3729 F.7. Example 7: Dual Interface on 1-Hop and 2-Hop Neighbors 3731 In Figure 18, all routers have a single IP address on each interface, 3732 and both the 1-hop and 2-hop neighbors have two interfaces. 3733 Furthermore, there are now two physical links between routers B and 3734 C, over distinct interface pairs. 3736 __________ __________ 3737 | | | 3738 {1} {2} {3} +-----+ +----{3} 3739 | | | {1}-------| {2} |---+ 3740 +--'--+ +--'--+ +-----+ | {5} | +----{4} 3741 | A | | B | | C | +-----+ 3742 +-----+ +-----+ +-----+ 3743 | | 3744 {5} {4} 3745 |__________| 3747 Figure 18: Single addresses, with 1-hop and 2-hop neighbors B and C 3748 having two interfaces (left), and corresponding NHDP representation 3749 (right) 3751 The Local Information Base is identical to that in Example 1. 3753 The Link Set is identical to that in Example 6, and the 2-Hop Set 3754 contains, as in Example 5 (and similarly to Examples 3 and 4), two 3755 2-Hop Tuples representing the two links between routers B and C 3757 Note that router A does not have information describing which of 3758 router B's interfaces is connected to which interfaces of router C, 3759 or even that the interfaces with addresses {3} and {4} are interfaces 3760 of the same router. However, router A knows that the addresses {3} 3761 and {4} (and thus router C) are reachable using {2} as next hop. 3763 F.8. Example 8: Dual Interface Locally and on 1-Hop Neighbor 3765 In Figure 19, all routers have a single IP address on each interface, 3766 and both A and its the 1-hop neighbor B have two interfaces. 3767 Furthermore, there are now two physical links between routers A and 3768 B, over distinct interface pairs. 3770 __________ __________ 3771 | | | +-----+ 3772 {1} {2} {3} {1}-------| {2} |--------{3} 3773 | | | | {5} | 3774 +--'--+ +--'--+ +-----+ +-----+ 3775 | A | | B | | C | 3776 +-----+ +-----+ +-----+ +-----+ 3777 | | | {2} | 3778 {6} {5} {6}-------| {5} |--------{3} 3779 |__________| +-----+ 3781 Figure 19: Single addresses, with both A and 1-hop neighbor B having 3782 two interfaces (left), and corresponding NHDP representation (right) 3784 The Local Information Set contains two Local Interface Tuples, with 3785 I_local_iface_addr_list of {1} and {6}, respectively. 3787 Each Interface Information Base's Link Set contains one Link Tuple, 3788 representing the links between {1} and {2}, and between {6} and {5}, 3789 respectively. The 2-Hop Set for interface {1} contains a single 3790 2-Hop Tuple, with N2_neighbor_iface_addr_list being {2} and 3791 N2_hop_addr being {3}. The 2-Hop Set for interface {6} contains a 3792 single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {5} and 3793 N2_hop_addr being {3}. 3795 The Neighbor Information Base contains a Neighbor Set containing a 3796 single Neighbor Tuple, which represents router B, with 3797 N_neighbor_addr_list being {2,5}. This entry is denoted by boxing 3798 {2} with {5}. 3800 F.9. Example 9: Dual Interface on All Routers 3802 In Figure 20, all routers have a single IP address on each interface, 3803 and all routers have two interfaces. Furthermore, there are now two 3804 physical links between A and B, over distinct interface pairs, and 3805 two physical links between B and C, also over distinct interface 3806 pairs. 3808 __________ __________ 3809 | | | +-----+ +----{3} 3810 {1} {2} {3} {1}-------| {2} |---+ 3811 | | | | {5} | +----{4} 3812 +--'--+ +--'--+ +-----+ +-----+ 3813 | A | | B | | C | 3814 +-----+ +-----+ +-----+ +-----+ 3815 | | | | {2} | +----{3} 3816 {6} {5} {4} {6}-------| {5} |---+ 3817 |__________|__________| +-----+ +----{4} 3819 Figure 20: Single addresses, with all routers having two interfaces 3820 (left), and corresponding NHDP representation (right) 3822 The Local Information Set is identical to that in Example 8. The 3823 Interface Information Base for each interface in A is also identical 3824 to that in Example 8, except that an additional 2-Hop Tuple is 3825 present in each 2-Hop Set, each representing the link between router 3826 B and the interface of router C with address {4}. 3828 As in Example 7, router A does not have information describing which 3829 of router B's interfaces is connected to which interface of C, or 3830 even that the interfaces with addresses {3} and {4} are interfaces of 3831 the same router. However, router A knows that the addresses {3} and 3832 {4} (and router C) are reachable by using {2} or {5} (depending on 3833 via which of its local interfaces) as next hop. 3835 F.10. Example 10: Dual Addressed Dual Interfaces on All Routers 3837 In Figure 21, all routers have two IP addresses on each interface, 3838 and all routers have two interfaces. Furthermore, there are now two 3839 physical links between A and B, over distinct interface pairs, and 3840 two physical links between B and C, also over distinct interface 3841 pairs. 3843 +--{9} 3844 __________ __________ +------| 3845 | | | +-----+ | +--{10} 3846 {1,2} {5,6} {9,10} {1,2}--|{5,6}|---+ 3847 | | | |{7,8}| | +--{11} 3848 +--'--+ +--'--+ +-----+ +-----+ +------| 3849 | A | | B | | C | +--{12} 3850 +-----+ +-----+ +-----+ 3851 | | | +--{9} 3852 | | | +-----+ +------| 3853 | | | |{5,6}| | +--{10} 3854 {3,4} {7,8} {11,12} {3,4}--|{7,8}|---+ 3855 |__________|__________| +-----+ | +--{11} 3856 +------| 3857 +--{12} 3859 Figure 21: Dual addresses, with all routers having two interfaces 3860 (left) and corresponding NHDP representation (right) 3862 This example is the combination of all the preceding examples in this 3863 appendix. The Local Information Set in A contains Local Information 3864 Tuples for each of its interfaces, and each Interface Information 3865 Base contains in its Link Set a representation of links {1,2}-{5,6} 3866 or {3,4}-{7,8}, respectively. The Neighbor Set (in the Neighbor 3867 Information Base) records the existence of router B and all of its 3868 addresses on all its interfaces, i.e., {5,6,7,8}. 3870 As in Example 9, each interface address of router C is represented in 3871 the 2-Hop Set of each Interface Information Base as a link from 3872 router B to each of these addresses. Router A does not have 3873 information describing which of router B's interfaces is connected to 3874 which interface of C, nor that the addresses {9}, {10}, {11}, and 3875 {12} are addresses of the same router (or that some of these, such as 3876 {9} and {10}, are addresses on the same interface of the router). 3878 F.11. Example 11: Single Addressed Dual Interface Locally 3880 In Figure 22, all routers have a single interface, except for router 3881 A which has two. Each of A's two interfaces has a link with the 3882 single interface of router B. All interfaces have a single address. 3884 __________ __________ 3885 | _____| | 3886 {1} | {2} {3} {1}--------{2}---------{3} 3887 | | | | 3888 +--'--+ | +--'--+ +-----+ 3889 | A | | | B | | C | 3890 +-----+ | +-----+ +-----+ 3891 | | 3892 {6} | {6}--------{2}---------{3} 3893 |____| 3895 Figure 22: Single addresses, with A having two interfaces, both 3896 linked to the single interface of B (left), and corresponding NHDP 3897 representation (right) 3899 This is similar to Example 8, except that the single address {2} also 3900 replaces the address {5}. In particular both Link Tuples (one in 3901 each Link Set, each in its corresponding Interface Information Base) 3902 have L_neighbor_iface_addr_list being {2}, the Neighbor Set (in the 3903 Neighbor Information Base) contains a single Neighbor Tuple with 3904 N_neighbor_addr_list being {2}, and both 2-Hop Tuples (one in each 3905 2-Hop Set, each in its corresponding Interface Information Base) have 3906 N2_neighbor_iface_list being {2} and N2_2hop_addr being {3}. 3908 Authors' Addresses 3910 Thomas Heide Clausen 3911 LIX, Ecole Polytechnique 3913 Phone: +33 6 6058 9349 3914 EMail: T.Clausen@computer.org 3915 URI: http://www.ThomasClausen.org/ 3917 Christopher Dearlove 3918 BAE Systems ATC 3920 Phone: +44 1245 242194 3921 EMail: chris.dearlove@baesystems.com 3922 URI: http://www.baesystems.com/ 3923 Justin W. Dean 3924 Naval Research Laboratory 3926 Phone: +1 202 767 3397 3927 EMail: jdean@itd.nrl.navy.mil 3928 URI: http://pf.itd.nrl.navy.mil/ 3930 The OLSRv2 Design Team 3931 MANET Working Group