idnits 2.17.1 draft-ietf-manet-olsrv2-10.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 1091 has weird spacing: '...ig_addr is a ...' == Line 1094 has weird spacing: '... O_time speci...' == Line 1110 has weird spacing: '...et_addr is th...' == Line 1115 has weird spacing: '...AL_dist is th...' == Line 1140 has weird spacing: '...ig_addr is th...' == (36 more instances...) == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: o AL_net_addr MUST not equal this router's originator address, or equal the O_orig_addr in any Originator Tuple. -- 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 (September 25, 2009) is 5326 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 ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) == Outdated reference: A later version (-15) exists of draft-ietf-manet-nhdp-10 Summary: 3 errors (**), 0 flaws (~~), 9 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: March 29, 2010 BAE Systems ATC 6 P. Jacquet 7 Project Hipercom, INRIA 8 The OLSRv2 Design Team 9 MANET Working Group 10 September 25, 2009 12 The Optimized Link State Routing Protocol version 2 13 draft-ietf-manet-olsrv2-10 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 March 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 version 2 of the Optimized Link State Routing 61 (OLSRv2) protocol for Mobile Ad hoc NETworks (MANETs). 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 66 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 67 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 8 68 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 9 69 4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 9 70 4.2. Routers and Interfaces . . . . . . . . . . . . . . . . . . 11 71 4.3. Information Base Overview . . . . . . . . . . . . . . . . 12 72 4.3.1. Local Information Base . . . . . . . . . . . . . . . . 12 73 4.3.2. Interface Information Bases . . . . . . . . . . . . . 12 74 4.3.3. Neighbor Information Base . . . . . . . . . . . . . . 13 75 4.3.4. Topology Information Base . . . . . . . . . . . . . . 13 76 4.3.5. Received Message Information Base . . . . . . . . . . 14 77 4.4. Signaling Overview . . . . . . . . . . . . . . . . . . . . 15 78 4.5. Routing Set . . . . . . . . . . . . . . . . . . . . . . . 16 79 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 16 80 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 17 81 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 17 82 5.3. Local History Times . . . . . . . . . . . . . . . . . . . 17 83 5.4. Message Intervals . . . . . . . . . . . . . . . . . . . . 18 84 5.5. Advertised Information Validity Times . . . . . . . . . . 18 85 5.6. Received Message Validity Times . . . . . . . . . . . . . 19 86 5.7. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 20 87 5.8. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 20 88 5.9. Willingness . . . . . . . . . . . . . . . . . . . . . . . 21 89 5.10. Parameter Change Constraints . . . . . . . . . . . . . . . 21 90 6. Information Bases . . . . . . . . . . . . . . . . . . . . . . 22 91 6.1. Local Information Base . . . . . . . . . . . . . . . . . . 23 92 6.1.1. Originator Set . . . . . . . . . . . . . . . . . . . . 23 93 6.1.2. Local Attached Network Set . . . . . . . . . . . . . . 24 94 6.2. Neighbor Information Base . . . . . . . . . . . . . . . . 24 95 6.3. Topology Information Base . . . . . . . . . . . . . . . . 25 96 6.3.1. Advertising Remote Router Set . . . . . . . . . . . . 26 97 6.3.2. Router Topology Set . . . . . . . . . . . . . . . . . 26 98 6.3.3. Routable Address Topology Set . . . . . . . . . . . . 27 99 6.3.4. Attached Network Set . . . . . . . . . . . . . . . . . 27 100 6.3.5. Routing Set . . . . . . . . . . . . . . . . . . . . . 28 101 6.4. Received Message Information Base . . . . . . . . . . . . 28 102 6.4.1. Received Set . . . . . . . . . . . . . . . . . . . . . 29 103 6.4.2. Processed Set . . . . . . . . . . . . . . . . . . . . 29 104 6.4.3. Forwarded Set . . . . . . . . . . . . . . . . . . . . 30 105 6.5. Corresponding Protocol Tuples . . . . . . . . . . . . . . 30 106 7. Message Processing and Forwarding . . . . . . . . . . . . . . 31 107 7.1. Actions when Receiving a Message . . . . . . . . . . . . . 32 108 7.2. Message Considered for Processing . . . . . . . . . . . . 32 109 7.3. Message Considered for Forwarding . . . . . . . . . . . . 33 110 8. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 35 111 8.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 36 112 8.1.1. HELLO Message TLVs . . . . . . . . . . . . . . . . . . 37 113 8.1.2. HELLO Message Address Block TLVs . . . . . . . . . . . 37 114 8.2. TC Messages . . . . . . . . . . . . . . . . . . . . . . . 37 115 8.2.1. TC Message TLVs . . . . . . . . . . . . . . . . . . . 39 116 8.2.2. TC Message Address Block TLVs . . . . . . . . . . . . 39 117 9. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 40 118 9.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 41 119 10. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 41 120 10.1. Updating Willingness . . . . . . . . . . . . . . . . . . . 42 121 10.2. Updating MPR Selectors . . . . . . . . . . . . . . . . . . 42 122 11. TC Message Generation . . . . . . . . . . . . . . . . . . . . 43 123 11.1. TC Message Transmission . . . . . . . . . . . . . . . . . 44 124 12. TC Message Processing . . . . . . . . . . . . . . . . . . . . 45 125 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 45 126 12.2. TC Message Processing Definitions . . . . . . . . . . . . 47 127 12.3. Initial TC Message Processing . . . . . . . . . . . . . . 47 128 12.3.1. Populating the Advertising Remote Router Set . . . . . 48 129 12.3.2. Populating the Router Topology Set . . . . . . . . . . 48 130 12.3.3. Populating the Routable Address Topology Set . . . . . 49 131 12.3.4. Populating the Attached Network Set . . . . . . . . . 49 132 12.4. Completing TC Message Processing . . . . . . . . . . . . . 50 133 12.4.1. Purging the Router Topology Set . . . . . . . . . . . 50 134 12.4.2. Purging the Routable Address Topology Set . . . . . . 50 135 12.4.3. Purging the Attached Network Set . . . . . . . . . . . 51 136 13. Information Base Changes . . . . . . . . . . . . . . . . . . . 51 137 13.1. Originator Address Changes . . . . . . . . . . . . . . . . 51 138 13.2. Neighbor State Changes . . . . . . . . . . . . . . . . . . 51 139 13.3. Advertised Neighbor Changes . . . . . . . . . . . . . . . 52 140 13.4. Advertising Remote Router Tuple Expires . . . . . . . . . 52 141 13.5. Neighborhood Changes and MPR Updates . . . . . . . . . . . 53 142 13.6. Routing Set Updates . . . . . . . . . . . . . . . . . . . 54 143 14. Selecting MPRs . . . . . . . . . . . . . . . . . . . . . . . . 54 144 15. Routing Set Calculation . . . . . . . . . . . . . . . . . . . 56 145 15.1. Network Topology Graph . . . . . . . . . . . . . . . . . . 56 146 15.2. Populating the Routing Set . . . . . . . . . . . . . . . . 58 147 16. Proposed Values for Parameters and Constants . . . . . . . . . 59 148 16.1. Local History Time Parameters . . . . . . . . . . . . . . 59 149 16.2. Message Interval Parameters . . . . . . . . . . . . . . . 59 150 16.3. Advertised Information Validity Time Parameters . . . . . 59 151 16.4. Received Message Validity Time Parameters . . . . . . . . 60 152 16.5. Jitter Time Parameters . . . . . . . . . . . . . . . . . . 60 153 16.6. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 60 154 16.7. Willingness Parameter and Constants . . . . . . . . . . . 60 155 17. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 60 156 18. Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 61 157 19. Security Considerations . . . . . . . . . . . . . . . . . . . 62 158 19.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . 62 159 19.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 62 160 19.3. Interaction with External Routing Domains . . . . . . . . 63 161 20. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 64 162 20.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 64 163 20.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 64 164 20.3. Message-Type-specific TLV Type Registries . . . . . . . . 64 165 20.4. Message TLV Types . . . . . . . . . . . . . . . . . . . . 65 166 20.5. Address Block TLV Types . . . . . . . . . . . . . . . . . 66 167 21. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 67 168 22. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 68 169 23. References . . . . . . . . . . . . . . . . . . . . . . . . . . 68 170 23.1. Normative References . . . . . . . . . . . . . . . . . . . 68 171 23.2. Informative References . . . . . . . . . . . . . . . . . . 69 172 Appendix A. Example Algorithm for Calculating MPRs . . . . . . . 69 173 A.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 70 174 A.2. MPR Selection Algorithm for each OLSRv2 Interface . . . . 71 175 Appendix B. Example Algorithm for Calculating the Routing Set . . 71 176 B.1. Local Interfaces and Neighbors . . . . . . . . . . . . . . 72 177 B.2. Add Neighbor Routers . . . . . . . . . . . . . . . . . . . 72 178 B.3. Add Remote Routers . . . . . . . . . . . . . . . . . . . . 73 179 B.4. Add Neighbor Addresses . . . . . . . . . . . . . . . . . . 73 180 B.5. Add Remote Routable Addresses . . . . . . . . . . . . . . 74 181 B.6. Add Attached Networks . . . . . . . . . . . . . . . . . . 74 182 B.7. Add 2-Hop Neighbors . . . . . . . . . . . . . . . . . . . 75 183 Appendix C. Example Message Layout . . . . . . . . . . . . . . . 76 184 Appendix D. Constraints . . . . . . . . . . . . . . . . . . . . . 77 185 Appendix E. Flow and Congestion Control . . . . . . . . . . . . . 81 187 1. Introduction 189 The Optimized Link State Routing protocol version 2 (OLSRv2) is an 190 update to OLSRv1 as published in [RFC3626]. Compared to [RFC3626], 191 OLSRv2 retains the same basic mechanisms and algorithms, while using 192 a more flexible and efficient signaling framework, and includes some 193 simplification of the messages being exchanged. 195 OLSRv2 is developed for mobile ad hoc networks. It operates as a 196 table driven, proactive protocol, i.e. it exchanges topology 197 information with other routers in the network regularly. OLSRv2 is 198 an optimization of the classical link state routing protocol. Its 199 key concept is that of MultiPoint Relays (MPRs). Each router selects 200 a set of its neighbor routers (which "cover" all of its symmetrically 201 connected 2-hop neighbor routers) as MPRs. MPRs are then used to 202 achieve both flooding reduction and topology reduction. 204 Flooding reduction is achieved by control traffic being flooded 205 through the network using hop by hop forwarding, but with a router 206 only needing to forward control traffic which is first received 207 directly from one of the routers which have selected it as an MPR 208 (its "MPR selectors"). This mechanism, denoted "MPR flooding", 209 provides an efficient mechanism for information distribution within 210 the MANET by reducing the number of transmissions required. 212 Topology redction is achieved by a mechanism where the routers 213 selected as MPRs have a special responsibility when declaring link 214 state information in the network. A sufficient requirement for 215 OLSRv2 to provide shortest (lowest hop count) routes to all 216 destinations is that routers declare link state information for their 217 MPR selectors, if any. Routers which are not selected as MPRs need 218 not send any link state information. Additional available link state 219 information may be transmitted, e.g. for redundancy. Thus the use of 220 MPRs allows reduction of the number and the size of link state 221 messages, and in the amount of link state information maintained in 222 each router. Based on this reduced link state information, MPRs are 223 used as intermediate routers in multi-hop routes. 225 A router selects MPRs from among its one hop neighbors connected by 226 "symmetric", i.e. bidirectional, links. Therefore, selecting routes 227 through MPRs avoids the problems associated with data packet transfer 228 over unidirectional links (such as the problem of not getting link 229 layer acknowledgments at each hop, for link layers employing this 230 technique). 232 OLSRv2 uses and extends [NHDP] and uses [RFC5444], [RFC5497] and, 233 optionally, [RFC5148]. These other protocols and specifications were 234 all originally created as part of OLSRv2, but have been specified 235 separately for wider use. 237 OLSRv2 makes no assumptions about the underlying link layer. OLSRv2, 238 through its use of [NHDP], may use link layer information and 239 notifications when available and applicable. 241 OLSRv2, as OLSRv1, inherits its concept of forwarding and relaying 242 from HIPERLAN (a MAC layer protocol) which is standardized by ETSI 243 [HIPERLAN], [HIPERLAN2]. 245 2. Terminology 247 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 248 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 249 "OPTIONAL" in this document are to be interpreted as described in 250 [RFC2119]. 252 All terms introduced in [RFC5444], including "packet", "message", 253 "Address Block", "TLV Block", and "TLV", are to be interpreted as 254 described there. 256 All terms introduced in [NHDP], including "interface", "MANET 257 interface", "address", "symmetric link", "symmetric 1-hop neighbor", 258 "symmetric 2-hop neighbor", "constant", "interface parameter", and 259 "router parameter", are to be interpreted as described there. 261 Additionally, this document uses the following terminology: 263 Router - A MANET router which implements the protocol specified in 264 this document. 266 OLSRv2 interface - A MANET interface running this protocol. 268 Routable address - An address which may be used as the destination 269 of a packet. A router MUST be able to distinguish a routable 270 address from a non-routable address by direct inpsection of the 271 address, based on global scope address allocations by IANA and/or 272 administrative configuration. Broadcast, multicast and anycast 273 addresses, and addresses which are limited in scope to less than 274 the entire MANET, MUST NOT be considered as routable addresses. 276 Originator address - An address which is unique (within the MANET) 277 to a router. A router MUST select an originator address; it MAY 278 choose one of its interface addresses as its originator address. 279 If it selects a routable address then this MUST be one which this 280 router will accept as destination. An originator address MUST NOT 281 have a prefix length. 283 Message originator address - The originator address of the router 284 which created a message, as deduced from that message by its 285 recipient. The message originator address will usually be 286 included in the message as its element as defined 287 in [RFC5444]. However an exceptional case in a HELLO message is 288 also allowed by this specification when a router only uses a 289 single address. All messages used in this specification, 290 including HELLO messages defined in [NHDP], MUST have a message 291 originator address. 293 Willingness - A numerical value between WILL_NEVER and WILL_ALWAYS 294 (both inclusive), which represents the router's willingness to be 295 selected as an MPR. 297 Willing symmetric 1-hop neighbor - A symmetric 1-hop neighbor of 298 this router which has willingness not equal to WILL_NEVER. 300 Symmetric 1-hop neighbor through OLSRv2 interface I - A symmetric 301 1-hop neighbor of the router via a symmetric link using OLSRv2 302 interface I of the router. 304 Symmetric strict 2-hop neighbor - A router, X, is a symmetric strict 305 2-hop neighbor of a router Y, if router X is a symmetric 2-hop 306 neighbor of router Y and if router X is not also a willing 307 symmetric 1-hop neighbor of router Y. 309 Symmetric strict 2-hop neighbor through OLSRv2 interface I - A 310 symmetric strict 2-hop neighbor of the router which is a symmetric 311 1-hop neighbor of a willing symmetric 1-hop neighbor through 312 OLSRv2 interface I. The router MAY elect to consider only 313 information received over OLSRv2 interface I in making this 314 determination. 316 Symmetric strict 2-hop neighborhood - The symmetric strict 2-hop 317 neighborhood of a router X is the set of symmetric strict 2-hop 318 neighbors of router X. 320 Multipoint relay (MPR) - A router, X, is an MPR for a router, Y, if 321 router Y has selected router X to "re-transmit" all the broadcast 322 messages that it receives from router X, provided that the message 323 is not a duplicate, and that the hop limit field of the message is 324 greater than one. 326 MPR selector - A router, Y, is an MPR selector of router X if router 327 Y has selected router X as MPR. 329 MPR flooding - The optimized MANET-wide information distribution 330 mechanism, employed by this protocol, in which a message is 331 relayed by only a reduced subset of the routers in the network. 332 MPR flooding is the mechanism by which flooding reduction is 333 achieved. 335 This document employs the same notational conventions as in [RFC5444] 336 and [NHDP]. 338 3. Applicability Statement 340 This protocol: 342 o Is a proactive routing protocol for mobile ad hoc networks 343 (MANETs) [RFC2501]. 345 o Is designed to work in networks with a dynamic topology, and in 346 which messages may be lost, such as due to collisions in wireless 347 networks. 349 o Supports routers that each have one or more participating OLSRv2 350 interfaces. The set of a router's interfaces may change over 351 time. Each OLSRv2 interface may have one or more addresses (which 352 may have prefix lengths), and these may also be dynamically 353 changing. 355 o Enables hop-by-hop routing, i.e., each router can use its local 356 information provided by this protocol to route packets. 358 o Continuously maintains routes to all destinations in the network, 359 i.e., routes are instantly available and data traffic is subject 360 to no delays due to route discovery. Consequently, no data 361 traffic buffering is required. 363 o Supports routers which have non-OLSRv2 interfaces which may be 364 local to a router or which can serve as gateways towards other 365 networks. 367 o Is optimized for large and dense networks: the larger and more 368 dense a network, the more optimization can be achieved by using 369 MPRs, compared to the classic link state algorithm. 371 o Uses the message format specified in [RFC5444]. This includes the 372 definition of a TC Message Type, used for MANET wide signaling of 373 network topology information. 375 o Allows "external" and "internal" extensibility as enabled by 376 [RFC5444]. 378 o Uses [NHDP] for discovering each router's 1-hop and symmetric 379 2-hop neighbors, and extends [NHDP] by addition of MPR and 380 willingness information. 382 o Is designed to work in a completely distributed manner, and does 383 not depend on any central entity. 385 4. Protocol Overview and Functioning 387 The objective of this protocol is for each router to, independently: 389 o Identify all destinations in the network. 391 o Identify a sufficient subset of links in the network, in order 392 that shortest paths can be calculated to all available 393 destinations. 395 o Provide a Routing Set, containing these shortest paths from this 396 router to all destinations (routable addresses and local links). 398 4.1. Overview 400 These objectives are achieved, for each router, by: 402 o Using [NHDP] to identify symmetric 1-hop neighbors and symmetric 403 2-hop neighbors. 405 o Independently selecting MPRs from among its symmetric 1-hop 406 neighbors such that all symmetric 2-hop neighbors are reachable 407 via at least one symmetric 1-hop neighbor. An analysis and 408 examples of MPR selection algorithms is given in [MPR], a 409 suggested algorithm is included in this specification. Note that 410 it is not necessary for routers to use the same algorithm in order 411 to interoperate in the same MANET. 413 o Signaling its MPR selection by extending [NHDP] to include this 414 information in outgoing HELLO messages, by the addition of MPR 415 Address Block TLV(s) associated with appropriate addresses. 417 o Extracting its MPR selectors from received HELLO messages, using 418 the included MPR Address Block TLV(s). 420 o Reporting its willingness to be an MPR in HELLO messages, by the 421 addition on an MPR_WILLING Message TLV. The router's willingness 422 to be an MPR indicates how willing it is to participate in MPR 423 flooding and to be an intermediate node for routing. A node can 424 absolutely decline to perform either role. 426 o Periodically signaling links between MPR selectors and itself 427 throughout the MANET, by using TC (Topology Control) messages, 428 defined in this specification. 430 o Diffusing TC messages by using flooding reduction mechanism, 431 denoted "MPR flooding": only the MPRs of a router will retransmit 432 messages received from (i.e., originated or last relayed by) that 433 router. 435 Note that the indicated extensions to [NHDP] are of forms permitted 436 by that specification. 438 This specification defines, in turn: 440 o Parameters and constants used by this protocol, in addition to 441 those specified in [NHDP]. Parameters used by this protocol may, 442 where appropriate, be specific to a given OLSRv2 interface, or to 443 a router. This protocol allows all parameters to be changed 444 dynamically, and to be set independently for each router or each 445 OLSRv2 interface, as appropriate. 447 o Extensions to the Information Bases specified in [NHDP]. 449 o Two new Information Bases: the Topology Information Base and the 450 Received Message Information Base. 452 o A requirement for each router to have an originator address to be 453 included in the HELLO messages of [NHDP]. 455 o A Message TLV, to be included in the HELLO messages of [NHDP], 456 allowing a router to indicate its willingness to be an MPR. 458 o An Address Block TLV, to be included in the HELLO messages of 459 [NHDP], allowing a router to signal its MPR selection. 461 o The MPR flooding mechanism, including the inclusion of message 462 originator address and sequence number to manage duplicate 463 messages. 465 o TC messages, which are used for MANET wide signaling (using MPR 466 flooding) of selected topology (link state) information. 468 o The specification of new Message TLVs and Address Block TLVs which 469 are used in TC messages. 471 o The generation of TC messages from the appropriate information in 472 the Information Bases. 474 o The updating of the Topology Information Base according to 475 received TC messages. 477 o The response to other events, such as the expiration of 478 information in the Information Bases. 480 This protocol inherits the stability of a link state algorithm and 481 has the advantage of having routes immediately available when needed, 482 due to its proactive nature. 484 This protocol only interacts with IP through routing table 485 management, and the use of the sending IP address for IP datagrams 486 containing OLSRv2 packets. 488 4.2. Routers and Interfaces 490 In order for a router to participate in a MANET, it MUST have at 491 least one, and possibly more, OLSRv2 interfaces. Each OLSRv2 492 interface: 494 o Is configured with one or more addresses, as specified in [NHDP]. 495 These addresses MUST each be unique within the MANET and MUST 496 include any address that will be used as the sending address of 497 any IP packet sent on this OLSRv2 interface. 499 o Has a number of interface parameters, adding to those specified in 500 [NHDP]. 502 o Has an Interface Information Base, extending that specified in 503 [NHDP]. 505 o Generates and processes HELLO messages according to [NHDP], 506 extended as specified in Section 9 and Section 10. 508 In addition to a set of OLSRv2 interfaces as described above, each 509 router: 511 o May have one or more non-OLSRv2 interfaces and/or local attached 512 networks which this router can accept packets destined for. All 513 routable addresses of the router for which it is to accept packets 514 as destination MUST be used as an (OLSRv2 or non-OLSRv2) interface 515 address or of a local attached network. 517 o Has a number of router parameters, adding to those specified in 518 [NHDP]. 520 o Has a Local Information Base, extending that specified in [NHDP], 521 including selection of an originator address and recording any 522 locally attached networks. 524 o Has a Neighbor Information Base, extending that specified in 525 [NHDP] to record MPR selection and advertisement information. 527 o Has a Topology Information Base, recording information received in 528 TC messages and derived therefrom. 530 o Has a Received Message Information Base, recording information 531 about received messages to ensure that each TC message is only 532 processed once, and forwarded at most once on each OLSRv2 533 interface, by a router. 535 o Generates and processes TC messages. 537 4.3. Information Base Overview 539 Each router maintains the Information Bases described in the 540 following sections. These are used for describing the protocol in 541 this document. An implementation of this protocol MAY maintain this 542 information in the indicated form, or in any other organization which 543 offers access to this information. In particular, note that it is 544 not necessary to remove Tuples from Sets at the exact time indicated, 545 only to behave as if the Tuples were removed at that time. 547 4.3.1. Local Information Base 549 The Local Information Base is specified in [NHDP] and contains a 550 router's local configuration. It is extended in this specification 551 to also record an originator address and to include a router's: 553 o Originator Set, containing addresses that were recently used as 554 this router's originator address, and is used to enable a router 555 to recognize and discard control traffic which was originated by 556 the router itself. 558 o Local Attached Network Set, containing addresses of networks to 559 which this router can act as a gateway, and advertises in its TC 560 messages. 562 4.3.2. Interface Information Bases 564 The Interface Information Bases, one for each OLSRv2 interface, are 565 specified in [NHDP]. In addition to the uses in [NHDP], information 566 recorded in the Interface Information Bases is used for completing 567 the Routing Set. 569 4.3.3. Neighbor Information Base 571 The Neighbor Information Base is specified in [NHDP], and is extended 572 to also record each neighbor's originator address, the willingness of 573 each neighbor to be an MPR, as well as this router's MPR 574 relationships with each neighbor (whether an MPR and/or an MPR 575 selector of that neighbor) and whether that neighbor is to be 576 advertised in TC messages. 578 A router selects some of its symmetric 1-hop neighbors as MPRs (see 579 Section 14). That selection is recorded in the Neighbor Set. This 580 selection is then reported in the router's HELLO messages, extending 581 the specification in [NHDP], by using an MPR Address Block TLV. In 582 making that selection a router MUST consider its 1-hop neighbors' 583 willingness to be an MPR, which (unless having default value) is 584 reported using an Address Block TLV in HELLO messages and recorded in 585 the receiving router's Neighbor Set. 587 A router also records in the Neighbor Set which symmetric 1-hop 588 neighbors have selected it as an MPR (i.e. its MPR selectors). This 589 is determined from the MPR TLVs in received HELLO messages. It also 590 records which symmetric 1-hop neighbors that it is to advertise 591 connectivity to in its TC messages; this MUST include all of its MPR 592 selectors. 594 The Neighbor Set finally records each 1-hop neighbor's originator 595 address, as included in its HELLO messages in an extension to [NHDP]. 596 This, and other information in the Neighbor Set, including each 1-hop 597 neighbor's routable addresses, is used in advertising the selected 598 symmetric 1-hop neighbors in TC messages. 600 4.3.4. Topology Information Base 602 The purpose of the Topology Information Base is to record information 603 used, in addition to that in the Local Information Base, the 604 Interface Information Bases and the Neighbor Information Base, to 605 construct the Routing Set (which is also included in the Topology 606 Information Base). 608 This specification describes the calculation of the Routing Set based 609 on a Topology Graph constructed in two phases. First, a "backbone" 610 graph representing the routers in the MANET, and the connectivity 611 between them, is constructed from the Local Information Base, the 612 Neighbor Information Base and the Router Topology Set in the Topology 613 Information Base. Second, this graph is "decorated" with additional 614 destination addresses using the Local Information Base, and the 615 Routable Address Topology Set and the Attached Network Set in the 616 Topology Information Base. 618 The Topology Graph does not need to be recorded in the Topology 619 Information Base, it can either be constructed as required when the 620 Routing Set is to be changed, or need not be explicitly constructed 621 (as illustrated in Appendix B. An implementation MAY construct and 622 retain the Topology Graph if preferred. 624 The Topology Information Base in each router contains: 626 o An Advertising Remote Router Set, recording each other router from 627 which TC messages have been received. This is used in order to 628 determine if a received TC messages contains fresh or outdated 629 information; the TC message is ignored in the latter case. 631 o A Router Topology Set, recording links between routers in the 632 MANET, as described by received TC messages. 634 o A Routable Address Topology Set, recording routable addresses in 635 the MANET (available as packet destinations) and from which other 636 router these addresses can be directly reached (i.e. in a single 637 IP hop) as reported by received TC messages. 639 o An Attached Network Set, recording networks to which a remote 640 router has advertised that it may act as a gateway. These 641 networks may be reached in one or more IP hops. 643 o A Routing Set, recording routes from this router to all available 644 destinations. The IP routing table is to be updated using this 645 Routing Set. (A router MAY choose to use any or all destination 646 addresses in the Routing Set to update the IP routing table, this 647 selection is outside the scope of this protocol.) 649 4.3.5. Received Message Information Base 651 The Received Message Information Base in each router contains: 653 o A Received Set for each OLSRv2 interface, describing TC messages 654 received by this router on that OLSRv2 interface. 656 o A Processed Set, describing TC messages processed by this router. 658 o A Forwarded Set, describing TC messages forwarded by this router. 660 The Received Message Information Base serves the MPR flooding 661 mechanism by ensuring that received messages are forwarded at most 662 once by a router, and also ensures that received messages are 663 processed exactly once by a router. 665 4.4. Signaling Overview 667 This protocol generates and processes HELLO messages according to 668 [NHDP], extended according to Section 9 and Section 10 of this 669 specification to include an originator address and MPR selection 670 information. 672 This protocol specifies a single message type, the TC message. 674 This protocol is tolerant of unreliable transmissions of TC messages; 675 each router sends TC messages periodically, and can therefore sustain 676 a reasonable loss of some such messages. Such losses may occur more 677 frequently in wireless networks due to collisions or other 678 transmission problems. This protocol MAY use "jitter", randomized 679 adjustments to message transmission times, to reduce the incidence of 680 collisions as specified in [RFC5148]. 682 This protocol is tolerant of out of sequence delivery of TC messages 683 due to in transit message reordering (possibly due to message 684 alternative routing by flooding and message loss). Each router 685 maintains an Advertised Neighbor Sequence Number (ANSN) which is 686 incremented when its recorded neighbor information that is to be 687 included in its TC messages changes. This ANSN is included in the 688 router's TC messages. The recipient of a TC message can used this 689 included ANSN to identify which of the information it has received is 690 most recent, even if messages have been re-ordered while in transit. 691 Only the most recent information received is used, older information 692 received later is discarded. 694 TC messages may be "complete" or "incomplete". A complete TC message 695 advertises all of the originating router's MPR selectors, it may also 696 advertise other symmetric 1-hop neighbors. Complete TC messages are 697 generated periodically (and also, optionally, in response to 698 neighborhood changes). Incomplete TC messages may be used to report 699 additions to advertised information without repeating unchanged 700 information. 702 TC messages, and HELLO messages as extended by this specification, 703 include an originator address for the router that created the 704 message. A TC message reports both the originator addresses and 705 routable addresses of its advertised neighbors, distinguishing the 706 two using a TLV for this purpose (an address may be both). 708 TC messages also report the originator's locally attached networks. 710 TC messages are MPR flooded throughout the MANET. A router 711 retransmits a TC message only if it is received from (i.e., 712 originated from or was last relayed by) one of that router's MPR 713 selectors. 715 Some TC messages may be MPR flooded over only part of the network, 716 e.g., allowing a router to ensure that nearer routers are kept more 717 up to date than distant routers, such as is used in Fisheye State 718 Routing [FSR] and Fuzzy Sighted Link State routing [FSLS]. This is 719 enabled using [RFC5497]. 721 4.5. Routing Set 723 The purpose of the Routing Set is to determine and record routes 724 (local interface address and next hop interface address) to all 725 possible routable addresses and of all destinations that are local, 726 i.e. within one hop, to the router (whether using routable addresses 727 or not). Only symmetric links are used in such routes. 729 It is intended that the Routing Set can be used for packet routing, 730 by using its contents to update IP's routing tables. That update, 731 and whether any Routing Tuples are not used in IP's routing table, is 732 outside the scope of this specification. 734 The signaling in this specification has been designed so that a 735 "backbone" Topology Graph of routers, each identified by its 736 originator address, with at most one direct connection between any 737 pair of routers, can be constructed (from the Neighbor Set and the 738 Router Topology Set) using a suitable minimum path length algorithm, 739 and then this Topology Graph can have other addresses (routable, or 740 of symmetric 1-hop neighbors) added to it (using the Interface 741 Information Base, the Routable Address Topology Set and the Attached 742 Network Set). 744 5. Protocol Parameters and Constants 746 The parameters and constants used in this specification are those 747 defined in [NHDP] plus those defined in this section. The separation 748 in [NHDP] into interface parameters, router parameters and constants 749 is also used in this specification, however all but one 750 (RX_HOLD_TIME) of the parameters added by this protocol are router 751 parameters. Parameters may be categorized as follows: 753 o Local history times 755 o Message intervals 757 o Advertised information validity times 759 o Received message validity times 760 o Jitter times 762 o Hop limits 764 o Willingness 766 In addition, constants for particular cases of a router's willingness 767 to be an MPR are defined. These parameters and constants are 768 detailed in the following sections. As for the parameters in [NHDP], 769 parameters defined in this document may be changed dynamically by a 770 router, and need not be the same on different routers, even in the 771 same MANET, or, for interface parameters, on different interfaces of 772 the same router. 774 5.1. Protocol and Port Numbers 776 This protocol specifies TC messages, which are included in packets as 777 defined by [RFC5444]. These packets may be sent either using the 778 "manet" protocol number or the "manet" well-known UDP port number, as 779 specified in [RFC5498]. 781 TC messages and HELLO messages [NHDP] SHOULD, in a given deployment 782 of this protocol, both be using the same of either of IP or UDP, in 783 order that it is possible to combine messages of both protocols into 784 the same [RFC5444] packet for transmission. 786 5.2. Multicast Address 788 This protocol specifies TC messages, which are included in packets as 789 defined by [RFC5444]. These packets may be locally transmitted using 790 the link local multicast address "LL-MANET-Routers", as specified in 791 [RFC5498]. 793 5.3. Local History Times 795 The following router parameter manages the time for which local 796 information is retained: 798 O_HOLD_TIME - is used to define the time for which a recently used 799 and replaced originator address is used to recognize the router's 800 own messages. 802 The following constraint applies to this parameter: 804 o O_HOLD_TIME >= 0 806 5.4. Message Intervals 808 The following router parameters regulate TC message transmissions by 809 a router. TC messages are usually sent periodically, but MAY also be 810 sent in response to changes in the router's Neighbor Set and/or Local 811 Attached Network Set. With a larger value of the parameter 812 TC_INTERVAL, and a smaller value of the parameter TC_MIN_INTERVAL, TC 813 messages may more often be transmitted in response to changes in a 814 highly dynamic network. However because a router has no knowledge 815 of, for example, routers remote to it (i.e. beyond 2 hops away) 816 joining the network, TC messages MUST NOT be sent purely 817 responsively. 819 TC_INTERVAL - is the maximum time between the transmission of two 820 successive TC messages by this router. When no TC messages are 821 sent in response to local network changes (by design, or because 822 the local network is not changing) then TC messages SHOULD be sent 823 at a regular interval TC_INTERVAL, possibly modified by jitter as 824 specified in [RFC5148]. 826 TC_MIN_INTERVAL - is the minimum interval between transmission of 827 two successive TC messages by this router. (This minimum interval 828 MAY be modified by jitter, as specified in [RFC5148].) 830 The following constraints apply to these parameters: 832 o TC_INTERVAL > 0 834 o TC_MIN_INTERVAL >= 0 836 o TC_INTERVAL >= TC_MIN_INTERVAL 838 o If INTERVAL_TIME TLVs as defined in [RFC5497] are included in TC 839 messages, then TC_INTERVAL MUST be representable as described in 840 [RFC5497]. 842 5.5. Advertised Information Validity Times 844 The following router parameters manage the validity time of 845 information advertised in TC messages: 847 T_HOLD_TIME - is used to define the minimum Value in the 848 VALIDITY_TIME TLV included in all TC messages sent by this router. 849 If a single value of parameter TC_HOP_LIMIT (see Section 5.8) is 850 used then this will be the only Value in that TLV. 852 A_HOLD_TIME - is the period during which TC messages are sent after 853 they no longer have any advertised information to report, but are 854 sent in order to accelerate outdated information removal by other 855 routers. 857 The following constraints apply to these parameters: 859 o T_HOLD_TIME > 0 861 o A_HOLD_TIME >= 0 863 o T_HOLD_TIME >= TC_INTERVAL 865 o If TC messages can be lost, then both T_HOLD_TIME and A_HOLD_TIME 866 SHOULD be significantly greater than TC_INTERVAL; a value >= 3 x 867 TC_INTERVAL is RECOMMENDED. 869 o T_HOLD_TIME MUST be representable as described in [RFC5497]. 871 5.6. Received Message Validity Times 873 The following parameters manage the validity time of recorded 874 received message information: 876 RX_HOLD_TIME - is an interface parameter, and is the period after 877 receipt of a message by the appropriate OLSRv2 interface of this 878 router for which that information is recorded, in order that the 879 message is recognized as having been previously received on this 880 OLSRv2 interface. 882 P_HOLD_TIME - is a router parameter, and is the period after receipt 883 of a message which is processed by this router for which that 884 information is recorded, in order that the message is not 885 processed again if received again. 887 F_HOLD_TIME - is a router parameter, and is the period after receipt 888 of a message which is forwarded by this router for which that 889 information is recorded, in order that the message is not 890 forwarded again if received again. 892 The following constraints apply to these parameters: 894 o RX_HOLD_TIME > 0 896 o P_HOLD_TIME > 0 898 o F_HOLD_TIME > 0 899 o All of these parameters SHOULD be greater than the maximum 900 difference in time that a message may take to traverse the MANET, 901 taking into account any message forwarding jitter as well as 902 propagation, queuing, and processing delays. 904 5.7. Jitter 906 If jitter, as defined in [RFC5148], is used then the governing jitter 907 parameters are as follows: 909 TP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 910 for periodically generated TC messages sent by this router. 912 TT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 913 for externally triggered TC messages sent by this router. 915 F_MAXJITTER - represents the default value of MAXJITTER used in 916 [RFC5148] for messages forwarded by this router. However before 917 using F_MAXJITTER a router MAY attempt to deduce a more 918 appropriate value of MAXJITTER, for example based on any 919 INTERVAL_TIME or VALIDITY_TIME TLVs contained in the message to be 920 forwarded. 922 For constraints on these parameters see [RFC5148]. 924 5.8. Hop Limit Parameter 926 The parameter TC_HOP_LIMIT is the hop limit set in each TC message. 927 TC_HOP_LIMIT MAY be a single fixed value, or MAY be different in TC 928 messages sent by the same router. However each other router, at any 929 hop count distance, SHOULD see a regular pattern of TC messages, in 930 order that meaningful Values of INTERVAL_TIME and VALIDITY_TIME TLVs 931 at each hop count distance can be included as defined in [RFC5497]. 932 Thus the pattern of TC_HOP_LIMIT SHOULD be defined to have this 933 property. For example the repeating pattern (255 4 4) satisfies this 934 property (having period TC_INTERVAL at hop counts up to 4, inclusive, 935 and 3 x TC_INTERVAL at hop counts greater than 4), but the repeating 936 pattern (255 255 4 4) does not satisfy this property because at hop 937 counts greater than 4, message intervals are alternately TC_INTERVAL 938 and 3 x TC_INTERVAL. 940 The following constraints apply to this parameter: 942 o The maximum value of TC_HOP_LIMIT >= the network diameter in hops, 943 a value of 255 is RECOMMENDED. Note that if using a pattern of 944 different values of TC_HOP_LIMIT as described above, then only the 945 maximum value in the patttern is so constrained. 947 o All values of TC_HOP_LIMIT >= 2. 949 5.9. Willingness 951 Each router has a WILLINGNESS parameter, which MUST be in the range 952 WILL_NEVER to WILL_ALWAYS, inclusive, and represents the router's 953 willingness to be an MPR, and hence its willingness to forward 954 messages and be an intermediate router on routes. If a router has 955 WILLINGNESS = WILL_NEVER it does not perform these tasks. A MANET 956 using this protocol with too many routers having WILLINGNESS = 957 WILL_NEVER will not function; it MUST be ensured, by administrative 958 or other means, that this does not happen. 960 Routers MAY have different WILLINGNESS values; however the three 961 constants WILL_NEVER, WILL_DEFAULT and WILL_ALWAYS MUST have the 962 values defined in Section 16. (Use of WILLINGNESS = WILL_DEFAULT 963 allows a router to avoid including an MPR_WILLING TLV in its TC 964 messages, use of WILLINGNESS = WILL_ALWAYS means that a router will 965 always be selected as an MPR by all symmetric 1-hop neighbors.) 967 The following constraints apply to this parameter: 969 o WILLINGNESS >= WILL_NEVER 971 o WILLINGNESS <= WILL_ALWAYS 973 5.10. Parameter Change Constraints 975 This section presents guidelines, applicable if protocol parameters 976 are changed dynamically. 978 O_HOLD_TIME 980 * If O_HOLD_TIME for a router changes, then O_time for all 981 Originator Tuples MAY be changed. 983 TC_INTERVAL 985 * If the TC_INTERVAL for a router increases, then the next TC 986 message generated by this router MUST be generated according to 987 the previous, shorter, TC_INTERVAL. Additional subsequent TC 988 messages MAY be generated according to the previous, shorter, 989 TC_INTERVAL. 991 * If the TC_INTERVAL for a router decreases, then the following 992 TC messages from this router MUST be generated according to the 993 current, shorter, TC_INTERVAL. 995 RX_HOLD_TIME 997 * If RX_HOLD_TIME for an OLSRv2 interface changes, then RX_time 998 for all Received Tuples for that OLSRv2 interface MAY be 999 changed. 1001 P_HOLD_TIME 1003 * If P_HOLD_TIME changes, then P_time for all Processed Tuples 1004 MAY be changed. 1006 F_HOLD_TIME 1008 * If F_HOLD_TIME changes, then F_time for all Forwarded Tuples 1009 MAY be changed. 1011 TP_MAXJITTER 1013 * If TP_MAXJITTER changes, then the periodic TC message schedule 1014 on this router MAY be changed immediately. 1016 TT_MAXJITTER 1018 * If TT_MAXJITTER changes, then externally triggered TC messages 1019 on this router MAY be rescheduled. 1021 F_MAXJITTER 1023 * If F_MAXJITTER changes, then TC messages waiting to be 1024 forwarded with a delay based on this parameter MAY be 1025 rescheduled. 1027 TC_HOP_LIMIT 1029 * If TC_HOP_LIMIT changes, and the router uses multiple values 1030 after the change, then message intervals and validity times 1031 included in TC messages MUST be respected. The simplest way to 1032 do this is to start any new repeating pattern of TC_HOP_LIMIT 1033 values with its largest value. 1035 6. Information Bases 1037 The purpose of this protocol is to determine the Routing Set, which 1038 may be used to update IP's Routing Table, providing "next hop" 1039 routing information for IP packets. This specification includes the 1040 following Information Bases: 1042 Local Information Base - as defined in [NHDP], extended by the 1043 inclusion of the router's originator address and the addition of 1044 an Originator Set, defined in Section 6.1.1, and a Local Attached 1045 Network Set, defined in Section 6.1.2. 1047 Interface Information Bases - as defined in [NHDP], an Interface 1048 Information Base for each OLSRv2 interface. 1050 Neighbor Information Base - as defined in [NHDP], extended by the 1051 addition of five elements to each Neighbor Tuple, and the 1052 inclusion of an Advertised Neighbor Sequence Number (ANSN), both 1053 as defined in Section 6.2. 1055 Topology Information Base - this Information Base is specific to 1056 this protocol, and is defined in Section 6.3. 1058 Received Message Information Base - this Information Base is 1059 specific to this protocol, and is defined in Section 6.4. 1061 The ordering of sequence numbers, when considering which is the 1062 greater, is as defined in Section 17. 1064 6.1. Local Information Base 1066 The Local Information Base as defined in [NHDP] is extended by: 1068 o Recording the router's originator address. Note that this MAY be 1069 equal to any address in any I_local_iface_addr_list in a Local 1070 Interface Tuple, but MUST NOT be equal to the AL_net_addr in a 1071 Local Attached Network Tuple. 1073 o The addition of an Originator Set, defined in Section 6.1.1, and a 1074 Local Attached Network Set, defined in Section 6.1.2. 1076 All routable addresses of the router for which it is to accept 1077 packets as destination MUST be included in the Local Interface Set or 1078 the Local Attached Network Set. 1080 6.1.1. Originator Set 1082 A router's Originator Set records addresses that were recently used 1083 as originator addresses by this router. If a router's originator 1084 address is immutable then this set is always empty and MAY be 1085 omitted. It consists of Originator Tuples: 1087 (O_orig_addr, O_time) 1089 where: 1091 O_orig_addr is a recently used originator address, note that this 1092 does not include a prefix length; 1094 O_time specifies the time at which this Tuple expires and MUST be 1095 removed. 1097 6.1.2. Local Attached Network Set 1099 A router's Local Attached Network Set records its local non-OLSRv2 1100 interfaces via which it can act as gateways to other networks. The 1101 Local Attached Network Set is not modified by this protocol. This 1102 protocol MAY respond to changes to the Local Attached Network Set, 1103 which MUST reflect corresponding changes in the router's status. It 1104 consists of Local Attached Network Tuples: 1106 (AL_net_addr, AL_dist) 1108 where: 1110 AL_net_addr is the network address of an attached network which can 1111 be reached via this router. This SHOULD be a routable address, 1112 and MUST NOT be an interface address, or the originator address, 1113 of this router. 1115 AL_dist is the number of hops to the network with address 1116 AL_net_addr from this router. 1118 Attached networks local to this router only (i.e. not reachable 1119 except via this router) SHOULD be treated as local non-MANET 1120 interfaces, and added to the Local Interface Set, as specified in 1121 [NHDP], rather than be added to the Local Attached Network Set. 1123 Because an attached network is not specific to the router, and may be 1124 outside the MANET, an attached network MAY also be attached to other 1125 routers. 1127 It is not the responsibility of this protocol to maintain routes from 1128 this router to networks recorded in the Local Attached Network Set. 1130 Local Attached Neighbor Tuples are removed from the Local Attached 1131 Network Set only when the routers' local attached network 1132 configuration changes, i.e., they are not subject to timer-based 1133 expiration or changes due to received messages. 1135 6.2. Neighbor Information Base 1137 Each Neighbor Tuple in the Neighbor Set, defined in [NHDP], has these 1138 additional elements: 1140 N_orig_addr is the neighbor's originator address, which may be 1141 unknown. Note that this originator address does not include a 1142 prefix length; 1144 N_willingness is the neighbor's willingness to be selected as an 1145 MPR, in the range from WILL_NEVER to WILL_ALWAYS, both inclusive; 1147 N_mpr is a boolean flag, describing if this neighbor is selected as 1148 an MPR by this router; 1150 N_mpr_selector is a boolean flag, describing if this neighbor has 1151 selected this router as an MPR, i.e., is an MPR selector of this 1152 router. 1154 N_advertised is a boolean flag, describing if this router has 1155 elected to advertise a link to this neighbor in its TC messages. 1157 A Neighbor Tuple created (but not updated) by [NHDP] MUST set: 1159 N_orig_addr := unknown; 1161 N_willingness := WILL_NEVER; 1163 N_mpr := false; 1165 N_mpr_selector := false; 1167 N_advertised := false. 1169 The Neighbor Information Base also includes a variable, the 1170 Advertised Neighbor Sequence Number (ANSN), whose value is included 1171 in TC messages to indicate the freshness of the information 1172 transmitted. The ANSN is incremented whenever advertised information 1173 (the originator and routable addresses included in Neighbor Tuples 1174 with N_advertised = true, and local attached networks recorded in the 1175 Local Attached Network Set in the Local Information Base) changes. 1177 6.3. Topology Information Base 1179 The Topology Information Base stores information received in TC 1180 messages, in the Advertising Remote Router Set, the Router Topology 1181 Set, the Routable Address Topology Set and the Attached Network Set. 1183 Additionally, a Routing Set is maintained, derived from the 1184 information recorded in the Local Information Base, the Interface 1185 Information Bases, the Neighbor Information Base and the rest of the 1186 Topology Information Base. 1188 6.3.1. Advertising Remote Router Set 1190 A router's Advertising Remote Router Set records information 1191 describing each remote router in the network that transmits TC 1192 messages, allowing outdated TC messages to be recognized and 1193 discarded. It consists of Advertising Remote Router Tuples: 1195 (AR_orig_addr, AR_seq_number, AR_time) 1197 where: 1199 AR_orig_addr is the originator address of a received TC message, 1200 note that this does not include a prefix length; 1202 AR_seq_number is the greatest ANSN in any TC message received which 1203 originated from the router with originator address AR_orig_addr 1204 (i.e., which contributed to the information contained in this 1205 Tuple); 1207 AR_time is the time at which this Tuple expires and MUST be removed. 1209 6.3.2. Router Topology Set 1211 A router's Topology Set records topology information about the links 1212 between routers in the MANET, allowing a "backbone" graph of all 1213 routers to be constructed using a minimum distance algorithm. It 1214 consists of Router Topology Tuples: 1216 (TR_from_orig_addr, TR_to_orig_addr, TR_seq_number, TR_time) 1218 where: 1220 TR_from_orig_addr is the originator address of a router which can 1221 reach the router with originator address TR_to_orig_addr in one 1222 hop, note that this does not include a prefix length; 1224 TR_to_orig_addr is the originator address of a router which can be 1225 reached by the router with originator address TR_to_orig_addr in 1226 one hop, note that this does not include a prefix length; 1228 TR_seq_number is the greatest ANSN in any TC message received which 1229 originated from the router with originator address 1230 TR_from_orig_addr (i.e., which contributed to the information 1231 contained in this Tuple); 1233 TR_time specifies the time at which this Tuple expires and MUST be 1234 removed. 1236 6.3.3. Routable Address Topology Set 1238 A router's Routable Address Topology Set records topology information 1239 about the routable addresses within the MANET, and via which routers 1240 they may be reached. It consists of Routable Address Topology 1241 Tuples: 1243 (TA_from_orig_addr, TA_dest_addr, TA_seq_number, TA_time) 1245 where: 1247 TA_from_orig_addr is the originator address of a router which can 1248 reach the router with routable address TA_dest_addr in one hop, 1249 note that this does not include a prefix length; 1251 TA_dest_addr is a routable address of a router which can be reached 1252 by the router with originator address TA_from_orig_addr in one 1253 hop; 1255 TA_seq_number is the greatest ANSN in any TC message received which 1256 originated from the router with originator address 1257 TA_from_orig_addr (i.e., which contributed to the information 1258 contained in this Tuple); 1260 TA_time specifies the time at which this Tuple expires and MUST be 1261 removed. 1263 6.3.4. Attached Network Set 1265 A router's Attached Network Set records information about networks 1266 (which may be outside the MANET) attached to other routers and their 1267 routable addresses. It consists of Attached Network Tuples: 1269 (AN_orig_addr, AN_net_addr, AN_dist, AN_seq_number, AN_time) 1271 where: 1273 AN_orig_addr is the originator address of a router which can act as 1274 gateway to the network with address AN_net_addr, note that this 1275 does not include a prefix length; 1277 AN_net_addr is the network address of an attached network, which may 1278 be reached via the router with originator address AN_orig_addr; 1280 AN_dist is the number of hops to the network with address 1281 AN_net_addr from the router with originator address AN_orig_addr; 1283 AN_seq_number is the greatest ANSN in any TC message received which 1284 originated from the router with originator address AN_orig_addr 1285 (i.e., which contributed to the information contained in this 1286 Tuple); 1288 AN_time specifies the time at which this Tuple expires and MUST be 1289 removed. 1291 6.3.5. Routing Set 1293 A router's Routing Set records the first hop along a selected path to 1294 each destination for which any such path is known. It consists of 1295 Routing Tuples: 1297 (R_dest_addr, R_next_iface_addr, R_local_iface_addr, R_dist) 1299 where: 1301 R_dest_addr is the address of the destination, either the address of 1302 an interface of a destination router, or the network address of an 1303 attached network; 1305 R_next_iface_addr is the address of the "next hop" on the selected 1306 path to the destination; 1308 R_local_iface_addr is the address of the local OLSRv2 interface over 1309 which a packet MUST be sent to reach the destination by the 1310 selected path. 1312 R_dist is the number of hops on the selected path to the 1313 destination; 1315 The Routing Set for a router is derived from the contents of other 1316 protocol Sets of the router (the Link Sets, the Neighbor Set, the 1317 Router Topology Set, the Routable Address Topology Set, the Attached 1318 Network Set, and OPTIONALLY the Two Hop Sets). The Routing Set is 1319 updated (Routing Tuples added or removed, or the complete Routing Set 1320 recalculated) when routing paths are calculated, based on changes to 1321 these other protocol Sets. Routing Tuples are not subject to timer- 1322 based expiration. 1324 6.4. Received Message Information Base 1326 The Received Message Information Base records information required to 1327 ensure that a message is processed at most once and is forwarded at 1328 most once per OLSRv2 interface of a router, using MPR flooding. 1330 6.4.1. Received Set 1332 A router has a Received Set per OLSRv2 interface. Each Received Set 1333 records the signatures of messages which have been received over that 1334 OLSRv2 interface. Each consists of Received Tuples: 1336 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 1338 where: 1340 RX_type is the received Message Type; 1342 RX_orig_addr is the originator address of the received message, note 1343 that this does not include a prefix length; 1345 RX_seq_number is the message sequence number of the received 1346 message; 1348 RX_time specifies the time at which this Tuple expires and MUST be 1349 removed. 1351 6.4.2. Processed Set 1353 A router has a single Processed Set which records signatures of 1354 messages which have been processed by the router. It consists of 1355 Processed Tuples: 1357 (P_type, P_orig_addr, P_seq_number, P_time) 1359 where: 1361 P_type is the processed Message Type; 1363 P_orig_addr is the originator address of the processed message, note 1364 that this does not include a prefix length; 1366 P_seq_number is the message sequence number of the processed 1367 message; 1369 P_time specifies the time at which this Tuple expires and MUST be 1370 removed. 1372 6.4.3. Forwarded Set 1374 A router has a single Forwarded Set which records signatures of 1375 messages which have been forwarded by the router. It consists of 1376 Forwarded Tuples: 1378 (F_type, F_orig_addr, F_seq_number, F_time) 1380 where: 1382 F_type is the forwarded Message Type; 1384 F_orig_addr is the originator address of the forwarded message, note 1385 that this does not include a prefix length; 1387 F_seq_number is the message sequence number of the forwarded 1388 message; 1390 F_time specifies the time at which this Tuple expires and MUST be 1391 removed. 1393 6.5. Corresponding Protocol Tuples 1395 In a number of cases there is a natural correspondence from a 1396 Protocol Tuple in a Protocol Set to a single Protocol Tuple in 1397 another Protocol Set. The latter Protocol Tuple is referred to as 1398 "corresponding" to the former. 1400 Specific examples include: 1402 o There is a Local Interface Tuple corresponding to each Link Tuple, 1403 where the Link Tuple is in the Link Set for an OLSRv2 interface, 1404 and the Local Interface Tuple represents that OLSRv2 interface. 1406 o There is a Neighbor Tuple corresponding to each Link Tuple which 1407 has L_HEARD_time not expired, such that N_neighbor_addr_list 1408 contains L_neighbor_iface_addr_list. 1410 o There is a Link Tuple (in the Link Set in the same Interface 1411 Information Base) corresponding to each 2-Hop Tuple such that 1412 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 1414 o There is a Neighbor Tuple corresponding to each 2-Hop Tuple, such 1415 that N_neighbor_addr_list contains N2_neighbor_iface_addr_list. 1417 o There is an Advertising Remote Router Tuple corresponding to each 1418 Router Topology Tuple such that AR_orig_addr = TR_from_orig_addr. 1420 o There is an Advertising Remote Router Tuple corresponding to each 1421 Routable Address Topology Tuple such that AR_orig_addr = 1422 TA_from_orig_addr. 1424 o There is an Advertising Remote Router Tuple corresponding to each 1425 Attached Network Tuple such that AR_orig_addr = AN_orig_addr. 1427 o There is an Neighbor Tuple corresponding to each Routing Tuple 1428 such that N_neighbor_addr_list contains R_next_iface_addr. 1430 7. Message Processing and Forwarding 1432 This protocol defines, and hence owns, the TC message type (see 1433 Section 20). Thus, as specified in [RFC5444], this protocol receives 1434 all TC messages and is responsible for determining whether and how 1435 each TC message is to be processed (updating Information Bases) 1436 and/or forwarded, according to this specification. OLSRv2 does not 1437 require any part of the Packet Header. 1439 This protocol also receives HELLO messages, which are defined, and 1440 hence owned, by [NHDP]. Such messages, when received on an OLSRv2 1441 interface, are made available to this protocol in two ways, both as 1442 permitted by [NHDP]. First, such received HELLO messages MUST be 1443 made available to this protocol on reception, which allows them to be 1444 discarded before being processed by [NHDP], for example if the 1445 information added to the HELLO message by this protocol is 1446 inconsistent. Second, such received HELLO messages MUST be made 1447 available to OLSRv2 after [NHDP] has completed its processing 1448 thereof, unless discarded as malformed by [NHDP], for processing by 1449 this protocol. HELLO messages are not forwarded by this protocol. 1451 Extensions to this protocol which define, and hence own, other 1452 Messages Types, MAY manage the processing and/or forwarding of these 1453 messages using the same mechanism as for TC messages. These 1454 mechanisms contain elements (P_type, RX_type, F_type) required only 1455 for such usage. 1457 The processing selection and forwarding mechanisms are designed to 1458 only need to parse the Message Header in order to determine whether a 1459 message is to be processed and/or forwarded, and not to have to parse 1460 the Message Body even if the message is forwarded (but not 1461 processed). An implementation MAY either only parse the Message Body 1462 if necessary, or MAY always parse the Message Body. 1464 An implementation MUST discard the message silently if it is unable 1465 to parse the Message Header or (if attempted) the Message Body. 1467 7.1. Actions when Receiving a Message 1469 If the router receives a HELLO message from [NHDP], then the message 1470 may be rejected before processing by [NHDP] or processed after 1471 processing by [NHDP], both according to Section 10. 1473 A router MUST perform the following tasks for each received TC 1474 message (or other Message Type defined by an extension to this 1475 protocol and specified to use this process): 1477 1. If the router recognizes from the originator address of the 1478 message that the message is one which the receiving router itself 1479 originated (i.e. is the originator address of this router, or is 1480 an O_orig_addr in an Originator Tuple) then the message MUST be 1481 silently discarded. 1483 2. Otherwise: 1485 1. If the message is of a type which may be processed, including 1486 being a TC message, then the message is considered for 1487 processing according to Section 7.2, AND; 1489 2. If the message is of a type which may be forwarded, including 1490 being a TC message, AND: 1492 + is present and > 1, AND; 1494 + is not present or < 255 1496 then the message is considered for forwarding according to 1497 Section 7.3. 1499 7.2. Message Considered for Processing 1501 If a message (the "current message") is considered for processing, 1502 then the following tasks MUST be performed: 1504 1. If a Processed Tuple exists with: 1506 * P_type = the Message Type of the current message, AND; 1508 * P_orig_addr = the originator address of the current message, 1509 AND; 1511 * P_seq_number = the message sequence number of the current 1512 message; 1514 then the current message MUST NOT be processed. 1516 2. Otherwise: 1518 1. Create a Processed Tuple with: 1520 + P_type := the Message Type of the current message; 1522 + P_orig_addr := the originator address of the current 1523 message; 1525 + P_seq_number := the sequence number of the current 1526 message; 1528 + P_time := current time + P_HOLD_TIME. 1530 2. Process the current message according to its type. For a TC 1531 message this is as defined in Section 12. 1533 7.3. Message Considered for Forwarding 1535 If a message (the "current message") is considered for forwarding, 1536 then the following tasks MUST be performed: 1538 1. If the sending address (i.e., the source address of the IP 1539 datagram containing the current message) does not match (taking 1540 into account any address prefix) an address in an 1541 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 1542 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 1543 current message was received (the "receiving interface") then the 1544 current message MUST be silently discarded. 1546 2. Otherwise: 1548 1. If a Received Tuple exists in the Received Set for the 1549 receiving interface, with: 1551 + RX_type = the Message Type of the current message, AND; 1553 + RX_orig_addr = the originator address of the current 1554 message, AND; 1556 + RX_seq_number = the sequence number of the current 1557 message; 1559 then the current message MUST be silently discarded. 1561 2. Otherwise: 1563 1. Create a Received Tuple in the Received Set for the 1564 receiving interface with: 1566 - RX_type := the Message Type of the current message; 1568 - RX_orig_addr := originator address of the current 1569 message; 1571 - RX_seq_number := sequence number of the current 1572 message; 1574 - RX_time := current time + RX_HOLD_TIME. 1576 2. If a Forwarded Tuple exists with: 1578 - F_type = the Message Type of the current message, AND; 1580 - F_orig_addr = the originator address of the current 1581 message, AND; 1583 - F_seq_number = the sequence number of the current 1584 message. 1586 then the current message MUST be silently discarded. 1588 3. Otherwise if the sending address matches (taking account 1589 of any address prefix) any address in an 1590 L_neighbor_iface_addr_list of a Link Tuple in the Link 1591 Set for the receiving OLSRv2 interface which has L_status 1592 = SYMMETRIC and whose corresponding Neighbor Tuple has 1593 N_mpr_selector = true, then: 1595 1. Create a Forwarded Tuple with: 1597 o F_type := the Message Type of the current message; 1599 o F_orig_addr := originator address of the current 1600 message; 1602 o F_seq_number := sequence number of the current 1603 message; 1605 o F_time := current time + F_HOLD_TIME. 1607 2. The Message Header of the current message is modified 1608 by: 1610 o if present, decrement in the 1611 Message Header by 1, AND; 1613 o if present, increment in the 1614 Message Header by 1. 1616 3. For each OLSRv2 interface of the router, include the 1617 message in a packet to be transmitted on that OLSRv2 1618 interface, as described in Section 8. This packet 1619 MAY contain other forwarded messages and/or messages 1620 generated by this router, including by other 1621 protocols using [RFC5444]. Forwarded messages MAY be 1622 jittered as described in [RFC5148]. The value of 1623 MAXJITTER used in jittering a forwarded message MAY 1624 be based on information in that message (in 1625 particular any INTERVAL_TIME or VALIDITY_TIME TLVs in 1626 that message) or otherwise SHOULD be with a maximum 1627 delay of F_MAXJITTER. A router MAY modify the jitter 1628 applied to a message in order to more efficiently 1629 combine messages in packets, as long as the maximum 1630 jitter is not exceeded. 1632 8. Packets and Messages 1634 The packet and message format used by this protocol is defined in 1635 [RFC5444]. Except as otherwise noted, options defined in [RFC5444] 1636 may be freely used, in particular alternative formats defined by 1637 packet, message, Address Block and TLV flags. 1639 This protocol may extend HELLO messages (owned by [NHDP]) by adding a 1640 message originator address and/or TLVs to these messages when sent 1641 over OLSRv2 interfaces, and processes these HELLO messages after 1642 their processing by NHDP, as permitted by [NHDP]. 1644 This protocol defines and owns the TC Message Type. Extensions to 1645 this protocol MAY define additions to TC messages. These MAY include 1646 new Message TLVs and/or Address Block TLVs. Extensions MAY also 1647 include new Messsage Types to be handled similarly to TC messages. 1648 See Section 18. 1650 Routers using this protocol exchange information through messages. 1651 One or more messages sent by a router at the same time SHOULD be 1652 combined into a single packet (size permitting). These messages may 1653 have originated at the sending router, or have originated at another 1654 router and are forwarded by the sending router. Messages with 1655 different originating routers MAY be combined for transmission within 1656 the same packet. Messages from other protocols defined using 1657 [RFC5444] MAY be combined for transmission within the same packet. 1659 The remainder of this section defines, within the framework of 1660 [RFC5444], Message Types and TLVs specific to this protocol. All 1661 references in this specification to TLVs that do not indicate a type 1662 extension, assume Type Extension = 0. TLVs in processed messages 1663 with a type extension which is neither zero as so assumed, nor a 1664 specifically indicated non-zero type extension, are ignored. 1666 8.1. HELLO Messages 1668 A HELLO message is generated as specified in [NHDP]. In addition, a 1669 router using this protocol MUST be able to add information to such 1670 messages, prior to these being sent on an OLSRv2 interface, as 1671 permitted by [NHDP], so that all HELLO messages sent on an OLSRv2 1672 interface: 1674 o MUST allow a message originator address to be determined. This 1675 will usually use the message's element as defined 1676 in [RFC5444]. There are two permitted exceptions when the router 1677 MAY omit a element, but an originator address of 1678 the message is still correctly defined: 1680 * If the message contains only a single local interface address, 1681 and that address is equal to this router's originator address, 1682 then that local interface address is the message originator 1683 address. 1685 * If the message contains no local interface addresses, then, as 1686 specified in [NHDP], the source address of the IP datagram 1687 containing the message is recognised as the only interface 1688 address of the router. In this case, that address is also the 1689 message originator address. 1691 o MUST, if it is including any addresses from an 1692 N_neighbor_addr_list that has N_mpr = true and are associated with 1693 a TLV with Type = LINK_STATUS and Value = SYMMETRIC, include 1694 TLV(s) with Type := MPR associated with at least one such address 1695 from each such N_neighbor_addr_list. 1697 o MUST NOT include any TLVs with Type = MPR associated with any 1698 other addresses. 1700 o MAY include a message TLV with Type := MPR_WILLING, indicating the 1701 router's willingness to be selected as an MPR. 1703 An router using this protocol MUST also be able to access any 1704 incoming HELLO message received on an OLSRv2 interface, subsequent to 1705 the processing specified in [NHDP], as permitted by [NHDP]. 1707 8.1.1. HELLO Message TLVs 1709 In a HELLO message, a router MUST include an MPR_WILLING Message TLV 1710 as specified in Table 1, unless WILLINGNESS = WILL_DEFAULT (in which 1711 case it MAY be included). A router MUST NOT include more than one 1712 MPR_WILLING Message TLV. 1714 +-------------+--------------+--------------------------------------+ 1715 | Type | Value Length | Value | 1716 +-------------+--------------+--------------------------------------+ 1717 | MPR_WILLING | 1 octet | Router parameter WILLINGNESS; unused | 1718 | | | bits (based on the maximum | 1719 | | | willingness value WILL_ALWAYS) are | 1720 | | | RESERVED and SHOULD be set to zero. | 1721 +-------------+--------------+--------------------------------------+ 1723 Table 1: MPR_WILLING TLV definition 1725 If a router does not advertise an MPR_WILLING TLV in a HELLO message, 1726 then the router MUST be assumed to have WILLINGNESS equal to 1727 WILL_DEFAULT. 1729 8.1.2. HELLO Message Address Block TLVs 1731 In a HELLO message, a router MAY include MPR Address Block TLV(s) as 1732 specified in Table 2. 1734 +------+--------------+-------+ 1735 | Type | Value Length | Value | 1736 +------+--------------+-------+ 1737 | MPR | 0 octets | None. | 1738 +------+--------------+-------+ 1740 Table 2: MPR TLV definition 1742 8.2. TC Messages 1744 A TC message MUST contain: 1746 o A message originator address, using the message's 1747 element as defined in [RFC5444]. 1749 o and elements, as specified in 1750 [RFC5444]. 1752 o A element in its Message Header if the message 1753 contains a TLV with either Type = VALIDITY_TIME or Type = 1754 INTERVAL_TIME indicating more than one time value according to 1755 distance. (A TC message MAY contain even if it 1756 does not need to.) 1758 o A single Message TLV with Type := CONT_SEQ_NUM, and Type Extension 1759 := COMPLETE or Type Extension := INCOMPLETE, as specified in 1760 Section 8.2.1 (for complete and incomplete TC messages, 1761 respectively) except that the latter MAY be omitted if the message 1762 does not contain any addresses associated with a TLV with Type = 1763 NBR_ADDR_TYPE or Type = GATEWAY. 1765 o A Message TLV with Type := VALIDITY_TIME, as specified in 1766 [RFC5497]. The options included in [RFC5497] for representing 1767 zero and infinite times MUST NOT be used. 1769 o If the TC message is complete, all addresses which are the 1770 N_orig_addr of a Neighbor Tuple with N_advertised = true, each 1771 associated with a TLV with Type = NBR_ADDR_TYPE, and Value = 1772 ORIGINATOR, or with Value = ROUTABLE_ORIG if also to be associated 1773 with Value = ROUTABLE, see Section 8.2.2. If the TC message is 1774 incomplete then any such addresses MAY be included; if any such 1775 addresses are included then this MUST be with the appropriate 1776 associated TLV(s). 1778 o If the TC message is complete, all routable addresses which are in 1779 the N_neighbor_addr_list of a Neighbor Tuple with N_advertised = 1780 true. Each such address MUST be associated with a TLV with Type = 1781 NBR_ADDR_TYPE, and Value = ROUTABLE, or with Value = ROUTABLE_ORIG 1782 if also to be associated with Value = ORIGINATOR, see 1783 Section 8.2.2. If the TC message is incomplete then any such 1784 addresses MAY be included; if any such addresses are included then 1785 this MUST be with the appropriate associated TLV(s). 1787 o If the TC message is complete, all addresses which are the 1788 AL_net_addr of a Local Attached Network Tuple. Each such address 1789 MUST be associated with a TLV with Type = GATEWAY, and Value = 1790 AN_dist as specified in Section 8.2.2. If the TC message is 1791 incomplete then any such addresses MAY be included; if included 1792 then this MUST be with the appropriate associated TLV. 1794 A TC message MAY contain: 1796 o A Message TLV with Type := INTERVAL_TIME, as specified in 1797 [RFC5497]. The options included in [RFC5497] for representing 1798 zero and infinite times MUST NOT be used. 1800 8.2.1. TC Message TLVs 1802 In each TC message which contains any addresses associated with a TLV 1803 with Type = NBR_ADDR_TYPE or Type = GATEWAY, a router MUST include a 1804 single CONT_SEQ_NUM Message TLV, as specified in Table 3, and with 1805 Type Extension = COMPLETE or Type Extension = INCOMPLETE, according 1806 to whether the TC message is complete or incomplete. 1808 +--------------+--------------+-------------------------------------+ 1809 | Type | Value Length | Value | 1810 +--------------+--------------+-------------------------------------+ 1811 | CONT_SEQ_NUM | 2 octets | The ANSN contained in the Neighbor | 1812 | | | Information Base. | 1813 +--------------+--------------+-------------------------------------+ 1815 Table 3: CONT_SEQ_NUM TLV definition 1817 8.2.2. TC Message Address Block TLVs 1819 In a TC message, a router MAY include NBR_ADDR_TYPE Address Block 1820 TLV(s) as specified in Table 4. 1822 +---------------+--------------+------------------------------------+ 1823 | Type | Value Length | Value | 1824 +---------------+--------------+------------------------------------+ 1825 | NBR_ADDR_TYPE | 1 octet | ORIGINATOR indicates that the | 1826 | | | address is an originator address, | 1827 | | | ROUTABLE indicates that the | 1828 | | | address is a routable address of | 1829 | | | an interface, ROUTABLE_ORIG | 1830 | | | indicates that the address is both | 1831 +---------------+--------------+------------------------------------+ 1833 Table 4: NBR_ADDR_TYPE TLV definition 1835 If an address is both a originator address and a routable interface 1836 address, then it may be associated, using a TLV with Type = 1837 NBR_ADDR_TYPE, with either a Value = ROUTABLE_ORIG, or (using two 1838 separate TLVs) both with Value = ORIGINATOR and with Value = 1839 ROUTABLE. 1841 In a TC message, a router MAY include GATEWAY Address Block TLV(s) as 1842 specified in Table 5. 1844 +---------+--------------+-------------------------------------+ 1845 | Type | Value Length | Value | 1846 +---------+--------------+-------------------------------------+ 1847 | GATEWAY | 1 octet | Number of hops to attached network. | 1848 +---------+--------------+-------------------------------------+ 1850 Table 5 1852 All addresses included in a TC message according to this 1853 specification MUST be associated with either at least one TLV with 1854 Type = NBR_ADDR_TYPE or a TLV with Type = GATEWAY, but not both. 1855 Other addresses MAY be included in the TC message, but (other than 1856 the message originator address) are ignored by this specification. 1858 9. HELLO Message Generation 1860 An HELLO message is composed and generated as defined in [NHDP], 1861 extended by the following being added to the HELLO message by this 1862 protocol before being sent over an OLSRv2 interface, as permitted by 1863 [NHDP]: 1865 o A message originator address, using a element, 1866 unless: 1868 * The message contains only a single local interface address, 1869 which is then interpreted as the message originator address, 1870 OR; 1872 * The message does not include any local interface addresses, as 1873 permitted by the specification in [NHDP] when the router that 1874 generated the HELLO message has only one interface address, and 1875 will use that as the sending address of the IP datagram in 1876 which the HELLO message is contained. In this case that 1877 address MAY also be used as the message originator address. 1879 o A Message TLV with Type := MPR_WILLING and Value := WILLINGNESS 1880 MUST be included, unless WILLINGNESS = WILL_DEFAULT (in which case 1881 it MAY be included). 1883 o For each Neighbor Tuple with N_mpr = true, and for which one or 1884 more addresses in its N_neighbor_addr_list are included with an 1885 associated TLV with Type = LINK_STATUS and Value = SYMMETRIC, at 1886 least one of these addresses (including a different copy of that 1887 address, in the same or a different Address Block) MUST be 1888 associated with an Address Block TLV with Type := MPR. Note that 1889 other addresses (which do not meet this specification) MUST NOT be 1890 associated with an Address Block TLV with Type = MPR, but that 1891 more than one address from the same qualifying 1892 N_neighbor_addr_list MAY be associated with an Address Block TLV 1893 with Type := MPR. 1895 o An additional HELLO message MAY be sent when the router's set of 1896 MPRs changes, in addition to the cases specified in [NHDP], and 1897 subject to the same constraints. 1899 9.1. HELLO Message: Transmission 1901 HELLO messages are included in packets as specified in [RFC5444]. 1902 These packets may contain other messages, including TC messages. 1904 10. HELLO Message Processing 1906 All HELLO message processing, including determination of whether a 1907 message is invalid, considers only TLVs with Type Extension = 0. 1908 TLVs with any other type extension are ignored. All references to, 1909 for example, a TLV with Type = MPR_WILLING refer to a TLV with Type = 1910 MPR_WILLING and Type Extension = 0. 1912 In addition to the reasons specified in [NHDP] for discarding a HELLO 1913 message on reception, a HELLO message MUST be discarded before 1914 processing by [NHDP] or this specification if it: 1916 o Has more than one TLV with Type = MPR_WILLING in its Message TLV 1917 Block. 1919 o Has a message originator address, or any address associated with a 1920 TLV with Type = LOCAL_IF, that the receiving router has recorded 1921 as: 1923 * its originator address, OR; 1925 * as the O_orig_addr in an Originator Tuple, OR; 1927 * in an I_local_iface_addr_list in a Local Interface Tuple, OR; 1929 * as the IR_local_iface_addr in a Removed Interface Address 1930 Tuple, OR; 1932 * as the AL_net_addr in a Local Attached Network Tuple. 1934 Note that some of these cases are already excluded by [NHDP]. 1936 o Includes any address associated with a TLV with Type = LINK_STATUS 1937 or Type = OTHER_NEIGHB that is also the message's originator 1938 address. 1940 o Contains any address associated with a TLV with Type = MPR, where 1941 that address (including a different copy of that address, in the 1942 same or a different Address Block) is not also associated with a 1943 TLV with Type = LINK_STATUS and Value = SYMMETRIC. 1945 HELLO messages are first processed as specified in [NHDP]. That 1946 processing includes identifying (or creating) a Neighbor Tuple 1947 corresponding to the originator of the HELLO message (the "current 1948 Neighbor Tuple"). After this, the following MUST be performed: 1950 1. If the HELLO message has a well-defined message originator 1951 address, i.e., has an element or has zero or one 1952 addresses associated with a TLV with Type = LOCAL_IF: 1954 1. Remove any other Neighbor Tuples with N_orig_addr = message 1955 originator address, taking any consequent action (including 1956 removing one or more Link Tuples) as specified in [NHDP]. 1958 2. The current Neighbor Tuple is then updated according to: 1960 1. N_orig_addr := message originator address; 1962 2. Update N_willingness as described in Section 10.1; 1964 3. Update N_mpr_selector as described in Section 10.2. 1966 2. If there are any changes to the router's Information Bases, then 1967 perform the processing defined in Section 13. 1969 10.1. Updating Willingness 1971 N_willingness in the current Neighbor Tuple is updated as follows: 1973 1. If the HELLO message contains a Message TLV with Type = 1974 MPR_WILLING then N_willingness := the Value of that TLV; 1976 2. Otherwise, N_willingness := WILL_DEFAULT. 1978 10.2. Updating MPR Selectors 1980 N_mpr_selector is updated as follows: 1982 1. If a router finds any of its local interface addresses (i.e., 1983 those contained in the I_local_iface_addr_list of an OLSRv2 1984 interface) with an associated TLV with Type = MPR in the HELLO 1985 message (indicating that the originating router has selected the 1986 receiving router as an MPR) then, for the current Neighbor Tuple: 1988 * N_mpr_selector := true 1990 2. Otherwise (i.e., if no such address and TLV were found) if a 1991 router finds any of its local interface addresses with an 1992 associated TLV with Type = LINK_STATUS and Value = SYMMETRIC in 1993 the HELLO message, then for the current Neighbor Tuple: 1995 * N_mpr_selector := false 1997 * N_advertised := false 1999 11. TC Message Generation 2001 A router with one or more OLSRv2 interfaces, and with any Neighbor 2002 Tuples with N_advertised = true, or with a non-empty Local Attached 2003 Network Set MUST generate TC messages. A router which does not have 2004 such information to advertise SHOULD also generate "empty" TC 2005 messages for a period A_HOLD_TIME after it last generated a non-empty 2006 TC message. TC messages (non-empty and empty) are generated 2007 according to the following: 2009 1. The message originator address MUST be the router's originator 2010 address. 2012 2. The message hop count, if included, MUST be set to zero. 2014 3. The message hop limit MUST be set to a value greater than 1. A 2015 router MAY use the same hop limit TC_HOP_LIMIT in all TC 2016 messages, or use different values of the hop limit TC_HOP_LIMIT 2017 in TC messages, see Section 5.8. 2019 4. The message MUST contain a Message TLV with Type := CONT_SEQ_NUM 2020 and Value := ANSN from the Neighbor Information Base. If the TC 2021 message is complete then this Message TLV MUST have Type 2022 Extension := COMPLETE, otherwise it MUST have Type Extension := 2023 INCOMPLETE. (Exception: a TC message MAY omit such a Message TLV 2024 if the TC message is not reporting any addresses with associated 2025 TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY.) 2027 5. The message MUST contain a Message TLV with Type := 2028 VALIDITY_TIME, as specified in [RFC5497]. If all TC messages are 2029 sent with the same hop limit then this TLV MUST have Value := 2030 T_HOLD_TIME. If TC messages are sent with different hop limits 2031 (more than one value of TC_HOP_LIMIT) then this TLV MUST specify 2032 times which vary with the number of hops distance appropriate to 2033 the chosen pattern of TC message hop limits, as specified in 2034 [RFC5497], these times SHOULD be appropriate multiples of 2035 T_HOLD_TIME. 2037 6. The message MAY contain a Message TLV with Type := INTERVAL_TIME, 2038 as specified in [RFC5497]. If all TC messages are sent with the 2039 same hop limit then this TLV MUST have Value := TC_INTERVAL. If 2040 TC messages are sent with different hop limits, then this TLV 2041 MUST specify times which vary with the number of hops distance 2042 appropriate to the chosen pattern of TC message hop limits, as 2043 specified in [RFC5497], these times SHOULD be appropriate 2044 multiples of TC_INTERVAL. 2046 7. A complete message MUST include, and an incomplete message MAY 2047 include, in its Address Blocks: 2049 1. N_orig_addr in each Neighbor Tuple with N_advertised = true, 2050 associated with a TLV with Type := NBR_ADDR_TYPE and Value := 2051 ORIGINATOR (or Value := ROUTABLE_ORIG if also to be 2052 associated with Value = ROUTABLE). 2054 2. Each routable address in an N_neighbor_addr_list in each 2055 Neighbor Tuple with N_advertised = true, associated with a 2056 TLV with Type := NBR_ADDR_TYPE and Value := ROUTABLE (or 2057 Value := ROUTABLE_ORIG if also to be associated with Value = 2058 ORIGINATOR). 2060 3. AL_net_addr in each Local Attached Neighbor Tuple, each 2061 associated with a TLV with Type := GATEWAY and Value := 2062 AL_dist. 2064 11.1. TC Message Transmission 2066 Complete TC messages are generated and transmitted periodically on 2067 all OLSRv2 interfaces, with a default interval between two 2068 consecutive TC transmissions by the same router of TC_INTERVAL. 2070 TC messages MAY be generated in response to a change in the 2071 information which they are to advertise, indicated by a change in 2072 ANSN. In this case a router MAY send a complete TC message, and if 2073 so MAY re-start its TC message schedule. Alternatively a router MAY 2074 send an incomplete TC message with at least the newly advertised 2075 addresses (i.e. not previously, but now, an N_orig_addr or an 2076 N_neighbor_addr_list in a Neighbor Tuple with N_advertised = true, or 2077 in an AL_net_addr) in its Address Blocks, with associated TLV(s). 2078 Note that a router cannot report removal of advertised content using 2079 an incomplete TC message. 2081 When sending a TC message in response to a change of advertised 2082 addresses, a router must respect a minimum interval of 2083 TC_MIN_INTERVAL between generated TC messages. Sending an incomplete 2084 TC message MUST NOT cause the interval between complete TC messages 2085 to be increased, and thus a router MUST NOT send an incomplete TC 2086 message if within TC_MIN_INTERVAL of the next scheduled complete TC 2087 message. 2089 The generation of TC messages, whether scheduled or triggered by a 2090 change of contents MAY be jittered as described in [RFC5148]. The 2091 values of MAXJITTER used SHOULD be: 2093 o TP_MAXJITTER for periodic TC message generation; 2095 o TT_MAXJITTER for responsive TC message generation. 2097 TC messages are included in packets as specified in [RFC5444]. These 2098 packets MAY contain other messages, including HELLO messages and TC 2099 messages with different originator addresses. TC messages are 2100 forwarded according to the specification in Section 7.3. 2102 12. TC Message Processing 2104 On receiving a TC message, a router MUST first check if the message 2105 is invalid for processing by this router, as defined in Section 12.1. 2106 Otherwise the receiving router MUST update its appropriate Interface 2107 Information Base and its Router Information Base as specified in 2108 Section 12.2. 2110 All TC message processing, including determination of whether a 2111 message is invalid, unless otherwise noted considers only TLVs with 2112 Type Extension = 0. TLVs with any other type extension (or any 2113 unmentioned type extension when other type extensions are considered) 2114 are ignored. All references to, for example, a TLV with Type = 2115 VALIDITY_TIME refer to a TLV with Type = VALIDITY_TIME and Type 2116 Extension = 0. 2118 Following TC message processing, if there are any changes in the 2119 router's Information Bases, then the processing in Section 13 MUST be 2120 performed. 2122 12.1. Invalid Message 2124 A received TC message is invalid for processing by this router if the 2125 message: 2127 o Does not include a message originator address, a message sequence 2128 number, and a hop limit. 2130 o Does not include a hop count, and contains a multi-value TLV with 2131 Type = VALIDITY_TIME or Type = INTERVAL_TIME, as defined in 2132 [RFC5497]. 2134 o Does not have exactly one TLV with Type = VALIDITY_TIME in its 2135 Message TLV Block. 2137 o Has more than one TLV with Type = INTERVAL_TIME in its Message TLV 2138 Block. 2140 o Does not have a TLV with Type = CONT_SEQ_NUM and Type Extension = 2141 COMPLETE or Type Extension = INCOMPLETE in its Message TLV Block, 2142 and contains at least one address associated with a TLV with Type 2143 = NBR_ADDR_TYPE or Type = GATEWAY. 2145 o Has more than one TLV with Type = CONT_SEQ_NUM and Type Extension 2146 = COMPLETE or Type Extension = INCOMPLETE in its Message TLV 2147 Block. 2149 o Has a message originator address, or any address associated with a 2150 TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY, that the 2151 receiving router has recorded as: 2153 * its originator address, OR; 2155 * as the O_orig_addr in an Originator Tuple, OR; 2157 * in an I_local_iface_addr_list in a Local Interface Tuple, OR; 2159 * the IR_local_iface_addr in a Removed Interface Address Tuple. 2161 o Has a message originator address, or any address associated with a 2162 TLV with Type = NBR_ADDR_TYPE, that the receiving router has 2163 recorded as the AL_net_addr in a Local Attached Network Tuple. 2165 o Includes any address with a prefix length which is not maximal 2166 (equal to the address length, in bits) associated with a TLV with 2167 Type = NBR_ADDR_TYPE and Value = ORIGINATOR or Value = 2168 ROUTABLE_ORIG. 2170 o Includes any non-routable address associated with a TLV with Type 2171 = NBR_ADDR_TYPE and Value = ROUTABLE or Value = ROUTABLE_ORIG. 2173 o Includes any address associated with a TLV with Type = 2174 NBR_ADDR_TYPE or Type = GATEWAY that is also the message's 2175 originator address. 2177 o Associates any address (including different copies of an address, 2178 in the same or different Address Blocks) with more than one single 2179 Value using one or more TLV(s) with Type = GATEWAY. 2181 o Associates any address (including different copies of an address, 2182 in the same or different Address Blocks) with TLVs with Type = 2183 NBR_ADDR_TYPE and Type = GATEWAY. 2185 A router MAY recognize additional reasons for identifying that a 2186 message is invalid. An invalid message MUST be silently discarded, 2187 without updating the router's Information Bases. 2189 12.2. TC Message Processing Definitions 2191 When, according to Section 7.2, a TC message is to be "processed 2192 according to its type", this means that: 2194 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2195 and Type Extension = COMPLETE, then processing according to 2196 Section 12.3 and then according to Section 12.4 is carried out. 2198 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2199 and Type Extension = INCOMPLETE, then only processing according to 2200 Section 12.3 is carried out. 2202 For the purposes of this section: 2204 o "validity time" is calculated from a VALIDITY_TIME Message TLV in 2205 the TC message according to the specification in [RFC5497]. All 2206 information in the TC message has the same validity time. 2208 o "received ANSN" is defined as being the Value of a Message TLV 2209 with Type = CONT_SEQ_NUM. 2211 o Comparisons of sequence numbers are carried out as specified in 2212 Section 17. 2214 12.3. Initial TC Message Processing 2216 The TC message is processed as follows: 2218 1. The Advertising Remote Router Set is updated according to 2219 Section 12.3.1. If the TC message is indicated as discarded in 2220 that processing then the following steps are not carried out. 2222 2. The Router Topology Set is updated according to Section 12.3.2. 2224 3. The Routable Address Topology Set is updated according to 2225 Section 12.3.3. 2227 4. The Attached Network Set is updated according to Section 12.3.4. 2229 12.3.1. Populating the Advertising Remote Router Set 2231 The router MUST update its Advertising Remote Router Set as follows: 2233 1. If there is an Advertising Remote Router Tuple with: 2235 * AR_orig_addr = message originator address; AND 2237 * AR_seq_number > received ANSN 2239 then the TC message MUST be discarded. 2241 2. Otherwise: 2243 1. If there is no Advertising Remote Router Tuple such that: 2245 + AR_orig_addr = message originator address; 2247 then create an Advertising Remote Router Tuple with: 2249 + AR_orig_addr := message originator address. 2251 2. This Advertising Remote Router Tuple (existing or new) is 2252 then modified as follows: 2254 + AR_seq_number := received ANSN; 2256 + AR_time := current time + validity time. 2258 12.3.2. Populating the Router Topology Set 2260 The router MUST update its Router Topology Set as follows: 2262 1. For each address (henceforth advertised address) in an Address 2263 Block that has an associated TLV with Type = NBR_ADDR_TYPE and 2264 Value = ORIGINATOR or Value = ROUTABLE_ORIG, perform the 2265 following processing: 2267 1. If there is no Router Topology Tuple such that: 2269 + TR_from_orig_addr = message originator address; AND 2271 + TR_to_orig_addr = advertised address 2273 then create a new Router Topology Tuple with: 2275 + TR_from_orig_addr := message originator address 2276 + TR_to_orig_addr := advertised address. 2278 2. This Router Topology Tuple (existing or new) is then modified 2279 as follows: 2281 + TR_seq_number := received ANSN; 2283 + TR_time := current time + validity time. 2285 12.3.3. Populating the Routable Address Topology Set 2287 The router MUST update its Routable Address Topology Set as follows: 2289 1. For each address (henceforth advertised address) in an Address 2290 Block that has an associated TLV with Type = NBR_ADDR_TYPE and 2291 Value = ROUTABLE or Value = ROUTABLE_ORIG, perform the following 2292 processing: 2294 1. If there is no Routable Address Topology Tuple such that: 2296 + TA_from_orig_addr = message originator address; AND 2298 + TA_dest_addr = advertised address 2300 then create a new Routable Address Topology Tuple with: 2302 + TA_from_orig_addr := message originator address; 2304 + TA_dest_addr := advertised address. 2306 2. This Routable Address Topology Tuple (existing or new) is 2307 then modified as follows: 2309 + TA_seq_number := received ANSN; 2311 + TA_time := current time + validity time. 2313 12.3.4. Populating the Attached Network Set 2315 The router MUST update its Attached Network Set as follows: 2317 1. For each address (henceforth advertised address) in an Address 2318 Block that has an associated TLV with Type = GATEWAY, and is not 2319 an AL_net_addr in a Local Attached Network Tuple, perform the 2320 following processing: 2322 1. If there is no Attached Network Tuple such that: 2324 + AN_net_addr = network address; AND 2326 + AN_orig_addr = message originator address 2328 then create a new Attached Network Tuple with: 2330 + AN_net_addr := network address; 2332 + AN_orig_addr := message originator address. 2334 2. This Attached Network Tuple (existing or new) is then 2335 modified as follows: 2337 + AN_dist := the Value of the associated GATEWAY TLV; 2339 + AN_seq_number := received ANSN; 2341 + AN_time := current time + validity time. 2343 12.4. Completing TC Message Processing 2345 The TC message is processed as follows: 2347 1. The Router Topology Set is updated according to Section 12.4.1. 2349 2. The Routable Address Topology Set is updated according to 2350 Section 12.4.2. 2352 3. The Attached Network Set is updated according to Section 12.4.3. 2354 12.4.1. Purging the Router Topology Set 2356 The Router Topology Set MUST be updated as follows: 2358 1. Any Router Topology Tuples with: 2360 * TR_from_orig_addr = message originator address; AND 2362 * TR_seq_number < received ANSN 2364 MUST be removed. 2366 12.4.2. Purging the Routable Address Topology Set 2368 The Routable Address Topology Set MUST be updated as follows: 2370 1. Any Routable Address Topology Tuples with: 2372 * TA_from_orig_addr = message originator address; AND 2374 * TA_seq_number < received ANSN 2376 MUST be removed. 2378 12.4.3. Purging the Attached Network Set 2380 The Attached Network Set MUST be updated as follows: 2382 1. Any Attached Network Tuples with: 2384 * AN_orig_addr = message originator address; AND 2386 * AN_seq_number < received ANSN 2388 MUST be removed. 2390 13. Information Base Changes 2392 The changes described in the following sections MUST be carried out 2393 when any Information Base changes as indicated. 2395 13.1. Originator Address Changes 2397 If the router changes originator address, then: 2399 1. If there is no Originator Tuple with: 2401 * O_orig_addr = old originator address 2403 then create an Originator Tuple with: 2405 * O_orig_addr := old originator address 2407 The Originator Tuple (existing or new) with: 2409 * O_orig_addr = new originator address 2411 is then modified as follows: 2413 * O_time := current time + O_HOLD_TIME 2415 13.2. Neighbor State Changes 2417 The N_mpr_selector and N_advertised flags in Neighbor Tuples MUST be 2418 maintained according to the following rules: 2420 1. If N_symmetric = false, then N_mpr_selector = false and 2421 N_advertised = false. 2423 2. If N_mpr_selector = true, then N_advertised = true. 2425 3. In other cases (i.e. N_symmetric = true and N_mpr_selector = 2426 false) a router MAY select N_advertised = true or N_advertised = 2427 false. The more neighbors that are advertised, the larger TC 2428 messages become, but the more redundancy is available for 2429 routing. A router SHOULD consider the nature of its network in 2430 making such a decision, and SHOULD avoid unnecessary changes in 2431 advertising status, which may result both in additional TC 2432 messages having to be sent by its neighbors, and in unnecessary 2433 changes to routing, which will have similar effects to other 2434 forms of topology changes in the MANET. 2436 13.3. Advertised Neighbor Changes 2438 The router MUST increment the ANSN in the Neighbor Information Base 2439 whenever: 2441 1. Any Neighbor Tuple changes its N_advertised value. 2443 2. N_orig_addr is changed, or any routable address is added to or 2444 removed from any Neighbor Tuple with N_advertised = true. 2446 3. There is any change to the Local Attached Network Set. 2448 13.4. Advertising Remote Router Tuple Expires 2450 The Router Topology Set, the Routable Address Topology Set and the 2451 Attached Network Set MUST be changed when an Advertising Remote 2452 Router Tuple expires (AR_time is reached). The following changes are 2453 required before the Advertising Remote Router Tuple is removed: 2455 1. All Router Topology Tuples with: 2457 * TR_from_orig_addr = AR_orig_addr of the Advertising Remote 2458 Router Tuple 2460 are removed. 2462 2. All Routable Address Topology Tuples with: 2464 * TA_from_orig_addr = AR_orig_addr of the Advertising Remote 2465 Router Tuple 2467 are removed. 2469 3. All Attached Network Tuples with: 2471 * AN_orig_addr = AR_orig_addr of the Advertising Remote Router 2472 Tuple 2474 are removed. 2476 13.5. Neighborhood Changes and MPR Updates 2478 The set of symmetric 1-hop neighbors selected as MPRs MUST satisfy 2479 the conditions defined in Section 14. To ensure this: 2481 1. The set of MPRs of a router MUST be recalculated if: 2483 * a Link Tuple is added with L_status = SYMMETRIC, OR; 2485 * a Link Tuple with L_status = SYMMETRIC is removed, OR; 2487 * a Link Tuple with L_status = SYMMETRIC changes to having 2488 L_status = HEARD or L_status = LOST, OR; 2490 * a Link Tuple with L_status = HEARD or L_status = LOST changes 2491 to having L_status = SYMMETRIC, OR; 2493 * a 2-Hop Tuple is added or removed, OR; 2495 * the N_willingness of a Neighbor Tuple with N_symmetric = true 2496 changes from WILL_NEVER to any other value, OR; 2498 * the N_willingness of a Neighbor Tuple with N_symmetric = true 2499 and N_mpr = true changes to WILL_NEVER from any other value, 2500 OR; 2502 * the N_willingness of a Neighbor Tuple with N_symmetric = true 2503 and N_mpr = false changes to WILL_ALWAYS from any other value. 2505 2. Otherwise, the set of MPRs of a router MAY be recalculated if the 2506 N_willingness of a Neighbor Tuple with N_symmetric = true changes 2507 in any other way; it SHOULD be recalculated if N_mpr = false and 2508 this is an increase in N_willingness or if N_mpr = true and this 2509 is a decrease in N_willingness. 2511 If the set of MPRs of a router is recalculated, this MUST be as 2512 described in Section 14. Before that calculation, the N_mpr of all 2513 Neighbor Tuples are set false (although the previous values of N_mpr 2514 MAY be used by an algorithm that minimises changes to the set of 2515 MPRs). After that calculation the N_mpr of all Neighbor Tuples 2516 representing symmetric 1-hop neighbors which are chosen as MPRs, are 2517 set true. 2519 13.6. Routing Set Updates 2521 The Routing Set MUST be updated, as described in Section 15 when 2522 changes in the Local Information Base, the Neighborhood Information 2523 Base or the Topology Information Base indicate a change of the known 2524 symmetric links and/or attached networks in the MANET, hence changing 2525 the Topology Graph. It is sufficient to consider only changes which 2526 affect at least one of: 2528 o The Local Interface Set, if the change removes any address in an 2529 I_local_iface_addr_list. In this case, unless the OLSRv2 2530 interface is removed, it may not be necessary to do more than 2531 replace such addresses, if used, by an alternative address from 2532 the same I_local_iface_addr_list. 2534 o The Local Attached Set, if the change removes any AL_net_addr 2535 which is also an AN_net_addr. In this case it may not be 2536 necessary to do more than add and remove Routing Tuples with 2537 R_dest_addr equal to that AN_net_addr. 2539 o The Link Set of any OLSRv2 interface, and to consider only Link 2540 Tuples which have, or just had, L_status = SYMMETRIC (including 2541 removal of such Link Tuples). 2543 o The Neighbor Set of the router, and to consider only Neighbor 2544 Tuples that have, or just had, N_symmetric = true, and do not have 2545 N_orig_addr = unknown. 2547 o The 2-Hop Set of any OLSRv2 interface, if used in the creation of 2548 the Routing Set. 2550 o The Router Topology Set of the router. 2552 o The Routable Address Topology Set of the router. 2554 o The Attached Network Set of the router. 2556 14. Selecting MPRs 2558 Each router MUST select, from among its willing symmetric 1-hop 2559 neighbors, a subset of these routers as MPRs. Only MPRs forward 2560 control messages flooded through the MANET, thus effecting a flooding 2561 reduction, an optimization of the classical flooding mechanism, known 2562 as MPR flooding. MPRs MAY also be used to effect a topology 2563 reduction in the MANET. Consequently, while it is not essential that 2564 the set of MPRs is minimal, keeping the number of MPRs small ensures 2565 that the overhead is kept at a minimum. 2567 A router MUST select MPRs for each of its OLSRv2 interfaces, but then 2568 forms the union of those sets as its single set of MPRs. This union 2569 MUST include all symmetric 1-hop neighbors with willingness 2570 WILL_ALWAYS. Only this overall set of MPRs is relevant, the recorded 2571 and used MPR relationship is one of routers, not interfaces. Routers 2572 MAY select their MPRs by any process which satisfies the conditions 2573 which follow. Routers can freely interoperate whether they use the 2574 same or different MPR selection algorithms. 2576 For each OLSRv2 interface a router MUST select a set of MPRs. This 2577 set MUST have the properties that: 2579 o All of the selected MPRs are willing symmetric 1-hop neighbors, 2580 AND; 2582 o If the selecting router sends a message on that OLSRv2 interface, 2583 and that message is successfully forwarded by all of the selected 2584 MPRs for that interface, then all symmetric strict 2-hop neighbors 2585 of the selecting router through that OLSRv2 interface will receive 2586 that message over a symmetric link. 2588 Note that it is always possible to select a valid set of MPRs. The 2589 set of all willing symmetric 1-hop neighbors of a router is a 2590 (maximal) valid set of MPRs for that router. However a router SHOULD 2591 NOT select a symmetric 1-hop neighbor with Willingness != WILL_ALWAYS 2592 as an MPR if there are no symmetric strict 2-hop neighbors with a 2593 symmetric link to that symmetric 1-hop neighbor. Thus a router with 2594 no symmetric 1-hop neighbors with willingness WILL_ALWAYS and with no 2595 symmetric strict 2-hop neighbors SHOULD NOT select any MPRs. 2597 A router MAY select its MPRs for each OLSRv2 interface independently, 2598 or it MAY coordinate its MPR selections across its OLSRv2 interfaces, 2599 as long as the required condition is satisfied for each OLSRv2 2600 interface. Each router MAY select its MPRs independently from the 2601 MPR selection by other routers, or it MAY, for example, give 2602 preference to routers that either are, or are not, already selected 2603 as MPRs by other routers. 2605 When selecting MPRs for each OLSRv2 interface independently, this MAY 2606 be done using information from the Link Set and 2-Hop Set of that 2607 OLSRv2 interface only, and the Neighbor Set of the router 2608 (specifically the N_willingness elements). 2610 The selection of MPRs (overall, not per OLSRv2 interface) is recorded 2611 in the Neighbor Set of the router (using the N_mpr elements). A 2612 selected MPR MUST be a willing symmetric 1-hop neighbor (i.e. the 2613 corresponding N_symmetric = true, and the corresponding N_willingness 2614 != WILL_NEVER). 2616 A router MUST recalculate its MPRs whenever the currently selected 2617 set of MPRs does not still satisfy the required conditions. It MAY 2618 recalculate its MPRs if the current set of MPRs is still valid, but 2619 could be more efficient. Sufficient conditions to recalculate a 2620 router's set of MPRs are given in Section 13.5. 2622 An example algorithm that creates a set of MPRs that satisfies the 2623 required conditions is given in Appendix A. 2625 15. Routing Set Calculation 2627 The Routing Set of a router is populated with Routing Tuples that 2628 represent paths from that router to all destinations in the network. 2629 These paths are calculated based on the Network Topology Graph, which 2630 is constructed from information in the Information Bases, obtained 2631 via HELLO and TC message exchange. 2633 Changes to the Routing Set do not require any messages to be 2634 transmitted. The state of the Routing Set SHOULD, however, be 2635 reflected in IP's routing table by adding and removing entries from 2636 IP's routing table as appropriate. Only appropriate Routing Tuples 2637 (in particular only those that represent local links or paths to 2638 routable addresses) need be reflected in IP's routing table. 2640 15.1. Network Topology Graph 2642 The Network Topology Graph is formed from information from the 2643 router's Local Interface Set, Link Sets, Neighbor Set, Router 2644 Topology Set, Routable Address Topology Set and Attached Network Set. 2645 The Network Topology Graph MAY also use information from the router's 2646 2-Hop Sets. The Network Topology Graph forms the router's 2647 topological view of the network in form of a directed graph. The 2648 Network Topology Graph has a "backbone" (within which minimum 2649 distance routes will be constructed) containing the following edges: 2651 o Edges X -> Y for all possible Y, and one X per Y, such that: 2653 * Y is the N_orig_addr of a Neighbor Tuple, AND; 2655 * N_orig_addr is not unknown; 2657 * X is in the I_local_iface_addr_list of a Local Interface Tuple, 2658 AND; 2660 * There is a Link Tuple with L_status = SYMMETRIC such that this 2661 Neighbor Tuple and this Local Interface Tuple correspond to it. 2662 An address from L_neighbor_iface_addr_list will be denoted R in 2663 this case. 2665 It SHOULD be preferred, where possible, to select R = S and X from 2666 the Local Interface Tuple corresponding to the Link Tuple from 2667 which R was selected. 2669 o All edges W -> U such that: 2671 * W is the TR_from_orig_addr of a Router Topology Tuple, AND; 2673 * U is the TR_to_orig_addr of the same Router Topology Tuple. 2675 The Network Topology Graph is further "decorated" with the following 2676 edges. If an address S, V, Z or T equals an address Y or W, then the 2677 edge terminating in the address S, V, Z or T MUST NOT be used in any 2678 path. 2680 o Edges X -> S for all possible S, and one X per S, such that: 2682 * S is in the N_neighbor_addr_list of a Neighbor Tuple, AND; 2684 * X is in the I_local_iface_addr_list of a Local Interface Tuple, 2685 AND; 2687 * There is a Link Tuple with L_status = SYMMETRIC such that this 2688 Neighbor Tuple and this Local Interface Tuple correspond to it. 2689 An address from L_neighbor_iface_addr_list will be denoted R in 2690 this case. 2692 It SHOULD be preferred, where possible, to select R = S and X from 2693 the Local Interface Tuple corresponding to the Link Tuple from 2694 which R was selected. 2696 o All edges W -> V such that: 2698 * W is the TA_from_orig_addr of a Routable Address Topology 2699 Tuple, AND; 2701 * V is the TA_dest_addr of the same Routable Address Topology 2702 Tuple. 2704 o All edges W -> T such that: 2706 * W is the AN_orig_addr of an Attached Network Tuple, AND; 2707 * T is the AN_net_addr of the same Attached Network Tuple. 2709 o OPTIONALLY, all edges Y -> Z such that: 2711 * Z is a routable address and is the N2_2hop_addr of a 2-Hop 2712 Tuple, AND; 2714 * Y is the N_orig_addr of the corresponding Neighbor Tuple, AND; 2716 * This Neighbor Tuple has N_willingness not equal to WILL_NEVER. 2718 A path terminating with such an edge SHOULD NOT be used in 2719 preference to any other path. 2721 Any part of the Topology Graph which is not connected to an address X 2722 is not used. Only one selection X need be made from each 2723 I_local_iface_addr_list, and only one selection R need be made from 2724 any L_neighbor_iface_addr_list. All edges have a cost (hop count) of 2725 one, except edges W -> T which each have a cost (hop count) equal to 2726 the appropriate value of AN_dist. 2728 15.2. Populating the Routing Set 2730 The Routing Set MUST contain the shortest paths for all destinations 2731 from all local OLSRv2 interfaces using the Network Topology Graph. 2732 This calculation MAY use any algorithm, including any means of 2733 choosing between paths of equal length. 2735 Using the notation of Section 15.1, initially "backbone" paths using 2736 only edges X -> Y and W -> U need be constructed (using a minimum 2737 distance algorithm). Then paths using only a final edge of the other 2738 types may be added. These MUST NOT replace backbone paths with the 2739 same destination (and paths terminating in an edge Y -> Z SHOULD NOT 2740 replace paths with any other form of terminating edge). 2742 Each path will correspond to a Routing Tuple. These will be of two 2743 types. The first type will represent single edge paths, of type X -> 2744 S or X -> Y, by: 2746 o R_local_iface_addr := X; 2748 o R_next_iface_addr := R; 2750 o R_dest_addr := S or Y; 2752 o R_dist := 1, 2754 where R is as defined in Section 15.1 for these types of edges. 2756 The second type will represent a multiple edge path, which will 2757 always have first edge of type X -> Y, and will have final edge of 2758 type W -> U, W -> V, W -> T or Y -> Z. The Routing Tuple will be: 2760 o R_local_iface_addr := X; 2762 o R_next_iface_addr := Y; 2764 o R_dest_addr := U, V, T or Z; 2766 o R_dist := the total hop count of the path. 2768 Finally, Routing Tuples of the second type whose R_dest_addr is not 2769 routable MAY be discarded. 2771 An example algorithm for calculating the Routing Set of a router is 2772 given in Appendix B. 2774 16. Proposed Values for Parameters and Constants 2776 This protocol uses all parameters and constants defined in [NHDP] and 2777 additional parameters and constants defined in this document. All 2778 but one (RX_HOLD_TIME) of these additional parameters are router 2779 parameters as defined in [NHDP]. These proposed values of the 2780 additional parameters are appropriate to the case where all 2781 parameters (including those defined in [NHDP]) have a single value. 2782 Proposed values for parameters defined in [NHDP] are given in that 2783 document. 2785 16.1. Local History Time Parameters 2787 o O_HOLD_TIME := 30 seconds 2789 16.2. Message Interval Parameters 2791 o TC_INTERVAL := 5 seconds 2793 o TC_MIN_INTERVAL := TC_INTERVAL/4 2795 16.3. Advertised Information Validity Time Parameters 2797 o T_HOLD_TIME := 3 x TC_INTERVAL 2799 o A_HOLD_TIME := T_HOLD_TIME 2801 16.4. Received Message Validity Time Parameters 2803 o RX_HOLD_TIME := 30 seconds 2805 o P_HOLD_TIME := 30 seconds 2807 o F_HOLD_TIME := 30 seconds 2809 16.5. Jitter Time Parameters 2811 o TP_MAXJITTER := HP_MAXJITTER 2813 o TT_MAXJITTER := HT_MAXJITTER 2815 o F_MAXJITTER := TT_MAXJITTER 2817 16.6. Hop Limit Parameter 2819 o TC_HOP_LIMIT := 255 2821 16.7. Willingness Parameter and Constants 2823 o WILLINGNESS := WILL_DEFAULT 2825 o WILL_NEVER := 0 2827 o WILL_DEFAULT := 3 2829 o WILL_ALWAYS := 7 2831 17. Sequence Numbers 2833 Sequence numbers are used in this specification for the purpose of 2834 discarding "old" information, i.e. messages received out of order. 2835 However with a limited number of bits for representing sequence 2836 numbers, wrap-around (that the sequence number is incremented from 2837 the maximum possible value to zero) will occur. To prevent this from 2838 interfering with the operation of this protocol, the following MUST 2839 be observed when determining the ordering of sequence numbers. 2841 The term MAXVALUE designates in the following one more than the 2842 largest possible value for a sequence number. For a 16 bit sequence 2843 number (as are those defined in this specification) MAXVALUE is 2844 65536. 2846 The sequence number S1 is said to be "greater than" the sequence 2847 number S2 if: 2849 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 2851 o S2 > S1 AND S2 - S1 > MAXVALUE/2 2853 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 2854 cannot be determined. In this case, which should not occur, either 2855 ordering may be assumed. 2857 Thus when comparing two messages, it is possible - even in the 2858 presence of wrap-around - to determine which message contains the 2859 most recent information. 2861 18. Extensions 2863 An extension to this protocol will need to interact with this 2864 specification, and possibly also with [NHDP]. This protocol is 2865 designed to permit such interactions, in particular: 2867 o Through accessing, and possibly extending, the information in the 2868 Information Bases. All updates to the elements specified in this 2869 document are subject to the constraints specified in [NHDP] and 2870 Appendix D. 2872 o Through accessing an outgoing message prior to it being 2873 transmitted over any OLSRv2 interface, and to add information to 2874 it as specified in [RFC5444]. This MAY include Message TLVs 2875 and/or addresses with associated Address Block TLVs. (Addresses 2876 without new associated TLVs SHOULD NOT be added to messages.) 2877 This may, for example, be to allow a security protocol, as 2878 suggested in Section 19, to add a TLV containing a cryptographic 2879 signature to the message. 2881 o Through accessing an incoming message, and potentially discarding 2882 it prior to processing by this protocol. This may, for example, 2883 allow a security protocol as suggested in Section 19 to perform 2884 verification of message signatures and prevent processing and/or 2885 forwarding of unverifiable messages by this protocol. 2887 o Through accessing an incoming message after it has been completely 2888 processed by this protocol. This may, in particular, allow a 2889 protocol which has added information, by way of inclusion of 2890 appropriate TLVs, or of addresses associated with new TLVs, access 2891 to such information after appropriate updates have been recorded 2892 in the Information Bases in this protocol. 2894 o Through requesting that a message be generated at a specific time. 2895 In that case, message generation MUST still respect the 2896 constraints in [NHDP] and Section 5.4. 2898 19. Security Considerations 2900 Currently, this protocol does not specify any special security 2901 measures. As a proactive routing protocol, this protocol is a 2902 potential target for various attacks. Various possible 2903 vulnerabilities are discussed in this section. 2905 19.1. Confidentiality 2907 This protocol periodically MPR floods topological information to all 2908 routers in the network. Hence, if used in an unprotected wireless 2909 network, the network topology is revealed to anyone who listens to 2910 the control messages. 2912 In situations where the confidentiality of the network topology is of 2913 importance, regular cryptographic techniques, such as exchange of 2914 OLSRv2 control traffic messages encrypted by PGP [RFC4880] or 2915 encrypted by some shared secret key, can be applied to ensure that 2916 control traffic can be read and interpreted by only those authorized 2917 to do so. 2919 19.2. Integrity 2921 Each router is injecting topological information into the network 2922 through transmitting HELLO messages and, for some routers, TC 2923 messages. If some routers for some reason, malicious or malfunction, 2924 inject invalid control traffic, network integrity may be compromised. 2925 Therefore, message authentication is recommended. 2927 Different such situations may occur, for instance: 2929 1. a router generates TC messages, advertising links to non-neighbor 2930 routers; 2932 2. a router generates TC messages, pretending to be another router; 2934 3. a router generates HELLO messages, advertising non-neighbor 2935 routers; 2937 4. a router generates HELLO messages, pretending to be another 2938 router; 2940 5. a router forwards altered control messages; 2942 6. a router does not forward control messages; 2944 7. a router does not select multipoint relays correctly; 2945 8. a router forwards broadcast control messages unaltered, but does 2946 not forward unicast data traffic; 2948 9. a router "replays" previously recorded control traffic from 2949 another router. 2951 Authentication of the originator router for control messages (for 2952 situations 2, 4 and 5) and on the individual links announced in the 2953 control messages (for situations 1 and 3) may be used as a 2954 countermeasure. However to prevent routers from repeating old (and 2955 correctly authenticated) information (situation 9) temporal 2956 information is required, allowing a router to positively identify 2957 such delayed messages. 2959 In general, digital signatures and other required security 2960 information may be transmitted as a separate Message Type, or 2961 signatures and security information may be transmitted within the 2962 HELLO and TC messages, using the TLV mechanism. Either option 2963 permits that "secured" and "unsecured" routers can coexist in the 2964 same network, if desired, 2966 Specifically, the authenticity of entire control packets can be 2967 established through employing IPsec authentication headers, whereas 2968 authenticity of individual links (situations 1 and 3) require 2969 additional security information to be distributed. 2971 An important consideration is that all control messages are 2972 transmitted either to all routers in the neighborhood (HELLO 2973 messages) or broadcast to all routers in the network (TC messages). 2975 For example, a control message in this protocol is always a point-to- 2976 multipoint transmission. It is therefore important that the 2977 authentication mechanism employed permits that any receiving router 2978 can validate the authenticity of a message. As an analogy, given a 2979 block of text, signed by a PGP private key, then anyone with the 2980 corresponding public key can verify the authenticity of the text. 2982 19.3. Interaction with External Routing Domains 2984 This protocol does, through the use of TC messages, provide a basic 2985 mechanism for injecting external routing information to this 2986 protocol's domain. Routing information can be extracted from the 2987 protocol's Information Bases, in particular the Routing Set, of this 2988 protocol and, potentially, injected into an external domain, if the 2989 routing protocol governing that domain permits this. 2991 When operating routers connecting a MANET using this protocol to an 2992 external routing domain, care MUST be taken not to allow potentially 2993 insecure and untrustworthy information to be injected from this 2994 domain to external routing domains. Care MUST also be taken to 2995 validate the correctness of information prior to it being injected as 2996 to avoid polluting routing tables with invalid information. 2998 A recommended way of extending connectivity from an existing routing 2999 domain to a MANET routed using this protocol is to assign an IP 3000 prefix (under the authority of the routers/gateways connecting the 3001 MANET with the exiting routing domain) exclusively to that MANET 3002 area, and to statically configure the gateways to advertise routes 3003 for that IP sequence to routers in the existing routing domain. 3005 20. IANA Considerations 3007 This specification defines one Message Type, which must be allocated 3008 from the "Message Types" repository of [RFC5444], two Message TLV 3009 Types, which must be allocated from the "Message TLV Types" 3010 repository of [RFC5444], and three Address Block TLV Types, which 3011 must be allocated from the "Address Block TLV Types" repository of 3012 [RFC5444]. 3014 20.1. Expert Review: Evaluation Guidelines 3016 For the registries where an Expert Review is required, the designated 3017 expert SHOULD take the same general recommendations into 3018 consideration as are specified by [RFC5444]. 3020 20.2. Message Types 3022 This specification defines one Message Type, to be allocated from the 3023 0-223 range of the "Message Types" namespace defined in [RFC5444], as 3024 specified in Table 6. 3026 +------+------+-----------------------------------------+ 3027 | Name | Type | Description | 3028 +------+------+-----------------------------------------+ 3029 | TC | TBD1 | Topology Control (MANET-wide signaling) | 3030 +------+------+-----------------------------------------+ 3032 Table 6: Message Type assignment 3034 20.3. Message-Type-specific TLV Type Registries 3036 IANA is requested to create a registry for Message-Type-specific 3037 Message TLVs for TC messages, in accordance with Section 6.2.1 of 3038 [RFC5444], and with initial assignments and allocation policies as 3039 specified in Table 7. 3041 +---------+-------------+-------------------+ 3042 | Type | Description | Allocation Policy | 3043 +---------+-------------+-------------------+ 3044 | 128-223 | Unassigned | Expert Review | 3045 +---------+-------------+-------------------+ 3047 Table 7: TC Message-Type-specific Message TLV Types 3049 IANA is requested to create a registry for Message-Type-specific 3050 Address Block TLVs for TC messages, in accordance with Section 6.2.1 3051 of [RFC5444], and with initial assignments and allocation policies as 3052 specified in Table 8. 3054 +---------+-------------+-------------------+ 3055 | Type | Description | Allocation Policy | 3056 +---------+-------------+-------------------+ 3057 | 128-223 | Unassigned | Expert Review | 3058 +---------+-------------+-------------------+ 3060 Table 8: TC Message-Type-specific Address Block TLV Types 3062 20.4. Message TLV Types 3064 This specification defines two Message TLV Types, which must be 3065 allocated from the "Message TLV Types" namespace defined in 3066 [RFC5444]. IANA are requested to make allocations in the 8-127 range 3067 for these types. This will create two new Type Extension registries 3068 with assignments as specified in Table 9 and Table 10. 3069 Specifications of these TLVs are in Section 8.1.1 and Section 8.2.1, 3070 respectively. Each of these TLVs MUST NOT be included more than once 3071 in a Message TLV Block. 3073 +-------------+------+-----------+----------------------------------+ 3074 | Name | Type | Type | Description | 3075 | | | Extension | | 3076 +-------------+------+-----------+----------------------------------+ 3077 | MPR_WILLING | TBD2 | 0 | Specifies the originating | 3078 | | | | router's willingness to act as a | 3079 | | | | relay and to partake in network | 3080 | | | | formation | 3081 | Unassigned | TBD2 | 1-255 | Expert Review | 3082 +-------------+------+-----------+----------------------------------+ 3084 Table 9: Message TLV Type assignment: MPR_WILLING 3086 +--------------+------+----------------+----------------------------+ 3087 | Name | Type | Type Extension | Description | 3088 +--------------+------+----------------+----------------------------+ 3089 | CONT_SEQ_NUM | TBD3 | 0 (COMPLETE) | Specifies a content | 3090 | | | | sequence number for this | 3091 | | | | complete message | 3092 | CONT_SEQ_NUM | TBD3 | 1 (INCOMPLETE) | Specifies a content | 3093 | | | | sequence number for this | 3094 | | | | incomplete message | 3095 | Unassigned | TBD3 | 2-255 | Expert Review | 3096 +--------------+------+----------------+----------------------------+ 3098 Table 10: Message TLV Type assignment: CONT_SEQ_NUM 3100 Type extensions indicated as Expert Review SHOULD be allocated as 3101 described in [RFC5444], based on Expert Review as defined in 3102 [RFC5226]. 3104 20.5. Address Block TLV Types 3106 This specification defines three Address Block TLV Types, which must 3107 be allocated from the "Address Block TLV Types" namespace defined in 3108 [RFC5444]. IANA are requested to make allocations in the 8-127 range 3109 for these types. This will create three new Type Extension 3110 registries with assignments as specified in Table 11, Table 12 and 3111 Table 13, respectively. Specifications of these TLVs are in 3112 Section 8.1.2 and Section 8.2.2. 3114 +------------+------+-----------+-----------------------------------+ 3115 | Name | Type | Type | Description | 3116 | | | Extension | | 3117 +------------+------+-----------+-----------------------------------+ 3118 | MPR | TBD4 | 0 | Specifies that a given address is | 3119 | | | | of a router selected as an MPR | 3120 | Unassigned | TBD4 | 1-255 | Expert Review | 3121 +------------+------+-----------+-----------------------------------+ 3123 Table 11: Address Block TLV Type assignment: MPR 3125 +---------------+------+-----------+--------------------------------+ 3126 | Name | Type | Type | Description | 3127 | | | Extension | | 3128 +---------------+------+-----------+--------------------------------+ 3129 | NBR_ADDR_TYPE | TBD5 | 0 | Specifies that a given address | 3130 | | | | is of a neighbor reached via | 3131 | | | | the originating router | 3132 | Unassigned | TBD5 | 1-255 | Expert Review | 3133 +---------------+------+-----------+--------------------------------+ 3135 Table 12: Address Block TLV Type assignment: NBR_ADDR_TYPE 3137 The Values which the NBR_ADDR_TYPE Address Block TLV can use are the 3138 following: 3140 o ORIGINATOR := 1; 3142 o ROUTABLE := 2; 3144 o ROUTABLE_ORIG := 3. 3146 +------------+------+-----------+-----------------------------------+ 3147 | Name | Type | Type | Description | 3148 | | | extension | | 3149 +------------+------+-----------+-----------------------------------+ 3150 | GATEWAY | TBD6 | 0 | Specifies that a given address is | 3151 | | | | reached via a gateway on the | 3152 | | | | originating router | 3153 | Unassigned | TBD6 | 1-255 | Expert Review | 3154 +------------+------+-----------+-----------------------------------+ 3156 Table 13: Address Block TLV Type assignment: GATEWAY 3158 Type extensions indicated as Expert Review SHOULD be allocated as 3159 described in [RFC5444], based on Expert Review as defined in 3160 [RFC5226]. 3162 21. Contributors 3164 This specification is the result of the joint efforts of the 3165 following contributors -- listed alphabetically. 3167 o Cedric Adjih, INRIA, France, 3169 o Emmanuel Baccelli, INRIA , France, 3171 o Thomas Heide Clausen, LIX, France, 3172 o Justin Dean, NRL, USA, 3174 o Christopher Dearlove, BAE Systems, UK, 3175 3177 o Satoh Hiroki, Hitachi SDL, Japan, 3179 o Philippe Jacquet, INRIA, France, 3181 o Monden Kazuya, Hitachi SDL, Japan, 3183 o Kenichi Mase, Niigata University, Japan, 3185 o Ryuji Wakikawa, Toyota, Japan, 3187 22. Acknowledgments 3189 The authors would like to acknowledge the team behind OLSRv1, 3190 specified in RFC3626, including Anis Laouiti (INT, Paris), Pascale 3191 Minet (INRIA, France), Laurent Viennot (INRIA, France), and Amir 3192 Qayyum (M.A. Jinnah University, Islamabad) for their contributions. 3194 The authors would like to gratefully acknowledge the following people 3195 for intense technical discussions, early reviews and comments on the 3196 specification and its components (listed alphabetically): Khaldoun Al 3197 Agha (LRI), Teco Boot (Infinity Networks), Song-Yean Cho (LIX), Alan 3198 Cullen (BAE Systems), Louise Lamont (CRC), Li Li (CRC), Joe Macker 3199 (NRL), Richard Ogier (SRI), Charles E. Perkins (WiChorus), Henning 3200 Rogge (FGAN), and the entire IETF MANET working group. 3202 23. References 3204 23.1. Normative References 3206 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3207 Requirement Levels", RFC 2119, BCP 14, March 1997. 3209 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 3210 considerations in MANETs", RFC 5148, February 2008. 3212 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 3213 IANA Considerations Section in RFCs", RFC 5226, BCP 26, 3214 May 2008. 3216 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 3217 "Generalized MANET Packet/Message Format", RFC 5444, 3218 February 2009. 3220 [RFC5497] Clausen, T. and C. Dearlove, "Representing multi-value 3221 time in MANETs", RFC 5497, March 2009. 3223 [RFC5498] Chakeres, I., "IANA Allocations for MANET Protocols", 3224 RFC 5498, March 2009. 3226 [NHDP] Clausen, T., Dean, J., and C. Dearlove, "MANET 3227 Neighborhood Discovery Protocol (NHDP)", work in 3228 progress draft-ietf-manet-nhdp-10.txt, July 2009. 3230 23.2. Informative References 3232 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 3233 (MANET): Routing Protocol Performance Issues and 3234 Evaluation Considerations", RFC 2501, January 1999. 3236 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 3237 Routing Protocol", RFC 3626, October 2003. 3239 [RFC4880] Callas, J., Donnerhacke, L., Finney, H., and R. Thayer, 3240 "OpenPGP message format", RFC 4880, November 2007. 3242 [HIPERLAN] ETSI, "ETSI STC-RES10 Committee. Radio equipment and 3243 systems: HIPERLAN type 1, functional specifications ETS 3244 300-652", June 1996. 3246 [HIPERLAN2] Jacquet, P., Minet, P., Muhlethaler, P., and N. 3247 Rivierre, "Increasing reliability in cable free radio 3248 LANs: Low level forwarding in HIPERLAN.", 1996. 3250 [MPR] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint 3251 relaying: An efficient technique for flooding in mobile 3252 wireless networks.", 2001. 3254 [FSR] Pei, G., Gerla, M., and T. Chen, "Fisheye state routing 3255 in mobile ad hoc networks", 2000. 3257 [FSLS] Santivanez, C., Ramanathan, R., and I. Stavrakakis, 3258 "Making link-state routing scale for ad hoc networks", 3259 2000. 3261 Appendix A. Example Algorithm for Calculating MPRs 3263 The following specifies an algorithm which MAY be used to select 3264 MPRs. MPRs are calculated per OLSRv2 interface, but then a single 3265 set of MPRs is formed from the union of the MPRs for all OLSRv2 3266 interfaces. (As noted in Section 14 a router MAY improve on this, by 3267 coordination between OLSRv2 interfaces.) A router's MPRs are 3268 recorded using the element N_mpr in Neighbor Tuples. 3270 If using this example algorithm then the following steps MUST be 3271 executed in order for a router to select its MPRs: 3273 1. Set N_mpr := false in all Neighbor Tuples; 3275 2. For each Neighbor Tuple with N_symmetric = true and N_willingness 3276 = WILL_ALWAYS, set N_mpr := true; 3278 3. For each OLSRv2 interface of the router, use the algorithm in 3279 Appendix A.2. Note that this sets N_mpr := true for some 3280 Neighbor Tuples, these routers are already selected as MPRs when 3281 using the algorithm for following OLSRv2 interfaces. 3283 4. OPTIONALLY, consider each selected MPR in turn, and if the set of 3284 selected MPRs without that router still satisfies the necessary 3285 conditions, for all OLSRv2 interfaces, then that router MAY be 3286 removed from the set of MPRs. This process MAY be repeated until 3287 no MPRs are removed. Routers MAY be considered in order of 3288 increasing N_willingness. 3290 Note that only symmetric strict 2-hop neighbors are considered, thus: 3292 o Symmetric 1-hop neighbor routers with N_willingness = WILL_NEVER 3293 MUST NOT be selected as MPRs, and MUST be ignored in the following 3294 algorithm (and hence also ignore any 2-Hop Tuples whose 3295 N2_neighbor_iface_addr_list is included in the 3296 N_neighbor_addr_list of any such Neighbor Tuple). 3298 o Symmetric 2-hop neighbor routers which are also symmetric 1-hop 3299 neighbor routers MUST be ignored in the following algorithm (i.e. 3300 ignore any 2-Hop Tuples whose N2_2hop_addr is in the 3301 N_neighbor_addr_list of any Neighbor Tuple). 3303 A.1. Terminology 3305 The following terminology will be used when selecting MPRs for the 3306 OLSRv2 interface I: 3308 N(I) - The set of symmetric 1-hop neighbors which have a symmetric 3309 link to I. 3311 N2(I) - The set of addresses of interfaces of a router with a 3312 symmetric link to a router in N(I); this MAY be restricted to 3313 considering only information received over I (in which case N2(I) 3314 is the set of N2_2hop_addr in 2-Hop Tuples in the 2-Hop Set for 3315 OLSRv2 interface I). 3317 Connected to I via Y - An address A in N2(I) is connected to I via a 3318 router Y in N(I) if A is an address of an interface of a symmetric 3319 1-hop neighbor of Y (i.e. A is the N2_2hop_addr in a 2-Hop Tuple 3320 in the 2-Hop Set for OLSRv2 interface I, and whose 3321 N2_neighbor_iface_addr_list is contained in the set of interface 3322 addresses of Y). 3324 D(Y, I) - For a router Y in N(I), the number of addresses in N2(I) 3325 which are connected to I via Y. 3327 R(Y, I): - For a router Y in N(I), the number of addresses in N2(I) 3328 which are connected to I via Y, but are not connected to I via any 3329 router which has already been selected as an MPR. 3331 A.2. MPR Selection Algorithm for each OLSRv2 Interface 3333 When selecting MPRs for the OLSRv2 interface I: 3335 1. For each address A in N2(I) for which there is only one router Y 3336 in N(I) such that A is connected to I via Y, select that router Y 3337 as an MPR (i.e. set N_mpr := true in the Neighbor Tuple 3338 corresponding to Y). 3340 2. While there exists any router Y in N(I) with R(Y, I) > 0: 3342 1. Select a router Y in N(I) with R(Y, I) > 0 in the following 3343 order of priority: 3345 + greatest N_willingness in the Neighbor Tuple corresponding 3346 to Y, THEN; 3348 + greatest R(Y, I), THEN; 3350 + greatest D(Y, I), THEN; 3352 + N_mpr_selector is equal to true, if possible, THEN; 3354 + any choice. 3356 2. Select Y as an MPR (i.e. set N_mpr := true in the Neighbor 3357 Tuple corresponding to Y). 3359 Appendix B. Example Algorithm for Calculating the Routing Set 3361 The following procedure is given as an example for calculating the 3362 Routing Set using a variation of Dijkstra's algorithm. First all 3363 Routing Tuples are removed, and then, using the selections and 3364 definitions in Appendix B.1, the procedures in the following sections 3365 (each considered a "stage" of the processing) are applied in turn. 3367 B.1. Local Interfaces and Neighbors 3369 The following selections and definitions are made: 3371 1. For each Local Interface Tuple, select an address from its 3372 I_local_iface_addr_list, this is defined as the selected address 3373 for this Local Interface Tuple. 3375 2. For each Link Tuple, the selected address of its corresponding 3376 Local Interface Tuple is defined as the selected local address 3377 for this Local Interface Tuple. 3379 3. For each Neighbor Tuple with N_symmetric = true, the selected 3380 local address is defined as the selected local address of the 3381 selected Link Tuple for that Neighbor Tuple. 3383 4. For each address (N_orig_addr or in N_neighbor_addr_list, the 3384 "neighbor address") from a Neighbor Tuple with N_symmetric = 3385 true, select a Link Tuple with L_status = SYMMETRIC whose 3386 corresponding Neighbor Tuple is this Neighbor Tuple and where, if 3387 possible, L_neighbor_iface_addr_list contains the neighbor 3388 address. This is defined as the selected Link Tuple for that 3389 neighbor address. 3391 5. For each address (N_orig_addr or in N_neighbor_addr_list, the 3392 "neighbor address") from a Neighbor Tuple with N_symmetric = 3393 true, a selected address from the L_neighbor_iface_addr_list of 3394 the selected Link Tuple for the neighbor address, if possible 3395 equal to the neighbor address, is defined as the selected link 3396 address for that neighbor address. 3398 6. Routing Tuple preference is decided by preference for 3399 corresponding Neighbor Tuples in this order: 3401 * For greater N_willingness. 3403 * For N_mpr_selector = true over N_mpr_selector = false. 3405 B.2. Add Neighbor Routers 3407 The following procedure is executed once. 3409 1. For each Neighbor Tuple with N_symmetric = true, add a Routing 3410 Tuple with: 3412 * R_dest_addr := N_orig_addr; 3414 * R_next_iface_addr := selected link address; 3416 * R_local_iface_addr := selected local address; 3418 * R_dist := 1. 3420 B.3. Add Remote Routers 3422 The following procedure is executed for each value of h, starting 3423 with h := 1 and incrementing by 1 for each iteration. The execution 3424 MUST stop if no new Routing Tuples are added in an iteration. 3426 1. For each Router Topology Tuple, if: 3428 * TR_to_orig_addr is not equal to the R_dest_addr of any Routing 3429 Tuple added in an earlier stage, AND; 3431 * TR_from_orig_addr is equal to the R_dest_addr of a Routing 3432 Tuple with R_dist = h (the "previous Routing Tuple"), 3434 then add a new Routing Tuple, with: 3436 * R_dest_addr := TR_to_orig_addr; 3438 * R_next_iface_addr := R_next_iface_addr of the previous Routing 3439 Tuple; 3441 * R_local_iface_addr := R_local_iface_addr of the previous 3442 Routing Tuple; 3444 * R_dist := h+1. 3446 There may be more than one possible Routing Tuple that may be 3447 added for an R_dest_addr in this stage. If so, then, for each 3448 such R_dest_addr, a Routing Tuple which is preferred SHOULD be 3449 added. 3451 B.4. Add Neighbor Addresses 3453 The following procedure is executed once. 3455 1. For each Neighbor Tuple with N_symmetric = true: 3457 1. For each address (the "current address") in 3458 N_neighbor_addr_list, if the current address is not equal to 3459 the R_dest_addr of any Routing Tuple, then add a new Routing 3460 Tuple, with: 3462 + R_dest_addr := current address; 3464 + R_next_iface_addr := selected link address; 3466 + R_local_iface_addr := selected local address; 3468 + R_dist := 1. 3470 B.5. Add Remote Routable Addresses 3472 The following procedure is executed once. 3474 1. For each Routable Address Topology Tuple, if: 3476 * TA_dest_addr is not equal to the R_dest_addr of any Routing 3477 Tuple added in an earlier stage, AND; 3479 * TR_from_orig_addr is equal to the R_dest_addr of a Routing 3480 Tuple (the "previous Routing Tuple"), 3482 then add a new Routing Tuple, with: 3484 * R_dest_addr := TA_dest_addr; 3486 * R_next_iface_addr := R_next_iface_addr of the previous Routing 3487 Tuple; 3489 * R_local_iface_addr := R_local_iface_addr of the previous 3490 Routing Tuple; 3492 * R_dist := R_dist of the previous Routing Tuple + 1. 3494 There may be more than one possible Routing Tuple that may be 3495 added for an R_dest_addr in this stage. If so, then, for each 3496 such R_dest_addr, a Routing Tuple which is preferred SHOULD be 3497 added. 3499 B.6. Add Attached Networks 3501 The following procedure is executed once. 3503 1. For each Attached Network Tuple, if: 3505 * AN_orig_addr is not equal to the R_dest_addr of any Routing 3506 Tuple added in an earlier stage, AND; 3508 * AN_orig_addr is equal to the R_dest_addr of a Routing Tuple 3509 (the "previous Routing Tuple), 3511 then add a new Routing Tuple, with: 3513 * R_dest_addr := AN_net_addr; 3515 * R_next_iface_addr := R_next_iface_addr of the previous Routing 3516 Tuple; 3518 * R_local_iface_addr := R_local_iface_addr of the previous 3519 Routing Tuple; 3521 * R_dist := R_dist of the previous Routing Tuple + AN_dist. 3523 There may be more than one possible Routing Tuple that may be 3524 added for an R_dest_addr in this stage. If so, then, for each 3525 such R_dest_addr, a Routing Tuple with minimum R_dist MUST be 3526 selected, otherwise a Routing Tuple which is preferred SHOULD be 3527 added. 3529 B.7. Add 2-Hop Neighbors 3531 The following procedure is executed once. 3533 1. For each 2-Hop Tuple, if: 3535 * N2_2hop_addr is a routable address, AND; 3537 * N2_2hop_addr is not equal to the R_dest_addr of any Routing 3538 Tuple added in an earlier stage, 3540 then define the "previous Routing Tuple" as that with R_dest_addr 3541 = N_orig_addr of the corresponding Neighbor Tuple, and add a new 3542 Routing Tuple, with: 3544 * R_dest_addr := N2_2hop_addr; 3546 * R_next_iface_addr := R_next_iface_addr of the previous Routing 3547 Tuple; 3549 * R_local_iface_addr := R_local_iface_addr of the previous 3550 Routing Tuple; 3552 * R_dist := 2. 3554 There may be more than one possible Routing Tuple that may be 3555 added for an R_dest_addr in this stage. If so, then, for each 3556 such R_dest_addr, a Routing Tuple which is preferred SHOULD be 3557 added. 3559 Appendix C. Example Message Layout 3561 An example TC message is as follows. The message has full Message 3562 Header (four bit Flags field value is 15). Its four bit Message 3563 Address Length field has value 3 and hence addresses in the message 3564 have length four octets, here being IPv4 addresses. The overall 3565 message length is 57 octets. 3567 The message has a Message TLV Block with content length 13 octets 3568 containing three TLVs. The first two TLVs are interval and validity 3569 times for the message. The third TLV is the content sequence number 3570 TLV used to carry the 2 octet ANSN, and (with default type extension 3571 zero, i.e. COMPLETE) indicating that the TC message is complete. 3572 Each TLV uses a TLV with Flags octet value 16, indicating that it has 3573 a Value, but no type extension or start and stop indexes. The first 3574 two TLVs have a Value Length of 1 octet, the last has a Value Length 3575 of 2 octets. 3577 The message has two Address Blocks. (This is not necessary, the 3578 information could be conveyed using a single Address Block, the use 3579 of two Address Blocks, which is also allowed, is illustrative only.) 3580 The first Address Block contains 3 addresses, with Flags octet value 3581 128, hence with a Head section, (with length 2 octets) but no Tail 3582 section, and hence Mid sections with length two octets. The 3583 following TLV Block (content length 6 octets) contains a single 3584 NBR_ADDR_TYPE TLV (Flags octet value 16, includes a Value but no 3585 indexes) indicating that these addresses are associated with the 3586 Value (with Value Length 1 octet) ROUTABLE_ORIG, i.e. they are 3587 originator addresses of advertised neighbors that are also routable 3588 addresses. 3590 The second Address Block contains 1 address, with Flags octet 176 3591 indicating that there is a Head section (with length 2 octets), that 3592 the Tail section (length 2 octets) consists of zero valued octets 3593 (not included), and that there is a single prefix length, which is 3594 16. The network address is thus Head.0.0/16. The following TLV 3595 Block (content length 8 octets) includes one TLV that indicates that 3596 the originating router is a gateway to this network, at a given 3597 number of hops distance (Value Length 1 octet). The TLV Flags octet 3598 value of 16 again indicates that a Value, but no indexes are needed. 3600 0 1 2 3 3601 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 3602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3603 | TC |1 1 1 1 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1| 3604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3605 | Originator Address | 3606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3607 | Hop Limit | Hop Count | Message Sequence Number | 3608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3609 |0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1| INTERVAL_TIME |0 0 0 1 0 0 0 0| 3610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3611 |0 0 0 0 0 0 0 1| Value | VALIDITY_TIME |0 0 0 1 0 0 0 0| 3612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3613 |0 0 0 0 0 0 0 1| Value | CONT_SEQ_NUM |0 0 0 1 0 0 0 0| 3614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3615 |0 0 0 0 0 0 1 0| Value (ANSN) |0 0 0 0 0 0 1 1| 3616 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3617 |1 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0| Head | 3618 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3619 | Mid | Mid | 3620 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3621 | Mid |0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0| 3622 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3623 | NBR_ADDR_TYPE |0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 1| ROUTABLE_ORIG | 3624 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3625 |0 0 0 0 0 0 0 1|1 0 1 1 0 0 0 0|0 0 0 0 0 0 1 0| Head | 3626 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3627 | Head (cont) |0 0 0 0 0 0 1 0|0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 0| 3628 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3629 |0 0 0 0 0 1 0 0| GATEWAY |0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 1| 3630 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3631 | Number Hops | 3632 +-+-+-+-+-+-+-+-+ 3634 Appendix D. Constraints 3636 Any process which updates the Local Information Base, the 3637 Neighborhood Information Base or the Topology Information Base MUST 3638 ensure that all constraints specified in this appendix are 3639 maintained, as well as those specified in [NHDP]. 3641 In each Originator Tuple: 3643 o O_orig_addr MUST NOT equal any other O_orig_addr. 3645 o O_orig_addr MUST NOT equal this router's originator address. 3647 In each Local Attached Network Tuple: 3649 o AL_net_addr MUST NOT equal any other AL_net_addr. 3651 o AL_net_addr MUST NOT be in the I_local_iface_addr_list of any 3652 Local Interface Tuple or equal the IR_local_iface_addr of any 3653 Removed Interface Address Tuple. 3655 o AL_net_addr MUST not equal this router's originator address, or 3656 equal the O_orig_addr in any Originator Tuple. 3658 o AL_dist MUST NOT be less than zero. 3660 In each Link Tuple: 3662 o L_neighbor_iface_addr_list MUST NOT contain the AL_net_addr of any 3663 Local Attached Network Tuple. 3665 In each Neighbor Tuple: 3667 o N_orig_addr MUST NOT be changed to unknown. 3669 o N_orig_addr MUST NOT equal this router's originator address, or 3670 equal O_orig_addr in any Originator Tuple. 3672 o N_orig_addr MUST NOT equal the AL_net_addr in any Local Attached 3673 Network Tuple. 3675 o N_neighbor_addr_list MUST NOT contain this router's originator 3676 address, the O_orig_addr in any Originator Tuple, or the 3677 AL_net_addr in any Local Attached Network Tuple. 3679 o If N_orig_addr = unknown, then N_willingness = WILL_NEVER, N_mpr = 3680 false, N_mpr_selector = false, and N_advertised = false. 3682 o If N_willingness MUST be in the range from WILL_NEVER to 3683 WILL_ALWAYS, inclusive. 3685 o If N_mpr = true, then N_symmetric MUST be true and N_willingness 3686 MUST NOT equal WILL_NEVER. 3688 o If N_symmetric = true and N_mpr = false, then N_willingness MUST 3689 NOT equal WILL_ALWAYS. 3691 o If N_mpr_selector = true, then N_symmetric MUST be true and 3692 N_advertised MUST be true. 3694 o If N_advertised = true, then N_symmetric MUST be true. 3696 In each Lost Neighbor Tuple: 3698 o NL_neighbor_addr MUST NOT equal this router's originator address, 3699 equal the O_orig_addr in any Originator Tuple, or equal the 3700 AL_net_addr in any Local Attached Network Tuple. 3702 In each 2-Hop Tuple: 3704 o N2_2hop_addr MUST NOT equal this router's originator address, 3705 equal the O_orig_addr in any Originator Tuple, or equal the 3706 AL_net_addr in any Local Attached Network Tuple. 3708 In each Advertising Remote Router Tuple: 3710 o AR_orig_addr MUST NOT be in the I_local_iface_addr_list in any 3711 Local Interface Tuple or equal the IR_local_iface_addr in any 3712 Removed Interface Address Tuple. 3714 o AR_orig_addr MUST NOT equal this router's originator address or 3715 equal the O_orig_addr in any Originator Tuple. 3717 o AR_orig_addr MUST NOT equal the AL_net_addr in any Local Attached 3718 Network Tuple. 3720 o AR_orig_addr MUST NOT equal the AR_orig_addr in any other 3721 Advertising Remote Router Tuple. 3723 In each Router Topology Tuple: 3725 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 3726 = TR_from_orig_addr. 3728 o TR_to_orig_addr MUST NOT be in the I_local_iface_addr_list in any 3729 Local Interface Tuple or equal the IR_local_iface_addr in any 3730 Removed Interface Address Tuple. 3732 o TR_to_orig_addr MUST NOT equal this router's originator address or 3733 equal the O_orig_addr in any Originator Tuple. 3735 o TR_to_orig_addr MUST NOT equal the AL_net_addr in any Local 3736 Attached Network Tuple. 3738 o The ordered pair (TR_from_orig_addr, TR_to_orig_addr) MUST NOT 3739 equal the corresponding pair for any other Router Topology Tuple. 3741 o TR_seq_number MUST NOT be greater than AR_seq_number in the 3742 Advertising Remote Router Tuple with AR_orig_addr = 3743 TR_from_orig_addr. 3745 In each Routable Address Topology Tuple: 3747 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 3748 = TA_from_orig_addr. 3750 o TA_dest_addr MUST be routable. 3752 o TA_dest_addr MUST NOT be in the I_local_iface_addr_list in any 3753 Local Interface Tuple or equal the IR_local_iface_addr in any 3754 Removed Interface Address Tuple. 3756 o TA_dest_addr MUST NOT equal this router's originator address or 3757 equal the O_orig_addr in any Originator Tuple. 3759 o TA_dest_addr MUST NOT equal the AL_net_addr in any Local Attached 3760 Network Tuple. 3762 o The ordered pair (TA_from_orig_addr, TA_dest_addr) MUST NOT equal 3763 the corresponding pair for any other Attached Network Tuple. 3765 o TA_seq_number MUST NOT be greater than AR_seq_number in the 3766 Advertising Remote Router Tuple with AR_orig_addr = 3767 TA_from_orig_addr. 3769 In each Attached Network Tuple: 3771 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 3772 = AN_orig_addr. 3774 o AN_net_addr MUST NOT be in the I_local_iface_addr_list in any 3775 Local Interface Tuple or equal the IR_local_iface_addr in any 3776 Removed Interface Address Tuple. 3778 o AN_net_addr MUST NOT equal this router's originator address or 3779 equal the O_orig_addr in any Originator Tuple. 3781 o AN_net_addr MUST NOT equal the AL_net_addr in any Local Attached 3782 Network Tuple. 3784 o The ordered pair (AN_orig_addr, AN_net_addr) MUST NOT equal the 3785 corresponding pair for any other Attached Network Tuple. 3787 o AN_seq_number MUST NOT be greater than AR_seq_number in the 3788 Advertising Remote Router Tuple with AR_orig_addr = AN_orig_addr. 3790 o AN_dist MUST NOT be less than zero. 3792 In each Received Tuple: 3794 o RX_orig_addr MUST NOT equal this router's originator address or 3795 the O_orig_addr in any Originator Tuple. 3797 o Each ordered triple (RX_type, RX_orig_addr, RX_seq_number) MUST 3798 NOT equal the corresponding triple for any other Received Tuple in 3799 the same Received Set. 3801 In each Processed Tuple: 3803 o P_orig_addr MUST NOT equal this router's originator address or 3804 equal the O_orig_addr in any Originator Tuple. 3806 o Each ordered triple (P_type, P_orig_addr, P_seq_number) MUST NOT 3807 equal the corresponding triple for any other Processed Tuple. 3809 In each Forwarded Tuple: 3811 o F_orig_addr MUST NOT equal this router's originator address or 3812 equal the O_orig_addr in any Originator Tuple. 3814 o Each ordered triple (F_type, F_orig_addr, F_seq_number) MUST NOT 3815 equal the corresponding triple for any other Forwarded Tuple. 3817 Appendix E. Flow and Congestion Control 3819 Due to its proactive nature, this protocol has a natural control over 3820 the flow of its control traffic. Routers transmit control messages 3821 at predetermined rates specified and bounded by message intervals. 3823 This protocol employs [NHDP] for local signaling, embedding MPR 3824 selection advertisement through a simple Address Block TLV, and 3825 router willingness advertisement (if any) as a single Message TLV. 3826 Local signaling, therefore, shares the characteristics and 3827 constraints of [NHDP]. 3829 Furthermore, the use of MPRs can greatly reduce the signaling 3830 overhead from link state information dissemination in two ways, 3831 attaining both flooding reduction and topology reduction. First, 3832 using MPR flooding, the cost of distributing link state information 3833 throughout the network is reduced, as compared to when using classic 3834 flooding, since only MPRs need to forward link state declaration 3835 messages. Second, the amount of link state information for a router 3836 to declare is reduced to need only contain that router's MPR 3837 selectors. This reduces the size of a link state declaration as 3838 compared to declaring full link state information. In particular 3839 some routers may not need to declare any such information. In dense 3840 networks, the reduction of control traffic can be of several orders 3841 of magnitude compared to routing protocols using classical flooding 3843 [MPR]. This feature naturally provides more bandwidth for useful 3844 data traffic and pushes further the frontier of congestion. 3846 Since the control traffic is continuous and periodic, it keeps the 3847 quality of the links used in routing more stable. However, using 3848 some options, some control messages (HELLO messages or TC messages) 3849 may be intentionally sent in advance of their deadline in order to 3850 increase the responsiveness of the protocol to topology changes. 3851 This may cause a small, temporary, and local increase of control 3852 traffic, however this is at all times bounded by the use of minimum 3853 message intervals. 3855 Authors' Addresses 3857 Thomas Heide Clausen 3858 LIX, Ecole Polytechnique 3860 Phone: +33 6 6058 9349 3861 EMail: T.Clausen@computer.org 3862 URI: http://www.ThomasClausen.org/ 3864 Christopher Dearlove 3865 BAE Systems ATC 3867 Phone: +44 1245 242194 3868 EMail: chris.dearlove@baesystems.com 3869 URI: http://www.baesystems.com/ 3871 Philippe Jacquet 3872 Project Hipercom, INRIA 3874 Phone: +33 1 3963 5263 3875 EMail: philippe.jacquet@inria.fr 3877 The OLSRv2 Design Team 3878 MANET Working Group