idnits 2.17.1 draft-ietf-manet-olsrv2-17.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 (October 14, 2012) is 4212 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) -- Obsolete informational reference (is this intentional?): RFC 6622 (Obsoleted by RFC 7182) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique 4 Intended status: Standards Track C. Dearlove 5 Expires: April 17, 2013 BAE Systems ATC 6 P. Jacquet 7 Alcatel-Lucent Bell Labs 8 U. Herberg 9 Fujitsu Laboratories of America 10 October 14, 2012 12 The Optimized Link State Routing Protocol version 2 13 draft-ietf-manet-olsrv2-17 15 Abstract 17 This specification describes version 2 of the Optimized Link State 18 Routing (OLSRv2) protocol for Mobile Ad hoc NETworks (MANETs). 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on April 17, 2013. 37 Copyright Notice 39 Copyright (c) 2012 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 This document may contain material from IETF Documents or IETF 53 Contributions published or made publicly available before November 54 10, 2008. The person(s) controlling the copyright in some of this 55 material may not have granted the IETF Trust the right to allow 56 modifications of such material outside the IETF Standards Process. 57 Without obtaining an adequate license from the person(s) controlling 58 the copyright in such materials, this document may not be modified 59 outside the IETF Standards Process, and derivative works of it may 60 not be created outside the IETF Standards Process, except to format 61 it for publication as an RFC or to translate it into languages other 62 than English. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 6 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 68 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 69 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 10 70 4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 10 71 4.2. Routers and Interfaces . . . . . . . . . . . . . . . . . 13 72 4.3. Information Base Overview . . . . . . . . . . . . . . . . 14 73 4.3.1. Local Information Base . . . . . . . . . . . . . . . 14 74 4.3.2. Interface Information Bases . . . . . . . . . . . . . 14 75 4.3.3. Neighbor Information Base . . . . . . . . . . . . . . 15 76 4.3.4. Topology Information Base . . . . . . . . . . . . . . 15 77 4.3.5. Received Message Information Base . . . . . . . . . . 16 78 4.4. Signaling Overview . . . . . . . . . . . . . . . . . . . 16 79 4.5. Link Metrics . . . . . . . . . . . . . . . . . . . . . . 18 80 4.6. Flooding MPRs and Routing MPR . . . . . . . . . . . . . . 19 81 4.7. Routing Set Use . . . . . . . . . . . . . . . . . . . . . 19 82 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 19 83 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 20 84 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 20 85 5.3. Interface Parameters . . . . . . . . . . . . . . . . . . 20 86 5.3.1. Received Message Validity Time . . . . . . . . . . . 20 87 5.4. Router Parameters . . . . . . . . . . . . . . . . . . . . 21 88 5.4.1. Local History Times . . . . . . . . . . . . . . . . . 21 89 5.4.2. Link Metric Parameters . . . . . . . . . . . . . . . 21 90 5.4.3. Message Intervals . . . . . . . . . . . . . . . . . . 21 91 5.4.4. Advertised Information Validity Times . . . . . . . . 22 92 5.4.5. Processing and Forwarding Validity Times . . . . . . 23 93 5.4.6. Jitter . . . . . . . . . . . . . . . . . . . . . . . 23 94 5.4.7. Hop Limit . . . . . . . . . . . . . . . . . . . . . . 24 95 5.4.8. Willingness . . . . . . . . . . . . . . . . . . . . . 24 96 5.5. Parameter Change Constraints . . . . . . . . . . . . . . 25 97 5.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 27 98 5.6.1. Link Metric Constants . . . . . . . . . . . . . . . . 27 99 5.6.2. Willingness Constants . . . . . . . . . . . . . . . . 27 100 5.6.3. Time Constant . . . . . . . . . . . . . . . . . . . . 28 101 6. Link Metric Values . . . . . . . . . . . . . . . . . . . . . 28 102 6.1. Link Metric Representation . . . . . . . . . . . . . . . 28 103 6.2. Link Metric Compressed Form . . . . . . . . . . . . . . . 29 104 7. Local Information Base . . . . . . . . . . . . . . . . . . . 29 105 7.1. Originator Set . . . . . . . . . . . . . . . . . . . . . 30 106 7.2. Local Attached Network Set . . . . . . . . . . . . . . . 30 107 8. Interface Information Base . . . . . . . . . . . . . . . . . 31 108 8.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . 31 109 8.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 32 110 9. Neighbor Information Base . . . . . . . . . . . . . . . . . . 32 111 10. Topology Information Base . . . . . . . . . . . . . . . . . . 34 112 10.1. Advertising Remote Router Set . . . . . . . . . . . . . . 34 113 10.2. Router Topology Set . . . . . . . . . . . . . . . . . . . 34 114 10.3. Routable Address Topology Set . . . . . . . . . . . . . . 35 115 10.4. Attached Network Set . . . . . . . . . . . . . . . . . . 36 116 10.5. Routing Set . . . . . . . . . . . . . . . . . . . . . . . 36 117 11. Received Message Information Base . . . . . . . . . . . . . . 37 118 11.1. Received Set . . . . . . . . . . . . . . . . . . . . . . 37 119 11.2. Processed Set . . . . . . . . . . . . . . . . . . . . . . 38 120 11.3. Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 38 121 12. Information Base Properties . . . . . . . . . . . . . . . . . 39 122 12.1. Corresponding Protocol Tuples . . . . . . . . . . . . . . 39 123 12.2. Address Ownership . . . . . . . . . . . . . . . . . . . . 40 124 13. Packets and Messages . . . . . . . . . . . . . . . . . . . . 40 125 13.1. Messages . . . . . . . . . . . . . . . . . . . . . . . . 41 126 13.2. Packets . . . . . . . . . . . . . . . . . . . . . . . . . 41 127 13.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . 42 128 13.3.1. Message TLVs . . . . . . . . . . . . . . . . . . . . 42 129 13.3.2. Address Block TLVs . . . . . . . . . . . . . . . . . 42 130 14. Message Processing and Forwarding . . . . . . . . . . . . . . 44 131 14.1. Actions when Receiving a Message . . . . . . . . . . . . 45 132 14.2. Message Considered for Processing . . . . . . . . . . . . 46 133 14.3. Message Considered for Forwarding . . . . . . . . . . . . 47 134 15. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . . 49 135 15.1. HELLO Message Generation . . . . . . . . . . . . . . . . 49 136 15.2. HELLO Message Transmission . . . . . . . . . . . . . . . 51 137 15.3. HELLO Message Processing . . . . . . . . . . . . . . . . 51 138 15.3.1. HELLO Message Discarding . . . . . . . . . . . . . . 51 139 15.3.2. HELLO Message Usage . . . . . . . . . . . . . . . . . 52 140 16. TC Messages . . . . . . . . . . . . . . . . . . . . . . . . . 55 141 16.1. TC Message Generation . . . . . . . . . . . . . . . . . . 55 142 16.2. TC Message Transmission . . . . . . . . . . . . . . . . . 57 143 16.3. TC Message Processing . . . . . . . . . . . . . . . . . . 58 144 16.3.1. TC Message Discarding . . . . . . . . . . . . . . . . 58 145 16.3.2. TC Message Processing Definitions . . . . . . . . . . 60 146 16.3.3. Initial TC Message Processing . . . . . . . . . . . . 61 147 16.3.4. Completing TC Message Processing . . . . . . . . . . 64 148 17. Information Base Changes . . . . . . . . . . . . . . . . . . 65 149 17.1. Originator Address Changes . . . . . . . . . . . . . . . 65 150 17.2. Link State Changes . . . . . . . . . . . . . . . . . . . 66 151 17.3. Neighbor State Changes . . . . . . . . . . . . . . . . . 66 152 17.4. Advertised Neighbor Changes . . . . . . . . . . . . . . . 67 153 17.5. Advertising Remote Router Tuple Expires . . . . . . . . . 67 154 17.6. Neighborhood Changes and MPR Updates . . . . . . . . . . 68 155 17.7. Routing Set Updates . . . . . . . . . . . . . . . . . . . 70 156 18. Selecting MPRs . . . . . . . . . . . . . . . . . . . . . . . 70 157 18.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 71 158 18.2. Neighbor Graph . . . . . . . . . . . . . . . . . . . . . 72 159 18.3. MPR Properties . . . . . . . . . . . . . . . . . . . . . 73 160 18.4. Flooding MPRs . . . . . . . . . . . . . . . . . . . . . . 73 161 18.5. Routing MPRs . . . . . . . . . . . . . . . . . . . . . . 75 162 18.6. Calculating MPRs . . . . . . . . . . . . . . . . . . . . 77 163 19. Routing Set Calculation . . . . . . . . . . . . . . . . . . . 77 164 19.1. Network Topology Graph . . . . . . . . . . . . . . . . . 77 165 19.2. Populating the Routing Set . . . . . . . . . . . . . . . 79 166 20. Proposed Values for Parameters . . . . . . . . . . . . . . . 80 167 20.1. Local History Time Parameters . . . . . . . . . . . . . . 81 168 20.2. Message Interval Parameters . . . . . . . . . . . . . . . 81 169 20.3. Advertised Information Validity Time Parameters . . . . . 81 170 20.4. Received Message Validity Time Parameters . . . . . . . . 81 171 20.5. Jitter Time Parameters . . . . . . . . . . . . . . . . . 81 172 20.6. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 81 173 20.7. Willingness Parameter . . . . . . . . . . . . . . . . . . 82 174 21. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . 82 175 22. Extensions . . . . . . . . . . . . . . . . . . . . . . . . . 82 176 23. Security Considerations . . . . . . . . . . . . . . . . . . . 83 177 23.1. Security Architecture . . . . . . . . . . . . . . . . . . 83 178 23.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 84 179 23.3. Confidentiality . . . . . . . . . . . . . . . . . . . . . 86 180 23.4. Interaction with External Routing Domains . . . . . . . . 86 181 24. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 87 182 24.1. Expert Review: Evaluation Guidelines . . . . . . . . . . 87 183 24.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 87 184 24.3. Message-Type-Specific TLV Type Registries . . . . . . . . 87 185 24.4. Message TLV Types . . . . . . . . . . . . . . . . . . . . 88 186 24.5. Address Block TLV Types . . . . . . . . . . . . . . . . . 89 187 24.6. NBR_ADDR_TYPE and MPR Values . . . . . . . . . . . . . . 92 188 25. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 92 189 26. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 93 190 27. References . . . . . . . . . . . . . . . . . . . . . . . . . 93 191 27.1. Normative References . . . . . . . . . . . . . . . . . . 93 192 27.2. Informative References . . . . . . . . . . . . . . . . . 94 194 Appendix A. Constraints . . . . . . . . . . . . . . . . . . . . 95 195 Appendix B. Example Algorithm for Calculating MPRs . . . . . . . 99 196 B.1. Additional Notation . . . . . . . . . . . . . . . . . . . 99 197 B.2. MPR Selection Algorithm . . . . . . . . . . . . . . . . . 100 198 Appendix C. Example Algorithm for Calculating the Routing Set . 100 199 C.1. Local Interfaces and Neighbors . . . . . . . . . . . . . 100 200 C.2. Add Neighbor Routers . . . . . . . . . . . . . . . . . . 102 201 C.3. Add Remote Routers . . . . . . . . . . . . . . . . . . . 102 202 C.4. Add Neighbor Addresses . . . . . . . . . . . . . . . . . 103 203 C.5. Add Remote Routable Addresses . . . . . . . . . . . . . . 104 204 C.6. Add Attached Networks . . . . . . . . . . . . . . . . . . 104 205 C.7. Add 2-Hop Neighbors . . . . . . . . . . . . . . . . . . . 105 206 Appendix D. TC Message Example . . . . . . . . . . . . . . . . . 106 207 Appendix E. Flow and Congestion Control . . . . . . . . . . . . 108 209 1. Introduction 211 The Optimized Link State Routing protocol version 2 (OLSRv2) is the 212 successor to OLSR (version 1) as published in [RFC3626]. Compared to 213 [RFC3626], OLSRv2 retains the same basic mechanisms and algorithms, 214 enhanced by the ability to use a link metric other than hop count in 215 the selection of shortest routes. OLSRv2 also uses a more flexible 216 and efficient signaling framework, and includes some simplification 217 of the messages being exchanged. 219 OLSRv2 is developed for mobile ad hoc networks (MANETs). It operates 220 as a table driven, proactive protocol, i.e., it exchanges topology 221 information with other routers in the network regularly. OLSRv2 is 222 an optimization of the classic link state routing protocol. Its key 223 concept is that of MultiPoint Relays (MPRs). Each router selects two 224 sets of MPRs, each being a set of its neighbor routers that "cover" 225 all of its symmetrically connected 2-hop neighbor routers. These two 226 sets are of "flooding MPRs" and "routing MPRs", and are used to 227 achieve flooding reduction and topology reduction, respectively. 229 Flooding reduction is achieved by control traffic being flooded 230 through the network using hop by hop forwarding, but with a router 231 only needing to forward control traffic that is first received 232 directly from one of the routers that have selected it as a flooding 233 MPR (its "flooding MPR selectors"). This mechanism, denoted "MPR 234 flooding", provides an efficient mechanism for information 235 distribution within the MANET by reducing the number of transmissions 236 required [MPR]. 238 Topology reduction is achieved by assigning a special responsibility 239 to routers selected as routing MPRs when declaring link state 240 information. A sufficient requirement for OLSRv2 to provide shortest 241 routes to all destinations is that routers declare link state 242 information for their routing MPR selectors, if any. Routers that 243 are not selected as routing MPRs need not send any link state 244 information. Based on this reduced link state information, routing 245 MPRs are used as intermediate routers in multi-hop routes. 247 Thus the use of MPRs allows reduction of the number and the size of 248 link state messages, and in the amount of link state information 249 maintained in each router. When possible (in particular if using a 250 hop count metric) the same routers may be picked as both flooding 251 MPRs and routing MPRs. 253 A router selects both routing and flooding MPRs from among its one 254 hop neighbors connected by "symmetric", i.e., bidirectional, links. 255 Therefore, selecting routes through routing MPRs avoids the problems 256 associated with data packet transfer over unidirectional links (e.g., 257 the problem of not getting link layer acknowledgments at each hop, 258 for link layers employing this technique). 260 OLSRv2 uses and extends the MANET NeighborHood Discovery Protocol 261 (NHDP) defined in [RFC6130] and also uses the Generalized MANET 262 Packet/Message Format [RFC5444], the TLVs specified in [RFC5497] and, 263 optionally, message jitter as specified in [RFC5148]. These four 264 other protocols and specifications were all originally created as 265 part of OLSRv2, but have been specified separately for wider use. 267 OLSRv2 makes no assumptions about the underlying link layer. OLSRv2, 268 through its use of [RFC6130], may use link layer information and 269 notifications when available and applicable. In addition, OLSRv2 270 uses link metrics that may be derived from link layer or any other 271 information. OLSRv2 does not specify the physical meaning of link 272 metrics, but specifies a means by which new types of link metrics may 273 be specified in the future, but used by OLSRv2 without modification. 275 OLSRv2, as OLSR [RFC3626], inherits its concept of forwarding and 276 relaying from HIPERLAN (a MAC layer protocol) which is standardized 277 by ETSI [HIPERLAN], [HIPERLAN2]. This document does not obsolete 278 [RFC3626] which is left in place for further experimentation. 280 2. Terminology 282 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 283 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 284 "OPTIONAL" in this document are to be interpreted as described in 285 [RFC2119]. 287 All terms introduced in [RFC5444], including "packet", "Packet 288 Header", "message", "Message Header", "Message Body", "Message Type", 289 "message sequence number", "hop limit", "hop count", "Address Block", 290 "TLV Block", "TLV", "Message TLV", "Address Block TLV", "type" (of 291 TLV), "type extension" (of TLV), "value" (of TLV), "address", 292 "address prefix", and "address object" are to be interpreted as 293 described there. 295 All terms introduced in [RFC6130], including "interface", "MANET 296 interface", "network address", "link", "symmetric link", "symmetric 297 1-hop neighbor", "symmetric 2-hop neighbor", "symmetric 1-hop 298 neighborhood" "constant", "interface parameter", "router parameter", 299 "Information Base", and "HELLO message" are to be interpreted as 300 described there. 302 Additionally, this specification uses the following terminology: 304 Router: 305 A MANET router which implements this protocol. 307 OLSRv2 interface: 308 A MANET interface running this protocol. A router running this 309 protocol MUST have at least one OLSRv2 interface. 311 Routable address: 312 A network address which may be used as the destination of a data 313 packet. A router which implements this protocol will need to 314 distinguish a routable address from a non-routable address by 315 direct inspection of the network address, based on global scope 316 address allocations by IANA and/or administrative configuration 317 (consistently across the MANET). Broadcast and multicast 318 addresses, and addresses which are limited in scope to less than 319 the entire MANET, MUST NOT be considered as routable addresses. 320 Anycast addresses may be considered as routable addresses. 322 Originator address: 323 An address which is unique (within the MANET) to a router. A 324 router MUST select an originator address; it MAY choose one of its 325 interface addresses as its originator address; it MAY select 326 either a routable or non-routable address. A broadcast, multicast 327 or anycast address MUST NOT be chosen as an originator address. 328 If the router selects a routable address then this MUST be one 329 which the router will accept as destination. An originator 330 address MUST NOT have a prefix length, except for when included in 331 an Address Block where it MAY be associated with a prefix of 332 maximum prefix length (e.g., if the originator address is an IPv6 333 address, it MUST have either no prefix length, or have a prefix 334 length of 128). 336 Message originator address: 337 The originator address of the router which created a message, as 338 deduced from that message by its recipient. For all messages used 339 in this specification, including HELLO messages defined in 340 [RFC6130], the recipient MUST be able to deduce an originator 341 address. The message originator address will usually be included 342 in the message as its element as defined in 343 [RFC5444]. However, an exceptional case, which does not add a 344 element to a HELLO message, may be used by a 345 router that only has a single address. 347 Willingness: 348 A numerical value between WILL_NEVER and WILL_ALWAYS (both 349 inclusive), that represents the router's willingness to be 350 selected as an MPR. A router has separate willingness values to 351 be a flooding MPR and a routing MPR. 353 Willing symmetric 1-hop neighbor: 354 A symmetric 1-hop neighbor that has willingness not equal to 355 WILL_NEVER. 357 Multipoint relay (MPR): 358 A router, X, is an MPR for a router, Y, if router Y has indicated 359 its selection of router X as an MPR in a recent HELLO message. 360 Router X may be a flooding MPR for Y if it is indicated to 361 participate in the flooding process of messages received from 362 router Y, or it may be a routing MPR for Y, if it is indicated to 363 declare link-state information for the link from X to Y. It may 364 also be both at the same time. 366 MPR selector: 367 A router, Y, is a flooding/routing MPR selector of router X if 368 router Y has selected router X as a flooding/routing MPR. 370 MPR flooding: 371 The optimized MANET-wide information distribution mechanism, 372 employed by this protocol, in which a message is relayed by only a 373 reduced subset of the routers in the network. MPR flooding is the 374 mechanism by which flooding reduction is achieved. 376 EXPIRED: 377 Indicates that a timer is set to a value clearly preceding the 378 current time (e.g., current time - 1). 380 This specification employs the same notational conventions as in 381 [RFC5444] and [RFC6130]. 383 3. Applicability Statement 385 This document specifies OLSRv2, a proactive routing protocol intended 386 for use in mobile ad hoc networks (MANETs) [RFC2501]. The protocol's 387 applicability is determined by its characteristics, which are that 388 this protocol: 390 o Is designed to work in networks with a dynamic topology, and in 391 which messages may be lost, such as due to collisions over 392 wireless media. 394 o Supports routers that each have one or more participating OLSRv2 395 interfaces, which will consist of some or all of its MANET 396 interfaces using [RFC6130]. The set of a router's OLSRv2 397 interfaces, and the sets of its other MANET and non-MANET 398 interfaces, may change over time. Each interface may have one or 399 more network addresses (which may have prefix lengths), and these 400 may also be dynamically changing. 402 o Enables hop-by-hop routing, i.e., each router can use its local 403 information provided by this protocol to route packets. 405 o Continuously maintains routes to all destinations in the network, 406 i.e., routes are instantly available and data traffic is subject 407 to no delays due to route discovery. Consequently, no data 408 traffic buffering is required. 410 o Supports routers that have non-OLSRv2 interfaces that may be local 411 to a router or that can serve as gateways towards other networks. 413 o Enables the use of bidirectional additive link metrics to use 414 shortest distance routes (i.e., routes with smallest total of link 415 metrics). Incoming link metric values are to be determined by a 416 process outside this specification. 418 o Is optimized for large and dense networks; the larger and more 419 dense a network, the more optimization can be achieved by using 420 MPRs, compared to the classic link state algorithm [MPR]. 422 o Uses [RFC5444] as described in its "Intended Usage" appendix and 423 by [RFC5498]. 425 o Allows "external" and "internal" extensibility (adding new message 426 types and adding information to existing messages) as enabled by 427 [RFC5444]. 429 o Is designed to work in a completely distributed manner, and does 430 not depend on any central entity. 432 4. Protocol Overview and Functioning 434 The objectives of this protocol are for each router to: 436 o Identify all destinations in the network. 438 o Identify a sufficient subset of links in the network, in order 439 that shortest routes can be calculated to all available 440 destinations. 442 o Provide a Routing Set, containing these shortest routes from this 443 router to all destinations (routable addresses and local links). 445 4.1. Overview 447 These objectives are achieved, for each router, by: 449 o Using [RFC6130] to identify symmetric 1-hop neighbors and 450 symmetric 2-hop neighbors. 452 o Reporting its participation in OLSRv2, and its willingness to be a 453 flooding MPR and to be a routing MPR, by extending the HELLO 454 messages defined in [RFC6130], by the addition of an MPR_WILLING 455 Message TLV. The router's "flooding willingness" indicates how 456 willing it is to participate in MPR flooding. The router's 457 "routing willingness" indicates how willing it is to be an 458 intermediate router for routing. Note that a router is still able 459 to be a routing source or destination, even if unwilling to 460 perform either function. 462 o Extending the HELLO messages defined in [RFC6130] to allow the 463 addition of directional link metrics to advertised links with 464 other routers participating in OLSRv2, and to indicate which link 465 metric type is being used by those routers. Both incoming and 466 outgoing link metrics may be reported, the former determined by 467 the advertising router. 469 o Selecting flooding MPRs and routing MPRs from among its willing 470 symmetric 1-hop neighbors such that, for each set of MPRs, all 471 symmetric 2-hop neighbors are reachable either directly or via at 472 least one selected MPR, using a path of appropriate minimum total 473 metric for at least routing MPR selection. An analysis and 474 examples of MPR selection algorithms are given in [MPR]; a 475 suggested algorithm, appropriately adapted for each set of MPRs, 476 is included in Appendix B of this specification. Note that it is 477 not necessary for routers to use the same algorithm in order to 478 interoperate in the same MANET, but each such algorithm must have 479 the appropriate properties, described in Section 18. 481 o Signaling its flooding MPR and routing MPR selections, by 482 extending the HELLO messages defined in [RFC6130] to report this 483 information by the addition of MPR Address Block TLV(s) associated 484 with the appropriate network addresses. 486 o Extracting its flooding MPR selectors and routing MPR selectors 487 from received HELLO messages, using the included MPR Address Block 488 TLV(s). 490 o Defining a TC (Topology Control) Message Type using the message 491 format specified in [RFC5444]. TC messages are used to 492 periodically signal links between routing MPR selectors and itself 493 throughout the MANET. This signaling includes suitable 494 directional neighbor metrics (the best link metric in that 495 direction between those routers). 497 o Allowing its TC messages, as well as HELLO messages, to be 498 included in packets specified in [RFC5444], using the "manet" IP 499 protocol or UDP port as specified in [RFC5498]. 501 o Diffusing TC messages by using a flooding reduction mechanism, 502 denoted "MPR flooding"; only the flooding MPRs of a router will 503 retransmit messages received from (i.e., originated or last 504 relayed by) that router. 506 Note that the indicated extensions to [RFC6130] are of forms 507 permitted by that specification. 509 This specification defines: 511 o The requirement to use [RFC6130], its parameters, constants, HELLO 512 messages, and Information Bases, each as extended in this 513 specification. 515 o Two new Information Bases: the Topology Information Base and the 516 Received Message Information Base. 518 o TC messages, which are used for MANET wide signaling (using MPR 519 flooding) of selected topology (link state) information. 521 o A requirement for each router to have an originator address to be 522 included in, or deducible from, HELLO messages and TC messages. 524 o The specification of new Message TLVs and Address Block TLVs that 525 are used in HELLO messages and TC messages, including for 526 reporting neighbor status, MPR selection, external gateways, link 527 metrics, willingness to be an MPR, and content sequence numbers. 528 Note that the generation of (incoming) link metric values is to be 529 undertaken by a process outside this specification; this 530 specification concerns only the distribution and use of those 531 metrics. 533 o The generation of TC messages from the appropriate information in 534 the Information Bases. 536 o The updating of the Topology Information Base according to 537 received TC messages. 539 o The MPR flooding mechanism, including the inclusion of message 540 originator address and sequence number to manage duplicate 541 messages, using information recorded in the Received Message 542 Information Base. 544 o The response to other events, such as the expiration of 545 information in the Information Bases. 547 This protocol inherits the stability of a link state algorithm, and 548 has the advantage of having routes immediately available when needed, 549 due to its proactive nature. 551 This protocol only interacts with IP through routing table 552 management, and the use of the sending IP address for IP datagrams 553 containing messages used by this specification. 555 4.2. Routers and Interfaces 557 In order for a router to participate in a MANET using this protocol 558 it must have at least one, and possibly more, OLSRv2 interfaces. 559 Each OLSRv2 interface: 561 o Is a MANET interface, as specified in [RFC6130]. In particular it 562 must be configured with one or more network addresses; these 563 addresses must each be specific to this router, and must include 564 any address that will be used as the sending address of any IP 565 packet sent on this OLSRv2 interface. 567 o Has a number of interface parameters, adding to those specified in 568 [RFC6130]. 570 o Has an Interface Information Base, extending that specified in 571 [RFC6130]. 573 o Generates and processes HELLO messages according to [RFC6130], 574 extended as specified in Section 15. 576 In addition to a set of OLSRv2 interfaces as described above, each 577 router: 579 o May have one or more non-OLSRv2 interfaces (which may include 580 MANET interfaces and/or non-MANET interfaces) and/or local 581 attached networks for which this router can accept IP packets. 582 All routable addresses for which the router is to accept IP 583 packets must be used as an (OLSRv2 or non-OLSRv2) interface 584 network address, or as an address of a local attached network of 585 the router. 587 o Has a number of router parameters, adding to those specified in 588 [RFC6130]. 590 o Has a Local Information Base, extending that specified in 591 [RFC6130], including selection of an originator address and 592 recording any locally attached networks. 594 o Has a Neighbor Information Base, extending that specified in 595 [RFC6130] to record MPR selection and advertisement information. 597 o Has a Topology Information Base, recording information received in 598 TC messages. 600 o Has a Received Message Information Base, recording information 601 about received messages to ensure that each TC message is only 602 processed once, and forwarded at most once on each OLSRv2 603 interface, by a router. 605 o Generates, receives, and processes TC messages. 607 4.3. Information Base Overview 609 Each router maintains the Information Bases described in the 610 following sections. These are used for describing the protocol in 611 this specification. An implementation of this protocol may maintain 612 this information in the indicated form, or in any other organization 613 which offers access to this information. In particular, note that it 614 is not necessary to remove Tuples from Sets at the exact time 615 indicated, only to behave as if the Tuples were removed at that time. 617 4.3.1. Local Information Base 619 The Local Information Base is specified in [RFC6130], and contains a 620 router's local configuration. It is extended in this specification 621 to also record an originator address, and to include a router's: 623 o Originator Set, containing addresses that were recently used as 624 this router's originator address, and is used, together with the 625 router's current originator address, to enable a router to 626 recognize and discard control traffic which was originated by the 627 router itself. 629 o Local Attached Network Set, containing network addresses of 630 networks to which this router can act as a gateway, and advertises 631 in its TC messages. 633 4.3.2. Interface Information Bases 635 The Interface Information Base for each OLSRv2 interface is as 636 specified in [RFC6130], extended to also record, in each Link Set, 637 link metric values (incoming and outgoing) and flooding MPR selector 638 information. 640 4.3.3. Neighbor Information Base 642 The Neighbor Information Base is specified in [RFC6130], and is 643 extended to also record, in the Neighbor Tuple for each neighbor: 645 o Its originator address. 647 o Neighbor metric values, these being the minimum of the link metric 648 values in the indicated direction for all symmetric 1-hop links 649 with that neighbor. 651 o Its willingness to be a flooding MPR and to be a routing MPR. 653 o Whether it has been selected by this router as a flooding MPR or 654 as a routing MPR, and whether it is a routing MPR selector of this 655 router. (Whether it is a flooding MPR selector of this neighbor 656 is recorded in the Interface Information Base.) 658 o Whether it is to be advertised in TC messages sent by this router. 660 4.3.4. Topology Information Base 662 The Topology Information Base in each router contains: 664 o An Advertising Remote Router Set, recording each remote router 665 from which TC messages have been received. This is used in order 666 to determine if a received TC message contains fresh or outdated 667 information; a received TC message is ignored in the latter case. 669 o A Router Topology Set, recording links between routers in the 670 MANET, as described by received TC messages. 672 o A Routable Address Topology Set, recording routable addresses in 673 the MANET (available as IP packet destinations) and from which 674 remote router these routable addresses can be directly reached 675 (i.e., in a single IP hop from that remote router), as reported by 676 received TC messages. 678 o An Attached Network Set, recording networks to which a remote 679 router has advertised that it may act as a gateway. These 680 networks may be reached in one or more IP hops from that remote 681 router. 683 o A Routing Set, recording routes from this router to all available 684 destinations. The IP routing table is to be updated using this 685 Routing Set. (A router may choose to use any or all destination 686 network addresses in the Routing Set to update the IP routing 687 table, this selection is outside the scope of this specification.) 689 The purpose of the Topology Information Base is to record information 690 used, in addition to that in the Local Information Base, the 691 Interface Information Bases and the Neighbor Information Base, to 692 construct the Routing Set (which is also included in the Topology 693 Information Base). 695 This specification describes the calculation of the Routing Set based 696 on a Topology Graph constructed in two phases. First, a "backbone" 697 graph representing the routers in the MANET, and the connectivity 698 between them, is constructed from the Local Information Base, the 699 Neighbor Information Base and the Router Topology Set. Second, this 700 graph is "decorated" with additional destination network addresses 701 using the Local Information Base, the Routable Address Topology Set 702 and the Attached Network Set. 704 The Topology Graph does not need to be recorded in the Topology 705 Information Base, it can either be constructed as required when the 706 Routing Set is to be changed, or need not be explicitly constructed 707 (as illustrated in Appendix C). An implementation may however 708 construct and retain the Topology Graph if preferred. 710 4.3.5. Received Message Information Base 712 The Received Message Information Base in each router contains: 714 o A Received Set for each OLSRv2 interface, describing TC messages 715 received by this router on that OLSRv2 interface. 717 o A Processed Set, describing TC messages processed by this router. 719 o A Forwarded Set, describing TC messages forwarded by this router. 721 The Received Message Information Base serves the MPR flooding 722 mechanism by ensuring that received messages are forwarded at most 723 once by a router, and also ensures that received messages are 724 processed exactly once by a router. The Received Message Information 725 Base may also record information about other Message Types that use 726 the MPR flooding mechanism. 728 4.4. Signaling Overview 730 This protocol generates and processes HELLO messages according to 731 [RFC6130]. HELLO messages transmitted on OLSRv2 interfaces are 732 extended according to Section 15 of this specification to include an 733 originator address, link metrics, and MPR selection information. 735 This specification defines a single Message Type, the TC message. TC 736 messages are sent by their originating router proactively, at a 737 regular interval, on all OLSRv2 interfaces. This interval may be 738 fixed, or may be dynamic, for example it may be backed off due to 739 congestion or network stability. TC messages may also be sent as a 740 response to a change in the router itself, or its advertised 741 symmetric 1-hop neighborhood, for example on first being selected as 742 a routing MPR. 744 Because TC messages are sent periodically, this protocol is tolerant 745 of unreliable transmissions of TC messages. Message losses may occur 746 more frequently in wireless networks due to collisions or other 747 transmission problems. This protocol may use "jitter", randomized 748 adjustments to message transmission times, to reduce the incidence of 749 collisions, as specified in [RFC5148]. 751 This protocol is tolerant of out of sequence delivery of TC messages 752 due to in transit message reordering. Each router maintains an 753 Advertised Neighbor Sequence Number (ANSN) that is incremented when 754 its recorded neighbor information that is to be included in its TC 755 messages changes. This ANSN is included in the router's TC messages. 756 The recipient of a TC message can use this included ANSN to identify 757 which of the information it has received is most recent, even if 758 messages have been reordered while in transit. Only the most recent 759 information received is used, older information received later is 760 discarded. 762 TC messages may be "complete" or "incomplete". A complete TC message 763 advertises all of the originating router's routing MPR selectors, it 764 may also advertise other symmetric 1-hop neighbors. Complete TC 765 messages are generated periodically (and also, optionally, in 766 response to symmetric 1-hop neighborhood changes). Incomplete TC 767 messages may be used to report additions to advertised information, 768 without repeating unchanged information. 770 TC messages, and HELLO messages as extended by this specification, 771 define (by inclusion, or by deduction when having a single address) 772 an originator address for the router that created the message. A TC 773 message reports both the originator addresses and routable addresses 774 of its advertised neighbors, distinguishing the two using an Address 775 Block TLV (an address may be both routable and an originator 776 address). TC messages also report the originator's locally attached 777 networks. 779 TC messages are MPR flooded throughout the MANET. A router 780 retransmits a TC message received on an OLSRv2 interface if and only 781 if the message did not originate at this router and has not been 782 previously forwarded by this router, this is the first time the 783 message has been received on this OLSRv2 interface, and the message 784 is received from (i.e., originated from or was last relayed by) one 785 of this router's flooding MPR selectors. 787 Some TC messages may be MPR flooded over only part of the network, 788 e.g., allowing a router to ensure that nearer routers are kept more 789 up to date than distant routers, such as is used in Fisheye State 790 Routing [FSR] and Fuzzy Sighted Link State routing [FSLS]. This is 791 enabled using [RFC5497]. 793 TC messages include outgoing neighbor metrics that will be used in 794 the selection of routes. 796 4.5. Link Metrics 798 OLSRv1 [RFC3626] created minimum hop routes to destinations. However 799 in many, if not most, circumstances, better routes (in terms of 800 quality of service for end users) can be created by use of link 801 metrics. 803 OLSRv2, as defined in this specification, supports metric-based 804 routing, i.e., it allows links to each have a chosen metric. Link 805 metrics as defined in OLSRv2 are additive, and the routes that are to 806 be created are those with the minimum sum of the link metrics along 807 that route. 809 Link metrics are defined to be directional; the link metric from one 810 router to another may be different from that on the reverse link. 811 The link metric is assessed at the receiver, as on a (typically) 812 wireless link, that is the better informed as to link information. 813 Both incoming and outgoing link information is used by OLSRv2, the 814 distinctions in this specification must be clearly followed. 816 This specification also defines both incoming and outgoing neighbor 817 metrics for each symmetric 1-hop neighbor, these being the minimum 818 value of the link metrics in the same direction for all symmetric 819 links with that neighbor. Note that this means that all neighbor 820 metric values are link metric values and that specification of, for 821 example, link metric value encoding also includes encoding of 822 neighbor metric values. 824 This specification does not define the nature of the link metric. 825 However, this specification allows, through use of the type extension 826 of a defined Address Block TLV, for link metrics with specific 827 meanings to be defined and either allocated by IANA or privately 828 used. Each HELLO or TC message carrying link (or neighbor) metrics 829 thus indicates which link metric information it is carrying, allowing 830 routers to determine if they can interoperate. If link metrics 831 require additional signaling to determine their values, whether in 832 HELLO messages or otherwise, then this is permitted but is outside 833 the scope of this specification. 835 Careful consideration should be given to how to use link metrics. In 836 particular it is advisable to not simply default to use of all links 837 with equal metrics (i.e., hop count) for routing without careful 838 consideration of whether that is appropriate or not. 840 4.6. Flooding MPRs and Routing MPR 842 This specification uses two sets of MPRs: flooding MPRs and routing 843 MPRs. These are selected separately, because: 845 o Flooding MPRs may use metrics, routing MPRs must use metrics. 847 o When flooding MPRs use metrics, these are outgoing link metrics, 848 routing MPRs use incoming neighbor metrics. 850 o Flooding MPRs need not be selected per OLSRv2 interface, routing 851 MPRs must be selected per OLSRv2 interface. 853 4.7. Routing Set Use 855 The purpose of the Routing Set is to determine and record routes 856 (local interface network address and next hop interface network 857 address) to all possible routable addresses advertised by this 858 protocol, as well as of all destinations that are local, i.e., within 859 one hop, to the router (whether using routable addresses or not). 860 Only symmetric links are used in such routes. 862 It is intended that the Routing Set can be used for IP packet 863 routing, by using its contents to update the IP routing table. That 864 update, and whether any Routing Tuples are not used in the IP routing 865 table, is outside the scope of this specification. 867 The signaling in this specification has been designed so that a 868 "backbone" Topology Graph of routers, each identified by its 869 originator address, with at most one direct connection between any 870 pair of routers, can be constructed (from the Neighbor Set and the 871 Router Topology Set) using a suitable minimum path length algorithm. 872 This Topology Graph can then have other network addresses (routable, 873 or of symmetric 1-hop neighbors) added to it (using the Interface 874 Information Bases, the Routable Address Topology Set and the Attached 875 Network Set). 877 5. Protocol Parameters and Constants 879 The parameters and constants used in this specification are those 880 defined in [RFC6130] plus those defined in this section. The 881 separation in [RFC6130] into interface parameters, router parameters 882 and constants is also used in this specification. 884 As for the parameters in [RFC6130], parameters defined in this 885 specification MAY be changed dynamically by a router, and need not be 886 the same on different routers, even in the same MANET, or, for 887 interface parameters, on different interfaces of the same router. 889 5.1. Protocol and Port Numbers 891 This protocol specifies TC messages, which are included in packets as 892 defined by [RFC5444]. These packets MUST be sent either using the 893 "manet" protocol number or the "manet" UDP well-known port number, as 894 specified in [RFC5498]. 896 TC messages and HELLO messages [RFC6130] MUST, in a given MANET, 897 either both be using IP or both be using UDP, in order that it is 898 possible to combine messages of both protocols into the same 899 [RFC5444] packet for transmission. 901 5.2. Multicast Address 903 This protocol specifies TC messages, which are included in packets as 904 defined by [RFC5444]. These packets MAY be transmitted using the 905 Link-Local multicast address "LL-MANET-Routers", as specified in 906 [RFC5498]. 908 5.3. Interface Parameters 910 A single additional interface parameter is specified for OLSRv2 911 interfaces only. 913 5.3.1. Received Message Validity Time 915 The following parameter manages the validity time of recorded 916 received message information: 918 RX_HOLD_TIME: 919 The period after receipt of a message by the appropriate OLSRv2 920 interface of this router for which that information is recorded, 921 in order that the message is recognized as having been previously 922 received on this OLSRv2 interface. 924 The following constraints apply to this parameter: 926 o RX_HOLD_TIME > 0 927 o RX_HOLD_TIME SHOULD be greater than the maximum difference in time 928 that a message may take to traverse the MANET, taking into account 929 any message forwarding jitter as well as propagation, queuing, and 930 processing delays. 932 5.4. Router Parameters 934 The following router parameters are specified for routers. 936 5.4.1. Local History Times 938 The following router parameter manages the time for which local 939 information is retained: 941 O_HOLD_TIME: 942 The time for which a recently used and replaced originator address 943 is used to recognize the router's own messages. 945 The following constraint applies to this parameter: 947 o O_HOLD_TIME > 0 949 5.4.2. Link Metric Parameters 951 All routes found using this specification use a single link metric 952 type that is specified by the router parameter LINK_METRIC_TYPE, 953 which may take any value from 0 to 255, both inclusive. 955 5.4.3. Message Intervals 957 The following parameters regulate TC message transmissions by a 958 router. TC messages are usually sent periodically, but MAY also be 959 sent in response to changes in the router's Neighbor Set and/or Local 960 Attached Network Set. In a highly dynamic network, and with a larger 961 value of the parameter TC_INTERVAL and a smaller value of the 962 parameter TC_MIN_INTERVAL, TC messages MAY be transmitted more often 963 in response to changes than periodically. However, because a router 964 has no knowledge of, for example, routers remote to it (i.e., beyond 965 two hops away) joining the network, TC messages MUST NOT be sent 966 purely responsively. 968 TC_INTERVAL: 969 The maximum time between the transmission of two successive TC 970 messages by this router. When no TC messages are sent in response 971 to local network changes (by design, or because the local network 972 is not changing) then TC messages MUST be sent at a regular 973 interval TC_INTERVAL, possibly modified by jitter as specified in 974 [RFC5148]. 976 TC_MIN_INTERVAL: 977 The minimum interval between transmission of two successive TC 978 messages by this router. (This minimum interval MAY be modified 979 by jitter, as specified in [RFC5148].) 981 The following constraints apply to these parameters: 983 o TC_INTERVAL > 0 985 o 0 <= TC_MIN_INTERVAL <= TC_INTERVAL 987 o If TLVs with Type = INTERVAL_TIME, as defined in [RFC5497], are 988 included in TC messages, then TC_INTERVAL MUST be representable by 989 way of the exponent-mantissa notation described in Section 5 of 990 [RFC5497]. 992 5.4.4. Advertised Information Validity Times 994 The following parameters manage the validity time of information 995 advertised in TC messages: 997 T_HOLD_TIME: 998 Used as the minimum value in the TLV with Type = VALIDITY_TIME 999 included in all TC messages sent by this router. If a single 1000 value of parameter TC_HOP_LIMIT (see Section 5.4.7) is used then 1001 this will be the only value in that TLV. 1003 A_HOLD_TIME: 1004 The period during which TC messages are sent after they no longer 1005 have any advertised information to report, but are sent in order 1006 to accelerate outdated information removal by other routers. 1008 The following constraints apply to these parameters: 1010 o T_HOLD_TIME > 0 1012 o A_HOLD_TIME >= 0 1014 o T_HOLD_TIME >= TC_INTERVAL 1016 o If TC messages can be lost, then both T_HOLD_TIME and A_HOLD_TIME 1017 SHOULD be significantly greater than TC_INTERVAL; a value >= 3 x 1018 TC_INTERVAL is RECOMMENDED. 1020 o T_HOLD_TIME MUST be representable by way of the exponent-mantissa 1021 notation described in Section 5 of [RFC5497]. 1023 5.4.5. Processing and Forwarding Validity Times 1025 The following parameters manage the processing and forwarding 1026 validity time of recorded message information: 1028 P_HOLD_TIME: 1029 The period after receipt of a message that is processed by this 1030 router for which that information is recorded, in order that the 1031 message is not processed again if received again. 1033 F_HOLD_TIME: 1034 The period after receipt of a message that is forwarded by this 1035 router for which that information is recorded, in order that the 1036 message is not forwarded again if received again. 1038 The following constraints apply to these parameters: 1040 o P_HOLD_TIME > 0 1042 o F_HOLD_TIME > 0 1044 o Both of these parameters SHOULD be greater than the maximum 1045 difference in time that a message may take to traverse the MANET, 1046 taking into account any message forwarding jitter as well as 1047 propagation, queuing, and processing delays. 1049 5.4.6. Jitter 1051 If jitter, as defined in [RFC5148], is used then the governing jitter 1052 parameters are as follows: 1054 TP_MAXJITTER: 1055 Represents the value of MAXJITTER used in [RFC5148] for 1056 periodically generated TC messages sent by this router. 1058 TT_MAXJITTER: 1059 Represents the value of MAXJITTER used in [RFC5148] for externally 1060 triggered TC messages sent by this router. 1062 F_MAXJITTER: 1063 Represents the default value of MAXJITTER used in [RFC5148] for 1064 messages forwarded by this router. However, before using 1065 F_MAXJITTER a router MAY attempt to deduce a more appropriate 1066 value of MAXJITTER, for example based on any TLVs with Type = 1067 INTERVAL_TIME or Type = VALIDITY_TIME contained in the message to 1068 be forwarded. 1070 For constraints on these parameters see [RFC5148]. 1072 5.4.7. Hop Limit 1074 The parameter TC_HOP_LIMIT is the hop limit set in each TC message. 1075 TC_HOP_LIMIT MAY be a single fixed value, or MAY be different in TC 1076 messages sent by the same router. However each other router, at any 1077 hop count distance, MUST see a regular pattern of TC messages in 1078 order that meaningful values of TLVs with Type = INTERVAL_TIME and 1079 Type = VALIDITY_TIME at each hop count distance can be included as 1080 defined in [RFC5497]. Thus the pattern of TC_HOP_LIMIT MUST be 1081 defined to have this property. For example the repeating pattern 1082 (255 4 4) satisfies this property (having period TC_INTERVAL at hop 1083 counts up to 4, inclusive, and 3 x TC_INTERVAL at hop counts greater 1084 than 4), but the repeating pattern (255 255 4 4) does not satisfy 1085 this property because at hop counts greater than 4, message intervals 1086 are alternately TC_INTERVAL and 3 x TC_INTERVAL. 1088 The following constraints apply to this parameter: 1090 o The maximum value of TC_HOP_LIMIT >= the network diameter in hops, 1091 a value of 255 is RECOMMENDED. Note that if using a pattern of 1092 different values of TC_HOP_LIMIT as described above, then only the 1093 maximum value in the pattern is so constrained. 1095 o All values of TC_HOP_LIMIT >= 2. 1097 5.4.8. Willingness 1099 Each router has two willingness parameters: WILL_FLOODING and 1100 WILL_ROUTING, each of which MUST be in the range WILL_NEVER to 1101 WILL_ALWAYS, inclusive. 1103 WILL_FLOODING represents the router's willingness to be selected as a 1104 flooding MPR and hence to participate in MPR flooding, in particular 1105 of TC messages. 1107 WILL_ROUTING represents the router's willingness to be selected as a 1108 routing MPR and hence to be an intermediate router on routes. 1110 In either case, the higher the value, the greater the router's 1111 willingness to be a flooding or routing MPR, respectively. If a 1112 router has a willingness value of WILL_NEVER (the lowest possible 1113 value) it does not perform the corresponding task. A MANET using 1114 this protocol with too many routers having either willingness value 1115 equal to WILL_NEVER will not function; it MUST be ensured, by 1116 administrative or other means, that this does not happen. 1118 Note that how many routers having either willingness value equal to 1119 WILL_NEVER is "too many" depends on the network topology - which, in 1120 a MANET may change dynamically. Willingness is intended to enable 1121 that certain routers (e.g., routers that have generous resources, 1122 such as a permanent power supply) can be configured to assume more of 1123 the network operation, while others (e.g., routers that have lesser 1124 resources, such as are battery operated) can avoid such tasks. A 1125 general guideline would be that only if a router is not actually able 1126 to assume the task (flooding or routing) should it be configured with 1127 the corresponding willingness WILL_NEVER. 1129 If a router has a willingness value equal to WILL_ALWAYS (the highest 1130 possible value) then it will always be selected as a flooding or 1131 routing MPR, respectively, by all symmetric 1-hop neighbors. 1133 In a MANET in which all routers have WILL_FLOODING = WILL_ALWAYS, 1134 flooding reduction will effectively be disabled, and flooding will 1135 perform as blind flooding. 1137 In a MANET in which all routers have WILL_ROUTING = WILL_ALWAYS, 1138 topology reduction will effectively be disabled, and all routers will 1139 advertise all of their links in TC messages. 1141 A router that has WILL_ROUTING = WILL_NEVER will not act as an 1142 intermediate router in the MANET. Such a router can, act as a 1143 source, destination or gateway to another routing domain. 1145 Different routers MAY have different values for WILL_FLOODING and/or 1146 WILL_ROUTING. 1148 The following constraints apply to these parameters: 1150 o WILL_NEVER <= WILL_FLOODING <= WILL_ALWAYS 1152 o WILL_NEVER <= WILL_ROUTING <= WILL_ALWAYS 1154 5.5. Parameter Change Constraints 1156 If protocol parameters are changed dynamically, then the constraints 1157 in this section apply. 1159 RX_HOLD_TIME 1161 * If RX_HOLD_TIME for an OLSRv2 interface changes, then the 1162 expiry time for all Received Tuples for that OLSRv2 interface 1163 MAY be changed. 1165 O_HOLD_TIME 1167 * If O_HOLD_TIME changes, then the expiry time for all Originator 1168 Tuples MAY be changed. 1170 TC_INTERVAL 1172 * If TC_INTERVAL increases, then the next TC message generated by 1173 this router MUST be generated according to the previous, 1174 shorter, TC_INTERVAL. Additional subsequent TC messages MAY be 1175 generated according to the previous, shorter, TC_INTERVAL. 1177 * If TC_INTERVAL decreases, then the following TC messages from 1178 this router MUST be generated according to the current, 1179 shorter, TC_INTERVAL. 1181 P_HOLD_TIME 1183 * If P_HOLD_TIME changes, then the expiry time for all Processed 1184 Tuples MAY be changed. 1186 F_HOLD_TIME 1188 * If F_HOLD_TIME changes, then the expiry time for all Forwarded 1189 Tuples MAY be changed. 1191 TP_MAXJITTER 1193 * If TP_MAXJITTER changes, then the periodic TC message schedule 1194 on this router MAY be changed immediately. 1196 TT_MAXJITTER 1198 * If TT_MAXJITTER changes, then externally triggered TC messages 1199 on this router MAY be rescheduled. 1201 F_MAXJITTER 1203 * If F_MAXJITTER changes, then TC messages waiting to be 1204 forwarded with a delay based on this parameter MAY be 1205 rescheduled. 1207 TC_HOP_LIMIT 1209 * If TC_HOP_LIMIT changes, and the router uses multiple values 1210 after the change, then message intervals and validity times 1211 included in TC messages MUST be respected. The simplest way to 1212 do this is to start any new repeating pattern of TC_HOP_LIMIT 1213 values with its largest value. 1215 LINK_METRIC_TYPE 1217 * If LINK_METRIC_TYPE changes, then all link metric information 1218 recorded by the router is invalid. The router MUST take the 1219 following actions, and all consequent actions described in 1220 Section 17 and [RFC6130]. 1222 + For each Link Tuple in any Link Set for an OLSRv2 interface, 1223 either update L_in_metric (the value MAXIMUM_METRIC MAY be 1224 used) or remove the Link Tuple from the Link Set. 1226 + For each Link Tuple that is not removed, set: 1228 - L_out_metric := UNKNOWN_METRIC; 1230 - L_SYM_time := EXPIRED; 1232 - L_MPR_selector := false. 1234 + Remove all Router Topology Tuples, Routable Address Topology 1235 Tuples, Attached Network Tuples and Routing Tuples from 1236 their respective Protocol Sets in the Topology Information 1237 Base. 1239 5.6. Constants 1241 The following constants are specified for routers. Unlike router 1242 parameters, constants MUST NOT change, and MUST be the same on all 1243 routers. 1245 5.6.1. Link Metric Constants 1247 The constant minimum and maximum link metric values are defined by: 1249 o MINIMUM_METRIC := 1 1251 o MAXIMUM_METRIC := 16776960 1253 The symbolic value UNKNOWN_METRIC is defined in Section 6.1. 1255 5.6.2. Willingness Constants 1257 The constant minimum, RECOMMENDED default, and maximum, willingness 1258 values are defined by: 1260 o WILL_NEVER := 0 1262 o WILL_DEFAULT := 7 1264 o WILL_ALWAYS := 15 1266 5.6.3. Time Constant 1268 The constant C (time granularity) is used as specified in [RFC5497]. 1269 It MUST be the same as is used by [RFC6130], with RECOMMENDED value: 1271 o C := 1/1024 second 1273 Note that this parameter is used in the representation of time 1274 intervals. Time values (such as are stored in Protocol Tuples) are 1275 not so represented. A resolution of C in such values is sufficient 1276 (but not necessary) for such values. 1278 6. Link Metric Values 1280 A router records a link metric value for each direction of a link of 1281 which it has knowledge. These link metric values are used to create 1282 metrics for routes by the addition of link metric values. 1284 6.1. Link Metric Representation 1286 Link metrics are reported in messages using a compressed 1287 representation that occupies 12 bits, consisting of a 4 bit field and 1288 an 8 bit field. The compressed representation represents positive 1289 integer values with a minimum value of 1 and a maximum value that is 1290 slightly smaller than the maximum 24 bit value. Only those values 1291 that have exact representation in the compressed form are used. 1292 Route metrics are the summation of no more than 255 link metric 1293 values, and can therefore be represented using no more than 32 bits. 1295 Link and route metrics used in the Information Bases defined in this 1296 specification refer to the uncompressed values, and arithmetic 1297 involving them does likewise, and assumes full precision in the 1298 result. (How an implementation records the values is not part of 1299 this specification, as long as it behaves as if recording 1300 uncompressed values. An implementation can, for example, use 32 bit 1301 values for all link and route metrics.) 1303 In some cases a link metric value may be unknown. This is indicated 1304 in this specification by the symbolic value UNKNOWN_METRIC. An 1305 implementation may use any representation of UNKNOWN_METRIC as it is 1306 never included in messages, or used in any computation. (Possible 1307 representations are zero, or any value greater than the maximum 1308 representable metric value.) 1310 6.2. Link Metric Compressed Form 1312 The 12-bit compressed form of a link metric uses a modified form of a 1313 representation with an 8-bit mantissa (denoted a) and a 4-bit 1314 exponent (denoted b). Note that if represented as the 12 bit value 1315 256b+a then the ordering of those 12 bit values is identical to the 1316 ordering of the represented values. 1318 The value so represented is (257+a)2^b - 256, where ^ denotes 1319 exponentiation. This has a minimum value (when a = 0 and b = 0) of 1320 MINIMUM_METRIC = 1 and a maximum value (when a = 255 and b = 15) of 1321 MAXIMUM_METRIC = 2^24 - 256. 1323 An algorithm for computing a and b for the smallest representable 1324 value not less than a link metric value v such that MINIMUM_METRIC <= 1325 v <= MAXIMUM_METRIC is: 1327 1. Find the smallest integer b such that v + 256 <= 2^(b + 9). 1329 2. Set a := (v - 256(2^b - 1)) / (2^b) - 1, rounded up to the 1330 nearest integer. 1332 7. Local Information Base 1334 The Local Information Base, as defined for each router in [RFC6130], 1335 is extended by this protocol by: 1337 o Recording the router's originator address. The originator address 1338 MUST be unique to this router. It MUST NOT be used by any other 1339 router as an originator address. It MAY be included in any 1340 network address in any I_local_iface_addr_list of this router, it 1341 MUST NOT be included in any network address in any 1342 I_local_iface_addr_list of any other router. It MAY be included 1343 in, but MUST NOT be equal to, the AL_net_addr in any Local 1344 Attached Network Tuple in this or any other router. 1346 o The addition of an Originator Set, defined in Section 7.1, and a 1347 Local Attached Network Set, defined in Section 7.2. 1349 All routable addresses of the router for which it is to accept IP 1350 packets as destination MUST be included in the Local Interface Set or 1351 the Local Attached Network Set. 1353 7.1. Originator Set 1355 A router's Originator Set records addresses that were recently used 1356 as originator addresses by this router. If a router's originator 1357 address is immutable then the Originator Set is always empty and MAY 1358 be omitted. It consists of Originator Tuples: 1360 (O_orig_addr, O_time) 1362 where: 1364 O_orig_addr is a recently used originator address; note that this 1365 does not include a prefix length. 1367 O_time specifies the time at which this Tuple expires and MUST be 1368 removed. 1370 7.2. Local Attached Network Set 1372 A router's Local Attached Network Set records its local non-OLSRv2 1373 interfaces via which it can act as a gateway to other networks. The 1374 Local Attached Network Set MUST be provided to this protocol and MUST 1375 reflect any changes in the router's status. (In cases where the 1376 router's configuration is static, the Local Attached Network Set will 1377 be constant; in cases where the router has no non-OLSRv2 interfaces, 1378 the Local Attached Network Set will be empty.) The Local Attached 1379 Network Set is not modified by this protocol. This protocol will 1380 respond to (externally provided) changes to the Local Attached 1381 Network Set. It consists of Local Attached Network Tuples: 1383 (AL_net_addr, AL_dist, AL_metric) 1385 where: 1387 AL_net_addr is the network address of an attached network which 1388 can be reached via this router. This SHOULD be a routable 1389 address. It is constrained as described below. 1391 AL_dist is the number of hops to the network with network address 1392 AL_net_addr from this router. 1394 AL_metric is the metric of the link to the attached network with 1395 address AL_net_addr from this router. 1397 Attached networks local to this router only (i.e., not reachable 1398 except via this router) SHOULD be treated as local non-MANET 1399 interfaces, and added to the Local Interface Set, as specified in 1400 [RFC6130], rather than be added to the Local Attached Network Set. 1402 Because an attached network is not specific to the router, and may be 1403 outside the MANET, an attached network MAY also be attached to other 1404 routers. Routing to an AL_net_addr will use maximum prefix length 1405 matching; consequently an AL_net_addr MAY include, but MUST NOT equal 1406 or be included in, any network address which is of any interface of 1407 any router (i.e., is included in any I_local_iface_addr_list) or 1408 equal any router's originator address. 1410 It is not the responsibility of this protocol to maintain routes from 1411 this router to networks recorded in the Local Attached Network Set. 1413 Local Attached Neighbor Tuples are removed from the Local Attached 1414 Network Set only when the router's local attached network 1415 configuration changes, i.e., they are not subject to timer-based 1416 expiration or changes due to received messages. 1418 8. Interface Information Base 1420 An Interface Information Base, as defined in [RFC6130], is maintained 1421 for each MANET interface. The Link Set and 2-Hop Set in the 1422 Interface Information Base for an OLSRv2 interface are modified by 1423 this protocol. In some cases it may be convenient to consider these 1424 Sets as also containing these additional elements for other MANET 1425 interfaces, taking the indicated values on creation, but never being 1426 updated. 1428 8.1. Link Set 1430 The Link Set is modified by adding these additional elements to each 1431 Link Tuple: 1433 L_in_metric is the metric of the link from the OLSRv2 interface 1434 with addresses L_neighbor_iface_addr_list to this OLSRv2 1435 interface; 1437 L_out_metric is the metric of the link to the OLSRv2 interface 1438 with addresses L_neighbor_iface_addr_list from this OLSRv2 1439 interface; 1441 L_mpr_selector is a boolean flag, describing if this neighbor has 1442 selected this router as a flooding MPR, i.e., is a flooding MPR 1443 selector of this router. 1445 L_in_metric will be specified by a process that is external to this 1446 specification. Any Link Tuple with L_status = HEARD or L_status = 1447 SYMMETRIC MUST have a specified value of L_in_metric if it is to be 1448 used by this protocol. 1450 A Link Tuple created (but not updated) by [RFC6130] MUST set: 1452 o L_in_metric := UNKNOWN_METRIC; 1454 o L_out_metric := UNKNOWN_METRIC; 1456 o L_mpr_selector := false. 1458 8.2. 2-Hop Set 1460 The 2-Hop Set is modified by adding these additional elements to each 1461 2-Hop Tuple: 1463 N2_in_metric is the neighbor metric from the router with address 1464 N2_2hop_iface_addr to the router with OLSRv2 interface addresses 1465 N2_neighbor_iface_addr_list; 1467 N2_out_metric is the neighbor metric to the router with address 1468 N2_2hop_iface_addr from the router with OLSRv2 interface addresses 1469 N2_neighbor_iface_addr_list. 1471 A 2-Hop Tuple created (but not updated) by [RFC6130] MUST set: 1473 o N2_in_metric := UNKNOWN_METRIC; 1475 o N2_out_metric := UNKNOWN_METRIC. 1477 9. Neighbor Information Base 1479 A Neighbor Information Base, as defined in [RFC6130], is maintained 1480 for each router. It is modified by this protocol by adding these 1481 additional elements to each Neighbor Tuple in the Neighbor Set. In 1482 some cases it may be convenient to consider these Sets as also 1483 containing these additional elements for other MANET interfaces, 1484 taking the indicated values on creation, but never being updated. 1486 N_orig_addr is the neighbor's originator address, which may be 1487 unknown. Note that this originator address does not include a 1488 prefix length; 1490 N_in_metric is the neighbor metric of any link from this neighbor 1491 to an OLSRv2 interface of this router, i.e., the minimum of all 1492 corresponding L_in_metric with L_status = SYMMETRIC and 1493 L_in_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no such 1494 Link Tuples; 1496 N_out_metric is the neighbor metric of any link from an OLSRv2 1497 interface of this router to this neighbor, i.e., the minimum of 1498 all corresponding L_out_metric with L_status = SYMMETRIC and 1499 L_out_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no 1500 such Link Tuples; 1502 N_will_flooding is the neighbor's willingness to be selected as a 1503 flooding MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1504 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1505 information is received from this neighbor; 1507 N_will_routing is the neighbor's willingness to be selected as a 1508 routing MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1509 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1510 information is received from this neighbor; 1512 N_flooding_mpr is a boolean flag, describing if this neighbor is 1513 selected as a flooding MPR by this router; 1515 N_routing_mpr is a boolean flag, describing if this neighbor is 1516 selected as a routing MPR by this router; 1518 N_mpr_selector is a boolean flag, describing if this neighbor has 1519 selected this router as a routing MPR, i.e., is a routing MPR 1520 selector of this router. 1522 N_advertised is a boolean flag, describing if this router has 1523 elected to advertise a link to this neighbor in its TC messages. 1525 A Neighbor Tuple created (but not updated) by [RFC6130] MUST set: 1527 o N_orig_addr := unknown; 1529 o N_in_metric := UNKNOWN_METRIC; 1531 o N_out_metric := UNKNOWN_METRIC; 1533 o N_will_flooding := WILL_NEVER; 1535 o N_will_routing := WILL_NEVER; 1537 o N_routing_mpr := false; 1539 o N_flooding_mpr := false; 1541 o N_mpr_selector := false; 1543 o N_advertised := false. 1545 The Neighbor Information Base also includes a variable, the 1546 Advertised Neighbor Sequence Number (ANSN), whose value is included 1547 in TC messages to indicate the freshness of the information 1548 transmitted. The ANSN is incremented whenever advertised information 1549 (the originator and routable addresses included in Neighbor Tuples 1550 with N_advertised = true, and local attached networks recorded in the 1551 Local Attached Network Set in the Local Information Base) changes, 1552 including addition or removal of such information. 1554 10. Topology Information Base 1556 The Topology Information Base, defined for each router by this 1557 specification, stores information received in TC messages, in the 1558 Advertising Remote Router Set, the Router Topology Set, the Routable 1559 Address Topology Set and the Attached Network Set. 1561 Additionally, a Routing Set is maintained, derived from the 1562 information recorded in the Local Information Base, the Interface 1563 Information Bases, the Neighbor Information Base and the rest of the 1564 Topology Information Base. 1566 10.1. Advertising Remote Router Set 1568 A router's Advertising Remote Router Set records information 1569 describing each remote router in the network that transmits TC 1570 messages, allowing outdated TC messages to be recognized and 1571 discarded. It consists of Advertising Remote Router Tuples: 1573 (AR_orig_addr, AR_seq_number, AR_time) 1575 where: 1577 AR_orig_addr is the originator address of a received TC message, 1578 note that this does not include a prefix length; 1580 AR_seq_number is the greatest ANSN in any TC message received 1581 which originated from the router with originator address 1582 AR_orig_addr (i.e., which contributed to the information contained 1583 in this Tuple); 1585 AR_time is the time at which this Tuple expires and MUST be 1586 removed. 1588 10.2. Router Topology Set 1590 A router's Topology Set records topology information about the links 1591 between routers in the MANET. It consists of Router Topology Tuples: 1593 (TR_from_orig_addr, TR_to_orig_addr, TR_seq_number, TR_metric, 1594 TR_time) 1596 where: 1598 TR_from_orig_addr is the originator address of a router which can 1599 reach the router with originator address TR_to_orig_addr in one 1600 hop, note that this does not include a prefix length; 1602 TR_to_orig_addr is the originator address of a router which can be 1603 reached by the router with originator address TR_to_orig_addr in 1604 one hop, note that this does not include a prefix length; 1606 TR_seq_number is the greatest ANSN in any TC message received 1607 which originated from the router with originator address 1608 TR_from_orig_addr (i.e., which contributed to the information 1609 contained in this Tuple); 1611 TR_metric is the neighbor metric from the router with originator 1612 address TR_from_orig_addr to the router with originator address 1613 TR_to_orig_addr; 1615 TR_time specifies the time at which this Tuple expires and MUST be 1616 removed. 1618 10.3. Routable Address Topology Set 1620 A router's Routable Address Topology Set records topology information 1621 about the routable addresses within the MANET, and via which routers 1622 they may be reached. It consists of Routable Address Topology 1623 Tuples: 1625 (TA_from_orig_addr, TA_dest_addr, TA_seq_number, TA_metric, 1626 TA_time) 1628 where: 1630 TA_from_orig_addr is the originator address of a router which can 1631 reach the router with routable address TA_dest_addr in one hop, 1632 note that this does not include a prefix length; 1634 TA_dest_addr is a routable address of a router which can be 1635 reached by the router with originator address TA_from_orig_addr in 1636 one hop; 1638 TA_seq_number is the greatest ANSN in any TC message received 1639 which originated from the router with originator address 1640 TA_from_orig_addr (i.e., which contributed to the information 1641 contained in this Tuple); 1642 TA_metric is the neighbor metric from the router with originator 1643 address TA_from_orig_addr to the router with OLSRv2 interface 1644 address TA_dest_addr; 1646 TA_time specifies the time at which this Tuple expires and MUST be 1647 removed. 1649 10.4. Attached Network Set 1651 A router's Attached Network Set records information about networks 1652 (which may be outside the MANET) attached to other routers and their 1653 routable addresses. It consists of Attached Network Tuples: 1655 (AN_orig_addr, AN_net_addr, AN_seq_number, AN_dist, AN_metric, 1656 AN_time) 1658 where: 1660 AN_orig_addr is the originator address of a router which can act 1661 as gateway to the network with network address AN_net_addr, note 1662 that this does not include a prefix length; 1664 AN_net_addr is the network address of an attached network, which 1665 may be reached via the router with originator address 1666 AN_orig_addr; 1668 AN_seq_number is the greatest ANSN in any TC message received 1669 which originated from the router with originator address 1670 AN_orig_addr (i.e., which contributed to the information contained 1671 in this Tuple); 1673 AN_dist is the number of hops to the network with network address 1674 AN_net_addr from the router with originator address AN_orig_addr; 1676 AN_metric is the metric of the link from the router with 1677 originator address AN_orig_addr to the attached network with 1678 address AN_net_addr; 1680 AN_time specifies the time at which this Tuple expires and MUST be 1681 removed. 1683 10.5. Routing Set 1685 A router's Routing Set records the first hop along a selected path to 1686 each destination for which any such path is known. It consists of 1687 Routing Tuples: 1689 (R_dest_addr, R_next_iface_addr, R_local_iface_addr, R_dist, 1690 R_metric) 1692 where: 1694 R_dest_addr is the network address of the destination, either the 1695 network address of an interface of a destination router, or the 1696 network address of an attached network; 1698 R_next_iface_addr is the network address of the "next hop" on the 1699 selected path to the destination; 1701 R_local_iface_addr is an address of the local interface over which 1702 an IP packet MUST be sent to reach the destination by the selected 1703 path. 1705 R_dist is the number of hops on the selected path to the 1706 destination; 1708 R_metric is the metric of the route to the destination with 1709 address R_dest_addr. 1711 The Routing Set for a router is derived from the contents of other 1712 Protocol Sets of the router (the Link Sets, the Neighbor Set, the 1713 Router Topology Set, the Routable Address Topology Set, the Attached 1714 Network Set, and OPTIONAL use of the 2-Hop Sets). The Routing Set is 1715 updated (Routing Tuples added or removed, or the complete Routing Set 1716 recalculated) when routing paths are calculated, based on changes to 1717 these other Protocol Sets. Routing Tuples are not subject to timer- 1718 based expiration. 1720 11. Received Message Information Base 1722 The Received Message Information Base, defined by this specification, 1723 records information required to ensure that a message is processed at 1724 most once and is forwarded at most once per OLSRv2 interface of a 1725 router, using MPR flooding. Messages are recorded using their 1726 "signature", consisting of their type, originator address, and 1727 message sequence number. 1729 11.1. Received Set 1731 A router has a Received Set per OLSRv2 interface. Each Received Set 1732 records the signatures of messages which have been received over that 1733 OLSRv2 interface. Each consists of Received Tuples: 1735 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 1737 where: 1739 RX_type is the received Message Type; 1741 RX_orig_addr is the originator address of the received message, 1742 note that this does not include a prefix length; 1744 RX_seq_number is the message sequence number of the received 1745 message; 1747 RX_time specifies the time at which this Tuple expires and MUST be 1748 removed. 1750 11.2. Processed Set 1752 A router has a single Processed Set which records signatures of 1753 messages which have been processed by the router. It consists of 1754 Processed Tuples: 1756 (P_type, P_orig_addr, P_seq_number, P_time) 1758 where: 1760 P_type is the processed Message Type; 1762 P_orig_addr is the originator address of the processed message, 1763 note that this does not include a prefix length; 1765 P_seq_number is the message sequence number of the processed 1766 message; 1768 P_time specifies the time at which this Tuple expires and MUST be 1769 removed. 1771 11.3. Forwarded Set 1773 A router has a single Forwarded Set which records signatures of 1774 messages which have been forwarded by the router. It consists of 1775 Forwarded Tuples: 1777 (F_type, F_orig_addr, F_seq_number, F_time) 1779 where: 1781 F_type is the forwarded Message Type; 1783 F_orig_addr is the originator address of the forwarded message, 1784 note that this does not include a prefix length; 1785 F_seq_number is the message sequence number of the forwarded 1786 message; 1788 F_time specifies the time at which this Tuple expires and MUST be 1789 removed. 1791 12. Information Base Properties 1793 This section describes some additional properties of Information 1794 Bases and their contents. 1796 12.1. Corresponding Protocol Tuples 1798 As part of this specification, in a number of cases there is a 1799 natural correspondence from a Protocol Tuple in one Protocol Set to a 1800 single Protocol Tuple in another Protocol Set, in the same or another 1801 Information Base. The latter Protocol Tuple is referred to as 1802 "corresponding" to the former Protocol Tuple. 1804 Specific examples of corresponding Protocol Tuples include: 1806 o There is a Local Interface Tuple corresponding to each Link Tuple, 1807 where the Link Tuple is in the Link Set for a MANET interface, and 1808 the Local Interface Tuple represents that MANET interface. 1810 o There is a Neighbor Tuple corresponding to each Link Tuple which 1811 has L_HEARD_time not EXPIRED, such that N_neighbor_addr_list 1812 contains L_neighbor_iface_addr_list. 1814 o There is a Link Tuple (in the Link Set in the same Interface 1815 Information Base) corresponding to each 2-Hop Tuple such that 1816 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 1818 o There is a Neighbor Tuple corresponding to each 2-Hop Tuple, such 1819 that N_neighbor_addr_list contains N2_neighbor_iface_addr_list. 1820 (This is the Neighbor Tuple corresponding to the Link Tuple 1821 corresponding to the 2-Hop Tuple.) 1823 o There is an Advertising Remote Router Tuple corresponding to each 1824 Router Topology Tuple such that AR_orig_addr = TR_from_orig_addr. 1826 o There is an Advertising Remote Router Tuple corresponding to each 1827 Routable Address Topology Tuple such that AR_orig_addr = 1828 TA_from_orig_addr. 1830 o There is an Advertising Remote Router Tuple corresponding to each 1831 Attached Network Tuple such that AR_orig_addr = AN_orig_addr. 1833 o There is a Neighbor Tuple corresponding to each Routing Tuple such 1834 that N_neighbor_addr_list contains R_next_iface_addr. 1836 12.2. Address Ownership 1838 Addresses or network addresses with the following properties are 1839 considered as "fully owned" by a router when processing a received 1840 message: 1842 o Equaling its originator address, OR; 1844 o Equaling the O_orig_addr in an Originator Tuple, OR; 1846 o Equaling or being a sub-range of the I_local_iface_addr_list in a 1847 Local Interface Tuple, OR; 1849 o Equaling or being a sub-range of the IR_local_iface_addr in a 1850 Removed Interface Address Tuple, OR; 1852 o Equaling an AL_net_addr in a Local Attached Network Tuple. 1854 Addresses or network addresses with the following properties are 1855 considered as "partially owned" (which may include being fully owned) 1856 by a router when processing a received message: 1858 o Overlapping (equaling or containing) its originator address, OR; 1860 o Overlapping (equaling or containing) the O_orig_addr in an 1861 Originator Tuple, OR; 1863 o Overlapping the I_local_iface_addr_list in a Local Interface 1864 Tuple, OR; 1866 o Overlapping the IR_local_iface_addr in a Removed Interface Address 1867 Tuple, OR; 1869 o Equaling or having as a sub-range an AL_net_addr in a Local 1870 Attached Network Tuple. 1872 13. Packets and Messages 1874 The packet and message format used by this protocol is defined in 1875 [RFC5444]. Except as otherwise noted, options defined in [RFC5444] 1876 may be freely used, in particular alternative formats defined by 1877 packet, message, Address Block and TLV flags. 1879 This section describes the usage of the packets and messages defined 1880 in [RFC5444] by this specification, and the TLVs defined by, and used 1881 in, this specification. 1883 13.1. Messages 1885 Routers using this protocol exchange information through messages. 1886 The message types used by this protocol are the HELLO message and the 1887 TC message. The HELLO message is defined by [RFC6130] and extended 1888 by this specification, see Section 15. The TC message is defined by 1889 this specification, see Section 16. 1891 13.2. Packets 1893 One or more messages sent by a router at the same time SHOULD be 1894 combined into a single packet, subject to any constraints on maximum 1895 packet size (such as derived from the MTU over a local single hop) 1896 that MAY be imposed. These messages may have originated at the 1897 sending router, or have originated at another router and are being 1898 forwarded by the sending router. Messages with different originating 1899 routers MAY be combined for transmission within the same packet. 1900 Messages from other protocols defined using [RFC5444], including but 1901 not limited to [RFC6130], MAY be combined for transmission within the 1902 same packet. This specification does not define or use any contents 1903 of the Packet Header. 1905 Forwarded messages MAY be jittered as described in [RFC5148], 1906 including the observation that the forwarding jitter of all messages 1907 received in a single packet SHOULD be the same. The value of 1908 MAXJITTER used in jittering a forwarded message MAY be based on 1909 information in that message (in particular any Message TLVs with Type 1910 = INTERVAL_TIME or Type = VALIDITY_TIME) or otherwise SHOULD be with 1911 a maximum delay of F_MAXJITTER. A router MAY modify the jitter 1912 applied to a message in order to more efficiently combine messages in 1913 packets, as long as the maximum jitter is not exceeded. 1915 13.3. TLVs 1917 This specification defines two Message TLVs and four Address Block 1918 TLVs. 1920 All references in this specification to TLVs that do not indicate a 1921 type extension, assume Type Extension = 0. TLVs in processed 1922 messages with a type extension which is neither zero as so assumed, 1923 nor a specifically indicated non-zero type extension, are ignored. 1925 13.3.1. Message TLVs 1927 The MPR_WILLING TLV is used in HELLO messages. A message MUST NOT 1928 contain more than one MPR_WILLING TLV. 1930 +-------------+--------------+--------------------------------------+ 1931 | Type | Value Length | Value | 1932 +-------------+--------------+--------------------------------------+ 1933 | MPR_WILLING | 1 octet | Bits 0-3 encode the parameter | 1934 | | | WILL_FLOODING; bits 4-7 encode the | 1935 | | | parameter WILL_ROUTING. | 1936 +-------------+--------------+--------------------------------------+ 1938 Table 1: MPR_WILLING TLV definition 1940 The CONT_SEQ_NUM TLV is used in TC messages. A message MUST NOT 1941 contain more than one CONT_SEQ_NUM TLV. 1943 +--------------+--------------+-------------------------------------+ 1944 | Type | Value Length | Value | 1945 +--------------+--------------+-------------------------------------+ 1946 | CONT_SEQ_NUM | 2 octets | The ANSN contained in the Neighbor | 1947 | | | Information Base. | 1948 +--------------+--------------+-------------------------------------+ 1950 Table 2: CONT_SEQ_NUM TLV definition 1952 13.3.2. Address Block TLVs 1954 The LINK_METRIC TLV is used in HELLO messages and TC messages. It 1955 MAY use any type extension; only LINK_METRIC TLVs with type extension 1956 equal to LINK_METRIC_TYPE will be used by this specification. An 1957 address MUST NOT be associated with more than one link metric value 1958 for any given type extension, kind (link or neighbor) and direction 1959 using this TLV. 1961 +-------------+--------------+--------------------------------------+ 1962 | Type | Value Length | Value | 1963 +-------------+--------------+--------------------------------------+ 1964 | LINK_METRIC | 2 octets | Bits 0-3 indicates kind(s) and | 1965 | | | direction(s), bits 4-7 indicate | 1966 | | | exponent (a), bits 8-15 indicate | 1967 | | | mantissa (b) | 1968 +-------------+--------------+--------------------------------------+ 1970 Table 3: LINK_METRIC TLV definition 1972 The exponent and mantissa use the representation defined in 1973 Section 6. Each bit of the types and directions sub-field, if set 1974 ('1') indicates that the link metric is of the indicated kind and 1975 direction. Any combination of these bits MAY be used. 1977 +-----+-----------------+-----------+ 1978 | Bit | Kind | Direction | 1979 +-----+-----------------+-----------+ 1980 | 0 | Link metric | Incoming | 1981 | 1 | Link metric | Outgoing | 1982 | 2 | Neighbor metric | Incoming | 1983 | 3 | Neighbor metric | Outgoing | 1984 +-----+-----------------+-----------+ 1986 Table 4: LINK_METRIC TLV types and directions 1988 The MPR TLV is used in HELLO messages, and indicates that an address 1989 with which it is associated is of a symmetric 1-hop neighbor that has 1990 been selected as an MPR. 1992 +------+--------------+---------------------------------------------+ 1993 | Type | Value Length | Value | 1994 +------+--------------+---------------------------------------------+ 1995 | MPR | 1 octet | FLOODING indicates that the corresponding | 1996 | | | address is of a neighbor selected as a | 1997 | | | flooding MPR, ROUTING indicates that the | 1998 | | | corresponding address is of a neighbor | 1999 | | | selected as a routing MPR, FLOOD_ROUTE | 2000 | | | indicates both (see Section 24.6). | 2001 +------+--------------+---------------------------------------------+ 2003 Table 5: MPR TLV definition 2005 The NBR_ADDR_TYPE TLV is used in TC messages. 2007 +---------------+--------------+------------------------------------+ 2008 | Type | Value Length | Value | 2009 +---------------+--------------+------------------------------------+ 2010 | NBR_ADDR_TYPE | 1 octet | ORIGINATOR indicates that the | 2011 | | | corresponding address (which MUST | 2012 | | | have maximum prefix length) is an | 2013 | | | originator address, ROUTABLE | 2014 | | | indicates that the corresponding | 2015 | | | network address is a routable | 2016 | | | address of an interface, | 2017 | | | ROUTABLE_ORIG indicates that the | 2018 | | | corresponding address is both (see | 2019 | | | Section 24.6). | 2020 +---------------+--------------+------------------------------------+ 2022 Table 6: NBR_ADDR_TYPE TLV definition 2024 If an address is both an originator address and a routable address, 2025 then it may be associated with either one Address Block TLV with Type 2026 := NBR_ADDR_TYPE and Value := ROUTABLE_ORIG, or with two Address 2027 Block TLVs with Type:= NBR_ADDR_TYPE, one with Value := ORIGINATOR 2028 and one with Value := ROUTABLE. 2030 The GATEWAY TLV is used in TC messages. An address MUST NOT be 2031 associated with more than one hop count value using this TLV. 2033 +---------+--------------+-------------------------------------+ 2034 | Type | Value Length | Value | 2035 +---------+--------------+-------------------------------------+ 2036 | GATEWAY | 1 octet | Number of hops to attached network. | 2037 +---------+--------------+-------------------------------------+ 2039 Table 7: GATEWAY TLV definition 2041 All address objects included in a TC message according to this 2042 specification MUST be associated either with at least one TLV with 2043 Type := NBR_ADDR_TYPE or with a TLV with Type := GATEWAY, but not 2044 both. Any other address objects MAY be included in Address Blocks in 2045 a TC message, but are ignored by this specification. 2047 14. Message Processing and Forwarding 2049 This section describes the optimized flooding operation (MPR 2050 flooding) used when control messages, as instances of [RFC5444], are 2051 intended for MANET wide distribution. This flooding mechanism 2052 defines when a received message is, or is not, processed and/or 2053 forwarded. 2055 This flooding mechanism is used by this protocol and MAY be used by 2056 extensions to this protocol which define, and hence own, other 2057 Message Types, to manage processing and/or forwarding of these 2058 messages. This specification contains elements (P_type, RX_type, 2059 F_type) required only for such usage. 2061 This flooding mechanism is always used for TC messages (see 2062 Section 16). Received HELLO messages (see Section 15) are, unless 2063 invalid, always processed, and never forwarded by this flooding 2064 mechanism. They thus do not need to be recorded in the Received 2065 Message Information Base. 2067 The processing selection and forwarding mechanisms are designed to 2068 only need to parse the Message Header in order to determine whether a 2069 message is to be processed and/or forwarded, and not to have to parse 2070 the Message Body even if the message is forwarded (but not 2071 processed). An implementation MAY only parse the Message Body if 2072 necessary, or MAY always parse the Message Body and reject the 2073 message if it cannot be so parsed, or any other error is identified. 2075 An implementation MUST discard the message silently if it is unable 2076 to parse the Message Header or (if attempted) the Message Body, or if 2077 a message (other than a HELLO message) does not include a message 2078 sequence number. 2080 14.1. Actions when Receiving a Message 2082 On receiving, on an OLSRv2 interface, a message of a type specified 2083 to be using this mechanism, which includes the TC messages defined in 2084 this specification, a router MUST perform the following: 2086 1. If the router recognizes from the originator address of the 2087 message that the message is one which the receiving router itself 2088 originated (i.e., the message originator address is the 2089 originator address of this router, or is an O_orig_addr in an 2090 Originator Tuple) then the message MUST be silently discarded. 2092 2. Otherwise: 2094 1. If the message is of a type which may be processed, then the 2095 message is considered for processing according to 2096 Section 14.2. 2098 2. If the message is of a type which may be forwarded, AND: 2100 + is present and > 1; AND 2102 + is not present or < 255; 2104 then the message is considered for forwarding according to 2105 Section 14.3. 2107 14.2. Message Considered for Processing 2109 If a message (the "current message") is considered for processing, 2110 then the following tasks MUST be performed: 2112 1. If the sending address (i.e., the source address of the IP 2113 datagram containing the current message) does not match (taking 2114 into account any address prefix) a network address in an 2115 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2116 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2117 current message was received (the "receiving interface") then 2118 processing the current message is OPTIONAL. If the current 2119 message is not processed then the following steps are not carried 2120 out. 2122 2. If a Processed Tuple exists with: 2124 * P_type = the Message Type of the current message; AND 2126 * P_orig_addr = the originator address of the current message; 2127 AND 2129 * P_seq_number = the message sequence number of the current 2130 message; 2132 then the current message MUST NOT be processed. 2134 3. Otherwise: 2136 1. Create a Processed Tuple in the Processed Set with: 2138 + P_type := the Message Type of the current message; 2140 + P_orig_addr := the originator address of the current 2141 message; 2143 + P_seq_number := the sequence number of the current 2144 message; 2146 + P_time := current time + P_HOLD_TIME. 2148 2. Process the current message according to its Message Type. 2149 For a TC message this is as defined in Section 16.3. 2151 14.3. Message Considered for Forwarding 2153 If a message (the "current message") is considered for forwarding, 2154 then the following tasks MUST be performed: 2156 1. If the sending address (i.e., the source address of the IP 2157 datagram containing the current message) does not match (taking 2158 into account any address prefix) a network address in an 2159 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2160 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2161 current message was received (the "receiving interface") then the 2162 current message MUST be silently discarded. 2164 2. Otherwise: 2166 1. If a Received Tuple exists in the Received Set for the 2167 receiving interface, with: 2169 + RX_type = the Message Type of the current message; AND 2171 + RX_orig_addr = the originator address of the current 2172 message; AND 2174 + RX_seq_number = the sequence number of the current 2175 message; 2177 then the current message MUST be silently discarded. 2179 2. Otherwise: 2181 1. Create a Received Tuple in the Received Set for the 2182 receiving interface with: 2184 - RX_type := the Message Type of the current message; 2186 - RX_orig_addr := originator address of the current 2187 message; 2189 - RX_seq_number := sequence number of the current 2190 message; 2192 - RX_time := current time + RX_HOLD_TIME. 2194 2. If a Forwarded Tuple exists with: 2196 - F_type = the Message Type of the current message; AND 2198 - F_orig_addr = the originator address of the current 2199 message; AND 2201 - F_seq_number = the sequence number of the current 2202 message. 2204 then the current message MUST be silently discarded. 2206 3. Otherwise if the sending address matches (taking account 2207 of any address prefix) any network address in an 2208 L_neighbor_iface_addr_list of a Link Tuple in the Link 2209 Set for the receiving OLSRv2 interface that has L_status 2210 = SYMMETRIC and whose corresponding Neighbor Tuple has 2211 N_mpr_selector = true, then: 2213 1. Create a Forwarded Tuple in the Forwarded Set with: 2215 o F_type := the Message Type of the current message; 2217 o F_orig_addr := originator address of the current 2218 message; 2220 o F_seq_number := sequence number of the current 2221 message; 2223 o F_time := current time + F_HOLD_TIME. 2225 2. The Message Header of the current message is modified 2226 by: 2228 o Decrement in the Message Header by 2229 1; AND 2231 o If present, increment in the 2232 Message Header by 1. 2234 3. The message is transmitted over all OLSRv2 2235 interfaces, as described in Section 13. 2237 4. Otherwise, the current message MUST be silently 2238 discarded. 2240 15. HELLO Messages 2242 The HELLO Message Type is owned by [RFC6130], and thus HELLO messages 2243 are generated, transmitted, received and processed by [RFC6130]. 2244 This protocol, as permitted by [RFC6130], also uses HELLO messages, 2245 including adding to HELLO message generation, and implementing 2246 additional processing based on received HELLO messages. HELLO 2247 messages are not forwarded by [RFC6130] or by this specification. 2249 15.1. HELLO Message Generation 2251 HELLO messages sent over OLSRv2 interfaces are generated as defined 2252 in [RFC6130], and then modified as described in this section. HELLO 2253 messages sent on other MANET interfaces are not modified by this 2254 specification. 2256 HELLO messages sent over OLSRv2 interfaces are extended by adding the 2257 following elements: 2259 o A message originator address, recording this router's originator 2260 address. This MUST use a element, unless: 2262 * The message specifies only a single local interface address 2263 (i.e., contains only one address object that is associated with 2264 an Address Block TLV with Type = LOCAL_IF, and which has no 2265 prefix length, or a maximum prefix length) which will then be 2266 used as the message originator address, OR; 2268 * The message does not include any local interface network 2269 addresses (i.e., has no address objects associated with an 2270 Address Block TLV with Type = LOCAL_IF), as permitted by the 2271 specification in [RFC6130], when the router that generated the 2272 HELLO message has only one interface address and will use that 2273 as the sending address of the IP datagram in which the HELLO 2274 message is contained. In this case, that address will be used 2275 as the message originator address. 2277 o A Message TLV with Type := MPR_WILLING MUST be included. 2279 o The following cases associate Address Block TLVs with one or more 2280 addresses from a Link Tuple or a Neighbor Tuple if these are 2281 included in the HELLO message. In each case, the TLV MUST be 2282 associated with at least one address object for an address from 2283 the relevant Tuple; the TLV MAY be associated with more such 2284 addresses (including a copy of that address object, possibly not 2285 itself associated with any other indicated TLVs, in the same or a 2286 different Address Block). These additional TLVs MUST NOT be 2287 associated with any other addresses in a HELLO message that will 2288 be processed by [RFC6130]. 2290 * For each Link Tuple for which L_in_metric != UNKNOWN_METRIC, 2291 and for which one or more addresses in its 2292 L_neighbor_iface_addr_list are included as address objects with 2293 an associated Address Block TLV with Type = LINK_STATUS and 2294 Value = HEARD or Value = SYMMETRIC, at least one of these 2295 addresses MUST be associated with an Address Block TLV with 2296 Type := LINK_METRIC indicating an incoming link metric with 2297 value L_in_metric. 2299 * For each Link Tuple for which L_out_metric != UNKNOWN_METRIC, 2300 and for which one or more addresses in its 2301 L_neighbor_iface_addr_list are included as address objects with 2302 an associated Address Block TLV with Type = LINK_STATUS and 2303 Value = SYMMETRIC, at least one of these addresses MUST be 2304 associated with an Address Block TLV with Type := LINK_METRIC 2305 indicating an outgoing link metric with value L_out_metric. 2307 * For each Neighbor Tuple for which N_symmetric = true, and for 2308 which one or more addresses in its N_neighbor_addr_list are 2309 included as address objects with an associated Address Block 2310 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2311 SYMMETRIC, at least one of these addresses MUST be associated 2312 with an Address Block TLV with Type := LINK_METRIC indicating 2313 an incoming neighbor metric with value N_in_metric. 2315 * For each Neighbor Tuple for which N_symmetric = true, and for 2316 which one or more addresses in its N_neighbor_addr_list are 2317 included as address objects with an associated Address Block 2318 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2319 SYMMETRIC, at least one of these addresses MUST be associated 2320 with an Address Block TLV with Type := LINK_METRIC indicating 2321 an outgoing neighbor metric with value N_out_metric. 2323 * For each Neighbor Tuple with N_flooding_mpr = true, and for 2324 which one or more network addresses in its N_neighbor_addr_list 2325 are included as address objects in the HELLO message with an 2326 associated Address Block TLV with Type = LINK_STATUS and Value 2327 = SYMMETRIC, at least one of these addresses MUST be associated 2328 with an Address Block TLV with Type := MPR and Value := 2329 FLOODING or Value := FLOOD_ROUTE. 2331 * For each Neighbor Tuple with N_routing_mpr = true, and for 2332 which one or more network addresses in its N_neighbor_addr_list 2333 are included as address objects in the HELLO message with an 2334 associated Address Block TLV with Type = LINK_STATUS and Value 2335 = SYMMETRIC, at least one of these addresses MUST be associated 2336 with an Address Block TLV with Type := MPR and Value := ROUTING 2337 or Value := FLOOD_ROUTE. 2339 15.2. HELLO Message Transmission 2341 HELLO messages are scheduled and transmitted by [RFC6130]. This 2342 protocol MAY require that an additional HELLO message is sent on each 2343 OLSRv2 interface when either of the router's sets of MPRs changes, in 2344 addition to the cases specified in [RFC6130], and subject to the 2345 constraints specified in [RFC6130] (notably on minimum HELLO message 2346 transmission intervals). 2348 15.3. HELLO Message Processing 2350 When received on an OLSRv2 interface, HELLO messages are made 2351 available to this protocol in two ways, both as permitted by 2352 [RFC6130]: 2354 o Such received HELLO messages MUST be made available to this 2355 protocol on reception, which allows them to be discarded before 2356 being processed by [RFC6130], for example if the information added 2357 to the HELLO message by this specification is inconsistent. 2359 o Such received HELLO messages MUST be made available to OLSRv2 2360 after [RFC6130] has completed its processing thereof, unless 2361 discarded as malformed by [RFC6130], for processing by this 2362 specification. 2364 15.3.1. HELLO Message Discarding 2366 In addition to the reasons specified in [RFC6130] for discarding a 2367 HELLO message on reception, a HELLO message received on an OLSRv2 2368 interface MUST be discarded before processing by [RFC6130] or this 2369 specification if it: 2371 o Has more than one Message TLV with Type = MPR_WILLING. 2373 o Has a message originator address, or a network address 2374 corresponding to an address object associated with an Address 2375 Block TLV with Type = LOCAL_IF, that is partially owned by this 2376 router. (Some of these cases are already excluded by [RFC6130].) 2378 o Includes any address object associated with an Address Block TLV 2379 with Type = LINK_STATUS or Type = OTHER_NEIGHB that overlaps the 2380 message's originator address. 2382 o Contains any address that will be processed by [RFC6130] that is 2383 associated, using the same or different address objects, with two 2384 different values of link metric with the same kind and direction 2385 using a TLV with Type = LINK_METRIC and Type Extension = 2386 LINK_METRIC_TYPE. This also applies to different addresses that 2387 are both of the OLSRv2 interface on which the HELLO message was 2388 received. 2390 o Contains any address object associated with an Address Block TLV 2391 with Type = MPR that is not also associated with an Address Block 2392 TLV with Type = LINK_STATUS and Value = SYMMETRIC (including using 2393 a different copy of that address object, in the same or a 2394 different Address Block). 2396 15.3.2. HELLO Message Usage 2398 HELLO messages are first processed as specified in [RFC6130]. That 2399 processing includes identifying (or creating) a Link Tuple and a 2400 Neighbor Tuple corresponding to the originator of the HELLO message 2401 (the "current Link Tuple" and the "current Neighbor Tuple"). After 2402 this, the following processing MUST also be performed if the HELLO 2403 message is received on an OLSRv2 interface and contains a TLV with 2404 Type = MPR_WILLING: 2406 1. If the HELLO message has a well-defined message originator 2407 address, i.e., has an element, or has zero or one 2408 network addresses associated with a TLV with Type = LOCAL_IF: 2410 1. Remove any Neighbor Tuple, other than the current Neighbor 2411 Tuple, with N_orig_addr = message originator address, taking 2412 any consequent action (including removing one or more Link 2413 Tuples) as specified in [RFC6130]. 2415 2. The current Link Tuple is then updated according to: 2417 1. Update L_in_metric and L_out_metric as described in 2418 Section 15.3.2.1; 2420 2. Update L_mpr_selector as described in Section 15.3.2.3. 2422 3. The current Neighbor Tuple is then updated according to: 2424 1. N_orig_addr := message originator address; 2426 2. Update N_in_metric and N_out_metric as described in 2427 Section 15.3.2.1; 2429 3. Update N_will_flooding and N_will_routing as described in 2430 Section 15.3.2.2; 2432 4. Update N_mpr_selector as described in Section 15.3.2.3. 2434 2. If there are any changes to the router's Information Bases, then 2435 perform the processing defined in Section 17. 2437 15.3.2.1. Updating Metrics 2439 For each address in a received HELLO message with an associated TLV 2440 with Type = LINK_STATUS and Value = HEARD or Value = SYMMETRIC, an 2441 incoming (to the message originator) link metric value is defined 2442 either using an associated TLV with Type = LINK_METRIC and Type 2443 Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2444 (link) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2446 For each address in a received HELLO message with an associated TLV 2447 with Type = LINK_STATUS and Value = SYMMETRIC, an outgoing (from the 2448 message originator) link metric value is defined either using an 2449 associated TLV with Type = LINK_METRIC and Type Extension = 2450 LINK_METRIC_TYPE that indicates the appropriate kind (link) and 2451 direction (outgoing) of metric, or as UNKNOWN_METRIC. 2453 For each address in a received HELLO message with an associated TLV 2454 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2455 an incoming (to the message originator) neighbor metric value is 2456 defined either using an associated TLV with Type = LINK_METRIC and 2457 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2458 (neighbor) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2460 For each address in a received HELLO message with an associated TLV 2461 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2462 an outgoing (from the message originator) neighbor metric value is 2463 defined either using an associated TLV with Type = LINK_METRIC and 2464 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2465 (neighbor) and direction (outgoing) of metric, or as UNKNOWN_METRIC. 2467 The link metric elements L_in_metric and L_out_metric in a Link Tuple 2468 are updated according to the following: 2470 o For any Link Tuple, L_in_metric MAY be set to any representable 2471 value, by a process outside this specification, at any time. 2472 L_in_metric MUST be so set whenever L_status becomes equal to 2473 HEARD or SYMMETRIC (if no other value is available then the value 2474 MAXIMUM_METRIC MUST be used). Setting L_in_metric MAY use 2475 information based on the receipt of a packet including a HELLO 2476 message that causes the creation or updating of the Link Tuple. 2478 o When, as specified in [RFC6130], a Link Tuple is updated (possibly 2479 immediately after being created) due to the receipt of a HELLO 2480 message, if L_status = SYMMETRIC, then L_out_metric is set equal 2481 to the incoming link metric for any included address of the 2482 interface on which the HELLO message was received. (Note that the 2483 rules for discarding HELLO messages in Section 15.3.1 make this 2484 value unambiguous.) If there is no such link metric then 2485 L_out_metric is set to UNKNOWN_METRIC. 2487 The neighbor metric elements N_in_metric and N_out_metric in a 2488 Neighbor Tuple are updated according to Section 17.3. 2490 The metric elements N2_in_metric and N2_out_metric in any 2-Hop Tuple 2491 updated as defined in [RFC6130] are updated to equal the incoming 2492 neighbor metric and outgoing neighbor metric, respectively, 2493 associated with the corresponding N2_2hop_addr. If there are no such 2494 metrics then these elements are set to UNKNOWN_METRIC. 2496 15.3.2.2. Updating Willingness 2498 N_will_flooding and N_will_routing in the current Neighbor Tuple are 2499 updated using the Message TLV with Type = MPR_WILLING (note that this 2500 must be present) as follows: 2502 o N_will_flooding := bits 0-3 of the value of that TLV; AND 2504 o N_will_routing := bits 4-7 of the value of that TLV. 2506 (Each being in the range 0 to 15, i.e., WILL_NEVER to WILL_ALWAYS.) 2508 15.3.2.3. Updating MPR Selector Status 2510 L_mpr_selector is updated as follows: 2512 1. If a router finds an address object representing any of its 2513 relevant local interface network addresses (i.e., those contained 2514 in the I_local_iface_addr_list of an OLSRv2 interface) with an 2515 associated Address Block TLV with Type = MPR and Value = FLOODING 2516 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2517 originating router has selected the receiving router as a 2518 flooding MPR) then, for the current Link Tuple: 2520 * L_mpr_selector := true. 2522 2. Otherwise (i.e., if no such address object and Address Block TLV 2523 was found), if a router finds an address object representing any 2524 of its relevant local interface network addresses (i.e., those 2525 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2526 with an associated Address Block TLV with Type = LINK_STATUS and 2527 Value = SYMMETRIC in the HELLO message, then for the current Link 2528 Tuple: 2530 * L_mpr_selector := false. 2532 N_mpr_selector is updated as follows: 2534 1. If a router finds an address object representing any of its 2535 relevant local interface network addresses (those contained in 2536 the I_local_iface_addr_list of an OLSRv2 interface) with an 2537 associated Address Block TLV with Type = MPR and Value = ROUTING 2538 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2539 originating router has selected the receiving router as a routing 2540 MPR) then, for the current Neighbor Tuple: 2542 * N_mpr_selector := true; 2544 * N_advertised := true. 2546 2. Otherwise (i.e., if no such address object and Address Block TLV 2547 was found), if a router finds an address object representing any 2548 of its relevant local interface network addresses (those 2549 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2550 with an associated Address Block TLV with Type = LINK_STATUS and 2551 Value = SYMMETRIC in the HELLO message, then for the current 2552 Neighbor Tuple: 2554 * N_mpr_selector := false; 2556 * The router MAY also set N_advertised := false. 2558 16. TC Messages 2560 This protocol defines, and hence owns, the TC Message Type (see 2561 Section 24). Thus, as specified in [RFC5444], this protocol 2562 generates and transmits all TC messages, receives all TC messages and 2563 is responsible for determining whether and how each TC message is to 2564 be processed (updating the Topology Information Base) and/or 2565 forwarded, according to this specification. 2567 16.1. TC Message Generation 2569 A TC message is a message as defined in [RFC5444]. A generated TC 2570 message MUST contain the following elements as defined in [RFC5444]: 2572 o A message originator address, recording this router's originator 2573 address. This MUST use a element. 2575 o element containing the message sequence number. 2577 o A element, containing TC_HOP_LIMIT. A router MAY 2578 use the same or different values of TC_HOP_LIMIT in its TC 2579 messages, see Section 5.4.7. 2581 o A element, containing zero, if the message 2582 contains a TLV with either Type = VALIDITY_TIME or Type = 2583 INTERVAL_TIME (as specified in [RFC5497]) indicating more than one 2584 time value according to distance. A TC message MAY contain such a 2585 element even if it does not need to. 2587 o A single Message TLV with Type := CONT_SEQ_NUM and Value := ANSN 2588 from the Neighbor Information Base. If the TC message is complete 2589 then this Message TLV MUST have Type Extension := COMPLETE, 2590 otherwise it MUST have Type Extension := INCOMPLETE. (Exception: 2591 a TC message MAY omit such a Message TLV if the TC message does 2592 not include any address objects with an associated Address Block 2593 TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY.) 2595 o A single Message TLV with Type := VALIDITY_TIME, as specified in 2596 [RFC5497]. If all TC messages are sent with the same hop limit 2597 then this TLV MUST have a value encoding the period T_HOLD_TIME. 2598 If TC messages are sent with different hop limits (more than one 2599 value of TC_HOP_LIMIT) then this TLV MUST specify times that vary 2600 with the number of hops appropriate to the chosen pattern of TC 2601 message hop limits, as specified in [RFC5497]; these times SHOULD 2602 be appropriate multiples of T_HOLD_TIME. The options included in 2603 [RFC5497] for representing zero and infinite times MUST NOT be 2604 used. 2606 o If the TC message is complete, all network addresses which are the 2607 N_orig_addr of a Neighbor Tuple with N_advertised = true, MUST be 2608 represented by address objects in one or more Address Blocks. If 2609 the TC message is incomplete then any such address objects MAY be 2610 included. At least one copy of each such address object that is 2611 included MUST be associated with an Address Block TLV with Type := 2612 NBR_ADDR_TYPE, and Value := ORIGINATOR, or with Value := 2613 ROUTABLE_ORIG if that address object is also to be associated with 2614 Value = ROUTABLE. 2616 o If the TC message is complete, all routable addresses which are in 2617 the N_neighbor_addr_list of a Neighbor Tuple with N_advertised = 2618 true MUST be represented by address objects in one or more Address 2619 Blocks. If the TC message is incomplete then any such address 2620 objects MAY be included. At least one copy of each such address 2621 object MUST be associated with an Address Block TLV with Type = 2622 NBR_ADDR_TYPE, and Value = ROUTABLE, or with Value = ROUTABLE_ORIG 2623 if also to be associated with Value = ORIGINATOR. At least one 2624 copy of each such address object MUST be associated with an 2625 Address Block TLV with Type = LINK_METRIC and Type Extension = 2626 LINK_METRIC_TYPE indicating an outgoing neighbor metric with value 2627 equal to the corresponding N_out_metric. 2629 o If the TC message is complete, all network addresses which are the 2630 AL_net_addr of a Local Attached Network Tuple MUST be represented 2631 by address objects in one or more Address Blocks. If the TC 2632 message is incomplete then any such address objects MAY be 2633 included. At least one copy of each such address object MUST be 2634 associated with an Address Block TLV with Type := GATEWAY, and 2635 Value := AN_dist. At least one copy of each such address object 2636 MUST be associated with an Address Block TLV with Type = 2637 LINK_METRIC and Type Extension = LINK_METRIC_TYPE indicating an 2638 outgoing neighbor metric equal to the corresponding AL_metric. 2640 A TC message MAY contain: 2642 o A single Message TLV with Type := INTERVAL_TIME, as specified in 2643 [RFC5497]. If all TC messages are sent with the same hop limit 2644 then this TLV MUST have a value encoding the period TC_INTERVAL. 2645 If TC messages are sent with different hop limits, then this TLV 2646 MUST specify times that vary with the number of hops appropriate 2647 to the chosen pattern of TC message hop limits, as specified in 2648 [RFC5497]; these times MUST be appropriate multiples of 2649 TC_INTERVAL. The options included in [RFC5497] for representing 2650 zero and infinite times MUST NOT be used. 2652 16.2. TC Message Transmission 2654 A router with one or more OLSRv2 interfaces, and with any Neighbor 2655 Tuples with N_advertised = true, or with a non-empty Local Attached 2656 Network Set MUST generate TC messages. A router which does not have 2657 such information to advertise MUST also generate "empty" TC messages 2658 for a period A_HOLD_TIME after it last generated a non-empty TC 2659 message. 2661 Complete TC messages are generated and transmitted periodically on 2662 all OLSRv2 interfaces, with a default interval between two 2663 consecutive TC message transmissions by the same router of 2664 TC_INTERVAL. 2666 TC messages MAY be generated in response to a change in the 2667 information which they are to advertise, indicated by a change in the 2668 ANSN in the Neighbor Information Base. In this case a router MAY 2669 send a complete TC message, and if so MAY re-start its TC message 2670 schedule. Alternatively, a router MAY send an incomplete TC message 2671 with at least the newly advertised network addresses (i.e., not 2672 previously, but now, an N_orig_addr or in an N_neighbor_addr_list in 2673 a Neighbor Tuple with N_advertised = true, or an AL_net_addr) in its 2674 Address Blocks, with associated Address Block TLV(s). Note that a 2675 router cannot report removal of advertised content using an 2676 incomplete TC message. 2678 When sending a TC message in response to a change of advertised 2679 network addresses, a router MUST respect a minimum interval of 2680 TC_MIN_INTERVAL between sending TC messages (complete or incomplete), 2681 and a maximum interval of TC_INTERVAL between sending complete TC 2682 messages. Thus a router MUST NOT send an incomplete TC message if 2683 within TC_MIN_INTERVAL of the next scheduled time to send a complete 2684 TC message. 2686 The generation of TC messages, whether scheduled or triggered by a 2687 change of contents, MAY be jittered as described in [RFC5148]. The 2688 values of MAXJITTER used MUST be: 2690 o TP_MAXJITTER for periodic TC message generation; 2692 o TT_MAXJITTER for responsive TC message generation. 2694 16.3. TC Message Processing 2696 On receiving a TC message on an OLSRv2 interface, the receiving 2697 router MUST then follow the processing and forwarding procedures, 2698 defined in Section 14. 2700 If the message is considered for processing (Section 14.2), then a 2701 router MUST first check if the message is invalid for processing by 2702 this router, as defined in Section 16.3.1. A router MAY make a 2703 similar check before considering a message for forwarding, it MUST 2704 make those aspects of the check that apply to elements in the Message 2705 Header. 2707 If the TC message is not invalid, then the TC Message Type specific 2708 processing, described in Section 16.3.2 MUST be applied. This will 2709 update its appropriate Interface Information Bases and its Router 2710 Information Base. Following this, if there are any changes in these 2711 Information Bases, then the processing in Section 17 MUST be 2712 performed. 2714 16.3.1. TC Message Discarding 2716 A received TC message is invalid for processing by this router if the 2717 message: 2719 o Has an address length specified in the Message Header that is not 2720 equal to the length of the addresses used by this router. 2722 o Does not include a message originator address and a message 2723 sequence number. 2725 o Does not include a hop count, and contains a multi-value TLV with 2726 Type = VALIDITY_TIME or Type = INTERVAL_TIME, as defined in 2727 [RFC5497]. 2729 o Does not have exactly one Message TLV with Type = VALIDITY_TIME. 2731 o Has more than one Message TLV with Type = INTERVAL_TIME. 2733 o Does not have a Message TLV with Type = CONT_SEQ_NUM and Type 2734 Extension = COMPLETE or Type Extension = INCOMPLETE, and contains 2735 at least one address object associated with an Address Block TLV 2736 with Type = NBR_ADDR_TYPE or Type = GATEWAY. 2738 o Has more than one Message TLV with Type = CONT_SEQ_NUM and Type 2739 Extension = COMPLETE or Type Extension = INCOMPLETE. 2741 o Has a message originator address that is partially owned by this 2742 router. 2744 o Includes any address object with a prefix length which is not 2745 maximal (equal to the address length, in bits), associated with an 2746 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ORIGINATOR 2747 or Value = ROUTABLE_ORIG. 2749 o Includes any address object that represents a non-routable 2750 address, associated with an Address Block TLV with Type = 2751 NBR_ADDR_TYPE and Value = ROUTABLE or Value = ROUTABLE_ORIG. 2753 o Includes any address object associated with an Address Block TLV 2754 with Type = NBR_ADDR_TYPE or Type = GATEWAY that also represents 2755 the message's originator address. 2757 o Includes any address object (including different copies of an 2758 address object, in the same or different Address Blocks) that is 2759 associated with an Address Block TLV with Type = NBR_ADDR_TYPE or 2760 Type = GATEWAY, that is also associated with more than one 2761 outgoing neighbor metric using a TLV with Type = LINK_METRIC and 2762 Type Extension = LINK_METRIC_TYPE. 2764 o Associates any address object (including different copies of an 2765 address object, in the same or different Address Blocks) with more 2766 than one single hop count value using one or more Address Block 2767 TLV(s) with Type = GATEWAY. 2769 o Associates any address object (including different copies of an 2770 address object, in the same or different Address Blocks) with 2771 Address Block TLVs with Type = NBR_ADDR_TYPE and Type = GATEWAY. 2773 A router MAY recognize additional reasons for identifying that a 2774 message is invalid. An invalid message MUST be silently discarded, 2775 without updating the router's Information Bases. 2777 Note that a router that acts inconsistently, for example rejecting TC 2778 messages "at random", may cause parts of the network to not be able 2779 to communicate with other parts of the network. It is RECOMMENDED 2780 that such "additional reasons for identifying that a message is 2781 invalid" be a consistent network-wide policy (e.g., as part of a 2782 security policy), implemented on all participating routers. 2784 16.3.2. TC Message Processing Definitions 2786 When, according to Section 14.2, a TC message is to be "processed 2787 according to its type", this means that: 2789 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2790 and Type Extension = COMPLETE, then processing according to 2791 Section 16.3.3 and then according to Section 16.3.4 is carried 2792 out. 2794 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2795 and Type Extension = INCOMPLETE, then only processing according to 2796 Section 16.3.3 is carried out. 2798 For the purposes of the TC message processing in Section 16.3.3 and 2799 Section 16.3.4: 2801 o "validity time" is calculated from a VALIDITY_TIME Message TLV in 2802 the TC message according to the specification in [RFC5497]. All 2803 information in the TC message has the same validity time. 2805 o "received ANSN" is defined as being the value of a Message TLV 2806 with Type = CONT_SEQ_NUM. 2808 o "associated metric value" is defined for any address in the TC 2809 message as being either the outgoing neighbor metric value 2810 indicated by a TLV with Type = LINK_METRIC and Type Extension = 2811 LINK_METRIC_TYPE that is associated with any address object in the 2812 TC message that is equal to that address, or as UNKNOWN_METRIC 2813 otherwise. (Note that the rules in Section 16.3.1 make this 2814 definition unambiguous.) 2816 o Comparisons of sequence numbers are carried out as specified in 2817 Section 21. 2819 16.3.3. Initial TC Message Processing 2821 The TC message is processed as follows: 2823 1. The Advertising Remote Router Set is updated according to 2824 Section 16.3.3.1. If the TC message is indicated as discarded in 2825 that processing then the following steps are not carried out. 2827 2. The Router Topology Set is updated according to Section 16.3.3.2. 2829 3. The Routable Address Topology Set is updated according to 2830 Section 16.3.3.3. 2832 4. The Attached Network Set is updated according to 2833 Section 16.3.3.4. 2835 16.3.3.1. Populating the Advertising Remote Router Set 2837 The router MUST update its Advertising Remote Router Set as follows: 2839 1. If there is an Advertising Remote Router Tuple with: 2841 * AR_orig_addr = message originator address; AND 2843 * AR_seq_number > received ANSN, 2845 then the TC message MUST be discarded. 2847 2. Otherwise: 2849 1. If there is no Advertising Remote Router Tuple such that: 2851 + AR_orig_addr = message originator address; 2853 then create an Advertising Remote Router Tuple with: 2855 + AR_orig_addr := message originator address. 2857 2. This Advertising Remote Router Tuple (existing or new) is 2858 then modified as follows: 2860 + AR_seq_number := received ANSN; 2862 + AR_time := current time + validity time. 2864 16.3.3.2. Populating the Router Topology Set 2866 The router MUST update its Router Topology Set as follows: 2868 1. For each address (henceforth advertised address) corresponding to 2869 one or more address objects with an associated Address Block TLV 2870 with Type = NBR_ADDR_TYPE and Value = ORIGINATOR or Value = 2871 ROUTABLE_ORIG, and that is not partially owned by this router, 2872 perform the following processing: 2874 1. If the associated metric is UNKNOWN_METRIC then remove any 2875 Router Topology Tuple such that: 2877 + TR_from_orig_addr = message originator address; AND 2879 + TR_to_orig_addr = advertised address, 2881 2. Otherwise if there is no Router Topology Tuple such that: 2883 + TR_from_orig_addr = message originator address; AND 2885 + TR_to_orig_addr = advertised address, 2887 then create a new Router Topology Tuple with: 2889 + TR_from_orig_addr := message originator address; 2891 + TR_to_orig_addr := advertised address. 2893 3. This Router Topology Tuple (existing or new) is then modified 2894 as follows: 2896 + TR_seq_number := received ANSN; 2898 + TR_metric := associated link metric; 2900 + TR_time := current time + validity time. 2902 16.3.3.3. Populating the Routable Address Topology Set 2904 The router MUST update its Routable Address Topology Set as follows: 2906 1. For each network address (henceforth advertised address) 2907 corresponding to one or more address objects with an associated 2908 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ROUTABLE 2909 or Value = ROUTABLE_ORIG, and that is not partially owned by this 2910 router, perform the following processing: 2912 1. If the associated metric is UNKNOWN_METRIC then remove any 2913 Routable Address Topology Tuple such that: 2915 + TA_from_orig_addr = message originator address; AND 2917 + TA_dest_addr = advertised address. 2919 2. Otherwise if there is no Routable Address Topology Tuple such 2920 that: 2922 + TA_from_orig_addr = message originator address; AND 2924 + TA_dest_addr = advertised address, 2926 then create a new Routable Address Topology Tuple with: 2928 + TA_from_orig_addr := message originator address; 2930 + TA_dest_addr := advertised address. 2932 3. This Routable Address Topology Tuple (existing or new) is 2933 then modified as follows: 2935 + TA_seq_number := received ANSN; 2937 + TA_metric := associated link metric; 2939 + TA_time := current time + validity time. 2941 16.3.3.4. Populating the Attached Network Set 2943 The router MUST update its Attached Network Set as follows: 2945 1. For each network address (henceforth attached address) 2946 corresponding to one or more address objects with an associated 2947 Address Block TLV with Type = GATEWAY, and that is not fully 2948 owned by this router, perform the following processing: 2950 1. If the associated metric is UNKNOWN_METRIC then remove any 2951 Attached Network Tuple such that: 2953 + AN_net_addr = attached address; AND 2955 + AN_orig_addr = message originator address. 2957 2. Otherwise if there is no Attached Network Tuple such that: 2959 + AN_net_addr = attached address; AND 2961 + AN_orig_addr = message originator address, 2963 then create a new Attached Network Tuple with: 2965 + AN_net_addr := attached address; 2967 + AN_orig_addr := message originator address. 2969 3. This Attached Network Tuple (existing or new) is then 2970 modified as follows: 2972 + AN_seq_number := received ANSN; 2974 + AN_dist := the Value of the associated GATEWAY TLV; 2976 + AN_metric := associated link metric; 2978 + AN_time := current time + validity time. 2980 16.3.4. Completing TC Message Processing 2982 The TC message is processed as follows: 2984 1. The Router Topology Set is updated according to Section 16.3.4.1. 2986 2. The Routable Address Topology Set is updated according to 2987 Section 16.3.4.2. 2989 3. The Attached Network Set is updated according to 2990 Section 16.3.4.3. 2992 16.3.4.1. Purging the Router Topology Set 2994 The Router Topology Set MUST be updated as follows: 2996 1. Any Router Topology Tuples with: 2998 * TR_from_orig_addr = message originator address; AND 3000 * TR_seq_number < received ANSN, 3002 MUST be removed. 3004 16.3.4.2. Purging the Routable Address Topology Set 3006 The Routable Address Topology Set MUST be updated as follows: 3008 1. Any Routable Address Topology Tuples with: 3010 * TA_from_orig_addr = message originator address; AND 3012 * TA_seq_number < received ANSN, 3014 MUST be removed. 3016 16.3.4.3. Purging the Attached Network Set 3018 The Attached Network Set MUST be updated as follows: 3020 1. Any Attached Network Tuples with: 3022 * AN_orig_addr = message originator address; AND 3024 * AN_seq_number < received ANSN, 3026 MUST be removed. 3028 17. Information Base Changes 3030 The changes described in the following sections MUST be carried out 3031 when any Information Base changes as indicated. 3033 17.1. Originator Address Changes 3035 If the router changes its originator address, then: 3037 1. If there is no Originator Tuple with: 3039 * O_orig_addr = old originator address 3041 then create an Originator Tuple with: 3043 * O_orig_addr := old originator address 3045 The Originator Tuple (existing or new) with: 3047 * O_orig_addr = new originator address 3049 is then modified as follows: 3051 * O_time := current time + O_HOLD_TIME 3053 17.2. Link State Changes 3055 The consistency of a Link Tuple MUST be maintained according to the 3056 following rules, in addition to those in [RFC6130]: 3058 o If L_status = HEARD or L_status = SYMMETRIC, then L_in_metric MUST 3059 be set (by a process outside this specification). 3061 o If L_status != SYMMETRIC, then set L_mpr_selector := false. 3063 o If L_out_metric = UNKNOWN_METRIC, then L_status MUST NOT equal 3064 SYMMETRIC; set L_SYM_time := EXPIRED if this would otherwise be 3065 the case. 3067 17.3. Neighbor State Changes 3069 The consistency of a Neighbor Tuple MUST be maintained according to 3070 the following rules, in addition to those in [RFC6130]: 3072 1. If N_symmetric = true, then N_in_metric MUST equal the minimum 3073 value of all L_in_metric of corresponding Link Tuples with 3074 L_status = SYMMETRIC and L_in_metric != UNKNOWN_METRIC. If there 3075 are no such Link Tuples then N_in_metric MUST equal 3076 UNKNOWN_METRIC. 3078 2. If N_symmetric = true, then N_out_metric MUST equal the minimum 3079 value of all L_out_metric of corresponding Link Tuples with 3080 L_status = SYMMETRIC and L_out_metric != UNKNOWN_METRIC. If 3081 there are no such Link Tuples then N_out_metric MUST equal 3082 UNKNOWN_METRIC. 3084 3. If N_symmetric = false, then N_flooding_mpr, N_routing_mpr, 3085 N_mpr_selector and N_advertised MUST all be equal to false. 3087 4. If N_mpr_selector = true, then N_advertised MUST be equal to 3088 true. 3090 5. If N_symmetric = true, N_out_metric != UNKNOWN_METRIC and 3091 N_mpr_selector = false, then a router MAY select N_advertised = 3092 true or N_advertised = false. The more neighbors that are 3093 advertised, the larger TC messages become, but the more 3094 redundancy is available for routing. A router SHOULD consider 3095 the nature of its network in making such a decision, and SHOULD 3096 avoid unnecessary changes in advertising status, which may result 3097 both in additional TC messages having to be sent by its 3098 neighbors, and in unnecessary changes to routing, which will have 3099 similar effects to other forms of topology changes in the MANET. 3101 17.4. Advertised Neighbor Changes 3103 The router MUST increment the ANSN in the Neighbor Information Base 3104 whenever: 3106 1. Any Neighbor Tuple changes its N_advertised value, or any 3107 Neighbor Tuple with N_advertised = true is removed. 3109 2. Any Neighbor Tuple with N_advertised = true changes its 3110 N_orig_addr, or has any routable address is added to or removed 3111 from N_neighbor_addr_list. 3113 3. Any Neighbor Tuple with N_advertised = true has N_out_metric 3114 changed. 3116 4. There is any change to the Local Attached Network Set. 3118 17.5. Advertising Remote Router Tuple Expires 3120 The Router Topology Set, the Routable Address Topology Set and the 3121 Attached Network Set MUST be changed when an Advertising Remote 3122 Router Tuple expires (AR_time is reached). The following changes are 3123 required before the Advertising Remote Router Tuple is removed: 3125 1. All Router Topology Tuples with: 3127 * TR_from_orig_addr = AR_orig_addr of the Advertising Remote 3128 Router Tuple 3130 are removed. 3132 2. All Routable Address Topology Tuples with: 3134 * TA_from_orig_addr = AR_orig_addr of the Advertising Remote 3135 Router Tuple 3137 are removed. 3139 3. All Attached Network Tuples with: 3141 * AN_orig_addr = AR_orig_addr of the Advertising Remote Router 3142 Tuple 3144 are removed. 3146 17.6. Neighborhood Changes and MPR Updates 3148 The sets of symmetric 1-hop neighbors selected as flooding MPRs and 3149 routing MPRs MUST satisfy the conditions defined in Section 18. To 3150 ensure this: 3152 1. The set of flooding MPRs of a router MUST be recalculated if: 3154 * A Link Tuple is added with L_status = SYMMETRIC and 3155 L_out_metric != UNKNOWN_METRIC, OR; 3157 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3158 UNKNOWN_METRIC is removed, OR; 3160 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3161 UNKNOWN_METRIC changes to having L_status = HEARD, L_status = 3162 LOST or L_out_metric = UNKNOWN_METRIC, OR; 3164 * A Link Tuple with L_status = HEARD or L_status = LOST changes 3165 to having L_status = SYMMETRIC and L_out_metric != 3166 UNKNOWN_METRIC, OR; 3168 * The flooding MPR selection process uses metric values (see 3169 Section 18.4) and the L_out_metric of any Link Tuple with 3170 L_status = SYMMETRIC changes, OR; 3172 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3173 true and N_out_metric != UNKNOWN_METRIC changes from 3174 WILL_NEVER to any other value, OR; 3176 * The N_will_flooding of a Neighbor Tuple with N_flooding_mpr = 3177 true changes to WILL_NEVER from any other value, OR; 3179 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3180 true, N_out_metric != UNKNOWN_METRIC, and N_flooding_mpr = 3181 false changes to WILL_ALWAYS from any other value, OR; 3183 * A 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC is added or 3184 removed, OR; 3186 * The flooding MPR selection process uses metric values (see 3187 Section 18.4) and the N2_out_metric of any 2-Hop Tuple 3188 changes. 3190 2. Otherwise, the set of flooding MPRs of a router MAY be 3191 recalculated if the N_will_flooding of a Neighbor Tuple with 3192 N_symmetric = true changes in any other way; it SHOULD be 3193 recalculated if N_flooding_mpr = false and this is an increase in 3194 N_will_flooding or if N_flooding_mpr = true and this is a 3195 decrease in N_will_flooding. 3197 3. The set of routing MPRs of a router MUST be recalculated if: 3199 * A Neighbor Tuple is added with N_symmetric = true and 3200 N_in_metric != UNKNOWN_METRIC, OR; 3202 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3203 UNKNOWN_METRIC is removed, OR; 3205 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3206 UNKNOWN_METRIC changes to having N_symmetric = false, OR; 3208 * A Neighbor Tuple with N_symmetric = false changes to having 3209 N_symmetric = true and N_in_metric != UNKNOWN_METRIC, OR; 3211 * The N_in_metric of any Neighbor Tuple with N_symmetric = true 3212 changes, OR; 3214 * The N_will_routing of a Neighbor Tuple with N_symmetric = true 3215 and N_in_metric != UNKNOWN_METRIC changes from WILL_NEVER to 3216 any other value, OR; 3218 * The N_will_routing of a Neighbor Tuple with N_routing_mpr = 3219 true changes to WILL_NEVER from any other value, OR; 3221 * The N_will_routing of a Neighbor Tuple with N_symmetric = 3222 true, N_in_metric != UNKNOWN_METRIC and N_routing_mpr = false 3223 changes to WILL_ALWAYS from any other value, OR; 3225 * A 2-Hop Tuple with N2_in_metric != UNKNOWN_METRIC is added or 3226 removed, OR; 3228 * The N2_in_metric of any 2-Hop Tuple changes. 3230 4. Otherwise, the set of routing MPRs of a router MAY be 3231 recalculated if the N_will_routing of a Neighbor Tuple with 3232 N_symmetric = true changes in any other way; it SHOULD be 3233 recalculated if N_routing_mpr = false and this is an increase in 3234 N_will_routing or if N_routing_mpr = true and this is a decrease 3235 in N_will_routing. 3237 If either set of MPRs of a router is recalculated, this MUST be as 3238 described in Section 18. 3240 17.7. Routing Set Updates 3242 The Routing Set MUST be updated, as described in Section 19, when 3243 changes in the Local Information Base, the Neighborhood Information 3244 Base or the Topology Information Base indicate a change (including of 3245 any potentially used outgoing neighbor metric values) of the known 3246 symmetric links and/or attached networks in the MANET, hence changing 3247 the Topology Graph. It is sufficient to consider only changes which 3248 affect at least one of: 3250 o The Local Interface Set for an OLSRv2 interface, if the change 3251 removes any network address in an I_local_iface_addr_list. In 3252 this case, unless the OLSRv2 interface is removed, it may not be 3253 necessary to do more than replace such network addresses, if used, 3254 by an alternative network address from the same 3255 I_local_iface_addr_list. 3257 o The Local Attached Set, if the change removes any AL_net_addr 3258 which is also an AN_net_addr. In this case it may not be 3259 necessary to do more than add Routing Tuples with R_dest_addr 3260 equal to that AN_net_addr. 3262 o The Link Set of any OLSRv2 interface, considering only Link Tuples 3263 which have, or just had, L_status = SYMMETRIC and L_out_metric != 3264 UNKNOWN_METRIC (including removal of such Link Tuples). 3266 o The Neighbor Set of the router, considering only Neighbor Tuples 3267 that have, or just had, N_symmetric = true and N_out_metric != 3268 UNKNOWN_METRIC, and do not have N_orig_addr = unknown. 3270 o The 2-Hop Set of any OLSRv2 interface, if used in the creation of 3271 the Routing Set, and if the change affects any 2-Hop Tuples with 3272 N2_out_metric != UNKNOWN_METRIC. 3274 o The Router Topology Set of the router. 3276 o The Routable Address Topology Set of the router. 3278 o The Attached Network Set of the router. 3280 18. Selecting MPRs 3282 Each router MUST select, from among its willing symmetric 1-hop 3283 neighbors, two subsets of these routers, as flooding and routing 3284 MPRs. This selection is recorded in the router's Neighbor Set, and 3285 reported in the router's HELLO messages. Routers MAY select their 3286 MPRs by any process that satisfies the conditions which follow, which 3287 may, but need not, use the organization of the data described. 3289 Routers can freely interoperate whether they use the same or 3290 different MPR selection algorithms. 3292 Only flooding MPRs forward control messages flooded through the 3293 MANET, thus effecting a flooding reduction, an optimization of the 3294 flooding mechanism, known as MPR flooding. Routing MPRs are used to 3295 effect a topology reduction in the MANET. (If no such reduction is 3296 required then a router can select all of its relevant neighbors as 3297 routing MPRs.) Consequently, while it is not essential that these 3298 two sets of MPRs are minimal, keeping the numbers of MPRs small 3299 ensures that the overhead of this protocol is kept to a minimum. 3301 18.1. Overview 3303 MPRs are selected according to the following steps, defined in the 3304 following sections: 3306 o A data structure known as a Neighbor Graph is defined. 3308 o The properties of an MPR Set derived from a Neighbor Graph are 3309 defined. Any algorithm that creates an MPR Set that satisfies 3310 these properties is a valid MPR selection algorithm. An example 3311 algorithm that creates such an MPR Set is given in Appendix B. 3313 o How to create a Neighbor Graph for each interface based on the 3314 corresponding Interface Information Base is defined, and how to 3315 combine the resulting MPR Sets to determine the router's flooding 3316 MPRs and record those in the router's Neighbor Set. 3318 o How to create a single Neighbor Graph based on all Interface 3319 Information Bases and the Neighbor Information Base is defined, 3320 and how to record the resulting MPR Set as the router's routing 3321 MPRs in the router's Neighbor Set. 3323 o A specification as to when MPRs MUST be calculated is given. 3325 When a router selects its MPRs it MAY consider any characteristics of 3326 its neighbors that it is aware of. In particular it SHOULD consider 3327 the willingness of the neighbor, as recorded by the corresponding 3328 N_will_flooding or N_will_routing value, as appropriate, preferring 3329 neighbors with higher values. (Note that willingness values equal to 3330 WILL_NEVER and WILL_ALWAYS are always considered, as described.) 3331 However, a router MAY consider other characteristics to have a 3332 greater significance. 3334 Each router MAY select its flooding and routing MPRs independently 3335 from each other, or coordinate its selections. A router MAY make its 3336 MPR selections independently of the MPR selection by other routers, 3337 or it MAY, for example, give preference to routers that either are, 3338 or are not, already selected as MPRs by other routers. 3340 18.2. Neighbor Graph 3342 A Neighbor Graph is a structure defined here as consisting of sets N1 3343 and N2 and some associated metric and willingness values. Elements 3344 of set N1 represent willing symmetric 1-hop neighbors, and elements 3345 of set N2 represent addresses of a symmetric 2-hop neighbor. 3347 A Neighbor Graph has the following properties: 3349 o It contains two disjoint sets N1 and N2. 3351 o For each element x in N1 there is an associated willingness value 3352 W(x) such that WILL_NEVER < W(x) <= WILL_ALWAYS. 3354 o For each element x in N1 there is an associated metric d1(x) > 0. 3356 o For some elements y in N2 there is an associated metric d1(y) > 0. 3357 (Other elements y in N2 have undefined d1(y), this may be 3358 considered to be infinite.) 3360 o For each element x in N1 there is a subset N2(x) of elements of 3361 N2; this subset may be empty. For each x in N1 and each y in 3362 N2(x) there is an associated metric d2(x,y) > 0. (For other x in 3363 N1 and y in N2, d2(x,y) is undefined, and may be considered 3364 infinite.) 3366 o N2 is equal to the union of all the N2(x) for all x in N1, i.e. 3367 for each y in N2 there is at least one x in N1 such that y is in 3368 N2(x). 3370 It is convenient to also define: 3372 o For each y in N2 the set N1(y) that contains x in N1 if and only 3373 if y is in N2(x). From the final property above, N1(y) is not 3374 empty. 3376 o For each x in N1 and y in N2, if d2(x,y) is defined then d(x,y) := 3377 d1(x)+d2(x,y), otherwise d(x,y) is not defined. (Thus d(x,y) is 3378 defined if y is in N2(x), or equivalently if x is in N1(y).) 3380 o For any subset S of N1, and for each y in N2, the metric d(y,S) is 3381 the minimum value of d1(y), if defined, and of all d(x,y) for x in 3382 N1(y) and in S. If there are no such metrics to take the minimum 3383 value of, then d(y,S) is undefined (may be considered to be 3384 infinite). From the final property above, d(y,N1) is defined for 3385 all y. 3387 18.3. MPR Properties 3389 Given a Neighbor Graph as defined in Section 18.2, an MPR Set for 3390 that Neighbor Graph is a subset M of the set N1 that satisfies the 3391 following properties: 3393 o If x in N1 has W(x) = WILL_ALWAYS then x is in M. 3395 o For any y in N2 that does not have a defined d1(y), there is at 3396 least one element in M that is also in N1(y). This is equivalent 3397 to the requirement that d(y,M) is defined. 3399 o For any y in N2, d(y,M) = d(y,N1). 3401 These two properties correspond first to that the MPR Set consists of 3402 a set of symmetric 1-hop neighbors that cover all the symmetric 2-hop 3403 neighbors, and second that they do so retaining a minimum distance 3404 route (1-hop, if present, or 2-hop) to each symmetric 2-hop neighbor. 3406 Note that if M is an MPR Set, then so is any subset of N1 that 3407 contains M, and also that N1 is always an MPR Set. An MPR Set may be 3408 empty, but cannot be empty if N2 contains any elements y that do not 3409 have a defined d1(y). 3411 18.4. Flooding MPRs 3413 Whenever flooding MPRs are to be calculated, an implementation MUST 3414 determine and record a set of flooding MPRs that is equivalent to one 3415 calculated as described in this section. 3417 The calculation of flooding MPRs need not use link metrics, or 3418 equivalently may use link metrics with a fixed value, here taken to 3419 be 1. However, links with unknown metric (L_out_metric = 3420 UNKNOWN_METRIC) MUST NOT be used even if link metrics are otherwise 3421 not used. 3423 Routers MAY make individual decisions as to whether to use link 3424 metrics for the calculation of flooding MPRs. A router MUST use the 3425 same approach to the choice of whether to use link metrics for all 3426 links, i.e., in the cases indicated by A or B, the same choice MUST 3427 be made in each case. 3429 For each OLSRv2 interface (the "current interface") define a Neighbor 3430 Graph as defined in Section 18.2 according to the following: 3432 o Define a reachable Link Tuple to be a Link Tuple in the Link Set 3433 for the current interface with L_status = SYMMETRIC and 3434 L_out_metric != UNKNOWN_METRIC. 3436 o Define an allowed Link Tuple to be a reachable Link Tuple whose 3437 corresponding Neighbor Tuple has N_will_flooding > WILL_NEVER. 3439 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3440 for the current interface for which N2_out_metric != 3441 UNKNOWN_METRIC and there is an allowed Link Tuple with 3442 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 3444 o Define an element of N1 for each allowed Link Tuple. This then 3445 defines the corresponding Link Tuple for each element of N1 and 3446 the corresponding Neighbor Tuple for each element of N1, being the 3447 Neighbor Tuple corresponding to that Link Tuple. 3449 o For each element x in N1, define W(x) := N_will_flooding of the 3450 corresponding Neighbor Tuple. 3452 o For each element x in N1, define d1(x) as either: 3454 A. L_out_metric of the corresponding Link Tuple, OR; 3456 B. 1. 3458 o Define an element of N2 for each network address that is the 3459 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3460 defines the corresponding address for each element of N2. 3462 o For each element y in N2, if the corresponding address is in the 3463 N_neighbor_addr_list of a Neighbor Tuple that corresponds to one 3464 or more reachable Link Tuples, then define d1(y) as either: 3466 A. the minimum value of the L_out_metric of those Link Tuples, 3467 OR; 3469 B. 1. 3471 Otherwise d1(y) is not defined. In the latter case, where d1(y) 3472 := 1, all such y in N2 may instead be removed from N2. 3474 o For each element x in N1, define N2(x) as the set of elements y in 3475 N2 whose corresponding address is the N2_2hop_addr of an allowed 3476 2-Hop Tuple that has N2_neighbor_iface_addr_list = 3477 L_neighbor_iface_addr_list of the Link Tuple corresponding to x. 3478 For all such x and y, define d2(x,y) as either: 3480 A. N2_out_metric of that 2-Hop Tuple, OR; 3482 B. 1. 3484 It is up to an implementation to decide how to label each element of 3485 N1 or N2. For example an element of N1 may be labeled with one or 3486 more addresses from the corresponding L_neighbor_iface_addr_list, or 3487 with a pointer or reference to the corresponding Link Tuple. 3489 Using these Neighbor Graphs, flooding MPRs are selected and recorded 3490 by: 3492 o For each OLSRv2 interface, determine an MPR Set as specified in 3493 Section 18.3. 3495 o A Neighbor Tuple represents a flooding MPR and has N_flooding_mpr 3496 := true (otherwise N_flooding_mpr := false) if and only if that 3497 Neighbor Tuple corresponds to an element in an MPR Set created for 3498 any interface as described above. That is, the overall set of 3499 flooding MPRs is the union of the sets of flooding MPRs for all 3500 OLSRv2 interfaces. 3502 A router MAY select its flooding MPRs for each OLSRv2 interface 3503 independently, or it MAY coordinate its MPR selections across its 3504 OLSRv2 interfaces, as long as the required condition is satisfied for 3505 each OLSRv2 interface. One such coordinated approach is to process 3506 the OLSRv2 interfaces sequentially, and for each OLSRv2 interface 3507 start with flooding MPRs selected (and not removable) if the neighbor 3508 has been already selected as an MPR for an OLSRv2 interface that has 3509 already been processed. The algorithm specified in Appendix B can be 3510 used in this way. 3512 18.5. Routing MPRs 3514 Whenever routing MPRs are to be calculated, an implementation MUST 3515 determine and record a set of routing MPRs that is equivalent to one 3516 calculated as described in this section. 3518 Define a single Neighbor Graph as defined in Section 18.2 according 3519 to the following: 3521 o Define a reachable Neighbor Tuple to be a Neighbor Tuple with 3522 N_symmetric = true and N_in_metric != UNKNOWN_METRIC. 3524 o Define an allowed Neighbor Tuple to be a reachable Neighbor Tuple 3525 with N_will_routing > WILL_NEVER. 3527 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3528 for any OLSRv2 interface with N2_in_metric != UNKNOWN_METRIC and 3529 for which there is an allowed Neighbor Tuple with 3530 N_neighbor_addr_list containing N2_neighbor_iface_addr_list. 3532 o Define an element of N1 for each allowed Neighbor Tuple. This 3533 then defines the corresponding Neighbor Tuple for each element of 3534 N1. 3536 o For each element x in N1, define W(x) := N_will_routing of the 3537 corresponding Neighbor Tuple. 3539 o For each element x in N1, define d1(x) := N_in_metric of the 3540 corresponding Neighbor Tuple. 3542 o Define an element of N2 for each network address that is the 3543 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3544 defines the corresponding address for each element of N2. 3546 o For each element y in N2, if the corresponding address is in the 3547 N_neighbor_addr_list of a reachable Neighbor Tuple, then define 3548 d1(y) to be the N_in_metric of that Neighbor Tuple, otherwise 3549 d1(y) is not defined. 3551 o For each element x in N1, define N2(x) as the set of elements y in 3552 N2 whose corresponding address is the N2_2hop_addr of an allowed 3553 2-Hop Tuple that has N2_neighbor_iface_addr_list contained in 3554 N_neighbor_addr_list of the Neighbor Tuple corresponding to x. 3555 For all such x and y, define d2(x,y) := N2_out_metric of that 3556 2-Hop Tuple. 3558 It is up to an implementation to decide how to label each element of 3559 N1 or N2. For example an element of N1 may be labeled with one or 3560 more addresses from the corresponding N_neighbor_addr_list, or with a 3561 pointer or reference to the corresponding Neighbor Tuple. 3563 Using these Neighbor Graphs, routing MPRs are selected and recorded 3564 according to the following: 3566 o Determine an MPR Set as specified in Section 18.3. 3568 o A Neighbor Tuple represents a routing MPR and has N_routing_mpr := 3569 true (otherwise N_routing_mpr := false) if and only if that 3570 Neighbor Tuple corresponds to an element in the MPR Set created as 3571 described above. 3573 18.6. Calculating MPRs 3575 A router MUST recalculate each of its sets of MPRs whenever the 3576 currently selected set of MPRs does not still satisfy the required 3577 conditions. It MAY recalculate its MPRs if the current set of MPRs 3578 is still valid, but could be more efficient. Sufficient conditions 3579 to recalculate a router's sets of MPRs are given in Section 17.6. 3581 19. Routing Set Calculation 3583 The Routing Set of a router is populated with Routing Tuples that 3584 represent paths from that router to all destinations in the network. 3585 These paths are calculated based on the Network Topology Graph, which 3586 is constructed from information in the Information Bases, obtained 3587 via HELLO and TC message exchange. 3589 Changes to the Routing Set do not require any messages to be 3590 transmitted. The state of the Routing Set SHOULD, however, be 3591 reflected in the IP routing table by adding and removing entries from 3592 that routing table as appropriate. Only appropriate Routing Tuples 3593 (in particular only those that represent local links or paths to 3594 routable addresses) need be reflected in the IP routing table. 3596 19.1. Network Topology Graph 3598 The Network Topology Graph is formed from information from the 3599 router's Local Interface Set, Link Sets for OLSRv2 interfaces, 3600 Neighbor Set, Router Topology Set, Routable Address Topology Set and 3601 Attached Network Set. The Network Topology Graph MAY also use 3602 information from the router's 2-Hop Sets for OLSRv2 interfaces. The 3603 Network Topology Graph forms the router's topological view of the 3604 network in form of a directed graph. Each edge in that graph has a 3605 metric value. The Network Topology Graph has a "backbone" (within 3606 which minimum total metric routes will be constructed) containing the 3607 following edges: 3609 o Edges X -> Y for all possible Y, and one X per Y, such that: 3611 * Y is the N_orig_addr of a Neighbor Tuple; AND 3613 * N_orig_addr is not unknown; 3615 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3616 AND 3618 * There is a Link Tuple with L_status = SYMMETRIC and 3619 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3620 and this Local Interface Tuple correspond to it. A network 3621 address from L_neighbor_iface_addr_list will be denoted R in 3622 this case. 3624 It SHOULD be preferred, where possible, to select R = S and X from 3625 the Local Interface Tuple corresponding to the Link Tuple from 3626 which R was selected. The metric for such an edge is the 3627 corresponding N_out_metric. 3629 o All edges W -> U such that: 3631 * W is the TR_from_orig_addr of a Router Topology Tuple; AND 3633 * U is the TR_to_orig_addr of the same Router Topology Tuple. 3635 The metric of such an edge is the corresponding TR_metric. 3637 The Network Topology Graph is further "decorated" with the following 3638 edges. If a network address S, V, Z or T equals a network address Y 3639 or W, then the edge terminating in the network address S, V, Z or T 3640 MUST NOT be used in any path. 3642 o Edges X -> S for all possible S, and one X per S, such that: 3644 * S is in the N_neighbor_addr_list of a Neighbor Tuple; AND 3646 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3647 AND 3649 * There is a Link Tuple with L_status = SYMMETRIC and 3650 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3651 and this Local Interface Tuple correspond to it. A network 3652 address from L_neighbor_iface_addr_list will be denoted R in 3653 this case. 3655 It SHOULD be preferred, where possible, to select R = S and X from 3656 the Local Interface Tuple corresponding to the Link Tuple from 3657 which R was selected. The metric for such an edge is the 3658 corresponding N_out_metric. 3660 o All edges W -> V such that: 3662 * W is the TA_from_orig_addr of a Routable Address Topology 3663 Tuple; AND 3665 * V is the TA_dest_addr of the same Routable Address Topology 3666 Tuple. 3668 The metric for such an edge is the corresponding TA_metric. 3670 o All edges W -> T such that: 3672 * W is the AN_orig_addr of an Attached Network Tuple; AND 3674 * T is the AN_net_addr of the same Attached Network Tuple. 3676 The metric for such an edge is the corresponding AN_metric. 3678 o (OPTIONAL) All edges Y -> Z such that: 3680 * Z is a routable address and is the N2_2hop_addr of a 2-Hop 3681 Tuple with N2_out_metric != UNKNOWN_METRIC; AND 3683 * Y is the N_orig_addr of the corresponding Neighbor Tuple; AND 3685 * This Neighbor Tuple has N_will_routing not equal to WILL_NEVER. 3687 A path terminating with such an edge MUST NOT be used in 3688 preference to any other path. The metric for such an edge is the 3689 corresponding N2_out_metric. 3691 Any part of the Topology Graph which is not connected to a local 3692 network address X is not used. Only one selection X SHOULD be made 3693 from each I_local_iface_addr_list, and only one selection R SHOULD be 3694 made from any L_neighbor_iface_addr_list. All edges have a hop count 3695 of 1, except edges W -> T that have a hop count of the corresponding 3696 value of AN_dist. 3698 19.2. Populating the Routing Set 3700 The Routing Set MUST contain the shortest paths for all destinations 3701 from all local OLSRv2 interfaces using the Network Topology Graph. 3702 This calculation MAY use any algorithm, including any means of 3703 choosing between paths of equal total metric. (In the case of two 3704 paths of equal total metric but differing hop counts, the path with 3705 the lower hop count SHOULD be used.) 3707 Using the notation of Section 19.1, initially "backbone" paths using 3708 only edges X -> Y and W -> U need be constructed (using a minimum 3709 distance algorithm). Then paths using only a final edge of the other 3710 types may be added. These MUST NOT replace backbone paths with the 3711 same destination (and paths terminating in an edge Y -> Z SHOULD NOT 3712 replace paths with any other form of terminating edge). 3714 Each path will correspond to a Routing Tuple. These will be of two 3715 types. The first type will represent single edge paths, of type X -> 3716 S or X -> Y, by: 3718 o R_local_iface_addr := X; 3720 o R_next_iface_addr := R; 3722 o R_dest_addr := S or Y; 3724 o R_dist := 1; 3726 o R_metric := edge metric, 3728 where R is as defined in Section 19.1 for these types of edges. 3730 The second type will represent a multiple edge path, which will 3731 always have first edge of type X -> Y, and will have final edge of 3732 type W -> U, W -> V, W -> T or Y -> Z. The Routing Tuple will be: 3734 o R_local_iface_addr := X; 3736 o R_next_iface_addr := Y; 3738 o R_dest_addr := U, V, T or Z; 3740 o R_dist := the total hop count of all edges in the path; 3742 o R_metric := the total metric of all edges in the path. 3744 Finally, Routing Tuples of the second type whose R_dest_addr is not 3745 routable MAY be discarded. 3747 An example algorithm for calculating the Routing Set of a router is 3748 given in Appendix C. 3750 20. Proposed Values for Parameters 3752 This protocol uses all parameters defined in [RFC6130] and additional 3753 parameters and defined in this specification. All but one 3754 (RX_HOLD_TIME) of these additional parameters are router parameters 3755 as defined in [RFC6130]. The proposed values of the additional 3756 parameters defined in the following sections are appropriate to the 3757 case where all parameters (including those defined in [RFC6130]) have 3758 a single value. Proposed values for parameters defined in [RFC6130] 3759 are given in that specification. 3761 The following proposed values are based on experience with [RFC3626] 3762 deployments (such as documented in [McCabe]), and are considered 3763 typical. They can be changed to accommodate different deployment 3764 requirements - for example, a network with capacity-limited network 3765 interfaces would be expected to use greater values for message 3766 intervals, whereas a highly mobile network would be expected to use 3767 lower values for message intervals. When determining these values, 3768 the constraints specified in Section 5 MUST be respected. 3770 Note that routers in a MANET need not all use the same set of 3771 parameters, and those parameters that are indicated as interface 3772 parameters need not be the same on all OLSRv2 interfaces of a single 3773 router. 3775 20.1. Local History Time Parameters 3777 o O_HOLD_TIME := 30 seconds 3779 20.2. Message Interval Parameters 3781 o TC_INTERVAL := 5 seconds 3783 o TC_MIN_INTERVAL := TC_INTERVAL/4 3785 20.3. Advertised Information Validity Time Parameters 3787 o T_HOLD_TIME := 3 x TC_INTERVAL 3789 o A_HOLD_TIME := T_HOLD_TIME 3791 20.4. Received Message Validity Time Parameters 3793 o RX_HOLD_TIME := 30 seconds 3795 o P_HOLD_TIME := 30 seconds 3797 o F_HOLD_TIME := 30 seconds 3799 20.5. Jitter Time Parameters 3801 o TP_MAXJITTER := HP_MAXJITTER 3803 o TT_MAXJITTER := HT_MAXJITTER 3805 o F_MAXJITTER := TT_MAXJITTER 3807 20.6. Hop Limit Parameter 3809 o TC_HOP_LIMIT := 255 3811 20.7. Willingness Parameter 3813 o WILL_FLOODING := WILL_DEFAULT 3815 o WILL_ROUTING := WILL_DEFAULT 3817 21. Sequence Numbers 3819 Sequence numbers are used in this specification for the purpose of 3820 discarding "old" information, i.e., messages received out of order. 3821 However with a limited number of bits for representing sequence 3822 numbers, wrap-around (that the sequence number is incremented from 3823 the maximum possible value to zero) will occur. To prevent this from 3824 interfering with the operation of this protocol, the following MUST 3825 be observed when determining the ordering of sequence numbers. 3827 The term MAXVALUE designates in the following one more than the 3828 largest possible value for a sequence number. For a 16 bit sequence 3829 number (as are those defined in this specification) MAXVALUE is 3830 65536. 3832 The sequence number S1 is said to be "greater than" the sequence 3833 number S2 if: 3835 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 3837 o S2 > S1 AND S2 - S1 > MAXVALUE/2 3839 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 3840 cannot be determined. In this case, which should not occur, either 3841 ordering may be assumed. 3843 Thus when comparing two messages, it is possible - even in the 3844 presence of wrap-around - to determine which message contains the 3845 most recent information. 3847 22. Extensions 3849 An extension to this protocol will need to interact with this 3850 specification, and possibly also with [RFC6130]. This protocol is 3851 designed to permit such interactions, in particular: 3853 o Through accessing, and possibly extending, the information in the 3854 Information Bases. All updates to the elements specified in this 3855 specification are subject to the normative constraints specified 3856 in [RFC6130] and Appendix A. Note that the processing specified 3857 in this document ensures that these constraints are satisfied. 3859 o Through accessing an outgoing message prior to it being 3860 transmitted over any OLSRv2 interface, and to add information to 3861 it as specified in [RFC5444]. This MAY include Message TLVs 3862 and/or network addresses with associated Address Block TLVs. 3863 (Network addresses without new associated TLVs SHOULD NOT be added 3864 to messages.) This may, for example, be to allow a security 3865 protocol, as suggested in Section 23, to add a TLV containing a 3866 cryptographic signature to the message. 3868 o Through accessing an incoming message, and potentially discarding 3869 it prior to processing by this protocol. This may, for example, 3870 allow a security protocol, as suggested in Section 23, to perform 3871 verification of message signatures and prevent processing and/or 3872 forwarding of unverifiable messages by this protocol. 3874 o Through accessing an incoming message after it has been completely 3875 processed by this protocol. In particular, this may allow a 3876 protocol which has added information, by way of inclusion of 3877 appropriate TLVs, or of network addresses associated with new 3878 TLVs, access to such information after appropriate updates have 3879 been recorded in the Information Bases in this protocol. 3881 o Through requesting that a message be generated at a specific time. 3882 In that case, message generation MUST still respect the 3883 constraints in [RFC6130] and Section 5.4.3. 3885 23. Security Considerations 3887 As a proactive routing protocol, this protocol is a potential target 3888 for various attacks. This section presents the envisioned security 3889 architecture for OLSRv2, and gives guidelines on how to provide 3890 integrity, confidentiality, and integration into external routing 3891 domains. 3893 23.1. Security Architecture 3895 OLSRv2 integrates into the architecture specified in Appendix A of 3896 [RFC5444], in [RFC5498], and in Section 16 of [RFC6130], the latter 3897 by using and extending its messages and Information Bases. 3899 As part of this architecture, OLSRv2, and [RFC6130], recognize that 3900 there may be external reasons for rejecting messages that would be 3901 considered "badly formed" or "insecure", e.g., if a digital signature 3902 included in a message by an external mechanism cannot be verified. 3903 This architecture allows options as to whether and how to implement 3904 security features, reflecting the situation that MANET routing 3905 protocol deployment domains have varying security requirements, 3906 ranging from "practically unbreakable" to "virtually none". This 3907 approach allows MANET routing protocol specifications to remain 3908 generic, with extensions to them, and/or extensions to the 3909 multiplexing and demultiplexing process described in Appendix A of 3910 [RFC5444], providing security mechanisms appropriate to a given 3911 deployment domain. 3913 The following sections provide guidelines how to provide integrity, 3914 confidentiality, and integration with external routing domains in 3915 such extensions. 3917 23.2. Integrity 3919 Each router injects topological information into the network by 3920 transmitting HELLO messages and, for some routers, also TC messages. 3921 If some routers for some reason, malice or malfunction, inject 3922 invalid control traffic, network integrity may be compromised. 3923 Therefore, message, or packet, authentication is recommended. 3925 Different such situations may occur, for example: 3927 1. A router generates TC messages, advertising links to non-neighbor 3928 routers; 3930 2. A router generates TC messages, pretending to be another router; 3932 3. A router generates HELLO messages, advertising non-neighbor 3933 routers; 3935 4. A router generates HELLO messages, pretending to be another 3936 router; 3938 5. A router forwards altered control messages; 3940 6. A router does not forward control messages; 3942 7. A router does not select multipoint relays correctly; 3944 8. A router forwards broadcast control messages unaltered, but does 3945 not forward unicast data traffic; 3947 9. A router "replays" previously recorded control traffic from 3948 another router. 3950 Authentication of the originator router for control messages (for 3951 situations 2, 4 and 5), and of the individual links announced in the 3952 control messages (for situations 1 and 3), may be used as a 3953 countermeasure. However to prevent routers from repeating old (and 3954 correctly authenticated) information (situation 9) temporal 3955 information (a timestamp) is required, allowing a router to 3956 positively identify such replayed messages. 3958 In general, digital signatures and other required security 3959 information may be transmitted within the HELLO and TC messages, or 3960 within a packet header, using the TLV mechanism. Either option 3961 permits "secured" and "unsecured" routers to coexist in the same 3962 network, if desired. 3964 An important consideration is that all control messages (HELLO 3965 messages and TC messages) are transmitted to all routers in the 1-hop 3966 neighborhood and some control messages (TC messages) are flooded to 3967 all routers in the network. This is done in a packet that is 3968 transmitted to all routers in the 1-hop neighborhood, the current set 3969 of which may not be known. Thus, a control message, or packet, used 3970 by this protocol is always contained in a transmission destined for 3971 multiple destinations, and it is important that the authentication 3972 mechanism employed permits any receiving router to validate the 3973 authenticity of a message or packet. 3975 [RFC6622] specifies a common exchange format for cryptographic 3976 information in the form of Packet TLVs, Message TLVs, and Address 3977 Block TLVs, as specified in [RFC5444]. These may be used (and 3978 shared) among MANET routing protocol security extensions. In 3979 particular, [RFC6622] specifies the format of TLVs for containing 3980 Integrity Check Values (ICVs), i.e., signatures, for providing 3981 integrity, as well as TLVs for containing temporal information for 3982 preventing replay attacks. [RFC6622] specifies registries for using 3983 different ciphers and formats of temporal information. Failure to 3984 verify an ICV included can be used as a reason to reject an incoming 3985 message or packet as "invalid", according to Section 12.1 of 3986 [RFC6130], and according to Section 16.3.1 of this specification, 3987 when using the multiplexing and demultiplexing process described in 3988 Appendix A of [RFC5444]. 3990 Any security extension that uses [RFC6622] must specify how to insert 3991 IVCs in generated messages, how to verify incoming messages, and to 3992 reject "insecure" messages (i.e., messages without an ICV or with an 3993 ICV that cannot be verified) when operating in a secure mode. 3994 Different MANET deployments may, as a result of their purpose for 3995 which they are used and the possibility and nature of their 3996 configuration, require different ICV algorithms and timestamps, and 3997 thus a security extension may use any of the different options 3998 provided in [RFC6622]. 4000 23.3. Confidentiality 4002 OLSRv2 periodically MPR floods topological information to all routers 4003 in the network. Hence, if used in an unprotected network, in 4004 particular an unprotected wireless network, the network topology is 4005 revealed to anyone who successfully listens to the control messages. 4006 This information may serve an attacker to acquire details about the 4007 topology, and therefore to initiate more effective attacks against 4008 routers in the routing domain e.g., by spoofing addresses of routers 4009 in the network and attracting traffic for these addresses. Note that 4010 this is independent of the data traffic, and purely protects the 4011 control traffic, i.e., information about the network topology. 4013 In situations where the confidentiality of the network topology is of 4014 importance, regular cryptographic techniques, such as use of OLSRv2 4015 multicast control packets encrypted using IPsec (e.g., with a shared 4016 secret key), can be applied to ensure that control traffic can be 4017 read and interpreted by only those authorized to do so. 4018 Alternatively, a security extension may specify a mechanism to 4019 provide confidentiality for control messages and/or packets. 4020 However, unless the information about the network topology itself is 4021 confidential, integrity of control messages (as specified in 4022 Section 23.2) is sufficient to admit only trusted routers (i.e. 4023 routers with valid credentials) to the network. 4025 23.4. Interaction with External Routing Domains 4027 This protocol provides a basic mechanism for injecting external 4028 routing information into this protocol's routing domain. Routing 4029 information can also be extracted from this protocol's Information 4030 Bases, in particular the Routing Set, and injected into an external 4031 routing domain, if the routing protocol governing that routing domain 4032 permits this. 4034 When operating routers connecting a routing domain using this 4035 protocol to an external routing domain, care MUST be taken not to 4036 allow potentially insecure and untrustworthy information to be 4037 injected from this routing domain to an external routing domain. 4038 Care MUST also be taken to validate the correctness of information 4039 prior to it being injected, so as to avoid polluting routing tables 4040 with invalid information. 4042 A recommended way of extending connectivity from an external routing 4043 domain to this routing domain, which is routed using this protocol, 4044 is to assign an IP prefix (under the authority of the routers/ 4045 gateways connecting this routing domain with the external routing 4046 domain) exclusively to this routing domain, and to configure the 4047 gateways to advertise routes for that IP prefix into the external 4048 routing domain. 4050 24. IANA Considerations 4052 This specification defines one Message Type, which must be allocated 4053 from the "Message Types" repository of [RFC5444], two Message TLV 4054 Types, which must be allocated from the "Message TLV Types" 4055 repository of [RFC5444], and four Address Block TLV Types, which must 4056 be allocated from the "Address Block TLV Types" repository of 4057 [RFC5444]. 4059 24.1. Expert Review: Evaluation Guidelines 4061 For the registries where an Expert Review is required, the designated 4062 expert SHOULD take the same general recommendations into 4063 consideration as are specified by [RFC5444]. 4065 24.2. Message Types 4067 This specification defines one Message Type, to be allocated from the 4068 0-223 range of the "Message Types" namespace defined in [RFC5444], as 4069 specified in Table 8. 4071 +------+----------------------------------------------+ 4072 | Type | Description | 4073 +------+----------------------------------------------+ 4074 | TBD1 | TC : Topology Control (MANET-wide signaling) | 4075 +------+----------------------------------------------+ 4077 Table 8: Message Type assignment 4079 24.3. Message-Type-Specific TLV Type Registries 4081 IANA is requested to create a registry for Message-Type-specific 4082 Message TLVs for TC messages, in accordance with Section 6.2.1 of 4083 [RFC5444], and with initial assignments and allocation policies as 4084 specified in Table 9. 4086 +---------+-------------+-------------------+ 4087 | Type | Description | Allocation Policy | 4088 +---------+-------------+-------------------+ 4089 | 128-223 | Unassigned | Expert Review | 4090 +---------+-------------+-------------------+ 4092 Table 9: TC Message-Type-specific Message TLV Types 4094 IANA is requested to create a registry for Message-Type-specific 4095 Address Block TLVs for TC messages, in accordance with Section 6.2.1 4096 of [RFC5444], and with initial assignments and allocation policies as 4097 specified in Table 10. 4099 +---------+-------------+-------------------+ 4100 | Type | Description | Allocation Policy | 4101 +---------+-------------+-------------------+ 4102 | 128-223 | Unassigned | Expert Review | 4103 +---------+-------------+-------------------+ 4105 Table 10: TC Message-Type-specific Address Block TLV Types 4107 24.4. Message TLV Types 4109 This specification defines two Message TLV Types, which must be 4110 allocated from the "Message TLV Types" namespace defined in 4111 [RFC5444]. IANA is requested to make allocations in the 0-127 range 4112 for these types. This will create two new Type Extension registries 4113 with assignments as specified in Table 11 and Table 12. 4114 Specifications of these TLVs are in Section 13.3.1. Each of these 4115 TLVs MUST NOT be included more than once in a Message TLV Block. 4117 +-------------+------+-----------+---------------------+------------+ 4118 | Name | Type | Type | Description | Allocation | 4119 | | | Extension | | Policy | 4120 +-------------+------+-----------+---------------------+------------+ 4121 | MPR_WILLING | TBD2 | 0 | Bits 0-3 specify | | 4122 | | | | the originating | | 4123 | | | | router's | | 4124 | | | | willingness to act | | 4125 | | | | as a flooding MPR; | | 4126 | | | | bits 4-7 specify | | 4127 | | | | the originating | | 4128 | | | | router's | | 4129 | | | | willingness to act | | 4130 | | | | as a routing MPR. | | 4131 | MPR_WILLING | TBD2 | 1-255 | Unassigned. | Expert | 4132 | | | | | Review | 4133 +-------------+------+-----------+---------------------+------------+ 4135 Table 11: Message TLV Type assignment: MPR_WILLING 4137 +--------------+------+-----------+--------------------+------------+ 4138 | Name | Type | Type | Description | Allocation | 4139 | | | Extension | | Policy | 4140 +--------------+------+-----------+--------------------+------------+ 4141 | CONT_SEQ_NUM | TBD3 | 0 | COMPLETE: | | 4142 | | | | Specifies a | | 4143 | | | | content sequence | | 4144 | | | | number for this | | 4145 | | | | complete message. | | 4146 | CONT_SEQ_NUM | TBD3 | 1 | INCOMPLETE: | | 4147 | | | | Specifies a | | 4148 | | | | content sequence | | 4149 | | | | number for this | | 4150 | | | | incomplete | | 4151 | | | | message. | | 4152 | CONT_SEQ_NUM | TBD3 | 2-255 | Unassigned. | Expert | 4153 | | | | | Review | 4154 +--------------+------+-----------+--------------------+------------+ 4156 Table 12: Message TLV Type assignment: CONT_SEQ_NUM 4158 Type extensions indicated as Expert Review SHOULD be allocated as 4159 described in [RFC5444], based on Expert Review as defined in 4160 [RFC5226]. 4162 24.5. Address Block TLV Types 4164 This specification defines four Address Block TLV Types, which must 4165 be allocated from the "Address Block TLV Types" namespace defined in 4166 [RFC5444]. IANA are requested to make allocations in the 8-127 range 4167 for these types. This will create four new Type Extension registries 4168 with assignments as specified in Table 13, Table 14, Table 15 and 4169 Table 16. Specifications of these TLVs are in Section 13.3.2. 4171 +-------------+------+-----------+-------------------+--------------+ 4172 | Name | Type | Type | Description | Allocation | 4173 | | | Extension | | Policy | 4174 +-------------+------+-----------+-------------------+--------------+ 4175 | LINK_METRIC | TBD4 | 0 | Link metric | | 4176 | | | | meaning assigned | | 4177 | | | | by administrative | | 4178 | | | | action. | | 4179 | LINK_METRIC | TBD4 | 1-223 | Unassigned. | Expert | 4180 | | | | | Review | 4181 | LINK_METRIC | TBD4 | 224-255 | Unassigned. | Experimental | 4182 | | | | | Use | 4183 +-------------+------+-----------+-------------------+--------------+ 4184 Table 13: Address Block TLV Type assignment: LINK_METRIC 4186 All LINK_METRIC TLVs, whatever their type extension, MUST use their 4187 value field to encode the kind and value (in the interval 4188 MINIMUM_METRIC, to MAXIMUM_METRIC, inclusive) of a link metric as 4189 specified in Section 6 and Section 13.3.2. An assignment of a 4190 LINK_METRIC TLV type extension MUST specify the physical meaning, and 4191 mapping of that physical meaning to the representable values in the 4192 indicated interval, of the link metric. 4194 +------+------+-----------+----------------------------+------------+ 4195 | Name | Type | Type | Description | Allocation | 4196 | | | Extension | | Policy | 4197 +------+------+-----------+----------------------------+------------+ 4198 | MPR | TBD5 | 0 | Specifies that a given | | 4199 | | | | network address is of a | | 4200 | | | | router selected as a | | 4201 | | | | flooding MPR (FLOODING = | | 4202 | | | | 1), that a given network | | 4203 | | | | address is of a router | | 4204 | | | | selected as a routing MPR | | 4205 | | | | (ROUTING = 2), or both | | 4206 | | | | (FLOOD_ROUTE = 3). | | 4207 | MPR | TBD5 | 1-255 | Unassigned. | Expert | 4208 | | | | | Review | 4209 +------+------+-----------+----------------------------+------------+ 4211 Table 14: Address Block TLV Type assignment: MPR 4213 +---------------+------+-----------+-------------------+------------+ 4214 | Name | Type | Type | Description | Allocation | 4215 | | | Extension | | Policy | 4216 +---------------+------+-----------+-------------------+------------+ 4217 | NBR_ADDR_TYPE | TBD6 | 0 | Specifies that a | | 4218 | | | | given network | | 4219 | | | | address is of a | | 4220 | | | | neighbor reached | | 4221 | | | | via the | | 4222 | | | | originating | | 4223 | | | | router, if it is | | 4224 | | | | an originator | | 4225 | | | | address | | 4226 | | | | (ORIGINATOR = 1), | | 4227 | | | | is a routable | | 4228 | | | | address (ROUTABLE | | 4229 | | | | = 2), or if it is | | 4230 | | | | both | | 4231 | | | | (ROUTABLE_ORIG = | | 4232 | | | | 3). | | 4233 | NBR_ADDR_TYPE | TBD6 | 1-255 | Unassigned. | Expert | 4234 | | | | | Review | 4235 +---------------+------+-----------+-------------------+------------+ 4237 Table 15: Address Block TLV Type assignment: NBR_ADDR_TYPE 4239 +---------+------+-----------+-------------------------+------------+ 4240 | Name | Type | Type | Description | Allocation | 4241 | | | extension | | Policy | 4242 +---------+------+-----------+-------------------------+------------+ 4243 | GATEWAY | TBD7 | 0 | Specifies that a given | | 4244 | | | | network address is | | 4245 | | | | reached via a gateway | | 4246 | | | | on the originating | | 4247 | | | | router, with value | | 4248 | | | | equal to the number of | | 4249 | | | | hops. | | 4250 | GATEWAY | TBD7 | 1-255 | | Expert | 4251 | | | | | Review | 4252 +---------+------+-----------+-------------------------+------------+ 4254 Table 16: Address Block TLV Type assignment: GATEWAY 4256 Type extensions indicated as Expert Review SHOULD be allocated as 4257 described in [RFC5444], based on Expert Review as defined in 4258 [RFC5226]. 4260 24.6. NBR_ADDR_TYPE and MPR Values 4262 Note: This section does not require any IANA action, as the required 4263 information is included in the descriptions of the MPR and 4264 NBR_ADDR_TYPE Address Block TLVs allocated in Section 24.5. This 4265 information is recorded here for clarity, and for use elsewhere in 4266 this specification. 4268 The Values which the MPR Address Block TLV can use are the following: 4270 o FLOODING := 1; 4272 o ROUTING := 2; 4274 o FLOOD_ROUTE := 3. 4276 The Values which the NBR_ADDR_TYPE Address Block TLV can use are the 4277 following: 4279 o ORIGINATOR := 1; 4281 o ROUTABLE := 2; 4283 o ROUTABLE_ORIG := 3. 4285 25. Contributors 4287 This specification is the result of the joint efforts of the 4288 following contributors -- listed alphabetically. 4290 o Cedric Adjih, INRIA, France, 4292 o Emmanuel Baccelli, INRIA , France, 4294 o Thomas Heide Clausen, LIX, France, 4296 o Justin Dean, NRL, USA, 4298 o Christopher Dearlove, BAE Systems, UK, 4299 4301 o Ulrich Herberg, Fujitsu Laboratories of America, USA, 4302 4304 o Satoh Hiroki, Hitachi SDL, Japan, 4306 o Philippe Jacquet, Alcatel Lucent Bell Labs, France, 4307 4309 o Monden Kazuya, Hitachi SDL, Japan, 4311 o Kenichi Mase, Niigata University, Japan, 4313 o Ryuji Wakikawa, Toyota, Japan, 4315 26. Acknowledgments 4317 The authors would like to acknowledge the team behind OLSRv1, as 4318 listed in RFC3626, including Anis Laouiti (INT), Pascale Minet 4319 (INRIA), Paul Muhlethaler (INRIA), Amir Qayyum (M.A. Jinnah 4320 University), and Laurent Viennot (INRIA) for their contributions. 4322 The authors would like to gratefully acknowledge the following people 4323 for intense technical discussions, early reviews and comments on the 4324 specification and its components (listed alphabetically): Khaldoun Al 4325 Agha (LRI), Teco Boot (Infinity Networks), Ross Callon (Juniper), 4326 Song-Yean Cho (Samsung), Alan Cullen (BAE Systems), Louise Lamont 4327 (CRC), Li Li (CRC), Joseph Macker (NRL), Richard Ogier (SRI), Charles 4328 E. Perkins (Futurewei), Henning Rogge (Frauenhofer FKIE), and the 4329 entire IETF MANET Working Group. 4331 Finally, the authors would like to express their gratitude to the 4332 Area Directors for providing valuable review comments during the IESG 4333 evaluation, in particular (listed alphabetically) Benoit Claise, 4334 Adrian Farrel, Stephen Farrell, Barry Leiba, Pete Resnick, and Martin 4335 Stiemerling. 4337 27. References 4339 27.1. Normative References 4341 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 4342 Requirement Levels", RFC 2119, BCP 14, March 1997. 4344 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 4345 Considerations in Mobile Ad Hoc Networks (MANETs)", 4346 RFC 5148, February 2008. 4348 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 4349 IANA Considerations Section in RFCs", RFC 5226, BCP 26, 4350 May 2008. 4352 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 4353 "Generalized Mobile Ad Hoc Network (MANET) Packet/ 4354 Message Format", RFC 5444, February 2009. 4356 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 4357 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, 4358 March 2009. 4360 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc 4361 Network (MANET) Protocols", RFC 5498, March 2009. 4363 [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc 4364 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 4365 RFC 6130, April 2011. 4367 27.2. Informative References 4369 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 4370 (MANET): Routing Protocol Performance Issues and 4371 Evaluation Considerations", RFC 2501, January 1999. 4373 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 4374 Routing Protocol", RFC 3626, October 2003. 4376 [RFC6622] Herberg, U. and T. Clausen, "Integrity Check Value and 4377 Timestamp TLV Definitions for Mobile Ad Hoc Networks 4378 (MANETs)", RFC 6622, May 2012. 4380 [HIPERLAN] ETSI, "ETSI STC-RES10 Committee. Radio equipment and 4381 systems: HIPERLAN type 1, functional specifications ETS 4382 300-652", June 1996. 4384 [HIPERLAN2] Jacquet, P., Minet, P., Muhlethaler, P., and N. 4385 Rivierre, "Increasing reliability in cable free radio 4386 LANs: Low level forwarding in HIPERLAN.", 1996. 4388 [MPR] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint 4389 relaying: An efficient technique for flooding in mobile 4390 wireless networks.", 2001. 4392 [FSR] Pei, G., Gerla, M., and T. Chen, "Fisheye state routing 4393 in mobile ad hoc networks", 2000. 4395 [FSLS] Santivanez, C., Ramanathan, R., and I. Stavrakakis, 4396 "Making link-state routing scale for ad hoc networks", 4397 2000. 4399 [McCabe] McCabe, A., Dearlove, C., Fredin, M., and L. Axelsson, 4400 "Scalability Modelling of Ad Hoc Routing Protocols - A 4401 Comparison of OLSR and DSR", 2004. 4403 Appendix A. Constraints 4405 Updates to the Local Information Base, the Neighborhood Information 4406 Base or the Topology Information Base MUST ensure that all 4407 constraints specified in this appendix are maintained, as well as 4408 those specified in [RFC6130]. This is the case for the processing, 4409 specified in this document. Any protocol extension or outside 4410 process, which updates the Neighborhood Information Base or the 4411 Topology Information Base, MUST also ensure that these constraints 4412 are maintained. 4414 In each Originator Tuple: 4416 o O_orig_addr MUST NOT equal any other O_orig_addr. 4418 o O_orig_addr MUST NOT equal this router's originator address. 4420 In each Local Attached Network Tuple: 4422 o AL_net_addr MUST NOT equal any other AL_net_addr. 4424 o AL_net_addr MUST NOT equal or be a sub-range of any network 4425 address in the I_local_iface_addr_list of any Local Interface 4426 Tuple. 4428 o AL_net_addr MUST NOT equal this router's originator address, or 4429 equal the O_orig_addr in any Originator Tuple. 4431 o AL_dist MUST NOT be less than zero. 4433 In each Link Tuple: 4435 o L_neighbor_iface_addr_list MUST NOT contain any network address 4436 that AL_net_addr of any Local Attached Network Tuple equals or is 4437 a sub-range of. 4439 o if L_in_metric != UNKNOWN_METRIC then L_in_metric MUST be 4440 representable in the defined compressed form. 4442 o if L_out_metric != UNKNOWN_METRIC then L_out_metric MUST be 4443 representable in the defined compressed form. 4445 o If L_mpr_selector = true, then L_status = SYMMETRIC. 4447 In each Neighbor Tuple: 4449 o N_orig_addr MUST NOT be changed to unknown. 4451 o N_orig_addr MUST NOT equal this router's originator address, or 4452 equal O_orig_addr in any Originator Tuple. 4454 o N_orig_addr MUST NOT equal the AL_net_addr in any Local Attached 4455 Network Tuple. 4457 o If N_orig_addr != unknown, then N_orig_addr MUST NOT equal the 4458 N_orig_addr in any other Neighbor Tuple. 4460 o N_neighbor_addr_list MUST NOT contain any network address which 4461 includes this router's originator address, the O_orig_addr in any 4462 Originator Tuple, or equal or have as a sub-range the AL_net_addr 4463 in any Local Attached Network Tuple. 4465 o If N_orig_addr = unknown, then N_will_flooding = WILL_NEVER, 4466 N_will_routing = WILL_NEVER, N_flooding_mpr, N_routing_mpr = 4467 false, N_mpr_selector = false, and N_advertised = false. 4469 o N_in_metric MUST equal the minimum value of the L_in_metric values 4470 of all corresponding Link Tuples with L_status = SYMMETRIC and 4471 L_in_metric != UNKNOWN_METRIC, if any, otherwise N_in_metric = 4472 UNKNOWN_METRIC. 4474 o N_out_metric MUST equal the minimum value of the L_out_metric 4475 values of all corresponding Link Tuples with L_status = SYMMETRIC 4476 and L_out_metric != UNKNOWN_METRIC, if any, otherwise N_out_metric 4477 = UNKNOWN_METRIC. 4479 o N_will_flooding and N_will_routing MUST be in the range from 4480 WILL_NEVER to WILL_ALWAYS, inclusive. 4482 o If N_flooding_mpr = true, then N_symmetric MUST be true, 4483 N_out_metric MUST NOT equal UNKNOWN_METRIC and N_will_flooding 4484 MUST NOT equal WILL_NEVER. 4486 o If N_routing_mpr = true, then N_symmetric MUST be true, 4487 N_in_metric MUST NOT equal UNKNOWN_METRIC and N_will_routing MUST 4488 NOT equal WILL_NEVER. 4490 o If N_symmetric = true and N_flooding_mpr = false, then 4491 N_will_flooding MUST NOT equal WILL_ALWAYS. 4493 o If N_symmetric = true and N_routing_mpr = false, then 4494 N_will_routing MUST NOT equal WILL_ALWAYS. 4496 o If N_mpr_selector = true, then N_advertised MUST be true. 4498 o If N_advertised = true, then N_symmetric MUST be true and 4499 N_out_metric MUST NOT equal UNKNOWN_METRIC. 4501 In each Lost Neighbor Tuple: 4503 o NL_neighbor_addr MUST NOT include this router's originator 4504 address, the O_orig_addr in any Originator Tuple, or equal or have 4505 as a sub-range the AL_net_addr in any Local Attached Network 4506 Tuple. 4508 In each 2-Hop Tuple: 4510 o N2_2hop_addr MUST NOT equal this router's originator address, 4511 equal the O_orig_addr in any Originator Tuple, or equal or have as 4512 a sub-range the AL_net_addr in any Local Attached Network Tuple. 4514 o if N2_in_metric != UNKNOWN_METRIC then N2_in_metric MUST be 4515 representable in the defined compressed form. 4517 o if N2_out_metric != UNKNOWN_METRIC then N2_out_metric MUST be 4518 representable in the defined compressed form. 4520 In each Advertising Remote Router Tuple: 4522 o AR_orig_addr MUST NOT be in any network address in the 4523 I_local_iface_addr_list in any Local Interface Tuple or be in the 4524 IR_local_iface_addr in any Removed Interface Address Tuple. 4526 o AR_orig_addr MUST NOT equal this router's originator address or 4527 equal the O_orig_addr in any Originator Tuple. 4529 o AR_orig_addr MUST NOT be in the AL_net_addr in any Local Attached 4530 Network Tuple. 4532 o AR_orig_addr MUST NOT equal the AR_orig_addr in any other 4533 Advertising Remote Router Tuple. 4535 In each Router Topology Tuple: 4537 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4538 = TR_from_orig_addr. 4540 o TR_to_orig_addr MUST NOT be in any network address in the 4541 I_local_iface_addr_list in any Local Interface Tuple or be in the 4542 IR_local_iface_addr in any Removed Interface Address Tuple. 4544 o TR_to_orig_addr MUST NOT equal this router's originator address or 4545 equal the O_orig_addr in any Originator Tuple. 4547 o TR_to_orig_addr MUST NOT be in the AL_net_addr in any Local 4548 Attached Network Tuple. 4550 o The ordered pair (TR_from_orig_addr, TR_to_orig_addr) MUST NOT 4551 equal the corresponding pair for any other Router Topology Tuple. 4553 o TR_seq_number MUST NOT be greater than AR_seq_number in the 4554 Advertising Remote Router Tuple with AR_orig_addr = 4555 TR_from_orig_addr. 4557 o TR_metric MUST be representable in the defined compressed form. 4559 In each Routable Address Topology Tuple: 4561 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4562 = TA_from_orig_addr. 4564 o TA_dest_addr MUST be routable. 4566 o TA_dest_addr MUST NOT overlap any network address in the 4567 I_local_iface_addr_list in any Local Interface Tuple or overlap 4568 the IR_local_iface_addr in any Removed Interface Address Tuple. 4570 o TA_dest_addr MUST NOT include this router's originator address or 4571 include the O_orig_addr in any Originator Tuple. 4573 o TA_dest_addr MUST NOT equal or have as a sub-range the AL_net_addr 4574 in any Local Attached Network Tuple. 4576 o The ordered pair (TA_from_orig_addr, TA_dest_addr) MUST NOT equal 4577 the corresponding pair for any other Attached Network Tuple. 4579 o TA_seq_number MUST NOT be greater than AR_seq_number in the 4580 Advertising Remote Router Tuple with AR_orig_addr = 4581 TA_from_orig_addr. 4583 o TA_metric MUST be representable in the defined compressed form. 4585 In each Attached Network Tuple: 4587 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4588 = AN_orig_addr. 4590 o AN_net_addr MUST NOT equal or be a sub-range of any network 4591 address in the I_local_iface_addr_list in any Local Interface 4592 Tuple or be a sub-range of the IR_local_iface_addr in any Removed 4593 Interface Address Tuple. 4595 o AN_net_addr MUST NOT equal this router's originator address or 4596 equal the O_orig_addr in any Originator Tuple. 4598 o AN_net_addr MUST NOT equal the AL_net_addr in any Local Attached 4599 Network Tuple. 4601 o The ordered pair (AN_orig_addr, AN_net_addr) MUST NOT equal the 4602 corresponding pair for any other Attached Network Tuple. 4604 o AN_seq_number MUST NOT be greater than AR_seq_number in the 4605 Advertising Remote Router Tuple with AR_orig_addr = AN_orig_addr. 4607 o AN_dist MUST NOT be less than zero. 4609 o AN_metric MUST be representable in the defined compressed form. 4611 Appendix B. Example Algorithm for Calculating MPRs 4613 The following specifies an algorithm which MAY be used to select an 4614 MPR Set given a Neighbor Graph, as defined in Section 18.2 and 4615 Section 18.3. 4617 This algorithm selects an MPR Set M that is a subset of the set N1 4618 that is part of the Neighbor Graph. This algorithm assumes that a 4619 subset I of N1 is pre-selected as MPRs, i.e., that M will contain I. 4621 B.1. Additional Notation 4623 The following additional notation, in addition to that in 4624 Section 18.2 will be used by this algorithm: 4626 N: 4627 A subset of N2, consisting of those elements y in N2 such that 4628 either d1(y) is not defined, or there is at least one x in N1 such 4629 that d(x,y) is defined and d(x,y) < d1(y). 4631 D(x): 4632 For an element x in N1, the number of elements y in N for which 4633 d(x,y) is defined and has minimal value among the d(z,y) for all z 4634 in N1. 4636 R(x,M): 4637 For an element x in N1, the number of elements y in N for which 4638 d(x,y) is defined, has minimal value among the d(z,y) for all z in 4639 N1, and no such minimal values have z in M. (Note that, denoting 4640 the empty set by 0, D(x) = R(x,0).) 4642 B.2. MPR Selection Algorithm 4644 To create the MPR Set M, starting with M := I: 4646 1. Add all elements x in N1 that have W(x) = WILL_ALWAYS to M. 4648 2. For each element y in N for which there is only one element x in 4649 N1 such that d2(x,y) is defined, add that element x to M. 4651 3. While there exists any element x in N1 with R(x,M) > 0: 4653 1. Select an element x in N1 with R(x,M) > 0 in the following 4654 order of priority, and then add to M: 4656 + greatest W(x), THEN; 4658 + greatest R(x,M), THEN; 4660 + greatest D(x), THEN; 4662 + any choice, which MAY be based on other criteria (for 4663 example a router MAY choose to prefer a neighbor as an MPR 4664 if that neighbor has already selected the router as an MPR 4665 of the same type, MAY prefer a neighbor based on 4666 information freshness, or MAY prefer a neighbor based on 4667 length of time previously selected as an MPR) or MAY be 4668 random. 4670 4. OPTIONAL: consider each element x in M, but not in I, in turn and 4671 if x can be removed from M while still leaving it satisfying the 4672 definition of an MPR Set, then remove that element x from M. 4673 Elements MAY be considered in any order, e.g., in order of 4674 increasing W(x). 4676 Appendix C. Example Algorithm for Calculating the Routing Set 4678 The following procedure is given as an example for calculating the 4679 Routing Set using a variation of Dijkstra's algorithm. First all 4680 Routing Tuples are removed, and then, using the selections and 4681 definitions in Appendix C.1, the procedures in the following sections 4682 (each considered a "stage" of the processing) are applied in turn. 4684 C.1. Local Interfaces and Neighbors 4686 The following selections and definitions are made: 4688 1. For each Local Interface Tuple, select a network address from its 4689 I_local_iface_addr_list, this is defined as the selected address 4690 for this Local Interface Tuple. 4692 2. For each Link Tuple, the selected address of its corresponding 4693 Local Interface Tuple is defined as the selected local address 4694 for this Local Interface Tuple. 4696 3. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4697 != UNKNOWN_METRIC, select a Link Tuple with L_status = SYMMETRIC 4698 for which this is the corresponding Neighbor Tuple and has 4699 L_out_metric = N_out_metric. This is defined as the selected 4700 Link Tuple for this Neighbor Tuple. 4702 4. For each network address (N_orig_addr or in N_neighbor_addr_list, 4703 the "neighbor address") from a Neighbor Tuple with N_symmetric = 4704 true and N_out_metric != UNKNOWN_METRIC, select a Link Tuple (the 4705 "selected Link Tuple") from those for which this is the 4706 corresponding Neighbor Tuple, have L_status = SYMMETRIC, and have 4707 L_out_metric = N_out_metric, by: 4709 1. If there is such a Link Tuple whose 4710 L_neighbor_iface_addr_list contains the neighbor address, 4711 select that Link Tuple. 4713 2. Otherwise select the selected Link Tuple for this Neighbor 4714 Tuple. 4716 Then for this neighbor address: 4718 3. The selected local address is defined as the selected local 4719 address for the selected Link Tuple. 4721 4. The selected link address is defined as an address from the 4722 L_neighbor_iface_addr_list of the selected Link Tuple, if 4723 possible equal to this neighbor address. 4725 5. Routing Tuple preference is decided by preference for minimum 4726 R_dist, then for minimum R_dist, and then for preference for 4727 corresponding Neighbor Tuples in this order: 4729 * For greater N_will_routing. 4731 * For N_mpr_selector = true over N_mpr_selector = false. 4733 Note that preferred Routing Tuples SHOULD be used. Routing 4734 Tuples with minimum R_metric MUST be used, this is specified 4735 outside the definition of preference. An implementation MAY 4736 modify this definition of preference (including for minimum 4737 R_dist) without otherwise affecting this algorithm. 4739 C.2. Add Neighbor Routers 4741 The following procedure is executed once. 4743 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4744 != UNKNOWN_METRIC, add a Routing Tuple with: 4746 * R_dest_addr := N_orig_addr; 4748 * R_next_iface_addr := selected link address for N_orig_addr; 4750 * R_local_iface_addr := selected local address for N_orig_addr; 4752 * R_metric := N_out_metric; 4754 * R_dist := 1. 4756 C.3. Add Remote Routers 4758 The following procedure is executed once. 4760 1. Add a label that may be "used" or "unused" to each Routing Tuple, 4761 with all initial values equal to unused. (Note that this label 4762 is only required during this algorithm.) 4764 2. If there are no unused Routing Tuples then this stage is 4765 complete, otherwise repeat the following until that is the case. 4767 1. Find the unused Routing Tuple with minimum R_metric (if more 4768 than one, pick any) and denote it the "current Routing 4769 Tuple". 4771 2. Mark the current Routing Tuple as used. 4773 3. For each Router Topology Tuple, with: 4775 + TR_from_orig_addr = R_dest_addr of the current Routing 4776 Tuple. 4778 2. Define: 4780 - new_metric := R_metric of the current Routing Tuple + 4781 TR_metric; 4783 - new_dist := R_dist of the current Routing Tuple + 1. 4785 3. If there is no Routing Tuple with R_dest_addr = 4786 TR_to_orig_addr, then create an unused Routing Tuple 4787 with: 4789 - R_dest_addr := TR_to_orig_addr; 4791 - R_next_iface_addr := R_next_iface_addr of the current 4792 Routing Tuple; 4794 - R_local_iface_addr := R_local_iface_addr of the 4795 current Routing Tuple; 4797 - R_metric := new_metric; 4799 - R_dist := new_dist. 4801 4. Otherwise, if there is an unused Routing Tuple with 4802 R_dest_addr = TR_to_orig_addr, and either new_metric < 4803 R_metric or (new_metric = R_metric and the updated 4804 Routing Tuple would be preferred) then update this 4805 Routing Tuple to have: 4807 - R_next_iface_addr := R_next_iface_addr of the current 4808 Routing Tuple; 4810 - R_local_iface_addr := R_local_iface_addr of the 4811 current Routing Tuple; 4813 - R_metric := new_metric; 4815 - R_dist := new_dist. 4817 C.4. Add Neighbor Addresses 4819 The following procedure is executed once. 4821 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4822 != UNKNOWN_METRIC: 4824 1. For each network address (the "neighbor address") in 4825 N_neighbor_addr_list, if the neighbor address is not equal to 4826 the R_dest_addr of any Routing Tuple, then add a new Routing 4827 Tuple, with: 4829 + R_dest_addr := neighbor address; 4831 + R_next_iface_addr := selected link address for the 4832 neighbor address; 4834 + R_local_iface_addr := selected local address for the 4835 neighbor address; 4837 + R_metric := N_out_metric; 4839 + R_dist := 1. 4841 C.5. Add Remote Routable Addresses 4843 The following procedure is executed once. 4845 1. For each Routable Address Topology Tuple, if: 4847 * TA_dest_addr is not equal to the R_dest_addr of any Routing 4848 Tuple added in an earlier stage; AND 4850 * TA_from_orig_addr is equal to the R_dest_addr of a Routing 4851 Tuple (the "previous Routing Tuple"), 4853 then add a new Routing Tuple, with: 4855 * R_dest_addr := TA_dest_addr; 4857 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4858 Tuple; 4860 * R_local_iface_addr := R_local_iface_addr of the previous 4861 Routing Tuple; 4863 * R_metric := R_metric of the previous Routing Tuple + 4864 TA_metric. 4866 * R_dist := R_dist of the previous Routing Tuple + 1. 4868 There may be more than one Routing Tuple that may be added for an 4869 R_dest_addr in this stage. If so, then, for each such 4870 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4871 selected, otherwise a Routing Tuple which is preferred SHOULD be 4872 added. 4874 C.6. Add Attached Networks 4876 The following procedure is executed once. 4878 1. For each Attached Network Tuple, if: 4880 * AN_net_addr is not equal to the R_dest_addr of any Routing 4881 Tuple added in an earlier stage; AND 4883 * AN_orig_addr is equal to the R_dest_addr of a Routing Tuple 4884 (the "previous Routing Tuple), 4886 then add a new Routing Tuple, with: 4888 * R_dest_addr := AN_net_addr; 4890 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4891 Tuple; 4893 * R_local_iface_addr := R_local_iface_addr of the previous 4894 Routing Tuple; 4896 * R_metric := R_metric of the previous Routing Tuple + 4897 AN_metric; 4899 * R_dist := R_dist of the previous Routing Tuple + AN_dist. 4901 There may be more than one Routing Tuple that may be added for an 4902 R_dest_addr in this stage. If so, then, for each such 4903 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4904 selected, otherwise a Routing Tuple which is preferred SHOULD be 4905 added. 4907 C.7. Add 2-Hop Neighbors 4909 The following procedure is executed once. 4911 1. For each 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC, if: 4913 * N2_2hop_addr is a routable address; AND 4915 * N2_2hop_addr is not equal to the R_dest_addr of any Routing 4916 Tuple added in an earlier stage; AND 4918 * the Routing Tuple with R_dest_addr = N_orig_addr of the 4919 corresponding Neighbor Tuple (the "previous Routing Tuple") 4920 has R_dist = 1, 4922 then add a new Routing Tuple, with: 4924 * R_dest_addr := N2_2hop_addr; 4926 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4927 Tuple; 4929 * R_local_iface_addr := R_local_iface_addr of the previous 4930 Routing Tuple; 4932 * R_metric := R_metric of the previous Routing Tuple + 4933 N_out_metric of the corresponding Neighbor Tuple; 4935 * R_dist := 2. 4937 There may be more than one Routing Tuple that may be added for an 4938 R_dest_addr in this stage. If so, then, for each such 4939 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4940 selected, otherwise a Routing Tuple which is preferred SHOULD be 4941 added. 4943 Appendix D. TC Message Example 4945 TC messages are instances of [RFC5444] messages. This specification 4946 requires that TC messages contain and 4947 fields. It supports TC messages with any combination of remaining 4948 message header options and address encodings, enabled by [RFC5444] 4949 that convey the required information. As a consequence, there is no 4950 single way to represent how all TC messages look. This appendix 4951 illustrates a TC message, the exact values and content included are 4952 explained in the following text. 4954 The TC message's four bit Message Flags (MF) field has value 15 4955 indicating that the message header contains originator address, hop 4956 limit, hop count, and message sequence number fields. Its four bit 4957 Message Address Length (MAL) field has value 3, indicating addresses 4958 in the message have a length of four octets, here being IPv4 4959 addresses. The overall message length is 75 octets. 4961 The message has a Message TLV Block with content length 17 octets 4962 containing four TLVs. The first two TLVs are validity and interval 4963 times for the message. The third TLV is the content sequence number 4964 TLV used to carry the 2 octet ANSN, and (with default type extension 4965 zero, i.e., COMPLETE) indicating that the TC message is complete. 4966 The fourth TLV contains forwarding and routing willingness values for 4967 the originating router (FWILL and RWILL, respectively). Each TLV 4968 uses a TLV with Flags octet (MTLVF) value 16, indicating that it has 4969 a Value, but no type extension or start and stop indexes. The first 4970 two TLVs have a Value Length of 1 octet, the last has a Value Length 4971 of 2 octets. 4973 The message has two Address Blocks. (This is not necessary, the 4974 information could be conveyed using a single Address Block, the use 4975 of two Address Blocks, which is also allowed, is illustrative only.) 4976 The first Address Block contains 3 addresses, with Flags octet 4977 (ATLVF) value 128, hence with a Head section (with length 2 octets), 4978 but no Tail section, and hence with Mid sections with length two 4979 octets. The following TLV Block (content length 13 octets) contains 4980 two TLVs. The first TLV is a NBR_ADDR_TYPE TLV with Flags octet 4981 (ATLVF) value 16, indicating a single Value but no indexes. Thus all 4982 these addresses are associated with the Value (with Value Length 1 4983 octet) ROUTABLE_ORIG, i.e., they are originator addresses of 4984 advertised neighbors that are also routable addresses. The second 4985 TLV is a LINK_STATUS TLV with Flags octet (ATLVF) value 20, 4986 indicating a Value for each address, i.e., as the total Value Length 4987 is 6 octets, each address is associated with a Value with length two 4988 octets. These Value fields are each shown as having four bits 4989 indicating that they are outgoing neighbor metric values, and as 4990 having twelve bits that represent the metric value (the first four 4991 bits being the exponent, the remaining twelve bits the mantissa). 4993 The second Address Block contains 1 address, with Flags octet (ATLVF) 4994 176, indicating that there is a Head section (with length 2 octets), 4995 that the Tail section (with length 2 octets) consists of zero valued 4996 octets (not included), and that there is a single prefix length, 4997 which is 16. The network address is thus Head.0.0/16. The following 4998 TLV Block (content length 8 octets) includes two TLVs. The first has 4999 a Flags octet (ATLVF) of 16, again indicating that no indexes are 5000 needed, but that a Value (with Value Length 1 octet) is present, 5001 indicating the address distance as a number of hops. The second TLV 5002 is another LINK_METRIC TLV, as in the first Address TLV Block except 5003 with a Flags octet (ATLVF) value 16, indicating that a single Value 5004 is present. 5006 0 1 2 3 5007 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 5008 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5009 | TC | MF=15 | MAL=3 | Message Length = 75 | 5010 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5011 | Originator Address | 5012 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5013 | Hop Limit | Hop Count | Message Sequence Number | 5014 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5015 | Message TLV Block Length = 17 | VALIDITY_TIME | MTLVF = 16 | 5016 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5017 | Value Len = 1 | Value (Time) | INTERVAL_TIME | MTLVF = 16 | 5018 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5019 | Value Len = 1 | Value (Time) | CONT_SEQ_NUM | MTLVF = 16 | 5020 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5021 | Value Len = 2 | Value (ANSN) | MPR_WILLING | 5022 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5023 | MTLVF = 16 | Value Len = 1 | FWILL | RWILL | Num Addrs = 3 | 5024 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5025 | ABF = 128 | Head Len = 2 | Head | 5026 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5027 | Mid | Mid | 5028 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5029 | Mid | Address TLV Block Length = 13 | 5030 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5031 | NBR_ADDR_TYPE | ATLVF = 16 | Value Len = 1 | ROUTABLE_ORIG | 5032 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5033 | LINK_METRIC | ATLVF = 20 | Value Len = 6 |0|0|0|1|Metric | 5034 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5035 | Metric (cont) |0|0|0|1| Metric |0|0|0|1|Metric | 5036 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5037 | Metric (cont) | Num Addrs = 1 | ABF = 176 | Head Len = 2 | 5038 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5039 | Head | Tail Len = 2 | Pref Len = 16 | 5040 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5041 | Address TLV Block Length = 9 | GATEWAY | ATLVF = 16 | 5042 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5043 | Value Len = 1 | Value (Hops) | LINK_METRIC | ATLVF = 16 | 5044 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5045 | Value Len = 2 |0|0|0|1| Metric | 5046 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5048 Appendix E. Flow and Congestion Control 5050 Due to its proactive nature, this protocol has a natural control over 5051 the flow of its control traffic. Routers transmit control messages 5052 at predetermined rates specified and bounded by message intervals. 5054 This protocol employs [RFC6130] for local signaling, embedding MPR 5055 selection advertisement through a simple Address Block TLV, and 5056 router willingness advertisement (if any) as a single Message TLV. 5057 Local signaling, therefore, shares the characteristics and 5058 constraints of [RFC6130]. 5060 Furthermore, the use of MPRs can greatly reduce the signaling 5061 overhead from link state information dissemination in two ways, 5062 attaining both flooding reduction and topology reduction. First, 5063 using MPR flooding, the cost of distributing link state information 5064 throughout the network is reduced, as compared to when using blind 5065 flooding, since only MPRs need to forward link state declaration 5066 messages. Second, the amount of link state information for a router 5067 to declare is reduced to need only contain that router's MPR 5068 selectors. This reduces the size of a link state declaration as 5069 compared to declaring full link state information. In particular 5070 some routers may not need to declare any such information. In dense 5071 networks, the reduction of control traffic can be of several orders 5072 of magnitude compared to routing protocols using blind flooding 5073 [MPR]. This feature naturally provides more bandwidth for useful 5074 data traffic and pushes further the frontier of congestion. 5076 Since the control traffic is continuous and periodic, it keeps the 5077 quality of the links used in routing more stable. However, using 5078 some options, some control messages (HELLO messages or TC messages) 5079 may be intentionally sent in advance of their deadline in order to 5080 increase the responsiveness of the protocol to topology changes. 5081 This may cause a small, temporary, and local increase of control 5082 traffic, however this is at all times bounded by the use of minimum 5083 message intervals. 5085 A router that recognizes that the network is suffering from 5086 congestion can increase its message interval parameters. If this is 5087 done by most or all routers in the network, then the overall control 5088 traffic in the network will be reduced. Routers will have to take 5089 care in using this capability not to increase message interval 5090 parameters such that they cannot cope with network topology changes. 5091 Note that routers can make such decisions independently, it is not 5092 necessary for all routers to be using the same parameter values, nor 5093 is it necessary that all routers decide to change their intervals at 5094 the same time. 5096 Authors' Addresses 5098 Thomas Heide Clausen 5099 LIX, Ecole Polytechnique 5101 Phone: +33 6 6058 9349 5102 EMail: T.Clausen@computer.org 5103 URI: http://www.ThomasClausen.org/ 5105 Christopher Dearlove 5106 BAE Systems ATC 5108 Phone: +44 1245 242194 5109 EMail: chris.dearlove@baesystems.com 5110 URI: http://www.baesystems.com/ 5112 Philippe Jacquet 5113 Alcatel-Lucent Bell Labs 5115 Phone: +33 6 7337 1880 5116 EMail: philippe.jacquet@alcatel-lucent.com 5118 Ulrich Herberg 5119 Fujitsu Laboratories of America 5120 1240 E. Arques Ave. 5121 Sunnyvale, CA, 94085 5122 USA 5124 EMail: ulrich@herberg.name 5125 URI: http://www.herberg.name/