idnits 2.17.1 draft-ietf-manet-olsrv2-16.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 2, 2012) is 4214 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Informational RFC: RFC 5148 ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) -- Obsolete informational reference (is this intentional?): RFC 6622 (Obsoleted by RFC 7182) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique 4 Intended status: Standards Track C. Dearlove 5 Expires: April 5, 2013 BAE Systems ATC 6 P. Jacquet 7 Alcatel-Lucent Bell Labs 8 U. Herberg 9 Fujitsu Laboratories of America 10 October 2, 2012 12 The Optimized Link State Routing Protocol version 2 13 draft-ietf-manet-olsrv2-16 15 Abstract 17 This specification describes version 2 of the Optimized Link State 18 Routing (OLSRv2) protocol for Mobile Ad hoc NETworks (MANETs). 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on April 5, 2013. 37 Copyright Notice 39 Copyright (c) 2012 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 This document may contain material from IETF Documents or IETF 53 Contributions published or made publicly available before November 54 10, 2008. The person(s) controlling the copyright in some of this 55 material may not have granted the IETF Trust the right to allow 56 modifications of such material outside the IETF Standards Process. 57 Without obtaining an adequate license from the person(s) controlling 58 the copyright in such materials, this document may not be modified 59 outside the IETF Standards Process, and derivative works of it may 60 not be created outside the IETF Standards Process, except to format 61 it for publication as an RFC or to translate it into languages other 62 than English. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 6 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 68 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 69 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 10 70 4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 10 71 4.2. Routers and Interfaces . . . . . . . . . . . . . . . . . 13 72 4.3. Information Base Overview . . . . . . . . . . . . . . . . 14 73 4.3.1. Local Information Base . . . . . . . . . . . . . . . 14 74 4.3.2. Interface Information Bases . . . . . . . . . . . . . 14 75 4.3.3. Neighbor Information Base . . . . . . . . . . . . . . 14 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. Routing Set Use . . . . . . . . . . . . . . . . . . . . . 19 81 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 19 82 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 19 83 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 20 84 5.3. Interface Parameters . . . . . . . . . . . . . . . . . . 20 85 5.3.1. Received Message Validity Time . . . . . . . . . . . 20 86 5.4. Router Parameters . . . . . . . . . . . . . . . . . . . . 20 87 5.4.1. Local History Times . . . . . . . . . . . . . . . . . 20 88 5.4.2. Link Metric Parameters . . . . . . . . . . . . . . . 21 89 5.4.3. Message Intervals . . . . . . . . . . . . . . . . . . 21 90 5.4.4. Advertised Information Validity Times . . . . . . . . 22 91 5.4.5. Processing and Forwarding Validity Times . . . . . . 22 92 5.4.6. Jitter . . . . . . . . . . . . . . . . . . . . . . . 23 93 5.4.7. Hop Limit . . . . . . . . . . . . . . . . . . . . . . 23 94 5.4.8. Willingness . . . . . . . . . . . . . . . . . . . . . 24 95 5.5. Parameter Change Constraints . . . . . . . . . . . . . . 25 96 5.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 27 97 5.6.1. Link Metric Constants . . . . . . . . . . . . . . . . 27 98 5.6.2. Willingness Constants . . . . . . . . . . . . . . . . 27 99 6. Link Metric Values . . . . . . . . . . . . . . . . . . . . . 27 100 6.1. Link Metric Representation . . . . . . . . . . . . . . . 27 101 6.2. Link Metric Compressed Form . . . . . . . . . . . . . . . 28 102 7. Local Information Base . . . . . . . . . . . . . . . . . . . 28 103 7.1. Originator Set . . . . . . . . . . . . . . . . . . . . . 29 104 7.2. Local Attached Network Set . . . . . . . . . . . . . . . 29 105 8. Interface Information Base . . . . . . . . . . . . . . . . . 30 106 8.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . 30 107 8.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 31 108 9. Neighbor Information Base . . . . . . . . . . . . . . . . . . 31 109 10. Topology Information Base . . . . . . . . . . . . . . . . . . 33 110 10.1. Advertising Remote Router Set . . . . . . . . . . . . . . 33 111 10.2. Router Topology Set . . . . . . . . . . . . . . . . . . . 34 112 10.3. Routable Address Topology Set . . . . . . . . . . . . . . 34 113 10.4. Attached Network Set . . . . . . . . . . . . . . . . . . 35 114 10.5. Routing Set . . . . . . . . . . . . . . . . . . . . . . . 36 115 11. Received Message Information Base . . . . . . . . . . . . . . 36 116 11.1. Received Set . . . . . . . . . . . . . . . . . . . . . . 37 117 11.2. Processed Set . . . . . . . . . . . . . . . . . . . . . . 37 118 11.3. Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 37 119 12. Information Base Properties . . . . . . . . . . . . . . . . . 38 120 12.1. Corresponding Protocol Tuples . . . . . . . . . . . . . . 38 121 12.2. Address Ownership . . . . . . . . . . . . . . . . . . . . 39 122 13. Packets and Messages . . . . . . . . . . . . . . . . . . . . 40 123 13.1. Messages . . . . . . . . . . . . . . . . . . . . . . . . 40 124 13.2. Packets . . . . . . . . . . . . . . . . . . . . . . . . . 40 125 13.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . 41 126 13.3.1. Message TLVs . . . . . . . . . . . . . . . . . . . . 41 127 13.3.2. Address Block TLVs . . . . . . . . . . . . . . . . . 41 128 14. Message Processing and Forwarding . . . . . . . . . . . . . . 43 129 14.1. Actions when Receiving a Message . . . . . . . . . . . . 44 130 14.2. Message Considered for Processing . . . . . . . . . . . . 45 131 14.3. Message Considered for Forwarding . . . . . . . . . . . . 46 132 15. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . . 47 133 15.1. HELLO Message Generation . . . . . . . . . . . . . . . . 48 134 15.2. HELLO Message Transmission . . . . . . . . . . . . . . . 50 135 15.3. HELLO Message Processing . . . . . . . . . . . . . . . . 50 136 15.3.1. HELLO Message Discarding . . . . . . . . . . . . . . 50 137 15.3.2. HELLO Message Usage . . . . . . . . . . . . . . . . . 51 138 16. TC Messages . . . . . . . . . . . . . . . . . . . . . . . . . 54 139 16.1. TC Message Generation . . . . . . . . . . . . . . . . . . 54 140 16.2. TC Message Transmission . . . . . . . . . . . . . . . . . 56 141 16.3. TC Message Processing . . . . . . . . . . . . . . . . . . 57 142 16.3.1. TC Message Discarding . . . . . . . . . . . . . . . . 57 143 16.3.2. TC Message Processing Definitions . . . . . . . . . . 59 144 16.3.3. Initial TC Message Processing . . . . . . . . . . . . 59 145 16.3.4. Completing TC Message Processing . . . . . . . . . . 63 146 17. Information Base Changes . . . . . . . . . . . . . . . . . . 64 147 17.1. Originator Address Changes . . . . . . . . . . . . . . . 64 148 17.2. Link State Changes . . . . . . . . . . . . . . . . . . . 64 149 17.3. Neighbor State Changes . . . . . . . . . . . . . . . . . 65 150 17.4. Advertised Neighbor Changes . . . . . . . . . . . . . . . 65 151 17.5. Advertising Remote Router Tuple Expires . . . . . . . . . 66 152 17.6. Neighborhood Changes and MPR Updates . . . . . . . . . . 66 153 17.7. Routing Set Updates . . . . . . . . . . . . . . . . . . . 68 154 18. Selecting MPRs . . . . . . . . . . . . . . . . . . . . . . . 69 155 18.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 69 156 18.2. Neighbor Graph . . . . . . . . . . . . . . . . . . . . . 70 157 18.3. MPR Properties . . . . . . . . . . . . . . . . . . . . . 71 158 18.4. Flooding MPRs . . . . . . . . . . . . . . . . . . . . . . 72 159 18.5. Routing MPRs . . . . . . . . . . . . . . . . . . . . . . 74 160 18.6. Calculating MPRs . . . . . . . . . . . . . . . . . . . . 75 161 19. Routing Set Calculation . . . . . . . . . . . . . . . . . . . 75 162 19.1. Network Topology Graph . . . . . . . . . . . . . . . . . 76 163 19.2. Populating the Routing Set . . . . . . . . . . . . . . . 78 164 20. Proposed Values for Parameters . . . . . . . . . . . . . . . 79 165 20.1. Local History Time Parameters . . . . . . . . . . . . . . 79 166 20.2. Message Interval Parameters . . . . . . . . . . . . . . . 79 167 20.3. Advertised Information Validity Time Parameters . . . . . 79 168 20.4. Received Message Validity Time Parameters . . . . . . . . 79 169 20.5. Jitter Time Parameters . . . . . . . . . . . . . . . . . 80 170 20.6. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 80 171 20.7. Willingness Parameter . . . . . . . . . . . . . . . . . . 80 172 21. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . 80 173 22. Extensions . . . . . . . . . . . . . . . . . . . . . . . . . 81 174 23. Security Considerations . . . . . . . . . . . . . . . . . . . 81 175 23.1. Security Architecture . . . . . . . . . . . . . . . . . . 82 176 23.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 82 177 23.3. Confidentiality . . . . . . . . . . . . . . . . . . . . . 84 178 23.4. Interaction with External Routing Domains . . . . . . . . 84 179 24. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 85 180 24.1. Expert Review: Evaluation Guidelines . . . . . . . . . . 85 181 24.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 85 182 24.3. Message-Type-Specific TLV Type Registries . . . . . . . . 85 183 24.4. Message TLV Types . . . . . . . . . . . . . . . . . . . . 86 184 24.5. Address Block TLV Types . . . . . . . . . . . . . . . . . 88 185 24.6. NBR_ADDR_TYPE and MPR Values . . . . . . . . . . . . . . 90 186 25. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 91 187 26. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 91 188 27. References . . . . . . . . . . . . . . . . . . . . . . . . . 92 189 27.1. Normative References . . . . . . . . . . . . . . . . . . 92 190 27.2. Informative References . . . . . . . . . . . . . . . . . 92 191 Appendix A. Example Algorithm for Calculating MPRs . . . . . . . 93 192 A.1. Additional Notation . . . . . . . . . . . . . . . . . . . 93 193 A.2. MPR Selection Algorithm . . . . . . . . . . . . . . . . . 93 194 Appendix B. Example Algorithm for Calculating the Routing Set . 94 195 B.1. Local Interfaces and Neighbors . . . . . . . . . . . . . 94 196 B.2. Add Neighbor Routers . . . . . . . . . . . . . . . . . . 95 197 B.3. Add Remote Routers . . . . . . . . . . . . . . . . . . . 96 198 B.4. Add Neighbor Addresses . . . . . . . . . . . . . . . . . 97 199 B.5. Add Remote Routable Addresses . . . . . . . . . . . . . . 98 200 B.6. Add Attached Networks . . . . . . . . . . . . . . . . . . 98 201 B.7. Add 2-Hop Neighbors . . . . . . . . . . . . . . . . . . . 99 202 Appendix C. TC Message Example . . . . . . . . . . . . . . . . . 100 203 Appendix D. Constraints . . . . . . . . . . . . . . . . . . . . 102 204 Appendix E. Flow and Congestion Control . . . . . . . . . . . . 107 206 1. Introduction 208 The Optimized Link State Routing protocol version 2 (OLSRv2) is the 209 successor to OLSR (version 1) as published in [RFC3626]. Compared to 210 [RFC3626], OLSRv2 retains the same basic mechanisms and algorithms, 211 enhanced by the ability to use a link metric other than hop count in 212 the selection of shortest routes. OLSRv2 also uses a more flexible 213 and efficient signaling framework, and includes some simplification 214 of the messages being exchanged. 216 OLSRv2 is developed for mobile ad hoc networks (MANETs). It operates 217 as a table driven, proactive protocol, i.e., it exchanges topology 218 information with other routers in the network regularly. OLSRv2 is 219 an optimization of the classic link state routing protocol. Its key 220 concept is that of MultiPoint Relays (MPRs). Each router selects two 221 sets of MPRs, each being a set of its neighbor routers that "cover" 222 all of its symmetrically connected 2-hop neighbor routers. These two 223 sets are of "flooding MPRs" and "routing MPRs", and are used to 224 achieve flooding reduction and topology reduction, respectively. 226 Flooding reduction is achieved by control traffic being flooded 227 through the network using hop by hop forwarding, but with a router 228 only needing to forward control traffic that is first received 229 directly from one of the routers that have selected it as a flooding 230 MPR (its "flooding MPR selectors"). This mechanism, denoted "MPR 231 flooding", provides an efficient mechanism for information 232 distribution within the MANET by reducing the number of transmissions 233 required [MPR]. 235 Topology reduction is achieved by assigning a special responsibility 236 to routers selected as routing MPRs when declaring link state 237 information. A sufficient requirement for OLSRv2 to provide shortest 238 routes to all destinations is that routers declare link state 239 information for their routing MPR selectors, if any. Routers that 240 are not selected as routing MPRs need not send any link state 241 information. Based on this reduced link state information, routing 242 MPRs are used as intermediate routers in multi-hop routes. 244 Thus the use of MPRs allows reduction of the number and the size of 245 link state messages, and in the amount of link state information 246 maintained in each router. When possible (in particular if using a 247 hop count metric) the same routers may be picked as both flooding 248 MPRs and routing MPRs. 250 A router selects both routing and flooding MPRs from among its one 251 hop neighbors connected by "symmetric", i.e., bidirectional, links. 252 Therefore, selecting routes through routing MPRs avoids the problems 253 associated with data packet transfer over unidirectional links (e.g., 254 the problem of not getting link layer acknowledgments at each hop, 255 for link layers employing this technique). 257 OLSRv2 uses and extends the MANET NeighborHood Discovery Protocol 258 (NHDP) defined in [RFC6130] and also uses the Generalized MANET 259 Packet/Message Format [RFC5444], the TLVs specified in [RFC5497] and, 260 optionally, message jitter as specified in [RFC5148]. These four 261 other protocols and specifications were all originally created as 262 part of OLSRv2, but have been specified separately for wider use. 264 OLSRv2 makes no assumptions about the underlying link layer. OLSRv2, 265 through its use of [RFC6130], may use link layer information and 266 notifications when available and applicable. In addition, OLSRv2 267 uses link metrics that may be derived from link layer or any other 268 information. OLSRv2 does not specify the physical meaning of link 269 metrics, but specifies a means by which new types of link metrics may 270 be specified in the future, but used by OLSRv2 without modification. 272 OLSRv2, as OLSR [RFC3626], inherits its concept of forwarding and 273 relaying from HIPERLAN (a MAC layer protocol) which is standardized 274 by ETSI [HIPERLAN], [HIPERLAN2]. This document does not obsolete 275 [RFC3626] which is left in place for further experimentation. 277 2. Terminology 279 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 280 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 281 "OPTIONAL" in this document are to be interpreted as described in 282 [RFC2119]. 284 All terms introduced in [RFC5444], including "packet", "Packet 285 Header", "message", "Message Header", "Message Body", "Message Type", 286 "message sequence number", "hop limit", "hop count", "Address Block", 287 "TLV Block", "TLV", "Message TLV", "Address Block TLV", "type" (of 288 TLV), "type extension" (of TLV), "value" (of TLV), "address", 289 "address prefix", and "address object" are to be interpreted as 290 described there. 292 All terms introduced in [RFC6130], including "interface", "MANET 293 interface", "network address", "link", "symmetric link", "symmetric 294 1-hop neighbor", "symmetric 2-hop neighbor", "symmetric 1-hop 295 neighborhood" "constant", "interface parameter", "router parameter", 296 "Information Base", and "HELLO message" are to be interpreted as 297 described there. 299 Additionally, this specification uses the following terminology: 301 Router: 302 A MANET router which implements this protocol. 304 OLSRv2 interface: 305 A MANET interface running this protocol. A router running this 306 protocol MUST have at least one OLSRv2 interface. 308 Routable address: 309 A network address which may be used as the destination of a data 310 packet. A router MUST be able to distinguish a routable address 311 from a non-routable address by direct inspection of the network 312 address, based on global scope address allocations by IANA and/or 313 administrative configuration. Broadcast and multicast addresses, 314 and addresses which are limited in scope to less than the entire 315 MANET, MUST NOT be considered as routable addresses. Anycast 316 addresses may be considered as routable addresses. 318 Originator address: 319 An address which is unique (within the MANET) to a router. A 320 router MUST select an originator address; it MAY choose one of its 321 interface addresses as its originator address; it MAY select 322 either a routable or non-routable address. A broadcast, multicast 323 or anycast address MUST NOT be chosen as an originator address. 324 If the router selects a routable address then this MUST be one 325 which the router will accept as destination. An originator 326 address MUST NOT have a prefix length, except for when included in 327 an Address Block where it MAY be associated with a prefix of 328 maximum prefix length (e.g., if the originator address is an IPv6 329 address, it MUST have either no prefix length, or have a prefix 330 length of 128). 332 Message originator address: 333 The originator address of the router which created a message, as 334 deduced from that message by its recipient. For all messages used 335 in this specification, including HELLO messages defined in 336 [RFC6130], the recipient MUST be able to deduce an originator 337 address. The message originator address will usually be included 338 in the message as its element as defined in 339 [RFC5444]. However, an exceptional case, which does not add a 340 element to a HELLO message, may be used by a 341 router that only has a single address. 343 Willingness: 344 A numerical value between WILL_NEVER and WILL_ALWAYS (both 345 inclusive), that represents the router's willingness to be 346 selected as an MPR. A router has separate willingness values to 347 be a flooding MPR and a routing MPR. 349 Willing symmetric 1-hop neighbor: 350 A symmetric 1-hop neighbor that has willingness not equal to 351 WILL_NEVER. 353 Multipoint relay (MPR): 354 A router, X, is an MPR for a router, Y, if router Y has indicated 355 its selection of router X as an MPR in a recent HELLO message. 356 Router X may be a flooding MPR for Y if it is indicated to 357 participate in the flooding process of messages received from 358 router Y, or it may be a routing MPR for Y, if it is indicated to 359 declare link-state information for the link from X to Y. It may 360 also be both at the same time. 362 MPR selector: 363 A router, Y, is a flooding/routing MPR selector of router X if 364 router Y has selected router X as a flooding/routing MPR. 366 MPR flooding: 367 The optimized MANET-wide information distribution mechanism, 368 employed by this protocol, in which a message is relayed by only a 369 reduced subset of the routers in the network. MPR flooding is the 370 mechanism by which flooding reduction is achieved. 372 This specification employs the same notational conventions as in 373 [RFC5444] and [RFC6130]. 375 3. Applicability Statement 377 This protocol: 379 o Is a proactive routing protocol for mobile ad hoc networks 380 (MANETs) [RFC2501]. 382 o Is designed to work in networks with a dynamic topology, and in 383 which messages may be lost, such as due to collisions over 384 wireless media. 386 o Supports routers that each have one or more participating OLSRv2 387 interfaces, which will consist of some or all of its MANET 388 interfaces using [RFC6130]. The set of a router's OLSRv2 389 interfaces, and the sets of its other MANET and non-MANET 390 interfaces, may change over time. Each interface may have one or 391 more network addresses (which may have prefix lengths), and these 392 may also be dynamically changing. 394 o Enables hop-by-hop routing, i.e., each router can use its local 395 information provided by this protocol to route packets. 397 o Continuously maintains routes to all destinations in the network, 398 i.e., routes are instantly available and data traffic is subject 399 to no delays due to route discovery. Consequently, no data 400 traffic buffering is required. 402 o Supports routers that have non-OLSRv2 interfaces that may be local 403 to a router or that can serve as gateways towards other networks. 405 o Enables the use of bidirectional additive link metrics to use 406 shortest distance routes (i.e., routes with smallest total of link 407 metrics). Incoming link metric values are to be determined by a 408 process outside this specification. 410 o Is optimized for large and dense networks; the larger and more 411 dense a network, the more optimization can be achieved by using 412 MPRs, compared to the classic link state algorithm [MPR]. 414 o Uses [RFC5444] as described in its "Intended Usage" appendix and 415 by [RFC5498]. 417 o Allows "external" and "internal" extensibility (adding new message 418 types and adding information to existing messages) as enabled by 419 [RFC5444]. 421 o Is designed to work in a completely distributed manner, and does 422 not depend on any central entity. 424 4. Protocol Overview and Functioning 426 The objectives of this protocol are for each router to: 428 o Identify all destinations in the network. 430 o Identify a sufficient subset of links in the network, in order 431 that shortest routes can be calculated to all available 432 destinations. 434 o Provide a Routing Set, containing these shortest routes from this 435 router to all destinations (routable addresses and local links). 437 4.1. Overview 439 These objectives are achieved, for each router, by: 441 o Using [RFC6130] to identify symmetric 1-hop neighbors and 442 symmetric 2-hop neighbors. 444 o Reporting its participation in OLSRv2, and its willingness to be a 445 flooding MPR and to be a routing MPR, by extending the HELLO 446 messages defined in [RFC6130], by the addition of an MPR_WILLING 447 Message TLV. The router's "flooding willingness" indicates how 448 willing it is to participate in MPR flooding. The router's 449 "routing willingness" indicates how willing it is to be an 450 intermediate router for routing. Note that a router is still able 451 to be a routing source or destination, even if unwilling to 452 perform either function. 454 o Extending the HELLO messages defined in [RFC6130] to allow the 455 addition of directional link metrics to advertised links with 456 other routers participating in OLSRv2, and to indicate which link 457 metric type is being used by those routers. Both incoming and 458 outgoing link metrics may be reported, the former determined by 459 the advertising router. 461 o Selecting flooding MPRs and routing MPRs from among its willing 462 symmetric 1-hop neighbors such that, for each set of MPRs, all 463 symmetric 2-hop neighbors are reachable either directly or via at 464 least one selected MPR, using a path of appropriate minimum total 465 metric for at least routing MPR selection. An analysis and 466 examples of MPR selection algorithms are given in [MPR]; a 467 suggested algorithm, appropriately adapted for each set of MPRs, 468 is included in Appendix A of this specification. Note that it is 469 not necessary for routers to use the same algorithm in order to 470 interoperate in the same MANET, but each such algorithm must have 471 the appropriate properties, described in Section 18. 473 o Signaling its flooding MPR and routing MPR selections, by 474 extending the HELLO messages defined in [RFC6130] to report this 475 information by the addition of MPR Address Block TLV(s) associated 476 with the appropriate network addresses. 478 o Extracting its flooding MPR selectors and routing MPR selectors 479 from received HELLO messages, using the included MPR Address Block 480 TLV(s). 482 o Defining a TC (Topology Control) Message Type using the message 483 format specified in [RFC5444]. TC messages are used to 484 periodically signal links between routing MPR selectors and itself 485 throughout the MANET. This signaling includes suitable 486 directional neighbor metrics (the best link metric in that 487 direction between those routers). 489 o Allowing its TC messages, as well as HELLO messages, to be 490 included in packets specified in [RFC5444], using the "manet" IP 491 protocol or UDP port as specified in [RFC5498]. 493 o Diffusing TC messages by using a flooding reduction mechanism, 494 denoted "MPR flooding"; only the flooding MPRs of a router will 495 retransmit messages received from (i.e., originated or last 496 relayed by) that router. 498 Note that the indicated extensions to [RFC6130] are of forms 499 permitted by that specification. 501 This specification defines: 503 o The requirement to use [RFC6130], its parameters, constants, HELLO 504 messages, and Information Bases, each as extended in this 505 specification. 507 o Two new Information Bases: the Topology Information Base and the 508 Received Message Information Base. 510 o TC messages, which are used for MANET wide signaling (using MPR 511 flooding) of selected topology (link state) information. 513 o A requirement for each router to have an originator address to be 514 included in, or deducible from, HELLO messages and TC messages. 516 o The specification of new Message TLVs and Address Block TLVs that 517 are used in HELLO messages and TC messages, including for 518 reporting neighbor status, MPR selection, external gateways, link 519 metrics, willingness to be an MPR, and content sequence numbers. 520 Note that the generation of (incoming) link metric values is to be 521 undertaken by a process outside this specification; this 522 specification concerns only the distribution and use of those 523 metrics. 525 o The generation of TC messages from the appropriate information in 526 the Information Bases. 528 o The updating of the Topology Information Base according to 529 received TC messages. 531 o The MPR flooding mechanism, including the inclusion of message 532 originator address and sequence number to manage duplicate 533 messages, using information recorded in the Received Message 534 Information Base. 536 o The response to other events, such as the expiration of 537 information in the Information Bases. 539 This protocol inherits the stability of a link state algorithm, and 540 has the advantage of having routes immediately available when needed, 541 due to its proactive nature. 543 This protocol only interacts with IP through routing table 544 management, and the use of the sending IP address for IP datagrams 545 containing messages used by this specification. 547 4.2. Routers and Interfaces 549 In order for a router to participate in a MANET using this protocol 550 it must have at least one, and possibly more, OLSRv2 interfaces. 551 Each OLSRv2 interface: 553 o Is a MANET interface, as specified in [RFC6130]. In particular it 554 must be configured with one or more network addresses; these 555 addresses must each be specific to this router, and must include 556 any address that will be used as the sending address of any IP 557 packet sent on this OLSRv2 interface. 559 o Has a number of interface parameters, adding to those specified in 560 [RFC6130]. 562 o Has an Interface Information Base, extending that specified in 563 [RFC6130]. 565 o Generates and processes HELLO messages according to [RFC6130], 566 extended as specified in Section 15. 568 In addition to a set of OLSRv2 interfaces as described above, each 569 router: 571 o May have one or more non-OLSRv2 interfaces (which may include 572 MANET interfaces and/or non-MANET interfaces) and/or local 573 attached networks for which this router can accept IP packets. 574 All routable addresses for which the router is to accept IP 575 packets must be used as an (OLSRv2 or non-OLSRv2) interface 576 network address, or as an address of a local attached network of 577 the router. 579 o Has a number of router parameters, adding to those specified in 580 [RFC6130]. 582 o Has a Local Information Base, extending that specified in 583 [RFC6130], including selection of an originator address and 584 recording any locally attached networks. 586 o Has a Neighbor Information Base, extending that specified in 587 [RFC6130] to record MPR selection and advertisement information. 589 o Has a Topology Information Base, recording information received in 590 TC messages. 592 o Has a Received Message Information Base, recording information 593 about received messages to ensure that each TC message is only 594 processed once, and forwarded at most once on each OLSRv2 595 interface, by a router. 597 o Generates, receives, and processes TC messages. 599 4.3. Information Base Overview 601 Each router maintains the Information Bases described in the 602 following sections. These are used for describing the protocol in 603 this specification. An implementation of this protocol may maintain 604 this information in the indicated form, or in any other organization 605 which offers access to this information. In particular, note that it 606 is not necessary to remove Tuples from Sets at the exact time 607 indicated, only to behave as if the Tuples were removed at that time. 609 4.3.1. Local Information Base 611 The Local Information Base is specified in [RFC6130], and contains a 612 router's local configuration. It is extended in this specification 613 to also record an originator address, and to include a router's: 615 o Originator Set, containing addresses that were recently used as 616 this router's originator address, and is used, together with the 617 router's current originator address, to enable a router to 618 recognize and discard control traffic which was originated by the 619 router itself. 621 o Local Attached Network Set, containing network addresses of 622 networks to which this router can act as a gateway, and advertises 623 in its TC messages. 625 4.3.2. Interface Information Bases 627 The Interface Information Base for each OLSRv2 interface is as 628 specified in [RFC6130], extended to also record, in each Link Set, 629 link metric values (incoming and outgoing) and flooding MPR selector 630 information. 632 4.3.3. Neighbor Information Base 634 The Neighbor Information Base is specified in [RFC6130], and is 635 extended to also record, in the Neighbor Tuple for each neighbor: 637 o Its originator address. 639 o Neighbor metric values, these being the minimum of the link metric 640 values in the indicated direction for all symmetric 1-hop links 641 with that neighbor. 643 o Its willingness to be a flooding MPR and to be a routing MPR. 645 o Whether it has been selected by this router as a flooding MPR or 646 as a routing MPR, and whether it is a routing MPR selector of this 647 router. (Whether it is a flooding MPR selector of this neighbor 648 is recorded in the Interface Information Base.) 650 o Whether it is to be advertised in TC messages sent by this router. 652 4.3.4. Topology Information Base 654 The Topology Information Base in each router contains: 656 o An Advertising Remote Router Set, recording each remote router 657 from which TC messages have been received. This is used in order 658 to determine if a received TC message contains fresh or outdated 659 information; a received TC message is ignored in the latter case. 661 o A Router Topology Set, recording links between routers in the 662 MANET, as described by received TC messages. 664 o A Routable Address Topology Set, recording routable addresses in 665 the MANET (available as IP packet destinations) and from which 666 remote router these routable addresses can be directly reached 667 (i.e., in a single IP hop from that remote router), as reported by 668 received TC messages. 670 o An Attached Network Set, recording networks to which a remote 671 router has advertised that it may act as a gateway. These 672 networks may be reached in one or more IP hops from that remote 673 router. 675 o A Routing Set, recording routes from this router to all available 676 destinations. The IP routing table is to be updated using this 677 Routing Set. (A router may choose to use any or all destination 678 network addresses in the Routing Set to update the IP routing 679 table, this selection is outside the scope of this specification.) 681 The purpose of the Topology Information Base is to record information 682 used, in addition to that in the Local Information Base, the 683 Interface Information Bases and the Neighbor Information Base, to 684 construct the Routing Set (which is also included in the Topology 685 Information Base). 687 This specification describes the calculation of the Routing Set based 688 on a Topology Graph constructed in two phases. First, a "backbone" 689 graph representing the routers in the MANET, and the connectivity 690 between them, is constructed from the Local Information Base, the 691 Neighbor Information Base and the Router Topology Set. Second, this 692 graph is "decorated" with additional destination network addresses 693 using the Local Information Base, the Routable Address Topology Set 694 and the Attached Network Set. 696 The Topology Graph does not need to be recorded in the Topology 697 Information Base, it can either be constructed as required when the 698 Routing Set is to be changed, or need not be explicitly constructed 699 (as illustrated in Appendix B). An implementation may however 700 construct and retain the Topology Graph if preferred. 702 4.3.5. Received Message Information Base 704 The Received Message Information Base in each router contains: 706 o A Received Set for each OLSRv2 interface, describing TC messages 707 received by this router on that OLSRv2 interface. 709 o A Processed Set, describing TC messages processed by this router. 711 o A Forwarded Set, describing TC messages forwarded by this router. 713 The Received Message Information Base serves the MPR flooding 714 mechanism by ensuring that received messages are forwarded at most 715 once by a router, and also ensures that received messages are 716 processed exactly once by a router. The Received Message Information 717 Base may also record information about other Message Types that use 718 the MPR flooding mechanism. 720 4.4. Signaling Overview 722 This protocol generates and processes HELLO messages according to 723 [RFC6130]. HELLO messages transmitted on OLSRv2 interfaces are 724 extended according to Section 15 of this specification to include an 725 originator address, link metrics, and MPR selection information. 727 This specification defines a single Message Type, the TC message. TC 728 messages are sent by their originating router proactively, at a 729 regular interval, on all OLSRv2 interfaces. This interval may be 730 fixed, or may be dynamic, for example it may be backed off due to 731 congestion or network stability. TC messages may also be sent as a 732 response to a change in the router itself, or its advertised 733 symmetric 1-hop neighborhood, for example on first being selected as 734 a routing MPR. 736 Because TC messages are sent periodically, this protocol is tolerant 737 of unreliable transmissions of TC messages. Message losses may occur 738 more frequently in wireless networks due to collisions or other 739 transmission problems. This protocol may use "jitter", randomized 740 adjustments to message transmission times, to reduce the incidence of 741 collisions, as specified in [RFC5148]. 743 This protocol is tolerant of out of sequence delivery of TC messages 744 due to in transit message reordering. Each router maintains an 745 Advertised Neighbor Sequence Number (ANSN) that is incremented when 746 its recorded neighbor information that is to be included in its TC 747 messages changes. This ANSN is included in the router's TC messages. 748 The recipient of a TC message can use this included ANSN to identify 749 which of the information it has received is most recent, even if 750 messages have been reordered while in transit. Only the most recent 751 information received is used, older information received later is 752 discarded. 754 TC messages may be "complete" or "incomplete". A complete TC message 755 advertises all of the originating router's routing MPR selectors, it 756 may also advertise other symmetric 1-hop neighbors. Complete TC 757 messages are generated periodically (and also, optionally, in 758 response to symmetric 1-hop neighborhood changes). Incomplete TC 759 messages may be used to report additions to advertised information, 760 without repeating unchanged information. 762 TC messages, and HELLO messages as extended by this specification, 763 define (by inclusion, or by deduction when having a single address) 764 an originator address for the router that created the message. A TC 765 message reports both the originator addresses and routable addresses 766 of its advertised neighbors, distinguishing the two using an Address 767 Block TLV (an address may be both routable and an originator 768 address). TC messages also report the originator's locally attached 769 networks. 771 TC messages are MPR flooded throughout the MANET. A router 772 retransmits a TC message received on an OLSRv2 interface if and only 773 if the message did not originate at this router and has not been 774 previously forwarded by this router, this is the first time the 775 message has been received on this OLSRv2 interface, and the message 776 is received from (i.e., originated from or was last relayed by) one 777 of this router's flooding MPR selectors. 779 Some TC messages may be MPR flooded over only part of the network, 780 e.g., allowing a router to ensure that nearer routers are kept more 781 up to date than distant routers, such as is used in Fisheye State 782 Routing [FSR] and Fuzzy Sighted Link State routing [FSLS]. This is 783 enabled using [RFC5497]. 785 TC messages include outgoing neighbor metrics that will be used in 786 the selection of routes. 788 4.5. Link Metrics 790 OLSRv1 [RFC3626] created minimum hop routes to destinations. However 791 in many, if not most, circumstances, better routes (in terms of 792 quality of service for end users) can be created by use of link 793 metrics. 795 OLSRv2, as defined in this specification, supports metric-based 796 routing, i.e., it allows links to each have a chosen metric. Link 797 metrics as defined in OLSRv2 are additive, and the routes that are to 798 be created are those with the minimum sum of the link metrics along 799 that route. 801 Link metrics are defined to be directional; the link metric from one 802 router to another may be different from that on the reverse link. 803 The link metric is assessed at the receiver, as on a (typically) 804 wireless link, that is the better informed as to link information. 805 Both incoming and outgoing link information is used by OLSRv2, the 806 distinctions in this specification must be clearly followed. 808 This specification also defines both incoming and outgoing neighbor 809 metrics for each symmetric 1-hop neighbor, these being the minimum 810 value of the link metrics in the same direction for all symmetric 811 links with that neighbor. Note that this means that all neighbor 812 metric values are link metric values and that specification of, for 813 example, link metric value encoding also includes encoding of 814 neighbor metric values. 816 This specification does not define the nature of the link metric. 817 However, this specification allows, through use of the type extension 818 of a defined Address Block TLV, for link metrics with specific 819 meanings to be defined and either allocated by IANA or privately 820 used. Each HELLO or TC message carrying link (or neighbor) metrics 821 thus indicates which link metric information it is carrying, allowing 822 routers to determine if they can interoperate. If link metrics 823 require additional signaling to determine their values, whether in 824 HELLO messages or otherwise, then this is permitted but is outside 825 the scope of this specification. 827 Careful consideration should be given to how to use link metrics. In 828 particular it is advisable to not simply default to use of all links 829 with equal metrics (i.e., hop count) for routing without careful 830 consideration of whether that is appropriate or not. 832 4.6. Routing Set Use 834 The purpose of the Routing Set is to determine and record routes 835 (local interface network address and next hop interface network 836 address) to all possible routable addresses advertised by this 837 protocol, as well as of all destinations that are local, i.e., within 838 one hop, to the router (whether using routable addresses or not). 839 Only symmetric links are used in such routes. 841 It is intended that the Routing Set can be used for IP packet 842 routing, by using its contents to update the IP routing table. That 843 update, and whether any Routing Tuples are not used in the IP routing 844 table, is outside the scope of this specification. 846 The signaling in this specification has been designed so that a 847 "backbone" Topology Graph of routers, each identified by its 848 originator address, with at most one direct connection between any 849 pair of routers, can be constructed (from the Neighbor Set and the 850 Router Topology Set) using a suitable minimum path length algorithm. 851 This Topology Graph can then have other network addresses (routable, 852 or of symmetric 1-hop neighbors) added to it (using the Interface 853 Information Bases, the Routable Address Topology Set and the Attached 854 Network Set). 856 5. Protocol Parameters and Constants 858 The parameters and constants used in this specification are those 859 defined in [RFC6130] plus those defined in this section. The 860 separation in [RFC6130] into interface parameters, router parameters 861 and constants is also used in this specification. 863 As for the parameters in [RFC6130], parameters defined in this 864 specification MAY be changed dynamically by a router, and need not be 865 the same on different routers, even in the same MANET, or, for 866 interface parameters, on different interfaces of the same router. 868 5.1. Protocol and Port Numbers 870 This protocol specifies TC messages, which are included in packets as 871 defined by [RFC5444]. These packets MAY be sent either using the 872 "manet" protocol number or the "manet" UDP well-known port number, as 873 specified in [RFC5498]. 875 TC messages and HELLO messages [RFC6130] MUST, in a given MANET, both 876 be using the same of either of IP or UDP, in order that it is 877 possible to combine messages of both protocols into the same 878 [RFC5444] packet for transmission. 880 5.2. Multicast Address 882 This protocol specifies TC messages, which are included in packets as 883 defined by [RFC5444]. These packets MAY be transmitted using the 884 Link-Local multicast address "LL-MANET-Routers", as specified in 885 [RFC5498]. 887 5.3. Interface Parameters 889 A single additional interface parameter is specified for OLSRv2 890 interfaces only. 892 5.3.1. Received Message Validity Time 894 The following parameter manages the validity time of recorded 895 received message information: 897 RX_HOLD_TIME: 898 The period after receipt of a message by the appropriate OLSRv2 899 interface of this router for which that information is recorded, 900 in order that the message is recognized as having been previously 901 received on this OLSRv2 interface. 903 The following constraints apply to this parameter: 905 o RX_HOLD_TIME > 0 907 o RX_HOLD_TIME SHOULD be greater than the maximum difference in time 908 that a message may take to traverse the MANET, taking into account 909 any message forwarding jitter as well as propagation, queuing, and 910 processing delays. 912 5.4. Router Parameters 914 The following router parameters are specified for routers. 916 5.4.1. Local History Times 918 The following router parameter manages the time for which local 919 information is retained: 921 O_HOLD_TIME: 922 The time for which a recently used and replaced originator address 923 is used to recognize the router's own messages. 925 The following constraint applies to this parameter: 927 o O_HOLD_TIME > 0 929 5.4.2. Link Metric Parameters 931 All routes found using this specification use a single link metric 932 type that is specified by the router parameter LINK_METRIC_TYPE, 933 which may take any value from 0 to 255, both inclusive. 935 5.4.3. Message Intervals 937 The following parameters regulate TC message transmissions by a 938 router. TC messages are usually sent periodically, but MAY also be 939 sent in response to changes in the router's Neighbor Set and/or Local 940 Attached Network Set. In a highly dynamic network, and with a larger 941 value of the parameter TC_INTERVAL and a smaller value of the 942 parameter TC_MIN_INTERVAL, TC messages MAY be transmitted more often 943 in response to changes than periodically. However, because a router 944 has no knowledge of, for example, routers remote to it (i.e., beyond 945 two hops away) joining the network, TC messages MUST NOT be sent 946 purely responsively. 948 TC_INTERVAL: 949 The maximum time between the transmission of two successive TC 950 messages by this router. When no TC messages are sent in response 951 to local network changes (by design, or because the local network 952 is not changing) then TC messages MUST be sent at a regular 953 interval TC_INTERVAL, possibly modified by jitter as specified in 954 [RFC5148]. 956 TC_MIN_INTERVAL: 957 The minimum interval between transmission of two successive TC 958 messages by this router. (This minimum interval MAY be modified 959 by jitter, as specified in [RFC5148].) 961 The following constraints apply to these parameters: 963 o TC_INTERVAL > 0 965 o TC_MIN_INTERVAL >= 0 967 o TC_INTERVAL >= TC_MIN_INTERVAL 968 o If TLVs with Type = INTERVAL_TIME, as defined in [RFC5497], are 969 included in TC messages, then TC_INTERVAL MUST be representable as 970 described in [RFC5497]. 972 5.4.4. Advertised Information Validity Times 974 The following parameters manage the validity time of information 975 advertised in TC messages: 977 T_HOLD_TIME: 978 Used as the minimum value in the TLV with Type = VALIDITY_TIME 979 included in all TC messages sent by this router. If a single 980 value of parameter TC_HOP_LIMIT (see Section 5.4.7) is used then 981 this will be the only value in that TLV. 983 A_HOLD_TIME: 984 The period during which TC messages are sent after they no longer 985 have any advertised information to report, but are sent in order 986 to accelerate outdated information removal by other routers. 988 The following constraints apply to these parameters: 990 o T_HOLD_TIME > 0 992 o A_HOLD_TIME >= 0 994 o T_HOLD_TIME >= TC_INTERVAL 996 o If TC messages can be lost, then both T_HOLD_TIME and A_HOLD_TIME 997 SHOULD be significantly greater than TC_INTERVAL; a value >= 3 x 998 TC_INTERVAL is RECOMMENDED. 1000 o T_HOLD_TIME MUST be representable as described in [RFC5497]. 1002 5.4.5. Processing and Forwarding Validity Times 1004 The following parameters manage the processing and forwarding 1005 validity time of recorded message information: 1007 P_HOLD_TIME: 1008 The period after receipt of a message that is processed by this 1009 router for which that information is recorded, in order that the 1010 message is not processed again if received again. 1012 F_HOLD_TIME: 1013 The period after receipt of a message that is forwarded by this 1014 router for which that information is recorded, in order that the 1015 message is not forwarded again if received again. 1017 The following constraints apply to these parameters: 1019 o P_HOLD_TIME > 0 1021 o F_HOLD_TIME > 0 1023 o Both of these parameters SHOULD be greater than the maximum 1024 difference in time that a message may take to traverse the MANET, 1025 taking into account any message forwarding jitter as well as 1026 propagation, queuing, and processing delays. 1028 5.4.6. Jitter 1030 If jitter, as defined in [RFC5148], is used then the governing jitter 1031 parameters are as follows: 1033 TP_MAXJITTER: 1034 Represents the value of MAXJITTER used in [RFC5148] for 1035 periodically generated TC messages sent by this router. 1037 TT_MAXJITTER: 1038 Represents the value of MAXJITTER used in [RFC5148] for externally 1039 triggered TC messages sent by this router. 1041 F_MAXJITTER: 1042 Represents the default value of MAXJITTER used in [RFC5148] for 1043 messages forwarded by this router. However, before using 1044 F_MAXJITTER a router MAY attempt to deduce a more appropriate 1045 value of MAXJITTER, for example based on any TLVs with Type = 1046 INTERVAL_TIME or Type = VALIDITY_TIME contained in the message to 1047 be forwarded. 1049 For constraints on these parameters see [RFC5148]. 1051 5.4.7. Hop Limit 1053 The parameter TC_HOP_LIMIT is the hop limit set in each TC message. 1054 TC_HOP_LIMIT MAY be a single fixed value, or MAY be different in TC 1055 messages sent by the same router. However each other router, at any 1056 hop count distance, MUST see a regular pattern of TC messages in 1057 order that meaningful values of TLVs with Type = INTERVAL_TIME and 1058 Type = VALIDITY_TIME at each hop count distance can be included as 1059 defined in [RFC5497]. Thus the pattern of TC_HOP_LIMIT MUST be 1060 defined to have this property. For example the repeating pattern 1061 (255 4 4) satisfies this property (having period TC_INTERVAL at hop 1062 counts up to 4, inclusive, and 3 x TC_INTERVAL at hop counts greater 1063 than 4), but the repeating pattern (255 255 4 4) does not satisfy 1064 this property because at hop counts greater than 4, message intervals 1065 are alternately TC_INTERVAL and 3 x TC_INTERVAL. 1067 The following constraints apply to this parameter: 1069 o The maximum value of TC_HOP_LIMIT >= the network diameter in hops, 1070 a value of 255 is RECOMMENDED. Note that if using a pattern of 1071 different values of TC_HOP_LIMIT as described above, then only the 1072 maximum value in the pattern is so constrained. 1074 o All values of TC_HOP_LIMIT >= 2. 1076 5.4.8. Willingness 1078 Each router has two willingness parameters: WILL_FLOODING and 1079 WILL_ROUTING, each of which MUST be in the range WILL_NEVER to 1080 WILL_ALWAYS, inclusive. 1082 WILL_FLOODING represents the router's willingness to be selected as a 1083 flooding MPR and hence to participate in MPR flooding, in particular 1084 of TC messages. 1086 WILL_ROUTING represents the router's willingness to be selected as a 1087 routing MPR and hence to be an intermediate router on routes. 1089 In either case, the higher the value, the greater the router's 1090 willingness to be a flooding or routing MPR, respectively. If a 1091 router has a willingness value of WILL_NEVER (the lowest possible 1092 value) it does not perform the corresponding task. A MANET using 1093 this protocol with too many routers having either willingness value 1094 equal to WILL_NEVER will not function; it MUST be ensured, by 1095 administrative or other means, that this does not happen. 1097 If a router has a willingness value equal to WILL_ALWAYS (the highest 1098 possible value) then it will always be selected as a flooding or 1099 routing MPR, respectively, by all symmetric 1-hop neighbors. 1101 In a MANET in which all routers have WILL_FLOODING = WILL_ALWAYS, 1102 flooding reduction will effectively be disabled, and flooding will 1103 perform as blind flooding. 1105 In a MANET in which all routers have WILL_ROUTING = WILL_ALWAYS, 1106 topology reduction will effectively be disabled, and all routers will 1107 advertise all of their links in TC messages. 1109 A router that has WILL_ROUTING = WILL_NEVER will not act as an 1110 intermediate router in the MANET. Such a router can, act as a 1111 source, destination or gateway to another routing domain. 1113 Different routers MAY have different values for WILL_FLOODING and/or 1114 WILL_ROUTING. 1116 The following constraints apply to these parameters: 1118 o WILL_FLOODING >= WILL_NEVER 1120 o WILL_FLOODING <= WILL_ALWAYS 1122 o WILL_ROUTING >= WILL_NEVER 1124 o WILL_ROUTING <= WILL_ALWAYS 1126 5.5. Parameter Change Constraints 1128 If protocol parameters are changed dynamically, then the constraints 1129 in this section apply. 1131 RX_HOLD_TIME 1133 * If RX_HOLD_TIME for an OLSRv2 interface changes, then the 1134 expiry time for all Received Tuples for that OLSRv2 interface 1135 MAY be changed. 1137 O_HOLD_TIME 1139 * If O_HOLD_TIME changes, then the expiry time for all Originator 1140 Tuples MAY be changed. 1142 TC_INTERVAL 1144 * If TC_INTERVAL increases, then the next TC message generated by 1145 this router MUST be generated according to the previous, 1146 shorter, TC_INTERVAL. Additional subsequent TC messages MAY be 1147 generated according to the previous, shorter, TC_INTERVAL. 1149 * If TC_INTERVAL decreases, then the following TC messages from 1150 this router MUST be generated according to the current, 1151 shorter, TC_INTERVAL. 1153 P_HOLD_TIME 1155 * If P_HOLD_TIME changes, then the expiry time for all Processed 1156 Tuples MAY be changed. 1158 F_HOLD_TIME 1160 * If F_HOLD_TIME changes, then the expiry time for all Forwarded 1161 Tuples MAY be changed. 1163 TP_MAXJITTER 1165 * If TP_MAXJITTER changes, then the periodic TC message schedule 1166 on this router MAY be changed immediately. 1168 TT_MAXJITTER 1170 * If TT_MAXJITTER changes, then externally triggered TC messages 1171 on this router MAY be rescheduled. 1173 F_MAXJITTER 1175 * If F_MAXJITTER changes, then TC messages waiting to be 1176 forwarded with a delay based on this parameter MAY be 1177 rescheduled. 1179 TC_HOP_LIMIT 1181 * If TC_HOP_LIMIT changes, and the router uses multiple values 1182 after the change, then message intervals and validity times 1183 included in TC messages MUST be respected. The simplest way to 1184 do this is to start any new repeating pattern of TC_HOP_LIMIT 1185 values with its largest value. 1187 LINK_METRIC_TYPE 1189 * If LINK_METRIC_TYPE changes, then all link metric information 1190 recorded by the router is invalid. The router MUST take the 1191 following actions, and all consequent actions described in 1192 Section 17 and [RFC6130]. 1194 + For each Link Tuple in any Link Set for an OLSRv2 interface, 1195 either update L_in_metric (the value MAXIMUM_METRIC MAY be 1196 used) or remove the Link Tuple from the Link Set. 1198 + For each Link Tuple that is not removed, set: 1200 - L_out_metric := UNKNOWN_METRIC; 1202 - L_SYM_time := expired; 1204 - L_MPR_selector := false. 1206 + Remove all Router Topology Tuples, Routable Address Topology 1207 Tuples, Attached Network Tuples and Routing Tuples from 1208 their respective Protocol Sets in the Topology Information 1209 Base. 1211 5.6. Constants 1213 The following constants are specified for routers. Unlike router 1214 parameters, constants MUST NOT change, and MUST be the same on all 1215 routers. 1217 5.6.1. Link Metric Constants 1219 The constant minimum and maximum link metric values are defined by: 1221 o MINIMUM_METRIC := 1 1223 o MAXIMUM_METRIC := 16776960 1225 The symbolic value UNKNOWN_METRIC is defined in Section 6.1. 1227 5.6.2. Willingness Constants 1229 The constant minimum, RECOMMENDED default, and maximum, willingness 1230 values are defined by: 1232 o WILL_NEVER := 0 1234 o WILL_DEFAULT := 7 1236 o WILL_ALWAYS := 15 1238 6. Link Metric Values 1240 A router records a link metric value for each direction of a link of 1241 which it has knowledge. These link metric values are used to create 1242 metrics for routes by the addition of link metric values. 1244 6.1. Link Metric Representation 1246 Link metrics are reported in messages using a compressed 1247 representation that occupies 12 bits, a 4 bit field and an 8 bit 1248 field. The compressed representation represents positive integer 1249 values with a minimum value of 1 and a maximum value that is slightly 1250 smaller than the maximum 24 bit value. Only those values that have 1251 exact representation in the compressed form are used. Route metrics 1252 are the summation of no more than 255 link metric values, and can 1253 therefore be represented using no more than 32 bits. 1255 Link and route metrics used in the Information Bases defined in this 1256 specification refer to the uncompressed values, and arithmetic 1257 involving them does likewise, and assumes full precision in the 1258 result. (How an implementation records the values is not part of 1259 this specification, as long as it behaves as if recording 1260 uncompressed values. An implementation can, for example, use 32 bit 1261 values for all link and route metrics.) 1263 In some cases a link metric value may be unknown. This is indicated 1264 in this specification by the symbolic value UNKNOWN_METRIC. An 1265 implementation may use any representation of UNKNOWN_METRIC as it is 1266 never included in messages, or used in any computation. (Possible 1267 representations are zero, or any value greater than the maximum 1268 representable metric value.) 1270 6.2. Link Metric Compressed Form 1272 The 12-bit compressed form of a link metric uses a modified form of a 1273 representation with an 8-bit mantissa (denoted a) and a 4-bit 1274 exponent (denoted b). Note that if represented as the 12 bit value 1275 256b+a then the ordering of those 12 bit values is identical to the 1276 ordering of the represented values. 1278 The value so represented is (257+a)2^b - 256, where ^ denotes 1279 exponentiation. This has a minimum value (when a = 0 and b = 0) of 1280 MINIMUM_METRIC = 1 and a maximum value (when a = 255 and b = 15) of 1281 MAXIMUM_METRIC = 2^24 - 256. 1283 An algorithm for computing a and b for the smallest representable 1284 value not less than a link metric value v such that MINIMUM_METRIC <= 1285 v <= MAXIMUM_METRIC is: 1287 1. Find the smallest integer b such that v + 256 <= 2^(b + 9). 1289 2. Set a := (v - 256(2^b - 1)) / (2^b) - 1, rounded up to the 1290 nearest integer. 1292 7. Local Information Base 1294 The Local Information Base, as defined for each router in [RFC6130], 1295 is extended by this protocol by: 1297 o Recording the router's originator address. The originator address 1298 MUST be unique to this router. It MUST NOT be used by any other 1299 router as an originator address. It MAY be included in any 1300 network address in any I_local_iface_addr_list of this router, it 1301 MUST NOT be included in any network address in any 1302 I_local_iface_addr_list of any other router. It MAY be included 1303 in, but MUST NOT be equal to, the AL_net_addr in any Local 1304 Attached Network Tuple in this or any other router. 1306 o The addition of an Originator Set, defined in Section 7.1, and a 1307 Local Attached Network Set, defined in Section 7.2. 1309 All routable addresses of the router for which it is to accept IP 1310 packets as destination MUST be included in the Local Interface Set or 1311 the Local Attached Network Set. 1313 7.1. Originator Set 1315 A router's Originator Set records addresses that were recently used 1316 as originator addresses by this router. If a router's originator 1317 address is immutable then the Originator Set is always empty and MAY 1318 be omitted. It consists of Originator Tuples: 1320 (O_orig_addr, O_time) 1322 where: 1324 O_orig_addr is a recently used originator address; note that this 1325 does not include a prefix length. 1327 O_time specifies the time at which this Tuple expires and MUST be 1328 removed. 1330 7.2. Local Attached Network Set 1332 A router's Local Attached Network Set records its local non-OLSRv2 1333 interfaces via which it can act as gateways to other networks. The 1334 Local Attached Network Set is not modified by this protocol. This 1335 protocol MAY respond to changes to the Local Attached Network Set, 1336 which MUST reflect corresponding changes in the router's status. It 1337 consists of Local Attached Network Tuples: 1339 (AL_net_addr, AL_dist, AL_metric) 1341 where: 1343 AL_net_addr is the network address of an attached network which 1344 can be reached via this router. This SHOULD be a routable 1345 address. It is constrained as described below. 1347 AL_dist is the number of hops to the network with network address 1348 AL_net_addr from this router. 1350 AL_metric is the metric of the link to the attached network with 1351 address AL_net_addr from this router. 1353 Attached networks local to this router only (i.e., not reachable 1354 except via this router) SHOULD be treated as local non-MANET 1355 interfaces, and added to the Local Interface Set, as specified in 1356 [RFC6130], rather than be added to the Local Attached Network Set. 1358 Because an attached network is not specific to the router, and may be 1359 outside the MANET, an attached network MAY also be attached to other 1360 routers. Routing to an AL_net_addr will use maximum prefix length 1361 matching; consequently an AL_net_addr MAY include, but MUST NOT equal 1362 or be included in, any network address which is of any interface of 1363 any router (i.e., is included in any I_local_iface_addr_list) or 1364 equal any router's originator address. 1366 It is not the responsibility of this protocol to maintain routes from 1367 this router to networks recorded in the Local Attached Network Set. 1369 Local Attached Neighbor Tuples are removed from the Local Attached 1370 Network Set only when the router's local attached network 1371 configuration changes, i.e., they are not subject to timer-based 1372 expiration or changes due to received messages. 1374 8. Interface Information Base 1376 An Interface Information Base, as defined in [RFC6130], is maintained 1377 for each MANET interface. The Link Set and 2-Hop Set in the 1378 Interface Information Base for an OLSRv2 interface are modified by 1379 this protocol. In some cases it may be convenient to consider these 1380 Sets as also containing these additional elements for other MANET 1381 interfaces, taking the indicated values on creation, but never being 1382 updated. 1384 8.1. Link Set 1386 The Link Set is modified by adding these additional elements to each 1387 Link Tuple: 1389 L_in_metric is the metric of the link from the OLSRv2 interface 1390 with addresses L_neighbor_iface_addr_list to this OLSRv2 1391 interface; 1393 L_out_metric is the metric of the link to the OLSRv2 interface 1394 with addresses L_neighbor_iface_addr_list from this OLSRv2 1395 interface; 1396 L_mpr_selector is a boolean flag, describing if this neighbor has 1397 selected this router as a flooding MPR, i.e., is a flooding MPR 1398 selector of this router. 1400 L_in_metric will be specified by a process that is external to this 1401 specification. Any Link Tuple with L_status = HEARD or L_status = 1402 SYMMETRIC MUST have a specified value of L_in_metric if it is to be 1403 used by this protocol. 1405 A Link Tuple created (but not updated) by [RFC6130] MUST set: 1407 o L_in_metric := UNKNOWN_METRIC; 1409 o L_out_metric := UNKNOWN_METRIC; 1411 o L_mpr_selector := false. 1413 8.2. 2-Hop Set 1415 The 2-Hop Set is modified by adding these additional elements to each 1416 2-Hop Tuple: 1418 N2_in_metric is the neighbor metric from the router with address 1419 N2_2hop_iface_addr to the router with OLSRv2 interface addresses 1420 N2_neighbor_iface_addr_list; 1422 N2_out_metric is the neighbor metric to the router with address 1423 N2_2hop_iface_addr from the router with OLSRv2 interface addresses 1424 N2_neighbor_iface_addr_list. 1426 A 2-Hop Tuple created (but not updated) by [RFC6130] MUST set: 1428 o N2_in_metric := UNKNOWN_METRIC; 1430 o N2_out_metric := UNKNOWN_METRIC. 1432 9. Neighbor Information Base 1434 A Neighbor Information Base, as defined in [RFC6130], is maintained 1435 for each router. It is modified by this protocol by adding these 1436 additional elements to each Neighbor Tuple in the Neighbor Set. In 1437 some cases it may be convenient to consider these Sets as also 1438 containing these additional elements for other MANET interfaces, 1439 taking the indicated values on creation, but never being updated. 1441 N_orig_addr is the neighbor's originator address, which may be 1442 unknown. Note that this originator address does not include a 1443 prefix length; 1444 N_in_metric is the neighbor metric of any link from this neighbor 1445 to an OLSRv2 interface of this router, i.e., the minimum of all 1446 corresponding L_in_metric with L_status = SYMMETRIC and 1447 L_in_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no such 1448 Link Tuples; 1450 N_out_metric is the neighbor metric of any link from an OLSRv2 1451 interface of this router to this neighbor, i.e., the minimum of 1452 all corresponding L_out_metric with L_status = SYMMETRIC and 1453 L_out_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no 1454 such Link Tuples; 1456 N_will_flooding is the neighbor's willingness to be selected as a 1457 flooding MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1458 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1459 information is received from this neighbor; 1461 N_will_routing is the neighbor's willingness to be selected as a 1462 routing MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1463 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1464 information is received from this neighbor; 1466 N_flooding_mpr is a boolean flag, describing if this neighbor is 1467 selected as a flooding MPR by this router; 1469 N_routing_mpr is a boolean flag, describing if this neighbor is 1470 selected as a routing MPR by this router; 1472 N_mpr_selector is a boolean flag, describing if this neighbor has 1473 selected this router as a routing MPR, i.e., is a routing MPR 1474 selector of this router. 1476 N_advertised is a boolean flag, describing if this router has 1477 elected to advertise a link to this neighbor in its TC messages. 1479 A Neighbor Tuple created (but not updated) by [RFC6130] MUST set: 1481 o N_orig_addr := unknown; 1483 o N_in_metric := UNKNOWN_METRIC; 1485 o N_out_metric := UNKNOWN_METRIC; 1487 o N_will_flooding := WILL_NEVER; 1489 o N_will_routing := WILL_NEVER; 1490 o N_routing_mpr := false; 1492 o N_flooding_mpr := false; 1494 o N_mpr_selector := false; 1496 o N_advertised := false. 1498 The Neighbor Information Base also includes a variable, the 1499 Advertised Neighbor Sequence Number (ANSN), whose value is included 1500 in TC messages to indicate the freshness of the information 1501 transmitted. The ANSN is incremented whenever advertised information 1502 (the originator and routable addresses included in Neighbor Tuples 1503 with N_advertised = true, and local attached networks recorded in the 1504 Local Attached Network Set in the Local Information Base) changes, 1505 including addition or removal of such information. 1507 10. Topology Information Base 1509 The Topology Information Base, defined for each router by this 1510 specification, stores information received in TC messages, in the 1511 Advertising Remote Router Set, the Router Topology Set, the Routable 1512 Address Topology Set and the Attached Network Set. 1514 Additionally, a Routing Set is maintained, derived from the 1515 information recorded in the Local Information Base, the Interface 1516 Information Bases, the Neighbor Information Base and the rest of the 1517 Topology Information Base. 1519 10.1. Advertising Remote Router Set 1521 A router's Advertising Remote Router Set records information 1522 describing each remote router in the network that transmits TC 1523 messages, allowing outdated TC messages to be recognized and 1524 discarded. It consists of Advertising Remote Router Tuples: 1526 (AR_orig_addr, AR_seq_number, AR_time) 1528 where: 1530 AR_orig_addr is the originator address of a received TC message, 1531 note that this does not include a prefix length; 1533 AR_seq_number is the greatest ANSN in any TC message received 1534 which originated from the router with originator address 1535 AR_orig_addr (i.e., which contributed to the information contained 1536 in this Tuple); 1537 AR_time is the time at which this Tuple expires and MUST be 1538 removed. 1540 10.2. Router Topology Set 1542 A router's Topology Set records topology information about the links 1543 between routers in the MANET. It consists of Router Topology Tuples: 1545 (TR_from_orig_addr, TR_to_orig_addr, TR_seq_number, TR_metric, 1546 TR_time) 1548 where: 1550 TR_from_orig_addr is the originator address of a router which can 1551 reach the router with originator address TR_to_orig_addr in one 1552 hop, note that this does not include a prefix length; 1554 TR_to_orig_addr is the originator address of a router which can be 1555 reached by the router with originator address TR_to_orig_addr in 1556 one hop, note that this does not include a prefix length; 1558 TR_seq_number is the greatest ANSN in any TC message received 1559 which originated from the router with originator address 1560 TR_from_orig_addr (i.e., which contributed to the information 1561 contained in this Tuple); 1563 TR_metric is the neighbor metric from the router with originator 1564 address TR_from_orig_addr to the router with originator address 1565 TR_to_orig_addr; 1567 TR_time specifies the time at which this Tuple expires and MUST be 1568 removed. 1570 10.3. Routable Address Topology Set 1572 A router's Routable Address Topology Set records topology information 1573 about the routable addresses within the MANET, and via which routers 1574 they may be reached. It consists of Routable Address Topology 1575 Tuples: 1577 (TA_from_orig_addr, TA_dest_addr, TA_seq_number, TA_metric, 1578 TA_time) 1580 where: 1582 TA_from_orig_addr is the originator address of a router which can 1583 reach the router with routable address TA_dest_addr in one hop, 1584 note that this does not include a prefix length; 1585 TA_dest_addr is a routable address of a router which can be 1586 reached by the router with originator address TA_from_orig_addr in 1587 one hop; 1589 TA_seq_number is the greatest ANSN in any TC message received 1590 which originated from the router with originator address 1591 TA_from_orig_addr (i.e., which contributed to the information 1592 contained in this Tuple); 1594 TA_metric is the neighbor metric from the router with originator 1595 address TA_from_orig_addr to the router with OLSRv2 interface 1596 address TA_dest_addr; 1598 TA_time specifies the time at which this Tuple expires and MUST be 1599 removed. 1601 10.4. Attached Network Set 1603 A router's Attached Network Set records information about networks 1604 (which may be outside the MANET) attached to other routers and their 1605 routable addresses. It consists of Attached Network Tuples: 1607 (AN_orig_addr, AN_net_addr, AN_seq_number, AN_dist, AN_metric, 1608 AN_time) 1610 where: 1612 AN_orig_addr is the originator address of a router which can act 1613 as gateway to the network with network address AN_net_addr, note 1614 that this does not include a prefix length; 1616 AN_net_addr is the network address of an attached network, which 1617 may be reached via the router with originator address 1618 AN_orig_addr; 1620 AN_seq_number is the greatest ANSN in any TC message received 1621 which originated from the router with originator address 1622 AN_orig_addr (i.e., which contributed to the information contained 1623 in this Tuple); 1625 AN_dist is the number of hops to the network with network address 1626 AN_net_addr from the router with originator address AN_orig_addr; 1628 AN_metric is the metric of the link from the router with 1629 originator address AN_orig_addr to the attached network with 1630 address AN_net_addr; 1631 AN_time specifies the time at which this Tuple expires and MUST be 1632 removed. 1634 10.5. Routing Set 1636 A router's Routing Set records the first hop along a selected path to 1637 each destination for which any such path is known. It consists of 1638 Routing Tuples: 1640 (R_dest_addr, R_next_iface_addr, R_local_iface_addr, R_dist, 1641 R_metric) 1643 where: 1645 R_dest_addr is the network address of the destination, either the 1646 network address of an interface of a destination router, or the 1647 network address of an attached network; 1649 R_next_iface_addr is the network address of the "next hop" on the 1650 selected path to the destination; 1652 R_local_iface_addr is an address of the local interface over which 1653 an IP packet MUST be sent to reach the destination by the selected 1654 path. 1656 R_dist is the number of hops on the selected path to the 1657 destination; 1659 R_metric is the metric of the route to the destination with 1660 address R_dest_addr. 1662 The Routing Set for a router is derived from the contents of other 1663 Protocol Sets of the router (the Link Sets, the Neighbor Set, the 1664 Router Topology Set, the Routable Address Topology Set, the Attached 1665 Network Set, and OPTIONAL use of the 2-Hop Sets). The Routing Set is 1666 updated (Routing Tuples added or removed, or the complete Routing Set 1667 recalculated) when routing paths are calculated, based on changes to 1668 these other Protocol Sets. Routing Tuples are not subject to timer- 1669 based expiration. 1671 11. Received Message Information Base 1673 The Received Message Information Base, defined by this specification, 1674 records information required to ensure that a message is processed at 1675 most once and is forwarded at most once per OLSRv2 interface of a 1676 router, using MPR flooding. Messages are recorded using their 1677 "signature", consisting of their type, originator address, and 1678 message sequence number. 1680 11.1. Received Set 1682 A router has a Received Set per OLSRv2 interface. Each Received Set 1683 records the signatures of messages which have been received over that 1684 OLSRv2 interface. Each consists of Received Tuples: 1686 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 1688 where: 1690 RX_type is the received Message Type; 1692 RX_orig_addr is the originator address of the received message, 1693 note that this does not include a prefix length; 1695 RX_seq_number is the message sequence number of the received 1696 message; 1698 RX_time specifies the time at which this Tuple expires and MUST be 1699 removed. 1701 11.2. Processed Set 1703 A router has a single Processed Set which records signatures of 1704 messages which have been processed by the router. It consists of 1705 Processed Tuples: 1707 (P_type, P_orig_addr, P_seq_number, P_time) 1709 where: 1711 P_type is the processed Message Type; 1713 P_orig_addr is the originator address of the processed message, 1714 note that this does not include a prefix length; 1716 P_seq_number is the message sequence number of the processed 1717 message; 1719 P_time specifies the time at which this Tuple expires and MUST be 1720 removed. 1722 11.3. Forwarded Set 1724 A router has a single Forwarded Set which records signatures of 1725 messages which have been forwarded by the router. It consists of 1726 Forwarded Tuples: 1728 (F_type, F_orig_addr, F_seq_number, F_time) 1730 where: 1732 F_type is the forwarded Message Type; 1734 F_orig_addr is the originator address of the forwarded message, 1735 note that this does not include a prefix length; 1737 F_seq_number is the message sequence number of the forwarded 1738 message; 1740 F_time specifies the time at which this Tuple expires and MUST be 1741 removed. 1743 12. Information Base Properties 1745 This section describes some additional properties of Information 1746 Bases and their contents. 1748 12.1. Corresponding Protocol Tuples 1750 As part of this specification, in a number of cases there is a 1751 natural correspondence from a Protocol Tuple in one Protocol Set to a 1752 single Protocol Tuple in another Protocol Set, in the same or another 1753 Information Base. The latter Protocol Tuple is referred to as 1754 "corresponding" to the former Protocol Tuple. 1756 Specific examples of corresponding Protocol Tuples include: 1758 o There is a Local Interface Tuple corresponding to each Link Tuple, 1759 where the Link Tuple is in the Link Set for a MANET interface, and 1760 the Local Interface Tuple represents that MANET interface. 1762 o There is a Neighbor Tuple corresponding to each Link Tuple which 1763 has L_HEARD_time not expired, such that N_neighbor_addr_list 1764 contains L_neighbor_iface_addr_list. 1766 o There is a Link Tuple (in the Link Set in the same Interface 1767 Information Base) corresponding to each 2-Hop Tuple such that 1768 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 1770 o There is a Neighbor Tuple corresponding to each 2-Hop Tuple, such 1771 that N_neighbor_addr_list contains N2_neighbor_iface_addr_list. 1772 (This is the Neighbor Tuple corresponding to the Link Tuple 1773 corresponding to the 2-Hop Tuple.) 1775 o There is an Advertising Remote Router Tuple corresponding to each 1776 Router Topology Tuple such that AR_orig_addr = TR_from_orig_addr. 1778 o There is an Advertising Remote Router Tuple corresponding to each 1779 Routable Address Topology Tuple such that AR_orig_addr = 1780 TA_from_orig_addr. 1782 o There is an Advertising Remote Router Tuple corresponding to each 1783 Attached Network Tuple such that AR_orig_addr = AN_orig_addr. 1785 o There is a Neighbor Tuple corresponding to each Routing Tuple such 1786 that N_neighbor_addr_list contains R_next_iface_addr. 1788 12.2. Address Ownership 1790 Addresses or network addresses with the following properties are 1791 considered as "fully owned" by a router when processing a received 1792 message: 1794 o Equaling its originator address, OR; 1796 o Equaling the O_orig_addr in an Originator Tuple, OR; 1798 o Equaling or being a sub-range of the I_local_iface_addr_list in a 1799 Local Interface Tuple, OR; 1801 o Equaling or being a sub-range of the IR_local_iface_addr in a 1802 Removed Interface Address Tuple, OR; 1804 o Equaling an AL_net_addr in a Local Attached Network Tuple. 1806 Addresses or network addresses with the following properties are 1807 considered as "partially owned" (which may include being fully owned) 1808 by a router when processing a received message: 1810 o Overlapping (equaling or containing) its originator address, OR; 1812 o Overlapping (equaling or containing) the O_orig_addr in an 1813 Originator Tuple, OR; 1815 o Overlapping the I_local_iface_addr_list in a Local Interface 1816 Tuple, OR; 1818 o Overlapping the IR_local_iface_addr in a Removed Interface Address 1819 Tuple, OR; 1821 o Equaling or having as a sub-range an AL_net_addr in a Local 1822 Attached Network Tuple. 1824 13. Packets and Messages 1826 The packet and message format used by this protocol is defined in 1827 [RFC5444]. Except as otherwise noted, options defined in [RFC5444] 1828 may be freely used, in particular alternative formats defined by 1829 packet, message, Address Block and TLV flags. 1831 This section describes the usage of the packets and messages defined 1832 in [RFC5444] by this specification, and the TLVs defined by, and used 1833 in, this specification. 1835 13.1. Messages 1837 Routers using this protocol exchange information through messages. 1838 The message types used by this protocol are the HELLO message and the 1839 TC message. The HELLO message is defined by [RFC6130] and extended 1840 by this specification, see Section 15. The TC message is defined by 1841 this specification, see Section 16. 1843 13.2. Packets 1845 One or more messages sent by a router at the same time SHOULD be 1846 combined into a single packet, subject to any constraints on maximum 1847 packet size (such as derived from the MTU over a local single hop) 1848 that MAY be imposed. These messages may have originated at the 1849 sending router, or have originated at another router and are being 1850 forwarded by the sending router. Messages with different originating 1851 routers MAY be combined for transmission within the same packet. 1852 Messages from other protocols defined using [RFC5444], including but 1853 not limited to [RFC6130], MAY be combined for transmission within the 1854 same packet. This specification does not define or use any contents 1855 of the Packet Header. 1857 Forwarded messages MAY be jittered as described in [RFC5148], 1858 including the observation that the forwarding jitter of all messages 1859 received in a single packet SHOULD be the same. The value of 1860 MAXJITTER used in jittering a forwarded message MAY be based on 1861 information in that message (in particular any Message TLVs with Type 1862 = INTERVAL_TIME or Type = VALIDITY_TIME) or otherwise SHOULD be with 1863 a maximum delay of F_MAXJITTER. A router MAY modify the jitter 1864 applied to a message in order to more efficiently combine messages in 1865 packets, as long as the maximum jitter is not exceeded. 1867 13.3. TLVs 1869 This specification defines two Message TLVs and four Address Block 1870 TLVs. 1872 All references in this specification to TLVs that do not indicate a 1873 type extension, assume Type Extension = 0. TLVs in processed 1874 messages with a type extension which is neither zero as so assumed, 1875 nor a specifically indicated non-zero type extension, are ignored. 1877 13.3.1. Message TLVs 1879 The MPR_WILLING TLV is used in HELLO messages. A message MUST NOT 1880 contain more than one MPR_WILLING TLV. 1882 +-------------+--------------+--------------------------------------+ 1883 | Type | Value Length | Value | 1884 +-------------+--------------+--------------------------------------+ 1885 | MPR_WILLING | 1 octet | Bits 0-3 encode the parameter | 1886 | | | WILL_FLOODING; bits 4-7 encode the | 1887 | | | parameter WILL_ROUTING. | 1888 +-------------+--------------+--------------------------------------+ 1890 Table 1: MPR_WILLING TLV definition 1892 The CONT_SEQ_NUM TLV is used in TC messages. A message MUST NOT 1893 contain more than one CONT_SEQ_NUM TLV. 1895 +--------------+--------------+-------------------------------------+ 1896 | Type | Value Length | Value | 1897 +--------------+--------------+-------------------------------------+ 1898 | CONT_SEQ_NUM | 2 octets | The ANSN contained in the Neighbor | 1899 | | | Information Base. | 1900 +--------------+--------------+-------------------------------------+ 1902 Table 2: CONT_SEQ_NUM TLV definition 1904 13.3.2. Address Block TLVs 1906 The LINK_METRIC TLV is used in HELLO messages and TC messages. It 1907 MAY use any type extension; only LINK_METRIC TLVs with type extension 1908 equal to LINK_METRIC_TYPE will be used by this specification. An 1909 address MUST NOT be associated with more than one link metric value 1910 for any given type extension, kind (link or neighbor) and direction 1911 using this TLV. 1913 +-------------+--------------+--------------------------------------+ 1914 | Type | Value Length | Value | 1915 +-------------+--------------+--------------------------------------+ 1916 | LINK_METRIC | 2 octets | Bits 0-3 indicates kind(s) and | 1917 | | | direction(s), bits 4-7 indicate | 1918 | | | exponent (a), bits 8-15 indicate | 1919 | | | mantissa (b) | 1920 +-------------+--------------+--------------------------------------+ 1922 Table 3: LINK_METRIC TLV definition 1924 The exponent and mantissa use the representation defined in 1925 Section 6. Each bit of the types and directions sub-field, if set 1926 ('1') indicates that the link metric is of the indicated kind and 1927 direction. Any combination of these bits MAY be used. 1929 +-----+-----------------+-----------+ 1930 | Bit | Kind | Direction | 1931 +-----+-----------------+-----------+ 1932 | 0 | Link metric | Incoming | 1933 | 1 | Link metric | Outgoing | 1934 | 2 | Neighbor metric | Incoming | 1935 | 3 | Neighbor metric | Outgoing | 1936 +-----+-----------------+-----------+ 1938 Table 4: LINK_METRIC TLV types and directions 1940 The MPR TLV is used in HELLO messages, and indicates that an address 1941 with which it is associated is of a symmetric 1-hop neighbor that has 1942 been selected as an MPR. 1944 +------+--------------+---------------------------------------------+ 1945 | Type | Value Length | Value | 1946 +------+--------------+---------------------------------------------+ 1947 | MPR | 1 octet | FLOODING indicates that the corresponding | 1948 | | | address is of a neighbor selected as a | 1949 | | | flooding MPR, ROUTING indicates that the | 1950 | | | corresponding address is of a neighbor | 1951 | | | selected as a routing MPR, FLOOD_ROUTE | 1952 | | | indicates both (see Section 24.6). | 1953 +------+--------------+---------------------------------------------+ 1955 Table 5: MPR TLV definition 1957 The NBR_ADDR_TYPE TLV is used in TC messages. 1959 +---------------+--------------+------------------------------------+ 1960 | Type | Value Length | Value | 1961 +---------------+--------------+------------------------------------+ 1962 | NBR_ADDR_TYPE | 1 octet | ORIGINATOR indicates that the | 1963 | | | corresponding address (which MUST | 1964 | | | have maximum prefix length) is an | 1965 | | | originator address, ROUTABLE | 1966 | | | indicates that the corresponding | 1967 | | | network address is a routable | 1968 | | | address of an interface, | 1969 | | | ROUTABLE_ORIG indicates that the | 1970 | | | corresponding address is both (see | 1971 | | | Section 24.6). | 1972 +---------------+--------------+------------------------------------+ 1974 Table 6: NBR_ADDR_TYPE TLV definition 1976 If an address is both an originator address and a routable address, 1977 then it may be associated with either one Address Block TLV with Type 1978 := NBR_ADDR_TYPE and Value := ROUTABLE_ORIG, or with two Address 1979 Block TLVs with Type:= NBR_ADDR_TYPE, one with Value := ORIGINATOR 1980 and one with Value := ROUTABLE. 1982 The GATEWAY TLV is used in TC messages. An address MUST NOT be 1983 associated with more than one hop count value using this TLV. 1985 +---------+--------------+-------------------------------------+ 1986 | Type | Value Length | Value | 1987 +---------+--------------+-------------------------------------+ 1988 | GATEWAY | 1 octet | Number of hops to attached network. | 1989 +---------+--------------+-------------------------------------+ 1991 Table 7: GATEWAY TLV definition 1993 All address objects included in a TC message according to this 1994 specification MUST be associated either with at least one TLV with 1995 Type := NBR_ADDR_TYPE or with a TLV with Type := GATEWAY, but not 1996 both. Any other address objects MAY be included in Address Blocks in 1997 a TC message, but are ignored by this specification. 1999 14. Message Processing and Forwarding 2001 This section describes the optimized flooding operation (MPR 2002 flooding) used when control messages, as instances of [RFC5444], are 2003 intended for MANET wide distribution. This flooding mechanism 2004 defines when a received message is, or is not, processed and/or 2005 forwarded. 2007 This flooding mechanism is used by this protocol and MAY be used by 2008 extensions to this protocol which define, and hence own, other 2009 Message Types, to manage processing and/or forwarding of these 2010 messages. This specification contains elements (P_type, RX_type, 2011 F_type) required only for such usage. 2013 This flooding mechanism is always used for TC messages (see 2014 Section 16). Received HELLO messages (see Section 15) are, unless 2015 invalid, always processed, and never forwarded by this flooding 2016 mechanism. They thus do not need to be recorded in the Received 2017 Message Information Base. 2019 The processing selection and forwarding mechanisms are designed to 2020 only need to parse the Message Header in order to determine whether a 2021 message is to be processed and/or forwarded, and not to have to parse 2022 the Message Body even if the message is forwarded (but not 2023 processed). An implementation MAY only parse the Message Body if 2024 necessary, or MAY always parse the Message Body and reject the 2025 message if it cannot be so parsed, or any other error is identified. 2027 An implementation MUST discard the message silently if it is unable 2028 to parse the Message Header or (if attempted) the Message Body, or if 2029 a message (other than a HELLO message) does not include a message 2030 sequence number. 2032 14.1. Actions when Receiving a Message 2034 On receiving, on an OLSRv2 interface, a message of a type specified 2035 to be using this mechanism, which includes the TC messages defined in 2036 this specification, a router MUST perform the following: 2038 1. If the router recognizes from the originator address of the 2039 message that the message is one which the receiving router itself 2040 originated (i.e., the message originator address is the 2041 originator address of this router, or is an O_orig_addr in an 2042 Originator Tuple) then the message MUST be silently discarded. 2044 2. Otherwise: 2046 1. If the message is of a type which may be processed, then the 2047 message is considered for processing according to 2048 Section 14.2. 2050 2. If the message is of a type which may be forwarded, AND: 2052 + is present and > 1; AND 2054 + is not present or < 255; 2056 then the message is considered for forwarding according to 2057 Section 14.3. 2059 14.2. Message Considered for Processing 2061 If a message (the "current message") is considered for processing, 2062 then the following tasks MUST be performed: 2064 1. If the sending address (i.e., the source address of the IP 2065 datagram containing the current message) does not match (taking 2066 into account any address prefix) a network address in an 2067 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2068 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2069 current message was received (the "receiving interface") then 2070 processing the current message is OPTIONAL. If the current 2071 message is not processed then the following steps are not carried 2072 out. 2074 2. If a Processed Tuple exists with: 2076 * P_type = the Message Type of the current message; AND 2078 * P_orig_addr = the originator address of the current message; 2079 AND 2081 * P_seq_number = the message sequence number of the current 2082 message; 2084 then the current message MUST NOT be processed. 2086 3. Otherwise: 2088 1. Create a Processed Tuple in the Processed Set with: 2090 + P_type := the Message Type of the current message; 2092 + P_orig_addr := the originator address of the current 2093 message; 2095 + P_seq_number := the sequence number of the current 2096 message; 2098 + P_time := current time + P_HOLD_TIME. 2100 2. Process the current message according to its Message Type. 2101 For a TC message this is as defined in Section 16.3. 2103 14.3. Message Considered for Forwarding 2105 If a message (the "current message") is considered for forwarding, 2106 then the following tasks MUST be performed: 2108 1. If the sending address (i.e., the source address of the IP 2109 datagram containing the current message) does not match (taking 2110 into account any address prefix) a network address in an 2111 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2112 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2113 current message was received (the "receiving interface") then the 2114 current message MUST be silently discarded. 2116 2. Otherwise: 2118 1. If a Received Tuple exists in the Received Set for the 2119 receiving interface, with: 2121 + RX_type = the Message Type of the current message; AND 2123 + RX_orig_addr = the originator address of the current 2124 message; AND 2126 + RX_seq_number = the sequence number of the current 2127 message; 2129 then the current message MUST be silently discarded. 2131 2. Otherwise: 2133 1. Create a Received Tuple in the Received Set for the 2134 receiving interface with: 2136 - RX_type := the Message Type of the current message; 2138 - RX_orig_addr := originator address of the current 2139 message; 2141 - RX_seq_number := sequence number of the current 2142 message; 2144 - RX_time := current time + RX_HOLD_TIME. 2146 2. If a Forwarded Tuple exists with: 2148 - F_type = the Message Type of the current message; AND 2150 - F_orig_addr = the originator address of the current 2151 message; AND 2153 - F_seq_number = the sequence number of the current 2154 message. 2156 then the current message MUST be silently discarded. 2158 3. Otherwise if the sending address matches (taking account 2159 of any address prefix) any network address in an 2160 L_neighbor_iface_addr_list of a Link Tuple in the Link 2161 Set for the receiving OLSRv2 interface that has L_status 2162 = SYMMETRIC and whose corresponding Neighbor Tuple has 2163 N_mpr_selector = true, then: 2165 1. Create a Forwarded Tuple in the Forwarded Set with: 2167 o F_type := the Message Type of the current message; 2169 o F_orig_addr := originator address of the current 2170 message; 2172 o F_seq_number := sequence number of the current 2173 message; 2175 o F_time := current time + F_HOLD_TIME. 2177 2. The Message Header of the current message is modified 2178 by: 2180 o Decrement in the Message Header by 2181 1; AND 2183 o If present, increment in the 2184 Message Header by 1. 2186 3. The message is transmitted over all OLSRv2 2187 interfaces, as described in Section 13. 2189 15. HELLO Messages 2191 The HELLO Message Type is owned by [RFC6130], and thus HELLO messages 2192 are generated, transmitted, received and processed by [RFC6130]. 2193 This protocol, as permitted by [RFC6130], also uses HELLO messages, 2194 including adding to HELLO message generation, and implementing 2195 additional processing based on received HELLO messages. HELLO 2196 messages are not forwarded by [RFC6130] or by this specification. 2198 15.1. HELLO Message Generation 2200 HELLO messages sent over OLSRv2 interfaces are generated as defined 2201 in [RFC6130], and then modified as described in this section. HELLO 2202 messages sent on other MANET interfaces are not modified by this 2203 specification. 2205 HELLO messages sent over OLSRv2 interfaces are extended by adding the 2206 following elements: 2208 o A message originator address, recording this router's originator 2209 address. This MUST use a element, unless: 2211 * The message specifies only a single local interface address 2212 (i.e., contains only one address object that is associated with 2213 an Address Block TLV with Type = LOCAL_IF, and which has no 2214 prefix length, or a maximum prefix length) which will then be 2215 used as the message originator address, OR; 2217 * The message does not include any local interface network 2218 addresses (i.e., has no address objects associated with an 2219 Address Block TLV with Type = LOCAL_IF), as permitted by the 2220 specification in [RFC6130], when the router that generated the 2221 HELLO message has only one interface address and will use that 2222 as the sending address of the IP datagram in which the HELLO 2223 message is contained. In this case, that address will be used 2224 as the message originator address. 2226 o A Message TLV with Type := MPR_WILLING MUST be included. 2228 o The following cases associate Address Block TLVs with one or more 2229 addresses from a Link Tuple or a Neighbor Tuple if these are 2230 included in the HELLO message. In each case, the TLV MUST be 2231 associated with at least one address object for an address from 2232 the relevant Tuple; the TLV MAY be associated with more such 2233 addresses (including a copy of that address object, possibly not 2234 itself associated with any other indicated TLVs, in the same or a 2235 different Address Block). These additional TLVs MUST NOT be 2236 associated with any other addresses in a HELLO message that will 2237 be processed by [RFC6130]. 2239 * For each Link Tuple for which L_in_metric != UNKNOWN_METRIC, 2240 and for which one or more addresses in its 2241 L_neighbor_iface_addr_list are included as address objects with 2242 an associated Address Block TLV with Type = LINK_STATUS and 2243 Value = HEARD or Value = SYMMETRIC, at least one of these 2244 addresses MUST be associated with an Address Block TLV with 2245 Type := LINK_METRIC indicating an incoming link metric with 2246 value L_in_metric. 2248 * For each Link Tuple for which L_out_metric != UNKNOWN_METRIC, 2249 and for which one or more addresses in its 2250 L_neighbor_iface_addr_list are included as address objects with 2251 an associated Address Block TLV with Type = LINK_STATUS and 2252 Value = SYMMETRIC, at least one of these addresses MUST be 2253 associated with an Address Block TLV with Type := LINK_METRIC 2254 indicating an outgoing link metric with value L_out_metric. 2256 * For each Neighbor Tuple for which N_symmetric = true, and for 2257 which one or more addresses in its N_neighbor_addr_list are 2258 included as address objects with an associated Address Block 2259 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2260 SYMMETRIC, at least one of these addresses MUST be associated 2261 with an Address Block TLV with Type := LINK_METRIC indicating 2262 an incoming neighbor metric with value N_in_metric. 2264 * For each Neighbor Tuple for which N_symmetric = true, and for 2265 which one or more addresses in its N_neighbor_addr_list are 2266 included as address objects with an associated Address Block 2267 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2268 SYMMETRIC, at least one of these addresses MUST be associated 2269 with an Address Block TLV with Type := LINK_METRIC indicating 2270 an outgoing neighbor metric with value N_out_metric. 2272 * For each Neighbor Tuple with N_flooding_mpr = true, and for 2273 which one or more network addresses in its N_neighbor_addr_list 2274 are included as address objects in the HELLO message with an 2275 associated Address Block TLV with Type = LINK_STATUS and Value 2276 = SYMMETRIC, at least one of these addresses MUST be associated 2277 with an Address Block TLV with Type := MPR and Value := 2278 FLOODING or Value := FLOOD_ROUTE. 2280 * For each Neighbor Tuple with N_routing_mpr = true, and for 2281 which one or more network addresses in its N_neighbor_addr_list 2282 are included as address objects in the HELLO message with an 2283 associated Address Block TLV with Type = LINK_STATUS and Value 2284 = SYMMETRIC, at least one of these addresses MUST be associated 2285 with an Address Block TLV with Type := MPR and Value := ROUTING 2286 or Value := FLOOD_ROUTE. 2288 15.2. HELLO Message Transmission 2290 HELLO messages are scheduled and transmitted by [RFC6130]. This 2291 protocol MAY require that an additional HELLO message is sent on each 2292 OLSRv2 interface when either of the router's sets of MPRs changes, in 2293 addition to the cases specified in [RFC6130], and subject to the 2294 constraints specified in [RFC6130] (notably on minimum HELLO message 2295 transmission intervals). 2297 15.3. HELLO Message Processing 2299 When received on an OLSRv2 interface, HELLO messages are made 2300 available to this protocol in two ways, both as permitted by 2301 [RFC6130]: 2303 o Such received HELLO messages MUST be made available to this 2304 protocol on reception, which allows them to be discarded before 2305 being processed by [RFC6130], for example if the information added 2306 to the HELLO message by this specification is inconsistent. 2308 o Such received HELLO messages MUST be made available to OLSRv2 2309 after [RFC6130] has completed its processing thereof, unless 2310 discarded as malformed by [RFC6130], for processing by this 2311 specification. 2313 15.3.1. HELLO Message Discarding 2315 In addition to the reasons specified in [RFC6130] for discarding a 2316 HELLO message on reception, a HELLO message received on an OLSRv2 2317 interface MUST be discarded before processing by [RFC6130] or this 2318 specification if it: 2320 o Has more than one Message TLV with Type = MPR_WILLING. 2322 o Has a message originator address, or a network address 2323 corresponding to an address object associated with an Address 2324 Block TLV with Type = LOCAL_IF, that is partially owned by this 2325 router. (Some of these cases are already excluded by [RFC6130].) 2327 o Includes any address object associated with an Address Block TLV 2328 with Type = LINK_STATUS or Type = OTHER_NEIGHB that overlaps the 2329 message's originator address. 2331 o Contains any address that will be processed by [RFC6130] that is 2332 associated, using the same or different address objects, with two 2333 different values of link metric with the same kind and direction 2334 using a TLV with Type = LINK_METRIC and Type Extension = 2335 LINK_METRIC_TYPE. This also applies to different addresses that 2336 are both of the OLSRv2 interface on which the HELLO message was 2337 received. 2339 o Contains any address object associated with an Address Block TLV 2340 with Type = MPR that is not also associated with an Address Block 2341 TLV with Type = LINK_STATUS and Value = SYMMETRIC (including using 2342 a different copy of that address object, in the same or a 2343 different Address Block). 2345 15.3.2. HELLO Message Usage 2347 HELLO messages are first processed as specified in [RFC6130]. That 2348 processing includes identifying (or creating) a Link Tuple and a 2349 Neighbor Tuple corresponding to the originator of the HELLO message 2350 (the "current Link Tuple" and the "current Neighbor Tuple"). After 2351 this, the following processing MUST also be performed if the HELLO 2352 message is received on an OLSRv2 interface and contains a TLV with 2353 Type = MPR_WILLING: 2355 1. If the HELLO message has a well-defined message originator 2356 address, i.e., has an element, or has zero or one 2357 network addresses associated with a TLV with Type = LOCAL_IF: 2359 1. Remove any Neighbor Tuple, other than the current Neighbor 2360 Tuple, with N_orig_addr = message originator address, taking 2361 any consequent action (including removing one or more Link 2362 Tuples) as specified in [RFC6130]. 2364 2. The current Link Tuple is then updated according to: 2366 1. Update L_in_metric and L_out_metric as described in 2367 Section 15.3.2.1; 2369 2. Update L_mpr_selector as described in Section 15.3.2.3. 2371 3. The current Neighbor Tuple is then updated according to: 2373 1. N_orig_addr := message originator address; 2375 2. Update N_in_metric and N_out_metric as described in 2376 Section 15.3.2.1; 2378 3. Update N_will_flooding and N_will_routing as described in 2379 Section 15.3.2.2; 2381 4. Update N_mpr_selector as described in Section 15.3.2.3. 2383 2. If there are any changes to the router's Information Bases, then 2384 perform the processing defined in Section 17. 2386 15.3.2.1. Updating Metrics 2388 For each address in a received HELLO message with an associated TLV 2389 with Type = LINK_STATUS and Value = HEARD or Value = SYMMETRIC, an 2390 incoming (to the message originator) link metric value is defined 2391 either using an associated TLV with Type = LINK_METRIC and Type 2392 Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2393 (link) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2395 For each address in a received HELLO message with an associated TLV 2396 with Type = LINK_STATUS and Value = SYMMETRIC, an outgoing (from the 2397 message originator) link metric value is defined either using an 2398 associated TLV with Type = LINK_METRIC and Type Extension = 2399 LINK_METRIC_TYPE that indicates the appropriate kind (link) and 2400 direction (outgoing) of metric, or as UNKNOWN_METRIC. 2402 For each address in a received HELLO message with an associated TLV 2403 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2404 an incoming (to the message originator) neighbor metric value is 2405 defined either using an associated TLV with Type = LINK_METRIC and 2406 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2407 (neighbor) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2409 For each address in a received HELLO message with an associated TLV 2410 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2411 an outgoing (from the message originator) neighbor metric value is 2412 defined either using an associated TLV with Type = LINK_METRIC and 2413 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2414 (neighbor) and direction (outgoing) of metric, or as UNKNOWN_METRIC. 2416 The link metric elements L_in_metric and L_out_metric in a Link Tuple 2417 are updated according to the following: 2419 o For any Link Tuple, L_in_metric MAY be set to any representable 2420 value, by a process outside this specification, at any time. 2421 L_in_metric MUST be so set whenever L_status becomes equal to 2422 HEARD or SYMMETRIC (if no other value is available then the value 2423 MAXIMUM_METRIC MUST be used). Setting L_in_metric MAY use 2424 information based on the receipt of a packet including a HELLO 2425 message that causes the creation or updating of the Link Tuple. 2427 o When, as specified in [RFC6130], a Link Tuple is updated (possibly 2428 immediately after being created) due to the receipt of a HELLO 2429 message, if L_status = SYMMETRIC, then L_out_metric is set equal 2430 to the incoming link metric for any included address of the 2431 interface on which the HELLO message was received. (Note that the 2432 rules for discarding HELLO messages in Section 15.3.1 make this 2433 value unambiguous.) If there is no such link metric then 2434 L_out_metric is set to UNKNOWN_METRIC. 2436 The neighbor metric elements N_in_metric and N_out_metric in a 2437 Neighbor Tuple are updated according to Section 17.3. 2439 The metric elements N2_in_metric and N2_out_metric in any 2-Hop Tuple 2440 updated as defined in [RFC6130] are updated to equal the incoming 2441 neighbor metric and outgoing neighbor metric, respectively, 2442 associated with the corresponding N2_2hop_addr. If there are no such 2443 metrics then these elements are set to UNKNOWN_METRIC. 2445 15.3.2.2. Updating Willingness 2447 N_will_flooding and N_will_routing in the current Neighbor Tuple are 2448 updated using the Message TLV with Type = MPR_WILLING (note that this 2449 must be present) as follows: 2451 o N_will_flooding := bits 0-3 of the value of that TLV; AND 2453 o N_will_routing := bits 4-7 of the value of that TLV. 2455 (Each being in the range 0 to 15, i.e., WILL_NEVER to WILL_ALWAYS.) 2457 15.3.2.3. Updating MPR Selector Status 2459 L_mpr_selector is updated as follows: 2461 1. If a router finds an address object representing any of its 2462 relevant local interface network addresses (i.e., those contained 2463 in the I_local_iface_addr_list of an OLSRv2 interface) with an 2464 associated Address Block TLV with Type = MPR and Value = FLOODING 2465 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2466 originating router has selected the receiving router as a 2467 flooding MPR) then, for the current Link Tuple: 2469 * L_mpr_selector := true. 2471 2. Otherwise (i.e., if no such address object and Address Block TLV 2472 was found), if a router finds an address object representing any 2473 of its relevant local interface network addresses (i.e., those 2474 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2475 with an associated Address Block TLV with Type = LINK_STATUS and 2476 Value = SYMMETRIC in the HELLO message, then for the current Link 2477 Tuple: 2479 * L_mpr_selector := false. 2481 N_mpr_selector is updated as follows: 2483 1. If a router finds an address object representing any of its 2484 relevant local interface network addresses (those contained in 2485 the I_local_iface_addr_list of an OLSRv2 interface) with an 2486 associated Address Block TLV with Type = MPR and Value = ROUTING 2487 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2488 originating router has selected the receiving router as a routing 2489 MPR) then, for the current Neighbor Tuple: 2491 * N_mpr_selector := true; 2493 * N_advertised := true. 2495 2. Otherwise (i.e., if no such address object and Address Block TLV 2496 was found), if a router finds an address object representing any 2497 of its relevant local interface network addresses (those 2498 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2499 with an associated Address Block TLV with Type = LINK_STATUS and 2500 Value = SYMMETRIC in the HELLO message, then for the current 2501 Neighbor Tuple: 2503 * N_mpr_selector := false; 2505 * The router MAY also set N_advertised := false. 2507 16. TC Messages 2509 This protocol defines, and hence owns, the TC Message Type (see 2510 Section 24). Thus, as specified in [RFC5444], this protocol 2511 generates and transmits all TC messages, receives all TC messages and 2512 is responsible for determining whether and how each TC message is to 2513 be processed (updating the Topology Information Base) and/or 2514 forwarded, according to this specification. 2516 16.1. TC Message Generation 2518 A TC message is a message as defined in [RFC5444]. A generated TC 2519 message MUST contain the following elements as defined in [RFC5444]: 2521 o A message originator address, recording this router's originator 2522 address. This MUST use a element. 2524 o element containing the message sequence number. 2526 o A element, containing TC_HOP_LIMIT. A router MAY 2527 use the same or different values of TC_HOP_LIMIT in its TC 2528 messages, see Section 5.4.7. 2530 o A element, containing zero, if the message 2531 contains a TLV with either Type = VALIDITY_TIME or Type = 2532 INTERVAL_TIME (as specified in [RFC5497]) indicating more than one 2533 time value according to distance. A TC message MAY contain such a 2534 element even if it does not need to. 2536 o A single Message TLV with Type := CONT_SEQ_NUM and Value := ANSN 2537 from the Neighbor Information Base. If the TC message is complete 2538 then this Message TLV MUST have Type Extension := COMPLETE, 2539 otherwise it MUST have Type Extension := INCOMPLETE. (Exception: 2540 a TC message MAY omit such a Message TLV if the TC message does 2541 not include any address objects with an associated Address Block 2542 TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY.) 2544 o A single Message TLV with Type := VALIDITY_TIME, as specified in 2545 [RFC5497]. If all TC messages are sent with the same hop limit 2546 then this TLV MUST have a value encoding the period T_HOLD_TIME. 2547 If TC messages are sent with different hop limits (more than one 2548 value of TC_HOP_LIMIT) then this TLV MUST specify times that vary 2549 with the number of hops appropriate to the chosen pattern of TC 2550 message hop limits, as specified in [RFC5497]; these times SHOULD 2551 be appropriate multiples of T_HOLD_TIME. The options included in 2552 [RFC5497] for representing zero and infinite times MUST NOT be 2553 used. 2555 o If the TC message is complete, all network addresses which are the 2556 N_orig_addr of a Neighbor Tuple with N_advertised = true, MUST be 2557 represented by address objects in one or more Address Blocks. If 2558 the TC message is incomplete then any such address objects MAY be 2559 included. At least one copy of each such address object that is 2560 included MUST be associated with an Address Block TLV with Type := 2561 NBR_ADDR_TYPE, and Value := ORIGINATOR, or with Value := 2562 ROUTABLE_ORIG if that address object is also to be associated with 2563 Value = ROUTABLE. 2565 o If the TC message is complete, all routable addresses which are in 2566 the N_neighbor_addr_list of a Neighbor Tuple with N_advertised = 2567 true MUST be represented by address objects in one or more Address 2568 Blocks. If the TC message is incomplete then any such address 2569 objects MAY be included. At least one copy of each such address 2570 object MUST be associated with an Address Block TLV with Type = 2571 NBR_ADDR_TYPE, and Value = ROUTABLE, or with Value = ROUTABLE_ORIG 2572 if also to be associated with Value = ORIGINATOR. At least one 2573 copy of each such address object MUST be associated with an 2574 Address Block TLV with Type = LINK_METRIC and Type Extension = 2575 LINK_METRIC_TYPE indicating an outgoing neighbor metric with value 2576 equal to the corresponding N_out_metric. 2578 o If the TC message is complete, all network addresses which are the 2579 AL_net_addr of a Local Attached Network Tuple MUST be represented 2580 by address objects in one or more Address Blocks. If the TC 2581 message is incomplete then any such address objects MAY be 2582 included. At least one copy of each such address object MUST be 2583 associated with an Address Block TLV with Type := GATEWAY, and 2584 Value := AN_dist. At least one copy of each such address object 2585 MUST be associated with an Address Block TLV with Type = 2586 LINK_METRIC and Type Extension = LINK_METRIC_TYPE indicating an 2587 outgoing neighbor metric equal to the corresponding AL_metric. 2589 A TC message MAY contain: 2591 o A single Message TLV with Type := INTERVAL_TIME, as specified in 2592 [RFC5497]. If all TC messages are sent with the same hop limit 2593 then this TLV MUST have a value encoding the period TC_INTERVAL. 2594 If TC messages are sent with different hop limits, then this TLV 2595 MUST specify times that vary with the number of hops appropriate 2596 to the chosen pattern of TC message hop limits, as specified in 2597 [RFC5497]; these times MUST be appropriate multiples of 2598 TC_INTERVAL. The options included in [RFC5497] for representing 2599 zero and infinite times MUST NOT be used. 2601 16.2. TC Message Transmission 2603 A router with one or more OLSRv2 interfaces, and with any Neighbor 2604 Tuples with N_advertised = true, or with a non-empty Local Attached 2605 Network Set MUST generate TC messages. A router which does not have 2606 such information to advertise MUST also generate "empty" TC messages 2607 for a period A_HOLD_TIME after it last generated a non-empty TC 2608 message. 2610 Complete TC messages are generated and transmitted periodically on 2611 all OLSRv2 interfaces, with a default interval between two 2612 consecutive TC message transmissions by the same router of 2613 TC_INTERVAL. 2615 TC messages MAY be generated in response to a change in the 2616 information which they are to advertise, indicated by a change in the 2617 ANSN in the Neighbor Information Base. In this case a router MAY 2618 send a complete TC message, and if so MAY re-start its TC message 2619 schedule. Alternatively, a router MAY send an incomplete TC message 2620 with at least the newly advertised network addresses (i.e., not 2621 previously, but now, an N_orig_addr or in an N_neighbor_addr_list in 2622 a Neighbor Tuple with N_advertised = true, or an AL_net_addr) in its 2623 Address Blocks, with associated Address Block TLV(s). Note that a 2624 router cannot report removal of advertised content using an 2625 incomplete TC message. 2627 When sending a TC message in response to a change of advertised 2628 network addresses, a router MUST respect a minimum interval of 2629 TC_MIN_INTERVAL between generated TC messages. Sending an incomplete 2630 TC message MUST NOT cause the interval between complete TC messages 2631 to be increased, and thus a router MUST NOT send an incomplete TC 2632 message if within TC_MIN_INTERVAL of the next scheduled complete TC 2633 message. 2635 The generation of TC messages, whether scheduled or triggered by a 2636 change of contents, MAY be jittered as described in [RFC5148]. The 2637 values of MAXJITTER used MUST be: 2639 o TP_MAXJITTER for periodic TC message generation; 2641 o TT_MAXJITTER for responsive TC message generation. 2643 16.3. TC Message Processing 2645 On receiving a TC message on an OLSRv2 interface, the receiving 2646 router MUST then follow the processing and forwarding procedures, 2647 defined in Section 14. 2649 If the message is considered for processing (Section 14.2), then a 2650 router MUST first check if the message is invalid for processing by 2651 this router, as defined in Section 16.3.1. A router MAY make a 2652 similar check before considering a message for forwarding, it MUST 2653 make those aspects of the check that apply to elements in the Message 2654 Header. 2656 If the TC message is not invalid, then the TC Message Type specific 2657 processing, described in Section 16.3.2 MUST be applied. This will 2658 update its appropriate Interface Information Bases and its Router 2659 Information Base. Following this, if there are any changes in these 2660 Information Bases, then the processing in Section 17 MUST be 2661 performed. 2663 16.3.1. TC Message Discarding 2665 A received TC message is invalid for processing by this router if the 2666 message: 2668 o Has an address length specified in the Message Header that is not 2669 equal to the length of the addresses used by this router. 2671 o Does not include a message originator address and a message 2672 sequence number. 2674 o Does not include a hop count, and contains a multi-value TLV with 2675 Type = VALIDITY_TIME or Type = INTERVAL_TIME, as defined in 2676 [RFC5497]. 2678 o Does not have exactly one Message TLV with Type = VALIDITY_TIME. 2680 o Has more than one Message TLV with Type = INTERVAL_TIME. 2682 o Does not have a Message TLV with Type = CONT_SEQ_NUM and Type 2683 Extension = COMPLETE or Type Extension = INCOMPLETE, and contains 2684 at least one address object associated with an Address Block TLV 2685 with Type = NBR_ADDR_TYPE or Type = GATEWAY. 2687 o Has more than one Message TLV with Type = CONT_SEQ_NUM and Type 2688 Extension = COMPLETE or Type Extension = INCOMPLETE. 2690 o Has a message originator address that is partially owned by this 2691 router. 2693 o Includes any address object with a prefix length which is not 2694 maximal (equal to the address length, in bits), associated with an 2695 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ORIGINATOR 2696 or Value = ROUTABLE_ORIG. 2698 o Includes any address object that represents a non-routable 2699 address, associated with an Address Block TLV with Type = 2700 NBR_ADDR_TYPE and Value = ROUTABLE or Value = ROUTABLE_ORIG. 2702 o Includes any address object associated with an Address Block TLV 2703 with Type = NBR_ADDR_TYPE or Type = GATEWAY that also represents 2704 the message's originator address. 2706 o Includes any address object (including different copies of an 2707 address object, in the same or different Address Blocks) that is 2708 associated with an Address Block TLV with Type = NBR_ADDR_TYPE or 2709 Type = GATEWAY, that is also associated with more than one 2710 outgoing neighbor metric using a TLV with Type = LINK_METRIC and 2711 Type Extension = LINK_METRIC_TYPE. 2713 o Associates any address object (including different copies of an 2714 address object, in the same or different Address Blocks) with more 2715 than one single hop count value using one or more Address Block 2716 TLV(s) with Type = GATEWAY. 2718 o Associates any address object (including different copies of an 2719 address object, in the same or different Address Blocks) with 2720 Address Block TLVs with Type = NBR_ADDR_TYPE and Type = GATEWAY. 2722 A router MAY recognize additional reasons for identifying that a 2723 message is invalid. An invalid message MUST be silently discarded, 2724 without updating the router's Information Bases. 2726 16.3.2. TC Message Processing Definitions 2728 When, according to Section 14.2, a TC message is to be "processed 2729 according to its type", this means that: 2731 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2732 and Type Extension = COMPLETE, then processing according to 2733 Section 16.3.3 and then according to Section 16.3.4 is carried 2734 out. 2736 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2737 and Type Extension = INCOMPLETE, then only processing according to 2738 Section 16.3.3 is carried out. 2740 For the purposes of the TC message processing in Section 16.3.3 and 2741 Section 16.3.4: 2743 o "validity time" is calculated from a VALIDITY_TIME Message TLV in 2744 the TC message according to the specification in [RFC5497]. All 2745 information in the TC message has the same validity time. 2747 o "received ANSN" is defined as being the value of a Message TLV 2748 with Type = CONT_SEQ_NUM. 2750 o "associated metric value" is defined for any address in the TC 2751 message as being either the outgoing neighbor metric value 2752 indicated by a TLV with Type = LINK_METRIC and Type Extension = 2753 LINK_METRIC_TYPE that is associated with any address object in the 2754 TC message that is equal to that address, or as UNKNOWN_METRIC 2755 otherwise. (Note that the rules in Section 16.3.1 make this 2756 definition unambiguous.) 2758 o Comparisons of sequence numbers are carried out as specified in 2759 Section 21. 2761 16.3.3. Initial TC Message Processing 2763 The TC message is processed as follows: 2765 1. The Advertising Remote Router Set is updated according to 2766 Section 16.3.3.1. If the TC message is indicated as discarded in 2767 that processing then the following steps are not carried out. 2769 2. The Router Topology Set is updated according to Section 16.3.3.2. 2771 3. The Routable Address Topology Set is updated according to 2772 Section 16.3.3.3. 2774 4. The Attached Network Set is updated according to 2775 Section 16.3.3.4. 2777 16.3.3.1. Populating the Advertising Remote Router Set 2779 The router MUST update its Advertising Remote Router Set as follows: 2781 1. If there is an Advertising Remote Router Tuple with: 2783 * AR_orig_addr = message originator address; AND 2785 * AR_seq_number > received ANSN, 2787 then the TC message MUST be discarded. 2789 2. Otherwise: 2791 1. If there is no Advertising Remote Router Tuple such that: 2793 + AR_orig_addr = message originator address; 2795 then create an Advertising Remote Router Tuple with: 2797 + AR_orig_addr := message originator address. 2799 2. This Advertising Remote Router Tuple (existing or new) is 2800 then modified as follows: 2802 + AR_seq_number := received ANSN; 2804 + AR_time := current time + validity time. 2806 16.3.3.2. Populating the Router Topology Set 2808 The router MUST update its Router Topology Set as follows: 2810 1. For each address (henceforth advertised address) corresponding to 2811 one or more address objects with an associated Address Block TLV 2812 with Type = NBR_ADDR_TYPE and Value = ORIGINATOR or Value = 2813 ROUTABLE_ORIG, and that is not partially owned by this router, 2814 perform the following processing: 2816 1. If the associated metric is UNKNOWN_METRIC then remove any 2817 Router Topology Tuple such that: 2819 + TR_from_orig_addr = message originator address; AND 2821 + TR_to_orig_addr = advertised address, 2823 2. Otherwise if there is no Router Topology Tuple such that: 2825 + TR_from_orig_addr = message originator address; AND 2827 + TR_to_orig_addr = advertised address, 2829 then create a new Router Topology Tuple with: 2831 + TR_from_orig_addr := message originator address; 2833 + TR_to_orig_addr := advertised address. 2835 3. This Router Topology Tuple (existing or new) is then modified 2836 as follows: 2838 + TR_seq_number := received ANSN; 2840 + TR_metric := associated link metric; 2842 + TR_time := current time + validity time. 2844 16.3.3.3. Populating the Routable Address Topology Set 2846 The router MUST update its Routable Address Topology Set as follows: 2848 1. For each network address (henceforth advertised address) 2849 corresponding to one or more address objects with an associated 2850 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ROUTABLE 2851 or Value = ROUTABLE_ORIG, and that is not partially owned by this 2852 router, perform the following processing: 2854 1. If the associated metric is UNKNOWN_METRIC then remove any 2855 Routable Address Topology Tuple such that: 2857 + TA_from_orig_addr = message originator address; AND 2859 + TA_dest_addr = advertised address. 2861 2. Otherwise if there is no Routable Address Topology Tuple such 2862 that: 2864 + TA_from_orig_addr = message originator address; AND 2866 + TA_dest_addr = advertised address, 2868 then create a new Routable Address Topology Tuple with: 2870 + TA_from_orig_addr := message originator address; 2872 + TA_dest_addr := advertised address. 2874 3. This Routable Address Topology Tuple (existing or new) is 2875 then modified as follows: 2877 + TA_seq_number := received ANSN; 2879 + TA_metric := associated link metric; 2881 + TA_time := current time + validity time. 2883 16.3.3.4. Populating the Attached Network Set 2885 The router MUST update its Attached Network Set as follows: 2887 1. For each network address (henceforth attached address) 2888 corresponding to one or more address objects with an associated 2889 Address Block TLV with Type = GATEWAY, and that is not fully 2890 owned by this router, perform the following processing: 2892 1. If the associated metric is UNKNOWN_METRIC then remove any 2893 Attached Network Tuple such that: 2895 + AN_net_addr = attached address; AND 2897 + AN_orig_addr = message originator address. 2899 2. Otherwise if there is no Attached Network Tuple such that: 2901 + AN_net_addr = attached address; AND 2903 + AN_orig_addr = message originator address, 2905 then create a new Attached Network Tuple with: 2907 + AN_net_addr := attached address; 2908 + AN_orig_addr := message originator address. 2910 3. This Attached Network Tuple (existing or new) is then 2911 modified as follows: 2913 + AN_seq_number := received ANSN; 2915 + AN_dist := the Value of the associated GATEWAY TLV; 2917 + AN_metric := associated link metric; 2919 + AN_time := current time + validity time. 2921 16.3.4. Completing TC Message Processing 2923 The TC message is processed as follows: 2925 1. The Router Topology Set is updated according to Section 16.3.4.1. 2927 2. The Routable Address Topology Set is updated according to 2928 Section 16.3.4.2. 2930 3. The Attached Network Set is updated according to 2931 Section 16.3.4.3. 2933 16.3.4.1. Purging the Router Topology Set 2935 The Router Topology Set MUST be updated as follows: 2937 1. Any Router Topology Tuples with: 2939 * TR_from_orig_addr = message originator address; AND 2941 * TR_seq_number < received ANSN, 2943 MUST be removed. 2945 16.3.4.2. Purging the Routable Address Topology Set 2947 The Routable Address Topology Set MUST be updated as follows: 2949 1. Any Routable Address Topology Tuples with: 2951 * TA_from_orig_addr = message originator address; AND 2953 * TA_seq_number < received ANSN, 2955 MUST be removed. 2957 16.3.4.3. Purging the Attached Network Set 2959 The Attached Network Set MUST be updated as follows: 2961 1. Any Attached Network Tuples with: 2963 * AN_orig_addr = message originator address; AND 2965 * AN_seq_number < received ANSN, 2967 MUST be removed. 2969 17. Information Base Changes 2971 The changes described in the following sections MUST be carried out 2972 when any Information Base changes as indicated. 2974 17.1. Originator Address Changes 2976 If the router changes its originator address, then: 2978 1. If there is no Originator Tuple with: 2980 * O_orig_addr = old originator address 2982 then create an Originator Tuple with: 2984 * O_orig_addr := old originator address 2986 The Originator Tuple (existing or new) with: 2988 * O_orig_addr = new originator address 2990 is then modified as follows: 2992 * O_time := current time + O_HOLD_TIME 2994 17.2. Link State Changes 2996 The consistency of a Link Tuple MUST be maintained according to the 2997 following rules, in addition to those in [RFC6130]: 2999 o If L_status = HEARD or L_status = SYMMETRIC, then L_in_metric MUST 3000 be set (by a process outside this specification). 3002 o If L_status != SYMMETRIC, then set L_mpr_selector := false. 3004 o If L_out_metric = UNKNOWN_METRIC, then L_status MUST NOT equal 3005 SYMMETRIC; set L_SYM_time := expired if this would otherwise be 3006 the case. 3008 17.3. Neighbor State Changes 3010 The consistency of a Neighbor Tuple MUST be maintained according to 3011 the following rules, in addition to those in [RFC6130]: 3013 1. If N_symmetric = true, then N_in_metric MUST equal the minimum 3014 value of all L_in_metric of corresponding Link Tuples with 3015 L_status = SYMMETRIC and L_in_metric != UNKNOWN_METRIC. If there 3016 are no such Link Tuples then N_in_metric MUST equal 3017 UNKNOWN_METRIC. 3019 2. If N_symmetric = true, then N_out_metric MUST equal the minimum 3020 value of all L_out_metric of corresponding Link Tuples with 3021 L_status = SYMMETRIC and L_out_metric != UNKNOWN_METRIC. If 3022 there are no such Link Tuples then N_out_metric MUST equal 3023 UNKNOWN_METRIC. 3025 3. If N_symmetric = false, then N_flooding_mpr, N_routing_mpr, 3026 N_mpr_selector and N_advertised MUST all be equal to false. 3028 4. If N_mpr_selector = true, then N_advertised MUST be equal to 3029 true. 3031 5. If N_symmetric = true, N_out_metric != UNKNOWN_METRIC and 3032 N_mpr_selector = false, then a router MAY select N_advertised = 3033 true or N_advertised = false. The more neighbors that are 3034 advertised, the larger TC messages become, but the more 3035 redundancy is available for routing. A router SHOULD consider 3036 the nature of its network in making such a decision, and SHOULD 3037 avoid unnecessary changes in advertising status, which may result 3038 both in additional TC messages having to be sent by its 3039 neighbors, and in unnecessary changes to routing, which will have 3040 similar effects to other forms of topology changes in the MANET. 3042 17.4. Advertised Neighbor Changes 3044 The router MUST increment the ANSN in the Neighbor Information Base 3045 whenever: 3047 1. Any Neighbor Tuple changes its N_advertised value, or any 3048 Neighbor Tuple with N_advertised = true is removed. 3050 2. Any Neighbor Tuple with N_advertised = true changes its 3051 N_orig_addr, or has any routable address is added to or removed 3052 from N_neighbor_addr_list. 3054 3. Any Neighbor Tuple with N_advertised = true has N_out_metric 3055 changed. 3057 4. There is any change to the Local Attached Network Set. 3059 17.5. Advertising Remote Router Tuple Expires 3061 The Router Topology Set, the Routable Address Topology Set and the 3062 Attached Network Set MUST be changed when an Advertising Remote 3063 Router Tuple expires (AR_time is reached). The following changes are 3064 required before the Advertising Remote Router Tuple is removed: 3066 1. All Router Topology Tuples with: 3068 * TR_from_orig_addr = AR_orig_addr of the Advertising Remote 3069 Router Tuple 3071 are removed. 3073 2. All Routable Address Topology Tuples with: 3075 * TA_from_orig_addr = AR_orig_addr of the Advertising Remote 3076 Router Tuple 3078 are removed. 3080 3. All Attached Network Tuples with: 3082 * AN_orig_addr = AR_orig_addr of the Advertising Remote Router 3083 Tuple 3085 are removed. 3087 17.6. Neighborhood Changes and MPR Updates 3089 The sets of symmetric 1-hop neighbors selected as flooding MPRs and 3090 routing MPRs MUST satisfy the conditions defined in Section 18. To 3091 ensure this: 3093 1. The set of flooding MPRs of a router MUST be recalculated if: 3095 * A Link Tuple is added with L_status = SYMMETRIC and 3096 L_out_metric != UNKNOWN_METRIC, OR; 3098 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3099 UNKNOWN_METRIC is removed, OR; 3101 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3102 UNKNOWN_METRIC changes to having L_status = HEARD, L_status = 3103 LOST or L_out_metric = UNKNOWN_METRIC, OR; 3105 * A Link Tuple with L_status = HEARD or L_status = LOST changes 3106 to having L_status = SYMMETRIC and L_out_metric != 3107 UNKNOWN_METRIC, OR; 3109 * The flooding MPR selection process uses metric values (see 3110 Section 18.4) and the L_out_metric of any Link Tuple with 3111 L_status = SYMMETRIC changes, OR; 3113 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3114 true and N_out_metric != UNKNOWN_METRIC changes from 3115 WILL_NEVER to any other value, OR; 3117 * The N_will_flooding of a Neighbor Tuple with N_flooding_mpr = 3118 true changes to WILL_NEVER from any other value, OR; 3120 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3121 true, N_out_metric != UNKNOWN_METRIC, and N_flooding_mpr = 3122 false changes to WILL_ALWAYS from any other value, OR; 3124 * A 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC is added or 3125 removed, OR; 3127 * The flooding MPR selection process uses metric values (see 3128 Section 18.4) and the N2_out_metric of any 2-Hop Tuple 3129 changes. 3131 2. Otherwise, the set of flooding MPRs of a router MAY be 3132 recalculated if the N_will_flooding of a Neighbor Tuple with 3133 N_symmetric = true changes in any other way; it SHOULD be 3134 recalculated if N_flooding_mpr = false and this is an increase in 3135 N_will_flooding or if N_flooding_mpr = true and this is a 3136 decrease in N_will_flooding. 3138 3. The set of routing MPRs of a router MUST be recalculated if: 3140 * A Neighbor Tuple is added with N_symmetric = true and 3141 N_in_metric != UNKNOWN_METRIC, OR; 3143 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3144 UNKNOWN_METRIC is removed, OR; 3146 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3147 UNKNOWN_METRIC changes to having N_symmetric = false, OR; 3149 * A Neighbor Tuple with N_symmetric = false changes to having 3150 N_symmetric = true and N_in_metric != UNKNOWN_METRIC, OR; 3152 * The N_in_metric of any Neighbor Tuple with N_symmetric = true 3153 changes, OR; 3155 * The N_will_routing of a Neighbor Tuple with N_symmetric = true 3156 and N_in_metric != UNKNOWN_METRIC changes from WILL_NEVER to 3157 any other value, OR; 3159 * The N_will_routing of a Neighbor Tuple with N_routing_mpr = 3160 true changes to WILL_NEVER from any other value, OR; 3162 * The N_will_routing of a Neighbor Tuple with N_symmetric = 3163 true, N_in_metric != UNKNOWN_METRIC and N_routing_mpr = false 3164 changes to WILL_ALWAYS from any other value, OR; 3166 * A 2-Hop Tuple with N2_in_metric != UNKNOWN_METRIC is added or 3167 removed, OR; 3169 * The N2_in_metric of any 2-Hop Tuple changes. 3171 4. Otherwise, the set of routing MPRs of a router MAY be 3172 recalculated if the N_will_routing of a Neighbor Tuple with 3173 N_symmetric = true changes in any other way; it SHOULD be 3174 recalculated if N_routing_mpr = false and this is an increase in 3175 N_will_routing or if N_routing_mpr = true and this is a decrease 3176 in N_will_routing. 3178 If either set of MPRs of a router is recalculated, this MUST be as 3179 described in Section 18. 3181 17.7. Routing Set Updates 3183 The Routing Set MUST be updated, as described in Section 19, when 3184 changes in the Local Information Base, the Neighborhood Information 3185 Base or the Topology Information Base indicate a change (including of 3186 any potentially used outgoing neighbor metric values) of the known 3187 symmetric links and/or attached networks in the MANET, hence changing 3188 the Topology Graph. It is sufficient to consider only changes which 3189 affect at least one of: 3191 o The Local Interface Set for an OLSRv2 interface, if the change 3192 removes any network address in an I_local_iface_addr_list. In 3193 this case, unless the OLSRv2 interface is removed, it may not be 3194 necessary to do more than replace such network addresses, if used, 3195 by an alternative network address from the same 3196 I_local_iface_addr_list. 3198 o The Local Attached Set, if the change removes any AL_net_addr 3199 which is also an AN_net_addr. In this case it may not be 3200 necessary to do more than add Routing Tuples with R_dest_addr 3201 equal to that AN_net_addr. 3203 o The Link Set of any OLSRv2 interface, considering only Link Tuples 3204 which have, or just had, L_status = SYMMETRIC and L_out_metric != 3205 UNKNOWN_METRIC (including removal of such Link Tuples). 3207 o The Neighbor Set of the router, considering only Neighbor Tuples 3208 that have, or just had, N_symmetric = true and N_out_metric != 3209 UNKNOWN_METRIC, and do not have N_orig_addr = unknown. 3211 o The 2-Hop Set of any OLSRv2 interface, if used in the creation of 3212 the Routing Set, and if the change affects any 2-Hop Tuples with 3213 N2_out_metric != UNKNOWN_METRIC. 3215 o The Router Topology Set of the router. 3217 o The Routable Address Topology Set of the router. 3219 o The Attached Network Set of the router. 3221 18. Selecting MPRs 3223 Each router MUST select, from among its willing symmetric 1-hop 3224 neighbors, two subsets of these routers, as flooding and routing 3225 MPRs. This selection is recorded in the router's Neighbor Set, and 3226 reported in the router's HELLO messages. Routers MAY select their 3227 MPRs by any process that satisfies the conditions which follow, which 3228 may, but need not, use the organization of the data described. 3229 Routers can freely interoperate whether they use the same or 3230 different MPR selection algorithms. 3232 Only flooding MPRs forward control messages flooded through the 3233 MANET, thus effecting a flooding reduction, an optimization of the 3234 flooding mechanism, known as MPR flooding. Routing MPRs are used to 3235 effect a topology reduction in the MANET. (If no such reduction is 3236 required then a router can select all of its relevant neighbors as 3237 routing MPRs.) Consequently, while it is not essential that these 3238 two sets of MPRs are minimal, keeping the numbers of MPRs small 3239 ensures that the overhead of this protocol is kept to a minimum. 3241 18.1. Overview 3243 MPRs are selected according to the following steps, defined in the 3244 following sections: 3246 o A data structure known as a Neighbor Graph is defined. 3248 o The properties of an MPR Set derived from a Neighbor Graph are 3249 defined. Any algorithm that creates an MPR Set that satisfies 3250 these properties is a valid MPR selection algorithm. An example 3251 algorithm that creates such an MPR Set is given in Appendix A. 3253 o How to create a Neighbor Graph for each interface based on the 3254 corresponding Interface Information Base is defined, and how to 3255 combine the resulting MPR Sets to determine the router's flooding 3256 MPRs and record those in the router's Neighbor Set. 3258 o How to create a single Neighbor Graph based on all Interface 3259 Information Bases and the Neighbor Information Base is defined, 3260 and how to record the resulting MPR Set as the router's routing 3261 MPRs in the router's Neighbor Set. 3263 o A specification as to when MPRs MUST be calculated is given. 3265 When a router selects its MPRs it MAY consider any characteristics of 3266 its neighbors that it is aware of. In particular it SHOULD consider 3267 the willingness of the neighbor, as recorded by the corresponding 3268 N_will_flooding or N_will_routing value, as appropriate, preferring 3269 neighbors with higher values. (Note that willingness values equal to 3270 WILL_NEVER and WILL_ALWAYS are always considered, as described.) 3271 However, a router MAY consider other characteristics to have a 3272 greater significance. 3274 Each router MAY select its flooding and routing MPRs independently 3275 from each other, or coordinate its selections. A router MAY make its 3276 MPR selections independently of the MPR selection by other routers, 3277 or it MAY, for example, give preference to routers that either are, 3278 or are not, already selected as MPRs by other routers. 3280 18.2. Neighbor Graph 3282 A Neighbor Graph is a structure defined here as consisting of sets N1 3283 and N2 and some associated metric and willingness values. Elements 3284 of set N1 represent willing symmetric 1-hop neighbors, and elements 3285 of set N2 represent addresses of a symmetric 2-hop neighbor. 3287 A Neighbor Graph has the following properties: 3289 o It contains two disjoint sets N1 and N2. 3291 o For each element x in N1 there is an associated willingness value 3292 W(x) such that WILL_NEVER < W(x) <= WILL_ALWAYS. 3294 o For each element x in N1 there is an associated metric d1(x) > 0. 3296 o For some elements y in N2 there is an associated metric d1(y) > 0. 3297 (Other elements y in N2 have undefined d1(y), this may be 3298 considered to be infinite.) 3300 o For each element x in N1 there is a subset N2(x) of elements of 3301 N2; this subset may be empty. For each x in N1 and each y in 3302 N2(x) there is an associated metric d2(x,y) > 0. (For other x in 3303 N1 and y in N2, d2(x,y) is undefined, and may be considered 3304 infinite.) 3306 o N2 is equal to the union of all the N2(x) for all x in N1, i.e. 3307 for each y in N2 there is at least one x in N1 such that y is in 3308 N2(x). 3310 It is convenient to also define: 3312 o For each y in N2 the set N1(y) that contains x in N1 if and only 3313 if y is in N2(x). From the final property above, N1(y) is not 3314 empty. 3316 o For each x in N1 and y in N2, if d2(x,y) is defined then d(x,y) := 3317 d1(x)+d2(x,y), otherwise d(x,y) is not defined. (Thus d(x,y) is 3318 defined if y is in N2(x), or equivalently if x is in N1(y).) 3320 o For any subset S of N1, and for each y in N2, the metric d(y,S) is 3321 the minimum value of d1(y), if defined, and of all d(x,y) for x in 3322 N1(y) and in S. If there are no such metrics to take the minimum 3323 value of, then d(y,S) is undefined (may be considered to be 3324 infinite). From the final property above, d(y,N1) is defined for 3325 all y. 3327 18.3. MPR Properties 3329 Given a Neighbor Graph as defined in Section 18.2, an MPR Set for 3330 that Neighbor Graph is a subset M of the set N1 that satisfies the 3331 following properties: 3333 o If x in N1 has W(x) = WILL_ALWAYS then x is in M. 3335 o For any y in N2 that does not have a defined d1(y), there is at 3336 least one element in M that is also in N1(y). This is equivalent 3337 to the requirement that d(y,M) is defined. 3339 o For any y in N2, d(y,M) = d(y,N1). 3341 These two properties correspond first to that the MPR Set consists of 3342 a set of symmetric 1-hop neighbors that cover all the symmetric 2-hop 3343 neighbors, and second that they do so retaining a minimum distance 3344 route (1-hop, if present, or 2-hop) to each symmetric 2-hop neighbor. 3346 Note that if M is an MPR Set, then so is any subset of N1 that 3347 contains M, and also that N1 is always an MPR Set. An MPR Set may be 3348 empty, but cannot be empty if N2 contains any elements y that do not 3349 have a defined d1(y). 3351 18.4. Flooding MPRs 3353 Whenever flooding MPRs are to be calculated, an implementation MUST 3354 determine and record a set of flooding MPRs that is equivalent to one 3355 calculated as described in this section. 3357 The calculation of flooding MPRs need not use link metrics, or 3358 equivalently may use link metrics with a fixed value, here taken to 3359 be 1. However, links with unknown metric (L_out_metric = 3360 UNKNOWN_METRIC) MUST NOT be used even if link metrics are otherwise 3361 not used. 3363 Routers MAY make individual decisions as to whether to use link 3364 metrics for the calculation of flooding MPRs. A router MUST use the 3365 same approach to the choice of whether to use link metrics for all 3366 links, i.e., in the cases indicated by A or B, the same choice MUST 3367 be made in each case. 3369 For each OLSRv2 interface (the "current interface") define a Neighbor 3370 Graph as defined in Section 18.2 according to the following: 3372 o Define a reachable Link Tuple to be a Link Tuple in the Link Set 3373 for the current interface with L_status = SYMMETRIC and 3374 L_out_metric != UNKNOWN_METRIC. 3376 o Define an allowed Link Tuple to be a reachable Link Tuple whose 3377 corresponding Neighbor Tuple has N_will_flooding > WILL_NEVER. 3379 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3380 for the current interface for which N2_out_metric != 3381 UNKNOWN_METRIC and there is an allowed Link Tuple with 3382 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 3384 o Define an element of N1 for each allowed Link Tuple. This then 3385 defines the corresponding Link Tuple for each element of N1 and 3386 the corresponding Neighbor Tuple for each element of N1, being the 3387 Neighbor Tuple corresponding to that Link Tuple. 3389 o For each element x in N1, define W(x) := N_will_flooding of the 3390 corresponding Neighbor Tuple. 3392 o For each element x in N1, define d1(x) as either: 3394 A. L_out_metric of the corresponding Link Tuple, OR; 3396 B. 1. 3398 o Define an element of N2 for each network address that is the 3399 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3400 defines the corresponding address for each element of N2. 3402 o For each element y in N2, if the corresponding address is in the 3403 N_neighbor_addr_list of a Neighbor Tuple that corresponds to one 3404 or more reachable Link Tuples, then define d1(y) as either: 3406 A. the minimum value of the L_out_metric of those Link Tuples, 3407 OR; 3409 B. 1. 3411 Otherwise d1(y) is not defined. In the latter case, where d1(y) 3412 := 1, all such y in N2 may instead be removed from N2. 3414 o For each element x in N1, define N2(x) as the set of elements y in 3415 N2 whose corresponding address is the N2_2hop_addr of an allowed 3416 2-Hop Tuple that has N2_neighbor_iface_addr_list = 3417 L_neighbor_iface_addr_list of the Link Tuple corresponding to x. 3418 For all such x and y, define d2(x,y) as either: 3420 A. N2_out_metric of that 2-Hop Tuple, OR; 3422 B. 1. 3424 It is up to an implementation to decide how to label each element of 3425 N1 or N2. For example an element of N1 may be labeled with one or 3426 more addresses from the corresponding L_neighbor_iface_addr_list, or 3427 with a pointer or reference to the corresponding Link Tuple. 3429 Using these Neighbor Graphs, flooding MPRs are selected and recorded 3430 by: 3432 o For each OLSRv2 interface, determine an MPR Set as specified in 3433 Section 18.3. 3435 o A Neighbor Tuple represents a flooding MPR and has N_flooding_mpr 3436 := true (otherwise N_flooding_mpr := false) if and only if that 3437 Neighbor Tuple corresponds to an element in an MPR Set created for 3438 any interface as described above. That is, the overall set of 3439 flooding MPRs is the union of the sets of flooding MPRs for all 3440 OLSRv2 interfaces. 3442 A router MAY select its flooding MPRs for each OLSRv2 interface 3443 independently, or it MAY coordinate its MPR selections across its 3444 OLSRv2 interfaces, as long as the required condition is satisfied for 3445 each OLSRv2 interface. One such coordinated approach is to process 3446 the OLSRv2 interfaces sequentially, and for each OLSRv2 interface 3447 start with flooding MPRs selected (and not removable) if the neighbor 3448 has been already selected as an MPR for an OLSRv2 interface that has 3449 already been processed. The algorithm specified in Appendix A can be 3450 used in this way. 3452 18.5. Routing MPRs 3454 Whenever routing MPRs are to be calculated, an implementation MUST 3455 determine and record a set of routing MPRs that is equivalent to one 3456 calculated as described in this section. 3458 Define a single Neighbor Graph as defined in Section 18.2 according 3459 to the following: 3461 o Define a reachable Neighbor Tuple to be a Neighbor Tuple with 3462 N_symmetric = true and N_in_metric != UNKNOWN_METRIC. 3464 o Define an allowed Neighbor Tuple to be a reachable Neighbor Tuple 3465 with N_will_routing > WILL_NEVER. 3467 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3468 for any OLSRv2 interface with N2_in_metric != UNKNOWN_METRIC and 3469 for which there is an allowed Neighbor Tuple with 3470 N_neighbor_addr_list containing N2_neighbor_iface_addr_list. 3472 o Define an element of N1 for each allowed Neighbor Tuple. This 3473 then defines the corresponding Neighbor Tuple for each element of 3474 N1. 3476 o For each element x in N1, define W(x) := N_will_routing of the 3477 corresponding Neighbor Tuple. 3479 o For each element x in N1, define d1(x) := N_in_metric of the 3480 corresponding Neighbor Tuple. 3482 o Define an element of N2 for each network address that is the 3483 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3484 defines the corresponding address for each element of N2. 3486 o For each element y in N2, if the corresponding address is in the 3487 N_neighbor_addr_list of a reachable Neighbor Tuple, then define 3488 d1(y) to be the N_in_metric of that Neighbor Tuple, otherwise 3489 d1(y) is not defined. 3491 o For each element x in N1, define N2(x) as the set of elements y in 3492 N2 whose corresponding address is the N2_2hop_addr of an allowed 3493 2-Hop Tuple that has N2_neighbor_iface_addr_list contained in 3494 N_neighbor_addr_list of the Neighbor Tuple corresponding to x. 3495 For all such x and y, define d2(x,y) := N2_out_metric of that 3496 2-Hop Tuple. 3498 It is up to an implementation to decide how to label each element of 3499 N1 or N2. For example an element of N1 may be labeled with one or 3500 more addresses from the corresponding N_neighbor_addr_list, or with a 3501 pointer or reference to the corresponding Neighbor Tuple. 3503 Using these Neighbor Graphs, routing MPRs are selected and recorded 3504 according to the following: 3506 o Determine an MPR Set as specified in Section 18.3. 3508 o A Neighbor Tuple represents a routing MPR and has N_routing_mpr := 3509 true (otherwise N_routing_mpr := false) if and only if that 3510 Neighbor Tuple corresponds to an element in the MPR Set created as 3511 described above. 3513 18.6. Calculating MPRs 3515 A router MUST recalculate each of its sets of MPRs whenever the 3516 currently selected set of MPRs does not still satisfy the required 3517 conditions. It MAY recalculate its MPRs if the current set of MPRs 3518 is still valid, but could be more efficient. Sufficient conditions 3519 to recalculate a router's sets of MPRs are given in Section 17.6. 3521 19. Routing Set Calculation 3523 The Routing Set of a router is populated with Routing Tuples that 3524 represent paths from that router to all destinations in the network. 3525 These paths are calculated based on the Network Topology Graph, which 3526 is constructed from information in the Information Bases, obtained 3527 via HELLO and TC message exchange. 3529 Changes to the Routing Set do not require any messages to be 3530 transmitted. The state of the Routing Set SHOULD, however, be 3531 reflected in the IP routing table by adding and removing entries from 3532 that routing table as appropriate. Only appropriate Routing Tuples 3533 (in particular only those that represent local links or paths to 3534 routable addresses) need be reflected in the IP routing table. 3536 19.1. Network Topology Graph 3538 The Network Topology Graph is formed from information from the 3539 router's Local Interface Set, Link Sets for OLSRv2 interfaces, 3540 Neighbor Set, Router Topology Set, Routable Address Topology Set and 3541 Attached Network Set. The Network Topology Graph MAY also use 3542 information from the router's 2-Hop Sets for OLSRv2 interfaces. The 3543 Network Topology Graph forms the router's topological view of the 3544 network in form of a directed graph. Each edge in that graph has a 3545 metric value. The Network Topology Graph has a "backbone" (within 3546 which minimum total metric routes will be constructed) containing the 3547 following edges: 3549 o Edges X -> Y for all possible Y, and one X per Y, such that: 3551 * Y is the N_orig_addr of a Neighbor Tuple; AND 3553 * N_orig_addr is not unknown; 3555 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3556 AND 3558 * There is a Link Tuple with L_status = SYMMETRIC and 3559 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3560 and this Local Interface Tuple correspond to it. A network 3561 address from L_neighbor_iface_addr_list will be denoted R in 3562 this case. 3564 It SHOULD be preferred, where possible, to select R = S and X from 3565 the Local Interface Tuple corresponding to the Link Tuple from 3566 which R was selected. The metric for such an edge is the 3567 corresponding N_out_metric. 3569 o All edges W -> U such that: 3571 * W is the TR_from_orig_addr of a Router Topology Tuple; AND 3573 * U is the TR_to_orig_addr of the same Router Topology Tuple. 3575 The metric of such an edge is the corresponding TR_metric. 3577 The Network Topology Graph is further "decorated" with the following 3578 edges. If a network address S, V, Z or T equals a network address Y 3579 or W, then the edge terminating in the network address S, V, Z or T 3580 MUST NOT be used in any path. 3582 o Edges X -> S for all possible S, and one X per S, such that: 3584 * S is in the N_neighbor_addr_list of a Neighbor Tuple; AND 3586 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3587 AND 3589 * There is a Link Tuple with L_status = SYMMETRIC and 3590 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3591 and this Local Interface Tuple correspond to it. A network 3592 address from L_neighbor_iface_addr_list will be denoted R in 3593 this case. 3595 It SHOULD be preferred, where possible, to select R = S and X from 3596 the Local Interface Tuple corresponding to the Link Tuple from 3597 which R was selected. The metric for such an edge is the 3598 corresponding N_out_metric. 3600 o All edges W -> V such that: 3602 * W is the TA_from_orig_addr of a Routable Address Topology 3603 Tuple; AND 3605 * V is the TA_dest_addr of the same Routable Address Topology 3606 Tuple. 3608 The metric for such an edge is the corresponding TA_metric. 3610 o All edges W -> T such that: 3612 * W is the AN_orig_addr of an Attached Network Tuple; AND 3614 * T is the AN_net_addr of the same Attached Network Tuple. 3616 The metric for such an edge is the corresponding AN_metric. 3618 o (OPTIONAL) All edges Y -> Z such that: 3620 * Z is a routable address and is the N2_2hop_addr of a 2-Hop 3621 Tuple with N2_out_metric != UNKNOWN_METRIC; AND 3623 * Y is the N_orig_addr of the corresponding Neighbor Tuple; AND 3625 * This Neighbor Tuple has N_will_routing not equal to WILL_NEVER. 3627 A path terminating with such an edge MUST NOT be used in 3628 preference to any other path. The metric for such an edge is the 3629 corresponding N2_out_metric. 3631 Any part of the Topology Graph which is not connected to a local 3632 network address X is not used. Only one selection X SHOULD be made 3633 from each I_local_iface_addr_list, and only one selection R SHOULD be 3634 made from any L_neighbor_iface_addr_list. All edges have a hop count 3635 of 1, except edges W -> T that have a hop count of the corresponding 3636 value of AN_dist. 3638 19.2. Populating the Routing Set 3640 The Routing Set MUST contain the shortest paths for all destinations 3641 from all local OLSRv2 interfaces using the Network Topology Graph. 3642 This calculation MAY use any algorithm, including any means of 3643 choosing between paths of equal total metric. (In the case of two 3644 paths of equal total metric but differing hop counts, the path with 3645 the lower hop count SHOULD be used.) 3647 Using the notation of Section 19.1, initially "backbone" paths using 3648 only edges X -> Y and W -> U need be constructed (using a minimum 3649 distance algorithm). Then paths using only a final edge of the other 3650 types may be added. These MUST NOT replace backbone paths with the 3651 same destination (and paths terminating in an edge Y -> Z SHOULD NOT 3652 replace paths with any other form of terminating edge). 3654 Each path will correspond to a Routing Tuple. These will be of two 3655 types. The first type will represent single edge paths, of type X -> 3656 S or X -> Y, by: 3658 o R_local_iface_addr := X; 3660 o R_next_iface_addr := R; 3662 o R_dest_addr := S or Y; 3664 o R_dist := 1; 3666 o R_metric := edge metric, 3668 where R is as defined in Section 19.1 for these types of edges. 3670 The second type will represent a multiple edge path, which will 3671 always have first edge of type X -> Y, and will have final edge of 3672 type W -> U, W -> V, W -> T or Y -> Z. The Routing Tuple will be: 3674 o R_local_iface_addr := X; 3676 o R_next_iface_addr := Y; 3677 o R_dest_addr := U, V, T or Z; 3679 o R_dist := the total hop count of all edges in the path; 3681 o R_metric := the total metric of all edges in the path. 3683 Finally, Routing Tuples of the second type whose R_dest_addr is not 3684 routable MAY be discarded. 3686 An example algorithm for calculating the Routing Set of a router is 3687 given in Appendix B. 3689 20. Proposed Values for Parameters 3691 This protocol uses all parameters defined in [RFC6130] and additional 3692 parameters and defined in this specification. All but one 3693 (RX_HOLD_TIME) of these additional parameters are router parameters 3694 as defined in [RFC6130]. The proposed values of the additional 3695 parameters defined in the following sections are appropriate to the 3696 case where all parameters (including those defined in [RFC6130]) have 3697 a single value. Proposed values for parameters defined in [RFC6130] 3698 are given in that specification. 3700 20.1. Local History Time Parameters 3702 o O_HOLD_TIME := 30 seconds 3704 20.2. Message Interval Parameters 3706 o TC_INTERVAL := 5 seconds 3708 o TC_MIN_INTERVAL := TC_INTERVAL/4 3710 20.3. Advertised Information Validity Time Parameters 3712 o T_HOLD_TIME := 3 x TC_INTERVAL 3714 o A_HOLD_TIME := T_HOLD_TIME 3716 20.4. Received Message Validity Time Parameters 3718 o RX_HOLD_TIME := 30 seconds 3720 o P_HOLD_TIME := 30 seconds 3722 o F_HOLD_TIME := 30 seconds 3724 20.5. Jitter Time Parameters 3726 o TP_MAXJITTER := HP_MAXJITTER 3728 o TT_MAXJITTER := HT_MAXJITTER 3730 o F_MAXJITTER := TT_MAXJITTER 3732 20.6. Hop Limit Parameter 3734 o TC_HOP_LIMIT := 255 3736 20.7. Willingness Parameter 3738 o WILL_FLOODING := WILL_DEFAULT 3740 o WILL_ROUTING := WILL_DEFAULT 3742 21. Sequence Numbers 3744 Sequence numbers are used in this specification for the purpose of 3745 discarding "old" information, i.e., messages received out of order. 3746 However with a limited number of bits for representing sequence 3747 numbers, wrap-around (that the sequence number is incremented from 3748 the maximum possible value to zero) will occur. To prevent this from 3749 interfering with the operation of this protocol, the following MUST 3750 be observed when determining the ordering of sequence numbers. 3752 The term MAXVALUE designates in the following one more than the 3753 largest possible value for a sequence number. For a 16 bit sequence 3754 number (as are those defined in this specification) MAXVALUE is 3755 65536. 3757 The sequence number S1 is said to be "greater than" the sequence 3758 number S2 if: 3760 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 3762 o S2 > S1 AND S2 - S1 > MAXVALUE/2 3764 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 3765 cannot be determined. In this case, which should not occur, either 3766 ordering may be assumed. 3768 Thus when comparing two messages, it is possible - even in the 3769 presence of wrap-around - to determine which message contains the 3770 most recent information. 3772 22. Extensions 3774 An extension to this protocol will need to interact with this 3775 specification, and possibly also with [RFC6130]. This protocol is 3776 designed to permit such interactions, in particular: 3778 o Through accessing, and possibly extending, the information in the 3779 Information Bases. All updates to the elements specified in this 3780 specification are subject to the constraints specified in 3781 [RFC6130] and Appendix D. 3783 o Through accessing an outgoing message prior to it being 3784 transmitted over any OLSRv2 interface, and to add information to 3785 it as specified in [RFC5444]. This MAY include Message TLVs 3786 and/or network addresses with associated Address Block TLVs. 3787 (Network addresses without new associated TLVs SHOULD NOT be added 3788 to messages.) This may, for example, be to allow a security 3789 protocol, as suggested in Section 23, to add a TLV containing a 3790 cryptographic signature to the message. 3792 o Through accessing an incoming message, and potentially discarding 3793 it prior to processing by this protocol. This may, for example, 3794 allow a security protocol, as suggested in Section 23, to perform 3795 verification of message signatures and prevent processing and/or 3796 forwarding of unverifiable messages by this protocol. 3798 o Through accessing an incoming message after it has been completely 3799 processed by this protocol. In particular, this may allow a 3800 protocol which has added information, by way of inclusion of 3801 appropriate TLVs, or of network addresses associated with new 3802 TLVs, access to such information after appropriate updates have 3803 been recorded in the Information Bases in this protocol. 3805 o Through requesting that a message be generated at a specific time. 3806 In that case, message generation MUST still respect the 3807 constraints in [RFC6130] and Section 5.4.3. 3809 23. Security Considerations 3811 As a proactive routing protocol, this protocol is a potential target 3812 for various attacks. This section presents the envisioned security 3813 architecture for OLSRv2, and gives guidelines on how to provide 3814 integrity, confidentiality, and integration into external routing 3815 domains. 3817 23.1. Security Architecture 3819 OLSRv2 integrates into the architecture specified in Appendix A of 3820 [RFC5444], in [RFC5498], and in Section 16 of [RFC6130], the latter 3821 by using and extending its messages and Information Bases. 3823 As part of this architecture, OLSRv2, and NHDP, recognize that there 3824 may be external reasons for rejecting messages that would be 3825 considered "badly formed" or "insecure", e.g., if a digital signature 3826 included in a message by an external mechanism cannot be verified. 3827 This architecture allows options as to whether and how to implement 3828 security features, reflecting the situation that MANET routing 3829 protocol deployment domains have varying security requirements, 3830 ranging from "practically unbreakable" to "virtually none". This 3831 approach allows MANET routing protocol specifications to remain 3832 generic, with extensions to them, and/or extensions to the 3833 multiplexing and demultiplexing process described in Appendix A of 3834 [RFC5444], providing security mechanisms appropriate to a given 3835 deployment domain. 3837 The following sections provide guidelines how to provide integrity, 3838 confidentiality, and integration with external routing domains in 3839 such extensions. 3841 23.2. Integrity 3843 Each router injects topological information into the network by 3844 transmitting HELLO messages and, for some routers, also TC messages. 3845 If some routers for some reason, malice or malfunction, inject 3846 invalid control traffic, network integrity may be compromised. 3847 Therefore, message, or packet, authentication is recommended. 3849 Different such situations may occur, for example: 3851 1. A router generates TC messages, advertising links to non-neighbor 3852 routers; 3854 2. A router generates TC messages, pretending to be another router; 3856 3. A router generates HELLO messages, advertising non-neighbor 3857 routers; 3859 4. A router generates HELLO messages, pretending to be another 3860 router; 3862 5. A router forwards altered control messages; 3863 6. A router does not forward control messages; 3865 7. A router does not select multipoint relays correctly; 3867 8. A router forwards broadcast control messages unaltered, but does 3868 not forward unicast data traffic; 3870 9. A router "replays" previously recorded control traffic from 3871 another router. 3873 Authentication of the originator router for control messages (for 3874 situations 2, 4 and 5), and of the individual links announced in the 3875 control messages (for situations 1 and 3), may be used as a 3876 countermeasure. However to prevent routers from repeating old (and 3877 correctly authenticated) information (situation 9) temporal 3878 information (a timestamp) is required, allowing a router to 3879 positively identify such replayed messages. 3881 In general, digital signatures and other required security 3882 information may be transmitted within the HELLO and TC messages, or 3883 within a packet header, using the TLV mechanism. Either option 3884 permits "secured" and "unsecured" routers to coexist in the same 3885 network, if desired. 3887 An important consideration is that all control messages (HELLO 3888 messages and TC messages) are transmitted to all routers in the 1-hop 3889 neighborhood and some control messages (TC messages) are flooded to 3890 all routers in the network. This is done in a packet that is 3891 transmitted to all routers in the 1-hop neighborhood, the current set 3892 of which may not be known. Thus, a control message, or packet, used 3893 by this protocol is always contained in a transmission destined for 3894 multiple destinations, and it is important that the authentication 3895 mechanism employed permits any receiving router to validate the 3896 authenticity of a message or packet. 3898 [RFC6622] specifies a common exchange format for cryptographic 3899 information in the form of Packet TLVs, Message TLVs, and Address 3900 Block TLVs, as specified in [RFC5444]. These may be used (and 3901 shared) among MANET routing protocol security extensions. In 3902 particular, [RFC6622] specifies the format of TLVs for containing 3903 Integrity Check Values (ICVs), i.e., signatures, for providing 3904 integrity, as well as TLVs for containing temporal information for 3905 preventing replay attacks. [RFC6622] specifies registries for using 3906 different ciphers and formats of temporal information. Failure to 3907 verify an ICV included can be used as a reason to reject an incoming 3908 message or packet as "valid", according to Section 12.1 of [RFC6130], 3909 and according to Section 16.3.1 of this specification, when using the 3910 multiplexing and demultiplexing process described in Appendix A of 3912 [RFC5444]. 3914 Any security extension that uses [RFC6622] must specify how to insert 3915 IVCs in generated messages, how to verify incoming messages, and to 3916 reject "insecure" messages (i.e., messages without an ICV or with an 3917 ICV that cannot be verified) when operating in a secure mode. 3918 Different MANET deployments may, as a result of their purpose for 3919 which they are used and the possibility and nature of their 3920 configuration, require different ICV algorithms and timestamps, and 3921 thus a security extension may use any of the different options 3922 provided in [RFC6622]. 3924 23.3. Confidentiality 3926 OLSRv2 periodically MPR floods topological information to all routers 3927 in the network. Hence, if used in an unprotected network, in 3928 particular an unprotected wireless network, the network topology is 3929 revealed to anyone who successfully listens to the control messages. 3930 This information may serve an attacker to acquire details about the 3931 topology, and therefore to initiate more effective attacks against 3932 routers in the routing domain e.g., by spoofing addresses of routers 3933 in the network and attracting traffic for these addresses. Note that 3934 this is independent of the data traffic, and purely protects the 3935 control traffic, i.e., information about the network topology. 3937 In situations where the confidentiality of the network topology is of 3938 importance, regular cryptographic techniques, such as use of OLSRv2 3939 multicast control packets encrypted using IPsec (e.g., with a shared 3940 secret key), can be applied to ensure that control traffic can be 3941 read and interpreted by only those authorized to do so. 3942 Alternatively, a security extension may specify a mechanism to 3943 provide confidentiality for control messages and/or packets. 3944 However, unless the information about the network topology itself is 3945 confidential, integrity of control messages (as specified in 3946 Section 23.2) is sufficient to admit only trusted routers (i.e. 3947 routers with valid credentials) to the network. 3949 23.4. Interaction with External Routing Domains 3951 This protocol provides a basic mechanism for injecting external 3952 routing information into this protocol's routing domain. Routing 3953 information can also be extracted from this protocol's Information 3954 Bases, in particular the Routing Set, and injected into an external 3955 routing domain, if the routing protocol governing that routing domain 3956 permits this. 3958 When operating routers connecting a routing domain using this 3959 protocol to an external routing domain, care MUST be taken not to 3960 allow potentially insecure and untrustworthy information to be 3961 injected from this routing domain to an external routing domain. 3962 Care MUST also be taken to validate the correctness of information 3963 prior to it being injected, so as to avoid polluting routing tables 3964 with invalid information. 3966 A recommended way of extending connectivity from an external routing 3967 domain to this routing domain, which is routed using this protocol, 3968 is to assign an IP prefix (under the authority of the routers/ 3969 gateways connecting this routing domain with the external routing 3970 domain) exclusively to this routing domain, and to configure the 3971 gateways to advertise routes for that IP prefix into the external 3972 routing domain. 3974 24. IANA Considerations 3976 This specification defines one Message Type, which must be allocated 3977 from the "Message Types" repository of [RFC5444], two Message TLV 3978 Types, which must be allocated from the "Message TLV Types" 3979 repository of [RFC5444], and four Address Block TLV Types, which must 3980 be allocated from the "Address Block TLV Types" repository of 3981 [RFC5444]. 3983 24.1. Expert Review: Evaluation Guidelines 3985 For the registries where an Expert Review is required, the designated 3986 expert SHOULD take the same general recommendations into 3987 consideration as are specified by [RFC5444]. 3989 24.2. Message Types 3991 This specification defines one Message Type, to be allocated from the 3992 0-223 range of the "Message Types" namespace defined in [RFC5444], as 3993 specified in Table 8. 3995 +------+----------------------------------------------+ 3996 | Type | Description | 3997 +------+----------------------------------------------+ 3998 | TBD1 | TC : Topology Control (MANET-wide signaling) | 3999 +------+----------------------------------------------+ 4001 Table 8: Message Type assignment 4003 24.3. Message-Type-Specific TLV Type Registries 4005 IANA is requested to create a registry for Message-Type-specific 4006 Message TLVs for TC messages, in accordance with Section 6.2.1 of 4007 [RFC5444], and with initial assignments and allocation policies as 4008 specified in Table 9. 4010 +---------+-------------+-------------------+ 4011 | Type | Description | Allocation Policy | 4012 +---------+-------------+-------------------+ 4013 | 128-223 | Unassigned | Expert Review | 4014 +---------+-------------+-------------------+ 4016 Table 9: TC Message-Type-specific Message TLV Types 4018 IANA is requested to create a registry for Message-Type-specific 4019 Address Block TLVs for TC messages, in accordance with Section 6.2.1 4020 of [RFC5444], and with initial assignments and allocation policies as 4021 specified in Table 10. 4023 +---------+-------------+-------------------+ 4024 | Type | Description | Allocation Policy | 4025 +---------+-------------+-------------------+ 4026 | 128-223 | Unassigned | Expert Review | 4027 +---------+-------------+-------------------+ 4029 Table 10: TC Message-Type-specific Address Block TLV Types 4031 24.4. Message TLV Types 4033 This specification defines two Message TLV Types, which must be 4034 allocated from the "Message TLV Types" namespace defined in 4035 [RFC5444]. IANA is requested to make allocations in the 0-127 range 4036 for these types. This will create two new Type Extension registries 4037 with assignments as specified in Table 11 and Table 12. 4038 Specifications of these TLVs are in Section 13.3.1. Each of these 4039 TLVs MUST NOT be included more than once in a Message TLV Block. 4041 +-------------+------+-----------+---------------------+------------+ 4042 | Name | Type | Type | Description | Allocation | 4043 | | | Extension | | Policy | 4044 +-------------+------+-----------+---------------------+------------+ 4045 | MPR_WILLING | TBD2 | 0 | Bits 0-3 specify | | 4046 | | | | the originating | | 4047 | | | | router's | | 4048 | | | | willingness to act | | 4049 | | | | as a flooding MPR; | | 4050 | | | | bits 4-7 specify | | 4051 | | | | the originating | | 4052 | | | | router's | | 4053 | | | | willingness to act | | 4054 | | | | as a routing MPR. | | 4055 | MPR_WILLING | TBD2 | 1-255 | Unassigned. | Expert | 4056 | | | | | Review | 4057 +-------------+------+-----------+---------------------+------------+ 4059 Table 11: Message TLV Type assignment: MPR_WILLING 4061 +--------------+------+-----------+--------------------+------------+ 4062 | Name | Type | Type | Description | Allocation | 4063 | | | Extension | | Policy | 4064 +--------------+------+-----------+--------------------+------------+ 4065 | CONT_SEQ_NUM | TBD3 | 0 | COMPLETE: | | 4066 | | | | Specifies a | | 4067 | | | | content sequence | | 4068 | | | | number for this | | 4069 | | | | complete message. | | 4070 | CONT_SEQ_NUM | TBD3 | 1 | INCOMPLETE: | | 4071 | | | | Specifies a | | 4072 | | | | content sequence | | 4073 | | | | number for this | | 4074 | | | | incomplete | | 4075 | | | | message. | | 4076 | CONT_SEQ_NUM | TBD3 | 2-255 | Unassigned. | Expert | 4077 | | | | | Review | 4078 +--------------+------+-----------+--------------------+------------+ 4080 Table 12: Message TLV Type assignment: CONT_SEQ_NUM 4082 Type extensions indicated as Expert Review SHOULD be allocated as 4083 described in [RFC5444], based on Expert Review as defined in 4084 [RFC5226]. 4086 24.5. Address Block TLV Types 4088 This specification defines four Address Block TLV Types, which must 4089 be allocated from the "Address Block TLV Types" namespace defined in 4090 [RFC5444]. IANA are requested to make allocations in the 8-127 range 4091 for these types. This will create four new Type Extension registries 4092 with assignments as specified in Table 13, Table 14, Table 15 and 4093 Table 16. Specifications of these TLVs are in Section 13.3.2. 4095 +-------------+------+-----------+-------------------+--------------+ 4096 | Name | Type | Type | Description | Allocation | 4097 | | | Extension | | Policy | 4098 +-------------+------+-----------+-------------------+--------------+ 4099 | LINK_METRIC | TBD4 | 0 | Link metric | | 4100 | | | | meaning assigned | | 4101 | | | | by administrative | | 4102 | | | | action. | | 4103 | LINK_METRIC | TBD4 | 1-223 | Unassigned. | Expert | 4104 | | | | | Review | 4105 | LINK_METRIC | TBD4 | 224-255 | Unassigned. | Experimental | 4106 | | | | | Use | 4107 +-------------+------+-----------+-------------------+--------------+ 4109 Table 13: Address Block TLV Type assignment: LINK_METRIC 4111 All LINK_METRIC TLVs, whatever their type extension, MUST use their 4112 value field to encode the kind and value (in the interval 4113 MINIMUM_METRIC, to MAXIMUM_METRIC, inclusive) of a link metric as 4114 specified in Section 6 and Section 13.3.2. An assignment of a 4115 LINK_METRIC TLV type extension MUST specify the physical meaning, and 4116 mapping of that physical meaning to the representable values in the 4117 indicated interval, of the link metric. 4119 +------+------+-----------+----------------------------+------------+ 4120 | Name | Type | Type | Description | Allocation | 4121 | | | Extension | | Policy | 4122 +------+------+-----------+----------------------------+------------+ 4123 | MPR | TBD5 | 0 | Specifies that a given | | 4124 | | | | network address is of a | | 4125 | | | | router selected as a | | 4126 | | | | flooding MPR (FLOODING = | | 4127 | | | | 1), that a given network | | 4128 | | | | address is of a router | | 4129 | | | | selected as a routing MPR | | 4130 | | | | (ROUTING = 2), or both | | 4131 | | | | (FLOOD_ROUTE = 3). | | 4132 | MPR | TBD5 | 1-255 | Unassigned. | Expert | 4133 | | | | | Review | 4134 +------+------+-----------+----------------------------+------------+ 4136 Table 14: Address Block TLV Type assignment: MPR 4138 +---------------+------+-----------+-------------------+------------+ 4139 | Name | Type | Type | Description | Allocation | 4140 | | | Extension | | Policy | 4141 +---------------+------+-----------+-------------------+------------+ 4142 | NBR_ADDR_TYPE | TBD6 | 0 | Specifies that a | | 4143 | | | | given network | | 4144 | | | | address is of a | | 4145 | | | | neighbor reached | | 4146 | | | | via the | | 4147 | | | | originating | | 4148 | | | | router, if it is | | 4149 | | | | an originator | | 4150 | | | | address | | 4151 | | | | (ORIGINATOR = 1), | | 4152 | | | | is a routable | | 4153 | | | | address (ROUTABLE | | 4154 | | | | = 2), or if it is | | 4155 | | | | both | | 4156 | | | | (ROUTABLE_ORIG = | | 4157 | | | | 3). | | 4158 | NBR_ADDR_TYPE | TBD6 | 1-255 | Unassigned. | Expert | 4159 | | | | | Review | 4160 +---------------+------+-----------+-------------------+------------+ 4162 Table 15: Address Block TLV Type assignment: NBR_ADDR_TYPE 4164 +---------+------+-----------+-------------------------+------------+ 4165 | Name | Type | Type | Description | Allocation | 4166 | | | extension | | Policy | 4167 +---------+------+-----------+-------------------------+------------+ 4168 | GATEWAY | TBD7 | 0 | Specifies that a given | | 4169 | | | | network address is | | 4170 | | | | reached via a gateway | | 4171 | | | | on the originating | | 4172 | | | | router, with value | | 4173 | | | | equal to the number of | | 4174 | | | | hops. | | 4175 | GATEWAY | TBD7 | 1-255 | | Expert | 4176 | | | | | Review | 4177 +---------+------+-----------+-------------------------+------------+ 4179 Table 16: Address Block TLV Type assignment: GATEWAY 4181 Type extensions indicated as Expert Review SHOULD be allocated as 4182 described in [RFC5444], based on Expert Review as defined in 4183 [RFC5226]. 4185 24.6. NBR_ADDR_TYPE and MPR Values 4187 Note: This section does not require any IANA action, as the required 4188 information is included in the descriptions of the MPR and 4189 NBR_ADDR_TYPE Address Block TLVs allocated in Section 24.5. This 4190 information is recorded here for clarity, and for use elsewhere in 4191 this specification. 4193 The Values which the MPR Address Block TLV can use are the following: 4195 o FLOODING := 1; 4197 o ROUTING := 2; 4199 o FLOOD_ROUTE := 3. 4201 The Values which the NBR_ADDR_TYPE Address Block TLV can use are the 4202 following: 4204 o ORIGINATOR := 1; 4206 o ROUTABLE := 2; 4208 o ROUTABLE_ORIG := 3. 4210 25. Contributors 4212 This specification is the result of the joint efforts of the 4213 following contributors -- listed alphabetically. 4215 o Cedric Adjih, INRIA, France, 4217 o Emmanuel Baccelli, INRIA , France, 4219 o Thomas Heide Clausen, LIX, France, 4221 o Justin Dean, NRL, USA, 4223 o Christopher Dearlove, BAE Systems, UK, 4224 4226 o Ulrich Herberg, Fujitsu Laboratories of America, USA, 4227 4229 o Satoh Hiroki, Hitachi SDL, Japan, 4231 o Philippe Jacquet, Alcatel Lucent Bell Labs, France, 4232 4234 o Monden Kazuya, Hitachi SDL, Japan, 4236 o Kenichi Mase, Niigata University, Japan, 4238 o Ryuji Wakikawa, Toyota, Japan, 4240 26. Acknowledgments 4242 The authors would like to acknowledge the team behind OLSRv1, as 4243 listed in RFC3626, including Anis Laouiti (INT), Pascale Minet 4244 (INRIA), Paul Muhlethaler (INRIA), Amir Qayyum (M.A. Jinnah 4245 University), and Laurent Viennot (INRIA) for their contributions. 4247 The authors would like to gratefully acknowledge the following people 4248 for intense technical discussions, early reviews and comments on the 4249 specification and its components (listed alphabetically): Khaldoun Al 4250 Agha (LRI), Teco Boot (Infinity Networks), Song-Yean Cho (Samsung), 4251 Alan Cullen (BAE Systems), Louise Lamont (CRC), Li Li (CRC), Joseph 4252 Macker (NRL), Richard Ogier (SRI), Charles E. Perkins (Futurewei), 4253 Henning Rogge (Frauenhofer FKIE), and the entire IETF MANET Working 4254 Group. 4256 27. References 4257 27.1. Normative References 4259 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 4260 Requirement Levels", RFC 2119, BCP 14, March 1997. 4262 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 4263 Considerations in Mobile Ad Hoc Networks (MANETs)", 4264 RFC 5148, February 2008. 4266 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 4267 IANA Considerations Section in RFCs", RFC 5226, BCP 26, 4268 May 2008. 4270 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 4271 "Generalized Mobile Ad Hoc Network (MANET) Packet/ 4272 Message Format", RFC 5444, February 2009. 4274 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 4275 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, 4276 March 2009. 4278 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc 4279 Network (MANET) Protocols", RFC 5498, March 2009. 4281 [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc 4282 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 4283 RFC 6130, April 2011. 4285 27.2. Informative References 4287 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 4288 (MANET): Routing Protocol Performance Issues and 4289 Evaluation Considerations", RFC 2501, January 1999. 4291 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 4292 Routing Protocol", RFC 3626, October 2003. 4294 [RFC6622] Herberg, U. and T. Clausen, "Integrity Check Value and 4295 Timestamp TLV Definitions for Mobile Ad Hoc Networks 4296 (MANETs)", RFC 6622, May 2012. 4298 [HIPERLAN] ETSI, "ETSI STC-RES10 Committee. Radio equipment and 4299 systems: HIPERLAN type 1, functional specifications ETS 4300 300-652", June 1996. 4302 [HIPERLAN2] Jacquet, P., Minet, P., Muhlethaler, P., and N. 4303 Rivierre, "Increasing reliability in cable free radio 4304 LANs: Low level forwarding in HIPERLAN.", 1996. 4306 [MPR] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint 4307 relaying: An efficient technique for flooding in mobile 4308 wireless networks.", 2001. 4310 [FSR] Pei, G., Gerla, M., and T. Chen, "Fisheye state routing 4311 in mobile ad hoc networks", 2000. 4313 [FSLS] Santivanez, C., Ramanathan, R., and I. Stavrakakis, 4314 "Making link-state routing scale for ad hoc networks", 4315 2000. 4317 Appendix A. Example Algorithm for Calculating MPRs 4319 The following specifies an algorithm which MAY be used to select an 4320 MPR Set given a Neighbor Graph, as defined in Section 18.2 and 4321 Section 18.3. 4323 This algorithm selects an MPR Set M that is a subset of the set N1 4324 that is part of the Neighbor Graph. This algorithm assumes that a 4325 subset I of N1 is pre-selected as MPRs, i.e., that M will contain I. 4327 A.1. Additional Notation 4329 The following additional notation, in addition to that in 4330 Section 18.2 will be used by this algorithm: 4332 N: 4333 A subset of N2, consisting of those elements y in N2 such that 4334 either d1(y) is not defined, or there is at least one x in N1 such 4335 that d(x,y) is defined and d(x,y) < d1(y). 4337 D(x): 4338 For an element x in N1, the number of elements y in N for which 4339 d(x,y) is defined and has minimal value among the d(z,y) for all z 4340 in N1. 4342 R(x,M): 4343 For an element x in N1, the number of elements y in N for which 4344 d(x,y) is defined, has minimal value among the d(z,y) for all z in 4345 N1, and no such minimal values have z in M. (Note that, denoting 4346 the empty set by 0, D(x) = R(x,0).) 4348 A.2. MPR Selection Algorithm 4350 To create the MPR Set M, starting with M := I: 4352 1. Add all elements x in N1 that have W(x) = WILL_ALWAYS to M. 4354 2. For each element y in N for which there is only one element x in 4355 N1 such that d2(x,y) is defined, add that element x to M. 4357 3. While there exists any element x in N1 with R(x,M) > 0: 4359 1. Select an element x in N1 with R(x,M) > 0 in the following 4360 order of priority, and then add to M: 4362 + greatest W(x), THEN; 4364 + greatest R(x,M), THEN; 4366 + greatest D(x), THEN; 4368 + any choice, which MAY be based on other criteria (for 4369 example a router MAY choose to prefer a neighbor as an MPR 4370 if that neighbor has already selected the router as an MPR 4371 of the same type, MAY prefer a neighbor based on 4372 information freshness, or MAY prefer a neighbor based on 4373 length of time previously selected as an MPR) or MAY be 4374 random. 4376 4. OPTIONAL: consider each element x in M, but not in I, in turn and 4377 if x can be removed from M while still leaving it satisfying the 4378 definition of an MPR Set, then remove that element x from M. 4379 Elements MAY be considered in any order, e.g., in order of 4380 increasing W(x). 4382 Appendix B. Example Algorithm for Calculating the Routing Set 4384 The following procedure is given as an example for calculating the 4385 Routing Set using a variation of Dijkstra's algorithm. First all 4386 Routing Tuples are removed, and then, using the selections and 4387 definitions in Appendix B.1, the procedures in the following sections 4388 (each considered a "stage" of the processing) are applied in turn. 4390 B.1. Local Interfaces and Neighbors 4392 The following selections and definitions are made: 4394 1. For each Local Interface Tuple, select a network address from its 4395 I_local_iface_addr_list, this is defined as the selected address 4396 for this Local Interface Tuple. 4398 2. For each Link Tuple, the selected address of its corresponding 4399 Local Interface Tuple is defined as the selected local address 4400 for this Local Interface Tuple. 4402 3. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4403 != UNKNOWN_METRIC, select a Link Tuple with L_status = SYMMETRIC 4404 for which this is the corresponding Neighbor Tuple and has 4405 L_out_metric = N_out_metric. This is defined as the selected 4406 Link Tuple for this Neighbor Tuple. 4408 4. For each network address (N_orig_addr or in N_neighbor_addr_list, 4409 the "neighbor address") from a Neighbor Tuple with N_symmetric = 4410 true and N_out_metric != UNKNOWN_METRIC, select a Link Tuple (the 4411 "selected Link Tuple") from those for which this is the 4412 corresponding Neighbor Tuple, have L_status = SYMMETRIC, and have 4413 L_out_metric = N_out_metric, by: 4415 1. If there is such a Link Tuple whose 4416 L_neighbor_iface_addr_list contains the neighbor address, 4417 select that Link Tuple. 4419 2. Otherwise select the selected Link Tuple for this Neighbor 4420 Tuple. 4422 Then for this neighbor address: 4424 3. The selected local address is defined as the selected local 4425 address for the selected Link Tuple. 4427 4. The selected link address is defined as an address from the 4428 L_neighbor_iface_addr_list of the selected Link Tuple, if 4429 possible equal to this neighbor address. 4431 5. Routing Tuple preference is decided by preference for minimum 4432 R_dist, then for minimum R_dist, and then for preference for 4433 corresponding Neighbor Tuples in this order: 4435 * For greater N_will_routing. 4437 * For N_mpr_selector = true over N_mpr_selector = false. 4439 Note that preferred Routing Tuples SHOULD be used. Routing 4440 Tuples with minimum R_metric MUST be used, this is specified 4441 outside the definition of preference. An implementation MAY 4442 modify this definition of preference (including for minimum 4443 R_dist) without otherwise affecting this algorithm. 4445 B.2. Add Neighbor Routers 4447 The following procedure is executed once. 4449 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4450 != UNKNOWN_METRIC, add a Routing Tuple with: 4452 * R_dest_addr := N_orig_addr; 4454 * R_next_iface_addr := selected link address for N_orig_addr; 4456 * R_local_iface_addr := selected local address for N_orig_addr; 4458 * R_metric := N_out_metric; 4460 * R_dist := 1. 4462 B.3. Add Remote Routers 4464 The following procedure is executed once. 4466 1. Add a label that may be "used" or "unused" to each Routing Tuple, 4467 with all initial values equal to unused. (Note that this label 4468 is only required during this algorithm.) 4470 2. If there are no unused Routing Tuples then this stage is 4471 complete, otherwise repeat the following until that is the case. 4473 1. Find the unused Routing Tuple with minimum R_metric (if more 4474 than one, pick any) and denote it the "current Routing 4475 Tuple". 4477 2. Mark the current Routing Tuple as used. 4479 3. For each Router Topology Tuple, with: 4481 + TR_from_orig_addr = R_dest_addr of the current Routing 4482 Tuple. 4484 2. Define: 4486 - new_metric := R_metric of the current Routing Tuple + 4487 TR_metric; 4489 - new_dist := R_dist of the current Routing Tuple + 1. 4491 3. If there is no Routing Tuple with R_dest_addr = 4492 TR_to_orig_addr, then create an unused Routing Tuple 4493 with: 4495 - R_dest_addr := TR_to_orig_addr; 4496 - R_next_iface_addr := R_next_iface_addr of the current 4497 Routing Tuple; 4499 - R_local_iface_addr := R_local_iface_addr of the 4500 current Routing Tuple; 4502 - R_metric := new_metric; 4504 - R_dist := new_dist. 4506 4. Otherwise, if there is an unused Routing Tuple with 4507 R_dest_addr = TR_to_orig_addr, and either new_metric < 4508 R_metric or (new_metric = R_metric and the updated 4509 Routing Tuple would be preferred) then update this 4510 Routing Tuple to have: 4512 - R_next_iface_addr := R_next_iface_addr of the current 4513 Routing Tuple; 4515 - R_local_iface_addr := R_local_iface_addr of the 4516 current Routing Tuple; 4518 - R_metric := new_metric; 4520 - R_dist := new_dist. 4522 B.4. Add Neighbor Addresses 4524 The following procedure is executed once. 4526 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4527 != UNKNOWN_METRIC: 4529 1. For each network address (the "neighbor address") in 4530 N_neighbor_addr_list, if the neighbor address is not equal to 4531 the R_dest_addr of any Routing Tuple, then add a new Routing 4532 Tuple, with: 4534 + R_dest_addr := neighbor address; 4536 + R_next_iface_addr := selected link address for the 4537 neighbor address; 4539 + R_local_iface_addr := selected local address for the 4540 neighbor address; 4542 + R_metric := N_out_metric; 4543 + R_dist := 1. 4545 B.5. Add Remote Routable Addresses 4547 The following procedure is executed once. 4549 1. For each Routable Address Topology Tuple, if: 4551 * TA_dest_addr is not equal to the R_dest_addr of any Routing 4552 Tuple added in an earlier stage; AND 4554 * TA_from_orig_addr is equal to the R_dest_addr of a Routing 4555 Tuple (the "previous Routing Tuple"), 4557 then add a new Routing Tuple, with: 4559 * R_dest_addr := TA_dest_addr; 4561 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4562 Tuple; 4564 * R_local_iface_addr := R_local_iface_addr of the previous 4565 Routing Tuple; 4567 * R_metric := R_metric of the previous Routing Tuple + 4568 TA_metric. 4570 * R_dist := R_dist of the previous Routing Tuple + 1. 4572 There may be more than one Routing Tuple that may be added for an 4573 R_dest_addr in this stage. If so, then, for each such 4574 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4575 selected, otherwise a Routing Tuple which is preferred SHOULD be 4576 added. 4578 B.6. Add Attached Networks 4580 The following procedure is executed once. 4582 1. For each Attached Network Tuple, if: 4584 * AN_net_addr is not equal to the R_dest_addr of any Routing 4585 Tuple added in an earlier stage; AND 4587 * AN_orig_addr is equal to the R_dest_addr of a Routing Tuple 4588 (the "previous Routing Tuple), 4590 then add a new Routing Tuple, with: 4592 * R_dest_addr := AN_net_addr; 4594 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4595 Tuple; 4597 * R_local_iface_addr := R_local_iface_addr of the previous 4598 Routing Tuple; 4600 * R_metric := R_metric of the previous Routing Tuple + 4601 AN_metric; 4603 * R_dist := R_dist of the previous Routing Tuple + AN_dist. 4605 There may be more than one Routing Tuple that may be added for an 4606 R_dest_addr in this stage. If so, then, for each such 4607 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4608 selected, otherwise a Routing Tuple which is preferred SHOULD be 4609 added. 4611 B.7. Add 2-Hop Neighbors 4613 The following procedure is executed once. 4615 1. For each 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC, if: 4617 * N2_2hop_addr is a routable address; AND 4619 * N2_2hop_addr is not equal to the R_dest_addr of any Routing 4620 Tuple added in an earlier stage; AND 4622 * the Routing Tuple with R_dest_addr = N_orig_addr of the 4623 corresponding Neighbor Tuple (the "previous Routing Tuple") 4624 has R_dist = 1, 4626 then add a new Routing Tuple, with: 4628 * R_dest_addr := N2_2hop_addr; 4630 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4631 Tuple; 4633 * R_local_iface_addr := R_local_iface_addr of the previous 4634 Routing Tuple; 4636 * R_metric := R_metric of the previous Routing Tuple + 4637 N_out_metric of the corresponding Neighbor Tuple; 4639 * R_dist := 2. 4641 There may be more than one Routing Tuple that may be added for an 4642 R_dest_addr in this stage. If so, then, for each such 4643 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4644 selected, otherwise a Routing Tuple which is preferred SHOULD be 4645 added. 4647 Appendix C. TC Message Example 4649 TC messages are instances of [RFC5444] messages. This specification 4650 requires that TC messages contain and 4651 fields. It supports TC messages with any combination of remaining 4652 message header options and address encodings, enabled by [RFC5444] 4653 that convey the required information. As a consequence, there is no 4654 single way to represent how all TC messages look. This appendix 4655 illustrates a TC message, the exact values and content included are 4656 explained in the following text. 4658 The TC message's four bit Message Flags (MF) field has value 15 4659 indicating that the message header contains originator address, hop 4660 limit, hop count, and message sequence number fields. Its four bit 4661 Message Address Length (MAL) field has value 3, indicating addresses 4662 in the message have a length of four octets, here being IPv4 4663 addresses. The overall message length is 75 octets. 4665 The message has a Message TLV Block with content length 17 octets 4666 containing four TLVs. The first two TLVs are validity and interval 4667 times for the message. The third TLV is the content sequence number 4668 TLV used to carry the 2 octet ANSN, and (with default type extension 4669 zero, i.e., COMPLETE) indicating that the TC message is complete. 4670 The fourth TLV contains forwarding and routing willingness values for 4671 the originating router (FWILL and RWILL, respectively). Each TLV 4672 uses a TLV with Flags octet (MTLVF) value 16, indicating that it has 4673 a Value, but no type extension or start and stop indexes. The first 4674 two TLVs have a Value Length of 1 octet, the last has a Value Length 4675 of 2 octets. 4677 The message has two Address Blocks. (This is not necessary, the 4678 information could be conveyed using a single Address Block, the use 4679 of two Address Blocks, which is also allowed, is illustrative only.) 4680 The first Address Block contains 3 addresses, with Flags octet 4681 (ATLVF) value 128, hence with a Head section (with length 2 octets), 4682 but no Tail section, and hence with Mid sections with length two 4683 octets. The following TLV Block (content length 13 octets) contains 4684 two TLVs. The first TLV is a NBR_ADDR_TYPE TLV with Flags octet 4685 (ATLVF) value 16, indicating a single Value but no indexes. Thus all 4686 these addresses are associated with the Value (with Value Length 1 4687 octet) ROUTABLE_ORIG, i.e., they are originator addresses of 4688 advertised neighbors that are also routable addresses. The second 4689 TLV is a LINK_STATUS TLV with Flags octet (ATLVF) value 20, 4690 indicating a Value for each address, i.e., as the total Value Length 4691 is 6 octets, each address is associated with a Value with length two 4692 octets. These Value fields are each shown as having four bits 4693 indicating that they are outgoing neighbor metric values, and as 4694 having twelve bits that represent the metric value (the first four 4695 bits being the exponent, the remaining twelve bits the mantissa). 4697 The second Address Block contains 1 address, with Flags octet (ATLVF) 4698 176, indicating that there is a Head section (with length 2 octets), 4699 that the Tail section (with length 2 octets) consists of zero valued 4700 octets (not included), and that there is a single prefix length, 4701 which is 16. The network address is thus Head.0.0/16. The following 4702 TLV Block (content length 8 octets) includes two TLVs. The first has 4703 a Flags octet (ATLVF) of 16, again indicating that no indexes are 4704 needed, but that a Value (with Value Length 1 octet) is present, 4705 indicating the address distance as a number of hops. The second TLV 4706 is another LINK_METRIC TLV, as in the first Address TLV Block except 4707 with a Flags octet (ATLVF) value 16, indicating that a single Value 4708 is present. 4710 0 1 2 3 4711 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 4712 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4713 | TC | MF=15 | MAL=3 | Message Length = 75 | 4714 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4715 | Originator Address | 4716 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4717 | Hop Limit | Hop Count | Message Sequence Number | 4718 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4719 | Message TLV Block Length = 17 | VALIDITY_TIME | MTLVF = 16 | 4720 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4721 | Value Len = 1 | Value (Time) | INTERVAL_TIME | MTLVF = 16 | 4722 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4723 | Value Len = 1 | Value (Time) | CONT_SEQ_NUM | MTLVF = 16 | 4724 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4725 | Value Len = 2 | Value (ANSN) | MPR_WILLING | 4726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4727 | MTLVF = 16 | Value Len = 1 | FWILL | RWILL | Num Addrs = 3 | 4728 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4729 | ABF = 128 | Head Len = 2 | Head | 4730 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4731 | Mid | Mid | 4732 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4733 | Mid | Address TLV Block Length = 13 | 4734 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4735 | NBR_ADDR_TYPE | ATLVF = 16 | Value Len = 1 | ROUTABLE_ORIG | 4736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4737 | LINK_METRIC | ATLVF = 20 | Value Len = 6 |0|0|0|1|Metric | 4738 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4739 | Metric (cont) |0|0|0|1| Metric |0|0|0|1|Metric | 4740 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4741 | Metric (cont) | Num Addrs = 1 | ABF = 176 | Head Len = 2 | 4742 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4743 | Head | Tail Len = 2 | Pref Len = 16 | 4744 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4745 | Address TLV Block Length = 9 | GATEWAY | ATLVF = 16 | 4746 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4747 | Value Len = 1 | Value (Hops) | LINK_METRIC | ATLVF = 16 | 4748 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4749 | Value Len = 2 |0|0|0|1| Metric | 4750 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4752 Appendix D. Constraints 4754 Any process which updates the Local Information Base, the 4755 Neighborhood Information Base or the Topology Information Base MUST 4756 ensure that all constraints specified in this appendix are 4757 maintained, as well as those specified in [RFC6130]. 4759 In each Originator Tuple: 4761 o O_orig_addr MUST NOT equal any other O_orig_addr. 4763 o O_orig_addr MUST NOT equal this router's originator address. 4765 In each Local Attached Network Tuple: 4767 o AL_net_addr MUST NOT equal any other AL_net_addr. 4769 o AL_net_addr MUST NOT equal or be a sub-range of any network 4770 address in the I_local_iface_addr_list of any Local Interface 4771 Tuple. 4773 o AL_net_addr MUST NOT equal this router's originator address, or 4774 equal the O_orig_addr in any Originator Tuple. 4776 o AL_dist MUST NOT be less than zero. 4778 In each Link Tuple: 4780 o L_neighbor_iface_addr_list MUST NOT contain any network address 4781 that AL_net_addr of any Local Attached Network Tuple equals or is 4782 a sub-range of. 4784 o if L_in_metric != UNKNOWN_METRIC then L_in_metric MUST be 4785 representable in the defined compressed form. 4787 o if L_out_metric != UNKNOWN_METRIC then L_out_metric MUST be 4788 representable in the defined compressed form. 4790 o If L_mpr_selector = true, then L_status = SYMMETRIC. 4792 In each Neighbor Tuple: 4794 o N_orig_addr MUST NOT be changed to unknown. 4796 o N_orig_addr MUST NOT equal this router's originator address, or 4797 equal O_orig_addr in any Originator Tuple. 4799 o N_orig_addr MUST NOT equal the AL_net_addr in any Local Attached 4800 Network Tuple. 4802 o If N_orig_addr != unknown, then N_orig_addr MUST NOT equal the 4803 N_orig_addr in any other Neighbor Tuple. 4805 o N_neighbor_addr_list MUST NOT contain any network address which 4806 includes this router's originator address, the O_orig_addr in any 4807 Originator Tuple, or equal or have as a sub-range the AL_net_addr 4808 in any Local Attached Network Tuple. 4810 o If N_orig_addr = unknown, then N_will_flooding = WILL_NEVER, 4811 N_will_routing = WILL_NEVER, N_flooding_mpr, N_routing_mpr = 4812 false, N_mpr_selector = false, and N_advertised = false. 4814 o N_in_metric MUST equal the minimum value of the L_in_metric values 4815 of all corresponding Link Tuples with L_status = SYMMETRIC and 4816 L_in_metric != UNKNOWN_METRIC, if any, otherwise N_in_metric = 4817 UNKNOWN_METRIC. 4819 o N_out_metric MUST equal the minimum value of the L_out_metric 4820 values of all corresponding Link Tuples with L_status = SYMMETRIC 4821 and L_out_metric != UNKNOWN_METRIC, if any, otherwise N_out_metric 4822 = UNKNOWN_METRIC. 4824 o N_will_flooding and N_will_routing MUST be in the range from 4825 WILL_NEVER to WILL_ALWAYS, inclusive. 4827 o If N_flooding_mpr = true, then N_symmetric MUST be true, 4828 N_out_metric MUST NOT equal UNKNOWN_METRIC and N_will_flooding 4829 MUST NOT equal WILL_NEVER. 4831 o If N_routing_mpr = true, then N_symmetric MUST be true, 4832 N_in_metric MUST NOT equal UNKNOWN_METRIC and N_will_routing MUST 4833 NOT equal WILL_NEVER. 4835 o If N_symmetric = true and N_flooding_mpr = false, then 4836 N_will_flooding MUST NOT equal WILL_ALWAYS. 4838 o If N_symmetric = true and N_routing_mpr = false, then 4839 N_will_routing MUST NOT equal WILL_ALWAYS. 4841 o If N_mpr_selector = true, then N_advertised MUST be true. 4843 o If N_advertised = true, then N_symmetric MUST be true and 4844 N_out_metric MUST NOT equal UNKNOWN_METRIC. 4846 In each Lost Neighbor Tuple: 4848 o NL_neighbor_addr MUST NOT include this router's originator 4849 address, the O_orig_addr in any Originator Tuple, or equal or have 4850 as a sub-range the AL_net_addr in any Local Attached Network 4851 Tuple. 4853 In each 2-Hop Tuple: 4855 o N2_2hop_addr MUST NOT equal this router's originator address, 4856 equal the O_orig_addr in any Originator Tuple, or equal or have as 4857 a sub-range the AL_net_addr in any Local Attached Network Tuple. 4859 o if N2_in_metric != UNKNOWN_METRIC then N2_in_metric MUST be 4860 representable in the defined compressed form. 4862 o if N2_out_metric != UNKNOWN_METRIC then N2_out_metric MUST be 4863 representable in the defined compressed form. 4865 In each Advertising Remote Router Tuple: 4867 o AR_orig_addr MUST NOT be in any network address in the 4868 I_local_iface_addr_list in any Local Interface Tuple or be in the 4869 IR_local_iface_addr in any Removed Interface Address Tuple. 4871 o AR_orig_addr MUST NOT equal this router's originator address or 4872 equal the O_orig_addr in any Originator Tuple. 4874 o AR_orig_addr MUST NOT be in the AL_net_addr in any Local Attached 4875 Network Tuple. 4877 o AR_orig_addr MUST NOT equal the AR_orig_addr in any other 4878 Advertising Remote Router Tuple. 4880 In each Router Topology Tuple: 4882 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4883 = TR_from_orig_addr. 4885 o TR_to_orig_addr MUST NOT be in any network address in the 4886 I_local_iface_addr_list in any Local Interface Tuple or be in the 4887 IR_local_iface_addr in any Removed Interface Address Tuple. 4889 o TR_to_orig_addr MUST NOT equal this router's originator address or 4890 equal the O_orig_addr in any Originator Tuple. 4892 o TR_to_orig_addr MUST NOT be in the AL_net_addr in any Local 4893 Attached Network Tuple. 4895 o The ordered pair (TR_from_orig_addr, TR_to_orig_addr) MUST NOT 4896 equal the corresponding pair for any other Router Topology Tuple. 4898 o TR_seq_number MUST NOT be greater than AR_seq_number in the 4899 Advertising Remote Router Tuple with AR_orig_addr = 4900 TR_from_orig_addr. 4902 o TR_metric MUST be representable in the defined compressed form. 4904 In each Routable Address Topology Tuple: 4906 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4907 = TA_from_orig_addr. 4909 o TA_dest_addr MUST be routable. 4911 o TA_dest_addr MUST NOT overlap any network address in the 4912 I_local_iface_addr_list in any Local Interface Tuple or overlap 4913 the IR_local_iface_addr in any Removed Interface Address Tuple. 4915 o TA_dest_addr MUST NOT include this router's originator address or 4916 include the O_orig_addr in any Originator Tuple. 4918 o TA_dest_addr MUST NOT equal or have as a sub-range the AL_net_addr 4919 in any Local Attached Network Tuple. 4921 o The ordered pair (TA_from_orig_addr, TA_dest_addr) MUST NOT equal 4922 the corresponding pair for any other Attached Network Tuple. 4924 o TA_seq_number MUST NOT be greater than AR_seq_number in the 4925 Advertising Remote Router Tuple with AR_orig_addr = 4926 TA_from_orig_addr. 4928 o TA_metric MUST be representable in the defined compressed form. 4930 In each Attached Network Tuple: 4932 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4933 = AN_orig_addr. 4935 o AN_net_addr MUST NOT equal or be a sub-range of any network 4936 address in the I_local_iface_addr_list in any Local Interface 4937 Tuple or be a sub-range of the IR_local_iface_addr in any Removed 4938 Interface Address Tuple. 4940 o AN_net_addr MUST NOT equal this router's originator address or 4941 equal the O_orig_addr in any Originator Tuple. 4943 o AN_net_addr MUST NOT equal the AL_net_addr in any Local Attached 4944 Network Tuple. 4946 o The ordered pair (AN_orig_addr, AN_net_addr) MUST NOT equal the 4947 corresponding pair for any other Attached Network Tuple. 4949 o AN_seq_number MUST NOT be greater than AR_seq_number in the 4950 Advertising Remote Router Tuple with AR_orig_addr = AN_orig_addr. 4952 o AN_dist MUST NOT be less than zero. 4954 o AN_metric MUST be representable in the defined compressed form. 4956 Appendix E. Flow and Congestion Control 4958 Due to its proactive nature, this protocol has a natural control over 4959 the flow of its control traffic. Routers transmit control messages 4960 at predetermined rates specified and bounded by message intervals. 4962 This protocol employs [RFC6130] for local signaling, embedding MPR 4963 selection advertisement through a simple Address Block TLV, and 4964 router willingness advertisement (if any) as a single Message TLV. 4965 Local signaling, therefore, shares the characteristics and 4966 constraints of [RFC6130]. 4968 Furthermore, the use of MPRs can greatly reduce the signaling 4969 overhead from link state information dissemination in two ways, 4970 attaining both flooding reduction and topology reduction. First, 4971 using MPR flooding, the cost of distributing link state information 4972 throughout the network is reduced, as compared to when using blind 4973 flooding, since only MPRs need to forward link state declaration 4974 messages. Second, the amount of link state information for a router 4975 to declare is reduced to need only contain that router's MPR 4976 selectors. This reduces the size of a link state declaration as 4977 compared to declaring full link state information. In particular 4978 some routers may not need to declare any such information. In dense 4979 networks, the reduction of control traffic can be of several orders 4980 of magnitude compared to routing protocols using blind flooding 4981 [MPR]. This feature naturally provides more bandwidth for useful 4982 data traffic and pushes further the frontier of congestion. 4984 Since the control traffic is continuous and periodic, it keeps the 4985 quality of the links used in routing more stable. However, using 4986 some options, some control messages (HELLO messages or TC messages) 4987 may be intentionally sent in advance of their deadline in order to 4988 increase the responsiveness of the protocol to topology changes. 4989 This may cause a small, temporary, and local increase of control 4990 traffic, however this is at all times bounded by the use of minimum 4991 message intervals. 4993 Authors' Addresses 4995 Thomas Heide Clausen 4996 LIX, Ecole Polytechnique 4998 Phone: +33 6 6058 9349 4999 EMail: T.Clausen@computer.org 5000 URI: http://www.ThomasClausen.org/ 5002 Christopher Dearlove 5003 BAE Systems ATC 5005 Phone: +44 1245 242194 5006 EMail: chris.dearlove@baesystems.com 5007 URI: http://www.baesystems.com/ 5009 Philippe Jacquet 5010 Alcatel-Lucent Bell Labs 5012 Phone: +33 6 7337 1880 5013 EMail: philippe.jacquet@alcatel-lucent.com 5015 Ulrich Herberg 5016 Fujitsu Laboratories of America 5017 1240 E. Arques Ave. 5018 Sunnyvale, CA, 94085 5019 USA 5021 EMail: ulrich@herberg.name 5022 URI: http://www.herberg.name/