idnits 2.17.1 draft-ietf-manet-olsrv2-19.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 (March 23, 2013) is 4014 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) == Missing Reference: 'TK' is mentioned on line 4115, but not defined == Missing Reference: 'NIST' is mentioned on line 4115, but not defined == Missing Reference: 'WHF' is mentioned on line 4116, but not defined ** Downref: Normative reference to an Informational RFC: RFC 5148 ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) == Outdated reference: A later version (-06) exists of draft-ietf-manet-rfc6622-bis-01 == Outdated reference: A later version (-05) exists of draft-ietf-manet-nhdp-olsrv2-sec-01 Summary: 2 errors (**), 0 flaws (~~), 6 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique 4 Intended status: Standards Track C. Dearlove 5 Expires: September 24, 2013 BAE Systems ATC 6 P. Jacquet 7 Alcatel-Lucent Bell Labs 8 U. Herberg 9 Fujitsu Laboratories of America 10 March 23, 2013 12 The Optimized Link State Routing Protocol version 2 13 draft-ietf-manet-olsrv2-19 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 September 24, 2013. 37 Copyright Notice 39 Copyright (c) 2013 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 23.5. Mandatory Security Mechanisms . . . . . . . . . . . . . . 87 182 23.6. Key Management . . . . . . . . . . . . . . . . . . . . . 87 183 24. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 90 184 24.1. Expert Review: Evaluation Guidelines . . . . . . . . . . 90 185 24.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 90 186 24.3. Message-Type-Specific TLV Type Registries . . . . . . . . 90 187 24.4. Message TLV Types . . . . . . . . . . . . . . . . . . . . 91 188 24.5. Address Block TLV Types . . . . . . . . . . . . . . . . . 92 189 24.6. NBR_ADDR_TYPE and MPR Values . . . . . . . . . . . . . . 95 190 25. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 95 191 26. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 96 192 27. References . . . . . . . . . . . . . . . . . . . . . . . . . 96 193 27.1. Normative References . . . . . . . . . . . . . . . . . . 96 194 27.2. Informative References . . . . . . . . . . . . . . . . . 97 195 Appendix A. Constraints . . . . . . . . . . . . . . . . . . . . 98 196 Appendix B. Example Algorithm for Calculating MPRs . . . . . . . 102 197 B.1. Additional Notation . . . . . . . . . . . . . . . . . . . 102 198 B.2. MPR Selection Algorithm . . . . . . . . . . . . . . . . . 103 199 Appendix C. Example Algorithm for Calculating the Routing Set . 104 200 C.1. Local Interfaces and Neighbors . . . . . . . . . . . . . 104 201 C.2. Add Neighbor Routers . . . . . . . . . . . . . . . . . . 105 202 C.3. Add Remote Routers . . . . . . . . . . . . . . . . . . . 105 203 C.4. Add Neighbor Addresses . . . . . . . . . . . . . . . . . 107 204 C.5. Add Remote Routable Addresses . . . . . . . . . . . . . . 107 205 C.6. Add Attached Networks . . . . . . . . . . . . . . . . . . 108 206 C.7. Add 2-Hop Neighbors . . . . . . . . . . . . . . . . . . . 108 207 Appendix D. TC Message Example . . . . . . . . . . . . . . . . . 109 208 Appendix E. Flow and Congestion Control . . . . . . . . . . . . 111 210 1. Introduction 212 The Optimized Link State Routing protocol version 2 (OLSRv2) is the 213 successor to OLSR (version 1) as published in [RFC3626]. Compared to 214 [RFC3626], OLSRv2 retains the same basic mechanisms and algorithms, 215 enhanced by the ability to use a link metric other than hop count in 216 the selection of shortest routes. OLSRv2 also uses a more flexible 217 and efficient signaling framework, and includes some simplification 218 of the messages being exchanged. 220 OLSRv2 is developed for mobile ad hoc networks (MANETs). It operates 221 as a table driven, proactive protocol, i.e., it exchanges topology 222 information with other routers in the network regularly. OLSRv2 is 223 an optimization of the classic link state routing protocol. Its key 224 concept is that of MultiPoint Relays (MPRs). Each router selects two 225 sets of MPRs, each being a set of its neighbor routers that "cover" 226 all of its symmetrically connected 2-hop neighbor routers. These two 227 sets are of "flooding MPRs" and "routing MPRs", and are used to 228 achieve flooding reduction and topology reduction, respectively. 230 Flooding reduction is achieved by control traffic being flooded 231 through the network using hop by hop forwarding, but with a router 232 only needing to forward control traffic that is first received 233 directly from one of the routers that have selected it as a flooding 234 MPR (its "flooding MPR selectors"). This mechanism, denoted "MPR 235 flooding", provides an efficient mechanism for information 236 distribution within the MANET by reducing the number of transmissions 237 required [MPR]. 239 Topology reduction is achieved by assigning a special responsibility 240 to routers selected as routing MPRs when declaring link state 241 information. A sufficient requirement for OLSRv2 to provide shortest 242 routes to all destinations is that routers declare link state 243 information for their routing MPR selectors, if any. Routers that 244 are not selected as routing MPRs need not send any link state 245 information. Based on this reduced link state information, routing 246 MPRs are used as intermediate routers in multi-hop routes. 248 Thus the use of MPRs allows reduction of the number and the size of 249 link state messages, and in the amount of link state information 250 maintained in each router. When possible (in particular if using a 251 hop count metric) the same routers may be picked as both flooding 252 MPRs and routing MPRs. 254 A router selects both routing and flooding MPRs from among its one 255 hop neighbors connected by "symmetric", i.e., bidirectional, links. 256 Therefore, selecting routes through routing MPRs avoids the problems 257 associated with data packet transfer over unidirectional links (e.g., 258 the problem of not getting link layer acknowledgments at each hop, 259 for link layers employing this technique). 261 OLSRv2 uses and extends the MANET NeighborHood Discovery Protocol 262 (NHDP) defined in [RFC6130] and also uses the Generalized MANET 263 Packet/Message Format [RFC5444], the TLVs specified in [RFC5497] and, 264 optionally, message jitter as specified in [RFC5148]. These four 265 other protocols and specifications were all originally created as 266 part of OLSRv2, but have been specified separately for wider use. 268 OLSRv2 makes no assumptions about the underlying link layer. OLSRv2, 269 through its use of [RFC6130], may use link layer information and 270 notifications when available and applicable. In addition, OLSRv2 271 uses link metrics that may be derived from link layer or any other 272 information. OLSRv2 does not specify the physical meaning of link 273 metrics, but specifies a means by which new types of link metrics may 274 be specified in the future, but used by OLSRv2 without modification. 276 OLSRv2, as OLSR [RFC3626], inherits its concept of forwarding and 277 relaying from HIPERLAN (a MAC layer protocol) which is standardized 278 by ETSI [HIPERLAN], [HIPERLAN2]. This document does not obsolete 279 [RFC3626] which is left in place for further experimentation. 281 2. Terminology 283 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 284 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 285 "OPTIONAL" in this document are to be interpreted as described in 286 [RFC2119]. 288 All terms introduced in [RFC5444], including "packet", "Packet 289 Header", "message", "Message Header", "Message Body", "Message Type", 290 "message sequence number", "hop limit", "hop count", "Address Block", 291 "TLV Block", "TLV", "Message TLV", "Address Block TLV", "type" (of 292 TLV), "type extension" (of TLV), "value" (of TLV), "address", 293 "address prefix", and "address object" are to be interpreted as 294 described there. 296 All terms introduced in [RFC6130], including "interface", "MANET 297 interface", "network address", "link", "symmetric link", "symmetric 298 1-hop neighbor", "symmetric 2-hop neighbor", "symmetric 1-hop 299 neighborhood" "constant", "interface parameter", "router parameter", 300 "Information Base", and "HELLO message" are to be interpreted as 301 described there. 303 Additionally, this specification uses the following terminology: 305 Router: 306 A MANET router which implements this protocol. 308 OLSRv2 interface: 309 A MANET interface running this protocol. A router running this 310 protocol MUST have at least one OLSRv2 interface. 312 Routable address: 313 A network address which may be used as the destination of a data 314 packet. A router which implements this protocol will need to 315 distinguish a routable address from a non-routable address by 316 direct inspection of the network address, based on global scope 317 address allocations by IANA and/or administrative configuration 318 (consistently across the MANET). Broadcast and multicast 319 addresses, and addresses which are limited in scope to less than 320 the entire MANET, MUST NOT be considered as routable addresses. 321 Anycast addresses may be considered as routable addresses. 323 Originator address: 324 An address which is unique (within the MANET) to a router. A 325 router MUST select an originator address; it MAY choose one of its 326 interface addresses as its originator address; it MAY select 327 either a routable or non-routable address. A broadcast, multicast 328 or anycast address MUST NOT be chosen as an originator address. 329 If the router selects a routable address then this MUST be one 330 which the router will accept as destination. An originator 331 address MUST NOT have a prefix length, except for when included in 332 an Address Block where it MAY be associated with a prefix of 333 maximum prefix length (e.g., if the originator address is an IPv6 334 address, it MUST have either no prefix length, or have a prefix 335 length of 128). 337 Message originator address: 338 The originator address of the router which created a message, as 339 deduced from that message by its recipient. For all messages used 340 in this specification, including HELLO messages defined in 341 [RFC6130], the recipient MUST be able to deduce an originator 342 address. The message originator address will usually be included 343 in the message as its element as defined in 344 [RFC5444]. However, an exceptional case, which does not add a 345 element to a HELLO message, may be used by a 346 router that only has a single address. 348 Willingness: 349 A numerical value between WILL_NEVER and WILL_ALWAYS (both 350 inclusive), that represents the router's willingness to be 351 selected as an MPR. A router has separate willingness values to 352 be a flooding MPR and a routing MPR. 354 Willing symmetric 1-hop neighbor: 355 A symmetric 1-hop neighbor that has willingness not equal to 356 WILL_NEVER. 358 Multipoint relay (MPR): 359 A router, X, is an MPR for a router, Y, if router Y has indicated 360 its selection of router X as an MPR in a recent HELLO message. 361 Router X may be a flooding MPR for Y if it is indicated to 362 participate in the flooding process of messages received from 363 router Y, or it may be a routing MPR for Y, if it is indicated to 364 declare link-state information for the link from X to Y. It may 365 also be both at the same time. 367 MPR selector: 368 A router, Y, is a flooding/routing MPR selector of router X if 369 router Y has selected router X as a flooding/routing MPR. 371 MPR flooding: 372 The optimized MANET-wide information distribution mechanism, 373 employed by this protocol, in which a message is relayed by only a 374 reduced subset of the routers in the network. MPR flooding is the 375 mechanism by which flooding reduction is achieved. 377 EXPIRED: 378 Indicates that a timer is set to a value clearly preceding the 379 current time (e.g., current time - 1). 381 This specification employs the same notational conventions as in 382 [RFC5444] and [RFC6130]. 384 3. Applicability Statement 386 This document specifies OLSRv2, a proactive routing protocol intended 387 for use in mobile ad hoc networks (MANETs) [RFC2501]. The protocol's 388 applicability is determined by its characteristics, which are that 389 this protocol: 391 o Is designed to work in networks with a dynamic topology, and in 392 which messages may be lost, such as due to collisions over 393 wireless media. 395 o Supports routers that each have one or more participating OLSRv2 396 interfaces, which will consist of some or all of its MANET 397 interfaces using [RFC6130]. The set of a router's OLSRv2 398 interfaces, and the sets of its other MANET and non-MANET 399 interfaces, may change over time. Each interface may have one or 400 more network addresses (which may have prefix lengths), and these 401 may also be dynamically changing. 403 o Enables hop-by-hop routing, i.e., each router can use its local 404 information provided by this protocol to route packets. 406 o Continuously maintains routes to all destinations in the network, 407 i.e., routes are instantly available and data traffic is subject 408 to no delays due to route discovery. Consequently, no data 409 traffic buffering is required. 411 o Supports routers that have non-OLSRv2 interfaces that may be local 412 to a router or that can serve as gateways towards other networks. 414 o Enables the use of bidirectional additive link metrics to use 415 shortest distance routes (i.e., routes with smallest total of link 416 metrics). Incoming link metric values are to be determined by a 417 process outside this specification. 419 o Is optimized for large and dense networks; the larger and more 420 dense a network, the more optimization can be achieved by using 421 MPRs, compared to the classic link state algorithm [MPR]. 423 o Uses [RFC5444] as described in its "Intended Usage" appendix and 424 by [RFC5498]. 426 o Allows "external" and "internal" extensibility (adding new message 427 types and adding information to existing messages) as enabled by 428 [RFC5444]. 430 o Is designed to work in a completely distributed manner, and does 431 not depend on any central entity. 433 4. Protocol Overview and Functioning 435 The objectives of this protocol are for each router to: 437 o Identify all destinations in the network. 439 o Identify a sufficient subset of links in the network, in order 440 that shortest routes can be calculated to all available 441 destinations. 443 o Provide a Routing Set, containing these shortest routes from this 444 router to all destinations (routable addresses and local links). 446 4.1. Overview 448 These objectives are achieved, for each router, by: 450 o Using [RFC6130] to identify symmetric 1-hop neighbors and 451 symmetric 2-hop neighbors. 453 o Reporting its participation in OLSRv2, and its willingness to be a 454 flooding MPR and to be a routing MPR, by extending the HELLO 455 messages defined in [RFC6130], by the addition of an MPR_WILLING 456 Message TLV. The router's "flooding willingness" indicates how 457 willing it is to participate in MPR flooding. The router's 458 "routing willingness" indicates how willing it is to be an 459 intermediate router for routing. Note that a router is still able 460 to be a routing source or destination, even if unwilling to 461 perform either function. 463 o Extending the HELLO messages defined in [RFC6130] to allow the 464 addition of directional link metrics to advertised links with 465 other routers participating in OLSRv2, and to indicate which link 466 metric type is being used by those routers. Both incoming and 467 outgoing link metrics may be reported, the former determined by 468 the advertising router. 470 o Selecting flooding MPRs and routing MPRs from among its willing 471 symmetric 1-hop neighbors such that, for each set of MPRs, all 472 symmetric 2-hop neighbors are reachable either directly or via at 473 least one selected MPR, using a path of appropriate minimum total 474 metric for at least routing MPR selection. An analysis and 475 examples of MPR selection algorithms are given in [MPR]; a 476 suggested algorithm, appropriately adapted for each set of MPRs, 477 is included in Appendix B of this specification. Note that it is 478 not necessary for routers to use the same algorithm in order to 479 interoperate in the same MANET, but each such algorithm must have 480 the appropriate properties, described in Section 18. 482 o Signaling its flooding MPR and routing MPR selections, by 483 extending the HELLO messages defined in [RFC6130] to report this 484 information by the addition of MPR Address Block TLV(s) associated 485 with the appropriate network addresses. 487 o Extracting its flooding MPR selectors and routing MPR selectors 488 from received HELLO messages, using the included MPR Address Block 489 TLV(s). 491 o Defining a TC (Topology Control) Message Type using the message 492 format specified in [RFC5444]. TC messages are used to 493 periodically signal links between routing MPR selectors and itself 494 throughout the MANET. This signaling includes suitable 495 directional neighbor metrics (the best link metric in that 496 direction between those routers). 498 o Allowing its TC messages, as well as HELLO messages, to be 499 included in packets specified in [RFC5444], using the "manet" IP 500 protocol or UDP port as specified in [RFC5498]. 502 o Diffusing TC messages by using a flooding reduction mechanism, 503 denoted "MPR flooding"; only the flooding MPRs of a router will 504 retransmit messages received from (i.e., originated or last 505 relayed by) that router. 507 Note that the indicated extensions to [RFC6130] are of forms 508 permitted by that specification. 510 This specification defines: 512 o The requirement to use [RFC6130], its parameters, constants, HELLO 513 messages, and Information Bases, each as extended in this 514 specification. 516 o Two new Information Bases: the Topology Information Base and the 517 Received Message Information Base. 519 o TC messages, which are used for MANET wide signaling (using MPR 520 flooding) of selected topology (link state) information. 522 o A requirement for each router to have an originator address to be 523 included in, or deducible from, HELLO messages and TC messages. 525 o The specification of new Message TLVs and Address Block TLVs that 526 are used in HELLO messages and TC messages, including for 527 reporting neighbor status, MPR selection, external gateways, link 528 metrics, willingness to be an MPR, and content sequence numbers. 529 Note that the generation of (incoming) link metric values is to be 530 undertaken by a process outside this specification; this 531 specification concerns only the distribution and use of those 532 metrics. 534 o The generation of TC messages from the appropriate information in 535 the Information Bases. 537 o The updating of the Topology Information Base according to 538 received TC messages. 540 o The MPR flooding mechanism, including the inclusion of message 541 originator address and sequence number to manage duplicate 542 messages, using information recorded in the Received Message 543 Information Base. 545 o The response to other events, such as the expiration of 546 information in the Information Bases. 548 This protocol inherits the stability of a link state algorithm, and 549 has the advantage of having routes immediately available when needed, 550 due to its proactive nature. 552 This protocol only interacts with IP through routing table 553 management, and the use of the sending IP address for IP datagrams 554 containing messages used by this specification. 556 4.2. Routers and Interfaces 558 In order for a router to participate in a MANET using this protocol 559 it must have at least one, and possibly more, OLSRv2 interfaces. 560 Each OLSRv2 interface: 562 o Is a MANET interface, as specified in [RFC6130]. In particular it 563 must be configured with one or more network addresses; these 564 addresses must each be specific to this router, and must include 565 any address that will be used as the sending address of any IP 566 packet sent on this OLSRv2 interface. 568 o Has a number of interface parameters, adding to those specified in 569 [RFC6130]. 571 o Has an Interface Information Base, extending that specified in 572 [RFC6130]. 574 o Generates and processes HELLO messages according to [RFC6130], 575 extended as specified in Section 15. 577 In addition to a set of OLSRv2 interfaces as described above, each 578 router: 580 o May have one or more non-OLSRv2 interfaces (which may include 581 MANET interfaces and/or non-MANET interfaces) and/or local 582 attached networks for which this router can accept IP packets. 583 All routable addresses for which the router is to accept IP 584 packets must be used as an (OLSRv2 or non-OLSRv2) interface 585 network address, or as an address of a local attached network of 586 the router. 588 o Has a number of router parameters, adding to those specified in 589 [RFC6130]. 591 o Has a Local Information Base, extending that specified in 592 [RFC6130], including selection of an originator address and 593 recording any locally attached networks. 595 o Has a Neighbor Information Base, extending that specified in 596 [RFC6130] to record MPR selection and advertisement information. 598 o Has a Topology Information Base, recording information received in 599 TC messages. 601 o Has a Received Message Information Base, recording information 602 about received messages to ensure that each TC message is only 603 processed once, and forwarded at most once on each OLSRv2 604 interface, by a router. 606 o Generates, receives, and processes TC messages. 608 4.3. Information Base Overview 610 Each router maintains the Information Bases described in the 611 following sections. These are used for describing the protocol in 612 this specification. An implementation of this protocol may maintain 613 this information in the indicated form, or in any other organization 614 which offers access to this information. In particular, note that it 615 is not necessary to remove Tuples from Sets at the exact time 616 indicated, only to behave as if the Tuples were removed at that time. 618 4.3.1. Local Information Base 620 The Local Information Base is specified in [RFC6130], and contains a 621 router's local configuration. It is extended in this specification 622 to also record an originator address, and to include a router's: 624 o Originator Set, containing addresses that were recently used as 625 this router's originator address, and is used, together with the 626 router's current originator address, to enable a router to 627 recognize and discard control traffic which was originated by the 628 router itself. 630 o Local Attached Network Set, containing network addresses of 631 networks to which this router can act as a gateway, and advertises 632 in its TC messages. 634 4.3.2. Interface Information Bases 636 The Interface Information Base for each OLSRv2 interface is as 637 specified in [RFC6130], extended to also record, in each Link Set, 638 link metric values (incoming and outgoing) and flooding MPR selector 639 information. 641 4.3.3. Neighbor Information Base 643 The Neighbor Information Base is specified in [RFC6130], and is 644 extended to also record, in the Neighbor Tuple for each neighbor: 646 o Its originator address. 648 o Neighbor metric values, these being the minimum of the link metric 649 values in the indicated direction for all symmetric 1-hop links 650 with that neighbor. 652 o Its willingness to be a flooding MPR and to be a routing MPR. 654 o Whether it has been selected by this router as a flooding MPR or 655 as a routing MPR, and whether it is a routing MPR selector of this 656 router. (Whether it is a flooding MPR selector of this neighbor 657 is recorded in the Interface Information Base.) 659 o Whether it is to be advertised in TC messages sent by this router. 661 4.3.4. Topology Information Base 663 The Topology Information Base in each router contains: 665 o An Advertising Remote Router Set, recording each remote router 666 from which TC messages have been received. This is used in order 667 to determine if a received TC message contains fresh or outdated 668 information; a received TC message is ignored in the latter case. 670 o A Router Topology Set, recording links between routers in the 671 MANET, as described by received TC messages. 673 o A Routable Address Topology Set, recording routable addresses in 674 the MANET (available as IP packet destinations) and from which 675 remote router these routable addresses can be directly reached 676 (i.e., in a single IP hop from that remote router), as reported by 677 received TC messages. 679 o An Attached Network Set, recording networks to which a remote 680 router has advertised that it may act as a gateway. These 681 networks may be reached in one or more IP hops from that remote 682 router. 684 o A Routing Set, recording routes from this router to all available 685 destinations. The IP routing table is to be updated using this 686 Routing Set. (A router may choose to use any or all destination 687 network addresses in the Routing Set to update the IP routing 688 table, this selection is outside the scope of this specification.) 690 The purpose of the Topology Information Base is to record information 691 used, in addition to that in the Local Information Base, the 692 Interface Information Bases and the Neighbor Information Base, to 693 construct the Routing Set (which is also included in the Topology 694 Information Base). 696 This specification describes the calculation of the Routing Set based 697 on a Topology Graph constructed in two phases. First, a "backbone" 698 graph representing the routers in the MANET, and the connectivity 699 between them, is constructed from the Local Information Base, the 700 Neighbor Information Base and the Router Topology Set. Second, this 701 graph is "decorated" with additional destination network addresses 702 using the Local Information Base, the Routable Address Topology Set 703 and the Attached Network Set. 705 The Topology Graph does not need to be recorded in the Topology 706 Information Base, it can either be constructed as required when the 707 Routing Set is to be changed, or need not be explicitly constructed 708 (as illustrated in Appendix C). An implementation may however 709 construct and retain the Topology Graph if preferred. 711 4.3.5. Received Message Information Base 713 The Received Message Information Base in each router contains: 715 o A Received Set for each OLSRv2 interface, describing TC messages 716 received by this router on that OLSRv2 interface. 718 o A Processed Set, describing TC messages processed by this router. 720 o A Forwarded Set, describing TC messages forwarded by this router. 722 The Received Message Information Base serves the MPR flooding 723 mechanism by ensuring that received messages are forwarded at most 724 once by a router, and also ensures that received messages are 725 processed exactly once by a router. The Received Message Information 726 Base may also record information about other Message Types that use 727 the MPR flooding mechanism. 729 4.4. Signaling Overview 731 This protocol generates and processes HELLO messages according to 732 [RFC6130]. HELLO messages transmitted on OLSRv2 interfaces are 733 extended according to Section 15 of this specification to include an 734 originator address, link metrics, and MPR selection information. 736 This specification defines a single Message Type, the TC message. TC 737 messages are sent by their originating router proactively, at a 738 regular interval, on all OLSRv2 interfaces. This interval may be 739 fixed, or may be dynamic, for example it may be backed off due to 740 congestion or network stability. TC messages may also be sent as a 741 response to a change in the router itself, or its advertised 742 symmetric 1-hop neighborhood, for example on first being selected as 743 a routing MPR. 745 Because TC messages are sent periodically, this protocol is tolerant 746 of unreliable transmissions of TC messages. Message losses may occur 747 more frequently in wireless networks due to collisions or other 748 transmission problems. This protocol may use "jitter", randomized 749 adjustments to message transmission times, to reduce the incidence of 750 collisions, as specified in [RFC5148]. 752 This protocol is tolerant of out of sequence delivery of TC messages 753 due to in transit message reordering. Each router maintains an 754 Advertised Neighbor Sequence Number (ANSN) that is incremented when 755 its recorded neighbor information that is to be included in its TC 756 messages changes. This ANSN is included in the router's TC messages. 757 The recipient of a TC message can use this included ANSN to identify 758 which of the information it has received is most recent, even if 759 messages have been reordered while in transit. Only the most recent 760 information received is used, older information received later is 761 discarded. 763 TC messages may be "complete" or "incomplete". A complete TC message 764 advertises all of the originating router's routing MPR selectors, it 765 may also advertise other symmetric 1-hop neighbors. Complete TC 766 messages are generated periodically (and also, optionally, in 767 response to symmetric 1-hop neighborhood changes). Incomplete TC 768 messages may be used to report additions to advertised information, 769 without repeating unchanged information. 771 TC messages, and HELLO messages as extended by this specification, 772 define (by inclusion, or by deduction when having a single address) 773 an originator address for the router that created the message. A TC 774 message reports both the originator addresses and routable addresses 775 of its advertised neighbors, distinguishing the two using an Address 776 Block TLV (an address may be both routable and an originator 777 address). TC messages also report the originator's locally attached 778 networks. 780 TC messages are MPR flooded throughout the MANET. A router 781 retransmits a TC message received on an OLSRv2 interface if and only 782 if the message did not originate at this router and has not been 783 previously forwarded by this router, this is the first time the 784 message has been received on this OLSRv2 interface, and the message 785 is received from (i.e., originated from or was last relayed by) one 786 of this router's flooding MPR selectors. 788 Some TC messages may be MPR flooded over only part of the network, 789 e.g., allowing a router to ensure that nearer routers are kept more 790 up to date than distant routers, such as is used in Fisheye State 791 Routing [FSR] and Fuzzy Sighted Link State routing [FSLS]. This is 792 enabled using [RFC5497]. 794 TC messages include outgoing neighbor metrics that will be used in 795 the selection of routes. 797 4.5. Link Metrics 799 OLSRv1 [RFC3626] created minimum hop routes to destinations. However 800 in many, if not most, circumstances, better routes (in terms of 801 quality of service for end users) can be created by use of link 802 metrics. 804 OLSRv2, as defined in this specification, supports metric-based 805 routing, i.e., it allows links to each have a chosen metric. Link 806 metrics as defined in OLSRv2 are additive, and the routes that are to 807 be created are those with the minimum sum of the link metrics along 808 that route. 810 Link metrics are defined to be directional; the link metric from one 811 router to another may be different from that on the reverse link. 812 The link metric is assessed at the receiver, as on a (typically) 813 wireless link, that is the better informed as to link information. 814 Both incoming and outgoing link information is used by OLSRv2, the 815 distinctions in this specification must be clearly followed. 817 This specification also defines both incoming and outgoing neighbor 818 metrics for each symmetric 1-hop neighbor, these being the minimum 819 value of the link metrics in the same direction for all symmetric 820 links with that neighbor. Note that this means that all neighbor 821 metric values are link metric values and that specification of, for 822 example, link metric value encoding also includes encoding of 823 neighbor metric values. 825 This specification does not define the nature of the link metric. 826 However, this specification allows, through use of the type extension 827 of a defined Address Block TLV, for link metrics with specific 828 meanings to be defined and either allocated by IANA or privately 829 used. Each HELLO or TC message carrying link (or neighbor) metrics 830 thus indicates which link metric information it is carrying, allowing 831 routers to determine if they can interoperate. If link metrics 832 require additional signaling to determine their values, whether in 833 HELLO messages or otherwise, then this is permitted but is outside 834 the scope of this specification. 836 Careful consideration should be given to how to use link metrics. In 837 particular it is advisable to not simply default to use of all links 838 with equal metrics (i.e., hop count) for routing without careful 839 consideration of whether that is appropriate or not. 841 4.6. Flooding MPRs and Routing MPR 843 This specification uses two sets of MPRs: flooding MPRs and routing 844 MPRs. These are selected separately, because: 846 o Flooding MPRs may use metrics, routing MPRs must use metrics. 848 o When flooding MPRs use metrics, these are outgoing link metrics, 849 routing MPRs use incoming neighbor metrics. 851 o Flooding MPRs need not be selected per OLSRv2 interface, routing 852 MPRs must be selected per OLSRv2 interface. 854 4.7. Routing Set Use 856 The purpose of the Routing Set is to determine and record routes 857 (local interface network address and next hop interface network 858 address) to all possible routable addresses advertised by this 859 protocol, as well as of all destinations that are local, i.e., within 860 one hop, to the router (whether using routable addresses or not). 861 Only symmetric links are used in such routes. 863 It is intended that the Routing Set can be used for IP packet 864 routing, by using its contents to update the IP routing table. That 865 update, and whether any Routing Tuples are not used in the IP routing 866 table, is outside the scope of this specification. 868 The signaling in this specification has been designed so that a 869 "backbone" Topology Graph of routers, each identified by its 870 originator address, with at most one direct connection between any 871 pair of routers, can be constructed (from the Neighbor Set and the 872 Router Topology Set) using a suitable minimum path length algorithm. 873 This Topology Graph can then have other network addresses (routable, 874 or of symmetric 1-hop neighbors) added to it (using the Interface 875 Information Bases, the Routable Address Topology Set and the Attached 876 Network Set). 878 5. Protocol Parameters and Constants 880 The parameters and constants used in this specification are those 881 defined in [RFC6130] plus those defined in this section. The 882 separation in [RFC6130] into interface parameters, router parameters 883 and constants is also used in this specification. 885 As for the parameters in [RFC6130], parameters defined in this 886 specification MAY be changed dynamically by a router, and need not be 887 the same on different routers, even in the same MANET, or, for 888 interface parameters, on different interfaces of the same router. 890 5.1. Protocol and Port Numbers 892 This protocol specifies TC messages, which are included in packets as 893 defined by [RFC5444]. These packets MUST be sent either using the 894 "manet" protocol number or the "manet" UDP well-known port number, as 895 specified in [RFC5498]. 897 TC messages and HELLO messages [RFC6130] MUST, in a given MANET, 898 either both be using IP or both be using UDP, in order that it is 899 possible to combine messages of both protocols into the same 900 [RFC5444] packet for transmission. 902 5.2. Multicast Address 904 This protocol specifies TC messages, which are included in packets as 905 defined by [RFC5444]. These packets MAY be transmitted using the 906 Link-Local multicast address "LL-MANET-Routers", as specified in 907 [RFC5498]. 909 5.3. Interface Parameters 911 A single additional interface parameter is specified for OLSRv2 912 interfaces only. 914 5.3.1. Received Message Validity Time 916 The following parameter manages the validity time of recorded 917 received message information: 919 RX_HOLD_TIME: 920 The period after receipt of a message by the appropriate OLSRv2 921 interface of this router for which that information is recorded, 922 in order that the message is recognized as having been previously 923 received on this OLSRv2 interface. 925 The following constraints apply to this parameter: 927 o RX_HOLD_TIME > 0 928 o RX_HOLD_TIME SHOULD be greater than the maximum difference in time 929 that a message may take to traverse the MANET, taking into account 930 any message forwarding jitter as well as propagation, queuing, and 931 processing delays. 933 5.4. Router Parameters 935 The following router parameters are specified for routers. 937 5.4.1. Local History Times 939 The following router parameter manages the time for which local 940 information is retained: 942 O_HOLD_TIME: 943 The time for which a recently used and replaced originator address 944 is used to recognize the router's own messages. 946 The following constraint applies to this parameter: 948 o O_HOLD_TIME > 0 950 5.4.2. Link Metric Parameters 952 All routes found using this specification use a single link metric 953 type that is specified by the router parameter LINK_METRIC_TYPE, 954 which may take any value from 0 to 255, both inclusive. 956 5.4.3. Message Intervals 958 The following parameters regulate TC message transmissions by a 959 router. TC messages are usually sent periodically, but MAY also be 960 sent in response to changes in the router's Neighbor Set and/or Local 961 Attached Network Set. In a highly dynamic network, and with a larger 962 value of the parameter TC_INTERVAL and a smaller value of the 963 parameter TC_MIN_INTERVAL, TC messages MAY be transmitted more often 964 in response to changes than periodically. However, because a router 965 has no knowledge of, for example, routers remote to it (i.e., beyond 966 two hops away) joining the network, TC messages MUST NOT be sent 967 purely responsively. 969 TC_INTERVAL: 970 The maximum time between the transmission of two successive TC 971 messages by this router. When no TC messages are sent in response 972 to local network changes (by design, or because the local network 973 is not changing) then TC messages MUST be sent at a regular 974 interval TC_INTERVAL, possibly modified by jitter as specified in 975 [RFC5148]. 977 TC_MIN_INTERVAL: 978 The minimum interval between transmission of two successive TC 979 messages by this router. (This minimum interval MAY be modified 980 by jitter, as specified in [RFC5148].) 982 The following constraints apply to these parameters: 984 o TC_INTERVAL > 0 986 o 0 <= TC_MIN_INTERVAL <= TC_INTERVAL 988 o If TLVs with Type = INTERVAL_TIME, as defined in [RFC5497], are 989 included in TC messages, then TC_INTERVAL MUST be representable by 990 way of the exponent-mantissa notation described in Section 5 of 991 [RFC5497]. 993 5.4.4. Advertised Information Validity Times 995 The following parameters manage the validity time of information 996 advertised in TC messages: 998 T_HOLD_TIME: 999 Used as the minimum value in the TLV with Type = VALIDITY_TIME 1000 included in all TC messages sent by this router. If a single 1001 value of parameter TC_HOP_LIMIT (see Section 5.4.7) is used then 1002 this will be the only value in that TLV. 1004 A_HOLD_TIME: 1005 The period during which TC messages are sent after they no longer 1006 have any advertised information to report, but are sent in order 1007 to accelerate outdated information removal by other routers. 1009 The following constraints apply to these parameters: 1011 o T_HOLD_TIME > 0 1013 o A_HOLD_TIME >= 0 1015 o T_HOLD_TIME >= TC_INTERVAL 1017 o If TC messages can be lost, then both T_HOLD_TIME and A_HOLD_TIME 1018 SHOULD be significantly greater than TC_INTERVAL; a value >= 3 x 1019 TC_INTERVAL is RECOMMENDED. 1021 o T_HOLD_TIME MUST be representable by way of the exponent-mantissa 1022 notation described in Section 5 of [RFC5497]. 1024 5.4.5. Processing and Forwarding Validity Times 1026 The following parameters manage the processing and forwarding 1027 validity time of recorded message information: 1029 P_HOLD_TIME: 1030 The period after receipt of a message that is processed by this 1031 router for which that information is recorded, in order that the 1032 message is not processed again if received again. 1034 F_HOLD_TIME: 1035 The period after receipt of a message that is forwarded by this 1036 router for which that information is recorded, in order that the 1037 message is not forwarded again if received again. 1039 The following constraints apply to these parameters: 1041 o P_HOLD_TIME > 0 1043 o F_HOLD_TIME > 0 1045 o Both of these parameters SHOULD be greater than the maximum 1046 difference in time that a message may take to traverse the MANET, 1047 taking into account any message forwarding jitter as well as 1048 propagation, queuing, and processing delays. 1050 5.4.6. Jitter 1052 If jitter, as defined in [RFC5148], is used then the governing jitter 1053 parameters are as follows: 1055 TP_MAXJITTER: 1056 Represents the value of MAXJITTER used in [RFC5148] for 1057 periodically generated TC messages sent by this router. 1059 TT_MAXJITTER: 1060 Represents the value of MAXJITTER used in [RFC5148] for externally 1061 triggered TC messages sent by this router. 1063 F_MAXJITTER: 1064 Represents the default value of MAXJITTER used in [RFC5148] for 1065 messages forwarded by this router. However, before using 1066 F_MAXJITTER a router MAY attempt to deduce a more appropriate 1067 value of MAXJITTER, for example based on any TLVs with Type = 1068 INTERVAL_TIME or Type = VALIDITY_TIME contained in the message to 1069 be forwarded. 1071 For constraints on these parameters see [RFC5148]. 1073 5.4.7. Hop Limit 1075 The parameter TC_HOP_LIMIT is the hop limit set in each TC message. 1076 TC_HOP_LIMIT MAY be a single fixed value, or MAY be different in TC 1077 messages sent by the same router. However each other router, at any 1078 hop count distance, MUST see a regular pattern of TC messages in 1079 order that meaningful values of TLVs with Type = INTERVAL_TIME and 1080 Type = VALIDITY_TIME at each hop count distance can be included as 1081 defined in [RFC5497]. Thus the pattern of TC_HOP_LIMIT MUST be 1082 defined to have this property. For example the repeating pattern 1083 (255 4 4) satisfies this property (having period TC_INTERVAL at hop 1084 counts up to 4, inclusive, and 3 x TC_INTERVAL at hop counts greater 1085 than 4), but the repeating pattern (255 255 4 4) does not satisfy 1086 this property because at hop counts greater than 4, message intervals 1087 are alternately TC_INTERVAL and 3 x TC_INTERVAL. 1089 The following constraints apply to this parameter: 1091 o The maximum value of TC_HOP_LIMIT >= the network diameter in hops, 1092 a value of 255 is RECOMMENDED. Note that if using a pattern of 1093 different values of TC_HOP_LIMIT as described above, then only the 1094 maximum value in the pattern is so constrained. 1096 o All values of TC_HOP_LIMIT >= 2. 1098 5.4.8. Willingness 1100 Each router has two willingness parameters: WILL_FLOODING and 1101 WILL_ROUTING, each of which MUST be in the range WILL_NEVER to 1102 WILL_ALWAYS, inclusive. 1104 WILL_FLOODING represents the router's willingness to be selected as a 1105 flooding MPR and hence to participate in MPR flooding, in particular 1106 of TC messages. 1108 WILL_ROUTING represents the router's willingness to be selected as a 1109 routing MPR and hence to be an intermediate router on routes. 1111 In either case, the higher the value, the greater the router's 1112 willingness to be a flooding or routing MPR, respectively. If a 1113 router has a willingness value of WILL_NEVER (the lowest possible 1114 value) it does not perform the corresponding task. A MANET using 1115 this protocol with too many routers having either willingness value 1116 equal to WILL_NEVER will not function; it MUST be ensured, by 1117 administrative or other means, that this does not happen. 1119 Note that how many routers having either willingness value equal to 1120 WILL_NEVER is "too many" depends on the network topology - which, in 1121 a MANET may change dynamically. Willingness is intended to enable 1122 that certain routers (e.g., routers that have generous resources, 1123 such as a permanent power supply) can be configured to assume more of 1124 the network operation, while others (e.g., routers that have lesser 1125 resources, such as are battery operated) can avoid such tasks. A 1126 general guideline would be that only if a router is not actually able 1127 to assume the task (flooding or routing) should it be configured with 1128 the corresponding willingness WILL_NEVER. 1130 If a router has a willingness value equal to WILL_ALWAYS (the highest 1131 possible value) then it will always be selected as a flooding or 1132 routing MPR, respectively, by all symmetric 1-hop neighbors. 1134 In a MANET in which all routers have WILL_FLOODING = WILL_ALWAYS, 1135 flooding reduction will effectively be disabled, and flooding will 1136 perform as blind flooding. 1138 In a MANET in which all routers have WILL_ROUTING = WILL_ALWAYS, 1139 topology reduction will effectively be disabled, and all routers will 1140 advertise all of their links in TC messages. 1142 A router that has WILL_ROUTING = WILL_NEVER will not act as an 1143 intermediate router in the MANET. Such a router can, act as a 1144 source, destination or gateway to another routing domain. 1146 Different routers MAY have different values for WILL_FLOODING and/or 1147 WILL_ROUTING. 1149 The following constraints apply to these parameters: 1151 o WILL_NEVER <= WILL_FLOODING <= WILL_ALWAYS 1153 o WILL_NEVER <= WILL_ROUTING <= WILL_ALWAYS 1155 5.5. Parameter Change Constraints 1157 If protocol parameters are changed dynamically, then the constraints 1158 in this section apply. 1160 RX_HOLD_TIME 1162 * If RX_HOLD_TIME for an OLSRv2 interface changes, then the 1163 expiry time for all Received Tuples for that OLSRv2 interface 1164 MAY be changed. 1166 O_HOLD_TIME 1168 * If O_HOLD_TIME changes, then the expiry time for all Originator 1169 Tuples MAY be changed. 1171 TC_INTERVAL 1173 * If TC_INTERVAL increases, then the next TC message generated by 1174 this router MUST be generated according to the previous, 1175 shorter, TC_INTERVAL. Additional subsequent TC messages MAY be 1176 generated according to the previous, shorter, TC_INTERVAL. 1178 * If TC_INTERVAL decreases, then the following TC messages from 1179 this router MUST be generated according to the current, 1180 shorter, TC_INTERVAL. 1182 P_HOLD_TIME 1184 * If P_HOLD_TIME changes, then the expiry time for all Processed 1185 Tuples MAY be changed. 1187 F_HOLD_TIME 1189 * If F_HOLD_TIME changes, then the expiry time for all Forwarded 1190 Tuples MAY be changed. 1192 TP_MAXJITTER 1194 * If TP_MAXJITTER changes, then the periodic TC message schedule 1195 on this router MAY be changed immediately. 1197 TT_MAXJITTER 1199 * If TT_MAXJITTER changes, then externally triggered TC messages 1200 on this router MAY be rescheduled. 1202 F_MAXJITTER 1204 * If F_MAXJITTER changes, then TC messages waiting to be 1205 forwarded with a delay based on this parameter MAY be 1206 rescheduled. 1208 TC_HOP_LIMIT 1210 * If TC_HOP_LIMIT changes, and the router uses multiple values 1211 after the change, then message intervals and validity times 1212 included in TC messages MUST be respected. The simplest way to 1213 do this is to start any new repeating pattern of TC_HOP_LIMIT 1214 values with its largest value. 1216 LINK_METRIC_TYPE 1218 * If LINK_METRIC_TYPE changes, then all link metric information 1219 recorded by the router is invalid. The router MUST take the 1220 following actions, and all consequent actions described in 1221 Section 17 and [RFC6130]. 1223 + For each Link Tuple in any Link Set for an OLSRv2 interface, 1224 either update L_in_metric (the value MAXIMUM_METRIC MAY be 1225 used) or remove the Link Tuple from the Link Set. 1227 + For each Link Tuple that is not removed, set: 1229 - L_out_metric := UNKNOWN_METRIC; 1231 - L_SYM_time := EXPIRED; 1233 - L_MPR_selector := false. 1235 + Remove all Router Topology Tuples, Routable Address Topology 1236 Tuples, Attached Network Tuples and Routing Tuples from 1237 their respective Protocol Sets in the Topology Information 1238 Base. 1240 5.6. Constants 1242 The following constants are specified for routers. Unlike router 1243 parameters, constants MUST NOT change, and MUST be the same on all 1244 routers. 1246 5.6.1. Link Metric Constants 1248 The constant minimum and maximum link metric values are defined by: 1250 o MINIMUM_METRIC := 1 1252 o MAXIMUM_METRIC := 16776960 1254 The symbolic value UNKNOWN_METRIC is defined in Section 6.1. 1256 5.6.2. Willingness Constants 1258 The constant minimum, RECOMMENDED default, and maximum, willingness 1259 values are defined by: 1261 o WILL_NEVER := 0 1263 o WILL_DEFAULT := 7 1265 o WILL_ALWAYS := 15 1267 5.6.3. Time Constant 1269 The constant C (time granularity) is used as specified in [RFC5497]. 1270 It MUST be the same as is used by [RFC6130], with RECOMMENDED value: 1272 o C := 1/1024 second 1274 Note that this parameter is used in the representation of time 1275 intervals. Time values (such as are stored in Protocol Tuples) are 1276 not so represented. A resolution of C in such values is sufficient 1277 (but not necessary) for such values. 1279 6. Link Metric Values 1281 A router records a link metric value for each direction of a link of 1282 which it has knowledge. These link metric values are used to create 1283 metrics for routes by the addition of link metric values. 1285 6.1. Link Metric Representation 1287 Link metrics are reported in messages using a compressed 1288 representation that occupies 12 bits, consisting of a 4 bit field and 1289 an 8 bit field. The compressed representation represents positive 1290 integer values with a minimum value of 1 and a maximum value that is 1291 slightly smaller than the maximum 24 bit value. Only those values 1292 that have exact representation in the compressed form are used. 1293 Route metrics are the summation of no more than 255 link metric 1294 values, and can therefore be represented using no more than 32 bits. 1296 Link and route metrics used in the Information Bases defined in this 1297 specification refer to the uncompressed values, and arithmetic 1298 involving them does likewise, and assumes full precision in the 1299 result. (How an implementation records the values is not part of 1300 this specification, as long as it behaves as if recording 1301 uncompressed values. An implementation can, for example, use 32 bit 1302 values for all link and route metrics.) 1304 In some cases a link metric value may be unknown. This is indicated 1305 in this specification by the symbolic value UNKNOWN_METRIC. An 1306 implementation may use any representation of UNKNOWN_METRIC as it is 1307 never included in messages, or used in any computation. (Possible 1308 representations are zero, or any value greater than the maximum 1309 representable metric value.) 1311 6.2. Link Metric Compressed Form 1313 The 12-bit compressed form of a link metric uses a modified form of a 1314 representation with an 8-bit mantissa (denoted a) and a 4-bit 1315 exponent (denoted b). Note that if represented as the 12 bit value 1316 256b+a then the ordering of those 12 bit values is identical to the 1317 ordering of the represented values. 1319 The value so represented is (257+a)2^b - 256, where ^ denotes 1320 exponentiation. This has a minimum value (when a = 0 and b = 0) of 1321 MINIMUM_METRIC = 1 and a maximum value (when a = 255 and b = 15) of 1322 MAXIMUM_METRIC = 2^24 - 256. 1324 An algorithm for computing a and b for the smallest representable 1325 value not less than a link metric value v such that MINIMUM_METRIC <= 1326 v <= MAXIMUM_METRIC is: 1328 1. Find the smallest integer b such that v + 256 <= 2^(b + 9). 1330 2. Set a := (v - 256(2^b - 1)) / (2^b) - 1, rounded up to the 1331 nearest integer. 1333 7. Local Information Base 1335 The Local Information Base, as defined for each router in [RFC6130], 1336 is extended by this protocol by: 1338 o Recording the router's originator address. The originator address 1339 MUST be unique to this router. It MUST NOT be used by any other 1340 router as an originator address. It MAY be included in any 1341 network address in any I_local_iface_addr_list of this router, it 1342 MUST NOT be included in any network address in any 1343 I_local_iface_addr_list of any other router. It MAY be included 1344 in, but MUST NOT be equal to, the AL_net_addr in any Local 1345 Attached Network Tuple in this or any other router. 1347 o The addition of an Originator Set, defined in Section 7.1, and a 1348 Local Attached Network Set, defined in Section 7.2. 1350 All routable addresses of the router for which it is to accept IP 1351 packets as destination MUST be included in the Local Interface Set or 1352 the Local Attached Network Set. 1354 7.1. Originator Set 1356 A router's Originator Set records addresses that were recently used 1357 as originator addresses by this router. If a router's originator 1358 address is immutable then the Originator Set is always empty and MAY 1359 be omitted. It consists of Originator Tuples: 1361 (O_orig_addr, O_time) 1363 where: 1365 O_orig_addr is a recently used originator address; note that this 1366 does not include a prefix length. 1368 O_time specifies the time at which this Tuple expires and MUST be 1369 removed. 1371 7.2. Local Attached Network Set 1373 A router's Local Attached Network Set records its local non-OLSRv2 1374 interfaces via which it can act as a gateway to other networks. The 1375 Local Attached Network Set MUST be provided to this protocol and MUST 1376 reflect any changes in the router's status. (In cases where the 1377 router's configuration is static, the Local Attached Network Set will 1378 be constant; in cases where the router has no non-OLSRv2 interfaces, 1379 the Local Attached Network Set will be empty.) The Local Attached 1380 Network Set is not modified by this protocol. This protocol will 1381 respond to (externally provided) changes to the Local Attached 1382 Network Set. It consists of Local Attached Network Tuples: 1384 (AL_net_addr, AL_dist, AL_metric) 1386 where: 1388 AL_net_addr is the network address of an attached network which 1389 can be reached via this router. This SHOULD be a routable 1390 address. It is constrained as described below. 1392 AL_dist is the number of hops to the network with network address 1393 AL_net_addr from this router. 1395 AL_metric is the metric of the link to the attached network with 1396 address AL_net_addr from this router. 1398 Attached networks local to this router only (i.e., not reachable 1399 except via this router) SHOULD be treated as local non-MANET 1400 interfaces, and added to the Local Interface Set, as specified in 1401 [RFC6130], rather than be added to the Local Attached Network Set. 1403 Because an attached network is not specific to the router, and may be 1404 outside the MANET, an attached network MAY also be attached to other 1405 routers. Routing to an AL_net_addr will use maximum prefix length 1406 matching; consequently an AL_net_addr MAY include, but MUST NOT equal 1407 or be included in, any network address which is of any interface of 1408 any router (i.e., is included in any I_local_iface_addr_list) or 1409 equal any router's originator address. 1411 It is not the responsibility of this protocol to maintain routes from 1412 this router to networks recorded in the Local Attached Network Set. 1414 Local Attached Neighbor Tuples are removed from the Local Attached 1415 Network Set only when the router's local attached network 1416 configuration changes, i.e., they are not subject to timer-based 1417 expiration or changes due to received messages. 1419 8. Interface Information Base 1421 An Interface Information Base, as defined in [RFC6130], is maintained 1422 for each MANET interface. The Link Set and 2-Hop Set in the 1423 Interface Information Base for an OLSRv2 interface are modified by 1424 this protocol. In some cases it may be convenient to consider these 1425 Sets as also containing these additional elements for other MANET 1426 interfaces, taking the indicated values on creation, but never being 1427 updated. 1429 8.1. Link Set 1431 The Link Set is modified by adding these additional elements to each 1432 Link Tuple: 1434 L_in_metric is the metric of the link from the OLSRv2 interface 1435 with addresses L_neighbor_iface_addr_list to this OLSRv2 1436 interface; 1438 L_out_metric is the metric of the link to the OLSRv2 interface 1439 with addresses L_neighbor_iface_addr_list from this OLSRv2 1440 interface; 1442 L_mpr_selector is a boolean flag, describing if this neighbor has 1443 selected this router as a flooding MPR, i.e., is a flooding MPR 1444 selector of this router. 1446 L_in_metric will be specified by a process that is external to this 1447 specification. Any Link Tuple with L_status = HEARD or L_status = 1448 SYMMETRIC MUST have a specified value of L_in_metric if it is to be 1449 used by this protocol. 1451 A Link Tuple created (but not updated) by [RFC6130] MUST set: 1453 o L_in_metric := UNKNOWN_METRIC; 1455 o L_out_metric := UNKNOWN_METRIC; 1457 o L_mpr_selector := false. 1459 8.2. 2-Hop Set 1461 The 2-Hop Set is modified by adding these additional elements to each 1462 2-Hop Tuple: 1464 N2_in_metric is the neighbor metric from the router with address 1465 N2_2hop_iface_addr to the router with OLSRv2 interface addresses 1466 N2_neighbor_iface_addr_list; 1468 N2_out_metric is the neighbor metric to the router with address 1469 N2_2hop_iface_addr from the router with OLSRv2 interface addresses 1470 N2_neighbor_iface_addr_list. 1472 A 2-Hop Tuple created (but not updated) by [RFC6130] MUST set: 1474 o N2_in_metric := UNKNOWN_METRIC; 1476 o N2_out_metric := UNKNOWN_METRIC. 1478 9. Neighbor Information Base 1480 A Neighbor Information Base, as defined in [RFC6130], is maintained 1481 for each router. It is modified by this protocol by adding these 1482 additional elements to each Neighbor Tuple in the Neighbor Set. In 1483 some cases it may be convenient to consider these Sets as also 1484 containing these additional elements for other MANET interfaces, 1485 taking the indicated values on creation, but never being updated. 1487 N_orig_addr is the neighbor's originator address, which may be 1488 unknown. Note that this originator address does not include a 1489 prefix length; 1491 N_in_metric is the neighbor metric of any link from this neighbor 1492 to an OLSRv2 interface of this router, i.e., the minimum of all 1493 corresponding L_in_metric with L_status = SYMMETRIC and 1494 L_in_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no such 1495 Link Tuples; 1497 N_out_metric is the neighbor metric of any link from an OLSRv2 1498 interface of this router to this neighbor, i.e., the minimum of 1499 all corresponding L_out_metric with L_status = SYMMETRIC and 1500 L_out_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no 1501 such Link Tuples; 1503 N_will_flooding is the neighbor's willingness to be selected as a 1504 flooding MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1505 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1506 information is received from this neighbor; 1508 N_will_routing is the neighbor's willingness to be selected as a 1509 routing MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1510 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1511 information is received from this neighbor; 1513 N_flooding_mpr is a boolean flag, describing if this neighbor is 1514 selected as a flooding MPR by this router; 1516 N_routing_mpr is a boolean flag, describing if this neighbor is 1517 selected as a routing MPR by this router; 1519 N_mpr_selector is a boolean flag, describing if this neighbor has 1520 selected this router as a routing MPR, i.e., is a routing MPR 1521 selector of this router. 1523 N_advertised is a boolean flag, describing if this router has 1524 elected to advertise a link to this neighbor in its TC messages. 1526 A Neighbor Tuple created (but not updated) by [RFC6130] MUST set: 1528 o N_orig_addr := unknown; 1530 o N_in_metric := UNKNOWN_METRIC; 1532 o N_out_metric := UNKNOWN_METRIC; 1534 o N_will_flooding := WILL_NEVER; 1536 o N_will_routing := WILL_NEVER; 1538 o N_routing_mpr := false; 1540 o N_flooding_mpr := false; 1542 o N_mpr_selector := false; 1544 o N_advertised := false. 1546 The Neighbor Information Base also includes a variable, the 1547 Advertised Neighbor Sequence Number (ANSN), whose value is included 1548 in TC messages to indicate the freshness of the information 1549 transmitted. The ANSN is incremented whenever advertised information 1550 (the originator and routable addresses included in Neighbor Tuples 1551 with N_advertised = true, and local attached networks recorded in the 1552 Local Attached Network Set in the Local Information Base) changes, 1553 including addition or removal of such information. 1555 10. Topology Information Base 1557 The Topology Information Base, defined for each router by this 1558 specification, stores information received in TC messages, in the 1559 Advertising Remote Router Set, the Router Topology Set, the Routable 1560 Address Topology Set and the Attached Network Set. 1562 Additionally, a Routing Set is maintained, derived from the 1563 information recorded in the Local Information Base, the Interface 1564 Information Bases, the Neighbor Information Base and the rest of the 1565 Topology Information Base. 1567 10.1. Advertising Remote Router Set 1569 A router's Advertising Remote Router Set records information 1570 describing each remote router in the network that transmits TC 1571 messages, allowing outdated TC messages to be recognized and 1572 discarded. It consists of Advertising Remote Router Tuples: 1574 (AR_orig_addr, AR_seq_number, AR_time) 1576 where: 1578 AR_orig_addr is the originator address of a received TC message, 1579 note that this does not include a prefix length; 1581 AR_seq_number is the greatest ANSN in any TC message received 1582 which originated from the router with originator address 1583 AR_orig_addr (i.e., which contributed to the information contained 1584 in this Tuple); 1586 AR_time is the time at which this Tuple expires and MUST be 1587 removed. 1589 10.2. Router Topology Set 1591 A router's Topology Set records topology information about the links 1592 between routers in the MANET. It consists of Router Topology Tuples: 1594 (TR_from_orig_addr, TR_to_orig_addr, TR_seq_number, TR_metric, 1595 TR_time) 1597 where: 1599 TR_from_orig_addr is the originator address of a router which can 1600 reach the router with originator address TR_to_orig_addr in one 1601 hop, note that this does not include a prefix length; 1603 TR_to_orig_addr is the originator address of a router which can be 1604 reached by the router with originator address TR_to_orig_addr in 1605 one hop, note that this does not include a prefix length; 1607 TR_seq_number is the greatest ANSN in any TC message received 1608 which originated from the router with originator address 1609 TR_from_orig_addr (i.e., which contributed to the information 1610 contained in this Tuple); 1612 TR_metric is the neighbor metric from the router with originator 1613 address TR_from_orig_addr to the router with originator address 1614 TR_to_orig_addr; 1616 TR_time specifies the time at which this Tuple expires and MUST be 1617 removed. 1619 10.3. Routable Address Topology Set 1621 A router's Routable Address Topology Set records topology information 1622 about the routable addresses within the MANET, and via which routers 1623 they may be reached. It consists of Routable Address Topology 1624 Tuples: 1626 (TA_from_orig_addr, TA_dest_addr, TA_seq_number, TA_metric, 1627 TA_time) 1629 where: 1631 TA_from_orig_addr is the originator address of a router which can 1632 reach the router with routable address TA_dest_addr in one hop, 1633 note that this does not include a prefix length; 1635 TA_dest_addr is a routable address of a router which can be 1636 reached by the router with originator address TA_from_orig_addr in 1637 one hop; 1639 TA_seq_number is the greatest ANSN in any TC message received 1640 which originated from the router with originator address 1641 TA_from_orig_addr (i.e., which contributed to the information 1642 contained in this Tuple); 1643 TA_metric is the neighbor metric from the router with originator 1644 address TA_from_orig_addr to the router with OLSRv2 interface 1645 address TA_dest_addr; 1647 TA_time specifies the time at which this Tuple expires and MUST be 1648 removed. 1650 10.4. Attached Network Set 1652 A router's Attached Network Set records information about networks 1653 (which may be outside the MANET) attached to other routers and their 1654 routable addresses. It consists of Attached Network Tuples: 1656 (AN_orig_addr, AN_net_addr, AN_seq_number, AN_dist, AN_metric, 1657 AN_time) 1659 where: 1661 AN_orig_addr is the originator address of a router which can act 1662 as gateway to the network with network address AN_net_addr, note 1663 that this does not include a prefix length; 1665 AN_net_addr is the network address of an attached network, which 1666 may be reached via the router with originator address 1667 AN_orig_addr; 1669 AN_seq_number is the greatest ANSN in any TC message received 1670 which originated from the router with originator address 1671 AN_orig_addr (i.e., which contributed to the information contained 1672 in this Tuple); 1674 AN_dist is the number of hops to the network with network address 1675 AN_net_addr from the router with originator address AN_orig_addr; 1677 AN_metric is the metric of the link from the router with 1678 originator address AN_orig_addr to the attached network with 1679 address AN_net_addr; 1681 AN_time specifies the time at which this Tuple expires and MUST be 1682 removed. 1684 10.5. Routing Set 1686 A router's Routing Set records the first hop along a selected path to 1687 each destination for which any such path is known. It consists of 1688 Routing Tuples: 1690 (R_dest_addr, R_next_iface_addr, R_local_iface_addr, R_dist, 1691 R_metric) 1693 where: 1695 R_dest_addr is the network address of the destination, either the 1696 network address of an interface of a destination router, or the 1697 network address of an attached network; 1699 R_next_iface_addr is the network address of the "next hop" on the 1700 selected path to the destination; 1702 R_local_iface_addr is an address of the local interface over which 1703 an IP packet MUST be sent to reach the destination by the selected 1704 path. 1706 R_dist is the number of hops on the selected path to the 1707 destination; 1709 R_metric is the metric of the route to the destination with 1710 address R_dest_addr. 1712 The Routing Set for a router is derived from the contents of other 1713 Protocol Sets of the router (the Link Sets, the Neighbor Set, the 1714 Router Topology Set, the Routable Address Topology Set, the Attached 1715 Network Set, and OPTIONAL use of the 2-Hop Sets). The Routing Set is 1716 updated (Routing Tuples added or removed, or the complete Routing Set 1717 recalculated) when routing paths are calculated, based on changes to 1718 these other Protocol Sets. Routing Tuples are not subject to timer- 1719 based expiration. 1721 11. Received Message Information Base 1723 The Received Message Information Base, defined by this specification, 1724 records information required to ensure that a message is processed at 1725 most once and is forwarded at most once per OLSRv2 interface of a 1726 router, using MPR flooding. Messages are recorded using their 1727 "signature", consisting of their type, originator address, and 1728 message sequence number. 1730 11.1. Received Set 1732 A router has a Received Set per OLSRv2 interface. Each Received Set 1733 records the signatures of messages which have been received over that 1734 OLSRv2 interface. Each consists of Received Tuples: 1736 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 1738 where: 1740 RX_type is the received Message Type; 1742 RX_orig_addr is the originator address of the received message, 1743 note that this does not include a prefix length; 1745 RX_seq_number is the message sequence number of the received 1746 message; 1748 RX_time specifies the time at which this Tuple expires and MUST be 1749 removed. 1751 11.2. Processed Set 1753 A router has a single Processed Set which records signatures of 1754 messages which have been processed by the router. It consists of 1755 Processed Tuples: 1757 (P_type, P_orig_addr, P_seq_number, P_time) 1759 where: 1761 P_type is the processed Message Type; 1763 P_orig_addr is the originator address of the processed message, 1764 note that this does not include a prefix length; 1766 P_seq_number is the message sequence number of the processed 1767 message; 1769 P_time specifies the time at which this Tuple expires and MUST be 1770 removed. 1772 11.3. Forwarded Set 1774 A router has a single Forwarded Set which records signatures of 1775 messages which have been forwarded by the router. It consists of 1776 Forwarded Tuples: 1778 (F_type, F_orig_addr, F_seq_number, F_time) 1780 where: 1782 F_type is the forwarded Message Type; 1784 F_orig_addr is the originator address of the forwarded message, 1785 note that this does not include a prefix length; 1786 F_seq_number is the message sequence number of the forwarded 1787 message; 1789 F_time specifies the time at which this Tuple expires and MUST be 1790 removed. 1792 12. Information Base Properties 1794 This section describes some additional properties of Information 1795 Bases and their contents. 1797 12.1. Corresponding Protocol Tuples 1799 As part of this specification, in a number of cases there is a 1800 natural correspondence from a Protocol Tuple in one Protocol Set to a 1801 single Protocol Tuple in another Protocol Set, in the same or another 1802 Information Base. The latter Protocol Tuple is referred to as 1803 "corresponding" to the former Protocol Tuple. 1805 Specific examples of corresponding Protocol Tuples include: 1807 o There is a Local Interface Tuple corresponding to each Link Tuple, 1808 where the Link Tuple is in the Link Set for a MANET interface, and 1809 the Local Interface Tuple represents that MANET interface. 1811 o There is a Neighbor Tuple corresponding to each Link Tuple which 1812 has L_HEARD_time not EXPIRED, such that N_neighbor_addr_list 1813 contains L_neighbor_iface_addr_list. 1815 o There is a Link Tuple (in the Link Set in the same Interface 1816 Information Base) corresponding to each 2-Hop Tuple such that 1817 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 1819 o There is a Neighbor Tuple corresponding to each 2-Hop Tuple, such 1820 that N_neighbor_addr_list contains N2_neighbor_iface_addr_list. 1821 (This is the Neighbor Tuple corresponding to the Link Tuple 1822 corresponding to the 2-Hop Tuple.) 1824 o There is an Advertising Remote Router Tuple corresponding to each 1825 Router Topology Tuple such that AR_orig_addr = TR_from_orig_addr. 1827 o There is an Advertising Remote Router Tuple corresponding to each 1828 Routable Address Topology Tuple such that AR_orig_addr = 1829 TA_from_orig_addr. 1831 o There is an Advertising Remote Router Tuple corresponding to each 1832 Attached Network Tuple such that AR_orig_addr = AN_orig_addr. 1834 o There is a Neighbor Tuple corresponding to each Routing Tuple such 1835 that N_neighbor_addr_list contains R_next_iface_addr. 1837 12.2. Address Ownership 1839 Addresses or network addresses with the following properties are 1840 considered as "fully owned" by a router when processing a received 1841 message: 1843 o Equaling its originator address, OR; 1845 o Equaling the O_orig_addr in an Originator Tuple, OR; 1847 o Equaling or being a sub-range of the I_local_iface_addr_list in a 1848 Local Interface Tuple, OR; 1850 o Equaling or being a sub-range of the IR_local_iface_addr in a 1851 Removed Interface Address Tuple, OR; 1853 o Equaling an AL_net_addr in a Local Attached Network Tuple. 1855 Addresses or network addresses with the following properties are 1856 considered as "partially owned" (which may include being fully owned) 1857 by a router when processing a received message: 1859 o Overlapping (equaling or containing) its originator address, OR; 1861 o Overlapping (equaling or containing) the O_orig_addr in an 1862 Originator Tuple, OR; 1864 o Overlapping the I_local_iface_addr_list in a Local Interface 1865 Tuple, OR; 1867 o Overlapping the IR_local_iface_addr in a Removed Interface Address 1868 Tuple, OR; 1870 o Equaling or having as a sub-range an AL_net_addr in a Local 1871 Attached Network Tuple. 1873 13. Packets and Messages 1875 The packet and message format used by this protocol is defined in 1876 [RFC5444]. Except as otherwise noted, options defined in [RFC5444] 1877 may be freely used, in particular alternative formats defined by 1878 packet, message, Address Block and TLV flags. 1880 This section describes the usage of the packets and messages defined 1881 in [RFC5444] by this specification, and the TLVs defined by, and used 1882 in, this specification. 1884 13.1. Messages 1886 Routers using this protocol exchange information through messages. 1887 The message types used by this protocol are the HELLO message and the 1888 TC message. The HELLO message is defined by [RFC6130] and extended 1889 by this specification, see Section 15. The TC message is defined by 1890 this specification, see Section 16. 1892 13.2. Packets 1894 One or more messages sent by a router at the same time SHOULD be 1895 combined into a single packet, subject to any constraints on maximum 1896 packet size (such as derived from the MTU over a local single hop) 1897 that MAY be imposed. These messages may have originated at the 1898 sending router, or have originated at another router and are being 1899 forwarded by the sending router. Messages with different originating 1900 routers MAY be combined for transmission within the same packet. 1901 Messages from other protocols defined using [RFC5444], including but 1902 not limited to [RFC6130], MAY be combined for transmission within the 1903 same packet. This specification does not define or use any contents 1904 of the Packet Header. 1906 Forwarded messages MAY be jittered as described in [RFC5148], 1907 including the observation that the forwarding jitter of all messages 1908 received in a single packet SHOULD be the same. The value of 1909 MAXJITTER used in jittering a forwarded message MAY be based on 1910 information in that message (in particular any Message TLVs with Type 1911 = INTERVAL_TIME or Type = VALIDITY_TIME) or otherwise SHOULD be with 1912 a maximum delay of F_MAXJITTER. A router MAY modify the jitter 1913 applied to a message in order to more efficiently combine messages in 1914 packets, as long as the maximum jitter is not exceeded. 1916 13.3. TLVs 1918 This specification defines two Message TLVs and four Address Block 1919 TLVs. 1921 All references in this specification to TLVs that do not indicate a 1922 type extension, assume Type Extension = 0. TLVs in processed 1923 messages with a type extension which is neither zero as so assumed, 1924 nor a specifically indicated non-zero type extension, are ignored. 1926 13.3.1. Message TLVs 1928 The MPR_WILLING TLV is used in HELLO messages. A message MUST NOT 1929 contain more than one MPR_WILLING TLV. 1931 +-------------+--------------+--------------------------------------+ 1932 | Type | Value Length | Value | 1933 +-------------+--------------+--------------------------------------+ 1934 | MPR_WILLING | 1 octet | Bits 0-3 encode the parameter | 1935 | | | WILL_FLOODING; bits 4-7 encode the | 1936 | | | parameter WILL_ROUTING. | 1937 +-------------+--------------+--------------------------------------+ 1939 Table 1: MPR_WILLING TLV definition 1941 The CONT_SEQ_NUM TLV is used in TC messages. A message MUST NOT 1942 contain more than one CONT_SEQ_NUM TLV. 1944 +--------------+--------------+-------------------------------------+ 1945 | Type | Value Length | Value | 1946 +--------------+--------------+-------------------------------------+ 1947 | CONT_SEQ_NUM | 2 octets | The ANSN contained in the Neighbor | 1948 | | | Information Base. | 1949 +--------------+--------------+-------------------------------------+ 1951 Table 2: CONT_SEQ_NUM TLV definition 1953 13.3.2. Address Block TLVs 1955 The LINK_METRIC TLV is used in HELLO messages and TC messages. It 1956 MAY use any type extension; only LINK_METRIC TLVs with type extension 1957 equal to LINK_METRIC_TYPE will be used by this specification. An 1958 address MUST NOT be associated with more than one link metric value 1959 for any given type extension, kind (link or neighbor) and direction 1960 using this TLV. 1962 +-------------+--------------+--------------------------------------+ 1963 | Type | Value Length | Value | 1964 +-------------+--------------+--------------------------------------+ 1965 | LINK_METRIC | 2 octets | Bits 0-3 indicates kind(s) and | 1966 | | | direction(s), bits 4-7 indicate | 1967 | | | exponent (a), bits 8-15 indicate | 1968 | | | mantissa (b) | 1969 +-------------+--------------+--------------------------------------+ 1971 Table 3: LINK_METRIC TLV definition 1973 The exponent and mantissa use the representation defined in 1974 Section 6. Each bit of the types and directions sub-field, if set 1975 ('1') indicates that the link metric is of the indicated kind and 1976 direction. Any combination of these bits MAY be used. 1978 +-----+-----------------+-----------+ 1979 | Bit | Kind | Direction | 1980 +-----+-----------------+-----------+ 1981 | 0 | Link metric | Incoming | 1982 | 1 | Link metric | Outgoing | 1983 | 2 | Neighbor metric | Incoming | 1984 | 3 | Neighbor metric | Outgoing | 1985 +-----+-----------------+-----------+ 1987 Table 4: LINK_METRIC TLV types and directions 1989 The MPR TLV is used in HELLO messages, and indicates that an address 1990 with which it is associated is of a symmetric 1-hop neighbor that has 1991 been selected as an MPR. 1993 +------+--------------+---------------------------------------------+ 1994 | Type | Value Length | Value | 1995 +------+--------------+---------------------------------------------+ 1996 | MPR | 1 octet | FLOODING indicates that the corresponding | 1997 | | | address is of a neighbor selected as a | 1998 | | | flooding MPR, ROUTING indicates that the | 1999 | | | corresponding address is of a neighbor | 2000 | | | selected as a routing MPR, FLOOD_ROUTE | 2001 | | | indicates both (see Section 24.6). | 2002 +------+--------------+---------------------------------------------+ 2004 Table 5: MPR TLV definition 2006 The NBR_ADDR_TYPE TLV is used in TC messages. 2008 +---------------+--------------+------------------------------------+ 2009 | Type | Value Length | Value | 2010 +---------------+--------------+------------------------------------+ 2011 | NBR_ADDR_TYPE | 1 octet | ORIGINATOR indicates that the | 2012 | | | corresponding address (which MUST | 2013 | | | have maximum prefix length) is an | 2014 | | | originator address, ROUTABLE | 2015 | | | indicates that the corresponding | 2016 | | | network address is a routable | 2017 | | | address of an interface, | 2018 | | | ROUTABLE_ORIG indicates that the | 2019 | | | corresponding address is both (see | 2020 | | | Section 24.6). | 2021 +---------------+--------------+------------------------------------+ 2023 Table 6: NBR_ADDR_TYPE TLV definition 2025 If an address is both an originator address and a routable address, 2026 then it may be associated with either one Address Block TLV with Type 2027 := NBR_ADDR_TYPE and Value := ROUTABLE_ORIG, or with two Address 2028 Block TLVs with Type:= NBR_ADDR_TYPE, one with Value := ORIGINATOR 2029 and one with Value := ROUTABLE. 2031 The GATEWAY TLV is used in TC messages. An address MUST NOT be 2032 associated with more than one hop count value using this TLV. 2034 +---------+--------------+-------------------------------------+ 2035 | Type | Value Length | Value | 2036 +---------+--------------+-------------------------------------+ 2037 | GATEWAY | 1 octet | Number of hops to attached network. | 2038 +---------+--------------+-------------------------------------+ 2040 Table 7: GATEWAY TLV definition 2042 All address objects included in a TC message according to this 2043 specification MUST be associated either with at least one TLV with 2044 Type := NBR_ADDR_TYPE or with a TLV with Type := GATEWAY, but not 2045 both. Any other address objects MAY be included in Address Blocks in 2046 a TC message, but are ignored by this specification. 2048 14. Message Processing and Forwarding 2050 This section describes the optimized flooding operation (MPR 2051 flooding) used when control messages, as instances of [RFC5444], are 2052 intended for MANET wide distribution. This flooding mechanism 2053 defines when a received message is, or is not, processed and/or 2054 forwarded. 2056 This flooding mechanism is used by this protocol and MAY be used by 2057 extensions to this protocol which define, and hence own, other 2058 Message Types, to manage processing and/or forwarding of these 2059 messages. This specification contains elements (P_type, RX_type, 2060 F_type) required only for such usage. 2062 This flooding mechanism is always used for TC messages (see 2063 Section 16). Received HELLO messages (see Section 15) are, unless 2064 invalid, always processed, and never forwarded by this flooding 2065 mechanism. They thus do not need to be recorded in the Received 2066 Message Information Base. 2068 The processing selection and forwarding mechanisms are designed to 2069 only need to parse the Message Header in order to determine whether a 2070 message is to be processed and/or forwarded, and not to have to parse 2071 the Message Body even if the message is forwarded (but not 2072 processed). An implementation MAY only parse the Message Body if 2073 necessary, or MAY always parse the Message Body and reject the 2074 message if it cannot be so parsed, or any other error is identified. 2076 An implementation MUST discard the message silently if it is unable 2077 to parse the Message Header or (if attempted) the Message Body, or if 2078 a message (other than a HELLO message) does not include a message 2079 sequence number. 2081 14.1. Actions when Receiving a Message 2083 On receiving, on an OLSRv2 interface, a message of a type specified 2084 to be using this mechanism, which includes the TC messages defined in 2085 this specification, a router MUST perform the following: 2087 1. If the router recognizes from the originator address of the 2088 message that the message is one which the receiving router itself 2089 originated (i.e., the message originator address is the 2090 originator address of this router, or is an O_orig_addr in an 2091 Originator Tuple) then the message MUST be silently discarded. 2093 2. Otherwise: 2095 1. If the message is of a type which may be processed, then the 2096 message is considered for processing according to 2097 Section 14.2. 2099 2. If the message is of a type which may be forwarded, AND: 2101 + is present and > 1; AND 2103 + is not present or < 255; 2105 then the message is considered for forwarding according to 2106 Section 14.3. 2108 14.2. Message Considered for Processing 2110 If a message (the "current message") is considered for processing, 2111 then the following tasks MUST be performed: 2113 1. If the sending address (i.e., the source address of the IP 2114 datagram containing the current message) does not match (taking 2115 into account any address prefix) a network address in an 2116 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2117 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2118 current message was received (the "receiving interface") then 2119 processing the current message is OPTIONAL. If the current 2120 message is not processed then the following steps are not carried 2121 out. 2123 2. If a Processed Tuple exists with: 2125 * P_type = the Message Type of the current message; AND 2127 * P_orig_addr = the originator address of the current message; 2128 AND 2130 * P_seq_number = the message sequence number of the current 2131 message; 2133 then the current message MUST NOT be processed. 2135 3. Otherwise: 2137 1. Create a Processed Tuple in the Processed Set with: 2139 + P_type := the Message Type of the current message; 2141 + P_orig_addr := the originator address of the current 2142 message; 2144 + P_seq_number := the sequence number of the current 2145 message; 2147 + P_time := current time + P_HOLD_TIME. 2149 2. Process the current message according to its Message Type. 2150 For a TC message this is as defined in Section 16.3. 2152 14.3. Message Considered for Forwarding 2154 If a message (the "current message") is considered for forwarding, 2155 then the following tasks MUST be performed: 2157 1. If the sending address (i.e., the source address of the IP 2158 datagram containing the current message) does not match (taking 2159 into account any address prefix) a network address in an 2160 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2161 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2162 current message was received (the "receiving interface") then the 2163 current message MUST be silently discarded. 2165 2. Otherwise: 2167 1. If a Received Tuple exists in the Received Set for the 2168 receiving interface, with: 2170 + RX_type = the Message Type of the current message; AND 2172 + RX_orig_addr = the originator address of the current 2173 message; AND 2175 + RX_seq_number = the sequence number of the current 2176 message; 2178 then the current message MUST be silently discarded. 2180 2. Otherwise: 2182 1. Create a Received Tuple in the Received Set for the 2183 receiving interface with: 2185 - RX_type := the Message Type of the current message; 2187 - RX_orig_addr := originator address of the current 2188 message; 2190 - RX_seq_number := sequence number of the current 2191 message; 2193 - RX_time := current time + RX_HOLD_TIME. 2195 2. If a Forwarded Tuple exists with: 2197 - F_type = the Message Type of the current message; AND 2199 - F_orig_addr = the originator address of the current 2200 message; AND 2202 - F_seq_number = the sequence number of the current 2203 message. 2205 then the current message MUST be silently discarded. 2207 3. Otherwise if the sending address matches (taking account 2208 of any address prefix) any network address in an 2209 L_neighbor_iface_addr_list of a Link Tuple in the Link 2210 Set for the receiving OLSRv2 interface that has L_status 2211 = SYMMETRIC and whose corresponding Neighbor Tuple has 2212 N_mpr_selector = true, then: 2214 1. Create a Forwarded Tuple in the Forwarded Set with: 2216 o F_type := the Message Type of the current message; 2218 o F_orig_addr := originator address of the current 2219 message; 2221 o F_seq_number := sequence number of the current 2222 message; 2224 o F_time := current time + F_HOLD_TIME. 2226 2. The Message Header of the current message is modified 2227 by: 2229 o Decrement in the Message Header by 2230 1; AND 2232 o If present, increment in the 2233 Message Header by 1. 2235 3. The message is transmitted over all OLSRv2 2236 interfaces, as described in Section 13. 2238 4. Otherwise, the current message MUST be silently 2239 discarded. 2241 15. HELLO Messages 2243 The HELLO Message Type is owned by [RFC6130], and thus HELLO messages 2244 are generated, transmitted, received and processed by [RFC6130]. 2245 This protocol, as permitted by [RFC6130], also uses HELLO messages, 2246 including adding to HELLO message generation, and implementing 2247 additional processing based on received HELLO messages. HELLO 2248 messages are not forwarded by [RFC6130] or by this specification. 2250 15.1. HELLO Message Generation 2252 HELLO messages sent over OLSRv2 interfaces are generated as defined 2253 in [RFC6130], and then modified as described in this section. HELLO 2254 messages sent on other MANET interfaces are not modified by this 2255 specification. 2257 HELLO messages sent over OLSRv2 interfaces are extended by adding the 2258 following elements: 2260 o A message originator address, recording this router's originator 2261 address. This MUST use a element, unless: 2263 * The message specifies only a single local interface address 2264 (i.e., contains only one address object that is associated with 2265 an Address Block TLV with Type = LOCAL_IF, and which has no 2266 prefix length, or a maximum prefix length) which will then be 2267 used as the message originator address, OR; 2269 * The message does not include any local interface network 2270 addresses (i.e., has no address objects associated with an 2271 Address Block TLV with Type = LOCAL_IF), as permitted by the 2272 specification in [RFC6130], when the router that generated the 2273 HELLO message has only one interface address and will use that 2274 as the sending address of the IP datagram in which the HELLO 2275 message is contained. In this case, that address will be used 2276 as the message originator address. 2278 o A Message TLV with Type := MPR_WILLING MUST be included. 2280 o The following cases associate Address Block TLVs with one or more 2281 addresses from a Link Tuple or a Neighbor Tuple if these are 2282 included in the HELLO message. In each case, the TLV MUST be 2283 associated with at least one address object for an address from 2284 the relevant Tuple; the TLV MAY be associated with more such 2285 addresses (including a copy of that address object, possibly not 2286 itself associated with any other indicated TLVs, in the same or a 2287 different Address Block). These additional TLVs MUST NOT be 2288 associated with any other addresses in a HELLO message that will 2289 be processed by [RFC6130]. 2291 * For each Link Tuple for which L_in_metric != UNKNOWN_METRIC, 2292 and for which one or more addresses in its 2293 L_neighbor_iface_addr_list are included as address objects with 2294 an associated Address Block TLV with Type = LINK_STATUS and 2295 Value = HEARD or Value = SYMMETRIC, at least one of these 2296 addresses MUST be associated with an Address Block TLV with 2297 Type := LINK_METRIC indicating an incoming link metric with 2298 value L_in_metric. 2300 * For each Link Tuple for which L_out_metric != UNKNOWN_METRIC, 2301 and for which one or more addresses in its 2302 L_neighbor_iface_addr_list are included as address objects with 2303 an associated Address Block TLV with Type = LINK_STATUS and 2304 Value = SYMMETRIC, at least one of these addresses MUST be 2305 associated with an Address Block TLV with Type := LINK_METRIC 2306 indicating an outgoing link metric with value L_out_metric. 2308 * For each Neighbor Tuple for which N_symmetric = true, and for 2309 which one or more addresses in its N_neighbor_addr_list are 2310 included as address objects with an associated Address Block 2311 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2312 SYMMETRIC, at least one of these addresses MUST be associated 2313 with an Address Block TLV with Type := LINK_METRIC indicating 2314 an incoming neighbor metric with value N_in_metric. 2316 * For each Neighbor Tuple for which N_symmetric = true, and for 2317 which one or more addresses in its N_neighbor_addr_list are 2318 included as address objects with an associated Address Block 2319 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2320 SYMMETRIC, at least one of these addresses MUST be associated 2321 with an Address Block TLV with Type := LINK_METRIC indicating 2322 an outgoing neighbor metric with value N_out_metric. 2324 * For each Neighbor Tuple with N_flooding_mpr = true, and for 2325 which one or more network addresses in its N_neighbor_addr_list 2326 are included as address objects in the HELLO message with an 2327 associated Address Block TLV with Type = LINK_STATUS and Value 2328 = SYMMETRIC, at least one of these addresses MUST be associated 2329 with an Address Block TLV with Type := MPR and Value := 2330 FLOODING or Value := FLOOD_ROUTE. 2332 * For each Neighbor Tuple with N_routing_mpr = true, and for 2333 which one or more network addresses in its N_neighbor_addr_list 2334 are included as address objects in the HELLO message with an 2335 associated Address Block TLV with Type = LINK_STATUS and Value 2336 = SYMMETRIC, at least one of these addresses MUST be associated 2337 with an Address Block TLV with Type := MPR and Value := ROUTING 2338 or Value := FLOOD_ROUTE. 2340 15.2. HELLO Message Transmission 2342 HELLO messages are scheduled and transmitted by [RFC6130]. This 2343 protocol MAY require that an additional HELLO message is sent on each 2344 OLSRv2 interface when either of the router's sets of MPRs changes, in 2345 addition to the cases specified in [RFC6130], and subject to the 2346 constraints specified in [RFC6130] (notably on minimum HELLO message 2347 transmission intervals). 2349 15.3. HELLO Message Processing 2351 When received on an OLSRv2 interface, HELLO messages are made 2352 available to this protocol in two ways, both as permitted by 2353 [RFC6130]: 2355 o Such received HELLO messages MUST be made available to this 2356 protocol on reception, which allows them to be discarded before 2357 being processed by [RFC6130], for example if the information added 2358 to the HELLO message by this specification is inconsistent. 2360 o Such received HELLO messages MUST be made available to OLSRv2 2361 after [RFC6130] has completed its processing thereof, unless 2362 discarded as malformed by [RFC6130], for processing by this 2363 specification. 2365 15.3.1. HELLO Message Discarding 2367 In addition to the reasons specified in [RFC6130] for discarding a 2368 HELLO message on reception, a HELLO message received on an OLSRv2 2369 interface MUST be discarded before processing by [RFC6130] or this 2370 specification if it: 2372 o Has more than one Message TLV with Type = MPR_WILLING. 2374 o Has a message originator address, or a network address 2375 corresponding to an address object associated with an Address 2376 Block TLV with Type = LOCAL_IF, that is partially owned by this 2377 router. (Some of these cases are already excluded by [RFC6130].) 2379 o Includes any address object associated with an Address Block TLV 2380 with Type = LINK_STATUS or Type = OTHER_NEIGHB that overlaps the 2381 message's originator address. 2383 o Contains any address that will be processed by [RFC6130] that is 2384 associated, using the same or different address objects, with two 2385 different values of link metric with the same kind and direction 2386 using a TLV with Type = LINK_METRIC and Type Extension = 2387 LINK_METRIC_TYPE. This also applies to different addresses that 2388 are both of the OLSRv2 interface on which the HELLO message was 2389 received. 2391 o Contains any address object associated with an Address Block TLV 2392 with Type = MPR that is not also associated with an Address Block 2393 TLV with Type = LINK_STATUS and Value = SYMMETRIC (including using 2394 a different copy of that address object, in the same or a 2395 different Address Block). 2397 15.3.2. HELLO Message Usage 2399 HELLO messages are first processed as specified in [RFC6130]. That 2400 processing includes identifying (or creating) a Link Tuple and a 2401 Neighbor Tuple corresponding to the originator of the HELLO message 2402 (the "current Link Tuple" and the "current Neighbor Tuple"). After 2403 this, the following processing MUST also be performed if the HELLO 2404 message is received on an OLSRv2 interface and contains a TLV with 2405 Type = MPR_WILLING: 2407 1. If the HELLO message has a well-defined message originator 2408 address, i.e., has an element, or has zero or one 2409 network addresses associated with a TLV with Type = LOCAL_IF: 2411 1. Remove any Neighbor Tuple, other than the current Neighbor 2412 Tuple, with N_orig_addr = message originator address, taking 2413 any consequent action (including removing one or more Link 2414 Tuples) as specified in [RFC6130]. 2416 2. The current Link Tuple is then updated according to: 2418 1. Update L_in_metric and L_out_metric as described in 2419 Section 15.3.2.1; 2421 2. Update L_mpr_selector as described in Section 15.3.2.3. 2423 3. The current Neighbor Tuple is then updated according to: 2425 1. N_orig_addr := message originator address; 2427 2. Update N_in_metric and N_out_metric as described in 2428 Section 15.3.2.1; 2430 3. Update N_will_flooding and N_will_routing as described in 2431 Section 15.3.2.2; 2433 4. Update N_mpr_selector as described in Section 15.3.2.3. 2435 2. If there are any changes to the router's Information Bases, then 2436 perform the processing defined in Section 17. 2438 15.3.2.1. Updating Metrics 2440 For each address in a received HELLO message with an associated TLV 2441 with Type = LINK_STATUS and Value = HEARD or Value = SYMMETRIC, an 2442 incoming (to the message originator) link metric value is defined 2443 either using an associated TLV with Type = LINK_METRIC and Type 2444 Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2445 (link) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2447 For each address in a received HELLO message with an associated TLV 2448 with Type = LINK_STATUS and Value = SYMMETRIC, an outgoing (from the 2449 message originator) link metric value is defined either using an 2450 associated TLV with Type = LINK_METRIC and Type Extension = 2451 LINK_METRIC_TYPE that indicates the appropriate kind (link) and 2452 direction (outgoing) of metric, or as UNKNOWN_METRIC. 2454 For each address in a received HELLO message with an associated TLV 2455 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2456 an incoming (to the message originator) neighbor metric value is 2457 defined either using an associated TLV with Type = LINK_METRIC and 2458 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2459 (neighbor) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2461 For each address in a received HELLO message with an associated TLV 2462 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2463 an outgoing (from the message originator) neighbor metric value is 2464 defined either using an associated TLV with Type = LINK_METRIC and 2465 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2466 (neighbor) and direction (outgoing) of metric, or as UNKNOWN_METRIC. 2468 The link metric elements L_in_metric and L_out_metric in a Link Tuple 2469 are updated according to the following: 2471 o For any Link Tuple, L_in_metric MAY be set to any representable 2472 value, by a process outside this specification, at any time. 2473 L_in_metric MUST be so set whenever L_status becomes equal to 2474 HEARD or SYMMETRIC (if no other value is available then the value 2475 MAXIMUM_METRIC MUST be used). Setting L_in_metric MAY use 2476 information based on the receipt of a packet including a HELLO 2477 message that causes the creation or updating of the Link Tuple. 2479 o When, as specified in [RFC6130], a Link Tuple is updated (possibly 2480 immediately after being created) due to the receipt of a HELLO 2481 message, if L_status = SYMMETRIC, then L_out_metric is set equal 2482 to the incoming link metric for any included address of the 2483 interface on which the HELLO message was received. (Note that the 2484 rules for discarding HELLO messages in Section 15.3.1 make this 2485 value unambiguous.) If there is no such link metric then 2486 L_out_metric is set to UNKNOWN_METRIC. 2488 The neighbor metric elements N_in_metric and N_out_metric in a 2489 Neighbor Tuple are updated according to Section 17.3. 2491 The metric elements N2_in_metric and N2_out_metric in any 2-Hop Tuple 2492 updated as defined in [RFC6130] are updated to equal the incoming 2493 neighbor metric and outgoing neighbor metric, respectively, 2494 associated with the corresponding N2_2hop_addr. If there are no such 2495 metrics then these elements are set to UNKNOWN_METRIC. 2497 15.3.2.2. Updating Willingness 2499 N_will_flooding and N_will_routing in the current Neighbor Tuple are 2500 updated using the Message TLV with Type = MPR_WILLING (note that this 2501 must be present) as follows: 2503 o N_will_flooding := bits 0-3 of the value of that TLV; AND 2505 o N_will_routing := bits 4-7 of the value of that TLV. 2507 (Each being in the range 0 to 15, i.e., WILL_NEVER to WILL_ALWAYS.) 2509 15.3.2.3. Updating MPR Selector Status 2511 L_mpr_selector is updated as follows: 2513 1. If a router finds an address object representing any of its 2514 relevant local interface network addresses (i.e., those contained 2515 in the I_local_iface_addr_list of an OLSRv2 interface) with an 2516 associated Address Block TLV with Type = MPR and Value = FLOODING 2517 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2518 originating router has selected the receiving router as a 2519 flooding MPR) then, for the current Link Tuple: 2521 * L_mpr_selector := true. 2523 2. Otherwise (i.e., if no such address object and Address Block TLV 2524 was found), if a router finds an address object representing any 2525 of its relevant local interface network addresses (i.e., those 2526 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2527 with an associated Address Block TLV with Type = LINK_STATUS and 2528 Value = SYMMETRIC in the HELLO message, then for the current Link 2529 Tuple: 2531 * L_mpr_selector := false. 2533 N_mpr_selector is updated as follows: 2535 1. If a router finds an address object representing any of its 2536 relevant local interface network addresses (those contained in 2537 the I_local_iface_addr_list of an OLSRv2 interface) with an 2538 associated Address Block TLV with Type = MPR and Value = ROUTING 2539 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2540 originating router has selected the receiving router as a routing 2541 MPR) then, for the current Neighbor Tuple: 2543 * N_mpr_selector := true; 2545 * N_advertised := true. 2547 2. Otherwise (i.e., if no such address object and Address Block TLV 2548 was found), if a router finds an address object representing any 2549 of its relevant local interface network addresses (those 2550 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2551 with an associated Address Block TLV with Type = LINK_STATUS and 2552 Value = SYMMETRIC in the HELLO message, then for the current 2553 Neighbor Tuple: 2555 * N_mpr_selector := false; 2557 * The router MAY also set N_advertised := false. 2559 16. TC Messages 2561 This protocol defines, and hence owns, the TC Message Type (see 2562 Section 24). Thus, as specified in [RFC5444], this protocol 2563 generates and transmits all TC messages, receives all TC messages and 2564 is responsible for determining whether and how each TC message is to 2565 be processed (updating the Topology Information Base) and/or 2566 forwarded, according to this specification. 2568 16.1. TC Message Generation 2570 A TC message is a message as defined in [RFC5444]. A generated TC 2571 message MUST contain the following elements as defined in [RFC5444]: 2573 o A message originator address, recording this router's originator 2574 address. This MUST use a element. 2576 o element containing the message sequence number. 2578 o A element, containing TC_HOP_LIMIT. A router MAY 2579 use the same or different values of TC_HOP_LIMIT in its TC 2580 messages, see Section 5.4.7. 2582 o A element, containing zero, if the message 2583 contains a TLV with either Type = VALIDITY_TIME or Type = 2584 INTERVAL_TIME (as specified in [RFC5497]) indicating more than one 2585 time value according to distance. A TC message MAY contain such a 2586 element even if it does not need to. 2588 o A single Message TLV with Type := CONT_SEQ_NUM and Value := ANSN 2589 from the Neighbor Information Base. If the TC message is complete 2590 then this Message TLV MUST have Type Extension := COMPLETE, 2591 otherwise it MUST have Type Extension := INCOMPLETE. (Exception: 2592 a TC message MAY omit such a Message TLV if the TC message does 2593 not include any address objects with an associated Address Block 2594 TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY.) 2596 o A single Message TLV with Type := VALIDITY_TIME, as specified in 2597 [RFC5497]. If all TC messages are sent with the same hop limit 2598 then this TLV MUST have a value encoding the period T_HOLD_TIME. 2599 If TC messages are sent with different hop limits (more than one 2600 value of TC_HOP_LIMIT) then this TLV MUST specify times that vary 2601 with the number of hops appropriate to the chosen pattern of TC 2602 message hop limits, as specified in [RFC5497]; these times SHOULD 2603 be appropriate multiples of T_HOLD_TIME. The options included in 2604 [RFC5497] for representing zero and infinite times MUST NOT be 2605 used. 2607 o If the TC message is complete, all network addresses which are the 2608 N_orig_addr of a Neighbor Tuple with N_advertised = true, MUST be 2609 represented by address objects in one or more Address Blocks. If 2610 the TC message is incomplete then any such address objects MAY be 2611 included. At least one copy of each such address object that is 2612 included MUST be associated with an Address Block TLV with Type := 2613 NBR_ADDR_TYPE, and Value := ORIGINATOR, or with Value := 2614 ROUTABLE_ORIG if that address object is also to be associated with 2615 Value = ROUTABLE. 2617 o If the TC message is complete, all routable addresses which are in 2618 the N_neighbor_addr_list of a Neighbor Tuple with N_advertised = 2619 true MUST be represented by address objects in one or more Address 2620 Blocks. If the TC message is incomplete then any such address 2621 objects MAY be included. At least one copy of each such address 2622 object MUST be associated with an Address Block TLV with Type = 2623 NBR_ADDR_TYPE, and Value = ROUTABLE, or with Value = ROUTABLE_ORIG 2624 if also to be associated with Value = ORIGINATOR. At least one 2625 copy of each such address object MUST be associated with an 2626 Address Block TLV with Type = LINK_METRIC and Type Extension = 2627 LINK_METRIC_TYPE indicating an outgoing neighbor metric with value 2628 equal to the corresponding N_out_metric. 2630 o If the TC message is complete, all network addresses which are the 2631 AL_net_addr of a Local Attached Network Tuple MUST be represented 2632 by address objects in one or more Address Blocks. If the TC 2633 message is incomplete then any such address objects MAY be 2634 included. At least one copy of each such address object MUST be 2635 associated with an Address Block TLV with Type := GATEWAY, and 2636 Value := AN_dist. At least one copy of each such address object 2637 MUST be associated with an Address Block TLV with Type = 2638 LINK_METRIC and Type Extension = LINK_METRIC_TYPE indicating an 2639 outgoing neighbor metric equal to the corresponding AL_metric. 2641 A TC message MAY contain: 2643 o A single Message TLV with Type := INTERVAL_TIME, as specified in 2644 [RFC5497]. If all TC messages are sent with the same hop limit 2645 then this TLV MUST have a value encoding the period TC_INTERVAL. 2646 If TC messages are sent with different hop limits, then this TLV 2647 MUST specify times that vary with the number of hops appropriate 2648 to the chosen pattern of TC message hop limits, as specified in 2649 [RFC5497]; these times MUST be appropriate multiples of 2650 TC_INTERVAL. The options included in [RFC5497] for representing 2651 zero and infinite times MUST NOT be used. 2653 16.2. TC Message Transmission 2655 A router with one or more OLSRv2 interfaces, and with any Neighbor 2656 Tuples with N_advertised = true, or with a non-empty Local Attached 2657 Network Set MUST generate TC messages. A router which does not have 2658 such information to advertise MUST also generate "empty" TC messages 2659 for a period A_HOLD_TIME after it last generated a non-empty TC 2660 message. 2662 Complete TC messages are generated and transmitted periodically on 2663 all OLSRv2 interfaces, with a default interval between two 2664 consecutive TC message transmissions by the same router of 2665 TC_INTERVAL. 2667 TC messages MAY be generated in response to a change in the 2668 information which they are to advertise, indicated by a change in the 2669 ANSN in the Neighbor Information Base. In this case a router MAY 2670 send a complete TC message, and if so MAY re-start its TC message 2671 schedule. Alternatively, a router MAY send an incomplete TC message 2672 with at least the newly advertised network addresses (i.e., not 2673 previously, but now, an N_orig_addr or in an N_neighbor_addr_list in 2674 a Neighbor Tuple with N_advertised = true, or an AL_net_addr) in its 2675 Address Blocks, with associated Address Block TLV(s). Note that a 2676 router cannot report removal of advertised content using an 2677 incomplete TC message. 2679 When sending a TC message in response to a change of advertised 2680 network addresses, a router MUST respect a minimum interval of 2681 TC_MIN_INTERVAL between sending TC messages (complete or incomplete), 2682 and a maximum interval of TC_INTERVAL between sending complete TC 2683 messages. Thus a router MUST NOT send an incomplete TC message if 2684 within TC_MIN_INTERVAL of the next scheduled time to send a complete 2685 TC message. 2687 The generation of TC messages, whether scheduled or triggered by a 2688 change of contents, MAY be jittered as described in [RFC5148]. The 2689 values of MAXJITTER used MUST be: 2691 o TP_MAXJITTER for periodic TC message generation; 2693 o TT_MAXJITTER for responsive TC message generation. 2695 16.3. TC Message Processing 2697 On receiving a TC message on an OLSRv2 interface, the receiving 2698 router MUST then follow the processing and forwarding procedures, 2699 defined in Section 14. 2701 If the message is considered for processing (Section 14.2), then a 2702 router MUST first check if the message is invalid for processing by 2703 this router, as defined in Section 16.3.1. A router MAY make a 2704 similar check before considering a message for forwarding, it MUST 2705 make those aspects of the check that apply to elements in the Message 2706 Header. 2708 If the TC message is not invalid, then the TC Message Type specific 2709 processing, described in Section 16.3.2 MUST be applied. This will 2710 update its appropriate Interface Information Bases and its Router 2711 Information Base. Following this, if there are any changes in these 2712 Information Bases, then the processing in Section 17 MUST be 2713 performed. 2715 16.3.1. TC Message Discarding 2717 A received TC message is invalid for processing by this router if the 2718 message: 2720 o Has an address length specified in the Message Header that is not 2721 equal to the length of the addresses used by this router. 2723 o Does not include a message originator address and a message 2724 sequence number. 2726 o Does not include a hop count, and contains a multi-value TLV with 2727 Type = VALIDITY_TIME or Type = INTERVAL_TIME, as defined in 2728 [RFC5497]. 2730 o Does not have exactly one Message TLV with Type = VALIDITY_TIME. 2732 o Has more than one Message TLV with Type = INTERVAL_TIME. 2734 o Does not have a Message TLV with Type = CONT_SEQ_NUM and Type 2735 Extension = COMPLETE or Type Extension = INCOMPLETE, and contains 2736 at least one address object associated with an Address Block TLV 2737 with Type = NBR_ADDR_TYPE or Type = GATEWAY. 2739 o Has more than one Message TLV with Type = CONT_SEQ_NUM and Type 2740 Extension = COMPLETE or Type Extension = INCOMPLETE. 2742 o Has a message originator address that is partially owned by this 2743 router. 2745 o Includes any address object with a prefix length which is not 2746 maximal (equal to the address length, in bits), associated with an 2747 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ORIGINATOR 2748 or Value = ROUTABLE_ORIG. 2750 o Includes any address object that represents a non-routable 2751 address, associated with an Address Block TLV with Type = 2752 NBR_ADDR_TYPE and Value = ROUTABLE or Value = ROUTABLE_ORIG. 2754 o Includes any address object associated with an Address Block TLV 2755 with Type = NBR_ADDR_TYPE or Type = GATEWAY that also represents 2756 the message's originator address. 2758 o Includes any address object (including different copies of an 2759 address object, in the same or different Address Blocks) that is 2760 associated with an Address Block TLV with Type = NBR_ADDR_TYPE or 2761 Type = GATEWAY, that is also associated with more than one 2762 outgoing neighbor metric using a TLV with Type = LINK_METRIC and 2763 Type Extension = LINK_METRIC_TYPE. 2765 o Associates any address object (including different copies of an 2766 address object, in the same or different Address Blocks) with more 2767 than one single hop count value using one or more Address Block 2768 TLV(s) with Type = GATEWAY. 2770 o Associates any address object (including different copies of an 2771 address object, in the same or different Address Blocks) with 2772 Address Block TLVs with Type = NBR_ADDR_TYPE and Type = GATEWAY. 2774 A router MAY recognize additional reasons for identifying that a 2775 message is invalid. An invalid message MUST be silently discarded, 2776 without updating the router's Information Bases. 2778 Note that a router that acts inconsistently, for example rejecting TC 2779 messages "at random", may cause parts of the network to not be able 2780 to communicate with other parts of the network. It is RECOMMENDED 2781 that such "additional reasons for identifying that a message is 2782 invalid" be a consistent network-wide policy (e.g., as part of a 2783 security policy), implemented on all participating routers. 2785 16.3.2. TC Message Processing Definitions 2787 When, according to Section 14.2, a TC message is to be "processed 2788 according to its type", this means that: 2790 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2791 and Type Extension = COMPLETE, then processing according to 2792 Section 16.3.3 and then according to Section 16.3.4 is carried 2793 out. 2795 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2796 and Type Extension = INCOMPLETE, then only processing according to 2797 Section 16.3.3 is carried out. 2799 For the purposes of the TC message processing in Section 16.3.3 and 2800 Section 16.3.4: 2802 o "validity time" is calculated from a VALIDITY_TIME Message TLV in 2803 the TC message according to the specification in [RFC5497]. All 2804 information in the TC message has the same validity time. 2806 o "received ANSN" is defined as being the value of a Message TLV 2807 with Type = CONT_SEQ_NUM. 2809 o "associated metric value" is defined for any address in the TC 2810 message as being either the outgoing neighbor metric value 2811 indicated by a TLV with Type = LINK_METRIC and Type Extension = 2812 LINK_METRIC_TYPE that is associated with any address object in the 2813 TC message that is equal to that address, or as UNKNOWN_METRIC 2814 otherwise. (Note that the rules in Section 16.3.1 make this 2815 definition unambiguous.) 2817 o Comparisons of sequence numbers are carried out as specified in 2818 Section 21. 2820 16.3.3. Initial TC Message Processing 2822 The TC message is processed as follows: 2824 1. The Advertising Remote Router Set is updated according to 2825 Section 16.3.3.1. If the TC message is indicated as discarded in 2826 that processing then the following steps are not carried out. 2828 2. The Router Topology Set is updated according to Section 16.3.3.2. 2830 3. The Routable Address Topology Set is updated according to 2831 Section 16.3.3.3. 2833 4. The Attached Network Set is updated according to 2834 Section 16.3.3.4. 2836 16.3.3.1. Populating the Advertising Remote Router Set 2838 The router MUST update its Advertising Remote Router Set as follows: 2840 1. If there is an Advertising Remote Router Tuple with: 2842 * AR_orig_addr = message originator address; AND 2844 * AR_seq_number > received ANSN, 2846 then the TC message MUST be discarded. 2848 2. Otherwise: 2850 1. If there is no Advertising Remote Router Tuple such that: 2852 + AR_orig_addr = message originator address; 2854 then create an Advertising Remote Router Tuple with: 2856 + AR_orig_addr := message originator address. 2858 2. This Advertising Remote Router Tuple (existing or new) is 2859 then modified as follows: 2861 + AR_seq_number := received ANSN; 2863 + AR_time := current time + validity time. 2865 16.3.3.2. Populating the Router Topology Set 2867 The router MUST update its Router Topology Set as follows: 2869 1. For each address (henceforth advertised address) corresponding to 2870 one or more address objects with an associated Address Block TLV 2871 with Type = NBR_ADDR_TYPE and Value = ORIGINATOR or Value = 2872 ROUTABLE_ORIG, and that is not partially owned by this router, 2873 perform the following processing: 2875 1. If the associated metric is UNKNOWN_METRIC then remove any 2876 Router Topology Tuple such that: 2878 + TR_from_orig_addr = message originator address; AND 2880 + TR_to_orig_addr = advertised address, 2882 2. Otherwise if there is no Router Topology Tuple such that: 2884 + TR_from_orig_addr = message originator address; AND 2886 + TR_to_orig_addr = advertised address, 2888 then create a new Router Topology Tuple with: 2890 + TR_from_orig_addr := message originator address; 2892 + TR_to_orig_addr := advertised address. 2894 3. This Router Topology Tuple (existing or new) is then modified 2895 as follows: 2897 + TR_seq_number := received ANSN; 2899 + TR_metric := associated link metric; 2901 + TR_time := current time + validity time. 2903 16.3.3.3. Populating the Routable Address Topology Set 2905 The router MUST update its Routable Address Topology Set as follows: 2907 1. For each network address (henceforth advertised address) 2908 corresponding to one or more address objects with an associated 2909 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ROUTABLE 2910 or Value = ROUTABLE_ORIG, and that is not partially owned by this 2911 router, perform the following processing: 2913 1. If the associated metric is UNKNOWN_METRIC then remove any 2914 Routable Address Topology Tuple such that: 2916 + TA_from_orig_addr = message originator address; AND 2918 + TA_dest_addr = advertised address. 2920 2. Otherwise if there is no Routable Address Topology Tuple such 2921 that: 2923 + TA_from_orig_addr = message originator address; AND 2925 + TA_dest_addr = advertised address, 2927 then create a new Routable Address Topology Tuple with: 2929 + TA_from_orig_addr := message originator address; 2931 + TA_dest_addr := advertised address. 2933 3. This Routable Address Topology Tuple (existing or new) is 2934 then modified as follows: 2936 + TA_seq_number := received ANSN; 2938 + TA_metric := associated link metric; 2940 + TA_time := current time + validity time. 2942 16.3.3.4. Populating the Attached Network Set 2944 The router MUST update its Attached Network Set as follows: 2946 1. For each network address (henceforth attached address) 2947 corresponding to one or more address objects with an associated 2948 Address Block TLV with Type = GATEWAY, and that is not fully 2949 owned by this router, perform the following processing: 2951 1. If the associated metric is UNKNOWN_METRIC then remove any 2952 Attached Network Tuple such that: 2954 + AN_net_addr = attached address; AND 2956 + AN_orig_addr = message originator address. 2958 2. Otherwise if there is no Attached Network Tuple such that: 2960 + AN_net_addr = attached address; AND 2962 + AN_orig_addr = message originator address, 2964 then create a new Attached Network Tuple with: 2966 + AN_net_addr := attached address; 2968 + AN_orig_addr := message originator address. 2970 3. This Attached Network Tuple (existing or new) is then 2971 modified as follows: 2973 + AN_seq_number := received ANSN; 2975 + AN_dist := the Value of the associated GATEWAY TLV; 2977 + AN_metric := associated link metric; 2979 + AN_time := current time + validity time. 2981 16.3.4. Completing TC Message Processing 2983 The TC message is processed as follows: 2985 1. The Router Topology Set is updated according to Section 16.3.4.1. 2987 2. The Routable Address Topology Set is updated according to 2988 Section 16.3.4.2. 2990 3. The Attached Network Set is updated according to 2991 Section 16.3.4.3. 2993 16.3.4.1. Purging the Router Topology Set 2995 The Router Topology Set MUST be updated as follows: 2997 1. Any Router Topology Tuples with: 2999 * TR_from_orig_addr = message originator address; AND 3001 * TR_seq_number < received ANSN, 3003 MUST be removed. 3005 16.3.4.2. Purging the Routable Address Topology Set 3007 The Routable Address Topology Set MUST be updated as follows: 3009 1. Any Routable Address Topology Tuples with: 3011 * TA_from_orig_addr = message originator address; AND 3013 * TA_seq_number < received ANSN, 3015 MUST be removed. 3017 16.3.4.3. Purging the Attached Network Set 3019 The Attached Network Set MUST be updated as follows: 3021 1. Any Attached Network Tuples with: 3023 * AN_orig_addr = message originator address; AND 3025 * AN_seq_number < received ANSN, 3027 MUST be removed. 3029 17. Information Base Changes 3031 The changes described in the following sections MUST be carried out 3032 when any Information Base changes as indicated. 3034 17.1. Originator Address Changes 3036 If the router changes its originator address, then: 3038 1. If there is no Originator Tuple with: 3040 * O_orig_addr = old originator address 3042 then create an Originator Tuple with: 3044 * O_orig_addr := old originator address 3046 The Originator Tuple (existing or new) with: 3048 * O_orig_addr = new originator address 3050 is then modified as follows: 3052 * O_time := current time + O_HOLD_TIME 3054 17.2. Link State Changes 3056 The consistency of a Link Tuple MUST be maintained according to the 3057 following rules, in addition to those in [RFC6130]: 3059 o If L_status = HEARD or L_status = SYMMETRIC, then L_in_metric MUST 3060 be set (by a process outside this specification). 3062 o If L_status != SYMMETRIC, then set L_mpr_selector := false. 3064 o If L_out_metric = UNKNOWN_METRIC, then L_status MUST NOT equal 3065 SYMMETRIC; set L_SYM_time := EXPIRED if this would otherwise be 3066 the case. 3068 17.3. Neighbor State Changes 3070 The consistency of a Neighbor Tuple MUST be maintained according to 3071 the following rules, in addition to those in [RFC6130]: 3073 1. If N_symmetric = true, then N_in_metric MUST equal the minimum 3074 value of all L_in_metric of corresponding Link Tuples with 3075 L_status = SYMMETRIC and L_in_metric != UNKNOWN_METRIC. If there 3076 are no such Link Tuples then N_in_metric MUST equal 3077 UNKNOWN_METRIC. 3079 2. If N_symmetric = true, then N_out_metric MUST equal the minimum 3080 value of all L_out_metric of corresponding Link Tuples with 3081 L_status = SYMMETRIC and L_out_metric != UNKNOWN_METRIC. If 3082 there are no such Link Tuples then N_out_metric MUST equal 3083 UNKNOWN_METRIC. 3085 3. If N_symmetric = false, then N_flooding_mpr, N_routing_mpr, 3086 N_mpr_selector and N_advertised MUST all be equal to false. 3088 4. If N_mpr_selector = true, then N_advertised MUST be equal to 3089 true. 3091 5. If N_symmetric = true, N_out_metric != UNKNOWN_METRIC and 3092 N_mpr_selector = false, then a router MAY select N_advertised = 3093 true or N_advertised = false. The more neighbors that are 3094 advertised, the larger TC messages become, but the more 3095 redundancy is available for routing. A router SHOULD consider 3096 the nature of its network in making such a decision, and SHOULD 3097 avoid unnecessary changes in advertising status, which may result 3098 both in additional TC messages having to be sent by its 3099 neighbors, and in unnecessary changes to routing, which will have 3100 similar effects to other forms of topology changes in the MANET. 3102 17.4. Advertised Neighbor Changes 3104 The router MUST increment the ANSN in the Neighbor Information Base 3105 whenever: 3107 1. Any Neighbor Tuple changes its N_advertised value, or any 3108 Neighbor Tuple with N_advertised = true is removed. 3110 2. Any Neighbor Tuple with N_advertised = true changes its 3111 N_orig_addr, or has any routable address is added to or removed 3112 from N_neighbor_addr_list. 3114 3. Any Neighbor Tuple with N_advertised = true has N_out_metric 3115 changed. 3117 4. There is any change to the Local Attached Network Set. 3119 17.5. Advertising Remote Router Tuple Expires 3121 The Router Topology Set, the Routable Address Topology Set and the 3122 Attached Network Set MUST be changed when an Advertising Remote 3123 Router Tuple expires (AR_time is reached). The following changes are 3124 required before the Advertising Remote Router Tuple is removed: 3126 1. All Router Topology Tuples with: 3128 * TR_from_orig_addr = AR_orig_addr of the Advertising Remote 3129 Router Tuple 3131 are removed. 3133 2. All Routable Address Topology Tuples with: 3135 * TA_from_orig_addr = AR_orig_addr of the Advertising Remote 3136 Router Tuple 3138 are removed. 3140 3. All Attached Network Tuples with: 3142 * AN_orig_addr = AR_orig_addr of the Advertising Remote Router 3143 Tuple 3145 are removed. 3147 17.6. Neighborhood Changes and MPR Updates 3149 The sets of symmetric 1-hop neighbors selected as flooding MPRs and 3150 routing MPRs MUST satisfy the conditions defined in Section 18. To 3151 ensure this: 3153 1. The set of flooding MPRs of a router MUST be recalculated if: 3155 * A Link Tuple is added with L_status = SYMMETRIC and 3156 L_out_metric != UNKNOWN_METRIC, OR; 3158 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3159 UNKNOWN_METRIC is removed, OR; 3161 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3162 UNKNOWN_METRIC changes to having L_status = HEARD, L_status = 3163 LOST or L_out_metric = UNKNOWN_METRIC, OR; 3165 * A Link Tuple with L_status = HEARD or L_status = LOST changes 3166 to having L_status = SYMMETRIC and L_out_metric != 3167 UNKNOWN_METRIC, OR; 3169 * The flooding MPR selection process uses metric values (see 3170 Section 18.4) and the L_out_metric of any Link Tuple with 3171 L_status = SYMMETRIC changes, OR; 3173 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3174 true and N_out_metric != UNKNOWN_METRIC changes from 3175 WILL_NEVER to any other value, OR; 3177 * The N_will_flooding of a Neighbor Tuple with N_flooding_mpr = 3178 true changes to WILL_NEVER from any other value, OR; 3180 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3181 true, N_out_metric != UNKNOWN_METRIC, and N_flooding_mpr = 3182 false changes to WILL_ALWAYS from any other value, OR; 3184 * A 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC is added or 3185 removed, OR; 3187 * The flooding MPR selection process uses metric values (see 3188 Section 18.4) and the N2_out_metric of any 2-Hop Tuple 3189 changes. 3191 2. Otherwise, the set of flooding MPRs of a router MAY be 3192 recalculated if the N_will_flooding of a Neighbor Tuple with 3193 N_symmetric = true changes in any other way; it SHOULD be 3194 recalculated if N_flooding_mpr = false and this is an increase in 3195 N_will_flooding or if N_flooding_mpr = true and this is a 3196 decrease in N_will_flooding. 3198 3. The set of routing MPRs of a router MUST be recalculated if: 3200 * A Neighbor Tuple is added with N_symmetric = true and 3201 N_in_metric != UNKNOWN_METRIC, OR; 3203 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3204 UNKNOWN_METRIC is removed, OR; 3206 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3207 UNKNOWN_METRIC changes to having N_symmetric = false, OR; 3209 * A Neighbor Tuple with N_symmetric = false changes to having 3210 N_symmetric = true and N_in_metric != UNKNOWN_METRIC, OR; 3212 * The N_in_metric of any Neighbor Tuple with N_symmetric = true 3213 changes, OR; 3215 * The N_will_routing of a Neighbor Tuple with N_symmetric = true 3216 and N_in_metric != UNKNOWN_METRIC changes from WILL_NEVER to 3217 any other value, OR; 3219 * The N_will_routing of a Neighbor Tuple with N_routing_mpr = 3220 true changes to WILL_NEVER from any other value, OR; 3222 * The N_will_routing of a Neighbor Tuple with N_symmetric = 3223 true, N_in_metric != UNKNOWN_METRIC and N_routing_mpr = false 3224 changes to WILL_ALWAYS from any other value, OR; 3226 * A 2-Hop Tuple with N2_in_metric != UNKNOWN_METRIC is added or 3227 removed, OR; 3229 * The N2_in_metric of any 2-Hop Tuple changes. 3231 4. Otherwise, the set of routing MPRs of a router MAY be 3232 recalculated if the N_will_routing of a Neighbor Tuple with 3233 N_symmetric = true changes in any other way; it SHOULD be 3234 recalculated if N_routing_mpr = false and this is an increase in 3235 N_will_routing or if N_routing_mpr = true and this is a decrease 3236 in N_will_routing. 3238 If either set of MPRs of a router is recalculated, this MUST be as 3239 described in Section 18. 3241 17.7. Routing Set Updates 3243 The Routing Set MUST be updated, as described in Section 19, when 3244 changes in the Local Information Base, the Neighborhood Information 3245 Base or the Topology Information Base indicate a change (including of 3246 any potentially used outgoing neighbor metric values) of the known 3247 symmetric links and/or attached networks in the MANET, hence changing 3248 the Topology Graph. It is sufficient to consider only changes which 3249 affect at least one of: 3251 o The Local Interface Set for an OLSRv2 interface, if the change 3252 removes any network address in an I_local_iface_addr_list. In 3253 this case, unless the OLSRv2 interface is removed, it may not be 3254 necessary to do more than replace such network addresses, if used, 3255 by an alternative network address from the same 3256 I_local_iface_addr_list. 3258 o The Local Attached Set, if the change removes any AL_net_addr 3259 which is also an AN_net_addr. In this case it may not be 3260 necessary to do more than add Routing Tuples with R_dest_addr 3261 equal to that AN_net_addr. 3263 o The Link Set of any OLSRv2 interface, considering only Link Tuples 3264 which have, or just had, L_status = SYMMETRIC and L_out_metric != 3265 UNKNOWN_METRIC (including removal of such Link Tuples). 3267 o The Neighbor Set of the router, considering only Neighbor Tuples 3268 that have, or just had, N_symmetric = true and N_out_metric != 3269 UNKNOWN_METRIC, and do not have N_orig_addr = unknown. 3271 o The 2-Hop Set of any OLSRv2 interface, if used in the creation of 3272 the Routing Set, and if the change affects any 2-Hop Tuples with 3273 N2_out_metric != UNKNOWN_METRIC. 3275 o The Router Topology Set of the router. 3277 o The Routable Address Topology Set of the router. 3279 o The Attached Network Set of the router. 3281 18. Selecting MPRs 3283 Each router MUST select, from among its willing symmetric 1-hop 3284 neighbors, two subsets of these routers, as flooding and routing 3285 MPRs. This selection is recorded in the router's Neighbor Set, and 3286 reported in the router's HELLO messages. Routers MAY select their 3287 MPRs by any process that satisfies the conditions which follow, which 3288 may, but need not, use the organization of the data described. 3290 Routers can freely interoperate whether they use the same or 3291 different MPR selection algorithms. 3293 Only flooding MPRs forward control messages flooded through the 3294 MANET, thus effecting a flooding reduction, an optimization of the 3295 flooding mechanism, known as MPR flooding. Routing MPRs are used to 3296 effect a topology reduction in the MANET. (If no such reduction is 3297 required then a router can select all of its relevant neighbors as 3298 routing MPRs.) Consequently, while it is not essential that these 3299 two sets of MPRs are minimal, keeping the numbers of MPRs small 3300 ensures that the overhead of this protocol is kept to a minimum. 3302 18.1. Overview 3304 MPRs are selected according to the following steps, defined in the 3305 following sections: 3307 o A data structure known as a Neighbor Graph is defined. 3309 o The properties of an MPR Set derived from a Neighbor Graph are 3310 defined. Any algorithm that creates an MPR Set that satisfies 3311 these properties is a valid MPR selection algorithm. An example 3312 algorithm that creates such an MPR Set is given in Appendix B. 3314 o How to create a Neighbor Graph for each interface based on the 3315 corresponding Interface Information Base is defined, and how to 3316 combine the resulting MPR Sets to determine the router's flooding 3317 MPRs and record those in the router's Neighbor Set. 3319 o How to create a single Neighbor Graph based on all Interface 3320 Information Bases and the Neighbor Information Base is defined, 3321 and how to record the resulting MPR Set as the router's routing 3322 MPRs in the router's Neighbor Set. 3324 o A specification as to when MPRs MUST be calculated is given. 3326 When a router selects its MPRs it MAY consider any characteristics of 3327 its neighbors that it is aware of. In particular it SHOULD consider 3328 the willingness of the neighbor, as recorded by the corresponding 3329 N_will_flooding or N_will_routing value, as appropriate, preferring 3330 neighbors with higher values. (Note that willingness values equal to 3331 WILL_NEVER and WILL_ALWAYS are always considered, as described.) 3332 However, a router MAY consider other characteristics to have a 3333 greater significance. 3335 Each router MAY select its flooding and routing MPRs independently 3336 from each other, or coordinate its selections. A router MAY make its 3337 MPR selections independently of the MPR selection by other routers, 3338 or it MAY, for example, give preference to routers that either are, 3339 or are not, already selected as MPRs by other routers. 3341 18.2. Neighbor Graph 3343 A Neighbor Graph is a structure defined here as consisting of sets N1 3344 and N2 and some associated metric and willingness values. Elements 3345 of set N1 represent willing symmetric 1-hop neighbors, and elements 3346 of set N2 represent addresses of a symmetric 2-hop neighbor. 3348 A Neighbor Graph has the following properties: 3350 o It contains two disjoint sets N1 and N2. 3352 o For each element x in N1 there is an associated willingness value 3353 W(x) such that WILL_NEVER < W(x) <= WILL_ALWAYS. 3355 o For each element x in N1 there is an associated metric d1(x) > 0. 3357 o For some elements y in N2 there is an associated metric d1(y) > 0. 3358 (Other elements y in N2 have undefined d1(y), this may be 3359 considered to be infinite.) 3361 o For each element x in N1 there is a subset N2(x) of elements of 3362 N2; this subset may be empty. For each x in N1 and each y in 3363 N2(x) there is an associated metric d2(x,y) > 0. (For other x in 3364 N1 and y in N2, d2(x,y) is undefined, and may be considered 3365 infinite.) 3367 o N2 is equal to the union of all the N2(x) for all x in N1, i.e. 3368 for each y in N2 there is at least one x in N1 such that y is in 3369 N2(x). 3371 It is convenient to also define: 3373 o For each y in N2 the set N1(y) that contains x in N1 if and only 3374 if y is in N2(x). From the final property above, N1(y) is not 3375 empty. 3377 o For each x in N1 and y in N2, if d2(x,y) is defined then d(x,y) := 3378 d1(x)+d2(x,y), otherwise d(x,y) is not defined. (Thus d(x,y) is 3379 defined if y is in N2(x), or equivalently if x is in N1(y).) 3381 o For any subset S of N1, and for each y in N2, the metric d(y,S) is 3382 the minimum value of d1(y), if defined, and of all d(x,y) for x in 3383 N1(y) and in S. If there are no such metrics to take the minimum 3384 value of, then d(y,S) is undefined (may be considered to be 3385 infinite). From the final property above, d(y,N1) is defined for 3386 all y. 3388 18.3. MPR Properties 3390 Given a Neighbor Graph as defined in Section 18.2, an MPR Set for 3391 that Neighbor Graph is a subset M of the set N1 that satisfies the 3392 following properties: 3394 o If x in N1 has W(x) = WILL_ALWAYS then x is in M. 3396 o For any y in N2 that does not have a defined d1(y), there is at 3397 least one element in M that is also in N1(y). This is equivalent 3398 to the requirement that d(y,M) is defined. 3400 o For any y in N2, d(y,M) = d(y,N1). 3402 These two properties correspond first to that the MPR Set consists of 3403 a set of symmetric 1-hop neighbors that cover all the symmetric 2-hop 3404 neighbors, and second that they do so retaining a minimum distance 3405 route (1-hop, if present, or 2-hop) to each symmetric 2-hop neighbor. 3407 Note that if M is an MPR Set, then so is any subset of N1 that 3408 contains M, and also that N1 is always an MPR Set. An MPR Set may be 3409 empty, but cannot be empty if N2 contains any elements y that do not 3410 have a defined d1(y). 3412 18.4. Flooding MPRs 3414 Whenever flooding MPRs are to be calculated, an implementation MUST 3415 determine and record a set of flooding MPRs that is equivalent to one 3416 calculated as described in this section. 3418 The calculation of flooding MPRs need not use link metrics, or 3419 equivalently may use link metrics with a fixed value, here taken to 3420 be 1. However, links with unknown metric (L_out_metric = 3421 UNKNOWN_METRIC) MUST NOT be used even if link metrics are otherwise 3422 not used. 3424 Routers MAY make individual decisions as to whether to use link 3425 metrics for the calculation of flooding MPRs. A router MUST use the 3426 same approach to the choice of whether to use link metrics for all 3427 links, i.e., in the cases indicated by A or B, the same choice MUST 3428 be made in each case. 3430 For each OLSRv2 interface (the "current interface") define a Neighbor 3431 Graph as defined in Section 18.2 according to the following: 3433 o Define a reachable Link Tuple to be a Link Tuple in the Link Set 3434 for the current interface with L_status = SYMMETRIC and 3435 L_out_metric != UNKNOWN_METRIC. 3437 o Define an allowed Link Tuple to be a reachable Link Tuple whose 3438 corresponding Neighbor Tuple has N_will_flooding > WILL_NEVER. 3440 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3441 for the current interface for which N2_out_metric != 3442 UNKNOWN_METRIC and there is an allowed Link Tuple with 3443 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 3445 o Define an element of N1 for each allowed Link Tuple. This then 3446 defines the corresponding Link Tuple for each element of N1 and 3447 the corresponding Neighbor Tuple for each element of N1, being the 3448 Neighbor Tuple corresponding to that Link Tuple. 3450 o For each element x in N1, define W(x) := N_will_flooding of the 3451 corresponding Neighbor Tuple. 3453 o For each element x in N1, define d1(x) as either: 3455 A. L_out_metric of the corresponding Link Tuple, OR; 3457 B. 1. 3459 o Define an element of N2 for each network address that is the 3460 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3461 defines the corresponding address for each element of N2. 3463 o For each element y in N2, if the corresponding address is in the 3464 N_neighbor_addr_list of a Neighbor Tuple that corresponds to one 3465 or more reachable Link Tuples, then define d1(y) as either: 3467 A. the minimum value of the L_out_metric of those Link Tuples, 3468 OR; 3470 B. 1. 3472 Otherwise d1(y) is not defined. In the latter case, where d1(y) 3473 := 1, all such y in N2 may instead be removed from N2. 3475 o For each element x in N1, define N2(x) as the set of elements y in 3476 N2 whose corresponding address is the N2_2hop_addr of an allowed 3477 2-Hop Tuple that has N2_neighbor_iface_addr_list = 3478 L_neighbor_iface_addr_list of the Link Tuple corresponding to x. 3479 For all such x and y, define d2(x,y) as either: 3481 A. N2_out_metric of that 2-Hop Tuple, OR; 3483 B. 1. 3485 It is up to an implementation to decide how to label each element of 3486 N1 or N2. For example an element of N1 may be labeled with one or 3487 more addresses from the corresponding L_neighbor_iface_addr_list, or 3488 with a pointer or reference to the corresponding Link Tuple. 3490 Using these Neighbor Graphs, flooding MPRs are selected and recorded 3491 by: 3493 o For each OLSRv2 interface, determine an MPR Set as specified in 3494 Section 18.3. 3496 o A Neighbor Tuple represents a flooding MPR and has N_flooding_mpr 3497 := true (otherwise N_flooding_mpr := false) if and only if that 3498 Neighbor Tuple corresponds to an element in an MPR Set created for 3499 any interface as described above. That is, the overall set of 3500 flooding MPRs is the union of the sets of flooding MPRs for all 3501 OLSRv2 interfaces. 3503 A router MAY select its flooding MPRs for each OLSRv2 interface 3504 independently, or it MAY coordinate its MPR selections across its 3505 OLSRv2 interfaces, as long as the required condition is satisfied for 3506 each OLSRv2 interface. One such coordinated approach is to process 3507 the OLSRv2 interfaces sequentially, and for each OLSRv2 interface 3508 start with flooding MPRs selected (and not removable) if the neighbor 3509 has been already selected as an MPR for an OLSRv2 interface that has 3510 already been processed. The algorithm specified in Appendix B can be 3511 used in this way. 3513 18.5. Routing MPRs 3515 Whenever routing MPRs are to be calculated, an implementation MUST 3516 determine and record a set of routing MPRs that is equivalent to one 3517 calculated as described in this section. 3519 Define a single Neighbor Graph as defined in Section 18.2 according 3520 to the following: 3522 o Define a reachable Neighbor Tuple to be a Neighbor Tuple with 3523 N_symmetric = true and N_in_metric != UNKNOWN_METRIC. 3525 o Define an allowed Neighbor Tuple to be a reachable Neighbor Tuple 3526 with N_will_routing > WILL_NEVER. 3528 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3529 for any OLSRv2 interface with N2_in_metric != UNKNOWN_METRIC and 3530 for which there is an allowed Neighbor Tuple with 3531 N_neighbor_addr_list containing N2_neighbor_iface_addr_list. 3533 o Define an element of N1 for each allowed Neighbor Tuple. This 3534 then defines the corresponding Neighbor Tuple for each element of 3535 N1. 3537 o For each element x in N1, define W(x) := N_will_routing of the 3538 corresponding Neighbor Tuple. 3540 o For each element x in N1, define d1(x) := N_in_metric of the 3541 corresponding Neighbor Tuple. 3543 o Define an element of N2 for each network address that is the 3544 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3545 defines the corresponding address for each element of N2. 3547 o For each element y in N2, if the corresponding address is in the 3548 N_neighbor_addr_list of a reachable Neighbor Tuple, then define 3549 d1(y) to be the N_in_metric of that Neighbor Tuple, otherwise 3550 d1(y) is not defined. 3552 o For each element x in N1, define N2(x) as the set of elements y in 3553 N2 whose corresponding address is the N2_2hop_addr of an allowed 3554 2-Hop Tuple that has N2_neighbor_iface_addr_list contained in 3555 N_neighbor_addr_list of the Neighbor Tuple corresponding to x. 3556 For all such x and y, define d2(x,y) := N2_out_metric of that 3557 2-Hop Tuple. 3559 It is up to an implementation to decide how to label each element of 3560 N1 or N2. For example an element of N1 may be labeled with one or 3561 more addresses from the corresponding N_neighbor_addr_list, or with a 3562 pointer or reference to the corresponding Neighbor Tuple. 3564 Using these Neighbor Graphs, routing MPRs are selected and recorded 3565 according to the following: 3567 o Determine an MPR Set as specified in Section 18.3. 3569 o A Neighbor Tuple represents a routing MPR and has N_routing_mpr := 3570 true (otherwise N_routing_mpr := false) if and only if that 3571 Neighbor Tuple corresponds to an element in the MPR Set created as 3572 described above. 3574 18.6. Calculating MPRs 3576 A router MUST recalculate each of its sets of MPRs whenever the 3577 currently selected set of MPRs does not still satisfy the required 3578 conditions. It MAY recalculate its MPRs if the current set of MPRs 3579 is still valid, but could be more efficient. Sufficient conditions 3580 to recalculate a router's sets of MPRs are given in Section 17.6. 3582 19. Routing Set Calculation 3584 The Routing Set of a router is populated with Routing Tuples that 3585 represent paths from that router to all destinations in the network. 3586 These paths are calculated based on the Network Topology Graph, which 3587 is constructed from information in the Information Bases, obtained 3588 via HELLO and TC message exchange. 3590 Changes to the Routing Set do not require any messages to be 3591 transmitted. The state of the Routing Set SHOULD, however, be 3592 reflected in the IP routing table by adding and removing entries from 3593 that routing table as appropriate. Only appropriate Routing Tuples 3594 (in particular only those that represent local links or paths to 3595 routable addresses) need be reflected in the IP routing table. 3597 19.1. Network Topology Graph 3599 The Network Topology Graph is formed from information from the 3600 router's Local Interface Set, Link Sets for OLSRv2 interfaces, 3601 Neighbor Set, Router Topology Set, Routable Address Topology Set and 3602 Attached Network Set. The Network Topology Graph MAY also use 3603 information from the router's 2-Hop Sets for OLSRv2 interfaces. The 3604 Network Topology Graph forms the router's topological view of the 3605 network in form of a directed graph. Each edge in that graph has a 3606 metric value. The Network Topology Graph has a "backbone" (within 3607 which minimum total metric routes will be constructed) containing the 3608 following edges: 3610 o Edges X -> Y for all possible Y, and one X per Y, such that: 3612 * Y is the N_orig_addr of a Neighbor Tuple; AND 3614 * N_orig_addr is not unknown; 3616 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3617 AND 3619 * There is a Link Tuple with L_status = SYMMETRIC and 3620 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3621 and this Local Interface Tuple correspond to it. A network 3622 address from L_neighbor_iface_addr_list will be denoted R in 3623 this case. 3625 It SHOULD be preferred, where possible, to select R = S and X from 3626 the Local Interface Tuple corresponding to the Link Tuple from 3627 which R was selected. The metric for such an edge is the 3628 corresponding N_out_metric. 3630 o All edges W -> U such that: 3632 * W is the TR_from_orig_addr of a Router Topology Tuple; AND 3634 * U is the TR_to_orig_addr of the same Router Topology Tuple. 3636 The metric of such an edge is the corresponding TR_metric. 3638 The Network Topology Graph is further "decorated" with the following 3639 edges. If a network address S, V, Z or T equals a network address Y 3640 or W, then the edge terminating in the network address S, V, Z or T 3641 MUST NOT be used in any path. 3643 o Edges X -> S for all possible S, and one X per S, such that: 3645 * S is in the N_neighbor_addr_list of a Neighbor Tuple; AND 3647 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3648 AND 3650 * There is a Link Tuple with L_status = SYMMETRIC and 3651 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3652 and this Local Interface Tuple correspond to it. A network 3653 address from L_neighbor_iface_addr_list will be denoted R in 3654 this case. 3656 It SHOULD be preferred, where possible, to select R = S and X from 3657 the Local Interface Tuple corresponding to the Link Tuple from 3658 which R was selected. The metric for such an edge is the 3659 corresponding N_out_metric. 3661 o All edges W -> V such that: 3663 * W is the TA_from_orig_addr of a Routable Address Topology 3664 Tuple; AND 3666 * V is the TA_dest_addr of the same Routable Address Topology 3667 Tuple. 3669 The metric for such an edge is the corresponding TA_metric. 3671 o All edges W -> T such that: 3673 * W is the AN_orig_addr of an Attached Network Tuple; AND 3675 * T is the AN_net_addr of the same Attached Network Tuple. 3677 The metric for such an edge is the corresponding AN_metric. 3679 o (OPTIONAL) All edges Y -> Z such that: 3681 * Z is a routable address and is the N2_2hop_addr of a 2-Hop 3682 Tuple with N2_out_metric != UNKNOWN_METRIC; AND 3684 * Y is the N_orig_addr of the corresponding Neighbor Tuple; AND 3686 * This Neighbor Tuple has N_will_routing not equal to WILL_NEVER. 3688 A path terminating with such an edge MUST NOT be used in 3689 preference to any other path. The metric for such an edge is the 3690 corresponding N2_out_metric. 3692 Any part of the Topology Graph which is not connected to a local 3693 network address X is not used. Only one selection X SHOULD be made 3694 from each I_local_iface_addr_list, and only one selection R SHOULD be 3695 made from any L_neighbor_iface_addr_list. All edges have a hop count 3696 of 1, except edges W -> T that have a hop count of the corresponding 3697 value of AN_dist. 3699 19.2. Populating the Routing Set 3701 The Routing Set MUST contain the shortest paths for all destinations 3702 from all local OLSRv2 interfaces using the Network Topology Graph. 3703 This calculation MAY use any algorithm, including any means of 3704 choosing between paths of equal total metric. (In the case of two 3705 paths of equal total metric but differing hop counts, the path with 3706 the lower hop count SHOULD be used.) 3708 Using the notation of Section 19.1, initially "backbone" paths using 3709 only edges X -> Y and W -> U need be constructed (using a minimum 3710 distance algorithm). Then paths using only a final edge of the other 3711 types may be added. These MUST NOT replace backbone paths with the 3712 same destination (and paths terminating in an edge Y -> Z SHOULD NOT 3713 replace paths with any other form of terminating edge). 3715 Each path will correspond to a Routing Tuple. These will be of two 3716 types. The first type will represent single edge paths, of type X -> 3717 S or X -> Y, by: 3719 o R_local_iface_addr := X; 3721 o R_next_iface_addr := R; 3723 o R_dest_addr := S or Y; 3725 o R_dist := 1; 3727 o R_metric := edge metric, 3729 where R is as defined in Section 19.1 for these types of edges. 3731 The second type will represent a multiple edge path, which will 3732 always have first edge of type X -> Y, and will have final edge of 3733 type W -> U, W -> V, W -> T or Y -> Z. The Routing Tuple will be: 3735 o R_local_iface_addr := X; 3737 o R_next_iface_addr := Y; 3739 o R_dest_addr := U, V, T or Z; 3741 o R_dist := the total hop count of all edges in the path; 3743 o R_metric := the total metric of all edges in the path. 3745 Finally, Routing Tuples of the second type whose R_dest_addr is not 3746 routable MAY be discarded. 3748 An example algorithm for calculating the Routing Set of a router is 3749 given in Appendix C. 3751 20. Proposed Values for Parameters 3753 This protocol uses all parameters defined in [RFC6130] and additional 3754 parameters and defined in this specification. All but one 3755 (RX_HOLD_TIME) of these additional parameters are router parameters 3756 as defined in [RFC6130]. The proposed values of the additional 3757 parameters defined in the following sections are appropriate to the 3758 case where all parameters (including those defined in [RFC6130]) have 3759 a single value. Proposed values for parameters defined in [RFC6130] 3760 are given in that specification. 3762 The following proposed values are based on experience with [RFC3626] 3763 deployments (such as documented in [McCabe]), and are considered 3764 typical. They can be changed to accommodate different deployment 3765 requirements - for example, a network with capacity-limited network 3766 interfaces would be expected to use greater values for message 3767 intervals, whereas a highly mobile network would be expected to use 3768 lower values for message intervals. When determining these values, 3769 the constraints specified in Section 5 MUST be respected. 3771 Note that routers in a MANET need not all use the same set of 3772 parameters, and those parameters that are indicated as interface 3773 parameters need not be the same on all OLSRv2 interfaces of a single 3774 router. 3776 20.1. Local History Time Parameters 3778 o O_HOLD_TIME := 30 seconds 3780 20.2. Message Interval Parameters 3782 o TC_INTERVAL := 5 seconds 3784 o TC_MIN_INTERVAL := TC_INTERVAL/4 3786 20.3. Advertised Information Validity Time Parameters 3788 o T_HOLD_TIME := 3 x TC_INTERVAL 3790 o A_HOLD_TIME := T_HOLD_TIME 3792 20.4. Received Message Validity Time Parameters 3794 o RX_HOLD_TIME := 30 seconds 3796 o P_HOLD_TIME := 30 seconds 3798 o F_HOLD_TIME := 30 seconds 3800 20.5. Jitter Time Parameters 3802 o TP_MAXJITTER := HP_MAXJITTER 3804 o TT_MAXJITTER := HT_MAXJITTER 3806 o F_MAXJITTER := TT_MAXJITTER 3808 20.6. Hop Limit Parameter 3810 o TC_HOP_LIMIT := 255 3812 20.7. Willingness Parameter 3814 o WILL_FLOODING := WILL_DEFAULT 3816 o WILL_ROUTING := WILL_DEFAULT 3818 21. Sequence Numbers 3820 Sequence numbers are used in this specification for the purpose of 3821 discarding "old" information, i.e., messages received out of order. 3822 However with a limited number of bits for representing sequence 3823 numbers, wrap-around (that the sequence number is incremented from 3824 the maximum possible value to zero) will occur. To prevent this from 3825 interfering with the operation of this protocol, the following MUST 3826 be observed when determining the ordering of sequence numbers. 3828 The term MAXVALUE designates in the following one more than the 3829 largest possible value for a sequence number. For a 16 bit sequence 3830 number (as are those defined in this specification) MAXVALUE is 3831 65536. 3833 The sequence number S1 is said to be "greater than" the sequence 3834 number S2 if: 3836 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 3838 o S2 > S1 AND S2 - S1 > MAXVALUE/2 3840 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 3841 cannot be determined. In this case, which should not occur, either 3842 ordering may be assumed. 3844 Thus when comparing two messages, it is possible - even in the 3845 presence of wrap-around - to determine which message contains the 3846 most recent information. 3848 22. Extensions 3850 An extension to this protocol will need to interact with this 3851 specification, and possibly also with [RFC6130]. This protocol is 3852 designed to permit such interactions, in particular: 3854 o Through accessing, and possibly extending, the information in the 3855 Information Bases. All updates to the elements specified in this 3856 specification are subject to the normative constraints specified 3857 in [RFC6130] and Appendix A. Note that the processing specified 3858 in this document ensures that these constraints are satisfied. 3860 o Through accessing an outgoing message prior to it being 3861 transmitted over any OLSRv2 interface, and to add information to 3862 it as specified in [RFC5444]. This MAY include Message TLVs 3863 and/or network addresses with associated Address Block TLVs. 3864 (Network addresses without new associated TLVs SHOULD NOT be added 3865 to messages.) This may, for example, be to allow a security 3866 protocol, as suggested in Section 23, to add a TLV containing a 3867 cryptographic signature to the message. 3869 o Through accessing an incoming message, and potentially discarding 3870 it prior to processing by this protocol. This may, for example, 3871 allow a security protocol, as suggested in Section 23, to perform 3872 verification of message signatures and prevent processing and/or 3873 forwarding of unverifiable messages by this protocol. 3875 o Through accessing an incoming message after it has been completely 3876 processed by this protocol. In particular, this may allow a 3877 protocol which has added information, by way of inclusion of 3878 appropriate TLVs, or of network addresses associated with new 3879 TLVs, access to such information after appropriate updates have 3880 been recorded in the Information Bases in this protocol. 3882 o Through requesting that a message be generated at a specific time. 3883 In that case, message generation MUST still respect the 3884 constraints in [RFC6130] and Section 5.4.3. 3886 23. Security Considerations 3888 As a proactive routing protocol, OLSRv2 is a potential target for 3889 various attacks. This section presents the envisioned security 3890 architecture for OLSRv2, and gives guidelines on how to provide 3891 integrity, confidentiality, and integration into external routing 3892 domains. Separately specified mandatory security mechanisms are 3893 summarised, and some observations on key management are given. 3895 23.1. Security Architecture 3897 OLSRv2 integrates into the architecture specified in Appendix A of 3898 [RFC5444], in [RFC5498], and in Section 16 of [RFC6130], the latter 3899 by using and extending its messages and Information Bases. 3901 As part of this architecture, OLSRv2, and [RFC6130], recognize that 3902 there may be external reasons for rejecting messages that would be 3903 considered "badly formed" or "insecure", e.g., if an Integrity Check 3904 Value (ICV) included in a message by an external mechanism cannot be 3905 verified. This architecture allows options as to whether and how to 3906 implement security features, reflecting the situation that MANET 3907 routing protocol deployment domains have varying security 3908 requirements, ranging from "practically unbreakable" to "virtually 3909 none". This approach allows MANET routing protocol specifications to 3910 remain generic, with extensions to them, and/or extensions to the 3911 multiplexing and demultiplexing process described in Appendix A of 3912 [RFC5444], providing security mechanisms appropriate to a given 3913 deployment domain. 3915 The following sections provide guidelines how to provide integrity, 3916 confidentiality, and integration with external routing domains in 3917 such extensions. 3919 23.2. Integrity 3921 Each router injects topological information into the network by 3922 transmitting HELLO messages and, for some routers, also TC messages. 3923 If some routers for some reason, malice or malfunction, inject 3924 invalid control traffic, network integrity may be compromised. 3925 Therefore, message, or packet, authentication is strongly advised. 3927 Different such situations may occur, for example: 3929 1. A router generates TC messages, advertising links to non-neighbor 3930 routers; 3932 2. A router generates TC messages, pretending to be another router; 3934 3. A router generates HELLO messages, advertising non-neighbor 3935 routers; 3937 4. A router generates HELLO messages, pretending to be another 3938 router; 3940 5. A router forwards altered control messages; 3942 6. A router does not forward control messages; 3944 7. A router does not select multipoint relays correctly; 3946 8. A router forwards broadcast control messages unaltered, but does 3947 not forward unicast data traffic; 3949 9. A router "replays" previously recorded control traffic from 3950 another router. 3952 Authentication of the originator router for control messages (for 3953 situations 2, 4 and 5), and of the individual links announced in the 3954 control messages (for situations 1 and 3), may be used as a 3955 countermeasure. However to prevent routers from repeating old (and 3956 correctly authenticated) information (situation 9) additional 3957 information is required (e.g., a timestamp or sequence number), 3958 allowing a router to positively identify such replayed messages. 3960 In general, ICVs (e.g., digital signatures) and other required 3961 security information can be transmitted within the HELLO and TC 3962 messages, or within a packet header, using the TLV mechanism. Either 3963 option permits different levels of protection to coexist in the same 3964 network, if desired. 3966 An important consideration is that all control messages (HELLO 3967 messages and TC messages) are transmitted to all routers in the 1-hop 3968 neighborhood and some control messages (TC messages) are flooded to 3969 all routers in the network. This is done in a packet that is 3970 transmitted to all routers in the 1-hop neighborhood, the current set 3971 of which may not be known. Thus, a control message, or packet, used 3972 by this protocol is always contained in a transmission destined for 3973 multiple destinations, and it is important that the authentication 3974 mechanism employed permits any receiving router to validate the 3975 authenticity of a message or packet. 3977 [RFC6622bis] specifies a common exchange format for cryptographic 3978 information in the form of Packet TLVs, Message TLVs, and Address 3979 Block TLVs, as specified in [RFC5444]. These may be used (and 3980 shared) among MANET routing protocol security extensions. In 3981 particular, [RFC6622bis] specifies the format of TLVs for containing 3982 Integrity Check Values (ICVs), i.e., signatures, for providing 3983 integrity, as well as TLVs for containing temporal information for 3984 preventing replay attacks. [RFC6622bis] specifies registries for 3985 using different ciphers and formats of temporal information. When 3986 using ICV TLVs in an OLSRv2 deployment, failure to verify an ICV 3987 included mandates to reject an incoming message or packet as 3988 "invalid", according to Section 12.1 of [RFC6130], and according to 3989 Section 16.3.1 of this specification, when using the multiplexing and 3990 demultiplexing process described in Appendix A of [RFC5444]. 3992 [RFC6622bis] specifies how to insert IVCs into generated messages, 3993 how to verify incoming messages, and to reject "insecure" messages 3994 (i.e., messages without an ICV or with an ICV that cannot be 3995 verified). Different MANET deployments may, as a result of the 3996 purpose for which they are used and the possibility and nature of 3997 their configuration, require different ICV algorithms and timestamps, 3998 or multiple keys, and thus a security extension may use any of the 3999 different options provided in [RFC6622bis]. 4001 23.3. Confidentiality 4003 OLSRv2 periodically MPR floods topological information to all routers 4004 in the network. Hence, if used in an unprotected network, in 4005 particular an unprotected wireless network, the network topology is 4006 revealed to anyone who successfully listens to the control messages. 4007 This information may serve an attacker to acquire details about the 4008 topology, and therefore to initiate more effective attacks against 4009 routers in the routing domain e.g., by spoofing addresses of routers 4010 in the network and attracting traffic for these addresses. Note that 4011 this is independent of the data traffic, and purely protects the 4012 control traffic, i.e., information about the network topology. 4014 In situations where the confidentiality of the network topology is of 4015 importance, regular cryptographic techniques, such as use of OLSRv2 4016 multicast control packets encrypted using IPsec (e.g., with a shared 4017 secret key), can be applied to ensure that control traffic can be 4018 read and interpreted by only those authorized to do so. 4019 Alternatively, a security extension may specify a mechanism to 4020 provide confidentiality for control messages and/or packets. 4021 However, unless the information about the network topology itself is 4022 confidential, integrity of control messages (as specified in 4023 Section 23.2) is sufficient to admit only trusted routers (i.e. 4024 routers with valid credentials) to the network. 4026 23.4. Interaction with External Routing Domains 4028 This protocol provides a basic mechanism for injecting external 4029 routing information into this protocol's routing domain. Routing 4030 information can also be extracted from this protocol's Information 4031 Bases, in particular the Routing Set, and injected into an external 4032 routing domain, if the routing protocol governing that routing domain 4033 permits this. 4035 When operating routers connecting a routing domain using this 4036 protocol to an external routing domain, care MUST be taken not to 4037 allow potentially insecure and untrustworthy information to be 4038 injected from this routing domain to an external routing domain. 4039 Care MUST also be taken to validate the correctness of information 4040 prior to it being injected, so as to avoid polluting routing tables 4041 with invalid information. 4043 A recommended way of extending connectivity from an external routing 4044 domain to this routing domain, which is routed using this protocol, 4045 is to assign an IP prefix (under the authority of the routers/ 4046 gateways connecting this routing domain with the external routing 4047 domain) exclusively to this routing domain, and to configure the 4048 gateways to advertise routes for that IP prefix into the external 4049 routing domain. 4051 23.5. Mandatory Security Mechanisms 4053 A conformant implementation of OLSRv2 MUST, at minimum, implement the 4054 security mechanisms specified in [OLSRv2-integrity], providing 4055 integrity and replay protection of OLSRv2 control messages, including 4056 of HELLO messages specified by [RFC6130] and used by OLSRv2, by 4057 inclusion of a timestamp TLV and an Integrity Check Value (ICV) TLV. 4058 This ICV TLV uses a SHA-256 based HMAC and one or more manually 4059 managed shared secret keys. The timestamp TLV is based on POSIX 4060 time, assuming router time synchronization. 4062 The baseline use case, for which this security mechanism provides 4063 adequate integrity protection without rekeying, is for short-lived 4064 (for example up to a couple of months) OLSRv2 deployments. 4066 Any deployment of OLSRv2 SHOULD use the security mechanism specified 4067 in [OLSRv2-integrity], but MAY use another mechanism if more 4068 appropriate in an OLSRv2 deployment. For example, for longer-term 4069 OLSRv2 deployments, alternative security mechanisms (e.g., re-keying) 4070 SHOULD be considered. 4072 23.6. Key Management 4074 This specification, including [OLSRv2-integrity], does not mandate 4075 automatic key management (AKM) as part of the security architecture 4076 for OLSRv2. While some use cases for OLSRv2 may require AKM, the 4077 baseline assumption is that many use cases do not, for the reasons 4078 detailed below. 4080 Bootstrapping a key is hard in a radio network, where it is - in 4081 general - not possible to determine from where a received signal was 4082 transmitted, or if two transmissions come from the same or from 4083 different sources. 4085 A widespread use of radio networks, mobile phone networks, works 4086 under the assumptions that (i) secret information is embedded in 4087 mobile phones at manufacture, and (ii) a centralized database of this 4088 is accessible during the network lifetime. 4090 As a primary use case of a MANET is to provide connectivity without 4091 centralized entities, and with minimal management, a solution such as 4092 described in the previous paragraph is not feasible. In many 4093 instances, a cryptographic authority may not be present in the MANET 4094 at all, since such a cryptographic authority would be too vulnerable. 4095 Due to the potentially dynamic topology of a MANET, a cryptographic 4096 authority may also become unreachable (to some or all of the MANET 4097 routers) without prior warning. 4099 [BCP107] provides guidelines for cryptographic key management. 4100 Specifically, Section 2.1 sets forth requirements for when AKM is 4101 required, and Section 2.2 sets forth conditions under which manual 4102 key management is acceptable. 4104 Section 2.1 of [BCP107] stipulates that "Automated key management 4105 MUST be used if any of [a set of given] conditions hold". These 4106 conditions are listed below, for each of which arguments are provided 4107 as to their applicability for the baseline use case of OLSRv2. 4109 A party will have to manage n^2 static keys, where n may become 4110 large. 4112 The baseline use case of OLSRv2 uses only one or a small set of 4113 manually managed shared secrets in the whole MANET. 4115 Any stream cipher (such as RC4 [TK], AES-CTR [NIST], or AES-CCM 4116 [WHF]) is used. 4118 A stream cipher is not envisioned for use to generate ICVs for 4119 OLSRv2 control messages. 4121 An initialization vector (IV) might be reused, especially an implicit 4122 IV. Note that random or pseudo-random explicit IVs are not a problem 4123 unless the probability of repetition is high. 4125 An IV is not envisioned for use to generate ICVs for OLSRv2 4126 control messages. 4128 Large amounts of data might need to be encrypted in a short time, 4129 causing frequent change of the short-term session key. 4131 Integrity Check Values (ICVs) are required only for OLSRv2 control 4132 messages, which are low-volume messages. 4134 Long-term session keys are used by more than two parties. Multicast 4135 is a necessary exception, but multicast key management standards are 4136 emerging in order to avoid this in the future. Sharing long-term 4137 session keys should generally be discouraged. 4139 OLSRv2 control messages are all sent using link local multicast. 4141 The likely operational environment is one where personnel (or device) 4142 turnover is frequent, causing frequent change of the short-term 4143 session key. 4145 This is not an intended deployment of OLSRv2. For longer-term 4146 OLSRv2 deployments, alternative security mechanisms (e.g., 4147 including re-keying) SHOULD be considered. 4149 Section 2.2 of [BCP107] stipulates that "Manual key management may be 4150 a reasonable approach in any of [a given set of] situations". These 4151 situation are listed below, for each of which arguments are provided 4152 as to their applicability for the baseline use case of OLSRv2. 4154 The environment has very limited available bandwidth or very high 4155 round-trip times. Public key systems tend to require long messages 4156 and lots of computation; symmetric key alternatives, such as 4157 Kerberos, often require several round trips and interaction with 4158 third parties. 4160 As previously noted, there may not be the required infrastructure 4161 (cryptographic authority) present (or, if present, may not be 4162 reachable) in the MANET. Bandwidth in a MANET is commonly 4163 limited, both by being a radio environment, and by the need for 4164 any signaling to consume a minimal proportion thereof, and round 4165 trip times may also be significant. 4167 The information being protected has low value. 4169 This depends on the OLSRv2 use case, but the information being 4170 protected is OLSRv2 control traffic, which is of at least moderate 4171 value, thus this case does not apply. 4173 The total volume of traffic over the entire lifetime of the long-term 4174 session key will be very low. 4176 Integrity Check Values (ICVs) are required only for OLSRv2 control 4177 messages, which are low-volume messages. 4179 The scale of each deployment is very limited 4181 A typical use case for OLSRv2 may involve only tens of devices - 4182 with even the largest use cases for OLSRv2 being small by Internet 4183 standards. 4185 24. IANA Considerations 4187 This specification defines one Message Type, which must be allocated 4188 from the "Message Types" repository of [RFC5444], two Message TLV 4189 Types, which must be allocated from the "Message TLV Types" 4190 repository of [RFC5444], and four Address Block TLV Types, which must 4191 be allocated from the "Address Block TLV Types" repository of 4192 [RFC5444]. 4194 24.1. Expert Review: Evaluation Guidelines 4196 For the registries where an Expert Review is required, the designated 4197 expert SHOULD take the same general recommendations into 4198 consideration as are specified by [RFC5444]. 4200 24.2. Message Types 4202 This specification defines one Message Type, to be allocated from the 4203 0-223 range of the "Message Types" namespace defined in [RFC5444], as 4204 specified in Table 8. 4206 +------+----------------------------------------------+ 4207 | Type | Description | 4208 +------+----------------------------------------------+ 4209 | TBD1 | TC : Topology Control (MANET-wide signaling) | 4210 +------+----------------------------------------------+ 4212 Table 8: Message Type assignment 4214 24.3. Message-Type-Specific TLV Type Registries 4216 IANA is requested to create a registry for Message-Type-specific 4217 Message TLVs for TC messages, in accordance with Section 6.2.1 of 4218 [RFC5444], and with initial assignments and allocation policies as 4219 specified in Table 9. 4221 +---------+-------------+-------------------+ 4222 | Type | Description | Allocation Policy | 4223 +---------+-------------+-------------------+ 4224 | 128-223 | Unassigned | Expert Review | 4225 +---------+-------------+-------------------+ 4227 Table 9: TC Message-Type-specific Message TLV Types 4229 IANA is requested to create a registry for Message-Type-specific 4230 Address Block TLVs for TC messages, in accordance with Section 6.2.1 4231 of [RFC5444], and with initial assignments and allocation policies as 4232 specified in Table 10. 4234 +---------+-------------+-------------------+ 4235 | Type | Description | Allocation Policy | 4236 +---------+-------------+-------------------+ 4237 | 128-223 | Unassigned | Expert Review | 4238 +---------+-------------+-------------------+ 4240 Table 10: TC Message-Type-specific Address Block TLV Types 4242 24.4. Message TLV Types 4244 This specification defines two Message TLV Types, which must be 4245 allocated from the "Message TLV Types" namespace defined in 4246 [RFC5444]. IANA is requested to make allocations in the 0-127 range 4247 for these types. This will create two new Type Extension registries 4248 with assignments as specified in Table 11 and Table 12. 4249 Specifications of these TLVs are in Section 13.3.1. Each of these 4250 TLVs MUST NOT be included more than once in a Message TLV Block. 4252 +-------------+------+-----------+---------------------+------------+ 4253 | Name | Type | Type | Description | Allocation | 4254 | | | Extension | | Policy | 4255 +-------------+------+-----------+---------------------+------------+ 4256 | MPR_WILLING | TBD2 | 0 | Bits 0-3 specify | | 4257 | | | | the originating | | 4258 | | | | router's | | 4259 | | | | willingness to act | | 4260 | | | | as a flooding MPR; | | 4261 | | | | bits 4-7 specify | | 4262 | | | | the originating | | 4263 | | | | router's | | 4264 | | | | willingness to act | | 4265 | | | | as a routing MPR. | | 4266 | MPR_WILLING | TBD2 | 1-255 | Unassigned. | Expert | 4267 | | | | | Review | 4268 +-------------+------+-----------+---------------------+------------+ 4270 Table 11: Message TLV Type assignment: MPR_WILLING 4272 +--------------+------+-----------+--------------------+------------+ 4273 | Name | Type | Type | Description | Allocation | 4274 | | | Extension | | Policy | 4275 +--------------+------+-----------+--------------------+------------+ 4276 | CONT_SEQ_NUM | TBD3 | 0 | COMPLETE: | | 4277 | | | | Specifies a | | 4278 | | | | content sequence | | 4279 | | | | number for this | | 4280 | | | | complete message. | | 4281 | CONT_SEQ_NUM | TBD3 | 1 | INCOMPLETE: | | 4282 | | | | Specifies a | | 4283 | | | | content sequence | | 4284 | | | | number for this | | 4285 | | | | incomplete | | 4286 | | | | message. | | 4287 | CONT_SEQ_NUM | TBD3 | 2-255 | Unassigned. | Expert | 4288 | | | | | Review | 4289 +--------------+------+-----------+--------------------+------------+ 4291 Table 12: Message TLV Type assignment: CONT_SEQ_NUM 4293 Type extensions indicated as Expert Review SHOULD be allocated as 4294 described in [RFC5444], based on Expert Review as defined in 4295 [RFC5226]. 4297 24.5. Address Block TLV Types 4299 This specification defines four Address Block TLV Types, which must 4300 be allocated from the "Address Block TLV Types" namespace defined in 4301 [RFC5444]. IANA are requested to make allocations in the 8-127 range 4302 for these types. This will create four new Type Extension registries 4303 with assignments as specified in Table 13, Table 14, Table 15 and 4304 Table 16. Specifications of these TLVs are in Section 13.3.2. 4306 +-------------+------+-----------+-------------------+--------------+ 4307 | Name | Type | Type | Description | Allocation | 4308 | | | Extension | | Policy | 4309 +-------------+------+-----------+-------------------+--------------+ 4310 | LINK_METRIC | TBD4 | 0 | Link metric | | 4311 | | | | meaning assigned | | 4312 | | | | by administrative | | 4313 | | | | action. | | 4314 | LINK_METRIC | TBD4 | 1-223 | Unassigned. | Expert | 4315 | | | | | Review | 4316 | LINK_METRIC | TBD4 | 224-255 | Unassigned. | Experimental | 4317 | | | | | Use | 4318 +-------------+------+-----------+-------------------+--------------+ 4319 Table 13: Address Block TLV Type assignment: LINK_METRIC 4321 All LINK_METRIC TLVs, whatever their type extension, MUST use their 4322 value field to encode the kind and value (in the interval 4323 MINIMUM_METRIC, to MAXIMUM_METRIC, inclusive) of a link metric as 4324 specified in Section 6 and Section 13.3.2. An assignment of a 4325 LINK_METRIC TLV type extension MUST specify the physical meaning, and 4326 mapping of that physical meaning to the representable values in the 4327 indicated interval, of the link metric. 4329 +------+------+-----------+----------------------------+------------+ 4330 | Name | Type | Type | Description | Allocation | 4331 | | | Extension | | Policy | 4332 +------+------+-----------+----------------------------+------------+ 4333 | MPR | TBD5 | 0 | Specifies that a given | | 4334 | | | | network address is of a | | 4335 | | | | router selected as a | | 4336 | | | | flooding MPR (FLOODING = | | 4337 | | | | 1), that a given network | | 4338 | | | | address is of a router | | 4339 | | | | selected as a routing MPR | | 4340 | | | | (ROUTING = 2), or both | | 4341 | | | | (FLOOD_ROUTE = 3). | | 4342 | MPR | TBD5 | 1-255 | Unassigned. | Expert | 4343 | | | | | Review | 4344 +------+------+-----------+----------------------------+------------+ 4346 Table 14: Address Block TLV Type assignment: MPR 4348 +---------------+------+-----------+-------------------+------------+ 4349 | Name | Type | Type | Description | Allocation | 4350 | | | Extension | | Policy | 4351 +---------------+------+-----------+-------------------+------------+ 4352 | NBR_ADDR_TYPE | TBD6 | 0 | Specifies that a | | 4353 | | | | given network | | 4354 | | | | address is of a | | 4355 | | | | neighbor reached | | 4356 | | | | via the | | 4357 | | | | originating | | 4358 | | | | router, if it is | | 4359 | | | | an originator | | 4360 | | | | address | | 4361 | | | | (ORIGINATOR = 1), | | 4362 | | | | is a routable | | 4363 | | | | address (ROUTABLE | | 4364 | | | | = 2), or if it is | | 4365 | | | | both | | 4366 | | | | (ROUTABLE_ORIG = | | 4367 | | | | 3). | | 4368 | NBR_ADDR_TYPE | TBD6 | 1-255 | Unassigned. | Expert | 4369 | | | | | Review | 4370 +---------------+------+-----------+-------------------+------------+ 4372 Table 15: Address Block TLV Type assignment: NBR_ADDR_TYPE 4374 +---------+------+-----------+-------------------------+------------+ 4375 | Name | Type | Type | Description | Allocation | 4376 | | | extension | | Policy | 4377 +---------+------+-----------+-------------------------+------------+ 4378 | GATEWAY | TBD7 | 0 | Specifies that a given | | 4379 | | | | network address is | | 4380 | | | | reached via a gateway | | 4381 | | | | on the originating | | 4382 | | | | router, with value | | 4383 | | | | equal to the number of | | 4384 | | | | hops. | | 4385 | GATEWAY | TBD7 | 1-255 | | Expert | 4386 | | | | | Review | 4387 +---------+------+-----------+-------------------------+------------+ 4389 Table 16: Address Block TLV Type assignment: GATEWAY 4391 Type extensions indicated as Expert Review SHOULD be allocated as 4392 described in [RFC5444], based on Expert Review as defined in 4393 [RFC5226]. 4395 24.6. NBR_ADDR_TYPE and MPR Values 4397 Note: This section does not require any IANA action, as the required 4398 information is included in the descriptions of the MPR and 4399 NBR_ADDR_TYPE Address Block TLVs allocated in Section 24.5. This 4400 information is recorded here for clarity, and for use elsewhere in 4401 this specification. 4403 The Values which the MPR Address Block TLV can use are the following: 4405 o FLOODING := 1; 4407 o ROUTING := 2; 4409 o FLOOD_ROUTE := 3. 4411 The Values which the NBR_ADDR_TYPE Address Block TLV can use are the 4412 following: 4414 o ORIGINATOR := 1; 4416 o ROUTABLE := 2; 4418 o ROUTABLE_ORIG := 3. 4420 25. Contributors 4422 This specification is the result of the joint efforts of the 4423 following contributors -- listed alphabetically. 4425 o Cedric Adjih, INRIA, France, 4427 o Emmanuel Baccelli, INRIA , France, 4429 o Thomas Heide Clausen, LIX, France, 4431 o Justin Dean, NRL, USA, 4433 o Christopher Dearlove, BAE Systems, UK, 4434 4436 o Ulrich Herberg, Fujitsu Laboratories of America, USA, 4437 4439 o Satoh Hiroki, Hitachi SDL, Japan, 4441 o Philippe Jacquet, Alcatel Lucent Bell Labs, France, 4442 4444 o Monden Kazuya, Hitachi SDL, Japan, 4446 o Kenichi Mase, Niigata University, Japan, 4448 o Ryuji Wakikawa, Toyota, Japan, 4450 26. Acknowledgments 4452 The authors would like to acknowledge the team behind OLSRv1, as 4453 listed in RFC3626, including Anis Laouiti (INT), Pascale Minet 4454 (INRIA), Paul Muhlethaler (INRIA), Amir Qayyum (M.A. Jinnah 4455 University), and Laurent Viennot (INRIA) for their contributions. 4457 The authors would like to gratefully acknowledge the following people 4458 for intense technical discussions, early reviews and comments on the 4459 specification and its components (listed alphabetically): Khaldoun Al 4460 Agha (LRI), Teco Boot (Infinity Networks), Ross Callon (Juniper), 4461 Song-Yean Cho (Samsung), Alan Cullen (BAE Systems), Louise Lamont 4462 (CRC), Li Li (CRC), Joseph Macker (NRL), Richard Ogier (SRI), Charles 4463 E. Perkins (Futurewei), Henning Rogge (Frauenhofer FKIE), and the 4464 entire IETF MANET Working Group. 4466 Finally, the authors would like to express their gratitude to the 4467 Area Directors for providing valuable review comments during the IESG 4468 evaluation, in particular (listed alphabetically) Benoit Claise, 4469 Adrian Farrel, Stephen Farrell, Barry Leiba, Pete Resnick, and Martin 4470 Stiemerling. 4472 27. References 4474 27.1. Normative References 4476 [RFC2119] Bradner, S., "Key words for use in RFCs to 4477 Indicate Requirement Levels", RFC 2119, BCP 14, 4478 March 1997. 4480 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, 4481 "Jitter Considerations in Mobile Ad Hoc Networks 4482 (MANETs)", RFC 5148, February 2008. 4484 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for 4485 Writing an IANA Considerations Section in RFCs", 4486 RFC 5226, BCP 26, May 2008. 4488 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. 4489 Adjih, "Generalized Mobile Ad Hoc Network (MANET) 4490 Packet/Message Format", RFC 5444, February 2009. 4492 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi- 4493 Value Time in Mobile Ad Hoc Networks (MANETs)", 4494 RFC 5497, March 2009. 4496 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc 4497 Network (MANET) Protocols", RFC 5498, March 2009. 4499 [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile 4500 Ad Hoc Network (MANET) Neighborhood Discovery 4501 Protocol (NHDP)", RFC 6130, April 2011. 4503 [RFC6622bis] Herberg, U., Clausen, T., and C. Dearlove, 4504 "Integrity Check Value and Timestamp TLV 4505 Definitions for Mobile Ad Hoc Networks (MANETs)", 4506 work in progress draft-ietf-manet-rfc6622-bis-01, 4507 March 2013. 4509 [OLSRv2-integrity] Herberg, U., Dearlove, C., and T. Clausen, 4510 "Integrity Protection for Control Messages in 4511 NHDP and OLSRv2", work in 4512 progress draft-ietf-manet-nhdp-olsrv2-sec-01, 4513 March 2013. 4515 27.2. Informative References 4517 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc 4518 Networking (MANET): Routing Protocol Performance 4519 Issues and Evaluation Considerations", RFC 2501, 4520 January 1999. 4522 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link 4523 State Routing Protocol", RFC 3626, October 2003. 4525 [HIPERLAN] ETSI, "ETSI STC-RES10 Committee. Radio equipment 4526 and systems: HIPERLAN type 1, functional 4527 specifications ETS 300-652", June 1996. 4529 [HIPERLAN2] Jacquet, P., Minet, P., Muhlethaler, P., and N. 4530 Rivierre, "Increasing reliability in cable free 4531 radio LANs: Low level forwarding in HIPERLAN.", 4532 1996. 4534 [MPR] Qayyum, A., Viennot, L., and A. Laouiti, 4535 "Multipoint relaying: An efficient technique for 4536 flooding in mobile wireless networks.", 2001. 4538 [FSR] Pei, G., Gerla, M., and T. Chen, "Fisheye state 4539 routing in mobile ad hoc networks", 2000. 4541 [FSLS] Santivanez, C., Ramanathan, R., and I. 4542 Stavrakakis, "Making link-state routing scale for 4543 ad hoc networks", 2000. 4545 [McCabe] McCabe, A., Dearlove, C., Fredin, M., and L. 4546 Axelsson, "Scalability Modelling of Ad Hoc 4547 Routing Protocols - A Comparison of OLSR and 4548 DSR", 2004. 4550 [BCP107] Bellovin, S. and R. Housley, "Guidelines for 4551 Cryptographic Key Management", BCP 107, RFC 4107, 4552 June 2005. 4554 Appendix A. Constraints 4556 Updates to the Local Information Base, the Neighborhood Information 4557 Base or the Topology Information Base MUST ensure that all 4558 constraints specified in this appendix are maintained, as well as 4559 those specified in [RFC6130]. This is the case for the processing, 4560 specified in this document. Any protocol extension or outside 4561 process, which updates the Neighborhood Information Base or the 4562 Topology Information Base, MUST also ensure that these constraints 4563 are maintained. 4565 In each Originator Tuple: 4567 o O_orig_addr MUST NOT equal any other O_orig_addr. 4569 o O_orig_addr MUST NOT equal this router's originator address. 4571 In each Local Attached Network Tuple: 4573 o AL_net_addr MUST NOT equal any other AL_net_addr. 4575 o AL_net_addr MUST NOT equal or be a sub-range of any network 4576 address in the I_local_iface_addr_list of any Local Interface 4577 Tuple. 4579 o AL_net_addr MUST NOT equal this router's originator address, or 4580 equal the O_orig_addr in any Originator Tuple. 4582 o AL_dist MUST NOT be less than zero. 4584 In each Link Tuple: 4586 o L_neighbor_iface_addr_list MUST NOT contain any network address 4587 that AL_net_addr of any Local Attached Network Tuple equals or is 4588 a sub-range of. 4590 o if L_in_metric != UNKNOWN_METRIC then L_in_metric MUST be 4591 representable in the defined compressed form. 4593 o if L_out_metric != UNKNOWN_METRIC then L_out_metric MUST be 4594 representable in the defined compressed form. 4596 o If L_mpr_selector = true, then L_status = SYMMETRIC. 4598 In each Neighbor Tuple: 4600 o N_orig_addr MUST NOT be changed to unknown. 4602 o N_orig_addr MUST NOT equal this router's originator address, or 4603 equal O_orig_addr in any Originator Tuple. 4605 o N_orig_addr MUST NOT equal the AL_net_addr in any Local Attached 4606 Network Tuple. 4608 o If N_orig_addr != unknown, then N_orig_addr MUST NOT equal the 4609 N_orig_addr in any other Neighbor Tuple. 4611 o N_neighbor_addr_list MUST NOT contain any network address which 4612 includes this router's originator address, the O_orig_addr in any 4613 Originator Tuple, or equal or have as a sub-range the AL_net_addr 4614 in any Local Attached Network Tuple. 4616 o If N_orig_addr = unknown, then N_will_flooding = WILL_NEVER, 4617 N_will_routing = WILL_NEVER, N_flooding_mpr, N_routing_mpr = 4618 false, N_mpr_selector = false, and N_advertised = false. 4620 o N_in_metric MUST equal the minimum value of the L_in_metric values 4621 of all corresponding Link Tuples with L_status = SYMMETRIC and 4622 L_in_metric != UNKNOWN_METRIC, if any, otherwise N_in_metric = 4623 UNKNOWN_METRIC. 4625 o N_out_metric MUST equal the minimum value of the L_out_metric 4626 values of all corresponding Link Tuples with L_status = SYMMETRIC 4627 and L_out_metric != UNKNOWN_METRIC, if any, otherwise N_out_metric 4628 = UNKNOWN_METRIC. 4630 o N_will_flooding and N_will_routing MUST be in the range from 4631 WILL_NEVER to WILL_ALWAYS, inclusive. 4633 o If N_flooding_mpr = true, then N_symmetric MUST be true, 4634 N_out_metric MUST NOT equal UNKNOWN_METRIC and N_will_flooding 4635 MUST NOT equal WILL_NEVER. 4637 o If N_routing_mpr = true, then N_symmetric MUST be true, 4638 N_in_metric MUST NOT equal UNKNOWN_METRIC and N_will_routing MUST 4639 NOT equal WILL_NEVER. 4641 o If N_symmetric = true and N_flooding_mpr = false, then 4642 N_will_flooding MUST NOT equal WILL_ALWAYS. 4644 o If N_symmetric = true and N_routing_mpr = false, then 4645 N_will_routing MUST NOT equal WILL_ALWAYS. 4647 o If N_mpr_selector = true, then N_advertised MUST be true. 4649 o If N_advertised = true, then N_symmetric MUST be true and 4650 N_out_metric MUST NOT equal UNKNOWN_METRIC. 4652 In each Lost Neighbor Tuple: 4654 o NL_neighbor_addr MUST NOT include this router's originator 4655 address, the O_orig_addr in any Originator Tuple, or equal or have 4656 as a sub-range the AL_net_addr in any Local Attached Network 4657 Tuple. 4659 In each 2-Hop Tuple: 4661 o N2_2hop_addr MUST NOT equal this router's originator address, 4662 equal the O_orig_addr in any Originator Tuple, or equal or have as 4663 a sub-range the AL_net_addr in any Local Attached Network Tuple. 4665 o if N2_in_metric != UNKNOWN_METRIC then N2_in_metric MUST be 4666 representable in the defined compressed form. 4668 o if N2_out_metric != UNKNOWN_METRIC then N2_out_metric MUST be 4669 representable in the defined compressed form. 4671 In each Advertising Remote Router Tuple: 4673 o AR_orig_addr MUST NOT be in any network address in the 4674 I_local_iface_addr_list in any Local Interface Tuple or be in the 4675 IR_local_iface_addr in any Removed Interface Address Tuple. 4677 o AR_orig_addr MUST NOT equal this router's originator address or 4678 equal the O_orig_addr in any Originator Tuple. 4680 o AR_orig_addr MUST NOT be in the AL_net_addr in any Local Attached 4681 Network Tuple. 4683 o AR_orig_addr MUST NOT equal the AR_orig_addr in any other 4684 Advertising Remote Router Tuple. 4686 In each Router Topology Tuple: 4688 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4689 = TR_from_orig_addr. 4691 o TR_to_orig_addr MUST NOT be in any network address in the 4692 I_local_iface_addr_list in any Local Interface Tuple or be in the 4693 IR_local_iface_addr in any Removed Interface Address Tuple. 4695 o TR_to_orig_addr MUST NOT equal this router's originator address or 4696 equal the O_orig_addr in any Originator Tuple. 4698 o TR_to_orig_addr MUST NOT be in the AL_net_addr in any Local 4699 Attached Network Tuple. 4701 o The ordered pair (TR_from_orig_addr, TR_to_orig_addr) MUST NOT 4702 equal the corresponding pair for any other Router Topology Tuple. 4704 o TR_seq_number MUST NOT be greater than AR_seq_number in the 4705 Advertising Remote Router Tuple with AR_orig_addr = 4706 TR_from_orig_addr. 4708 o TR_metric MUST be representable in the defined compressed form. 4710 In each Routable Address Topology Tuple: 4712 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4713 = TA_from_orig_addr. 4715 o TA_dest_addr MUST be routable. 4717 o TA_dest_addr MUST NOT overlap any network address in the 4718 I_local_iface_addr_list in any Local Interface Tuple or overlap 4719 the IR_local_iface_addr in any Removed Interface Address Tuple. 4721 o TA_dest_addr MUST NOT include this router's originator address or 4722 include the O_orig_addr in any Originator Tuple. 4724 o TA_dest_addr MUST NOT equal or have as a sub-range the AL_net_addr 4725 in any Local Attached Network Tuple. 4727 o The ordered pair (TA_from_orig_addr, TA_dest_addr) MUST NOT equal 4728 the corresponding pair for any other Attached Network Tuple. 4730 o TA_seq_number MUST NOT be greater than AR_seq_number in the 4731 Advertising Remote Router Tuple with AR_orig_addr = 4732 TA_from_orig_addr. 4734 o TA_metric MUST be representable in the defined compressed form. 4736 In each Attached Network Tuple: 4738 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4739 = AN_orig_addr. 4741 o AN_net_addr MUST NOT equal or be a sub-range of any network 4742 address in the I_local_iface_addr_list in any Local Interface 4743 Tuple or be a sub-range of the IR_local_iface_addr in any Removed 4744 Interface Address Tuple. 4746 o AN_net_addr MUST NOT equal this router's originator address or 4747 equal the O_orig_addr in any Originator Tuple. 4749 o AN_net_addr MUST NOT equal the AL_net_addr in any Local Attached 4750 Network Tuple. 4752 o The ordered pair (AN_orig_addr, AN_net_addr) MUST NOT equal the 4753 corresponding pair for any other Attached Network Tuple. 4755 o AN_seq_number MUST NOT be greater than AR_seq_number in the 4756 Advertising Remote Router Tuple with AR_orig_addr = AN_orig_addr. 4758 o AN_dist MUST NOT be less than zero. 4760 o AN_metric MUST be representable in the defined compressed form. 4762 Appendix B. Example Algorithm for Calculating MPRs 4764 The following specifies an algorithm which MAY be used to select an 4765 MPR Set given a Neighbor Graph, as defined in Section 18.2 and 4766 Section 18.3. 4768 This algorithm selects an MPR Set M that is a subset of the set N1 4769 that is part of the Neighbor Graph. This algorithm assumes that a 4770 subset I of N1 is pre-selected as MPRs, i.e., that M will contain I. 4772 B.1. Additional Notation 4774 The following additional notation, in addition to that in 4775 Section 18.2 will be used by this algorithm: 4777 N: 4778 A subset of N2, consisting of those elements y in N2 such that 4779 either d1(y) is not defined, or there is at least one x in N1 such 4780 that d(x,y) is defined and d(x,y) < d1(y). 4782 D(x): 4783 For an element x in N1, the number of elements y in N for which 4784 d(x,y) is defined and has minimal value among the d(z,y) for all z 4785 in N1. 4787 R(x,M): 4788 For an element x in N1, the number of elements y in N for which 4789 d(x,y) is defined, has minimal value among the d(z,y) for all z in 4790 N1, and no such minimal values have z in M. (Note that, denoting 4791 the empty set by 0, D(x) = R(x,0).) 4793 B.2. MPR Selection Algorithm 4795 To create the MPR Set M, starting with M := I: 4797 1. Add all elements x in N1 that have W(x) = WILL_ALWAYS to M. 4799 2. For each element y in N for which there is only one element x in 4800 N1 such that d2(x,y) is defined, add that element x to M. 4802 3. While there exists any element x in N1 with R(x,M) > 0: 4804 1. Select an element x in N1 with R(x,M) > 0 in the following 4805 order of priority, and then add to M: 4807 + greatest W(x), THEN; 4809 + greatest R(x,M), THEN; 4811 + greatest D(x), THEN; 4813 + any choice, which MAY be based on other criteria (for 4814 example a router MAY choose to prefer a neighbor as an MPR 4815 if that neighbor has already selected the router as an MPR 4816 of the same type, MAY prefer a neighbor based on 4817 information freshness, or MAY prefer a neighbor based on 4818 length of time previously selected as an MPR) or MAY be 4819 random. 4821 4. OPTIONAL: consider each element x in M, but not in I, in turn and 4822 if x can be removed from M while still leaving it satisfying the 4823 definition of an MPR Set, then remove that element x from M. 4824 Elements MAY be considered in any order, e.g., in order of 4825 increasing W(x). 4827 Appendix C. Example Algorithm for Calculating the Routing Set 4829 The following procedure is given as an example for calculating the 4830 Routing Set using a variation of Dijkstra's algorithm. First all 4831 Routing Tuples are removed, and then, using the selections and 4832 definitions in Appendix C.1, the procedures in the following sections 4833 (each considered a "stage" of the processing) are applied in turn. 4835 C.1. Local Interfaces and Neighbors 4837 The following selections and definitions are made: 4839 1. For each Local Interface Tuple, select a network address from its 4840 I_local_iface_addr_list, this is defined as the selected address 4841 for this Local Interface Tuple. 4843 2. For each Link Tuple, the selected address of its corresponding 4844 Local Interface Tuple is defined as the selected local address 4845 for this Local Interface Tuple. 4847 3. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4848 != UNKNOWN_METRIC, select a Link Tuple with L_status = SYMMETRIC 4849 for which this is the corresponding Neighbor Tuple and has 4850 L_out_metric = N_out_metric. This is defined as the selected 4851 Link Tuple for this Neighbor Tuple. 4853 4. For each network address (N_orig_addr or in N_neighbor_addr_list, 4854 the "neighbor address") from a Neighbor Tuple with N_symmetric = 4855 true and N_out_metric != UNKNOWN_METRIC, select a Link Tuple (the 4856 "selected Link Tuple") from those for which this is the 4857 corresponding Neighbor Tuple, have L_status = SYMMETRIC, and have 4858 L_out_metric = N_out_metric, by: 4860 1. If there is such a Link Tuple whose 4861 L_neighbor_iface_addr_list contains the neighbor address, 4862 select that Link Tuple. 4864 2. Otherwise select the selected Link Tuple for this Neighbor 4865 Tuple. 4867 Then for this neighbor address: 4869 3. The selected local address is defined as the selected local 4870 address for the selected Link Tuple. 4872 4. The selected link address is defined as an address from the 4873 L_neighbor_iface_addr_list of the selected Link Tuple, if 4874 possible equal to this neighbor address. 4876 5. Routing Tuple preference is decided by preference for minimum 4877 R_dist, then for minimum R_dist, and then for preference for 4878 corresponding Neighbor Tuples in this order: 4880 * For greater N_will_routing. 4882 * For N_mpr_selector = true over N_mpr_selector = false. 4884 Note that preferred Routing Tuples SHOULD be used. Routing 4885 Tuples with minimum R_metric MUST be used, this is specified 4886 outside the definition of preference. An implementation MAY 4887 modify this definition of preference (including for minimum 4888 R_dist) without otherwise affecting this algorithm. 4890 C.2. Add Neighbor Routers 4892 The following procedure is executed once. 4894 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4895 != UNKNOWN_METRIC, add a Routing Tuple with: 4897 * R_dest_addr := N_orig_addr; 4899 * R_next_iface_addr := selected link address for N_orig_addr; 4901 * R_local_iface_addr := selected local address for N_orig_addr; 4903 * R_metric := N_out_metric; 4905 * R_dist := 1. 4907 C.3. Add Remote Routers 4909 The following procedure is executed once. 4911 1. Add a label that may be "used" or "unused" to each Routing Tuple, 4912 with all initial values equal to unused. (Note that this label 4913 is only required during this algorithm.) 4915 2. If there are no unused Routing Tuples then this stage is 4916 complete, otherwise repeat the following until that is the case. 4918 1. Find the unused Routing Tuple with minimum R_metric (if more 4919 than one, pick any) and denote it the "current Routing 4920 Tuple". 4922 2. Mark the current Routing Tuple as used. 4924 3. For each Router Topology Tuple, with: 4926 + TR_from_orig_addr = R_dest_addr of the current Routing 4927 Tuple. 4929 2. Define: 4931 - new_metric := R_metric of the current Routing Tuple + 4932 TR_metric; 4934 - new_dist := R_dist of the current Routing Tuple + 1. 4936 3. If there is no Routing Tuple with R_dest_addr = 4937 TR_to_orig_addr, then create an unused Routing Tuple 4938 with: 4940 - R_dest_addr := TR_to_orig_addr; 4942 - R_next_iface_addr := R_next_iface_addr of the current 4943 Routing Tuple; 4945 - R_local_iface_addr := R_local_iface_addr of the 4946 current Routing Tuple; 4948 - R_metric := new_metric; 4950 - R_dist := new_dist. 4952 4. Otherwise, if there is an unused Routing Tuple with 4953 R_dest_addr = TR_to_orig_addr, and either new_metric < 4954 R_metric or (new_metric = R_metric and the updated 4955 Routing Tuple would be preferred) then update this 4956 Routing Tuple to have: 4958 - R_next_iface_addr := R_next_iface_addr of the current 4959 Routing Tuple; 4961 - R_local_iface_addr := R_local_iface_addr of the 4962 current Routing Tuple; 4964 - R_metric := new_metric; 4966 - R_dist := new_dist. 4968 C.4. Add Neighbor Addresses 4970 The following procedure is executed once. 4972 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4973 != UNKNOWN_METRIC: 4975 1. For each network address (the "neighbor address") in 4976 N_neighbor_addr_list, if the neighbor address is not equal to 4977 the R_dest_addr of any Routing Tuple, then add a new Routing 4978 Tuple, with: 4980 + R_dest_addr := neighbor address; 4982 + R_next_iface_addr := selected link address for the 4983 neighbor address; 4985 + R_local_iface_addr := selected local address for the 4986 neighbor address; 4988 + R_metric := N_out_metric; 4990 + R_dist := 1. 4992 C.5. Add Remote Routable Addresses 4994 The following procedure is executed once. 4996 1. For each Routable Address Topology Tuple, if: 4998 * TA_dest_addr is not equal to the R_dest_addr of any Routing 4999 Tuple added in an earlier stage; AND 5001 * TA_from_orig_addr is equal to the R_dest_addr of a Routing 5002 Tuple (the "previous Routing Tuple"), 5004 then add a new Routing Tuple, with: 5006 * R_dest_addr := TA_dest_addr; 5008 * R_next_iface_addr := R_next_iface_addr of the previous Routing 5009 Tuple; 5011 * R_local_iface_addr := R_local_iface_addr of the previous 5012 Routing Tuple; 5014 * R_metric := R_metric of the previous Routing Tuple + 5015 TA_metric. 5017 * R_dist := R_dist of the previous Routing Tuple + 1. 5019 There may be more than one Routing Tuple that may be added for an 5020 R_dest_addr in this stage. If so, then, for each such 5021 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 5022 selected, otherwise a Routing Tuple which is preferred SHOULD be 5023 added. 5025 C.6. Add Attached Networks 5027 The following procedure is executed once. 5029 1. For each Attached Network Tuple, if: 5031 * AN_net_addr is not equal to the R_dest_addr of any Routing 5032 Tuple added in an earlier stage; AND 5034 * AN_orig_addr is equal to the R_dest_addr of a Routing Tuple 5035 (the "previous Routing Tuple), 5037 then add a new Routing Tuple, with: 5039 * R_dest_addr := AN_net_addr; 5041 * R_next_iface_addr := R_next_iface_addr of the previous Routing 5042 Tuple; 5044 * R_local_iface_addr := R_local_iface_addr of the previous 5045 Routing Tuple; 5047 * R_metric := R_metric of the previous Routing Tuple + 5048 AN_metric; 5050 * R_dist := R_dist of the previous Routing Tuple + AN_dist. 5052 There may be more than one Routing Tuple that may be added for an 5053 R_dest_addr in this stage. If so, then, for each such 5054 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 5055 selected, otherwise a Routing Tuple which is preferred SHOULD be 5056 added. 5058 C.7. Add 2-Hop Neighbors 5060 The following procedure is executed once. 5062 1. For each 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC, if: 5064 * N2_2hop_addr is a routable address; AND 5066 * N2_2hop_addr is not equal to the R_dest_addr of any Routing 5067 Tuple added in an earlier stage; AND 5069 * the Routing Tuple with R_dest_addr = N_orig_addr of the 5070 corresponding Neighbor Tuple (the "previous Routing Tuple") 5071 has R_dist = 1, 5073 then add a new Routing Tuple, with: 5075 * R_dest_addr := N2_2hop_addr; 5077 * R_next_iface_addr := R_next_iface_addr of the previous Routing 5078 Tuple; 5080 * R_local_iface_addr := R_local_iface_addr of the previous 5081 Routing Tuple; 5083 * R_metric := R_metric of the previous Routing Tuple + 5084 N_out_metric of the corresponding Neighbor Tuple; 5086 * R_dist := 2. 5088 There may be more than one Routing Tuple that may be added for an 5089 R_dest_addr in this stage. If so, then, for each such 5090 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 5091 selected, otherwise a Routing Tuple which is preferred SHOULD be 5092 added. 5094 Appendix D. TC Message Example 5096 TC messages are instances of [RFC5444] messages. This specification 5097 requires that TC messages contain and 5098 fields. It supports TC messages with any combination of remaining 5099 message header options and address encodings, enabled by [RFC5444] 5100 that convey the required information. As a consequence, there is no 5101 single way to represent how all TC messages look. This appendix 5102 illustrates a TC message, the exact values and content included are 5103 explained in the following text. 5105 The TC message's four bit Message Flags (MF) field has value 15 5106 indicating that the message header contains originator address, hop 5107 limit, hop count, and message sequence number fields. Its four bit 5108 Message Address Length (MAL) field has value 3, indicating addresses 5109 in the message have a length of four octets, here being IPv4 5110 addresses. The overall message length is 75 octets. 5112 The message has a Message TLV Block with content length 17 octets 5113 containing four TLVs. The first two TLVs are validity and interval 5114 times for the message. The third TLV is the content sequence number 5115 TLV used to carry the 2 octet ANSN, and (with default type extension 5116 zero, i.e., COMPLETE) indicating that the TC message is complete. 5117 The fourth TLV contains forwarding and routing willingness values for 5118 the originating router (FWILL and RWILL, respectively). Each TLV 5119 uses a TLV with Flags octet (MTLVF) value 16, indicating that it has 5120 a Value, but no type extension or start and stop indexes. The first 5121 two TLVs have a Value Length of 1 octet, the last has a Value Length 5122 of 2 octets. 5124 The message has two Address Blocks. (This is not necessary, the 5125 information could be conveyed using a single Address Block, the use 5126 of two Address Blocks, which is also allowed, is illustrative only.) 5127 The first Address Block contains 3 addresses, with Flags octet 5128 (ATLVF) value 128, hence with a Head section (with length 2 octets), 5129 but no Tail section, and hence with Mid sections with length two 5130 octets. The following TLV Block (content length 13 octets) contains 5131 two TLVs. The first TLV is a NBR_ADDR_TYPE TLV with Flags octet 5132 (ATLVF) value 16, indicating a single Value but no indexes. Thus all 5133 these addresses are associated with the Value (with Value Length 1 5134 octet) ROUTABLE_ORIG, i.e., they are originator addresses of 5135 advertised neighbors that are also routable addresses. The second 5136 TLV is a LINK_STATUS TLV with Flags octet (ATLVF) value 20, 5137 indicating a Value for each address, i.e., as the total Value Length 5138 is 6 octets, each address is associated with a Value with length two 5139 octets. These Value fields are each shown as having four bits 5140 indicating that they are outgoing neighbor metric values, and as 5141 having twelve bits that represent the metric value (the first four 5142 bits being the exponent, the remaining twelve bits the mantissa). 5144 The second Address Block contains 1 address, with Flags octet (ATLVF) 5145 176, indicating that there is a Head section (with length 2 octets), 5146 that the Tail section (with length 2 octets) consists of zero valued 5147 octets (not included), and that there is a single prefix length, 5148 which is 16. The network address is thus Head.0.0/16. The following 5149 TLV Block (content length 8 octets) includes two TLVs. The first has 5150 a Flags octet (ATLVF) of 16, again indicating that no indexes are 5151 needed, but that a Value (with Value Length 1 octet) is present, 5152 indicating the address distance as a number of hops. The second TLV 5153 is another LINK_METRIC TLV, as in the first Address TLV Block except 5154 with a Flags octet (ATLVF) value 16, indicating that a single Value 5155 is present. 5157 0 1 2 3 5158 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 5159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5160 | TC | MF=15 | MAL=3 | Message Length = 75 | 5161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5162 | Originator Address | 5163 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5164 | Hop Limit | Hop Count | Message Sequence Number | 5165 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5166 | Message TLV Block Length = 17 | VALIDITY_TIME | MTLVF = 16 | 5167 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5168 | Value Len = 1 | Value (Time) | INTERVAL_TIME | MTLVF = 16 | 5169 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5170 | Value Len = 1 | Value (Time) | CONT_SEQ_NUM | MTLVF = 16 | 5171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5172 | Value Len = 2 | Value (ANSN) | MPR_WILLING | 5173 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5174 | MTLVF = 16 | Value Len = 1 | FWILL | RWILL | Num Addrs = 3 | 5175 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5176 | ABF = 128 | Head Len = 2 | Head | 5177 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5178 | Mid | Mid | 5179 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5180 | Mid | Address TLV Block Length = 13 | 5181 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5182 | NBR_ADDR_TYPE | ATLVF = 16 | Value Len = 1 | ROUTABLE_ORIG | 5183 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5184 | LINK_METRIC | ATLVF = 20 | Value Len = 6 |0|0|0|1|Metric | 5185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5186 | Metric (cont) |0|0|0|1| Metric |0|0|0|1|Metric | 5187 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5188 | Metric (cont) | Num Addrs = 1 | ABF = 176 | Head Len = 2 | 5189 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5190 | Head | Tail Len = 2 | Pref Len = 16 | 5191 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5192 | Address TLV Block Length = 9 | GATEWAY | ATLVF = 16 | 5193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5194 | Value Len = 1 | Value (Hops) | LINK_METRIC | ATLVF = 16 | 5195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5196 | Value Len = 2 |0|0|0|1| Metric | 5197 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5199 Appendix E. Flow and Congestion Control 5201 Due to its proactive nature, this protocol has a natural control over 5202 the flow of its control traffic. Routers transmit control messages 5203 at predetermined rates specified and bounded by message intervals. 5205 This protocol employs [RFC6130] for local signaling, embedding MPR 5206 selection advertisement through a simple Address Block TLV, and 5207 router willingness advertisement (if any) as a single Message TLV. 5208 Local signaling, therefore, shares the characteristics and 5209 constraints of [RFC6130]. 5211 Furthermore, the use of MPRs can greatly reduce the signaling 5212 overhead from link state information dissemination in two ways, 5213 attaining both flooding reduction and topology reduction. First, 5214 using MPR flooding, the cost of distributing link state information 5215 throughout the network is reduced, as compared to when using blind 5216 flooding, since only MPRs need to forward link state declaration 5217 messages. Second, the amount of link state information for a router 5218 to declare is reduced to need only contain that router's MPR 5219 selectors. This reduces the size of a link state declaration as 5220 compared to declaring full link state information. In particular 5221 some routers may not need to declare any such information. In dense 5222 networks, the reduction of control traffic can be of several orders 5223 of magnitude compared to routing protocols using blind flooding 5224 [MPR]. This feature naturally provides more bandwidth for useful 5225 data traffic and pushes further the frontier of congestion. 5227 Since the control traffic is continuous and periodic, it keeps the 5228 quality of the links used in routing more stable. However, using 5229 some options, some control messages (HELLO messages or TC messages) 5230 may be intentionally sent in advance of their deadline in order to 5231 increase the responsiveness of the protocol to topology changes. 5232 This may cause a small, temporary, and local increase of control 5233 traffic, however this is at all times bounded by the use of minimum 5234 message intervals. 5236 A router that recognizes that the network is suffering from 5237 congestion can increase its message interval parameters. If this is 5238 done by most or all routers in the network, then the overall control 5239 traffic in the network will be reduced. Routers will have to take 5240 care in using this capability not to increase message interval 5241 parameters such that they cannot cope with network topology changes. 5242 Note that routers can make such decisions independently, it is not 5243 necessary for all routers to be using the same parameter values, nor 5244 is it necessary that all routers decide to change their intervals at 5245 the same time. 5247 Authors' Addresses 5249 Thomas Heide Clausen 5250 LIX, Ecole Polytechnique 5252 Phone: +33 6 6058 9349 5253 EMail: T.Clausen@computer.org 5254 URI: http://www.ThomasClausen.org/ 5256 Christopher Dearlove 5257 BAE Systems Advanced Technology Centre 5258 West Hanningfield Road 5259 Great Baddow, Chelmsford 5260 United Kingdom 5262 Phone: +44 1245 242194 5263 EMail: chris.dearlove@baesystems.com 5264 URI: http://www.baesystems.com/ 5266 Philippe Jacquet 5267 Alcatel-Lucent Bell Labs 5269 Phone: +33 6 7337 1880 5270 EMail: philippe.jacquet@alcatel-lucent.com 5272 Ulrich Herberg 5273 Fujitsu Laboratories of America 5274 1240 E. Arques Ave. 5275 Sunnyvale, CA 94085 5276 USA 5278 EMail: ulrich@herberg.name 5279 URI: http://www.herberg.name/