idnits 2.17.1 draft-ietf-manet-olsrv2-12.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 26, 2011) is 4655 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) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique 4 Intended status: Standards Track C. Dearlove 5 Expires: January 27, 2012 BAE Systems ATC 6 P. Jacquet 7 Project Hipercom, INRIA 8 July 26, 2011 10 The Optimized Link State Routing Protocol version 2 11 draft-ietf-manet-olsrv2-12 13 Abstract 15 This document describes version 2 of the Optimized Link State Routing 16 (OLSRv2) protocol for Mobile Ad hoc NETworks (MANETs). 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on January 27, 2012. 35 Copyright Notice 37 Copyright (c) 2011 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 This document may contain material from IETF Documents or IETF 51 Contributions published or made publicly available before November 52 10, 2008. The person(s) controlling the copyright in some of this 53 material may not have granted the IETF Trust the right to allow 54 modifications of such material outside the IETF Standards Process. 55 Without obtaining an adequate license from the person(s) controlling 56 the copyright in such materials, this document may not be modified 57 outside the IETF Standards Process, and derivative works of it may 58 not be created outside the IETF Standards Process, except to format 59 it for publication as an RFC or to translate it into languages other 60 than English. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 65 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 66 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 8 67 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 9 68 4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 10 69 4.2. Routers and Interfaces . . . . . . . . . . . . . . . . . . 12 70 4.3. Information Base Overview . . . . . . . . . . . . . . . . 13 71 4.3.1. Local Information Base . . . . . . . . . . . . . . . . 13 72 4.3.2. Interface Information Bases . . . . . . . . . . . . . 13 73 4.3.3. Neighbor Information Base . . . . . . . . . . . . . . 14 74 4.3.4. Topology Information Base . . . . . . . . . . . . . . 14 75 4.3.5. Received Message Information Base . . . . . . . . . . 15 76 4.4. Signaling Overview . . . . . . . . . . . . . . . . . . . . 15 77 4.5. Link Metrics . . . . . . . . . . . . . . . . . . . . . . . 17 78 4.6. Routing Set . . . . . . . . . . . . . . . . . . . . . . . 18 79 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 18 80 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 18 81 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 19 82 5.3. Interface Parameters . . . . . . . . . . . . . . . . . . . 19 83 5.3.1. Received Message Validity Time . . . . . . . . . . . . 19 84 5.4. Router Parameters . . . . . . . . . . . . . . . . . . . . 19 85 5.4.1. Local History Times . . . . . . . . . . . . . . . . . 19 86 5.4.2. Link_Metric_Parameters . . . . . . . . . . . . . . . . 19 87 5.4.3. Message Intervals . . . . . . . . . . . . . . . . . . 20 88 5.4.4. Advertised Information Validity Times . . . . . . . . 20 89 5.4.5. Processing and Forwarding Validity Times . . . . . . . 21 90 5.4.6. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 22 91 5.4.7. Hop Limit . . . . . . . . . . . . . . . . . . . . . . 22 92 5.4.8. Willingness . . . . . . . . . . . . . . . . . . . . . 23 93 5.5. Parameter Change Constraints . . . . . . . . . . . . . . . 24 94 5.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 25 95 5.6.1. Link Metric Constants . . . . . . . . . . . . . . . . 25 96 6. Link Metric Values . . . . . . . . . . . . . . . . . . . . . . 26 97 6.1. Link Metric Representation . . . . . . . . . . . . . . . . 26 98 6.2. Link Metric Compressed Form . . . . . . . . . . . . . . . 26 99 7. Local Information Base . . . . . . . . . . . . . . . . . . . . 27 100 7.1. Originator Set . . . . . . . . . . . . . . . . . . . . . . 27 101 7.2. Local Attached Network Set . . . . . . . . . . . . . . . . 28 102 8. Interface Information Base . . . . . . . . . . . . . . . . . . 29 103 9. Neighbor Information Base . . . . . . . . . . . . . . . . . . 30 104 10. Topology Information Base . . . . . . . . . . . . . . . . . . 31 105 10.1. Advertising Remote Router Set . . . . . . . . . . . . . . 31 106 10.2. Router Topology Set . . . . . . . . . . . . . . . . . . . 32 107 10.3. Routable Address Topology Set . . . . . . . . . . . . . . 32 108 10.4. Attached Network Set . . . . . . . . . . . . . . . . . . . 33 109 10.5. Routing Set . . . . . . . . . . . . . . . . . . . . . . . 34 110 11. Received Message Information Base . . . . . . . . . . . . . . 35 111 11.1. Received Set . . . . . . . . . . . . . . . . . . . . . . . 35 112 11.2. Processed Set . . . . . . . . . . . . . . . . . . . . . . 35 113 11.3. Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 36 114 12. Information Base Properties . . . . . . . . . . . . . . . . . 36 115 13. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 38 116 13.1. Messages . . . . . . . . . . . . . . . . . . . . . . . . . 38 117 13.2. Packets . . . . . . . . . . . . . . . . . . . . . . . . . 38 118 13.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 119 13.3.1. Message TLVs . . . . . . . . . . . . . . . . . . . . . 39 120 13.3.2. Address Block TLVs . . . . . . . . . . . . . . . . . . 39 121 14. Message Processing and Forwarding . . . . . . . . . . . . . . 41 122 14.1. Actions when Receiving a Message . . . . . . . . . . . . . 42 123 14.2. Message Considered for Processing . . . . . . . . . . . . 43 124 14.3. Message Considered for Forwarding . . . . . . . . . . . . 44 125 15. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . . . 45 126 15.1. HELLO Message Generation . . . . . . . . . . . . . . . . . 46 127 15.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 47 128 15.3. HELLO Message Processing . . . . . . . . . . . . . . . . . 48 129 15.3.1. HELLO Message Discarding . . . . . . . . . . . . . . . 48 130 15.3.2. HELLO Message Usage . . . . . . . . . . . . . . . . . 49 131 16. TC Messages . . . . . . . . . . . . . . . . . . . . . . . . . 52 132 16.1. TC Message Generation . . . . . . . . . . . . . . . . . . 52 133 16.2. TC Message Transmission . . . . . . . . . . . . . . . . . 54 134 16.3. TC Message Processing . . . . . . . . . . . . . . . . . . 55 135 16.3.1. Invalid Message . . . . . . . . . . . . . . . . . . . 55 136 16.3.2. TC Message Processing Definitions . . . . . . . . . . 56 137 16.3.3. Initial TC Message Processing . . . . . . . . . . . . 57 138 16.3.4. Completing TC Message Processing . . . . . . . . . . . 60 139 17. Information Base Changes . . . . . . . . . . . . . . . . . . . 61 140 17.1. Originator Address Changes . . . . . . . . . . . . . . . . 61 141 17.2. Link State Changes . . . . . . . . . . . . . . . . . . . . 62 142 17.3. Neighbor State Changes . . . . . . . . . . . . . . . . . . 62 143 17.4. Advertised Neighbor Changes . . . . . . . . . . . . . . . 63 144 17.5. Advertising Remote Router Tuple Expires . . . . . . . . . 63 145 17.6. Neighborhood Changes and MPR Updates . . . . . . . . . . . 64 146 17.7. Routing Set Updates . . . . . . . . . . . . . . . . . . . 65 147 18. Selecting MPRs . . . . . . . . . . . . . . . . . . . . . . . . 66 148 19. Routing Set Calculation . . . . . . . . . . . . . . . . . . . 68 149 19.1. Network Topology Graph . . . . . . . . . . . . . . . . . . 68 150 19.2. Populating the Routing Set . . . . . . . . . . . . . . . . 70 151 20. Proposed Values for Parameters and Constants . . . . . . . . . 71 152 20.1. Local History Time Parameters . . . . . . . . . . . . . . 72 153 20.2. Message Interval Parameters . . . . . . . . . . . . . . . 72 154 20.3. Advertised Information Validity Time Parameters . . . . . 72 155 20.4. Received Message Validity Time Parameters . . . . . . . . 72 156 20.5. Jitter Time Parameters . . . . . . . . . . . . . . . . . . 72 157 20.6. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 72 158 20.7. Willingness Parameter and Constants . . . . . . . . . . . 72 159 21. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 73 160 22. Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 73 161 23. Security Considerations . . . . . . . . . . . . . . . . . . . 74 162 23.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . 74 163 23.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 74 164 23.3. Interaction with External Routing Domains . . . . . . . . 76 165 24. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 76 166 24.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 76 167 24.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 77 168 24.3. Message-Type-specific TLV Type Registries . . . . . . . . 77 169 24.4. Message TLV Types . . . . . . . . . . . . . . . . . . . . 77 170 24.5. Address Block TLV Types . . . . . . . . . . . . . . . . . 79 171 24.6. NBR_ADDR_TYPE Values . . . . . . . . . . . . . . . . . . . 81 172 25. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 82 173 26. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 82 174 27. References . . . . . . . . . . . . . . . . . . . . . . . . . . 82 175 27.1. Normative References . . . . . . . . . . . . . . . . . . . 82 176 27.2. Informative References . . . . . . . . . . . . . . . . . . 83 177 Appendix A. Example Algorithm for Calculating MPRs . . . . . . . 84 178 A.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 85 179 A.2. MPR Selection Algorithm for each OLSRv2 Interface . . . . 85 180 Appendix B. Example Algorithm for Calculating the Routing Set . . 86 181 B.1. Local Interfaces and Neighbors . . . . . . . . . . . . . . 86 182 B.2. Add Neighbor Routers . . . . . . . . . . . . . . . . . . . 87 183 B.3. Add Remote Routers . . . . . . . . . . . . . . . . . . . . 87 184 B.4. Add Neighbor Addresses . . . . . . . . . . . . . . . . . . 88 185 B.5. Add Remote Routable Addresses . . . . . . . . . . . . . . 89 186 B.6. Add Attached Networks . . . . . . . . . . . . . . . . . . 89 187 B.7. Add 2-Hop Neighbors . . . . . . . . . . . . . . . . . . . 90 188 Appendix C. TC Message Example . . . . . . . . . . . . . . . . . 91 189 Appendix D. Constraints . . . . . . . . . . . . . . . . . . . . . 93 190 Appendix E. Flow and Congestion Control . . . . . . . . . . . . . 98 192 1. Introduction 194 The Optimized Link State Routing protocol version 2 (OLSRv2) is an 195 update to OLSR (version 1) as published in [RFC3626]. Compared to 196 [RFC3626], OLSRv2 retains the same basic mechanisms and algorithms, 197 enhanced by the ability to use a link metric other than hop count in 198 the selection of shortest routes. OLSRv2 also uses a more flexible 199 and efficient signaling framework, and includes some simplification 200 of the messages being exchanged. 202 OLSRv2 is developed for mobile ad hoc networks. It operates as a 203 table driven, proactive protocol, i.e., it exchanges topology 204 information with other routers in the network regularly. OLSRv2 is 205 an optimization of the classical link state routing protocol. Its 206 key concept is that of MultiPoint Relays (MPRs). Each router selects 207 as MPRs a set of its neighbor routers that "cover" all of its 208 symmetrically connected 2-hop neighbor routers. Separate sets of 209 flooding MPRs and routing MPRs are then used to achieve flooding 210 reduction and topology reduction, respectively. 212 Flooding reduction is achieved by control traffic being flooded 213 through the network using hop by hop forwarding, but with a router 214 only needing to forward control traffic that is first received 215 directly from one of the routers that have selected it as a flooding 216 MPR (its "flooding MPR selectors"). This mechanism, denoted "MPR 217 flooding", provides an efficient mechanism for information 218 distribution within the MANET by reducing the number of transmissions 219 required. 221 Topology reduction is achieved by assigning a special responsibility 222 to routers selected as routing MPRs when declaring link state 223 information. A sufficient requirement for OLSRv2 to provide shortest 224 routes to all destinations is that routers declare link state 225 information for their routing MPR selectors, if any. Routers that 226 are not selected as routing MPRs need not send any link state 227 information. Based on this reduced link state information, routing 228 MPRs are used as intermediate routers in multi-hop routes. 230 Thus the use of MPRs allows reduction of the number and the size of 231 link state messages, and in the amount of link state information 232 maintained in each router. When possible (in particular when using a 233 hop count metric) the same routers may be picked as both flooding 234 MPRs and routing MPRs. 236 A router selects both routing and flooding MPRs from among its one 237 hop neighbors connected by "symmetric", i.e., bidirectional, links. 238 Therefore, selecting routes through routing MPRs avoids the problems 239 associated with data packet transfer over unidirectional links (e.g., 240 the problem of not getting link layer acknowledgments at each hop, 241 for link layers employing this technique). 243 OLSRv2 uses and extends [RFC6130] and uses [RFC5444], [RFC5497] and, 244 optionally, [RFC5148]. These other protocols and specifications were 245 all originally created as part of OLSRv2, but have been specified 246 separately for wider use. 248 OLSRv2 makes no assumptions about the underlying link layer. OLSRv2, 249 through its use of [RFC6130], may use link layer information and 250 notifications when available and applicable. Link metrics may be 251 derived from link layer or any other information. OLSRv2 does not 252 specify the physical meaning of link metrics, but specifies a means 253 by which new types of link metrics may be specified in the future, 254 but used by OLSRv2 without modification. 256 OLSRv2, as OLSR [RFC3626], inherits its concept of forwarding and 257 relaying from HIPERLAN (a MAC layer protocol) which is standardized 258 by ETSI [HIPERLAN], [HIPERLAN2]. 260 Note: This is the first version of this specification to incorporate 261 the use of link metrics. It is not compete: Section 18 and 262 Appendix A have not yet been updated to use link metrics and separate 263 sets of flooding and routing MPRs. 265 2. Terminology 267 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 268 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 269 "OPTIONAL" in this document are to be interpreted as described in 270 [RFC2119]. 272 All terms introduced in [RFC5444], including "packet", "Packet 273 Header", "message", "Message Header", "Message Body", "Message Type", 274 "message sequence number", "hop limit", "hop count", "Address Block", 275 "TLV Block", "TLV", "Message TLV", "Address Block TLV", "type" (of 276 TLV), "type extension" (of TLV), "value" (of TLV), "address", 277 "address prefix", and "address object" are to be interpreted as 278 described there. 280 All terms introduced in [RFC6130], including "interface", "MANET 281 interface", "network address", "link", "symmetric link", "1-hop 282 neighbor", "symmetric 1-hop neighbor", "symmetric 2-hop neighbor", 283 "constant", "interface parameter", "router parameter", "Information 284 Base", and "HELLO message" are to be interpreted as described there. 286 Additionally, this specification uses the following terminology: 288 Router - A MANET router which implements this protocol. 290 OLSRv2 interface - A MANET interface running this protocol. 292 Routable address - A network address which may be used as the 293 destination of a data packet. A router MUST be able to 294 distinguish a routable address from a non-routable address by 295 direct inspection of the network address, based on global scope 296 address allocations by IANA and/or administrative configuration. 297 Broadcast, multicast and anycast addresses, and addresses which 298 are limited in scope to less than the entire MANET, MUST NOT be 299 considered as routable addresses. 301 Originator address - An address which is unique (within the MANET) 302 to a router. A router MUST select an originator address; it MAY 303 choose one of its interface addresses as its originator address. 304 If it selects a routable address then this MUST be one which this 305 router will accept as destination. An originator address MUST NOT 306 have a prefix length, except for when included in an Address Block 307 where it MAY be associated with a prefix of maximum prefix length 308 (e.g., if the originator address is an IPv6 address, it MUST have 309 either no prefix length, or have a prefix length of 128). An 310 originator address may be a routable or non-routable address. 312 Message originator address - The originator address of the router 313 which created a message, as deduced from that message by its 314 recipient. The message originator address will usually be 315 included in the message as its element as defined 316 in [RFC5444]. However an exceptional case in a HELLO message is 317 also allowed by this specification, when a router only uses a 318 single address. For all messages used in this specification, 319 including HELLO messages defined in [RFC6130], the recipient MUST 320 be able to deduce an originator address. 322 Willingness - A numerical value between WILL_NEVER and WILL_ALWAYS 323 (both inclusive), that represents the router's willingness to be 324 selected as an MPR. 326 Willing symmetric 1-hop neighbor - A symmetric 1-hop neighbor of 327 this router that has willingness not equal to WILL_NEVER. 329 Symmetric 1-hop neighbor through OLSRv2 interface I - A symmetric 330 1-hop neighbor of the router via a symmetric link using OLSRv2 331 interface I of the router. 333 Willing symmetric 1-hop neighbor through OLSRv2 interface I - A 334 willing symmetric 1-hop neighbor of the router via a symmetric 335 link using OLSRv2 interface I of the router. 337 Symmetric strict 2-hop neighbor - A symmetric 1-hop neighbor of a 338 willing symmetric 1-hop neighbor that is not a symmetric 1-hop 339 neighbor. 341 Symmetric strict 2-hop neighbor through OLSRv2 interface I - A 342 symmetric 1-hop neighbor of a willing symmetric 1-hop neighbor 343 through OLSRv2 interface I that is not a symmetric 1-hop neighbor 344 through OLSRv2 interface I. The router MAY elect to use only 345 information received over OLSRv2 interface I in making this 346 determination. 348 Multipoint relay (MPR) - A router, X, is an MPR for a router, Y, if 349 router Y has indicated its selection of router X as an MPR in a 350 recent HELLO message. Router X may be a Flooding MPR for Y, if it 351 is indicated to participate in the flooding process of messages 352 received from router Y, or it may be a Routing MPR for Y, if it is 353 indicated to declare link-state information for the link from X to 354 Y. It may also be both at the same time. 356 MPR selector - A router, Y, is an MPR selector of router X if router 357 Y has selected router X as an MPR. 359 MPR flooding - The optimized MANET-wide information distribution 360 mechanism, employed by this protocol, in which a message is 361 relayed by only a reduced subset of the routers in the network. 362 MPR flooding is the mechanism by which flooding reduction is 363 achieved. 365 This document employs the same notational conventions as in [RFC5444] 366 and [RFC6130]. 368 3. Applicability Statement 370 This protocol: 372 o Is a proactive routing protocol for mobile ad hoc networks 373 (MANETs) [RFC2501]. 375 o Is designed to work in networks with a dynamic topology, and in 376 which messages may be lost, such as due to collisions in wireless 377 networks. 379 o Supports routers that each have one or more participating OLSRv2 380 interfaces. The set of a router's interfaces may change over 381 time. Each OLSRv2 interface may have one or more network 382 addresses (which may have prefix lengths), and these may also be 383 dynamically changing. 385 o Enables hop-by-hop routing, i.e., each router can use its local 386 information provided by this protocol to route packets. 388 o Continuously maintains routes to all destinations in the network, 389 i.e., routes are instantly available and data traffic is subject 390 to no delays due to route discovery. Consequently, no data 391 traffic buffering is required. 393 o Supports routers that have non-OLSRv2 interfaces which may be 394 local to a router or that can serve as gateways towards other 395 networks. 397 o Enables the use of bidirectional additive link metrics to use 398 shortest distance (i.e., the total of metrics) routes. Incoming 399 link metric values are to be determined by a process outside this 400 specification. 402 o Is optimized for large and dense networks; the larger and more 403 dense a network, the more optimization can be achieved by using 404 MPRs, compared to the classic link state algorithm. 406 o Uses [RFC5444] as described in its "Intended Usage" appendix and 407 by [RFC5498]. 409 o Allows "external" and "internal" extensibility as enabled by 410 [RFC5444]. 412 o Is designed to work in a completely distributed manner, and does 413 not depend on any central entity. 415 4. Protocol Overview and Functioning 417 The objective of this protocol is for each router to, independently: 419 o Identify all destinations in the network. 421 o Identify a sufficient subset of links in the network, in order 422 that shortest paths can be calculated to all available 423 destinations. 425 o Provide a Routing Set, containing these shortest paths from this 426 router to all destinations (routable addresses and local links). 428 4.1. Overview 430 These objectives are achieved, for each router, by: 432 o Using [RFC6130] to identify symmetric 1-hop neighbors and 433 symmetric 2-hop neighbors. 435 o Extending [RFC6130] to allow the addition of directional link 436 metrics to advertised links, and to indicate which link metric 437 type is being used by that router. Both incoming and outgoing 438 link metrics may be reported, the latter determined by the 439 advertising router. 441 o Independently selecting flooding MPRs and routing MPRs from among 442 its symmetric 1-hop neighbors such that, for each set of MPRs all 443 symmetric 2-hop neighbors are reachable via at least one symmetric 444 1-hop neighbor. An analysis and examples of MPR selection 445 algorithms is given in [MPR], a suggested algorithm, modified for 446 each set of MPRs, is included in this specification. Note that it 447 is not necessary for routers to use the same algorithm in order to 448 interoperate in the same MANET, but these algorithms must each 449 have the appropriate properties. 451 o Signaling its flooding MPR and routing MPR selections by extending 452 [RFC6130] to report this information in outgoing HELLO messages, 453 by the addition of MPR Address Block TLV(s) associated with the 454 appropriate network addresses. 456 o Extracting its flooding MPR selectors and routing MPR selectors 457 from received HELLO messages, using the included MPR Address Block 458 TLV(s). 460 o Reporting its willingness to be a flooding MPR and to be a routing 461 MPR in HELLO messages, by the addition on an MPR_WILLING Message 462 TLV. The router's flooding willingness indicates how willing it 463 is to participate in MPR flooding and the router's routing 464 willingness indicates how willing is is to be an intermediate node 465 for routing, while still being able to be a routing source or 466 destination. 468 o Using the message format specified in [RFC5444], specifically 469 defining a TC (Topology Control) Message Type, used to 470 periodically signal links between routing MPR selectors and itself 471 throughout the MANET. This signaling includes suitable direction 472 router metrics (the best link metric in that direction between 473 those routers). 475 o Allowing its TC messages, as well as HELLO messages, to be 476 included in packets specified in [RFC5444], using the "manet" IP 477 protocol or UDP port as specified in [RFC5498]. 479 o Diffusing TC messages by using a flooding reduction mechanism, 480 denoted "MPR flooding"; only the flooding MPRs of a router will 481 retransmit messages received from (i.e., originated or last 482 relayed by) that router. 484 Note that the indicated extensions to [RFC6130] are of forms 485 permitted by that specification. 487 This specification defines: 489 o The requirement to use [RFC6130], its parameters, constants, HELLO 490 messages, and Information Bases, each as extended in this 491 specification. 493 o Two new Information Bases: the Topology Information Base and the 494 Received Message Information Base. 496 o TC messages, which are used for MANET wide signaling (using MPR 497 flooding) of selected topology (link state) information. 499 o A requirement for each router to have an originator address to be 500 included in, or deducible from, HELLO messages and TC messages. 502 o The specification of new Message TLVs and Address Block TLVs that 503 are used in HELLO messages and TC messages, including for 504 reporting link metrics and their usage, willingness to be an MPR, 505 MPR selection, and content sequence number information. Note that 506 the generation of (incoming) link metric values is to be 507 undertaken by a process outside this specification. This 508 specification concerns only the distribution and use of those 509 metrics. 511 o The generation of TC messages from the appropriate information in 512 the Information Bases. 514 o The updating of the Topology Information Base according to 515 received TC messages. 517 o The MPR flooding mechanism, including the inclusion of message 518 originator address and sequence number to manage duplicate 519 messages, using information recorded in the Received Message 520 Information Base. 522 o The response to other events, such as the expiration of 523 information in the Information Bases. 525 This protocol inherits the stability of a link state algorithm, and 526 has the advantage of having routes immediately available when needed, 527 due to its proactive nature. 529 This protocol only interacts with IP through routing table 530 management, and the use of the sending IP address for IP datagrams 531 containing OLSRv2 packets. 533 4.2. Routers and Interfaces 535 In order for a router to participate in a MANET, it MUST have at 536 least one, and possibly more, OLSRv2 interfaces. Each OLSRv2 537 interface: 539 o Is configured with one or more network addresses, as specified in 540 [RFC6130]. These addresses MUST each be specific to this router, 541 and MUST include any address that will be used as the sending 542 address of any IP packet sent on this OLSRv2 interface. 544 o Has a number of interface parameters, adding to those specified in 545 [RFC6130]. 547 o Has an Interface Information Base, extending that specified in 548 [RFC6130]. 550 o Generates and processes HELLO messages according to [RFC6130], 551 extended as specified in Section 15. 553 In addition to a set of OLSRv2 interfaces as described above, each 554 router: 556 o May have one or more non-OLSRv2 interfaces and/or local attached 557 networks for which this router can accept packets. All routable 558 addresses for which the router is to accept packets MUST be used 559 as an (OLSRv2 or non-OLSRv2) interface network address or as an 560 address of a local attached network of the router. 562 o Has a number of router parameters, adding to those specified in 563 [RFC6130]. 565 o Has a Local Information Base, extending that specified in 566 [RFC6130], including selection of an originator address and 567 recording any locally attached networks. 569 o Has a Neighbor Information Base, extending that specified in 570 [RFC6130] to record MPR selection and advertisement information. 572 o Has a Topology Information Base, recording information received in 573 TC messages. 575 o Has a Received Message Information Base, recording information 576 about received messages to ensure that each TC message is only 577 processed once, and forwarded at most once on each OLSRv2 578 interface, by a router. 580 o Generates and processes TC messages. 582 4.3. Information Base Overview 584 Each router maintains the Information Bases described in the 585 following sections. These are used for describing the protocol in 586 this specification. An implementation of this protocol MAY maintain 587 this information in the indicated form, or in any other organization 588 which offers access to this information. In particular, note that it 589 is not necessary to remove Tuples from Sets at the exact time 590 indicated, only to behave as if the Tuples were removed at that time. 592 4.3.1. Local Information Base 594 The Local Information Base is specified in [RFC6130], and contains a 595 router's local configuration. It is extended in this specification 596 to also record an originator address, and to include a router's: 598 o Originator Set, containing addresses that were recently used as 599 this router's originator address, and is used, together with the 600 router's current originator address, to enable a router to 601 recognize and discard control traffic which was originated by the 602 router itself. 604 o Local Attached Network Set, containing network addresses of 605 networks to which this router can act as a gateway, and advertises 606 in its TC messages. 608 4.3.2. Interface Information Bases 610 The Interface Information Bases, one for each OLSRv2 interface, are 611 specified in [RFC6130], and are extended to also record, in each Link 612 Set, link metric values (incoming and outgoing) and flooding MPR 613 selector information. 615 4.3.3. Neighbor Information Base 617 The Neighbor Information Base is specified in [RFC6130], and is 618 extended to also record, in the Neighbor Tuple for each neighbor: 620 o Its originator address. 622 o Neighbor metric values, these being the minimum of the link metric 623 values in the indicated directon for all symmetric 1-hop links 624 with that neighbor. 626 o Its willingness to be a flooding MPR and to be a routing MPR. 628 o Whether it has been selected by this router as a flooding MPR or 629 as a routing MPR, and whether it is a routing MPR selector of this 630 router. (Whether it is a flooding MPR selector of this neighbor 631 is recorded in the Interface Information Base.) 633 o Whether it is to be advertised in TC messages sent by this router. 635 4.3.4. Topology Information Base 637 The Topology Information Base in each router contains: 639 o An Advertising Remote Router Set, recording each other router from 640 which TC messages have been received. This is used in order to 641 determine if a received TC message contains fresh or outdated 642 information; a received TC message is ignored in the latter case. 644 o A Router Topology Set, recording links between routers in the 645 MANET, as described by received TC messages. 647 o A Routable Address Topology Set, recording routable addresses in 648 the MANET (available as packet destinations) and from which other 649 router these routable addresses can be directly reached (i.e., in 650 a single IP hop), as reported by received TC messages. 652 o An Attached Network Set, recording networks to which a remote 653 router has advertised that it may act as a gateway. These 654 networks may be reached in one or more IP hops. 656 o A Routing Set, recording routes from this router to all available 657 destinations. The IP routing table is to be updated using this 658 Routing Set. (A router MAY choose to use any or all destination 659 network addresses in the Routing Set to update the IP routing 660 table, this selection is outside the scope of this protocol.) 662 The purpose of the Topology Information Base is to record information 663 used, in addition to that in the Local Information Base, the 664 Interface Information Bases and the Neighbor Information Base, to 665 construct the Routing Set (which is also included in the Topology 666 Information Base). 668 This specification describes the calculation of the Routing Set based 669 on a Topology Graph constructed in two phases. First, a "backbone" 670 graph representing the routers in the MANET, and the connectivity 671 between them, is constructed from the Local Information Base, the 672 Neighbor Information Base and the Router Topology Set. Second, this 673 graph is "decorated" with additional destination network addresses 674 using the Local Information Base, the Routable Address Topology Set 675 and the Attached Network Set. 677 The Topology Graph does not need to be recorded in the Topology 678 Information Base, it can either be constructed as required when the 679 Routing Set is to be changed, or need not be explicitly constructed 680 (as illustrated in Appendix B). An implementation MAY construct and 681 retain the Topology Graph if preferred. 683 4.3.5. Received Message Information Base 685 The Received Message Information Base in each router contains: 687 o A Received Set for each OLSRv2 interface, describing TC messages 688 received by this router on that OLSRv2 interface. 690 o A Processed Set, describing TC messages processed by this router. 692 o A Forwarded Set, describing TC messages forwarded by this router. 694 The Received Message Information Base serves the MPR flooding 695 mechanism by ensuring that received messages are forwarded at most 696 once by a router, and also ensures that received messages are 697 processed exactly once by a router. 699 4.4. Signaling Overview 701 This protocol generates and processes HELLO messages according to 702 [RFC6130], extended according to Section 15 of this specification to 703 include an originator address, link metrics, and MPR selection 704 information. 706 This protocol specifies a single message type, the TC message. TC 707 messages are sent by their originating router proactively, at a 708 regular interval. This interval may be fixed, or may be dynamic, for 709 example it may be backed off due to congestion or network stability. 710 TC messages may also be sent as a response to a change in the router 711 itself, or its advertised 1-hop neighborhood, for example on first 712 being selected as a routing MPR. 714 Because TC messages are sent periodically, this protocol is tolerant 715 of unreliable transmissions of TC messages. Message losses may occur 716 more frequently in wireless networks due to collisions or other 717 transmission problems. This protocol MAY use "jitter", randomized 718 adjustments to message transmission times, to reduce the incidence of 719 collisions, as specified in [RFC5148]. 721 This protocol is tolerant of out of sequence delivery of TC messages 722 due to in transit message reordering. Each router maintains an 723 Advertised Neighbor Sequence Number (ANSN) that is incremented when 724 its recorded neighbor information that is to be included in its TC 725 messages changes. This ANSN is included in the router's TC messages. 726 The recipient of a TC message can used this included ANSN to identify 727 which of the information it has received is most recent, even if 728 messages have been reordered while in transit. Only the most recent 729 information received is used, older information received later is 730 discarded. 732 TC messages may be "complete" or "incomplete". A complete TC message 733 advertises all of the originating router's routing MPR selectors, it 734 may also advertise other symmetric 1-hop neighbors. Complete TC 735 messages are generated periodically (and also, optionally, in 736 response to neighborhood changes). Incomplete TC messages may be 737 used to report additions to advertised information, without repeating 738 unchanged information. 740 TC messages, and HELLO messages as extended by this specification, 741 include an originator address for the router that created the 742 message. A TC message reports both the originator addresses and 743 routable addresses of its advertised neighbors, distinguishing the 744 two using an Address Block TLV (an address may be both routable and 745 an originator address). TC messages also report the originator's 746 locally attached networks. 748 TC messages are MPR flooded throughout the MANET. A router 749 retransmits a TC message only if it is received from (i.e., 750 originated from or was last relayed by) one of that router's flooding 751 MPR selectors. 753 Some TC messages may be MPR flooded over only part of the network, 754 e.g., allowing a router to ensure that nearer routers are kept more 755 up to date than distant routers, such as is used in Fisheye State 756 Routing [FSR] and Fuzzy Sighted Link State routing [FSLS]. This is 757 enabled using [RFC5497]. 759 TC messages include outgoing neighbor metrics that will be used in 760 the creation of route metrics. 762 4.5. Link Metrics 764 OLSRv1 [RFC3626] created minimum hop routes to destinations. However 765 in many, if not most, circumstances, better routes (in terms of 766 quality of service for end users) can be created by use of link 767 metrics. 769 OLSRv2, as defined in this specification, allows links to have a 770 metric (also known as a cost). Link metrics as defined in OLSRv2 are 771 additive, and the routes that are to be created are minimum length 772 routes, where the length of a route is defined as the sum of the 773 metrics of the links in that route. 775 Link metrics are defined to be directional; the link metric from one 776 router to another may be different from that on the reverse link. 777 The link metric is assessed at the receiver, as on a (typically) 778 wireless link, that is the better informed as to link information. 779 Both incoming and outgoing link information is used by OLSRv2, the 780 distinctions in the specification must be clearly followed. 782 This specification also defines both incoming annd outgoing neighbor 783 metrics for each symmetric 1-hop neighbor, these being the minimum 784 value of the link metrics in the same direction for all symmstric 785 links with that neighbor. Note that this means that all neighbor 786 metric values are link metric values and that specification of, for 787 example, link metric value encoding also includes neighbor metric 788 values. 790 This specification does not define the nature of the link metric. 791 However this psecification allows, through use of the type extension 792 of a defined Address Block TLV, for link metrics with specific 793 meanings to be defined and either allocated by IANA or privately 794 used. Each HELLO or TC message carrying link (or neighbor) metrics 795 thus indicates which link metric information it is carrying, thus 796 allowing routers to determine if they can interoperate. If link 797 metrics require additional signaling to determine their values, 798 whether in HELLO messages or otherwise, then this is permitted but is 799 outside the scope of this specification. 801 Users are advised that they should carefully consider how to use link 802 metrics. In particular they should not simply default to use of all 803 links with equal metrics (i.e. hop count) without careful 804 consideration of whether that is advisable or not. 806 4.6. Routing Set 808 The purpose of the Routing Set is to determine and record routes 809 (local interface network address and next hop interface network 810 address) to all possible routable addresses advertised by this 811 protocol, as well as of all destinations that are local, i.e., within 812 one hop, to the router (whether using routable addresses or not). 813 Only symmetric links are used in such routes. 815 It is intended that the Routing Set can be used for packet routing, 816 by using its contents to update IP's routing tables. That update, 817 and whether any Routing Tuples are not used in IP's routing table, is 818 outside the scope of this specification. 820 The signaling in this specification has been designed so that a 821 "backbone" Topology Graph of routers, each identified by its 822 originator address, with at most one direct connection between any 823 pair of routers, can be constructed (from the Neighbor Set and the 824 Router Topology Set) using a suitable minimum path length algorithm. 825 This Topology Graph can, then, have other network addresses (routable 826 or of symmetric 1-hop neighbors) added to it (using the Interface 827 Information Bases, the Routable Address Topology Set and the Attached 828 Network Set). 830 5. Protocol Parameters and Constants 832 The parameters and constants used in this specification are those 833 defined in [RFC6130] plus those defined in this section. The 834 separation in [RFC6130] into interface parameters, router parameters 835 and constants is also used in this specification. 837 As for the parameters in [RFC6130], parameters defined in this 838 specification may be changed dynamically by a router, and need not be 839 the same on different routers, even in the same MANET, or, for 840 interface parameters, on different interfaces of the same router. 842 5.1. Protocol and Port Numbers 844 This protocol specifies TC messages, which are included in packets as 845 defined by [RFC5444]. These packets may be sent either using the 846 "manet" protocol number or the "manet" UDP well-known port number, as 847 specified in [RFC5498]. 849 TC messages and HELLO messages [RFC6130] SHOULD, in a given 850 deployment of this protocol, both be using the same of either of IP 851 or UDP, in order that it is possible to combine messages of both 852 protocols into the same [RFC5444] packet for transmission. 854 5.2. Multicast Address 856 This protocol specifies TC messages, which are included in packets as 857 defined by [RFC5444]. These packets MAY be transmitted using the 858 link local multicast address "LL-MANET-Routers", as specified in 859 [RFC5498]. 861 5.3. Interface Parameters 863 5.3.1. Received Message Validity Time 865 The following parameter manages the validity time of recorded 866 received message information: 868 RX_HOLD_TIME - is the period after receipt of a message by the 869 appropriate OLSRv2 interface of this router for which that 870 information is recorded, in order that the message is recognized 871 as having been previously received on this OLSRv2 interface. 873 The following constraints apply to this parameters: 875 o RX_HOLD_TIME > 0 877 o RX_HOLD_TIME SHOULD be greater than the maximum difference in time 878 that a message may take to traverse the MANET, taking into account 879 any message forwarding jitter as well as propagation, queuing, and 880 processing delays. 882 5.4. Router Parameters 884 5.4.1. Local History Times 886 The following router parameter manages the time for which local 887 information is retained: 889 O_HOLD_TIME - is used to define the time for which a recently used 890 and replaced originator address is used to recognize the router's 891 own messages. 893 The following constraint applies to this parameter: 895 o O_HOLD_TIME >= 0 897 5.4.2. Link_Metric_Parameters 899 All routes found using this specification use a single link metric 900 type that is specified by the router parameter LINK_METRIC_TYPE, 901 which may take any value from 0 to 255, inclusive. 903 5.4.3. Message Intervals 905 The following parameters regulate TC message transmissions by a 906 router. TC messages are usually sent periodically, but MAY also be 907 sent in response to changes in the router's Neighbor Set and/or Local 908 Attached Network Set. In a highly dynamic network, and with a larger 909 value of the parameter TC_INTERVAL and a smaller value of the 910 parameter TC_MIN_INTERVAL, TC messages may be transmitted more often 911 in response to changes than periodically. However because a router 912 has no knowledge of, for example, routers remote to it (i.e., beyond 913 two hops away) joining the network, TC messages MUST NOT be sent 914 purely responsively. 916 TC_INTERVAL - is the maximum time between the transmission of two 917 successive TC messages by this router. When no TC messages are 918 sent in response to local network changes (by design, or because 919 the local network is not changing) then TC messages SHOULD be sent 920 at a regular interval TC_INTERVAL, possibly modified by jitter as 921 specified in [RFC5148]. 923 TC_MIN_INTERVAL - is the minimum interval between transmission of 924 two successive TC messages by this router. (This minimum interval 925 MAY be modified by jitter, as specified in [RFC5148].) 927 The following constraints apply to these parameters: 929 o TC_INTERVAL > 0 931 o TC_MIN_INTERVAL >= 0 933 o TC_INTERVAL >= TC_MIN_INTERVAL 935 o If TLVs with Type = INTERVAL_TIME, as defined in [RFC5497], are 936 included in TC messages, then TC_INTERVAL MUST be representable as 937 described in [RFC5497]. 939 5.4.4. Advertised Information Validity Times 941 The following parameters manage the validity time of information 942 advertised in TC messages: 944 T_HOLD_TIME - is used to define the minimum value in the TLV with 945 Type = VALIDITY_TIME included in all TC messages sent by this 946 router. If a single value of parameter TC_HOP_LIMIT (see 947 Section 5.4.7) is used then this will be the only value in that 948 TLV. 950 A_HOLD_TIME - is the period during which TC messages are sent after 951 they no longer have any advertised information to report, but are 952 sent in order to accelerate outdated information removal by other 953 routers. 955 The following constraints apply to these parameters: 957 o T_HOLD_TIME > 0 959 o A_HOLD_TIME >= 0 961 o T_HOLD_TIME >= TC_INTERVAL 963 o If TC messages can be lost, then both T_HOLD_TIME and A_HOLD_TIME 964 SHOULD be significantly greater than TC_INTERVAL; a value >= 3 x 965 TC_INTERVAL is RECOMMENDED. 967 o T_HOLD_TIME MUST be representable as described in [RFC5497]. 969 5.4.5. Processing and Forwarding Validity Times 971 The following parameters manage the processing and forwarding 972 validity time of recorded message information: 974 P_HOLD_TIME is the period after receipt of a message that is 975 processed by this router for which that information is recorded, 976 in order that the message is not processed again if received 977 again. 979 F_HOLD_TIME is the period after receipt of a message that is 980 forwarded by this router for which that information is recorded, 981 in order that the message is not forwarded again if received 982 again. 984 The following constraints apply to these parameters: 986 o P_HOLD_TIME > 0 988 o F_HOLD_TIME > 0 990 o Both of these parameters SHOULD be greater than the maximum 991 difference in time that a message may take to traverse the MANET, 992 taking into account any message forwarding jitter as well as 993 propagation, queuing, and processing delays. 995 5.4.6. Jitter 997 If jitter, as defined in [RFC5148], is used then the governing jitter 998 parameters are as follows: 1000 TP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 1001 for periodically generated TC messages sent by this router. 1003 TT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] 1004 for externally triggered TC messages sent by this router. 1006 F_MAXJITTER - represents the default value of MAXJITTER used in 1007 [RFC5148] for messages forwarded by this router. However before 1008 using F_MAXJITTER a router MAY attempt to deduce a more 1009 appropriate value of MAXJITTER, for example based on any TLVs with 1010 Type = INTERVAL_TIME or Type = VALIDITY_TIME contained in the 1011 message to be forwarded. 1013 For constraints on these parameters see [RFC5148]. 1015 5.4.7. Hop Limit 1017 The parameter TC_HOP_LIMIT is the hop limit set in each TC message. 1018 TC_HOP_LIMIT MAY be a single fixed value, or MAY be different in TC 1019 messages sent by the same router. However each other router, at any 1020 hop count distance, SHOULD see a regular pattern of TC messages in 1021 order that meaningful values of TLVs with Type = INTERVAL_TIME and 1022 Type = VALIDITY_TIME at each hop count distance can be included as 1023 defined in [RFC5497]. Thus the pattern of TC_HOP_LIMIT SHOULD be 1024 defined to have this property. For example the repeating pattern 1025 (255 4 4) satisfies this property (having period TC_INTERVAL at hop 1026 counts up to 4, inclusive, and 3 x TC_INTERVAL at hop counts greater 1027 than 4), but the repeating pattern (255 255 4 4) does not satisfy 1028 this property because at hop counts greater than 4, message intervals 1029 are alternately TC_INTERVAL and 3 x TC_INTERVAL. 1031 The following constraints apply to this parameter: 1033 o The maximum value of TC_HOP_LIMIT >= the network diameter in hops, 1034 a value of 255 is RECOMMENDED. Note that if using a pattern of 1035 different values of TC_HOP_LIMIT as described above, then only the 1036 maximum value in the pattern is so constrained. 1038 o All values of TC_HOP_LIMIT >= 2. 1040 5.4.8. Willingness 1042 Each router has two willingness parameters: WILL_FLOODING and 1043 WILL_ROUTING, each of which MUST be in the range WILL_NEVER to 1044 WILL_ALWAYS, inclusive. 1046 WILL_FLOODING represents the router's willingness to be selected as a 1047 flooding MPR and hence to participate in MPR flooding, in particular 1048 of TC messages. 1050 WILL_ROUTING represents the router's willingness to be selected as a 1051 routing MPR and hence to be an intermediate router on routes. 1053 In either case, the higher the value, the greater the router's 1054 willingness to be a flooding or routing MPR, respectively. If a 1055 router has a willingness value of WILL_NEVER (the lowest possible 1056 value) it does not perform the corresponding task. A MANET using 1057 this protocol with too many routers having either willingness value 1058 equal to WILL_NEVER will not function; it MUST be ensured, by 1059 administrative or other means, that this does not happen. 1061 If a router has a willingness value equal to WILL_ALWAYS (the highest 1062 possible value) then it will always be selected as a flooding or 1063 routing MPR, respectively, by all symmetric 1-hop neighbors. 1065 A MANET in which all routers have WILL_FLOODING = WILL_ALWAYS, the 1066 flooding operation will effectively disable optimizations, and 1067 perform as classic flooding. 1069 A router, which has WILL_ROUTING = WILL_NEVER will not act as an 1070 intermediate router in the MANET. Such a router can, act as a 1071 source, destination or gateway to another routing domain. 1073 Different routers MAY have different values for WILL_FLOODING and/or 1074 WILL_ROUTING. A router that has both WILL_FLOODING = WILL_DEFAULT 1075 and WILL_ROUTING = WILL_DEFAULT need not include an MPR_WILLING TLV 1076 in its HELLO messages. 1078 The following constraints apply to these parameters: 1080 o WILL_FLOODING >= WILL_NEVER 1082 o WILL_FLOODING <= WILL_ALWAYS 1084 o WILL_ROUTING >= WILL_NEVER 1086 o WILL_ROUTING <= WILL_ALWAYS 1088 5.5. Parameter Change Constraints 1090 If protocol parameters are changed dynamically, then the constraints 1091 in this section apply. 1093 RX_HOLD_TIME 1095 * If RX_HOLD_TIME for an OLSRv2 interface changes, then the 1096 expiry time for all Received Tuples for that OLSRv2 interface 1097 MAY be changed. 1099 O_HOLD_TIME 1101 * If O_HOLD_TIME for a router changes, then the expiry time for 1102 all Originator Tuples MAY be changed. 1104 TC_INTERVAL 1106 * If the TC_INTERVAL for a router increases, then the next TC 1107 message generated by this router MUST be generated according to 1108 the previous, shorter, TC_INTERVAL. Additional subsequent TC 1109 messages MAY be generated according to the previous, shorter, 1110 TC_INTERVAL. 1112 * If the TC_INTERVAL for a router decreases, then the following 1113 TC messages from this router MUST be generated according to the 1114 current, shorter, TC_INTERVAL. 1116 P_HOLD_TIME 1118 * If P_HOLD_TIME changes, then the expiry time for all Processed 1119 Tuples MAY be changed. 1121 F_HOLD_TIME 1123 * If F_HOLD_TIME changes, then the expiry time for all Forwarded 1124 Tuples MAY be changed. 1126 TP_MAXJITTER 1128 * If TP_MAXJITTER changes, then the periodic TC message schedule 1129 on this router MAY be changed immediately. 1131 TT_MAXJITTER 1133 * If TT_MAXJITTER changes, then externally triggered TC messages 1134 on this router MAY be rescheduled. 1136 F_MAXJITTER 1138 * If F_MAXJITTER changes, then TC messages waiting to be 1139 forwarded with a delay based on this parameter MAY be 1140 rescheduled. 1142 TC_HOP_LIMIT 1144 * If TC_HOP_LIMIT changes, and the router uses multiple values 1145 after the change, then message intervals and validity times 1146 included in TC messages MUST be respected. The simplest way to 1147 do this is to start any new repeating pattern of TC_HOP_LIMIT 1148 values with its largest value. 1150 LINK_METRIC_TYPE 1152 * If LINK_METRIC_TYPE changes then all link metric information 1153 recorded by the router is invalid. The router MUST take the 1154 following actions, and all consequent actions described in 1155 Section 17 and [RFC6130]. 1157 + For each Link Tuple in any Link Set, either update 1158 L_in_metric (the value MAXIMUM_METRIC MAY be used) or remove 1159 the Link Tuple from the Link Set. 1161 + For each Link Tuple that is not removed, set: 1163 - L_out_metric := UNKNOWN_METRIC; 1165 - L_SYM_time := expired; 1167 - L_MPR_selector := false. 1169 + Remove all Router Topology Tuples, Routable Address Topology 1170 Tuples, Attached Network Tuples and Routing Tuples from 1171 their respective protocol sets in the Topology Information 1172 Base. 1174 5.6. Constants 1176 5.6.1. Link Metric Constants 1178 The constant minimum, maximum and default metric values are defined 1179 by: 1181 o MINIMUM_METRIC := 1 1182 o MAXIMUM_METRIC := 16776960 1184 o DEFAULT_METRIC := 256 1186 The symbolic value UNKNOWN_METRIC is defined in Section 6.1. 1188 6. Link Metric Values 1190 A router records a link metric value for each direction of a link of 1191 which it has knowledge. These link metric values are used to create 1192 metrics for routes by the addition of link metric values. 1194 6.1. Link Metric Representation 1196 Link metric are reported in messages using a compressed 1197 representation that occupies 12 bits, a 4 bit field and an 8 bit 1198 field. The compressed representation represents positive integer 1199 values with a minimum value of 1 and a maximum value that is slightly 1200 smaller than the maximum 24 bit value. Only those values that have 1201 exact representation in the compressed form are used. Route metrics 1202 are the summation of no more then 255 link metric values, and can 1203 therefore be represented using no more than 32 bits. 1205 Link and route metrics used in the Information Bases defined in this 1206 specification refer to the uncompressed values, and arithmetic 1207 involving them does likewise, and assumes full precision in the 1208 result. (How an implementation records the values is not part of 1209 this specification, as long as it behaves as if recording 1210 uncompressed values. An implementation can, for example, use 32 bit 1211 values for all link and route metrics.) 1213 In some cases a link metric value may be unknown. This is indicated 1214 in this specification by the value UNKNOWN_METRIC. An implementation 1215 may use any representation of UNKNOWN_METRIC as it is never included 1216 in messages or used in any computation. (Possible values are zero, 1217 or any value greater than the maximum representable metric value.) 1219 6.2. Link Metric Compressed Form 1221 The 12-bit compressed form of a link metric uses a modified form of a 1222 representation with as 8-bit mantissa (denoted b) and a 4-bit 1223 exponent (denoted a). Note that if represented as the 12 bit value 1224 256a+b then the ordering of those 12 bit values is identical to the 1225 ordering of the represented values. 1227 The value so represented is (257+b)2^a - 256, where ^ denotes 1228 exponentiation. This has a minimum value (when a = 0 and b = 0) of 1229 MINUMUM_METRIC = 1 and a maximum value (when a = 15 and b = 255) of 1230 MAXIMUM_METRIC = 2^24 - 256. 1232 An algorithm for computing a and b for the smallest representable 1233 value not less than a link metric value v such that MINIMUM_METRIC <= 1234 v <= MAXIMUM_METRIC is: 1236 1. Find the smallest integer a such that v + 256 <= 2^(a + 9). 1238 2. Set b := (v - 256(2^a - 1)) / (2^a) - 1, rounded up to the 1239 nearest integer. 1241 To allow for more efficient messages, a default link metric 1242 DEFAULT_METRIC is defined, which can be omitted from messages. Note 1243 that this is not the same as the link metric value that should be 1244 used when this specification requires a link metric, but no 1245 information about a link, beyond that a HELLO message has been 1246 received using that link, is available. In this case the link metric 1247 used SHOULD be MAXIMUM_METRIC. 1249 7. Local Information Base 1251 The Local Information Base, as defined for each router in [RFC6130], 1252 is extended by this protocol by: 1254 o Recording the router's originator address. The originator address 1255 MUST be unique to this router. It MUST NOT be used by any other 1256 router as an originator address. It MAY be included in any 1257 network address in any I_local_iface_addr_list of this router, it 1258 MUST NOT be included in any network address in any 1259 I_local_iface_addr_list of any other router. It MAY be included 1260 in, but MUST NOT be equal to, the AL_net_addr in any Local 1261 Attached Network Tuple in this or any other router. 1263 o The addition of an Originator Set, defined in Section 7.1, and a 1264 Local Attached Network Set, defined in Section 7.2. 1266 All routable addresses of the router for which it is to accept 1267 packets as destination MUST be included in the Local Interface Set or 1268 the Local Attached Network Set. 1270 7.1. Originator Set 1272 A router's Originator Set records addresses that were recently used 1273 as originator addresses by this router. If a router's originator 1274 address is immutable then this set is always empty and MAY be 1275 omitted. It consists of Originator Tuples: 1277 (O_orig_addr, O_time) 1279 where: 1281 O_orig_addr - is a recently used originator address, note that this 1282 does not include a prefix length; 1284 O_time - specifies the time at which this Tuple expires and MUST be 1285 removed. 1287 7.2. Local Attached Network Set 1289 A router's Local Attached Network Set records its local non-OLSRv2 1290 interfaces via which it can act as gateways to other networks. The 1291 Local Attached Network Set is not modified by this protocol. This 1292 protocol MAY respond to changes to the Local Attached Network Set, 1293 which MUST reflect corresponding changes in the router's status. It 1294 consists of Local Attached Network Tuples: 1296 (AL_net_addr, AL_dist, AL_metric) 1298 where: 1300 AL_net_addr - is the network address of an attached network which 1301 can be reached via this router. This SHOULD be a routable 1302 address. It is constrained as described below. 1304 AL_dist - is the number of hops to the network with network address 1305 AL_net_addr from this router. 1307 AL_metric - is the metric of the link to the attached network with 1308 address AL_net_addr from this router; 1310 Attached networks local to this router only (i.e., not reachable 1311 except via this router) SHOULD be treated as local non-MANET 1312 interfaces, and added to the Local Interface Set, as specified in 1313 [RFC6130], rather than be added to the Local Attached Network Set. 1315 Because an attached network is not specific to the router, and may be 1316 outside the MANET, an attached network MAY also be attached to other 1317 routers. Routing to an AL_net_addr will use maximum prefix length 1318 matching; consequently an AL_net_addr MAY include, but MUST NOT equal 1319 or be included in, any network address which is of any interface of 1320 any router (i.e., is included in any I_local_iface_addr_list) or 1321 equal any router's originator address. 1323 It is not the responsibility of this protocol to maintain routes from 1324 this router to networks recorded in the Local Attached Network Set. 1326 Local Attached Neighbor Tuples are removed from the Local Attached 1327 Network Set only when the routers' local attached network 1328 configuration changes, i.e., they are not subject to timer-based 1329 expiration or changes due to received messages. 1331 8. Interface Information Base 1333 An Interface Information Base, as defined in [RFC6130], is maintained 1334 for each OLSRv2 interface. Its Link Set and 2-Hop Set are modified 1335 by this protocol. 1337 The Link Set is modified by adding these additional elements to each 1338 Link Tuple: 1340 L_in_metric - is the metric of the link from the OLSRv2 interface 1341 with addresses L_neighbor_iface_addr_list to this OLSRv2 1342 interface; 1344 L_out_metric - is the metric of the link to the OLSRv2 interface 1345 with addresses L_neighbor_iface_addr_list from this OLSRv2 1346 interface; 1348 L_mpr_selector - is a boolean flag, describing if this neighbor has 1349 selected this router as a flooding MPR, i.e., is a flooding MPR 1350 selector of this router. 1352 L_in_metric will be specified by a process that is external to this 1353 specification. Any Link Tuple with L_status = HEARD or L_status = 1354 SYMMETRIC MUST have a specified value of L_in_metric. 1356 A Link Tuple created (but not updated) by [RFC6130] MUST set: 1358 o L_in_metric := unknown; 1360 o L_out_metric := unknown; 1362 o L_mpr_selector := false. 1364 The 2-Hop Set is modified by adding these additional elements to each 1365 2-Hop Tuple: 1367 N2_in_metric - is the router metric from the router with address 1368 N2_2hop_iface_addr to the router with OLSRv2 interface addresses 1369 N2_neighbor_iface_addr_list; 1371 N2_out_metric - is the router metric to the router with address 1372 N2_2hop_iface_addr from the router with OLSRv2 interface addresses 1373 N2_neighbor_iface_addr_list. 1375 A Neighbor Tuple created (but not updated) by [RFC6130] MUST set: 1377 o N2_in_metric := unknown; 1379 o N2_out_metric := unknown. 1381 9. Neighbor Information Base 1383 An Neighbor Information Base, as defined in [RFC6130], is maintained 1384 for each router. It is modified by this protocol by adding these 1385 additional elements to each Neighbor Tuple in the Neighbor Set: 1387 N_orig_addr - is the neighbor's originator address, which may be 1388 unknown. Note that this originator address does not include a 1389 prefix length; 1391 N_in_metric - is the router metric of any link from this neighbor to 1392 this router, i.e., the minimum of all corresponding L_in_metric 1393 with L_status = SYMMETRIC, unspecified if there are no such Link 1394 Tuples; 1396 N_out_metric - is the router metric of any link from this router to 1397 this neighbor, i.e., the minimum of all corresponding L_out_metric 1398 with L_status = SYMMETRIC, unspecified if there are no such Link 1399 Tuples; 1401 N_will_flooding - is the neighbor's willingness to be selected as a 1402 flooding MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1403 inclusive; 1405 N_will_routing - is the neighbor's willingness to be selected as a 1406 routing MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1407 inclusive; 1409 N_flooding_mpr - is a boolean flag, describing if this neighbor is 1410 selected as a flooding MPR by this router; 1412 N_routing_mpr - is a boolean flag, describing if this neighbor is 1413 selected as a routing MPR by this router; 1415 N_mpr_selector - is a boolean flag, describing if this neighbor has 1416 selected this router as a routing MPR, i.e., is a routing MPR 1417 selector of this router. 1419 N_advertised - is a boolean flag, describing if this router has 1420 elected to advertise a link to this neighbor in its TC messages. 1422 A Neighbor Tuple created (but not updated) by [RFC6130] MUST set: 1424 o N_orig_addr := unknown; 1426 o N_in_metric := unknown; 1428 o N_out_metric := unknown; 1430 o N_will_flooding := WILL_NEVER; 1432 o N_will_routing := WILL_NEVER; 1434 o N_routing_mpr := false; 1436 o N_flooding_mpr := false; 1438 o N_mpr_selector := false; 1440 o N_advertised := false. 1442 The Neighbor Information Base also includes a variable, the 1443 Advertised Neighbor Sequence Number (ANSN), whose value is included 1444 in TC messages to indicate the freshness of the information 1445 transmitted. The ANSN is incremented whenever advertised information 1446 (the originator and routable addresses included in Neighbor Tuples 1447 with N_advertised = true, and local attached networks recorded in the 1448 Local Attached Network Set in the Local Information Base) changes, 1449 including addition or removal of such information. 1451 10. Topology Information Base 1453 The Topology Information Base, defined for each router by this 1454 specification, stores information received in TC messages, in the 1455 Advertising Remote Router Set, the Router Topology Set, the Routable 1456 Address Topology Set and the Attached Network Set. 1458 Additionally, a Routing Set is maintained, derived from the 1459 information recorded in the Local Information Base, the Interface 1460 Information Bases, the Neighbor Information Base and the rest of the 1461 Topology Information Base. 1463 10.1. Advertising Remote Router Set 1465 A router's Advertising Remote Router Set records information 1466 describing each remote router in the network that transmits TC 1467 messages, allowing outdated TC messages to be recognized and 1468 discarded. It consists of Advertising Remote Router Tuples: 1470 (AR_orig_addr, AR_seq_number, AR_time) 1472 where: 1474 AR_orig_addr - is the originator address of a received TC message, 1475 note that this does not include a prefix length; 1477 AR_seq_number - is the greatest ANSN in any TC message received 1478 which originated from the router with originator address 1479 AR_orig_addr (i.e., which contributed to the information contained 1480 in this Tuple); 1482 AR_time - is the time at which this Tuple expires and MUST be 1483 removed. 1485 10.2. Router Topology Set 1487 A router's Topology Set records topology information about the links 1488 between routers in the MANET. It consists of Router Topology Tuples: 1490 (TR_from_orig_addr, TR_to_orig_addr, TR_seq_number, TR_metric, 1491 TR_time) 1493 where: 1495 TR_from_orig_addr - is the originator address of a router which can 1496 reach the router with originator address TR_to_orig_addr in one 1497 hop, note that this does not include a prefix length; 1499 TR_to_orig_addr - is the originator address of a router which can be 1500 reached by the router with originator address TR_to_orig_addr in 1501 one hop, note that this does not include a prefix length; 1503 TR_seq_number - is the greatest ANSN in any TC message received 1504 which originated from the router with originator address 1505 TR_from_orig_addr (i.e., which contributed to the information 1506 contained in this Tuple); 1508 TR_metric - is the router metric from the router with originator 1509 address TR_from_orig_addr to the router with originator address 1510 TR_to_orig_addr; 1512 TR_time - specifies the time at which this Tuple expires and MUST be 1513 removed. 1515 10.3. Routable Address Topology Set 1517 A router's Routable Address Topology Set records topology information 1518 about the routable addresses within the MANET, and via which routers 1519 they may be reached. It consists of Routable Address Topology 1520 Tuples: 1522 (TA_from_orig_addr, TA_dest_addr, TA_seq_number, TA_metric, 1523 TA_time) 1525 where: 1527 TA_from_orig_addr - is the originator address of a router which can 1528 reach the router with routable address TA_dest_addr in one hop, 1529 note that this does not include a prefix length; 1531 TA_dest_addr - is a routable address of a router which can be 1532 reached by the router with originator address TA_from_orig_addr in 1533 one hop; 1535 TA_seq_number - is the greatest ANSN in any TC message received 1536 which originated from the router with originator address 1537 TA_from_orig_addr (i.e., which contributed to the information 1538 contained in this Tuple); 1540 TA_metric - is the router metric from the router with originator 1541 address TA_from_orig_addr to the router with OLSRv2 interface 1542 address TA_dest_addr; 1544 TA_time - specifies the time at which this Tuple expires and MUST be 1545 removed. 1547 10.4. Attached Network Set 1549 A router's Attached Network Set records information about networks 1550 (which may be outside the MANET) attached to other routers and their 1551 routable addresses. It consists of Attached Network Tuples: 1553 (AN_orig_addr, AN_net_addr, AN_seq_number, AN_dist, AN_metric, 1554 AN_time) 1556 where: 1558 AN_orig_addr - is the originator address of a router which can act 1559 as gateway to the network with network address AN_net_addr, note 1560 that this does not include a prefix length; 1562 AN_net_addr - is the network address of an attached network, which 1563 may be reached via the router with originator address 1564 AN_orig_addr; 1566 AN_seq_number - is the greatest ANSN in any TC message received 1567 which originated from the router with originator address 1568 AN_orig_addr (i.e., which contributed to the information contained 1569 in this Tuple); 1571 AN_dist - is the number of hops to the network with network address 1572 AN_net_addr from the router with originator address AN_orig_addr; 1574 AN_metric - is the metric of the link from the router with 1575 originator address AN_orig_addr to the attached network with 1576 address AN_net_addr; 1578 AN_time - specifies the time at which this Tuple expires and MUST be 1579 removed. 1581 10.5. Routing Set 1583 A router's Routing Set records the first hop along a selected path to 1584 each destination for which any such path is known. It consists of 1585 Routing Tuples: 1587 (R_dest_addr, R_next_iface_addr, R_local_iface_addr, R_dist, 1588 R_metric) 1590 where: 1592 R_dest_addr - is the network address of the destination, either the 1593 network address of an interface of a destination router, or the 1594 network address of an attached network; 1596 R_next_iface_addr - is the network address of the "next hop" on the 1597 selected path to the destination; 1599 R_local_iface_addr - is the network address of the local OLSRv2 1600 interface over which a packet MUST be sent to reach the 1601 destination by the selected path. 1603 R_dist - is the number of hops on the selected path to the 1604 destination; 1606 R_metric - is the metric of the route to the destination with 1607 address R_dest_addr. 1609 The Routing Set for a router is derived from the contents of other 1610 protocol Sets of the router (the Link Sets, the Neighbor Set, the 1611 Router Topology Set, the Routable Address Topology Set, the Attached 1612 Network Set, and OPTIONALLY the Two Hop Sets). The Routing Set is 1613 updated (Routing Tuples added or removed, or the complete Routing Set 1614 recalculated) when routing paths are calculated, based on changes to 1615 these other protocol Sets. Routing Tuples are not subject to timer- 1616 based expiration. 1618 11. Received Message Information Base 1620 The Received Message Information Base, defined by this specification, 1621 records information required to ensure that a message is processed at 1622 most once and is forwarded at most once per OLSRv2 interface of a 1623 router, using MPR flooding. 1625 11.1. Received Set 1627 A router has a Received Set per OLSRv2 interface. Each Received Set 1628 records the signatures of messages which have been received over that 1629 OLSRv2 interface. Each consists of Received Tuples: 1631 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 1633 where: 1635 RX_type - is the received Message Type; 1637 RX_orig_addr - is the originator address of the received message, 1638 note that this does not include a prefix length; 1640 RX_seq_number - is the message sequence number of the received 1641 message; 1643 RX_time - specifies the time at which this Tuple expires and MUST be 1644 removed. 1646 11.2. Processed Set 1648 A router has a single Processed Set which records signatures of 1649 messages which have been processed by the router. It consists of 1650 Processed Tuples: 1652 (P_type, P_orig_addr, P_seq_number, P_time) 1654 where: 1656 P_type - is the processed Message Type; 1658 P_orig_addr - is the originator address of the processed message, 1659 note that this does not include a prefix length; 1661 P_seq_number - is the message sequence number of the processed 1662 message; 1664 P_time - specifies the time at which this Tuple expires and MUST be 1665 removed. 1667 11.3. Forwarded Set 1669 A router has a single Forwarded Set which records signatures of 1670 messages which have been forwarded by the router. It consists of 1671 Forwarded Tuples: 1673 (F_type, F_orig_addr, F_seq_number, F_time) 1675 where: 1677 F_type - is the forwarded Message Type; 1679 F_orig_addr - is the originator address of the forwarded message, 1680 note that this does not include a prefix length; 1682 F_seq_number - is the message sequence number of the forwarded 1683 message; 1685 F_time - specifies the time at which this Tuple expires and MUST be 1686 removed. 1688 12. Information Base Properties 1690 As part of this specification, in a number of cases there is a 1691 natural correspondence from a Protocol Tuple in one Protocol Set to a 1692 single Protocol Tuple in another Protocol Set, in the same or another 1693 Information Base. The latter Protocol Tuple is referred to as 1694 "corresponding" to the former Protocol Tuple. 1696 Specific examples of corresponding Protocol Tuples include: 1698 o There is a Local Interface Tuple corresponding to each Link Tuple, 1699 where the Link Tuple is in the Link Set for an OLSRv2 interface, 1700 and the Local Interface Tuple represents that OLSRv2 interface. 1702 o There is a Neighbor Tuple corresponding to each Link Tuple which 1703 has L_HEARD_time not expired, such that N_neighbor_addr_list 1704 contains L_neighbor_iface_addr_list. 1706 o There is a Link Tuple (in the Link Set in the same Interface 1707 Information Base) corresponding to each 2-Hop Tuple such that 1708 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 1710 o There is a Neighbor Tuple corresponding to each 2-Hop Tuple, such 1711 that N_neighbor_addr_list contains N2_neighbor_iface_addr_list. 1712 (This is the Neighbor Tuple corresponding to the Link Tuple that 1713 corresponds to the 2-Hop Tuple.) 1715 o There is an Advertising Remote Router Tuple corresponding to each 1716 Router Topology Tuple such that AR_orig_addr = TR_from_orig_addr. 1718 o There is an Advertising Remote Router Tuple corresponding to each 1719 Routable Address Topology Tuple such that AR_orig_addr = 1720 TA_from_orig_addr. 1722 o There is an Advertising Remote Router Tuple corresponding to each 1723 Attached Network Tuple such that AR_orig_addr = AN_orig_addr. 1725 o There is an Neighbor Tuple corresponding to each Routing Tuple 1726 such that N_neighbor_addr_list contains R_next_iface_addr. 1728 Addresses or network addresses with the following properties are 1729 considered as "fully owned" by a router when processing a received 1730 message: 1732 o Equaling its originator address, OR; 1734 o Equaling the O_orig_addr in an Originator Tuple, OR; 1736 o Equaling or being a sub-range of the I_local_iface_addr_list in a 1737 Local Interface Tuple, OR; 1739 o Equaling or being a sub-range of the IR_local_iface_addr in a 1740 Removed Interface Address Tuple, OR; 1742 o Equaling an AL_net_addr in a Local Attached Network Tuple. 1744 Addresses or network addresses with the following properties are 1745 considered as "partially owned" (which may include being fully owned) 1746 by a router when processing a received message: 1748 o Overlapping (equaling or containing) its originator address, OR; 1750 o Overlapping (equaling or containing) the O_orig_addr in an 1751 Originator Tuple, OR; 1753 o Overlapping the I_local_iface_addr_list in a Local Interface 1754 Tuple, OR; 1756 o Overlapping the IR_local_iface_addr in a Removed Interface Address 1757 Tuple, OR; 1759 o Equaling or having as a sub-range an AL_net_addr in a Local 1760 Attached Network Tuple. 1762 13. Packets and Messages 1764 The packet and message format used by this protocol is defined in 1765 [RFC5444]. Except as otherwise noted, options defined in [RFC5444] 1766 may be freely used, in particular alternative formats defined by 1767 packet, message, Address Block and TLV flags. 1769 This section describes the usage of the packets and messages defined 1770 in [RFC5444] by this specification, and the TLVs defined by, and used 1771 in, this specification. 1773 13.1. Messages 1775 Routers using this protocol exchange information through messages. 1776 The message types used by this protocol are the HELLO message and the 1777 TC message. The HELLO message is defined by [RFC6130] and extended 1778 by this specification, see Section 15. The TC message is defined by 1779 this specification, see Section 16. 1781 13.2. Packets 1783 One or more messages sent by a router at the same time SHOULD be 1784 combined into a single packet, subject to any constraints on maximum 1785 packet size (such as derived from the MTU over a local single hop) 1786 that MAY be imposed. These messages may have originated at the 1787 sending router, or have originated at another router and are being 1788 forwarded by the sending router. Messages with different originating 1789 routers MAY be combined for transmission within the same packet. 1790 Messages from other protocols defined using [RFC5444], including but 1791 not limited to [RFC6130], MAY be combined for transmission within the 1792 same packet. This specification does not define or use any contents 1793 of the Packet Header. 1795 Forwarded messages MAY be jittered as described in [RFC5148], 1796 including the observation that the forwarding jitter of all messages 1797 received in a single packet SHOULD be the same. The value of 1798 MAXJITTER used in jittering a forwarded message MAY be based on 1799 information in that message (in particular any Message TLVs with Type 1800 = INTERVAL_TIME or Type = VALIDITY_TIME) or otherwise SHOULD be with 1801 a maximum delay of F_MAXJITTER. A router MAY modify the jitter 1802 applied to a message in order to more efficiently combine messages in 1803 packets, as long as the maximum jitter is not exceeded. 1805 13.3. TLVs 1807 This specification defines 2 Message TLVs and 4 Address Block TLVs. 1809 All references in this specification to TLVs that do not indicate a 1810 type extension, assume Type Extension = 0. TLVs in processed 1811 messages with a type extension which is neither zero as so assumed, 1812 nor a specifically indicated non-zero type extension, are ignored. 1814 13.3.1. Message TLVs 1816 The MPR_WILLING TLV is used in HELLO messages. At most one 1817 MPR_WILLING TLV may appear in any message. 1819 +-------------+--------------+--------------------------------------+ 1820 | Type | Value Length | Value | 1821 +-------------+--------------+--------------------------------------+ 1822 | MPR_WILLING | 1 octet | Bits 0-3 encode the parameter | 1823 | | | WILL_FLOODING; bits 4-7 encode the | 1824 | | | parameter WILL_ROUTING. | 1825 +-------------+--------------+--------------------------------------+ 1827 Table 1: MPR_WILLING TLV definition 1829 The CONT_SEQ_NUM TLV is used in TC messages. At most one 1830 CONT_SEQ_NUM TLV may appear in any message. 1832 +--------------+--------------+-------------------------------------+ 1833 | Type | Value Length | Value | 1834 +--------------+--------------+-------------------------------------+ 1835 | CONT_SEQ_NUM | 2 octets | The ANSN contained in the Neighbor | 1836 | | | Information Base. | 1837 +--------------+--------------+-------------------------------------+ 1839 Table 2: CONT_SEQ_NUM TLV definition 1841 13.3.2. Address Block TLVs 1843 The LINK_METRIC TLV is used in HELLO messages and TC messages. It 1844 may use any type extension; only LINK_METRIC TLVs with type extension 1845 equal to LINK_METRIC_TYPE will be used by this specification. At 1846 most one link metric value of any given kind (link or neighbor) and 1847 direction may be associated with any address. 1849 +-------------+--------------+--------------------------------------+ 1850 | Type | Value Length | Value | 1851 +-------------+--------------+--------------------------------------+ 1852 | LINK_METRIC | 2 octets | Bits 0-3 indicates kind(s) and | 1853 | | | direction(s), Bits 4-7 indicate | 1854 | | | exponent (a), Bits 8-15 indicate | 1855 | | | mantissa (b) | 1856 +-------------+--------------+--------------------------------------+ 1858 Table 3: LINK_METRIC TLV definition 1860 The exponent and mantissa use the representation defined in 1861 Section 6. Each bit of the types and directions sub-field, if set 1862 ('1') indicates that the link metric is of the indicated kind and 1863 direction. Any combination of these bits MAY be used, except that 1864 the combination with all bits unset ('0') SHOULD NOT be used. 1866 +-----+-----------------+-----------+ 1867 | Bit | Kind | Direction | 1868 +-----+-----------------+-----------+ 1869 | 0 | Link metric | Incoming | 1870 | 1 | Link metric | Outgoing | 1871 | 2 | Neighbor metric | Incoming | 1872 | 3 | Neighbor metric | Outgoing | 1873 +-----+-----------------+-----------+ 1875 Table 4: LINK_METRIC TLV types and directions 1877 The MPR TLV is used in HELLO messages, and indicates that an address 1878 with which it is associated is of a symmetric 1-hop neighbor that has 1879 been selected as an MPR. 1881 +------+--------------+---------------------------------------------+ 1882 | Type | Value Length | Value | 1883 +------+--------------+---------------------------------------------+ 1884 | MPR | 1 octet | FLOODING indicates that the corresponding | 1885 | | | address is of a neighbor selected as a | 1886 | | | flooding MPR, ROUTING indicates that the | 1887 | | | corresponding address is of a neighbor | 1888 | | | selected as a routing MPR, FLOOD_ROUTE | 1889 | | | indicates both | 1890 +------+--------------+---------------------------------------------+ 1892 Table 5: MPR TLV definition 1894 The NBR_ADDR_TYPE TLV is used in TC messages. 1896 +---------------+--------------+------------------------------------+ 1897 | Type | Value Length | Value | 1898 +---------------+--------------+------------------------------------+ 1899 | NBR_ADDR_TYPE | 1 octet | ORIGINATOR indicates that the | 1900 | | | corresponding address (which MUST | 1901 | | | have maximum prefix length) is an | 1902 | | | originator address, ROUTABLE | 1903 | | | indicates that the corresponding | 1904 | | | network address is a routable | 1905 | | | address of an interface, | 1906 | | | ROUTABLE_ORIG indicates that the | 1907 | | | corresponding address is both | 1908 +---------------+--------------+------------------------------------+ 1910 Table 6: NBR_ADDR_TYPE TLV definition 1912 If an address is both a originator address and a routable address, 1913 then it may be associated with either one Address Block TLV with Type 1914 := NBR_ADDR_TYPE and Value := ROUTABLE_ORIG, or with two Address 1915 Block TLVs with Type:= NBR_ADDR_TYPE, one with Value := ORIGINATOR 1916 and one with Value := ROUTABLE. 1918 The GATEWAY TLV is used in TC messages. At most one GATEWAY TLV may 1919 be associated with any address. 1921 +---------+--------------+-------------------------------------+ 1922 | Type | Value Length | Value | 1923 +---------+--------------+-------------------------------------+ 1924 | GATEWAY | 1 octet | Number of hops to attached network. | 1925 +---------+--------------+-------------------------------------+ 1927 Table 7: GATEWAY TLV definition 1929 All address objects included in a TC message according to this 1930 specification MUST be associated either with at least one TLV with 1931 Type := NBR_ADDR_TYPE or with a TLV with Type := GATEWAY, but not 1932 both. Any other address objects MAY be included in Address Blocks in 1933 a TC message, but are ignored by this specification. 1935 14. Message Processing and Forwarding 1937 This section describes the optimized flooding operation (MPR 1938 flooding) used when control messages, as instances of [RFC5444], are 1939 intended for MANET wide distribution. This flooding mechanism 1940 defines when a received message is, or is not, processed and/or 1941 forwarded. 1943 This flooding mechanism is used by this protocol and MAY be used by 1944 extensions to this protocol which define, and hence own, other 1945 message types, to manage processing and/or forwarding of these 1946 messages. This specification contains elements (P_type, RX_type, 1947 F_type) required only for such usage. 1949 This flooding mechanism is always used for TC messages (see 1950 Section 16). Received HELLO messages (see Section 15 are, unless 1951 invalid, always processed, and never forwarded by this flooding 1952 mechanism. They thus do not need to be recorded in the Received 1953 Message Information Base. 1955 The processing selection and forwarding mechanisms are designed to 1956 only need to parse the Message Header in order to determine whether a 1957 message is to be processed and/or forwarded, and not to have to parse 1958 the Message Body even if the message is forwarded (but not 1959 processed). An implementation MAY only parse the Message Body if 1960 necessary, or MAY always parse the Message Body and reject the 1961 message if it cannot be so parsed, or any other error is identified. 1963 An implementation MUST discard the message silently if it is unable 1964 to parse the Message Header or (if attempted) the Message Body, or if 1965 a message (other than a HELLO message) does not include a message 1966 sequence number. 1968 14.1. Actions when Receiving a Message 1970 On receiving a message of a type specified to be using this 1971 mechanism, which includes the TC messages defined in this 1972 specification, a router MUST perform the following: 1974 1. If the router recognizes from the originator address of the 1975 message that the message is one which the receiving router itself 1976 originated (i.e., the message originator address is the 1977 originator address of this router, or is an O_orig_addr in an 1978 Originator Tuple) then the message MUST be silently discarded. 1980 2. Otherwise: 1982 1. If the message is of a type which may be processed, then the 1983 message is considered for processing according to 1984 Section 14.2. 1986 2. If the message is of a type which may be forwarded, AND: 1988 + is present and > 1, AND; 1990 + is not present or < 255; 1991 then the message is considered for forwarding according to 1992 Section 14.3. 1994 14.2. Message Considered for Processing 1996 If a message (the "current message") is considered for processing, 1997 then the following tasks MUST be performed: 1999 1. If the sending address (i.e., the source address of the IP 2000 datagram containing the current message) does not match (taking 2001 into account any address prefix) a network address in an 2002 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2003 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2004 current message was received (the "receiving interface") then 2005 processing the current message is OPTIONAL. If the current 2006 message is not processed then the following steps are not carried 2007 out. 2009 2. If a Processed Tuple exists with: 2011 * P_type = the Message Type of the current message, AND; 2013 * P_orig_addr = the originator address of the current message, 2014 AND; 2016 * P_seq_number = the message sequence number of the current 2017 message; 2019 then the current message MUST NOT be processed. 2021 3. Otherwise: 2023 1. Create a Processed Tuple with: 2025 + P_type := the Message Type of the current message; 2027 + P_orig_addr := the originator address of the current 2028 message; 2030 + P_seq_number := the sequence number of the current 2031 message; 2033 + P_time := current time + P_HOLD_TIME. 2035 2. Process the current message according to its Message Type. 2036 For a TC message this is as defined in Section 16.3. 2038 14.3. Message Considered for Forwarding 2040 If a message (the "current message") is considered for forwarding, 2041 then the following tasks MUST be performed: 2043 1. If the sending address (i.e., the source address of the IP 2044 datagram containing the current message) does not match (taking 2045 into account any address prefix) a network address in an 2046 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2047 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2048 current message was received (the "receiving interface") then the 2049 current message MUST be silently discarded. 2051 2. Otherwise: 2053 1. If a Received Tuple exists in the Received Set for the 2054 receiving interface, with: 2056 + RX_type = the Message Type of the current message, AND; 2058 + RX_orig_addr = the originator address of the current 2059 message, AND; 2061 + RX_seq_number = the sequence number of the current 2062 message; 2064 then the current message MUST be silently discarded. 2066 2. Otherwise: 2068 1. Create a Received Tuple in the Received Set for the 2069 receiving interface with: 2071 - RX_type := the Message Type of the current message; 2073 - RX_orig_addr := originator address of the current 2074 message; 2076 - RX_seq_number := sequence number of the current 2077 message; 2079 - RX_time := current time + RX_HOLD_TIME. 2081 2. If a Forwarded Tuple exists with: 2083 - F_type = the Message Type of the current message, AND; 2084 - F_orig_addr = the originator address of the current 2085 message, AND; 2087 - F_seq_number = the sequence number of the current 2088 message. 2090 then the current message MUST be silently discarded. 2092 3. Otherwise if the sending address matches (taking account 2093 of any address prefix) any network address in an 2094 L_neighbor_iface_addr_list of a Link Tuple in the Link 2095 Set for the receiving OLSRv2 interface that has L_status 2096 = SYMMETRIC and whose corresponding Neighbor Tuple has 2097 N_mpr_selector = true, then: 2099 1. Create a Forwarded Tuple with: 2101 o F_type := the Message Type of the current message; 2103 o F_orig_addr := originator address of the current 2104 message; 2106 o F_seq_number := sequence number of the current 2107 message; 2109 o F_time := current time + F_HOLD_TIME. 2111 2. The Message Header of the current message is modified 2112 by: 2114 o if present, decrement in the 2115 Message Header by 1, AND; 2117 o if present, increment in the 2118 Message Header by 1. 2120 3. The message is transmitted over all OLSRv2 2121 interfaces, as described in Section 13. 2123 15. HELLO Messages 2125 The HELLO message Message Type is owned by [RFC6130], and thus HELLO 2126 messages are generated, transmitted, received and processed by 2127 [RFC6130]. This protocol, as permitted by [RFC6130], also uses HELLO 2128 messages, including adding to HELLO message generation, and # 2129 implementing additional processing based on received HELLO messages. 2130 HELLO messages are not forwarded by [RFC6130] or this specification. 2132 15.1. HELLO Message Generation 2134 An HELLO message is generated as defined in [RFC6130], extended by 2135 the following elements being added to the HELLO message by this 2136 specification before the HELLO message is sent over an OLSRv2 2137 interface: 2139 o A message originator address, recording this router's originator 2140 address. This MUST use a element, unless: 2142 * The message specifies only a single local interface address 2143 (i.e., contains only one address object that is associated with 2144 an Address Block TLV with Type = LOCAL_IF, and which has no 2145 prefix length, or a maximum prefix length) which will then be 2146 interpreted as the message originator address, OR; 2148 * The message does not include any local interface network 2149 addresses (i.e., has no address objects associated with an 2150 Address Block TLV with Type = LOCAL_IF), as permitted by the 2151 specification in [RFC6130] when the router that generated the 2152 HELLO message has only one interface address and will use that 2153 as the sending address of the IP datagram in which the HELLO 2154 message is contained. In this case that address will be 2155 interpreted as the message originator address. 2157 o A Message TLV with Type := MPR_WILLING and Value := WILLINGNESS 2158 MUST be included, unless WILLINGNESS = WILL_DEFAULT (in which case 2159 it MAY be included). 2161 o The following cases associate Address Block TLVs with one or more 2162 addresses from a Link Tuple or a Neighbor Tuple if these are 2163 included in the HELLO message. In each case the TLV MUST be 2164 associated with at least copy of one address from the relevant 2165 Tuple, the TLV MAY be associated with more such addresses 2166 (including a copy of that address object, possibly not itself 2167 associated with any other indicated TLVs, in the same or a 2168 different Address Block). These additional TLVs MUST NOT be 2169 associated with any other addresses in a HELLO message that will 2170 be processed by [RFC6130]. 2172 * For each Link Tuple for which L_in_metric != UNKNOWN_METRIC, 2173 and for which one or more addresses in its 2174 L_neighbor_iface_addr_list are included as address objects with 2175 an associated Address Block TLV with Type = LINK_STATUS and 2176 Value = HEARD or Value = SYMMETRIC, at least one of these 2177 addresses MUST be associated with an Address Block TLV with 2178 Type := LINK_METRIC indicating an incoming link metric with 2179 value L_in_metric, unless this equals DEFAULT_METRIC. 2181 * For each Link Tuple for which L_out_metric != UNKNOWN_METRIC, 2182 and for which one or more addresses in its 2183 L_neighbor_iface_addr_list are included as address objects with 2184 an associated Address Block TLV with Type = LINK_STATUS and 2185 Value = SYMMETRIC, at least one of these addresses MUST be 2186 associated with an Address Block TLV with Type := LINK_METRIC 2187 indicating an outgoing link metric with value L_out_metric, 2188 unless this equals DEFAULT_METRIC. 2190 * For each Neighbor Tuple for which N_symmetric = true, and for 2191 which one or more addresses in its N_neighbor_addr_list are 2192 included as address objects with an associated Address Block 2193 TLV with Type = LINK_STATUS and Value = SYMMETRIC, at least one 2194 of these addresses MUST be associated with an Address Block TLV 2195 with Type := LINK_METRIC indicating an incoming neighbor metric 2196 with value N_in_metric, unless this equals DEFAULT_METRIC. 2198 * For each Neighbor Tuple for which N_symmetric = true, and for 2199 which one or more addresses in its N_neighbor_addr_list are 2200 included as address objects with an associated Address Block 2201 TLV with Type = LINK_STATUS and Value = SYMMETRIC, at least one 2202 of these addresses MUST be associated with an Address Block TLV 2203 with Type := LINK_METRIC indicating an outcoming neighbor 2204 metric with value N_out_metric, unless this equals 2205 DEFAULT_METRIC. 2207 * For each Neighbor Tuple with N_flooding_mpr = true, and for 2208 which one or more network addresses in its N_neighbor_addr_list 2209 are included as address objects in the HELLO message with an 2210 associated Address Block TLV with Type = LINK_STATUS and Value 2211 = SYMMETRIC, at least one of these addresses MUST be associated 2212 with an Address Block TLV with Type := MPR and Value := 0 or 2213 Value := 1. 2215 * For each Neighbor Tuple with N_routing_mpr = true, and for 2216 which one or more network addresses in its N_neighbor_addr_list 2217 are included as address objects in the HELLO message with an 2218 associated Address Block TLV with Type = LINK_STATUS and Value 2219 = SYMMETRIC, at least one of these addresses MUST be associated 2220 with an Address Block TLV with Type := MPR and Value := 0 or 2221 Value := 2. 2223 15.2. HELLO Message Transmission 2225 HELLO messages are scheduled and transmitted by [RFC6130]. This 2226 protocol MAY require that an additional HELLO message is sent when 2227 the router's set of MPRs changes, in addition to the cases specified 2228 in [RFC6130], and subject to the same constraints. 2230 15.3. HELLO Message Processing 2232 When received on an OLSRv2 interface, HELLO messages are made 2233 available to this protocol in two ways, both as permitted by 2234 [RFC6130]: 2236 o Such received HELLO messages MUST be made available to this 2237 protocol on reception, which allows them to be discarded before 2238 being processed by [RFC6130], for example if the information added 2239 to the HELLO message by this protocol is inconsistent. 2241 o Such received HELLO messages MUST be made available to OLSRv2 2242 after [RFC6130] has completed its processing thereof, unless 2243 discarded as malformed by [RFC6130], for processing by this 2244 protocol. 2246 15.3.1. HELLO Message Discarding 2248 In addition to the reasons specified in [RFC6130] for discarding a 2249 HELLO message on reception, a HELLO message MUST be discarded before 2250 processing by [RFC6130] or this specification if it: 2252 o Has more than one Message TLV with Type = MPR_WILLING. 2254 o Has a message originator address, or a network address 2255 corresponding to an address object associated with an Address 2256 Block TLV with Type = LOCAL_IF, that is partially owned by this 2257 router. (Some of these cases are already excluded by [RFC6130].) 2259 o Includes any address object associated with an Address Block TLV 2260 with Type = LINK_STATUS or Type = OTHER_NEIGHB that overlaps the 2261 message's originator address. 2263 o Contains any address that will be processed by [RFC6130] that is 2264 associated, using the same or different address objects, with two 2265 different values of link metric with the same kind and direction 2266 using a TLV with Type = LINK_METRIC and Type Extension = 2267 LINK_METRIC_TYPE. This also applies to different addresses that 2268 are both of the OLSRv2 interface on which the HELLO message was 2269 received. 2271 o Contains any address object associated with an Address Block TLV 2272 with Type = MPR that is not also associated with an Address Block 2273 TLV with Type = LINK_STATUS and Value = SYMMETRIC (including using 2274 a different copy of that address object, in the same or a 2275 different Address Block). 2277 15.3.2. HELLO Message Usage 2279 HELLO messages are first processed as specified in [RFC6130]. That 2280 processing includes identifying (or creating) a Neighbor Tuple 2281 corresponding to the originator of the HELLO message (the "current 2282 Neighbor Tuple"). After this, the following processing MUST also be 2283 performed: 2285 1. If the HELLO message has a well-defined message originator 2286 address, i.e., has an element or has zero or one 2287 network addresses associated with a TLV with Type = LOCAL_IF: 2289 1. Remove any other Neighbor Tuple with N_orig_addr = message 2290 originator address, taking any consequent action (including 2291 removing one or more Link Tuples) as specified in [RFC6130]. 2293 2. The current Link Tuple is then updated according to: 2295 1. Update L_in_metric and L_out_metric as described in 2296 Section 15.3.2.1; 2298 2. Update L_mpr_selector as described in Section 15.3.2.3. 2300 3. The current Neighbor Tuple is then updated according to: 2302 1. N_orig_addr := message originator address; 2304 2. Update N_in_metric and N_out_metric as described in 2305 Section 15.3.2.1; 2307 3. Update N_will_flooding and N_will_routing as described in 2308 Section 15.3.2.2; 2310 4. Update N_mpr_selector as described in Section 15.3.2.3. 2312 2. If there are any changes to the router's Information Bases, then 2313 perform the processing defined in Section 17. 2315 15.3.2.1. Updating Metrics 2317 For each address in a received HELLO message with an associated TLV 2318 with Type = LINK_STATUS and Value = HEARD or Value = SYMMETRIC, an 2319 incoming (to the message originator) link metric value is defined 2320 either using an associated TLV with Type = LINK_METRIC and Type 2321 Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2322 (link) and direction (incoming) of metric, or as the value 2323 DEFAULT_METRIC. 2325 For each address in a received HELLO message with an associated TLV 2326 with Type = LINK_STATUS and Value = SYMMETRIC, an outgoing (to the 2327 message originator) link metric value is defined either using an 2328 associated TLV with Type = LINK_METRIC and Type Extension = 2329 LINK_METRIC_TYPE that indicates the appropriate kind (link) and 2330 direction (outgoing) of metric, or as the value DEFAULT_METRIC. 2332 For each address in a received HELLO message with an associated TLV 2333 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2334 an incoming (to the message originator) neighbor metric value is 2335 defined either using an associated TLV with Type = LINK_METRIC and 2336 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2337 (neighbor) and direction (incoming) of metric, or as the value 2338 DEFAULT_METRIC. 2340 For each address in a received HELLO message with an associated TLV 2341 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2342 an outgoing (to the message originator) neighbor metric value is 2343 defined either using an associated TLV with Type = LINK_METRIC and 2344 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2345 (neighbor) and direction (outgoing) of metric, or as the value 2346 DEFAULT_METRIC. 2348 The link metric elements L_in_metric and L_out_metric in a Link Tuple 2349 are updated according to the following: 2351 o For any Link Tuple, L_in_metric MAY be set to any representable 2352 value, by a process outside this specification, at any time. 2353 L_in_metric MUST be so set whenever L_status becomes equal to 2354 HEARD or SYMMETRIC (if no other value is available then the value 2355 MAXIMUM_METRIC SHOULD be used). This MAY use information based on 2356 the receipt of a packet including a HELLO message that causes the 2357 creation or updating of that Link Tuple. 2359 o When, as specified in [RFC6130], a Link Tuple is updated (possibly 2360 immediately after being created) due to the receipt of a HELLO 2361 message, if L_status = SYMMETRIC, then L_out_metric is set equal 2362 to the incoming link metric for any included address of the 2363 interface on which the HELLO message was received, ignoring any 2364 values equal to DEFAULT_METRIC unless there are only such values. 2365 (Note that the rules for discarding HELLO messages in 2366 Section 15.3.1 make this value unambiguous.) 2368 The neighbor metric elements N_in_metric and N_out_metric in a 2369 Neighbor Tuple are updated according to Section 17.3. 2371 The metric elements N2_in_metric and N2_out_metric in any 2-Hop Tuple 2372 updated as defined in [RFC6130] are updated to equal the incoming 2373 neighbor metric and outgoing neighbor metric, respectively, 2374 associated with the corresponsing N2_2hop_addr. 2376 15.3.2.2. Updating Willingness 2378 N_will_flooding and N_will_routing in the current Neighbor Tuple are 2379 updated as follows: 2381 1. If the HELLO message contains a Message TLV with Type = 2382 MPR_WILLING then N_will_flooding := bits 0-3 of the value of that 2383 TLV, and N_will_routing := bits 4-7 of the value of that TLV 2384 (each in the range 0 to 15). 2386 2. Otherwise, N_will_flooding := WILL_DEFAULT, and N_will_routing := 2387 WILL_DEFAULT. 2389 15.3.2.3. Updating MPR Selector Status 2391 L_mpr_selector is updated as follows: 2393 1. If a router finds an address object representing any of its local 2394 interface network addresses (i.e., those contained in the 2395 I_local_iface_addr_list of an OLSRv2 interface) with an 2396 associated Address Block TLV with Type = MPR and Value = 0 or 2397 Value = 1 in the HELLO message (indicating that the originating 2398 router has selected the receiving router as a flooding MPR) then, 2399 for the current Link Tuple: 2401 * L_mpr_selector := true 2403 2. Otherwise (i.e., if no such address object and Address Block TLV 2404 was found) if a router finds an address object representing any 2405 of its local interface network addresses (i.e., those contained 2406 in the I_local_iface_addr_list of an OLSRv2 interface) with an 2407 associated Address Block TLV with Type = LINK_STATUS and Value = 2408 SYMMETRIC in the HELLO message, then for the current Link Tuple: 2410 * L_mpr_selector := false 2412 N_mpr_selector is updated as follows: 2414 1. If a router finds an address object representing any of its local 2415 interface network addresses (i.e., those contained in the 2416 I_local_iface_addr_list of an OLSRv2 interface) with an 2417 associated Address Block TLV with Type = MPR and Value = 0 or 2418 Value = 2 in the HELLO message (indicating that the originating 2419 router has selected the receiving router as a routing MPR) then, 2420 for the current Neighbor Tuple: 2422 * N_mpr_selector := true 2424 * N_advertised := true 2426 2. Otherwise (i.e., if no such address object and Address Block TLV 2427 was found) if a router finds an address object representing any 2428 of its local interface network addresses (i.e., those contained 2429 in the I_local_iface_addr_list of an OLSRv2 interface) with an 2430 associated Address Block TLV with Type = LINK_STATUS and Value = 2431 SYMMETRIC in the HELLO message, then for the current Neighbor 2432 Tuple: 2434 * N_mpr_selector := false 2436 * The router MAY also set N_advertised := false 2438 16. TC Messages 2440 This protocol defines, and hence owns, the TC message type (see 2441 Section 24). Thus, as specified in [RFC5444], this protocol 2442 generates and transmits all TC messages, receives all TC messages and 2443 is responsible for determining whether and how each TC message is to 2444 be processed (updating the Topology Information Base) and/or 2445 forwarded, according to this specification. 2447 16.1. TC Message Generation 2449 A TC message is a message as defined in [RFC5444]. A generated TC 2450 message MUST contain the following elements as defined in [RFC5444]: 2452 o A message originator address, recording this router's originator 2453 address. This MUST use a element. 2455 o element containing the message sequence number. 2457 o A element, containing TC_HOP_LIMIT. A router MAY 2458 use the same or different values of TC_HOP_LIMIT in its TC 2459 messages, see Section 5.4.7. 2461 o A element, containing zero, if the message 2462 contains a TLV with either Type = VALIDITY_TIME or Type = 2463 INTERVAL_TIME (as specified in [RFC5497]) indicating more than one 2464 time value according to distance. A TC message MAY contain such a 2465 element even if it does not need to. 2467 o A single Message TLV with Type := CONT_SEQ_NUM and Value := ANSN 2468 from the Neighbor Information Base. If the TC message is complete 2469 then this Message TLV MUST have Type Extension := COMPLETE, 2470 otherwise it MUST have Type Extension := INCOMPLETE. (Exception: 2471 a TC message MAY omit such a Message TLV if the TC message does 2472 not include any address objects with an associated Address Block 2473 TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY.) 2475 o A single Message TLV with Type := VALIDITY_TIME, as specified in 2476 [RFC5497]. If all TC messages are sent with the same hop limit 2477 then this TLV MUST have a value encoding the period T_HOLD_TIME. 2478 If TC messages are sent with different hop limits (more than one 2479 value of TC_HOP_LIMIT) then this TLV MUST specify times that vary 2480 with the number of hops distance appropriate to the chosen pattern 2481 of TC message hop limits, as specified in [RFC5497]; these times 2482 SHOULD be appropriate multiples of T_HOLD_TIME. The options 2483 included in [RFC5497] for representing zero and infinite times 2484 MUST NOT be used. 2486 o If the TC message is complete, all network addresses which are the 2487 N_orig_addr of a Neighbor Tuple with N_advertised = true, MUST be 2488 represented by address objects in one or more Address Blocks. If 2489 the TC message is incomplete then any such address objects MAY be 2490 included. At least one copy of each such address object that is 2491 included MUST be associated with an Address Block TLV with Type := 2492 NBR_ADDR_TYPE, and Value := ORIGINATOR, or with Value := 2493 ROUTABLE_ORIG if that address object is also to be associated with 2494 Value = ROUTABLE. 2496 o If the TC message is complete, all routable addresses which are in 2497 the N_neighbor_addr_list of a Neighbor Tuple with N_advertised = 2498 true MUST be represented by address objects in one or more Address 2499 Blocks. If the TC message is incomplete then any such address 2500 objects MAY be included. At least one copy of each such address 2501 object MUST be associated with an Address Block TLV with Type = 2502 NBR_ADDR_TYPE, and Value = ROUTABLE, or with Value = ROUTABLE_ORIG 2503 if also to be associated with Value = ORIGINATOR. At least one 2504 copy of each such address object MUST be associated with an 2505 Address Block TLV with Type = LINK_METRIC and Type Extension = 2506 LINK_METRIC_TYPE indicating an outgoing neighbor metric with value 2507 equal to the corresponding N_out_metric, unless that value is 2508 DEFAULT_METRIC. 2510 o If the TC message is complete, all network addresses which are the 2511 AL_net_addr of a Local Attached Network Tuple MUST be represented 2512 by address objects in one or more Address Blocks. If the TC 2513 message is incomplete then any such address objects MAY be 2514 included. At least one copy of each such address object MUST be 2515 associated with an Address Block TLV with Type := GATEWAY, and 2516 Value := AN_dist. At least one copy of each such address object 2517 MUST be associated with an Address Block TLV with Type = 2518 LINK_METRIC and Type Extension = LINK_METRIC_TYPE indicating an 2519 outgoing neighbor metric equal to the corresponding AL_metric, 2520 unless that value is DEFAULT_METRIC. 2522 A TC message MAY contain: 2524 o A single Message TLV with Type := INTERVAL_TIME, as specified in 2525 [RFC5497]. If all TC messages are sent with the same hop limit 2526 then this TLV MUST have a value encoding the period TC_INTERVAL. 2527 If TC messages are sent with different hop limits, then this TLV 2528 MUST specify times that vary with the number of hops distance 2529 appropriate to the chosen pattern of TC message hop limits, as 2530 specified in [RFC5497]; these times SHOULD be appropriate 2531 multiples of TC_INTERVAL. The options included in [RFC5497] for 2532 representing zero and infinite times MUST NOT be used. 2534 16.2. TC Message Transmission 2536 A router with one or more OLSRv2 interfaces, and with any Neighbor 2537 Tuples with N_advertised = true, or with a non-empty Local Attached 2538 Network Set MUST generate TC messages. A router which does not have 2539 such information to advertise SHOULD also generate "empty" TC 2540 messages for a period A_HOLD_TIME after it last generated a non-empty 2541 TC message. 2543 Complete TC messages are generated and transmitted periodically on 2544 all OLSRv2 interfaces, with a default interval between two 2545 consecutive TC transmissions by the same router of TC_INTERVAL. 2547 TC messages MAY be generated in response to a change in the 2548 information which they are to advertise, indicated by a change in the 2549 ANSN in the Neighbor Information Base. In this case a router MAY 2550 send a complete TC message, and if so MAY re-start its TC message 2551 schedule. Alternatively a router MAY send an incomplete TC message 2552 with at least the newly advertised network addresses (i.e., not 2553 previously, but now, an N_orig_addr or in an N_neighbor_addr_list in 2554 a Neighbor Tuple with N_advertised = true, or an AL_net_addr) in its 2555 Address Blocks, with associated Address Block TLV(s). Note that a 2556 router cannot report removal of advertised content using an 2557 incomplete TC message. 2559 When sending a TC message in response to a change of advertised 2560 network addresses, a router MUST respect a minimum interval of 2561 TC_MIN_INTERVAL between generated TC messages. Sending an incomplete 2562 TC message MUST NOT cause the interval between complete TC messages 2563 to be increased, and thus a router MUST NOT send an incomplete TC 2564 message if within TC_MIN_INTERVAL of the next scheduled complete TC 2565 message. 2567 The generation of TC messages, whether scheduled or triggered by a 2568 change of contents, MAY be jittered as described in [RFC5148]. The 2569 values of MAXJITTER used SHOULD be: 2571 o TP_MAXJITTER for periodic TC message generation; 2573 o TT_MAXJITTER for responsive TC message generation. 2575 16.3. TC Message Processing 2577 On receiving a TC message, the receiving router MUST then follow the 2578 processing and forwarding procedure, defined in Section 14. 2580 If the message is considered for processing (Section 14.2), then a 2581 router MUST first check if the message is invalid for processing by 2582 this router, as defined in Section 16.3.1. A router MAY make a 2583 similar check before considering a message for forwarding, it MUST 2584 make those aspects of the check that apply to elements in the Message 2585 Header. 2587 If the TC message is not invalid, then the TC message type specific 2588 processing, described in Section 16.3.2 MUST be applied. This will 2589 update its appropriate Interface Information Base and its Router 2590 Information Base. Following this, if there are any changes in these 2591 Information Bases, then the processing in Section 17 MUST be 2592 performed. 2594 16.3.1. Invalid Message 2596 A received TC message is invalid for processing by this router if the 2597 message: 2599 o Has an address length specified in the Message Header that is not 2600 equal to the length of the addresses used by this router. 2602 o Does not include a message originator address and a message 2603 sequence number. 2605 o Does not include a hop count, and contains a multi-value TLV with 2606 Type = VALIDITY_TIME or Type = INTERVAL_TIME, as defined in 2607 [RFC5497]. 2609 o Does not have exactly one Message TLV with Type = VALIDITY_TIME. 2611 o Has more than one Message TLV with Type = INTERVAL_TIME. 2613 o Does not have a Message TLV with Type = CONT_SEQ_NUM and Type 2614 Extension = COMPLETE or Type Extension = INCOMPLETE, and contains 2615 at least one address object associated with an Address Block TLV 2616 with Type = NBR_ADDR_TYPE or Type = GATEWAY. 2618 o Has more than one Message TLV with Type = CONT_SEQ_NUM and Type 2619 Extension = COMPLETE or Type Extension = INCOMPLETE. 2621 o Has a message originator address that is partially owned by this 2622 router. 2624 o Includes any address object with a prefix length which is not 2625 maximal (equal to the address length, in bits), associated with an 2626 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ORIGINATOR 2627 or Value = ROUTABLE_ORIG. 2629 o Includes any address object that represents a non-routable 2630 address, associated with an Address Block TLV with Type = 2631 NBR_ADDR_TYPE and Value = ROUTABLE or Value = ROUTABLE_ORIG. 2633 o Includes any address object associated with an Address Block TLV 2634 with Type = NBR_ADDR_TYPE or Type = GATEWAY that also represents 2635 the message's originator address. 2637 o Includes any address object (including different copies of an 2638 address object, in the same or different Address Blocks) that is 2639 associated with an Address Block TLV with Type = NBR_ADDR_TYPE or 2640 Type = GATEWAY, that is also associated with more than one 2641 outgoing neighbor metric using a TLV with Type = LINK_METRIC and 2642 Type Extension = LINK_METRIC_TYPE. 2644 o Associates any address object (including different copies of an 2645 address object, in the same or different Address Blocks) with more 2646 than one single hop count value using one or more Address Block 2647 TLV(s) with Type = GATEWAY. 2649 o Associates any address object (including different copies of an 2650 address object, in the same or different Address Blocks) with 2651 Address Block TLVs with Type = NBR_ADDR_TYPE and Type = GATEWAY. 2653 A router MAY recognize additional reasons for identifying that a 2654 message is invalid. An invalid message MUST be silently discarded, 2655 without updating the router's Information Bases. 2657 16.3.2. TC Message Processing Definitions 2659 When, according to Section 14.2, a TC message is to be "processed 2660 according to its type", this means that: 2662 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2663 and Type Extension = COMPLETE, then processing according to 2664 Section 16.3.3 and then according to Section 16.3.4 is carried 2665 out. 2667 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2668 and Type Extension = INCOMPLETE, then only processing according to 2669 Section 16.3.3 is carried out. 2671 For the purposes of this section: 2673 o "validity time" is calculated from a VALIDITY_TIME Message TLV in 2674 the TC message according to the specification in [RFC5497]. All 2675 information in the TC message has the same validity time. 2677 o "received ANSN" is defined as being the value of a Message TLV 2678 with Type = CONT_SEQ_NUM. 2680 o "associated metric value" is defined for any address in the TC 2681 message as being either the outgoing neighbor metric value 2682 indicated by a TLV with Type = LINK_METRIC and Type Extemsion = 2683 LINK_METRIC_TYPE that is associated with any address object in the 2684 TC message that is equal to that address, or as DEFAULT_METRIC 2685 otherwise. (Note that the rules in Section 16.3.1 make this 2686 definition unambiguous.) 2688 o Comparisons of sequence numbers are carried out as specified in 2689 Section 21. 2691 16.3.3. Initial TC Message Processing 2693 The TC message is processed as follows: 2695 1. The Advertising Remote Router Set is updated according to 2696 Section 16.3.3.1. If the TC message is indicated as discarded in 2697 that processing then the following steps are not carried out. 2699 2. The Router Topology Set is updated according to Section 16.3.3.2. 2701 3. The Routable Address Topology Set is updated according to 2702 Section 16.3.3.3. 2704 4. The Attached Network Set is updated according to 2705 Section 16.3.3.4. 2707 16.3.3.1. Populating the Advertising Remote Router Set 2709 The router MUST update its Advertising Remote Router Set as follows: 2711 1. If there is an Advertising Remote Router Tuple with: 2713 * AR_orig_addr = message originator address, AND; 2715 * AR_seq_number > received ANSN, 2717 then the TC message MUST be discarded. 2719 2. Otherwise: 2721 1. If there is no Advertising Remote Router Tuple such that: 2723 + AR_orig_addr = message originator address; 2725 then create an Advertising Remote Router Tuple with: 2727 + AR_orig_addr := message originator address. 2729 2. This Advertising Remote Router Tuple (existing or new) is 2730 then modified as follows: 2732 + AR_seq_number := received ANSN; 2734 + AR_time := current time + validity time. 2736 16.3.3.2. Populating the Router Topology Set 2738 The router MUST update its Router Topology Set as follows: 2740 1. For each address (henceforth advertised address) corresponding to 2741 one or more address objects with an associated Address Block TLV 2742 with Type = NBR_ADDR_TYPE and Value = ORIGINATOR or Value = 2743 ROUTABLE_ORIG, and that is not partially owned by this router, 2744 perform the following processing: 2746 1. If there is no Router Topology Tuple such that: 2748 + TR_from_orig_addr = message originator address, AND; 2750 + TR_to_orig_addr = advertised address, 2752 then create a new Router Topology Tuple with: 2754 + TR_from_orig_addr := message originator address; 2756 + TR_to_orig_addr := advertised address. 2758 2. This Router Topology Tuple (existing or new) is then modified 2759 as follows: 2761 + TR_seq_number := received ANSN; 2763 + TR_metric := associated link metric; 2765 + TR_time := current time + validity time. 2767 16.3.3.3. Populating the Routable Address Topology Set 2769 The router MUST update its Routable Address Topology Set as follows: 2771 1. For each network address (henceforth advertised address) 2772 corresponding to one or more address objects with an associated 2773 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ROUTABLE 2774 or Value = ROUTABLE_ORIG, and that is not partially owned by this 2775 router, perform the following processing: 2777 1. If there is no Routable Address Topology Tuple such that: 2779 + TA_from_orig_addr = message originator address, AND; 2781 + TA_dest_addr = advertised address, 2783 then create a new Routable Address Topology Tuple with: 2785 + TA_from_orig_addr := message originator address; 2787 + TA_dest_addr := advertised address. 2789 2. This Routable Address Topology Tuple (existing or new) is 2790 then modified as follows: 2792 + TA_seq_number := received ANSN; 2794 + TA_metric := associated link metric; 2796 + TA_time := current time + validity time. 2798 16.3.3.4. Populating the Attached Network Set 2800 The router MUST update its Attached Network Set as follows: 2802 1. For each network address (henceforth attached address) 2803 corresponding to one or more address objects with an associated 2804 Address Block TLV with Type = GATEWAY, and that is not fully 2805 owned by this router, perform the following processing: 2807 1. If there is no Attached Network Tuple such that: 2809 + AN_net_addr = attached address, AND; 2811 + AN_orig_addr = message originator address, 2813 then create a new Attached Network Tuple with: 2815 + AN_net_addr := attached address; 2817 + AN_orig_addr := message originator address. 2819 2. This Attached Network Tuple (existing or new) is then 2820 modified as follows: 2822 + AN_seq_number := received ANSN; 2824 + AN_dist := the Value of the associated GATEWAY TLV; 2826 + AN_metric := associated link metric; 2828 + AN_time := current time + validity time. 2830 16.3.4. Completing TC Message Processing 2832 The TC message is processed as follows: 2834 1. The Router Topology Set is updated according to Section 16.3.4.1. 2836 2. The Routable Address Topology Set is updated according to 2837 Section 16.3.4.2. 2839 3. The Attached Network Set is updated according to 2840 Section 16.3.4.3. 2842 16.3.4.1. Purging the Router Topology Set 2844 The Router Topology Set MUST be updated as follows: 2846 1. Any Router Topology Tuples with: 2848 * TR_from_orig_addr = message originator address, AND; 2850 * TR_seq_number < received ANSN, 2852 MUST be removed. 2854 16.3.4.2. Purging the Routable Address Topology Set 2856 The Routable Address Topology Set MUST be updated as follows: 2858 1. Any Routable Address Topology Tuples with: 2860 * TA_from_orig_addr = message originator address, AND; 2862 * TA_seq_number < received ANSN, 2864 MUST be removed. 2866 16.3.4.3. Purging the Attached Network Set 2868 The Attached Network Set MUST be updated as follows: 2870 1. Any Attached Network Tuples with: 2872 * AN_orig_addr = message originator address, AND; 2874 * AN_seq_number < received ANSN, 2876 MUST be removed. 2878 17. Information Base Changes 2880 The changes described in the following sections MUST be carried out 2881 when any Information Base changes as indicated. 2883 17.1. Originator Address Changes 2885 If the router changes originator address, then: 2887 1. If there is no Originator Tuple with: 2889 * O_orig_addr = old originator address 2891 then create an Originator Tuple with: 2893 * O_orig_addr := old originator address 2895 The Originator Tuple (existing or new) with: 2897 * O_orig_addr = new originator address 2899 is then modified as follows: 2901 * O_time := current time + O_HOLD_TIME 2903 17.2. Link State Changes 2905 The consistency of a Link Tuple MUST be maintained accoprding to the 2906 following rules, in addition to those in [RFC6130]: 2908 o If L_status = HEARD or L_status = SYMMETRIC, then L_in_metric MUST 2909 be set (by a process outside this specification). 2911 o If L_status != SYMMETRIC, then set L_mpr_selector := false. 2913 o If L_out_metric = UNKNOWN_METRIC, then L_status MUST NOT equal 2914 SYMMETRIC; set L_SYM_time := expired if this would otherwise be 2915 the case. 2917 17.3. Neighbor State Changes 2919 The consistency of a Neighbor Tuple MUST be maintained according to 2920 the following rules, in addition to those in [RFC6130]: 2922 1. If N_symmetric = true, then N_in_metric MUST equal the minimum 2923 value of all L_in_metric of corresponding Link Tuples with 2924 L_status = SYMMETRIC. 2926 2. If N_symmetric = true, then N_out_metric MUST equal the minimum 2927 value of all L_out_metric of corresponding Link Tuples with 2928 L_status = SYMMETRIC. 2930 3. If N_symmetric = false, then N_flooding_mpr, N_routing_mpr, 2931 N_mpr_selector and N_advertised MUST all be equal to false. 2933 4. If N_mpr_selector = true, then N_advertised MUST be equal to 2934 true. 2936 5. If N_symmetric = true and N_mpr_selector = false, then a router 2937 MAY select N_advertised = true or N_advertised = false. The more 2938 neighbors that are advertised, the larger TC messages become, but 2939 the more redundancy is available for routing. A router SHOULD 2940 consider the nature of its network in making such a decision, and 2941 SHOULD avoid unnecessary changes in advertising status, which may 2942 result both in additional TC messages having to be sent by its 2943 neighbors, and in unnecessary changes to routing, which will have 2944 similar effects to other forms of topology changes in the MANET. 2946 17.4. Advertised Neighbor Changes 2948 The router MUST increment the ANSN in the Neighbor Information Base 2949 whenever: 2951 1. Any Neighbor Tuple changes its N_advertised value, or any 2952 Neighbor Tuple with N_advertised = true is removed. 2954 2. Any Neighbor Tuple with N_advertised = true changes its 2955 N_orig_addr, or has any routable address is added to or removed 2956 from N_neighbor_addr_list. 2958 3. Any Neighbor Tuple with N_advertised = true has N_out_metric 2959 changed. 2961 4. There is any change to the Local Attached Network Set. 2963 17.5. Advertising Remote Router Tuple Expires 2965 The Router Topology Set, the Routable Address Topology Set and the 2966 Attached Network Set MUST be changed when an Advertising Remote 2967 Router Tuple expires (AR_time is reached). The following changes are 2968 required before the Advertising Remote Router Tuple is removed: 2970 1. All Router Topology Tuples with: 2972 * TR_from_orig_addr = AR_orig_addr of the Advertising Remote 2973 Router Tuple 2975 are removed. 2977 2. All Routable Address Topology Tuples with: 2979 * TA_from_orig_addr = AR_orig_addr of the Advertising Remote 2980 Router Tuple 2982 are removed. 2984 3. All Attached Network Tuples with: 2986 * AN_orig_addr = AR_orig_addr of the Advertising Remote Router 2987 Tuple 2989 are removed. 2991 17.6. Neighborhood Changes and MPR Updates 2993 The sets of symmetric 1-hop neighbors selected as flooding MPRs and 2994 routing MPRs MUST satisfy the conditions defined in Section 18. To 2995 ensure this: 2997 1. The set of flooding MPRs of a router MUST be recalculated if: 2999 * a Link Tuple is added with L_status = SYMMETRIC, OR; 3001 * a Link Tuple with L_status = SYMMETRIC is removed, OR; 3003 * a Link Tuple with L_status = SYMMETRIC changes to having 3004 L_status = HEARD or L_status = LOST, OR; 3006 * a Link Tuple with L_status = HEARD or L_status = LOST changes 3007 to having L_status = SYMMETRIC, OR; 3009 * a 2-Hop Tuple is added or removed, OR; 3011 * the N_will_flooding of a Neighbor Tuple with N_symmetric = 3012 true changes from WILL_NEVER to any other value, OR; 3014 * the N_will_flooding of a Neighbor Tuple with N_flooding_mpr = 3015 true changes to WILL_NEVER from any other value, OR; 3017 * the N_will_flooding of a Neighbor Tuple with N_symmetric = 3018 true and N_flooding_mpr = false changes to WILL_ALWAYS from 3019 any other value. 3021 2. Otherwise, the set of flooding MPRs of a router MAY be 3022 recalculated if the N_will_flooding of a Neighbor Tuple with 3023 N_symmetric = true changes in any other way; it SHOULD be 3024 recalculated if N_flooding_mpr = false and this is an increase in 3025 N_will_flooding or if N_flooding_mpr = true and this is a 3026 decrease in N_will_flooding. 3028 3. The set of routing MPRs of a router MUST be recalculated if: 3030 * a Link Tuple is added with L_status = SYMMETRIC, OR; 3031 * a Link Tuple with L_status = SYMMETRIC is removed, OR; 3033 * a Link Tuple with L_status = SYMMETRIC changes to having 3034 L_status = HEARD or L_status = LOST, OR; 3036 * a Link Tuple with L_status = HEARD or L_status = LOST changes 3037 to having L_status = SYMMETRIC, OR; 3039 * a 2-Hop Tuple is added or removed, OR; 3041 * the N_will_routing of a Neighbor Tuple with N_symmetric = true 3042 changes from WILL_NEVER to any other value, OR; 3044 * the N_will_routing of a Neighbor Tuple with N_routing mpr = 3045 true changes to WILL_NEVER from any other value, OR; 3047 * the N_will_routing of a Neighbor Tuple with N_symmetric = true 3048 and N_routing_mpr = false changes to WILL_ALWAYS from any 3049 other value. 3051 4. Otherwise, the set of routing MPRs of a router MAY be 3052 recalculated if the N_will_routing of a Neighbor Tuple with 3053 N_symmetric = true changes in any other way; it SHOULD be 3054 recalculated if N_routing_mpr = false and this is an increase in 3055 N_will_routing or if N_routing_mpr = true and this is a decrease 3056 in N_will_routing. 3058 If either set of MPRs of a router is recalculated, this MUST be as 3059 described in Section 18. Before that calculation, N_flooding_mpr or 3060 N_routing_mpr (as appropriate) of all Neighbor Tuples is set false 3061 (although its previous value MAY be used by an algorithm that 3062 minimizes changes to the set of MPRs). After that calculation the 3063 N_flooding_mpr or N_routing_mpr (as appropriate) of all Neighbor 3064 Tuples representing symmetric 1-hop neighbors that are chosen as 3065 MPRs, are set true. 3067 17.7. Routing Set Updates 3069 The Routing Set MUST be updated, as described in Section 19 when 3070 changes in the Local Information Base, the Neighborhood Information 3071 Base or the Topology Information Base indicate a change (including of 3072 any potentially used link metric values, all outgoing) of the known 3073 symmetric links and/or attached networks in the MANET, hence changing 3074 the Topology Graph. It is sufficient to consider only changes which 3075 affect at least one of: 3077 o The Local Interface Set, if the change removes any network address 3078 in an I_local_iface_addr_list. In this case, unless the OLSRv2 3079 interface is removed, it may not be necessary to do more than 3080 replace such network addresses, if used, by an alternative network 3081 address from the same I_local_iface_addr_list. 3083 o The Local Attached Set, if the change removes any AL_net_addr 3084 which is also an AN_net_addr. In this case it may not be 3085 necessary to do more than add Routing Tuples with R_dest_addr 3086 equal to that AN_net_addr. 3088 o The Link Set of any OLSRv2 interface, considering only Link Tuples 3089 which have, or just had, L_status = SYMMETRIC (including removal 3090 of such Link Tuples). 3092 o The Neighbor Set of the router, considering only Neighbor Tuples 3093 that have, or just had, N_symmetric = true, and do not have 3094 N_orig_addr = unknown. 3096 o The 2-Hop Set of any OLSRv2 interface, if used in the creation of 3097 the Routing Set. 3099 o The Router Topology Set of the router. 3101 o The Routable Address Topology Set of the router. 3103 o The Attached Network Set of the router. 3105 18. Selecting MPRs 3107 Note: This section has not yet been updated to use link metrics and 3108 separate sets of flooding and routing MPRs. 3110 Each router MUST select, from among its willing symmetric 1-hop 3111 neighbors, a subset of these routers as MPRs. Only MPRs forward 3112 control messages flooded through the MANET, thus effecting a flooding 3113 reduction, an optimization of the classical flooding mechanism, known 3114 as MPR flooding. MPRs MAY also be used to effect a topology 3115 reduction in the MANET. Consequently, while it is not essential that 3116 the set of MPRs is minimal, keeping the number of MPRs small ensures 3117 that the overhead is kept at a minimum. 3119 A router MUST select MPRs for each of its OLSRv2 interfaces, but then 3120 forms the union of those sets as its single set of MPRs. This union 3121 MUST include all symmetric 1-hop neighbors with willingness 3122 WILL_ALWAYS. Only this overall set of MPRs is relevant, the recorded 3123 and used MPR relationship is one of routers, not interfaces. Routers 3124 MAY select their MPRs by any process which satisfies the conditions 3125 which follow. Routers can freely interoperate whether they use the 3126 same or different MPR selection algorithms. 3128 For each OLSRv2 interface a router MUST select a set of MPRs. This 3129 set MUST have the properties that: 3131 o All of the selected MPRs are willing symmetric 1-hop neighbors, 3132 AND; 3134 o If the selecting router sends a message on that OLSRv2 interface, 3135 and that message is successfully forwarded by all of the selected 3136 MPRs for that interface, then all symmetric strict 2-hop neighbors 3137 of the selecting router through that OLSRv2 interface will receive 3138 that message over a symmetric link. 3140 When a router selects its set of MPRs it MAY consider any other 3141 characteristics of its neighbors that it is aware of. In particular 3142 it SHOULD consider the willingness of the neighbor, as recorded by 3143 the corresponding N_willingness value, preferring neighbors with 3144 higher values of N_willingness, but MAY consider other 3145 characteristics to have a greater significance. 3147 Note that it is always possible to select a valid set of MPRs. The 3148 set of all willing symmetric 1-hop neighbors of a router is a 3149 (maximal) valid set of MPRs for that router. However a router SHOULD 3150 NOT select a symmetric 1-hop neighbor with N_willingness != 3151 WILL_ALWAYS as an MPR if there are no symmetric strict 2-hop 3152 neighbors with a symmetric link to that symmetric 1-hop neighbor. 3153 Thus a router with no symmetric 1-hop neighbors with N_willingness = 3154 WILL_ALWAYS and with no symmetric strict 2-hop neighbors SHOULD NOT 3155 select any MPRs. 3157 A router MAY select its MPRs for each OLSRv2 interface independently, 3158 or it MAY coordinate its MPR selections across its OLSRv2 interfaces, 3159 as long as the required condition is satisfied for each OLSRv2 3160 interface. Each router MAY select its MPRs independently from the 3161 MPR selection by other routers, or it MAY, for example, give 3162 preference to routers that either are, or are not, already selected 3163 as MPRs by other routers. 3165 When selecting MPRs for each OLSRv2 interface independently, this MAY 3166 be done using information from the Link Set and 2-Hop Set of that 3167 OLSRv2 interface only, and the Neighbor Set of the router 3168 (specifically the N_willingness elements). 3170 The selection of MPRs is recorded in the Neighbor Set of the router, 3171 by setting N_mpr = true for any selected MPR (on any OLSRv2 3172 interface) and ensuring that N_mpr = false otherwise. A selected MPR 3173 MUST be a willing symmetric 1-hop neighbor (i.e., MUST have 3174 corresponding N_symmetric = true, and corresponding N_willingness != 3175 WILL_NEVER). Note that although selected per OLSRv2 interface, MPRs 3176 are recorded and used independent of interface, i.e., a router's set 3177 of MPRs is the union of the sets of MPRs selected per OLSRv2 3178 interface. 3180 A router MUST recalculate its MPRs whenever the currently selected 3181 set of MPRs does not still satisfy the required conditions. It MAY 3182 recalculate its MPRs if the current set of MPRs is still valid, but 3183 could be more efficient. Sufficient conditions to recalculate a 3184 router's set of MPRs are given in Section 17.6. 3186 An example algorithm that creates a set of MPRs that satisfies the 3187 required conditions is given in Appendix A. 3189 19. Routing Set Calculation 3191 The Routing Set of a router is populated with Routing Tuples that 3192 represent paths from that router to all destinations in the network. 3193 These paths are calculated based on the Network Topology Graph, which 3194 is constructed from information in the Information Bases, obtained 3195 via HELLO and TC message exchange. 3197 Changes to the Routing Set do not require any messages to be 3198 transmitted. The state of the Routing Set SHOULD, however, be 3199 reflected in IP's routing table by adding and removing entries from 3200 IP's routing table as appropriate. Only appropriate Routing Tuples 3201 (in particular only those that represent local links or paths to 3202 routable addresses) need be reflected in IP's routing table. 3204 19.1. Network Topology Graph 3206 The Network Topology Graph is formed from information from the 3207 router's Local Interface Set, Link Sets, Neighbor Set, Router 3208 Topology Set, Routable Address Topology Set and Attached Network Set. 3209 The Network Topology Graph MAY also use information from the router's 3210 2-Hop Sets. The Network Topology Graph forms the router's 3211 topological view of the network in form of a directed graph. Each 3212 edge in that graph has a metric value. The Network Topology Graph 3213 has a "backbone" (within which minimum total metric routes will be 3214 constructed) containing the following edges: 3216 o Edges X -> Y for all possible Y, and one X per Y, such that: 3218 * Y is the N_orig_addr of a Neighbor Tuple, AND; 3220 * N_orig_addr is not unknown; 3222 * X is in the I_local_iface_addr_list of a Local Interface Tuple, 3223 AND; 3225 * There is a Link Tuple with L_status = SYMMETRIC such that this 3226 Neighbor Tuple and this Local Interface Tuple correspond to it. 3227 A network address from L_neighbor_iface_addr_list will be 3228 denoted R in this case. 3230 It SHOULD be preferred, where possible, to select R = S and X from 3231 the Local Interface Tuple corresponding to the Link Tuple from 3232 which R was selected. The metrio such an edge is the 3233 corresponding N_out_metric. 3235 o All edges W -> U such that: 3237 * W is the TR_from_orig_addr of a Router Topology Tuple, AND; 3239 * U is the TR_to_orig_addr of the same Router Topology Tuple. 3241 The metrio of such an edge is the corresponding TR_metric. 3243 The Network Topology Graph is further "decorated" with the following 3244 edges. If a network address S, V, Z or T equals a network address Y 3245 or W, then the edge terminating in the network address S, V, Z or T 3246 MUST NOT be used in any path. 3248 o Edges X -> S for all possible S, and one X per S, such that: 3250 * S is in the N_neighbor_addr_list of a Neighbor Tuple, AND; 3252 * X is in the I_local_iface_addr_list of a Local Interface Tuple, 3253 AND; 3255 * There is a Link Tuple with L_status = SYMMETRIC such that this 3256 Neighbor Tuple and this Local Interface Tuple correspond to it. 3257 A network address from L_neighbor_iface_addr_list will be 3258 denoted R in this case. 3260 It SHOULD be preferred, where possible, to select R = S and X from 3261 the Local Interface Tuple corresponding to the Link Tuple from 3262 which R was selected. The metric of such an edge is the 3263 corresponding N_out_metric. 3265 o All edges W -> V such that: 3267 * W is the TA_from_orig_addr of a Routable Address Topology 3268 Tuple, AND; 3270 * V is the TA_dest_addr of the same Routable Address Topology 3271 Tuple. 3273 The metric for such an edge is the corresponding TA_metric. 3275 o All edges W -> T such that: 3277 * W is the AN_orig_addr of an Attached Network Tuple, AND; 3279 * T is the AN_net_addr of the same Attached Network Tuple. 3281 The metric for such an edge is the corresponding AN_metric. 3283 o OPTIONALLY, all edges Y -> Z such that: 3285 * Z is a routable address and is the N2_2hop_addr of a 2-Hop 3286 Tuple, AND; 3288 * Y is the N_orig_addr of the corresponding Neighbor Tuple, AND; 3290 * This Neighbor Tuple has N_willingness not equal to WILL_NEVER. 3292 A path terminating with such an edge SHOULD NOT be used in 3293 preference to any other path. The metric for such an edge is the 3294 corresponding N2_metric. 3296 Any part of the Topology Graph which is not connected to a local 3297 network address X is not used. Only one selection X SHOULD be made 3298 from each I_local_iface_addr_list, and only one selection R SHOULD be 3299 made from any L_neighbor_iface_addr_list. All edges have a hop count 3300 of 1, except edges W -> T that have a hop count of the corresponding 3301 value of AN_dist. 3303 19.2. Populating the Routing Set 3305 The Routing Set MUST contain the shortest paths for all destinations 3306 from all local OLSRv2 interfaces using the Network Topology Graph. 3307 This calculation MAY use any algorithm, including any means of 3308 choosing between paths of equal total metric. (In the case of two 3309 paths of equal total metric but differing hop counts, the path with 3310 the lower hop count SHOULD be used.) 3312 Using the notation of Section 19.1, initially "backbone" paths using 3313 only edges X -> Y and W -> U need be constructed (using a minimum 3314 distance algorithm). Then paths using only a final edge of the other 3315 types may be added. These MUST NOT replace backbone paths with the 3316 same destination (and paths terminating in an edge Y -> Z SHOULD NOT 3317 replace paths with any other form of terminating edge). 3319 Each path will correspond to a Routing Tuple. These will be of two 3320 types. The first type will represent single edge paths, of type X -> 3321 S or X -> Y, by: 3323 o R_local_iface_addr := X; 3325 o R_next_iface_addr := R; 3327 o R_dest_addr := S or Y; 3329 o R_dist := 1; 3331 o R_metric := edge metric. 3333 where R is as defined in Section 19.1 for these types of edges. 3335 The second type will represent a multiple edge path, which will 3336 always have first edge of type X -> Y, and will have final edge of 3337 type W -> U, W -> V, W -> T or Y -> Z. The Routing Tuple will be: 3339 o R_local_iface_addr := X; 3341 o R_next_iface_addr := Y; 3343 o R_dest_addr := U, V, T or Z; 3345 o R_dist := the total hop count of all edges in the path; 3347 o R_dist := the total metric of all edges in the path. 3349 Finally, Routing Tuples of the second type whose R_dest_addr is not 3350 routable MAY be discarded. 3352 An example algorithm for calculating the Routing Set of a router is 3353 given in Appendix B. 3355 20. Proposed Values for Parameters and Constants 3357 This protocol uses all parameters and constants defined in [RFC6130] 3358 and additional parameters and constants defined in this 3359 specification. All but one (RX_HOLD_TIME) of these additional 3360 parameters are router parameters as defined in [RFC6130]. These 3361 proposed values of the additional parameters are appropriate to the 3362 case where all parameters (including those defined in [RFC6130]) have 3363 a single value. Proposed values for parameters defined in [RFC6130] 3364 are given in that specification. 3366 20.1. Local History Time Parameters 3368 o O_HOLD_TIME := 30 seconds 3370 20.2. Message Interval Parameters 3372 o TC_INTERVAL := 5 seconds 3374 o TC_MIN_INTERVAL := TC_INTERVAL/4 3376 20.3. Advertised Information Validity Time Parameters 3378 o T_HOLD_TIME := 3 x TC_INTERVAL 3380 o A_HOLD_TIME := T_HOLD_TIME 3382 20.4. Received Message Validity Time Parameters 3384 o RX_HOLD_TIME := 30 seconds 3386 o P_HOLD_TIME := 30 seconds 3388 o F_HOLD_TIME := 30 seconds 3390 20.5. Jitter Time Parameters 3392 o TP_MAXJITTER := HP_MAXJITTER 3394 o TT_MAXJITTER := HT_MAXJITTER 3396 o F_MAXJITTER := TT_MAXJITTER 3398 20.6. Hop Limit Parameter 3400 o TC_HOP_LIMIT := 255 3402 20.7. Willingness Parameter and Constants 3404 o WILLINGNESS := WILL_DEFAULT 3406 o WILL_NEVER := 0 3408 o WILL_DEFAULT := 7 3410 o WILL_ALWAYS := 15 3412 21. Sequence Numbers 3414 Sequence numbers are used in this specification for the purpose of 3415 discarding "old" information, i.e., messages received out of order. 3416 However with a limited number of bits for representing sequence 3417 numbers, wrap-around (that the sequence number is incremented from 3418 the maximum possible value to zero) will occur. To prevent this from 3419 interfering with the operation of this protocol, the following MUST 3420 be observed when determining the ordering of sequence numbers. 3422 The term MAXVALUE designates in the following one more than the 3423 largest possible value for a sequence number. For a 16 bit sequence 3424 number (as are those defined in this specification) MAXVALUE is 3425 65536. 3427 The sequence number S1 is said to be "greater than" the sequence 3428 number S2 if: 3430 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 3432 o S2 > S1 AND S2 - S1 > MAXVALUE/2 3434 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 3435 cannot be determined. In this case, which should not occur, either 3436 ordering may be assumed. 3438 Thus when comparing two messages, it is possible - even in the 3439 presence of wrap-around - to determine which message contains the 3440 most recent information. 3442 22. Extensions 3444 An extension to this protocol will need to interact with this 3445 specification, and possibly also with [RFC6130]. This protocol is 3446 designed to permit such interactions, in particular: 3448 o Through accessing, and possibly extending, the information in the 3449 Information Bases. All updates to the elements specified in this 3450 specification are subject to the constraints specified in 3451 [RFC6130] and Appendix D. 3453 o Through accessing an outgoing message prior to it being 3454 transmitted over any OLSRv2 interface, and to add information to 3455 it as specified in [RFC5444]. This MAY include Message TLVs 3456 and/or network addresses with associated Address Block TLVs. 3457 (Network addresses without new associated TLVs SHOULD NOT be added 3458 to messages.) This may, for example, be to allow a security 3459 protocol, as suggested in Section 23, to add a TLV containing a 3460 cryptographic signature to the message. 3462 o Through accessing an incoming message, and potentially discarding 3463 it prior to processing by this protocol. This may, for example, 3464 allow a security protocol as suggested in Section 23 to perform 3465 verification of message signatures and prevent processing and/or 3466 forwarding of unverifiable messages by this protocol. 3468 o Through accessing an incoming message after it has been completely 3469 processed by this protocol. This may, in particular, allow a 3470 protocol which has added information, by way of inclusion of 3471 appropriate TLVs, or of network addresses associated with new 3472 TLVs, access to such information after appropriate updates have 3473 been recorded in the Information Bases in this protocol. 3475 o Through requesting that a message be generated at a specific time. 3476 In that case, message generation MUST still respect the 3477 constraints in [RFC6130] and Section 5.4.3. 3479 23. Security Considerations 3481 Currently, this protocol does not specify any special security 3482 measures. As a proactive routing protocol, this protocol is a 3483 potential target for various attacks. Various possible 3484 vulnerabilities are discussed in this section. 3486 23.1. Confidentiality 3488 This protocol periodically MPR floods topological information to all 3489 routers in the network. Hence, if used in an unprotected wireless 3490 network, the network topology is revealed to anyone who listens to 3491 the control messages. 3493 In situations where the confidentiality of the network topology is of 3494 importance, regular cryptographic techniques, such as exchange of 3495 OLSRv2 control traffic messages encrypted by PGP [RFC4880] or 3496 encrypted by some shared secret key, can be applied to ensure that 3497 control traffic can be read and interpreted by only those authorized 3498 to do so. 3500 23.2. Integrity 3502 Each router is injecting topological information into the network 3503 through transmitting HELLO messages and, for some routers, TC 3504 messages. If some routers for some reason, malicious or malfunction, 3505 inject invalid control traffic, network integrity may be compromised. 3506 Therefore, message authentication is recommended. 3508 Different such situations may occur, for instance: 3510 1. a router generates TC messages, advertising links to non-neighbor 3511 routers; 3513 2. a router generates TC messages, pretending to be another router; 3515 3. a router generates HELLO messages, advertising non-neighbor 3516 routers; 3518 4. a router generates HELLO messages, pretending to be another 3519 router; 3521 5. a router forwards altered control messages; 3523 6. a router does not forward control messages; 3525 7. a router does not select multipoint relays correctly; 3527 8. a router forwards broadcast control messages unaltered, but does 3528 not forward unicast data traffic; 3530 9. a router "replays" previously recorded control traffic from 3531 another router. 3533 Authentication of the originator router for control messages (for 3534 situations 2, 4 and 5) and on the individual links announced in the 3535 control messages (for situations 1 and 3) may be used as a 3536 countermeasure. However to prevent routers from repeating old (and 3537 correctly authenticated) information (situation 9) temporal 3538 information is required, allowing a router to positively identify 3539 such delayed messages. 3541 In general, digital signatures and other required security 3542 information may be transmitted as a separate Message Type, or 3543 signatures and security information may be transmitted within the 3544 HELLO and TC messages, using the TLV mechanism. Either option 3545 permits that "secured" and "unsecured" routers can coexist in the 3546 same network, if desired, 3548 Specifically, the authenticity of entire control packets can be 3549 established through employing IPsec authentication headers, whereas 3550 authenticity of individual links (situations 1 and 3) require 3551 additional security information to be distributed. 3553 An important consideration is that all control messages are 3554 transmitted either to all routers in the neighborhood (HELLO 3555 messages) or broadcast to all routers in the network (TC messages). 3557 For example, a control message in this protocol is always a point-to- 3558 multipoint transmission. It is therefore important that the 3559 authentication mechanism employed permits that any receiving router 3560 can validate the authenticity of a message. As an analogy, given a 3561 block of text, signed by a PGP private key, then anyone with the 3562 corresponding public key can verify the authenticity of the text. 3564 23.3. Interaction with External Routing Domains 3566 This protocol does, through the use of TC messages, provide a basic 3567 mechanism for injecting external routing information to this 3568 protocol's domain. Routing information can be extracted from the 3569 protocol's Information Bases, in particular the Routing Set, of this 3570 protocol and, potentially, injected into an external domain, if the 3571 routing protocol governing that domain permits this. 3573 When operating routers connecting a MANET using this protocol to an 3574 external routing domain, care MUST be taken not to allow potentially 3575 insecure and untrustworthy information to be injected from this 3576 domain to external routing domains. Care MUST also be taken to 3577 validate the correctness of information prior to it being injected as 3578 to avoid polluting routing tables with invalid information. 3580 A recommended way of extending connectivity from an existing routing 3581 domain to a MANET routed using this protocol is to assign an IP 3582 prefix (under the authority of the routers/gateways connecting the 3583 MANET with the exiting routing domain) exclusively to that MANET 3584 area, and to statically configure the gateways to advertise routes 3585 for that IP sequence to routers in the existing routing domain. 3587 24. IANA Considerations 3589 This specification defines one Message Type, which must be allocated 3590 from the "Message Types" repository of [RFC5444], two Message TLV 3591 Types, which must be allocated from the "Message TLV Types" 3592 repository of [RFC5444], and four Address Block TLV Types, which must 3593 be allocated from the "Address Block TLV Types" repository of 3594 [RFC5444]. 3596 24.1. Expert Review: Evaluation Guidelines 3598 For the registries where an Expert Review is required, the designated 3599 expert SHOULD take the same general recommendations into 3600 consideration as are specified by [RFC5444]. 3602 24.2. Message Types 3604 This specification defines one Message Type, to be allocated from the 3605 0-223 range of the "Message Types" namespace defined in [RFC5444], as 3606 specified in Table 8. 3608 +------+----------------------------------------------+ 3609 | Type | Description | 3610 +------+----------------------------------------------+ 3611 | TBD1 | TC : Topology Control (MANET-wide signaling) | 3612 +------+----------------------------------------------+ 3614 Table 8: Message Type assignment 3616 24.3. Message-Type-specific TLV Type Registries 3618 IANA is requested to create a registry for Message-Type-specific 3619 Message TLVs for TC messages, in accordance with Section 6.2.1 of 3620 [RFC5444], and with initial assignments and allocation policies as 3621 specified in Table 9. 3623 +---------+-------------+-------------------+ 3624 | Type | Description | Allocation Policy | 3625 +---------+-------------+-------------------+ 3626 | 128-223 | Unassigned | Expert Review | 3627 +---------+-------------+-------------------+ 3629 Table 9: TC Message-Type-specific Message TLV Types 3631 IANA is requested to create a registry for Message-Type-specific 3632 Address Block TLVs for TC messages, in accordance with Section 6.2.1 3633 of [RFC5444], and with initial assignments and allocation policies as 3634 specified in Table 10. 3636 +---------+-------------+-------------------+ 3637 | Type | Description | Allocation Policy | 3638 +---------+-------------+-------------------+ 3639 | 128-223 | Unassigned | Expert Review | 3640 +---------+-------------+-------------------+ 3642 Table 10: TC Message-Type-specific Address Block TLV Types 3644 24.4. Message TLV Types 3646 This specification defines two Message TLV Types, which must be 3647 allocated from the "Message TLV Types" namespace defined in 3648 [RFC5444]. IANA is requested to make allocations in the 0-127 range 3649 for these types. This will create two new Type Extension registries 3650 with assignments as specified in Table 11 and Table 12. 3651 Specifications of these TLVs are in Section 13.3.1. Each of these 3652 TLVs MUST NOT be included more than once in a Message TLV Block. 3654 +-------------+------+-----------+---------------------+------------+ 3655 | Name | Type | Type | Description | Allocation | 3656 | | | Extension | | Policy | 3657 +-------------+------+-----------+---------------------+------------+ 3658 | MPR_WILLING | TBD2 | 0 | Bits 0-3 encode | | 3659 | | | | specify the | | 3660 | | | | originating | | 3661 | | | | router's | | 3662 | | | | willingness to act | | 3663 | | | | as a flooding | | 3664 | | | | relay; bits 4-7 | | 3665 | | | | encode specify the | | 3666 | | | | originating | | 3667 | | | | router's | | 3668 | | | | willingness to act | | 3669 | | | | as a routing relay | | 3670 | MPR_WILLING | TBD2 | 1-255 | Unassigned | Expert | 3671 | | | | | Review | 3672 +-------------+------+-----------+---------------------+------------+ 3674 Table 11: Message TLV Type assignment: MPR_WILLING 3676 +--------------+------+-----------+--------------------+------------+ 3677 | Name | Type | Type | Description | Allocation | 3678 | | | Extension | | Policy | 3679 +--------------+------+-----------+--------------------+------------+ 3680 | CONT_SEQ_NUM | TBD3 | 0 | COMPLETE : | | 3681 | | | | Specifies a | | 3682 | | | | content sequence | | 3683 | | | | number for this | | 3684 | | | | complete message | | 3685 | CONT_SEQ_NUM | TBD3 | 1 | INCOMPLETE : | | 3686 | | | | Specifies a | | 3687 | | | | content sequence | | 3688 | | | | number for this | | 3689 | | | | incomplete message | | 3690 | CONT_SEQ_NUM | TBD3 | 2-255 | Unassigned | Expert | 3691 | | | | | Review | 3692 +--------------+------+-----------+--------------------+------------+ 3694 Table 12: Message TLV Type assignment: CONT_SEQ_NUM 3696 Type extensions indicated as Expert Review SHOULD be allocated as 3697 described in [RFC5444], based on Expert Review as defined in 3699 [RFC5226]. 3701 24.5. Address Block TLV Types 3703 This specification defines four Address Block TLV Types, which must 3704 be allocated from the "Address Block TLV Types" namespace defined in 3705 [RFC5444]. IANA are requested to make allocations in the 8-127 range 3706 for these types. This will create four new Type Extension registries 3707 with assignments as specified in Table 13, Table 14, Table 15 and 3708 Table 16. Specifications of these TLVs are in Section 13.3.2. 3710 +-------------+------+-----------+-------------------+--------------+ 3711 | Name | Type | Type | Description | Allocation | 3712 | | | Extension | | Policy | 3713 +-------------+------+-----------+-------------------+--------------+ 3714 | LINK_METRIC | TBD4 | 0 | Link metric | | 3715 | | | | meaning assigned | | 3716 | | | | by administrative | | 3717 | | | | action | | 3718 | LINK_METRIC | TBD4 | 1-223 | Unassigned | Expert | 3719 | | | | | Review | 3720 | LINK_METRIC | TBD4 | 224-255 | Unassigned | Experimental | 3721 | | | | | Use | 3722 +-------------+------+-----------+-------------------+--------------+ 3724 Table 13: Address Block TLV Type assignment: LINK_METRIC 3726 All LINK_METRIC TLVs, whatever their type extension, MUST use their 3727 value field to encode the kind and value (in the interval 3728 MINIMUM_METRIC, to MAXIMUM_METRIC, inclusive) of a link metric as 3729 specified in Section 6 and Section 13.3.2. An assignment of a 3730 LINK_METRIC TLV type extension MUST specify the physical meaning, and 3731 mapping of that physical meaning to the representable values in the 3732 indicated interval, of the link metric. 3734 +------+------+-----------+----------------------------+------------+ 3735 | Name | Type | Type | Description | Allocation | 3736 | | | Extension | | Policy | 3737 +------+------+-----------+----------------------------+------------+ 3738 | MPR | TBD5 | 0 | Specifies that a given | | 3739 | | | | network address is of a | | 3740 | | | | router selected as a | | 3741 | | | | flooding MPR (FLOODING = | | 3742 | | | | 1), that a given network | | 3743 | | | | address is of a router | | 3744 | | | | selected as a routing MPR | | 3745 | | | | (ROUTING = 2), or both | | 3746 | | | | (FLOOD_ROUTE = 3) | | 3747 | MPR | TBD5 | 1-255 | Unassigned | Expert | 3748 | | | | | Review | 3749 +------+------+-----------+----------------------------+------------+ 3751 Table 14: Address Block TLV Type assignment: MPR 3753 +---------------+------+-----------+-------------------+------------+ 3754 | Name | Type | Type | Description | Allocation | 3755 | | | Extension | | Policy | 3756 +---------------+------+-----------+-------------------+------------+ 3757 | NBR_ADDR_TYPE | TBD6 | 0 | Specifies that a | | 3758 | | | | given network | | 3759 | | | | address is of a | | 3760 | | | | neighbor reached | | 3761 | | | | via the | | 3762 | | | | originating | | 3763 | | | | router, if it is | | 3764 | | | | an originator | | 3765 | | | | address | | 3766 | | | | (ORIGINATOR = 1), | | 3767 | | | | is a routable | | 3768 | | | | address (ROUTABLE | | 3769 | | | | = 2), or if it is | | 3770 | | | | both | | 3771 | | | | (ROUTABLE_ORIG = | | 3772 | | | | 3) | | 3773 | NBR_ADDR_TYPE | TBD6 | 1-255 | Unassigned | Expert | 3774 | | | | | Review | 3775 +---------------+------+-----------+-------------------+------------+ 3777 Table 15: Address Block TLV Type assignment: NBR_ADDR_TYPE 3779 +---------+------+-----------+-------------------------+------------+ 3780 | Name | Type | Type | Description | Allocation | 3781 | | | extension | | Policy | 3782 +---------+------+-----------+-------------------------+------------+ 3783 | GATEWAY | TBD7 | 0 | Specifies that a given | | 3784 | | | | network address is | | 3785 | | | | reached via a gateway | | 3786 | | | | on the originating | | 3787 | | | | router, with value | | 3788 | | | | equal to the number of | | 3789 | | | | hops | | 3790 | GATEWAY | TBD7 | 1-255 | | Expert | 3791 | | | | | Review | 3792 +---------+------+-----------+-------------------------+------------+ 3794 Table 16: Address Block TLV Type assignment: GATEWAY 3796 Type extensions indicated as Expert Review SHOULD be allocated as 3797 described in [RFC5444], based on Expert Review as defined in 3798 [RFC5226]. 3800 24.6. NBR_ADDR_TYPE Values 3802 Note: This section does not require any IANA action, as the required 3803 information is included in the descriptions of the MPR and 3804 NBR_ADDR_TYPE Address Block TLVs allocated in Section 24.5. This 3805 information is recorded here for clarity, and for use elsewhere in 3806 this specification. 3808 The Values which the MPR Address Block TLV can use are the following: 3810 o FLOODING := 1; 3812 o ROUTING := 2; 3814 o FLOOD_ROUTE := 3. 3816 The Values which the NBR_ADDR_TYPE Address Block TLV can use are the 3817 following: 3819 o ORIGINATOR := 1; 3821 o ROUTABLE := 2; 3823 o ROUTABLE_ORIG := 3. 3825 25. Contributors 3827 This specification is the result of the joint efforts of the 3828 following contributors -- listed alphabetically. 3830 o Cedric Adjih, INRIA, France, 3832 o Emmanuel Baccelli, INRIA , France, 3834 o Thomas Heide Clausen, LIX, France, 3836 o Justin Dean, NRL, USA, 3838 o Christopher Dearlove, BAE Systems, UK, 3839 3841 o Satoh Hiroki, Hitachi SDL, Japan, 3843 o Philippe Jacquet, INRIA, France, 3845 o Monden Kazuya, Hitachi SDL, Japan, 3847 o Kenichi Mase, Niigata University, Japan, 3849 o Ryuji Wakikawa, Toyota, Japan, 3851 26. Acknowledgments 3853 The authors would like to acknowledge the team behind OLSRv1, 3854 specified in RFC3626, including Anis Laouiti (INT, Paris), Pascale 3855 Minet (INRIA, France), Laurent Viennot (INRIA, France), and Amir 3856 Qayyum (M.A. Jinnah University, Islamabad) for their contributions. 3858 The authors would like to gratefully acknowledge the following people 3859 for intense technical discussions, early reviews and comments on the 3860 specification and its components (listed alphabetically): Khaldoun Al 3861 Agha (LRI), Teco Boot (Infinity Networks), Song-Yean Cho (LIX), Alan 3862 Cullen (BAE Systems), Louise Lamont (CRC), Li Li (CRC), Joe Macker 3863 (NRL), Richard Ogier (SRI), Charles E. Perkins (WiChorus), Henning 3864 Rogge (FGAN), and the entire IETF MANET working group. 3866 27. References 3868 27.1. Normative References 3870 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3871 Requirement Levels", RFC 2119, BCP 14, March 1997. 3873 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 3874 Considerations in Mobile Ad Hoc Networks (MANETs)", 3875 RFC 5148, February 2008. 3877 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 3878 IANA Considerations Section in RFCs", RFC 5226, BCP 26, 3879 May 2008. 3881 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 3882 "Generalized Mobile Ad Hoc Network (MANET) Packet/ 3883 Message Format", RFC 5444, February 2009. 3885 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 3886 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, 3887 March 2009. 3889 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc 3890 Network (MANET) Protocols", RFC 5498, March 2009. 3892 [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc 3893 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 3894 RFC 6130, April 2011. 3896 27.2. Informative References 3898 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 3899 (MANET): Routing Protocol Performance Issues and 3900 Evaluation Considerations", RFC 2501, January 1999. 3902 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 3903 Routing Protocol", RFC 3626, October 2003. 3905 [RFC4880] Callas, J., Donnerhacke, L., Finney, H., and R. Thayer, 3906 "OpenPGP message format", RFC 4880, November 2007. 3908 [HIPERLAN] ETSI, "ETSI STC-RES10 Committee. Radio equipment and 3909 systems: HIPERLAN type 1, functional specifications ETS 3910 300-652", June 1996. 3912 [HIPERLAN2] Jacquet, P., Minet, P., Muhlethaler, P., and N. 3913 Rivierre, "Increasing reliability in cable free radio 3914 LANs: Low level forwarding in HIPERLAN.", 1996. 3916 [MPR] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint 3917 relaying: An efficient technique for flooding in mobile 3918 wireless networks.", 2001. 3920 [FSR] Pei, G., Gerla, M., and T. Chen, "Fisheye state routing 3921 in mobile ad hoc networks", 2000. 3923 [FSLS] Santivanez, C., Ramanathan, R., and I. Stavrakakis, 3924 "Making link-state routing scale for ad hoc networks", 3925 2000. 3927 Appendix A. Example Algorithm for Calculating MPRs 3929 Note: This appendix has not yet been updated to use link metrics and 3930 separate sets of flooding and routing MPRs. 3932 The following specifies an algorithm which MAY be used to select 3933 MPRs. MPRs are calculated per OLSRv2 interface, but then a single 3934 set of MPRs is formed from the union of the MPRs for all OLSRv2 3935 interfaces. (As noted in Section 18 a router MAY improve on this, by 3936 coordination between OLSRv2 interfaces.) A router's MPRs are 3937 recorded using the element N_mpr in Neighbor Tuples. 3939 If using this example algorithm then the following steps MUST be 3940 executed in order for a router to select its MPRs: 3942 1. Set N_mpr := false in all Neighbor Tuples; 3944 2. For each Neighbor Tuple with N_symmetric = true and N_willingness 3945 = WILL_ALWAYS, set N_mpr := true; 3947 3. For each OLSRv2 interface of the router, use the algorithm in 3948 Appendix A.2. Note that this sets N_mpr := true for some 3949 Neighbor Tuples, these routers are already selected as MPRs when 3950 using the algorithm for following OLSRv2 interfaces. 3952 4. OPTIONALLY, consider each selected MPR in turn, and if the set of 3953 selected MPRs without that router still satisfies the necessary 3954 conditions, for all OLSRv2 interfaces, then that router MAY be 3955 removed from the set of MPRs. This process MAY be repeated until 3956 no MPRs are removed. Routers MAY be considered in order of 3957 increasing N_willingness. 3959 Note that only symmetric strict 2-hop neighbors are considered, thus: 3961 o Symmetric 1-hop neighbor routers with N_willingness = WILL_NEVER 3962 MUST NOT be selected as MPRs, and MUST be ignored in the following 3963 algorithm (and hence also ignore any 2-Hop Tuples whose 3964 N2_neighbor_iface_addr_list is included in the 3965 N_neighbor_addr_list of any such Neighbor Tuple). 3967 o Symmetric 2-hop neighbor routers which are also symmetric 1-hop 3968 neighbor routers MUST be ignored in the following algorithm (i.e., 3969 ignore any 2-Hop Tuples whose N2_2hop_addr is in the 3970 N_neighbor_addr_list of any Neighbor Tuple). 3972 A.1. Terminology 3974 The following terminology will be used when selecting MPRs for the 3975 OLSRv2 interface I: 3977 N(I) - The set of symmetric 1-hop neighbors which have a symmetric 3978 link to I. 3980 N2(I) - The set of network addresses of interfaces of a router with 3981 a symmetric link to a router in N(I); this MAY be restricted to 3982 considering only information received over I (in which case N2(I) 3983 is the set of N2_2hop_addr in 2-Hop Tuples in the 2-Hop Set for 3984 OLSRv2 interface I). 3986 Connected to I via Y - A network address A in N2(I) is connected to 3987 I via a router Y in N(I) if A is a network address of an interface 3988 of a symmetric 1-hop neighbor of Y (i.e., A is the N2_2hop_addr in 3989 a 2-Hop Tuple in the 2-Hop Set for OLSRv2 interface I, and whose 3990 N2_neighbor_iface_addr_list is contained in the set of interface 3991 network addresses of Y). 3993 D(Y, I) - For a router Y in N(I), the number of network addresses in 3994 N2(I) which are connected to I via Y. 3996 R(Y, I): - For a router Y in N(I), the number of network addresses 3997 in N2(I) which are connected to I via Y, but are not connected to 3998 I via any router which has already been selected as an MPR. 4000 A.2. MPR Selection Algorithm for each OLSRv2 Interface 4002 When selecting MPRs for the OLSRv2 interface I: 4004 1. For each network address A in N2(I) for which there is only one 4005 router Y in N(I) such that A is connected to I via Y, select that 4006 router Y as an MPR (i.e., set N_mpr := true in the Neighbor Tuple 4007 corresponding to Y). 4009 2. While there exists any router Y in N(I) with R(Y, I) > 0: 4011 1. Select a router Y in N(I) with R(Y, I) > 0 in the following 4012 order of priority: 4014 + greatest N_willingness in the Neighbor Tuple corresponding 4015 to Y, THEN; 4017 + greatest R(Y, I), THEN; 4019 + greatest D(Y, I), THEN; 4021 + N_mpr_selector is equal to true, if possible, THEN; 4023 + any choice. 4025 2. Select Y as an MPR (i.e., set N_mpr := true in the Neighbor 4026 Tuple corresponding to Y). 4028 Appendix B. Example Algorithm for Calculating the Routing Set 4030 The following procedure is given as an example for calculating the 4031 Routing Set using a variation of Dijkstra's algorithm. First all 4032 Routing Tuples are removed, and then, using the selections and 4033 definitions in Appendix B.1, the procedures in the following sections 4034 (each considered a "stage" of the processing) are applied in turn. 4036 B.1. Local Interfaces and Neighbors 4038 The following selections and definitions are made: 4040 1. For each Local Interface Tuple, select a network address from its 4041 I_local_iface_addr_list, this is defined as the selected address 4042 for this Local Interface Tuple. 4044 2. For each Link Tuple, the selected address of its corresponding 4045 Local Interface Tuple is defined as the selected local address 4046 for this Local Interface Tuple. 4048 3. For each Neighbor Tuple with N_symmetric = true, select a Link 4049 Tuple with L_status = SYMMETRIC for which this is the 4050 corresponding Neighbor Tuple and has L_out_metric = N_out_metric. 4051 This is defined as the selected Link Tuple for this Neighbor 4052 Tuple. 4054 4. For each network address (N_orig_addr or in N_neighbor_addr_list, 4055 the "neighbor address") from a Neighbor Tuple with N_symmetric = 4056 true, select a Link Tuple (the "selected Link Tuple") from those 4057 for which this is the corresponding Neighbor Tuple, have L_status 4058 = SYMMETRIC, and have L_out_metric = N_out_metric, by: 4060 1. If there is such a Link Tuple whose 4061 L_neighbor_iface_addr_list contains the neighbor address, 4062 select that Link Tuple. 4064 2. Otherwise select the selected Link Tuple for this Neighbor 4065 Tuple. 4067 Then for this neighbor address: 4069 3. The selected local address is defined as the selected local 4070 address for the selected Link Tuple. 4072 4. The selected link address is defined as an address from the 4073 L_neighbor_iface_addr_list of the selected Link Tuple, if 4074 possible equal to this neighbor address. 4076 5. Routing Tuple preference is decided by preference for minimum 4077 R_dist, and then for preference for corresponding Neighbor Tuples 4078 in this order: 4080 * For greater N_willingness. 4082 * For N_mpr_selector = true over N_mpr_selector = false. 4084 Note that preferred Routing Tuples SHOULD be used. Routing 4085 Tuples with minimum R_metric MUST be used, this is specified 4086 outside the definition of preference. An implementation MAY 4087 modify this definition of preference without otherwise affecting 4088 this algorithm. 4090 B.2. Add Neighbor Routers 4092 The following procedure is executed once. 4094 1. For each Neighbor Tuple with N_symmetric = true, add a Routing 4095 Tuple with: 4097 * R_dest_addr := N_orig_addr; 4099 * R_next_iface_addr := selected link address for N_orig_addr; 4101 * R_local_iface_addr := selected local address for N_orig_addr; 4103 * R_metric := N_out_metric; 4105 * R_dist := 1. 4107 B.3. Add Remote Routers 4109 The following procedure is executed for each value of h, starting 4110 with h := 1 and incrementing by 1 for each iteration. The execution 4111 MUST stop if no Routing Tuples are added or modified in an iteration. 4113 1. For each Router Topology Tuple, if: 4115 * TR_from_orig_addr is equal to the R_dest_addr of a Routing 4116 Tuple with R_dist = h (the "previous Routing Tuple"), 4118 then consider the candidate Routing Tuple with: 4120 * R_dest_addr := TR_to_orig_addr; 4122 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4123 Tuple; 4125 * R_local_iface_addr := R_local_iface_addr of the previous 4126 Routing Tuple; 4128 * R_metric := R_metric of the previous Routing Tuple + 4129 TR_metric; 4131 * R_dist := h+1. 4133 This candidate Routing Tuple MUST be added to the Routing Set if 4134 there is no existing Routing Tuple with the same R_dest_addr. 4135 Otherwise this candidate Routing Tuple MUST replace the existing 4136 Routing Tuple with the same R_dest_addr if this candidate Routing 4137 Tuple has a smaller R_metric, this candidate Routing Tuple SHOULD 4138 replace the existing Routing Tuple with the same R_dest_addr if 4139 this candidate Routing Tuple has an equal R_metric and is 4140 preferred to the existing Routing Tuple. 4142 B.4. Add Neighbor Addresses 4144 The following procedure is executed once. 4146 1. For each Neighbor Tuple with N_symmetric = true: 4148 1. For each network address (the "neighbor address") in 4149 N_neighbor_addr_list, if the neighbor address is not equal to 4150 the R_dest_addr of any Routing Tuple, then add a new Routing 4151 Tuple, with: 4153 + R_dest_addr := neighbor address; 4155 + R_next_iface_addr := selected link address for the 4156 neighbor address; 4158 + R_local_iface_addr := selected local address for the 4159 neighbor address; 4161 + R_metric := N_out_metric; 4163 + R_dist := 1. 4165 B.5. Add Remote Routable Addresses 4167 The following procedure is executed once. 4169 1. For each Routable Address Topology Tuple, if: 4171 * TA_dest_addr is not equal to the R_dest_addr of any Routing 4172 Tuple added in an earlier stage, AND; 4174 * TA_from_orig_addr is equal to the R_dest_addr of a Routing 4175 Tuple (the "previous Routing Tuple"), 4177 then add a new Routing Tuple, with: 4179 * R_dest_addr := TA_dest_addr; 4181 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4182 Tuple; 4184 * R_local_iface_addr := R_local_iface_addr of the previous 4185 Routing Tuple; 4187 * R_metric := R_metric of the previous Routing Tuple + 4188 TA_metric. 4190 * R_dist := R_dist of the previous Routing Tuple + 1. 4192 There may be more than one Routing Tuple that may be added for an 4193 R_dest_addr in this stage. If so, then, for each such 4194 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4195 selected, otherwise a Routing Tuple which is preferred SHOULD be 4196 added. 4198 B.6. Add Attached Networks 4200 The following procedure is executed once. 4202 1. For each Attached Network Tuple, if: 4204 * AN_net_addr is not equal to the R_dest_addr of any Routing 4205 Tuple added in an earlier stage, AND; 4207 * AN_orig_addr is equal to the R_dest_addr of a Routing Tuple 4208 (the "previous Routing Tuple), 4210 then add a new Routing Tuple, with: 4212 * R_dest_addr := AN_net_addr; 4214 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4215 Tuple; 4217 * R_local_iface_addr := R_local_iface_addr of the previous 4218 Routing Tuple; 4220 * R_metric := R_metric of the previous Routing Tuple + 4221 AN_metric; 4223 * R_dist := R_dist of the previous Routing Tuple + AN_dist. 4225 There may be more than one Routing Tuple that may be added for an 4226 R_dest_addr in this stage. If so, then, for each such 4227 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4228 selected, otherwise a Routing Tuple which is preferred SHOULD be 4229 added. 4231 B.7. Add 2-Hop Neighbors 4233 The following procedure is executed once. 4235 1. For each 2-Hop Tuple, if: 4237 * N2_2hop_addr is a routable address, AND; 4239 * N2_2hop_addr is not equal to the R_dest_addr of any Routing 4240 Tuple added in an earlier stage, AND; 4242 * the Routing Tuple with R_dest_addr = N_orig_addr of the 4243 corresponding Neighbor Tuple (the "previous Routing Tuple") 4244 has R_dist = 1, 4246 then add a new Routing Tuple, with: 4248 * R_dest_addr := N2_2hop_addr; 4250 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4251 Tuple; 4253 * R_local_iface_addr := R_local_iface_addr of the previous 4254 Routing Tuple; 4256 * R_metric := R_metric of the previous Routing Tuple + 4257 N_out_metric of the corresponding Neighbor Tuple; 4259 * R_dist := 2. 4261 There may be more than one Routing Tuple that may be added for an 4262 R_dest_addr in this stage. If so, then, for each such 4263 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4264 selected, otherwise a Routing Tuple which is preferred SHOULD be 4265 added. 4267 Appendix C. TC Message Example 4269 TC messages are instances of [RFC5444] messages. This specification 4270 requires that TC messages contains and fields. It supports TC messages with any combination of 4272 remaining message header options and address encodings, enabled by 4273 [RFC5444] that convey the required information. As a consequence, 4274 there is no single way to represent how all TC messages look. This 4275 appendix illustrates a TC message, the exact values and content 4276 included are explained in the following text. 4278 The TC message's four bit Message Flags (MF) field has value 15 4279 indicating that the message header contains originaor address, hop 4280 limit, hop count, and message sequence number fields. Its four bit 4281 Message Address Length (MAL) field has value 3, indicating addresses 4282 in the message have a length of four octets, here being IPv4 4283 addresses. The overall message length is 71 octets. 4285 The message has a Message TLV Block with content length 13 octets 4286 containing three TLVs. The first two TLVs are validity and interval 4287 times for the message. The third TLV is the content sequence number 4288 TLV used to carry the 2 octet ANSN, and (with default type extension 4289 zero, i.e., COMPLETE) indicating that the TC message is complete. 4290 Each TLV uses a TLV with Flags octet (MTLVF) value 16, indicating 4291 that it has a Value, but no type extension or start and stop indexes. 4292 The first two TLVs have a Value Length of 1 octet, the last has a 4293 Value Length of 2 octets. 4295 The message has two Address Blocks. (This is not necessary, the 4296 information could be conveyed using a single Address Block, the use 4297 of two Address Blocks, which is also allowed, is illustrative only.) 4298 The first Address Block contains 3 addresses, with Flags octet 4299 (ATLVF) value 128, hence with a Head section (with length 2 octets), 4300 but no Tail section, and hence with Mid sections with length two 4301 octets. The following TLV Block (content length 13 octets) contains 4302 two TLVs. The first TLV is a NBR_ADDR_TYPE TLV with Flags octet 4303 (ATLVF) value 16, indicating a single Value but no indexes. Thus all 4304 three addresses are associated with the Value (with Value Length 1 4305 octet) ROUTABLE_ORIG, i.e., they are originator addresses of 4306 advertised neighbors that are also routable addresses. The second 4307 TLV is a LINK_STATUS TLV with Flags octet (ATLVF) value 20, 4308 indicating a Value for each address, i.e. as the total Value Length 4309 is 6 octets, each address is associated with a Value with length two 4310 octets. These Value fields are each shown as having four bits 4311 indicating that they are outgoing neighbor metric values, and as 4312 having twelve bits that represent the metric value (the first four 4313 bits being the exponent, the remaining twelve bits the mantissa). 4315 The second Address Block contains 1 address, with Flags octet (ATLVF) 4316 176, indicating that there is a Head section (with length 2 octets), 4317 that the Tail section (with length 2 octets) consists of zero valued 4318 octets (not included), and that there is a single prefix length, 4319 which is 16. The network address is thus Head.0.0/16. The following 4320 TLV Block (content length 8 octets) includes two TLVs. The first has 4321 a Flags octet (ATLVF) of 16, again indicating that no indexes are 4322 needed, but that a Value (with Value Length 1 octet) is present, 4323 indicating the address distance as a number of hops. The second TLV 4324 is another LINK_METRIC TLV, as in the first Address TLV Block except 4325 with a Flags octet (ATLVF) value 16, indicating that a single Value 4326 is present. 4328 0 1 2 3 4329 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 4330 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4331 | TC | MF=15 | MAL=3 | Message Length = 71 | 4332 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4333 | Originator Address | 4334 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4335 | Hop Limit | Hop Count | Message Sequence Number | 4336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4337 | Message TLV Block Length = 13 | VALIDITY_TIME | MTLVF = 16 | 4338 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4339 | Value Len = 1 | Value (Time) | INTERVAL_TIME | MTLVF = 16 | 4340 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4341 | Value Len = 1 | Value (Time) | CONT_SEQ_NUM | MTLVF = 16 | 4342 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4343 | Value Len = 2 | Value (ANSN) | Num Addrs = 3 | 4344 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4345 | ABF = 128 | Head Len = 2 | Head | 4346 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4347 | Mid | Mid | 4348 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4349 | Mid | Address TLV Block Length = 13 | 4350 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4351 | NBR_ADDR_TYPE | ATLVF = 16 | Value Len = 1 | ROUTABLE_ORIG | 4352 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4353 | LINK_METRIC | ATLVF = 20 | Value Len = 6 |0|0|0|1|Metric | 4354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4355 | Metric (cont) |0|0|0|1| Metric |0|0|0|1|Metric | 4356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4357 | Metric (cont) | Num Addrs = 1 | ABF = 176 | Head Len = 2 | 4358 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4359 | Head | Tail Len = 2 | Pref Len = 16 | 4360 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4361 | Address TLV Block Length = 9 | GATEWAY | ATLVF = 16 | 4362 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4363 | Value Len = 1 | Value (Hops) | LINK_METRIC | ATLVF = 16 | 4364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4365 | Value Len = 2 |0|0|0|1| Metric | 4366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4368 Appendix D. Constraints 4370 Any process which updates the Local Information Base, the 4371 Neighborhood Information Base or the Topology Information Base MUST 4372 ensure that all constraints specified in this appendix are 4373 maintained, as well as those specified in [RFC6130]. 4375 In each Originator Tuple: 4377 o O_orig_addr MUST NOT equal any other O_orig_addr. 4379 o O_orig_addr MUST NOT equal this router's originator address. 4381 In each Local Attached Network Tuple: 4383 o AL_net_addr MUST NOT equal any other AL_net_addr. 4385 o AL_net_addr MUST NOT equal or be a sub-range of any network 4386 address in the I_local_iface_addr_list of any Local Interface 4387 Tuple. 4389 o AL_net_addr MUST NOT equal this router's originator address, or 4390 equal the O_orig_addr in any Originator Tuple. 4392 o AL_dist MUST NOT be less than zero. 4394 In each Link Tuple: 4396 o L_neighbor_iface_addr_list MUST NOT contain any network address 4397 that AL_net_addr of any Local Attached Network Tuple equals or is 4398 a sub-range of. 4400 o If L_status = HEARD or L_status = SYMMETRIC then L_in_metric != 4401 UNKNOWN_METRIC. 4403 o If L_status = SYMMETRIC then L_in_metric != UNKNOWN_METRIC. 4405 o if L_in_metric != UNKNOWN_METRIC then L_in_metric MUST be 4406 representable in the defined compressed form. 4408 o if L_out_metric != UNKNOWN_METRIC then L_out_metric MUST be 4409 representable in the defined compressed form. 4411 o If L_mpr_selector = true, then L_status = SYMMETRIC. 4413 In each Neighbor Tuple: 4415 o N_orig_addr MUST NOT be changed to unknown. 4417 o N_orig_addr MUST NOT equal this router's originator address, or 4418 equal O_orig_addr in any Originator Tuple. 4420 o N_orig_addr MUST NOT equal the AL_net_addr in any Local Attached 4421 Network Tuple. 4423 o If N_orig_addr != unknown, then N_orig_addr MUST NOT equal the 4424 N_orig_addr in any other Neighbor Tuple. 4426 o N_neighbor_addr_list MUST NOT contain any network address which 4427 includes this router's originator address, the O_orig_addr in any 4428 Originator Tuple, or equal or have as a sub-range the AL_net_addr 4429 in any Local Attached Network Tuple. 4431 o If N_orig_addr = unknown, then N_willingness = WILL_NEVER, N_mpr = 4432 false, N_mpr_selector = false, and N_advertised = false. 4434 o N_in_metric MUST equal the minimum value of the L_in_metric values 4435 of all corrsponding Link Tuples, if any, otherwise N_in_metric = 4436 UNKNOWN_METRIC. 4438 o N_out_metric MUST equal the minimum value of the L_out_metric 4439 values of all corrsponding Link Tuples, if any, otherwise 4440 N_out_metric = UNKNOWN_METRIC. 4442 o N_will_flooding and N_will_routing MUST be in the range from 4443 WILL_NEVER to WILL_ALWAYS, inclusive. 4445 o If N_flooding_mpr = true, then N_symmetric MUST be true and 4446 N_will_flooding MUST NOT equal WILL_NEVER. 4448 o If N_routing_mpr = true, then N_symmetric MUST be true and 4449 N_will_routing MUST NOT equal WILL_NEVER. 4451 o If N_symmetric = true and N_mpr_flooding = false, then 4452 N_will_flooding MUST NOT equal WILL_ALWAYS. 4454 o If N_symmetric = true and N_mpr_routing = false, then 4455 N_will_routing MUST NOT equal WILL_ALWAYS. 4457 o If N_mpr_selector = true, then N_advertised MUST be true. 4459 o If N_advertised = true, then N_symmetric MUST be true. 4461 In each Lost Neighbor Tuple: 4463 o NL_neighbor_addr MUST NOT include this router's originator 4464 address, the O_orig_addr in any Originator Tuple, or equal or have 4465 as a sub-range the AL_net_addr in any Local Attached Network 4466 Tuple. 4468 In each 2-Hop Tuple: 4470 o N2_2hop_addr MUST NOT equal this router's originator address, 4471 equal the O_orig_addr in any Originator Tuple, or equal or have as 4472 a sub-range the AL_net_addr in any Local Attached Network Tuple 4474 o N2_in_metric and N2_out_metric MUST be representable in the 4475 defined compressed form. 4477 In each Advertising Remote Router Tuple: 4479 o AR_orig_addr MUST NOT be in any network address in the 4480 I_local_iface_addr_list in any Local Interface Tuple or be in the 4481 IR_local_iface_addr in any Removed Interface Address Tuple. 4483 o AR_orig_addr MUST NOT equal this router's originator address or 4484 equal the O_orig_addr in any Originator Tuple. 4486 o AR_orig_addr MUST NOT be in the AL_net_addr in any Local Attached 4487 Network Tuple. 4489 o AR_orig_addr MUST NOT equal the AR_orig_addr in any other 4490 Advertising Remote Router Tuple. 4492 In each Router Topology Tuple: 4494 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4495 = TR_from_orig_addr. 4497 o TR_to_orig_addr MUST NOT be in any network address in the 4498 I_local_iface_addr_list in any Local Interface Tuple or be in the 4499 IR_local_iface_addr in any Removed Interface Address Tuple. 4501 o TR_to_orig_addr MUST NOT equal this router's originator address or 4502 equal the O_orig_addr in any Originator Tuple. 4504 o TR_to_orig_addr MUST NOT be in the AL_net_addr in any Local 4505 Attached Network Tuple. 4507 o The ordered pair (TR_from_orig_addr, TR_to_orig_addr) MUST NOT 4508 equal the corresponding pair for any other Router Topology Tuple. 4510 o TR_seq_number MUST NOT be greater than AR_seq_number in the 4511 Advertising Remote Router Tuple with AR_orig_addr = 4512 TR_from_orig_addr. 4514 o TR_metric MUST be representable in the defined compressed form. 4516 In each Routable Address Topology Tuple: 4518 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4519 = TA_from_orig_addr. 4521 o TA_dest_addr MUST be routable. 4523 o TA_dest_addr MUST NOT overlap any network address in the 4524 I_local_iface_addr_list in any Local Interface Tuple or overlap 4525 the IR_local_iface_addr in any Removed Interface Address Tuple. 4527 o TA_dest_addr MUST NOT include this router's originator address or 4528 include the O_orig_addr in any Originator Tuple. 4530 o TA_dest_addr MUST NOT equal or have as a sub-range the AL_net_addr 4531 in any Local Attached Network Tuple. 4533 o The ordered pair (TA_from_orig_addr, TA_dest_addr) MUST NOT equal 4534 the corresponding pair for any other Attached Network Tuple. 4536 o TA_seq_number MUST NOT be greater than AR_seq_number in the 4537 Advertising Remote Router Tuple with AR_orig_addr = 4538 TA_from_orig_addr. 4540 o TA_metric MUST be representable in the defined compressed form. 4542 In each Attached Network Tuple: 4544 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4545 = AN_orig_addr. 4547 o AN_net_addr MUST NOT equal or be a sub-range of any network 4548 address in the I_local_iface_addr_list in any Local Interface 4549 Tuple or be a sub-range of the IR_local_iface_addr in any Removed 4550 Interface Address Tuple. 4552 o AN_net_addr MUST NOT equal this router's originator address or 4553 equal the O_orig_addr in any Originator Tuple. 4555 o AN_net_addr MUST NOT equal the AL_net_addr in any Local Attached 4556 Network Tuple. 4558 o The ordered pair (AN_orig_addr, AN_net_addr) MUST NOT equal the 4559 corresponding pair for any other Attached Network Tuple. 4561 o AN_seq_number MUST NOT be greater than AR_seq_number in the 4562 Advertising Remote Router Tuple with AR_orig_addr = AN_orig_addr. 4564 o AN_dist MUST NOT be less than zero. 4566 o AN_metric MUST be representable in the defined compressed form. 4568 Appendix E. Flow and Congestion Control 4570 Due to its proactive nature, this protocol has a natural control over 4571 the flow of its control traffic. Routers transmit control messages 4572 at predetermined rates specified and bounded by message intervals. 4574 This protocol employs [RFC6130] for local signaling, embedding MPR 4575 selection advertisement through a simple Address Block TLV, and 4576 router willingness advertisement (if any) as a single Message TLV. 4577 Local signaling, therefore, shares the characteristics and 4578 constraints of [RFC6130]. 4580 Furthermore, the use of MPRs can greatly reduce the signaling 4581 overhead from link state information dissemination in two ways, 4582 attaining both flooding reduction and topology reduction. First, 4583 using MPR flooding, the cost of distributing link state information 4584 throughout the network is reduced, as compared to when using classic 4585 flooding, since only MPRs need to forward link state declaration 4586 messages. Second, the amount of link state information for a router 4587 to declare is reduced to need only contain that router's MPR 4588 selectors. This reduces the size of a link state declaration as 4589 compared to declaring full link state information. In particular 4590 some routers may not need to declare any such information. In dense 4591 networks, the reduction of control traffic can be of several orders 4592 of magnitude compared to routing protocols using classical flooding 4593 [MPR]. This feature naturally provides more bandwidth for useful 4594 data traffic and pushes further the frontier of congestion. 4596 Since the control traffic is continuous and periodic, it keeps the 4597 quality of the links used in routing more stable. However, using 4598 some options, some control messages (HELLO messages or TC messages) 4599 may be intentionally sent in advance of their deadline in order to 4600 increase the responsiveness of the protocol to topology changes. 4601 This may cause a small, temporary, and local increase of control 4602 traffic, however this is at all times bounded by the use of minimum 4603 message intervals. 4605 Authors' Addresses 4607 Thomas Heide Clausen 4608 LIX, Ecole Polytechnique 4610 Phone: +33 6 6058 9349 4611 EMail: T.Clausen@computer.org 4612 URI: http://www.ThomasClausen.org/ 4613 Christopher Dearlove 4614 BAE Systems ATC 4616 Phone: +44 1245 242194 4617 EMail: chris.dearlove@baesystems.com 4618 URI: http://www.baesystems.com/ 4620 Philippe Jacquet 4621 Project Hipercom, INRIA 4623 Phone: +33 1 3963 5263 4624 EMail: philippe.jacquet@inria.fr