idnits 2.17.1 draft-ietf-manet-nhdp-11.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 1079 has weird spacing: '...dr_list is an...' == Line 1082 has weird spacing: '...I_manet is a ...' == Line 1102 has weird spacing: '...ce_addr is a ...' == Line 1105 has weird spacing: '...IR_time speci...' == Line 1140 has weird spacing: '...dr_list is an...' == (13 more instances...) -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 26, 2009) is 5296 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Informational RFC: RFC 5148 Summary: 2 errors (**), 0 flaws (~~), 7 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique 4 Intended status: Standards Track C. Dearlove 5 Expires: April 29, 2010 BAE Systems ATC 6 J. Dean 7 Naval Research Laboratory 8 The OLSRv2 Design Team 9 MANET Working Group 10 October 26, 2009 12 Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP) 13 draft-ietf-manet-nhdp-11 15 Status of This Memo 17 This Internet-Draft is submitted to IETF in full conformance with the 18 provisions of BCP 78 and BCP 79. This document may contain material 19 from IETF Documents or IETF Contributions published or made publicly 20 available before November 10, 2008. The person(s) controlling the 21 copyright in some of this material may not have granted the IETF 22 Trust the right to allow modifications of such material outside the 23 IETF Standards Process. Without obtaining an adequate license from 24 the person(s) controlling the copyright in such materials, this 25 document may not be modified outside the IETF Standards Process, and 26 derivative works of it may not be created outside the IETF Standards 27 Process, except to format it for publication as an RFC or to 28 translate it into languages other than English. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF), its areas, and its working groups. Note that 32 other groups may also distribute working documents as Internet- 33 Drafts. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 The list of current Internet-Drafts can be accessed at 41 http://www.ietf.org/ietf/1id-abstracts.txt. 43 The list of Internet-Draft Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html. 46 This Internet-Draft will expire on April 29, 2010. 48 Copyright Notice 49 Copyright (c) 2009 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents in effect on the date of 54 publication of this document (http://trustee.ietf.org/license-info). 55 Please review these documents carefully, as they describe your rights 56 and restrictions with respect to this document. 58 Abstract 60 This document describes a 1-hop and symmetric 2-hop neighborhood 61 discovery protocol (NHDP) for mobile ad hoc networks (MANETs). 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 66 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 68 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 69 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 10 70 4.1. Routers and Interfaces . . . . . . . . . . . . . . . . . . 11 71 4.2. Information Base Overview . . . . . . . . . . . . . . . . 12 72 4.2.1. Local Information Base . . . . . . . . . . . . . . . . 12 73 4.2.2. Interface Information Bases . . . . . . . . . . . . . 13 74 4.2.3. Neighbor Information Base . . . . . . . . . . . . . . 13 75 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 14 76 4.3.1. HELLO Message Generation . . . . . . . . . . . . . . . 15 77 4.3.2. HELLO Message Content . . . . . . . . . . . . . . . . 15 78 4.3.3. HELLO Message Processing . . . . . . . . . . . . . . . 16 79 4.4. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 17 80 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 17 81 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 17 82 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 17 83 5.3. Interface Parameters . . . . . . . . . . . . . . . . . . . 17 84 5.3.1. Message Intervals . . . . . . . . . . . . . . . . . . 18 85 5.3.2. Information Validity Times . . . . . . . . . . . . . . 19 86 5.3.3. Link Quality . . . . . . . . . . . . . . . . . . . . . 20 87 5.3.4. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 20 88 5.4. Router Parameters . . . . . . . . . . . . . . . . . . . . 21 89 5.4.1. Information Validity Time . . . . . . . . . . . . . . 21 90 5.5. Parameter Change Constraints . . . . . . . . . . . . . . . 21 91 5.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 22 92 6. Local Information Base . . . . . . . . . . . . . . . . . . . . 23 93 6.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 23 94 6.2. Removed Interface Address Set . . . . . . . . . . . . . . 24 95 7. Interface Information Base . . . . . . . . . . . . . . . . . . 24 96 7.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 25 97 7.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 26 98 8. Neighbor Information Base . . . . . . . . . . . . . . . . . . 26 99 8.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . 26 100 8.2. Lost Neighbor Set . . . . . . . . . . . . . . . . . . . . 27 101 9. Local Information Base Changes . . . . . . . . . . . . . . . . 27 102 9.1. Adding an Interface . . . . . . . . . . . . . . . . . . . 27 103 9.2. Removing an Interface . . . . . . . . . . . . . . . . . . 28 104 9.3. Adding a Network Address to an Interface . . . . . . . . . 28 105 9.4. Removing a Network Address from an Interface . . . . . . . 29 106 10. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 30 107 10.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 30 108 10.1.1. Address Blocks . . . . . . . . . . . . . . . . . . . . 31 109 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 32 110 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 33 111 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 35 112 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 35 113 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 35 114 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 36 115 12.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 37 116 12.3. Updating the Neighbor Set . . . . . . . . . . . . . . . . 38 117 12.4. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 40 118 12.5. Updating the Link Set . . . . . . . . . . . . . . . . . . 40 119 12.6. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 42 120 13. Other Information Base Changes . . . . . . . . . . . . . . . . 43 121 13.1. Link Tuple Symmetric . . . . . . . . . . . . . . . . . . . 44 122 13.2. Link Tuple Not Symmetric . . . . . . . . . . . . . . . . . 44 123 13.3. Link Tuple Heard Timeout . . . . . . . . . . . . . . . . . 45 124 14. Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . 45 125 14.1. Deployment Without Link Quality . . . . . . . . . . . . . 46 126 14.2. Basic Principles of Link Quality . . . . . . . . . . . . . 46 127 14.3. When Link Quality Changes . . . . . . . . . . . . . . . . 47 128 14.4. Updating Link Quality . . . . . . . . . . . . . . . . . . 48 129 15. Proposed Values for Parameters and Constants . . . . . . . . . 48 130 15.1. Message Interval Interface Parameters . . . . . . . . . . 48 131 15.2. Information Validity Time Interface Parameters . . . . . . 49 132 15.3. Information Validity Time Router Parameters . . . . . . . 49 133 15.4. Link Quality Interface Parameters . . . . . . . . . . . . 49 134 15.5. Jitter Interface Parameters . . . . . . . . . . . . . . . 49 135 15.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 49 136 16. Usage with Other Protocols . . . . . . . . . . . . . . . . . . 49 137 17. Security Considerations . . . . . . . . . . . . . . . . . . . 51 138 17.1. Invalid HELLO messages . . . . . . . . . . . . . . . . . . 53 139 17.2. Authentication, Integrity and Confidentiality 140 Suggestions . . . . . . . . . . . . . . . . . . . . . . . 54 141 18. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 54 142 18.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 55 143 18.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 55 144 18.3. Message-Type-specific TLV Type Registries . . . . . . . . 55 145 18.4. Address Block TLV Types . . . . . . . . . . . . . . . . . 56 146 18.5. LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Values . . . . . . 57 147 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 57 148 20. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 58 149 21. References . . . . . . . . . . . . . . . . . . . . . . . . . . 58 150 21.1. Normative References . . . . . . . . . . . . . . . . . . . 58 151 21.2. Informative References . . . . . . . . . . . . . . . . . . 58 152 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 59 153 Appendix B. Constraints . . . . . . . . . . . . . . . . . . . . . 60 154 Appendix C. HELLO Message Example . . . . . . . . . . . . . . . . 63 155 Appendix D. Flow and Congestion Control . . . . . . . . . . . . . 65 156 Appendix E. Interval and Timer Illustrations . . . . . . . . . . 66 157 E.1. HELLO Message Generation Timing . . . . . . . . . . . . . 66 158 E.2. HELLO Message Processing Timing . . . . . . . . . . . . . 72 159 E.3. Other HELLO Message Timing . . . . . . . . . . . . . . . . 73 160 Appendix F. Topology Pictures . . . . . . . . . . . . . . . . . . 75 161 F.1. Example 1: Standard Single Interface Topology . . . . . . 75 162 F.2. Example 2: Dual Addressed Interface on One Hop Neighbor . 76 163 F.3. Example 3: Dual Addressed Interface on Two Hop Neighbor . 77 164 F.4. Example 4: Dual Addressed Interfaces . . . . . . . . . . . 77 165 F.5. Example 5: Dual Interface on Two Hop Neighbor . . . . . . 78 166 F.6. Example 6: Dual interface on One Hop Neighbor . . . . . . 78 167 F.7. Example 7: Dual Interface on One and Two Hop Neighbors . . 79 168 F.8. Example 8: Dual Interface Locally and on One Hop 169 Neighbor . . . . . . . . . . . . . . . . . . . . . . . . . 80 170 F.9. Example 9: Dual Interface on All Routers . . . . . . . . . 80 171 F.10. Example 10: Dual Addressed Dual Interfaces on All 172 Routers . . . . . . . . . . . . . . . . . . . . . . . . . 81 173 F.11. Example 11: Single Addressed Dual Interface Locally . . . 82 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 and symmetric 2-hop neighborhood information is recorded in the 185 form of Information Bases. These are available for use by other 186 protocols, such as MANET routing protocols, which require information 187 regarding the local network connectivity. This protocol is designed 188 to maintain the information in these Information Bases even in the 189 presence of a dynamic network topology and wireless communication 190 channel characteristics. 192 This protocol makes no assumptions about the underlying link layer, 193 other than support of local broadcast or multicast for communication 194 to 1-hop neighbor routers. Link layer information may be used if 195 available and applicable. 197 This protocol is based on the neighborhood discovery process 198 contained in the Optimized Link State Routing Protocol (OLSR) 199 [RFC3626]. 201 1.1. Motivation 203 MANETs differ from more traditional wired and infrastructure-based 204 wireless networks, due to their envisioned applicability also over 205 more challenging communication channels (e.g., wireless, lossy, 206 broadcast channels with moderate and shared bandwidth, hidden and 207 exposed terminals and interference from other network devices and the 208 environment) and in more challenging topological conditions (e.g., 209 rapid and unpredictable mobility, dynamic and non-predetermined 210 network membership). 212 Due to the properties of wireless transmissions, communication 213 between two neighboring routers may not be bi-directional; even if 214 router A is able to receive packets from router B, the converse is 215 not guaranteed to be true. Furthermore, because of the localized 216 nature of wireless broadcast communication, neighboring routers 217 within the same communications channel may have different sets of 218 neighbors. That is, when using the same communication channel, even 219 if router A is able to exchange packets with router B and router B is 220 able to exchange packets with router C, then this does not guarantee 221 that router A and router C can exchange packets directly. 223 Each router in a MANET may use more than one communication channel. 224 In particular, between the same pair of routers, more than one 225 distinct communication channel may exist, each with different 226 properties. This may, for example, be the case where MANET routers 227 are equipped with multiple distinct wireless interfaces, operating at 228 different frequencies. 230 For use by MANET routing protocols, as well as for establishing a 231 router's neighbors, a router may also need to determine whether each 232 communication channel with that neighbor is bi-directional. 234 The set of neighbor routers of a given MANET router may be 235 continuously changing, often due to router mobility or a changing 236 physical environment in which the MANET is located. There is 237 typically no information from lower layers which would enable an IP 238 routing protocol to detect and, as appropriate, react to such 239 changes. Such changes can often take place on a short timescale, 240 such as of the order of seconds, requiring MANET routing protocols to 241 act rapidly to ensure suitable convergence properties. 243 MANET routing protocols, for example [RFC3626] and [RFC5449], often 244 employ relay set reductions in order to conserve network capacity 245 when maintaining network-wide topological information, with 246 calculation of these reduced relay sets employing up to two hop 247 information. 249 The neighborhood discovery protocol specified in this document 250 provides continued tracking of neighborhood changes, link bi- 251 directionality, and local topological information up to two hops. 252 Combined, this allows a MANET routing protocol access to information 253 describing link establishment/disappearance, and provides the 254 necessary topological information for reduced relay set selection and 255 other purposes. 257 2. Terminology 259 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 260 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 261 "OPTIONAL" in this document are to be interpreted as described in 262 [RFC2119]. 264 All terms introduced in [RFC5444], including "packet", "message", 265 "Address Block", "TLV Block", "TLV", "address", "address prefix", and 266 "address object" are to be interpreted as described therein. 268 Additionally, this document uses the following terminology: 270 Network Address An address plus an associated prefix length. This 271 may be an address with an associated maximum prefix length, or an 272 address prefix including a prefix length. 274 Router - A MANET router which implements this neighborhood discovery 275 protocol. 277 Interface - A network device, configured and assigned one or more 278 addresses. 280 MANET interface - An interface participating in a MANET and using 281 this neighborhood discovery protocol. A router may have several 282 MANET interfaces. 284 Heard - A MANET interface of router X is considered heard on a MANET 285 interface of a router Y if the latter can receive traffic from the 286 former. 288 Link - A link between two MANET interfaces exists if either can be 289 heard by the other. 291 Symmetric link - A symmetric link between two MANET interfaces 292 exists if both can be heard by the other. 294 1-hop neighbor - A router X is a 1-hop neighbor of a router Y if a 295 MANET interface of router X is heard by a MANET interface of 296 router Y. 298 Symmetric 1-hop neighbor - A router X is a symmetric 1-hop neighbor 299 of a router Y if a symmetric link exists between a MANET interface 300 on router X and a MANET interface on router Y. 302 2-hop neighbor - A router X is a 2-hop neighbor of a router Y if 303 router X is a 1-hop neighbor of a 1-hop neighbor of router Y, but 304 is not router Y itself. 306 Symmetric 2-hop neighbor - A router X is a symmetric 2-hop neighbor 307 of a router Y if router X is a symmetric 1-hop neighbor of a 308 symmetric 1-hop neighbor of router Y, but is not router Y itself. 310 1-hop neighborhood - The 1-hop neighborhood of a router X is the set 311 of the 1-hop neighbors of router X. 313 Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a 314 router X is the set of the symmetric 1-hop neighbors of router X. 316 2-hop neighborhood - The 2-hop neighborhood of a router X is the set 317 of the 2-hop neighbors of router X. (This may include routers in 318 the 1-hop neighborhood of router X.) 320 Symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of a 321 router X is the set of the symmetric 2-hop neighbors of router X. 322 (This may include routers in the 1-hop neighborhood, or even in 323 the symmetric 1-hop neighborhood, of router X.) 325 Constant - A numerical value which MUST be the same for all MANET 326 interfaces of all routers in the MANET, at all times. 328 Interface parameter - A boolean or numerical value, specified 329 separately for each MANET interface of each router. A router MAY 330 change interface parameter values at any time, subject to some 331 constraints. 333 Router parameter - A boolean or numerical value, specified for each 334 router, and not specific to an interface. A router MAY change 335 router parameter values at any time, subject to some constraints. 337 Information Base - A collection of information maintained by this 338 protocol, and which is to be made available to MANET routing 339 protocols. An Information Base may be associated with a MANET 340 interface, or with a router. 342 Furthermore, this document uses the following notational conventions: 344 X contains y, or y is contained in X, is an unordered list 345 membership operator, returning true if the unordered list X 346 includes the element y, and returning false otherwise. 348 X contains Y, or Y is contained in X, is an unordered list inclusion 349 operator, returning true if the unordered list X contains all 350 elements y which are contained in Y, and returning false 351 otherwise. 353 A overlaps B if A and B are network addresses, and the range of 354 network addresses represented by A, and the range of network 355 addresses represented by B both contain at least one common 356 network address. (This is only possible if one range is a sub- 357 range of the other.) 359 a := b is an assignment operator, whereby the left side (a) is 360 assigned the value of the right side (b). a and b may be values, 361 network addresses, or unordered lists (they must be of the same 362 type). 364 c = d is a comparison operator, returning true if the value of the 365 left side (c) is equal to the value of the right side (d). c and d 366 may be values, network addresses, or unordered lists (they must be 367 of the same type). If c and d are unordered lists, then they are 368 considered to be equal if they contain the same set of elements, 369 regardless of the order in which they are recorded in either list 370 (in which case c contains d, and d contains c). If c and d are 371 network addresses, they are considered equal only if both 372 addresses and prefix lengths are equal. 374 e != f is a comparison operator, returning true where (e = f) would 375 have returned false, and returning false where (e = f) would have 376 returned true. 378 3. Applicability Statement 380 This protocol: 382 o Is applicable to networks, especially wireless networks, in which 383 unknown neighbors can be reached by local broadcast or multicast 384 packets. 386 o Is designed to work in networks with a dynamic topology, and in 387 which messages may be lost, such as due to collisions in wireless 388 networks. 390 o Supports routers that each have one or more participating MANET 391 interfaces. The set of a router's interfaces may change over 392 time. Each interface may have one or more associated network 393 addresses, and these may also be dynamically changing. 395 o Provides each router with current local topology information up to 396 two hops away, and makes this local topology information available 397 to MANET routing protocols in Information Bases. 399 o Uses the packet and message formats specified in [RFC5444]. This 400 includes the definition of a HELLO Message Type, used for 401 signaling local topology information. 403 o Allows "external" and "internal" extensibility as enabled by 404 [RFC5444]. 406 o May interact with, and be extended by, other protocols, such as 407 MANET routing protocols, see Section 16. 409 o Can use relevant link layer information if it is available. 411 o Is designed to work in a completely distributed manner, and does 412 not depend on any central entity. 414 4. Protocol Overview and Functioning 416 The objective of this protocol is, for each router: 418 o To identify 1-hop neighbors and symmetric 1-hop neighbors of this 419 router. 421 o To find the interface network addresses of the router's symmetric 422 2-hop neighbors. 424 o To record this information in Information Bases and thus make this 425 information available to other protocols that use this 426 neighborhood discovery protocol. 428 o To be available for use by other protocols, which MAY extend the 429 information in these Information Bases, including adding new Sets 430 to Information Bases, new elements to protocol Tuples and new TLVs 431 to be included in outgoing HELLO messages and processed when in 432 incoming HELLO messages. 434 These objectives are achieved using local (1-hop) signaling that: 436 o Advertises the presence of a router and its interface network 437 addresses. 439 o Discovers links from neighboring routers. 441 o Performs bi-directionality checks on the discovered links. 443 o Advertises discovered links, and whether each is symmetric, to its 444 1-hop neighbors, and hence discovers symmetric 2-hop neighbors. 446 This specification defines, in turn: 448 o Parameters and constants used by the protocol. Parameters used by 449 this protocol may, where appropriate, be specific to a given MANET 450 interface, or to a MANET router. This protocol allows all 451 parameters to be changed dynamically, and to be set independently 452 for each MANET router or MANET interface, as appropriate. 454 o The Information Bases describing local interfaces, discovered 455 links and their status, current and former 1-hop neighbors, and 456 symmetric 2-hop neighbors. 458 o The format of the HELLO message that is used for local signaling. 460 o The generation of HELLO messages from some of the information in 461 the Information Bases. 463 o The updating of the Information Bases according to received HELLO 464 messages and other events. 466 o The response to other events, such as the expiration of 467 information in the Information Bases. 469 4.1. Routers and Interfaces 471 In order for a router to participate in a MANET, it MUST have at 472 least one, and possibly more, MANET interfaces. 474 Each MANET interface: 476 o Is configured with one or more network addresses. All addresses 477 represented by these network addresses MUST be unique to this 478 router at least within its 2-hop neighborhood. All such addresses 479 MUST be unique to this MANET interface, except that an address can 480 be used by more than one MANET interface on the same router if 481 those MANET interfaces are "isolated" from each other (no MANET 482 interface on another router can hear or be heard by two MANET 483 interfaces using overlapping network addresses). 485 o Has a set of interface parameters, defining the behavior of this 486 MANET interface. Each MANET interface MAY be individually 487 parameterized. 489 o Has an Interface Information Base, recording information regarding 490 links to this MANET interface and symmetric 2-hop neighbors which 491 can be reached through such links. 493 o Generates and processes HELLO messages. 495 In addition to a set of MANET interfaces as described above, each 496 router has: 498 o A Local Information Base, containing the network addresses of the 499 interfaces (MANET and non-MANET) of this router. The contents of 500 this Information Base are not changed by signaling. 502 o A Neighbor Information Base, recording information regarding 503 current and recently lost 1-hop neighbors of this router. 505 A router may have both MANET interfaces and non-MANET interfaces. 507 Interfaces of both of these types are recorded in a router's Local 508 Information Base, which is used, but not updated, by the signaling of 509 this protocol. 511 4.2. Information Base Overview 513 Each router maintains the Information Bases described in the 514 following sections. These are used for describing the protocol in 515 this document. An implementation of this protocol MAY maintain this 516 information in the indicated form, or in any other organization which 517 offers access to this information. In particular, note that it is 518 not necessary to remove Tuples from Sets at the exact time indicated, 519 only to behave as if the Tuples were removed at that time. 521 Information in the Local Information Base is defined locally, and 522 included in HELLO messages. Information in the Interface Information 523 Base and the Neighbor Information Base is determined from received 524 HELLO messages; some of this information may also be included in 525 transmitted HELLO messages. Such information has a limited duration 526 in which it is considered valid. This duration is determined from 527 the VALIDITY_TIME TLV in the HELLO message in which the information 528 is received, which in turn is set by the router that originated the 529 HELLO message, using its corresponding interface parameter 530 H_HOLD_TIME. 532 Appendix E illustrates the relationship between message reception, 533 included VALIDITY_TIME TLVs, and the duration for which information 534 received in a HELLO message is considered valid. Appendix F 535 illustrates some example two hop topologies and how they correspond 536 to information in the Information Bases. 538 4.2.1. Local Information Base 540 Each router maintains a Local Information Base, which contains the 541 router's local configuration information, specifically: 543 o The Local Interface Set, which consists of Local Interface Tuples, 544 each of which represents an interface (MANET or non-MANET) of the 545 router. 547 o The Removed Interface Address Set, which consists of Removed 548 Interface Address Tuples, each of which records a recently used 549 network address of an interface (MANET or non-MANET) of the 550 router. 552 The Local Interface Set is used for generating HELLO messages, 553 specifically for determining which interface network addresses are to 554 be included and identified as local interfaces. The Removed 555 Interface Address Set is used to avoid incorrectly recording a 556 formerly used network address as a symmetric 2-hop neighbor's network 557 address. 559 The Local Information Base is used for generating signaling, but is 560 not itself updated by signaling specified in this document. Updates 561 to the Local Information Base are due to changes of the router 562 configuration, and may be allowed to trigger signaling. 564 4.2.2. Interface Information Bases 566 Each router maintains, for each of its MANET interfaces, an Interface 567 Information Base, which contains 1-hop neighborhood and symmetric 568 2-hop neighborhood information collected from this MANET interface, 569 specifically: 571 o A Link Set, which records information about current and recently 572 lost links between this MANET interface and MANET interfaces of 573 1-hop neighbors. The Link Set consists of Link Tuples, each of 574 which contains information about a single link. Link quality 575 information (see Section 14), when used, is recorded in Link 576 Tuples. 578 o A 2-Hop Set, which records the existence of symmetric links 579 between symmetric 1-hop neighbors of this MANET interface and 580 other routers (symmetric 2-hop neighbors). The 2-Hop Set consists 581 of 2-Hop Tuples, each of which records a network address of a 582 symmetric 2-hop neighbor, and all network addresses of the 583 corresponding symmetric 1-hop neighbor. 585 The Link Set for a MANET interface is used for generating HELLO 586 messages. Specifically, the Link Set information is included to both 587 allow other routers to identify symmetric links and to populate the 588 2-Hop Set. Recently lost links are recorded in the Link Set for a 589 MANET interface so that they can be advertised in HELLO messages, 590 accelerating their removal from relevant 1-hop neighbors' Link Sets. 592 The Link Set for a MANET interface is itself updated on receiving a 593 HELLO message, including recording symmetric links as indicated 594 above. The 2-Hop Set for a MANET interface is updated as indicated 595 above, and is not itself used in generating HELLO messages. 597 4.2.3. Neighbor Information Base 599 Each router maintains a Neighbor Information Base, which contains 600 collected information about current and recently lost 1-hop 601 neighbors, specifically: 603 o The Neighbor Set consists of Neighbor Tuples, each of which 604 records all network addresses of a single 1-hop neighbor. 605 Neighbor Tuples are maintained as long as there are corresponding 606 Link Tuples. 608 o The Lost Neighbor Set consists of Lost Neighbor Tuples, each of 609 which records a network address of a recently lost symmetric 1-hop 610 neighbor. 612 The Neighbor Set associates all network addresses of each 1-hop 613 neighbor. These network addresses may be included when generating a 614 HELLO message, so that other symmetric 1-hop neighbors can record 615 this information in a 2-Hop Set. The Neighbor Set can be updated on 616 receiving a HELLO message. 618 The Lost Neighbor Set is used to determine which network addresses 619 are to be included in a HELLO message as being lost (of a recently 620 symmetric 1-hop neighbor). The Lost Neighbor Set can itself be 621 updated on receiving a HELLO message. 623 4.3. Signaling Overview 625 This protocol contains a signaling mechanism for maintaining the 626 Interface Information Bases and the Neighbor Information Base. If 627 information from the link layer, or any other source, is available 628 and appropriate, it may also be used to update these Information 629 Bases. Such updates are subject to the constraints specified in 630 Appendix B. 632 Signaling consists of a single type of message, known as a HELLO 633 message. Each router generates HELLO messages on each of its MANET 634 interfaces. HELLO messages are generated independently on each MANET 635 interface of a MANET router; the content of a given HELLO message 636 depends on the MANET interface for which it has been generated. 638 Each HELLO message: 640 o Identifies, as far as is required, the MANET interface for which 641 it is generated and transmitted; this allows recipients of that 642 HELLO message to identify that MANET interface from among those it 643 may hear. 645 o Reports the network addresses of other interfaces (MANET and non- 646 MANET) of the router; this allows recipients of that HELLO message 647 to associate a set of network addresses with a single 1-hop 648 neighbor. 650 o Includes 1-hop neighbor information from the Information Bases; 651 this allows detection of local symmetric links, and symmetric 652 2-hop neighbors. 654 HELLO message generation, and the validity of the information 655 recorded as a consequence of processing a HELLO message, is affected 656 by timers and validity information included in HELLO messages through 657 TLVs. The relationship between message timers and intervals is 658 illustrated in Appendix E. 660 4.3.1. HELLO Message Generation 662 HELLO messages are generated by a router for each of its MANET 663 interfaces, and MAY be sent: 665 o Proactively, at a regular interval, known as HELLO_INTERVAL. 666 HELLO_INTERVAL may be fixed, or may be dynamic. For example 667 HELLO_INTERVAL may be backed off due to congestion or network 668 stability. 670 o As a response to a change in the router itself, or its 1-hop 671 neighborhood, for example on first becoming active or in response 672 to a new, lost, or changed status link. 674 o In a combination of these proactive and responsive mechanisms. 676 Jittering of HELLO message generation and transmission, as described 677 in Section 11.2, SHOULD be used if appropriate. 679 HELLO messages MAY be scheduled independently for each MANET 680 interface, or, interface parameters permitting, using the same 681 schedule for all MANET interfaces of a router. 683 4.3.2. HELLO Message Content 685 The content of a HELLO message MUST satisfy the following: 687 o A HELLO message MUST contain all of the network addresses in the 688 Local Interface Set of the router on which the HELLO message is 689 being generated. This includes: 691 * At least one network address of each MANET interface of the 692 router. 694 * Network addresses that include all source addresses of any IP 695 datagrams sent by the router on any MANET interface. 697 * All other network addresses of the router which are to be made 698 known to any other router for any reason. 700 o For each MANET interface, within every time interval equal to the 701 corresponding REFRESH_INTERVAL, sent HELLO messages MUST 702 collectively include all of the relevant information in the 703 corresponding Link Set and the Neighbor Information Base. Note 704 that when determining whether to include information in a HELLO 705 message, the sender MUST consider all times up to the latest time 706 when it may send its next HELLO message on this MANET interface. 708 o A HELLO message MUST include exactly one VALIDITY_TIME Message 709 TLV, as specified in [RFC5497], that indicates the length of time 710 for which the message content is to be considered valid, and is 711 therefore to be included in the receiving router's Interface 712 Information Base. 714 o A periodically generated HELLO message SHOULD include exactly one 715 INTERVAL_TIME Message TLV, as specified in [RFC5497], that 716 indicates the current value of HELLO_INTERVAL for that MANET 717 interface, i.e. the period within which a further HELLO message is 718 guaranteed to be sent on that MANET interface. 720 4.3.3. HELLO Message Processing 722 HELLO messages received by a router are used to update the Interface 723 Information Base for the MANET interface over which that HELLO 724 message was received, as well as the Neighbor Information Base of the 725 router. Specifically: 727 o The router ensures that there is a single Neighbor Tuple 728 corresponding to the originator of that HELLO message. 730 o The router ensures that there is a Link Tuple, with appropriate 731 status (heard or symmetric) and advertised duration, corresponding 732 to the link between the MANET interfaces on which that HELLO 733 message was sent and received. One or more Lost Neighbor Tuples 734 may be created if the HELLO message reports that the link was 735 lost. 737 o If the link between the MANET interfaces on which the HELLO 738 message was sent and received is symmetric, then the router 739 ensures that there are the appropriate 2-Hop Tuples, with 740 advertised duration. 742 The processing defined in this specification handles any unexpected 743 and erroneous information in a HELLO message, maintaining the 744 constraints on Information Base contents specified in Appendix B. 746 4.4. Link Quality 748 Some links in a MANET may be marginal, e.g., due to adverse wireless 749 propagation. In order to avoid using such marginal links, a link 750 quality value is recorded in each Link Tuple. A MANET router 751 considers links for which an insufficient link quality is recorded as 752 lost. Modifying the recorded link quality in a Link Tuple is 753 OPTIONAL. If link quality is not to be modified it MUST be set to 754 indicate an always usable quality link. 756 Note that Link Quality is a "link admittance" mechanism, allowing a 757 router to determine that a given link is too unstable to even 758 consider for use. It is specifically not a link metric nor a 759 substitute for one. 761 Link quality information is only used locally and is not used in 762 signaling. Routers may interoperate whether they are using the same, 763 different, or no, link quality information. Link quality information 764 is thus not equivalent to a link metric. 766 5. Protocol Parameters and Constants 768 The parameters and constants used in this specification are described 769 in this section. 771 5.1. Protocol and Port Numbers 773 This protocol specifies HELLO messages, which are included in packets 774 as defined by [RFC5444]. These packets may be sent either using the 775 "manet" protocol number or the "manet" well-known UDP port number, as 776 specified in [RFC5498]. 778 5.2. Multicast Address 780 This protocol specifies HELLO messages, which are included in packets 781 as defined by [RFC5444]. These packets may be locally transmitted 782 using the link local multicast address "LL-MANET-Routers", as 783 specified in [RFC5498]. 785 5.3. Interface Parameters 787 The interface parameters used by this specification may be classified 788 into the following four categories: 790 o Message intervals 792 o Information validity times 793 o Link quality 795 o Jitter 797 These are detailed in the following sections. 799 Different MANET interfaces (on the same or on different routers) MAY 800 employ different interface parameter values, and MAY change their 801 interface parameter values dynamically, subject to the constraints 802 given in this section. A particular case is where all MANET 803 interfaces on all MANET routers within a given MANET employ the same 804 set of interface parameter values. 806 5.3.1. Message Intervals 808 HELLO messages serve two principal functions: 810 o To advertise network addresses of this router's interface to its 811 1-hop neighbors. The frequency of these advertisements is 812 regulated by the interface parameters HELLO_INTERVAL and 813 HELLO_MIN_INTERVAL. 815 o To advertise this router's knowledge of each of its 1-hop 816 neighbors. The frequency of the advertisement of each such 817 neighbor is regulated by the interface parameter REFRESH_INTERVAL. 819 Specifically, these parameters are as follows: 821 HELLO_INTERVAL - is the maximum time between the transmission of two 822 successive HELLO messages on this MANET interface. If using 823 periodic transmission of HELLO messages, these SHOULD be at a 824 separation of HELLO_INTERVAL, possibly modified by jitter as 825 specified in [RFC5148]. 827 HELLO_MIN_INTERVAL - is the minimum interval between transmission of 828 two successive HELLO messages, on this MANET interface. (This 829 minimum interval MAY be modified by jitter, as defined in 830 [RFC5148].) 832 REFRESH_INTERVAL - is the maximum interval between advertisements, 833 in a HELLO message on this MANET interface, of each 1-hop neighbor 834 network address and its status. In all intervals of length 835 REFRESH_INTERVAL, a router MUST include each 1-hop neighbor 836 network address and its status in at least one HELLO message on 837 this MANET interface. (This may be in the same or in different 838 HELLO messages.) 840 The following constraints apply to these interface parameters: 842 o HELLO_INTERVAL > 0 844 o HELLO_MIN_INTERVAL >= 0 846 o HELLO_INTERVAL >= HELLO_MIN_INTERVAL 848 o REFRESH_INTERVAL >= HELLO_INTERVAL 850 o If an INTERVAL_TIME Message TLV as defined in [RFC5497] is 851 included in a HELLO messages, then HELLO_INTERVAL MUST be 852 representable as described in [RFC5497]. 854 If REFRESH_INTERVAL > HELLO_INTERVAL, then a router may distribute 855 its neighbor advertisements between HELLO messages in any manner, 856 subject to the constraints above. 858 For a router to employ this protocol in a purely responsive manner on 859 a MANET interface, REFRESH_INTERVAL and HELLO_INTERVAL SHOULD both be 860 set to a value such that a responsive HELLO message is always 861 expected in a shorter period than this value. 863 If a router has more than one MANET interface, then, even if the 864 router configures different values of HELLO_INTERVAL on each MANET 865 interface, the router SHOULD configure the same value of 866 HELLO_MIN_INTERVAL on all MANET interfaces on which responsive HELLO 867 messages may be sent. 869 5.3.2. Information Validity Times 871 The following interface parameters manage the validity time of link 872 information: 874 L_HOLD_TIME - is the period of advertisement, on this MANET 875 interface, of former 1-hop neighbor network addresses as lost in 876 HELLO messages, allowing recipients of these HELLO messages to 877 accelerate removal of this information from their Link Sets. 878 L_HOLD_TIME MAY be set to zero, if accelerated information removal 879 is not required. 881 H_HOLD_TIME - is used as the Value in the VALIDITY_TIME Message TLV 882 included in all HELLO messages on this MANET interface. It is 883 then used by each router receiving such a HELLO message to 884 indicate the validity of the information taken from that HELLO 885 message and recorded in the receiving router's Information Bases. 887 The following constraints apply to these interface parameters: 889 o L_HOLD_TIME >= 0 891 o H_HOLD_TIME >= REFRESH_INTERVAL 893 o If HELLO messages can be lost then both parameters SHOULD be 894 significantly greater than REFRESH_INTERVAL. 896 o H_HOLD_TIME MUST be representable as described in [RFC5497]. 898 5.3.3. Link Quality 900 The following interface parameters manage the usage of link quality 901 (see Section 14): 903 HYST_ACCEPT - is the link quality threshold at or above which a link 904 becomes usable, if it was not already so. 906 HYST_REJECT - is the link quality threshold below which a link 907 becomes unusable, if it was not already so. 909 INITIAL_QUALITY - is the initial quality of a newly identified link. 911 INITIAL_PENDING - if true, then a newly identified link is 912 considered pending, and is not usable until the link quality has 913 reached or exceeded the HYST_ACCEPT threshold. 915 The following constraints apply to these interface parameters: 917 o 0 <= HYST_REJECT <= HYST_ACCEPT <= 1 919 o 0 <= INITIAL_QUALITY <= 1. 921 o If link quality is not updated, then INITIAL_QUALITY >= 922 HYST_ACCEPT. 924 o If INITIAL_QUALITY >= HYST_ACCEPT, then INITIAL_PENDING := false. 926 o If INITIAL_QUALITY < HYST_REJECT, then INITIAL_PENDING := true. 928 5.3.4. Jitter 930 If jitter, as defined in [RFC5148], is used then these parameters are 931 as follows: 933 HP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 934 for periodically generated HELLO messages on this MANET interface. 936 HT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 937 for externally triggered HELLO messages on this MANET interface. 939 For constraints on these interface parameters see [RFC5148]. 941 5.4. Router Parameters 943 The two router parameters defined by this specification are in the 944 category of information validity time. 946 5.4.1. Information Validity Time 948 The following router parameter manages the validity time of lost 949 symmetric 1-hop neighbor information: 951 N_HOLD_TIME - is used as the period during which former 1-hop 952 neighbor network addresses are advertised as lost in HELLO 953 messages, allowing recipients of these HELLO messages to 954 accelerate removal of this information from their 2-Hop Sets. 955 N_HOLD_TIME MAY be set to zero, if accelerated information removal 956 is not required. 958 I_HOLD_TIME - is the period for which a recently used local 959 interface network address is recorded. 961 The following constraints applies to these router parameters: 963 o N_HOLD_TIME >= 0 965 o I_HOLD_TIME >= 0 967 5.5. Parameter Change Constraints 969 If protocol parameters are changed dynamically, the constraints in 970 this section apply. 972 HELLO_INTERVAL 974 * If the HELLO_INTERVAL for a MANET interface increases, then the 975 next HELLO message on this MANET interface MUST be generated 976 according to the previous, shorter, HELLO_INTERVAL. A number 977 of subsequent HELLO messages MAY be generated according to the 978 previous, shorter, HELLO_INTERVAL (but MUST include times 979 according to current parameters). This ensures that "promises" 980 as to timely transmission of a future HELLO message is kept 981 until these previous promises have expired. 983 * If the HELLO_INTERVAL for a MANET interface decreases, then the 984 following HELLO messages on this MANET interface MUST be 985 generated according to this current, shorter, HELLO_INTERVAL. 987 REFRESH_INTERVAL 989 * If the REFRESH_INTERVAL for a MANET interface increases, then 990 the content of subsequent HELLO messages must be organized such 991 that the specification of the old value of REFRESH_INTERVAL is 992 satisfied for a further period equal to the old value of 993 REFRESH_INTERVAL. 995 * If the REFRESH_INTERVAL for a MANET interface decreases, then 996 it MAY be necessary to reschedule HELLO message generation on 997 that MANET interface, in order that the specification of 998 REFRESH_INTERVAL is satisfied from the time of change. 1000 HYST_ACCEPT and HYST_REJECT 1002 * If HYST_ACCEPT or HYST_REJECT changes, then the appropriate 1003 actions for link quality change, as specified in Section 14.3, 1004 MUST be taken. 1006 L_HOLD_TIME 1008 * If L_HOLD_TIME changes, then L_time for all relevant Link 1009 Tuples MUST be changed. 1011 N_HOLD_TIME 1013 * If N_HOLD_TIME changes, then NL_time for all relevant Lost 1014 Neighbor Tuples MUST be changed. 1016 HP_MAXJITTER 1018 * If HP_MAXJITTER changes, then the periodic HELLO message 1019 schedule on this MANET interface MAY be changed. 1021 HT_MAXJITTER 1023 * If HT_MAXJITTER changes, then externally triggered HELLO 1024 messages on this MANET interface MAY be rescheduled. 1026 5.6. Constants 1028 The constant C (time granularity) is used as specified in [RFC5497]. 1030 6. Local Information Base 1032 A router maintains a Local Information Base that records information 1033 about its interfaces (MANET and non-MANET). Each interface of a 1034 router MUST be identified by at least one network address. Such 1035 network addresses MAY be specific to that interface, or MAY in some 1036 circumstances be used by more than one interface as specified below. 1038 The Local Information Base is not modified by signaling. If a 1039 router's interface configuration changes, then the Local Information 1040 Base MUST reflect these changes. This MAY also result in signaling 1041 to advertise these changes. 1043 It is not necessary to include all addresses of an interface in the 1044 Local Information Base, and hence in HELLO messages. However any 1045 address that may be the source address of an IP datagram sent from 1046 that interface MUST be included (and at least one address MUST be 1047 included). A protocol using this specification MAY add additional 1048 requirements to these, e.g. that any address that may be the 1049 destination address of an IP datagram is also included. 1051 The addresses assigned to an interface are "owned" by the router, and 1052 MUST NOT be used by any other router as an interface address. If an 1053 address has a prefix length and represents a range of addresses, this 1054 applies to all addresses in that range (i.e. such ranges MUST NOT 1055 overlap). 1057 The addresses assigned to different interfaces on the same router 1058 MUST be distinct (hence network address ranges MUST NOT overlap) 1059 except that: 1061 o The same address MAY be assigned to any number of non-MANET 1062 interfaces as well as to one (or more if the following condition 1063 also applies) MANET interface. 1065 o The same address MAY be assigned to two (or more if each pair 1066 satisfies this condition) MANET interfaces if those two MANET 1067 interfaces cannot communicate to, from, or one to and one from, 1068 any other MANET interface of another router. 1070 6.1. Local Interface Set 1072 A router's Local Interface Set records its local interfaces. It 1073 consists of Local Interface Tuples, one per interface: 1075 (I_local_iface_addr_list, I_manet) 1077 where: 1079 I_local_iface_addr_list is an unordered list of the network 1080 addresses of this interface. 1082 I_manet is a boolean flag, describing if this interface is a MANET 1083 interface. 1085 Local Interface Tuples are removed from the Local Interface Set only 1086 when the routers' interface configuration changes, subject to 1087 Section 9, i.e. they are not subject to timer-based expiration. 1089 6.2. Removed Interface Address Set 1091 A router's Removed Interface Address Set records network addresses 1092 which were recently used as local interface network addresses. If a 1093 router's interface network addresses are immutable then the Removed 1094 Interface Address Set is always empty and MAY be omitted. It 1095 consists of Removed Interface Address Tuples, one per network 1096 address: 1098 (IR_local_iface_addr, IR_time) 1100 where: 1102 IR_local_iface_addr is a recently used network address of an 1103 interface of this router. 1105 IR_time specifies when this Tuple expires and MUST be removed. 1107 7. Interface Information Base 1109 A router maintains an Interface Information Base for each of its 1110 MANET interfaces. This records information about links to that MANET 1111 interface and symmetric 2-hop neighbors which can be reached in two 1112 hops using those links as the first hop. The Interface Information 1113 Base includes the Link Set and the 2-Hop Set. 1115 A network address of a symmetric 2-hop neighbor can also be present 1116 as the network address of a 1-hop neighbor. This allows the router 1117 using this network address to be immediately considered as a 1118 symmetric 2-hop neighbor if it fails to be a symmetric 1-hop 1119 neighbor. 1121 An element which specifies a time is considered expired if the 1122 current time is greater than or equal to that time. One such 1123 element, present in most Tuples, indicates when expired that the 1124 Tuple itself is considered expired and MUST be removed. Tuples which 1125 do not have such a time element are removed at other times as 1126 specified, for example a Neighbor Tuple is removed when all 1127 corresponding Link Tuples have been removed. 1129 7.1. Link Set 1131 A router's Link Set records links from other routers which are, or 1132 recently were, 1-hop neighbors. It consists of Link Tuples, each 1133 representing a single link: 1135 (L_neighbor_iface_addr_list, L_HEARD_time, L_SYM_time, 1136 L_quality, L_pending, L_lost, L_time) 1138 where: 1140 L_neighbor_iface_addr_list is an unordered list of the network 1141 addresses of the MANET interface of the 1-hop neighbor; 1143 L_HEARD_time is the time until which the MANET interface of the 1144 1-hop neighbor would be considered heard if not considering link 1145 quality; 1147 L_SYM_time is the time until which the link to the 1-hop neighbor 1148 would be considered symmetric if not considering link quality; 1150 L_quality is a dimensionless number between 0 (inclusive) and 1 1151 (inclusive) describing the quality of a link; a greater value of 1152 L_quality indicating a higher quality link; 1154 L_pending is a boolean flag, describing if a link is considered 1155 pending (i.e. a candidate, but not yet established, link); 1157 L_lost is a boolean flag, describing if a link is considered lost 1158 due to low link quality; 1160 L_time specifies when this Tuple expires and MUST be removed. 1162 The status of the link, as obtained through HELLO message exchange 1163 and using link quality, is denoted L_status. L_status can take the 1164 Values PENDING, HEARD, SYMMETRIC and LOST. The values LOST, 1165 SYMMETRIC and HEARD are defined in Section 18.5. The Value PENDING 1166 is never used in a HELLO message, it is only used locally by a 1167 router, and any Value distinct from LOST, SYMMETRIC and HEARD may be 1168 used. 1170 L_status is defined by: 1172 1. If L_pending = true, then L_status := PENDING; 1173 2. otherwise, if L_lost = true, then L_status := LOST; 1175 3. otherwise, if L_SYM_time is not expired, then L_status := 1176 SYMMETRIC; 1178 4. otherwise, if L_HEARD_time is not expired, then L_status := 1179 HEARD; 1181 5. otherwise, L_status := LOST. 1183 7.2. 2-Hop Set 1185 A router's 2-Hop Set records network addresses of symmetric 2-hop 1186 neighbors, and the symmetric links to symmetric 1-hop neighbors 1187 through which these symmetric 2-hop neighbors can be reached. It 1188 consists of 2-Hop Tuples, each representing a single network address 1189 of a symmetric 2-hop neighbor, and a single MANET interface of a 1190 symmetric 1-hop neighbor. 1192 (N2_neighbor_iface_addr_list, N2_2hop_addr, N2_time) 1194 where: 1196 N2_neighbor_iface_addr_list is an unordered list of the network 1197 addresses of the MANET interface of the symmetric 1-hop neighbor 1198 from which this information was received; 1200 N2_2hop_addr is a network address of a symmetric 2-hop neighbor 1201 which has a symmetric link (using any MANET interface) to the 1202 indicated symmetric 1-hop neighbor; 1204 N2_time specifies when this Tuple expires and MUST be removed. 1206 8. Neighbor Information Base 1208 Each router maintains a Neighbor Information Base that records 1209 information about network addresses of current and recently symmetric 1210 1-hop neighbors. 1212 8.1. Neighbor Set 1214 A router's Neighbor Set records all network addresses of each 1-hop 1215 neighbor. It consists of Neighbor Tuples, each representing a single 1216 1-hop neighbor: 1218 (N_neighbor_addr_list, N_symmetric) 1220 where: 1222 N_neighbor_addr_list is an unordered list of the network addresses 1223 of a 1-hop neighbor; 1225 N_symmetric is a boolean flag, describing if this is a symmetric 1226 1-hop neighbor. 1228 Neighbor Tuples are removed from the Neighbor Set only when 1229 corresponding Link Tuples expire from the routers' Link Set, i.e. 1230 Neighbor Tuples are not directly subject to timer-based expiration. 1232 8.2. Lost Neighbor Set 1234 A router's Lost Neighbor Set records network addresses of routers 1235 which recently were symmetric 1-hop neighbors, but which are now 1236 advertised as lost. It consists of Lost Neighbor Tuples, each 1237 representing a single such network address: 1239 (NL_neighbor_addr, NL_time) 1241 where: 1243 NL_neighbor_addr is a network address of a router which recently was 1244 a symmetric 1-hop neighbor of this router; 1246 NL_time specifies when this Tuple expires and MUST be removed. 1248 9. Local Information Base Changes 1250 The Local Information Base MUST be updated in response to changes in 1251 the router's local interface configuration. These may also change 1252 the the Interface Information Base and the Neighbor Information Base. 1253 If any changes to the latter Information Bases satisfy any of the 1254 conditions described in Section 13, then those changes must be 1255 applied immediately, unless noted otherwise below. 1257 A router MAY transmit HELLO messages in response to these changes. 1259 9.1. Adding an Interface 1261 If an interface is added to the router, then this is indicated by the 1262 addition of a Local Interface Tuple to the Local Interface Set. If 1263 the new interface is a MANET interface, then an initially empty 1264 Interface Information Base MUST be created for this new MANET 1265 interface. The actions in Section 9.3 MUST be taken for each network 1266 address of this added interface. A HELLO message MAY be sent on all 1267 MANET interfaces, it SHOULD be sent on the new interface if it is a 1268 MANET interface. If using scheduled messages, then a message 1269 schedule MUST be established on the new MANET interface. 1271 9.2. Removing an Interface 1273 If an interface is removed from the router, then this MUST result in 1274 changes to the Local Information Base and to the Neighbor Information 1275 Base as follows: 1277 1. Identify the Local Interface Tuple that corresponds to the 1278 interface to be removed. 1280 2. For each network address (henceforth removed address) in the 1281 I_local_iface_addr_list of that Local Interface Tuple, if that 1282 network address is not in the I_local_iface_addr_list of any 1283 other Local Interface Tuple, then create a Removed Interface 1284 Address Tuple with: 1286 * IR_local_iface_addr := removed address; 1288 * IR_time := current time + I_HOLD_TIME. 1290 3. Remove that Local Interface Tuple from the Local Interface Set. 1292 4. If the interface to be removed is a MANET interface (i.e. with 1293 I_manet = true) then: 1295 1. Remove the Interface Information Base for that MANET 1296 interface; 1298 2. All Neighbor Tuples for which none of the network addresses 1299 in its N_neighbor_addr_list are contained in any 1300 L_neighbor_iface_addr_list in any remaining Link Tuple, are 1301 removed. 1303 If the removed interface is the last MANET interface of the router, 1304 then there will be no remaining Interface Information Bases, and the 1305 router will longer participate in this protocol. 1307 After removing the interface and making these changes, a HELLO 1308 message MAY be sent on all remaining MANET interfaces. 1310 9.3. Adding a Network Address to an Interface 1312 If a network address is added to an interface then this is indicated 1313 by the addition of a network address to the appropriate 1314 I_local_iface_addr_list. The following changes MUST be made to the 1315 Information Bases: 1317 1. Any Removed Interface Address Tuple whose IR_local_iface_addr is 1318 the added network address is removed. 1320 2. Any Neighbor Tuples whose N_neighbor_addr_list contains the added 1321 network address, are removed. 1323 3. Any Link Tuples, in any Link Set, whose 1324 L_neighbor_iface_addr_list contains: 1326 * the added network address; OR 1328 * any network address in the N_neighbor_addr_list of any removed 1329 Neighbor Tuple 1331 are removed; apply Section 13.2, but not Section 13.3. 1333 4. Any Lost Neighbor Tuples whose NL_neighbor_addr = the added 1334 network address, are removed. 1336 5. Any 2-Hop Tuples whose N2_2hop_addr = the added network address, 1337 are removed. 1339 After adding the network address and making these changes, a HELLO 1340 message MAY be sent on all MANET interfaces. 1342 These changes, other than to the appropriate I_local_iface_addr_list, 1343 are made in order to maintain consistency of the Information Bases. 1344 Specifically, these changes remove any record of any use of this 1345 network address by routers in the 1-hop neighborhood or in the 1346 symmetric 2-hop neighborhood of this router. 1348 9.4. Removing a Network Address from an Interface 1350 If a network address (henceforth removed address) is removed from an 1351 interface then: 1353 1. Identify the Local Interface Tuple that corresponds to the 1354 removed address. 1356 2. If this is the only network address of that interface (the only 1357 network address in the corresponding I_local_iface_addr_list) 1358 then remove that interface as specified in Section 9.2. 1360 3. Otherwise: 1362 1. Remove the removed address from this I_local_iface_addr_list. 1364 2. If the removed address is not in the I_local_iface_addr_list 1365 of any other Local Interface Tuple, then create a Removed 1366 Interface Address Tuple with: 1368 + IR_local_iface_addr := removed address; 1370 + IR_time := current time + I_HOLD_TIME. 1372 After removing the network address and making these changes, a HELLO 1373 message MAY be sent on all MANET interfaces. 1375 10. Packets and Messages 1377 The packet and message format used by this protocol is defined in 1378 [RFC5444], which is used with the following considerations: 1380 o This protocol specifies one Message Type, the HELLO message. 1382 o A HELLO message MAY use any combination of Message Header options 1383 specified in [RFC5444]. 1385 o HELLO messages MUST NOT be forwarded, i.e. a , if 1386 present, MUST have the value 1. 1388 o HELLO messages MAY be included in multi-message packets as 1389 specified in [RFC5444]. 1391 o Received HELLO messages MUST be parsed in accordance with 1392 [RFC5444]. A HELLO message which is not in conformance with 1393 [RFC5444] MUST be discarded without being processed. A HELLO 1394 message can also be discarded without being processed for other 1395 reasons, see Section 12.1. 1397 o This protocol specifies three Address Block TLVs. It also uses 1398 two Message TLVs defined in [RFC5497]. These five TLV Types are 1399 all defined only with Type Extension = 0. TLVs of other types, 1400 and of these types but without Type Extension = 0, are ignored by 1401 this protocol. All references in this specification to, for 1402 example, an Address Block TLV with Type = LINK_STATUS, are to be 1403 considered as referring to an Address Block TLV with Type = 1404 LINK_STATUS and Type Extension = 0. 1406 10.1. HELLO Messages 1408 A HELLO message MUST contain: 1410 o Exactly one VALIDITY_TIME Message TLV as specified in [RFC5497], 1411 representing H_HOLD_TIME for the transmitting MANET interface. 1412 The options included in [RFC5497] for representing zero and 1413 infinite times MUST NOT be used. 1415 A HELLO message which is transmitted periodically SHOULD contain, and 1416 otherwise MAY contain: 1418 o Exactly one INTERVAL_TIME Message TLV as specified in [RFC5497], 1419 representing HELLO_INTERVAL for the transmitting MANET interface. 1420 The options included in [RFC5497] for representing zero and 1421 infinite times MUST NOT be used. 1423 A HELLO message MAY contain: 1425 o Other Message TLVs. 1427 o One or more Address Blocks, each with an associated Address Block 1428 TLV Block, which MAY contain other Address Block TLVs. 1430 10.1.1. Address Blocks 1432 All network addresses in a router's Local Interface Set (i.e. in any 1433 I_local_iface_addr_list) MUST be represented as address objects (see 1434 [RFC5444]), and included in the Address Blocks in all generated HELLO 1435 messages, with the following permitted exception: 1437 o If the MANET interface on which the HELLO message is to be sent 1438 has a single address with maximum prefix length (i.e. /32 for 1439 IPv4, /128 for IPv6), then that address MAY be omitted from being 1440 included in any Address Block, provided that this address is 1441 included as the sending address of the IP datagram in which the 1442 HELLO message is included. 1444 All network addresses of the router's interfaces included in any 1445 Address Block(s) MUST be associated with an Address Block TLV with 1446 Type = LOCAL_IF, as defined in Table 1. 1448 +----------+---------+----------------------------------------------+ 1449 | Name | Value | Description | 1450 | | Length | | 1451 +----------+---------+----------------------------------------------+ 1452 | LOCAL_IF | 1 octet | Specifies that the network address is | 1453 | | | associated with the MANET interface on which | 1454 | | | the message was sent (THIS_IF) or another | 1455 | | | interface of the sending router (OTHER_IF). | 1456 +----------+---------+----------------------------------------------+ 1458 Table 1: LOCAL_IF TLV definition 1460 Address Blocks MAY contain current or recently lost 1-hop neighbors' 1461 network addresses, represented as address objects (see [RFC5444]), 1462 each of which is associated with one or both Address Block TLVs as 1463 described in Table 2. 1465 +--------------+---------+------------------------------------------+ 1466 | Name | Value | Description | 1467 | | Length | | 1468 +--------------+---------+------------------------------------------+ 1469 | LINK_STATUS | 1 octet | Specifies the status of the link from | 1470 | | | the indicated network address and to the | 1471 | | | MANET interface over which the HELLO | 1472 | | | message is transmitted (LOST, SYMMETRIC | 1473 | | | or HEARD). | 1474 | OTHER_NEIGHB | 1 octet | Specifies that the network address is | 1475 | | | (SYMMETRIC) or was (LOST) of a MANET | 1476 | | | interface of a symmetric 1-hop neighbor | 1477 | | | of the router transmitting the HELLO | 1478 | | | message. | 1479 +--------------+---------+------------------------------------------+ 1481 Table 2: LINK_STATUS and OTHER_NEIGHB TLV definition 1483 An Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC or 1484 Value = LOST also performs the function of an Address Block TLV with 1485 Type = OTHER_NEIGHB and the same Value. Including the latter 1486 associated with the same address object is discouraged for efficiency 1487 reasons. If an Address Block TLV with Type = LINK_STATUS and Value = 1488 SYMMETRIC is combined with an Address Block TLV with Type = 1489 OTHER_NEIGHB and Value = LOST associated with the same address 1490 object, then the latter MUST be ignored, and SHOULD NOT be included. 1491 See Appendix A. 1493 Other network addresses MAY be represented as address objects (see 1494 [RFC5444] and included in Address Blocks, but MUST NOT be associated 1495 with any of the Address Block TLVs specified in this specification. 1497 11. HELLO Message Generation 1499 Each MANET interface MUST generate HELLO messages according to the 1500 specification in this section. HELLO messages are generated for each 1501 MANET interface independently. HELLO message generation and 1502 scheduling MUST be according to the interface parameters for that 1503 MANET interface, and MAY be independent for each MANET interface or, 1504 interface parameters permitting, MANET interfaces MAY use the same 1505 schedule. 1507 If transmitting periodic HELLO messages then, following a HELLO 1508 message transmission on a MANET interface, another HELLO message MUST 1509 be transmitted on the same MANET interface after an interval not 1510 greater than HELLO_INTERVAL. Two successive HELLO message 1511 transmissions on the same MANET interface MUST be separated by at 1512 least HELLO_MIN_INTERVAL, except as noted in Section 11.2.1. 1514 11.1. HELLO Message Specification 1516 HELLO messages are generated independently on each MANET interface. 1518 All network addresses in any I_local_iface_addr_list MUST be 1519 included, represented as address objects (see [RFC5444]), except 1520 that: 1522 o If the interface on which the HELLO message is to be sent has a 1523 single address with maximum prefix length (i.e. /32 for IPv4, /128 1524 for IPv6) then that address MAY be omitted, provided that this 1525 address is included as the sending address of the IP datagram in 1526 which the HELLO message is included. 1528 All such included address objects MUST be associated with an Address 1529 Block TLV with Type := LOCAL_IF and Value according to the following: 1531 o If the address object represents a network address of the sending 1532 MANET interface, then Value := THIS_IF. 1534 o Otherwise, Value := OTHER_IF. 1536 If such a network address is included in more than one 1537 I_local_iface_addr_list, then, for efficiency reasons, it is 1538 encouraged that the corresponding address object is associated with 1539 only one Value using an Address Block TLV with Type := LOCAL_IF, this 1540 MUST be Value := THIS_IF if the address object represents a network 1541 address of the sending MANET interface. 1543 The following network addresses of current or former 1-hop neighbors 1544 MAY be represented as address objects (see [RFC5444]) and included in 1545 any HELLO message, respecting the parameter REFRESH_INTERVAL for each 1546 association for that MANET interface, and according to the following: 1548 o Network addresses of MANET interfaces of 1-hop neighbors from the 1549 Link Set of the Interface Information Base for this MANET 1550 interface (i.e. from an L_neighbor_iface_addr_list), other than 1551 those from Link Tuples with L_status = PENDING. 1553 o Other network addresses of symmetric 1-hop neighbors from the 1554 Neighbor Set of this router's Neighbor Information Base (i.e. from 1555 an N_neighbor_addr_list). 1557 o Network addresses of MANET interfaces of previously symmetric or 1558 heard 1-hop neighbors connected on this MANET interface from the 1559 Link Set of the Interface Information Base for this MANET 1560 interface (i.e. from an L_neighbor_iface_addr_list with L_status = 1561 LOST). 1563 o Other network addresses of previously symmetric 1-hop neighbors 1564 from the Lost Neighbor Set of this router's Neighbor Information 1565 Base (i.e. from an NL_neighbor_addr). 1567 Each such address object (see [RFC5444]) MUST be associated with one 1568 or more appropriate Address Block TLVs. Specifically: 1570 1. For each address object (henceforth linked address) which 1571 represents a network address contained in an 1572 L_neighbor_iface_addr_list of a Link Tuple in the Link Set for 1573 this MANET interface, for which L_status != PENDING, include the 1574 linked address with an associated Address Block TLV with: 1576 * Type := LINK_STATUS; AND 1578 * Value := L_status. 1580 2. For each address object (henceforth neighbor address) which 1581 represents a network address contained in an N_neighbor_addr_list 1582 in a Neighbor Tuple with N_symmetric = true, and which has not 1583 already been included with an associated Address Block TLV with 1584 Type = LINK_STATUS and Value = SYMMETRIC, include the neighbor 1585 network address with an associated Address Block TLV with: 1587 * Type := OTHER_NEIGHB; AND 1589 * Value := SYMMETRIC. 1591 3. For each Lost Neighbor Tuple whose NL_neighbor_addr (henceforth 1592 lost address) has not already been represented as an address 1593 object and included, include lost address with an associated 1594 Address Block TLV with: 1596 * Type := OTHER_NEIGHB; AND 1598 * Value := LOST. 1600 If any such network addresses have been added to these Information 1601 Bases since the last HELLO message was sent on this MANET interface, 1602 or if their status (as indicated by these TLVs and the Values they 1603 associate with that network address) have changed since that network 1604 address was last reported on this MANET interface, then that network 1605 address, and the indicated TLVs, MUST be included in the HELLO 1606 message. 1608 If the address object (see [RFC5444]) representing a network address 1609 of a 1-hop neighbor is specified with more than one associated 1610 Address Block TLV, then these Address Block TLVs MAY be independently 1611 included or excluded from each HELLO message. Each such Address 1612 Block TLV MUST be included associated with the address object 1613 representation of that network address in a HELLO message sent on 1614 that MANET interface in every interval of length equal to that MANET 1615 interface's parameter REFRESH_INTERVAL. Address Block TLVs 1616 associated with the same address object included in the same HELLO 1617 message MAY be applied to the same or different copies of that 1618 address object. 1620 11.2. HELLO Message Transmission 1622 HELLO messages are transmitted in the format specified by [RFC5444]. 1624 11.2.1. HELLO Message Jitter 1626 HELLO messages MAY be sent using periodic message generation or 1627 externally triggered message generation. If using data link and 1628 physical layers which are subject to packet loss due to collisions, 1629 HELLO messages SHOULD be jittered as described in [RFC5148]. 1631 Internally triggered message generation (such as due to a change in 1632 local interfaces) MAY be treated as if externally generated message 1633 generation, or MAY be not jittered. 1635 HELLO messages MUST NOT be forwarded, and thus message forwarding 1636 jitter does not apply to HELLO messages. 1638 Each form of jitter described in [RFC5148] requires a parameter 1639 MAXJITTER. These interface parameters may be dynamic, and are 1640 specified by: 1642 o For periodic message generation: HP_MAXJITTER. 1644 o For externally triggered message generation: HT_MAXJITTER. 1646 When HELLO message generation is delayed in order that a HELLO 1647 message is not sent within HELLO_MIN_INTERVAL of the previous HELLO 1648 message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD 1649 be reduced by jitter, with maximum reduction HP_MAXJITTER, as 1650 described in [RFC5148]. In this case HP_MAXJITTER MUST NOT be 1651 greater than HELLO_MIN_INTERVAL. 1653 12. HELLO Message Processing 1655 On receiving a HELLO message, a router MUST first check if the 1656 message is invalid for processing by this router, as defined in 1657 Section 12.1 and, if so, discard the message without further 1658 processing. Otherwise, for each received and valid HELLO message the 1659 receiving router MUST update its appropriate Interface Information 1660 Base and its Neighbor Information Base as specified in Section 12.3 1661 to Section 12.6. These updates MUST be performed in the order in 1662 which they are presented in this specification. If any changes 1663 satisfy any of the conditions described in Section 13 then the 1664 indicated consequences in that section MUST be applied immediately, 1665 unless noted otherwise. 1667 All message processing, including determination of whether a message 1668 is invalid, considers only TLVs with Type Extension = 0. TLVs with 1669 any other type extension are ignored. All references to, for 1670 example, a TLV with Type = LINK_STATUS refer to a TLV with Type = 1671 LINK_STATUS and Type Extension = 0. 1673 12.1. Invalid Message 1675 A received HELLO message is invalid for processing by this router if 1676 any of the following conditions are true: 1678 o The address length as specified in the Message Header is not equal 1679 to the length of the addresses used by this router. 1681 o The message has a field in its Message Header with 1682 a value other than one. (Note that the message need not have a 1683 field.) 1685 o The message has a field in its Message Header with 1686 a value other than zero. (Note that the message need not have a 1687 field.) 1689 o The message does not have a Message TLV with Type = VALIDITY_TIME 1690 in its Message TLV Block. 1692 o The message has more than one Message TLV with Type = 1693 VALIDITY_TIME in its Message TLV Block. 1695 o The message has more than one Message TLV with Type = 1696 INTERVAL_TIME in its Message TLV Block. 1698 o The message has any Address Block TLV(s) with Type = LOCAL_IF and 1699 any single Value v such that v != THIS_IF and v != OTHER_IF. 1701 o Any address object (including different address objects 1702 representing the same network address, in the same or different 1703 Address Blocks) is associated with more than one Value by one or 1704 more Address Block TLV(s) with Type = LOCAL_IF. 1706 o Any address object (henceforth local address) associated with an 1707 Address Block TLV with Type = LOCAL_IF represents one of the 1708 receiving router's current or recently used network addresses 1709 (i.e. local address overlaps any network address in any 1710 I_local_iface_addr_list in the Local Interface Set or any 1711 IR_local_iface_addr in the Removed Interface Address Set). 1713 o The message has any Address Block TLV(s) with Type = LINK_STATUS 1714 with any single Value v such that v != LOST, v != SYMMETRIC, and v 1715 != HEARD. 1717 o The message has any Address Block TLV(s) with Type = OTHER_NEIGHB 1718 with any single Value v such that v != LOST and v != SYMMETRIC. 1720 o Any address object (including different copies of an address 1721 object, in the same or different Address Blocks) is associated 1722 with an Address Block TLV with Type = LOCAL_IF and with an Address 1723 Block TLV with Type = LINK_STATUS. 1725 o Any address object (including different copies of an address 1726 object, in the same or different Address Blocks) is associated 1727 with an Address Block TLV with Type = LOCAL_IF and with an Address 1728 Block TLV with Type = OTHER_NEIGHB. 1730 o Any address object (including different copies of an address 1731 object, in the same or different Address Blocks) is associated 1732 with more than one Value by one or more Address Block TLVs with 1733 Type = LINK_STATUS. 1735 o Any address object (including different copies of an address 1736 object, in the same or different Address Blocks) is associated 1737 with more than one Value by one or more Address Block TLVs with 1738 Type = OTHER_NEIGHB. 1740 A router MAY recognize additional reasons for identifying that a 1741 message is badly formed and therefore invalid for processing, e.g. to 1742 allow a security protocol as suggested in Section 17 to perform 1743 verification of HELLO message signatures and prevent processing of 1744 unverifiable HELLO messages by this protocol. 1746 An invalid message MUST be silently discarded, without updating the 1747 router's Information Bases. 1749 12.2. Definitions 1751 For the purpose of this section, note the following definitions: 1753 o "validity time" is calculated from the Message TLV with Type = 1754 VALIDITY_TIME of the HELLO message as specified in [RFC5497]. 1755 (Note that, as specified by Section 12.1, there must be exactly 1756 one such Message TLV in the HELLO message.) All information in 1757 the HELLO message used by this specification has the same validity 1758 time. 1760 o "Receiving Address List" is the I_local_iface_addr_list 1761 corresponding to the MANET interface on which the HELLO message 1762 was received 1764 o "Sending Address List" is an unordered list of network addresses 1765 of the MANET interface over which the HELLO message was sent, i.e. 1766 is an unordered list of the network addresses represented by 1767 address objects contained in the HELLO message with an associated 1768 Address Block TLV with Type = LOCAL_IF and Value = THIS_IF. If 1769 the Sending Address List is otherwise empty, then the Sending 1770 Address List contains a single network address with maximum prefix 1771 length (i.e. /32 for IPv64, /128 for IPv6) with address equal to 1772 the sending address of the IP datagram in which the HELLO message 1773 was included. 1775 o "Neighbor Address List" is an unordered list of all the network 1776 addresses of all the interfaces of the router which generated the 1777 HELLO message, i.e. is the Sending Address List, plus the network 1778 addresses represented by address objects contained in the HELLO 1779 message with an associated Address Block TLV with Type = LOCAL_IF 1780 and Value = OTHER_IF. 1782 o "EXPIRED" indicates that a timer is set to a value clearly 1783 preceding the current time (e.g., current time - 1). 1785 o "Removed Address List" is a list of network addresses created by 1786 this HELLO message processing which were formerly reported as 1787 local by the router originating the HELLO message, but which are 1788 not included in the Neighbor Address List. This list is 1789 initialized as empty. 1791 o "Lost Address List" is a subset of the Removed Address List 1792 containing network addresses which were formerly considered as 1793 symmetric. This list is initialized as empty. 1795 12.3. Updating the Neighbor Set 1797 On receiving a HELLO message, the router MUST update its Neighbor Set 1798 and populate the Removed Address List and Lost Address List: 1800 1. Find all Neighbor Tuples (henceforth matching Neighbor Tuples) 1801 where N_neighbor_addr_list contains any network address which 1802 overlaps with any network address in the Neighbor Address List. 1804 2. If there are no matching Neighbor Tuples, then: 1806 1. Create a new Neighbor Tuple with: 1808 + N_neighbor_addr_list := Neighbor Address List; 1810 + N_symmetric := false. 1812 3. If there is one matching Neighbor Tuple, then: 1814 1. If the matching Neighbor Tuple's N_neighbor_addr_list != 1815 Neighbor Address List, then: 1817 1. For each network address (henceforth removed address) 1818 which is contained in that N_neighbor_addr_list, but is 1819 not contained in the Neighbor Address List: 1821 1. Add removed address to the Removed Address List. 1823 2. If N_symmetric = true, then add removed address to 1824 the Lost Address List. 1826 2. Update the matching Neighbor Tuple by: 1828 - N_neighbor_addr_list := Neighbor Address List. 1830 4. If there are two or more matching Neighbor Tuples, then: 1832 1. For each network address (henceforth removed address) which 1833 is contained in the N_neighbor_addr_list of any of the 1834 matching Neighbor Tuples but is not contained in the Neighbor 1835 Address List: 1837 1. Add removed address to the Removed Address List. 1839 2. If N_symmetric = true, then add removed address to the 1840 Lost Address List. 1842 2. Replace the matching Neighbor Tuples by a single Neighbor 1843 Tuple with: 1845 + N_neighbor_addr_list := Neighbor Address List; 1846 + N_symmetric := false 1848 12.4. Updating the Lost Neighbor Set 1850 On receiving a HELLO message, a router MUST update its Lost Neighbor 1851 Set: 1853 1. For each network address (henceforth lost address) which is 1854 contained in the Lost Address List, if no Lost Neighbor Tuple 1855 with NL_neighbor_addr = lost address exists, then add a Lost 1856 Neighbor Tuple with: 1858 * NL_neighbor_addr := lost address; 1860 * NL_time := current time + N_HOLD_TIME. 1862 12.5. Updating the Link Set 1864 On receiving a HELLO message, a router MUST update its Link Set for 1865 the MANET interface on which the HELLO message is received: 1867 1. Remove all network addresses in the Removed Address List from the 1868 L_neighbor_iface_addr_list of all Link Tuples. 1870 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now 1871 empty; apply Section 13.2, but not Section 13.3. 1873 3. Find all Link Tuples (henceforth matching Link Tuples) where: 1875 * L_neighbor_iface_addr_list contains one or more network 1876 addresses in the Sending Address List. 1878 4. If there is more than one matching Link Tuple, then remove them 1879 all; apply Section 13.2, but not Section 13.3. 1881 5. If no matching Link Tuples remain, then create a new matching 1882 Link Tuple with: 1884 * L_neighbor_iface_addr_list := empty; 1886 * L_HEARD_time := EXPIRED; 1888 * L_SYM_time := EXPIRED; 1890 * L_quality := INITIAL_QUALITY; 1892 * L_pending := INITIAL_PENDING; 1893 * L_lost := false; 1895 * L_time := current time + validity time. 1897 6. The matching Link Tuple, existing or new, is then modified as 1898 follows: 1900 1. If the router finds any network address (henceforth receiving 1901 address) in the Receiving Address List in an Address Block in 1902 the HELLO message, then the Link Tuple is modified as 1903 follows: 1905 1. If any receiving address in the HELLO message is 1906 associated with an Address Block TLV with Type = 1907 LINK_STATUS and with Value = HEARD or Value = SYMMETRIC 1908 then: 1910 - L_SYM_time := current time + validity time. 1912 2. Otherwise if any receiving address in the HELLO message 1913 is associated with an Address Block TLV with Type = 1914 LINK_STATUS and Value = LOST then: 1916 1. if L_SYM_time has not expired, then: 1918 1. L_SYM_time := EXPIRED. 1920 2. if L_status = HEARD, then: 1922 * L_time := current time + L_HOLD_TIME. 1924 2. L_neighbor_iface_addr_list := Sending Address List. 1926 3. L_HEARD_time := max(current time + validity time, 1927 L_SYM_time). 1929 4. If L_status = PENDING, then: 1931 + L_time := max(L_time, L_HEARD_time). 1933 5. Otherwise if L_status = HEARD or L_status = SYMMETRIC, then: 1935 + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 1937 12.6. Updating the 2-Hop Set 1939 On receiving a HELLO message a router MUST update its 2-Hop Set for 1940 the MANET interface on which the HELLO message was received: 1942 1. Remove all network addresses in the Removed Address List from the 1943 N2_neighbor_iface_addr_list of all 2-Hop Tuples. 1945 2. If the Link Tuple whose L_neighbor_iface_addr_list = Sending 1946 Address List, has L_status = SYMMETRIC then: 1948 1. For each network address (henceforth 2-hop address) in an 1949 Address Block of the HELLO message, where: 1951 + 2-hop address is not contained in the Neighbor Address 1952 List; 1954 + 2-hop address is not contained in any 1955 I_local_iface_addr_list; AND 1957 + 2-hop address != any IR_local_iface_addr 1959 perform the following processing: 1961 1. If 2-hop address has an associated Address Block TLV 1962 with: 1964 - Type = LINK_STATUS and Value = SYMMETRIC; OR 1966 - Type = OTHER_NEIGHB and Value = SYMMETRIC, 1968 then, if there is no 2-Hop Tuple such that: 1970 - N2_neighbor_iface_addr_list contains one or more 1971 network addresses in the Sending Address List; AND 1973 - N2_2hop_addr = 2-hop address. 1975 then create a 2-Hop Neighbor Tuple with: 1977 - N2_2hop_addr := 2-hop address. 1979 This 2-Hop Tuple (existing or new) is then modified as 1980 follows: 1982 - N2_neighbor_iface_addr_list := Sending Address List; 1983 - N2_time := current time + validity time. 1985 2. Otherwise if 2-hop address has an Address Block TLV with: 1987 - Type = LINK_STATUS and Value = LOST or Value = HEARD; 1988 OR 1990 - Type = OTHER_NEIGHB and Value = LOST; 1992 then remove all 2-Hop Tuples with: 1994 - N2_neighbor_iface_addr_list contains one or more 1995 network addresses in the Sending Address List; AND 1997 - N2_2hop_addr = 2-hop address. 1999 13. Other Information Base Changes 2001 The Interface and Neighbor Information Bases MUST be changed when 2002 certain events occur. These events may result from HELLO message 2003 processing, or may be otherwise generated (e.g., expiry of timers or 2004 link quality changes). 2006 Events which cause changes in the Information Bases are: 2008 o A Link Tuple's L_status changes to SYMMETRIC. In this case, the 2009 actions specified in Section 13.1 are performed. 2011 o A Link Tuple's L_status changes from SYMMETRIC, or the Link Tuple 2012 is removed. In this case, the actions specified in Section 13.2 2013 are performed. 2015 o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed. 2016 In this case, the actions specified in Section 13.3 are performed. 2018 o Local interface network address changes. In this case, the 2019 actions specified in Section 9 are performed. 2021 o Link quality changes. In this case, the actions specified in 2022 Section 14 are performed. 2024 If a Link Tuple is removed, or if L_status changes from SYMMETRIC and 2025 L_HEARD_time expires, then the actions specified in Section 13.2 MUST 2026 be performed before the actions specified in Section 13.3 are 2027 performed for that Link Tuple. 2029 A router MAY report updated information in response to any of these 2030 changes in HELLO message(s), subject to the constraints in 2031 Section 11. 2033 A router which transmits HELLO messages in response to such changes 2034 SHOULD transmit a HELLO message: 2036 o On all MANET interfaces, if the Neighbor Set changes such as to 2037 indicate the change in symmetry of any 1-hop neighbors (including 2038 addition or removal of symmetric 1-hop neighbors). 2040 o Otherwise, on all those MANET interfaces whose Link Set changes 2041 such as to indicate a change in L_status of any 1-hop neighbors 2042 (including the addition or removal of any 1-hop neighbors, other 2043 than those considered pending). 2045 13.1. Link Tuple Symmetric 2047 If, for any Link Tuple which does not have L_status = SYMMETRIC: 2049 o L_status changes to SYMMETRIC; 2051 (this includes a newly created Link Tuple which is immediately 2052 updated such that L_status = SYMMETRIC) then: 2054 1. For the Neighbor Tuple whose N_neighbor_addr_list contains 2055 L_neighbor_iface_addr_list, set: 2057 * N_symmetric := true. 2059 2. Remove all Lost Neighbor Tuples whose NL_neighbor_addr is 2060 contained in that N_neighbor_addr_list. 2062 13.2. Link Tuple Not Symmetric 2064 If for any Link Tuple with L_status = SYMMETRIC: 2066 o L_status changes to any other value; OR 2068 o the Link Tuple is removed; 2070 then: 2072 1. All 2-Hop Tuples for the same MANET interface with: 2074 * N2_neighbor_iface_addr_list contains one or more network 2075 addresses in L_neighbor_iface_addr_list; 2077 are removed. 2079 2. For the Neighbor Tuple whose N_neighbor_addr_list contains 2080 L_neighbor_iface_addr_list: 2082 1. If there are no remaining Link Tuples for any MANET interface 2083 where: 2085 + L_neighbor_iface_addr_list is contained in 2086 N_neighbor_addr_list; AND 2088 + L_status = SYMMETRIC; 2090 then modify the Neighbor Tuple by: 2092 1. N_symmetric := false. 2094 2. For each network address (henceforth neighbor address) in 2095 N_neighbor_addr_list, add a Lost Neighbor Tuple with: 2097 - NL_neighbor_addr := neighbor address; 2099 - NL_time := current time + N_HOLD_TIME. 2101 13.3. Link Tuple Heard Timeout 2103 If, for any Link Tuple: 2105 o L_HEARD_time expires; OR 2107 o the Link Tuple is removed; 2109 then: 2111 1. For the Neighbor Tuple whose N_neighbor_addr_list contains 2112 L_neighbor_iface_addr_list, if no Link Tuples for any MANET 2113 interface remain where: 2115 * L_neighbor_iface_addr_list is contained in 2116 N_neighbor_addr_list; AND 2118 * L_HEARD_time is not expired; 2120 then remove the Neighbor Tuple. 2122 14. Link Quality 2124 Link quality is a mechanism whereby a router MAY take considerations 2125 other than message exchange into account for determining when a link 2126 is and is not a candidate for being considered as HEARD or SYMMETRIC. 2128 As such, it is a "link admission" mechanism. 2130 Link quality information for a link is generated (e.g., through 2131 access to signal to noise ratio, packet loss rate, or other 2132 information from the link layer) and used only locally, i.e. is not 2133 included in signaling, and routers may interoperate whether they are 2134 using the same, different, or no, link quality information. 2136 For deployments where no link quality is used, the considerations in 2137 Section 14.1 apply. For deployments where link quality is used, the 2138 general principles of link quality usage are described in 2139 Section 14.2. Section 14.3 and Section 14.4 detail link quality 2140 functioning. 2142 14.1. Deployment Without Link Quality 2144 In order for a router to not employ link quality, the router MUST 2145 define: 2147 o INITIAL_PENDING := false; 2149 o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define 2150 INITIAL_QUALITY := 1). 2152 14.2. Basic Principles of Link Quality 2154 To enable link quality usage, the L_quality value of a Link Tuple is 2155 used in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, 2156 to set the flags L_pending and L_lost of that Link Tuple. Based on 2157 these flags, the link status to advertise for that Link Tuple is 2158 determined as described in Section 7.1. 2160 The use of two thresholds implements link hysteresis, whereby a link 2161 which has HYST_REJECT <= L_quality < HYST_ACCEPT may be either 2162 accepted or rejected (depending on which threshold it has most 2163 recently crossed, or, if neither, on the value of parameter 2164 INITIAL_PENDING). With appropriate values of these parameters, this 2165 prevents over-rapid changes of link status. 2167 The basic principles of link quality usage are as follows: 2169 o A router does not advertise a neighbor interface in any state 2170 until L_quality is acceptable: 2172 * If INITIAL_PENDING = true, then the link is advertised when 2173 link L_quality >= HYST_ACCEPT. 2175 * Otherwise the link is advertised when L_quality >= HYST_REJECT. 2177 A link which is not yet advertised has L_pending = true. 2179 o Once L_quality >= HYST_ACCEPT, the router sets L_pending := false, 2180 indicating that the link can be advertised. 2182 o A link for which L_pending = false is advertised until its 2183 L_quality drops below HYST_REJECT. 2185 o If a link has L_pending = false and L_quality < HYST_REJECT, the 2186 link is LOST and is advertised as such. This link is not 2187 reconsidered as a candidate HEARD or SYMMETRIC link until 2188 L_quality >= HYST_ACCEPT. 2190 o A link which has an acceptable quality may be advertised as HEARD, 2191 SYMMETRIC or LOST according to the exchange of HELLO messages. 2193 In order that these principles can all hold, a router MUST NOT 2194 define: 2196 o INITIAL_PENDING = false and INITIAL_QUALITY < HYST_REJECT; OR 2198 o INITIAL_PENDING = true and INITIAL_QUALITY >= HYST_ACCEPT. 2200 14.3. When Link Quality Changes 2202 If L_quality for a link changes, then the following actions MUST be 2203 taken: 2205 1. If L_quality >= HYST_ACCEPT then the corresponding Link Tuple is 2206 modified by: 2208 1. L_pending := false; 2210 2. L_lost := false; 2212 3. If L_status = HEARD or L_status = SYMMETRIC, then: 2214 + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 2216 2. If L_status != PENDING, and L_quality < HYST_REJECT then the 2217 corresponding Link Tuple is modified by: 2219 1. If L_lost = false, then: 2221 + L_lost := true; 2222 + L_time := min(L_time, current time + L_HOLD_TIME). 2224 Any appropriate action indicted in Section 13 MUST also be taken. 2226 If L_quality for a link is updated based on HELLO message reception, 2227 or on reception of a packet including a HELLO message, then L_quality 2228 MUST be updated prior to the HELLO message processing described in 2229 Section 12. (If the receipt of the HELLO message, or the packet 2230 containing it, creates the Link Tuple, then the Link Tuple MUST be 2231 created with the appropriately updated L_quality value, rather than 2232 with L_quality := INITIAL_QUALITY.) 2234 14.4. Updating Link Quality 2236 A router MAY update link quality based on any information available 2237 to it. Particular cases that MAY be used include: 2239 o Information from the link layer, such as signal to noise ratio or 2240 packet acknowledgement reception and loss information. 2242 o Receipt or loss of control packets. If control packets include a 2243 sequential packet sequence number, as defined in [RFC5444], then 2244 link quality can be updated when a control packet is received, 2245 whether or not it contains a HELLO message. The link quality may 2246 then, for example, be based on whether the last N out of M control 2247 packets on the link were received, or may use a "leaky integrator" 2248 tracking packet reception and loss. 2250 o Receipt or loss of HELLO messages. If the maximum interval 2251 between HELLO messages is known (such as by inclusion in HELLO 2252 messages of a Message TLV with Type := INTERVAL_TIME, as defined 2253 in [RFC5497]) then the loss of HELLO messages can be determined 2254 without the need to receive a later HELLO message. Note that if 2255 this case is combined with the previous case then care must be 2256 taken to avoid "double counting" a lost HELLO message in a lost 2257 packet. 2259 15. Proposed Values for Parameters and Constants 2261 This section lists the parameters and constants used in the 2262 specification of the protocol, and proposed values of each which may 2263 be used when a single value of each is used. 2265 15.1. Message Interval Interface Parameters 2267 o HELLO_INTERVAL := 2 seconds 2268 o HELLO_MIN_INTERVAL := HELLO_INTERVAL/4 2270 o REFRESH_INTERVAL := HELLO_INTERVAL 2272 15.2. Information Validity Time Interface Parameters 2274 o H_HOLD_TIME := 3 x REFRESH_INTERVAL 2276 o L_HOLD_TIME := H_HOLD_TIME 2278 15.3. Information Validity Time Router Parameters 2280 o N_HOLD_TIME := L_HOLD_TIME 2282 o I_HOLD_TIME := N_HOLD_TIME 2284 15.4. Link Quality Interface Parameters 2286 If link quality is changed, then parameter values will depend on the 2287 link quality process. If link quality is not changed, then: 2289 o HYST_ACCEPT := 1 2291 o HYST_REJECT := 0 2293 o INITIAL_QUALITY := 1 2295 o INITIAL_PENDING := false 2297 15.5. Jitter Interface Parameters 2299 o HP_MAXJITTER := HELLO_INTERVAL/4 2301 o HT_MAXJITTER := HP_MAXJITTER 2303 15.6. Constants 2305 o C := 1/1024 second 2307 16. Usage with Other Protocols 2309 Other protocols, such as MANET routing protocols, which use 2310 neighborhood discovery, may need to interact with this protocol. 2311 This protocol is designed to permit such interactions, in particular: 2313 o Through accessing, and possibly extending, the information in the 2314 Local Information Base (Section 6), the Interface Information Base 2315 (Section 7) and the Neighbor Information Base (Section 8). These 2316 Information Bases record the interface configuration of the 2317 router, as well as the local connectivity, up to two hops away. 2318 All updates to the elements specified in this document are subject 2319 to the constraints specified in Appendix B. 2321 o Through accessing an outgoing HELLO message prior to it being 2322 transmitted over any MANET interface, and to add information 2323 (e.g., TLVs) as specified in [RFC5444]. This may, for example, be 2324 to allow a security protocol, as suggested in Section 17, to add a 2325 TLV containing a cryptographic signature to the message, or be to 2326 allow inserting relay selection information into a HELLO message 2327 by way of adding a TLV to an outgoing HELLO message prior to it 2328 being transmitted. 2330 o Through accessing an incoming HELLO message, and potentially 2331 discarding it prior to processing by this protocol. This may, for 2332 example, allow a security protocol as suggested in Section 17 to 2333 perform verification of HELLO message signatures and prevent 2334 processing of unverifiable HELLO messages by this protocol. 2336 o Through accessing an incoming HELLO message after it has been 2337 completely processed by this protocol. This may, in particular, 2338 allow a protocol which has added information, such as relay 2339 selection information by way of inclusion of appropriate TLVs, 2340 access to such information after appropriate updates have been 2341 recorded in the Information Bases in this protocol. 2343 o Through requesting that a HELLO message be generated at a specific 2344 time. In that case, HELLO message generation MUST still respect 2345 the constraints in Appendix B. 2347 Address objects in HELLO messages are processed according to their 2348 associated Address Block TLVs. All such address objects are to be 2349 processed according to this specification are associated with Address 2350 Block TLVs with Type of LOCAL_IF, OTHER_NEIGHB or LINK_STATUS (and 2351 type extension zero). Address objects not associated with an Address 2352 Block TLV of any of these Types are therefore not processed by the 2353 protocol described in this specification. 2355 A protocol, such as a MANET routing protocol, interacting with this 2356 protocol may need to add information to HELLO messages. This may be 2357 in form of associating TLVs (of Type other than LOCAL_IF, 2358 OTHER_NEIGHB or LINK_STATUS) to address objects already included by 2359 this specification. 2361 A protocol, such as a MANET routing protocol, interacting with this 2362 protocol may also add information to HELLO messages by inserting 2363 address objects not already included by this specification. Such 2364 address objects are in the following called "inserted addresses". 2365 These inserted addresses may added to Address Blocks already present 2366 by virtue of the HELLO message generation in this specification, or 2367 may appear in new Address Blocks. In both cases, the following MUST 2368 be observed: 2370 o An inserted address MUST NOT be associated with an Address Block 2371 TLV of Type LOCAL_IF, OTHER_NEIGHB or LINK_STATUS. Consequently, 2372 the processing in this specification will ignore such address 2373 objects. 2375 o Each inserted address MUST be associated with an Address Block 2376 TLV, to be defined by the specification of the protocol inserting 2377 the address object. In this way, all addresses present in a HELLO 2378 message are associated with an Address Block TLV defining their 2379 semantics. 2381 Informally speaking, Address Block TLVs define the semantics of 2382 address objects in an Address Block. If an address object in an 2383 Address Block does not have any Address Block TLVs associated, that 2384 address object has no semantics. Consequently, all protocols using 2385 the protocol defined in this specification MUST respect the 2386 following: 2388 o An address object in an Address Block, which is not associated 2389 with any Address Block TLV, MUST be silently ignored; the mere 2390 presence of an address object without an associated Address Block 2391 TLV in a HELLO message MUST NOT cause any processing. 2393 Strict adherence to this enables unambiguous co-existence of future 2394 "extensions" to HELLO messages. 2396 In some cases, a protocol interacting with the protocol defined in 2397 this specification, may need to recognize which HELLO messages to 2398 process and which HELLO messages to discard. It is the 2399 responsibility of that protocol to ensure that such messages are 2400 suitably identifiable, e.g. through inclusion of a Message TLV or 2401 through recognizing an administrative configuration (such as address 2402 ranges). Note that such a protocol interacting with this protocol 2403 MAY specify such interaction by recognizing an additional reason for 2404 discarding a message. As suggested in Section 17 this might, for 2405 example, be a security protocol discarding a message which does not 2406 carry a Message TLV containing a cryptographic signature. 2408 17. Security Considerations 2410 The objective of this protocol is to allow each router in the network 2411 to acquire information describing its 1-hop neighborhood and 2412 symmetric 2-hop neighborhood. This is acquired through HELLO message 2413 exchange between neighboring routers. This information is made 2414 available through the Interface Information Bases and Neighbor 2415 Information Base, describing the router's 1-hop neighborhood and 2416 symmetric 2-hop neighborhood. 2418 Under normal circumstances, the information recorded in these 2419 Information Bases is correct, i.e. corresponds to the actual network 2420 topology, apart from any changes which have not (yet) been tracked by 2421 the HELLO message exchanges. 2423 If a router for some reason, whether malice or malfunction, transmits 2424 invalid HELLO messages, incorrect information may be recorded in 2425 other routers' Information Bases. This protocol specification does, 2426 however, prevent inconsistent information from being included in the 2427 Information Bases through the specified processing, which maintains 2428 the constraints in Appendix B. The exact consequence of information 2429 inexactness depends on the use of these Information Bases, and SHOULD 2430 therefore be reflected in the specification of protocols which use 2431 information provided by this neighborhood discovery protocol. 2433 This section, therefore, firstly outlines the ways in which correctly 2434 formed, but still invalid, HELLO messages may appear, in 2435 Section 17.1. 2437 Injection of invalid HELLO messages into a network may be prevented 2438 by different means. If, for example, a network is deployed in a site 2439 to which access is strictly regulated, in order that physical access 2440 and proximity to the network is prevented, then further security 2441 mechanisms to protect against malicious routers injecting invalid 2442 HELLO messages may not be required. Similarly, if the link layer 2443 over which the network is formed provides appropriate 2444 confidentiality, authentication, and integrity, then this may, for a 2445 given deployment, suffice to appropriately protect against disclosure 2446 of information to an eavesdropper, and against a malicious router 2447 injecting invalid HELLO messages. In the latter case the link layer 2448 would discard frames that fail the link layer checks, without 2449 attempting to deliver such frames to IP. Finally, certain usage may 2450 be of a nature where disruption of service is of no consequence, or 2451 at least not of sufficient consequence to warrant deployment of 2452 additional security mechanisms. 2454 A further point to stress, and which follows from the discussions 2455 above is, that it will not be the case that "one size security fits 2456 all". Different deployments may have different requirements. For 2457 example in a deployment of a low value sensor network, authentication 2458 using a simple message authentication code and shared symmetric keys 2459 may suffice, while anything beyond that may require too many 2460 computational resources to be viable. Conversely, in, for example, a 2461 community network, verifying not only that the originator of a HELLO 2462 message "has the right key" but also the precise identity of the 2463 originator may be required to be proved, and computational resources 2464 may be available to make such a requirement feasible. 2466 Section 17.2, therefore, does not specify a single "one-size-fits- 2467 all" mechanism, but rather details how the security suggestions in 2468 [RFC5444] are considered for applicability within the context of this 2469 protocol, and with the purpose of aiding deployment-specific security 2470 mechanisms to be developed. 2472 17.1. Invalid HELLO messages 2474 A correctly formed, but still invalid, HELLO message may take any of 2475 the following forms. Note that a present or absent address object in 2476 an Address Block, does not by itself cause a problem. It is the 2477 presence, absence, or incorrectness of associated LOCAL_IF, 2478 LINK_STATUS and OTHER_NEIGHB Address Block TLVs that causes problems. 2480 A router may provide false information about its own identity: 2482 * The HELLO message may contain address objects with an 2483 associated LOCAL_IF Address Block TLV which do not correspond 2484 to addresses of interfaces of the router transmitting the HELLO 2485 message. 2487 * The HELLO message may omit network addresses, or their 2488 associated LOCAL_IF Address Block TLV, of interfaces of the 2489 router transmitting the HELLO message (other than the allowed 2490 omission of the only local interface network address of the 2491 MANET interface over which the HELLO message is transmitted, if 2492 that is the case). 2494 * The HELLO message may incorrectly specify the LOCAL_IF Address 2495 Block TLV Value associated with one or more local interface 2496 network addresses, indicating incorrectly whether they are 2497 associated with the MANET interface over which the HELLO 2498 message is transmitted. 2500 A router may provide false information about the identity of other 2501 routers: 2503 * A present LINK_STATUS Address Block TLV may, incorrectly, 2504 identify a network address as being of a MANET interface which 2505 is or was heard on the MANET interface over which the HELLO 2506 message is transmitted. 2508 * A consistently absent LINK_STATUS Address Block TLV may, 2509 incorrectly, fail to identify a network address as being of a 2510 MANET interface which is or was heard on the MANET interface 2511 over which the HELLO message is transmitted. 2513 * A present OTHER_NEIGHB Address Block TLV may, incorrectly, 2514 identify a network address as being of a router which is or was 2515 in the sending router's symmetric 1-hop neighborhood; 2517 * A consistently absent OTHER_NEIGHB Address Block TLV may, 2518 incorrectly, fail to identify a network address as being of a 2519 router which is or was in the sending router's symmetric 1-hop 2520 neighborhood; 2522 * The Value of a LINK_STATUS Address Block TLV may incorrectly 2523 indicate the status (LOST, SYMMETRIC or HEARD) of the link from 2524 a 1-hop neighbor. 2526 * The Value of an OTHER_NEIGHB Address Block TLV may incorrectly 2527 indicate the status (LOST or SYMMETRIC) of a symmetric 1-hop 2528 neighbor. 2530 17.2. Authentication, Integrity and Confidentiality Suggestions 2532 The security suggestions in [RFC5444] regarding inclusion of a 2533 cryptographic signature in a Message TLV or a Packet TLV can be 2534 applied to this protocol. Failure to verify either form of 2535 cryptographic signature should cause a HELLO message to be rejected 2536 without being processed. 2538 The following simplification of the suggestions for end-to-end 2539 authentication for integrity in [RFC5444] may be applied to HELLO 2540 messages: 2542 o As the Message Header fields and 2543 are either omitted or will always have the values 0 and 1, 2544 respectively, an end to end cryptographic signature can be 2545 calculated based on the entire HELLO message, including its 2546 unmodified Message Header. 2548 The security mechanisms suggested in [RFC5444] with respect to 2549 confidentiality can be directly applied to this protocol. 2551 18. IANA Considerations 2553 This specification defines one Message Type, which must be allocated 2554 from the "Message Types" repository of [RFC5444], and three Address 2555 Block TLV Types, which must be allocated from the "Address Block TLV 2556 Types" repository of [RFC5444]. 2558 18.1. Expert Review: Evaluation Guidelines 2560 For the registries where an Expert Review is required, the designated 2561 expert SHOULD take the same general recommendations into 2562 consideration as are specified by [RFC5444]. 2564 18.2. Message Types 2566 This specification defines one Message Type, to be allocated from the 2567 0-223 range of the "Message Types" namespace defined in [RFC5444], as 2568 specified in Table 3. 2570 +-------+------+-----------------+ 2571 | Name | Type | Description | 2572 +-------+------+-----------------+ 2573 | HELLO | TBD1 | Local signaling | 2574 +-------+------+-----------------+ 2576 Table 3: Message Type assignment 2578 18.3. Message-Type-specific TLV Type Registries 2580 IANA is requested to create a registry for Message-Type-specific 2581 Message TLVs for HELLO messages, in accordance with Section 6.2.1 of 2582 [RFC5444], and with initial assignments and allocation policies as 2583 specified in Table 4. 2585 +---------+-------------+-------------------+ 2586 | Type | Description | Allocation Policy | 2587 +---------+-------------+-------------------+ 2588 | 128-223 | Unassigned | Expert Review | 2589 +---------+-------------+-------------------+ 2591 Table 4: HELLO Message-Type-specific Message TLV Types 2593 IANA is requested to create a registry for Message-Type-specific 2594 Address Block TLVs for HELLO messages, in accordance with Section 2595 6.2.1 of [RFC5444], and with initial assignments and allocation 2596 policies as specified in Table 5. 2598 +---------+-------------+-------------------+ 2599 | Type | Description | Allocation Policy | 2600 +---------+-------------+-------------------+ 2601 | 128-223 | Unassigned | Expert Review | 2602 +---------+-------------+-------------------+ 2604 Table 5: HELLO Message-Type-specific Address Block TLV Types 2606 18.4. Address Block TLV Types 2608 This specification defines three Address Block TLV Types, which must 2609 be allocated from the "Address Block TLV Types" namespace defined in 2610 [RFC5444]. IANA are requested to make allocations in the 0-127 range 2611 for these types. This will create three new type extension 2612 registries with assignments as specified in Table 6, Table 7 and 2613 Table 8. Specifications of these Address Block TLVs are in 2614 Section 10.1.1, with Value Constants defined in Section 18.5. 2616 +------------+------+-----------+-----------------------------------+ 2617 | Name | Type | Type | Description | 2618 | | | extension | | 2619 +------------+------+-----------+-----------------------------------+ 2620 | LOCAL_IF | TBD2 | 0 | Specifies that the network | 2621 | | | | address is associated with a | 2622 | | | | local interface of the sending | 2623 | | | | router | 2624 | Unassigned | TBD2 | 1-255 | Expert Review | 2625 +------------+------+-----------+-----------------------------------+ 2627 Table 6: Address Block TLV Type assignment: LOCAL_IF 2629 +-------------+------+-----------+----------------------------------+ 2630 | Name | Type | Type | Description | 2631 | | | extension | | 2632 +-------------+------+-----------+----------------------------------+ 2633 | LINK_STATUS | TBD3 | 0 | Specifies the status of the link | 2634 | | | | from the indicated network | 2635 | | | | address (LOST, SYMMETRIC or | 2636 | | | | HEARD) | 2637 | Unassigned | TBD3 | 1-255 | Expert Review | 2638 +-------------+------+-----------+----------------------------------+ 2640 Table 7: Address Block TLV Type assignment: LINK_STATUS 2642 +--------------+------+-----------+---------------------------------+ 2643 | Name | Type | Type | Description | 2644 | | | extension | | 2645 +--------------+------+-----------+---------------------------------+ 2646 | OTHER_NEIGHB | TBD4 | 0 | Specifies that the network | 2647 | | | | address is (SYMMETRIC) or | 2648 | | | | recently was (LOST) of an | 2649 | | | | interface of a symmetric 1-hop | 2650 | | | | neighbor of the router | 2651 | | | | transmitting the message | 2652 | Unassigned | TBD4 | 1-255 | Expert Review | 2653 +--------------+------+-----------+---------------------------------+ 2655 Table 8: Address Block TLV Type assignment: OTHER_NEIGHB 2657 18.5. LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Values 2659 The Values which the LOCAL_IF Address Block TLV can use are the 2660 following: 2662 o THIS_IF := 0 2664 o OTHER_IF := 1 2666 The Values which the LINK_STATUS Address Block TLV can use are the 2667 following: 2669 o LOST := 0 2671 o SYMMETRIC := 1 2673 o HEARD := 2 2675 The Values which the OTHER_NEIGHB Address Block TLV can use are the 2676 following: 2678 o LOST := 0 2680 o SYMMETRIC := 1 2682 19. Contributors 2684 This specification is the result of the joint efforts of the 2685 following contributors, listed alphabetically. 2687 o Brian Adamson, NRL, USA, 2688 o Cedric Adjih, INRIA, France, 2690 o Thomas Heide Clausen, LIX, France, 2692 o Justin Dean, NRL, USA, 2694 o Christopher Dearlove, BAE Systems ATC, UK, 2695 2697 o Philippe Jacquet, INRIA, France, 2699 20. Acknowledgements 2701 The authors would like to acknowledge the team behind OLSRv1, 2702 specified in RFC3626 for their contributions. 2704 The authors would like to gratefully acknowledge the following people 2705 for intense technical discussions, early reviews and comments on the 2706 specification and its components (listed alphabetically): Alan Cullen 2707 (BAE Systems), Ulrich Herberg (LIX), Satoh Hiroki (Hitachi) Joe 2708 Macker (NRL), Charles E. Perkins (WiChorus), Laurent Viennot (INRIA), 2709 and the entire IETF MANET working group. 2711 21. References 2713 21.1. Normative References 2715 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2716 Requirement Levels", RFC 2119, BCP 14, March 1997. 2718 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 2719 considerations in MANETs", RFC 5148, February 2008. 2721 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2722 "Generalized MANET Packet/Message Format", RFC 5444, 2723 February 2009. 2725 [RFC5497] Clausen, T. and C. Dearlove, "Representing multi-value 2726 time in MANETs", RFC 5497, March 2009. 2728 [RFC5498] Chakeres, I., "IANA Allocations for MANET Protocols", 2729 RFC 5498, March 2009. 2731 21.2. Informative References 2733 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 2734 (MANET): Routing Protocol Performance Issues and 2735 Evaluation Considerations", RFC 2501, January 1999. 2737 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 2738 Routing Protocol", RFC 3626, October 2003. 2740 [RFC5449] Clausen, T., Baccelli, E., Nguyen, D., and P. Jacquet, 2741 "OSPF Multipoint Relay (MPR) Extension for Ad Hoc 2742 Networks", RFC 5449, February 2009. 2744 Appendix A. Address Block TLV Combinations 2746 The algorithm for generating HELLO messages in Section 11 specifies 2747 which 1-hop neighbor network addresses may be included in the Address 2748 Blocks, and with which associated Address Block TLVs. These Address 2749 Block TLVs may have Type = LINK_STATUS or Type = OTHER_NEIGHB, or 2750 both. Address Block TLVs with Type = LINK_STATUS may have three 2751 possible Values (Value = HEARD, Value = SYMMETRIC or Value = LOST), 2752 and Address Block TLVs of TYPE = OTHER_NEIGHB may have two possible 2753 Values (Value = SYMMETRIC or Value = LOST). When both Address Block 2754 TLVs are associated with the same network address only certain 2755 combinations of these Address Block TLV Values are necessary, and are 2756 the only combinations generated by the algorithm in Section 11. 2757 These combinations are indicated in Table 9. 2759 Cells labeled with "Yes" indicate the possible combinations which are 2760 generated by the algorithm in Section 11. Cells labeled with "No" 2761 indicate combinations not generated by the algorithm in Section 11, 2762 but which are correctly parsed and interpreted by the algorithm in 2763 Section 12. The cell labeled with "No*" is actually inconsistent, it 2764 is handled by ignoring the Address Block TLV with Type = 2765 OTHER_NEIGHB, but SHOULD NOT be used. 2767 +----------------+----------------+----------------+----------------+ 2768 | | Type = | Type = | Type = | 2769 | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | 2770 | | (absent) | Value = | Value = LOST | 2771 | | | SYMMETRIC | | 2772 +----------------+----------------+----------------+----------------+ 2773 | Type = | No | Yes | Yes | 2774 | LINK_STATUS | | | | 2775 | (absent) | | | | 2776 | Type = | Yes | Yes | Yes | 2777 | LINK_STATUS, | | | | 2778 | Value = HEARD | | | | 2779 | Type = | Yes | No | No* | 2780 | LINK_STATUS, | | | | 2781 | Value = | | | | 2782 | SYMMETRIC | | | | 2783 | Type = | Yes | Yes | No | 2784 | LINK_STATUS, | | | | 2785 | Value = LOST | | | | 2786 +----------------+----------------+----------------+----------------+ 2788 Table 9: LINK_STATUS and OTHER_NEIGHB TLV combinations 2790 Appendix B. Constraints 2792 Any process which updates the Local Information Base or the Neighbor 2793 Information Base MUST ensure that all constraints specified in this 2794 appendix are maintained. 2796 In each Local Interface Tuple: 2798 o I_local_iface_addr_list MUST NOT be empty. 2800 o I_local_iface_addr_list MUST NOT contain any duplicated network 2801 addresses. 2803 o If I_manet = true, then I_local_iface_addr_list MUST NOT contain 2804 any network address which overlaps any network address in the 2805 I_local_iface_addr_list of any other Local Interface Tuple with 2806 I_manet = true, unless it is known that the corresponding MANET 2807 interfaces will ALWAYS communicate with separate sets of MANET 2808 interfaces on other routers. 2810 In each Removed Interface Address Tuple: 2812 o IR_local_iface_addr MUST NOT contain any network address which is 2813 in the I_local_iface_addr_list of any Local Interface Tuple. 2815 o IR_local_iface_addr MUST NOT equal the IR_local_iface_addr of any 2816 other Removed Interface Address Tuple. 2818 In each Link Tuple: 2820 o L_neighbor_iface_addr_list MUST NOT be empty. 2822 o L_neighbor_iface_addr_list MUST NOT contain any network address 2823 which overlaps any network address in the I_local_iface_addr_list 2824 of any Local Interface Tuple or the IR_local_iface_addr of any 2825 Removed Interface Address Tuple. 2827 o L_neighbor_iface_addr_list MUST NOT contain any duplicated network 2828 addresses. 2830 o L_neighbor_iface_addr_list MUST NOT contain any network address 2831 which is in the L_neighbor_iface_addr_list of any other Link Tuple 2832 in the same Link Set. 2834 o If L_HEARD_time has not expired then there MUST be a Neighbor 2835 Tuple whose N_neighbor_addr_list contains 2836 L_neighbor_iface_addr_list. 2838 o L_HEARD_time MUST NOT be greater than L_time. 2840 o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are 2841 expired). 2843 o L_quality MUST NOT be less than 0 or greater than 1. 2845 o If L_quality >= HYST_ACCEPT then L_pending MUST be false. 2847 o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST. 2849 o L_pending MUST NOT be set to true if it is currently false. 2851 In each Neighbor Tuple: 2853 o N_neighbor_addr_list MUST NOT contain any network address which 2854 overlaps any network address in the I_local_iface_addr_list of any 2855 Local Interface Tuple or the IR_local_iface_addr of any Removed 2856 Interface Address Tuple. 2858 o N_neighbor_addr_list MUST NOT contain any duplicated network 2859 addresses. 2861 o N_neighbor_addr_list MUST NOT contain any network address which is 2862 in the N_neighbor_addr_list of any other Neighbor Tuple. 2864 o If N_symmetric is = true, then there MUST be one or more Link 2865 Tuples with: 2867 * L_neighbor_iface_addr_list contained in N_neighbor_addr_list; 2868 AND 2870 * L_status = SYMMETRIC. 2872 o If N_symmetric is = false, then there MUST be one or more Link 2873 Tuples with: 2875 * L_neighbor_iface_addr_list contained in N_neighbor_addr_list. 2877 All such Link Tuples MUST NOT have L_status = SYMMETRIC. At least 2878 one such Link Tuple MUST have L_HEARD_time not expired. 2880 In each Lost Neighbor Tuple: 2882 o NL_neighbor_addr MUST NOT overlap any network address in the 2883 I_local_iface_addr_list of any Local Interface Tuple or the 2884 IR_local_iface_addr of any Removed Interface Address Tuple. 2886 o NL_neighbor_addr MUST NOT equal the NL_neighbor_addr of any other 2887 Lost Neighbor Tuple. 2889 o NL_neighbor_addr MUST NOT be in the N_neighbor_addr_list of any 2890 Neighbor Tuple with N_symmetric = true. 2892 In each 2-Hop Tuple: 2894 o There MUST be a Link Tuple associated with the same MANET 2895 interface with: 2897 * L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list; AND 2899 * L_status = SYMMETRIC. 2901 o N2_2hop_addr MUST NOT overlap any network address in the 2902 I_local_iface_addr_list of any Local Interface Tuple or the 2903 IR_local_iface_addr of any Removed Interface Address Tuple. 2905 o N2_2hop_addr MUST NOT be the N2_2hop_addr of any other 2-Hop Tuple 2906 in the same 2-Hop Set and with the same 2907 N2_neighbor_iface_addr_list. 2909 o N2_2hop_addr MUST NOT be in the N2_neighbor_iface_addr_list of the 2910 same 2-Hop Tuple. 2912 Appendix C. HELLO Message Example 2914 An example HELLO message, transmitted by an originating router with a 2915 single MANET interface, is as follows. 2917 The message has Message Header containing hop-limit, hop-count and 2918 message sequence number (four bit Flags field value is 14). Its four 2919 bit Message Address Length field has value 3 and hence addresses in 2920 the message have length four octets, here being IPv4 addresses. The 2921 message is as transmitted with a hop limit of 1 and a hop count of 0. 2922 The overall message length is 45 octets. 2924 The message contains a Message TLV Block with content length 8 octets 2925 containing two Message TLVs, of types VALIDITY_TIME and 2926 INTERVAL_TIME. Each uses a Message TLV with Flags octet value 16, 2927 indicating that each has a Value. Each has a Value Length of 1 2928 octet; the Values included (0x64 and 0x58) are time codes 2929 representing the default values of parameters H_HOLD_TIME and 2930 HELLO_INTERVAL, respectively (6 seconds and 2 seconds) assuming the 2931 default value of constant C (1/1024 second). 2933 The message has a single Address Block containing 5 addresses. The 2934 Flags octet value 128 indicates an address Head but no address Tail, 2935 and no address prefixes. The Head Length of 3 octets indicates 2936 address Mid sections of one octet each (Mid 0 to Mid 4). 2938 The following Address Block TLV Block (content length 14 octets) 2939 includes two Address Block TLVs. The first is a LOCAL_IF Address 2940 Block TLV which (with Flags octet value 80) indicates that a single 2941 address, with index 0 (i.e. Head:Mid 0) is the single local 2942 interface address of this router (the 1 octet Value THIS_IF indicates 2943 that this address is of this interface). The second is a LINK_STATUS 2944 Address Block TLV which (with Flags octet value 48) specifies the 2945 link status values of all reported neighbors in a single multivalue 2946 Address Block TLV which covers the addresses with indexes 1 to 4. 2947 The Address Block TLV Value Length of 4 octets indicates one octet 2948 per Value per address. The last four addresses have associated link 2949 status, the first and second HEARD, the third SYMMETRIC, and the 2950 fourth LOST. 2952 0 1 2 3 2953 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 2954 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2955 | HELLO |1 1 1 0 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1| 2956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2957 |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number | 2958 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2959 |0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0| 2960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2961 |0 0 0 0 0 0 0 1|0 1 1 0 0 1 0 0| INTERVAL_TIME |0 0 0 1 0 0 0 0| 2962 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2963 |0 0 0 0 0 0 0 1|0 1 0 1 1 0 0 0|0 0 0 0 0 1 0 1|1 0 0 0 0 0 0 0| 2964 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2965 |0 0 0 0 0 0 1 1| Head | 2966 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2967 | Mid 0 | Mid 1 | Mid 2 | Mid 3 | 2968 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2969 | Mid 4 |0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0| LOCAL_IF | 2970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2971 |0 1 0 1 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 1| THIS_IF | 2972 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2973 | LINK_STATUS |0 0 1 1 0 0 0 0|0 0 0 0 0 0 0 1|0 0 0 0 0 1 0 0| 2974 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2975 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 2976 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2977 | LOST | 2978 +-+-+-+-+-+-+-+-+ 2980 Note that this example is for illustrative purposes. The essential 2981 information can be conveyed, more efficiently (assuming that the 2982 local interface address will be supplied by IP, and that the 2983 INTERVAL_TIME TLV is not needed) by the 29 octets: 2985 0 1 2 3 2986 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 2987 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2988 | 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| 2989 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2990 |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| 2991 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2992 |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| 2993 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2994 |0 0 0 0 0 0 1 1| Head | 2995 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2996 | Mid 1 | Mid 2 | Mid 3 | Mid 4 | 2997 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2998 |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| 2999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3000 |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | 3001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3002 | LOST | 3003 +-+-+-+-+-+-+-+-+ 3005 Appendix D. Flow and Congestion Control 3007 This protocol specifies one Message Type, the HELLO message. The 3008 maximum size of a HELLO message is proportional to the size of the 3009 originating router's 1-hop neighborhood. HELLO messages MUST NOT be 3010 forwarded. 3012 A router MUST report its 1-hop neighborhood in HELLO messages on each 3013 of its MANET interfaces at least each REFRESH_INTERVAL. This puts a 3014 lower bound on the control traffic generated by each router in the 3015 network employing this protocol. 3017 A router MUST ensure that two successive HELLO messages sent on the 3018 same MANET interface are separated by at least HELLO_MIN_INTERVAL. 3019 (If using jitter then this may be reduced to a mean minimum value of 3020 HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound 3021 on the control traffic generated by each router in the network 3022 employing this protocol. 3024 Appendix E. Interval and Timer Illustrations 3026 This informative appendix illustrates the relationship between 3027 message timers and intervals. (The adjustments to this timing when 3028 using timing jitter, as defined in [RFC5148], are not shown.) 3030 E.1. HELLO Message Generation Timing 3032 Figure 1 illustrates a basic HELLO message schedule for a router, on 3033 a MANET interface, employing strictly periodic transmission of HELLO 3034 messages. The router transmits a HELLO message each HELLO_INTERVAL. 3035 Each HELLO message contains all 1-hop neighbor network addresses of 3036 the router that are to be reported in any such HELLO message. (The 3037 parameter REFRESH_INTERVAL, not shown, is in this example equal to 3038 the parameter HELLO_INTERVAL.) 3040 The router includes a VALIDITY_TIME TLV in each HELLO message, 3041 encoding the parameter H_HOLD_TIME, the duration for which 3042 information received in the HELLO message should be considered valid 3043 by receiving routers. Receiving routers will, when recording the 3044 information received in the HELLO message, each use this for setting 3045 the L_HEARD_time, L_SYM_time and L_time elements of their 3046 corresponding Link Tuple, and the N2_time in the corresponding 2-Hop 3047 Tuple for each network address. Only L_time is illustrated in 3048 Figure 1. 3050 H_HOLD_TIME: |-----------------------------| ... 3052 HELLO_INTERVAL: |---------|---------|---------| ... 3054 Time: ---*---------*---------*---------*------> 3056 ^ ^ ^ ^ 3057 | | | | 3058 HELLO (a, b, c, d) | | | 3059 | | | 3060 HELLO (a, b, c, d) | | ... 3061 | | 3062 HELLO (a, b, c, d) | 3063 | 3064 HELLO (a, b, c, d) 3066 L_time: |-----------------------------| 3067 |-------------------- ... 3068 |---------- ... 3069 | ... 3071 Figure 1: HELLO message generation: regular schedule 3073 Figure 2 illustrates a message schedule similar to Figure 1, where 3074 the router announces its own presence more frequently by sending 3075 additional HELLO messages. HELLO messages are still sent regularly, 3076 at a reduced interval defined by a new value of HELLO_INTERVAL. 3077 However REFRESH_INTERVAL has not been reduced. Each 1-hop neighbor 3078 network address included in these HELLO messages need be advertised 3079 only once within each REFRESH_INTERVAL. Consequently the additional 3080 HELLO messages due to the reduced value of HELLO_INTERVAL may 3081 therefore be empty. (This is not the only allowed distribution of 3082 1-hop neighbor network addresses, they could, for example, be sent 3083 alternately a, b and c, d.) 3085 H_HOLD_TIME: |-----------------------------| ... 3087 REFRESH_INTERVAL: |---------|---------|---------| ... 3089 HELLO_INTERVAL: |----|----|----|----|----|----| ... 3091 Time: ---*---------*---------*---------*------> 3093 ^ ^ ^ ^ ^ ^ ^ 3094 | | | | | | | 3095 HELLO (a, b, c, d) | | | | | | 3096 | | | | | | 3097 HELLO () | | | | | 3098 | | | | | 3099 HELLO (a, b, c, d) | | | | 3100 | | | | ... 3101 HELLO () | | | 3102 | | | 3103 HELLO (a, b, c, d) | | 3104 | | 3105 HELLO () | 3106 | 3107 HELLO (a, b, c, d) 3109 L_time: |-----------------------------| 3110 |------------------------- ... 3111 |-------------------- ... 3112 |--------------- ... 3113 |---------- ... 3114 |----- ... 3115 | ... 3117 Figure 2: HELLO message generation: regular schedule with different 3118 HELLO_INTERVAL and REFRESH_INTERVAL 3120 HELLO messages may also be sent in response to events. The minimal 3121 interval between two successive HELLO message transmissions by a 3122 router is HELLO_MIN_INTERVAL, setting an upper bound of the HELLO 3123 message emission rate. Hence, for each HELLO message transmission, a 3124 router must wait at least HELLO_MIN_INTERVAL before the next HELLO 3125 message transmission. Similarly, the maximum interval between two 3126 successive HELLO message transmissions is HELLO_INTERVAL, setting a 3127 lower bound on the message transmission rate. Hence, for each HELLO 3128 message transmission, the router must ensure that the next HELLO 3129 message transmission must not wait more than HELLO_INTERVAL. 3131 Figure 3 illustrates a message schedule similar to Figure 1, but with 3132 HELLO messages responding to events at maximum rate, i.e. with HELLO 3133 messages being sent each HELLO_MIN_INTERVAL. Note that when a HELLO 3134 message is sent, it is assumed that the following messages may all be 3135 scheduled at an interval of HELLO_INTERVAL, and hence each HELLO 3136 message contains all 1-hop neighbor network addresses. In each HELLO 3137 message in this example, a new 1-hop neighbor network address is 3138 added, reflecting the changes occurring since the last HELLO message 3139 was sent. HELLO messages are sent at the maximum allowed rate in 3140 order to signal these changes as rapidly as possible. 3142 H_HOLD_TIME: |-----------------------------| ... 3144 HELLO_INTERVAL: |---------|---------|---------| ... 3146 HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... 3148 Time: ---*---------*---------*---------*------> 3150 ^ ^ ^ ^ ^ ^ ^ 3151 | | | | | | | 3152 HELLO () | | | | | | 3153 | | | | | | 3154 HELLO (a) | | | | | 3155 | | | | | 3156 HELLO (a, b) | | | | 3157 | | | | ... 3158 HELLO (a, b, c) | | | 3159 | | | 3160 HELLO (a, b, c, d) | | 3161 | | 3162 HELLO (a, b, c, d, e) | 3163 | 3164 HELLO (a, b, c, d, e, f) 3166 L_time: |-----------------------------| 3167 |------------------------- ... 3168 |-------------------- ... 3169 |--------------- ... 3170 |---------- ... 3171 |----- ... 3172 | ... 3174 Figure 3: HELLO message generation: regular schedule with responsive 3175 messages 3177 Figure 4 shows the same example as Figure 3, but with an increased 3178 REFRESH_INTERVAL, and showing partial HELLO messages which include 3179 only the necessary network addresses. 3181 H_HOLD_TIME: |-----------------------------| ... 3183 REFRESH_INTERVAL: |-------------------|---------- ... 3184 |-------------------|----- ... 3185 |-------------------| ... 3186 |--------------- ... 3187 |---------- ... 3188 |----- ... 3189 | ... 3191 HELLO_INTERVAL: |---------|---------|---------| ... 3193 HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... 3195 Time: ---*---------*---------*---------*------> 3197 ^ ^ ^ ^ ^ ^ ^ 3198 | | | | | | | 3199 HELLO () | | | | | | 3200 | | | | | | 3201 HELLO (a) | | | | | 3202 | | | | | 3203 HELLO (b) | | | | 3204 | | | | ... 3205 HELLO (c) | | | 3206 | | | 3207 HELLO (a, d) | | 3208 | | 3209 HELLO (b, e) | 3210 | 3211 HELLO (c, f) 3213 L_time: |-----------------------------| 3214 |------------------------- ... 3215 |-------------------- ... 3216 |--------------- ... 3217 |---------- ... 3218 |----- ... 3219 | ... 3221 Figure 4: HELLO message generation: regular schedule with responsive 3222 messages and different HELLO_INTERVAL and REFRESH_INTERVAL 3224 Figure 5 summarizes the overall relationship between the intervals 3225 governing HELLO message transmissions by a router. 3227 H_HOLD_TIME: |------------------------------------| 3229 REFRESH_INTERVAL: |----------------| 3231 HELLO_INTERVAL: |----------| 3233 HELLO_MIN_INTERVAL: |---| 3235 Time: -----------------------------------------------> 3237 ^ ^ ^ ^ ^ 3238 | | | | | 3239 | | | | Time until which 3240 HELLO message | | | received HELLO 3241 transmission | | | message content 3242 | | | is valid. 3243 | | | 3244 | | Time before which all 3245 | | neighbor information must 3246 | | be transmitted in HELLO 3247 | | messages (one or more) 3248 | | 3249 | Latest time for next HELLO message 3250 | transmission 3251 | 3252 Earliest time for next HELLO message 3253 transmission 3255 Figure 5: HELLO message generation intervals 3257 E.2. HELLO Message Processing Timing 3259 Figure 6 illustrates the Link Set timers when receiving a HELLO 3260 message not including the network address of the receiving MANET 3261 interface. 3263 VALIDITY_TIME: |--------------------------| 3265 L_time: |--------------------------| 3267 L_HEARD_time: |--------------------------| 3269 L_SYM_time: *-| (i.e. expired) 3271 Time: ---*--------------------------------> 3272 ^ 3273 | 3274 HELLO () received 3276 Figure 6: HELLO message processing: network address not present 3278 Figure 7 illustrates the Link Set timers when, following the received 3279 HELLO message illustrated in Figure 6, a router receives a HELLO 3280 message including the network address (a) of the receiving interface 3281 with link status = HEARD (or SYM). 3283 VALIDITY_TIME: |--------------------------| 3284 |--------------------------| 3286 L_time: |--------------------------| 3287 |--------------------------| 3289 L_HEARD_time: |--------------------------| 3290 |--------------------------| 3292 L_SYM_time: *-| (i.e. expired) 3293 L_SYM_time: |--------------------------| 3295 Time: -*-----*---------------------------------> 3296 ^ ^ 3297 | | 3298 HELLO () received | 3299 | 3300 HELLO (a:HEARD) received 3302 Figure 7: HELLO message processing: network address present 3304 Figure 8 illustrates the Link Set timers when, following the received 3305 HELLO messages illustrated in Figure 7, a router receives a HELLO 3306 message including the network address (a) of the receiving interface 3307 with link status = LOST. 3309 VALIDITY_TIME: |--------------------------| 3310 |--------------------------| 3311 |--------------------------| 3313 L_time: |--------------------------| 3314 |--------------------------| 3315 |--------------------------| 3317 L_HEARD_time: |--------------------------| 3318 |--------------------------| 3319 |--------------------------| 3321 L_SYM_time: *-| (i.e. expired) 3322 |--------------------------| 3323 *-| (i.e. expired) 3325 Time: -*-----*-----*---------------------------------> 3326 ^ ^ ^ 3327 | | | 3328 HELLO () received | | 3329 | | 3330 HELLO (a:HEARD) received | 3331 | 3332 HELLO (a:LOST) received 3334 Figure 8: HELLO message processing: network address lost 3336 E.3. Other HELLO Message Timing 3338 There are three other timing parameters which are used by a router to 3339 control HELLO message generation and processing. 3341 Figure 9 illustrates the time, with duration L_HOLD_TIME, during 3342 which the appropriate network addresses of a formerly, but no longer, 3343 symmetric 1-hop neighbor, as connected by this MANET interface, are 3344 advertised as LOST using a LINK_STATUS TLV in HELLO messages on this 3345 MANET interface, thus allowing that 1-hop neighbor to update its Link 3346 Set accordingly. 3348 L_HOLD_TIME: |----------------------------| 3350 Time: ---*----------------------------------> 3351 ^ ^ 3352 | | 3353 Formerly symmetric 1-hop neighbor | 3354 ceases to be symmetric on this | 3355 MANET interface | 3356 | 3357 Time until which network addresses of 3358 this neighbor connected using this MANET 3359 interface are advertised in HELLO 3360 messages on this MANET interface 3361 using a LINK_STATUS TLV, Value = LOST 3363 Figure 9: HELLO message generation: advertisement of formerly 3364 symmetric 1-hop neighbor on this MANET interface as lost 3366 Figure 10 illustrates the time, with duration N_HOLD_TIME, during 3367 which all network addresses of a formerly, but no longer, symmetric 3368 1-hop neighbor, are advertised as LOST in HELLO messages on all MANET 3369 interfaces using an OTHER_NEIGHB TLV (if not also reported using a 3370 LINK_STATUS TLV) thus allowing all other symmetric 1-hop neighbors to 3371 update their 2-Hop Sets accordingly. 3373 L_HOLD_TIME: |----------------------------| 3375 Time: ---*----------------------------------> 3376 ^ ^ 3377 | | 3378 Formerly symmetric 1-hop neighbor | 3379 ceases to be symmetric | 3380 | 3381 Time until which network addresses of 3382 this neighbor are advertised in HELLO 3383 messages on all MANET interfaces 3384 using an OTHER_NEIGHB TLV, 3385 Value = LOST 3387 Figure 10: HELLO message generation: advertisement of formerly 3388 symmetric 1-hop neighbor on any MANET interface as lost 3390 Figure 11 illustrates the time, with duration I_HOLD_TIME, during 3391 which a formerly, but no longer, used local interface network address 3392 is excluded from being considered as a 2-hop neighbor network address 3393 (in order that a router is not recorded as its own 2-hop neighbor 3394 during that period). 3396 I_HOLD_TIME: |----------------------------| 3398 Time: ---*-----------------------------------> 3399 ^ ^ 3400 | | 3401 Formerly used local interface | 3402 network address ceases to be | 3403 assigned to a local interface | 3404 | 3405 Time until which this network 3406 address is excluded from being 3407 included in this router's 2-Hop Set 3409 Figure 11: Local interface removed network address 3411 Appendix F. Topology Pictures 3413 This appendix illustrates various examples of physical topologies, as 3414 well as how these are logically recorded by NHDP from the point of 3415 view of the router A. This representation is a composite of 3416 information which would be contained within A's various Information 3417 Bases after NHDP has been running for sufficiently long time for the 3418 state to converge. 3420 Note that the examples given in this appendix are NOT exhaustive, but 3421 are selected to be illustrative of NHDP neighborhood representations 3422 of physical MANET topologies. 3424 The example topologies presented contain 3 physical routers A, B and 3425 C. Each of these routers has one or two distinct interfaces, denoted 3426 "top" and "bottom". Each interface has one or two addresses, and 3427 symmetric connectivity between a pair of interfaces is illustrated by 3428 these being connected by a line. 3430 In all examples, the topology is described as it is recorded by NHDP 3431 in router A. 3433 F.1. Example 1: Standard Single Interface Topology 3435 In Figure 12, each router has a single interface, each with a single 3436 IP address. This is the simplest possible network, and the resulting 3437 representation is given to the right in Figure 12. 3439 __________ __________ 3440 | | | 3441 {1} {2} {3} 3442 | | | {1}--------{2}--------{3} 3443 +--'--+ +--'--+ +--'--+ 3444 | A | | B | | C | 3445 +-----+ +-----+ +-----+ 3447 Figure 12: Standard single interface topology (left), and 3448 corresponding NHDP representation (right) 3450 The Local Information Set in A contains a single Local Interface 3451 Tuple which has an I_local_iface_addr_list of {1}. This value is 3452 denoted with a {1} on the leftmost part of the resulting 3453 representation. 3455 The Interface Information Base has only one Link Set, which 3456 represents the "top" interface of A, or {1}. This Link Set's only 3457 Link Tuple has an L_neighbor_iface_addr_list containing {2}; this 3458 corresponds to the dashed line from {1} to {2} to the right in 3459 Figure 12. The 2-Hop Set contains a single 2-Hop Tuple, with 3460 N2_neighbor_iface_addr_list being {2} and N2_hop_addr being {3}; this 3461 corresponds to the dashed line from {2} to {3} to the right in 3462 Figure 12. 3464 The descriptions of the following examples in this appendix will be 3465 derived similarly, and use the same notational conventions. 3467 F.2. Example 2: Dual Addressed Interface on One Hop Neighbor 3469 In Figure 13, the network is identical to that in Example 1, except 3470 that the middle router, B, has two IP addresses on its single 3471 interface. 3473 __________ __________ 3474 | | | 3475 {1} {2,4} {3} 3476 | | | {1}-------{2,4}-------{3} 3477 +--'--+ +--'--+ +--'--+ 3478 | A | | B | | C | 3479 +-----+ +-----+ +-----+ 3481 Figure 13: Single interfaces, with 1-hop neighbor B having two 3482 addresses (left), and corresponding NHDP representation (right) 3484 The content of the Interface Information Base is in this case 3485 identical to Example 1, except that L_neighbor_iface_addr_list is 3486 {2,4} and N2_neighbor_iface_addr_list is {2,4}. 3488 F.3. Example 3: Dual Addressed Interface on Two Hop Neighbor 3490 In Figure 14, the network is identical to that in Example 1, except 3491 that the rightmost router, C, has two IP addresses on its interface. 3493 __________ __________ 3494 | | | 3495 {1} {2} {3,4} _.---{3} 3496 | | | {1}--------{2}--<_ 3497 +--'--+ +--'--+ +--'--+ '---{4} 3498 | A | | B | | C | 3499 +-----+ +-----+ +-----+ 3501 Figure 14: Single interfaces, with 2-hop neighbor C having two 3502 addresses (left), and corresponding NHDP representation (right) 3504 The content of the Interface Information Base is in this case 3505 identical to than in Example 1, except that the 2-Hop Set contains an 3506 extra 2-Hop Tuple with N2_neighbor_iface_addr_list being {2} and 3507 N2_hop_addr being {4}. These two 2-Hop Tuples are illustrated by the 3508 two lines from {2} to {3} and (2) to {4}, respectively. 3510 F.4. Example 4: Dual Addressed Interfaces 3512 In Figure 15, the network is identical to that in Example 1, except 3513 that all routers have two IP addresses on their interface. The Local 3514 Information Base in router A is the same as in Example 1, except that 3515 I_local_iface_addr_list is {1,5}. 3517 __________ __________ 3518 | | | 3519 {1,5} {2,6} {3,4} _.---{3} 3520 | | | {1,5}------{2,6}-<_ 3521 +--'--+ +--'--+ +--'--+ '---{4} 3522 | A | | B | | C | 3523 +-----+ +-----+ +-----+ 3525 Figure 15: Single interfaces, all routers having two addresses 3526 (left), and corresponding NHDP representation (right) 3528 The content of the Interface Information Base is in this case a 3529 combination of the Interface Information Bases from Example 1, 3530 Example 2 and Example 3. 3532 F.5. Example 5: Dual Interface on Two Hop Neighbor 3534 In Figure 16, all routers have a single IP address on each interface, 3535 and with the 2-hop neighbor having two interfaces. 3537 __________ __________ 3538 | | | 3539 {1} {2} {3} _.---{3} 3540 | | | {1}--------{2}--<_ 3541 +--'--+ +--'--+ +-----+ '---{4} 3542 | A | | B | | C | 3543 +-----+ +-----+ +-----+ 3544 | 3545 {4} 3547 Figure 16: Single addresses, with 2-hop neighbor C having two 3548 interfaces (left), and corresponding NHDP representation (right) 3550 The Interface Information Base is identical to that in Example 3; 3551 NHDP does not distinguish topologically between this example and 3552 Example 3. 3554 F.6. Example 6: Dual interface on One Hop Neighbor 3556 In Figure 17, all routers have a single IP address on each interface, 3557 and with the 1-hop neighbor having two interfaces. 3559 __________ 3560 | | 3561 {1} {2} ,-. 3562 | | {1}-------/{2}\-------{4} 3563 +--'--+ +--'--+ +-----+ \{5}/ 3564 | A | | B | | C | `-' 3565 +-----+ +-----+ +-----+ 3566 | | 3567 {5} {4} 3568 |__________| 3570 Figure 17: Single addresses, with 1-hop neighbor B having two 3571 interfaces (left), and corresponding NHDP representation (right) 3573 The Local Information Base is identical to that in Example 1. 3575 The Interface Information Base has only one Link Set containing one 3576 Link Tuple with L_neighbor_iface_addr_list being {2}. The 2-Hop Set 3577 contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being 3578 {2} and N2_hop_addr being {4}. 3580 The Neighbor Information Base contains a Neighbor Set containing a 3581 single Neighbor Tuple, which represents router B, with 3582 N_neighbor_addr_list being {2,5}. This entry is represented on the 3583 right of Figure 17 by circling {2} with {5}. 3585 Note that router A does not have information indicating which of 3586 router B's interfaces is connected to router C. However, router A 3587 knows that the address {4} (and thus router C) is reachable by using 3588 {2} as next hop. 3590 F.7. Example 7: Dual Interface on One and Two Hop Neighbors 3592 In Figure 18, all routers have a single IP address on each interface, 3593 and both the 1-hop and 2-hop neighbors have two interfaces. 3594 Furthermore, there are now two physical links between routers B and 3595 C, over distinct interface pairs. 3597 __________ __________ 3598 | | | 3599 {1} {2} {3} ,-. _.---{3} 3600 | | | {1}-------/{2}\--<_ 3601 +--'--+ +--'--+ +-----+ \{5}/ '---{4} 3602 | A | | B | | C | `-' 3603 +-----+ +-----+ +-----+ 3604 | | 3605 {5} {4} 3606 |__________| 3608 Figure 18: Single addresses, with 1-hop and 2-hop neighbors B and C 3609 having two interfaces (left), and corresponding NHDP representation 3610 (right) 3612 The Local Information Base is identical to that in Example 1. 3614 The Link Set is identical to that in Example 6, and the 2-Hop Set 3615 contains, as in Example 5 (and similarly to Examples 3 and 4), two 3616 2-Hop Tuples representing the two links between routers B and C 3618 Note that router A does not have information describing which of 3619 router B's interfaces is connected to which interfaces of router C, 3620 or even that the interfaces with addresses {3} and {4} are interfaces 3621 of the same router. However, router A knows that the addresses {3} 3622 and {4} (and thus router C) are reachable using {2} as next hop. 3624 F.8. Example 8: Dual Interface Locally and on One Hop Neighbor 3626 In Figure 19, all routers have a single IP address on each interface, 3627 and both A and its the 1-hop neighbor B have two interfaces. 3628 Furthermore, there are now two physical links between routers A and 3629 B, over distinct interface pairs. 3631 __________ __________ 3632 | | | ,-. 3633 {1} {2} {3} {1}-------/{2}\--------{3} 3634 | | | \{5}/ 3635 +--'--+ +--'--+ +-----+ `-' 3636 | A | | B | | C | 3637 +-----+ +-----+ +-----+ ,-. 3638 | | /{2}\ 3639 {6} {5} {6}-------\{5}/--------{3} 3640 |__________| `-' 3642 Figure 19: Single addresses, with both A and 1-hop neighbor B having 3643 two interfaces (left), and corresponding NHDP representation (right) 3645 The Local Information Set contains two Local Interface Tuples, with 3646 I_local_iface_addr_list of {1} and {6}, respectively. 3648 Each Interface Information Base's Link Set contains one Link Tuple, 3649 representing the links between {1} and {2}, and between {6} and {5}, 3650 respectively. The 2-Hop Set for interface {1} contains a single 3651 2-Hop Tuple, with N2_neighbor_iface_addr_list being {2} and 3652 N2_hop_addr being {3}. The 2-Hop Set for interface {6} contains a 3653 single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {5} and 3654 N2_hop_addr being {3}. 3656 The Neighbor Information Base contains a Neighbor Set containing a 3657 single Neighbor Tuple, which represents router B, with 3658 N_neighbor_addr_list being {2,5}. This entry is denoted by circling 3659 {2} with {5}. 3661 F.9. Example 9: Dual Interface on All Routers 3663 In Figure 20, all routers have a single IP address on each interface, 3664 and all routers have two interfaces. Furthermore, there are now two 3665 physical links between A and B, over distinct interface pairs, and 3666 two physical links between B and C, also over distinct interface 3667 pairs. 3669 __________ __________ 3670 | | | ,-. _.---{3} 3671 {1} {2} {3} {1}-------/{2}\--<_ 3672 | | | \{5}/ '---{4} 3673 +--'--+ +--'--+ +-----+ `-' 3674 | A | | B | | C | 3675 +-----+ +-----+ +-----+ ,-. 3676 | | | /{2}\ _.---{3} 3677 {6} {5} {4} {6}-------\{5}/--<_ 3678 |__________|__________| `-' '---{4} 3680 Figure 20: Single addresses, with all routers having two interfaces 3681 (left), and corresponding NHDP representation (right) 3683 The Local Information Set is identical to that in Example 8. The 3684 Interface Information Base for each interface in A is also identical 3685 to that in Example 8, except that an additional 2-Hop Tuple is 3686 present in each 2-Hop Set, each representing the link between router 3687 B and the interface of router C with address {4}. 3689 As in Example 7, router A does not have information describing which 3690 of router B's interfaces is connected to which interface of C, or 3691 even that the interfaces with addresses {3} and {4} are interfaces of 3692 the same router. However, router A knows that the addresses {3} and 3693 {4} (and router C) are reachable by using {2} or {5} (depending on 3694 via which of its local interfaces) as next hop. 3696 F.10. Example 10: Dual Addressed Dual Interfaces on All Routers 3698 In Figure 21, all routers have two IP addresses on each interface, 3699 and all routers have two interfaces. Furthermore, there are now two 3700 physical links between A and B, over distinct interface pairs, and 3701 two physical links between B and C, also over distinct interface 3702 pairs. 3704 __________ __________ _ _.--{9} 3705 | | | ,' `. _.-<__-{10} 3706 {1,2} {5,6} {9,10} {1,2}--|{5,6}|-<_ __ 3707 | | | |{7,8}| '-<_ -{11} 3708 +--'--+ +--'--+ +-----+ `._,' '-{12} 3709 | A | | B | | C | _ 3710 +-----+ +-----+ +-----+ ,' `. _.--{9} 3711 | | | |{5,6}| _.-<__-{10} 3712 {3,4} {7,8} {11,12} {3,4}--|{7,8}|-<_ __ 3713 |__________|__________| `._,' '-<_ -{11} 3714 '-{12} 3716 Figure 21: Dual addresses, with all routers having two interfaces 3717 (left) and corresponding NHDP representation (right) 3719 This example is the combination of all the preceding examples in this 3720 appendix. The Local Information Set in A contains Local Information 3721 Tuples for each of its interfaces, and each Interface Information 3722 Base contains in its Link Set a representation of links {1,2}-{5,6} 3723 or {3,4}-{7,8}, respectively. The Neighbor Set (in the Neighbor 3724 Information Base) records the existence of router B and all of its 3725 addresses on all its interfaces, i.e. {5,6,7,8}. 3727 As in Example 9, each interface address of router C is represented in 3728 the 2-Hop Set of each Interface Information Base as a link from 3729 router B to each of these addresses. Router A does not have 3730 information describing which of router B's interfaces is connected to 3731 which interface of C, nor that the addresses {9}, {10}, {11}, and 3732 {12} are addresses of the same router (or that some of these, such as 3733 {9} and {10}, are addresses on the same interface of the router). 3735 F.11. Example 11: Single Addressed Dual Interface Locally 3737 In Figure 22, all routers have a single interface, except for router 3738 A which has two. Each of A's two interfaces has a link with the 3739 single interface of router B. All interfaces have a single address. 3741 __________ __________ 3742 | _____| | 3743 {1} | {2} {3} {1}--------{2}---------{3} 3744 | | | | 3745 +--'--+ | +--'--+ +-----+ 3746 | A | | | B | | C | 3747 +-----+ | +-----+ +-----+ 3748 | | 3749 {6} | {6}--------{2}---------{3} 3750 |____| 3752 Figure 22: Single addresses, with A having two interfaces, both 3753 linked to the single interface of B (left), and corresponding NHDP 3754 representation (right) 3756 This is similar to Example 8, except that the single address {2} also 3757 replaces the address {5}. In particular both Link Tuples (one in 3758 each Link Set, each in its corresponding Interface Information Base) 3759 have L_neighbor_iface_addr_list being {2}, the Neighbor Set (in the 3760 Neighbor Information Base) contains a single Neighbor Tuple with 3761 N_neighbor_addr_list being {2}, and both 2-Hop Tuples (one in each 3762 2-Hop Set, each in its corresponding Interface Information Base) have 3763 N2_neighbor_iface_list being {2} and N2_2hop_addr being {3}. 3765 Authors' Addresses 3767 Thomas Heide Clausen 3768 LIX, Ecole Polytechnique 3770 Phone: +33 6 6058 9349 3771 EMail: T.Clausen@computer.org 3772 URI: http://www.ThomasClausen.org/ 3774 Christopher Dearlove 3775 BAE Systems ATC 3777 Phone: +44 1245 242194 3778 EMail: chris.dearlove@baesystems.com 3779 URI: http://www.baesystems.com/ 3780 Justin W. Dean 3781 Naval Research Laboratory 3783 Phone: +1 202 767 3397 3784 EMail: jdean@itd.nrl.navy.mil 3785 URI: http://pf.itd.nrl.navy.mil/ 3787 The OLSRv2 Design Team 3788 MANET Working Group