idnits 2.17.1 draft-ietf-manet-olsrv2-15.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 (May 15, 2012) is 4354 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Informational RFC: RFC 5148 ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique 4 Intended status: Standards Track C. Dearlove 5 Expires: November 16, 2012 BAE Systems ATC 6 P. Jacquet 7 Alcatel-Lucent Bell Labs 8 U. Herberg 9 Fujitsu Laboratories of America 10 May 15, 2012 12 The Optimized Link State Routing Protocol version 2 13 draft-ietf-manet-olsrv2-15 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 November 16, 2012. 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. Confidentiality . . . . . . . . . . . . . . . . . . . . . 81 176 23.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 82 177 23.3. Interaction with External Routing Domains . . . . . . . . 83 178 24. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 84 179 24.1. Expert Review: Evaluation Guidelines . . . . . . . . . . 84 180 24.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 84 181 24.3. Message-Type-Specific TLV Type Registries . . . . . . . . 84 182 24.4. Message TLV Types . . . . . . . . . . . . . . . . . . . . 85 183 24.5. Address Block TLV Types . . . . . . . . . . . . . . . . . 86 184 24.6. NBR_ADDR_TYPE and MPR Values . . . . . . . . . . . . . . 89 185 25. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 89 186 26. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 90 187 27. References . . . . . . . . . . . . . . . . . . . . . . . . . 90 188 27.1. Normative References . . . . . . . . . . . . . . . . . . 90 189 27.2. Informative References . . . . . . . . . . . . . . . . . 91 190 Appendix A. Example Algorithm for Calculating MPRs . . . . . . . 91 191 A.1. Additional Notation . . . . . . . . . . . . . . . . . . . 92 192 A.2. MPR Selection Algorithm . . . . . . . . . . . . . . . . . 92 194 Appendix B. Example Algorithm for Calculating the Routing Set . 93 195 B.1. Local Interfaces and Neighbors . . . . . . . . . . . . . 93 196 B.2. Add Neighbor Routers . . . . . . . . . . . . . . . . . . 94 197 B.3. Add Remote Routers . . . . . . . . . . . . . . . . . . . 94 198 B.4. Add Neighbor Addresses . . . . . . . . . . . . . . . . . 96 199 B.5. Add Remote Routable Addresses . . . . . . . . . . . . . . 96 200 B.6. Add Attached Networks . . . . . . . . . . . . . . . . . . 97 201 B.7. Add 2-Hop Neighbors . . . . . . . . . . . . . . . . . . . 98 202 Appendix C. TC Message Example . . . . . . . . . . . . . . . . . 98 203 Appendix D. Constraints . . . . . . . . . . . . . . . . . . . . 101 204 Appendix E. Flow and Congestion Control . . . . . . . . . . . . 105 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]. 276 2. Terminology 278 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 279 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 280 "OPTIONAL" in this document are to be interpreted as described in 281 [RFC2119]. 283 All terms introduced in [RFC5444], including "packet", "Packet 284 Header", "message", "Message Header", "Message Body", "Message Type", 285 "message sequence number", "hop limit", "hop count", "Address Block", 286 "TLV Block", "TLV", "Message TLV", "Address Block TLV", "type" (of 287 TLV), "type extension" (of TLV), "value" (of TLV), "address", 288 "address prefix", and "address object" are to be interpreted as 289 described there. 291 All terms introduced in [RFC6130], including "interface", "MANET 292 interface", "network address", "link", "symmetric link", "symmetric 293 1-hop neighbor", "symmetric 2-hop neighbor", "symmetric 1-hop 294 neighborhood" "constant", "interface parameter", "router parameter", 295 "Information Base", and "HELLO message" are to be interpreted as 296 described there. 298 Additionally, this specification uses the following terminology: 300 Router: 301 A MANET router which implements this protocol. 303 OLSRv2 interface: 304 A MANET interface running this protocol. A router running this 305 protocol MUST have at least one OLSRv2 interface. 307 Routable address: 308 A network address which may be used as the destination of a data 309 packet. A router MUST be able to distinguish a routable address 310 from a non-routable address by direct inspection of the network 311 address, based on global scope address allocations by IANA and/or 312 administrative configuration. Broadcast and multicast addresses, 313 and addresses which are limited in scope to less than the entire 314 MANET, MUST NOT be considered as routable addresses. Anycast 315 addresses MAY be considered as routable addresses. 317 Originator address: 318 An address which is unique (within the MANET) to a router. A 319 router MUST select an originator address; it MAY choose one of its 320 interface addresses as its originator address; it MAY select 321 either a routable or non-routable address. A broadcast, multicast 322 or anycast address MUST NOT be chosen as an originator address. 323 If the router selects a routable address then this MUST be one 324 which the router will accept as destination. An originator 325 address MUST NOT have a prefix length, except for when included in 326 an Address Block where it MAY be associated with a prefix of 327 maximum prefix length (e.g., if the originator address is an IPv6 328 address, it MUST have either no prefix length, or have a prefix 329 length of 128). 331 Message originator address: 332 The originator address of the router which created a message, as 333 deduced from that message by its recipient. For all messages used 334 in this specification, including HELLO messages defined in 335 [RFC6130], the recipient MUST be able to deduce an originator 336 address. The message originator address will usually be included 337 in the message as its element as defined in 338 [RFC5444]. However, an exceptional case, which does not add a 339 element to a HELLO message, may be used by a 340 router that only has a single address. 342 Willingness: 343 A numerical value between WILL_NEVER and WILL_ALWAYS (both 344 inclusive), that represents the router's willingness to be 345 selected as an MPR. A router has separate willingness values to 346 be a flooding MPR and a routing MPR. 348 Willing symmetric 1-hop neighbor: 349 A symmetric 1-hop neighbor that has willingness not equal to 350 WILL_NEVER. 352 Multipoint relay (MPR): 353 A router, X, is an MPR for a router, Y, if router Y has indicated 354 its selection of router X as an MPR in a recent HELLO message. 355 Router X may be a flooding MPR for Y if it is indicated to 356 participate in the flooding process of messages received from 357 router Y, or it may be a routing MPR for Y, if it is indicated to 358 declare link-state information for the link from X to Y. It may 359 also be both at the same time. 361 MPR selector: 362 A router, Y, is a flooding/routing MPR selector of router X if 363 router Y has selected router X as a flooding/routing MPR. 365 MPR flooding: 366 The optimized MANET-wide information distribution mechanism, 367 employed by this protocol, in which a message is relayed by only a 368 reduced subset of the routers in the network. MPR flooding is the 369 mechanism by which flooding reduction is achieved. 371 This specification employs the same notational conventions as in 372 [RFC5444] and [RFC6130]. 374 3. Applicability Statement 376 This protocol: 378 o Is a proactive routing protocol for mobile ad hoc networks 379 (MANETs) [RFC2501]. 381 o Is designed to work in networks with a dynamic topology, and in 382 which messages may be lost, such as due to collisions over 383 wireless media. 385 o Supports routers that each have one or more participating OLSRv2 386 interfaces, which will consist of some or all of its MANET 387 interfaces using [RFC6130]. The set of a router's OLSRv2 388 interfaces, and the sets of its other MANET and non-MANET 389 interfaces, may change over time. Each interface may have one or 390 more network addresses (which may have prefix lengths), and these 391 may also be dynamically changing. 393 o Enables hop-by-hop routing, i.e., each router can use its local 394 information provided by this protocol to route packets. 396 o Continuously maintains routes to all destinations in the network, 397 i.e., routes are instantly available and data traffic is subject 398 to no delays due to route discovery. Consequently, no data 399 traffic buffering is required. 401 o Supports routers that have non-OLSRv2 interfaces that may be local 402 to a router or that can serve as gateways towards other networks. 404 o Enables the use of bidirectional additive link metrics to use 405 shortest distance routes (i.e., routes with smallest total of link 406 metrics). Incoming link metric values are to be determined by a 407 process outside this specification. 409 o Is optimized for large and dense networks; the larger and more 410 dense a network, the more optimization can be achieved by using 411 MPRs, compared to the classic link state algorithm [MPR]. 413 o Uses [RFC5444] as described in its "Intended Usage" appendix and 414 by [RFC5498]. 416 o Allows "external" and "internal" extensibility (adding new message 417 types and adding information to existing messages) as enabled by 418 [RFC5444]. 420 o Is designed to work in a completely distributed manner, and does 421 not depend on any central entity. 423 4. Protocol Overview and Functioning 425 The objectives of this protocol are for each router to: 427 o Identify all destinations in the network. 429 o Identify a sufficient subset of links in the network, in order 430 that shortest routes can be calculated to all available 431 destinations. 433 o Provide a Routing Set, containing these shortest routes from this 434 router to all destinations (routable addresses and local links). 436 4.1. Overview 438 These objectives are achieved, for each router, by: 440 o Using [RFC6130] to identify symmetric 1-hop neighbors and 441 symmetric 2-hop neighbors. 443 o Reporting its participation in OLSRv2, and its willingness to be a 444 flooding MPR and to be a routing MPR, by extending the HELLO 445 messages defined in [RFC6130], by the addition of an MPR_WILLING 446 Message TLV. The router's "flooding willingness" indicates how 447 willing it is to participate in MPR flooding. The router's 448 "routing willingness" indicates how willing it is to be an 449 intermediate router for routing. Note that a router is still able 450 to be a routing source or destination, even if unwilling to 451 perform either function. 453 o Extending the HELLO messages defined in [RFC6130] to allow the 454 addition of directional link metrics to advertised links with 455 other routers participating in OLSRv2, and to indicate which link 456 metric type is being used by those routers. Both incoming and 457 outgoing link metrics may be reported, the former determined by 458 the advertising router. 460 o Selecting flooding MPRs and routing MPRs from among its willing 461 symmetric 1-hop neighbors such that, for each set of MPRs, all 462 symmetric 2-hop neighbors are reachable either directly or via at 463 least one selected MPR, using a path of appropriate minimum total 464 metric for at least routing MPR selection. An analysis and 465 examples of MPR selection algorithms are given in [MPR]; a 466 suggested algorithm, appropriately adapted for each set of MPRs, 467 is included in Appendix A of this specification. Note that it is 468 not necessary for routers to use the same algorithm in order to 469 interoperate in the same MANET, but each such algorithm must have 470 the appropriate properties, described in Section 18. 472 o Signaling its flooding MPR and routing MPR selections, by 473 extending the HELLO messages defined in [RFC6130] to report this 474 information by the addition of MPR Address Block TLV(s) associated 475 with the appropriate network addresses. 477 o Extracting its flooding MPR selectors and routing MPR selectors 478 from received HELLO messages, using the included MPR Address Block 479 TLV(s). 481 o Defining a TC (Topology Control) Message Type using the message 482 format specified in [RFC5444]. TC messages are used to 483 periodically signal links between routing MPR selectors and itself 484 throughout the MANET. This signaling includes suitable 485 directional neighbor metrics (the best link metric in that 486 direction between those routers). 488 o Allowing its TC messages, as well as HELLO messages, to be 489 included in packets specified in [RFC5444], using the "manet" IP 490 protocol or UDP port as specified in [RFC5498]. 492 o Diffusing TC messages by using a flooding reduction mechanism, 493 denoted "MPR flooding"; only the flooding MPRs of a router will 494 retransmit messages received from (i.e., originated or last 495 relayed by) that router. 497 Note that the indicated extensions to [RFC6130] are of forms 498 permitted by that specification. 500 This specification defines: 502 o The requirement to use [RFC6130], its parameters, constants, HELLO 503 messages, and Information Bases, each as extended in this 504 specification. 506 o Two new Information Bases: the Topology Information Base and the 507 Received Message Information Base. 509 o TC messages, which are used for MANET wide signaling (using MPR 510 flooding) of selected topology (link state) information. 512 o A requirement for each router to have an originator address to be 513 included in, or deducible from, HELLO messages and TC messages. 515 o The specification of new Message TLVs and Address Block TLVs that 516 are used in HELLO messages and TC messages, including for 517 reporting neighbor status, MPR selection, external gateways, link 518 metrics, willingness to be an MPR, and content sequence numbers. 519 Note that the generation of (incoming) link metric values is to be 520 undertaken by a process outside this specification; this 521 specification concerns only the distribution and use of those 522 metrics. 524 o The generation of TC messages from the appropriate information in 525 the Information Bases. 527 o The updating of the Topology Information Base according to 528 received TC messages. 530 o The MPR flooding mechanism, including the inclusion of message 531 originator address and sequence number to manage duplicate 532 messages, using information recorded in the Received Message 533 Information Base. 535 o The response to other events, such as the expiration of 536 information in the Information Bases. 538 This protocol inherits the stability of a link state algorithm, and 539 has the advantage of having routes immediately available when needed, 540 due to its proactive nature. 542 This protocol only interacts with IP through routing table 543 management, and the use of the sending IP address for IP datagrams 544 containing messages used by this specification. 546 4.2. Routers and Interfaces 548 In order for a router to participate in a MANET using this protocol 549 it must have at least one, and possibly more, OLSRv2 interfaces. 550 Each OLSRv2 interface: 552 o Is a MANET interface, as specified in [RFC6130]. In particular it 553 must be configured with one or more network addresses; these 554 addresses must each be specific to this router, and must include 555 any address that will be used as the sending address of any IP 556 packet sent on this OLSRv2 interface. 558 o Has a number of interface parameters, adding to those specified in 559 [RFC6130]. 561 o Has an Interface Information Base, extending that specified in 562 [RFC6130]. 564 o Generates and processes HELLO messages according to [RFC6130], 565 extended as specified in Section 15. 567 In addition to a set of OLSRv2 interfaces as described above, each 568 router: 570 o May have one or more non-OLSRv2 interfaces (which may include 571 MANET interfaces and/or non-MANET interfaces) and/or local 572 attached networks for which this router can accept IP packets. 573 All routable addresses for which the router is to accept IP 574 packets must be used as an (OLSRv2 or non-OLSRv2) interface 575 network address, or as an address of a local attached network of 576 the router. 578 o Has a number of router parameters, adding to those specified in 579 [RFC6130]. 581 o Has a Local Information Base, extending that specified in 582 [RFC6130], including selection of an originator address and 583 recording any locally attached networks. 585 o Has a Neighbor Information Base, extending that specified in 586 [RFC6130] to record MPR selection and advertisement information. 588 o Has a Topology Information Base, recording information received in 589 TC messages. 591 o Has a Received Message Information Base, recording information 592 about received messages to ensure that each TC message is only 593 processed once, and forwarded at most once on each OLSRv2 594 interface, by a router. 596 o Generates, receives, and processes TC messages. 598 4.3. Information Base Overview 600 Each router maintains the Information Bases described in the 601 following sections. These are used for describing the protocol in 602 this specification. An implementation of this protocol may maintain 603 this information in the indicated form, or in any other organization 604 which offers access to this information. In particular, note that it 605 is not necessary to remove Tuples from Sets at the exact time 606 indicated, only to behave as if the Tuples were removed at that time. 608 4.3.1. Local Information Base 610 The Local Information Base is specified in [RFC6130], and contains a 611 router's local configuration. It is extended in this specification 612 to also record an originator address, and to include a router's: 614 o Originator Set, containing addresses that were recently used as 615 this router's originator address, and is used, together with the 616 router's current originator address, to enable a router to 617 recognize and discard control traffic which was originated by the 618 router itself. 620 o Local Attached Network Set, containing network addresses of 621 networks to which this router can act as a gateway, and advertises 622 in its TC messages. 624 4.3.2. Interface Information Bases 626 The Interface Information Base for each OLSRv2 interface is as 627 specified in [RFC6130], extended to also record, in each Link Set, 628 link metric values (incoming and outgoing) and flooding MPR selector 629 information. 631 4.3.3. Neighbor Information Base 633 The Neighbor Information Base is specified in [RFC6130], and is 634 extended to also record, in the Neighbor Tuple for each neighbor: 636 o Its originator address. 638 o Neighbor metric values, these being the minimum of the link metric 639 values in the indicated direction for all symmetric 1-hop links 640 with that neighbor. 642 o Its willingness to be a flooding MPR and to be a routing MPR. 644 o Whether it has been selected by this router as a flooding MPR or 645 as a routing MPR, and whether it is a routing MPR selector of this 646 router. (Whether it is a flooding MPR selector of this neighbor 647 is recorded in the Interface Information Base.) 649 o Whether it is to be advertised in TC messages sent by this router. 651 4.3.4. Topology Information Base 653 The Topology Information Base in each router contains: 655 o An Advertising Remote Router Set, recording each remote router 656 from which TC messages have been received. This is used in order 657 to determine if a received TC message contains fresh or outdated 658 information; a received TC message is ignored in the latter case. 660 o A Router Topology Set, recording links between routers in the 661 MANET, as described by received TC messages. 663 o A Routable Address Topology Set, recording routable addresses in 664 the MANET (available as IP packet destinations) and from which 665 remote router these routable addresses can be directly reached 666 (i.e., in a single IP hop from that remote router), as reported by 667 received TC messages. 669 o An Attached Network Set, recording networks to which a remote 670 router has advertised that it may act as a gateway. These 671 networks may be reached in one or more IP hops from that remote 672 router. 674 o A Routing Set, recording routes from this router to all available 675 destinations. The IP routing table is to be updated using this 676 Routing Set. (A router may choose to use any or all destination 677 network addresses in the Routing Set to update the IP routing 678 table, this selection is outside the scope of this specification.) 680 The purpose of the Topology Information Base is to record information 681 used, in addition to that in the Local Information Base, the 682 Interface Information Bases and the Neighbor Information Base, to 683 construct the Routing Set (which is also included in the Topology 684 Information Base). 686 This specification describes the calculation of the Routing Set based 687 on a Topology Graph constructed in two phases. First, a "backbone" 688 graph representing the routers in the MANET, and the connectivity 689 between them, is constructed from the Local Information Base, the 690 Neighbor Information Base and the Router Topology Set. Second, this 691 graph is "decorated" with additional destination network addresses 692 using the Local Information Base, the Routable Address Topology Set 693 and the Attached Network Set. 695 The Topology Graph does not need to be recorded in the Topology 696 Information Base, it can either be constructed as required when the 697 Routing Set is to be changed, or need not be explicitly constructed 698 (as illustrated in Appendix B). An implementation may however 699 construct and retain the Topology Graph if preferred. 701 4.3.5. Received Message Information Base 703 The Received Message Information Base in each router contains: 705 o A Received Set for each OLSRv2 interface, describing TC messages 706 received by this router on that OLSRv2 interface. 708 o A Processed Set, describing TC messages processed by this router. 710 o A Forwarded Set, describing TC messages forwarded by this router. 712 The Received Message Information Base serves the MPR flooding 713 mechanism by ensuring that received messages are forwarded at most 714 once by a router, and also ensures that received messages are 715 processed exactly once by a router. The Received Message Information 716 Base may also record information about other Message Types that use 717 the MPR flooding mechanism. 719 4.4. Signaling Overview 721 This protocol generates and processes HELLO messages according to 722 [RFC6130]. HELLO messages transmitted on OLSRv2 interfaces are 723 extended according to Section 15 of this specification to include an 724 originator address, link metrics, and MPR selection information. 726 This specification defines a single Message Type, the TC message. TC 727 messages are sent by their originating router proactively, at a 728 regular interval, on all OLSRv2 interfaces. This interval may be 729 fixed, or may be dynamic, for example it may be backed off due to 730 congestion or network stability. TC messages may also be sent as a 731 response to a change in the router itself, or its advertised 732 symmetric 1-hop neighborhood, for example on first being selected as 733 a routing MPR. 735 Because TC messages are sent periodically, this protocol is tolerant 736 of unreliable transmissions of TC messages. Message losses may occur 737 more frequently in wireless networks due to collisions or other 738 transmission problems. This protocol may use "jitter", randomized 739 adjustments to message transmission times, to reduce the incidence of 740 collisions, as specified in [RFC5148]. 742 This protocol is tolerant of out of sequence delivery of TC messages 743 due to in transit message reordering. Each router maintains an 744 Advertised Neighbor Sequence Number (ANSN) that is incremented when 745 its recorded neighbor information that is to be included in its TC 746 messages changes. This ANSN is included in the router's TC messages. 747 The recipient of a TC message can use this included ANSN to identify 748 which of the information it has received is most recent, even if 749 messages have been reordered while in transit. Only the most recent 750 information received is used, older information received later is 751 discarded. 753 TC messages may be "complete" or "incomplete". A complete TC message 754 advertises all of the originating router's routing MPR selectors, it 755 may also advertise other symmetric 1-hop neighbors. Complete TC 756 messages are generated periodically (and also, optionally, in 757 response to symmetric 1-hop neighborhood changes). Incomplete TC 758 messages may be used to report additions to advertised information, 759 without repeating unchanged information. 761 TC messages, and HELLO messages as extended by this specification, 762 define (by inclusion, or by deduction when having a single address) 763 an originator address for the router that created the message. A TC 764 message reports both the originator addresses and routable addresses 765 of its advertised neighbors, distinguishing the two using an Address 766 Block TLV (an address may be both routable and an originator 767 address). TC messages also report the originator's locally attached 768 networks. 770 TC messages are MPR flooded throughout the MANET. A router 771 retransmits a TC message received on an OLSRv2 interface if and only 772 if the message did not originate at this router and has not been 773 previously forwarded by this router, this is the first time the 774 message has been received on this OLSRv2 interface, and the message 775 is received from (i.e., originated from or was last relayed by) one 776 of this router's flooding MPR selectors. 778 Some TC messages may be MPR flooded over only part of the network, 779 e.g., allowing a router to ensure that nearer routers are kept more 780 up to date than distant routers, such as is used in Fisheye State 781 Routing [FSR] and Fuzzy Sighted Link State routing [FSLS]. This is 782 enabled using [RFC5497]. 784 TC messages include outgoing neighbor metrics that will be used in 785 the selection of routes. 787 4.5. Link Metrics 789 OLSRv1 [RFC3626] created minimum hop routes to destinations. However 790 in many, if not most, circumstances, better routes (in terms of 791 quality of service for end users) can be created by use of link 792 metrics. 794 OLSRv2, as defined in this specification, supports metric-based 795 routing, i.e., it allows links to each have a chosen metric. Link 796 metrics as defined in OLSRv2 are additive, and the routes that are to 797 be created are those with the minimum sum of the link metrics along 798 that route. 800 Link metrics are defined to be directional; the link metric from one 801 router to another may be different from that on the reverse link. 802 The link metric is assessed at the receiver, as on a (typically) 803 wireless link, that is the better informed as to link information. 804 Both incoming and outgoing link information is used by OLSRv2, the 805 distinctions in this specification must be clearly followed. 807 This specification also defines both incoming and outgoing neighbor 808 metrics for each symmetric 1-hop neighbor, these being the minimum 809 value of the link metrics in the same direction for all symmetric 810 links with that neighbor. Note that this means that all neighbor 811 metric values are link metric values and that specification of, for 812 example, link metric value encoding also includes encoding of 813 neighbor metric values. 815 This specification does not define the nature of the link metric. 816 However, this specification allows, through use of the type extension 817 of a defined Address Block TLV, for link metrics with specific 818 meanings to be defined and either allocated by IANA or privately 819 used. Each HELLO or TC message carrying link (or neighbor) metrics 820 thus indicates which link metric information it is carrying, allowing 821 routers to determine if they can interoperate. If link metrics 822 require additional signaling to determine their values, whether in 823 HELLO messages or otherwise, then this is permitted but is outside 824 the scope of this specification. 826 Careful consideration should be given to how to use link metrics. In 827 particular it is advisable to not simply default to use of all links 828 with equal metrics (i.e., hop count) for routing without careful 829 consideration of whether that is appropriate or not. 831 4.6. Routing Set Use 833 The purpose of the Routing Set is to determine and record routes 834 (local interface network address and next hop interface network 835 address) to all possible routable addresses advertised by this 836 protocol, as well as of all destinations that are local, i.e., within 837 one hop, to the router (whether using routable addresses or not). 838 Only symmetric links are used in such routes. 840 It is intended that the Routing Set can be used for IP packet 841 routing, by using its contents to update the IP routing table. That 842 update, and whether any Routing Tuples are not used in the IP routing 843 table, is outside the scope of this specification. 845 The signaling in this specification has been designed so that a 846 "backbone" Topology Graph of routers, each identified by its 847 originator address, with at most one direct connection between any 848 pair of routers, can be constructed (from the Neighbor Set and the 849 Router Topology Set) using a suitable minimum path length algorithm. 850 This Topology Graph can then have other network addresses (routable, 851 or of symmetric 1-hop neighbors) added to it (using the Interface 852 Information Bases, the Routable Address Topology Set and the Attached 853 Network Set). 855 5. Protocol Parameters and Constants 857 The parameters and constants used in this specification are those 858 defined in [RFC6130] plus those defined in this section. The 859 separation in [RFC6130] into interface parameters, router parameters 860 and constants is also used in this specification. 862 As for the parameters in [RFC6130], parameters defined in this 863 specification MAY be changed dynamically by a router, and need not be 864 the same on different routers, even in the same MANET, or, for 865 interface parameters, on different interfaces of the same router. 867 5.1. Protocol and Port Numbers 869 This protocol specifies TC messages, which are included in packets as 870 defined by [RFC5444]. These packets MAY be sent either using the 871 "manet" protocol number or the "manet" UDP well-known port number, as 872 specified in [RFC5498]. 874 TC messages and HELLO messages [RFC6130] MUST, in a given MANET, both 875 be using the same of either of IP or UDP, in order that it is 876 possible to combine messages of both protocols into the same 877 [RFC5444] packet for transmission. 879 5.2. Multicast Address 881 This protocol specifies TC messages, which are included in packets as 882 defined by [RFC5444]. These packets MAY be transmitted using the 883 Link-Local multicast address "LL-MANET-Routers", as specified in 884 [RFC5498]. 886 5.3. Interface Parameters 888 A single additional interface parameter is specified for OLSRv2 889 interfaces only. 891 5.3.1. Received Message Validity Time 893 The following parameter manages the validity time of recorded 894 received message information: 896 RX_HOLD_TIME: 897 The period after receipt of a message by the appropriate OLSRv2 898 interface of this router for which that information is recorded, 899 in order that the message is recognized as having been previously 900 received on this OLSRv2 interface. 902 The following constraints apply to this parameter: 904 o RX_HOLD_TIME > 0 906 o RX_HOLD_TIME SHOULD be greater than the maximum difference in time 907 that a message may take to traverse the MANET, taking into account 908 any message forwarding jitter as well as propagation, queuing, and 909 processing delays. 911 5.4. Router Parameters 913 The following router parameters are specified for routers. 915 5.4.1. Local History Times 917 The following router parameter manages the time for which local 918 information is retained: 920 O_HOLD_TIME: 921 The time for which a recently used and replaced originator address 922 is used to recognize the router's own messages. 924 The following constraint applies to this parameter: 926 o O_HOLD_TIME > 0 928 5.4.2. Link Metric Parameters 930 All routes found using this specification use a single link metric 931 type that is specified by the router parameter LINK_METRIC_TYPE, 932 which may take any value from 0 to 255, both inclusive. 934 5.4.3. Message Intervals 936 The following parameters regulate TC message transmissions by a 937 router. TC messages are usually sent periodically, but MAY also be 938 sent in response to changes in the router's Neighbor Set and/or Local 939 Attached Network Set. In a highly dynamic network, and with a larger 940 value of the parameter TC_INTERVAL and a smaller value of the 941 parameter TC_MIN_INTERVAL, TC messages MAY be transmitted more often 942 in response to changes than periodically. However, because a router 943 has no knowledge of, for example, routers remote to it (i.e., beyond 944 two hops away) joining the network, TC messages MUST NOT be sent 945 purely responsively. 947 TC_INTERVAL: 948 The maximum time between the transmission of two successive TC 949 messages by this router. When no TC messages are sent in response 950 to local network changes (by design, or because the local network 951 is not changing) then TC messages MUST be sent at a regular 952 interval TC_INTERVAL, possibly modified by jitter as specified in 953 [RFC5148]. 955 TC_MIN_INTERVAL: 956 The minimum interval between transmission of two successive TC 957 messages by this router. (This minimum interval MAY be modified 958 by jitter, as specified in [RFC5148].) 960 The following constraints apply to these parameters: 962 o TC_INTERVAL > 0 964 o TC_MIN_INTERVAL >= 0 966 o TC_INTERVAL >= TC_MIN_INTERVAL 967 o If TLVs with Type = INTERVAL_TIME, as defined in [RFC5497], are 968 included in TC messages, then TC_INTERVAL MUST be representable as 969 described in [RFC5497]. 971 5.4.4. Advertised Information Validity Times 973 The following parameters manage the validity time of information 974 advertised in TC messages: 976 T_HOLD_TIME: 977 Used as the minimum value in the TLV with Type = VALIDITY_TIME 978 included in all TC messages sent by this router. If a single 979 value of parameter TC_HOP_LIMIT (see Section 5.4.7) is used then 980 this will be the only value in that TLV. 982 A_HOLD_TIME: 983 The period during which TC messages are sent after they no longer 984 have any advertised information to report, but are sent in order 985 to accelerate outdated information removal by other routers. 987 The following constraints apply to these parameters: 989 o T_HOLD_TIME > 0 991 o A_HOLD_TIME >= 0 993 o T_HOLD_TIME >= TC_INTERVAL 995 o If TC messages can be lost, then both T_HOLD_TIME and A_HOLD_TIME 996 SHOULD be significantly greater than TC_INTERVAL; a value >= 3 x 997 TC_INTERVAL is RECOMMENDED. 999 o T_HOLD_TIME MUST be representable as described in [RFC5497]. 1001 5.4.5. Processing and Forwarding Validity Times 1003 The following parameters manage the processing and forwarding 1004 validity time of recorded message information: 1006 P_HOLD_TIME: 1007 The period after receipt of a message that is processed by this 1008 router for which that information is recorded, in order that the 1009 message is not processed again if received again. 1011 F_HOLD_TIME: 1012 The period after receipt of a message that is forwarded by this 1013 router for which that information is recorded, in order that the 1014 message is not forwarded again if received again. 1016 The following constraints apply to these parameters: 1018 o P_HOLD_TIME > 0 1020 o F_HOLD_TIME > 0 1022 o Both of these parameters SHOULD be greater than the maximum 1023 difference in time that a message may take to traverse the MANET, 1024 taking into account any message forwarding jitter as well as 1025 propagation, queuing, and processing delays. 1027 5.4.6. Jitter 1029 If jitter, as defined in [RFC5148], is used then the governing jitter 1030 parameters are as follows: 1032 TP_MAXJITTER: 1033 Represents the value of MAXJITTER used in [RFC5148] for 1034 periodically generated TC messages sent by this router. 1036 TT_MAXJITTER: 1037 Represents the value of MAXJITTER used in [RFC5148] for externally 1038 triggered TC messages sent by this router. 1040 F_MAXJITTER: 1041 Represents the default value of MAXJITTER used in [RFC5148] for 1042 messages forwarded by this router. However, before using 1043 F_MAXJITTER a router MAY attempt to deduce a more appropriate 1044 value of MAXJITTER, for example based on any TLVs with Type = 1045 INTERVAL_TIME or Type = VALIDITY_TIME contained in the message to 1046 be forwarded. 1048 For constraints on these parameters see [RFC5148]. 1050 5.4.7. Hop Limit 1052 The parameter TC_HOP_LIMIT is the hop limit set in each TC message. 1053 TC_HOP_LIMIT MAY be a single fixed value, or MAY be different in TC 1054 messages sent by the same router. However each other router, at any 1055 hop count distance, MUST see a regular pattern of TC messages in 1056 order that meaningful values of TLVs with Type = INTERVAL_TIME and 1057 Type = VALIDITY_TIME at each hop count distance can be included as 1058 defined in [RFC5497]. Thus the pattern of TC_HOP_LIMIT MUST be 1059 defined to have this property. For example the repeating pattern 1060 (255 4 4) satisfies this property (having period TC_INTERVAL at hop 1061 counts up to 4, inclusive, and 3 x TC_INTERVAL at hop counts greater 1062 than 4), but the repeating pattern (255 255 4 4) does not satisfy 1063 this property because at hop counts greater than 4, message intervals 1064 are alternately TC_INTERVAL and 3 x TC_INTERVAL. 1066 The following constraints apply to this parameter: 1068 o The maximum value of TC_HOP_LIMIT >= the network diameter in hops, 1069 a value of 255 is RECOMMENDED. Note that if using a pattern of 1070 different values of TC_HOP_LIMIT as described above, then only the 1071 maximum value in the pattern is so constrained. 1073 o All values of TC_HOP_LIMIT >= 2. 1075 5.4.8. Willingness 1077 Each router has two willingness parameters: WILL_FLOODING and 1078 WILL_ROUTING, each of which MUST be in the range WILL_NEVER to 1079 WILL_ALWAYS, inclusive. 1081 WILL_FLOODING represents the router's willingness to be selected as a 1082 flooding MPR and hence to participate in MPR flooding, in particular 1083 of TC messages. 1085 WILL_ROUTING represents the router's willingness to be selected as a 1086 routing MPR and hence to be an intermediate router on routes. 1088 In either case, the higher the value, the greater the router's 1089 willingness to be a flooding or routing MPR, respectively. If a 1090 router has a willingness value of WILL_NEVER (the lowest possible 1091 value) it does not perform the corresponding task. A MANET using 1092 this protocol with too many routers having either willingness value 1093 equal to WILL_NEVER will not function; it MUST be ensured, by 1094 administrative or other means, that this does not happen. 1096 If a router has a willingness value equal to WILL_ALWAYS (the highest 1097 possible value) then it will always be selected as a flooding or 1098 routing MPR, respectively, by all symmetric 1-hop neighbors. 1100 In a MANET in which all routers have WILL_FLOODING = WILL_ALWAYS, 1101 flooding reduction will effectively be disabled, and flooding will 1102 perform as blind flooding. 1104 In a MANET in which all routers have WILL_ROUTING = WILL_ALWAYS, 1105 topology reduction will effectively be disabled, and all routers will 1106 advertise all of their links in TC messages. 1108 A router that has WILL_ROUTING = WILL_NEVER will not act as an 1109 intermediate router in the MANET. Such a router can, act as a 1110 source, destination or gateway to another routing domain. 1112 Different routers MAY have different values for WILL_FLOODING and/or 1113 WILL_ROUTING. 1115 The following constraints apply to these parameters: 1117 o WILL_FLOODING >= WILL_NEVER 1119 o WILL_FLOODING <= WILL_ALWAYS 1121 o WILL_ROUTING >= WILL_NEVER 1123 o WILL_ROUTING <= WILL_ALWAYS 1125 5.5. Parameter Change Constraints 1127 If protocol parameters are changed dynamically, then the constraints 1128 in this section apply. 1130 RX_HOLD_TIME 1132 * If RX_HOLD_TIME for an OLSRv2 interface changes, then the 1133 expiry time for all Received Tuples for that OLSRv2 interface 1134 MAY be changed. 1136 O_HOLD_TIME 1138 * If O_HOLD_TIME changes, then the expiry time for all Originator 1139 Tuples MAY be changed. 1141 TC_INTERVAL 1143 * If TC_INTERVAL increases, then the next TC message generated by 1144 this router MUST be generated according to the previous, 1145 shorter, TC_INTERVAL. Additional subsequent TC messages MAY be 1146 generated according to the previous, shorter, TC_INTERVAL. 1148 * If TC_INTERVAL decreases, then the following TC messages from 1149 this router MUST be generated according to the current, 1150 shorter, TC_INTERVAL. 1152 P_HOLD_TIME 1154 * If P_HOLD_TIME changes, then the expiry time for all Processed 1155 Tuples MAY be changed. 1157 F_HOLD_TIME 1159 * If F_HOLD_TIME changes, then the expiry time for all Forwarded 1160 Tuples MAY be changed. 1162 TP_MAXJITTER 1164 * If TP_MAXJITTER changes, then the periodic TC message schedule 1165 on this router MAY be changed immediately. 1167 TT_MAXJITTER 1169 * If TT_MAXJITTER changes, then externally triggered TC messages 1170 on this router MAY be rescheduled. 1172 F_MAXJITTER 1174 * If F_MAXJITTER changes, then TC messages waiting to be 1175 forwarded with a delay based on this parameter MAY be 1176 rescheduled. 1178 TC_HOP_LIMIT 1180 * If TC_HOP_LIMIT changes, and the router uses multiple values 1181 after the change, then message intervals and validity times 1182 included in TC messages MUST be respected. The simplest way to 1183 do this is to start any new repeating pattern of TC_HOP_LIMIT 1184 values with its largest value. 1186 LINK_METRIC_TYPE 1188 * If LINK_METRIC_TYPE changes, then all link metric information 1189 recorded by the router is invalid. The router MUST take the 1190 following actions, and all consequent actions described in 1191 Section 17 and [RFC6130]. 1193 + For each Link Tuple in any Link Set for an OLSRv2 interface, 1194 either update L_in_metric (the value MAXIMUM_METRIC MAY be 1195 used) or remove the Link Tuple from the Link Set. 1197 + For each Link Tuple that is not removed, set: 1199 - L_out_metric := UNKNOWN_METRIC; 1201 - L_SYM_time := expired; 1203 - L_MPR_selector := false. 1205 + Remove all Router Topology Tuples, Routable Address Topology 1206 Tuples, Attached Network Tuples and Routing Tuples from 1207 their respective Protocol Sets in the Topology Information 1208 Base. 1210 5.6. Constants 1212 The following constants are specified for routers. Unlike router 1213 parameters, constants MUST NOT change, and MUST be the same on all 1214 routers. 1216 5.6.1. Link Metric Constants 1218 The constant minimum and maximum link metric values are defined by: 1220 o MINIMUM_METRIC := 1 1222 o MAXIMUM_METRIC := 16776960 1224 The symbolic value UNKNOWN_METRIC is defined in Section 6.1. 1226 5.6.2. Willingness Constants 1228 The constant minimum, RECOMMENDED default, and maximum, willingness 1229 values are defined by: 1231 o WILL_NEVER := 0 1233 o WILL_DEFAULT := 7 1235 o WILL_ALWAYS := 15 1237 6. Link Metric Values 1239 A router records a link metric value for each direction of a link of 1240 which it has knowledge. These link metric values are used to create 1241 metrics for routes by the addition of link metric values. 1243 6.1. Link Metric Representation 1245 Link metrics are reported in messages using a compressed 1246 representation that occupies 12 bits, a 4 bit field and an 8 bit 1247 field. The compressed representation represents positive integer 1248 values with a minimum value of 1 and a maximum value that is slightly 1249 smaller than the maximum 24 bit value. Only those values that have 1250 exact representation in the compressed form are used. Route metrics 1251 are the summation of no more than 255 link metric values, and can 1252 therefore be represented using no more than 32 bits. 1254 Link and route metrics used in the Information Bases defined in this 1255 specification refer to the uncompressed values, and arithmetic 1256 involving them does likewise, and assumes full precision in the 1257 result. (How an implementation records the values is not part of 1258 this specification, as long as it behaves as if recording 1259 uncompressed values. An implementation can, for example, use 32 bit 1260 values for all link and route metrics.) 1262 In some cases a link metric value may be unknown. This is indicated 1263 in this specification by the symbolic value UNKNOWN_METRIC. An 1264 implementation may use any representation of UNKNOWN_METRIC as it is 1265 never included in messages, or used in any computation. (Possible 1266 representations are zero, or any value greater than the maximum 1267 representable metric value.) 1269 6.2. Link Metric Compressed Form 1271 The 12-bit compressed form of a link metric uses a modified form of a 1272 representation with an 8-bit mantissa (denoted b) and a 4-bit 1273 exponent (denoted a). Note that if represented as the 12 bit value 1274 256a+b then the ordering of those 12 bit values is identical to the 1275 ordering of the represented values. 1277 The value so represented is (257+b)2^a - 256, where ^ denotes 1278 exponentiation. This has a minimum value (when a = 0 and b = 0) of 1279 MINIMUM_METRIC = 1 and a maximum value (when a = 15 and b = 255) of 1280 MAXIMUM_METRIC = 2^24 - 256. 1282 An algorithm for computing a and b for the smallest representable 1283 value not less than a link metric value v such that MINIMUM_METRIC <= 1284 v <= MAXIMUM_METRIC is: 1286 1. Find the smallest integer a such that v + 256 <= 2^(a + 9). 1288 2. Set b := (v - 256(2^a - 1)) / (2^a) - 1, rounded up to the 1289 nearest integer. 1291 7. Local Information Base 1293 The Local Information Base, as defined for each router in [RFC6130], 1294 is extended by this protocol by: 1296 o Recording the router's originator address. The originator address 1297 MUST be unique to this router. It MUST NOT be used by any other 1298 router as an originator address. It MAY be included in any 1299 network address in any I_local_iface_addr_list of this router, it 1300 MUST NOT be included in any network address in any 1301 I_local_iface_addr_list of any other router. It MAY be included 1302 in, but MUST NOT be equal to, the AL_net_addr in any Local 1303 Attached Network Tuple in this or any other router. 1305 o The addition of an Originator Set, defined in Section 7.1, and a 1306 Local Attached Network Set, defined in Section 7.2. 1308 All routable addresses of the router for which it is to accept IP 1309 packets as destination MUST be included in the Local Interface Set or 1310 the Local Attached Network Set. 1312 7.1. Originator Set 1314 A router's Originator Set records addresses that were recently used 1315 as originator addresses by this router. If a router's originator 1316 address is immutable then the Originator Set is always empty and MAY 1317 be omitted. It consists of Originator Tuples: 1319 (O_orig_addr, O_time) 1321 where: 1323 O_orig_addr is a recently used originator address; note that this 1324 does not include a prefix length. 1326 O_time specifies the time at which this Tuple expires and MUST be 1327 removed. 1329 7.2. Local Attached Network Set 1331 A router's Local Attached Network Set records its local non-OLSRv2 1332 interfaces via which it can act as gateways to other networks. The 1333 Local Attached Network Set is not modified by this protocol. This 1334 protocol MAY respond to changes to the Local Attached Network Set, 1335 which MUST reflect corresponding changes in the router's status. It 1336 consists of Local Attached Network Tuples: 1338 (AL_net_addr, AL_dist, AL_metric) 1340 where: 1342 AL_net_addr is the network address of an attached network which 1343 can be reached via this router. This SHOULD be a routable 1344 address. It is constrained as described below. 1346 AL_dist is the number of hops to the network with network address 1347 AL_net_addr from this router. 1349 AL_metric is the metric of the link to the attached network with 1350 address AL_net_addr from this router. 1352 Attached networks local to this router only (i.e., not reachable 1353 except via this router) SHOULD be treated as local non-MANET 1354 interfaces, and added to the Local Interface Set, as specified in 1355 [RFC6130], rather than be added to the Local Attached Network Set. 1357 Because an attached network is not specific to the router, and may be 1358 outside the MANET, an attached network MAY also be attached to other 1359 routers. Routing to an AL_net_addr will use maximum prefix length 1360 matching; consequently an AL_net_addr MAY include, but MUST NOT equal 1361 or be included in, any network address which is of any interface of 1362 any router (i.e., is included in any I_local_iface_addr_list) or 1363 equal any router's originator address. 1365 It is not the responsibility of this protocol to maintain routes from 1366 this router to networks recorded in the Local Attached Network Set. 1368 Local Attached Neighbor Tuples are removed from the Local Attached 1369 Network Set only when the router's local attached network 1370 configuration changes, i.e., they are not subject to timer-based 1371 expiration or changes due to received messages. 1373 8. Interface Information Base 1375 An Interface Information Base, as defined in [RFC6130], is maintained 1376 for each MANET interface. The Link Set and 2-Hop Set in the 1377 Interface Information Base for an OLSRv2 interface are modified by 1378 this protocol. In some cases it may be convenient to consider these 1379 Sets as also containing these additional elements for other MANET 1380 interfaces, taking the indicated values on creation, but never being 1381 updated. 1383 8.1. Link Set 1385 The Link Set is modified by adding these additional elements to each 1386 Link Tuple: 1388 L_in_metric is the metric of the link from the OLSRv2 interface 1389 with addresses L_neighbor_iface_addr_list to this OLSRv2 1390 interface; 1392 L_out_metric is the metric of the link to the OLSRv2 interface 1393 with addresses L_neighbor_iface_addr_list from this OLSRv2 1394 interface; 1395 L_mpr_selector is a boolean flag, describing if this neighbor has 1396 selected this router as a flooding MPR, i.e., is a flooding MPR 1397 selector of this router. 1399 L_in_metric will be specified by a process that is external to this 1400 specification. Any Link Tuple with L_status = HEARD or L_status = 1401 SYMMETRIC MUST have a specified value of L_in_metric if it is to be 1402 used by this protocol. 1404 A Link Tuple created (but not updated) by [RFC6130] MUST set: 1406 o L_in_metric := UNKNOWN_METRIC; 1408 o L_out_metric := UNKNOWN_METRIC; 1410 o L_mpr_selector := false. 1412 8.2. 2-Hop Set 1414 The 2-Hop Set is modified by adding these additional elements to each 1415 2-Hop Tuple: 1417 N2_in_metric is the neighbor metric from the router with address 1418 N2_2hop_iface_addr to the router with OLSRv2 interface addresses 1419 N2_neighbor_iface_addr_list; 1421 N2_out_metric is the neighbor metric to the router with address 1422 N2_2hop_iface_addr from the router with OLSRv2 interface addresses 1423 N2_neighbor_iface_addr_list. 1425 A 2-Hop Tuple created (but not updated) by [RFC6130] MUST set: 1427 o N2_in_metric := UNKNOWN_METRIC; 1429 o N2_out_metric := UNKNOWN_METRIC. 1431 9. Neighbor Information Base 1433 A Neighbor Information Base, as defined in [RFC6130], is maintained 1434 for each router. It is modified by this protocol by adding these 1435 additional elements to each Neighbor Tuple in the Neighbor Set. In 1436 some cases it may be convenient to consider these Sets as also 1437 containing these additional elements for other MANET interfaces, 1438 taking the indicated values on creation, but never being updated. 1440 N_orig_addr is the neighbor's originator address, which may be 1441 unknown. Note that this originator address does not include a 1442 prefix length; 1443 N_in_metric is the neighbor metric of any link from this neighbor 1444 to an OLSRv2 interface of this router, i.e., the minimum of all 1445 corresponding L_in_metric with L_status = SYMMETRIC and 1446 L_in_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no such 1447 Link Tuples; 1449 N_out_metric is the neighbor metric of any link from an OLSRv2 1450 interface of this router to this neighbor, i.e., the minimum of 1451 all corresponding L_out_metric with L_status = SYMMETRIC and 1452 L_out_metric != UNKNOWN_METRIC, UNKNOWN_METRIC if there are no 1453 such Link Tuples; 1455 N_will_flooding is the neighbor's willingness to be selected as a 1456 flooding MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1457 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1458 information is received from this neighbor; 1460 N_will_routing is the neighbor's willingness to be selected as a 1461 routing MPR, in the range from WILL_NEVER to WILL_ALWAYS, both 1462 inclusive, taking the value WILL_NEVER if no OLSRv2 specific 1463 information is received from this neighbor; 1465 N_flooding_mpr is a boolean flag, describing if this neighbor is 1466 selected as a flooding MPR by this router; 1468 N_routing_mpr is a boolean flag, describing if this neighbor is 1469 selected as a routing MPR by this router; 1471 N_mpr_selector is a boolean flag, describing if this neighbor has 1472 selected this router as a routing MPR, i.e., is a routing MPR 1473 selector of this router. 1475 N_advertised is a boolean flag, describing if this router has 1476 elected to advertise a link to this neighbor in its TC messages. 1478 A Neighbor Tuple created (but not updated) by [RFC6130] MUST set: 1480 o N_orig_addr := unknown; 1482 o N_in_metric := UNKNOWN_METRIC; 1484 o N_out_metric := UNKNOWN_METRIC; 1486 o N_will_flooding := WILL_NEVER; 1488 o N_will_routing := WILL_NEVER; 1489 o N_routing_mpr := false; 1491 o N_flooding_mpr := false; 1493 o N_mpr_selector := false; 1495 o N_advertised := false. 1497 The Neighbor Information Base also includes a variable, the 1498 Advertised Neighbor Sequence Number (ANSN), whose value is included 1499 in TC messages to indicate the freshness of the information 1500 transmitted. The ANSN is incremented whenever advertised information 1501 (the originator and routable addresses included in Neighbor Tuples 1502 with N_advertised = true, and local attached networks recorded in the 1503 Local Attached Network Set in the Local Information Base) changes, 1504 including addition or removal of such information. 1506 10. Topology Information Base 1508 The Topology Information Base, defined for each router by this 1509 specification, stores information received in TC messages, in the 1510 Advertising Remote Router Set, the Router Topology Set, the Routable 1511 Address Topology Set and the Attached Network Set. 1513 Additionally, a Routing Set is maintained, derived from the 1514 information recorded in the Local Information Base, the Interface 1515 Information Bases, the Neighbor Information Base and the rest of the 1516 Topology Information Base. 1518 10.1. Advertising Remote Router Set 1520 A router's Advertising Remote Router Set records information 1521 describing each remote router in the network that transmits TC 1522 messages, allowing outdated TC messages to be recognized and 1523 discarded. It consists of Advertising Remote Router Tuples: 1525 (AR_orig_addr, AR_seq_number, AR_time) 1527 where: 1529 AR_orig_addr is the originator address of a received TC message, 1530 note that this does not include a prefix length; 1532 AR_seq_number is the greatest ANSN in any TC message received 1533 which originated from the router with originator address 1534 AR_orig_addr (i.e., which contributed to the information contained 1535 in this Tuple); 1536 AR_time is the time at which this Tuple expires and MUST be 1537 removed. 1539 10.2. Router Topology Set 1541 A router's Topology Set records topology information about the links 1542 between routers in the MANET. It consists of Router Topology Tuples: 1544 (TR_from_orig_addr, TR_to_orig_addr, TR_seq_number, TR_metric, 1545 TR_time) 1547 where: 1549 TR_from_orig_addr is the originator address of a router which can 1550 reach the router with originator address TR_to_orig_addr in one 1551 hop, note that this does not include a prefix length; 1553 TR_to_orig_addr is the originator address of a router which can be 1554 reached by the router with originator address TR_to_orig_addr in 1555 one hop, note that this does not include a prefix length; 1557 TR_seq_number is the greatest ANSN in any TC message received 1558 which originated from the router with originator address 1559 TR_from_orig_addr (i.e., which contributed to the information 1560 contained in this Tuple); 1562 TR_metric is the neighbor metric from the router with originator 1563 address TR_from_orig_addr to the router with originator address 1564 TR_to_orig_addr; 1566 TR_time specifies the time at which this Tuple expires and MUST be 1567 removed. 1569 10.3. Routable Address Topology Set 1571 A router's Routable Address Topology Set records topology information 1572 about the routable addresses within the MANET, and via which routers 1573 they may be reached. It consists of Routable Address Topology 1574 Tuples: 1576 (TA_from_orig_addr, TA_dest_addr, TA_seq_number, TA_metric, 1577 TA_time) 1579 where: 1581 TA_from_orig_addr is the originator address of a router which can 1582 reach the router with routable address TA_dest_addr in one hop, 1583 note that this does not include a prefix length; 1584 TA_dest_addr is a routable address of a router which can be 1585 reached by the router with originator address TA_from_orig_addr in 1586 one hop; 1588 TA_seq_number is the greatest ANSN in any TC message received 1589 which originated from the router with originator address 1590 TA_from_orig_addr (i.e., which contributed to the information 1591 contained in this Tuple); 1593 TA_metric is the neighbor metric from the router with originator 1594 address TA_from_orig_addr to the router with OLSRv2 interface 1595 address TA_dest_addr; 1597 TA_time specifies the time at which this Tuple expires and MUST be 1598 removed. 1600 10.4. Attached Network Set 1602 A router's Attached Network Set records information about networks 1603 (which may be outside the MANET) attached to other routers and their 1604 routable addresses. It consists of Attached Network Tuples: 1606 (AN_orig_addr, AN_net_addr, AN_seq_number, AN_dist, AN_metric, 1607 AN_time) 1609 where: 1611 AN_orig_addr is the originator address of a router which can act 1612 as gateway to the network with network address AN_net_addr, note 1613 that this does not include a prefix length; 1615 AN_net_addr is the network address of an attached network, which 1616 may be reached via the router with originator address 1617 AN_orig_addr; 1619 AN_seq_number is the greatest ANSN in any TC message received 1620 which originated from the router with originator address 1621 AN_orig_addr (i.e., which contributed to the information contained 1622 in this Tuple); 1624 AN_dist is the number of hops to the network with network address 1625 AN_net_addr from the router with originator address AN_orig_addr; 1627 AN_metric is the metric of the link from the router with 1628 originator address AN_orig_addr to the attached network with 1629 address AN_net_addr; 1630 AN_time specifies the time at which this Tuple expires and MUST be 1631 removed. 1633 10.5. Routing Set 1635 A router's Routing Set records the first hop along a selected path to 1636 each destination for which any such path is known. It consists of 1637 Routing Tuples: 1639 (R_dest_addr, R_next_iface_addr, R_local_iface_addr, R_dist, 1640 R_metric) 1642 where: 1644 R_dest_addr is the network address of the destination, either the 1645 network address of an interface of a destination router, or the 1646 network address of an attached network; 1648 R_next_iface_addr is the network address of the "next hop" on the 1649 selected path to the destination; 1651 R_local_iface_addr is an address of the local interface over which 1652 an IP packet MUST be sent to reach the destination by the selected 1653 path. 1655 R_dist is the number of hops on the selected path to the 1656 destination; 1658 R_metric is the metric of the route to the destination with 1659 address R_dest_addr. 1661 The Routing Set for a router is derived from the contents of other 1662 Protocol Sets of the router (the Link Sets, the Neighbor Set, the 1663 Router Topology Set, the Routable Address Topology Set, the Attached 1664 Network Set, and OPTIONAL use of the 2-Hop Sets). The Routing Set is 1665 updated (Routing Tuples added or removed, or the complete Routing Set 1666 recalculated) when routing paths are calculated, based on changes to 1667 these other Protocol Sets. Routing Tuples are not subject to timer- 1668 based expiration. 1670 11. Received Message Information Base 1672 The Received Message Information Base, defined by this specification, 1673 records information required to ensure that a message is processed at 1674 most once and is forwarded at most once per OLSRv2 interface of a 1675 router, using MPR flooding. Messages are recorded using their 1676 "signature", consisting of their type, originator address, and 1677 message sequence number. 1679 11.1. Received Set 1681 A router has a Received Set per OLSRv2 interface. Each Received Set 1682 records the signatures of messages which have been received over that 1683 OLSRv2 interface. Each consists of Received Tuples: 1685 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 1687 where: 1689 RX_type is the received Message Type; 1691 RX_orig_addr is the originator address of the received message, 1692 note that this does not include a prefix length; 1694 RX_seq_number is the message sequence number of the received 1695 message; 1697 RX_time specifies the time at which this Tuple expires and MUST be 1698 removed. 1700 11.2. Processed Set 1702 A router has a single Processed Set which records signatures of 1703 messages which have been processed by the router. It consists of 1704 Processed Tuples: 1706 (P_type, P_orig_addr, P_seq_number, P_time) 1708 where: 1710 P_type is the processed Message Type; 1712 P_orig_addr is the originator address of the processed message, 1713 note that this does not include a prefix length; 1715 P_seq_number is the message sequence number of the processed 1716 message; 1718 P_time specifies the time at which this Tuple expires and MUST be 1719 removed. 1721 11.3. Forwarded Set 1723 A router has a single Forwarded Set which records signatures of 1724 messages which have been forwarded by the router. It consists of 1725 Forwarded Tuples: 1727 (F_type, F_orig_addr, F_seq_number, F_time) 1729 where: 1731 F_type is the forwarded Message Type; 1733 F_orig_addr is the originator address of the forwarded message, 1734 note that this does not include a prefix length; 1736 F_seq_number is the message sequence number of the forwarded 1737 message; 1739 F_time specifies the time at which this Tuple expires and MUST be 1740 removed. 1742 12. Information Base Properties 1744 This section describes some additional properties of Information 1745 Bases and their contents. 1747 12.1. Corresponding Protocol Tuples 1749 As part of this specification, in a number of cases there is a 1750 natural correspondence from a Protocol Tuple in one Protocol Set to a 1751 single Protocol Tuple in another Protocol Set, in the same or another 1752 Information Base. The latter Protocol Tuple is referred to as 1753 "corresponding" to the former Protocol Tuple. 1755 Specific examples of corresponding Protocol Tuples include: 1757 o There is a Local Interface Tuple corresponding to each Link Tuple, 1758 where the Link Tuple is in the Link Set for a MANET interface, and 1759 the Local Interface Tuple represents that MANET interface. 1761 o There is a Neighbor Tuple corresponding to each Link Tuple which 1762 has L_HEARD_time not expired, such that N_neighbor_addr_list 1763 contains L_neighbor_iface_addr_list. 1765 o There is a Link Tuple (in the Link Set in the same Interface 1766 Information Base) corresponding to each 2-Hop Tuple such that 1767 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 1769 o There is a Neighbor Tuple corresponding to each 2-Hop Tuple, such 1770 that N_neighbor_addr_list contains N2_neighbor_iface_addr_list. 1771 (This is the Neighbor Tuple corresponding to the Link Tuple 1772 corresponding to the 2-Hop Tuple.) 1774 o There is an Advertising Remote Router Tuple corresponding to each 1775 Router Topology Tuple such that AR_orig_addr = TR_from_orig_addr. 1777 o There is an Advertising Remote Router Tuple corresponding to each 1778 Routable Address Topology Tuple such that AR_orig_addr = 1779 TA_from_orig_addr. 1781 o There is an Advertising Remote Router Tuple corresponding to each 1782 Attached Network Tuple such that AR_orig_addr = AN_orig_addr. 1784 o There is a Neighbor Tuple corresponding to each Routing Tuple such 1785 that N_neighbor_addr_list contains R_next_iface_addr. 1787 12.2. Address Ownership 1789 Addresses or network addresses with the following properties are 1790 considered as "fully owned" by a router when processing a received 1791 message: 1793 o Equaling its originator address, OR; 1795 o Equaling the O_orig_addr in an Originator Tuple, OR; 1797 o Equaling or being a sub-range of the I_local_iface_addr_list in a 1798 Local Interface Tuple, OR; 1800 o Equaling or being a sub-range of the IR_local_iface_addr in a 1801 Removed Interface Address Tuple, OR; 1803 o Equaling an AL_net_addr in a Local Attached Network Tuple. 1805 Addresses or network addresses with the following properties are 1806 considered as "partially owned" (which may include being fully owned) 1807 by a router when processing a received message: 1809 o Overlapping (equaling or containing) its originator address, OR; 1811 o Overlapping (equaling or containing) the O_orig_addr in an 1812 Originator Tuple, OR; 1814 o Overlapping the I_local_iface_addr_list in a Local Interface 1815 Tuple, OR; 1817 o Overlapping the IR_local_iface_addr in a Removed Interface Address 1818 Tuple, OR; 1820 o Equaling or having as a sub-range an AL_net_addr in a Local 1821 Attached Network Tuple. 1823 13. Packets and Messages 1825 The packet and message format used by this protocol is defined in 1826 [RFC5444]. Except as otherwise noted, options defined in [RFC5444] 1827 may be freely used, in particular alternative formats defined by 1828 packet, message, Address Block and TLV flags. 1830 This section describes the usage of the packets and messages defined 1831 in [RFC5444] by this specification, and the TLVs defined by, and used 1832 in, this specification. 1834 13.1. Messages 1836 Routers using this protocol exchange information through messages. 1837 The message types used by this protocol are the HELLO message and the 1838 TC message. The HELLO message is defined by [RFC6130] and extended 1839 by this specification, see Section 15. The TC message is defined by 1840 this specification, see Section 16. 1842 13.2. Packets 1844 One or more messages sent by a router at the same time SHOULD be 1845 combined into a single packet, subject to any constraints on maximum 1846 packet size (such as derived from the MTU over a local single hop) 1847 that MAY be imposed. These messages may have originated at the 1848 sending router, or have originated at another router and are being 1849 forwarded by the sending router. Messages with different originating 1850 routers MAY be combined for transmission within the same packet. 1851 Messages from other protocols defined using [RFC5444], including but 1852 not limited to [RFC6130], MAY be combined for transmission within the 1853 same packet. This specification does not define or use any contents 1854 of the Packet Header. 1856 Forwarded messages MAY be jittered as described in [RFC5148], 1857 including the observation that the forwarding jitter of all messages 1858 received in a single packet SHOULD be the same. The value of 1859 MAXJITTER used in jittering a forwarded message MAY be based on 1860 information in that message (in particular any Message TLVs with Type 1861 = INTERVAL_TIME or Type = VALIDITY_TIME) or otherwise SHOULD be with 1862 a maximum delay of F_MAXJITTER. A router MAY modify the jitter 1863 applied to a message in order to more efficiently combine messages in 1864 packets, as long as the maximum jitter is not exceeded. 1866 13.3. TLVs 1868 This specification defines two Message TLVs and four Address Block 1869 TLVs. 1871 All references in this specification to TLVs that do not indicate a 1872 type extension, assume Type Extension = 0. TLVs in processed 1873 messages with a type extension which is neither zero as so assumed, 1874 nor a specifically indicated non-zero type extension, are ignored. 1876 13.3.1. Message TLVs 1878 The MPR_WILLING TLV is used in HELLO messages. A message MUST NOT 1879 contain more than one MPR_WILLING TLV. 1881 +-------------+--------------+--------------------------------------+ 1882 | Type | Value Length | Value | 1883 +-------------+--------------+--------------------------------------+ 1884 | MPR_WILLING | 1 octet | Bits 0-3 encode the parameter | 1885 | | | WILL_FLOODING; bits 4-7 encode the | 1886 | | | parameter WILL_ROUTING. | 1887 +-------------+--------------+--------------------------------------+ 1889 Table 1: MPR_WILLING TLV definition 1891 The CONT_SEQ_NUM TLV is used in TC messages. A message MUST NOT 1892 contain more than one CONT_SEQ_NUM TLV. 1894 +--------------+--------------+-------------------------------------+ 1895 | Type | Value Length | Value | 1896 +--------------+--------------+-------------------------------------+ 1897 | CONT_SEQ_NUM | 2 octets | The ANSN contained in the Neighbor | 1898 | | | Information Base. | 1899 +--------------+--------------+-------------------------------------+ 1901 Table 2: CONT_SEQ_NUM TLV definition 1903 13.3.2. Address Block TLVs 1905 The LINK_METRIC TLV is used in HELLO messages and TC messages. It 1906 MAY use any type extension; only LINK_METRIC TLVs with type extension 1907 equal to LINK_METRIC_TYPE will be used by this specification. An 1908 address MUST NOT be associated with more than one link metric value 1909 for any given type extension, kind (link or neighbor) and direction 1910 using this TLV. 1912 +-------------+--------------+--------------------------------------+ 1913 | Type | Value Length | Value | 1914 +-------------+--------------+--------------------------------------+ 1915 | LINK_METRIC | 2 octets | Bits 0-3 indicates kind(s) and | 1916 | | | direction(s), bits 4-7 indicate | 1917 | | | exponent (a), bits 8-15 indicate | 1918 | | | mantissa (b) | 1919 +-------------+--------------+--------------------------------------+ 1921 Table 3: LINK_METRIC TLV definition 1923 The exponent and mantissa use the representation defined in 1924 Section 6. Each bit of the types and directions sub-field, if set 1925 ('1') indicates that the link metric is of the indicated kind and 1926 direction. Any combination of these bits MAY be used. 1928 +-----+-----------------+-----------+ 1929 | Bit | Kind | Direction | 1930 +-----+-----------------+-----------+ 1931 | 0 | Link metric | Incoming | 1932 | 1 | Link metric | Outgoing | 1933 | 2 | Neighbor metric | Incoming | 1934 | 3 | Neighbor metric | Outgoing | 1935 +-----+-----------------+-----------+ 1937 Table 4: LINK_METRIC TLV types and directions 1939 The MPR TLV is used in HELLO messages, and indicates that an address 1940 with which it is associated is of a symmetric 1-hop neighbor that has 1941 been selected as an MPR. 1943 +------+--------------+---------------------------------------------+ 1944 | Type | Value Length | Value | 1945 +------+--------------+---------------------------------------------+ 1946 | MPR | 1 octet | FLOODING indicates that the corresponding | 1947 | | | address is of a neighbor selected as a | 1948 | | | flooding MPR, ROUTING indicates that the | 1949 | | | corresponding address is of a neighbor | 1950 | | | selected as a routing MPR, FLOOD_ROUTE | 1951 | | | indicates both (see Section 24.6). | 1952 +------+--------------+---------------------------------------------+ 1954 Table 5: MPR TLV definition 1956 The NBR_ADDR_TYPE TLV is used in TC messages. 1958 +---------------+--------------+------------------------------------+ 1959 | Type | Value Length | Value | 1960 +---------------+--------------+------------------------------------+ 1961 | NBR_ADDR_TYPE | 1 octet | ORIGINATOR indicates that the | 1962 | | | corresponding address (which MUST | 1963 | | | have maximum prefix length) is an | 1964 | | | originator address, ROUTABLE | 1965 | | | indicates that the corresponding | 1966 | | | network address is a routable | 1967 | | | address of an interface, | 1968 | | | ROUTABLE_ORIG indicates that the | 1969 | | | corresponding address is both (see | 1970 | | | Section 24.6). | 1971 +---------------+--------------+------------------------------------+ 1973 Table 6: NBR_ADDR_TYPE TLV definition 1975 If an address is both an originator address and a routable address, 1976 then it may be associated with either one Address Block TLV with Type 1977 := NBR_ADDR_TYPE and Value := ROUTABLE_ORIG, or with two Address 1978 Block TLVs with Type:= NBR_ADDR_TYPE, one with Value := ORIGINATOR 1979 and one with Value := ROUTABLE. 1981 The GATEWAY TLV is used in TC messages. An address MUST NOT be 1982 associated with more than one hop count value using this TLV. 1984 +---------+--------------+-------------------------------------+ 1985 | Type | Value Length | Value | 1986 +---------+--------------+-------------------------------------+ 1987 | GATEWAY | 1 octet | Number of hops to attached network. | 1988 +---------+--------------+-------------------------------------+ 1990 Table 7: GATEWAY TLV definition 1992 All address objects included in a TC message according to this 1993 specification MUST be associated either with at least one TLV with 1994 Type := NBR_ADDR_TYPE or with a TLV with Type := GATEWAY, but not 1995 both. Any other address objects MAY be included in Address Blocks in 1996 a TC message, but are ignored by this specification. 1998 14. Message Processing and Forwarding 2000 This section describes the optimized flooding operation (MPR 2001 flooding) used when control messages, as instances of [RFC5444], are 2002 intended for MANET wide distribution. This flooding mechanism 2003 defines when a received message is, or is not, processed and/or 2004 forwarded. 2006 This flooding mechanism is used by this protocol and MAY be used by 2007 extensions to this protocol which define, and hence own, other 2008 Message Types, to manage processing and/or forwarding of these 2009 messages. This specification contains elements (P_type, RX_type, 2010 F_type) required only for such usage. 2012 This flooding mechanism is always used for TC messages (see 2013 Section 16). Received HELLO messages (see Section 15) are, unless 2014 invalid, always processed, and never forwarded by this flooding 2015 mechanism. They thus do not need to be recorded in the Received 2016 Message Information Base. 2018 The processing selection and forwarding mechanisms are designed to 2019 only need to parse the Message Header in order to determine whether a 2020 message is to be processed and/or forwarded, and not to have to parse 2021 the Message Body even if the message is forwarded (but not 2022 processed). An implementation MAY only parse the Message Body if 2023 necessary, or MAY always parse the Message Body and reject the 2024 message if it cannot be so parsed, or any other error is identified. 2026 An implementation MUST discard the message silently if it is unable 2027 to parse the Message Header or (if attempted) the Message Body, or if 2028 a message (other than a HELLO message) does not include a message 2029 sequence number. 2031 14.1. Actions when Receiving a Message 2033 On receiving, on an OLSRv2 interface, a message of a type specified 2034 to be using this mechanism, which includes the TC messages defined in 2035 this specification, a router MUST perform the following: 2037 1. If the router recognizes from the originator address of the 2038 message that the message is one which the receiving router itself 2039 originated (i.e., the message originator address is the 2040 originator address of this router, or is an O_orig_addr in an 2041 Originator Tuple) then the message MUST be silently discarded. 2043 2. Otherwise: 2045 1. If the message is of a type which may be processed, then the 2046 message is considered for processing according to 2047 Section 14.2. 2049 2. If the message is of a type which may be forwarded, AND: 2051 + is present and > 1; AND 2053 + is not present or < 255; 2055 then the message is considered for forwarding according to 2056 Section 14.3. 2058 14.2. Message Considered for Processing 2060 If a message (the "current message") is considered for processing, 2061 then the following tasks MUST be performed: 2063 1. If the sending address (i.e., the source address of the IP 2064 datagram containing the current message) does not match (taking 2065 into account any address prefix) a network address in an 2066 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2067 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2068 current message was received (the "receiving interface") then 2069 processing the current message is OPTIONAL. If the current 2070 message is not processed then the following steps are not carried 2071 out. 2073 2. If a Processed Tuple exists with: 2075 * P_type = the Message Type of the current message; AND 2077 * P_orig_addr = the originator address of the current message; 2078 AND 2080 * P_seq_number = the message sequence number of the current 2081 message; 2083 then the current message MUST NOT be processed. 2085 3. Otherwise: 2087 1. Create a Processed Tuple in the Processed Set with: 2089 + P_type := the Message Type of the current message; 2091 + P_orig_addr := the originator address of the current 2092 message; 2094 + P_seq_number := the sequence number of the current 2095 message; 2097 + P_time := current time + P_HOLD_TIME. 2099 2. Process the current message according to its Message Type. 2100 For a TC message this is as defined in Section 16.3. 2102 14.3. Message Considered for Forwarding 2104 If a message (the "current message") is considered for forwarding, 2105 then the following tasks MUST be performed: 2107 1. If the sending address (i.e., the source address of the IP 2108 datagram containing the current message) does not match (taking 2109 into account any address prefix) a network address in an 2110 L_neighbor_iface_addr_list of a Link Tuple, with L_status = 2111 SYMMETRIC, in the Link Set for the OLSRv2 interface on which the 2112 current message was received (the "receiving interface") then the 2113 current message MUST be silently discarded. 2115 2. Otherwise: 2117 1. If a Received Tuple exists in the Received Set for the 2118 receiving interface, with: 2120 + RX_type = the Message Type of the current message; AND 2122 + RX_orig_addr = the originator address of the current 2123 message; AND 2125 + RX_seq_number = the sequence number of the current 2126 message; 2128 then the current message MUST be silently discarded. 2130 2. Otherwise: 2132 1. Create a Received Tuple in the Received Set for the 2133 receiving interface with: 2135 - RX_type := the Message Type of the current message; 2137 - RX_orig_addr := originator address of the current 2138 message; 2140 - RX_seq_number := sequence number of the current 2141 message; 2143 - RX_time := current time + RX_HOLD_TIME. 2145 2. If a Forwarded Tuple exists with: 2147 - F_type = the Message Type of the current message; AND 2149 - F_orig_addr = the originator address of the current 2150 message; AND 2152 - F_seq_number = the sequence number of the current 2153 message. 2155 then the current message MUST be silently discarded. 2157 3. Otherwise if the sending address matches (taking account 2158 of any address prefix) any network address in an 2159 L_neighbor_iface_addr_list of a Link Tuple in the Link 2160 Set for the receiving OLSRv2 interface that has L_status 2161 = SYMMETRIC and whose corresponding Neighbor Tuple has 2162 N_mpr_selector = true, then: 2164 1. Create a Forwarded Tuple in the Forwarded Set with: 2166 o F_type := the Message Type of the current message; 2168 o F_orig_addr := originator address of the current 2169 message; 2171 o F_seq_number := sequence number of the current 2172 message; 2174 o F_time := current time + F_HOLD_TIME. 2176 2. The Message Header of the current message is modified 2177 by: 2179 o Decrement in the Message Header by 2180 1; AND 2182 o If present, increment in the 2183 Message Header by 1. 2185 3. The message is transmitted over all OLSRv2 2186 interfaces, as described in Section 13. 2188 15. HELLO Messages 2190 The HELLO Message Type is owned by [RFC6130], and thus HELLO messages 2191 are generated, transmitted, received and processed by [RFC6130]. 2192 This protocol, as permitted by [RFC6130], also uses HELLO messages, 2193 including adding to HELLO message generation, and implementing 2194 additional processing based on received HELLO messages. HELLO 2195 messages are not forwarded by [RFC6130] or by this specification. 2197 15.1. HELLO Message Generation 2199 HELLO messages sent over OLSRv2 interfaces are generated as defined 2200 in [RFC6130], and then modified as described in this section. HELLO 2201 messages sent on other MANET interfaces are not modified by this 2202 specification. 2204 HELLO messages sent over OLSRv2 interfaces are extended by adding the 2205 following elements: 2207 o A message originator address, recording this router's originator 2208 address. This MUST use a element, unless: 2210 * The message specifies only a single local interface address 2211 (i.e., contains only one address object that is associated with 2212 an Address Block TLV with Type = LOCAL_IF, and which has no 2213 prefix length, or a maximum prefix length) which will then be 2214 used as the message originator address, OR; 2216 * The message does not include any local interface network 2217 addresses (i.e., has no address objects associated with an 2218 Address Block TLV with Type = LOCAL_IF), as permitted by the 2219 specification in [RFC6130], when the router that generated the 2220 HELLO message has only one interface address and will use that 2221 as the sending address of the IP datagram in which the HELLO 2222 message is contained. In this case, that address will be used 2223 as the message originator address. 2225 o A Message TLV with Type := MPR_WILLING MUST be included. 2227 o The following cases associate Address Block TLVs with one or more 2228 addresses from a Link Tuple or a Neighbor Tuple if these are 2229 included in the HELLO message. In each case, the TLV MUST be 2230 associated with at least one address object for an address from 2231 the relevant Tuple; the TLV MAY be associated with more such 2232 addresses (including a copy of that address object, possibly not 2233 itself associated with any other indicated TLVs, in the same or a 2234 different Address Block). These additional TLVs MUST NOT be 2235 associated with any other addresses in a HELLO message that will 2236 be processed by [RFC6130]. 2238 * For each Link Tuple for which L_in_metric != UNKNOWN_METRIC, 2239 and for which one or more addresses in its 2240 L_neighbor_iface_addr_list are included as address objects with 2241 an associated Address Block TLV with Type = LINK_STATUS and 2242 Value = HEARD or Value = SYMMETRIC, at least one of these 2243 addresses MUST be associated with an Address Block TLV with 2244 Type := LINK_METRIC indicating an incoming link metric with 2245 value L_in_metric. 2247 * For each Link Tuple for which L_out_metric != UNKNOWN_METRIC, 2248 and for which one or more addresses in its 2249 L_neighbor_iface_addr_list are included as address objects with 2250 an associated Address Block TLV with Type = LINK_STATUS and 2251 Value = SYMMETRIC, at least one of these addresses MUST be 2252 associated with an Address Block TLV with Type := LINK_METRIC 2253 indicating an outgoing link metric with value L_out_metric. 2255 * For each Neighbor Tuple for which N_symmetric = true, and for 2256 which one or more addresses in its N_neighbor_addr_list are 2257 included as address objects with an associated Address Block 2258 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2259 SYMMETRIC, at least one of these addresses MUST be associated 2260 with an Address Block TLV with Type := LINK_METRIC indicating 2261 an incoming neighbor metric with value N_in_metric. 2263 * For each Neighbor Tuple for which N_symmetric = true, and for 2264 which one or more addresses in its N_neighbor_addr_list are 2265 included as address objects with an associated Address Block 2266 TLV with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = 2267 SYMMETRIC, at least one of these addresses MUST be associated 2268 with an Address Block TLV with Type := LINK_METRIC indicating 2269 an outgoing neighbor metric with value N_out_metric. 2271 * For each Neighbor Tuple with N_flooding_mpr = true, and for 2272 which one or more network addresses in its N_neighbor_addr_list 2273 are included as address objects in the HELLO message with an 2274 associated Address Block TLV with Type = LINK_STATUS and Value 2275 = SYMMETRIC, at least one of these addresses MUST be associated 2276 with an Address Block TLV with Type := MPR and Value := 2277 FLOODING or Value := FLOOD_ROUTE. 2279 * For each Neighbor Tuple with N_routing_mpr = true, and for 2280 which one or more network addresses in its N_neighbor_addr_list 2281 are included as address objects in the HELLO message with an 2282 associated Address Block TLV with Type = LINK_STATUS and Value 2283 = SYMMETRIC, at least one of these addresses MUST be associated 2284 with an Address Block TLV with Type := MPR and Value := ROUTING 2285 or Value := FLOOD_ROUTE. 2287 15.2. HELLO Message Transmission 2289 HELLO messages are scheduled and transmitted by [RFC6130]. This 2290 protocol MAY require that an additional HELLO message is sent on each 2291 OLSRv2 interface when either of the router's sets of MPRs changes, in 2292 addition to the cases specified in [RFC6130], and subject to the 2293 constraints specified in [RFC6130] (notably on minimum HELLO message 2294 transmission intervals). 2296 15.3. HELLO Message Processing 2298 When received on an OLSRv2 interface, HELLO messages are made 2299 available to this protocol in two ways, both as permitted by 2300 [RFC6130]: 2302 o Such received HELLO messages MUST be made available to this 2303 protocol on reception, which allows them to be discarded before 2304 being processed by [RFC6130], for example if the information added 2305 to the HELLO message by this specification is inconsistent. 2307 o Such received HELLO messages MUST be made available to OLSRv2 2308 after [RFC6130] has completed its processing thereof, unless 2309 discarded as malformed by [RFC6130], for processing by this 2310 specification. 2312 15.3.1. HELLO Message Discarding 2314 In addition to the reasons specified in [RFC6130] for discarding a 2315 HELLO message on reception, a HELLO message received on an OLSRv2 2316 interface MUST be discarded before processing by [RFC6130] or this 2317 specification if it: 2319 o Has more than one Message TLV with Type = MPR_WILLING. 2321 o Has a message originator address, or a network address 2322 corresponding to an address object associated with an Address 2323 Block TLV with Type = LOCAL_IF, that is partially owned by this 2324 router. (Some of these cases are already excluded by [RFC6130].) 2326 o Includes any address object associated with an Address Block TLV 2327 with Type = LINK_STATUS or Type = OTHER_NEIGHB that overlaps the 2328 message's originator address. 2330 o Contains any address that will be processed by [RFC6130] that is 2331 associated, using the same or different address objects, with two 2332 different values of link metric with the same kind and direction 2333 using a TLV with Type = LINK_METRIC and Type Extension = 2334 LINK_METRIC_TYPE. This also applies to different addresses that 2335 are both of the OLSRv2 interface on which the HELLO message was 2336 received. 2338 o Contains any address object associated with an Address Block TLV 2339 with Type = MPR that is not also associated with an Address Block 2340 TLV with Type = LINK_STATUS and Value = SYMMETRIC (including using 2341 a different copy of that address object, in the same or a 2342 different Address Block). 2344 15.3.2. HELLO Message Usage 2346 HELLO messages are first processed as specified in [RFC6130]. That 2347 processing includes identifying (or creating) a Link Tuple and a 2348 Neighbor Tuple corresponding to the originator of the HELLO message 2349 (the "current Link Tuple" and the "current Neighbor Tuple"). After 2350 this, the following processing MUST also be performed if the HELLO 2351 message is received on an OLSRv2 interface and contains a TLV with 2352 Type = MPR_WILLING: 2354 1. If the HELLO message has a well-defined message originator 2355 address, i.e., has an element, or has zero or one 2356 network addresses associated with a TLV with Type = LOCAL_IF: 2358 1. Remove any Neighbor Tuple, other than the current Neighbor 2359 Tuple, with N_orig_addr = message originator address, taking 2360 any consequent action (including removing one or more Link 2361 Tuples) as specified in [RFC6130]. 2363 2. The current Link Tuple is then updated according to: 2365 1. Update L_in_metric and L_out_metric as described in 2366 Section 15.3.2.1; 2368 2. Update L_mpr_selector as described in Section 15.3.2.3. 2370 3. The current Neighbor Tuple is then updated according to: 2372 1. N_orig_addr := message originator address; 2374 2. Update N_in_metric and N_out_metric as described in 2375 Section 15.3.2.1; 2377 3. Update N_will_flooding and N_will_routing as described in 2378 Section 15.3.2.2; 2380 4. Update N_mpr_selector as described in Section 15.3.2.3. 2382 2. If there are any changes to the router's Information Bases, then 2383 perform the processing defined in Section 17. 2385 15.3.2.1. Updating Metrics 2387 For each address in a received HELLO message with an associated TLV 2388 with Type = LINK_STATUS and Value = HEARD or Value = SYMMETRIC, an 2389 incoming (to the message originator) link metric value is defined 2390 either using an associated TLV with Type = LINK_METRIC and Type 2391 Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2392 (link) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2394 For each address in a received HELLO message with an associated TLV 2395 with Type = LINK_STATUS and Value = SYMMETRIC, an outgoing (from the 2396 message originator) link metric value is defined either using an 2397 associated TLV with Type = LINK_METRIC and Type Extension = 2398 LINK_METRIC_TYPE that indicates the appropriate kind (link) and 2399 direction (outgoing) of metric, or as UNKNOWN_METRIC. 2401 For each address in a received HELLO message with an associated TLV 2402 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2403 an incoming (to the message originator) neighbor metric value is 2404 defined either using an associated TLV with Type = LINK_METRIC and 2405 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2406 (neighbor) and direction (incoming) of metric, or as UNKNOWN_METRIC. 2408 For each address in a received HELLO message with an associated TLV 2409 with Type = LINK_STATUS or Type = OTHER_NEIGHB and Value = SYMMETRIC, 2410 an outgoing (from the message originator) neighbor metric value is 2411 defined either using an associated TLV with Type = LINK_METRIC and 2412 Type Extension = LINK_METRIC_TYPE that indicates the appropriate kind 2413 (neighbor) and direction (outgoing) of metric, or as UNKNOWN_METRIC. 2415 The link metric elements L_in_metric and L_out_metric in a Link Tuple 2416 are updated according to the following: 2418 o For any Link Tuple, L_in_metric MAY be set to any representable 2419 value, by a process outside this specification, at any time. 2420 L_in_metric MUST be so set whenever L_status becomes equal to 2421 HEARD or SYMMETRIC (if no other value is available then the value 2422 MAXIMUM_METRIC MUST be used). Setting L_in_metric MAY use 2423 information based on the receipt of a packet including a HELLO 2424 message that causes the creation or updating of the Link Tuple. 2426 o When, as specified in [RFC6130], a Link Tuple is updated (possibly 2427 immediately after being created) due to the receipt of a HELLO 2428 message, if L_status = SYMMETRIC, then L_out_metric is set equal 2429 to the incoming link metric for any included address of the 2430 interface on which the HELLO message was received. (Note that the 2431 rules for discarding HELLO messages in Section 15.3.1 make this 2432 value unambiguous.) If there is no such link metric then 2433 L_out_metric is set to UNKNOWN_METRIC. 2435 The neighbor metric elements N_in_metric and N_out_metric in a 2436 Neighbor Tuple are updated according to Section 17.3. 2438 The metric elements N2_in_metric and N2_out_metric in any 2-Hop Tuple 2439 updated as defined in [RFC6130] are updated to equal the incoming 2440 neighbor metric and outgoing neighbor metric, respectively, 2441 associated with the corresponding N2_2hop_addr. If there are no such 2442 metrics then these elements are set to UNKNOWN_METRIC. 2444 15.3.2.2. Updating Willingness 2446 N_will_flooding and N_will_routing in the current Neighbor Tuple are 2447 updated using the Message TLV with Type = MPR_WILLING (note that this 2448 must be present) as follows: 2450 o N_will_flooding := bits 0-3 of the value of that TLV; AND 2452 o N_will_routing := bits 4-7 of the value of that TLV. 2454 (Each being in the range 0 to 15, i.e., WILL_NEVER to WILL_ALWAYS.) 2456 15.3.2.3. Updating MPR Selector Status 2458 L_mpr_selector is updated as follows: 2460 1. If a router finds an address object representing any of its 2461 relevant local interface network addresses (i.e., those contained 2462 in the I_local_iface_addr_list of an OLSRv2 interface) with an 2463 associated Address Block TLV with Type = MPR and Value = FLOODING 2464 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2465 originating router has selected the receiving router as a 2466 flooding MPR) then, for the current Link Tuple: 2468 * L_mpr_selector := true. 2470 2. Otherwise (i.e., if no such address object and Address Block TLV 2471 was found), if a router finds an address object representing any 2472 of its relevant local interface network addresses (i.e., those 2473 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2474 with an associated Address Block TLV with Type = LINK_STATUS and 2475 Value = SYMMETRIC in the HELLO message, then for the current Link 2476 Tuple: 2478 * L_mpr_selector := false. 2480 N_mpr_selector is updated as follows: 2482 1. If a router finds an address object representing any of its 2483 relevant local interface network addresses (those contained in 2484 the I_local_iface_addr_list of an OLSRv2 interface) with an 2485 associated Address Block TLV with Type = MPR and Value = ROUTING 2486 or Value = FLOOD_ROUTE in the HELLO message (indicating that the 2487 originating router has selected the receiving router as a routing 2488 MPR) then, for the current Neighbor Tuple: 2490 * N_mpr_selector := true; 2492 * N_advertised := true. 2494 2. Otherwise (i.e., if no such address object and Address Block TLV 2495 was found), if a router finds an address object representing any 2496 of its relevant local interface network addresses (those 2497 contained in the I_local_iface_addr_list of an OLSRv2 interface) 2498 with an associated Address Block TLV with Type = LINK_STATUS and 2499 Value = SYMMETRIC in the HELLO message, then for the current 2500 Neighbor Tuple: 2502 * N_mpr_selector := false; 2504 * The router MAY also set N_advertised := false. 2506 16. TC Messages 2508 This protocol defines, and hence owns, the TC Message Type (see 2509 Section 24). Thus, as specified in [RFC5444], this protocol 2510 generates and transmits all TC messages, receives all TC messages and 2511 is responsible for determining whether and how each TC message is to 2512 be processed (updating the Topology Information Base) and/or 2513 forwarded, according to this specification. 2515 16.1. TC Message Generation 2517 A TC message is a message as defined in [RFC5444]. A generated TC 2518 message MUST contain the following elements as defined in [RFC5444]: 2520 o A message originator address, recording this router's originator 2521 address. This MUST use a element. 2523 o element containing the message sequence number. 2525 o A element, containing TC_HOP_LIMIT. A router MAY 2526 use the same or different values of TC_HOP_LIMIT in its TC 2527 messages, see Section 5.4.7. 2529 o A element, containing zero, if the message 2530 contains a TLV with either Type = VALIDITY_TIME or Type = 2531 INTERVAL_TIME (as specified in [RFC5497]) indicating more than one 2532 time value according to distance. A TC message MAY contain such a 2533 element even if it does not need to. 2535 o A single Message TLV with Type := CONT_SEQ_NUM and Value := ANSN 2536 from the Neighbor Information Base. If the TC message is complete 2537 then this Message TLV MUST have Type Extension := COMPLETE, 2538 otherwise it MUST have Type Extension := INCOMPLETE. (Exception: 2539 a TC message MAY omit such a Message TLV if the TC message does 2540 not include any address objects with an associated Address Block 2541 TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY.) 2543 o A single Message TLV with Type := VALIDITY_TIME, as specified in 2544 [RFC5497]. If all TC messages are sent with the same hop limit 2545 then this TLV MUST have a value encoding the period T_HOLD_TIME. 2546 If TC messages are sent with different hop limits (more than one 2547 value of TC_HOP_LIMIT) then this TLV MUST specify times that vary 2548 with the number of hops appropriate to the chosen pattern of TC 2549 message hop limits, as specified in [RFC5497]; these times SHOULD 2550 be appropriate multiples of T_HOLD_TIME. The options included in 2551 [RFC5497] for representing zero and infinite times MUST NOT be 2552 used. 2554 o If the TC message is complete, all network addresses which are the 2555 N_orig_addr of a Neighbor Tuple with N_advertised = true, MUST be 2556 represented by address objects in one or more Address Blocks. If 2557 the TC message is incomplete then any such address objects MAY be 2558 included. At least one copy of each such address object that is 2559 included MUST be associated with an Address Block TLV with Type := 2560 NBR_ADDR_TYPE, and Value := ORIGINATOR, or with Value := 2561 ROUTABLE_ORIG if that address object is also to be associated with 2562 Value = ROUTABLE. 2564 o If the TC message is complete, all routable addresses which are in 2565 the N_neighbor_addr_list of a Neighbor Tuple with N_advertised = 2566 true MUST be represented by address objects in one or more Address 2567 Blocks. If the TC message is incomplete then any such address 2568 objects MAY be included. At least one copy of each such address 2569 object MUST be associated with an Address Block TLV with Type = 2570 NBR_ADDR_TYPE, and Value = ROUTABLE, or with Value = ROUTABLE_ORIG 2571 if also to be associated with Value = ORIGINATOR. At least one 2572 copy of each such address object MUST be associated with an 2573 Address Block TLV with Type = LINK_METRIC and Type Extension = 2574 LINK_METRIC_TYPE indicating an outgoing neighbor metric with value 2575 equal to the corresponding N_out_metric. 2577 o If the TC message is complete, all network addresses which are the 2578 AL_net_addr of a Local Attached Network Tuple MUST be represented 2579 by address objects in one or more Address Blocks. If the TC 2580 message is incomplete then any such address objects MAY be 2581 included. At least one copy of each such address object MUST be 2582 associated with an Address Block TLV with Type := GATEWAY, and 2583 Value := AN_dist. At least one copy of each such address object 2584 MUST be associated with an Address Block TLV with Type = 2585 LINK_METRIC and Type Extension = LINK_METRIC_TYPE indicating an 2586 outgoing neighbor metric equal to the corresponding AL_metric. 2588 A TC message MAY contain: 2590 o A single Message TLV with Type := INTERVAL_TIME, as specified in 2591 [RFC5497]. If all TC messages are sent with the same hop limit 2592 then this TLV MUST have a value encoding the period TC_INTERVAL. 2593 If TC messages are sent with different hop limits, then this TLV 2594 MUST specify times that vary with the number of hops appropriate 2595 to the chosen pattern of TC message hop limits, as specified in 2596 [RFC5497]; these times MUST be appropriate multiples of 2597 TC_INTERVAL. The options included in [RFC5497] for representing 2598 zero and infinite times MUST NOT be used. 2600 16.2. TC Message Transmission 2602 A router with one or more OLSRv2 interfaces, and with any Neighbor 2603 Tuples with N_advertised = true, or with a non-empty Local Attached 2604 Network Set MUST generate TC messages. A router which does not have 2605 such information to advertise MUST also generate "empty" TC messages 2606 for a period A_HOLD_TIME after it last generated a non-empty TC 2607 message. 2609 Complete TC messages are generated and transmitted periodically on 2610 all OLSRv2 interfaces, with a default interval between two 2611 consecutive TC message transmissions by the same router of 2612 TC_INTERVAL. 2614 TC messages MAY be generated in response to a change in the 2615 information which they are to advertise, indicated by a change in the 2616 ANSN in the Neighbor Information Base. In this case a router MAY 2617 send a complete TC message, and if so MAY re-start its TC message 2618 schedule. Alternatively, a router MAY send an incomplete TC message 2619 with at least the newly advertised network addresses (i.e., not 2620 previously, but now, an N_orig_addr or in an N_neighbor_addr_list in 2621 a Neighbor Tuple with N_advertised = true, or an AL_net_addr) in its 2622 Address Blocks, with associated Address Block TLV(s). Note that a 2623 router cannot report removal of advertised content using an 2624 incomplete TC message. 2626 When sending a TC message in response to a change of advertised 2627 network addresses, a router MUST respect a minimum interval of 2628 TC_MIN_INTERVAL between generated TC messages. Sending an incomplete 2629 TC message MUST NOT cause the interval between complete TC messages 2630 to be increased, and thus a router MUST NOT send an incomplete TC 2631 message if within TC_MIN_INTERVAL of the next scheduled complete TC 2632 message. 2634 The generation of TC messages, whether scheduled or triggered by a 2635 change of contents, MAY be jittered as described in [RFC5148]. The 2636 values of MAXJITTER used MUST be: 2638 o TP_MAXJITTER for periodic TC message generation; 2640 o TT_MAXJITTER for responsive TC message generation. 2642 16.3. TC Message Processing 2644 On receiving a TC message on an OLSRv2 interface, the receiving 2645 router MUST then follow the processing and forwarding procedures, 2646 defined in Section 14. 2648 If the message is considered for processing (Section 14.2), then a 2649 router MUST first check if the message is invalid for processing by 2650 this router, as defined in Section 16.3.1. A router MAY make a 2651 similar check before considering a message for forwarding, it MUST 2652 make those aspects of the check that apply to elements in the Message 2653 Header. 2655 If the TC message is not invalid, then the TC Message Type specific 2656 processing, described in Section 16.3.2 MUST be applied. This will 2657 update its appropriate Interface Information Bases and its Router 2658 Information Base. Following this, if there are any changes in these 2659 Information Bases, then the processing in Section 17 MUST be 2660 performed. 2662 16.3.1. TC Message Discarding 2664 A received TC message is invalid for processing by this router if the 2665 message: 2667 o Has an address length specified in the Message Header that is not 2668 equal to the length of the addresses used by this router. 2670 o Does not include a message originator address and a message 2671 sequence number. 2673 o Does not include a hop count, and contains a multi-value TLV with 2674 Type = VALIDITY_TIME or Type = INTERVAL_TIME, as defined in 2675 [RFC5497]. 2677 o Does not have exactly one Message TLV with Type = VALIDITY_TIME. 2679 o Has more than one Message TLV with Type = INTERVAL_TIME. 2681 o Does not have a Message TLV with Type = CONT_SEQ_NUM and Type 2682 Extension = COMPLETE or Type Extension = INCOMPLETE, and contains 2683 at least one address object associated with an Address Block TLV 2684 with Type = NBR_ADDR_TYPE or Type = GATEWAY. 2686 o Has more than one Message TLV with Type = CONT_SEQ_NUM and Type 2687 Extension = COMPLETE or Type Extension = INCOMPLETE. 2689 o Has a message originator address that is partially owned by this 2690 router. 2692 o Includes any address object with a prefix length which is not 2693 maximal (equal to the address length, in bits), associated with an 2694 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ORIGINATOR 2695 or Value = ROUTABLE_ORIG. 2697 o Includes any address object that represents a non-routable 2698 address, associated with an Address Block TLV with Type = 2699 NBR_ADDR_TYPE and Value = ROUTABLE or Value = ROUTABLE_ORIG. 2701 o Includes any address object associated with an Address Block TLV 2702 with Type = NBR_ADDR_TYPE or Type = GATEWAY that also represents 2703 the message's originator address. 2705 o Includes any address object (including different copies of an 2706 address object, in the same or different Address Blocks) that is 2707 associated with an Address Block TLV with Type = NBR_ADDR_TYPE or 2708 Type = GATEWAY, that is also associated with more than one 2709 outgoing neighbor metric using a TLV with Type = LINK_METRIC and 2710 Type Extension = LINK_METRIC_TYPE. 2712 o Associates any address object (including different copies of an 2713 address object, in the same or different Address Blocks) with more 2714 than one single hop count value using one or more Address Block 2715 TLV(s) with Type = GATEWAY. 2717 o Associates any address object (including different copies of an 2718 address object, in the same or different Address Blocks) with 2719 Address Block TLVs with Type = NBR_ADDR_TYPE and Type = GATEWAY. 2721 A router MAY recognize additional reasons for identifying that a 2722 message is invalid. An invalid message MUST be silently discarded, 2723 without updating the router's Information Bases. 2725 16.3.2. TC Message Processing Definitions 2727 When, according to Section 14.2, a TC message is to be "processed 2728 according to its type", this means that: 2730 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2731 and Type Extension = COMPLETE, then processing according to 2732 Section 16.3.3 and then according to Section 16.3.4 is carried 2733 out. 2735 o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM 2736 and Type Extension = INCOMPLETE, then only processing according to 2737 Section 16.3.3 is carried out. 2739 For the purposes of the TC message processing in Section 16.3.3 and 2740 Section 16.3.4: 2742 o "validity time" is calculated from a VALIDITY_TIME Message TLV in 2743 the TC message according to the specification in [RFC5497]. All 2744 information in the TC message has the same validity time. 2746 o "received ANSN" is defined as being the value of a Message TLV 2747 with Type = CONT_SEQ_NUM. 2749 o "associated metric value" is defined for any address in the TC 2750 message as being either the outgoing neighbor metric value 2751 indicated by a TLV with Type = LINK_METRIC and Type Extension = 2752 LINK_METRIC_TYPE that is associated with any address object in the 2753 TC message that is equal to that address, or as UNKNOWN_METRIC 2754 otherwise. (Note that the rules in Section 16.3.1 make this 2755 definition unambiguous.) 2757 o Comparisons of sequence numbers are carried out as specified in 2758 Section 21. 2760 16.3.3. Initial TC Message Processing 2762 The TC message is processed as follows: 2764 1. The Advertising Remote Router Set is updated according to 2765 Section 16.3.3.1. If the TC message is indicated as discarded in 2766 that processing then the following steps are not carried out. 2768 2. The Router Topology Set is updated according to Section 16.3.3.2. 2770 3. The Routable Address Topology Set is updated according to 2771 Section 16.3.3.3. 2773 4. The Attached Network Set is updated according to 2774 Section 16.3.3.4. 2776 16.3.3.1. Populating the Advertising Remote Router Set 2778 The router MUST update its Advertising Remote Router Set as follows: 2780 1. If there is an Advertising Remote Router Tuple with: 2782 * AR_orig_addr = message originator address; AND 2784 * AR_seq_number > received ANSN, 2786 then the TC message MUST be discarded. 2788 2. Otherwise: 2790 1. If there is no Advertising Remote Router Tuple such that: 2792 + AR_orig_addr = message originator address; 2794 then create an Advertising Remote Router Tuple with: 2796 + AR_orig_addr := message originator address. 2798 2. This Advertising Remote Router Tuple (existing or new) is 2799 then modified as follows: 2801 + AR_seq_number := received ANSN; 2803 + AR_time := current time + validity time. 2805 16.3.3.2. Populating the Router Topology Set 2807 The router MUST update its Router Topology Set as follows: 2809 1. For each address (henceforth advertised address) corresponding to 2810 one or more address objects with an associated Address Block TLV 2811 with Type = NBR_ADDR_TYPE and Value = ORIGINATOR or Value = 2812 ROUTABLE_ORIG, and that is not partially owned by this router, 2813 perform the following processing: 2815 1. If the associated metric is UNKNOWN_METRIC then remove any 2816 Router Topology Tuple such that: 2818 + TR_from_orig_addr = message originator address; AND 2820 + TR_to_orig_addr = advertised address, 2822 2. Otherwise if there is no Router Topology Tuple such that: 2824 + TR_from_orig_addr = message originator address; AND 2826 + TR_to_orig_addr = advertised address, 2828 then create a new Router Topology Tuple with: 2830 + TR_from_orig_addr := message originator address; 2832 + TR_to_orig_addr := advertised address. 2834 3. This Router Topology Tuple (existing or new) is then modified 2835 as follows: 2837 + TR_seq_number := received ANSN; 2839 + TR_metric := associated link metric; 2841 + TR_time := current time + validity time. 2843 16.3.3.3. Populating the Routable Address Topology Set 2845 The router MUST update its Routable Address Topology Set as follows: 2847 1. For each network address (henceforth advertised address) 2848 corresponding to one or more address objects with an associated 2849 Address Block TLV with Type = NBR_ADDR_TYPE and Value = ROUTABLE 2850 or Value = ROUTABLE_ORIG, and that is not partially owned by this 2851 router, perform the following processing: 2853 1. If the associated metric is UNKNOWN_METRIC then remove any 2854 Routable Address Topology Tuple such that: 2856 + TA_from_orig_addr = message originator address; AND 2858 + TA_dest_addr = advertised address. 2860 2. Otherwise if there is no Routable Address Topology Tuple such 2861 that: 2863 + TA_from_orig_addr = message originator address; AND 2865 + TA_dest_addr = advertised address, 2867 then create a new Routable Address Topology Tuple with: 2869 + TA_from_orig_addr := message originator address; 2871 + TA_dest_addr := advertised address. 2873 3. This Routable Address Topology Tuple (existing or new) is 2874 then modified as follows: 2876 + TA_seq_number := received ANSN; 2878 + TA_metric := associated link metric; 2880 + TA_time := current time + validity time. 2882 16.3.3.4. Populating the Attached Network Set 2884 The router MUST update its Attached Network Set as follows: 2886 1. For each network address (henceforth attached address) 2887 corresponding to one or more address objects with an associated 2888 Address Block TLV with Type = GATEWAY, and that is not fully 2889 owned by this router, perform the following processing: 2891 1. If the associated metric is UNKNOWN_METRIC then remove any 2892 Attached Network Tuple such that: 2894 + AN_net_addr = attached address; AND 2896 + AN_orig_addr = message originator address. 2898 2. Otherwise if there is no Attached Network Tuple such that: 2900 + AN_net_addr = attached address; AND 2902 + AN_orig_addr = message originator address, 2904 then create a new Attached Network Tuple with: 2906 + AN_net_addr := attached address; 2907 + AN_orig_addr := message originator address. 2909 3. This Attached Network Tuple (existing or new) is then 2910 modified as follows: 2912 + AN_seq_number := received ANSN; 2914 + AN_dist := the Value of the associated GATEWAY TLV; 2916 + AN_metric := associated link metric; 2918 + AN_time := current time + validity time. 2920 16.3.4. Completing TC Message Processing 2922 The TC message is processed as follows: 2924 1. The Router Topology Set is updated according to Section 16.3.4.1. 2926 2. The Routable Address Topology Set is updated according to 2927 Section 16.3.4.2. 2929 3. The Attached Network Set is updated according to 2930 Section 16.3.4.3. 2932 16.3.4.1. Purging the Router Topology Set 2934 The Router Topology Set MUST be updated as follows: 2936 1. Any Router Topology Tuples with: 2938 * TR_from_orig_addr = message originator address; AND 2940 * TR_seq_number < received ANSN, 2942 MUST be removed. 2944 16.3.4.2. Purging the Routable Address Topology Set 2946 The Routable Address Topology Set MUST be updated as follows: 2948 1. Any Routable Address Topology Tuples with: 2950 * TA_from_orig_addr = message originator address; AND 2952 * TA_seq_number < received ANSN, 2954 MUST be removed. 2956 16.3.4.3. Purging the Attached Network Set 2958 The Attached Network Set MUST be updated as follows: 2960 1. Any Attached Network Tuples with: 2962 * AN_orig_addr = message originator address; AND 2964 * AN_seq_number < received ANSN, 2966 MUST be removed. 2968 17. Information Base Changes 2970 The changes described in the following sections MUST be carried out 2971 when any Information Base changes as indicated. 2973 17.1. Originator Address Changes 2975 If the router changes its originator address, then: 2977 1. If there is no Originator Tuple with: 2979 * O_orig_addr = old originator address 2981 then create an Originator Tuple with: 2983 * O_orig_addr := old originator address 2985 The Originator Tuple (existing or new) with: 2987 * O_orig_addr = new originator address 2989 is then modified as follows: 2991 * O_time := current time + O_HOLD_TIME 2993 17.2. Link State Changes 2995 The consistency of a Link Tuple MUST be maintained according to the 2996 following rules, in addition to those in [RFC6130]: 2998 o If L_status = HEARD or L_status = SYMMETRIC, then L_in_metric MUST 2999 be set (by a process outside this specification). 3001 o If L_status != SYMMETRIC, then set L_mpr_selector := false. 3003 o If L_out_metric = UNKNOWN_METRIC, then L_status MUST NOT equal 3004 SYMMETRIC; set L_SYM_time := expired if this would otherwise be 3005 the case. 3007 17.3. Neighbor State Changes 3009 The consistency of a Neighbor Tuple MUST be maintained according to 3010 the following rules, in addition to those in [RFC6130]: 3012 1. If N_symmetric = true, then N_in_metric MUST equal the minimum 3013 value of all L_in_metric of corresponding Link Tuples with 3014 L_status = SYMMETRIC and L_in_metric != UNKNOWN_METRIC. If there 3015 are no such Link Tuples then N_in_metric MUST equal 3016 UNKNOWN_METRIC. 3018 2. If N_symmetric = true, then N_out_metric MUST equal the minimum 3019 value of all L_out_metric of corresponding Link Tuples with 3020 L_status = SYMMETRIC and L_out_metric != UNKNOWN_METRIC. If 3021 there are no such Link Tuples then N_out_metric MUST equal 3022 UNKNOWN_METRIC. 3024 3. If N_symmetric = false, then N_flooding_mpr, N_routing_mpr, 3025 N_mpr_selector and N_advertised MUST all be equal to false. 3027 4. If N_mpr_selector = true, then N_advertised MUST be equal to 3028 true. 3030 5. If N_symmetric = true, N_out_metric != UNKNOWN_METRIC and 3031 N_mpr_selector = false, then a router MAY select N_advertised = 3032 true or N_advertised = false. The more neighbors that are 3033 advertised, the larger TC messages become, but the more 3034 redundancy is available for routing. A router SHOULD consider 3035 the nature of its network in making such a decision, and SHOULD 3036 avoid unnecessary changes in advertising status, which may result 3037 both in additional TC messages having to be sent by its 3038 neighbors, and in unnecessary changes to routing, which will have 3039 similar effects to other forms of topology changes in the MANET. 3041 17.4. Advertised Neighbor Changes 3043 The router MUST increment the ANSN in the Neighbor Information Base 3044 whenever: 3046 1. Any Neighbor Tuple changes its N_advertised value, or any 3047 Neighbor Tuple with N_advertised = true is removed. 3049 2. Any Neighbor Tuple with N_advertised = true changes its 3050 N_orig_addr, or has any routable address is added to or removed 3051 from N_neighbor_addr_list. 3053 3. Any Neighbor Tuple with N_advertised = true has N_out_metric 3054 changed. 3056 4. There is any change to the Local Attached Network Set. 3058 17.5. Advertising Remote Router Tuple Expires 3060 The Router Topology Set, the Routable Address Topology Set and the 3061 Attached Network Set MUST be changed when an Advertising Remote 3062 Router Tuple expires (AR_time is reached). The following changes are 3063 required before the Advertising Remote Router Tuple is removed: 3065 1. All Router Topology Tuples with: 3067 * TR_from_orig_addr = AR_orig_addr of the Advertising Remote 3068 Router Tuple 3070 are removed. 3072 2. All Routable Address Topology Tuples with: 3074 * TA_from_orig_addr = AR_orig_addr of the Advertising Remote 3075 Router Tuple 3077 are removed. 3079 3. All Attached Network Tuples with: 3081 * AN_orig_addr = AR_orig_addr of the Advertising Remote Router 3082 Tuple 3084 are removed. 3086 17.6. Neighborhood Changes and MPR Updates 3088 The sets of symmetric 1-hop neighbors selected as flooding MPRs and 3089 routing MPRs MUST satisfy the conditions defined in Section 18. To 3090 ensure this: 3092 1. The set of flooding MPRs of a router MUST be recalculated if: 3094 * A Link Tuple is added with L_status = SYMMETRIC and 3095 L_out_metric != UNKNOWN_METRIC, OR; 3097 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3098 UNKNOWN_METRIC is removed, OR; 3100 * A Link Tuple with L_status = SYMMETRIC and L_out_metric != 3101 UNKNOWN_METRIC changes to having L_status = HEARD, L_status = 3102 LOST or L_out_metric = UNKNOWN_METRIC, OR; 3104 * A Link Tuple with L_status = HEARD or L_status = LOST changes 3105 to having L_status = SYMMETRIC and L_out_metric != 3106 UNKNOWN_METRIC, OR; 3108 * The flooding MPR selection process uses metric values (see 3109 Section 18.4) and the L_out_metric of any Link Tuple with 3110 L_status = SYMMETRIC changes, OR; 3112 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3113 true and N_out_metric != UNKNOWN_METRIC changes from 3114 WILL_NEVER to any other value, OR; 3116 * The N_will_flooding of a Neighbor Tuple with N_flooding_mpr = 3117 true changes to WILL_NEVER from any other value, OR; 3119 * The N_will_flooding of a Neighbor Tuple with N_symmetric = 3120 true, N_out_metric != UNKNOWN_METRIC, and N_flooding_mpr = 3121 false changes to WILL_ALWAYS from any other value, OR; 3123 * A 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC is added or 3124 removed, OR; 3126 * The flooding MPR selection process uses metric values (see 3127 Section 18.4) and the N2_out_metric of any 2-Hop Tuple 3128 changes. 3130 2. Otherwise, the set of flooding MPRs of a router MAY be 3131 recalculated if the N_will_flooding of a Neighbor Tuple with 3132 N_symmetric = true changes in any other way; it SHOULD be 3133 recalculated if N_flooding_mpr = false and this is an increase in 3134 N_will_flooding or if N_flooding_mpr = true and this is a 3135 decrease in N_will_flooding. 3137 3. The set of routing MPRs of a router MUST be recalculated if: 3139 * A Neighbor Tuple is added with N_symmetric = true and 3140 N_in_metric != UNKNOWN_METRIC, OR; 3142 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3143 UNKNOWN_METRIC is removed, OR; 3145 * A Neighbor Tuple with N_symmetric = true and N_in_metric != 3146 UNKNOWN_METRIC changes to having N_symmetric = false, OR; 3148 * A Neighbor Tuple with N_symmetric = false changes to having 3149 N_symmetric = true and N_in_metric != UNKNOWN_METRIC, OR; 3151 * The N_in_metric of any Neighbor Tuple with N_symmetric = true 3152 changes, OR; 3154 * The N_will_routing of a Neighbor Tuple with N_symmetric = true 3155 and N_in_metric != UNKNOWN_METRIC changes from WILL_NEVER to 3156 any other value, OR; 3158 * The N_will_routing of a Neighbor Tuple with N_routing_mpr = 3159 true changes to WILL_NEVER from any other value, OR; 3161 * The N_will_routing of a Neighbor Tuple with N_symmetric = 3162 true, N_in_metric != UNKNOWN_METRIC and N_routing_mpr = false 3163 changes to WILL_ALWAYS from any other value, OR; 3165 * A 2-Hop Tuple with N2_in_metric != UNKNOWN_METRIC is added or 3166 removed, OR; 3168 * The N2_in_metric of any 2-Hop Tuple changes. 3170 4. Otherwise, the set of routing MPRs of a router MAY be 3171 recalculated if the N_will_routing of a Neighbor Tuple with 3172 N_symmetric = true changes in any other way; it SHOULD be 3173 recalculated if N_routing_mpr = false and this is an increase in 3174 N_will_routing or if N_routing_mpr = true and this is a decrease 3175 in N_will_routing. 3177 If either set of MPRs of a router is recalculated, this MUST be as 3178 described in Section 18. 3180 17.7. Routing Set Updates 3182 The Routing Set MUST be updated, as described in Section 19, when 3183 changes in the Local Information Base, the Neighborhood Information 3184 Base or the Topology Information Base indicate a change (including of 3185 any potentially used outgoing neighbor metric values) of the known 3186 symmetric links and/or attached networks in the MANET, hence changing 3187 the Topology Graph. It is sufficient to consider only changes which 3188 affect at least one of: 3190 o The Local Interface Set for an OLSRv2 interface, if the change 3191 removes any network address in an I_local_iface_addr_list. In 3192 this case, unless the OLSRv2 interface is removed, it may not be 3193 necessary to do more than replace such network addresses, if used, 3194 by an alternative network address from the same 3195 I_local_iface_addr_list. 3197 o The Local Attached Set, if the change removes any AL_net_addr 3198 which is also an AN_net_addr. In this case it may not be 3199 necessary to do more than add Routing Tuples with R_dest_addr 3200 equal to that AN_net_addr. 3202 o The Link Set of any OLSRv2 interface, considering only Link Tuples 3203 which have, or just had, L_status = SYMMETRIC and L_out_metric != 3204 UNKNOWN_METRIC (including removal of such Link Tuples). 3206 o The Neighbor Set of the router, considering only Neighbor Tuples 3207 that have, or just had, N_symmetric = true and N_out_metric != 3208 UNKNOWN_METRIC, and do not have N_orig_addr = unknown. 3210 o The 2-Hop Set of any OLSRv2 interface, if used in the creation of 3211 the Routing Set, and if the change affects any 2-Hop Tuples with 3212 N2_out_metric != UNKNOWN_METRIC. 3214 o The Router Topology Set of the router. 3216 o The Routable Address Topology Set of the router. 3218 o The Attached Network Set of the router. 3220 18. Selecting MPRs 3222 Each router MUST select, from among its willing symmetric 1-hop 3223 neighbors, two subsets of these routers, as flooding and routing 3224 MPRs. This selection is recorded in the router's Neighbor Set, and 3225 reported in the router's HELLO messages. Routers MAY select their 3226 MPRs by any process that satisfies the conditions which follow, which 3227 may, but need not, use the organization of the data described. 3228 Routers can freely interoperate whether they use the same or 3229 different MPR selection algorithms. 3231 Only flooding MPRs forward control messages flooded through the 3232 MANET, thus effecting a flooding reduction, an optimization of the 3233 flooding mechanism, known as MPR flooding. Routing MPRs are used to 3234 effect a topology reduction in the MANET. (If no such reduction is 3235 required then a router can select all of its relevant neighbors as 3236 routing MPRs.) Consequently, while it is not essential that these 3237 two sets of MPRs are minimal, keeping the numbers of MPRs small 3238 ensures that the overhead of this protocol is kept to a minimum. 3240 18.1. Overview 3242 MPRs are selected according to the following steps, defined in the 3243 following sections: 3245 o A data structure known as a Neighbor Graph is defined. 3247 o The properties of an MPR Set derived from a Neighbor Graph are 3248 defined. Any algorithm that creates an MPR Set that satisfies 3249 these properties is a valid MPR selection algorithm. An example 3250 algorithm that creates such an MPR Set is given in Appendix A. 3252 o How to create a Neighbor Graph for each interface based on the 3253 corresponding Interface Information Base is defined, and how to 3254 combine the resulting MPR Sets to determine the router's flooding 3255 MPRs and record those in the router's Neighbor Set. 3257 o How to create a single Neighbor Graph based on all Interface 3258 Information Bases and the Neighbor Information Base is defined, 3259 and how to record the resulting MPR Set as the router's routing 3260 MPRs in the router's Neighbor Set. 3262 o A specification as to when MPRs MUST be calculated is given. 3264 When a router selects its MPRs it MAY consider any characteristics of 3265 its neighbors that it is aware of. In particular it SHOULD consider 3266 the willingness of the neighbor, as recorded by the corresponding 3267 N_will_flooding or N_will_routing value, as appropriate, preferring 3268 neighbors with higher values. (Note that willingness values equal to 3269 WILL_NEVER and WILL_ALWAYS are always considered, as described.) 3270 However, a router MAY consider other characteristics to have a 3271 greater significance. 3273 Each router MAY select its flooding and routing MPRs independently 3274 from each other, or coordinate its selections. A router MAY make its 3275 MPR selections independently of the MPR selection by other routers, 3276 or it MAY, for example, give preference to routers that either are, 3277 or are not, already selected as MPRs by other routers. 3279 18.2. Neighbor Graph 3281 A Neighbor Graph is a structure defined here as consisting of sets N1 3282 and N2 and some associated metric and willingness values. Elements 3283 of set N1 represent willing symmetric 1-hop neighbors, and elements 3284 of set N2 represent addresses of a symmetric 2-hop neighbor. 3286 A Neighbor Graph has the following properties: 3288 o It contains two disjoint sets N1 and N2. 3290 o For each element x in N1 there is an associated willingness value 3291 W(x) such that WILL_NEVER < W(x) <= WILL_ALWAYS. 3293 o For each element x in N1 there is an associated metric d1(x) > 0. 3295 o For some elements y in N2 there is an associated metric d1(y) > 0. 3296 (Other elements y in N2 have undefined d1(y), this may be 3297 considered to be infinite.) 3299 o For each element x in N1 there is a subset N2(x) of elements of 3300 N2; this subset may be empty. For each x in N1 and each y in 3301 N2(x) there is an associated metric d2(x,y) > 0. (For other x in 3302 N1 and y in N2, d2(x,y) is undefined, and may be considered 3303 infinite.) 3305 o N2 is equal to the union of all the N2(x) for all x in N1, i.e. 3306 for each y in N2 there is at least one x in N1 such that y is in 3307 N2(x). 3309 It is convenient to also define: 3311 o For each y in N2 the set N1(y) that contains x in N1 if and only 3312 if y is in N2(x). From the final property above, N1(y) is not 3313 empty. 3315 o For each x in N1 and y in N2, if d2(x,y) is defined then d(x,y) := 3316 d1(x)+d2(x,y), otherwise d(x,y) is not defined. (Thus d(x,y) is 3317 defined if y is in N2(x), or equivalently if x is in N1(y).) 3319 o For any subset S of N1, and for each y in N2, the metric d(y,S) is 3320 the minimum value of d1(y), if defined, and of all d(x,y) for x in 3321 N1(y) and in S. If there are no such metrics to take the minimum 3322 value of, then d(y,S) is undefined (may be considered to be 3323 infinite). From the final property above, d(y,N1) is defined for 3324 all y. 3326 18.3. MPR Properties 3328 Given a Neighbor Graph as defined in Section 18.2, an MPR Set for 3329 that Neighbor Graph is a subset M of the set N1 that satisfies the 3330 following properties: 3332 o If x in N1 has W(x) = WILL_ALWAYS then x is in M. 3334 o For any y in N2 that does not have a defined d1(y), there is at 3335 least one element in M that is also in N1(y). This is equivalent 3336 to the requirement that d(y,M) is defined. 3338 o For any y in N2, d(y,M) = d(y,N1). 3340 These two properties correspond first to that the MPR Set consists of 3341 a set of symmetric 1-hop neighbors that cover all the symmetric 2-hop 3342 neighbors, and second that they do so retaining a minimum distance 3343 route (1-hop, if present, or 2-hop) to each symmetric 2-hop neighbor. 3345 Note that if M is an MPR Set, then so is any subset of N1 that 3346 contains M, and also that N1 is always an MPR Set. An MPR Set may be 3347 empty, but cannot be empty if N2 contains any elements y that do not 3348 have a defined d1(y). 3350 18.4. Flooding MPRs 3352 Whenever flooding MPRs are to be calculated, an implementation MUST 3353 determine and record a set of flooding MPRs that is equivalent to one 3354 calculated as described in this section. 3356 The calculation of flooding MPRs need not use link metrics, or 3357 equivalently may use link metrics with a fixed value, here taken to 3358 be 1. However, links with unknown metric (L_out_metric = 3359 UNKNOWN_METRIC) MUST NOT be used even if link metrics are otherwise 3360 not used. 3362 Routers MAY make individual decisions as to whether to use link 3363 metrics for the calculation of flooding MPRs. A router MUST use the 3364 same approach to the choice of whether to use link metrics for all 3365 links, i.e., in the cases indicated by A or B, the same choice MUST 3366 be made in each case. 3368 For each OLSRv2 interface (the "current interface") define a Neighbor 3369 Graph as defined in Section 18.2 according to the following: 3371 o Define a reachable Link Tuple to be a Link Tuple in the Link Set 3372 for the current interface with L_status = SYMMETRIC and 3373 L_out_metric != UNKNOWN_METRIC. 3375 o Define an allowed Link Tuple to be a reachable Link Tuple whose 3376 corresponding Neighbor Tuple has N_will_flooding > WILL_NEVER. 3378 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3379 for the current interface for which N2_out_metric != 3380 UNKNOWN_METRIC and there is an allowed Link Tuple with 3381 L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list. 3383 o Define an element of N1 for each allowed Link Tuple. This then 3384 defines the corresponding Link Tuple for each element of N1 and 3385 the corresponding Neighbor Tuple for each element of N1, being the 3386 Neighbor Tuple corresponding to that Link Tuple. 3388 o For each element x in N1, define W(x) := N_will_flooding of the 3389 corresponding Neighbor Tuple. 3391 o For each element x in N1, define d1(x) as either: 3393 A. L_out_metric of the corresponding Link Tuple, OR; 3395 B. 1. 3397 o Define an element of N2 for each network address that is the 3398 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3399 defines the corresponding address for each element of N2. 3401 o For each element y in N2, if the corresponding address is in the 3402 N_neighbor_addr_list of a Neighbor Tuple that corresponds to one 3403 or more reachable Link Tuples, then define d1(y) as either: 3405 A. the minimum value of the L_out_metric of those Link Tuples, 3406 OR; 3408 B. 1. 3410 Otherwise d1(y) is not defined. In the latter case, where d1(y) 3411 := 1, all such y in N2 may instead be removed from N2. 3413 o For each element x in N1, define N2(x) as the set of elements y in 3414 N2 whose corresponding address is the N2_2hop_addr of an allowed 3415 2-Hop Tuple that has N2_neighbor_iface_addr_list = 3416 L_neighbor_iface_addr_list of the Link Tuple corresponding to x. 3417 For all such x and y, define d2(x,y) as either: 3419 A. N2_out_metric of that 2-Hop Tuple, OR; 3421 B. 1. 3423 It is up to an implementation to decide how to label each element of 3424 N1 or N2. For example an element of N1 may be labeled with one or 3425 more addresses from the corresponding L_neighbor_iface_addr_list, or 3426 with a pointer or reference to the corresponding Link Tuple. 3428 Using these Neighbor Graphs, flooding MPRs are selected and recorded 3429 by: 3431 o For each OLSRv2 interface, determine an MPR Set as specified in 3432 Section 18.3. 3434 o A Neighbor Tuple represents a flooding MPR and has N_flooding_mpr 3435 := true (otherwise N_flooding_mpr := false) if and only if that 3436 Neighbor Tuple corresponds to an element in an MPR Set created for 3437 any interface as described above. That is, the overall set of 3438 flooding MPRs is the union of the sets of flooding MPRs for all 3439 OLSRv2 interfaces. 3441 A router MAY select its flooding MPRs for each OLSRv2 interface 3442 independently, or it MAY coordinate its MPR selections across its 3443 OLSRv2 interfaces, as long as the required condition is satisfied for 3444 each OLSRv2 interface. One such coordinated approach is to process 3445 the OLSRv2 interfaces sequentially, and for each OLSRv2 interface 3446 start with flooding MPRs selected (and not removable) if the neighbor 3447 has been already selected as an MPR for an OLSRv2 interface that has 3448 already been processed. The algorithm specified in Appendix A can be 3449 used in this way. 3451 18.5. Routing MPRs 3453 Whenever routing MPRs are to be calculated, an implementation MUST 3454 determine and record a set of routing MPRs that is equivalent to one 3455 calculated as described in this section. 3457 Define a single Neighbor Graph as defined in Section 18.2 according 3458 to the following: 3460 o Define a reachable Neighbor Tuple to be a Neighbor Tuple with 3461 N_symmetric = true and N_in_metric != UNKNOWN_METRIC. 3463 o Define an allowed Neighbor Tuple to be a reachable Neighbor Tuple 3464 with N_will_routing > WILL_NEVER. 3466 o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set 3467 for any OLSRv2 interface with N2_in_metric != UNKNOWN_METRIC and 3468 for which there is an allowed Neighbor Tuple with 3469 N_neighbor_addr_list containing N2_neighbor_iface_addr_list. 3471 o Define an element of N1 for each allowed Neighbor Tuple. This 3472 then defines the corresponding Neighbor Tuple for each element of 3473 N1. 3475 o For each element x in N1, define W(x) := N_will_routing of the 3476 corresponding Neighbor Tuple. 3478 o For each element x in N1, define d1(x) := N_in_metric of the 3479 corresponding Neighbor Tuple. 3481 o Define an element of N2 for each network address that is the 3482 N2_2hop_addr of one or more allowed 2-Hop Tuples. This then 3483 defines the corresponding address for each element of N2. 3485 o For each element y in N2, if the corresponding address is in the 3486 N_neighbor_addr_list of a reachable Neighbor Tuple, then define 3487 d1(y) to be the N_in_metric of that Neighbor Tuple, otherwise 3488 d1(y) is not defined. 3490 o For each element x in N1, define N2(x) as the set of elements y in 3491 N2 whose corresponding address is the N2_2hop_addr of an allowed 3492 2-Hop Tuple that has N2_neighbor_iface_addr_list contained in 3493 N_neighbor_addr_list of the Neighbor Tuple corresponding to x. 3494 For all such x and y, define d2(x,y) := N2_out_metric of that 3495 2-Hop Tuple. 3497 It is up to an implementation to decide how to label each element of 3498 N1 or N2. For example an element of N1 may be labeled with one or 3499 more addresses from the corresponding N_neighbor_addr_list, or with a 3500 pointer or reference to the corresponding Neighbor Tuple. 3502 Using these Neighbor Graphs, routing MPRs are selected and recorded 3503 according to the following: 3505 o Determine an MPR Set as specified in Section 18.3. 3507 o A Neighbor Tuple represents a routing MPR and has N_routing_mpr := 3508 true (otherwise N_routing_mpr := false) if and only if that 3509 Neighbor Tuple corresponds to an element in the MPR Set created as 3510 described above. 3512 18.6. Calculating MPRs 3514 A router MUST recalculate each of its sets of MPRs whenever the 3515 currently selected set of MPRs does not still satisfy the required 3516 conditions. It MAY recalculate its MPRs if the current set of MPRs 3517 is still valid, but could be more efficient. Sufficient conditions 3518 to recalculate a router's sets of MPRs are given in Section 17.6. 3520 19. Routing Set Calculation 3522 The Routing Set of a router is populated with Routing Tuples that 3523 represent paths from that router to all destinations in the network. 3524 These paths are calculated based on the Network Topology Graph, which 3525 is constructed from information in the Information Bases, obtained 3526 via HELLO and TC message exchange. 3528 Changes to the Routing Set do not require any messages to be 3529 transmitted. The state of the Routing Set SHOULD, however, be 3530 reflected in the IP routing table by adding and removing entries from 3531 that routing table as appropriate. Only appropriate Routing Tuples 3532 (in particular only those that represent local links or paths to 3533 routable addresses) need be reflected in the IP routing table. 3535 19.1. Network Topology Graph 3537 The Network Topology Graph is formed from information from the 3538 router's Local Interface Set, Link Sets for OLSRv2 interfaces, 3539 Neighbor Set, Router Topology Set, Routable Address Topology Set and 3540 Attached Network Set. The Network Topology Graph MAY also use 3541 information from the router's 2-Hop Sets for OLSRv2 interfaces. The 3542 Network Topology Graph forms the router's topological view of the 3543 network in form of a directed graph. Each edge in that graph has a 3544 metric value. The Network Topology Graph has a "backbone" (within 3545 which minimum total metric routes will be constructed) containing the 3546 following edges: 3548 o Edges X -> Y for all possible Y, and one X per Y, such that: 3550 * Y is the N_orig_addr of a Neighbor Tuple; AND 3552 * N_orig_addr is not unknown; 3554 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3555 AND 3557 * There is a Link Tuple with L_status = SYMMETRIC and 3558 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3559 and this Local Interface Tuple correspond to it. A network 3560 address from L_neighbor_iface_addr_list will be denoted R in 3561 this case. 3563 It SHOULD be preferred, where possible, to select R = S and X from 3564 the Local Interface Tuple corresponding to the Link Tuple from 3565 which R was selected. The metric for such an edge is the 3566 corresponding N_out_metric. 3568 o All edges W -> U such that: 3570 * W is the TR_from_orig_addr of a Router Topology Tuple; AND 3572 * U is the TR_to_orig_addr of the same Router Topology Tuple. 3574 The metric of such an edge is the corresponding TR_metric. 3576 The Network Topology Graph is further "decorated" with the following 3577 edges. If a network address S, V, Z or T equals a network address Y 3578 or W, then the edge terminating in the network address S, V, Z or T 3579 MUST NOT be used in any path. 3581 o Edges X -> S for all possible S, and one X per S, such that: 3583 * S is in the N_neighbor_addr_list of a Neighbor Tuple; AND 3585 * X is in the I_local_iface_addr_list of a Local Interface Tuple; 3586 AND 3588 * There is a Link Tuple with L_status = SYMMETRIC and 3589 L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple 3590 and this Local Interface Tuple correspond to it. A network 3591 address from L_neighbor_iface_addr_list will be denoted R in 3592 this case. 3594 It SHOULD be preferred, where possible, to select R = S and X from 3595 the Local Interface Tuple corresponding to the Link Tuple from 3596 which R was selected. The metric for such an edge is the 3597 corresponding N_out_metric. 3599 o All edges W -> V such that: 3601 * W is the TA_from_orig_addr of a Routable Address Topology 3602 Tuple; AND 3604 * V is the TA_dest_addr of the same Routable Address Topology 3605 Tuple. 3607 The metric for such an edge is the corresponding TA_metric. 3609 o All edges W -> T such that: 3611 * W is the AN_orig_addr of an Attached Network Tuple; AND 3613 * T is the AN_net_addr of the same Attached Network Tuple. 3615 The metric for such an edge is the corresponding AN_metric. 3617 o (OPTIONAL) All edges Y -> Z such that: 3619 * Z is a routable address and is the N2_2hop_addr of a 2-Hop 3620 Tuple with N2_out_metric != UNKNOWN_METRIC; AND 3622 * Y is the N_orig_addr of the corresponding Neighbor Tuple; AND 3624 * This Neighbor Tuple has N_will_routing not equal to WILL_NEVER. 3626 A path terminating with such an edge MUST NOT be used in 3627 preference to any other path. The metric for such an edge is the 3628 corresponding N2_out_metric. 3630 Any part of the Topology Graph which is not connected to a local 3631 network address X is not used. Only one selection X SHOULD be made 3632 from each I_local_iface_addr_list, and only one selection R SHOULD be 3633 made from any L_neighbor_iface_addr_list. All edges have a hop count 3634 of 1, except edges W -> T that have a hop count of the corresponding 3635 value of AN_dist. 3637 19.2. Populating the Routing Set 3639 The Routing Set MUST contain the shortest paths for all destinations 3640 from all local OLSRv2 interfaces using the Network Topology Graph. 3641 This calculation MAY use any algorithm, including any means of 3642 choosing between paths of equal total metric. (In the case of two 3643 paths of equal total metric but differing hop counts, the path with 3644 the lower hop count SHOULD be used.) 3646 Using the notation of Section 19.1, initially "backbone" paths using 3647 only edges X -> Y and W -> U need be constructed (using a minimum 3648 distance algorithm). Then paths using only a final edge of the other 3649 types may be added. These MUST NOT replace backbone paths with the 3650 same destination (and paths terminating in an edge Y -> Z SHOULD NOT 3651 replace paths with any other form of terminating edge). 3653 Each path will correspond to a Routing Tuple. These will be of two 3654 types. The first type will represent single edge paths, of type X -> 3655 S or X -> Y, by: 3657 o R_local_iface_addr := X; 3659 o R_next_iface_addr := R; 3661 o R_dest_addr := S or Y; 3663 o R_dist := 1; 3665 o R_metric := edge metric, 3667 where R is as defined in Section 19.1 for these types of edges. 3669 The second type will represent a multiple edge path, which will 3670 always have first edge of type X -> Y, and will have final edge of 3671 type W -> U, W -> V, W -> T or Y -> Z. The Routing Tuple will be: 3673 o R_local_iface_addr := X; 3675 o R_next_iface_addr := Y; 3676 o R_dest_addr := U, V, T or Z; 3678 o R_dist := the total hop count of all edges in the path; 3680 o R_metric := the total metric of all edges in the path. 3682 Finally, Routing Tuples of the second type whose R_dest_addr is not 3683 routable MAY be discarded. 3685 An example algorithm for calculating the Routing Set of a router is 3686 given in Appendix B. 3688 20. Proposed Values for Parameters 3690 This protocol uses all parameters defined in [RFC6130] and additional 3691 parameters and defined in this specification. All but one 3692 (RX_HOLD_TIME) of these additional parameters are router parameters 3693 as defined in [RFC6130]. The proposed values of the additional 3694 parameters defined in the following sections are appropriate to the 3695 case where all parameters (including those defined in [RFC6130]) have 3696 a single value. Proposed values for parameters defined in [RFC6130] 3697 are given in that specification. 3699 20.1. Local History Time Parameters 3701 o O_HOLD_TIME := 30 seconds 3703 20.2. Message Interval Parameters 3705 o TC_INTERVAL := 5 seconds 3707 o TC_MIN_INTERVAL := TC_INTERVAL/4 3709 20.3. Advertised Information Validity Time Parameters 3711 o T_HOLD_TIME := 3 x TC_INTERVAL 3713 o A_HOLD_TIME := T_HOLD_TIME 3715 20.4. Received Message Validity Time Parameters 3717 o RX_HOLD_TIME := 30 seconds 3719 o P_HOLD_TIME := 30 seconds 3721 o F_HOLD_TIME := 30 seconds 3723 20.5. Jitter Time Parameters 3725 o TP_MAXJITTER := HP_MAXJITTER 3727 o TT_MAXJITTER := HT_MAXJITTER 3729 o F_MAXJITTER := TT_MAXJITTER 3731 20.6. Hop Limit Parameter 3733 o TC_HOP_LIMIT := 255 3735 20.7. Willingness Parameter 3737 o WILL_FLOODING := WILL_DEFAULT 3739 o WILL_ROUTING := WILL_DEFAULT 3741 21. Sequence Numbers 3743 Sequence numbers are used in this specification for the purpose of 3744 discarding "old" information, i.e., messages received out of order. 3745 However with a limited number of bits for representing sequence 3746 numbers, wrap-around (that the sequence number is incremented from 3747 the maximum possible value to zero) will occur. To prevent this from 3748 interfering with the operation of this protocol, the following MUST 3749 be observed when determining the ordering of sequence numbers. 3751 The term MAXVALUE designates in the following one more than the 3752 largest possible value for a sequence number. For a 16 bit sequence 3753 number (as are those defined in this specification) MAXVALUE is 3754 65536. 3756 The sequence number S1 is said to be "greater than" the sequence 3757 number S2 if: 3759 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 3761 o S2 > S1 AND S2 - S1 > MAXVALUE/2 3763 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 3764 cannot be determined. In this case, which should not occur, either 3765 ordering may be assumed. 3767 Thus when comparing two messages, it is possible - even in the 3768 presence of wrap-around - to determine which message contains the 3769 most recent information. 3771 22. Extensions 3773 An extension to this protocol will need to interact with this 3774 specification, and possibly also with [RFC6130]. This protocol is 3775 designed to permit such interactions, in particular: 3777 o Through accessing, and possibly extending, the information in the 3778 Information Bases. All updates to the elements specified in this 3779 specification are subject to the constraints specified in 3780 [RFC6130] and Appendix D. 3782 o Through accessing an outgoing message prior to it being 3783 transmitted over any OLSRv2 interface, and to add information to 3784 it as specified in [RFC5444]. This MAY include Message TLVs 3785 and/or network addresses with associated Address Block TLVs. 3786 (Network addresses without new associated TLVs SHOULD NOT be added 3787 to messages.) This may, for example, be to allow a security 3788 protocol, as suggested in Section 23, to add a TLV containing a 3789 cryptographic signature to the message. 3791 o Through accessing an incoming message, and potentially discarding 3792 it prior to processing by this protocol. This may, for example, 3793 allow a security protocol, as suggested in Section 23, to perform 3794 verification of message signatures and prevent processing and/or 3795 forwarding of unverifiable messages by this protocol. 3797 o Through accessing an incoming message after it has been completely 3798 processed by this protocol. In particular, this may allow a 3799 protocol which has added information, by way of inclusion of 3800 appropriate TLVs, or of network addresses associated with new 3801 TLVs, access to such information after appropriate updates have 3802 been recorded in the Information Bases in this protocol. 3804 o Through requesting that a message be generated at a specific time. 3805 In that case, message generation MUST still respect the 3806 constraints in [RFC6130] and Section 5.4.3. 3808 23. Security Considerations 3810 Currently, this protocol does not specify any special security 3811 measures. As a proactive routing protocol, this protocol is a 3812 potential target for various attacks. Various possible 3813 vulnerabilities are discussed in this section. 3815 23.1. Confidentiality 3817 This protocol periodically MPR floods topological information to all 3818 routers in the network. Hence, if used in an unprotected network, 3819 such as an unprotected wireless network, the network topology is 3820 revealed to anyone who listens to the control messages. 3822 In situations where the confidentiality of the network topology is of 3823 importance, regular cryptographic techniques, such as exchange of 3824 OLSRv2 control traffic messages encrypted by PGP [RFC4880] or 3825 encrypted by some shared secret key, can be applied to ensure that 3826 control traffic can be read and interpreted by only those authorized 3827 to do so. 3829 23.2. Integrity 3831 Each router is injecting topological information into the network 3832 through transmitting HELLO messages and, for some routers, TC 3833 messages. If some routers for some reason, malice or malfunction, 3834 inject invalid control traffic, network integrity may be compromised. 3835 Therefore, message authentication is RECOMMENDED. 3837 Different such situations may occur, for instance: 3839 1. A router generates TC messages, advertising links to non-neighbor 3840 routers; 3842 2. A router generates TC messages, pretending to be another router; 3844 3. A router generates HELLO messages, advertising non-neighbor 3845 routers; 3847 4. A router generates HELLO messages, pretending to be another 3848 router; 3850 5. A router forwards altered control messages; 3852 6. A router does not forward control messages; 3854 7. A router does not select multipoint relays correctly; 3856 8. A router forwards broadcast control messages unaltered, but does 3857 not forward unicast data traffic; 3859 9. A router "replays" previously recorded control traffic from 3860 another router. 3862 Authentication of the originator router for control messages (for 3863 situations 2, 4 and 5) and on the individual links announced in the 3864 control messages (for situations 1 and 3) may be used as a 3865 countermeasure. However to prevent routers from repeating old (and 3866 correctly authenticated) information (situation 9) temporal 3867 information is required, allowing a router to positively identify 3868 such delayed messages. 3870 In general, digital signatures and other required security 3871 information MAY be transmitted as a separate Message Type, or 3872 signatures and security information MAY be transmitted within the 3873 HELLO and TC messages, using the TLV mechanism. Either option 3874 permits that "secured" and "unsecured" routers can coexist in the 3875 same network, if desired. 3877 Specifically, the authenticity of entire control packets can be 3878 established through employing IPsec authentication headers, whereas 3879 authenticity of individual links (situations 1 and 3) require 3880 additional security information to be distributed. 3882 An important consideration is that all control messages (HELLO 3883 messages and TC messages) are transmitted to all routers in the 1-hop 3884 neighborhood and some (TC messages) are flooded to all routers in the 3885 network. 3887 Thus, a control message in this protocol is always a point-to- 3888 multipoint transmission. It is therefore important that the 3889 authentication mechanism employed permits that any receiving router 3890 can validate the authenticity of a message. As an analogy, given a 3891 block of text, signed by a PGP private key, then anyone with the 3892 corresponding public key can verify the authenticity of the text. 3894 23.3. Interaction with External Routing Domains 3896 This protocol does, through the use of TC messages, provide a basic 3897 mechanism for injecting external routing information to this 3898 protocol's domain. Routing information can be extracted from the 3899 protocol's Information Bases, in particular the Routing Set, of this 3900 protocol and, potentially, injected into an external domain, if the 3901 routing protocol governing that domain permits this. 3903 When operating routers connecting a MANET using this protocol to an 3904 external routing domain, care MUST be taken not to allow potentially 3905 insecure and untrustworthy information to be injected from this 3906 domain to external routing domains. Care MUST also be taken to 3907 validate the correctness of information prior to it being injected as 3908 to avoid polluting routing tables with invalid information. 3910 A RECOMMENDED way of extending connectivity from an external routing 3911 domain to a MANET routed using this protocol is to assign an IP 3912 prefix (under the authority of the routers/gateways connecting the 3913 MANET with the external routing domain) exclusively to that MANET 3914 area, and to statically configure the gateways to advertise routes 3915 for that IP sequence to routers in the external routing domain. 3917 24. IANA Considerations 3919 This specification defines one Message Type, which must be allocated 3920 from the "Message Types" repository of [RFC5444], two Message TLV 3921 Types, which must be allocated from the "Message TLV Types" 3922 repository of [RFC5444], and four Address Block TLV Types, which must 3923 be allocated from the "Address Block TLV Types" repository of 3924 [RFC5444]. 3926 24.1. Expert Review: Evaluation Guidelines 3928 For the registries where an Expert Review is required, the designated 3929 expert SHOULD take the same general recommendations into 3930 consideration as are specified by [RFC5444]. 3932 24.2. Message Types 3934 This specification defines one Message Type, to be allocated from the 3935 0-223 range of the "Message Types" namespace defined in [RFC5444], as 3936 specified in Table 8. 3938 +------+----------------------------------------------+ 3939 | Type | Description | 3940 +------+----------------------------------------------+ 3941 | TBD1 | TC : Topology Control (MANET-wide signaling) | 3942 +------+----------------------------------------------+ 3944 Table 8: Message Type assignment 3946 24.3. Message-Type-Specific TLV Type Registries 3948 IANA is requested to create a registry for Message-Type-specific 3949 Message TLVs for TC messages, in accordance with Section 6.2.1 of 3950 [RFC5444], and with initial assignments and allocation policies as 3951 specified in Table 9. 3953 +---------+-------------+-------------------+ 3954 | Type | Description | Allocation Policy | 3955 +---------+-------------+-------------------+ 3956 | 128-223 | Unassigned | Expert Review | 3957 +---------+-------------+-------------------+ 3959 Table 9: TC Message-Type-specific Message TLV Types 3961 IANA is requested to create a registry for Message-Type-specific 3962 Address Block TLVs for TC messages, in accordance with Section 6.2.1 3963 of [RFC5444], and with initial assignments and allocation policies as 3964 specified in Table 10. 3966 +---------+-------------+-------------------+ 3967 | Type | Description | Allocation Policy | 3968 +---------+-------------+-------------------+ 3969 | 128-223 | Unassigned | Expert Review | 3970 +---------+-------------+-------------------+ 3972 Table 10: TC Message-Type-specific Address Block TLV Types 3974 24.4. Message TLV Types 3976 This specification defines two Message TLV Types, which must be 3977 allocated from the "Message TLV Types" namespace defined in 3978 [RFC5444]. IANA is requested to make allocations in the 0-127 range 3979 for these types. This will create two new Type Extension registries 3980 with assignments as specified in Table 11 and Table 12. 3981 Specifications of these TLVs are in Section 13.3.1. Each of these 3982 TLVs MUST NOT be included more than once in a Message TLV Block. 3984 +-------------+------+-----------+---------------------+------------+ 3985 | Name | Type | Type | Description | Allocation | 3986 | | | Extension | | Policy | 3987 +-------------+------+-----------+---------------------+------------+ 3988 | MPR_WILLING | TBD2 | 0 | Bits 0-3 specify | | 3989 | | | | the originating | | 3990 | | | | router's | | 3991 | | | | willingness to act | | 3992 | | | | as a flooding MPR; | | 3993 | | | | bits 4-7 specify | | 3994 | | | | the originating | | 3995 | | | | router's | | 3996 | | | | willingness to act | | 3997 | | | | as a routing MPR. | | 3998 | MPR_WILLING | TBD2 | 1-255 | Unassigned. | Expert | 3999 | | | | | Review | 4000 +-------------+------+-----------+---------------------+------------+ 4002 Table 11: Message TLV Type assignment: MPR_WILLING 4004 +--------------+------+-----------+--------------------+------------+ 4005 | Name | Type | Type | Description | Allocation | 4006 | | | Extension | | Policy | 4007 +--------------+------+-----------+--------------------+------------+ 4008 | CONT_SEQ_NUM | TBD3 | 0 | COMPLETE: | | 4009 | | | | Specifies a | | 4010 | | | | content sequence | | 4011 | | | | number for this | | 4012 | | | | complete message. | | 4013 | CONT_SEQ_NUM | TBD3 | 1 | INCOMPLETE: | | 4014 | | | | Specifies a | | 4015 | | | | content sequence | | 4016 | | | | number for this | | 4017 | | | | incomplete | | 4018 | | | | message. | | 4019 | CONT_SEQ_NUM | TBD3 | 2-255 | Unassigned. | Expert | 4020 | | | | | Review | 4021 +--------------+------+-----------+--------------------+------------+ 4023 Table 12: Message TLV Type assignment: CONT_SEQ_NUM 4025 Type extensions indicated as Expert Review SHOULD be allocated as 4026 described in [RFC5444], based on Expert Review as defined in 4027 [RFC5226]. 4029 24.5. Address Block TLV Types 4031 This specification defines four Address Block TLV Types, which must 4032 be allocated from the "Address Block TLV Types" namespace defined in 4033 [RFC5444]. IANA are requested to make allocations in the 8-127 range 4034 for these types. This will create four new Type Extension registries 4035 with assignments as specified in Table 13, Table 14, Table 15 and 4036 Table 16. Specifications of these TLVs are in Section 13.3.2. 4038 +-------------+------+-----------+-------------------+--------------+ 4039 | Name | Type | Type | Description | Allocation | 4040 | | | Extension | | Policy | 4041 +-------------+------+-----------+-------------------+--------------+ 4042 | LINK_METRIC | TBD4 | 0 | Link metric | | 4043 | | | | meaning assigned | | 4044 | | | | by administrative | | 4045 | | | | action. | | 4046 | LINK_METRIC | TBD4 | 1-223 | Unassigned. | Expert | 4047 | | | | | Review | 4048 | LINK_METRIC | TBD4 | 224-255 | Unassigned. | Experimental | 4049 | | | | | Use | 4050 +-------------+------+-----------+-------------------+--------------+ 4052 Table 13: Address Block TLV Type assignment: LINK_METRIC 4054 All LINK_METRIC TLVs, whatever their type extension, MUST use their 4055 value field to encode the kind and value (in the interval 4056 MINIMUM_METRIC, to MAXIMUM_METRIC, inclusive) of a link metric as 4057 specified in Section 6 and Section 13.3.2. An assignment of a 4058 LINK_METRIC TLV type extension MUST specify the physical meaning, and 4059 mapping of that physical meaning to the representable values in the 4060 indicated interval, of the link metric. 4062 +------+------+-----------+----------------------------+------------+ 4063 | Name | Type | Type | Description | Allocation | 4064 | | | Extension | | Policy | 4065 +------+------+-----------+----------------------------+------------+ 4066 | MPR | TBD5 | 0 | Specifies that a given | | 4067 | | | | network address is of a | | 4068 | | | | router selected as a | | 4069 | | | | flooding MPR (FLOODING = | | 4070 | | | | 1), that a given network | | 4071 | | | | address is of a router | | 4072 | | | | selected as a routing MPR | | 4073 | | | | (ROUTING = 2), or both | | 4074 | | | | (FLOOD_ROUTE = 3). | | 4075 | MPR | TBD5 | 1-255 | Unassigned. | Expert | 4076 | | | | | Review | 4077 +------+------+-----------+----------------------------+------------+ 4079 Table 14: Address Block TLV Type assignment: MPR 4081 +---------------+------+-----------+-------------------+------------+ 4082 | Name | Type | Type | Description | Allocation | 4083 | | | Extension | | Policy | 4084 +---------------+------+-----------+-------------------+------------+ 4085 | NBR_ADDR_TYPE | TBD6 | 0 | Specifies that a | | 4086 | | | | given network | | 4087 | | | | address is of a | | 4088 | | | | neighbor reached | | 4089 | | | | via the | | 4090 | | | | originating | | 4091 | | | | router, if it is | | 4092 | | | | an originator | | 4093 | | | | address | | 4094 | | | | (ORIGINATOR = 1), | | 4095 | | | | is a routable | | 4096 | | | | address (ROUTABLE | | 4097 | | | | = 2), or if it is | | 4098 | | | | both | | 4099 | | | | (ROUTABLE_ORIG = | | 4100 | | | | 3). | | 4101 | NBR_ADDR_TYPE | TBD6 | 1-255 | Unassigned. | Expert | 4102 | | | | | Review | 4103 +---------------+------+-----------+-------------------+------------+ 4105 Table 15: Address Block TLV Type assignment: NBR_ADDR_TYPE 4107 +---------+------+-----------+-------------------------+------------+ 4108 | Name | Type | Type | Description | Allocation | 4109 | | | extension | | Policy | 4110 +---------+------+-----------+-------------------------+------------+ 4111 | GATEWAY | TBD7 | 0 | Specifies that a given | | 4112 | | | | network address is | | 4113 | | | | reached via a gateway | | 4114 | | | | on the originating | | 4115 | | | | router, with value | | 4116 | | | | equal to the number of | | 4117 | | | | hops. | | 4118 | GATEWAY | TBD7 | 1-255 | | Expert | 4119 | | | | | Review | 4120 +---------+------+-----------+-------------------------+------------+ 4122 Table 16: Address Block TLV Type assignment: GATEWAY 4124 Type extensions indicated as Expert Review SHOULD be allocated as 4125 described in [RFC5444], based on Expert Review as defined in 4126 [RFC5226]. 4128 24.6. NBR_ADDR_TYPE and MPR Values 4130 Note: This section does not require any IANA action, as the required 4131 information is included in the descriptions of the MPR and 4132 NBR_ADDR_TYPE Address Block TLVs allocated in Section 24.5. This 4133 information is recorded here for clarity, and for use elsewhere in 4134 this specification. 4136 The Values which the MPR Address Block TLV can use are the following: 4138 o FLOODING := 1; 4140 o ROUTING := 2; 4142 o FLOOD_ROUTE := 3. 4144 The Values which the NBR_ADDR_TYPE Address Block TLV can use are the 4145 following: 4147 o ORIGINATOR := 1; 4149 o ROUTABLE := 2; 4151 o ROUTABLE_ORIG := 3. 4153 25. Contributors 4155 This specification is the result of the joint efforts of the 4156 following contributors -- listed alphabetically. 4158 o Cedric Adjih, INRIA, France, 4160 o Emmanuel Baccelli, INRIA , France, 4162 o Thomas Heide Clausen, LIX, France, 4164 o Justin Dean, NRL, USA, 4166 o Christopher Dearlove, BAE Systems, UK, 4167 4169 o Ulrich Herberg, Fujitsu Laboratories of America, USA, 4170 4172 o Satoh Hiroki, Hitachi SDL, Japan, 4174 o Philippe Jacquet, Alcatel Lucent Bell Labs, France, 4175 4177 o Monden Kazuya, Hitachi SDL, Japan, 4179 o Kenichi Mase, Niigata University, Japan, 4181 o Ryuji Wakikawa, Toyota, Japan, 4183 26. Acknowledgments 4185 The authors would like to acknowledge the team behind OLSRv1, as 4186 listed in RFC3626, including Anis Laouiti (INT), Pascale Minet 4187 (INRIA), Paul Muhlethaler (INRIA), Amir Qayyum (M.A. Jinnah 4188 University), and Laurent Viennot (INRIA) for their contributions. 4190 The authors would like to gratefully acknowledge the following people 4191 for intense technical discussions, early reviews and comments on the 4192 specification and its components (listed alphabetically): Khaldoun Al 4193 Agha (LRI), Teco Boot (Infinity Networks), Song-Yean Cho (Samsung), 4194 Alan Cullen (BAE Systems), Louise Lamont (CRC), Li Li (CRC), Joseph 4195 Macker (NRL), Richard Ogier (SRI), Charles E. Perkins (Futurewei), 4196 Henning Rogge (Frauenhofer FKIE), and the entire IETF MANET Working 4197 Group. 4199 27. References 4201 27.1. Normative References 4203 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 4204 Requirement Levels", RFC 2119, BCP 14, March 1997. 4206 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 4207 Considerations in Mobile Ad Hoc Networks (MANETs)", 4208 RFC 5148, February 2008. 4210 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 4211 IANA Considerations Section in RFCs", RFC 5226, BCP 26, 4212 May 2008. 4214 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 4215 "Generalized Mobile Ad Hoc Network (MANET) Packet/ 4216 Message Format", RFC 5444, February 2009. 4218 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 4219 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, 4220 March 2009. 4222 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc 4223 Network (MANET) Protocols", RFC 5498, March 2009. 4225 [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc 4226 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 4227 RFC 6130, April 2011. 4229 27.2. Informative References 4231 [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking 4232 (MANET): Routing Protocol Performance Issues and 4233 Evaluation Considerations", RFC 2501, January 1999. 4235 [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State 4236 Routing Protocol", RFC 3626, October 2003. 4238 [RFC4880] Callas, J., Donnerhacke, L., Finney, H., and R. Thayer, 4239 "OpenPGP message format", RFC 4880, November 2007. 4241 [HIPERLAN] ETSI, "ETSI STC-RES10 Committee. Radio equipment and 4242 systems: HIPERLAN type 1, functional specifications ETS 4243 300-652", June 1996. 4245 [HIPERLAN2] Jacquet, P., Minet, P., Muhlethaler, P., and N. 4246 Rivierre, "Increasing reliability in cable free radio 4247 LANs: Low level forwarding in HIPERLAN.", 1996. 4249 [MPR] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint 4250 relaying: An efficient technique for flooding in mobile 4251 wireless networks.", 2001. 4253 [FSR] Pei, G., Gerla, M., and T. Chen, "Fisheye state routing 4254 in mobile ad hoc networks", 2000. 4256 [FSLS] Santivanez, C., Ramanathan, R., and I. Stavrakakis, 4257 "Making link-state routing scale for ad hoc networks", 4258 2000. 4260 Appendix A. Example Algorithm for Calculating MPRs 4262 The following specifies an algorithm which MAY be used to select an 4263 MPR Set given a Neighbor Graph, as defined in Section 18.2 and 4264 Section 18.3. 4266 This algorithm selects an MPR Set M that is a subset of the set N1 4267 that is part of the Neighbor Graph. This algorithm assumes that a 4268 subset I of N1 is pre-selected as MPRs, i.e., that M will contain I. 4270 A.1. Additional Notation 4272 The following additional notation, in addition to that in 4273 Section 18.2 will be used by this algorithm: 4275 N: 4276 A subset of N2, consisting of those elements y in N2 such that 4277 either d1(y) is not defined, or there is at least one x in N1 such 4278 that d(x,y) is defined and d(x,y) < d1(y). 4280 D(x): 4281 For an element x in N1, the number of elements y in N for which 4282 d(x,y) is defined and has minimal value among the d(z,y) for all z 4283 in N1. 4285 R(x,M): 4286 For an element x in N1, the number of elements y in N for which 4287 d(x,y) is defined, has minimal value among the d(z,y) for all z in 4288 N1, and no such minimal values have z in M. (Note that, denoting 4289 the empty set by 0, D(x) = R(x,0).) 4291 A.2. MPR Selection Algorithm 4293 To create the MPR Set M, starting with M := I: 4295 1. Add all elements x in N1 that have W(x) = WILL_ALWAYS to M. 4297 2. For each element y in N for which there is only one element x in 4298 N1 such that d2(x,y) is defined, add that element x to M. 4300 3. While there exists any element x in N1 with R(x,M) > 0: 4302 1. Select an element x in N1 with R(x,M) > 0 in the following 4303 order of priority, and then add to M: 4305 + greatest W(x), THEN; 4307 + greatest R(x,M), THEN; 4309 + greatest D(x), THEN; 4311 + any choice, which MAY be based on other criteria (for 4312 example a router MAY choose to prefer a neighbor as an MPR 4313 if that neighbor has already selected the router as an MPR 4314 of the same type, MAY prefer a neighbor based on 4315 information freshness, or MAY prefer a neighbor based on 4316 length of time previously selected as an MPR) or MAY be 4317 random. 4319 4. OPTIONAL: consider each element x in M, but not in I, in turn and 4320 if x can be removed from M while still leaving it satisfying the 4321 definition of an MPR Set, then remove that element x from M. 4322 Elements MAY be considered in any order, e.g., in order of 4323 increasing W(x). 4325 Appendix B. Example Algorithm for Calculating the Routing Set 4327 The following procedure is given as an example for calculating the 4328 Routing Set using a variation of Dijkstra's algorithm. First all 4329 Routing Tuples are removed, and then, using the selections and 4330 definitions in Appendix B.1, the procedures in the following sections 4331 (each considered a "stage" of the processing) are applied in turn. 4333 B.1. Local Interfaces and Neighbors 4335 The following selections and definitions are made: 4337 1. For each Local Interface Tuple, select a network address from its 4338 I_local_iface_addr_list, this is defined as the selected address 4339 for this Local Interface Tuple. 4341 2. For each Link Tuple, the selected address of its corresponding 4342 Local Interface Tuple is defined as the selected local address 4343 for this Local Interface Tuple. 4345 3. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4346 != UNKNOWN_METRIC, select a Link Tuple with L_status = SYMMETRIC 4347 for which this is the corresponding Neighbor Tuple and has 4348 L_out_metric = N_out_metric. This is defined as the selected 4349 Link Tuple for this Neighbor Tuple. 4351 4. For each network address (N_orig_addr or in N_neighbor_addr_list, 4352 the "neighbor address") from a Neighbor Tuple with N_symmetric = 4353 true and N_out_metric != UNKNOWN_METRIC, select a Link Tuple (the 4354 "selected Link Tuple") from those for which this is the 4355 corresponding Neighbor Tuple, have L_status = SYMMETRIC, and have 4356 L_out_metric = N_out_metric, by: 4358 1. If there is such a Link Tuple whose 4359 L_neighbor_iface_addr_list contains the neighbor address, 4360 select that Link Tuple. 4362 2. Otherwise select the selected Link Tuple for this Neighbor 4363 Tuple. 4365 Then for this neighbor address: 4367 3. The selected local address is defined as the selected local 4368 address for the selected Link Tuple. 4370 4. The selected link address is defined as an address from the 4371 L_neighbor_iface_addr_list of the selected Link Tuple, if 4372 possible equal to this neighbor address. 4374 5. Routing Tuple preference is decided by preference for minimum 4375 R_dist, then for minimum R_dist, and then for preference for 4376 corresponding Neighbor Tuples in this order: 4378 * For greater N_will_routing. 4380 * For N_mpr_selector = true over N_mpr_selector = false. 4382 Note that preferred Routing Tuples SHOULD be used. Routing 4383 Tuples with minimum R_metric MUST be used, this is specified 4384 outside the definition of preference. An implementation MAY 4385 modify this definition of preference (including for minimum 4386 R_dist) without otherwise affecting this algorithm. 4388 B.2. Add Neighbor Routers 4390 The following procedure is executed once. 4392 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4393 != UNKNOWN_METRIC, add a Routing Tuple with: 4395 * R_dest_addr := N_orig_addr; 4397 * R_next_iface_addr := selected link address for N_orig_addr; 4399 * R_local_iface_addr := selected local address for N_orig_addr; 4401 * R_metric := N_out_metric; 4403 * R_dist := 1. 4405 B.3. Add Remote Routers 4407 The following procedure is executed once. 4409 1. Add a label that may be "used" or "unused" to each Routing Tuple, 4410 with all initial values equal to unused. (Note that this label 4411 is only required during this algorithm.) 4413 2. If there are no unused Routing Tuples then this stage is 4414 complete, otherwise repeat the following until that is the case. 4416 1. Find the unused Routing Tuple with minimum R_metric (if more 4417 than one, pick any) and denote it the "current Routing 4418 Tuple". 4420 2. Mark the current Routing Tuple as used. 4422 3. For each Router Topology Tuple, with: 4424 + TR_from_orig_addr = R_dest_addr of the current Routing 4425 Tuple. 4427 2. Define: 4429 - new_metric := R_metric of the current Routing Tuple + 4430 TR_metric; 4432 - new_dist := R_dist of the current Routing Tuple + 1. 4434 3. If there is no Routing Tuple with R_dest_addr = 4435 TR_to_orig_addr, then create an unused Routing Tuple 4436 with: 4438 - R_dest_addr := TR_to_orig_addr; 4440 - R_next_iface_addr := R_next_iface_addr of the current 4441 Routing Tuple; 4443 - R_local_iface_addr := R_local_iface_addr of the 4444 current Routing Tuple; 4446 - R_metric := new_metric; 4448 - R_dist := new_dist. 4450 4. Otherwise, if there is an unused Routing Tuple with 4451 R_dest_addr = TR_to_orig_addr, and either new_metric < 4452 R_metric or (new_metric = R_metric and the updated 4453 Routing Tuple would be preferred) then update this 4454 Routing Tuple to have: 4456 - R_next_iface_addr := R_next_iface_addr of the current 4457 Routing Tuple; 4459 - R_local_iface_addr := R_local_iface_addr of the 4460 current Routing Tuple; 4462 - R_metric := new_metric; 4463 - R_dist := new_dist. 4465 B.4. Add Neighbor Addresses 4467 The following procedure is executed once. 4469 1. For each Neighbor Tuple with N_symmetric = true and N_out_metric 4470 != UNKNOWN_METRIC: 4472 1. For each network address (the "neighbor address") in 4473 N_neighbor_addr_list, if the neighbor address is not equal to 4474 the R_dest_addr of any Routing Tuple, then add a new Routing 4475 Tuple, with: 4477 + R_dest_addr := neighbor address; 4479 + R_next_iface_addr := selected link address for the 4480 neighbor address; 4482 + R_local_iface_addr := selected local address for the 4483 neighbor address; 4485 + R_metric := N_out_metric; 4487 + R_dist := 1. 4489 B.5. Add Remote Routable Addresses 4491 The following procedure is executed once. 4493 1. For each Routable Address Topology Tuple, if: 4495 * TA_dest_addr is not equal to the R_dest_addr of any Routing 4496 Tuple added in an earlier stage; AND 4498 * TA_from_orig_addr is equal to the R_dest_addr of a Routing 4499 Tuple (the "previous Routing Tuple"), 4501 then add a new Routing Tuple, with: 4503 * R_dest_addr := TA_dest_addr; 4505 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4506 Tuple; 4508 * R_local_iface_addr := R_local_iface_addr of the previous 4509 Routing Tuple; 4511 * R_metric := R_metric of the previous Routing Tuple + 4512 TA_metric. 4514 * R_dist := R_dist of the previous Routing Tuple + 1. 4516 There may be more than one Routing Tuple that may be added for an 4517 R_dest_addr in this stage. If so, then, for each such 4518 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4519 selected, otherwise a Routing Tuple which is preferred SHOULD be 4520 added. 4522 B.6. Add Attached Networks 4524 The following procedure is executed once. 4526 1. For each Attached Network Tuple, if: 4528 * AN_net_addr is not equal to the R_dest_addr of any Routing 4529 Tuple added in an earlier stage; AND 4531 * AN_orig_addr is equal to the R_dest_addr of a Routing Tuple 4532 (the "previous Routing Tuple), 4534 then add a new Routing Tuple, with: 4536 * R_dest_addr := AN_net_addr; 4538 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4539 Tuple; 4541 * R_local_iface_addr := R_local_iface_addr of the previous 4542 Routing Tuple; 4544 * R_metric := R_metric of the previous Routing Tuple + 4545 AN_metric; 4547 * R_dist := R_dist of the previous Routing Tuple + AN_dist. 4549 There may be more than one Routing Tuple that may be added for an 4550 R_dest_addr in this stage. If so, then, for each such 4551 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4552 selected, otherwise a Routing Tuple which is preferred SHOULD be 4553 added. 4555 B.7. Add 2-Hop Neighbors 4557 The following procedure is executed once. 4559 1. For each 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC, if: 4561 * N2_2hop_addr is a routable address; AND 4563 * N2_2hop_addr is not equal to the R_dest_addr of any Routing 4564 Tuple added in an earlier stage; AND 4566 * the Routing Tuple with R_dest_addr = N_orig_addr of the 4567 corresponding Neighbor Tuple (the "previous Routing Tuple") 4568 has R_dist = 1, 4570 then add a new Routing Tuple, with: 4572 * R_dest_addr := N2_2hop_addr; 4574 * R_next_iface_addr := R_next_iface_addr of the previous Routing 4575 Tuple; 4577 * R_local_iface_addr := R_local_iface_addr of the previous 4578 Routing Tuple; 4580 * R_metric := R_metric of the previous Routing Tuple + 4581 N_out_metric of the corresponding Neighbor Tuple; 4583 * R_dist := 2. 4585 There may be more than one Routing Tuple that may be added for an 4586 R_dest_addr in this stage. If so, then, for each such 4587 R_dest_addr, a Routing Tuple with minimum R_metric MUST be 4588 selected, otherwise a Routing Tuple which is preferred SHOULD be 4589 added. 4591 Appendix C. TC Message Example 4593 TC messages are instances of [RFC5444] messages. This specification 4594 requires that TC messages contain and 4595 fields. It supports TC messages with any combination of remaining 4596 message header options and address encodings, enabled by [RFC5444] 4597 that convey the required information. As a consequence, there is no 4598 single way to represent how all TC messages look. This appendix 4599 illustrates a TC message, the exact values and content included are 4600 explained in the following text. 4602 The TC message's four bit Message Flags (MF) field has value 15 4603 indicating that the message header contains originator address, hop 4604 limit, hop count, and message sequence number fields. Its four bit 4605 Message Address Length (MAL) field has value 3, indicating addresses 4606 in the message have a length of four octets, here being IPv4 4607 addresses. The overall message length is 75 octets. 4609 The message has a Message TLV Block with content length 17 octets 4610 containing four TLVs. The first two TLVs are validity and interval 4611 times for the message. The third TLV is the content sequence number 4612 TLV used to carry the 2 octet ANSN, and (with default type extension 4613 zero, i.e., COMPLETE) indicating that the TC message is complete. 4614 The fourth TLV contains forwarding and routing willingness values for 4615 the originating router (FWILL and RWILL, respectively). Each TLV 4616 uses a TLV with Flags octet (MTLVF) value 16, indicating that it has 4617 a Value, but no type extension or start and stop indexes. The first 4618 two TLVs have a Value Length of 1 octet, the last has a Value Length 4619 of 2 octets. 4621 The message has two Address Blocks. (This is not necessary, the 4622 information could be conveyed using a single Address Block, the use 4623 of two Address Blocks, which is also allowed, is illustrative only.) 4624 The first Address Block contains 3 addresses, with Flags octet 4625 (ATLVF) value 128, hence with a Head section (with length 2 octets), 4626 but no Tail section, and hence with Mid sections with length two 4627 octets. The following TLV Block (content length 13 octets) contains 4628 two TLVs. The first TLV is a NBR_ADDR_TYPE TLV with Flags octet 4629 (ATLVF) value 16, indicating a single Value but no indexes. Thus all 4630 these addresses are associated with the Value (with Value Length 1 4631 octet) ROUTABLE_ORIG, i.e., they are originator addresses of 4632 advertised neighbors that are also routable addresses. The second 4633 TLV is a LINK_STATUS TLV with Flags octet (ATLVF) value 20, 4634 indicating a Value for each address, i.e., as the total Value Length 4635 is 6 octets, each address is associated with a Value with length two 4636 octets. These Value fields are each shown as having four bits 4637 indicating that they are outgoing neighbor metric values, and as 4638 having twelve bits that represent the metric value (the first four 4639 bits being the exponent, the remaining twelve bits the mantissa). 4641 The second Address Block contains 1 address, with Flags octet (ATLVF) 4642 176, indicating that there is a Head section (with length 2 octets), 4643 that the Tail section (with length 2 octets) consists of zero valued 4644 octets (not included), and that there is a single prefix length, 4645 which is 16. The network address is thus Head.0.0/16. The following 4646 TLV Block (content length 8 octets) includes two TLVs. The first has 4647 a Flags octet (ATLVF) of 16, again indicating that no indexes are 4648 needed, but that a Value (with Value Length 1 octet) is present, 4649 indicating the address distance as a number of hops. The second TLV 4650 is another LINK_METRIC TLV, as in the first Address TLV Block except 4651 with a Flags octet (ATLVF) value 16, indicating that a single Value 4652 is present. 4654 0 1 2 3 4655 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 4656 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4657 | TC | MF=15 | MAL=3 | Message Length = 75 | 4658 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4659 | Originator Address | 4660 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4661 | Hop Limit | Hop Count | Message Sequence Number | 4662 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4663 | Message TLV Block Length = 17 | VALIDITY_TIME | MTLVF = 16 | 4664 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4665 | Value Len = 1 | Value (Time) | INTERVAL_TIME | MTLVF = 16 | 4666 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4667 | Value Len = 1 | Value (Time) | CONT_SEQ_NUM | MTLVF = 16 | 4668 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4669 | Value Len = 2 | Value (ANSN) | MPR_WILLING | 4670 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4671 | MTLVF = 16 | Value Len = 1 | FWILL | RWILL | Num Addrs = 3 | 4672 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4673 | ABF = 128 | Head Len = 2 | Head | 4674 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4675 | Mid | Mid | 4676 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4677 | Mid | Address TLV Block Length = 13 | 4678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4679 | NBR_ADDR_TYPE | ATLVF = 16 | Value Len = 1 | ROUTABLE_ORIG | 4680 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4681 | LINK_METRIC | ATLVF = 20 | Value Len = 6 |0|0|0|1|Metric | 4682 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4683 | Metric (cont) |0|0|0|1| Metric |0|0|0|1|Metric | 4684 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4685 | Metric (cont) | Num Addrs = 1 | ABF = 176 | Head Len = 2 | 4686 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4687 | Head | Tail Len = 2 | Pref Len = 16 | 4688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4689 | Address TLV Block Length = 9 | GATEWAY | ATLVF = 16 | 4690 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4691 | Value Len = 1 | Value (Hops) | LINK_METRIC | ATLVF = 16 | 4692 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4693 | Value Len = 2 |0|0|0|1| Metric | 4694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4696 Appendix D. Constraints 4698 Any process which updates the Local Information Base, the 4699 Neighborhood Information Base or the Topology Information Base MUST 4700 ensure that all constraints specified in this appendix are 4701 maintained, as well as those specified in [RFC6130]. 4703 In each Originator Tuple: 4705 o O_orig_addr MUST NOT equal any other O_orig_addr. 4707 o O_orig_addr MUST NOT equal this router's originator address. 4709 In each Local Attached Network Tuple: 4711 o AL_net_addr MUST NOT equal any other AL_net_addr. 4713 o AL_net_addr MUST NOT equal or be a sub-range of any network 4714 address in the I_local_iface_addr_list of any Local Interface 4715 Tuple. 4717 o AL_net_addr MUST NOT equal this router's originator address, or 4718 equal the O_orig_addr in any Originator Tuple. 4720 o AL_dist MUST NOT be less than zero. 4722 In each Link Tuple: 4724 o L_neighbor_iface_addr_list MUST NOT contain any network address 4725 that AL_net_addr of any Local Attached Network Tuple equals or is 4726 a sub-range of. 4728 o if L_in_metric != UNKNOWN_METRIC then L_in_metric MUST be 4729 representable in the defined compressed form. 4731 o if L_out_metric != UNKNOWN_METRIC then L_out_metric MUST be 4732 representable in the defined compressed form. 4734 o If L_mpr_selector = true, then L_status = SYMMETRIC. 4736 In each Neighbor Tuple: 4738 o N_orig_addr MUST NOT be changed to unknown. 4740 o N_orig_addr MUST NOT equal this router's originator address, or 4741 equal O_orig_addr in any Originator Tuple. 4743 o N_orig_addr MUST NOT equal the AL_net_addr in any Local Attached 4744 Network Tuple. 4746 o If N_orig_addr != unknown, then N_orig_addr MUST NOT equal the 4747 N_orig_addr in any other Neighbor Tuple. 4749 o N_neighbor_addr_list MUST NOT contain any network address which 4750 includes this router's originator address, the O_orig_addr in any 4751 Originator Tuple, or equal or have as a sub-range the AL_net_addr 4752 in any Local Attached Network Tuple. 4754 o If N_orig_addr = unknown, then N_will_flooding = WILL_NEVER, 4755 N_will_routing = WILL_NEVER, N_flooding_mpr, N_routing_mpr = 4756 false, N_mpr_selector = false, and N_advertised = false. 4758 o N_in_metric MUST equal the minimum value of the L_in_metric values 4759 of all corresponding Link Tuples with L_status = SYMMETRIC and 4760 L_in_metric != UNKNOWN_METRIC, if any, otherwise N_in_metric = 4761 UNKNOWN_METRIC. 4763 o N_out_metric MUST equal the minimum value of the L_out_metric 4764 values of all corresponding Link Tuples with L_status = SYMMETRIC 4765 and L_out_metric != UNKNOWN_METRIC, if any, otherwise N_out_metric 4766 = UNKNOWN_METRIC. 4768 o N_will_flooding and N_will_routing MUST be in the range from 4769 WILL_NEVER to WILL_ALWAYS, inclusive. 4771 o If N_flooding_mpr = true, then N_symmetric MUST be true, 4772 N_out_metric MUST NOT equal UNKNOWN_METRIC and N_will_flooding 4773 MUST NOT equal WILL_NEVER. 4775 o If N_routing_mpr = true, then N_symmetric MUST be true, 4776 N_in_metric MUST NOT equal UNKNOWN_METRIC and N_will_routing MUST 4777 NOT equal WILL_NEVER. 4779 o If N_symmetric = true and N_flooding_mpr = false, then 4780 N_will_flooding MUST NOT equal WILL_ALWAYS. 4782 o If N_symmetric = true and N_routing_mpr = false, then 4783 N_will_routing MUST NOT equal WILL_ALWAYS. 4785 o If N_mpr_selector = true, then N_advertised MUST be true. 4787 o If N_advertised = true, then N_symmetric MUST be true and 4788 N_out_metric MUST NOT equal UNKNOWN_METRIC. 4790 In each Lost Neighbor Tuple: 4792 o NL_neighbor_addr MUST NOT include this router's originator 4793 address, the O_orig_addr in any Originator Tuple, or equal or have 4794 as a sub-range the AL_net_addr in any Local Attached Network 4795 Tuple. 4797 In each 2-Hop Tuple: 4799 o N2_2hop_addr MUST NOT equal this router's originator address, 4800 equal the O_orig_addr in any Originator Tuple, or equal or have as 4801 a sub-range the AL_net_addr in any Local Attached Network Tuple. 4803 o if N2_in_metric != UNKNOWN_METRIC then N2_in_metric MUST be 4804 representable in the defined compressed form. 4806 o if N2_out_metric != UNKNOWN_METRIC then N2_out_metric MUST be 4807 representable in the defined compressed form. 4809 In each Advertising Remote Router Tuple: 4811 o AR_orig_addr MUST NOT be in any network address in the 4812 I_local_iface_addr_list in any Local Interface Tuple or be in the 4813 IR_local_iface_addr in any Removed Interface Address Tuple. 4815 o AR_orig_addr MUST NOT equal this router's originator address or 4816 equal the O_orig_addr in any Originator Tuple. 4818 o AR_orig_addr MUST NOT be in the AL_net_addr in any Local Attached 4819 Network Tuple. 4821 o AR_orig_addr MUST NOT equal the AR_orig_addr in any other 4822 Advertising Remote Router Tuple. 4824 In each Router Topology Tuple: 4826 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4827 = TR_from_orig_addr. 4829 o TR_to_orig_addr MUST NOT be in any network address in the 4830 I_local_iface_addr_list in any Local Interface Tuple or be in the 4831 IR_local_iface_addr in any Removed Interface Address Tuple. 4833 o TR_to_orig_addr MUST NOT equal this router's originator address or 4834 equal the O_orig_addr in any Originator Tuple. 4836 o TR_to_orig_addr MUST NOT be in the AL_net_addr in any Local 4837 Attached Network Tuple. 4839 o The ordered pair (TR_from_orig_addr, TR_to_orig_addr) MUST NOT 4840 equal the corresponding pair for any other Router Topology Tuple. 4842 o TR_seq_number MUST NOT be greater than AR_seq_number in the 4843 Advertising Remote Router Tuple with AR_orig_addr = 4844 TR_from_orig_addr. 4846 o TR_metric MUST be representable in the defined compressed form. 4848 In each Routable Address Topology Tuple: 4850 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4851 = TA_from_orig_addr. 4853 o TA_dest_addr MUST be routable. 4855 o TA_dest_addr MUST NOT overlap any network address in the 4856 I_local_iface_addr_list in any Local Interface Tuple or overlap 4857 the IR_local_iface_addr in any Removed Interface Address Tuple. 4859 o TA_dest_addr MUST NOT include this router's originator address or 4860 include the O_orig_addr in any Originator Tuple. 4862 o TA_dest_addr MUST NOT equal or have as a sub-range the AL_net_addr 4863 in any Local Attached Network Tuple. 4865 o The ordered pair (TA_from_orig_addr, TA_dest_addr) MUST NOT equal 4866 the corresponding pair for any other Attached Network Tuple. 4868 o TA_seq_number MUST NOT be greater than AR_seq_number in the 4869 Advertising Remote Router Tuple with AR_orig_addr = 4870 TA_from_orig_addr. 4872 o TA_metric MUST be representable in the defined compressed form. 4874 In each Attached Network Tuple: 4876 o There MUST be an Advertising Remote Router Tuple with AR_orig_addr 4877 = AN_orig_addr. 4879 o AN_net_addr MUST NOT equal or be a sub-range of any network 4880 address in the I_local_iface_addr_list in any Local Interface 4881 Tuple or be a sub-range of the IR_local_iface_addr in any Removed 4882 Interface Address Tuple. 4884 o AN_net_addr MUST NOT equal this router's originator address or 4885 equal the O_orig_addr in any Originator Tuple. 4887 o AN_net_addr MUST NOT equal the AL_net_addr in any Local Attached 4888 Network Tuple. 4890 o The ordered pair (AN_orig_addr, AN_net_addr) MUST NOT equal the 4891 corresponding pair for any other Attached Network Tuple. 4893 o AN_seq_number MUST NOT be greater than AR_seq_number in the 4894 Advertising Remote Router Tuple with AR_orig_addr = AN_orig_addr. 4896 o AN_dist MUST NOT be less than zero. 4898 o AN_metric MUST be representable in the defined compressed form. 4900 Appendix E. Flow and Congestion Control 4902 Due to its proactive nature, this protocol has a natural control over 4903 the flow of its control traffic. Routers transmit control messages 4904 at predetermined rates specified and bounded by message intervals. 4906 This protocol employs [RFC6130] for local signaling, embedding MPR 4907 selection advertisement through a simple Address Block TLV, and 4908 router willingness advertisement (if any) as a single Message TLV. 4909 Local signaling, therefore, shares the characteristics and 4910 constraints of [RFC6130]. 4912 Furthermore, the use of MPRs can greatly reduce the signaling 4913 overhead from link state information dissemination in two ways, 4914 attaining both flooding reduction and topology reduction. First, 4915 using MPR flooding, the cost of distributing link state information 4916 throughout the network is reduced, as compared to when using blind 4917 flooding, since only MPRs need to forward link state declaration 4918 messages. Second, the amount of link state information for a router 4919 to declare is reduced to need only contain that router's MPR 4920 selectors. This reduces the size of a link state declaration as 4921 compared to declaring full link state information. In particular 4922 some routers may not need to declare any such information. In dense 4923 networks, the reduction of control traffic can be of several orders 4924 of magnitude compared to routing protocols using blind flooding 4925 [MPR]. This feature naturally provides more bandwidth for useful 4926 data traffic and pushes further the frontier of congestion. 4928 Since the control traffic is continuous and periodic, it keeps the 4929 quality of the links used in routing more stable. However, using 4930 some options, some control messages (HELLO messages or TC messages) 4931 may be intentionally sent in advance of their deadline in order to 4932 increase the responsiveness of the protocol to topology changes. 4933 This may cause a small, temporary, and local increase of control 4934 traffic, however this is at all times bounded by the use of minimum 4935 message intervals. 4937 Authors' Addresses 4939 Thomas Heide Clausen 4940 LIX, Ecole Polytechnique 4942 Phone: +33 6 6058 9349 4943 EMail: T.Clausen@computer.org 4944 URI: http://www.ThomasClausen.org/ 4946 Christopher Dearlove 4947 BAE Systems ATC 4949 Phone: +44 1245 242194 4950 EMail: chris.dearlove@baesystems.com 4951 URI: http://www.baesystems.com/ 4953 Philippe Jacquet 4954 Alcatel-Lucent Bell Labs 4956 Phone: +33 6 7337 1880 4957 EMail: philippe.jacquet@alcatel-lucent.fr 4959 Ulrich Herberg 4960 Fujitsu Laboratories of America 4961 1240 E. Arques Ave. 4962 Sunnyvale, CA, 94085 4963 USA 4965 EMail: ulrich@herberg.name 4966 URI: http://www.herberg.name/