idnits 2.17.1 draft-ietf-manet-olsrv2-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 953 has weird spacing: '...ig_addr is a ...' == Line 955 has weird spacing: '... O_time speci...' == Line 971 has weird spacing: '...et_addr is th...' == Line 974 has weird spacing: '...AL_dist is th...' == Line 997 has weird spacing: '...ingness is th...' == (31 more instances...) -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 13, 2009) is 5372 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 (~~), 8 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: January 14, 2010 BAE Systems ATC 6 P. Jacquet 7 Project Hipercom, INRIA 8 The OLSRv2 Design Team 9 MANET Working Group 10 July 13, 2009 12 The Optimized Link State Routing Protocol version 2 13 draft-ietf-manet-olsrv2-09 15 Status of This Memo 17 This Internet-Draft is submitted to IETF in full conformance with the 18 provisions of BCP 78 and BCP 79. This document may contain material 19 from IETF Documents or IETF Contributions published or made publicly 20 available before November 10, 2008. The person(s) controlling the 21 copyright in some of this material may not have granted the IETF 22 Trust the right to allow modifications of such material outside the 23 IETF Standards Process. Without obtaining an adequate license from 24 the person(s) controlling the copyright in such materials, this 25 document may not be modified outside the IETF Standards Process, and 26 derivative works of it may not be created outside the IETF Standards 27 Process, except to format it for publication as an RFC or to 28 translate it into languages other than English. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF), its areas, and its working groups. Note that 32 other groups may also distribute working documents as Internet- 33 Drafts. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 The list of current Internet-Drafts can be accessed at 41 http://www.ietf.org/ietf/1id-abstracts.txt. 43 The list of Internet-Draft Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html. 46 This Internet-Draft will expire on January 14, 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 . . . . . . . . . . . . . . . . . . . 7 68 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 8 69 4.1. Routers and Interfaces . . . . . . . . . . . . . . . . . . 10 70 4.2. Information Base Overview . . . . . . . . . . . . . . . . 11 71 4.2.1. Local Information Base . . . . . . . . . . . . . . . . 11 72 4.2.2. Interface Information Bases . . . . . . . . . . . . . 11 73 4.2.3. Neighbor Information Base . . . . . . . . . . . . . . 11 74 4.2.4. Topology Information Base . . . . . . . . . . . . . . 12 75 4.2.5. Processing and Forwarding Information Base . . . . . . 13 76 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 13 77 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 14 78 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 14 79 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 15 80 5.3. Local History Times . . . . . . . . . . . . . . . . . . . 15 81 5.4. Message Intervals . . . . . . . . . . . . . . . . . . . . 15 82 5.5. Advertised Information Validity Times . . . . . . . . . . 16 83 5.6. Received Message Validity Times . . . . . . . . . . . . . 17 84 5.7. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 17 85 5.8. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 18 86 5.9. Willingness . . . . . . . . . . . . . . . . . . . . . . . 18 87 5.10. Parameter Change Constraints . . . . . . . . . . . . . . . 19 88 6. Information Bases . . . . . . . . . . . . . . . . . . . . . . 20 89 6.1. Local Information Base . . . . . . . . . . . . . . . . . . 21 90 6.1.1. Originator Set . . . . . . . . . . . . . . . . . . . . 21 91 6.1.2. Local Attached Network Set . . . . . . . . . . . . . . 21 92 6.2. Neighbor Information Base . . . . . . . . . . . . . . . . 22 93 6.3. Topology Information Base . . . . . . . . . . . . . . . . 22 94 6.3.1. Advertised Neighbor Set . . . . . . . . . . . . . . . 22 95 6.3.2. Advertising Remote Router Set . . . . . . . . . . . . 23 96 6.3.3. Topology Set . . . . . . . . . . . . . . . . . . . . . 23 97 6.3.4. Attached Network Set . . . . . . . . . . . . . . . . . 24 98 6.3.5. Routing Set . . . . . . . . . . . . . . . . . . . . . 25 99 6.4. Processing and Forwarding Information Base . . . . . . . . 25 100 6.4.1. Received Set . . . . . . . . . . . . . . . . . . . . . 25 101 6.4.2. Processed Set . . . . . . . . . . . . . . . . . . . . 26 102 6.4.3. Forwarded Set . . . . . . . . . . . . . . . . . . . . 26 103 6.4.4. Relay Set . . . . . . . . . . . . . . . . . . . . . . 27 104 7. Message Processing and Forwarding . . . . . . . . . . . . . . 27 105 7.1. Actions when Receiving a Message . . . . . . . . . . . . . 28 106 7.2. Message Considered for Processing . . . . . . . . . . . . 28 107 7.3. Message Considered for Forwarding . . . . . . . . . . . . 29 108 8. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 31 109 8.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 32 110 8.1.1. HELLO Message TLVs . . . . . . . . . . . . . . . . . . 32 111 8.1.2. HELLO Message Address Block TLVs . . . . . . . . . . . 33 112 8.2. TC Messages . . . . . . . . . . . . . . . . . . . . . . . 33 113 8.2.1. TC Message TLVs . . . . . . . . . . . . . . . . . . . 34 114 8.2.2. TC Message Address Block TLVs . . . . . . . . . . . . 34 115 9. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 35 116 9.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 35 117 10. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 36 118 10.1. Updating Willingness . . . . . . . . . . . . . . . . . . . 36 119 10.2. Updating MPR Selectors . . . . . . . . . . . . . . . . . . 36 120 10.3. Symmetric 1-Hop and 2-Hop Neighborhood Changes . . . . . . 37 121 11. TC Message Generation . . . . . . . . . . . . . . . . . . . . 38 122 11.1. TC Message: Transmission . . . . . . . . . . . . . . . . . 39 123 12. TC Message Processing . . . . . . . . . . . . . . . . . . . . 40 124 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 40 125 12.2. Initial TC Message Processing . . . . . . . . . . . . . . 41 126 12.3. Initial TC Message Processing . . . . . . . . . . . . . . 42 127 12.3.1. Populating the Advertising Remote Router Set . . . . . 42 128 12.3.2. Populating the Topology Set . . . . . . . . . . . . . 43 129 12.3.3. Populating the Attached Network Set . . . . . . . . . 43 130 12.4. Completing TC Message Processing . . . . . . . . . . . . . 44 131 12.4.1. Purging the Topology Set . . . . . . . . . . . . . . . 44 132 12.4.2. Purging the Attached Network Set . . . . . . . . . . . 44 133 13. Information Base Changes . . . . . . . . . . . . . . . . . . . 45 134 14. Selecting MPRs . . . . . . . . . . . . . . . . . . . . . . . . 46 135 15. Populating Derived Sets . . . . . . . . . . . . . . . . . . . 48 136 15.1. Populating the Relay Set . . . . . . . . . . . . . . . . . 48 137 15.2. Populating the Advertised Neighbor Set . . . . . . . . . . 48 138 16. Routing Set Calculation . . . . . . . . . . . . . . . . . . . 49 139 16.1. Network Topology Graph . . . . . . . . . . . . . . . . . . 49 140 16.2. Populating the Routing Set . . . . . . . . . . . . . . . . 50 141 16.3. Routing Set Updates . . . . . . . . . . . . . . . . . . . 51 142 17. Proposed Values for Parameters and Constants . . . . . . . . . 51 143 17.1. Local History Time Parameters . . . . . . . . . . . . . . 51 144 17.2. Message Interval Parameters . . . . . . . . . . . . . . . 51 145 17.3. Advertised Information Validity Time Parameters . . . . . 52 146 17.4. Received Message Validity Time Parameters . . . . . . . . 52 147 17.5. Jitter Time Parameters . . . . . . . . . . . . . . . . . . 52 148 17.6. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 52 149 17.7. Willingness Parameter and Constants . . . . . . . . . . . 52 150 18. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 52 151 19. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 53 152 19.1. Message Types . . . . . . . . . . . . . . . . . . . . . . 53 153 19.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 53 154 19.3. Address Block TLV Types . . . . . . . . . . . . . . . . . 54 155 20. Security Considerations . . . . . . . . . . . . . . . . . . . 55 156 20.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . 55 157 20.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 56 158 20.3. Interaction with External Routing Domains . . . . . . . . 57 159 21. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 58 160 22. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 58 161 23. References . . . . . . . . . . . . . . . . . . . . . . . . . . 58 162 23.1. Normative References . . . . . . . . . . . . . . . . . . . 58 163 23.2. Informative References . . . . . . . . . . . . . . . . . . 59 164 Appendix A. Router Configuration . . . . . . . . . . . . . . . . 60 165 Appendix B. Example Algorithm for Calculating MPRs . . . . . . . 60 166 B.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 61 167 B.2. MPR Selection Algorithm for each OLSRv2 Interface . . . . 61 168 Appendix C. Example Algorithm for Calculating the Routing Set . . 62 169 C.1. Add Local Symmetric Links . . . . . . . . . . . . . . . . 62 170 C.2. Add Remote Symmetric Links . . . . . . . . . . . . . . . . 63 171 C.3. Add Attached Networks . . . . . . . . . . . . . . . . . . 64 172 Appendix D. Example Message Layout . . . . . . . . . . . . . . . 65 173 Appendix E. Constraints . . . . . . . . . . . . . . . . . . . . . 67 174 Appendix F. Flow and Congestion Control . . . . . . . . . . . . . 70 176 1. Introduction 178 The Optimized Link State Routing protocol version 2 (OLSRv2) is an 179 update to OLSRv1 as published in [RFC3626]. Compared to [RFC3626], 180 OLSRv2 retains the same basic mechanisms and algorithms, while using 181 a more flexible and efficient signaling framework, and includes some 182 simplification of the messages being exchanged. 184 OLSRv2 is developed for mobile ad hoc networks. It operates as a 185 table driven, proactive protocol, i.e. it exchanges topology 186 information with other routers in the network regularly. It is an 187 optimization of the classical link state routing protocol. The key 188 concept used in the protocol is that of MultiPoint Relays (MPRs). 189 Each router selects a set of its neighbor routers (which "cover" all 190 of its symmetrically connected 2-hop neighbor routers) as MPRs. 191 Control traffic is flooded through the network using hop by hop 192 forwarding, but where a router only needs to forward control traffic 193 directly received from its MPR selectors (routers which have selected 194 it as an MPR). This mechanism, denoted "MPR flooding", provides an 195 efficient mechanism for information distribution within the MANET by 196 reducing the number of transmissions required. 198 Routers selected as MPRs also have a special responsibility when 199 declaring link state information in the network. A sufficient 200 requirement for OLSRv2 to provide shortest (lowest hop count) path 201 routes to all destinations is that routers declare link state 202 information for their MPR selectors, if any. Additional available 203 link state information may be transmitted, e.g. for redundancy. 204 Thus, as well as being used to facilitate MPR flooding, use of MPRs 205 allows the reduction of the number and size of link state messages, 206 and MPRs are used as intermediate routers in multi-hop routes. 208 A router selects MPRs from among its one hop neighbors connected by 209 "symmetric", i.e. bidirectional, links. Therefore, selecting routes 210 through MPRs automatically avoids the problems associated with data 211 packet transfer over unidirectional links (such as the problem of not 212 getting link layer acknowledgments at each hop, for link layers 213 employing this technique). 215 OLSRv2 uses and extends [NHDP] and uses [RFC5444], [RFC5497] and, 216 optionally, [RFC5148]. (These other protocols and specifications 217 were all originally created as part of OLSRv2, but have been 218 specified separately for wider use.) 220 OLSRv2 makes no assumptions about the underlying link layer. 221 However, OLSRv2, through its use of [NHDP], may use link layer 222 information and notifications when available and applicable. 224 OLSRv2, as OLSRv1, inherits its concept of forwarding and relaying 225 from HIPERLAN (a MAC layer protocol) which is standardized by ETSI 226 [HIPERLAN], [HIPERLAN2]. 228 2. Terminology 230 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 231 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 232 "OPTIONAL" in this document are to be interpreted as described in 233 [RFC2119]. 235 All terms introduced in [RFC5444], including "packet", "message", 236 "Address Block", "TLV Block", and "TLV", are to be interpreted as 237 described there. 239 All terms introduced in [NHDP], including "interface", "MANET 240 interface", "address", "symmetric link", "symmetric 1-hop neighbor", 241 "symmetric 2-hop neighbor", "constant", "interface parameter", and 242 "router parameter", are to be interpreted as described there. 244 Additionally, this document uses the following terminology: 246 Router - A MANET router which implements the Optimized Link State 247 Routing protocol version 2 as specified in this document. 249 OLSRv2 interface - A MANET interface, running OLSRv2. Note that all 250 references to MANET interfaces in [NHDP] refer to OLSRv2 251 interfaces when using [NHDP] to support OLSRv2. 253 Originator address - An address which is unique (within the MANET) 254 to the selecting router. A router MUST select an originator 255 address; it MAY choose one of its interface addresses as its 256 originator address. An originator address MUST NOT have a prefix 257 length. An originator address MUST be included in all messages 258 generated by this protocol, and as specified in [RFC5444]. 260 Willingness - A numerical value between WILL_NEVER and WILL_ALWAYS 261 (both inclusive), which represents the router's willingness to be 262 selected as an MPR. 264 Willing symmetric 1-hop neighbor - A symmetric 1-hop neighbor of 265 this router which has willingness not equal to WILL_NEVER. 267 Symmetric strict 2-hop neighbor - A router, X, is a symmetric strict 268 2-hop neighbor of a router Y, if router X is a symmetric 2-hop 269 neighbor of router Y and if router X is not also a willing 270 symmetric 1-hop neighbor of router Y. 272 Symmetric strict 2-hop neighbor through OLSRv2 interface I - A 273 symmetric strict 2-hop neighbor of the router with OLSRv2 274 interface I which is a symmetric 1-hop neighbor of a willing 275 symmetric 1-hop neighbor of that router via a symmetric link using 276 OLSRv2 interface I. The router MAY elect to consider only 277 information received over OLSRv2 interface I in making this 278 determination. 280 Symmetric strict 2-hop neighborhood - The symmetric strict 2-hop 281 neighborhood of a router X is the set of symmetric strict 2-hop 282 neighbors of router X. 284 Multipoint relay (MPR) - A router, X, is an MPR for a router, Y, if 285 router Y has selected router X to "re-transmit" all the broadcast 286 messages that it receives from router X, provided that the message 287 is not a duplicate, and that the hop limit field of the message is 288 greater than one. 290 MPR selector - A router, Y, is an MPR selector of router X if router 291 Y has selected router X as MPR. 293 MPR flooding - The optimized MANET-wide information distribution 294 mechanism, employed by this protocol, in which a message is 295 relayed by only a reduced subset of the routers in the network. 297 This document employs the same notational conventions as in [RFC5444] 298 and [NHDP]. 300 3. Applicability Statement 302 The Optimized Link State Routing protocol version 2 (OLSRv2): 304 o Is a proactive routing protocol for mobile ad hoc networks 305 (MANETs) [RFC2501]. 307 o Is designed to work in networks with a dynamic topology, and in 308 which messages may be lost, such as due to collisions in wireless 309 networks. 311 o Supports routers that each have one or more participating OLSRv2 312 interfaces. The set of a router's interfaces may change over 313 time. Each OLSRv2 interface may have one or more addresses (which 314 may have prefix lengths), and these may also be dynamically 315 changing. 317 o Enables hop-by-hop routing, i.e., each router can use its local 318 information provided by OLSRv2 to route packets. 320 o Continuously maintains routes to all destinations in the network, 321 i.e., routes are instantly available and data traffic is subject 322 to no delays due to route discovery. Consequently, no data 323 traffic buffering is required. 325 o Supports routers which have non-OLSRv2 interfaces which may be 326 local to a router or which can serve as gateways towards other 327 networks. 329 o Is optimized for large and dense networks: the larger and more 330 dense a network, the more optimization can be achieved by using 331 MPRs, compared to the classic link state algorithm. 333 o Uses the message format specified in [RFC5444]. This includes the 334 definition of a TC Message Type, used for MANET wide signaling of 335 network topology information. 337 o Allows "external" and "internal" extensibility as enabled by 338 [RFC5444]. 340 o Uses [NHDP] for discovering each OLSRv2 router's 1-hop and 341 symmetric 2-hop neighbors, and extends [NHDP] by addition of MPR 342 and willingness information. 344 o Is designed to work in a completely distributed manner, and does 345 not depend on any central entity. 347 4. Protocol Overview and Functioning 349 The objective of OLSRv2 is, for each router to, independently: 351 o Identify all destinations in the network. 353 o Identify a sufficient subset of links in the network, in order 354 that shortest paths can be calculated to all available 355 destinations. 357 o Provide a Routing Set, containing these shortest paths from this 358 router to all destinations. 360 These objectives are achieved for each router by: 362 o Using [NHDP] to identify symmetric 1-hop neighbors and symmetric 363 2-hop neighbors. 365 o Independently selecting MPRs from among its symmetric 1-hop 366 neighbors such that all symmetric 2-hop neighbors are reachable 367 via at least one symmetric 1-hop neighbor. An analysis and 368 examples of MPR selection algorithms is given in [MPR], a 369 suggested algorithm is included in this specification. Note that 370 it is not necessary for routers to use the same algorithm to 371 interoperate. 373 o Signaling its MPR selection by extending [NHDP] to include this 374 information in outgoing HELLO messages. 376 o Extracting its MPR selectors from received HELLO messages. 378 o Reporting its willingness to be an MPR in HELLO messages. The 379 router's willingness to be an MPR indicates how willing it is to 380 participate in MPR flooding and to be an intermediate node for 381 routing. A node can absolutely decline to perform either role. 383 o Periodically signaling links between MPR selectors and itself 384 throughout the MANET, by using TC (Topology Control) messages, 385 defined in this specification. 387 o Diffusing TC messages by using flooding reduction mechanism, 388 denoted "MPR flooding": only the MPRs of a router will retransmit 389 messages received from (i.e., originated or last relayed by) that 390 router. 392 This specification defines, in turn: 394 o Parameters and constants used by OLSRv2, in addition to those 395 specified in [NHDP]. Parameters used by OLSRv2 may be, where 396 appropriate, specific to a given OLSRv2 interface, or to an OLSRv2 397 router. OLSRv2 allows all parameters to be changed dynamically, 398 and to be set independently for each OLSRv2 router or OLSRv2 399 interface, as appropriate. 401 o Extensions to the Information Bases specified in [NHDP], and new 402 Topology Information Base and Processing and Forwarding 403 Information Base. 405 o An Address Block TLV, to be included within the HELLO messages of 406 [NHDP], allowing a router to signal MPR selection. 408 o A Message TLV, to be included within the HELLO messages of [NHDP], 409 allowing a router to indicate its willingness to be an MPR. 411 o The MPR flooding mechanism. 413 o The format of the TC message that is used for MANET wide 414 signaling. 416 o The generation of TC messages from the appropriate information in 417 the Information Bases. 419 o The updating of the Information Bases according to received TC 420 messages. 422 o The response to other events, such as the expiration of 423 information in the Information Bases. 425 OLSRv2 inherits the stability of a link state algorithm and has the 426 advantage of having routes immediately available when needed due to 427 its proactive nature. 429 OLSRv2 only interacts with IP through routing table management, and 430 the use of the sending IP address for IP datagrams containing OLSRv2 431 messages. 433 4.1. Routers and Interfaces 435 In order for a router to participate in a MANET, it MUST have at 436 least one, and possibly more, OLSRv2 interfaces. Each OLSRv2 437 interface: 439 o Is configured with one or more addresses, as specified in [NHDP]. 440 These addresses MUST be unique within the MANET. 442 o Has a number of interface parameters, adding to those specified in 443 [NHDP]. 445 o Has an Interface Information Base, extending that specified in 446 [NHDP]. 448 o Generates and processes HELLO messages according to [NHDP], 449 extended as specified in Section 9 and Section 10. 451 In addition to a set of MANET interfaces as described above, each 452 router: 454 o Has a number of router parameters, adding to those specified in 455 [NHDP]. 457 o Has a Local Information Base, extending that specified in [NHDP]. 459 o Has a Neighbor Information Base, extending that specified in 460 [NHDP]. 462 o Has a Topology Information Base, recording information required 463 for generation and processing of TC messages. 465 o Has a Processing and Forwarding Information Base, recording 466 information required for MPR flooding, and to ensure that each TC 467 message is only processed once by a router. 469 o Generates and processes TC messages. 471 4.2. Information Base Overview 473 Each router maintains the Information Bases described in the 474 following sections. These are used for describing the protocol in 475 this document. An implementation of this protocol MAY maintain this 476 information in the indicated form, or in any other organization which 477 offers access to this information. In particular, note that it is 478 not necessary to remove Tuples from Sets at the exact time indicated, 479 only to behave as if the Tuples were removed at that time. 481 4.2.1. Local Information Base 483 The Local Information Base is specified in [NHDP] and contains a 484 router's local configuration. It is extended in this specification 485 to also contain a router's: 487 o Originator Set, containing addresses that were recently used as 488 this router's originator address. 490 o Local Attached Network Set, containing addresses of networks to 491 which this router can act as a gateway. 493 The Originator Set is used to enable a router to recognize and 494 discard control traffic which was originated by the router itself. 496 The Local Attached Network Set is used to enable a router to include 497 advertisement of reachability to a network, for which the router can 498 act as a gateway, when generating TC messages. 500 4.2.2. Interface Information Bases 502 The Interface Information Bases, one for each OLSRv2 interface, are 503 specified in [NHDP]. In addition to the uses in [NHDP], information 504 recorded in the Interface Information Bases is used for completing 505 the Routing Set. 507 4.2.3. Neighbor Information Base 509 The Neighbor Information Base is specified in [NHDP], and is extended 510 to also record the willingness of each neighbor to be an MPR, as well 511 as this router's MPR relationships with each neighbor. Specifically, 512 each Neighbor Tuple is extended to record whether that neighbor is an 513 MPR and/or MPR selector of this router, as well as the neighbor's 514 willingness to be an MPR. 516 In addition to the uses in [NHDP], information recorded in the 517 Neighbor Information Base is used to determine inclusion of the MPR 518 Address Block TLV, defined in this document, as well as for 519 populating the Advertised Neighbor Set and the Relay Sets of a 520 router. 522 4.2.4. Topology Information Base 524 The Topology Information Base contains: 526 o An Advertised Neighbor Set, describing the symmetric 1-hop 527 neighbors of this router that are to be advertised in TC messages. 528 This set contains at least the MPR selectors of this router, and 529 is associated with an Advertised Neighbor Sequence Number (ANSN), 530 which is incremented for each change made to this Advertised 531 Neighbor Set. 533 o An Advertising Remote Router Set, describing each other router 534 from which TC messages have been received. 536 o A Topology Set, recording links between routers in the MANET, as 537 described by received TC messages. 539 o An Attached Network Set, recording networks to which a remote 540 router has advertised that it may act as a gateway. 542 o A Routing Set, calculated based on the Interface Information 543 Bases, the Neighbor Information Base, and the Topology Information 544 Base to record routes from this router to all available 545 destinations, The routing table is to be updated from this Routing 546 Set. (A router MAY choose to use any or all destination addresses 547 in the Routing Set to update the routing table, this selection is 548 outside the scope of OLSRv2.) 550 The Advertised Neighbor Set is used for when generating TC messages; 551 the Advertised Neighbor Sequence Number is included in each TC 552 message, thereby allowing a receiving router to identify if a TC 553 message contains fresh or outdated information. 555 The Advertising Remote Router Set, the Topology Set and the Attached 556 Network Set are all updated upon receipt of TC messages, and are used 557 when determining the contents of the Routing Set. 559 4.2.5. Processing and Forwarding Information Base 561 The Processing and Forwarding Information Base contains: 563 o A Received Set, describing TC messages received by this router. 565 o A Processed Set, describing TC messages processed by this router. 567 o A Forwarded Set, describing TC messages forwarded by this router. 569 o A Relay Set for each OLSRv2 interface, describing the set of 570 neighbor routers from which received traffic is to be relayed (if 571 otherwise appropriate). 573 The Processing and Forwarding Information Base serves the MPR 574 flooding mechanism by enabling that received messages are forwarded 575 at most once, by a router. and also ensures that received messages 576 are processed exactly once. 578 4.3. Signaling Overview 580 OLSRv2 uses the neighborhood discovery protocol [NHDP], and generates 581 and processes HELLO messages according to [NHDP], extended according 582 to Section 9 and Section 10. 584 OLSRv2 specifies a single message type, the TC message. 586 OLSRv2 does not require reliable transmission of TC messages; each 587 router sends TC messages periodically, and can therefore sustain a 588 reasonable loss of some such messages. Such losses may occur 589 frequently in wireless networks due to collisions or other 590 transmission problems. OLSRv2 MAY use "jitter", randomized 591 adjustments to message transmission times, to reduce the incidence of 592 collisions as specified in [RFC5148]. 594 OLSRv2 does not require sequenced delivery of TC messages. Each TC 595 message contains a sequence number which is incremented when the 596 message contents change. Thus the recipient of a TC message can, if 597 required, easily identify which information is more recent, even if 598 messages have been re-ordered while in transmission. 600 TC messages may be "complete" or "incomplete". A complete TC message 601 contains at least the set of addresses of the originating router's 602 MPR selectors. Complete TC messages are generated periodically (and 603 also, optionally, in response to neighborhood changes). Incomplete 604 TC messages may be used to report additions to advertised information 605 without repeating unchanged information. 607 TC messages are MPR flooded throughout the MANET. A router 608 retransmits a TC message only if it is received from (i.e., 609 originated from or was last relayed by) one of that router's MPR 610 selectors. 612 Some TC messages may be MPR flooded over only part of the network, 613 allowing a router to ensure that nearer routers are kept more up to 614 date than distant routers, such as is used in Fisheye State Routing 615 [FSR] and Fuzzy Sighted Link State routing [FSLS]. This is enabled 616 in OLSRv2 by using [RFC5497]. 618 5. Protocol Parameters and Constants 620 The parameters and constants used in this specification are those 621 defined in [NHDP] plus those defined in this section. The separation 622 in [NHDP] into interface parameters, router parameters and constants 623 is also used in OLSRv2, however all but one (RX_HOLD_TIME) of the 624 parameters added by OLSRv2 are router parameters. Parameters may be 625 classified into the following categories: 627 o Local history times 629 o Message intervals 631 o Advertised information validity times 633 o Received message validity times 635 o Jitter times 637 o Hop limits 639 o Willingness 641 In addition, constants for particular cases of a router's willingness 642 to be an MPR are defined. These parameters and constants are 643 detailed in the following sections. As for the parameters in [NHDP], 644 parameters defined in this document may be changed dynamically by a 645 router, and need not be the same on different routers, even in the 646 same MANET, or on different interfaces of the same router (for 647 interface parameters). 649 5.1. Protocol and Port Numbers 651 This protocol specifies TC messages, which are included in packets as 652 defined by [RFC5444]. These packets may be sent either using the 653 "manet" protocol number or the "manet" well-known UDP port number, as 654 specified in [RFC5498]. 656 TC messages and HELLO messages [NHDP] SHOULD, in a given deployment 657 of OLSRv2, both be using the same of either of IP or UDP, in order 658 that it is possible to combine messages of both protocols into the 659 same [RFC5444] packet. 661 5.2. Multicast Address 663 This protocol specifies HELLO messages, which are included in packets 664 as defined by [RFC5444]. These packets may be locally transmitted 665 using the link local multicast address "LL-MANET-Routers", as 666 specified in [RFC5498]. 668 5.3. Local History Times 670 The following router parameter manages the time for which local 671 information is retained: 673 O_HOLD_TIME - is used to define the time for which a recently used 674 and replaced originator address is used to recognize the router's 675 own messages. 677 The following constraint applies to this parameter: 679 o O_HOLD_TIME >= 0 681 5.4. Message Intervals 683 The following router parameters regulate TC message transmissions by 684 a router. TC messages are usually sent periodically, but MAY also be 685 sent in response to changes in the router's Advertised Neighbor Set 686 and Local Attached Network Set. With a larger value of the parameter 687 TC_INTERVAL, and a smaller value of the parameter TC_MIN_INTERVAL, TC 688 messages may more often be transmitted in response to changes in a 689 highly dynamic network. However because a router has no knowledge 690 of, for example, routers remote to it (i.e. beyond 2 hops away) 691 joining the network, TC messages MUST NOT be sent purely 692 responsively. 694 TC_INTERVAL - is the maximum time between the transmission of two 695 successive TC messages by this router. When no TC messages are 696 sent in response to local network changes (by design, or because 697 the local network is not changing) then TC messages SHOULD be sent 698 at a regular interval TC_INTERVAL, possibly modified by jitter as 699 specified in [RFC5148]. 701 TC_MIN_INTERVAL - is the minimum interval between transmission of 702 two successive TC messages by this router. (This minimum interval 703 MAY be modified by jitter, as specified in [RFC5148].) 705 The following constraints apply to these parameters: 707 o TC_INTERVAL > 0 709 o TC_MIN_INTERVAL >= 0 711 o TC_INTERVAL >= TC_MIN_INTERVAL 713 o If INTERVAL_TIME TLVs as defined in [RFC5497] are included in TC 714 messages, then TC_INTERVAL MUST be representable as described in 715 [RFC5497]. 717 5.5. Advertised Information Validity Times 719 The following router parameters manage the validity time of 720 information advertised in TC messages: 722 T_HOLD_TIME - is used to define the minimum Value in the 723 VALIDITY_TIME TLV included in all TC messages sent by this router. 724 If a single value of parameter TC_HOP_LIMIT (see Section 5.8) is 725 used then this will be the only Value in that TLV. 727 A_HOLD_TIME - is the period during which TC messages are sent after 728 they no longer have any advertised information to report, but are 729 sent in order to accelerate outdated information removal by other 730 routers. 732 The following constraints apply to these parameters: 734 o T_HOLD_TIME > 0 736 o A_HOLD_TIME >= 0 738 o T_HOLD_TIME >= TC_INTERVAL 740 o If TC messages can be lost, then both T_HOLD_TIME and A_HOLD_TIME 741 SHOULD be significantly greater than TC_INTERVAL; a value >= 3 x 742 TC_INTERVAL is RECOMMENDED. 744 o T_HOLD_TIME MUST be representable as described in [RFC5497]. 746 5.6. Received Message Validity Times 748 The following parameters manage the validity time of recorded 749 received message information: 751 RX_HOLD_TIME - is an interface parameter, and is the period after 752 receipt of a message by the appropriate OLSRv2 interface of this 753 router for which that information is recorded, in order that the 754 message is recognized as having been previously received on this 755 OLSRv2 interface. 757 P_HOLD_TIME - is a router parameter, and is the period after receipt 758 of a message which is processed by this router for which that 759 information is recorded, in order that the message is not 760 processed again if received again. 762 F_HOLD_TIME - is a router parameter, and is the period after receipt 763 of a message which is forwarded by this router for which that 764 information is recorded, in order that the message is not 765 forwarded again if received again. 767 The following constraints apply to these parameters: 769 o RX_HOLD_TIME > 0 771 o P_HOLD_TIME > 0 773 o F_HOLD_TIME > 0 775 o All of these parameters SHOULD be greater than the maximum 776 difference in time that a message may take to traverse the MANET, 777 taking into account any message forwarding jitter as well as 778 propagation, queuing, and processing delays. 780 5.7. Jitter 782 If jitter, as defined in [RFC5148], is used then these parameters are 783 as follows: 785 TP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 786 for periodically generated TC messages sent by this router. 788 TT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 789 for externally triggered TC messages sent by this router. 791 F_MAXJITTER - represents the default value of MAXJITTER used in 792 [RFC5148] for messages forwarded by this router. However before 793 using F_MAXJITTER a router MAY attempt to deduce a more 794 appropriate value of MAXJITTER, for example based on any 795 INTERVAL_TIME or VALIDITY_TIME TLVs contained in the message to be 796 forwarded. 798 For constraints on these parameters see [RFC5148]. 800 5.8. Hop Limit Parameter 802 The parameter TC_HOP_LIMIT is the hop limit set in each TC message. 803 TC_HOP_LIMIT MAY be a single fixed value, or MAY be different in TC 804 messages sent by the same router. However each other router, at any 805 hop count distance, SHOULD see a regular pattern of TC messages, in 806 order that meaningful Values of INTERVAL_TIME and VALIDITY_TIME TLVs 807 at each hop count distance can be included as defined in [RFC5497]. 808 Thus the pattern of TC_HOP_LIMIT SHOULD be defined to have this 809 property. For example the repeating pattern (255 4 4) satisfies this 810 property (having period TC_INTERVAL at hop counts up to 4, inclusive, 811 and 3 x TC_INTERVAL at hop counts greater than 4), but the repeating 812 pattern (255 255 4 4) does not satisfy this property because at hop 813 counts greater than 4, message intervals are alternately TC_INTERVAL 814 and 3 x TC_INTERVAL. 816 The following constraints apply to this parameter: 818 o The maximum value of TC_HOP_LIMIT >= the network diameter in hops, 819 a value of 255 is RECOMMENDED. 821 o All values of TC_HOP_LIMIT >= 2. 823 5.9. Willingness 825 Each router has a WILLINGNESS parameter, which MUST be in the range 826 WILL_NEVER to WILL_ALWAYS, inclusive, and represents its willingness 827 to be an MPR, and hence its willingness to forward messages and be an 828 intermediate router on routes. If a router has WILLINGNESS = 829 WILL_NEVER it does not perform these tasks. A MANET using OLSRv2 830 with too many routers with WILLINGNESS = WILL_NEVER will not 831 function; it MUST be ensured, by administrative or other means, that 832 this does not happen. 834 Routers MAY have different WILLINGNESS values; however the three 835 constants WILL_NEVER, WILL_DEFAULT and WILL_ALWAYS MUST have the 836 values defined in Section 17. (Use of WILLINGNESS = WILL_DEFAULT 837 allows a router to avoid including an MPR_WILLING TLV in its TC 838 messages, use of WILLINGNESS = WILL_ALWAYS means that a router will 839 always be selected as an MPR by all symmetric 1-hop neighbors.) 841 The following constraints apply to this parameter: 843 o WILLINGNESS >= WILL_NEVER 845 o WILLINGNESS <= WILL_ALWAYS 847 5.10. Parameter Change Constraints 849 This section presents guidelines, applicable if protocol parameters 850 are changed dynamically. 852 O_HOLD_TIME 854 * If O_HOLD_TIME for a router changes, then O_time for all 855 Originator Tuples MAY be changed. 857 TC_INTERVAL 859 * If the TC_INTERVAL for a router increases, then the next TC 860 message generated by this router MUST be generated according to 861 the previous, shorter, TC_INTERVAL. Additional subsequent TC 862 messages MAY be generated according to the previous, shorter, 863 TC_INTERVAL. 865 * If the TC_INTERVAL for a router decreases, then the following 866 TC messages from this router MUST be generated according to the 867 current, shorter, TC_INTERVAL. 869 RX_HOLD_TIME 871 * If RX_HOLD_TIME for an OLSRv2 interface changes, then RX_time 872 for all Received Tuples for that OLSRv2 interface MAY be 873 changed. 875 P_HOLD_TIME 877 * If P_HOLD_TIME changes, then P_time for all Processed Tuples 878 MAY be changed. 880 F_HOLD_TIME 882 * If F_HOLD_TIME changes, then F_time for all Forwarded Tuples 883 MAY be changed. 885 TP_MAXJITTER 887 * If TP_MAXJITTER changes, then the periodic TC message schedule 888 on this router MAY be changed immediately. 890 TT_MAXJITTER 892 * If TT_MAXJITTER changes, then externally triggered TC messages 893 on this router MAY be rescheduled. 895 F_MAXJITTER 897 * If F_MAXJITTER changes, then TC messages waiting to be 898 forwarded with a delay based on this parameter MAY be 899 rescheduled. 901 TC_HOP_LIMIT 903 * If TC_HOP_LIMIT changes, and the router uses multiple values 904 after the change, then message intervals and validity times 905 included in TC messages MUST be respected. The simplest way to 906 do this is to start any new repeating pattern of TC_HOP_LIMIT 907 values with its largest value. 909 6. Information Bases 911 The purpose of OLSRv2 is to determine the Routing Set, which may be 912 used to update IP's Routing Table, providing "next hop" routing 913 information for IP datagrams. OLSRv2 maintains the following 914 Information Bases: 916 Local Information Base - as defined in [NHDP], extended by the 917 addition of an Originator Set, defined in Section 6.1.1 and a 918 Local Attached Network Set, defined in Section 6.1.2. 920 Interface Information Bases - as defined in [NHDP], one Interface 921 Information Base for each OLSRv2 interface. 923 Neighbor Information Base - as defined in [NHDP], extended by the 924 addition of three elements to each Neighbor Tuple, as defined in 925 Section 6.2. 927 Topology Information Base - this Information Base is specific to 928 OLSRv2, and is defined in Section 6.3. 930 Processing and Forwarding Information Base - this Information Base 931 is specific to OLSRv2, and is defined in Section 6.4. 933 The ordering of sequence numbers, when considering which is the 934 greater, is as defined in Section 18. 936 6.1. Local Information Base 938 The Local Information Base as defined in [NHDP] is extended by the 939 addition of an Originator Set, defined in Section 6.1.1, and a Local 940 Attached Network Set, defined in Section 6.1.2. 942 6.1.1. Originator Set 944 A router's Originator Set records addresses that were recently used 945 as originator addresses by this router. If a router's originator 946 address is immutable then this set is always empty and MAY be 947 omitted. It consists of Originator Tuples: 949 (O_orig_addr, O_time) 951 where: 953 O_orig_addr is a recently used originator address; 955 O_time specifies the time at which this Tuple expires and MUST be 956 removed. 958 6.1.2. Local Attached Network Set 960 A router's Local Attached Network Set records its local non-OLSRv2 961 interfaces via which it can act as gateways to other networks. The 962 Local Attached Network Set is not modified by this protocol. This 963 protocol MAY respond to changes to the Local Attached Network Set, 964 which MUST reflect corresponding changes in the router's status. It 965 consists of Local Attached Network Tuples: 967 (AL_net_addr, AL_dist) 969 where: 971 AL_net_addr is the network address of an attached network which can 972 be reached via this router. 974 AL_dist is the number of hops to the network with address 975 AL_net_addr from this router. 977 Attached networks local to this router SHOULD be treated as local 978 non-MANET interfaces, and added to the Local Interface Set, as 979 specified in [NHDP], rather than being added to the Local Attached 980 Network Set. 982 An attached network MAY also be attached to other routers. 984 It is not the responsibility of OLSRv2 to maintain routes from this 985 router to networks recorded in the Local Attached Network Set. 987 Local Attached Neighbor Tuples are removed from the Local Attached 988 Network Set only when the routers' local attached network 989 configuration changes, i.e., they are not subject to timer-based 990 expiration or changes due to received messages. 992 6.2. Neighbor Information Base 994 Each Neighbor Tuple in the Neighbor Set, defined in [NHDP], has these 995 additional elements: 997 N_willingness is the router's willingness to be selected as an MPR, 998 in the range from WILL_NEVER to WILL_ALWAYS, both inclusive; 1000 N_mpr is a boolean flag, describing if this neighbor is selected as 1001 an MPR by this router; 1003 N_mpr_selector is a boolean flag, describing if this neighbor has 1004 selected this router as an MPR, i.e., is an MPR selector of this 1005 router. 1007 6.3. Topology Information Base 1009 The Topology Information Base stores information required for the 1010 generation and processing of TC messages, and information received in 1011 TC messages. The Advertised Neighbor Set contains addresses of 1012 symmetric 1-hop neighbors which are to be reported in TC messages. 1013 The Advertising Remote Router Set, the Topology Set and the Attached 1014 Network Set record information received in TC messages. 1016 Additionally, a Routing Set is maintained, derived from the 1017 information recorded in the Neighborhood Information Base, Topology 1018 Set, Attached Network Set and Advertising Remote Router Set. 1020 6.3.1. Advertised Neighbor Set 1022 A router's Advertised Neighbor Set contains addresses of symmetric 1023 1-hop neighbors which are to be advertised through TC messages. It 1024 consists of Advertised Neighbor Tuples: 1026 (A_neighbor_addr) 1028 In addition, an Advertised Neighbor Set Sequence Number (ANSN) is 1029 maintained. Each time the Advertised Neighbor Set is updated, the 1030 ANSN MUST be incremented. The ANSN MUST also be incremented if there 1031 is a change to the set of Local Attached Network Tuples that are to 1032 be advertised in the router's TC messages. 1034 The Advertised Neighbor Set for a router is derived from the Neighbor 1035 Set of that same router, specifically, each address in the 1036 N_neighbor_addr_list of a Neighbor Tuple MUST be an A_neighbor_addr 1037 if the corresponding N_mpr_selector = true, and MAY be an 1038 A_neighbor_addr if the corresponding N_mpr_selector = false. No 1039 other address may be an A_neighbor_addr. The Advertised Neighbor Set 1040 MUST therefore be updated when the Neighbor Set changes, see 1041 Section 13. Advertised Neighbor Tuples are not subject to timer- 1042 based expiration. 1044 6.3.2. Advertising Remote Router Set 1046 A router's Advertising Remote Router Set records information 1047 describing each remote router in the network that transmits TC 1048 messages. It consists of Advertising Remote Router Tuples: 1050 (AR_orig_addr, AR_seq_number, AR_addr_list, AR_time) 1052 where: 1054 AR_orig_addr is the originator address of a received TC message, 1055 note that this does not include a prefix length; 1057 AR_seq_number is the greatest ANSN in any TC message received which 1058 originated from the router with originator address AR_orig_addr 1059 (i.e., which contributed to the information contained in this 1060 Tuple); 1062 AR_addr_list is an unordered list of the addresses of the router 1063 with originator address AR_orig_addr; 1065 AR_time is the time at which this Tuple expires and MUST be removed. 1067 6.3.3. Topology Set 1069 A router's Topology Set records topology information about the 1070 network. It consists of Topology Tuples: 1072 (T_dest_addr, T_orig_addr, T_seq_number, T_time) 1074 where: 1076 T_dest_addr is an address of a destination router, which may be 1077 reached in one hop from the router with originator address 1078 T_orig_addr; 1080 T_orig_addr is the originator address of a router which is the last 1081 hop on a path towards the router with address T_dest_addr, note 1082 that this does not include a prefix length; 1084 T_seq_number is the greatest ANSN in any TC message received which 1085 originated from the router with originator address T_orig_addr 1086 (i.e., which contributed to the information contained in this 1087 Tuple); 1089 T_time specifies the time at which this Tuple expires and MUST be 1090 removed. 1092 6.3.4. Attached Network Set 1094 A router's Attached Network Set records information about networks 1095 attached to other routers. It consists of Attached Network Tuples: 1097 (AN_net_addr, AN_orig_addr, AN_dist, AN_seq_number, AN_time) 1099 where: 1101 AN_net_addr is the network address of an attached network, which may 1102 be reached via the router with originator address AN_orig_addr; 1104 AN_orig_addr is the originator address of a router which can act as 1105 gateway to the network with address AN_net_addr, note that this 1106 does not include a prefix length; 1108 AN_dist is the number of hops to the network with address 1109 AN_net_addr from the router with originator address AN_orig_addr; 1111 AN_seq_number is the greatest ANSN in any TC message received which 1112 originated from the router with originator address AN_orig_addr 1113 (i.e., which contributed to the information contained in this 1114 Tuple); 1116 AN_time specifies the time at which this Tuple expires and MUST be 1117 removed. 1119 6.3.5. Routing Set 1121 A router's Routing Set records the selected path to each destination 1122 for which a route is known. It consists of Routing Tuples: 1124 (R_dest_addr, R_next_iface_addr, R_dist, R_local_iface_addr) 1126 where: 1128 R_dest_addr is the address of the destination, either the address of 1129 an interface of a destination router, or the network address of an 1130 attached network; 1132 R_next_iface_addr is the address of the "next hop" on the selected 1133 path to the destination; 1135 R_dist is the number of hops on the selected path to the 1136 destination; 1138 R_local_iface_addr is the address of the local OLSRv2 interface over 1139 which a packet MUST be sent to reach the destination by the 1140 selected path. 1142 The Routing Set for a router is derived from the contents of the 1143 other sets of the router, and is updated (Routing Tuples added or 1144 removed) when routing paths are calculated. Routing Tuples are not 1145 subject to timer-based expiration. 1147 6.4. Processing and Forwarding Information Base 1149 The Processing and Forwarding Information Base records information 1150 required to ensure that a message is processed at most once and is 1151 forwarded at most once per OLSRv2 interface of a router, using MPR 1152 flooding. 1154 6.4.1. Received Set 1156 A router has a Received Set per local OLSRv2 interface. Each 1157 Received Set records the signatures of messages which have been 1158 received over that OLSRv2 interface. Each consists of Received 1159 Tuples: 1161 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 1163 where: 1165 RX_type is the received Message Type; 1167 RX_orig_addr is the originator address of the received message; 1169 RX_seq_number is the message sequence number of the received 1170 message; 1172 RX_time specifies the time at which this Tuple expires and MUST be 1173 removed. 1175 6.4.2. Processed Set 1177 A router's Processed Set records signatures of messages which have 1178 been processed by the router. It consists of Processed Tuples: 1180 (P_type, P_orig_addr, P_seq_number, P_time) 1182 where: 1184 P_type is the processed Message Type; 1186 P_orig_addr is the originator address of the processed message; 1188 P_seq_number is the message sequence number of the processed 1189 message; 1191 P_time specifies the time at which this Tuple expires and MUST be 1192 removed. 1194 6.4.3. Forwarded Set 1196 A router's Forwarded Set records signatures of messages which have 1197 been processed by the router. It consists of Forwarded Tuples: 1199 (F_type, F_orig_addr, F_seq_number, F_time) 1201 where: 1203 F_type is the forwarded Message Type; 1205 F_orig_addr is the originator address of the forwarded message; 1207 F_seq_number is the message sequence number of the forwarded 1208 message; 1210 F_time specifies the time at which this Tuple expires and MUST be 1211 removed. 1213 6.4.4. Relay Set 1215 A router has a Relay Set per local OLSRv2 interface. Each Relay Set 1216 records the addresses of symmetric 1-hop neighbors, such that the 1217 router is to forward messages received from those neighbors' OLSRv2 1218 interfaces, on that local OLSRv2 interface, if not otherwise excluded 1219 from forwarding that message (e.g., by it having been previously 1220 forwarded). It consists of Relay Tuples: 1222 (RY_neighbor_iface_addr) 1224 The Relay Set for an interface is derived from the Link Set for the 1225 same interface, and so Relay Tuples are removed when the 1226 corresponding Link Tuples in the Link Set of this interface are 1227 removed, or when processing otherwise suggests their removal. Relay 1228 Tuples are not subject to timer-based expiration. 1230 7. Message Processing and Forwarding 1232 On receiving a packet, as defined in [RFC5444], a router divides the 1233 packet into the Packet Header and messages. OLSRv2 defines, and 1234 hence owns, the TC Message Type, and hence receives all TC messages. 1235 OLSRv2 is responsible for determining whether a TC message is to be 1236 processed (updating Information Bases) and/or forwarded. 1238 OLSRv2 also receives HELLO messages, which are defined, and hence 1239 owned, by [NHDP]. Received HELLO messages MUST be made available to 1240 OLSRv2 when received on an OLSRv2 interface and after NHDP has 1241 completed its processing thereof. OLSRv2 also processes HELLO 1242 messages, OLSRv2 does not forward HELLO messages. 1244 Extensions to OLSRv2 which define, and hence own, other Messages 1245 Types, MAY manage the processing and/or forwarding of these messages 1246 using the same mechanism as for TC messages. These mechanisms 1247 contain elements (P_type, RX_type, F_type) required only for such 1248 usage. 1250 The processing selection and forwarding mechanisms are designed to 1251 only need to parse the Message Header in order to determine whether a 1252 message is to be processed and/or forwarded, and not to have to parse 1253 the Message Body even if the message is forwarded (but not 1254 processed). An implementation MAY either only parse the Message Body 1255 if necessary, or MAY always parse the Message Body. An 1256 implementation MUST discard the message silently if it is unable to 1257 parse the Message Header or (if attempted) the Message Body. 1259 OLSRv2 does not require any part of the Packet Header. 1261 7.1. Actions when Receiving a Message 1263 If the router receives a HELLO message from [NHDP], then the message 1264 is processed according to Section 10. 1266 A router MUST perform the following tasks for each received TC 1267 message or other Message Type defined by an extension to OLSRv2 and 1268 specified to use this process: 1270 1. If the router recognizes from the originator address of the 1271 message that the message is one which the receiving router itself 1272 originated (i.e. is the current originator address of the router, 1273 or is an O_orig_addr in an Originator Tuple) then the message 1274 MUST be silently discarded. 1276 2. Otherwise: 1278 1. Otherwise: 1280 1. If the message is of a type which may be processed, 1281 including being a TC message, then the message is 1282 considered for processing according to Section 7.2, AND; 1284 2. If for the message is of a type which may be forwarded, 1285 including being a TC message, AND: 1287 - is present and > 1, 1288 AND; 1290 - is not present or < 1291 255 1293 then the message is considered for forwarding according 1294 to Section 7.3. 1296 7.2. Message Considered for Processing 1298 If a message (the "current message") is considered for processing, 1299 then the following tasks MUST be performed: 1301 1. If a Processed Tuple exists with: 1303 * P_type = the Message Type of the current message, AND; 1305 * P_orig_addr = the originator address of the current message, 1306 AND; 1308 * P_seq_number = the message sequence number of the current 1309 message; 1311 then the current message MUST NOT be processed. 1313 2. Otherwise: 1315 1. Create a Processed Tuple with: 1317 + P_type := the Message Type of the current message; 1319 + P_orig_addr := the originator address of the current 1320 message; 1322 + P_seq_number := the sequence number of the current 1323 message; 1325 + P_time := current time + P_HOLD_TIME. 1327 2. Process the current message according to its type. For a TC 1328 message this is as defined in Section 12. 1330 7.3. Message Considered for Forwarding 1332 If a message (the "current message") is considered for forwarding, 1333 then the following tasks MUST be performed: 1335 1. If the sending address (i.e., the source address of the IP 1336 datagram containing the current message) does not match (taking 1337 into account any address prefix) an address in an 1338 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 1339 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 1340 current message was received (the "receiving interface") then the 1341 current message MUST be silently discarded. 1343 2. Otherwise: 1345 1. If a Received Tuple exists in the Received Set for the 1346 receiving interface, with: 1348 + RX_type = the Message Type of the current message, AND; 1350 + RX_orig_addr = the originator address of the current 1351 message, AND; 1353 + RX_seq_number = the sequence number of the current 1354 message; 1356 then the current message MUST be silently discarded. 1358 2. Otherwise: 1360 1. Create a Received Tuple in the Received Set for the 1361 receiving interface with: 1363 - RX_type := the Message Type of the current message; 1365 - RX_orig_addr := originator address of the current 1366 message; 1368 - RX_seq_number := sequence number of the current 1369 message; 1371 - RX_time := current time + RX_HOLD_TIME. 1373 2. If a Forwarded Tuple exists with: 1375 - F_type = the Message Type of the current message, AND; 1377 - F_orig_addr = the originator address of the current 1378 message, AND; 1380 - F_seq_number = the sequence number of the current 1381 message. 1383 then the current message MUST be silently discarded. 1385 3. Otherwise if the sending address matches (taking account 1386 of any address prefix) an RY_neighbor_iface_addr in the 1387 Relay Set for the receiving interface, then: 1389 1. Create a Forwarded Tuple with: 1391 o F_type := the Message Type of the current message; 1393 o F_orig_addr := originator address of the current 1394 message; 1396 o F_seq_number := sequence number of the current 1397 message; 1399 o F_time := current time + F_HOLD_TIME. 1401 2. The Message Header of the current message is modified 1402 by: 1404 o if present, decrement in the 1405 Message Header by 1, AND; 1407 o if present, increment in the 1408 Message Header by 1. 1410 3. For each OLSRv2 interface of the router, include the 1411 message in a packet to be transmitted on that OLSRv2 1412 interface, as described in Section 8. This packet 1413 MAY contain other forwarded messages and/or messages 1414 generated by this router, including by other 1415 protocols using [RFC5444]. Forwarded messages MAY be 1416 jittered as described in [RFC5148]. The value of 1417 MAXJITTER used in jittering a forwarded message MAY 1418 be based on information in that message (in 1419 particular any INTERVAL_TIME or VALIDITY_TIME TLVs in 1420 that message) or otherwise SHOULD be with a maximum 1421 delay of F_MAXJITTER. A router MAY modify the jitter 1422 applied to a message in order to more efficiently 1423 combine messages in packets, as long as the maximum 1424 jitter is not exceeded. 1426 8. Packets and Messages 1428 The packet and message format used by OLSRv2 is defined in [RFC5444]. 1429 Except as otherwise noted, options defined in [RFC5444] may be freely 1430 used, in particular alternative formats defined by packet, message, 1431 Address Block and TLV flags. 1433 OLSRv2 defines and owns the TC Message Type. OLSRv2 also modifies 1434 HELLO messages (owned by [NHDP]) by adding TLVs to these messages 1435 when sent over OLSRv2 interfaces, and processes these HELLO messages, 1436 subsequent to their processing by NHDP. Extensions to OLSRv2 MAY 1437 define additional Message Types to be handled similarly to TC 1438 messages. 1440 Routers using OLSRv2 exchange information through messages. One or 1441 more messages sent by a router at the same time SHOULD be combined 1442 into a single packet. These messages may have originated at the 1443 sending router, or have originated at another router and are 1444 forwarded by the sending router. Messages with different originating 1445 routers MAY be combined for transmission within the same packet. 1446 Messages from other protocols defined using [RFC5444] MAY be combined 1447 for transmission within the same packet. 1449 The remainder of this section defines, within the framework of 1450 [RFC5444], Message Types and TLVs specific to OLSRv2. All references 1451 in this specification to TLVs that do not indicate a type extension, 1452 assume Type Extension = 0. TLVs in processed messages with a type 1453 extension which is neither zero as so assumed, nor a specifically 1454 indicated non-zero type extension, are ignored. 1456 8.1. HELLO Messages 1458 A HELLO message in OLSRv2 is generated as specified in [NHDP]. In 1459 addition, an OLSRv2 router MUST be able to modify such messages, 1460 prior to these being sent on an OLSRv2 interface, so that such HELLO 1461 messages: 1463 o MUST include TLV(s) with Type := MPR associated with all addresses 1464 that: 1466 * are included in the HELLO message associated with a TLV with 1467 Type = LINK_STATUS and Value = SYMMETRIC; AND 1469 * are included in a Neighbor Tuple with N_mpr = true. 1471 o MUST NOT include any TLVs with Type = MPR associated with any 1472 other addresses. 1474 o MAY include a message TLV with Type := MPR_WILLING, indicating the 1475 router's willingness to be selected as an MPR. 1477 An OLSRv2 router MUST also be able to process any HELLO message 1478 received on an OLSRv2 interface, subsequent to the processing 1479 specified in [NHDP]. 1481 8.1.1. HELLO Message TLVs 1483 In a HELLO message, a router MUST include an MPR_WILLING Message TLV 1484 as specified in Table 1, unless WILLINGNESS = WILL_DEFAULT (in which 1485 case it MAY be included). A router MUST NOT include more than one 1486 MPR_WILLING Message TLV. 1488 +-------------+--------------+--------------------------------------+ 1489 | Type | Value Length | Value | 1490 +-------------+--------------+--------------------------------------+ 1491 | MPR_WILLING | 1 octet | Router parameter WILLINGNESS; unused | 1492 | | | bits (based on the maximum | 1493 | | | willingness value WILL_ALWAYS) are | 1494 | | | RESERVED and SHOULD be set to zero. | 1495 +-------------+--------------+--------------------------------------+ 1497 Table 1 1499 If a router does not advertise an MPR_WILLING TLV in a HELLO message, 1500 then the router MUST be assumed to have WILLINGNESS equal to 1501 WILL_DEFAULT. 1503 8.1.2. HELLO Message Address Block TLVs 1505 In a HELLO message, a router MAY include MPR Address Block TLV(s) as 1506 specified in Table 2. 1508 +------+--------------+-------+ 1509 | Type | Value Length | Value | 1510 +------+--------------+-------+ 1511 | MPR | 0 octets | None. | 1512 +------+--------------+-------+ 1514 Table 2 1516 8.2. TC Messages 1518 A TC message MUST contain: 1520 o , and elements in its 1521 Message Header, as specified in [RFC5444]. 1523 o A element in its Message Header if the message 1524 contains a TLV with either Type = VALIDITY_TIME or Type = 1525 INTERVAL_TIME indicating more than one time value according to 1526 distance. (A TC message MAY contain even if it 1527 does not need to.) 1529 o A single Message TLV with Type := CONT_SEQ_NUM, and Type Extension 1530 := COMPLETE or Type Extension := INCOMPLETE, as specified in 1531 Section 8.2.1 (for complete and incomplete TC messages, 1532 respectively). 1534 o A Message TLV with Type := VALIDITY_TIME, as specified in 1535 [RFC5497]. The options included in [RFC5497] for representing 1536 zero and infinite times MUST NOT be used. 1538 o All of the router's addresses. These MUST be included in the 1539 message's Address Blocks, unless: 1541 * the router has a single interface, with a single address with 1542 maximum prefix length; AND 1544 * that address is the router's originator address. 1546 In this exceptional case, the address will be included as the 1547 message's originator address, and MAY be omitted from the 1548 message's Address Blocks. 1550 o TLV(s) with Type := LOCAL_IF and Value := UNSPEC_IF associated 1551 with all of the router's addresses. 1553 o If the TC message is complete, all addresses in the Advertised 1554 Address Set and all addresses in the Local Attached Network Set, 1555 the latter (only) with associated GATEWAY Address Block TLV(s), as 1556 specified in Section 8.2.2. 1558 A TC message MAY contain: 1560 o If the TC message is incomplete, any addresses in the Advertised 1561 Address Set and any addresses in the Local Attached Network Set, 1562 the latter (only) with associated GATEWAY Address Block TLV(s), as 1563 specified in Section 8.2.2. 1565 o A Message TLV with Type := INTERVAL_TIME, as specified in 1566 [RFC5497]. The options included in [RFC5497] for representing 1567 zero and infinite times MUST NOT be used. 1569 8.2.1. TC Message TLVs 1571 In a TC message, a router MUST include a single CONT_SEQ_NUM Message 1572 TLV, as specified in Table 3, and with Type Extension = COMPLETE or 1573 Type Extension = INCOMPLETE, according to whether the TC message is 1574 complete or incomplete. 1576 +--------------+--------------+-------------------------------------+ 1577 | Type | Value Length | Value | 1578 +--------------+--------------+-------------------------------------+ 1579 | CONT_SEQ_NUM | 2 octets | The ANSN contained in the | 1580 | | | Advertised Neighbor Set. | 1581 +--------------+--------------+-------------------------------------+ 1583 Table 3 1585 8.2.2. TC Message Address Block TLVs 1587 In a TC message, a router MAY include GATEWAY Address Block TLV(s) as 1588 specified in Table 4. 1590 +---------+--------------+-------------------------------------+ 1591 | Type | Value Length | Value | 1592 +---------+--------------+-------------------------------------+ 1593 | GATEWAY | 1 octet | Number of hops to attached network. | 1594 +---------+--------------+-------------------------------------+ 1596 Table 4 1598 GATEWAY Address Block TLV(s) MUST be associated with all attached 1599 network addresses, and MUST NOT be associated with any other 1600 addresses. 1602 9. HELLO Message Generation 1604 An OLSRv2 HELLO message is composed and generated as defined in 1605 [NHDP], with the following additions: 1607 o A Message TLV with Type := MPR_WILLING and Value := WILLINGNESS 1608 MUST be included, unless WILLINGNESS = WILL_DEFAULT (in which case 1609 it MAY be included). 1611 o For each address which is included in the message with an 1612 associated TLV with Type = LINK_STATUS and Value = SYMMETRIC, and 1613 is of an MPR (i.e. the address is in the N_neighbor_addr_list of a 1614 Neighbor Tuple with N_mpr = true), that address (including a 1615 different copy of that address, in the same or a different Address 1616 Block) MUST be associated with an Address Block TLV with Type := 1617 MPR. 1619 o For each address which is included in the message and is not 1620 associated with a TLV with Type = LINK_STATUS and Value = 1621 SYMMETRIC, or is not of an MPR (i.e. the address is not in the 1622 N_neighbor_addr_list of a Neighbor Tuple with N_mpr = true), that 1623 address (including different copies of that address, in the same 1624 or different Address Blocks) MUST NOT be associated with an 1625 Address Block TLV with Type := MPR. 1627 o An additional HELLO message MAY be sent when the router's set of 1628 MPRs changes, in addition to the cases specified in [NHDP], and 1629 subject to the same constraints. 1631 9.1. HELLO Message: Transmission 1633 HELLO messages are included in packets as specified in [RFC5444]. 1634 These packets may contain other messages, including TC messages. 1636 10. HELLO Message Processing 1638 All HELLO message processing, including determination of whether a 1639 message is invalid, considers only TLVs with Type Extension = 0. 1640 TLVs with any other type extension are ignored. All references to, 1641 for example, a TLV with Type = MPR_WILLING refer to a TLV with Type = 1642 MPR_WILLING and Type Extension = 0. 1644 In addition to the reasons specified in [NHDP], for discarding a 1645 HELLO message on reception, a HELLO message MUST NOT: 1647 o Have more than one TLV with Type = MPR_WILLING in its Message TLV 1648 Block, where TLVs have different Values. 1650 o Contain any address associated with a TLV with Type = MPR, where 1651 that address (including a different copy of that address, in the 1652 same or a different Address Block) which is not also associated 1653 with the single Value SYMMETRIC by a TLV with Type = LINK_STATUS 1654 or Type = OTHER_NEIGHB. 1656 Such a HELLO message MAY be discarded before processing. If it is 1657 not then all TLVs with the type(s) for which an error was indicated 1658 MUST be ignored (treated as not present) in the following processing. 1660 HELLO messages are first processed as specified in [NHDP]. The 1661 router MUST identify the Neighbor Tuple corresponding to the 1662 originator of the HELLO message (the "current Neighbor Tuple") and 1663 update its N_willingness as described in Section 10.1 and its 1664 N_mpr_selector as described in Section 10.2. Following these, the 1665 router MUST also perform the processing defined in Section 10.3. 1667 10.1. Updating Willingness 1669 N_willingness in the current Neighbor Tuple is updated as follows: 1671 1. If the HELLO message contains a Message TLV with Type = 1672 MPR_WILLING then N_willingness := the Value of that TLV; 1674 2. Otherwise, N_willingness := WILL_DEFAULT. 1676 10.2. Updating MPR Selectors 1678 N_mpr_selector is updated as follows: 1680 1. If a router finds any of its local addresses with an associated 1681 TLV with Type = MPR in the HELLO message (indicating that the 1682 originator router has selected the receiving router as an MPR) 1683 then, for the current Neighbor Tuple: 1685 * N_mpr_selector := true 1687 2. Otherwise, if a router finds any of its own addresses with an 1688 associated TLV with Type = LINK_STATUS and Value = SYMMETRIC in 1689 the HELLO message, then for the current Neighbor Tuple: 1691 * N_mpr_selector := false 1693 10.3. Symmetric 1-Hop and 2-Hop Neighborhood Changes 1695 A router MUST also perform the following: 1697 1. If N_symmetric of a Neighbor Tuple changes from true to false, 1698 for that Neighbor Tuple: 1700 * N_mpr_selector := false 1702 2. The set of MPRs of a router MUST be recalculated if: 1704 * a Link Tuple is added with L_status = SYMMETRIC, OR; 1706 * a Link Tuple with L_status = SYMMETRIC is removed, OR; 1708 * a Link Tuple with L_status = SYMMETRIC changes to having 1709 L_status = HEARD or L_status = LOST, OR; 1711 * a Link Tuple with L_status = HEARD or L_status = LOST changes 1712 to having L_status = SYMMETRIC, OR; 1714 * a 2-Hop Tuple is added or removed, OR; 1716 * the N_willingness of a Neighbor Tuple with N_symmetric = true 1717 changes from WILL_NEVER to any other value, OR; 1719 * the N_willingness of a Neighbor Tuple with N_symmetric = true 1720 and N_mpr = true changes to WILL_NEVER from any other value, 1721 OR; 1723 * the N_willingness of a Neighbor Tuple with N_symmetric = true 1724 and N_mpr = false changes to WILL_ALWAYS from any other value. 1726 3. Otherwise the set of MPRs of a router MAY be recalculated if the 1727 N_willingness of a Neighbor Tuple with N_symmetric = true changes 1728 in any other way; it SHOULD be recalculated if N_mpr = false and 1729 this is an increase in N_willingness or if N_mpr = true and this 1730 is a decrease in N_willingness. 1732 If the set of MPRs of a router is recalculated, this MUST be as 1733 described in Section 14. Before that calculation, the N_mpr of all 1734 Neighbor Tuples are set false. After that calculation the N_mpr of 1735 all Neighbor Tuples representing symmetric 1-hop neighbors which are 1736 chosen as MPRs, are set true. 1738 11. TC Message Generation 1740 A router with one or more OLSRv2 interfaces, and with a non-empty 1741 Advertised Neighbor Set or a non-empty Local Attached Network Set 1742 MUST generate TC messages. A router with an empty Advertised 1743 Neighbor Set and empty Local Attached Network Set SHOULD also 1744 generate "empty" TC messages for a period A_HOLD_TIME after it last 1745 generated a non-empty TC message. TC messages (non-empty and empty) 1746 are generated according to the following: 1748 1. The message originator address MUST be set to the router's 1749 originator address. 1751 2. The message hop count, if included, MUST be set to zero. 1753 3. The message hop limit MUST be set to a value greater than 1. A 1754 router MAY use the same hop limit TC_HOP_LIMIT in all TC 1755 messages, or use different values of the hop limit TC_HOP_LIMIT 1756 in TC messages, see Section 5.8. 1758 4. The message MUST contain a Message TLV with Type := CONT_SEQ_NUM 1759 and Value := ANSN from the Advertised Neighbor Set. If the TC 1760 message is complete then this Message TLV MUST have Type 1761 Extension := COMPLETE, otherwise it MUST have Type Extension := 1762 INCOMPLETE. 1764 5. The message MUST contain a Message TLV with Type := 1765 VALIDITY_TIME, as specified in [RFC5497]. If all TC messages are 1766 sent with the same hop limit then this TLV MUST have Value := 1767 T_HOLD_TIME. If TC messages are sent with different hop limits 1768 (more than one value of TC_HOP_LIMIT) then this TLV MUST specify 1769 times which vary with the number of hops distance appropriate to 1770 the chosen pattern of TC message hop limits, as specified in 1771 [RFC5497], these times SHOULD be appropriate multiples of 1772 T_HOLD_TIME. 1774 6. The message MAY contain a Message TLV with Type := INTERVAL_TIME, 1775 as specified in [RFC5497]. If all TC messages are sent with the 1776 same hop limit then this TLV MUST have Value := TC_INTERVAL. If 1777 TC messages are sent with different hop limits, then this TLV 1778 MUST specify times which vary with the number of hops distance 1779 appropriate to the chosen pattern of TC message hop limits, as 1780 specified in [RFC5497], these times SHOULD be appropriate 1781 multiples of TC_INTERVAL. 1783 7. Unless the router has a single interface, with a single address 1784 with maximum prefix length, and that address is the router's 1785 originator address, the message MUST contain all of the router's 1786 addresses (i.e. all addresses in an I_local_iface_addr_list) in 1787 its Address Blocks. 1789 8. All addresses of the router's interfaces that are included in an 1790 Address Block MUST each be associated with a TLV with Type := 1791 LOCAL_IF and Value := UNSPEC_IF. 1793 9. A complete message MUST include, and an incomplete message MAY 1794 include, in its Address Blocks: 1796 1. Each A_neighbor_addr from the Advertised Neighbor Set; 1798 2. AL_net_addr from each Local Attached Neighbor Tuple, each 1799 associated with a TLV with Type := GATEWAY and Value := 1800 AL_dist. 1802 11.1. TC Message: Transmission 1804 Complete TC messages are generated and transmitted periodically on 1805 all OLSRv2 interfaces, with a default interval between two 1806 consecutive TC transmissions by the same router of TC_INTERVAL. 1808 TC messages MAY be generated in response to a change of contents, 1809 indicated by a change in ANSN. In this case a router MAY send a 1810 complete TC message, and if so MAY re-start its TC message schedule. 1811 Alternatively a router MAY send an incomplete TC message with at 1812 least the new content in its Address Blocks. Note that a router 1813 cannot report removal of advertised content using an incomplete TC 1814 message. 1816 When sending a TC message in response to a change of contents, a 1817 router must respect a minimum interval of TC_MIN_INTERVAL between 1818 generated TC messages. Sending an incomplete TC message MUST NOT 1819 cause the interval between complete TC messages to be increased, and 1820 thus a router MUST NOT send an incomplete TC message if within 1821 TC_MIN_INTERVAL of the next scheduled complete TC message. 1823 The generation of TC messages, whether scheduled or triggered by a 1824 change of contents MAY be jittered as described in [RFC5148]. The 1825 values of MAXJITTER used SHOULD be: 1827 o TP_MAXJITTER for periodic TC message generation; 1828 o TT_MAXJITTER for responsive TC message generation. 1830 TC messages are included in packets as specified in [RFC5444]. These 1831 packets MAY contain other messages, including HELLO messages and TC 1832 messages with different originator addresses. TC messages are 1833 forwarded according to the specification in Section 7.3. 1835 12. TC Message Processing 1837 On receiving a TC message, a router MUST first check if the message 1838 is invalid for processing by this router, as defined in Section 12.1. 1839 Otherwise the receiving router MUST update its appropriate Interface 1840 Information Base and its Router Information Base as specified in 1841 Section 12.2. 1843 All TC message processing, including determination of whether a 1844 message is invalid, unless otherwise noted considers only TLVs with 1845 Type Extension = 0. TLVs with any other type extension (or any 1846 unmentioned type extension when other type extensions are considered) 1847 are ignored. All references to, for example, a TLV with Type = 1848 VALIDITY_TIME refer to a TLV with Type = VALIDITY_TIME and Type 1849 Extension = 0. 1851 12.1. Invalid Message 1853 A received TC message is invalid for processing by this router if any 1854 of the following conditions are true. 1856 o The Message Header does not include an originator address, a 1857 message sequence number, and a hop limit. 1859 o The Message Header a hop count, and contains a multi-value TLV 1860 with Type = VALIDITY_TIME or Type == INTERVAL_TIME, as defined in 1861 [RFC5497]. 1863 o The message does not have a single TLV with Type = VALIDITY_TIME 1864 in its Message TLV Block. 1866 o The message has more than one TLV with Type = INTERVAL_TIME in its 1867 Message TLV Block. 1869 o The message does not have a TLV with Type = CONT_SEQ_NUM and Type 1870 Extension = COMPLETE or Type Extension = INCOMPLETE in its Message 1871 TLV Block. 1873 o The message has more than one TLV with Type = CONT_SEQ_NUM and 1874 Type Extension = COMPLETE or Type Extension = INCOMPLETE in its 1875 Message TLV Block, and these do not have the same type extension 1876 and the same Value. 1878 o The message has any Address Block TLV(s) with Type = LOCAL_IF and 1879 any single Value(s) which are not equal to UNSPEC_IF. 1881 o Any address associated with a TLV with Type = LOCAL_IF is one of 1882 the receiving router's current or recently used addresses (i.e. is 1883 in any I_local_iface_addr_list in the Local Interface Set or is 1884 equal to any IR_local_iface_addr in the Removed Interface Address 1885 Set). 1887 o Any address (including different copies of an address, in the same 1888 or different Address Blocks) is associated with more than one 1889 single Value by one or more TLV(s) with Type = GATEWAY. 1891 A router MAY recognize additional reasons for identifying that a 1892 message is invalid. An invalid message MUST be silently discarded, 1893 without updating the router's Information Bases. 1895 12.2. Initial TC Message Processing 1897 When, according to Section 7.2, a TC message is to be "processed 1898 according to its type", this means that: 1900 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 1901 and Type Extension = COMPLETE, then processing according to 1902 Section 12.3 and then according to Section 12.4 is carried out. 1904 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 1905 and Type Extension = INCOMPLETE, then only processing according to 1906 Section 12.3 is carried out. 1908 For the purposes of this section: 1910 o "originator address" refers to the originator address in the TC 1911 Message Header. 1913 o "validity time" is calculated from a VALIDITY_TIME Message TLV in 1914 the TC message according to the specification in [RFC5497]. All 1915 information in the TC message has the same validity time. 1917 o "ANSN" is defined as being the Value of a Message TLV with Type = 1918 CONT_SEQ_NUM. 1920 o "sending address list" refers to the list of addresses in all 1921 Address Blocks which have associated TLV(s) with Type = LOCAL_IF 1922 and Value = UNSPEC_IF. If the sending address list is otherwise 1923 empty, then the message's originator address is added to the 1924 sending address list, with maximum prefix length. 1926 o Comparisons of sequence numbers are carried out as specified in 1927 Section 18. 1929 12.3. Initial TC Message Processing 1931 The TC message is processed as follows: 1933 1. The Advertising Remote Router Set is updated according to 1934 Section 12.3.1; if the TC message is indicated as discarded in 1935 that processing then the following steps are not carried out. 1937 2. The Topology Set is updated according to Section 12.3.2. 1939 3. The Attached Network Set is updated according to Section 12.3.3. 1941 12.3.1. Populating the Advertising Remote Router Set 1943 The router MUST update its Advertising Remote Router Set as follows: 1945 1. If there is an Advertising Remote Router Tuple with: 1947 * AR_orig_addr = originator address; AND 1949 * AR_seq_number > ANSN 1951 then the TC message MUST be discarded. 1953 2. Otherwise: 1955 1. If there is no Advertising Remote Router Tuple such that: 1957 + AR_orig_addr = originator address; 1959 then create an Advertising Remote Router Tuple with: 1961 + AR_orig_addr := originator address. 1963 2. This Advertising Remote Router Tuple (existing or new, the 1964 "current tuple") is then modified as follows: 1966 + AR_seq_number := ANSN; 1968 + AR_time := current time + validity time. 1970 + AR_addr_list := sending address list 1972 3. For each other Advertising Remote Router Tuple (with a 1973 different AR_orig_addr, the "other tuple") whose AR_addr_list 1974 contains any address in the AR_addr_list of the current 1975 tuple: 1977 1. remove all Topology Tuples with T_orig_addr = 1978 AR_orig_addr of the other tuple; 1980 2. remove all Attached Network Tuples with AN_orig_addr = 1981 AR_orig_addr of the other tuple; 1983 3. remove the other tuple. 1985 12.3.2. Populating the Topology Set 1987 The router MUST update its Topology Set as follows: 1989 1. For each address (henceforth advertised address) in an Address 1990 Block that does not have an associated TLV with Type = LOCAL_IF, 1991 or an associated TLV with Type = GATEWAY: 1993 1. If there is no Topology Tuple such that: 1995 + T_dest_addr = advertised address; AND 1997 + T_orig_addr = originator address 1999 then create a new Topology Tuple with: 2001 + T_dest_addr := advertised address; 2003 + T_orig_addr := originator address. 2005 2. This Topology Tuple (existing or new) is then modified as 2006 follows: 2008 + T_seq_number := ANSN; 2010 + T_time := current time + validity time. 2012 12.3.3. Populating the Attached Network Set 2014 The router MUST update its Attached Network Set as follows: 2016 1. For each address (henceforth network address) in an Address Block 2017 that does not have an associated TLV with Type = LOCAL_IF, and 2018 does have an associated TLV with Type = GATEWAY: 2020 1. If there is no Attached Network Tuple such that: 2022 + AN_net_addr = network address; AND 2024 + AN_orig_addr = originator address 2026 then create a new Attached Network Tuple with: 2028 + AN_net_addr := network address; 2030 + AN_orig_addr := originator address 2032 2. This Attached Network Tuple (existing or new) is then 2033 modified as follows: 2035 + AN_dist := the Value of the associated GATEWAY TLV; 2037 + AN_seq_number := ANSN; 2039 + AN_time := current time + validity time. 2041 12.4. Completing TC Message Processing 2043 The TC message is processed as follows: 2045 1. The Topology Set is updated according to Section 12.4.1. 2047 2. The Attached Network Set is updated according to Section 12.4.2. 2049 12.4.1. Purging the Topology Set 2051 The Topology Set MUST be updated as follows: 2053 1. Any Topology Tuples with: 2055 * T_orig_addr = originator address; AND 2057 * T_seq_number < ANSN 2059 MUST be removed. 2061 12.4.2. Purging the Attached Network Set 2063 The Attached Network Set MUST be updated as follows: 2065 1. Any Attached Network Tuples with: 2067 * AN_orig_addr = originator address; AND 2069 * AN_seq_number < ANSN 2071 MUST be removed. 2073 13. Information Base Changes 2075 1. The Originator Set in the Local Information Base MUST be updated 2076 when the router changes originator address. If there is no 2077 Originator Tuple with: 2079 * O_orig_addr = old originator address 2081 then create an Originator Tuple with: 2083 * O_orig_addr := old originator address 2085 This Originator Tuple (existing or new) is then modified as 2086 follows: 2088 * O_time := current time + O_HOLD_TIME 2090 2. The Advertised Neighbor Set in the Topology Information Base MUST 2091 be changed when the Neighbor Set changes. The following changes 2092 are required: 2094 1. If an address in an N_neighbor_addr_list in a Neighbor Tuple 2095 is removed (including when that Neighbor Tuple is removed) 2096 and that address is also an A_neighbor_addr in an Advertised 2097 Neighbor Tuple, then that Advertised Neighbor Tuple MUST be 2098 removed. 2100 2. If an address is added to an N_neighbor_addr_list in a 2101 Neighbor Tuple with N_mpr_selector = true (including when 2102 such a Neighbor Tuple is added) or for each address in an 2103 N_neighbor_addr_list in a Neighbor Tuple whose N_mpr_selector 2104 has changed from false to true, and that address is not 2105 already an A_neighbor_addr in an Advertised Neighbor Tuple, 2106 then an Advertised Neighbor Tuple MUST be added to the 2107 Advertised Neighbor Set with A_neighbor_addr equal to that 2108 address. 2110 Other changes to the Advertised Neighbor Set MAY be made when the 2111 Neighbor Set changes, in particular if the N_mpr_selector of a 2112 Neighbor Tuple changes from true to false, then the Advertised 2113 Neighbor Tuples whose A_neighbor_addr are addresses in the 2114 N_neighbor_addr_list of that Neighbor Tuple MAY be removed. 2116 3. The Topology Set and the Attached Network Set in the Topology 2117 Information Base MUST be changed when an Advertising Remote 2118 Router Tuple expires (AR_time is reached). The following changes 2119 are required before the Advertising Remote Router Tuple is 2120 removed: 2122 1. All Topology Tuples with: 2124 + T_orig_addr = AR_orig_addr of the Advertising Remote 2125 Router Tuple 2127 are removed. 2129 2. All Attached Network Tuples with: 2131 + AN_orig_addr = AR_orig_addr of the Advertising Remote 2132 Router Tuple 2134 are removed. 2136 14. Selecting MPRs 2138 Each router MUST select, from among its willing symmetric 1-hop 2139 neighbors, a subset of routers as MPRs. MPRs are used to flood 2140 control messages from a router into the network, while reducing the 2141 number of retransmissions that will occur in a region. Thus, the 2142 concept of MPR flooding is an optimization of a classical flooding 2143 mechanism. MPRs MAY also be used to reduce the shared topology 2144 information in the network. Consequently, while it is not essential 2145 that the set of MPRs is minimal, keeping the number of MPRs small 2146 ensures that the overhead of OLSRv2 is kept at a minimum. 2148 A router MUST select MPRs for each of its OLSRv2 interfaces, but then 2149 forms the union of those sets as its single set of MPRs. This union 2150 MUST include all symmetric 1-hop neighbors with willingness 2151 WILL_ALWAYS. Only this overall set of MPRs is relevant, the recorded 2152 and used MPR relationship is one of routers, not interfaces. Routers 2153 MAY select their MPRs by any process which satisfies the conditions 2154 which follow. Routers can freely interoperate whether they use the 2155 same or different MPR selection algorithms. 2157 For each OLSRv2 interface a router MUST select a set of MPRs. This 2158 set MUST have the properties that: 2160 o All of the selected MPRs are willing symmetric 1-hop neighbors, 2161 AND; 2163 o If the selecting router sends a message on that OLSRv2 interface, 2164 and that message is successfully forwarded by all of the selected 2165 MPRs for that interface, then all symmetric strict 2-hop neighbors 2166 of the selecting router through that OLSRv2 interface will receive 2167 that message on a symmetric link. 2169 Note that it is always possible to select a valid set of MPRs. The 2170 set of all willing symmetric 1-hop neighbors of a router is a 2171 (maximal) valid set of MPRs for that router. However a router SHOULD 2172 NOT select a symmetric 1-hop neighbor with Willingness != WILL_ALWAYS 2173 as an MPR if there are no symmetric strict 2-hop neighbors with a 2174 symmetric link to that symmetric 1-hop neighbor. Thus a router with 2175 no symmetric 1-hop neighbors with willingness WILL_ALWAYS and with no 2176 symmetric strict 2-hop neighbors SHOULD NOT select any MPRs. 2178 A router MAY select its MPRs for each OLSRv2 interface independently, 2179 or it MAY coordinate its MPR selections across its OLSRv2 interfaces, 2180 as long as the required condition is satisfied for each OLSRv2 2181 interface. Each router MAY select its MPRs independently from the 2182 MPR selection by other routers, or it MAY, for example, give 2183 preference to routers that either are, or are not, already selected 2184 as MPRs by other routers. 2186 When selecting MPRs for each OLSRv2 interface independently, this MAY 2187 be done using information from the Link Set and 2-Hop Set of that 2188 OLSRv2 interface, and the Neighbor Set of the router (specifically 2189 the N_willingness elements). 2191 The selection of MPRs (overall, not per OLSRv2 interface) is recorded 2192 in the Neighbor Set of the router (using the N_mpr elements). A 2193 selected MPR MUST be a willing symmetric 1-hop neighbor (i.e. the 2194 corresponding N_symmetric = true, and the corresponding N_willingness 2195 != WILL_NEVER). 2197 A router MUST recalculate its MPRs whenever the currently selected 2198 set of MPRs does not still satisfy the required conditions. It MAY 2199 recalculate its MPRs if the current set of MPRs is still valid, but 2200 could be more efficient. It is sufficient to recalculate a router's 2201 MPRs when there is a change to any of the router's Link Sets 2202 affecting the symmetry of any link (addition or removal of a Link 2203 Tuple with L_status = SYMMETRIC, or change of any L_status to or from 2204 SYMMETRIC), any change to any of the router's 2-Hop Sets, or a change 2205 of the N_willingness (to or from WILL_NEVER or to WILL_ALWAYS is 2206 sufficient) of any Neighbor Tuple with N_symmetric = true. 2208 An algorithm that creates a set of MPRs that satisfies the required 2209 conditions is given in Appendix B. 2211 15. Populating Derived Sets 2213 The Relay Sets and the Advertised Neighbor Set of a router are 2214 denoted derived sets, since updates to these sets are not directly a 2215 function of message exchanges, but rather are derived from updates to 2216 other sets, in particular to the MPR selector status of other routers 2217 recorded in the Neighbor Set. 2219 15.1. Populating the Relay Set 2221 The Relay Set for an OLSRv2 interface contains the set of OLSRv2 2222 interface addresses of those symmetric 1-hop neighbors for which this 2223 OLSRv2 interface is to relay broadcast traffic. This set MUST 2224 contain only addresses of OLSRv2 interfaces with which this OLSRv2 2225 interface has a symmetric link. This set MUST include all such 2226 addresses of all such OLSRv2 interfaces of routers which are MPR 2227 selectors of this router. 2229 The Relay Set for an OLSRv2 interface of this router is thus created 2230 by: 2232 1. For each Link Tuple in the Link Set for this OLSRv2 interface 2233 with L_status = SYMMETRIC, and the corresponding Neighbor Tuple 2234 with N_neighbor_addr_list containing L_neighbor_iface_addr_list: 2236 1. All addresses from L_neighbor_iface_addr_list MUST be 2237 included in the Relay Set of this OLSRv2 interface if 2238 N_mpr_selector = true, and otherwise MAY be so included. 2240 15.2. Populating the Advertised Neighbor Set 2242 The Advertised Neighbor Set of a router contains all addresses of 2243 those symmetric 1-hop neighbors to which the router advertises a link 2244 in its TC messages. This set MUST include all addresses in all MPR 2245 selector of this router. 2247 The Advertised Neighbor Set for this router is thus created by: 2249 1. For each Neighbor Tuple with N_symmetric = true: 2251 1. All addresses from N_neighbor_addr_list MUST be included in 2252 the Advertised Neighbor Set if N_mpr_selector = true, and 2253 otherwise MAY be so included. 2255 Whenever address(es) are added to or removed from the Advertised 2256 Neighbor Set, its ANSN MUST be incremented. 2258 16. Routing Set Calculation 2260 The Routing Set of a router is populated with Routing Tuples that 2261 represent paths from that router to all destinations in the network. 2262 These paths are calculated based on the Network Topology Graph, which 2263 is constructed from information in the Information Bases, obtained 2264 via HELLO and TC message exchange. 2266 16.1. Network Topology Graph 2268 The Network Topology Graph is formed from information from the 2269 router's Link Sets, Neighbor Set, Topology Set and Attached Network 2270 Set. The Network Topology Graph SHOULD also use information from the 2271 router's 2-Hop Sets. The Network Topology Graph forms that router's 2272 topological view of the network in form of a directed graph, 2273 containing the following arcs: 2275 o Local symmetric links - all arcs X -> Y such that: 2277 * X is an address in the I_local_iface_addr_list of a Local 2278 Interface Tuple of this router, AND; 2280 * Y is an address in the L_neighbor_iface_addr_list of a Link 2281 Tuple in the corresponding (to the OLSRv2 interface of that 2282 I_local_iface_addr_list) Link Set which has L_status = 2283 SYMMETRIC. 2285 o 2-hop symmetric links - all arcs Y -> Z such that: 2287 * Y is an address in the L_neighbor_iface_addr_list of a Link 2288 Tuple, in any of the router's Link Sets, which has L_status = 2289 SYMMETRIC, AND; 2291 * the Neighbor Tuple with Y in its N_neighbor_addr_list has 2292 N_willingness not equal to WILL_NEVER, AND; 2294 * Z is the N2_2hop_addr of a 2-Hop Tuple in the 2-Hop Set 2295 corresponding to the OLSRv2 interface of the chosen Link Set. 2297 o Advertised symmetric links - all arcs U -> V such that there 2298 exists a Topology Tuple and a corresponding Advertising Remote 2299 Router Tuple (i.e. with AR_orig_addr = T_orig_addr) with: 2301 * U is in the AR_addr_list of the Advertising Remote Router 2302 Tuple, AND; 2304 * V is the T_dest_addr of the Topology Tuple. 2306 o Symmetric 1-hop neighbor addresses - all arcs Y -> W such that: 2308 * Y is, and W is not, an address in the 2309 L_neighbor_iface_addr_list of a Link Tuple, in any of the 2310 router's Link Sets, which has L_status = SYMMETRIC, AND; 2312 * W and Y are included in the same N_neighbor_addr_list (i.e. the 2313 one in the Neighbor Tuple whose N_neighbor_addr_list contains 2314 the L_neighbor_iface_addr_list that includes Y). 2316 o Attached network addresses - all arcs U -> T such that there 2317 exists an Attached Network Tuple and a corresponding Advertising 2318 Remote Router Tuple (i.e. with AR_orig_addr = AN_orig_addr) with: 2320 * U is in the AR_addr_list of the Advertising Remote Router 2321 Tuple, AND; 2323 * T is the AN_net_addr of the Attached Network Tuple. 2325 All links in the first three cases above have a hop count of one, the 2326 symmetric 1-hop neighbor addresses have a hop count of zero, and the 2327 attached network addresses have a hop count given by the appropriate 2328 value of AN_dist. 2330 16.2. Populating the Routing Set 2332 The Routing Set MUST contain the shortest paths for all destinations 2333 from all local OLSRv2 interfaces using the Network Topology Graph. 2334 This calculation MAY use any algorithm, including any means of 2335 choosing between paths of equal length. 2337 Using the notation of Section 16.1, each path will have as its first 2338 arc a local symmetric link X -> Y. There will be a path for each 2339 terminating Y, Z, V, W and T which can be connected to local OLSRv2 2340 address X using the indicated arcs. The corresponding Routing Tuple 2341 for this path will have: 2343 o R_dest_addr := the terminating Y, Z, V, W or T; 2345 o R_next_iface_addr := the first arc's Y; 2347 o R_dist := the total hop count of the path; 2349 o R_local_iface_addr := the first arc's X. 2351 An example algorithm for calculating the Routing Set of a router is 2352 given in Appendix C. 2354 16.3. Routing Set Updates 2356 The Routing Set MUST be updated when changes in the Neighborhood 2357 Information Base or the Topology Information Base indicate a change 2358 of the known symmetric links and/or attached networks in the MANET. 2359 It is sufficient to consider only changes which affect at least one 2360 of: 2362 o The Link Set of any OLSRv2 interface, and to consider only Link 2363 Tuples which have, or just had, L_status = SYMMETRIC (including 2364 removal of such Link Tuples). 2366 o The Neighbor Set of the router, and to consider only Neighbor 2367 Tuples that have, or just had, N_symmetric = true. 2369 o The 2-Hop Set of any OLSRv2 interface. 2371 o The Advertising Remote Router Set of the router. 2373 o The Topology Set of the router. 2375 o The Attached Network Set of the router. 2377 Updates to the Routing Set do not generate or trigger any messages to 2378 be transmitted. The state of the Routing Set SHOULD, however, be 2379 reflected in the IP routing table by adding and removing entries from 2380 the IP routing table as appropriate. 2382 17. Proposed Values for Parameters and Constants 2384 OLSRv2 uses all parameters and constants defined in [NHDP] and 2385 additional parameters and constants defined in this document. All 2386 but one (RX_HOLD_TIME) of these additional parameters are router 2387 parameters as defined in [NHDP]. These proposed values of the 2388 additional parameters are appropriate to the case where all 2389 parameters (including those defined in [NHDP]) have a single value. 2390 Proposed values for parameters defined in [NHDP] are given in that 2391 document. 2393 17.1. Local History Time Parameters 2395 o O_HOLD_TIME := 30 seconds 2397 17.2. Message Interval Parameters 2399 o TC_INTERVAL := 5 seconds 2400 o TC_MIN_INTERVAL := TC_INTERVAL/4 2402 17.3. Advertised Information Validity Time Parameters 2404 o T_HOLD_TIME := 3 x TC_INTERVAL 2406 o A_HOLD_TIME := T_HOLD_TIME 2408 17.4. Received Message Validity Time Parameters 2410 o RX_HOLD_TIME := 30 seconds 2412 o P_HOLD_TIME := 30 seconds 2414 o F_HOLD_TIME := 30 seconds 2416 17.5. Jitter Time Parameters 2418 o TP_MAXJITTER := HP_MAXJITTER 2420 o TT_MAXJITTER := HT_MAXJITTER 2422 o F_MAXJITTER := TT_MAXJITTER 2424 17.6. Hop Limit Parameter 2426 o TC_HOP_LIMIT := 255 2428 17.7. Willingness Parameter and Constants 2430 o WILLINGNESS := WILL_DEFAULT 2432 o WILL_NEVER := 0 2434 o WILL_DEFAULT := 3 2436 o WILL_ALWAYS := 7 2438 18. Sequence Numbers 2440 Sequence numbers are used in OLSRv2 with the purpose of discarding 2441 "old" information, i.e. messages received out of order. However with 2442 a limited number of bits for representing sequence numbers, wrap- 2443 around (that the sequence number is incremented from the maximum 2444 possible value to zero) will occur. To prevent this from interfering 2445 with the operation of OLSRv2, the following MUST be observed when 2446 determining the ordering of sequence numbers. 2448 The term MAXVALUE designates in the following one more than the 2449 largest possible value for a sequence number. For a 16 bit sequence 2450 number (as are those defined in this specification) MAXVALUE is 2451 65536. 2453 The sequence number S1 is said to be "greater than" the sequence 2454 number S2 if: 2456 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 2458 o S2 > S1 AND S2 - S1 > MAXVALUE/2 2460 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 2461 cannot be determined. In this case, which should not occur, either 2462 ordering may be assumed. 2464 Thus when comparing two messages, it is possible - even in the 2465 presence of wrap-around - to determine which message contains the 2466 most recent information. 2468 19. IANA Considerations 2470 19.1. Message Types 2472 This specification defines one Message Type, to be allocated from the 2473 0-223 range of the "Message Types" namespace defined in [RFC5444], as 2474 specified in Table 5. 2476 +------+------+-----------------------------------------+ 2477 | Name | Type | Description | 2478 +------+------+-----------------------------------------+ 2479 | TC | TBD1 | Topology Control (MANET-wide signaling) | 2480 +------+------+-----------------------------------------+ 2482 Table 5 2484 19.2. Message TLV Types 2486 This specification defines two Message TLV Types, which must be 2487 allocated from the "Message TLV Types" namespace defined in 2488 [RFC5444]. IANA are requested to make allocations in the 8-127 range 2489 for these types. This will create two new type extension registries 2490 with assignments as specified in Table 6 and Table 7. Specifications 2491 of these TLVs are in Section 8.1.1 and Section 8.2.1. 2493 +-------------+------+-----------+----------------------------------+ 2494 | Name | Type | Type | Description | 2495 | | | extension | | 2496 +-------------+------+-----------+----------------------------------+ 2497 | MPR_WILLING | TBD2 | 0 | Specifies the originating | 2498 | | | | router's willingness to act as a | 2499 | | | | relay and to partake in network | 2500 | | | | formation | 2501 | Unassigned | TBD2 | 1-255 | Expert Review | 2502 +-------------+------+-----------+----------------------------------+ 2504 Table 6 2506 +--------------+------+----------------+----------------------------+ 2507 | Name | Type | Type extension | Description | 2508 +--------------+------+----------------+----------------------------+ 2509 | CONT_SEQ_NUM | TBD3 | 0 (COMPLETE) | Specifies a content | 2510 | | | | sequence number for this | 2511 | | | | complete message | 2512 | CONT_SEQ_NUM | TBD3 | 1 (INCOMPLETE) | Specifies a content | 2513 | | | | sequence number for this | 2514 | | | | incomplete message | 2515 | Unassigned | TBD3 | 2-255 | Expert Review | 2516 +--------------+------+----------------+----------------------------+ 2518 Table 7 2520 Type extensions indicated as Expert Review SHOULD be allocated as 2521 described in [RFC5444], based on Expert Review as defined in 2522 [RFC5226]. 2524 19.3. Address Block TLV Types 2526 This specification defines two Address Block TLV Types, which must be 2527 allocated from the "Address Block TLV Types" namespace defined in 2528 [RFC5444]. IANA are requested to make allocations in the 8-127 range 2529 for these types. This will create two new type extension registries 2530 with assignments as specified in Table 8 and Table 9. Specifications 2531 of these TLVs are in Section 8.1.2 and Section 8.2.2. 2533 +------------+------+-----------+-----------------------------------+ 2534 | Name | Type | Type | Description | 2535 | | | extension | | 2536 +------------+------+-----------+-----------------------------------+ 2537 | MPR | TBD4 | 0 | Specifies that a given address is | 2538 | | | | of a router selected as an MPR | 2539 | Unassigned | TBD4 | 1-255 | Expert Review | 2540 +------------+------+-----------+-----------------------------------+ 2542 Table 8 2544 +------------+------+-----------+-----------------------------------+ 2545 | Name | Type | Type | Description | 2546 | | | extension | | 2547 +------------+------+-----------+-----------------------------------+ 2548 | GATEWAY | TBD5 | 0 | Specifies that a given address is | 2549 | | | | reached via a gateway on the | 2550 | | | | originating router | 2551 | Unassigned | TBD5 | 1-255 | Expert Review | 2552 +------------+------+-----------+-----------------------------------+ 2554 Table 9 2556 Type extensions indicated as Expert Review SHOULD be allocated as 2557 described in [RFC5444], based on Expert Review as defined in 2558 [RFC5226]. 2560 The Address Block TLV with Type = LOCAL_IF defined in [NHDP] is 2561 extended to also permit inclusion of the Value UNSPEC_IF = 2, 2562 representing a local address which may or may not be that of the 2563 interface on which this message is transmitted. 2565 20. Security Considerations 2567 Currently, OLSRv2 does not specify any special security measures. As 2568 a proactive routing protocol, OLSRv2 makes a target for various 2569 attacks. The various possible vulnerabilities are discussed in this 2570 section. 2572 20.1. Confidentiality 2574 Being a proactive protocol, OLSRv2 periodically MPR floods 2575 topological information to all routers in the network. Hence, if 2576 used in an unprotected wireless network, the network topology is 2577 revealed to anyone who listens to OLSRv2 control messages. 2579 In situations where the confidentiality of the network topology is of 2580 importance, regular cryptographic techniques, such as exchange of 2581 OLSRv2 control traffic messages encrypted by PGP [RFC4880] or 2582 encrypted by some shared secret key, can be applied to ensure that 2583 control traffic can be read and interpreted by only those authorized 2584 to do so. 2586 20.2. Integrity 2588 In OLSRv2, each router is injecting topological information into the 2589 network through transmitting HELLO messages and, for some routers, TC 2590 messages. If some routers for some reason, malicious or malfunction, 2591 inject invalid control traffic, network integrity may be compromised. 2592 Therefore, message authentication is recommended. 2594 Different such situations may occur, for instance: 2596 1. a router generates TC messages, advertising links to non-neighbor 2597 routers; 2599 2. a router generates TC messages, pretending to be another router; 2601 3. a router generates HELLO messages, advertising non-neighbor 2602 routers; 2604 4. a router generates HELLO messages, pretending to be another 2605 router; 2607 5. a router forwards altered control messages; 2609 6. a router does not forward control messages; 2611 7. a router does not select multipoint relays correctly; 2613 8. a router forwards broadcast control messages unaltered, but does 2614 not forward unicast data traffic; 2616 9. a router "replays" previously recorded control traffic from 2617 another router. 2619 Authentication of the originator router for control messages (for 2620 situations 2, 4 and 5) and on the individual links announced in the 2621 control messages (for situations 1 and 3) may be used as a 2622 countermeasure. However to prevent routers from repeating old (and 2623 correctly authenticated) information (situation 9) temporal 2624 information is required, allowing a router to positively identify 2625 such delayed messages. 2627 In general, digital signatures and other required security 2628 information may be transmitted as a separate OLSRv2 Message Type, or 2629 signatures and security information may be transmitted within the 2630 OLSRv2 HELLO and TC messages, using the TLV mechanism. Either option 2631 permits that "secured" and "unsecured" routers can coexist in the 2632 same network, if desired, 2634 Specifically, the authenticity of entire OLSRv2 control packets can 2635 be established through employing IPsec authentication headers, 2636 whereas authenticity of individual links (situations 1 and 3) require 2637 additional security information to be distributed. 2639 An important consideration is that all control messages in OLSRv2 are 2640 transmitted either to all routers in the neighborhood (HELLO 2641 messages) or broadcast to all routers in the network (TC messages). 2643 For example, a control message in OLSRv2 is always a point-to- 2644 multipoint transmission. It is therefore important that the 2645 authentication mechanism employed permits that any receiving router 2646 can validate the authenticity of a message. As an analogy, given a 2647 block of text, signed by a PGP private key, then anyone with the 2648 corresponding public key can verify the authenticity of the text. 2650 20.3. Interaction with External Routing Domains 2652 OLSRv2 does, through the use of TC messages, provide a basic 2653 mechanism for injecting external routing information to the OLSRv2 2654 domain. Appendix A also specifies that routing information can be 2655 extracted from the topology table or the routing table of OLSRv2 and, 2656 potentially, injected into an external domain if the routing protocol 2657 governing that domain permits. 2659 Other than as described in Appendix A, when operating routers 2660 connecting OLSRv2 to an external routing domain, care MUST be taken 2661 not to allow potentially insecure and untrustworthy information to be 2662 injected from the OLSRv2 domain to external routing domains. Care 2663 MUST be taken to validate the correctness of information prior to it 2664 being injected as to avoid polluting routing tables with invalid 2665 information. 2667 A recommended way of extending connectivity from an existing routing 2668 domain to an OLSRv2 routed MANET is to assign an IP prefix (under the 2669 authority of the routers/gateways connecting the MANET with the 2670 exiting routing domain) exclusively to the OLSRv2 MANET area, and to 2671 configure the gateways statically to advertise routes to that IP 2672 sequence to routers in the existing routing domain. 2674 21. Contributors 2676 This specification is the result of the joint efforts of the 2677 following contributors -- listed alphabetically. 2679 o Cedric Adjih, INRIA, France, 2681 o Emmanuel Baccelli, INRIA , France, 2683 o Thomas Heide Clausen, LIX, France, 2685 o Justin Dean, NRL, USA, 2687 o Christopher Dearlove, BAE Systems, UK, 2688 2690 o Satoh Hiroki, Hitachi SDL, Japan, 2692 o Philippe Jacquet, INRIA, France, 2694 o Monden Kazuya, Hitachi SDL, Japan, 2696 o Kenichi Mase, Niigata University, Japan, 2698 o Ryuji Wakikawa, KEIO University, Japan, 2700 22. Acknowledgments 2702 The authors would like to acknowledge the team behind OLSRv1, 2703 specified in RFC3626, including Anis Laouiti (INT, Paris), Pascale 2704 Minet (INRIA, France), Laurent Viennot (INRIA, France), and Amir 2705 Qayyum (M.A. Jinnah University, Islamabad) for their contributions. 2707 The authors would like to gratefully acknowledge the following people 2708 for intense technical discussions, early reviews and comments on the 2709 specification and its components (listed alphabetically): Khaldoun Al 2710 Agha (LRI), Song-Yean Cho (LIX), Alan Cullen (BAE Systems), Louise 2711 Lamont (CRC), Li Li (CRC), Joe Macker (NRL), Richard Ogier (SRI), 2712 Charles E. Perkins (WiChorus), Shubhranshu Singh (Samsung AIT), and 2713 the entire IETF MANET working group. 2715 23. References 2717 23.1. Normative References 2719 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2720 Requirement Levels", RFC 2119, BCP 14, March 1997. 2722 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 2723 considerations in MANETs", RFC 5148, February 2008. 2725 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 2726 IANA Considerations Section in RFCs", RFC 5226, BCP 26, 2727 May 2008. 2729 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 2730 "Generalized MANET Packet/Message Format", RFC 5444, 2731 February 2009. 2733 [RFC5497] Clausen, T. and C. Dearlove, "Representing multi-value 2734 time in MANETs", RFC 5497, March 2009. 2736 [RFC5498] Chakeres, I., "IANA Allocations for MANET Protocols", 2737 RFC 5498, March 2009. 2739 [NHDP] Clausen, T., Dean, J., and C. Dearlove, "MANET 2740 Neighborhood Discovery Protocol (NHDP)", work in 2741 progress draft-ietf-manet-nhdp-10.txt, July 2009. 2743 23.2. Informative References 2745 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 2746 (MANET): Routing Protocol Performance Issues and 2747 Evaluation Considerations", RFC 2501, January 1999. 2749 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 2750 Routing Protocol", RFC 3626, October 2003. 2752 [RFC4880] Callas, J., Donnerhacke, L., Finney, H., and R. Thayer, 2753 "OpenPGP message format", RFC 4880, November 2007. 2755 [HIPERLAN] ETSI, "ETSI STC-RES10 Committee. Radio equipment and 2756 systems: HIPERLAN type 1, functional specifications ETS 2757 300-652", June 1996. 2759 [HIPERLAN2] Jacquet, P., Minet, P., Muhlethaler, P., and N. 2760 Rivierre, "Increasing reliability in cable free radio 2761 LANs: Low level forwarding in HIPERLAN.", 1996. 2763 [MPR] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint 2764 relaying: An efficient technique for flooding in mobile 2765 wireless networks.", 2001. 2767 [FSR] Pei, G., Gerla, M., and T. Chen, "Fisheye state routing 2768 in mobile ad hoc networks", 2000. 2770 [FSLS] Santivanez, C., Ramanathan, R., and I. Stavrakakis, 2771 "Making link-state routing scale for ad hoc networks", 2772 2000. 2774 Appendix A. Router Configuration 2776 OLSRv2 does not make any assumption about router addresses, other 2777 than that each router is assumed to have at least one unique and 2778 routable IP address for each interface that it has which participates 2779 in the MANET. 2781 When applicable, a recommended way of connecting an OLSRv2 network to 2782 an existing IP routing domain is to assign an IP prefix (under the 2783 authority of the routers/gateways connecting the MANET with the 2784 routing domain) exclusively to the OLSRv2 area, and to configure the 2785 gateways statically to advertise routes to that IP sequence to 2786 routers in the existing routing domain. 2788 Appendix B. Example Algorithm for Calculating MPRs 2790 The following specifies an algorithm which MAY be used to select 2791 MPRs. MPRs are calculated per OLSRv2 interface, but then a single 2792 set of MPRs is formed from the union of the MPRs for all OLSRv2 2793 interfaces. (As noted in Section 14 a router MAY improve on this, by 2794 coordination between OLSRv2 interfaces.) A router's MPRs are 2795 recorded using the element N_mpr in Neighbor Tuples. 2797 If using this algorithm then the following steps MUST be executed in 2798 order for a router to select its MPRs: 2800 1. Set N_mpr := false in all Neighbor Tuples; 2802 2. For each Neighbor Tuple with N_symmetric = true and N_willingness 2803 = WILL_ALWAYS, set N_mpr := true; 2805 3. For each OLSRv2 interface of the router, use the algorithm in 2806 Appendix B.2. Note that this sets N_mpr := true for some 2807 Neighbor Tuples, these routers are already selected as MPRs when 2808 using the algorithm for following OLSRv2 interfaces. 2810 4. OPTIONALLY, consider each selected MPR in turn, and if the set of 2811 selected MPRs without that router still satisfies the necessary 2812 conditions, for all OLSRv2 interfaces, then that router MAY be 2813 removed from the set of MPRs. This process MAY be repeated until 2814 no MPRs are removed. Routers MAY be considered in order of 2815 increasing N_willingness. 2817 Symmetric 1-hop neighbor routers with N_willingness = WILL_NEVER MUST 2818 NOT be selected as MPRs, and MUST be ignored in the following 2819 algorithm, as MUST be symmetric 2-hop neighbor routers which are also 2820 symmetric 1-hop neighbor routers (i.e. when considering 2-Hop Tuples, 2821 ignore any 2-Hop Tuples whose N2_2hop_addr is in the 2822 N_neighbor_addr_list of any Neighbor Tuple, or whose 2823 N2_neighbor_iface_addr_list is included in the N_neighbor_addr_list 2824 of any Neighbor Tuple with N_willingness = WILL_NEVER). 2826 B.1. Terminology 2828 The following terminology will be used when selecting MPRs for the 2829 OLSRv2 interface I: 2831 N(I) - The set of symmetric 1-hop neighbors which have a symmetric 2832 link to I. 2834 N2(I) - The set of addresses of interfaces of a router with a 2835 symmetric link to a router in N(I); this MAY be restricted to 2836 considering only information received over I (in which case N2(I) 2837 is the set of N2_2hop_addr in 2-Hop Tuples in the 2-Hop Set for 2838 OLSRv2 interface I). 2840 Connected to I via Y - An address A in N2(I) is connected to I via a 2841 router Y in N(I) if A is an address of an interface of a symmetric 2842 1-hop neighbor of Y (i.e. A is the N2_2hop_addr in a 2-Hop Tuple 2843 in the 2-Hop Set for OLSRv2 interface I, and whose 2844 N2_neighbor_iface_addr_list is contained in the set of interface 2845 addresses of Y). 2847 D(Y, I) - For a router Y in N(I), the number of addresses in N2(I) 2848 which are connected to I via Y. 2850 R(Y, I): - For a router Y in N(I), the number of addresses in N2(I) 2851 which are connected to I via Y, but are not connected to I via any 2852 router which has already been selected as an MPR. 2854 B.2. MPR Selection Algorithm for each OLSRv2 Interface 2856 When selecting MPRs for the OLSRv2 interface I: 2858 1. For each address A in N2(I) for which there is only one router Y 2859 in N(I) such that A is connected to I via Y, select that router Y 2860 as an MPR (i.e. set N_mpr := true in the Neighbor Tuple 2861 corresponding to Y). 2863 2. While there exists any router Y in N(I) with R(Y, I) > 0: 2865 1. Select a router Y in N(I) with R(Y, I) > 0 in the following 2866 order of priority: 2868 + greatest N_willingness in the Neighbor Tuple corresponding 2869 to Y, THEN; 2871 + greatest R(Y, I), THEN; 2873 + greatest D(Y, I), THEN; 2875 + N_mpr_selector is equal to true, if possible, THEN; 2877 + any choice. 2879 2. Select Y as an MPR (i.e. set N_mpr := true in the Neighbor 2880 Tuple corresponding to Y). 2882 Appendix C. Example Algorithm for Calculating the Routing Set 2884 The following procedure is given as an example for calculating the 2885 Routing Set using a variation of Dijkstra's algorithm. First all 2886 Routing Tuples are removed, and then the procedures in the following 2887 sections are applied in turn. 2889 C.1. Add Local Symmetric Links 2891 1. For each Local Interface Tuple: 2893 1. Select an address (the "local address") in 2894 I_local_iface_addr_list. 2896 2. For each Link Tuple for this local interface with L_status = 2897 SYMMETRIC: 2899 1. For each address (the "current address") in 2900 L_neighbor_iface_addr_list, if there is no Routing Tuple 2901 with R_dest_addr = current address, then add a Routing 2902 Tuple with: 2904 - R_dest_addr := current address; 2906 - R_next_iface_addr := current address; 2908 - R_dist := 1; 2910 - R_local_iface_addr := local address. 2912 2. For each Neighbor Tuple whose N_neighbor_addr_list contains the 2913 R_dest_addr of a Routing Tuple (the "previous Tuple"): 2915 1. For each address (the "current address") in 2916 N_neighbor_addr_list, if there is no Routing Tuple with 2917 R_dest_addr = current address, then add a Routing Tuple with: 2919 + R_dest_addr := current address; 2921 + R_next_iface_addr := R_dest_addr of the previous Tuple; 2923 + R_dist := 1; 2925 + R_local_iface_addr := R_local_iface_addr of the previous 2926 Tuple. 2928 C.2. Add Remote Symmetric Links 2930 The following procedure, which adds Routing Tuples for destination 2931 routers h+1 hops away, MUST be executed for each value of h, starting 2932 with h := 1 and incrementing by 1 for each iteration. The execution 2933 MUST stop if no new Routing Tuples are added in an iteration. 2935 1. For each Topology Tuple, if: 2937 * T_dest_addr is not equal to R_dest_addr of any Routing Tuple, 2938 AND; 2940 * for the Advertising Remote Router Tuple with AR_orig_addr = 2941 T_orig_addr, there is an address in the AR_addr_list which is 2942 equal to the R_dest_addr of a Routing Tuple (the "previous 2943 Routing Tuple") whose R_dist = h 2945 then add a new Routing Tuple, with: 2947 * R_dest_addr := T_dest_addr; 2949 * R_next_iface_addr := R_next_iface_addr of the previous Routing 2950 Tuple; 2952 * R_dist := h+1; 2954 * R_local_iface_addr := R_local_iface_addr of the previous 2955 Routing Tuple. 2957 More than one Topology Tuple may be usable to select the next hop 2958 R_next_iface_addr for reaching the address R_dest_addr. Ties 2959 should be broken such that routers with greater willingness are 2960 preferred, and between routers of equal willingness, MPR 2961 selectors are preferred over non-MPR selectors. 2963 2. After the above iteration has completed, if h = 1, for each 2-Hop 2964 Neighbor Tuple where: 2966 * N2_2hop_addr is not equal to R_dest_addr of any Routing Tuple, 2967 AND; 2969 * The Neighbor Tuple whose N_neighbor_addr_list contains 2970 N2_neighbor_iface_addr_list has N_willingness not equal to 2971 WILL_NEVER 2973 select a Routing Tuple (the "previous Routing Tuple") whose 2974 R_dest_addr is contained in N2_neighbor_iface_addr_list, and add 2975 a new Routing Tuple with: 2977 * R_dest_addr := N2_2hop_addr; 2979 * R_next_iface_addr := R_next_iface_addr of the previous Routing 2980 Tuple; 2982 * R_dist := 2; 2984 * R_local_iface_addr := R_local_iface_addr of the previous 2985 Routing Tuple. 2987 More than one 2-Hop Neighbor Tuple may be usable to select the 2988 next hop R_next_iface_addr for reaching the address R_dest_addr. 2989 Ties should be broken such that routers with greater willingness 2990 are preferred, and between routers of equal willingness, MPR 2991 selectors are preferred over non-MPR selectors. 2993 C.3. Add Attached Networks 2995 1. For each Attached Network Tuple, if for the Advertising Remote 2996 Router Tuple with AR_orig_addr = AN_orig_addr, there is an 2997 address in the AR_addr_list which is equal to the R_dest_addr of 2998 a Routing Tuple (the "previous Routing Tuple"), then: 3000 1. If there is no Routing Tuple with R_dest_addr = AN_net_addr, 3001 then add a new Routing Tuple with: 3003 + R_dest_addr := AN_net_addr; 3005 + R_next_iface_addr := R_next_iface_addr of the previous 3006 Routing Tuple; 3008 + R_dist := (R_dist of the previous Routing Tuple) + 3009 AN_dist; 3011 + R_local_iface_addr := R_local_iface_addr of the previous 3012 Routing Tuple. 3014 2. Otherwise if the Routing Tuple with R_dest_addr = AN_net_addr 3015 (the "current Routing Tuple") has R_dist > (R_dist of the 3016 previous Routing Tuple) + AN_dist, then modify the current 3017 Routing Tuple by: 3019 + R_next_iface_addr := R_next_iface_addr of the previous 3020 Routing Tuple; 3022 + R_dist := (R_dist of the previous Routing Tuple) + 3023 AN_dist; 3025 + R_local_iface_addr := R_local_iface_addr of the previous 3026 Routing Tuple. 3028 Appendix D. Example Message Layout 3030 An example TC message is as follows. The message has full Message 3031 Header (four bit Flags field value is 15). Its four bit Message 3032 Address Length field has value 3 and hence addresses in the message 3033 have length four octets, here being IPv4 addresses. The overall 3034 message length is 65 octets. 3036 The message has a Message TLV Block with content length 13 octets 3037 containing three TLVs. The first two TLVs are interval and validity 3038 times for the message. The third TLV is the content sequence number 3039 TLV used to carry the 2 octet ANSN, and (with default type extension 3040 zero, i.e. COMPLETE) indicating that the TC message is complete. 3041 Each TLV uses a TLV with Flags octet value 16, indicating that it has 3042 a Value, but no type extension or start and stop indexes. The first 3043 two TLVs have a Value Length of 1 octet, the last has a Value Length 3044 of 2 octets. 3046 The message has two Address Blocks. The first Address Block contains 3047 6 addresses, with Flags octet value 128, hence with a Head section, 3048 (with length 2 octets) but no Tail section, and hence Mid sections 3049 with length two octets. The following TLV Block (content length 6 3050 octets) contains a single LOCAL_IF TLV (Flags octet value 48) 3051 indicating that the first three addresses (indexes 0 to 2) are 3052 associated with the Value (with Value Length 1 octet) UNSPEC_IF, i.e. 3053 they are the originating router's local addresses. The remaining 3054 three addresses have no associated TLV, they are the addresses of 3055 advertised neighbors. 3057 The second Address Block contains 1 address, with Flags octet 176 3058 indicating that there is a Head section (with length 2 octets), that 3059 the Tail section (length 2 octets) consists of zero valued octets 3060 (not included), and that there is a single prefix length, which is 3061 16. The network address is thus Head.0.0/16. The following TLV 3062 Block (content length 8 octets) includes one TLV that indicates that 3063 the originating router is a gateway to this network, at a given 3064 number of hops distance (Value Length 1 octet). The TLV Flags octet 3065 value of 16 indicates that no indexes are needed. 3067 0 1 2 3 3068 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 3069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3070 | TC |1 1 1 1 0 0 1 1|0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1| 3071 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3072 | Originator Address | 3073 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3074 | Hop Limit | Hop Count | Message Sequence Number | 3075 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3076 |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| 3077 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3078 |0 0 0 0 0 0 0 1| Value | VALIDITY_TIME |0 0 0 1 0 0 0 0| 3079 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3080 |0 0 0 0 0 0 0 1| Value | CONT_SEQ_NUM |0 0 0 1 0 0 0 0| 3081 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3082 |0 0 0 0 0 0 1 0| Value (ANSN) |0 0 0 0 0 1 1 0| 3083 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3084 |1 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0| Head | 3085 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3086 | Mid | Mid | 3087 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3088 | Mid | Mid | 3089 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3090 | Mid | Mid | 3091 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3092 |0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0| LOCAL_IF |0 0 1 1 0 0 0 0| 3093 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3094 |0 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0|0 0 0 0 0 0 0 1| UNSPEC_IF | 3095 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3096 |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 | 3097 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3098 | 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| 3099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3100 |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| 3101 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3102 | Number Hops | 3103 +-+-+-+-+-+-+-+-+ 3105 Appendix E. Constraints 3107 Any process which updates the Local Information Base, the 3108 Neighborhood Information Base or the Topology Information Base MUST 3109 ensure that all constraints specified in this appendix are 3110 maintained, as well as those specified in [NHDP]. 3112 In each Originator Tuple: 3114 o O_orig_addr MUST NOT equal any other O_orig_addr. 3116 o O_orig_addr MUST NOT equal this router's originator address. 3118 In each Local Attached Network Tuple: 3120 o AL_net_addr MUST NOT equal any other AL_net_addr. 3122 o AL_net_addr MUST NOT be in the I_local_iface_addr_list of any 3123 Local Interface Tuple or be equal to the IR_local_iface_addr of 3124 any Removed Interface Address Tuple. 3126 o AL_dist MUST NOT be less than zero. 3128 In each Link Tuple: 3130 o L_neighbor_iface_addr_list MUST NOT contain the AL_net_addr of any 3131 Local Attached Network Tuple. 3133 o If L_status = SYMMETRIC and the Neighbor Tuple whose 3134 N_neighbor_addr_list contains L_neighbor_iface_addr_list has 3135 N_mpr_selector = true, then, for each address in this 3136 L_neighbor_iface_addr_list, there MUST be an equal 3137 RY_neighbor_iface_addr in the Relay Set associated with the same 3138 OLSRv2 interface. 3140 In each Neighbor Tuple: 3142 o N_neighbor_addr_list MUST NOT contain the AL_net_addr of any Local 3143 Attached Network Tuple. 3145 o If N_willingness MUST be in the range from WILL_NEVER to 3146 WILL_ALWAYS, inclusive. 3148 o If N_mpr = true, then N_symmetric MUST be true and N_willingness 3149 MUST NOT equal WILL_NEVER. 3151 o If N_symmetric = true and N_mpr = false, then N_willingness MUST 3152 NOT equal WILL_ALWAYS. 3154 o If N_mpr_selector = true, then N_symmetric MUST be true. 3156 o If N_mpr_selector = true, then, for each address in this 3157 N_neighbor_addr_list, there MUST be an equal A_neighbor_addr in 3158 the Advertised Neighbor Set. 3160 In each Lost Neighbor Tuple: 3162 o NL_neighbor_addr MUST NOT equal the AL_net_addr of any Local 3163 Attached Network Tuple. 3165 In each 2-Hop Tuple: 3167 o N2_2hop_addr MUST NOT equal the AL_net_addr of any Local Attached 3168 Network Tuple. 3170 In each Received Tuple: 3172 o RX_orig_addr MUST NOT equal this router's originator address or 3173 any O_orig_addr. 3175 o Each ordered triple (RX_type, RX_orig_addr, RX_seq_number) MUST 3176 NOT equal the corresponding triple in any other Received Tuple in 3177 the same Received Set. 3179 In each Processed Tuple: 3181 o P_orig_addr MUST NOT equal this router's originator address or any 3182 O_orig_addr. 3184 o Each ordered triple (P_type, P_orig_addr, P_seq_number) MUST NOT 3185 equal the corresponding triple in any other Processed Tuple. 3187 In each Forwarded Tuple: 3189 o F_orig_addr MUST NOT equal this router's originator address or any 3190 O_orig_addr. 3192 o Each ordered triple (F_type, F_orig_addr, F_seq_number) MUST NOT 3193 equal the corresponding triple in any other Forwarded Tuple. 3195 In each Relay Tuple: 3197 o RY_neighbor_iface_addr MUST NOT equal the RY_neighbor_iface_addr 3198 in any other Relay Tuple in the same Relay Set. 3200 o RY_neighbor_iface_addr MUST be in the L_neighbor_iface_addr_list 3201 of a Link Tuple with L_status = SYMMETRIC. 3203 In the Advertised Neighbor Set: 3205 o Each A_neighbor_addr MUST NOT equal any other A_neighbor_addr. 3207 o Each A_neighbor_addr MUST be in the N_neighbor_addr_list of a 3208 Neighbor Tuple with N_symmetric = true. 3210 In each Advertising Remote Router Tuple: 3212 o AR_orig_addr MUST NOT equal this router's originator address or 3213 any O_orig_addr. 3215 o AR_orig_addr MUST NOT equal the AR_orig_addr in any other ANSN 3216 History Tuple. 3218 o AR_addr_list MUST NOT be empty. 3220 o AR_addr_list MUST NOT contain any duplicated addresses. 3222 o AR_addr_list MUST NOT contain any address which is in the 3223 I_local_iface_addr_list of any Local Interface Tuple or be equal 3224 to the IR_local_iface_addr of any Removed Interface Address Tuple. 3226 o AR_addr_list MUST NOT contain any address which is the AL_net_addr 3227 of any Local Attached Network Tuple. 3229 In each Topology Tuple: 3231 o T_dest_addr MUST NOT be in the I_local_iface_addr_list of any 3232 Local Interface Tuple or be equal to the IR_local_iface_addr of 3233 any Removed Interface Address Tuple. 3235 o T_dest_addr MUST NOT equal the AL_net_addr of any Local Attached 3236 Network Tuple. 3238 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 3239 = T_orig_addr. 3241 o T_dest_addr MUST NOT be in the AR_addr_list of the Advertising 3242 Remote Router Tuple with AR_orig_addr = T_orig_addr. 3244 o T_seq_number MUST NOT be greater than AR_seq_number of the 3245 Advertising Remote Router Tuple with AR_orig_addr = T_orig_addr. 3247 o The ordered pair (T_dest_addr, T_orig_addr) MUST NOT equal the 3248 corresponding pair in any other Topology Tuple. 3250 In each Attached Network Tuple: 3252 o AN_net_addr MUST NOT be in the I_local_iface_addr_list of any 3253 Local Interface Tuple or be equal to the IR_local_iface_addr of 3254 any Removed Interface Address Tuple. 3256 o AN_net_addr MUST NOT equal the AL_net_addr of any Local Attached 3257 Network Tuple. 3259 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 3260 = AN_orig_addr. 3262 o AN_seq_number MUST NOT be greater than AR_seq_number of the 3263 Advertising Remote Router Tuple with AR_orig_addr = AN_orig_addr. 3265 o AN_dist MUST NOT be less than zero. 3267 o The ordered pair (AN_net_addr, AN_orig_addr) MUST NOT equal the 3268 corresponding pair in any other Attached Network Tuple. 3270 Appendix F. Flow and Congestion Control 3272 Due to its proactive nature, the OLSRv2 protocol has a natural 3273 control over the flow of its control traffic. Routers transmit 3274 control messages at predetermined rates specified and bounded by 3275 message intervals. 3277 OLSRv2 employs [NHDP] for local signaling, embedding MPR selection 3278 advertisement through a simple Address Block TLV, and router 3279 willingness advertisement (if any) as a single Message TLV. OLSRv2 3280 local signaling, therefore, shares the characteristics and 3281 constraints of [NHDP]. 3283 Furthermore, MPR flooding greatly reduces signaling overhead from 3284 from link state information dissemination in two ways. First, the 3285 amount of link state information for a router to declare is reduced 3286 to only contain that router's MPR selectors. This reduces the size 3287 of a link state declaration as compared to declaring full link state 3288 information. In particular some routers may not need to declare any 3289 such information. Second, using MPR flooding, the cost of 3290 distributing link state information throughout the network is greatly 3291 reduced, as compared to when using classic flooding, since only MPRs 3292 need to forward link state declaration messages. In dense networks, 3293 the reduction of control traffic can be of several orders of 3294 magnitude compared to routing protocols using classical flooding 3295 [MPR]. This feature naturally provides more bandwidth for useful 3296 data traffic and pushes further the frontier of congestion. 3298 Since the control traffic is continuous and periodic, it keeps the 3299 quality of the links used in routing more stable. However, using 3300 certain OLSRv2 options, some control messages (HELLO messages or TC 3301 messages) may be intentionally sent in advance of their deadline in 3302 order to increase the responsiveness of the protocol to topology 3303 changes. This may cause a small, temporary, and local increase of 3304 control traffic, however this is at all times bounded by the use of 3305 minimum message intervals. 3307 Authors' Addresses 3309 Thomas Heide Clausen 3310 LIX, Ecole Polytechnique 3312 Phone: +33 6 6058 9349 3313 EMail: T.Clausen@computer.org 3314 URI: http://www.ThomasClausen.org/ 3316 Christopher Dearlove 3317 BAE Systems ATC 3319 Phone: +44 1245 242194 3320 EMail: chris.dearlove@baesystems.com 3321 URI: http://www.baesystems.com/ 3323 Philippe Jacquet 3324 Project Hipercom, INRIA 3326 Phone: +33 1 3963 5263 3327 EMail: philippe.jacquet@inria.fr 3329 The OLSRv2 Design Team 3330 MANET Working Group