idnits 2.17.1 draft-ietf-manet-nhdp-15.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 (December 19, 2010) is 4870 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: June 22, 2011 BAE Systems ATC 6 J. Dean 7 Naval Research Laboratory 8 The OLSRv2 Design Team 9 MANET Working Group 10 December 19, 2010 12 Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP) 13 draft-ietf-manet-nhdp-15 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 June 22, 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 . . . . . . . . . . . . . . . . 13 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 . . . . . . . . . . . . . . . . 16 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 . . . . . . . . . . . . . . . . . . . . 33 110 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 34 111 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 35 112 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 37 113 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 37 114 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 38 115 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 38 116 12.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 40 117 12.3. Updating the Neighbor Set . . . . . . . . . . . . . . . . 41 118 12.4. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 42 119 12.5. Updating the Link Sets . . . . . . . . . . . . . . . . . . 42 120 12.6. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 44 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 . . . . . . . . . . . . . . . . . . . . . . . . . 48 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 . . . . . . . . . 51 131 15.1. Message Interval Interface Parameters . . . . . . . . . . 51 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 . . . . . . . . . . . . . . . . . . . . . . . . 52 137 16. Usage with Other Protocols . . . . . . . . . . . . . . . . . . 52 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 . . . . . . 60 148 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 61 149 20. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 61 150 21. References . . . . . . . . . . . . . . . . . . . . . . . . . . 61 151 21.1. Normative References . . . . . . . . . . . . . . . . . . . 61 152 21.2. Informative References . . . . . . . . . . . . . . . . . . 62 153 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 62 154 Appendix B. Constraints . . . . . . . . . . . . . . . . . . . . . 63 155 Appendix C. HELLO Message Example . . . . . . . . . . . . . . . . 66 156 Appendix D. Flow and Congestion Control . . . . . . . . . . . . . 68 157 Appendix E. Interval and Timer Illustrations . . . . . . . . . . 69 158 E.1. HELLO Message Generation Timing . . . . . . . . . . . . . 69 159 E.2. HELLO Message Processing Timing . . . . . . . . . . . . . 75 160 E.3. Other HELLO Message Timing . . . . . . . . . . . . . . . . 76 161 Appendix F. Topology Pictures . . . . . . . . . . . . . . . . . . 78 162 F.1. Example 1: Standard Single Interface Topology . . . . . . 78 163 F.2. Example 2: Dual Addressed Interface on 1-Hop Neighbor . . 79 164 F.3. Example 3: Dual Addressed Interface on 2-Hop Neighbor . . 80 165 F.4. Example 4: Dual Addressed Interfaces . . . . . . . . . . . 80 166 F.5. Example 5: Dual Interface on 2-Hop Neighbor . . . . . . . 81 167 F.6. Example 6: Dual interface on 1-Hop Neighbor . . . . . . . 81 168 F.7. Example 7: Dual Interface on 1-Hop and 2-Hop Neighbors . . 82 169 F.8. Example 8: Dual Interface Locally and on 1-Hop Neighbor . 83 170 F.9. Example 9: Dual Interface on All Routers . . . . . . . . . 83 171 F.10. Example 10: Dual Addressed Dual Interfaces on All 172 Routers . . . . . . . . . . . . . . . . . . . . . . . . . 84 173 F.11. Example 11: Single Addressed Dual Interface Locally . . . 85 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 router's attachment to a communications medium. An 286 interface is assigned one or more 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. Each address in 487 the range of addresses represented by that network address MUST 488 satisfy the following properties: 490 o It MUST be unique to this router, i.e., it MUST NOT be assigned 491 to any interface of any other router. 493 o If assigned to other MANET interfaces, on the same router, 494 these MANET interfaces MUST be isolated, i.e., addresses may 495 only be assigned to different interfaces on the same router if 496 no MANET interface on another router can communicate with both. 497 For example interfaces using distinct radio "channels" MAY be 498 assigned the same address. 500 o Has a set of interface parameters, defining the behavior of this 501 MANET interface. Each MANET interface MAY be individually 502 parameterized. 504 o Has an Interface Information Base, recording information regarding 505 links to this MANET interface and symmetric 2-hop neighbors which 506 can be reached through such links. 508 o Generates and processes HELLO messages. 510 In addition to a set of MANET interfaces as described above, each 511 router has: 513 o A Local Information Base, containing the network addresses of the 514 interfaces (MANET and non-MANET) of this router. The contents of 515 this Information Base are not changed by signaling. 517 o A Neighbor Information Base, recording information regarding 518 current and recently lost 1-hop neighbors of this router. 520 A router may have both MANET interfaces and non-MANET interfaces. 521 Interfaces of both of these types are recorded in a router's Local 522 Information Base, which is used, but not updated, by the signaling of 523 this protocol. 525 4.2. Information Base Overview 527 Each router maintains protocol state using Information Bases, 528 described in the following sections. Each Information Base consists 529 of a number of Protocol Sets. Each Protocol Set contains a number of 530 Protocol Tuples. 532 An implementation of this protocol MAY maintain this information in 533 the indicated form, or in any other organization which offers access 534 to this information. In particular, note that it is not necessary to 535 remove Protocol Tuples from Protocol Sets at the exact time 536 indicated, only to behave as if the Protocol Tuples were removed at 537 that time. 539 Information in the Local Information Base is defined locally, and 540 included in HELLO messages. Information in the Interface Information 541 Base and the Neighbor Information Base is determined from received 542 HELLO messages; some of this information may also be included in 543 transmitted HELLO messages. Such information has a limited duration 544 in which it is considered valid. This duration is determined from 545 the VALIDITY_TIME TLV in the HELLO message in which the information 546 is received, which in turn is set by the router that originated the 547 HELLO message, using its corresponding interface parameter 548 H_HOLD_TIME. 550 Appendix E illustrates the relationship between message reception, 551 included VALIDITY_TIME TLVs, and the duration for which information 552 received in a HELLO message is considered valid. Appendix F 553 illustrates some example topologies and how they correspond to 554 information in the Information Bases. 556 4.2.1. Local Information Base 558 Each router maintains a Local Information Base, which contains the 559 router's local configuration information, specifically: 561 o The Local Interface Set, which consists of Local Interface Tuples, 562 each of which represents an interface (MANET or non-MANET) of the 563 router. 565 o The Removed Interface Address Set, which consists of Removed 566 Interface Address Tuples, each of which records a recently used 567 network address of an interface (MANET or non-MANET) of the 568 router. 570 The Local Interface Set is used for generating HELLO messages, 571 specifically for determining which interface network addresses are to 572 be included and identified as local interfaces. The Removed 573 Interface Address Set is used to avoid incorrectly recording a 574 formerly used network address as a symmetric 2-hop neighbor's network 575 address. 577 The Local Information Base is used for generating signaling, but is 578 not itself updated by signaling specified in this document. Updates 579 to the Local Information Base are due to changes of the router 580 configuration, and may be allowed to trigger signaling. 582 4.2.2. Interface Information Bases 584 Each router maintains, for each of its MANET interfaces, an Interface 585 Information Base, which contains 1-hop neighborhood and symmetric 586 2-hop neighborhood information collected from this MANET interface, 587 specifically: 589 o A Link Set, which records information about current and recently 590 lost links between this MANET interface and MANET interfaces of 591 1-hop neighbors. The Link Set consists of Link Tuples, each of 592 which contains information about a single link. Link quality 593 information (see Section 14), when used, is recorded in Link 594 Tuples. 596 o A 2-Hop Set, which records the existence of symmetric links 597 between symmetric 1-hop neighbors of this MANET interface and 598 other routers (symmetric 2-hop neighbors). The 2-Hop Set consists 599 of 2-Hop Tuples, each of which records a network address of a 600 symmetric 2-hop neighbor, and all network addresses of the 601 corresponding symmetric 1-hop neighbor. 603 The Link Set for a MANET interface is used for generating HELLO 604 messages. Specifically, the Link Set information is included to both 605 allow other routers to identify symmetric links and to populate the 606 2-Hop Set. Recently lost links are recorded in the Link Set for a 607 MANET interface so that they can be advertised in HELLO messages, 608 accelerating their removal from relevant 1-hop neighbors' Link Sets. 610 The Link Set for a MANET interface is itself updated on receiving a 611 HELLO message, including recording symmetric links as indicated 612 above. The 2-Hop Set for a MANET interface is updated as indicated 613 above, and is not itself used in generating HELLO messages. 615 4.2.3. Neighbor Information Base 617 Each router maintains a Neighbor Information Base, which contains 618 collected information about current and recently lost 1-hop 619 neighbors, specifically: 621 o The Neighbor Set consists of Neighbor Tuples, each of which 622 records all network addresses of a single 1-hop neighbor. 623 Neighbor Tuples are maintained as long as there are corresponding 624 Link Tuples. 626 o The Lost Neighbor Set consists of Lost Neighbor Tuples, each of 627 which records a network address of a recently lost symmetric 1-hop 628 neighbor. 630 The Neighbor Set associates all network addresses of each 1-hop 631 neighbor. These network addresses may be included when generating a 632 HELLO message, so that other symmetric 1-hop neighbors can record 633 this information in a 2-Hop Set. The Neighbor Set can be updated on 634 receiving a HELLO message. 636 The Lost Neighbor Set is used to determine which network addresses 637 are to be included in a HELLO message as being lost (of a recently 638 symmetric 1-hop neighbor). The Lost Neighbor Set can itself be 639 updated on receiving a HELLO message. 641 4.3. Signaling Overview 643 This protocol contains a signaling mechanism for maintaining the 644 Interface Information Bases and the Neighbor Information Base. If 645 information from the link layer, or any other source, is available 646 and appropriate, it may also be used to update these Information 647 Bases. Such updates are subject to the constraints specified in 648 Appendix B. 650 Signaling consists of a single type of message, known as a HELLO 651 message. Each router generates HELLO messages on each of its MANET 652 interfaces. HELLO messages are generated independently on each MANET 653 interface of a MANET router; the content of a given HELLO message 654 depends on the MANET interface for which it has been generated. 656 Each HELLO message: 658 o Identifies, as far as is required, the MANET interface for which 659 it is generated and transmitted; this allows recipients of that 660 HELLO message to identify that MANET interface from among those it 661 may hear. 663 o Reports the network addresses of other interfaces (MANET and non- 664 MANET) of the router; this allows recipients of that HELLO message 665 to associate a set of network addresses with a single 1-hop 666 neighbor. 668 o Includes 1-hop neighbor information from the Information Bases; 669 this allows detection of local symmetric links, and symmetric 670 2-hop neighbors. 672 HELLO message generation, and the validity of the information 673 recorded as a consequence of processing a HELLO message, is affected 674 by timers and validity information included in HELLO messages through 675 TLVs. The relationship between message timers and intervals is 676 illustrated in Appendix E. 678 4.3.1. HELLO Message Generation 680 HELLO messages are generated by a router for each of its MANET 681 interfaces, and MAY be sent: 683 o Proactively, at a regular interval, known as HELLO_INTERVAL. 684 HELLO_INTERVAL may be fixed, or may be dynamic. For example 685 HELLO_INTERVAL may be backed off due to congestion or network 686 stability. 688 o As a response to a change in the router itself, or its 1-hop 689 neighborhood, for example on first becoming active or in response 690 to a new, lost, or changed status link. 692 o In a combination of these proactive and responsive mechanisms. 694 Jittering of HELLO message generation and transmission SHOULD be used 695 as described in Section 11.2, unless the medium access control 696 mechanism in use prevents any simultaneous transmissions by 697 potentially interfering routers. 699 HELLO messages MAY be scheduled independently for each MANET 700 interface, or, interface parameters permitting, using the same 701 schedule for all MANET interfaces of a router. 703 4.3.2. HELLO Message Content 705 The content of a HELLO message MUST satisfy the following: 707 o A HELLO message MUST contain all of the network addresses in the 708 Local Interface Set of the router on which the HELLO message is 709 being generated. This includes: 711 o At least one network address of each MANET interface of the 712 router. 714 o Network addresses that include all source addresses of any IP 715 datagrams sent by the router on any MANET interface. 717 o All other network addresses of the router which are to be made 718 known to any other router for any reason. 720 o For each MANET interface, within every time interval equal to the 721 corresponding REFRESH_INTERVAL, sent HELLO messages MUST 722 collectively include all of the relevant information in the 723 corresponding Link Set and the Neighbor Information Base. Note 724 that when determining whether to include information in a HELLO 725 message, the sender MUST consider all times up to the latest time 726 when it may send its next HELLO message on this MANET interface. 728 o For each MANET interface, within every time interval equal to the 729 corresponding REFRESH_INTERVAL, sent HELLO messages MUST 730 collectively include all of the relevant information in the 731 corresponding Link Set and the Neighbor Information Base. 733 o When determining whether to include a given piece of neighbor 734 information in a HELLO message, it is not sufficient to consider 735 whether that information has been sent in the interval of length 736 REFRESH_INTERVAL up to the current time. Instead, the router MUST 737 consider the interval of length REFRESH_INTERVAL that will end at 738 the latest possible time at which the next HELLO message will be 739 sent on this MANET interface. (Normally, this will be 740 HELLO_INTERVAL past the current time, but MAY be earlier if this 741 router elects to divide its neighbor information among more than 742 one HELLO message in order to reduce the size of its HELLO 743 messages.) All neighbor information MUST be sent in this 744 interval, i.e., the router MUST ensure that this HELLO message 745 includes all neighbor information that has not already been 746 included in any HELLO messages sent since the start of this 747 interval (normally the current time - (REFRESH_INTERVAL - 748 HELLO_INTERVAL)). 750 o A HELLO message MUST include exactly one VALIDITY_TIME Message 751 TLV, as specified in [RFC5497], that indicates the length of time 752 for which the message content is to be considered valid, and is 753 therefore to be included in the receiving router's Interface 754 Information Base. 756 o A periodically generated HELLO message SHOULD include exactly one 757 INTERVAL_TIME Message TLV, as specified in [RFC5497], that 758 indicates the current value of HELLO_INTERVAL for that MANET 759 interface, i.e., the period within which a further HELLO message 760 is guaranteed to be sent on that MANET interface. 762 4.3.3. HELLO Message Processing 764 HELLO messages received by a router are used to update the Interface 765 Information Base for the MANET interface over which that HELLO 766 message was received, as well as the Neighbor Information Base of the 767 router. Specifically: 769 o The router ensures that there is a single Neighbor Tuple 770 corresponding to the originator of that HELLO message. 772 o The router ensures that there is a Link Tuple, with appropriate 773 status (heard or symmetric) and advertised duration, corresponding 774 to the link between the MANET interfaces on which that HELLO 775 message was sent and received. One or more Lost Neighbor Tuples 776 may be created if the HELLO message reports that the link was 777 lost. 779 o If the link between the MANET interfaces on which the HELLO 780 message was sent and received is symmetric, then the router 781 ensures that there are the appropriate 2-Hop Tuples, with 782 advertised duration. 784 The processing defined in this specification handles any unexpected 785 and erroneous information in a HELLO message, maintaining the 786 constraints on Information Base contents specified in Appendix B. 788 4.4. Link Quality 790 Some links in a MANET may be marginal, e.g., due to adverse wireless 791 propagation. In order to avoid using such marginal links, a link 792 quality value is recorded in each Link Tuple. A MANET router 793 considers links for which an insufficient link quality is recorded as 794 lost. Modifying the recorded link quality in a Link Tuple is 795 OPTIONAL. If link quality is not to be modified it MUST be set to 796 indicate an always usable quality link. 798 Note that Link Quality is a "link admittance" mechanism, allowing a 799 router to determine that a given link is too unstable to even 800 consider for use. It is specifically not a link metric nor a 801 substitute for one. 803 Link quality information is only used locally and is not used in 804 signaling. Routers may interoperate whether they are using the same, 805 different, or no, link quality information. Link quality information 806 is thus not equivalent to a link metric. 808 Link quality information is defined in this specification as a 809 normalized, dimensionless, value in the interval zero to one, 810 inclusive, where the greater the value, the better the link quality. 811 See Section 14 for further details. 813 5. Protocol Parameters and Constants 815 The parameters and constants used in this specification are described 816 in this section. 818 5.1. Protocol and Port Numbers 820 This protocol specifies HELLO messages, which are included in packets 821 as defined by [RFC5444]. These packets may be sent either using the 822 "manet" protocol number or the "manet" well-known UDP port number, as 823 specified in [RFC5498]. 825 5.2. Multicast Address 827 This protocol specifies HELLO messages, which are included in packets 828 as defined by [RFC5444]. These packets may be locally transmitted 829 using the link local multicast address "LL-MANET-Routers", as 830 specified in [RFC5498]. 832 5.3. Interface Parameters 834 The interface parameters used by this specification may be classified 835 into the following four categories: 837 o Message intervals 839 o Information validity times 841 o Link quality 842 o Jitter 844 These are detailed in the following sections. 846 Different MANET interfaces (on the same or on different routers) MAY 847 employ different interface parameter values, and MAY change their 848 interface parameter values dynamically, subject to the constraints 849 given in this section. A particular case is where all MANET 850 interfaces on all MANET routers within a given MANET employ the same 851 set of interface parameter values. 853 5.3.1. Message Intervals 855 HELLO messages serve two principal functions: 857 o To advertise network addresses of this router's interface to its 858 1-hop neighbors. The frequency of these advertisements is 859 regulated by the interface parameters HELLO_INTERVAL and 860 HELLO_MIN_INTERVAL. 862 o To advertise this router's knowledge of each of its 1-hop 863 neighbors. The frequency of the advertisement of each such 864 neighbor is regulated by the interface parameter REFRESH_INTERVAL. 866 Specifically, these parameters are as follows: 868 HELLO_INTERVAL - is the maximum time between the transmission of two 869 successive HELLO messages on this MANET interface. If using 870 periodic transmission of HELLO messages, these SHOULD be at a 871 separation of HELLO_INTERVAL, possibly modified by jitter as 872 specified in [RFC5148]. 874 HELLO_MIN_INTERVAL - is the minimum interval between transmission of 875 two successive HELLO messages, on this MANET interface. (This 876 minimum interval MAY be modified by jitter, as defined in 877 [RFC5148].) 879 REFRESH_INTERVAL - is the maximum interval between advertisements, 880 in a HELLO message on this MANET interface, of each 1-hop neighbor 881 network address and its status. In all intervals of length 882 REFRESH_INTERVAL, a router MUST include each 1-hop neighbor 883 network address and its status in at least one HELLO message on 884 this MANET interface. (This may be in the same or in different 885 HELLO messages.) 887 REFRESH_INTERVAL thus represents the frequency at which a piece of 888 information, as received in HELLO messages, can be expected to be 889 refreshed. Thus, the REFRESH_INTERVAL is used as a basis for 890 determining when such information expires in receiving routers (see 891 Section 5.3.2). HELLO_INTERVAL represents the frequency of HELLO 892 message emissions. Logically, HELLO_INTERVAL cannot be greater than 893 the REFRESH_INTERVAL, otherwise information cannot be refreshed in a 894 timely manner. 896 HELLO messages can, however, be sent with a higher frequency. A 897 possible use for sending HELLO messages at such a higher frequency 898 includes sending partial HELLO messages (e.g., accommodating 899 constraints on packet sizes from the underlying medium) refreshing 900 only part of the information in each HELLO message. Another use is 901 for a router to send "empty HELLO messages", advertising its own 902 presence frequently in smaller HELLO messages (e.g., in case HELLO 903 message exchange success rates are used for link quality estimation, 904 or to enable rapid detection by new routers in the neighborhood) in 905 between HELLO messages refreshing neighbor information in other 906 routers. 908 The following constraints apply to these interface parameters: 910 o HELLO_INTERVAL > 0 912 o HELLO_MIN_INTERVAL >= 0 914 o HELLO_INTERVAL >= HELLO_MIN_INTERVAL 916 o REFRESH_INTERVAL >= HELLO_INTERVAL 918 o If an INTERVAL_TIME Message TLV as defined in [RFC5497] is 919 included in a HELLO messages, then HELLO_INTERVAL MUST be 920 representable as described in [RFC5497]. 922 If REFRESH_INTERVAL > HELLO_INTERVAL, then a router may distribute 923 its neighbor advertisements between HELLO messages in any manner, 924 subject to the constraints above. 926 In the absence of any changes to the local neighborhood, a router 927 will send a HELLO message on a MANET interface after a (possibly 928 jittered) interval of length HELLO_INTERVAL. For a router to employ 929 this protocol in a purely responsive manner on a MANET interface, 930 i.e., for the router to only send HELLO messages on that MANET 931 interface as a response to external events, HELLO_INTERVAL (and hence 932 also REFRESH_INTERVAL) SHOULD be set sufficiently large, i.e., such 933 that a responsive HELLO message is always expected with a shorter 934 period than this value. 936 If a router has more than one MANET interface, then, even if the 937 router configures different values of HELLO_INTERVAL on each MANET 938 interface, the router SHOULD configure the same value of 939 HELLO_MIN_INTERVAL on all MANET interfaces on which responsive HELLO 940 messages may be sent. (This ensures that changes observed on one 941 MANET interface are reported on other MANET interfaces, so that 1-hop 942 neighbors connected to the latter can maintain up to date 2-hop 943 neighborhood information.) 945 5.3.2. Information Validity Times 947 The following interface parameters manage the validity time of link 948 information: 950 L_HOLD_TIME - is the period of advertisement, on this MANET 951 interface, of former 1-hop neighbor network addresses as lost in 952 HELLO messages, allowing recipients of these HELLO messages to 953 accelerate removal of this information from their Link Sets. 954 L_HOLD_TIME MAY be set to zero, if accelerated information removal 955 is not required. 957 H_HOLD_TIME - is used as the Value in the VALIDITY_TIME Message TLV 958 included in all HELLO messages on this MANET interface. It is 959 then used by each router receiving such a HELLO message to 960 indicate the validity of the information taken from that HELLO 961 message and recorded in the receiving router's Information Bases. 963 Note that as each item of neighbor information is included in HELLO 964 messages within an interval of length REFRESH_INTERVAL, constraints 965 on H_HOLD_TIME are based on REFRESH_INTERVAL, not on HELLO_INTERVAL. 967 The following constraints apply to these interface parameters: 969 o L_HOLD_TIME >= 0 971 o H_HOLD_TIME >= REFRESH_INTERVAL 973 o If HELLO messages can be lost then both parameters SHOULD be 974 significantly greater than REFRESH_INTERVAL. 976 o H_HOLD_TIME MUST be representable as described in [RFC5497]. 978 5.3.3. Link Quality 980 The following interface parameters manage the usage of link quality 981 (see Section 14): 983 HYST_ACCEPT - is the link quality threshold at or above which a link 984 becomes usable, if it was not already so. 986 HYST_REJECT - is the link quality threshold below which a link 987 becomes unusable, if it was not already so. 989 INITIAL_QUALITY - is the initial quality of a newly identified link. 991 INITIAL_PENDING - if true, then a newly identified link is 992 considered pending, and is not usable until the link quality has 993 reached or exceeded the HYST_ACCEPT threshold. 995 The following constraints apply to these interface parameters: 997 o 0 <= HYST_REJECT <= HYST_ACCEPT <= 1 999 o 0 <= INITIAL_QUALITY <= 1. 1001 o If link quality is not updated, then INITIAL_QUALITY >= 1002 HYST_ACCEPT. 1004 o If INITIAL_QUALITY >= HYST_ACCEPT, then INITIAL_PENDING := false. 1006 o If INITIAL_QUALITY < HYST_REJECT, then INITIAL_PENDING := true. 1008 5.3.4. Jitter 1010 If jitter, as defined in [RFC5148], is used then these parameters are 1011 as follows: 1013 HP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 1014 for periodically generated HELLO messages on this MANET interface. 1016 HT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 1017 for externally triggered HELLO messages on this MANET interface. 1019 For constraints on these interface parameters see [RFC5148]. 1021 5.4. Router Parameters 1023 The two router parameters defined by this specification are in the 1024 category of information validity time. 1026 5.4.1. Information Validity Time 1028 The following router parameter manages the validity time of lost 1029 symmetric 1-hop neighbor information: 1031 N_HOLD_TIME - is used as the period during which former 1-hop 1032 neighbor network addresses are advertised as lost in HELLO 1033 messages, allowing recipients of these HELLO messages to 1034 accelerate removal of this information from their 2-Hop Sets. 1035 N_HOLD_TIME MAY be set to zero, if accelerated information removal 1036 is not required. 1038 I_HOLD_TIME - is the period for which a recently used local 1039 interface network address is recorded. 1041 The following constraints applies to these router parameters: 1043 o N_HOLD_TIME >= 0 1045 o I_HOLD_TIME >= 0 1047 5.5. Parameter Change Constraints 1049 If protocol parameters are changed dynamically, the constraints in 1050 this section apply. 1052 HELLO_INTERVAL 1054 o If the HELLO_INTERVAL for a MANET interface increases, then the 1055 next HELLO message on this MANET interface MUST be generated 1056 according to the previous, shorter, HELLO_INTERVAL. A number 1057 of subsequent HELLO messages MAY be generated according to the 1058 previous, shorter, HELLO_INTERVAL (but MUST include times 1059 according to current parameters). This ensures that "promises" 1060 as to timely transmission of a future HELLO message is kept 1061 until these previous promises have expired. 1063 o If the HELLO_INTERVAL for a MANET interface decreases, then the 1064 following HELLO messages on this MANET interface MUST be 1065 generated according to this current, shorter, HELLO_INTERVAL. 1067 REFRESH_INTERVAL 1069 o If the REFRESH_INTERVAL for a MANET interface increases, then 1070 the content of subsequent HELLO messages must be organized such 1071 that the specification of the old value of REFRESH_INTERVAL is 1072 satisfied for a further period equal to the old value of 1073 REFRESH_INTERVAL. 1075 o If the REFRESH_INTERVAL for a MANET interface decreases, then 1076 it MAY be necessary to reschedule HELLO message generation on 1077 that MANET interface, in order that the specification of 1078 REFRESH_INTERVAL is satisfied from the time of change. 1080 HYST_ACCEPT and HYST_REJECT 1082 o If HYST_ACCEPT or HYST_REJECT changes, then the appropriate 1083 actions for link quality change, as specified in Section 14.3, 1084 MUST be taken. 1086 L_HOLD_TIME 1088 o If L_HOLD_TIME changes, then the expiry times of all relevant 1089 Link Tuples MUST be changed. 1091 N_HOLD_TIME 1093 o If N_HOLD_TIME changes, then the expiry times of all relevant 1094 Lost Neighbor Tuples MUST be changed. 1096 HP_MAXJITTER 1098 o If HP_MAXJITTER changes, then the periodic HELLO message 1099 schedule on this MANET interface MAY be changed. 1101 HT_MAXJITTER 1103 o If HT_MAXJITTER changes, then externally triggered HELLO 1104 messages on this MANET interface MAY be rescheduled. 1106 5.6. Constants 1108 The constant C (time granularity) is used as specified in [RFC5497]. 1110 6. Local Information Base 1112 A router maintains a Local Information Base that records information 1113 about its interfaces (MANET and non-MANET). Each interface of a 1114 router MUST be identified by at least one network address. Such 1115 network addresses MAY be specific to that interface, or MAY in some 1116 circumstances be used by more than one interface as specified below. 1118 The Local Information Base is not modified by signaling. If a 1119 router's interface configuration changes, then the Local Information 1120 Base MUST reflect these changes. This MAY also result in signaling 1121 to advertise these changes. 1123 It is not necessary to include all addresses of an interface in the 1124 Local Information Base, and hence in HELLO messages. However any 1125 address that may be the source address of an IP datagram sent from 1126 that interface MUST be included (and at least one address MUST be 1127 included). A protocol using this specification MAY add additional 1128 requirements to these, e.g., that any address that may be the 1129 destination address of an IP datagram is also included. 1131 The addresses assigned to an interface are "owned" by the router, and 1132 MUST NOT be used by any other router as an interface address. If an 1133 address has a prefix length and represents a range of addresses, this 1134 applies to all addresses in that range (i.e., such ranges MUST NOT 1135 overlap). 1137 The addresses assigned to different interfaces on the same router 1138 MUST be distinct (hence network address ranges MUST NOT overlap) 1139 except that: 1141 o The same address MAY be assigned to any number of non-MANET 1142 interfaces as well as to one (or more if the following condition 1143 also applies) MANET interface. 1145 o The same address MAY be assigned to two (or more if each pair 1146 satisfies this condition) MANET interfaces if those two MANET 1147 interfaces cannot communicate to, from, or one to and one from, 1148 any other MANET interface of another router. 1150 6.1. Local Interface Set 1152 A router's Local Interface Set records its local interfaces. It 1153 consists of Local Interface Tuples, one per interface: 1155 (I_local_iface_addr_list, I_manet) 1157 where: 1159 I_local_iface_addr_list - is an unordered list of the network 1160 addresses of this interface. 1162 I_manet - is a boolean flag, describing if this interface is a MANET 1163 interface. 1165 Local Interface Tuples are removed from the Local Interface Set only 1166 when the routers' interface configuration changes, subject to 1167 Section 9, i.e., they are not subject to timer-based expiration. 1169 6.2. Removed Interface Address Set 1171 A router's Removed Interface Address Set records network addresses 1172 which were recently used as local interface network addresses. If a 1173 router's interface network addresses are immutable then the Removed 1174 Interface Address Set is always empty and MAY be omitted. It 1175 consists of Removed Interface Address Tuples, one per network 1176 address: 1178 (IR_local_iface_addr, IR_time) 1180 where: 1182 IR_local_iface_addr - is a recently used network address of an 1183 interface of this router. 1185 IR_time - specifies when this Tuple expires and MUST be removed. 1187 7. Interface Information Bases 1189 A router maintains an Interface Information Base for each of its 1190 MANET interfaces. This records information about links to that MANET 1191 interface and symmetric 2-hop neighbors which can be reached in two 1192 hops using those links as the first hop. Each Interface Information 1193 Base includes a Link Set and a 2-Hop Set. 1195 A network address of a symmetric 2-hop neighbor can also be present 1196 as the network address of a 1-hop neighbor. This allows the router 1197 using this network address to be immediately considered as a 1198 symmetric 2-hop neighbor if it fails to be a symmetric 1-hop 1199 neighbor. 1201 An element which specifies a time is considered expired if the 1202 current time is greater than or equal to that time. One such 1203 element, present in most Tuples, indicates when expired that the 1204 Tuple itself is considered expired and MUST be removed. Tuples which 1205 do not have such a time element are removed at other times as 1206 specified, for example a Neighbor Tuple is removed when all 1207 corresponding Link Tuples have been removed. 1209 7.1. Link Set 1211 An interface's Link Set records links from other routers which are, 1212 or recently were, 1-hop neighbors. It consists of Link Tuples, each 1213 representing a single link: 1215 (L_neighbor_iface_addr_list, L_HEARD_time, L_SYM_time, 1216 L_quality, L_pending, L_lost, L_time) 1218 where: 1220 L_neighbor_iface_addr_list - is an unordered list of the network 1221 addresses of the MANET interface of the 1-hop neighbor; 1223 L_HEARD_time - is the time up to which the MANET interface of the 1224 1-hop neighbor would be considered heard if not considering link 1225 quality; 1227 L_SYM_time - is the time up to which the link to the 1-hop neighbor 1228 would be considered symmetric if not considering link quality; 1230 L_quality - is a dimensionless number between 0 (inclusive) and 1 1231 (inclusive) describing the quality of a link; a greater value of 1232 L_quality indicating a higher quality link; 1234 L_pending - is a boolean flag, describing if a link is considered 1235 pending (i.e., a candidate, but not yet established, link); 1237 L_lost - is a boolean flag, describing if a link is considered lost 1238 due to low link quality; 1240 L_time - specifies when this Tuple expires and MUST be removed. 1242 The status of the link, as obtained through HELLO message exchange 1243 and using link quality, is denoted L_status. L_status can take the 1244 Values PENDING, HEARD, SYMMETRIC and LOST. The values LOST, 1245 SYMMETRIC and HEARD are defined in Section 18.5. The Value PENDING 1246 is never used in a HELLO message, it is only used locally by a 1247 router, and any Value distinct from LOST, SYMMETRIC and HEARD may be 1248 used. 1250 L_status is defined by: 1252 1. If L_pending = true, then L_status := PENDING; 1254 2. otherwise, if L_lost = true, then L_status := LOST; 1256 3. otherwise, if L_SYM_time is not expired, then L_status := 1257 SYMMETRIC; 1259 4. otherwise, if L_HEARD_time is not expired, then L_status := 1260 HEARD; 1262 5. otherwise, L_status := LOST. 1264 7.2. 2-Hop Set 1266 An interface's 2-Hop Set records network addresses of symmetric 2-hop 1267 neighbors, and the symmetric links to symmetric 1-hop neighbors 1268 through which these symmetric 2-hop neighbors can be reached. It 1269 consists of 2-Hop Tuples, each representing a single network address 1270 of a symmetric 2-hop neighbor, and a single MANET interface of a 1271 symmetric 1-hop neighbor. 1273 (N2_neighbor_iface_addr_list, N2_2hop_addr, N2_time) 1275 where: 1277 N2_neighbor_iface_addr_list - is an unordered list of the network 1278 addresses of the MANET interface of the symmetric 1-hop neighbor 1279 from which this information was received; 1281 N2_2hop_addr - is a network address of a symmetric 2-hop neighbor 1282 which has a symmetric link (using any MANET interface) to the 1283 indicated symmetric 1-hop neighbor; 1285 N2_time - specifies when this Tuple expires and MUST be removed. 1287 8. Neighbor Information Base 1289 Each router maintains a Neighbor Information Base that records 1290 information about network addresses of current and recently symmetric 1291 1-hop neighbors. 1293 8.1. Neighbor Set 1295 A router's Neighbor Set records all network addresses of each 1-hop 1296 neighbor. It consists of Neighbor Tuples, each representing a single 1297 1-hop neighbor: 1299 (N_neighbor_addr_list, N_symmetric) 1301 where: 1303 N_neighbor_addr_list - is an unordered list of the network addresses 1304 of a 1-hop neighbor; 1306 N_symmetric - is a boolean flag, describing if this is a symmetric 1307 1-hop neighbor. 1309 Neighbor Tuples are removed from the Neighbor Set only when 1310 corresponding Link Tuples expire from the routers' Link Set, i.e., 1311 Neighbor Tuples are not directly subject to timer-based expiration. 1313 8.2. Lost Neighbor Set 1315 A router's Lost Neighbor Set records network addresses of routers 1316 which recently were symmetric 1-hop neighbors, but which are now 1317 advertised as lost. It consists of Lost Neighbor Tuples, each 1318 representing a single such network address: 1320 (NL_neighbor_addr, NL_time) 1322 where: 1324 NL_neighbor_addr - is a network address of a router which recently 1325 was a symmetric 1-hop neighbor of this router; 1327 NL_time - specifies when this Tuple expires and MUST be removed. 1329 9. Local Information Base Changes 1331 The Local Information Base MUST be updated in response to changes in 1332 the router's local interface configuration. These MAY also change 1333 the Interface Information Base and the Neighbor Information Base. If 1334 any changes to the latter Information Bases satisfy any of the 1335 conditions described in Section 13, then those changes MUST be 1336 applied immediately, unless noted otherwise below. 1338 A router MAY transmit HELLO messages in response to these changes. 1340 9.1. Adding an Interface 1342 If an interface is added to the router, then this is indicated by the 1343 addition of a Local Interface Tuple to the Local Interface Set. If 1344 the new interface is a MANET interface, then an initially empty 1345 Interface Information Base MUST be created for this new MANET 1346 interface. The actions in Section 9.3 MUST be taken for each network 1347 address of this added interface. A HELLO message MAY be sent on all 1348 MANET interfaces, it SHOULD be sent on the new interface if it is a 1349 MANET interface. If using scheduled messages, then a message 1350 schedule MUST be established on the new MANET interface. 1352 9.2. Removing an Interface 1354 If an interface is removed from the router, then this MUST result in 1355 changes to the Local Information Base and to the Neighbor Information 1356 Base as follows: 1358 1. Identify the Local Interface Tuple that corresponds to the 1359 interface to be removed. 1361 2. For each network address (henceforth removed address) in the 1362 I_local_iface_addr_list of that Local Interface Tuple, if that 1363 network address is not in the I_local_iface_addr_list of any 1364 other Local Interface Tuple, then create a Removed Interface 1365 Address Tuple with: 1367 o IR_local_iface_addr := removed address; 1369 o IR_time := current time + I_HOLD_TIME. 1371 3. Remove that Local Interface Tuple from the Local Interface Set. 1373 4. If the interface to be removed is a MANET interface (i.e., with 1374 I_manet = true) then: 1376 1. Remove the Interface Information Base for that MANET 1377 interface; 1379 2. All Neighbor Tuples for which none of the network addresses 1380 in its N_neighbor_addr_list are contained in any 1381 L_neighbor_iface_addr_list in any remaining Link Tuple, are 1382 removed. 1384 If the removed interface is the last MANET interface of the router, 1385 then there will be no remaining Interface Information Bases, and the 1386 router will no longer participate in this protocol. 1388 After removing the interface and making these changes, a HELLO 1389 message MAY be sent on all remaining MANET interfaces. 1391 9.3. Adding a Network Address to an Interface 1393 If a network address is added to an interface then this is indicated 1394 by the addition of a network address to the appropriate 1395 I_local_iface_addr_list. The following changes MUST be made to the 1396 Information Bases: 1398 1. Remove any Removed Interface Address Tuple whose 1399 IR_local_iface_addr is the added network address. 1401 2. Remove any Neighbor Tuples whose N_neighbor_addr_list contains a 1402 network address that overlaps the added network address. 1404 3. Remove any Link Tuples, in any Link Set, for which either: 1406 o L_neighbor_iface_addr_list contains any network address in the 1407 N_neighbor_addr_list of any removed Neighbor Tuple; OR 1409 o L_neighbor_iface_addr_list contains a network address that 1410 overlaps the added network address. 1412 Apply Section 13.2, but not Section 13.3. 1414 4. Remove any Lost Neighbor Tuples whose NL_neighbor_addr overlaps 1415 the added network address. 1417 5. Remove any 2-Hop Tuples whose N2_2hop_addr overlaps the added 1418 network address. 1420 After adding the network address and making these changes, a HELLO 1421 message MAY be sent on all MANET interfaces. 1423 These changes, other than to the appropriate I_local_iface_addr_list, 1424 are made in order to maintain consistency of the Information Bases. 1425 Specifically, these changes remove any record of any use of this 1426 network address by routers in the 1-hop neighborhood or in the 1427 symmetric 2-hop neighborhood of this router. 1429 9.4. Removing a Network Address from an Interface 1431 If a network address (henceforth removed address) is removed from an 1432 interface then: 1434 1. Identify the Local Interface Tuple that corresponds to the 1435 removed address. 1437 2. If this is the only network address of that interface (the only 1438 network address in the corresponding I_local_iface_addr_list) 1439 then remove that interface as specified in Section 9.2. 1441 3. Otherwise: 1443 1. Remove the removed address from this I_local_iface_addr_list. 1445 2. If the removed address is not in the I_local_iface_addr_list 1446 of any other Local Interface Tuple, then create a Removed 1447 Interface Address Tuple with: 1449 o IR_local_iface_addr := removed address; 1451 o IR_time := current time + I_HOLD_TIME. 1453 After removing the network address and making these changes, a HELLO 1454 message MAY be sent on all MANET interfaces. 1456 10. Packets and Messages 1458 The packet and message format used by this protocol is defined in 1459 [RFC5444], which is used with the following considerations: 1461 o This protocol specifies one Message Type, the HELLO message. 1463 o A HELLO message MAY use any combination of Message Header options 1464 specified in [RFC5444]. 1466 o HELLO messages MUST NOT be forwarded, i.e., a , if 1467 present, MUST have the value 1. 1469 o HELLO messages MAY be included in multi-message packets as 1470 specified in [RFC5444]. 1472 o Received HELLO messages MUST be parsed in accordance with 1473 [RFC5444]. A HELLO message which is not in conformance with 1474 [RFC5444] MUST be discarded without being processed. A HELLO 1475 message can also be discarded without being processed for other 1476 reasons, see Section 12.1. 1478 o This protocol specifies three Address Block TLVs. It also uses 1479 two Message TLVs defined in [RFC5497]. These five TLV Types are 1480 all defined only with Type Extension = 0. TLVs of other types, 1481 and of these types but without Type Extension = 0, are ignored by 1482 this protocol. All references in this specification to, for 1483 example, an Address Block TLV with Type = LINK_STATUS, are to be 1484 considered as referring to an Address Block TLV with Type = 1485 LINK_STATUS and Type Extension = 0. 1487 10.1. HELLO Messages 1489 A HELLO message MUST contain: 1491 o Exactly one VALIDITY_TIME Message TLV as specified in [RFC5497], 1492 representing H_HOLD_TIME 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 transmitted due to a periodic timer SHOULD contain, 1497 and otherwise (i.e., transmitted for any other reason, in particular 1498 in response to any Information Base changes) MAY contain: 1500 o Exactly one INTERVAL_TIME Message TLV as specified in [RFC5497], 1501 representing HELLO_INTERVAL for the transmitting MANET interface. 1502 The options included in [RFC5497] for representing zero and 1503 infinite times MUST NOT be used. 1505 A HELLO message MAY contain: 1507 o Other Message TLVs. 1509 o One or more Address Blocks, each with an associated Address Block 1510 TLV Block, which MAY contain other Address Block TLVs. 1512 10.1.1. Address Blocks 1514 All network addresses in a router's Local Interface Set (i.e., in any 1515 I_local_iface_addr_list) MUST be represented as address objects (see 1516 [RFC5444]), and included in the Address Blocks in all generated HELLO 1517 messages, with the following permitted exception: 1519 o If the MANET interface on which the HELLO message is to be sent 1520 has a single address with maximum prefix length (i.e., /32 for 1521 IPv4, /128 for IPv6), then that address MAY be omitted from being 1522 included in any Address Block, provided that this address is 1523 included as the sending address of the IP datagram in which the 1524 HELLO message is included. 1526 All network addresses of the router's interfaces included in any 1527 Address Block(s) MUST be associated with an Address Block TLV with 1528 Type = LOCAL_IF, as defined in Table 1. 1530 +----------+---------+----------------------------------------------+ 1531 | Name | Value | Description | 1532 | | Length | | 1533 +----------+---------+----------------------------------------------+ 1534 | LOCAL_IF | 1 octet | Specifies that the network address is | 1535 | | | associated with the MANET interface on which | 1536 | | | the message was sent (THIS_IF) or another | 1537 | | | interface of the sending router (OTHER_IF). | 1538 +----------+---------+----------------------------------------------+ 1540 Table 1: LOCAL_IF TLV definition 1542 Address Blocks MAY contain current or recently lost 1-hop neighbors' 1543 network addresses, represented as address objects (see [RFC5444]), 1544 each of which is associated with one or both Address Block TLVs as 1545 described in Table 2. 1547 +--------------+---------+------------------------------------------+ 1548 | Name | Value | Description | 1549 | | Length | | 1550 +--------------+---------+------------------------------------------+ 1551 | LINK_STATUS | 1 octet | Specifies the status of the link from | 1552 | | | the indicated network address and to the | 1553 | | | MANET interface over which the HELLO | 1554 | | | message is transmitted (LOST, SYMMETRIC | 1555 | | | or HEARD). | 1556 | OTHER_NEIGHB | 1 octet | Specifies that the network address is | 1557 | | | (SYMMETRIC) or was (LOST) of a MANET | 1558 | | | interface of a symmetric 1-hop neighbor | 1559 | | | of the router transmitting the HELLO | 1560 | | | message. | 1561 +--------------+---------+------------------------------------------+ 1563 Table 2: LINK_STATUS and OTHER_NEIGHB TLV definition 1565 An Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC or 1566 Value = LOST also performs the function of an Address Block TLV with 1567 Type = OTHER_NEIGHB and the same Value. Including the latter 1568 associated with the same address object is discouraged for efficiency 1569 reasons. If an Address Block TLV with Type = LINK_STATUS and Value = 1570 SYMMETRIC is combined with an Address Block TLV with Type = 1571 OTHER_NEIGHB and Value = LOST associated with the same address 1572 object, then the latter MUST be ignored, and SHOULD NOT be included. 1573 See Appendix A. 1575 Other network addresses MAY be represented as address objects (see 1576 [RFC5444]) and included in Address Blocks, but MUST NOT be associated 1577 with any of the Address Block TLVs specified in this specification. 1579 11. HELLO Message Generation 1581 Each MANET interface MUST generate HELLO messages according to the 1582 specification in this section. HELLO messages are generated for each 1583 MANET interface independently. HELLO message generation and 1584 scheduling MUST be according to the interface parameters for that 1585 MANET interface, and MAY be independent for each MANET interface or, 1586 interface parameters permitting, MANET interfaces MAY use the same 1587 schedule. 1589 If transmitting periodic HELLO messages then, following a HELLO 1590 message transmission on a MANET interface, another HELLO message MUST 1591 be transmitted on the same MANET interface after an interval not 1592 greater than HELLO_INTERVAL. Two successive HELLO message 1593 transmissions on the same MANET interface MUST be separated by at 1594 least HELLO_MIN_INTERVAL, except as noted in Section 11.2.1. 1596 11.1. HELLO Message Specification 1598 HELLO messages are generated independently on each MANET interface. 1600 All network addresses in any I_local_iface_addr_list MUST be 1601 included, represented as address objects (see [RFC5444]), except 1602 that: 1604 o If the interface on which the HELLO message is to be sent has a 1605 single address with maximum prefix length (i.e., /32 for IPv4, 1606 /128 for IPv6) then that address MAY be omitted, provided that 1607 this address is included as the sending address of the IP datagram 1608 in which the HELLO message is included. 1610 All such included address objects MUST be associated with an Address 1611 Block TLV with Type := LOCAL_IF and Value according to the following: 1613 o If the address object represents a network address of the sending 1614 MANET interface, then Value := THIS_IF. 1616 o Otherwise, Value := OTHER_IF. 1618 If such a network address is included in more than one 1619 I_local_iface_addr_list, then, for efficiency reasons, it is 1620 encouraged that the corresponding address object is associated with 1621 only one Value using an Address Block TLV with Type := LOCAL_IF, this 1622 MUST be Value := THIS_IF if the address object represents a network 1623 address of the sending MANET interface. 1625 The following network addresses of current or former 1-hop neighbors 1626 MAY be represented as address objects (see [RFC5444]) and included in 1627 any HELLO message, respecting the parameter REFRESH_INTERVAL for each 1628 association for that MANET interface, and according to the following: 1630 o Network addresses of MANET interfaces of 1-hop neighbors from the 1631 Link Set of the Interface Information Base for this MANET 1632 interface (i.e., from an L_neighbor_iface_addr_list), other than 1633 those from Link Tuples with L_status = PENDING. 1635 o Other network addresses of symmetric 1-hop neighbors from the 1636 Neighbor Set of this router's Neighbor Information Base (i.e., 1637 from an N_neighbor_addr_list). 1639 o Network addresses of MANET interfaces of previously symmetric or 1640 heard 1-hop neighbors connected on this MANET interface from the 1641 Link Set of the Interface Information Base for this MANET 1642 interface (i.e., from an L_neighbor_iface_addr_list with L_status 1643 = LOST). 1645 o Other network addresses of previously symmetric 1-hop neighbors 1646 from the Lost Neighbor Set of this router's Neighbor Information 1647 Base (i.e., from an NL_neighbor_addr). 1649 Each such address object (see [RFC5444]) MUST be associated with one 1650 or more appropriate Address Block TLVs. Specifically: 1652 1. For each address object (henceforth linked address) which 1653 represents a network address contained in an 1654 L_neighbor_iface_addr_list of a Link Tuple in the Link Set for 1655 this MANET interface, for which L_status != PENDING, include the 1656 linked address with an associated Address Block TLV with: 1658 o Type := LINK_STATUS; AND 1660 o Value := L_status. 1662 2. For each address object (henceforth neighbor address) which 1663 represents a network address contained in an N_neighbor_addr_list 1664 in a Neighbor Tuple with N_symmetric = true, and which has not 1665 already been included with an associated Address Block TLV with 1666 Type = LINK_STATUS and Value = SYMMETRIC, include the neighbor 1667 network address with an associated Address Block TLV with: 1669 o Type := OTHER_NEIGHB; AND 1671 o Value := SYMMETRIC. 1673 3. For each Lost Neighbor Tuple whose NL_neighbor_addr (henceforth 1674 lost address) has not already been represented as an address 1675 object and included, include lost address with an associated 1676 Address Block TLV with: 1678 o Type := OTHER_NEIGHB; AND 1680 o Value := LOST. 1682 If any such network addresses have been added to these Information 1683 Bases since the last HELLO message was sent on this MANET interface, 1684 or if their status (as indicated by these TLVs and the Values they 1685 associate with that network address) have changed since that network 1686 address was last reported on this MANET interface, then that network 1687 address, and the indicated TLVs, SHOULD be included in the HELLO 1688 message. 1690 If the address object (see [RFC5444]) representing a network address 1691 of a 1-hop neighbor is specified with more than one associated 1692 Address Block TLV, then these Address Block TLVs MAY be independently 1693 included or excluded from each HELLO message. Each such Address 1694 Block TLV MUST be included associated with the address object 1695 representation of that network address in a HELLO message sent on 1696 that MANET interface in every interval of length equal to that MANET 1697 interface's parameter REFRESH_INTERVAL. Address Block TLVs 1698 associated with the same address object included in the same HELLO 1699 message MAY be applied to the same or different copies of that 1700 address object. 1702 An implementation of this protocol MAY limit the information included 1703 in each HELLO message, for example to accommodate smaller MTU sizes. 1704 HELLO messages remain constrained by the above requirements, in 1705 particular that all local interface information MUST be included in 1706 all HELLO messages, and that all neighbor information MUST be sent 1707 within each interval of length REFRESH_INTERVAL. This neighbor 1708 information MAY, however, be sent in the same or in different HELLO 1709 messages. 1711 11.2. HELLO Message Transmission 1713 HELLO messages are transmitted in the format specified by [RFC5444]. 1715 11.2.1. HELLO Message Jitter 1717 HELLO messages MAY be sent using periodic message generation or 1718 externally triggered message generation. If using data link and 1719 physical layers which are subject to packet loss due to collisions, 1720 HELLO messages SHOULD be jittered as described in [RFC5148]. 1722 Internally triggered message generation (such as due to a change in 1723 local interfaces) MAY be treated as if externally generated message 1724 generation, or MAY be not jittered. 1726 HELLO messages MUST NOT be forwarded, and thus message forwarding 1727 jitter does not apply to HELLO messages. 1729 Each form of jitter described in [RFC5148] requires a parameter 1730 MAXJITTER. These interface parameters may be dynamic, and are 1731 specified by: 1733 o For periodic message generation: HP_MAXJITTER. 1735 o For externally triggered message generation: HT_MAXJITTER. 1737 When HELLO message generation is delayed in order that a HELLO 1738 message is not sent within HELLO_MIN_INTERVAL of the previous HELLO 1739 message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD 1740 be reduced by jitter, with maximum reduction HP_MAXJITTER, as 1741 described in [RFC5148]. In this case HP_MAXJITTER MUST NOT be 1742 greater than HELLO_MIN_INTERVAL. 1744 12. HELLO Message Processing 1746 On receiving a HELLO message, a router MUST first check if the 1747 message is invalid for processing by this router, as defined in 1748 Section 12.1 and, if so, discard the message without further 1749 processing. Otherwise, for each received and valid HELLO message the 1750 receiving router MUST update its appropriate Interface Information 1751 Base and its Neighbor Information Base as specified in Section 12.3 1752 to Section 12.6. These updates MUST be performed in the order in 1753 which they are presented in this specification. If any changes 1754 satisfy any of the conditions described in Section 13 then the 1755 indicated consequences in that section MUST be applied immediately, 1756 unless noted otherwise. 1758 All message processing, including determination of whether a message 1759 is invalid, considers only TLVs with Type Extension = 0. TLVs with 1760 any other type extension are ignored. All references to, for 1761 example, a TLV with Type = LINK_STATUS refer to a TLV with Type = 1762 LINK_STATUS and Type Extension = 0. 1764 12.1. Invalid Message 1766 A received HELLO message is invalid for processing by this router if 1767 any of the following conditions are true: 1769 o The address length as specified in the Message Header is not equal 1770 to the length of the addresses used by this router. 1772 o The message has a field in its Message Header with 1773 a value other than one. (Note that the message does not need to 1774 have a field.) 1776 o The message has a field in its Message Header with 1777 a value other than zero. (Note that the message does not need to 1778 have a field.) 1780 o The message does not have a Message TLV with Type = VALIDITY_TIME 1781 in its Message TLV Block. 1783 o The message has more than one Message TLV with Type = 1784 VALIDITY_TIME in its Message TLV Block. 1786 o The message has more than one Message TLV with Type = 1787 INTERVAL_TIME in its Message TLV Block. 1789 o The message has any Address Block TLV(s) with Type = LOCAL_IF and 1790 any single Value v such that v != THIS_IF and v != OTHER_IF. 1792 o Any address object (including different address objects 1793 representing the same network address, in the same or different 1794 Address Blocks) is associated with more than one Value by one or 1795 more Address Block TLV(s) with Type = LOCAL_IF. 1797 o Any address object (henceforth local address) associated with an 1798 Address Block TLV with Type = LOCAL_IF represents one of the 1799 receiving router's current or recently used network addresses 1800 (i.e., local address overlaps any network address in any 1801 I_local_iface_addr_list in the Local Interface Set or any 1802 IR_local_iface_addr in the Removed Interface Address Set). 1804 o The message has any Address Block TLV(s) with Type = LINK_STATUS 1805 with any single Value v such that v != LOST, v != SYMMETRIC, and v 1806 != HEARD. 1808 o The message has any Address Block TLV(s) with Type = OTHER_NEIGHB 1809 with any single Value v such that v != LOST and v != SYMMETRIC. 1811 o Any address object (including different copies of an address 1812 object, in the same or different Address Blocks) is associated 1813 with an Address Block TLV with Type = LOCAL_IF and with an Address 1814 Block TLV with Type = LINK_STATUS. 1816 o Any address object (including different copies of an address 1817 object, in the same or different Address Blocks) is associated 1818 with an Address Block TLV with Type = LOCAL_IF and with an Address 1819 Block TLV with Type = OTHER_NEIGHB. 1821 o Any address object (including different copies of an address 1822 object, in the same or different Address Blocks) is associated 1823 with more than one Value by one or more Address Block TLVs with 1824 Type = LINK_STATUS. 1826 o Any address object (including different copies of an address 1827 object, in the same or different Address Blocks) is associated 1828 with more than one Value by one or more Address Block TLVs with 1829 Type = OTHER_NEIGHB. 1831 A router MAY recognize additional reasons for identifying that a 1832 message is badly formed and therefore invalid for processing, e.g., 1833 to allow a security protocol as suggested in Section 17 to perform 1834 verification of HELLO message signatures and prevent processing of 1835 unverifiable HELLO messages by this protocol. 1837 An invalid message MUST be silently discarded, without updating the 1838 router's Information Bases. 1840 12.2. Definitions 1842 For the purpose of this section, note the following definitions: 1844 o "validity time" is calculated from the Message TLV with Type = 1845 VALIDITY_TIME of the HELLO message as specified in [RFC5497]. 1846 (Note that, as specified by Section 12.1, there must be exactly 1847 one such Message TLV in the HELLO message.) All information in 1848 the HELLO message used by this specification has the same validity 1849 time. 1851 o "Receiving Address List" is the I_local_iface_addr_list 1852 corresponding to the MANET interface on which the HELLO message 1853 was received 1855 o "Sending Address List" is an unordered list of network addresses 1856 of the MANET interface over which the HELLO message was sent, 1857 i.e., is an unordered list of the network addresses represented by 1858 address objects contained in the HELLO message with an associated 1859 Address Block TLV with Type = LOCAL_IF and Value = THIS_IF. If 1860 the Sending Address List is otherwise empty, then the Sending 1861 Address List contains a single network address with maximum prefix 1862 length (i.e., /32 for IPv4, /128 for IPv6) with address equal to 1863 the sending address of the IP datagram in which the HELLO message 1864 was included. 1866 o "Neighbor Address List" is an unordered list of all the network 1867 addresses of all the interfaces of the router which generated the 1868 HELLO message, i.e., is the Sending Address List, plus the network 1869 addresses represented by address objects contained in the HELLO 1870 message with an associated Address Block TLV with Type = LOCAL_IF 1871 and Value = OTHER_IF. 1873 o "EXPIRED" indicates that a timer is set to a value clearly 1874 preceding the current time (e.g., , current time - 1). 1876 o "Removed Address List" is a list of network addresses created by 1877 this HELLO message processing which were formerly reported as 1878 local by the router originating the HELLO message, but which are 1879 not included in the Neighbor Address List. This list is 1880 initialized as empty. 1882 o "Lost Address List" is a subset of the Removed Address List 1883 containing network addresses which were formerly considered as 1884 symmetric. This list is initialized as empty. 1886 12.3. Updating the Neighbor Set 1888 On receiving a HELLO message, the router MUST update its Neighbor Set 1889 and populate the Removed Address List and Lost Address List: 1891 1. Find all Neighbor Tuples (henceforth matching Neighbor Tuples) 1892 where N_neighbor_addr_list contains any network address which 1893 overlaps with any network address in the Neighbor Address List. 1895 2. If there are no matching Neighbor Tuples, then: 1897 1. Create a new Neighbor Tuple with: 1899 o N_neighbor_addr_list := Neighbor Address List; 1901 o N_symmetric := false. 1903 3. If there is one matching Neighbor Tuple, then: 1905 1. If the matching Neighbor Tuple's N_neighbor_addr_list != 1906 Neighbor Address List, then: 1908 1. For each network address (henceforth removed address) 1909 which is contained in that N_neighbor_addr_list, but is 1910 not contained in the Neighbor Address List: 1912 1. Add removed address to the Removed Address List. 1914 2. If N_symmetric = true, then add removed address to 1915 the Lost Address List. 1917 2. Update the matching Neighbor Tuple by: 1919 o N_neighbor_addr_list := Neighbor Address List. 1921 4. If there are two or more matching Neighbor Tuples, then: 1923 1. For each network address (henceforth removed address) which 1924 is contained in the N_neighbor_addr_list of any of the 1925 matching Neighbor Tuples but is not contained in the Neighbor 1926 Address List: 1928 1. Add removed address to the Removed Address List. 1930 2. If N_symmetric = true, then add removed address to the 1931 Lost Address List. 1933 2. Replace the matching Neighbor Tuples by a single Neighbor 1934 Tuple with: 1936 o N_neighbor_addr_list := Neighbor Address List; 1938 o N_symmetric := false 1940 12.4. Updating the Lost Neighbor Set 1942 On receiving a HELLO message, a router MUST update its Lost Neighbor 1943 Set: 1945 1. For each network address (henceforth lost address) which is 1946 contained in the Lost Address List, if no Lost Neighbor Tuple 1947 with NL_neighbor_addr = lost address exists, then add a Lost 1948 Neighbor Tuple with: 1950 o NL_neighbor_addr := lost address; 1952 o NL_time := current time + N_HOLD_TIME. 1954 12.5. Updating the Link Sets 1956 On receiving a HELLO message, a router MUST update its Link Sets: 1958 1. Remove all network addresses in the Removed Address List from the 1959 L_neighbor_iface_addr_list of all Link Tuples. 1961 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now 1962 empty; apply Section 13.2, but not Section 13.3. 1964 The router MUST then update its Link Set for the MANET interface on 1965 which the HELLO message is received: 1967 1. Find all Link Tuples (henceforth matching Link Tuples) where: 1969 o L_neighbor_iface_addr_list contains one or more network 1970 addresses in the Sending Address List. 1972 2. If there is more than one matching Link Tuple, then remove them 1973 all; apply Section 13.2, but not Section 13.3. 1975 3. If no matching Link Tuples remain, then create a new matching 1976 Link Tuple with: 1978 o L_neighbor_iface_addr_list := empty; 1979 o L_HEARD_time := EXPIRED; 1981 o L_SYM_time := EXPIRED; 1983 o L_quality := INITIAL_QUALITY; 1985 o L_pending := INITIAL_PENDING; 1987 o L_lost := false; 1989 o L_time := current time + validity time. 1991 4. The matching Link Tuple, existing or new, is then modified as 1992 follows: 1994 1. If the router finds any network address (henceforth receiving 1995 address) in the Receiving Address List in an Address Block in 1996 the HELLO message, then the Link Tuple is modified as 1997 follows: 1999 1. If any receiving address in the HELLO message is 2000 associated with an Address Block TLV with Type = 2001 LINK_STATUS and with Value = HEARD or Value = SYMMETRIC 2002 then: 2004 o L_SYM_time := current time + validity time. 2006 2. Otherwise if any receiving address in the HELLO message 2007 is associated with an Address Block TLV with Type = 2008 LINK_STATUS and Value = LOST then: 2010 1. if L_SYM_time has not expired, then: 2012 1. L_SYM_time := EXPIRED. 2014 2. if L_status = HEARD, then: 2016 o L_time := current time + L_HOLD_TIME. 2018 2. L_neighbor_iface_addr_list := Sending Address List. 2020 3. L_HEARD_time := max(current time + validity time, 2021 L_SYM_time). 2023 4. If L_status = PENDING, then: 2025 o L_time := max(L_time, L_HEARD_time). 2027 5. Otherwise if L_status = HEARD or L_status = SYMMETRIC, then: 2029 o L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 2031 12.6. Updating the 2-Hop Set 2033 On receiving a HELLO message a router MUST update its 2-Hop Set for 2034 the MANET interface on which the HELLO message was received: 2036 1. Remove all network addresses in the Removed Address List from the 2037 N2_neighbor_iface_addr_list of all 2-Hop Tuples. 2039 2. If the Link Tuple whose L_neighbor_iface_addr_list = Sending 2040 Address List, has L_status = SYMMETRIC then: 2042 1. For each network address (henceforth 2-hop address) in an 2043 Address Block of the HELLO message, where: 2045 o 2-hop address is not contained in the Neighbor Address 2046 List; 2048 o 2-hop address is not contained in any 2049 I_local_iface_addr_list; AND 2051 o 2-hop address != any IR_local_iface_addr 2053 perform the following processing: 2055 1. If 2-hop address has an associated Address Block TLV 2056 with: 2058 o Type = LINK_STATUS and Value = SYMMETRIC; OR 2060 o Type = OTHER_NEIGHB and Value = SYMMETRIC, 2062 then, if there is no 2-Hop Tuple such that: 2064 o N2_neighbor_iface_addr_list contains one or more 2065 network addresses in the Sending Address List; AND 2067 o N2_2hop_addr = 2-hop address. 2069 then create a 2-Hop Neighbor Tuple with: 2071 o N2_2hop_addr := 2-hop address. 2073 This 2-Hop Tuple (existing or new) is then modified as 2074 follows: 2076 o N2_neighbor_iface_addr_list := Sending Address List; 2078 o N2_time := current time + validity time. 2080 2. Otherwise if 2-hop address has an Address Block TLV with: 2082 o Type = LINK_STATUS and Value = LOST or Value = HEARD; 2083 OR 2085 o Type = OTHER_NEIGHB and Value = LOST; 2087 then remove all 2-Hop Tuples with: 2089 o N2_neighbor_iface_addr_list contains one or more 2090 network addresses in the Sending Address List; AND 2092 o N2_2hop_addr = 2-hop address. 2094 13. Other Information Base Changes 2096 The Interface and Neighbor Information Bases MUST be changed when 2097 certain events occur. These events may result from HELLO message 2098 processing, or may be otherwise generated (e.g., expiry of timers or 2099 link quality changes). 2101 Events which cause changes in the Information Bases are: 2103 o A Link Tuple's L_status changes to SYMMETRIC. In this case, the 2104 actions specified in Section 13.1 are performed. 2106 o A Link Tuple's L_status changes from SYMMETRIC, or the Link Tuple 2107 is removed. In this case, the actions specified in Section 13.2 2108 are performed. 2110 o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed. 2111 In this case, the actions specified in Section 13.3 are performed. 2113 o Local interface network address changes. In this case, the 2114 actions specified in Section 9 are performed. 2116 o Link quality changes. In this case, the actions specified in 2117 Section 14 are performed. 2119 If a Link Tuple is removed, or if L_status changes from SYMMETRIC and 2120 L_HEARD_time expires, then the actions specified in Section 13.2 MUST 2121 be performed before the actions specified in Section 13.3 are 2122 performed for that Link Tuple. 2124 A router MAY report updated information in response to any of these 2125 changes in HELLO message(s), subject to the constraints in 2126 Section 11. 2128 A router which transmits HELLO messages in response to such changes 2129 SHOULD transmit a HELLO message: 2131 o On all MANET interfaces, if the Neighbor Set changes such as to 2132 indicate the change in symmetry of any 1-hop neighbors (including 2133 addition or removal of symmetric 1-hop neighbors). 2135 o Otherwise, on all those MANET interfaces whose Link Set changes 2136 such as to indicate a change in L_status of any 1-hop neighbors 2137 (including the addition or removal of any 1-hop neighbors, other 2138 than those considered pending). 2140 13.1. Link Tuple Symmetric 2142 If, for any Link Tuple which does not have L_status = SYMMETRIC: 2144 o L_status changes to SYMMETRIC; 2146 then: 2148 1. For the Neighbor Tuple whose N_neighbor_addr_list contains 2149 L_neighbor_iface_addr_list, set: 2151 o N_symmetric := true. 2153 2. Remove all Lost Neighbor Tuples whose NL_neighbor_addr is 2154 contained in that N_neighbor_addr_list. 2156 This includes any newly created Link Tuples whose status is 2157 immediately updated such that L_status = SYMMETRIC. (Note that in 2158 this specification all Link Tuples are created such that their 2159 L_status is not SYMMETRIC, but a Link Tuple may be immediately 2160 updated by subsequent processing of the same HELLO message that 2161 caused the creation of the Link Tuple such that the Link Tuple's 2162 L_status changes to SYMMETRIC.) 2164 13.2. Link Tuple Not Symmetric 2166 If for any Link Tuple with L_status = SYMMETRIC: 2168 o L_status changes to any other value; OR 2170 o the Link Tuple is removed; 2171 then: 2173 1. All 2-Hop Tuples for the same MANET interface with: 2175 o N2_neighbor_iface_addr_list contains one or more network 2176 addresses in L_neighbor_iface_addr_list; 2178 are removed. 2180 2. For the Neighbor Tuple whose N_neighbor_addr_list contains 2181 L_neighbor_iface_addr_list: 2183 1. If there are no remaining Link Tuples for any MANET interface 2184 where: 2186 o L_neighbor_iface_addr_list is contained in 2187 N_neighbor_addr_list; AND 2189 o L_status = SYMMETRIC; 2191 then modify the Neighbor Tuple by: 2193 1. N_symmetric := false. 2195 2. For each network address (henceforth neighbor address) in 2196 N_neighbor_addr_list, add a Lost Neighbor Tuple with: 2198 o NL_neighbor_addr := neighbor address; 2200 o NL_time := current time + N_HOLD_TIME. 2202 13.3. Link Tuple Heard Timeout 2204 If, for any Link Tuple: 2206 o L_HEARD_time expires; OR 2208 o the Link Tuple is removed; 2210 then: 2212 1. For the Neighbor Tuple whose N_neighbor_addr_list contains 2213 L_neighbor_iface_addr_list, if no Link Tuples for any MANET 2214 interface remain where: 2216 o L_neighbor_iface_addr_list is contained in 2217 N_neighbor_addr_list; AND 2219 o L_HEARD_time is not expired; 2221 then remove the Neighbor Tuple. 2223 14. Link Quality 2225 Link quality is a mechanism whereby a router MAY take considerations 2226 other than message exchange into account for determining when a link 2227 is and is not a candidate for being considered as HEARD or SYMMETRIC. 2228 As such, it is a "link admission" mechanism. 2230 Link quality information for a link is generated (e.g., through 2231 access to signal to noise ratio, packet loss rate, or other 2232 information from the link layer) and used only locally, i.e., is not 2233 included in signaling, and routers may interoperate whether they are 2234 using the same, different, or no, link quality information. Link 2235 quality information is specified as a normalized, dimensionless 2236 figure in the interval zero to one, inclusive, a higher value 2237 indicating a better link quality. 2239 For deployments where no link quality is used, the considerations in 2240 Section 14.1 apply. For deployments where link quality is used, the 2241 general principles of link quality usage are described in 2242 Section 14.2. Section 14.3 and Section 14.4 detail link quality 2243 functioning. 2245 14.1. Deployment Without Link Quality 2247 In order for a router to not employ link quality, the router MUST 2248 define: 2250 o INITIAL_PENDING := false; 2252 o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define 2253 INITIAL_QUALITY := 1). 2255 14.2. Basic Principles of Link Quality 2257 To enable link quality usage, the L_quality value of a Link Tuple is 2258 used in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, 2259 to set the flags L_pending and L_lost of that Link Tuple. Based on 2260 these flags, the link status to advertise for that Link Tuple is 2261 determined as described in Section 7.1. 2263 The use of two thresholds implements link hysteresis, whereby a link 2264 which has HYST_REJECT <= L_quality < HYST_ACCEPT may be either 2265 accepted or rejected (depending on which threshold it has most 2266 recently crossed, or, if neither, on the value of parameter 2267 INITIAL_PENDING). With appropriate values of these parameters, this 2268 prevents over-rapid changes of link status. 2270 The basic principles of link quality usage are as follows: 2272 o A router does not advertise a neighbor interface in any state 2273 until L_quality is acceptable: 2275 o If INITIAL_PENDING = true, then the link is advertised when 2276 link L_quality >= HYST_ACCEPT. 2278 o Otherwise the link is advertised when L_quality >= HYST_REJECT. 2280 A link which is not yet advertised has L_pending = true. 2282 o Once L_quality >= HYST_ACCEPT, the router sets L_pending := false, 2283 indicating that the link can be advertised. 2285 o A link for which L_pending = false is advertised until its 2286 L_quality drops below HYST_REJECT. 2288 o If a link has L_pending = false and L_quality < HYST_REJECT, the 2289 link is LOST and is advertised as such. This link is not 2290 reconsidered as a candidate HEARD or SYMMETRIC link until 2291 L_quality >= HYST_ACCEPT. 2293 o A link which has an acceptable quality may be advertised as HEARD, 2294 SYMMETRIC or LOST according to the exchange of HELLO messages. 2296 In order that these principles can all hold, a router MUST NOT 2297 define: 2299 o INITIAL_PENDING = false and INITIAL_QUALITY < HYST_REJECT; OR 2301 o INITIAL_PENDING = true and INITIAL_QUALITY >= HYST_ACCEPT. 2303 14.3. When Link Quality Changes 2305 If L_quality for a link changes, then the following actions MUST be 2306 taken: 2308 1. If L_quality >= HYST_ACCEPT then the corresponding Link Tuple is 2309 modified by: 2311 1. L_pending := false; 2313 2. L_lost := false; 2314 3. If L_status = HEARD or L_status = SYMMETRIC, then: 2316 o L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 2318 2. If L_status != PENDING, and L_quality < HYST_REJECT then the 2319 corresponding Link Tuple is modified by: 2321 1. If L_lost = false, then: 2323 o L_lost := true; 2325 o L_time := min(L_time, current time + L_HOLD_TIME). 2327 As a result of this processing, the L_STATUS of a Link Tuple may 2328 change. In this case, the processing actions corresponding to this 2329 change, as specified in Section 13, MUST also be taken. 2331 If L_quality for a link is updated based on HELLO message reception, 2332 or on reception of a packet including a HELLO message, then L_quality 2333 MUST be updated prior to the HELLO message processing described in 2334 Section 12. (If the receipt of the HELLO message, or the packet 2335 containing it, creates the Link Tuple, then the Link Tuple MUST be 2336 created with the appropriately updated L_quality value, rather than 2337 with L_quality := INITIAL_QUALITY.) 2339 14.4. Updating Link Quality 2341 A router MAY update link quality based on any information available 2342 to it. Particular cases that MAY be used include: 2344 o Information from the link layer, such as signal to noise ratio or 2345 packet acknowledgment reception and loss information. 2347 o Receipt or loss of control packets. If control packets include a 2348 sequential packet sequence number, as defined in [RFC5444], then 2349 link quality can be updated when a control packet is received, 2350 whether or not it contains a HELLO message. The link quality may 2351 then, for example, be based on whether the last N out of M control 2352 packets on the link were received, or may use a "leaky integrator" 2353 tracking packet reception and loss. 2355 o Receipt or loss of HELLO messages. If the maximum interval 2356 between HELLO messages is known (such as by inclusion in HELLO 2357 messages of a Message TLV with Type := INTERVAL_TIME, as defined 2358 in [RFC5497]) then the loss of HELLO messages can be determined 2359 without the need to receive a later HELLO message. Note that if 2360 this case is combined with the previous case then care must be 2361 taken to avoid "double counting" a lost HELLO message in a lost 2362 packet. 2364 15. Proposed Values for Parameters and Constants 2366 This section lists the parameters and constants used in the 2367 specification of the protocol, and proposed values of each which MAY 2368 be used when a single value of each is used. 2370 15.1. Message Interval Interface Parameters 2372 o HELLO_INTERVAL := 2 seconds 2374 o HELLO_MIN_INTERVAL := HELLO_INTERVAL/4 2376 o REFRESH_INTERVAL := HELLO_INTERVAL 2378 15.2. Information Validity Time Interface Parameters 2380 o H_HOLD_TIME := 3 x REFRESH_INTERVAL 2382 o L_HOLD_TIME := H_HOLD_TIME 2384 15.3. Information Validity Time Router Parameters 2386 o N_HOLD_TIME := L_HOLD_TIME 2388 o I_HOLD_TIME := N_HOLD_TIME 2390 15.4. Link Quality Interface Parameters 2392 If link quality is changed, then parameter values will depend on the 2393 link quality process. If link quality is not changed, then: 2395 o HYST_ACCEPT := 1 2397 o HYST_REJECT := 0 2399 o INITIAL_QUALITY := 1 2401 o INITIAL_PENDING := false 2403 15.5. Jitter Interface Parameters 2405 o HP_MAXJITTER := HELLO_INTERVAL/4 2407 o HT_MAXJITTER := HP_MAXJITTER 2409 15.6. Constants 2411 o C := 1/1024 second 2413 16. Usage with Other Protocols 2415 Other protocols, such as MANET routing protocols, which use 2416 neighborhood discovery, may need to interact with this protocol. 2417 This protocol is designed to permit such interactions, in particular: 2419 o Through accessing, and possibly extending, the information in the 2420 Local Information Base (Section 6), the Interface Information Base 2421 (Section 7) and the Neighbor Information Base (Section 8). These 2422 Information Bases record the interface configuration of the 2423 router, as well as the local connectivity, up to two hops away. 2424 All updates to the elements specified in this document are subject 2425 to the constraints specified in Appendix B. 2427 o Through accessing an outgoing HELLO message prior to it being 2428 transmitted over any MANET interface, and to add information 2429 (e.g., , TLVs) as specified in [RFC5444]. This may, for example, 2430 be to allow a security protocol, as suggested in Section 17, to 2431 add a TLV containing a cryptographic signature to the message, or 2432 be to allow inserting relay selection information into a HELLO 2433 message by way of adding a TLV to an outgoing HELLO message prior 2434 to it being transmitted. 2436 o Through accessing an incoming HELLO message, and potentially 2437 discarding it prior to processing by this protocol. This may, for 2438 example, allow a security protocol as suggested in Section 17 to 2439 perform verification of HELLO message signatures and prevent 2440 processing of unverifiable HELLO messages by this protocol. 2442 o Through accessing an incoming HELLO message after it has been 2443 completely processed by this protocol. This may, in particular, 2444 allow a protocol which has added information, such as relay 2445 selection information by way of inclusion of appropriate TLVs, 2446 access to such information after appropriate updates have been 2447 recorded in the Information Bases in this protocol. 2449 o Through requesting that a HELLO message be generated at a specific 2450 time. In that case, HELLO message generation MUST still respect 2451 the constraints in Appendix B. 2453 Address objects in HELLO messages are processed according to their 2454 associated Address Block TLVs. All such address objects are to be 2455 processed according to this specification are associated with Address 2456 Block TLVs with Type of LOCAL_IF, OTHER_NEIGHB or LINK_STATUS (and 2457 type extension zero). Address objects not associated with an Address 2458 Block TLV of any of these Types are therefore not processed by the 2459 protocol described in this specification. 2461 A protocol, such as a MANET routing protocol, interacting with this 2462 protocol may need to add information to HELLO messages. This may be 2463 in form of associating TLVs (of Type other than LOCAL_IF, 2464 OTHER_NEIGHB or LINK_STATUS) to address objects already included by 2465 this specification. 2467 A protocol, such as a MANET routing protocol, interacting with this 2468 protocol may also add information to HELLO messages by inserting 2469 address objects not already included by this specification. Such 2470 address objects are in the following called "inserted addresses". 2471 These inserted addresses may added to Address Blocks already present 2472 by virtue of the HELLO message generation in this specification, or 2473 may appear in new Address Blocks. In both cases, the following MUST 2474 be observed: 2476 o An inserted address MUST NOT be associated with an Address Block 2477 TLV of Type LOCAL_IF, OTHER_NEIGHB or LINK_STATUS. Consequently, 2478 the processing in this specification will ignore such address 2479 objects. 2481 o Each inserted address MUST be associated with an Address Block 2482 TLV, to be defined by the specification of the protocol inserting 2483 the address object. In this way, all addresses present in a HELLO 2484 message are associated with an Address Block TLV defining their 2485 semantics. 2487 Informally speaking, Address Block TLVs define the semantics of 2488 address objects in an Address Block. If an address object in an 2489 Address Block does not have any Address Block TLVs associated, that 2490 address object has no semantics. Consequently, all protocols using 2491 the protocol defined in this specification MUST respect the 2492 following: 2494 o An address object in an Address Block, which is not associated 2495 with any Address Block TLV, MUST be silently ignored; the mere 2496 presence of an address object without an associated Address Block 2497 TLV in a HELLO message MUST NOT cause any processing. 2499 A protocol interacting with this protocol MAY also add an originator 2500 address to HELLO messages, as specified in [RFC5444]. Such an 2501 originator address MUST be unique to the originating router, it MAY 2502 be a local interface address of the router. It SHOULD be used 2503 consistently, but SHOULD NOT be constrained in any other way. 2505 Strict adherence to these points will enable unambiguous co-existence 2506 of future "extensions" to HELLO messages. 2508 In some cases, a protocol interacting with the protocol defined in 2509 this specification, may need to recognize which HELLO messages to 2510 process and which HELLO messages to discard. It is the 2511 responsibility of that protocol to ensure that such messages are 2512 suitably identifiable, e.g., through inclusion of a Message TLV or 2513 through recognizing an administrative configuration (such as address 2514 ranges). Note that such a protocol interacting with this protocol 2515 MAY specify such interaction by recognizing an additional reason for 2516 discarding a message. As suggested in Section 17 this might, for 2517 example, be a security protocol discarding a message which does not 2518 carry a Message TLV containing a cryptographic signature. 2520 17. Security Considerations 2522 The objective of this protocol is to allow each router in the network 2523 to acquire information describing its 1-hop neighborhood and 2524 symmetric 2-hop neighborhood. This is acquired through HELLO message 2525 exchange between neighboring routers. This information is made 2526 available through the Interface Information Bases and Neighbor 2527 Information Base, describing the router's 1-hop neighborhood and 2528 symmetric 2-hop neighborhood. 2530 Under normal circumstances, the information recorded in these 2531 Information Bases is correct, i.e., corresponds to the actual network 2532 topology, apart from any changes which have not (yet) been tracked by 2533 the HELLO message exchanges. 2535 If a router for some reason, whether malice or malfunction, transmits 2536 invalid HELLO messages, incorrect information may be recorded in 2537 other routers' Information Bases. This protocol specification does, 2538 however, prevent inconsistent information from being included in the 2539 Information Bases through the specified processing, which maintains 2540 the constraints in Appendix B. The exact consequence of information 2541 inexactness depends on the use of these Information Bases, and SHOULD 2542 therefore be reflected in the specification of protocols which use 2543 information provided by this neighborhood discovery protocol. 2545 This section, therefore, firstly outlines the ways in which correctly 2546 formed, but still invalid, HELLO messages may appear, in 2547 Section 17.1. 2549 Injection of invalid HELLO messages into a network may be prevented 2550 in a number of ways. If, for example, a network is deployed in a 2551 site to which access is strictly regulated, so that physical access 2552 and proximity to the network is prevented, then further security 2553 mechanisms to protect against malicious routers injecting invalid 2554 HELLO messages may not be required. Similarly, if the link layer 2555 over which the network is formed provides appropriate 2556 confidentiality, authentication, and integrity, then this may, for a 2557 given deployment, suffice to appropriately protect against disclosure 2558 of information to an eavesdropper, and against a malicious router 2559 injecting invalid HELLO messages. In the latter case the link layer 2560 would discard frames that fail the link layer checks, without 2561 attempting to deliver such frames to IP. Finally, certain usage may 2562 be of a nature where disruption of service is of no consequence, or 2563 at least not of sufficient consequence to warrant deployment of 2564 additional security mechanisms. 2566 A further point to stress, and which follows from the discussions 2567 above is, that it will not be the case that "one size security fits 2568 all". Different deployments may have different requirements. For 2569 example in a deployment of a low value sensor network, authentication 2570 using a simple message authentication code and shared symmetric keys 2571 may suffice, while anything beyond that may require too many 2572 computational resources to be viable. Conversely, in, for example, a 2573 community network, verifying not only that the originator of a HELLO 2574 message "has the right key" but also the precise identity of the 2575 originator may be required to be proved, and computational resources 2576 may be available to make such a requirement feasible. 2578 Section 17.2, therefore, does not specify a single "one-size-fits- 2579 all" mechanism, but rather details how the security suggestions in 2580 [RFC5444] are considered for applicability within the context of this 2581 protocol, and with the purpose of aiding deployment-specific security 2582 mechanisms to be developed. 2584 17.1. Invalid HELLO Messages 2586 A correctly formed, but still invalid, HELLO message may take any of 2587 the following forms. Note that a present or absent address object in 2588 an Address Block, does not by itself cause a problem. It is the 2589 presence, absence, or incorrectness of associated LOCAL_IF, 2590 LINK_STATUS and OTHER_NEIGHB Address Block TLVs that causes problems. 2592 A router may provide false information about its own identity: 2594 o The HELLO message may contain address objects with an 2595 associated LOCAL_IF Address Block TLV which do not correspond 2596 to addresses of interfaces of the router transmitting the HELLO 2597 message. 2599 o The HELLO message may omit network addresses, or their 2600 associated LOCAL_IF Address Block TLV, of interfaces of the 2601 router transmitting the HELLO message (other than the allowed 2602 omission of the only local interface network address of the 2603 MANET interface over which the HELLO message is transmitted, if 2604 that is the case). 2606 o The HELLO message may incorrectly specify the LOCAL_IF Address 2607 Block TLV Value associated with one or more local interface 2608 network addresses, indicating incorrectly whether they are 2609 associated with the MANET interface over which the HELLO 2610 message is transmitted. 2612 A router may provide false information about the identity of other 2613 routers: 2615 o A present LINK_STATUS Address Block TLV may, incorrectly, 2616 identify a network address as being of a MANET interface which 2617 is or was heard on the MANET interface over which the HELLO 2618 message is transmitted. 2620 o A consistently absent LINK_STATUS Address Block TLV may, 2621 incorrectly, fail to identify a network address as being of a 2622 MANET interface which is or was heard on the MANET interface 2623 over which the HELLO message is transmitted. 2625 o A present OTHER_NEIGHB Address Block TLV may, incorrectly, 2626 identify a network address as being of a router which is or was 2627 in the sending router's symmetric 1-hop neighborhood. 2629 o A consistently absent OTHER_NEIGHB Address Block TLV may, 2630 incorrectly, fail to identify a network address as being of a 2631 router which is or was in the sending router's symmetric 1-hop 2632 neighborhood. 2634 o The Value of a LINK_STATUS Address Block TLV may incorrectly 2635 indicate the status (LOST, SYMMETRIC or HEARD) of the link from 2636 a 1-hop neighbor. 2638 o The Value of an OTHER_NEIGHB Address Block TLV may incorrectly 2639 indicate the status (LOST or SYMMETRIC) of a symmetric 1-hop 2640 neighbor. 2642 17.2. Authentication, Integrity and Confidentiality Suggestions 2644 The security suggestions in [RFC5444] regarding inclusion of a 2645 cryptographic signature in a Message TLV or a Packet TLV can be 2646 applied to this protocol. Failure to verify either form of 2647 cryptographic signature should cause a HELLO message to be rejected 2648 without being processed. 2650 The following simplification of the suggestions for end-to-end 2651 authentication for integrity in [RFC5444] may be applied to HELLO 2652 messages: 2654 o As the Message Header fields and 2655 are either omitted or will always have the values 0 and 1, 2656 respectively, an end to end cryptographic signature can be 2657 calculated based on the entire HELLO message, including its 2658 unmodified Message Header. 2660 The security mechanisms suggested in [RFC5444] with respect to 2661 confidentiality can be directly applied to this protocol. 2663 18. IANA Considerations 2665 This specification defines one Message Type, which must be allocated 2666 from the "Message Types" registry of [RFC5444], and three Address 2667 Block TLV Types, which must be allocated from the "Address Block TLV 2668 Types" registry of [RFC5444]. 2670 18.1. Expert Review: Evaluation Guidelines 2672 For the registries where an Expert Review is required, the designated 2673 expert SHOULD take the same general recommendations into 2674 consideration as are specified by [RFC5444]. 2676 18.2. Message Types 2678 This specification defines one Message Type, to be allocated from the 2679 0-223 range of the "Message Types" namespace defined in [RFC5444], as 2680 specified in Table 3. 2682 +------+-------------------------+ 2683 | Type | Description | 2684 +------+-------------------------+ 2685 | TBD1 | HELLO : Local signaling | 2686 +------+-------------------------+ 2688 Table 3: Message Type assignment 2690 18.3. Message-Type-Specific TLV Type Registries 2692 IANA is requested to create a registry for Message-Type-specific 2693 Message TLVs for HELLO messages, in accordance with Section 6.2.1 of 2694 [RFC5444], and with initial assignments and allocation policies as 2695 specified in Table 4. 2697 +---------+-------------+-------------------+ 2698 | Type | Description | Allocation Policy | 2699 +---------+-------------+-------------------+ 2700 | 128-223 | Unassigned | Expert Review | 2701 +---------+-------------+-------------------+ 2703 Table 4: HELLO Message-Type-specific Message TLV Types 2705 IANA is requested to create a registry for Message-Type-specific 2706 Address Block TLVs for HELLO messages, in accordance with Section 2707 6.2.1 of [RFC5444], and with initial assignments and allocation 2708 policies as specified in Table 5. 2710 +---------+-------------+-------------------+ 2711 | Type | Description | Allocation Policy | 2712 +---------+-------------+-------------------+ 2713 | 128-223 | Unassigned | Expert Review | 2714 +---------+-------------+-------------------+ 2716 Table 5: HELLO Message-Type-specific Address Block TLV Types 2718 18.4. Address Block TLV Types 2720 This specification defines three Address Block TLV Types, which must 2721 be allocated from the "Address Block TLV Types" namespace defined in 2722 [RFC5444]. IANA are requested to make allocations in the 0-127 range 2723 for these types. This will create three new type extension 2724 registries with assignments as specified in Table 6, Table 7 and 2725 Table 8. Specifications of these Address Block TLVs are in 2726 Section 10.1.1, with Value Constants defined in Section 18.5. 2728 +----------+------+-----------+------------------------+------------+ 2729 | Name | Type | Type | Description | Allocation | 2730 | | | extension | | policy | 2731 +----------+------+-----------+------------------------+------------+ 2732 | LOCAL_IF | TBD2 | 0 | Specifies that the | | 2733 | | | | network address is | | 2734 | | | | associated with this | | 2735 | | | | local interface of the | | 2736 | | | | sending router | | 2737 | | | | (THIS_IF = 0) or | | 2738 | | | | another local | | 2739 | | | | interface of the | | 2740 | | | | sending router | | 2741 | | | | (OTHER_IF = 1) | | 2742 | LOCAL_IF | TBD2 | 1-255 | Unassigned | Expert | 2743 | | | | | Review | 2744 +----------+------+-----------+------------------------+------------+ 2746 Table 6: Address Block TLV Type assignment: LOCAL_IF 2748 +-------------+------+-----------+---------------------+------------+ 2749 | Name | Type | Type | Description | Allocation | 2750 | | | extension | | policy | 2751 +-------------+------+-----------+---------------------+------------+ 2752 | LINK_STATUS | TBD3 | 0 | Specifies the | | 2753 | | | | status of the link | | 2754 | | | | from the indicated | | 2755 | | | | network address | | 2756 | | | | (LOST = 0, | | 2757 | | | | SYMMETRIC = 1, or | | 2758 | | | | HEARD = 2) | | 2759 | LINK_STATUS | TBD3 | 1-255 | Unassigned | Expert | 2760 | | | | | Review | 2761 +-------------+------+-----------+---------------------+------------+ 2763 Table 7: Address Block TLV Type assignment: LINK_STATUS 2765 +--------------+------+-----------+--------------------+------------+ 2766 | Name | Type | Type | Description | Allocation | 2767 | | | extension | | policy | 2768 +--------------+------+-----------+--------------------+------------+ 2769 | OTHER_NEIGHB | TBD4 | 0 | Specifies that the | | 2770 | | | | network address is | | 2771 | | | | (SYMMETRIC = 1) or | | 2772 | | | | recently was (LOST | | 2773 | | | | = 0) of an | | 2774 | | | | interface of a | | 2775 | | | | symmetric 1-hop | | 2776 | | | | neighbor of the | | 2777 | | | | router | | 2778 | | | | transmitting the | | 2779 | | | | message | | 2780 | OTHER_NEIGHB | TBD4 | 1-255 | Unassigned | Expert | 2781 | | | | | Review | 2782 +--------------+------+-----------+--------------------+------------+ 2784 Table 8: Address Block TLV Type assignment: OTHER_NEIGHB 2786 18.5. LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Values 2788 Note: This section does not require any IANA action, as the required 2789 information is included in the descriptions of the Address Block TLVs 2790 allocated in Section 18.4. This information is recorded here for 2791 clarity, and for use elsewhere in this specification. 2793 The Values which the LOCAL_IF Address Block TLV can use are the 2794 following: 2796 o THIS_IF := 0 2798 o OTHER_IF := 1 2800 The Values which the LINK_STATUS Address Block TLV can use are the 2801 following: 2803 o LOST := 0 2805 o SYMMETRIC := 1 2807 o HEARD := 2 2809 The Values which the OTHER_NEIGHB Address Block TLV can use are the 2810 following: 2812 o LOST := 0 2814 o SYMMETRIC := 1 2816 19. Contributors 2818 This specification is the result of the joint efforts of the 2819 following contributors, listed alphabetically. 2821 o Brian Adamson, NRL, USA, 2823 o Cedric Adjih, INRIA, France, 2825 o Thomas Heide Clausen, LIX, France, 2827 o Justin Dean, NRL, USA, 2829 o Christopher Dearlove, BAE Systems ATC, UK, 2830 2832 o Philippe Jacquet, INRIA, France, 2834 20. Acknowledgments 2836 The authors would like to acknowledge the team behind OLSRv1, 2837 specified in RFC3626 for their contributions. 2839 The authors would like to gratefully acknowledge the following people 2840 for intense technical discussions, early reviews and comments on the 2841 specification and its components (listed alphabetically): Alan Cullen 2842 (BAE Systems), Ulrich Herberg (LIX), Satoh Hiroki (Hitachi) Joe 2843 Macker (NRL), Charles E. Perkins (WiChorus), Laurent Viennot (INRIA), 2844 and the entire IETF MANET working group. 2846 21. References 2848 21.1. Normative References 2850 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2851 Requirement Levels", RFC 2119, BCP 14, March 1997. 2853 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 2854 considerations in MANETs", RFC 5148, February 2008. 2856 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2857 "Generalized MANET Packet/Message Format", RFC 5444, 2858 February 2009. 2860 [RFC5497] Clausen, T. and C. Dearlove, "Representing multi-value 2861 time in MANETs", RFC 5497, March 2009. 2863 [RFC5498] Chakeres, I., "IANA Allocations for MANET Protocols", 2864 RFC 5498, March 2009. 2866 21.2. Informative References 2868 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 2869 (MANET): Routing Protocol Performance Issues and 2870 Evaluation Considerations", RFC 2501, January 1999. 2872 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 2873 Routing Protocol", RFC 3626, October 2003. 2875 [RFC5449] Clausen, T., Baccelli, E., Nguyen, D., and P. Jacquet, 2876 "OSPF Multipoint Relay (MPR) Extension for Ad Hoc 2877 Networks", RFC 5449, February 2009. 2879 Appendix A. Address Block TLV Combinations 2881 The algorithm for generating HELLO messages in Section 11 specifies 2882 which 1-hop neighbor network addresses may be included in the Address 2883 Blocks, and with which associated Address Block TLVs. These Address 2884 Block TLVs may have Type = LINK_STATUS or Type = OTHER_NEIGHB, or 2885 both. Address Block TLVs with Type = LINK_STATUS may have three 2886 possible Values (Value = HEARD, Value = SYMMETRIC or Value = LOST), 2887 and Address Block TLVs of TYPE = OTHER_NEIGHB may have two possible 2888 Values (Value = SYMMETRIC or Value = LOST). When both Address Block 2889 TLVs are associated with the same network address only certain 2890 combinations of these Address Block TLV Values are necessary, and are 2891 the only combinations generated by the algorithm in Section 11. 2892 These combinations are indicated in Table 9. 2894 Cells labeled with "Yes" indicate the possible combinations which are 2895 generated by the algorithm in Section 11. Cells labeled with "No" 2896 indicate combinations not generated by the algorithm in Section 11, 2897 but which are correctly parsed and interpreted by the algorithm in 2898 Section 12. The cell labeled with "No*" is actually inconsistent, it 2899 is handled by ignoring the Address Block TLV with Type = 2900 OTHER_NEIGHB, but SHOULD NOT be used. 2902 +----------------+----------------+----------------+----------------+ 2903 | | Type = | Type = | Type = | 2904 | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | 2905 | | (absent) | Value = | Value = LOST | 2906 | | | SYMMETRIC | | 2907 +----------------+----------------+----------------+----------------+ 2908 | Type = | No | Yes | Yes | 2909 | LINK_STATUS | | | | 2910 | (absent) | | | | 2911 | Type = | Yes | Yes | Yes | 2912 | LINK_STATUS, | | | | 2913 | Value = HEARD | | | | 2914 | Type = | Yes | No | No* | 2915 | LINK_STATUS, | | | | 2916 | Value = | | | | 2917 | SYMMETRIC | | | | 2918 | Type = | Yes | Yes | No | 2919 | LINK_STATUS, | | | | 2920 | Value = LOST | | | | 2921 +----------------+----------------+----------------+----------------+ 2923 Table 9: LINK_STATUS and OTHER_NEIGHB TLV combinations 2925 Appendix B. Constraints 2927 Any process which updates the Local Information Base or the Neighbor 2928 Information Base MUST ensure that all constraints specified in this 2929 appendix are maintained. 2931 In each Local Interface Tuple: 2933 o I_local_iface_addr_list MUST NOT be empty. 2935 o I_local_iface_addr_list MUST NOT contain any duplicated network 2936 addresses. 2938 o If I_manet = true, then I_local_iface_addr_list MUST NOT contain 2939 any network address which overlaps any network address in the 2940 I_local_iface_addr_list of any other Local Interface Tuple with 2941 I_manet = true, unless it is known that the corresponding MANET 2942 interfaces will always communicate with separate sets of MANET 2943 interfaces on other routers. 2945 In each Removed Interface Address Tuple: 2947 o IR_local_iface_addr MUST NOT contain any network address which is 2948 in the I_local_iface_addr_list of any Local Interface Tuple. 2950 o IR_local_iface_addr MUST NOT equal the IR_local_iface_addr of any 2951 other Removed Interface Address Tuple. 2953 In each Link Tuple: 2955 o L_neighbor_iface_addr_list MUST NOT be empty. 2957 o L_neighbor_iface_addr_list MUST NOT contain any network address 2958 which overlaps any network address in the I_local_iface_addr_list 2959 of any Local Interface Tuple or the IR_local_iface_addr of any 2960 Removed Interface Address Tuple. 2962 o L_neighbor_iface_addr_list MUST NOT contain any duplicated network 2963 addresses. 2965 o L_neighbor_iface_addr_list MUST NOT contain any network address 2966 which is in the L_neighbor_iface_addr_list of any other Link Tuple 2967 in the same Link Set. 2969 o If L_HEARD_time has not expired then there MUST be a Neighbor 2970 Tuple whose N_neighbor_addr_list contains 2971 L_neighbor_iface_addr_list. 2973 o L_HEARD_time MUST NOT be greater than L_time. 2975 o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are 2976 expired). 2978 o L_quality MUST NOT be less than 0 or greater than 1. 2980 o If L_quality >= HYST_ACCEPT then L_pending MUST be false. 2982 o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST. 2984 o L_pending MUST NOT be set to true if it is currently false. 2986 In each Neighbor Tuple: 2988 o N_neighbor_addr_list MUST NOT contain any network address which 2989 overlaps any network address in the I_local_iface_addr_list of any 2990 Local Interface Tuple or the IR_local_iface_addr of any Removed 2991 Interface Address Tuple. 2993 o N_neighbor_addr_list MUST NOT contain any duplicated network 2994 addresses. 2996 o N_neighbor_addr_list MUST NOT contain any network address which is 2997 in the N_neighbor_addr_list of any other Neighbor Tuple. 2999 o If N_symmetric is = true, then there MUST be one or more Link 3000 Tuples with: 3002 o L_neighbor_iface_addr_list contained in N_neighbor_addr_list; 3003 AND 3005 o L_status = SYMMETRIC. 3007 o If N_symmetric is = false, then there MUST be one or more Link 3008 Tuples with: 3010 o L_neighbor_iface_addr_list contained in N_neighbor_addr_list. 3012 All such Link Tuples MUST NOT have L_status = SYMMETRIC. At least 3013 one such Link Tuple MUST have L_HEARD_time not expired. 3015 In each Lost Neighbor Tuple: 3017 o NL_neighbor_addr MUST NOT overlap any network address in the 3018 I_local_iface_addr_list of any Local Interface Tuple or the 3019 IR_local_iface_addr of any Removed Interface Address Tuple. 3021 o NL_neighbor_addr MUST NOT equal the NL_neighbor_addr of any other 3022 Lost Neighbor Tuple. 3024 o NL_neighbor_addr MUST NOT be in the N_neighbor_addr_list of any 3025 Neighbor Tuple with N_symmetric = true. 3027 In each 2-Hop Tuple: 3029 o There MUST be a Link Tuple associated with the same MANET 3030 interface with: 3032 o L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list; AND 3034 o L_status = SYMMETRIC. 3036 o N2_2hop_addr MUST NOT overlap any network address in the 3037 I_local_iface_addr_list of any Local Interface Tuple or the 3038 IR_local_iface_addr of any Removed Interface Address Tuple. 3040 o N2_2hop_addr MUST NOT be the N2_2hop_addr of any other 2-Hop Tuple 3041 in the same 2-Hop Set and with the same 3042 N2_neighbor_iface_addr_list. 3044 o N2_2hop_addr MUST NOT be in the N2_neighbor_iface_addr_list of the 3045 same 2-Hop Tuple. 3047 Appendix C. HELLO Message Example 3049 HELLO messages are instances of [RFC5444] messages, and this protocol 3050 supports any combination of message header options and address 3051 encodings, enabled by [RFC5444] that convey the required information. 3052 As a consequence, there is no single way to represent how all HELLO 3053 messages look. This appendix illustrates two HELLO message with 3054 similar content, the exact values included are explained in the 3055 following text. 3057 The HELLO message's four bit Message Flags (MF) field has value 7 3058 indicating that the message header contains hop limit, hop count and 3059 message sequence number fields. Its four bit Message Address Length 3060 (MAL) field has value 3 indicating addresses in the message have 3061 length four octets, here being IPv4 addresses. The message is as 3062 transmitted, with a hop limit of 1 and a hop count of 0. The overall 3063 message length is 45 octets. 3065 The message contains a Message TLV Block with content length 8 octets 3066 containing two Message TLVs, of types VALIDITY_TIME and 3067 INTERVAL_TIME. Each uses a Message TLV with Flags octet (MTLVF) 3068 value 16, indicating that each has a Value, and each has a Value 3069 Length of 1 octet. The Values included are time codes (as defined in 3070 [RFC5497]) representing the parameters H_HOLD_TIME and 3071 HELLO_INTERVAL, respectively. 3073 The message has a single Address Block containing 5 addresses. The 3074 Address Block Flags octet (ABF) value 128 indicates an address Head 3075 but no address Tail, and no address prefixes. The Head Length of 3 3076 octets indicates address Mid sections of one octet each (Mid 0 to Mid 3077 4). 3079 The following Address Block TLV Block (content length 14 octets) 3080 includes two Address Block TLVs. The first is a LOCAL_IF Address 3081 Block TLV with Flags octet (ATLVF) value 80, which indicates that a 3082 single address, with index 0 (i.e., the address Head:Mid 0) is the 3083 single local interface address of this router (the 1 octet Value 3084 THIS_IF indicates that this address is of this interface). The 3085 second is a LINK_STATUS Address Block TLV with Flags octet (ATLVF) 3086 value 52, which specifies the link status values of all reported 3087 neighbors in a single multivalue Address Block TLV that covers the 3088 addresses with indexes 1 to 4, inclusive. The Address Block TLV 3089 Value Length of 4 octets indicates one octet per Value per address. 3090 The last four addresses thus are of neighbors, each an with 3091 associated link status: the first and second HEARD, the third 3092 SYMMETRIC, and the fourth LOST. 3094 0 1 2 3 3095 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 3096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3097 | HELLO | MF=7 | MAL=3 | Message Length = 45 | 3098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3099 | Hop Limit = 1 | Hop Count = 0 | Message Sequence Number | 3100 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3101 | Message TLV Block Length = 8 | VALIDITY_TIME | MTLVF = 16 | 3102 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3103 | Value Len = 1 | Value (Time) | INTERVAL_TIME | MTLVF = 16 | 3104 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3105 | Value Len = 1 | Value (Time) | Num Addrs = 5 | ABF = 128 | 3106 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3107 | Head Len = 3 | Head | 3108 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3109 | Mid 0 | Mid 1 | Mid 2 | Mid 3 | 3110 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3111 | Mid 4 | Address TLV Block Length = 14 | LOCAL_IF | 3112 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3113 | ATLVF = 80 | Index = 0 | Value Len = 1 | THIS_IF | 3114 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3115 | LINK_STATUS | ATLV = 52 | Strt Indx = 1 | Stop Indx = 4 | 3116 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3117 | Value Len = 4 | HEARD | HEARD | SYMMETRIC | 3118 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3119 | LOST | 3120 +-+-+-+-+-+-+-+-+ 3122 Note that this example is for illustrative purposes. The essential 3123 information can be conveyed, more efficiently (assuming that the 3124 local interface address will be supplied by IP, and that the 3125 INTERVAL_TIME TLV is not needed) by the 29 octets: 3127 0 1 2 3 3128 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 3129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3130 | 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| 3131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3132 |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| 3133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3134 |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| 3135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3136 |0 0 0 0 0 0 1 1| Head | 3137 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3138 | Mid 1 | Mid 2 | Mid 3 | Mid 4 | 3139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3140 |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| 3141 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3142 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 3143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3144 | LOST | 3145 +-+-+-+-+-+-+-+-+ 3147 Note that the above example assumes that H_HOLD_TIME and C have their 3148 default values of 6 seconds and 1/1024 second, and thus result in a 3149 time code of 100 (hexadecimal 64). 3151 Appendix D. Flow and Congestion Control 3153 This protocol specifies one Message Type, the HELLO message. The 3154 maximum size of a HELLO message is proportional to the size of the 3155 originating router's 1-hop neighborhood. HELLO messages MUST NOT be 3156 forwarded. 3158 A router MUST report its 1-hop neighborhood in HELLO messages on each 3159 of its MANET interfaces at least each REFRESH_INTERVAL. This puts a 3160 lower bound on the control traffic generated by each router in the 3161 network employing this protocol. 3163 A router MUST ensure that two successive HELLO messages sent on the 3164 same MANET interface are separated by at least HELLO_MIN_INTERVAL. 3165 (If using jitter then this may be reduced to a mean minimum value of 3166 HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound 3167 on the control traffic generated by each router in the network 3168 employing this protocol. 3170 Appendix E. Interval and Timer Illustrations 3172 This informative appendix illustrates the relationship between 3173 message timers and intervals. (The adjustments to this timing when 3174 using timing jitter, as defined in [RFC5148], are not shown.) 3176 E.1. HELLO Message Generation Timing 3178 Figure 1 illustrates a basic HELLO message schedule for a router, on 3179 a MANET interface, employing strictly periodic transmission of HELLO 3180 messages. The router transmits a HELLO message each HELLO_INTERVAL. 3181 Each HELLO message contains all 1-hop neighbor network addresses of 3182 the router that are to be reported in any such HELLO message. (The 3183 parameter REFRESH_INTERVAL, not shown, is in this example equal to 3184 the parameter HELLO_INTERVAL.) 3186 The router includes a VALIDITY_TIME TLV in each HELLO message, 3187 encoding the parameter H_HOLD_TIME, the duration for which 3188 information received in the HELLO message should be considered valid 3189 by receiving routers. Receiving routers will, when recording the 3190 information received in the HELLO message, each use this for setting 3191 the L_HEARD_time, L_SYM_time and L_time elements of their 3192 corresponding Link Tuple, and the N2_time in the corresponding 2-Hop 3193 Tuple for each network address. Only L_time is illustrated in 3194 Figure 1. 3196 H_HOLD_TIME: |-----------------------------| ... 3198 HELLO_INTERVAL: |---------|---------|---------| ... 3200 Time: ---*---------*---------*---------*------> 3202 ^ ^ ^ ^ 3203 | | | | 3204 HELLO (a, b, c, d) | | | 3205 | | | 3206 HELLO (a, b, c, d) | | ... 3207 | | 3208 HELLO (a, b, c, d) | 3209 | 3210 HELLO (a, b, c, d) 3212 L_time: |-----------------------------| 3213 |-------------------- ... 3214 |---------- ... 3215 | ... 3217 Figure 1: HELLO message generation: regular schedule 3219 Figure 2 illustrates a message schedule similar to Figure 1, where 3220 the router announces its own presence more frequently by sending 3221 additional HELLO messages. HELLO messages are still sent regularly, 3222 at a reduced interval defined by a new value of HELLO_INTERVAL. 3223 However REFRESH_INTERVAL has not been reduced. Each 1-hop neighbor 3224 network address included in these HELLO messages need be advertised 3225 only once within each REFRESH_INTERVAL. Consequently the additional 3226 HELLO messages due to the reduced value of HELLO_INTERVAL may 3227 therefore be empty. (This is not the only allowed distribution of 3228 1-hop neighbor network addresses, they could, for example, be sent 3229 alternately a, b and c, d.) 3231 H_HOLD_TIME: |-----------------------------| ... 3233 REFRESH_INTERVAL: |---------|---------|---------| ... 3235 HELLO_INTERVAL: |----|----|----|----|----|----| ... 3237 Time: ---*---------*---------*---------*------> 3239 ^ ^ ^ ^ ^ ^ ^ 3240 | | | | | | | 3241 HELLO (a, b, c, d) | | | | | | 3242 | | | | | | 3243 HELLO () | | | | | 3244 | | | | | 3245 HELLO (a, b, c, d) | | | | 3246 | | | | ... 3247 HELLO () | | | 3248 | | | 3249 HELLO (a, b, c, d) | | 3250 | | 3251 HELLO () | 3252 | 3253 HELLO (a, b, c, d) 3255 L_time: |-----------------------------| 3256 |------------------------- ... 3257 |-------------------- ... 3258 |--------------- ... 3259 |---------- ... 3260 |----- ... 3261 | ... 3263 Figure 2: HELLO message generation: regular schedule with different 3264 HELLO_INTERVAL and REFRESH_INTERVAL 3266 HELLO messages may also be sent in response to events. The minimal 3267 interval between two successive HELLO message transmissions by a 3268 router is HELLO_MIN_INTERVAL, setting an upper bound of the HELLO 3269 message emission rate. Hence, for each HELLO message transmission, a 3270 router must wait at least HELLO_MIN_INTERVAL before the next HELLO 3271 message transmission. Similarly, the maximum interval between two 3272 successive HELLO message transmissions is HELLO_INTERVAL, setting a 3273 lower bound on the message transmission rate. Hence, for each HELLO 3274 message transmission, the router must ensure that the next HELLO 3275 message transmission must not wait more than HELLO_INTERVAL. 3277 Figure 3 illustrates a message schedule similar to Figure 1, but with 3278 HELLO messages responding to events at maximum rate, i.e., with HELLO 3279 messages being sent each HELLO_MIN_INTERVAL. Note that when a HELLO 3280 message is sent, it is assumed that the following messages may all be 3281 scheduled at an interval of HELLO_INTERVAL, and hence each HELLO 3282 message contains all 1-hop neighbor network addresses. In each HELLO 3283 message in this example, a new 1-hop neighbor network address is 3284 added, reflecting the changes occurring since the last HELLO message 3285 was sent. HELLO messages are sent at the maximum allowed rate in 3286 order to signal these changes as rapidly as possible. 3288 H_HOLD_TIME: |-----------------------------| ... 3290 HELLO_INTERVAL: |---------|---------|---------| ... 3292 HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... 3294 Time: ---*---------*---------*---------*------> 3296 ^ ^ ^ ^ ^ ^ ^ 3297 | | | | | | | 3298 HELLO () | | | | | | 3299 | | | | | | 3300 HELLO (a) | | | | | 3301 | | | | | 3302 HELLO (a, b) | | | | 3303 | | | | ... 3304 HELLO (a, b, c) | | | 3305 | | | 3306 HELLO (a, b, c, d) | | 3307 | | 3308 HELLO (a, b, c, d, e) | 3309 | 3310 HELLO (a, b, c, d, e, f) 3312 L_time: |-----------------------------| 3313 |------------------------- ... 3314 |-------------------- ... 3315 |--------------- ... 3316 |---------- ... 3317 |----- ... 3318 | ... 3320 Figure 3: HELLO message generation: regular schedule with responsive 3321 messages 3323 Figure 4 shows the same example as Figure 3, but with an increased 3324 REFRESH_INTERVAL, and showing partial HELLO messages which include 3325 only the necessary network addresses. 3327 H_HOLD_TIME: |-----------------------------| ... 3329 REFRESH_INTERVAL: |-------------------|---------- ... 3330 |-------------------|----- ... 3331 |-------------------| ... 3332 |--------------- ... 3333 |---------- ... 3334 |----- ... 3335 | ... 3337 HELLO_INTERVAL: |---------|---------|---------| ... 3339 HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... 3341 Time: ---*---------*---------*---------*------> 3343 ^ ^ ^ ^ ^ ^ ^ 3344 | | | | | | | 3345 HELLO () | | | | | | 3346 | | | | | | 3347 HELLO (a) | | | | | 3348 | | | | | 3349 HELLO (b) | | | | 3350 | | | | ... 3351 HELLO (c) | | | 3352 | | | 3353 HELLO (a, d) | | 3354 | | 3355 HELLO (b, e) | 3356 | 3357 HELLO (c, f) 3359 L_time: |-----------------------------| 3360 |------------------------- ... 3361 |-------------------- ... 3362 |--------------- ... 3363 |---------- ... 3364 |----- ... 3365 | ... 3367 Figure 4: HELLO message generation: regular schedule with responsive 3368 messages and different HELLO_INTERVAL and REFRESH_INTERVAL 3370 Figure 5 summarizes the overall relationship between the intervals 3371 governing HELLO message transmissions by a router. 3373 H_HOLD_TIME: |------------------------------------| 3375 REFRESH_INTERVAL: |----------------| 3377 HELLO_INTERVAL: |----------| 3379 HELLO_MIN_INTERVAL: |---| 3381 Time: -----------------------------------------------> 3383 ^ ^ ^ ^ ^ 3384 | | | | | 3385 | | | | Time up to which 3386 HELLO message | | | received HELLO 3387 transmission | | | message content 3388 | | | is valid. 3389 | | | 3390 | | Time before which all 3391 | | neighbor information must 3392 | | be transmitted in HELLO 3393 | | messages (one or more) 3394 | | 3395 | Latest time for next HELLO message 3396 | transmission 3397 | 3398 Earliest time for next HELLO message 3399 transmission 3401 Figure 5: HELLO message generation intervals 3403 E.2. HELLO Message Processing Timing 3405 Figure 6 illustrates the Link Set timers when receiving a HELLO 3406 message not including the network address of the receiving MANET 3407 interface. 3409 VALIDITY_TIME: |--------------------------| 3411 L_time: |--------------------------| 3413 L_HEARD_time: |--------------------------| 3415 L_SYM_time: *-| (i.e., expired) 3417 Time: ---*--------------------------------> 3418 ^ 3419 | 3420 HELLO () received 3422 Figure 6: HELLO message processing: network address not present 3424 Figure 7 illustrates the Link Set timers when, following the received 3425 HELLO message illustrated in Figure 6, a router receives a HELLO 3426 message including the network address (a) of the receiving interface 3427 with link status = HEARD (or SYM). 3429 VALIDITY_TIME: |--------------------------| 3430 |--------------------------| 3432 L_time: |--------------------------| 3433 |--------------------------| 3435 L_HEARD_time: |--------------------------| 3436 |--------------------------| 3438 L_SYM_time: *-| (i.e., expired) 3439 L_SYM_time: |--------------------------| 3441 Time: -*-----*---------------------------------> 3442 ^ ^ 3443 | | 3444 HELLO () received | 3445 | 3446 HELLO (a:HEARD) received 3448 Figure 7: HELLO message processing: network address present 3450 Figure 8 illustrates the Link Set timers when, following the received 3451 HELLO messages illustrated in Figure 7, a router receives a HELLO 3452 message including the network address (a) of the receiving interface 3453 with link status = LOST. 3455 VALIDITY_TIME: |--------------------------| 3456 |--------------------------| 3457 |--------------------------| 3459 L_time: |--------------------------| 3460 |--------------------------| 3461 |--------------------------| 3463 L_HEARD_time: |--------------------------| 3464 |--------------------------| 3465 |--------------------------| 3467 L_SYM_time: *-| (i.e., expired) 3468 |--------------------------| 3469 *-| (i.e., expired) 3471 Time: -*-----*-----*---------------------------------> 3472 ^ ^ ^ 3473 | | | 3474 HELLO () received | | 3475 | | 3476 HELLO (a:HEARD) received | 3477 | 3478 HELLO (a:LOST) received 3480 Figure 8: HELLO message processing: network address lost 3482 E.3. Other HELLO Message Timing 3484 There are three other timing parameters which are used by a router to 3485 control HELLO message generation and processing. 3487 Figure 9 illustrates the time, with duration L_HOLD_TIME, during 3488 which the appropriate network addresses of a formerly, but no longer, 3489 symmetric 1-hop neighbor, as connected by this MANET interface, are 3490 advertised as LOST using a LINK_STATUS TLV in HELLO messages on this 3491 MANET interface, thus allowing that 1-hop neighbor to update its Link 3492 Set accordingly. 3494 L_HOLD_TIME: |----------------------------| 3496 Time: ---*----------------------------------> 3497 ^ ^ 3498 | | 3499 Formerly symmetric 1-hop neighbor | 3500 ceases to be symmetric on this | 3501 MANET interface | 3502 | 3503 Time up to which network addresses of 3504 this neighbor connected using this MANET 3505 interface are advertised in HELLO 3506 messages on this MANET interface 3507 using a LINK_STATUS TLV, Value = LOST 3509 Figure 9: HELLO message generation: advertisement of formerly 3510 symmetric 1-hop neighbor on this MANET interface as lost 3512 Figure 10 illustrates the time, with duration N_HOLD_TIME, during 3513 which all network addresses of a formerly, but no longer, symmetric 3514 1-hop neighbor, are advertised as LOST in HELLO messages on all MANET 3515 interfaces using an OTHER_NEIGHB TLV (if not also reported using a 3516 LINK_STATUS TLV) thus allowing all other symmetric 1-hop neighbors to 3517 update their 2-Hop Sets accordingly. 3519 L_HOLD_TIME: |----------------------------| 3521 Time: ---*----------------------------------> 3522 ^ ^ 3523 | | 3524 Formerly symmetric 1-hop neighbor | 3525 ceases to be symmetric | 3526 | 3527 Time up to which network addresses of 3528 this neighbor are advertised in HELLO 3529 messages on all MANET interfaces 3530 using an OTHER_NEIGHB TLV, 3531 Value = LOST 3533 Figure 10: HELLO message generation: advertisement of formerly 3534 symmetric 1-hop neighbor on any MANET interface as lost 3536 Figure 11 illustrates the time, with duration I_HOLD_TIME, during 3537 which a formerly, but no longer, used local interface network address 3538 is excluded from being considered as a 2-hop neighbor network address 3539 (in order that a router is not recorded as its own 2-hop neighbor 3540 during that period). 3542 I_HOLD_TIME: |----------------------------| 3544 Time: ---*-----------------------------------> 3545 ^ ^ 3546 | | 3547 Formerly used local interface | 3548 network address ceases to be | 3549 assigned to a local interface | 3550 | 3551 Time up to which this network 3552 address is excluded from being 3553 included in this router's 2-Hop Set 3555 Figure 11: Local interface removed network address 3557 Appendix F. Topology Pictures 3559 This appendix illustrates various examples of physical topologies, as 3560 well as how these are logically recorded by NHDP from the point of 3561 view of the router A. This representation is a composite of 3562 information which would be contained within A's various Information 3563 Bases after NHDP has been running for sufficiently long time for the 3564 state to converge. 3566 Note that the examples given in this appendix are NOT exhaustive, but 3567 are selected to be illustrative of NHDP neighborhood representations 3568 of physical MANET topologies. 3570 The example topologies presented contain 3 physical routers A, B and 3571 C. Each of these routers has one or two distinct interfaces, denoted 3572 "top" and "bottom". Each interface has one or two addresses, and 3573 symmetric connectivity between a pair of interfaces is illustrated by 3574 these being connected by a line. 3576 In all examples, the topology is described as it is recorded by NHDP 3577 in router A. 3579 F.1. Example 1: Standard Single Interface Topology 3581 In Figure 12, each router has a single interface, each with a single 3582 IP address. This is the simplest possible network, and the resulting 3583 representation is given to the right in Figure 12. 3585 __________ __________ 3586 | | | 3587 {1} {2} {3} 3588 | | | {1}--------{2}--------{3} 3589 +--'--+ +--'--+ +--'--+ 3590 | A | | B | | C | 3591 +-----+ +-----+ +-----+ 3593 Figure 12: Standard single interface topology (left), and 3594 corresponding NHDP representation (right) 3596 The Local Information Set in A contains a single Local Interface 3597 Tuple which has an I_local_iface_addr_list of {1}. This value is 3598 denoted with a {1} on the leftmost part of the resulting 3599 representation. 3601 The Interface Information Base has only one Link Set, which 3602 represents the "top" interface of A, or {1}. This Link Set's only 3603 Link Tuple has an L_neighbor_iface_addr_list containing {2}; this 3604 corresponds to the dashed line from {1} to {2} to the right in 3605 Figure 12. The 2-Hop Set contains a single 2-Hop Tuple, with 3606 N2_neighbor_iface_addr_list being {2} and N2_2hop_addr being {3}; 3607 this corresponds to the dashed line from {2} to {3} to the right in 3608 Figure 12. 3610 The descriptions of the following examples in this appendix will be 3611 derived similarly, and use the same notational conventions. 3613 F.2. Example 2: Dual Addressed Interface on 1-Hop Neighbor 3615 In Figure 13, the network is identical to that in Example 1, except 3616 that the middle router, B, has two IP addresses on its single 3617 interface. 3619 __________ __________ 3620 | | | 3621 {1} {2,4} {3} 3622 | | | {1}-------{2,4}-------{3} 3623 +--'--+ +--'--+ +--'--+ 3624 | A | | B | | C | 3625 +-----+ +-----+ +-----+ 3627 Figure 13: Single interfaces, with 1-hop neighbor B having two 3628 addresses (left), and corresponding NHDP representation (right) 3630 The content of the Interface Information Base is in this case 3631 identical to Example 1, except that L_neighbor_iface_addr_list is 3632 {2,4} and N2_neighbor_iface_addr_list is {2,4}. 3634 F.3. Example 3: Dual Addressed Interface on 2-Hop Neighbor 3636 In Figure 14, the network is identical to that in Example 1, except 3637 that the rightmost router, C, has two IP addresses on its interface. 3639 __________ __________ 3640 | | | 3641 {1} {2} {3,4} +----{3} 3642 | | | {1}--------{2}---+ 3643 +--'--+ +--'--+ +--'--+ +----{4} 3644 | A | | B | | C | 3645 +-----+ +-----+ +-----+ 3647 Figure 14: Single interfaces, with 2-hop neighbor C having two 3648 addresses (left), and corresponding NHDP representation (right) 3650 The content of the Interface Information Base is in this case 3651 identical to than in Example 1, except that the 2-Hop Set contains an 3652 extra 2-Hop Tuple with N2_neighbor_iface_addr_list being {2} and 3653 N2_2hop_addr being {4}. These two 2-Hop Tuples are illustrated by 3654 the two lines from {2} to {3} and (2) to {4}, respectively. 3656 F.4. Example 4: Dual Addressed Interfaces 3658 In Figure 15, the network is identical to that in Example 1, except 3659 that all routers have two IP addresses on their interface. The Local 3660 Information Base in router A is the same as in Example 1, except that 3661 I_local_iface_addr_list is {1,5}. 3663 __________ __________ 3664 | | | 3665 {1,5} {2,6} {3,4} +----{3} 3666 | | | {1,5}------{2,6}--+ 3667 +--'--+ +--'--+ +--'--+ +----{4} 3668 | A | | B | | C | 3669 +-----+ +-----+ +-----+ 3671 Figure 15: Single interfaces, all routers having two addresses 3672 (left), and corresponding NHDP representation (right) 3674 The content of the Interface Information Base is in this case a 3675 combination of the Interface Information Bases from Example 1, 3676 Example 2 and Example 3. 3678 F.5. Example 5: Dual Interface on 2-Hop Neighbor 3680 In Figure 16, all routers have a single IP address on each interface, 3681 and with the 2-hop neighbor having two interfaces. 3683 __________ __________ 3684 | | | 3685 {1} {2} {3} +----{3} 3686 | | | {1}--------{2}---+ 3687 +--'--+ +--'--+ +-----+ +----{4} 3688 | A | | B | | C | 3689 +-----+ +-----+ +-----+ 3690 | 3691 {4} 3693 Figure 16: Single addresses, with 2-hop neighbor C having two 3694 interfaces (left), and corresponding NHDP representation (right) 3696 The Interface Information Base is identical to that in Example 3; 3697 NHDP does not distinguish topologically between this example and 3698 Example 3. 3700 F.6. Example 6: Dual interface on 1-Hop Neighbor 3702 In Figure 17, all routers have a single IP address on each interface, 3703 and with the 1-hop neighbor having two interfaces. 3705 __________ 3706 | | 3707 {1} {2} +-----+ 3708 | | {1}-------| {2} |------{4} 3709 +--'--+ +--'--+ +-----+ | {5} | 3710 | A | | B | | C | +-----+ 3711 +-----+ +-----+ +-----+ 3712 | | 3713 {5} {4} 3714 |__________| 3716 Figure 17: Single addresses, with 1-hop neighbor B having two 3717 interfaces (left), and corresponding NHDP representation (right) 3719 The Local Information Base is identical to that in Example 1. 3721 The Interface Information Base has only one Link Set containing one 3722 Link Tuple with L_neighbor_iface_addr_list being {2}. The 2-Hop Set 3723 contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being 3724 {2} and N2_2hop_addr being {4}. 3726 The Neighbor Information Base contains a Neighbor Set containing a 3727 single Neighbor Tuple, which represents router B, with 3728 N_neighbor_addr_list being {2,5}. This entry is represented on the 3729 right of Figure 17 by boxing {2} with {5}. 3731 Note that router A does not have information indicating which of 3732 router B's interfaces is connected to router C. However, router A 3733 knows that the address {4} (and thus router C) is reachable by using 3734 {2} as next hop. 3736 F.7. Example 7: Dual Interface on 1-Hop and 2-Hop Neighbors 3738 In Figure 18, all routers have a single IP address on each interface, 3739 and both the 1-hop and 2-hop neighbors have two interfaces. 3740 Furthermore, there are now two physical links between routers B and 3741 C, over distinct interface pairs. 3743 __________ __________ 3744 | | | 3745 {1} {2} {3} +-----+ +----{3} 3746 | | | {1}-------| {2} |---+ 3747 +--'--+ +--'--+ +-----+ | {5} | +----{4} 3748 | A | | B | | C | +-----+ 3749 +-----+ +-----+ +-----+ 3750 | | 3751 {5} {4} 3752 |__________| 3754 Figure 18: Single addresses, with 1-hop and 2-hop neighbors B and C 3755 having two interfaces (left), and corresponding NHDP representation 3756 (right) 3758 The Local Information Base is identical to that in Example 1. 3760 The Link Set is identical to that in Example 6, and the 2-Hop Set 3761 contains, as in Example 5 (and similarly to Examples 3 and 4), two 3762 2-Hop Tuples representing the two links between routers B and C 3764 Note that router A does not have information describing which of 3765 router B's interfaces is connected to which interfaces of router C, 3766 or even that the interfaces with addresses {3} and {4} are interfaces 3767 of the same router. However, router A knows that the addresses {3} 3768 and {4} (and thus router C) are reachable using {2} as next hop. 3770 F.8. Example 8: Dual Interface Locally and on 1-Hop Neighbor 3772 In Figure 19, all routers have a single IP address on each interface, 3773 and both A and its the 1-hop neighbor B have two interfaces. 3774 Furthermore, there are now two physical links between routers A and 3775 B, over distinct interface pairs. 3777 __________ __________ 3778 | | | +-----+ 3779 {1} {2} {3} {1}-------| {2} |--------{3} 3780 | | | | {5} | 3781 +--'--+ +--'--+ +-----+ +-----+ 3782 | A | | B | | C | 3783 +-----+ +-----+ +-----+ +-----+ 3784 | | | {2} | 3785 {6} {5} {6}-------| {5} |--------{3} 3786 |__________| +-----+ 3788 Figure 19: Single addresses, with both A and 1-hop neighbor B having 3789 two interfaces (left), and corresponding NHDP representation (right) 3791 The Local Information Set contains two Local Interface Tuples, with 3792 I_local_iface_addr_list of {1} and {6}, respectively. 3794 Each Interface Information Base's Link Set contains one Link Tuple, 3795 representing the links between {1} and {2}, and between {6} and {5}, 3796 respectively. The 2-Hop Set for interface {1} contains a single 3797 2-Hop Tuple, with N2_neighbor_iface_addr_list being {2} and 3798 N2_2hop_addr being {3}. The 2-Hop Set for interface {6} contains a 3799 single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {5} and 3800 N2_2hop_addr being {3}. 3802 The Neighbor Information Base contains a Neighbor Set containing a 3803 single Neighbor Tuple, which represents router B, with 3804 N_neighbor_addr_list being {2,5}. This entry is denoted by boxing 3805 {2} with {5}. 3807 F.9. Example 9: Dual Interface on All Routers 3809 In Figure 20, all routers have a single IP address on each interface, 3810 and all routers have two interfaces. Furthermore, there are now two 3811 physical links between A and B, over distinct interface pairs, and 3812 two physical links between B and C, also over distinct interface 3813 pairs. 3815 __________ __________ 3816 | | | +-----+ +----{3} 3817 {1} {2} {3} {1}-------| {2} |---+ 3818 | | | | {5} | +----{4} 3819 +--'--+ +--'--+ +-----+ +-----+ 3820 | A | | B | | C | 3821 +-----+ +-----+ +-----+ +-----+ 3822 | | | | {2} | +----{3} 3823 {6} {5} {4} {6}-------| {5} |---+ 3824 |__________|__________| +-----+ +----{4} 3826 Figure 20: Single addresses, with all routers having two interfaces 3827 (left), and corresponding NHDP representation (right) 3829 The Local Information Set is identical to that in Example 8. The 3830 Interface Information Base for each interface in A is also identical 3831 to that in Example 8, except that an additional 2-Hop Tuple is 3832 present in each 2-Hop Set, each representing the link between router 3833 B and the interface of router C with address {4}. 3835 As in Example 7, router A does not have information describing which 3836 of router B's interfaces is connected to which interface of C, or 3837 even that the interfaces with addresses {3} and {4} are interfaces of 3838 the same router. However, router A knows that the addresses {3} and 3839 {4} (and router C) are reachable by using {2} or {5} (depending on 3840 via which of its local interfaces) as next hop. 3842 F.10. Example 10: Dual Addressed Dual Interfaces on All Routers 3844 In Figure 21, all routers have two IP addresses on each interface, 3845 and all routers have two interfaces. Furthermore, there are now two 3846 physical links between A and B, over distinct interface pairs, and 3847 two physical links between B and C, also over distinct interface 3848 pairs. 3850 +--{9} 3851 __________ __________ +------| 3852 | | | +-----+ | +--{10} 3853 {1,2} {5,6} {9,10} {1,2}--|{5,6}|---+ 3854 | | | |{7,8}| | +--{11} 3855 +--'--+ +--'--+ +-----+ +-----+ +------| 3856 | A | | B | | C | +--{12} 3857 +-----+ +-----+ +-----+ 3858 | | | +--{9} 3859 | | | +-----+ +------| 3860 | | | |{5,6}| | +--{10} 3861 {3,4} {7,8} {11,12} {3,4}--|{7,8}|---+ 3862 |__________|__________| +-----+ | +--{11} 3863 +------| 3864 +--{12} 3866 Figure 21: Dual addresses, with all routers having two interfaces 3867 (left) and corresponding NHDP representation (right) 3869 This example is the combination of all the preceding examples in this 3870 appendix. The Local Information Set in A contains Local Information 3871 Tuples for each of its interfaces, and each Interface Information 3872 Base contains in its Link Set a representation of links {1,2}-{5,6} 3873 or {3,4}-{7,8}, respectively. The Neighbor Set (in the Neighbor 3874 Information Base) records the existence of router B and all of its 3875 addresses on all its interfaces, i.e., {5,6,7,8}. 3877 As in Example 9, each interface address of router C is represented in 3878 the 2-Hop Set of each Interface Information Base as a link from 3879 router B to each of these addresses. Router A does not have 3880 information describing which of router B's interfaces is connected to 3881 which interface of C, nor that the addresses {9}, {10}, {11}, and 3882 {12} are addresses of the same router (or that some of these, such as 3883 {9} and {10}, are addresses on the same interface of the router). 3885 F.11. Example 11: Single Addressed Dual Interface Locally 3887 In Figure 22, all routers have a single interface, except for router 3888 A which has two. Each of A's two interfaces has a link with the 3889 single interface of router B. All interfaces have a single address. 3891 __________ __________ 3892 | _____| | 3893 {1} | {2} {3} {1}--------{2}---------{3} 3894 | | | | 3895 +--'--+ | +--'--+ +-----+ 3896 | A | | | B | | C | 3897 +-----+ | +-----+ +-----+ 3898 | | 3899 {6} | {6}--------{2}---------{3} 3900 |____| 3902 Figure 22: Single addresses, with A having two interfaces, both 3903 linked to the single interface of B (left), and corresponding NHDP 3904 representation (right) 3906 This is similar to Example 8, except that the single address {2} also 3907 replaces the address {5}. In particular both Link Tuples (one in 3908 each Link Set, each in its corresponding Interface Information Base) 3909 have L_neighbor_iface_addr_list being {2}, the Neighbor Set (in the 3910 Neighbor Information Base) contains a single Neighbor Tuple with 3911 N_neighbor_addr_list being {2}, and both 2-Hop Tuples (one in each 3912 2-Hop Set, each in its corresponding Interface Information Base) have 3913 N2_neighbor_iface_addr_list being {2} and N2_2hop_addr being {3}. 3915 Authors' Addresses 3917 Thomas Heide Clausen 3918 LIX, Ecole Polytechnique 3920 Phone: +33 6 6058 9349 3921 EMail: T.Clausen@computer.org 3922 URI: http://www.ThomasClausen.org/ 3924 Christopher Dearlove 3925 BAE Systems ATC 3927 Phone: +44 1245 242194 3928 EMail: chris.dearlove@baesystems.com 3929 URI: http://www.baesystems.com/ 3931 Justin W. Dean 3932 Naval Research Laboratory 3934 Phone: +1 202 767 3397 3935 EMail: jdean@itd.nrl.navy.mil 3936 URI: http://pf.itd.nrl.navy.mil/ 3938 The OLSRv2 Design Team 3939 MANET Working Group